Методичне керівництво для виконання контрольного завдання з дисципліни Паралельні та розподілені обчислення

Для студентів денної і заочної форми навчання

з підготовки бакалаврів за напрямом

«Комп’ютерна інженерія»

Торошанко Ярослав Іванович

ЧАСТЬ 1.1

1.1. Содержание и порядок выполнения контрольной работы (Ч. 1) 

а). Сформировать в соответствии с РСТ УССР 2018-91 двоичное 100-байтное сообщение, содержащее следующую информацию (со знаками препинания):

– фамилия, имя и отчество студента;

– числа 147595+45N, 54896846+5967N, (словами).

Таблица кодирования символов русской и украинской азбуки приведена в таблице 1.1, коды символов приведены в шестнадцатиричной системе счисления.

б). Из полученного сообщения сформировать информационные кадры с длиной информационного поля 10 байт и поля управления равна 16 бит (см. ниже Теоретические сведения – п. 2 настоящего документа).

Проверочные комбинации FCS сформировать как контрольную сумму по mod 2¹⁶ содержимого кадра (эта процедура не входит в стандарт Х.25). Показать ход вычисления этих комбинаций.

Контрольная сумма по mod 2¹⁶ формируется следующим образом. Содержимое кадра разбивается на блоки по 16 бит. Затем содержимое этих блоков суммируется по mod 2¹⁶, т.е., переносы из 16 разряда игнорируются. Заметим при этом, что все остальные переносы должны учитываться.

Рассмотрим пример. Пусть кадр содержит следующую информацию:

01111110 11000111 10101000 01110001 11100111 00011011 FCS¢ 01111110

Выделенные курсивом флаги в состав кадра не входят.

После разбиения имеем три 16-разрядных блока (младшие 8 разрядов третьего неполного блока дополняются нулями): 11000111 10101000, 01110001 11100111, 00011011 00000000.

1) Суммируем первые два блока, при этом единица переноса из 16-го разряда (выделена курсивом) игнорируется : 

2) Полученный результат суммируем с 3-м блоком:

в). Во всех кадрах произвести процедуру “прозрачность” (см. п. 2.5).

г) В одном из принятых кадров показать порядок обнаружения 4- и 7-кратных ошибок (см. п. 2.6). 

Таблица 1.1. Стандарт РСТ УССР 2018-91.

Кодирование символов украинской и русской азбуки.

ЧАСТЬ 1.2

1.2. Содержание и порядок выполнения контрольной работы (Ч. 2)

а). Определение варианта V. Вариант V является 8-разрядным двоичным числом. Младшие 5 разрядов представляют собой порядковый номер студента в журнале (номера разрядов 0...4). Старшие 3 разряда с номерами 5...7 – «110».

б) Построить схему умножения по mod2 16-разрядных чисел А на образующий полином Р 10-й степени, . При этом для четных вариантов Р = (101 v₇ v₆ . . . v₁ v₀ ) + 1, для нечетных вариантов Р = 11 v₇ v₆ . . . v₁ v₀ , где v_i – значения разрядов числа V .

– Привести таблицу функционирования этой схемы для числа А = 1011р₉ р₈...р₁ р₀01, где р_i – значения разрядов числа P.

– Проверить полученный результат путем умножения “в столбик”.

в). Построить схему деления по mod2 16-ти разрядных чисел А на образующий полином Р 10-й степени, полученный в п. 2.2).

– Привести таблицу функционирования этой схемы для числа А и Р 110101р₉ (числа А и Р определенны в п. 2.2).

– Проверить полученный результат путем деления “в столбик”.

– Проверить выполненую операцию деления с помощью операции умножения (“в столбик”).

2. ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ (по части 1.1).

Кодирование информации в стандарте Х.25 

2.1. Общие сведения. Стандарт (протокол) Х.25 впервые был изложен в 1974 г. в Рекомендации МККТТ (ныне МСЭ или ITU-T). В дальнейшем стандарт пересматривался, дополнялся и сейчас занимает доминирующее положение среди протоколов сетевого и канального уровней в иерархической системе протоколов эталонной модели взаимодействия открытых систем (ЭМВОС). 

2.2. Общая структура кадра. На канальном уровне (уровень 2) обмен информацией осуществляется кадрами (пакетами). В стандарте Х.25 пакет принято называть кадром. Кадры содержат поля флага, адреса, управления, информации, проверочной комбинации кадраFCS и бывают 2-х видов: с полем информации и без поля информации. Форматы таких кадров показаны в таблицах 2.1 и 2.2.

Таблица 2.1 Формат кадра с полем информации 

Таблица 2.2 Формат кадра без поля информации

2.3. Типы кадров и команды. По функциональному назначению имеется 3 типа кадров, которые определяются форматом поля управления. В таблицах 2.3. и 2.4 приведены форматы 8- и 16-битового поля управления для каждого из 3-х типов кадров.

Обозначения в таблицах 2.3 и 2.4:

¤ N(S) – порядковый номер передаваемого кадра “I”;

¤ N(R) – порядковый номер ожидаемого на прием кадра “I”;

¤ P – признак запроса состояния адресуемого узла (P =1);

¤ F – признак ответа на запрос состояния узла;

¤ s – кодирование команд кадров типа “S” (см. п. 2.1.3.2);

¤ u – кодирование команд кадров типа “U” (см. п.2.1.3.3);

¤ x – неиспользуемые биты, обычно устанавливаются в “0”. 

Таблица 2.3 Формат 8-битового поля управления 

Таблица 2.4 Формат 16-битового поля управления 

2.3.1. Кадр “I” (Information Transfer Format) – информационный кадр, используется для передачи информации. Признаком такого кадра является код “0” в 0-м бите поля управления. Применяются кадры 1-го вида (с полем информации).

2.3.2. Кадр “S” (Supervisory Format) – супервизорный (контрольный) кадр, используется для управления и контроля процесса обмена информацией. Признаком такого кадра является код “10” в 0-м и 1-м битах поля управления. Применяются кадры 2-го вида (без поля информации).

В этом кадре передаются следующие команды:

– RR (Receive Ready, готовность к приему), используются для указания на то, что узел (станция) готов принять кадр “I”, либо для подтверждения ранее принятых кадров. Кодирование команды – ss = 00 (разряды 2 и 3 в таблицах 2.3. и 2.4).

– REJ (Reject, неприем), используется для запроса повторной передачи кадров “I” (например, при обнаружении ошибок в принятом кадре). Кодирование команды – ss = 01.

– RNR (Receive Not Ready, неготовность к приему), используются для указания на то, что узел (станция) не готова принимать информацию (например, из-за перегрузки). Кодирование команды – ss = 10.

2.3.3. Кадр “U” – (Unnumber Format, ненумерованный кадр), используется при инициализации и установки режима канала в начала и конце сеанса обмена информацией между двумя узлами. Признаком такого кадра является код “11” в 0-м и 1-м битах поля управления. Применяются кадры 1-го и 2-го видов (с полем информации и без него). Поле управления этих кадров всегда содержит только 8 бит.

В этом кадре передаются следующие команды (кодирование этих команд осуществляется разрядами 2, 3, 5, 6 и 7 в поле управления кадра, т.е. – разряды “u” в таблицах 2.3 и 2.4):

– SARM8 и SARM16 (Set Asynchronous Response Mode), кадр без поля информации, используется для перевода узла, которому адресована команда, в режим асинхронного ответа с использованием 8- или 16-битового поля управления. Коды команд 11000 и 11010. Подтверждением выполнения этих команд является команда/ответ UA (см. ниже);

– SABM8 и SABM16 (Set Asynchronous Balanced Mode), кадр без поля информации, используется для перевода узла, которому адресована команда, в асинхронный балансный режим с использованием 8- или 16-битового поля управления. Коды команд 11100 и 11110. Подтверждением выполнения этих команд является команда/ответ UA (см. ниже);

– DISC (Disconnect, прерывание), кадр без поля информации, используется для окончания режима, установленного ранее командами SARM или SABM. Код команды 00010. Подтверждением выполнения этой команды является команда/ответ UA (см. ниже);

– UA (Unnumber Acknowledge, подтверждение без номера), команда/ответ, кадр без поля информации, используется для подтверждения приема команд формата “U”. Код команды 00110.

– DM (Disconnect Mode, режим прерывание), команда/ответ, кадр без поля информации, используется для сообщения о таком состоянии, при котором узел логически отключается от канала. Код команды – 11000.

– FMDR, неприем кадра. Код команды – 10001. 

2.4. Порядок кодирования кадров.

2.4.1. Поле “Флаг” (см. таблицы 2.1 и 2.2). Все кадры должны начинаться и заканчиваться флаговой комбинацией “01111110”. Одна и та же флаговая комбинация может использоваться как закрывающая один кадр и открывающая следующий кадр.

Примечание: Комбинация “Флаг” процедуре “прозрачность” не подвергается (см. п. 2.5).

2.4.2. Поле “Адрес” состоит из 8-ми бит, обеспечивая таким образом адресацию 256 узлов (2⁸). Передача адреса осуществляется начиная с младшего разряда (младшими разрядами вперед).

2.4.3. Поле “Управление” состоит из 8-ми или 16-ти бит. Кодирование этого поля описано в п. 2.3, таблицы 2.3 и 2.4. Передача поля осуществляется младшими разрядами вперед.

2.4.4. Поле “Информация” содержится в кадрах типа “I” и в командах/ответах CDMR и FRMR, которые передаются с помощью кадров типа “U”.

2.4.4.1. Протокол Х.25 допускает использование следующих максимальных значений поля “Информация” в кадрах типа “I”: 16, 32, 64, 128, 256, 512 и 1024 байта. Предпочтительна длина 128 байт. Расположение информации определяется на верхних уровнях (прикладном).

2.4.4.2. Кодирование поля “Информация” в кадрах типа “U” описано в п. 2.1.3.3 (команды/ответы CMDR и FMDR).

2.4.5. Поле “FCS” (Frame Checking Sequence, проверочная комбинация кадра) содержит 16-битовое число, которое является дополнением до единиц (обратный код) суммы по mod2 следующих двух чисел:

а) остатка от деления по mod2 числа 2^к(2¹⁵+ 2¹⁴+2¹³+2¹²+...+2²+2¹+1) на порождающий (образующий) полином 2¹⁶+2¹²+2⁵+1, где “к” равно числу бит в кадре находящихся между последним битом открывающего флага и первым битом “FCS” (но без этих битов), за исключением битов процедуры “прозрачность” (процедура “прозрачность” описана в п. 2.5).

б) остатка после умножения на 2¹⁶ и последующего деления по mod2 на образующий полином 2¹⁶+2¹²+2⁵+1 содержания кадра, находящегося между последним битом открывающего флага и первым битом “FCS” (но без этих битов), за исключением битов процедуры “прозрачность”.

Примечания:

1. Вышеприведенные числа в 2-м коде представляются следующим образом:

¤ 2^к = 1000...00 (количество нулей равно “к”); 

¤ 2¹⁵+ 2¹⁴+2¹³+2¹²+...+2²+2¹+1 = 111...11 (количество единиц равно 16); 

¤ 2¹⁶+2¹²+2⁵+1 = 10001000000100001 (единицы только в тех разрядах, номера которых являются показателями степеней в образующем полиноме; нулевым разрядом является крайний правый разряд).

2. Выполнение операций умножения и деления по mod2 на порождающий полином см. в Л. [3].

3. В данной контрольной работе для формирования поля “FCS” будет использоваться другой алгоритм, который не является алгоритмом протокола Х.25 (см. п.2.2). 

2.5. Прозрачность передачи информации. Система передачи информации называется прозрачной, если она обеспечивает передачу всех без исключения битовых комбинаций, в противном случае она является непрозрачной.

В протоколе Х.25 для обозначения границ кадра используется флаговая комбинация “01111110” (см. п. 2.4.1.). Внутри кадра такая комбинация может появиться как полезная информация, не являющаяся флагом (признаком конца кадра). Для того, чтобы эта комбинация внутри кадра не была воспринята как флаг и не прервала прием незавершенного кадра, в протоколе Х.25 используется процедура “прозрачность”, выполнение которой заключается в следующем.

Передающая аппаратура осуществляет защиту от преднамеренного появления флаговой последовательности, вставляя “0” в поток данных внутри кадра после любой последовательности из пяти единичных битов. Этот вставляемый бит “0” называется бит-стаффингом.

Приемная аппаратура будет убирать из потока данных внутри кадра каждый “0” , следующий за пятью единичными битами. 

2.6. Контроль правильности передачи осуществляется приемной аппаратурой следующим образом.

1) Выполняется обратная процедура “прозрачность”, т.е., в принятом кадре исключаются бит-стаффинги.

2) В принятом кадре по алгоритму протокола Х.25 (см. п. 2.4.5) вычисляется проверочная комбинация FCS¢.

3) Если принятая комбинация FCS и вычисленная FCS¢ совпадают, принимается решение, что передача осуществлена без искажений, блок примается для дальнейшей обработки, а на передающую станцию направляется положительное подтверждение.

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

8. Теоретические сведения по части 1.2

