циклічний код

Циклічні коди відносяться до числа блокових систематичних кодів, в яких кожна комбінація кодується самостійно (у вигляді блоку) таким чином, що інформаційні k і контрольні т символи завжди нах

одятся на певних місцях. Можливість виявлення та виправлення практично будь-яких помилок при відносно малій надмірності в порівнянні з іншими кодами, а також простота схемної реалізації апаратури кодування і декодування зробили ці коди широко поширеними. Теорія циклічних кодів базується на теорії груп і алгебри многочленів над полем Галуа.

Код циклічний - код, порядок розподілу кодових комбінацій в якому здійснюється таким чином, що при переході від будь-якої комбінації до сусідньої кожен раз кодове відстань по Хеммінга залишається постійним.

Циклічні коди - це ціле сімейство перешкодостійких кодів, що включає в себе в якості одного з різновидів коди Хеммінга, але в цілому забезпечує велику гнучкість з точки зору можливості реалізації кодів з необхідною здатністю виявлення та виправлення помилок, що виникають при передачі кодових комбінацій по каналу зв'язку. Циклічний код відноситься до систематичних блоковим (n, k) -код, в яких k перших розрядів являють собою комбінацію первинного коду, а наступні (n? K) розрядів є перевірочними.

В основі побудови циклічних кодів лежить операція ділення переданої кодової комбінації на який породжує не приводиться поліном ступеня r. Залишок від ділення використовується при формуванні перевірочних розрядів. При цьому операції ділення передує операція множення, що здійснює зрушення вліво k-розрядної інформаційної кодової комбінації на r розрядів.

Многочлен (поліном), який можна представити у вигляді добутку многочленів нижчих ступенів, називають які наводяться (у цьому полі), в іншому випадку - не приводиться. Многочлени грають роль, подібну з простими числами в теорії чисел. Многочлени Р (Х) можна записати у вигляді десяткових або двійкових чисел або у вигляді многочлена.

Процес циклічного кодування

В основу циклічного кодування покладено використання неприводимого многочлена Р (Х), який стосовно циклічним кодами називається утворюючим, генераторним або виробляють многочленом (поліномом).

В якості інформаційних символів k для побудови циклічних кодів беруть комбінації двійкового коду на всі сполучення. У загальному випадку, якщо задану кодову комбінацію Q (x) помножити на який утворює многочлен Р (х), вийти циклічний код, що володіє тими чи іншими коригуючими властивостями в залежності від вибору Р (х). Однак в цьому коді контрольні символи m будуть розташовуватися в найрізноманітніших місцях кодової комбінації. Такий код не є систематичним, що ускладнює його схемну реалізацію. Ситуацію можна значно спростити, якщо контрольні символи приписати в кінці, тобто після інформаційних символів. Для цієї мети доцільно скористатися наступним методом:

Множимо кодову комбінацію G (x), яку потрібно закодувати, на одночлен Х m, що має ту ж ступінь, що і утворить многочлен Р (х);

Ділимо твір G (x) Х m на який утворює многочлен Р (х m):

де Q (x) - частка від ділення; R (x) - залишок.

Помноживши вираз (2.1) на Р (х) і переносячи R (x) в іншу частину рівності без зміни знака на зворотний, отримуємо:

Таким чином, відповідно до рівності (2.2), циклічний код, тобто закодоване повідомлення F (x), можна утворити двома способами:

Множення однієї кодової комбінацій двійкового коду на всі сполучення на який утворює поліном Р (х);

Множенням заданої кодової комбінації G (x) на одиночний многочлен Х m, що має ту ж саму ступінь, що і утворить многочлен Р (х), з додаванням залишку R (x), отриманого після поділу праці G (x) Х m на який утворює многочлен Р ( х).

кодування повідомлення

Потрібно закодувати кодову комбінацію 1100, що відповідає G (x) = х 3 + х 2 за допомогою Р (х) = х 3 + х + 1.

Множимо G (x) на Х m, який має третю ступінь, отримаємо:

Розділивши твір G (x) Х m на який утворює многочлен Р (х m), згідно (2.1) отримаємо:

або в двійковій еквіваленті:

Таким чином, в результаті отримуємо приватне Q (x) тією самою мірою, що й G (x):

Q (x) = x 3 + x 2 + x> 1110

