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

 

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

„„ Ы„„ l75690ll All

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

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

РЕСПУБЛИК

Îsi)s G 06 F 15/332

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

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

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (54) ПОТОЧНО-ПАРАЛЛЕЛЬНЫЙ ПРОЦЕСС0Р ХААРА (57) Изобретение относится к вычислительной технике и цифровой обработке сигналов. Цель изобретения — повышение быстродействия за счет применения поточИзобретение относится к области ВТ и Наиболее близким техническим реше- (Л обработки случайных процессов и может нием к предлагаемому является устройство С)ц, быть использовано в системах цифровой для вычисления коэффициентов Хаара, со-. фильтрации, сжатия изображения и выделе-: держащее группу из пятнадцати сумматония признаков, основанных на параллель- ров, хранящих в себе информацию до ном алгоритме преобразования Хаара., прихода следующей и выполняющих одну

Известны устройства, аыпояняювтие . операцию (вычитание или саожение) за один );в конвейерное рационализированное преоб- такт работы, группу переключателей, состо- д разование Хаара для входных выборок дли- ящую иэ шестнадцати переключателей, ной N = 2", представляемых счетчика, схемы ИЛИ и дешифратора. В последовательнымиотсчетами. " —.— этой устройстве с целью йосвышения быстОднако во многих областях цифровой родействия применяется параллельно-пообработки сигналов возникает необходи- следовательный метод обработки, мость в поточной обработке входных выбо- Устройство осуществляет параллельное вырок, поступающих параллельно в виде чиспениекоэффициентовХаараот16отсчевекторов длиной N = 2", что невозможно тов входной выборки цифрового сигнала за реализовать на известных устройствах. - девять тактов работы сумматоров. (21) 4773604/24 (22) 23,12.89 (46 23.08.92. Бюл. ¹ 31 (71) Вычислительный центр АН АрмССР (72) A.Ï.Ãàëàíòåðÿí, Д,З.Геворкян и

А, В.Мелкумян (56) Патент США N. 3981443, кл. 6 06 F 15/34, 1975.

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

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

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

¹ ã 11334433442233, . кKл . G 06 F 15/332,,1987.

2 ной обработки векторов длиной N = 2" и унификация процессора, заключающаяся в реализации процессора йа 2 (t = 1, и-1) сумматорах-вычитатепях в зависимости 07 требуемого быстродействия. Указанная цель достигаешься тем, что в поуточно-параллельный процессор Хаара, содержащий группу сумматоров-вычитателей, группу переключателей и блок синхронизации, введены t;îðîâ-вычитателей (t= 1, п-1, N = 2" — размер входной выборки), три группы переключателей, (2 — 2) блоков сдвига и две группы элементов задержки, Поточно-параллельный процессор

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

Хаара. 6 ил.

1756901

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

Если реализовать известное устройство для входных выборок-векторов длиной N =2", то следует ожидать, что преобразование Хаара над каждым вектором будет выполняться за (2" + 1) тактов и потребуется (2"--1) сумматоров.

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

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

+ 2" ) элементов, i-я и последняя (t+1)-я (i =

=1, t) группы сумматоров-вычитателей состоят соответственно из 2 " и одногоссумматора-вычитателя, причем )-й (j = О, 2 -1) информационный вход процессора соединен с 1-м (I = j mod 2 + 2 (j — j mod 2 )/2 ) информационным входом К-ro (К = (j mod 2t — j гпос12)/2) переключателя первой группы, 1-й информационный выход которого (1 = О, 1) соединен с 1-м входом одноименного

К-го сумматора-вычитателя первой группы, выход суммы m-га сумматора-вычитателя первой группы через m-й(m = 0,2 -1) блок

t-1 сдвига соединен с Ь-м (Ь = m mod 2) входом

q-го (q =- (m — Ь)/2) сумматора -вычитатрлтуя второй группы, выходсуммы д-га(о==0,2 " ) сумматора-вычитателя г-й (r = 2, т-1) группы через (m + 2 " 1 — 2" 2")-й блок сдвига соединен с Р-м (Р = m, mod 2) входом q-ro

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

2. группы, выход суммы ед1лнственнаго сумматора-вычитателя ((+1)-й группы соединен с

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

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

15 входом переключателя третьей группы, 1-й (1 = О, 2 (п-.т-1) — 1) выход которого через (2 +1+1)-й элемент задержки второй группы соединен с (1+2)-м информационным входом переключателя четвертой группы, а 2(n-t-1)2р и выход переключателя третьей группы является первым выходом процессора, выход разности последнего сумматора-вычитателя (t+1)-й группы соединен с информационным входом 2 -го переключателя второй

25 группы, с-й (с, = 1, 2" — 1) выход которого является с-м информационным выходомл процессора, выход разности d-ro (d = 0,2 — 2)

1 сумматора-вычитателя через d-й элемент задержки первой группы связан с информа30 ционным входом d-го переключателя цтщ2цф группы, h-й (h =- О, 2 — 1) выход )-го O = О, 2 ") переключателя второй группы соединен с входом f-ro (f = J, 2" + h) элемента задержки., С первого па (2" )-й выходы (2 — 2)-го пере35 ключателя второй группы связаны с информационными входами с (2" (2 — 2))-го по . (2" — 1)-й элементов задержки второй группы, выходы которых являются с 5-ro па

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

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

Выходы перекл1очателей второй группы соответственно с 1-го по (2 -1)-й соединены с

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

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

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

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

1756901 тели второй группы ZQ-27, переключатель

55 ров-вычитателей

На фиг.ба — r римскими цифрами указаны состояния переключателей первой, втотретьей группы, 31, переключатель четвертой группы 41, сумматоры-вычитатели 5О-57, блоки 6p — 65 сдвига, состоящие из четырех . рой, третьей и четвертой групп в последовательно соединенных регистров зависимости от двоичного кода на управлясдвига, элементы задержки первой группы ющих входах переключателей, который поуправляющими входами переключателей 7о — 7

mod (2 (n-t) — 1) с logy 2(n-t) разрядной шиной генератора 10 тактовых импульсов с выхона выходе, которая является третьим выхо- дом 14, счетчика 11 по mod 4, с 2-разрядной дом блока синхронизации и соединена с 5 шиной 15 на выходе, счетчика 12 по тоб" управляющими входами переключателя с 2-разрядной шиной 15 на выходе, счетчика третьей группы, третий счетчик по mod(n-т) с 13 по mod 2 с одноразрядной шиной на

1ogz (n-t) разрядной шиной на выходе, кото- выхбде 17. рая является четвертым выходом блока синх- Поточно-параллельный процессор Хааронизации и соединена с управляющими 10 ра при t = 2 (фиг.2) содержит информационвходами переключателя четвертой группы:.- Ные входы Хр-Хз>, информационные

На фиг.1 представлена схема поточно-па- выходы Yо-У31, переключатели первой групраллельного процессора Хаара для последо- пы 1< и 1t, переключатели второй группы вательности входных выборок-векторов 2о-23, переключатель третьей руппы 31, net размерами и = 2" для 2 сумматоров-вычита- 15 реключатель четвертой группы 4t, сумматотелей, где t = 1, и-1; на фиг.2 — схемы поточно- ры-вычитатели 5Π— 5з, блоки Gp и 61 сдв ra, параллельных процессоров Хаара для состоящие из восьми регистров сдвига, элепоследовательности входных выборок-ВеКТо менты задержки первой группы 7р 7Q, элеров размерами N = 25 для 2 сумматоров-вы- менты задержки второй группы 8 -S

5 на фиг,б — схемы состояний переключателей выходе, счетчика по mod 5 с 3-разрядной с первой по четвертую групп и последнего шинои l6 на выходе, счетчика по mod 3 с переключателя второй группы для процес- 25 2-разрядной шиной 17 на выходе, сора при t =3. Поточно-параллельный процессор ХааПоточно-параллельный процессор Хаа- ра при t = 1 (фиг.4) содержит информационра (фиг.1) содержит 2" информационных ные входы Хо — X3< и информационные входы входов Xp — Х2-1 и 2" информационных вы- Ур — У3н переключатель первой rpynr ы 1,, ходов Yp — Y2 1, пеРвУю гРУппУ пеРеключа- 30 пеРеключатели втоРой гРУппы 2р и 21, пеРетелей 1Π— 12" "-1, втору о группу ключатель третьей группы З, переключаЕ переключателей 2, — 22, третью группу 31 тель четвертой группы:. 4t, и четвертую группу 4t, 2 сумматоров-вы- сумматоры-вычитатели 5р и 51, элементы за1 читателей 5> — 5р ->, разбитых íà (t + 1) держки второЙ группы 8Π— 87, элементы загрупп lp — )ь l ÿ группа содержит 2 сум- 35 держки первой группы 7p — 7в, блок 9 маторов-вычитателей,t-я группасодержит синхронизации, состоящий из генератора

t один сумматор-вйчитатель, блоки 6p — 6>-з 10 тактовых импульсов с выходом 14, счетсдвига с 2" последовательно соединен- чика по mod 16 с 4-разрядной шиной 15 ча ными регистрами сдвига, элементы за- выходе, счетчика по тоб 7 с 3-разрядной держки nepBOA rpynn 7о 7(2+2(п-<-1)), 40 шинОЙ на выходЕ 16, счетчика по mod 4 с

t элементы задержки второй груйпы 2-разрядной шиной на выходе 17.

РЗ.Ф t n-й-4

8o — 82 р -2)+2 -1) и блок 9 синхронизации, Каждый сумматор-вычитатель без внуткоторый состоит из генератора 10 такто- ренней памяти состоит из двух сумматоров вых импульсов, счетчика 11 по rriod 2", (один для выполнения операции сложения, счетчика 12 по mod (2x(n-t)-1), счетчика 13 по 45 другой для вычитания).

mod(n-t) и имеет четыре выхода 14-17, прй- Каждый блок сдвига состоит из 2" почем последние три выхода являются соот- следовательно соединенных регистров ветственнî (n-t)-pазрядной; !О922(п-t} сдвига, разрядной и togz(n+разрядной шинами. Каждый элемент задержки запоминает

Поточно-йараллельный процессор Хаа- 50 поступившее число до прихода следующего, ра прй t = 3 (фиг.2) содержит тридцать два На фиг.5 рядом с каждой базовой опеинформационных входа Хр Х31, тридцать рацией двухточечйого преобразования укаДва инфоРмаЦионных выхоДа Yp — У31, пеРе- зан номеР такта, во вРемл котоРого она ключатели первой группы 1о-13, переключа- выполняется, при t = 3, т.е. для 2 суммато1756901. 1 О О О О

-1ОООО!

O1iO0l

0 1-1 0 О jа

О 0 О 1 1

О О 0 1-1

10 (1) Y! -- Ни Х! {! = 1, 2,...) о

1ÎÎÎ

001О о1аo i

ООО1

40 о . О 1

I ооооа

ООО1О

О1ООО аоооо

1ОООО аооо1

0010а ооооа а о а о о а

1 О 1 а о а о а i о а о

И .=

1 1

7 дается через соответствующие многоразрядные вины с выходов блока синхронизации.

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

2ï где HN — матрица преобразования Хаара;

Y! — преобразованные выборки..: . Алгоритм строится посредством факто- 15 ризации матрицы Ни в виде произведенйя слабо заполненных матриц

Н,„ Н !) ф!) H(2) -,Р) Н ) Т+) (2) г" 20

H0) =О+ Чз 9 Х!!-г" . (3) S-.0. где 6) — прямая сумма матриц, . Ъ-2}- единичная матрица порядка N-2 ;

1 1

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

ТО = ({P2lg+ $2э) P2itf) ®Т2 -2 е (4) где $2!- матрица оператора двоично-инвер- 35 сной перестановки порядка 2;

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

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

Н16 * НИ Т(1) НР) ТР) Н(3) ТР} Н(4) g4) о о ! а о а а а а а

-1о I т„ !

1 1 0 О О О

1-1 О О О О

О О 1 1 О О о01-100

00.0011

ОООО1-1

0 О О О О О оооеоо аооооо

О 0 О О а О

О О О О О О

0 О О О 0.0

0 0 O 0 0 0

О О О 0 О О

0 О О О О О

0 а О о а О

О О О 0 О 0 оооаоа а о о а о о оооооо

О О О О О О

0 0 О О О О

1OO

1-1аооа

001-1оа оооо а о о о.1-1

О О 0 0 О О

О О 0 О О 0

О О а 0 0 а

О О а а О О оооо оооо оооо оооо оооо оооо оооо оооо ааоо оооо оооо оооо

1оа а а о а а а

1756901

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

У1 = (Н(1) (1) {Н(2) 1-(2) . (Н(-1) T(n- ) (Н(п) )-() Х ) ) ) Сущность алгоритма заключается в следующем, Алгоритм состоит из К = 2 (t = 1, и-1, 2" — длина входной выборки) взаимодействующих между собой ветвей, Ветви алгоритма условно разбиваются íà (t+1) групп. В I-io (1= 0, t-1) входят 2 ветвей, а в1= t-e группу входит одна 2-я ветвь, На очередном i-м

t цикле алгоритма (! = О, 1„„.), состоящем из

2" шагов (шагу алгоритма соответствует такт работы сумматоров-вычитателей в предлагаемом процессоре). параллельно в каждой группе ветвей {(I =- О, 1,...Л-1), t= mitt {t, i+1)) выполняется I-й этап преобразования, т.е. умножение матрицы К " ) T" ) на очередной вектор, являющийся результатам работы предыдущей группы ветвей на предыдущем цикле, а при! = Π— новой входной выборкой Хь Итак, на каждом цикле начинает обрабатываться новая входная выборка. Начиная с t-го цикла работы, на каждом цикле, кроме операций, исполняемых в группах ветвей I = О, t 1, параллельно (одновременно) в t-й группе ветвей (т.е, в

2-й ветви) выполняются последовательно

tэтапы t, t+1,...,n-1 преобразования Хаара

r о о

001

0 О О

0О0

0 о о

000 о о о

0ОО

000 ооо оооо оооо оооо оооо оооо

000 о о о о оооо

01о о

О 01 О оооо оооо оооо оооо оооо

О 0 О О О

00ООО о1о о о ооо1о

ОО0ОО

ОО0О0 оо1оо оооо

О0ООО

0 О 0 0 0

О 0 0 0 О оооо

0 0 0 0 О

0000 О

0О0ОО

0О0О0 оооо оооо оооо оооо оооо оооо оооо оооо оооо оооо оооо оооо

0О0

01ОО

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

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

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

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

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

4 соединенных регистров сдвига в каждом из . 25 них, двенадцать элементов задержки в первой группе, двадцать шесть элементов задержки во второй группе и блок синхронизации, состоящий из генератора тактовых импульсов, счетчика no mod 4, счетчика по mod 3 и счетчика по то ) 2, На первом такте при поступлении на управляющие входы переключателей 10-1з сигнала от блока синхронизации они устанавливаются в первое состояние и подклю35 чают к входам сумматоров-вычитателей

5о — 5з )о-й группы первые восемь информационных входов процессора; Хо и Х1 50;

Х2 и Хз-» 51; Х4 и Х4 —:«52; Х6 и Х7 - 5з, ВычислЯютсЯ сУммы (Хо+ Х1), (Х2+ Хз). (Х4

40 + X5), (Х6+ Хт) и разности (Хо — Х1), (Х2 — Хз)." (X4- Х5). (Х6- Хт). Суммы поступают на входы блоков 6>-6з сдвига. а разности — на элементы 7,-7з задержки.

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

45 синхронизации переключатели 1о — 1з устанавливаются во второе состояние, переключатели 2,-2 — в первое, а на входы сумматоров-вычитателей 5о-5з поступают следующие четыре парйвходных сигналов:

50 Х8 и Х9 -»5о, Х 10 и Х11»51; Х 12 14 Х13» 52; Х14 и Х15- 5З, Вычисляются суммы {Х8+ Xg), (X104

+ Х11), {Х12 + X13) (Х14 + Х15) и разности (X8—

-X9), (Х10 Х11), (Х12 Х1з), (Х14 X15). Суммы поступают на входы блоков бо-6з сдвига, в которых предыдущие результаты с каждым тактом сдвигаются вправо. Разности поступают на элементы 7о-7з задержки, с которых предыдущие результаты через переключатели 2о — 2з поступают на элемен1756901

