УСТРОЙСТВО ВЫЧИСЛЕНИЯ МЕТРИК ПУТЕЙ ДЕКОДЕРА ВИТЕРБИ Российский патент 1994 года по МПК H03M13/12 

Изобретение относится к электросвязи и может быть использовано в цифровых системах передачи сверточным кодом для декодирования по алгоритму Витерби при реализации на технологии базовых матричных кристаллов (БМК).

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

Недостаток этого декодера заключается в том, что устройство вычисления метрик путей выполняет параллельную обработку принятой кодовой последовательности и содержит 2^ν каналов обработки, из-за чего не может быть реализовано на перспективной технологии БМК для ν = 4 и более. Экспоненциальный (по ν ) рост сложности устройства существенно ограничивает реализуемую величину ν и тем самым снижает помехоустойчивость декодера.

Наиболее близким к предлагаемому является устройство вычисления метрик путей [2] , содержащее два канала обработки, каждый из которых состоит из двух сумматоров, выходы которых подключены через блок сравнения и коммутатор метрик к вычислителю, второй вход которого связан с выходом блока нормированного порога, вход которого, соединенный с входом блока памяти метрик, подключен к выходу схемы ИЛИ, входы которой соединены с выходами вычислителей обоих каналов обработки, а выходы блока памяти метрик подключены к выходам соответствующих сумматоров. Два канала обработки вместо 2^ν каналов обеспечивают последовательную обработку метрик.

Недостатком прототипа является то, что оно ориентировано на программную реализацию с адресной организацией памяти метрик, выполненной на оперативных запоминающих устройствах (ОЗУ). Сложная система адресации плохо приспособлена для технологии БМК, собственно память и схема управления ею занимает неприемлемо большую часть кристалла, и для остальных блоков декодера места не остается. В прототипе предлагается также выполнять память метрик на параллельных регистрах, однако при ν ≥ 3 возникает проблема экспоненциального увеличения числа межсоединений на кристалле БМК. Это также делает невыполнимой задачу размещения электрической схемы декодера Витерби с высокой помехоустойчивостью на одном кристалле.

Цель изобретения - упрощение устройства для жесткой аппаратной реализации на БМК и, как следствие, повышение помехоустойчивости декодера.

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

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

Традиционные принципы организации памяти метрик основаны на применении либо многоразрядных ОЗУ, либо многоразрядных параллельных регистров. В первом случае экспоненциальный рост сложности ОЗУ и соответствующей схемы управления, а втором случае экспоненциальное увеличение числа межсоединений не позволяет реализовать на БМК декодер Витерби, достаточно сложный для обеспечения требуемой помехоустойчивости.

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

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

На фиг. 1 представлена структурная схема предлагаемого устройства, где 1-1 и 1-2 - первый и второй арифметические сумматоры, 2 - блоки сравнения, 3 - коммутаторы метрик, 4 - схема ИЛИ, 5 - блок нормированного порога, 6 - первый недвоичный сдвиговый регистр, 7 - второй недвоичный сдвиговый регистр, 8 - первый переключатель, 9 - третий недвоичный сдвиговый регистр, 10 - четвертый недвоичный сдвиговый регистр, 11 - второй переключатель, 12 - пятый недвоичный сдвиговый регистр, 13 - третий переключатель; на фиг. 2 изображен сверточный кодер в виде автомата Мура; на фиг. 3 - решетчатая диаграмма (состояний) кодера; на фиг. 4 показано соответствие между "бабочкой" (а) решетчатой диаграммы кодера и обрабатывающим узлом (б) ССВ; на фиг. 5-12 показаны процессы, протекающие в устройстве при полном цикле декодирования одной кодовой ветви; на фиг. 13 - временные диаграммы сигналов, управляющих процессом декодирования, показанным на фиг. 5-12, где а - тактовый сигнал, период которого равен полному циклу декодирования одного бита, б - тактовый сигнал первого и третьего недвоичных сдвиговых регистров; в - сигнал управления первым переключателем, г - тактовый сигнал второго недвоичного сдвигового регистра, д - сигнал управления вторым переключателем, е - тактовый сигнал четвертого недвоичного сдвигового регистра, ж - сигнал управления третьим переключателем, з - тактовый сигнал пятого недвоичного сдвигового регистра.

