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

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

Обозначим

P–массив вероятностей символов алфавита

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

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

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

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

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

SL – сумма элементов первой части массива

SR – сумма элементов второй части массива.

 

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)

SL:= 0

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

SL:=SL+ P [i]

OD

SR:=P [R]

m:= R

DO (SL ≥ SR)

m:=m-1

SL:=SL - P [m]

SR:=SR+ P [m]

OD

Med:= m

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

Е. Н. Гилбертом и Э. Ф. Муром был предложен метод построения алфавитного кода, для которого .

Пусть символы алфавита некоторым образом упорядочены, например, a1≤a2≤…≤an. Код называется алфавитным, если кодовые слова лексикографически упорядочены, т.е. .

Процесс построения кода происходит следующим образом.

1. Вычислим величины Qi, i=1,n:

Q1=p1/2,

Q2=p1+p2/2,

Q3=p1+p2+p3/2,

Qn=p1+p2+…+pn-1+pn/2.

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

3. В качестве кодовых слов возьмем младших бит в двоичном представлении Qi, .

Пример. Пусть дан алфавит A={a1, a2, a3, a4, a5, a6} с вероятностями p1=0.36, p2=0.18, p3=0.18, p4=0.12, p5=0.09, p6=0.07. Построенный код приведен в таблице 8.

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

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

 

Средняя длина кодового слова не превышает значения энтропии плюс 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

 








Дата добавления: 2019-02-07; просмотров: 283;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.005 сек.