Циклічний зсув кодової комбінації

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

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

Припустимо, задана вихідна кодова комбінація і відповідний їй поліном:

a(x) = a_nxⁿ⁻¹ + a_n−1xⁿ⁻² + … + a₂x + a₁

Помножимо на :

a(x) · x = a_nxⁿ + a_n−1xⁿ⁻¹ + … + a₂x² + a₁x

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

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

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

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

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

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

, ( 9.1 )

де r – кількість перевірочних розрядів у комбінації циклічного коду; ‑ поліном первинної кодової комбінації (представляє інформаційні біти); ‑ твірний поліном; ‑ частка від ділення того степеня, що і ; ‑ остача від ділення, яка має степінь, не більший за .

З виразу (9.1) можна одержати три способи побудови циклічного коду:

;

,

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

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

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

Таблиця 9.1

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

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

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

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

G= .

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

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

,

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

H = .

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

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

P(x)_(d=4)=P(x)_(d=3)(xÅ1).

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

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

Задача 9.2.1

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

Розв’язання. Побудуємо кодову комбінацію першим способом . Для того, щоб закодувати комбінацію простого коду циклічним кодом, необхідно вибрати твірний поліном. Степінь твірного поліному визначається кількістю перевірочних елементів у комбінації циклічного коду, а величина при визначається з виразу . Тобто, при маємо . Таким чином з табл. 9.1 вибираємо поліном степені : 1.

Виконуємо кодування комбінації двійкового простого коду . Для цього

– записуємо її у вигляді полінома: ;

– помножимо на ;

– оскільки , то ;

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

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

Покажемо процес виправлення однократної помилки. Для цього припустимо, що при передачі виникла однократна помилка, поліном та вектор якої відповідно та . Тоді поліном прийнятої комбінації F^*(x)=F(x)ÅE(x)=x⁶Åx⁵Åx⁴Åx³Åx² ® 1111100.

Декодер виконує перевірочне ділення F^*(x) на той же твірний поліном P(x), який був використаний при кодуванні:

Отже, остача або .

Оскільки остача від ділення не дорівнює нулю, робимо висновок про наявність помилки у прийнятій комбінації F^*(x).

Для визначення місця помилки скористуємося методом гіпотез.

Крок 1. Висуваємо гіпотезу про помилку у молодшому розряді комбінації циклічного коду F^*(x), тобто вважаємо, що поліном та вектор помилки відповідно E₁(x)=1 та E₁=0000001. Беремо суму за модулем 2 F^*(x)ÅE₁(x):

F^*(x)ÅE₁(x)=(x⁶Åx⁵Åх⁴Åx³Åx²)Å1= x⁶Åx⁵Åх⁴Åx³Åx²Å1;

ділимо отриману суму на з метою підтвердження (у разі нульової остачі) або спростування (у разі ненульової остачі) висунутої гіпотези:

Остача R(x) = x, тобто R(x)¹0, і гіпотеза відхиляється.

Крок 2. Висуваємо гіпотезу про помилку у другому розряді F^*(x), тобто вважаємо, що E₂(x)=x ® E₂=0000010. Беремо суму за модулем 2 F^*(x)ÅE₂(x):

F^*(x)E₂(x) = (x⁶Åx⁵Åx⁴Åx³Åx²)Åx = x⁶Åx⁵Åx⁴Åx³Åx²Åx;

ділимо цю суму на P(x) з метою підтвердження або спростування гіпотези:

Остача , тобто , і гіпотеза відхиляється.

Крок 3. Висуваємо гіпотезу про помилку у третьому розряді F^*(x), тобто вважаємо, що E₃(x)=x² ® E₃=0000100. Беремо суму за модулем 2 F^*(x)ÅE₃(x):

F^*(x)ÅE₃(x)=(x⁶Åx⁵Åx⁴Åx³Åx²)Åx²=x⁶Åx⁵Åx⁴Åx³;

ділимо цю суму на P(x) з метою підтвердження або спростування гіпотези:

Остача R(x)=x²ÅxÅ1, тобто R(x) 0, і гіпотеза відхиляється.

Крок 4. Висуваємо гіпотезу про помилку у четвертому розряді F^*(x), тобто вважаємо, що E₄(x)=x³ ® E₄=0001000. Беремо суму за модулем 2 F^*(x)ÅE₄(x):

F^*(x)ÅE₄(x) = (x⁶Åx⁵Åx⁴Åx³Åx²)Åx³= x⁶Åx⁵Åx⁴Åx²;

ділимо отриману суму на P(x) з метою підтвердження або спростування гіпотези:

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

F(x)=F^*(x)ÅE₄(x)= x⁶Åx⁵Åх⁴Åx² ® F=1110100.

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

