Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике § 1.12. Неравномерное кодирование дискретных стационарных источниковВ этом параграфе мы получим теоремы кодирования дискретного стационарного источника при неравномерном кодировании. Вначале будут доказаны вспомогательные утверждения, относящиеся к побуквенному кодированию произвольных ансамблей сообщений. В дальнейшем они будут применены к ансамблю последовательностей сообщений. Пусть Обозначим: Теорема 1.12.1. Для любого кода со свойством однозначного декодирования
Доказательство. Из определения средней длины кодовых слов имеем
Рассмотрим разность
Воспользуемся неравенством (1.3.7). В результате получим, что
где последнее неравенство является следствием того, что код обладает свойством однозначного декодирования (см. теорему Замечание. Первое неравенство в (1.12.4), так же как и второе, обращается в точное равенство, если
Таким образом, если вероятности сообщений являются целыми отрицательными степенями числа О (1.12.5), то существует
т. е. равную нижней границе. Коды, для которых средняя длина кодовых слов (и соответственно скорость кодирования) равна наименьшему возможному значению, называются оптимальными. Этим рассуждением мы показали, что в случае, когда вероятности сообщений есть целые отрицательные степени числа Теорема 1.12.2. Существует D-ичный код со свойством однозначного декодирования, для которого
Доказательство. Пусть Очевидно,
Поскольку
то по теореме 1.11.1 существует дерево с концевыми вершинами порядков
Теорема доказана. Легко усмотреть в теоремах 1.11.1 и 1.11.2 обратную и прямую теоремы при побуквенном кодировании источника, выбирающего сообщения из ансамбля Пусть
Кроме того, существует код, для которого
Рассмотрим стационарный источник
При этом средняя скорость кодирования
Теорема 1.12.3 (обратная теорема кодирования). Для любого кода, кодирующего источник
Доказательство. Из определения средней скорости (1.12.14), из неравенства (1.12.11), справедливого для всех однозначно декодирующих кодов, и из теорем 1.5.1 и 1.5.2 следует, что для всех
Теорема доказана. Теорема 1.12.4 (прямая теорема кодирования). Пусть
Доказательство. Согласно теореме 1.5.2 для любого положительного найдется такое
Отсюда и из утверждения, связанного с неравенством (1.12.12), вытекает, что для произвольного целого однозначно декодируемый D-ичный код со средним колинеством символов на сообщение
и, следовательно, со скоростью кодирования
Полагая Из теорем 1.12.3 и 1.12.4 (обратной и прямой теорем кодирования дискретного стационарного источника при неравномерном кодировании) следует, что средняя скорость создания информации таким источником равна энтропии на сообщение
|
1 |
Оглавление
|