- •Министерство образования и науки, молодёжи и спорта украины
- •Тема 1. Предмет теории информации и количественная мера информации
- •1.2 Этапы обращения информации
- •1.3 Система передачи информации
- •1.4 Задачи и постулаты прикладной теории информации
- •1.5. Количественная оценка информации дискретного источника. Энтропия.
- •1.6 Фундаментальные свойства энтропии
- •Тема 2. Основные виды энтропии дискретных источников. Условная и взаимная энтропии.
- •2.1 Условная энтропия.
- •2.2 Основные свойства условной энтропии.
- •2.3 Взаимная энтропия. Свойства энтропии объединения.
- •Тема 3. Эффективное кодирование источника дискретных сообщений в канале без помех.
- •3.1 Избыточность информации, причины ее появления.
- •3.2 Способы сокращения избыточности.
- •3.3 Теорема Шеннона для канала без помех.
- •4.1 Общие понятия и элементы теории кодирования
- •4.2 Цели кодирования
- •4.3 Оптимальные неравномерные коды
- •4.4 Коды Шеннона-Фэно
- •4.5 Коды Хаффмена
- •4.6 Особенности эффективных кодов.
- •Тема 4. Кодирование источника дискретных сообщений в канале с помехами. Общие принципы помехоустойчивого кодирования.
- •5.1 Кодирование информации для канала с помехами. Теорема Шеннона для канала с помехами.
- •5.2 Общие принципы использования избыточности
- •5.3 Связь корректирующей способности кода с кодовым расстоянием
- •6.1 Корректирующие свойства кодов с избыточностью.
- •6.2 Классификация корректирующих кодов
- •Тема 5. Регулярные методы построения двоичных помехоустойчивых кодов
- •7.1 Линейные коды. Общие медоды построения.
- •7.2 Определение числа добавочных разрядов r.
- •7.3 Построение образующей(порождающей) матрицы |om|.
- •7.4 Порядок кодирования
- •7.5 Порядок декодирования
- •7.6 Систематические коды. Код Хэмминга.
- •7.7 Обнаружение и исправление ошибок в коде Хэмминга
- •8.1 Двоичные циклические коды
- •8.2 Некоторые свойства циклических кодов
- •8.3 Матричное описание циклических кодов
- •8.4 Выбор образующего полинома
- •8.5 Декодирование циклических кодов
- •Тема 6. Построение кодов заданой помехоустойчивости. Применение недвоичных помехоустойчивых кодов.
- •9.1 Матричное описание циклических кодов.
- •9.2 Коды Боуза — Чоудхури — Хоквингема (бчх)
- •9.3 Систематический вид циклического кода.
- •9.4 Коды Рида–Соломона и их применение.
- •9.5 Циклический избыточный код crc
- •Тема 7. Информационные характеристики источников непрерывных сообщений. Источники с максимальной энтропией. Максимальная пропускающая способность канала связи с помехами.
- •10.1 Информационные характеристики источников непрерывных сообщений
- •10.2 Энтропия равномерного закона распределения
- •10.3 Энтропия гауссового закона распределения.
- •11.1 Пропускная способность канала связи с помехами для непрерывных сообщений
- •Тема 8. Методы кодирования информации со сжатием.
- •12.1 Подстановочные или словарно-ориентированные алгоритмы сжатия информации. Методы Лемпела-Зива.
- •13.1 Описание алгоритма сжатия lzw
- •Декодирование по lzw
- •Достоинства и недостатки lzw
- •13.2 Применение lz-алгоритмов упаковки данных
- •14.1 Кодирование длин повторений
- •14.2 Дифференциальное кодирование
- •Тема 9. Методы кодирования со сжатием и с потерями информации..
- •15.1 Методы сжатия с потерей информации
- •15.2 Точность. Помехи и искажения. Приближенное восстановление
- •15.5 Кодирование преобразований. Стандарт сжатия jpeg
- •Или же, в матричной форме,
- •Тема 10. Методы кодирования физических сигналов в компьютерных сетях.
- •16.1 Кодирование на физическом уровне.
- •16.2 Самонихронизирующиеся коды - коды rz и Манчестер-II
- •16.3 Несамосинхронизирующиеся коды. - код nrz
- •16.4 Высокоскоростные коды - код mlt-3 и pam 5
- •Еще более высокоскоростной код - код pam 5
- •16.5 Требуемая полоса частот для передачи данных и ширина спектра сигнала
- •Ширина спектра сигнала
4.3 Оптимальные неравномерные коды
Определения.
Неравномерными называют коды, кодовые слова которых имеют различную длину.
Оптимальность можно понимать по-разному, в зависимости от критерия. В данном случае таким критерием является средняя длина кодового слова. Оптимальность с учетом этого критерия понимается в смысле минимальной длины средней длины кодового слова.
Дальнейшие выводы будем делать при следующих условиях:
Пусть буквы первичного источника a1 a2.,.., ак имеют вероятности появления p1, р2, ... , рк . Упорядочим буквы в порядке убывания вероятностей их появления в сообщении и пронумеруем их в этом порядке. В результате p1 > р2 >...> рк . Для кодирования будем использовать вторичный алфавит, состоящий из 2 букв - 0 и 1, т.е. двоичный код.
Пусть x1, х2, ... , хk - множество кодовых слов, имеющих длину n1, n2, ... , nk. Ограничимся также рассмотрением только префиксных кодов. Результаты, полученные в отношении длин кодовых слов для префиксных кодов, можно распространять на весь класс однозначно декодируемых кодов, а результаты, полученные для двоичных кодов можно обобщить на коды с любым объемом вторичного алфавита.
4.4 Коды Шеннона-Фэно
Независимо друг от друга Шенноном и Фэно была предложена процедура построения эффективного кода. Получаемый при ее помощи код называют кодом Шеннона-Фэно.
Код Шеннона-Фэно строится следующим образом:
1) буквы алфавита сообщений выписываются в таблицу в порядке убывания вероятностей;
2) затем они разделяются на две группы так, чтобы суммы вероятностей в каждой из групп были по возможности одинаковы;
3) всем буквам верхней половины в качестве первого символа приписывается 1, а всем нижним буквам символ 0;
4) каждая из полученных групп, в свою очередь, разбивается на две подгруппы с одинаковыми суммарными вероятностями и т. д. ;
5) процесс повторяется до тех пор, пока в каждой подгруппе не останется по одной букве.
Рассмотрим первичный источник из восьми символов. Ясно, что при обычном (не учитывающем статистических характеристик) кодировании для представления каждой буквы требуется три символа. Пусть вероятности появления букв первичного источника равны:
p1=1/2; p2=1/4; p3=1/8; p4=1/16; p5=1/32; p==1/64; p7=1/128; p8=1/128/
Наибольший эффект сжатия получается в случае, когда вероятности букв представляют собой целочисленные отрицательные степени двойки. Среднее число символов на букву в этом случае точно равно энтропии.
Убедимся в этом, вычислив энтропию для нашего примера:
и среднее число символов на букву первичного алфавита.
где n(zi) —число символов в кодовой комбинации , соответствующей букве zi. Характеристики такого ансамбля и коды букв представлены в таблице 4.2.
Таблица 4.2.
В более общем случае для алфавита из восьми букв среднее число символов на букву будет меньше трех, но больше энтропии алфавита H(Z). Для ансамбля букв, приведенного в следующей таблице для другого источника, энтропия равна 2,76, а среднее число символов на букву 2,84.
Таблица 4.3.
Следовательно, некоторая избыточность в последовательностях символов осталась. Из теоремы Шеннона следует, что эту избыточность также можно уменьшить, если перейти к кодированию достаточно большими блоками.
Рассмотрим сообщения, образованные с помощью алфавита, состоящего всего из двух букв Z1 и Z2, с вероятностями появления соответственно p(Z1)=0,9 и p(Z2) =0,1.
Поскольку вероятности не равны, то последовательность из таких букв будет обладать избыточностью. Однако при побуквенном кодировании Шеннона-Фано никакого эффекта не получается.
Действительно, на передачу каждой буквы требуется символ либо 1, либо 0, и nср.=1 в то время как энтропия равна 0,47.
При кодировании блоков, содержащих по две буквы, получим коды, показанные в таблице.
Таблица 4.4.
Так как буквы статистически не связаны, вероятности блоков определяются как произведение вероятностей составляющих букв.
Среднее число символов на блок получается равным 1,29; а на букву -0,645.
Кодирование блоков, содержащих по три буквы, дает еще больший эффект. Соответствующий ансамбль и коды приведены в таблице.
Таблица 4.5.
Среднее число символов на блок равно 1,59; а на букву - 0,53; что всего на 12% больше энтропии. Теоретический минимум H(Z) = 0,47 может быть достигнут при кодировании блоков, включающих бесконечное число букв:
lim lcp=H(Z), при m→∞
Следует подчеркнуть, что увеличение эффективности кодирования при укрупнении блоков, не связано с учетом все более далеких статистических связей, так как нами рассматривались алфавиты с некоррелированными буквами. Повышение эффективности определяется лишь тем, что набор вероятностей, получающийся при укрупнении блоков, можно делить на более близкие по суммарным вероятностям подгруппы.
Рассмотренная нами методика Шеннона—Фэно не всегда приводит к однозначному построению кода. В методике присутствует элемент субъективизма. Ведь при разбиении на подгруппы можно сделать большей по вероятности как верхнюю, так и нижнюю подгруппу.
Поэтому конкретный полученный код может оказаться не самым лучшим. При построении эффективных кодов с основанием т>2 неопределенность разделения на группы становится еще большей.
От указанного недостатка свободна методика Хаффмена. Она гарантирует однозначное построение кода с наименьшим для данного распределения вероятностей средним числом символов на букву.