Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
гипотезу, что передано множество 111, соответствующее верхнему разветвлению первого ребра дерева. Пусть принята эта гипотеза; тогда следующие три символа должны быть символами одной из двух верхних троек символов, обозначенных на рис. 6.9.2 как хt2), *г2\ xi3)-Очевидно, что предпочтительнее принятие гипотезы 101, соответствующей верхнему разветвлению. Продолжая таким же образом, мы принимаем гипотезу, что третья тройка переданных символов равна 001,
Рис. 6.9.2. Древовидная структура сверточного кода.
а четвертая ООО. Этим гипотезам соответствует пунктирная линия на рис. 6.9.2. Метод, который был продемонстрирован — это, по существу, декодирование символ за символом, при котором выбор гипотезы при декодировании тройки символов используется для уменьшения числа возможных выборов при декодировании последующей тройки. В рассмотренном примере совпадение всех, начиная с третьего, символов последовательности, которую мы на основании нашей гипотезы считаем переданной, с символами принятой последовательности подтверждает, что принятые ранее гипотезы правильны.
Теперь рассмотрим второй пример, который иллюстрирует, что случится, если была принята неправильная гипотеза. Предположим, что передана та же самая первоначальная последовательность 111 101
283
001 ООО, но принята последовательность 010 101 001 000... Декодер, которому не известно, что было передано, принимает гипотезу, что первые три переданные символа равны 000, что соответствует нижнему ребру, выходящему из первой точки ветвления. Две следующие принятые гипотезы тогда соответствуют символам 111 и 101. Из этих первых девяти символов последовательности, которую мы считаем переданной, три символа не совпадают с символами принятой последовательности. Случившееся является следствием того, что декодер, приняв однажды неправильную гипотезу, вынужден выбирать последующие гипотезы среди последовательностей, не имеющих отношения к принятой последовательности. Поэтому в конце концов декодер, как правило, способен распознать, что он, по-видимому, принял неправильную гипотезу. Тогда можно вернуться назад, проверить альтернативные гипотезы, после чего, вероятно, декодирование будет правильным. Таким образом, принятие каждой гипотезы упрощает дальнейший процесс проверки гипотез путем уменьшения числа возможных выборов и в то же время дает дополнительные данные для проверки правильности ранее принятых гипотез.
Последовательный декодер является декодером, предназначенным для кодов с древовидной структурой, который декодирует их путем принятия пробных гипотез относительно последовательных ребер дерева и изменяет эти гипотезы, если последующий выбор указывает на неправильность ранее принятых гипотез. К сожалению, чрезвычайная простота этой концепции исчезнет при четкой формулировке правила о том, должен ли декодер продолжать принимать новые гипотезы, или он должен вернуться для изменения старой гипотезы. Нашим целям отвечают три требования к стратегии поиска при последовательном декодировании. Во-первых, стратегия должна в конце концов с высокой вероятностью привести к правильному декодированию последовательности источника. Во-вторых, количество вычислений, требуемых декодером, не должно быть чрезмерным. Наконец (это требование не возникает для действующих систем), стратегия должна допускать математическое исследование. Первая такая стратегия (или алгоритм) была предложена Возенкрафтом (1957), который к тому же явился автором идеи последовательного декодирования. Мы ограничимся здесь рассмотрением усовершенствованного более позднего алгоритма, принадлежащего Фано (1963).
Предполагается, что канал является дискретным каналом без памяти с переходными вероятностями Р (/1 k). Детальное рассмотрение кодера будет проведено позднее; коротко говоря, он состоит из трех блоков. Первый из них является двоичным сверточным кодером, аналогичным представленному на рис. 6.8.3 или описываемому соотношением (6.8.8). Каждую единицу времени в двоичный кодер поступают от источника к двоичных символов, а он производит на выходе av двоичных символов, где а и v целые. Второй блок осуществляет сложение фиксированной двоичной последовательности и этой двоичной последовательности. В-третьих, полученная сумма разбивается на подблоки из а символов каждый, и каждый подблок отображается во входную букву канала с помощью отображения, аналогичного представленному 284
Г(х,; у,)~2 2
на рис. 6.2.1*>. Мы видим, что при таком кодировании каждые X символов источника порождают v символов канала и что скорость кода, вычисленная в натуральных единицах на символ канала, равна
R= — In 2. (6.9.1)
v
Графически можно представить такое кодирование в виде древовидной структуры, аналогичной изображенной на рис. 6.9.2, отличающейся, однако, тем, что из каждой точки ветвления выходит не 2 возможных ребра, как на рисунке, а 2к, и что каждое ребро состоит из v символов канала.
