Iron - Some RND-generators.

           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.