Кодування

[ виправити ] текст може містити помилки, будь ласка перевіряйте перш ніж використовувати.

скачати

Тема реферату: "КОДУВАННЯ"
1. ОСНОВНІ ПОНЯТТЯ І ВИЗНАЧЕННЯ ТЕОРІЇ КОДУВАННЯ
Оптимальним статистичними (економним) кодуванням називається кодування, при якому забезпечується розподіл часу на передачу окремих символів алфавіту в залежності від апріорних ймовірностей їх появи:
; (1)
де C п - пропускна здатність каналу; p i - апріорна ймовірність i-й кодової комбінації; t i-тривалість i-й кодової комбінації.
Оптимальними нерівномірними кодами (ОНК) - називаються коди, в яких символи алфавіту кодуються кодовими словами мініма-льно середньої довжини.
Принципи побудови оптимальних кодів:
1. Кожна кодова комбінація повинна містити максимальну кількість інформації, що забезпечує максимальну швидкість передачі даних.
2. Символів первинного алфавіту, що мають найбільшу ймовірність появи в повідомленні, присвоюються більш короткі кодові слова, при цьому, середня довжина кодових комбінацій має мінімально-можливу довжину.
При такому кодуванні надмірність коду, яка викликана нерівній ймовірністю символів алфавіту, зводиться до мінімуму (практично до нуля). Оптимальні коди є нерівномірними блочними кодами, при їх побудові необхідно забезпечити однозначність декодування. Префіксним (непріводімим) - називається код, в якому жодна кодова комбінація не є початком іншої. Для забезпечення цієї властивості кодові комбінації повинні записуватися від кореня кодового дерева.
Можливість однозначного декодування нерівномірного коду забезпечується виконанням вимоги разделимости (префіксного) кодових комбінацій.
При нерівномірному кодуванні проводиться стиснення даних. Стиснення даних використовується як при зберіганні даних у пам'яті, так і при їх передачі. Оптимальне кодування можна використовувати тільки в каналах без перешкод або у випадку низької вимогливості до достовірності переданої інформації.
Існує багато методів оптимального, статистичного кодування. Найбільш часто використовують оптимальне кодування за методом Шеннона - Фано і Хаффмена.
2. КОД Шенона-Фано
Кодування за методом Шеннона - Фано здійснюється наступним чином:
1. Безліч символів, з яких формуються повідомлення, записуються в порядку убування їх апріорних ймовірностей.
2. Подальше побудова коду проводиться методом послідовного ділення навпіл. Символи повідомлення розбиваються на дві групи з приблизно рівними ймовірностями (оскільки за відсутності статистичного зв'язку між символами швидкість передачі максимальна за умови рівної ймовірності передачі символів). Якщо рівної ймовірності в підгрупах досягти не можна, то бажано щоб сумарна ймовірність нижньої підгрупи була більше верхньої.
3. Всім символам верхньої групи приписується кодовий символ 1, а символам нижньої - 0. Можна, навпаки, тому що для кодової реалізації байдуже 0 або 1, але з точки зору потужності, краще, якщо в кодової комбінації менше одиниць.
4. Потім кожна підгрупа аналогічним чином розбивається на підгрупи по можливості з однаковими ймовірностями. Розбиття здійснюється до тих пір, поки в кожній підгрупі залишиться по одному символу.
Приклад побудови коду наведено в таблиці 1.
Таблиця 1
a i
p i
Розбиття
Кодова комбінація
Довжина
a 1
a 2
a 3
a 4
1 / 2
1 / 4
1 / 8
1 / 8
} 1
0} 1
0} 1
} 0
1
01
001
000
? t
2? T
3? T
3? T
Побудований код є префіксним.
Наприклад: отримана кодова послідовність 11100001 однозначно декодується як:
1 1 1 000 1 01 => a 1 a 1 a 1 a 4 a 1 a 2.
a 1 a 1 a 1 a 4 a 1 a 2
Застосовуючи статистичне кодування можна отримати результат, близький до ідеального кодування з Шеннону.
Середня довжина кодової комбінації, при використанні двійкового коду в якості вторинного, дорівнює
, (2)
де l i - довжина i-ї комбінації; N-основа первинного коду.
Ефективність ОНК максимальна при
; . (3)
Коефіцієнт відносної ефективності (коефіцієнт використання пропускної спроможності) дорівнює
. (4)
Коефіцієнт статистичного стиснення (зменшення кількості двійкових розрядів на символ повідомлення при використанні статистичного кодування в порівнянні зі звичайним кодуванням) дорівнює
. (5)
Для розглянутого прикладу при тривалості символу кодової комбінації (0 або 1) рівною t середня довжина і середня тривалість кодової комбінації, відповідно рівні:

