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

Все помехоустойчивые коды делятся на блоковые и непрерывные (их называют также цепные или рекуррентные). При блоковом коди­ровании данные передаются отдельными блоками (словами, кодовыми комбинациями). При этом поступающие в кодер символы, разбиваются на блоки по k информационных символов. В кодере этот блок информационных символов преобразует­ся в блок из кодовых символов, где п называется дли­ной кода. Добавленные при кодировании r = n – k символов являются проверочными. Такой блоковый код принято обозначать как (n, k) – код. Величину R = k / n называют скоростью кода, а величину, обратную скорости, R_и = n / k называют избыточностью кода.

Проверочные символы являются избыточными, они необходимы для обнаружения и (или) исправления ошибок, возникших при передаче. Существуют безызбыточные (примитивные) коды. У этих кодов проверочных символов нет (n = k), поэтому у них самая высокая скорость кода R = 1, но они не способны обнаруживать ошибки.

Ошибки при передаче кодового слова возникают потому, что некоторые из переданных символов могут быть приняты неверно. Принцип обнаружения ошибок заключается в следующем. Если блоковый (n, k) – код имеет основание (количество символов в используемом алфавите) q, то возможно Q = qⁿ различных кодовых слов. Для передачи же используются только Q_р = q^k кодовых слов, которые называются разрешенными. Остальные Q_з = Q – Q_р слов априорно для передачи не используются и называются запрещенными.

В дальнейшем будут рассматриваться только двоичные коды, у которых алфавит состоит из двух символов 0 и 1, т. е. с основанием q = 2.

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

Пример 1. Требуется передача сообщения о наступлении одного из четырех возможных событий A, B, C, D. Эти события представлены информационными словами 00, 01, 10, 11 соответственно. При передаче этих слов безызбыточным кодом все возможные комбинации являются разрешенными. Поэтому достаточно искажения хотя бы одного символа, чтобы сообщение было принято неверно. Так, если передавалось сообщение A в виде кодового слова 00, а принято было слово 01, то декодер, найдя в таблице такое разрешенное слово, вынесет решение о приеме сообщения B.

Если к вышеперечисленным информационным словам добавить по одному избыточному символу, поставив в соответствие разрешенные слова 000, 011, 101, 110, то искажение одного символа в переданном слове можно обнаружить. Так, если передавалось сообщение A в виде кодового слова 000, а принято было слово 001, то декодер, не найдя в таблице такого разрешенного слова, объявит принятое слово запрещенным и сообщит об обнаружении ошибки в слове. Однако если было принято слово 011, то декодер вынесет решение о приеме сообщения B.

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

Пример 2. Для передачи используются три разрешенных слова 000, 100, 111. Расстояние между первым и вторым словами равно 1, между вторым и третьим словами – 2, а между первым и вторым – 3. Кодовое расстояние для данного кода d = 1.

Очевидно, что у безызбыточного кода d = 1, так как между любой парой его слов расстояние равно единице. Этот код не позволяет обнаруживать ошибки. Приведенный в примере 1 избыточный код (он называется кодом с проверкой на четность) имеет d = 2. Он позволяет гарантировано обнаружить однократную ошибку.

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

Можно заметить, что максимальная кратность гарантировано обнаруживаемой ошибки t_о = d – 1. Действительно, при возникновении необнаруженной ошибки одно разрешенное слово должно превратиться в другое разрешенное слово. А для этого надо, чтобы кратность возникшей ошибки была не менее d, поскольку все разрешенные слова по определению кодового расстояния различаются не менее, чем на d символов. Если же принятое кодовое слово хотя бы на один символ отличается от разрешенных кодовых слов, то будет зафиксировано появление ошибки.

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

Пример 3. Для передачи используется два разрешенных кодовых слова 000 и 111. Было принято слово 001, на беглый взгляд оно больше похоже на 000, чем на 111. Действительно, слово 001 от первого разрешенного слова отличается на один символ, а от второго на два. Так как однократная ошибка вероятнее двукратной, то скорее всего было передано первое слово и в нем исказился один символ. Декодер принимает решение по минимуму расстояния Хэмминга и объявляет принятым разрешенное слово 000.

В
рассмотренном примере код имеет d = 3, он позволяет гарантировано исправлять однократную ошибку. Можно заметить, что максимальная кратность гарантировано исправляемой ошибки :

где [x] –целая часть числа x.

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

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

Для сохранения различимости кодовых комбинаций при стирании не более s знаков кодовое расстояние d должно удовлетворять условию:

Для того, чтобы код мог одновременно исправлять t ошибок и восстанавливать s стертых символов кодовое расстояние должно быть:

Преимущество кодов со стираниями очевидно: например, при d = 3 такой код может как и обычный исправить одиночную ошибку, но может восстановить два стертых символа.

Описанный выше метод кодирования и декодирования, основанный на запоминании таблицы разрешенных слов, называется универсальным, поскольку годится для всех блочных кодов. Однако этот метод практически не применяется из-за сложности реализации и низкого быстродействия. Если длина информационного слова достаточно велика, то требуется большой объем памяти для хранения всех разрешенных слов. Кроме того, сравнение принятого слова со всей таблицей может продолжаться очень долго, что недопустимо при работе в режиме реального времени. Поэтому созданы другие методы кодирования и декодирования блочных кодов, в которых используется не поиск разрешенных слов, а математические операции над информационными и проверочными символами.

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

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

Если в кодере используются лишь линейные операции над поступающими информационными символами, то код называется линейным. Принцип кодирования и декодирования линейного кода заключается в системе линейных уравнений, в которую входят информационные и проверочные символы. Для каждого кода эта система своя. Рассмотрим её на примере кода (7, 4), имеющего d = 3.

a₁  а₂  а₃  а₅ = 0

а₂  а₃  а₄  а₆ = 0

а₁  а₂  а₄  а₇ = 0

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

Проверочные символы вычисляются с помощью про­изводящей (порождающей) матрицы. Производящая матрица G – это таблица, у которой k строк и n столбцов, в которой записаны k ли­нейно независимых разрешенных комбинаций данного кода. По ней можно построить все остальные разрешенные кодовые комбинации, складывая поразрядно по модулю 2 строки производящей матрицы во всех возможных сочетаниях. В памяти кодера достаточно иметь производящую матрицу. С помощью набора сумматоров можно получить любую разрешенную кодовую комбинацию.

Производящую матрицу принято представлять в каноническом виде. Для рассматриваемого кода она будет:

Где левая часть матрицы - единичная матрица, соответствующая информационным символам, а правая часть матрицы соответствует проверочным символам. Схема кодирования строится на основе производящей матрицы. Кодер состоит из k-элементного регистра для информационного слова и n – k сумматоров по модулю 2. Элементы правой части производящей матрицы p_ij отвечают за вычисление проверочных символов. Они показывают связь i-ой ячейки регистра с j-м сумматором. Если p_ij = 1, то связь есть, если p_ij = 0 , то связи нет.

Д
ля декодирования требуется проверочная матрица H, содержащая n – k строк и n столбцов. В каждой строке этой матрицы единицы находятся в тех разрядах, которые входят в соответствующее проверочное уравнение. Для рассмотренного кода Хэмминга (7, 4) проверочная матрица будет иметь вид:

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