Аналіз сучасних кодів із захистом від помилок
Методичні вказівки до виконання лабораторної роботи №6
з курсу «Теорія інформації та кодування»


Архів з матеріалами для виконання роботи можно скачати тут (пароль TIK2018).
Приклад оформлення звіту тут.

Мета роботи:
- закріпити знання про різновиди кодів із захистом від помилок і напрями їх застосування;
- дослідити коригувальну здатність коду Хеммінга, циклічного коду та згорткового коду Фінка за допомогою їх моделювання;
- закріпити теоретичні знання про побудову лінійних завадозахисних кодів.

Короткі теоретичні відомості

Коди із захистом від помилок широко використовуються для виявлення і виправлення помилок при передачі та зберіганні інформації. До складу найбільш вживаних належать:
- код з перевіркою парності по рядках та по рядках і стовпцях (він був розглянутий в лабораторній роботі №5)
- код Хеммінга з виправленням однократних помилок (застосовується для забезпечення надійності зберігання даних в серверній оперативної пам'яті);
- циклічний CRC-код із можливістю для виявлення «пачок» помилок (використвується при передачі даних по лініях зв'язку і зберіганні файлів на магнітних дисках);
- згорткові коди, зокрема код Фінка з виправленням помилок безпосередньо в потоці передачі даних (їх різновиди застосовуються в мобільному зв'язку).

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

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

У всіх випадках оцінка коригуючої здатності коду спирається в першу чергу на величину його мінімальної кодової відстані по Хеммінгу dmin, хоча враховує при цьому додаткові властивості конкретного коду.
Теоретичний матеріал про завадозахисні коди викладено в лекціях 10 та11.

Зміст роботи

Ця лабораторна робота включає три розділи:
- аналіз коду Хеммінга з виправленням однократних помилок;
- аналіз циклічного CRC-коду з виявленням пачок помилок;
- аналіз згорткового коду Фінка з виправленням помилок в потоці передачі даних та схеми каскадного кодування.


У всіх розділах виконується експериментальне дослідження коригуючої здатності відповідних кодів за допомогою демонстраційної програми correcting-code. Такому дослідженню повинно передувати загальне знайомство з кодом (принципом його дії, можливостями і областю застосування). В якості даних при моделюванні передачі використайте свій 16-ковий номер в списку підгрупи або його подвоєне значення. Також при поглибленому вивченні кодів використвуються додаткові демонстраційні програми, які відображують роботу кодів більшої розрядності.

Порядок виконання роботи

1) Аналіз коду Хеммінга з виправленням однократних помилок
а) Розберіться з принципом дії і коригуючою здатністю коду. Помістіть в звіт його коротку характеристику.
б) За допомогою демонстраційної програми correcting-code дослідіть можливості коду з параметрами 7,4: виправлення одноразової помилки; пропуск помилок подвійний кратності. При виконанні експериментів звертайте увагу на правильність формування контрольних розрядів і синдрому помилки відповідно до рівнянь коду.
* в) Розберіться з математичним апаратом коду Хемінга, який базується на перевірці ортогональності кодового вектору до перевірочної матриці.
** г) За допомогою демонстраційної програми Hemming_code познайомтеся з роботою 64-розрядної версії коду, яка застосовується в серверній пам'яті. Імітуйте внесення та виправлення одноразової помилки. Поясніть кількість використовуваних контрольних розрядів.

2) Аналіз циклічного CRC-коду з виявленням пачок помилок
а) Розберіться з принципом дії і коригуючою здатністю коду. Помістіть в звіт його коротку характеристику.
б) За допомогою демонстраційної програми correcting-code досліджуйте можливості коду з параметрами 7,4: виявлення пачки помилок довжиною m розрядів (в прикладі m = 3); можливість виявлення множинних помилок при m> 3. При виконанні експериментів звертайте увагу на вірність формування контрольних розрядів і синдрому відповідно до заданого утворюючого многочлену коду.
* в) Розберіться з математичним апаратом циклічного коду, який базується на перевірці ділимості поточного поліному коду на утворюючий поліном.
** г) За допомогою демонстраційної програми CRC_code познайомтеся зі схемною реалізацією циклічного кодування на базі зсувних регістрів з зворотними зв'язками. Виконайте і проаналізуйте приклад для коду (15,11).

3) Аналіз згорткового коду з виправленням помилок в потоці передачі даних та схеми каскадного кодування
а) Розберіться з принципом дії коду Фінка. Помістіть в звіт його коротку характеристику.
б) За допомогою демонстраційної програми correcting-code досліджуйте можливості коду з параметром s=0: виправлення одиничних помилок; пропуск подвійних помилок, а також при s=1 (виправлення парних помилок). При виконанні експериментів звертайте увагу на вірність формування контрольних розрядів відповідно до принципу контролю парності.
* в) Розберіться з роботою схеми каскадного кодування та відобразіть в звіті функції її основних рівнів.

Контрольні запитання

До розділу 1.
1) Опишіть дію коду Хеммінга з перевіркою і виправленням однократних помилок. Охарактеризуйте його застосування.
2) Охарактеризуйте коригувальну здатність коду в зв'язку з величиною dmin.
* 3) Опишіть визначення рівнянь кодування і декодування по Хеммінга виходячи із заданої утворючої і перевірочної матриці (використовуйте приклад коду 7,4).
* 4) Поясніть принцип математичного апарату коду Хеммінга.
** 5) Поясніть, яким чином в загальному випадку визначається кількість перевірочних розрядів коду Хеммінга на прикладі 64-розрядного коду.

До розділу 2.
1) Опишіть дію циклічного CRC-коду з виявленням пачок помилок. Охарактеризуйте його застосування.
2) Охарактеризуйте коригувальну здатність коду.
* 3) Опишіть вибір утворюючого многочлену коду. Наведіть приклади стандартних многочленів CRC-кодів.
* 4) Поясніть принцип математичного апарату циклічних кодів.
** 5) Поясніть, роботу схеми CRC-кодування на прикладі з демо-програми.

До розділу 3.
1) Опишіть дію згорткового коду Фінка з виправленням одиничних помилок в потоці даних. Охарактеризуйте його застосування.
2) Охарактеризуйте переваги і недоліки згорткових кодів (зокрема коду Фінка) порівняно із блоковими кодами (зокрема, кодом CRC)
* 3) Поясніть спосіб роздріблення ”пачок” помилок перемежінням.
* 4) Поясніть дію каскадної схеми кодування із захистом від помилок.
О дисциплине ТИК
Почему «Теория информации и кодирования» - одна из самых интересных дисциплин, которые изучают будущие системщики и защитники информации?

В ней сочетаются золотая классика и самая актуальная современность computer-science.

продолжение
О сайте
Здесь вы найдете материалы, которые помогут в изучении дисциплины “Теория информации и кодирования” (ТИК) в том виде, как она преподается на кафедре ЭВМ ДИИТа.

На сайте размещены методические материалы:
  • электронный конспект лекций;
  • методическое обеспечение к лабораторным работам;
  • полезные ссылки.

продолжение
© 2008-2013 • Теория информации и кодирования
UP