ДОСЛІДЖЕННЯ КОДІВ ХЕМІНГА.. Методичні вказівки з Методи кодування інформації. Робота № 203567

Перехід до торгівельного партнера Binance

ДОСЛІДЖЕННЯ КОДІВ ХЕМІНГА.

Інформація про навчальний заклад

ВУЗ:

Національний університет Львівська політехніка

Інститут:

Не вказано

Факультет:

Не вказано

Кафедра:

Кафедра Телекомунікацій

Інформація про роботу

Рік:

2001

Тип роботи:

Методичні вказівки

Предмет:

Методи кодування інформації

Завантажити

Частина тексту файла (без зображень, графіків і формул):

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ Національний університет “Львівська політехніка” Кафедра “Телекомунікації” ДОСЛІДЖЕННЯ КОДІВ ХЕМІНГА Методичні вказівки до лабораторної роботи № 3 з курсу «Методи кодування інформації» для студентів базового напрямку «Телекомунікації» Львів 2001 “Дослідження кодів Хемінга”. Методичні вказівки до лабораторної роботи № 3 з курсу “Методи кодування інформації” для студентів базового напрямку 0924 - “Телекомунікації”. - Львів 2001. – 6 с. Автори: доцент Коваль Б.В. ст. викладач Чайковський І.Б. Рецензенти: професор, д.т.н. Оганесян А.Г. доцент, к.т.н. Волочій Б.Ю. У лабораторній роботі досліджується процес виправлення однократних незалежних помилок систематичними кодами на прикладі досконалого коду Хемінга та ефекти розмноження помилок вищої кратності. Методичні вказівки затверджено на засіданні кафедри “Телекомунікації” Національного університету “Львівська політехніка” 04.04.2001 р., протокол № 8. Мета роботи Дослідити процес виправлення однократних незалежних помилок систематичними кодами на прикладі досконалого коду Хемінга та ефекти розмноження помилок вищої кратності. Теоретична частина. Одним з найбільш поширених систематичних кодів є код Хемінга. Відомо декілька різновидностей цих кодів, що характеризуються різними коректуючими здатностями. До них кодів звичайно відносяться коди з мінімальною кодовою відстанню dmin=3, які виправляють всі одиночні помилки, і коди з відстанню dmin=4, які виправляють всі одиночні і виявляють всі подвійні помилки, або ж виявляють всі потрійні помилки. Код Хемінга є одним з небагатьох досконалих кодів, для яких виконується ідеальне співвідношення між довжиною коду п та кількістю перевірочних r або інформаційних к розрядів, що випливає з виразу (1) для границі Хемінга: п2 r-1 (1) Досконалий код Хемінга має кодову відстань dmin=3 і відповідає випадку, коли досягається крайнє значення границі Хемінга: n=2 r-1. Отже, його параметри (n, k) = (2 r-1, 2 r-1-r),’ де r=2, 3,... - кількість перевірочних розрядів. В табл.1 наведені параметри деяких кодів Хеммінга. Коди Хемінга відносяться до швидких кодів. Характерною особливістю матриці перевірки Н коду з dmin=3 є те, що її стовбці представляють собою будь-які ненульові комбінації довжиною r. Отже ми, наприклад, можемо отримати матрицю Н для коду (15, 11), з r=4 i n=15, записавши у двійковому вигляді всі числа від 1 до (2 r-1)=15 у вигляді стовбчиків матриці: Н15,11= EMBED Equation.2 (2) Перестановкою стовбців, що містять одну одиницю, дану матрицю можна звести до канонічної форми: Н15,11= EMBED Equation.2 (3) Кодування Знаючи матрицю Н, легко побудувати матрицю G і всі її робочі кодові комбінації. Декодування Отримавши кодову комбінацію (КК), ми обчислюємо синдром і дивимось, з яким стовбцем матриці він співпадає: - якщо синдром рівний нулеві, прийнята КК вважається правильною і з неї видаляємо перевірочні розряди; - якщо синдром не нульовий, тоді знаходимо номер стовбчика матриці Н, що рівний синдромові, і виправляємо помилку у розряді прийнятої КК, що має цей же номер, або робимо висновок, що прийнята КК - помилкова. Хемінг запропонував використовувати матрицю Н не в канонічному вигляді (3), а у вигляді (2) -номер стовбчика у двійковому вигляді співпадає з елементами у цьому ж стовбчику. Тоді перевірочні розряди КК повинні знаходитись не в кінці КК, а на номерах позицій, що відповідають степені 2: 20, 21, 22,..., 2 r-1. У цьому випадку синдром, отриманий з прийнятої КК, буде двійковим номером розряда КК, у якому виникла помилка, що значно полегшує процес декодування. Наприклад, для матриці (2) перевірочними будуть 1, 2, 4 та 8 розряди, а інформаційними - 3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15. Повідомлення 11010101011 після кодування матиме вигляд 011110100101011. Якщо помилка виникла в 7-ому розряді, тоді прийнята КК буде 01110000101011 синдром, після підрахунку, буде мати вигляд 0111, тобто 710. Отже, помилка виникла в 7-у розряді. Таблиця 1. Параметри кодів Хеммінга Розширений код Хемінга має кодову відстань dmin=4 і може бути отриманий з досконалого коду Хеммінга шляхом додавання до нього перевірочного розряду, що є результатом суми по модулю два всіх символів кодової комбінації. Це код виду (2 r-1, 2 r-1-r), n  2 r-1. Кодування виконується в два етапи: -визначаєтся КК з використанням матриці H що відповідає досконалому коду Хеммінга; - додається ще один розряд, що дорівнює сумі по модулю два всіх розрядів КК, отриманої на першому етапі. Матриця Н розширеного коду Хемінга буде мати вигляд (тобто (3) доповнена справа нулями, а знизу - одиницями): H= EMBED Equation.2 (4) Декодування: -обчислюється синдром, який відповідає досконалому коду Хеммінга; -перевіряється останнє перевірочне співвідношення. При декодуванні може виникнути чотири наступні ситуації: 1. Синдром не дорівнює нулю, перевірка на парність виконується - двократна помилка. 2. Синдром не дорівнює нулю, перевірка на парність не виконується - однократна помилка. 3. Синдром дорівнює нулю, перевірка на парність виконується - нема помилок (до 2-х кратної включно). 4. Синдром дорівнює нулю, перевірка на парність не виконується - потрійна чи інша непарна помилка >3. Розрахункова частина. 1. Розрахувати імовірність невиявленої помилки для досконалих кодів Хемінга (7,4) та (15,11), що виправляють однократні помилки, для p0 = 0.1; 0.025; 0.01; 0.002. 2. Розрахувати імовірність невиявленої помилки для досконалого коду Хемінга (7,4), що виявляє помилки, для p0 = 0.1; 0.025; 0.01; 0.002. Порядок виконання. 1. Створити пустий файл розміром 500 байт. 2. За допомогою програми-кодера закодувати файл кодом Хеммінга. 3. Запустити модель телекомунікаційної системи зв’язку. 4. Передати закодований файл через канал з незалежними помилками. 5. Отриманий спотворений файл декодувати за допомогою програми-декодера. 6. Підрахувати кількість спотворених блоків після виконання п. 4 та п. 5. 7. Обчислити імовірність невиявленої помилки для декодованого файлу та порівняти її з розрахованою імовірністю невиявленої помилки для даного коду. 8. Повторити п.п. 1 - 7 для різних значень p0 = 0.1; 0.025; 0.01; 0.002. Контрольні запитання. 1. Назвати коди Хеммінга, вказати їх коректуючі властивості. 2. Як визначається довжина коду Хеммінга? 3. Як виглядають перевірочні матриці для кодів Хеммінга? 4. В чому полягає декодування для кодів Хеммінга? Література Цымбал В.П. Теория информации и кодирование. - 1992. Кузьмин И.В., Кедрус В.А. Основы теории информации и кодирования: Учебник для вузов, 2-е изд., перераб. и доп. -1986. Кларк Д., Кейн Д. Кодирование с исправлением ошибок в системах цифровой связи. - 1987. Коваль Б.В. Конспект лекцій з курсу „Методи кодування інформації” для студентів базового напрямку „Телекомунікації”. – Львів, 2001. Підписано до друку 14.05.2001. Папір офсетний. Друк офсетний. Умов.-друк. арк. 0,38. Формат 60х84 1/16. Наклад 100 прим. Зам. 1021. Віддруковано в НВМ Поліграфічного технікуму УАД 79008, м. Львів, пл. Митна, 1

Методичні вказівки Методи кодування інформації

01.01.1970 03:01-

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

Маєш корисні навчальні матеріали, які припадають пилом на твоєму комп'ютері? Розрахункові, лабораторні, практичні чи контрольні роботи — завантажуй їх прямо зараз і одразу отримуй бали на свій рахунок! Заархівуй всі файли в один .zip (до 100 МБ) або завантажуй кожен файл окремо. Внесок у спільноту – це легкий спосіб допомогти іншим та отримати додаткові можливості на сайті. Твої старі роботи можуть приносити тобі нові нагороди!

поділитись