Устройство вычисления метрик декодера Витерби (фиг. 1) содержит два канала обработки, каждый из которых состоит из первого 1-1 и второго 1-2 сумматоров, младшие разряды которых подключены к соответствующим выходам блока вычисления метрик ветвей и являются входами устройства, блока 2 сравнения и коммутатора 3 метрик. Выходы коммутаторов 3 через схему ИЛИ 4 и блок 5 нормированного порога связаны со старшими разрядами всех сумматоров 1. Выходы первого сумматора 1-1 каждого канала обработки подсоединены к первому входу блока 2 сравнения и третьему входу коммутатора 3 метрик этого же канала обработки, а выходы второго сумматора 1-2 каждого канала обработки подсоединены к вторым входам блока 2 сравнения и коммутатора 3 метрик другого канала обработки. Первые входы коммутаторов 3 подключены к входам блоков 2 сравнения соответствующих каналов обработки и одновременно к выходам устройства, которые связаны с входами блока памяти путей декодеров. Управляющие входы сумматоров 1-1 и 1-2 первого канала обработки объединены и подключены к выходу первого недвоичного сдвигового регистра 6, вход которого подключен к выходу первого переключателя 8, первый вход которого непосредственно, а второй через второй недвоичный сдвиговый регистр 7 соединены с выходом коммутатора 3 первого канала обработки. Управляющие входы сумматоров 1-1 и 1-2 второго канала обработки объединены и подключены к выходу третьего недвоичного сдвигового регистра 9, вход которого подключен к выходу третьего переключателя 13. Первый вход последнего связан с выходом пятого недвоичного сдвигового регистра 12, вход которого подключен к выходу второго переключателя 11. Первый вход переключателя 11 соединен с выходом четвертого регистра 10, вход которого подсоединен к выходу коммутатора 3 метрик второго канала обработки и к вторым входам второго 11 и третьего 13 переключателей.

Для описания работы устройства в составе декодера Витерби сначала рассмотрим процесс кодирования сверточного кода. Сверточный кодер представлен на фиг. 4, а в виде четырехразрядного (К = 4) сдвигового регистра (автомата Мура, т.е. конечного цифрового автомата, выходы которого являются функцией его состояния). Состоянием кодера называют содержимое ν = К-1 разрядов его регистра сдвига, в нашем случае - это три информационных бита
i_t, i_t-1, i_t-2, хранящихся в разрядах кодера в момент времени t. По определению кодовым ограничением ν сверточного кода называют число ν = К - 1. В нашем примере ν = 3. Скорость кода R = k_o/n_o, поскольку при вводе k_o = 1 одного информационного бита i_t кодер генерирует n_o = 2 кодовых символа: Y_1t, Y_2t. Скорость передачи кодовой последовательности в этом случае в два раза больше, чем скорость передачи информационной последовательности. Кодовые символы появляются на выходах сумматоров по модулю два, входы которых подключены к предопределенным разрядам регистра сдвига. Конфигурация этих соединений описывается ( ν + 1)-разрядными двоичными последовательностями: G₁ = 1111, G₂ = 1011, которые называют субгенераторами. Единицы в позициях субгенератора соответствуют номеру разряда, выход которого подключен к данному сумматору по модулю два, причем первая единица в субгенераторе означает, что один из входов сумматора по модулю два подсоединен к входу регистра. Кодовые символы образуются по правилу
y_1t = i_t + i_t-1 + i_t-2 + i_t-3 (mod 2);
y_2t = i_t + i_t-2 + i_t-3 (mod 2), где сложение выполняется по модулю два. Процесс кодирования описывают с помощью решетчатой диаграммы, представленной на фиг. 3, которая отражает динамику перехода кодера от одного состояния к другому при поступлении очередного информационного бита на вход кодера. Так как число разрядов кодера равно в нашем примере К = 4, то число состояний, которые может принимать кодер в данный момент времени, равно
2^ν = 2^K-1 = 8.

