ВЫСОКОСКОРОСТНОЙ МОДУЛЬ СЛОЖЕНИЯ (СРАВНЕНИЯ) ВЫБОРА ДЛЯ ДЕКОДЕРА ВИТЕРБИ Российский патент 2005 года по МПК G06F7/38 H03M13/41 

Настоящее изобретение относится, в целом, к приложениям алгоритма Витерби. В частности, настоящее изобретение относится к усовершенствованным системе и способу осуществления высокоскоростной операции сложения/сравнения/выбора (ССВ) по схеме “бабочка” в реализации алгоритма Витерби.

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

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

На фиг.1А изображен типичный сверточный кодер. Сверточный кодер 100 содержит 8-разрядный секционированный сдвиговый регистр 110 и пару сумматоров 120 типа “исключающее ИЛИ”, которые преобразуют последовательность входных информационных битов U(D) 105 в последовательность выходных кодовых символов 125 C₀(D), C₁(D). В частности, фиг.1А демонстрирует пример кодирования со скоростью 1/2, которое порождает два выходных кодовых символа 125 C₀(D), C₁(D) для каждого входного информационного бита U(D) 105. Заметим, что конкретные кодовая скорость и конфигурация сверточного кодера 100 показаны лишь в иллюстративных целях и никоим образом не ограничивают действие или объем различных вариантов осуществления изобретения. Поэтому, применительно к вариантам осуществления изобретения, можно использовать разные кодовые скорости, например 1/3 или 3/4.

Кодер 100 генерирует каждый выходной кодовый символ 125 C₀(D), C₁(D), подвергая входной битовый поток U(D) 105 операциям сдвига и исключительного ИЛИ, согласно конкретной конфигурации сдвигового регистра, заданной порождающими многочленами кодирования G₀(D), G₁(D). В данном случае на фиг.1А показана схема соединений сдвигового регистра, которая обеспечивает порождающий многочлен кодирования со скоростью . Коэффициенты многочлена G₀(D) подвергают свертке со входной последовательностью данных U(D) 105, чтобы генерировать выходной символ 125 сверточного кода C₀(D). Аналогично, на фиг.1А показан порождающий многочлен кодирования со скоростью , коэффициенты которого подвергают свертке со входной информационной последовательностью U(D) 105, чтобы генерировать выходной символ 125 сверточного кода C₁(D). Ограничительная длина К кодера 100 на единицу превышает количество элементов задержки в сдвиговом регистре 110; для кодера 100 ограничительная длина К равна 9. Для каждого информационного бита 105, введенного в кодер 100, выходные кодовые символы 125 C₀(D), C₁(D) зависят от введенного бита равно, как и от предыдущих К-1 входных битов. Поэтому кодер 100 порождает выходные кодовые символы 125 C₀(D), C₁(D), которые способны пробегать 2^K-l возможных состояний кодера.

В типичной системе связи выходные кодовые символы 125 C₀(D), C₁(D) затем модулируют и передают по зашумленному каналу (не показан). В итоге декодер принимает зашумленный поток данных, подвергнутых сверточному кодированию, и применяет алгоритм Витерби, который использует свойства сверточных кодов окончательно определять входную информационную последовательность U(D) 105.

Достоинство сверточных кодов состоит в повторяемости их структуры с высокой степенью, которая обеспечивает симметричное кодовое дерево. Теоретически сверточный код способен порождать бесконечную последовательность кодовых символов. Однако, ввиду его симметрии, количество состояний, подлежащих оцениванию при построении наиболее вероятного пути, ведущего к введенной последовательности данных U(D) 105, снижается до 2^K-1 (в данном случае, 256) состояний. Кроме того, при декодировании такого симметричного кода интерес представляет только наиболее вероятный (т.е. выбранный) локальный путь - все остальные пути можно отбросить и более не рассматривать. Дело в том, что наиболее вероятный глобальный путь через состояние обязательно должен следовать выбранному локальному пути через это состояние.

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

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

Алгоритм Витерби можно кратко охарактеризовать следующим образом: когда время разделено на d выборок и для каждой временной выборки k существует n возможных состояний Ski

(где i - целое число из 1•n, и k - целое число из 1•d). Для k>l каждого состояния можно достичь путем из любого из р предшествующих состояний Sk-1j (где j - целое число из 1•d). Для каждого состояния идентифицируют и сохраняют тот путь из этих р возможных путей, который имеет минимальную метрику, а также сохраняют значение этой метрики:

Инициализация: для начальной временной выборки (k=1) инициализируют метрику, сохраненную для каждого состоянии S1i

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

Итерация: для каждой временной выборки (k=2•d) посещают все эти состояния Ski

