Поняття про ідею корекції помилок

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

10110 - передана|передавати| кодова комбінація;

10010-1-я прийнята комбінація;

10100 - 2-я прийнята комбінація;

00110 - 3-я прийнята комбінація;

10110 - накопичена комбінація.

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

Прийняте повідомлення може також складатися з коди і його інверсії. Код і інверсія посилаються в канал зв'язку як одне ціле. Помилка на приймальному|усиновленому| кінці виділяється при зіставленні коди і його інверсії.

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

(39)

де - число одиниць в кодовому слові. Якби|аби| не існувало умови постійної ваги, те число комбінацій коди могло б бути набагато більшим, а саме . Прикладом|зразком| коди з|із| постійною вагою може служити стандартний телеграфний код № 3. Комбінації цієї коди побудовані|спорудити| таким чином, що на 7 тактів, протягом яких має бути прийнята одна кодова комбінація, завжди доводяться|припадають| три струмові і чотири безтоковые| посилки|посилання|. Збільшення або зменшення кількості струмових посилок|посилань| говорить про наявність помилки.

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

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

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

У загальному випадку для виявлення r помилок мінімальна кодова відстань

(40)

Мінімальна кодова відстань, необхідна для одночасного виявлення і виправлення помилок

(41)

де s - число помилок, що виправляються.

Для код, що тільки|лише| виправляють помилки

(42)

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

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

Якщо кодова комбінація двійкової коди А отстоит від кодової комбінації В на відстані d, то це означає, що в коді А потрібно d символів замінити на зворотних, щоб отримати код, але це не означає, що потрібне d додаткових символів, щоб код володів даними властивостями, що коректували. У двійкових кодах для виявлення одиночної помилки досить мати 1 додатковий символ незалежно від числа інформаційних розрядів коди, а мінімальна кодова відстань

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

(43)

(44)

при цьому мається на увазі, що загальна|спільна| довжина кодової комбінації

. (45)

Для практичних розрахунків при визначенні числа контрольних розрядів код з|із| мінімальною кодовою відстанню зручно користуватися виразами:

(46)

якщо відома довжина повної кодової комбінації п, і

(47)

якщо при розрахунках зручніше виходити із заданого числа інформаційних символів [9].

Для кодів, що виявляють всі триразові|трикратні| помилки

(48)

або

(49)

Для кодів завдовжки в п символів, що виправляють одну або дві помилки

(50)

Для практичних розрахунків можна користуватися виразом|вираженням|

(51)

Для кодів, що виправляють 3 помилки

(52)

Для кодів, виправляючих s помилок

(53)

Вираз зліва відомий як нижня межа Хеммінга, а вираз справа - як верхня межа Варшамова - Гильберта.

Для наближених розрахунків можна користуватися виразом|вираженням|

(54)

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

Завдання 6.1: Визначити кількість перевірочних розрядів для побудови систематичної коди, що виправляє одиночну помилку і що містить 5 інформаційних розрядів.

Рішення|розв'язання|:

при n = 6, 192 + 32 > 64;

при n = 7, 224 + 32 > 128;

при n = 8, 288 + 32 >256;

при n = 9, 288 + 32 < 512

тобто n = 9.

Завдання 6.2. Визначити максимальну кількість інформаційних розрядів систематичного коду, що виправляє одиночну помилку, якщо допустима довжина всього коду 10 символів.

Рішення|розв'язання|:

1)

2)

Завдання 6.3. Визначити мінімально можливу довжину кодової комбінації систематичного коду, що виправляє одиночну помилку, якщо кількість інформаційних розрядів n_u=11.

Рішення|розв'язання|:

при n = 12;

при n = 13;

при n = 14;

при n = 15;

тобто n = 15.

Завдання 6.4: Визначити кількість розрядів, що коректують, для побудови коди, що виявляє всі триразові помилки, якщо допустима довжина коди n=15.

Рішення|розв'язання|:

Дата добавления: 2015-07-26; просмотров: 597; Нарушение авторских прав

Мы поможем в написании ваших работ!