• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

ПОНЯТТЯ ПРО КОДУВАННЯ. ОПТИМАЛЬНИЙ КОД. КЛАСИФІКАЦІЯ КОДІВ І ЇХ ПАРАМЕТРИ. ШВИДКІСТЬ МОДУЛЯЦІЇ І ПЕРЕДАЧІ ІНФОРМАЦІЇ

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

У поняття "кодування" входить дуже широкий круг явищ. Наприклад, будь-яке вимірювання є кодування, оскільки його можна розглядати як перетворення багатьох значень, які може приймати вимірювана величина (її алфавіт), у вихідний алфавіт вимірювального приладу — безліч відлічуваних значень стрілки приладу. Кодування виробляється в мікрофоні, в якому кожному певному значенню повітряного тиску (первинний алфавіт) відповідає певне значення струму в ланцюзі мікрофону (вторинний алфавіт) і т.д.

Дуже важливим параметром кодування є об'єм первинного і вторинного алфавіту — кількість різних символів, з яких будується повідомлення і які відрізняються один від одного тими або іншими фізичними ознаками. Наприклад, китайський алфавіт містить декілька десяток тисяч елементів (ієрогліфів), а російський — тільки 32 знаки.

У окремому випадку кількість елементів в первинному і вторинному алфавітах може бути однаковою.

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

Якщо повідомлення повинно бути передано по електричному каналу зв'язку, а алфавіт складений з неелектричних елементів, то необхідно шляхом кодування перетворити алфавіт, складений з елементів, що відрізняються один від одного неелектричними параметрами (наприклад, букви азбуки — формою), в алфавіт такого ж об'єму, елементи якого відрізняються один від одного по якому-небудь електричному параметру — величині струму, напруженості електричного або електромагнітного поля і т.д. Інакше кажучи, для створення вторинного алфавіту в цьому випадку необхідно перетворити неелектричні параметри в електричні, здійснивши модуляцію одного з параметрів електричного стану ланцюга, тобто створити електричні сигнали.

Таким чином, перетворення повідомлення, представленого у вигляді набору елементів, що мають неелектричні параметри, в повідомлення, представлене елементами алфавіту, складеного з різних (по параметру) електричних сигналів, включає три операції: 1) кодування, 2) перетворення неелектричної величини в електричну, 3) модуляцію.

Можна сказати, що кодування визначає математичну, а модуляція — фізичну сторони процесу перетворення повідомлення в електричні сигнали.

Розглянемо методику перетворення дискретного повідомлення, записаного знаками російського алфавіту, у відповідні електричні сигнали.

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

При цьому ми перетворили елементи одного алфавіту в елементи або комбінації елементів іншого алфавіту, в загальному випадку, з іншим об'ємом. Комбінація або сукупність елементів алфавіту, що відображає одне повідомлення, називається кодовою комбінацією.

Тепер при передачі будь-якого тексту передаватимемо послідовний ряд чисел, але при цьому велике значення має те, по якій системі побудовано числення. Так, в звичній нам десятковій системі числення є десять відмінних один від одного знаків, з яких може бути побудовано будь-яке число (об'єм алфавіту рівний десяти): 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.

Але можуть бути і інші системи числення. Пятерічная система числення припускає наявність п'яти різних знаків для написання будь-якого числа — 0, 1, 2, 3, 4; трійкова система має три різні знаки — 0, 1, 2; двійкова система числення має два різні знаки — 0, 1.

Кількість різних знаків даної системи числення (об'єм коду) називається її підставою. Так, у десяткової системи числення підстава рівна десяти, у двійкової — двом і т.д.

У будь-якій системі числення кожне число Л', відмінне від нуля, можна записати

(1.29)

де kt — знаки (цифри) даної системи числення, що показують число в г-м розряді; тс — підстава системи числення.

Наприклад, число 105 в десятковій системі числення можна записати так:

У двійковій системі числення те ж саме число запишемо у такому вигляді:

Ряд чисел, записаних в десятковій і двійковій системах числення, відповідно має вигляд

Легко визначити максимальне число, яке може бути записане заданою кількістю знаків (розрядів) в якій-небудь системі числення:

(1.30)

де Л'шах — максимальне записане число.

Загальна ж кількість різних чисел (з урахуванням нуля)

(1.31)

Наприклад, двома знаками в різних системах числення можна записати такі максимальні числа:

у десятковій системі 102 - 1 -99

у двійковій системі 22 — 1 = 3.

З розглянутого видно, що чим більша підстава системи числення т, тим менша кількість знаків потрібна для запису одного і того ж числа, але, разом з тим, росте кількість різних знаків системи.

Будь-яке число в двійковій системі числення записується у вигляді комбінації з двох відмінних один від одного знаків 0 і 1 і є комбінацію елементів двійкового коду. Якщо потрібно передати це число по каналу зв'язку, то його необхідно перетворити в таку ж комбінацію двох значень якого-небудь параметра переносника електричної енергії.

Наприклад, число десять в двійковій системі числення має вигляд 1010. Джерелом енергії є генератор постійного струму. Хай одиниці при однополюсному телеграфуванні відповідає струмова, а нулю — бестоковая посилки. Тоді вказане число у вигляді електричних посилок може бути представлено, як показано на рис. 1.4,а. При двополюсній роботі запис цього ж числа приведена на рис. 1.4,б.

Рис. 1.4. Передача двійкових чисел

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

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

Розглянемо двійковий код (код, побудований по двійковій системі числення), число елементів в комбінації якого не перевищує п'яти. Максимальне число, яке можна записати, використовуючи не більше п'яти знаків AW* - 2s — 1 = 31.

Пронумеруємо знаки первинного алфавіту в двійковій системі числення:

і представимо числа у вигляді комбінацій елементарних посилок (рис. 1.5). Це буде нерівномірний код, оскільки в ньому не всі числа представлені однаковою кількістю елементарних посилок.

Рис. 1.5. Кодові сигнальні конструкції

Оскільки комбінації посилок слідують одна за одною безперервно, то на станції прийому важко визначити почало і кінець кожної комбінації, що абсолютно необхідно, щоб прочитати записані числа. Завдання значно спрощується, якщо комбінації, що відносяться до кожного з ряду передаваних чисел, починатимуться через рівні проміжки часу. Для цього доповнимо кожну комбінацію до максимально можливої кількості елементарних посилок — п'яти і одержимо двійковий п'ятизначний рівномірний код. Виникає питання: з якого боку слід помістити бракуючі елементарні посилки — зліва ілг праворуч від записаної комбінації і який стан (0 або 1) повинні мати ті, що не ці дістають елементарні посилки?

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

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

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

З нерівномірних кодів знайшли застосування код Морзе і кабельний код.

Код Морзе будується по двійковій системі числення (рис. 1.6), причому знакам, що найбільш часто зустрічаються в даному алфавіті, привласнюються числа, записувані мінімальною кількістю елементарних посилок (враховується статистика даної мови, для коду Морзе — англійського).

Рис. 1.6. Сигнальні кодові конструкції при двопозиційних сигналах

Для передачі кодом Морзе, з урахуванням пропусків, потрібний в середньому близько 9,5 fa на кожен знак, де to — тривалість елементарної посилки.

Гідність коду Морзе — легка запомінаємость, можливість запису простими засобами і прийому на слух при сильних перешкодах.

У кабельному коді (рис. 1.7) крапка записується позитивною посилкою, тире — негативної і пропуск — бестокової. Таким чином, кабельний код є трійковим кодом, побудованим по трійковій системі числення (є три різні знаки для запису чисел). На кожен знак первинного коду доводиться в середньому близько чотирьох елементарних посилок. Таке різке зменшення кількості елементарних посилок в кодовій комбінації пояснюється застосуванням трійкової системи числення. Застосовується кабельний код при малому рівні перешкод в каналі зв'язку, оскільки його перешкодостійкість значно нижча, ніж у двійкового коду.

Рис. 1.7. Сигнальні кодові конструкції при різній позиційності

Оптимальним називається такий код, у якого середнє число елементів в комбінації є мінімальним. Ясно, що знаки первинного алфавіту, що в цьому випадку частіше зустрічаються, повинні записуватися меншою кількістю елементарних посилок, тобто оптимальний код не може бути рівномірним. Наприклад, код Морзе є ? оптимальним в цьому сенсі для англійської мови (для російської мови відмінність від оптимальності складає 8 %). Проте в ньому після кожного знаку слідує пропуск з трьох елементарних посилок, що знижує ефективність коду. Було б доцільно побудувати нерівномірний оптимальний код без пропусків між комбінаціями.

Для оцінки ступеня оптимальності коду слід знати той преде, i, до якого потрібно прагнути, зменшуючи кількість елементів вторинного коду на кожен знак передаваного повідомлення (первинного коду).

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

де Pi — вірогідність появи i-й букви в повідомленні. Все Р, зв'язані між собою співвідношенням

При цьому 0 < Pi < 1.

Якщо в повідомленні міститься одна буква, вірогідність появи якої рівна одиниці, а вірогідність появи всієї решти т — 1 буква рівна нулю, то

тобто ентропія повідомлення рівна нулю. Передавати, таке повідомлення немає необхідності, оскільки воно наперед відоме одержувачу.

Припустимо, що в повідомленні поява всіх т букв рівноімовірна. Звідси Pi = \/m,

Ентропія при цьому буде максимальною.

К. Шеннон показав, що передаване повідомлення може бути закодовано так, щоб середнє число двійкових одиниць на букву повідомлення скільки завгодно наближалося до ентропії даного повідомлення. Але це число не може бути менше ентропії. Отже, знання значення ентропії дозволяє оцінити ступінь наближення використовуваного коду до оптимального.

Ентропія Я джерела повідомлень телеграфного тексту для російської мови визначається статистичними дослідженнями декількох тисяч телеграм. Вірогідність використання різних букв різна. Наприклад, Р (пропуск) = 0,17; Р (0) = 0,078; Р (а) = 0,0626 і т.д., причому ^ Р (г) = 1 (без урахування вірогідності проходження буквених поєднань).

На підставі одержаних вище даних Н = 4,363 біт/букву.

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

Наприклад, в двійковому алфавіті з рівноімовірними знаками „, _, біт Н = Iog22 = 1, тобто кожен елемент двійкового коду містить знзк один біт інформації. Якщо ж підстава коду т>2, то кожен елемент такого коду містить більшу кількість біт інформації, що дозволяє підвищити ефективність системи зв'язку. Якщо т = 32, то Н = log2m = Iog225 = 5

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

Розглянемо один із способів побудови оптимального двійкового коду. Було відмічено, що оптимальним може бути тільки нерівномірний код. Буквам, що при цьому найбільш часто зустрічаються, привласнюються найбільш короткі кодові комбінації.

Для знаходження меж між кодовими комбінаціями можна скористатися двома способами:

1) після кожної комбінації передбачається знак розділу (саме так побудований код Морзе), але це збільшує довжину кодової комбінації;

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

Хай є чотирьохбуквений алфавіт А\, Аг, Аз, А* з вірогідністю появи окремих букв Р = 0,5; Р2 = 0,25; Р3 = 0,125;

Ентропія джерела повідомлення з таким алфавітом

Максимальне значення ентропії, коли всі значення р, рівні між собою, складає Нтах = log2 т — Iog2 4 = 2 -? . Следова тільний, надмірність D = Нп^—Н = 2—1,75 = 0,25.

Для даного алфавіту найбільш простим оптимальним двійковим кодом був наступний:

Проте кодові позначення для А\ і Аг є початковими частинами для А' і At, тому розділити прийняті комбінації на станції прийому неможливо. Комбінація 0100110 може бути розшифрована в декількох варіантах, наприклад:

Для вибору кодових комбінацій користуються наступним правилом (рис. 1.8).

Рис. 1.8. Формування слів оптимального коду

Всі букви записуються у порядку убування вірогідності. Одержана послідовність розбивається на дві групи так, щоб сумарна вірогідність розподілилася між групами по можливості порівну. Потім кожна підгрупа, у свою чергу, розбивається на дві підгрупи з дотриманням тієї ж умови рівності вірогідності. Таке ділення продовжується до тих пір, поки в підгрупах не залишиться по одному повідомленню. Кодове позначення кожної підгрупи визначається так: крок вліво дає цифру 0, крок управо — цифру 1.

Приведена вище комбінація розшифровується однозначно:

Визначимо середню довжину кодової комбінації

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

Не дивлячись на те що оптимальні коди зменшують середню тривалість кодового слова, на практиці користуються рівномірними кодами, що істотно спрощує апаратуру зв'язку.

Отже, при передачі кожному символу початкового алфавіту повідомлень об'єму JVH ставиться у відповідність m-елементарна двійкова послідовність — кодова комбінація. Ясно, що можливе число послідовностей рівне

(1.32)

Якщо при передачі використовуються всі можливі кодові комбінації, то код називається простим Ш„ = No).

