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

 

Изобретение относится к вычислительной технике и может быть использовано в автоматических и вычислительных устройствах для осуществления вычисления линейной свертки. Целью изобретения является повышение быстродействия и экономия оборудования за счет уменьшения количества циклов обращения к источнику операндов. Поставленная цель достигается путем введения в устройство 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

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

 

Похожие патенты:

Изобретение относится к вычислительной технике и может быть использовано в составе процессора БПФ

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

Изобретение относится к области цифровой вычислительной техники

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

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

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

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

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

Изобретение относится к автоматике и вычислительной технике и может быть использовано при создании специализированных устройств обработки информации, Цель изобретения - расширение функциональных возможностей устройства за счет вычисления факториалов и перестановок Комбинаторное устройство содержит триггер 1, генератор 2 импульсов, циклические сдвигающие регистры 3, счетчик 4, преобразователь кодов 5, коммутатор 6, формирователь импульсов 7

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

Изобретение относится к специализированным цифровым вычислительным устройствам и может использоваться в декодирующих устройствах двоичных кодов , проверочные матрицы которых содержат элементы конечных полей GF(2m)

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

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

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

Изобретение относится к специализированным цифровым вычислительным устройствам и может использоваться в кодирующих и декодирующих устройствах двоичных кодов, проверочные матрицы которых содержат элементы конечных полей GF (2<SP POS="POST">M</SP>), образованных неприводимыми многочленами вида F(X) = X<SP POS="POST">M</SP> + β<SB POS="POST">M-1</SB>X<SP POS="POST">M-1</SP> + ..

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

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

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