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

 

Изобретение относится к вычислительной технике и предназначено для использования в цифровых вычислительных устройствах для формирования конечных полей. Цель изобретения - повышение быстродействия формирования остатка, что достигается введением первой схемы сравнения 7, второй схемы сравнения 8, блока 9 умножения по произвольному модулю, сумматора 10 по произвольному модулю, регистра 11 и триггера 12. Сущность изобретения заключается в том, что для ускорения реализации выражения g_i(ν)=jν+C_o(mod M), где , предлагается применять процедуры ускоренного получения результатов умножения и суммирования по модулю. 1 ил.

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

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

Недостатком этого устройства является низкое быстродействие процесса формирования остатка.

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

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

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

Сущность изобретения заключается в том, что для ускоренной реализации выражения a_j( ν) = j ν + C_o(modM), где ν , ν, C_o= ; j = предлагается применять процедуры ускоренного получения результатов умножения по модулю и суммирования по модулю.

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

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

Счетчик 1 конструктивно выполнен таким образом, что поступление на его первый вход (вход записи) сигнала происходит запись в его ячейки когда единицы.

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

В исходном состоянии счетчики 1, 2 и 12 обнулены, триггер 11 находится в нулевом состоянии, при котором сигналом с его выхода запрещается прохождение тактовых импульсов с выхода генератора тактовых импульсов 13 на вход счетчика 12.

Перед началом работы по шине задания кода числа задается код С_о, который в течение времени формирования воздействует на вторые входы сумматора 9 по произвольному модулю. Также задается код модуля М на шине задания кода модуля, который воздействует на первые входы первой 6 и второй 7 схем сравнения, блока 8 умножения по произвольному модулю и сумматора 9 по произвольному модулю.

Импульс с шины "Пуск" запускает устройство в работу. Этот импульс проходит через элемент ИЛИ 3 на вход записи счетчика 1, в результате чего в счетчик 1 запишется код единицы, проходя через второй элемент ИЛИ 4 на вход обнуления второго счетчика 2, подтвердит его нулевое состояние, поступая через третий элемент ИЛИ 5 на вход триггера 11, переведет его в единичное состояние. Код единицы с выхода счетчика 1 поступит на вторые входы схемы сравнения 6 и блока 8 умножения по произвольному модулю. Результат умножения кодов, записанных в счетчике 1 (единица) и втором счетчике 2 (ноль), с выхода блока 8 поступит на вход сумматора 9 по произвольному модулю, в котором происходит сложение результата умножения по модулю с кодом числа С_о.

Перевод триггера 11 в единичное состояние разрешит прохождение тактовых импульсов с выхода генератора 13 на вход счетчика 12.

Как только результат суммирования по модулю появится на выходе сумматора 9, произойдет переполнение счетчика 12, поэтому сигнал с его выхода поступит на вход формирователя 14 импульсов и возвратит в нулевое состояние триггер 11, чем запретит прохождение импульсов с генератора 13 на вход счетчика 12. Импульс с выхода формирователя 14 поступит на вход записи регистра 10, что обеспечит запись в него первого сигнала и появление этого сигнала на информационных выходах устройства. Одновременно этот импульс поступит на суммирующий вход счетчика 2, записывая в него единицу, а также через второй вход элемента ИЛИ 5 поступит на первый вход триггера 11, переводя его в единичное состояние. Теперь на информационные входы блока 8 умножения по произвольному модулю с выходов счетчиков 1 и 2 подаются коды единиц. Как только результат умножения и суммирования по модулю появится на выходе сумматора 9, с выхода формирователя 14 поступит импульс, который обеспечит запись второго сформированного сигнала в регистр 10 и поступление его на выход устройства, прибавит единицу к содержимому счетчика 2 и, поступая через элемент ИЛИ 5, переведет триггер 11 в единичное состояние.

Работа устройства в таком режиме будет продолжаться до тех пор, пока в счетчик 2 не будет записан код числа М-1. С приходом очередного импульса с выхода формирователя 14 импульсов в счетчик 2 будет записан код модуля М, за счет чего вторая схема сравнения 7 выдаст импульс совпадения, который через элемент ИЛИ 4 обнулит счетчик 2 и, поступая на суммирующий вход счетчика 1, прибавит к его содержимому единицу. Поэтому в счетчике 1 будет записан код числа два, а счетчик 2 будет обнулен. Начинается новый цикл формирования остатков, при котором в счетчике 1 будет записан код числа два, а в счетчике 2 последовательно будут меняться коды от 0 до М-1. После формирования последнего сигнала вторая схема 7 сравнения снова выдаст импульс совпадения, за счет чего счетчик 2 будет обнулен, а в счетчик 1 будет записан код числа три.

Работа устройства в таком режиме будет продолжаться до тех пор, пока в счетчик 1 не будет записан код числа М-1. Как только такой же код будет записан в счетчике 2, то с приходом импульса с формирователя 14 в счетчике 1 будет записан код числа М, поэтому произойдет совпадение также в схеме 6 сравнения, за счет чего на ее выходе появится импульс, который, поступая на управляющий выход устройства, явится сигналом конца формирования. Кроме того, этот импульс, проходя через элемент 4 на вход записи счетчика 2, запишет в нем код единицы.

Сигнал конца формирования свидетельствует о том, что закончился процесс формирования сигналов по выбранному модулю М и коду числа С_о и может быть использован для смены исходных параметров и выбора новых значений М1 и С1.

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

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

УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ ОСТАТКА ПО ПРОИЗВОЛЬНОМУ МОДУЛЮ ОТ ЧИСЛА, содержащее первый, второй, третий счетчики, три элемента ИЛИ, генератор тактовых импульсов, формирователь импульсов, причем вход пуска устройства соединен с первыми входами первого, второго и третьего элементов ИЛИ, выход первого элемента ИЛИ соединен с входом записи первого счетчика, выход второго элемента ИЛИ соединен с входом сброса второго счетчика, выход переполнения третьего счетчика соединен с входом формирователя импульсов, отличающееся тем, что, с целью повышения быстродействия устройства, в него введены триггер, две схемы сравнения, блок умножения по произвольному модулю, сумматор по произвольному модулю и триггер, причем вход задания кода модуля устройства соединен с первыми входами первой и второй схем сравнения, блока умножения по произвольному модулю и сумматора по произвольному модулю, вход задания кода числа устройства соединен с вторым входом сумматора по произвольному модулю, выход первого счетчика соединен с вторым входом блока умножения по произвольному модулю и первой схемы сравнения, выход которой соединен с вторым входом первого элемента ИЛИ и является выходом конца работы устройства, выход второго счетчика соединен с третьим входом блока умножения по произвольному модулю и вторым входом второй схемы сравнения, выход которой соединен с вторым входом второго элемента ИЛИ и счетным входом первого счетчика, выход третьего элемента ИЛИ соединен с единичным входом триггера, выход которого соединен с входом сброса третьего счетчика, выход переполнения которого соединен с входом сброса триггера, выход формирователя импульсов соединен с входом записи регистра, вторым входом третьего элемента ИЛИ и счетным входом второго счетчика, выход генератора тактовых импульсов соединен со счетным входом третьего счетчика, выход блока умножения по произвольному модулю соединен с третьим входом сумматора по произвольному модулю, выход которого соединен с информационным входом регистра, выход которого является выходом результата устройства.

РИСУНКИ

Рисунок 1