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

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

Пример. Двоичный вектор может быть представлен в виде полинома следующим образом:

Представление двоичных векторов в виде полиномов позволяет свести действие над векторами к действиям над многочленами. При этом:

сложение многочленов сводится к сумме по модулю 2 коэффициентов при равных степенях переменной

умножение производится по обычному правилу умножения степенных функций, однако полученные коэффициенты при данной степени складываются по модулю 2;

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

Пример. Найти сумму многочленов

Найти произведение многочленов

Выполнить деление многочленов

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

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

Примеры неприводимых многочленов:

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

где остаток от деления

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

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

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

В результате деления полинома на полином получаем остаток . Поэтому

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

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

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

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

Для нахождения строк проверочных разрядов матрицы вычислим и запишем в виде полинома каждый вектор единичной матрицы

Длина вектора циклического кода поэтому

(см. скан)

В результате получаем порождающую матрицу С:

Любой вектрр циклического кода получается как сумма по моду векторов его порождающей матрицы. Так как циклический код является групповым, то нулевой вектор всегда приписывается циклическому коду как единичный элемент группы»

Таблица 13.5

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

Код представлен в табл. 13.5.

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

Пример, Циклический код задан своей порождающей матрицей

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

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

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

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

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

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

3. По справочникам находятся все неприводимые полиномы степени

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

где - полином информационного вектора порождающей матрицы; - одночлен степени - остаток от деления

5. Построенная порождающая матрица проверяется на выполнение следующих условий:

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

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

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

Построим циклический код мощностью 16 и корректирующей с по собностью

Для определяем значение по

3» По справочникам находим все неприводимые полиномы степени Таких полиномов два:

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

Каждый информационный вектор из матрицы представляем полиномом

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

Так как длина вектора циклического кода (см. формат порождающей матрицы то

Аналогично находим все остальные векторы порождающей мат рицы

Таблица 13.6

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

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

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

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

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

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

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

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

Код имеет в 3, т. е. корректирует ошибки кратности Пусть вместо вектора 0001101 принят вектор 0011101. Для исправления ошибки осуществляем следующие действия. Принятый вектор записываем в виде полинома: затем делим на

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

Осуществляем деление на

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

Осуществляем деление на

Полученный остаток снова содержит две единицы, поэтому делаем еще один циклический сдвиг влево на один разряд и получаем Делим на

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

Комбинация циклического кода;

Также комбинация циклического кода.

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

Например, комбинация 1001111 (п= 7) будет представлена многочленом

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

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

Построение комбинаций циклического кода возможно путем умножения исходной комбинации А (х ) на образующий полином G (x )с приведением подобных членов по модулю 2:

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

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

Часто в качестве полинома, на который осуществляется деление, берется полином G (x )= +1. При таком формировании кодовых комбинаций позиции информационных и контрольных символов заранее определить нельзя.

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

Число разрядов регистра выбирается равным степени образующего полинома.

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

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

Рисунок 17 - Схема кодирующего регистра

В табл. 4 показано, как путем сдвигов исходной комбинации 0101 получается комбинация циклического кода 1010011.п= 7, k =4. Комбинация 0101, ключ в положении 1. В течение первых четырех тактов регистр будет заполнен, затем ключ переводится в положение 2. Обратная связь замыкается. Под действием семи сдвигающих тактов проходит формирование семиразрядного циклического кода.

Таблица 4

Свойства циклического кода :

1) циклический код обнаруживает все одиночные ошибки, если образующий полином содержит более одного члена. Если G (x )=x+ 1, то код обнаруживает одиночные ошибки и все нечетные;

2) циклический код с G (x )= (x+ 1)G (x ) обнаруживает все одиночные, двойные и тройные ошибки;

3) циклический код с образующим полиномом G (x ) степени r = n - k обнаруживает все групповые ошибки длительностью в r символов.

Контрольные вопросы

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

Многие важнейшие помехоустойчивые коды систем связи, -

в частности циклические, основаны на структурах конечных Арифметика

полей Галуа. Полем называется множество элементов, которые конечного поля

звания операций взяты в кавычки, потому что они не всегда являются общепринятыми арифметическими операциями. В поле всегда имеется нулевой элемент (0), или нуль, и единичный элемент (1), или единица. Если число q элементов поля ограничено, то поле называется конечным полем , или конечным полем Галуа , и обозначается GF(q) y где q - порядок поля. Наименьшим полем Галуа является двухэлементное иоле GF(2), состоящее всего из двух элементов 1 и 0. Для того чтобы

1 Эварист Галуа (Evariste Galois, 1811 - 1832) - французский математик, заложил основы современной алгебры.

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

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

Для операций сложения и умножения выполняются обычные математические правила ассоциативности - а + (Ь + с) = (а + Ь) + с, коммутативности - а + b = b + а и а b = b а и дистрибутивности - а (Ь + с) = а b + а с.

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

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

Поле должно содержать мультипликативную единицу - элемент 1, такой, что аЛ = а для любого элемента поля а.

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

Фактически все наборы, образованные циклической перестановкой кодовой комбинации, также являются кодовыми комбинациями. Так, например, циклические перестановки комбинации 1000101 будут также кодовыми комбинациями 0001011, 0010110, 0101100 и т.д. Это свойство позволяет в значительной степени упростить кодирующее и декодирующее устройства, особенно при обнаружении ошибок и исправлении одиночной ошибки. Внимание к циклическим кодам обусловлено тем, что присущие им высокие корректирующие свойства реализуют на основе сравнительно простых алгебраических методов. В то же время для декодирования произвольного линейного блокового кода чаще применяют табличные методы, требующие большой объем памяти декодера.

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

В циклическом коде кодовые слова представляют многочленами (полиномами)

где п - длина кода; A i - коэффициенты поля Галуа (значений кодовой комбинации).

Например, для кодовой комбинации 101101 полиномиальная запись имеет вид

Примерами циклических кодов являются коды с четной проверкой, коды с повторениями, коды Хемминга, PC-коды и турбокоды.

Код Хемминга . Возможности исправления ошибок в коде Хемминга связаны с минимальным кодовым расстоянием d 0 . Исправляются все ошибки кратности q = cnt(d 0 - l)/2 (здесь cnt означает «целая часть») и обнаруживаются ошибки кратности d 0 - 1. Так, при контроле на нечетность d Q = 2 и обнаруживаются одиночные ошибки. В коде Хемминга d 0 = 3. Дополнительно к информационным разрядам вводится L = log 2 Q избыточных контролирующих разрядов, где Q - число информационных разрядов. Параметр L округляется до ближайшего большего целого значения. L-разрядный контролирующий код есть инвертированный результат поразрядного сложения (сложения по модулю 2) номеров тех информационных разрядов, значения которых равны единице.

Пример 7.7

Пусть имеем основной код 100110, т.е. Q = 6. Определим дополнительный код.

Решение

Находим, что L = 3 и дополнительный код равен

где П - символ операции поразрядного сложения, и после инвертирования имеем 000. Теперь с основным кодом будет передан и дополнительный. В приемнике вновь рассчитывают дополнительный код и сравнивают с переданным. Фиксируется код сравнения, и если он отличен от нуля, то его значение есть номер ошибочно принятого разряда основного кода. Так, если принят код 100010, го рассчитанный дополнительный код равен инверсии от 010Ш10 = 100, т.е. 011, что означает ошибку в 3-м разряде.

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

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

