2.1.7. Примеры решения задач

1. =

10 8

Задача поставлена некорректно, так как в десятичной системе коэффициент быть не может.

2. 

5 6 6₈

3. 

	1		2		3
	–		–		–

Схема решения:

	59	2
	-58	29	2
	1	-28	14	2
		1	-14	7	2
			0	-6	3	2
				1	-2	1
					1

1).2).

3).

4. А=10, В=11.

5. 

	1		2
	–		–

Схема:

6. Задача поставлена некорректно, так как в троичной системе коэффициентабыть не может.

7. 

	1		2
	–		–

Схема:

1). По схеме Горнера:

2).

8. 	1		2		3
   	–		–		–

   Схема:

1).

2).– по схеме Горнера

3).

2.1.8. Пример задания по контрольной работе – часть 1

1. 

2. 

3. 

4. 

5. 

2.2. Контрольная работа – часть 2

В контрольную работу включены задачи из следующих разделов теории информации и кодирования:

1. измерение информации (аддитивная мера Хартли);

2. избыточность сообщений (абсолютная и информационная);

3. эффективное кодирование по методам Шеннона-Фано и Хаффмена;

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

Краткие теоретические сведения

Информация по мере Хартли приведена в разделе 1.2 настоящих методических указаний (1.4).

2.2.1. Избыточность сообщений

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

Абсолютная величина избыточности определяется выражением:

, (2.1)

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

Относительная избыточность, называемая информационной, определяется выражением:

(2.2)

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

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

(2.3)

где – объем используемого алфавита;.

2.2.2. Теоретические основы эффективного кодирования

Пусть требуется передать достаточно длинное сообщение, составленное из ансамбля знаков ,, где– объем первичного алфавита:.

При кодировании каждому знаку первичного алфавита ставится в соответствие своя кодовая комбинация во вторичном алфавите, содержащем символов. Обозначим черездлину кодовой комбинации, соответствующей знаку, а через– среднюю длину кодовой комбинации при выбранном способе кодирования. Тогда:

(2.4)

При эффективном кодировании стремятся к тому, чтобы . Это значит, что при определенном объеме передаваемой информации необходимо увеличивать ее количество на каждый символ сигнала, т.е. повышать, как обычно говорят, «плотность» упаковки информации.

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

(2.5)

Справедливость теоремы Шеннона можно видеть из следующих рассуждений.

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

Дополнительное сокращение времени, затрачиваемого на передачу сообщения, можно достигнуть с помощью специального кода, позволяющего вести передачу без промежутков между кодовыми комбинациями. Чтобы на приемной стороне можно было отличить одну комбинацию от другой, т.е. чтобы код был разделимым (однозначно декодируемым), он должен строиться так, чтобы ни одна более длинная кодовая комбинация не являлась продолжением более короткой. Например, при указанном кодировании нельзя применять комбинации 110 и 11010, так как вторая комбинация получена из первой путем добавления 10.