Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
*> В более общем случае буквы дискретного источника могут выбираться из бесконечного счетного алфавита аг, а2, ... Мы будем различать случай конечного алфавита от случая счетного алфавита, указывая объем алфавита в первом случае.
54
связанные с кодированием источника, избегая математических трудностей, к которым приводит учет статистической зависимости.
Во многих практических кодах для источника, таких, как код Морзе и стенография, короткие кодовые слова приписываются наиболее часто возникающим буквам или сообщениям, а длинные кодовые слова—более редким буквам или сообщениям. Например, в коде Морзе часто встречающаяся буква е имеет кодовое слово «•», а редкая буква q имеет кодовое слово «•-----». Такие коды, в которых различные кодо-
вые слова содержат различное число кодовых символов, называются неравномерными кодами. Если источник производит буквы с фиксированной во времени скоростью и если необходимо передавать закодированные символы с фиксированной во времени скоростью, то неравномерный код приводит к проблеме ожидающей очереди. Когда источник выдает редкую букву, производится длинное кодовое слово и ожидающая очередь увеличивается. Наоборот, часто встречающиеся буквы порождают короткие кодовые слова, сокращая ожидающую очередь.
С практической точки зрения обычно желательно избежать эти проблемы, связанные с ожидающей очередью, с помощью кода с фиксированной длиной, т. е. кода, в котором каждое кодовое слово имеет одну и ту же длину. Число кодовых слов в таких практических кодах, в общем, довольно мало (так, например, 32 слова для телетайпа). Рассмотрением кодов с фиксированной длиной мы начнем следующий параграф, однако наибольший интерес для нас будут представлять коды очень большой длины. Такие коды имеют небольшую практическую значимость, но позволяют ясно обнаружить некоторые более глубокие свойства собственной информации и энтропии.
3.1. коды С ФИКСИРОВАННОЙ длинои
Обозначим через uL — (иъ иг, ..., uL) последовательность L последовательных букв дискретного источника. Каждая буква выбирается из алфавита аъ ..., а% и, таким образом, имеются KL различных последовательностей длины L, которые могут появляться на выходе источника. Предположим, что нужно закодировать эти последовательности в слова кода с фиксированной длиной. Если кодовый алфавит состоит из D символов и если длина каждого кодового слова равна N, то существуют DN различных последовательностей кодовых букв, которые могут быть рассмотрены как кодовые слова. Следовательно, если нужно сопоставить различные кодовые слова разным последовательностям источника (это необходимо сделать, если требуется восстановить каждую возможную последовательность источника по ее кодовому слову), то получаем
A^Jog
L log D v '
Таким образом, для кодов с фиксированной длиной всегда, когда требуется декодировать последовательность источника по кодовому слову, необходимо иметь по меньшей мере log К /log N кодовых букв на одну букву источника. Так, например, в случае телетайпа источник
55
имеет алфавит из К — 32 символов (26 английских букв и 6 специальных символов). Кодируя одну букву источника (L = 1) в буквы двоичного кода (D = 2), нужно иметь N = 5 двоичных символов на один символ источника для того, чтобы удовлетворить условию (3.1.1).
Если мы хотим использовать меньше чем log KIlog D кодовых букв на один символ источника, то, очевидно, нужно ослабить требование того, чтобы всегда было возможно декодировать последовательность источника по кодовой последовательности. Отсюда следует, что мы должны приписать кодовые слова только некоторому подмножеству последовательностей источника длины L. Далее будет показано, что для достаточно больших L вероятность получения последовательности источника, которая не соответствует никакому слову, может быть сделана произвольно малой и в то же самое время число кодовых букв на один символ источника может быть сделано сколь угодно близким к H(U)llogD.
Для источника без памяти вероятность данной последовательности ul = («1, •••, Ul) из L букв источника равна произведению вероятностей отдельных букв источника
L
Рг(щ.) = П Р(щ).
1 = 1
В этом равенстве каждая буква их выбирается из алфавита ах..........ак
с вероятностью Р (и{). Так, например, если источник имеет алфавит из двух букв аг и а2 с Р (%) = 0,7 и Р (а2) = 0,3, то вероятность последовательности и3 = (иъ и2, и3) при их — а2, и2 = аъ и3 = ах равна
0,3x0,7x0,7 = 0,147. Собственная информация последовательности Ui имеет вид
L
I (ul) = — log Pr (uL) -- — log П p (щ) ¦=
1 = 1
¦ = 2 -logP(ut)= 2 I(Ui). (3.1.2)
i=i i=i
