Кодирование Шеннона-Фано-Элиаса

В теории информации кодирование Шеннона-Фано-Элиаса является предшественником арифметического кодирования , в котором вероятности используются для определения кодовых слов. Он назван в честь Клода Шеннона , Роберта Фано и Питера Элиаса .

Описание алгоритма

Учитывая дискретную случайную величину X значений , упорядоченных подлежащих кодированию, пусть $p(x)$ быть вероятностью для любого x в X . Определить функцию

${\bar {F}}(x)=\sum _{x_{i}<x}p(x_{i})+{\frac {1}{2}}p(x)$

Алгоритм:

Для каждого x в X ,

Пусть Z — двоичное разложение ${\bar {F}}(x)$.

Выберите длину кодирования x , $L(x)$, чтобы быть целым числом $\left\lceil \log _{2}{\frac {1}{p(x)}}\right\rceil +1$

Выберите кодировку x , $code(x)$, будь первым $L(x)$ наиболее значимые биты после десятичной точки Z .

Пример

Пусть X = { A , B , C , D } с вероятностями p = {1/3, 1/4, 1/6, 1/4}.

Для А

${\bar {F}}(A)={\frac {1}{2}}p(A)={\frac {1}{2}}\cdot {\frac {1}{3}}=0.1666\ldots$

В двоичном формате Z ( A ) = 0,001 0101010 ...

$L(A)=\left\lceil \log _{2}{\frac {1}{\frac {1}{3}}}\right\rceil +1=\mathbf {3}$

код ( А ) 001

Для Б

${\bar {F}}(B)=p(A)+{\frac {1}{2}}p(B)={\frac {1}{3}}+{\frac {1}{2}}\cdot {\frac {1}{4}}=0.4583333\ldots$

В двоичном формате Z ( B ) = 0,011 10101010101...

$L(B)=\left\lceil \log _{2}{\frac {1}{\frac {1}{4}}}\right\rceil +1=\mathbf {3}$

код ( B ) - 011

Для С

${\bar {F}}(C)=p(A)+p(B)+{\frac {1}{2}}p(C)={\frac {1}{3}}+{\frac {1}{4}}+{\frac {1}{2}}\cdot {\frac {1}{6}}=0.66666\ldots$

В двоичном формате Z ( C ) = 0. 1010 10101010...

$L(C)=\left\lceil \log _{2}{\frac {1}{\frac {1}{6}}}\right\rceil +1=\mathbf {4}$

код ( C ) - 1010

Для Д

${\bar {F}}(D)=p(A)+p(B)+p(C)+{\frac {1}{2}}p(D)={\frac {1}{3}}+{\frac {1}{4}}+{\frac {1}{6}}+{\frac {1}{2}}\cdot {\frac {1}{4}}=0.875$

В двоичном формате Z(D) = 0,111 .

$L(D)=\left\lceil \log _{2}{\frac {1}{\frac {1}{4}}}\right\rceil +1=\mathbf {3}$

код ( D ) 111

Алгоритмический анализ

Префиксный код

Кодирование Шеннона-Фано-Элиаса создает двоичный префиксный код , позволяющий осуществлять прямое декодирование.

Пусть bcode( x ) будет рациональным числом, образованным добавлением десятичной точки перед двоичным кодом. Например, если code( C ) = 1010, то bcode( C ) = 0,1010. Для всех x , если не существует y такого, что

$\operatorname {bcode} (x)\leq \operatorname {bcode} (y)<\operatorname {bcode} (x)+2^{-L(x)}$

тогда все коды образуют префиксный код.

Сравнивая F с CDF X . , это свойство можно продемонстрировать графически для кодирования Шеннона-Фано-Элиаса

По определению L отсюда следует, что

$2^{-L(x)}\leq {\frac {1}{2}}p(x)$

А поскольку биты после L ( y ) отсекаются от F ( y ) для формирования кода ( y ), отсюда следует, что

${\bar {F}}(y)-\operatorname {bcode} (y)\leq 2^{-L(y)}$

таким образом, bcode( y ) должен быть не меньше CDF( x ).

Таким образом, приведенный выше график показывает, что $\operatorname {bcode} (y)-\operatorname {bcode} (x)>p(x)\geq 2^{-L(x)}$, поэтому свойство префикса сохраняется.

Длина кода

Средняя длина кода $LC(X)=\sum _{x\in X}p(x)L(x)=\sum _{x\in X}p(x)\left(\left\lceil \log _{2}{\frac {1}{p(x)}}\right\rceil +1\right)$.
Таким образом, для H ( X ) энтропия случайной величины X ,

$H(X)+1\leq LC(X)<H(X)+2$

Шеннон Фано Элиас кодирует от 1 до 2 дополнительных битов на символ из X , чем энтропия, поэтому на практике код не используется.

См. также

• Кодирование Шеннона – Фано