Практичне заняття №2
Методи ефективного кодування
Задача 1.
Передається текст «УСАЧОВ ІЛЛЯ ОЛЕКСАНДРОВИЧ».
Закодувати повідомлення кодом Хаффмена.
Рішення
Виписуємо символи в порядку не зростаючих ймовірностей їх появи (ймовірності взяті з попереднього практичного заняття).
Рисунок 1 – Результат роботы.
Кодові комбінації символів
Символ |
Кодова комбінація |
А |
000 |
Е |
001 |
О |
010 |
Р |
011 |
Пробіл |
1000 |
В |
1001 |
К |
1010 |
М |
1011 |
Н |
1100 |
Д |
11010 |
И |
11011 |
Л |
11100 |
С |
11101 |
Т |
11110 |
Ч |
11111 |
Закодоване повідомлення кодом Хаффмена
0001001011000101100111001010010100000001111110001101110000101110000110101110100011001101001101010011101111111
Задача 2. Передається текст «АВРАМЕНКО АРТЕМ ОЛЕКСАНДРОВИЧ».
Закодувати повідомлення кодом Шеннона-Фано.
Рішення
Виписуємо символи в порядку не зростаючих ймовірностей їх появи.
Символ |
Ймовірність |
|
|
|
|
|
|
|
|
|
P(A) |
0,137 |
0 |
0 |
0 |
|
|
|
|
|
|
P(Е) |
0,103 |
0 |
0 |
1 |
|
|
|
|
|
|
P(О) |
0,103 |
0 |
1 |
1 |
|
|
|
|
|
|
P(Р) |
0,103 |
0 |
1 |
0 |
1 |
|
|
|
|
|
P(Пробіл) |
0,068 |
0 |
1 |
0 |
0 |
|
|
|
|
|
P(В) |
0,068 |
1 |
0 |
0 |
0 |
|
|
|
|
|
P(К) |
0,068 |
1 |
0 |
0 |
1 |
|
|
|
|
|
P(М) |
0,068 |
1 |
0 |
1 |
0 |
|
|
|
|
|
P(Н) |
0,068 |
1 |
0 |
1 |
1 |
|
|
|
|
|
P(Д) |
0,034 |
1 |
1 |
0 |
0 |
0 |
|
|
|
|
P(И) |
0,034 |
1 |
1 |
0 |
0 |
1 |
0 |
|
|
|
P(Л) |
0,034 |
1 |
1 |
0 |
0 |
1 |
1 |
|
|
|
P(С) |
0,034 |
1 |
1 |
1 |
1 |
0 |
|
|
|
|
P(Т) |
0,034 |
1 |
1 |
1 |
1 |
1 |
0 |
|
|
|
P(Ч) |
0,034 |
1 |
1 |
1 |
1 |
1 |
1 |
|
|
|
Кодові комбінації читаються зліва направо.
В даному випадку ми отримали ті ж самі кодові комбінації, що і для кода Хаффмена. Але це не завжди так відбувається. Кодові комбінації для кода Шеннона-Фано і для кода Хаффмена можуть відрізнятись.
Закодоване повідомлення кодом Шеннона-Фано.
000100000100010100011011100101101000000101111110001101001000111100110011001111100001011110000101011100011001011111
Задача 3
Дискретне джерело «АРТЕМ» з ймовірностями появи Р(А) = 1/5, Р(Р)= 1/5, Р(Т)=1/5, Р(Е)=1/5, Р(М)= 1/5. Кожному із символів виділені інтервали
Символ |
А |
Р |
Т |
Е |
М |
Інтервал |
0 – 0,2 |
0,2 – 0,4 |
0,4 – 0,6 |
0,6 - 0,8 |
0,8 - 1 |
Закодувати повідомлення «АРТЕМ» арифметичним кодом.
Рішення
1) Н0= 0.
К0=1.
2) надходить символ А
Число для передачі
Х=0,1544.
Задача 4
Дискретне джерело видає символи «а», «р», «т», «е», «м». Кодер кодує повідомлення арифметичним кодом. Кожному із символів виділені інтервали
Символ |
А |
Р |
Т |
Е |
М |
Інтервал |
0 – 0,2 |
0,2 – 0,4 |
0,4 – 0,6 |
0,6 - 0,8 |
0,8 - 1 |
Декодувати Х=0,1544.
Рішення
1) Х1=0,1544
Потрапляє в інтервал символа «А».
Виключаємо вплив символу «А»
2) Х2=0,772
Потрапляє в інтервал символа «Е»
Виключаємо вплив символу «Е»
3) Х3= 0,86
Потрапляє в інтервал символа «М»
Виключаємо вплив символу «М»
4) Х4=0,3
Потрапляє в інтервал символа «Р»
Виключаємо вплив символу «Р»
5) Х5=0,5
Потрапляє в інтервал символа «Т»
Виключаємо вплив символу «Т»
.