КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Алгоритм Фано префиксного кодирования
Пусть кодируемое сообщения таково, что известны вероятности вхождения каждого символа, причем, p1 ≥ p2 ≥… ≥ pn (1) При этом =1 (2) То есть прежде чем производить кодирование, необходимо расположить буквы алфавита А так, чтобы удовлетворялось условие (1). Затем проверить равенство (2 ), после чего назначать коды. Итак, имеем p1 = 0,… p2 = 0,… …. pn = 0,…. pi =1
Алгоритм. Разобьем вероятности на две части так, чтобы суммы вероятностей каждой из частей были примерно равны. Пусть это будет после вероятности: pi pj. Назначим коды: в верхней части 0, а в нижней 1. Теперь разбиваем верхнюю часть на две части, с примерно равными суммами вероятности: pi pj. И вновь делаем то же самое: для данного деления: к имеющимся кодам добавляем в верхней части 0, а в нижней 1. И так далее до тех пор, пока в верхней части не останется одна строка. Добавим в нее 0, а в нижнюю часть 1. Последнюю нижнюю часть опять разбиваем на две части (если она содержит более одной строки) и так далее, пока в нижней части не останется одна строка. После этого переходим к делению предыдущей нижней части и повторяем процедуру назначения кодов. Полученная схема кодирования является префиксной, так как код первой строки и код второй строки отличаются друг от друга, по крайней мере, в последнем знаке, то эти коды не могут быть префиксами друг друга. Аналогично, так как в верхней части разбиения добавляется 0, а в нижней 1, то ни один из кодов верхней части не может быть префиксом кода нижней части. Таким образом, схема префиксная, следовательно, разделимая. Пример: пусть заданы вероятности 0,25 0,15 0,12 0,11 0,08 0,06 0,06 0,06 0,06 0,05. После первого разбиения получим вероятности коды 0,25 0 0,15 0 0,12 0 0,11 1 0,08 1 0,06 1 0,06 1 0,06 1 0,06 1 0,05 1 После второго разбиения вероятостити коды 0,25 0 00 код назначен 0,15 0 01 0,12 0 01 0,11 1 0,08 1 0,06 1 0,06 1 0,06 1 0,06 1 0,05 1 После третьего разбиения 0,25 0 00 0,15 0 01 010 код назначен 0,12 0 01 011 код назначен 0,11 1 0,08 1 0,06 1 0,06 1 0,06 1 0,06 1 0,05 1 После четвертого разбиения 0,25 0 00 00 0,15 0 01 010 0,12 0 01 011 0,11 1 1 10 0,08 1 1 10 0,06 1 1 10 0,06 1 1 11 0,06 1 1 11 0,06 1 1 11 0,05 1 1 11 Окончательно получим: 0,25 0 00 0,15 0 01 010 0,12 0 01 011 0,11 1 1 10 100 0,08 1 1 10 101 1010 0,06 1 1 10 101 1011 0,06 1 1 11 11 11 110 1100 0,06 1 1 11 11 11 110 1101 0,06 1 1 11 11 11 111 111 1110 0,05 1 1 11 11 11 111 111 1111 Если кодирование равномерное, то цена кодирования по формуле Хартли равна:= log 104. По алгоритму Фано:= pi l i =3,12, что меньше 4, а значит, общая длина кода будет меньше.
Дата добавления: 2014-01-06; Просмотров: 691; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |