Систолический процессор обобщенного дискретного преобразования

 

Изобретение относится к автоматике и вычислительной технике и может быть использовано в высокопроизводительных системах цифровой обработки и сжатия изображений, а также в системах спектрального анализа. Цель изобретения - расширение функциональных возможностей за счет обеспечения сжатия информации. Процессор содержит блок 1 из N (N - размер преобразования ) регистров 2 сдвига, N арифметических блоков 3, объединенных в матрицу 4, генератор 5 двумерных базисных функций, элемент 6 задержки, счетчик 7, дешифратор 8, сумматор 9, элемент 10 задержки и регистр 11.4 ил., 1 табл.

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

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

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

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

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

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

1Ф

16

f7 (21) 4707951/24 (22) 21.06.89 (46) 23.05.91. Бюл. М19 (71) Институт технической кибернетики АН

БССР (72) А.Г.Мачнев, P.Х.Садыхов и С.А.Золотой (53) 681.32 (088.8) (56) Авторское свидетельство СССР

М 1363243, кл. G 06 F 15/332, 1986.

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

М 1471200, кл, G 06 F 15/332, 1987. (54) СИСТОЛИЧЕСКИЙ ПРОЦЕССОР

ОБОБЩЕННОГО ДИСКРЕТНОГО ПРЕОБРАЗОВАНИЯ... Ы „„1651295 А1 (57) Изобретение относится к автоматике и вычислительной технике и может быть использовано в высокопроизводительных системах цифровой обработки и сжатия иэображений, а также в системах спектрального анализа, Цель изобретения — расширение функциональных возможностей за счет обеспечения сжатия информации. Процессор содержит блок 1 из N (N — размер преобразования) регистров 2 сдвига, N арифметических блоков 3, обьединенных в матрицу 4, генератор 5двумерных базисных функций, элемент 6 задержки, счетчик 7, дешифратор 8, сумматор 9, элемент 10 задержки и регистр 11. 4 ил., 1 табл. (3 (1651295

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

Целью изобретения является расширение функциональных возможностей путем

Выполнения сжатия информации.

Дискретное двумерное обобщенное преобразование можно выполнять используя двумерные функции Виленкина-Крестенсона (ВКФ), При этом коэффициент fI, матрицы преобразования F вычисляется следующим образом:

Л1 — 1Л1 — 1 а.1 8! ", =о =о где а1 = (А), $ 1 = (Яп )ц; .

S II = V(m,ï,x,у) I(V(m,x) V(n,ó)); m,n = О,N-1;

А — матрица отсчетов сигнала;

SI> — матрица значений двумерной функции;

V(m,x), V(n,у) — ВКФ по соответствующим координатам.

Двумерные ВКФ можно представить в удобном для их формирования виде:

V(m,ï,х,у) =- V(m,x)8V(n,ó), (2) гдето- символ Кронекеровского произведения.

Система ВКФ V(m,х), определяемая обычно на конечном интервале N = P, при

Р = 2 включает фукнции Уолша, при

Р = К(а =1) — дискретные экспоненциальные функции. Аналитически ВКФ могут быть получены как произведение соответствующих обобщенных функций Радемахера: а

V(m,х) — — Ц (X(k,x)) к (3)

k = 1

В свою очередь обобщенные функции

Радемахера определяются следующим соотношением: - !2>Рр.еп1 (х/р "), (4) где Р— простое число:

i — мнимая единица; а =!Оср N;

k=0.1,..., а; х = 0,1„...¹1;

ent() -целая часть, B выражении (3) m = 0,1...„N-1 — номер

ВКФ; g — разрядные коэффициенты в Р-ичном представлении числа m = с11р + q ð +

+...+ qa p

На фиг.1 представлена структурная схема процессора; на фиг.2 и 3 — структурные схемы соответственно арифметического блока и генератора двумерных базисных

50 функций; на фиг.4 — первые ILIe(,тнадцать двумерных функций Фурье, Систолический процессор дискретного обобщенного преобразования содержит (фиг.1) блок 1 сдвиговых регистров 2, арифметические блоки (АБ) 3 линейной матрицы

4, (цифровой) генератор 5 двумерных базисных функций, первый элемент б задержки, счетчик 7 (импульсов), дешифратор 8 (с импульсным выходом), сумматор 9, второй элемент 10 задержки, регистр 11, группу информационных входов 12, входы 13 и 14 номера функции, вход 15 запуска, тактовый вход 16, вход 17 кодов функции. информационный выход 18 и выход 19 синхронизации, АБ 3 (фиг,2) содержиг умножитель 20, сумматор 21 и регистр 22, Цифровой генератор 5 двумерных базисных функций (фиг.3) содержит элемент

23 задержки, блоки 24 и 25 постоянной памяти (ПЗУ), регистр 26, умножитель 27 и сдвиговые регистры 28 и 29.

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

Nl = ехр(— ) /N). При этом сама функция г.7г

def(m,ï,х,у) находится на пересечении стол6иа, определяемого функцией def(m,x), и строки, определяемой функцией def(n,ó), Б таблице представлена диаграмма работ каждого АБ в различные временные такты при вычислении одного коэффициента преобразования для размерности равной 4.

Процессор работает следующим образом.

Вначале производится настройка генератора 5 на требуемый базис ВКФ, Зто осуществляется путем последовательной подачи HB входы 13 и l4 двоичных кодов номеров m,n функций выбранного базиса

ВКФ (например, Фурье, где гп,п = О,N-1), на вход 17 — значений функций, а на вход 15— соответствующих управляющих сигналов для записи информации. При этом двоичные коды являются адресами. Так как обработка двумерных сигналов (иэображений) обычно осуществляется "окном" небольшой размерности, то этот процесс не требует значительных временных затрат.

Затем на группу входов 12 последовательно подаются соответствующие значения исходных данных a;i(i,j =- 1 N), на входы

13 и 14 — коды номеров требуемой двумерной функции def(m,n,х,у), а на вход 15— сигналы запуска генератора (сигналы считывания информации). На вход 16 процессора подается (2N-1) тактовых импульсов. Ðàñ1651295

10 столбец а13,а23,а33,а4з данных, на выходы ли50

55 смотрим работу устройства для случая NxN=- 4х4 при m = 3 и n = 1.

По первому тактовому импульсу значения первого столбца данных а11,а21,а31,а41 заносятся в соответствующие 1-разрядные регистры 2 сдвига блока 1. которые осуществляют задержку íà (1-1) такт, где i — номер выхода блока 1 (а следовательно, и номер регистра 2). В результате только на первом выходе блока 1 появляется а11, а на остальных выходах будет сигнал "0". Одновременно только на первом выходе генератора 5. появляется $п = Wo (фиг.4), а на остальных выходах — "0". АБ 3 линейной матрицы 4 работают в соответствии со следующим рекурсивным алгоритмом:

С1" = С1" "+ ац. Skj, (5) где k — номер шага вычислений, k j = 1,4.

При этом С = О. Следовательно, в АБ 31 (см.таблицу) будет найдено произведение

1 а11 Wo = C1, которое поступает в АБ 32.

Одновременно тактовый импульс проходит элемент 6 задержки и записывается в счетчик 7, осуществляющий подсчет поступающих импульсов, а также приходит на вход записи регистра 11. Так как в исходный момент содержимое регистра 11 оавно нулю, на вход сумматора 9 поступает "0". На другой вход суммматора 9 одновременно поступает сигнал "0 с выхода АБ 34, и поэтому на выходе сумматора 9 значение "0", которое перезаписывается в регистр 11 тактовым импульсом.

По второму тактовому импульсу в блок

1 записываются значения второго столбца данных а12,а22.аз2,а42. Одновременно на выходах блока 1 появляются а12 и а21, а на выходах генератора 5 — значения функции

S12 = W3 и S21 = W1 (фиг4).

АБ 32 вцчисляет Cf = C1+ а21 W1, а АБ

31 С2= д12 W3 (см,таблицу).

По третьему тактовому импульсу в блок

1 сдвиговь1х регистров записывается третий нейной матрицы 4 поступают очередные значения а1з,а22,а31 и соответственно S13 =

=W2, S22 = WO, S31 = W2, АБ 3 матрицы рабатают в соответствии с (5) и вычисляют Cj =

= аз1 W2;C) = С2+ а22 Wo; С1 = С1+аз1 W2 (см.таблицу), По четвертому импульсу в блок 1 заносятся данные а14,a24,аз4,а44 четвертого столбца, а на его выходах появляются а14,а23,дЗЗ,a41, Одновременно на выходах генератора 5 формируются s14 = W1, s 23 =

° = W3; s32 = W1 и s 41 == W3, (см. фиг. 4). AS

31 -" Зз вычисля ют соответствен но C) = a 14 W1;

Сз = С + а23 W3; С2 = С2+ а32 W1, а АБ 34 находит значениеС1 = С1+ а41 W3 (см.таблицу). Вычисленное значение С1 проходит сумматор 9 без изменения (так как на второй вход сумматора 9 поступает "0" с выхода регистра 11) и записывается в регистр 11 тактовым импульсом с выхода элемента 6 задержки. Задержка на элементе 6 необходима для того. чтобы вычислительный процесс в сумматоре 9 оканчивался раньше, чем осуществится запись результата в регистр 11, Таким образом, за первые N тактов (N = 4) происходит вычисление суммы произведений С1 соответствующих элементов первого столбца исходных данных ап и первого столбца значений двумерной функцИИ 5.1. ВЫЧИСЛЕНИЕ fm В СООтВЕтСтВИИ С (1) осуществляется теперь следующим образом:

fmn =, «„С, ., (6)

1 — 1 где .1 — номер столбца.

С каждым последующим тактовым импульсом происходит вычисление последующих сумм произведений остальных столбцов исходных данных и двумерной функции С2,CÇ,C) (см.таблицу). При этом осуществляется накопление результатов в регистре 11, т.е. вычисление fm<.

Как только счетчик 7 подсчитает (2N - 1) тактовых импульсов, то на выходе подключенного к нему дешифратора 8 появляется импульс, который поступает на выход 19 и сигналузирует о получении в регистре 11, а следовательно, и на выходе 18 процессора необходимого коэффициента преобразования, определяемого двумерной функцией

def(m,n,õ,ó). Одновременно импульс с выхода дешифратора 8 поступает на вход элемента 10 задержки и, появившись на его выходе, производит установку в исходное состояние ("0") счетчик 7 и регистр 11. Задержка на элементе 10 необходима для считывания результата с выхода регистра 11 до его установки в исходное состояние. Процессор готов к вычислению новых коэффициентов.

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

Блок 1 сдвиговых регистров работает следующим образом.

Тактовыми импульсами информация а,1 с входа 12 заносится и сдвигается в ре -ист" рах 2, число разрядов в которых соответствует номеру регистра 2. При этом исходные

1651295

35 рически программируемые ПЗУ 24 и 25, Так как базисные функции V(m,х) и V (п,у) имеют

55 данные BIJ поступают на вход последовательного ввода информации в регистр 11 (т.е. занесение осуществляется путем сдвига на один разряд), а процесс сдвига производится по переднему фронту тактового

Импульса, Так как регистр 21 имеет один разряд, регистр 2 — два разряда и т,д., то регистр 2> не производит задержки инфор/чации, регистр 2 осуществляет задержку а один такт, регистр 2з — на два такта и т.д., оэтому по первому тактовому импульсу информация появляется только на выходе ре гистра 21, а следовательно, только на первом выходе блока 1. По второму импульсу появляется информация и на втором выходе блока 1 и т.д.

АБ 3i работает следующим образом.

На входы умножителя 20 поступают aJj ,и SJJ, последний производит их перемноже ние, а результат произведения поступает на ,один из входов сумматора 21, на второй

| вход которого подается результат вычисле ния (5) из АБ Зь<. Полученная сумма с выхода ,сумматора 21 записывается в регистр 22 по заднему фронту тактового импульса (того

,тактового импульса, под действием которого в АБ 3 поступили соответствующие щ,эи ).

Генератор 5 работает следующим образом.

В режиме настройки на вход 17 поступают значения заданных базисных функций, а на входы 13 и 14 — двоичные коды номеров функции, служащие одновременно адресами для записи информации в электодинаковые значения (для функции с одинаковыми m,n), то занесение информации осуществляется одновременно по одинаковым адресам в оба ПЗУ (по одной шине 17) управляющими сигналами по входу 15. При этом адреса последовательно увеличиваются, а функции V(m,х) и V(n,у) записываются соответственно в ПЗУ 25 и 24, В режиме генерации требуемой двумерной функции V(m,n,х,у) по двоичным кодам

m и и на выходах 13 и 14 (например.

def(3,1,х,y)) сигналами считывания информации (запуска генератора) на входе 15 осуществляется выборка значений соответствующих функций (например, def(3,х) и def(1,y)). Значения функций по установочным входам заносятся в соответствующие регистры 29 и 26. При этом для функции def(3,х) в регистр 29 будут записаны значения Ф/о,Wз,ФЬ,W1, а для функции

def(1,у) в регистре 26 будут Wo,W1,М/ъУЧэ. С выходов регистра 26 значения функции

def(1,у) поступают на входы умножителей

27, на другие входы которых поступает первое значение (Wo) функции бе1(3,х) с выхода регистра 29. На выходах умножителей 27 в соответствии с (2) формируется первый столбец двумерной функции def(3,1,х,у); (WoW>WzWaj (см.фиг.4), По переднему фронту первого тактового импульса полученные значения первого столбца функции def(3,1,х,у) записываются в регистры 28.

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

5 появляется только первое значение первого столбца (Wo), Одновременно первый тактовый импульс поступает на вход элемента

23 задержки, появившись на его выходе, производит сдвиг содержимого регистра 29 в сторону младшего разряда (в сторону выхода), В результате на выходе регистра 29 появляется второе значение (О/з) функции

def(3,1,х.у), Задержка на элементе 23 необходима для того, чтобы осуществить запись результатов в регистры 28 прежде, чем появится новое значение функции def(3,1,х.у) на входе регистра 29. На выходе умножителей

27 появляется второй столбец функции

def(3,1,х,у): (WzWoWlWz) (фиг,4), который заносится в регистры 28 вторым тактовым импульсом, На выходах регистра 28 появляются значения М/з,W1 функции def(3,1,x,у), требуемой двумерной функции (фиг.4), значения которых последовательно появляются на выходах регистров 28.

Аналогичным образом формируются другие функции def(m,n,x,у), а также функции в других базисах ВКФ.

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

Систолический процессор обобщенного дискретного преобразования, содержащий блок сдвиговых регистров,N (N — размер преобразования) арифметических блоков, сумматор и регистр, причем i-й (i = 1Я) выход блока регистров подключен к первому информационному входу i-го арифметического блока, выход j-го (J = 1,N - 1)-го арифметического блока подключен к второму информационному входу (j + 1) = го арифметического блока, выход N-го арифметического блока подключен к первому входу сумматора, I-й информационный вход блока сдвиговых регистров является i-м информационным входом группы процессора, тактовым входом которого являются соединенные между собой тактовые входы арифметических блоков и блока регистров, отличающийся тем, что. с целью расширения функциональных возможностей путем обеспечения сжатия информа10

1651295

AS/31

АБ/Зг

A6/Зз

АБ/34 омер такта

Выход 18

С1 =О+а 11 з11

С11=0+а12 з 1г

С1З=О+а1З З1З

С14=0+а14 з14

0

0+C1 C1+C2 = Х1

Ъ+Сз = Ь

Хг+ С4

С1 =С111+а21 з21

С2 =С2 +а22 $22

Сз =Сз +агз згз г

С4 =С4 +д24 $24

2 1

С1 =С1+аз1 зз1 з

С2 =С2 +а32 з32 з г

Сз =Сз+азз s33

3 2

С4 =С4 +а34 з34

3 2

С1 =С1 +а41.з41 з

С2 =Сг+а42 з42

4 3

Сз = Сз +а43 з4з

4 3

С4 =С4 +а44 s44 з ции, в него введены два элемента задержки, счетчик, дешифратор и генератор двумерных базисных функций, выход i-й функции которого подключен к входу задания коэффициентов 1-го арифметического блока, вы- 5 ход первого элемента задержки подключен к входу разрешения записи регистра и счет ному входу счетчика, информационный выход которого подключен к входу дешифратора, выход которого является вы- 10 ходом синхронизации процессора и подключен к входу второго элемента задержки, выход которого подключен к установочным входам счетчика и регистра, выход которого является информационным выходом процессора и подключен к второму входу сумматора, выход которого подключен к информационному входу регистра, вход первого элемента задержки соединен с тактовым входом генератора двумерных базисных функций и подключен к тактовому входу процессора, первым и вторым входами номера функции и входом кодов функции которого являются соответственно первый и второй входы номера функции и вход кодов функции генератора двумерных базисных функций, вход запуска которого является входом запуска процессора.

1651295

Wy

Wy

Юр Фф

ИФ ее Iiy

<о

grz

IV2

®2

W0

W2

1 е0 "Ъ

Ко

+z II o И

@3 еу1

Редактор A. Петраш е

Заказ 2684 Тираж 418 Подписное

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

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

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

0 феу(о,у) yf

f а ey(g,х) <йу(1,x) сну(2М «g(З,Х

И W WZIV

IVZ N IVy

+0 +1 УЗ 11 о ®1 И

Составитель H. Баранов

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