Кафедра А втоматікі і І Інформаційні Т ехнологія
Лабораторна робота
"ПРОГРАМНИЙ кодер-декодером для циклічних (n, k) - КОДІВ"
1. Переслідувані мети
Проведення лабораторних робіт з даної тематики переслідує такі цілі:
- Закріплення теоретичного матеріалу, який стосується основних положень математичної теорії лінійних (n, k) - кодів;
- Усвідомлення механізму кодування пакетів даних при передачі файлів;
- Практичне освоєння алгоритмів кодування і декодування стосовно циклічним (n, k) - кодами.
2. Необхідні відомості з теорії
Відомо, що циклічні коди з усіх завадостійких кодів знаходять найбільше застосування на практиці.
Циклічні коди є підклас (підмножина) лінійних (n, k) - кодів. Це означає, що всі положення теорії, які справедливі для нециклічних лінійних (n, k) - кодів, справедливі і для кодів циклічних. Але циклічні коди мають декілька додаткових позитивних властивостей, зокрема, вони «гостро реагують» на близько розташовані в кодовому слові помилки, так звані «пачки помилок». Крім того, для них знайдені надзвичайно прості алгоритми кодування та декодування. Все це і забезпечило їм широке застосування на практиці. Їх застосування обумовлено багатьма міжнародними стандартами, що регламентують роботу каналів передачі.
Для опису циклічних кодів паралельно використовується представлення кодових слів і двійковим вектором, і многочленом від деякої формальної змінної x. Постійно доводиться переходити від однієї форми подання до іншої. Одну й ту ж двійкову послідовність позначимо V, якщо вона розглядається як вектор, або V (x), якщо вона інтерпретується як многочлен.
2.1 Конструктивне визначення циклічного (n, k) - коду
Циклічним (n, k) - кодом називається безліч многочленів мірою не більше (n -1), кожен з яких без остачі ділиться на (спеціально підібраний) породжує многочлен G (x) ступеня (n - k), що є дільником бінома x n +1 .
Циклічний код зі словами довжини n і з породжує многочленом G (x) існує тоді і тільки тоді, коли G (x) ділить x n +1 [1]. У лекційному курсі було показано, що ця вимога подільності бінома x n +1 на G (x) випливає зі специфіки визначення операції символічного множення многочленів (за модулем бінома x n +1). Для того, щоб максимізувати безліч слів породжуваного коду при фіксованих значеннях довжини слів n і кодового відстані d 0, многочлен G (x) повинен бути непріводімим дільником ступеня (nk).
2.2 Алгоритм кодування
На практиці найчастіше застосовується алгоритм кодування, який формує систематичний разделімие код. В основу такого алгоритму покладено операція ділення на G (x). Систематичні разделімие коди привабливі тим, що процедуру кодування, тобто перетворення інформаційного вектора A (довжини k) у вектор коду V (довжини n> k) вдається звести лише до формування (nk) контрольних біт.
Крок 1. Попередньо вектор A «отнорміруем за форматом» під довжину n, скориставшись операцією множення многочленів A (x) × x nk. Як було показано в лекційному курсі - це еквівалентно зсуву вектора A на (nk) позицій вліво. Твір многочленів мовою векторів має довжину n. Істотно для подальшого, що праві (nk) позицій виявляються неодмінно нульовими.
Крок 2. Твір A (x) × x n - k розділимо на G (x). Ясно, що в загальному випадку вона не зобов'язана ділитися на G (x) без остачі. Тому слід записати
A (x) × x nk = Q (x) × G (x) + R (x),
де Q (x) - частка від ділення;
R (x) - залишок. Це многочлен ступеня не більше (n - k -1), тому що дільник має ступінь (n - k) за визначенням. Як вектор він має довжину (n - k).
Крок 3. Перенесемо залишок R (x) у ліву частину рівності. Отримаємо:
A (x) × x nk + R (x) = Q (x) × G (x).
Тепер в лівій частині ми отримуємо многочлен, який без остачі ділиться на G (x), а це за визначенням - многочлен, що належить циклічним (n, k) - коду. У цієї останньої операції залишок R складається з нулями (див. шаг1 алгоритму). Отже, кінцевий підсумок еквівалентний конкатенірованію R до вектора А.
2.3 Алгоритм декодування
Відомо кілька алгоритмів декодування циклічних (n, k) - кодів. У даній лабораторній роботі досліджується «декодування по синдрому», роль якого (синдрому) грає залишок від ділення Декодовані многочлена F (x) на G (x). Декодування може проводитися з метою тільки виявляти помилки або з метою виправляти помилки кратності до t включно. У будь-якому випадку мета досягається у декілька кроків алгоритму.
2.3.1 Декодування з виявленням помилок
Крок 1. Обчислення залишку R (x);
Крок 2. Аналіз залишку «на нуль». Нульовий залишок означає, що помилки не виявлені;
2.3.2 Декодування з виправленням помилок
Крок 1. Обчислення залишку R (x);
Крок 2. Обчислення за знайденому залишку передбачуваного (найбільш ймовірного) многочлена помилки Е (х);
Крок 3. Виправлення Декодовані вектора F шляхом підсумовування F + E = V;
3. Параметри досліджуваних кодів
Щоб трудомісткість лабораторних робіт погодити з відпущеним часом, досліджуються короткі (за мірками практики) коди. Параметри кодів наведено у таблицях 1 - 3.
Узгодьте з викладачем номер варіанта, з яким Ви будете працювати. Програми CODER і DECODER слід писати для одного варіанта коду.
Таблиця № 1. Варіанти завдань для (n, k) - кодів з довжиною слова n = 15
Таблиця № 2. Варіанти завдань для (n, k) - кодів з довжиною слова n = 31
Таблиця № 3. Варіанти завдань для (n, k) - кодів з довжиною слова n = 63
4. Порядок виконання лабораторної роботи CODER
Кінцевою завданням є написання та налагодження програми CODER, здатної перетворити пропонований файл. Програма повинна розглядати файл (не обов'язково двійковий) як послідовність двійкових векторів А j довжини k і перетворити його в інший файл - файл, що складається з слів V j довжини n надлишкового коду заданих параметрів.
Легко проглядається проміжна, технологічне завдання: потрібно мати кошти, за допомогою яких можна було б переконати себе і опонентів у тому, що програма CODER виконує перетворення потрібним чином. Назвемо цю програму налагоджувальної.
4.1 Інтерфейс налагоджувальної програми
Необхідно мати (хоча б) два «вікна»:
- Одне для введення вручну кодованого вектора А j заданих параметрів;
- Інше - для показу вихідного вектора V j (або тільки контрольних біт цього вектора).
Необхідно заздалегідь вручну обчислити кілька вихідних векторів V j, відповідних відомим А j. У викладача повинні бути заготовлені свої тестові слова коду. Таким чином можна буде забезпечити певний рівень довіри до кодує програмі [2].
4.2 Інтерфейс основний кодуючої програми CODER [3]
Необхідно передбачити можливість вибору вихідного (кодованого) файлу з каталогів Windows (або писати вручну в будь-якій «командної рядку» шлях до цього файлу). Необхідно передбачити можливість запам'ятовування вихідного файлу програми CODER на диску і можливість багаторазового повернення до аналізу цього файлу.
Вихідний файл (файли) програми CODER знадобляться при виконанні лабораторної роботи, пов'язаної з декодуванням.
4.3 Звіт з лабораторної роботи, захист результатів
Звіт повинен містити:
q короткий виклад постановки завдання;
q необхідні параметри вихідного коду і граф-схему алгоритму роботи основного кодує модуля з коментарями;
q характер і результати тестового кодування:
· (5 ... 6) «пар» вхідних і вихідних векторів кодера;
· Перевірка властивості замкнутості безлічі кодових векторів щодо операції підсумовування по mod2;
· Перевірка відстаней між кодовими векторами на відповідність вихідним вимогам.
Результати роботи програми CODER повинні бути продемонстровані викладачу.
5. Умови і порядок виконання лабораторної роботи DE CODER
Кінцевою завданням у цій роботі є не тільки практичне вивчення алгоритму декодування по синдрому (залишку) та налагодження декодуючої програми, а й вивчення структури (конфігурацій) виявляються і / або виправляє помилок, тобто непряма оцінка завадостійкості коду з конкретними заданими параметрами. Програма - DECODER повинна вміти декодувати пропонований файл.
Вихідними даними, предметом перетворень для програми DECODER повинен з'явитися вихідний файл програми CODER. Але як і в лабораторній роботі CODER, тут також знадобиться певна технологія налагодження основного модуля, за допомогою якої можна переконатися в правильності роботи програми DECODER і проаналізувати специфікації виявляються / виправляє помилок.
5.1 Інтерфейс отладочного модуля
Інтерфейс може бути побудований за принципом двох вікон - «вхідний» і «вихідна». Необхідно мати можливість вручну вводити Декодовані двійкову послідовність (неспотворене слово коду, спотворене слово, вектор помилки) і отримувати в вихідному вікні результат декодування (вид синдрому [4], структуру обчисленої (передбачуваної) помилки або виправлене слово коду, в залежності від конкретного варіанта завдання і Вашого рішення).
5.2 Елементарний план налагодження декодуючого модуля
1) Взяти 3-4 вектора коду V 1, V 2, V 3, V 4 і переконатися, що вони дають нульовий залишок;
2) подіяти на ці вектори помилками.
Маючи на увазі, що спотворення многочлена V j (х) моделюється операцією F j ℓ (х) = V j (х) + E ℓ (х), де многочлен E ℓ (х) символізує ℓ-ту конфігурацію помилок, результат обчислення синдрому ( залишку) R j ℓ (x) = F j ℓ (х) / G (x) можна представити як R ℓ (x) = E ℓ (х) / G (x) [5] Отже, при правильному функціонуванні програми DECODER повинні вийти залишки , що підкоряються такою схемою (табл. 4).
Таблиця 4
Якщо поведінка DECODER `а підпорядковується таблиці 4, його можна прийняти для подальшої роботи відповідно з індивідуальним завданням.
5.3 Варіант DECODER `а з виявленням помилок
Виходячи з характеристик G (x) і величини d 0, запропонувати конфігурації помилок, які програма неодмінно повинна виявляти і які не зобов'язана виявляти. Особливу увагу слід звернути на конфігурації помилок типу «пачка», вага яких знаходиться в межах (nk) ³ w (E)> (d 0 -1).
Знайти конфігурації необнаружіваемие помилок, сформулювати властивості (ознаки) таких помилок;
Результати дослідження звести в таблицю і забезпечити коментарями.
5.4 Варіант DECODER `а з виправленням помилок
Виходячи з характеристик G (x) і величини d 0, запропонувати конфігурації помилок, які ілюструють властивості коду положення щодо виправлення помилок. Підібрати конфігурації, що ведуть до «неправильного виправленню», тобто до вручення одержувачу кодового слова з непоміченими помилками, які залишаються після формально виконаної процедури виправлення.
6. Захист результатів, звіт з лабораторної роботи
Результати роботи програми DECODER повинні бути продемонстровані викладачу. Звіт повинен містити короткий виклад постановки задачі, необхідні параметри вихідного коду, граф-схему алгоритму роботи основного декодуючого модуля з коментарями, обсяг і результати тестового декодування (наприклад, в табличній формі) з докладними коментарями.
7. Швидкий кодер / декодер для циклічних кодів
Застосування швидкого алгоритму в лабораторній роботі не є обов'язковим для всіх. Він може бути використаний за бажанням студентів або за прямою вказівкою викладача.
Вище говорилося, що при циклічному кодуванні основною операцією алгоритмів кодування вхідної послідовності А (х) і декодування вихідний є операція поділу вираження А (х) х (nk) на породжує многочлен з метою знаходження залишку, який підсумовується з А (х) х (nk ) за mod2.
Труднощі програмної реалізації кодують і декодер модулів для циклічних кодів полягає в тому, що алгоритми, зазвичай, передбачають процедуру багаторазово повторюваного «бітового розподілу». Час кодування / декодування часто виявляється неприйнятним. Далі викладається математична суть алгоритму розподілу двійкових послідовностей, що дозволяє виконувати розподіл по частинах. «Крупністю» частин у відомих межах можна варіювати, домагаючись оптимізації процедури в конкретних умовах.
Лабораторна робота
"ПРОГРАМНИЙ кодер-декодером для циклічних (n, k) - КОДІВ"
1. Переслідувані мети
Проведення лабораторних робіт з даної тематики переслідує такі цілі:
- Закріплення теоретичного матеріалу, який стосується основних положень математичної теорії лінійних (n, k) - кодів;
- Усвідомлення механізму кодування пакетів даних при передачі файлів;
- Практичне освоєння алгоритмів кодування і декодування стосовно циклічним (n, k) - кодами.
2. Необхідні відомості з теорії
Відомо, що циклічні коди з усіх завадостійких кодів знаходять найбільше застосування на практиці.
Циклічні коди є підклас (підмножина) лінійних (n, k) - кодів. Це означає, що всі положення теорії, які справедливі для нециклічних лінійних (n, k) - кодів, справедливі і для кодів циклічних. Але циклічні коди мають декілька додаткових позитивних властивостей, зокрема, вони «гостро реагують» на близько розташовані в кодовому слові помилки, так звані «пачки помилок». Крім того, для них знайдені надзвичайно прості алгоритми кодування та декодування. Все це і забезпечило їм широке застосування на практиці. Їх застосування обумовлено багатьма міжнародними стандартами, що регламентують роботу каналів передачі.
Для опису циклічних кодів паралельно використовується представлення кодових слів і двійковим вектором, і многочленом від деякої формальної змінної x. Постійно доводиться переходити від однієї форми подання до іншої. Одну й ту ж двійкову послідовність позначимо V, якщо вона розглядається як вектор, або V (x), якщо вона інтерпретується як многочлен.
2.1 Конструктивне визначення циклічного (n, k) - коду
Циклічним (n, k) - кодом називається безліч многочленів мірою не більше (n -1), кожен з яких без остачі ділиться на (спеціально підібраний) породжує многочлен G (x) ступеня (n - k), що є дільником бінома x n +1 .
Циклічний код зі словами довжини n і з породжує многочленом G (x) існує тоді і тільки тоді, коли G (x) ділить x n +1 [1]. У лекційному курсі було показано, що ця вимога подільності бінома x n +1 на G (x) випливає зі специфіки визначення операції символічного множення многочленів (за модулем бінома x n +1). Для того, щоб максимізувати безліч слів породжуваного коду при фіксованих значеннях довжини слів n і кодового відстані d 0, многочлен G (x) повинен бути непріводімим дільником ступеня (nk).
2.2 Алгоритм кодування
На практиці найчастіше застосовується алгоритм кодування, який формує систематичний разделімие код. В основу такого алгоритму покладено операція ділення на G (x). Систематичні разделімие коди привабливі тим, що процедуру кодування, тобто перетворення інформаційного вектора A (довжини k) у вектор коду V (довжини n> k) вдається звести лише до формування (nk) контрольних біт.
Крок 1. Попередньо вектор A «отнорміруем за форматом» під довжину n, скориставшись операцією множення многочленів A (x) × x nk. Як було показано в лекційному курсі - це еквівалентно зсуву вектора A на (nk) позицій вліво. Твір многочленів мовою векторів має довжину n. Істотно для подальшого, що праві (nk) позицій виявляються неодмінно нульовими.
Крок 2. Твір A (x) × x n - k розділимо на G (x). Ясно, що в загальному випадку вона не зобов'язана ділитися на G (x) без остачі. Тому слід записати
A (x) × x nk = Q (x) × G (x) + R (x),
де Q (x) - частка від ділення;
R (x) - залишок. Це многочлен ступеня не більше (n - k -1), тому що дільник має ступінь (n - k) за визначенням. Як вектор він має довжину (n - k).
Крок 3. Перенесемо залишок R (x) у ліву частину рівності. Отримаємо:
A (x) × x nk + R (x) = Q (x) × G (x).
Тепер в лівій частині ми отримуємо многочлен, який без остачі ділиться на G (x), а це за визначенням - многочлен, що належить циклічним (n, k) - коду. У цієї останньої операції залишок R складається з нулями (див. шаг1 алгоритму). Отже, кінцевий підсумок еквівалентний конкатенірованію R до вектора А.
2.3 Алгоритм декодування
Відомо кілька алгоритмів декодування циклічних (n, k) - кодів. У даній лабораторній роботі досліджується «декодування по синдрому», роль якого (синдрому) грає залишок від ділення Декодовані многочлена F (x) на G (x). Декодування може проводитися з метою тільки виявляти помилки або з метою виправляти помилки кратності до t включно. У будь-якому випадку мета досягається у декілька кроків алгоритму.
2.3.1 Декодування з виявленням помилок
Крок 1. Обчислення залишку R (x);
Крок 2. Аналіз залишку «на нуль». Нульовий залишок означає, що помилки не виявлені;
2.3.2 Декодування з виправленням помилок
Крок 1. Обчислення залишку R (x);
Крок 2. Обчислення за знайденому залишку передбачуваного (найбільш ймовірного) многочлена помилки Е (х);
Крок 3. Виправлення Декодовані вектора F шляхом підсумовування F + E = V;
3. Параметри досліджуваних кодів
Щоб трудомісткість лабораторних робіт погодити з відпущеним часом, досліджуються короткі (за мірками практики) коди. Параметри кодів наведено у таблицях 1 - 3.
Узгодьте з викладачем номер варіанта, з яким Ви будете працювати. Програми CODER і DECODER слід писати для одного варіанта коду.
Таблиця № 1. Варіанти завдань для (n, k) - кодів з довжиною слова n = 15
| Варі-анти | Параметри n, k | Відстань коду d 0 | Породжує многочлен G (x) | G (x) в двійковому і HEX-форматах |
| 1 | 2 | 3 | 4 | 5 |
| 1.1 | (15,11) | 3 | G 1 (x) = x 4 + x +1 | Січень 0011 «13h |
| 1.2 | (15,7) | 5 | G 2 (x) = x 8 + x 7 + x 6 + x 4 +1 | 1 1101 0001 «1D1h |
| 1.3 | (15,5) | 7 | G 3 (x) = x 10 + x 8 + x 5 + x 4 + x 2 + x +1 | 101 0011 0111 «537h |
| Варі-анти | Параметри n, k | Відстань коду d 0 | Породжує многочлен G (x) | G (x) в двійковому і HEX-форматах |
| 1 | 2 | 3 | 4 | 5 |
| 2.1 | (31,26) | 3 | G 1 (x) = x 5 + x 2 +1 | Жовтень 0101 «25h |
| 2.2 | G 2 (x) = x 5 + x 4 + x 2 + x +1 | Листопад 0111 «37h | ||
| 2.3 | G 3 (x) = x 5 + x 4 + x 3 + x +1 | Листопад 1011 «3Bh | ||
| 2.4 | G 4 (x) = x 5 + x 3 +1 | Жовтень 1001 «29h | ||
| 2.5 | (31,21) | 5 | G 5 (x) = x 10 + x 9 + x 8 + x 6 + x 5 + x 3 +1 | 111 0110 1001 «769h |
| 2.6 | G 6 (x) = x 10 + x 7 + x 5 + x 4 + x 2 + x +1 | 100 1011 0111 «4B7h | ||
| 2.7 | (31,16) | 7 | G 7 (x) = x 15 + x 11 + x 10 + x 9 + x 8 + x 7 + + x 5 + + X 3 + x 2 + x +1 | 1000 1111 1010 1111 «8FAFh |
| 2.8 | G 8 (x) = x 15 + x 14 + x 13 + x 12 + x 11 + + X 10 + x 9 + x 8 + x 7 + x 6 +1 | 1111 1111 1100 0001 «FFC1h |
Таблиця № 3. Варіанти завдань для (n, k) - кодів з довжиною слова n = 63
| Варі-анти | Параметри n, k | Відстань коду d 0 | Породжує многочлен G (x) | G (x) в двійковому і HEX-форматах |
| 1 | 2 | 3 | 4 | 5 |
| 3.1 | (63,57) | 3 | G 1 (x) = x 6 + x +1 | 100 0011 «43h |
| 3.2 | (63,51) | 5 | G 2 (x) = Ååх i, i = 12,10,8,5,4,3,0 | 1 0101 0011 1001 «1539h |
| 3.3 | (63,45) | 7 | G 3 (x) = Ååх i, i = 18,17,16,15,9,7,6,3,2,1,0 | 111 1000 0010 1100 1111 «« 782СFh |
| 3.4 | (63,39) | 9 | G 4 (x) = Ååх i, i = 24,23,22,20,19,17,16,13, 10,9,8,6,5,4,2,1,0 | 1 1101 1011 0010 0111 0111 0111 «« 1DB2777h |
| 3.5 | (63,36) | 11 | G 5 (x) = Ååх i, i = 27,22,21,19,18,17,15, 8,4,1,0 | 1 000 0110 1110 1000 0001 0001 0011 «86Е8113h |
| 3.6 | (63,30) | 13 | G 6 (x) = Ååх i, i = 33,32,30,29,28,27,26,23,22, 20,15,14,13,11,9,8,6,5,1,0 | 11 0111 1100 1101 0000 1110 1011 0110 0011 « «37СD0EB63h |
| 3.7 | (63,24) | 15 | G 7 (x) = Ååх i, i = 39,38,37,36,34,33,31,28,27, 25,22,19,17,11,6,3,0 | 111 1011 0100 1101 0010 0101 0000 0100 0100 1001 «« 7B4D250449h |
4. Порядок виконання лабораторної роботи CODER
Кінцевою завданням є написання та налагодження програми CODER, здатної перетворити пропонований файл. Програма повинна розглядати файл (не обов'язково двійковий) як послідовність двійкових векторів А j довжини k і перетворити його в інший файл - файл, що складається з слів V j довжини n надлишкового коду заданих параметрів.
Легко проглядається проміжна, технологічне завдання: потрібно мати кошти, за допомогою яких можна було б переконати себе і опонентів у тому, що програма CODER виконує перетворення потрібним чином. Назвемо цю програму налагоджувальної.
4.1 Інтерфейс налагоджувальної програми
Необхідно мати (хоча б) два «вікна»:
- Одне для введення вручну кодованого вектора А j заданих параметрів;
- Інше - для показу вихідного вектора V j (або тільки контрольних біт цього вектора).
Необхідно заздалегідь вручну обчислити кілька вихідних векторів V j, відповідних відомим А j. У викладача повинні бути заготовлені свої тестові слова коду. Таким чином можна буде забезпечити певний рівень довіри до кодує програмі [2].
4.2 Інтерфейс основний кодуючої програми CODER [3]
Необхідно передбачити можливість вибору вихідного (кодованого) файлу з каталогів Windows (або писати вручну в будь-якій «командної рядку» шлях до цього файлу). Необхідно передбачити можливість запам'ятовування вихідного файлу програми CODER на диску і можливість багаторазового повернення до аналізу цього файлу.
Вихідний файл (файли) програми CODER знадобляться при виконанні лабораторної роботи, пов'язаної з декодуванням.
4.3 Звіт з лабораторної роботи, захист результатів
Звіт повинен містити:
q короткий виклад постановки завдання;
q необхідні параметри вихідного коду і граф-схему алгоритму роботи основного кодує модуля з коментарями;
q характер і результати тестового кодування:
· (5 ... 6) «пар» вхідних і вихідних векторів кодера;
· Перевірка властивості замкнутості безлічі кодових векторів щодо операції підсумовування по mod2;
· Перевірка відстаней між кодовими векторами на відповідність вихідним вимогам.
Результати роботи програми CODER повинні бути продемонстровані викладачу.
5. Умови і порядок виконання лабораторної роботи DE CODER
Кінцевою завданням у цій роботі є не тільки практичне вивчення алгоритму декодування по синдрому (залишку) та налагодження декодуючої програми, а й вивчення структури (конфігурацій) виявляються і / або виправляє помилок, тобто непряма оцінка завадостійкості коду з конкретними заданими параметрами. Програма - DECODER повинна вміти декодувати пропонований файл.
Вихідними даними, предметом перетворень для програми DECODER повинен з'явитися вихідний файл програми CODER. Але як і в лабораторній роботі CODER, тут також знадобиться певна технологія налагодження основного модуля, за допомогою якої можна переконатися в правильності роботи програми DECODER і проаналізувати специфікації виявляються / виправляє помилок.
5.1 Інтерфейс отладочного модуля
Інтерфейс може бути побудований за принципом двох вікон - «вхідний» і «вихідна». Необхідно мати можливість вручну вводити Декодовані двійкову послідовність (неспотворене слово коду, спотворене слово, вектор помилки) і отримувати в вихідному вікні результат декодування (вид синдрому [4], структуру обчисленої (передбачуваної) помилки або виправлене слово коду, в залежності від конкретного варіанта завдання і Вашого рішення).
5.2 Елементарний план налагодження декодуючого модуля
1) Взяти 3-4 вектора коду V 1, V 2, V 3, V 4 і переконатися, що вони дають нульовий залишок;
2) подіяти на ці вектори помилками.
Маючи на увазі, що спотворення многочлена V j (х) моделюється операцією F j ℓ (х) = V j (х) + E ℓ (х), де многочлен E ℓ (х) символізує ℓ-ту конфігурацію помилок, результат обчислення синдрому ( залишку) R j ℓ (x) = F j ℓ (х) / G (x) можна представити як R ℓ (x) = E ℓ (х) / G (x) [5] Отже, при правильному функціонуванні програми DECODER повинні вийти залишки , що підкоряються такою схемою (табл. 4).
Таблиця 4
| E 1 | R ℓ | E 2 | R m | |
| V i | F i1 (х) = V i (х) + E 1 (х) | R 1 | F i2 (х) = V i (х) + E 2 (х) | R 2 |
| V j | F j 1 (х) = V j (х) + E 1 (х) | R 1 | F j 2 (х) = V j (х) + E 2 (х) | R 2 |
5.3 Варіант DECODER `а з виявленням помилок
Виходячи з характеристик G (x) і величини d 0, запропонувати конфігурації помилок, які програма неодмінно повинна виявляти і які не зобов'язана виявляти. Особливу увагу слід звернути на конфігурації помилок типу «пачка», вага яких знаходиться в межах (nk) ³ w (E)> (d 0 -1).
Знайти конфігурації необнаружіваемие помилок, сформулювати властивості (ознаки) таких помилок;
Результати дослідження звести в таблицю і забезпечити коментарями.
5.4 Варіант DECODER `а з виправленням помилок
Виходячи з характеристик G (x) і величини d 0, запропонувати конфігурації помилок, які ілюструють властивості коду положення щодо виправлення помилок. Підібрати конфігурації, що ведуть до «неправильного виправленню», тобто до вручення одержувачу кодового слова з непоміченими помилками, які залишаються після формально виконаної процедури виправлення.
6. Захист результатів, звіт з лабораторної роботи
Результати роботи програми DECODER повинні бути продемонстровані викладачу. Звіт повинен містити короткий виклад постановки задачі, необхідні параметри вихідного коду, граф-схему алгоритму роботи основного декодуючого модуля з коментарями, обсяг і результати тестового декодування (наприклад, в табличній формі) з докладними коментарями.
7. Швидкий кодер / декодер для циклічних кодів
Застосування швидкого алгоритму в лабораторній роботі не є обов'язковим для всіх. Він може бути використаний за бажанням студентів або за прямою вказівкою викладача.
Вище говорилося, що при циклічному кодуванні основною операцією алгоритмів кодування вхідної послідовності А (х) і декодування вихідний є операція поділу вираження А (х) х (nk) на породжує многочлен з метою знаходження залишку, який підсумовується з А (х) х (nk ) за mod2.
Труднощі програмної реалізації кодують і декодер модулів для циклічних кодів полягає в тому, що алгоритми, зазвичай, передбачають процедуру багаторазово повторюваного «бітового розподілу». Час кодування / декодування часто виявляється неприйнятним. Далі викладається математична суть алгоритму розподілу двійкових послідовностей, що дозволяє виконувати розподіл по частинах. «Крупністю» частин у відомих межах можна варіювати, домагаючись оптимізації процедури в конкретних умовах.
7.1 Алгоритм розподілу по частинах
Розіб'ємо k-бітову послідовність А, виражену многочленом А (х), на ℓ - бітові відрізки (блоки). Так як в загальному випадку k не зобов'язана бути кратним ℓ, вхідна послідовність буде поділена на s блоків, з яких останній має довжину m 0 <ℓ. Виконується умова: k = ℓ (s -1) + m 0.Крок 1
Виділимо в послідовності А ліві ℓ біт. Нехай у символіці многочленів вони виражаються многочленом А 1 (х), а решту (праворуч) частину позначимо А `1 (х).Тоді вхідну послідовність А (х) можна представити у формі:
А (х) = А 1 (х) х (k-ℓ) + А `1 (х). (1)
(Тут і далі підсумовування двійкових многочленів і векторів ведеться за mod2).
Ділене А (х) х (nk) в алгоритмі кодування запишемо як
А (х) х (nk) = (А 1 (х) х (k-ℓ) + А `1 (х)) х (nk) (2)
Векторна ілюстрація до кроку 1.
При ℓ = 4, k = 11 (одинадцять) нехай А = 1101 1000 110. Тут m 0 = 3, А 1 = 1101.
А 1 (х) х (k-ℓ) у векторній формі виглядає як 1101 0000000, так як множення на х (k-ℓ) еквівалентно приписування праворуч (k - ℓ) нулів. А `1 = 1000 110. Сума А 1 (х) х (k-ℓ) + А `1 = А (х) виглядає як
1101 0000000
1000110 Å
1101 1000110
У виразі (2) перший член суми в круглих дужках помножимо і поділимо на породжує многочлен і зробимо множення обох членів на х (nk). Отримаємо:
Дріб
Отримаємо:
А (х) х (nk) = Q 1 (х) G (x) х (k-ℓ) + R 1 (x) х (k-ℓ) + А `1 (х) х (nk) (4)
Старша ступінь многочлена
Старша ступінь залишку R 1 (x) не перевершує величини (nk-1), а всього другого доданка в (4) - величини (n-ℓ -1). Таку ж ступінь має і третій доданок А `1 (х) х (nk). Складемо ці два останні члена, суму позначимо F 1 (х). Перепишемо (4) в наступному вигляді:
А (х) х (nk) = Q 1 (х) G (x) х (k-ℓ) + F 1 (х) (5)
Рис. 1 ілюструє формування послідовності F 1 у векторній інтерпретації всіх що величин. Звернемо увагу на довжину послідовності F 1, на ту обставину, що при підсумовуванні вектори R 1 і A `1« вирівняні »з боку старших розрядів, а F 1 має праворуч (nk) нульових біт.
Рис. 1. Формування послідовності F 1 при векторному поданні величин
На цьому перший крок алгоритму розподілу по частинах закінчений. Отримано F 1 (х), куди увійшов перший проміжний залишок R 1 (x), контролюючий поділ першого блоку з ℓ лівих біт вхідної послідовності А (х).
Крок 2
Черговий крок алгоритму полягає в тому, що в F 1 (х) виділяємо ℓ лівих біт. Цей відрізок повинен бути позначений А 2 (х). Залишилася права частина F 1 (х) - це А `2 (х). Відповідно до (3), (4) знаходимо вираз залишку R 2 (x) і послідовності F 2 (х).
Рис. 2. Формування послідовності F 2 при векторному поданні величин
На рис. 2 проілюстровано отримання F 2. Здійснено спробу масштабно відобразити зміна беруть участь у справі векторів. Тут показано, що після другого кроку F 2 все ще має праворуч (nk) нулів. Це еквівалентно допущенню, що розподіл вхідного вектора А на відрізки довжини ℓ двома кроками не вичерпується.
Ділене (у його стартовому розумінні) після другого кроку має вигляд:
У загальному випадку, поки (ki ℓ) ≥ (nk) вектор F i повинен буде мати справа (nk) нулів. Це, як відомо, місце контрольних біт в словах циклічного кодового слова. Вони поки не сформовані.
Крок s-1
У процесі виконання (s -1) - го кроку ми оперуємо векторами довжини (n - k + m 0) (див. рис. 3). До цього часу всі відрізки довжини ℓ у складі вхідного вектора будуть вичерпані і (якщо в загальному випадку k не ділиться без остачі на ℓ) у нас залишається від вхідної послідовності обчислений залишок R s -1 і «правий» відрізок A `s-1 довжини m 0 <ℓ.
Відповідно до виразами (4) і (5) отримаємо «вихідний продукт» даного кроку - многочлен F s -1 (х) = R s -1 (x) x (k - (s -1) ℓ) + A `s -1 (х) х (n - k) = R s -1 (x) x (m 0) + A `s -1 (х) х (n - k), т. к. k = (s -1) ℓ + m 0 за визначенням цих величин.
Рис. 3. Формування послідовності F s -1 при векторному поданні величин
Позначимо останні формуються (nk) біт Y (х). Як ми бачили до (s-1) - го кроку Y (х) = 0. Отже, Y (х) можна ввести в (6) як нульове доданок, якщо межі підсумовування обмежити величиною (su-1). Після кроку s можна записати
Тут
7.2 Алгоритм кодування
Відомо на старті:
- Довжина вихідних кодових слів n;
- Довжина вхідної послідовності k;
- Число контрольних біт (nk) = r;
- Породжує многочлен G (x);
Призначається величина ℓ ≤ r. Обчислюються параметри s і m 0. У пам'яті машини організується 2 ℓ рядків («місць»). У кожну рядок для кожної конфігурації двійкового відрізка довжини ℓ пишеться залишок, обчислений заздалегідь по викладеному вище алгоритмом. У процесі кодування процедура поділу замінюється зчитуванням з пам'яті залишку для чергового ℓ-відрізка кодируемой послідовності. Це істотно підвищує швидкодію програмного кодера при (зазвичай) прийнятному витраті пам'яті. Бажано так писати програму, щоб ℓ-відрізок міг виступати в ролі «зсуву» по адресного простору списку залишків.
Алгоритм кодування зводиться до наступного.
1. З вихідної k-бітової інформаційної послідовності з боку лівих («старших») розрядів виділяється відрізок довжини ℓ і з таблиці вибирається відповідний йому залишок.
2. Отриманий залишок підсумовується за mod2 з лівими розрядами решти блоку довжиною (k-ℓ) біт.
3. З отриманої суми з боку лівих розрядів виділяється черговий ℓ-відрізок, для якого з таблиці зчитується відповідний залишок і т.д.
4. Через (s-1) таких кроків з отриманої суми виділяються m 0 старших розрядів ℓ-m 0 і для сформованої ℓ - розрядної комбінації вибирається відповідний залишок з таблиці.
5. Отриманий залишок підсумовується за mod 2 з рештою (після виділення m 0 розрядів) бітами. Ця сума є комбінацією перевірочних розрядів циклічного коду.
8. Змістовний приклад [3]
Методом поділу по частинах побудувати кодер для циклічного (15,11) - коду, заданого породжує многочленом G (x) = х 4 + х +1.
Тут n = 15; k = 11. Вибираємо ℓ = 4. Тоді s = 3, m 0 = 3. Всього маємо 2 ℓ різних конфігурацій ℓ-відрізків. Залишки, що відповідають цим відрізкам, обчислені згідно з алгоритмом розподілу по частинах, наведені в табл. 1.
Нехай вхідна (інформаційна) послідовність, розділена на відрізки, має вигляд: 1101 1000 110
Вибираємо перший ℓ-відрізок 1101 та вибираємо з таблиці відповідний залишок 0100. Складаємо по mod 2 з наступним відрізком 0100 +1000 = 1100. Отриманою сумі відповідає залишок 0111. Оскільки зроблено вже (s-1) кроків, додамо цей залишок до решти трьох бітам 0111 +110 = 1011. На цей результат знадобиться посилання, тому привласнимо йому найменування U s-1. З отриманої суми виділимо m 0 лівих біт і доповнимо їх зліва нулями до розмірності ℓ (у даному випадку - одним нулем). Отримаємо 0101. З таблиці знайдемо залишок - 1111. Виконується s-й крок поділу. Частину, що залишилася «1» (праворуч) від U s-1, з якого виділяли m 0 лівих біт, складемо з боку старших розрядів з тільки - но отриманими залишком 1111 +1 = 0111. Це і є контрольні біти до інформаційної послідовності 1101 1000 110.
Результат можна перевірити традиційним розподілом послідовності А (х) х (n - k) на G (x) (у нашому випадку 1101 1000 110 0000 на 10 011).
Табл. 1. Залишки для ℓ-відрізків інформаційної послідовності
| ℓ - відрізок | Залишок | ℓ - відрізок | Залишок |
| 0000 0001 0010 0011 0100 0101 0110 0111 | 0000 0011 0110 0101 1100 1111 1010 1001 | 1000 1001 1010 1011 1100 1101 1110 1111 | 1011 1000 1101 1110 0111 0100 0001 0010 |
Використана література
1. М.М. Аршинов, Л.Є. Садовський Коди й математика (розповіді про кодування) .- М.: Наука, Головна редакція фізико-математичної літератури, 1983. - 144 с.
2. Блейхут Р. Теорія і практика кодів, контролюючих помилки: Пер. з англ. - М.: Світ, 1986. - 576 с.
3. Гончаров Е.А, Слєпаков В.Б. Про один метод кодування інформації циклічними кодами на універсальній ЕОМ. - В кн.: Зб наукових праць ЦНИИС. М., 1970, вип. 3, с. 58-65.
4. В.С. Чернега, В.А. Василенко, В.М. Бондарєв Розрахунок і проектування технічних засобів обміну і передачі інформації: Навчальний посібник для вузів. - М.: Вищ. шк., 1990. -224 С.
[1] Тут і всюди далі операції підсумовування виконуються за mod2.
[2] Взагалі кажучи, такий метод тестування великої довіри не заслуговує не тільки з-за малого числа перевірених векторів, а й з-за кодування вхідних векторів «нарізно», а не шляхом їх «вилучення» з файлу довільного формату. На допоміжних операціях легко привнести помилку в кодування. Однак, через обмеженість часу таким поверхневим тестуванням доведеться задовольнитися.
Можна написати вихідний файл відомої двійковій структури і шукати нескладні прийоми перегляду двійковій структури вихідного файлу, структура якого теж стає наперед відомою.
Можна написати вихідний файл відомої двійковій структури і шукати нескладні прийоми перегляду двійковій структури вихідного файлу, структура якого теж стає наперед відомою.
[3] Інтерфейси основної та допоміжної програм, зрозуміло, можуть бути суміщені.
[4] Але не значення типу «нуль / не нуль» без розкриття структури синдрому.
[5] V (х) по визначенню без остачі ділиться на G (x).