12.2  Поліноміальні коди

 

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

Поліноміальний код з твірним многочленом g(x) кодує повідомлення m(x) поліномом вигляду

 

u(x)=m(x)g(x)=u0 + u1x + u2x2  + … + un-1xn-1,                (3.15)

 

або кодовим словом з коефіцієнтів цього многочлена u= (u0, u1, …, un-1).

Матриця  поліноміального коду з твірним многочленом g(x) степеня r=n-k має вигляд

 

,                                (3.16)

 

де ненульові елементи в i-му рядку - це послідовність коефіцієнтів твірного многочлена, розташованих з j-го по (j+r)-й стовпець.

Приклад 1  Поліноміальний код заданий твірним многочленом вигляду g(x)=1 + x2 + x3. Закодуємо за його допомогою повідомлення (01011).

Повідомленню (01011) відповідає многочлен

m(x)= 0x0+1x+0x2+1x3+ 1x4 = x + x3 + x4

Тоді кодовим словом буде поліном 

u(x)= m(x)g(x) = (x + x3 + + x4)(1 + x2 + x3) = x + x3 + x4 + x3 + +x5+ x6 +x4+x6+x7=x+(1+1)x3+(1+1)x3+x5+(1+1)x6+x7= x + x5 + x7.

Цьому поліному відповідає кодова послідовність u = (01000101).

Інші способи задання поліноміального (5, 8)- коду з твірним поліномом g(x)=1+x2+x3 – це його подання за допомогою твірної матриці

 

або відображення

00000 → 00000000,

00001 → 00001011,

00010 → 00010110,  

01011 → 01000101.

Теорема.  Вектор помилок e=e0, …, en-1 залишиться не визначеним у тому і лише у тому випадку, якщо його многочлен e(x)=e0+e1x+…+en-1xn-1 ділиться на твірний поліном коду g(x) без остачі.

Доведення.  Прийнята послідовність c(x)=m(x)g(x)+e(x) ділиться на g(x) без остачі тоді і тільки тоді, коли e(x) ділиться на g(x) без остачі.

Тому будь-яка помилка, многочлен якої не ділиться на g(x), буде знайденою, відповідно будь-яка помилка, многочлен якої ділиться на g(x), знайденою не буде. Отже, виявлення помилки поліноміальним кодом з твірним поліномом g(x) може бути здійснене за допомогою ділення многочленів: якщо залишок від ділення многочлена прийнятої послідовності на твірний поліном g(x) ненульовий, то при передачі відбулося спотворення даних.

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

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