Основные свойства циклического кода

↑

⇐ ПредыдущаяСтр 2 из 4Следующая ⇒

1.2 Параметры циклического кода

ЦК имеют параметры аналогичные параметрам СЛБК, т.е. (n, k, d₀),  ;  l=n-k,  r=(1-R) · 100%, P_ош.дек ≤ _nⁱ · P_kⁱ · (1 - P_k)^n-i – вероятность ошибочного декодирования, - кратность неправильных ошибок t_обн≤ d_o – 1 – кратность обнаруживающих ошибок.

1) k – количество информационных двоичных символов в кодовой последовательности, и их число может быть равным k=1,2,..;

2) n – длина кодовой последовательности, равная количеству двоичных символов (бит) в кодовой последовательности.

3)  – скорость передачи кода, характеризует количество избыточных символов приходящиеся на один информации символ. Чем больше , т.е.     1 (  всегда меньше 1), тем эффективнее помехоустойчивый код, так как передается меньше избыточной информации;

4) l=(n-k) – абсолютная избыточность кода, или количество поврежденных символов;

5) r=(n-k) / n = (l/n) · 100% - относительная избыточность кода;

6) d₀ ≥ 2t + 1(2) – кодовое расстояние равно (соответствует) количеству позиций, которыми разнятся (отличаются) две сравнимые кодовые последовательности; сравнивание кодовых последовательностей производится посимвольно (побитно) путем суммирования по модулю два, например:

                                             1001110010

                   F_i(x) ⊕ F_j(x) = ⊕

0010101100

                                       d = 1 11 1111 = 7, т.е. d=7.

Так как общее количество кодовых комбинаций K_общ=2ⁿ, то общее число кодовых расстояний может быть более чем 2ⁿ/2, среди которых d может быть как максимальным, так и минимальным.

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

Минимальное кодовое расстояние обозначается как d₀ или d_x (хемминговое расстояние) и равно наименьшему значению d из всей их совокупности. Например, d₁=7, d₂=5, d₃=8,….., d_i=3, d_i+1=4,… d_j=9, d₀= d_x=3.

Хемминговое расстояние (d_x) чаще всего используется при передаче информации в дискретном канале связи, т.е. при передаче информации на видеочастоте.

7) t_исп ≤  – кратность неправильных ошибок;

8) t_обн≤ d_о-1 – кратность обнаруживающих ошибок;

9) P_ош.дек ≤ _nⁱ · P_kⁱ · (1 - P_k)^n-i – вероятность ошибочного декодирования при передаче информации по каналу связи с независимыми(случайными) ошибками.

ЦК – являясь дальнейшим развитием СЛБК, обладают всеми их свойствами, а и имеют следующие дополнительные свойства:

1. Сдвиг кодовых символов разрешенной кодовой последовательности влево или вправо на один, два,…, (k – 1) символ вновь приводит к разрешенной кодовой последовательности. Если же при циклическом сдвиге всегда будет получаться кодовая последовательность нового кода, то такой код будет называться квазициклическим; данные коды имеют несколько большую корректирующую способность и сложность реализации, чем ЦК;

2. Разрешенная кодовая последовательность без ошибок F_p′(x) при делении на полином P(x) дает нулевой остаток, т.е. F_p′(x)/ P(x)= R(x)=0 и R(x) не равно 0 – при наличии ошибок;

3. Сумма по модулю два символов двух, трех,…, (k – 1) разрешенных кодовых последовательностей вновь образует разрешенную кодовую последовательность;

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

5. Если все операции над полиномами (кодовыми последовательностями) проводятся в двоичном поле Галуа (GF(2)), т.е. действия над коэффициентами полиномов осуществляется по модулю два, а умножение полиномов производится по модулю образующего полинома P(x), то применение указанных операций не приводит к кодовым последовательностям, длина которых больше длины заданного кода, т.е. n;

6. Результат деления двучлена xⁿ+1 на образующий полином P(x) дает полином, который носит название проверочного полинома и обозначается как h(x), т.е. h(x) = (xⁿ+1)/ P(x) и который в теории и практике помехоустойчивого кодирования играет важную роль. Произведение h(x) · P(x)= xⁿ+1=0, а потому полиномы h(x) и P(x) рассматриваются как ортогональные и операция деления (xⁿ+1)/ P(x) используется в основе построения алгоритмов декодирования;

