***** Google.Поиск по сайту:


Лекции по Теоретическим основам цифровой связи   

7. Канальное кодирование: часть 2

7.5. Другие алгоритмы сверточного декодирования

7.5.1. Последовательное декодирование

Ранее, до того как Витерби открыл оптимальный алгоритм декодирования сверточных кодов, существовали и другие алгоритмы. Самым первым был алгоритм последовательного декодирования, предложенный Уозенкрафтом (Wozencraft) [24, 25] и модифицированный Фано (Fano) [2]. В ходе работы последовательного декодера генерируется гипотеза о переданной последовательности кодовых слов и рассчитывается метрика между этой гипотезой и принятым сигналом. Эта процедура продолжается до тех пор, пока метрика показывает, что выбор гипотезы правдоподобен, в противном случае гипотеза последовательно заменяется, пока не будет найдена наиболее правдоподобная. Поиск при этом происходит методом проб и ошибок. Для мягкого или жесткого декодирования можно разработать последовательный декодер, но обычно мягкого декодирования стараются избегать из-за сложных расчетов и большой требовательности к памяти.

Рассмотрим ситуацию, когда используется кодер, изображенный на рис. 7.3, и последовательность m=11011 кодирована в последовательность кодовых слов U=1101010001, как было в примере 7.1. Допустим, что принятая последовательность Z является, фактически, правильной передачей U. У декодера имеется копия кодового дерева, показанная на рис. 7.6, и он может воспользоваться принятой последовательностью Z для прохождения дерева. Декодер начинает с узла дерева в момент t и генерирует оба пути, исходящие из этого узла. Декодер следует пути, который согласуется с полученными n кодовыми символами. На следующем уровне дерева декодер снова генерирует два пути, выходящие из узла, и следует пути, согласующемуся со второй группой и символов. Продолжая аналогичным образом, декодер быстро перебирает все дерево.

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

Если счет несовпадений превышает некоторое число (оно может увеличиваться после прохождения дерева), декодер решает, что он находится на неправильном пути, отбрасывая этот путь и повторяет все снова. Декодер помнит список отброшенных путей, чтобы иметь возможность избежать их при следующем прохождении дерева. Допустим, кодер, представленный на рис. 7.3, кодирует информационную последовательность m=11011 в последовательность кодовых слов U, как показано на рис. 7.1. Предположим, что четвертый и седьмой биты переданной последовательности U приняты с ошибкой.

Время

 

Информационная последовательность

m=

1

1

0

1

1

Переданная последовательность

U=

11

01

01

00

01

Принятая последовательность

Z=

11

00

01

10

01

Давайте проследим за траекторией пути декодирования на рис. 7.23. Допустим; что критерием возврата и повторного прохождения путей будет общий счет не согласующихся путей, равный 3. На рис. 7.23 числа у путей прохождения представляют собой текущее значение счетчика несовпадений. Итак, прохождение дерева будет иметь следующий вид.

Рис. 7.23. Схема последовательного декодирования

1.        В момент времени мы принимаем символы 11 и сравниваем их с ответвляющимся словами, исходящими из первого узла.

2.       Наиболее вероятна та ветвь, у которой ответвляющееся слово 11 (соответствующее входной битовой единице или ответвлению вниз), поэтому декодер решает, что входная битовая единица правильно декодирована, и переходит на следующий уровень.

3.       В момент на этом втором уровне декодер принимает символы 00 и сравнивает их с возможными ответвленными словами 10 и 01.

4.       Здесь нет "хорошего" пути; поэтому декодер произвольно выбирает путь, соответствующий входному битовому нулю (или ответвляющемуся слову 10), и счетчик несовпадений регистрирует 1.

5.       В момент времени декодер принимает символы 01 и сравнивает их на третьем уровне с ответвляющимися словами 11 и 00.

6.       Здесь снова ни один из путей не имеет преимуществ. Декодер произвольно выбирает нулевой входной путь (или ответвленное слово 11), и счетчик несовпадений возрастает до 2.

7.       В момент декодер принимает символы 10 и сравнивает их на четвертом уровне с ответвленными словами 00 и 11.

8.       Здесь снова ни один из путей не имеет преимуществ, и декодер произвольно выбирает нулевой входной путь (или ответвленное слово 00); счетчик несовпадений возрастает до 3.

9.       Поскольку счет несовпадений, равный 3, соответствует точке возврата, декодер "делает откат" и пробует альтернативный путь. Счетчик переустанавливается на 2 несовпадения.

10.   Альтернативный путь на четвертом уровне соответствует пути входной битовой единицы (или ответвленному слову 11). Декодер принимает этот путь, но после сравнения его с принятыми символами 10 несовпадение остается равным 1, и счетчик устанавливается равным 3.

11.   Счет 3 является критерием точки возврата, поэтому декодер делает откат назад с этого пути, и счетчик снова устанавливается на 2. На данном уровне все альтернативные пути использованы, поэтому декодер возвращается на узел в момент и переустанавливает счетчик на 1.

12.   В узле декодер сравнивает символы, принятые в момент времени а именно 01, с неиспользованным путем 00. В данном случае несовпадение равно 1, и счетчик устанавливается на 2.

13.   В узле декодер следует за ответвляющимся словом 10, которое совпадает с принятым в момент кодовым символом 10. Счетчик остается равным 2.

14.   В узле ни один из путей не имеет преимуществ, и декодер, как и определяется правилами, следует верхней ветви. Счетчик устанавливается на 3 несовпадения.

15.   При таком счете декодер делает откат, переустанавливает счетчик на 2 и пробует альтернативный путь в узле . Поскольку другим ответвляющимся словом является 00, снова получаем одно несовпадение с принятым в момент кодовым символом 01, и счетчик устанавливается равным 3.

16.   Декодер уходит с этого пути, и счетчик переустанавливается на 2. На этом уровне все альтернативные пути исправлены, по этому декодер возвращается на узел в момент и переустанавливает счетчик на 1.

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

18.   В узле декодер следует ответвляющемуся слову 01. Поскольку имеются не совпадения в одной позиции с принятыми в момент кодовыми символами 00, то счетчик устанавливается на 1.

Далее декодер продолжает свои поиски таким же образом. Как видно из рис. 7.23, финальный путь, счетчик которого не нарушает критерия точки возврата, дает правильно декодированную информационную последовательность 11011. Последовательное декодирование можно понимать как тактику проб и ошибок для поиска правильного пути на кодовом дереве. Поиск осуществляется последовательно; всегда рассматривается только один путь за раз. Если принимается не правильное решение, последующие пути будут ошибочными. Декодер может со временем распознать ошибку, отслеживая метрики пути. Алгоритм напоминает путешественника, отыскивающего путь на карте дорог. До тех пор, пока путешественник видит, что дорожные ориентиры соответствуют таковым на карте, он продолжает путь. Когда он замечает странные ориентиры (увеличение его своеобразной метрики), в конце концов приходит к выводу, что он находиться на не правильном пути, и возвращается к точке, где он может узнать ориентиры (его метрика возвращается в приемлемые рамки). Тогда он пробует альтернативный путь.




***** Яндекс.Поиск по сайту:



© Банк лекций Siblec.ru
Формальные, технические, естественные, общественные, гуманитарные, и другие науки.