Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
Согласно закону больших чисел, если кодируется очень длинная последовательность букв источника с помощью описанной выше процедуры кодирования, то число кодовых букв на одну букву источника будет с большой вероятностью близко к п.
До того как изучить вопрос о том, на сколько мало может быть п, рассмотрим некоторые ограничения на неравномерные коды, которые иллюстрируются рис. 3.2.1.
Заметим, что код I имеет неудачное свойство, состоящее в том, что буквы aL и а2 кодируются в одно и то же кодовое слово 0. Таким образом, это кодовое слово не может быть однозначно декодировано в букву источника, которая привела к этому слову. Так как такие коды не могут представлять буквы источника, они будут исключены из дальнейшего рассмотрения.
60
Буквы Код Код Код Код
источни 1 11 III IV
ка
«1 0,5 0 0 0 0
0,25 0 1 10 01
а3 0,125 1 00 но он
^4 0,125 10 11 111 0111
Рис. 3.2.1.
Код II на рис. 3.2.1 обладает тем же самым недостатком что и код
I, хотя и выраженным более тонким образом. Если источник порождает последовательность a1а1, то она будет закодирована в 00, что совпадает с кодовым словом для а3. Это не вызовет затруднения при декодировании, если между последовательными кодовыми словами имеется какой-то интервал или разделение. Однако если такой интервал допустим, то он должен быть рассмотрен как отдельный символ s кодового алфавита и кодовые слова в коде II должны быть Os, Is, 00s и 11s. Вводя обозначение для интервала (для ясности), когда это требуется, можно рассматривать такие коды просто как частные случаи кодов без интервала. По этой причине в дальнейшем такие коды не будут рассматриваться отдельно.
Как было отмечено, коды I и И из рис. 3.2.1 не могут быть использованы для представления источника, так как они не являются однозначно декодируемыми. Это приводит [к следующему определению. Код является однозначно декодируемым; если последовательности кодовых букв, соответствующие различным последовательностям источника конечной длины, являются различными.
Приведенное выше определение непосредственно не дает какого-либо способа определить, является ли некоторый код однозначно декодируемым или нет*'. Однако нас будет главным образом интересовать частный класс кодов, которые удовлетворяют условию, известному под названием «свойство префикса», легко показывается, что эти коды однозначно декодируемы.
Для того чтобы определить свойство префикса, допустим, что k-e
кодовое слово в коде представляется как xh = (xft l........*ь,пь)> гДе
Xk,i ¦¦¦> xh, nk —отдельные кодовые буквы, составляющие кодовое слово. Любая последовательность, составленная из начальной части хь, т. е. xk l, ..., xh> i для некоторого i nh, называется префиксом xk. Код, обладающий свойством префикса, определяется как код, в котором никакое кодовое слово не является префиксом никакого другого кодового слова.
*> Сардинас и Паттерсон (1953) придумали критерий однозначной декодируемое™. Простое изложение и доказательство этого критерия см. в задаче 3.14.
61
На рис. 3.2.1. можно заметить, что код I не обладает свойством префикса, так как 1, кодовое слово для а3, является префиксом 10, кодового слова для а4. Аналогично, если внимательно просмотреть определение префикса, то можно заметить, что 0, кодовое слово для aL, является префиксом 0, кодового слова для а2. Иными словами, любой код, два или более кодовых слова которого совпадают, не являются кодом, обладающим свойством префикса. Читателю предлагается проверить, что коды II и IV на рис. 3.2.1 не обладают свойством префикса, а код III обладает.
Для того чтобы декодировать последовательность кодовых слов из кода, обладающего свойством префикса, следует просто начать с начала последовательности и декодировать одно слово сразу. Когда дойдем до конца кодового слова, мы будем знать, что это конец, так как это кодовое слово не является префиксом какого-либо другого кодового слова. Таким образом, можно однозначно декодировать любую последовательность кодовых букв, соответствующую последовательности букв источника и, тем самым доказано, что любой код, удовлетворяющий свойству префикса, является однозначно декодируемым кодом. Так, например, последовательность источника кодируется
кодом III рис. 3.2.1 в 0М1100. Так как первая буква в кодовой последовательности есть 0 и она соответствует ах и не является начальным отрезком любой другой последовательности, то декодируется а± и остается кодовая последовательность 111100. Как 1, так 11 не соответствуют никакому кодовому слову, а 111 соответствует и декодируется в av после чего остается 100. Далее 10 декодируется в а2 остается только 0, который декодируется в ах.
Не любой однозначно декодируемый код обладает свойством префикса. Чтобы заметить это, рассмотрим код IV на рис. 3.2.1. В нем каждое кодовое слово является префиксом каждого более длинного кодового слова. Вместе с тем единственность декодирования является тривиальной, так как символ 0 всегда означает начало нового кодового слова. Коды, обладающие свойством префикса, отличаются, однако, от других однозначно декодируемых кодов тем, что конец кодового слова всегда может быть опознан, так что декодирование может быть выполнено без задержки наблюдаемой последовательности кодовых слов. По этой причине коды, обладающие свойством префикса, называются иногда мгновенными кодами.
