2.6. Постоянный симметричный канал. Регулярное кодирование

Наибольшее распространение среди регулярных кодов получили систематические коды, вопросы построения которых рассматриваются в алгебраической теории кодирования, пользующейся аппаратом современной алгебры [11, 12, 43].

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

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

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

                           (2.49)

Корректирующие символы формируются с помощью линейных операций, определенных над конечным полем и производимых над информационными символами. В частном случае, когда  — простое число, эти операции совпадают с операциями сравнении по модулю  [17]. Напомним, что целые числа  и  называются сравнимыми по модулю  [записывается,], если оба эти числа при делении на  дают одинаковый остаток. Так, например,  или . Дли формирования корректирующих символов производится сложение по модулю  определенных информационных символов (представленных числами от  до ). Это значит, что произведя арифметическое сложение указанных чисел, сумму заменяют наименьшим целым неотрицательным числом, сравнимым с этой суммой по модулю  (или «наименьшим вычетом по модулю »). Так, например,

и т.д.

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

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

                              (2.50)

где сложения  производятся по  модулю 2. Так, например, если информационными символами являются  1001, то корректирующими должны быть . В таком коде . В этом легко убедиться, если заметить, что замена значения одного из информационных символов на противоположное влечет за собой замену значений по меньшей мере двух корректирующих символов, а замена значении каких-либо двух из информационных символов неминуемо приводит к замене значения по крайней мере одного корректирующего символа. Поэтому любые две допустимые [т. е. удовлетворяющие уравнениям (2.50)] кодовые комбинации отличаются друг от друга не менее чем в трех разрядах. Отсюда следует, что, используя такой код, можно всегда обнаруживать ошибку, если ошибочно принято не более двух символов в комбинации, либо исправлять ошибку, если ошибочно принят один символ.

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

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

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

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

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

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

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

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

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

В последние годы особое внимание привлекает разновидность систематических кодов, называемых циклическими. Они отличаются тем свойством, что всякая циклическая перестановка символов разрешенной кодовой комбинации приводит также к разрешенной комбинации. Эта особенность, а также некоторые алгебраические свойства циклических кодов позволяют существенно упростить схемы кодирования и декодирования [II, 14, 18]. Для некоторых циклических кодов возможна сравнительно простая (хотя и не всегда оптимальная) процедура декодирования, называемая мажоритарным   или  пороговым декодированием [13,   19].

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

Введение циклических кодов сделало возможным построение кодеров и декодеров для  порядка нескольких десятков при исправлении ошибок и порядка сотен при обнаружении ошибок. Такие коды с различной избыточностью позволяют обеспечить довольно высокую верность приема в реальных каналах. Тем не менее в ряде случаев желательно применять еще более длинные коды с возможно более простым устройством декодера. Поэтому не прекращаются изыскания новых методов построения кодов. Здесь следует упомянуть о работе Р. Галлагера [20], предложившего систематический код, построение проверочной матрицы которого содержит на одном из этапов случайный выбор. Поэтому такой код нельзя считать полностью регулярным. Благодаря тому, что строки и столбцы проверочной матрицы содержат значительно меньше единиц чем нулей, этот код допускает относительно простую процедуру декодирования.

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

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

В качестве примера опишем один из рекуррентных кодов, называемый цепным (14, 21] и отличающийся предельно простыми методами кодирования и декодирования. В частности, он допускает мажоритарное декодирование.

Как уже указывалось, в этом коде последовательность кодовых символов не разделяется на отдельные кодовые комбинации. В поток информационных символов включаются корректирующие символы, так что между каждыми двумя информационными символами помещается один корректирующий. Обозначая по-прежнему информационные символы через , а корректирующие через получаем такую последовательность символов:

Информационные символы определяются передаваемым сообщением, а корректирующие формируются по следующему правилу:

                            (2.51)

где  — произвольное целое число, называемое шагом кода.

Очевидно, что при ошибочном приеме некоторого корректирующего символа  соотношение (2.51)  в принятой последовательности не будет выполнено для .

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

Очевидно, что избыточность такого кода равна 1/2. Он позволяет исправлять все ошибочно принятые символы, если они возникают достаточно редко. Так, если , он обеспечивает правильное декодирование, когда между двумя ошибочно принятыми символами имеется не менее трех (а в некоторых случаях двух) правильно принятых символов (при этом учитываются как информационные, так и корректирующие символы). О факторах, обусловливающих выбор шага , будет сказано в § 2.8.