2. Случайные образующие элементы

Анализ, проведенный в гл. 3, был основан на пред положении, что рассматривается конечная древовидная совокупность, в которой каждая ветвь дерева выбрана независимым образом при помощи случайного выбора в совокупности всех двоичных последовательностей длины Мы покажем теперь, что этот анализ переносится без изменений на ансамбль бесконечных древовидных групповых кодов получающийся при случайном выборе последовательности

Так как процедура декодирования не зависит (если не сделано ошибок ранее) от того, какой именно символ должен быть декодирован, мы можем без потери общности рассмотреть случай Структура совокупности усеченных сообщений идентична тогда структуре, рассмотренной в гл. 3, хотя, конечно, сообщения имеют в случае группового кода меньшее число

степеней свободы. Приемник должен будет при заданном в полученном сигнале у определять, возник ли этот сигнал из переданного сигнала принадлежащего подмножеству 5° (сигналов, для которых или же подмножеству (сигналов, для которых Снова в силу свойств групповой симметрии, которыми обладает мы можем без потери общности считать, что х тождественно равно нулю и, следовательно, что Таким образом, в дальнейшем анализе мы можем считать, что множество является неправильным.

Единственное требование, которому должно удовлетворять для того, чтобы были приложимы результаты гл. 3, состоит в том, чтобы в статистическом ансамбле последовательностей для каждой последовательности из выполнялось неравенство

То, что это верно для ансамбля случайных порождающих элементов следует непосредственно из рассмотрения рис. 13. Предположим, что мы хотим найти такое, чтобы некоторая последовательность х, первый символ которой равен единице , давала заданное значение Пусть первые символов совпадают с первыми символов Если то пусть вторая группа из символов совпадает со второй группой из символов если же то пусть вторая группа из символов совпадает с суммой (по модулю 2) второй группы из символов и первых символов Продолжая таким образом, мы увидим, что следующие

символов всегда определяются однозначно по х и предшествующим символам

Предположим, например, чтох . Тогда Запишем прежде всего (такая форма записи встретится ниже) в соответствующие графы и прочерки, обозначающие переносы. Значения, которые должны стоять в графах, оставшихся незаполненными, определяются однозначно в порядке, указанном верхними индексами:

Итак, мы видим, что при заданном и произвольном во всех отношениях (за исключением того, что существует взаимно однозначное соответствие между возможными значениями Другими словами, в ансамбле равновероятных образующих элементов любое заданное из с равными вероятностями оказывается любым набором из двоичных символов. Как и в случае блоковых групповых кодов, рассмотренном в гл. 2, эта попарная статистическая независимость между и каждым достаточна для того, чтобы вывести соотношение для случайного древовидного группового кода , а следовательно, и иметь возможность применить этому случаю исследование, проведенное ранее для

До сих пор изучение этих двух величин проводилось независимо, и поэтому не было гарантии, что существуют порождающие элементы, для которых верны одновременно обе границы. Мы можем теперь воспользоваться соображениями Шеннона о положительных числах. Только доля всех возможных наборов порождающих элементов может дать вероятность ошибки, большую чем и по той же самой причине только доля может дать коды, для которых трудность вычисления больше, чем

Следовательно, по крайней мере, доля всех возможных наборов порождающих элементов даст коды, для которых их рабочие характеристики совместно ограничены сверху числами