Алфавитное кодирование

Начало математическому исследованию вопросов экономного кодирования, учитывающего вероятностные и структурные свойства информации, было положено работой К. Шеннона «Математическая теория связи», опубликованной в 1948 году. При построении алгоритмов кодирования Шенноном учитывались главным образом вероятностные свойства сообщений, порождаемых источником с конечным числом состояний. Однако эти вероятностные свойства определялись как вероятностными свойствами состояний источника, так и синтаксическими (структурными) свойствами последовательностей символов, генерируемых источником.

Введение 3
1. Теоретические основы задачи кодирования……………………………………………...6
1.1. Постановка задачи кодирования………….……………………………..….……………6
1.2. Первая теорема Шеннона…………………………………………………………….....10
1.3. Вторая теорема Шеннона……………………………………………………………….13
1.4. Помехоустойчивые коды…..........………………………………………….......…….…14
2. Алфавитное кодирование......................................................................................................17
2.1. Основные определения.....................................................................................................17
2.2. Проблема распознавания взаимной однозначности алфавитного кодирования.......18
2.3. Алгоритм построения префиксного кода по набору длин элементарных кодов........22
2.4. Алгоритмы экономного алфавитного кодирования......................................................23
2.4.1. Алгоритм Хаффмана...............................................................................................24
2.4.2. Алгоритм Фано........................................................................................................26
2.4.3. Алгоритм Шеннона.................................................................................................27
2.4.4. Энтропия и ее связь со стоимостью оптимального алфавитного
код