12 ты Sp, 84, 8в и 812. Аналогично процессор работает следующие два такта: переключатели 1О -13 и 2р-23 переходят в следующие состояния, вычисляются суммы и разности очередных входных пар и заполняются блоки сдвига. После этого первый этап преобразования завершается, заканчивается первый цикл работы процессора.

На пятом такте переключатели 1р 13 вновь устанавливаются в первое состояние, переключатели 2p — 23 в четвертое. На вход процессора поступает новая входная выборка и первые восемь сигналов через переключатели 1О-13, поступают нэ входы сумматоров-вычитателей; Х и Х1 5О, Хг и

Х3-51; Х4иX5 2; ХбиХ7- 53. Вычисляются суммы (Xp + Х1). (Х2 + ХЗ), (X4 + Х5), Хв+ X7) и разности (Хо — Х1), (Xz — Х3), (Х4 — X5). (Х6 — Х7).

Разности поступают на элементы 7Π— 73 задержки, с которых предыдущие результаты через переключатели 2о-23 поступают на элементы 83, 87, 811 и 81 задержки. Суммы поступают на входы блоков 6p — 63, с выходов которых результаты, полученные на первом татке, поступают на входы сумматоров-вычитателей 54и 55,т.е. (Хо+ Х1) и(Хг+Хз) -«54; (Х4+ Х5) и (Хв+ Хт) -«55. Вычисляются суммы (Х +Х1+Xz+Х3),(Х4+Х5+Х6+Хт) ираэности (Xp+ Х1) — (Хг + Х3), (X4+ Х5) — (X6+ XY). Суммы поступают на входы блоков 64 и 65 сдвига, а разности — на элементы 74 и 75 задержки, На шестом такте переключатели 1О-13 устанавливаются во второе состояние, а переключатели 2Π— 23 — в первое. Нулевая группа сумматоров-вычитателей работает аналогично описанному, продолжая преобразование над второй входной выборкой, причем при поступлении информации на элементы 7р-73 задержки предыдущая инфоРмациЯ постУпает на элементы Sp, 84, 8в, S1z задержки, с которых на 16-й, 17-й, 18-й и

19-й выходы поступает часть конечных ре,зультатов преобразования: У16, У1т, У1в и т19

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

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

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

5 работу включается lz-я группа сумматороввычитателей. ПеРеключатели 1р 13 — в пеР8оМ состоянии, а переключатели 2р-23 — в четвертом. Информация из блоков сдвига 64 и 65 поступает на вход сумматора-вычитате1ð ля 56: (Хо+ Х1+ Х2+ Хз) и (Х4+ Х5+ Х6+ Х7)» .66. ВычислЯетсЯ сУмма (Xp+ ... + Хт), котоРаЯ поступает на элемент задержки 7т, и разность (Xp + ... + X3) — (X4 + ...4XY), которая поступает на элемент задержки 76. На деся15 том такте гРУппы lp,!1сУмматоРов-вычитателей продолжают преобразование второй и третьей входных выборок.

В работу включается переключатель 26, который под действием управляющих сигналов от блока синхронизации устанавливается в первое состояние. la вход сумматора-вычитателя 56 из блоков 64 и 65 сдвига поступает следуюЩая информация: (Хв+ Xg+ Х1о+ X11) и (Х1г+ Х 13+

25 + Х14+ X15) 56. Вычисляется сумма (Хв+ ...

+ X15) и разность (X6 + °" + Х11) (Х12 + " +

X15), Разность поступает на элемент задержки 76 с которого предыдущая информация через переключатель 26 поступает на элемент 8г4, задержки, а сумма — на элемент 7т задержки,с которого предыдущая информация поступает на элемент 76 задержки.

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

На одиннадцатом такте переключатель

26устанавливается во второе состояние, переключатели 27, 31, 41 — в первое состояние.

На вход сумматора-вычитателя поступает

40 следующая информация:(Х16+ ... + X1g) и(Xzp»

+... +X23) - 56. Вычисляется сумма(Х16+ ...

+ Хгз) и разность (Х16+ ... + Х1э) — (Хго+ ... +

Xz3), Разность йоступэет на элемент 76 задержки, с которого предыдущий результата

45 через переключатель 26 передается на элемент 825 задержки, а сумма поступает на элемент.7т задержки, с которого предыдущая информация поступает на второй вход переключателя 41. на первый вход которого поступает информация из элемента 7в задержки. Через переключатель 41 на вход сумматора-вычитателя 57 поступает следующая информация: (Хо+ ... + Х7) и (Хв+ ... + Х16)--«57, Вычисляется сумма (Xp + ... +Х16) и разность (Хо+ ... + X7) (Õâ + ... + Х16). Сумма через переключатель 31 передается на элемент Yg задержки, а разность —.на третий выход процессора.

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

1756901 выход переключателя не используется), переключатели 31 и 41 закрыты. На выход сумматора-вычитателя 56 поступает следующая информация: (Х24+ ... + Х27) и (Х26+ ... + Хз1)

56, Вычйсляется сумма (Х2 + .„Хз1) и раз- 5 ность (Х24+ ... X27) (Х26+ .„+ X31). Разность передается на элемент 76 задержки, откуда предыдущий результат поступает на шестой выход процессора, а сумма — на элемент 77 задержки. 10

На тринадцатом такте переключатель 41 устанавливается s первое состояние, переключатель 26 — в четвертое состояние, 27 — в. третьем состояние, а 31 — во второе состояние. На вход сумматора-вычислителя 56 поступает результат преобразования второй входнойвыборки:(Xo +Xl +X2 +X3)и(Х4;

+ Х6 + X6 + X7 ). Вычисляется с мма {Xp +

1 1 I

+„, +Х 7) и разность(Xp + ... + Хз ) — (Х4 + ...

l I 1 1

I ...+ Х7 ). Разность поступает на элемент 76 задержки, а сумма — на элемент 77 задержки, с которого предыдущий результат поступает на второй вход переключателя 41, на первый вход которого поступает информация из элемента 7в задержки. Таким обра- 25 зом, через переключатель 41 на входы сумматора-вычитателя 57 поступает следуЮщая инфОрмация: (Х16+ ... + Х2З) и (X24+ ...+

+ Хз1). Вычисляется сумма (Х16 + ... +Хз1), которая через переключатель 31 поступает на элемент 71о задержки, и разность (X16+... ... + Х2з) — (X24 + ... + Хз1), которая через переключатель 27 поступает на второй выход процессора. Заканчивается четвертый этап преобразования над первой входной 35 выборкой. . На четырнадцатом такте переключатель

26 вновь устанавливается в первое состояние, переключатель 41 — во втброе, 27 — в четвертое. 31 — в третье состояние, На вход сумматора-аычитателя 56 поступает следующая информация; (Хв + ... + Х 11) и (Х 12+ ...

+ Х 16), Вычисляется С1умма (Х в+ ... + Х 16) и

1 l разность (X в + ... + Х 11) — (Х 12+ ... + Х 16).

Разность поступает на элемент 76 задержки, а сумма — на элемент 77 задержки. Пред45

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

Предыдущая информация с элемента 77 задержки передается на второй вход переключателя 41, на первый вход которого поступает информация с элемента.76 задер- жки. Так как переключатель 41 во втором состоянии, то на вход сумматора-вычитателя 57 поступает информация с третьего и четвертого входов переключателя, на которые в свою очередь поступила информация из элементов 79 и 71о задержки. Сумматорвычитатель 57 вычисляет сумму {Хо+ ... + X31) и разность (Хо + ... + X15) — (Х16+ °" + Хз1), Сумма через переключатель 31 поступает на нулевой выход процессора, а разность через переключатель 27 — на первый вход процессора.

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

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

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

t сумматоров-вычитателей t = 1, и-1). Таким образом, если t = n-1, то при практически равном числе сумматоров (2" сумматороввычитателей в предлагаемом процессоре и (2" — 1) сумматоров в базовом обьекте) предлагаемый процессор на каждый.обрабатываемый вектор затратит 2" " = 2 тактУ против (2" + 1) тактов в базовом объекте.

Если же t = 1, то при практически равном затрачиваемом на обработку времени (2" тактов в предлагаемом процессоре и (2" +

+1) тактов в базовом объекте) количество сумматоров-вычитателей в предлагаемом процессоре равно 2 против (2" — 1) суммато- ров в базовом объекте. В случае N = 2 при

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

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

1756901

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

Формула изобретения

Поточно-параллельный процессор Хаара, содержащий группу сумматоров-вычитателей, группу переключателей и блок синхронизации, отличающийся тем„ что, с целью повышения быстродействия в него введены 1 групп сумматоров-нычитателей (t = 1, п-1, N = 2" — размер входной выборки), три группы переключателей, (2 2) блоков сдвига и две группы ыэлементов задержки, причем j-й (1 = О, 2 -1) информационный вход процесса и соединен с 1-м (i = j mod 2 + 2 (j — j mod 2 )/2 ) информационным входом К-f o (K = (j mod 2 — j mod 2)/2 переключателя первой группы, 1-й информационный выход которого (I = О, 1) соединен с I-входом одноименного К-го сумматораоычитателя первой группы, выход суммы mro сумматора-вычитателя первой группы через m-й(m =00,2 -1) блок сдвига соединен — -1 с b-м (b = m mod 2) входом q-го (q = (m — Ь)/2) сумматора-вычитателя второй группы, выход суммы д-го (д =-0,2 " ) сумматора-вычитателя r-й (r = 2, t — 1) группы через (m+ 2"

- 2" ")-й блок сдвига. соединен с р-м (р= m mod 2) входом q-го (q = (m-p)/2) сумматора-вычитателя (г+1)-й группы, выход суммы единственного сумматора-вычитателя (t+1)-й группы соединен с (2 — 1}-и элементом задержки второй группы, выход которого соединен с первым входом переключателя четвертой группы и входом

2 -ro элемента задержки второй группы, выход которого соединен с первым входом переключателя четвертой группы, 1-й оЮод которого (1 = 0,1) соединен с одноименным входом единственного сумматора-нычитателя (t+ 1)-й группы, выход которого соединен с информационным входдм пе екгпочателя третьей группы, I-й (i = О, 2 (п-t.-1 — 1 выход которогочерез(2 + 1+ 1)-йзлементзадержки второй группы соединен с (1+2)-м информационным входом переключателя четвертой группы, а 2(п-т-1)-й выход переключателя третьей группы является первым выходом процессора, выход разности последнего сумматора-нычитателя (t+1)-й группы соединен с информационным входом 2 переключателя второй группы, с-й (с = 1, 2" — 1) выход которого является с-м информационным выходом процессора, выход разности

10 d-ro (d = 0,2 — 2) сумматора-вычитателя через d-й элемент задержки первой группы связан с информационным входом d-ro переключателя второй г1цппы, h-й выход (h= 0,2" — 1) j-го (j = 0,2 ) переключателя второй группы соединен с входом

f-ro (f= j2" +h) элемента задержки, с первого по 2 -й выходы (2-2)-Io переключателя и-1 t второй группы соединены с информационными входами элементов задержки второй

20 группы соответственно с (2" (2 — 2)-го по

n-t-1 (2 — 1)-й, выходы которых являются с 5-го и-t- по 2 "-й информационными выходами процессора, а с (2н + 1)-ro 2" -й выходы (2 — 2)-го переключателя второй группы янляt ются с (2" + 1)-ro (2" )-й информацион:ными выходами процессора, выходы переключателей второй группы с 1-го по (2 -1)-й соединены соответственно с информационными входами элементов за30 держки второй группы соответственно с

1-го по (2" (2 -2) + 2" )-й, выходы с первого по (2" (2 — 1)-й элементов задержки второй груйпы являются с 2"-го по (2" + 5)-й

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

1756901

1756901

1756901

>i i amen

V 8mdn

iv crn

1756901

Ь >

Составитель А,Галантерян

Техред М.Моргентал Корректор Л.Лукач

Редактор И.Дербак

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

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

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

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