11.5. Сложные систематические коды

1. Систематический ( , ) код.

Представляет собой набор n-разрядных кодовых комбинаций, в которых разрядов (обычно первые) представляют собой результат примитивного кодирования сообщения. Они называются информационными разрядами. Остальные разрядов образуются по определенным правилам из информационных, они называются проверочными (корректирующими) и служат для обнаружения и исправления ошибок. Так, например, код (7,4) – это код, в котором семиэлементная кодовая комбинация содержит 4 информационных символа.

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

Приведем пример построения кода (7,4). Как видно из обозначения, 4 разряда кодовой комбинации заняты информационными символами. Обозначим их , , , . Остальные 3 разряда заняты корректирующими символами, которые обозначим , , . Символы определяются уравнениями:

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

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

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

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

При исправлении ошибок необходимо учитывать, какие из уравнений не удовлетворены, и руководствоваться специальными правилами:

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

2. Если не удовлетворены первые два уравнения, то подлежит исправлению (замене 0 на 1 или 1 на 0) символ , который входит в оба этих уравнения. Если не удовлетворены 1 и 3 уравнения, то исправлению подлежит символ . Если не удовлетворены 2-е и 3-е уравнение, исправлению подлежит символ . Наконец, если все три уравнения не удовлетворены, то исправлению подлежит символ . Если в кодовой комбинации ошибочно приняты два или более символов, то такая комбинация не будет правильно декодирована.

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

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

Для кода ( , ) производящая матрица может быть записана в таком виде:

r

n

– производящая матрица.

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

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

(единичная матрица)

2. Циклические коды (систематический блочный код).

Разрешенные комбинации циклического кода можно вычислить последовательно, применяя две операции: циклическую перестановку и суммирование по модулю 2. Циклическая перестановка менее трудоемкая, и это обстоятельство полезно использовать для упрощения процесса вычислений. Расширим производящий полином кода (7,4) до семи членов, применяя нулевые коэффициенты:

Запишем первую комбинацию: .

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

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

Рассмотрим еще один способ нахождения разрешенных кодовых комбинаций, который широко применяется на практике.

Пусть – информационный полином, наивысшая степень которого (состоит из элементов). Умножим каждый информационный многочлен на выравнивающий полином (в нашем случае ), что соответствует приписыванию справа нулей. Разделим полученный результат на производящий полином , операция деления выполняется по модулю 2.

где – частное от деления, нас не интересует,

– остаток от деления.

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

Пример:

, ,

, .

, .

Разрешенная кодовая комбинация имеет вид:

, .

В приемнике (декодере) принятая кодовая комбинация делится на производящий полином. При нулевом остатке комбинация принята верно, либо содержит необнаруженную ошибку; остаток от деления указывает, что комбинация принята с обнаруженной ошибкой. По виду остатка может быть определен искаженный элемент в информационной части принятой комбинации (формируется так называемый синдром).