Лекция 11. Помехозащитное кодирование при передаче по линиям связи
Курс “Теория информации и кодирования”

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

Циклические коды
Потоковые (сверточные) коды
Другие направления помехозащитного кодирования
Обзор направлений классификации и применения

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

Общая характеристика циклических кодов
Напомним, что название “циклических” кодов связано с особенностью построения их образующей матрицы: все ее строки образуются циклическим сдвигом первой строки. Эти коды также часто обозначаются аббревиатурой CRC (Cyclic redundancy check — циклическая избыточная проверка). Требования к CRC-кодам исходя из их применения иллюстрирует рис.11.1:
  • при передаче информационных блоков в последовательном режиме (например, по линиям связи) контрольные разряды образуют “хвостовик”, который может формироваться по мере поступления информации. На практике это означает, что скорость кодирования не важна, поскольку темп поступления данных для передачи на порядки ниже, чем скорость логической обработки (в отличие например, от кодирования в оперативной памяти, где весь результат должен быть получен максимально быстро);
  • вместе с тем, важным требованием является масштабируемость — информационные блоки могут иметь различную длину, в том числе и большую. Например, это могут быть тысячи разрядов кода (опять-таки, в противоположность случаю оперативной памяти, где все кодовые блоки имеют фиксированную и небольшую длину);
  • наконец, для передачи по линиям связи характерно возникновение “пачек” ошибок в соседних разрядах. Например, при искажении сигнала, который несет несколько бит информации. Ключевым требованием к коду является выявление таких случаев (для кодирования в оперативной памяти напротив характерны были однократные ошибки). При этом исправление обнаруженных ошибок выполняется методом перезапроса (в ОП, где невозможно хранить копии всех данных, исправление должен был выполнять сам код);
  • исходя из упомянутых требований оптимальным математическим инструментом кодирования являются операции с многочленами. Например, признаком правильности кода может быть его делимость нацело на определенный многочлен (как среди чисел выделяются делящиеся например на 10). Операция деления занимает много времени, но для нас это не важно. С другой стороны делить можно любые числа (масштабируемость). И конечно, при искажении число с большой вероятностью перестанет делиться нацело на заданную величину. Рассмотрим теперь конретную реализацию такого подхода.

Математический аппарат циклических кодов
Особенности математического аппарата циклических кодов иллюстрирует рис.11.2:
  • напомним, что исходному k-разрядному значению информационного кода соответствует определенный полином, который обозначим b(x). Чтобы перейти к полному n-разрядному формату дополним исходный m код нулями. Это соотвествует умножению полинома на xm;
  • результирующий n-разрядный полином f(x) по условиям кодирования должен нацело делиться на образующий g(x) со старшей степенью m. Чтобы это обеспечить, поделим b(x) xm на и остаток r(x), который «мешает» делению нацело, прибавим к b(x) xm. Результат, который теперь наверняка поделится на g(x), и будет искомым f(x). Таким образом, кодирование выполнено;
  • декодирование сводится к делению полученного многочлена f*(x) на g(x). Если ошибок не было, то он поделится нацело. Ненулевой остаток от деления говорит об ошибках передачи. Важно, что CRC-код позволяет обнаружить любые сочетания ошибок на отрезке кода длиной m разрядов. Например, если мы используем 8 контрольных разрядов (m=8), то код сможет обнаружить любое сочетание ошибок в соседних 8 разрядах;
  • отдельный вопрос составляет выбор образующего многочлена кода. Он должен отвечать ряду математических условий (рис.11.2). Однако на практике такие многочлены выбирают из готовых таблиц. Наиболее удобные варианты стандартизированы. Помимо примеров, показанных на рис.11.2, существуют стандарты для 4-, 12- и 32-разрядных многочленов. В современной практике CRC-коды с образующими многочленами g16(x) широко используются в глобальных компьютерных сетях и дисковых контроллерах, а g32(x) – в контроллерах сетевых карт ПК (для локальных сетей).

