Maker Pro
Maker Pro

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

C

Colin Howarth

Jan 1, 1970
0
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
 
G

Guy Macon

Jan 1, 1970
0
Colin 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?

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.
 
G

Guy Macon

Jan 1, 1970
0
Colin 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?

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.
 
J

John Fields

Jan 1, 1970
0
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
 
K

Ken Smith

Jan 1, 1970
0
Guy Macon 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.

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.
 
J

John Fields

Jan 1, 1970
0
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!
 
R

Rich Grise

Jan 1, 1970
0
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.
If your ALU has a parity bit, you can make an arbitrarily long
(within the limits of the word length) sequence with an AND and
a "branch on parity".

I suppose there should be an "all zeroes" test so that it doesn't
get stuck, but other than that:

PATTERN EQU 00000101 ; this is the set of whichever bits
; you want to XOR for your PSRG.

LOOP: LDA $RANDNO ; Allocating this byte is LAAEFTR. :)
ANDA #PATTERN ; if your AND doesn't clear the
; carry bit, you'll need to clear
; it explicitly - see below
JPE ItsZero ; this evaluates to an XOR of whichever
; bits made it through the AND.
STC ; set the carry bit
ItsZero: ; or don't
ASR 1 ; shift right 1, shifting in the
; 1 or 0 carry bit
TEST A ; exercise the ZERO flag
JNZ DontReset ; the sequence hasn't got stuck at zero
LDA #0x55 ; pick any ol' thing here, just make it
; non-zero
DontReset: STA $RANDNO
OUT @PORT
JMP LOOP

And modifying it for longer words is also LAAEFTR. :)

Hope This Helps!
Rich
 
C

Colin Howarth

Jan 1, 1970
0
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
 
G

Guy Macon

Jan 1, 1970
0
Ken said:
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.

That's a nice trick!

I think I can do even better.

Fill memory with instructions that XOR a preloaded random values
into the accumulator then outputs the result (or XORs the preloaded
random value with the context of the output port if the chip allows).
Tweak a bit here and a bit there so that each time it goes through
the loop the accumulator is Decimal 149 / Hex 95 / Binary 10010101
larger (with overflow modulo 256). 149 is a prime, so it won't
repeat until the 256th loop.

Here are the first 8 values that will be XORed into the results
on the first 8 loops through memory:

10010101
00101010
10111111
01010100
11101001
01111110
00010011
10111011

(This is all off the top of my head, so forgive me if I made an error.)
 
G

Guy Macon

Jan 1, 1970
0
John said:
^^^^^^^^^^^^^^^^^
funny!

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

Guy Macon

Jan 1, 1970
0
Colin said:
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.
 
J

John Fields

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

---
The output of which may or may not be random, depending on how they're
pre-chosen and/or how the table's accessed. Just the term
"pre-chosen" smacks of planning, which is anathema to true randomness.

Consider this 5 bit pseudorandom sequence:

00 00000
01 10000
02 01000
03 00100
04 10010
05 01001
06 10100
07 11010
08 01101
09 00110
10 10011
11 11001
12 11100
13 11110
14 11111
15 01111
16 00111
17 00011
18 10001
19 11000
20 01100
21 10111
22 11011
23 11101
24 01110
25 10111
26 01011
27 10101
28 01010
29 00101
30 00010
31 00001

Now consider that you're going to randomly "pre-choose" numbers from
the sequence and write them to a table which you'll index linearly,
and that the sequence you'll use to randomly select the table entries
is:

00
31
30
17
03
29
09
16
02
..
..
..


Now,fill in the values next to the sequence numbers for a chuckle :)
 
J

John Fields

Jan 1, 1970
0
---
The output of which may or may not be random, depending on how they're
pre-chosen and/or how the table's accessed. Just the term
"pre-chosen" smacks of planning, which is anathema to true randomness.

Consider this 5 bit pseudorandom sequence:

00 00000
01 10000
02 01000
03 00100
04 10010
05 01001
06 10100
07 11010
08 01101
09 00110
10 10011
11 11001
12 11100
13 11110
14 11111
15 01111
16 00111
17 00011
18 10001
19 11000
20 01100 21 10111 <--- 10110 Ooops...
22 11011
23 11101
24 01110
25 10111
26 01011
27 10101
28 01010
29 00101
30 00010
31 00001

Now consider that you're going to randomly "pre-choose" numbers from
the sequence and write them to a table which you'll index linearly,
and that the sequence you'll use to randomly select the table entries
is:

00
31
30
17
03
29
09
16
02
.
.
.


Now,fill in the values next to the sequence numbers for a chuckle :)
 
G

Guy Macon

Jan 1, 1970
0
John said:
Just the term "pre-chosen" smacks of planning, which is
anathema to true randomness.

Call it cached random nunbers then.
 
A

artie

Jan 1, 1970
0
If you're interested in theory, still one of the best works is Donald
Knuth's "Seminumerical Algorithms," Vol. 2 of his series. The first
chapter of Vol. 2 is devoted to generating and testing (pseudo)random
numbers.

The Xilinx app note (APP052) is still a concise reference for LFSR taps
up to a very long length.

And for true random bits, you can't beat Hotbits --
http://www.fourmilab.ch/hotbits/

"Anyone who considers arithmetical methods of producing random digits
is, of course, in a state of sin."

--John Von Neumann, 1951



--
 
Top