В пт6

 

ОПИСАНИЕ З9Б6!

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Союз Советских

Социалистических

Республик

Зависимое от авт. свидетельства №

Заявлено 15Х11.1970 (№ 1468950/18-24) М. Кл. С 061 4/52

С 061 11/08 с присоединением заявки №

Приоритет

Опубликовано 25.VII.1973. Бюллетень № 31 УДК 681.326(088.8)

Дата опубликования описания 26.XI I.1973

Государственный комитет

Совета Министров СССР во делам изобретений и открытий

ВПТУ

1"" ". о" .PT08

Автор изобретения

Г. Г. Иванов

Институт математики Сибирского отделения АН СССР

Заявитель

УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ВЫЧЕТОВ

ЧИСЕЛ ПО МОДУЛЮ

Изобретение относится к области вычислительной техники.

Предлагаемое устройство может быть использовано для перевода двоично-кодированных чисел из систем счисления с основаниями

2" в систему остаточных классов и для свертки чисел B устройствах контроля по модулю.

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

Пусть исходное двоичное число записано в ви де:

А = ат2т + ат — I2m-т+... + а,2 + ао2о, (1)

15 где а — — 0,1, i=0,1,2,..., m.

Необходимо вычислить наименьший положительный вычет А во модулю р, назовем его 20

А>. Рассматривается число

А = атКт + ат-I Кт — I + + а,К, + аоКо (2) где k =2 (mod р) — наименьшие положительные вычеты степеней осно- 25 вания 2 IIо модулю р.

Из свойсвв вычетов следует, что А и А принадлежат к одному классу вычетов А. Будем считать, что k; характеризует вес i-го разряда.

Известно, что ряд вычетов 4 обнаруживает 30

2 периодичность. Например, последовательность возрастающих степеней 2, 2, 2, 2, ... по модулю p=5, дает ряд вычетов 1, 2, 4, 3, 1, 2, ...

Длина периода этого ряда 1=4. Вообще для простого модуля, для которого основание степенной последовательности является первообразным корнем, длина периода I=p — 1. Если в качестве модуля берется составное число, то ряд вычетов может иметь начальный отрезок, не включенный в период, например для р=12 ряд lг; имеет вид:1, 2, 4, 8, 4, 8,... Длина периода

1=2, длина начального отрезка 1=2. Таким образом, исходное число разбивается на период% в зависимости от модуля р. На основании изложенного А определяется следующим способом.

Разряды исходного числа разбиваются на 1 групп, в:каждую из которых входят все разряды с одинаковым весом k;. Количество значащих разрядо в каждой группы подсчитывается счетчиком по модулю р. Шифратор, стоящий на выходе счетчика, выдает наименьший положительный вычет:

В, N,Ê,(IIIOd Р), где С=1,2,..., 1;

N, — число значащих разрядов в с-й группе; й, †в разрядов, объединенных в с-ю группу.

391561

Назовем В, частичным вычетом. Количество частичных вычетов равно 1. Эти вычеты подаются на сумматор по модулю р. Сумма всех частичных вычетов, которая, получается на выходе сумматора, есть искомый вычет А„(если число содержит начальный отрезок, то он без изменения включается .в сумму, поскольку не может быть больше р) .

Однако этот метод требует большого количества оборудования при одновременном суммировании частичных вычетов (например, на пирамидальном сумматоре) пли много времени при последовательном суммировании частичных вычетов.

Цель изобретения — уменьшение расхода оборудования при одновременном суммировании частичных вычетов с сохранением примерно того же быстродействия или уменьшение затрат времени при последовательном суммировании частичных вычетов. Эффективность описываемого устройства повышается при увеличении периода l. Предлагаемый метод предназначен для систем счисления с основаниями

2П

Метод непригоден для построения устройства определения вычетов по следующим модулям:

1. р=2 Р d=O, 1, 2, 3, ...

2. р=2 — 2 d=0, 1, 2, 3, ...; 1=3, 4, 5 ...;

