Параллельный каскадный сверточный код с конечной последовательностью битов и декодер для такого кода

Параллельный каскадный сверточный код с конечной последовательностью битов и декодер для такого кода

Реферат

 

Изобретение относится к кодированию с исправлением ошибок, используемому при передаче коротких сообщений по каналам низкого качества, и, более конкретно, к способу параллельного каскадного сверточного кодирования и к соответствующему устройству декодирования. Технический результат повышение точности кодирования и декодирования при применении коротких сообщений. Схема параллельного каскадного сверточного кодирования использует нерекурсивные систематические сверточные коды с конечной последовательностью битов. Соответствующий декодер осуществляет циклическое декодирование по методу максимума апостериорной вероятности для формирования выходных результатов непрограммируемого и программируемого решений. Данная схема кодирования/декодирования обеспечивает повышение эффективности исправления ошибок для коротких сообщений. 6 с. и 30 з.п.ф-лы, 5 ил.

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

Предшествующий уровень техники Один из видов параллельного каскадного кодирования, определяемый как параллельное каскадное сверточное кодирование или "турбо"-кодирование, явился предметом недавних исследований, связанных со способами кодирования, ввиду весьма существенного выигрыша, обеспечиваемого таким кодированием, при использовании с блоками из 10000 и более битов (см. C.Berrou, A.Glavieux, P. Thitimajshima, "Near Shannon Limit Error-Correcting Coding and Decoding: Turbo-Codes, "Proceedings of the IEEE International Conference on Communications, 1993, pp. 1064-1070; J.D. Andersen, "The TURBO Coding Scheme, "Report IT-146 ISSN 0105-854, Institute of Telecommunication, Technical University of Denmark, December 1994; P. Robertson, "Illuminating the Structure of Code and Decoder of Parallel Concatenated Recursive Systematic (Turbo) Codes", 1994 IEEE Globecom Conference, pp. 1298-1303).

Однако было показано, что эффективность турбо-кода существенно снижается по мере уменьшения длины кодированного блока данных. Этот эффект обусловлен сильной зависимостью структуры весов рекурсивных систематических кодов для их компонентов от длины блока. Еще одной проблемой является надлежащее завершение блоков сообщения, подаваемых на турбо-кодер. Как описано в работе O. Joersson, H.Meyer, "Terminating the Trellis of Turbo-Codes", IEE Electronics Letters, vol.30, 16, August 4, 1994, pp. 1285-1286, перемежение, используемое в турбо-кодерах, может привести к невозможности завершения входных последовательностей кодера как с перемежением, так и без перемежения единственным набором конечных битов. Хотя возможно использование второй конечной последовательности в составе структуры сообщения, так чтобы кодер, работающий с последовательностью данных с перемежением, имел возможность надлежащего завершения последовательности данных, однако такой подход приводит к удвоению непроизводительных расходов на обработку, связанных с завершением цикла обработки кодера, и к снижению эффективной скорости кода. Альтернативный подход состоит в том, чтобы не завершать одну из последовательностей кодера, однако это снижает эффективность системы кодирования/декодирования, в частности, при применении для коротких сообщений. В работе A.S. Barbulescu, S.S. Pietrobon, "Terminating the Trellis of Turbo-Codes in the Same State", IEE Electronics Letters, 1995, vol. 31, 1, January 5, pp. 22-23, описан способ, который предусматривает ограничения, накладываемые на схему перемежителя, для того, чтобы обеспечить завершение цикла обработки рекурсивных систематических сверточных кодеров двух компонентов одной последовательностью битов завершения. Полученные результаты показывают некоторое снижение эффективности по сравнению с эффективностью, обеспечиваемой завершением цикла обработки обоих кодеров при использовании оптимизированного перемежителя. Кроме того, опубликованные данные для частоты ошибок по битам (BER) в зависимости от отношения энергии, приходящейся на бит, к спектральной плотности мощности шума (Е_b/N₀) показывают выравнивание коэффициента BER в диапазоне значений отношения Е_b/N₀, когда в турбо-кодере используются устройства кодирования на основе рекурсивного систематического сверточного кода.

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

Сущность изобретения В соответствии с настоящим изобретением схема параллельного каскадного сверточного кодирования использует нерекурсивные систематические сверточные коды (NSC-коды) с конечной последовательностью битов. Соответствующее устройство декодирования итеративно использует циклическое декодирование по методу апостериорного максимума (МАР-декодирование) для формирования на выходе непрограммируемого и программируемого решения. Использование кодов конечной последовательности битов решает проблему завершения входных последовательностей данных при турбо-кодировании, без связанного обычно с этим снижения эффективности устройства декодирования. Хотя нерекурсивные систематические сверточные коды, т. е. NSC-коды, в общем случае асимптотически слабее, чем рекурсивные систематические сверточные коды (RSC-коды), имеющие ту же память, по мере увеличения длины блока данных, свободное кодовое расстояние для NSC-кодов менее чувствительно к длине блока данных. Следовательно, параллельное каскадное кодирование с использованием NSC-кодов будет давать лучший результат, чем при использовании RSC-кодов с той же самой памятью для сообщений, которые короче, чем некоторое пороговое значение размера блока данных.

Краткое описание чертежей Признаки и преимущества настоящего изобретения поясняются в нижеследующем детальном описании изобретения, иллюстрируемом чертежами, на которых представлено следующее: фиг.1 - упрощенная блок-схема, иллюстрирующая параллельный каскадный кодер; фиг. 2 - упрощенная блок-схема, иллюстрирующая декодер для использования с параллельными каскадными кодами; фиг. 3 - упрощенная блок-схема, иллюстрирующая нерекурсивный систематический сверточный кодер с конечной последовательностью битов, предназначенный для использования в схеме кодирования согласно настоящему изобретению; фиг. 4 - упрощенная блок-схема, иллюстрирующая циклический МАР-декодер, используемый в качестве декодера компонента, для декодера, соответствующего схеме параллельного каскадного сверточного кодирования, согласно настоящему изобретению; фиг.5 - упрощенная блок-схема, иллюстрирующая другой вариант циклического MAP-декодера, используемого в качестве декодера компонента, для декодера, соответствующего схеме параллельного каскадного сверточного кодирования, согласно настоящему изобретению.

Детальное описание изобретения На фиг. 1 представлена обобщенная блок-схема кодера 10, осуществляющего обработку по схемам параллельного каскадного кодирования. Он содержит множество N кодеров компонентов 12, которые осуществляют обработку блоков битов данных, поступающих от источника. Блоки данных подвергаются перестановке согласно алгоритмам перемежения, реализуемым блоками перемежения 14. Как показано на чертеже, множеству N кодеров 12 соответствуют N-1 блоков перемежения 14. Выходы кодеров компонентов объединены для формирования одного составного кодового слова с помощью блока форматирования 16 кодового слова. Блок форматирования кодового слова соответствует характеристикам канала, и за ним может следовать блок форматирования кадра, соответствующий каналу и методу доступа к каналу системы связи. Блок форматирования кадра может обеспечивать ввод необходимых дополнительных элементов, таких как контрольные биты и символы синхронизации.

Значительное преимущество, касающееся скорости кода, может быть получено при параллельном каскадном кодировании, если коды компонентов представляют собой систематические коды. Кодовые слова (полученные на выходе), генерируемые систематическим кодером, включают в себя биты исходных данных, являющихся входными для кодера, и дополнительные биты контроля четности. (Избыточность, обусловленная контрольными битами, обеспечивает возможность исправления ошибок кода.) Поэтому если в параллельном каскадном кодере, показанном на фиг. 1, используются систематические кодеры, то кодовые слова, формируемые всеми кодерами компонентов 12, содержат биты входных данных. Если блок форматирования 16 формирует пакет данных или составное кодовое слово, содержащее только биты контроля четности, генерируемые каждым кодером компонентов 12, и блок информационных битов, подлежащий кодированию, то достигается существенное улучшение в скорости составного параллельного каскадного кода за счет исключения повторения информационных битов в передаваемом составном кодовом слове. Например, если кодер компонента 1 и кодер компонента 2 параллельного каскадного сверточного кодера, содержащего только два кодера компонентов, оба имеют скорость кодов, определяемую как 1/2, то скорость составного параллельного каскадного кода увеличивается с 1/4 для несистематических кодов компонентов до 1/3 при использовании систематических кодов компонентов.

Схемы параллельного каскадного кодирования, которые используют рекурсивные систематические сверточные коды (RSC-коды), в последнее время стали предметом множества исследований. Такие параллельные каскадные сверточные коды в литературе известны как "турбо"-коды. Как отмечено выше, показано, что эти параллельные каскадные сверточные коды могут обеспечивать высокую эффективность в смысле коэффициента BER в зависимости от отношения Е_b/N₀ для случая относительно больших сообщений, например, состоящих из десяти тысяч или более битов. Однако также было показано, что выигрыш, получаемый за счет кодирования, обеспечиваемый "турбо"-кодами, существенно снижается, когда размер блока данных уменьшается, так как мощность кодов компонентов, представляющих собой рекурсивные систематические сверточные коды, весьма чувствительная к длине блока данных. С другой стороны, эффективность нерекурсивного систематического сверточного кода с конечной последовательностью битов не зависит от длины блока данных для большинства практических целей. Достигаемая эффективность снижается, только если блок кодируемых битов данных меньше, чем минимальный размер, который определяется свойствами глубины решения для NSC-кодов.

На фиг. 2 показана обобщенная блок-схема декодера 20, используемого с параллельными каскадными кодами. Декодер 20 содержит следующие блоки: преобразователь 22 составного кодового слова в кодовые слова-компоненты, обеспечивающий преобразование составного кодового слова, принятого из канала, в индивидуальные принятые кодовые слова для каждого декодера компонентов 24; N декодеров компонентов 24, соответствующих N кодерам компонентов, показанных на фиг. 1; блоки перемежения 14 того же типа, что и использованные в параллельном каскадном кодере по фиг.1; первый и второй блоки исключения перемежения 28 и 29 соответственно, каждый из которых имеет характеристику переупорядочивания последовательности, которая эквивалентна последовательной цепочке из N-1 блоков исключения перемежения 30, соответственно N-1 блокам перемежения, использованных при кодировании. Требуемый порядок этих блоков исключения перемежения показан на фиг.2 и является обратным порядку блоков перемежения по фиг. 1. На выходах декодеров компонентов 24 формируется информация программируемого решения некоторого типа для оцениваемого значения каждого бита данных в принимаемом кодовом слове. Например, на выходах декодеров компонентов может быть сформирована первая функция вероятностей, что декодированные биты представляют собой 0 или 1 при условии принятой последовательности символов из канала. Одним из примеров такой первой функции, которая устраняет влияние условной вероятности P{d^j _t=0/Y^j _t}, является вероятность того, что j-й информационный бит в момент t равен 0 при условии j-го (систематического) бита принятого выходного символа Y_t канала. Как вариант, информация программируемого решения, выдаваемого на выходе декодеров компонентов 24, может представлять собой функцию отношения правдоподобия или функцию логарифма отношения правдоподобия Как показано N-ый декодер компонента имеет второй выход, например, второй функции условных вероятностей для декодируемых значений битов или указанных выше отношений правдоподобия. Примером такой второй функции является произведение P{d^j _t=0/Y^L ₁} и априорной вероятности, что d^j _t=0 принято от предыдущего декодера компонента.

