I. RND-generators
for shift registers
You've probably already heard of such a gene
operators. They are widely used in shemote
hnike: for example, is a generator with
rented the noise in the AY-Ke. In English such n
erator called LFSR (linear feedback
shift register).
Their operating principle can be understood from
Pictures:
V
XOR
trigger a
...
K1-th tap ...
V ...
...
Trigger 2 ...
...
K2-th tap ...
V ...
...
trigger 3 ...
...
...
V ................
........... ................
Km-LIMITED removal ...
V
trigger N
V
output
Set of triggers 1 .. N is
shift register that shifts bits in this
If the top vniz.S * some * triggers
K1, K2, ..., Km, as well as the most recent
trigger signals are removed, a heap XOR'yatsya
and fed to the input shift register.
Output is a 1-bit.
The theory states that for every N susches
tvuet a set K1 .. Km, that the period gene
the generated sequence is the maxim
flax possible - 2 ^ N-1 (clearly, if at
all flip-flops 0, then not change anything
is because the state of all flip-flops of
runs all the options, except for zero) [2].
Examples of generators for some N,
in which to obtain consistently
STPs are the maximum length of a sufficient challenge
[1]:
N = 3, K = 2
N = 4, K = 3
N = 5, K = 3
N = 6, K = 5
N = 7, K = 6
N = 9, K = 5
N = 10, K = 7
N = 11, K = 9
N = 15, K = 14
N = 17, K = 14
N = 18, K = 11
N = 20, K = 17
N = 21, K = 19
N = 22, K = 21
N = 23, K = 18
N = 25, K = 22
N = 28, K = 25
N = 29, K = 27
N = 31, K = 28
N = 33, K = 20
N = 35, K = 33
N = 36, K = 25
N = 39, K = 35
Sequence generator maxim
belorussian length for N = 8,16,24,32 [1], [3]:
N = 8, K1 = 4, K2 = 5, K3 = 6
N = 16, K1 = 4, K2 = 13, K3 = 15
N = 24, K1 = 17, K2 = 22, K3 = 23
N = 32, K1 = 22, K2 = 2, K3 = 1
A list of outlets at which we obtain
sequence of maximum length for
all N up to 168 is given in [3].
An example of a generator for N = 4:
1: 0001
2: 1000
3: 0100
4: 0010
5: 1001
6: 1100
7: 0110
8: 1011
9: 0101
10: 1010
11: 1101
12: 1110
13: 1111
14: 0111
15: 0011
1: 0001
etc.
Example implementation of an oscillator with N = 15,
K = 14 for Z80:
LFSR9
; OUT: carry flag
SEED EQU $ +1
LD HL, 1, any nonzero number
LD A, H; bit 13 (numbered from 0)
RLCA
XOR H; bit 13 ~ bit 14
RLCA
RLCA; to carry
ADC HL, HL; vdvinuli
LD (SEED), HL
RET
The main drawback of such generators
lies in the fact that their output - a random
(Actually - a pseudo-random) BIT.Esli
in the above generator as
random value to take, for example, byte
Word from the register or HL, a chance to
They will be at least - only one new random
bits (see also the state table generator
for N = 4).
If you want the random bytes, then
require other podhody.Odin possible
- The use of linear congruent n
generators (of the form X [n +1] = (A * X [n] + B) mod M),
this issue in detail in [4].
Another option - the use of productivity
dnyh of LFSR generators.
II. Based on LFSR
the random bytes
As written in clever books [4], one
of such generators invented Mitchell'om
and Moore'om and has the form:
X [n] = (X [n-24] + X [n-55]) mod m
If m = 2 ^ k, then the period of such a generator
(2 ^ 55-1) · 2 ^ (k-1) that in the case of bytes
is 2 ^ (55-1) · 2 ^ 7 2 ^ 62 ¢ ¢ 4.6 × 10 ^ 18.
You can see that for LSB
such a generator is a LFSRgenerator (in this case, N = 55, K =
24). Could be used instead of addition
operation XOR, in which case we would have 8
55-bit LFSR, generating different
phase sequence of length 2 ^ 55-1 bits
and be combined into 1 byte. Instead LFSR with
parameters N = 55, K = 24 can be used
any other with the sequence of maximal
normal length.
Placing on the Z80 (with a table 256 bytes):
DO_RND
; OUT: A or B or C - random bytes
LD H, 'PRT_RND; 256-byte
; Table
CURND LD A, 0
INC A
LD (CURND +1), A; not random
; Room, but only
; Pointer in the table
LD L, A
LD B, (HL)
ADD A ,55-24
LD L, A
LD C, (HL)
ADD A, 24
LD L, A
LD A, B
ADD A, C
LD (HL), A
; In registers A, B and C are random
; Values that are separated from each other
And several tens of counts
RET
Before using such a generator
should write at least 1 non-zero bytes
in table PRT_RND, but to a random number
received good immediately - better filling
thread chart some data with boleemenee uniform distribution of
all bytes. The annex contains ALASM'ovy
sorets this generator is a procedure initiated
realizations.
lvd ^ mHm lvd@dgap.mipt.ru
Literature:
1. P. Horowitz, W. Hill. Art
circuitry, gl.9.
2. http://en.wikipedia.org/wiki/
Linear_feedback_shift_register
3. http://www.xilinx.com/bvdocs/
appnotes/xapp052.pdf
4. Knuth. Art
Programming ", Volume 2, Chapter 3.