і залишок:

У підсумку комбінація двійкового коду, закодована циклічним кодом, згідно (2.2) набуде вигляду:

F (x) = 1110 1011 = 1100010

Так як кожна дозволена кодова комбінація циклічного коду являє собою всі можливі суми утворює полінома G (х), то вони повинні ділитися без залишку на Р (х). Тому перевірка правильності прийнятої кодової комбінації зводиться до виявлення залишку при діленні її на виробляє поліном.

Отримання залишку свідчить про наявність помилки. Залишок від ділення в циклічних кодах грає роль синдрому.

Наприклад, передана кодова комбінація F (x) = 1100010, побудована за допомогою утворює полінома Р (х) = 1011. Під впливом перешкоди кодова комбінація трансформувалася в комбінацію F "(x) = 1000010

Ділимо прийняту комбінацію на який утворює поліном

Наявність залишку R (x) = 001 свідчить про помилку. Однак він не вказує безпосередньо на місце помилки в комбінації. Для визначення помилки існує кілька методів, заснованих на аналізі синдрому.

Визначимо місце знаходження помилки, для цього одиницю з будь-якою кількістю нулів ділимо на Р (х) = 1011.

Помилка сталася в елементі з номером:

Кількість залишків -2> 4-2 = 2

Тобто, помилка в другому елементі.

Циклічним кодом називається лінійний код, який представляє собою кінцеве безліч, замкнутий щодо операції циклічного зсуву кодових векторів, що утворюють його. нехай дано n-мірний вектор v = a 0 a 1 …a n-1 з координатами з кінцевого поля F. Його циклічним зрушенням називається вектор v "= a n-1 a 0 a 1 ... a n -2 .

Розглянемо n-мірним арифметичне простір над полем Галуа GF(2). кожному вектору a 0 a 1 …a n-1 з GF(2) можна зіставити взаємно однозначно многочлен a 0 +a 1 x+…+a n -1 x n-1 з коефіцієнтами з GF(2). Сумі двох векторів a 0 a 1 …a n-1 і b 0 b 1 …b n-1 ставиться у відповідність сума відповідних їм многочленів, твору елементів поля на вектор - твір многочлена, що відповідає цьому вектору, на елемент.

Розглянемо деякий многочлен g(x) З описаного лінійного простору. Безліч всіх многочленів з цього підпростору, які діляться без залишку на g(x), Утворює лінійне підпростір. Лінійне підпростір призначає Він деякий лінійний код.

Лінійний код, утворений класом многочленів C(g(x)), Кратних деякому полиному g(x), Званому породжує многочленом, називається поліноміальним.

Покажемо, як пов'язані поліноміальні коди C(g(x)) І циклічні коди. нехай a = a 0 ... a n-1 - деякий кодове слово, а відповідний кодовий многочлен a(x) = a 0 +...+a n -1 x n-1. циклічного зсуву a"Відповідає кодовий многочлен a"(x) = a n -1 +a 0 x+…+a n -2 x n -1, який можна виразити через первинний:

Оскільки поліноміальний код повинен ділитися на g(x), То для того, щоб він був циклічним, многочлен a"(x) Повинен ділитися на g(x). З цього міркування можна сформулювати наступну теорему. Поліноміальний код є циклічним тоді і тільки тоді, коли многочлен g(x) Є дільником многочлена x n-1. В цьому випадку многочлен g(x) Називається породжує многочленом циклічного коду.

В теорії кодування доводиться наступна теорема: якщо многочлен g(x) Має ступінь n–kі є дільником x n-1, то C(g(x)) Є лінійним циклічним ( n, k)-Кодом.

многочлен x n-1 розкладемо на множники x n–1 = (x–1)(x n -1 +x n-1 + ... + 1). Отже, циклічні коди існують при будь-якому n. число циклічних nрозрядних кодів дорівнює числу дільників багаточлена x n-1. Для побудови циклічних кодів розроблені таблиці розкладу многочленів x n-1 на многочлени, тобто на такі, які діляться тільки на одиницю і на самого себе.

Розглянемо, наприклад, які коди можна побудувати на основі многочлена x 7 -1 над полем GF(2). Розкладання многочлена на незвідні множники має вигляд

Оскільки можна утворити шість дільників багаточлена x 7 -1, комбінуючи Непріводімие подільники, існує шість довічних циклічних кодів. ( n, k) -Код визначається, по-перше, значенням n, А по-друге, значенням k = n – s, s- ступінь многочлена-дільника x n-1, що визначає код. Нижче наведені подільники полінома і відповідні їм значення k:

x – 1, s=1, k=6;

x 3 + x 2 +1, s=3, k=4;

x 3 + x+1, s=3, k=4;

(x–1)(x 3 + x 2 +1)=x 4 + x 2 + x + 1, s=4, k=3;

(x–1)(x 3 + x+1)=x 4 + x 3 + x 2 +1, s=4, k=3;

(x 3 + x 2 +1)(x 3 + x+1)=x 6 +x 5 +x 4 +x 3 +x 2 +x, s=6, k=1.

(7, 6) -код має лише один перевірки символ, а (7, 1) -код - лише один інформаційний. Вони є відповідно кодом з перевіркою на парність і кодом з повторенням.

Як і звичайний лінійний код, циклічний код може бути заданий породжує матрицею. Отже, завдання полягає в тому, щоб знайти таку матрицю, тобто знайти kлінійно незалежних кодових комбінацій, що утворюють її. Скористаємося для цього властивістю замкнутості циклічного коду щодо операції циклічного зсуву. Зауважимо, що циклічний зсув вправо на один розряд еквівалентний множенню многочлена g(x) на x. Тоді породжує матрицю можна побудувати, взявши в якості рядків породжує многочлен і kйого циклічних зрушень:

Розглянемо тепер, як за допомогою породжує многочлена g(x) = 1+x+x 3 здійснюється кодування (7, 4)-кодом. Візьмемо, наприклад, 4-розрядне слово (0101), якому відповідає многочлен f(x) = x + x 3. Перемноживши ці два многочлена.

Відповідний цьому слову, від формальної змінної x. Видно, що це відповідність не просто взаимнооднозначное, але і изоморфное. Так як «слова» складаються з літер з поля, то їх можна складати і множити (поелементно), причому результат буде в тому ж полі. Поліном, відповідний лінійної комбінації пари слів і, дорівнює лінійної комбінації поліномів цих слів

Це дозволяє розглядати безліч слів довжини n над кінцевим полем як лінійний простір поліномів зі ступенем не вище n-1 над полем

алгебраїчне опис

Якщо кодове слово, що виходить циклічним зрушенням на один розряд вправо з слова, то йому відповідний поліном c 1 (x) Виходить з попереднього множенням на x:

Користуючись тим, що,

Зрушення вправо і вліво відповідно на jрозрядів:

якщо m(x) - довільний поліном над полем GF(q) і c(x) - кодове слово циклічного ( n,k) Коду, то m(x)c(x)mod(x n − 1) теж кодове слово цього коду.

породжує поліном

визначенняПороджує поліномом циклічного ( n,k) коду Cназивається такий ненульовий поліном з C, Ступінь якого найменша і коефіцієнт при старшій ступеня g r = 1 .

теорема 1

якщо C- циклічний ( n,k) Код і g(x) - його породжує поліном, тоді ступінь g(x) дорівнює r = n − k і кожне кодове слово може бути єдиним чином представлено у вигляді

c(x) = m(x)g(x) ,

де ступінь m(x) Менше або дорівнює k − 1 .

теорема 2

g(x) - породжує поліном циклічного ( n,k) Коду є дільником двочлена x n − 1

наслідки:таким чином в якості породжує полінома можна вибирати будь-який поліном, дільник x n- 1. Ступінь обраного полінома буде визначати кількість перевірочних символів r, Число інформаційних символів k = n − r .

породжує матриця

Поліноми лінійно незалежні, інакше m(x)g(x) = 0 при ненулевом m(x) , що неможливо.

Значить кодові слова можна записувати, як і для лінійних кодів, наступні чином:

, де Gє породжує матрицею, m(x) - інформаційнимполиномом.

матрицю Gможна записати в символьній формі:

перевірочна матриця

Для кожного кодового слова циклічного коду справедливо. Тому перевірочну матрицюможна записати як:

кодування

несистематичне

При несистематичний кодування кодове слово виходить у вигляді твору інформаційного полінома на який породжує

c(x) = m(x)g(x) .