Ступінь відмінності комбінацій називається кодовою відстанню. Між двома кодовими комбінаціями воно визначається числом відмінних елементів (розрядів). Наприклад, комбінації 010 і 100 відрізняються двома розрядами.

Кодова відстань рівна числу одиниць в кодовому слові, що одержується при підсумовуванні розрядів порівнюваних кодових слів по модулю два. Наприклад:

Якщо число використовуваних кодових слів М < No (не всі можливі комбінації використовуються), то коди називаються надмірними, або що коректують.

Принцип побудови коректуючих кодів розглянемо на геометричній моделі трьохелементного коду (рис. 1.9), всі вісім комбінацій якого можна представити у вигляді крапок в тривимірному просторі, співпадаючих з координатами вершин одиничного куба.

Рис. 1.9. Геометрична модель трьохелементного коду

Якщо для передачі використовуються всі вісім комбінацій, то виходить звичайний трьохелементний код. Найменша кодова відстань с/щш — найменша відстань між двома використовуваними комбінаціями — рівно довжині ребра куба, тобто одиниці. При помилковому прийомі будь-якого елементу кожна комбінація переходить в іншу використовувану комбінацію і помилка не може бути виявлена. При використанні для передачі тільки деяких комбінацій, наприклад, з парним числом одиниць (011, 101), одержимо код з виявленням одноразової і триразової помилок.

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

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

Число помилок /об і найменша необхідна відстань dmin взаїмозавісими, що виявляються: dmm-tn& + 1.

Для того, щоб одноразова помилка могла бути не тільки виявлена, але і виправлена, необхідно, щоб найменша відстань складала не менше трьох одиниць (три ребра куба). Цій вимозі задовольняє будь-яка пара крапок, розташованих на діагоналі куба, наприклад, 000 і 111.

При одноразовій помилці, наприклад, при заміні комбінації 000 комбінацією 010, одержана невживана комбінація буде ближча до істинної (000), чим до помилкової (111). Це і дає можливість виправити помилку. Крім того, такий код виявляє без виправлення двократну помилку, оскільки при останній виходить невживана комбінація.

Число помилок, що виправляються ?„ і кодова відстань dm\n зв'язані формулою dmm ~ 2и + 1.

Таким чином, ідея двійкових коректуючих кодів полягає в тому, що із загальної кількості кодових комбінацій N = 2п для передачі інформації вибирається S комбінацій (S < N) так, щоб при помилковому прийомі З елементів одна використовувана комбінація не перетворилася на іншу використовувану комбінацію. Отже, коректуючі коди володіють надмірністю.

Для оцінки економічності і ефективності кодів з виявленням помилок вводиться поняття коефіцієнта надмірності KW26 і коефіцієнта виявлення К^н'-

(1.33)

де N = 2" — загальна кількість комбінацій, які можна одержати в «-элементном коді; S — кількість використовуваних комбінацій.

де L — загальна кількість помилкових комбінацій, помилка в яких може бути виявлена; М — те ж, але помилка не піддається виявленню.

Розглянемо прості коректуючі коди.

Код з парним числом одиниць в комбінації утворюється із звичайного коду шляхом додавання до комбінації m-елементного коду ще одного елементу, щоб кількість одиниць в новому (т+1) -эле-ментном коді була парною. Такий код дозволяє виявити непарне число помилково прийнятих елементів. Послідовність перетворень кодових комбінацій приведена на рис. 1.10.

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

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

Коефіцієнт надмірності

Коефіцієнт виявлення Ко6н можна підрахувати, якщо відома вірогідність одиночної помилки Р3. Під одиночною помилкою розуміють неправильний прийом одного елементу з послідовності переданих.

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

(1.35)

де q= 1-Я; С\ = щ^Т-

Вірогідність правильного прийому комбінації

(1.36)

Вірогідність виявлення помилки буде рівна сумі вірогідності появи непарного числа помилок

(1.37)

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

(1.38)

Вірогідність всіх помилок, що як виявляються, так і невиявляються

(1.39)

При передачі досить великої кількості комбінацій Q можна рахувати, що кількість комбінацій, помилки в яких виявляються, рівне L = Qрса і загальна кількість комбінацій, в яких помилки як виявляються, так і НР виявляються, рівно сумі

(1.40)

Звідси

(1.41)

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

Візьмемо звичайний п'ятиелементний код Z = 25 = 32. Після перетворення його в шестиелементний код з парним числом одиниць одержимо S = 26 = 64. При цьому

(1.42)

При Ре = 10 3 Кова = 0,795, тобто приблизно 20 % всіх помилок виявляються невиявленими.

Типовим прикладом коду з постійним числом одиниць і нулів в комбінації є семиелементний код з відношенням одиниць і нулів, рівним 3/4, тобто будь-яка використовувана комбінація в ньому містить три одиниці і чотири нулі (рис. 1.11).

Рис. 1.11. Сигнальні конструкції дйя коду з відношенням 3/4

Загальна можлива кількість комбінацій в семиелементному коді S = 27 = 128. Кількість використовуваних комбінацій

Коефіцієнт надмірності

Що виявляє здатність коду з постійним числом одиниць і нулів значно більше, чим коду з парним числом одиниць. Такий код дозволяє виявити всі одиночні, подвійні, потрійні і т.д. помилки, за винятком випадків, коли одна з одиниць комбінації переходить в нуль, а один з нулів — в одиницю. Помилки такого вигляду називаються зсувом.

Знайдемо коефіцієнт виявлення. Вірогідність помилкового прийому одній з трьох одиниць складе

(1.43)

Вірогідність помилкового прийому одного з чотирьох нулів рівна

(1.44)

Якщо нехтувати вельми малою вірогідністю того, що будуть помилково прийняті дві одиниці і два нулі або три одиниці і три нулі, то вірогідність невиявленої помилки

Оскільки вірогідність /-кратной помилки Pi = C'n Pi q"~l, то вірогідність правильного прийому комбінації Ра, а = qn.

Для семиелементного коду Ра.п = а7.

Вірогідність всіх помилок Р„вш = 1—Q''?

Вірогідність помилок Роья, що виявляються = Л,бщ—Рв.о —

Коефіцієнт виявлення

Якщо Р3 = 10~2, то КОБІ = 0,985, що трохи відрізняється від експериментальних даних.

Читайте також:

1. II. Класифікація видатків та кредитування бюджету.
2. II. Поняття соціального процесу.
3. V. Класифікація і внесення поправок
4. V. Класифікація рахунків
5. V. Поняття та ознаки (характеристики) злочинності
6. Vу -швидкість ударника
7. А. Структурно-функціональна класифікація нирок залежно від ступеню злиття окремих нирочок у компактний орган.
8. А/. Поняття про судовий процес.
9. Автоматичне кодування.
10. Адміністративний проступок: поняття, ознаки, види.
11. Адміністративні правовідносини: поняття, ознаки,
12. Адміністративні провадження: поняття, класифікація, стадії

Переглядів: 3770