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

 

Изобретение относится к вычислительной технике и предназначено для использования в цифровых вычислительных устройствах. Цель изобретения - сокращение времени свертки - достигается введением дополнительного блока сравнения, элемента ИЛИ - НЕ и элемента "Запрет". Сущность для свертки по модулю P формируются константы по следующему закону: const 1 = P; const 2 = 2P; const 3 = 4P; const i = (i - 1) 2P, ...; const n = (n - 1)2P, затем находят остатки чисел A_k-const 1, ..., A_k-const n . Если величина любого остатка равна нулю, то число A_k делится на модуль P нацело и остаток равен нулю. Если величина остатка не равна нулю, то из всех остатков A_k-const i выбирают наименьший положительный, значение которого лежит в пределах 1≅ a¹_k≅ 2P-1 , и уже от него формируются новые остатки A_k-const(i)-const1, ..., (A_к-const i)-const n , из которых выбирают значение a_к , которое лежит в пределах 1≅ a_к≅ P-1 . 1 ил.

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

Целью изобретения является сокращение времени свертки.

Сущность изобретения заключается в том, что число элементов, входящих в состав устройства, определяется выражением n=A_max/2P , а число констант, необходимых для нормального функционирования, определяется выражением n = n₁ + 1. Константы формируются по следующему закону const1 = P; const2 = 2P; const3 = 4P;...; const i = (i-1) ˙2P;...; const n = n₁ 2P (1) Вычитатели формирует остатки чисел A_k - const1; A_k - const 2... A_k- constn. Если величина любого остатка равна нулю, то число A_k делится на модуль Р нацело и остаток равен нулю. Если величина остатка не равна нулю, то из всех остатков A_k - const i выбирают меньший, значение которого лежит в пределах 1≅ a_k ≅ 2P-1, и уже от него формируют новые остатки (A_k - consti) - const1; (A_k - consti) - const2;...; (A_k - consti - constn, из которых выбирают значение a_k, которое лежит в пределах 1 ≅ ≅ a_k ≅ P-1.

Сущность изобретения реализуется за счет введения новой совокупности конструктивных признаков, определяющих его соответствие критерию "Новизна".

Введение элемента ИЛИ-НЕ обеспечивает определение моментов, при которых первый регистр обнулен, и выдачу управляющих сигналов для запирания элемента "запрет".

Введение элемента "запрет" обеспечивает исключение подачи сигнала об окончании процесса формирования остатка в том случае, если в первом регистре информация отсутствует.

Введение дополнительного блока сравнения обеспечивает нахождение значения a_k, 0 ≅ a_k ≅ P-1 и запись его в выходной регистр.

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

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

На чертеже представлена функциональная схема устройства для свертки по произвольному модулю.

Устройство содержит первый 1 и второй 2 регистры, группу вычитателей 3, группу блоков сравнения 4, группу элементов И5, группу коммутаторов 6, дополнительный коммутатор 7, первый 8 и второй 9 элементы ИЛИ, элемент задержки 10, дополнительный блок сравнения 11, элемент ИЛИ-НЕ 12 и элемент запрета 13.

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

В исходном состоянии на входы задания констант устройства в соответствии с (1) поданы значения констант, которые поступают на первые входы группы вычитателей 3. Значение const1=P_i подается также на вторые входы группы блоков сравнения 4 и на вторые входы дополнительного блока сравнения 11. Регистры 1 и 2 обнулены, поэтому на объединенных входах группы вычитателей 3, информационных входах регистра 2, входах элемента ИЛИ-НЕ 12 и первых входах дополнительного блока сравнения 11 информация отсутствует, на выходах вычитателей 3 присутствуют в инверсном коде значения констант (O - consti = - consti), следовательно на выходах блоков сравнения 4 присутствуют сигналы (-consti < P), которые на выход ни одного из элементов И группы не проходят, следовательно, коммутаторы 6 группы разомкнуты, с выхода "меньше" дополнительного блока сравнения 11 сигнал на выход устройства не поступает, так как элемент "запрет" 13 закрыт сигналом, поступающим с выхода элемента ИЛИ-НЕ 12, так как регистр 1 обнулен.

Двоичный код числа A_k, от которого необходимо сформировать остаток по заданному модулю P_i, подается на информационный вход устройства. Одновременно на выход запуска устройства поступает управляющий сигнал, который открывает дополнительный коммутатор 7 и через элементы ИЛИ 8 и задержки 10 воздействует на вход записи первого регистра 1, на информационные входы которого с выхода дополнительного коммутатора 7 поступает код числа A_k, в результате чего код последнего записывается в регистр 1. Код числа с выхода регистра 1 поступает на входы вторых операндов группы вычитателей 3, на первые входы блока 11 сравнения, входы элемента ИЛИ-НЕ 12, и на информационные входы второго регистра 2, в результате чего на выходах вычитателей образуются разностные коды A_k - const1, A_k - const2,... A_k - constn, а на выходе элемента ИЛИ-НЕ 12 появляется сигнал логического нуля, открывающий элемент "запрет" 13. Там, где разностные коды меньше значений констант, на выходе "меньше" блоков сравнения 4 появляются управляющие сигналы, а где эти разностные коды больше значений констант, управляющие сигналы появляются на выходах "больше". Так как значения констант рассчитаны по формулам (1), то код разности может быть либо равен нулю, либо же попасть в промежуток между рядом расположенными константами. Если код разности равен нулю, то сигнал с выхода соответствующего блока сравнения 4 группы через элементы "запрет" 13 и ИЛИ 9 поступает на выход устройства, сигнализируя о том, что на его информационном выходе сформирован остаток r = AkmodP_i = 0, а также устанавливает регистр 1 в нулевое состояние. При этом элемент "запрет" 13 запирается сигналом, поступающим с выхода элемента ИЛИ-НЕ 12.

Если код разности не равен нулю, то в промежутке между рядом расположенными константами блок сравнения 4_j+1 выдаст сигнал "больше", а блок сравнения 4_j+1 выдаст сигнал "меньше", следовательно, сработает элемент И 5_j+1, сигнал с выхода которого включит коммутатор 6_j+1, а через элемент ИЛИ 8 и задержки 10 обеспечит запись кода A_k - constj в регистр 1. Так как записанное значение разности лежит в пределах от 1 до 2P_i-1, то если результат больше значения модуля, сигналы появляются на выходе "больше" блока сравнения 11 и на выходе "меньше" первого блока сравнения 4, откроется элемент И 5 и снова произойдет запись кода A_k - constj - const1 = a_k в регистр 1. Поэтому сигнал появится на выходе "меньше" блока сравнения 11. Этот сигнал через элемент "запрет" 13 поступит на вход записи регистра 2, обеспечивая запись кода остатка с выхода регистра 1 в регистр 2, а, поступая на управляющий выход устройства через элемент ИЛИ 9, сигнализирует об окончании процесса формирования остатка, а также обнулит содержимое регистра 1, обеспечивая тем самым запирание элемента "запрет" 13. Если A_k - constj = a_k < P_i, то запись остатка в регистр 2 произойдет после первого цикла вычитания. Код остатка остается на информационных выходах устройства до тех пор, пока на информационные входы не поступит следующее число A_k+1, от которого необходимо сформировать остаток, а на управляющий вход - сигнал запуска. При этом работа устройства осуществляется аналогично описанному выше.

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

УСТРОЙСТВО ДЛЯ СВЕРТКИ ПО ПРОИЗВОЛЬНОМУ МОДУЛЮ, содержащее группу вычитателей, группу блоков сравнения, группу элементов И, группу коммутаторов, первый и второй регистры, первый и второй элементы ИЛИ, дополнительный коммутатор и элемент задержки, причем входы первого операнда вычитателей группы подключены к соответствующим входам задания констант вычитания устройства, информационный вход устройства через дополнительный коммутатор подключен к информационному входу первого регистра, информационный выход которого подключен к входам второго операнда вычитателей группы, выходы результата вычитателей группы соединены с первыми информационными входами соответствующих блоков сравнения группы и с информационными входами соответствующих коммутаторов группы, информационные выходы которых объединены по схеме МОНТАЖНОЕ ИЛИ и соединены с информационным входом первого регистра,выход "Меньше" каждого i-го блока сравнения группы соединен с первым входом i-го элемента И группы 1 ≅ i ≅ n , где n = A_макс/2P + 1; A_макс - наибольшее контролируемое число; P - значение модуля свертки; - целая часть числа,
выход которого соединен с управляющим входом i-го коммутатора группы и с i-м входом первого элемента ИЛИ, выход которого через элемент задержки соединен с входом записи первого регистра, выход "Больше" каждого i-го блока сравнения группы, за исключением последнего, соединен с вторым входом (i+1)-го элемента И группы, выходы "Равно" блоков сравнения группы соединены с входами второго элемента ИЛИ, выход которого соединен с входом обнуления первого элемента ИЛИ, выход которого соединен с входом обнуления первого регистра и является выходом окончания работы устройства, вход начала вычисления устройства соединен с управляющим входом дополнительного коммутатора, (n+1)-м входом первого элемента ИЛИ и входом обнуления второго регистра, выход которого является выходом результата свертки устройства, отличающееся тем, что, с целью сокращения времени свертки, в устройство введены элемент ИЛИ - НЕ, элемент ЗАПРЕТ и дополнительный блок сравнения, первый информационный вход которого соединен с информационным входом второго регистра и с информационным выходом первого регистра, второй информационный вход дополнительного блока сравнения объединен с вторыми информационными входами блоков сравнения группы и подключен к входу задания константы устройства, выходы "Равно" и "Больше" дополнительного блока сравнения соединены соответственно с (n+1)-м входом второго элемента ИЛИ и вторым входом первого элемента И группы, выход "Меньше" дополнительного блока сравнения соединен с первым входом элемента ЗАПРЕТ, выход которого соединен с входом записи второго регистра и (n+2)-м входом второго элемента ИЛИ, второй вход элемента ЗАПРЕТ соединен с выходом элемента ИЛИ - НЕ, вход которого соединен с выходом первого регистра.

РИСУНКИ

Рисунок 1