«Кодування інформації. Коректувальні коди. Основні параметри та принципи побудови коректувальних кодів»

Тема: «Кодування інформації. Коректувальні коди. Основні параметри та принципи побудови коректувальних кодів» Перетворення дискретного повідомлення в сигнал складається з двох операцій: кодування і модуляції Кодування визначає закон побудови сигналу, а модуляція – вид формованого сигналу, що має передаватися каналом зв’язку. Приклад Найпростішим прикладом дискретного повідомлення є текст. Будь-який текст складається зі скінченного числа елементів: букв, цифр, розділових знаків. Для європейських мов число елементів коливається від 52 до 55, для східних – може обчислюватися сотнями і навіть тисячами. Оскіль­ки число елементів у дискретному повідомленні скінченне, то їх можна пронумерувати і тим самим звести передавання повідомлень до передавання послідовності чисел. МНОЖИНА ЗНАКІВ (СИМВОЛІВ) І СИСТЕМА ПРАВИЛ ПОБУДОВИ СКЛАДЕНИХ ЗНАКІВ НАЗИВАЄТЬСЯ КОДОМ. КІНЦЕВА ПОСЛІДОВНІСТЬ КОДОВИХ ЗНАКІВ НАЗИВАЄТЬСЯ СЛОВОМ АБО КОДОВОЮ КОМБІНАЦІЄЮ. Приклад З цього погляду алфавіт української або іншої мови і сукупність правил побудови слів є кодом, за допомогою якого усне мовлення перетворюється в текст. Слова (кодові комбінації) можуть розглядатися як символи деякої іншої множини; разом із установленими правилами утворення речень вони теж утворюють код, яким ми користуємося для обміну інформацією. Коди поділяються:  за числом m символів у множині – на двійкові (m = 2) і недвійкові (m ≠ 2). Залежно від числа символів у множині коди називають, наприклад, трійковими, вісімковими. Кількість символів у множині є основою коду;  за довжиною кодових комбінацій – на нерівномірні, у яких слова мають нерівну кількість символів, і рівномірні – з однаковою кількістю сим­волів у словах;  за принципом використання кодових комбінацій – на коди з використанням усіх дозволених комбінацій заданої довжини n для подання повідомлень і коди з використанням частини можливих комбінацій. Останні у свою чергу поділяються на коди, що дають змогу виявляти або виправляти спотворені символи (помилки), які виникають через завади, – коректувальні коди, і на коди, що не дають такої можливості. У ЗАГАЛЬНОМУ ВИПАДКУ ПРОЦЕС ПЕРЕТВОРЕННЯ ПОВІДОМЛЕННЯ В КОДОВУ КОМБІНАЦІЮ ПРИЙНЯТО НАЗИВАТИ КОДУВАННЯМ. При цьому мається на увазі взаємооднозначне перетворення. В окремому випадку кодування можна визначити як операцію встановлення однозначної відповідності між символами групи символів деякого коду з символами групи символів іншого коду. Таке кодування є переведенням з однієї системи числення в іншу (наприклад, десяткових чисел у двійкові). Слова “код” і “кодування” походять від латинського слова codex – кодекс, тобто книга, що містить знаки, систему правил. Довідка Повідомлення, які є текстом природною мовою, мають значний надлишок, тому для його зменшення використовують кодування, що враховує статистичні особливості повідомлення. Для зменшення надлишку доцільно кодувати повідомлення так, щоб середня довжина L кодових комбінацій була найменшою, тобто здійснювати статистичне кодування. Одним з кодів, що використовують статистичні властивості повідомлень, є код Шеннона – Фано. Поліпшення якісних характеристик каналів для підвищення надійності приймання завжди пов’язано зі значними матеріальними витратами, а іноді й дуже високими. Тому величез­не значення мають широко застосовувані в техніці передавання методи підвищення надійності приймання, які не потребують поліпшення якості каналу. Ці методи засновані на внесенні в переданий сигнал значного надлишку. Надлишок, що вводиться в переданий сигнал, накладає на нього певні додаткові умови, перевірка дотримання яких при прийманні дає змогу встановити факт спотворення сигналу, а також ототожнити прийнятий спотворений сигнал з відповідним неспотвореним. Будь-які методи внесення надлишку в переданий сигнал пов’язані зі збільшенням об’єму сигналу, тобто зі збільшенням або потужності сигналу, або ширини спектра, або часу передавання. Можливості підвищення надійності приймання збільшенням потужності і ширини спектра при передаванні дискретної інформації зі стандартних каналів зв’язку досить обмежені, тому переважне застосування дістав метод уведення надлишку збільшенням часу передавання сигналу. Цей метод можна реалізувати у двох різновидах – використанням для передавання дискретної інформації, зниженої стосовно номінального значення швидкості, і застосуванням коректувальних кодів. Зниження швидкості передавання інформації по каналах невисокої якості набуло широкого застосування. Так, у багатьох типах апаратури передавання даних (АПД), що працюють по каналах тональної частоти (ТЧ), передбачаються дві і більше швидкості модуляції (наприклад, 600 і 1200 бод), причому з меншою швидкістю звичайно ведеться передавання на великі відстані, а також робота по каналах зі звуженою смугою пропускання (300–2700 Гц). Застосування коректувальних кодів є ефективнішим методом підвищення надійності, ніж застосування зниженої швидкості. Зазначимо, що обидва методи не слід протиставляти один одному: зниження швидкості передавання можна вважати окремим випадком застосування коректувального коду. Розглянемо деякі поняття, пов’язані з коректувальними кодами. Звичайний (простий) код характеризується тим, що окремі його кодові комбінації відрізняються одна від одної лише одним розрядом. Тому навіть один помилково прийнятий розряд спричинює заміну однієї кодової комбінації іншою і, отже, неправильне приймання повідомлення. Коректувальні (надлишкові, завадостійкі) коди будують так, що для передавання інформації використовується лише частина кодових комбінацій (дозволені комбінації), які відрізняються одна від одної більше ніж одним розрядом. Усі інші комбінації для передавання не використовуються і належать до числа недозволених (заборонених). Таким чином, при застосуванні коректувальних кодів помилка в одному розряді спричинює заміну дозволеної кодової комбінації недозволеною, що дає змогу знайти помилку. При досить великій відмінності дозволених комбінацій одна від одної можливе виявлення дворазової, триразової і т. д. помилки, оскільки вони зумовлять утворення недозволених комбінацій, а перехід однієї дозволеної комбінації в іншу відбуватиметься під впливом помилок більшої кратності, що є результатом найбільш інтенсивних завад. Приклад Використаємо для передавання інформації чотирирозрядні кодові комбінації, що відрізняються одна від одної не менш ніж двома розрядами: 0011, 0110, 1001, 1010, 1100, 1111, 0101, 0000. Нехай при передаванні кожної з цих комбінацій (наприклад, 0011) сталася одинична помилка, внаслідок чого спотворився перший розряд, і прийнято комбінацію 1011. Ця комбінація є недозволеною, що свідчить про наявність помилки. Підберемо далі чотирирозрядні комбінації, що відрізняються всіма чотирма розрядами: 0011 і 1100. Легко переконатися, що при використанні цих комбінацій виявляються одно-, дво- і триразові помилки, а не виявляється лише чотириразова помилка. Цей самий код, що складається з двох кодових комбінацій, може використовуватися і для виправлення одиничних помилок. Нехай, наприклад, прийнято комбінацію 1011. Ця комбінація відрізняється від дозволеної комбінації 0011 одним розрядом, а від іншої дозволеної 1100 – трьома. Отже, прийнята комбінація “ближча” до комбінації 0011, ніж до комбінації 1100; це дає підставу вважати, що була передана комбінація 0011. Підвищена завадостійкість двох розглянутих кодів пов’язана з наявним в них надлишком. Так, перший код містить вісім комбінацій, що становлять чотири розряди кожна. В той самий час у простому коді для утворення восьми комбінацій достатньо трьох розрядів, а не чотирьох. Отже, підвищення завадостійкості потребує введення додаткового Рис. 1. Класифікація коректувальних кодів розряду. Другий код має ще більшу завадостійкість, і це потребує ще більшого надлишку – трьох додаткових розрядів. Коректувальні коди так само, як і прості, можуть бути рівномірними або нерівномірними, двійковими або багатопозиційними. Використання нерівномірних або багатопозиційних кодів спричинює значне ускладнення апаратури передавання даних, тому застосовуються вони дуже рідко. У зв’язку з цим надалі розглядатимемо лише двійкові рівномірні коректувальні коди. Останні поділяються на два класи – блокові і неперервні (рис.1). При використанні блокових кодів передана інформаційна послідовність розбивається на окремі кодові комбінації (блоки), що кодуються і декодуються незалежно одна від одної. Неперервні коди – це неперервна послідовність розрядів, і поділ її на окремі блоки неможливий. Блокові коди, у свою чергу, поділяються на роздільні та нероздільні. Роздільними називаються коди, в яких одні розряди є інформаційними, інші – перевірними. Останні і вносять у код надлишок, необхідний для виявлення або виправлення помилок. У роздільних кодах інформаційні і перевірні розряди займають завжди одні й ті самі позиції в кодовій комбінації. Роздільні коди позначаються як (n, k)-коди, де n – довжина або число розрядів коду; k – число інформаційних розрядів. Нероздільні коди утворюють зараз нечисленну групу. До них, зокрема, належать рекомендований МСЕ стандартний телеграфний код № 3 – семирозрядний код, кожна кодова комбінація якого містить три одиниці і чотири нулі. Серед роздільних кодів розрізняють коди систематичні і несистематичні. Систематичними називаються такі блокові роздільні (n, k)-коди, в яких перевірні розряди – це лінійні комбінації інформаційних. Систематичні коди утворюють велику групу кодів і дуже широко застосовуються на практиці. Тому головну увагу приділяють саме цим кодам і, зокрема, їх найбільш відомим різновидам – кодам Хеммінга і циклічним. Кількість розрядів, якими різняться дві кодові комбінації, називається кодовою відстанню між двома комбінаціями. Так, кодова відстань між комбінаціями 11011 і 00010 дорівнює трьом, оскільки вони різняться трьома розрядами – першим, другим і п’ятим. Найменша з кодових відстаней у коді називається мінімальною кодовою або хеммінговою відстанню. Наприклад, у трирозрядному коді з дозволеними комбінаціями 101, 110, 011, 000 мінімальна кодова відстань дорівнює двом, для простих кодів – одиниці. Мінімальна кодова відстань пов’язана з кількістю помилок, що виявляються, і кількістю помилок, що виправляються, так: , (1) , (2) де  – кількість помилок, що виявляються; t – кількість помилок, що виправляються. Коректувальні коди можна використовувати для виправлення помилок і одночасного виявлення помилок більшої кратності. Можна показати, що при цьому (коли ) . (3) Мінімальна кодова відстань лише частково характеризує коректувальні властивості коду, оскільки звичайно забезпечується виправлення і виявлення помилок і більш високої кратності, ніж обумовлене співвідношеннями (1) – (3). Загальна кількість комбінацій коду завдовжки n дорівнює . Число дозволених кодових комбінацій визначається числом інформаційних розрядів і дорівнює , де r – число перевірних розрядів. Отже, число дозволених кодових комбінацій у рази менше загального числа комбінацій. Надлишком коду називають відношення r/n. Питання про мінімально необхідний надлишок коду при заданих мінімальних кодовій відстані і довжині коду в загальному випадку не вирішено. Існує лише ряд верхніх і нижніх оцінок. Найбільше наближення звичайно забезпечує критерій Варламова , (4) де – число сполучень з елементів по i елементах. Для деяких кодів отримано точні залежності між числом перевірних і інформаційних розрядів при заданій мінімальній кодовій відстані. Так, при має місце співвідношення , (5) причому r – найменше ціле число, при якому задовольняється нерівність (5).

Схожі: