Тема 14-15. Недвійкові  коди

 

 

Недвійкові коди за аналогією з двійковими можна поділити на такі: первинні коди; коди, що виявляють помилки;  коди, що виправляють помилки.

Недвійкові  первинні  коди  використовуються у телекомунікаційних системах та мережах і системах телемеханіки. Далі наведені вирази для розрахунку кількості  N 0  кодових комбінацій, які можна отримати при побудові таких первинних кодів ( вони пов’язані з відповідним розділом математики, який називається комбінаторикою ).

Код на перестановки:

N0= q!,  q = n ;

тут і далі  q – потужність алфавіту коду,  n – довжина кодової ком-бінації.

Код на певне число розміщень:

N=  =  q! / ( q – n )! q > n .

Код на певне число сполучень:

N=  =  q! / [ ( q – n )! n! ] ,  q > n .

Код на всі сполучення:

N 0 = q ,   q  n .

Змінно-якісний код:

N0 = q – 1 ) – 1 .

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

Код з перевіркою за mod q  будується за аналогією з двійковим кодом з перевіркою на парність, але з тією різницею, що виконується доповнення кодової комбінації первинного q-ічного коду перевіроч-ним елементом таким чином, щоб сума усіх елементів дорівнювала нулю за  mod q. Значення перевірочного елемента у даному разі визначається різницею між  q та сумою значень всіх елементів первинної кодової комбінації  за  mod q .

Такий код має незначну надмірність  R = 1 / ( k + 1)  і дозволяє виявити наявність помилок у кодовій комбінації, якщо сума усіх елементів  ( інформаційних та перевірочного )  за  mod q  відрізняється від нуля.

Код з простим повторенням  є аналогом двійкового коду з простим повторенням ( див. розділ 7 ), в основу якого покладено просте повторення первинної кодової комбінації. Алгоритм побудови коду має вигляд:

bi =  ai,  i  [ 1, k ] ,

де  ai – інформаційний елемент, що знаходиться на  i-ій позиції інфор-маційної частини кодової комбінації; bi – перевірочний елемент, що знаходиться на i-ій позиції перевірочної частини кодової комбінації;    k – кількість інформаційних елементів.

Надмірність коду  R = 0,5. Код дозволяє  виявити всі помилки, за винятком деяких помилок на однакових позиціях в інформаційній та перевірочній частинах коду.

Незвідний змінно-позиційний код НЗЗПК  задовольняє таким умовам:

кожна кодова комбінація містить однакову кількість елементів, які передаються послідовно;

кожний елемент кодової комбінації містить  m  позицій алфаві-ту  потужністю  q ;

сусідні елементи кодової комбінації повинні відрізнятися хоча б однією позицією;

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

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

Послідовність побудови  НЗЗПК:

береться  m  символів з  q  позицій алфавіту;

визначається кількість сполучень позицій за заданим числом позицій у кожному сполученні;

вся кількість сполучень позицій розбивається  на  n  груп, де  n – кількість елементів кодової комбінації  ( довжина коду ),  і  кожна група взаємно однозначно закріплюється за елементом кодової комбінації;

утворюються кодові комбінації з  n  елементами за правилом: для кожного елемента  беруться сполучення позицій із закріпленої за даним елементом групи сполучень позицій.

За методом побудови кодових комбінацій багатопозиційні НЗЗПК поділяють на такі класи:

без розділення алфавіту коду на групи;

з розділенням алфавіту коду на  v  груп, кожна з котрих  має  qi символів.  

Останній клас, у свою чергу, поділяють на НЗЗПК, кожний елемент якого містить  m  позицій, які беруться з різних груп сполучень, і НЗЗПК, кожний елемент якого містить  m  позицій, які беруться з однієї групи сполучень.

Кількість N 0  кодових комбінацій для НЗЗПК без розділення  алфавіту коду на групи

–  у  разі, коли всі сполучення позицій розподілені між n групами сполучень порівну        

N= ( / n ) n ;

–  у  разі, коли вся кількість сполучень розподіляється між групами сполучень не нарівно через остачу деякої кількості сполучень

N0  =  ( – Q ) n – Q ´ ( – Q + n ) n n ,

де  Q  –  остача від ділення /n,  що є цілим додатним числом.

Для  НЗЗПК  з  розділенням алфавіту коду  на  v  груп з однако-вою кількістю  q / v  позицій у кожній групі та за умов, що кожний кодовий елемент містить  m  позицій, які вибираються з різних груп ( v ³  m )  кількість  кодових комбінацій

N=  ( l m / n ) n ;

якщо ж для кожного кодового елемента  m  різних позицій  вибираються із однієї групи  l ³ m,= n ),  то

N=  () n .

Недвійкові коди, що виправляють помилки, поділяють  на блокові і неперервні. Блокові  q - коди, як і аналогічні двійкові,  призначені для  виправлення, головним чином, незалежних помилок. Однак,  на  відміну  від  двійкових, один  елемент  недвійкового коду несе

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

Код з багатократним повторенням застосовується при передачі інформації по каналам з високим рівнем завад. Цей код містить k інформаційних елементів, а кількість r перевірочних елементів залежить від числа  m  повторень, причому кожний перевірочний елемент збігається з відповідним йому інформаційним. Таким чином довжина кодової комбінації:  n =  k + k m  =  k ( 1 + m ). Алгоритм побудови коду:

b=  ai,  i  [ 1, k ] ,  j  [ 1, m ] ,

де  ai – інформаційний елемент, що знаходиться на  i-ій позиції інфор-маційної частини кодової комбінації;   b– перевірочний елемент, що знаходиться на  i-ій позиції  j-го повторення.

Процедура виявлення помилок у прийнятій кодовій комбінації полягає у порівнянні однойменних інформаційних і перевірочних розрядів. Їх незбіг говорить про наявність помилок у прийнятій комбінації. При виправленні помилок у комбінації застосовується мажоритарний принцип виправлення для кожного інформаційного елемента, тобто “голосування за більшістю”, коли за істинне значення приймається те, яке частіше зустрічається у цьому інформаційному і відповідних йому перевірочних елементах.

При  m - кратному повторенні надмірність коду   R  = m / ( 1 + m ). 

Код  з  простим  повторенням  та  перевіркою  за  mod q є ко-мбінованим використанням двох недвійкових кодів, що виявляють помилки: з простим повторенням та перевіркою за  mod q. Це дає можливість одержати код, що виправляє однократні помилки. В основу коду покладене просте повторення первинної кодової комбінації з подальшим доповненням кодової комбінації перевірочним елементом, який отримують як доповнення до суми елементів первинної кодової комбінації до значення потужності  q  алфавіту  коду ( основи коду ). Значення перевірочного елемента визначається різницею між  q та сумою значень всіх елементів первинної кодової комбінації  за  mod q.

Код дозволяє  виправити тільки всі однократні помилки. При цьому місце помилки визначається в декодері простим співставленням інформаційної та повтореної частин прийнятої кодової комбінації. Незбіг значень елементів у деякому розряді вказує на помилку у цьому розряді. Для визначення, в якій частині кодової комбінації виникла помилка: в інформаційній чи повтореній, виконують перевірку за mod q кожної частини комбінації окремо. При цьому у перевірку за mod q повинен входити і перевірочний елемент, який міститься у кінці кодової комбінації. При перевірці отримуємо контрольний елемент, значення якого при відсутності помилки буде дорівнювати нулю, а при виникненні однократної помилки – буде  відрізнятися від нуля.

При виникненні помилки в інформаційній частині прийнятої кодової комбінації її виправляють. Виправлене значення інформа-ційного елемента отримують як різницю за  mod q  між спотвореним інформаційним елементом та одержаним при перевірці у декодері контрольним елементом.

Надмірність коду   R = ( k + 1 ) / ( 2 + 1 ).

Узагальнений  код  Хеммінга  УКХ  є найбільш поширеним з недвійкових кодів такого класу. Код призначений для виправлення однократних помилок у термінах недвійкової арифметики.

Перевірочна матриця  УКХ  має розмір  r ´ n: 

H  =  [ h i j ] ,  = 1, 2, 3,…, ;   j = 1, 2, 3,…, ;

де  r – кількість перевірочних елементів, n – довжина кодової ком-бінації,  i – номер рядка,  j – номер стовпця. Стовпці  матриці  Н  повинні бути ненульовими і різними та, крім того, всі вони повинні мати однакову першу ненульову компоненту  d . Оскільки  d  відповідає умові   1 d  q – 1, число її можливих значень дорівнює   q – 1. Звідси, виключивши нульовий вектор-стовпець, отримаємо число вектор-стовпців у матриці  Н  ( отже і максимальну довжину   nmax   кодової комбінації ) 

          nmax  =  ( q r – 1 ) / ( q – 1 ) .                                 ( 10.1 )

При побудові матриці  Н  виявляється,  що  r  перших її вектор-стовпців, кожний з яких містить єдину ненульову компоненту d , утворюють діагональну підматрицю розміру  r ´ r . Ця обставина вказує на зручні позиції для розміщення  r  перевірочних елементів у комбінації.

Загалом макет кодової комбінації  X  можна подати як:

              X  =  b1 b 2 b 3…br  a1a2 a3…ak ,                            ( 10.2 )

де   a, b –  q-ічні  відповідно інформаційні та перевірочні елементи кодової комбінації.

З розв’язання фундаментального матричного рівняння систематичних кодів

H X  Т =  0

відносно перевірочних елементів   b,  випливає

  b ,                       ( 10.3 )

де   X  Т    транспонований  вектор  X  .

Показане у (10.1) розміщення  перевірочних елементів не є єдино можливим, але воно забезпечує мінімальний обсяг обчислень при кодуванні та декодуванні. При цьому вираз  (10.2)  дає оптимальний алгоритм кодування. Кодовий вектор (10.1) поелементно передається у канал зв’язку у вигляді певних сигналів, де він може бути спотворений завадою. Фізичні явища процесу спотворення сигналів не мають значення, тому що з алгебраїчних міркувань його доцільно подати як  Y = X  Å E ( mod q ),  де  Y  – спотворений  кодовий вектор на виході тракту передачі;  E  –  вектор помилки з єдиною ненульовою компонентою  е  ( у припущенні однієї помилки ).

Процедура декодування містить у собі, як перший крок, за аналогією з двійковим кодом Хеммінга, обчислення  r-компонентного перевірочного синдрому: S  = H Y  Т =  L e . Вектор  S  являє собою помножений на значення помилки  е  ( 1 е  q – 1 )  стовпець  L  перевірочної матриці Н, що відповідає позиції спотвореного елемента у кодовому векторі Y . Його називають  локатором місця помилки . Оскільки  всі вектор-стовпці у  Н  мають першу ненульову компоненту, що дорівнює  d , то у  S  перша ненульова компонента  s1  завжди буде  s1 = d e. Це обумовлює другий крок процедури декодування – визначення  значення  помилки:

                                      e   s1d  – 1  =  s/d  .                                     ( 10.4 )

З  визначення  S  L e  випливає третій крок процедури декодування    знаходження локатора місця помилки:

   L    S / e ,                                             ( 10.5 )

тобто кожна компонента вектора  S  ділится на значення помилки  e.

На четвертому кроку процедури декодування  шляхом упорядкованого перебору стовпців перевірочної матриці   H   і порівняння кожного з локатором  L  по збігу визначають позицію спотвореного елемента у кодовій комбінації. П’ятим і останнім кроком декодування є виправлення помилки, яке виконується  відніманням за mod q  значення помилки  е  від значення спотвореного елемента, знайденого у  Y  за його локатором  L . Після цього спотворений елемент  у прийнятій кодовій комбінації замінюють результатом віднімання  і, виключивши перевірочні елементи, подають одержувачу інформаційну частину кодової комбінації.

Надмірність коду   = n .

Зазначимо, що недвійкові коди прийнято ділити на дві великі групи: коди з простою основою, коли  q  є простим числом, і коди з основою  q, що  розкладається. Найбільший практичний інтерес має окремий випадок таких кодів при q  =  2, символи якого  мають інформаційну ємність  h  біт  і  можуть бути співставленні з усіма  h-розрядними двійковими числами. Вибір  q  впливає на визначення операцій додавання, віднімання, множення і ділення, які використовуються у процедурах кодування і декодування. Якщо основа – просте число, зручно використати апарат обчислень за модулем простого числа. Якщо ж  q  =  2h, то необхідно звернутися до алгебраїчного апарату обчислень за модулем незвідного полінома. Символи коду при цьому ставлять у відповідність елементам скінченого поля порядку  q , а саме GF(q).