Ентропія джерела дорівнює


При цьому: До ое = 1,75 / 1,75 = 1; До cc = 2 / 1, 75 = 1,14.
Швидкість передачі інформації
, (6)
тобто коефіцієнт використання пропускної здатності каналу дорівнює 1, а значить, має місце ідеальне використання каналу (оптимальне статистичне кодування).
Якщо підгрупи мають не однакову сумарну ймовірність, то коефіцієнт менше 1. Для рівномірного коду , При цьому
.
Недолік коду ОНК - низька завадостійкість, тому що втрата одного розряду може означати втрату символу.
3. КОД Хаффмена
Кодування за методом Хаффмена здійснюється наступним чином:
1. Всі підлягають кодуванню символи записуються в порядку убування їх апріорних ймовірностей. Якщо деякі символи мають однакові ймовірності, то їх розташовують поруч у довільному порядку.
2. Вибирають символи з мінімальними ймовірностями по 2 і одному приписують 0, а іншому 1.
3. Вибрані символи об'єднують в проміжні символи з сумарною ймовірністю.
4. Знову знаходять пару символів з найменшими ймовірностями і надходять аналогічно.
У таблиці 2 наведено приклад кодування за методом Хаффмена для джерела повідомлень із заданими ймовірностями символів алфавіту:
x 1 = 0,4; x 2 = x 5 = 0,2; x 3 = 0,1; x 4 = x 6 = 0,05.
Таблиця 2
Символ
p i
Граф коду Хаффмена
Код
x 1
x 2
x 5
x 3
x 4
x 6
0,4
0,2
0,2
0,1
0,05
0,05
1
(1,0)
1 0
(0,6)
1 0
(0,4)
1 0
(0,2)
1 0
(0,1)
0
1
01
001
0001
00001
00000

Ентропія джерела дорівнює


Середня довжина кодової комбінації даного коду

Довжина кодової комбінації примітивного коду визначається співвідношенням
(7)
Округляючи до найближчого цілого в більшу сторону, отримаємо l = 3.
Ефективність ОНК максимальна, якщо .
Коефіцієнт відносної ефективності дорівнює
.
Коефіцієнт статистичного стиснення дорівнює
.
Нерівномірний код можна передавати блоками заданої довжини, а на приймальній стороні декодувати всю послідовність.
Приклад 1. Побудувати оптимальні нерівномірні коди (ОНК) за методом Шеннона-Фано і за методом Хаффмена для передачі повідомлень, в яких ймовірності символів первинного алфавіту рівні:

p (a 1) = 0,1; p (a 2) = 0,07; p (a 3) = 0,02; p (a 4) = 0,17;
p (a 5) = 0,42; p (a 6) = 0,09; p (a 7) = 0,08; p (a 8) = 0,05.
Оцінити ефективність кожного коду, тобто наскільки вони близькі до оптимальних. Визначити ємність (пропускну здатність) каналу зв'язку для кожного коду, якщо швидкість передачі двійкових символів (V = 1 / t) дорівнює 1000 симв / с, тобто час передачі одного символу вторинного алфавіту (двійкового символу) дорівнює t = 0,001 с = 1мкс.
Рішення: Побудуємо код за методом Шеннона-Фано, використовуючи сле-дме алгоритм:
1. Символи повідомлення в своєму розпорядженні в порядку убування їх апріорних ймовірностей.
2. Вихідний ансамбль кодованих символів розбиваємо на дві групи з приблизно рівними ймовірностями (краще, якщо сумарна ймовірність верхньої групи менше).
3. Верхньої групі присвоюємо символ 1, а нижній 0.
4. Процес поділу повторюємо до тих пір, поки в кожній підгрупі залишиться по одному символу.
Процес побудови коду наведемо в таблиці 3.
Таблиця 3
a i
p (a i)
Розбиття
Код
l i
p i l i
a 5
a 4
a 1
a 6
a 7
a 2
a 8
a 3
0,42
0,17
0,10
0,09
0,08
0,07
0,05
0,02
} 0
1 0} 0
} 1
1 0} 0
} 1
1} 0
} 0
} 1
0
100
101
1100
1101
1110
11110
11111
1
3
3
4
4
4
5
5
0,42
0,51
0,3
0,36
0,32
0,28
0,25
0,1

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

