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

(9) (1) е)5 (Ь 06 Г 15/ЗЗ ИЕ ИЗОБРЕТЕНИЯ ОПИСА К АВТО ыст- о-поГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР МУ СВИДЕТЕЛЬСТВУ(71) Вычислительный центр АН АрмССР (72) А,П,Галантерян, Д,З.Геворкян и А, В,Мелкумян(56) Патент США М 3981443,кл. 6 06 Р 15/34, 1975.Авторское свидетельство СССР М 1061150, кл. 6 06 Г 15/332, 1983.Авторское свидетельство СССР Кт 1343423, кл. С 06 Г 15/332, 1987.(57) Изобретение относится к вычислительной технике и цифровой обработке сигналов. Цель изобретения - повышение быстродействия за счет применения поточИзобретение относится к области ВТ и обработки случайных процессов и может. быть использовано в системах цифровой фильтрации, сжатия изображения и выделе-: ния признаков, основанных на параллельном алгоритме преобразования Хаара,Известны устройства, выполняющие конвейерное рационализированное преобразование Хаара для входных выборок длиной Й = 2", представляемых последовательными отсчетами.Однако во многих. областях цифровой обработки сигналов возникает необходимость в поточной обработке входных выборок, поступающих параллельно в виде векторов длиной й = 2", что невозможно реализовать на известных устройствах. 2ной обработки векторов длиной й = 2" и унификация процессора, заключающаяся в реализации процессора йа 2(т = 1, и) сумматорах-вычитатепях в зависимости от требуемого быстродействия. Указанная цель достигаешься тем; что"в"поточно-параллельный процессор Хаара, содержащий группу сумматоров-вычитателей, группу переключателей и блок синхронизации, введены т групп сумматоров-вычитателей (1= 1, п, И = 2" - размер входной выборки), три группы переключателей, (2 - 2) блоков сдвига и две группы"элементов задержки, Поточно-параллельный процессор Хаара может быть использован в системах цифровой фильтрации, сжатия изображения и выделения признаков, основанных на параллельном алгоритме преобразования Хаара. 6 ил. Наиболее близким техническим решением к предлагаемому явпяется устройство для вычисления коэффициентов Хаара, со-. держащее группу из пятнадцати сумматоров, хранящих в себе информацию до прихода следующей и выполняющих одну . операцию (вычитание или сложение) за один такт работы, группу переключателей, состоящую иэ шестнадцати переключателей, счетчика, схемы ИЛИ и дешифратора. В этом устройстве с целью йовцшения б родействия применяется параплельн следовательный метод . обработки, Устройство осуществляет параллельное вычисление коэффициентов Хаара от 16 отсче тов входной выборки цифрового сигнала за девять тактов работы сумматоров.1756901 р Л.Лукач Составитель А,Гала Техред М,Моргентал Дерб к роизводственно-издательский комбинат "Патент", г, Ужгород, ул,Гага 3089 . Тираж : . ПодписноеНИИПИ Государственного комитета по йзобретениям и открытиям при ГКНТ СССР 113035.,Москва, Ж, Раушская наб 4/5Однако известное устройство не производит поточную обработку векторов, т.е. для выполнения преобразования над следующей входной выборкой цифрового сигнала потребуются еще девять тактов. При этом сумматоры работают с неполной загруженностью, т.е. используются не эффективно. Если реализовать известное устройство для входных выборок-векторов длиной й =2", то следует ожидать, что преобразование Хаара над каждым вектором будет выполняться за (2" + 1) тактов и потребуется (2" -1) сумматоров.Недостатками известного устройства являются низкое быстродействие и не эффективное использование аппаратуры,Цель изобретения - повышение быстродействия за счет применения поточной обработки векторов длиной й = 2" и унификация процессора, заключающаяся в реализации на 2 ( = 1, и) сумматорах-вычитателях в зависимости от требуемого быстродействия.В поточно-параллельный процессор Хаара, содержащий группу сумматоров-вычитателей, группу переключателей и блок синхронизации, введены 1 групп сумматоров-вычитателей, три группы переключателей, блоки сдвига и две группы элементов задержки, Первая группа переключателей содержит 2 переключателей с 2входа 1-1 в-+1 ми и двумя выходами, вторая группа содерижит 2 переключателей с одним входом и 2 выходами, третья группа - одий переключатель с однимвходом и (2(п)-1) выходами, четвертая - один переключатель с 2(п) входами и двумя выходами, каждый из блоков сдвига состоит из 2" последовательно соединенных регистров сдвига, первая группа элементов задержки состоит из (2 + 2(п-1) элементов, а вторая группа - из (2"(2-2) + + 2"1) элементов, 1-я и последняя (т+1)-я (1 = =1, т) группы сумматоров-вычитателей состоят соответственно из 2 и одного ссумматора-вычитателя, причем )-й (1 = О, 2 -1) информационный вход процессора соединен с 1-м (1 = ) гпоб 2 + 2 О - ) гпоб 2)/2) информационным входом К-го (К = ( воб 2 с - 3 гпоб 2)/2) переключателя первой группы, 1-й информационный выход которого (1 = О, 1 соединен с 1-м входом одноименного К-го сумматора-вычитателя первой группы, выход суммы п 1-го сумматора-вычитателя первой группы через гп-й (а = О, 2 -1) блоктсдвига соединен с Ь-м (Ь = п 1 проб 2) вхбдом о-го (ц =- (п 1 - Ь)12) сумматора-вычитатрля второй группы, выходсуммы д-го(о=:0,2 " ) сумматора-вычитателя г-й (г = 2, -1) группы через (гл+ 2 "1 - 2" 2")-й блок сдвига соединен с Р-м (Р.= гп, ваб 2) входом с 1-го п 1 - Р(Ц= ) сумматора-вычитателя (г+ 1)-й2.группы, выход суммы ед 1 лнственнаго сумматора-вычитателя (1+1)-й группы соединен с 5 (2-1)-м элементом задержки второй группы,выход которого соединен с первым входом переключателя четвертой группы и с входом, 2-го элемента задержки второй группы, выход которого соединен с первым входом пе-.10 реключателя четвертой группы, 1-й выходкоторого (1 = О, 1) соединен с одноименным входом единственного сумматоравычитателя (с+1)-й группы, выход которого соединен с информационным 15 входом переключателя третьей группы,1-й (1 = О, 2 (п-.т) - 1) выход которого через (2+1+1)-й элемент задержки второй группы соединен с(1+2)-м информационным входом переключателя четвертой группы, а 2(п-т)- 20 й выход переключателя третьей группы является первым выходом процессора, выход разности последнего сумматара-вычитателя (1+1)-й группы соединен с информационным входом 2-го переключателя второй 25 группы, с-й (с, = 1, 2" - 1) выход которогоявляется с-м информационнь 1 м выходомл процессора, выход разности б-го (б = 0,2 - 2) сумматора-вычитателя через б-й элемент задержки первой группы связан с информа- ЗО ционным входом б-го переключателя цтарафгруппы, 11-й(11 =0,2 - 1) выход 1-го(1=0,2 ) переключателя второй группы соединен с входом 1-го (Г =), 2" + Ь) элемента задержки., С первого по (2")-й выходы (2 - 2)-го пере ключателя второй группы связаны с информационными входами с (2"(2 - 2-го по.. (2" - 1)-й элементов задержки второйгруппы, выходы которых являются с 5-го по 2" -й выходами процессоров, а с(2+1)-го 40 по 2 -й выходы(22)-го переключателя второй группы являктся с(2"+1)-го по(2")-й информационными выходами процессора.Выходы перекл 1 очателей второй группы соответственно с 1-го по (2-1)-й соединены с 45 входами с 1-го по (2" (2 - 2) + 2")-й элементов задержки второй группы, Выходы с 1-го по (2" (2 - 1)-й элементов задержки второй группы явля 1 отся с 2"-го по (2"+ 5)-й выходами процессора.50 Блок Синхройизации состоит из генератора тактовых импульсов и трех счетчиков, причем выход генератора тактовых импульсов соединен как с управляющими входами блоков сдвига и элементов задержки первой 55 и второй групп, являясь первым выходомблока синхронизации, так и с тремя счетчиками блока синхронизации, причем первый счетчик по воб 2" с(п) разрядной шиной на выходе, которая является вторым выходом блока синхронизации и соединена с1756901 входами переключателя четвертой группы:" . ные входы ХО-Хзм, информационныеНа фиг.1 представлена схема поточно-па-выходы Уо-Уз 1, переключатели первой групраллельного процессора Хаара для последо- пы 1 О и 11, переключатели второй гоуппы вательности входных выборок-векторов 2 оз, переключатель третьей руппы 31, перазмерами й = 2" для 2 сумматоров-вычита реключатель четвертой группы 41, сумматотелей, где с = 1, и; на фиг.2 - схемы поточно- ры-вычитатели 5 о - 5 з, блоки бо и 61 сдвига, параллельных процессоров Хаара для состоящие из восьми регистров сдвига, элепоследовательности входных выборок-оекто- менты задержки перобй группы 7 ов, элеров размерами М = 2" для 2 сумматоров-оы- менты задержки второй группы 8-81 э, блок читателей, когда с =-3,2, 1 соответственно; на 20 9 синхронизации, состояьций из генератора фиг,5 - граф последовательности вычисле тактовых импульсов с выходом 14, счетчиния коэффициентов Хаара для й = 2, = 32; ка по гпоб 8 с 3-разрядной шиной 15 на5нафиг,б - схемы состоянийпереключателей выходе, счетчика по споб 5 с 3-разрядной с первой по четвертую групп и последнего шинои 6 на выходе, счетчика по п 1 об 3 с переключателя второй группы для процес 2-разрядной шиной 17 на выходе,сора при т = 3, Поточно-параллельный процессор ХааПоточно-параллельный процессор Хаа- ра при т = 1 (фиг.4) содержит информационра (фиг.1) содержит 2" информационных ные входы Хо - Хз( и информационные входы оходов Хо -. Х 2 -1 и 2" информационных вы- . Уо-Уз 1, г 1 ереключатель первой групг;ы 1 ходов Уо - У 2-1, первую группу переключа переключатели второй группы 2 о и 21, перетелей 1 о - 1 о -1, вторую группу ключатель третьей группы 3, переключапереключателей 2, - 22, третью группу 31 тель четвертой группы: 41, и четвертую группу 4(, 2 сумматоров-вы- сумматоры-вычитатели 5 о и 5(, элементы зачитателей 5 о - 52-1, разбитых на (с + 1) держки второй группы 8 о - 8 т, элементы загрупп )о - )ь )-я группа содержит 2 сум держки первой группы 7 о - 7 в, блок 9 матороо-вычитателей,с-я группа содержит синхронизации, состоящий из генератораВодин сумматор-вйчитатель, блоки бо - 62-з 10 тактовых импульсов с выходом 14, счет- сдвига с 2" последовательно соединен-чика по воб 16 с 4-разрядной шиной 15 ча ными регистрами сдвига, элементы за- выходе, счетчика по тоб 7 с 3-разрядной держки первой группы 7 о - 7(2+2(п-с, 40 шиной на Выходе 16, счетчика по воб 4 с элементы задержки второй груйпы 2-разрядной шиной на выходе 17.н.а (, ий (8 о - 82 р -2)+2 -1) и блок 9 синхронизации, Каждый сумматор-вычитатель без внут- который состоит из генератора 10 такто-ренней памяти состоит из двух сумматоров оых импульсов, счетчика 11 по п 1 об 2", (один для выполнения операции сложения,счетчика 12 по тоб(2 х(п-с)-1), счетчика 13 по 45 другой для вычитания).проб(п-т) и имеет четыре выхода 14-17, прй- Каждый блок сдвига состоит из 2"почем последние три выхода являются соот- следовательно соединенных регистровветственно (п-т)-разрядной, одг 2(п-т) сдвига,разрядной и )од(п+разрядной шинами. Каждый элемент задержки запоминаетПоточно-йараллельный процессор Хаа поступиошее число до прихода следующего,ра прй с = 3 (фиг.2) содержит тридцать два На фиг,5 рядом с каждой базовой опеинформационных входа Хо-Хэ 1, тридцать рацией двухточечйого преобразования укадва информационных выхода Уо - Уз 1, пере- зан номер такта, во время которого онаключатели первой группы 1 оз, переключа- выполняется, при т = 3, т.е. для 2 суммато- з тели второй группы 2 От, переключатель 55 роо-оычитателей третьей группы, 31, переключатель четвертой группы 41, сумматоры-вычитатели 5 о,На фиг.ба - г римскими цифрами указаны состояния переключателей первой, втоблоки бо - 6 ь сдвига, состоящие из четырех . рой, третьей и четвертой групп о последовательно соединенных регистров зависимости от двоичного кода на упраолясдвига, элементы задержки первой группы ющих входах переключателей, который поуправляющими входами переключателей 7 о - 7(о, элементы задержки второй группы первой и второй групп, второй счетчик по 8 о - 8 ж, блок 9 синхронизации,состоящийиз глоб(2 (пн) - 1) с одг 2(п-т) разрядной шиной генератора 10 тактовых импульсов с оыхона выходе, которая является третьим выхо- дом 14, счетчика 1 по гпоб 4, с 2-разрядной дом блока синхронизации и соединена с 5 шиной 15 на выходе, счетчика 12 по споб 3 управляющими входами переключателя с 2-разрядной шиной 15 на выходе, счетчика третьей группы, третий счетчик по еоб(п-с) е 13 по аоб 2 с одноразрядной шиной на од 2 (и-т) разрядной шиной на выходе, кото- выхбде 17.рая является четвертым выходом блока синх- Поточно-параллельный процессор Хааронизации и соединена с управляющими 10 ра при т = 2 (фиг.2) содержит информацион1756901 дается через соответствующие многоразрядные аины с выходов блока синхронизации.Вычисление коэффициентов Хаара основано на разработанном параллельном 5 алгоритме преобразования Хаара над последовательностью входных выборок, представляемымх векторами Х размером2 п10У = Нн Х= 1, 2,). (1)-1 ОООО 011003 О 1-1 ООООО 1 0 0 0 1-1 5 . н1 1 0 О 0 0 0 1-1 0 0 0 0 О О О 1 1 О О О 0 0 1-1 0 0 00 О. 0 0 1 1 0 ОООО 1-1 О 0000001О ОО 1- 0 0 0 0 00 О 0 0 0 0 0 00 0 0 0 0 0.0 0 0 0 0 0 0 0 .0 О 0 0 0 0 О 0 0 0 0 0 0 О 0 0 00 0 0 О 0 0 0 0 ООО 000 000 ООО ООО 000 0000 0 2);2 0 0 О 0 О 0 0 О 1 О 0 О -1 0 0 0 О 11 О 0 1-1 0 0 0 01 0 0 0 1 ТО) - матрмая следующ перестановок, образом; ел Лз тЫ", и) ратора двоичнб-инвер- Э 5 орядка 2);ратора полной тасовки акторизация матрицы а при И 2"ц(2) Н(З) (3) Н(4) 4). 0= 1(Р 20+ Я Де 52)- м ной пер атрица опестановки иатрица опемер.Фвания Хаар. Алгоритм строится посредством Факторизации матрицы Ни в виде произведенйя .слабо заполненных матриц, (О Н(2).,Р) (и),(.) р)гР(НО) =О+ Чз а Ь-г"5-0.где 9 - прямая сумма матриц,Ъ)- единичная матрица порядка й 0 0 0 0 0 0 0 0 0 О 0 0 0 0 О 0 0 0 О 0 ОООО 1 0 0 0 1 0: 0 0 0 1 1 0 0 1-1 О О 0 0 1 0 0 0,1 О 0 0 0 0 О 0 0В соответствии с(2) преобразование Хаара над одной входной выборкой Х производится в и этапов, т.е. Ъ: (Н Т(1) (Н(2) т(2)(Н( ") Т( ) ( и) .( ) Х ) ) ) Сущность алгоритма заключается в следующем,Алгоритм состоит из К = 2 (1 = 1, и, 2" - длина входной выборки) взаимодействующих между собой ветвей, Ветви алгоритма условно разбиваются на (1+1) групп. В )-ю (= О, т) входят 2ветвей, а в= 1-ю группу входит одна 2-я ветвь,На очередном )-м1цикле алгоритма ( = О, 1.), состоящем из 2" шагов (шагу алгоритма соответствует такт работы сумматоров-вычитателей в предлагаемом процессоре). параллельно в каждой группе ветвей=- О, 1 Л), т= ти (т, +1 выполняется 3-й этап преобразования, т.е. умножение матрицы К" ) Т" ) на очередной вектор, являющийся результатам работы предыдущей группы ветвей на предыдущем цикле, а при= 0 - новой входной выборкой Хь Итак, на каждом цикле начинает обрабатываться новая входная выборка. Начиная с 1-го цикла работы, на каждом цикле, кроме операций, исполняемых в группах ветвей= О, 1-1, параллельно (одновременно) в т-й группе ветвей (т.е, в 2-й ветви) выполняются последовательно1 этапы т, т+1ппреобразования Хаара о о ОО 1 ооо ООО о 1 о ооо ооо ооо ООО ООО ооо ооо ооо ООО ООО ООО оооо оооо оооо оооо ооооооо оооо оооо о 1 оо ооо оо 1 о оооо оооо оооо оооо оооо ООООО ООООО о 1 ооо ооо 1 о ооооо ООООО оо 1 оо 00001 ООООО 00000 00000оооо ООООО ООООО ООООО ООООО оооо ОООО оооо оооо оооо оооо оооо оооо оооо оооо оооо ооооООО ОО 1 О О 1 ОО ООО 1 над очередным вектором результатов, полученных в (1-1)-й группе ветвей, т.е. в (2-1)-й ветви. Для этого требуются (2" - 1) шагов,П а не (2 ), т,е. на каждом цикле в течении 5 одного шага в т-й ветви операции не выполняются. Таким образом, преобразование одной входной выборки осуществляется за ф+1) (2" ) - 2) шагов и, при этом, начиная с+ 1)2"- 2)-го шага через каждые 2" 10 шагов формируется результат преобразования очередной входной выборки,Рассмотрим работу процессора на примере последовательности входных выборок 15 размерами й = 2 для 2 сумматоров-вычи 5 3тателей: в нулевую группу входят четыре сумматора-вычитателя, в первую - два сумматора-вычитателя, во вторую и третью - по одному сумматору-вычитателю, Процессор содержит четыре переключателя в первой группе, восемь переключателей во второй, один - в третьей и один в четвертой группах, шесть блоков сдвига, по 2 последовательно4соединенных регистров-сдвига в каждом из 25 них, двенадцать элементов задержки в первой группе, двадцать шесть элементов задержки во второй группе и блок синхронизации, состоящий из генератора тактовых импульсов, счетчика потоб 4, счетчика по тос 3 и счетчика по то 4 2,На первом такте при поступлении науправляющие входы переключателей 1 оз сигнала от блока синхронизации они устанавливаются в первое состояние и подклюЭ 5 чают к входам сумматоров-вычитателей5 о - 5 з о-й группы первые восемь информа- ЦИОННЫХ ВХОДОВ ПРОЦЕССОРа; Хо И Х 1 -+5 о, Х 2 и Хз; Х 4 и Х 4 +52: Хб и Х 7 - 5 з.Вычисляются суммы (Хо + Х 1), (Х 2 + Хз), (Х 4 40 + Х 5), (Хб + Х 7) и разности (Хо - Х 1), (Х 2 - Хз)."(Х 4- Х 5), (Х 5- Х 7). Суммы поступают на входы блоков боз сдвига, а разности - на элементы 7 оз задержки.На втором такте по сигналу от блока 45 синхронизации переключатели 1 о - 1 з устанавливаются во второе состояние, переключатели 2 о- в первое, а на входы сумматоров-вычитателей 5 оз поступают следующие четыре парйвходных сигналов: Х 8 и Х 9 -5 о, Х 1 о и Х 11 -ф 51; Х 12 и Х 13-ф 52; Х 14 и Х 15-+ 5 З, Вычисляются суммы (Хв+ Х 9), (Х 1 о + Х 11), (Х 12 + Х 1 з), (Х 14 + Х 15) и разности (Хв - Х 9), (Х 1 о - Х 11), (Х 12 - Х 1 з), (Х 14 Х 15), Суммы поступают на входы блоков 6 оз сдвига, в котоРых предыдущие результаты с каждымтактом сдвигаются вправо, Разности поступают на элементы 7 оз задержки, с которых предыдущие результаты через переключатели 2 оз поступают на элементы Оо, 84, 8 в и 812. Аналогично процессор работает следующие два такта: переключатели 1 оз и 2 оз переходят в следующие состояния, вычисляются суммы и разности очередных входных пар и заполняются блоки сдвига. После этого первый этап преобразования завершается, заканчивается первый цикл работы процессора.На пятом такте переключатели 1 оз вновь устанавливаются в первое состояние, переключатели 2 о - 2 з в четвертое. На вход процессора поступает новая входная выборка и первые восемь сигналов через переключатели 1 оз, поступают на входы СУММатОРОВ-ВЫЧИтатЕЛЕй; Х И Х 1- 5 о, Х 2 И Хз.51; Х 4 и Х 5-+52; Хби Х 7- 5 з, Вычисляются сУммы (Хо + Х 1), (Х 2 + Хз), (Х 4 + Х 5), Хв+ Х 7) и разности (Хо - Х 1), (Х 2 - Хз), (Х 4 - Х 5), (Х 6 - Х 7). Разности поступают на элементы 7 о - 7 з задержки, с которых предыдущие результаты через переключатели 2 оз поступают на элементы 8 з, 87, 811 и М задержки. Суммы поступают на входы блоков 6 о - 6 з, с выходов которых результаты, полученные на первом татке,поступают на входы сумматоров-выЧИтатЕЛЕй 54 И 55,т.Е. (Хо+ Х 1) И(Х 2+ХЗ) -+54; (Х 4+ Х 5) и(Х 6+ Х 7) - 55. ВычисляютсЯ суммы (Хо+ Х 1+ Х 2+ Хз), (Х 4+ Х 5+ Х 6+ Х 7) и разности (Хо + Х 1) - (Х 2 + Хз), (Х 4+ Х 5) - (Х 6+ Х 7). Суммы поступают на входы блоков 64 и 65 сдвига, а разности - на элементы 74 и 75 задержки,На шестом такте переключатели 1 оз устанавливаются во второе состояние, а переключатели 2 о - 2 з - в первое. Нулевая группа сумматоров-вычитателей работает аналогично описанному, продолжая преобразование над второй входной выборкой, причем при поступлении информации на элементы 7 оз задержки предыдущая инфоРмацид постУпает на элементы 8 о, 84, 8 в, 812 задержки, с которых на 16-й, 17-й, 18-й и 19-й выходы поступает часть конечных ре, зультатов преобразования: У 16, У 17, У 1 в й У 19На восьмом такте заканчивается первый этап преобразования над второй входной выборкой и второй этап преобразования над первой входной выборкой.На седьмом и восьмом тактах из элементов задержки 81, 85, 89, 81 з и 82, 86, 810, 814 соответственно на 20-й, 21-й, 22- й, 23-й, 24-й, 25-й, 26-й, 27-й выходы процессора поступают очередные результаты преобразования. На следующих тактах на выходы процессора поступают очередные результаты преобразования. На девятом такте на вход процессорапоступает новая входная выборка, промежуточные результаты передаются из одной группы сумматоров-вычитателей в другую, в 5 работу включается 2-я группа сумматороввычитателей. Переключатели 1 оз - в первом состоянии, а переключатели 2 оз - в четвертом. Информация из блоков сдвига 64 и 65 поступает на вход сумматора-вычитате ля 56; (Хо+ Х 1+ Х 2+ ХЗ) и (Х 4+ Х 5+ Х 6+ Х 7)66. ВычислЯетсЯ сУмма(Хо++ Х 7), котоРаЯ поступает на элемент задержки 77, и разнОсть (Хо ++ Хз) - (Х 4 + Х 7) котоРаЯ поступает на элемент задержки 76. На деся том такте гРУппы 1 о,1 СУмматоРов-вычитателей продолжают преобразование второй и третьей входных выборок.В работу включается переключатель 26.который под действием управляющих сигналов от блока синхронизации устанавливается в первое состояние.а вход сумматора-вычитателя 56 изблоков 64 и 65 сдвига поступает следуюЩая информация: (Хв+ Х 9+ Х 1 о+ Х 11) и (ХТ 2+ Х 1 з+ 25 + Х 14+ Х 15) -56, Вычисляется сумма (Хв++ Х 15) и разность (Хв + , + Х 11) - (Х 12 + . + Х 15), Разность поступает на элемент задержки 76 с которого предыдущая информация через переключатель 26 поступает на элемент 824, задержки, а сумма - на элемент 77 задержки,с которого предыдущая информацияпоступает на элемент 76 задержки.Преобразование следующих входныхвыборок продолжается аналогично преобразованию первой входной выборки,На одиннадцатом такте переключатель26 устанавливается во второе состояние, переключатели 27, 31, 41 - в первое состояние, На вход сумматора-вычитателя поступает 40 следующая информациЯ:(Х 16++ Х 19) и(Х 20+ Х 2 з) и разность (Х 16++ Х 1 э) - (Х 2 о++ Х 2 з), Разность поступает на элемент 76 задержки, с которого предыдущий результата 45 через переключатель 26 передается на элемент 825 задержки, а сумма поступает на элемент.77 задержки, с которого предыдущая информация поступает на второй вход переключателя 41, на первый вход которого поступает информация из элемента 7 в задержки, Через переключатель 4 т на вход сумматора-вычитателя 57 поступает следующая ИмфОрМацИя; (Хо+ ., + Х 7) И (ХВ+ . + Х 16)ф - 57, Вычисляется сумма (Хо ++Х 16) и разность(Хо+ +Х 7)-(Хв ++ Х 16). Сумма через переключатель 31 передается на элемент 79 задержки, а разность - .на третий выход процессора.На двенадцатом такте переключатель 27устанавливается во второе состояние (этотвыход переключателя не используется), переключатели 31 и 41 закрыты. На выход сумматора-вычитателя 56 поступает следующая информация; (Х 24++ Х 27) и (Х 26++ Хз 1)+ 56, Вычйсляется сумма (Х 24+ .Хз 1) и раз нОсть(Х 24+Х 27) - (Х 26+ + Х 31). Разность передается на элемент 76 задержки, откуда предыдущий результат поступает на шестой выход процессора, а сумма - на элемент 77 задержки. 10На тринадцатом такте переключатель 41 устанавливается в первое состояние, переключатель 26 - в четвертое состояние, 27- в. третьем состояние, а 31 - во второе состояние. На вход сумматора-вычислителя 56 поступает результат преобразования второй входной вьборки: (Хо + Х 1 + Х 2 +Хэ ) и(Х 4; + Хб + Хб + Хт ). Вычисляется сумма (Хо ++,+Х 7)и разность(Хо Хз) - (Х 4 +Л 1 + Х 7 ), Разность поступает на элемент 76 задержки, а сумма - на элемент 7 т задержки, с которого предыдущий результат поступает на второй вход переключателя 41, на первый вход которого поступает информация изэлемента 7 в задержки. Таким обра зом, через переключатель 41 на входы сумматора-вычитателя 57 поступает следуЮщая инфОрмация: (Хгб++ Х 2 З) и (Х 24+ .+ + Хз 1). Вычисляется сумма (Хгб ++Хз 1), которая через переключатель 31 поступает на элемент 71 о задержки, и разность (Х 16++ Х 2 з) - (Х 24 + .+ Хзг), которая через переключатель 27 поступает на второй выход процессора, Заканчивается четвертый этап преобразования гад первой входной выборкой.На четырнадцатом такте переключатель 26 вновь устанавливается в первое состояние, переключатель 41 - во втброе, 2 т - в четвертбе, 31 - в третье состояние, На вход сумматора-аычитателя 56 постпает следующая информация; (Хв ++ Х 11) и (Х 12++Х 16), Вычисляется смма(Х в++Х гб) и1разность (Х в ++ Х 11) - (Х 12 + . + Х 16), Разность поступает на элемент 76 задержки, а сумма - на элемент 77 задержки. Пред 45 ыдущий результат с элемента 76 задержки поступает на элемент 824 задержки, информация из которого в свою очередь передается йа четвертый выход процессора. Предыдущая информация с элемента 77 задержки передается на второй вход переключателя 41, на первый вход которого поступает информация с элемента 7 в задер- жки. Так как переключатель 41 во втором состоянии, то на вход сумматора-вычитателя 5 т поступает информация с третьего и четвертого входов переключателя, на которые в свою очередь поступила информация из элементов 79 и 71 о задержки. Сумматорвычитатель 5 т вычисляет сумму (Хо++ Хз 1) и разность (Хо++ Хгб) - (Х 16++ Хзг), Сумма через переключатель 31 поступает на нулевой выход процессора, а разность через переключатель 27 - на первый вход процессора.Таким образом, заканчивается последний этап преобразования над первой входной выборкой, на всех выходах процессора имеются требуемые результаты. Результаты преобразования над следующими входными выборками выдаются через каждые четыре такта работы сумматоров-вычитателей.За базовый объект взято известное устройство (при сравнении необходимо учитывать, что один сумматор-вычитатель по. сложности соответствует двум сумматорам), Базовый обьект, реализованный для длины вектора 2, содержит (2" - 1) сумматоров (что приблизительно соответствует 2" 1 сумматорам-вычитателямпредлагаемого процессора) и может выдавать очередной вектор-результат черезкаждые (2" + 1) тактов,Предлагаемый процессор производит поточную обработку выборок-векторов с перекрытием ва времени. При этом в ста но- вившемся режиме, начиная с 1+1)2" - 2)-го такта, процессор черезкаждые 2" тактов выдает очередной вектор-результат преобразования Хаара (где 2" - длина выборки- вектора, а 2 - количествогсумматоров-вычитателей 1 = 1, и). Таким образом, если 1 = п, то при практически равном числе сумматоров (2" сумматороввычитателей в предлагаемом процессоре и (2" - 1) сумматоров в базовом обьекте) предлагаемый процессор на каждый.обрабатываемый вектор затратит 2"(" ) = 2 такта против (2" + 1) тактовв базовом объекте.Если же с = 1, то при практически равном затрачиваемом на обработку времени (2" тактов в предлагаемом процессоре и (2" + +1) тактов в базовом объекте) количество сумматоров-вычитателей в предлагаемом процессоре равно 2 против (2" - 1) суммато- ров в базовом объекте. В случае ч = 2 при22 сумматорах-вычитателях на преобразование первой входнойвыборки требуется 10, а не девять тактов, как при пятнадцати сумматорах в базовом обьекте, а результаты преобразования последующих входных вы- борок получаются через каждые четыре, а не девять тактов как в базовом объекте,Архитектура прОцессора. унифицирована, т.е. дает возможность на базе единой структуры реализовать ряд процессоров с различной степенью сложности.и быстродействия.В предлагаемом процессоре эффективно используются сумматоры-вычитатели.чФормула изобретения Поточно-параллельный процессор Хаара, содержащий группу сумматоров-вычитателей, группу переключателей и блок синхронизации, о т л и ч а ю щ и й с я тем что, с целью повышения быстродействия в него введены 1 групп сумматоров-вычитателей (т = 1, п, й = 2" - размер входной выборки), три группы переключателей, (22) блоков сдвига и две группы элементов задержки, причем )-й (1 = О, 2 -1) информационный вход процессаа соединен с 1-м (1 =) тпос 12+ 2 9 - ) вод 2)/2) информационным входом К-го(К=О аоб 2 - ) вос 1 2)/2 переключателя первой группы, 1-й информационный выход которого (1 = О, 1) соединен с 1-входом одноименного К-го сумматоравычитателя первой группы, выход суммы щго сумматора-вычитателя первой группы через в-й (в =00, 2 -1) блок сдвига соединен- -1с Ь-м (Ь = в вос 1 2) входом ц-го (ц = (в - Ь)/2) сумматора-вычитателя второй группы, выход суммы д -го (д =- 0,2 " ) сумматора-вычитателя г-й (г = 2, т - 1) группы через (п+ 2" - 2" ")-й блок сдвига. соединен с р-м (р= в вод 2) входом с 1-го (ц = (а-р)/2) сумматора-вычитателя (г+1)-й группы, выход суммы единственного сумматора-вычитателя (1+1)-й группы соединен с (2 - 1)-и элементом задержки второй группы, выход которого соединен с первым входом переключателя четвертой группы и входом 2-го элемента задержки второй группы, выход которого соединен с первым входом переключателя четвертой группы, 1-й вйчход которого (1 = 0,1) соединен с одноименным входом единственного сумматора-вычитателя (т+ 1)-й группы, выход которого соединен с информационным входдм пе екгпочателя третьей. группы, 1-й (1 = О, 2 (и1 - 1 выход которогочерез(2+ 1+ 1)-йзлементзадержки второй группы соединен с (1+2)-м информационным входом переключателя четвертой группы, а 2(п-т)-й выход переключателя третьей группы является первым выходом процессора, выход разности последнего сумматора-вычитателя (1+1)-й группы соединен с информационным входом 2 переключателя второй группы, с-й (с = 1, 2" - 1) выход которого является с-м информационным выходом процессора, выход разности 10 б-го (с 1 = 0,2 - 2) сумматора-вычитателя через О-й элемент задержки первой группы связан с информационным входом с 1-го переключателя второй гцппы, Ь-й выход (Ь= 0,2"- 1) )-го О = 0,2 ) переключателя второй группы соединен с входом Г-го (1=2 п +Ь) элемента задержки, с первого по 2 -й выходы (2-2)-го переключателяи второй группы соединены с информационными входами элементов задержки второй 20 группы соответственно с (2" (2 - 2)-го пол-1(2 - 1)-й, выходы которых являются с 5-гоипо 2 "-й информационными выходами процессора, а с (2 П+ 1)-го 2" -й выходы (2 - 2)-го переключателя второй группы являются с (2" + 1)-го (2" )-й информацион:ными выходами процессора, выходы переключателей второй группы с 1-го по (2-1)-й соединены соответственно с информационными входами элементов задержки второй группы соответственно с 1-го по(2" (2-2)+ 2)-й, выходы с первого по (2"(2 - 1)-й элементов задержки второй груйпы являются с 2"-го по (2" + 5)-й -информационными выходами процессора,первый выход блока синхронизации соединен с тактовыми входами с блоков сдвига и элементов задержки первой и второй группы, второй выход блока синхронизации соединен с управляющими входами ,10 переключателей первой и второй групп, третий выход блока синхронизации соединен суправляющими входами переключателейтретьей группы, четвертый выход блока синхронизации соединен с управляющими входами переключателей четвертой группы,