У табл. 10.1.1 та 10.1.2 наведені результати операцій додавання та множення у скінченому полі  GF ( 2)  =  GF ( 8 ). Операцію додавання  +  двох елементів виконано як порозрядне додавання за mod 2 їх двійкових еквівалентів з подальшим  записом цього числа у вісімковому поданні. Операція множення ´ виконується як множення двох поліномів, що відповідають елементам поля,  за модулем незвідного полінома степеня   h = 3   ( у  даному  разі  х3Å x Å 1 ) .

 Таблиця 10.1.1                                        Таблиця 10.1.2

+

0

1

2

3

4

5

6

7

 

´

0

1

2

3

4

5

6

7

0

0

1

2

3

4

5

6

7

 

0

0

0

0

0

0

0

0

0

1

1

0

3

2

5

4

7

6

 

1

0

1

2

3

4

5

6

7

2

2

3

0

1

6

7

4

5

 

2

0

2

4

6

3

1

7

5

3

3

2

1

0

7

6

5

4

 

3

0

3

6

5

7

4

1

2

4

4

5

6

7

0

1

2

3

 

4

0

4

3

7

6

2

5

1

5

5

4

7

6

1

0

3

2

 

5

0

5

1

4

2

7

3

6

6

6

7

4

5

2

3

0

1

 

6

0

6

7

1

5

3

2

4

7

7

6

5

4

3

2

1

0

 

7

0

7

5

2

1

6

4

3

 

Для виконання операцій додавання і множення у скінченому полі GF ( 16 ) зручніше користуватися  адитивною та мультипліка-тивною формами запису десяткового числа, які подані у табл. 10.1.3. Операції виконуються на основі модульного полінома  Р ( х )  =  =  x 4 Å  x Å 1, який задає розширювальне рівняння  x 4 =  x  Å 1  або b  4 =  b  Å 1 . В першій колонці цієї таблиці наведені елементи поля  GF ( 16 ) у десятковому поданні ( ці номерні записи можна розглядати як імена окремих елементів ). У другій колонці наведено подання елементів поля  GF ( 16 )  у формі двійкового вектора ( сукупності коефіцієнтів двійкового поліному – остачі від ділення на  Р ( х ) = x 4 Å  x Å 1 )  з природнім розподілом вагів  23 22 21 20. У третій колонці наведено мультиплікативну форму подання елементів поля  GF ( 16 )  у вигляді степенів примітивного елемента   bGF ( 16 ) .

Можна замінити будь-який високий степінь  b  на такий, що не перевищує 14, якщо мати на увазі, що b15  = 1, b16  b , b17  b2, b18  b, . . .

Таблиця 10.1.3

Елементи

GF ( 16 )

Подання

у формі

 вектора

23 22 21 20

b j

Адитивна  форма abÅ bb2  Å cb1Å db0, a,b,c,dΠ{ 0,1 } у базисі

b b b1 b0

 

 

0

0 0 0 0

0 = 1 /b  ¥

0

 

1

0 0 0 1

b0= 1

1

 

2

0 0 1 0

b1

b

 

3

0 0 1 1

b4

b  Å 1

 

4

0 1 0 0

b2

b2

 

5

0 1 0 1

b8

b Å 1

 

6

0 1 1 0

b5

b2 Å b

 

7

0 1 1 1

b10

b2 Å b  Å 1

 

8

1 0 0 0

b3

b3

 

9

1 0 0 1

b14

b3 Å 1

 

10

1 0 1 0

b9

b3 Å b

 

11

1 0 1 1

b7

b3 Å b  Å 1

 

12

1 1 0 0

b6

b3 Å b2

 

13

1 1 0 1

b13

b3 Å b2 Å 1

 

14

1 1 1 0

b11

b3 Å b2 Å b

 

15

1 1 1 1

b12

bÅ b2 Å b  Å 1

 

Виконаємо, наприклад, множення елементів 13 та 15 поля  GF ( 16 )  за допомогою степенів  b :

13 ´ 15 = b13 ´ b12  b25 = b10´ b15 = b10´ 1 = b10 =  7.   

Код Ріда-Соломона ( РС  ) застосовується для передачі інфор-мації по каналах з високою інтенсивністю завад, за яких виникають помилки кратністю два і більше та пачки помилок. Коди РС розглядають як такий випадок кодів БЧХ, коли поле локаторів збігається з полем його елементів. Тобто, якщо поле елементів  GF ( q )  БЧХ - коду має  q  окремих елементів ( потужність поля q ), а поле його локаторів  GF ( ql )  має  ql  елементів і є  l - розширенням поля елементів  GF ( q ),  то у  РС - коді  і  елементи коду  і  їх локатори знаходяться у одному полі і належать  GF ( q ). Інакше кажучи,  РС - код – це вироджена форма  БЧХ - коду,  у  якого   l = 1.

