Код Шеннона-Фано

Алгоритм кодирования Шеннона-Фано заключается в следующем.

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

Этот ансамбль сообщений затем разбивается на две, по возможности, равновероятные группы. Всем сообщениям, входящим в первую группу (с большими вероятностями) в качестве первого кодового символа приписывают «1», а сообщениям второй группы в качестве первого кодового символа приписывают «0».

Далее первая группа делится снова на две, по возможности, равновероятные подгруппы. Всем сообщениям первых подгрупп в качестве второго кодового символа приписывается «1», а всем сообщениям вторых подгрупп в качестве второго кодового символа приписывается «0». Процесс деления на подгруппы и присвоения значений элементам кода продолжается до тех пор, пока в каждой из подгрупп не останется по одному сообщению. На этом процесс кодирования прекращается.

Рассмотрим пример.

Дискретный источник выдает сообщения из ансамбля {X_j}, где j = 1, 2, …, 10 с вероятностями, приведенными в таблице

Xj	X1	X2	X3	X4	X5	X6	X7	X8	X9	X10
P(xj)	0,25	0,12	0,10	0,06	0,03	0,02	0,05	0,12	0,17	0,08

Закодировать данные сообщения кодом Шеннона-Фано. Определить среднюю длину кодовой комбинации, количество информации, содержащееся в одном элементе кода, минимальную длину кодовой комбинации и избыточность кода. При определении минимальной длины кодовой комбинации следует воспользоваться приближенной формулой.

Решение.

Таблица, иллюстрирующая процесс построение кода

X1	0,25
X9	0,17
X2	0,12
X8	0,12
X3	0,10
X10	0,08
X4	0,06
X7	0,05
X5	0,03
X6	0,02

Определение энтропии источника

бит

Определение средней длины кодовой комбинации

элемента

Определение среднего количества информации, приходящейся на один элемент кода

бит/элемент

Определение минимальной средней длины кодовой комбинации

элемента

Определение избыточности кода

Дата добавления: 2015-07-01