Устройство для свертки по модулю

 

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

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

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

РЕСПУБЛИК (я>s 6 06 Г 11/08

ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕ

ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР) ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4904739/24 (22) 22.01.91 (46) 15.04.93. Бюл. N 14 (72) А.Н.Назаров, (56) Авторское свидетельство СССР

В 922749, кл. G 06 F 11/00, 1980.

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

hh 1124310, кл. G 06 F 11/00, 1984, Изобретение относится к автоматике и вычислительной технике и может быть использовано при построении распознающих систем, контрольно-диагностической аппаратуры и других устройств вычислительной техники.

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

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

Устройство для свертки по модулю содержит первый 1 и второй 2 регистры, входы которых являются группами информационных входов первого и второго чисел устройства, а выход каждого разряда регистров подключен к первому входу соответствующего элемента И первой 3 и второй 4 группы элементов И, а выходы подгрупп из элементов И первой 3 и второй 4 группы соединены с соответствующими входами элементов ИЛИ первой 5 и второй 6 групп элементов ИЛИ.

Выходы элементов ИЛИ 5 и 6 подключены ко входам блока 7 сравнения, соответствующие выходы которого соединены с информационными входами соответствующего

„„!Ы„„1809443 А1 (54) УСТРОЙСТВО ДЛЯ СВЕРТКИ ПО МОДУЛЮ (57) Изобретение относится к автоматк.ке и вычислительной технике. Цель изобретения — повышение быстродействия свертки чисел. Поставленная цель достигается введением двух групп элементов ИЛИ, блока сравнения, группы сумматоров, обеспечивающих организацию считывания информации из приемных регистров параллельно по частям, 2 ил. алгебраического сумматора 8, Выходы устройства подключены через третью группу элементов 9 к выходам сумматоров 8. Вход запуска устройства соединен с единичным входом триггера 10, прямой выход которого подключен к первому входу элемента 11, второй вход которого соединен с выходом генератора 12 импульсов. Выход элемента

И 11 соединен с входом второго элемента 19 задержки, со счетным входом первого счетчика 13, выходы разрядов которого соединены с входами первого дешифратора 14 и с первыми входами соответствующих сумматоров по модулю два 15, выходы которых соединены со входами второго дешифратора 16. Первые входы сумматоров по модулю два 15 подключены к соответствующим разрядным выходам второго счетчика 17, 1-ый выход первого 14 и второго 16 дешифратора подключен ко второму входу 1-го элемента И каждой подгруппы из первой 3 и второй 4 групп элементов И. Счетный вход второго счетчика 17 подключен к выходу переполнения первого счетчика 13 и соединен со вторым входом каждого элемента И 9 третьей группы элементов И и со входом элемента задержки 18, выход которого подключен ко

1809443 входам установки в ноль каждого сумматора 8.

Выход переполнения второго счетчика 17 соединен с нулевым входом три гера 10; инверсный выход которого подключен к входам устайовки в ноль первого 1 и второго 2 регистра, первого 13 и второго 11 счетчиков.

Синхронизирующий вход каждого сумматора 8 соединен с выходом элемента 19 задержки, а вход элемента 19 задержки соединен с выходом элемента И 11.

Функциональная схема блока сравнения 7 изображена на фиг.2.

Блок содержит L вертикальных и L горизонтальных шин, (L х L) элементов И, обозначенных на схеме двойными индексами (1,1), (1,2),...,(L;L), первый из которых номер горизонтальной и второй — вертикальной шин, i-я горизонтальная шина соединена с . первыми входами каждого элемента (-ой строки, второй вход каждого из которых подключен к соответствующей вертикальной шине. Выходы элементов И (i, j) образуют группу выходов блока 7..Устройство для свертки по модулю рабЬтает следующим образом.

По запускающему импульсу триггер 10 открывает второй элемент 11, через который импульсы от-генератора 12 импульсов поступают на счетный вход первого счетчика 13, на выходе которого формируется текущий набор аргументов Х = (О, 1„„,2" "— 1), который поступает на вход. первого дешифратора 14 и поразрядно складывается по модулю в соответствующих сумматорах по модулю два группы 15 с двоичным набором

Х = О, 1,...,2." — 1, формируемым вторым счетчиком 17. Набор (Х 3 т) с выходов сумматоров по модулю два 15 поступает на вход второго дешифратора 1б. Первый 14 и второй 16 дешифратор в соответствии с входным набором формируют считывающий сигнал, который поступает на вторые входы

j-rc элемента И каждой из подгрупп элементов И первой 2 и второй 4 групп элементов

И, Информация, предварительно записанная в первый 1 и второй 2 регистры через их входы, считывается из разрядов, адрес которого соответствует набору Х для каждой подгруппы разрядов первого регистра 1 и (Х 5 т) для каждой подгруппы разрядов второго регистра 2. Информация в регистрах 1 и 2 разбита на„подгрупп; таким образом, свертываемые 2." разрядные числа) представлены в виде блоков S (Х), Sz (Х), где а) (а

Q — 1, 2„...2, номер подгруппы разрядов регистров 1, 2 пр 2" разрядов в каждрй $1(Х) = Si $ (, S1 ..S3. Sz(X) = $2

$z®,.„,$)@ Выборки из подгрупп (Х) из первого и из второго регистров через соответствующие элементы и первой 3 и второй 4 групп элементов И, соответствующие эле5 менты ИЛИ первой 5 и второй групп элементов И одновременно поступают на.входы блока 7. Таким образом, на входы блока 7 одновременно поступают двоичные разряды первого и второго свертываемых чисел

$Р(Х), $Р(Х Е ф (Xz О, 1,...,2" + — 1). Блок

7 сравнения осуществляет сравнение отсчетов и в случае одинакового значения $1 (Х)

15 и Sz((Х В z ) с выхода элемента И елока 7 формируется импульс, который поступает на .информационный вход сумматора 8, где он а

n — k складывается Х М )(Х) Sz (X В т).

20 х=о

Синхронизация процесса суммирования с накоплением с общей цикличностью функционирования устройства осуществляется подачей тактовых импульсов с выхода генератора 12 через элемент 11 И и второй элемент задержки 19. Таким образом, е сумматоре будет сформирована свертка от составных частей чи ел, т,е. от их 2 п-k разрядов К()(г) = $ (*Я ). В то-же время

3р полная свертка определяется из выражения:

У К(а)$„(а)Я 9 2) 35

Таким образом номера подгруппы разрядов чисел определяются числами 0 и (Q Щ Z). Следовательно, номера элементов

И блока 7, которые необходимо соединить с информационными входами одного и того же сумматора, определяются двоичным кодом числа2=0, 1,.„2 — 1 по правилу(! — 1) 5 (j — 1)= Z, где i, j — номер столбца и строки блока 1 (, j-1, 2, 3,...,,2 . Например, разряды 32-х битовых чисел разделены на 2 - 4 блока по

2" = 8 разрядов в каждом, тогда при Z - О необходимо на один и тот же сумматор вывести выходы элементов И блока 7 (1,1), (2,2); (3,3), (4,4); при 2 = 3 — (1,4), (4,1), (2,3), (3,2).

В результате в сумматорах 8 (фиг.1) будет сформировано значение свертки чисел

$ и Sz за 2"" импульса генератора при фиксированном значении. Импульс переполнения с выхода первого счетчика 13 под-: ключает третью rpynny элементов И 9, и код, соответствующий значению свертки Kz(r ), передается на выход устройства. Импульс

1809443

25

35

55 переполнения одновременно поступает на счетный вход второго счетчика 17, который формирует следующий набор (t+ 1), а через первый элемент задержки 18, по окончании считывания предыдущего значения свертки, обнуляет сумматоры 8, подготавливая их к последующей работе, Таким образом„процесс повторяется при т= О, 1, 2,...,2" — 1. . По окончании вычисления всех составляющих свертки, импульсы переполнения с выхода второго счетчика 17 поступают на нулевой вход триггера 10, импульс с нулевого выхода которого обнуляет первый и второй счетчики 13 и 17 и оба регистра 1 и 2, подготавливая устройство для приема и выполнения свертки следующих входных сигналов.

Положительный эффект — повышение быстродействия устройства для свертки по модулю подтверждается следующим. Для свертки чисел, содержащих 2" разрядов, необходимо генерировать 2" импульсов. Время свертки и ри частоте генератора f< у п." базового обьекта составляет tg = 2" -, <г

В предложенном устройстве время сверт ки составляет при той же частоте генератора = 2 -. Т.е, свертка чисел происходит в и-k 1

2" раз быстрее. Причем, чем больше количество разбиений исходной информации на составные части, тем больше быстродействие устройства. Кроме того, сокращается количество разрядов счетчиков, дешифратора и сумматоров по модулю два на 2 единиц, п-k

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

Устройство для свертки по модулю, содержащее первый и второй регистры, первый и второй счетчики, первый и второй дешифраторы, две группы элементов И, состоящие из 1. подгрупп по 2" (n = )log2N(, k = logzl) элементов И в каждой (где L— число входов), третью группу элементов И, группу сумматоров по модулю два, триггер, генератор тактовых импульсов, первый элемент задержки и элемент И, причем информационные входы первого и второго регистров являются входами первого и второго чисел устройства,.единичный вход триггера является запускающим входом устройства, нулевой вход триггера соединен с выходом переполнения первого счетчика, вход установки в "0" которого соединен с входами установки в "0" второго счетчика, первого и второго регистров и инверсным выходом триггера, прямой выход которого соединен с первым входом элемента И, второй вход которого соединен с выходом генератора тактовых импульсов, выход элемента

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

ИЛИ, блок сравнения, второй элемент задержки и группа алгебраических сумматоров, группы информационных входов которых соединены с соответствующими группами выходов блока сравнения, информационные выходы алгебраических сумматоров подключены к вторым входам соответствующих элементов И третьей группы, вход установки в "0" каждого алгебраического сумматора группы соединен с выходом первого элемента задержки,!-е выходы первого и второго дешифраторов соединены с вторыми входами i-x элементов И каждой подгруппы первой и второй групп соответственно, выходы элементов И каждой подгруппы первой и второй групп соединены с входами соответствующих элементов ИЛИ первой и второй групп, выходы элементов ИЛИ первой и второй групп соединены с соответствующими группами входов блока сравнения, вход синхронизации каждого -алгебраического сумматора группы подключен к выходу второго элемента задержки, вход которого соединен с выходом элемента И.

1809443 фигЛ

1809443

Составитель А. Назаров

Техред M.Ìîðãåíòàë Корректор С. Векман

Редактор

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

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

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

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