6.3.2. Свойство независимости в древовидном коде

На следующем этапе вывода верхней границы для среднего числа операций при декодировании используется метод случайного кодирования и проводится усреднение (6.15) по ансамблю кодов, шумам в канале и информационным последовательностям. Чтобы можно было применить метод случайного кодирования, потребуется ансамбль древовидных кодов, обладающий следующими свойствами:

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

II. Символы канала каждого кодового слова должны быть статистически независимыми. А именно для любой кодовой последрвательности длины должно выполняться равенство

Приведенная несколько ниже лемма, принадлежащая Галлагеру [11], дает метод построения ансамбля древовидных кодов, обладающих указанными выше свойствами.

Пусть а — некоторое целое число; рассмотрим двоичный сверточный кодер с входами и выходами. Пусть последовательности символов соответственно на входах и выходах этого кодера. Согласно формуле (5.14), входные и выходные символы сверточного кодера связаны между собой следующим соотношением:

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

двоичными информационными символами, и, следовательно, рассматриваемый код имеет скорость передачи

Предположим, что параметры а также соответствие между двоичными последовательностями длины а и символами канала заданы. Рассмотрим ансамбль кодов, который получается в том случае, если все коэффициенты в формуле (6.16) и все компоненты последовательности являются независимыми двоичными случайными величинами, принимающими значения 0 и 1 с равными вероятностями.

Лемма 6.1. (Галлагер.) В рассмотренном выше ансамбле кодов кодовая последовательность соответствующая произвольной, но заданной информационной последовательности, является случайной последовательностью, символы которой являются независимыми случайными величинами, принимающими значение с вероятностью Если информационные последовательности совпадают лишь в первых блоках, то соответствующие им кодовые последовательности также совпадают в первых блоках, а символы остальных блоков этих кодовых последовательностей являются статистически независимыми.

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

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

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

Выше в целях упрощения предполагалось, что кодовое ограничение имеет бесконечно большие значения. Поскольку кодовое ограничение сверточных кодов, порождаемых реальными кодерами, является конечным, то из-за этого, как описывается в следующем разделе, могут возникать необнаруживаемые ошибки. Однако при определении среднего числа операций предположение о бесконечности кодового ограничения позволяет упростить анализ, проводимый методом случайного кодирования, и, как будет показано ниже, получить для алгоритма Фано верхнюю границу для среднего числа операций, не зависящую от длины кодового ограничения . Это показывает целесообразность предположения о бесконечности кодового ограничения при анализе среднего числа операций.