Параллельный процессор Хаара Советский патент 1991 года по МПК G06F17/14 G06F19/00 

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

Цель изобретения - повышение быстродействия путем применения нового параллельного алгоритма преобразования Хаара.

На фиг.1 представлена схема параллельного процессора Хаара для последовательности входных выборок векторов размерами N 24 16; на фиг.2 - граф последовательности вычисления коэффициентов Хаара для N 16; на фиг.За и б - схемы состояний переключателей первой и второй групп соответственно.

Параллельный процессор Хаара (фиг.1) содержит шестнадцать информационных входов, на которые поступают отсчеты входного вектора (Xo(t) - X(t), и шестнадцать информационных выходов, на которых получаются коэффициенты Хаара (Yo(t-4) - Yi5()), первую группу коммутаторов 1о 1б, вторую группу коммутаторов , восемь сумматоров-вычитателей Зо-З, разбитых на четыре группы: нулевая группа lo содержит четыре сумматора-вычитателя, первая группа И - два, вторая и третья группы 2 и з - по одному сумматору-вычитате- лю.

Устройство содержит также первую группу блоков задержки, вторую группу блоков задержки, блок 6 синхронизации, содержащий генератор 7 тактовых импульсов и делительл 8 частоты на два.

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

СП

с

о о VJ

о

СА

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

Каждый блок задержки первой группы 4| содержит один регистр сдвига и запоминает поступившее число на один такт работы сумматоров-вычитателей. Каждый блок задержки второй группы 5| так же состоит из одного регистра сдвига и запоминает поступившее число на один такт работы сумматоров-вычитателей, так как гН-3 1.

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

Переключатели первой и второй групп принимают первое или второе состояние (на фиг.З показаны римскими цифрами I и II) в зависимости от управляющего сигнала О или 1 с второго выхода 10 блока 6 синхронизации.

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

(l 1,2,...),

О)

где HN - матрица преобразования Хаара; YI - преобразованные выборки.

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

НМ .. (2)

2-й

-V ©lN-2J

(3)

где ®- обозначает прямую сумму матриц; - единичная матрица порядка N21;

15

vs(

В (2)г - матрицы перестановок, определяемые следующим образом.

20

тО)(р2©52 )х

-1

xP2J + 1 6H2n-2l+1 (14)

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

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

Для примера рассмотрим факторизацию матрицы преобразования Хаара при N

2 ж н® н® т(3 ).

где

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

