Визначення і способи задання групових кодів (стр. 1 из 3)
Зміст
Вступ
Елементи теорії кодування
Відстань Хеммінга
Матричне кодування
Групові коди
Досконалі і квазідосконалі коди
Висновки
Література
Використання електронно-обчислювальних машин для переробки інформації з'явилося корінним етапом у вдосконаленні систем планування і управління на всіх рівнях народного господарства. Проте при цьому, на відміну від звичайних способів збору і обробки інформації, виникли проблеми перетворення інформації в символи, зрозумілі для машини. Невід'ємним елементом цього процесу є кодування інформації.
У теорії передачі інформації надзвичайно важливим є вирішення проблеми кодування і декодування, що забезпечує надійну передачу по каналах зв'язку з «шумом».
Метою даної роботи є розглянути деякі питання кодування інформації по каналах зв'язку з перешкодами.
Передача інформації зводиться до передачі по якомусь каналу зв'язку символів деякого алфавіту. Проте в реальних ситуаціях сигнали при передачі практично завжди можуть спотворюватися, і переданий символ сприйматиметься неправильно. Наприклад, в системі ЕОМ → ЕОМ одна з обчислювальних машин може бути пов'язана з іншою через супутник. Канал зв'язку в цьому випадку фізично реалізується електромагнітним полем між поверхнею Землі і супутником. Електромагнітні сигнали, накладаючись на зовнішнє поле, можуть спотворитися і ослабитися. Для забезпечення надійності передачі інформації в таких системах розроблені ефективні методи, що використовують коди різних типів.
Одна з таких моделей зв’язана з груповими кодами.
Алфавіт, в якому записуються повідомлення, вважаємо за той, що складається з двох символів {0, 1}. Він називається двійковим алфавітом. Тоді повідомлення є кінцева послідовність символів цього алфавіту. Повідомлення, що треба передати, кодується по певній схемі довшою послідовністю символів в алфавіті {0, 1}. Ця послідовність називається кодом або кодовим словом. При прийомі можна виправляти або розпізнавати помилки, що виникли при передачі по каналу зв'язку, аналізуючи інформацію, що міститься в додаткових символах. Прийнята послідовність символів декодується по певній схемі в повідомлення, з великою вірогідністю співпадаюче з переданим.
Блоковий двійковий (m, n) -код визначається двома функціями: E:{0,1}m - {0, 1}n і D: {0, 1}n - {0, 1}m, де m . n і {0, 1}n - безліч всіх двійкових послідовностей довжини n. Функція E визначає схему кодування, а функція D - схему декодування. Математичну модель системи зв'язку можна представити у вигляді схеми (мал. 1):
Малюнок 1 – Модель системи зв'язку.
Тут T - «функція помилок» ; E і D вибираються так, щоб композиція D T E була функцією, з великою вірогідністю близькою до тотожної. Двійковий (m, n) -код містить 2m кодових слів.
Коди діляться на два великі класи: коди з виявленням помилок, які з великою вірогідністю визначають наявність помилки в прийнятому повідомленні, і коди з виправленням помилок, які з великою вірогідністю можуть відновити послане повідомлення.
Відстань Хеммінга
На безлічі двійкових слів довжини m відстанню d(а, b) між словами а і b називають число неспівпадаючих позицій цих слів, наприклад: відстань між словами а = 01101 і b = 00111 рівне 2.
Визначене таким чином поняття називається відстанню Хеммінга. Воно задовольняє наступним аксіомам відстаней:
1) d(а, b) 0 і d(а, b)= 0 тоді і тільки тоді, коли а = b;
2) d(а, b)= d(b, а);
3) d(а, b)+ d(b, з) d(а, з) (нерівність трикутника).
Вагою w(a) слова а називають число одиниць серед його координат. Тоді відстань між словами а і b є вага їх суми а b: d(а, b)= w(а b), де символом позначена операція покоординатного складання по модулю 2.
Інтуїтивно зрозуміло, що код тим краще пристосований до виявлення і виправлення помилок, чим більше розрізняються кодові слова. Поняття відстані Хеммінга дозволяє це уточнити.
Теорема. Для того, щоб код дозволяв виявляти помилки (або менш) позиціях, необхідно і достатньо, щоб найменша відстань між кодовими словами була
k + 1.Доведення цієї теореми аналогічно доказу наступного твердження.
Теорема. Для того, щоб код дозволяв виправляти всі помилки (або менш) позиціях, необхідно і достатньо, щоб найменша відстань між кодовими словами була
2k + 1.У математичній моделі кодування і декодування зручно розглядати рядки помилок. Дане повідомлення a = a1a2 ...am кодується кодовим словом b= b1b2...bn.. При передачі канал зв'язку додає до нього рядок помилок e=e1e2...en,, отже приймач приймає сигнал c = c1c2...cn, , де ci = bi + ei.. Система, що виправляє помилки, переводить слово c1c2...cn у найближче кодове слово b1b2 ...bn.. Система, що виявляє помилки, тільки встановлює, чи є прийняте слово кодовим чи ні. Останнє означає, що при передачі відбулася помилка.
Ідею представлення код, що коректують, можна представити за допомогою N-вимірного куба.
Візьмемо тривимірний куб (мал. 2), довжина ребер, в якому дорівнює одній одиниці. Вершини такого куба відображають двійкові коди. Мінімальна відстань між вершинами визначається мінімальною кількістю ребер, що знаходяться між вершинами. Ця відстань називається кодовою (або хемінговою) і позначається буквою d.
Малюнок 2 – Представлення двійкових код за допомогою куба
Інакше, кодова відстань - це те мінімальне число елементів, в яких одна кодова комбінація відрізняється від іншої. Для визначення кодової відстані досить порівняти дві кодові комбінації по модулю 2. Так, склавши дві комбінації
10110101101
11001010101
01111111000
визначимо, що відстань між ними d=7.
Для коду з N=3 вісім кодових комбінацій розміщуються на вершинах тривимірного куба. Такий код має кодову відстань d=1, і для передачі використовуються всі вісім кодових комбінацій 000,001..,111. Такий код є не перешкодостійким, він не в змозі виявити помилку.
Якщо виберемо комбінації з кодовою відстанню d=2, наприклад, 000,110,101,011, то такий код дозволить виявляти одноразові помилки. Назвемо ці комбінації дозволеними, призначеними для передачі інформації. Всі останні 001,010,100,111 - заборонені.
Будь-яка одиночна помилка приводить до того, що дозволена комбінація переходить в найближчу, заборонену комбінацію (див. мал. 2). Отримавши заборонену комбінацію, ми виявимо помилку. Виберемо далі вершини з кодовою відстанню d=3
Такий код може виправити одну одиночну помилку або виявити дві помилки. Таким чином, збільшуючи кодову відстань можна збільшити перешкодостійкість коди. У загальному випадку кодова відстань визначається по формулі
d=t + l + 1
де t - число помилок, що виправляються, l - число помилок, що виявляються. Зазвичай l>t.
Більшість кодів, що коректують, утворюються шляхом додавання до початкової k - комбінації r - контрольних символів. У результаті в лінію передаються n=k+r символів. При цьому коди, що коректують, називаються (n,k) кодами. Як можна визначити необхідне число контрольних символів?
Для побудови коди здатного виявляти і виправляти одиночну помилку необхідне число контрольних розрядів складатиме
. Це рівносильно відомому завданню про мінімум числа контрольних питань, на які можуть бути даны відповіді вигляду “та чи ні”, для однозначного визначення одного з елементів кінцевої множини.Якщо необхідно виправити дві помилки, то число різних результатів складатиме
Тоді 
, в цьому випадку виявляються одноразові і двократні помилки. У загальному випадку, число контрольних символів має бути не менше 
Ця формула називається нерівністю Хеммінга, або нижньою межею Хеммінга для числа контрольних символів.
Матричне кодування
При явному завданні схеми кодування в (m, n) -коде слід вказати 2m кодових слів, що вельми неефективно.
Одним з економних способів опису схеми кодування є методика матричного кодування.
Хай
- матриця порядку m f n з елементами eij, рівними 0 або 1. Символ + позначає складання по модулю 2. Тоді схема кодування задається системою рівнянь 
або в матричній формі b = aЕ, де a = a1a2...am - вектор, відповідний передаваному повідомленню; b = b1b2...bn - вектор, відповідний кодованому повідомленню; Е - матриця коду, що породжує.
Матриця коду, що породжує, визначена неоднозначно. Код не повинен приписувати різним словам-повідомленням одне і те ж кодове слово. Можна довести, що цього не відбудеться, якщо перші m стовпців матриці Е утворюють одиничну матрицю.
Замість 2m кодові слова досить знати m слів, що є рядками матриці Е.
Групові коди
Безліч всіх двійкових слів a=a1 … am довжини m утворює абелеву (комутативну) групу щодо порозрядного складання.
Хай E - кодуюча
-матрица, у якої є -підматриця з відмінним від нуля визначником, наприклад, одинична. Тоді відображення 
переводить групу всіх двійкових слів довжини m в групу кодових слів довжини n.