Пример использования циклического кода 7,4
Рассмотрим пример кодирования и декодирования циклическим кодом 7,4.
Для данного кода количество контрольных разрядов составляет m=3. Перечисленным выше требованиям отвечают всего два варианта образующего многочлена: g(x) = x3+x +1 и g(x) = x2+x2+1. В дальнейшем в примере используется первый из этих двух многочленов (рис.11.3).
Пусть k=4 информационных разряда имеют значения 1010. На верхней части рисунка показана последовательность выполнения кодирования и декодирования согласно описанной выше процедуре:
  • информационному блоку 1010 отвечает многочлен b(x) = x3+x. Соответственно b(x)*x3= x6+x4;
  • контрольные разряды 011 отображают многочлен r(x) = x+1 - остаток от деления b(x)*x3 на образующий многочлен g(x)=x3+x2+1. В результате кодовый многочлен имеет вид f(x) = x6+x4+x+1;
  • при передаче без ошибок полученный кодовый многочлен f*(x) совпадает с переданным и потому остаток от его деления на образующий равен 0 (это признак правильной передачи);
  • при возникновении ошибок остаток от деления f*(x) на g(x) отличен от 0, что является признаком неправильной передачи. В примере видно, что таким образом обнаруживаются не только однократная ошибка в разряде 3, но и последовательность из трех ошибок в разрядах 1-3.

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

11.2 Потоковые (сверточные) коды

Общая характеристика
В отличие от блоковых кодов, которые мы рассматривали выше, потоковые помехозащитные коды предполагают вставку контрольных разрядов непосредственно в поток информационных — рис.11.4:
  • такой подход позволяет выявлять и исправлять ошибки, не дождаясь окончания передачи блока данных. Потому его широко используют в случаях, когда исправления должны быть максимально оперативными — например, в мобильной телефонии;
  • платой за такую возможность является значительный рост избыточности. Если, например, в коде CRC избыточность может составлять менее одного процента (для g16 это два контрольных байта на блок из нескольких сотен байтов данных), то для потоковых кодов она может достигать 50% и даже выше;
  • принципиальная слабость таких кодов состоит в неумении справляться с длинными “пачками” ошибок, которые могут появляться при передаче. Решением здесь является использование двухуровневой “каскадной” схемы кодирования, которую мы рассмотрим в дальнейшем. Такая схема сочетает достоинства блоковых и потоковых кодов;
  • математический аппарат, как и в случае циклического кода, основывается на операциях с многочленами. Входной последовательности ставится в соответствие многочлен (полином) А(X). Структура кодера определяется образующим многочленом G(Х). Выходной последовательности отвечает многочлен B(X), который получается в результате операции «свертки» многочленов А(X) и G(Х), поэтому такие коды часто называют “сверточными”.

Простой потоковый код Финка-Хегельбергера
Мы познакомимся с реализацией потокового кодирования на примере просто кода, предложенный советским инженером и ученым Финком и впоследствие независимо “переоткрытый” американцем Хегельбергером. Помимо того, что этот код стал первым в данном классе, при его рассмотрении нам не понадобится сложный математический аппарат (рис.11.5):
  • в данном коде контрольные разряды b(i) (на рисунке показаны красным цветом) чередуются с информационными a(i). В простейшем случае при кодировании контрольные разряды вычислются как b(i) = a(i) + a(i+1) (сложение по mod2). При декодировании они рассчитываются снова b(i)*=a(i)* + a(i+1)* и сравниваются с полученными в результате передачи;
  • на рис.11.5а ошибка обнаруживается, если полученное при передаче значение контрольного разряда не совпадает с расчетным. При этом учитывается закономерность: если искаженным оказался информационный разряд а(i), то несовпадение проявится для двух “обрамляющих” его контрольных разрядах; если же при передаче был искажен контрольный разряд, то несовпадение будет только в нем. Это позволяют гарантированно исправлять одиночные ошибки, однако уже при появлении пары ошибок (в информационном и соседнем контрольном разрядах) этот вариант кода не может с ними справиться;
  • возможность исправления коротких пачек ошибок дает модификация кода, которая предусматривает интервал между информационными разрядами, участвующими в определении контрольных: b(i) = a(i-s) + a(i+1+s), где s=1, 2,... При s=1 между разрядами, участвующими в контроле будет находиться еще пара “промежуточных”, при s=2 их будет четыре (при s=0 формула выродится в ранее рассмотренный вариант). С увеличением s растет длина «пачки» ошибок, исправляемой кодом;
  • на рис.11.5б показано исправление пачки из трех ошибок (включая 2 информационных разряда) для случая, когда s=1. При этом поскольку в формировании контрольного разряда b(i) должен участвовать не просто предшествующий ему информационный разряд а(i), но и предыдущий по отношению к нему а(i-1), в начале кодирования приходится использовать условное значение a(0) на рисунке показано зеленым цветом.

Возможности современных сверточных кодеров
В современной практике применяются потоковые коды с различным уровнем избыточности и корректирующей способности. Эти характеристики тесно связаны с логической структурой кодеров (рис.11.6):
  • во всех случаях кодеры включают сдвиговые регистры с сумматорами по модулю 2, которые формируют выходную последовательность разрядов. Такие разряды поступают на выход по нескольким каналам, для каждого из которых выделяется время подключения. Преобразование данных по каждому каналу задается соответствующим образующим многочленом Gi(х) (на схеме структура многочлена отображается расположением связей). Основные характеристики кода включают количество входных и выходных разрядов, обрабатываемых схемой за один такт (соотвественно k и n), относительную скорость кодирования R=k/n (она также характеризует величину избыточности), а также значение dmin, которое определяет кратность исправляемых ошибок;
  • на рис. 11.6а и 11.6б показаны схемы кодеров с одним входным и двумя выходными каналами (k=1, n=2, R=1/2). При этом кодер на рис.11.6а, который реализует уже знакомый нам код Финка, является систематическим (здесь информационные разряды поступают на выход неизменными и лишь дополняются контрольными разрядами). Кодер на рис.11.6б несистематический. Здесь информационные разряды также меняют значения с учетом контрольных соотношений. Такой подход позволяет без увеличения избыточности значительно усилить корректирующую способность (значение dmin возрастает с 3 до 5, что позволяет исправлять не только однократные, но и двойные ошибки). Декодирование несистематических кодов требует довольно сложных математических методов и мы не будем его рассмоатривать;
  • на рис. 11.6в и 11.6г отображены схемы с тремя выходными каналами (в каждом такте на выходе формируется три разряда кода). Как видно, это позволяет дополнительно нарастить dmin до 7 (при этом можно исправлять уже трехкратные ошибки). Платой является уменьшение скорости кодирования. Однако, это может быть компенсировано распараллеливанием входного потока (рис.11.6в и 11.6г);
  • в практике применяются стандартизированные варианты сверточных кодов. Так, в мобильной связи в рамках стандарта GSM, применяются кодеры с dmin=7. В системах спутниковой передачи данных используются кодеры с dmin=10. Образующие полиномы для обоих кодов показаны на рис.11.6. Как видно, оба эти кода являются двухканальными (относительная скорость кодирования составляет 1/2) и несистематическими (последнее, как мы уже знаем, позволяет при заданном уровне избыточности получить максимум корректирующей способности).

11.3 Другие направления помехозащитного кодирования

Итеративные коды
В лекции 10 мы познакомились с простейшим матричным кодом, в котором обнаружение и исправление ошибок выполняется за счет контроля четности по строкам и столбцам. Такой код может быть обобщен для случая, когда по строкам и столбцам используются и другие блоковые коды (рис. 11.7).
  • помимо проверки четности здесь могут применяться код Хэмминга или циклический. Подобные матричные (“двумерные”) коды называют также итеративными, поскольку одни и те же информационные разряды здесь обрабатываются последовательно по строкам и столбцам;
  • в общем случае блок информационных разрядов ai,j включает k1 столбцов и k2 строк. Полное количество столбцов и строк с учетом контрольных разрядов bi,j составляет соотвественно n1 и n2. Кодовое расстояние по строке равно d1min, а по столбцу d2min. При этом для строк и столбцов могут использоваться различные способы кодирования (условно код X и код Y);
  • принципиально важно, что минимальное кодовое расстояние для всего блока равно произведению расстояний по строке и столбцу (это доказано математически). В случае простейшего матричного кода с проверкой четности, как мы помним, dmin=2х2=4 (код может исправлять однокрантые ошибки). Если, например, по строке будет применяться код Хэмминга, а по столбцу — проверка четности, то dmin=3х2=6 (исправляются также ошибки кратности 2). А при использовании для каждой из координат кода Хэмминга значение dmin=3х3=9, что позволяет исправлять уже все ошибки кратности до 4;
  • выбор кода для строки и столбца матрицы может определяться не только требованиями к dmin. Например, для ленточных накопителей широко применялся вариант, в котором по столбцам выполнялось циклическое кодирование с полиномом g(x) степени 8 в сочетании с контролем четности по строкам. Этот код, предложенный фирмой IBM, позволяет обнаруживать пачки ошибок, появление которых характерно для дорожек магнитной записи. При этом проверка четности по строке позволяет исправлять ошибки, поскольку одновременный сбой на двух и более дорожках маловероятен;
  • дополнительное увеличение корректирующей способности матричных кодов возможно за счет использования «третьего измерения», когда в единый блок объединяется пакет из нескольких матриц. На рис.11.7б показано простейшее подобное решение, когда N матриц содержат информационные разряды и биты контроля четности по строкам (ось Y) и столбцам (ось X). Дополнительная матрица N+1 включает только контрольные биты, значения которых поддерживают контроль четности по оси Z. Разумеется, такой подход может быть обобщен на случай использования различных кодов по каждой из координат. Более того, теоретически могут быть введены и дополнительные координаты. При этом по-прежнему действует правило, когда минимальное кодовое произведение для всего блока кода определяется как произведение dmin по всем его координатам.

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