. Для каждого состояния Ski вычисляют метрику каждого пути j, ведущего к этому состоянию, как сумму (а) метрики предшествующего состояния Sk-1j и (b) метрики bmkj ветви, ведущей из состояния Sk-1j к состоянию Ski Среди р путей, ведущих к каждому состоянию Ski, выбирают путь с наименьшей метрикой (т.е. выбранный путь) и сохраняют его для этого состояния, и метрику этого пути также сохраняют как метрику smki этого состояния.

Обратная цепь: после посещения всех состояний, отвечающих последней временной выборке, идентифицируют состояние Sdi

, имеющее наименьшую метрику состояния. Из памяти считывают выбранный путь к этому состоянию и, таким образом, идентифицируют соответствующее состояние для временной выборки d-1. Затем, из памяти считывают выбранный путь к этому последнему состоянию, и повторяют процесс обратной цепи до тех пор, пока не идентифицируют все состояния, содержащие путь, ведущий к состоянию Sdi (т.е. наиболее вероятный путь через матрицу состояние-время).

Таким образом, для любой временной выборки k алгоритм Витерби вычисляет метрику путей, ведущих к состояниям Skn

, определяет выбранные пути (по одному для каждого из n состояний Skn) и сохраняет n выбранных путей, а также их соответствующие метрики. Это все равно, что сохранять, для каждого рассматриваемого конечного состояния, исходное состояние, из которого к нему можно придти. Поэтому любая реализация алгоритма Витерби предусматривает использование модуля 150 сложения/сравнения/выбора (ССВ), показанного на фиг.1В, для выполнения этих операций. Модуль 150 ССВ предназначен для вычисления значений метрики состояния, а также для определения взаимосвязи между исходным и конечным состояниями посредством операций ССВ по схеме “бабочка”. Одна операция 155 ССВ по схеме “бабочка” представлена на фиг.2.

Операция 155 “бабочка” содержит только те из возможных переходов между состояниями, которые могли бы произойти для двух конкретных исходных состояний кодера 100. Это отчасти объясняется тем фактом, что в любое данное время состояние кодера 100 получено из предыдущего состояния кодера сдвигом вправо на 1 разряд. Следующий (после сдвига вправо) информационный бит определяет, какой переход произошел из исходного состояния, и становится старшим разрядом (СР) конечного состояния. Поэтому существует только два возможных конечных состояния, в которые возможен переход из исходного состояния. Таким образом, о чем свидетельствует фиг.2, кодер 100 может переходить только из исходного состояния “х0” в конечное состояние “0х” или “1х” и из исходного состояния “х1” в конечное состояние “0х” или “1х”, в зависимости от значения введенного информационного бита U(D). Заметим, что обозначение “х0” и “х1” указывает, что младший разряд (МР) исходного состояния равен “0” и “1” соответственно, а более высокие разряды представлены как “х”; и обозначение “0х” или “1х” указывает, что СР конечных состояний равен 0 или 1 соответственно, а более низкие разряды представлены как “х”. Величина “х” имеет одно и то же значение (например, 7-разрядное значение) независимо от того, входит она в состав представления исходного состояния или конечного состояния.

На фиг.2 также отражен тот факт, что каждый переход из исходного состояния в конечное состояние порождает гипотетический набор кодовых символов H₀(D), H₁(D) или В действительности, когда кодер 100 действует по параллельным ветвям схемы “бабочка” 155 ССВ (например, осуществляет переходы из “х0” в “0х” или из “х1” в “1х”), для обоих параллельных ветвей генерируются кодовые символы Н₀(D), H₁(D). Эта особенность отчасти объясняется, в целом, повторяющимся характером сверточных кодов, а также использованием порождающих многочленов кодирования, в которых СБ и МБ заданы равными единице (т.е. в обоих многочленах G₀(D) и G₁(D) коэффициенты g₀ и g₈ равны 1). Аналогично, кодовые символы генерируются, когда кодер 100 действует по любой из диагональных ветвей схемы “бабочка” 155 (например, осуществляет переходы из “х0” в “1х” или из “х1” в “0x”).

Согласно вышесказанному, модуль 150 ССВ вычисляет метрики tm_0x, tm_1x конечных состояний. Логическая схема 150 ССВ сохраняет метрики sm_x0, sm_x1 исходных состояний, которые связаны с вероятностью того, что принятый набор кодовых символов ведет к исходным состояниям “х0” и “х1”. Согласно фиг.1В, приняв набор кодовых символов, модуль 140 метрики ветви вычисляет значения метрики bm_ij, ветви. Модуль 150 ССВ “суммирует” метрику bm_ij, ветви, соответствующую каждому из двух переходов, ведущих к конкретному конечному состоянию, с соответствующей метрикой sm_x0, sm_x1 состояния. Метрики bm_ij, ветви выражают условную вероятность перехода из конкретного исходного состояния в конкретное конечное состояние. Метрика bm_ij ветви указывает, насколько близко принятые кодовые символы совпадают с гипотетическими кодовыми символами H₀(D), H₁(D) 125, сформированными модулем 150 ССВ, а метрика ветви указывает, насколько точно принятые кодовые символы совпадают с Значение метрик bm_ij, ветви зависит только от расстояния между принятой парой символов и гипотетической парой символов H₀(D), H₁(D).