dc 1 — 3.

3. Если простое р не имеет 2 в числе своих первообразных корней.

4. Если в разложении составного р на простые множители есть хоть один, для которого

2 не является первообразным корнем.

Для достижения поставленной цели ис пользуется следующее свойство рядо в вычетов.

В периоде ряда вычетов k; по любому модулю (за исключением перечисленных в пунктах 1—

4) четное число членов, причем в нем сущестl вует — пар, сумма членов которых равна р, 2 т, е. сравнима с нулем по модулю р. Назовем такие пары дополнительными, а их члены— дополняющими вычетами, причем, если перенумеровать члены периода числами от 1 до l„ то до полнительные пары составят члены, стоt ящие под номерами п и n+l п (— 1.

Таким образом, если в двоичном числе

А = я 2 "+ am р2 +... + a,2 + аю2, (3) 1 и 1 2

2 а = 1, если единицы содержатся в группе п, а=О, если группа п состоит из нулей;

60 A — число единиц в ненулевой группе, k„— вес разрядов в группе п, l й„+ — вес разрядов в группе n+ —.

По аналогии с предыдущим будем называть

65 В„также частичным вычетом, Поскольку коа;=1 и а;=1, где i u j — номера разрядов, в которых вычеты чисел 2 и 21 составляют дополнительную пару, то можно присвоить а, и а, значения О, та к как 2 +21=0 (mod р).

В сумме (формула 2) исчезнут д ва слагаемых

u;k; и à;k,. Назовем эту операцию исклю чением.

Пусть исходное число имеет длину Я+1, где

S — число периодов (в общем случае последний, S-й период может быть неполным) . В каждом периоде перенумеруем разряды, начиная с младшего, числами от 1 до l. Если в исходном числе выполнить операцию исключения над всеми дополнительными парами, то в преооразованном числе не останется ни одной дополнительной пары единичных разрядов. Если хотя бы один разряд с весом k,,â преобразованном числе равен 1, то можно утверждать, что все разряды, имеющие вес р — k, равны О.

Преобразованное число может содержать мак1 симум 1+5 — единичных разрядов и разнообг разие весое в нем уменьшается вдвое по сравнению с исходным.

Для получения преобразованного числа

l каждык п-й разряд n=1,2,...,— ) f-го пе " г риода должен быть поэтапно объединен в nal1 ру с(п+ — )-м разрядом д-го периода (f=l, 2)

2, ..., S; д =1, 2, ..., S) и каждый п-й разряд

I го

