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

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

p₀:=0, Q₀:=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

Код Фано

Метод Фано построения префиксного почти оптимального кода заключается в следующем. Упорядоченный по убыванию вероятностей список букв алфавита источника делится на две части так, чтобы суммы вероятностей букв, входящих в эти части, как можно меньше отличались друг от друга. Буквам первой части приписывается 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. Построенный код приведен в таблице и на рисунке.

Таблица 12 Код Фано

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

Рисунок 68 Кодовое дерево для кода Фано

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

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

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

Алгоритм Фано

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

L – левая граница обрабатываемой части массива P

R– правая граница обрабатываемой части массива P

k – длина уже построенной части элементарных кодов

С – массив элементарных кодов

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

Fano(L,R,k)

IF (L<R)

k:=k+1

m:=Med(L,R)

DO (i=L,…,R)

IF (i≤m) C[i,k]:=0, Length[i]:= Length[i]+1

ELSE C[i,k]:=1, Length[i]:= Length[i]+1

FI

OD

Fano (L,m,k)

Fano (m+1,R,k)

FI

Функция Med находит медиану массива P, т.е. такой индекс L≤m≤R, что

величина минимальна.

Med (L,R)

S_L:=0

DO (i=L,…,R-1)

S_L:=S_L+p[i] <сумма элементов первой части>

OD

S_R:=p[R] <сумма элементов второй части>

m:=R

DO (S_L ≥ S_R)

m:=m-1

S_L:=S_L-p[m]

S_R:=S_R+p[m]

OD

Med:=m

Алфавитный код Гилберта – Мура

Рассмотрим источник с алфавитом А={a₁,a₂,…,a_n} и вероятностями p₁,…p_n. Пусть символы алфавита некоторым образом упорядочены, например, a₁≤a₂≤…≤a_n. Алфавитным называется код, в котором кодовые слова лексико-графически упорядочены, т.е. φ(a₁)≤φ(a₂)≤…≤φ(a_n).

Е.Н. Гилбертом и Э.Ф. Муром предложили метод построения алфавитного кода, для которого L_ср < H+2. Процесс построения происходит следующим образом.

1. Составим суммы Q_i, i=1,n, вычисленные следующим образом:

Q₁=p₁/2, Q₂=p₁+p₂/2, Q₃=p₁+p₂+p₃/2,…, Q_n=p₁+p₂+…+p_n-1+p_n/2.

2. Представим суммы Q_i в двоичном виде.

3. В качестве кодовых слов возьмем -log₂p_i +1 младших бит в двоичном представлении Q_i.

Пример. Пусть дан алфавит 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. Построенный код приведен в таблице.

Таблица 13 Код Гилберта-Мура

ai	Pi	Qi	Li	кодовое слово
a1 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