2018-03-09
88
Е. Н. Гилбертом и Э. Ф. Муром был предложен метод построения алфавитного кода, для которого 
.
Пусть символы алфавита некоторым образом упорядочены, например, a 1 ≤a 2 ≤…≤an. Код 
называется алфавитным, если кодовые слова лексикографически упорядочены, т.е. 
.
Процесс построения кода происходит следующим образом.
1. Вычисляем величины Qi, i= 1 ,n:
Q 1 =p 1 / 2,
Q 2 =p 1 +p2/ 2,
Q 3 =p 1 +p 2 +p 3 / 2,
…
Qn=p 1 +p 2 +…+pn- 1 +pn/ 2.
2. Представляем суммы Qi в двоичном виде.
3. В качестве кодовых слов берем 
младших бит в двоичном представлении Qi, 
.
Пример. Пусть дан алфавит A={ a 1, a 2, a 3, a 4, a 5, a 6} с вероятностями p 1=0.36, p 2=0.18, p 3=0.18, p4=0.12, p 5=0.09, p 6=0.07. Построенный код приведен в табл. 1.
Таблица 1
Код Гилберта-Мура
| ai | Pi | Qi | Li | кодовое слово |
| a 1 a2 a3 a4 a5 a6 | 1/23≤0.18 1/23≤0.18<1/22 1/22≤0.36<1/21 1/24≤0.07 1/24≤0.09 1/24≤0.12 | 0.09 0.27 0.54 0.755 0.835 0.94 | 4 4 3 5 5 5 | 0001 0100 100 11000 11010 11110 |
Средняя длина кодового слова не превышает значения энтропии плюс 2. Действительно,
Lср =4 . 0.18+4 . 0.18+3 . 0.36+5 . 0.07+5 . 0.09+5 . 0.12=3.92<2.37+2
|
|
|
Алгоритм на псевдокоде
Построение кода Гилберта-Мура
Обозначим:
n – количество символов исходного алфавита;
P – массив вероятностей символов;
Q – массив для величин Qi;
L – массив длин кодовых слов;
C – матрица элементарных кодов.
pr:=0
DO (i=1,…,n)
Q [i]:= pr+ P[i] /2
pr:=pr+ P[i]
L [i]:= - élog2P[i] ù +1 (использовать соотношение из п. 6.1)
OD
DO (i=1,…,n)
DO (j=1,…,L[i])
Q [i]:=Q [i] *2 (формирование кодового слова
C [i,j]:= ëQ [i]û в двоичном виде)
IF (Q [i] >1) Q [i]:=Q [i] - 1 FI
OD
OD
Порядок выполнения работы
1. Изучить теоретический материал.
2. Реализовать процедуру построения кода Гилберта-Мура.
3. Построить код Гилберта-Мура для текста на английском языке (использовать файл не менее 1 Кб). Распечатать полученную кодовую таблицу в виде:
| Символ | Вероятность | Кодовое слово | Длина кодового слова |
4. Сравнить среднюю длину кодового слова с энтропией исходного файла для построенного кода Гилберта-Мура. Полученные результаты оформить в виде таблицы:
| Энтропия исходного текста | Средняя длина кодового слова |
Контрольные вопросы
1. Почему код Гилберта-Мура считается почти оптимальным?
2. На сколько средняя длина кодового слова превосходит энтропию источника для кода Гилберта-Мура?
3. Какой код называется алфавитным?
4. Является ли алфавитным код Гилберта-Мура?
5. Почему код Гилберта-Мура имеет наибольшую избыточность среди рассмотренных почти оптимальных кодов?
Лабораторная работа № 6
|
|
|
Тема: Оптимальный код Хаффмана.
Цель работы: ознакомление с алгоритмами эффективного кодирования неравновероятных символов источника дискретных сообщений и сравнение их эффективности.
