IV. Объем вычислительных операций при декодировании и определение порогового значения скорости передачи

А. "Правильное“ и "неправильное“ подмножества кода Пусть произвольная последовательность информационных символов, и пусть где выбранное для передачи значение первого символа. Назовем множества

соответственно "правильным" и "неправильным" подмножествами последовательностей длины Так как при фиксированных последовательностях каждому элементу из соответствует один (и только один) элемент из то с подмножествами

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

Б. Объем вычислительных операций для прослеживания "неправильного“ подмножества

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

Если для фиксированной реализации процесса декодирования обозначить через число операций, связанное с декодированием в "неправильном" подмножестве, то

где число операций, необходимых для того, чтобы перейти от "неправильного" множества для длины к "неправильному" множеству для длины

Будем обозначать чертой сверху переход к средним значениям; тогда

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

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

Обратимся к двойной сумме в формуле (19). Выражение дает вероятность совместного наступления следующих двух событий:

1) начальный отрезок длины k "правильной“ последовательности не удовлетворяет критерию;

2) в последовательности, случайно выбранной из "неправильного" подмножества, начальный отрезок длины удовлетворяет критерию. Использование критерия при декодировании необходимо лишь в том случае, когда все последовательности, в том числе и истинная, оказываются отвергнутыми критерием при проверке по какой-нибудь длине Это и приводит к указанной оценке для

Так как нас интересует лишь экспоненциальная оценка поведения мы можем выбрать достаточно большую величину такую, что

Из неравенств (18) -(20) следует, что

В выражении

мы опускаем индекс Оценим эту вероятность сверху, используя обозначения приложения И и воспользовавшись неравенством Чернова (85) с двумя параметрами:

Пороговые величины были определены формулой (15), согласно которой

и

Здесь те величины, которые обозначались ранее через поэтому при Эти модифицированные обозначения мы используем только в этом разделе статьи для записи выражений (25) и (26) в более сжатой форме.

Подставляя оценку (22) в неравенство (21) и принимая во внимание равенства (23а) и (23б), мы получаем

где

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

Подставляя выражение (26) в неравенство (24), получаем

Для скоростей передачи сумма в неравенстве (27) не превосходит суммы бесконечной геометрической прогрессии; поэтому оценка сверху для этой суммы не зависит от длины кодовых ограничений Суммирование по X состоит в сложении одинаковых величин,

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

В. Каналы, симметричные по выходу

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

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

Рассмотрим случай, когда для декодирования выбран критерий, и предположим, что среднее число операций, требуемое для того, чтобы проследить "неправильную“ часть кода. Тогда

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

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

Для простоты положим, что

и

В силу условия (31) оценка (29) принимает вид

Среднее число операций равно

Подставив в формулу (33) оценки (28) и (32), получим

Воспользуемся указанным в разд. III методом нахождения величин в частности из формулы (14) следует, что

При — из оценок (78) получаем

для положим

Подставляя оценки в неравенство (34), мы получаем

Как показано в приложении III, функция

имеет единственный минимум в точке Так как , мы можем переписать оценку (37) в следующей форме:

где, по определению,

Сумма по в неравенстве (39) для скоростей не превосходит суммы бесконечной геометрической прогрессии и поэтому оценивается сверху величиной, не зависящей от длины кодовых ограничений При суммировании по индексу число слагаемых пропорционально Это следует из того, что наибольшее значение равно модулю логарифма вероятности ошибки при скорости передачи [см. соотношение (51)]. Таким образом, для Явыч. величина ограничена сверху величиной, пропорциональной

При более детальном анализе может быть получен следующий результат:

где не зависит от но зависит от и

Для невырожденных каналов величина В равна Оценка (41) справедлива при следующем выборе величин

Г. Обсуждение

Указанные оценки для величины характеризуют лишь ту часть работы при декодировании, которая необходима для прослеживания входных последовательностей, принадлежащих к "неправильной" части кода. Задача оценки сложности декодирования в "правильной" части кода связана с некоторыми математическими трудностями. Г. Галлагер из Массачусетского технологического института в частной беседе предложил несколько изменить описанный здесь алгоритм декодирования, что позволило оценить общее число операций при декодировании. Этот измененный алгоритм описан в боте Возенкрафта и автора Методами, схожими с теми, которые применялись в разд. IV, можно показать, что в целом среднее число операций при декодировании не превосходит величины, пропорциональной Интуитивные соображения подсказывают, что алгоритм, предложенный Галлагером, приводит к некоторому увеличению среднего числа операций по сравнению с числом, соответствующим первоначальному способу декодирования. Помимо этого, существуют еще некоторые модификации алгоритма последовательного декодирования, кажущиеся рациональными (см. [2]), но для них трудно (а может быть, и вообще нельзя) оценить объем вычислительных операций.

Мы не будем рассматривать здесь модификаций алгоритма декодирования. Достаточно будет сказать, что сложность последовательного декодирования растет с увеличением длины кода не экспоненциально, а по степенному закону. Моделируя на вычислительной машине алгоритм последовательного декодирования в приложении к двоичному симметричному каналу, Хорстейн установил [10], что среднее число всех вычислительных операций при декодировании меньше той величины,

которая указана в оценке (41). Краткое описание результатов, полученных Хорстейном, сделано Возекрафтом и автором этой статьи в работе [2].