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


Шаблон оформлення звіту можна одержати тут.
Комплект матеріалів до виконання роботи (демо-програми) можна скачати звідсіля.


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

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

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

Теоретичний матеріал про завадозахисні коди викладено в лекціях 8 -10.

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

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

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

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

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

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

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

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

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

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

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

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