Теорія інформації та кодування
Визначення кількості інформації в повідомленні, ентропії повідомлень в каналі зв’язку, ентропії двох джерел повідомлень. Продуктивність джерела повідомлень, швидкість передачі інформації та пропускна здатність каналу зв’язку. Кодування, стиснення даних.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | контрольная работа |
| Язык | украинский |
| Дата добавления | 07.06.2012 |
| Размер файла | 590,8 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Міністерство освіти та науки України
Черкаський національний університет
імені Богдана Хмельницького
Кафедра інформаційних систем та медичних технологій
РОЗРАХУНКОВО-ГРАФІЧНА РОБОТА
з дисципліни «Теорія інформації та кодування»
Перевірив:
ст. викл. Колос П.О.
Виконала:
студентка групи ЗКС-07
Дейнеко І.В.
Черкаси 2011
1. Визначення кількості інформації повідомлення
канал інформація ентропія повідомлення кодування
Варіант 5. Алфавіт джерела повідомлень місить 879 символів. Кожне повідомлення складеться з 57 рівноймовірних знаків. Передано 555 повідомлень. Яка загальна кількість інформації?
Розв'язок:
Кількість інформації, яка міститься в одному повідомленню обраховується за формулою Хартлі:
Загальна кількість інформації:
2. Визначення ентропії повідомлень в каналі зв'язку
Варіант 5. Дослідження каналу зв'язку між джерелом А та спостерігачем В виявило такі умовні ймовірності вибору повідомлень :
Визначити часткову та загальну умовну ентропію в цьому каналі при рівноймовірному виборі джерелом A та при PA = {0,3; 0,3; 0,4}.
Розв'язок:
Часткова умовна ентропія обраховується за формулою:
Загальна умовна ентропія обраховується за формулою:
Загальна умовна ентропія при рівноймовірному виборі джерелом :
Загальна умовна ентропія при :
3. Визначення ентропії двох джерел повідомлень
Варіант 5. Два статистично незалежних джерела А та В визначаються матрицею сумісних імовірностей:
Визначити часткову та загальну умовну ентропію, ентропію об'єднання, безумовну ентропію цих джерел, а також кількість інформації, що припадає на пару повідомлень .
Розв'язок:
Знаходимо розподіл ймовірностей джерел та :
Обраховуємо матриці умовних ймовірностей:
,
Часткова умовна ентропія:
Загальна умовна ентропія:
Безумовна ентропія:
Ентропія об'єднання:
Також ентропію об'єднання можна обрахувати за формулою:
Кількість інформації, що припадає на пару повідомлень = 2,9 біт.
4. Визначення продуктивності джерела повідомлень та швидкості передачі інформації
Варіант 5. Повідомлення передаються взаємонезалежними, рівноймовірними символами тривалістю 62·10 -5 с. Визначити продуктивність джерела повідомлень та швидкість передачі кожного символу, якщо обсяг алфавіту дорівнює 72.
Розв'язок:
Так як повідомлення передаються рівноймовірними символами, середня тривалість передачі одного символу:
с.
Обсяг алфавіту: m=72.
Безумовна ентропія джерела А:
біт
Для каналу зв'язку без завад
Продуктивність джерела повідомлень та швидкість передачі кожного символу:
5. Визначення пропускної здатності каналу зв'язку
Варіант 5. Визначити пропускну здатність каналу зв'язку між джерелами А та В матриця ймовірностей якого при = 5·10 -5 с має вигляд:
Розв'язок:
Обраховуємо матрицю умовних ймовірностей :
Часткові умовні ентропії:
,
Загальна умовна ентропія:
Безумовна ентропія:
Пропускна здатність каналу зв'язку:
6. Ефективне кодування
Варіант 5. Алфавіт джерела повідомлень , імовірності появи кожного зі знаків у повідомленні P = {0,08; 0,01; 0,05; 0,04; 0,2; 0,1; 0,01; 0,2; 0,1; 0,21}. Закодувати повідомлення 7985686345699 методом Шеннона-Фано та методом Хаффмена. Порівняти ефективність отриманих кодів.
Розв'язок:
Теоретичний мінімум довжини повідомлення
Метод Шенона-Фано:
Всі знаки поділяються на дві групи так, щоб суми імовірностей кожної з груп були приблизно однакові. Усім знакам першої групи поточна знакова комбінація призначається 1, другої - 0. Кожну з груп знову поділяють таким же чином, поки в кожній з груп не залишиться по 1 знаку.
|
Знак |
Імовірність |
Корові комбінації |
||||||
|
9 |
0,21 |
1 |
1 |
|||||
|
4 |
0,2 |
1 |
0 |
|||||
|
7 |
0,2 |
0 |
1 |
1 |
||||
|
5 |
0,1 |
0 |
1 |
0 |
||||
|
8 |
0,1 |
0 |
0 |
1 |
1 |
|||
|
0 |
0,08 |
0 |
0 |
1 |
0 |
|||
|
2 |
0,05 |
0 |
0 |
0 |
1 |
|||
|
3 |
0,04 |
0 |
0 |
0 |
0 |
1 |
||
|
1 |
0,01 |
0 |
0 |
0 |
0 |
0 |
1 |
|
|
6 |
0,01 |
0 |
0 |
0 |
0 |
0 |
0 |
Середня довжина кодової інформації:
Кодування повідомлення «7985686345699»:
|
7 |
9 |
8 |
5 |
6 |
8 |
6 |
3 |
4 |
5 |
6 |
9 |
9 |
|
|
011 |
11 |
0011 |
010 |
000000 |
0011 |
000000 |
00001 |
10 |
010 |
000000 |
11 |
11 |
Повідомлення «7985686345699» в закодованому вигляді:
01111001 10100000 00001100 00000000 11001000 00001111
Довжина закодованого повідомлення - 48 біт
Метод Хаффмена:
Сума двох найменших імовірностей додається та записується в заново відсортовану множину імовірностей. Процес продовжується поки не залишиться два числа, сума яких складає 1. За цими даними будується дерево та позначаються дуги (права дуга - 1, ліва - 0).
|
Знак |
Імовірність |
||||||||||
|
9 |
0,21 |
0,21 |
0,21 |
0,21 |
0,21 |
0,21 |
0,38 |
0,41 |
0,59 |
1 |
|
|
4 |
0,2 |
0,2 |
0,2 |
0,2 |
0,2 |
0,21 |
0,21 |
0,38 |
0,41 |
||
|
7 |
0,2 |
0,2 |
0,2 |
0,2 |
0,2 |
0,2 |
0,21 |
0,21 |
|||
|
5 |
0,1 |
0,1 |
0,1 |
0,11 |
0,18 |
0,2 |
0,2 |
||||
|
8 |
0,1 |
0,1 |
0,1 |
0,1 |
0,11 |
0,18 |
|||||
|
0 |
0,08 |
0,08 |
0,08 |
0,1 |
0,1 |
||||||
|
2 |
0,05 |
0,05 |
0,06 |
0,08 |
|||||||
|
3 |
0,04 |
0,04 |
0,05 |
||||||||
|
1 |
0,01 |
0,02 |
|||||||||
|
6 |
0,01 |
Кодове дерево:
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Кодові комбінації:
|
Знак |
Імовірність |
Корові комбінації |
||||||
|
9 |
0,21 |
1 |
0 |
|||||
|
4 |
0,2 |
0 |
0 |
|||||
|
7 |
0,2 |
1 |
1 |
1 |
||||
|
5 |
0,1 |
0 |
1 |
0 |
||||
|
8 |
0,1 |
1 |
1 |
0 |
1 |
|||
|
0 |
0,08 |
1 |
1 |
0 |
0 |
|||
|
2 |
0,05 |
0 |
1 |
1 |
0 |
|||
|
3 |
0,04 |
0 |
1 |
1 |
1 |
1 |
||
|
1 |
0,01 |
0 |
1 |
1 |
1 |
0 |
1 |
|
|
6 |
0,01 |
0 |
1 |
1 |
1 |
0 |
0 |
Середня довжина кодової комбінації:
Кодування повідомлення «7985686345699»:
|
7 |
9 |
8 |
5 |
6 |
8 |
6 |
3 |
4 |
5 |
6 |
9 |
9 |
|
|
111 |
10 |
1101 |
010 |
011100 |
1101 |
011100 |
01111 |
00 |
010 |
011100 |
10 |
10 |
Повідомлення «7985686345699» в закодованому вигляді:
11110110 10100111 00110101 11000111 10001001 11001010
Довжина закодованого повідомлення - 48 біт
Середня довжина кодової комбінації і довжина закодованого повідомлення для обох методів є однаковими. Отже кодування заданого повідомлення обома методами мають однакову ефективність.
7. Завадостійке кодування. Прямокутні коди
Варіант 5. Побудувати прямокутний завадостійкий код для повідомлення: „Глобальна комп'ютерна мережа”. В якості двійкових кодів символів використовувати ASCII коди. Продемонструвати завадостійкість на прикладах виникнення помилок. Виконати як етап кодування так і етап декодування.
Розв'язок:
Таблиця ASCII кодів для заданого повідомлення:
|
Символ |
ASCII код |
||
|
Г |
131 |
10000011 |
|
|
л |
171 |
10101011 |
|
|
о |
174 |
10101110 |
|
|
б |
161 |
10100001 |
|
|
а |
160 |
10100000 |
|
|
ь |
236 |
11101100 |
|
|
н |
173 |
10101101 |
|
|
«Пробіл» |
32 |
00100000 |
|
|
к |
170 |
10101010 |
|
|
м |
172 |
10101100 |
|
|
п |
175 |
10101111 |
|
|
` |
96 |
01100000 |
|
|
ю |
238 |
11101110 |
|
|
т |
226 |
11100010 |
|
|
е |
165 |
10100101 |
|
|
р |
224 |
11100000 |
|
|
ж |
166 |
10100110 |
Прямокутний код для заданого повідомлення:
|
Символ |
Двійкове представлення |
|||||||||
|
Г |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
|
|
л |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
|
|
о |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
|
|
б |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
|
|
а |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
л |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
|
|
ь |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
|
|
н |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
|
|
а |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
||
|
к |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
|
|
о |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
|
|
м |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
|
|
п |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
|
|
` |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
ю |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
|
|
т |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
|
|
е |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
|
|
р |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
|
|
н |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
|
|
а |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
||
|
м |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
|
|
е |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
|
|
р |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
|
|
е |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
|
|
ж |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
|
|
а |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
1 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
В даній таблиці, для кожного рядка і кожного стовпчика додається розряд для перевірки парності.
Виникнення одиничної помилки:
Одинична помилка призведе до порушення парності одночасно і у рядку, і у стовпчику. Припустимо виникла помилка (помилковий біт, а також відповідні розряди для перевірки парності, виділені заливкою):
|
Символ |
Двійкове представлення |
|||||||||
|
Г |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
|
|
л |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
|
|
о |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
|
|
б |
1 |
0 |
1 |
1(0) |
0 |
0 |
0 |
1 |
0(1) |
|
|
а |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
л |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
|
|
ь |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
|
|
н |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
|
|
а |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
||
|
к |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
|
|
о |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
|
|
м |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
|
|
п |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
|
|
` |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
ю |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
|
|
т |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
|
|
е |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
|
|
р |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
|
|
н |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
|
|
а |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
||
|
м |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
|
|
е |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
|
|
р |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
|
|
е |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
|
|
ж |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
|
|
а |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
1 |
0 |
1 |
1(0) |
0 |
1 |
0 |
0 |
В результаті перевірки, розраховані значення парності відрізняються від правильних значень (вказані в дужках) одночасно і в рядку, і в стовпчику, а номери рядка і стовпчика, в яких виникла помилка, вказують на помилковий розряд. Після виправлення помилки отримуємо правильний код.
Після перевірки та виправлення помилок двійковий код буде декодуватись, тобто перетворюватись у ASCII коди символів та відтворювати власне самі символи. Так, після отримання та декодування повідомлення буде наступним: «Глобальна комп'ютерна мережа». Слід зазначити, що прямокутні коди здатні виявляти лише одиничні помилки, якщо ж їх кількість буде більшою, відповідно і повідомлення буде з помилками.
8. Завадостійке кодування. Код Хеммінга
Варіант 5. Побудувати код Хеммінга для двійкового повідомлення „11111111”. Продемонструвати завадостійкість на прикладах виникнення помилок.
Розв'язок:
Кількість розрядів: k=8.
Кількість допоміжних розрядів, m, для побудови коду Хеммінга обирається так, щоб виконувалась нерівність:
Отже m=4, а загальна кількість розрядів n=8+4=12.
Для m=4 перевірочні позиції степені двійки: 1, 2, 4, 8.
|
Розряд |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
|
|
Символ |
_ |
_ |
1 |
_ |
1 |
1 |
1 |
_ |
1 |
1 |
1 |
1 |
Розрахунок перевірочних розрядів:
1 перевірочний розряд:
Необхідно, щоб перевірка на парність розрядів 1, 3, 5, 7, 9, 11 давала 0.
Отже розряд 1 повинен мати значення 1.
2 перевірочний розряд:
Необхідно, щоб перевірка на парність розрядів 2, 3, 6, 7, 10, 11 давала 0.
Отже розряд 2 повинен мати значення 1.
3 перевірочний розряд:
Необхідно, щоб перевірка на парність розрядів 4, 5, 6, 7, 12 давала 0.
Отже розряд 4 повинен мати значення 0.
4 перевірочний розряд:
Необхідно, щоб перевірка на парність розрядів 8, 9, 10, 11, 12 давала 0.
Отже розряд 8 повинен мати значення 0.
Код Хеммінга для повідомлення «11111111» матиме вигляд: 111011101111.
Демонстрація завадостійкості:
Припустимо, що в 5 розряді коду Хеммінга допущено помилку:
|
Розряд |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
|
|
Символ |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
Проводимо перевірки:
Перша перевірка на парність: 1, 3, 5, 7, 9, 11 = 1
Друга перевірка на парність: 2, 3, 6, 7, 10, 11 = 0
Третя перевірка на парність: 4, 5, 6, 7, 12 = 1
Четверта перевірка на парність: 8, 9, 10, 11, 12 = 0
Отримано двійкове число 0101 (оскільки розряди нумерувалися зліва на право)
Отже ми маємо помилку в 5 розряді. Виправляємо помилку і отримуємо правильне повідомлення: 111011101111.
9. Стиснення даних. Метод Лавінського
Варіант 5. Стиснути повідомлення із завдання №7 методом Лавінського. При розрахунках використовувати ASCII коди символів повідомлення. Продемонструвати як етап компресії, так і декомпресії.
Розв'язок:
Записуємо повідомлення «Глобальна комп'ютерна мере» у вигляді ASCII кодів та сортуємо ASCII коди за неспаданням:
|
Символ |
ASCII коди |
Відсортовані ASCII коди |
||
|
Г |
131 |
32 |
||
|
л |
171 |
32 |
||
|
о |
174 |
96 |
||
|
б |
161 |
131 |
||
|
а |
160 |
160 |
||
|
л |
171 |
160 |
||
|
ь |
236 |
160 |
||
|
н |
173 |
160 |
||
|
а |
160 |
161 |
||
|
32 |
165 |
|||
|
к |
170 |
165 |
||
|
о |
174 |
165 |
||
|
м |
172 |
166 |
||
|
п |
175 |
170 |
||
|
` |
96 |
171 |
||
|
ю |
238 |
171 |
||
|
т |
226 |
172 |
||
|
е |
165 |
172 |
||
|
р |
224 |
173 |
||
|
н |
173 |
173 |
||
|
а |
160 |
174 |
||
|
32 |
174 |
|||
|
м |
172 |
175 |
||
|
е |
165 |
224 |
||
|
р |
224 |
224 |
||
|
е |
165 |
226 |
||
|
ж |
166 |
236 |
||
|
а |
160 |
238 |
Кількість чисел у повідомленні: M=28.
Максимальне число, що містить повідомлення: N=238.
Для того, щоб закодувати число 238 необхідно 8 розрядів.
Пля кодування всього повідомлення необхідно: 28 чисел * 8 розрядів = 224 розряди.
Визначення кількості відрізків:
Визначення довжни відрізка:
Знаходимо та , що є степенями двійки і задовольняють умову:
Порівняння ефектів стиснення при та :
, відрізків.
Щоб закодувати 16 значень, потрібно 5 розрядів; 5, , розрядів.
, відрізків.
Щоб закодувати 32 значень, потрібно 6 розрядів; 6, 7, розрядів.
Оскільки , ефективність стиснення вища, обираємо .
|
# |
Діапазон |
Кількість чисел |
Числа, які потрапляють в діапазон |
||
|
Початкові |
Закодовані |
||||
|
0 |
(0..32) |
2 |
32,32 |
0,0 |
|
|
1 |
(33..64) |
0 |
|||
|
2 |
(65..96) |
1 |
96 |
0 |
|
|
3 |
(97..128) |
0 |
|||
|
4 |
(129..160) |
5 |
131,160,160,160,160 |
0,29,29,29,29 |
|
|
5 |
(161..192) |
15 |
161,165,165,165,166,170,171,171,172,172,173,173,174,174,175 |
0,4,4,4,5,9,10,10,11,11,12,12,13,13,14 |
|
|
6 |
(193..224) |
2 |
224,224 |
0,0 |
|
|
7 |
(225..256) |
3 |
226,236,238 |
0,10,12 |
Повідомлення в закодованому вигляді:
Для формування стиснутого повідомлення, для кожного відрізку спочатку записуємо кількість чисел (крім останнього), які попадають у даний відрізок, а потім записуємо самі закодовані числа. Стиснуте повідомлення (для зручності, кількість чисел у відрізках виділено):
2,0,0,0,1,0,0,5,0,29,29,29,29,15,0,4,4,4,5,9,10,10,11,11,12,12,13,13,14,2,0,0,0,10,12
Відновлення початкової послідовності чисел відбувається наступним чином. Читається перше число (в даному випадку 0) -- це кількість чисел у відрізку 0. Так як вона нульова, то наступне число -- кількість чисел у відрізку 1. Вона також нульова, тому наступне число -- кількість чисел у відрізку 2 -- вона дорівнює 2, отже до наступних двох чисел додаємо 32 (нижню межу відрізку 2) і отримуємо перші 2 числа початкової послідовності. Таким же чином відновлюються всі числа, доки не дійдемо до останнього відрізку -- для нього кількість чисел не записується.
10. Стиснення даних. Метод Лемпела-Зіва
Варіант 5. Стиснути повідомлення „ПРОПОНУВАННЯ ПОЗИКИ” методом Лемпела-Зіва. Продемонструвати як етап компресії, так і декомпресії.
Розв'язок:
«ПРОПОНУВАННЯ ПОЗИКИ» - повідомлення.
Довжина повідомлення n=19 символів.
q - доповнюючий знак.
P - номер за словником.
K - номер поточного знаку вихідного тексту.
Етап компресії:
|
Словник |
K |
N |
Стиснуте повідомлення |
|||
|
і |
D[i] |
P |
q |
|||
|
0 |
«» |
1 |
1 |
0 |
«П» |
|
|
1 |
«П» |
2 |
2 |
0 |
«Р» |
|
|
2 |
«Р» |
3 |
3 |
0 |
«О» |
|
|
3 |
«О» |
4 |
4 |
1 |
«О» |
|
|
4 |
«ПО» |
6 |
5 |
0 |
«Н» |
|
|
5 |
«Н» |
7 |
6 |
0 |
«У» |
|
|
6 |
«У» |
8 |
7 |
0 |
«В» |
|
|
7 |
«В» |
9 |
8 |
0 |
«А» |
|
|
8 |
«А» |
10 |
9 |
5 |
«Н» |
|
|
9 |
«НН» |
12 |
10 |
0 |
«Я» |
|
|
10 |
«Я» |
13 |
11 |
0 |
« » |
|
|
11 |
« » |
14 |
12 |
4 |
«З» |
|
|
12 |
«ПОЗ» |
17 |
13 |
0 |
«И» |
|
|
13 |
«И» |
18 |
14 |
0 |
«К» |
|
|
14 |
«К» |
19 |
15 |
13 |
«» |
|
|
15 |
«И» |
Довжина стиснутого повідомлення m=14, отже ефект стиснення 19-15=4 символи.
Після стиснення, словник зберігати непотрібно -- його буде відтворено із стиснутого подання під час декомпресії.
Етап декомпресії:
|
Словник |
Стиснуте повідомлення |
Прочитане повідомлення |
|||
|
i |
D[i] |
P |
q |
||
|
0 |
«» |
0 |
«П» |
«» |
|
|
1 |
«П» |
0 |
«Р» |
«П» |
|
|
2 |
«Р» |
0 |
«О» |
«ПР» |
|
|
3 |
«О» |
1 |
«О» |
«ПРО» |
|
|
4 |
«ПО» |
0 |
«Н» |
«ПРОПО» |
|
|
5 |
«Н» |
0 |
«У» |
«ПРОПОН» |
|
|
6 |
«У» |
0 |
«В» |
«ПРОПОНУ» |
|
|
7 |
«В» |
0 |
«А» |
«ПРОПОНУВ» |
|
|
8 |
«А» |
5 |
«Н» |
«ПРОПОНУВА» |
|
|
9 |
«НН» |
0 |
«Я» |
«ПРОПОНУВАНН» |
|
|
10 |
«Я» |
0 |
« » |
«ПРОПОНУВАННЯ» |
|
|
11 |
« » |
4 |
«З» |
«ПРОПОНУВАННЯ » |
|
|
12 |
«ПОЗ» |
0 |
«И» |
«ПРОПОНУВАННЯ ПОЗ» |
|
|
13 |
«И» |
0 |
«К» |
«ПРОПОНУВАННЯ ПОЗИ» |
|
|
14 |
«К» |
13 |
«» |
«ПРОПОНУВАННЯ ПОЗИК» |
|
|
15 |
«И» |
«ПРОПОНУВАННЯ ПОЗИКИ» |
Після формування словника, можна прочитати повідомлення.
Размещено на www.allbest.ru
Подобные документы
Програма розрахунку інформаційних характеристик каналу зв'язку. Побудова коду для передачі повідомлень. Процедури кодування, декодування та оцінка ефективності кодів. Програма на алгоритмічній мові Паскаль. Канальна матриця, що визначає втрати інформації.
курсовая работа [147,7 K], добавлен 09.07.2009Визначення кількості інформації на символ повідомлення, обчислення диференційної ентропії системи. Розрахунок послаблення сигналу у децибелах, знаходження граничної його міцності. Суть обчислення ймовірності помилкового приймання кодової комбінації.
контрольная работа [165,4 K], добавлен 10.05.2013Значимість двійкової системи числення для кодування інформації. Способи кодування і декодування інформації в комп'ютері. Відповідність десятковій, двійковій, вісімковій і шістнадцятковій систем числення. Двійкове кодування інформації, алфавіт цифр.
презентация [1,4 M], добавлен 30.09.2013Практичне застосування систем кодування знакової та графічної інформації в електронних обчислювальних машинах. Позиційні системи числення. Представлення цілих і дійсних чисел. Машинні одиниці інформації. Основні системи кодування текстових даних.
практическая работа [489,5 K], добавлен 21.03.2012Основні поняття теорії інформації та їх роль у визначенні фундаментальних меж представлення інформації. Телевізійні стандарти стиснення. Кодер і декодер каналу. Стандарти стиснення двійкових та півтонових нерухомих зображень. Кодування бітових площин.
дипломная работа [8,1 M], добавлен 02.10.2014Імовірнисний підхід у теорії ощадливого кодування. Оцінка інформативності ознак та їх оптимальна градація. Застосування імовірнісних методів для підвищення ефективності ощадливого кодування відеоінформації. Ефективні алгоритми кодування інформації.
реферат [1,6 M], добавлен 29.06.2009Стиснення даних як процедура перекодування даних, яка проводиться з метою зменшення їх об'єму, розміру, обсягу. Знайомство с особливостями стиснення інформації способом кодування серій. Загальна характеристика формату ZIP, аналіз основних функцій.
презентация [1,8 M], добавлен 14.08.2013Порядок та етапи розробки системи загальнодержавної класифікації економічної інформації, її призначення. Діяльність міжнародних статистичних організацій. Завдання Єдиної системи класифікації і кодування інформації. Можливості електронної пошти НБУ.
контрольная работа [39,1 K], добавлен 26.07.2009Склад та організація інформаційного забезпечення. Організація збору та передачі інформації. Основні методи класифікації та кодування об'єктів прийняті в інформаційній системі. Перелік вхідних та вихідних даних, які характеризують предметну область.
курсовая работа [1,1 M], добавлен 08.09.2012Інформація та інформаційні процеси, носії інформації, властивості, форми і способи її подання, кодування повідомлень. Інформаційні процеси: пошук, зберігання, збирання, опрацювання, подання, передавання, використання, захист та сучасні засоби зберігання.
методичка [237,8 K], добавлен 15.09.2009
