Файл: Яковлев, В. В. Стохастические вычислительные машины.pdf

Генерирование псевдослучайных чисел Х к с равномерным за­ коном распределения в большинстве практических случаев осно­ вывается на решении следующего рекуррентного соотношения:

где В , С, R — постоянные числа.

Алгоритмы, основанные на вычислениях по формуле (7.1), довольно просто реализуются на ЦВМ, однако они малопригодны для использования в СтВМ, поскольку для этого требуется нали­ чие сложного арифметического устройства.Кроме того, присутствие

операции умножения привело бы к ограничению быстродействия центрального генератора управляющих сигналов СтВМ.

Для построения ГПСЧ стохастических вычислительных ма­ шин применяется метод формирования псевдослучайных чисел с равномерным распределением, основанный на использовании линейной двоичной последовательности, генерируемой в соответ­ ствии с рекуррентным соотношением

где к — номер машинного такта; ak — 0 или 1 — символы после­ довательности; а (- = 0 или 1 — постоянные коэффициенты; знак

означает суммирование по модулю 2.

Преимущество метода заключается в простоте устройства» реализующего зависимость (7.2). Все устройство состоит из т-раз- рядного регистра сдвига и набора сумматоров по модулю 2 в цепи обратной связи (рис. 115). Регистр сдвига выполняет функцию хранения предшествующих т символов последовательности а*_15 ак_ 2, . . ., ak_m, а сумматоры в цепи обратной связи производят вычисление последующего символа ак в соответствии с выраже­ нием (7.2). Набор коэффициентов а г (г = 1, 2, . . ., т) задает структуру цепи обратной связи регистра сдвига. При этом равен­ ство а { = 1 означает наличие соединения i-ro разряда регистра с сумматором, а а г = 0 — отсутствие такого соединения.

239

При соответствующем выборе коэффициентов а,- последователь­ ность двоичных символов ак, генерируемая устройством, может иметь максимально возможный (для данного т) период М = 2т —

— 1. Такая последовательность характеризуется равновероят­ ностью и случайностью появления нулей и единиц [63] подобно

<*)

Рис. 116. Генератор двоичной последовательности максималь­ ной длины (а) и граф последовательности состояний регистра сдвига (б)

истинно случайной последовательности, и поэтому она получила название псевдослучайной последовательности максимальной длины.

Получение такой последовательности можно показать на при­ мере генератора с четырехразрядным регистром сдвига (рис. 116, а). Произвольный к-й символ двоичной последовательности, гене­

240

дулю 2. Если исходное состояние регистра (xlt х 2, х3, ж4) = (1 ,0 , 0, 0), то на выходе цепи обратной связи будет генерироваться по­ следовательность с периодом М = 15 ...111010110010001...

Последовательность состояний регистра сдвига приведена на рис. 116, б. Из шестнадцати возможных состояний отсутствует только одно состояние (0,0,0,0), которое является запрещенным. Если регистр сдвига установить в нулевое состояние, то генери­ руемая им последовательность будет состоять только из одних нулей.

Последовательность двоичных чисел, формируемых разрядами регистра сдвига на рис. 115, может обладать свойствами последо­ вательности случайных чисел с равномерным распределением. Изучение этого вопроса начнем с исследования свойств псевдослу­ чайных последовательностей максимальной длины.

38. Условия генерирования и свойства псевдослучайных последовательностей максимальной длины

Поведение схемы на рис. 115 можно описать в виде следующей матрицы:

где значения коэффициентов a i , a 2, . . ., а т £ (0,1) определяются видом обратной связи регистра сдвига. Элементы первой строки матрицы ||Л|| определяют операцию, осуществляемую суммато­ рами по модулю 2 цепи обратной связи, а единичные элементы

бивается на ряд подмножеств или циклов, каждый из которых может генерироваться схемой, если первоначальное состояние регистра будет соответствовать какому-либо вектору X из данного подмножества. При этом каждому циклу соответствует своя по­ следовательность двоичных символов с периодом, равным периоду цикла.

В зависимости от свойств матрицы ||М|| генератор последова­ тельностей на основе регистра сдвига с линейной обратной связью может иметь один нулевой — тривиальный цикл с периодом М = = 1 и некоторое число нетривиальных циклов одинаковой или разной длины. Генератору последовательности максимальной длины соответствует предельный случай, когда вся совокупность нетривиальных циклов состоит только из одного цикла макси­ мальной длины М = 2т — 1.

Циклические свойства генератора последовательностей пол­ ностью определяются характеристическим многочленом

ф(х) = х"1 + а1хт_1 + а2хт -2+ . . . + а т ,

которым является определитель матрицы |А + х^Ц, образо­ ванной прибавлением переменной х к диагональным элементам матрицы |^41|. Так для схемы, изображенной на рис. 116, а, ха­ рактеристический многочлен запишется в виде

схемой, связаны с понятиями приводимости и примитивности многочлена ф (х). Если многочлен ф (х) степени т не делится ни на какой другой многочлен от х пониженной степени, то такой многочлен называется неприводимым. Примитивность ф (х) озна­ чает, что он не является сомножителем к многочлену xs + 1 для любого s меньшего, чем (2т — 1). Если характеристический много­ член ф (х) неприводим и примитивен, то схемой генерируется по­

1 Необходимо пояснить, что действия над многочленами производятся по правилам арифметики по модулю 2, в которой сложение равносильно вы­ читанию, т. е. х* + х* = 0.

подставив значения коэффициентов а,- многочлена <р(х) в рекур­ рентное соотношение (7.2) и решая его для каждого к (к = 0, 1,

ной последовательности равен числу различных состояний регистра в данном цикле, а сумма периодов всех последовательностей — полному числу состояний (24 — 1).

Таким же образом можно показать, что непримитивный много­

М= 5.

Итак, основной задачей синтеза генератора псевдослучайной

последовательности максимальной длины М = 2т — 1 является нахождение многочлена т-ж степени, удовлетворяющего назван­ ным условиям. Расстановка связей от разрядов регистра сдвига к сумматорам по модулю 2 цепи обратной связи (рис. 115) произ­ водится в соответствии с коэффициентами а, этого многочлена.

Известно, что для данного т существует точно Ф (М} = 2т —

— 1 )]т различных многочленов, являющихся неприводимыми и примитивными. Функция Ф (М), называемая функцией Эйлера, представляет количество положительных целых чисел меньших или равных М и взаимно простых с М . Так как число Ф (М) с ро­ стом т очень быстро растет, то число многочленов степени т , порождающих последовательности максимальной длины, с ростом т также быстро увеличивается. Если при т = 8 оно равно 16, то при т = 16 это число уже равно 2048. Среди множества много­ членов заданной степени можно отыскать многочлен, имеющий минимальное число ненулевых коэффициентов а,-. Этому случаю будет соответствовать технически простейшая реализация генера­ тора, так как при этом цепь обратной связи регистра сдвига будет

стей максимальной длины с одним сумматором в цепи обратной связи, соединенным с т-м и i-м разрядами регистра сдвига. Если один из входов сумматора подключить не к i-му, а к (т — £)"МУ разряду регистра, то устройство будет генерировать последова­ тельность максимальной длины с обратным порядком следования двоичных символов.

Исчерпывающую таблицу всех неприводимых многочленов любой степени вплоть до т = 34 можно найти в [52], а в [97] приводится таблица многочленов, порождающих последовательно­