Оптимальный декодер программируемых выходных данных для решетчатых кодов с конечной последовательностью битов

Оптимальный декодер программируемых выходных данных для решетчатых кодов с конечной последовательностью битов

Реферат

 

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

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

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

С другой стороны, вероятность ошибки символа или бита минимизируется с использованием так называемого декодера максимума апостериорной вероятности (MAP-декодера). MAP-декодер был впервые формально описан в работе Bahl, Cocke, Jelinek, Raviv (отсюда альтернативное название "BCJR-алгоритм"), "Optimal Decoding of Linear codes for Minimizing Symbol Error Rate, "IEEE Transactions on Information Theory, pp. 284-287, March 1976. Термины "МАР-декодер" или "BCJR-алгоритм" используются здесь для характеристики декодера данных, который выдает распределение вероятности состояний в каждом каскаде решетчатого кода и который также может использовать априорную информацию о статистике битов данных. MAP-декодер оптимален в том смысле, что он формирует эти вероятности состояния или программируемый ("мягкий") выходной результат с высокой точностью, в то время как имеются другие, хотя и более простые декодеры, которые могут формировать только аппроксимацию этих вероятностей. Варианты указанного алгоритма позволяют сформировать другую, связанную с указанной информацию, например вероятностное распределение символов данных в каждом каскаде или распределение выходных символов кодера в каждом каскаде.

MAP-декодер требует, чтобы начальное состояние в передаче решетчатого кода было известным, а в некоторых случаях требует также, чтобы было известно и конечное состояние. К сожалению, вследствие этого MAP-декодер не может быть использован для декодирования решетчатых кодов, которые используют конечную последовательность битов, т. е. кодов, для которых начальное и конечное состояния кодера не могут быть известны заранее. В частности, говорят, что передача решетчатого кода использует "конечную последовательность битов", если начальное состояние кодера идентично конечному состоянию для заданного блока входных битов. Очевидным для устройства "кодирования вперед" является знание того, каким должно быть, исходя из битов данных, конечное состояние. Это просто последние km битов блока сообщения, где k - число битов на входной символ кодера, m - размер памяти кода. Кодер с конечной последовательностью битов отличается от обычного кодера, в котором начальное состояние является предварительно конфигурированным состоянием, обычно состоянием "всех нулей". Обычные кодеры могут также завершать обработку предварительно конфигурированным состоянием путем добавления "конца" из km битов к входному блоку сообщения. Декодер с конечной последовательностью битов отличается тем, что он должен оценивать начальное состояние кодера в дополнение к его другим функциям. Если кодер с конечной последовательностью битов использует цилиндрическую решетку кодов, кодовое слово, генерируемое таким кодером, можно представить в виде круга символов. Декодер может начать обработку с любой произвольной точки круга, добиться состояния синхронизации и затем кодировать биты данных.

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

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

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

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

Детальное описание изобретения Кодер с конечной последовательностью битов использует цилиндрическую "решетку" решетчатого кода, поэтому кодовое слово, генерируемое таким кодером, можно представить как круг символов. На фиг. 1 показан пример цилиндрической решетки для кодера решетчатого кода с конечной последовательностью битов, имеющего четыре состояния и использующего двоичные входные символы. Недостаток априорной информации относительно начального состояния кодера в случае таких решетчатых кодов ухудшает надежность декодирования с использованием стандартного MAP (или BCJR) алгоритма декодирования для первой части принимаемого сообщения.

Выходная последовательность кодера для решетчатого кода с конечной последовательностью битов образует круговую диаграмму, как показано на фиг. 2. Состояния кодера показаны как упорядоченные по кругу. Если S₀ - одно из таких состояний, то кодер начинает обработку по процедуре кодирования с состояния S₀ в момент времени t₀ и после прохождения цикла по кругу через ряд переходов состояний заканчивает обработку в том же состоянии S₀. Декодер, который работает циклически с закодированной таким образом последовательностью, причем каждое состояние кодера приводит к следующему состоянию по кругу, представляет собой циклический декодер или декодер с конечной последовательностью битов.

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

Задачей обычного алгоритма максимума апостериорной вероятности (или BJCR-алгоритма) является нахождение следующих условных вероятностей: P { состояние в момент времени t/выходные данные канала приема y₁. . . y_L} .

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

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

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

Затем определяется M элементов совместной вероятности вектора-строки _t в виде _t(j) = P{состояние j в момемт t; y₁,...,y_t} (3) и M элементов условных вероятностей вектора-столбца _t в виде для j = 0, 1, . . . , (M-1), где M - число состояний кодера. (Матрицы и вектора обозначены жирным шрифтом. ) Этапы алгоритма MAP (или BCJR)-декодирования можно представить следующим образом: (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) для всех i,t = 1,..,L (7) (iv) Найти связанные величины, если это необходимо. Например, пусть A_t ^j - множество состояний S_t = { S_t ¹, S_t ², . . . , S_t ^km} , такое, что j-й элемент S_t ^j множества S_t равен нулю. Для обычного нерекурсивного решетчатого кода S_t ^j = d_t ^j, т. е. j-й бит данных в момент t. Поэтому выходные данные программируемого решения декодера имеют вид где и m - индекс, соответствующий состоянию S_t.

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

В качестве другого примера связанных значений для этапа (iv), упомянутого выше, можно привести матрицу вероятностей _t, содержащую элементы, как определено ниже: _t(i,j) = P{S_t-1= i; S_t= j; Y^L₁} = _t-1(i)_t(i,j)_t(j) Эти вероятности можно использовать, когда желательно определить апостериорную вероятность выходных битов кодера.

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

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

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

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

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

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

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

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

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

На фиг. 3 представлена упрощенная блок-схема, иллюстрирующая циклический MAP-декодер 10 для декодирования решетчатого кода с конечной последовательностью битов с исправлением ошибок в соответствии со способом, использующим собственный вектор, как описано выше. Декодер 10 содержит вычислитель 12 Г_t, предназначенный для приема упомянутых выходных сигналов канала, вероятности R(Y_t, X) перехода канала, вероятности p_t(m/m') того, что кодер осуществляет переход из состояния m' в состояние m в момент времени t, и вероятности q_t(X/m', m) того, что выходной символ кодера есть X при условии, что предыдущее состояние кодера есть m', а текущее состояние кодера есть m, и для определения из указанных данных скалярных элементов упомянутых матриц Г_t вероятности. Таким образом, вычислитель 12 получает на своих входах из памяти 30 вышеуказанные данные и осуществляет вычисление Г_t в функции выходных данных канала y_t. Вычислитель 12 вычисляет каждый элемент Г_t путем суммирования по всем возможным выходным данным X кодера в соответствии с уравнением (2).

Вычисленные значения Г_t подаются на вычислитель 14 произведения матриц Г_t, предназначенный для формирования произведения матриц Г₁, Г₂, . . . , Г_L с использованием единичной матрицы 16, получаемой, например, из памяти, переключателя 18 и схемы задержки 20. В момент t = 1 единичная матрица подается на вход вычислителя 14 произведения матриц. Для каждого последующего момента времени с t = 2 до t = L произведение матриц подается назад через схему задержки на вычислитель произведения матриц. Затем в момент времени t = L полученное произведение матриц подается через переключатель 21 на вычислитель 22 нормированного произведения матриц подается через переключатель 21 на вычислитель 22 нормированного собственного вектора, который вычисляет нормированный собственный вектор, соответствующий максимальному собственному значению матричного произведения, введенного в него. Если таким образом инициализировано ₀, т. е. как этот нормированный собственный вектор, последующие вектора _t определяются рекурсивно в соответствии с уравнением (5) в вычислителе 24 произведения матриц с использованием элемента задержки 26 и переключателя 28, как показано на чертеже. Соответствующие значения Г_t извлекаются из памяти 30, и полученные значения _t запоминаются затем в памяти 30.

Значения _t определяются в вычислителе 32 произведения матриц с использованием переключателя 34 и элемента задержки 36 в соответствии с уравнением (6). Затем с использованием значений _{t и t} вычисляются вероятности _t в вычислителе 40 поэлементного произведения, согласно уравнению (7). Значения _t подаются на вычислитель 50 вероятности значения декодированного бита, который определяет вероятность того, что j-й декодированный бит в момент времени t, т. е. d, равен нулю. Эта вероятность подается на устройство 52 пороговой обработки, которое реализует следующее решающее правило: если вероятность с вычислителя 50 превышает 1/2, то принимается решение, что декодированный бит равен нулю; если вероятность меньше 1/2, то принимается решение, что декодированный бит равен единице; если вероятность равна 1/2, то декодированному биту случайным образом присваивается значение 0 или 1. Выходное значение устройства пороговой обработки соответствует биту на выходе декодера в момент времени t.

Вероятность того, что декодированный бит равен нулю, т. е. P{ d_t ^j = 0} , также подается, как показано на фиг. 3, на блок 54 определения функции "мягкого" выходного результата для определения функции вероятности, т. е. P{ d^j, = 0} , такой, например, как в качестве выходного результата "мягкого" решения декодера. Кроме того, может быть использована другая функция P{ d_t ^j = 0} Как вариант, полезной функцией для блока 54 может быть просто единичная функция, так что программируемое выходное решение соответствует просто P{ d_t ^j = 0} .

Альтернативный вариант осуществления MAP-декодера согласно настоящему изобретению, определяет распределения вероятности состояния путем рекурсивного метода. В частности, в одном из вариантов осуществления (метод динамической сходимости) рекурсия продолжает осуществляться, пока не будет обнаружена сходимость декодера. В этом рекурсивном методе (или методе динамической сходимости) этапы (ii) и (iii) метода собственного вектора, описанного выше, заменяются следующим образом: (ii. a) Начиная с начального ₀, равного (1/M, . . . , 1/M), где M - число состояний в решетчатом коде, вычислить рекурсию вперед L раз. Нормировать результаты так, чтобы элементы каждого нового _t суммировались до единицы. Сохранить все L векторов _t. (ii. b) Принимая ₀ равным _L из предыдущего этапа и начиная с момента t = 1, вычислить первые L_{w min} векторов _t. Т. е. вычислить для m = 0, 1, . . . , M-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). Если M соответствующих элементов их нового и старого значения _{Lw min} находятся в пределах поля допуска, то перейти к этапу (iv), как описано выше. В противном случае продолжать обработку согласно этапу (ii. d).

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

(ii. e) Сравнить новые значения _t с ранее найденным множеством. Если M новых и старые _t находятся в пределах поля допуска, то перейти к этапу (iv). В противном случае продолжить обработку с этапа (ii. d), если два самых последних вектора не совпадают в пределах поля допуска и если число рекурсий не превысило определенный максимум (в типовом случае 2L); в противном случае перейти к этапу (iv).

Круговой "временной цикл", показанный на фиг. 4, показывает итоги обработки на этапах (ii. a) - (ii. e) для вычисления _t для t = 1, 2, . . . , L для циклического MAP-декодера, в результате которой получены оценки всех L векторов _t. Данный способ затем продолжается обработкой на этапах (iv) и (v), описанных выше для способа с использованием собственных векторов, для получения выходных результатов "мягкого" (программируемого) решения и декодированных выходных битов циклического MAP-декодера.

В циклическом MAP-декодере ₀ инициализируется как ₀= (1/M,...,1/M), поскольку исходное состояние кодера не известно. Также предполагается, что все M исходных состояний равновероятны. (Если это не соответствует действительности, то исходное состояние ₀(m) может быть присвоено соответственно априорной информации с учетом вероятностей исходного начального состояния. Таким образом, декодер, описанный здесь, также успешно применим для решеточных кодов с частичными конечными состояниями. ) Объяснение работы циклического MAP-декодера, соответствующего изобретению, облегчается с учетом определения _t(m). Элемент _t(m) представляет собой совместную вероятность того, что кодер находится в состоянии m в момент времени t и что декодер принимает последовательность символов { y₁, . . . , y_t} , поступающих из канала. Анализ уравнения (5) для рекурсивного вычисления _t выявляет влияние отсутствия априорной информации о начальном состоянии кодера решеточного кода с конечной последовательностью битов. Из уравнения (5) видно, что отсутствие информации о начальном состоянии кодера решеточного кода с конечной последовательностью битов будет приводить к смещению ₁(m) в том смысле, что вычисленная совместная вероятность того, что кодер находится в состоянии m в момент времени t = 1 и что декодер принимает выходной результат канала y₁, будет больше, чем это действительно имеет место для спусков при некорректных начальных состояниях, и меньше, чем это действительно имеет место для спусков при корректном начальном состоянии. Хотя это смещение будет иметь тенденцию к распространению вследствие рекурсивных вычислений _t(m), однако оно вместе с тем будет уменьшаться по мере приема большего количества выходных символов канала. Поэтому если длина L блока сообщения довольно велика, то _L(m) будет более точным, чем ₀(m), с учетом того, что декодер уже обработал всю последовательность символов при второй итерации декодирования, как показано выше для этапа (ii. b).

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

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

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

Возможный способ оценки требуемой глубины цикла для MAP-декодирования сверточного кода с конечной последовательностью битов состоит в определении ее из экспериментов с аппаратными средствами или с программным обеспечением при условии, что необходимо осуществить циклический MAP-декодер с переменной глубиной цикла, причем эксперименты должны проводиться для измерения частоты ошибок в декодированных битах данных в зависимости от отношения E_b/N₀ для последовательно возрастающих значений глубины цикла. Минимальная глубина цикла декодера, которая обеспечивает минимальную вероятность ошибки декодированных битов данных для конкретного значения отношения E_b/N₀, находится при условии, когда дальнейшее увеличение глубины цикла не снижает вероятности ошибки.

Если частота ошибок в декодированных битах данных, которая превышает минимально достижимую при конкретном значении отношения E_b/N₀, допустима, то возможно уменьшить требуемое число каскадов решетчатого кода, обрабатываемых MAP-декодером. В частности, поиск глубины цикла, как описано выше, может быть просто завершен, когда получена желаемая вероятность ошибки в битах данных.

Другим способом определения глубины цикла для данного кода является использование свойств кодового расстояния. С этой целью необходимо определить две различные глубины для принятия решения в декодере. Как использовано в настоящем описании, термин "корректный путь" относится к последовательности состояний или к пути через решетку решетчатого кода, который вытекает из кодирования блока битов данных. Термин "некорректное подмножество узла" относится к множеству некорректных (решетчатых) ответвлений из узла корректного пути и их "спускам". Обе глубины решений, определенные ниже, зависят от сверточного кодера. (Для целей иллюстрации данный вариант осуществления настоящего изобретения описан здесь со ссылками на сверточный кодер, однако следует иметь в виду, что настоящее изобретение не ограничено сверточными кодами. ) Глубины решений определяются следующим образом.

(i) Определить глубину прямого решения для исправления e-ошибки, LF(e), в качестве первой глубины в решетчатом коде, при которой все пути в некорректном подмножестве исходного узла корректного пути, независимо от того, сливается ли этот узел с корректным путем или нет, лежат более чем на Хэмминговом расстоянии 2e от корректного пути. Важность параметра LF(e) состоит в том, что если e или менее ошибок имеется перед исходным узлом и известно, что кодирование начато в данной позиции, то декодер должен осуществлять корректное декодирование. Формальное табулирование глубин прямого решения для сверточных кодов было проведено в работе J. B. Anderson, K. Balachandran, "Decision Depth of Convolutional Codes", IEEE Transactions on Information Theory, vol. IT-35, pp. 455-59, March 1989. Ряд свойств параметра LF(e) был описан в указанной работе, а также в работе J. B. Anderson, S. Mohan, "Source and Channel Coding - An Algorithmic Approach, Kluwer Academic Publishers, Norwell, MA, 1991. Главным из этих свойств является то, что существует простое линейное соотношение между LF и e, например, для кодов скорости 1/2 параметр LF примерно равен 9,08e.

(ii) Затем определить глубину решения без слияния для исправления e-ошибок, т. е. LU(e), которая определяется как первая глубина в решетчатом коде, при которой все пути в решетчатом коде, которые нигде не касаются корректного пути, лежат более чем на Хэмминговом расстоянии 2e от корректного пути.

Важность параметра LU(e) для циклического MAP-декодирования с принятием программируемого решения состоит в том, что вероятность идентификации состояния на действительно переданном пути высока после того, как декодер обработает LU(e) каскадов решетчатого кода. Поэтому минимальная глубина цикла для циклического MAP-декодирования равна LU(e). Вычисления глубины LU(e) показывают, что она всегда больше, чем LF(e), но что она подчиняется тому же самому аппроксимирующему закону. Это означает, что минимальная глубина цикла может быть оценена как глубина прямого решения LF(e), если глубина решения без слияния для кода не известна.

Путем нахождения минимальной глубины решения без слияния для данного кодера тем самым находим наименьшее число каскадов решетчатого кода, которое должно быть обработано конкретным циклическим декодером, который генерирует выходные резул