Глава 5. МОДЕЛИРОВАНИЕ

Результаты гл. 3 показывают, что вычислительная машина при проведении последовательного декодирования сверточного кода может достичь пренебрежимо малой вероятности ошибки без необходимости проведения экспоненциально большого количества вычислений, связанных с неправильным множеством Однако задача оценки требуемого количества вычислений, связанных с правильным множеством оказывается трудно преодолимой математически. По существу, проведенный выше анализ для опирается на статистическую независимость полученной последовательности у и любой последовательности из в статистическом ансамбле случайных порождающих элементов Так как у представляет собой сумму переданного сигнала и шума, эта статистическая независимость не имеет места для [10]).

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

Имеются и другие модификации процедуры декодирования, которые эвристически кажутся

привлекательными, но для которых трудно, если вообще не невозможно, построить границу для среднего количества вычислений, необходимых при декодировании. Пусть, например, каждый информационный символ декодируется на основе некоторой предположительной последовательности, скажем охватывающей символов. Мы можем представить себе апостериорное распределение вероятностей для как "экспоненциальную воронку": мы почти наверняка знаем первый символ, несколько хуже второй, Относительно последнего символа в мы имеем мало информации или почти не имеем ее. Грубо говоря, процедура декодирования должна, используя у, расположить нашу воронку над тем х, для которого [правдоподобно получение из него этого у. Поэтому ясно, что должно быть эффективным начать поиски переменного отбросив первый символ от и добавив новый последний символ.

В подобных обстоятельствах представляется разумным при окончательной проверке метода последовательного декодирования и его модификаций положиться не на математический анализ, а на экспериментальные результаты. Исходя из этого, М. Хорстейн [15] моделировал операцию последовательного декодирования и двоичный симметрический канал на вычислительной машине ИБМ-704 Линкольновской лаборатории Массачусетского технологического института.