Поскольку информационный бит может принимать одно из двух значений - "0" или "1", то число возможных переходов из одного состояния в другое при поступлении очередного информационного бита равно также двум: переход по верхней ветви, исходящей из каждого состояния диаграммы, соответствует поступлению "0", а переход по нижней ветви соответствует поступлению "1". Каждый переход (ветвь диаграммы) соответствует паре символов: y_1t, y_2t, которые также называют кодовой ветвью.

При рассмотрении фиг. 3 можно заметить, что решетчатая диаграмма распадается на четыре независимых двудольных графа (фиг. 4а), которые называют "бабочками" в литературе по вычислительным аспектам алгоритмов (см.,например, в книге Дж. Д. Ульман. Вычислительные аспекты. СБИС. М., РС, 1990, с. 215). Следовательно, декодирование одного бита в декодере Витерби сводится к 2^ν -кратному повторению вычислительной процедуры ССВ, которая описывается "бабочкой". На фиг. 4б изображена структурная схема обрабатывающего узла, выполняющего операцию ССВ. Узел ССВ содержит два канала обработки, их входы "Метрика состояния" на фиг. 4б отожествляют с левыми вершинами двудольного графа "бабочки". На фиг. 4 входы "Метрика ветви" при необходимости отожествляют с соответствующими ветвями "бабочки", а выходы блока ССВ "Метрика состояния" на фиг. 4б - с правыми вершинами двудольного графа "бабочки".

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

Устройство вычисления метрик работает следующим образом.

На интервале Т декодирования одного информационного бита, который равен
Т = 1/2^ν-1, где 1/Т - скорость передачи информационной последовательности, устройство последовательно выполняет четыре раза процедуру ССВ (фиг. 5-12) для каждой из четырех "бабочек", изображенных на фиг. 4а. Для этого интервал Т делят на четыре равных подынтервала
Т_п = (1/4)Т по числу "бабочек" на одном шаге решетчатой диаграммы. Рассмотрим состояние устройства на первом подынтервале, т.е. в начале декодирования информационного бита (см. фиг. 5 и 6). В этом состоянии с выхода первого недвоичного сдвигового регистра 6 на объединенные управляющие входы сумматоров 1 первого канала обработки поступает метрика состояния "1" (на фиг. 5 и 6 это отмечено числом 1 в выходном разряде первого двоичного сдвигового регистра), на объединенные управляющие входы сумматоров 1 второго канала обработки с выхода третьего недвоичного сдвигового регистра 9 поступает метрика состояния "0" (на фиг. 13 это отмечено числом 0 в выходном разряде третьего недвоичного сдвигового регистра). На младшие разряды соответствующих первых входов сумматоров обоих каналов обработки подаются метрики ветвей 00 и 11. Сумма метрики состояния "1" и метрики ветви 00 поступает на первый вход блока 2 сравнения первого канала обработки, а на его второй вход поступает сумма метрики состояния "0" и метрики ветви 11. Аналогично сумма метрики состояния "1" и метрики ветви 11 поступает на второй вход блока 2 сравнения второго канала обработки, а на его первый вход поступает сумма метрики состояния "0" и метрики ветви 00. Если сумма метрик на первом входе блока 2 сравнения больше суммы метрик на втором его входе, то сигнал на его выходе принимает уровень логической "1", в противном случае - уровень логического "0". В результате воздействия этого сигнала на первый вход коммутатора 3 метрик на его выходе появляется меньшая из двух указанных сумм: на выходе коммутатора 3 метрик первого канала обработки имеет место новая метрика состояния "4", а на выходе коммутатора 3 метрик второго канала обработки имеет место новая метрика состояния "0". Управляющий сигнал (фиг. 13в) первого переключателя 8 принимает уровень логической "1", в результате чего его выходной контакт подключается к выходу второго недвоичного сдвигового регистра 7. Управляющие сигналы второго 11 и третьего 13 переключателей также принимают уровень логической "1" (фиг. 13д и ж соответственно), в результате чего вход третьего недвоичного сдвигового регистра 9 подключается к выходу пятого регистра 12, вход которого, в свою очередь, подключается к выходу четвертого регистра 10. Как показано на фиг. 13б,г,ж, з, в конце данного подынтервала после того, как закончатся все переходные процессы в схеме фиг. 2 и 3, происходит переход от логического "0" к логической "1", тактовых сигналов всех недвоичных сдвиговых регистров. По этому переходу происходит сдвиг на один разряд влево содержимого всех недвоичных сдвиговых регистров 6, 7, 9, 10, 12. Результирующее состояние схемы показано на фиг. 7 - устройство подготовлено к выполнению операции ССВ, которая соответствует "бабочке", изображенной на фиг. 8. На последующих семи подынтервалах устройство работает аналогично. Недвоичный сдвиговый регистр работает в режиме хранения, т.е. его содержимое не сдвигается в том случае, если на данном подынтервале для соответствующего регистра отсутствует тактовый импульс. Как показано на фиг. 13, это условие выполняется для второго регистра на фиг. 7-12, для четвертого регистра на фиг. 9-12 и для пятого регистра на фиг. 11 и 12.