= - (0,42 × log 2 0,42 +0,17 × log 2 0,17 +0,1 × log 2 0,1 +0,09 × log 2 0,09 +0,08 × log 2 0 , 08 +
+0,07 × log два 0,07 +0,05 × log 2 0,05 +0,02 × log 2 0,02) = 0,5256 +0,4346 +0,3322 +
+0,3126 +0,2915 +0,2686 +0,2161 +0,1129 = 2,49 біт / симв.
Оцінимо ефективність побудованого коду, яка визначається коефіцієнтами відносної ефективності та статистичного стиснення.
Коефіцієнт відносної ефективності дорівнює

Коефіцієнт статистичного стиснення дорівнює
.
Необхідна пропускна здатність каналу зв'язку для передачі повідомлень оптимальними кодами обчислюється за формулою
.
Для отриманого коду вона дорівнює
З = 10 3 × 2,54 = 2,54 Кбіт / с.
Побудуємо код за методом Хаффмена, використовуючи наступний алгоритм:
1. Символи первинного алфавіту в своєму розпорядженні в порядку убування їх ймовірностей.
2. Останні два символи об'єднуємо в один, із сумарною ймовірністю.
3. Упорядковуємо символи з урахуванням новостворених і останні два символи об'єднуємо в один із сумарною ймовірністю. Цю процедуру повторюємо до тих пір, поки не залишиться два символи.
4. Будуємо кодове дерево, вершиною якого є 1 (сумарна вірогідність всіх символів повідомлення).
При побудові дерева символи, в принципі, можна не впорядковувати.
Процес побудови коду наведено в таблиці 4.
Коефіцієнт статистичного стиснення дорівнює
.
Коефіцієнт відносної ефективності
.
Необхідна пропускна здатність каналу зв'язку
Кбіт / c.
Таблиця 4
а i
p (a i)
Кодове дерево
Код
l i
p i l i

a 5
a 4
a 1
a 6
a 7
a 2
a 8
a 3
0,42
0,17
0,10
0,09
0,08
0,07
0,05
0,02
1 (1,0)
1 1 0
(0,34) (0,58)
0 1 0
(0,24)
1 0
(0,17)
0
1
(0,14)
1 0
(0,7)
0
1
011
001
0101
0100
0001
00001
00000
1
3
3
4
4
4
5
5
0,42
0,51
0,3
0,36
0,32
0,28
0,25
0,1
. .
Побудовані коди Шеннона - Фано і Хаффмена рівноцінні, оскільки вони мають однакові показники ефективності. Обидва коди відрізняються від оптимального на 2%.

4. Завадостійке КОДУВАННЯ

