Содержание

Задание 3

Вопрос. 3

Задача 1. 6

Задача 2. 8

Литература 10

Задание

1. Вопрос.

   Как оценить оптимальность и экономичность статистического кода Шеннона-Фано?

2. Задача 1

   Перевести десятичное число 10, представленное в циклическом коде Грея, в двоичный код. При этом изложить правила перевода и представить их в аналитическом виде.

3. Задача 2

   Определить максимальную скорось изменения выходного сигнала датчика, если его погрешность равна 1 %, диапазон изменения сигнала от 0 до 100 В, а пропускная способность ПНК на выходе данчика равна 100 бит/с.

Вопрос.

Как оценить оптимальность и экономичность статистического кода Шеннона-Фано?

Пусть имеется некоторый источник информации, с выхода которого поступают команды А₁ - А₄ с вероятностями:

p (А₁)= 0,500; p (А₂)= 0,250; p (А₃)=p (А₄)= 0,125.

Представление указанных команд для передачи, например, на объект управления в закодированном виде, должно быть выполнено с учетом вероятности их формирования.

Очевидно, что при кодировании необходимо, чтобы:

1. код был наиболее кратким;

2. кодовые комбинации были наиболее короткими для наиболее частых команд;

3. код должен обеспечивать разделение команд.

Если команды закодированы в виде А₁ ®0; А₂ ®1; А₃ ®10; А₄ ®11, то разделить их при последовательной и непрерывной передаче двоичных символов нельзя.

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

Любой код, используемый для передачи команд, подобно сообщениям, может быть оценен его экономичностью посредством коэфиициента сжатия:

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

,

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

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

Код, для которого средняя длина двоичных знаков (разрядов), приходящихся на символ сообщения, равна энтропии источника сообщения, будет являться оптимальным.

Для кодирования команд по методу Шеннона-Фано рекомендуется следующий порядок операций:

1. записать команды в последовательности убывания или возрастания вероятностей их появления;

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

3. для команд верхней подгруппы принят значение 0, а для команд нижней подгруппы 1;

4. для каждой из подгрупп команд выполнить пункты 2 и 3.

Пример 1. Для заданных в таблице 1. команд А₁ - А₄ построить код Шеннона-Фано, проверить его оптимальность и оценить экономичность.

Таблица 1

Команды Ai	p(Ai)	Операции разбиения			Число знаков	li p(Ai)	Равномерный код
		1	2	3	кода li
А1	0,500	0			1	0,500		00
А2	0,250	1	0		2	0,500		01
А3	0,125	1	1	0	3	0,375		10
А4	0,125	1	1	1	3	0,375		11

Решение. В соответствии с изложенными выше правилами производим построение кода и определяем его параметры исходя из данных в таблице.

Проверим оптимальнось полученного кода:

дв.ед./команда;

дв.ед./команда.

Полученный код является оптимальным, так как т.е. средняя длина двоичных знаков, используемых для представления команд равна энтропии источника.

Оценим экономичность кода:

В рассмотренном выше примере при разделении команд на группы сумарные вероятности делятся точно пополам. Однако более вероятно, что этого может не произойти, вследствии чего средняя длина двоичных знаков кода будет отличаться от энтропии источника на некоторую величину r, называемую иногда “разрядным излишком”.

Пример 2. Для данных в таблице 2 команд А₁ - А₄ построить код Шеннона-Фано, проверить его оптимальность.

Таблица 2

Команды Ai	p(Ai)	Операции разбиения			Число знаков	li p(Ai)	Равномерный код
		1	2	3	кода li
А1	0,2	0	0		2	0,4		000
А2	0,2	0	1		2	0,4		001
А3	0,2	1	0		2	0,4		010
А4	0,2	1	1	0	3	0,6		011
А5	0,2	1	1	1	3	0,6		100

Решение. В соответствии с изложенными правилами производим построение кода и определяем его параметры, заполняя графы в таблице 2.

Проверяем оптимальность кода:

дв.ед./команда;

дв.ед./команда.

Величина разрядного излишка при этом равна r=или 4,35% H₁(A).

Уменьшение разрядного излишка может быть достигнуто за счет группового кодирования сообщений (команд).

Пример3. Пусть имеются две команды А₁ и А₀ с вероятностями появления p(А₀)=0,89 и p(А₁)=0,11.

Таблица 3

Команды Ai	p(Ai)	Операции разбиения	Число знаков кода li	li p(Ai)
А0	0,89	0	1	0,89
А1	0,11	1	1	0,11

Построить код по методу Шеннона-Фано, проверить их оптимальность при кодировании по одной, по две и по три команды.

Решение. Проверка оптимальности кода при кодировании по одной команде

т.е. .

Проверка оптимальности кода при кодировании по две команды (таблица 4)

Таблица 4

Команды	p(Ai)	Операции разбиения			Число знаков		li p(Ai)
		1	2	3	кода li
	0,792	0			1	0,792
	0,098	1	0		2	0,196
	0,098	1	1	0	3	0,294
	0,012	1	1	1	3	0,036

;

разряд / две команды;

разряд / команда;

или , т.е. 32% теоретического значения энтропии оптимального кода.

Проверка оптимальности кода при кодировании по три команды (таблица 5).

Таблица 5

Команды	p(Ai)	Операции разбиения									Число знаков		li p(Ai)
		1			2		3		4	5	кода li
	0,705	0									1		0,705
	0,087	1			0		0				3		0,261
	0,087		1	0		1						3	0,261
	0,087	1			1		0				3		0,261
	0,011	1			1		1		0	0	5		0,055
	0,011	1			1		1		0	1	5		0,055
	0,011	1			1		1		0	1	5		0,055
	0,011	1			1		1		1	1	5		0,055

разряд / три команды;

разряд / команда;

или , т.е. 10 % теоретического значения энтропии оптимального кода.