04 Завадостійке кодування

Мал. 1. Класифікація завадостійкого кодування

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

Для двійкового коду все безліч кодових комбінацій одно N = 2 n. де n - число розрядів в кодової комбінації. Це безліч розбивається на дві підмножини: дозволених кодових комбінацій і заборонених. Ці підмножини відомі як на передавальній, так і на приймальній сторонах.

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

При необхідності виправлення деяких виникають спотворень надходять у такий спосіб. Всі безліч кодових комбінацій N розбивають на N 0

Якщо прийнята комбінація А j входить в підмножина N 0j (A j N 0j), то приймається рішення, що передана комбінація A j. Тобто, якщо прийнята кодова комбінація залишилася в тому ж підмножині, що і передається, то прийом буде без помилки. якщо

кодова комбінація в результаті спотворень переходить в інше підмножина, то прийом буде з помилкою.

Мал. 2. Принцип виправлення виникаючих помилок

Коди, які не тільки виявляють помилку, але і вказують номер спотвореної позиції, називаються кодами з виправленням помилок. При використанні завадостійкого коду в каналі зв'язку передаються тільки дозволені кодові комбінації. Якби не було перешкод, то для передачі цих кодових комбінацій

треба було б менше число розрядів n 0. n 0 log 2 N 0 n.

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

2. виявляти і виправляти здатність кодів

Розглянемо можливість виявлення та виправлення помилок на простому прикладі. Припустимо, що інформація передається однорозрядним двійковим кодом. Тобто передається інформація 0 або 1. Число можливих кодових комбінацій N 0 = 2 n 0. де n 0 = 1, N 0 = 2 1 = 2. У кожної кодової комбінації додамо ще один розряд: n = n 0 + 1 = 1 + 1 = 2. Число кодових комбінацій N = 2 n = 2 2 = 4. Ці комбінації складають безліч, що складається з 00, 01, 10, 11. Це безліч розділимо на два підмножини дозволених і заборонених комбінацій. До числа дозволених віднесемо ті комбінації, у яких сума одиниць завжди парна. Дозволеними виберемо такі комбінації, які відрізняються один від одного двома розрядами - це 00 і 11. При такому виділенні дозволених комбінацій будь-яка одиночна (або непарна) помилка буде змінювати число одиниць на непарне. Прийнята кодова комбінація в цьому випадку переходить в підмножина заборонених і помилка буде виявлена.

Якщо в кодову комбінацію ввести кількість додаткових розрядів, то можна не тільки виявляти, але і виправляти помилки. Якщо дозволені комбінації визначити таким чином, що будь-які з них відрізняються один від одного не менш ніж трьома розрядами, то одиночна помилка може бути виправлена. Можливість виправлення одиночної помилки в цьому випадку пов'язана з тим, що помилкова комбінація буде відрізнятися від справжньої тільки одним розрядом і залишиться в області, що відноситься до переданої дозволеної комбінації.

Розглянемо сказане на геометричній моделі трехразрядного двійкового коду за допомогою якого можна одержати 2 3 = 8 комбінацій. А саме: 000, 001, 010, 011, 100, 101, 110, 111. Кожну нову комбінацію можна уявити точкою в тривимірному просторі (рис. 3).

Для виправлення одиночної помилки розіб'ємо все безлічі комбінацій на дві області, і будемо передавати тільки дві кодові комбінації 111 і 000. Ці комбінації відрізняються один від одного трьома розрядами. Будь-які одинарні помилка залишає кодову комбінацію в області, що відноситься до переданої комбінації. Так, при спотворенні одного розряду в комбінації 000 вона перетвориться в 001, або в 100, або в 010. Всі ці

а = (а 0. a 1. a n-1); b = (b 0. b 1. b n-1).

Користуючись відстанню Хеммінга як метрикою в множині кодових слів можна виділити зони виправлення і виявлення помилок.

Затвердження. Якщо код використовується тільки для виявлення помилок, то, щоб виявити в кодовому слові довільну комбінацію з s помилок, необхідно і достатньо, щоб відстань Хеммінга для будь-яких двох дозволених кодових слів було на 1 більше, ніж s (кількість виявлених помилок): d min a . b s 1

Відповідно до твердження в даному прикладі можуть бути виявлені помилки кратні s = 1 і s = 2. При s = 3 передана кодова комбінація переходить в іншу дозволену комбінацію. Помилка не виявляється.

Затвердження. Якщо код використовується тільки для виправлення помилок, то, щоб виправити t помилок необхідно і досить, щоб d min a. b 2 t 1.

Затвердження. Для того, щоб виправити t і виявити s помилок в кодовому слові, необхідно і достатньо, щоб d min a. b

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

3. Блокові перешкодостійкі коди

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

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

Шляхом елементарних перетворень (перестановкою рядків; заміною рядки сумою цього рядка з будь-якої іншої рядком, перестановкою стовпців) породжує матриця може бути перетворена до канонічної формі:

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

тобто S 000. Якщо ж який-небудь символ буде прийнятий з спотворенням, то синдром збігається зі стовпцем перевірочної матриці і вкаже на номер розряду (символу в кодовому слові), який прийнятий з помилкою.

Для виправлення помилки потрібно до символу розряду в якому сталася помилка додати одиницю по модулю два.

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

При декодуванні кодом Хеммінга використовується синдромное декодування.

Для породжує матриці виду (3),

перевірочна матриця має канонічний

Перевірочна матриця H складається з 2-х підматриць:

r - транспонованою матриці, яка визначається з породжує матриці;

- одиничної матриці розмірністю r

Властивість перевірочної матриці: твір закодованого слова (дозволеної кодової комбінації) на транспоновану перевірочну матрицю одно нуль-вектору:

b 0. b 1. b 2. b k 1. a 0. a 1. a r 1 H T 0,0. 0 r 1.

Перевірочна і породжує матриці пов'язані виразом:

де С b 0 b 1 b 2 b 3 _ a 0 a 1 a 2 - прийняте повідомлення;

H T - транспонована перевірочна матриця.

Згідно з правилом множення вектора на матрицю елементи синдрому будуть визначатися виразами:

S 0 b 1 b 2 b 3 a 0. S 1 b 0 b 2 b 3 a 1. S 2 b 0 b 1 b 3 a 2.

Якщо кодове слово буде прийнято без спотворень, то синдром буде дорівнює нулю,

Якщо ж який-небудь символ буде прийнятий з спотворенням, то синдром вкаже на номер елемента в кодовому слові, який прийнятий помилково.

Вектор помилок це кодова комбінація, яка ставиться у відповідність синдрому і містить одиницю в тому розряді, де сталася помилка, і нулі у всіх інших розрядах. Складемо таблицю відповідності синдрому і вектора помилок:

Таблиця відповідності вектора помилки синдрому повідомлення