Устройство для вычисления линейной свертки Советский патент 1991 года по МПК G06F17/10 G06F9/34 

сл

с

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

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

Цель изобретения - повышение быстродействия и экономия оборудования за счет уменьшения количества циклов обращения к источнику операндов.

На фиг.1 представлена функциональная схема предлагаемого устройства; на фиг.2 - схема блока управления; на фиг.З - схема цифровой линии задержки; на фиг.4 - схема одномерного цифрового фильтра (ЦФ); на фиг.5 - схема m-входового сумматора для .

Устройство содержит блок 1 управления, одномерные цифровые фильтры 2.1- 2.т, цифровые линии задержки 3.1-3.(т-1), т-входовой сумматор 4, выход 5 тактового сигнала последовательности операндов X,

вход 6 последовательности операндов X, вход 7 тактового сигнала последовательности операндов Н, вход 8 последовательности операндов Н, выход 9 запроса очередного операнда X яыход 10.1 запроса начала последовательности операндов X, адресный выход 10.2, чыход 11 сброса в О и выход 12 готового результата вычислений

Блок 1 управления содержит задатчик размеров матриц операндов X, выполненный в виде счетчиков 13 (ча т-1 счетных состояний), 14 (на q+1 счетных состояний). 15 (на п-1 счетных состояний), 16 (на р+1 счетных состоянии), схему ИЛИ 17 схему НЕ 18, схему ИЛИ 19, схемы НЕ 20 и 21 и схемы И 22 и 23

Каждая линия 3 m задержки содержит схему НЕ 24, счетчик 25 (на s-p-tn k-1 счетных состояний) и оперативное запоминающее устройство (03V) 26 выход которого является выходом линии 3 iTi пдерхч1о

00

ы о ю

Каждый цифровой фильтр 2.1-2.т содержит п регистров 27.1-27.П для операндов X, п регистров 28,1-28.п для операндов Н, п умножителей 29.1-29.п, п-входовый сумматор 30 и выход сумматора 30, который служит выходом для одномерного цифрового фильтра.

Сумматор 4 содержит m входов, где ,11 регистров 31.1-31.6,32.1-32.3,33.1- 33.2 1-го, 2-го и 3-го ярусов соответственно, 5 сумматоров 34.1-34.3, 35, 36 1-го, 2-го и 3-го ярусов соответственно и выход 12, являющийся также выходом сумматора 36 и одновременно выходом устройства,

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

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

m - 1 п - 1

yst- 2 S hijxs-i.t-j, С1)

I 0 J 0

где hij, xs-i, t-j - операнды X и Н устройства.

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

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

Темп работы устройства определяется тактовым сигналом на входе 5. После включения тактового сигнала на входе 5 устройство будет готово к работе только после того, как на выходе 10.1 появится сигнал запроса начала последовательности операндов X (исключение составляет первый сигнал на выходе 10.1, появившийся после включения тактового сигнала на входе 5, его необходимо пропустить, так как устройство может оказаться неготовым).

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

X: xoi, xo2Xpq. На выходе 12 устройства

появляются элементы последовательности двумерной линейной свертки уоо, yoi....,ym+q-2,n+p-2, сопровождаемые тактовым сигналом на входе 5. Задержка во времени появления элемента yoi на выходе 12 по отношению к моменту поступления операнда xoi на вход 6 определяется суммарной задержкой на одном одномерном цифровом фильтре и m-входовом сумматоре 4

Устройство работает в конвейерном режиме. По окончании свертки одной последовательности операндов X устройство готово для вычисления свертки с другой последовательностью X операндов, так что на выходе 12 после последнего элемента ym+q-i,n+p-2 одной последовательности двумерной ли0 нейной свертки у сразу следует элемент уоо следующей последовательности двумерной линейной свертки.

После загрузки операндов последовательности Н первый цифровой фильтр 2.1

5 будет настроен на вычисление одномерной свертки с последовательностью операндов hoo,hoi,.,,,hon, которая записана в его регистрах 28.1-28.п. Соответственно второй цифровой фильтр 2.2 будет настроен на вы0 числение свертки с последовательностью

операндов rno,hnhin и т д., m-й цифровой

фильтр 2.гп - с hmo, hmihmn.

Покажем, что, если в момент прихода начала последовательности операндов X во

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

0 Х°-//хц°//)И),1m+q-2; j 01n+p-2), которая читается справа налево и сверху вниз, причем в левом верхнем углу матрицы операндов Х° располагается матрица операндов X, а остальные элементы матрицы

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

