ДЕКОДЕР ВИТЕРБИ Российский патент 1999 года по МПК H03M13/12 

Область техники
Настоящее изобретение относится к декодеру Витерби (Viterby) и, в частности, к декодеру Витерби, имеющему множество блоков суммирования-сравнения-выбора для суммирования, сравнения и выбора метрики разветвлений и метрики состояний и вывода декодированных данных из сигнала выбора, представляющего оптимальный путь.

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

Известный декодер Витерби (фиг. 1) имеет блок вычисления метрики разветвлений 100, блок ACS (суммирования-сравнения-выбора) 110, память метрики состояния 120, память пути 130 и логический блок 140.

Блок вычисления метрики разветвлений 100 вычисляет евклидово расстояние или расстояние Хэмминга между принятыми данными и кодовым словом, подлежащим передаче. Блок ACS 110 суммирует и сравнивает метрики разветвлений, рассчитанные в блоке вычисления метрик разветвлений 100, и метрики состояний и выбирает оставшуюся ветвь для каждого состояния, которая наиболее близка к кодовой последовательности принятых данных. То есть в блоке ACS 110 вычисленные метрики разветвлений суммируются с метриками предыдущих состояний в сумматоре в соответствии с решетчатой диаграммой, получаемые метрики текущих состояний сравниваются в компараторе и в селекторе выбираются метрики малых состояний, где выбранные метрики состояний хранятся в памяти метрик состояний 120. Здесь отобранные сигналы выбора пути хранятся в памяти пути 130 после прохождения через логический блок отслеживания пути 140. Между тем, память метрики состояний 120 хранит метрику текущего состояния. Логический блок отслеживания пути 140 отслеживает информацию о пути, хранящуюся в памяти пути 130, для поиска состояния, имеющего наибольшее правдоподобие, находит самый близкий путь к данным, посланным из передающего кодера (не показан), и выводит декодированные данные. В системе, использующей способ связи с многостанционным доступом с кодовым разделением каналов (СДМА), применяется декодер Витерби, содержащий один блок ACS. В нем обычно используется свернутое кодовое слово с длиной кодового ограничения К=9, и таким образом количество состояний составляет 2^9-1, то есть 256. Следовательно, один блок ACS 110 выполняет суммирование, сравнение и выбор из 256 состояний для одного символа. В результате необходимо выполнять операции для множества каналов, что ограничивает скорость декодирования.

Сущность изобретения
Целью настоящего изобретения является создание декодера Витерби, использующего алгоритм Витерби для одновременной обработки множества каналов путем использования множества блоков суммирования-сравнения-выбора (ACS) для суммирования, сравнения и выбора метрик разветвлений и метрик состояний принимаемых данных.

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

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

Подробное описание предпочтительного варианта изобретения
Декодер Витерби, согласно изобретению, содержит блок вычисления метрик разветвлений 210 (фиг. 2) для приема кода, для вычисления каждой метрики разветвлений, исходя из полученного кода, и вывода восьми метрик разветвлений BM0, BM1, BM2, BM3, BM4, BM5, BM6 и BM7, распределитель метрик разветвлений 220 для метрик, поступающих от блока вычисления метрик разветвлений 210 на EBM_U, EBM_L, OBM_U и OBM_L, ACS блоки с первого по четвертый 232, 234, 236 и 238 для суммирования и сравнения метрик разветвлений, выводимых из распределителя метрик разветвлений 220, и метрик состояний, выводимых из памяти метрики состояния 240, выбора оптимального пути и вывода новых метрик состояний, память метрик состояния 240 для хранения новых метрик состояний и распределения четырех метрик состояний в виде ESM_U, ESM_L, OSM_U и OSM_L по блокам ACS с первого по четвертый 232, 234, 236 и 238, логический блок отслеживания пути 250 для отслеживания информации о выборе пути, отбираемой в блоках ACS с первого по четвертый 232, 234, 236 и 238, поиска самого близкого пути принятых данных и вывода декодированных данных, и память пути 260 для хранения сигнала выбора пути, выбираемого в логическом блоке отслеживания пути 250.

В описываемом варианте воплощения изобретения декодирование Витерби задается со скоростью кода 1/3 и длиной кодового ограничения, равной 9. На фиг. 5 показаны переходы для 256 состояний при декодировании Витерби. Например, 0 и 1 обозначают номер предшествующего состояния. 0 и 128 обозначают номер текущего состояния. 000 и 111 обозначают верхнее кодовое слово CW_U. 111 и 000 обозначают нижнее кодовое слово CW_L.