Довжина блока  РС - коду  n = q – 1,  де  q – потужність алфавіту ( основа )  коду.

РС - код, як і БЧХ - код, може задаватися твірною чи перевірочною матрицями або твірним чи перевірочним поліномами. Найбільш поширений спосіб побудови РС - коду на основі твірного поліному Р(х). Перевірочну матрицю Н часто використовують для вивчення деяких властивостей  РС - коду та його зв’язку з систематичними кодами.

Твірний поліном  Р(х) коду  РС, що виправляє  s  помилок, є добутком   r   мінімальних поліномів для спектру елементів  з  GF ( q ),  де r  =  2 s  –  кількість перевірочних елементів у блоці коду:

      Р(х) = ( x – b  j ) ( x – b  j + 1 ) ( x – b  j + 2 )… ( x – b  j + – 1 ) ,             ( 10.6 )

де  b  jb  j + 1b  j + 2,…, b  j + – 1   спектр твірних коренів поліному Р(х).

Степінь такого поліному дорівнює числу перевірочних елементів  r  =  2 s.

Для спрощення побудови  РС - коду часто вибирають  j = 1 та одержують:

         Р(х) = ( x – b  1 ) ( x – b  2 )… ( x – b  )  = .       ( 10.7 )

Перевірочний поліном  Н(х)  РС - коду одержують як частку від ділення  ( x q – 1  1 )  на  Р(х).

Мінімальна кодова відстань  РС - коду  d 0  r + 1 = 2 + 1.

Надмірність коду   R  =  r / n  =  2 s / ( q – 1 ).

Найбільш просто коди  РС  реалізуються для алфавіту потужністю  q = 2 h,  тобто коли  q =  4, 8, 16,… .У цьому випадку операції віднімання співпадають з операціями додавання, тому скрізь можна знак    “ замінити на “ + “, зокрема у виразах  ( 10.6 )  та  ( 10.7 ).

Декодування кодів РС виконується у відповідності з загальними принципами циклічних кодів . У разі виправлення помилок одержують значення локаторів = b  j , що відповідають спотвореним елементам, і значення помилок для кожного спотвореного елемента. Виправлення помилок виконують відніманням від значення відповідного елемента значення помилки. Для полегшення виконання операцій результати додавання і множення у полі  GF ( 16 )  наведені табл. 10.3.

Недвійкові ітеративні коди  мають більш високу здатність виявляти помилки у порівнянні з аналогічними  двійковими ітератив-ними кодами. При  q > 2  зростає обсяг інформації, що передається, завдяки тому, що кількість інформації, яка міститься в одному елементі кодової комбінації, визначається потужністю  q  алфавіту коду. У таких ітеративних кодах для кодування по рядках і стовпцях використовують недвійкові коди з перевіркою за  mod q. Виявлення помилок виконується за аналогією з двійковим кодом – порівнянням перевірочних елементів кожного рядка ( стовпця ), поданих з каналу до декодера елементів коду, та одержаних у декодері шляхом обчислень.

Виправлення спотвореного елемента виконують наступним чином. Якщо не виконується перевірка для  i-го рядка та  j-го стовпця, то елемент, що знаходиться на перетинанні i-го рядка та  j-го стовпця, замінюють елементом, який є сумою за  mod q  даного прийнятого елемента ( помилкового ) та перевірочного елемента i-го рядка ( або j-го  стовпця ),  який був одержаний у декодері.

При виникненні декількох помилок у одному рядку ( стовпці ), помилки виправляють послідовно для тих стовпців  ( рядків ), де вони є  поодинокими.

степенів додаються за модулем 2. Так, ( x 4 Å x 3 Å x  Å 1 ) x Å 1 )  =  x 5 Å x 4 Å x 2 Å x Å Å x 3 Å  x Å 1 =  =  x 5 Å  x 3 Å  x 2 Å 1.

Ділення також виконується як звичайне ділення поліномів, при цьому операція віднімання співпадає з операцією додавання  Å. Наприклад,   x 5 Å x 3 Å  x 2  Å 1 ) / ( x Å 1 )  =  х 4 Å  х 3  Å х  Å 1.

До циклічних належать лінійні блокові ( n, ) - коди, у яких циклічний зсув елементів будь-якої дозволеної комбінації призводить до виникнення також дозволеної комбінації, що належить до даного коду. Така циклічна перестановка з’являється завдяки помноженню полінома даної комбінації на  x . Щоб степінь полінома не перевищував  n – 1, член  n замінюється одиницею.

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

Циклічні коди з  d min  = 3 . Розрізняють алгебраїчні та матричні способи побудови циклічних кодів. Існують три алгебраїчні спо­соби  побудови кодових комбінацій циклічного коду, які випливають з виразу

                              ,                              ( 9.1 )

де  r – кількість перевірочних розрядів у комбінації циклічного коду; Q ( x ) – поліном первинної кодової комбінації; P x ) – твірний полі-ном; C ( x ) – частка від ділення того степеня, що і Q ( x );  R ( x ) – ос­тача від ділення, яка має степінь, не більший за  r – 1. З виразу  ( 9.1 )  можна одержати три способи побудови циклічного коду :

F( x )  =  x r Q ( x Å R ( x ) ;

F( x )  =  C ( x P ( x ) ;

F( x )  =  Q ( x P ( x ) ,

де  F ( x )  –  комбінація циклічного коду.

Перші два способи дають один і той же роздільний циклічний код, тобто  F( x )  =  F( x ), у якому розташування інформаційних і перевірочних елементів буде підпорядковано правилу:  k  старших роз-рядів комбінації  –  інформаційні, решта  n – r  розрядів  –  пере-вірочні. Третій спосіб використовується для побудови нероздільного циклічного коду, де інформаційні і перевірочні елементи в комбінаціях не відокремлені одні від одних, що ускладнює процес декодування.

Деякі твірні поліноми для циклічних кодів наведені у табл. 9.1.

                                                                                 Таблиця 9.1

Кількість

перевірочних

еле­ментів  r

 

Твірний    поліном    P ( x )

Двійковий

за­пис

полінома

3

x3x1

1011

3

x3x21

1101

4

x4x1

10011

4

x4x31

11001

5

x5x21

100101

5

x5x31

101001

5

x5x3x2x1

101111

5

x5x4x2x1

110111

6

x6x5x41

1110001

8

x8x7x6x5x2x1

111100111

9

x9x5x31

1000101001

Очевидно, що  F(x) повинен  ділитися на  P(x)  без остачі. На цьому і грунтується перевірка кодової комбінації на наявність помилок при прийомі. Якщо прийнята комбінація  F*(x)  ділиться на  P(x)  без ос­тачі, вона визнається безпомилковою. Якщо після ділення залишається ненульова остача, це свідчить про наявність помилки у прийнятій комбінації циклічного коду.

Для виправлення помилки можна скористатися методом гіпотез. Цей метод грунтується на послідовній побудові гіпотез про помилки у молодшому розряді прийнятої кодової комбінації, потім, якщо гіпотеза не підтверджується, у другому розряді і так далі, поки гіпотеза не підтвердиться і остача від ділення  F*(x)ÅE(x), де E(x) – поліном по­милки, на  P(x)  не дасть нульовий результат. Це означає, що F(x) = F*(x)ÅE(x)  і  помилка виправлена.

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

За першим способом будується твірна матриця

G   .

За другим способом також будується твірна матриця циклічного коду, але на відміну від першого, у якості рядків такої матриці викори­стовують усі можливі комбінації коду, що мають тільки одну одиницю в інформаційній частині; перевірочні елементи для таких комбінацій можна ви­значити за допомогою першого алгеб­раїчного способу побудови коду.

Третій матричний спосіб побудови циклічного коду грун­тується на одержанні перевірочної матриці за допомогою викори­стання перевірочного полінома, який визначається за формулою:

Н(х)=(xn1)/P(x),

де  n=2r–1. При цьому, перевірочна матриця має вигляд:

H  =     .

Процес кодування і декодування за допомогою твірної або перевірочної матриць циклічного коду провадиться аналогічно даному процесу у  двійковому груповому коді, викладеному  в  розділі  8.

Циклічні  коди з  d min 4  можуть виявляти одно-, дво- і три­кратні помилки. Для збільшення кодової відстані до d min = 4 кількість перевірочних елементів у кодовій комбінації такого коду має бути на один більшою, ніж у коді  з  d min = 3. Твірний поліном  P(x)(d=4) такого коду визначається як добуток твірного поліному  P(x)(d=3) циклічного коду,  який має  d min = 3,  на поліном  xÅ1), тобто :

P(x)(d=4)= P(x)(d=3)(x1).

Процедура кодування  і  декоду­вання залишається такою ж,  як і для циклічного коду  з  d min = 3.

Вкорочені  циклічні  коди  будуються за аналогією з двійковими груповими кодами на основі побудови твірної або перевірочної матриць  ( див. розділ  8 ).

Коди Боуза-Чоудхурі-Хоквінгема  ( БЧХ ) є різновидом циклічних кодів з кодовою відстанню  d min  3. Коди БЧХ дозволяють виявляти і виправляти будь-яку кількість помилок у залежності від мінімальної кодової відстані. При кодуванні задаються кількістю по­милок, яку слід виправити, або кодовою відстанню і загальною кількістю елементів у кодовій комбінації n. Кількість інформаційних елементів  k  та перевірочних елементів  r  визначається при побудові коду.

Так  довжина кодової комбінації  n  у  кодах  БЧХ  визначається  з виразів  [24]:

   = 2h–1,   або   = (2h–1)/g,            ( 9.2 )

де  h – ціле число;   g  – непарне додатне число, при діленні на яке одержуємо  n  цілим непарним числом. Таким чином,  n  може бути тільки непарним числом. Тобто, керуючись виразом ( 9.2 ), визначаємо, що кількість елементів у комбінаціях коду БЧХ може дорівнювати 3, 7, 15, 31, 63, 127, 255, 511, 1023  тощо.

Кількість перевірочних елементів коду відповідає співвідношенню

£  h d min – 1 ) / 2 ,                                   ( 9.3 )

звідки кількість інформаційних елементів

         k ³ ( 2 h – 1 ) – h d min – 1) / 2 .                         ( 9.4 )

