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.
