Электронный учебник - Assembler - Ответ 5356779

@Mikl___ · m n Длина m n Длина

ГЛАВА 12
КОМАНДЫ СДВИГА
(часть 3/3)

Генерация псевдослучайных чисел

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

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

Поскольку генерируемые псевдослучайные числа являются остатками от деления P/M, то значение модуля M определяет максимально возможную длину последовательности. Так, если M=2¹⁶, то переменная X может принимать 2¹⁶ или 65536 значений. Такой диапазон последовательности вполне достаточен для большинства применений. Если вычисления ограничиваются 16-битовыми числами, то для достижения максимально возможной независимости соседних членов последовательности величина множителя N не должна превосходить квадратный корень из модуля M. Для того чтобы закон распределения чисел был более или менее постоянен на протяжении всей последовательности, последние три бита сомножителя X должны содержать 011 или 101. Начальное значение для процедуры можно взять из значения секунд и сотых долей секунд внутреннего таймера системы или ASCII или SCAN-кода последнего введенного с клавиатуры символа (желательно проследить что бы в начальное значение не попал 0).

Assembler

;читаем значение сотых долей секунд в таймере для
;начального значения последовательности случайных
;чисел. В регистр AH номер функции получения времени
AGAIN: MOV AH,2Ch
INT 21h ;получаем время
MOV AX,DX ;берем секунды из DH и сотые доли секунды из DL
CMP AX,0
JE AGAIN
;генерация 200 псевдослучайных чисел
MOV CX,200
RANDOM: CALL PSEUDO_RANDOM
LOOP RANDOM
· · ·
PSEUDO_RANDOM PROC NEAR
PUSH DX
MOV BX,261
MUL BX
POP DX
RET

Псевдослучайные последовательности,
образованные при помощи циклического сдвига

Еще одним из достаточно простых способов образования псевдослучайной последовательности чисел является комбинирование операций циклического сдвига, операции «логического И» (AND) для выделения одиночных разрядов и «операции исключающего ИЛИ» (XOR).

Пусть командами RCR или RCL сдвигается число, имеющее размер $https://www.cyberforum.ru/cgi-bin/latex.cgi?m$ бит. Результат операции XOR между $https://www.cyberforum.ru/cgi-bin/latex.cgi?n$ -м и последним ( $https://www.cyberforum.ru/cgi-bin/latex.cgi?m$ -м) разрядом помещается во флаг переноса и оттуда попадает в 1-й разряд. Такая схема проходит совокупность состояний, которая определяется комбинациями битов в регистре после каждого сдвига и эта последовательность повторится через каждые K чисел, то есть является циклической с периодом K.
Число возможных состояний m-разрядного регистра составляет $https://www.cyberforum.ru/cgi-bin/latex.cgi?K=2^m$ , то есть равно числу двоичных комбинаций $https://www.cyberforum.ru/cgi-bin/latex.cgi?m$ бит. Однако состояние, когда в регистре содержатся все 0, является для данной схемы «тупиковым», поскольку операция XOR будет формировать только нули. Поэтому максимальная длина последовательности, которую можно сформировать с помощью данной схемы, равна $https://www.cyberforum.ru/cgi-bin/latex.cgi?2^{m}-1$ . Получить последовательности максимальной длины можно лишь в том случае, если $https://www.cyberforum.ru/cgi-bin/latex.cgi?m$ и $https://www.cyberforum.ru/cgi-bin/latex.cgi?n$ выбраны правильно и результирующая последовательность битов является псевдослучайной. (Критерием для определения максимальной длины служит неприводимость полинома $https://www.cyberforum.ru/cgi-bin/latex.cgi?1+x^{m}+x^{n}$ и его первичность на поле Галуа.) В качестве примера рассмотрим 4-разрядный регистр сдвига с обратной связью. В таблице перечислены генерируемые псевдослучайные числа, начиная с 1111b (15) (с тем же успехом можно выбрать любое начальное число, за исключением 0000).

1111 (15)	1000 (08)	1100 (12)	1010 (10)
0111 (07)	0100 (04)	0110 (06)	1101 (13)
0011 (03)	0010 (02)	1011 (11)	1110 (14)
0001 (01)	1001 (09)	0101 (05)

Регистры сдвига максимальной длины можно строить, используя и более двух точек для подключения обратной связи через операцию «Исключающее ИЛИ». В этом случае по модулю 2 суммируются несколько битов. При некоторых m для построения регистра максимальной длины требуется более двух точек подключения обратной связи. В таблице приводятся все значения m, вплоть до 33, при которых для построения регистра максимальной длины достаточно двух точек подключения обратной связи, то есть обратная связь берется с n-го и m-го (последнего) разряда. Значения n и циклической длины изменяются числом периодов. Иногда n может иметь более одного значения; в любом случае вместо n можно взять m–n. Для 4-разрядного регистра можно было бы использовать точки подключения обратной связи при $https://www.cyberforum.ru/cgi-bin/latex.cgi?n=1$ и $https://www.cyberforum.ru/cgi-bin/latex.cgi?m=4$ .

m	n	Длина	m	n	Длина
3	2	7	18	11	262143
4	3	15	20	17	1048575
5	3	31	21	19	2097151
6	5	63	22	21	4194303
7	6	127	23	18	8388607
9	5	511	25	22	33554431
10	7	1023	28	25	268435455
11	9	2047	29	27	536870911
15	14	32767	31	28	2147483647
17	14	131071	33	20	8589934591