Турбокоды. Избыточные коды могут применяться как самостоятельно, так и в виде некоторого объединения нескольких кодов, когда наборы символов одного избыточного кода рассматриваются как элементарные информационные символы другого избыточного кода. Такое объединение стали называть каскадным кодом. Огромным достоинством каскадных кодов является то, что их применение позволяет упростить кодер и особенно декодер по сравнению с аналогичными устройствами некаскадных кодов той же длины и избыточности. Каскадное кодирование привело к созданию турбокодов. Турбокодом называют параллельную структуру сигнала, состоящую из двух или большего числа систематических кодов. Основной принцип их построения - использование нескольких параллельно работающих компонентных кодеров. В качестве компонентных можно использовать как блочные, так и сверточные коды, коды Хемминга, PC-код, БЧХ и др. Использование перфорации (выкалывания) позволяет увеличить относительную скорость турбокода, адаптировав его исправляющую способность к статистическим характеристикам канала связи. Принцип формирования турбокода состоит в следующем: входной сигнал х, состоящий из К бит, подается параллельно на N перемежителей. Каждый из последних представляет собой устройство, осуществляющее перестановку элементов в блоке из К бит в псевдослучайном порядке. Выходной сигнал с перемежителей - символы с измененным порядком следования - поступает на соответствующие элементарные кодеры. Двоичные последовательности х р i = 1,2,..., JV, на выходе кодера представляют собой проверочные символы, которые вместе с информационными битами составляют единое кодовое слово. Применение перемежителя позволяет предотвратить появление последовательностей коррелированных ошибок при декодировании турбокодов, что немаловажно при использовании традиционного в обработке рекурентного способа декодирования. В зависимости от выбора компонентного кода турбокоды делятся на сверточные турбокоды и блоковые коды-произведения.

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

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

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

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

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

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

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

Процесс циклического кодирования

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

В качестве информационных символов k для построения циклических кодов берут комбинации двоичного кода на все сочетания. В общем случае, если заданную кодовую комбинацию Q(x) умножить на образующий многочлен Р(х), получиться циклический код, обладающий теми или иными корректирующими свойствами в зависимости от выбора Р(х). Однако в этом коде контрольные символы m будут располагаться в самых разнообразных местах кодовой комбинации. Такой код не является систематическим, что затрудняет его схемную реализацию. Ситуацию можно значительно упростить, если контрольные символы приписать в конце, то есть после информационных символов. Для этой цели целесообразно воспользоваться следующим методом:

Умножаем кодовую комбинацию G(x), которую нужно закодировать, на одночлен Х m , имеющий ту же степень, что и образующий многочлен Р(х);

Делим произведение G(x)Х m на образующий многочлен Р(х m):

где Q(x) - частное от деления; R(x) - остаток.

Умножая выражение (2.1) на Р(х) и перенося R(x) в другую часть равенства без перемены знака на обратный, получаем:

Таким образом, согласно равенству (2.2), циклический код, то есть закодированное сообщение F(x), можно образовать двумя способами:

Умножение одной кодовой комбинаций двоичного кода на все сочетания на образующий полином Р(х);

Умножением заданной кодовой комбинации G(x) на одиночный многочлен Х m , имеющий туже степень, что и образующий многочлен Р(х), с добавлением остатка R(x), полученного после деления произведения G(x)Х m на образующий многочлен Р(х).

Кодирование сообщения

Требуется закодировать кодовую комбинацию 1100, что соответствует G(x)=х 3 +х 2 с помощью Р(х)=х 3 +х+1.

Умножаем G(x) на Х m , который имеет третью степень, получим:

Разделив произведение G(x)Х m на образующий многочлен Р(х m), согласно (2.1) получим:

или в двоичной эквиваленте:

Таким образом, в результате получаем частное Q(x) той же степени, что и G(x):

Q(x)=x 3 +x 2 +x>1110

и остаток:

В итоге комбинация двоичного кода, закодированная циклическим кодом, согласно (2.2) примет вид:

F(x)=1110 1011=1100010

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

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

Например, переданная кодовая комбинация F(x)=1100010, построенная с помощью образующего полинома Р(х)=1011. Под воздействием помехи кодовая комбинация трансформировалась в комбинацию F"(x)=1000010

Делим принятую комбинацию на образующий полином

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

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

Ошибка произошла в элементе с номером:

Количество остатков -2>4-2=2

То есть,ошибка во втором элементе.

Соответствующий этому слову, от формальной переменной x . Видно, что это соответствие не просто взаимнооднозначное, но и изоморфное . Так как «слова» состоят из букв из поля, то их можно складывать и умножать (поэлементно), причём результат будет в том же поле. Полином, соответствующий линейной комбинации пары слов и , равен линейной комбинации полиномов этих слов

Это позволяет рассматривать множество слов длины n над конечным полем как линейное пространство полиномов со степенью не выше n-1 над полем

Алгебраическое описание

Если кодовое слово, получающееся циклическим сдвигом на один разряд вправо из слова , то ему соответствующий полином c 1 (x ) получается из предыдущего умножением на x:

Пользуясь тем, что ,

Сдвиг вправо и влево соответственно на j разрядов:

Если m (x ) - произвольный полином над полем G F (q ) и c (x ) - кодовое слово циклического (n ,k ) кода, то m (x )c (x )m o d (x n − 1) тоже кодовое слово этого кода.

Порождающий полином

Определение Порождающим полиномом циклического (n ,k ) кода C называется такой ненулевой полином из C , степень которого наименьшая и коэффициент при старшей степени g r = 1 .

Теорема 1

Если C - циклический (n ,k ) код и g (x ) - его порождающий полином, тогда степень g (x ) равна r = n − k и каждое кодовое слово может быть единственным образом представлено в виде

c (x ) = m (x )g (x ) ,

где степень m (x ) меньше или равна k − 1 .

Теорема 2

g (x ) - порождающий полином циклического (n ,k ) кода является делителем двучлена x n − 1

Следствия: таким образом в качестве порождающего полинома можно выбирать любой полином, делитель x n − 1 . Степень выбранного полинома будет определять количество проверочных символов r , число информационных символов k = n − r .

Порождающая матрица

Полиномы линейно независимы, иначе m (x )g (x ) = 0 при ненулевом m (x ) , что невозможно.

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

, где G является порождающей матрицей , m (x ) - информационным полиномом.

Матрицу G можно записать в символьной форме:

Проверочная матрица

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

Кодирование

Несистематическое

При несистематическом кодирование кодовое слово получается в виде произведения информационного полинома на порождающий

c (x ) = m (x )g (x ) .

Оно может быть реализовано при помощи перемножителей полиномов.

Систематическое

При систематическом кодировании кодовое слово формируется в виде информационного подблока и проверочного

Пусть информационное слово образует старшие степени кодового слова, тогда

c (x ) = x r m (x ) + s (x ),r = n − k

Тогда из условия , следует

Это уравнение и задает правило систематичекого кодирования. Оно может быть реализовано при помощи многотактных линейных фильтров(МЛФ)

Примеры

Двоичный (7,4,3) код

В качестве делителя x 7 − 1 выберем порождающий полином третьей степени g (x ) = x 3 + x + 1 , тогда полученный код будет иметь длину n = 7 , число проверочных символов (степень порождающего полинома) r = 3 , число информационных символов k = 4 , минимальное расстояние d = 3 .

Порождающая матрица кода:

где первая строка представляет собой запись полинома g (x ) коэффициентами по возрастанию степени. Остальные строки - циклические сдвиги первой строки.

Проверочная матрица:

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

Так, например, 3-ий столбец получается , или в векторной записи .

Легко убедиться, что G H T = 0 .

Двоичный (15,7,5) БЧХ код

В качестве порождающего полинома g (x ) можно выбрать произведение двух делителей x 15 − 1 ^

g (x ) = g 1 (x )g 2 (x ) = (x 4 + x + 1)(x 4 + x 3 + x 2 + x + 1) = x 8 + x 7 + x 6 + x 4 + 1 .

Тогда каждое кодовое слово можно получить с помощью произведения информационного полинома m (x ) со степенью k − 1 таким образом:

c (x ) = m (x )g (x ) .

Например, информационному слову соответствует полином m (x ) = x 6 + x 5 + x 4 + 1 , тогда кодовое слово c (x ) = (x 6 + x 5 + x 4 + 1)(x 8 + x 7 + x 6 + x 4 + 1) = x 14 + x 12 + x 9 + x 7 + x 5 + 1 , или в векторном виде

См. также

Ссылки

Wikimedia Foundation . 2010 .

Смотреть что такое "Циклические коды" в других словарях:

укороченные циклические коды - — [Л.Г.Суменко. Англо русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003.] Тематики информационные технологии в целом EN shortened cyclic codes …

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

коды Голея - Семейство совершенных линейных блоковых кодов с исправлением ошибок. Наиболее полезным является двоичный код Голея. Известен также троичный код Голея. Коды Голея можно рассматривать как циклические коды. … … Справочник технического переводчика

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