Y, ((H®-...(H(n-1)(H(n) .уМ. xfi ...).

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

Алгоритм состоит из К 2П взаимодействующих между собой ветвей. Ветви алгоритма условно разбиваются на о групп. В

l-ю группу (1 0,1п-2) входят ветвей,

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

0,1t-1 (t мин {п-1,1+1}) выполняется 1-й

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

работы предыдущей группы ветвей на предыдущем цикле, а при I 0 - новой входной выборкой XI.

Итак, на каждом цикле, т.е. через шаг, начинает обрабатываться новая входная выборка. Начиная с п-го шага в 2 -йветви алгоритма (в n-й группе) через один шаг выполняется последний (п-1)й этап преобразования Хаара, над очередным вектором результатов, полученных в(2п 1-1)-й ветви. Тким образом, преобразование одной входной выборки осуществляется за п шагов, и

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

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

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

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

размерами N 24 16. В этом случае, процессор содержит четыре группы сумматоров-вычитателей: в нулевую группу входят четыре сумматора-вычитателя, в первую группу - два сумматора-вычитателя, во вторую и в третью - по одному сумматору-вы- читателю. Процессрр содержит семь коммутаторов в первой группе, четыре - во второй группе, тринадцать блоков задержки в первой группе, задерживающих информацию на один такт работы сумматоров-вычитателей, восемь блоков задержки во второй группе, задерживающих информацию также на один такт (так как n-l-З 1 при п 4, I 0) и блок синхронизации, содержащий

генератор тактовых импульсов и делитель частоты на два.

С каждым тактом на синхронизирующие входы блоков задержки первой и вто

рой групп поступают сигналы от генератора 7 тактовых импульсов блока 6 синхронизации, запоминая информацию на один такт работы сумматоров-вычитателей. На первом такте при поступлении на синхронизи- рующие входы 10 коммутаторов 2о-2з сигнала отделителя 8 частоты блока 6 синхронизации они устанавливаются в первое состояние и подключают к входам сумматоров-вычитателей IQ-Й группы первые восемь информационных входа процессора: Хс и У1 . Х2 и , Х4 и Xs , Хб и Х7 .

Вычисляются суммы (Хо + Xi), (X2 + Хз), (Х4 + Xs) (Хе + Ху) и разности (), (), (), (). Суммы поступают на блоки 4о, 42,44,4е задержки и запоминаются в них, а разности- на блоки 4i, 4з, 4s, 4у. На втором такте по сигналу от блока синхронизации коммутаторы устанавливаются во вто- рое состояние, коммутаторы 1о-1з в первое.

Через коммутаторы на входы сумматоров-вычитателей поступают следующие четыре пары входных сигналов: Ха , XionXn-v3i, Xi2 и , Xi4 и . Вычисляются суммы (Ха + Хд). (Хю + Xn), (Xi2 + Xi3), (Xi4 + Xis) и разности (Xa-Xg), (Xю-Хи). (Xi2-Xi3). (Xi4-Xis). Разности поступают на блоки задержки первой группы 4i. 4з, 4s, 4, откуда предыдущие результаты через коммутаторы передаются на блоки задержки второй группы 5о, 52, 5i, 5б, где и запоминаются на один такт.

Суммы из сумматоров-вычитателей Зсг

33поступают на блоки задержки 4о, 42. 44, 4е, откуда предыдущие результаты передаются на входы сумматоров-вычитателей следующей группы И-й 34 и 3s- Таким образом базовые операции первого этапа полностью завершены.

Одновременно сумматоры-вычитатели

34и 3s продолжают преобразование первой входной выборки, т.е. вычисляются соответ- ственно суммы ((Хо + Xi) + (Х2 + Хз)), ((Х4 + Xs)

+ (Хб + X)) и разности ((Хо + Xi) - (Х2 + Хз)), ((Х4 + Xs) - (Хе + X)) Суммы поступают на блоки задержки 4в и 4ю, а разности - на блоки 4д и 4ц. Двум тактам работы суммато- ров-вычитателей соответствует цикл работы процессора. С каждым циклом, т.е. через такт на вход процессора р поступает новая входная выборка. На третьем такте коммутаторы устанавливаются вновь в пер- вое состояние, коммутаторы - во второе состояние, коммутаторы 14 и 1s - в первое. Первый этап преобразования над первой половиной новой входной выборки вычисляется аналогично указанному.при

0

5 0

5

5

0

5

0 5

этом предыдущие результаты из блоков задержки 4i, 4з, 4s, 4у через коммутаторы 1о- 1з передаются на блоки задержки 5i, 5з, 5s, 5, а с блоков задержки 5о, 52, 54, 5е предыдущие результаты, т.е. (Xo-Xi), Х2-Хз), (Х4- Xs), (Хб-Ху) поступают на восьмой, девятый, десятый и одиннадцатый информационные выходы процессора, т.е. на выходах процессора имеется уже часть коэффициентов: Ye, Yg, Yio, Yn.

Информация с блоков задержки 4д и 4ц через коммутаторы 14 и 1s. т.е. ((Xo + Xi)-(X2 + Хз)). ((ХА + Xs) - (Хе + Ху)) поступает на четвертый и пятый информационные выходы процессора, т.е. имеются У4-й, Ys-й коэффициенты. На этом же такте включается в работу 12-я группа сумматоров-вычитателей, т.е. в сумматоре-вычитателе Зе вычисляется сумма ((Хо + Xi + Х2 + Хз) + (Х4 + Xs + Хб + Ху)) и разность ((Хо + Xi + Х2 + Хз) - (Х4 + Xs + Хб + Ху)). Разность через коммутатор 1б поступает на второй выход процессора, т.е. на выходе имеется коэффициент Y2, а сумма поступает на блок задержки 4i2.

На следующем четвертом такте коммутаторы 2о-2з устанавливаются во второе состояние, коммутаторы - в первое, коммутаторы 14, 1s, 1б - во второе состояние. На двенадцатый, тринадцатый, четырнадцатый и пятнадцатый информационные выходы процессора поступают результаты из блоков задержки 5i, 5з. 5s, 5y, на седьмой и шестой выходы - через коммутаторы 14 и 1s из блоков задержки 4д и 4ц, т.е. на указанных выходах имеются Yi2, Yi3, Yis, YG, Yy коэффициенты преобразования. На этом же такте сумматор-вычитатель Зб вычисляет сумму ((Ха + Хд + Хю + Хц) + (Xi2 + Xis + Xi4 - Xis)) и разность ((Xs + Xg + Хю + Хц) - (Xi2 + X13 -Х14+Х15)).

Разность через коммутатор 1б поступает на первый информационный выход процессора, а сумма - непосредственно на второй вход сумматора-вычитателя ЗУ, на первый вход которого поступает предыдущий результат из блока 4i2 задержки. Сумматор-вычитатель Зу выполняет последний этап преобразования Хаара, вычисляя сумму (Хо + Xi + ... Xis) и разность ((Хо + ... Ху) - (Ха + ... Xis)). Сумма поступает на нулевой выход процессора, а разность - на первый.

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

Конечные результаты преобразования

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

Предлагаемый процессор реализует преобразование Хаара для входных выборок длиной 2П (n-целое число, п з), на которое требуется п тактов работы сумматоров-вычитателей.

В случае N 2 16 на преобразование входной выборки требуются четыре такта работы сумматоров-вычитателей или два цикла работы процессора вместо девяти тактов в базовом объекте.

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

Формула изобретения Параллельный процессор Хаара, содержащий п групп (N 2П -объем входной выборки) сумматоров-вычислителей, первую группу коммутаторов и блок синхронизации, о т л и ч а ю щ и и с я тем, что. с целью повышения быстродействия, в него введены вторая группа коммутаторов и две пы блоков задержки, причем j-й (j -- 0,2- ) информационный вход процессора соединен с 1-м (i - j mod 2 - 0 J mod N/2/2n 2 информационным входом К-го (К (j mod N/2 - j mod 2))коммутатора второй группы. S-й (S 0,1) информационный выход которого соединен с одноименным S-м входом сумматора-вычитателя первой группы, выход суммы j-ro сумматора-вычитателя первой группы через J-й блок задержки первой группы соединен с q-м (q j mod 2) входом Z-ro (Z 0 0/2) сумматора-вычитателя первой группы, выход суммы M-ro (M

0,2

0

n-2-l

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

1,п-2) группы через М + 2П 1 - 2n l й блок задержки первой группы соединен с t-м (t

0 М mod 2) входом R-го (R (M-t)/2) сумматора-вычитателя (I + 1)-й группы, кроме того, выход суммы сумматора-вычитателя (п-2)-й группы соединен непосредственно с вторым входом сумматора-вычитателя (п-1)-й

5 группы, выход разности М- го су мматора вы- читателя р-й группы (р 0,п-3) через (М + 2 - 2П р)-й блок задержки первой группы соединен с информационным входом L- го (L М + 2n - коммутатора первой группы, выход разности сумматора-вычитателя ()-й группы соединен с информационным входом (2П - 1)-го коммутатора первой группы, выходы суммы и разности сумматора-вычитателя (п-1)-й группы сое5 динены соответственно с первым и вторым выходами процессора, выходы коммутаторов с ( - 5)-го по ( - 3)-й первой группы соединены соответственно с третьего по восьмой выходами процессора, а вы0 ходы коммутаторов с первого по ( - 6)-й через блоки задержки второй группы соединены с девятого по (2п-т)-й выходами процессора, первый выход блока синхронизации соединен с входами синхро5 низации всех блоков задержки, второй выход блока синхронизации соединен с управляющими входами коммутаторов первой и второй групп.

Изобретение относится к вычислительной технике и может быть использовано в системах цифровой обработки сигналов для построения устройств цифровой фильтрации, сжатия изображения и выделения признаков, основанных на параллельном алгоритме преобразования Хаара. Цель изобретения - повышение быстродействия. Для этого процессор содержит две группы коммутаторов, N групп сумматоров - вычитателей (N = 2^N - объем входной выборки), две группы блоков задержки и блок синхронизации. Указанная цель достигается за счет применения нового параллельного алгоритма преобразования Хаара. 3 ил.

о

-mgr

3 r-i -(t-ч)

.-.)

$w,

- 1

Ю

r,-,

) 3 U3(t-4)

(tt2 Јft-«;

-H) 1.9 r

Фиг 1

-ЧУ 1 г /

yf- доьоьал операция

rt / t - x

Фиг. 2