Параллельный процессор хаара

.с ПИСАНИЕ ИЗОБРЕТЕНИЯ АВТОРСКОМУ СВ ЕЛЬСТВУ нтр АН АрмССР нтерян, Д.З.Ге 4 ство СССР /332, 1983. ство СССР /332, 1987. О лю. Ус группу группу рониза вых имБлок синхронизации 9 и 10, которые подключе к одноименным входам с ков задержки и к управля мутаторов первой и втор имеет два выхода ы соответственно нхрониэации блоющим входам комй групп. ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР(54) ПАРАЛЛЕЛЬНЫЙ ПРОЦЕССОР ХААРА Изобретение относится к вычислительной технике и может быть использовано в системах цифровой обработки сигналов для построения устройств цифровой фильтрации, сжатия изображения и выделения признаков, основанных на параллельном алгоритме преобразования Хаара.Цель изобретения - повышение быстро.действия путем применения нового парал-лельного алгоритма преобразования Хаара. На фиг,1 представлена схема параллельного процессора Хаара для последовательности входных выборок. векторов размерами й = 2 = 16; на фиг,2 - граф последовательности вычисления коэффициентов Хаара для М = 16; на фиг.3 а и б - схемы состояний переключателей первой и второй групп соответственно.Параллельный процессор Хаара (фиг.1) содержит шестнадцать информационных входов, на которые поступают отсчеты вход 50, ц 1667103 А 1(57) Изобретение относится к вычислительной технике и может быть использовано в системах цифровой обработки сигналов для построения устройств цифровой фильтрации, сжатия изображения и выделения признаков, основанных на параллельном алгоритме преобразования Хаара, Цель изобретения - повышение быстродействия. Для этого процессор содержит две группы коммутаторов, и групп сумматоров-вычитателей (й = 2 - объем входной выборки), две группы блоков задержки и блок синхронизации, Указанная цель достигается эа счет применения нового параллельного алгоритма преобразования Хаара. 3 ил. ного вектора (Хф) - Х(т), и шестнадцать информационных выходов, на которых получаются коэффициенты Хаара (Уо(т - 4) - ф У 15(е, первую группу коммутаторов 10- 16, вторую группу коммутаторов 2 о - 2, восемь сумматоров-вычитателей Зо, разбитых на четыре группы: нулевая группа о содержит четыре сумматора-вычитателя, 0 первая группа 11-два, вторая и третья груп пы 12 из - по одному сумматору-вычитате- ф роиство содержит также первую блоков 40-412 задержки, вторую блоков 5 озадержки, блок 6 синхции, содержащий генератор 7 тактопульсов и делительл 8 частоты на два.(2)Н = 1 Х О О 0 О 1 1 О . О О 1 -1 О Х О 8 Каждый сумматор-вычитатель состоитиз двух сумматоров: один для выполненияоперации сложения, другой - для выполнения операции вычитания,Каждый блок задержки первой группы 541 содержит один регистр сдвига и эапомикает поступившее число на один такт работы сумматоров-вычитателей. Каждый блокзадержки второй группы 5 так же состоитиэ одного регистра сдвига и запоминает по- . 10ступившее число на один такт работы сумматоров-вычитателей, так как и -- 3 = 1.На фиг.2 рядом с каждой базовой операцией двухточечного преобразования указан номер такта, во время которого она 15выполняется,Переключатели первой и второй групппринимают первое или второе состояние(на фиг.З показаны римскими цифрамии )в зависимости от управляющего сигнала 0 20или 1 с второго выхода 10 блока 6 синхронизации,Вычисление коэффициентов Хаара основано на разработанном параллельном алгоритме преобразования Хаара над 25последовательностью входных выборок,представляемых векторами Хь размеромй =2" У 1 = Нч Х ( = 1,2), (1) 30 где Нч - матрица преобразования Хаара;У - преобразованные выборки. 1 1 0 О 0 0 1 -1 0 0 0 О 0 0 1 1 0 0 0 О 1 -1 0 О 0 0 0 0 1 1 0 О 0 0 1 -1Алгоритм строится посредством факторизации матрицы Нч в виде произведения слабо заполненных матриц. Н(1 Т(1) Н(2) Т(2) Н(п) .Г(п) (2) фН(=ВЧ ОЬ 2 (3) б О В где 9- обозначает прямую сумму матриц; ч- единичная матрица порядка Й -2);В (2)ТО) - матрицы перестановок, определяемые следующим образом. х Р 2)+1; 9(2 п 2+1 4)ь где Я 2) - матрица операторэдвоично-инверсной перестановки порядка 2);Р 2) - матрица оператора полной тасовки порядка 2.Для примера рассмотрим факторизациЮ 4 матрицы преобразования Хаара при й =2 =16.Н 16 = Н(1) Т(1) Н(2) Т(2)3) Т(З)(4) Т(4)1667103 1 0 0 0 0 0 О 0 0 0 0 0 О 0 0 0 0 0 1 0 0 0 О 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 О 0 1 0 0 0 0 О 0 0 0 О О 0 0 0 0 0 О 0 1 0 0 0 0 О 0 1 О 0 0 0 0 0 О 0 0 0 0 0 0 0 0 0 0 1 0 О О 0 О О О 0 0 0 0 0 0 0 0 0 0 О О 0 0 1 0 0 0 0 0 0 0 0 0 О О О О 0 0 0 0 1 0 0 0 0 О 0 О О 1 0 О 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 О 0 О 0 0 0 О 1 0 0 0 0 0 О 0 0 0 0 0 О О 0 0 0 0 1 0 0 0 0 О О 0 0 О О 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 О 0 О О О 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 О О 0 0 0 0 0 1 0 О 0 0 0 0 О 0 О О 0 0 00 0 О 0 О 1 В соответствии с (2) преобразование Хаара над одной входной выборкой Г( производится в и этапов, т е.У,: ДС) .ТС 1) .(Н(г). ТР) (Н(п), Т(п-,1),(Н (и); Упт.Сущность алгоритма заключается в следующем,Алгоритм состоит из К-.= 2" взаимодействующих между собой ветвей, Ветви алгоритма условно разбиваются на о групп. В 10-ю группу( =0,1п - 2) входят 2" ветвей,а в= и-ю группу входит одна ветвь, Наочередном -м цикле алгоритма ( = 1,2.,),состоящем из двух шагов (шагу алгоритмасоответствует такт раЬоты сумматоров-вычитателей в предлагаемом процессоре), параллельно в каждой группе ветвей=0,1 Л - 1 (с = мин (и - 1, +1 выполняется )-йэтап преобразования, т.е, умножение матрицы Н(" Т(" ) на очередной вектор, являющийся при= 1,2., т - 1 результатомработы предыдущей группы ветвей на предыдущем цикле, а при= 0 - новой входнойвыборкой Х,Итак, на каждом цикле, т.е, через шаг, 25начинает обрабатываться новая входнаявыборка. Начиная с п-го шага в 2 ".йветвиалгоритма (в п-й группе) через один шаг выполняется последний (и - 1)-й этап преобразования Хаара, над очередным вектором 30результатов, полученных в(2" -1)-й ветви. Таким образом, преобразование одной входной выборки осуществляется за и шагов, и при этом, начиная с и-го шага через каждый шаг формируется результат преобразования очередной входной выборки.В соответствии с приведенным алгоритмом для последовательности входных выбоаок оазмерами й = 2" процессор содержит 2"сумматоров-вычитателей, на каждом из которых реализуются вычисления, выполняемые одной ветвью алгоритма. По аналогии с ветвями алгоритма сумматорывычитатели разбиваются на конвейерно соединенные группы.Рассмотрим работу процессора на примере последовательности входных выборок размерами ч= 2 = 16, В этом случае,процессор содержит четыре группы сумматоров-вычитателей: в нулевую группу входят четыре сумматора-вычитателя, в первую группу - два сумматора-вычитателя, во вторую и в третью - по одному сумматору-вычитателю, Процессрр содержит семь коммутаторов в первой группе, четыре - во второй группе, тринадцать блоков задержки в первой группе, задерживающих информацию на один такт работы сумматоров-вычитателей, восемь блоков задержки во второй группе, задерживающих информацию также на один такт (так как и - -3 = 1 при и = 4,= 0) и блок синхронизации, содержащий генератор тактовых импульсов и делитель частоты на два.С каждым тактом на синхронизирующие входы блоков задержки первой и второй групп поступают сигналы от генератора 7 тактовых импульсов блока 6 синхронизации, запоминая информацию на один такт работы сумматоров-вычитателей. На первом такте при поступлении на синхронизирующие входы 10 коммутаторов 20 - 2 з сигнала от делителя 8 частоты блока 6 синхронизации они устанавливаются в первое состояние и подключают к входам сумматоров-вычитателей 30 - Зз 1 О-Й группы первые восемь информационных входа процессора: Хсих 1 - 30 Х 2 иХЗ - ъ 31,Х 4 и Х 5 -32,Х 6 и Х 7 -Зз.ВычисляютсЯ суммы (ХО + Х 1), (Х 2 + Хз), (Х 4+ Х 5) (Х 6+ Хт) и разности (Хо-Х 1), (Х 2 - Хз), (Х 4-Х 5), (Х 6-Х 7), Суммы поступают на блоки 40, 42, 44, 46 задержки и запоминаются в них, а разности- на блоки 41,4 з,45,47. На втором такте по сигналу от блока синхронизации коммутаторы 20-2 з устанавливаются во второе состояние, коммутаторы 10-1 з - в первое,Через коммутаторы 40-4 з на входы сумматоров-вычита 1 елей 30 - Зз поступают следующие четыре пары входных сигналов: Х 8 и Х 9 "+30, Х 10 и Х 11-ъ, Х 12 и Х 1 з -)32, Х 14 и Х 15-УЗз. Вычисляются суммы (Х 8 + Х 9), (Х 10 + Х 11), (Х 12 + Х 13), (Х 14 + Х 15) и разнОсти (Х 8-Х 9), (Х 10-Х 11), (Х 12-Х 1 з), (Х 14-Х 15). Разности поступают на блоки задержки первой группы 41, 4 з, 45, 47, откуда предыдущие результаты через коммутаторы 10 - 1 з передаются на блоки задержки второй группы 50, 52, 54, 56, где и запоминаются на один такт. Суммы из сумматоров-вычитателей Зов Зз поступают на блоки задержки 40, 42, 44, 46, откуда предыдущие результаты передаются на входы сумматоров-вычитателей следующей группы 1-й 34 и 35, Таким образом базовые операции первого этапа полностью завершены.Одновременно сумматоры-вычитатели 34 и 35 продолжают преобразование первой входной выборки, т.е. вычисляются соответственноо суммы Хо+ Х 1) + (Х 2+ Хз, Х 4+ Х 5) + (Х 6+ Х 7 и разности Х 0+ Х 1) - (Х 2+ Хз, Х 4 + Х 5) - (Х 6 + Х 7; Суммы поступают на блоки задержки 48 и 410, а разности - . на блоки 49 и 411. Двум тактам работы сумматоров-вычитателей соответствует цикл работы процессора, С каждым циклом, т.е, через такт на вход процессора р поступает новая входная выборка, На третьем такте коммутаторы 20-2 з устанавливаются вновь в первое состояние, коммутаторы 10-1 з - во второе состояние, коммутаторы 14 и 15 - в первое, Первый этап преобразования над первой половиной новой входной выборки вычисляется аналогично укаэанному, приэтом предыдущие результаты из блоков задержки 41, 4 з, 45, 47 через коммутаторы 10- 1 з передаются на блоки задержки 515 з, 55, 57, а с блоков задержки 50, Ж, 54, 56 предыдущие результаты, т.е, (Х 0 - Х 1), Х 2-Хз), (Х 4- Х 5), (Х 6 - Х 7) поступают на восьмой, девятый, десятый и одиннадцатый информационные выходы процессора, т.е, на выходах процессора имеется уже часть коэффициентов: У 8, У 9, У 10, У 11. 5 10 Таким образом на информационных выходах процессора через четыре такта работы сумматоров-вычитателей, т.е. через два цикла работы процессора, имеются все коэффициенты Хаара,Конечные результаты преобразования Информация с блоков задержки 49 и 411через коммутаторы 14 и 15, т.е. Хо+ Х 1) - (Х 2 + Хз, Х 4 + Х 5) - (Х 6 + Х 7 поступает на 15 четвертый и пятый информационные выходы процессора, т.е. имеются У 4-й, У 5-й коэф.фициенты, На этом же такте включается в работу 12-я группа сумматоров-вычитателей, т.е. в сумматоре-вычитателе 36 вычисляется сумма Хо+ Х 1+ Х 2+ Хз)+(Х 4+ Х 5+ Х 6 + Х 7 и разность Хо+ Х 1+ Х 2+ Хз) - (Х 4+ Х 5 + Х 6 + Х 7. Разность через коммутатор 16 поступает на второй выход процессора, т.е, на выходе имеется коэффициент У 2, а сумма 25 поступает на блок задержки 412.На следующем четвертом такте коммутаторы 20 - 2 з устанавливаются во второе состояние, коммутаторы 10-1 з - в первое, коммутаторы 14, 15, 16 - во второе состоя ние. На двенадцатый, тринадцатый, четырнадцатый и пятнадцатый информационные выходы процессора поступают результаты из блоков задержки 51, 5 з, 55, 57, на седьмой и шестой выходы - через коммутаторы 14 и 15 из блоков задержки 49 и 411, т.е, на указанных выходах имеются У 12, У 1 з, У 15, У 6, У 7 коэффициенты преобразования. На этом же такте сумматор-вычитатель 36 вычисляет сумму Х 8+ Х 9+ Х 10+ Х 11) + (Х 12+ Х 1 з+ Х 14 40 + Х 15 и разность Х 8 + Х 9 + Х 10+ Х 11) - (Х 12+ Х 13+ Х 14 + Х 15.Разность через коммутатор 16 поступает на первый информационный выход процессора, а сумма - непосредственно на 45 второй вход сумматора-вычитателя 37, напервый вход которого поступает предыдущий результат из блока 412 задержки. Сумматор-вычитатель 37 выполняет последний этап преобразования Хаара, вычисляя сум му(Х 0+ Х 1+Х 15) и разность Х 0+Х 7) -(Х 8+Х 15. Сумма поступает на нулевой выход процессора. а разность - на первый.1667103 12 хаЮ ху /) хл (1 х (т) хр(е ха(Е ж 5 ка(ц хз(с) Йай) хп(Ц х 2 сц(й) ХИ (г) М( 5 З--/г-) над следующими входными выборками будут готовы на каждом втором такте работы сумматоров-вычитателей, т,е. на каждом цикле процессора.Предлагаемый процессор реализует преобразование Хаара для входных выборок длиной 2" (и-целое число, и з), на которое требуется и тактов работы сумматоров-вь 1 читателей,В случае И = 2 = 16 на преобразование4входной выборки требуются четыре такта работы сумматоров-вычитателей или два цикла работы процессора вместо девяти тактов в базовом объекте,Процессор производит конвейерную обработку с перекрытием во времени последовательности поступающих на каждый цикл (через такт) выборок-векторов, при этом в установивщемся режиме, начиная с и-го такта через такт (на каждый цикл). он выдает очередной вектор коэффициентов преобразования Хаара. Формула изобретения Параллельный процессор Хаара, содержащий и групп (М = 2" - Объем вхоцной выборки) сумматоров-вычислителей, первую группу коммутаторов и блок синхронизации, о т л и ч а ющ и й с я тем, что, с целью повышения быстродействия, в него введены вторая группа коммутаторов и две группы блоков задержки, причем)-й Ц:= 0,2" - 1) информационный вход процессора соединен с 1-м= ) гиос) 2 +- ) тоо М/2/2" информационным входом К-го (К =и 1 ос) И/2 - ) прог) 2)/2) коммута 1 ора второй группы, Я-й (Б = 0,1) информационный выход которого соединен с одноименным 5-м входом сумматора-вычитателя первой группы, выход суммы )-го сумматора-вычитателя первой группы через 3-й блок задержки первой группы соединен с ц-м (ц = ) гиос) 2) 5 входом Е-го (Е = Ц - /2) сумматора-вычитателя первой группы, выход суммы М-го (М = О 2 - 1) сумматора-вычитателя 1-й ( = 1,и) группы через М+ 2" - 2" )-й блок задержки первой группы соединен с с-м (т = 10 М гиок 2) входом К-го (В = (М - с)/2) сумматора-вычитателя+ 1)-й группы, кроме того, выход суммы сумматора-вычитателя (и - 2)-й группы соединен непосредственно с вторым входом сумматора-вычитателя (и - 1)-й 15 группы, выход разности М-го сумматора вычитателя у-й группы (р = О,и - 3) через (М + 2" - 2" Р)-й блок задержки первой группы соединен с информационным входом ): го= М+ 2" - 2" ) коммутатора первой 20 группы, выход разности сумматора-вычитателя (и)-й группы соединен с информационным входом (2" - 1)-го коммутатора первой группы, выходы суммы и разности сумматора-вычитателя (и - 1)-й группы сое динены соответственно с первым и вторымвыходами процессора, выходы коммутаторов с (2" - 5)-го по (2" - 3)-й первой группы соединены соответственно с третьего по восьмой выходами процессора 1 а вы ходы коммутаторов с первого по (2" - 6)-йчерез блоки задержки второй группы соединены с девятого по (2"й выходами процессора, первый выход блока синхронизации соединен с входами синхро низации всех блоков задержки, второй выход блока синхронизации соединен с управляющими входами коммутаторов первой и второй групп,/УггщщэтаП Х "с+фа- АзаХм олср К гю-гФиг.дСоставитель Ю.Ланцовктор С.Лисина Техред М. Моргентал Корректор М.П Заказ 2526 Тираж 413 Подписное 8 НИИПИ Государственного комитета по.изобретениям и открытиям при ГКНТ СС 113035, Москва, Ж, Раушская наб., 4/5 Производственно-издательский комбинат "Патент", г, Ужгород, ул.Гагарина