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

[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?

Thanks,

colin

 

[Colin Howarth]

On 2004-11-14 03:32:38 +0100, artie <artie.m@gmail.com> said:

Check out Xilinx App note XAPP 052, which is a great reference on
pseudo-random sequence generators using linear feedback shift
registers.

http://www.xilinx.com/bvdocs/appnotes/xapp052.pdf

Thanks, I'd just found LFSRs in google - and there are a lot of them
This was just whhat i was looking for, thanks.


colin

 

[Guy Macon]

Colin Howarth wrote:

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?

Do a websearch on "Linear Feedback Shift Register".

You might be able to get the RC4 algorithm running at the speed
you are looking for with some careful coding.

 

[Guy Macon]

Colin Howarth wrote:

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?

I had just hit send when it occured to me that your application is
a perfect match for filling all of memory with output instructions,
each putting out a pre-chosen random number.

 

[John Fields]

On Sun, 14 Nov 2004 03:08:19 +0100, Colin Howarth
<colinDEL@howarth.de> wrote:

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?

---
Here's the BASIC source code for a 5 bit pseudo-random sequence
generator. Increase the length of the shift register and change the
location of the taps to get a longer repeat and different sequences.

If you want to see it run and you don't have a
compiler/interpreter/whatever, ask and I'll post an executable to
abse.


'5 bit pseudo-random sequence generator with no lockup state.
'03 December 2001
'John Fields


SCREEN 0
COLOR 0, 7
CLS

q1 = 0
q2 = 0
q3 = 0
q4 = 0
q5 = 0
clk = 0
new$ = "0"

PRINT "CLOCK Q1 Q2 Q3 Q4 Q5"

VIEW PRINT 2 TO 25


shift: IF clk < 10 THEN PRINT clk; " "; q1; q2; q3; q4; q5: GOTO
skip
PRINT clk; " "; q1; q2; q3; q4; q5

skip: nor = q1 OR q2 OR q3 OR q4
IF nor = 0 THEN nor = 1 ELSE nor = 0

tap = q3 XOR q5

srin = nor XOR tap

q5 = q4
q4 = q3
q3 = q2
q2 = q1
q1 = srin

clk = clk + 1
IF clk = 33 THEN clk = 1

old$ = new$
WHILE old$ = new$
new$ = TIME$
WEND

GOTO shift
END

--
John Fields

 

[Ken Smith]

In article <10pdphldufn0mb0@corp.supernews.com>,
Guy Macon <http://www.guymacon.com> wrote:
[...]

I had just hit send when it occured to me that your application is
a perfect match for filling all of memory with output instructions,
each putting out a pre-chosen random number.

This sort of idea works quite well. I've used it. There is a little
trick that makes the sequence even longer. If instead of simply
outputting the value from the memory, the values are used in a running sum
the sequence length can be at least doubled.

--
--
kensmith@rahul.net forging knowledge

 

[John Fields]

On Sun, 14 Nov 2004 04:59:16 +0000, Guy Macon
<http://www.guymacon.com> wrote:

I had just hit send when it occured to me that your application is
a perfect match for filling all of memory with output instructions,
each putting out a pre-chosen random number.
^^^^^^^^^^^^^^^^^

funny!

--
John Fields

 

[ChrisGibboGibson]

Rich Grise wrote:

LAAEFTR

Eh ?

Gibbo

 

[Colin Howarth]

On 2004-11-14 19:40:04 +0100, chrisgibbogibson@aol.com (ChrisGibboGibson) said:

Rich Grise wrote:

LAAEFTR


Eh ?

Gibbo

Left as an exercise for the reader, presumably.

colin

 

[Colin Howarth]

On 2004-11-14 05:59:16 +0100, Guy Macon <http://www.guymacon.com> said:

I had just hit send when it occured to me that your application is
a perfect match for filling all of memory with output instructions,
each putting out a pre-chosen random number.

Hmmm, do you have a script for generating the source code?

colin

 

[Chaos Master]

ChrisGibboGibson > /dev/null :

Rich Grise wrote:

LAAEFTR


Eh ?

Left As An Exercise For The Reader.

[]s
--
Chaos MasterŽ, posting from Brazil.
"It's not what it seems, not what you think. No, I must be dreaming."

http://marreka.no-ip.com | http://tinyurl.com/46vru
http://renan182.no-ip.org | http://marreka.blogspot.com (in Portuguese)

 

[Guy Macon]

John Fields wrote:

pre-chosen random number.
^^^^^^^^^^^^^^^^^
funny!

Why so? That's the correct term for a table filled with
numbers that were generated by a random number generator.

 

[Guy Macon]

Colin Howarth wrote:

On 2004-11-14 05:59:16 +0100, Guy Macon <http://www.guymacon.com> said:

I had just hit send when it occured to me that your application is
a perfect match for filling all of memory with output instructions,
each putting out a pre-chosen random number.

Hmmm, do you have a script for generating the source code?

Other than the random value, its the same few instructions repeated
over and over. I would use a text editor such as Ultra-Edit-32 as
follows:

FAST VERSION:

Generate 32K of random numbers ( [ http://www.fourmilab.ch/hotbits/ ]
and [ http://www.fourmilab.ch/hotbits/generate.html ] has some).

set the line length to two characters, and convert wrap to hard
returns.

Search and replace each hard return with your bit of code.

truncate at whatever point gives you 64K.

SLOW VERSION WITH MORE RANDOM NUMBERS:
Same as above, but put the random numbers in a big data table
and write a small tight loop that grabs them and outputs them.

Also see my other post about using XOR to increase cycle time 256x.

 

[Guy Macon]

John Fields wrote:

Just the term "pre-chosen" smacks of planning, which is
anathema to true randomness.

Call it cached random nunbers then.

 

[Tim Shoppa]

Colin Howarth <colinDEL@howarth.de> wrote in message news:<cn6emi$epu$00$1@news.t-online.com>...

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]

On Mon, 15 Nov 2004 05:25:03 -0800, Tim Shoppa wrote:

Colin Howarth <colinDEL@howarth.de> wrote in message news:<cn6emi$epu$00$1@news.t-online.com>...
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.)

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]

On 2004-11-14 03:08:19 +0100, Colin Howarth <colinDEL@howarth.de> said:

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]

Colin Howarth wrote:

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.

 

[bogax]

Rich Grise <rich@example.net> wrote in message news:<pan.2004.11.15.18.29.38.564926@example.net>...

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/

 

[Colin Howarth]

On 2004-11-15 20:25:33 +0100, Rich Grise <rich@example.net> said:

On Mon, 15 Nov 2004 05:25:03 -0800, Tim Shoppa wrote:

Colin Howarth <colinDEL@howarth.de> wrote in message
news:<cn6emi$epu$00$1@news.t-online.com>...
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.)

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.

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 .

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