Устройство для вычисления линейной свертки

 

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

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

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

РЕСПУБЛИК (л)5 G 06 Е 15/31, 9/34

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

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

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4084035/63 (22) 27,06.86 (46) 30,09.91. Бюл. N 36 (71) Специальное конструкторско-технологическое бюро Физико-механического инс- . титута АН УССР (72) Г,И.Малашонок (53) 681.333:681.325 (088,8) (56) Клингман Э. Проектирование специализированных микропроцессорных систем.

М.: Мир, 1985, c,216 — 217.

Heuft R,W., Little W.D. Convolution

Computer/lEEE Transaction on Computer. с 29, М 8. 1980, р.738-740.

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

Цель изобретения — повышение быстродействия и экономия оборудования за счет уменьшения количества циклов обращения к источнику операндов, На фиг.1 представлена функциональная схема предлагаемого устройства; на фиг.2— схема блока управления; на фиг.3 — схема цифровой линии задержки; на фиг.4 — схема одномерного цифрового фильтра (ЦФ): на фиг.5 — схема m-входового сумматора для

m=6.

Устройство содержит блок 1 управления, одномерные цифровые фильтры 2.1—

2.m, цифровые линии задержки 3.1-3.(m-1).

m-входовой сумматор 4, выход 5 тактового сйгнала последовательности операндов Х, Ы 1681309 А1 (54) УСТРОЙСТВО ДЛ Я ВЫЧИСЛЕНИЯ Л ИНЕЙНОЙ СВЕРТКИ (57) Изобретение относится к вычислительной технике и может быть использовано в автоматических и вычислительных устройствах для осуществления вычисления линейной свертки, Целью изобретения является повышение быстродействия и зкономия оборудования за счет уменьшения количества циклов обращения к источнику операндов. Поставленная цель достигается путем введения в устройство m одномерных цифровых фильтров, rn линий задержки, гпвходового сумматора и блока управления, содержащего информацию об источнике операндов. 3 з.п. ф-лы, 5 ил. вход 6 последовательности операндов Х, вход 7 тактового сигнала последовательности операндов Н, вход 8 последовательности операндов Н, выход 9 запроса очередного операнда Х. выход 10.1 запроса начала последовательности операндов Х, адресный выход 10.2, выход 11 сброса в "0" и выход 12 готового результата вычислений, Блок 1 управления содержит задатчик размеров матриц операндов Х, выполненный в виде счетчиков 13 {на m-1 счетных состояний}, 14 (на о+1 счетных состояний), 15 (на и-1 счетных состояний), 16 (на р+1 счетных состояний), схему ИЛИ 17. схему

НЕ 18, схему ИЛИ 19, схемы НЕ 20 и 21 и схемы И 22 и 23.

Каждая линия З.m задержки содержит схему НЕ 24, счетчик 25 (на s=-p n-i-1 счетных состояний) и оперативное запоминающее устройство (СЭУ) 26. выход которого является выходом линии 3,rn задерккг.

1681309

10

5 сумматоров 34.1-34.3, 35, 36 1-го, 2-ro и сл

3-го ярусов соответственно и выход 12, яв- л ляющийся также выходом сумматора 36 и одновременно выходом устройства, те

Устройство работает следующим обра- 15 б зом, с

Известна формула для линейной дву- h мерной свертки с

m — 1 n — 1 ц у,< — — g, hr1xs-r,t-1, (1) 20 ч

r=o i=o где hi1, x, r, 1 — операнды Х и Н устройства.

Внутренняя сумма в выражении (1) представляет собой одномерную линейную свеРткУ и длЯ ее вычислениЯ пРименЯютсЯ 25 в цифровые фильтры 2.1-2.m. Для вычисления внешней суммы в выражении (1) применяется m-входовой сумматор 4. 3

Для подготовки устройства к работе необходимо записать последовательность ко- 30 эффициентов — операндов Н, для этого на вход 8 необходимо подать последовательность операндов Н, сопровождаемых тактовыми сигналами на входе 7.

Темп Работы УстРойства опРеделЯетсн 35 о тактовым сигналом на входе 5. После включения тактового сигнала на входе 5 устройство будет готово к работе только после того, как на выходе 10,1 появится сигнал запроса начала последовательности one- 40 рандов Х (исключение составляет первый сигнал на выходе 10.1, появившийся после включения тактового сигнала на входе 5, его необходимо пропустить, так как устройство 2 может оказаться неготовым). 45

По запросу начала последовательности операндов X (выход 10.1) на входе 6 должен быть установлен первый операнд последовательности Х вЂ” хоо. После этого по запросу очередного операнда последовательности

Х (выход 9) на вход 6 должны поступать очередные операнды последовательности

X: хо1, xo2,...,xpq. На выхоДе 12 УстРойства ь появляются элементы последовательно- с сти двумерной линейной свертки уоо, 55 д уО1,".,fm+q-2,r+p-2 СОПрОВОждаЕМЫЕ таКтО- С вым сигналом на входе 5. Задержка во времени появления элемента уо1 на выходе 12 ф по отношению к моменту поступления one- ц ранда хо1 на вход 6 определяется суммар- и

Каждый цифровой фильтр 2.1 — 2.m содержит и регистров 27,1-27.п для операндов Х, и регистров 28.1 — 28.п для операндов

Н, и умножителей 29.1-29.п, и-входовый сумматор 30 и выход сумматора 30, который служит выходом для одномерного цифрового фильтра, Сумматор 4 содержит m входов, где

m=6,11 регистров 31,1 — 31.6, 32.1 — 32.3, 33. 133.2 1-го, 2-ro и 3-ro ярусов соответственно, ной задержкой на одном одномерном цифровом фильтре и m-входовом сумматоре 4.

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

12 ПОСЛЕ ПОСЛЕДНЕГО ЭЛЕМЕНта Ym+q-1,r+p-2 одной последовательности двумерной линейной свертки у сразу следует элемент уоо едующей последовательности двумерной инейной свертки.

После загрузки операндов последовальности H первый цифровой фильтр 2.1 удет настроен на вычисление одномерной вертки о последовательностью операндов оо,ho1,.„,hoï, которая записана в его регитрах 28,1-28.п. Соответственно второй ифровой фильтр 2.2 будет настроен на выисление свертки с последовательностью перандов h1o,h« „.„Ьп и т,д., m-й цифровой

wlbTp 2.m — с hmo, hm1,...,hmn.

Покажем, что, если в момент прихода ачала последовательности операндов X во сех цифровых фильтрах регистры 27.1-27 и я последовательности Х операндов обнуены, во всех цифровых линиях задержки ,е записаны нули, в каждый такт на вход 6 стройства поступают операнды Х-матрицы

= Д xrj // )1=0,1„...m+g-2; )=01 „„ A+p-2), Коорая читается справа налево и сверху вниз, ричем в левом верхнем углу матрицы опеандов Хо располагается матрица операнов Х, а остальные элементы матриць. перандов Х вЂ” нули, то устройство будет

ычислять элементы у последовательности вумерной линейной свертки. Действительо, пусть матрица операндов Х уже частичо считана, и на вход первого цифрового ильтра 2,1 поступает операнд X>,i, в этот омент на вход второго цифрового фильтра .2 поступает операнд Xs-1,1О, третьего—

8-2д и Т,Д., на ВХОД m-го цифрового цильтра

° П1 Xs-в+1д °

Нумеруя цифровые фильтры 2.1-2 m ислами 0,1,...,m-1, получим в соответствии (1) на выходе i-ro цифрового фильтра реультат линейной свертки и — 1

hr)xs-rä-Р (I=0,1,...,m-1).

1 =О

Эти числа суммируются на m-входовом умматоре 4, в результате на выходе устройтва получаем результат: элементы послеовательности двумерной линейной вертки у1 по формуле (1).

Блок 1 управления предназначен для ормирования последовательности матриы операндов Х в результате дополнения оследовательности операндов матрицы Х

1681309 ческого нуля, свидетельствующий о запросе 55 первого элемента новой последовательности операндов Х, Таким образом, перед приходом первого элемента новой последовательности операндов Х во все цифровые линии задержки нулями. Счетчики 13 и 14 образуют счетчик столбцов матрицы операндов Х, счетчики

15 и 16 — счетчик строк матрицы операндов

Х . Счетчик 14 имеет ц+1-счетное состояние. Сигнал логического нуля на выходе счетчика 14, который появляется при достижении q+1-го состояния, через схему И 22 обеспечивает появление сигнала обнуления на выходе 11, а также прекращает прохождение через схему И 23 тактовых сигналов с входа 5 на выход 9 запроса очередного элемента.