0 фильтра 2.1 поступает операнд Xs,t°, в этот момент на вход второго цифрового фильтра 2.2 поступает операнд Xs-i,t°, третьего - Xs-2,t° и т.д., на вход m-го цифрового цильтра 2.m - Xs-m+i,t°.

5 Нумеруя цифровые фильтры 2.1-2 m

числами 0,1т-1, получим в соответствие

с (1) на выходе f-ro цифрового фильтра ре зультат линейной свертки

hijXs-i,t-j° (,1m-1).

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

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

нулями. Счетчики 13 и 14 образуют счетчик столбцов матрицы операндов Х°, счетчики

15и 16 - счетчик строк матрицы операндов Х°. Счетчик 14 имеет q+1-счетное состояние. Сигнал логического нуля на выходе счетчика 14, который появляется при достижении q+1-ro состояния, через схему И 22 обеспечивает появление сигнала обнуления

на выходе 11, а также прекращает прохождение через схему И 23 тактовых сигналов с входа 5 на выход 9 запроса очередного элемента.

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

14подключен к входу разрешения счета счетчика 13, а через схему НЕ 18 - к входу разрешения счета счетчика 14. Поэтому при его появлении счетчик 14 останавливается,

а счетчик 13, имеющий т-1 счетных состояний, начинает счет и отсчитывает т-1 тактов, в течение которых на вход последовательно- сти операндов X первого цифрового фильтра 2.1 поступают нулевые элементы последних т-1 столбцов каждой строки матрицы операндов Х°.

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

Аналогично работает счетчик строк мат- рицы операндов Х°, образованный счетчиками 15 и 16. Счетчик 16 имеет Р+1 счетных состояний и отсчитывает первые р строк матрицы операндов Х°. При достижении P+1-ro состояния сигнал на выходе счетчика

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

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

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

Состояния счетчиков 16 и 14 использованы для управления выборкой операнда последовательноси X: состояния счетчика 16 (1,2,...,р) соответствуют номеру строки, а

состояния счетчика 14 (1,2q) - номеру

столбца матрицы операндов X, который должен в этот момент поступать на вход 6 последовательности операндов X.

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

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

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

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

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

1, Устройство для вычисления линейной свертки, содержащее двумерный цифровой фильтр, источник операндов и блок управления, отличающееся тем, что. с целью повышения быстродействия и экономии оборудования, блок управления содержит задатчик размеров матриц, выполненный в виде четырех счетчиков соответственно на m-1, q+1, п-1 и р+1 счетных состояний, две схемы И, две схемы ИЛИ и три схемы НЕ,

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

результат свертки, подсоединен к соответствующему входу m-входового сумматора, выход m-входового сумматора является выходом устройства, вход тактового сигнала

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

0 входу тактового сигнала последовательности операндов X каждого цифрового фильтра, входу тактового сигнала каждой цифровой линии задержки, тактовому входу rn-входового сумматора и такговому входу

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

0 последовательности операндов X и адресные выходы второго и четвертого счетчиков блока управления подключены к источникам операндов устройства,

содержит счетчик на p+n-k-1 счетных состояний, оперативное запоминающее устройство (ОЗУ) и схему НЕ, причем тактовый вход цифровой линии задержки подсоеди0 нен к входу схемы НЕ, выход схемы НЕ подсоединен к тактовому входу счетчика и входу Чтение-запись ОЗУ, выход счетчика подсоединен к адресному входу ОЗУ, выход переноса счетчика подсоединен к входу ка5 чальной установки счетчика, вход цифровой линии задержки подсоединен к входу данных ОЗУ, выход данных ОЗУ является выходом цифровой линии задержки.

содержит п последовательно соединенных между собой регистров для последовательностей операндов X и Н, входы первых регистров соединены с входами

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

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

5 фильтра, дополнительно соединены с тактовым входом последовательности операндов Н цифрового фильтра - тактовые входы регистров последовательности операндов Н, с тактовым входом последовательности операндов X цифрового фильтра - тактовые эходы регистров последовательности операндов X и n-входового сумматора, с выходом последовательности операндов Н цифрового фильтра - выход последнего регистра поU ff

i i i i i i

Mr

ik 4

1м

следовательности операндов Н, с выходом последовательности операндов X цифрового фильтра - выход последнего регистра последовательности операндов X.

JS

т

Фиг. 1

Фиг. 2

мф

/-

о

01

: . Т

81

У

Зп/г/

и

60С1891

1-й ярус

Ј

2- и прус

ш

Si

т

-

т

о

№

fs

Ts

fNj

в

$

Xi

r

Ш

-N

Фив. 5

5-й ярус

Ј

LN

56

П Ґ

«V4