Помехоустойчивое кодирование (ч.3) (Материалы к семинарам по помехоустойчивому кодированию)

Пример 4. Рассмотрим процедуру кодирования циклического кода (7, 3). Его производящий полином g(x) = x³ + x² + 1, что соответствует комбинации 1101. Схема кодера представляет собой сдвиговый регистр с обратной связью, выполняющей сложение по модулю 2. Включение обратных связей зависит от производящего полинома. Номера ячеек регистра, включенных в обратную связь, соответствуют номерам ненулевых коэффициентов производящего полинома. В регистр записывается информационное слово. Умножение информационного полинома (слова) на производящий полином происходит при пошаговом сдвиге регистра, когда на каждом шаге в освободившийся старший разряд записывается символ, вычисленный обратной связью. После n = 7 шагов из регистра выходит кодовое слово.

С реди циклических кодов существуют такие, для которых возможна упрощенная процедура декодирования. Это – циклические коды, допускающие мажоритарное декодирование. Суть мажоритарного декодирования заключается в следующем: каждый очередной декодированный символ принимает то логическое значение, которое имеют большинство из вычисленных проверочных уравнений. Например, если большинство проверок имеют значение «1», то и очередной символ принимает значение «1». В случае, если количество проверок четное и половина из них имеют значение «1», а другая половина – значение «0», то декодер выносит решение о том, что кодовом слове обнаружена ошибка.

Пример 5. Рассмотренный в примере 4 циклический код (7, 3) допускает мажоритарное декодирование. Система контрольных проверок имеет вид:

a₀ = a₀

a₁  a₅ = a₀

a₂  a₃ = a₀

a₄  a₆ = a₀

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

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

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

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

На рис. 11 изображены два кодера сверточного кода – кодер систематического (рис. 11, а) и несистематического (рис. 11, б) сверточного кода. Каждый из них состоит из сдвигающего регистра, имеющего b = 3 ячеек, и каждый такт работы кодера в этот регистр приходят k = 1 информационных символов. Каждый такт работы ком­мутатор (ком.) опрашивает n = 2 выхода кодера, формируя n = 2 вы­ходных кодовых символа. В общем случае целые числа k, b, n, могут быть любые, с очевидными ограничениями – условиями и b ┴ k. Последнее условие означает, что длина регистра b должна делиться нацело на число приходящих за один такт работы кодера информацион­ных символов k. Параметры R = k / n, R_и = 1 / R = n / k называются соответст­венно скорость кода и избыточность кода, они полностью аналогичны таким же понятиям в блочном кодировании. Параметр  = (bn) / k называется длиной кодовых ограничений сверточного кода и играет роль, аналогичную блоковой длине блочного кода. Если вычислить расстояние Хэмминга между последовательностями сверточного кода на длине кодовых ограничений, то минимальное из этих расстояний будет называться минимальным свободным расстоянием сверточного кода. Оно играет ту же роль, что и кодовое расстояние d блокового кода.

Из рис. 11, а можно сделать вывод, что в систематическом сверточном коде выходные кодовые символы содержат без изменения вход­ные информационные символы, их породившие. Для кодера несистемати­ческого сверточного кода этого нет, в чем и состоит отличие этих кодеров.

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

Задать сверточный код можно посредством его производящих многочленов. Например, для кодера рис. 11, б производящие многочлены G₁(х) и G₂(х), описывающие связи на первый и второй сумматоры по модулю два, будут следующие:

Здесь x – фиктивная (символическая) переменная, как и для блоковых кодов.

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

Рассмотрим её на примере кода Хэмминга (7, 4), этот код обладает d = 3, т. е. способен исправить любую однократную ошибку. Его система уравнений имеет вид:

а₄  а₅  а₆  а₇ = 0

а₂  а₃  а₆  а₇ = 0

а₁  а₃  а₅  а₇ = 0

где  - знак сложения по модулю 2, символы а₃, а₅, а₆, а₇ являются информационными, а символы а₁, а₂, а₄ – проверочными. Анализ синдрома позволяет исправлять ошибки. Если синдром нулевой, то ошибка не обнаружена, а если синдром ненулевой, то его значение в двоичной записи является номером неверно принятого символа.

Так, если синдром принятого слова 011, что в двоичной записи означает число 3, значит ошибочно принят символ а₃. Надо изменить значение этого символа на противоположное, и ошибка будет исправлена.

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