Задача 9.2.2

Закодувати двійковим циклічним кодом, що виправляє однократні помилки, кодову комбінацію двійкового простого коду Q(x)=x⁵Åx² і виправити будь-яку однократну помилку в одержаній комбінації циклічного коду. Визначити надмірність коду.

Розв’язання. Щоб закодувати задану кодову комбінацію Q(x)=x⁵Åx² ( ) циклічним кодом, що виправляє однократні помилки (d_min=3) необхідно вибрати твірний поліном. Степінь твірного поліному P(x) визначається кількістю перевірочних елементів , яку визначаємо з виразу 2^r–1 n (для d_min=3). При одержуємо та вибираємо з таблиці 9.1 поліном четвертого степеня: P(x)=x⁴ÅxÅ1.

Виконаємо кодування первинної кодової комбінації Q(x)=x⁵Åx², для чого знайдемо частку C(x) від ділення Q(x)x⁴ на P(x), а потім помножимо її на P(x). Маємо

Q(x)x⁴=(x⁵Åx²)x⁴=x⁹Åx⁶.

Поділимо отриманий добуток на P(x) з метою визначення частки C(x) від ділення:

Тобто C(x)=x⁵Åx. Помножимо C(x) на P(x) і одержимо кодову комбінацію циклічного коду:

F(x)=C(x)P(x)=(x⁵Åx)(x⁴ÅxÅ1)=x⁹Åx⁶Åx²Åx,

або у двійковому вигляді .

Виправляємо однократну помилку.

Припустимо, що при передачі по каналу зв’язку виникла однократна помилка, поліном якої . Тоді поліном прийнятої кодової комбінації циклічного коду F^*(x)=x⁹Åx⁶Åx²ÅxÅ1.

Декодер виконує перевірочне ділення F^*(x) на твірний поліном P(x):

Тобто R(x)=1¹0.Це вказує на наявність помилки у прийнятій кодовій комбінації.

Для визначення місця помилки скористуємося методом гіпотез, першим кроком якої є гіпотеза про наявність помилки у молодшому розряді прийнятої кодової комбінації F^*(x), тобто вважаємо, що поліном та вектор помилки відповідно E₁(x)=1 та E₁=0000000001. Визначаємо суму за модулем 2 F^*(x)E₁(x) та ділимо цю суму на Р(х) з метою підтвердження або спростування гіпотези:

F^*(x)E₁(x)=(x⁹Åx⁶Åx²ÅxÅ1)Å1= x⁹Åx⁶Åx²Åx;

Тобто , що вказує на те, що помилка дійсно була у першому розряді.

Таким чином, вихідна комбінація циклічного коду F(x)=x⁹Åx⁶Åx²Åx ® F = 1001000110.

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

2. Коди Боуза-Чоудхурі-Хоквінгема (БЧХ)

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

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

, або , (9.2)

де – ціле число; – непарне додатне число, при діленні на яке одержуємо цілим непарним числом. Таким чином, може бути тільки непарним числом. Тобто, керуючись виразом (9.2), визначаємо, що кількість елементів у комбінаціях коду БЧХ може дорівнювати тощо.

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

, (9.3)

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

. (9.4)

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

, (9.5)

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

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

Таблиця 9.2

Подані в таблиці параметри були визначені у відповідності з викладеною вище методикою. Для зручності запису твірні поліноми подані у вісімковій системі числення (P₈). Щоб одержати твірний поліном у звичайному вигляді, тобто у тій формі, яка використовується для побудови кодів БЧХ, треба перевести кожну вісімкову цифру у три біти. Так, наприклад, Р₈=45 запишеться двійковими числами: та . Таким чином одержуємо двійкове число , яке записується поліномом Р(х)=x⁵Åx²Å1.

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

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

Задача 9.2.3

Знайти твірний поліном двійкового коду БЧХ, здатного виправляти трикратні помилки та призначеного для передачі символів деякого алфавіту, потужність якого дорівнює 32.

Розв’язання. Мінімальна кодова відстань для коду БЧХ, здатного виправляти трикратні помилки, . Для передачі символів алфавіту потужністю повідомлень достатньо мати двійкових інформаційних символів ( ).

Для визначення твірного полінома коду БЧХ, що має та , скористаємося таблицею 9.2. Бачимо, що мінімальна довжина коду БЧХ з заданими параметрами , для якого твірний поліном у вісімковій системі числення P₈=2467, або у двійковій системі числення P₂=010100110111. Таким чином твірний поліном коду БЧХ буде мати вигляд P(x)=x¹⁰Åx⁸Åx⁵Åx⁴Åx²ÅxÅ1.