Особливості практичного застосування способів кодування Способи декодування з виявленням помилок

Білоруський державний університет інформатики і радіоелектроніки
кафедра РЕЗ
реферат на тему:
«Особливості практичного застосування способів кодування. Способи декодування з виявленням помилок »
МІНСЬК, 2009

Завдання кодування полягає у формуванні з інформаційних словами a (x) кодових слів (x) циклічного (n, k)-коду, який за своєю структурою може бути несистематичним і систематичним.
Формування кодових слів несистематичного коду полягає в множенні многочлена a (x), що відображає інформаційну послідовність довжини k, на який породжує многочлен, тобто (X) = a (x) (g (x). Формування кодових слів систематичного коду полягає в перетворенні інформаційної послідовності a (x) відповідно з виразом (x) = a (x)  x ^r + r (x).
Перевірочна послідовність r (x) визначається двома способами:
при використанні "класичного" способу кодування ;
при використанні способу кодування, рекомендованого МККТТ ,
де x (1) ^r-1 - одиничний многочлен ступеня (r-1).
Зазначені вище математичні операції виконують кодери несистематичного і систематичного кодів.
Способи декодування з виявленням помилок
Процедура декодування циклічного коду з виявленням помилок, за аналогією з процесом кодування, використовує два способи:
- При кодуванні "класичним" способом декодування засноване на використанні властивості подільності без залишку кодового многочлена (x) циклічного (n, k)-коду на породжує многочлен g (x). Тому алгоритм декодування включає в себе розподіл прийнятого кодового слова, описуваного многочленом на g (x), обчислення і аналіз залишку r (x). Якщо r (x) = 0, то прийняте кодове слово вважається неспотвореним. Якщо r (x)  0, то прийняте кодове слово стирається і формується сигнал "помилка".
- При кодуванні способом МККТТ декодування засноване на властивості отримання певного контрольного залишку R ₀ (x) при розподілі прийнятого кодового многочлена (x) на породжує многочлен. Тому, якщо отриманий при діленні залишок , То прийняте кодове слово вважається неспотвореним. Якщо залишок , То прийняте кодове слово стирається і формується сигнал "помилка". Значення контрольного залишку визначається з виразу .
Способи декодування з виправленням помилок та схемна реалізація декодер
Декодування циклічного коду в режимі виправлення помилок можна здійснювати різними способами. Нижче викладаються два способи, які є найбільш простими.
В основу першого способу покладено використання таблиці синдромів (декодування), в якій кожному многочлену або зразку помилок e _i (x), відповідає певний синдром S _i (x), що представляє залишок від ділення прийнятого кодового слова і відповідного йому e _i (x) на g (x). Процедура декодування наступна. Прийняте кодове слово ділиться на g (x), визначається S _i (x) і відповідний йому многочлен e _i (x), а потім підсумовується з e _i (x). У результаті отримуємо виправлене кодове слово, тобто .
До складу декодера входять: обчислювач синдрому (ЗС), два регістри зсуву RG1 і RG2, постійний запам'ятовуючий пристрій (ПЗУ), яке містить слова довжини n, відповідні многочленів помилок e _i (x).
Прийняте кодове слово надходить на вхід обчислювача синдрому, де здійснюється розподіл його на g (x) та формування S _i (x), і одночасно - на вхід RG2, де накопичується. Синдром S _i (x) використовується в якості адреси, по якому з ПЗУ в регістр RG1 записується e _i (x), відповідний синдрому S _i (x). Перераховані операції завершуються за n тактів. Протягом наступних n тактів відбувається поелементне підсумовування вмісту RG2 і RG1, тобто операція , І виправлення. помилок.
В основі другого способу виправлення помилок, що дозволяє значно скоротити обсяг використовуваних табличних синдромів і істотно спростити схему декодера, лежать наступні положення:
1. Синдром S _i (x), відповідний прийнятому кодовому слову дорівнює залишку від ділення на g (x), а також залишку від ділення відповідного многочлена помилок ei (x) на g (x), тобто .
2. Якщо S _i (x) відповідає і e _i (x), то x (S _i (x) є синдромом, який відповідає і або .
3. При виправленні помилок використовуються синдроми зразків помилок лише із ненульовим коефіцієнтом у старшому розряді.
Тому при реалізації цього способу безліч всіх зразків помилок розбивається на класи еквівалентності. Кожен клас представляє циклічний зсув одного зразка помилок, а синдром цього класу відповідає зразку помилок з ненульовим старшим розрядом. Якщо обчислений синдром належить одному з класів еквівалентності зразків виправляє помилок, то старший символ кодового слова виправляється. Потім прийняте слово і синдром циклічно зсувається, а процес знаходження в попередній за старшинством позиції повторюється.
Для виправлення помилок, що належать даному класу еквівалентності, потрібно провести n циклічних зрушень.
Найпростішим є декодер Меггітта. До складу декодера входять: обчислювач синдрому, який здійснює розподіл кодового слова на g (x) та формування відповідного синдрому; блок декодерів (ДК), який налаштований на синдроми всіх зразків виправляє помилок з ненульовими старшими розрядами; регістр зсуву RG.
При надходженні на вхід схеми кодового слова його символи заповнюють регістр RG, а в обчислювачі формується відповідний синдром S _i (x). Обчислений синдром порівнюється з усіма табличними синдромами, закладеними в схему блоку ДК, і в разі збігу з одним із них на його виході формується сигнал, який виправляє помилковий символ, що знаходиться в старшому розряді регістру. Після цього вміст обчислювача і RG циклічно зсувається на один крок. Цей зсув реалізує операції і . Якщо новий синдром збігається з одним із табличних синдромів, то це означає, що сталася помилка в другому за старшинством символі кодового слова, який, перейшовши в старший розряд RG, виправляється. Потім проводиться новий циклічний зсув на одну позицію і нова перевірка на збіг синдромів. Після повторення цього процесу n раз на RG буде сформовано виправлене кодове слово. Введення зворотного зв'язку для RG не обов'язково, тому що в процесі виправлення помилок символи кодового слова надходять на вихід декодера.
Приклад. Розглянемо схему і роботу декодера Меггітта циклічного (15,7)-коду, забезпечує виправлення одиночних і подвійних помилок, з g (x) = x ⁸ + x ⁷ + x ⁶ + x ⁴ +1 (див. малюнок 1).












Блок декодерів налаштовується на 15 синдромів, які представлені в таблиці 1 і відповідають класам еквівалентності із зразками помилок в старшому розряді.

Таблиця 1
№
е (х)	S (x)	№	е (х)	S (x)
1	x 14	x 7 + x 6 + x 5 + x 3	9	x 14 + x 6
2	x 14 + x 13	x 7 + x 4 + x 3 + x 2	10	x 14 + x 5	x 7 + x 6 + x 3
3	x 14 + x 12	x 7 + x 6 + x 4 + x	11	x 14 + x 4	x 7 + x 6 + x 5 + x 4 + x 3
4	x 14 + x 11		12	x 14 + x 3	x 7 + x 6 + x 5
5	x 14 + x 10		13	x 14 + x 2	x 7 + x 6 + x 5 + x 3 + x 2
6	x 14 + x 9		14	x 14 + x 1	x 7 + x 6 + x 5 + x 3 + x
7	x 14 + x 8		15	x 14 + x 0	x 7 + x 6 + x 5 + x 3 +0
8	x 14 + x 7

Припустимо, що помилки в 3 та 5 розрядах, тобто їм відповідає многочлен помилки e (x) = x ¹² + x ^10.
При надходженні на вхід декодера спотвореного кодового слова він заповнює регістр і в обчислювачі формується синдром .
Блок декодерів не реагує на цей синдром.
Потім відбувається зрушення кодового слова в RG, а у BC формується новий синдром .
Блок декодерів і в цьому випадку не спрацьовує.
При наступному зсуві кодового слова в RG перший спотворений розряд займає старшу позицію в RG, а у BC формується синдром , Від якого спрацьовує БДК. У результаті виправляється перша помилка.
Наступним зсув призводить до формування синдрому .
Цей синдром відповідає многочлену помилки e (x) = x ¹³ + x ^0, тому перший спотворений розряд з зворотного зв'язку повинен зайняти молодшу позицію RG.
На синдром S _(13,0) блок декодерів не реагує.
При наступному зсуві кодового слова в RG другий спотворений розряд займає старшу позицію в RG, а у BC формується синдром , Від якого спрацьовує БДК. У результаті виправляється друга помилка в кодовому слові.
Коди Ріда-Соломона (РС)
Коди РС є Недвійкова циклічними кодами, символи кодових слів яких беруться з кінцевого поля GF (q). Тут q ступінь деякого простого числа, наприклад q = 2 ^m.
Припустимо, що РС-код побудований над GF (8), яке є розширенням поля GF (2) по модулю примітивного многочлена f (z) = z ³ + z +1. У цьому випадку символи кодових слів коду будуть мати значення, подані в таблиці 2.

Таблиця 2
000	0	0	011	z +1	 3
001	1	 0	110	z 2 + z	 4
010	z	 1	111	z 2 + z +1	 5
100	z 2	 2	101	z 2 +1	 6

Кодові слова РС-коду відображаються у вигляді многочленів
,
де N - довжина коду; V _i - q-ічние коефіцієнти (символи кодових слів), які можуть приймати будь-яке значення з GF (q).
Ці коефіцієнти як це випливає з таблиці, також відображаються многочленами з двійковими коефіцієнтами . Коди РС є максимальними, тому що при довжині коду N та інформаційної послідовності k вони володіють найбільшим кодовою відстанню d = N-k +1.
Породжує многочленом g (x) РС-коду є дільник двочлена x ^N +1 ступеня меншою N з коефіцієнтами з GF (q) за умови, що елементи цього поля є корінням g (x). Тут - Примітивний елемент GF (q).
На основі цього визначення, а також теореми Безу, вираз для породжує многочлена РС-коду буде мати вигляд .
Ступінь g (x) дорівнює d-1 = Nk = R.
У РС-кодах приналежність кодових слів даному коду визначається виконанням d-1 рівнянь відповідно до вираження (*), Де V _i - символи-коефіцієнти з GF (q); z _0, z ₁ ... z _N-1 - ненульові елементи GF (q).
Елементи z _0, z ₁ ... z _N-1 називаються локаторами, тобто вказують на номер позиції символу кодового слова.
Наприклад, покажчиком i - позиції є локатор zi або елемент  ⁱ GF (q).
Так як всі локатори повинні бути різні і причому ненульовими, то їх число в GF (q) дорівнює q-1. Отже, така кількість символів має бути в кодових словах кода.Поетому зазвичай довжина РС-коду визначається з виразу N = q-1.
Приклад. Припустимо, що довжина РС-коду дорівнює N, кодова відстань d = 3, то відповідно до (*) перевірочними рівняннями будуть

Властивості РС-кодів.
1. Циклічний зсув кодових слів, символи яких приймають значення з GF (q), породжує нові кодові слова цього ж коду.
2. Сума за mod2 двох і більше кодових слів дає кодове слово, що належить цьому ж коду.
3. Кодова відстань РС-коду визначається не за двійковим елементам, а по q-ічним символів.
4. У РС-коді, що виправляє t _u помилок породжує многочлен визначається з виразу . Зазвичай m ₀ приймають рівним 1. Проте, за допомогою розумного вибору значення m _0, іноді можна спростити схему кодера.
5. Коригувальні здібності РС-коду визначаються його кодовою відстанню.

де T ₀ і T _u - довжина пакетів, в яких виявляються і виправляються помилки.
Виявлення помилок у кодових словах полягає у перевірці умов ((), тобто визначенні синдрому , Елементи якого визначаються з виразу .
Приклад. Потрібно сформувати кодове слово РС-коду над GF (2 ^3), відповідне двійковій інформаційної послідовності a (1,0) = 000000011100101.
Так як m = 3, то кожен q-ічний символ коду складається з трьох двійкових елементів. Тому з урахуванням таблиці 6 a (X) =  ³ x ² +  ² x +  ^6.
Визначаємо параметри коду. N = q-1 = 7; k = 5; R = 2; d = N-k +1 = 3;
.
Кодове слово формується відповідно до вираження. ,
де .
У результаті або у двійковій формі V (1,0) = 000.000.011.100.101.101.101.

ЛІТЕРАТУРА
1. Лідовскій В.І. Теорія інформації. - М., «Вища школа», 2002р. - 120с.
2. Метрологія та радіовимірювань в телекомунікаційних системах. Підручник для ВУЗів. / В. І. Нефедов, В. І. Халкин, Є. В. Федоров та ін - М.: Вища школа, 2001 р . - 383с.
3. Цапенко М.П. Вимірювальні інформаційні системи. -. - М.: Енергоатом издат, 2005. - 440С.
4. Зюко А.Г. , Кловський Д.Д., Назаров М.В., Фінк Л.М. Теорія передачі сигналів. М: Радіо і зв'язок, 2001 р . -368 С.
5. Б. Скляр. Цифрова зв'язок. Теоретичні основи та практичне застосування. Вид. 2-е, испр.: Пер. з англ. - М.: Видавничий дім «Вільямс», 2003 р . - 1104 с.