Таблица 1.1. ASCII-код

Таблица 1.2. Определения управляющих сигналов ASCII-кода

Десятичное представление

Аббревиатура сигнала

Определение

О 1 2 3 4 5 6 7 8 9

10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

28 29 30 31 127

FS GS RS

US DEL

Пустой символ Начало заголовка Начало текста Конец текста Конец передачи Запрос

Подтверждение приема

Возврат

Горизонтальная табуляция Перевод строки Вертикальная табуляция Перевод страницы Возврат каретки

Переход к новому набору символов Возврат в основной набор символов Смена канала данных Контроль устройства 1 Контроль устройства 2 Контроль устройства 3 Контроль устройства 4 Неподтверждение приема Символ синхронизации Конец передачи блока Отмена

Конец носителя Замена (символа) Переход к управляющей

последовательности Разделитель файлов Разделитель групп Разделитель записей Разделитель элементов Стирание

Набор символов IBM PC

Когда фирма IBM разрабатывала свой первый персональный компьютер, она создала набор символов, который в большей своей части был основан на ASCII-стандарте. Однако в дополнение к базовым ASCII-символам были определены печатные символы для первых 32 кодовых позиций, соответствующих управляющим символам. ASCII-алфавит был затем расширен за счет использования 8-разрядного двоичного кода, и 128 новых символов были определены для позиций от 128 до 255. Этот новый набор символов, используемый всюду в данной книге и называемый расширенным ASCII-кодом, представлен в табл. 1.3.

Таблица 1.3. Расширенный ASCII-код

Первая шестнад-цатеричная цифра

Вторая шестнадцатеричная цифра

0123456789ABCDEF

Глава 2

Ошибки, их обнаружение и коррекция

Ошибки возникают в любых системах передачи данных. Насколько серьзно влияние возникающих ошибок зависит как от типа данных, так и от ситуации, в которой эти данные генерируются. Информационная ценность простого текстового сообщения часто сохраняется при довольно большом числе ошибок, вносимых при передаче. В сообщении Встуетимся зт обедом в атоловой точное значение легко определяется из контекста.

Но бывают и совсем иные ситуации, когда требуется, чтобы полученная информация точно соответствовала первоначальной. Например, весьма неприятной была бы ошибка в одной-единственной цифре, сделанная при обновлении вашего текущего счета. В случаях, подобных этому, данные должны быть проверены, чтобы можно было гарантировать, что ошибки не прошли незамеченными. В этой главе рассматриваются типы и источники ошибок, а также представлен обзор методов, используемых для их обнаружения и коррекции.

Происхождение ошибок

Ошибки возникают во всех каналах связи. Эти ошибки можно классифицировать в соответствии с их источником по отношению к каналу связи (внутренние или внешние) и их временными характеристиками (статические или переходные). В зависимости от источника и длительности, усилия, которые нужно приложить для компенсации ошибки, могут изменяться от совершенно тривиальных до практически нереализуемых. В табл. 2.1 представлены некоторые ошибки, классифицированные в соответствии с их типом и длительностью. Имейте в виду, что многие ошибки попадают более чем в один класс, затрудняя тем самым простую классификацию.

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

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

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

Посимвольный контроль четности

Один из наиболее простых методов обнаружения ошибок - посимвольный контроль четности, известный также как поперечный контроль. В системе с таким контролем для обнаружения ошибок к каждому символу добавляется один дополнительный бит, называемый битом четности. Значение бита четности устанавливается равным О или 1 в зависимости от числа логических единиц в разрядах символа и в зависимости от того, какой тип контроля четности используется: проверка на четность или проверка на нечетность.

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

Хотя посимвольный контроль четности прост как по программной, так и по аппаратной реализации, его трудно назвать эффективным методом обнаружения ошибок. На рис. 2.1(a) показан 7-разрядный символ с добавленным битом четности в случае использования проверки на четность. Все 8 разрядов пересылаются по каналу связи.

Обнаружение ошибок

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

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

Рис. 2.1. Посимвольный контроль четности семиразрядного символа

(а) Символ, переданный с добавленным битом четности (проверка на четность)

10 I

(6) Рассчитанное значение бита четности совпадает с полученным значением

ПГвШйГТй

(в) Ошибка в одном разряде; рассчитанное значение бита четности не совпадает с полученным значением

1000№010!

(г) Ошибка в двух разрядах, не обнаруживаемая методом посимвольного контроля четности

ГИ000011 0 -

При получении символа требуемое значение бита четности рассчитывается по значениям 7 информационных разрядов и сравнивается со значением полученного бита четности, как показано на рис.2.1(6). Если символ и бит четности переданы без ошибок, эти два значения будут совпадать. На рис. 2.1(b) иллюстрируется случай появления ошибки в одном из разрядов исходного символа (неверный разряд отмечен жирным шрифтом). При сравнении рассчитываемого и принятого значений бита четности несовпадение указывает на ошибку.

В рассмотренном случае посимвольный контроль четности работал хорошо. Однако ситуация, иллюстрируемая на рис. 2.1(г), покат зывает слабость этого метода. В данном случае принимается символ с ошибками в двух разрядах: в шестом разряде символа (самый левый разряд) вместо 1 принят О, а в первом - вместо О принята 1. Но, поскольку в разрядах символа при этом по-прежнему остается четное число логических единиц, проверка на четность удовлетворяется и двойная ошибка не обнаруживается.

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

символов в стартстопном режиме передача бита четности соответствует 10% избыточной информации. Ясно, что по уровню обеспечиваемой при этом эффективности обнаружения ошибок посимвольный контроль четности - весьма слабый метод.

Поблочный контроль четности

Идея посимвольного контроля четности может быть логически продолжена для обнаружения ошибок на уровне блоков символов. Соответствующий метод известен как поблочный, или продольный, контроль четности. При использовании данной схемы заранее согласованное число символов (каждый со своим собственным битом четности) рассматривается как блок данных. Значение бита четности рассчитывается поперек блока для каждой позиции разрядов в символе. Эти разряды поблочного контроля затем добавляются к блоку (в его конце) в виде обычного символа.

На рис. 2.2(a) представлен пример реализации поблочного контроля четности. В этом примере соглашение между передатчиком и приемником состоит в том, что блок будет включать семь 7-разрядных символов, для каждого символа будет генерироваться его собственный бит четности (тип контроля - проверка на четность) и за информационными символами будет следовать символ четности блока (с тем же типом контроля). Точно так же, как бит четности символа устанавливает четность для отдельного символа, каждый разряд символа четности блока устанавливает четность для одной колонки разрядов в блоке.

Вспомним, что посимвольный контроль четности не обеспечивал выявления ошибок в четном числе разрядов отдельного символа. Подобная ситуация иллюстрируется на рис. 2.2(6), где двойная ошибка в первом символе не обнаруживается с помощью посимвольного контроля четности. Поблочный контроль четности, однако, обеспечивает обнаружение такой ошибки. Двухразрядная ошибка в первом символе блока преобразуется в две одноразрядные ошибки, когда четность рассчитывается для двух самых правых колонок данных. Поскольку рассчитываемый и принятый символы четности блока не совпадают, выдается сообщение об ошибке.

Хотя поблочный контроль четности является более эффективным методом обнаружения ошибок (с соразмерным увеличением избыточности), он все-таки не позволяет выявлять определенные типы ошибок. Иллюстрация такой ситуации представлена на рис. 2.2(b). Здесь двухразрядная ошибка возникает в первом и третьем символах. Как и следовало ожидать, эти ошибки не обнаруживаются с помощью по-

Рис. 2.2. Поблочный контроль четности

(а) Данные, переданные в виде блока с добавленным символом четности блока

Информационные Биты четности

разряды

символов

- Символы

(б) Данные, полученные с двухразрядной ошибкой в одном символе

Двухразрядная ошибка, не обнаруживаемая методом посимвольного контроля четности

[Г Ошибка, обнаруживаемая методом поблочного контроля четности

(в) Данные, полученные с двухразрядными ошибками в одних и тех же разрядах двух символов

Двухразрядная ошибка, не обнаруживаемая методом посимвольного контроля четности

Двухразоядная ошибка, не обнаруживаемая методом посимвольного контроля четности

Т Ошибки, не обнаруживаемые методом поблочного контроля четности

символьного контроля четности. Но, поскольку эти ошибки возникают в четном числе строк, они не обнаруживаются и с помощью поблочного контроля.

Поблочный контроль четности страдает тем же недостатком, что и поси.мвольный контроль: неспособностью к обнаружеНиюВсех ошибок. Посимвольный контроль четности обычно осуществляется автоматически в аппаратуре связи. Для поблочного контроля это не так. По этой причине, а также из-за его в целом низкой эффективности, поблочный контроль четности редко встречается в асинхронной связи.

Контрольная сумма

Хотя на практике возможности поблочного контроля четности весьма ограничены, но он позволяет ввести концепцию выявления ошибок на уровне контроля блоков. Более общим методом такого поблочного контроля является метод контрольной суммы. В простейшем случае арифметическая контрольная сумма вычисляется путем суммирования значений всех символов блока. Результирующая сумма затем добавляется к блоку и передается вместе с исходными данными.

К сожалению, термин контрольная сумма стал использоваться в более широком смысле - для обозначения любой величины, рассчитываемой для блока данных в соответствии с протоколом обнаружения ошибок. Однако в данной книге, если нет специальных указаний, термин контрольная сумма будет использоваться исключительно для обозначения простой арифметической контрольной суммы.

Например, контрольная сумма для семи 7-разрядных символов рассчитывается следующим образом:

1001000

+ 1101001

+ 1000111

+ 1110111

+ 1100101

+ 1101110

-I- 0100001

= 1001100011

Число разрядов, позволяющее вместить результируюш,ую контрольную сумму, изменяется в зависимости от значений суммируемых символов. В предыдущем примере контрольная сумма занимает 10 разрядов. Добавление этой контрольной суммы к блоку дан-

Рис. 2.3. Пример ошибок, которые не выявляются методом контрольной суммы

(а) Четное число одноразрядных ошибок в одном и том же столбце не обнаруживается

1111111 1010101

+ 0000000 -f 0101010

= 1111111 = 1111111

(б) Изменение порядка следования символов внутри блока не приводит к выявлению ошибки

0000011 0110000

+ 0001100 + 0001100

-f 0110000 + 0000011

= 0111111 = 0111111

ных осуществляется путем распределения ее разрядов по двум 7-разрядным символам с последующим восстановлением полной разрядности на приемном конце.

Чем больше длина символа и число символов в блоке, тем большее число разрядов требуется для максимально возможной контрольной суммы. Например, для блока из 256 семиразрядных символов максимальная контрольная сумма была бы 17-разрядной, и для ее переда чи потребовалось бы три символа. Во многих случаях контрольную сумму укладывают в заранее определенное число разрядов (обычно кратное разрядности символа) путем отбрасывания ее старших разрядов.

Как и рассмотренные выше методы обнаружения ошибок, метод контрольной суммы страдает присущими ему внутренними недостатками, ограничивающими его применимость. Самый главный из них - нечувствительность контрольной суммы к четному числу ошибок в одной колонке. Рассмотрим две контрольные суммы на рис. 2.3(a). Ясно видно, что данные в этих двух случаях существенно различаются, а контрольные суммы получаются одинаковыми. Кроме того, контрольная сумма нечувствительна к порядку следования символов в блоке. Такая ситуация иллюстрируется на рис. 2.3(6).

Контроль циклическим избыточным кодом

Как было показано выше, схемы обнаружения ошибок с использовав нием битов четности, символов четности и контрольной суммы реализуются относительно просто. К сожалению, неспособность этих схем

выявлять по отдельности неодиночные ошибки ограничивает их практическую применимость. Если бы в нашем наборе средств обнаружения ошибок были только такие методы, техника передачи данных находилась бы в весьма плачевном состоянии. К счастью, существуют более эффективные методы обнаружения ошибок, практическая реализация которых не вызывает проблем (хотя они не так просты в теории). Главный из них - контроль циклическим избыточным кодом, ЦИК (cyclical redundancy check, CRC).

ЦИК-контроль - гораздо более мощный метод обнаружения ошибок по сравнению с уже рассмотренными методами. Например, вариант данного метода, реализованный в популярном протоколе передачи файлов XMODEM-CRC, позволяет обнаруживать все одиночные и двойные ошибки и все ошибки в нечетном числе разрядов. Кроме того, выявляются все ошибки в пакетах длиной 16 разрядов и менее, 99,9969% ошибок в пакетах длиной точно 17 разрядов и 99,9984% ошибок во всех более длинных пакетах.

ЦИК-контроль, как и метод контрольной суммы, используется для обнаружения ошибок на уровне блоков данных. Однако он основан не на прямом суммировании значений символов, а на делении и умножении многочленов. В определенном смысле ЦИК-контроль есть алгоритм хэширования. Алгоритм хэширования отображает (хэ-ширует) элементы большого набора (набора данных) на элементы меньшего и, как правило, более управляемого набора (хэш-набора).

Процесс хэширования приводит к потере информации - такова его природа. Это следует из простого анализа. Хотя каждый отдельный элемент набора данных отображается на один и только один элемент хэш-набора - обратное неверно. При ЦИК-контроле большой набор всех возможных двоичных чисел отображается на меньший набор всех возможных ЦИК. По определению, с помощью 16-разрядного ЦИК можно представить 65 536 различных величин. Если, например, имеется набор из 65537 различных блоков данных, то по меньшей мере двум различным блокам будет соответствовать один и тот же ЦИК. Наиболее существенное практическое следствие изложенного заключается в том, что ЦИК-контроль очень хорошо подходит для обнаружения изменений в блоках данных, вызванных ошибками, возникающими при последовательной передаче данных. Однако при его использовании для выявления вирусных искажений дисковых файлов он не обеспечивает вполне надежной защиты от изощренных создателей вирусных программ.

Строгое математическое рассмотрение работы ЦИК-алгоритма и анализ причин его высокой эффективности не входит в задачу данной книги. Но, если эта проблема вас заинтересует, вы можете получить соответствующую информацию из нескольких литературных источ-

НИКОВ, ссылки на которые приведены в конце книги. Поэтому после краткого обсуждения принципов ЦИК-контроля основное внимание будет уделено его реализации и применению.

Многочлены. Согласно формальному опреде.г1ению, много-ч.пен - это линейная комбинация произведений целых степеней заданного набора переменных с постоянными коэффициентами. В качестве примера рассмотрим представление десятичного числа 511 в виде многочлена:

51110 = S-lO-f ЫО-Ь 1-10°

= bz + lz+l (где Z = 10).

Здесь в качестве значения переменной, о которой шла речь в определении многочлена, выбрано число 10, и коэффициенты многочлена, взятые в порядке убывания степеней переменной, образуют число 511.

Выбор числа 10 в качестве значения переменной z не имеет какого-то особого смысла. Любое число с таким же успехом можно представить в виде многочлена с другим основанием. Так, чтобы представить десятичное число 498 в виде многочлена с основанием 8, нужно просто изменить значение переменной, как показано ниже:

498io = 7628 = 7-82-f 6 8-f 2-8° =

= 7j/2-f6j/-f2 (где J/= 8).

Обратим опять внимание, что коэффициенты многочлена есть просто отдельные цифры 7, 6 и 2 в записи исходного восьмеричного числа.

Расчеты ЦИК выполняются в двоичной системе. Отдельные символы в передаваемом блоке как бы соединяются последовательно в одно большое двоичное число. Результирующая двоичная последовательность представляется затем в виде линейной комбинации степеней двойки. Например, двоичное число 10100101b представляется в виде многочлена с основанием 2 следующим образом:

10100101b = 1-2-f 0-2-fl.25--0-2-f 0-23-f 1-22 +

-fO-21-f 1-2°

= Ix -f Ox -f la: + Oa: + Qi -f la: + Oi* + la:°

(где X = 2).

Нет ничего удивительного, что коэффициенты этого многочлена есть цифры исходного двоичного числа.

Совершенно очевидно, что при используемом способе записи полученное выражение выглядит весьма громоздко. К счастью, в силу своей природы коэффициенты двоичного многочлена должны быть

равны или О, или 1. Поскольку слагаемые с нулевыми коэффициентами не дают никакого вклада, их можно отбросить. Следовательно, все оставшиеся коэффициенты должны быть равны 1. Упрощая дальше, эти единицы можно опустить, оставляя только переменную и ее степени. И наконец, слагаемое а;° можно записать в эквивалентном виде как 1. Результирующее, численно эквивалентное исходному (и намного более компактное) выражение для многочлена принимает вид:

lOlOOlOlb = + z* + а: + 1 (где х = 2).

Операхщи над многочленами. Двоичное число, которое бы.по преобразовано в многочлен в предыдущем примере, содержало всего восемь разрядов. Естественно, что полученный многочлен не является типичным представителем тех многочленов, которые используются в обычных системах передачи данных. Например, блок данных, включающий 128 восьмиразрядных символов, представляется в виде многочлена, состоящего из 1024 слагаемых. Аналогично, для 1024-байтного блока потребовался бы многочлен с 8192 слагаемыми. Очевидно, что попытка записи таких многочленов в тексте совершенно бесполезна для иллюстративных целей.

В операциях над многочленами (а вычисления ЦИК - их частный случай) двоичное число, сформированное путем последовательной сцепки составляющих блока данных, называется многочленом данных (или многочленом сообщения) и обозначается как D(x). Многочлен данных делится на предварительно согласованный многочлен, называемый порождающим многочленом G{x). Операция деления дает в результате многочлен-частное Q(x) и остаточный многочлен Rix).

На это можно взглянуть и несколько иначе: R(x) есть просто двоичное число, которое после вычитания из D{x) дает в результате еще один многочлен, деляид4йся без остатка на G(a;). Результат этой операции деления есть частное <Э(а;). Вообще, частное за ненадобностью отбрасывается, а остаточный член R(x) известен просто как ЦИК. Это соотношение между многочленами записывается спедую-шам образом:

D(x) = Q(x)-G{x)-{-R(x)

или в эквивалентной форме

Р{х)-Щх)

G{x)

Одно из важных свойств порождающих многочленов заключается в том, что число разрядов в остатке непосредственно определяется

ЧИСЛОМ разрядов в G{x). Чтобы понять причину этого, вспомним, что по определению остаток при любой операции деления должен быть меньше делителя. Выбор п-разрядного порождающего многочлена гарантирует, что остаточный многочлен будет иметь не более чем п-1 двоичных разрядов.

Вообще, при выборе порождающего многочлена руководствуются двумя соображениями: желаемой разрядностью остатка (см. предыдущий абзац) и его способностью выявлять ошибки. Обсуждение математических подходов, позволяющих оценить эффективность того или иного порождающего многочлена, не входит в задачу данной книги. Да это, к счастью, не так уж необходимо. Несколько избранных порождающих многочленов всесторонне проанализированы в отношении их эффективности, приняты практически повсеместно и одобрены международными организациями - учредителями стандартов.

Общепринятые ЦИК-многочлены. Один из наиболее известных порождающих многочленов стандартизован в спецификации V.41 МККТТ, озаглавленной Кодонезависимая система контроля ошибок . Это тот же самый многочлен, который используется в протоколе XMODEM-CRC и производных от него протоколах передачи данных. Этот многочлен порождает 16-разрядный остаточный многочлен и представляется в виде

Всюду в данной книге данный многочлен называется порождающим многочленом CCITT-16 (МККТТ-16). Другое общепринятое обозначение этого многочлена CRC-CCITT (ЦИК-МККТТ). Не спутайте только этот многочлен с еще одним популярным 16-разрядным порождающим многочленом, который обозначается просто как CRC-16 {ЦИК-16). Последний приобрел широкую известность как часть протокола двоичной синхронной передачи фирмы IBM. Он также определяется в альтернативной процедуре в Приложении А к стандарту V.42 МККТТ, озаглавленной Процедура коррекции ошибок для ООЛ*) с использованием асинхронно-синхронного преобразования . Многочлен CRC-16 представляется в виде

Как уже отмечалось выше, ЦИК-контроль представляет собой алгоритм хэширования с ограниченным числом различных хэш-величин. Увеличение их числа легко достигается путем увеличения

Оконечное оборудованве линии (см. гл. 4). - Прим. персе.

числа разрядов ЦИК, т. е. путем выбора других порождающих многочленов. Так, порождающий многочлен CCITT-32 дает 32-разрядный остаток и также стандартизован в спецификации V.42 МККТТ. Благодаря 32-разрядному остатку набор различных хэш-величин (т. е. набор ЦИК) расширяется более чем до 4 млн. Многочлен СС1ТГ-32 представляется в виде

а;32 + 23 22 16 12 11 10 8

+ х' + х^ + x + + X + I.

И еще один последний порождающий многочлен, который может вам встретиться - это мпогоч.пен CRC-12. Данный многочлен используется в тех случаях, когда для ЦИК выделяется меньшее число рг1зрядов или когда не требуется более высокая точность более длинных ЦИК. Многочлен CRC-12 представляется в виде

х + х' + х^ + 1.

Вычисления 16-разрядного ЦИК. При расчете 16-разрядного ЦИК отдельные разряды сообщения последовательно объединяются в одно большое двоичное число , значения разрядов этого числа образуют набор коэффициентов многочлена данных. Величина самого старшего разряда первого байта данных есть коэффициент при слагаемом высшей степени в многочлене данных. Величина самого младшего разряда последнего байта данных есть коэффициент при х° в этом многочлене.

Перед операцией деления многочлен данных умножается на a;. Это обеспечивает добавление 16 нулевых разрядов к исходному многочлену данных (на его конце). Затем многочлен данных делится на порождающий многочлен. Заметим, однако, что при расчете ЦИК не используется операция обычного арифметического деления. Вместо этого используется арифметика по модулю 2 (без каких-либо переносов или заемов). На практике такая арифметика реализуется с помощью логической функции исключающее ИЛИ (XOR). Добавление 16 нулевых разрядов необходимо для того, чтобы пропустить через эту операцию деления все разряды сообщения. Остаток, получаемый в результате деления, есть нужный нам ЦИК.

На практике алгоритм вычислений ЦИК переписывается таким образом, что отпадает необходимость в хвосте нулевых разрядов, по в результате получается тот же самый ЦИК, который получи.пся бы при использовании исходного алгоритма. Отметим также, что в аппаратной и программной реализациях ЦИК-алгоритма (в отличие от обычной операции деления многочленов) совершенно необязательно

использовать слагаемое высшей степени в порождающем многочлене. Например, многочлен CCITT-16 используется просто как 16-разрядная величина 1021h.

В данном разделе представлено несколько различных, но функционально эквивалентных программных реализаций вычислений ЦИК. Приведенные здесь подпрограммы написаны в основном для иллюстрации принципов расчета ЦИК, а не самых быстрых методов ЦИК-вычислений. Используйте эти подпрограммы для создания своих собственных программ. Помните, что независимо от языка программирования, с помощью которого реализуется ЦИК-алгоритм, наиболее важным достоинством ЦИК-подпрограммы является ее быстродействие. Канал связи с быстродействием 14,4 Кбит/с может потерять уйму времени, если он каждый раз будет ждать результатов выполнения медленной ЦИК-подпрограммы.

В листинге 2.1 представлена программная реализация поразрядного алгоритма расчета ЦИК на ассемблере (с использованием порождающего многочлена CCITT-16). Листинг 2.2 представляет эквивалентный вариант на языке Си. Поразрядный алгоритм - весьма допотопный вариант ЦИК-вычислений. Программа выполняется медленно даже при ее полной оптимизации. Данный способ вычислений ЦИК приведен здесь только потому, что он хорошо иллюстрирует ЦИК-алгоритм.

Листинг 2.1. Программа расчета 16-разрядного ЦИК на ассемблере (поразрядный алгоритм)

CRC16 BIT

Поразрядно преобразует байт в 16-разрлдн|18 ЦИК

tL S байт данных

ВХ = лорождашцин ниогочлен CCITT-16 DX = ЦИК-аккуиулятор (О при первой внзове) Выход:

DX = обновленный аккумулятор

Изиенеиил: АХ СХ DX

CRCie.BIT PROC BEAR

ASSUME CS:CSEG, DS:IOTHIIG, ES:IOTHIIG. SS:IOTHIIC

C l:

nOV CX,8 ;Число обрабатнваешх разрядов

HOV AH.DH ;Переслать ЦНК в АН

XOR AH.AL :н XOR с байтои данннх

CLC RCL

JIS XOR

LOOP

CRC16 Bir EIDP

DX.l

C 2 DX.BX

AL,1 C l

;длл установки SF

;Если CF=0, RCL действует так ; же, как SHL, но не изменяет SF

;Еспн HSB для XOR бил 1, SF=1 ;XGR ЦИК с порождавший ;иногочлеиои

; Переслать следунищй бит ;данных в HSB

;Повторить для каждого бита

Листинг 2.2. Программа расчета 16-разрядного ЦИК на языке Си (поразрядный алгоритм)

* int CRC16 Bit(int. char*, int) *

* Эта функция вычисляет 16-разрядкий ЦИК для блока данных

* поразрядный кетодон.

* Первый аргунент - начальное значение ЦИК.

* Второй аргунент - указатель блока данных.

* Третий аргунент - число байтов в блоке.

* Функция возвраадет 16-разрядный ЦИК как целуй величину. *

* Обязательно определите CRC POLY как ♦ define CRC.POLY 0x1021

int CRC16 Bit(crc, msg, nsg.len)

int crc ;/ исходное значение ЦИК, О при первой вызове */

char nsg ;/* указатель блока сообщения / int nsg len ;/* число байтов в блоке /

int j, data ; nhile(nsg len- >0) {

data = risg++ 8 ; /♦ данные - в старший байт */

for(j=0; j<8; ++j) {/ проверить каждый бит */

LOOP С 1 RET

CRC16 BVTE EIDP

return (crc к OxFFFF) ; / возвратить 16 илвдвих разрядов */

Побайтовый алгоритм работгт немного быстрее, но он менее очевиден. В этом случае байт данных объединяется функцией исключающее ИЛИ с содержимым ЦИК-аккумулятора только один раз. Но результат должен по-прежнему сдвигаться и, возможно, объединяться по исключающему ИЛИ с порождающим многочленом по одному разу для каждого разряда. Листинг 2.3 представляет этот алгоритм на ассемблере, а листинг 2.4 - на языке Си.

Листинг 2.3. Программа расчета 16-разрядного ЦЙК на ассемблере (побайтовый алгоритм)

CRC16 BYTE

Преобразует байт в 1б-разрядни8 ЦИК (побайтовый алгоритм)

Листинг 2.4. Программа расчета 16-разрядного ЦИК на языке Си (побайтовый алгоритм)

AL = байт данных

ВХ = порождаи110<й нногочяен CCITT-16 DX = ЦИК-аккунулятор (О при лервон вызове) Выход:

DX - обновленный аккунулятор

int CRC16 Byte(int, char*, int) *

Эта функция вычисляет 16-разрядный ЦИК для блока данных

побайтовый методом.

Первый аргумент - начальное значение ЦИК.

Второй аргумент - уназатель блока данных.

Третий аргумент - число байтов в блоке.

Функция воэвра ает 16-разрядный ЦИК как целув величину. *

Обязательно определите CRC.POLY как . define CRC POLY 0x1021

int CRC16 Byte(crc, nisg, msg.len)

int crc ;/ исходное значение ЦИК, О при первом вызове /

char rasg ;/ указатель блока сообкенял / int nsg.len ;/ число байтов в блоке /

int j ;

vhile(nsg len~ >0) {

/*XOR байта данных со старшин байтом аккумулятора / crc = crc (int)*iiisg++ 8 ;

for(j=0; j<8; ++j) / проверить каждый бит / if (crc к 0x8000) /* if HSB = 1 /

crc = crc l - 0x1021 ; / сдвиг и XOR */ else

crc = crc l ; /*иначе просто сдвиг */

return (crc к OxFFFF) ; / возвратить 16 младших разрядов /

/ если msb для хог даиных с ЦИК стк TRUE */ if ( (data - crc) к 0x8000)

crc = (crc 1) * CRC POLY ; /* сдвиг и XOR / else crc = crc 1 ; / иначе просто сдвиг /

data =1 ; /* проверить следуиций бит /

;Повторить для каждого бита