Твірний поліном коду БЧХ визначається як добуток так званих мінімальних поліномів  Мi(x),  із непарними індексами:

           P(x) = M1(x)M3(x)...MV(x),                       ( 9.5 )

де   =  d min – 2 . Можна пересвідчитись, що кількість мінімальних поліномів  у  добутку  ( 9.5 )  дорівнює максимальній кількості  s  помилок,  які  гарантовано  виправляються  кодом .

У таблиці  9.2  наведені основні параметри деяких кодів  БЧХ .

                                                                     Таблиця  9.2

n

k

r

d min

Твірний  поліном  Р8

7

4

3

3

13

15

11

4

3

23

 

7

8

5

721

 

5

10

7

2467

31

26

5

3

45

 

21

10

5

3551

 

16

15

7

107657

 

11

20

11

5423325

 

6

25

15

313365047

63

57

6

3

103

 

51

12

5

12471

 

45

18

7

1701317

 

39

24

9

166623567

 

36

27

11

1033500423

 

30

33

13

1574641656547

 

24

39

15

17323260404441

 

18

45

21

1363026512351725

 

Подані в таблиці параметри були визначені у відповідності з вик­ладеною вище методикою. Для зручності запису твірні поліноми Р(х) подані у вісімковій системі числення  P) . Щоб одержати твірний поліном у звичайному вигляді, тобто у тій формі, яка використовується для побудови кодів БЧХ, треба перевести кожну вісімкову цифру  у  двійковий трибіт. Так, наприклад,  Р8 =  45  запишеться двійковими числами: 4 – 100  та  5 – 101. Таким чином одержуємо двійкове число 100101, яке запи­сується поліномом    Р(х) = x5x21.

Як було показано вище, коди БЧХ мають непарне значення мінімальної кодової відстані  d min. Для того, щоб збільшити d min на оди­ницю, досить помножити твірний поліном коду БЧХ на двочлен (х1).

Кодування у кодах БЧХ виконується так само, як і у звичай­них циклічних кодах, у тому числі і за допомогою матричних способів ( див. вище ). Декодування кодів БЧХ ( виявлення та виправлення поми­лок ) також може виконуватися з використанням методики, викладеної для циклічних кодів  з  d min < 5.

 

 

.