Декодер для параллельных каскадных кодов работает итеративным методом следующим образом. Первый декодер компонента (декодер 1) вычисляет множество программируемых решений для последовательности информационных битов, кодированных первым кодером компонента, на основе принятого кодового слова и априорной информации о переданных информационных битах. В первой итерации, если отсутствует априорная информация о статистических характеристиках источника, предполагается, что биты могут с равной вероятностью принимать значения 0 и 1 ( т.е. Р{бит=0}=Р{бит=1}=1/2). Значения программируемых решений, вычисленные декодером 1, затем обрабатываются с перемежением с использованием блока перемежения того де типа (или того же самого блока), что был использован в кодере для обеспечения перестановки блока битов данных для второго кодера. Полученные значения программируемого решения с перестановкой и соответствующее принятое кодовое слово образуют входные данные для следующего декодера компонента (декодера 2). Значения программируемого решения с перестановкой, полученные от предыдущего декодера компонента и блока перемежения, затем используются следующим декодером компонента в качестве априорной информации о битах данных, которые должны быть декодированы. Декодеры компонентов осуществляют указанную обработку последовательно до тех пор, пока N-й декодер не вычислит множество выходных программируемых решений для блока битов данных, которые были закодированы кодером. На следующем этапе осуществляется исключение перемежения для значений программируемых решений с выхода N-го декодера, как описано выше. Затем первый декодер вновь осуществляет обработку принятого кодового слова, используя новые значения программируемого решения с N-го декодера в качестве априорной информации. Такая обработка в декодере осуществляется для желательного числа итераций. В заключение последней итерации последовательность значений, которые являются второй функцией выходных программируемых решений, вычисленных N-м декодером, обрабатывается для исключения перемежения и восстановления данных в порядке, в котором они были приняты параллельным каскадным сверточным кодером. Число итераций может быть задано предварительно, или может определяться динамически путем определения сходимости декодера.

Декодер обеспечивает информацию программируемого решения, которая является функцией вероятности P{d^j _t=0/Y^L ₁}, т.е. условной вероятности того, что j-й бит данных в k-битовом символьном входном сигнале кодера в момент t равен 0 при условии, что принимается множество канальных выходных сигналов Y^L ₁,={y₁,..,y_L}. Кроме того, декодер может обеспечить информацию непрограммируемого решения в функции своих выходных данных программируемого решения посредством устройства принятия решения, которое реализует решающее правило, такое как Это означает, что если P{d^j _t=0/Y^L ₁}>1/2, то если P{d^j _t=0/Y^L ₁} <1/2, то в других случаях d^j _t принимает случайным образом значения 0 или 1.

Типовые турбо-декодеры используют либо MAP-декодеры, как описано в работе L.R.Bahl, J.Соске, F.Jelinek, J.Raviv, "Optimal Decoding of Linear Codes for Minimizing Symbol error Rate", IEEE Transactions of Information Theory, March 1974, pp.284-287, или декодеры, использующие алгоритм Витерби для программируемых выходных данных (SOVA-декодеры), как описано в работе J. Hagenauer. P.Hoeher, "A Viterbi Algorithm with Soft-Decision Outputs and its Applications, 1989 IEEE Globecom Conference, pp. 1680-1686. MAP-декодер формирует вероятность того, что декодированное значение бита равно 0 или 1. С другой стороны, SOVA-декодер обычно вычисляет отношение правдоподобия для каждого декодированного бита. Очевидно, что это отношение правдоподобия может быть получено из вероятности Р {декодированный бит имеет значение 0} и, наоборот, с использованием вероятности Р{декодированный бит имеет значение 0}=1-Р{декодированный бит имеет значение 1}. Некоторые преимущества в смысле вычислений могут быть получены, если MAP-декодеры или SOVA-декодеры определяют логарифм отношений правдоподобия, то есть Показано, что выигрыш, получаемый за счет кодирования (возможность исправления ошибок), обеспечиваемый турбо-кодами, существенно снижается при уменьшении размера блока данных. Некоторые авторы объясняли данную закономерность в первую очередь свойствами RSC-кодов. Показано, что кодовое расстояние RSC-кода увеличивается с увеличением длины блока данных. И наоборот, минимальное кодовое расстояние RSC-кода уменьшается с уменьшением длины блока данных. Вторая проблема состоит в трудности завершения цикла обработки всех RSC-кодов, образующих схему турбо-кодирования, вследствие перемежения. К сожалению, отрицательные эффекты, обусловленные отсутствием завершения последовательности или наложением ограничений на схему блока перемежения, становятся тем более значительными при уменьшении длины блока данных.

В соответствии с настоящим изобретением коды компонентов в схеме параллельного каскадного кодирования содержат нерекурсивные систематические сверточные коды конечной последовательности битов. Использование таких кодов конечной последовательности битов решает проблему завершения цикла обработки входных последовательностей данных при турбо-кодировании и, тем самым, позволяет избежать ухудшения эффективности декодера для коротких сообщений. Хотя NSC-коды в общем случае более слабы, чем RSC-коды с той же самой памятью, свободное кодовое расстояние для NSC-кода менее чувствительно к длине блока данных. Следовательно, параллельное каскадное кодирование с использованием NSC-кодов будет более эффективно, чем с использованием RSC-кодов, при той же самой памяти для сообщений более коротких, чем предварительно определенное пороговое значение размера блока данных. Точка пересечения, определяющая эффективность, является функцией требуемой частоты ошибок в декодированных битах, скорости кода и памяти кода.

На фиг.3 представлен пример нерекурсивного систематического сверточного кодера с конечной последовательностью битов для скорости =1/2 и памяти = m, предназначенного для использования в схеме параллельного каскадного сверточного кодирования согласно настоящему изобретению. Для целей настоящего описания кодер, обозначенный как (n, k, m)-кодер, представляет собой кодер, для которого входные символы содержат k битов, выходные символы содержат n битов и m - память кодера в k-битовых символах. Для целей иллюстрации схема на фиг.3 показана для двоичных входных символов, т.е. k=1. Однако настоящее изобретение применимо для любых значений k, n, m.

Первоначально переключатель 50 находится в нижнем положении, и L входных битов записываются в регистр сдвига 52, по k за один раз (по одному входному символу за один раз для данного примера). После загрузки L-го бита в кодер переключатель устанавливается в верхнее положение, и кодирование начинается со сдвига пяти первых битов из второго регистра сдвига 54 в нерекурсивный систематический кодер; состояние кодера в этот момент соответствует {b_L, b_L-1,..., b_L-(km-1)} В данном примере выходные данные кодера содержат текущий входной бит и бит контроля четности, сформированный в блоке 56 (показанном в данном примере как сумматор по модулю 2) в функции состояния кодера и текущего входного символа. Кодирование заканчивается, когда закодирован L-й бит.

Другой аспект настоящего изобретения связан с декодером, соответствующим вышеописанному параллельному каскадному кодеру, содержащим циклический MAP-декодер, как описано авторами настоящего изобретения в совместно поданной заявке на патент США (RD-24923). В частности, в указанной заявке описан циклический MAP-декодер, предназначенный для декодирования сверточных кодов с конечной последовательностью битов. Циклический MAP-декодер может вырабатывать как оценку блока кодированных данных, так и надежную информацию для приемника данных, например процессора синтеза речевого сигнала для использования при маскировании ошибок передачи или процессора протокола для пакетированных данных в качестве меры вероятности ошибок блока для использования при принятии решений о запросе повторения.