БЧХ-коды и коды Рида-Соломона
Рассмотренные выше коды ориентированы на конкретные частные результаты: код Хэмминга исправляет однократные ошибки, а циклический — обнаруживает пачки ошибок с заданным ограничением по их длине. Более общий подход — исправление ошибок любой заданной кратности — обеспечивают коды, созданные по методу Боуза, Чоудхури и Хоквингема (так называемые БЧХ-коды). К данному классу относится также популярный код Рида-Соломона, для которого вместо двоичных элементов могут использоваться например 16-ричные цифры. Эти коды получили ширкое практическое применение. Однако их математический аппарат сложен, поэтому мы рассмотрим их лишь на уровне принципов (рис.11.8):
  • коды БЧХ являются подклассом циклических кодов и отсюда их свойства определяются образующим полиномом g(x). При этом сам такой полином строится специальным способом — исходя из заданного dmin (с учетом кратности исправляемых ошибок s) и длины кодового слова n. Такая длина должна отвечать условию n = 2m-1, где m – целое число. Свойства кода определяются тройкой значений (n, k, dmin). Например, обозначение (15, 7, 5) соответствует коду с длиной блока 15 разрядов, из которых 7 информационные, при этом его минимальное кодовое расстояние 5 позволяет исправлять все ошибки с кратностью s равной 1 и 2. Популярен код (255, 231, 7), который используют для обнаружения ошибок с кратностью до 6 включительно;
  • процедура построения g(x) достаточно громозка. Здесь лишь обозначим, что образующий многочлен строится исходя из заданных значений s, n на базе набора неприводимых многочленов fi(x), которые выбираются из справочных таблиц. Например, для упомянутого кода (15, 7, 5) образующий многочлен получается как g(x)=f1(x) f2(x) = (x4+x+1) (x4+x3+x2+x+1)= x8+x7+x6+x4+1;
  • кодирование по заданному g(x) может выполняться по той-же процедуре, что и для любого циклического кода: «хвостовик» блока строится по многочлену r(x) – остатку от деления исходного кодового многочлена f(x) на образующий g(x). Декодирование также начинается с вычисления остатка полученного в результате передачи многочлена f*(x) на образующий. Однако в дальнейшем для выяснения расположения всех ошибок приходится использовать достаточно сложные процедуры;
  • важным частным случаем БЧХ-кодов является недвоичный код Рида-Соломона (РС). Здесь вместо двоичной переменной, значение которой соотвествует одному биту, могут применяться переменные значительно большей размерности. Например, используются коды с 16-ричной переменной, значение которой кодируется полубайтом. Популярны коды с 256-ричным основанием (значение представляется байтом). При том, что все процедуры для РС-кодов отвечают правилам БЧХ-кодов, их корректирующая способность значительно выше. Такие коды используются, например для восстановления данных, постардавших из-за царапин на оптических дисках.

Каскадные коды
Каскадные коды используются для надежной передачи сообщений в сложных условиях. Примером может быть передача речи в мобильной связи, где относительно низкая надежность радиоканала сочетается с требованием непрерывности принимаемого потока данных. Использование каскадного кодирования предусмотрено, в частности, стандартом GSM. Идея этого способа состоит в том, чтобы система кодирования включала три уровня (рис.11.9):
  • на “нижнем” уровне схемы кодирования (внутренний контур) поток разрядов обрабатывается потоковым (сверточным) кодом с исправлением более часто встречающихся одиночных и двойных ошибок;
  • на "верхнем" уровне (внешний контур) за счет использования блочного кода устраняются относительно редко встречающиеся длинные пачки ошибок. Во внешнем контуре используется мощный блочный код. В частности, здесь применяется код Рида-Соломона (RS), элементами которого могут являться байты;
  • дополнительный промежуточный уровень схемы обеспечивает "дробление" пачек ошибок, чтобы повысить эффективность работы внутреннего контура. Такое дробление может быть достигнуто относительно простым способом, который принято называть "перемежением";
  • простейший способ перемежения - «блоковый» (рис.11.9). Здесь исходная последовательность записывается после кодирования по столбцам, а выдается для передачи по строкам. После восстановления соседние искаженные разряды, образующие в канале «пачку» ошибок, оказываются разнесенными в разные строки матрицы. В примере на рис.11.9 длинная пачка ошибок в 6 разрядов разбивается на 4 коротких фрагмента по 1-2 ошибки, которые могут быть устранены потоковым кодом.

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

11.4 Обзор направлений классификации и применения

Классификация помехозащитных кодов
Подведем итоги рассмотрения помехозащитных кодов, их кратким обзором. Приведенная на рис.11.10 классификация позволит нам не только упорядочить уже полученные представления, но и несколько их расширить:
  • направления классификации а), б) и в) нам знакомы. По способу введения избыточности коды подразделяются на блоковые и потоковые (непрерывные).
    Для блоковых кодов используются структуры, где информационные и контрольные разряды разделены или не разделяются. Также длины блоков кода могут быть равномерными (постоянными) или неравномерными. Эти признаки характерны для всех рассмотренных выше кодов;
  • г) по используемому математическому аппарату выделяются линейные коды (для которых применяются только операции по модулю 2), а также нелинейные (для них могут применяться и другие математические операции). В качестве примеров нелинейных кодов используем коды «равного веса» с одинаковым количеством 1 в блоке (ошибка обнаруживается, если принятое число 1 отличается от заданного), а также код Бергера, где количество 1 кодируется в хвостовике (такой способ применяется в «асимметричных» каналах, где ошибки выражаются только в изменении 1 на 0);
  • д) по количеству уровней кодирования выделяются одноуровневые коды (к ним относится большинство нами изученных), а также многоуровневые — в том числе итеративные и каскадные. Как мы уже знаем, увеличение количества уровней кодирования значительно повышает корректирующую способность, однако дается ценой повышения избыточности и скорости. На практике в большинстве случаев используются коды с количеством уровней не больше двух;
  • е) по уровню оптимальности (в смысле близости к теоретической границе Шеннона) выделяются обычные (сюда относятся все рассмотренные нами выше коды) и квазиоптимальные. В последнюю категорию попадают, в частности, так называемые «турбо-коды» коды LDPC с «низкой плотностью проверок на четность”. Первые максимально приспособлены к высокой вероятности ошибок и позволяют использовать длинные блоки данных. Вторые лучше работают на более “чистых” каналах. Квазиоптимальные коды были созданы относительно недавно и отличаются высокой сложностью, но сейчас активно применяются в мобильной и спутниковой связи.

Направления применения
В завершении еще раз систематизируем представления о сферах практического использования помехозащитных кодов (рис.11.11):
  • блоковые коды с обнаружением ошибок широко применяются как для обеспечения передачи в пространстве (компьютерные сети), так и во времени (хранение информации на внешних носителях). При этом, поскольку в обоих случаях возможно хранение копий передаваемых сообщений или их блоков, для исправления ошибок применяется метод перезапроса. Наиболее широко применяются циклические CRC-коды. Находят применение также коды БЧХ и Рида-Соломона. Менее распространены итеративные коды;
  • блоковые коды с исправлением ошибок используются в серверной оперативной памяти, где невозможно хранение копий данных, а следовательно, функция исправления ошибок полностью ложится на помехозащитный кодов. С этой функцией справлется код Хэмминга;
  • потоковые и каскадные коды применяются в системах мобильной и спутниковой связи. Они обеспечивают исправление ошибок без значительных задержек, связанных с ожиданием полной передачи блоков. Наиболее современными и надежными решениями является использование квазиоптимальных турбо-кодов и кодов LDPC.

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







О дисциплине ТИК
Почему «Теория информации и кодирования» - одна из самых интересных дисциплин, которые изучают будущие системщики и защитники информации?

В ней сочетаются золотая классика и самая актуальная современность computer-science.

продолжение
О сайте
Здесь вы найдете материалы, которые помогут в изучении дисциплины “Теория информации и кодирования” (ТИК) в том виде, как она преподается на кафедре ЭВМ ДИИТа.

На сайте размещены методические материалы:
  • электронный конспект лекций;
  • методическое обеспечение к лабораторным работам;
  • полезные ссылки.

продолжение
© 2008-2013 • Теория информации и кодирования
UP