Железо - О некоторых RND-генераторах.

<b>Железо</b> - О некоторых RND-генераторах.

           I. RND-генераторы
         на сдвиговых регистрах

   Наверняка  вы уже слышали о таких гене─
раторах. Они широко применяются в схемоте─
хнике: например,именно такой генератор со─
здаёт  шум в AY-ке. По-английски такие ге─
нераторы  называются LFSR (linear feedback
shift register).
   Принцип  их  действия  можно  понять из
картинки:
 

       ┌───────────────────┐
       │                   │
       V                ┌──────┐
  ┌─────────┐           │ XOR  │
  │триггер 1│           └──────┘
  └─────────┘            ││...│
       ┌─────K1-ый отвод─┘│...│
       V                  │...│
  ┌─────────┐             │...│
  │триггер 2│             │...│
  └─────────┘             │...│
       ┌──────K2-ый отвод─┘...│
       V                   ...│
  ┌─────────┐              ...│
  │триггер 3│              ...│
  └─────────┘              ...│
       ┌───────────────────...│
       V      ................│
  ........... ................│
       ┌──────Km-ный отвод─...│
       V                      │
  ┌─────────┐                 │
  │триггер N│                 │
  └─────────┘                 │
       ┌──────────────────────┘
       │
       V
    выход

   Набор триггеров 1..N представляет собой
сдвиговый регистр,сдвигающий биты в данном
случае сверху вниз.С *некоторых* триггеров
K1,K2, ...,Km, а также с выхода последнего 
триггера снимаются сигналы,XOR'ятся в кучу
и  подаются  на  вход сдвигового регистра.
Выход является 1-битным.

   Теория гласит, что для каждого N сущес─
твует такой набор K1..Km, что период гене─
рируемой последовательности равен максима─
льно возможному - 2^N-1 (ясно, что если во
всех  триггерах  0, то  ничего меняться не
будет,потому состояние всех триггеров про─
бегает все варианты,кроме нулевого) [2].

   Примеры  генераторов  для  некоторых N,
при которых для получения последовательно─
сти максимальной длины достаточно 1 отвода
[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 

   Генераторы последовательностей максима─
льной длины для 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 

   Список отводов, при которых  получается
последовательность максимальной длины, для
всех N до 168 дан в [3].

   Пример состояний генератора для 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 
и т.д.

   Пример  реализации  генератора  с N=15,
K=14 на Z80: 

 LFSR9 
        ;OUT: carry flag

 SEED    EQU   $+1 
         LD    HL,1  ;любое ненулевое число
         LD    A,H   ;бит 13 (нумеруем с 0)
         RLCA
         XOR   H     ;бит 13^бит 14
         RLCA
         RLCA        ;в carry
         ADC   HL,HL ;вдвинули
         LD    (SEED),HL
        RET

   Основной  недостаток  таких генераторов
заключается в том,что их выход - случайный
(на самом деле - псевдослучайный) БИТ.Если
в  вышеприведённом  генераторе  в качестве
случайного  значения брать, например, байт
или  ворд из регистра HL, то случайности в
них будет минимум - лишь 1 новый случайный
бит (см.также таблицу состояний генератора
для N=4 ).

   Если нужен генератор случайных байт, то
требуются другие подходы.Один из возможных
- использование  линейных конгруэнтных ге─
нераторов (вида X[n+1]=(A*X[n]+B) mod M ),
этот вопрос подробно рассмотрен в [4].
   Другой вариант - использование произво─
дных от LFSR генераторов.

          II. Основанный на LFSR
         генератор случайных байт

   Как  написано в умных книжках [4], один
из таких генераторов  придуман Mitchell'ом
и Moore'ом и имеет вид:
 

    X[n] = ( X[n-24] + X[n-55] ) mod m

   Если m=2^k, то период такого генератора
(2^55-1)·2^(k-1), что  для  случая  байтов 
составит 2^(55-1)·2^7 ў 2^62 ў 4.6·10^18.

   Можно  заметить, что  для младшего бита
такой  генератор  представляет собой LFSR-
генератор (в данном  случае  N=55, K=24 ).
Можно было бы вместо сложения использовать
операцию  XOR, в этом случае мы имели бы 8
55-битовых  LFSR,  генерирующих  различные
фазы  последовательности длиной 2^55-1 бит
и  комбинируемые  в  1 байт. Вместо LFSR с
параметрами  N=55, K=24 можно использовать
любой  другой с последовательностью макси─
мальной длины.

  Реализация на Z80 (с таблицей 256 байт):

 DO_RND 
      ;OUT: A или B или C - случайный байт
 

         LD    H,'PRT_RND ; 256-байтовая
                         ;таблица
 CURND   LD    A,0 
         INC   A
        LD    (CURND+1),A ; не случайный
                        ;номер, а лишь
                       ;указатель в таблице
         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
;в регистрах A, B и С находятся случайные 
;величины, отстоящие друг от друга на 
 ;несколько десятков отсчётов 
        RET

   Перед  использованием такого генератора
следует  записать хотя бы 1 ненулевой байт
в таблицу PRT_RND, а чтобы случайные числа
получались  хорошими  сразу - лучше запол─
нить таблицу каким-нибудь данными с более-
менее   равномерным   распределением  всех
байт. В  приложении  приводится ALASM'овый
сорец этого генератора с процедурой иници─
ализации.

lvd^mHm  lvd@dgap.mipt.ru 

               Литература:
 

  1. П. Хоровиц, У. Хилл. "Искусство
 схемотехники", гл.9. 
  2. http://en.wikipedia.org/wiki/
 Linear_feedback_shift_register 
  3. http://www.xilinx.com/bvdocs/
 appnotes/xapp052.pdf 
  4. Д. Кнут. "Искусство
программирования", т.2, гл.3.