Воно може бути реалізовано за допомогою перемножителя полиномов.

систематичне

При систематичному кодуванні кодове слово формується у вигляді інформаційного подблока і перевірочного

Нехай інформаційне слово утворює старші ступеня кодового слова, тоді

c(x) = x r m(x) + s(x),r = n − k

Тоді з умови, слід

Це рівняння і задає правило сістематічекого кодування. Воно може бути реалізовано за допомогою багатотактних лінійних фільтрів (МЛФ)

приклади

Двійковий (7,4,3) код

В якості подільника x 7 - 1 виберемо породжує поліном третього ступеня g(x) = x 3 + x + 1 , Тоді отриманий код буде мати довжину n= 7, число перевірочних символів (ступінь породжує полінома) r= 3, число інформаційних символів k= 4, мінімальна відстань d = 3 .

породжує матрицякоду:

де перший рядок являє собою запис полінома g(x) Коефіцієнтами по зростанню ступеня. Решта рядків - циклічні зрушення першого рядка.

Перевірочна матриця:

де i-ий стовпець, починаючи з 0-ого, являє собою залишок від ділення x iна поліном g(x), Записаний за зростанням ступенів, починаючи зверху.

Так, наприклад, 3-ий стовпець виходить, або у векторній запису.

Легко переконатися, що GH T = 0 .

Двійковий (15,7,5) БЧХ код

Як породжує полінома g(x) Можна вибрати твір двох подільників x 15 − 1 ^

g(x) = g 1 (x)g 2 (x) = (x 4 + x + 1)(x 4 + x 3 + x 2 + x + 1) = x 8 + x 7 + x 6 + x 4 + 1 .

Тоді кожне кодове слово можна отримати за допомогою твори інформаційного полінома m(x) Зі ступенем k- 1 таким чином:

c(x) = m(x)g(x) .

Наприклад, інформаційномуслову відповідає поліном m(x) = x 6 + x 5 + x 4 + 1 , Тоді кодове слово c(x) = (x 6 + x 5 + x 4 + 1)(x 8 + x 7 + x 6 + x 4 + 1) = x 14 + x 12 + x 9 + x 7 + x 5 + 1 , Або у векторному вигляді

Див. також

посилання

Wikimedia Foundation. 2010 року.

Циклічні форми в музиці
Циклічні граничні умови

Дивитися що таке "Циклічні коди" в інших словниках:

укорочені циклічні коди- - [Л.Г.Суменко. Англо російський словник з інформаційних технологій. М .: ДП ЦНДІЗ, 2003.] Тематики інформаційні технології в цілому EN shortened cyclic codes ...

Коди Ріда-Соломона- недвійкові циклічні коди, що дозволяють виправляти помилки в блоках даних. Елементами кодового вектора не є біти, а групи бітів (блоки). Дуже поширені коди Ріда Соломона, що працюють з байтами (октетами). Код Ріда Соломона є ... Вікіпедія

коди Голі- Сімейство скоєних лінійних блокових кодів з виправленням помилок. Найбільш корисним є двійковий код Голі. Відомий також трійчастий код Голі. Коди Голі можна розглядати як циклічні коди. ... ... Довідник технічного перекладача

Коди, що виправляють помилки

Коди виправляють помилки- Виявлення помилок в техніці зв'язку дія, спрямована на контроль цілісності даних при записі / відтворенні інформації або при її передачі по лініях зв'язку. Виправлення помилок (корекція помилок) процедура відновлення інформації після ... ... Вікіпедія

Виправляють помилки Коди- Виявлення помилок в техніці зв'язку дія, спрямована на контроль цілісності даних при записі / відтворенні інформації або при її передачі по лініях зв'язку. Виправлення помилок (корекція помилок) процедура відновлення інформації після ... ... Вікіпедія

Білоруський державний університет інформатики і радіоелектроніки

кафедра РЕЗ

реферат на тему:

«Циклічні коди. Коди БЧХ »

МІНСЬК 2009

циклічні коди

Циклічним кодом називається лінійний блоковий (n, k) -код, який характеризується властивістю циклічності, тобто зсув вліво на один крок будь-якого дозволеного кодового слова дає також дозволене кодове слово, що належить цьому ж коду і у якого, безліч кодових слів представляється сукупністю многочленів ступеня (n-1) і менш, діляться на деякий многочлен g (x) ступеня r = nk , який є співмножником двочлена xn +1.

