Автор статьи
Валерия
Эксперт по сдаче вступительных испытаний в ВУЗах
Задание на курсовую работу
Задание № 1. Построить кодовое дерево и код Хаффмена для последовательности символов в соответствии с вариантом. Подсчитать энтропию исходного сообщения и среднюю длину получившегося кода.| Вариант | Сообщение |
| 4 | there are kinds of symbols available, then so |
| Вариант | Последовательность символов | Полином |
| 4 | 61 67 65 73 | x^8 +x^5 +x^4 +1 |
Введение
Вопросы сжатия данных и помехоустойчивого кодирования информации играют важную роль при построении телекоммуникационных систем и систем архивного хранения. В первом случае преследуется цель обеспечения максимальной скорости и надежности передачи данных при неизменной физической пропускной способности канала связи. Во втором – минимизации объема носителей, задействованных для хранения информации. Эти вопросы могут быть решены путем использования различных кодов, обеспечивающих эффективное представление данных. Курсовая работа посвящена построению кода Хаффмана для оптимального кодирования алфавита источника сообщений и CRC-коду для обнаружения ошибок, возникающих в ходе передачи сообщений.Задание № 1.
Построить кодовое дерево и код Хаффмена для последовательности символов в соответствии с вариантом. Подсчитать энтропию исходного сообщения и среднюю длину получившегося кода.| Вариант | Сообщение |
| 4 | there are kinds of symbols available, then so |
| № | Символ | pi | |
| 1 | <space> | 7/45 | |
| 2 | e e e e e | 5/45 | |
| 3 | a a a a | 4/45 | |
| 4 | s s s s | 4/45 | |
| 5 | l l l | 3/45 | |
| 6 | o o o | 3/45 | |
| 7 | b b | 2/45 | |
| 8 | h h | 2/45 | |
| 9 | i i | 2/45 | |
| 10 | n n | 2/45 | |
| 11 | r r | 2/45 | |
| 12 | t t | 2/45 | |
| 13 | d | 1/45 | |
| 14 | f | 1/45 | |
| 15 | k | 1/45 | |
| 16 | m | 1/45 | |
| 17 | v | 1/45 | |
| 18 | y | 1/45 | |
| 19 | , | 1/45 |
| № | Символ | Вероятности | |||||||||||||||||
| Исходный алфавит | Промежуточные алфавиты | ||||||||||||||||||
| A(1) | A(2) | A(3) | A(4) | A(5) | A(6) | A(7) | A(8) | A(9) | A(10) | A(11) | A(12) | A(13) | A(14) | A(15) | A(16) | A(17) | |||
| 1 | <space> | 7/45 | 7/45 | 7/45 | 7/45 | 7/45 | 7/45 | 7/45 | 7/45 | 7/45 | 7/45 | 7/45 | 8/45 | 8/45 | 9/45 | 13/45 | 15/45 | 17/45 | 28/45 |
| 2 | e | 5/45 | 5/45 | 5/45 | 5/45 | 5/45 | 5/45 | 5/45 | 5/45 | 5/45 | 6/45 | 7/45 | 7/45 | 8/45 | 8/45 | 9/45 | 13/45 | 15/45 | 17/45 |
| 3 | a | 4/45 | 4/45 | 4/45 | 4/45 | 4/45 | 4/45 | 4/45 | 4/45 | 4/45 | 5/45 | 6/45 | 7/45 | 7/45 | 8/45 | 8/45 | 9/45 | 13/45 | |
| 4 | s | 4/45 | 4/45 | 4/45 | 4/45 | 4/45 | 4/45 | 4/45 | 4/45 | 4/45 | 4/45 | 5/45 | 6/45 | 7/45 | 7/45 | 8/45 | 8/45 | ||
| 5 | l | 3/45 | 3/45 | 3/45 | 3/45 | 3/45 | 4/45 | 4/45 | 4/45 | 4/45 | 4/45 | 4/45 | 5/45 | 6/45 | 7/45 | 7/45 | |||
| 6 | o | 3/45 | 3/45 | 3/45 | 3/45 | 3/45 | 3/45 | 4/45 | 4/45 | 4/45 | 4/45 | 4/45 | 4/45 | 5/45 | 6/45 | ||||
| 7 | b | 2/45 | 2/45 | 2/45 | 2/45 | 3/45 | 3/45 | 3/45 | 4/45 | 4/45 | 4/45 | 4/45 | 4/45 | 4/45 | |||||
| 8 | h | 2/45 | 2/45 | 2/45 | 2/45 | 2/45 | 3/45 | 3/45 | 3/45 | 4/45 | 4/45 | 4/45 | 4/45 | ||||||
| 9 | i | 2/45 | 2/45 | 2/45 | 2/45 | 2/45 | 2/45 | 3/45 | 3/45 | 3/45 | 4/45 | 4/45 | |||||||
| 10 | n | 2/45 | 2/45 | 2/45 | 2/45 | 2/45 | 2/45 | 2/45 | 3/45 | 3/45 | 3/45 | ||||||||
| 11 | r | 2/45 | 2/45 | 2/45 | 2/45 | 2/45 | 2/45 | 2/45 | 2/45 | 3/45 | |||||||||
| 12 | t | 2/45 | 2/45 | 2/45 | 2/45 | 2/45 | 2/45 | 2/45 | 2/45 | ||||||||||
| 13 | d | 1/45 | 2/45 | 2/45 | 2/45 | 2/45 | 2/45 | 2/45 | |||||||||||
| 14 | f | 1/45 | 1/45 | 2/45 | 2/45 | 2/45 | 2/45 | ||||||||||||
| 15 | k | 1/45 | 1/45 | 1/45 | 2/45 | 2/45 | |||||||||||||
| 16 | m | 1/45 | 1/45 | 1/45 | 1/45 | ||||||||||||||
| 17 | v | 1/45 | 1/45 | 1/45 | |||||||||||||||
| 18 | y | 1/45 | 1/45 | ||||||||||||||||
| 19 | , | 1/45 | |||||||||||||||||
Задание № 2.
В соответствии с номером варианта получить для приведенного в шестнадцатеричном формате в виде четырех пар 4-битовых чисел исходного 32-битного сообщения циклический избыточный код.| Вариант | Последовательность символов | Полином |
| 4 | 61 67 65 73 | x^8 +x^5 +x^4 +1 |
Заключение
При выполнении курсовой работы изучены вопросы сжатия данных и помехоустойчивого кодирования информации. Построены код Хаффмана для оптимального кодирования алфавита источника сообщений и CRC-код, позволяющий обнаруживать ошибки, возникающие в ходе передачи сообщений.Список использованных источников
- Колесник В.Д. Кодирование при передаче и хранении информации (Алгебраическая теория блоковых кодов) : учеб. пособие для вузов / В. Д. Колесник .— М. : Высш. шк., 2009 .— 551 с.
- Новиков Ф.А. Дискретная математика для программистов : учеб. пособие для вузов / Ф.А. Новиков .— 3-е изд. — М. и др. : Питер, 2008 .— 384с.
- Информатика : учебник для вузов / В. В. Трофимов [и др.] ; под ред. В.В. Трофимова ; СПбГУЭФ .— М. : Юрайт, 2011 .— 912 с.
- Морелос-Сарагоса Р. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение : учебное пособие / М. Морелос-Сарагоса; пер. с англ. В.Б. Афанасьева .— М. : Техносфера, 2005 .— 320с.
О сайте
Ссылка на первоисточник:
http://rsreu.ru
Поделитесь в соцсетях: