3.3.4. Групповые коды с обнаружением и исправлением ошибок

Коды с обобщенными проверками на четность

Все систематические коды являются разделимыми. Их принято иногда называть (n,k)-кодами, где n- общее число разрядов в кодовой комбинации, k- число информационных разрядов. Число контрольных разрядов в кодовой комбинации, следовательно, равно n-k.

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

Наиболее важными и полезными границами для кодового расстояния являются граница Хэмминга, граница Плоткина и граница Варшамова - Гилберта.

Граница Хэмминга, выражаемая обычно следующим образом,

, (3.19)

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

Граница Плоткина также является верхней границей для кодового расстояния при данных n и k и может выражаться следующим образом

. (3.20)

Выражение (3.20) удобно для получения максимально возможного d при заданных n и k, но не очень удобно для получения максимального k при данных d и n, в связи с чем другая форма границы Плоткина выглядит следующим образом

. (3.21)

Граница Хэмминга обычно близка к оптимальной для высокоскоростных кодов (т.е. для больших значений k/n), а граница Плоткина - для низкоскоростных кодов.

Согласно границе Варшамова - Гилберта, выражаемой как

, (3.22)

существует (n,k)-код с кодовым расстоянием, не меньшим d, и с числом проверок на четность, не превышающим n-k. Таким образом, граница Варшамова-Гилберта является границей существования и дает нижнюю оценку для кодового расстояния «наилучшего» кода.

Приведем пример использования этих границ. Предположим, что требуется найти код длиной n=63 с кодовым расстоянием d=5 и наибольшим возможным значением k. Примером такого кода является (63,51)-код БЧХ. Для оценки того, насколько хорошим является этот код, используем границы Хэмминга и Варшамова-Гилберта. Из (3.19) следует, что 20172^n-k , откуда n-k 11. Граница Варшамова-Гилберта (3.22) «утверждает», что 39774>2^n-k , откуда n-k 16. Таким образом, из границы Хэмминга следует, что не существует кодов, обеспечивающих заданные параметры, с n-k<11, а граница Варшамова-Гилберта гарантирует существование таких кодов с n-k16. Отсюда можно сделать вывод, что код (63,51) является «хорошим» и дальнейшие поиски могут привести лишь к незначительному улучшению.

Для кодов с d=3 для определения требуемого числа контрольных разрядов можно найти более простое выражение, воспользовавшись следующими рассуждениями. При передаче кодовой комбинации может быть искажен любой из n разрядов комбинации или комбинация принята без искажений. Следовательно, всего может быть n+1 вариантов исхода. Использование контрольных разрядов должно обеспечить возможность различения всех n+1 вариантов. С помощью n-k разрядов можно описать 2^n-k событий, следовательно, должно выполняться условие или

(3.23)

Рассматриваемые (n,k)-коды называются групповыми. Своим названием они обязаны тому, что множество кодовых комбинаций вместе с нулевой кодовой комбинацией, снабженное операцией посимвольного сложения по модулю два, образуют математическую структуру, называемую группой. Основные свойства группы:

1. замкнутость - т.е. сумма по модулю два двух элементов группы всегда лежит в группе;

2. ассоциативность - т.е. (ab)c=a(bc);

3. наличие единичного элемента - для двоичных кодов это нулевая комбинация;

4. каждый элемент группы обладает обратным, для которого а+(-а)=0, для двоичных кодов каждая кодовая комбинация совпадает со своей обратной.

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

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

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

Пусть кодовая комбинация двоичного группового кода имеет n разрядов: u_nu_n-1u_n-2 . . . u₁. Положим, что среди этих n разрядов символы u_r, u_l, u_s - контрольные. Число проверочных уравнений определяется числом контрольных символов:

(3.24)

В этих уравнениях коэффициенты принимают значения 1 или 0 в зависимости от того, используется или нет соответственно для определения значения i-го контрольного разряда j-й информационный разряд.

