Из журнала Info Guide #10, Рязань, 05.2007 О некоторых RND-генераторах Lord Vader 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.