У. Питерсон - Коды, исправляющие ошибки (1267328), страница 92
Текст из файла (страница 92)
Поэтому эту вершину полезно расщепить, как это сделано на модифицированной диаграмме состояний, приведенной на фиг. 13.15,б. Для нахождения передаточной функции модифицированного графа Т(К Е) может быть использована стандартная процедура сокращения графа сигналов. Каждой ветви ставится в соответствие передаточная функция ()'Ч.', где () и 5 †.фиктивные переменные, д — вес Хэмминга ветви, а показатель степени при Е представляет собой длину, измеряемую числом ветвей.
Пример. Для кода из предыдущего примера Т((), Ь) = ( — — ))Ч,з ~~~~~ (()Е. (1 + Л))~. (13.15) в-О Полагая Ь = 1, получим передаточную функцию расстояний Т(д)= — =Ь)з+2И+4И+ ... +2Ч)'+'+ .... (13.16) Таким образом, код имеет д,„= 5 и содержит 2' кодовых слов веса ; 1 5, Поскольку коэффициент при И в равенстве (13.15) равен Ьз, то кодовое слово веса 5 распространяется на 3 ветви. Аналогично два кодовых слова веса 6 распространяются на 4 и 5 ветвей.
Передаточную функцию модифицированной диаграммы состояний кодера можно использовать и для вычисления вероятности первой ошибки Рм если двоичный код применяется в двоичном симметричном канале с вероятностью ошибки Р. Каждый член ,ОеЬВ в разложении функции Т(Ю,Ь) в степенной ряд по двум переменным соответствует кодовому слову длины 1 ветвей и веса о, у которого первый ненулевой символ находится в блоке с номером О. Пусть передана последовательность из нулей и рассматривается кодовое слово веса с( и длины 1. Если произошло ((о+ 1)/2) ошибок в с( ненулевых позициях, то блок с номером О будет неправильно декодирован.
(Если д четно и происходит о72 ошибок, то неправильное декодирование будет происходить с вероятностью 0,5.) Тогда вероятность неправильного декодирования кодового слова веса о равна С,'~Р'Я~ '. д — нечетное, 1 = ке+ 1)(2] — Се Р ~Я ~+ ) СеР'Я~ ', Н вЂ” четное. ьея+! (13.17) т(П)= Х 1,П". (13.16) Вероятность неправильного декодирования первого блока ограни-. чена сверху суммой вероятностей того, что зто слово нельзя отли. чить от какого-то другого произвольно выбранного ненулевого ко нового слова [Это и есть суммарная граница из равенства (4.24).] Таким образом, (! 3.19) При нечетном Ы первое слагаемое здесь отсутствует. Пусть пере- даточная функция расстояний Можно показать [152), что Р.
< Ьу~4К)'. т. е. Р„( т (~/ЮО). (13.20) (13.21) Итак, если задана передаточная функция кодера, то оценка для Р>, может быть найдена непосредственным образом. Однако найти Т(0,1.) даже для не очень сложных декодеров довольно трудно. 13.8. Последовательное декодирование Для систематической поисковой процедуры декодирования, описанной в начале предыдущего раздела, требуется ф действий, чтобы декодировать произвольный блок сверточного (и, й)-кода. Ясно, что такая процедура применима только к кодам с малыми значениями А. Хотя с помощью алгоритма Витерби можно декодировать и более длинные коды, его применение также ограничено кодами умеренной длины.
Рассмотрим в качестве канала без памяти двоичный симметричный канал. Для подавляющего большинства путей (кодовых слов) условная вероятность того, что было передано некоторое кодовое слово, при известном слове на выходе убывает экспоненциально с ростом кодовой длины. Если можно избежать рассмотрения этих маловероятных путей, то среднее число требуемых для декодирования действий может быть сведено до реально осуществимого даже для длинных кодов.
Последовательное декодирование — это практический путь к достижению этой цели [330). Приводимое здесь описание последовательного декодирования может быть использовано лишь для первоначального ознакомления с этим вопросом. Читатель также может обратиться к работам Возенкрафта и Джекобса [3321, Галлагера [103[ и работам, указанным там в списках цитированной литературы. Последовательное декодирование может быть использовано при декодировании любого сверточного кода. Далее рассматривается двоичный систематический код с йз информационными символами в блоке из лз символов. Длина кодового ограничения кода и, = т,пь Код будет использоваться в двоичном симметричном канале с метрикой Хэмминга; результаты без труда переносятся и на более общие метрики.
Предположим, что передается последовательность из нулей; рассмотрим следующую процедуру декодирования. Декодер, который может порождать кодовое дерево, проверяет принятый набор длины пь Он сравнивает его с 2ь ветвями, исходящими из первой вершины дерева, н выбирает ветвь, наиболее близкую к принятому набору длины пм При отсутствии ошибок декодирование происходит правильно. Бслн имеются ошибки, декодер выбирает неправильную ветвь, и даже при отсутствии дальнейших ошибок не будут найдены ветви, наиболее точно согласованные с принятыми наборами длины пг. Этот декодер в течение некоторого времени «исправляет» ошибки и выдает в результате некоторое кодовое слово. Было бы разумнее предположить, что как раз перед тем, как декодер начал исправлять <ошибки», он совершил ошибку в декодировании. Тогда декодер должен вернуться на прежнее место, заменить подозрительную ветвь и продолжить поиск вдоль нового пути по дереву.
Для двоичного симметричного канала с вероятностью ошибки Р принятая последовательность длины и будет отличаться от переданной кодовой последовательности в среднем в пр позициях. Наиболее удаленная кодовая последовательность будет отличаться приблизительно в п)2 позициях. Таким образом, если искаженная последовательность не содержит слишком много ошибок, у декодера будет мало трудностей в нахождении правильного пути. Однако, возможно, что декодер должен исследовать огромное количество путей, прежде чем найдет правильный. К счастью, количество проверяемых путей может быть значительно уменьшено при умелом выборе процедуры поиска по дереву.
Кроме того, если для потоков входных и выходных символов декодера имеется буферное устройство, то изредка можно исследовать и довольно большое количество путей. Пусть через 1 обозначено количество ветвей, которые предстоит декодировать, а й(1) — полное расстояние между путем из 1 ветвей, по которому должен пройти декодер, и принятой последовательностью из 1пл символов.
Рассмотрим нормированную функцию расстояния 1(1) = д (1) — па(Р', где Р(Р'('Ь. Для правильных путей с((1) приблизительно равно п,1Р, а функция 1(1) будет отрицателыюй. Почти для всех неверных путей а(1) = (па1)/2 и 1(1) положительная. Характерное поведение функции 1(1) показано на фиг. !3.16. Декодер вычисляет 1(1) для рассматриваемого пути; когда величина этой метрики превысит порог Т, декодер возвращается к ближайшему ранее иеисследо. ванному пути, для которого 1(1) «= Т, и начинает прослеживать новый путь. Процедура для отбрасывания маловероятных путей и поиска новых путей, известная как алгоритм Фана (80), представлена в виде блок-схемы на фиг.
13.17. В основном она состоит в том, что декодер, когда это возможно, уменьшает порог на фиксиро- щ и, Фиг, 13.16. Типичный вид нормированной функции расстояния 11рд — — — неправильные пути: — правильный путь, ванную величину Ь и переходит к следующей вершине. Если по всем ветвям, Исходящим из данной вершины, порог превышен, то декодер отступает на одну вершину и выбирает следующую наиболее вероятную неисследованную ветвь. После того как проверены и отвергнуты все ветви, выходящие из данной вершины, декодер отступает снова, увеличивая, если необходимо, порог. Целое Фиг. !3.17.
Блок-схема алгоритма последовательного декодирования Фано. число Л является расчетным параметром, который выбирается так, чтобы минимизировать среднее число ветвей, исследуемых декодером. для алгоритма Фано не существует ветвей, проверяемых дважды прн одном и том же пороге; следовательно, декодер не ~~жег «зациклиться». Тем не менее после появления необычно большого количества ошибок декодеру потребуется исследовать существенно большее число ветвей.
Переменная вычислительная нагрузка декодера обусловливает необходимость использовании буферного устройства на входе и выходе. Можно показать, что количество действий (т. е. число проверяемых ветвей), требуемых для декодирования одной ветви, имеет распределение Парето Рг (количество действий ) й) = Ь ", где а — положительная функция от Р, )г и Л 1265).
Для й )~ йщ„, = 1 — 1од (1 + -уг4РЯ среднее значение этого распределения увеличивается экспоненциальио с ростом л,. Для более низких скоростей среднее значение ограничено сверху константой и поэтому не зависит существенно от и,. Количество действий, требуемых в последнем случае, очень переменно, и даже при наличии большого буферного устройства вероятность переполнения его существенно больше, чем вероятность необнаружения ошибки. Поскольку переполнения буфера всегда распознаются декодером, ошибки декодирования, вызывающие эти переполнения, всегда могут быть обнаружены. На практике вероятность необнаружения ошибки декодером, работающим по алгоритму Фано, обычно ничтожно мала в предположении, что скорость Й ( Йвмч.
Это ограничение на скорости несколько слабее при использовании блоковых кодов в совокупности с последовательным декодированием. Удачные гибридные схемы предложены в работах (78, 146). Зигангиров (347) и Джелинек (153) предложили алгоритм последовательного декодирования (стзк-алгоритм), у которого имеются некоторые преимущества по сравнению с алгоритмом Фано. Замечания Первый найденный класс сверточных кодов, исправляющих многократные ошибки, составили самоортогональные коды Месси (205].
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