С помощью этих уравнений могут быть составлены все N_p=2^k разрешенных или рабочих комбинаций кода путем записи информационных разрядов каждой комбинации и вычисления значений контрольных разрядов по уравнениям (3.24) для каждой комбинации информационных разрядов. Таким образом, тот или иной код может быть задан таблицей информационных кодовых комбинаций и системой проверочных уравнений.

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

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

Пример.3.7. Построить образующую матрицу (7,4)-кода, имеющего следующие проверочные уравнения

Решение. Сначала целесообразно построить полную таблицу кода в соответствии с проверочными уравнениями.

a4	a3	a2	a1	b3	b2	b1
0	0	0	0	0	0	0
0	0	0	1	1	0	1
0	0	1	0	1	1	1
0	0	1	1	0	1	0
0	1	0	0	1	1	0
0	1	0	1	0	1	1
0	1	1	0	0	0	1
0	1	1	1	1	0	0
1	0	0	0	0	1	1
1	0	0	1	1	1	0
1	0	1	0	1	0	0
1	0	1	1	0	0	1
1	1	0	0	1	0	1
1	1	0	1	0	0	0
1	1	1	0	0	1	0
1	1	1	1	1	1	1

Выберем образующие кодовые комбинации (выделены жирным шрифтом) и запишем их в виде образующей матрицы

.

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

1000011

 0100110

0001101

1101000,

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

Анализ вида образующей матрицы приводит к выводу, что она состоит из двух матриц - единичной

и дополняющей .

Обобщая рассмотренный пример на любой систематический групповой блоковый (n,k)-код можно записать для него образующую матрицу

(3.25)

Единичная матрица является образующей для равномерного примитивного кода, поскольку с ее помощью могут быть построены все 2^k-1 ненулевых комбинаций этого кода путем суммирования по модулю два ее строк в различных сочетаниях.

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

1) количество единиц в комбинации должно быть не менее d-1,

2) сумма по модулю два любых двух комбинаций должна содержать не менее d-2 единиц.

Пример.3.8. Построить образующую матрицу систематического кода (7,4) с d=3.

Решение. Начать построение целесообразно с нахождения дополняющей матрицы . В данном случае n=7, k=4, n-k=3, т.е.D_3,4.. Следовательно, надо подобрать трехразрядные комбинации, каждая из которых содержит по d-1=3-1=2 единицы. Поскольку таких комбинаций всего три, а их требуется k=4, то в качестве четвертой выберем, не нарушая первого условия, комбинацию, содержащую три единицы. Тогда дополняющая матрица

и образующая матрица ,(3.26)

из которой может быть найдена система проверочных уравнений

(3.27)

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

В качестве еще одной равноправной формы описания систематического (n,k)-кода служит т.н. проверочная матрица, обозначаемая обычно H_n,n-k. При построении проверочной матрицы к единичной квадратной матрице J_n-k слева приписывают матрицу, содержащую k столбцов и n-k строк, причем каждая ее строка формируется из соответствующего столбца дополняющей матрицы, т.е. приписываемая матрица представляет собой транспонированную дополняющую матрицу

. (3.28)

Пример.3.9. Для кода из примера 3.8- построить проверочную матрицу.

Решение.

. (3.29)

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

(3.30)

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

Из анализа (3.30) видно, что a₁ входит во все три уравнения, а₂ - в первое и второе, а₃ - в первое и третье, а₄ - во второе и третье. Следовательно, искажение любого а_i нарушит вполне определенные уравнения, т.е. сумма по модулю два в них будет рана не нулю, а единице. По тому, какие именно уравнения нарушены, можно определить, в каком разряде произошла ошибка, и восстановить его истинное значение.

Таким образом, результаты проверок дают кодовую комбинацию вида , которую называют контрольной последовательностью или, чаще, синдромом. При считается, что кодовая комбинация принята верно или произошла не обнаруживаемая ошибка. Если , считается, что комбинация принята неверно, т.е. имеет место обнаружение ошибки. Если (n,k)-код используется только для обнаружения ошибок, то в теории кодирования доказывается, что при любой вероятности ошибочного приема кодового символа р1/2 найдется код, для которого вероятность необнаруженной ошибки будет меньше вполне определенного значения . Такие коды называются кодами равномерно обнаруживающими ошибки.

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