Длина регистра сдвига обычно выбирается кратной 8. В этом случае требуется более двух точек подключения обратной связи.

m	Точки подключения обратной связи	Длина
8	4, 5, 6	255
16	4, 13, 15	65535
24	17, 22, 23	16777215

Свойства последовательностей максимальной длины
для шифровальщиков и любителей взламывать чужие шифры

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

Контрольные вопросы и упражнения

Предположим, что регистр 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
Напишите программу, в которой, используя команды сдвига, пересылки и сложения, умножьте содержимое регистра AX на 100.
Напишите программу, в которой, используя команды сдвига и циклического сдвига, содержимое пары регистров DX:AX:
1. умножается на 4;
2. делится на 4;
3. 48 бит в регистрах DX:AX:BX умножается на 2.
Разделите 16-разрядное число, помещенное на вершину стека, на два 8-разрядных числа и снова разместите их в стеке.

Вернуться к обсуждению:
Электронный учебник Assembler

Следующий ответ

Другие темы раздела
Assembler задача для курсовой помогите пожалуйста.не могу найти в интернете ничего что могло бы помочь дан одномерный массив найти количество и сумму нечетных элементов https://www.cyberforum.ru/ assembler/ thread1000518.html	Assembler Компиляция masm32 из RadASM программ для DOS Доброго времени суток. Вот такая проблема у меня. Скачал masm32 установил в корень диска С: В notepad забил текст,отдаю команду в командной строке ml /c xxxx.asm получаю файл с расширением .obj Далее doslnk /t xxxx.asm и тишина "doslnk" не является внутренней или внешней командой, исполняемой программой или пакетным файлом. Это что ,получается у меня нет линковщика?! Хотя в папке bin файл...
Assembler Одна непонятная ситуация с отладчиком td Всем доброго времени суток. У меня небольшая проблема с программой. Заранее говорю, я новичок в этом. Сделал программу которая должна выводить числа на экран в диапазоне от нуля до 99999, короче говоря максимально 5-ти значные числа. Как пример должно выдать число 50784, а выдаёт мне вот такое: треугольник 6256. Но когда я запускаю эту программа через отладчик td она мне выдаёт в консоль нужное... https://www.cyberforum.ru/ assembler/ thread996648.html	Assembler Правильный выход из программы https://www.cyberforum.ru/ assembler/ thread995183.html Поправьте код код пожалуйста, чтобы программа выключалась после нажатия клавиши =) P.S. Компилятор TASM .MODEL small .DATA HelloMessage DB 'Hello, world $' .CODE mov ax,@data mov ds,ax mov ah,9 mov dx,OFFSET HelloMessage
Assembler Переписать алгоритм на ассемблер Есть код на делфи. тема - работа с BitMap. Вопрос: можно ли реализовать это на ассемблер? Это интерполяция изображений. P.s. Важен не сам код, как файл. Вот, то, что нужно ускорить: unit rsmpl; interface uses SysUtils, Classes, Graphics;	Assembler Ошибка в коде, необходимо разобраться! https://www.cyberforum.ru/ assembler/ thread990315.html .386 .model flat,stdcall option casemap:none WinMain proto :DWORD,:DWORD,:DWORD,:DWORD include C:\masm32\include\windows.inc include C:\masm32\include\user32.inc include C:\masm32\include\shell32.inc include C:\masm32\include\kernel32.inc includelib C:\masm32\lib\user32.lib includelib C:\masm32\include\shell32.inc
Assembler Tasm DosBox Доброго всем времени суток. Нужна ваша помощь: как запустить файл filename.asm в Tasm? файл размещен в d:\tasm. Tasm смонтировал с dosBox-ом: mount c: d:\tasm\bin Буду благодарен. https://www.cyberforum.ru/ assembler/ thread990002.html	Assembler Удобная среда для TASM Подскажите инструменты для комфортного изучения Ассемблер под Интел 8086 В данным момент использую DosBox и TASM, но это оочень неудобно, ведь при каждом запуске приходится настраивать, при чем при Debug'е иногда вылетает((
Assembler Команда сдвига Сразу скажу, работаю не в ассемблере, а в симуляторе микропроцессора VAX-11. Но все вполне аналогично и можно провести аналогию с ассемблером. Вопрос: Есть команда сдвига, выполняющаяся в формате long(4 байта). Число, которое я сдвигаю равно -226 в десятичной, FF1E в шестнадцатеричной. Доступ к этому числу выполняется через относительную адресация(адресация, при которой адрес операнда... https://www.cyberforum.ru/ assembler/ thread989662.html	Assembler Коллоквиум, практические задания В общем, расскажу честно, учусь в универе, с этого семестра начался ассемблер, в связи с большой загруженностью не успеваю его тщательно изучать, хватаю кусками. Завтра по теории колоквиум, ребят, кому не сложно, ответьте на любой вопрос, пожалуйста, буду очень признателен. "С мира по нитке - бедному рубаха", как говорится. 50. Сегмент данных программы описан следующим образом .data str db... https://www.cyberforum.ru/ assembler/ thread989322.html
Assembler некорректное выполнение цикла model small .stack 100h .data len equ 10 mass dw -1,0,-9,8,0,7,8,0,2,0 .code start: mov ax,@data	Assembler Как запустить Tasm в cmd на win xp? https://www.cyberforum.ru/ assembler/ thread988361.html Как запустить Tasm в cmd на win xp?

	15.11.2013, 04:43