7.6.4. Поліноміальні пристрої кодування та фільтрації
Поліноміальні пристрої кодування та фільтрації призначені для апаратної реалізації ряду операцій над поліномами, що мають бінарні коефіцієнти при ступінях змінної x. Такі операції дозволяють будувати широкий ряд циклічних кодів, які широко використовують для виявлення і виправлення помилок при передачі та зберіганні даних.
У Розділі I ми вже мали справу з поліномами, що мають бінарні коефіцієнти. Якщо записати такий поліном за зростаючими ступенями змінної x зліва направо і уявити, що бінарні коефіцієнти розміщені у регістрі зсуву, то, наприклад, для конкретного поліному
P = a0 x0 + a1 x1 + a2 x2 + … + an xn
зсув коефіцієнтів на один розряд праворуч відповідатиме домноженню поліному на x:
P ∙ x = x ∙ (a0 x0 + a1 x1 + a2 x2 + … + an xn),
а, відповідно, зсув ліворуч – діленню на поліном x.
Якщо, наприклад, код значень коефіцієнтів деякого поліному дорівнює P = 011101, то код поліному P ∙ x = 001110. Звідси витікає, що на основі правил двійкової арифметики можна виконувати операцію множення поліномів.
Приклад 7.7. Виконати операцію множення двох поліномів:
P1 = 1 + x3 ; P2 = 1 + x2 + x3 .
Розв’язання. Визначимо коди значень коефіцієнтів в обох поліномах. Для цього обидва поліноми запишемо у вигляді:
В результаті маємо: P1 = 1001; P2 = 1011.
Множення поліномів з бінарними коефіцієнтами має свою особливість, яка полягає в тому, що показники ступеню множених членів складаються за правилами арифметики, а коефіцієнти при однакових ступенях x – за модулем 2. Тому, наприклад, якщо потрібно знайти суму при коефіцієнтах, то маємо:
x3 + x3 = x3 (1 + 1) = 0 ∙ x3 = 0.
Тому процедура множення коефіцієнтів матиме вигляд:
|
1 |
0 |
0 |
1 |
||
1 |
0 |
1 |
1 |
|||
|
|
|
1 |
0 |
0 |
1 |
|
|
1 |
0 |
0 |
1 |
|
|
0 |
0 |
0 |
0 |
|
|
1 |
0 |
0 |
1 |
|
|
|
1 |
0 |
1 |
0 |
0 |
1 |
1 |
В результаті поліном, що знаходиться як добуток двох поліномів, матиме вигляд:
P = P1 ∙ P2 = 1 + 0 ∙ x + 1 ∙ x2 + 0 ∙ x3 + 0 ∙ x4 + 1 ∙ x5 + 1 ∙ x6 = 1 + x2 + x5 + x6.
З розглянутого прикладу витікає особливість побудови апаратних засобів для виконання операції множення поліномів. Найпоширеніші полягають у тому, що коефіцієнти поліному Р послідовно, починаючи зі старших розрядів, вводяться в структуру, що відображає інший поліном. Вказана структура забезпечує поетапне знаходження суми за модулем 2, внаслідок чого на виході отримуються коефіцієнти поліному-добутку. Важливим моментом у такій процедурі є те, що поліном А може бути будь-яким, у той час як поліном P2 реалізований апаратно і змінюватись не може.
За аналогією з множенням двійкових
поліномів, виконується і операція
ділення. Для ділення використовується
операція віднімання, але віднімання за
модулем 2 співпадає з сумою за модулем
2. При апаратній реалізації операції
ділення поліном P1 послідовно,
починаючи зі старших розрядів, вводиться
в структуру, в якій забезпечується
покроковий зсув і порозрядне віднімання.
В результаті на виході буде отриманий
поліном
.
Пристрої множення та ділення на поліноми широко використовується при контролі правильності передачі інформації у послідовному форматі. Це пристрої дистанційного керування через СОМ-порт та USB-шини, пристрої запису та зчитування інформації на жорсткі диски, системи телекомунікацій, техніка кабельного та радіозв’язку, окремі комп’ютерні мережі.
Практика такого контролю полягає в тому, що передаваний код P1 у пристрої, який називається кодером, помножується на поліном P2 , який називається породжуючим поліномом, і в лінію передається добуток P = P1 ∙ P2 . На приймальній стороні у пристрої, який називається фільтром, відбувається ділення коду Р на породжуючий поліном P2 . Якщо операція ділення виконується без залишку, то інформація прийнята без пошкоджень.
Використовуються і інші прийоми контролю правильності передачі інформації. Сучасна теорія перешкодостійкого кодування [] дає можливість цілеспрямовано підбирати вигляд породжуючого поліному для забезпечення необхідних корегуючих властивостей. Коди, які побудовані на використанні операцій з породжуючими поліномами, відносяться до класу циклічних кодів (коди Хемінга, Файра).
Використання операцій з породжуючими поліномами дає можливість забезпечувати автоматичне шифрування повідомлень.