Циклические коды. Циклические коды Содержится ли в циклическом префиксе полезная информация

Циклическим кодом называется линейный код, который представляет собой конечное множество, замкнутое относительно операции циклического сдвига кодовых векторов, образующих его. Пусть дан n -мерный вектор v = a 0 a 1 …a n -1 с координатами из конечного поля F . Его циклическим сдвигом называется вектор v" = a n -1 a 0 a 1 …a n -2 .

Рассмотрим n -мерное арифметическое пространство над полем Галуа GF (2). Каждому вектору a 0 a 1 …a n -1 из GF (2) можно сопоставить взаимно однозначно многочлен a 0 +a 1 x +…+a n -1 x n -1 с коэффициентами из GF (2). Сумме двух векторов a 0 a 1 …a n -1 и b 0 b 1 …b n -1 ставится в соответствие сумма соответствующих им многочленов, произведению элементов поля на вектор - произведение многочлена, соответствующего этому вектору, на элемент.

Рассмотрим некоторый многочлен g (x ) из описанного линейного пространства. Множество всех многочленов из этого подпространства, которые делятся без остатка на g (x ), образует линейное подпространство. Линейное подпространство определяет некоторый линейный код.

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

Покажем, как связаны полиномиальные коды C (g (x )) и циклические коды. Пусть a = a 0 …a n -1 – некоторое кодовое слово, а соответствующий кодовый многочлен a (x ) = a 0 +...+a n -1 x n -1 . Циклическому сдвигу a " соответствует кодовый многочлен a "(x ) = a n -1 +a 0 x +…+a n -2 x n -1 , который можно выразить через первоначальный:

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

В теории кодирования доказывается следующая теорема: если многочлен g (x ) имеет степень n –k и является делителем x n –1, то C (g (x )) является линейным циклическим (n , k )-кодом.

Многочлен x n –1 разложим на множители x n –1 = (x –1)(x n -1 +x n -1 +…+1). Следовательно, циклические коды существуют при любом n . Число циклических n -разрядных кодов равно числу делителей многочлена x n –1. Для построения циклических кодов разработаны таблицы разложения многочленов x n –1 на неприводимые многочлены, то есть на такие, которые делятся только на единицу и на самого себя.

Рассмотрим, например, какие коды можно построить на основе многочлена x 7 –1 над полем GF (2). Разложение многочлена на неприводимые множители имеет вид

Поскольку можно образовать шесть делителей многочлена x 7 –1, комбинируя неприводимые делители, существует шесть двоичных циклических кодов. (n , k )-код определяется, во-первых, значением n , а во-вторых, значением k = n – s , s – степень многочлена-делителя x n –1, определяющего код. Ниже приведены делители полинома и соответствующие им значения k :

x – 1, s =1, k =6;

x 3 +x 2 +1, s =3, k =4;

x 3 +x +1, s =3, k =4;

(x –1)(x 3 +x 2 +1)=x 4 +x 2 +x+1, s =4, k =3;

(x –1)(x 3 +x +1)=x 4 +x 3 +x 2 +1, s =4, k =3;

(x 3 +x 2 +1)( x 3 +x +1)=x 6 + x 5 + x 4 + x 3 + x 2 + x , s =6, k =1.

(7, 6)-код имеет лишь один проверочный символ, а (7, 1)-код – лишь один информационный. Они являются соответственно кодом с проверкой на чётность и кодом с повторением.

Как и обычный линейный код, циклический код может быть задан порождающей матрицей. Следовательно, задача состоит в том, чтобы найти такую матрицу, то есть найти k линейно независимых кодовых комбинаций, образующих её. Воспользуемся для этого свойством замкнутости циклического кода относительно операции циклического сдвига. Заметим, что циклический сдвиг вправо на один разряд эквивалентен умножению многочлена g (x ) на x . Тогда порождающую матрицу можно построить, взяв в качестве строк порождающий многочлен и k его циклических сдвигов:

Рассмотрим теперь, как с помощью порождающего многочлена g (x ) = 1+x +x 3 осуществляется кодирование (7, 4)-кодом. Возьмём, например, 4-разрядное слово (0101), которому соответствует многочлен f (x ) = x + x 3 . Перемножив эти два многочлена.

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

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

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

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

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

При декодировании принятой л-разрядной кодовой комбинации опять производится деление на порождающий (производящий, образующий) полином.

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

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

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

Таблица 2.6

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

Увеличивая разность (п - т), можно не только нарастить число исправляемых бит s, но и обнаружить множественные ошибки. Проценты обнаруживаемых множественных ошибок приведены в табл. 2.7.

Таблица 2.7

Проценты обнаруживаемых множественных ошибок

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

где a„_j = {0, 1}, причем а„_, = 0 соответствуют нулевым элементам комбинации, д„_, = 1 - ненулевым; i - номер разряда кодовой комбинации.

Представим полиномы для конкретных 4-элементных комбинаций:

Операции сложения и вычитания являются эквивалентными и ассоциативными и выполняются по модулю 2:

Примеры выполнения операций:

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

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

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

Допустим, задана исходная кодовая комбинация и соответствующий ей полином:

Умножим а(х) на х:

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

Сдвиг исходной комбинации на / тактов можно представить следующим образом: а(х) ? У - а„(х" - 1), т.е. умножением а(х) нах" и взятием остатка по модулю (х" - 1). Взятие остатка необходимо при получении многочлена степени, большей или равной п.

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

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

где Р(х) - исходная кодовая комбинация, на базе которой получены все остальные (т - 1) базовые комбинации;

С, = 0 или Cj = 1 («О», если результирующая степень полинома Р(х)-х‘ не превосходит (л - 1), или «1» - если превосходит).

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

Порождающий полином должен удовлетворять следующим требованиям:

Р(х) должен быть ненулевым;
вес Р(х ) не должен быть меньше минимального кодового расстояния: V(P(x)) > d mm ;
Р(х) должен иметь максимальную степень к (к - число избыточных элементов в коде);
Р(х) должен быть делителем полинома (х" - 1).

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

Для определения степени порождающего полинома можно воспользоваться выражением г > log 2 (и + 1), где п - размер передаваемого пакета за один раз, т.е. длина строящегося циклического кода.

Примеры порождающих полиномов приведены в табл. 2.8.

Таблица 2.8

Примеры порождающих полиномов

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

Пусть заданы полином Р(х) = а г _ { х г + а г _ 2 х г ~ 1 + ... + 1, определяющий корректирующую способность кода, и число проверочных разрядов к, а также исходная комбинация простого от-элементного кода и информационные разряды в виде многочлена А т (х).

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

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

полином:

Остаток деления обозначим как R(x).

3. Окончательно разрешенная кодовая комбинация циклического

кода определится как = А т (х) ? x r + R(x).

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

Алгоритм определения ошибки следующий.

Пусть заданы «-элементные комбинации (п = к + т).

1. Выявляем факт наличия ошибки. Получаем остаток от деления принятой комбинации А п -(х) на порождающий полином Р(х): А (х)
--- = Rq(x). Наличие остатка R 0 (x) при (Л 0 (х) ф 0) свидетельствует Р(х)

об ошибке.

2. Делим полученный полином #(х) = Л„_, (х) 0 Rq (х) на образующий Р г (х): Ш-1 = R(x), где R(x) - текущий остаток.

3. Сравниваем ЛДх) и R(x). Если они равны, то ошибка произошла в старшем разряде. Если нет, то увеличиваем степень принятого полинома на х и снова делим:

4. Сравниваем полученный остаток с Rq(x). Если они равны, то ошибка произошла во втором разряде. Если они не равны, то умножаем Щх) х 2 и повторяем эти операции до тех пор, пока не получим

R(x) = ад.

Ошибка будет в разряде, соответствующем числу, на которое повышена степень Щх), плюс 1. Например, в случае равенства R(x) и ЛДх)

БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ

кафедра РЭС

реферат на тему:

«Циклические коды. Коды БЧХ»

МИНСК, 2009

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

Циклическим кодом называется линейный блоковый (n,k)-код, который характеризуется свойством цикличности, т.е. сдвиг влево на один шаг любого разрешенного кодового слова дает также разрешенное кодовое слово, принадлежащее этому же коду и у которого, множество кодовых слов представляется совокупностью многочленов степени (n-1) и менее, делящихся на некоторый многочлен g(x) степени r = n-k, являющийся сомножителем двучлена x n +1.

Многочлен g(x) называется порождающим.

Как следует из определения, в циклическом коде кодовые слова представляются в виде многочленов

где n - длина кода; - коэффициенты из поля GF(q).

