Способы контроля правильности передачи данных

 

Управление правильностью (помехозащищенностью) пере­дачи информации выполняется с помощью помехоустойчивого кодирования. Различают коды, обнаруживающие ошибки, и корректирующие коды, которые дополнительно к обнаруже­нию еще и исправляют ошибки. Помехозащищенность дости­гается с помощью введения избыточности. Устранение ошибок с помощью корректирующих кодов (такое управление называют Forward Error Control) реализуют в симплексных каналах связи. В дуплексных каналах достаточно применения кодов, обнару­живающих ошибки (Feedback or Backward Error Control), так как сигнализация об ошибке вызывает повторную передачу от источника. Это основные методы, используемые в информа­ционных сетях.

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

 

Код Хемминга

 

В коде Хемминга вводится понятие кодового расстояния d (расстояния между двумя кодами), равного числу разрядов с неодинаковыми значениями. Возможности исправления оши­бок связаны с минимальным кодовым расстоянием d min. Ис­правляются ошибки кратности r = ent(d min–1)/2 и обнаружи­ваются ошибки кратности d min–1 (здесь ent означает “целая часть”). Так, при контроле на нечетность dmin=2 и обнару­живаются одиночные ошибки. В коде Хемминга d min=3. Дополнительно к информационным разрядам вводится L =log2 K избыточных контролирующих разрядов, где К – число информационных разрядов, L округляется до ближайшего большего целого значения. L -разрядный контролирующий код есть инвертированный результат поразрядного сложения (т.е. сложения по модулю 2) номеров тех информационных разря­дов, значения которых равны 1.

Пример 1. Пусть имеем основной код 100110, т.е. К = 6. Следовательно, L = 3 и дополнительный код равен

010 # 011 # 110= 111,

где # – символ операции поразрядного сложения, и после инвертирования имеем 000. Теперь вместе с основным кодом будет передан и дополнительный. На приемном конце вновь рассчитывается дополнительный код и сравнивается с передан­ным. Фиксируется код сравнения (поразрядная операция от­рицания равнозначности), и если он отличен от нуля, то его значение есть номер ошибочно принятого разряда основного кода. Так, если принят код 100010, то рассчитанный в прием­нике дополнительный код равен инверсии от 010 # 110 = 100, т.е. 011, что означает ошибку в третьем разряде.

Пример 2. Основной код 1100000, дополнительный код 110 (результат инверсии кода 110 # 111 =001). Пусть принятый код 1101000, его дополнительный код 010, код сравнения 100, т.е. ошибка в четвертом разряде.

 

Циклические коды

 

К числу эффективных кодов, обнаруживающих одиночные, кратные ошибки и пачки ошибок, относятся циклические коды (CRC – Cyclic Redundance Code). Они высоконадежны и могут применяться при блочной синхронизации, при которой выде­ление, например, бита нечетности было бы затруднительно.

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

Образующий полином есть двоичное представление одного из простых множителей, на которые раскладывается число Xn–1, где Xnобозначает единицу в n-м разряде, n равно числу разрядов кодовой группы. Так, если n =10 и Х=2, то Xn–1=1023=11·93, и если g (X) = 11 или в двоичном коде 1011, то примеры циклических кодов Ai · g (X) чисел Ai в кодовой группе при этом образующем полиноме можно видеть в табл. 2.2.

Основной вариант циклического кода, широко применяе­мый на практике, отличается от предыдущего тем, что операция деления на образующий полином заменяется следующим ал­горитмом: 1) к исходному кодируемому числу А справа припи­сывается К нулей, где К – число битов в образующем полиноме, уменьшенное на единицу; 2) над полученным числом А (2 К) выполняется операция О, отличающаяся от деления тем, что на каждом шаге операции вместо вычитания выполняется по­разрядная операция “исключающее ИЛИ”; 3) полученный ос­таток В и есть CRC – избыточный K -разрядный код, который заменяет в закодированном числе С приписанные справа К нулей, т.е.

 

На приемном конце над кодом С выполняется операция О. Если остаток не равен нулю, то при передаче произошла ошиб­ка и нужна повторная передача кода А.

Пример 3. Пусть А = 1001 1101, образующий полином 11001.

Так как К = 4, то А (2 К)=100111010000. Выполнение опера­ции О расчета циклического кода показано на рис. 2.7.

 

Рис. 2.7. Пример получения циклического кода

 

Положительными свойствами циклических кодов являются малая вероятность необнаружения ошибки и сравнительно не­большое число избыточных разрядов.

Общепринятое обозначение образующих полиномов дает следующий пример:

g (X) = Xl6 + Х l2 + Х5+ 1,

что эквивалентно коду 1 0001 0000 0010 0001.

 

Сжатие данных

 

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

К = n / q,

где n – число минимально необходимых символов для передачи сообщения (практически это число символов на выходе эталонного алгоритма сжатия); q – число символов в сообщении, сжатом данным алгоритмом. Так, при двоичном кодировании n равно энтропии источника информации. Часто степень сжа­тия оценивают отношением длин кодов на входе и выходе алгоритма сжатия.

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

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

Очевидный способ сжатия числовой информации, представленной в коде ASCII, заключается в использовании сокращенного кода с четырьмя битами на символ вместо восьми, так как передается набор, включающий только 10 цифр, сим­волы “точка”, “запятая” и “пробел”.

Среди простых алгоритмов сжатия наиболее известны ал­горитмы RLE (Run Length Encoding). В них вместо передачи цепочки из одинаковых символов передаются символ и значе­ние длины цепочки. Метод эффективен при передаче растро­вых изображений, но малополезен при передаче текста.

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

Предсказывающие (предиктивные) методы основаны на экстраполяции значений амплитуд отсчетов, и если выполнено условие

Ar – Ap > d,

то отсчет должен быть передан, иначе он является избыточным; здесь Аr и Ар – амплитуды реального и предсказанного отсчетов; d – допуск (допустимая погрешность представления амплитуд).

Иллюстрация предсказывающего метода с линейной экстрапо­ляцией представлена на рис. 2.8. Здесь точками показаны пред­сказываемые значения сигнала. Если точка выходит за пределы “коридора” (допуска d), показанного пунктирными линиями, то происходит передача отсче­та. На рис. 2.8 передаваемые отсчеты отмечены темными кружками в моменты времени t1, t2, t4, t7. Если передачи от­счета нет, то на приемном конце принимается экстрапо­лированное значение.

 

 

Рис. 2.8. Предиктивное кодирование

 

Методы MPEG (Moving Pic­tures Experts Group) используют предсказывающее кодирование изображений (для сжатия дан­ных о движущихся объектах вместе со звуком). Так, если передавать только изменившиеся во времени пиксели изображения, то достигается сжатие в несколько десятков раз. Методы MPEG становятся ми­ровыми стандартами для цифрового телевидения.

Для сжатия данных об изображениях можно использовать также методы типа JPEG (Joint Photographic Expert Group), ос­нованные на потере малосущественной информации (не раз­личимые для глаза оттенки кодируются одинаково, коды могут стать короче). В этих методах передаваемая последовательность пикселей делится на блоки, в каждом блоке производится преобразование Фурье, устраняются высокие частоты, переда­ются коэффициенты разложения для оставшихся частот, по ним в приемнике изображение восстанавливается.

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

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

Этот недостаток устраняется в однопроходных алгоритмах адаптивного сжатия, в которых схема кодирования есть схема приспособления к текущим особенностям передаваемого пото­ка символов. Поскольку схема кодирования известна как ко­деру, так и декодеру, сжатое сообщение будет восстановлено на приемном конце.

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

Интересен алгоритм “стопка книг”, в котором код символа равен его порядковому номеру в списке. Появление символа в кодируемом потоке вызывает его перемещение в начало списка. Очевидно, что часто встречающиеся символы будут тяготеть к малым номерам, а они кодируются более короткими цепочками 1 и 0.

Кроме упомянутых алгоритмов сжатия существует ряд дру­гих алгоритмов, например LZ-алгоритмы (алгоритмы Лемпеля–Зива). В LZ-алгоритме используется следующая идея: если в тексте сообщения появляется последовательность из двух ранее уже встречавшихся символов, то эта последовательность объявля­ется новым символом, для нее назначается код, который при определенных условиях может быть значительно короче исход­ной последовательности. В дальнейшем в сжатом сообщении вместо исходной последовательности записывается назначен­ный код. При декодировании повторяются аналогичные дей­ствия и поэтому становятся известными последовательности символов для каждого кода.