Перейдем к определению кодирования

Рассмотрим множество N, элементами которого являются

все возможные двоичные числа, разрядностью n, всего 2ⁿ

элементов. На Рис. 1 представлены элементы множества N для n = 5, расположенные в порядке возрастания.

Р ис.1. Элементы множества N для n = 5, расположенные в порядке возрастания

Определимна N подмножества, обозначим их M _k, L_s.

Элементами М _К являются все элементы множества N, содержащие k единиц (0 ≤ k ≤ n). Элементами L_s являются все элементы множества N, сумма номеров позиций единиц котор ых равна S (0 ≤ S≤ n(n+1)/2 ). На Рис. 1 показаны этиподмножества для n = 5.

Определим R_{k ,s}, как пересечение M _k, L_s.

Обозначим r(n,k,s) количество элементовмножества R_{k ,s.}

Поставим в соответствие каждому элементу множества R_{k ,s} номер b(n,k,s), причем 0 ≤ b(n,k,s) ≤ r(n,k,s) – 1.

Определим кодовое слово w соответствующее n -блоку,

как упорядоченную тройку двоичных наборов (k, s, b(n,k,s)).

Длина кодового слова (в битах) будет равна:

L=]log ₂ (n+1)[+ ]log ₂ (n(n+1)/2+1 [+]log ₂ r(n,k,s)[ (4).

Код определим, как множество W элементами которого являются все кодовые слова w. И з построения следует, что W - префикс­ное м ножество, а, следовательно, между n -блоками и кодовыми сло­вами w существует взаимо однозначное соответствие.

Данное кодирование назовем кодированием тройками двоичных наборов (сокращенно К Т).

Теорема 1. КТ об лает свойством универсальности для бернуллиевских источников.

Доказательство. Обозначим η(n,k,s) вероятность появления n -блока содержащего k единиц и при этом имеющего сумму номе­ров позиций единиц равную S.

η(n,k,s)=r(n,k,s)p.

Запишем выражение для средней длины кодового слова - n_ср.

n s_max(k)

n_ср= ]log₂ (n+1)[+]log₂ (n(n+1)/2+1[+∑∑ η(n,k,s)]log₂ r(n,k,s)[

K=0 s=s_min(k) (5)

S _min(k) = k(k+1)/2;

S _max(k) =kn - k(k+1)/2 (6)

Далее:

n_ср ≤ log₂ (n+1)+ log₂ (n(n+1)/2+1)+∑∑ η(n,k,s)log₂ r(n,k,s)+2 (7)

Дата добавления: 2014-01-13