Если код построен над полем GF(2), то коэффициенты принимают значения 0 или 1 и код называется двоичным.
Пример. Если кодовое слово циклического кода

то соответствующий ему многочлен

Например, если код построен над полем GF(q)=GF(2 3), которое является расширением GF(2) по модулю неприводимого многочлена f(z)=z 3 +z+1, а элементы этого поля имеют вид, представленный в таблице 1,

то коэффициенты

принимают значения элементов этого поля и поэтому они сами отображаются в виде многочленов следующего вида
где m - степень многочлена, по которому получено расширение поля GF(2);\ a i - коэффициенты, принимающие значение элементов GF(2), т.е. 0 и 1. Такой код называется q-ным.

Длина циклического кода называется примитивной и сам код называется примитивным, если его длина n=q m -1 на GF(q).

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

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

Результатом деления двучлена x n +1 на многочлен g(x) является проверочный многочлен h(x).

При декодировании циклических кодов используются многочлен ошибок e(x) и синдромный многочлен S(x).

Многочлен ошибок степени не более (n-1) определяется из выражения

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

Ненулевые коэффициенты в е(x) занимают позиции, которые соответствуют ошибкам.

Пример.

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

или

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

(см. таблицу 2).

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

Перечисленные многочлены можно складывать, умножать и делить, используя известные правила алгебры, но с приведением результата по mod 2, а затем по mod x n +1, если степень результата превышает степень (n-1).

Допустим, что длина кода n=7, то результат приводим по mod x 7 +1.

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

Пример.

Матричное задание кодов

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

При построении матрицы H (n,k) старший коэффициент многочлена h(x) располагается справа.

Пример. Для циклического (7,4)-кода с порождающим многочленом g(x)=x 3 +x+1 матрицы G (n,k) и H (n,k) имеют вид:

где

Для систематического циклического кода матрица G (n,k) определяется из выражения

где I k - единичная матрица; R k,r - прямоугольная матрица. Строки матрицы R k,r определяются из выражений или где a i (x) - значение i-той строки матрицы I k ; i - номер строки матрицы R k,r .

Пример. Матрица G (n,k) для (7,4)-кода на основе порождающего многочлена g(x)=x 3 +x+1, строится в следующей последовательности

или

Определяется R 4,3 , используя

так как

Аналогичным способом определяется

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

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

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

Таким образом, дополнительная матрица С, к имеет вид

Теперь строим производящую матрицу

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

Таблица 39 (см. скан)

Известный интерес представляет рассмотрение следующего простейшего кода с образованного с помощью неприводимого полинома второй степени

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

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