Блок вычисления метрик разветвлений 210 (фиг. 2) вычисляет евклидово расстояние или расстояние Хемминга между полученными данными и передаваемым кодовым словом. То есть вычисляется евклидово расстояние между полученными данными и кодовым словом (000, 001, ..., 111) и выводятся BM0, BM1, BM2, BM3, BM4, BM5, BM6 и BM7. Распределитель метрик разветвлений 220 распределяет метрики разветвлений, вычисленные исходя из полученных данных в виде EBM_U, EBM_L, OBM_U и OBM_L. Здесь E и O представляют четные и нечетные численные данные, a BM_U и BM_L расстояния соответственно между верхним кодовым словом CW_U и нижним кодовым словом CW_L (фиг. 5) и полученными данными. Четыре ACS блока 232 - 238 получают соответствующие метрики разветвлений, распределяемых в распределителе метрик разветвлений 220. Память метрик состояний 240 хранит метрики новых состояний, выводимых из блоков ACS с первого по четвертый 232 - 238, и распределяет четыре метрики состояний ESM_U, ESM_L, OSM_U и OSM_L к блокам ACS с первого по четвертый 232 - 238. В декодере Витерби, использующем алгоритм Витерби, если скорость кода составляет 1/3 (информационные биты/кодовые биты) и длина ограничена до 9, то количество состояний составляет 2^9-1, т.е. 256. Каждый ACS блок выполняет 64 (256/4) операций на одной полученной единице данных. Следовательно, первый и второй ACS блоки 232 и 234 выполняют операции для четных состояний из 256 состояний, в то время как третий и четвертый ACS блоки 236 и 238 выполняют операции для нечетных состояний из 256 состояний. То есть первый ACS блок 232 получает четыре сигнала (EBM_U, EBM_L, ESM_U и ESM_L) метрик разветвлений и состояний и выполняет операции для одной половины четных верхних состояний 0, 2, 4, . . . .., 126, а второй ACS блок 234 получает четыре сигнала (EBM_U, EBM_L, ESM_U и ESM_L) метрик разветвлений и состояний и выполняет операции для другой половины четных нижних состояний 128, 130, 132, ..., 254. Третий ACS блок 236 получает четыре сигнала (OBM_U, OBM_L, OSM_U и OSM_L) метрик разветвлений и состояний и выполняет операции для одной половины нечетных верхних состояний 1, 3, 5, ..., 127, а четвертый ACS блок 238 получает четыре сигнала (OBM_U, OBM_L, OSM_U и OSM_L) метрик разветвлений и состояний и выполняет операции для другой половины нечетных верхних состояний 129, 131, 133, ..., 255. Следовательно, ACS с первого по четвертый 232 - 238 получают метрики разветвлений и состояний параллельно и одновременно выполняют операции для состояний (0, 128, 1, 129), (2, 130, 3, 131), ..., (126, 254, 127, 255) (фиг. 5). Чтобы последовательно выполнить операции, метрики разветвлений и метрики состояний вводятся в блоки ACS следующим образом. BM_U первого ACS блока 232 равна BM_L второго ACS блока 234, BM_L первого ACS блока 232 равна BM_U второго ACS блока 234, BM_U третьего ACS блока 236 равна BM_L четвертого ACS блока 238, а BM_L третьего ACS блока 236 равна BM_U четвертого ACS блока 238 (таблица ). Следовательно, метрики разветвлений, дающих переходы из состояний 0, 4, 8, ... , 240, 244, 248, 252 в состояния 0, 2, 4, 6, ... , 120, 122, 124, 126, принимаются через терминал BM_U первого ACS блока 232 и терминал BM_L второго ACS блока 234. Метрики разветвлений, дающих переходы из состояний 0, 4, 8, ... , 240, 244, 248, 252 в состояния 128, 130, 132, ... , 248, 250, 252, 254, принимаются через терминал BM_L первого ACS блока 232 и терминал BM_U второго ACS блока 234. Метрики разветвлений, дающих переходы из состояний 2, 6, 10, ..., 242, 246, 250, 254 в состояния 1, 3, 5, 7, ..., 121, 123, 125, 127, принимаются через терминал BM_U третьего ACS блока 236 и терминал BM_L четвертого ACS блока 238. Метрики разветвлений, дающих переходы из состояний 2, 6, 10, . . . , 242, 246, 250, 254 в состояния 129, 131, 133, ... , 249, 251, 253, 255, принимаются через терминал BM_L третьего ACS блока 236 и терминал BM_U четвертого ACS блока 238.

Кроме того, метрики разветвлений, передаваемых из состояний 0, 4, 8, 12, . .., 240, 244, 248, 252 в состояния 0, 2,4, 6,..., 120, 122, 124, 126, принимаются через терминал SM_U первого ACS блока 232. Метрики разветвлений, передаваемых из состояний 1, 5, 9, 13,..., 241, 245, 249, 253 в состояния 0, 2, 4, 6, ... , 120, 122, 124, 126, принимаются через терминал SM_L первого ACS блока 232. Метрики разветвлений, передаваемых из состояний 0, 4, 8, 12,. .., 240, 244, 248, 252, в состояния 128, 130, 132, 134, ... , 248, 250, 252, 254, принимаются через терминал SM_U второго ACS блока 234. Метрики разветвлений, передаваемых из состояний 1, 5, 9, 13, ... , 241, 245, 249, 253, в состояния 128, 130, 132, 134, ... , 248, 250, 252, 254, принимаются через терминал SM_L второго ACS блока 234.

Сигналы ENSM_U и ENSM_L, выдаваемые первым и вторым ACS блоками 232 и 234, являются выходными сигналами, представляющими метрики новых состояний для четных состояний, а сигналы EPS_U и EPS_L являются сигналами выбора пути для четных состояний. Сигналы ONSM_U и ONSM_L, выдаваемые третьим и четвертым ACS блоками 236 и 238, являются выходными сигналами, представляющими метрики новых состояний для нечетных состояний, а сигналы OPS_U и OPS_L являются сигналами выбора пути для нечетных состояний.

Сигналы выбора пути, выдаваемые ACS блоками с первого по четвертый 232 - 238, представляют собой данные, декодированные с помощью алгоритма Витерби посредством логического блока отслеживания пути 250 и памяти пути 260.

Распределитель метрик разветвлений 220 (фиг. 3) имеет контроллер 310, содержащий счетчик состояний 316, генератор сигнала выбора четного состояния 312, генератор сигнала выбора нечетного состояния 314 для приема тактового сигнала и сигнала сброса и вывода сигналов выбора четных состояний EC0, EC1 и EC2 и сигналов выбора нечетных состояний OC0, OC1 и OC2 и мультиплексоры 320 и 330 для выбора необходимых сигналов среди метрик разветвлений BM0, BM1, BM2, BM3, BM4, BM5, BM6 и BM7 с помощью сигналов выбора состояний, выдаваемых контроллером 310.

Как показано в таблице , четные метрики разветвлений EBM_U и EBM_L и нечетные метрики разветвлений OBM_U и OBM_L (фиг. 2) выбираются в каждой паре из метрик разветвлений BM0, BM1, BM2, BM3, BM4, BM5, BM6 и BM7, которые выводятся из распределителя метрик разветвлений 220 через четный и нечетный мультиплексоры 320 и 330 с использованием четных управляющих сигналов EC0, EC1 и EC2 и нечетных управляющих сигналов ОC0, ОC1, ОC2, которые соответственно выдаются контроллером 310 (фиг. 3) в виде сигналов управления выбором.

Четный и нечетный мультиплексоры 320 и 330 работают, как представлено в таблице . Здесь сигналы выбора C0, C1 и C2 мультиплексоров являются четными сигналами выбора EC0, EC1 и EC2 либо нечетными сигналами выбора ОC0, ОC1 и ОC2. Метриками разветвлений BM_U и BM_L выбираемых сигналами выбора C₀, C₁ и C₂, являются EBM_U, EBM_L или OBM_U, OBM_L.

Четные управляющие сигналы EC0, EC1 и EC2 и нечетные управляющие сигналы ОC0, ОC1 и ОC2, которые должны быть использованы в качестве сигналов выбора четного и нечетного мультиплексоров 320 и 330, выдаются соответственно генераторами сигналов выбора четных и нечетных состояний 312 и 314 контроллера 310.

Генераторы сигналов выбора четных и нечетных состояний 312 и 314 выдают соответствующие кодовые слова согласно порождающему уравнению сверточного кодера (не показано) с использованием значения счетчика состояний 316.

Таблица
C0 C1 C2 - (BM_U, BM_L)
0 0 0 - (BM₀, BM₇)
0 0 1 - (BM₁, BM₆)
0 1 0 - (BM₂, BM₅)
0 1 1 - (BM₃, BM₄)
1 0 0 - (BM₄, BM₃)
1 0 1 - (BM₅, BM₂)
1 1 0 - (BM₆, BM₁)
1 1 1 - (BM₇, BM₀)
Блок ACS (фиг. 4) содержит первый сумматор 418, второй сумматор 420, компаратор 422 и селектор 424.

Первый и второй сумматоры суммируют полученные метрики разветвлений и состояний и выводят значения данных A и B соответственно. Компаратор 422 сравнивает A с B, выводит 0 в качестве сигнала выбора пути, если данные A не больше, чем данные B, и выводит 1 в качестве сигнала выбора пути (PS), если данные A больше, чем данные B. В то же время селектор 424 получает данные A и B, выбирает одно из них в соответствии с сигналом выбора пути компаратора 422 и выводит выбранные данные в качестве метрики нового состояния (NSM).

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

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

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