Циклические коды

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

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

Ознакомимся с принципами построения циклических кодов на примере кода (7, 4). Образуем порождающую матрицу этого кода из комбинаций, содержащих по три единицы. Учтем, что единицы в комбинациях не должны чередоваться с нулями через равные промежутки, так как при суммировании результирующая комбинация по условию замкнутости должна иметь не менее трех единиц. Этим требованиям отвечают только два варианта циклических комбинаций: 0001101 и 0001011. Таким образом, существуют только две матрицы циклического кода (7, 4):

Рассмотрим первый вариант циклического кода (7, 4). Кодовую комбинацию 0001101 удобно представлять в виде комбинации 1101 с приписанными в старших разрядах тремя нулями. Будем называть комбинацию 1101 порождающей (образующей). Циклический сдвиг кодовой комбинация на один разряд влево можно рассматривать как умножение порождающей комбинации на комбинации 10, 100 и 1000. Полученные таким образом комбинации, естественно, делятся на порождающую без остатка. Не вошедшие в порождающую матрицу разрешенные комбинации можно получить суммированием комбинаций, вошедших в матрицу. Один из возможных вариантов получения всех
15 разрешенных комбинаций сводится к следующему. В качестве 1-й разрешенной комбинации возьмем, например, первую комбинацию из порождающей матрицы: 0001101. Поочередно сдвигая эту комбинацию влево на один разряд, будем иметь еще шесть разрешенных комбинаций. Седьмая комбинация при этом будет такой: 1000110. Просуммировав 1-ю и 2-ю комбинации из порождающей матрицы, получим 8-ю разрешенную комбинацию. Циклическим сдвигом этой комбинации получаем еще шесть разрешенных комбинаций. Наконец. 15-ю комбинацию получаем путем суммирования (по модулю 2) всех комбинаций порождающей матрицы, за исключением 3-й.

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

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

В литературе при рассмотрении теории циклических кодов для удобства кодовые комбинации обычно записываются условно в виде многочленов. С каждой комбинацией сопоставляется соответствующий степенной многочлен, сформированный по следующему правилу: единица в i-м разряде комбинации обозначается как x^i-1, отсутствие в многочлене элемента x^k-1 означает, что в k-м разряде комбинации стоит нуль. Например, порождающие многочлены рассмотренных вариантов циклического кода (7, 4) 1101 и 1011 записываются условно так: х³+х²+1 и х³+х+1, кодовой комбинации 10000000 эквивалентен многочлен х⁷.

Построение циклического кода должно начинаться с выбора необходимого порождающего многочлена. В литературе приведены таблицы возможных порождающих многочленов с указанием корректирующих возможностей кодов при использовании этих многочленов. Так, при трех проверочных разрядах порождающие (неприводимые) многочлены имеют два вида: х³+х+1 (1011) и х³+х²+1 (1101); для четырех проверочных разрядов имеется три неприводимых многочлена: х⁴+х+1 (10011), х⁴+х³+1 (11001),
х⁴+х³+х²+х+1 (11111).

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

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

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

´ 1011

Å 1111

1111.

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

Декодирование систематических циклических кодов

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

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

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

Алгоритм первый. Декодируемая комбинация делится на порождающую. Если остаток после деления соответствует синдрому ошибки в младшем разряде, символ исправляется в этом разряде. Если получается иной синдром ошибки, декодируемая комбинация сдвигается на один разряд влево и процедура деления и определения остатка повторяется. Этот цикл (сдвиг - деление) повторяется до тех пор, пока полученный остаток не совпадет с синдромом ошибки в младшем разряде. При совпадении исправляется ошибка в младшем разряде, после чего комбинации сдвигается в обратную сторону в исходное состояние (если было проведено m делений, то производится сдвиг вправо на m-1 разрядов).

Алгоритм второй. Возможность применения этого метода основана на следующем. При делении комбинации с ошибкой на порождающую комбинацию остаток от деления образуется за счет того, что вектор ошибки не делится на порождающую комбинацию. Кроме того, вектор х^n+k-1, деленный на порождающий многочлен, дает остаток с единицей в
k-м разряде и нулями в остальных разрядах. Например, в коде (7, 4) многочлен х⁷ (комбинация 10000000) дает остаток 001, многочлен х⁸ – остаток 010 и т.д. С другой стороны, разрешенная комбинация, сдвинутая влево на любое число разрядов без перестановки старших разрядов (сдвиг при этом сводится к дописанию справа соответствующего количества нулей), также делится на порождающую без остатка. Указанные факторы позволяют применить следующую процедуру исправления ошибок.

1. Пришедшая комбинация делится на порождающую.

2. При отсутствии остатка комбинация считается безошибочной и передается потребителю информации.

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

4. Если при сравнении происходит совпадение, принимается решение о наличии ошибки в старшем разряде и производится исправление.

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

Пример. По каналу связи принята кодовая комбинация 1001000, закодированная циклическим кодом (7, 4) с порождающей комбинацией 1011. Необходимо произвести декодирование, т.е. исправление возможной ошибки, применив первый алгоритм.

Решение. 1. Делим полученную комбинацию на порождающую:

1001000 / 1011

Å 1011

==1000

Å 1011

==110

2. Поскольку синдром ошибки в младшем разряде равен 001, т.е. не совпадает в полученным, сдвигаем полученную комбинацию на 1 разряд влево в снова производим деление:

0010001 / 1011

Å 1011

==111

3. Так как остаток снова не равен 001, сдвигаем принятую комбинацию еще на разряд влево и делим:

0100010 / 1011

Å 1011

==1110

Å 1011

=101

4. Еще раз повторяем сдвиг и деление:

1000100 / 1011

Å 1011

==1110

Å 1011

=1010

Å 1011

=001

5. Исправляем символ в младшем разряде сдвинутой комбинация:

1000100Å 0000001=1000101.

6. Сдвигаем комбинацию в обратном направлении (вправо) на три разряда: 1011000.

7. Отсекаем три младших (проверочных) разряда и передаем потребителю информации комбинацию 1011.

Пример. Используется тот же код, что и в предыдущем примере. Получена комбинация 1001000. Необходимо произвести декодирование по 2-му алгоритму.

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

1000000 / 1011

Å 1011

==1100

Å 1011

=1110

Å 1011

=101

Таким образом, синдром ошибки в 7-м разряде равен 101. Делим полученную комбинацию на порождающую:

1001000 / 1011

Å 1011

==1000

Å 1011

==1100 ← дописан

Å 1011

==1100 ← дописан

Å 1011

=101 – синдром ошибки в 7-м разряде

При делении до получения остатка 101 потребовалось дописать два нуля, что эквивалентно сдвигу комбинации на два разряда влево, следовательно, ошибка в принятой комбинации имеет место в 5-м разряде (7-2=5). Суммируя вектор ошибки в 5-м разряде с полученной комбинацией, исправляем:

1001000Å 0010000=1011000