Многочлен g (x) називається породжує.

Як випливає з визначення, в циклічному коді кодові слова подаються у вигляді многочленів

де n - довжина коду; - коефіцієнти з поля GF (q).

Якщо код побудований над полем GF (2), то коефіцієнти приймають значення 0 або 1 і код називається двійковим.
Приклад.Якщо кодове слово циклічного коду

то відповідний йому многочлен

Наприклад, якщо код побудований над полем GF (q) = GF (2 3), яке є розширенням GF (2) по модулю неприводимого многочлена f (z) = z 3 + z + 1, а елементи цього поля мають вигляд, представлений в таблиці 1,

то коефіцієнти

приймають значення елементів цього поля і тому вони самі відображаються у вигляді многочленів такого вигляду
де m - ступінь многочлена, за яким отримано розширення поля GF (2); a i - коефіцієнти, які беруть значення елементів GF (2), тобто 0 і 1. Такий код називається q-ним.

Довжина циклічного коду називається примітивною і сам код називається примітивним, якщо його довжина n = q m -1 на GF (q).

Якщо довжина коду менше довжини примітивного коду, то код називається укороченим або непрімітівним.

Як випливає з визначення загальне властивість кодових слів циклічного коду - це їх подільність без залишку на деякий многочлен g (x), званий породжує.

Результатом поділу двочлена x n +1 на многочлен g (x) є перевірки многочлен h (x).

При декодуванні циклічних кодів використовуються многочлен помилок e (x) і синдромний многочлен S (x).

Многочлен помилок ступеня не більше (n-1) визначається з виразу

де - многочлени, що відображають відповідно прийняте (з помилкою) і передане кодові слова.

Ненульові коефіцієнти в е (x) займають позиції, які відповідають помилок.

Приклад.

Синдромний многочлен, який використовується під час декодування циклічного коду, визначається як залишок від ділення прийнятого кодового слова на породжує многочлен, тобто

або

Отже, синдромний многочлен залежить безпосередньо від многочлена помилок е (х) .Це положення використовується при побудові таблиці синдромів, що застосовується в процесі декодування. Ця таблиця містить список многочленів помилок і список відповідних синдромів, обумовлених з виразу

(Див. Таблицю 2).

У процесі декодування за прийнятим кодовим словом обчислюється синдром, потім в таблиці знаходиться відповідний многочлен е (х), підсумовування якого з прийнятим кодовим словом дає виправлене кодове слово, тобто

Перераховані многочлени можна складати, множити і ділити, використовуючи відомі правила алгебри, але з приведенням результату по mod 2, а потім по mod x n +1, якщо ступінь результату перевищує ступінь (n-1).

Припустимо, що довжина коду n = 7, то результат наводимо по mod x 7 +1.

При побудові та декодування циклічних кодів в результаті поділу многочленів зазвичай необхідно мати не приватна, а залишок від ділення.
Тому рекомендується більш простий спосіб розподілу, використовуючи не многочлени, а тільки його коефіцієнти (варіант 2 в прикладі).

Приклад.

Матричне завдання кодів

Циклічний код може бути заданий породжує і перевірочної матрицями. Для їх побудови досить знати що породжує g (x) і перевірки h (x) многочлени. Для несистематического циклічного коду матриці будуються циклічним зрушенням породжує і перевірочного многочленів, тобто шляхом їх множення на x

При побудові матриці H (n, k) старший коефіцієнт многочлена h (x) розташовується праворуч.

Приклад.Для циклічного (7,4)-коду до породжує многочленом g (x) = x 3 + x + 1 матриці G (n, k) і H (n, k) мають вигляд:

де

Для систематичного циклічного коду матриця G (n, k) визначається з виразу

де I k - одинична матриця; R k, r - прямокутна матриця. Рядки матриці R k, r визначаються з виразів або де a i (x) - значення i-того рядка матриці I k; i - номер рядка матриці R k, r.

Приклад.Матриця G (n, k) для (7,4)-коду на основі породжує многочлена g (x) = x 3 + x + 1, будується в наступній послідовності

або

Визначається R 4,3, використовуючи

так як

Аналогічним способом визначається