Теория информации
Кодирование информации. Построение кода Хаффмана для набора букв. Подсчет средней длины кодового слова. Использование частоты вхождения букв. Построение кода Шеннона. Кодировка имени арифметическим кодом. Вычисление кумулятивных вероятностей по формуле.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | контрольная работа |
| Язык | русский |
| Дата добавления | 16.02.2014 |
| Размер файла | 26,5 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Содержание
- Введение
- 1. Задание
- 2. Контрольная работа
- Заключение
- Список литературы
Введение
Объем информации, необходимой для удовлетворения растущих потребностей современного общества, постоянно растет. На сегодняшний день, эффективный информационный обмен возможен только при применении методов кодирования информации.
Дисциплина "Теория информации" дает знания о количественных мерах информационных сообщений, а также изучает методы информационного кодирования.
1. Задание
1. Построить код Хаффмана для набора букв ФИО. Для оценки вероятностей символов использовать частоты вхождения букв в ФИО. Подсчитать среднюю длину кодового слова построенного кода.
2. Построить код Фано для набора букв ФИО. Для оценки вероятностей символов использовать частоты вхождения букв в ФИО. Подсчитать среднюю длину кодового слова построенного кода.
3. Построить код Шеннона для набора букв ФИО. Для оценки вероятностей символов использовать частоты вхождения букв в ФИО. Подсчитать среднюю длину кодового слова построенного кода.
4. Закодировать первые три буквы своего имени арифметическим кодом. Для оценки вероятностей символов использовать частоты вхождения букв в ФИО. кодирование шеннон арифметический
5. Закодировать последовательность из 10 букв ФИО адаптивным кодом Хаффмана (размер окна 6).
2. Контрольная работа
1. Построить код Хаффмана для набора букв ФИО. Для оценки вероятностей символов использовать частоты вхождения букв в ФИО. Подсчитать среднюю длину кодового слова построенного кода.
ФИО: Рехлов Иван Сергеевич.
Таблица 1: Частоты вхождения символов и их вероятности
|
Алфавит символов |
Частота вхождения символа в ФИО |
Pi |
|
|
е |
4 |
0,1905 |
|
|
в |
3 |
0,1429 |
|
|
пробел |
2 |
0,0952 |
|
|
р |
2 |
0,0952 |
|
|
и |
2 |
0,0952 |
|
|
х |
1 |
0,0476 |
|
|
л |
1 |
0,0476 |
|
|
о |
1 |
0,0476 |
|
|
а |
1 |
0,0476 |
|
|
н |
1 |
0,0476 |
|
|
с |
1 |
0,0476 |
|
|
г |
1 |
0,0476 |
|
|
ч |
1 |
0,0476 |
Составляем кодирующую таблицу:
Таблица 2
|
е |
0,1905 |
0,1905 |
0,1905 |
0,1905 |
0,1905 |
0,1905 |
0,1905 |
0,1905 |
|
|
в |
0,1429 |
0,1429 |
0,1429 |
0,1429 |
0,1429 |
0,1904 |
0,1904 |
0,1904 |
|
|
пробел |
0,0952 |
0,0952 |
0,0952 |
0,0952 |
0,0952 |
0,1429 |
0,1904 |
0,1904 |
|
|
р |
0,0952 |
0,0952 |
0,0952 |
0,0952 |
0,0952 |
0,0952 |
0,1429 |
0,1904 |
|
|
и |
0,0952 |
0,0952 |
0,0952 |
0,0952 |
0,0952 |
0,0952 |
0,0952 |
0,1429 |
|
|
х |
0,0476 |
0,0952 |
0,0952 |
0,0952 |
0,0952 |
0,0952 |
0,0952 |
0,0952 |
|
|
л |
0,0476 |
0,0476 |
0,0952 |
0,0952 |
0,0952 |
0,0952 |
0,0952 |
||
|
о |
0,0476 |
0,0476 |
0,0476 |
0,0952 |
0,0952 |
0,0952 |
|||
|
а |
0,0476 |
0,0476 |
0,0476 |
0,0476 |
0,0952 |
||||
|
н |
0,0476 |
0,0476 |
0,0476 |
0,0476 |
|||||
|
с |
0,0476 |
0,0476 |
0,0476 |
||||||
|
г |
0,0476 |
0,0476 |
|||||||
|
ч |
0,0476 |
Продолжение таблицы 2
|
е |
0,381 |
0,381 |
0,381 |
0,62 |
0 |
|
|
в |
0,1905 |
0,238 |
0,381 |
0,381 |
1 |
|
|
пробел |
0,1904 |
0,1905 |
0,238 |
|||
|
р |
0,1429 |
0,1904 |
||||
|
и |
0,0952 |
|||||
|
х |
||||||
|
л |
||||||
|
о |
||||||
|
а |
||||||
|
н |
||||||
|
с |
||||||
|
г |
||||||
|
ч |
Таблица 3: код Хаффмана
|
символ |
Pi |
Li |
Кодовое слово |
|||||
|
е |
0,1905 |
3 |
1 |
0 |
0 |
|||
|
в |
0,1429 |
3 |
1 |
0 |
1 |
|||
|
пробел |
0,0952 |
4 |
1 |
1 |
0 |
0 |
||
|
р |
0,0952 |
4 |
1 |
1 |
1 |
0 |
||
|
и |
0,0952 |
4 |
0 |
0 |
0 |
0 |
||
|
х |
0,0476 |
4 |
0 |
0 |
0 |
1 |
||
|
л |
0,0476 |
5 |
0 |
0 |
1 |
0 |
1 |
|
|
о |
0,0476 |
5 |
0 |
0 |
1 |
1 |
0 |
|
|
а |
0,0476 |
5 |
0 |
1 |
0 |
0 |
1 |
|
|
н |
0,0476 |
5 |
1 |
1 |
1 |
1 |
0 |
|
|
с |
0,0476 |
5 |
0 |
1 |
0 |
1 |
1 |
|
|
г |
0,0476 |
5 |
0 |
1 |
0 |
1 |
0 |
|
|
ч |
0,0476 |
5 |
0 |
1 |
1 |
0 |
1 |
Подсчет средней длины кодового слова.
Lср = 0,1905Ч3+0,1429Ч3+0,0952Ч3+0,0952Ч3+0,0952Ч3+0,0476Ч4+0,0476Ч5+
+0,0476Ч5+0,0476Ч5+0,0476Ч5+0,0476Ч5+0,0476Ч5+0,0476Ч5 = 3,761
2. Построить код Фано для набора букв ФИО. Для оценки вероятностей символов использовать частоты вхождения букв в ФИО. Подсчитать среднюю длину кодового слова построенного кода.
ФИО: Рехлов Иван Сергеевич
Вероятности появления символов возьмем из Таблицы 1.
Таблица 4: Код Фано.
|
символ |
Pi |
Кодовое слово |
Li |
|||||
|
е |
0,1905 |
0 |
0 |
2 |
||||
|
в |
0,1429 |
0 |
1 |
0 |
3 |
|||
|
пробел |
0,0952 |
0 |
1 |
1 |
1 |
4 |
||
|
р |
0,0952 |
0 |
1 |
1 |
0 |
4 |
||
|
и |
0,0952 |
1 |
0 |
0 |
1 |
4 |
||
|
х |
0,0476 |
1 |
0 |
1 |
0 |
0 |
5 |
|
|
л |
0,0476 |
1 |
0 |
1 |
0 |
1 |
5 |
|
|
о |
0,0476 |
1 |
0 |
1 |
1 |
0 |
5 |
|
|
а |
0,0476 |
1 |
1 |
0 |
1 |
1 |
5 |
|
|
н |
0,0476 |
1 |
1 |
0 |
0 |
0 |
5 |
|
|
с |
0,0476 |
1 |
1 |
1 |
0 |
1 |
5 |
|
|
г |
0,0476 |
1 |
1 |
1 |
1 |
0 |
5 |
|
|
ч |
0,0476 |
1 |
1 |
1 |
1 |
1 |
5 |
Подсчет средней длины кодового слова.
Lср = 0,1905Ч2+0,1429Ч3+0,0952Ч4+0,0952Ч4+0,0952Ч4+0,0476Ч5+0,0476Ч5+
+0,0476Ч5+0,0476Ч5+0,0476Ч5+0,0476Ч5+0,0476Ч5+0,0476Ч5 = 3,8561
3. Построить код Шеннона для набора букв ФИО. Для оценки вероятностей символов использовать частоты вхождения букв в ФИО. Подсчитать среднюю длину кодового слова построенного кода. ФИО: Рехлов Иван Сергеевич
Вероятности появления символов возьмем из Таблицы 1.
Кумулятивные вероятности вычислим по формуле:
Q0 = 0; Qn = P1+ P2….+ Pn;
Таблица 5: Код Шеннона.
|
символ |
Pi |
Qi -1 |
[q] 2 |
-log Pi +1 |
Кодовое слово |
||||||
|
е |
0,1905 |
0 |
0,0000 |
3,392 |
3 |
0 |
0 |
0 |
|||
|
в |
0,1429 |
0,1905 |
0,0011 |
3,807 |
3 |
0 |
1 |
1 |
|||
|
пробел |
0,0952 |
0,3334 |
0,0101 |
4,393 |
4 |
0 |
1 |
0 |
1 |
||
|
р |
0,0952 |
0,4286 |
0,0110 |
4,393 |
4 |
0 |
1 |
1 |
0 |
||
|
и |
0,0952 |
0,5238 |
0,1000 |
4,393 |
4 |
1 |
0 |
0 |
0 |
||
|
х |
0,0476 |
0,619 |
0,10011 |
5,393 |
5 |
1 |
0 |
0 |
1 |
1 |
|
|
л |
0,0476 |
0,666 |
0,10101 |
5,393 |
5 |
1 |
0 |
1 |
0 |
1 |
|
|
о |
0,0476 |
0,7142 |
0,10110 |
5,393 |
5 |
1 |
0 |
1 |
1 |
0 |
|
|
а |
0,0476 |
0,7618 |
0,11000 |
5,393 |
5 |
1 |
1 |
0 |
0 |
0 |
|
|
н |
0,0476 |
0,8094 |
0,11001 |
5,393 |
5 |
1 |
1 |
0 |
0 |
1 |
|
|
с |
0,0476 |
0,8566 |
0,11011 |
5,393 |
5 |
1 |
1 |
0 |
1 |
1 |
|
|
г |
0,0476 |
0,9042 |
0,11100 |
5,393 |
5 |
1 |
1 |
1 |
0 |
0 |
|
|
ч |
0,0476 |
0,9518 |
0,11110 |
5,393 |
5 |
1 |
1 |
1 |
1 |
0 |
Подсчет средней длины кодового слова.
Lср = 0,1905Ч3+0,1429Ч3+0,0952Ч4+0,0952Ч4+0,0952Ч4+0,0476Ч5+0,0476Ч5+
+0,0476Ч5+0,0476Ч5+0,0476Ч5+0,0476Ч5+0,0476Ч5+0,0476Ч5 = 4,0556
4. Закодировать первые три буквы своего имени арифметическим кодом. Для оценки вероятностей символов использовать частоты вхождения букв в ФИО.
Буквы: Р,Е,Х.
Найдем границы интервала, первого символа кодируемого сообщения (Р), значения кумулятивных вероятностей, возьмем из Таблицы 5:
L1 = L0 + r0 * Q3; L1 = 0 + 1 * 0,4286 = 0,4286
h1 = L0 + r0 * Q4 ; h1 = 0 + 1 * 0,5238 = 0,5238
r1 = h1 - L1 ; r1 = 0,5238 - 0,4286 = 0,0952
Выполним аналогичные действия для второго символа (Е):
L2 = L1 + r1 * Q0 ; L2 = 0,5238+ 0,0952 * 0 = 0
h2 = L1 + r1 * Q1 ; h2 = 0,5238+ 0,0952 * 0,1905 = 0,1179
r2 = h2 - L2 ; r2 = 0,1179 - 0 = 0,1179
Определим границы интервала для третьего символа (Х):
L3 = L2 + r2 * Q5; L3 = 0 + 0,1179 * 0,619 = 0,0729
h3 = L2 + r2 * Q6 ; h3 = 0 + 0,1179 * 0,666 = 0,0785
r3 = h3 - L3 ; r3 = 0,0785 - 0,0729 = 0,0026
Кодом сообщения (РЕХ), будет двоичная запись любой точки интервала [0,0729 ; 0,0785].
Примем 0,0729 и вычислим количество разрядов кодируемого сообщения:
log r3 = -log 0,0026 = 9 разрядов.
В результате получаем код: 000100101.
5. Закодировать последовательность из 10 букв ФИО адаптивным кодом Хаффмана (размер окна 6).
Первые 10 букв: Рехлов_Ива
| Рехлов |_Ива
Вероятности определим по следующей формуле:
Pi = qi / W,
где qi
частота появления символа в окне, W = 6 - длинна окна.
Следующая буква после окна.
|
символ |
Частота появления символа в окне |
Pi |
Символ, закодированный обычным кодом Хафмана |
|
|
р |
1 |
0, 1667 |
111 |
|
|
е |
1 |
0, 1667 |
011 |
|
|
х |
1 |
0, 1667 |
101 |
|
|
л |
1 |
0, 1667 |
000 |
|
|
о |
1 |
0, 1667 |
110 |
|
|
в |
1 |
0, 1667 |
010 |
Передвигаем окно на один символ вправо и снова подсчитываем частоты символов в окне:
|ехлов _|Ива
Следующая буква после окна:
|
символ |
Частота появления символа в окне |
Pi |
Символ, закодированный обычным кодом Хафмана |
|
|
е |
1 |
0, 1667 |
011 |
|
|
х |
1 |
0, 1667 |
101 |
|
|
л |
1 |
0, 1667 |
000 |
|
|
о |
1 |
0, 1667 |
110 |
|
|
в |
1 |
0, 1667 |
010 |
|
|
_ |
1 |
0, 1667 |
100 |
|хлов _И|ва
Следующая буква после окна: в
|
символ |
Частота появления символа в окне |
Pi |
Символ, закодированный обычным кодом Хафмана |
|
|
х |
1 |
0, 1667 |
101 |
|
|
л |
1 |
0, 1667 |
000 |
|
|
о |
1 |
0, 1667 |
110 |
|
|
в |
1 |
0, 1667 |
010 |
|
|
_ |
1 |
0, 1667 |
100 |
|
|
И |
1 |
0, 1667 |
001 |
|лов _Ив|а
|
символ |
Частота появления символа в окне |
Символ, закодированный обычным кодом Хафмана |
||
|
л |
1 |
0, 1667 |
000 |
|
|
о |
1 |
0, 1667 |
110 |
|
|
в |
2 |
0,3333 |
010 |
|
|
_ |
1 |
0, 1667 |
100 |
|
|
И |
1 |
0, 1667 |
001 |
|
|
а |
0 |
0 |
10 |
В результате получаем код:
Рехлов_Ива: 111 011 101 000 110 010 100 001 010 10.
Заключение
В данной контрольной работе по дисциплине "Теория информации", выполнены задания по кодированию сообщения (Ф.И. О) методами Хаффмана, Фона и Шеннона, а также по методу арифметического кодирования.
Список литературы
1. Конспект лекций по дисциплине "Теория информации". Новосибирск, СибГУТИ 2013.
2. Золотарев. Помехоустойчивое кодирование. М.: Радио и связь, 2005.
3. Лидовский В.В. Теория информации. М.: Издательский дом "Вильямс", 2004.
4. Мартин Н., Ингленд Дж. Математическая теория энтропии. М.: Радио и связь, 2004.
5. Финк Л.М. - Теория передачи дискретных сообщений. Издательский дом "Вильямс", 2007.
Размещено на Allbest.ru
...Подобные документы
Общее число неповторяющихся сообщений. Вычисление скорости передачи информации и пропускной способности каналов связи. Определение избыточности сообщений и оптимальное кодирование. Процедура построения оптимального кода по методике Шеннона-Фано.
курсовая работа [59,4 K], добавлен 17.04.2009Описание и особенности некоторых алгоритмов архивации. Построение кода Хаффмана. Динамический алгоритм построения кода Хаффмана. Обратное восстановление текста. Способы двухступенчатого кодирования информации. Практическая реализация алгоритма LZ77.
курсовая работа [51,7 K], добавлен 24.12.2012Оценка вычислительной сложности программы. Реализация алгоритма кодирования информации Хаффмана. Кодировка теста двоичным кодом и в дереве Хаффмана. Бинарный код символов. Символ и частота его появления в тексте. Вычисление трудоемкости алгоритма.
контрольная работа [21,0 K], добавлен 16.12.2012Определение среднего количества информации. Зависимость между символами матрицы условных вероятностей. Кодирование методом Шеннона–Фано. Пропускная способность канала связи. Эффективность кодирования сообщений методом Д. Хаффмана, характеристика кода.
контрольная работа [94,6 K], добавлен 04.05.2015Определение понятий кода, кодирования и декодирования, виды, правила и задачи кодирования. Применение теорем Шеннона в теории связи. Классификация, параметры и построение помехоустойчивых кодов. Методы передачи кодов. Пример построения кода Шеннона.
курсовая работа [212,6 K], добавлен 25.02.2009Анализ эффективности способов кодирования. Средний размер одного разряда и средняя длина кодового слова. Кодирование по методу Хаффмена. Кодирование информации по методу Шенона-Фано. Построение кодового дерево для различных методов кодирования.
контрольная работа [491,4 K], добавлен 15.10.2013Кодирование и декодирование, преобразование дискретного сообщения в дискретный сигнал. Построение математической модели корректирующего кода. Образующая матрица информационного кода. Модульная структура программы. Спецификация на программные модули.
курсовая работа [98,9 K], добавлен 28.11.2014Вычисление количества информации, приходящейся на один символ по формуле Шеннона. Изменения информационной энтропии в текстах экономического, естественнонаучного и литературного содержания. Максимальное количество информации на знак по формуле Хартли.
лабораторная работа [28,2 K], добавлен 06.12.2013Информация и информационные процессы. Содержательный и алфавитный подходы к измерению количества информации. Определение мощности алфавита информационного сообщения. Описания компьютерной кодировки русских и латинских букв. Использование двоичной системы.
лабораторная работа [35,3 K], добавлен 04.09.2014Двоичные деревья в теории информации. Двоичные кодовые деревья допускают интерпретацию в рамках теории поиска. Обоснование выбора, описание алгоритма и структур данных. Обоснование набора тестов. Построение оптимального кода. Сущность алгоритма Хаффмана.
курсовая работа [241,6 K], добавлен 17.10.2008Генерация порождающего полинома для циклического кода. Преобразование порождающей матрицы в проверочную и обратно. Расчет кодового расстояния для линейного блокового кода. Генерация таблицы зависимости векторов ошибок от синдрома для двоичных кодов.
доклад [12,6 K], добавлен 11.11.2010Аналоговое и цифровое представление информации. Понятие, классификация и характеристика методов сжатия данных: алгоритмы одно- и двухпараметрической адаптации, линейной экстра- и интерполяции. Кодирование информации и вычисление циклического кода.
курсовая работа [157,4 K], добавлен 07.12.2012Средства и технологии обработки текстовой информации: MS-DOS Editor, Word Pad, Блокнот, Microsoft Word. Двоичное кодирование текстовой информации в компьютере. Рассмотрение разновидностей кодовых таблиц для русских букв: Windows, MS-DOS, КОИ-8, Мас, ISO.
курсовая работа [644,5 K], добавлен 27.04.2013Обзор существующих программ сжатия данных без потерь. Анализ методов сжатия: алгоритмов группы, KWE, Lossless JPEG, кодирование Хаффмана. Обзор составляющих компонентов. Разработка кода программы-архиватора, работающей на основе алгоритма Хаффмена.
курсовая работа [487,3 K], добавлен 14.07.2011Непрерывная и дискретная информация. Кодирование как процесс представления информации в виде кода. Особенности процедуры дискретизации непрерывного сообщения. Позиционные и непозиционные системы счисления. Представление информации в двоичном коде.
реферат [117,3 K], добавлен 11.06.2010Сущность линейного и двухмерного кодирования. Схема проверки подлинности штрих-кода. Анализ способов кодирования информации. Расчет контрольной цифры. Штриховое кодирование как эффективное направление автоматизации процесса ввода и обработки информации.
презентация [1,1 M], добавлен 05.10.2014Изучение методов кодирования Хаффмана, Фано. Модель информационной системы Шеннона. Среднестатистическая информационная емкость сообщений для эргодических источников с заданным распределением частот символов. Формулы Хартли для удельной емкости на символ.
презентация [528,9 K], добавлен 19.10.2014Кодирование как процесс представления информации в виде кода. Кодирование звуковой и видеоинформации, характеристика процесса формирования определенного представления информации. Особенности универсального дружественного интерфейса для пользователей.
контрольная работа [20,3 K], добавлен 22.04.2011Процедуры ввода и вывода. Оператор присваиваний: расчет площади боковой поверхности конуса. Операторы условия и выбора; циклы; символьные строки. Подсчет количества гласных букв в тексте, состоящем из латинских букв и заканчивающимся точкой; множества.
лабораторная работа [427,3 K], добавлен 21.01.2012Системы сбора и передачи информации. Обоснование выбора кода, способа передачи и синхронизации. Выбор длины посылки, формата кодового перехода. Расчет помехоустойчивости и времени запаздывания. Разработка структурной схемы передающего устройства.
курсовая работа [412,8 K], добавлен 24.06.2013
