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

существует двоичный префиксный код, в котором средняя длина кодового слова на один символ n удовлетворяет неравенству L XHn XH L L 1 ) ( ) (   , где ) ,..., , ( 1 ) ( 2 1 L L X XX H L XH  . Последнее неравенство позволяет утверждать, что существуют такие способы кодирования для достаточно длинного сообщения, что средняя длина кодового слова может быть сделана сколь угодно близкой к величине H ( X ). Так как минимально достижимой длиной кодового слова на символ является величина, равная значению энтропии H , то избыточность кода можно определить по формуле: n H n H n   1 . Пример 1.20. Сообщения составляются из букв алфавита: а, b, с, d. Вероятности появления букв алфавита в текстах равны соответственно: 0,2; 0,3; 0,4; 0,1. Найдите избыточность сообщений, составленных из букв данного алфавита. Решение. Для алфавита из четырех букв максимальная энтропия составит: H max = log m = log 4 = 2. Средняя энтропия на символ сообщения: бит 84,1 )1,0 log1,04,0 log4,03,0 log3,02,0 log2,0 ( p log p H m 1i i i          Тогда избыточность: D = 1 - H/H max = 1-1,84/2 = 0,08.