,

а принимается

.

При выполнении проверок на приеме в соответствии с системой (3.30) получается

т.е. синдром R=110, нарушены первое и второе уравнения, в которые входит а₂, следовательно, ошибка в разряде а₂ и тогда исправляющий вектор Е=0010000, а исправленная кодовая комбинация

.

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

Обобщая, можно сказать, что при ошибке в разряде а₄ синдром будет 011, при ошибке в разряде а₃ - 101, при ошибке в разряде а₁ - 111.

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

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

Так, кодер (рис. 3.9) для кода из примера 3.8 должен содержать

Рис. 3.9. Кодер систематического кода (7,4)

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

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

Для режима исправления ошибки в составе декодера (рис. 3.10) должны присутствовать следующие функциональные узлы:

- регистр для временного хранения принятой кодовой комбинации;

- устройство вычисления синдрома;

- дешифратор синдрома;

- устройство исправления ошибки;

- регистр для хранения исправленной информационной части комбинации.

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

Рис. 3.10. Декодер систематического кода (7,4)

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

Рис. 3.11. Схема выявления ненулевого синдрома

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

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

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

В связи с этим алгоритм максимального правдоподобия реализуется в виде следующей последовательности действий:

1) принятая кодовая комбинация Y суммируется по модулю два последовательно со всеми кодовыми комбинациями кода X_i , в результате каждого суммирования вычисляются векторы ошибок e_i = Y+X_i;

2) подсчитывается число d_i единиц в каждом из векторов ошибки e_i;

3) та из X_i, для которой d_i минимально, считается переданной кодовой комбинацией.

Для некоторых систематических (n,k)-кодов неравенство (3.23)

превращается в строгое равенство

. (3.31)

Для таких кодов можно записать и, поскольку , то . (n,k)-коды вида называются кодами Хэмминга.

Образующая матрица кода Хэмминга (7,4) приведена ранее (3.26). Образующие матрицы кодов больших размерностей строятся аналогично. Уравнение (3.31) имеет целочисленные решения при k=0,1,4,11,26,57,120, . . , что дает соответствующие коды Хэмминга (3,1), (7,4), (15,11), (31,26), (63,57), (127,120),. . . . Коды Хэмминга относятся к немногим известным совершенным кодам.

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

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

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

Код, у которого сферы радиуса t вокруг каждого кодового слова не пересекаются и все кодовые слова, не лежащие внутри какой-либо из этих сфер, находятся на расстоянии t+1 хотя бы от одного кодового слова, называется квазисовершенным. Квазисовершенные коды встречаются чаще, чем совершенные. Если для заданных n и k существует квазисовершенный и не существует совершенного кода, то для этих n и k не существует кода с большим, чем у квазисовершенного, кодовым расстоянием.

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

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

Укорочение кода состоит в уменьшении длины кодовых комбинаций путем удаления лишних информационных разрядов. Если код задан порождающей матрицей, то это приводит к уменьшению обоих размеров порождающей матрицы на одно и то же число. Так, например, как упоминалось ранее, коды Хэмминга с d=3 могут быть построены с вполне определенным сочетанием n и k. Как поступить в том случае, если требуется код Хэмминга с d=3, для передачи информации достаточно k=8, а на длину кодовой комбинации наложено ограничение n<15. Для выполнения этих требований можно выбрать код Хэмминга (15,11) и прибегнуть к его укорочению. Укорочение производится за счет удаления требуемого числа лишних информационных разрядов, обычно это первые слева разряды. В образующей матрице кода (15,11) полагаются равными нулю столько столбцов слева, сколько разрядов надо удалить, после чего вычеркиваются нулевые столбцы и строки с полностью нулевыми строками единичной матрицы. Относительно проверочной матрицы операция укорочения выражается в удалении соответствующего количества первых слева столбцов, так как число строк проверочной матрицы, равное числу контрольных разрядов, остается неизменным при укорочении. Для приведенных значений k=8 и n<15 из кода (15,11) нужно удалить три лишних информационных разряда, в результате чего получится укороченный код (12,8), который также называется кодом Хэмминга.

Расширение кода состоит в увеличении длины кодовых комбинаций за счет введения новых контрольных разрядов, что приводит к увеличению большего размера порождающей матрицы, и, естественно, к увеличению d, т.е. повышению корректирующих способностей. В качестве примера можно привести расширенный код Хэмминга (8,4) с d=4. Этот код образуется путем добавления к каждой кодовой комбинации кода Хэмминга (7,4) еще одного контрольного разряда, значение которого определяется как сумма по модулю два всех остальных разрядов кодовой комбинации, т.е. общая проверка на четность всей кодовой комбинации. При декодировании комбинаций этого кода возможны следующие варианты: 1) ошибок нет. Это показывает как общая проверка на четность, так и равенство нулю синдрома. 2) одиночная ошибка. Общая проверка на четность указывает на наличие ошибки, а по синдрому находится номер искаженного разряда и ошибка в нем исправляется. Нулевой синдром в этом случае указывает на наличие ошибки в дополнительном разряде, т.о. имеет место режим исправления ошибок. 3) две ошибки. Общая проверка на четность указывает на отсутствие ошибок, ненулевой синдром – на их наличие, причем значение синдрома указывает на разряд, в котором якобы произошла ошибка, однако в этом случае ее не следует исправлять, а лишь констатировать наличие двух ошибок, т.о. реализуется режим обнаружения ошибок.

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

Контрольные

вопросы к

лекции 14

14-1. Почему коды с обобщенными проверками на четность называются групповыми?

14-2. Что связывают проверочные уравнения группового кода?

14-3. Чем определяется количество проверочных уравнений того или иного группового кода?

14-4. Какие кодовые комбинации выбираются в качестве базисных при построении образующей матрицы группового кода?

14-5. Как строится образующая матрица (n,k)-кода?

14-6. Как с помощью образующей матрицы можно найти любую разрешенную комбинацию (n,k)-кода?

14-7. Из каких подматриц состоит образующая матрица (n,k)-кода?

14-8. Как может быть построена образующая матрица (n,k)-кода, если не задана система проверочных уравнений?

14-9. Как может быть построена проверочная матрица (n,k)-кода?

14-10. Что называется синдромом ошибки?

14-11. Какое значение синдрома указывает на наличие ошибки в принятой кодовой комбинации?

14-12. Что называется исправляющим вектором?

14-13. Из каких функциональных узлов состоит кодер (n,k)-кода?

14-14. Чем определяется количество сумматоров по модулю два в составе кодера (n,k)-кода?

14-15. Чем определяется количество входов у сумматоров по модулю два в составе кодера (n,k)-кода?

14-16. Из каких функциональных узлов состоит синдромный декодер (n,k)-кода?

14-17. Что представляет собой устройство вычисления синдрома в составе синдромного декодера (n,k)-кода?

14-18. Чем определяется количество входов у сумматоров по модулю два в составе устройства вычисления синдрома?

14-19. Какую функцию реализует дешифратор синдрома в составе синдромного декодера (n,k)-кода?

14-20. Как реализуется устройство исправления ошибок в составе синдромного декодера (n,k)-кода?

14-21. Как реализуется устройство обнаружения ошибок в составе синдромного декодера (n,k)-кода?

14-22. Как реализуется декодер максимального правдоподобия?

14-23. Какие (n,k)-коды называются кодами Хэмминга?

14-24. Что называется радиусом сферической упаковки кода?

14-25. Что называется радиусом покрытия кода?

14-26. Какие коды называются совершенными?

14-27. Какие коды называются квазисовершенными?

14-28. Как выполняется укорочение кода?

14-29. Как выполняется расширение кода?

14-30. Для чего выполняется расширение кода?

Лекция 15

Полиномиальные

коды

Полиномиальные коды

