Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Методи виявлення та виправлення помилок
Інформація про навчальний заклад
ВУЗ:
Інші
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2024
Тип роботи:
Курсова робота
Предмет:
Методи та засоби комп’ютерних інформаційних технологій
Частина тексту файла (без зображень, графіків і формул):
Зміст
Вступ………………………………………………………………...…….....…4
Методи боротьби з помилками……………………………………...…....…..5
Коди виявлення та виправлення помилок…………………………...……….6
Блокові коди та Лінійні коди загального вигляду…………………….….….7
Коди Хемінга………………………………………………………….…….….9
Лінійні циклічні коди…………………………………………………...…….12
Коди БЧХ………………………………………………………………….…..16
Висновки……………………………………………………………………....18
Список використаної літератури……………………………………….……19
Вступ
Виявлення помилок в техніці зв'язку - дія, спрямована на контроль цілісності даних при записі / відтворенні інформації або при її передачі лініями зв'язку. Виправлення помилок (корекція помилок) - процедура відновлення інформації після читання її з пристрою зберігання або каналу зв'язку.
Для виявлення помилок використовують коди виявлення помилок, для виправлення - коригувальні коди (коди, що виправляють помилки, коди з корекцією помилок, перешкодостійкі коди).
В даній курсовій роботі я хочу показати різні типи виявлення та виправлення помилок такі як: Блокові коди, Лінійні коди загального вигляду, Коди Хемінга та Лінійні циклічні коди Коди БЧХ.
Методи боротьби з помилками
У процесі зберігання даних і передачі інформації з мереж зв'язку неминуче виникають помилки. Контроль цілісності даних і виправлення помилок -важливі завдання на багатьох рівнях роботи з інформацією (в моделі OSI ).
У системах зв'язку можливі кілька стратегій боротьби з помилками:
виявлення помилок у блоках даних і автоматичний запит повторної передачі пошкоджених блоків - цей підхід застосовується в основному на канальному і транспортному рівнях;
виявлення помилок у блоках даних і відкидання пошкоджених блоків - такий підхід іноді застосовується в системах потокового мультимедіа, де важлива затримка передачі і немає часу на повторну передачу;
виправлення помилок ( англ. forward error correction) застосовується на фізичному рівні.
Коди виявлення та виправлення помилок
Коригувальні коди - коди, що служать для виявлення або виправлення помилок, що виникають при передачі інформації під впливом перешкод , а також при її зберіганні.(1)
Для цього при записі (передачі) у корисні дані додають спеціальним чином структуровану надлишкову інформацію ( контрольне число ), а при читанні (прийомі) її використовують для того, щоб виявити або виправити помилки. Природно, що кількість помилок, що можна виправити, обмежено і залежить від конкретного застосовуваного коду.
З кодами, що виправляють помилки, тісно пов'язані коди виявлення помилок. На відміну від перших, останні можуть тільки встановити факт наявності помилки в переданих даних, але не виправити її.
В дійсності, використовувані коди виявлення помилок належать до тих же класів кодів, що і коди, що виправляють помилки. Фактично, будь-який код, що виправляє помилки, може бути також використаний для виявлення помилок (при цьому він буде здатний виявити більше число помилок, ніж був здатний виправити).
За способом роботи з даними коди, що виправляють помилки поділяються на блокові, що ділять інформацію на фрагменти постійної довжини і обробні кожен з них окремо, і сверточних, що працюють з даними як з безперервним потоком.
Блокові коди та Лінійні коди загального вигляду
Нехай кодована інформація поділяється на фрагменти довжиною k біт, які перетворюються на кодові слова довжиною n біт. Тоді відповідний блоковий код зазвичай позначають / . (1)
При цьому число / називається швидкістю коду.
Якщо вихідні k біт код залишає незмінними, і додає n - k перевірочних,
такий код називається систематичним, інакше несистематичним.
Поставити блоковий код можна по-різному, в тому числі таблицею, де кожній сукупності з k інформаційних біт зіставляється n біт кодового слова. Однак, хороший код повинен задовольняти, як мінімум, наступним критеріям:
здатність виправляти якомога більшу кількість помилок,
як і менша надмірність,
простота кодування і декодування.
Неважко бачити, що наведені вимоги суперечать один одному. Саме тому існує велика кількість кодів, кожен з яких придатний для свого кола завдань.
Практично всі використовувані коди є лінійними . Це пов'язано з тим, що нелінійні коди значно складніше досліджувати, і для них важко забезпечити прийнятну легкість кодування і декодування.
Лінійний блоковий код - такий код, що безліч його кодових слів утворює k-мірне лінійне підпростір (назвемо його C) в n-мірному лінійному просторі , ізоморфне простору k-бітних векторів .
Це означає, що операція кодування відповідає множенню вихідного k-бітного вектора на невироджених матрицю G, звану породжує матрицею.
Нехай / - ортогональное підпростір по відношенню до C, а H - матриця, що задає базис цього підпростору. Тоді для будь-якого вектора / справедливо:
/
Мінімальна відстань і коригуюча здатність
Відстанню Хеммінга (метрикою Хемінга) між двома кодовими словами / і / називається кількість відмінних біт на відповідних позиціях:
/.
Мінімальна відстань Хемінга / є важливою характеристикою лінійного блокового коду. Вона показує наскільки «далеко» розташовані коди один від одного.Вона визначає іншу, не менш важливу характеристику - коригувальну здатність :
/.
Коригуюча здатність визначає, скільки помилок передачі коду
(типу /) Можна гарантовано виправити. Тобто навколо кожного кодового слова A маємо t-околиця A t, яка складається з усіх можливих варіантів передачі кодового слова A з числом помилок ( / ) Не більш t. Ніякі дві околиці двох будь-яких кодових слів не перетинаються один з одним, так як відстань між кодовими словами (тобто центрами цих околиць) завжди більше двох їхніх радіусів / .
Таким чином отримавши перекручену кодову комбінацію з A t, декодер приймає рішення, що вихідною була кодова комбінація A, виправляючи тим самим не більш t помилок.
Пояснимо на прикладі. Припустимо, що є два кодових слова A і B, відстань Хемінга між ними дорівнює 3. Якщо було передано слово A, і канал вніс помилку в одному бите, вона може бути виправлена, тому що навіть в цьому випадку прийняте слово ближче до кодового слова A, ніж до будь-іншому, і зокрема до B. Але якщо каналом були внесені помилки у двох бітах (в якихA відрізнялося від B) то результат помилковою передачі A виявиться ближче до B, ніж A, і декодер прийме рішення що передавалося слово B.
Коди Хемінга
Коди Хемінга - найпростіші лінійні коди з мінімальним відстанню 3, тобто здатні виправити одну помилку. Код Хемінга може бути представлений у такому вигляді, що синдром/ , Де / - Прийнятий вектор, буде дорівнює номеру позиції, в якій сталася помилка. Ця властивість дозволяє зробити декодування дуже простим.(2)
Загальний метод декодування лінійних кодів
Будь-який код (у тому числі нелінійний) можна декодувати за допомогою звичайної таблиці, де кожному значенню прийнятого слова / відповідає найбільш ймовірне передане слово / .Проте, даний метод вимагає застосування величезних таблиць вже для кодових слів порівняно невеликої довжини.
Для лінійних кодів цей метод можна істотно спростити. При цьому для кожного прийнятого вектора / обчислюється синдром / . Оскільки / , Де / - Кодове слово, а / - Вектор помилки, то / . Потім за допомогою таблиці по синдрому визначається вектор помилки, за допомогою якого визначається передане кодове слово. При цьому таблиця виходить набагато менше, ніж при використанні попереднього методу.
Код Хемінга - це код, який виявляє і виправляє одиничні помилки і виявляє подвійні помилки. Код Хемінга відноситься до систематичних кодів.
Систематичні коди - це коди, в яких інформаційні та надлишкові символи розташовані на певних наперед визначених місцях. Код Хемінга, як і будь-який (n,k)-код, містить k інформаційних і (n-k) надлишкових символів. Надлишкова частина коду будується таким чином, щоб при декодуванні можна було б встановити не лише факт наявності помилок в даній комбінації,але й вказати номер позиції, в якій помилка. Здійснити це можна шляхом багатократної перевірки прийнятої комбінації на парність. Кількість перевірок рівна кількості надлишкових символів. При кожній перевірці отримують двійковий контрольний символ. Якщо результат перевірки дає парне число, то контрольному символу присвоюється ”0”, якщо непарне - то “1”. В результаті всіх перевірок утворюється (n-k)-розрядне двійкове число, що вказує на номер спотвореного символа. Для виправлення помилки достатньо змінити значення символа, який стоїть у позиції ( перевід (n-k)двійкового розрядного числа у десяткове число) на протилежне.
Необхідна кількість надлишкових символів виводиться з формули:
/
Кодування
Кодується деяка інформація подана у вигляді у двійковій формі( послідовності нулів і одиниць) k1 k2 k3 k4 k5 k6 ... kn.
Нехай кодова довжина (довжина відрізків, на які ділиться потік) рівна 7 біт. Для того, щоб їх закодувати, потрібно на певні визначені місця внести надлишкові символи, які потім допоможуть декодувати цей потік.
В коді Хемінга надлишкові символи ставляться на тих позиціях в кодовій комбінації, що є степенями числа 2. Тобто, вихідною стрічкою буде потік
b1 b2 b3 b4 b5 b6 b7 b8 b9 b10 b11
r1 r2 k1 r3 k2 k3 k4 r4 k5 k6 k7
де r[i] - надлишкові символи, k[i] - інформаційні символи.
Складають кодову комбінацію з інформаційних і надлишкових символів, позиції надлишкових символів є степенями 2 (1, 2, 4, 8, 16, 32, …), а також при цьому позицію кожного символа(і інформаційних) у кодовій комбінації представляють у двійковій системі числення.
00001 b1 r1=k1 xor k2 xor k4 xor k5
00010 b2 r2=k1 xor k3 xor k4
00011 b3 k1
00100 b4 r3=k2 xor k3 xor k4
00101 b5 k2
00110 b6 k3
00111 b7 k4
01000 b8 r4=k5 xor k6 xor k7
01001 b9 k5
01010 b10 k6
01011 b11 k7
Надлишкові символи знаходять таким чином:
r1-це сума по модулю 2 (xor) тих k[i], в яких в першому розряді порядкового номера є "1";
r2-це сума по модулю 2(xor) тих k[i], в яких в другому розряді порядкового номера є"1";
r3- це сума по модулю 2 (xor) тих k[i], в яких в третьому розряді порядкового номера є "1";
r4- це сума по модулю 2 (xor) тих k[i], в яких в четвертому розряді порядкового номера є "1";
Приклад. Закодувати текст 1111101111 в коді Хемінга, кількість надлишкових і інформаційних дорівнює 9). Для цього потрібно текст поділити і додати надлишкові символи на потрібні позиції.
k1k2k3k4k5.k1k2k3k4k5
1 1 1 1 1 .0 1 1 1 1
Перше слово :
r1 = 1 xor 1 xor 1 xor 1 = 0
r2 = 1 xor 1 xor 1 = 1
r3 = 1 xor 1 xor 1 =1
r4 = 1
Друге слово :
r1 = 0 xor 1 xor 1 xor 1 = 1
r2 = 0 xor 1 xor 1 = 0
r3 = 1 xor 1 xor 1 = 1
r4 = 1 xor 1 xor 1 = 1
Результат : r1r2k1k2k3k4r4k5.r1r2k1r3k2k3k4r4k5
0 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1
Декодування
Для декодування записують систему рівнянь наступного вигляду:
r1 xor k1 xor k2 xor k4 xor k5 xor k7 xor… = С1 ,
r2 xor k1 xor k3 xor k4 xor k6 xor k7xor… = С2 ,
r3 xor k2 xor k3 xor k4 xor …=С3
r4 xor k5 xor k6 xor k7xor… = С4
Якщо кодове слово правильне, то система рівнянь виконується (тобто С1=С2=С3=С4=0). Якщо в кодовому слові є помилка, то права частина системи буде складатись не лише з нулів. Праву частину називають синдромом або розпізнавачем помилки. Щоб знайти помилку, необхідно прочитати синдром знизу вверх (С4С3С2С1) і перевести його в 10-ву систему числення- одержане число буде номером спотвореного символа.
Лінійні циклічні коди
Незважаючи на те, що декодування лінійних кодів значно простіше декодування більшості нелінійних, для більшості кодів цей процес все ще досить складний. Циклічні коди , крім більш простого декодування, володіють і іншими важливими властивостями.(3)
Циклічним кодом є лінійний код, що володіє наступною властивістю: якщо / є кодовим словом, то його циклічна перестановка також є кодовим словом.
Слова циклічного коду зручно представляти у вигляді многочленів. Наприклад, кодове слово / представляється у вигляді полінома / . При цьому циклічний зсув кодового слова еквівалентний множенню многочлена на x за модулем x n - 1.
Надалі, якщо не вказано інше, ми будемо вважати, що циклічний код є двійковим, тобто / можуть приймати значення 0 або 1.
Можна показати, що всі кодові слова конкретного циклічного коду кратні певному породжує полиному g (x). Породжує поліном є дільником x n - 1.
За допомогою породжує полінома здійснюється кодування циклічним кодом. Зокрема:
несистематичне кодування здійснюється шляхом множення кодованого вектора на g (x): v (x) = u (x) g (x);
систематичне кодування здійснюється шляхом «дописування» до кодованої слову залишку від ділення x n - k u (x) на g (x), тобто / .
Коди CRC
Коди CRC ( англ. cyclic redundancy check - циклічна надлишкова перевірка) є систематичними кодами, призначеними не для виправлення помилок, а для їх виявлення. Вони використовують спосіб систематичного кодування, викладений вище: «контрольна сума» обчислюється шляхом ділення x n - k u (x) на g (x). З огляду на те, що виправлення помилок не потрібно, перевірка правильності передачі може проводитися точно так само.
Таким чином, вид полінома g (x) задає конкретний код CRC. Приклади найбільш популярних поліномів:
/
В теорії циклічних кодів двійкові кодові комбінації представляють у вигляді поліномів. Показники степені х в поліномі відповідають номерам розрядів, коефіцієнти при х рівні нулю або одиниці в залежності від значення даного розряду.
Циклічні коди відносяться до блочних кодів і позначаються CRC(n, k), де k - кількість інформаційних символів, n - загальна кількість символів або довжина кодового слова: Кількість надлишкових символів r, що додаються до інформаційних з метою забезпечення корекції помилок:
r = n-k. (1)
Циклічні коди грунтуються на твірних поліномах. Ідея корекції помилок в циклічних кодах базується на тому, що дозволені комбінації коду діляться без залишку на деякий твірний поліном. Ні одна заборонена кодова комбінація не ділиться на твірний поліном без остачі.
Твірний поліном повинен відповідати таким вимогам:
степінь полінома повинна бути рівна кількості надлишкових символів r;
твірний поліном повинен бути не приводимий;
поліном (xn+1) повинен ділитися на твірний поліном без остачі.
Непрививодимими називаються поліноми, які не можуть бути представлені у вигляді добутку багаточленів нижчих степенів. Вони діляться без залишку тільки на себе або на одиницю. Перелік твірних поліномів наведено у додатку.
Розглянемо приклад циклічного коду CRC(7,3).
Виходячи з позначення CRC(7,3), маємо:
загальна довжина послідовності n = 7 біт;
довжина корисної інформації k = 3 біти;
довжина надлишкової послідовності r = n-k = 7-3 = 4 біти.
10000001|11101
11101 |
11010 |
11101 |
11101|
11101|
0|
10000001|10111
10111 |
11100 |
10111 |
10111|
10111|
0|
x4+x3+x2+x0
x4+x2+x1+x0
Для коду CRC(7,3) твірними поліномами можуть бути поліноми 11101 (x4+x3+x2+1) та 10111 (x4+x2+x1+1). Далі будемо розглядати перший твірний поліном g(x) = 1+x2+x3+x4.
Кодування
На основі твірного поліному g(x) = 1+x2+x3+x4 (11101) побудуємо схему код ера (рис.1).
Вертикальні зв’язки в кодері будуються за наступним принципом. Присутність і-го зв’язку на схемі відповідає присутності одинички при і-й степені у поліномі (при xi). При цьому 0 <= і <= r.
Рис. 1. Схема кодера для твірного поліному g(x) = 1+x2+x3+x4.
Степінь i
Коефіцієнт при xi
Опис зв’язку
0
1
Зв’язок зліва від a1 є
1
0
Зв’язок зліва від a2 відсутній
2
1
Зв’язок зліва від a3 є
3
1
Зв’язок зліва від a4 є
4
1
Останній зв’язок є
Треба зауважити, що перший та останній зв’язок є завжди.
На вхід кодера надходить k інформаційних символів, в даному прикладі - 3. При цьому за k кроків у регістрі a1,a2,a3,a4 утвориться послідовність надлишкових символів r коду CRC. r = 4.
Розглянемо формули, за якими можна визначити значення стану комірки aI на кожному кроці. Позначимо через aI стан комірки aI, через a’I стан комірки ai на попередньому кроці.
a1 = a’4k,
a2 = a’1,
a3 = ka’4a’2,
a4 = ka’4a’3.
Оскільки a’4k = a1 то формули для a3, a4 можна записати і так:
a3 = a1a’2,
a4 = a1a’3.
Декодування
Рис. 2. Схема декодера для твірного поліному g(x) = 1+x2+x3+x4
На основі твірного полінома будуємо схему декодера. Зв’язки у схемі будуються за тим самим принципом, що і у схемі кодера.
Формули для визначення a1,a2,a3,a4 тепер будуть мати такий вигляд:
a1=a’4+k, a2=a’1, a3=a’4+a’2, a4=a’4+a3
Декодер циклічного коду ділить прийняту кодову комбінацію на твірний поліном. Якщо у результаті в регістрах є лише нулі то має місце правильна передача або помилка що не виявляється.
Розглянемо роботу декодера:
У нашому випадку на вхід декодера поступає n=7 біт з них k=3 записуються у запам’ятовуючому регістрі. За n тактів (поки вона поступає) відбувається процес ділення на твірний поліном, якщо остача від ділення =0 то k біт з запам’ятовуючого регістру видаються користувачу.
Виправлення помилки(3)
Якщо після ділення (у декодері) у регістрах a1, a2, a3, a4 є хоча б одна одиничка то значить що при передачі послідовності була помилка. Для виправлення помилки застосовується таке правило:
На вхід декодера подається стільки нулів поки у регістрі не з’явиться комбінація 1000 (у нашому випадку) тобто у регістрі a1=1 а всі інші =0; номер такту при якому з’явилась комбінація 1000 і є номером спотвореного біту. Після цього залишається лише інвертувати спотворений біт і видати користувачу послідовність.
Коди БЧХ
Коди Боуза - Чоудхурі - Хоквінгема (БЧХ) є підкласом циклічних кодів. Їх відмітна властивість - можливість побудови коду БЧХ з мінімальним відстанню не менше заданого. Це важливо, тому що, взагалі кажучи, визначення мінімального відстані коду є дуже складне завдання.(4)
Математично полінома g (x) на множники в полі Галуа .
Коди корекції помилок Ріда - Соломона
Коди Ріда - Соломона - Недвійкова циклічні коди, що дозволяють виправляти помилки в блоках даних. Елементами кодового вектора є не біти, а групи бітів (блоки). Дуже поширені коди Ріда-Соломона, що працюють з байтами ( октетам ).
Математично коди Ріда - Соломона є кодами БЧХ.
Переваги і недоліки блокових кодів
Хоча блокові коди, як правило, добре справляються з рідкими, але великими пачками помилок, їх ефективність при частих, але невеликих помилки (наприклад, в каналі з АБГШ ), менш висока.
Оцінка ефективності кодів
Ефективність кодів визначається кількістю помилок, які той може виправити, кількістю надлишкової інформації, додавання якої вимагається, а також складністю реалізації кодування і декодування (як апаратної, так і у вигляді програми для ЕОМ ).
Кордон Хемінга і досконалі коди
Нехай є двійковий блоковий (n, k) код з коректує здатністю t. Тоді справедливо нерівність (зване кордоном Хемінга):
/
Коди, що задовольняють цьому кордоні з рівністю, називаються досконалими. До досконалим кодами відносяться, наприклад, коди Хеммінга . Часто застосовуються на практиці коди з великою коректує здатністю (такі, як коди Ріда - Соломона ) не є досконалими.
Енергетичний виграш
При передачі інформації по каналу зв'язку ймовірність помилки залежить від відношення сигнал / шум на вході демодулятора, таким чином при постійному рівні шуму вирішальне значення має потужність передавача. У системах супутникового і мобільного, а також інших типів зв'язку гостро стоїть питання економії енергії. Крім того, у певних системах зв'язку (наприклад, телефонного) необмежено підвищувати потужність сигналу не дають технічні обмеження.
Оскільки завадостійке кодування дозволяє виправляти помилки, при його застосуванні потужність передавача можна знизити, залишаючи швидкість передачі інформації незмінною.Енергетичний виграш визначається як різниця відносин с / ш при наявності і відсутності кодування.
Висновки
В даній курсовій роботі я оглянув декілька методів виявлення та виправлення помилок і можу сказати що досконалих методів немає, кожен з них є по своєму оригінальний. Я зрозумів принципи цих методів серед яких мені найбільше сподобався принцип Хемінга. Це найпростіший лінійний код, який здатний виправити одну або дві помилки. Звернувши увагу на лінійні циклічні коди я визначив що декодування лінійних кодів значно простіше декодування більшості нелінійних, для більшості кодів цей процес все ще досить складний.
Список використаної літератури
Блейхут Р. Теория и практика кодов, контролирующих ошибки = Theory and Practice of Error Control Codes — М.: Мир, 1986. — 576 с.
Мак-Вильямс Ф. Дж., Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки. М.: Радио и связь, 1979.
Морелос-Сарагоса Р. Методы, алгоритмы, применение. М.: Техносфера, 2006. — 320 с. — (Мир связи). —2000 экз.
http://ru.wikipedia.org
14.12.2013 01:12-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора