Кодування в дискретних каналах

Лабораторна робота № 1

1. Мета роботи

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

 

1. Класифікація кодів та їх характеристики.

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

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

Код – сукупність кодових комбінацій, побудованих за одним правилом і на основі одного алфавіту.

Наведемо коротку класифікацію кодів.

За потужністю алфавіту (кількістю q символів алфавіту) коди розділяють на двійкові (q =2) та недвійков і (q >2). Останні називають ще багатопозиційними або багатоосновними.

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

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

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

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

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

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

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

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

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

 

До основних характеристик кодів належать:

• потужність алфавіту коду q – кількість символів алфавіту (для двійкового коду q= 2);
• кількість інформаційних елементів k;
• кількість перевірочних елементів r (для коректувальних роздільних кодів);
• довжина (розрядність) КК n – кількість символів, які складають кодову комбінацію (для систематичних кодів n=k+r);
• потужність коду N_Д – кількість дозволених кодових комбінацій, які використовуються для передачі повідомлень (для блокових роздільних кодів у загальному вигляді N _Д =q^k, зокрема для двійкових кодів N_Д =2 ^k);
• повна кількість кодових комбінацій N - кількість всіх можливих комбінацій для даного коду, яка дорівнює у загальному вигляді N = qⁿ, зокрема для двійкового коду N =2 ⁿ;
• надмірність коду R_над, яка визначається для роздільних двійкових кодів:

R_над=1-k/n=r/n,

та для нероздільних двійкових кодів:

R_над= 1–(log ₂ N_Д/log ₂ N);

• відносна швидкість коду R_к, яка характеризує ступінь використання в надмірному коді інформаційних можливостей його потужності:

R_к= 1– R_над;

для роздільних двійкових кодів маємо

R_к=k/n= 1– r/n;

для нероздільних двійкових кодів:

R_к=log ₂ N_Д/log ₂ N

• вага кодової комбінації w – для двійкового коду визначається кількістю одиниць у кодовій комбінації;
• кодова відстань d між двома кодовими комбінаціями однакової довжини визначається як кількість одноіменних елементів (розрядів) з різними значеннями символів (відстань Хеммінга);
• мінімальна кодова відстань d_min - визначається для коду в цілому як мінімальне значення кодових відстаней між усіма парами кодових комбінацій, що належать до даного коду. Мінімальна кодова відстань визначає його здатність виявляти та виправляти помилки.

Так, для кодів, що виявляють помилки, d_min повинна мати значення: d_min ³ q_d + 1, для кодів, що виправляють помилки: d_min ³ 2q_c + 1, де q_d – кратність помилки, що виявляється кодом, q_c – кратність помилки, що виправляється кодом.

 

Задача 2.1

Алфавіт дискретногоджерела інформації налічує 64 символи, які кодуються в кодері рівномірним двійковим завадостійким кодом довжиною n =8. Визначити надмірність такого коду.

Розв'язання. Для безнадмірного кодування 64 символів достатньо застосувати рівномірний двійковий код довжиною k=log ₂64=6. Це число визначає кількість інформаційних елементів.

Тоді надмірність завадостійкого коду

R_над =1– k/n =1–6 / 8=1 / 4 = 0,25.

 

Задача 2.2 (для самостійного розв’язання)

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

 

 

Таблиця 2.1

№ варіанта	Кількість повідомлень, N	Довжина коду, n	Rнад

 

 

1. Системи числення

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

Назва системи числення походить від основи (алфавіту) q: q = 2 - двійкова, q = 8 – вісімкова, q = 16 – шістнадцяткова системи числення тощо.

Для запису чисел у десятковій системі використовують 10 цифр (0, 1, 2, 3, 4, 5, 6, 7, 8, 9); у двійковій - дві (0 і 1); у вісімковій — вісім (0, 1, 2, 3, 4, 5, 6, 7), а в шістнадцятковій - 16 знаків, з них - 10 цифр (0...9) і шість літер (А, В, С, D, Е, F).

Алгоритм перетворення цілих чисел між системами числення.

Перетворення числа з системи з основою p в систему з основою q.

Введемо позначення:

· ціле число в початковій системі числення з основою p – Z_p;

· правильний дріб в початковій системі числення з основою q – Z_q;

· перетворення між ними Z_pà Z_q.

З практичної точки зору зручні варіанти з проміжним перетворенням:

Z_pàZ₁₀àZ_q

Перетворення Z_pàZ₁₀

Це перетворення витікає з представлення Z_p у вигляді ряду

,

де - цифри числа, n – загальна кількість цифр числа.

Задача 3.1

Виконати перетворення (443)₅àZ₁₀

Розв'язання.

Перетворення Z₁₀àZ_q

Алгоритм перетворення Z₁₀àZ_q заснований на операції цілочисельного ділення:

· Цілочисельно розділити початкове число Z₁₀ на основу нової системи числення q і знайти остачу від ділення – це буде цифра 0-го розряду числа Z_q.

· Частку від ділення знову цілочисельно розділити на q з виділенням остачі; процедуру повторювати, поки частка від ділення не стане менше q.

· Останню частку і остачі від ділення, що утворилися, розташовують в порядку, зворотньому порядку їх отримання, і представляють Z_q.

Задача 3.2

Виконати перетворення (100)₁₀àZ₂

Розв'язання.

-100 | 2__

10 | -50 | 2 __

0 4 -25 | 2 __

-10 2_ -12 | 2__

10 -5 12 -6 | 2___

0 4 0 6 -3 | 2__

1 0 2 1

1 ←

(100)₁₀à(1100100)₂.

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

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

Задача 3.3

Виконати перетворення (100)₁₀àZ₁₆.

Розв'язання. Спочатку робимо перетворення (100)₁₀àZ₂: (100)₁₀ = (1100100)₂. Потім отримане число розбиваємо на тетради і доповнюємо нулями старші розряди: 0 110 та 0100. В результаті отримали два полубайта, кожен з якого перетворюємо на шістнадцяткові цифри: 6 та 4. Отже, (100)₁₀ = (64)₁₆.

Задача 3.4 (для самостійного розв’язання)

Виконати перетворення (10010)₂àZ₁₀; (64)₁₆àZ₁₀; (375)₈àZ₁₀; (745)₈àZ₂; (22)₈àZ₂. Заповнити даними таблицю 3.1:

Таблиця 3.1

Числа
десяткові	двійкові	Вісімкові	шістнадцяткові

4. Основні операції над елементами поля. Кодова відстань.

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