Поточно-параллельный процессор Хаара Советский патент 1992 года по МПК G06F15/332 

Изобретение относится к области ВТ и обработки случайных процессов и может быть использовано в системах цифровой фильтрации, сжатия изображения и выделения признаков, основанных на параллельном алгоритме преобразования Хаара.

Известны устройства, выполняющие конвейерное рационализированное преобразование Хаара для входных выборок длиной N 2П, представляемых последовательными отсчетами.

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

Наиболее близким техническим решением к предлагаемому является устройство для вычисления коэффициентов Хаара, содержащее группу из пятнадцати сумматоров, хранящих в себе информацию до прихода следующей и выполняющих одну операцию (вычитание или сложение) за один такт работы, группу переключателей, состоящую из шестнадцати переключателей, счетчика, схемы ИЛИ и дешифратора. В этом устройстве с целью повышения быстродействия применяется параллельно-последовательный метод обработки. Устройство осуществляет параллельное вычисление коэффициентов Хаара от 16 отсчетов входной выборки цифрового сигнала за девять тактов работы сумматоров.

хл

о ч

Однако известное устройство не производит поточную обработку векторов, т.е. для выполнения преобразования над следующей входной выборкой цифрового сигнала потребуются еще девять тактов. При этом сумматоры работают с неполной загруженностью, т.е. используются не эффективно, Если реализовать известное устройство для входных выборок-векторов длиной N 2, то следует ожидать, что преобразование Хаара над каждым вектором будет выполняться за ( + 1) тактов и потребуется (2п-1) сумматоров.

Недостатками известного устройства являются низкое быстродействие и не эффективное использование аппаратуры.

Цель изобретения -повышение быстродействия за счет применения поточной обработки векторов длиной N - 2П и унификация процессора, заключающаяся в реализации на 2l (t 1, п-1) сумматорах-вы- читателях в зависимости от требуемого быстродействия.

В поточно-параллельный процессор Хаара, содержащий группу сумматоров-вычи- тателей, группу переключателей и блок синхронизации, введены t групп суммато- ров-вычитателей, три группы переключателей, блоки сдвига и две группы элементов задержки, Первая группа переключателей содержит 2 переключателей с входами и двумя выходами, вторая группа содержит 21 переключателей с одним входом и выходами, третья группа-один переключатель с одним входом и (2(n-t)-1) выходами, четвертая - один переключатель с 2(n-t) входами и двумя выходами, каждый из блоков сдвига состоит из 2n l последовательно соединенных регистров сдвига, первая группа элементов задержки состоит из (2 + 2(n-t-1) элементов, а вторая группа - из ((2t-2) + + ) элементов, i-я и последняя (t+1)-a (I

1, t) группы сумматоров-вычитателей стоят соответственно из

сои одного сум- матора-вычитателя, причем J-й (j 0, 2 -1) информационный вход процессора соединен с Ьм (I j mod 2 -f- 2 0 - J mod 2т)/21) информационным входом К-го (К (j mod 2r - - j mod2)/2) переключателя первой груп- пы. 1-й информационный выход которого (I 0,1) соединен с 1-м входом одноименного К-го сумматора-аычитателя первой группы, выход суммы т-го сумматора-вычитателя первой группы через m-й (т 0, -1) блок сдвига соединен с b-м (Ь т mod 2) входом q-ro (q (т - b)/2) сумматора-вычитатедя второй группы, выход суммы HpJ.UlO,2 г ) суммзтора-вычитателя r-й (г 2, t-1) группы через {т + 2 - )-й блок сдвига соединен с Р-м (Р т, mod 2) входом q-ro

(q

m

) сумматора-вычитателя (г+ 1)-й

10

15

20

25

30

35

группы, выход суммы единственного сумматора-вычитателя (гн-1)-й группы соединен с (2т-1)-м элементом задержки второй группы, выход которого соединен с первым входом переключателя четвертой группы и с входом 21-го элемента задержки второй группы, выход которого соединен с первым входом переключателя четвертой группы, 1-й выход которого (I 0, 1) соединен с одноименным входом единственного сумматора- вычитателя (:+1)-й группы, выход которого соединен с информационным BxoflOM jiej jano4 aj fl третьей группы, 1-й (i 0, 2 (n-t-1) - 1) выход которого через ()-й элемент задержки второй группы соединен с (i )-2)-м информационным входом переключателя четвертой группы, a 2(n-t-1)- й выход переключателя третьей группы является первым выходом процессора, выход разности последнего сумматора-вычитателя (г+1)-й группы соединен с информационным входом 2{-го переключателя второй группы, с-й (с 1, 2 - 1) выход которого является с-м информационным выходом процессора, выход разности d-ro (d 0,2l - 2) сумматора-вычитателя через d-й элемент задержки первой группы связан с информационным входом d-ro переключателя гяарцй, группы, h-й (h 0, 2rt r - 1) выход j-ro 0 0. 2 переключателя второй группы соединен с входом f-ro (f j, 2lvt-i- h) элемента задержки. С первого по ()-й выходы (21-2)-го переключателя второй группы связаны с информационными входами с ( (21 - 2))-го по ( - 1)-й элементов задержки второй группы, выходы которых являются с 5-го по

in-t-1 ...

2 -и выходами процессоров, а с(2 +1)-го

АО по выходы (2 2)-го переключателя второй группы являются с( + 1)-го по()-й информационными выходами процессора. Выходы переключателей второй группы соответственно с 1-го по (21-1)-й соединены с

45 входами с 1-го по ( (21 - 2) + )-й элементов задержки второй группы. Выходы с 1-го по ( (21 - 1)-й элементов задержки второй группы являются с 2п-го по( + 5)-й выходами процессора.

50 Блок синхронизации состоит из генератора тактовых импульсов и трех счетчиков, причем выход генератора тактовых импульсов соединен как с управляющими входами блоков сдвига и элементов задержки первой

55 и второй групп, являясь первым выходом блока синхронизации, так и с тремя счетчиками блока синхронизации, причем первый счетчик по mod с (n-т) разрядной шиной на выходе, которая является вторым выходом блока синхронизации и соединена с

управляющими входами переключателей первой и второй групп, второй счетчик по mod (2 (n-t) -1) с Iog2 2(n-t) разрядной шиной на выходе, которая является третьим выходом блока синхронизации и соединена с управляющими входами переключателя третьей группы, третий счетчик по mod (n-t) с Iog2 (n-t) разрядной шиной на выходе, которая является четвертым выходом блока синхронизации и соединена с управляющими входами переключателя четвертой группы.

На фиг.1 представлена схема поточно-параллельного процессора Хаара для последовательности входных выборок-векторов размерами N 2П для 21 сумматоров-вычита- телей, где t 1, п-1; на фиг.2 - схемы поточно- параллельных процессоров Хаара для последовательности входных выборок-векторов размерами N 25 для 21 суммэторов-вы- читателей, когда t 3,2,1 соответственно; на фиг.5 - граф последовательности вычисления коэффициентов Хаара для N 2 32; на фиг.6 - схемы состояний переключателей с первой по четвертую групп и последнего переключателя второй группы для процессора при t 3.

Поточно-параллельный процессор Хаара (фиг.1) содержит 2П информационных входов Х0 - Х2Ч-1 и 2П информационных выходов Yo - Ya11-, первую группу переключателей 10 - 21 1- (, вторую группу переключателей 20 - 22 третью группу 3i и четвертую группу 4i, 21 сумматоров-вы- читателей 5о - , разбитых на (t + 1) групп 10 - It, 1-я группа содержит 2 и сум- маторов-вычитателей, t-я группа содержит один сумматор-вычитатель, блоки 60 - 62-3 сдвига с 2n l последовательно соединенными регистрами сдвига, элементы задержки первой группы 70 - 7(2+2(n-t-i)), элементы задержки второй группы 80-82 {21-2)) и блок 9 синхронизации, который состоит из генератора 10 тактовых импульсов, счетчика 11 по mod 2ПЛ счетчика 12 по mod (2x(n-t)-1), счетчика 13 по mod(n-t) и имеет четыре выхода 14-17, причем последние три выхода являются соответственно (п-т.)-разрядн ой, Iog22(n-t) разрядной и 1од2(п-т)-разрядной шинами.

Поточно-параллельный процессор Хаара при t 3 (фиг.2) содержит тридцать два информационных входа Х0-Хз1, тридцать два информационных выхода У0-Уз1, переключатели первой группы 10-1з, переключатели второй группы 20-2, переключатель третьей группы, 3i, переключатель четвертой группы 4i, суммзторы-вычитатели Бо-В, блоки 6g-6s сдвига, состоящие из четырех последовательно соединенных регистров сдвига, элементы задержки первой группы

70-7ю, элементы задержки второй группы 80-825, блок 9 синхронизации, состоящий из генератора 10 тактовых импульсов с выходом VI, счетчика 11 no mod А, с 2-разрядной

шиной 15 на выходе, счетчика 12 по mod 3 с 2-разрядной шиной 15 на выходе, счетчика 13 по mod 2 с одноразрядной шиной на выходе 17.

Поточно-параллельный процессор Хаа0 ра при t 2 (фиг.2) содержит информационные входы Хо-Хз, информационные выходы У0-Уз1, переключатели первой группы 10 и 1i, переключатели второй группы 20-2з, переключатель третьей группы 3i, пе5 реключатель четвертой группы 4i, суммато- ры-вычитэтели 50-5з, блоки 60 и 6i сдвига, состоящие из восьми регистров сдвига, элементы задержки первой группы 70-7в, элементы задержки второй группы 80-8i9, блок

0 9 синхронизации, состоящий из генератора 10 тактовых импульсов с выходом 14, счетчика по mod 8 с 3-разрядной шиной 15 на выходе, счетчика по mod 5 с 3-разрядной шиной 6 на выходе, счетчика по mod 3 с

5 2-разрядной шиной 17 на выходе.

Поточно-параллельный процессор Хаара при t - 1 (фиг.4) содержит информационные входы Х0-Хз1 и информационные входы Yo-Yai, переключатель первой группы 10,

0 переключатели второй группы 20 и 2-|, переключатель третьей группы 3, переключатель четвертой группы 4i, сумматоры-вычитатели 5о и 5i. элементы задержки второй группы 8о-8у, эпементы за5 держки первой группы 70-7з, блок 9 синхронизации, состоящий из генератора 10 тактовых импульсов с выходом 14, счетчика по mod 16 с 4-разрядной шиной 15 на выходе, сиетчика по mod 7 с 3-разрядной

0 шиной на выходе 16, счетчика по mod 4 с 2-разрядной шиной на выходе 17.

Каждый сумматор-вычитатель без внутренней памяти состоит из двух сумматоров (один для выполнения операции сложения,

5 другой для вычитания).

Каждый блок сдвига состоит из последовательно соединенных регистров сдвига

Каждый элемент задержки запоминает

0 поступившее число до прихода следующего На фиг.5 рядом с каждой базовой операцией двухточечного преобразования указан номер такта, во время которого она выполняется, при t 3, т.е. для 23 суммато5 ров-вычитателей.

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

Вычисление коэффициентов Хаара основано на разработанном параллельном алгоритме преобразования Хаара над последовательностью входньгх выборок, представляемымх векторами Xi размером .

Изобретение относится к вычислительной технике и цифровой обработке сигналов. Цель изобретения - повышение быстродействия за счет применения поточной обработки векторов длиной N 2П и унификация процессора, заключающаяся в реализации процессора- йа 2l (t 1. п-1) сум- маторах-вычитателях в зависимости от требуемого быстродействия, Указанная цель достигается тем, что ё поточно-параллельный процессор Хаара, содержащий группу сумматоров-вычитателей, группу переключателей и блок синхронизации, введены t групп сумматоров-вычитателей (t 1. п-1, N 2П - размер входной выборки), три группы переключателей, (2е - 2) блоков сдвига и две группы элементов задержки. Поточно-параллельный процессор Хаара может быть использован в системах цифровой фильтрации, сжатия изображения и выделения признаков, основанных на параллельном алгоритме преобразования Хаара. 6 ил. (Л С

Yf MNXi(l 1,2,...)

(D

где HN - матрица преобразования Хаара: YI - преобразованные выборки. Алгоритм строится посредством факто-

ризации матрицы HN в виде произведения

слабо заполненных матриц

HN-H TflH«T«...

2J I

HO © Vs ©TN-2J

где Э - прямая сумма матриц;

IN-2 - единичная матрица порядка

VsO)

1 1 1 -1

Т® - матрица перестановок, определяв- зо мая следующим образом:

-.i

-1

Sii1) РаГ.1 ФТ2п-2- н , (4)

где S2 - матрица оператора двоично-инвер- сной перестановки порядка

PZ - матрица оператора полной тасовки порядка 2 .

Пример. Факторизация матрицы преобразования Хаара при N 2.

())

нт.

1 1 1 о

1 -1 I

Jtl, 1 L rj| л

о

I

(«

1100 1-100 0011 001-1

лсз;

В соответствии с (2) преобразование Ха- ара над одной входной выборкой X) производится в п этапов, т.е.

Y..

(Н(п-1)т(п-1)(н(п)т(п)х, ) )...).

