Задание на курсовую работу > Общая постановка задачи Содержание пояснительной записки (стр. 5 из 6)

Таблица 4

	0.20	0.15	0.15	0.12	0.10	0.10	0.08	0.06	0.04

Таблица 5

		1	2	3	4	5	6	7	8	Код.
	0.20									11
	0.15									001
	0.15									011
	0.12									010
	0.10									101
	0.10									100
	0.08									0001
	0.06									00001
	0.04									00000

В рисунке табл. 5 приведены все объединения, указанные в алгоритме Хаффмана. Нетрудно убедиться, что «дерево», изображенное на рис. 3, получено простым поворотом на

рисунка табл. 5. Рассмотрим движение по ветвям дерева от корня к листьям. Договоримся, что при каждом повороте направо будем записывать «0», а при повороте налево - «1».

Рис. 3. Схема реализации алгоритма Хафманна

При движении от корня к листу

мы дважды «повернем» направо, поэтому такому символу припишем кодовое слово -11. При движении к листу мы один раз повернем направо, затем налево и потом снова направо. Это дает кодовое слово – 101. Процедуру определения кодовых слов без труда можно продолжить.

Дерево Хаффмана в стандартном виде представлено на рис. 4. На нем каждому повороту направо или налево предыдущей схемы поставлены в соответствие стрелочки

и .

Рис. 4. Дерево Хаффмана для рассматриваемого примера

2.5. ЗАМЕЧАНИЯ ОТНОСИТЕЛЬНО АЛФАВИТА И ХАРАКТЕРИСТИК ОБОБЩЕННОГО ИСТОЧНИКА СООБЩЕНИЙ

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

Согласно изложенному в п.2.4., мощность нового алфавита равна двум (либо «0», либо «1»). А вот вероятности появления этих символов Вам предстоит вычислить. Как решить эту задачу?

Известны вероятности появления сообщений исходного алфавита, и Вы уже построили код Шеннона- Фано или Хаффмана. Согласно последнему можно рассчитать частоту появления «1» (или «0») в каждом кодовом слове. Известна и вероятность появления этого кодового слова. Так, в примере, рассмотренном выше, частота появления «1» при генерации

– , а вероятность появления - . Тогда вклад в вероятность появления «1» равен . Полная вероятность появления «1» в последовательности сообщений обобщенного источника может быть определена по формуле . Аналогично рассчитывается вероятность появления «0». Отличие полученных величин от характеризует степень отклонения кода от оптимального. Именно здесь кроется причина различия скорости передачи информации и пропускной способности канала при «оптимальном» кодировании.

2.6. Дискретные каналы связи

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

Неотъемлемым свойством любого реального канала связи является наличие в нем источников помех, шумов, искажений. В феноменологической модели канала связи воздействие шумов и помех на сигнал не детализируется, а лишь указывается вероятность того, что сигнал будет искажен на столько, что на приемном конце канала он будет воспринят как некоторый другой сигнал из возможного списка (из алфавита источника). Будем говорить, что дискретный канал – канал без памяти, если каждое сообщение в любой последовательности сообщений искажается в канале независимо от того, какие сообщения передавались ранее, до него. Говорят при этом, что межсимвольной интерференцией можно пренебречь.

Говорят, что дискретный канал без памяти задан, если заданы все условные вероятности

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

Остановимся на одном моменте. Должны ли алфавиты входного и выходного устройства канала совпадать? Оказывается – нет! Например, в канале со стиранием выходной алфавит содержит, кроме символов входного алфавита, специальный символ стирания, который появляется на выходе дискретного канала, когда демодулятор не может с уверенностью принять решение в пользу одного из входных символов.

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

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

Будем говорить, что канал зашумлен слабо, если величина

близка к единице. Другими словами, правильное распознавание ( было передано, и принимаемый сигнал был воспринят как ) является практически достоверным событием. Если величина отличается от единицы значимо, то канал будем называть сильно зашумленным.

Если входной и выходной алфавиты совпадают и при ошибке в приеме вероятности появления любых ошибочных символов одинаковы, т.е.

(5)

то канал называют симметричным. Если, кроме того, вероятность ошибки не зависит от времени, то говорят о стационарном симметричном канале. Наиболее просто выглядит модель стационарного симметричного канала без памяти, в котором ошибки при приеме различных символов являются статистически независимыми. Для такого канала вероятность получения

ошибок при передаче символов подчиняется биномиальному закону: