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

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (я)5 G 06 F 15/332

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4738804/24 (22) 14.06.89 (46) 30.07.91. Бюл. N. 28 (71) Вычислительный центр АН АрмССР (72) С.С.Агаян, А.П.Галантерян, Д.З.Геворкян и А.В.Мелкумян (53) 681.3 (088.8) (56) Патент США М 3981443, кл. G 06 F 15/34, 1975.

Авторское свидетельство СССР

М 1061150, кл, G 06 F 15/332, 1983.

Авторское свидетельство СССР

ЬЬ 1343423, кл. G 06 F 15/332, 1987. (54) ПАРАЛЛЕЛЬНЫЙ ПРОЦЕССОР XAAPA

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

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

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

Параллельный процессор Хаара (фиг.1) содержит шестнадцать информационных входов, на которые поступают отсчеты вход„, SU ÄÄ 1667103 А1 (57) Изобретение относится к вычислительной технике и может быть использовано в системах цифровой обработки сигналов для построения устройств цифровой фильтрации, сжатия изображения и выделения признаков, основанных на параллельном алгоритме преобразования Хаара. Цель изобретения — повышение быстродействия.

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

: (Л ного вектора (Хо(1) — Х(т), и шестнадцать информационных выходов, на которых получаются коэффициенты Хаарà (Yo(t — 4)

Y1s(z-4)), первую группу коммутаторов 1о16, вторую группу коммутаторов 20-2, soсемь сумматоров-вычитателей 30-37, разбитых на четыре группы: нулевая группа

lo содержит четыре сумматора-вычитателя, 0 первая группа l1-два, вторая и третья груп- 4 пы 12 и l3 — по одному сумматору-вычитателю. О

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

Блок синхронизации имеет два выхода

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

1667103

1 !

I -1

T (I ) = f (P L (P S @I ) х где

Х I О О

I Х

I -I

О Х,„, (4

Н (2)

Н =

Х Х 0 О

О 0 Х

О .

0 О Х -I

0 Х

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

Каждый блок задержки первой группы 5

4i содержит один регистр сдвига и эапомикает поступившее число на один такт работы сумматоров-вычитателей. Каждый блок задержки второй группы 5! так же состоит иэ одного регистра сдвига и запоминает по- . 10 ступившее число на один такт работы сумматоров-вычитателей, так как и — I — 3 = 1.

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

Переключатели первой и второй групп принимают первое или второе состояние (на фиг.3 показаны римскими цифрами l и II) в зависимости от управляющего сигнала 0 20 или 1 с второго выхода 10 блока 6 синхронизации, Вычисление коэффициентов Хаара основано на разработанном параллельном алгоритме преобразования Хаара над 25 последовательностью входных выборок, представляемых векторами Х, размером

N =2"

YI = !-IN Xl (I = 1,2,...), (1) 30 где «Н!ч — матрица преобразования Хаара; Yi — преобразованные выборки.

Х Х О О О 0

I -I 0 0 О О

О О I Х О О

О 0 Х -Х О О

О 0 0 О I I

О 0 О О I -Х Алгоритм строится посредством факторизации матрицы Н!ч в виде произведения слабо заполненных матриц.

HN = Н(1) -1{1) Н(2) ({2) Н(л) T{л) (2) ф-!

Н")=В Ч О1 - (3) S o S где 9- обозначает прямую сумму матриц;

1!ч-г — единичная матрица порядка Й—

21;

В (2)T") — матрицы перестановок, определяемые следующим образом. х Р 21+1 ; ) ф12" — 2 +1 (4)

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

P 1 — матрица оператора полной тасовки порядка 21.

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

=2 = 16.

H,в = Н() T{ ) Н() фг) Н(з) Цз) Н(4) -Т(!) 1667103

Х I 0 О О 0 О 0 0 О 0 О О О 0 О

Х-Е 0 О О 0 О О О О О О

О О 0 О

О О О О

0 0 О 0

I О О О О О 0 О 0

-I О О 0 О О О О 0

О 0 I

О 0 I

О 0 0 0-0 О I Х

О 0 О 0 О О I »I

О 0 О g

0 0 О О

О О 0 О

О 0 О О

Н=

О 0 0 О О О 0 0 Х Х О О О О О 0

О О О О О О О О I -Х О О О О 0 О

О О О 0 О 0 0 0 0 0 Х I О О О О

О О О О О 0 0 О О 0 Х Х 0 0 О О

О О О О О О О О 0 О О О I Х О О

О О О О О О О О О 0 О О I -I О О

О 0 О О О О 000

0 О О О 0 О О О

0 0 О О

О 0 О О

О О I Х

О О I -I

I О 0 О

O0 I 0 0

О I О О р)

О О 0 Х

ХХ2

Х О О О О 0 0 О

О О О 0 I 0 О О

О О I О О 0 0 О

О О О О О О Х О

О Х О О О О 0 О

О О О О О I О О

rg,)

О О О Х О О О О

О О 0 О О О О I о

0 О О О I I О О О 0 О 0 О О О 0

0 0 0 О Х-Х О 0 0 0 0 О 0 0 0 О

1667103

Х О О О О О 0 О О О О О О О О О

О О I О О О О О 0 О О О О О О О

О О О О О О О О I О О О О О О О

О О О О О О О О О О I О О О О О

О I О О О О О О О О О О О О 0 О

О О О Х О О 0 О О О О О О О О О

О О О О О 0 О О О I О О О О 0 О

О 0 О О О О 0 О О О О Х О О О О

О О О О Х О О О О О О О О О О О .Ю

T = О О О О О О I О О О О О О 0 О О

0 О О О О Х О О О О О О О О О О

О О О О О О О I О О О О О О О О

0 0 О О О 0 О О О О О О I О О О

О 0 0 O 0 G 0 0 0 0 0 O 0 0 I.О

0 О О О О О О 0 О О О О О I 0 О

0000 Î О О О ООООООООХ

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

У Д Ю .7(1) (q(2). -Т(2) (Н(п-1), Т(-.1). (Н!и) Т " Х,,)) ). 5

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

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

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

0,1„..,t — 1 (t = мин (n — 1, I+1)) выполняется )-й этап преобразования, т.е. умножение матрицы Н(" Т(" ) на очередной вектор, явля- 20 ющийся при I = 1,2...„t — 1 результатом работы предыдущей группы ветвей на предыдущем цикле, а при = Π— нов ой входной выборкой Xi, Итак, на каждом цикле, т.е. через шаг, 25 начинает обрабатываться новая входная . выборка. Начиная с п-го шага в 2" йветви алгоритма (в п-й группе) через один шаг выполняется последний (n — 1)-й этап преобразования Хаара, над очередным вектором 30

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

В соответствии с приведенным алгоритмом для последовательности входных выбоаок оазмерами N = 2" процессор содержит

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

Рассмотрим работу процессора на примере последовательности входных выборок размерами N = 2 = 16. В этом случае.процессор содержит четыре группы сумматоров-вычитателей: в нулевую группу входят четыре сумматора-вычитателя, в первую группу — два сумматора-вычитателя, во вторую и в третью — по одному сумматору-вычитателю. Процессрр содержит семь коммутаторов s первой группе, четыре — во второй группе, тринадцать блоков задержки в первой группе, задерживающих информацию на один такт работы сумматоров-вычитателей, восемь блоков задержки во второй группе, задерживающих информацию также на один такт (так как и — )-3 = 1 при n = 4, ! = О) и блок синхронизации, содержащий генератор тактовых импульсов и делитель частоты на два.

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

10 рой групп поступают сигналы от генератора

7 тактовых импульсов блока 6 синхронизации, запоминая информацию на один такт работы сумматоров-вычитателей. На первом такте при поступлении на синхронизирующие входы 10 коммутаторов 2o— - 2з сигнала от делителя 8 частоты блока 6 синхронизации они устанавливаются в первое состояние и подключают к входам сумматоров-вычитателей Зо — Зз lo-й группы первые восемь информационных входа процессора:

Хс и М1 — .30, Хг и Хз 31, Х4 и X5 - Эг. Х8 и

Х7 - Зз.

Вычисляются суммы (Xo + X1), (X2 + Хз), (Х4+ Х5) (Х8+ Х7) и разности (Xo-X1), (Хг — Хз), (X4-X5), (Х8-Х7), Суммы поступают на блоки

40, 42, 44, 48 задержки и запоминаются в них, а разности — на блоки 41,4з,45,47. На втором такте по сигналу от блока синхронизации коммутаторы 20-20 устанавливаются во второе состояние, коммутаторы 1о-1з — в первое.

Через коммутаторы 4р-4з на входы сумматоров-вычита1елей Зо — Зз поступают следующие четыре пары входных сигналов: Х8 и Х9 "+ 30, Х10 и Х11-ъ- 31, Х12 и Х1з ) 32, Х14 и

Х15-- Зз. Вычисляются суммы (Х8 + X9), (X10

+ Х11), (Х12 + Х1з), (Х14 + X15) и разности (Х8-X9), (X10 X11), (X12-X13), (X14-X15). Разности поступают на блоки задержки первой группы 41, 4з, 45, 47, откуда предыдущие результаты через коммутаторы 1o — 1з передаются на блоки задержки второй группы 5р, 52, 54, 55, где и запоминаются на один такт.

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

Зз поступают на блоки задержки 40, 4г, 44, 48, откуда предыдущие результаты передаются на входы сумматоров-вычитателей следующей группы I1-й 34 и 35, Таким образом базовые операции первого этапа полностью завершены.

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

34 и 35 продолжают преобразование первой входной выборки, т.е. вычисляются соответственно суммы ((Xo + Х1) + (X2 + Хз)). ((X4 + Х5)

+ (Х5+ Х7)) и разности ((Xp+ Х1) — (Х2+ Хз)), ((Х4 + Х5) — (Х5 + Х7)); Суммы поступают на блоки задержки 48 и 410, а разности —. на блоки 49 и 411. Двум тактам работы сумматоров-вычитателей соответствует цикл работы процессора, С каждым циклом, т.е. через такт на вход процессора р поступает новая входная выборка. На третьем такте коммутаторы 20-2з устанавливаются вновь в первое состояние, коммутаторы 10-1з — во второе состояние, коммутаторы 14 и 15 — в первое. Первый этап преобразования над первой половиной новой входной выборки вычисляется аналогично укаэанному, при этом предыдущие результаты из блоков задержки 41, 4з, 45, 47 через коммутаторы 101з передаются на блоки задержки 51, 5з, 55, 57, а с блоков задержки 50, 52, 54, 58 предыдущие результаты, т.e. (Xp — Х1), Хг-Хз), (Х4X5), (Х8 — Х7) поступают на восьмой, девятый, десятый и одиннадцатый информационные выходы процессора, т.е. на выходах процессора имеется уже часть коэффициентов: У8, У9, У10, У11

10

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

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

Информация с блоков задержки 49 и 411 через коммутаторы 14 и 15, т.е. ((Xp+ Х1) — (X2

+ Хз)), ((Xa + X5) — (Х8 + Х7)) поступает на

15 четвертый и пятый информационные выходы процессора, т.е. имеются У4-й, У5-й коэф.фициенты. На этом же такте включается в работу 12-я группа сумматоров-вычитателей, т.е. в сумматоре-вычитателе 38 вычисляется сумма ((Xp + Х1 + Х2 + Хз) + (Х4 + Х5 + X8

+ Х7)) и разность ((Xp+ X1+ X2+ Хз) — (Х4+ Х5

+ Х5 + Х7)). Разность через коммутатор 18 поступает на второй выход процессора, т.е. на выходе имеется коэффициент У2, а сумма

25 поступает на блок задержки 412.

На следующем четвертом такте коммутаторы 2p — 2з устанавливаются во второе состояние, коммутаторы 10 — 1з — в первое, коммутаторы 14, 15, 18 — во второе состояние. На двенадцатый, тринадцатый, четырнадцатый и пятнадцатый информационные выходы процессора поступают результаты из блоков задержки 51, 5з, 55, 57, на седьмой и шестой выходы — через коммутаторы 14 и

15 из блоков задержки 49 и 411, т.е. на указанных выходах имеются У12, У1з, У15, У9, У7 коэффициенты преобразования. На этом же такте сумматор-вычитатель 38 вычисляет сумму ((XS + X9 + X10 + X11) + (X12 + Х1з + X14

40 + X15)) и разность ((X8+ X9 + Х10 + X11) (X12

+ X13 + X 1 4 + Х15)).