Сущность алгоритма заключается в следующем.

Алгоритм состоит из К 2l (t 1, п-1, 2П - длина входной выборки) взаимодействующих между собой ветвей. Ветви алгоритма условно разбиваются на (t-t-1) групп. В 1-ю (1 О, М) входят ветвей, а в I t-ю группу входит одна 21-я ветвь. На очередном i-м

цикле алгоритма (i 0, 1), состоящем из

шагов (шагу алгоритма соответствует такт работы сумматоров-вычитателей в предлагаемом процессоре), параллельно

в каждой группе ветвей ((I 0, 1t -1),

{ min {t, i+1}) выполняется 1-й этап преобразования, т.е. умножение матрицы на очередной вектор, являющийся результатом работы предыдущей группы ветвей на предыдущем цикле, а при 1 0- новой входной выборкой Xi. Итак, на каждом цикле начинает обрабатываться новая входная выборка. Начиная с t-ro цикла работы, на каждом цикле, кроме операций, исполняемых в группах ветвей I 0, t-1, параллельно (одновременно) в t-й группе ветвей (т.е. в ветви) выполняются последовательно этапы t, t+1п-1 преобразования Хаара

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

5 одного шага в t-й ветви операции не выполняются. Таким образом, преобразование одной входной выборки осуществляется за ((t ь-1) () - 2) шагов и, при этом, начиная с ((t + 1) - 2}то шага через каждые 2П

0 шагов формируется результат преобразования очередной входной выборки.

Рассмотрим работу процессора на примере последовательности входных выборок

5 размерами N 25 для 23 сумматоров-вычитателей в нулевую группу входят четыре сумматорз-вычитателя, в первую - два сум- матора-вычитателя, во вторую и третью - по одному сумматору-вычитателю. Процессор

0 содержит четыре переключателя в первой группе, восемь переключателей во второй, один - в третьей и один в четвертой группах, шесть блоков сдвига, по 2А последовательно соединенных регистров сдвига в каждом из

5 них, двенадцать элементов задержки в первой группе, двадцать шесть элементов задержки во второй группе и блок синхронизации, состоящий из генератора тактовых импульсов, счетчика по mod A, счетчика no mod 3 и счетчика по mod 2.

На первом такте при поступлении на управляющие входы переключателей сигнала от блока синхронизации они устанавливаются в первое состояние и подклю5 чают к входам сумматоров-вычитателей lo-й группы первые восемь информационных входов процессора: Х0 и Xi Х2 и Хз- 5i; Х4 и Х4 Хб и X 5з Вычисляются суммы (Х0 + Xi), (Х2 + Хз), (Х4

0 + Xg) (Хб + Х7) и Разности (Х0 - Xi), (X2 - Хз).0 (Х4 - Xs). (Хе - X). Суммы поступают на входы блоков 60-6з сдвига, а разности - на элементы задержки.

На втором такте по сигналу от блока

5 синхронизации переключатели устанавливаются во второе состояние, переключатели 20-2Л - в первое, а на входы сумматоров-вычитателей поступают следующие четыре пары входных сигналов: Хв и Хд , Хю и Хп Xia и Xi3 62: Хц . Вычисляются суммы (Xs + Xg), (Хю+ + Хц), (Xi + Xia). (Xi4 + Xis) и разности (Хв - -Xg). (Хю - Хц), (Xi2 - Xi3). (Xi4 - Xis). Суммы поступают на входы блоков 6о-6з сдвига, в которых предыдущие результаты с каждым тактом сдвигаются вправо. Разности поступают на элементы 70-7з задержки, с которых предыдущие результаты через переключатели 20-2з поступают на элемен0

0

5

ты 80, 84, 8в и 8i2. Аналогично процессор работает следующие два такта: переключатели и 20-2з переходят в следующие состояния, вычисляются суммы и разности очередных входных пар и заполняются блоки сдвига. После этого первый этап преобразования завершается, заканчивается первый цикл работы процессора.

На пятом такте переключатели вновь устанавливаются в первое состояние, переключатели 20-2з в четвертое. На вход процессора поступает новая входная выборка и первые восемь сигналов через переключатели , поступают §на входы сумматцров-вычитателей; XI, и Xi- 5ol Xa и Х4 и ХБ , Хе и 5з. Вычисляются суммы (Х о + Xi), (Х2 + Хз), (Х4 + ХБ), ХЈ + XV) и разности (Хо - Xi). (Х2 - Хз), (Xii - ХБ). (Хе - Ху). Разности поступают на элементы 70-7з задержки, с которых предыдущие результаты через переключатели 2о-2з поступают на элементы 8з. 8, 8ц и 815 задержки. Суммы поступают на входы блоков 60-6з, с выходов которых результаты, полученные на первом татке, поступают на входы сумматоров-вы- читателей 54 и 5s. т.е. (Х0 + Xi) и (Х2 + Хз) - (Х4 + ХБ) и (Хе + XT) - 5s. Вычисляются суммы (Хо + Х1 + Х2 + Хз),(Х4 + Х5+Хб + Х7) и разности (Х0 + Xi) - (Х2 + Хз), (Х4 + Х5) - (Х6 + X). Суммы поступают на входы блоков 64 и 6s сдвига, а разности - на элементы 7/j и Б задержки.

