В ПТ6 Советский патент 1973 года по МПК G06F7/38 G06F11/10 

Изобретение относится к области вычислительной техники. Предлагаемое устройство может быть использовано для перевода двоично-кодированных чисел из систем счисленияС основаниями 2 в систему остаточных классов и для свертки чисел в уст|ройствах контроля по модулю. Известно устройство для вычисления вычетов чисел по модулю, содержащее регистр исходного числа, блок вычисления частичных вычетов, соединенный с сумматором, в основу которого положен следующий метод. Пусть исходное двоичное число записано в виде: Л а„2« + + ... + а,2 -f а,2 (1) где ,1, ,il,2,..., m. Необходимо вычислить наименьщ-ий положительный вычет А по модулю р, назовем его Ар. Рассматривается число А -f + ... :f a,/Ci + , (2) где (mod р)-наименьшие положительные вычеты степеней осно(вания 2 по модулю р. Из СВОЙСТ1В вычетов следует, что Ли Л принадлежат к одному классу вычетов А. Будем считать, что ki характеризует вес i-ro разряда. Известно, что ряд вычетов kt обнаруживает периодичность. Например, последовательность возрастающих степеней 2, 2, 2, 2, ... по модулю , дает ряд вычетов 1, 2, 4, 3, 1, 2, ... Длина периода этого ряда . Вообще для простого модуля, для которого основание степенной последовательности является первообразным корнем, длина периода . Если в качестве модуля берется составное число, то ряд вычетов может иметь начальный отрезок, не Включенный IB период, например для ряд ki имеет вид:1,2,4, 8,4,8,... Длина периода , длина начального отрезка . Таким образом, исходное число разбивается на период в зависимости от модуля р. На основании изложенного Ар определяется следующим способом. Разряды «сходного числа разбиваются яа / групп, в каждую из которых входят все разряды с одинаковым весом ki. Количество значащих разрядов каждой группы подсчитывается счетчиком по модулю р. Шифратор, стоящий на выходе счетчика, выдает наименьщий положительный вычет: с Е A cATcCmod р), где ,2,..., /; - число значащих разрядов в с-й группе;kc - вес разрядов, объединенных в с-ю группу. Назовем Be частичным вычетом. Количество частичных вычетов рав-но /. Эти вычеты подаются на сум,матор по модулю р. Сумма всех частичных вычетов, которая .получается на выходе сумматора, есть искомый вычет Ар (если число содержит начальный отрезок, то он без изменения включается -В сумму, поскольку не может быть больше р). Однако этот метод требует большого количества оборудования при одновременном суммировании частичных вычетов (например, на ниралгидальном сумм-аторе) илл много времени при последовательном суммировании частичных вычетов. Цель изобретения - уменьшение расхода оборудования при одновременном суммировании частичных вычетов с сохранением примерно того же быстродействия или уменьшение затрат времени пр« носледовательном сум.миро-вании частичных вычетов. Эффективность онисываемого устройства повышается при увеличении периода /. Предлагаемый метод предназначен для систем счисления с основаниями 2. Метод непригоден для построения устройства определения вычетов по следуюп;иМ модулям:1., 1, 2, 3, ... 2. , 1, 2, 3, ...; , 4, 5 ...; . 3.Если простое р не имеет 2 в числе своих первообразных корней. 4.Если в разложении составного р на простые множители есть хоть один, для которого 2 не является первообразным корнем. Для достижения поставленной цели используется слвдуюш;ее свойство рядов вычетов. В периоде ряда вычетов ki по любому модулю (за исключением перечисленных в пунктах 1 - 4) четное число членов, причем в нем существует - пар, сумма членов которых ра-вна р, т. е. сравнима с нулем по модулю р. Назовем такие нары до1полнительными, а их члены - дополняющими вычетами, причем, если перенуМеровать члены периода числами от 1 до /, то дополнительные пары составят- члены, сто, , / . I ящие под номерами п и « - 2 Таким образом, если в двоичном числе А 0(2™ 4- «m-i 2-1 + ... + + «о2, и , где i и / - номера разрядов, в которых вычеты чисел 2 и 2 составляют дополнительную пару, то можно присвоить а, и uj значения О, так как 2+2- 0 (mod/). В сумме (формула 2) исчезнут два слагаемых aiki и ujkj. Назовем эту операцию исключением. Пусть исходное число имеет длину 5/+/, где S - число периодов (в общем случае последний, S-й период может быть яеполл ьгм). В каждом периоде леренумеруем разряды, начиная с младшего, числами от 1 до /. Если в исходном числе выполнить операцию исключения над всеми дополнительными парами, то в преобразованном числе не останется ни одной дополнительной пары единичных разрядов. Если хотя бы один разряд с весом АС в преобразованном числе равен 1, то можно утверждать, что все разряды, имеющие вес р-kc, равны 0. Преобразованное число может содержать максимум -единичных разрядов и разнообразие весов в нем уменьшается вдвое по сравнению с, исходным. Для получения преобразованного числа каждый ге-й разряд (, 2,...,- ) /-го пеV2 риода должен быть поэтапно объединен в пару с(п-11-м разрядом g-ro периода (, / S; , 2, S) и каждый п-й разряд g-TO периода-с (/г-)-)-м разрядом /-го пе 2 / Процесс объединения всех разрядов риода. периодов / g в дополнительные пары назовем объединением периодов f и g. После исключения дополнительных пар разряды полученного числа, имеющие один и тот же вес, группируются в / групп. Пзсть в группу п группируются разряды с весом kn, а в группу весом f- . i I - „h -р Кп. скольку в полученном после исключения числа нет ни одной дополнительной пары единич/ , f ных разрядов, одна из групп n,n-ij абяза 2 / тельно должна состоять из нулей. Разряды этих rpynin можно попарно объединить логическими элементами «ИЛИ и подать на счетчик по модулю р для подсчета числа значащих разрядов. Если максимальное число разрядов в группе не более , то отпадает необходимость в счетчике по модулю р (нужно, чтобы счетчик мог сосчитать не менее k диниц). Шифратор, стоящий на выходе счетика, в зависимости от числа разрядов и от ого, в какой из двух групп со1а,ержатся едиицы, выдает код, соответствующий паименьему положительному вычету Вп: В„ + o.k, +1 j (mod р), ри этом kn + k I EO(modp), 2 - ) . если единицы содержатся в группе п, , если группа п состоит из нулей; - число единиц в ненулевой группе, kn - вес разрядов в группе п, в группе /гН kn + - -вес разрядов о аналогии с предыдущим будем называть п также частичным вычетом. Поскольку количество частичных вычетов в данном случае по срав нению с известным методом вдвое меньше, здесь требуется не /, а - счетчиков для подсчета числа еди«и:ц в группах. С выходов шифраторов на сумматор поступает не , а - слагаемых. 2 Для достижения поставленной цели в известное устройство введен блок исключения дополнительных пар, входы которого соединены с выходами регистра исходного числа, а выходы - со входами блока частичных вычетов. При использовании сумматора, воспринимающего одновременно все частичные вычеты, уменьшение количества слагаемых вдвое приводит к сокращению оборудования сумматора в два раза. На фиг. 1 изображена функциональная схема устройства для определения вычетов чисел по -модулю; на фиг. 2 - логическая схема блока исключения дополнительных пар устройства для определения вычетов 12-раз-рядного двоичного числа по модулю 5. На фзНкциональной схеме устройства исходное число хранится в регистре / исходного числа. Регистр исходного числа разбит на п-одрегистры, соответственно периодам ряда вычетов возрастающих степеней двойки. Буквой t обозначен подрегистр, хранящий начальный отрезок числа. К выходу регистра 1 подключен блок исключения дополнительных пар 2. Преобразованное число поступает на вход блока вычисления частичных вычетов 3. В этом блоке разряды с дополнительными весами попарно группируются схемами 4. Собирательные схемы 5 сигнализируют о наличии хотя бы одной единицы в одной из групп разрядов с дополнительными весами. Счетчики 6 суммируют поступающие со схем 4 единицы. Шифраторы 7 в зависимости от чисел, поступающих со счетчиков 6, и от наличия или отсутствия единицы на выходе собирательных схем 5 выдают код в соответствии с формулой (3). Сумматор 8 по модулю р вычисляет искомый вычет Ар. Предлата-емое устройство работает следующим образом. Исходное число с регистра / поступает в блок исключени я дополнительных пар 2. Каждое однолинейное функциональное соединение регистра / с блоком 2 (фиг. 1) словно -представляет / одинарных щин. Блок исключения дополнительных пар 2 на каждом этапе объединяет периоды (1-S} и производит операцию исключения. Причем, на каждом последующем этапе в качестве исходной информации используется число, лолученное на предыдущем этапе. Преобразованное число с блока 2 поступает в блок вычисл:ения частичных вычетов 3. Каждое функциональное соединение блока 2 с блоком 3 на фиг. 1 условно представляет S одинарных шин, и ло ним передаются разряды с одинаковым весом. На входе блока 3 имеются - схем группировкн . В п схему группировки 4 поступают две группы по S шин каждая. Одна из этих rpyinn передает инфор.мацию от всех п-X разрядов периодов, а вторая - от всех () -к. Схемы 4 осуществляют попарную группировку разрядов с дополнительными весами, т. е. каждая пара передается через логический элемент «ИЛП. Выходы схем 4 содержат по 5 шин. Счетчики 6 подсчитывают число единиц, поступающих со схем 4. Код, соответствующий этому числу, поступает на шифраторы 7. Схемы сборки 5, подключенные к одной из групп щин, входящих в схемы 4, представляют собой элементы «ИЛИ на 5 входов. Наличие на выходе сборки 5 единицы свидетельствует о том, что в той группе, к которой она подключена, есть хотя бы одна единица, следовательно по другой группе щин идут нули. Это дает щифратору 7 информацию о том, -какой из двух весов -должны иметь разряды числа. Шифратор определя-ет нанменьщий положительный вычет, соответствующий сумме, поступающей со счетчика. 6, с учетом веса. Функционирование шифраторов определяется формулой (3). Начальный отрезок i с регистра / н - частичных вычетов с щифраторов 7 поступают на сумматор 8 по модулю р, с выхода которого снимается искомый вычет А-р. Бло1К исключения дополнительных пар устройства для определения вычета 12-разрядного двоичного числа по модулю 5 (фиг. 2) содержит регистры 9 и /О и комбинационные схемы, выполняющие преобразования при передаче числа между регистрами. Исходное число хранится в регистре 9. На чертеже регистры условно разбиты на разряды, правые выходы которых соответствуют прямым кодам, а левые - инверсным. Период ряда вычетов возрастающих степеней 2 по модулю 5 имеет вид: 1, 2, 4, 3. Длина периода , начальный отрезок отсутствует. Исходное 12-разрядное число разбивается на трн периода, по четыре разряда в каждом. В начале преобразования регистр W устанавливается в О импульсом Гоь На первом этапе преобразования тактовый импульс 7i подается на схемы «И //, /2, 13, каждая из которых состоит из четырех элементов «И на -два входа. Информация с инверсных выходов перв-ого периода через схему 12 и схему 14, представляющую собой (так же как /5 и /5) четыре двухвходовых элемента «ИЛИ, поступа-ет в блок /7. С инверсных выходов разрядов второго периода через схемы 13 и 16--в блок 18 W с инверсных выходов разрядов третьего периода через схемы // и 15 - в блок 19. Каждый из блоков 17, 18 и 19 состоит из четырех элементов «И. На один из входов

каждого элемента «И подается сигнал с прямого выхода соответствующего разряда регистра 5, а на вход через соответствующие логические схемы поступает сигнал с инверсного выхода разряда с дополнительным весом. Схемы //, 12, 13, 14, 15, 16 выполняют олерацию объединения, а блоки 17, 18 19 - операцию исключения.

Рассмотрим подробнее работу блока 18 на первом этапе. На .первые входы элементов «И 20, 21, 22 и 23 поступают сипналы с прямых (ВЫХОДОВ разрядов третьего периода регистра 9. На вторые входы этих элементов подаются сигналы, пришедшие с инверсных выходов разрядов с дополнительными весами второго периода. Сигнал на выходе -некоторого элемента «И появится только в том случае, если в соответствующем разряде третьего периода содержится Лав разряде второго периода с дополнительным весом - 0. Соответственно, в блоке 19 объединяются прямые выходы разрядов второго периода с инверсными разрядами третьего периода. Разряды пе;рваго периода объединяются .на первом этапе схемами 12 -ц 14 с разрядами этого же периода, операцию исключения выполняет блок 17. Полученный таким образом результат первого этапа преобразования записывается в регистр 10. Например, число 1101 1011 1110 после первого этапа преобразования будет иметь вид: 0001 1000 0100.

На втором этапе регистр 9 предварительно 5Стана1вливается в О импульсом Тоа. Затем такто1вый импульс Гз подается на схемы «И 24, 25 и 26. Инверсные выходы разрядов третьего периода через схему 24 поступают в блок 27, первого периода через схему 25 -в блок 28 и второго периода через схему 26 - в блок 29. Блоки 27, 28 и 29 аналогичны блоку 18. Результат второго этапа преобразования заносится в регистр 9.

На третьем этапе регистр 10 устанавливается в О импульсом TOI, затем подается импульс Гз на схемы «И 30, 31 и 32. При этом число, находящееся в регистре 9, подвергается третьему этапу преобразования, который выполняется аналогично первому этапу. Результат третьего (последнего) этапа преобразования заносится в регистр 10.

При наличии трехвходовых элементов «И можно прямые выходы разрядов первого периода регистра 9 завести на схемы 12 и 31, второго периода--на схемы 11 и 32 и третьего периода - на схемы 13 и 30. Прямые выходы разрядов первого периода регистра 10 заводятся на схему 25, второго периода - на 26 и третьего периода - на 24, т. е. функции блоков 17, 18 и 19 перекладываются на схемы 12, 31, 13, 30, 11, 32, а функции блоков 27, 28 и 29 перекладываются на -схемы 24, 26 и 25 соответственно. При этом коммутацию надо производить так, чтобы схемы «И объединяли и инверсные выходы разрядов с дополнительными весами. Это позволяет сократить количество оборудования и время преобразования.

С регистра 10 тактовым импульсом Ti через схемы «И 33, 34 и 35 преобразованное число подается в блок вычисления частичных вьгчетов 3.

Пред мет изобретен и я

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

12jj

fe

УЗ

,327-J

J 2S 72

26

,

jrr

K/ /(2