В частности, как описано в вышеуказанной заявке, циклический МАР-декодер для решетчатых кодов с исправлением ошибок, которые используют конечные последовательности битов, формирует выходные данные программируемого ("мягкого") решения. Циклический МАР-декодер обеспечивает оценку вероятностей состояний в первом каскаде решеточного кода, причем эти вероятности заменяют априорно известное начальное состояние в обычном МАР-декодере. Циклический МАР-декодер обеспечивает распределение вероятности начального состояния любым из двух способов. Первый из них связывает решение с задачей собственного значения, для которой результирующий собственный вектор представляет собой желательное распределение вероятности начального состояния. Зная начальное состояние, циклический МАР-декодер выполняет остальную часть декодирования в соответствии с обычным алгоритмом декодирования на основе максимума апостериорной вероятности. Второй способ основан на рекурсивной обработке для обеспечения сходимости итераций к распределению начального состояния. После достаточного количества итераций состояние циклической последовательности состояний известно с высокой вероятностью, и циклический МАР-декодер выполняет остальную часть обработки в соответствии с обычным алгоритмом декодирования по методу максимума апостериорной вероятности.

Задачей обычного алгоритма максимума апостериорной вероятности является нахождение следующих условных вероятностей: Р{состояние в момент времени t/выходные данные канала приема у₁,...,у_L}.

В этом выражении L представляет длину блока данных в единицах числа символов кодера. (Кодер для (n,k)-кода обрабатывает k-битовые входные символы для формирования n-битовых выходных символов.) Обозначение у_t представляет собой выходные данные (символ) канала в момент t.

Алгоритм декодирования на основе максимума апостериорной вероятности прежде всего определяет вероятности: _t(m) = P{S_t= m; Y^L₁}; (1) т. е. совместную вероятность того, что состояние S_t кодера в момент t есть m и принято множество данных каналов Y^L ₁={y₁,...,y_L}. Это требуемые вероятности, умноженные на постоянную (Р{Y^L ₁}, вероятность приема множества выходных данных каналов {y₁,...,y_L}).

