Контрольні питання та задачі

Висновки

Пример 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 году аспирантом Массачусетского технологического института Дэвидом Хаффманом при написании им курсовой работы.