Побудова групового корректірующегоій коду обсягом 9 слів

;; ;; ;; ;; ;; ;; ;; ;; ;;;

Індивідуальне завдання по Теорії інформації

Підготував В.С. Прохоров

Побудувати груповий коригуючий код обсягом 9 слів. Код повинен забезпечувати виправлення одиночних і виявлення подвійних помилок.

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

Визначимо число інформаційних розрядів коду зі співвідношення

,

де Q - необхідний обсяг коду. У нашому випадку Q = 9, тому

Звідси отримуємо .

Далі знаходимо число n з нерівності

Підставляємо і підбором знаходимо мінімальне n, що задовольняє нерівності. У нашому випадку .

Далі ми повинні скласти таблицю розпізнавальних знаків. Для цього необхідно ввести поняття вектора помилок і розпізнавальні знаки. Вектор помилок це n-розрядна двійкова послідовність, що має одиниці у всіх розрядах, які зазнали спотворення, і нулі в інших розрядах. (Приклад: спотворення піддалися два молодших розряду 6-розрядного повідомлення - тоді вектор помилки буде виглядати як 000011), а опізнавач - деяка зіставлена ​​цього вектору контрольна послідовність символів. У нашому випадку вектори помилок мають розрядність 7 біт, так як , Розпізнавальні знаки мають розрядність 3 біт, так як . Розпізнавальні знаки рекомендується записувати у порядку зростання (нульову комбінацію не використовуємо).

Тепер необхідно визначити перевірочні рівності і сформулювати правила побудови коду, здатного виправляти всі одиночні помилки.

Вибираємо з таблиці рядки, де розпізнавальні знаки мають у першому (молодшому) розряді одиницю. Це рядки 1, 3, 5 і 7. Тоді перше перевірочне рівність буде виглядати так:

Тепер вибираємо рядки, де розпізнавальні знаки мають у другому розряді одиницю.

Це рядки 2, 3, 6, 7.

Тоді друге перевірочне правило виглядає так:

І, нарешті вибираємо рядки, де розпізнавальні знаки мають одиницю в третьому розряді. Це рядки 4, 5, 6, 7. Отже третє перевірочне рівність виглядає так:

Далі потрібно відібрати рядки, де розпізнавальні знаки мають всього одну одиницю. У нашому випадку це рядки 1, 2 і 4. Повертаємося до отриманих раніше рівнянь. У лівій частині залишаємо члени з вибраними нами тільки що індексами, а решта переносимо в праву частину:

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

Ми отримали остаточні правила побудови коду, здатного виправляти всі одиночні і виявляти подвійні помилки:

Використовуючи правила побудови коригуючого коду (*), побудуємо таблицю дозволених комбінацій групового коду обсягом 9 слів, здатного виправляти всі одиночні і виявляти подвійні помилки. У колонку «безнадлишкових код» записуємо дев'ять (за завданням Q = 9) комбінацій за зростанням (нульову комбінацію не використовуємо).

Всі колонки, крім , , і , Вміст яких визначається формулами (*), заповнюємо цифрами з безнадлишкових коду:

Щоб заповнити колонки , , і , Підставляємо значення необхідних змінних у відповідні рівняння з (*). Наприклад, для рядка 9 (слово ) Отримуємо таке:

Перейдемо до побудови функціональної схеми кодує пристрої (див. відповідний малюнок нижче). Призначення кодує пристрої - внесення надмірності в код за заданими нами правилами. Схему будуємо на підставі рівностей (*). На схемі використовується логічний елемент «суматор за модулем два», позначений М2. На схемі є два регістри, побудовані на D-тригерах. Один з них містить безнадлишкових код і має розрядність 4 біт, так як , А інший містить надлишковий код і має розрядність 8 біт, так як . Принцип роботи схеми такий: за сигналом синхронізації на k-розрядний регістр надходить кодова комбінація, яка підлягає кодуванню. Потім за допомогою суматорів ця комбінація кодується (вноситься надмірність). Суматор С1 реалізує перший рівність з (*), суматор С2 - друге, С3 - третє, а С4 - четверте. І, нарешті, по сигналу синхронізації отриманий надлишковий код записується у 8-розрядний регістр. Далі починається кодування наступної комбінації.

Далі розглянемо функціональну схему декодуючого пристрою (див. відповідний малюнок нижче). У ній також використовуються два регістри на D-тригерах. Один з них містить передане слово і має розрядність 8 біт, так як , А інший містить декодовані інформаційні символи і має розрядність 4 біт, так як . Для побудови схеми згадаємо перевірочні рівності, знайдені раніше:

Позначимо літерою ознака одиночної помилки. Якщо , То мала місце одиночна помилка, якщо ж , То одиночної помилки не було. Через позначимо результат спільної перевірки на парність.

Запишемо алгоритм декодування, нехтуючи можливістю виникнення помилок кратності 3 і вище.

Принцип роботи дешифратора такий. На приймальний регістр надходить кодова комбінація, яка може містити помилки. Суматор С1 реалізує перший рівність з (**), С2 - друге, а С3 - третє. Якщо помилок не було, то на виходах цих трьох суматорів будуть нулі. Якщо ж мала місце помилка, то в цьому випадку на виходах суматорів з'явиться опізнавач помилки. Цей опізнавач передається в дешифратор помилок ДС, який на підставі переданого в нього опізнавач видає відповідний вектор помилки. Його схема будується за наступною таблицею істинності: