Алгоритм на псевдокоде

 Построение кода Шеннона

Обозначим:

n – количество символов исходного алфавита;

P – массив вероятностей, упорядоченных по убыванию;

Q – массив для величин Q_i;

L – массив длин кодовых слов;

C – матрица элементарных кодов.

 

P [0]:=0, Q [0]:=0

DO (i=1,…,n)

    Q [i]:= Q [i-1]+P [i]

    L [i]:= - élog₂P[i] ù    (длину кодового слова определять из 

OD                                       соотношения, указанного выше)

 

DO (i=1,…,n)

    DO (j=1,…,L[i])

              Q [i-1]:=Q [i-1] _*2               (формирование кодового

                       C [i,j]:= ëQ [i-1]û                  слова в двоичном виде)

                  IF (Q [i-1]>1) Q [i-1]:=Q [i-1] - 1 FI

              OD

OD

 

Порядок выполнения работы

1. Изучить теоретический материал.

2. Реализовать процедуру построения кода Шеннона.

3. Построить код Шеннона для текста на английском языке (использовать файл не менее 1 Кб). Распечатать полученную кодовую таблицу в виде:

 

Символ	Вероятность	Кодовое слово	Длина кодового слова

 

4. Сравнить среднюю длину кодового слова с энтропией исходного файла для построенного кода Шеннона. Полученные результаты оформить в виде таблицы:

 

Энтропия исходного текста	Средняя длина кодового слова

Контрольные вопросы

1. Почему код Шеннона считается почти оптимальным?

2. Насколько средняя длина кодового слова превосходит энтропию источника для кода Шеннона?

3. Какой код называется алфавитным?

4. Являются ли алфавитным код Шеннона?

 

 

Лабораторная работа № 4

Тема: Код Фано.

 

Теоретические сведения

Метод Фано построения префиксного почти оптимального кода, для которого , заключается в следующем. Упорядоченный по убыванию вероятностей Cписок букв алфавита источника делится на две части так, чтобы суммы вероятностей букв, входящих в эти части, как можно меньше отличались друг от друга. Буквам первой части приписывается 0, а буквам из второй части – 1. Далее также поступают с каждой из полученных частей. Процесс продолжается до тех пор, пока весь список не разобьется на части, содержащие по одной букве.

Пример. Пусть дан алфавит A={ a ₁, a ₂, a ₃, a ₄, a ₅, a ₆} с вероятностями p ₁=0.36, p ₂=0.18, p ₃=0.18, p ₄=0.12, p ₅=0.09, p ₆=0.07. Построенный код приведен в табл. 1 и на рис. 1.

Таблица 1

 Код Фано

ai	Pi	кодовое слово				Li
a1	0.36	0	0			2
a2	0.18	0	1			2
a3	0.18	1	0			2
a4	0.12	1	1	0		3
a5	0.09	1	1	1	0	3
a6	0.07	1	1	1	1	4

 

 

 

 

Рис. 1 – Кодовое дерево для кода Фано

Полученный код является префиксным и почти оптимальным со средней длиной кодового слова

L_ср =0.36 ^. 2+0.18 ^. 2+0.18 ^. 2+0.12 ^. 3+0.09 ^. 4+0.07 ^. 4=2.44