Теория информации и кодирования

Титульный листОглавление TOC \o "1-3" \h \z \u Задание на работу PAGEREF _Toc96892470 \h 3Введение PAGEREF _Toc96892471 \h 4Задание 1 PAGEREF _Toc96892472 \h 5Задание 2 PAGEREF _Toc96892473 \h 11Заключение PAGEREF _Toc96892474 \h 13Список использованных источников PAGEREF _Toc96892475 \h 14Задание на работуЗадание 1 Построить кодовое дерево и код Хаффмена для последовательности символов в соответствии с вариантом. Подсчитать энтропию исходного сообщения и среднюю длину получившегося кода.Задание 2 В соответствии с номером варианта получить для приведенного в шестнадцатеричном формате в виде четырех пар 4-битовых чисел исходного 32-битного сообщения циклический избыточный код.ВведениеВопросы сжатия данных и помехоустойчивого кодирования информации играют важную роль при построении телекоммуникационных систем и систем архивного хранения. В первом случае преследуется цель обеспечения максимальной скорости и надежности передачи данных при неизменной физической пропускной способности канала связи. Во втором – минимизации объема носителей, задействованных для хранения информации. Эти вопросы могут быть решены путем использования различных кодов, обеспечивающих эффективное представление данных. Сжатие информации представляет собой процесс преобразования исходного сообщения из одной кодовой системы в другую, в результате которого уменьшается его размер. Алгоритмы, предназначенные для сжатия информации, можно разделить на две большие группы: реализующие сжатие без потерь (обратимое сжатие) и реализующие сжатие с потерями (необратимое сжатие). Обратимое сжатие подразумевает абсолютно точное восстановление данных после декодирования и может применяться для сжатия любой информации. Оно всегда приводит к снижению объема выходного потока информации без изменения его информативности, то есть без потери информационной структуры. Более того, из выходного потока, при помощи восстанавливающего или декомпрессирующего алгоритма, можно получить входной, а процесс восстановления называется декомпрессией или распаковкой и только после процесса распаковки данные пригодны для обработки в соответствии с их внутренним форматом. Сжатие без потерь применяется для текстов, исполняемых файлов, высококачественного звука и графики. Циклические коды составляют самый важный класс линейных кодов. Их название объясняется тем, что если над любым допустимым словом такого кода выполнить циклический сдвиг (в любую сторону и на любое число разрядов), то вновь получается допустимое слово того же кода. Циклические коды могут использоваться для внесения избыточности в сообщения, передаваемые по каналам связи, чтобы при возникновении потерь, возникающих в результате различных помех, можно было восстановить исходную информацию. Настоящая курсовая работа посвящена построению двух кодов из рассмотренных классов, а именно коду Хаффмана для оптимального кодирования алфавита источника сообщений и CRC-коду для обнаружения ошибок, возникающих в ходе передачи сообщений.Задание 1 Построить кодовое дерево и код Хаффмена для последовательности символов в соответствии с вариантом. Подсчитать энтропию исходного сообщения и среднюю длину получившегося кода.Решение:Строка: transmit in their place sequences of symbols.Рассчитаем вероятность появления каждого символа в строке (Всего символов:45)СимволКоличествоВероятностьпробел66/45e55/45s55/45i33/45n33/45t33/45o22/45c22/45a22/45r22/45l22/45m22/45y11/45f11/45.11/45b11/45p11/45h11/45u11/45q11/45СимволВероятностьпробел6/456/456/456/456/456/456/456/456/456/456/457/458/458/4510/4512/4515/4518/4527/451e5/455/455/455/455/455/455/455/455/455/456/456/457/458/458/4510/4512/4515/4518/45s5/455/455/455/455/455/455/455/455/455/455/456/456/457/458/458/4510/4512/45i3/453/453/453/453/454/454/454/454/454/455/455/456/456/457/458/458/45n3/453/453/453/453/453/454/454/454/454/454/455/455/456/456/457/45t3/453/453/453/453/453/453/454/454/454/454/454/455/455/456/45o2/452/452/452/452/453/453/453/454/454/454/454/454/455/45c2/452/452/452/452/452/453/453/453/454/454/454/454/45a2/452/452/452/452/452/452/453/453/453/454/454/45r2/452/452/452/452/452/452/452/453/453/453/45l2/452/452/452/452/452/452/452/452/453/45m2/452/452/452/452/452/452/452/452/45y1/452/452/452/452/452/452/452/45f1/451/452/452/452/452/452/45.1/451/451/452/452/452/45b1/451/451/451/452/45p1/451/451/451/45h1/451/451/45u1/451/45q1/45Построим дерево ХаффменаСимволКодпробел101e011s010i1100n1001t1000o11011c11010a0011r0010l0001m0000y111111f111110.111101b111100p111011h111010u111001q111000Рассчитаем энтропию исходного сообщения и среднюю длину получившегося кода:Символpilog2pi-pi ∙log2(pi)li пробел0,133333333-2,9068905960,38758541330,4e0,111111111-3,1699250010,35221388930,333333333s0,111111111-3,1699250010,35221388930,333333333i0,066666667-3,9068905960,26045937340,266666667n0,066666667-3,9068905960,26045937340,266666667t0,066666667-3,9068905960,26045937340,266666667o0,044444444-4,4918530960,19963791550,222222222c0,044444444-4,4918530960,19963791550,222222222a0,044444444-4,4918530960,19963791540,177777778r0,044444444-4,4918530960,19963791540,177777778l0,044444444-4,4918530960,19963791540,177777778m0,044444444-4,4918530960,19963791540,177777778y0,022222222-5,4918530960,1220411860,133333333f0,022222222-5,4918530960,1220411860,133333333.0,022222222-5,4918530960,1220411860,133333333b0,022222222-5,4918530960,1220411860,133333333p0,022222222-5,4918530960,1220411860,133333333h0,022222222-5,4918530960,1220411860,133333333u0,022222222-5,4918530960,1220411860,133333333q0,022222222-5,4918530960,1220411860,133333333 1 Н=4,047548242ML(X)=4,088888889Задание 2 В соответствии с номером варианта получить для приведенного в шестнадцатеричном формате в виде четырех пар 4-битовых чисел исходного 32-битного сообщения циклический избыточный код.Последовательность символов: 73 61 67 65Полином: x8+x2+x+1Решение:Cтепень полинома W=873 - 111001161 - 110000167 - 110011165 – 1100101Исходное сообщение 1110011110000111001111100101Полином G =100000111Сообщение, дополненное W битами : M' =111001111000011100111110010100000000Поделим M' на G с использованием правил CRC-арифметики.Полученный остаток и будет контрольной суммой.Остаток=11011001Ответ: 111001111000011100111110010111011001ЗаключениеВ ходе выполнения курсовой работы по дисциплине «Теория информации и кодирования» изучен алгоритм Хаффмена для оптимального префиксного кодирования алфавита с минимальной избыточностью, а также изучены принципы генерации циклического избыточного кода для обнаружения ошибок в передаваемых по каналам связи сообщениях Список использованных источниковКолесник В.Д. Кодирование при передаче и хранении информации (Алгебраическая теория блоковых кодов) : учеб. пособие для вузов / В. Д. Колесник .— М. : Высш. шк., 2009 .— 551 с.А.С. Новиков Методические указания к курсовой работе по дисциплине «Теория информации и кодирования»: учеб. пособие для вузов / А.С. Новиков, 2018.— 14 с.