Эффективное кодирование
Алматинский
УНИВЕРСИТЕТ энергетики и связи
Кафедра
«Инженерной кибернетики»
Расчетно-графическая
работа №3
Дисциплина:
«Прикладная теория информации»
На
тему: «Эффективное
кодирование»
Вариант 1
Выполнила:
ст.гр. АИСУ-10-3
Абдыгалыев
К.И.
Проверил:
ст. преп. каф. ИК
Бойко
В.М.
Алматы 2012
Задание к выполнению расчетно-графической работы
.Произвести кодирование данных для длин блоков А
(таблица вариантов) (по Шеннону) и В (таблица вариантов) (по Хаффмену).
Определить для каждого случая средний размер одного разряда и среднюю длину
кодового слова.
.Построить кодовое дерево для каждого метода.
.Провести анализ эффективности способов
кодирования для заданного варианта.
Согласно варианту, длины блоков:
А: 2, 3
В: 2, 3
Решение.
Кодирование по методу Шеннона-Фано.
) Блок А с длиной 2 символа:
Рассмотрим два случая:
а) когда вероятности появления 1 и 0 в длинном
сообщении равны:
=р(1)=0,1 =p(0)=0,9
|
у1=0,81
|
1
|
|
|
|
у2=0,09
|
0
|
1
|
|
|
у3=0,09
|
0
|
0
|
1
|
|
у4=0,01
|
0
|
0
|
0
|
Определим средний размер одного разряда и
среднюю длину кодового слова:
Средняя длина кодового слова:
Средний размер одного разряда: lср = LСР/n=1,2/2=0,6
б) =р(1)=0,4 =p(0)=0,6
|
у1=0,36
|
1
|
1
|
|
у2=0,24
|
1
|
0
|
|
у3=0,24
|
0
|
1
|
|
у4=0,16
|
0
|
0
|
Средняя длина кодового слова:
Средний размер одного разряда: lср = LСР/n=2/2=1
) Блок А с длиной 3 символа:
Рассмотрим два случая:
а) когда вероятности появления 1 и 0
в длинном сообщении равны:
=р(1)=0,1 =p(0)=0,9
|
y1
|
0,729
|
1
|
|
|
|
|
1
|
|
y2
|
0,081
|
1
|
1
|
|
|
011
|
|
y3
|
0,081
|
|
|
0
|
|
|
010
|
|
y4
|
0,081
|
|
0
|
1
|
|
|
001
|
|
y5
|
0,009
|
|
|
0
|
1
|
1
|
00011
|
|
y6
|
0,009
|
|
|
|
|
0
|
00010
|
|
y7
|
0,009
|
|
|
|
0
|
1
|
00001
|
|
y8
|
0,001
|
|
|
|
|
0
|
00000
|
Определим средний размер одного разряда, среднюю
длину кодового слова и энтропию:
Средняя длина кодового слова:
Средний размер одного разряда: lср = LСР/n=1,598/3=0,533
Энтропия: 
б) =р(1)=0,4 =p(0)=0,6
|
y1
|
0,216
|
1
|
1
|
|
|
11
|
|
y2
|
0,144
|
|
0
|
1
|
|
101
|
|
y3
|
0,144
|
|
|
0
|
|
100
|
|
y4
|
0,144
|
0
|
1
|
1
|
|
011
|
|
y5
|
0,096
|
|
|
0
|
|
010
|
|
y6
|
0,096
|
|
0
|
1
|
|
001
|
|
y7
|
0,096
|
|
|
0
|
0001
|
|
y8
|
0,064
|
|
|
|
0
|
0000
|
Средняя длина кодового слова:
Средний размер одного разряда: lср = LСР/n=2,944/3=0,98
Энтропия: 
Кодирование по методу Хаффмена
) Блок В с длиной 2 символа:
Рассмотрим два случая:
а) когда вероятности появления 1 и 0
в длинном сообщении равны :
=р(1)=0,1 =p(0)=0,9
Средняя длина кодового слова:
Средний размер одного разряда: lср = LСР/n=1,29/2=0,645
|
0,81
|
0,81
|
0,81
|
1
|
|
0,09
|
0,1
|
0,19
|
|
|
0,09
|
0,09
|
|
|
|
0,01
|
|
|
|
кодирование слово дерево
информация
б) =р(1)=0,4 =p(0)=0,6
Средняя длина кодового слова:
Средний размер одного разряда:
lср = LСР/n=2/2=1
|
0,36
|
0,40
|
0,60
|
1
|
|
0,24
|
0,36
|
0,40
|
|
|
0,24
|
0,24
|
|
|
|
0,16
|
|
|
|
) Блок В с длиной 3 символа:
Рассмотрим два случая:
а) когда вероятности появления 1 и 0 в длинном
сообщении равны:
=р(1)=0,1 =p(0)=0,9
Средняя длина кодового слова:
Средний размер одного разряда: lср = LСР/n=1,598/3=0,533
Энтропия:
|
y1
|
0,729
|
0,729
|
0,729
|
0,729
|
0,729
|
0,729
|
0,729
|
1
|
|
y2
|
0,081
|
0,081
|
0,081
|
0,081
|
0,109
|
0,162
|
|
|
y3
|
0,081
|
0,081
|
0,081
|
0,081
|
0,081
|
0,109
|
|
|
|
y4
|
0,081
|
0,081
|
0,081
|
0,081
|
0,081
|
|
|
|
|
y5
|
0,009
|
0,01
|
0,018
|
0,028
|
|
|
|
|
|
y6
|
0,009
|
0,009
|
0,01
|
|
|
|
|
|
|
y7
|
0,009
|
0,009
|
|
|
|
|
|
|
|
y8
|
0,001
|
|
|
|
|
|
|
|
Коды:
y1=1
y2=011
y3=010
y4=001
y5=00011
y6=00010
y7=00001=00000
б) =р(1)=0,4
=p(0)=0,6
Средняя длина кодового слова:
Средний размер одного разряда: lср = LСР/n=2,944/3=0,98
Энтропия:
|
y1
|
0,216
|
0,216
|
0,216
|
0,288
|
0,304
|
0,408
|
0,592
|
1
|
|
y2
|
0,144
|
0,16
|
0,192
|
0,216
|
0,288
|
0,304
|
0,408
|
|
|
y3
|
0,144
|
0,144
|
0,16
|
0,192
|
0,216
|
0,288
|
|
|
|
y4
|
0,144
|
0,144
|
0,144
|
0,192
|
|
|
|
|
y5
|
0,096
|
0,144
|
0,144
|
0,144
|
|
|
|
|
|
y6
|
0,096
|
0,096
|
0,144
|
|
|
|
|
|
|
y7
|
0,096
|
0,096
|
|
|
|
|
|
|
|
y8
|
0,064
|
|
|
|
|
|
|
|
Коды:
y1=01
y2=110
y3=101
y4=100
y5=001
y6=000
y7=1111
y8=1110
Вывод
В данной работе были рассмотрены два метода
кодирования информации: по методу Шенона-Фано (для блоков с длинами 2, 3)и по
методу Хаффмена (для блоков с длинами 2 и 3). Можно сделать вывод, что эти
методы действительно эффективные, т.к. они позволяют передавать информацию с
большей скоростью, не теряя своей полноты.
Список использованной литературы
· Ю. В. Шевяков, Ш. M.
Байматаева. Прикладная теория информации. Методические указания к выполнению
расчетно-графических работ для студентов всех форм обучения специальности
050702 - Автоматизация и управление.- Алматы:
АИЭС, 2008.
· Гоноровский И.С. Радиотехнические
цепи и сигналы. - М.: Радио и связь, 1994.