Устройство для свертки по модулю Советский патент 1993 года по МПК G06F11/08 

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

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

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

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

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

СО

с

00 О

ю

CJ

входам установки в ноль каждого сумматора 8. Выход переполнения второго счетчика 17 соединен с нулевым входом триггера 10, инверсный выход которого подключен к входам установки в ноль первого 1 и второго 2 регистра, первого 13 и второго 17 счетчиков. Синхронизирующий вход каждого сумматора 8 соединен с выходом элемента 19 задержки, а вход элемента 19 задержки соединен с выходом элемента И 11.

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

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

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

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

счетчиком 17. Набор (X ® т) с выходов сумматоров по модулю два 15 поступает на вход второго дешифратора 16. Первый 14 и второй 16 дешифратор в соответствии с вход- ным набором формируют считывающий сигнал, который поступает на вторые входы j-ro элемента И каждой из подгрупп элементов И первой 2 и второй 4 групп элементов И. Информация, предварительно записанная в первый 1 и второй 2 регистры через их входы, считывается из разрядов, адрес которого соответствует набору X для каждой подгруппы разрядов первого регистра 1 и

(X $ т) для каждой подгруппы разрядов второго регистра 2. Информация в регистрах 1 и 2 разбита на,подгрупп: таким образом,, свертываемые 2П разрядные числа представлены в виде блоков Si(Q)(X), Sa1 Ч), где Q - 1, 2,...,2k, номер подгруппы разрядов регистров 1, 2 по 2n k разрядов в каждой Si(Xj - Si(1VSi(4 Si(3)-..,S2(X) S20),

S2P),....S2()- Выборки из подгрупп (X) из первого и из второго регистров через соответствующие элементы И первой 3 и второй 4 групп элементов И, соответствующие эле- менты ИЛИ первой 5 и второй групп элементов И одновременно поступают на входы блока 7. Таким образом, на входы блока 7 одновременно поступают двоичные разряды первого и второго свертываемых чисел

Si(Q)(X), S2(Q)(X $ т); (Х2 - 0,1 ,...,2n-k - 1). Блок 7 сравнения осуществляет сравнение отсчетов и в случае Одинакового значения )

и X И т) с выхода элемента И блока 7 формируется импульс, который поступает на информационный вход сумматора 8, где он

2П - 1 складывается Z S/Q)(X)S2(Q)(XI8 т).

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

генератора 12 через элемент 11 И и второй элемент задержки 19. Таким образом, а сумматоре будет сформирована свертка от составных частей чисел, т.е. от их разрядов K(Q)(,r) Si(Q)S2(Q). В то-же время

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

KZ(T) 2 ЛЛИ z) (т)

Q 1

Таким образом номера подгруппы разрядов чисел определяются числами Q и

(Q $ Z). Следовательно, номера элементов И блока 7, которые необходимо соединить с информационными входами одного и того же сумматора, определяются двоичным кодом числаг 0,1,..,,2k-1 по правилу (i-1) и 0 - 1)

z, где i, j - номер столбца и строки блока 7

i, j 1, 2, 3,...,2k. Например, разряды 32-х

битовых чисел разделены на 2 4 блока по

8 разрядов в каждом, тогда при Z О

необходимо на один и тот же сумматор вывести выходы элементов И блока 7 (1,1), (2,2),

(3,3), (4,4); при Z -. 3 - (1,4), (4,1). (2,3), (3.2).

В результате в сумматорах 8 (фиг.1) будет сформировано значение свертки чисел Si и За за импульса генератора при фиксированном значении. Импульс переполнения с выхода первого счетчика 13 под- кл ючает третью группу элементов И 9, и код, соответствующий значению свертки К2(т), передается на выход устройства Г Импульс

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

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

1 базового объекта составляет tB 2п-х-.

Тг

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

n-k

1

Т

Т.е. свертка чисел происходит в

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

Формула изобретения Устройство для свертки по модулю, содержащее первый и второй регистры, первый и второй счетчики, первый и второй дешифраторы, две группы элементов И, состоящие из L подгрупп по (n log2N, к logaL) элементов И в каждой (где L - число входов), третью группу элементов И, группу сумматоров по модулю два, триггер, генератор тактовых импульсов, первый элемент задержки и элемент И, причем инфор- мационные входы первого и второго регистров являются входами первого и второго чисел устройства, .единичный вход триггера является запускающим входом устройства, нулевой вход триггера соединен с выходом переполнения первого счетчика,

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

0 с соответствующими входами первого дешифратора и с первыми входами соответствующих сумматоров по модулю два группы, выходы которых соединены с соответствующими входами второго дешифратора, вто5 рые входы сумматоров по модулю два группы подключены к соответствующим разрядным выходам первого счетчика, счетный вход которого соединен с выходом переполнения второго счетчика, с входом

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

. t

:H

фаз. 2

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