Основи теорії інформації
Практична робота № 4
«Кодування інформації при передачі по дискретному каналу з перешкодами»
Мета. закріпити теоретичні знання та отримати практичні навички кодування інформації по дискретному каналу з перешкодами шляхом застосування завадостійкого коду Хеммінга. Навчиться визначати парні і непарні помилки в повідомленнях, одинарні. Отримати навички виправлення одинарних помилок в повідомленнях.
Код Хеммінга - це алгоритм Самоконтролюючою і самокорегуюча коду, який дозволяє закодувати будь-яке інформаційне повідомлення певним чином і після передачі (наприклад, по мережі) визначити з'явилася якась помилка в цьому повідомленні (до при-міру через перешкоди) і , при можливості, відновити це повідомлення. В даному прикладі описаний са-мий простий алгоритм Хемминга, який може виправляти лише одну помилку (існують більш досконалі модифікації даного алгоритму, які дозволяють виявляти (і якщо можливо виправляти) більша кількість помилок).
Код Хеммінга складається з двох частин. Перша частина кодує вихідне повідомлення, вставляючи в нього в певних місцях контрольні біти (обчислені особливим чином). Друга частина отримує вхідне повідомлення і заново обчислює контрольні біти (за тим же алгоритмом, що і перша частина). Якщо все знову обчислені контрольні біти збігаються з отриманими, то повідомлення отримано без помилок. В іншому випадку, виводиться повідомлення про помилку і при можливості помилка виправляється.
Припустимо, у нас є повідомлення «habr», яке необхідно передати без помилок. Для цього спочатку потрібно наше повідомлення закодувати за допомогою Коду Хеммінга. Нам необхідно представити його в бінарному вигляді.
На цьому етапі варто визначитися з, так званої, довжиною інформаційного слова, тобто довжиною рядки з нулів і одиниць, які ми будемо кодувати. Припустимо, у нас довжина слова бу-дет дорівнює 16. Таким чином, нам необхідно розділити наше вихідне повідомлення ( «habr») на блоки по 16 біт, які ми будемо потім кодувати окремо один від одного. Так як один символ займає в пам'яті 8 біт, то в одне кодуються слово поміщається рівно два ASCII символу. Отже, ми отримали дві бінарні рядки по 16 біт:
кодуються незалежно один від одного. Розглянемо, як це робиться на прикладі першої частини.
Перш за все, необхідно вставити контрольні біти. Вони вставляються в строго певних місцях - це позиції з номерами, рівними ступенями двійки. У нашому випадку (при довжині інфор-мационного слова в 16 біт) це будуть позиції 1 (2 0), 2 (2 1), 4 (2 + 2), 8 (2 3), 16 (2 4). Відповідно, у нас вийшло 5 контрольних біт (підкреслені):
Таким чином, довжина всього сполучення збільшилася на 5 біт. До обчислення самих контрольних біт, ми присвоїли їм значення «0».
Обчислення контрольних біт
Тепер необхідно обчислити значення кожного контрольного біта. Значення кожного кон-контрольних біта залежить від значень інформаційних біт, але не від усіх, а тільки від тих, які цей контрольних біт контролює. Для того щоб зрозуміти, за які біти відповідає кожних контрольний біт необхідно зрозуміти дуже просту закономірність: контрольний біт з номером N контролює всі наступні N біт через кожні N біт, починаючи з позиції N:
Тут знаком «X» позначені ті біти, які контролює контрольний біт, номер якого справа. Тобто, наприклад, біт номер 12 контролюється битами з номерами 4 і 8. Ясно, що щоб дізнатися якими битами контролюється біт з номером N треба просто розкласти N за ступенями двійки.
Далі обчислюємо значення кожного контрольного біта: беремо кожен контрольний біт і дивимося скільки серед контрольованих ним бітів одиниць, отримуємо деяке ціле число і, якщо воно парне, то ставимо нуль, в іншому випадку ставимо одиницю. Можна звичайно і навпаки, якщо число парне, то ставимо одиницю, в іншому випадку, ставимо 0. Головне, щоб в «кодує» і «декодирующей» частинах алгоритм був однаковий. (Ми будемо застосовувати перший варіант).
Вирахувавши контрольні біти для нашого інформаційного слова отримуємо наступне: