5x5 + x2 + 1 x5 + x4 + x3 + x2 + 1 x5 + x4 + x2 + x + 1100101 111101 1101116x6 + x + 1 x6 + x5 + x2 + x + 11000011 1100111 7x7 + x3 + 1 x7 + x3 + x2 + x + 1 x7 + x4 + x3 + x2 + 110001001 10001111 10011101 8x8 + x7 + x6 + x5 + x2 + x +1 x8 + x4 + x3 + x2 + 1 x8 + x6 + x5 + x + 1111100111 100011101 101100011
Побудова дозволеної кодової комбінації циклічного коду зводиться до наступного:
. Представляємо інформаційну частину кодової комбінації довжиною k у вигляді полінома Q (x).
. Виробляємо зрушення k -розрядної кодової комбінації на r розрядів, шляхом множення Q (x) на одночлен xr.
. Ділимо многочлен Q (x) xr на який утворює поліном Р (x), ступінь якого дорівнює r. У результаті поділу утворюється залишок R (x).
. Дозволена кодова комбінація циклічного коду має наступний вигляд:
(2)
Виявлення помилок при циклічному кодуванні зводиться до поділу прийнятої кодової комбінації на той же утворює поліном Р (х), який використовувався при кодуванні. Якщо помилок у прийнятій кодової комбінації немає, то поділ на утворює поліном проводиться без залишку. Якщо при діленні вийде залишок, то це свідчить про наявність помилки. Залишок від ділення в циклічних кодах грає роль «синдрому».
Для визначення місця розташування помилки в циклічному коді існує ряд методів, заснованих на аналізі «синдрому» R (x).
Основним функціональним вузлом кодують і декодер циклічних кодів є схема поділу, структура якої наведена на рис. 1.
До складу схеми розподілу входять зсувний регістр (комірки 1 - 4), суматори за модулем 2 (М2) і ключ (Кл). Число осередків зрушується регістра вибирається рівним ступеня утворює полінома, а число суматорів за модулем 2 на одиницю менше його ваги. Подільне у вигляді двійкового коду подається на вхід зрушується регістру, а поліном Р (х) вводиться в регістр у вигляді відповідним чином підібраною структури зворотних зв'язків через суматори за модулем 2. Ключ замикає зворотний зв'язок, що забезпечує роботу схеми поділу.
Малюнок 1 - Схема розподілу на Р (х)
Укорочені циклічні коди
Коригувальні можливості циклічних кодів визначаються ступенем т утворює многочлена. У той час як необхідне число інформаційних символів може бути будь-яким цілим числом, можливості у виборі розрядності коду вельми обмежені.
Якщо, наприклад, необхідно виправити поодинокі помилки при k=5, то не можна взяти утворює многочлен третього ступеня, оскільки він дасть тільки сьомій залишків, а загальне число розрядів вийде рівним 8.
Отже, необхідно брати многочлен четвертого ступеня і тоді n=15. Такий код розрахований на 11 інформаційних розрядів.
Однак можна побудувати код мінімальної розрядності, замінивши в (n, k) -код j перших інформаційних символів нулями і виключивши їх з кодових комбінацій. Код вже не буде циклічним, оскільки циклічний зсув однієї дозволеної кодової комбінації не завжди призводить до іншої дозволеної комбінації того ж коду. Одержуваний таким шляхом лінійний (nj, kj) -код називають укороченим циклічним кодом. Мінімальна відстань цього коду не менше, ніж мінімальна кодова відстань (n, k) -коду, з якого він отриманий. Матриця укороченого коду виходить з утворює матриці (n, k) -коду винятком j рядків і стовпців, відповідних старшим розрядам. Наприклад, що утворює матриця коду (9,5), отримана з матриці коду (15,11), має вигляд
Виявлення і виправлення пачок помилок
Для довільного лінійного блокового (п, k) -коду, розрахованого на виправлення пакетів помилок довжини b-менш, основним співвідношенням, устанавливающим зв'язок коректує здібності з числом надлишкових символів, є межа рейджерів: n - k? 2b
При виправленні лінійним кодом пакетів довжини b-менш з одночасним виявленням пакетів довжини l? b-менш потрібно принаймні b + l перевірочних символів.
З циклічних кодів, призначених для виправлення пакетів помилок, широко відомі коди Бартона, Файр і Ріда-Соломона.
Перші два різновиди кодів служать для виправлення одного пакета помилок у блоці.
Коди Ріда-Соломона здатні виправляти кілька пачок помилок.
Висновок
Циклічні коди отримали досить широке застосування завдяки їх ефективності при виявленні і виправленні помилок. Схеми кодують і декодер для цих кодів надзвичайно прості і будуються на основі звичайних регістрів зсуву.
Список літератури
циклічний код многочлен помилка
Б. Скляр. Цифровий зв'язок. Теоретичні основи і практичне застосування. Изд. 2-е, испр .: Пер. з англ.- М .: Видавничий дім «Вільямс», 2003 р ...
