Виявлення помилок при циклічному кодуванні

Циклічні коди в теорії кодування.

Тема: Циклічні коди.

Зміст

Циклічні коди в теорії кодування для скорочення прийнято записувати у вигляді поліномів, наприклад, кодовому слову u=(U_n-1, U_n-2,...,U₂, U₁, U₀) відповідає поліном:

u(x)=(U_n-1х^n-1+U_n-2х^n-2+...+U₂х² +U₁х¹ + U₀) (2.1)

Щоб правильно розуміти запис поліному потрібно пам’ятати наступне:

по‑перше, розряди коду нумеруються справа наліво, починаючи від 0;

по‑друге, склад поліному (2.1) залежить від конкретних значень U_n (0 або 1) розрядів кодового слова;

по‑третє, змінна х є символічною і її значення не впливає на властивості коду. Значення має показник при х, який означає номер позиції символу в коді, зменшений на 1.

До складу поліному, отже, подаються і записуються в символічному вигляді тільки ті розряди для яких U_і=1, тоді як у кодовому слові записуються всі розряди, – для яких як U_і=1 так і U_і=0. Так, для кодового слова (1101001) (семирозрядного) кодовий поліном виглядає як: х⁶+х⁵+х³+1 (чотирирозрядний), кодова комбінація а₁ = 101100 зображується поліномом а₁(х) = х⁵+х³+х², а комбінація а₂ = 010110 поліномом а₂(х) = х⁴+х²+х.

Найчастіше запис перетворень кодових комбінацій виконується у вигляді математичних операцій над поліномами. Операції над поліномамн. виконуються за звичайними арифметичними правилами, тільки додавання виконується за модулем два а віднімання замінюється додаванням. Наприклад:

Додавання: а₁(х)+а₂(х)=(х⁵+х³+х²)+(х⁴+х²+х)=х⁵+х³+х⁴+х, оскільки х²+х²= =1Å1=0;

Множення: а₁(х)а₂(х) = (х⁵+х³+х²)(х⁴+х²+х)=х⁹+х⁷+х⁶+х⁷+х⁵+х⁴+х⁶+х⁴+х³= х⁹+х⁵+х³;

Ділення: а₁(х)/а₂(х) = х⁵+х³+х² | х⁴+х²+х

Åх⁵+х³+х²| x

0

Через властивість циклічності кожний кодовий поліном циклічного коду повинен бути кратним деякому мінімальному ненульовому кодовому поліному g(х), який називається породжуючим, або твірним поліномом. Будь який кодовий поліном u(х) (повна кодова комбінація) циклічного коду може бути отриманий шляхом множення породжуючого поліному g(х) степені (n-k) на відповідний інформаційний поліном m(х), степені (k) тобто u(х)= =m(х)g(х). Тому будь-який циклічний (n.k)-код степені (n) повністю визначається його породжуючим поліномом. За степінню породжуючого поліному, отже, можна визначити число перевіркових розрядів у циклічному коді, яке буде дорівнювати цій степені. З іншого боку циклічний (n.k)-код повинен мати породжуючий поліном степені не меншої (n-k).

Виявлення помилок при циклічному кодуванні здійснюється шляхом ділення кодового полінома на твірний. Якщо в результаті передачі каналами зв'язку кодове слово передане без помилок, то ділення його полінома на твірний поліном буде беззалишковим (остача від ділення, ‑ синдром циклічного коду, ‑ буде нульовою). Ненульовий залишок (синдром) буде свідчити про помилку. За значенням синдрому можна знайти конфігурацію (місце знаходження) помилки і виправити її. Взаємозалежність між синдромом (остачею) циклічного коду (7.4) і помилковим символом для породжуючого поліному g(х)=х³+х+1 наведена в табл. 2.1.

Таблиця 2.1.

Відповідність значень синдрому циклічного коду (7.4) та конфігурацій помилок

Помилковий символ	х^6	х^5	х^4	х^3	х^2	х
Синдром при g(х)=х^3+х+1

Контрольні питання:

1 Що таке циклічні коди?

2 Як виконують циклічну перестановку символів в циклічному коді?

3 Що означає символіч­ний запис (поліном) х⁴+х²+х?

4 Як виконуються опера­ції над поліномами?

5 Що таке породжуючий поліном циклічного (n.k) коду?

6 Як отримуємо дозволе­ні кодові комбінації циклічного коду?

Дата добавления: 2014-01-07