4.3 Циклічні коди при побудові РТС ПІ



Раніше n-розрядні двійкові послідовності розглядалися як вектори деякого ліній но го простору Vn. Тепер всяку впорядковану двійкову послідовність довжини n позна чимо через [2]

a = {(0,(1,...,(i,...,(n(1}, (4.12)



і будемо її розглядати як набір коефіцієнтів полiнома

a(x) = (0+(1x1+...+(ixi+...+(n(1xn(1. (4.13)



Оскільки (і дорівнюють 0 чи 1, то очевидно, що при такому уявленні степінь кож но го полiнома (кодового слова) не перевищує (n–1).

Означення. Лiнійний (n, k)-код називається циклічним, якщо разом з кожним ко до вим словом {(0,(1,...,(i,...,(n(1} він містить також його циклічну перестановку {(n(1,(0,(1,...,(i,...,(n(2}.

Суттєвість циклічної перестановки полягає в тому, що останній символ кодової ком бiнації займає місце першого, перший – другого і т. д. до тих пір, доки перед ос тан ній символ не займе місце останнього. Якщо циклічній обробці підлягає дозволена ко до ва комбiнація, то внаслідок цієї операції з'явиться нова дозволена кодова комбiнація, на приклад, якщо у вигляді дозволеної кодової комбiнації обрана а1 = {011}, то до зво ле ними кодовими комбінаціями будуть також а2 = {101} і а3 = {110}.

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

Подання кодових слів у вигляді полiномів або у вигляді елементів лiнійного век тор ного простору дозволяє використовувати для побудови кодів добре розвинений апа рат теорії алгебри. Звідси іде розвиток алгебраїчної теорії кодування (1-7(.

Надалі, при побудові циклічних кодів доводяться елементарні відомості з теорії ал гебри і, зокрема, фундаментальне поняття алгебраїчного поля.

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

Під операцією над множиною мають на увазі відповідність, при якій кожній па рі елементів відповідає однозначно визначений елемент цієї множини. Елементи мно жини звичайно позначають літерами а, b, c, d,..., множини через M = {а, b, c, d,...}, а операцію символічно записують у вигляді с = а( b. При операції додавання пи шуть с = а+b, а при операції множення – с = аb. Операції віднімання та ділення зви чай но не розглядаються як основні, бо вони є оберненими, відповідно для додавання та множення.

Нарешті, визначимо поняття мінімального полiнома m(х) над полем GF(2m) і ви зна чимо основні його властивості [1(6].

Мінімальним полiномом елемента а(GF(2m) називається незвідний над GF(2) полiном m(х) мінімального степеня, такий, що m(а) = 0. Одна із властивостей полiнома m(х) полягає в тому, що він не має кратних коренів, причому, якщо а(GF(2m) є його ко ренем, то елементи а2i, i = 1,2,3,... також є його коренями.

Для побудови двійкових циклічних кодів широко використовують розкладення дво члена F(x) = x2m(1(1 на добуток двійкових мінімальних полiномів, тобто

ion.2 HYPER14HYPER15, (4.14)

де І = {i} – деяка множина індексів.

Розкладення (4.14) засновано на тому, що у силу співвідношення а2m(1 = 1, спра вед ливого для будь-якого ненульового елемента а(GF(2m), всі ненульові елементи GF(2m) є простими коренями двочлена F(x) = x2m(1(1.

Розглянемо приклад такого розкладення. Нехай m = 4, тоді F(х) = x15(1. Всіма ко ренями цього полiнома є ненульові елементи поля GF(2m). В яко сті елемента а вибираємо первісний елемент ( поля GF(2m). Позначимо через mi(x) мінімальний полiном над GF(2) для (i, i = . Із зазначеної вище властивості мінімального полiнома маємо

. (4.15)



З таблиць незвідних полiномів над полем GF(2) [2] знаходимо



. (4.16)

Таким чином

, (4.17)

де множина індексів І= {0, 1, 3, 5, 7}.

Розкладення двочлена F(x) = на добуток мінімальних полiномів над GF(2) проводиться аналогічно для інших m. При цьому мінімальні полiноми mi(х) можуть бути взяти з таблиць у [2].

Для опису циклічного коду розіб’ємо множину індексів І у (4.17) на дві непересічні підмножини Іg та Іh так, що І = Іg ( Іh і уведемо два полiноми

g(x) = = g0+g1x+...+grxr, (4.18)

та

h(x) = = h0+h1x+...+hkxk. (4.19)

Полiноми g(x) та h(х) називають відповідно породжуючим та перевірочним. Оче вид но, що g(х)h(х) = F(х) = .

Лiнійним циклічним кодом є множина всіх тих і тільки тих полiномів а(х) степеня менше від 2m(1, кожний з яких ділиться на полiном g(x).

Лiнійний циклічний код можна задати також за допомогою породжуючої матриці

. (4.20)

Матриця G має n = 2m(1 стовпців та k = n–r рядків, причому її ненульові елементи є коефіцієнтами породжуючого полiнома g(х).

Зазначимо, що для циклічного коду число інформаційних символів k дорівнює сте пеню перевірочного полiнома, а число перевірочних символів r = n–k дорівнює степе ню породжуючого полiнома.

Для прикладу побудуємо циклічний код над GF(2) довжини n = 15 з кількістю пе ре вірочних символів r = 8. Розкладення двочлена х15(1 виражається формулою (4.17). При цьому множина індексів І має вигляд І = {0, 1, 3, 5, 7}. Цю множину розіб’ємо на дві підмножини: Іg = {1,3} і Іh = {0,5,7). Згідно з (4.18) маємо g(x) = m1(x)m3(x) = x8+x7+x6+x4+1, звідки витікає, що g0 = g4 = g6 = g7 = g8 = 1, інші gi = 0, i = {1, 2, 3, 5, 9, 10, 11, 12, 13, 14}. Таким чином, для розглядаємого прикладу породжуюча матриця має вигляд:

.



Кодування несистематичним циклічним кодом {Cj} можна просто здійснити за правилом Cj = UjG, де Uj = {uj,i}, i = ( вектор-рядок інформаційних символів.

Всі рядки породжуючої матриці G, як видно з (4.20), лiнійно незалежні.

Множина кодових слів (потужність) лiнійного циклічного (n, k)-коду – це множина всіх можливих лiнійних комбінацій рядків матриці G, отож потужність (n, k)-коду J = 2k.



РА-071.050901.006 ПЗ



Арк.



Дата



Підпис



№ докум.



Арк.



Змн.



РА-071.050901.006 ПЗ



Арк.



Дата



Підпис



№ докум.



Арк.



Змн.



РА-071.050901.006 ПЗ



Арк.



Дата



Підпис



№ докум.



Арк.



Змн.



РА-071.050901.006 ПЗ



Арк.



Дата



Підпис



№ докум.



Арк.



Змн.



РА-071.050901.006 ПЗ



Арк.



Дата



Підпис



№ докум.



Арк.



Змн.