Формирователь остатка по произвольному модулю от числа

(51) 06 7/72 (2006.01) 03 7/18 (2006.01) МИНИСТЕРСТВО ЮСТИЦИИ РЕСПУБЛИКИ КАЗАХСТАН ОПИСАНИЕ ИЗОБРЕТЕНИЯ К ИННОВАЦИОННОМУ ПАТЕНТУ достигается путем последовательного вычитания первоначально из числа А увеличенного модуля Р 2 (с использованием дополнительного кода), а затем вычитания из получаемых частичных остатковзначения Р 2, уменьшаемого на каждой итерации в два раза (путем сдвига вправо) до тех пор, пока очередной остатокне станет меньше Р. Исходное число А можно рассматривать как нулевой остаток 0. Вычитание -(2-)(первоначально 0, затем ,2,), выполняется на комбинационном сумматоре, формируется остаток 1. Параллельно с этой операцией на комбинационных схемах сравнениясравнивается с Р 2- и с модулем Р. ЕслиР, тоявляется результатом - остатком по модулю Р, процесс окончен. Еслии(2-), то полученный в результате вычитания остаток 1 запишется в регистр вместо предыдущего остатка . Если ,2-, остатокостается в регистре без изменения.(72) Айтхожаева Евгения Жамалхановна Тынымбаев Сахыбай Тынымбаевич(73) Республиканское государственное предприятие на праве хозяйственного ведения Казахский национальный технический университет им. К.И. Сатпаева Министерства образования и науки Республики Казахстан(54) ФОРМИРОВАТЕЛЬ ОСТАТКА ПО ПРОИЗВОЛЬНОМУ МОДУЛЮ ОТ ЧИСЛА(57) Изобретение относится к вычислительной технике и может быть использовано в цифровых вычислительных устройствах, а также в устройствах для формирования элементов конечных полей. Технической задачей изобретения является уменьшение аппаратных затрат формирователя остатка по произвольному модулю от числа и повышение быстродействия формирователя. Цель Изобретение относится к вычислительной технике и может быть использовано в цифровых вычислительных устройствах, а также в устройствах для формирования элементов конечных полей. Известно устройство формирования остатка по произвольному модулю от числа, содержащее генератор тактовых импульсов (ГТИ), триггер,элемент задержки, два элемента И, элемент ИЛИ,два регистра, блок формирования частичных остатков (содержит элемент И, два сумматора, ключ и элемент НЕ), накапливающий сумматор по модулю (содержит сумматор, блок формирования частичных остатков и регистр), мультиплексор,счетчик Патент РФ 2023546, кл. Н 03 М 7/18,15.11.1994. Алгоритм получения остатка по модулю, реализуемый в устройстве, основан на представлении двоичного числа А в виде следующего выражения 212120, гдеравно 1 или 0. Для вычисления остатка от числа А по модулю последовательно вычисляются и суммируются частичные остатки по модулю Р от каждого из слагаемых а 2 (0 ,), которые в сумме дают остаток от числа А по модулю. Но в формировании этой суммы не должны участвовать остатки от слагаемых, в которых 0. Вычисляются частичные остатки от чисел 2 и по мере вычисления остатки от 2 суммируются, только если для них коэффициент а 1. После суммирования очередного частичного остатка от полученной суммы частичных остатков (ч.о) также находится остаток по модулю Р. Описание работы данного устройства приведено ниже. Сигналом Пуск исходное число А записывается в первый регистр, во второй регистр записывается 201,в счетчик записывается единица,накапливающий сумматор по модулю устанавливается в нуль и триггер устанавливается в единичное состояние, которое используется для разрешения прохождения тактовых импульсов от ГТИ через первую схему И для тактирования работы устройства. Очередной тактовый импульс разрешает вычисление частичного остатка по модулю Р от очередного числа 2 (02,) в блоке формирования частичных остатков, на первые входы которого поступает 2 с выхода второго регистра, на вторые входы поступает модуль Р(реализуется операция 2-Р). Значение счетчика увеличивается на единицу каждым тактовым импульсом. Выходы счетчика подаются на адресные входы мультиплексора определяя, какой по счету коэффициент а числа А появится на выходе мультиплексора (а, или а 1,или, или а). Коэффициент а проходит через вторую схему И с задержкой, так как на второй вход схемы И тактовый сигнал (вначале сигнал Пуск через схему ИЛИ) поступает через элемент задержки. Задержка необходима, чтобы успел вычисляться и записаться во второй регистр очередной остаток от 2 в блоке формирования частичных остатков. Если а 1, то разрешается суммирование в накапливающем сумматоре по модулю вычисленного частичного остатка по модулю Р от очередного числа 2 из второго 2 регистра, в противном случае (а 0) суммирование не происходит. На вторые входы накапливающего сумматора по модулю поступает модуль Р,реализуется операция (ч.о-Р). После определения последнего частичного остатка (от 2) счетчик сбрасывается в 0, формируя сигнал переполнения,который устанавливает триггер в нулевое состояние,тем самым прекращая работу устройства. Недостатком данного устройства является низкая надежность, так как требуются большие аппаратные затраты, не приводящие к существенному увеличению быстродействия. Получение остатка по модулю от исходного числа А реализуется в виде операции вычитания в блоке формирования частичных остатков для каждого 2 (независимо от значения а и соотношения 2 и Р) и накапливающем сумматоре (в который входит еще один блок формирования частичных остатков) для каждой ч.(независимо от соотношения ч.о и Р) Если получаются отрицательные остатки, то выполняется их восстановление путем суммирования с модулем Р, на что требуется дополнительное время. В данном устройстве для формирования остатка по произвольному модулю от числа А необходимотактовых импульсов, где- разрядность возможного наибольшего числа А, приводимого по модулю (независимо от значения текущего числа А,приводимого по модулю). Технической задачей изобретения является уменьшение аппаратных затрат формирователя остатка по произвольному модулю от числа и повышение быстродействия формирователя. Техническая задача решается за счет замены блока формирования частичных остатков (элемент И, два сумматора, ключ и элемент НЕ) и накапливающего сумматора (сумматор, блок формирования частичных остатков и регистр) комбинационным сумматором для выполнения операции вычитания(с использованием дополнительного кода) с целью получения остатка,и использованием первого регистра как для хранения исходного числа А (первоначально), так и для получаемых частичных остатков,использованием второго регистра для хранения модуля Р, введением в формирователь регистра сдвига вправо для увеличенного модуля Р 2,первой схемы сравнения увеличенного модуля Р 2 с очередным остатком , второй схемы сравнения модуля Р с очередным остатком , двух схем И и схемы ИЛИ для разрешения занесения в первый регистр кода исходного числа А или частичных остатков, схемы И для разрешения занесения во второй регистр кода модуля Р и в регистр сдвига кода увеличенного модуля Р 2, схемы И для разрешения выдачи полученного остатка из первого регистра на выход. Цель достигается путем последовательного вычитания первоначально из числа А увеличенного модуля Р 2 (с использованием дополнительного кода), а затем вычитания из получаемых частичных остатковзначения Р 2, уменьшаемого в два раза на каждой итерации (путем сдвига вправо) до тех пор, пока очередной остатокне станет меньше Р. Остатокот деления исходного числа А на произвольный модуль Р можно получить путем последовательного вычитания из А, а затем из получающихся остатковмодуля Р --)-)-). Процесс вычитания продолжается до тех пор, пока очередной остаток . Для ускорения получения остатка последовательное вычитание модуля Р можно заменить вычитанием(Р), если А(Р). Если А(Р), то (Р) надо уменьшить. Выборзависит от диапазона входных чисел А. В общем случае можно считать, что разрядность возможного наибольшего числа А равна , разрядность Р равна . В этом случае необходимо увеличить Р таким образом, чтобы разрядность увеличенного Р была равна . Если наложить ограничение, чтократно двум, то Р необходимо умножить на 2-. Умножение на(реализация умножения 2-) заменяется записью Р в старшие разряды- разрядного регистра сдвига, с сохранением нулей в младших разрядах. Уменьшать 2- можно путем деления на два. В этом случае всегда очередное значение 2. Уменьшение увеличенного модуля 2- до 21 и далее достигается сдвигом вправо на один разряд. В дальнейшем разность - будет обозначаться как. Исходное число А можно рассматривать как нулевой остаток 0. На комбинационном сумматоре выполняется вычитание -(2-), формируется остаток 1 (первоначально 0, затем 1,2,). Параллельно с этой операцией на комбинационных схемах сравнениясравнивается с Р 2- и с модулем Р. ЕслиР, тоявляется результатом остатком по модулю Р, процесс окончен. Еслиибольше Р 2-, то полученный в результате вычитания остаток 1 запишется в регистр вместо предыдущего остатка . Если ,меньше Р 2-, остатокостается в регистре без изменения. Уменьшение в два раза значения Р 2 выполняется путем сдвига вправо на один разряд каждый раз после выполнения очередного вычитания на комбинационном сумматоре независимо от результата сравненияс Р 2-. Процесс продолжается до тех пор, пока очередной остатокне станет меньше Р ( Р). На чертеже представлена схема формирователя остатка по произвольному модулю от числа. Формирователь остатка по произвольному модулю от числа содержит регистры 1 и 2, регистр сдвига 3, комбинационный сумматор 4, схемы сравнения 5 и 6, генератор тактовых импульсов(ГТИ) 7, триггер 8, схемы И 9, И 10, И 11, И 12, И 13, схему ИЛИ 14, элемент задержки 15. Вход 16 служит для подачи сигнала начала вычисления остатка (Пуск), вход 17 служит для подачи двоичного кода исходного числа А, вход 18 служит для подачи двоичного кода модуля Р, выход 19 является выходом результата формирователя остатка. Формирователь остатка по произвольному модулю от числа работает следующим образом. В исходном состоянии триггер 8, регистр 1,регистр 2, регистр сдвига 3 обнулены. Перед началом работы на вход 17 формирователя подается код числа А, от которого необходимо сформировать остаток, а на вход 18 подается код модуля Р, по которому формируется остаток. Начало работы формирователя определяется моментом подачи на его вход 16 единичного сигнала Пуск. Этот сигнал разрешает прохождение кода исходного числа А с входа 17 через схему И 11 на схему ИЛИ 14 и далее в регистр 1, разрешает прохождение кода модуля Р с входа 18 через схему И 12 в регистр 2 и в старшие разряды регистра сдвига 3. Этот же сигнал Пуск с задержкой устанавливает триггер 8 в единичное состояние через элемент задержки 15, единичный потенциал с выхода триггера 8 поступает на схему И 9, разрешая в дальнейшем прохождение тактовых импульсов с выхода ГТИ 7 через схему И 9 для тактирования работы формирователя. Код числа А из регистра 1 поступает на вторые входы схемы сравнения 6, на первые входы схемы сравнения 6 поступает код модуля Р из регистра 2(при сравнении выравнивание идет по младшим разрядам), определяется АР или нет. Если АР(число А уже и есть остаток), то на выходе схемы сравнения 6 вырабатывается сигнал, который через схему И 13 разрешает выдачу числа А с выхода регистра 1 на выход результата формирователя 19 и обнуляет триггер 8 (прохождение тактовых сигналов запрещается), формирование остатка закончено. В противном случае процесс нахождения остатка продолжается. Одновременно число А из регистра 1 поступает на первые входы комбинационного сумматора 4, на вторые входы которого поступает инверсный код увеличенного модуля Р 2 с инверсных выходов регистра сдвига 3, на третий вход младшего разряда комбинационного сумматора поступает единица. Таким образом реализуется вычитание с использованием дополнительного кода,т.е. формирование остатка 1-(2). Число А из регистра 1 поступает также на вторые входы схемы сравнения 5, на первые входы схемы сравнения 5 поступает увеличенный модуль Р 2 из регистра сдвига 3, определяется А(Р 2), или нет. Если А меньше Р 2, то на выходе схемы сравнения 5 сигнал не вырабатывается и полученный остаток 1 не используется. В противном случае (А(Р 2 на выходе схемы сравнения 5 вырабатывается сигнал, который разрешает через схему И 10, с приходом тактового импульса с выхода схемы И 9 от ГТИ, передачу полученного остатка 1 с выходов комбинационного сумматора 4 на схему ИЛИ 14, с выхода ИЛИ 14 остаток подается на входы записи регистра 1, т.е. полученный остаток 1 записывается в регистр 1(вместо исходного числа А). Этот же тактовый импульс с выхода И 9 поступает на сдвиговый вход регистра сдвига 3, выполняя сдвиг увеличенного модуля (Р 2) в регистре сдвига 3 вправо на один разряд, уменьшая его в два раза, получается (Р 2-1). Далее работа формирователя осуществляется аналогично. Перед приходом каждого тактового импульса число из регистра 1 поступает на вторые входы схемы сравнения 6, на первые входы схемы сравнения 6 поступает модуль Р из регистра 2,определяетсяили нет. Если , то схема сравнения 6 вырабатывает сигнал, который через схему И 13 разрешает выдачу числас выхода регистра 1 на выход результата формирователя 19 и обнуляет триггер 8, формирование остатка закончено. В противном случае процесс нахождения остатка продолжается. Одновременно числоиз регистра 1 поступает на первые входы комбинационного сумматора 4, на вторые входы которого поступает инверсный код Р 2- с инверсных выходов регистра сдвига 3, на третий вход младшего разряда комбинационного сумматора 4 поступает единица, реализуется вычитание с использованием дополнительного кода,т.е. формирование остатка 1 -(2-).из регистра 1 поступает также на вторые входы схемы сравнения 5, на первые входы схемы сравнения 5 поступает Р 2- с выхода регистра сдвига 3,определяется(Р 2-), или нет. Еслименьше Р 2-, то на выходе схемы сравнения 5 сигнал не вырабатывается и полученный остаток 1 не используется. В противном случае Р 2- на выходе схемы сравнения 5 вырабатывается сигнал, который разрешает через схему И 10 с приходом следующего тактового импульса с выхода И 9 передачу полученного остатка 1 с выходов комбинационного сумматора 4 на схему ИЛИ 14, с выхода ИЛИ 14 остаток подается на входы записи регистра 1, т.е. полученный остаток 1 записывается в регистр 1 (вместо предыдущего остатка ). Этот же тактовый импульс с выхода И 9 поступает на сдвиговый вход регистра сдвига 3,выполняя сдвиг значения Р 2- в регистре сдвига 3 вправо на один разряд, уменьшая его в два раза. Так как по каждому тактовому импульсу разрешается запись в регистр 1 очередного остатка 1 с выходов комбинационного сумматора 4 вместо предыдущегопри наличии сигнала со схемы сравнения 5 и осуществляется сдвиг значения 2- в регистре сдвига 3 вправо на один разряд, то время задержки сигнала Пуск на элементе задержки 15 для установки триггера 8 в единичное состояние для разрешения прохождения тактовых импульсов и период тактовых импульсов должен превышать сумму времени распространения сигнала через элементы И 10, ИЛИ 14, времени записи в регистр 1,времени вычитания на комбинационном сумматоре 4. Время сдвига значения 2- в регистре сдвига 3 не учитывается, так как сдвиг выполняется одновременно с распространением сигнала через элементы И 10, ИЛИ 14, и записью в регистр 1. Время срабатывания схем сравнения 5 и 6 также не учитывается, так как сравнение на них выполняется одновременно с операцией вычитания на комбинационном сумматоре 4. Рассмотрим работу формирователя остатка по произвольному модулю от числа на примерах,считая, что разрядностьвозможного наибольшего числа А равна 7. В этом случае разрядность регистра 1 и регистра сдвига 3 равна 7. Пример 1. 7, 106101010102, Р 131011012(4), 7-43, Р 2 Р 2311010002. По сигналу Пуск в регистр 1 записывается двоичный код А (число 1101010), в регистр 2 записывается двоичный код модуля Р (число 1101),в регистр сдвига 3 записывается Р 23 (число 1101000). Этот же сигнал Пуск с задержкой, так как проходит через элемент задержки 15, установит триггер 8 в единичное состояние. На схеме сравнения 6 сравниваются поразрядно числа, находящиеся в регистре 1 и регистре 2 1101010 и 1101. При сравнении выравнивание идет по младшим разрядам, т.е. сравниваются числа 1101010 и 0001101. Так как 11010100001101 (АР),то процесс продолжается. Параллельно работает схема сравнения 5, на которой поразрядно сравниваются числа,находящиеся в регистре 1 (А 1101010) и регистре сдвига 3 (Р 231101000). Так как 1101010 1101000) на выходе схемы сравнения 5 вырабатывается разрешающий сигнал А(Р 23). Одновременно на комбинационном сумматоре 4 выполняется вычитание 1-(23).1101010-1101000110101000101111 младшего разряда 0000010. Через схему И 9 первый тактовый импульс поступает на третьи входы схемы И 10, на первые входы схемы И 10 поступает с выхода комбинационного сумматора 4 вычисленный остаток 1, на вторые входы поступает разрешающий сигнал со схемы сравнения 5, остаток 1 проходит через схему И 10 и через схему ИЛИ 14 поступает на входы записи регистра 1. Значение регистра 1 изменится и станет равным 0000010. Этот же тактовый импульс сдвигает вправо на один разряд содержимое регистра сдвига 3 Р 23 уменьшается в два раза и становится равным Р 22 0110100. Процесс повторяется. На схеме сравнения 6 сравниваются числа, находящиеся в регистре 1 и регистре 2 0000010 и 1101. Так как 0000001000001101, то схема сравнения 6 вырабатывает сигнал окончания процесса. Этот сигнал сбрасывает триггер 8 в нулевое состояние(запрет на разрешение прохождения тактовых импульсов от ГТИ) и поступает на первые входы(разрешающие) схемы И 13, на вторые входы схемы И 13 поступает содержимое регистра 1 (00000010). Вычисленный остаток выдается на выход результата 19. Формирование остатка закончено, остаток равен 000000102210. Остаток вычислен верно, так как 106/13 дает в остатке 2. Для вычисления остатка потребовался один тактовый импульс. Пример 2. 7, А 2510110012, Р 131011012(4), 7-43, 2 Р 2311010002. По сигналу Пуск в регистр 1 записывается двоичный код А (число 0011001), в регистр 2 записывается двоичный код модуля Р (число 1101), 30983 в регистр сдвига 3 записывается Р 23 (число 1101000). Этот же сигнал Пуск с задержкой, так как проходит через элемент задержки 15, установит триггер 8 в единичное состояние. На схеме сравнения 6 сравниваются поразрядно числа, находящиеся в регистре 1 и регистре 2 0011001 и 1101. При сравнении выравнивание идет по младшим разрядам, т.е. сравниваются числа 0011001 и 0001101. Так как 00110010001101 (АР),то процесс продолжается. Параллельно работает схема сравнения 5, на которой поразрядно сравниваются числа,находящиеся в регистре 1 (А 0011001) и регистре сдвига 3 (Р 231101000). Так как 00110011101000,разрешающий сигнал А(Р 23) на выходе схемы сравнения 5 не вырабатывается. Одновременно на комбинационном сумматоре 4 выполняется вычитание 1-(23). Но полученный остаток 1 не будет использован. Через схему И 9 первый тактовый импульс поступает на третьи входы схемы И 10, на первые входы схемы И 10 поступает с выходов комбинационного сумматора 4 вычисленный остаток 1, но так как разрешающего сигнала на вторых входах схемы И 10 с выхода схемы сравнения 5 нет, остаток 1 не проходит через схему И 10 и не запишется в регистр 1. Значение регистра 1 (0011001) не изменится. Этот же тактовый импульс сдвигает вправо на один разряд содержимое регистра сдвига 3 Р 23 уменьшается в два раза и становится равным Р 220110100. Процесс повторяется. На схеме сравнения 6 сравниваются поразрядно числа, находящиеся в регистре 1 и регистре 2 0011001 и 1101. При сравнении выравнивание идет по младшим разрядам, т.е. сравниваются числа 0011001 и 0001101. Так как 0011001 0001101 (АР), то схема сравнения 6 не вырабатывает сигнал окончания и процесс продолжается. Параллельно работает схема сравнения 5, на которой поразрядно сравниваются числа,находящиеся в регистре 1 (0011001) и регистре сдвига 3 (0110100). Так как 0011000110100,разрешающий сигнал А(Р 23) на выходе схемы сравнения 5 не вырабатывается. Одновременно на комбинационном сумматоре 4 выполняется вычитание 2-(22). Но полученный остаток 2 не будет использован. Через схему И 9 второй тактовый импульс поступает на третьи входы схемы И 10, на первые входы схемы И 10 поступает с выходов комбинационного сумматора 4 вычисленный остаток 2, но так как разрешающего сигнала на вторых входах схемы И 10 с выхода схемы сравнения 5 нет, остаток 2 не проходит через схему И 10 и не запишется в регистр 1. Значение регистра 1 (0011001) не изменится. Этот же тактовый импульс сдвигает вправо на один разряд содержимое регистра сдвига 3 Р 22 уменьшается в два раза и становится равным Р 210011010. Процесс повторяется. На схеме сравнения 6 сравниваются поразрядно числа, находящиеся в регистре 1 и регистре 2 0011001 и 1101. При сравнении выравнивание идет по младшим разрядам, т.е. сравниваются числа 0011001 и 0001101. Так как 00110010001101, то схема сравнения 6 не вырабатывает сигнал окончания и процесс продолжается. Параллельно работает схема сравнения 5, на которой поразрядно сравниваются числа,находящиеся в регистре 1 (0011001) и регистре сдвига 3 (0011010). Так как 00110010011010,разрешающий сигнал на выходе схемы сравнения 5 не вырабатывается. Одновременно на комбинационном сумматоре выполняется вычитание 3-(21). Но полученный остаток 3 не будет использован. Через схему И 9 третий тактовый импульс поступает на третьи входы схемы И 10, на первые входы схемы И 10 поступает с выходов комбинационного сумматора 4 вычисленный остаток 3, но так как разрешающего сигнала на вторых входах схемы И 10 с выхода схемы сравнения 5 нет, остаток 3 не проходит через схему И 10 и не запишется в регистр 1. Значение регистра 1 (0011001) не изменится. Этот же тактовый импульс сдвигает вправо на один разряд содержимое регистра сдвига 3 Р 21 уменьшается в два раза и становится равным Р 200001101. Процесс повторяется. На схеме сравнения 6 сравниваются поразрядно числа, находящиеся в регистре 1 и регистре 2 0011001 и 1101. При сравнении выравнивание идет по младшим разрядам, т.е. сравниваются числа 0011001 и 0001101. Так как 00110010001101, то схема сравнения 6 не вырабатывает сигнал окончания и процесс продолжается. Параллельно работает схема сравнения 5, на которой поразрядно сравниваются числа,находящиеся в регистре 1 (0011001) и регистре сдвига 3 (0001101). Так как 0011001 0001101, на выходе схемы сравнения 5 вырабатывается разрешающий сигнал. Одновременно на комбинационном сумматоре выполняется вычитание 4-(20). 40011001-0001101001100111100101 младшего разряда 0001100. Через схему И 9 четвертый тактовый импульс поступает на третьи входы схемы И 10, на первые входы схемы И 10 поступает с выходов комбинационного сумматора 4 вычисленный остаток 4, на вторые входы схемы И 10 поступает разрешающий сигнал с выхода схемы сравнения 5,остаток 4 проходит через схему И 10 и через схему ИЛИ 14 поступает на входы записи регистра 1. Значение регистра 1 изменится и станет равным 0001100. Этот же тактовый импульс сдвигает вправо на один разряд содержимое регистра сдвига 3 Р 20 уменьшается в два раза и становится равным Р 2-10000110. Процесс повторяется. На схеме сравнения 6 сравниваются числа, находящиеся в регистре 1 и регистре 2 0001100 и 1101. Так как 00011000001101 (4), то схема сравнения 6 вырабатывает сигнал окончания процесса. Этот сигнал сбрасывает триггер 8 в нулевое состояние 5(запрет на разрешение прохождения тактовых импульсов от ГТИ) и поступает на первые входы(разрешающие) схемы И 13, на вторые входы схемы И 13 поступает содержимое регистра 1 (0001100). Вычисленный остаток выдается на выход результата 19. Формирование остатка закончено, остаток равен 000110021210. Остаток вычислен верно, так как 25/13 дает в остатке 12. Для вычисления остатка потребовалось четыре тактовых импульса. Из приведенных примеров видно, что время формирования остатка зависит от соотношения значений А и Р. По быстродействию наилучший вариант формирования остатка (в случае АР) не потребует ни одного тактового импульса,наихудший вариант потребует (-1) тактовых импульсов. Таким образом, количество тактовых импульсов в среднем для вычисления остатка равно(-1)/2. В прототипе для вычисления остатка необходимо всегда использовать- тактовых импульсов. ФОРМУЛА ИЗОБРЕТЕНИЯ Формирователь остатка по произвольному модулю от числа, состоящий из генератора тактовых импульсов ГТИ, триггера, двух регистров, схемы И,элемента задержки, причем выход ГТИ соединен с первым входом первой схемы И, второй вход которой соединен с единичным выходом триггера,отличающийся тем, что дополнительно введены комбинационный сумматор, регистр сдвига вправо,схема сравнения модуля с очередным остатком,схема сравнения увеличенного модуля с очередным остатком, четыре схемы И и схема ИЛИ, где вход установки в единичное состояние триггера соединен с выходом элемента задержки, вход которого соединен с входом сигнала начала вычисления остатка, первые входы второй схемы И соединены с выходами комбинационного сумматора, вторые входы второй схемы И соединены с выходом первой схемы сравнения, третьи входы второй схемы И соединены с выходом первой схемы И, выходы второй схемы И соединены с первыми входами схемы ИЛИ, вторые входы схемы ИЛИ соединены с выходами третьей схемы И, первые входы которой соединены с входом сигнала начала вычисления остатка, вторые входы которой соединены с входом кода числа А, выходы схемы ИЛИ соединены с входами записи первого регистра, выходы которого соединены с первыми входами комбинационного сумматора, вторыми входами первой схемы сравнения, вторыми входами второй схемы сравнения, вторыми входами пятой схемы И,вторые входы комбинационного сумматора соединены с инверсными выходами регистра сдвига,третий вход младшего разряда комбинационного сумматора соединен с постоянным единичным сигналом, первые входы первой схемы сравнения соединены с выходами регистра сдвига, вход сдвига которого соединен с выходом первой схемы И, входы записи старших разрядов регистра сдвига соединены с выходами четвертой схемы И, первые входы которой соединены с входом сигнала начала вычисления остатка, вторые входы которой соединены с входом кода модуля Р, выходы которой соединены с входами записи второго регистра, выходы которого соединены с первыми входами второй схемы сравнения, выход которой соединен с входом сброса триггера в нулевое состояние и с первыми входами пятой схемы И, вторые входы которой соединены с выходами первого регистра, выходы пятой схемы И соединены с выходом результата формирователя.