Основные свойства циклического кода
ОБЩИЕ СВЕДЕНИЯ О ЦИКЛИЧЕСКИХ КОДАХ
Определение циклических кодов
Важнейшим недостатком СЛБК (систематических линейных блоковых кодов) является высокая трудоемкость их построения при длине кодовой последовательности n≥ 31 двоичный символ и коррекции ошибок кратностью tош≥ 3 двоичных символов. Поиск более простых принципов построения СЛБК привел к открытию нового широкого класса групповых линейных блоковых кодов, получивших название циклических кодов (ЦК). Основоположником ЦК является Прейндж. Дальнейшее развитие теория построения ЦК получила в работах Боуза, Чоудхури, Хоквингейма, Файра, Рида-Соломона, Гоппы и др [1 - 4].
Циклические коды являются подклассом в классе линейных блоковых кодов, удовлетворяющих определенным требованиям. Свое название данные коды получили по причине того, что основной операцией построения кодовых последовательностей, обозначаемых как Fi(x), является цикл, а точнее циклическая перестановка двоичных символов разрешенных кодовых последовательностей. Циклическим кодом называется линейный блоковый код, который представляет собой конечное множество, замкнутое относительно операции циклического сдвига кодовых последовательностей, образующих данный код. Для данных групповых кодов Fi,p(x) в результате циклического сдвига кодовых символов разрешенной КП влево или вправо на один, два, (k-1) символ вновь получается разрешенная КП.
|
|
|
В соответствии с теорией высшей алгебры ЦК – циклический код является идеалом в линейной коммутативной алгебре многочлена (полинома) n-го порядка по модулю двучлена xn – 1 над полем коэффициентов. Это означает, что кодовые последовательности ЦК имеют длину n двоичных кодовых символов и описываются полиномами степени (n – 1), в которых коэффициентами при соответствующих степенях формальной переменной, обозначаемой через x, являются двоичные символы кодовой последовательности. Формальная переменная «x» которая носит название оператора Хаффмана или оператора задержки не оказывает никакого влияния на свойства кода. Таким образом, кодовую последовательность ЦК в общем виде можно записать так:
Fi(x) = c n-1 · x n-1 + c n-2 · x n-2 + … + c1 · x1 + c0 · x0, (1.1)
где x – формальная переменная;
n-1, n-2,…,1,0 – показатели степеней, в которые возводятся основания кодов, и одновременно порядковые номера, которые занимают двоичные символы (разряды) кодовой последовательности, начиная со старшего и заканчивая последним;
ci – коэффициенты формальной переменной, которые могут принимать значения или быть равными логической 1 (ненулевой член Fi(x)) или логического 0 (нулевой член Fi(x)). Например,
|
|
|
Fi(x) = 1 · x4 + 0 · x2 + 1 · x1 + 0 · x0 = x4 + x = 10010. (1.2)
Представление кодовых последовательностей в виде полиномов позволяет установить однозначное соответствие между ними и свести действия над кодовыми последовательностями к действиям над полиномами: умножение, сложение, деление и вычитание этих полиномов производится по обычным правилам алгебры, но коэффициенты с одинаковыми показателями степени «x» суммируются по модулю два. Например, Fi(x) = (x3 + x2 +1) · Fj(x)= = (x + 1) = x4 + x3 + x3 + x2 + x + 1 = x4 + (1⊕1) · x3 + x2 + x +1= x4 + 0 · x3 + x2 + +x +1 = x4 + x2 + x + 1.
Уточним сущность понятия циклического сдвига или циклической перестановки двоичных символов кодовой последовательности. Пусть Fi(x) = c n-1 x n-1 + c n-2 x n-2 + … +c1 x1 + c0 x0, то циклический сдвиг на один разряд дает Fi(x) = c n-1 x n + c n-2 x n-1 + … +c1 x1 + c0 x0. Чтобы степень новой кодовой последовательности Fi(x) не превышала (n-1), член c n-1 · x n заменяется единицей, поэтому Fi(x) = c n-2 x n-1 + c n-3 x n-2 + … + c1x2 + c0x0 + c n-1 x 0 [1,2].
Заметим, что запись кодовой последовательности в виде многочлена, а затем перевода ее в двоичную форму записи, не всегда определяет длину кодовой последовательности n. Например, при n=5, многочлен F(x)= =x2+1=101, т.е. n=3, что неверно. В таких случаях надо дописать старшие нулевые символы, т.е. F(x)= x2+1=00101, что дает n=5 двоичным символам. Пусть F(x)= x5 + x3 + x2 + x и n=7. Перевод в двоичную форму записи F(x)=0101110.
|
|
|
Сдвигаем F(x) на один разряд (символ) влево, и получаем F(x)=1011100= x6 + x4 + x3 + x2. Очевидно, что x1(x5 + x3 + x2 + x)= x6 + x4 + x3+ +x2=1011100.
Следовательно, циклическую перестановку двоичных символов разрешенной кодовой последовательности можно рассматривать как умножение F(x) на x при первом сдвиге, на x2 при втором сдвиге и т.д., что можно в общем виде записать или представить так:
(1.3)
Так как при сложении по модулю два двучлен xn-1можно записать как xn=1, то замена xn на 1 в произведении 
дает новый многочлен, коэффициенты которого образуют новую разрешенную кодовую последовательность. Следовательно, в кодовой последовательности, имеющей длину n двоичных кодовых символов, степень полинома не может превышать n-1, так как в противном случае длина кодовой последовательности превысит n, а поэтому xn заменяется логической 1.
Таким образом, можно сделать следующие выводы:
- ЦК – это такой линейный код, который обладает свойством цикличности кодовых последовательностей, т.е. когда каждая разрешенная кодовая последовательность содержит ее циклическую перестановку;
|
|
|
- ЦК относятся к групповым линейным кодам, если они образуются путем умножения каждой последовательности равнодоступного (простого) кода, выраженных в виде многочлена Q(x) с максимальной степенью (k-1), на некоторой полином P(x) степени l=n-k. Приведение подобных членов производится по модулю два; порядок поля кодирования преобразуется с Kраз=2k до Kобщ=2n, но число разрешенных кодовых последовательностей кода при этом остается равным Kраз=2k, и они образуют циклическую подгруппу группы Kобщ=2n, отличающуюся тем, что все элементы подгруппы имеют общее свойство делимости на полином P(x), получивший название образующего или порождающего полинома.
В качестве образующего полинома используются полиномы, обладающие следующими свойствами:
- образующий полином P(x) должен быть делителем двучлена xn+1;
- образующий полином не должен раскладываться на сомножители более низких степеней, и должен делиться без остатка на самого себя и на 1, т.е. на x0;
- максимальная степень образующего полинома должна быть равной l=n-k, т.е. соответствовать количеству проверочных символов используемого кода.
В общем виде ЦК записывается как (n; k; d0), что полностью определяет его параметры.
Параметры циклического кода
ЦК имеют параметры аналогичные параметрам СЛБК, т.е. (n, k, d0), 
; l=n-k, r=(1-R) · 100%, Pош.дек ≤ 
ni · Pki · (1 - Pk)n-i – вероятность ошибочного декодирования, - кратность неправильных ошибок tобн≤ do – 1 – кратность обнаруживающих ошибок.
1) k – количество информационных двоичных символов в кодовой последовательности, и их число может быть равным k=1,2,..;
2) n – длина кодовой последовательности, равная количеству двоичных символов (бит) в кодовой последовательности.
3) 
– скорость передачи кода, характеризует количество избыточных символов приходящиеся на один информации символ. Чем больше 
, т.е. 
1 ( всегда меньше 1), тем эффективнее помехоустойчивый код, так как передается меньше избыточной информации;
4) l=(n-k) – абсолютная избыточность кода, или количество поврежденных символов;
5) r=(n-k) / n = (l/n) · 100% - относительная избыточность кода;
6) d0 ≥ 2t+ 1(2) – кодовое расстояние равно (соответствует) количеству позиций, которыми разнятся (отличаются) две сравнимые кодовые последовательности; сравнивание кодовых последовательностей производится посимвольно (побитно) путем суммирования по модулю два, например:
1001110010
Fi(x) ⊕ Fj(x) = ⊕
0010101100
d = 1 11 1111 = 7, т.е. d=7.
Так как общее количество кодовых комбинаций Kобщ=2n, то общее число кодовых расстояний может быть более чем 2n/2, среди которых dможет быть как максимальным, так и минимальным.
Хэмминг доказал, что не максимальное, а минимальное расстояние характеризует корректирующие свойства помехоустойчивого кода.
Минимальное кодовое расстояние обозначается как d0 или dx (хемминговое расстояние) и равно наименьшему значению d из всей их совокупности. Например, d1=7, d2=5, d3=8,….., di=3, di+1=4,… dj=9, d0= dx=3.
Хемминговое расстояние (dx) чаще всего используется при передаче информации в дискретном канале связи, т.е. при передаче информации на видеочастоте.
7) tисп ≤ 
– кратность неправильных ошибок;
8) tобн≤ dо-1 – кратность обнаруживающих ошибок;
9) Pош.дек ≤ ni · Pki · (1 - Pk)n-i – вероятность ошибочного декодирования при передаче информации по каналу связи с независимыми(случайными) ошибками.
Основные свойства циклического кода
ЦК – являясь дальнейшим развитием СЛБК, обладают всеми их свойствами, а и имеют следующие дополнительные свойства:
1. Сдвиг кодовых символов разрешенной кодовой последовательности влево или вправо на один, два,…, (k – 1) символ вновь приводит к разрешенной кодовой последовательности. Если же при циклическом сдвиге всегда будет получаться кодовая последовательность нового кода, то такой код будет называться квазициклическим; данные коды имеют несколько большую корректирующую способность и сложность реализации, чем ЦК;
2. Разрешенная кодовая последовательность без ошибок Fp′(x) при делении на полином P(x) дает нулевой остаток, т.е. Fp′(x)/ P(x)= R(x)=0 и R(x) не равно 0 – при наличии ошибок;
3. Сумма по модулю два символов двух, трех,…, (k – 1) разрешенных кодовых последовательностей вновь образует разрешенную кодовую последовательность;
4. Двучлен вида xn+1 должен делиться на порождающий полином P(x) без остатка (имеется в виду обычная операция деления многочленов);
5. Если все операции над полиномами (кодовыми последовательностями) проводятся в двоичном поле Галуа (GF(2)), т.е. действия над коэффициентами полиномов осуществляется по модулю два, а умножение полиномов производится по модулю образующего полиномаP(x), то применение указанных операций не приводит к кодовым последовательностям, длина которых больше длины заданного кода, т.е. n;
6. Результат деления двучлена xn+1 на образующий полином P(x) дает полином, который носит название проверочного полинома и обозначается как h(x), т.е. h(x) = (xn+1)/ P(x) и который в теории и практике помехоустойчивого кодирования играет важную роль. Произведение h(x) · P(x)= xn+1=0, а потому полиномы h(x) и P(x) рассматриваются как ортогональные и операция деления (xn+1)/ P(x) используется в основе построения алгоритмов декодирования;
7. Двучлен ЦК вида xn-1 можно разложить на множители
xn - 1= (x-1)( xn-1+ xn-2+…+1),
которые можно использовать в качестве образующих полиномов ЦК с n=const, k=var и do=var.
Например, можно разложить двучлен xn-1=x7-1 на множители вида xn--1=(x-1)(. .)(. .) и определить образующие полинома т параметры кодов.
Из x7-1=(x-1)(x3+x2+1)(x3+x+1) выражения видно, что можно образовать шесть делителей для двучлена x7-1, путем комбинирования полученных трех сомножителей. Следовательно, для двучлена x7-1 существует шесть разных двоичных линейных ЦК со следующими образующими полиномами и параметрами:
P1(x) = (x-1) = (x+1); l=1, n=7, k=6, d0=1 – простой код: l,n,k и tисп (tисп – кратность исправленных ошибок) – изменяются в двоичных символах;
P2(x) = (x3 +x2+1); l=3, n=7, k=4, d0=3, tисп=1;
P3(x) = (x3 +x+1); l=3, n=7, k=4, d0=3, tисп=1;
P4(x) =P1(x) ·P3(x) = (x4 +x3+x2+1); l=4, n=7, k=3, d0=4, tисп=1;
P5(x) =P1(x) ·P2(x) = (x4 +x2+x+1); l=4, n=7, k=3, d0=4, tисп=1;
P6(x) =P1(x) ·P5(x) = (x6 +x5+ x4 +x3+x2+x+1); l=6, n=7, k=1, d0=7, tисп≤3.
ЦК, задаваемые образующими полиномами P1(x), P2(x) и P3(x), относятся к классу ЦК Хэмминга. ЦК, задаваемые полиномами P4(x), P5(x) и P6(x), являются двойственными кодами Хэмминга и называются кодами максимальной длины (КМД).
Известно, что корректирующая способность групповых СБЛК существенно зависит от вида (структуры) образующего полинома, т.е. от количества ненулевых членов данного полинома и его максимальной степени l=n-k. В соответствии с этим можно еще дополнительно отметить следующие свойства ЦК:
8. ЦК, обнаруживающих ошибки:
- ЦК, образующий полином которого имеет более одного члена и не имеет общего множителя x, обнаруживает все одиночные ошибки и любое нечетное число ошибок. Простейшим образующим полиномом ЦК, обладающими данными свойствами, является полином вида P(x)=1+x;
- ЦК, образующий полином которого имеет вид P(x)=1+xc, обнаруживает любое нечетное число ошибок. Доказательство этого утверждения становится ясным, если образующий полином представить в следующим виде P(x)=1+xc=(1+x)×(1+x+x2+…+xc-1).
9. ЦК, обнаруживающих и корректирующих ошибки:
- ввиду того, что полином P(x)= 1+xc нацело делится на 1+x, то согласно предыдущему свойству ЦК обеспечивает обнаружение любого нечетного количества ошибок;
- ЦК, образующий полином которого имеет максимальную степень l=n-k, обнаруживает любой пакет ошибок длиной tпак.обн= l и менее двоичных символов или корректирует пакеты ошибок длиной tпак.исп= l/2 двоичных символов;
- количество пакетов длиной l+1, не обнаруживаемых ЦК, составляет 1/2l-1 части всех пакетов l+1 двоичных символов. Количество пакетов ошибок длиной более l+1, не обнаруживаемых ЦК, составляет часть всех пакетов ошибок длиной от (l+2) до n двоичных символов включительно. Доказательство данных утверждений свойств ЦК можно найти в литературе по теории кодирования.
Дата добавления: 2018-10-27; просмотров: 1296; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!