Коригувальні коди
Коригуючими називаються коди, які дозволяють виявляти помилки та виправляти їх на приймальній стороні, не вдаючись до повторної передачі помилкових кодових комбінацій.
Виходячи з основних параметрів та способів кодування та декодування, коригувальні коди в першу чергу можна розділити на блокові та безперервні.
Блокові коди характеризуються тим, кожна кодова комбінація складається з двох частин (блоків), перша складається з інформаційних символів, друга – з контрольних. Особливістю безперервних кодів є те, що кодова комбінація не поділяється на блоки, а контрольні символи розміщуються за певним правилом між інформаційними.
Для коригувальних кодів справедлива нерівність
N=Km
деМ– кількість повідомлень;N– кількість кодових комбінацій;К– основа коду;
m– довжина кодової комбінації:m=n+k;n- число інформаційних розрядів,k- число контрольних розрядів, що забезпечують локалізацію та виправлення спотворених елементів кодової комбінації.
Число контрольних розрядів, необхідні виявлення і виправлення одноразових помилок, визначимо шляхом наступних міркувань. При передачі будь-якогоМповідомлень може бути спотворений будь-який зmелементів кодової комбінації або повідомлення буде передано правильно. Отже, можливіm+1виходів. Використовуючи контрольних розрядів необхідно розрізнити всі ці результати. За допомогою kрозрядів можна закодувати 2kвиходів. Отже, має виконуватися умова
Наприклад, якщоМ = 10, то відповідно до рівностіM=Knотримуємоn3,3 = 4. Щоб мати можливість виявляти помилковікодові комбінації та виправляти їх слід додатиkконтрольних розрядів відповідно до виразу:
За виконання рівності отримаємо
При цьому надмірність коду складе
Коди виявляють помилки повинні мати кодову відстаньd= 2. Визначимо, чому має дорівнювати кодова відстань у коригувальних кодів. При цьому поставимо умову, що в одній кодовій комбінації не може виникнути більше однієї помилки. Вираз визначення кодової відстані матиме вид:
деα– кратність виявлених помилок,
β– кратність помилок, що виправляються,
1– кодова відстань для оптимального коду;
Розглянемо цю формулу з прикладу рівномірного трехразрядного коду.
Приα =0,β = 0d=1. Цей результат відповідає рівномірному оптимальному коду. Його кодові комбінації:000, 001, 010, 100, 110, 101, 011, 111.
При цьому надмірність коду дорівнює
Приα = 1,β = 0d=2. Цей результат відповідає рівномірному коду, що виявляє одноразову помилку. Його кодові комбінації:001, 010, 101, 110.
При цьому надмірність коду дорівнює.
Приα = 1,β = 1d=3. Цей результат відповідає рівномірному оптимальному коду. Його кодові комбінації:000, 111.
При цьому надмірність коду дорівнює.
Загальний алгоритм побудови блокових кодів, що коригують одноразові помилки
Залежно від необхідної розрядності коду записується поодинока матриця(n
За допомогою цієї матриці можна записати всекомбінації n-розрядного оптимального коду
Щоб утворити на підставі цієї матриці код, що коригує одноразову помилку, необхідно розширити її доmрозрядів, тобто(n
Отримана матриця називається производящей. Шляхом підсумовування модулем 2 рядків цієї матриці можна отримати рівномірний надлишковий код. У цьому коді виділено інформаційну та сервісну частини, тому такий код називається систематичним.
До матриціАвисуваються такі вимоги:
Оскільки синтезуватиметься надмірний рівномірний систематичний код, що дозволяє виявити та скоригувати одноразову помилку, то відстань між кодовими комбінаціями має бути:d
Відмінність між рядками в матриці, що приписується, повинна бути не менш ніж у(d- 2)розрядах, т.к. відмінність у одиничній матриці у двох рядках вже є.
Кодові комбінації, що передаються, на приймальній стороні повинні бути піддані контролю з метою виявлення наявності або відсутності помилки в будь-якому місці кодової комбінації. Для цього на приймальній стороні використовують перевірочну матрицю, завдання якої полягає у виявленні помилки та вказівці її розташування.
Перевірна матриця будується наступним чином: до одиничної матриці розміромk
До матриціПпред'являється така вимога.
Сума одиниць за модулем2будь-якого рядка перевірочної матриці повинна бути парним числом (або у всіх рядках непарна), т.к. сума за модулем2дорівнює нулю при парності. Це є умовою виявлення та локалізації помилки у будь-якій кодовій комбінації. Локалізація помилки заснована на індивідуальній кодовій комбінації (розпізнавачах), і ця кодова комбінація представляється у виглядіf0f1f2…fk-1(кількість контрольних розрядів)
Приклад: потрібно побудувати систематичний код, що дозволяє виявити помилкове відображення будь-якого числа від0до9на семисегментному індикаторі та виправити його.
Відповідно до умови завдання кількість відображених чисел (повідомлень)М = 10. Для представлення цих чиселn= 4,k= 3. Складемо матрицю, що виробляє.
Виконується умова: щонайменше(d-1)одиниць. З цієї матриці можна побудувати16кодових комбінацій з розрядністю. Складемо10кодових комбінацій, які будуть необхідні для індикації потрібних цифр. Нехай це будуть такі комбінації:
Перші чотири кодові комбінації – це рядки матриці А. Останні 6 кодових комбінацій є сумами рядків за модулем2, відповідно:
Будуємо перевірну матрицю
На підставі перевірочної матриці можна скласти рівняння кодів-розпізнавачів розташування помилки:
Послідовністьf0f1f2є кодом помилкової або безпомилкової комбінації
Якщо кодова комбінація не містить помилок, то згідно з (*) всі позиції будуть містити нулі, отже, вийде кодf0f1f2=0 0 0.
Розглянемо підкреслену кодову комбінацію1 0 1 0 1 0 1і почнемо послідовно вводити помилки.
Вводимо помилку в розрядa0і отримуємо код розпізнавача помилки в цьому розряді:
Потім вводимо помилку в розряда1і отримуємо код розпізнавача помилки у цьому розряді; потім вводимо помилкуа2і отримуємо код розпізнавателя помилки в цьому розряді і т.д.
У результаті отримуємо таблицю кодів розпізнавачів помилок:
Перевіримо результат, що вийшов. Нехай передали комбінацію1000011, а отримали1001011. Визначаємо код розпізнавача:
Недоліком такого способу є те, що коди розпізнавачів помилок не відповідають десятковим числам.