Затем определяем элементы матрицы Г_t в следующем виде: Г_t(i,j)=Р{состояние j в момент t; у_t состояние i в момент t-1} Матрица Г_t вычисляется как функция вероятности перехода канала R(Y_t, X), вероятности р_t(m/m'), что кодер осуществляет переход из состояния m в состояние m' в момент времени t, и вероятности q_t(X/m',m) того, что выходной символ кодера есть Х, при условии, что предыдущее состояние кодера есть m', а текущее состояние кодера есть m. В частности, каждый элемент Г_t вычисляется суммированием всех возможных выходных данных Х кодера следующим образом: МАР-декодер вычисляет L таких матриц, по одной для каждого решетчатого кода. Они формируются из принятых выходных символов канала с учетом свойства ветвей решетки для данного кода.

Затем определяется М элементов совместной вероятности вектора-строки _t в виде и М элементов условных вероятностей вектора-столбца _t в виде для j= 0, 1,..., (М-1), где М - число состояний кодера, (матрицы и вектора обозначены жирным шрифтом. ) Этапы алгоритма МАР-декодирования можно представить следующим образом: (i) Вычислить ₁,...,_L посредством прямой рекурсии: _t= _t-1Г_t, t = 1,..,L. (5) (ii) Вычислить ₁,...,_L-1 посредством обратной рекурсии: _t= Г_t+1t+1, t = L-1,...,1. (6) (iii) Вычислить элементы _t согласно выражению _t(i) = _t(i)_t(i), all i, t = 1,...,L. (7) (iv) Найти связанные величины, если это необходимо. Например, пусть А^J _t -множество состояний S_t={S¹ _t, S² _t,..., S^km _t) такое, что j-й элемент S^j _t множества S_t равен нулю. Для обычного нерекурсивного решетчатого кода S^j _t=d^j _t, т.е. бит данных в момент t. Поэтому выходные данные программируемого решения декодера имеют вид где и m - индекс, соответствующий состоянию S_t.

Выходные данные "жесткого" решения или декодированные биты получают с использованием выражения P{d^j _t=0/Y^L ₁} к следующему решающему правилу: T.e. ecли P{d^j _t=0/Y^L ₁}>1/2, то если P{d^j _t=0/Y^L ₁}<1/2, то в других случаях d^j _t принимает случайным образом значения 0 или 1.

В качестве другого примера связанных значений для этапа (iv), упомянутого выше, можно привести матрицу вероятностей _t, содержащую элементы, как определено ниже: Эти вероятности можно использовать, когда желательно определить апостериорную вероятность выходных битов кодера.

В стандартном применении алгоритма МАР-декодирования прямая рекурсия инициализируется вектором ₀= (1, 0,...,0), а обратная рекурсия инициализируется вектором _L= (1,0,..., 0)^T. Эти начальные условия основываются на предположении, что начальное состояние кодера S₀=0, а его конечное состояние S_L=0.

В одном из вариантов циклического МАР-декодера определяется распределение вероятности начальных состояний путем решения задачи собственных значений следующим образом. Пусть _t, _t, Г_t, _t будут теми же, что и ранее, а начальные ₀ и _L определяются следующим образом: _L- вектор-столбец (111... 1 )^T, а ₀- неизвестная (векторная) переменная.

Тогда (i) Вычислить Г_t для t=1, 2,...L согласно уравнению (2).

(ii) Найти максимальное собственное значение матричного произведения Г₁ Г₂. . .Г_L Нормировать соответствующий собственный вектор так, чтобы его компоненты суммировались до единицы. Этот вектор представляет собой решение для ₀. Собственное значение есть P(Y^L ₁).

(iii) Сформировать последующее значение _t путем прямой рекурсии согласно уравнению (5).

(iv) Начиная с _L, инициализированного, как указано выше, сформировать _t путем обратной рекурсии, как установлено в уравнении (6).

(v) Сформировать _t, как указано в уравнении (7), а также другие переменные, например выходные данные программируемого решения P{d^j _t=0/Y^L ₁} или матрицу вероятностей _t, как описано выше.

Изобретателями показано, что неизвестная переменная ₀ удовлетворяет матричному уравнению.

Из того факта, что эта формула выражает соотношение вероятностей, известно, что произведение Г_t матриц в правой части имеет максимальное собственное значение, равное P{ Y^L ₁} , и что соответствующий собственный вектор должен быть вектором вероятности.

При первоначальном _L= (111...1)^T уравнение (6) дает _L-1. Таким образом, повторное применение этой обратной рекурсии даст все значения _t. Если ₀ известно, a _L установлено, все вычисления в циклическом МАР-декодере в соответствии с изобретением осуществляются согласно обычному алгоритму МАР-декодирования.

На фиг.4 представлена упрощенная блок-схема, иллюстрирующая циклический МАР-декодер 110 для декодирования решетчатого кода с конечной последовательностью битов с исправлением ошибок в соответствии со способом, использующим собственный вектор, как описано выше. Декодер 110 содержит вычислитель Г_t, осуществляющий вычисление Г_t в функции выходных данных канала у_t. Вычислитель 112 получает на своих входах из памяти 130 следующие величины: вероятность перехода канала R(Y_t/X), вероятность p_t(m/m') того, что кодер осуществил переход из состояния m' в состояние m в момент t, и вероятность q_t((X/m', m) того, что выходной символ кодера есть X при условии, что предыдущее состояние кодера есть m', а текущее состояние кодера - m. Вычислитель 112 вычисляет каждый элемент Г_t путем суммирования по всем возможным выходным данным Х кодера в соответствии с уравнением (2).

Вычисленные значения Г_t подаются на вычислитель произведения матриц 114 для формирования матричного произведения Г₁, Г₂...Г_L с использованием единичной матрицы 116, например, из памяти переключателя 118 и схемы задержки 120. В момент t=l единичная матрица подается на вход вычислителя матричного произведения. Для каждого последующего момента времени с t=2 до t=L матричное произведение подается назад через схему задержки на вычислитель матричного произведения. Затем в момент времени t=L полученное матричное произведение подается через переключатель 121 на вычислитель нормированного собственного вектора 122, который вычисляет нормированный собственный вектор, соответствующий максимальному собственному значению матричного произведения, введенного в него. Если таким образом инициализировано ₀, т.е. как этот нормированный собственный вектор, последующие вектора _t определяются рекурсивно в соответствии с уравнением (5) в вычислителе матричного произведения 124 с использованием задержки 126 и переключателя 128. Соответствующие значения _t извлекаются из памяти 130, и полученные значения _t запоминаются в памяти 130.

Значения _t определяются в вычислителе матричного произведения 132 с использованием переключателя 134 и задержки 136 в соответствии с уравнением (6). Затем с использованием значений _t и _t вычисляются вероятности _t в вычислителе поэлементного произведения 140 согласно уравнению (7). Значения _t/ подаются на вычислитель вероятности значений декодированных битов 150, который определяет вероятность того, что j-й декодированный бит в момент времени t, т.е. d_t, равен нулю. Эта вероятность подается на устройство пороговой обработки 152, которое реализует следующее решающее правило: если вероятность с вычислителя 150 превышает 1/2, то принимается решение, что декодированный бит равен нулю; если вероятность меньше 1/2, то принимается решение, что декодированный бит равен единице; если вероятность равна 1/2 то декодированному биту случайным образом присваивается значение 0 или 1. Выходное значение устройства пороговой обработки соответствует биту на выходе декодера в момент времени t.

Вероятность того, что декодированный бит равен нулю, т.е. P(d^j _t=0/Y^j _t), также подается, как показано на фиг. 4, на блок 154 определения функции "мягкого" выходного результата для определения функции вероятности, т.е. f(P{d^j _t=0/Y^j _t)), так, чтобы, например, в качестве выходного результата "мягкого" решения декодера. Кроме того. может быть использована другая функция P(d^j _t=0/Y^j _t), Как вариант, полезной функцией для блока 154 может быть просто единичная функция, так что программируемое выходное решение соответствует просто P(d^j _t=О/Y^j _t).

Альтернативный вариант осуществления МАР-декодера определяет распределения вероятности состояния путем рекурсивного метода. В частности, в одном из вариантов осуществления (метод динамической сходимости) рекурсия продолжает осуществляться, пока не будет обнаружена сходимость декодера. В этом рекурсивном методе (или методе динамической сходимости) этапы (ii) и (iii) метода собственного вектора, описанного выше, заменяются следующим образом: (ii.a) Начиная с начального ₀ равного (1/М,...,1/М), где М - число состояний в решетчатом коде, вычислить рекурсию вперед L раз. Нормировать результаты так, чтобы элементы каждого нового _t суммировались до единицы. Сохранить все L векторов _t. (ii.b) Принимая ₀ равным _L из предыдущего этапа и начиная с момента t= 1, вычислить первые L_{w min} векторов _t. Т.е. вычислить для m=0, 1,...,М-1 и t=1, 2,..., L_{w min}, где L_{w min} соответствующее минимальное число каскадов решетчатого кода. Осуществить нормировку, как описано выше. Сохранить только самое последнее множество из L векторов , найденных путем рекурсивного вычисления согласно этапам (ii.a) и (ii.b), и _{Lw min} найденное ранее на этапе (ii.a).

(ii. c) Сравнить _{Lw min} полученное на этапе (ii.b) с ранее полученным множеством, полученным на этапе (ii.a). Если М соответствующих элементов их нового и старого значения _{Lw min} находятся в пределах поля допуска, то перейти к этапу (iv), как описано выше. В противном случае продолжать обработку согласно этапу (ii.d).

(ii.d) При t=t+1 вычислить _t= _t-1Г_t. Осуществить нормировку, как и ранее. Сохранить только самое последнее множество из L вычисленных векторов и _t, полученные ранее на этапе (ii.a).

(ii. e) Сравнить новые значения _t с ранее найденным множеством. Если М новых и старые _t находятся в пределах поля допуска, то перейти