Главная Обратная связь

Дисциплины:

Архитектура (936)
Биология (6393)
География (744)
История (25)
Компьютеры (1497)
Кулинария (2184)
Культура (3938)
Литература (5778)
Математика (5918)
Медицина (9278)
Механика (2776)
Образование (13883)
Политика (26404)
Правоведение (321)
Психология (56518)
Религия (1833)
Социология (23400)
Спорт (2350)
Строительство (17942)
Технология (5741)
Транспорт (14634)
Физика (1043)
Философия (440)
Финансы (17336)
Химия (4931)
Экология (6055)
Экономика (9200)
Электроника (7621)


 

 

 

 



Оптимальное (эффективное) кодирование



Для полного использования пропускной способности канала необходимо осуществить эффективное кодирование, которое обеспечит устранение избыточности в сообщениях, что приходят от источника. Кодирование при котором обеспечивается полное использование пропускной способности канала называется оптимальным.

Первая теорема Шеннона дает ответ на вопрос, всегда ли можно осуществить оптимальное кодирование: если есть канал с пропускной способностью С, то сообщение из любого источника с энтропией Н(х)можно закодировать так, что окажется возможным передавать эти сообщения со скоростью как угодно близкой к С/Н(х) сообщений в секунду (С двоичных единиц за секунду. Рассмотрим справедливость теоремы для двоичного канала связи.

Пусть алфавит источника сообщений создает конечную систему.

Для сообщения хi длинна кодовой комбинации равна mi, а вероятность ее появления Р(хі). Количество информации что содержится в i-м сообщении равно Ixi=-logP(xi). Пропускная способность канала будет полностью использована, если на каждыйдвоичный символ будет приходится один бит информации. Это будет в том случае, когда количество двоичных символов в кодовой комбинации будет равно количеству информации что содержится в ней. Таким образом, условием опримального кодирования является равенство.

Усреднив это сообщение повсем возможным сообщениям получим:

Меньше чем Н(х) средняя длинна сообщения быть не может.

Максимальная скорость что может быть достигнута в двоичном канале без помех равна:

Оптимальные коды:

1) Код Шеннона-Фано

Все множество возможных сообщений записывается в порядке уменьшения вероятности их появления, а потом разбивается на две группы так, что бы суммы вероятностей в одной и во второй группе были примерно одинаковы. Первой цифрой для одной (н-р верхней) группы выбирается ноль, а для другой – единица или наоборот. После этого каждая группа разделяется на две подгруппы с приме6рно одинаковыми суммарными вероятностями, причем в верхних подгруппах следующей цифрой выбирают ноль, а в нижних – единицу.

Процесс повторяется до тех пор пока в каждой подгруппе не останется по одному сообщению. Оптимальность обеспечивается: 1) ни одна кодовая комбинация не может быть началом другой 2) так как при каждом разбиении мы приписываем к одной подгруппе ноль, а к другой единице, обеспечивается равномерное распределение нулей и единиц – необходимое условие полного использования пропускной способности канала, 3) При каждом разделении сообщений на две группы с примерно равными суммарными вероятностями, эти вероятности в сообщении каждой группы примерно вдвое меньше начальных. Поэтому сообщение хi, что после k разбивок останется единственным в своей группе будет примерно равно Р(хi)=1/2k, откуда k=-log2P(xi). Но число знаков в кодовой комбинации (mi) равно числу разбивок, таким образом ее длинна равна:

 
 


Что отвечает условию оптимального кодирования. Пример:

       
   
 
 

 

 


При решении практических задач не всегда удается разделить таблицу на две части с одинаковой вероятностью. Этот не достаток устраняется при использовании кода Хаффмана.

 

2) Код Хаффмана

Аналогично к коду Шеннона-Фано при использовании кода Хаффмана строится таблица в порядке уменьшения вероятности появления сообщений. Сообщения хn и хn-1 соединяются в одну группу с вероятностью Р(х)=Р(хn)+Р(хn-1). Такое объединение повторяется до тех пор пока Р(х) не станет равно 1.

 
 

 


Отличие в кодировании в том, что в коде Шеннона-Фано формирование начинается со старшого (лівого) разряда. В коде Хаффмана кодове комбинации котируються начиння с младшего (правого) разряда.

 


Просмотров 1130

Эта страница нарушает авторские права



allrefrs.ru - 2023 год. Все права принадлежат их авторам!