Завадостійкість-здатність системи здійснювати прийом інформації в умовах наявності перешкод в лінії зв'язку і спотворень у внутрішньо апаратних трактів. Завадостійкість забезпечує надійність і достовірність переданої інформації (даних). Ми будемо в основному розглядати двійкові коди. Двійкові (коди) дані передаються між обчислювальними терміналами, літальними апаратами, супутниками і т. д.
Передача даних в обчислювальних системах чутлива до малої частки помилку, тому що одиночна помилка може істотно порушити процес обчислень.
Найбільш часто помилки з'являються в УВВ, шинах, пристроях пам'яті. УВВ містять велику кількість елементів, помилки обумовлюються старінням елементів, погіршенням якості електричних з'єднань, расфазіровкой сигналів. Значна частина помилок припадає на ВП, внаслідок відмови окремих ІС або всієї ІС, помилок пов'язаних з флуктуацією напруги харчування і т. д.
У системах з багатьма користувачами і поділом за часом довгі виконавчі повідомлення поділяються на пакети.
Повідомлення, подані довгими послідовностями бітів, звичайно розбиваються на більш короткі послідовності бітів, називаються пакетами. Пакети можна передати по мережі як незалежні об'єкти і збирати з них повідомлення на кінцевому пункті. Пакет, забезпечений ім'ям і керуючими бітами на початку і в кінці, називається кадром. Управління лінією передачі даних здійснюється за спеціальним алгоритмом, званому протоколом.
Наявність перешкод ставить додаткові вимоги до методів кодування. Для захисту інформації від перешкод необхідно вводити в тому чи іншому вигляді надмірність: підвищення потужності сигналу; повторення повідомлень; збільшення довжини кодової комбінації і т. д.
Збільшення потужності сигналів призводить до ускладнення і подорожчання апаратури, крім того, в деяких системах передачі інформації є обмеження для передачі потужності, наприклад, супутниковий зв'язок.
Повторна передача повідомлень вимагає наявності буферів для зберігання інформації та наявності зворотного зв'язку для підтвердження достовірності переданої інформації. При цьому, значно падає швидкість передачі інформації, крім того цей метод не завжди м. б. використаний, наприклад, в система реального часу.
Одним з найбільш ефективних методів підвищення достовірності та надійності передачі даних є завадостійке кодування, що дозволяє за рахунок внесення додаткової надмірності (збільшення мінімального кодового відстані) у кодових комбінаціях переданих повідомлень забезпечити можливість виявлення та виправлення одиночних, кратних і групових помилок.
Мінімальна кодова відстань характеризує завадостійкість і надмірність повідомлень. У залежності від величини мінімального кодового відстані існують коди, які виявляють і виправляють помилки.
Кодова відстань - d визначається як кількість одиниць в результаті підсумовування за модулем два двох кодових комбінацій. Мінімальна кодова відстань d 0 - мінімальне з кодових відстаней всіх можливих кодових комбінацій.
Для виявлення r помилок мінімальне кодова відстань дорівнює:
d 0 ³ r +1. (8)
Для виявлення r помилок та виправлення s помилок мінімальне кодова відстань дорівнює:
d 0 ³ r + s +1. (9)
Тільки для виправлення помилок мінімальне кодова відстань дорівнює:
d 0 ³ 2s +1. (10)
5. Виявляється КОДИ
Виявляють коди - це коди, що дозволяють виявити помилку, але не виправити її. Найпростіший спосіб виявлення помилки це додавання до послідовності бітів даних ще одного біта-біта перевірки на парність (непарність) значення, якого дорівнює сумі по модулю два вихідної послідовності бітів. Найчастіше організується перевірка на непарність.
У символьному коді ASCII до семи бітам коду додається восьмий біт перевірки на парність - k 1.
S 1 S 2 S 3 S 4 S 5 S 6 S 7 K 1
1
1
0
1
1
0
1
1
Однобітовий перевірка дозволяє виявити будь-яку одиничну помилку, дві помилки знайти не можна, в загальному випадку виявляється будь непарна кількість помилок.
Внесення надмірності за рахунок збільшення довжини кодової комбінації призводить до зниження швидкості передачі інформації.
Якщо швидкість ідеально використовує канал, то
. (11)
Якщо кодова комбінація довжиною n містить k інформаційних і m контрольних розрядів (n = k + m), то

