Розв'язання. При використанні завадостійкого (k, n)- коду Хеммінга контрольні суми, що додаються до інформаційного повідомлення

x⁴ + x³ +0×x² + x

+ x⁵ + x⁴+ 0×x³ + x² ___

Ділення поліномівздійснюється за правилами ділення степеневих функцій, причому операція віднімання замінюється додаванням за mod 2 (додавання і віднімання за mod 2 збігаються).

x³ + x² + x + 1

x + 1

00001 → 00001011,

Теорема. Якщо твірний поліном g(x) не є дільником жодного з многочленів вигляду x^j+ 1, де j<n, то мінімальна відстань між кодовими словами відповідного поліноміального коду d_min ≥ 3.

Доведення. Припустимо d_min= 2. Тоді існує многочлен m (x), такий, що m (x) ×g(x)=u (x) і степінь u (x) ≤ n. Мінімальна вага Хеммінга (мінімальна кодова відстань d_min) w (u)=2, тому u(x)=x^m+x^l, де l<m<n Отже, кодовий многочлен можна подати у вигляді u(x)=x^l ( x^m-l+ 1). Тоді двочлен (x^m-l+ 1) повинен ділитися на g (x), що унеможливлює умову теореми. Якщо припустити, що d_min =1, то це приведе до твердження, що x^m повинне ділитися на g (x), що також суперечить умові.

12.3 Циклічні коди

Серед поліноміальних кодів найпоширеніші циклічні коди.

Визначення. Лінійний блоковий ( k, n) - код називається циклічним, якщо в результаті циклічного зсуву кодового слова виходить інше кодове слово даного коду. Іншими словами, якщо u=(u₀, u₁, …, u_n-1) – кодове слово, то і v=(u_n-1, u₀, u₁, …, u_n-2), отримане циклічним зсувом елементів u _i, - кодове слово.

Наведемо властивостіциклічних кодів.

1) Для циклічного ( k, n) - коду кожний ненульовий поліном повинен мати степінь принаймні (n-k), але не більше n-1;

2) Існує тільки один кодовий поліном g(x)= 1 + g₁x +g₂x² + … + +g_n-k-1×x^n-k- + x^n-k степеня (n-k), що є дільником кожного кодового поліномаu(x)= m(x)×g(x), цей поліном називається твірним поліномом коду.

Припустимо, треба закодувати деяку послідовність m=(m₀, m₁, m₂, …, m_k-1). Відповідний їй поліном матиме вигляд

m(x)=m₀+m₁x+m₂x²+ … +m_k-1x^k-1. (3.17)

Помножимо m(x) на x^n-k, що рівнозначно зсуву двійкової послідовності m=(m₀, m₁, m₂, …, m_k-1) на n-k розрядів праворуч. У результаті отримаємо поліном степеня n- 1 або меншого

x^n-k×m(x)=m₀x^n-k+m₁x^n-k+1+ … +m_k-1x^n-1. (3.18)

Скориставшись теоремою ділення поліномів (3.14), можна записати

x^n-k×m(x)=q(x)×g(x) + ρ(x), (3.19)

де q(x) і ρ(x) - частка і остача від ділення полінома x^n-k × m(x) на твірний поліном g(x).

Оскільки степінь твірного полінома g(x) r =(n-k), то степінь остачі ρ (x) не більше (n-k-1), тобто

ρ(x)=ρ₀+ ρ₁x+ ρ₂x²+…+ ρ_n-k-1x^n-k-1. (3.20)

Використовуючи правила арифметики з GF (2), вираз (3.19) можна записати так:

ρ(x) + x^n-k × m(x) = q(x)×g(x). (3.21)

+ m_k-1x^n-1, (3.22)

u= (r₀, r₁, …, r_n-k-1, m₀, m₁, m₂, …, m_k-1),

де r₀, r₁, …, r_n-k-1 – перевірні символи; m₀, m₁, m₂, …, m_k-1 -інформаційні символи.

Відтак, кодове слово циклічного коду складається з перевірної частини з (n-k) перевірних символів і інформаційної частини m завдовжки k символів. Перевірні символи є коефіцієнтами полінома ρ(x) – остачі від ділення кодового слова u(x)=m(x) × x^n-k на твірний поліном g(x).

Приклад 2 Закодуємо послідовність m= (0111) циклічним кодом, заданим твірним поліномом g(x)=1+x+x³.

Вектору m =(0111) відповідає поліном m (x)= x + x ²+ x ³.

Помножимо m (x) на x^n-k=x³, де n-k – кількість перевірочних символів: m(x)× x^n-k=m(x)×x³= (x+x²+x³) x³=x⁴+x⁵+x⁶, або виконаємо зсув елементів інформаційної послідовності m(x) на r =3 розряди праворуч: (0111)® (0000111).

Розділимо добуток m(x)x^n-k на твірний поліном коду g(x):

x⁶ + x⁵ + x⁴ x³+x+1

+ x⁶ + x⁴ + x³ x³+x²

+ x⁵ + x³ + x²

x²= ρ(x).

ρ(x) = 0 ∙ x⁰ + 0 ∙ x¹ + 1× x².

Отже, кодовий поліном заданої інформаційної послідовності:

u(x)=ρ(x) + x^n-k × m(x)=x² + x⁴ + x⁵ + x⁶ = 0∙ x⁰ + 0 ∙ x¹ + 1× x² + 0 ∙x³ + + 1× x⁴ + 1× x⁵ + 1× x⁶,

що відповідає кодовому слову u =(0010111), де перші три символи перевірні.

Таким чином, алгоритм побудови циклічного( k, n)- коду для послідовності m=(m₀, m₁, m₂, …, m_k-1) такий:

1) многочлен інформаційної послідовності m(x) множиться на x^{n- k}, тобто зсувається праворуч на n-k розрядів;

2) отриманий у такий спосіб поліном ділиться на твірний поліном коду g(x);

3) остача від ділення x^n-k×m(x) на g(x) додається до x^n-k×m(x), тобто записується в молодших n-k розрядах.

Ще однією важливою властивістю циклічного (k, n)- коду є те, що твірний поліном g(x) ділить без остачі двочлен xⁿ +1, тобто комбінації лінійного коду мають властивість циклічності при виконанні умови

xⁿ+1=g(x) × h(x). (3.23)

Кожний такий двочлен xⁿ +1 може бути розкладений на декілька незвідних поліномів – таких поліномів, які не можуть бути подані як добуток многочленів меншого степеня, тобто вони діляться або самі на себе, або на 1.

Як твірні поліноми різних циклічних кодів використовуються незвідні поліноми і їх добутки, оскільки вони є дільниками двочлена xⁿ +1. Деякі з твірних поліномів наведені у табл. 3.4.

Таблиця 3.4

Продовження табл.3.4

Визначення. Поліном h(x) степеня k, що є часткою від ділення двочлена xⁿ+1 на твірний поліном коду g(x), називається перевірним поліномом. Оскільки h(x) однозначно зв'язаний з g(x), то він також визначає код.

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

y(x)=q(x)g(x)+s(x). (3.24)

Якщо у(x) є кодовим поліномом, то він ділиться на g(x) без остачі, тобто s(x)= 0.

Ненульова остача s(x)≠ 0 від ділення полінома прийнятого вектора у(x) на твірний поліном коду g(x ) є ознакою наявності помилки у прийнятій послідовності, тобто кодовим синдромом.

Поліном синдрому s(x) має вигляд

s(x)=s₀+s₁x+…+s_n-k-1x^n-k-1. (3.25)

Покажемо, що многочлен синдрому однозначно зв'язаний з многочленом помилок e(x) і, отже, за допомогою полінома синдрому можна не тільки виявляти, але й виправляти помилки у прийнятих послідовностях.

y(x)=u(x)+e(x). (3.26)

Додавши до лівої і правої частин виразу (3.26) кодовий поліном u (x), отримаємо

u(x)+y(x)=e(x). (3.27)

y(x)=q(x)×g(x) + s(x),

u(x)=m(x)×g(x),

вираз (3.27) запишемо так:

e(x)= [ m(x)+q(x) ]× g(x)+s(x)=f(x)×g(x)+s(x), (3.28)

тобто поліном синдрому s(x) – це остача від ділення многочлена помилки e(x) на твірний поліном коду g(x). Звідси випливає, що, знайшовши поліном синдрому, можна однозначно визначити вектор помилок, і отже, виправити помилку.

12.5 Твірна і перевірна матриці циклічного коду

Подамо кодове слово циклічного (k, n) - коду таким чином:

u(x)= ρ(x) + x^n-k × m(x), (3.29)

де ρ(x) – остача від ділення многочлена x^n-k×m (x) на твірний поліном коду g(x).

Твірна матриця циклічного коду складається з двох частин: перевірної підматриці P_k×(n-k) розмірністю k×(n-k), щовизначається поліномами остачі ρ(x) від ділення кодового многочлена x^n-k×m(x) на твірний поліном коду g (x) та одиничної підматриці I_k×k розмірністю k×k, що відповідає інформаційній частині кодової послідовності.

Для побудови твірної матриці циклічного кодуберуться тільки ті з комбінацій інформаційних послідовностей m_i (x), де i =1.. k, що мають одиницю тільки в одному розряді. Ці комбінації помножують на x^n-k і знаходять остачі від їх ділення на твірний поліном коду

 

, (3.30)

 

їм відповідні (n-k-1) - послідовностібудуть рядками перевірної частини P_k×(n-k) твірної матриці коду.

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

Приклад Для циклічного (4, 7)- коду, заданого твірним поліномом g(x)= 1 +x²+x³, побудувати твірну матрицю.

Запишемо чотириментні одиничні комбінації інформаційних повідомлень m_i (x): (1000) ® m₁(x)= 1; (0100) ® m₂(x)= x; (0010) ® m₃(x)= x²; (0001) ® m₄(x)= x³.

Помножимо кожну з них на x³ (кількість перевірних символів r=n-k= 7-4 = 3) і розділимо на твірний поліном коду g(x)= x³+x²+ 1.