Для каждого из двух конечных состояний модуль ССВ 150 сравнивает суммы пар метрика исходного состояния/метрика ветви, для исходных состояний из которых можно придти в конечное состояние. Затем, модуль 150 ССВ “выбирает” наиболее правдоподобный из переходов в каждое конечное состояние, представленный наименьшей суммой метрик, и присваивает конечному состоянию полученную величину в качестве метрики tm_0x, tm_1x конечного состояния.

Согласно вышесказанному, логическая схема модуля 150 ССВ суммирует метрику bm_ij, ветви с метрикой sm_x0, sm_x1 исходного состояния для каждого из двух переходов, ведущих в конечное состояние, и принимает решение, что наиболее правдоподобный путь в это конечное состояние пришел от перехода, который дает меньшую сумму метрик. Затем, выбирают меньшую сумму метрик и назначают ее новой метрикой tm_0x, tm_1x конечного состояния. Модуль 150 ССВ также сохраняет метрики состояний (т.е. стоимость, связанная с наиболее вероятным путем, ведущим в каждое конечное состояние) в ОЗУ 145 состояний. Согласно фиг.1В, выбор наименьшей суммы метрик приводит к сохранению одноразрядной величины, именуемой битом решения, в памяти путей в модуле 160 памяти обратной цепи. Бит решения, который представляет собой МР метрики выигрышного исходного состояния, указывает, какой из двух переходов был выбран.

Модуль 160 памяти обратной цепи сохраняет бит решения, соответствующий наиболее вероятному переходу в каждое конечное состояние. Для кодера 100, имеющего ограничительную длину К=9, генерируется 2^к-l или 256 битов решений, каждый из которых соответствует одному из 256 возможных состояний кодера 100. После генерации и сохранения матрицы всей этой информации для заданного количества состояний модуль 160 обратной цепи начинает с состояния, которое с наибольшим правдоподобием возглавляет правильный путь (т.е. состояния, которое из всех, соответствующих самому последнему интервалу времени, имеет наименьшую стоимость). После этого модуль 160 обратной цепи осуществляет обратный проход по цепи, считывая последние Р×256 (т.е. P×2^к-l) битов решения, чтобы выбрать Р битов, где Р - эффективная глубина обратной цепи памяти путей. Поскольку биты решения выражают наиболее правдоподобную гипотезу о множестве битов, прошедших через кодер 100, они являются наилучшими данными, которые может выдать декодер. В результате, чем глубже в историю решений погружается цепь, тем с большим правдоподобием полученный путь сливается с правильным путем. Таким образом, чем больше глубина Р обратной цепи, тем выше качество работы декодера, но тем больше задержки на конвейере и памяти. Поэтому глубина Р обратной цепи, в общем случае, должна превосходить ограничительную длину К кодера 100 в 3-10 раз. Для кодера с К=9 глубину Р обратной цепи обычно задают равной 64.

Цикл обработки ССВ задает период, в течение которого модуль 150 ССВ вычисляет новые метрики tm_0x, tm_1x конечного состояния для заданного количества принятых кодовых символов. Для сверточного кода со скоростью 1/2 каждая пара принятых кодовых символов требует 1 цикл обработки для вычислений метрики. Длина цикла обработки равна количеству тактов, необходимых для осуществления операций ССВ по схеме “бабочка” над всеми состояниями кодера для двух наборов принятых символов. Например, декодеру Витерби, имеющему одну схему “бабочка” ССВ, что отражено на фиг.2, в общем случае, требуется 128 тактов на каждый принятый кодовый символ для осуществления операций над всеми 256 состояниями кодера 100. Для повышения скорости обработки можно использовать массив схем “бабочка” ССВ той или иной архитектуры, что позволяет осуществлять один цикл обработки за меньшее количество тактов за счет применения множественных схем “бабочка” ССВ.

Примером такой архитектуры является массив 300 схем “бабочка” ССВ размерности 8×1, изображенный на фиг.3. Массив 300 обеспечивает 8-кратное увеличение скорости обработки за счет параллельного использования 8 модулей 155 схем “бабочка” ССВ. Для набора принятых кодовых символов массив 300 схем “бабочка” размерности 8×1 задействует все 8 модулей 155 схем “бабочка” для считывания 16 исходных состояний и вычисления 16 соответствующих метрик tm_0x и tm_1x конечных состояний за один такт. Согласно вышесказанному, модуль 155 ССВ принимает метрику состояния для каждого из исходных состояний и метрики bm_ij, ветви для каждого из четырех возможных переходов. Метрика bm_ij, ветви зависит только от значения принятой пары кодовых символов и гипотетической пары символов H₀(D), H₁(D) или и является мерой расстояния между ними. Величина “X”, будучи составной частью двоичного представления исходного и конечного состояний, изображенных на фиг.3, представляет четырехразрядный групповой символ (т.е. Х=[Х0,Х1,Х2,Х3]), который регистрирует все 16 тактов, пробегая значения от 0 до 15. Таким образом, для двух наборов принятых кодовых символов, массив 300 схем “бабочка” размерности 8×1 вычисляет метрики tm_0x, tm_1x конечных состояний для всех 256 возможных состояний кодера 100 за 32 такта (т.е. по 16 тактов на каждый принятый кодовый символ).

Недостатком архитектуры массива 300 размерности 8×1 является то, что для каждого набора принятых кодовых символов необходимо считывать 16 метрик исходного состояния и одновременно генерировать необходимые метрики ветви в каждом из 16 тактов. Таким образом, для осуществления операций на массиве 300 бабочек размерности 8×1 требуется очень большой объем памяти.

Другим вариантом архитектуры массива является массив 400 схем “бабочка” ССВ размерности 4×2, изображенный на фиг.4. Массив 400 схем “бабочка” ССВ размерности 4×2 обеспечивает такое же увеличение скорости, что и массив 300 размерности 8×1, но за счет 2 наборов из 4 параллельно действующих модулей 155 схем “бабочка” ССВ. Массив 400 решает проблему объема памяти за счет временного сохранения метрик tm_0x, tm_1x промежуточных конечных состояний. Например, за один такт первый каскад массива 400 считывает 8 исходных состояний и вычисляет 8 соответствующих метрик tm_0x, tm_1x конечных состояний. Однако массив 400 не сразу сохраняет метрики tm_0x, tm_1x промежуточных конечных состояний. Напротив, в том же такте массив 400 осуществляет перестановку промежуточных конечных состояний для подачи их в качестве исходных состояний на второй каскад, а затем вычисляет 8 соответствующих метрик tm_0x, tm_1x конечных состояний для следующего набора принятых кодовых символов. Таким образом, подобно массиву 300 8×1, массив 400 способен вычислять метрики tm_0x, tm_1x конечных состояний для двух наборов принятых кодовых символов в течение 32 тактов.

Массив 400 схем “бабочка” ССВ 4×2 обладает тем преимуществом, что позволяет уменьшить объем памяти состояний модуля 150 ССВ, поскольку метрики промежуточных конечных состояний (т.е. метрики tm_0x, tm_1x конечных состояний первого каскада) не требуется считывать из памяти состояний модуля 150 ССВ или записывать в нее. Напротив, значения промежуточных конечных состояний комбинаторно переходят на следующий каскад, что позволяет избегать задержек и минимизировать необходимый объем памяти.

Однако массив 400 схем “бабочка” ССВ 4×2 также имеет свои ограничения. Например, преимущество снижения объема памяти состояний непосредственно обусловлено тем, что массив 400 осуществляет 2 каскада вычислений ССВ 150 за один такт. Этот критический путь может быть значительным ограничением в отношении более высоких тактовых частот.

Кроме того, как для массива 300 схем “бабочка” ССВ размерности 8×1, так и для массива 400 схем “бабочка” ССВ размерности 4×2 существует проблема производительности в отношении операции обратной цепи. Согласно вышесказанному, модуль 160 обратной цепи предназначен для сохранения битов решения, порожденных массивом ССВ, и для восстановления обратной цепи сохраненных битов решения для порождения декодированных битов решения. Для кодера с ограничительной длиной К=9 (например, кодера 100) массив ССВ в декодере генерирует 2^K-1 или 256 битов решения для каждого набора принятых кодовых символов (т.е. по 1 биту решения для каждого из 256 возможных состояний кодера), и модуль 160 памяти обратной цепи обычно имеет глубину обратной цепи в памяти путей, составляющую Р=64 блока.

После 32 циклов обработки, в каждом из которых осуществляется вычисление метрик конечных состояний для двух наборов принятых символов, модуль 160 обратной цепи начинает с самого последнего цикла обработки (например, самого правого блока памяти В₀ из 64 блоков памяти), согласно фиг.5А. Модуль 160 обратной цепи выявляет среди 256 битов решения, содержащихся в блоке В₀ памяти обратной цепи, бит решения R₀, соответствующий состоянию с наименьшим значением метрики. Это состояние определяется как наилучшее состояние и имеет 8-разрядный адрес BS₀, что показано на фиг.5В. Модуль 160 обратной цепи считывает значение бита решения наилучшего состояния, после чего вводит это значение в адрес, сдвигая влево в BS₀ младший разряд (т.е. bs₀), согласно фиг.5В. На фиг.5В также показано, что значения других разрядов в адресе BS₀ (т.е. bs₆, bs₅, bs₄, bs₃, bs₂, bs₁) также смещаются влево, что приводит к потере в BS₀ старшего разряда (т.е. bs₇) и формированию нового адреса BS₁. Согласно фиг.5А, BS₁ представляет собой адрес значения R₁ наилучшего состояния в блоке B₁ памяти обратной цепи. Затем, модуль 160 обратной цепи считывает значение бита решения, соответствующего адресу BS₁, и вставляет со сдвигом влево это значение в адрес BS₁, порождая новый адрес BS₂, соответствующий наилучшему состоянию в блоке В₂ памяти обратной цепи.

Эта операция считывания и вставки со сдвигом влево повторяется до тех пор, пока не будут обработаны все блоки памяти обратной цепи (т.е. Р=64 блока). В целом, операция обратной цепи предусматривает операции считывания в количестве, равном длине Р обратной цепи, поэтому, в данном случае, для обратного прохождения нужного пути и порождения декодированных битов решения требуется 64 операции считывания. Однако столь большое количество операций считывания может снижать эффективность и производительность процесса декодирования.

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

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

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

Прилагаемые чертежи, являющиеся неотъемлемой частью описания изобретения, иллюстрируют вариант осуществления изобретения и, совместно с описанием, поясняют задачи, преимущества и принципы изобретения. На чертежах:

фиг.1А - схема действия сверточного кодера с К=9 и скоростью 1/2;

фиг.1B - блок-схема системы, на которой изображены модули ССВ и обратной цепи;

фиг.2 - диаграмма переходов, иллюстрирующая операцию ССВ по схеме “бабочка”;

фиг.3 - диаграмма переходов, изображающая массив 8×1 схем “бабочка” ССВ;

фиг.4 - диаграмма переходов, изображающая массив 4×2 схем “бабочка” ССВ;

фиг.5А, 5В - функциональные диаграммы операции обратной цепи;

фиг.6А, 6В - схемы, изображающие вариант осуществления настоящего изобретения.

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

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

Вариант осуществления настоящего изобретения изображен на фиг.6А, 6В. Вариант осуществления предусматривает использование массива 600 схем “бабочка” ССВ размерности 8×1, содержащего 8 параллельных модулей 155 схем “бабочка” ССВ для обеспечения 8-кратного увеличения скорости обработки. В отличие от других попыток добиться такого увеличения, массив 600 функционирует в течение разных тактов, что позволяет снизить необходимый объем памяти и, одновременно, ограничить количество вычислений, выполняемых за один такт.

Согласно фиг.6А, массив 600 использует 8 модулей 155 схем “бабочка” на протяжении четного такта для считывания очередной совокупности из 16 исходных состояний, идентифицируемой 4-разрядным счетчиком X. Затем, массив 600 вычисляет 16 соответствующих метрик tm_0x, tm_1x для текущего уровня решетки. После четного такта (т.е. в течение нечетного такта) массив 600 использует конечные состояния четного такта в качестве исходных состояний нечетного такта для следующего уровня решетки. Поэтому массив 600 использует значения tm_0x, tm_1x метрик конечных состояний четного такта в качестве значений sm_x0, sm_x1 метрик исходных состояний нечетного такта. Затем, массив 600 вычисляет метрики конечных состояний нечетного такта tm_0x, tm_1x в соответствии со значениями sm_x0, sm_x1 метрики для соответствующего уровня решетки.

Таким образом, для полной обработки двух наборов принятых символов, генерированных кодером с К=9 с помощью модифицированного массива 600 схем “бабочка” ССВ размерности 8×1, изображенного на фиг.6А, требуется 32 такта. В течение четных тактов массив 600 считывает очередную совокупность из 16 состояний, идентифицируемую 4-разрядным счетчиком Х с приращением, и вычисляет 16 соответствующих метрик tm_0x, tm_1x конечных состояний для первого набора принятых символов. В течение нечетных тактов массив 600 использует конечные состояния четного такта в качестве новых исходных состояний и вычисляет метрики tm_0x, tm_1x конечных состояний нечетного такта для второго набора принятых символов. Поэтому массив 600 в течение одного такта осуществляет только один уровень ССВ, тем самым преодолевая проблемы вычисления многоуровневого ССВ за один такт, присущие массиву 400 размерности 4×2.

На фиг.6В показана схема 650 декодера Витерби, поддерживающая модифицированный массив 600 схем “бабочка” ССВ размерности 8×1, изображенный на фиг.6А. Метрики sm_x0, sm_x1 исходных состояний для всех состояний сохраняются в ОЗУ 145 состояний. В иллюстративных целях начнем описание работы схемы 650 декодера Витерби с операции считывания из ОЗУ 145 состояний в течение четных тактов. Специалистам в данной области очевидно, что описание этого варианта осуществления также можно начать со считывания из ОЗУ 145 состояний в течение нечетных тактов. Аналогично, все операции считывания могут осуществляться в ходе нечетных тактов, а все операции записи могут осуществляться в ходе четных тактов или наоборот.

Поэтому в ходе четных тактов мультиплексор МУКС 670 настроен на выбор информации метрики исходного состояния для 16 последовательных состояний из ОЗУ 145, соответствующей первому набору принятых кодовых символов. Информация исходного состояния поступает непосредственно на модуль 150 ССВ, который содержит массив 600 размерности 8×1. Затем, массив 600 вычисляет соответствующие 16 метрик tm_0x, tm_1x конечных состояний, которые вновь поступают на ОЗУ 145 состояний и МУКС 670. Вычисленная информация конечного состояния затем поступает на регистр 680 для временного хранения информации конечного состояния. Временное хранение информации конечного состояния в регистре 680 позволяет массиву 600 обходиться без повторного сохранения информации состояния в памяти, тем самым снимая проблему объема памяти, характерную для массива 300 размерности 8×1.

В течение нечетных тактов мультиплексор МУКС 670 выбирает информацию метрики конечного состояния, вычисленную в течение предыдущего такта, содержащуюся в регистре 680. Затем, эта информация метрики конечного состояния используется в массиве 600 размерности 8×1 в качестве новых метрик sm_x0, sm_x1 исходных состояний. Затем, массив 600 обрабатывает информацию метрики исходного состояния, чтобы генерировать информацию метрики конечного состояния, соответствующую второму набору принятых кодовых символов. Информация метрики конечного состояния затем сохраняется в ОЗУ 145 состояний, чтобы использоваться в качестве метрик исходных состояний в течение следующей итерации. Для первого и второго наборов принятых кодовых символов этот процесс повторяется в течение 32 тактов для генерации 256 битов решения для каждого из двух наборов принятых символов. По завершении 32 тактов схема 650 декодера Витерби начинает процесс сначала, для следующих двух наборов принятых кодовых символов.

Схема 650 декодера Витерби также повышает производительность операции обратной цепи за счет уменьшения количества операций считывания, необходимого для генерации декодированных битов решения. Согласно вышесказанному, модуль 160 обратной цепи предназначен для сохранения битов решения, генерированных массивом ССВ. Кроме того, за два такта (т.е. в течение четного и нечетного тактов) модифицированный массив 600 размерности 8×1 генерирует 32 бита решения. Схема 650 декодера Витерби предусматривает сохранение этих 32 битов решения в виде одного 32-разрядного слова памяти, и, таким образом, биты решения, генерированные в течение четного и нечетного тактов, сохраняются в одном и том же слове памяти.

Итак, как было указано выше в связи с операциями обратной цепи, сначала, для задания начальной точки обратного прохождения цепи во времени, используется наилучшее состояние, идентифицирующее состояние с наименьшей метрикой, из последнего цикла обработки (т.е. значение бита решения наилучшего состояния). Поскольку слово памяти содержит 32 бита, существует 16 слов на цикл обработки (в силу 2 наборов принятых кодовых символов), и каждое из 32-разрядных слов памяти имеет уникальный 8-разрядный адрес. Один вариант осуществления предусматривает использование 4 битов адреса наилучшего состояния для выбора слова памяти, подлежащего считыванию, а 4 других битов адреса наилучшего состояния - для определения 16 битов из 32-разрядного слова памяти, подлежащих считыванию. В частности, если наилучшее состояние ВS₀ имеет 8-разрядный адрес (bs₇, bs₆, bs₅, bs₄, bs₃, bs₂, bs₁, bs₀), то, согласно этому варианту осуществления, биты (bs₅, bs₄, bs₃, bs₂) предназначены для выбора конкретного слова памяти в блоке памяти В₀, а биты (bs₇, bs₆, bs₁, bs₀) - для выбора бита решения R₀ наилучшего состояния. Адрес BS₁ нового наилучшего состояния формируется путем ввода бита решения R₀ наилучшего состояния в ВS₀ в качестве младшего бита со сдвигом влево (bs₆, bs₅, bs₄, bs₃, bs₂, bs₁, bs₀, R₀).

Поскольку вычисления ССВ производятся над двумя наборами принятых символов, исходные состояния, из которых можно придти в конечное состояние в соответствии с только что считанным битом решения, имеют свои собственные биты решения, которые хранятся в том же самом 32-разрядном слове памяти. Таким образом, вариант осуществления предусматривает выбор битов (bs₆, bs₁, bs₀, R₀) для выбора бита решения R₁ следующего наилучшего состояния из второй половины 32-разрядного слова памяти. Итак, бит решения наилучшего состояния выбирают из половины битов 32-разрядного слова памяти, причем эти выбранные биты позволяют определить, какой бит решения из другой половины 32-разрядного слова памяти является следующим битом решения наилучшего состояния. Благодаря этому, количество операций считывания, необходимое для правильного прохождения нужного пути в обратном направлении цепи и генерации декодированных битов решения, снижается с коэффициентом 2. Таким образом, для модуля 160 обратной цепи, имеющего глубину памяти путей Р=64 блока памяти, требуется только 32 операции считывания.