Так как в устройстве выполняется только одна арифметическая операция - сложение, то метрика носит кумулятивный характер: ее величина монотонно увеличивается во времени. Поэтому, если не принять специальных мер, то происходит переполнение памяти и, как следствие, нарушение работы устройства. Для того, чтобы избежать переполнения памяти, по мере необходимости осуществляют так называемую "нормализацию" метрики. Она сводится к вычитанию из всех метрик некоторого постоянного числа, или, что то же самое, к прибавлению ко всем метрикам при декодировании данного бита одного и того же числа по некоторому постоянному модулю, величина которого зависит от разрядности метрики. Нормализацию метрик выполняют с помощью блока 5 нормированного порога. Пусть сигналом опасности переполнения памяти служит появление логической "1" в старшем разряде метрики на выходе коммутатора 3 обоих каналов обработки на всех четырех тактовых подынтервалах. Это вызывает появление логической "1" на выходе схемы ИЛИ 4, к которому подключен вход блока 5 нормированного порога. Сигнал опасности переполнения хранится в блоке 5 до окончания интервала Т. Затем на интервале декодирования следующего бита уровень логической "1" имеет место на выходе блока 5, следовательно, к старшим разрядам первых входов сумматоров 1-1 и 1-2 на этом интервале подключена логическая "1". При надлежащем выборе старших разрядов (одинаковых для всех сумматоров) величина каждой метрики после операции сложения уменьшается на постоянную величину. После выполнения нормализации на следующем интервале Т на выходе блока 5 вновь устанавливается уровень логического "0".

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

УСТРОЙСТВО ВЫЧИСЛЕНИЯ МЕТРИК ПУТЕЙ ДЕКОДЕРА ВИТЕРБИ, содержащее элемент ИЛИ, выход которого подключен к входу блока нормированного порога, и два канала обработки, каждый из которых содержит блок сравнения, выход которого подключен к первому входу коммутатора метрик, и первый и второй сумматоры, выход первого сумматора подключен к первому входу блока сравнения своего канала обработки, отличающееся тем, что, с целью упрощения устройства, в него введены первый - пятый недвоичные сдвиговые регистры и первый - третий переключатели, выход блока нормированного порога подключен к входам старших разрядов всех сумматоров, входы младших разрядов которых являются входами устройства, выход второго сумматора каждого канала обработки подключен к вторым входам блока сравнения и коммутатора метрик другого канала обработки, выходы блоков сравнения всех каналов обработки являются выходами устройства, третьи входы коммутаторов метрик каждого канала обработки подключены к выходу первого сумматора того же канала обработки, выход коммутатора метрик первого канала обработки подключен к первому входу первого переключателя и элемента ИЛИ и входу второго недвоичного сдвигового регистра, выход которого подключен к второму входу первого переключателя, выход которого подключен к входу первого недвоичного сдвигового регистра, выход которого подключен к управляющим входам сумматоров первого канала обработки, выход коммутатора метрик второго канала обработки подключен к второму входу элемента ИЛИ, первым входам второго и третьего переключателей и входу четвертого недвоичного сдвигового регистра, выход которого подключен к второму входу второго переключателя, выход которого через пятый недвоичный сдвиговый регистр подключен к второму входу третьего переключателя, выход которого подключен к входу третьего недвоичного сдвигового регистра, выход которого подключен к управляющим входам сумматоров второго канала обработки.