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

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

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

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

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

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

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

БІЛОРУСЬКИЙ ДЕРЖАВНИЙ УНІВЕРСИТЕТ ІНФОРМАТИКИ ТА РАДІОЕЛЕКТРОНІКИ

кафедра РЕМ

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

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

МІНСЬК, 2009

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

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

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

або

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

так як

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

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

Багато найважливіших завадостійких кодів систем зв'язку, -

зокрема циклічні, засновані на структурах кінцевих Арифметика

поля Галуа. Полемназивається безліч елементів, які кінцевого поля

звання операцій взято в лапки, тому що вони не завжди є загальноприйнятими арифметичними операціями. У полі є нульовий елемент (0), або нуль, і одиничний елемент (1), або одиниця. Якщо число qелементів поля обмежено, то поле називається кінцевим полем, або кінцевим полем Галуа, і позначається GF(q) yде q -порядок поля. Найменшим полем Галуа є двоелементне оле GF( 2), що складається всього з двох елементів 1 і 0. Для того щоб

1 Еваріст Галуа (Evariste Galois, 1811 – 1832) – французький математик, заклав основи сучасної алгебри.

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

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

Для операцій складання та множення виконуються звичайні математичні правила асоціативності а + (Ь + с) = (а + Ь)+ с, комутативності - а + b = b + аі а b = b ата дистрибутивності - а (Ь+ с) = а b + а с.

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

Поле має містити адитивну одиницю -елемент 0, такий, що а + 0 = адля будь-якого елемента поля а.

Поле має містити мультиплікативну одиницю -елемент 1, такий, що аЛ = адля будь-якого елемента поля а.

Наприклад, існують поля дійсних чисел, раціональних чисел, комплексних чисел. Ці поля містять безліч елементів.

Практично всі набори, утворені циклічною перестановкою кодової комбінації, також є кодовими комбінаціями. Так, наприклад, циклічні перестановки комбінації 1000101 будуть кодовими комбінаціями 0001011, 0010110, 0101100 і т.д. Ця властивість дозволяє значною мірою спростити кодуючий і декодуючий пристрій, особливо при виявленні помилок і виправленні одиночної помилки. Увага до циклічних кодів обумовлена ​​тим, що властиві їм високі коригувальні властивості реалізують на основі порівняно простих методів алгебри. У той самий час для декодування довільного лінійного блокового коду частіше застосовують табличні методи, які потребують великого обсягу пам'яті декодера.

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

У циклічному коді кодові слова є багаточленами (поліномами)

де п -довжина коду; A i -коефіцієнти поля Галуа (значення кодової комбінації).

Наприклад, для кодової комбінації 101101 поліноміальний запис має вигляд

Прикладами циклічних кодів є коди з парною перевіркою, коди з повтореннями, коди Хеммінгу, PC-коди та турбокоди.

Код Хеммінгу. Можливості виправлення помилок у коді Хеммінгу пов'язані з мінімальною кодовою відстанню d0.Виправляються всі помилки кратності q= cnt (d 0- l)/2 (тут cnt означає «ціла частина») і виявляються помилки кратності d 0 - 1. Так, під час контролю на непарність d Q = 2 і виявляються поодинокі помилки. У коді Хеммінгу d 0 = 3. Додатково до інформаційних розрядів вводиться L = log 2 Q надлишкових контролюючих розрядів, де Q -кількість інформаційних розрядів. Параметр Lокругляється до найближчого більшого цілого значення. L-розрядний контрольний код є інвертованим результатом порозрядної складання (додавання за модулем 2) номерів тих інформаційних розрядів, значення яких рівні одиниці.

Приклад 7.7

Нехай маємо основний код 100 110, тобто. Q = 6. Визначимо додатковий код.

Рішення

Знаходимо, що L= 3 і додатковий код дорівнює

де П - символ операції порозрядного додавання, і після інвертування маємо 000. Тепер з основним кодом буде переданий і додатковий. У приймачі знову розраховують додатковий код і порівнюють із переданим. Фіксується код порівняння, і якщо він відмінний від нуля, його значення є номер помилково прийнятого розряду основного коду. Тож якщо прийнятий код 100010, го розрахований додатковий код дорівнює інверсії від 010Ш10 = 100, тобто. 011, що означає помилку у 3-му розряді.

Узагальненням кодів Хеммінгу є циклічні коди БЧХ, які дозволяють коригувати багаторазові помилки прийнятої кодової комбінації.

Коди Ріда - Соломонабазуються на полях Галуа або кінцевих нулях. Арифметичні дії додавання, віднімання, множення, поділ і т.д. над елементами кінцевого нуля дають результат, який є елементом цього нуля. Кодувальник або декодер Ріда-Соломона повинен обов'язково виконувати ці операції. Усі операції для реалізації коду вимагають спеціального обладнання чи спеціалізованого програмного забезпечення.

Турбокоди.Надлишкові коди можуть застосовуватися як самостійно, і у вигляді деякого об'єднання кількох кодів, коли набори символів одного надлишкового коду розглядаються як елементарні інформаційні символи іншого надлишкового коду. Таке об'єднання почали називати каскаднимкодом. Величезною перевагою каскадних кодів є те, що їх застосування дозволяє спростити кодер і особливо декодер у порівнянні з аналогічними пристроями некаскадних кодів тієї ж довжини та надмірності. Каскадне кодування спричинило створення турбокодів. Турбокодомназивають паралельну структуру сигналу, що складається із двох або більшої кількості систематичних кодів. Основний принцип їх побудови - використання кількох паралельних компонентних кодерів. Як компонентні можна використовувати як блокові, так і згорткові коди, коди Хеммінга, PC-код, БЧХ та ін. Використання перфорації (виколювання) дозволяє збільшити відносну швидкість турбокоду, адаптувавши його здатність виправляти до статистичних характеристик каналу зв'язку. Принцип формування турбокода полягає у наступному: вхідний сигнал х,Що складається з Добіт, подається паралельно на Nперемежувачів. Кожен з останніх являє собою пристрій, що здійснює перестановку елементів у блоці з Добіт у псевдовипадковому порядку. Вихідний сигнал з перемежувачів – символи із зміненим порядком прямування – надходить на відповідні елементарні кодери. Двійкові послідовності х р i= 1,2,..., JV, на виході кодера є перевірочними символами, які разом з інформаційними бітами становлять єдине кодове слово. Застосування перемежувача дозволяє запобігти появі послідовностей корельованих помилок при декодуванні турбокодів, що є важливим при використанні традиційного в обробці рекурентного способу декодування. Залежно від вибору компонентного коду турбокоди діляться на згорткові турбокоди та блокові коди-твори.

Циклічним кодом називається лінійний код, який являє собою кінцеву множину, замкнуту щодо операції циклічного зсуву кодових векторів, що утворюють його. Нехай даний 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+x2+x+1, s=4, k=3;

(x–1)(x 3 +x+1)=x 4+x3+x2+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) коефіцієнтами за зростанням ступеня. Інші рядки - циклічні зрушення першого рядка.

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

,

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

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

Легко переконатися, що 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 …

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

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

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

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

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