Поліноми остач від ділення r (x) мають степінь n - k -1 = 2, на одиницю менший за степінь дільника, і будуть такими:

1) 1 × x3 x3+x2+1 + x3+x2+1 1 x2+1, ρ1(x)= 1 + x2 ® (101);	2) x∙x3 x3+x2+1 + x4 + x3 + x x+1 x3 + x + x3 + x2 + 1 x2 + x +1, ρ2(x)= 1+ x + x2® (111);
3) x2∙x3 x3+x2+1 + x5 + x4 + x2 x2+x+1 x4 + x2 + x4 + x3 + x x3 + x2 + x + x3 + x2 + 1___ x + 1, ρ3(x)= 1+ x ® (110);	4) x3∙x3 x3+x2+1 + x6 + x5 + x3 x3+x2+x x5 + x3 + x5 + x4 + x2 x4 + x3 + x2 + x4 + x3 + x___ x2 + x, ρ4(x)= x + x2 ® (011).

Твірна матриця матиме вигляд

.

Відповідно перевірна матриця матиме вигляд

.

 

З перевірної матриці випливає система перевірних рівнянь коду

Кодові слова даного циклічного (4,7)-коду утворюються так:

u = (r₀, r₁, r₂, m₀, m₁, m₂, m₃).

12.6 Способи декодування циклічного коду

Для виправлення помилок циклічним кодом використовують умову, що кількість різних ненульових поліномів синдрому – остач від ділення многочлена прийнятої послідовності на твірний поліном коду – дорівнює кількості елементів n кодової послідовності, якщо кратність помилки, що виправляється, l =1 або числу сполук з n по l. Наприклад, при n =15 та l =2 необхідно =105 ненульових остач для однозначного виправлення двох помилок в коді довжини n. Для цього необхідно вибрати поліном g (x) степеня r= 7, оскільки 2⁷ >105, де r =7 – кількість перевірних елементів, k=n-r = 8 – довжина інформаційної послідовності.

Розглянемо способи виправлення поодиноких помилок циклічним кодом (багатократні помилки виправляються так само).

1-й спосіб декодування циклічного кодуґрунтується на побудові гіпотез про наявність помилки у певному розряді кодової комбінації. Цей спосіб декодування такий:

1) будуємо гіпотезу про наявність помилки у 1-му біті прийнятої комбінації у(x), тобто припускаємо, що вектор помилок (e₁= 10 … 00 ). Знаходимо порозрядну суму у(x)+e(x) і ділимо її на твірний поліном g(x): якщо остача від ділення (поліном синдрому) s(x)=0, то гіпотеза підтверджується, інакше відхиляється;

2) будуємо гіпотезу про помилку у 2-му розряді, тобто припускаємо, що e₂= (01 … 00). Знаходимо суму у(x)+e(x) і ділимо на g(x) – у результаті підтверджуємо або спростовуємо цю гіпотезу: якщо остача s(x)≠ 0, то гіпотеза відкидається, інакше – приймається і т. д. до того часу, поки не отримаємо остачу s(x)= 0, тобто підтвердження гіпотези. Нульовий поліном синдрому s(x)=0 свідчить про те, що помилки немає. Сума многочленів прийнятої кодованої послідовності і вектора помилок, що відповідає нульовій остачі s(x)=0, визначає передане кодове слово так: u(x)= y(x) + e _i(x).

2-й спосіб декодування циклічного коду такий:

1) визначається вага w вектора синдрому s(x) – остачі від ділення многочлена прийнятої послідовності у(x) на твірний поліном коду g(x). Якщо w £ l, де l - кратність помилок, що виправляються кодом, то остача s(x) додається доприйнятої комбінації у(x), і у такий спосіб вона виправляється;

2) якщо w > l, то виконується циклічний зсув прийнятої кодової комбінації у(x) на один розряд праворуч, і отримана так комбінація знову ділиться на g(x). Якщо вага вектора остачі s(x) w£ l, то циклічно зсунута комбінація додається з цією остачею, а потім циклічно зсовується на один розряд ліворуч (тобто повертається до попереднього положення). Отримана таким чином кодова комбінація вже не містить помилок;

3) якщо після першого циклічного зсуву і ділення на твірний поліном вага остачі залишається w > l, то так само виконується наступний циклічний зсув, ділення на g(x), визначення ваги остачі і т. д. Цей процес продовжується, поки вага остачі не стане w £ l. Кодова комбінація, отримана у результаті послідовного циклічного зсуву, для якої виконуватиметься умова w £ l, додається з остачею s(x) від ділення цієї комбінації на твірний поліном g(x). Після цього виконується циклічний зсув назад на стільки розрядів, на скільки був зсув щодо початкової прийнятої комбінації у(x). У результаті отримуємо виправлену кодову комбінацію u(x).

Зразки розв'язування задач до розділу 12

Приклад 1 Поліноміальний код заданий твірним многочленом g(x)=1+x⁴+x ⁵. Закодувати двійкові комбінації 1011, 11001100. Побудувати твірну матрицю для кожного з одержаних кодів.