менится на 0; во втором сохранится 1, так как в третьем разряде двоичного числа записан 0. В третьем сохранится 0, так как в четвертом разряде двоичного кода 0. В четвертом 0 изменится на 1, в пятом – 1 на 0 из-за того, что в пятом и шестом разряде двоичного кода стоит 1. Шестой разряд останется без изменения, так как подразумевается, что
левее шестого разряда двоичного числа стоит 0. |
|
СибАДИ |
|
На основании рассмотренных выше примеров значение разряда в |
|
коде Грея можно получ ть из выражения |
|
bi ai 1 ai. |
(2.3.9) |
В качестве пр мера рассмотрим преобразование двоичного числа |
|
1011001 в код Грея: |
|
1011001 a7a6a5a4a3a2a1 b7b6b5b4b3b2b1 a7 (a7 |
a6 )(a6 a5) |
(a5 a4)(a4 a3)(a3 a2 )(a2 a1) 1(1 0)(0 1)(1 1)(1 0)(0 0)(0 1) 1110101.
2.3.4. Оптимальные коды
Оптимальные по длине коды относятся к неравномерным непомехозащищенным кодам. Оптимальным кодом считается код, имеющий минимальную среднюю длину кодового слова [6]
n |
|
L iP(xi ), |
(2.3.10) |
i 1 |
|
где μi – длина кодового слова, сопоставляемая |
сообщению xi ; |
P(xi ) – вероятность появления этого сообщения. |
|
Очевидно, что μi L зависят от того, каким образом осуществляются формирование кодовых слов и их сопоставление с сообщениями xi. Наиболее вероятные сообщения кодируются кодом меньшей длины, а менее вероятные – кодом большей длины. Тогда, учитывая, что по каналу связи чаще будут передаваться кодовые комбинации меньшей длины, получаем экономию во времени при передаче последовательности сообщений.
В оптимальном коде энтропия на символ должна быть максимальной, а это возможно в том случае, когда вероятности появления единиц и нулей P(1) и P(0) приблизительно одинаковы. Рассмотрим
46
алгоритмы составления оптимальных кодов, удовлетворяющих максимальной энтропии на символ, при допущении, что время передачи единицы и нуля одинаковы: t(1)=t(0).
Код Шеннона
СибАДИуть метода Шеннона применительно к двоичному кодированию состоит в следующем. Все сообщения выписываются в порядке убывания х вероятностей. Далее множество дискретных сообщений делится на две части так м образом, чтобы сумма вероятностей сообщений, включенных в первую часть, была приблизительно равна сумме вероятностей соо щений второй части. После этого первому слева (старшему) разряду кода каждого сообщения первой части присваивается значен е, равное нулю, а старшему разряду кода каждого сообщен я второй части присваивается значение, равное единице. На этом сч тается законченным кодирование первого сообщения x1. Затем остальные соо щен я x2 , x3,...,xn также делятся на две по возможности равновероятные подгруппы; одной из них присваивается значение 0, другой 1. На этом заканчивается кодирование второго сообщения x2 . Так продолжается до тех пор, пока не будут закодированы все сообщения.
Пример для кодирования 9 сообщений кодом Шеннона приведен в табл. 2.3.4.
После пятой разбивки кодирование можно приостановить, так как нет двух одинаковых кодовых комбинаций.
Подсчитаем среднее число нулей единиц и вероятности их появления.
Среднее число нулей
L(0) 0,35 0,15 0,13 0,18 0,18 0,16 0,15 0,08 0,02 1,4.
Среднее число единиц
L(1) 0,15 0,26 0,18 0,27 0,24 0,10 0,08 1,4.
47
СибАДИ |
Таблица 2.3.4 |
||||||||
|
|
Код рование сообщений кодом Шеннона |
|
|
|
|
|||
|
Вероятность |
|
Разбиение сообщений на подмножества |
|
|
|
|||
Сообщения |
появления |
x1,x2 0 |
x2,x3,x8 1 |
x3,x6,x8 0 |
|
x4,x7,x8 0 |
x5,x7 0 |
|
μi |
xi |
сообщений |
x3,…,x9 1 |
x4,…,x7, x9 0 |
x4, x5,x7, x9 1 |
|
x5, x6,x9 1 |
x6, x8,x9 1 |
|
|
|
P(xi) |
I |
II |
III |
|
IV |
V |
|
|
x1 |
0,35 |
0 |
|
|
|
|
|
|
1 |
x2 |
0,15 |
0 |
1 |
|
|
|
|
|
2 |
x3 |
0,13 |
1 |
1 |
0 |
|
|
|
|
3 |
x4 |
0,09 |
1 |
0 |
1 |
|
0 |
|
|
4 |
x5 |
0,09 |
1 |
0 |
1 |
|
1 |
0 |
|
5 |
x6 |
0,08 |
1 |
0 |
0 |
|
1 |
1 |
|
5 |
x7 |
0,05 |
1 |
0 |
1 |
|
0 |
0 |
|
5 |
x8 |
0,04 |
1 |
1 |
0 |
|
0 |
1 |
|
5 |
x9 |
0,02 |
1 |
0 |
1 |
|
1 |
1 |
|
5 |
48
Средняя длина кодового слова
|
|
L =0,35 +0,30 +0,39 +0,36 +0,45 +0,40 +0,25 +0,20 +0,10 |
=2,8. |
|
||||||||||||||
|
|
Тогда P(1) L(1)/ L 1,4/2,8 0,5; |
P(0) L(0)/ L 1,4/2,8 0,5. |
|||||||||||||||
|
|
Таким образом, получим код с максимальной энтропией на сим- |
||||||||||||||||
СибАДИ |
||||||||||||||||||
|
вол, но более короткие комбинации являются началом более длин- |
|||||||||||||||||
|
ных, что требует передачи разделительных пауз между кодовыми со- |
|||||||||||||||||
|
общен ями, |
а следовательно, приводит к снижению эффективности. |
||||||||||||||||
|
От этого недостатка свободен метод Шеннона–Фано. |
|
|
|
|
|||||||||||||
|
|
|
|
|
|
|
|
Код Шеннона–Фано |
|
|
|
|
|
|||||
|
|
Для построен я этого кода все сообщения xi |
выписываются в по- |
|||||||||||||||
|
рядке убыван я х вероятностей (табл. 2.3.5). |
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
Построение кода Шеннона–Фано |
Таблица 2.3.5 |
|||||||||||
|
xi |
|
P(xi) |
|
Раз иение соо щений на подгруппы |
|
Код |
μi |
|
Lxi |
|
|||||||
|
x1 |
|
0,35 |
|
1 |
|
1 |
|
|
|
|
|
|
11 |
2 |
|
0,70 |
|
|
x2 |
|
0,15 |
|
1 |
|
|
|
|
|
|
|
|
10 |
2 |
|
0,30 |
|
|
0 |
|
|
|
|
|
|
|
||||||||||
|
x3 |
|
0,13 |
|
|
|
|
|
|
|
|
|
|
011 |
3 |
|
0,39 |
|
|
0 |
|
1 |
|
1 |
|
|
|
|
|
||||||||
|
x4 |
|
0,09 |
|
0 |
|
1 |
|
|
|
|
|
|
010 |
3 |
|
0,27 |
|
|
0 |
|
|
|
|
|
||||||||||||
|
x5 |
|
0,09 |
|
0 |
|
|
|
|
|
|
|
|
0011 |
4 |
|
0,36 |
|
|
0 |
|
1 |
1 |
|
|
|
|
||||||||||
|
x6 |
|
0,08 |
|
0 |
|
0 |
|
1 |
|
|
|
|
0010 |
4 |
|
0,32 |
|
|
0 |
|
|
|
|
|||||||||||||
|
x7 |
|
0,05 |
|
0 |
|
0 |
|
|
|
|
|
|
0001 |
4 |
|
0,20 |
|
|
0 |
1 |
|
|
|
|
||||||||||||
|
x8 |
|
0,04 |
|
0 |
|
0 |
|
0 |
|
|
|
|
00001 |
5 |
|
0,20 |
|
|
0 |
|
1 |
|
|
|||||||||||||
|
x9 |
|
0,02 |
|
0 |
|
0 |
|
0 |
|
|
|
|
00000 |
5 |
|
0,10 |
|
|
0 |
|
0 |
|
|
|||||||||||||
Записанные так сообщения затем разбивают на две по возможности равновероятные подгруппы. Всем сообщениям первой подгруппы присваивают цифру 1 в качестве первого кодового символа, а сообщениям второй подгруппы – цифру 0. Аналогичное деление на подгруппы продолжается до тех пор, пока в каждую подгруппу не попадает по одному сообщению.
49
Найденный код весьма близок к оптимальному. Энтропия сообщений
9
H(X) P(xi )logP(xi ) (0,35log0,35 0,15log0,15 0,13log0,13
i 1
0,09log0,09 0,09log0,09 0,08log0,08 0,05log0,05 0,04log0,04
Сиб0,02log0,02) 2,75 битА. ДИ
сообщение редняя дл на кодового слова
9
L LX i 0,70 0,30 0,39 0,27 0,36 0,32 0,20 0,20 0,10 2,84.
i 1
Среднее ч сло нулей
L(0) 0,15 0,13 0,18 0,18 0,24 0,15 0,16 0,10 1,29.
Среднее число единиц
L(1) 0,70 0,15 0,26 0,09 0,18 0,08 0,05 0,04 1,55.
Вероятность появления нулей
Р(0) L(0) 1,29 0,455.
L 2,84
Вероятность появления единиц
Р(1) L(1) 1,55 0,545.
L 2,84
Таким образом, получен код, близкий к оптимальному.
Код Хаффмана
Для получения кода Хаффмана все сообщения выписывают в порядке убывания вероятностей. Две наименьшие вероятности объединяют скобкой (табл. 2.3.6), одной из них присваивают символ 1, а
50