Устройство для пирамидальной свертки по модулю три
Изобретение относится к области вычислительной техники и позволяет вычислять остаток от деления контролируемого числа на три с повышенным быстродействием. Устройство содержит N ступеней свертки, причем ступени с первой по (N-1) -ю содержат 2L - разрядные сумматоры, где L - целое, L≥2, а N - я ступень содержит сумматор по модулю три. Контролируемое число поступает нечетными разрядами на входы нечетных разрядов и переносов, а четными разрядами на входы четных разрядов сумматоров первой ступени. С первых выходов всех сумматоров результаты сложения нечетных разрядов поступают на входы (2L-1)-го разряда первого слагаемого этих же сумматоров. Коды с выходов смежных (2K-1)-го и 2K-го сумматоров (J-1)-й ступени поступают на входы разрядов и вход переноса K-го сумматора (J )-й ступени. Таким образом продолжают свертку сумматоры второй ступени, затем следующих ступеней, сумматора (N-1)-й ступени, код с выхода которого поступает четными и нечетными разрядами на входы четных и нечетных разрядов сумматора по модулю три. При этом сумматор по модулю три формирует остаток от деления контролируемого числа на три. Повышение быстродействия достигается за счет отсутствия цепей обратной связи для прохождения сигналов переноса в сумматорах с первой по (N-1)-ю ступеней свертки. 1 ил.
СОЮЗ СОВЕТСКИХ
СОЦИАЛИСТИЧЕСКИХ
РЕСПУБЛИК
rsvp 4 С 06 F 11/10
; ° с
Вй .
Е .5,.
ОПИСАНИЕ ИЗОБРЕТЕНИЯ
К А ВТОРСКОМУ СВИДЕТЕЛЬСТВУ
ГОСУДАРСТВЕННЫЙ КОМИТЕТ
ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ
ПРИ ГКНТ СССР
1 (21) 4402162/24-24 (22} 04.04.88 (46) 07.11.89. Бюл. 8 41 (72) П.И. Плиц и А.В. Дрозд . (53) 681. 3 (088. 8) (56) Авторское свидетельство СССР
Р 1084799, кл. G 06 F 11/10, 1982 °
Авторское свидетельство СССР
Ф 1105896, кл. G 06 F 11/10, 1982.
{54) УстРойство для пиРлмидАльной сВеРтки пО ИОдулю ТРи (57) Изобретение относится к области вычислительной техники и позволяет вычислять остаток от деления контролируемого числа на три с повышенным быстродеиствием. Устройство содержит и ступеней свертки, причем ступени с первой по (n-1)-ю содержат 21-разрядные сумиаторы, где 1 — целое, 1 2, а п-я ступень содержит сумматор по модулю три. Контролируемое число поступает нечетными разрядами на входы нечетных разрядов и переносов, а чет° Изобретение относится к вычислительной технике и может быть использовано в цифровых устройствах для контроля арифметических операций.
Целью изобретения является повышение быстродействия устройства.
На чертеже представлена структурная схема предлагаеиого устройства пирамидальной свертки по модулю три для случая 1. = 2, Устройство. содержит сумматоры
1.1,.1;7 1.N/8-1, N/8 первой сту.пени свертки„ сумматоры 2.1,...2.N/16
„.Я0„„152 5 4 А1
2 ным разрядами на входы четных разрядов сумматоров первой ступени. С первых выходов всех сумматоров результаты сложения нечетных разрядов поступают на входы (21-1)-ro разряда первого слагаемого этих же сумматоров.
Коды с выходов смежных (2К-1)-ro u
2К-го сумматоров (j-1)-й ступени поступают на входы разрядов и вход переноса К-го сумматора (j-й)-й ступени. таким образом. продолжают свертку сумматоры второй ступени, затем следующих ступеней, сумматора (п-1)-й ступени, код с выхода которого поступает четными и нечетными разрядами на входы четных и нечетных разрядов сумматора по мацулю три. При этом сумматор по модулю три формирует остаток от деления контролируемого числа на три. Повышение быстродействия достигается за счет Отсутствия цепей обратной связи для прохождения сигналов переноса в сумматорах с первой по (n-1)-ю ступеней свертки. 1 ил. второй ступени свертки, сумматор 3 (и-1)-й ступени свертки и сумматор 4 по модулю три.п-й ступени свертки.
Устройство работает следуюцим .образом.
Контролируемое N-разрядное число поступает на входы нечетных разрядов
А 1, В 1, В 3 и входы переноса Р сумматоров 1.1, 1.2,...1.N/8-1, 1.N/8 первой ступени свертки своими нечетными разрядами, а на входы четных разрядов А 2, В 2 и А 4, В 4 этих сумматоров — четными разрядами. Ре1520524 зультаты сложения нечетных разрядов с первых выходов сумматоров с первой по (и-1)-ю ступень свертки поступают на входы нечетных разрядов А 3 этих же сумматоров. Получаемые при этом коды с выходов S 2, S 3 S 4 и Р 4 смежных (2К-1}-ro и 2К-го сумматоров первой, а затем второй и тед., т.е. (j-t}-й ступени свертки, j = 2, п-1, и
К 1,2" 1, поступают на входы разрядов А 2, В 1, В 2, А 1, А 4, В 3, В 4 и вход переноса Р К-ro сумматора второй, третьей и т.д., т.е.
j-й ступени свертки. Нечетные и четные разряды контролируемого числа, также как и нечетные и четные разряды кодов, получаемых с нечетных и четных выходов сумматоров, имеют соответственно веса по модулю три 1 и 2..
Это обеспечивает получение на выходах
$ 2, S 3,,S 4 и Р 4 каждого сумматора код, имеющий остаток от деления на три такой же, как и восьмиразрядное число, нечетные и четные разряды которого поданы на входы нечетных (включая вход переноса) и четных разрядов этого сумматора соответственно. Таким образом, на выходе сумматора 3 образуется код конгруентной .по модулю три контролируемому числу. Этот код сворачивается на сумматоре 4 по модулю три до двух разрядов и, являясь остатком от деления контролируемого числа на три, поступает на выходы устройства.
Формула
35 иэ о орет ения
Устройство для пирамидальной свертки по модулю три, содержащее п ступеней свертки, причем ступени свертки с 4О первой по (и-1)-ю содержат 21-разрядные сумматоры (1 — целое, 1 7 2),п-я ступень свертки содержит сумматор по модулю три, причем входы всех, кроме .(21-1}-го, нечетных разрядов первого 45 слагаемого и входы всех нечетных разрядов второго слагаемого сумматоров первой ступени свертки являются входаии нечетных разрядов контролируемого числа устройства, входы четных разрядов которого являются входами четных ! разрядов сумматоров первой ступени, входы всех, кроме первого и (21-1)-го, нечетных разрядов первого слагаемого и входы всех нечетных разрядов второгс спегееисгс К-го етпре -й ступени свертки (j = 2, и-1; К = 1,2" ) соединены соответственно с нечетными выходами, исключая первые выходы, двух смежных (2К-1)-го и 2К-го сумматоров (j-1)-й ступени свертки, входы четных разрядов первого и второго слагаемых К-ro сумматора j-й ступени свертки соединены с четными выходаии двух смежных (2К-1)-го и 2К-го сумматоров (j-1)-й ступени свертки, все входы, кроме первого, нечетных разрядов первого слагаемого и входы всех нечетных разрядов второго слагаемого сумматора по модулю три соединены соответственно с нечетными выходами, кроме первого, сумматора (п-1)-й ступени свертки, четные выходы которого соединены соответственно с входами четных разрядов суиматора по модулю три, вход переноса и выход переноса сумматора по модулю три объединены между собой, а выходы сумматора по модулю три являются выходами устройства, о т л и ч а ю щ е е с я тем, что, с целью повьппения быстродействия,.вход (21-1)-го разряда первого слагаемого и первый выход каждого сумматора с первой по (n-1)-ю ступени свертки объединены между собой, входы переносов сумматоров первой ступени свертки являются входами нечетных разрядов контролируемого числа устройства, выходы переносов двух смежных (2К-1)-ro и 2К-ro сумматоров (j-1)-й ступени свертки соединены соответственно с входом первого разряда первого слагаемого и входом переноса К-ro сумматора j-й ступени свертки, выход переноса сумматора (и-1}-й ступени свертки соединен с первым входом первого слагаемого сумматора по модулю три.
1520524. fl
fP
JP
tP
4Р
7Р
6Р
8Р
6Р
У
ftP
10Р
Sf
2Р
Ю
Ю
Я e)P
И-e)P и-ЯР (И)Р
fN-12)P (И)Р (u- )Р (N. 8)P
Ô-3)P (e-T)P (И-5)Р ф 6)P (И-ю)Р (iV-1)р (М-2) P Р
Составитель И. Иваныкин
Редактор В. Бугренкова Техред Л.Сердокова Корректор Э.Лончакова
Заказ 6759/50 Тираж 668 Подписное
ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР
113035, Москва, Ж-35, Раушская наб., д. 4/5
Производственно-издательский комбинат "Патент", r. Ужгород, ул. Гагарина, 101
