Коригувальні коди - Студопедія
Коригуючими називаються коди, що дозволяють виявляти і виправляти помилки. Ідею подання коригувальних кодів можна подати за допомогою N-мірного куба. Візьмемо тривимірний куб (рис.5.3), довжина ребер, у якому дорівнює одній одиниці. Вершини такого куба відображають двійкові коди. Мінімальна відстань між вершинами визначається мінімальною кількістю ребер, що знаходяться між вершинами. Ця відстань називається кодовою (або хемінговою) і позначається буквою d.
Рис.5.3. Подання двійкових кодів за допомогою куба
Інакше, кодова відстань - це мінімальна кількість елементів, в яких одна кодова комбінація відрізняється від іншої. Для визначення кодової відстані достатньо порівняти дві кодові комбінації за модулем 2. Так, склавши дві комбінації
визначимо, що відстань з-поміж них d=7.
Для коду N=3 вісім кодових комбінацій розміщуються на вершинах тривимірного куба. Такий код має кодову відстань d=1, і передачі використовуються всі вісім кодових комбінацій 000,001. 111. Такий код є не на заваді стійким, він не в змозі виявити помилку.
Якщо виберемо комбінації з кодовою відстанню d=2, наприклад, 000,110,101,011, такий код дозволить виявляти одноразові помилки. Назвемо ці комбінації дозволеними, призначеними передачі інформації. Решта 001,010,100,111 - заборонені.
Будь-яка одиночна помилка призводить до того, що дозволена комбінація перетворюється на найближчу, заборонену комбінацію (див. рис.5.3). Отримавши заборонену комбінацію, ми виявимо помилку. Виберемо далі вершини з кодовою відстанню d=3
Такий код може виправити одну помилку або виявити дві помилки. Таким чином, збільшуючи кодову відстаньможна збільшити завадостійкість коду. У загальному випадку кодова відстань визначається за формулоюd=t + l + 1деt- число помилок, що виправляються,l- число виявлених помилок. Зазвичайl>t.
Більшість коригувальних кодів є лінійними кодами. Лінійні коди - це коди, у яких контрольні символи утворюються шляхом лінійної комбінації інформаційних символів. Крім того, коригувальні коди є груповими кодами. Групові коди (Gn) - це коди, які мають одну основну операцію. При цьому повинна дотримуватися умова замкнутості (тобто при складанні двох елементів групи виходить елемент, що належить цій же групі). Число розрядів у групі не повинно збільшуватись. Цій умові задовольняє операція порозрядного додавання по модулю 2. У групі, крім того, має бути нульовий елемент.
Приклад 5.3.Нижче наведено кодові комбінації, які є групою чи ні.
1) 1101 1110 0111 1011 – не група, тому що немає нульового елемента
2) 0000 1101 1110 0111 – не група, тому що не дотримується умова замкнутості (1101+1110=0011)
3) 000 001 010 011 100 101 110 111 - група
4) 000 001 010 111 – підгрупа
Більшість коригувальних кодів утворюються шляхом додавання до комбінації r – контрольних символів. У результаті лінію передаються n=k+r символів. У цьому коригувальні коди називаються (n,k) кодами. Як визначити необхідну кількість контрольних символів?
Для побудови коду здатного виявляти та виправляти одиночну помилку необхідне число контрольних розрядів становитиме
. Це рівнозначно відомому завданню про мінімум кількості контрольних питань, на які можуть бути надані відповіді виду “так” чи “ні”, для однозначного визначення одногоз елементів кінцевої множини.
Якщо необхідно виправити дві помилки, то кількість різних результатів складатиме тоді , в цьому випадку виявляються одноразові та дворазові помилки. У загальному випадку число контрольних символів має бути не менше
(5.1)
Ця формула називається нерівністю Хеммінгу, а вивченням коду Хеммінгу ми займемося на наступній лекції
Чи не знайшли те, що шукали? Скористайтеся пошуком:
Вимкніть adBlock! і оновіть сторінку (F5)дуже потрібно