7. Двучлен ЦК вида xⁿ-1 можно разложить на множители

xⁿ - 1= (x-1)( x^n-1+ x^n-2+…+1),

которые можно использовать в качестве образующих полиномов ЦК с n=const, k=var и d_o=var.

Например, можно разложить двучлен xⁿ-1=x⁷-1 на множители вида xⁿ--1=(x-1)(. .)(. .) и определить образующие полинома т параметры кодов.

Из x⁷-1=(x-1)(x³+x²+1)(x³+x+1) выражения видно, что можно образовать шесть делителей для двучлена x⁷-1, путем комбинирования полученных трех сомножителей. Следовательно, для двучлена x⁷-1 существует шесть разных двоичных линейных ЦК со следующими образующими полиномами и параметрами:

P₁(x) = (x-1) = (x+1); l=1, n=7, k=6, d₀=1 – простой код: l,n,k и t_исп (t_исп – кратность исправленных ошибок) – изменяются в двоичных символах;                                                                      

           P₂(x) = (x³ +x²+1); l=3, n=7, k=4, d₀=3, t_исп=1;

           P₃(x) = (x³ +x+1); l=3, n=7, k=4, d₀=3, t_исп=1;

           P₄(x) =P₁(x) ·P₃(x) = (x⁴ +x³+x²+1); l=4, n=7, k=3, d₀=4, t_исп=1;

           P₅(x) =P₁(x) ·P₂(x) = (x⁴ +x²+x+1); l=4, n=7, k=3, d₀=4, t_исп=1;

           P₆(x) =P₁(x) ·P₅(x) = (x⁶ +x⁵+ x⁴ +x³+x²+x+1); l=6, n=7, k=1, d₀=7, t_исп≤3.

ЦК, задаваемые образующими полиномами P₁(x), P₂(x) и P₃(x), относятся к классу ЦК Хэмминга. ЦК, задаваемые полиномами P₄(x), P₅(x) и P₆(x), являются двойственными кодами Хэмминга и называются кодами максимальной длины (КМД).

Известно, что корректирующая способность групповых СБЛК существенно зависит от вида (структуры) образующего полинома, т.е. от количества ненулевых членов данного полинома и его максимальной степени l=n-k. В соответствии с этим можно еще дополнительно отметить следующие свойства ЦК:

8. ЦК, обнаруживающих ошибки:

- ЦК, образующий полином которого имеет более одного члена и не имеет общего множителя x, обнаруживает все одиночные ошибки и любое нечетное число ошибок. Простейшим образующим полиномом ЦК, обладающими данными свойствами, является полином вида P(x)=1+x;

- ЦК, образующий полином которого имеет вид P(x)=1+x^c, обнаруживает любое нечетное число ошибок. Доказательство этого утверждения становится ясным, если образующий полином представить в следующим виде P(x)=1+x^c=(1+x)×(1+x+x²+…+x^c-1).

9. ЦК, обнаруживающих и корректирующих ошибки:

- ввиду того, что полином P(x)= 1+x^c нацело делится на 1+x, то согласно предыдущему свойству ЦК обеспечивает обнаружение любого нечетного количества ошибок;

- ЦК, образующий полином которого имеет максимальную степень l=n-k, обнаруживает любой пакет ошибок длиной t_{пак.обн}= l и менее двоичных символов или корректирует пакеты ошибок длиной t_{пак.исп}= l/2 двоичных символов;

- количество пакетов длиной l+1, не обнаруживаемых ЦК, составляет 1/2^l-1 части всех пакетов l+1 двоичных символов. Количество пакетов ошибок длиной более l+1, не обнаруживаемых ЦК, составляет часть всех пакетов ошибок длиной от (l+2) до n двоичных символов включительно. Доказательство данных утверждений свойств ЦК можно найти в литературе по теории кодирования.

Познавательные статьи:



Техника нижней прямой подачи мяча

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

Стандарт Порядок надевания противочумного костюма

Общеразвивающие упражнения без предметов