g-го периода — c (h+ — l-м разрядом f-го пе2,1 риода. Процесс объединения всех разрядов периодов f u g в дополнительные пары назовем объединением периодов f u g.

После исключения дополнительных пар разряды полученного числа, имеющие о дин и тот же вес, группируются в 1 групп. Пусть в группу п группируются разряды с весом А, а в группу и+ — — с весом k + — — р — k . По1

2 2 скольку в полученном после исключения числа нет ни одной дополнительной пары вдинич11 ных разрядов, одна из групп и,и+ — 1 обязательно должна состоять из нулей. Разряды этих групп можно:попарно объединить логическими элементами «ИЛИ» и подать на:счетчи к по модулю р для подсчета числа значащих раз рядов. Е сли максимальное число раз,рядов в группе не более k(p, то отпадает

4О необходимость в счегчике по модулю р (нужно, чтобы счетчик мог сосчитать не менее Й единиц). Шифратор, стоящий на выходе счетчи ка, в зависимости от числа разрядов и от того, в какой из двух групп .содержатся еди4> ницы, выдает код, соответствующий наименьшему пооложительно му IBblчету В:

В„: N ak„+ а k, + (mod р), при этом

kÄ+ k t: 0(mod р), 2

39I 561 личество частичных вычетов в данном случае по сравнению с известным методом вдвое

l меньше, здесь требуется уже не l, а — счетг чиков для подсчета числа единиц в группах.

С выходов шифраторов на сумматор поступает

1 не l, а — слагаемых.

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

B два раза.

На фиг. 1 изображена функциональная схема устройства для о пределения вычетов чисел по модулю; на фиг. 2 — логическая схема блока исключения дополнительных пар устройства для определения вычетов 12-разрядного двоичного числа по модулю 5.

На функциональной схеме устройства исходное число хранится в регистре 1 исходного числа. Регистр исходного числа разбит на подрегистры, соответственно периодам ряда вычетов возрастающих степеней двойки. Буквой 1 обозначен подрегистр, хранящий начальный отрезок числа. К выходу регистра 1:подключен блок исключения дополнительных пар

2. Преобразованное число поступает на вход блока вычисления частичных вычетов 8. В этом блоке разряды с дополнительными весами попарно группируются схемами 4. Собирательные схемы 5 сигнализируют о наличии хотя бы одной единицы в одной из групп раз рядов с дополнительными весами.

Счетчики 6 суммируют поступающие со схем

4 единицы. Шифраторы 7 в за висимости от чисел, поступающих со счетчиков 6, и от наличия или отсутствия единицы на выходе собирательных схем 5 выдают код в соответст- 46 вии с формулой (3). Сумматор 8 по модулю р вычисляет искомый вычет А„.

Предлатаемое устройство работает следуюшим образом, Исходное число с регистра 1 посту пает в 6п блок исключения дополнительных пар 2. Каждое однолинейное функциональное соединение регистра 1 с блоком 2 (фиг. 1) условно представляет 1 одинарных шин. Блок исключения дополнительных пар 2 на каждом этапе объе- 65 диняет периоды (1 — $) и произ|водит операцию исключения. Причем, на каждом последующем этапе в качестве исходной информации используется число, .полученное на предыдущем этапе. 60

Преобразованное число с блока 2 лоступает в блок вычисления частичных вычетов 8. Каждое функциональное соединение блока 2 с блоком 8 HB фиг. 1 условно представляет S одинарных шин, и по ним передаются разряды с 66 одинаковым весом. На входе блока 8 имеются

l — схем группировки 4. В и схему группировки

4,поступают д ве группы по S шин каждая.

Одна из этих групп передает информацию от всех и — х разрядов периодов, а вторая — от

1 всех (и+ — ) — х. Схемы 4 осуществляют по2 парную группировку разрядов с дополнительными весами, т. е. каждая пара передается через логический элемент «ИЛИ». Выходы схем 4 содержат по S шин. Счетчики 6 подсчитывают число единиц, поступающих со схем 4.

Код, соответствующий этому числу, поступает на шифраторы 7.

Схемы сборки 5, подключенные к одной из групп шин, входящих в схемы 4, представляют собой элементы «ИЛИ» на S входов. Наличие на выходе сборки 5 единицы свидетельствует о том, что в той группе, к которой она подключена, есть хотя бы одна единица, следовательно по другой группе шин идут нули.

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

Функционирование шифраторов определяется формулой (3). Начальный отрезок t с регистl ра 1 и — частичных вычетов с шифраторов 7 г поступают на сумматор 8 по модулю р, с выхода которого снимается искомый вычет А„, Блок исключения дополнительных пар устройства для определения вычета 12-разрядного двоичного числа по модулю 5 (фиг, 2) содержит регистры 9 и 10 и комбинационные схемы, вьгполняющие преобразования при передаче числа между регистрами. Исходное число хранится в регистре 9. На чертеже регистры условно разбиты на разряды, правые выходы которых соответствуют прямым кодам, а левые — инверсным.

Период ряда вычетов возрастающих степеней 2 по модулю 5 имеет вид: 1, 2, 4, 3. Длина периода l=4, начальный отрезок отсутствует. Исходное 12-разрядное число разби вается на три периода, по четыре разряда в каждом.

В начале преобразования регистр 10 устана вливается в О импульсом Три На первом этапе преобразования тактовый импульс Ti подается на схемы «И» 11, 12, 13, каждая из которых состоит из четырех элементов «И» на два входа. Информация с инверсных выходов первого периода через схему 12 и схему 14, представляющую собой (так же как 15 и 16) четыре двухвходовых элемента «ИЛИ», поступает в блок 17. С инверсных выходов разрядов второго периода через схемы И и 16 — в блок 18 и с инверсных выходов разрядов третьего периода через схемы 11 и 15 — в блок

19. Каждый из блоков 17, 18 и 19 состоит из четырех элементов «И». На один из входов

391561 каждого элемента «И» подается сигнал с прямого выхода соответствующего разряда регистра 9, а на второй вход через соответствующие логические схемы поступает сигнал с инверсного выхода разряда с дополнительным весом. Схемы 11, 12, И, 14, 15, lб выполняют операцию объединекия, а блоки 17, 18 19— операцию исключения.

Рассмотрим подробнее работу блиКа 18 на первом этапе. На,первые входы элементов «И»

20, 21, 22 и 28 поступают сигналы с прямых выходов разрядов третьего периода регистра

9. На вторые входы этих элементов подаются сигналы, пришедшие с инверсных выходов разрядов с дополнительными весами второго периода. Сигнал на выходе некоторого элемента «И» появится только в том случае, если в соответствующем разряде третьего периода содержится 1, а в разряде второго периода с дополнительным весом — О, Соответственно, в блоке 19 объединяются прямые выходы разрядов второго периода с инверсными разрядами третьего периода. Разряды nepIIoI.o периода объединяются на первом этапе схемами

l2 и 14 с разрядами этого же периода, операцию исключения выполняет блок 17. Полученный таким образом результат первого этапа преобразования записывается в регистр 10.

Например, число 1101 1011 1110 после первого этапа преобразования будет иметь вид;

0001 1000 0100.

На втором этапе регистр 9 предварительно устава вливается;в 0 импульсом ТО2, Затем тактовый импульс Т2 подается на схемы «И»

24, 25 и 2б. Инверсные выходы разрядов третьего периода через схему 24 поступают в блок 27, первого периода через схему 25 — в блок 28 и второго периода через схему 2б— в бло.к 29. Блоки 27, 28 и 29 аналогичны блоку 18. Результат второго этапа преобразования заносится в регистр 9.

На третьем этапе регистр 10 устанавливается в 0 импульсом То, затем подается импульс

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

При наличии трехвходовых элементов «И» можно прямые выходы разрядов первого периода регистра 9 за вести,на схемы 12 и 81, второго периода — на схемы 11 и 32 и третьего периода — на схемы 18 и 80, Прямые выходы разрядов первого периода регистра 10 заводятся на схему 25, второго периода — на

2б и третьего периода — на 24, т. е. функции блоков 17, 18 и 19 перекладываются на схемы

12, 81, И, 80, 11, 82, а функции блоков 27, 28 и 29 перекладываются на схемы 24, 2б и 25 соответственно. При этом коммутацию надо производить так, чтобы схемы «И» объединяли прямые и инверсные выходы разрядов с дополнительными весами. Это позволяет сократить количество оборудования и время преобразования.

С регистра 10 TBKToiBbIM импульсом Tr, через схемы «И» 38, 84 и 85 преобразованное число подается в блок вычисления частичных вычетов 8.

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

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

® числа, а выходы — со входами блока частичных вычетов.

391561

Фиг / тл т и

72 7/ тЗ 50

701

25 Т2

7Z г

2Á

1 а

Фиг. 2

Составитель В. Крылова

Редактор Е. Гончар Техред Е .Борисова Корректоры: М. Коробова и В. Петрова

Заказ 425, 6 Изд. № 873 Тираж 647 Подписное

ЦНИИПИ Государствен|ного комитета Совета Министров СССР по делам изобретений и открытий

Москва, 7К-35, Раушская наб„д. 4/5

Типография, пр. Сапунова, 2

ТФ Ó5 Г

I!