Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформаційні моделі сигналів - Частина2
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Комп’ютерні науки
Кафедра:
Не вказано
Інформація про роботу
Рік:
2006
Тип роботи:
Конспект лекцій
Предмет:
Методи та засоби комп’ютерних інформаційних технологій
Частина тексту файла (без зображень, графіків і формул):
Розділ 2
КОДУВАННЯ ПОВІДОМЛЕНЬ
2.1. Основні поняття і визначення
Будь-яке відображення матеріального світу, яке може бути зафіксоване живою істотою чи приладом, несе в собі інформацію.
Відображення діяльності людини або розуміння оточуючого світу може бути представлене в формалізованому вигляді, наприклад, в вигляді наборів букв або цифр. Такі формалізовані набори називають даними. Дані, отримані від джерела інформації, називають повідомленнями.
Повідомлення передаються за допомогою сигналів. Взагалі сигналом може бути будь-яка зміна початкового стану об’єкта, яка в стані викликати реакцію людини або приладу. Сигнали можуть бути зорові, звукові, електричні, радіосигнали і т.п. Сигнали можуть бути взаємозв’язані в просторі і часі. Сигнали є матеріальними носіями повідомлень при передачі від джерела.
Для того щоб сигнали були однозначно зрозумілі, їх необхідно утворювати по правилах, які строго зафіксовані на протязі всього часу передачі даної групи повідомлень.
Правило (алгоритм), яке ставить у відповідність кожному конкретному повідомленню строго визначену комбінацію різних символів (або відповідних сигналів) називається кодом, а процес перетворення повідомлень в комбінацію різних символів, або відповідних сигналів - кодуванням.
Послідовність символів, яка в процесі кодування присвоюється кожному із множини повідомлень, називається кодовим словом.
Символи за допомогою яких записане повідомлення, утворюють первинний алфавіт, а символи, за допомогою яких повідомлення трансформується в код - вторинний алфавіт.
Процес відновлення змісту повідомлення по даному коду називається декодуванням. Необхідною умовою декодування є взаємно однозначна відповідність кодових слів у вторинному алфавіті закодованим символам первинного алфавіту.
Кодування використовується для досягнення декількох цілей. Перша з них полягає в тому, щоб представити повідомлення в такій системі символів, яка б забезпечувала простоту і надійність, апаратну реалізацію інформаційних пристроїв і їх необхідну ефективність.
Друга мета кодування - забезпечення найкращего узгодження властивостей джерела повідомлення з властивостями каналу зв’язку. Шляхом такого узгодження досягають виграшу в часі передачі, тобто підвищення ефективності системи.
Накінець, при наявності завад кодування може забезпечити високу достовірність передачі або обробки інформації.
Кодування змінює структуру сигналу, але не повинно змінювати кількість інформації в первинному повідомленні.
Елементарними сигналами, які відображують символи кодової комбінації, в технічних інформаційних системах звичайно служать одиночні імпульси струму (відеоімпульси) або радіоімпульси. Ці сигнали повинні розрізнятися по якихось параметрах, що називаються кодовими ознаками.
В якості кодових ознак використовуються такі параметри як величина, полярність, час (тривалість або фаза імпульсів), частота заповнення імпульсу і т.п.
Кількість символів, які складають кодову комбінацію, називається значністю або довжиною коду (n). Кількість кодових ознак, що використовуються в кодових комбінаціях, називається основою коду (m). На рис. 2.1 наведені приклади кодів із значністю n=5 і основою m=3. На рис. 2.1 а) у якості кодової ознаки прийнято рівень імпульсу. На рис. 2.1 б) – тривалість імпульсу.
\EMBED Visio.Drawing.6
Рис. 2.1. Приклад кодової комбінації з різними кодовими ознаками
Коди, у яких повідомлення представлені комбінаціями з неоднаковою кількістю символів називаються нерівномірними, або некомплектними. Типічним представником нерівномірних кодів є код Морзе. Нерівномірні коди можуть забезпечити високу ефективність кодування, зменшення сумарної довжини повідомлень і високу швидкість передачі даних. Однак, потрібно приймати до уваги, що нерівномірні коди мають низьку завадостійкість. Для їх декодування потрібен розділювач, або реалізація властивості префіксності.
Коди, у яких повідомлення представлені комбінаціями з однаковою довжиною називаються рівномірними, або комплектними. Наприклад, коди ASCII мають однакову довжину n=8.
За числом різних символів (m) в кодових комбінаціях розрізняють коди:
одиничні m=1;
двійкові m=2;
багатопозиційні m>2.
В одиничному коді використовують однакові символи. Кодові комбінації розрізняються лише кількістю символів. Такі коди мають низьку завадостійкість, по своїй суті нерівномірні і використовуються лише як проміжні у різноманітних вимірювальних системах
Найчастіше використовуються двійкові коди. Двійкові цифри (0,1) реалізуються релейними елементами з двома стійкими станамами. До такого типу елементів належить більшість електромагнітних, електронних, магнітних та інших типів безконтактних реле. Крім того, слід прийняти до уваги простоту збереження інформації і виконання арифметичних і логічних операцій при двійковому кодуванні.
Багатопозиційні коди не знайшли широкого застосування в інформаційних системах.
По формі представлення в каналі зв’язку розрізняють послідовні і паралельні коди. При послідовній формі елементарні сигнали, які складають кодову комбінацію, посилаються в канал пердачі послідовно в часі.
При паралельній формі елементарні сигнали посилаються одночасно по декількох електричних лініях, що дає можливість підвищити швидкість передачі даних.
За можливістю виявлення і виправлення помилок розрізняють прості (примітивні) і коректуючі. В простих кодах помилка у прийомі хоча б одного елемента кодової комбінації приводить до неправильної реєстрації переданого повідомлення. Коректуючі коди дають можливість виявляти і усувати помилки в кодових комбінаціях.
За законами кодоутворення коди можна поділити на два класи: комбінаторні (нечислові) і арифметичні (числові).
Комбінаторні коди будуються за законами теорії сполучень. Прикладом таких кодів є код по закону комбінацій. В цьому коді із m різних символів утворюються кодові комбінації із n<n символів. Довжина коду постійна і дорівнює n, можливе число кодових комбінацій EMBED Equation.3 . Наприклад код по закону комбінацій може утворити такі комбінації із трьох елементів a, b, і c по два елементи: ab, ac, bc
Арифметичні коди основані на відомих системах числення. Переважно використовуються у інформаційних системах.
2.2. Рівномірні прості цифрові коди.
Системи числення, на основі яких можуть будуватися цифрові коди, діляться, як відомо, на непозиційні і позиційні. З непозиційних систем можна навести як приклад римську систему числення. Значення символу в цих системах не залежить від його положення у ряді символів повідомлення.
Найпоширенішим при кодуванні в даний час є позиційний принцип утворення системи числення. При такому принципі значення кожного символу залежить від його положення - позиції у ряді символів, що утворюють число. Значення одиниці кожного наступного розряду більше від значення одиниці попереднього розряду в m раз, де m - основа системи числення. При цьому будь-яке n-разрядное число N із основою m може бути представлене у вигляді суми
EMBED Equation.3 (2.1)
де EMBED Equation.3 - значення розрядного коефіцієнта і-го розряду.
Число можливих значень розрядного коефіцієнта кожного розряду рівне основі вибраної системи числення.
Як приклад розглянемо чотирьохрозрядне десяткове число 4752. Це число може бути представлено у вигляді суми
EMBED Equation.3
При довжині коду n і основі m число різних кодових комбінацій буде
EMBED Equation.3 (2.2)
Найчастіше використовується двійкова система числення. Для двійкової системи числення запис коду має такий вигляд:
EMBED Equation.3, EMBED Equation.3. (2.3)
Максимально можливе число кодових комбінацій визначається виразом
EMBED Equation.3 (2.4)
Двійковий код, який широко використовується при передачі, зберіганні і обробці інформації, незручний при введенні і виведенні інформації, оскільки оператору важко оперувати з незвичними двійковими числами. Крім того, запис чисел в двійковій системі числення громіздкий. Тому крім двійкової отримали розповсюдження системи з основою, рівною цілому ступеню двійки (вісімкова, шістнадцяткова), які з одного боку, легко зводяться як до двійкової, так і до десяткової, а з іншого - дають більш компактний запис.
Для позначення будь-якого числа у вісімковій системі числення використовується вісім цифр: 0, 1,2, 3, 4, 5, 6, 7. Переведення чисел з вісімкової системи в двійкову зводиться до заміни кожної вісімкової цифри рівним їй трьохрозрядним двійковим числом. Наприклад, для вісімкового числа 3275 одержуємо:
3 2 7 5
011 010 111 101
Для представлення шістнадцяткових цифр використовуються цифри від 0 до 9 і букви латинського алфавіту від А до F. Переклад чисел з шістнадцяткової системи в двійкову здійснюється шляхом заміни кожної шістнадцяткової цифри чотирьохрозрядним двійковим числом. Позначення шістнадцяткової цифри і представлення їх двійковими числами ілюструються табл. 2.1.
Таблиця 2.1
Двійкове зображення шістнадцяткових цифр
2.3. Складені коди
Складені коди базуються системах числення, що мають дві і більше основ. При такому кодуванні числа, задані в системі з деякою основою q, зображаються за допомогою цифр іншої системи числення з основою р <q.
Серед складених кодів найбільше застосування знайшли двійково-десяткові коди. Такі коди звичайно використовуються як проміжні при перевеленні десяткових чисел в двійкові і навпаки, наприклад при введенні в обчислювальну машину даних, представлених в десятковій системі, або при виводі з машини інформації для реєстрації в десятковому коді.
В двійково-десятковому коді основною системою числення є десяткова. Проте кожна цифра десяткового числа записується у вигляді чотирьохрозрядного двійкового числа (тетради). Для фіксації цифр десяткового числа найбільше практичне застосування знайшли чотирьохелементні двійкові вагові коди 8-4-2-1, 7-4-2-1, 5-1-2-1 і 2-4-2-1. Цифри в назві коду виражають вагу одиниць у відповідних двійкових розрядах.
В табл. 2.2 приводиться запис десяткових цифр різними типами чотирьохелементних двійкових кодів.
Таблиця 2.2
Запис десяткових цифр із різними вагами розрядів в тетраді
Оскільки за допомогою чотирьох двійкових розрядів можна утворити 16 різних комбінацій, а використовується тільки 10, то двійково-десятковий код володіє деякою надлишковістю. До того ж у вагових кодах деякі цифри мають два різні допустимі зображення.
2.4. Рефлексні (відбиті коди)
В простому двійковому коді при переході від зображення одного числа до зображення сусіднього старшого або сусіднього молодшого числа може відбуватися одночасна зміна цифр в декількох розрядах. Як випливає з табл. 2,3 при переході від двійкового зображення числа 3 до зображення числа 4 відбувається одночасна зміна цифр в трьох розрядах, а при переході від зображення числа 7 до зображення числа 8 відбувається одночасна зміна цифр в чотирьох розрядах. Це може стати джерелом значних похибок при деяких способах кодування неперервних повідомлень, наприклад при перетворенні кута повороту валу в двійковий код. Особливістю таких перетворювачів є те, що під час переходу зображення одного числа до зображення наступного числа (більшого або меншого) може мати місце неоднозначність відліку в тих розрядах, де відбувається зміна цифр. Наприклад, при переході від зображення числа 7 до зображення числа 8 відбувається зміна цифр у всіх розрядах, тобто може мати місце неоднозначність відліку в будь-якому розряді і навіть відразу у всіх розрядах. Внаслідок цього, зокрема, може бути такий випадок, коли замість числа 1000 буде зафіксовано число 1111, тобто матиме місце неприпустимо велика похибка
Таблиця 2.3
Зображення десяткових цифр в коді Грея
Для усунення цього явища використовуються спеціальні двійкові коди, у яких при переході від зображення одного числа до зображення наступного сусіднього числа змінюється значення цифри тільки одного розряду. Внаслідок цього похибка за рахунок неоднозначності відліку не перевищує одиниці числа, що зображається. До числа таких кодів відноситься код Грея, який називають також рефлексним (відбитим) кодом (табл. 2.3).
Код Грея є непозиційним кодом, вага одиниці не визначається номером розряду. В цьому коді можна виділити осі симетрії (осі “віддзеркалення”), відносно яких спостерігається ідентичність елементів в деяких розрядах. Так, наприклад, має місце симетрія відносно осі, проведеної між числами 7 і 8. В комбінаціях, симетричних щодо цієї осі, ідентичні три символи молодших розрядів. Відзначена особливість послужила підставою для введення терміну “рефлексний код”.
EMBED Visio.Drawing.6
Схеми переведення із двійкової системи в код Грея і (а) і з коду Грея у двійковий (б)
2.5. Завадостійке кодування. Класифікація завадостійих кодів
Завадостійкі коди - один із найефективніших засобів забезпечення високої вірності передачі дискретної інформації. Бурхливий розвиток теорії завадостійкого кодування пов'язаний з впровадженням автоматизованих систем, у яких обробка інформації, здійснюється без участі людини. Використання для обробки інформації комп’ютерів ставить дуже високі вимоги до вірності передачі повідомлень.
К. Шеннон сформулював теорему для випадку передачі дискретної інформації по каналу з завадами (див. п. 1.5), яка стверджує, що імовірність помилкового декодування прийнятих сигналів може бути забезпечена як завгодно малою вибором відповідного способу кодування сигналів. В теоремі Шеннона не говориться про те, як потрібно будувати завадостійкі коди. Проте в ній вказується на принципову можливість кодування, при якому може бути забезпечений як завгодно висока вірність передачі. Це стало стимулом до розробки завадостійких кодів.
Під завадостійкими кодами розуміють коди, що дозволяють виявляти або виявляти і виправляти помилки, що виникають в результаті впливу завад.
Завадостійкість кодування забезпечується за рахунок введення надлишковості в кодові комбінації, тобто за рахунок того, що не всі символи в кодових комбінаціях використовуються для передачі інформації.
EMBED Visio.Drawing.6
Рис.2.3. Класифікація коректуючих кодів
Всі завадостійкі коди можна розділити на два основні класи: блокові і неперервні (рекурентні або ланцюгові) (рис. 2.3).
В блокових кодах кожному повідомленню (або елементу повідомлення) ставиться у видповідність кодова комбінація (блок). Блоки кодуються і декодуються окремо один від одного.
Блокові коди можуть бути рівномірними, коли довжина кодових комбінацій n постійна, або нерівномірними, коли n змінне.
Нерівномірні завадостійкі коди не отримали практичного застосування через складність їх технічної реалізації.
В неперервних кодах введення надлишковості в послідовність вхідних символів здійснюється без розбиття її на оокремі блоки. Процеси кодування і декодування в неперервних кодах мають також неперервний характер.
Як блокові, так і неперервні коди залежно від методів внесення надлишковості підрозділяються на розділені і нерозділені. В розділених кодах чітко розмежована роль окремих символів. Одні символи є інформаційними, інші є перевірними і служать для виявлення і виправлення помилок. Розділені блокові коди називаються звичайно n, k-кодами, де n - довжина кодових комбінацій, k число інформаційних символів в комбінаціях.
Нерозділtні коди не мають чіткого розділення кодової комбінації на інформаційні і перевірочні символи. Цей клас кодів поки що нечисленний.
Розділені блокові коди діляться, у свою чергу, на несистематичні і систематичні. Несистематичні розділені коди будуються таким чином, що перевірочні символи визначаються як сума підблоків довжини L, на які розділяється блок інформаційних символів.
Більшість відомих розділtних кодів складають систематичні коди. У цих кодах перевірні символи визначаються в результаті проведення лінійних операцій над певними інформаційними символами. Для випадку двійкових кодів кожний перевірний символ вибирається таким, щоб його сума по модулю два з певними інформаційними символами стала рівною нулю. Декодування зводиться до перевірки на парність певних груп символів. В результаті таких перевірок дається інформація про наявність помилок, а у разі потреби - про позицію символів, де є помилки.
2.6. Основні принципи завадостійкого кодування
При подальшому розгляді завадостійких кодів вважатимемо їх блоковими і рівномірними. Для з'ясування ідеї завадостійкого кодування розглянемо двійковий код, що знайшов на практиці найширше застосування.
Нагадаємо, що двійковий код - це код з основою m=2.
Кількість розрядів n кодової комбінації називається довжиною, або значністю коду. Символи кожного розряду можуть приймати значення 0 або 1. Кількість одиниць в кодовій комбінації будемо називати вагою кодової комбінації w. Наприклад, кодова комбінація 1000111 характеризується значністю n=7 і вагою w=4.
Ступінь відмінності кодових комбінацій одна від одної характеризується відстанню між кодами. Відстань - кількість розрядів, які відрізняються в кодових комбінаціях.
Відстань визначається сумуванням по модулю 2 розрядів кодових комбіна-цій.
EMBED Visio.Drawing.6
Отримана в результаті сумування нова кодова комбінація має вагу w = 3. Отже, відстань між цими кодовими комбінаціями d = 3
Помилки за рахунок завад виявляються в тому, що в одному або декількох розрядах нулі переходять в одиниці і, навпаки, одиниці в нулі. В результаті створюється нова - хибна комбінація.
Якщо похибка виникає тільки в одному розряді кодової комбінації, то її називають однократною. При виникненні похибок в двох, трьох і т.д. розрядах їх називають двократними, трикратними і т.д. Експериментальні дані свідчать, що похибки символів при передачі по каналах зв’язку групуються в пачки.
Місце виникнення похибки вказуєтья вектором похибки . Це n-розрядна комбінація одиниці в якій вказують місце перекручених розрядів. Вага вектора похибки вказує кратність похибки. Вага вектора помилки характеризує кратність помилки. Сума по модулю 2 перекрученої кодової комбінації і вектора помилки дає правильну комбінацію.
Завадостійкість забезпечується надлишковістю в кодовій комбінації. Це значить, що з n символів кодової комбінації для передачі інформації використовуються лише k<n символів. Загальна кількість комбінацій EMBED Equation.3 . Із них для передачі інформації використовується лише EMBED Equation.3 .
EMBED Visio.Drawing.6
Рис. 2.4. Можливі переходи при передачі кодів по каналу із завадами
Множина всіх прийнятих комбінацій ділиться на множину дозволених (N) і заборонених EMBED Equation.3 . Можливі переходи при передачі кодів по каналу із завадами наведені на рис. 2.4. Взагалі N комбінацій при передачі можуть трансформуватися в NNo комбінацій, з них:
N – вірних. На рисунку показані стрілками;
N(N-1) – хибні переходи в дозволені. Показані штриховими лініями. Ці переходи не виявляються;
N(No-N) - переходи в заборонені. Показані тонкими лініями. Виявляються завжди.
Частка помилок, які виявляються
EMBED Equation.3. (2.4)
Для використання коду для виправлення помилок множину заборонених ділять на N підмножин що не перетинаються. Тоді похибки виправляються в No-N випадках. На рис. 2.4 такі підмножини позначені горизонтальними фігурними дужками. Доля виправлених в загальній кількості виявлених:
EMBED Equation.3. (2.5)
2.7. Кодова відстань і виправляюча спроможність коду
Найменша відстань між дозволеними кодовими комбінаціями dmin -дуже важлива характеристика коду, оскільки якраз вона характеризує його виправляючу спроможність.
Розглянемо це на конкретних прикладах.
Нехай потрібно побудувати код, який виявляє всі помилки з кратністю t і нижче. Побудувати такий код - значить з множини No можливих комбінацій вибрати N дозволених так, щоб будь-яка з них в сумі по модулю 2 з будь-яким вектором помилок з вагою wi t не дала б в результаті ніякої дозволеної комбінації.
Очевидно, що для цього необхідно, щоб
dmin t+1
Розглянемо код зі значністю n=3. Всі можливі комбінації даються в таблиці 2.4:
Таблиця 2.4
Всі можливі комбінації коду із значністю n =3
Матриця відстаней має вигляд (табл 2.5):
Таблиця 2.5
Матриця відстаней трьохрозрядного коду
Для того, щоб код виявляв однократні помилки з No=8 комбінацій, необхідно вибрати як дозволені такі, відстань між якими була б не менша d=2.
Можна вибрати
EMBED Equation.3 =000; EMBED Equation.3 =011; EMBED Equation.3 =101; EMBED Equation.3 =110.
Для двократних помилок найменша кодова відстань повинна бути dmin=3. При цьому як дозволені можна вибрати: EMBED Equation.3 =000; EMBED Equation.3 =111.
Справедлива очевидна умова:
EMBED Equation.3 . (2.6)
Тепер побудуємо код для коректування однократних помилок. Виберемо першу комбінацію EMBED Equation.3 . Вектори помилок при однократних перекрученнях: EMBED Equation.3 , тобто комбінація може перейти в одну із можливих, які ми повинні розглядати як заборонені: EMBED Equation.3 . У випадку прийому однієї з цих комбінацій виноситься рішення, що передана EMBED Equation.3 .
Виберемо другу дозволену комбінацію з d=2, наприклад, EMBED Equation.3 . Для неї заборонені комбінації: EMBED Equation.3 . Множини заборонених комбінацій перетинаються і не можна встановити при прийомі А2 або А3, яка комбінація була передана - А1 чи А4.
Якщо другою дозволеною комбінацією вибрати EMBED Equation.3 з відстанню d=3, то підмножина заборонених комбінацій буде така: EMBED Equation.3 . Значить у цьому випадку підмножини заборонених комбінацій не перетинаються і при d=3 може бути забезпечене усунення всіх однократних помилок. Взагалі при кратності помилок кодова відстань повинна задовільняти умову:
EMBED Equation.3 . (2.7)
Аналогічно можна встановити, що для виправлення всіх помилок з кратністю і одночасного виявлення всіх помилок кратністю t (t) кодова відстань повинна задовільняти умову:
EMBED Equation.3 . (2.8)
Сказане стосується всіх блочних рівномірних кодів, незалежно від способу їх утворення. Єдина необхідна умова N<No. Вибір дозволених комбінацій може бути різним і залежить від нашої волі. Розбиття коду повинно задовільняти вимогам до коректуючої здатності.
Так, наприклад, природно вимагати, щоб середня імовірність помилок була найменшою. Якщо помилки в кожному символі незалежні, то імовірність помилки спадає з підвищенням їх кратності, і для зменшення середньої ймовірності помилки в першу чергу слід виправляти помилки нижчої кратності. Якщо статистика помилок така, що навпаки, більшу ймовірність мають помилки високої кратності, то розбиття слід вибирати так, щоб виявлялися і коректувалися помилки високої кратності.
2.8. Побудова кодів з заданою виправляючою здатністю.
До цього часу ми вважали даною розрядність коду n. Підвищення коректуючої здатності досягалося за рахунок зменшення множини дозволених комбінацій N при збереженні значності. На практиці коди будуються в оберненому порядку: спочатку вибирається кількість інформаційних символів k, виходячи з об’єму алфавіту джерела, а після того забезпечується необхідна коректуюча здатність коду за рахунок додавання надлишкових розрядів.
Нехай відомий об’єм алфавіту джерела N. Необхідна кількість інформаційних символів
EMBED Equation.3
Нехай також відома повна кількість помилок Е, яку необхідно виправити. Задача полягає в тому, щоб по N і E (кількість векторів помилок) визначити значність коду n, яка забезпечує необхідну коректуючу здатність.
Повне число помилкових комбінацій рівне EN. Код може виправити не більше No-N комбінацій. Необхідна умова для виправлення всіх помилок має вигляд:
EN No-N,
звідки отримаємо
EMBED Equation.3
або
EMBED Equation.3. (2.9)
Формула (2.) є небхідною умовою для вибору значності коду n.
У випадку однократних помилок однократних помилок
EMBED Equation.3 .
Відповідно формула (2.) набуде вигляду
EMBED Equation.3 . (2.10)
При цьому для виправлення всіх помилок необхідно, щоб dmin3.
При побудові коду доцільно користуватися таблицею типу табл. 2.6
таблиця 2.6
Верхня оцінка об’єму алфавіту від значності коду
Якщо необхідно забезпечити усунення всіх помилок кратності від 1 до r, то необхідно врахувати, що число можливих і-кратних помилок - EMBED Equation.3 . Загальна кількість помилок EMBED Equation.3.
Тоді залежність (2.9) набуде вигляду
EMBED Equation.3. (2.11)
Умова є нижньою оцінкою довжини коду. Ця ж умова є верхньою оцінкою для N (або k), тобто числа можливих дозволених комбінацій при заданій довжині коду, що забезпечує виправлення помилок заданої кратності.
У зв’язку з побудовою оптимальних кодів виникає така задача: знайти найбільше число N(d) кодових комбінацій n-значного двійкового коду, відстань між якими не менша d. Загальний розв’язок задачі невідомий (крім повного перебору).
Приведемо деякі оцінки:
а) Оцінка Хемінга
d N
1 EMBED Equation.3
2 EMBED Equation.3
3 EMBED Equation.3 (2.12)
4 EMBED Equation.3
………………….
2k+1 EMBED Equation.3.
б) Оцінка Джоші
EMBED Equation.3 . (2.13)
Обидві границі досяжні. Коди у яких досягається рівність в оцінках називають щільноупакованими або досконалими.
в) Оцінка Плоткіна
EMBED Equation.3. (2.2.14)
Оцінка Плоткіна застосовується для кодів з великими кодовими відстанями.
2.9. Систематичні коди
Систематичні коди будуються по спеціальних правилах. Закономірності, закладені в структурі цих кодів, дозволять проводити декодування більш простим способом, ніж пряме порівняння прийнятої кодової комбінації з повною кодовою таблицею або по кодовомк дереву.
Надалі будемо розглядати лише двійкові коди. Замість терміну “кодова комбінація” будемо користуватися як синонімом терміном “кодовий вектор”.
Систематичний n-значний код складається з N=2k кодових векторів, з n символів, які утворюють вектор, k символів є інформаційними, а решта (n-k) - надлишковоми. Надлишкові символи визначають коректуючу здатність коду і дозволяють виявляти, а потім і виправляти їх. Тому n-k символів називають контрольними (перевірними). У всіх кодових векторах контрольні символи займають одні ті ж позиції. Для систематичних кодів застосовують позначення: n, k код.
Найчастіше використовуються систематичні коди із першими k символами інформаційними і рештою n-k - контрольними.
Побудова систематичного коду проводиться в такій послідовності.
Першим беремо нульовий вектор.
1. Складаємо. так звану. породжуючу матрицю EMBED Equation.3 , яка має k стрічок і n стовбців. Як стрічки беруться будь-які ненульові лінійно-незалежні n-значні вектори , які мають відстань не меншу ніж EMBED Equation.3 - базисні вектори. Лінійно-незалежними називають вектори для яких виконується умова EMBED Equation.3. Сі приймають значення 0 або 1. В стрічки матриці G не повинна входити нульова комбінація. Кодова відстань між стрічками EMBED Equation.3 . Вага кожного базисного вектора EMBED Equation.3
2. Решта 2k-k-1 кодових векторів отримуються як лінійні комбінації векторів породжуючої матриці. Ваговими коефіцієнтами можуть бути 0 і 1. Так що все зводиться до сумування стрічок породжуючої матриці попарно, по три аж до суми всіх стрічок.
3. Далі складається множина векторів, ортогональних до базисних векторів коду, тобто, якщо базисний вектор EMBED Equation.3 , а ортогональний до нього вектор EMBED Equation.3 , то виконується рівність:
EMBED Equation.3 (2.15)
Тепер можна побудувати матрицю Н, яка породжує множину векторів ортогональних векторів u. Ця матриця має n-k стрічок і n стовбців. Її стрічками є лінійно-незалежні комбінації векторів u. Матриця Н називається перевірною.
Процедура побудови породжуючої і перевірної матриці може бути спрощена, якщо перші k-символів прийняти як інформаційні, а решту n-k контрольними. Породжуюча матриця тоді будується так: будується одинична EMBED Equation.3 - матриця. До цієї матриці справа дописується EMBED Equation.3 перевірна підматриця EMBED Equation.3 . При цьому перевірна підматриця EMBED Equation.3 повинна будуватися з виконанням таких умов:
Кількість одиниць у її стрічці повинна бути не менша ніж EMBED Equation.3 . Адже найменшою буде кодова відстань із нульовою комбінацією, а одна одиниця у інформацційній частині стрічки уже є..
Сума по модулю два двох будь-яких стрічок EMBED Equation.3 повинна містити не менше ніж EMBED Equation.3 одиниць. За рахунок інформаційної частини матриці забезпечується кодова відстань 2. Тому у перевірній частині необхідно збільшити кодову відстань ще хоча б на одну одиницю.
Виправляюча матриця тоді може бути побудована таким чином. Будується породжуюча кодова матриця. Виділяється підматриця EMBED Equation.3 і транспонується. До неї справа приписується одинична матриця.
Проілюструємо сказане на прикладі коду 7,4 із мінімальною кодовою відстанню EMBED Equation.3 . Будуємо породжуючу матрицю:
EMBED Equation.3 ;
Виділяємо перевірну підматрицю і формуємо повну перевірну матрицю:
Легко переконатися , що векори Gі ортогональні з векторами Ні.
Немає потреби утворювати всі кодові комбінації з G. Досить для будь-якої простої інформаційної комбінації визначити первірні символи. Підматриця EMBED Equation.3 вказує на те, що перевірні символи повинні визначатися рівняннями
EMBED Equation.3;
EMBED Equation.3;
EMBED Equation.3.
Тут EMBED Equation.3 - інформаційні і перевірні розряди коду відповідно. Наприклад, для простої кодової комбінації 0011.
EMBED Equation.3;
EMBED Equation.3;
EMBED Equation.3.
Сумуються розряди, які відповідають 1 в EMBED Equation.3 . Контрольні рівняння відповідно мають вигляд
EMBED Equation.3;
EMBED Equation.3;
EMBED Equation.3.
У результаті таких перевірок буде сформоване EMBED Equation.3 -розрядне двійкове число – синдром помилкик. Ящо код призначений для виправлення помилок, то попередньо небхідно побудувати таблицю синдромів помилок.
У нашому прикладі це виявляється доволі просто – такою таблицею є сукупність стовбців виправної матриці.
Для виправляння двократних, трикратних і помилок вищої кратності, а також пачок помилок, побудова синдромів помилок стає доводі складною задачею, яку вже треба вирішувати за допомогою комп’ютера.
Перейдемо до розгляду деяких типів систематичних кодів
2.10. Коди для виявлення помилок
Код із парним числом одиниць. Код містить лише один надлишковий розряд. Перевірка коду проводиться шляхом сумування по модулю два всіх розрядів. Надлишковість коду рівна
EMBED Equation.3 ,
де n – довжина кодової комбінації; EMBED Equation.3 кількість інформаційних розрядів; EMBED Equation.3 - кількість коттрольних розрядів.
Код виявляє однократні помилки і всі помилки непарної кратності. Не виявляються помилки парної кратності.
Код з подвоєнням елементів. Кожен символ інформаційної частини кодової комбінації доповнюється інвертованим, причому нуль доповнюється одиницею і перетворюється в 01, а одиниця доповнюється нулем і перетворюється в 10. Наприклад, комбінація 10101 буде мати вигляд 1001100110. Індікатором помилки є поява в парних елементах комбінацій 00 або 11.
Надлишковість Кн=0.5 і не залежить від числа інформаційних розрядів
Код виявляє всі помилки за виключенням двократних помилок в парних елементах. Найбільш вірогідна помилка, яка не виявляється - подвійна помилка в парних елементах.
Інверсний код. Повторюється початкова кодова комбінація з доповненням. Причому у тих випадках, коли початкова комбінація містить парне число одиниць, друга комбінація повторює початкову. Якщо ж вхідна комбінація містиь непарне число одиниць, то повторення здійснюється в інвертованому вигляді. Наприклад комбинації 01010 і 01110 в інверсному коді відображаються відповідно як 0101001010 і 0111010001.
Перевірка кодової комбінації проводиться у такій послідовності. Спочатку сумуються одиниці в основній комбінації.Якщо число одиниць виявляється парним, то друга частина комбінації приймається без змін Далі обидві комбініції порівнюються поелементно і при виявленні хоча б одного неспівпаління прийнята комбінація бракується.
Якщо ж число одиниць основної комбінації непарне, то елементи другої частини комбінації інвертуються іперша та друга частини коду порівнюються як в першому випадку.
Надлишковість коду не залежить від кількості елементів початкової комбінації і рівна
EMBED Equation.3 .
Код дозволяє виявити практично всі помилки. Не виявляє помилки коли перекручення виникають в 2-х, 4-х, 6-х, … т.д. елементах основної комбінації і відповідних контрольних розрядах одночасно. Із розглянутих кодів інверсний код має найвищу завадостійкість.
2.11. Коди Хемінга
Намагання спростити кодери і декодери є стимулом для створення різновидів кодів при підвищенні їх коректуючої здатності.
Код Хемінга є одним з найважливіших класів кодів, які знайшли широке застосування в практиці і які мають простий і зручний для технічної реалізації алгоритм виявлення і виправлення однократних помилок. Код Хемінга дозволяє також виявляти всі подвійні помилки при відносно невеликому ускладненні перевірок.
Код Хемінга для виправлення одиничних помилок має мінімальну кодову відстань dmin=3. Проста модифікація дозволяє збільшити dmin до чотирьох.
Код Хемінга для виправлення одиничних помилок повинен мати довжину, яка задовільняє умову
EMBED Equation.3, (2.16)
де k - кількість інформаційних символів.
Ця оцінка є нижньою оцінкою для n. Код Хемінга побудований так, що він зберігає коректуючі властивості, коли нижня оцінка співпадає з тим значенням n, яке забезпечує потрібну коректуючу здатність коду. Такі коди називаються щільними (щільно запакованими).
Код будується так, щоб в результаті =n-k перевірок отримати -розрядне число, яке вказує номер перекрученої позиції кодового вектора. Результат першої перевірки дає цифру молодшого розряду синдрому в двійковій системі числення. Якщо результат цієї перевірки 1, то один з символів групи, що перевіряється, перекручений. Тому першою перевіркою повинні бути охоплені символи з номерами, які мають в двійковому записі одиницю в молодшому розряді, тобто розряди з номерами 1, 3, 5, 7, 9, … . Результат другої перевірки дає значення наступного (старшого) розряду синдрому. Відповідно другою перевіркою повинні бути охоплені символи в позиціях з номерами 2, 3, 6, 7, 12 і т.д. Аналогічно при третій перевірці повинні контролюватися символи, номери яких містять одиницю в третьому розряді, тобто 4, ,6 , 7, 12 і т.д.
Таким чином рівняння для перевірки повинні мати наступний вигляд:
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3 (2.17)
EMBED Equation.3
……………………………
Як контрольні доцільно брати позиції з номерами рівними EMBED Equation.3 (і=0,1,...,-1). кожна із них входить тільки у одне рівняння (2.17) Перевірочна матриця має n-k стрічок і n стовбців. Легко переконатися, що кожен стовбець матриці є комбінацією, яка є двійковим зображенням номера позиції коду.
Наприклад, для коду із значністю n = 9, який забезпечує виправлення олнократних помилок, кількість перевірних символів EMBED Equation.3 , перевірна матриця має вигляд:
EMBED Equation.3
Зобразимо як приклад просту кодову комьбінацію 10011 в коді Хемінга.
Інформаційні розряди повинні бути в позиціях а3, а5, а6, а7, а9. Значення позицій: а3=1,.а5=0, а6=0, а7=1, а9=1. З а умовами (2.17) отримаємо такі значення перевірних розрядів: а1=1, а2=0, а4=1, а8=1. Отже п’ятиелементному коду 10011 відповідає девятиелементний код Хемінга 101100111
Припустимо, що при передачі перекручено 5-й символ 1001110111. Тоді в результаті перевірок отримаємо: перша перевірка – 1, друга – 0, третя – 1, четверта – 0. Отриманий синлром дає номер позиції 0101
Код Хемінга з кодовою відстанню dmin=4 отримується додаванням до коду Хемінга з dmin=3 перевірного символа, який доповнює до парності всі символи кодового вектора. Декодування проводиться за лва етапи. На першому етапі визначається синдром для коду з dmin=3 EMBED Equation.3 , на другому - здійснюється остання перевірка на парність EMBED Equation.3 .
Для попереднього прикладу перевірна матриця матиме вигляд
EMBED Equation.3
За результатами перевірок на вказаних двох етапах можливі такі ситуації: S1=0, S2=0 - без помилки; S1=0, S2=1 – помилка у восьмому розряді; S1=1, S2=0 –подвійна помилка; S1=1, S2=1 – корекція однократної помилки.
Надлишковість коду Хемінга EMBED Equation.3 залежить від кількості інформаційних символів і при зміні k від 4 до 1013 змінюється від 0.429 до 0.098 при dmin=3 від 0.5 до 0.0107 при dmin=4.
2.12. Циклічні коди
У пошуках більш простої техніки кодування і декодування створені так звані циклічні коди. Схеми кодуючих і декодуючих пристроїв цих кодів достатньо прості і будуються на основі звичайних зсувних регістрів. Назва кодів походить від їх властивостей, які полягають в тому, що кожна кодова комбінація може бути отримана шляхом циклічної перестановки символів комбінації, яка належить до цього кодового простору. Наприклад, якщо кодовий вектор EMBED Equation.3 є дозволеною комбінацією циклічного коду, то комбінація EMBED Equation.3 є також дозволеним кодовим вектором.
Циклічні коди належать до систематичних (групових) кодів, для яких стрічки породжуючих кодових матриць зв‘язані додатковою умовою циклічності. Всі стрічки породжуючої матриці такого роду можна отримати циклічним зсувом однієї комбінації, яка називається утворюючою. Будемо вважати, що зсув здійснюється справа наліво, причому крайній лівий символ кожен раз переноситься в кінець комбінації.
Кількість можливих циклічних (n,k)-кодів значно менша кількості різних систематичних (n,k)-кодів. Циклічні коди зручно розглядати, представляючи комбінації не в вигляді послідовністі нулів і одиниць, а в вигляді полінома від фіктивної зміної х:
EMBED Equation.3 , (2.18)
де EMBED Equation.3 - цифри даної системи числення (в двійковій системі 0 і 1). Наприклад двійковий семирозрядний код 1010101 може бути записаний у виді поліному:
EMBED Equation.3
EMBED Equation.3 . (2.19)
Така форма представлення дозволяє звести дії над комбінаціями до дій над многочленами. Множення виконується по звичних правилах, однак коефіцієнти при однакових степенях додаються по модулю 2; ділення здійснюється по правилах ділення степеневих функцій, при цьому операції віднімання замінюються операціями сумування по модулю два.
Представлення комбінацій в формі полінома зручне ще й тим, що циклічна перестановка є результатом множення даного полінома на х. Однак при цьому від результату слід відняти EMBED Equation.3 , тобто здійснити приведення по модулю xn+1.
У відповідності з визначенням циклічного коду для побудови породжуючої матриці (n, k) – коду достатньо вибрати тільки одну кодову n – розрядну комбінацію. З цієї комбінації циклічним зсувом можна отримати (n-1) комбінацій, з яких будь-які k комбінацій можуть бути взяті як базисні. Оскільки циклічний зсув еквівалентний множенню полінома на x по модулю (xn+1), то процес утворення базисних поліномів можна представити в такому вигляді:
EMBED Equation.3 ;
EMBED Equation.3 ;
EMBED Equation.3 ; (2.20)
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
EMBED Equation.3 .
де Р(х) - деякий поліном; с2, с3, …, сn-1 – коефіцієнти, які приймають значення 1 при EMBED Equation.3 і значення 0 при EMBED Equation.3 .
При такому способі побудови базисних поліномів Р(х) називається утворюючим поліномом. Якщо прийняти умову, що Р(х) є дільником двочлена (xn+1), то базисні поліноми, тобто всі дозволені комбінації діляться на Р(х). З цього випливає, що для всіх дозволених комбінацій многочлен ділиться на Р(х) без остачі.
Ні один многочлен, який відповідає забороненій комбінації, не ділиться на утворюючий без остачі. Ця властивість дозволяє виявити помилку. По виду остачі можна установити і вектор помилки.
Множення і ділення многочленів просто реалізується на зсувних регістрах зі зворотними зв‘язками, що і стало причиною широкого застосування циклічних кодів.
Таким чи...
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора