Ім'я файлу: Решетников Завдання 4.1.docx
Розширення: docx
Розмір: 96кб.
Дата: 19.03.2022
скачати

ЗАВДАННЯ No 4.1

«ЗАВАДОСТІЙКЕ КОДУВАННЯ»

Решетніков Богдан гр. ТК-91

Завдання

1. Ознайомитися з інформацією на тему «Завадостійке кодування»

(додаткова література).

2. Навести умови, яким повинна відповідати мінімальна кодова відстань для встановлення потрібного рівня здатності завадостійкого коду до виявлення та виправлення помилок.

3. Навести правила (алгоритми) формування наведених в «Плані заняття» завадостійких кодів та приклади їх побудови (5.1, 5.8, 5.9).

Відповідь:

2.Під завадостійкими кодами розуміють коди, що дозволяють виявляти або виявляти і виправляти помилки, які виникають у результаті впливу завад.

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

Всі завадостійкі коди можна розділити на два основних класи: блокові і неперервні (рекурентні або ланцюгові).

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

Нерівномірні завадостійкі коди не одержали практичного застосування через складність їх технічної реалізації.

Як уже відзначалося, завадостійкість кодування забезпечується за рахунок внесення надмірності в кодові комбінації. Це значить, що з n символів кодової комбінації для передачі інформації використовується k < n символів. Отже, із загального числа No=2n можливих кодових комбінацій для передачі інформації використовується тільки N = 2k комбінацій. Відповідно до цього вся множина No=2n можливих кодових комбінацій поділяється на дві групи. У першу групу входить множина N = 2k дозволених комбінацій, друга група містить у собі множину (No - N) = 2n-2k заборонених комбінацій.

3. Код з перевіркою на парність є найбільш поширеним кодом, який використовується для виявлення поодиноких помилок і всіх помилок непарної кратності. Код містить ( n – 1 ) інформаційних та один перевірочний елемент і позначається як ( n , n – 1 ) - код.

Перевірочний елемент визначається як сума за модулем 2 всіх інформаційних елементів: тобто кодова комбінація коду утворюється доповненням комбінації k - \елементного первинного коду одним елементом таким чином, щоб кількість одиниць у новому n - розрядному ( n = k + 1 ) коді була парною. Код має кодову відстань dmin = 2.

Для виявлення помилки на приймальному боці виконують перевірку на парність всієї прийнятої кодової комбінації за допомогою визначення кодового синдрому де – прийняті на приймальному боці відповідно інформаційні та перевірочний елементи.

Вважається, що при s1 = 0 помилки в комбінації нема, при s1 = 1 – помилка є. Код виявляє всі помилки непарної кратності.

Надмірність коду R = 1 – k / ( k + 1 ) = 1 / ( k + 1 ).

Задача 1


Закодувати комбінацію 1110101 двійкового простого коду ( k = 7 ) двійковими кодами, що виявляють помилки: з перевіркою на парність і простим повторенням. Виявити однократну помилку та порівняти надмірності цих кодів.

Розв’язання. Кодова комбінація коду з перевіркою на парність буде мати вигляд: A 1 = 11101011, а коду з простим повторенням – А2 = 11101011110101.

Нехай у комбінації коду з перевіркою на парність виникла однократна помилка, вектор якої Е 1 = 00000100. Тоді сума А1 Е1 = 11101111.

У цьому разі сума за модулем 2 елементів одержаної на приймальному боці кодової комбінації дорівнює 1, тобто непарна, що вказує на наявність у ній помилки. Надмірність коду R1 = 1 – 7 / 8 = 0,125.

Нехай в комбінації коду з простим повторенням вектор однократної помилки буде Е2 = 00000100000000. Тоді сума А 2 Е2 = 11101111110101. Порівнюючи першу і другу частини кодової комбінації ( одержуючи їх суму за модулем 2 ), отримаємо остачу, яка не буде дорівнювати нулю ( 1110111 1110101 = 0000010 ), що вказує на наявність помилки у прийнятій кодовій комбінації. Надмірністькоду R2 = 0,5. Таким чином R2 > R1.

Код Бергера є найбільш поширеним з несистематичних кодів. У такому коді перевірочні елементи, які дописуються у кінці первинної кодової комбінації, – це інвертований запис двійкового числа, яким записується сума одиниць у кодовій комбінації k – елемент-ного первинного коду, що кодується кодом Бергера. При цьому число r перевірочних елементів визначається як найменше ціле, для якого виконуються умови r log 2 ( k + 1 ). Так, наприклад, при k = 8, отри-маємо log 2 ( 8 + 1 ) = log 2 9 = 3,16993, тобто r = 4.

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

Надмірність коду R = 1 – r / n.

Задача 2


Закодувати комбінацію 1001111 двійкового простого коду ( k = 7 ) двійковими кодами, що виявляють помилки: інверсним ( Ба-уера ) та Бергера. Виявити однократну помилку і порівняти надмірності цих кодів.

Розв’язання. Кодова комбінація інверсного коду, з огляду на непарну кількість одиниць у первинній комбінації, буде мати вигляд: А1 = 10011110110000, а коду Бергера – А2 = 1001111010 (тому що, r = log2 ( 7 + 1 ) = log 2 8 = 3, 510 = 1012, інверсія 101 010 ).

Нехай у комбінації інверсного коду виникла однократна помилка, вектор якої Е1 = 00000100000000.Тоді сума А1 Е1 = 10011010110000. У декодері підраховується кількість одиниць у першій половині кодової комбінації, яка у даному разі дорівнює 4. Це означає, що друга половина комбінації повинна прийматися у позитиві. Порівнюючи першу і другу ( неінвертовану ) частини прийнятої кодової комбінації, одержимо незбіг у шести розрядах, що вказує на наявність у ній помилки. Надмірність коду R1 = 0,5.

Нехай у комбінації коду Бергера виникла однократна помилка, вектор якої Е2 = 0010000000. Тоді сума А2 Е2 = 1011111010.

При прийманні у декодері підраховується кількість одиниць в інформаційній частині кодової комбінації, яка дорівнює шести. У двійковій формі запису це буде 110, інвертуючі яку отримуємо – 001. Порівнюємо перевірочні елементи прийнятої кодової комбінації та одержані у декодері шляхом обчислення кількості одиниць в інформаційній частині прийнятої комбінації. Їх незбіг ( 010 – 001 ) вказує на наявність помилки у прийнятій кодовій комбінації. Надмірність коду R2 = 0,3. Таким чином R1 > R2.

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

(n–1) і менше, що діляться на деякий багаточлен G(x) степеня

r = n–m, що є співмножником двочлена xn + 1.

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

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



де n–довжина коду;

–коефіцієнти з поля GF(q).

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

Циклічні коди прості в реалізації і при невисокій надмірності мають хороші властивості виявлення спотворень. Циклічні коди поширені як у техніці зв’язку, так і в комп’ютерних засобах зберігання інформації. У зарубіжних джерелах циклічні коди зазвичай називають перевіркою циклічним надмірним кодом (CRC, Cyclic Redundancy Check).

Розглянемо даний клас кодів докладніше. Як уже згадувалося, назва циклічних кодів пов’язана з тим, що кожна кодова комбінація, одержана шляхом циклічної перестановки символів, також належить коду. Так, наприклад, циклічні перестановки комбінації 1000101 будуть також кодовими комбінаціями 0001011, 0010110, 0101100 і т.д.

Подання кодових комбінацій у вигляді багаточленів F(x) дозволяє встановити однозначну відповідність між ними і звести дії над комбінаціями до дії над багаточленами.

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

,

то багаточлен, відповідає йому:

.

Складання двійкових багаточленів зводиться до складання по модулю 2 коефіцієнтів при однакових степенях змінної x. Множення здійснюється за звичним правилом множення степеневих функцій, проте одержані коефіцієнти при даному степені складаються по модулю 2. Розподіл здійснюється як звичний розподіл багаточленів, при цьому операція віднімання замінюється операцією складання по модулю 2. Циклічна перестановка кодової комбінації еквівалентна множенню полінома F(x) на x із заміною на одиницю змінної зі степенем, що перевищує степінь полінома.

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

Ідея побудови циклічного коду (n, m) зводиться до того, що поліном Q(x), який подає інформаційну частину кодової комбінації, потрібно перетворити в поліном F(x) степені не більше (n–1), який без залишку ділиться на породжувальний поліном G(x) (багаточлен, що не приводиться) степені k = n - m. Розглянемо послідовність операцій побудови циклічного коду.

Подаємо інформаційну частину кодової комбінації завдовжки m у вигляді полінома Q(x). Для одержання k позицій під контрольні символи множимо Q(x) на одночлен xk і одержуємо Q(x)∙xk.

Ділимо поліном Q(x)∙xk на породжувальний поліном G(x) степені k, при цьому одержуємо результат розподілу С(x) такої ж степені, що і Q(x).


,

де R(x) – залишок від розподілу Q(x)∙xk на G(x).

Помноживши обидві частини на G(x), одержимо



Поліном F(x) ділиться без залишку на G(x), тобто є дозволеною комбінацією циклічного (n, m) коду.

Приклад циклічного коду (9, 5) з породжувальним поліномом

.

Як інформаційну частину кодової комбінації візьмемо поліном

Q(x)= x4+ x2+ x +1 = 10111.

Множення Q(x) на xk еквівалентне підвищенню степені багаточлена на k.

F(x)= Q(x)∙xk = = .

Формування перевірочної групи здійснюється в процесі розподілу Q(x)∙xk на G(x).

Внаслідок розподілу одержуємо результат С(x)= x4 + x2 =

= 10100 і залишок від розподілу R(x)= x3 + x2 = 1100. Для отримання дозволеної кодової комбінації залишок (перевірочна група) поміщається на місце «порожніх» розрядів Q(x)∙xk, тобто

F(x)= =

= 101111100.

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

Виявлення помилок при циклічному кодуванні зводиться до розподілу прийнятої кодової комбінації на той же породжувальний поліном, який використовувався для кодування. Якщо помилок у прийнятій комбінації немає (або вони такі, що передану комбінацію перетворюють на іншу дозволену), то розподіл на породжувальний поліном здійснюється без залишку. Наявність залишку свідчить про присутність помилок.

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

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

Для виправлення пакетів спотворень (три і більше помилки) розроблені коди Файра, Ріда-Соломона та ін. Останні можуть виправляти кілька пакетів помилок.
скачати

© Усі права захищені
написати до нас