Re: 8 Bit Random Numbers

On Wed, 4 Feb 2009 19:59:22 -0800 (PST), Bill
Bowden <wrongaddress@xxxxxxx> wrote:

On Feb 4, 2:14 am, Nobody <nob...@xxxxxxxxxxx> wrote:

For your original sequence of 3,4,5,7, use 0xB8 or 0x1D, depending upon
the shift direction. The following C code generates the same bit sequence
using both Fibonacci and Galois implementations.

Note that the two versions generate the same bit sequences, but the
sequence of 8-bit states differs.

#include <stdio.h>

typedef unsigned char byte;

byte f_taps = 0x1D; /* 0001 1101 */
byte g_taps = 0xB8; /* 1011 1000 */

byte xor(byte x)
{
x = (x & 0x0F) ^ (x >> 4);
x = (x & 0x03) ^ (x >> 2);
x = (x & 0x01) ^ (x >> 1);
return x;

}

byte f(byte *x)
{
byte t = xor(*x & f_taps);
*x >>= 1;
*x |= t << 7;
return t;

}

byte g(byte *x)
{
byte t = *x & 1;
byte k = (-t) & g_taps;
*x >>= 1;
*x ^= k;
return t;

}

int main(void)
{
byte x = 1, y = 1;
int i;

for (i = 0; i < 0x100; i++) {
byte tx = f(&x);
byte ty = g(&y);
printf("%d %d\n", tx, ty);
}

return 0;

}


Thanks for the C code, but my knowledge of C is limited, and it may be
a little slow to implement.

I found an assembly program for a PIC processor on the web which
requires 10 lines of code, or maybe 44 clock cycles.

The idea is to shift the random register left and obtain the result in
the working register (w) and then shift the register again which rolls
around the carry bit to the first bit, again in (w). Then the three
feedback bits are tested to determine the new input bit and the result
fed to the lowest bit.

Looks pretty speedy, but I was thinking the parallel approach might
reduce the 44 clocks to a lower number.

What I'm not understanding with the parallel approach is how the 8 bit
result from xoring a constant 8 bits is converted to a single bit to
be shifted into the register. In other words, if I xor
B8 with the contents of the random register, I get some new 8 bit
number. What can I do with that? How does the new 8 bit result resolve
to a single bit?

Main:

RLF RANDOM,0
RLF RANDOM,0
BTFSC RANDOM,3
XORLW 1
BTFSC RANDOM,4
XORLW 1
BTFSC RANDOM,5
XORLW 1
MOVWF RANDOM
GOTO Main



The parallel approach is what I was trying to
explain (perhaps not well enough) at the end of my
post of 1-28-09. You need to think of the whole
operation as a set of completely independent
parallel shift registers. The number of shift
registers is the number of bits in a register
(byte, word, or dword). The number of bits in a
single shift register is the number of memory
locations you dedicate to this.

Keeping that in mind, the overall operation uses
the same logic as a simple single-register LFSR,
but it's much easier. The Nth memory location is
now the Nth bit, so you XOR memory locations
directly. There are no rotate or shift
instructions... instead, you manipulate the index
into the memory array. The new 8-bit result
(assuming you use byte-sized memory) is 8
independent single-bit LFSR outputs at once.

Note that the LFSRs never actually do any
"shifting"... only your memory pointer changes so
that you regard different locations as different
LFSR bits after each crank of the machine.

The memory pointer math requires careful thought
to optimize for speed. A circular buffer topology
is essentially what you want here, but the problem
is that LFSRs are typically *not* powers of 2 (at
least, the efficient single-XOR types). That
makes it hard to wrap the pointer around at the
ends... you can't use a simple mask on the pointer
as you can with power-of-2, you need specific
test-and-branch comparisons.

A way around this is to use a larger power-of-2
mask, and adjust your thinking so that the memory
locations representing the LFSR are a subset that
"walks" around the larger memory array. This will
take a fair amount of pencil-and-paper chicken
tracks to work out, but the code will be faster.

Best regards,


Bob Masta

DAQARTA v4.51
Data AcQuisition And Real-Time Analysis
www.daqarta.com
Scope, Spectrum, Spectrogram, Sound Level Meter
FREE Signal Generator
Science with your sound card!
.

Relevant Pages

  • Re: Breaking LFSR.
    ... Irregular decimation isn't, but see below. ... testing this claim with some software models of 6-8 LFSR. ... in Solomon Golomb's "Shift Register Sequences". ... the important thing is that the number of shift must not have ...
    (sci.crypt)
  • Re: Mplayer: "Little-Endian"
    ... |> or written to memory. ... Shift operations are named are defined as if ... the bits in a register are arranged as they would be if they were ... Addr Endian Endian ...
    (comp.os.linux.misc)
  • Re: Mplayer: "Little-Endian"
    ... |> or written to memory. ... Shift operations are named are defined as if ... the bits in a register are arranged as they would be if they were ... Addr Endian Endian ...
    (comp.os.linux.misc)
  • Re: can somebody help me with the problem with tasm models
    ... When Intel created the x86 originally, ... registers...now, when addressing memory with something like "", this ... valid...the rest aren't yet wired in and are ignored in memory addressing ... "offset" register, this would give a 20-bit address...if, in time, they ...
    (alt.lang.asm)
  • Re: Multiplexing - how to speed up
    ... Currently I'm testing with 5 cascaded shift registers (serial in, ... After adding the 5th shift register the image started flickering. ... void shift_byte ... internal buffer but not to the output pins of that register. ...
    (sci.electronics.design)