Теория информации

Теорема 4. Существуют такие способы кодирования для достаточно длинного сообщения x 1 , x 2 , … , что средняя длина кодового слова может быть сделана сколь угодно близкой к D H log . Доказательство. Возьмем произвольное целое N>1 и разобьем последовательность x 1 , x 2 , … , на группы N случайных величин. Каждую такую группу будем рассматривать как одну случайную величину Y=( x 1 , x 2 , … ,x N ) и применим к ней теорему (3): 1 log   D H k Y Y , где H Y =NH X ,  Y k _ средняя длина слова, передающего сообщение Y=( x 1 , x 2 , … ,x N ) . Очевидно, что _ _ kN k Y   , тогда получим: ND H k X 1 log   Увеличивая N , Величину 1/N можно сделать сколь угодно малой, что доказывает теорему. Например 1.19 , продолжая пример 1.18 : Определение. Дискретный источник сообщений, который описывается моделью с независимыми символами сообщений, называется дискретным источником без памяти . Для любого дискретного источника без памяти X с конечным алфавитом и энтропией H ( X ) существует двоичный код, в котором средняя длина кодового слова n удовлетворяет неравенству 1 ) ( ) (   X Hn XH , т.е. средняя длина кодового слова не может быть меньше энтропии источника сообщений. Кроме того, доказано, что для блока длины L