Вышеприведенное описание предпочтительных вариантов осуществления настоящего изобретения носит иллюстративный характер, но не предназначено для исчерпывающего охвата или ограничения изобретения конкретной изложенной формой. Вышеописанные идеи изобретения предусматривают возможность модификаций и вариаций, которые также могут быть предложены в ходе практического применения изобретения. Например, архитектуру раскрытых здесь вариантов осуществления можно легко расширить до массива размерности 16×1 или массива размерности 32×1, где за один такт можно генерировать 32 или 64 состояния. Дополнительно, вместо работы на двух наборах принятых символов можно предложить варианты осуществления, предусматривающие работу на нескольких наборах принятых символов. Таким образом, следует подчеркнуть, что объем изобретения определяется прилагаемой формулой изобретения.

Изобретение относится к приложениям алгоритма Витерби и, в частности, к усовершенствованным системе и способу осуществления высокоскоростной операции сложения/сравнения/выбора (ССВ) по схеме “бабочка” в реализации алгоритма Витерби. Его использование позволяет получить технический результат в виде повышения эффективности при осуществлении высокоскоростных операций ССВ по схеме “бабочка” в реализации алгоритма Витерби. Технический результат достигается за счет того, что система содержит первый элемент памяти для хранения совокупности метрик исходных состояний, мультиплексор, способный выбирать между первым и вторым действующими путями на основании четных и нечетных тактов, механизм ССВ, который вычисляет метрики конечных состояний для каждой из метрик состояний. Второй элемент памяти, подключенный к механизму ССВ и мультиплексору, используется для временного хранения метрик конечных состояний. Мультиплексор выбирает первый действующий путь в течение четных тактов и подает метрики исходных состояний, извлеченные из первого элемента памяти, на механизм ССВ для порождения метрик конечных состояний. В течение нечетных циклов мультиплексор выбирает второй действующий путь для доступа ко второму элементу памяти и использования ранее вычисленных метрик конечных состояний в качестве метрик промежуточных исходных состояний. 2 с. и 19 з.п. ф-лы, 6 ил.

