В пт6

Союз СоветскихСоциалистическихРеспублик Зависимое от авт. свидетельстваЗаявлено 15.И 1.1970 ( 1468950/18-24)с присоединением заявкиПриоритетОпубликовано 25.И 1.1973. Бюллетень М. Кл. С 061 452С 061 11/08 Государственный комитет Совета о 1 иннстров СССР во делам изобретений и открытий.Х 11.197 та опубликования описан ВПТУГ. Г, Иванов г РО: ;:р тд и нстнтут математики Сибирского отделения АН СССР Авторизобретени явитель СТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ВЫЧЕТОВ ЧИСЕЛ ПО МОДУЛЮИзобретвние относится к области вычислительной техники.Предлагаемое устройство может быть использовано для перевода двоично-кодированных чисел из систем счисления с основаниями 2" в систему остаточных классов и для свертки чисел в устройствах контроля по модулю.Известно устройство для вычисления вычетов чисел по модулю, содержащее регистр ис. ходного числа, блок вычисления частичных вычетов, соединенный с сумматором, в основу которого положен следующий метод.Пусть исходное двоичное число записано в виде: А = а 2 П + а,2 - 1+ + а,2 + ао 2, (1)15где а=0,1,=0,1,2 т.Необходимо вычислить наименьший положительный вычет А по модулю р, назовем его 20А. Рассматривается числоА = а К + а,К, 1 + + а,К, + аоК, (2)где 1=2(гпос 1 р) - наименьшие положительные вычеты степеней основания 2 по модулю р.Из свойсвв вычетов следует, что А и А принадлежат к одному классу вычетов А, Будемсчитать, что Й характеризует вес-го разряда,Известно, что ряд вычетов Й обнаруживает 30 периодичность. Напр 1 имер, последовательность возрастающих степеней 2, 2, 2, 2,по модулю р=5, дает ряд вычетов 1, 2, 4, 3, 1, 2, . Длина периода этого ряда 1=4. Вообще для простого модуля, для которого основание степенной последовательности является первообразным корнем, длина периода 1=р - 1, Если в качестве модуля берется составное число, то ряд вычетов может иметь начальный отрезок, не включенный в период, например для р=12 ряд А имеет вид:1, 2, 4, 8, 4, 8, Длина периода 1=2, длина начального отрезка 1=2. Таким образом, исходное число разбивается на период% в зависимости от модуля р. На основании изложенного А определяется следующим способом.Разряды исходного числа разбиваются на групп, в каждую из которых входят все разряды с одинаковым весом й;. Количество значащих разрядов каждой группы подсчитывается счетчиком по модулю р. Шифратор, стоящий на выходе счетчика, выдает наименьший положительный вычет:Л,: Ж,К,(то 1 р),е С=1,2 1;У - число значащих разрядов в с-йпе;й, в в разрядов, объединенныхгруппу.391561 Назовем В, частичным вычетом, Количествочастичных вычетов равно 1. Эти вычеты подаются на сумматор по модулю р. Сумма всехчастичных вычетов, которая, получается на выходе сумматора, есть искомый вычет А(если число содержит начальный отрезок, то онбез изменения включается .в сумму, поскольку не может быть больше р).Однако этот метод требует большого количества оборудования при одновременном суммировании частичных вычетов (например, напирамидальном сумматоре) пли много времени при последовательном суммировании частичных вычетов.Цель изобретения - уменьшение расходаоборудования при одновременном суммировании частичных вычетов с сохранением примерно того же быстродействия или уменьшениезатрат времени при последовательном суммировании частичных вычетов. Эффективностьописываемого устройства повышается при увеличении периода 1. Предлагаемый метод предназначен для систем счисления с основаниями2 пМетод непригоден для построения устройства определения вычетов по следующим модулям:1. р=2 с с= О, 1, 2, 3,2. р=2 - 2 И=О, 1, 2, 3, ; 1=3, 4, 5 ;гУ 1 - 3.3, Если простое р не имеет 2 в числе своихпервообразных корней.4. Если в разложении составного р на простые мнокители есть хоть один, для которого2 не является первообразным корнем.Для достижения поставленной цели используется следующее свойство рядов вычетов.В периоде ряда вычетов й; по любому модулю(за исключением перечисленных в пунктах 1 -4) четное число членов, причем в нем существует - пар, сумма членов которых равна р,2т, е. сравнима с нулем по модулю р. Назовемтакие пары дополнительными, а их члены -дополняющими вычетами, причем, если перенумеровать члены периода числами от 1 до 1,то дополнительные пары составят члены, стоящие под номерами и и и+1 и ( - ) .Таким образом, если в двоичном числеА =я 2 мз+а,з 2 оа - г+ + а,2+а,2 з(3) 1п=1 23 3 еа=1, если единицы содержатся в группеи, а=О, если группа и состоит из нулей;60 Лг - число единиц в ненулевой группе,Й - вес разрядов в группе и,й, +- вес разрядов в группе а+ - .2По аналогии с предыдущим будем называть65 Втакже частичным вычетом, Поскольку коа;=1 и а;=1, где 1 и у - номера разрядов, в которых вычеты чисел 2 и 21 составляют дополнительную пару, то можно присвоить а, и а, значения О, так как 2+21 =О (гпод р). В сумме (формула 2) исчезнут два слагаемых аА и а;й,. Назовем эту операцию исключением.Пусть исходное число имеет длину 51+, где 5 - число периодов (в общем случае последний,5-й период может быть неполньгм). В каждом периоде перенумеруем разряды, начиная с младшего, числами от 1 до 1. Если в исходном числе выполнить операцию исключения над всеми дополнительными парами, то в преооразовапном числе не останется ни одной дополнительной пары единичных разрядов. Если хотя бы один разряд с весом йв преобразо 5 ванном числе равен 1, то можно утверждать,что все разряды, имеющие вес р - Аравны О, Преобразованное число может содержать мак 1симум 1+5 - единичных разрядов и разнообгразие весов в нем уменьшается вдвое по сравнению с исходным.Для получения преобразованного числакаждык гр-й разряд п=1, 2, , - ) 1-го пе" г )риода должен быть поэтапно объединен в па 1ру с(п+ -м разрядом д.го периода (=1,212, , 5; д=1, 2 5) и каждый и-й разряд1год-го периода - с(Й+ - 11-м разрядом 1-го пег(риода. Процесс объединения всех разрядов периодов 1 и д в дополнительные пары назовем объединением периодови д.После исключения дополнительных пар разряды полученного числа, имеющие один и тот же вес, группируются в 1 групп. Пусть в группу и группируются разряды с весом Аде, а в группу и+ -- с весом й, + -- р - И,. По 2 2скольку в полученном после исключения числа нет ни одной дополнительной пары вдиничных разрядов, одна из групп п,п+ в ) обязательно должна состоять из нулей. Разряды З 5 этих трувп можно попарно объединить логичеокими элементами ИЛИ и подать на счетчик по модулю р для подсчета числа значащих разрядов, Если максимальное число раз,рядов в группе не более й(р, то отпадает 4 О необходимость в счегчике по модулю р (нужно, чтобы счетчик мог сосчитать не менее Й единиц). Шифратор, стоящий на выходе очетчика, в зависимости от числа разрядов и от того, в какой из двух групп содержатся еди ницы, выдает код, соответствующий наименьшему положительному вычету В: В: Жай+ а 4+, (гпод р),при этомй+ й г - 0(гпос 1 р),личество частичных вычетов в данном случаепо сравнению с известным методом вдвоеменьше, здесь требуется уже не 1, а - счетгчиков для подсчета числа единиц в группах. 5С выходов шифраторов на сумматор поступает1не 1, а - слагаемых.2Для достижения постановленной цели в известное устройство введен блок иоключениядополнительных пар, входы которого соединены с выходами регистра исходного числа, авыходы - со входами блока частичных вычетов. При использовании сумматора, воспринимающего одновременно все частичные вычеты,уменьшение количества слагаемых вдвое приводит к сокращению оборудования сумматорав два раза.На фиг. 1 изображена функциональная схема устройства для определения вычетов чиселпо модулю; на фиг. 2 - логическая схема блока исключения дополнительных пар устройствадля определения вычетов 12-разрядного двоичного числа по модулю 5.На функциональной схеме устройства исходное число хранится в регистре 1 исходногочисла, Регистр исходного числа разбит наподрегистры, соответственно периодам рядавычетов возрастающих степеней двойки. Буквой 1 обозначен подрегистр, хранящий начальный отрезок числа. К выходу регистра 1 подключен блок исключения дополнительных пар2. Преобразованное число поступает на входблока вычисления частичных вычетов 8. В этомблоке разряды с дополнительными весами попарно группируются схемами 4. Собирательные схемы б сигнализируют о наличии хотя быодной единицы в одной из групп разрядов сдополнительными весами.40Счетчики б суммируют поступающие со схем4 единицы. Шифраторы 7 в зависимости отчисел, поступающих со счетчиков б, и от наличия или отсутствия единицы на выходе собирательных схем 5 выдают код в соответствии с формулой (3). Сумматор 8 по модулю рвычисляет искомый вычет А.Предлатаемое устройство работает следуюшим образом,Исходное число с регистра 1 поступает вблок исключения дополнительных пар 2. Каждое однолинейное функциональное соединениерегистра 1 с блоком 2 (фиг. 1) условно представляет 1 одинарных шин. Блок исключениядополнительных пар 2 на каждом этапе объединяет периоды (1 - 5) и производит операцию исключения. Причем, на каждом последующем этапе в качестве исходной информации используется число, .полученное на предыдущем этапе. 60Преобразованное число с блока 2 поступаетв блок вычисления частичных вычетов 8. Каждое функциональное соединение блока 2 с блоком 8 на фиг. 1 условно представляет 5 одинарных шин, и по ним передаются разряды с 66 одинаковым весом. На входе блока 8 имеются - схем группировки 4. В и схему группировки 24,поступают две группы по 5 шин каждая.Одна из этих групп передает информацию от всех и - х разрядов периодов, а вторая - от всех (и+ - ) - х. Схемы 4 осуществляют по.2парную группировку разрядов с дополнительными весами, т. е. каждая пара передается через логический элемент ИЛИ, Выходы схем 4 содержат по 5 шин. Счетчики б подсчитывают число единиц, поступающих со схем 4.Код, соответствующий этому числу, поступает на шифраторы 7.Схемы сборки б, подключенные к одной из групп шин, входящих в схемы 4, представляют собой элементы ИЛИ на 5 входов. Наличие на выходе сборки 5 единицы свидетельствует о том, что в той группе, к которой она подключена, есть хотя бы одна единица, следовательно по другой группе шин идут нули.Это дает шифратору 7 информацию о том, какой из двух весов должны иметь разряды числа. Шифратор определяет наименьший положительный вычет, соответствующий сумме, поступающей со счетчика б, с учетом веса. Функционирование шифраторов определяется формулой (3). Начальный отрезок 1 с регистра 1 и - частичных вычетов с шифраторов 7гпоступают на сумматор 8 по модулю р, с выхода которого снимается искомый вычет А,Блок исключения дополнительных пар устройства для определения вычета 12-разрядного двоичного числа по модулю 5 (фиг, 2) содержит регистры 9 и 10 и комбинационные схемы, вьгполняющие преобразования при передаче числа между регистрами, Исходное число хранится в регистре 9. На чертеже регистры условно разбиты на разряды, правые выходы которых соответствуют прямым кодам, а левые - инверсным.Период ряда вычетов возрастающих степеней 2 по модулю 5 имеет вид: 1, 2, 4, 3. Длина периода 1=4, начальный отрезок отсутствует. Исходное 12-разрядное число разбивается на три периода, по четыре разряда в каждом.В начале преобразования регистр 10 устанавливается в О импульсом То,. На первом этапе преобразования тактовый импульс Т подается на схемы И 11, 12, 13, каждая из которых состоит из четырех элементов И на два входа, Информация с инверсных выходов первого периода через схему 12 и схему 14, представляющую собой (так же как 15 и 1 б) четыре двухвходовых элемента ИЛИ, поступает в блок 17. С инверсных выходов разрядов второго периода через схемы И и 1 б - в блок 18 и с инверсных выходов разрядов третьего периода через схемы 11 и 1 б - в блок 19. Каждый из блоков 17, 18 и 19 состоит из четырех элементов И. На один из входовкаждого элемента И подается сигнал с прямого выхода соответствующего разряда регистра 9, а на второй вход через соответствующие логические схемы поступает сигнал с инверсного выхода разряда с дополнительным весом. Схемы 11, 12, И, 14, 15, 1 б выполняют операцию объединекия, а блоки 17, 18 19 - операцию исключения.Рассмотрим подробнее работу блиКа 18 на первом этапе. На,первые входы элементов И 20, 21, 22 и 23 поступают сигналы с прямых выходов разрядов третьего периода регистра 9. На вторые входы этих элементов подаются сигналы, пришедшие с инверсных выходов разрядов с дополнительными весами второго периода. Сигнал на выходе некоторого элемента И появится только в том случае, если в соот 1 ветствующем разряде третьего периода содержится 1, а в разряде второго периода с дополнительным весом - О, Соответственно, в блоке 19 объединяются прямые выходы разрядов второго периода с инверсными разрядами третьего периода. Разряды первого периода объединяются на перовом этапе схемами 12 и 14 с разрядами этого же периода, операцию исключения выполняет блок 17. Полученный таким образом результат первого этапа преобразования записывается в регистр 10. Например, число 1101 1011 1110 после первого этапа преобразования будет иметь вид;0001 1000 0100.На втором этапе регистр 9 предварительно устанавливается;в 0 импульсом ТО 2, Затем тактовый импульс Т, подается на схемы И 24, 2 б и 2 б. Инверсные выходы разрядов третьего периода через схему 24 поступают в блок 27, первого периода через схему 25 - в блок 28 и второго периода через схему 2 б - в блок 29. Блоки 27, 28 и 29 аналогичны блоку 18. Результат второго этапа преобразования заносится в регистр 9,На третьем этапе регистр 10 устанавливается в 0 импульсом То затем подается импульсТз на схемы И 30, 31 и 32. При этом число,находящееся в регистре 9, подвергается третьему этапу преобразования, который выполняется аналогично первому этапу. Результаттретьего (последнего) этапа преобразованиязаносится в регистр 10.При наличии трехвходовых элементов Иможно прямые выходы разрядов первого периода регистра 9 завести,на схемы 12 и 31,второго периода - на схемы 11 и 32 и третьего периода - на схемы 13 и 30, Прямые выходы разрядов первого периода регистра 10заводятся на схему 25, второго периода - на2 б и третьего периода - на 24, т. е. функцииблоков 17, 18 и 19 перекладываются на схемы12, 31, И, 30, 11, 32, а функции блоков 27, 28и 29 перекладываются на схемы 24, 2 б и 25соответственно. При этом коммутацию надопроизводить так, чтобы схемы И объединяли прямые и инверсные выходы разрядов сдополнительными весами. Это позволяет сократить количество оборудования и время преобразования,С регистра 10 тактовым импульсом Т через схемы И 33, 34 и 3 б преобразованноечисло подается в блок вычисления частичныхвычетов 3,30Предмет изобретенияУстройство для определения вычетов чиселпо модулю, содержащее регистр исходногочисла, блок вычисления частичных вычетов,выходы которото соединены с входами сумматора, отличающееся тем, что, с целью упрощения устройства, оно содержит блок иоключения дополнительных пар, входы которогосоединены с выходами регистра исходного4 О числа, а выходы - со входами блока частичных вычетов,.3 1Л Заказ 425,6 Изд,873 Тираж 647 Подписное ЦНИИПИ Государственного комитета Совета Министров СССР по делам изобретений и открытий Москва, Ж, Раушская набд. 4/5