Пороговий декодер

    Друзі, всім привіт!
 
Пару місяців тому, я вже почав розповідати про методи завадостійкого кодування. Перша стаття була присвячена алгоритмом Чейза. Вона ось тут . Багатьох зацікавила дана напрямок, тому я вирішив продовжити. На черзі вельми цікавий, перспективний, і що важливо простий для розуміння пороговий декодер. Давайте почнемо!
 
 Як працює
Пороговий декодер надає надзвичайно просте декодування, засноване на принципі «голосування по більшості».
Кодер являє собою регістр-чергу, заповненими битами вектора, який необхідно закодувати. Обробка починається з нульової комірки. Для біта що знаходиться в нульовій комірки обчислюються необхідні характеристики, а вийшов з черги біт переміщається в кінець черги, в тринадцятий осередок, і може бути використаний для обчислення необхідних даних для біта, що знаходиться в нульовій осередки. Механізм кодування буде працювати до тих пір, поки в нульовий вічка не побувають всі біти, вихідного вектора.
 image
 
Можна сказати, що представлений кодер, заданий за допомогою «утворює полінома» g (x) = 1 + x + x ^ 4 + x ^ 6.
Таким чином, з процесі кодування буде отримано дві частини зашифрованого повідомлення, які в наслідок будуть об'єднані і передані в канал, як єдиний вектор. Перша — інформаційна (u) буде містити біти, вихідного повідомлення, передані на пряму з нульовою осередку регістра, кодованого повідомлення. Друга — перевірочна (v) буде містити біти отримані шляхом додавання біт з осередків регістра з індексами, відповідним ненульовим ступенями «утворює полінома» g (x).
 
 Приклад роботи кодера
Нехай нам потрібно зашифрувати наступне повідомлення: 0111011011011. Інформаційна гілка (u) буде повністю відповідати вихідного повідомлення, тобто буде дорівнює «1101101101110».
Перевірочна гілка (v) буде складатися з біт отриманих за рахунок додавання «по модулю два» біт, з 0-ой, 1-ой, 4-ий і 6-ий осередків регістра.
Приклад:
1. У регістрі: 1 0 1 1 1 0 1 1 0 1 1 0 1
V = 1 ⊕ 0 ⊕ 1 ⊕ 1 = 1;
2. У регістрі: 1 1 0 1 1 1 0 1 1 0 1 1 0
V = 1 ⊕ 1 ⊕ 1 ⊕ 0 = 1;

13. У регістрі: 0 1 1 1 0 0 1 0 1 1 0 1 1
V = 0 ⊕ 1 ⊕ 0 ⊕ 1 = 0;
Після «кола» роботи кодера, перевірочна частина буде являти собою вектор: «111000000010».
Отже, в канал буде відправлений вектор «+10111011011011110000000010».
 
Варто відзначити що формат вектора [u | v] не є єдино вірним. І може бути з легкістю замінений на будь-який інший формат, наприклад: [u1 | v1 | u2 | v2… un | vn].
 
 Робота декодера
Розглянемо роботу порогового декодера. На першому кроці роботи декодера, за допомогою вхідного в його склад кодера, обчислюються перевірочні біти, для прийнятих з каналу інформаційних бітів гілки u, складається «за модулем два» з прийнятими перевірочними бітами з гілки v. У результаті в синдромного регістрі сформується синдром, який вказує на наявність помилок.
 image
Після заповнення синдромного регістра здійснюється декодування інформаційного символу з 0-ой осередку, для чого в пороговому елементі (ПЕ) здійснюється порівняння суми елементів синдромного регістра, відповідних декодіруемий символу. У разі, якщо сума виявиться більше порога, вихід ПЕ встановлюється рівним 1, що призводить до зміни інформаційного символу і пов'язаних з ним перевірок. В іншому випадку ПЕ буде 0.
Розглянутий декодер є декодером зі зворотним зв'язком, так як виправлення в інформаційному регістрі помилка за рахунок зворотного зв'язку віддаляється і з синдромного регістру.
Нехай у вихідне повідомлення «+10111011011011110000000010» буде внесена помилка «10111 1 1101101 1110000000010».
Синдромний регістр буде містити наступні значення: «00000011001010» (найперший біт — осередок «0» синдромного регістра на картинці)
1. В синдромного регістрі: «0000011001010» → «0000011001010»
У порозі: 1, 1 < 2 → змін немає. У результат йде значення «1»;
2. В синдромного регістрі: «0000110010100» → «0000110010100»
У порозі 1, 1 <2 → змін немає. У результат йде значення «1»;

6 У синдромного регістрі: «1100101000000» → «0000000000000».
У порозі 4, 4> 2 → зміна є. У результат йде значення «0», вносяться зміни до синдром;
В результаті після декодування ми отримаємо повідомлення «1 1 0 1 1 0 1 1 0 1 1 1 0». Помилка була виправлена. І після інверсії позицій всіх біт ми отримаємо вихідне повідомлення «0 1 1 1 0 1 1 0 1 1 0 1 1».
 
 Епілог
Пороговий декодер є вдалим поєднанням простоти реалізації, ефективності і швидкості роботи. Його розвитком є ​​многопороговий декодер. Розповісти про якому спробую найближчим часом.
Спасибі, всім хто прочитав. Буду радий конструктивних зауважень / коментарів. Намагався бути дохідливим :)
    
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.