Операция деления по mod2

Схема деления n -разрядного двоичного числа A на фиксированный образующий полином Р m -йстепени показана на рис. 3.

Схема содержит (n-m)-разрядный регистр числа RGА со сдвигом влево (в сторону старших разрядов), (m+1)-разрядный регистр полинома RGP со сдвигом влево, умножители на коэффициенты p_i и сумматоры по mod2. Заметим, что цепи сдвига между разрядами регистра RGP осуществляются через сумматоры по mod2.

В двоичных полиномах коэффициенты p_i могут принимать значения 1 или 0. Поэтому умножители на коэффициенты p_i на схемах трактуются следующим образом: если p_i =1, то связь между выходом старшего разряда регистра RGP и входомсумматора по mod2, который подключен к выходу i -го разряда регистра RGP, имеется; и если p_i =0, то эта связь и сам сумматор по mod2 отсутствует, т.е., i -й и i+1 -й разряды регистра RGP имеют между собой непосредственную (прямую)связь. Заметим, что старший разряд р_m образующего полинома всегда равен1, поэтому связь между выходом старшего разряда регистра RGP и входами соответствующихсумматоров по mod2 существует всегда.

В исходном состоянии младшие n-m разрядов числа А записываются в регистр RGА, остальные m разрядов – в младшие разряды регистра RGP. Старший разряд этого регистра устанавливается в 0. Формирование n-m -разрядного частного по mod2 и m -разрядного остатка осуществляется в реальном масштабе времени за n-m+1 тактов. Частное формируется в первых n-m тактах на выходе устройства (выход старшего разряда регистра RGP) старшими разрядами вперед (в такте Т1 формируется старший разряд и т. д.). А после выполнения (n-m+1)-го тактав m старших разрядах регистра RGP (разряды 1, 2,..., m) будет сформирован остаток.

Пример построения схемы деления по mod2 14-разрядного числа А на образующий полином 6-йстепени Р = 2⁶+2⁵+2⁴+2³+2⁰ = 1111001показана на рис. 4. Работа схемы при делении 14-разрядного числа D= 10110010011011 на указанный полином иллюстрируется таблицей 3.

В исходном состоянии в регистре RGА записаны младшие 8 разрядов числа А (10011011), в 6-ти младших разрядах регистра RGP – остальные 6 старших разрядов числа D ( 101100), старший (6-й) разряд регистра RGP установлен в 0. В каждом такте осуществляется совмещенный сдвиг содержимого регистров RGА и RGP сдвигается на 1 разряд влево (“выталкиваемый” из регистра RGА старший разрядзаносится в освобождающийся младший разрядрегистра RGP).

Сдвиг в регистре RGP осуществляется через сумматор по mod2 с учетом обратной связи: т.е. с учетом выхода старшего разряда регистра RGP (этот выход через сумматоры по mod2 подключен ко входам 1-го, 4-го, 5-го и 6-го разрядов регистра RGP. Например: в такте Т2 при сдвиге на входы этих сумматоров поступает “единица” из 6-го разряда такта Т1 (в таблице помечена звёздочкой – (“1^*”), а в такте Т5 – “нуль” из 6-го разряда такта Т4 (помечено звёздочкой). В овобождающиеся при сдвиге разряды регистра RGА заносятсянули. Восьми-разрядное частное формируется на выходе 6-го разряда регистра RGP в тактах Т1...Т8, 6-разрядный остаток (010100) формируется после выполнения такта Т9 в 1-м, 2-м,..., 6-м разрядах регистра RGP.

RGA (n-m = 14-4 = 8 разрядов)   Рис. 4

Разряды RGP

Разряды RGA

Исх. сост.

Такт

Т1

1*

Т2

Т3

Т4

0*

Т5

Т6

Т7

Т8

Т9

Остаток

Таблица 3. Деление 14-разрядного числа A на порождающий полином 6-йстепени

Частное и остаток от деления по mod2 двух чисел может быть осуществлено (и использовано для проверки) способом привычного деления “в столбик” с той лишь разницей, что вместо операции вычитания выполняется сложение по mod2 (таблица 6).

Алгоритм такого деления заключается в выполнении следующих n-m циклов (в нашем примере – 8-ми циклов).

1) Выделяется число R, которое состоит из m+1 старших разрядов делимого (в приведенном примере семь разрядов, выделенных курсивом).

2) Если старший разряд числа R равен “1”, то очередной разряд частного равен “1”. Если этот разряд равен “0”, то очередной разряд частного равен “0”.

3) Делитель умножаем на полученный разряд частного и это произведение складываем по mod2 с числом R (в таблице это произведение для 1-го цикла записано под числом R и оно выделено жирным шрифтом).

4) Младшие m-1 разрядов результата и следующий разряд делимого являются новым значением числа R (в таблице для 1-го цикла это число выделено курсивом и жирным шрифтом).

5) Если количество циклов меньше n-m, то переход к п. 2).

1	0	1	1	0	0	1
Å1
	1	0	0	0	0	0	0							Частное
Å
	Å
		Å
			Å
				Å
					Å
						Å
								Остаток

Таблица 4. Деление чисел “в столбик”

Литература

1. Мельников Д.А. Информационные процессы в компьютерных сетях. Москва. 1999

2. Стеклов В.К., Беркман Л.Н. Телекомунікаційні мережі. Київ. 2001.

3. Питерсон У., Уэдсон Э. Коды, исправляющие ошибки. Москва. 1976.

4. Рекомендация МККТТ Х.25. Стык между оконечным оборудованием данных (ООД) и аппаратурой окончания канала данных (АКД). Синяя книга. 1988.

5. Методичне керівництво для виконання комплексного контрольного завдання з дисципліни “Комп’ютерні мережі та Інтернет”. 2003.

6. Бертсекас Д., Галлагер Р. Сети передачи данных. Москва, 1989.

7. Блэк Ю. Сети ЭВМ: Протоколы, стандарты, интерфейсы. Москва. 1990.

8. Мельников Д.А. Организация информационного обмена в информационно-вычислительных сетях: Учебное пособие. М. ФАПСИ, 1998.

9. Республіканський стандарт Української РСР РСТ УРСР 2018-91. Кодування символів української абетки 8-бітними кодами.