Основы теории передачи информации


Алгоритмы поиска по решетке - часть 2


Если же ошибок становится намного больше, то декодер принимает решение, что он на ложном пути, и возвращается на несколько кадров назад.

Процедура декодирования последовательности r = (01000000..., содержащей ошибку во втором символе, показана на рис. 2.9.

Пусть    U  = (00000000000000000…   и   принята    последовательность  r = (0100000000000…, то есть возникла ошибка во второй позиции кода. Проследим путь декодера Фано по решетке  рис. 2.9.

Рис. 2.9

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

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




Начало  Назад  Вперед



Книжный магазин