5.6. Усечение указателей пути и ошибки начальной синхронизации
В § 4.7 уже указывалось на то, что соображения практического характера требуют ограничить длину хранимых для каждого состояния указателей пути величиной порядка нескольких длин кодового ограничения. Одним из способов ограничения указателей пути
ребрами является принятие решения по максимуму правдоподобия на основании совокупности всех путей, которые не совпадали с правильным на
ребрах, предшествующих рассматриваемой точке Как нетрудно проверить, ошибка усечения может появиться только в том случае, если неправильный путь, ответвляющийся от правильного в
узле и несовпадающий с ним на последующих
ребрах имеет на этом уровне большую метрику, чем правильный путь. Это связано с тем, что если пути сливаются с правильными до
ребра от момента ветвления, то путь с большим отношением правдоподобия будет выживать независимо от того, осуществляется или нет усечение указателей пути. Рассмотрим множество
путей, которые ответвляются от правильного пути в узле
и не совпадают с ним ровно на
последующих ребрах. Число таких путей не превышает
Используя в точности те же рассуждения, что и в § 5.1, и повторяя вывод (5.1.17) для
можно проверить, что средняя по ансамблю вероятность того, что неправильный путь имеет большую метрику, чем правильный путь после
несовпадающих ребер, ограничена сверху неравенством
После максимизации по
получаем обычную верхнюю границу для средней по ансамблю вероятности ошибки для блочного кода с длиной блока
где для малых скоростей
для больших скоростей
Сравнивая (5.6.2) с (5.1.32), приходим к выводу, что ошибка усечения не влияет существенно (экспоненциально) на общую вероятность ошибки, если длина усечения
такова, что
где функция
задаваемая формулами (5.6.3) и
показатель экспоненты блочного кодирования,
показатель экспоненты сверточного кодирования, задаваемый формулами (5.1.33) и (5.1.34). Для каналов с большим шумом условие (5.6.5) сводится к следующему:
При
это неравенство указывает на то, что для каналов с большим шумом длина усечения должна быть не меньше
На практике было установлено, что длина усечения, равная четырем-пяти длинам кодового ограничения, вполне достаточна для того, чтобы ухудшением характеристик из-за усечения указателей путей можно было пренебречь.
Другая задача, возникающая в реальном декодере, связана с установлением начальной синхронизации в узлах, отличных от
начального. Как уже отмечалось § 4.7, синхронизация со временем устанавливается автоматически, если только удается установить начальный символ для каждого из ребер (здесь предполагаем, что это сделано). Однако на начальном этапе установления синхронизации может возникнуть много ошибок. Начинать декодирование принятой последовательности не с начала — это значит не иметь начальных значений метрик. Поэтому можно положить их все равными нулю. При обычном декодировании ошибкой начальной синхронизации можно назвать любую ошибку, порождаемую путем, который в начале не совпадает с правильным, так как ошибка, порождаемая любым путем, совпадающим вначале с правильным, проявит себя в любом случае.
Через
ребер после начала декодирования, производимого с середины принятой последовательности с равными нулю начальными значениями метрик, число путей, первоначально не совпадающих с правильным путем, но на рассматриваемом уровне впервые начинающих совпадать с ним, не превышает
Ясно, что множество этих путей является двойственным (зеркальным отображением) для множества
рассматривавшегося выше в связи с ошибками, вызванными усечением. Следовательно, вероятность ошибки начальной синхронизации убывает экспоненциально по
где
число ребер до начала декодирования. В действительности верхняя граница для средней по ансамблю вероятности ошибки начальной синхронизации совпадает с (5.6.2), если в последнем соотношении
заменить на
Таким образом, после
ребер, где
влияние начальной синхронизации на вероятность ошибки становится пренебрежимо малым. На практике первые
ребер всегда считаются ненадежными, если декодер начинает работать с середины принятой последовательности.