Одним из наиболее полезных приложений микропроцессоров является применение их для моделирования реальных процессов и явлений окружающего нас мира. С помощью компьютера можно успешно моделировать такие процессы явления, как движение потока нефти или газа в трубопроводах, взлет и посадка самолетов, распределение потока работ в цифровой вычислительной системе, движение графического изображения в играх, и многое другое. Многие из этих моделей становятся тем ближе к своим реальным прототипам, чем больше содержат случайных и заранее неопределяемых элементов.
Псевдослучайные числовые последовательности могут использоваться для шифровки данных и сообщений, поскольку ключ для их дешифровки на приемной стороне строится с помощью идентичного генератора псевдослучайной числовой последовательности. Эти последовательности также широко используются в кодах с обнаружением и исправлением ошибок, поскольку они позволяют формировать такие блоки данных, в которых правильные сообщения оказываются разделенными большим расстоянием Хемминга (оно измеряется числом ошибочных битов). Благодаря хорошим автокорреляционным свойствам эти последовательности используются для помехозащищенных радарных систем, в которых ответный сигнал сравнивается с переданной строкой.
Одним из приемов, используемых при построении моделей, которые имитируют события, происходящие через случайные интервалы времени, является генерация с помощью микропроцессора последовательностей псевдослучайных чисел. Такие последовательности, заданные надлежащим образом, могут храниться в памяти в виде таблиц. Однако, часто желательно чтобы микропроцессор сам мог генерировать случайные величины, а не использовать заготовленные таблицы.
Если известны алгоритм и исходные величины, микропроцессор может генерировать последовательность случайных чисел. И хотя они не являются действительно случайными, многие их характеристики совпадают с характеристиками действительно случайных последовательностей. По этой причине генерируемые последовательности являются псевдослучайными. Особенно наглядно это проявляется в больших последовательностях псевдослучайных чисел, в которых практически невозможно предсказать каждое последующее число.
Одним из широко используемых методов генерации псевдослучайных чисел является метод последовательного умножения. Его алгоритм состоит из следующих шагов:

1. Выбирается какое-нибудь значение X. Оно называется начальным значением и является первым числом генерируемой псевдослучайной последовательности.
2. Число X умножается на постоянный множитель N. В результате получается число P.
3. Число P делится на константу M, называемую модулем. Остаток от деления образует новое значение величины X и является следующим числом псевдослучайной последовательности.
4. Шаги 2 и 3 повторяются.

Поскольку генерируемые псевдослучайные числа являются остатками от деления P/M, то значение модуля M определяет максимально возможную длину последовательности. Так, если M=2¹⁶, то переменная X может принимать 2¹⁶ или 65536 значений. Такой диапазон последовательности вполне достаточен для большинства применений. Если вычисления ограничиваются 16-битовыми числами, то для достижения максимально возможной независимости соседних членов последовательности величина множителя N не должна превосходить квадратный корень из модуля M. Для того чтобы закон распределения чисел был более или менее постоянен на протяжении всей последовательности, последние три бита сомножителя X должны содержать 011 или 101. Начальное значение для процедуры можно взять из значения секунд и сотых долей секунд внутреннего таймера системы или ASCII или SCAN-кода последнего введенного с клавиатуры символа (желательно проследить что бы в начальное значение не попал 0).
Еще одним из достаточно простых способов образования псевдослучайной последовательности чисел является комбинирование операций циклического сдвига, операции «логического И» (AND) для выделения одиночных разрядов и «операции исключающего ИЛИ» (XOR).Пусть командами RCR или RCL сдвигается число, имеющее размер бит. Результат операции XOR между -м и последним (-м) разрядом помещается во флаг переноса и оттуда попадает в 1-й разряд. Такая схема проходит совокупность состояний, которая определяется комбинациями битов в регистре после каждого сдвига и эта последовательность повторится через каждые K чисел, то есть является циклической с периодом K.
Число возможных состояний m-разрядного регистра составляет , то есть равно числу двоичных комбинаций бит. Однако состояние, когда в регистре содержатся все 0, является для данной схемы «тупиковым», поскольку операция XOR будет формировать только нули. Поэтому максимальная длина последовательности, которую можно сформировать с помощью данной схемы, равна . Получить последовательности максимальной длины можно лишь в том случае, если и выбраны правильно и результирующая последовательность битов является псевдослучайной. (Критерием для определения максимальной длины служит неприводимость полинома и его первичность на поле Галуа.) В качестве примера рассмотрим 4-разрядный регистр сдвига с обратной связью. В таблице перечислены генерируемые псевдослучайные числа, начиная с 1111b (15) (с тем же успехом можно выбрать любое начальное число, за исключением 0000).Регистры сдвига максимальной длины можно строить, используя и более двух точек для подключения обратной связи через операцию «Исключающее ИЛИ». В этом случае по модулю 2 суммируются несколько битов. При некоторых m для построения регистра максимальной длины требуется более двух точек подключения обратной связи. В таблице приводятся все значения m, вплоть до 33, при которых для построения регистра максимальной длины достаточно двух точек подключения обратной связи, то есть обратная связь берется с n-го и m-го (последнего) разряда. Значения n и циклической длины изменяются числом периодов. Иногда n может иметь более одного значения; в любом случае вместо n можно взять m–n. Для 4-разрядного регистра можно было бы использовать точки подключения обратной связи при и .Длина регистра сдвига обычно выбирается кратной 8. В этом случае требуется более двух точек подключения обратной связи.

1. В одном полном цикле (K тактов) число «единиц» на одну превышает число «нулей». Дополнительная единица возникает благодаря исключению нулевого состояния. При значениях длины регистра, которые обычно используются на практике, дополнительная единица не может оказать какого-либо влияния: 17-разрядный регистр (16-разрядов + флаг переноса) вырабатывает за один период 65536 единиц и 65535 нулей.
   

   1	1111 (15)	5	1000 (08)	9	1100 (12)	13	1010 (10)
   2	0111 (07)	6	0100 (04)	10	0110 (06)	14	1101 (13)
   3	0011 (03)	7	0010 (02)	11	1011 (11)	15	1110 (14)
   4	0001 (01)	8	1001 (09)	12	0101 (05)

2. В каждом цикле (K тактов) половину всех единиц составляют «одиночные» (5, 6, 7, 8, 11, 12, 13, 14), четвертую часть – двойные (то есть две следующие подряд) (3, 9, 10, 11), восьмую часть – тройные (2, 15) и т.д. То же самое относится и к последовательно идущим нулям. Это говорит о том, что вероятность появления начала и конца единичного состояния не зависит от результата последнего переброса и, следовательно, вероятность завершения цепочки последовательно возникших единиц или нулей для каждого переброса составляет одну вторую.
3. Если последовательность полного цикла (K тактов) сравнить с последовательностью такой же длины, но сдвинутой на любое число n бит (где n не равно 0 и не кратно K), то число несовпадений будет превышать число совпадений на единицу. Автокорреляционная функция такой последовательности при нулевой задержке представляет собой дельта-функцию Кронекера, а во всех остальных точках равна 1/K.

1. Предположим, что регистр DX содержит 1011100110111001b, а регистр CX – 3. Определите содержимое регистра DX после следующих несвязанных команд:
   1. SHR DX,1
   2. SHR DX,5
   3. SHR DL,CL
   4. SHL DX,CL
   5. SHL DL,1
   6. ROR DL,2
   7. ROR DX,4
   8. SAL DH,1
2. Напишите программу, в которой, используя команды сдвига, пересылки и сложения, умножьте содержимое регистра AX на 100.
3. Напишите программу, в которой, используя команды сдвига и циклического сдвига, содержимое пары регистров DX:AX:
   1. умножается на 4;
   2. делится на 4;
   3. 48 бит в регистрах DX:AX:BX умножается на 2.
4. Разделите 16-разрядное число, помещенное на вершину стека, на два 8-разрядных числа и снова разместите их в стеке.

Миниатюры

     

     

   

Изображения

 

7