5.2. Види коректуючих кодів
Розглянемо загальну класифікацію коректуючих кодів. В цілому, за типом побудови розрізняють два основні види завадостійких кодів: алгебраїчні завадостійкі коди та коди Вагнера. Всі коди, завадостійкість яких обумовлена структурою побудови кодових комбінацій, називають алгебраїчними. Коректуюча ж здатність кодів Вагнера визначається оцінкою ймовірності спотворення кожного символу в кодовій комбінації. Надалі ми будемо розглядати лише алгебраїчні коректуючі коди. І саме їх класифікацію розглянемо нижче.
Як зазначено вище, всі коректуючі коди поділяють на дві великі групи: виявляючі коди і випрямляючі коди. Виявляючі коди можуть забезпечити лише виявлення певних видів помилок. Для їх же виправлення в цьому випадку слід в електронну систему вводити канал зворотного зв’язку. Тоді приймач, виявивши помилку в отриманому повідомленні, посилає по каналу зворотного зв’язку запит на повторення повідомлення з помилкою.
Виправляючий код дозволяє самому приймачу не лише виявити помилку, а й визначити, які кодові символи є помилковими і виправити їх без повторної передачі спотвореного повідомлення.
Практичного поширення набули лише двійкові коректуючі коди. При цьому існує багато різновидів таких кодів. Розглянемо їх класифікацію, наведену на рис.5.2.
За способом внесення цієї надлишковості коди поділяють на блочні і неперервні.
При блочному кодуванні кожному дискретному елементу повідомлення відповідає кодова комбінація з певною кількістю символів. Операції кодування та декодування в таких кодах виконують окремо в кожній кодовій комбінації.
У неперервних кодах поділу на блоки немає і при їх утворенні в послідовність інформаційних символів звичайного коду включаються надлишкові контрольні символи, розміщення яких погоджується лише з видом помилок і не залежить від положення меж відповідних слів простого коду.
|
Рис.5.2. Класифікація двійкових алгебраїчних кодів
|
Ділимі коди – це коди, в яких можна провести виділення інформаційних кодових символів, що несуть передану інформацію, і контрольних кодових символів, які є надлишковими, інформації в собі не несуть і служать лише для коректування помилок, що виникають. У неділимих кодах такий поділ провести неможливо.
Систематичні коди (лінійні коди, групові коди) – це коди, в яких кожна кодова комбінація належить до своєї групи і має певні властивості. В протилежному випадку код буде несистематичним.
Систематичні коректуючі коди характерні тим, що будь-яка лінійна комбінація дозволених кодових комбінацій такого коду є також дозволеною кодовою комбінацією. Віддаль між кодовими словами в цих кодах визначається за Хеммінгом. Суттєвою характеристикою лінійного коду є так звана вага Хеммінга. Для кодового слова вага Хеммінга визначається як число ненульових компонент цього слова. Наприклад, для кодової комбінації А = (00100100) вага z = 2.
5.3. Виявляючі коди з постійною вагою
Як вказувалося раніше, вагою кодової комбінації називають кількість одиниць, яку вона містить. Якщо всі кодові комбінації коду мають однакову вагу, то такий код називають кодом із постійною вагою. В таких кодах не проводять розділення символів на інформаційні та контрольні. Різні види таких кодів позначають як a/b код з постійною вагою, де a – кількість двійкових одиниць в кожній кодовій комбінації, а b – кількість двійкових нулів.
Найбільш поширеним кодом цього виду є код 3/4, в кожній кодовій комбінації якого є три одиниці і чотири нулі; наприклад 1011000, 0101010, 0001110,… . Декодування таких кодів практично зводиться лише до визначення ваги кожної кодової комбінації. Якщо вона рівна a, то кодову комбінацію прийнято правильно. У протилежному випадку в ній є помилки. Такий код виявляє всі помилки непарної кратності, а також і багато помилок парної кратності, за винятком тих, які не змінюють вагу кодової комбінації.
5.4. Інверсійний код
Одним із простих блочних систематичних кодів, який дозволяє лише виявити помилки, є інверсійний код. Особливістю коду є умова, що число контрольних символів r рівне числу інформаційних символів, тобто r = k. У цьому коді використовуються такі правила утворення контрольних символів із інформаційних:
Рахують суму по модулю два всіх інформаційних символів.
Якщо ця сума рівна нулю, то контрольні символи беруть просто як повторення інформаційних символів.
Якщо ж ця сума рівна одиниці, то контрольні символи отримують шляхом інвертування відповідних інформаційних символів.
Контрольні символи добавляють в кінці інформаційних символів в порядку їх слідування, отримуючи на виході кодера виявляючий код із довжиною кодових комбінацій 2k.
Отримавши утворений вищеописаним способом код, декодер проводить порівняння інформаційних і контрольних символів. Для цього він виконує наступні операції:
1. Обчислює суму по модулю 2 всіх отриманих інформаційних символів.
Утворює свої контрольні символи за тим же правилом, що його використовував передавач.
Обчислює суму по модулю два отриманих і порахованих контрольних символів.
Якщо в результаті виконання таких операцій отримана сума контрольних символів рівна нулю, то приймач вважає прийняту комбінацію правильною. У протилежному випадку приймач вважає, що дану кодову комбінацію отримано з помилкою.
Аналіз показує, що інверсійний код виявляє всі помилки з кратністю g 3, якщо k 5. Цей код має високу виявну здатність, але і плата за це досить висока, оскільки надлишковість інверсійного коду складає  = (n – k)/n = (2k – k)/2k = 1/2.
5.5. Код з парним числом одиниць
Багато пристроїв сучасних інформаційних систем використовують перевірку отримуваної інформації на “парність”. Така перевірка проводиться з використанням простих виявляючих кодів з парним числом одиниць. Особливістю такого коду є те, що незалежно від числа інформаційних символів до них додається лише один контрольний символ. Тобто такий коректуючий код практично не впливає на швидкість передачі інформації.
У коді з парним числом одиниць передавач проводить наступні операції по утворенню контрольного символу з інформаційних:
Рахує суму по модулю два всіх інформаційних символів.
Якщо ця сума рівна нулю, то в кінці кодової комбінації додається контрольний символ, рівний нулю.
Якщо ж ця сума рівна одиниці, то в кінці кодової комбінації додається контрольний символ, рівний одиниці.
Таким чином, передавач формує кожну вихідну кодову комбінацію з парним числом двійкових одиниць у ній. Звідси і походить назва коду.
Отримавши утворений вищеописаним способом код, декодер у свою чергу виконує наступні дії:
Обчислює суму по модулю 2 отриманих інформаційних символів.
Утворює свій контрольний символ за тим же правилом, що його використовував передавач.
Обчислює суму по модулю для отриманого і обчисленого контрольних символів.
Якщо в результаті виконання таких операцій отримана сума контрольних символів рівна нулю, то приймач вважає прийняту комбінацію правильною. У протилежному випадку приймач вважає, що дана кодова комбінація отримана з помилкою.
Код з парним числом одиниць має непогану виявну здатність при досить малій (~10 %) надлишковості.
ЗАВДАННЯ РОБОТИ
1. Записати повідомлення у виді речення довжиною 20–30 символів. Розробити звичайний код Боде для кодування цього повідомлення.
2. Перетворити звичайний код у виявляючий інверсійний код.
3. Внести 10 однократних помилок, 2 двократні помилки і одну трикратну помилку в закодоване повідомлення і записати «отриманий передавачем» коректуючий код з помилками.
4. Провести виявлення помилок в отриманому повідомленні та відзначити кодові комбінації з помилками.
5. Проаналізувати, які помилки дозволяє виявляти інверсійний коректуючий код. Визначити параметри використаного виявляючого інверсійного коду: основу коду q, довжину кодових комбінацій n, число інформаційних символів у кодовій комбінації k, число контрольних символів у кодовій комбінації r, кодову відстань d, надлишковість коду , імовірність появи однократної помилки.
6. Виконати завдання 2–5 для коду з парним числом одиниць.
7. Результати роботи оформити у виді таблиці 5.2.
Таблиця 5.2.
Зразок оформлення результатів практичної роботи №5
№
|
Символи повідом-лення
|
Звичайний код Боде
|
Коректуючий код, який передається
|
Код, отриманий приймачем
|
Наявність помилки
|
|
|
|
|
|
|
ПРАКТИЧНА РОБОТА №6
Тема роботи: ВИВЧЕННЯ ВЛАСТИВОСТЕЙ СИСТЕМАТИЧНИХ БЛОЧНИХ ВИПРАВЛЯЮЧИХ КОДІВ
ТЕОРЕТИЧНІ ВІДОМОСТІ
6.1. Загальні властивості систематичних ділимих блочних кодів
Позначимо через с – інформаційні символи кодових комбінацій, а через е – контрольні символи кодових комбінацій. Нехай k – число інформаційних символів, а r = n – k – число контрольних символів у кодових комбінаціях, тоді будь-яку кодову комбінацію систематичного ділимого блочного коду можна записати у виді послідовності: с1с2…сkе1е2…еr. Перші k символів послідовності несуть повідомлення, а решта n – k символів є надлишковими, інформації не несуть і служать лише для виявлення і виправлення помилок.
У процесі кодування з використанням систематичних блочних кодів кодер використовує інформаційні символи кодової комбінації і на їх основі формує контрольні символи у вигляді лінійної комбінації інформаційних символів з використанням операції сумування по модулю 2, яку ми позначатимемо також значком нарівні із значком . Тоді  , де і = 1, 2, …, r; j = 1, 2, …, k; іj = 0 або 1. При цьому коефіцієнти іj вибираються за певним правилом, яке і задає вигляд коректуючого коду.
У декодері мають бути відомі всі коефіцієнти ij і правила їх вибору, що використовувалися при кодуванні повідомлень. Припустимо, що приймач прийняв і передав у декодер кодову комбінацію  , в якій можливі помилки. Декодер із отриманих інформаційних символів будує групу контрольних символів  за тими ж самими правилами, що і кодер, тобто 
Після цього проводиться сумування по модулю два двох груп контрольних символів:  = Х.
Отримана сума називається контрольним числом або синдромом. Саме синдром і дозволяє виявити або виправити помилки. Зокрема, якщо всі хі у синдромі рівні нулю, то помилок в отриманій кодовій комбінації нема. Якщо ж хоча б одне хі = 1, то це означає, що кодова комбінація має помилки, які потрібно виявляти і виправляти. Синдром вказує на наявність (Х 0) чи відсутність (Х = 0) помилок в отриманому кодовому слові, а також несе вказівки про те, як наявні помилки виправити в межах заданого коректуючого коду.
Для виправлення помилки необхідно знати номер у кодовій комбінації помилково прийнятого символу. Для цього кожному поєднанню помилок в кодовій комбінації присвоюється своє значення синдрому. Тоді, обчисливши синдром, декодер автоматично знає, які помилки треба виправляти в отриманій кодовій комбінації. При цьому правила вибору коефіцієнтів ij і дають можливість присвоювати кожній помилці своє значення синдрому.
Кількість відмінних від нуля значень синдрому рівна 2r – 1. Очевидно, що число різних видів поєднання помилок має бути не більше цієї кількості. Наприклад, для одиночних помилок число варіантів рівне k + r = n. Тоді умова виявлення і виправлення одиночних помилок декодером задається умовою 2r – 1 k + r.
Одночасно ця умова дає можливість визначати і число контрольних символів, які необхідні для виправлення одиночних помилок 2r – r k + 1.
6.2. Систематичні блочні виправляючі коди Хеммінга
Коди Xеммінга є систематичними кодами з віддаллю d = 3, які дозволяють виявляти і виправляти всі одиночні помилки, тобто всі помилки, які включають зміну лише одного кодового символу кодової комбінації.
Як і в попередніх блочних кодах розмістимо k інформаційних символів на перших місцях кодової комбінації, а r контрольних – на останніх місцях. Правила утворення контрольних символів відповідають загальній формулі  для систематичних блочних кодів, де коефіцієнти ij задаються відповідною таблицею – матрицею (таблиця 6.1). Така таблиця має складатися з r рядків, кожен із яких ділиться по k стовпчиків. Кожній позиції символів у кодовій комбінації ставиться у відповідність свій синдром, який відповідає появі помилки саме в символі, розміщеному в даній позиції. Відповідність позицій помилкового символу і значення синдрому задається у вигляді таблиці відповідності (таблиця 6.2).
Декодер містить у собі таблицю – матрицю коефіцієнтів ij та таблицю відповідності значень синдрому і помилкових позицій кодових комбінацій. Отримавши від передавача повідомлення у вигляді кодової комбінації, декодер розраховує свої контрольні символи. Після цього розраховується синдром кодової комбінації.
Таблиця 6.1
Матриця розрахунку контрольних символів
Контрольний символ
|
Коефіцієнти розрахунку контрольних символів
|
е1
|
11 = 0
|
12 = 1
|
13 = 1
|
14 = 1
|
е2
|
21 = 1
|
22 = 0
|
23 = 1
|
24 = 1
|
е3
|
31 = 1
|
32 = 1
|
33 = 0
|
34 = 1
|
Таблиця 6.2
Відповідність помилкових символів значенням синдрому
Помилковий символ
|
с1
|
с2
|
с3
|
с4
|
е1
|
е2
|
е3
|
Контрольне число
|
011
|
101
|
110
|
111
|
100
|
010
|
001
|
На закінчення зазначимо, що дані таблиць пов’язані між собою. Зокрема, значення контрольних чисел і помилок в інформаційних символах відповідають стовпцям таблиці коефіцієнтів ij. Це дає можливість із синдромів Х встановити таблицю коефіцієнтів ij або навпаки, з таблиці коефіцієнтів ij встановити відповідні значення синдромів.
6.3. Принципи побудови кодерiв в електронних системах
Кодери найчастіше всього проводять перетворення простого (звичайного) коду в коректуючий. При необхідності кодери одночасно можуть змінювати й основу коду. Після формування коректуючого коду для його передачі по каналах зв'язку проводиться відповідна модуляція певного носія, в результаті чого отримують цифровий сигнал. Сам носій вибирають таким чином, щоб мінімізувати об’єм сигналу й одночасно зробити максимально можливим розпізнання символів коду в прийнятому сигналі.
Сучасна теорія побудови кодерів грунтується на математичній теорії лінійних векторних просторів i алгебрі многочленiв. У цих теоріях кодова комбінація з довжиною n розглядається як вектор в n-мірному просторі, побудований на певному наборі базисних векторів.
Схеми завадостійкого кодування i декодування поділяють на активні i пасивні. У схемах активного типу використовуються генератори сигналів, які відтворюють базові вектори або вектори перевірочної матриці. У вихідних колах генератора формуються базисні вектори. Сформовані базисні вектори подаються на помножувачi по модулю 2. На iншi входи цих схем подаються символи кодового слова. Результати множення векторно сумуються в суматорі. Тривалість генерованих символів, початок i кінець формування символів i кодових комбінацій визначаються сигналами синхронізатора. Доцільність використання кодерiв активного типу визначається можливістю застосування складних за електронною схемою генераторів базисних векторів.
Схеми пасивного типу будуються лише на активних елементах без використання генераторів базисних векторів.
6.4. Принципи побудови декодерiв в електронних системах
На приймальній стороні каналу зв’язку отримані цифрові сигнали підсилюються, проходять певну обробку з розпізнанням елементарних складових сигналу, виявляються і при можливості виправляються помилки. Після цього сигнал направляється в декодер для декодування. Пристрої завадостійкого декодування (декодери) проводять перетворення коректуючого коду в звичайний, в якому в межах коректуючої здатності коду частину помилок уже виправлено. Ті кодові комбінації, де помилки лише виявлені кодером, але не можуть бути ним виправлені, позначаються спеціальними символами або зовсім стираються.
Структура декодерiв визначається перш за все методом декодування. В даний час найбільше використовують синдромне декодування. Декодер з синдромним декодуванням складається з формувача синдрому, дешифратора синдрому i схеми виявлення та виправлення помилок. Дешифратор встановлює зв'язок між синдромом Х i вектором помилок.
Для формування синдрому раніше використовували переважно схеми активного типу. На сьогодні частіше використовують схеми пасивного типу, побудовані на звичайних суматорах по модулю 2. В такому випадку для формування синдрому потрібно використовувати пристрій запам'ятовування символів кодових комбінацій (як правило, його роль виконує окремий регістр) i r = n – k схем сумування з кількома входами.
При ускладненні кодів складність кодуючих i декодуючих пристроїв сильно зростає, i на даний час ці операцiї переважно виконуються процесорними пристроями або з використанням спеціальних сучасних комп’ютерів. Широко розробляються i нові методи кодування та декодування, спеціально призначені для реалiзацiї з допомогою комп’ютерів. Такі методи будуть детально розглядатися у рамках спецкурсів у наступному році навчання.
ЗАВДАННЯ РОБОТИ
1. Записати повідомлення у виді речення довжиною 20–30 символів звичайним кодом Боде.
2. Перетворити звичайний код у виправляючий код Хеммінга. Контрольні символи розраховувати, враховуючи коефіцієнти ij із таблиці 6.1.
3. Внести 10 однократних помилок, 2 двократні помилки і одну трикратну помилку в закодоване повідомлення і записати «отриманий передавачем» коректуючий код з помилками. При введенні помилок змінювати можна як інформаційні, так і контрольні символи.
4. Розрахувати нові контрольні символи для «отриманого» повідомлення з помилками і записати отримані нові кодові комбінації.
5. Розрахувати і записати синдром для кожної кодової комбінації.
6. Провести виявлення помилок в отриманому повідомленні по синдрому та відзначити кодові комбінації з помилками. При цьому відмінний від нуля синдром достовірно вказує на наявність помилки в даній кодовій комбінації.
7. Проаналізувати, які помилки дозволяє виявляти код Хеммінга.
8. Провести виправлення всіх помилок, які дозволяє виконати код Хеммінга, використовуючи дані таблиці 6.2. Проаналізувати типи помилок, які може виправити цей код.
8. Результати роботи оформити у виді таблиці 6.3.
9. Визначити параметри використаного коду Хеммінга: основу коду q, довжину кодових комбінацій k, число інформаційних символів у кодовій комбінації n, число контрольних символів у кодовій комбінації r, кодову відстань d, надлишковість коду .
10. Записати умови виявлення і виправлення помилок даним кодом і перевірити реальність їх виконання.
18. Порівняти властивості виправляючого коду Хеммінга та виявляючих кодів.
Таблиця 6.3
Зразок оформлення результатів практичної роботи №6.
№
|
Сим-воли повідо-млення
|
Код Боде
|
Коректу-ючий код, який пе-редається
|
Код, отриманий приймачем
|
Код з пере-рахованими декодером символами
|
Синд-ром
|
Наяв-ність помилки
|
Виправ-лений код
|
ПРАКТИЧНА РОБОТА №7
Тема роботи: ВИВЧЕННЯ ВЛАСТИВОСТЕЙ НЕПЕРЕРВНИХ ВИПРАВЛЯЮЧИХ КОДІВ ФІНКА-ХАГЕЛЬБАРГЕРА
ТЕОРЕТИЧНІ ВІДОМОСТІ
У неперервних кодах контрольні символи утворюються шляхом певних дій над двома або кількома інформаційними символами. Одним із таких кодів є неперервний ланцюговий код Фінка-Хагельбаргера. В ньому контрольні символи утворюються шляхом сумування по модулю два двох інформаційних символів, які розміщені в коді на певній віддалі один від одного:  ;  .
Віддаль між інформаційними символами, які використовуються для утворення одного контрольного символу, l = k – i називається кроком додавання. Крок додавання й визначає основні властивості ланцюгового неперервного коду. Надлишковість такого коду = 0,5. Розраховані в процесі кодування контрольні символи розміщуються між інформаційними символами з затримкою на один крок додавання після другого інформаційного символу розглядуваної пари. В результаті схема утворення неперервного коду Фінка-Хагельбаргера буде мати вигляд:
|
k = i+e
m = k + l = I + 2e
|
При декодуванні з прийнятих інформаційних символів за тим же правилом формують допоміжні контрольні символи  і порівнюють їх із відповідними контрольними символами, які прийшли до приймача в повідомленні  . Схема цього процесу матиме такий вигляд:
Якщо в інформаційному символі  буде помилка, то це виявиться в реалізації двох нерівностей одночасно:  і  , оскільки інформаційний символ ck бере участь в утворенні обох цих контрольних символів. Якщо ж виконуються рівності  і  , то символ ck і обидва контрольні символи передалися правильно. Відповідно, при умовах і (або навпаки  і ) помилка могла трапитися в передачі відповідного контрольного символу.
Важливою перевагою такого неперервного коду є здатність виправляти не тільки одиночні помилки, а і групи помилок або пакети помилок довжиною до 2l.
ЗАВДАННЯ РОБОТИ
1. Записати повідомлення у вигляді речення довжиною до 30 символів звичайним кодом Боде з n = 4. Символи коду записувати у вигляді неперервної послідовності.
2. Закодувати вибране повідомлення коректуючим кодом Фінка-Хагельбаргера. Як контрольні символи використовувати суму по модулю два двох інформаційних символів. Крок сумування вибрати у межах від 6 до 9. Для зручності роботи виділяти контрольні символи в неперервному ланцюжку коду.
3. Внести 5 однократних помилок, 2 пакети помилок у двох послідовних символах і один пакет помилок у трьох послідовних символах у закодоване повідомлення і записати «отриманий передавачем» коректуючий код з помилками. При введенні помилок змінювати можна як інформаційні, так і контрольні символи.
4. Розрахувати нові контрольні символи для «отриманого» повідомлення з помилками і записати нове повідомлення під «отриманим» повідомленням. Для зручності виділити контрольні символи в обох повідомленнях.
5. Попарно порівнюючи контрольні символи «отриманого» і нового перерахованого повідомлень, проаналізувати умови виправлення помилок таким кодом та виправити помилки, внесені в повідомлення каналом зв’язку.
6. Визначити основні параметри коду Фінка-Хагельбаргера та проаналізувати його виправляючі властивості.
ПРАКТИЧНА РОБОТА №8
Тема роботи: ЕЛЕМЕНТИ ТЕОРІЇ ІНФОРМАЦІЇ В ЕЛЕКТРОННИХ СИСТЕМАХ
ТЕОРЕТИЧНІ ВІДОМОСТІ
|
