Can you help with a simple generator for a random series of bits?

[Tim Shoppa]

I'd like to test an RS-485 network using eye patterns.

For this I need an NRZ code i.e. a random sequence of 1's and 0's.

I'd like to use a uC (ATmega8 16 MHz). The code frequency should be
several MHz.

I'm not going to say it's impossible to do this with a 16MHz Atmega8.
Probably the most effective way to do it is as others have suggested,
with a look-up table that you step through. Doing the software
emulation of a pseudorandom generator through a shift register and
XOR's is "easy" but writing code tight enough to make the resulting bit
rate be several MHz will require some clverness (often intermediate
look-up tables to do multiple shifts in one swell fwoop.)

OTOH if you just use a shift register and some XOR's you can easily
do this with two non-programmable chips that will easily run at a rate
in the 10's of MHz. Maybe even less PCB real-estate than the CPLD solutions
others have suggested .

Tim.

 

[Rich Grise]

I'm not going to say it's impossible to do this with a 16MHz Atmega8.
Probably the most effective way to do it is as others have suggested,
with a look-up table that you step through. Doing the software
emulation of a pseudorandom generator through a shift register and
XOR's is "easy" but writing code tight enough to make the resulting bit
rate be several MHz will require some clverness (often intermediate
look-up tables to do multiple shifts in one swell fwoop.)

If your processor has a parity flag, you can do the whole XOR in one
AND instruction. I posted a quick little loop in another post.

OTOH if you just use a shift register and some XOR's you can easily
do this with two non-programmable chips that will easily run at a rate
in the 10's of MHz. Maybe even less PCB real-estate than the CPLD solutions
others have suggested .

Also true.

Cheers!
Rich

 

[Colin Howarth]

OK, I tried a couple of LFSR things. (From which it appears that the
AVR is not the ideal chip to do this with,
since you can only shift registers one bit at a time, but I have
several lying aound

From the xilinx XAPP 52 appnote it appears that the taps for 16 bits
are Q16,Q15,Q13 and Q4.
I hope I've understood things correctly and that all bits get shifted
up one bit, and the new bit Q1
is Q16 xor Q15 xor Q13 xor Q4 (old positions).

I have the bits stored in two bytes called "low" and "high".

First I made a copy of high and copied Q4 to Q14, swapped nibbles,
cleared the upper nibble and used
what was left as an index to a 16 byte table of results of xor of Q16:Q13.

But then I found some clverness and noticed that a 17 bit LFSR only
taps Q17 and Q14. So since I can shift
registers through the carry flag, the carry flags became bit 17.

If your processor has a parity flag, you can do the whole XOR in one
AND instruction. I posted a quick little loop in another post.

Unfortunately, it doesn't.

You mean, warm up my soldering iron?!


Here's my attempt.


ldi low, $EB ; random seed
ldi high, $55 ; I don't think it's my birthday in hex, anyway.

loop:

sbc tmp, tmp ; subtract with carry ie, tmp = tmp - tmp - C, ie.
if C = 0 then tmp = 0, else tmp = -1 = 1111.1111
bst high, 6 ; store bit Q14 in flag T of status register
brtc t_0 ; jump to t_0 if T is 0, ie C xor 0 = C
inc tmp ; otherwise C <- not C
t_0: ; the last bit of tmp is now C xor T ie. Q17 xor Q14
ror tmp ; rotate last bit into C
rol low ; rotate C into bit 0 of low
rol high ; and bit 7 of low into bit 0 of high, and bit 7 of high into C

out PORTC, high ; output the whole byte. All those bits - what a waste ;-(

rjmp loop


which can be reduced further by fiddling even more with the carry flag

loop:

sbc tmp, tmp ; subtract with carry ie, tmp = tmp - tmp - C, ie.
if C = 0 then tmp = 0, else tmp = -1 = 1111.1111
; status of C is maintained, a "copy" of C is made in tmp, and
tmp doesn't need initialising

bst high, 6 ; store bit Q14 in flag T of status register
brtc t_0 ; jump to t_0 if T is 0, ie C xor 0 = C
subi tmp, 1 ; if tmp = 0, then C is set, if tmp = -1 then C is cleared
t_0: ; C is now C xor T
rol low ; rotate C into bit 0 of low
rol high ; and bit 7 of low into bit 0 of high, and bit 7 of high into C

out PORTC, high ; output the whole byte. All those bits - what a waste ;-(

rjmp loop


This is 9 CLKs which at 16 MHz is nearly 1.8 MHz.
The nice things is that for 8n + 1 bits you always need only 2 taps
instead of 4.
So, for 25 bits it would simply be

rol low
rol med
rol high

after that you need to think of better names for the registers (and
adjust the bst instruction).

Anyway, thanks to all who replied.

colin

 

[Colin Howarth]

I'd like to test an RS-485 network using eye patterns.

For this I need an NRZ code i.e. a random sequence of 1's and 0's.

I'd like to use a uC (ATmega8 16 MHz). The code frequency should be
several MHz.

How does that pseudorandom thing with shift registers go?
Is it just shift, add, add or something like that ? (hopeful grin

Actually, I thought it might be easier just to connect a mega-ohm
resistor across the
analog comparator but I guess the Johnson noise would be less than the
comparator
offset voltage (and in any case I don't know how quickly the comparator
reacts).

Any ideas?

Hey! I noticed that although this is an electronics group, there
weren't ANY suggestions for a *real* random number generator using the
analog comparator
and some real random noise :-(


colin

 

[Guy Macon]

Hey! I noticed that although this is an electronics group, there
weren't ANY suggestions for a *real* random number generator using the
analog comparator and some real random noise :-(

IMO, it would be more trouble than it's worth for this application.
A HRNG pretty much requires a Von Neumann Compensator, and a simple
PRNG is about as easy to make as a VNC.

 

[John Fields]

Hey! I noticed that although this is an electronics group, there
weren't ANY suggestions for a *real* random number generator using the
analog comparator
and some real random noise :-(

---
OK

+V>------+---------+----+--------+
| | | |
[R] [R] [R] [R]
| | | |
+----[C]--+----|--|+\ |
| | | | >--+--->OUT
| | +--|-/
|K | |
[ZENER] [R] [R]
| | |
GND>-----+---------+----+------------>GND

 

[bogax]

If your processor has a parity flag, you can do the whole XOR in one
AND instruction. I posted a quick little loop in another post.

Ever heard of a Galois LFSR ?

http://learn.ouhk.edu.hk/~mt888/url/Unit9/2/m_sequence_linear_feedback_shift_register_lfsr.htm

lists of taps too

LFSR Testbench is fun to play with too

http://www.logiccell.com/~jean/LFSR/