Кроме того, сигнал на выходе счетчика

14 подключен к входу разрешения счета счетчика 13, а через схему НЕ 18 — к входу разрешения счета счетчика 14. Поэтому при его появлении счетчик 14 останавливается, а счетчик 13, имеющий m-1 счетных состояний, начинает счет и отсчитывает m-1 тактов, в течение которых на вход последовательности операндов Х первого цифрового фильтра 2.1 поступают нулевые элементы последних m-1 столбцов каждой строки матрицы операндов Х .

При достижении счетчиком 13 m-1-го состояния на его выходе появляется сигнал логического нуля, который передается на выход схемы ИЛИ 17, устанавливает одновременно счетчики 13 и 14 в исходное состояние и обеспечивает через схему НЕ- 21 появление положительного фронта сигнала на тактовом входе счетчиков 15 и 16, что обеспечивает переход на следующую строку, Аналогично работает счетчик строк матрицы операндов Х, образованный счетчиками 15 и 16. Счетчик 16 имеет Р+1 счетных состояний и отсчитывает первые р строк матрицы операндов Хо, При достижении

Р+1-го состояния сигнал на выходе счетчика

16 через схему И 22 обеспечивает появление сигнала обнуления на выходе 11, а также прекращает прохождение через схему И

23 тактовых сигналов с входа 5 на выход 9 запроса очередного операнда. При этом также счетчик 16 останавливается, а счетчик

15 начинает. счет. Счетчик 15, имеющий и-1 счетных состояний, отсчитывает и-1 нулевых строк матрицы операндов Х, При установке счетчика 15 в и-1-е состояние, т.е, перед поступлением первого элемента последней строки матрицы операндов Хо, на выходе 10.1 запроса начала последовательности операндов Х появляется сигнал логи5

ЗО

3.1 — 3,(m-1) и во все m цифровых фильтров будут записаны нулевые элементы, что необходимо для нормальной работы устройства, а все счетчики блока 1 управления будут находиться в исходных состояниях.

Состояния счетчиков 16 и 14 использованы для управления выборкой операнда последовательноси Х; состояния счетчика

16 (1,2,...,р) соответствуют номеру строки, а состояния счетчика 14 (1,2...„q) — номеру столбца матрицы операндов Х, который должен в этот момент поступать на вход 6 последовательности операндов Х.

Цифровая линия 3 m задержки, изображенная на фиг,З, работает следующим образом.

В течение положительного полупериода тактового сигнала, который инвертируется схемой НЕ 24, происходит запись данных, установленных на входе 03У. По окончании положительного полупериода тактового сигнала значение счетчика 25 увеличивается на единицу и происходит чтение данных из 03У 26 по новому адресу, Поскольку счетчик 25 имеет s счетных состояний и выход счетчика соединен с входом установки начального состояния счетчика, то за состоянием s следует первое состояние. Адрес данных 03У 26 определяется значением счетчика, г азтому данные, записанные в ОЗУ 26, появятся на выходе с задержкой на s тактов.

Каждый цифровой фильтр 2. t-2,m работает так, как в прототипе.

Сумматор 4 разбит на ярусы. На первом ярусе m чисел на входе запоминаются в lTl регистрах 31.1 — 31.6 и попарно суммируются на сумматорах 34.1 — 34.3, результаты суммирования запоминаются в регистрах 32.132.2 второго яруса и снова попарно суммируются и т.д. На последнем 3-м ярусе суммируются два числа (на фиг.5 m=6). Если же для какого-то числа не находится пары, то оно переносится в регистр следующего яруса без изменений. Для синхронизации работы всех регистро . сумматора 4 их тактовые входы соедине и с входом 5 тактового сигнала последовательности операндов Х.

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

1, Устройство для вычисления «инейной свертки, содержащее двумерный цифровой фильтр, источник операндов и блок управления, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия и экономии оборудования, блок управления содержит задатчик размеров матриц, выполненный в виде четырех счетчиков соответственно на

m-1, q+1, и-1 и р+1 счетных состояний, две схемы И, две схемы ИЛИ и три с>;емы НЕ, 1681309

