Файл: Бездудный, В. Г. Техника безопасности в шахтном строительстве.pdf

Пример 2. Построим оптимальный код сообщения, состоящего из восьми рав­ новероятных букв.

Так как вероятности данного ансамбля сообщений равны pi = р2 = ... = р8 =

с=2~3и порядок их расположения не играет роли,то расположим их так, как показано в табл. 11. Затем разбиваем данное множество сообщений на две равновероятные группы. Первой группе в качестве первого символа кодовых слов присваиваем О, а второй — 1. Во второй колонке табл. 11 записываем четыре нуля и четыре единицы. После чего разбиваем каждую из групп еще на две равновероятные подгруппы. За­ тем каждой первой подгруппе присваиваем 0, а второй — 1 и записываем в третью колонку табл. 11. Далее, каждую из четырех подгрупп разбиваем на две равновероят­ ные части и первой из них присваиваем 0, а второй — 1, Таким образом, в четзертой колонке табл. 11 появятся значения третьего символа кодовых слов.

Согласно основной теореме кодирования среднее число двоичных знаков на букву кода в достаточно длинной последовательности кодов равно энтропии источни-

ка сообщений. Для рассматриваемого примера энтропия источника сообщений

Н = log2 N = log2 8 = 3 бит/символ,

а среднее число двоичных знаков на букву кода

N

1 = 2 / (0Рг = 0 ,1 2 5 - 3 .8 = 3 ,

где 1ц) — длина i-й кодовой комбинации; рг — вероятность появления t-ro символа комбинации длиной в /(*>

' Таким образом, 11 L, т. е. код является оптимальным для данного ансамбля сообщении.

Вывод: для ансамблей равновероятных сообщений оптимальным является равномерный код.

74

Пример 3. Построим оптимальный код сообщения, в котором вероятности появ­

расположены таким образом, что вероятность появления каждой из них будет в два раза меньше вероятности появления последующей.

Таблица 12

Построение оптимального кода для сообщения, состоящего из неравновероятных букв

75

Построение ведем по общей методике. Оптимальный код для данных условий представлен в табл. 12. Среднее число двоичных знаков на букву кода

Некоторое расхождение в тысячных объясняется тем, что в данном коде. 2 р + 1,

i

т. е. данный ансамбль сообщений не является полной группой событий (2pi яз 0,984). Однако чем длиннее будет выбранный ряд значений Л,-, тем ближе 2р£ будет к 1, тем ближе будет значение L к энтропии источника сообщений.

Таким образом, Н фактически равно L, т. е. код является оптимальным для дан­ ного ансамбля сообщений.

Вывод: Число элементарных символов на букву сообщения с распре­

делением вероятностей появления букв по закону Р{ = (-^-) возрастает в порядке убывания вероятностей как натуральный ряд чисел (1, 2,

так как каждое кодовое слово заканчивается нулем, который отделя­ ет кодовые слова друг от друга.

Вывод. Кодовые слова одинаковой вероятности появления имеют равную длину.

На основании рассмотренных выше примеров, можно сказать, что оптимальными будут те коды, у которых средняя длина кодовой комбинации при заданном основании кода является минимальной и мало отличается от энтропии Источника сообщений. Коды с неравно­ мерным распределением символов, имеющие минимальную среднюю длину кодового слова, называются оптимальными неравномерными ко­ дами (ОНК).Максимально эффективными будут те ОНК, у которых

N

logs т 2 / ^ ( 0 = /ср = Я,

76

где т и N — символы соответственно вторичного и первичного алфа­ витов.

Для двоичных кодов

/(l) = — l0g2 pi = l0ga 1

Pi

Величина /,• точно равна Н, если pt == 2~"г, где п любое число. Если п не является целым числом для всех значений букв первичного алфавита, то /ср > Я и согласно основной теореме'кодирования при­ ближается к энтропии источника сообщений по мере укрупнения кодируемых блоков.

Эффективность ОНК оценивают при помощи коэффициента ста­ тистического сжатия

______ Iog2 N_____

Ясс =

ср

log2 т 2 Pih

i=1

который характеризует уменьшение количества двоичных знаков на символ сообщения при применении ОНК по сравнению с применением методов нестатистического кодирования, и коэффициента относитель­ ной эффективности

Чр

который показывает, насколько используется статистическая избы­ точность передаваемого сообщения.

Для наиболее общего случая неравновероятных и взаимонезависимых символов 1

ты статистического сжатия и относительной эффективности.

Оптимальный код для алфавитов с произвольным распределением вероятностей появления букв в текстах строится согласно общей методике. Перед построением ко­ да следует убедиться, что сумма вероятностей появления отдельных букв данного алфавита равна единице или близка к ней (в случае, если вероятности появления букв

1 Для случая неравновероятных и взаимозависимых символов

77

алфавита были получены в результате статистических исследований). Затем символы алфавита располагают в порядке убывания вероятностей и производят последова­ тельные разбиения на группы с возможно близкими суммарными значениями вероят­ ностей, присваивая каждый раз верхней группе символов значение 0, а нижней — 1.

Построение кода для условий, заданных в данном примере, представлено в табл. 12. Определяем Н, Ксс и К03‘-

В предыдущей теме был математически обоснован тот факт, что средняя длина кодового слова передаваемого сообщения по мере укрупнения кодируемых блоков будет уменьшаться, а код — прибли­ жаться к оптимальному. Попробуем теперь уяснить это.

Предположим, что кодируемое сообщение разделено на очень длинные группы символов. Тогда от символов предыдущего блока бу­ дут зависеть только несколько начальных символов последующего блока, и эта зависимость будет уменьшаться по мере удаления символа от начала блока.Чем больше символов в блоке, тем больше будет символов, которые не зависят от предыдущих блоков. Происходит декорреляция символов. Устраняется взаимозависимость. При этом растет энтропия сообщения, а с ростом энтропии увеличивается коэф-

н

фициент сжатия р = -щ— (см. тему 6), уменьшается избыточность

•“ max

D = 1 — р, код приближается к оптимальному. В случае декоррелированных сообщений значительноупрощается вычисление энтропии:

N

Н = — 2 p(Bi)log2p(Bj) бит/блок,

1"

Н= — -дг 2 Р iBi) log2 Р (Bi) бит]символ,

“/=1

где N — число символов в блоке.

78