Разность через коммутатор 18 поступает на первый информационный выход процессора, а сумма — непосредственно на

45 второй вход сумматора-вычитателя 37, на первый вход которого поступает предыдущий результат из блока 412 задержки. Сумматор-вычитатель 37 выполняет последний этап преобразования Хаара, вычисляя сумму (Xo + X1 + ... X15) и разность ((Xo + ... Х7)— (Х8 + ... X15)). Сумма поступает на нулевой выход процессора. а разность — на первый.1667103

Ф1г уа(> ь ((- ) (1-0) 9 (t þ) хп (t) ху (t) . ((Х1 (t)

xq(t

x (t

x,(tI

xz(tj

xg(t)

Х1ай 2 х11(t)

А!2()

x1a(t J

X1y (t)

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

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

В случае N = 2 = 16 на преобразование

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

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

1 и-го такта через такт (на каждый цикл), он выдает очередной вектор коэффициентов преобразования Хаара. (Формула изобретения

Параллельный процессор Хаара, содержащий и групп (N = 2" — Объем вхоцной выборки) сумматоров-вычислителей, первую группу коммутаторов и блок синхронизации, отличающийся тем, что, с целью повышения быстродействия, в него введены вторая группа коммутаторов и двег)заппы блоков задержки, причем j-й (j:- =0,2" — < ) информационный вход процессора соединен с 1-м (i = j mod 2 + (j — j mod N/2/2" информационным входом К-го (K = (j mod

N/2 — j mod 2)/2) коммутатора второй группы, S-й (S = 0,1) информационный выход которого соединен с одноименным S M входом сумматора-вычитателя первой группы, выход суммы J-го сумматора-вычитателя первой группы через J-й блок задержки первой группы соединен с q-м (q = J mod 2)

5 входом Z-го (Z = (j — i)/2) сумматора-вычитателя первой группы, выход суммы М-го (М =

0 2 — 1) сумматора-вычитателя 1-й (! =

1 и-2) группы через M+ 2" — 2" )-й блок задержки первой группы соединен с с-м (t =

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

15 группы, выход разности Мго ссумматора вычитателя у-й группы (р = О,n — 3) через (M +

2" — 2" Р)-й блок задержки первой группы соединен с информационным входом L"

ro (L = М + 2" — 2" 2 коммутатора первой

20 группы, выход разности сумматора-вычитателя (n-2)-й группы соединен с информационнымым входом (2" — 1)-го коммутатора первой группы, выходы суммы и разности сумматора-вычитателя (и — 1)-й группы сое25 динены соответственно с первым и вторым выходами процессора, выходы коммутаторов с (2" — 5)-го по (2" — 3)-й первой группы соединены соответственно с третьего по восьмой выходами процессора, а вы30 ходы коммутаторов с первого по (2" — 6)-й через блоки задержки второй группы соединены с девятого по (2"-))-й выходами процессора, первый Bыход блока синхронизации соединен с входами синхро35 низации всех блоков задержки, второй выход блока синхронизации соединен с управляющими входами коммутаторов первой и второй групп.

1667103 этап

У 9man

I Уожкщ oman

А с+ "л — оозо м олсрор4

Ai гю - М 2

9- Ъг. 2

b Йа.J

Составитель Ю.Ланцов

Техред M.Ìîðãåíòàë

Редактор С.Лисина

Корректор М.Пожо

Производственно-издательский комбинат "Патент". г. Ужгород, ул.Гагарина, 101

Заказ 2526 Тираж 413 Подписное .

ВНИИПИ Государственного комитета по.изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., 4/5