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

Циклическим кодом называется линейный код, который представляет собой конечное множество, замкнутое относительно операции циклического сдвига кодовых векторов, образующих его. Пусть дан 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 . Перемножив эти два многочлена.

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

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

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

При рассмотрении циклических кодов двоичные числа представляют в виде многочлена, степень которого (п - 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, на выходе кодера представляют собой проверочные символы, которые вместе с информационными битами составляют единое кодовое слово. Применение перемежителя позволяет предотвратить появление последовательностей коррелированных ошибок при декодировании турбокодов, что немаловажно при использовании традиционного в обработке рекурентного способа декодирования. В зависимости от выбора компонентного кода турбокоды делятся на сверточные турбокоды и блоковые коды-произведения.

Основные свойства и само название циклических кодов связаны с тем, что все разрешенные комбинации двоичных символов в передаваемом сообщении могут быть получены путем операции циклического сдвига некоторого исходного слова: Обычно кодовые комбинации циклического кода рассматривают не в виде последовательности нолей и единиц, а в виде полинома некоторой степени . Любое число в любой позиционной системе счисления можно представить в общем виде как: где х - основание системы счисления; а - цифры данной системы счисления; п-1, п-2,... - показатель степени, в которую возводится основание, и одновременно порядковые номера, которые занимают разряды. Для двоичной системы х=2, а а либо «О», либо «1». Например, двоичную комбинацию 01001 можно записать в виде полинома от аргумента х: При записи кодовой комбинации в виде многочлена единица в 1-м разряде записывается членом х", а ноль вообще не записывается. Представление кодовых комбинаций в виде многочленов позволяет установить однозначное соответствие между ними и свести действия над комбинациями к действию над многочленами. Так, сложение двоичных многочленов сводится к сложению по модулю 2 коэффициентов при равных степенях переменной. Например, Умножение производится по обычному правилу умножения степенных функций, однако полученные коэффициенты при данной степени складываются по модулю 2. Например, Деление также осуществляется как обычное деление многочленов; при этом операция вычитания заменяется операцией сложения по модулю 2: Как было отмечено выше, коды названы циклическими потому, что циклический сдвиг а п ^ а л Л,..., а 2 ,а 1 ,а д1 а п1 разрешенной комбинации а п (, а п _ 2 ,...,а 1 ,а 0 также является разрешенной комбинацией. Такая циклическая перестановка при использовании представлений в виде полиномов образуется в результате умножения данного полинома на х. Если У(х)=а пЛ х п1 + а п2 х п " 2 +... + а { х+а 0 , то У(х)х = а п] х п + а п 2 х п " 1 +... + а х х 2 + а^х. Чтобы степень многочлена не превышала п-1, член х" заменяется единицей, поэтому: Например, имеем кодовую комбинацию 1101110->х в +х 5 +х 3 +.х г -1-х. Сдвинем ее на один разряд. Получим: Что то же самое, что и умножения исходного полинома на х: Теория построения циклических кодов базируется на разделах высшей алгебры, изучающей свойства двоичных многочленов. Особую роль в этой теории играют так называемые неприводимые многочлены, т. е. полиномы, которые не могут быть представлены в виде произведения многочленов низших степеней. Такой много- член делится только на самого себя и на единицу. Из высшей алгебры известно, что на неприводимый многочлен делится без остатка двучлен х"+1. В теории кодирования неприводимое многочлены называются образующими полиномами, поскольку они «образуют» разрешенные кодовые комбинации (неприводимые полиномы табулированы, см. табл. 8.4) (9]. Идея построения циклического кода сводится к тому, что полином, представляющий информационную часть кодовой комбинации, нужно преобразовать в полином степени не более п-1, который без остатка делится на образующий полином Р(х). Существенно при этом, что степень последнего соответствует числу разрядов проверочной части кодовой комбинации. В циклических кодах все разрешенные комбинации, представленные в виде полиномов, обладают одним признаком: делимостью без остатка на образующий полином Р(х). Построение разрешенной кодовой комбинации сводится к следующему: 1. Представляем информационную часть кодовой комбинации длиной к в виде полинома О(х). 2. Умножаем О(х) на одночлен У и получаем 0(х)х г, т. е. производим сдвиг ¿-разрядной кодовой комбинации на г разрядов. 3. Делим многочлен О (х)х" на образующий полином Р(х), степень которого равна г. В результате умножения О(х) на х г степень каждого одночлена, входящего в О(х), повышается на г. При делении произведения х г О[х) на образующий полином степени г получается частное С(х) такой же степени, что и 0{х). Результаты этих операций можно представить в виде: (8.28) где Щх) -остаток от деления 0(х)х г на Р(х). Поскольку С(х) имеет такую же степень, что и 0{х), то С(х) представляет собой кодовую комбинацию того же ¿-разрядного кода. Степень остатка не может быть, очевидно, больше степени образующего полинома, т. е. его наивысшая степень равна г-1. Следовательно, наибольшее число разрядов остатка не превышает г. Умножив обе части (8.28) на Р(х), ползшим: (8.29) (знак вычитания заменяется знаком сложения по модулю 2). Очевидно, что F(x) делится на Р(х) без остатка. Полином F(x) представляет собой разрешенную кодовую комбинацию циклического кода. Из (8.29) следует, что разрешенную кодовую комбинации циклического кода можно получить двумя способами: умножением кодовой комбинации простого кода С(х) на образующий полином Р(х) или умножением кодовой комбинации 0{х) простого кода на одночлен х г к добавлением к этому произведению остатка Р(х), полученного в результате деления произведения на образующий полином Р(х). При первом способе кодирования информационные и проверочные разряды не отделены друг от друга (код получается неразделимым). Это затрудняет практическую реализацию процесса декодирования. При втором способе получается разделимый код: информационные разряды занимают старшие позиции, остальные п-к разряды являются проверочными. Этот способ кодирования широко применяется на практике. Пример 3. Дана кодовая комбинация 0111. Построим циклический код с d o = 3. Решение. На первом этапе исходя из требуемого d o = 3 определим длину кода л и количество проверочных элементов к. Для этого воспользуемся таблицей 8.6.1. Для заданной четырехразрядной кодовой комбинации N-16. Тогда для d = 3 из соотношения 16(табл. 8.3) находим п - 7, соответственно, к = п - т - = 7 - 4 = 3. Следовательно, необходим код (7,4). По таблице образующих полиномов (табл. 8.4) при к = 3 определяем Р(х) = х 3 + х 2 + 1. Далее: 1) для сообщения 0111 имеем О(х) = х 2 + х + 1; 2) умножаем 0(х) на х 3 (так как г = 3): О(х) х 3 = (х 2 -I- х + 1) х 3 = х 5 + х 4 + х 3 ; 3) делим (Э(х)х 3 на Р(х): 4) получаем: ^(х) = О (х) х 3 0 Я (х) = х 5 + х 4 + х 3 + 1. Этот полином соответствует кодовой комбинации: Все указанные операции можно производить и над двоичными числами: Таблица 8.4
4) F(0,1) = O(0,l)x 3 (0,l)©R(0 1 l) = 011100000001= 0111 001. Построим теперь разрешенную кодовую комбинацию первым способом: F(x)=C(x)P(x). Произведем умножение, представляя полиномы двоичными числами: Видно, что в полученной кодовой комбинации нельзя выделить информационные и проверочные разряды. Обнаружение ошибок при циклическом кодировании сводится к делению принятой кодовой комбинации на тот же образующий полином, который использовался при кодировании (его вид должен быть известен на приеме). Если ошибок в принятой кодовой комбинации нет (или они такие, что данную передаваемую кодовую комбинацию превращают в другую разрешенную), то деление на образующий полином будет выполнено без остатка. Если при делении получится остаток, то это и свидетельствует о наличии ошибки. Пример 4. В качестве разрешенной кодовой комбинации возьмем кодовую комбинацию, полученную в предыдущем примере: Р(х)=х 5 +х 4 + х 3 + 1, а Р(х) = х 3 + х 2 +1, или в двоичном виде Е(0,1) = 0111001; Р(0,1) = 1101. Допустим, что в информационной части произошла ошибка в старшем (7-м) разряде (разряды счита- ем справа налево). Принятая кодовая комбинация имеет вид 1111001. Произведем операцию обнаружения ошибки: Наличие остатка 110 свидетельствует об ошибке. Циклические коды находят большое применение в системах передачи информации. Например, в широко распространенном модемном протоколе \7.42 для кодирования кодовых групп используется образующий полином д(Х)= X 16 + X" -2 + X 5 + 1, что эквивалентно коду 1 0001 0000 0010 0001, а также образующий полином более высокого порядка д(Х) = X 32 + X 26 + X 23 + X 22 + X 16 + X 12 + X 11 + X 10 + X 8 + X 1 + X 5 + X 4 + X 2 + 1. 8.6.