50 причем тактовый вход блока управления подсоединен к тактовым входам первого и второго счетчиков и первому входу первой схемы И, выход первого счетчика подсоединен к первому входу первой схемы ИЛИ, выход второго счетчика подсоединен к входу первой схемы НЕ, второму входу первой схемы ИЛИ, первому входу второй схемы И и входу разрешения счета первого счетчика, выход третьего счетчика подсоединен к первому входу второй схеми ИЛИ, выход четвертого счетчика подсоединен к входу второй схемы Н Е, второму входу второй схемы ИЛИ, второму входу второй схемы И и входу разрешения счета третьего счетчика, выход первой схемы ИЛИ подсоединен к входу третьей схемы НЕ и входам начальной установки первого и второго счетчиков, выход третьей схемы КЕ подсоединен к тактовым входам третьего и четвертого счетчиков, выход первой схемы НЕ подсоединен к входу разрешения счета второго счетчика, выход второй схемы НЕ подсоединен к входу разрешения счета четвертого счетчика, выход второй схемы ИЛИ подсоединен к входам начальной установки третьего и четверого счетчиков и является выходом запроса начала последовательности операндов X блока управления, выход второй схемы И подсоединен к второму входу первой схемы И и является выходом обнуления, выход первой схемы И являешься выходом запроса очередного операнда последовательности Х, а адресные выходи второго и четвертого счетчиков являются выходами адресов операндов Х.

2. Устройство по п.1, о т л и ч а ю щ е ес я тем, что двумерный цифровой фильтр выполнен в виде одномерных m цифровых фильтров, m-1 цифровых линий задержки на

s=p+n-k-1 тактов, где k — количество тактов задержки последовательности Х в цифровых фильтрах, и m-входового сумматора, причем входом устройства для операндов Х является вход последовательности операндов Х первого цифрового цильтра, входом устройства для операндов Н является вход операндов последовательности Н m-ro цифрового фильтра, все цифровые фильтры последовательно соединены между собой так, что выход последовательности операндов Х предыдущего цифрового фильтра подсоединен к входу последовательности операндов

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

m-входового сумматора и тактовому входу блока управления, выход обнуления блока управления подсоединен к входу обнуления первого цифрового фильтра, выход запроса начала последовательности операндов Х, выход запроса очередного элемента последовательности операндов Xи :адресные выходы второго и четвертого счетчиков блока управления подключены к источникам операндов устройства, 3. Устройство по п.1, о т л и ч а ю щ е ес я тем, что цифровая линия задержки содержит счетчик на р+и-k-1 счетных состояний, оперативное запоминающее устройство (ОЗУ) и схему НЕ, причем тактовый вход цифровой линии задержки подсоединен к входу схемы НЕ, выход схемы НЕ подсоединен к тактовому входу счетчика и входу "Чтение-запись" ОЗУ, выход счетчика подсоединен к адресному входу ОЗУ, выход переноса счетчика подсоединен к входу начальной установки счетчика, вход цифровой линии задержки подсоединен к входу данных ОЗУ, выход данных ОЗУ является выходом цифровой линии задержки.

4, Устройство по п.1, о т л и ч а кгпв -е ес я тем, что одномерный цифровой фильтр содержит и последовательно соединенных между собой регистров для последовательностей операндов Х и Н, входы первых регистров соединены с входами последовательноСтей операндов Х и H цифрового фильтра соответственно, и умножителей, первые входы которых соединень с выходами соответствующих регистров последовательности операндов Х; а вторые входы соединены с выходами регистров последовательности операндов Н в обратном порядке, п-входовый сумматор, к входам Которого подсоединены выходы умножителей, а выход соединен с выходом цифрового фильтра, дополнительно соединены с тактовым входом последовательности операндов

Н цифрового фильтра — тактовые входы регистров последовательности операндов Н, с тактовым входом последовательности операндов Х цифрового фильтра — тактовые вхо1681309

10 ды регистров последовательности операндов Х и и-входового сумматора, с выходом последовательности операндов Н цифрового фильтра — выход последнего регистра последовательности операндов Н, с выходом пбследовательности операндов Х цифрового фильтра — выход последнего регистра последовательности операндов X. u>309

1681309

1681309

Составитель В.Белозеров

Техред M,Mîðãåíòàë Корректор M,Ìàêñèìèøèíåö

Редактор А.Лежнина

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

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

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

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