Эффективное кодирование
Анализ эффективности способов кодирования. Средний размер одного разряда и средняя длина кодового слова. Кодирование по методу Хаффмена. Кодирование информации по методу Шенона-Фано. Построение кодового дерево для различных методов кодирования.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | контрольная работа |
| Язык | русский |
| Дата добавления | 15.10.2013 |
| Размер файла | 491,4 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Алматинский УНИВЕРСИТЕТ энергетики и связи
Кафедра «Инженерной кибернетики»
Расчетно-графическая работа №3
Дисциплина: «Прикладная теория информации»
На тему: «Эффективное кодирование»
Вариант 1
Выполнила: ст.гр. АИСУ-10-3
Абдыгалыев К.И.
Проверил: ст. преп. каф. ИК
Бойко В.М.
Алматы 2012
Задание к выполнению расчетно-графической работы
1.Произвести кодирование данных для длин блоков А (таблица вариантов) (по Шеннону) и В (таблица вариантов) (по Хаффмену). Определить для каждого случая средний размер одного разряда и среднюю длину кодового слова.
2.Построить кодовое дерево для каждого метода.
3.Провести анализ эффективности способов кодирования для заданного варианта.
Согласно варианту, длины блоков:
А: 2, 3
В: 2, 3
Решение.
Кодирование по методу Шеннона-Фано.
1) Блок А с длиной 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
2) Блок А с длиной 3 символа:
Рассмотрим два случая:
а) когда вероятности появления 1 и 0 в длинном сообщении равны:
=р(1)=0,1 =p(0)=0,9
|
y1 |
0,729 |
1 |
1 |
|||||
|
y2 |
0,081 |
0 |
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 |
1 |
0001 |
|||
|
y8 |
0,064 |
0 |
0000 |
Средняя длина кодового слова:
Средний размер одного разряда: lср = LСР/n=2,944/3=0,98
Энтропия:
Кодирование по методу Хаффмена
1) Блок В с длиной 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 |
2) Блок В с длиной 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 |
0,271 |
||
|
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
y8=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,16 |
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.
Размещено на Allbest.ru
Подобные документы
Сущность линейного и двухмерного кодирования. Схема проверки подлинности штрих-кода. Анализ способов кодирования информации. Расчет контрольной цифры. Штриховое кодирование как эффективное направление автоматизации процесса ввода и обработки информации.
презентация [1,1 M], добавлен 05.10.2014Представление информации в двоичной системе. Необходимость кодирования в программировании. Кодирование графической информации, чисел, текста, звука. Разница между кодированием и шифрованием. Двоичное кодирование символьной (текстовой) информации.
реферат [31,7 K], добавлен 27.03.2010Сущность и содержание двоичного кодирования, цели и задачи, этапы реализации данного процесса, оценка его эффективности. Принципы и особенности кодирования чисел и символов, а также рисунков и звука. Используемые методы и приемы, применяемые инструменты.
презентация [756,5 K], добавлен 29.10.2013Методы компрессии информации. Обзор и характеристика существующих методов сжатия информации, основанных на процедуре кодирования Хаффмена. Алгоритмы динамического кодирования методом FGK и Виттера. Программная реализация и руководство пользователя.
курсовая работа [33,2 K], добавлен 09.03.2009Место темы "Кодирование информации" в школьном курсе информатики. Рекомендации по изучению "Кодирования информации" в школьном курсе информатики. Дидактический материал для изучения темы "Кодирование информации" и внеклассное мероприятие по информатике.
курсовая работа [2,3 M], добавлен 17.06.2012Информация и информационные процессы в природе, обществе, технике. Информационная деятельность человека. Кодирование информации. Способы кодирования. Кодирование изображений. Информация в кибернетике. Свойства информации. Измерение количества информации.
реферат [21,4 K], добавлен 18.11.2008Анализ методов сверточного кодирования. Понятие канала связи и корректирующих кодов, характеристика автомата типа Мура. Особенности сверточного декодирования Витерби. Сущность разработки программного обеспечения системы кодирования сверточным кодом.
дипломная работа [4,9 M], добавлен 11.03.2012Изучение методов кодирования Хаффмана, Фано. Модель информационной системы Шеннона. Среднестатистическая информационная емкость сообщений для эргодических источников с заданным распределением частот символов. Формулы Хартли для удельной емкости на символ.
презентация [528,9 K], добавлен 19.10.2014Оптимальное статистическое (экономное) кодирование. Основные понятия и определения теории кодирования. Принципы построения оптимальных кодов. Способность системы осуществлять прием информации в условиях наличия помех. Увеличение мощности сигналов.
реферат [69,3 K], добавлен 09.07.2009Основные понятия и определения кодирования информации. Кодовая комбинация и ее длина. Классификация кодов по различным признакам, способы их представления, назначение. Представление в виде кодовых деревьев или многочленов, матричное и геометрическое.
реферат [38,1 K], добавлен 05.08.2009
