Задание на курсовую работу
Задание № 1. Построить кодовое дерево и код Хаффмена для последовательности символов в соответствии с вариантом. Подсчитать энтропию исходного сообщения и среднюю длину получившегося кода.
| Вариант | Сообщение |
| 4 | there are kinds of symbols available, then so |
Задание № 2. В соответствии с номером варианта получить для приведенного в шестнадцатеричном формате в виде четырех пар 4-битовых чисел исходного 32-битного сообщения циклический избыточный код.
| Вариант | Последовательность символов | Полином |
| 4 | 61 67 65 73 | x^8 +x^5 +x^4 +1 |
Введение
Вопросы сжатия данных и помехоустойчивого кодирования информации играют важную роль при построении телекоммуникационных систем и систем архивного хранения. В первом случае преследуется цель обеспечения максимальной скорости и надежности передачи данных при неизменной физической пропускной способности канала связи. Во втором – минимизации объема носителей, задействованных для хранения информации. Эти вопросы могут быть решены путем использования различных кодов, обеспечивающих эффективное представление данных.
Курсовая работа посвящена построению кода Хаффмана для оптимального кодирования алфавита источника сообщений и CRC-коду для обнаружения ошибок, возникающих в ходе передачи сообщений.
Задание № 1.
Построить кодовое дерево и код Хаффмена для последовательности символов в соответствии с вариантом. Подсчитать энтропию исходного сообщения и среднюю длину получившегося кода.
| Вариант | Сообщение |
| 4 | there are kinds of symbols available, then so |
Сообщение состоит из 45 символов 19 разновидностей. Вычислим вероятности каждого из символов, встречающихся в сообщении:
| № | Символ | 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 |
Представим данную последовательность в двоичной системе:
61 67 65 73(16) = 0110 0001 0110 0111 0110 0101 0111 0011(2)
Полином: 100110001, степень полинома W= 8.
Добавим к сообщению W нулевых битов:
0110 0001 0110 0111 0110 0101 0111 0011 0000 0000
Выполним деление использованием правил CRC-арифметики
0110000101100111011001010111001100000000
100110001
———
101101001
100110001
———
010110000
000000000
———
101100000
100110001
———
010100011
000000000
———
101000111
100110001
———
011101101
000000000
———
111011010
100110001
———
111010111
100110001
———
111001101
100110001
———
111111000
100110001
———
110010010
100110001
———
101000111
100110001
———
011101100
000000000
———
111011001
100110001
———
111010000
100110001
———
111000011
100110001
———
111100101
100110001
———
110101001
100110001
———
100110000
100110001
———
000000010
000000000
———
000000101
000000000
———
000001011
000000000
———
000010110
000000000
———
000101100
000000000
———
001011000
000000000
———
010110000
000000000
———
101100000
100110001
———
010100010
000000000
———
101000100
100110001
———
011101010
000000000
———
11101010 = Остаток
Остаток (контрольная сумма) = 11101010, частное – 1101010111111011111100000001010.
Передаваемое сообщение: 011000010110011101100101011100111101010.
Заключение
При выполнении курсовой работы изучены вопросы сжатия данных и помехоустойчивого кодирования информации.
Построены код Хаффмана для оптимального кодирования алфавита источника сообщений и CRC-код, позволяющий обнаруживать ошибки, возникающие в ходе передачи сообщений.
Список использованных источников
- Колесник В.Д. Кодирование при передаче и хранении информации (Алгебраическая теория блоковых кодов) : учеб. пособие для вузов / В. Д. Колесник .— М. : Высш. шк., 2009 .— 551 с.
- Новиков Ф.А. Дискретная математика для программистов : учеб. пособие для вузов / Ф.А. Новиков .— 3-е изд. — М. и др. : Питер, 2008 .— 384с.
- Информатика : учебник для вузов / В. В. Трофимов [и др.] ; под ред. В.В. Трофимова ; СПбГУЭФ .— М. : Юрайт, 2011 .— 912 с.
- Морелос-Сарагоса Р. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение : учебное пособие / М. Морелос-Сарагоса; пер. с англ. В.Б. Афанасьева .— М. : Техносфера, 2005 .— 320с.