Кількість перевірних символів у кодовій комбінації (верхня межа Варшамова-Гільберта)

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

і

ІЗ

ЗО

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

Як видно з прикладу 19.4, задача декодування звичайним перебором і порівнянням не під силу навіть сучасним ЕОМ (і, можливо, ЕОМ майбутньо­го), тому на практиці набули розповсюдження такі методи кодування й декодування, що не потребують перебору та порівняння і мають допустиму складність при реалізації.

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

Чи досить знання синдрому для виправлення помилок? У загальному ви­падку - ні. Необхідно ще знати, на які символи потрібно замінити помилково прийняті. Проте для двійкових кодів виправлення помилок провадиться єди­ним способом - інверсією символів (0 замінюється на 1 і, навпаки, 1 - на 0). Тому знання синдрому є необхідною і достатньою умовою для виправлення помилок у двійкових кодах. Таким чином, синдромне декодування двійкових кодів зводиться до пошуку тим чи іншим способом синдрому, за яким вияв­ляються або виправляються помилки. Десятки запропонованих до цього часу коректуючих кодів і відрізняються саме методами формування перевірних символів та знаходження синдрому при декодуванні.

Класифікація коректуючих кодів. Згідно з основними параметрами й ме­тодами кодування коректуючі коди можна поділити на блокові та неперервні.

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

Різновидом як блокових, так і неперервних кодів є роздільні та нерозді­льні коди. У роздільних кодах завади можна визначити, де інформаційні та де перевірні символи. У нероздільних кодах це неможливо.

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

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

17.3. КОДИ З ПОСТІЙНОЮ ВАГОЮ

Усі дозволені кодові комбінації двійкового коду з постійною вагою ма­ють однакову кількість одиниць. Нагадаємо (див. § 19.1), що вага коду - кількість одиниць у двійковій кодовій комбінації. Коди з постійною вагою відносяться до класу блокових нероздільних кодів; тому що в них неможливо знайти окремо інформаційні та перевірні символи.

Типовим прикладом коду з постійною вагою є семирозрядний телеграфний код № З (МТК-3), рекомендований Міжнародним консультативним комітетом із телефонії й телеграфії (МККТТ) для використання в системах зі зворотним зв'язком із метою виявлення помилок. Вага коду дорівнює трьом, отже, кожна дозволена кодова комбінація має три одиниці й чотири нулі. У МТК-3 з усієї кількості кодових комбінацій М=128 дозволеними є тільки .

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

17.4. КОД ІЗ ПАРНИМ ЧИСЛОМ ОДИНИЦЬ

Це систематичний -код, в якому основним правилом при коду­ванні й декодуванні є перевірка на парність. Кодова віддаль для цього коду . Тому, згідно з правилом (19.3), код завжди виявляє однократні помилки. Дозволені кодові комбінації цього коду при будь-якому числі інформаційних символів мають один перевірний. Розміщення перевірного символу в кодовій комбінації не має значення. Звичайно його ставлять після інформаційних символів. Значення перевірного символу розраховується з умовою, що загальна кількість одиниць в утвореній таким чином дозволеній кодовій комбінації була парною (звідси і назва коду). Математично парність означає, що сума за модулем два всіх символів кодової комбінації дорівнює нулю (правило додавання за модулем два див. у § 19.2).

Якщо розряди кодових комбінацій пронумерувати справа наліво і симво­ли в цих розрядах позначити для ненадлишкового коду а для надлишкового коректуючого то описану вище процедуру формування дозволеної кодової комбінації і синдрому можна записати так:

, для (19.7)

і синдром

, (19.8)

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

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

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

17.5. ЦИКЛІЧНІ КОДИ

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

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

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

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

, оскільки ;

;

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

. (19.9)

У теорії циклічних кодів доводиться, що породжуючими поліномами можуть бути тільки поліноми, які є дільниками двочлена . Знайдені за допомогою ЕОМ породжуючі поліноми зведені у великі таблиці. Деякі із цих поліномів наведені в табл. 19.2. Слід відзначити, що із підвищенням макси­мального степеня породжуючих поліномів різко зростає їх число. Так, при є всього два поліноми, а при їх вже кілька десятків.

19.2. Породжуючі поліноми циклічних кодів

Максимальний степінь	Породжуючі поліноми

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

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

Правило кодування:

, (19.10)

де - остача від ділення на .

Згідно з алгоритмом (19.10) можна рекомендувати таку послідовність формування дозволених кодових комбінацій: 1) до комбінації первинного коду дописується праворуч нулів, що є еквівалентним мно­женню на ; 2) добуток ділиться на породжуючий полі­ном і знаходиться остача , максимальний степінь якої не переви­щує ; 3) вирахувана остача додається до .

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

Взаємозалежність між синдромом (остачею) і помилковим символом знаходиться просто. Необхідно взяти будь-яку дозволену кодову комбінацію (краще нульову ), ввести помилку в заданий символ і виконати ділення на поліном . Обчислена остача і буде вказувати на помилку в цьому символі. Для циклічного коду (7,4) взаємозалежність між синдромом і помилковим символом для різних породжуючих поліномів наведена в табл. 19.3. За синдромом із цієї таблиці можна знайти місцезнаходження помилки і виправити її.

Поиск по сайту: