Устройство для пирамидальной свертки по модулю три Советский патент 1989 года по МПК G06F11/10 

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

Целью изобретения является повышение быстродействия устройства.

На чертеже представлена структурная схема предлагаемого устройства пирамидальной свертки по модулю три для случая .

Устройство. содержит сумматоры

K1,-b2,...1.N/8-1, N/8 первой сту..пени свертки, сумматоры 2.1,...2.N/16

второй ступени свертки,сумматор 3 (п-1)-й ступени свертки и сумматор 4 по модулю три-П-й ступени свертки.

Устройство работает следую1цим .образом. .

Контролируемое N-разрядное число поступает на входы нечетных разрядов А 1, В 1, В 3 и входы переноса Р сумматоров 1.1, 1.2,...1.N/8-1, 1.N/8 первой ступени свертки своими нечетными разрядами, а на входы четных разрядов А 2, В 2иА4, В 4 этих сумматоров - четными разрядами. Результаты сложения нечетных разрядов с первых выходов сумматоров с первой по (п-1)-ю ступень свертки поступают на входы нечетных разрядов А 3 этих же сумматоров. Получаемые при этом коды с выходов S2, S3, 84иР4 смежных (2К-1)-го и 2К-го сумматоров первой, ц затем второй и т..д. , т.е. ( ступени свертки, j 2, ii-l, К 1,2 Т , пост5шают на входы разрядов А 2, В 1, В 2, А 1, А 4, В 3, В 4 и вход переноса РО К-го сумматора второй, третьей и т.д., т.е. j-й ступени свертки. Нечетные и чет- ные разряды контролируемого числа, также как и нечетные и четные разряды кодов, получаемых с нечетных и чет ньк выходов сумматоров, имеют соответственно веса по модулю три 1 и 2. Это обеспечивает получение на выходах S2, S3, 84иР4 каждого сумматора код, имеющий остаток от деления на три такой же, как и восьмиразрядное число, нечетные и четные разряды ко- торого поданы на входы нечетных (включая вход переноса) и четных разрядов этого сумматора соответственно. Таким образом, на выходе сумматора 3 образуется код. конгруентной -по модулю три контролируемому числу. Этот код сво- рачиваетЬя на сумматоре 4 по модулю три до двух разрядов и, являясь остатком от деления контролируемого числа на три, поступает на выходы устройства. Формула .изобретения

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

n 5 5

0 5

0

числа устройства, входы четных разрядов которого являются входами четных разрядов сумматоров первой ступени, входы всех, кроме первого и (21-1)-го, нечетных разрядов первого слагаемого и входы всех нечетных разрядов второго слагаемого К-го сумматора j-й сту- пени свертки (j 2, п-1; К 1,) соединены соответственно с нечетными выходами, исключая первые выходы,двух смежных (2К-1)-го и 2К-го сумматоров ()й ступени свертки, входы четных разрядов первого и второго слагаемых К-го сумматора j-й ступени свертки соединены с четными выхода т двух смежных (2К-1)-го и 2К-го сумматоров (з-1)-й ступени свертки, все входы, кроме первого, нечетных разрядов первого слагаемого и входы всех нечетных разрядов второго слагаемого сумматора по модулю три соединены соответственно с нечетными выходами, кроме первого, сумматора (п-1)-й ступени свертки, четные выходы которого соединены соответственно с входами четных разрядов сумматора по модулю три, вход переноса и выход переноса сумматора по модулю три объединены между собой, а выходы сумматора по модулю три являются выходами устройства, отличающееся тем, что, с целью повышения быстродействия, вход (21-1)-го разряда первого слагаемого и первьй выход каждого сумматора с первой по (п-1)-ю ступени свертки объединены между собой, входы переносов сумматоров первой ступени свертки являются входами нечетных разрядов контролируемого числа устройства, выходы переносов двух смежных (2К-1)-го и 2К-ГО сумматоров (j-1)-й ступени свертки соединены соответственно с входом первого разряда первого слагаемого и входом переноса К-го сумматора j-й ступени свертки, выход переноса сумматора (п-О-й ступени свертки соединен с первым входом первого слагаемого сумматора по модулю три. .

Изобретение относится к области вычислительной техники и позволяет вычислять остаток от деления контролируемого числа на три с повышенным быстродействием. Устройство содержит N ступеней свертки, причем ступени с первой по (N-1) -ю содержат 2L - разрядные сумматоры, где L - целое, L≥2, а N - я ступень содержит сумматор по модулю три. Контролируемое число поступает нечетными разрядами на входы нечетных разрядов и переносов, а четными разрядами на входы четных разрядов сумматоров первой ступени. С первых выходов всех сумматоров результаты сложения нечетных разрядов поступают на входы (2L-1)-го разряда первого слагаемого этих же сумматоров. Коды с выходов смежных (2K-1)-го и 2K-го сумматоров (J-1)-й ступени поступают на входы разрядов и вход переноса K-го сумматора (J )-й ступени. Таким образом продолжают свертку сумматоры второй ступени, затем следующих ступеней, сумматора (N-1)-й ступени, код с выхода которого поступает четными и нечетными разрядами на входы четных и нечетных разрядов сумматора по модулю три. При этом сумматор по модулю три формирует остаток от деления контролируемого числа на три. Повышение быстродействия достигается за счет отсутствия цепей обратной связи для прохождения сигналов переноса в сумматорах с первой по (N-1)-ю ступеней свертки. 1 ил.