Курс: Теорія інформації та кодування
Тема: Коригувальні КОДИ
Зміст
1. Коригувальні КОДИ. ОСНОВНІ ПОНЯТТЯ
2. ЛІНІЙНІ ГРУПОВІ КОДИ
3. Код Хеммінга
Список Літератури
1. Коригувальні КОДИ. ОСНОВНІ ПОНЯТТЯ
Відповідно до теоремою Шеннона для дискретного каналу з завадами, ймовірність помилки при передачі даних по каналу зв'язку може бути як завгодно малої при виборі відповідного методу кодування сигналу, тобто перешкода не накладає суттєвих обмежень на точність передачі інформації (даних). Достовірність переданої інформації може бути забезпечена застосуванням коригувальних кодів.
завадостійкості або коригуючими кодами називаються коди, що дозволяють виявити і усунути помилки при передачі інформації через впливу перешкод.
Найбільш поширеним є клас кодів з корекцією одиночних і виявленням подвійних помилок (КО-ОД). Самим відомих серед цих кодів є код Хеммінга, що має простий і зручний для технічної реалізації алгоритм виявлення та виправлення одиночної помилки.
У ЕОМ ці коди використовуються для підвищення надійності оперативної пам'яті (ОП) та магнітних дисків. Число помилок в ЕОМ залежить від типу несправностей елементів схем (наприклад, несправність одного елемента інтегральної схеми (ІС) викликає одиночну помилку, а всій ІС ОП - кратну). Для виявлення кратних помилок використовується код КО-ОД-ООГ (корекція одиночної, виявлення подвійної та виявлення кратної помилки в однойменній групі бітів).
Серед коригувальних кодів широко використовуються циклічні коди, в ЕОМ ці коди застосовуються при послідовній передачі даних між ЕОМ і зовнішніми пристроями, а також при передачі даних по каналах зв'язку. Для виправлення двох і більше помилок ( d 0 Ві 5 ) використовуються циклічні коди БЧХ (Боуза - Чоудхурі - хоквінгема), а також Ріда-Соломона, які широко використовуються в пристроях цифрового запису звуку на магнітну стрічку або оптичні компакт-диски і дозволяють здійснювати корекцію групових помилок. Здатність коду виявляти і виправляти помилки досягається за рахунок введень надмірності в кодові комбінації, тобто кодовою комбінаціям з до двійкових інформаційних символів, що надходять на вхід кодує пристрої, відповідає на виході послідовність з n двійкових символів (такий код називається ( n, k ) - кодом).
Якщо N 0 = 2 n - загальне число кодових комбінацій, а N = 2 k - число дозволених, то число заборонених кодових комбінацій одно
N 0 -N = 2 n -2 k .
При цьому число помилок, яке призводить до забороненої кодової комбінації одно:
, (1)
де S - кратність помилки, тобто кількість спотворених символів в кодової комбінації S = 0, 1, 2, ...
C n i - поєднання з n елементів по i , обчислюється за формулою:
, (2)
для S = 0;
S = 1;
S = 2;
S = 3; і т. д.
Для виправлення S помилок кількість комбінацій кодового слова, складеного з m перевірочних розрядів N = 2 m , має бути більше можливого числа помилок (2), при цьому кількість виявлених помилок в два рази більше, ніж виправляються
(3)
2 m Ві звідки.
Для одиночної помилки, як найбільш вірогідною.
В залежності від вихідних даних коду ( n або k ) можна використовувати
формули
. (4)
При цьому, m = [log 2 (1 + n)] або m = [log 2 {(k +1) + [log 2 (k +1)]}], де ква-дратние дужки позначають округлення до більшого цілого.
У таблиці 1 наведені співвідношення між довжиною кодової комбінації і кількістю інформаційних та контрольних розрядів для коду исправляющего одиночну помилку, а також ефективність використання каналу зв'язку.
Для виправлення дворазової помилки
або. (5)
Введення надмірності в кодові комбінації при використанні коригувальних кодів істотно знижує швидкість передачі інформації та ефективність використання каналу зв'язку.
Наприклад, для коду (31, 26) швидкість передачі інформації дорівнює
,
т. е. швидкість передачі зменшується на 16%.
Таблиця 1
n
7
10
15
31
63
127
255
k
4
6
11
26
57
120
247
m
3
4
4
5
6
7
8
0,57
0,6
0,75
0,84
0,9
0,95
0,97
Як видно з таблиці 1, чим більше n, тим ефективніше використовується канал.
Приклад 1. Визначити кількість перевірочних розрядів для систематичного коду исправляющего одиночну помилку і складається з 20 інформаційних розрядів.
Рішення: Загальна довжина кодової комбінації дорівнює n = k + m, де k - кількість інформаційних розрядів, а m - перевірочних розрядів.
Для виявлення подвійної та виправлення одиночної помилки залежності для розрядів мають вигляд, при цьому
m = [log 2 {(k +1) + [Log 2 (k +1)]}] = [log 2 {(20 +1) + [log 2 (20 +1 )]}] = 5,
т. тобто отримаємо (25, 20)-код.
2. ЛІНІЙНІ ГРУПОВІ КОДИ
Лінійним називається код, в якому перевірочні символи представляють собою лінійні комбінації інформаційних. Груповим називається код, який утворює алгебраїчну групу по відношенню операції додавання по модулю два.
Властивість лінійного коду : сума (різниця) кодових векторів линів-ного коду дає вектор, що належить цьому коду. Властивість групового коду: мінімальна кодова відстань між кодовими векторами одно мінімальної ваги ненульових векторів. Вага кодового вектора дорівнює числу одиниць в кодової комбінації.
Групові коди зручно задавати за допомогою матриць, розмірність яких визначається параметрами k і n . Число рядків одно k, а число стовпців дорівнює n = k + m.
. (6)
Коди, породжувані цими матрицями, називаються ( n, k )-кодами, а відповідні їм матриці породжують (Утворюючими, що виробляють). Породжує матриця G складається з інформаційної I kk і перевірочної R km матриць. Вона є стислим описом лінійного коду і може бути представлена в канонічній (типової) форми
. (7...
