Зміст
Вступ
Елементи теорії кодування
Відстань Хеммінга
Матричне кодування
Групові коди
Досконалі і квазідосконалі коди
Висновки
Література
Вступ
Використанняелектронно-обчислювальних машин для переробки інформації з'явилося корінниметапом у вдосконаленні систем планування і управління на всіх рівнях народногогосподарства. Проте при цьому, на відміну від звичайних способів збору іобробки інформації, виникли проблеми перетворення інформації в символи,зрозумілі для машини. Невід'ємним елементом цього процесу є кодуванняінформації.
У теорії передачіінформації надзвичайно важливим є вирішення проблеми кодування і декодування,що забезпечує надійну передачу по каналах зв'язку з «шумом».
Метою даноїроботи є розглянути деякі питання кодування інформації по каналах зв'язку зперешкодами.
Елементи теорії кодування
Передачаінформації зводиться до передачі по якомусь каналу зв'язку символів деякогоалфавіту. Проте в реальних ситуаціях сигнали при передачі практично завждиможуть спотворюватися, і переданий символ сприйматиметься неправильно.Наприклад, в системі ЕОМ → ЕОМ одна з обчислювальних машин може бутипов'язана з іншою через супутник. Канал зв'язку в цьому випадку фізичнореалізується електромагнітним полем між поверхнею Землі і супутником.Електромагнітні сигнали, накладаючись на зовнішнє поле, можуть спотворитися іослабитися. Для забезпечення надійності передачі інформації в таких системахрозроблені ефективні методи, що використовують коди різних типів.
Одна з такихмоделей зв’язана з груповими кодами.
Алфавіт, в якомузаписуються повідомлення, вважаємо за той, що складається з двох символів {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.
Припустимо, що
/>.
Тоді для b=b1…bn=aE,/>, отримуємо
/>
тобто /> . Отже, взаємно-однозначневідображення групи двійкових слів довжини m за допомогою заданої матриці Eзберігає властивості групової операції, що означає, що кодові слова утворюютьгрупу.
Блоковий кодназивається груповим, якщо його кодові слова утворюють групу.
Більшість код, щокоректують, є лінійними кодами. Лінійні коди — це такі коди, у яких контрольнісимволи утворюються шляхом лінійної комбінації інформаційних символів. Крімтого, що коректують коди є груповими кодами. Групові коди (Gn) — цетакі коди, які мають одну основну операцію. При цьому, повинна дотримуватисяумова замкнутості (тобто, при складанні двох елементів групи виходить елементщо належить цій же групі). Число розрядів в групі не повинне збільшуватися. Ційумові задовольняє операція порозрядного складання по модулю 2. У групі, крімтого, має бути нульовий елемент.
Наприклад, нижчеприведені кодові комбінації, що є групою чи ні.
1) 1101 1110 01111011 – не група, оскільки немає нульового елементу
2) 0000 1101 11100111 – не група, оскільки не дотримується умова замкнутості (1101+1110=0011)
3) 000 001 010011 100 101 110 111 — група
4) 000 001 010 111- підгрупа
Якщо код єгруповим, то найменша відстань між двома кодовими словами дорівнює найменшійвазі ненульового слова.
Це витікає ізспіввідношення /> .
При використаннігрупової коди непоміченими залишаються ті і лише ті помилки, які відповідаютьрядкам помилок, в точності рівним кодовим словам.
Такі рядкипомилок переводять одне кодове слово в інше.
Отже,вірогідність того, що помилка залишиться невиявленою, дорівнює сумівірогідності всіх рядків помилок, рівних кодовим словам.
Розглянемозавдання оптимізації декодування групової коди з двійковою матрицею кодуванняЕ. Требуєтся мінімізувати вірогідність того, що /> .
Схема декодуванняскладається з групи G всіх слів, які можуть бути прийняті (#G=2n).Оскільки кодові слова B утворюють нормальну (нормальність виходить зкомутативності G) підгрупу G, то безлічі G можна додати структуру таблиці:записуватимемо в один рядок ті елементи G, які є членами одного суміжного класуG по B. Перший рядок, відповідний нульовому слову з G, буде тоді всіма кодовимисловами з B, тобто />. У загальномувипадку, якщо />, то рядок, щомістить gi (суміжний клас giB ), має вигляд
/>.
Лідером кожного зтаких побудованих суміжних класів називається слово мінімальної ваги.
Кожен елемент g зG однозначно представляється у вигляді суми gi+bj де /> - лідер відповідногосуміжного класу і />.
Безліч класівсуміжності групи утворюють чинник-групу, яка є чинник-множина безлічі G повідношенню еквівалентності-приналежності до одного суміжного класу, а цеозначає, що множини, складові це чинник-множина, утворюють розбиття G. Звідсивитікає, що рядки побудованої таблиці попарно або не перетинаються, абозбігаються.
Якщо в данійтаблиці в першому стовпці записати лідери, то отримана таблиця називаєтьсятаблицею декодування. Вона має вигляд:
/>
Те, що рядківбуде 2n-m виходить з теореми Лагранжа1), оскільки 2n-m — це порядокфактор-группы G/B #(G/B)=#(G)/#(B), #B=2m.
Декодування словаg=bj+gi полягає у виборі кодового слова bj якпереданий і подальшому застосуванні операції, зворотної множенню на E. Такасхема декодування зможе виправляти помилки.
Для (3,6) -кода зданого прикладу таблиця декодування буде наступною:000000 100110 010011 110101 001111 101001 011100 111010 100000 000110 110011 010101 101111 001001 111100 011010 010000 110110 000011 100101 011111 001101 001100 101010 001000 101110 011011 111101 000111 100001 010100 110010 000100 100010 010111 110001 001011 101101 011000 111110 000010 100100 010001 110111 001101 101011 011110 111000 000001 100111 010010 110100 001110 101000 011101 111011 000101 100011 010110 11000 001010 101100 011001 111111
Перший рядок вній — це рядок кодових слів, а перший стовпець — це лідери.
Щоб декодувати словоbj+e, слід відшукати його в таблиці і вибрати як переданого слово втому ж стовпці і в першому рядку.
Наприклад, якщоприйнято слово 110011 (2-й рядок, 3-й стовпець таблиці), то вважається, що булопередане слово 010011; аналогічно, якщо прийнято слово 100101 (3-й рядок, 4-йстовпець таблиці), за передане вважається слово 110101, і так далі
Групове кодуванняз схемою декодування за допомогою лідерів виправляє всі помилки, рядки якихзбігаються з лідерами. Отже, вірогідність правильного декодування переданої подвійковому симетричному каналу коди дорівнює сумі вірогідності всіх лідерів,включаючи нульовий.
У розглянутійсхемі вірогідність правильної передачі слова буде
p6+6p5q+p4q2.
Кодове словобудь-якого стовпця таблиці декодування є найближчим кодовим словом до всіхінших слів даного стовпця.
Хай переданеслово bi прийняте як bi+e, d(bi,bi+e)=u(e),тобто ця відстань дорівнює вазі відповідного лідера. Відстань від bi+eдо будь-якого іншого кодового слова bj дорівнює вазі їх порозрядноїсуми, тобто
/>
оскільки e- лідерсуміжного класу, до якого належать як bk+e, так і bi+e.
Доведено, присхемі декодування лідерами по отриманому слову береться найближче до ньогокодове.Досконалі і квазідосконалі коди
Груповий /> -код, що виправляє всіпомилки ваги, не більшої k, і ніяких інших, називається досконалим.
Властивостідосконалого коду:
1. Длядосконалого /> -кода, що виправляє всіпомилки ваги, не більшої k, виконується співвідношення /> . Вірно і зворотне твердження;
2. Досконалийкод, що виправляє всі помилки ваги, не більшої k, в стовпцях таблицідекодування містить всі слова, віддалені від кодових на відстані, не більшому k.Вірно і зворотне твердження;
3. Таблицядекодування досконалого коду, що виправляє всі помилки в не більше ніж kпозиціях, має як лідерів всі рядки, що містять не більш k одиниць. Вірно ізворотне твердження.
Досконалий код — це кращий код, що забезпечує максимум мінімальної відстані між кодовими словамипри мінімумі довжини кодових слів. Досконалий код легко декодувати: кожномуотриманому слову однозначно ставиться у відповідність найближчу кодову. Чиселm, n і />, що задовольняють умовідосконалості коди, дуже мало. Але і при підібраних m, n і k досконалий кодможна побудувати тільки у виняткових випадках.
Якщо m, n і k незадовольняють умові досконалості, то кращий груповий код, який їм відповідає,називається квазідосконалим, якщо він виправляє всі помилки кратності, небільшої k, і деякі помилки кратності k+1. Квазідосконалі код також дуже мало.
Двійковийблоковий /> -код називаєтьсяоптимальним, якщо він мінімізує вірогідність помилкового декодування.Досконалий або квазідосконалий код — оптимальний. Загальний спосіб побудовиоптимальних код поки невідомий.
Для будь-якогоцілого позитивного числа r існує досконалий /> -код,що виправляє одну помилку, званий кодом Хеммінга (Hamming), в якому /> і /> .
Дійсно
/> .
Порядок побудовикоди Хеммінга наступний:
1. Вибираємоціле позитивне число r. Повідомлення будуть словами довжини />, а кодові слова — довжини /> ;
2. У кожномукодовому слові /> r біт зіндексами-ступенями двійки /> - єконтрольними, останні — в природному порядку — бітами повідомлення. Наприклад,якщо r=4, то биті /> - контрольні, а /> - з початковогоповідомлення;
3. Будуєтьсяматриця M з /> рядків і r стовпців. У i-омурядку стоять цифри двійкового представлення числа i. Матриці для r=2, 3 і 4такі:
/>
4. Записуєтьсясистема рівнянь bM=0, де M — матриця з попереднього пункту. Система складаєтьсяз r рівнянь. Наприклад, для r=3
/>
5. Щобзакодувати повідомлення а, беруться як bj, j не дорівнює ступенюдвійки, відповідні біти повідомлення і відшукуються, використовуючи отриманусистему рівнянь, ті bj, для яких j- ступінь двійки. У кожне рівняннявходить тільки одне bj, j=2j. У виписаній системі b4входить в 1-е рівняння, b2 — в друге і b1 — в третє. Урозглянутому прикладі повідомлення a=0111 буде закодовано кодовим словомb=0001111.
Декодування кодуХеммінга проходить за наступною схемою. Хай прийнято слово b+e, де b — переданекодове слово, а e — рядок помилок. Оскільки bM=0, то (b+e) M=bM+eM=eM. Якщорезультат нульовий, як відбувається при правильній передачі, вважається, щопомилок не було. Якщо рядок помилок має одиницю в і -ій позиції, то результатоммноження eM буде i-й рядок матриці M або двійкове представлення числа i. Вцьому випадку слід змінити символ в i-й позиції слова
Код Хеммінга — цегруповий код. Це витікає з того, що (m, n) -код Хеммінга можна отриматиматричним кодуванням, за допомогою /> -матрицы, в якій стовпці з номерамине ступенями 2 утворюють одиничну підматрицю. Решта стовпців відповідаєрівнянням кроку 4 побудови коди Хеммінга, тобто 1-у стовпцю відповідає рівняннядля обчислення 1-го контрольного розряду, 2-у — для 2-го, 4-у — для 4-го і такдалі Така матриця при кодуванні копіюватиме біти повідомлення у позиції неступеня 2 коди і заповнювати інші позиції коди згідно схемі кодування Хеммінга.
До (m, n) -кодуХеммінга можна додати перевірку парності. Вийде (m, n+1) -код з найменшою вагоюненульового кодового слова 4, здатний виправляти одну і виявляти дві помилки.
Коди Хеммінганакладають обмеження на довжину слів повідомлення: ця довжина може бути тількичислами вигляду 2r-r-1: 1, 4, 11, 26, 57… Але в реальних системахінформація передається байтам або машинними словами, тобто порціями по 8, 16,32 або 64 бита, що робить використання досконалих кодів не завжди відповідним.Тому в таких випадках часто використовуються квазідосконалі коди.
Квазідосконалі(m, n) -коды, що виправляють одну помилку, будуються таким чином. Вибираєтьсямінімальне n так, щоб />
Кожне кодовеслово такої коди міститиме k=n-m контрольних розрядів. З попередніхспіввідношень виходить, що
/>
Кожному з nрозрядів привласнюється зліва-направо номер від 1 до n. Для заданого словаповідомлення складаються k контрольних сум S1,…,Sk помодулю 2 значень спеціально вибраних розрядів кодового слова, які поміщаються впозиції-ступені 2 в ньому: для /> вибираютьсярозряди, що містять біти початкового повідомлення, двійкові числа-номери якихмають в i-м розряді одиницю. Для суми S1 це будуть, наприклад,розряди 3, 5, 7 і так далі, для суми S2 — 3, 6, 7 і так далі Такимчином, для слова повідомлення a=a1…am буде побудованокодове слово b=S1S2a1S3a2a3a4S4a5...am…Позначимо через /> суму по модулю 2розрядів отриманого слова, відповідних контрольній сумі Si і самійцієї контрольної суми. Якщо />, товважається, що передача пройшла без помилок. У разі одинарної помилки /> дорівнюватиме двійковомучислу-номеру збійного біта. У разі помилки, кратності більшої 1, коли />, її можна виявити. Подібнасхема декодування не дозволяє виправляти деякі подвійні помилки, чого можнабуло б досягти, використовуючи схему декодування з лідерами, але остання значноскладніше в реалізації і дає незначне поліпшення якості коди.
Приклад побудовикодового слова квазідосконалого (9, n) -кода, що виправляє всі одноразовіпомилки, для повідомлення 100011010.
/>
Шукане кодовеслово має вигляд1 2 3 4 5 6 7 8 9 10 11 12 13
S1
S2 1
S3
S4 1 1 1
Далі потрібнообчислити контрольні суми.
/>
Таким чином,шуканий код — 0011000111010. Якщо в процесі передачі цієї коди буде зіпсованиййого п'ятий біт, то приймач отримає код 0011100111010. Для його декодування зновуобчислюються контрольні суми:
/>
Приймачперетворить зміною п'ятого біта отримане повідомлення у відправленепередавачем, з якого потім відкиданням контрольних розрядів відновлює початковеповідомлення.
Досконалий кодХеммінга також можна будувати за розглянутою схемою, оскільки для нього /> .
Для виправленняодинарної помилки до 8-розрядного коду досить приписати 4 розряди />, до 16-розрядного — 5, до32-розрядного — 6, до 64-розрядного — 7.
Висновки
1. Передачаінформації по каналах зв'язку найчастіше пов'язана з рішенням задачіперешкодостійкого кодування. При цьому групове кодування є одним з можливихваріантів рішення даної задачі.
2. Коди, щовиявляють помилку, і коди, що коректують, обов'язково мають додаткові символи(надмірні).
3. Матричнекодування є одним з економних способів опису схеми кодування.
4. Груповийкод – це блоковий код, у якого кодові слова утворюють групу.
5. Одними знайбільш поширених перешкодостійких кодів є коди Хеммінга.
6. Уреальних системах для кодування інформації застосовується квазідосконалекодування.
Література
1. Чисар И.,Кернер Я. Теория информации. М.: Мир, 1985
2. БлейхерР. Теория и практика кодов, контролирующих ошибки. М.: Мир, 1986
/>3. ПитерсонР., Уэлдон Э. Коды, исправляющие ошибки. М.: Мир, 1976