1. Способ осуществления операции сложения(сравнения)выбора по схеме “бабочка” для реализации алгоритма Витерби, способ содержит этапы, на которых считывают в течение четных тактов совокупность метрик исходных состояний из первого элемента памяти, соответствующую первому набору принятых символов, вычисляют метрику конечного состояния для каждой из метрик исходных состояний, временно сохраняют метрики конечных состояний во втором элементе памяти, определяют, какая из метрик конечных состояний имеет наименьшее значение, сохраняют заданный логический бит, соответствующий наименьшему значению метрики конечного состояния, в третьем элементе памяти считывают в течение нечетных тактов метрики конечных состояний из второго элемента памяти и используют считанные метрики конечных состояний в качестве совокупности метрик промежуточных исходных состояний, соответствующих второму набору принятых символов, вычисляют метрику промежуточного конечного состояния для каждой из метрик промежуточных исходных состояний, определяют, какая из метрик промежуточных конечных состояний имеет наименьшее значение, сохраняют заданный логический бит, соответствующий наименьшему значению метрики промежуточного конечного состояния, в третьем элементе памяти.2. Способ по п.1, по которому первый и второй наборы принятых символов закодированы с использованием ограничительной длины К.3. Способ по п.2, по которому операцию сложения (сравнения)выбора по схеме “бабочка” осуществляют до тех пор, пока не достигнут каждого из 2^K-1 конечных состояний для каждого из первого и второго наборов принятых символов.4. Способ по п.3, по которому операцию сложения(сравнения)выбора по схеме “бабочка” осуществляют посредством структуры 8×1 схем “бабочка” сложения(сравнения)выбора.5. Способ по п.4, по которому совокупность метрик исходных состояний состоит из метрик для набора из 16 последовательных исходных состояний, причем набор из 16 последовательных исходных состояний последовательно выбирают в течение возрастающих четных тактов.6. Способ по п.5, по которому на этапе вычисления метрик конечных состояний суммируют метрики исходных состояний с метрикой ветви, соответствующей каждому из двух возможных переходов, сравнивают каждую из сумм метрик исходных состояний и метрик ветвей и выбирают и назначают наименьшую сумму метрикой конечного состояния.7. Способ по п.6, по которому на этапе вычисления метрик промежуточных конечных состояний суммируют метрики промежуточных исходных состояний с метрикой ветви, соответствующей каждому из двух возможных переходов, сравнивают каждую из сумм метрик промежуточных исходных состояний и метрик ветвей и выбирают наименьшую сумму и назначают ее метрикой промежуточного конечного состояния.8. Способ по п.7, по которому операцию сложения(сравнения)выбора по схеме “бабочка” используют для декодирования данных, подвергнутых сверточному кодированию.9. Способ по п.8, по которому в модуле памяти обратной цепи предусмотрен третий элемент памяти, содержащий совокупность блоков памяти, в каждом из которых хранится заданный логический бит для каждого четного и нечетного такта.10. Способ по п.8, по которому дополнительно осуществляют операцию обратной цепи для создания совокупности значений декодированных битов.11. Способ по п.10, по которому при осуществлении операции обратной цепи идентифицируют для самого последнего из блоков памяти в модуле памяти обратной цепи заданный логический бит имеющий наименьшее значение, связывают логический бит наименьшего значения с конкретным адресом, считывают заданный логический бит и переносят значение логического бита наименьшего значения в младший разряд конкретного адреса, сдвигая все значения в конкретном адресе на один разряд влево, для нахождения следующего конкретного адреса, соответствующего следующему блоку памяти в модуле памяти обратной цепи.12. Система для осуществления операции сложения(сравнения)выбора по схеме “бабочка” для реализации алгоритма Витерби, система содержит первый элемент памяти для хранения совокупности метрик исходных состояний, мультиплексор, подключенный к первому элементу памяти для выбора первого действующего пути в течение четных тактов и для выбора второго действующего пути в течение нечетных тактов, второй элемент памяти, подключенный к мультиплексору для временного хранения метрик конечных состояний, механизм сложения(сравнения)выбора, подключенный ко второму элементу памяти и мультиплексору для вычисления метрики конечного состояния для каждой из метрик исходных состояний и третий элемент памяти для хранения заданного логического бита, соответствующего вычисленной метрике конечного состояния, имеющей наименьшее значение, при этом мультиплексор выбирает упомянутый первый действующий путь в течение четных тактов и выдает метрики исходных состояний из первого элемента памяти на механизм сложения(сравнения)выбора, чтобы генерировать метрики конечных состояний, соответствующие первому набору принятых символов, и мультиплексор выбирает второй действующий путь в течение нечетных тактов, чтобы считывать метрики конечных состояний из второго элемента памяти и использовать считанные метрики конечных состояний в качестве метрик промежуточных исходных состояний, чтобы механизм сложения(сравнения)выбора генерировал на основании метрик промежуточных исходных состояний метрики промежуточных конечных состояний, соответствующие второму набору принятых символов.13. Система по п.12, в которой первый и второй наборы принятых символов закодированы с использованием ограничительной длины К.14. Система по п.13, в которой операция сложения(сравнения)выбора по схеме “бабочка” осуществляется до тех пор, пока не будет посещено каждое из 2^K-1 конечных состояний для каждого из первого и второго наборов принятых символов.15. Система по п.14, в которой операция сложения(сравнения)выбора по схеме “бабочка” осуществляется посредством структуры 8×1 схем “бабочка” сложения(сравнения)выбора.16. Система по п.15, в которой совокупность метрик исходных состояний состоит из метрик для набора из 16 последовательных исходных состояний, причем выбор набора из 16 последовательных исходных состояний осуществляется последовательно в течение возрастающих четных тактов.17. Система по п.12, в которой механизм сложения (сравнения)выбора осуществляет операцию сложения (сравнения)выбора, суммируя метрики исходных состояний с метрикой ветви, соответствующей каждому из двух возможных переходов, сравнивая каждую из сумм метрик исходных состояний и метрик ветвей и выбирая наименьшую сумму и назначая ее метрикой конечного состояния.18. Система по п.17, в которой операция сложения (сравнения)выбора по схеме “бабочка” используется для декодирования данных, подвергнутых сверточному кодированию.19. Система по п.18, в которой в модуле памяти обратной цепи предусмотрен третий элемент памяти, содержащий совокупность блоков памяти, в каждом из которых хранится заданный логический бит для каждого четного и нечетного такта.20. Система по п.19, в которой модуль памяти обратной цепи генерирует совокупность значений декодированных битов.21. Система по п.20, в которой модуль памяти обратной цепи идентифицирует для самого последнего из блоков памяти заданный логический бит, имеющий наименьшее значение, связывает логический бит наименьшего значения с конкретным адресом, считывает заданный логический бит и переносит значение логического бита наименьшего значения в младший разряд конкретного адреса, сдвигая все значения в конкретном адресе на один разряд влево для нахождения следующего конкретного адреса, соответствующего следующему блоку памяти в модуле памяти обратной цепи.