Недвійкові коди, що виправляють помилки

Недвійкові коди, що виправляють помилки, поділяють на

· блокові

· і неперервні.

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

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

де – інформаційний елемент, що знаходиться на i-ій позиції інформаційної частини кодової комбінації; ‑ перевірочний елемент, що знаходиться на i-ійпозиції j-го повторення.

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

При -кратному повторенні надмірність коду .

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

Код дозволяє виправити тільки всі однократні помилки. При цьому місце помилки визначається в декодері простим співставленням інформаційної та повтореної частин прийнятої кодової комбінації. Незбіг значень елементів у деякому розряді вказує на помилку у цьому розряді. Для визначення, в якій частині кодової комбінації виникла помилка: в інформаційній чи повтореній, виконують перевірку за кожної частини комбінації окремо. При цьому у перевірку за повинен входити і перевірочний елемент, який міститься у кінці кодової комбінації. При перевірці отримуємо контрольний елемент, значення якого при відсутності помилки буде дорівнювати нулю, а при виникненні однократної помилки – буде відрізнятися від нуля.

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

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

Приклад. Інформаційний код 102, . Кодуємо – . Вносимо помилку: , .

Узагальнений код Хеммінга УКХ є найбільш поширеним з недвійкових кодів такого класу. Код призначений для виправлення однократних помилок у термінах недвійкової арифметики.

Перевірочна матриця УКХ має розмір :

де r – кількість перевірочних елементів,

n – довжина кодової комбінації,

i – номер рядка,

j– номер стовпця.

Стовпці матриці повинні бути ненульовими і різними та, крім того, всі вониповинні мати однакову першу ненульову компоненту . Оскільки відповідає умові , число її можливих значень дорівнює . Звідси, виключивши нульовий вектор-стовпець, отримаємо число вектор-стовпців у матриці (отже і максимальну довжину кодової комбінації)

. (10.1)

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

Ця обставина вказує на зручні позиції для розміщення перевірочних елементів у комбінації. Загалом макет кодової комбінації можна подати як:

, (10.2)

де , – -ічні відповідно інформаційні та перевірочні елементи кодової комбінації.

З розв’язання фундаментального матричного рівняння систематичних кодів

відносно перевірочних елементів ,випливає

, (10.3)

де – транспонований вектор .

Показане у (10.2) розміщення перевірочних елементів не є єдино можливим, але воно забезпечує мінімальний обсяг обчислень при кодуванні та декодуванні. При цьому вираз (10.3) дає оптимальний алгоритм кодування. Кодовий вектор (10.2) поелементно передається у канал зв’язку у вигляді певних сигналів, де він може бути спотворений завадою. Фізичні явища процесу спотворення сигналів не мають значення, тому що з алгебраїчних міркувань його доцільно подати як , де – спотворений кодовий вектор на виході тракту передачі; – вектор помилки з єдиною ненульовою компонентою е (у припущенні однієї помилки).

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

,

.

Вектор являє собою помножений на значення помилки ( ) стовпець перевірочної матриці , що відповідає позиції спотвореного елемента у кодовому векторі . Його називають локатором місця помилки. Оскільки всі вектор-стовпці у мають першу ненульову компоненту, що дорівнює , то у перша ненульова компонента завжди буде . Це обумовлює другий крок процедури декодування – визначення значення помилки:

(10.4)

З визначення випливає третій крок процедури декодування – знаходження локатора місця помилки:

, (10.5)

тобто кожна компонента вектора ділиться на значення помилки .

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

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

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

Зазначимо, що недвійкові коди прийнято ділити на дві великі групи:

· коди з простою основою, коли є простим числом, і

· коди з основою , що розкладається.

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

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

Таблиця 10.1.1 Таблиця 10.1.2

Наприклад, перевіримо, що із табл. 10.1.2.

, , ,

Перевіримо, що із табл. 10.1.1.

, , , .

3/6=3∙6^-1=3∙3=5, 2/4=5

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

В першій колонці цієї таблиці наведені елементи поля у десятковому поданні (ці номерні записи можна розглядати як імена окремих елементів).

У другій колонці наведено подання елементів поля у формі двійкового вектора (сукупності коефіцієнтів двійкового поліному – остачі від ділення на ) з природнім розподілом вагів 2³ 2² 2¹ 2⁰.

У третій колонці наведено мультиплікативну форму подання елементів поля у вигляді степенів примітивного елемента[1] . Нагадаємо, що степені від до примітивного елемента відповідають усім ненульовим елементам поля , тобто .

Можна замінити будь-який високий степінь на такий, що не перевищує , якщо мати на увазі, що b¹⁵=b⁰=1, b¹⁶=b, b¹⁷=b², b¹⁸=b³, . . .

Таблиця 10.1.3

Виконаємо, наприклад, множення елементів 13 та 15 поля GF(16) за допомогою степенів b:

13´15 = b¹³´b¹²=b²⁵= b¹⁰´b¹⁵= b¹⁰´1 = b¹⁰= 7.

Задача10.2.7

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

Розв’язання. У відповідності з виразом (10.1) при та маємо , що недостатньо для побудови коду з . При максимальна довжина коду . Таким чином, вибираємо і матриця має розміри .

Довільно надаємо значення і будуємо матрицю :

Кодова комбінація закодована УКХ буде мати вигляд . Обчислюємо значення перевірочних елементів за алгоритмом (10.3). Множення і додавання виконуємо у відповідності з табл. 10.1.1 та 10.1.2:

Тобто одержуємо значення . Таким чином, у канал з кодера подається вектор .

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

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

Тобто синдром є таким .

Значення помилки, у відповідності із співвідношенням (10.4): (оберненим до 2 числом є 5, оскільки із табл. 10.2 маємо ), а локатор помилки, згідно із (10.5):

.

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

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

Довжина блока РС-коду , де – потужність алфавіту (основа) коду.

РС-код, як і БЧХ-код, може задаватися твірною чи перевірочною матрицями або твірним чи перевірочним поліномами. Найбільш поширений спосіб побудови РС-коду на основі твірного поліному . Перевірочну матрицю часто використовують для вивчення деяких властивостей РС-коду та його зв’язку з систематичними кодами.

Твірний поліном коду РС, що виправляє помилок, є добутком мінімальних поліномів для спектру елементів з , де – кількість перевірочних елементів у блоці коду:

, (10.6)

де – спектр твірних коренів поліному .

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

Для спрощення побудови РС-коду часто вибирають та одержують:

(10.7)

Перевірочний поліном РС-коду одержують як частку від ділення на .

Мінімальна кодова відстань РС-коду .

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

Найбільш просто коди РС реалізуються для алфавіту потужністю , тобто коли .У цьому випадку операції віднімання співпадають з операціями додавання, тому скрізь можна знак замінити на , зокрема у виразах (10.6) та (10.7).

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

Задача 10.2.8

Закодувати кодом Ріда-Соломона, що виправляє дві помилки, комбінацію шістнадцяткового первинного коду довжиною .

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

та

Як випливає з умови задачі, потужність алфавіту коду . Тоді РС-код може мати довжину . Кількість перевірочних елементів .

Твірний поліном коду РС, що виправляє помилок, є добутком мінімальних поліномів (10.6):

Приймаємо ; тоді твірний поліном буде мати вигляд:

Скориставшись для виконання розрахунків табл. 10.1.3, одержимо:

Кодування первинної кодової комбінації виконуємо за одним з правил побудови циклічного коду: :

1.
;

2. ділення дає остачу ;

3. .

Таким чином, кодова комбінація коду РС буде мати вигляд:

або

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

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

При виникненні декількох помилок у одному рядку (стовпці), помилки виправляють послідовно для тих стовпців (рядків), де вони є поодинокими.

Задача 10.2.9

Закодувати вісімковим ітеративним кодом, що виправляє однократні помилки, інформаційну послідовність

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

Розв’язання.Для того, щоб ітеративний код виправляв однократні помилки, досить для кодування по стовпцям і рядкам використати код з перевіркою за , тобто у даному разі – за .

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

Таким чином кодована послідовність вісімкового ітеративного коду буде мати вигляд: .

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

Припустимо, що при передачі по каналу зв’язку у кодованій послідовності виникла одна помилка і до декодера надходить така послідовність: . Для виявлення та виправлення помилки у декодері кодована послідовність, що надійшла з каналу, записується у вигляді матриці по 5 елементів у кожному рядку і виконується перевірка кожного рядка та кожного стовпця матриці за :

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

Виправлення спотвореного елемента виконують таким чином. У зв’язку з тим, що не виконується перевірка для 3-го рядка і 2-го стовпця, елемент, що знаходиться на перетинанні 3-го рядка і 2-го стовпця, замінюють елементом, який є сумою за прийнятого (помилкового) елемента та перевірочного елемента 3-го рядка (або 2-го стовпця), який був одержаний у декодері, тобто . Таким чином, виправлена послідовність на виході декодера буде мати вигляд: .