Глава 7. Алгоритмы сети Ethernet-Fast Ethernet (Глава 7. Алгоритмы сети Ethernet-Fast Ethernet)

Посмотреть архив целиком

7.2.2. Характеристики и разновидности помехоустойчивых кодов

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

Помехоустойчивый код характеризуется тройкой чисел (n, k, d0), где n— общее число разрядов в передаваемом сообщении, включая проверочные (г), k=n-r - число информационных разрядов, d0— минимальное кодовое расстояние между разрешенными кодовыми комбинациями, определяемое как минимальное число различающихся бит в этих комбинациях. Число обнаруживаемых (tj и (или) исправляемых (t ) ошибок (разрядов) связано с параметром d0 соотношениями

Иногда используются дополнительные показатели избыточности, производные от приведенных выше характеристик n, k:R = r/n- относительная избыточность, v = k / n - относительная скорость передачи.

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

Рис. 7.3. Классификация помехоустойчивых кодов

Простейшими систематическими кодами являются биты четности/нечетности. Они не позволяют обнаружить ошибки четной кратности (т.е. ошибки одновременно в двух, четырех и т.д. битах) и поэтому используются при невысоких требованиях к верности принимаемых данных (или при малой вероятности ошибок в линии передачи). Примером может служить бит Parity (соответствие) в установках режимов работы последовательного порта с помощью команды MODE (MS DOS). Несмотря на ограниченные возможности обнаружения ошибок, биты четности/нечетности имеют большое значение в теории помехоустойчивого кодирования. Одни иг первых математически обоснованных и практически использовании? помехоустойчивых кодов - коды Хэмминга представляют собой простс совокупность перекрестных проверок на четность/нечетность. Циклические коды могут рассматриваться как обобщенные проверки на четность/ нечетность (см. далее).

7.2.3. Циклические коды (CRC)

Циклические коды - это целое семейство помехоустойчивых кодов, вклю чающее в себя в качестве одной из разновидностей коды Хэмминга, но : целом обеспечивающее большую гибкость с точки зрения возможност] реализации кодов с необходимой способностью обнаружения и исправ ления ошибок, определяемой параметром d0, по сравнению с кодами Хэм минга (для которых dQ=3 или d0=4). Широкое использование цикличес ких кодов на практике обусловлено также простотой реализаци соответствующих кодеров и декодеров.

Основные свойства и само название циклических кодов связаны с те!\ что все разрешенные комбинации бит в передаваемом сообщении (коде вые слова) могут быть получены путем операции циклического сдвиг некоторого исходного кодового слова:

Циклические коды задаются с помощью так называемых порождающр полиномов (многочленов) g(x) или их корней. Кроме того, вводятся понятия полинома исходного сообщения

Для этих полиномов, представляющих собой, по существу, альтерната ную запись чисел в двоичной системе счисления, определяются опер ции сложения, умножения и деления, необходимые для организации i

дирования н декодирования сообщения. Все эти операции выполняются по модулю 2.

Рассмотрим последовательность кодирования на примере циклического кода (7,4,3), имеющего g(x) = х3 + х + 1:

1) информационная часть сообщения записывается в виде полинома:

В рассматриваемом примере k = 4 и для сообщения 0111 получаем

2) и(х) умножается хг, что соответствует циклическому сдвигу исходного сообщения на г разрядов влево:

3) полученный многочлен делится на g(x):

где с(х)-полином - частное с максимальной степенью (k-1); R(x)-полином - остаток с максимальной степенью (г-1); © - обозначение поразрядной операции суммирования по модулю 2 (исключающее ИЛИ).

Кодированное сообщение представляется в виде

то есть на месте младших, освобожденных после домножения на хг, разрядов, записываются проверочные разряды.

Для рассматриваемого примера:

Таким образом, в данном случае А(х) = (х3 + х4 + х3) © х = х5 + х4 + х3 + х. Передаваемое кодированное сообщение в обычной двоичной форме имеет вид:

Один из возможных вариантов аппаратурной реализации кодера для рассматриваемого примера представлен на рис. 7.4 вместе с последовательностью сигналов, подтверждающей получение тех же самых проверочных разрядов (010) на восьмом такте (г + k + 1 = 8).

Кодер представляет собой сдвиговый регистр с обратными связями, организуемыми с помощью элементов М2 (исключающее ИЛИ, сумматор по модулю 2). Структура обратных связей полностью определяется ненулевыми коэффициентами порождающего полинома g(x).

Рис. 7.4. Пример формирования циклического кода (сигнал обратной связи отличен от нуля на 5-м и б-м тактах)

На первых восьми тактах ключ Кл. находится в верхнем положении и формируются проверочные разряды. Затем ключ Кл. устанавливается в

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

Двухвходовый элемент М2, на один из входов которого подается в последовательной форме сообщение, на выходе формирует бит четности или нечетности (в зависимости от значения сигнала на втором входе элемента М2 - 0 или 1) для этого сообщения. В схеме кодера (рис. 7.4) элементы М2 включены между отдельными триггерами сдвигового регистра, причем сигналы обратной связи, поступающие на «свободные» входы элементов М2 (не связанные с передачей собственно сообщения через сдвиговый регистр), зависят как от предшествующих разрядов сообщения, так и от структуры обратных связей, принятой в кодере. В результате циклический код, формируемый таким кодером, можно считать совокупностью обобщенных бит четности и нечетности, тип которых (четность или нечетность) не определен заранее и может динамически меняться от такта к такту.

Порождающие полиномы, представляющие собой т. н. неприводимые многочлены (многочлены, которые делятся лишь на единицу и на самих себя), табулированы для разных значений n, k и dQ, например, п = 7...255, k = 3...247, d0= 3...127. Практически в компьютерных сетях используются циклические коды длиною в 2 или 4 байта (16 или 32 бита), а параметры п, k и d0 в явном виде не указываются. Это связано с возможностью выбора различной длины поля данных в пакете на этапе установления и выбора параметров соединения при неизменной длине поля циклического кода. Теоретическая вероятность ошибки при приеме в случае использования циклического кода не хуже рощ < 1/2г, так что для выполнения условия стандарта рош < 10"6 необходимое число проверочных разрядов г > Iog2106 = 20. Кроме случайно распределенных, циклический код позволяет обнаруживать подряд следующие ошибки (так называемые пакеты ошибок) длиною 1 = г или меньше. Это особенно важно в связи с возможностью возникновения продолжительных во времени помех, действующих на протяженные линии передачи в компьютерных сетях.

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

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

Следует сделать два замечания относительно сложившейся терминологии. Хотя понятие «циклические коды» достаточно широкое, на практике его обычно используют для обозначения только одной разновидности, описанной выше и имеющей в англоязычной литературе название CRC (Cyclic Redundancy Check - циклическая избыточная проверка). Более того, иногда поле пакета, фактически содержащее код CRC, называется «контрольной суммой», что в принципе не совсем верно, но встречается повсеместно.


Случайные файлы

Файл
21497.doc
63260.rtf
7404-1.rtf
71497-1.rtf
102335.rtf




Чтобы не видеть здесь видео-рекламу достаточно стать зарегистрированным пользователем.
Чтобы не видеть никакую рекламу на сайте, нужно стать VIP-пользователем.
Это можно сделать совершенно бесплатно. Читайте подробности тут.