На шестом такте переключатели 10-1з устанавливаются во второе состояние, а переключатели - в первое. Нулевая группа сумматоров-вычитателей работает аналогично описанному, продолжая преобразование над второй входной выборкой, причем при поступлении информации на элементы задержки предыдущая информация поступает на элементы 80, 84, 8в, 8i2 задержки, с которых на 16-й, 17-й, 18-й и 19-й выходы поступает часть конечных результатов преобразования: Yie, Yiy, Yis и

Y19.

На восьмом такте заканчивается первый этап преобразования над второй входной выборкой и второй этап преобразования над первой входной выборкой.

На седьмом и восьмом тактах из элементов задержки 8i, 85. 89, 813 и 82, 8е, 8ю. 814 соответственно на 20-й, 21-й, 22- й, 23-й, 24-й, 25-й, 26-й. 27-й выходы процессора поступают очередные результаты преобразования. На следующих тактах на выходы процессора поступают очередные результаты преобразования.

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

работу включается 12-я группа сумматоров- вычитателей. Переключатели 1о-1з- в первом состоянии, а переключатели 20-2з - в четвертом. Информация из блоков сдвига 64 и 6s поступает на вход сумматора-вычитате0 ля 5е: (Х0 + Xi + Х2 + Хз) и (Х4 + ХБ + Хе + Х . Вычисляется сумма (Х0 +... + X), которая поступает на элемент задержки 7, и разность (Х0 + ... + Хз) - (Х4 + ...Х), которая поступает на элемент задержки 7в. На деся5 том такте группы 0, И сумматоров-вычитателей продолжают преобразование второй и третьей входных выборок.

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

t a вход сумматора-вычитателя 5е из блоков 64 и 6s сдвига поступает следующая информация: (Ха + Хд + Хю + Xi 1) и (Xi2 + Xi3+

5 + Xi4 + ) . Вычисляется сумма (Хв + ... + Xis) и разность (Хв + ... + Хц) - (Xi2 + ... + XIB). Разность поступает на элемент задержки 7е с которого предыдущая информация через переключатель 2е поступает на эле0 мент 824, задержки, а сумма-на элемент 7 задержки.с которого предыдущая информация поступает на элемент 7в задержки.

Преобразование следующих входных выборок продолжается аналогично преоб5 разованию первой входной выборки.

На одиннадцатом такте переключатель 2е устанавливается во второе состояние, переключатели 2, 3i, 4i - в первое состояние. На вход сумматора-вычитателя поступает

Q следующая информация: (Хш+... + Xig) и (Х20 +... + Х2з) 5е. Вычисляется сумма (Хш + ... + Хаз) и разность (Xie + ... + Xig) - (Хао + ... + Х2з). Разность поступает на элемент 7е задержки, с которого предыдущий результата

5 через переключатель 2б передается на элемент 825 задержки, а сумма поступает на элемент 7 задержки, с которого предыдущая информация поступает на второй рход переключателя 4. на первый вход которого

Q поступает информация из элемента 7в задержки. Через переключатель 4| на вход сумматора-вычитателя 5 поступает следующая информация: (Хо + .-. + Х) и (Xe+... + Xie) . Вычисляется сумма (Х0 + ... +Хш) и

5 разность (Х0 +... + X) - (Ха +... + Xie). Сумма через переключатель 3i передается на элемент 7э задержки, а разность - на третий выход процессора.

На двенадцатом такте переключатель 2у устанавливается во второе состояние (этот

выход переключателя не используется), переключатели 3i и 4i закрыты. На выход сум- матора-вычитателя 5б поступает следующая информация: (Х24 + ... + Х2) и (Х28 + ... + Xsih 5б. Вычисляется сумма (Х24 + ... ХзО и раз- ность (Х24 +... Х2) - (Х28 + ... + Хз1). Разность передается на элемент 7е задержки, откуда предыдущий результат поступает на шестой выход процессора, а сумма - на элемент 7 задержки.

На тринадцатом такте переключатель 4i устанавливается в первое состояние, переключатель 2б - в четвертое состояние, 2 - в третьем состояние, a 3i - во второе состояние. На вход сумматора-вычислителя 5е по- ступает результат преобразования второй входной выборки: (Хо N Xi + Х21 + Хз ) и (Хл + Xs + XG + ). Вычисляется сумма (Х0 + +... + X ) и разность (Х0 + ... + Х3 ) - (Хл + ... ..,+ ). Разность поступает на элемент 7е задержки, а сумма - на элемент 7у задержки, с которого предыдущий результат поступает на второй вход переключателя 4i, на первый вход которого поступает информация из элемента 7в задержки. Таким обра- зом, через переключатель 4i на входы сумматора-вычитателя 5 поступает следующая информации: (Xie4 ... -Х2з)и (Х24 + ...+ + ХзО- Вычисляется сумма (Xie + ... +ХзО, которая через переключатель Зт поступает на элемент 7ю задержки, и разность (Хш +... ... + Х2з) - (Хгд н ... + ХзО, которая через переключатель 2 поступает на второй выход процессора. Заканчивается четвертый этап преобразования над первой входной выборкой.

На четырнадцатом такте переключатель 2б вновь устанавливается в первое состояние, переключатель 4i - во второе, 2 - в четвертое. 3i - в третье состояние. На вход сумматора-вычитателя 5е поступает следующая информация: (Хв + ... + X ц) и (x i + ... + x ls). Вычисляется сумма (х в + ... + X is) и разность (Х з + ... + Xfii) - (X i2 + ... + x ls). Разность поступает на элемент 7е задерж- ки, а сумма - на элемент 7 задержки. Предыдущий результат с элемента 7е задержки поступает на элемент 824 задержки, информация из которого в свою очередь передается на четвертый выход процессора. Предыдущая информация с элемента 7 задержки передается на второй вход переключателя 4i, на первый вход которого поступает информация с элемента 7в задержки. Так как переключатель 4t во втором состоянии, то на вход сумматора-вычитателя 5 поступает информация с третьего и четвертого входов переключателя, на которые в свою очередь поступила информация из элементов 7д и 7ю задержки. Сумматор

вычитатель 5 вычисляет сумму (Х0 + ... + ХзО и разность (Х0 + ... + Х1б) - (Xie + ... + ХзО. Сумма через переключатель 3i поступает на нулевой выход процессора, а разность через переключатель 2 - на первый вход процессора.

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

За базовый объект взято известное устройство (при сравнении необходимо учитывать, что один суммаюр-вычитзтель по сложности соответствует двум сумматорам) Базовый объект, реализованный для длины вектора 2П, содержит (2п-1) сумматоров (что приблизительно соответствует сумма- торам-вычитателям предлагаемого процессора) и может выдавать очередной

вектор-результат через каждые (2

ТОО.

п-1

+ 1)так

Предлагаемый процессор производит поточную обработку выборок-векторов с перекрытием во времени. При этом в установившемся режиме, начиная с ((t+1)2 - 2)-го такта, процессор через каждые тактов выдает очередной вектор-результат преобразования Хаара (где 2П - длина выборки- вектора, а 21количество сумматоров-вычитателей t 1, п-1) Таким образом, если t п-1, то при практически равном числе сумматоров ( сумматоров- вычитателей в предлагаемом процессоре и (2п-1) сумматоров в базовом объекте) предлагаемый процессор на каждый обрабатываемый вектор затратит 2 такта0 против (2П + 1) тактов в базовом объекте. Если же t 1, то при практически равном затрачиваемом на обработку времени ( тактов в предлагаемом процессоре и ( + +1) тактов в базовом объекте) количество сумматоров-вычитателей в предлагаемом процессоре равно 21 против (2п-1) сумматоров в базовом объекте. В случае N 24 при 22 сумматорах-вычитателях на преобразование первой входной выборки требуется 10, а не девять тактов, как при пятнадцати сумматорах в базовом объекте, а результаты преобразования последующих входных выборок получаются через каждые четыре, а не девять тактов как в базовом объекте.

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

В предлагаемом процессоре эффективно используются сумматоры-вычитатели.

Формула изобретения Поточно-параллельный процессор Хаа- ра, содержащий группу сумматоров-вычита- телей, группу переключателей и блок синхронизации, отличающийся тем, что, с целью повышения быстродействия в него введены t групп сумматоров-вычитате- лей (t 1, п-1, N 2П - размер входной выборки), три группы переключателей, (2l ± 2) блоков сдвига и две грутш элементов задержки, причем j-й О 0, 2 -1) информационный вход процессора соединен с 1-м (I j mod 2 + 2 0 - j mod 2)/21) информационным входом К-го (К 0 mod 21 - j mod 2)/2 переключателя первой группы. 1-й информационный выход которого (I - 0, 1) соединен с 1-входом одноименного К-го сумматора- вычитателя первой группы, выход суммы т- го сумматора-вычитателя первой группы через m-й (т ) блок сдвига соединен с Ь-м (Ь т mod 2) входом q-ro (q (т - b)/2) сумматора-вычитателя второй группы, вы- ход суммы д -го (б 0,21-г 1) сумматора-вычитателя r-й (г 2, t-1) группы через (т+ - - )-й блок сдвига соединен с р-м (р т mod 2) входом q-го (q (т-р)/2) сумма- тора-вычитателя (г+1)-й группы, пыход сум- мы единственного сумматора-вычитателя (х+1)-й группы соединен с (21 - 1)-м элементом задержки второй группы, выход которого соединен с первым входом переключателя четвертой группы и входом 2 -го элемента задержки второй группы, аы- ход которого соединен с первым входом переключателя четвертой группы, 1-й выход которого (I 0,1) соединен с одноименным входом единственного сумматора-вычитателя (t+ 1)-й группы, выход которого соединен с информационным входом переключателя третьей группы, 1-й 0 0, 2 (n-t-1) - 1) выход которого через (2Ј+ + 1)-й элемент задержки второй группы соединен с (Н-2)-м информа-

0

5 0 5 о

5

О

ционным входом переключателя четвертой группы, а 2(п-т.-1)-й выход переключателя третьей группы является первым выходом процессора, выход разности последнего сумматора-вычитателя (t-H)-u группы соединен с информационным входом 2 переклю- чателя второй группы, с-й (с 1, 2П - 1) выход которого является е-м информационным выходом процессора, выход разности d-ro (d 0,2l - 2) сумматора-вычитателя через d-й элемент задержки первой группы связан с информационным входом d-ro переключателя второй группы, h-й выход (h 0, - 1) J-ro (j переключателя второй группы соединен с входом f-ro (f J2n +h) элемента задержки, с первого по выходы (2-2)-го переключателя второй группы соединены с информационными входами элементов задержки второй группы соответственно с (2n (21 - 2)-го по ( - Я-й, выходы которых являются с 5-го по -и информационными выходами процессора, а с ( + 1)-го 2пЧ-й выходы (2 -2)-го переключателя второй группы являются с ( + 1)-го ()-й информационными выходами процессора, выходы переключателей второй группы с 1-го по ()-й соединены соответственно с информационными входами элементов задержки второй группы соответственно с 1-го по (2ПЧ (21-2) + )-й, выходы с первого по (2ГИ (21-1)-й элементов задержки второй группы являются с 2п-го по ( + 5)-й информационными выходами процессора, первый выход блока синхронизации соединен с тактовыми входами с блоков сдвига и элементов задержки первой и второй группы, второй выход блока синхронизации соединен с управляющими входами переключателей первой и второй групп, третий выход блока синхронизации соединен с управляющими входами переключателей третьей группы, четвертый выход блока синхронизации соединен с управляющими входами переключателей четвертой группы.

- -рП&ЛМ)

т4 i i i .

-ЈЗИ

во-/г -2 й

2Л

2-;

X

f

)

)

ТГхт ;t,

Pail

ЈЈЈЈЈ ЈrrЈ ЈЈЈЈ Јs Ј tf ff

i i м i j и и

Х.КХЧЧ iS5jURtv

l069Sil

о о

со

LO ГUOUJt ЛUDUfC д|

1069SZ.I.

%N

И.Дербак

Ъ

/

Составитель А.Галантерян Техред М.Моргентал

Э $

Ј

Корректор Л.Лукач