2Виявлення і виправлення спотворень в циклічних кодах

Процедури виявлення і виправлення спотворень у циклічних кодах витікають із загальних властивостей корегуючих кодів і ґрунтуються на аналізі залишків від ділення прийнятої комбінації на багаточлен , який утворює цей код. При цьому слід мати на увазі, що максимальна кількість можливих залишків при розподілі на багаточлен ступеня k є завжди меншою значення 2^k при максимальному значенні залишку, яке дорівнює (2^k – 1). Це означає, що і максимальна кількість спотворень, а отже і довжина коду п повинні відповідати умові

, (1)

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

Із виразу (1) неважко визначити ступінь утворюючого поліному, який потрібно застосовувати для виявлення і виправлення спотворень в інформаційному об’єкті загальною довжиною п символів. Зрозуміло, що з цією метою слід використати уже відомий вираз:

.

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

Алгоритм табличного виявлення місця та величини спотворень. Виходячи із шостої властивості коду (про наявність однозначного зв’язку ):

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

Приклад. Побудуємо перевірочну таблицю, якщо n = 7 і Р (x) = х³ + х² + 1. Будемо вважати, що вектор можливих спотворень має лише один відмінний від нуля елемент. Тоді такий вектор в поліноміальному представленні запишеться у вигляді , де номер спотвореного символу може бути довільним ( ). Отже для визначення однозначного зв’язку ) слід знайти відповідні залишки від розподілу на Р (x) усіх можливих спотворень і занести їх таблицю відповідності:

х⁰ : (х³ + х² + 1) → R (x) = х⁰ → ; х¹ : (х³ + х² + 1) → R (x) = х¹ → ;

х² : (х³ + х² + 1) → R (x) = х² → ; х³ : (х³ + х² + 1) → R (x) = (х² + 1) → ;

х⁴: (х³ + х² + 1)→ R (x) = (х² + х + 1)→ ; х⁵: (х³ + х² + 1)→ R (x) = (х + 1) → ;

х⁶: (х³ + х² + 1)→ R (x) = (х² +х)→ .

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

Показник ступеня хі	Значення Е = хі	Результат розподілу хі/Р(x)	Двійковий еквівалент хі/Р(x)
0	х0 =1	х0=1	001
1	х1	х1	010
2	х2	х2	100
3	х3	х2 + 1	101
4	х4	х2 + х + 1	111
5	х5	х + 1	011
6	х6	х2 +х	110

Приклад 4. Нехай для умов прикладу 1, при повідомленні 1011, m = 4, коли утворюючий багаточлен Р(x) = х³ + х² + х⁰, одержана і передавалася кодова комбінація F (x) = 1011100, в якій перевірочні розряди займають три останні позиції. Нехай прийнята комбінація має спотворення у шостому (відповідному х⁵) символі:

= х⁶ + х⁵ + х⁴ + х³ + х²,

де , а .

Для виявлення наявності спотворень прийняту комбінацію F(x) ділять на багаточлен :

х ⁶ + х⁵ +х⁴ + х³ + х² х³ + х² + 1

х ⁶ + х⁵ + х³ х³ + х+1

х⁴+ х²

х⁴ + х³+ х

х³+ х²+ х

х³ + х²+1

= х + 1=11 ≠ 0

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

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

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

1. Отримуємо залишок від ділення E_п-1, відповідного спотворенню в старшому розряді [100…00], на утворюючий поліном : R₀(x) =E_п-1 (x)/ .

2. Ділимо отриманий поліном на і одержуємо поточний залишок R(x).

3. Порівнюємо R₀(x) і R(x).

• Якщо вони рівні, то помилка сталася в старшому розряді, що має ступінь (п – 1).

• Якщо ні, то збільшуємо ступінь прийнятого полінома на одиницю шляхом множення поліному на x¹ і знову проводимо розподіл: •x/ = R(x).

4. Знову порівнюємо отриманий залишок з R₀(x).

• Якщо вони рівні, то помилка в розряді, що має ступінь (п –1 – 1) = = (п –2).

• Якщо ні, то множимо •х² і повторюємо ці операції до тих пір, поки R(x) не буде дорівнює R₀(x). Помилка буде в розряді, відповідному числу, на яке підвищено ступінь , плюс один. Наприклад: •x³/ = R₀(x), тоді спотворення в розряді, що має ступінь (п – (1 +3)) = (п – 1 –3) = (п – 4).

Приклад 5. Нехай, як і в прикладі 2, прийнята комбінація має спотворення у шостому (відповідному х⁵) символі:

= х⁶ + х⁵ + х⁴ + х³ + х².

Тоді:

1. Отримуємо залишки від ділення E_і, відповідного спотворенню в старшому розряді [100…00], на утворюючий поліном : R₀(x) = E_і (x)/ . Із таблиці маємо: R₀(x) = х⁶/ = х² + х = 110.

2. Ділимо отриманий поліном на і одержуємо поточний залишок R(x).

х ⁶ + х⁵ +х⁴ + х³ + х² х³ + х² + 1

х ⁶ + х⁵ + х³ х³ + х+1

х⁴+ х²

х⁴ + х³+ х

х³+ х²+ х

х³ + х²+1

= х + 1=11 ≠ 0

Отже, прийнята комбінація містить спотворення.

3. Порівнюємо R₀(x) і R(x):

R₀(x) = 110 ≠ 011.

Оскільки R₀(x) ≠ , то збільшуємо ступінь прийнятого полінома на x:

•x = ( х⁶ + х⁵ + х⁴ + х³ + х²)•x = х⁷ + х⁶ + х⁵ + х⁴ + х³ = 11111000.

і знову проводимо розподіл: •x/ = R(x):

х ⁷ + х⁶ +х⁵ + х⁴ + х³ х³ + х² + 1

х ⁷ + х⁶ + х⁴ х⁴ + х²+x

х⁵+ х³

х⁵ + х⁴+ х²

х⁴+х³+ х²

х⁴+х³+x

= х² + x =110 ≠ 0

4. Знову порівнюємо отриманий залишок з R₀(x):

R₀(x) = 110 = 110.

З того, що ці залишки є рівними витікає, що виявлено спотворення в розряді, який наразі є старшим. Оскільки зсув здійснено одноразово (і = 1), то для виправлення спотворення слід в прийнятій комбінації додати одиницю за модулем 2 (інвертувати) розряд, що має ступінь (n – 1 – i). Для розглянутого прикладу (n = 7, i = 1) робимо висновок щодо спотворення в розряді, що має ступінь n – 1 – i) = 7 – 1 – 1 = 5, тобто в символі відповідному х⁵, що і є насправді.