КАТЕГОРИИ: Архитектура-(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) |
Контрольні питання та задачі
Висновки Пример 2. Пусть первичный алфавит состоит из двух знаков с вероятностями, соответственно, 0,75 и 0,25. Сравнить избыточность кода Хаффмана при алфавитном и блочном двухбуквенном кодировании. При алфавитном кодировании:
,, При блочном двухбуквенном кодировании (очевидно,):
(в пересчете на 1 знак -), (в пересчете на знак - 0,844),.
Таким образом, блочное кодирование обеспечивает построение более оптимального кода, чем алфавитное. При использовании блоков большей длины (трехбуквенных и более) избыточность стремится к в полном соответствии с первой теоремой Шеннона. 5. Словникові коди. Алгоритм Лемпеля-Зіва (Lempel-Ziv, LZ) Рассмотренные ранее методы кодирования источника опираются на априорное знание вероятностей всех сообщений. В реальности статистика источника нередко неизвестна и единственный способ получения сведений о ней состоит в непосредственном исследовании самого потока сообщений. Этот подход лежит в основе словарного кодирования, имеющего множество разновидностей. Простейшей из них является базовый алгоритм Лемпеля-Зива, идея которого состоит в создании словаря фраз. Каждая новая строка словаря (новая фраза) включает в себя пару чисел: · – номер строки словаря с фразой, которая является частью новой фразы (адрес префикса уже имеющейся в словаре фразы) · ‑ обновляющий символ, преобразующий зафиксированную ранее фразу словаря в новую.
Эта пара и является результатом кодирования. Нет никакой нужды в предварительной передаче словаря декодирующей стороне: напротив, декодер без труда восстанавливает словарь самостоятельно в ходе декодирования, тем самым извлекая и само закодированное сообщение. Пример 3. Закодируем по Лемпелю-Зиву поток двоичных данных опираясь на словарь из 16 фраз. Предварительно мы имеем в словаре только две фразы, являющиеся самими символами алфавита 0 и 1, записанными как первая и вторая строки. Кодер видит, что первая самая короткая, отсутствующая в словаре фраза, есть 10 и добавляет ее как (2,0), где 2 – ссылка на вторую строку словаря, а 0 – новый символ, формирующий новую фразу для словаря. Все последующие шаги полностью аналогичны и понятны из приведенной таблицы. Итоговый код равномерен: его слова содержат четыре бита префикса плюс один обновляющий бит. Закодированный поток 00100001110011000010010110111110000 10001101001010110110011011101111010 содержит 70 битов при 74-х битах исходного. Для столь коротких потоков весьма вероятно даже увеличение длины последовательности после кодирования, однако, с увеличением длины входной последовательности среднее число битов на букву источника стремится к энтропии сообщения, то есть к потенциальной нижней границе. Чтобы понять ход декодирования, достаточно рассмотреть приведенный пример в обратном порядке, обратившись к потоку битов с выхода кодера. По получении очередного двоичного кодового слова, декодер разбивает его на префикс (в примере – 4 бита) и обновляющий бит. Префикс дает адрес части фразы, уже содержащейся в словаре. Вместе с обновляющим битом она вводится в словарь как его новая строка. Например, после того как декодер принимает слово 00100, он распознает префикс как 1 (присутствует в словаре под номером 2). Наряду с обновляющим символом 0 это дает новый вход словаря для фразы 10, помещаемой в третьей строке словаря, и т.д. Одновременно каждая новая фраза выдается на выход как результат декодирования. Если при кодировании заполнение словаря происходит слева направо (фраза, затем кодовое слово), в ходе декодирования словарь формируется в обратном порядке (от кодового слова к фразе).
1. Приведите примеры обратимого и необратимого кодирования помимо рассмотренных в тексте. 2. В чем смысл первой теоремы Шеннона для кодирования? 3. Первичный алфавит содержит 8 знаков с вероятностями: «пробел» - 0,25; «?» - 0,18; «&» - 0,15; «*» - 0,72; «+» - 0,1; «%» - 0,08; «#» - 0,07и «!» - 0,05. В соответствии с правилами, изложенными в п.3.2.1, предложите вариант неравномерного алфавитного двоичного кода с разделителем знаков, а также постройте коды Шеннона-Фано и Хаффмана; сравните их избыточности. 4. Постройте в виде блок-схемы последовательность действий устройства, производящего декодирование сообщения, коды которого удовлетворяют условию Фано. Реализуйте программно на каком-либо языке программирования. 5. Является ли кодирование по методу Шеннона-Фано и по методу Хаффмана однозначным? Докажите на примере алфавита А, описанного в п. 2.1. 6. С помощью электронных таблиц проверьте правильность данных о средней длине кода К(А,2) для всех обсуждавшихся в п. 2.1. примерах неравномерного алфавитного кодирования. 7. Продолжите пример 3.2, определив избыточность при трехбуквенном блочном кодировании. 8. Для алфавита, описанного в задаче 3, постройте вариант минимального кода Бодо. 9. Проверьте данные об избыточность кода Бодо для русского и английских языков, приведенных в п.2.2. Почему избыточность кода для русского языка меньше? 10. Почему в 1 байте содержится 8 бит? 11. Оцените, какое количество книг объемом 200 страниц может поместиться: (a) на флеш-памяти 8 Гб; (b) на оптическом DVD-диске емкостью 4,7 Гб? (c) на жестком магнитном диске винчестера емкостью 500 Гб? 12. Почему в компьютерных устройствах используется байтовое кодирование? 13. Что такое «лексикографический порядок кодов»? Чем он удобен? 14. Для цифр придумайте вариант байтового кодирования. Реализуйте процедуру кодирования программно (ввод - последовательность цифр; вывод - последовательность двоичных кодов в соответствии с разработанной кодовой таблицей). 15. Разработайте программу декодирования байтовых кодов из задачи 13. 16. Код Морзе для цифр следующий:
Считая алфавит цифр самостоятельным, а появление различных цифр равновероятным, найдите избыточность кода Морзе для цифрового алфавита. 17. В лексиконе «людоедки» Эллочки Щукиной из романа Ильфа и Петрова «12 стульев» было 17 словосочетаний («Хо-хо!», «Ого!», «Блеск!», «Шутишь, парниша», «У вас вся спина белая» и пр.). (a) Определите длину кода при равномерном словесном кодировании. (b) Предложите вариант равномерного кодирования данного словарного запаса.
[1] Был разработан в 1952 году аспирантом Массачусетского технологического института Дэвидом Хаффманом при написании им курсовой работы.
Дата добавления: 2013-12-12; Просмотров: 685; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |