3.8.       Методы генерации псевдослучайных чисел

Генераторы шума широко применяются в таких радиотехнических устройствах, как электронные игры (для генерации случайных чисел), синтезаторы музыки и речи, измерители частотных характеристик (например, в магнитофонах), анализаторы акустических свойств помещений и многое другое.

В большинстве названных устройств в качестве первичных источников шума используются «шумящие элементы». Создаваемые ими шумы обусловлены протекающими в них электрическими процессами. К ним относятся, например, тепловые шумы резисторов, шумы стабилитронов, специальных диодов и т.д. Однако все эти источники обладают существенными недостатками: малой мощностью шума, низкой временной и температурной стабильностью параметров, неравномерностью спектральных характеристик по частоте из-за действия других видов шума, например, фликкер-шума. Такие генераторы требуют повторной настройки при смене шумящего элемента.

Перечисленные недостатки отсутствуют у цифровых источников шума, «цифровой» шум которых представляет собой временной случайный процесс, близкий по своим свойствам к процессу физических шумов и называющийся поэтому «псевдослучайным процессом». Цифровая последовательность двоичных символов в цифровых генераторах шума называется псевдослучайной последовательностью (ПСП), представ

ляющей собой последовательность прямоугольных импульсов псевдослучайной длительности с псевдослучайными интервалами между ними. Период повторения всей последовательности значительно превышает наибольший интервал между импульсами.

Хотя в литературе на сегодняшний день описано много различных методов генерации последовательностей чисел с равномерным законом распределения, мы коротко рассмотрим некоторые из них.

Один из наиболее старых и распространенных методов, так называемый конгруэнтный метод, состоит в том, что очередное случайное число  получают из предыдущего числа  с использованием следующего правила:

,                                                     (3.69)

где p – большое простое число; А – соответствующим образом выбранная константа.

Подпись:  
Рис. 3.33. Метод генерации равномерно распределенных 
случайных чисел

При определенных значениях А по этому правилу в случайном порядке генерируются целые числа в интервале от 1 до , причем их последовательность периодически повторяется. Преимуществами этого метода являются его простота и возможность использования в процессе вычислений памяти малого объема. Однако ему свойственна низкая скорость генерации, так как при каждой итерации приходится выполнить одно умножение (и деление); кроме того, для этого метода характерна большая чувствительность к значениям А и р.

Еще один распространенный метод – метод генерации случайных последовательностей (рис. 3.33). Предполагается, что в k регистрах памяти содержатся предварительно записанные случайные числа в диапазоне от  до  (их можно взять из таблицы случайных чисел в справочниках по математике).

Новое случайное число  генерируется по правилу:

,                                               (3.70)

причем выполнение операции по модулю  пояснено на рис. 3.33: если результат сложения больше , из него вычитается единица; если же результат меньше , к нему добавляется единица. Поэтому  будет всегда находиться в пределах от  до .

Если использовать представление чисел в дополнительном коде, то при условии, что максимально возможное машинное число равно <
img width=24 height=23 src=http://electrono.ru/wp-content/image_post/osncifr/pic101_1.gif>, вычисления с использованием формулы (3.70) можно выполнить, просто складывая числа в дополнительном коде и не учитывая переполнений.

Подпись:  

Рис. 3.34. Блок-схема генератора псевдослучайных чисел 
с равномерным распределением
Итак, преимущество рассматриваемого метода состоит в том, что все вычисления в пределах итерации сводятся к одному сложению. Кроме того, для хранения чисел от  до  обычно требуется примерно 50 регистров. Измерения статистических свойств образуемых таким методом псевдослучайных последовательностей показывают, что их распределения близки к равномерному, причем их энергетический спектр тоже почти равномерный, т.е. генерируемый шум близок к белому. Таким образом, рассмотренный генератор можно с успехом использовать для цифровой обработки сигналов.

Подпись:  
Рис. 3.35. Схема генератора ПСП на 15 тактовых интервалов
(DD1  К155ИР1; DD2  К155ЛП5)
Третий метод получения случайных чисел основан на принципе сложения по модулю 2 (рис. 3.34). Формирование очередного L-разрядного случайного числа

осуществляется на основе двух предшествующих отсчетов  и  по следующему правилу:

,                                         (3.71)

причем символ  обозначает циклический сдвиг вправо на Р разрядов, а сложение является поразрядным и выполняется по модулю 2.

В схеме (рис. 3.34) принято, что . этому алгоритму свойственны высокие быстродействие и эффективность. Единственная выполняемая здесь операция – L-разрядное сложение по модулю 2, а объем памяти ограничен двумя L-разрядными словами для хранения  и . Последний способ и нашел широкое применение для генерации ПСП, которая чаще всего формируется последовательными регистрами сдвига, охваченными линейной обратной связью, в общем случае многопетлевой. Для получения сигнала обратной связи в каждой петле используется сумматор по модулю 2 или элемент «исключающее ИЛИ».

Регистр с определенным числом разрядов может синтезировать несколько видов псевдослучайных цифровых последовательностей в зависимости от структуры обратной связи. Из всех таких последовательностей М-последовательности имеют максимальное число символов в периоде повторения кодовой комбинации, поскольку они включают в себя все состояния регистра, кроме нулевого. Такая последовательность двоичных символов чаще всего используется для формирования шума с равномерной спектральной плотностью в рабочем диапазоне частот, который можно назвать «белым» в заданном частотном диапазоне.

Таблица 3.3 Пояснение принципа работы генератора

Номер такта

Код на выходе регистра

Уровень на выходе элемента DD2.1

Десятичное число

1

0001

0

1

2

0010

0

2

3

0100

1

4

4

1001

1

9

5

0011

0

3

6

0110

1

6

7

1101

0

13

8

1010

1

10

9

0101

1

5

10

1011

1

11

11

0111

1

7

12

1111

0

15

13

1110

0

14

14

1100

0

12

15

1000

1

8

Формируемая с помощью N-разрядного регистра сдвига М-последовательность двоичных символов периодична и содержит все  двоичные комбинации состояний регистра в одном периоде (кроме нулевой). Величина  называется числовым периодом псевдослучайной последовательности. Принципиальная схема генератора псевдослучайной последовательности (ПСП) длительностью, равной 15 тактовым интервалам, приведена на рис.3.35. В режиме «Пуск» (правое  положение переключателя SA1) регистр сдвига DD1 принимает состояние, соответствующее коду на выходах, отличному от 0000, например, 0001 (табл. 3.3), что соответствует десятичному числу 1. На выходе элемента DD2.1 устанавливается уровень 0.

При переключении тумблера SA1 в противоположное положение с выхода элемента «исключающее ИЛИ» на вход V1 регистра воздействует уровень 0. С приходом тактового импульса регистр переключается, и уровень 1 продвигается в его следующий разряд. Состояние выходов

регистра теперь соответствует коду 0010. После очередного тактового импульса на выходах регистра появляются сигналы кода 0100, а на выходе элемента DD2.1 возникает уровень 1, который записывается в регистр. На его выходах получаются сигналы кода 1001 и т.д. (см. табл. 3.3). Импульсы ПСП снимают с любого выхода регистра, а сигналы параллельного кода двоичных чисел – одновременно со всех выходов. Вид полученной ПСП показан на рис. 3.36.

Следует иметь в виду, что чем короче ПСП, тем заметнее период ее повторения, что и видно из рис. 3.37. Чтобы исключить этот недостаток, необходимо использовать сдвиговые регистры с большим числом выходных двоичных разрядов. Принципиальная схема генератора ПСП с числовым периодом длительностью 65535 тактовых импульсов изображена на рис. 3.37.

Из табл. 3.3 видно, что в последовательности кодов отсутствует комбинация 0000. Это – запрещенное состояние регистра, так как при появлении такой комбинации про

исходит срыв генерации. Для вывода устройства из этого состояния и введен переключатель SA1.

Подпись:  
Рис. 3.38. Схема генератора ПСП с исключением запрещенного 
состояния (DD1 К176ИР2; DD2 К176ЛП2; DD3 К176ЛИ1)

Принципиальная схема генератора ПСП длительностью 255 символов, свободного от указанного недостатка, представлена на рис. 3.38. Он отличается от рассмотренных тем, что на выходе элемента DD2.3 включен инвертор, который инвертирует импульсы ПСП, и запрещенным состоянием становится не 0000 0000, а 1111 1111. При его возникновении на выходе элемента «И» микросхемы DD3 (вывод 8) появляется уровень 1, который устанавливает регистр DD1 в состояние 0000 0000, т.е. в рабочий режим. Аналогично можно собрать узел сброса запрещенного состояния и для устройств, собранных по схемам (см. рис. 3.35 и 3.36), однако в этом случае ПСП будет формироваться в инверсном виде. Псевдослучайную последовательность можно использовать также для проверки трактов передачи цифровых сигналов при воздействии помех.