Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Комп'ютерні науки
Кафедра:
Не вказано
Інформація про роботу
Рік:
2002
Тип роботи:
Методичні вказівки до лабораторної роботи
Предмет:
Методи та засоби комп’ютерних інформаційних технологій
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
.
КОДИ ХЕМІНГА
МЕТОДИЧНІ ВКАЗІВКИ
до лабораторної роботи з курсу
“Методи та засоби комп’ютерних
інформаційних технологій”
для студентів базового напрямку
6.08.04 “Комп’ютерні науки”
Затверджено
на засіданні кафедри
“Системи автоматизації проектування”
Протокол № 9 від 07.02.2002 р.
Львів – 2002
Коди Хемінга: Методичні вказівки до лабораторної роботи з курсу “Методи та засоби комп’ютерних інформаційних технологій” для студентів базового напрямку 6.08.04 “Комп’ютерні науки”.
/ Укл.: В.В. Мазур. – Львів: Видавництво Національного університету “Львівська політехніка”, 2002. - 9 с.
Укладач Мазур В.В., канд, техн, наук, доц.
Відповідальний за випуск Ткаченко С.П., канд, техн. наук, доц.
Рецензенти Каркульовський В.І., канд. техн.наук.,доц.
МЕТА РОБОТИ
Мета роботи - вивчення методiв побудови кодiв Хемiнга та їх програмна реалiзацiя для практичного використання.
КОРОТКІ ТЕОРЕТИЧНІ ВІДОМОСТІ
2.1. Завадостійке кодування.
Завадостійкі коди – це один із найефективніших засобів забезпечення високої достовірності передачі інформації. Розвиток цього напрямку зумовлений використанням мікропроцесорної техніки у системах зв’язку.
Завадостійке кодування базується на теоремі Шеннона для передачі дискретної інформації по каналу із завадами: “Імовірністть помилкового декодування може бути як завгодно малою при виборі відповідного способу кодування”. Теорема вказує на принципову можливість, але не визначає спосіб кодування. Це обумовило інтерес до розробки завадостійких кодів.
Під завадостійкими розуміють коди, які дозволяють виявляти чи виявляти і виправляти помилки, які виникли через вплив завад.
Завадостійкість кодування забезпечується за рахунок внесення надлишковості в кодові комбінації, тобто крім інформаційних є і надлишкові (додаткові) розряди.
Всі завадостійкі коди поділяються на два класи:блочні та неперервні [1].
В блочних кодах кожному повідомленню (або елементу повідомлення) відповідає кодова комбінація (блок) із певної кількості сигналів. Блоки кодуються і декодуються окремо один від одного. Блочні коди можуть бути рівномірними (довжина кодових комбінацій n – постійна), або нерівномірними (n – міняється). Нерівномірні практично не використовуються через складність їх технічної реалізації.
В неперервних кодах внесення надлишковості в послідовність вхідних символів здійснюється без розбивки на окремі блоки. Для неперервних кодів процеси кодування та декодування мають теж неперервний характер. Цей напрям тільки розвивається.
Блочні і неперервні коди в залежності від методів внесення надлишковості поділяють на роздільні та нероздільні.
В роздільних чітко визначена роль окремих символів. Одні символи є інформаційні, інші є перевірочними і забезпечують виявлення і виправлення помилок.
Роздільні блочні коди називають ще n, k – кодами, де n – довжина кодових комбінацій, k – кількість інформаційних символів в комбінаціях.
У нероздільних кодах немає чіткого поділу символів кодової комбінації на інформаційні та перевірочні. Таких кодів мало.
Роздільні блочні коди поділяються на систематичні і несистематичні. Несистематичні будуються таким чином, що перевірочні символи визначаються як сума підблоків, на які поділяється блок інформаційних символів.
Більшість відомих роздільних кодів є систематичними кодами. Для цих кодів перевірочні символи визначаються в результаті проведення лінійних операцій над певними інформаційними символами.
Декодування зводиться до перевірки на парність певних груп символів. В результаті цих перевірок отримується інформація про наявність помилок, а при потребі і про позицію помилкових символів.
2.2. Основні принципи завадостійкого кодування.
Будемо розглядати блочні рівномірні двійкові завадостійкі коди. Кількість розрядів n в кодовій комбінації називається довжиною коду. Символи коду – 0,1. Кількість одиниць в кодовій комбінації називається її вагою w.
Наприклад: 100101100 – n=9, w=4.
Кодова віддаль d визначається кількістю позицій чи символів, в яких кодові комбінації відрізняються одна від одної і рівна вазі суми (по модулю 2) цих кодових комбінацій
100101100
+ 110110101
_________
010011001 w=4, d=4.
За рахунок впливу завад в одному чи кількох рядках кодової комбінації можуть з’являтися помилки (0 ( 1, 1(0).
По кількості помилкових розрядів помилки бувають одно, двох і більше кратними.
Експериментальні дослідження показали, що помилки символів при передачі по каналу зв’язку групуються у пачки різної тривалості. Пачка – це участок послідовності символів, які починаються і закінчується помилковими символами. В середині пачки можуть бути і окремі правильні символи.
Для визначення місця помилкових символів у кодовій комбінації використовується вектор помилки е (n – розрядна комбінація, одиниці якої вказують місце помилкових символів). Наприклад, е = 01100 – третій і четвертий символи справа – помилкові.
Сума по модулю 2 спотвореної кодової комбінації і вектора помилки дає правильну комбінацію.
Звадостійкість кодування забезпечується надлишковістю (k<n). Тобто із загальної кількості No = 2n можливих кодових комбінацій для передачі інформації використовується тільки N = 2k комбінацій, тобто множина No ділиться на дві групи N=2k – множина дозволених і (No-N)=2n-2k множина заборонених комбінацій. Якщо прийнята комбінація заборонена, то це означає, що сигнал створений в каналі. Якщо дозволена – то або комбінація без спотворень, або був перехід з однієї дозволеної в іншу.
У загальному випадку кожна із N дозволених комбінацій може перетворитись у будь-яку із No можливих, тобто можливі N* No варіантів передачі, з них N варіантів безпомилкові, N*(N-1) - перехід із одних дозволених у інші дозволені, N*(No-N) – перехіід із дозволених у заборонені.
Таким чином не всі спотворення можуть бути виявлені. Частка помилкових комбінацій, що можуть бути виявлені визначається як
;
Для використання коду як коректуючого, множина заборонених кодових комбінацій розбивається на N підмножин Mі , що не перетинаються. Кожна їз цих підмножин відповідає одній із дозволених комбінацій Аі . Якщо прийнята заборонена комбінація належить підмножині Mі , то вважається, що передана комбінація Аі. Помилка буде виправлена лише тоді, коли заборонена комбінація утворилася із Аі . Таким чином, помилка виправляється в (N0-N) випадках (тільки для заборонених комбінацій). Частка виправлених помилкових комбінацій із загальної кількості виявлених помилкових рівна
;
Спосіб розбиття на підмножини залежить від того які помилки повинні виправлятися даним кодом.
2.3. Зв’язок коректуючої здатності коду і кодової віддалі.
Кодова віддаль характеризує ступінь відмінності між двома довільними кодовими комбінаціями. Найменша віддаль між дозволеними кодовими комбінаціями dmin - важлива характеристика коду, яка визначає його виявляючу і коректуючу здатність. Якщо необхідно побудувати код, який виявляє всі помилки кратністю t і нижче – це значить із множини N0 можливих вибрати N дозволених комбінацій так, щоб будь-яка з них в сумі по модулю 2 із будь-яким вектором помилок з вагою Wі не більшою t, не дала б в результаті іншої дозволеної комбінації. Для цього необхідно, щоб кодова віддаль dmin була не меншою t+1. Для виправлення виявленої помилки необхідно щоб кодова віддаль між двома дозволеними комбінаціями була не меншою ніж t+2. Це забезпечує утворення для кожної із дозволениих комбінацій множини заборонених, яка, при заданій кратності помилки, не перетинається із множинами заборонених для інших дозволених, що дає можливість однозначно виправити помилку. Очевидно, що виправлення помилок зведенням до дозволеної будь-якої комбінації із її множини заборонених базується на гіпотезі, що мала місце помилка з кратністю не більше t. Однак на практиці не виключена можливіть виникнення помилки з більшою кратністю і тоді помилкова кодова комбінація буде неправильно виправлена до найближчої дозволеної. Таким чином методи виправлення помилок мають імовірнісний характер.
2.4. Код Хемінга.
Код Хемiнга належить до найважливiших лiнiйних кодiв, якi широко використовуються на практицi i мають зручний для технiчноi реалiзацii алгоритм виявлення та виправлення однiєї помилки.
Код складаеться з k iнформацiйних двійкових розрядів та n-k контрольних. Загальна кількість розрядів у кодi n. Нумерація розрядів здійснюється справа наліво від 1 до n.
Число n повинно задoвiльняти нерiвнiсть 2n-k не менше n+1. Для визначення основних параметрiв коду Хемiнга задається кiлькiсть iнформацiйних розрядів k, по яких обчислюється n та n-k. Кiлькiсть iнформацiйних k та контрольних n-k розрядів коду, який виявляє та коректує одну помилку приведена в таблиці.
k
1…4
5…11
12…26
27…57
58…120
121…247
n-k
3
4
5
6
7
8
n
7
15
31
63
127
255
На основi основних параметрiв коректуючого коду визначають позицii інформаційних та контрольних розрядів. Позиції контрольних розрядів вибираються по значенню степенi 2і, де i=0,1,2,3... Тобто номери контрольних розрядів будуть рiвнi 1,2,4,16... Між контрольними розрядами справа наліво вписуються інформаційні. Потiм визначають значення контрольних розрядів по такому правилу: сума одиниць на перевiрочних позицiях для даного контрольного розряду повинна бути непарною. Якщо ця сума непарна, то контрольний розряд встановлюється рiвним нулю, якщо парна – одиницi (доповнення до непарності).
Перевiрочнi позицii вибирають таким чином. Cкладають таблицю для ряду натуральних чисел у двiйковому кодi. Кiлькiсть чисел - n. Потiм визначають перевiрочнi позицii по такому правилу: в першу перевiрку входять розряди, якi мiстять одиницю в першому розрядi справа (1,3,5,7 і т.д.), в другу - в другому (2,3,6,7…) і т.д.
8 7 6 5 4 3 2 1
1
0
0
1
1
0
1
0
12 11 10 9 8 7 6 5 4 3 2 1
1
0
0
1
0
1
0
1
0
0
0
0
1
0
0
0
1100 1011 1010 1001 1000 0111 0110 0101 0100 0011 0010 0001
Рис.1. Формування коду Хемінга.
Для виявлення і виправлення одиночноi помилки в прийнятій кодовій комбінації проводять перевiрку на непарнiсть. Для першоi перевiрки сумують розряди для позицiй, що мiстять одиницю в молодшому розрядi (1,3,5,7...). Якщо кількість одиниць парна, то перший розряд справа для двійкового значення номера помилкової позиції (синдрома) встановлюється рівним одиниці. Потім сумуючи розряди для позицій, що містять одиницю у другому двійковому розряді, і перевіряючи суму на непарність визначають значення другого розряду синдрома. Процес повторюється для позицiй, що містять одиниці у розрядах 3,4,5 i т.д. В результатi формується номер помилкової позицiї коду. Для виправлення помилки символ у цiй позицii необхiдно замiнити на протилежний. Якщо синдром рівний нулю, то прийнята комбінація не містить одиночних помилок. Наприклад, при помилці в шостому розряді визначене значення синдрому буде рівне 0110.
Формування коду Хемінга і виправлення помилкових розрядів може бути реалізоване апаратурно (рис. 2) [2].
Рис. 2. Апаратурна реалізація коду Хемінга.
КОНТРОЛЬНІ ЗАПИТАННЯ
1. На чому базуються виявляючi та коректуючi властивостi коду Хемiнга?
2. Як визначаються iнформацiйнi та перевiрочнi позицii у кодi Хемiнга?
3. Як знаходиться номер помилковоi позицii у кодi Хемiнга?
4. ЛАБОРАТОРНЕ ЗАВДАННЯ
Ознайомтесь з методом побудови коду Хемiнга.
Для заданого варіанту вручну побудуйте код Хемінга, внесіть і виявіть помилку.
3. Розробiть алгоритм та реалiзуйте програму побудови коду Хемiнга.
Реалiзуйте програму перевiрки та виправлення кодових послiдовностей.
Перевiрте працездатнiсть програм на тестових прикладах.
ОФОРМЛЕННЯ ЗВІТУ
1. Короткий опис методу та алгоритму побудови коду Хемiнга.
2. Опис методу та алгоритму перевiрки та виправлення кодових послiдовностей.
3. Результати побудови коду та виправлення помилки вручну.
3. Тексти програм.
4. Результати тестування прогорам.
6. ЛІТЕРАТУРА
Цымбал В.П. Теория информации и кодирование.: - К.: Вища школа, 1992.
2. У.Титце, К. Шенк. Полупроводниковая схемотехника.: - М.: Мир, 1982.
Варіанти індивідуальних завдань
Для заданої інформаційної частини побудувати завадостійкий код, внести помилку у четвертий розряд коду, виявити її і виправити.
Варіант
1
2
3
4
5
6
7
8
Інформацій-на частина
10101111
11001100
10011100
11000011
10100101
10110100
10110110
10011010
Варіант
9
10
11
12
13
14
15
16
Інформацій-на частина
10111011
10111101
10111110
1011100
10100011
10110111
11100011
11110000
НАВЧАЛЬНЕ ВИДАННЯ
КОДИ ХЕМІНГА
МЕТОДИЧНІ ВКАЗІВКИ
до лабораторної роботи
з курсу “Методи та засоби комп’ютерних
інформаційних технологій”
для студентів базового напрямку 6.0804 “Комп’ютерні науки”
Укладач Мазур Віталій Володимирович
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора