10. Итеративные, сверточные и каскадные коды
Курс “Теория информации и кодирования”

Матричные итеративные коды
Особенности потоковых (сверточных) кодов
Характеристики сверточных кодов
Каскадные коды

10.1 Матричные итеративные коды

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

Здесь блок информационных разрядов 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, позволяет обнаруживать пачки ошибок, появление которых характерно для дорожек магнитной записи. При этом проверка четности по строке позволяет исправлять ошибки, поскольку одновременный сбой на двух и более дорожках маловероятен.

Дополнительное увеличение корректирующей способности матричных кодов возможно за счет использования «третьего измерения», когда в единый блок объединяется пакет из нескольких матриц. На рисунке показано простейшее подобное решение, когда N матриц содержат информационные разряды и биты контроля четности по строкам (ось Y) и столбцам (ось X). Дополнительная матрица N+1 включает только контрольные биты, значения которых поддерживают контроль четности по оси Z. Разумеется, такой подход может быть обобщен на случай использования различных кодов по каждой из координат. Более того, теоретически могут быть введены и дополнительные координаты. При этом по-прежнему действует правило, когда минимальное кодовое произведение для всего блока кода определяется как произведение dmin по всем его координатам.

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

Контрольные вопросы
1) Как устроены матричные итеративные коды. Какими параметрами они характеризуются.
2) Как определяется минимальное кодовое расстояние для матричного кода. Приведите примеры для случаев использования различных кодов по строке и столбцу.
3) Поясните принцип действия трехмерного итеративного кода.
4) В чем состоят преимущества и недостатки итеративных кодов.



10.2 Особенности потоковых (сверточных) кодов

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

Потоковые коды часто называют также “сверточными”. Это связано с применением в их математическом аппарате операции свертки. В дальнейшем мы также чаще будем использовать данный термин. Как мы уже знаем благодаря рассмотрению простого варианта кода Финка-Хейдебергера в лекции 8, сверточные коды позволяют оперативно исправлять одиночные ошибки в потоке данных.

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

На следующих двух рисунках показано исправление однократной ошибки и пачки из трех ошибок (включая 2 информационных разряда) при s=1.











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

Лучше понять функционирование сверточных кодеров при значениях s=0 и s=1 позволяют их структуры, показанные на рисунке. Структура устройства кодирования включает:
  • сдвиговый регистр, на котором при участии разрядов a(i) формируются контрольные разряды b(i);
  • сумматоры по модулю 2 для формирования контрольных разрядов;
  • переключатель, поочередно подающий на выход информационные и контрольные разряды.


Математически сверточное кодирование задается перемножением многочленов (рисунок):
  • первый многочлен А(х) отвечает входной последовательности;
  • второй многочлен Gj(x) отвечает структуре j-го канала кодера;
  • произведение для j-го канала кодирования вычисляется операцией свертки (отсюда «сверточный» код): Bj(x) = A(x) Gj(x)
.
Собственно вычисление свертки выполняется согласно показанной на рисунке формуле. Именно такую процедуру реализуют схемы сверточных кодеров, показанные на рисунке выше:
  • канал кодирования, которому отвечает один из образующих многочленов, соответствует одному выходу схемы кодирования (например, на рис a и б их два);
  • в составе многочлена G(X) содержатся те элементы, которые отвечают связям через сумматоры по модулю 2 (например, для рис а и б G2(X) = x2+1, поскольку связь с выходом через сумматор существует только для первого и третьего триггеров);
  • младшей (нулевой) степени многочлена отвечает первый от входа элемент (например, на рис а G1(X)=x0=1).


Контрольные вопросы
1) В чем состоит основная особенность сверточных кодов по сравнению с блоковыми. Какова область их применения.
2) Используя приведенный выше рисунок, поясните исправление коротких пачек ошибок с помощью сверточного кода.
3) Поясните действие простого сверточного кода на примере схем.
4) Охарактеризуйте математический аппарат сверточных кодов. Поясните связь структуры схем и соответствующих уравнений кода.


10.3 Характеристики сверточных кодов

Набор параметров, характеризующий сверточные коды включает:
  • число информационных разрядов за такт, поступающих на вход кодера k (на рисунке k=1);
  • число соответствующих кодовых знаков за такт на выходе кодера n (в нашем случае n=2);
  • скорость кодирования R=k/n и избыточность кодирования D=1-k/n (R=D=1/2);
  • число элементов памяти регистра кодирования m (соответственно 2 и 3);
  • память кода (полная длина регистров) l=km (соответственно 2 и 3)
  • кодовая длина блока (количество разрядов с взаимным влиянием) lп=nm= lm/k (соответственно 4 и 6).

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








Для систематического кодера а) исходная позиция и значение информационного разряда не меняется на выходе (информационный разряд поступает непосредственно на выход схемы в первом полутакте). Для не-систематического кодера б) значение информационного разряда на выходе преобразуется. Как мы увидим в дальнейшем, последний подход позволяет дополнительно увеличить корректирующую способность кода. В обоих случаях набор перечисленных выше параметров кодеров совпадает: k=1, n=2, R=D=1/2, m=3, l=3, lп=6.

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

В случае a) корректирующая способность кода увеличивается за счет использования двух контрольных разрядов на один информационный (при этом, однако, возрастает избыточность кода и уменьшается скорость кодирования). Параметры кода k=1, n=3, R=1/3, D=2/3, m=3, l=3, lп=9.
В случае б) решается задача повышения скорости кодирования за счет одновременной обработки двух входных потоков. Здесь k=2, n=3, R=2/3, D=1/3, m=2, l=4, lп=6.

Важнейший показатель корректирующей способности сверточных кодов - кратность исправляемых ошибок C. Она определяется исходя из минимального кодового расстояния кода по правилу 2C+1 = dmin. В частности, при dmin=3, 5, 7 значения С = 1, 2 и 3.

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

Для определения dmin используется следующий подход:
  • путем моделирования работы кодера определяется выходная последовательность B(X), которая соответсвует входной вида А(X) = 10000... (все «0» нули после первой «1»);
  • dmin определяется как количество «1» на интервале длиной lп от начала B(X).

На рисунке показаны «тестовые» последовательности B(X) и соответствующие значения dmin для нескольких рассмотренных выше структур кодеров (интервал длиной lп для подсчета количества «1» при определении dmin подчеркнут).

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

В частности, в мобильной связи, где сверточный код является элементом стандарта GSM, применяются стандартизированные кодеры с dmin=7. Образующие полиномы кода:
G1(X)=1+X3+X4, G2(X)=1+X+X3+X4.

В системах спутниковой передачи данных используются кодеры с dmin=10.
Образующие полиномы кода: G1(X)=1+X2+X3+X5+X6, G2(X)=1+X+X2+X3+X6.

Контрольные вопросы
1) Перечислите и поясните основные характеристики сверточных кодов.
2) Поясните особенности систематических и не-систематических сверточных кодов на примере приведенных выше схем. В чем состоят преимущества не-систематических кодов.
3) Поясните подход к оценке корректипующей способности сверточных кодов.
4) Приведите примеры практического использования стандартных сверточных кодов и охарактеризуйте их корректирующую способность.


10.4 Каскадные коды

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

Идея этого способа состоит в том, чтобы система кодирования включала три уровня (рисунок).

На “нижнем” уровне схемы кодирования (внутренний контур) поток разрядов обрабатывается сверточным кодом с исправлением более часто встречающихся одиночных и двойных ошибок.

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

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

Простейший способ перемежения - «блоковый» (рисунок). Здесь исходная последовательность записывается после кодирования по столбцам, а выдается для передачи по строкам. После восстановления соседние искаженные разряды, образующие в канале «пачку» ошибок, оказываются разнесенными в разные строки матрицы. На рисунке рассмотрен пример, когда число строк матрицы N=4, а количество столбцов M=6.

Варианты а) и б) различаются длиной пачки ошибок - соответственно 5 и 8. В первом случае перемежение позволяет преобразовать пачку в набор одиночных ошибок. Во втором ряд ошибок будут двойными, однако сверточный код по-прежнему в состоянии их исправить.

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

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

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

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

Контрольные вопросы
1) Какова область применения каскадных кодов.
2) Охарактеризуйте функции внутреннего и внешнего контуров каскадной схемы.
3) Поясните назначение слоя перемежения и блочный способ его реализации.
4) Каковы направления усовершенствования перемежения. Что такое "турбо-коды"


Литература
10.1 Бородин Л.Ф. Введение в теорию помехоустойчивого кодирования
М.: Советское радио, 1968, 408с.
10.2 Бернард Скляр. Цифровая связь: Теоретические основы и практическое применение. Издательский дом "Вильямс", 2004, 1104 с.
10.3 В.В.Лидовский Теория информации. Учебное пособие. - М.: Компания Спутник+. 2004., 111 с.

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

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

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

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

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