КУРСОВА РОБОТА НА ТЕМУ: «Завадостійке кодування інформації»

Зміст

ВСТУП    3

1. ЗАГАЛЬНА ХАРАКТЕРИСТИКА ЗАВАДОСТІЙКОГО КОДУВАННЯ. ПРИНЦИП ПОБУДОВИ ТА КЛАСИФІКАЦІЯ.    5

1.1    Основні параметри завадостійкого кодування.    6

1.2    Принципи завадостійкого кодування.    6

1.3    Класифікація    9

2.    ОПИС ТА ХАРАКТЕРИСТИКА ОСНОВНИХ ЗАВАДОСТІЙКИХ КОДІВ.    18

2.1    Циклічні коди    18

2.2    Лінійні групові коди    26

2.3    Код Хеммінга.    31

3.    ПОБУДОВА ЗАВАДОСТІЙКИХ КОДІВ    36

ВИСНОВКИ    41

ЛІТЕРАТУРА    43

 

ВСТУП

Метою курсової роботи є ознайомлення з завадостійким кодуванням, вивчення та дослідження характеристик основних завадостійких кодів.

Об’єктом дослідження є властивості та параметри циклічних, лінійних кодів та кодів Хеммінга. Основними завданнями курсової роботи є:

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

    Оскільки розвиток кодування спочатку стимулювався завданнями зв’язку, термінологія теорії кодування виникає з теорії зв’язку. Побудовані коди, проте, мають багато інших застосувань. Коди використовуються для захисту даних в пам’яті обчислювальних пристроїв і на цифрових стрічках і дисках, а також для захисту від неправильного функціонування або шумів в цифрових логічних ланцюгах. Коди використовуються також для стискування даних, і теорія кодування тісно пов’язана з теорією планування статистичних експериментів.

    Одним з найважливіших розділів теорії кодування є завдання кодування чисел, яка знаходиться на межі двох галузей науки: теорії чисел і теорії кодування інформації. Саме таке двояке положення завдання кодування чисел і вимога виконання арифметичних і логічних операцій над числами привело до появи нового розділу математики – теорії систем числення.

    Проте, з часом в теорії систем числення з’явилися результати, які виходили за рамки її традиційних завдань. Це перш за все можливість реалізації на основі тих або систем числення завдань перетворення кодів, наприклад, питань стискування інформації або завдостійкого кодування. Код є форма представлення повідомлення, не залежна від його фізичної суті. Це відрізняє код від сигналу, який визначає фізичне представлення повідомлення в системі зв’язку. Коди, що дозволяють виявити і виправити помилки в кодових комбінаціях називаються завадостійкими або корегуючими кодами. Вони діляться на дві групи: коди з виявленням помилок і коди з виявленням та виправленням помилок. Введення надмірності в код дозволяє окрім виявлення і виправлення помилок підвищити енергетичну ефективність лінії зв’язку, звузити частотний спектр переданого сигналу, скоротити час входження в зв’язок шляхом підвищення завадозахисного тракту синхронізації, поліпшити кореляційні властивості ансамблю сигналів, простими засобами реалізувати рознесений прийом. Завадостійке кодування припускає введення в передані повідомлення, разом з інформаційними, так званих перевірочних розрядів, що формуються в пристроях захисту від помилок (кодери на передавальному кінці, декодери на приймальному). Надмірність дозволяє відрізнити дозволену і заборонену (спотворену за рахунок помилок) комбінації при прийомі, інакше одна дозволена комбінація переходила б в іншу.

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

     

    1. ЗАГАЛЬНА ХАРАКТЕРИСТИКА ЗАВАДОСТІЙКОГО КОДУВАННЯ. ПРИНЦИП ПОБУДОВИ ТА КЛАСИФІКАЦІЯ.

    Проблема підвищення ймовірності обумовлена не відповідністю між вимогами, що пред’являються при передачі даних і якістю реальних каналів зв’язку. У мережах передачі даних потрібно забезпечити вірність не гірше -, а при використанні реальних каналів зв’язку і простого (первинного) коду вказана вірність не перевищує -. Одним з шляхів рішення задачі підвищення вірності в даний час є використання спеціальних процедур, заснованих на застосуванні завадостійких (коректуючих) кодів. Прості коди характеризуються тим, що для передачі інформації використовуються всі кодові слова (комбінації), кількість яких рівна N= (q – підстава коду, а n – довжина коду). У загальному випадку вони можуть відрізнятися один від одного одним символом (елементом). Тому навіть один помилково прийнятий символ приводить до заміни одного кодового слова іншим і, отже, до неправильного прийому повідомлення в цілому. Завадостійкими називаються коди, що дозволяють виявляти і виправляти помилки в кодових словах, які виникають при передачі по каналах зв’язку. Ці коди будуються таким чином, що для передачі повідомлення використовується лише частка кодових слів, які відрізняються один від одного більш ніж в одному символі. Ці кодові слова називаються дозволеними. Решта всіх кодових слів не використовується і належить до заборонених. Застосування завадостійкого коду для підвищення вірності передачі даних пов’язаного з вирішенням завдань кодування і декодування. Завдання кодування полягає в отриманні при передачі для кожного k- елементній комбінації з безлічі відповідного їй кодового слова довжиною n з безлічі. Завдання декодування полягає в отриманні k- елементній комбінації з прийнятого n – розрядного кодового слова при одночасному виявленні або виправленні помилок.

     

    1.1    Основні параметри завадостійкого кодування.

    Довжина коду – n;

    Довжина інформаційної послідовності – k;

    Довжина перевірочної послідовності – r=n-k;

    Кодова відстань коду -;

    Швидкість коду – R=k/n;

    Надмірність коду – R;

    Ймовірність виявлення помилки (спотворення) – РОО;

    Ймовірність не виявлення помилки (спотворення) – РНО.

    Кодова відстань між двома кодовими словами (відстань Хеммінга) – це число позицій, в яких вони відрізняються один від одного. Кодова відстань коду – це найменша відстань Хеммінга між різними парами кодових слів. Основні залежності між кратністю помилок t0, що виявляються, помилок tu, що виправляються, виправленням стирань tc і кодовою відстанню d0 коду:

    Стиранням називається “втрата” значення переданого символу в деякій позиції кодового слова, яка відома. Код, в якому кожне кодове слово починається з інформаційних символів і закінчується перевірочними символами, називається систематичним.

    1.2    Принципи завадостійкого кодування.

    У реальних умовах прийом двійкових символів завжди відбувається з помилками, коли замість символу “1” приймається символ “0” і навпаки. Помилки можуть виникати через перешкоди, що діють в каналі зв’язку (особливо перешкод імпульсного характеру), зміни за час передачі характеристик каналу (наприклад, завмирання), зниження рівня передачі, нестабільності амплитудно- і фазочастотних характеристик каналу і тому подібне. Загально прийнятим критерієм оцінки якості передачі в дискретних каналах є нормована на знак або символ допустима ймовірність помилки для даного виду повідомлень. Так, допустима ймовірність помилки при телеграфному зв’язку може складати (на знак) а при передачі даних – небільше (на символ). Для забезпечення таких значень ймовірності одного покращення тільки якісних показників каналу зв’язку може виявитися недостатнім. Тому основною мірою є застосування спеціальних методів підвищення якості прийому переданої інформації. Ці методи можна розбити на дві групи.

    До першої групи відносяться методи збільшення завадостійкого прийому одиничних елементів (символів) дискретної інформації, пов’язані з вибором рівня сигналу, відношення сигнал-перешкода (енергетичні характеристики), ширина смуги каналу, методів прийому і так далі.

    До другої групи відносяться методи виявлення і виправлення помилок заснованих на штучному введенні надмірності в передане повідомлення. Збільшити надмірність переданого сигналу можна різними способами. Оскільки об’єм сигналу можна обчислити за формулою:

        (1)

    де P – потужність сигналу, Вт; F – ширина спектру сигналу, Гц;T – час передачі сигналу, то його збільшення можливе за рахунок збільшення P F і T.

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

    1) багатократна передача кодових комбінацій (метод повторення);

    2) одночасна передача кодової комбінації по декількох паралельно працюючим каналам;

    3) завадостійке (що коректує) кодування, тобто використання кодів, що виправляють помилки. Інколи застосовують комбінації цих способів. Багатократне повторення (l раз) кодової комбінації є самим простим способом підвищення достовірності прийому і легко реалізується, особливо в низько швидкісних системах передачі для каналів з швидко змінюваними параметрами. Для способу багатократного повторення аналогічний спосіб передачі однієї і тієї ж інформації по декількох паралельних каналах зв’язку. У цьому випадку необхідно мати не менше трьох каналів зв’язку (наприклад, з частотним рознесенням), несущі частоти яких потрібно вибирати так, щоб помилки в каналах були незалежні. Гідністю таких систем є надійність і невеликий час затримки в отриманні інформації. Основним недоліком багатоканальних систем так само, як і систем з повторенням, є нераціональне використання надмірності. Найдоцільніше надмірність використовується при застосуванні завадостійких кодів. При завадостійкому кодуванні найчастіше вважають, що надмірність джерела повідомлень на вході кодера рівна χ = 0. Це обумовлено тим що дуже багато дискретних джерел володіють малою надмірністю. Якщо надмірність первинних джерел повідомлень істотна, то в цих випадках по можливості намагатиметься її зменшити шляхом ефективного кодування, застосовуючи, наприклад коди Шеннона-Фано або Хафмена. Потім методами завадостійкого кодування можна внести таку надмірність в сигнал, яка дозволить достатньо простими засобами поліпшити якість прийому. Таким чином ефективне кодування цілком може поєднуватися з завадостійким. У звичайному рівномірному не завадостійкому коді число розрядів n в кодових комбінаціях визначається числом повідомлень і підставою коду. Коди, у яких всі кодові комбінації дозволені до передачі, називаються простими або рівно доступними і є повністю без надмірними. Без надмірні первинні коди володіють великою “чутливістю” до перешкод. Внесення надмірності при використанні завадостійких кодів обов’язково пов’язане із збільшенням n – числа розрядів (довжини) кодової комбінації. Таким чином, всю множину комбінацій можна розбити на дві підмножини: підмножина дозволених комбінацій, тобто що володіють певними ознаками, і підмножина заборонених комбінацій, цими ознаками не володіють. Завадостійкий код відрізняється від звичайного тим, що в канал передаються не всі кодові комбінації N, які можна сформувати з даного числа розрядів n, а тільки їх частка яка складає підмножину дозволених комбінацій. Якщо при прийомі з’ясовується, що кодова комбінація належить до заборонених, то це свідчить про наявність помилок в комбінації, тобто таким чином вирішується завдання виявлення помилок. При цьому прийнята комбінація не декодується (не ухвалюється рішення про передане повідомлення). У зв’язку з цим завадостійкі коди називають кодами, що корегують. Корегуючі властивості надлишкових кодів залежать від правила їх побудови визначаючого структуру коду, і параметрів коду (тривалість символів числа розрядів, надмірності). Перші роботи по кодах, що коректують, належать Хеммінгу, який ввів поняття мінімальної кодової відстані і запропонував код, що дозволяє однозначно вказати ту позицію в кодовій комбінації, де виникла помилка. До “k” інформаційних елементів в коді Хеммінга додається “r” перевірочних елементів для автоматичного визначення місцезнаходження помилкового символу.

    1.3    Класифікація

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

     



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

    Блоковими називаються коди в яких інформаційний потік символів розбивається на відрізки і кожен з них перетвориться в певну послідовність (блок) кодових символів. У блокових кодах кодування при передачі (формування перевірочних елементів) і декодування при прийомі (виявлення і виправлення помилок) виконуються в межах кожної кодової комбінації (блоку) окремо по відповідних алгоритмах. Блокові коди діляться на рівномірні і нерівномірні. У рівномірних кодах, на відміну від нерівномірних, всі кодові комбінації містять однакове число n – символів (розрядів) з постійною тривалістю імпульсів символів коду. Рівномірні коди в основному і застосовуються в системах зв’язку, оскільки це спрощує техніку передачі і прийому.

    Класичними прикладами нерівномірного коду є код Морзе, широко вживаний в телеграфії, і код Хафмена, вживаний для компресії інформації (факсимільний зв’язок, ЕОМ). Ніяких спеціальних засобів виправленню і виявленню помилок в коді Морзе не передбачається у зв’язку з великою надмірністю самого переданого тексту. У цьому сенсі код Морзе не відноситься до класу коректуючих кодів.

    Майже всі блокові коди, що коректують, належать до роздільних кодів, в яких кодові комбінації складаються з двох часток: інформаційної і перевірочної. Їх символи завжди займають одні і ті ж позиції, тобто розташовуються на певних місцях. Як правило, в таких кодах, всі кодові комбінації яких містять n символів, перші до символів є інформаційними, а за ними розташовуються (n – k) перевірочних символів. Відповідно до цього роздільні коди отримали умовне позначення – (n, k). У нероздільних кодах ділення на інформаційні і перевірочні символи відсутні. До таких кодів відносяться, зокрема, коди з постійною вагою, так звані рівноважні коди.

    Неперервні або рекурентні
    коди утворюють послідовність символів, що не розділяється на окремі кодові комбінації. Кодування і декодування безперервно здійснюються над послідовністю елементів без ділення їх на блоки. Формування перевірочних символів ведеться по рекурентних (поворотним) правилах, тому безперервні коди часто називають рекурентними або ланцюговими. У простому ланцюговому коді кожен перевірочний елемент формується шляхом складання по модулю 2 сусідніх або віддалених один від одного на певне число позицій інформаційних елементів. У канал зв’язку передається послідовність імпульсів, в якій за кожним інформаційним слідує перевірочний. Подібну послідовність розрядів що чергується має наприклад, кореляційний манчестерський код. До безперервних кодів відносяться і згортальні коди, в яких кожен інформаційний символ, що поступає на вхід кодуючого пристрою, викликає появу на його виході ряду перевірочних елементів, утворених підсумовуванням по модулю 2, дані символи і ” k-1 ” попередніх інформаційних символів. Рекурентні коди дозволяють виправляти групові помилки (“пачки”) в каналах зв’язку.

    Систематичні коди утворюють найбільш обширну групу (n,k) – роздільних кодів. Особливістю цих кодів є те, що перевірочні (що коректують) символи утворюються за допомогою лінійних операцій над інформаційними. Крім того, будь-яка дозволена кодова комбінація може бути отримана в результаті лінійної операції над набором до лінійно незалежних кодових комбінацій. Зокрема, підсумовування по модулю 2 двох і більш дозволених комбінацій також дає дозволену кодову комбінацію.

    Оскільки теоретичною основою отримання таких комбінацій є математичний апарат лінійної алгебри, то коди і називають лінійними, враховуючи що перевірочні символи формуються по певній системі (правилам), блокові, рівномірні, роздільні, лінійні коди отримали назву систематичних. Використання апарату лінійної алгебри, в якій важливе значення має поняття “група”, називаються – групові.

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

    Несистематичні (нелінійні) коди вказаними вище властивостями не володіють і застосовуються значно рідше в спеціальних випадках. Прикладом нелінійного коду є вже згадуваний нероздільний, рівноважний код. Ці коди зазвичай використовуються в несиметричних каналах зв’язку, в яких ймовірність переходу 10 значно більше ймовірності переходу 10 або навпаки. У таких каналах мало ймовірно, щоб в одному блоці були переходи обох видів, і тому майже всі помилки приводять до зміни ваги блоку, і, отже, виявляються. Іншим прикладом несистематичного коду є код з контрольним підсумовуванням – ітеративний код. У цьому коді перевірочні розряди формуються в результаті підсумовування значень розрядів як в даній кодовій комбінації, так і однойменних розрядах у ряді сусідніх з нею комбінацій створюючи сумісний блок. Ітеративні коди дозволяють отримати так звані потужні коди, тобто коди з довгими блоками і великою кодовою відстанню при порівняні з простою процедурою декодування. Ітеративні коди можуть будуватися як комбінаційні за допомогою відтворення двох чи більше систематичних кодів. Найбільш відомі серед систематичних кодів – коди Хеммінга. Вони історично були знайдені раніше інших кодів і зіграли велику роль в розвитку теорії коректуючих кодів. У цих кодах використовується принцип перевірки на парність певного ряду інформаційних символів. Перевірочна група з r символів формується по елементно по відповідному алгоритму.

    Циклічні коди також відносяться до класу лінійних систематичних кодів і володіють всіма їх властивостями. Коди названі циклічними тому що циклічне зрушення будь-якої дозволеної кодової комбінації також є дозволеною комбінацією. Теорія побудови циклічних кодів базується на розділах вищої алгебри, що вивчає властивості двійкових многочленів. Особливу роль в цій теорії грають так звані многочлени, що не приводяться тобто поліноми, які не можуть бути представлені у вигляді відтворення многочленів нижчих ступенів. У зв’язку з цим циклічні коди відносять до різновиду поліноміальних кодів. Серед циклічних кодів особливе місце займає клас кодів запропонованих Боузом і Рой-Чоудхурі. Коди Боуза-Чоудхурі-Хоквінгема отримали скорочене найменування БЧХ – коди і відрізняються спеціальним вибором того, що породжує циклічний код поліном, що приводить до простої процедури декодування. Відзначимо, що коди Хеммінга також можна отримати по алгоритмах формування циклічних кодів. Проблема завадостійкого кодування є обширною областю теоретичних і прикладних досліджень. Основними завданнями при цьому є наступні: відшукання кодів що ефективно виправляють помилки необхідного вигляду; знаходження методів кодування і декодування і простих способів їх реалізації. Найбільш розроблені ці завдання стосовно систематичних кодів. Такі коди успішно застосовуються в обчислювальній техніці, різних автоматизованих, цифрових пристроях і цифрових системах передачі інформації.

    Похідні коди будують на основі деякого початкового коду, до якого або додають символи, збільшуючи відстань (розширений код), або скорочують частку інформаційних символів без зміни відстані (скорочений код), або викидають (виколюють) деякі символи (виколотий, або перфорований код). Код Хеммінга дає приклад процедури розширення, що збільшує відстань коду з 3 до 4. Необхідність у виколюванні виникає в результаті побудови на основі початкового коду іншого, менш потужного, коротшого коду з тією ж відстанню. При ширшому трактуванні терміну “похідний код” до цього класу можна віднести всі коди, отримані з початковим додаванням або виключенням як символів, так і слів.

    Формальне ділення кодів на двійкових і недвійкових носить штучний характер; аналогічно слід виділяти трійковий і чотирійковий та інші коди більшої підстави. Виправдовується таке ділення ускладненням алгоритмів побудови, кодування і декодування недвійкових кодів. За інших рівних умов бажано, щоб інформаційні і надлишкові символи розташовувалися окремо. У систематичних кодах ця умова виконується. У циклічних кодах кожне слово містить всі свої циклічні перестановки. Всі n циклічних перестановок (слова довжини n) утворюють цикл. У квазіциклічних кодах цикл утворюється на 0 числі символів n-1 або, рідше, n-2. Помилки в каналах зв’язку мають самий різний розподіл, проте для вибору завадостійких кодів доцільно розділити всі можливі конфігурації помилок на незалежних (не корельовані) і пакети (корельовані помилки). На практиці доводиться враховувати якість інтервалів між пакетами: вони можуть бути вільними від помилок або ж містити випадкові незалежні помилки.

    Під кореляційними мають на увазі коди, що володіють хорошими кореляційними властивостями, важливими при передачі сигналів входження в зв’язок, для підвищення захищеності від деяких видів перешкод, витягання сигналів з інтенсивних шумів, забезпечення багато станційного доступу, побудови асинхронно адресних систем зв’язку. Кореляційні коди включають пари протилежних сигналів з хорошою функцією автокореляції (метод внутрішньо імпульсної модуляції), імпульсно-інтервальні коди, що мають на фіксованому інтервалі часу постійне для всіх слів коду число імпульсів із значеннями інтервалів, що не перекриваються (при будь-якому взаємному зміщенні слів в часі), між імпульсами, ансамблі сигналів з хорошими взаємно кореляційними властивостями.

    Особливий клас утворюють частотно-компактні коди, призначені для зосередження енергії сигналу в можливо вужчій смузі частот. Така загальна побудова завдання розуміється в різних системах зв’язку по-різному: у дротяних лініях і лінійних трактах, що містять смугово-обмежуючі фільтри з крутими фронтами, необхідно основну енергію сигналу “відсунути” від крайніх частот до центру смуги пропускання метою зменшення між символьних спотворень; у мережах радіозв’язку з жорсткими обмеженнями по електромагнітній сумісності радіо засобів від коду потрібно значно (на десятки децибел) зменшити рівень поза смугових випромінювань. Побудова кодування і декодування частотно-компактних код істотно залежать від методу модуляції.

    Арифметичні коди призначені для боротьби з помилками при виконанні арифметичних операцій в мікропроцесорі ЕОМ.

    Лінійні коди утворюють векторний простір і володіють наступною важливою властивістю: два кодові слова можна скласти, використовуючи відповідне визначення суми, і отримати третє кодове слово. В разі звичайних двійкових кодів ця операція є по символьним складанням двох кодових слів по модулю 2 (тобто 1+1=0, 1+0=1, 0+0=0). Ця властивість приводить до двох важливих наслідків. Перше з них полягає в тому, що лінійність істотно спрощує процедури кодування і декодування, дозволяючи виразити кожне кодове слово у вигляді “лінійної” комбінації невеликого числа виділених кодових слів, так званих базисних векторів. Друга властивість полягає в тому, що лінійність істотно спрощує завдання обчислення параметрів коду, оскільки відстань між двома кодовими словами при цьому еквівалентна відстані між кодовим словом, полягаючи цілком з нулів, і деяким іншим кодовим словом. Таким чином, при обчисленні параметрів лінійного коду досить розгледіти, що відбувається при передачі кодового слова, що складається цілком з нулів. Обчислення параметрів спрощується ще і тому, що відстань Хеммінга між даним кодовим словом і нульовим кодовим словом дорівнює числу ненульових елементів даного кодового слова. Це число часто називають вагою Хеммінга даного слова, і список, що містить число кодових слів кожної ваги, можна використовувати для обчислення характеристик коду за допомогою адитивної межі. Такий список називають спектром коду.

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

    Як лінійні, так і нелінійні коди утворюють розширені класи, що містять багато різних конкретних видів завадостійких кодів. Серед лінійних блокових найбільше значення мають коди з однією перевіркою на парність, M-коди (симплексні), ортогональні, біортогональні, Хеммінга, Боуза-Чоудхурі-Хоквінгема, Голея, Рида-Соломона. До нелінійних відносять коди з контрольною сумою, інверсні, Нордстрома-Робінсона (HP), з постійною вагою, перестановочні з повторенням і без повторення символів (повні коди ортогональних таблиць, проектних груп, груп Матьє і інших груп перестановок).

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

    Нарешті, коди можна розбити на коди, що виправляють випадкові помилки, і коди, що виправляють пакети помилок. В основному ми матимемо справу з кодами, призначеними для виправлення випадкових, або незалежних, помилок. Для виправлення пакетів помилок було створено багато кодів, що мають хороші параметри. Проте за наявності пачок помилок часто виявляється вигіднішим використовувати коди, що виправляють випадкові помилки, разом з пристроєм перемноження відновлення. Такий підхід включає процедуру перемішування порядку символів в закодованій послідовності перед передачею і відновленням початкового порядку символів після прийому з тим, щоб рандомізувати помилки, об’єднані в пакети.

     

    2.    ОПИС ТА ХАРАКТЕРИСТИКА ОСНОВНИХ ЗАВАДОСТІЙКИХ КОДІВ.

    2.1    Циклічні коди

    Циклічні коди
    названі так тому, що в них частка комбінацій коди або всі комбінації можуть бути отримані шляхом циклічного зсуву однієї або декількох комбінацій коду. Циклічний зсув здійснюється справа на ліво, причому крайній лівий символ кожного разу переноситься в кінець комбінації. Циклічні коди, практично, всі відносяться до систематичних кодів, в них контрольні і інформаційні розряди розташовані на строго певних місцях. Крім того, циклічні коди належать до блокових
    кодів. Кожен блок (одна буква є окремим випадком блоку) кодується самостійно.

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

    Многочлени, що не зводяться, в теорії циклічних кодів відіграють роль утворюючих (генераторних, таких, що проводять) многочленів. Якщо задану кодову комбінацію помножити на вибраний многочлен, що не зводиться, то отримаємо циклічний код, що коректують здібності якого визначаються многочленом, що не зводиться. Припустимо, потрібно закодувати одну з комбінацій чотиризначного двійкового коду. Припустимо також, що ця комбінація – . Далі знайдемо такий многочлен . Потім помножимо на одночлен того ж ступеня, що і утворює многочлен. Від множення многочлена на одночлен ступеня п ступінь кожного члена многочлена підвищиться на n що еквівалентно приписуванню n нулів з боку молодших розрядів многочлена. Оскільки ступінь вибраного многочлена, що незводиться, рівний трьом, то початкова інформаційна комбінація множиться на одночлен третього степеня:

        (2)

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


        (3)

    або

        (4)

    Таким чином отримується:

        (5)

    або в загальному вигляді:

        (6)

    де – приватне, а – залишок від ділення на .

    Оскільки в двійковій арифметиці а значить то можна при складанні двійкових чисел переносити складову з однієї частки рівність в іншу без зміни знаку (якщо це зручно), тому рівність вигляду можна записати і як і як . Всі три рівність в даному випадку означають, що або і рівні 0, або а і рівні 1, тобто мають однакову парність. Таким чином, вираження (6) можна записати як:

        (7)

    що в разі нашого прикладу дасть вираження:

        (8)

    Або

        (9)

    Многочлен 1101001 і є шукана комбінація, де 1101 – інформаційна частка, а 001 – контрольні символи. Відмітимо, що шукану комбінацію ми отримали б і як в результаті множення однієї з комбінацій повного чотиризначного двійкового коду (в даному випадку 1111) на створений многочлен, так і множенням заданої комбінації на одночлен, що має той же ступінь, що і вибраний створений многочлен (у нашому випадку таким чином була отримана комбінація 1101000) з подальшим додаванням до отриманого твору залишку від ділення цього твору на створений многочлен (у нашому прикладі залишок мав вигляд 001).

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

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

    Отже, комбінації циклічних кодів можна представляти у вигляді многочленів, у яких показники ступеня відповідають номерам розрядів, коефіцієнти при х дорівнюють 0 або 1 залежно від того, стоїть 0 або 1 в розряді кодової комбінації, яку представляє даний многочлен, що показано на прикладі:

        (10)

    Циклічне зрушення кодової комбінації аналогічне множенню відповідного многочлена на х:

        (11)

    Якщо степінь многочлена досягає розрядності коду, то відбувається «перенесення» в нульовий ступінь при . У шифраторах циклічних кодів ця операція здійснюється шляхом з’єднання виходу осередку старшого розряду з входом осередку нульового розряду. Складання по модулю 2 будь-яких двох сусідніх комбінацій циклічного коду еквівалентно операції множення многочлена відповідного комбінації першого доданку на многочлен якщо приведення подібних членів здійснюється по модулю 2_

            (12)

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

    Проте мало побудувати циклічний код. Треба уміти виділити з нього можливі помилкові розряди, тобто ввести деякі пізнавальні помилки, які виділяли б помилковий блок зі всіх інших. Оскільки циклічні коди – блокові, то кожен блок повинен мати свій пізнавач. І тут вирішальну роль грають властивості утворюючого многочлена . Методика побудови циклічного коду така, що утворюючий многочлен бере участь в утворенні кожної кодової комбінації, тому будь-який многочлен циклічного коду ділиться на утворюючий без залишку. Але без залишку діляться тільки ті многочлени, які належать даному коду, тобто утворюючий многочлен дозволяє вибрати дозволені комбінації зі всіх можливих. Якщо ж при діленні циклічного коду на утворюючий многочлен буде отриманий залишок, то це означає або в коді сталася помилка, або це комбінація якогось іншого коду (заборонена комбінація), що для декодуючого пристрою не має принципової різниці. По залишку і виявляється наявність забороненої комбінації, тобто виявляється помилка. Залишки від ділення многочленів є пізнавальними помилками циклічних кодів.

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

    При діленні одиниці з нулями на утворюючий многочлен слід пам’ятати, що довжина залишку має бути не менше числа контрольних розрядів, тому в разі браку розрядів в залишку до залишку приписують справа необхідне число нулів:

        (13)

    починаючи з восьмого, залишки повторюватимуться.

    Залишки від ділення використовують для побудови утворюючих матриць, які, завдяки своїй наочності і зручності отримання похідних комбінацій, набули широкого поширення для побудови циклічних кодів. Побудова утворюючої матриці зводиться до складання одиничної транспонованої і додаткової матриці, елементами якої є залишки від ділення одиниці з нулями на утворюючий многочлен . Нагадаємо, що одинична транспонована матриця є квадратною матрицею, всі елементи якої – нулі, окрім елементів, розташованих по діагоналі справа наліво зверху вниз (у не транспонованій матриці діагональ з одиничними елементами розташована зліва направо зверху вниз). Елементи додаткової матриці приписуються праворуч від одиничної транспонованої матриці.

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

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

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

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

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

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


    Число ненульових комбінацій, що отримуються в результаті підсумовування по модулю 2 всіляких поєднань рядків утворюючої матриці що показано в формулі:

        (14)

    де – число інформаційних розрядів кодів.

    Число ненульових комбінацій, що отримуються в результаті циклічного зрушення будь-якого рядка утворюючої матриці і дзеркальної нею комбінації:

        (15)

    де довжина кодової комбінації.

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

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

    Ідея виправлення помилок базується на тому, що помилкова комбінація після певного числа циклічних зрушень “підганяється” під залишок таким чином, що в сумі із залишком вона дає виправлену комбінацію. Залишок при цьому є не що інше, як різниця між спотвореними і правильними символами, одиниці в залишку стоять на місцях спотворених розрядів в підігнаній циклічними зрушеннями комбінації. Підганяють спотворену комбінацію до тих пір, поки число одиниць в залишку не дорівнюватиме числу помилок в коді. При цьому, число одиниць може або дорівнювати числу помилок s що виправляються даним кодом (код виправляє 3 помилки і в спотвореній комбінації 3 помилки), або бути менше s (код виправляє 3 помилки, а в прийнятій комбінації – 1 помилка).

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

    2.2    Лінійні групові коди

    Лінійними
    називаються коди, в яких перевірочними символами є лінійні комбінації інформаційних символів.

    Для двійкових кодів в якості лінійної операції використовують складання по модулю 2.

    Правила складання по модулю 2 визначаються наступною рівністю:


    Послідовність нулів і одиниць, що належать даному коду, називатимемо кодовим вектором.

    Властивість лінійних кодів: сума (різниця) кодових векторів лінійного коду дає вектор, що належить даному коду.

    Лінійні коди утворюють групу алгебри по відношенню до операції складання по модулю 2. У цьому сенсі вони є груповими кодами.

    Властивість групового коду: мінімальна кодова відстань між кодовими векторами групового коду дорівнює мінімальній вазі ненульових кодових векторів.

    Вага кодового вектора (кодовій комбінації) дорівнює числу його ненульових компонентів.

    Відстань між двома кодовими векторами
    дорівнює вазі вектора, отриманого в результаті складання початкових векторів по модулю 2. Таким чином, для даного групового коду .

    Групові коди зручно задавати матрицями, розмірність яких визначається параметрами коду і .
    Число рядків матриці рівне число стовпців рівне +=:

        (16)

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

    Матриця(що зображена (17)), що породжує, С може бути представлена двома матрицями І і П (інформаційною і перевірочною). Число стовпців матриці П рівне число стовпців матриці І рівно :

        (17)

    Теорією і практикою встановлено, що матрицю І зручно брати за одиничну матрицю в канонічній формі(матриця(18)):

        (18)

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

    Вага кожного рядка матриці П має бути не менше де – вага відповідного рядка матриці І якщо матриця І – одинична, то (зручність вибору матриці І як одиничної матриці очевидно: при ускладнилася б як побудова кодів, так і їх технічна реалізація).

    При дотриманні перерахованих умов будь-яку матрицю групового коду, що породжує, можна привести до наступного вигляду:

        (19)

    званому лівою канонічною формою матриці, що породжує.

    Для коду з =2 матриця, С має вигляд:

        (20)

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

    Для коду з матриця, що породжує, не може бути представлена у формі, загальній для всіх кодів з даним . Вид матриці залежить від конкретних вимог до породжуваного коду. Цими вимогами можуть бути або мінімум розрядів, що коректують, або максимальна простота апаратури.

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

    Для код з співвідношення п і . наступні: (3; 1), (7;4), (15; 11), (31; 26), (63; 57) і так далі

    Щільно упаковані коди, оптимальні з погляду мінімуму надлишкових символів, виявляють максимально можливу кількість варіантів помилок кратністю r+1; r+2 і так далі і що мають і були досліджені Д. Слепяном. Для отримання цих кодів матриця П повинна мати комбінації з максимальною вагою. Для цього при побудові код з послідовно використовуються вектори довжиною пвагою . Ці коди економні з погляду простоти апаратури і містять мінімальне число одиниць в розрядах матриці, що коректує. При побудові коду з максимально простими шифраторами і дешифраторами послідовно вибираються вектори вагою =2,3…,. Якщо число комбінацій, що є розрядами коду, що коректують, і що задовольняють умові більше то в першому випадку не використовують набори з найменшою вагою, а в другому – з найбільшою.

    Рядки утворюючої матриці С є комбінацій шуканого коду. Решта комбінацій коду будується за допомогою утворюючої матриці за наступним правилом: символи, що коректують, призначені для виявлення або виправлення помилки в інформаційній частці коду, знаходяться шляхом підсумовування по модулю 2-ох рядків матриці П, номери яких збігаються з номерами розрядів, що містять одиниці в кодовому векторі, що представляє інформаційну частку коду. Отриману комбінацію приписують справа до інформаційної частки коду і отримують вектор повного коду, що коректує. Аналогічну процедуру проробляють з другою, третьою і подальшими інформаційними кодовими комбінаціями, поки не буде побудований код, щовиправляє, для передачі всіх символів первинного алфавіту.

    Для кожної конкретної матриці існує своя, єдина система перевірок. Перевірки проводяться за наступним правилом: у першу перевірку разом з перевірочним розрядом входять інформаційні розряди, які відповідають одиницям першого стовпця перевірочної матриці П; у другу перевірку входить другий перевірочний розряд і інформаційні розряди, відповідні одиницям другого стовпця перевірочної матриці, і так далі. Число перевірок дорівнює числу перевірочних розрядів коду, що коректує . В результаті здійснення перевірок утворюється перевірочний вектор який називають синдромом. Якщо вага синдрому дорівнює нулю, то прийнята комбінація вважається за безпомилкову. Якщо хоч би один розряд перевірочного вектора містить одиницю, то прийнята комбінація містить помилку. Виправлення помилки проводиться по вигляду синдрому, оскільки кожному помилковому розряду відповідає один-єдиний перевірочний вектор. Вид синдрому для кожної конкретної матриці може бути визначений за допомогою перевірочної матриці Н, яка є транспонованою матрицею П, доповненою одиничною матрицею число стовпців якої дорівнює числу перевірочних розрядів коду:

    .    (21)

    Стовпці такої матриці є значенням синдрому для розряду, відповідного номеру стовпця матриці Н. Процедура виправлення помилок в процесі декодування групових кодів зводиться до наступного. Будується кодова таблиця. У першому рядку таблиці розташовуються всі кодові вектори . У першому стовпці другого рядка розміщується вектор вага якого дорівнює 1. Решта позицій другого рядка заповнюється векторами, отриманими в результаті підсумовування по модулю 2 вектори з вектором розташованим у відповідному стовпці першого рядка. У першому стовпці третього рядка записується вектор вага якого також дорівнює 1, проте, якщо вектор містить одиницю в першому розряді, то – у другому. У решту позицій третього рядка записують суми і .

    Аналогічно поступають до тих пір, поки не будуть підсумовані з векторами всі вектори вагою 1, з одиницями в кожному з п розрядів. Потім підсумовуються по модулю 2 вектори вагою 2, з послідовним перекриттям всіх можливих розрядів. Вага вектора визначає число помилок, що виправляються. Число векторів визначається можливим числом синдромів, що не повторюються, і рівно (нульова комбінація говорить про відсутність помилки). Умова не повторюваності синдрому дозволяє по його вигляду визначати один-єдиний відповідний йому вектор Вектори є вектори помилок, які можуть бути виправлені даним груповим кодом.

    По вигляду синдрому прийнята комбінація може бути віднесена до того або іншого суміжного класу, утвореного складанням по модулю 2 кодових комбінації з вектором помилки тобто до певного рядка. Прийнята кодова комбінація порівнюється з векторами, записаними в рядку, відповідному отриманому в результаті перевірок синдрому. Дійсний код буде розташований в першому рядку тієї ж колонки таблиці. Процес виправлення помилки полягає в заміні на зворотне значення розрядів, відповідних одиницям у векторі помилок .
    Вектори не мають дорівнювати жодному з векторів інакше в таблиці з’явилися б нульові вектори.

    2.3    Код Хеммінга.

    Побудова коду Хеммінга базується на принципі перевірки на парність ваги W (числа одиничних символів) в інформаційній групі кодового блоку.

    Пояснимо ідею перевірки на парність на прикладі простого коректуючого коду, яка так і називається кодом з перевіркою на парність або кодом з перевіркою по паритету (рівності). У такому коді до кодових комбінацій без надійного первинного двійкового k – розрядного коду додається один додатковий розряд (символ перевірки на парність, названий перевірочним, або контрольним). Якщо число символів “1” початкової кодової комбінації парне, то в додатковому розряді формують контрольний символ 0, а якщо число символів “1” непарне, то в додатковому розряді формують символ 1. В результаті загальне число символів “1” в будь-якій переданій кодовій комбінації завжди буде парним. Таким чином, правило формування перевірочного символу зводиться до наступного виразу:

    =⊕⊕,    (22)

    де i – відповідний інформаційний символ (0 або 1), k – загальне їх число під операцією “” тут і далі розуміється складання по mod2. Очевидно що додавання додаткового розряду збільшує загальне число можливих комбінацій удвічі в порівнянні з числом комбінацій початкового первинного коду, а умова парності, переводить дозволену комбінацію в недозволену. Код з перевіркою на парність дозволяє виявляти одиничну помилку при прийомі кодової комбінації, оскільки така помилка порушує умову парності, переводячи дозволену комбінацію в заборонену. Критерієм правильності прийнятої комбінації є рівність нулю результату S підсумовування по mod2 всіх n символів коду, включаючи перевірочний символ. За наявності одиночної помилки S набуває значення 1:

    S = ⊕⊕= – помилки немає

    = – одноразова помилка.    (23)

    Цей код є (k+1,k) – кодом, або (n,n-1) – кодом. Мінімальна відстань коду рівна двом (=2), і, отже, ніякі помилки не можуть бути виправлені. Простий код з перевіркою на парність може використовуватися тільки для виявлення (але не виправлення) однократних помилок. Збільшуючи число додаткових перевірочних розрядів і формуючи по певним правилам перевірочні символи r, рівні 0 або 1, можна підсилити властивості коду, що коректують, так, щоб він дозволяв не лише знаходити, але і виправляти помилки. На цьому і заснована побудова коду Хеммінга. Розглянемо ці коди, що дозволяють виправляти одиничну помилку, за допомогою безпосереднього опису. Для кожного числа перевірених символів r=3,4,5. існує класичний код Хеммінга з манкіровкою:

    (n,k)=(–1,––1–r).    (24)

    При інших значеннях числа інформаційних символів k виходять так звані усічені (укорочені) коди Хеммінга. У простому варіанті при заданих чотири (k=4) інформаційні символи () важатимемо, що вони погруповані на початку кодового слова, хоча це і не обов’язково. Доповнимо ці інформаційні символи трьома перевірочними символами (r=3), задаючи їх наступною рівністю перевірки на парність, які визначаються відповідними алгоритмами:

    =⊕⊕

    =⊕⊕;    (25)

    =⊕⊕,

    де знак означає складання по модулю 2.

    Відповідно до цього алгоритму визначення значень перевірочних символів нижче виписані всі можливі 16 кодових слів (7,4) – коду Хеммінга.

    Схема декодера для (7,4) – коду Хеммінга, на вхід якого поступає кодове слово V=(‘,’, ‘, ‘,’, ‘, ‘).

    Апостроф означає, що будь-який символ слова може бути спотворений перешкодою в каналі передачі. У декодері в режимі виправлення помилок будується послідовність:

    =⊕⊕

    =’⊕⊕⊕‘;    (26)

    =’⊕⊕⊕‘.

    Трьох символьна послідовність (,,) називається синдромом. Термін “синдром” використовується і в медицині, де він позначає поєднання ознак, характерних для певного захворювання. В даному випадку синдром S=(,,) є поєднанням результатів перевірки на парність відповідних символів кодової групи і характеризує певну конфігурацію помилок (шумовий вектор).

     

    к = 4    г = 3

    0

    0

    0

    0

    0

    0

    0

    0

    0

    0

    1

    0

    1

    1

    0

    0

    1

    0

    1

    1

    0

    0

    0

    1

    1

    1

    0

    1

    0

    1

    0

    0

    1

    1

    1

    0

    1

    0

    1

    1

    0

    0

    0

    1

    1

    0

    0

    0

    1

    0

    1

    1

    1

    0

    1

    0

    1

    0

    0

    0

    1

    0

    1

    1

    0

    0

    1

    1

    1

    0

    1

    0

    1

    0

    0

    1

    1

    1

    0

    1

    1

    0

    0

    0

    1

    1

    0

    0

    0

    1

    0

    1

    1

    0

    1

    0

    0

    1

    1

    1

    1

    0

    1

    0

    0

    1

    1

    1

    0

    1

    1

    1

    \

    Рисунок 2.1    Кодові слова (7,4) – коди Хеммінга.


    Число можливих синдромів визначається вираженням

    S=     (27)

    При числі перевірочних символів r=3 є вісім можливих синдромів (=8). Нульовий синдром (000) указує на те, що помилки при прийомі відсутні або не виявлені. Всякому ненульовому синдрому відповідає певна конфігурація помилок, яка і виправляється. Класичні коди Хеммінга (24) мають число синдромів, точно рівне їх необхідному числу, дозволяють виправити всі однократні помилки в будь-якому інформативному і перевірочному символах і включають один нульовий синдром. Такі коди називаються щільно упакованими. Усічені коди є нещільно упакованими, оскільки число синдромів у них перевищує необхідне. Так, в коді (9,5) при чотирьох перевірочних символах число синдромів дорівнюватиме =16, тоді як необхідно всього 10. Зайві 6 синдромів свідчать про неповну упаковку коду (9,5).Для даного коду (7,4) в таблиці 2 представлені ненульові синдроми і відповідні конфігурації помилок.

    Таблиця 2 – Характеристика коду (7,4).

    Синдром

    001

    010

    011

    100

    101

    110

    111

    Конфігурація помилок

    0000001

    0000010

    0001000

    0000100

    1000000

    0010000

    0100000

    Помилка у символі

    Таким чином, код (7,4) дозволяє виправити всі одиночні помилки. Проста перевірка показує, що кожна з помилок має свій єдиний синдром. При цьому можливе створення такого цифрового коректора помилок (дешифратора синдрому), який по відповідному синдрому виправляє відповідний символ в прийнятій кодовій групі. Після внесення виправлення перевірочні символи можна на вихід декодера не виводити.

    Дві або більше помилок перевищують можливості коду Хеммінга, і декодер помилятиметься. Це означає, що він вноситиме неправильні виправлення і видавати спотворені інформаційні символи. Ідея побудови подібного коду, що коректує, природно, не міняється при перестановці позицій символів в кодових словах. Всі такі варіанти також називаються (7,4) – кодами Хеммінга.

ЗАВАНТАЖИТИ

Для скачування файлів необхідно або Зареєструватись

Перешкодостійке кодування інформації (302.3 KiB, Завантажень: 19)

Сторінка: 1 2 3 4 5
завантаження...
WordPress: 23.51MB | MySQL:26 | 0,357sec