единичной матрицы (для нахождения дополнительной матрицы образуется. три вида остатков: 11, 01 и 10. Следовательно, вес каждой комбинации полученного -кода будет не менее двух. Минимальное кодовое расстояние между двумя любыми комбинациями также равно двум. Но такими же величинами характеризуется и простейший код с одной проверкой на четность, образованный двучленом первой степени Однако корректирующая способность обоих кодов неодинакова. Рассматриваемый код имеет большую избыточность и позволяет обнаруживать не только любые ошибки нечетной кратности, но и любые парные смежные ошибки, а также все ошибки, разделенные одним неискаженным элементом .

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

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

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

Предположим, требуется закодировать одну из комбинаций четырехзначного двоичного кода. Предположим также, что эта комбинация G(x) = x 3 + x 2 + 1 ® 1011. Пока не обосновывая свой выбор, берем из таблицы неприводимых многочленов в качестве образующего многочлен P(x) = x 3 + x + 1 ® 1011. Затем умножим G(x) на одночлен той же степени, что и образующий многочлен. От умножения многочлена на одночлен степени n степень каждого члена многочлена повысится на n , что эквивалентно приписыванию n нулей со стороны младших разрядов многочлена. Так как степень выбранного неприводимого многочлена равна трем, то исходная информационная комбинация умножается на одночлен трех степеней

G(x) x n = (x 3 + x 2 + 1 ) x 3 =x 6 + x 5 + x 3 = 1101000.

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

Значение корректирующих разрядов находят по результатам от деления G(x) x n на P(x) :

x 6 +x 5 +0+x 3 +0+0+0 ½x 3 +x+1

x 6 +0+x 4 +x 3

x 5 +x 4 +0+0 x 3 +x 2 +x+1+ x 5 +0+x 3 +x 2

x 4 + x 3 +x 2 +0

x 4 + 0 +x 2 +x

x 3 +0+x+0

x 3 +0+x+1

Таким образом,

или в общем виде

где Q(x) ¾ частное, а R(x) ¾ остаток от деления G(x)×x n на P(x).

Так как в двоичной арифметике 1 Å 1 = 0, а значит, -1 = 1, то можно при сложении двоичных чисел переносить слагаемые из одной части в другую без изменения знака (если это удобно), поэтому равенство вида a Å b = 0 можно записать и как a = b , и как a - b = 0. Все три равенства в данном случае означают, что либо a и b равны 0, либо a и b равны 1, т.е. имеют одинаковую четность.

Таким образом, выражение (5.1) можно записать как

F(x)=Q(x) P(x)= G(x) x n +R(x),

что в случае нашего примера даст

F(x)= (x 3 + x 2 + x + 1) (x 3 + x + 1)= (x 3 + x 2 + 1) x 3 + 1,

F(x)= 1111 1011 = 1101000 + 001 = 1101001.

Многочлен 1101001 и есть искомая комбинация, где 1101‑ информационная часть, а 001 ‑ контрольные символы. Заметим, что искомую комбинацию мы получили бы и как в результате умножения одной из комбинаций полного четырехзначного двоичного кода (в данном случае 1111) на образующий многочлен, так и умножением заданной комбинации на одночлен, имеющий ту же степень, что и выбранный образующий многочлен (в нашем случае таким образом была получена комбинация 1101000) с последующим добавлением к полученному произведению остатка от деления этого произведения на образующий многочлен (в нашем примере остаток имеет вид 001).

И тут решающую роль играют свойства образующего многочлена P(x) . Методика построения циклического кода такова, что образующий многочлен принимает участие в образовании каждой кодовой комбинации, поэтому любой многочлен циклического кода делится на образующий без остатка. Но без остатка делятся только те многочлены, которые принадлежат данному коду, т. е. образующий многочлен позволяет выбрать разрешенные комбинации из всех возможных. Если же при делении циклического кода на образующий многочлен будет получен остаток, то значит либо в коде произошла ошибка, либо это комбинация какого-то другого кода (запрещенная комбинация). По остатку и обнаруживается наличие запрещенной комбинации, т. е. обнаруживается ошибка. Остатки от деления многочленов являются опознавателями ошибок циклических кодов.

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

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

01100 11111+

начиная с восьмого, остатки будут повторяться.

Остатки от деления используются для построения образующих матриц, которые, благодаря своей наглядности и удобству получения производных комбинаций, получили широкое распространение для построения циклических кодов. Построение образующей матрицы сводится к составлению единичной транспонированной и дополнительной матрицы, элементы которой представляют собой остатки от деления единицы с нулями на образующий многочлен P(x) . Напомним, что единичная транспонированная матрица представляет собой квадратную матрицу, все элементы которой ‑ нули, кроме элементов расположенных по диагонали справа налево сверху вниз (в нетранспонированной матрице диагональ с единичными элементами расположена слева направо сверху вниз). Элементы дополнительной матрицы приписываются справа от единичной транспонированной матрицы. Использоваться могут лишь те остатки, вес которых W ³ d 0 - 1, где d 0 ‑ минимальное кодовое расстояние. Длина остатков должна быть не менее количества контрольных разрядов, а число остатков должно равняться числу информационных разрядов.

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

Пример.

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

Решение.

По таблице 5.12 выбираем ближайшее значение k ³ 10 .

Таблица 5.12 – Соотношения между информационными и проверочными символами для кода длиной до 16 разрядов

n	k	ρ	n	k	ρ

Согласно таблице таким значением будет k = 11, при этом r = 4, а

n = 15. Также выбираем образующий многочлен x 4 + x 3 +1.

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

Транспонированная матрица для k = 11 имеет вид:

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

Полная образующая матрица будет иметь вид:

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

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

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

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

Место ошибки в кодовой комбинации не имеет значения. Если k ³ (n / 2) , то после определенного количества сдвигов все ошибки окажутся в зоне “разового” действия образующего многочлена, т. е. достаточно получить один остаток, вес которого W £ s , и этого уже будет достаточно для исправления искаженной комбинации.

Подробно процесс исправления ошибок рассматривается ниже на примерах построения конкретных кодов.