8.1. Общая структура кадра. На канальном уровне (уровень 2) обмен информацией осуществляется кадрами (пакетами). В стандарте Х.25 пакет принято называть кадром. Кадры содержат поля флага, адреса, управления, информации, проверочной комбинации кадраFCS и бывают 2-х видов: с полем информации и без поля информации. Форматы кадров, а также алгоритм формирования проверочной комбинации кадраFCS описаны в Л.1, 2, 4, 5. Алгоритм основан на выполнении арифметических операций по модулю 2 над двоичными числами (полиномами), в частности умножения и деления на образующий полином. 

8.2. Выполнение арифметических операций по модулю.

8.2.1. Общие сведения. В теориипомехоустойчивого кодирования (Л.3) числа представляются в виде многочленов (полиномов). Число А в позиционной системе счисления с естественным порядком весов представляется в следующем виде: 

где X ­– основание системы счисления, коэффициенты a_i – значения i-х разряда числа А.

Наибольшее значение показателя степени в полиноме называется степенью полинома.

Например, четырехразрядное число А=4809в десятичной системе счисления будет представлено следующим полиномом 3-ей степени:

4809 = 4·10³ + 8·10² + 0·10¹ +9·10⁰ = 4·10³ + 8·10² + 9. 

В двоичной системе счисления коэффициенты a_i могут принимать значения 0 или 1. Тогда семиразрядное число А=1001101 будет представлено следующим полиномом 6-степени:

1001101 = 1·2⁶ + 0·2⁵ + 0·2⁴ + 1·2³ + 1·2² + 0·2⁶ + 1·2⁰ = 2⁶ +2³ + 2²+1. 

В основу помехоустойчивого кодирования с помощью циклических кодов положено выполнение арифметических операций по modX (для 2-й системы счисления – по mod2) между кодируемыми числами А и фиксированным m-разрядным двоичным числом Р, которое представляется в виде фиксированного двоичного полинома (m-1)-й степени 

Р = p_m-1 X^m-1+ p_m-2 X^m-2+ p_m-3X^m-3 +....+ p₁ X¹ + p₀ X⁰. 

Такой фиксированный полином называется порождающим или образующим полиномом. Заметим, что в порождающем полиноме старший разряд (коэффициент p_m-1)всегда в общем случае не равен 0, т.е., в двоичной системе счисления он всегда равен 1.

В протоколе Х.25 для помехоустойчивого кодирования применяется циклический код с порождающим полиномом 16-й степени 

Р=2¹⁶+2¹²+2⁵+1= 1000100000010001. 

В этом полиноме коэффициенты p₁₆, p₁₂, p₅ и p₀ равны 1 (в выражении они не пишутся), остальные коэффициенты равны 0, поэтому соответствующие члены полинома отсутствуют. 

8.2.2. Операция умножения по mod2.

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

В исходном состоянии в регистре RGAзаписано число A, в регистре RGP – нули. Формирование n+m-разрядного произведения по mod2 осуществляется за n+mтактов в реальном масштабе времени. Произведение формируется на выходе устройства (выход правого сумматора по mod2) старшими разрядами вперед (в такте Т1 формируется старший разряд и т.д.).

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

Пример построения схемы умножения 7-разрядных чисел Aна порождающий полином 5-йстепени Р = 2⁵+2³+2⁰ = 101001показан на рис. 2. Работа схемы при умножении 7-разрядного числа A=1011011 на этот полином иллюстрируется таблицей 1.

В исходном состоянии в регистре RGAзаписано число A=1011011, в регистре RGP – нули. В каждом такте содержимое регистра RGAсдвигается на 1 разряд влево, а содержимое регистра RGP – вправо. При этом “выталкиваемый” из регистра RGAстарший разрядзаносится в освобождающийся старший разрядрегистра RGP. Для такта Т1 этот разряд помечен звездочкой (1* в строках “исх. сост.” регистра RGAи “Т1” регистра RGP). Для такта Т2 – 0* в строках “Т1” регистра RGAи “Т2” регистра RGP). В овобождающиеся при сдвиге разряды регистра RGAзаносятсянули.

Произведение по mod2 двух чисел может быть получено (и использовано для проверки) способом привычного умножения “в столбик” (таблица 2.).

Первая строка под верхней чертой представляет собой результат умножения множимого на младший разряд множителя, вторая строка – на третий разряд, третья строка – на пятый разряд множителя, т.е на те разряды, которые равны 1. В отличие от обычного умножения суммирование этих строк осуществляется по mod2. 

Таблица 1. Умножение 7-разрядного числа Aна порождающий полином 5-йстепени

Таблица 2. Умножение чисел “в столбик” 

8.2.3. Операция деления по 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.  

Таблица 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). 

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

Литература

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

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

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

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

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

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

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

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

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

З повагою ІЦ "KURSOVIKS"!