Коди, що виявляють помилки

Код з перевіркою на парність

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

Код відноситься до класу разделімих і систематичних. Перевірки символ в даному випадку виходить в результаті підсумовування інформаційних символів по модулю 2.

Нехай безізбиточная кодова комбінація має вигляд.

Перевірки символ. а кодова комбінація на виході кодера -

Код з числом одиниць, кратним трьом

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

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

Такий код дозволяє виявляти всі поодинокі помилки і будь-яке парне кількість помилок одного типу (наприклад, перехід від 0 до 1).

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

Кореляційний код по-іншому називають кодом з подвоєнням елементів. Тут кожен символ довічного безізбиточного коду кодується двома елементами, причому 1 перетворюється в 10, а 0 01. Таким чином, замість комбінації 01101, наприклад, в канал зв'язку передається 01.10.10.01.10. Помилка виявляється, якщо в парних елементах будуть міститися однакові символи, тобто 11 або 00 замість 10 і 01. При правильному прийомі парні елементи відкидаються і залишається первісна комбінація.

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

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

Комбінований інверсний код.

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

1 1 0 0 0 1 0 0 1 1 1 0

0 0 1 0 1 0 0 0 1 0 1 0

Прийом комбінованого інверсного коду здійснюється в два етапи.

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

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

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

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

Нехай вихідна комбінація має вигляд:

Припустимо, що сталася одноразова помилка в інформаційній частині, тобто прийнята комбінація

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

Приклади розв'язання задач

Завдання на міру Хартлі

1. Чому дорівнює максимальна кількість інформації, переносний 2 повідомленнями 5-значного 8-ричного коду?

Рішення: кількість інформації, переносний 1 сполученням, визначається виразом:. За умовою завдання:. .

біт. Кількість інформації, що переноситься 2 повідомленнями: біт.

2. Визначити обсяг використовуваного алфавіту, якщо відомо, що 16-значне повідомлення, складене з цього алфавіту, несе в собі 32 біта інформації.

Рішення: за умовою задачі n = 16, I = 32 біта, m =?

3. Чому дорівнює довжина повідомлення, складеного з 4-літерного алфавіту, якщо відомо, що кількість інформації, переносний 1 сполученням, дорівнює 20 біт?

Завдання на надмірність повідомлень

1. Абсолютна надмірність повідомлень, складених з m -літерні алфавіту, дорівнює 0,7 біт, а середня кількість інформації, що переноситься одним знаком повідомлення, - 1,3 біта. Визначити обсяг використовуваного алфавіту.

Рішення: абсолютна надмірність визначається виразом (2.1). . де - обсяг використовуваного алфавіту. визначає середня кількість інформації. переноситься одним знаком повідомлення. За умовою завдання = 1,3 біт. Отже,. . m = 4.

2. Інформаційна надмірність повідомлень, складених з 8-літерного алфавіту, дорівнює 0,3. Визначити середню кількість інформації, що припадає на 1 знак такого повідомлення.

Рішення: інформаційна надмірність визначається виразом; . За умовою завдання m = 8; D = 0,3. Отже,. Середня кількість інформації, що припадає на 1 знак такого повідомлення, = = біт.

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

Рішення: інформаційна надмірність

Завдання на ефективне кодування

1. Закодувати за методикою Хаффмена наступні літери первинного алфавіту. . . . . У дужках вказані ймовірності появи букв в повідомленні. Імовірність визначити.

Рішення: ефективне кодування може бути застосовано тільки до знаків, що становлять повну групу подій, тобто . Отже,. Володіємо підлягають кодування знаки в порядку убування ймовірностей і будуємо кодове дерево.

2. Закодувати за методикою Шеннона-Фано наступні літери первинного алфавіту. . . . . Імовірність визначити.

Завдання на кодування виявляють кодами

1. Закодувати кодом з перевіркою на парність наступні комбінації:

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

2. Закодувати кодом з числом 1 кратним 3 наступні комбінації: а). ; б). ; с).

В даному коді завжди m = 2, які вибираються так, щоб забезпечити вага повної комбінації кратним 3.

3. Кореляційний код (код з подвоєнням елементів). Кожен інформаційний символ представляється двома символами:. . Якщо інформаційна комбінація має вигляд 01101, то в кореляційному коді їй буде відповідати комбінація 0110100110.

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

Завдання на декодування виявляють кодів

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

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

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

2. Якщо надійшла комбінація закодована кодом з числом 1, кратним 3, перевіряється вага повної комбінації на кратність 3. Якщо умова виконується, контрольні розряди (два) відкидаються, а решту переводять в десятковий код. В іншому випадку комбінація бракується.

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

4. Приклад декодування комбінації комбінованого інверсного коду наведено вище, де розглянуто питання про його кодуванні і декодуванні. Слід пам'ятати, що при відсутності помилки результатом декодування будуть 0 у всіх розрядах. В цьому випадку контрольна частина відкидається, а інформаційна частина перекладається в десятковий код.

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

Якщо в результаті декодування отримані всі 0 і одна 1, значить сталася одноразова помилка в контрольній частині. Отже, інформаційна частина достовірна і її слід перевести в десятковий код.

У разі, коли відбувається багаторазова помилка, результат декодування не співпадатиме з жодним з розглянутих вище.

Приклад завдання з контрольної роботи - частина 2

1. Визначити обсяг використовуваного алфавіту, якщо відомо, що 10-значне повідомлення, складене з цього алфавіту, несе в собі 20 біт інформації.

2. Закодувати за методикою Хаффмена наступні літери первинного алфавіту:. . . . . . Імовірність визначити.

3. Інформаційна надмірність повідомлень, складених з 8-літерного алфавіту, дорівнює 0,3. Визначити середню кількість інформації, що припадає на 1 знак такого повідомлення.

4. Комбінація комбінованого інверсного коду має вигляд: 110111111111. Яке число передавалося?

5. Закодувати кореляційним кодом наступну комбінацію 11111001.