Циклічні коди характеризуються тим, що при циклічній перестановці всіх символів кодової комбінації цього коду утворюється інша кодова комбінація цього коду.
Комбінація циклічного коду;
Також є комбінація циклічного коду.
При розгляді циклічних кодів двійкові числа представляють як многочлена, ступінь якого ( п - 1), п- Довжина кодової комбінації.
Наприклад, комбінація 1001111 ( п= 7) буде представлена багаточленом
При такому поданні дії кодовими комбінаціями зводяться до дій над многочленами. Ці дії проводяться відповідно до звичайної алгебри, за винятком того, що приведення подібних членів здійснюється за модулем 2.
Виявлення помилок за допомогою циклічного коду забезпечується тим, що як дозволені комбінації вибираються такі, які діляться без залишку на деякий заздалегідь обраний поліном G(x). Якщо прийнята комбінація містить спотворені символи, то поділ на поліном G(x) здійснюється із залишком. При цьому формується сигнал, що свідчить про помилку. Поліном G(x)називається утворюючим.
Побудова комбінацій циклічного коду можлива шляхом множення вихідної комбінації А(х) на утворює поліном G(x)з наведенням подібних членів за модулем 2:
- якщо старший ступінь твору не перевищує ( п - 1), то отриманий поліном представлятиме кодову комбінацію циклічного коду;
- якщо старший ступінь твору більший або дорівнює п, то поліном твору ділиться на заздалегідь обраний поліном ступеня пі результатом множення вважається одержаний залишок від розподілу.
Таким чином, всі поліноми, що відображають комбінації циклічного коду, матимуть ступінь нижче п.
Часто як поліном, на який здійснюється поділ, береться поліном G(x)= +1. За такого формування кодових комбінацій позиції інформаційних і контрольних символів заздалегідь визначити не можна.
Великою перевагою циклічних кодів є простота побудови пристроїв, що кодують і декодують, які за своєю структурою представляють регістри зсуву зі зворотними зв'язками.
Число розрядів регістру вибирається рівним ступеня утворює полінома.
Зворотній зв'язокздійснюється з виходу регістру деякі розряди через суматори, кількість яких вибирається на одиницю менше кількості ненульових членів утворюючого полінома. Суматори встановлюються на входах тих розрядів регістру, яким відповідають ненульові члени полінома, що утворює.
На рис.17 наведена схема кодуючого регістру для перетворення чотирирозрядної комбінації на семирозрядну.
Малюнок 17 - Схема регістру, що кодує.
У табл. 4 показано, як шляхом зсувів вихідної комбінації 0101 виходить комбінація циклічного коду 1010011. п= 7, k=4. Комбінація 0101, ключ у положенні 1. Протягом перших чотирьох тактів регістр буде заповнений, потім ключ переводиться в положення 2. Зворотний зв'язок замикається. Під дією семи зсувних тактів відбувається формування семирозрядного циклічного коду.
Таблиця 4
Властивості циклічного коду:
1) циклічний код виявляє всі поодинокі помилки, якщо утворює поліном містить більше одного члена. Якщо G(x)=x+ 1, то код виявляє поодинокі помилки та всі непарні;
2) циклічний код з G(x)= (x+ 1)G(x) виявляє всі поодинокі, подвійні та потрійні помилки;
3) циклічний код з утворюючим поліномом G(x) ступеня r = n - kвиявляє всі групові помилки тривалістю в rсимволів.
Контрольні питання
Циклічні коди названі так тому, що в них частина комбінацій коду або всі комбінації можуть бути отримані шляхом циклічного зсуву однієї або кількох комбінацій коду. Циклічний зсув здійснюється праворуч наліво, причому крайній лівий символ щоразу переноситься в кінець комбінації. Циклічні коди, практично, всі відносяться до систематичних кодів, в них контрольні та інформаційні розряди розташовані на певних місцях. Крім того, коди відносяться до блокових кодів. Кожен блок (одна літера є окремим випадком блоку) кодується самостійно.
Ідея побудови циклічних кодів виходить з використання неприведених у полі двійкових чисел многочленов. Неприведениминазиваються багаточлени, які можуть бути представлені у вигляді твору багаточленів нижчих ступенів з коефіцієнтами з того ж поля, так само, як прості числа не можуть бути представлені твором інших чисел. Іншими словами, неприведені багаточлени діляться без залишку тільки на себе або на одиницю.
Неприводимые багаточлени теорії циклічних кодів грає роль утворюють многочленов. Якщо задану кодову комбінацію помножити на обраний багаточлен, що не приводиться, то отримаємо циклічний код, коригувальні здібності якого визначаються неприводимим многочленом.
Припустимо, потрібно закодувати одну із комбінацій чотиризначного двійкового коду. Припустимо також, що ця комбінація G(x) = x 3 + x 2 + 1 ® 1011. Поки не обґрунтовуючи свій вибір, беремо з таблиці багаточленів, що не наводяться, як утворює багаточлен. P(x) = x 3 + x + 1 ® 1011. Потім помножимо G(x)на одночлен того ж ступеня, що і багаточлен, що утворює. Від множення багаточлена на одночлен ступеня nступінь кожного члена багаточлена підвищиться на nщо еквівалентно приписуванню nнулів із боку молодших розрядів многочлена. Так як ступінь вибраного багаточлена, що не приводиться, дорівнює трьом, то вихідна інформаційна комбінація множиться на одночлен трьох ступенів
G(x) x n =(x 3 + x 2 + 1) x 3 = x 6 + x 5 + x 3 = 1101000.
Це робиться для того, щоб згодом у місці цих нулів можна було б записати корегуючі розряди.
Значення коригувальних розрядів знаходять за результатами від розподілу G(x) x nна P(x):
x 6 +x 5 +0+x 3 +0+0+0 ½x 3 +x+1
x6+0+x4+x3
x 5 +x 4 +0+0 x 3 +x 2 +x+1+ x 5 +0+x 3 +x 2
x4+x3+x2+0
x 4 + 0 +x 2 +x
x 3+0+x+0
x 3 +0+x+1
Таким чином,
або в загальному вигляді
де Q(x)¾ приватне, а R(x)¾ залишок від розподілу G(x)×x nна P(x).
Бо в двійковій арифметиці 1 Å 1 = 0, отже, -1 = 1, можна при додаванні двійкових чисел переносити доданки з однієї частини до іншої без зміни знака (якщо це зручно), тому рівність виду a Å b = 0 можна записати і як a = b, і як a - b = 0. Усі три рівності у разі означають, що чи aі bрівні 0, або aі bдорівнюють 1, тобто. мають однакову парність.
Таким чином, вираз (5.1) можна записати як
F(x) = Q (x) P (x) = G (x) x n + R (x),
що у разі нашого прикладу дасть
F(x)=(x 3 + x 2 + x + 1) (x 3 + x + 1)= (x 3 + x 2 + 1)x 3 + 1,
F(x)= 1111 1011 = 1101000 + 001 = 1101001.
Багаточлен 1101001 і є шукана комбінація, де 1101 - інформаційна частина, а 001 - контрольні символи. Зауважимо, що шукану комбінацію ми отримали б і як в результаті множення однієї з комбінацій повного чотиризначного двійкового коду (в даному випадку 1111) на багаточлен, що утворює, так і множенням заданої комбінації на одночлен, що має той же ступінь, що і обраний утворює многочлен (в в нашому випадку таким чином була отримана комбінація 1101000) з подальшим додаванням до отриманого твору залишку від розподілу цього твору на утворює многочлен (у нашому прикладі залишок має вигляд 001).
І тут вирішальну роль відіграють властивості утворює многочлена P(x). Методика побудови циклічного коду така, що багаточлен, що утворює, бере участь в утворенні кожної кодової комбінації, тому будь-який багаточлен циклічного коду ділиться на утворює без залишку. Але без залишку діляться лише багаточлени, які належать даному коду, т. е. утворює многочлен дозволяє вибрати дозволені комбінації з усіх можливих. Якщо ж при розподілі циклічного коду на багаточлен, що утворює, буде отриманий залишок, то значить або в коді відбулася помилка, або це комбінація якогось іншого коду (заборонена комбінація). За залишком і виявляється наявність забороненої комбінації, тобто виявляється помилка. Залишки від поділу багаточленів є розпізнавальниками помилок циклічних кодів.
З іншого боку, залишки від поділу одиниці з нулями на багаточлен, що утворює, використовуються для побудови циклічних кодів.
При розподілі одиниці з нулями на утворює многочлен слід пам'ятати, що довжина залишку повинна бути не меншою за кількість контрольних розрядів, тому у разі нестачі розрядів у залишку до залишку приписують справа необхідну кількість нулів.
01100 11111+
починаючи з восьмого, залишки повторюватимуться.
Залишки від розподілу використовуються для побудови утворюючих матриць, які, завдяки своїй наочності та зручності отримання похідних комбінацій, набули широкого поширення для побудови циклічних кодів. Побудова утворюючої матриці зводиться до складання одиничної транспонованої та додаткової матриці, елементи якої являють собою залишки від поділу одиниці з нулями на багаточлен, що утворює. P(x). Нагадаємо, що одинична транспонована матриця є квадратну матрицю, всі елементи якої нули, крім елементів розташованих по діагоналі праворуч наліво зверху вниз (у нетранспонованій матриці діагональ з одиничними елементами розташована зліва направо зверху вниз). Елементи додаткової матриці приписуються праворуч від одиничної матриці транспонованої. Використовуватися можуть лише ті залишки, вага яких W ³ d 0- 1, де d 0‑ мінімальна кодова відстань. Довжина залишків повинна бути не меншою за кількість контрольних розрядів, а кількість залишків повинна дорівнювати числу інформаційних розрядів.
Рядки утворюючої матриці є першими комбінаціями. вихідного коду. Інші комбінації коду виходять в результаті підсумовування по модулю 2 всіляких поєднань рядків утворює матриці.
приклад.
Побудувати повну утворюючу матрицю циклічного коду, що виявляє всі поодинокі та подвійні помилки при передачі 10-розрядних двійкових комбінацій.
Рішення.
За таблицею 5.12 вибираємо найближче значення k ³ 10.
Таблиця 5.12 – Співвідношення між інформаційними та перевірочними символами для коду довжиною до 16 розрядів
| n | k | ρ | n | k | ρ |
Відповідно до таблиці таким значенням буде k = 11, при цьому r = 4, а
n = 15. Також вибираємо утворюючий багаточлен x4+x3+1.
Повну утворюючу матрицю будуємо з одиничної транспонованої матриці в канонічній формі та додаткової матриці, що відповідає перевірочним розрядам.
Транспонована матриця для k = 11 має вигляд:
Додаткова матриця може бути побудована за залишками поділу комбінації у вигляді одиниці з нулями (останнього рядка одиничної матриці транспонованої) на обраний утворює многочлен.
Повна утворююча матриця матиме вигляд:
Описаний вище метод побудови матриць не є єдиним. Утворююча матриця може бути побудована в результаті безпосереднього множення елементів одиничної матриці на багаточлен, що утворює. Це часто буває зручніше, ніж перебування залишків від поділу. Отримані коди нічим не відрізняються від кодів, побудованих за утворюючими матрицями, в яких додаткова матриця складається з залишків від розподілу одиниці з нулями на багаточлен, що утворює.
Утворююча матриця може бути побудована також шляхом циклічного зсуву комбінації, отриманої в результаті множення рядка одиничної матриці рангу kна утворює многочлен.
Помилки в циклічних кодах виявляються за допомогою залишків від поділу отриманої комбінації на багаточлен, що утворює. Залишки від поділу є розпізнавальниками помилок, але не вказують безпосередньо місце помилки в циклічному коді.
Ідея виправлення помилок базується на тому, що помилкова комбінація після певної кількості циклічних зрушень "підганяється" під залишок таким чином, що в сумі із залишком вона дає виправлену кодову комбінацію. Залишок при цьому є не що інше, як різницю між спотвореними і правильними символами, одиниці у залишку стоять якраз на місцях спотворених розрядів у підігнаній циклічними зрушеннями комбінації. Підганяють спотворену комбінацію до тих пір, поки число одиниць у залишку не буде дорівнює числу помилок у коді. При цьому, природно, число одиниць може бути або дорівнює числу помилок s,що виправляються цим кодом (код виправляє 3 помилки та в спотвореній комбінації 3 помилки), або менше s(код виправляє 3 помилки, а прийнятої комбінації 1 помилка).
Місце помилки в кодовій комбінації не має значення. Якщо k³ (n/2), то після певної кількості зрушень всі помилки виявляться в зоні “разового” дії багаточлена, що утворює, тобто достатньо отримати один залишок, вага якого W £ s, і цього буде достатньо для виправлення спотвореної комбінації.
Докладно процес виправлення помилок розглядається на прикладах побудови конкретних кодів.
Циклічний код
Циклічні коди відносяться до блокових систематичних кодів, в яких кожна комбінація кодується самостійно (у вигляді блоку) таким чином, що інформаційні 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 , використовуючи
так якАналогічним способом визначається
Завантаження...