.
Для коду ASCII n = 8 і k = 7
,
тобто введення одного надлишкового розряду призводить до зменшення пропускної здатності каналу зв'язку на 12,5%.
Найчастіше шуми (блискавки, розрив і т.д.) породжують довгі пакети помилок і ймовірність парного і непарного числа помилок однакова, а значить і однобітовий перевірка не ефективна.
Перевірка на парність по вертикалі і горизонталі. При цьому послідовність бітів даних перебудовується в двомірний масив, і обчислюються біти на парність, як для кожного рядка, так і для кожного стовпця.
При цьому можна виявити кілька помилок, якщо вони не розташовуються в однакових рядках і стовпцях.
Найчастіше використовується при передачі даних коду ASCII, кожен символ можна вважати рядком масиву. Така перевірка може не тільки встановити факт помилки, але і виявити її місце, а значить, є принципова можливість її виправлення, хоча це практично не використовується.
1 0 1 1 0 1 1 1
0 1 0 0 0 1 0 0
1 0 1 0 0 1 0 1
1 1 0 0 1 0 1 0
0 0 0 1 0 1 0 0
1 0 0 0 1 0 0
Після виявлення помилок іноді можна повторити передачу повідомлень, іноді після виявлення помилки робиться друга і навіть третя спроба передачі повідомлення.
Перевірка на парність широко використовується на ЕОМ, як на апаратній, так і на програмному рівні.
Наприклад, при зчитуванні з магнітної стрічки у разі, коли умова на парність не виконується, то проводиться повторне зчитування, тобто якщо відбулася мала втрата намагніченості, то після другої спроби може бути зчитування відбудеться правильно.
Приклад 1. Символи алфавіту джерела кодуються семіразрядним двійковим кодом з вагою кодових векторів (кількістю одиниць в кодової комбінації) w = 3. Визначити необхідну потужність коду і його надмірність.
Рішення: Потужність семіразрядного коду дорівнює N = 2 7 = 128.
Так як для кодування використовуються тільки кодові вектора з вагою три, то кількість таких векторів у семіразрядном коді одно

Надмірність коду дорівнює R = 1 - log 2 K / log 2 N = 0,265.

СПИСОК ВИКОРИСТАНОЇ ЛІТЕРАТУРИ
1. Семенюк В. В. Економне кодування дискретної інформації. - СПб.: СПб ГІТМО (ТУ), 2001;
2. Мастрюков Д. Алгоритми стиснення інформації. Ч. 1. Стиснення по Хаффмену / / Монітор, 1993. - № 7 - 8 - С. 14 - 20;
3. Мастрюков Д. Алгоритми стиснення інформації. Ч. 2. Арифметичне кодування / / Монітор, 1994 - № 1 - С. 20 - 23;
4. Ф.Дж.Мак-Вільямс, Н.Дж.А.Слоен, Теорія кодів, що виправляють помилки, Москва, "Зв'язок", 1979.
5. . Лідл, Г. Нідеррайтер, Кінцеві поля, Т. 1,2, Москва, "Світ", 1988.
6. Т. касами, Н. Токур, Є. Івадарі, Я. Інагаки, Теорія кодування, Москва, "Світ", 1978.
7. У. Петерсон, Е. Уелдон, Коди, що виправляють помилки, Москва, "Світ", 1976.
8. Е. Берлекемп, Алгебраїчна теорія кодування, Москва, "Світ", 1971.
9. Дискретна математика і математичні питання кібернетики. Т.1. / Ю.Л. Васильєв, Ф. Я. Ветухновскій, В. В. Глаголєв, Ю. І. Журавльов, В. І. Левенштейн, С. В. Яблонський. Під загальною редакцією С. В. Яблонського та О. Б. Лупанова. - М.: Головна редакція фізико - математичної літератури вид-ва «Наука», 1974
10. Лідовскій В. В. Теорія інформації: Навчальний посібник. - М.: Компанія Супутник +, 2004
Додати в блог або на сайт

Цей текст може містити помилки.

Програмування, комп'ютери, інформатика і кібернетика | Реферат
60.9кб. | скачати


Схожі роботи:
Метод словникового кодування Зеева Лемпела Диференціальне кодування
Метод словникового кодування Зеева-Лемпела Диференціальне кодування
Арифметичне кодування Кодування довжин повторень
Основи кодування
Кодування мовлення
Кодування інформації
Завадостійке кодування
Кодування зображень
Штрихове кодування
© Усі права захищені
написати до нас