В предыдущем разделе кодовые комбинации (n,k)-кода представлялись в виде набора символов (а₀, а₁, . . .а_n-1) длиной n. Другой способ представления того же кодового слова состоит в том, чтобы элементы а₀, а₁, . . .а_n-1 считать коэффициентами полинома n-1 степени от некоторой фиктивной или формальной переменной x, т.е.

.

Используя это обозначение, можно определить полиномиальный код, как множество всех полиномов степени, не большей n-1, содержащих в качестве сомножителя некоторый фиксированный полином g(x). Полином g(x) называется порождающим полиномом кода.

Для того чтобы иметь возможность умножать кодовые полиномы, разлагать их на множители и производить другие операции, необходимо потребовать, чтобы все коэффициенты полинома были элементами некоторого конечного алгебраического поля. Конечное поле, называемое также полем Галуа и обозначаемое GF(q) – это конечное множество, состоящее из q элементов, в котором определены правила для выполнения арифметических операций. Основное отличие их от обычных арифметических операций состоит в том, что в конечном поле все операции производятся над конечным числом элементов, в связи с чем все конечные поля обладают следующими свойствами:

1. Существуют две операции, используемые для комбинирования элементов - умножение и сложение.

2. Результатом сложения или умножения двух элементов является третий элемент, лежащий в том же поле.

3. Поле всегда содержит мультипликативную единицу, обозначаемую 1, и аддитивную единицу, обозначаемую 0, так, что а*1=а и а+0=а для любого элемента а поля.

4. Для любого элемента а поля существует обратный элемент по сложению (-а), такой, что а + (-а)=0 и обратный элемент по умножению а^-1 (при а0), такой, что а* а^-1=1. Существование этих элементов позволяет использовать обычные обозначения для вычитания и деления.

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

Конечные поля существуют не при любом числе элементов q, а только в том случае, если число элементов q является простым числом или степенью простого числа. В первом случае поле называется простым, во втором – расширенным. Для каждого допустимого q существует ровно одно поле. Другими словами, правила сложения и умножения, удовлетворяющие всем указанным требованиям можно задать только одним способом. Если q – простое число, то элементами поля являются числа 0, 1, . . . , q-1, а сложение и умножение являются сложением и умножением по модулю q.

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

1. Кодовая комбинация 100101 может быть представлена в виде полинома

f(x)=1*x⁵+0*x⁴+0*x³+1*x²+0*x¹+1*x⁰b = x⁵+x²+1.

2. Сложение таких полиномов осуществляется следующим образом. Пусть, например, f₁ = x⁷+x⁴+x³+x+1, а f₂ = x⁵+x⁴+x²+x , тогда f₃=f₁+f₂ = x⁷+x⁵+x³+x²+1. в двоичном виде 10011011  00110110 = 10101101.

3. Умножение полиномов. Пусть, например, f₁ = x³+x²+1 и f₂ = x+1, тогда f₃=f₁*f₂ = x⁴+x³+x+x³+x²+1 = x⁴+x²+x+1. В двоичном виде (1101)*(11)=(01101)  (11010) = 10111. Циклический сдвиг некоторого полинома, а он, напоминаю, форма представления кодовой комбинации, соответствует простому умножению этого полинома на x.

4. Деление полиномов. Пусть, например, f₃ = x⁴+x²+x+1, а f₂ = x+1, тогда f₁= f₃/f₂ = x³+x²+1, что можно продемонстрировать, выполняя деление полиномов столбиком или делая то же самое в двоичном виде.

При некоторых значениях n полиномиальные коды обладают свойством цикличности и называются циклическими. Свойство цикличности состоит в том, что если кодовая комбинация а_n, а_n-1, . . . , а₁ является разрешенной кодовой комбинацией данного кода, то и кодовая комбинация, а_n-1, . . . , а₁, а_n, получаемая из нее путем циклического сдвига, тоже будет разрешенной кодовой комбинацией данного кода. Сдвиг обычно осуществляется справа налево, причем крайний левый символ переносится в конец комбинации. Число возможных циклических (n,k)- кодов значительно меньше числа различных групповых (n,k)- кодов.

При использовании циклических кодов процесс кодирования, так же, как и в рассмотренных (n,k)- кодах, сводится к определению значений n-k контрольных разрядов на основании известных значений k информационных разрядов для каждой кодовой комбинации.

При полиномиальном представлении этот процесс осуществляется следующим образом. Полином f(x), отображающий комбинацию безизбыточного двоичного кода умножается на x^n-k. Это приводит к увеличению длины кодовой комбинации на n-k разрядов, которые и используются в качестве контрольных. Далее произведение f(x)* x^n-k делится на некоторый полином g(x), названный ранее образующим, и остаток от этого деления r(x) суммируется с произведением f(x)* x^n-k. Полученная кодовая комбинация описывается полиномом

, (3.32)

который без остатка делится на образующий полином g(x).

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

Пример 3.10. Пусть n=7, k=4, g(x)=x³+x²+1. Найти кодовую комбинацию s(x), если ее информационная часть описывается полиномом f(x)=x³+x+1.

Решение: n-k=7-4=3, тогда f(x)* x^n-k = (x³+x+1)x³ = x⁶+x⁴+x³.

с остатком r(x)=x². Таким образом, искомая кодовая комбинация = x⁶+x⁴+x³+x² или в двоичном виде 1011100, где левые четыре разряда представляют собой информационные разряды, соответствующие полиному f(x)=x³+x+1, а остальные три разряда – контрольные, соответствующие полиному r(x)=x².

Таким образом, выявлено первое свойство образующего полинома g(x), состоящее в том, что все разрешенные комбинации данного кода делятся на него без остатка. Он позволяет выбрать из большого числа комбинаций только те, которые удовлетворяют заданному закону построения кода, т.е. разрешенные. Именно поэтому полином g(x) и называется образующим.

Степень l образующего полинома g(x) не может быть меньше требуемого числа контрольных разрядов n-k. Для упрощения обычно полагают l=n-k. Но не любой полином этой степени может выступать в качестве образующего полинома циклического кода. В качестве таковых могут использоваться только так называемые неприводимые полиномы. Полином называется приводимым, если он может быть представлен в виде произведения полиномов низших степеней, в противном случае полином называется неприводимым. Другими словами, неприводимый полином делится без остатка только на самого себя и на единицу. Неприводимые полиномы играют роль, сходную с простыми числами в теории чисел. Из нескольких неприводимых полиномов данной степени в качестве образующего полинома следует выбирать самый короткий, однако число ненулевых членов g(x) не должно быть меньше требуемого кодового расстояния кода.

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

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

Пример 3.11. Построить образующую матрицу циклического кода (7,4) с образующим полиномом g(x)=x³+x+1.

Решение.

Запишем базовые информационные комбинации:

0001

0010

0100

1000

Представим их в виде полиномов:

1

x

x^2

x^3

Умножим на x^n-k=x³

x^3

x^4

x^5

x^6

Поделим каждый из них на образующий полином и зафиксируем остаток:

	Частное	Остаток
	1		011
			110
			111
			101

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

Существует другой способ построения образующей матрицы, базирующийся на основной особенности циклического (n,k)-кода. Первая строка образующей матрицы формируется путем приписывания слева к представленному двоичным кодом образующему полиному k-1 нулей. Каждая следующая строка образуется циклическим сдвигом предыдущей строки на один разряд влево. Для того же образующего полинома g(x)=x³+x+1 образующая матрица, построенная таким способом, будет выглядеть следующим образом .

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

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

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

Тогда для рассматриваемого циклического кода с образующим полиномом g(x)=x³+x+1 проверочная матрица будет выглядеть следующим образом .

Идея обнаружения ошибок в кодовой комбинации циклического кода основана на сформулированном ранее утверждении, что при отсутствии ошибок принятая кодовая комбинация совпадает с переданной , т.е. без остатка делится на образующий полином g(x).

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

Следовательно, при делении на g(x) получим .

При наличии однократной ошибки в каком-либо информационном разряде полиномы ошибок имеют вид:

1

x

x^2

x^3

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

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

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

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

1. Число разрядов регистра, т.е. число триггеров, выбирается равным числу проверочных разрядов n-k, т.е. равным степени образующего полинома.

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

3. Триггеры регистра нумеруются слева направо от 1 до n-k.

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

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

6. На второй вход сумматора по модулю два, первый вход которого соединен с выходом последнего триггера с номером n-k, подаются в последовательном коде информационные разряды, т.е. этот вход является входом кодера. Выход этого сумматора соединяется с входом первого триггера и вторыми входами всех остальных сумматоров по модулю два.

После того, как все k информационных разрядов последовательно поступят в кодер, одновременно будучи выданными в линию, в триггерах регистра будет сформирован остаток, состоящий из n-k контрольных символов, которые должны быть переданы вслед за информационными. Для управления этим процессом в структуру кодера необходимо ввести три ключа К1, К2, К3. Ключи К1 и К2 необходимы для того, чтобы коммутировать выход кодера либо с входом кодера при передаче k информационных разрядов, либо с выходом регистра при передаче n-k контрольных разрядов. Чтобы эти уже сформированные разряды выдвигались из регистра без искажений, необходимо разорвать цепь обратной связи, для чего и служит ключ К3.

С учетом всего сказанного построим структуру кодера (рис. 3.12) циклического кода (7,4) с образующим полиномом g(x)=x³+x+1.

Рис. 3.12. Кодер циклического кода (7,4)

Иногда более удобной оказывается другая реализация кодера с использованием не (n-k)-разрядного, а k-разрядного регистра сдвига с обратной связью на основе сумматоров по модулю два, который описывается не образующим, а т.н. проверочным полиномом h(x), получаемым в соответствии с выражением . Для рассмотренного ранее кода проверочный полином .

Построенная в соответствии с этим полиномом структура кодера приведена на рис. 3.13.

Рис. 3.13. Кодер циклического кода (7,4)

Работа кодера начинается с того, что в регистр с отключенной обратной связью (0 на входе управления) заносятся четыре информационных символа (старший разряд в Т4). Затем обратная связь включается (1 на входе управления) и регистр сдвигается семь раз. Первые четыре символа, поступающие с выхода кодера, являются информационными, следующие за ними три символа – контрольными.

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

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

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

Рис. 3.14. Декодер циклического кода (7,4) с обнаружением ошибки

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

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

Для увеличения кодового расстояния циклического кода может быть использовано преобразование расширения кода, выполняемое за счет введения дополнительных контрольных разрядов. Одним из простейших способов расширения кода является введение одного контрольного разряда общей проверки на четность. В результате, например, циклический код (7,4) с образующим полиномом превратиться в циклический код (8,4) с образующим полиномом , поскольку полином (x+1) является образующим для циклического кода с одним контрольным разрядом, способным обнаруживать все ошибки нечетной кратности. Отсюда (попутно) можно сделать вывод о том, что код с проверкой на четность является циклическим кодом с образующим полиномом (x+1). Полученный расширенный код с d=4 будет обладать такими же корректирующими свойствами, что и аналогичный расширенный код Хэмминга. Можно сделать обобщение, состоящее в том, что для любого кода с нечетным кодовым расстоянием введение общей проверки на четность увеличивает кодовое расстояние на 1.

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

.

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

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

,

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

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

Случай, когда число s проверок в каждой ортогональной системе на единицу меньше кодового расстояния s=d-1 является в известном смысле идеальным. В этом случае голосование позволяет полностью реализовать корректирующие свойства кода. Код, для каждого символа которого существует система из d-1 ортогональных проверок, называется полностью ортогонализируемым.

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

.

Суммируя по модулю два второе и третье уравнения и разрешая полученные три уравнения относительно а₇, получаем систему

,

отвечающую сформулированным ранее условиям ортогональности.

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

Анализируя указанным выше способом каждый символ принятой кодовой комбинации можно правильно восстановить посланную кодовую комбинацию, если произошло не более одной ошибки, или обнаружит двойную ошибку. Тем самым полностью реализуются корректирующие способности этого кода, поскольку его кодовое расстояние d=4.

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

1 проверка	2 проверка	3 проверка	М
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1