SU1325484A1 - Device for q = 2m-1 modulus convolution - Google Patents

Abstract

The invention relates to computing technology and is intended to form the residuals of the numbers modulo -1, where m is an integer, when hardware controls the transfer of binary numbers represented in parallel code and arithmetic operations on them. The purpose of the invention is to increase the efficiency of control by the expense of (L. F., F & m l lH i I.,, V t Yat On-l t Li O

Description

elimination of the ambiguity of the result of the formation of the remainder modulo q 2 -1. The device contains N groups 1 through m subgroups 2 in each group of one-digit adders, two t-times a regular adder 3.4, inputs 5 of the device, outputs 6 of the device. Device

1325484

forms, as a zero balance, a q code for nonzero codes that are multiples of q 2 –1. An increase in the monitoring efficiency is achieved by introducing a second t-bit adder, which forms a transfer to the first ' -disk adder. 2 Il.

one

The invention relates to computing and is intended for

modulo modulo

t. -1, where m is an integer, with

hardware control of the transfer of binary numbers presented in parallel code, and arithmetic operations on them.

The purpose of the invention is to increase the credibility of the control by eliminating the ambiguity of the result of the form2W J ..... -one.

FIG. 1 shows a functional diagram of the device; in fig. 2 - functional diagram of the i-th subgroup of the 1st group of adders.

The device contains N groups 1 through m subgroups 2 in each group of one-digit adders, two t-bit adders 3 and 4, inputs 5 and outputs 6 of the device. Each subgroup 2 (Fig. 2) contains one-digit adders 7.

The device works as follows.

A parallel p-bit code arrives at the inputs 5 of the device, and the inputs of the K. each i-th subgroup 2 1 and the groups from groups 1 receive the values of bits with a weight of 2

1-1

which

35

are summed with one-bit adders 7, making up a subgroup 2. The outputs of the A. i-th subgroup have weight 2, and the outputs of c. - weight 2. Outputs In the m-th subgroup have a weight of 2, which modulo 2 - 1 corresponds to 1, since 2 1 Joa () and is equal to the weight of outputs A. The 1st subgroup. In the i-x subgroups 2, all subsequent groups 1 similarly perform the summation of the values of the subgroups of the previous group with the same weight for each i-th subgroup. Outputs A of the subgroups have

Q

five

0

five

0

five

about

weight, and inputs B1 - weight 2. At the last stage after the N-th group, when Р 2, where P is the number of outputs of the i-th subgroup of the N-th group of cy D4 atopors, where 1 ii t, 1 i IN, the summation is performed by a t-bit adder 3 taking into account the transfer value coming from adder 4, which ensures sum modulo q.

At the outputs of the t-bit adder 3, which are the outputs 6 of the device, the final code value of the remainder r modulo q 2 - 1 is formed. At the same time when the zero n-bit code arrives at the inputs 5 of the device, the zero code of the remainder (g 0) , and on receipt of any nonzero n-bit code, the code of the remainder r is formed in such a way that 1 g q. Moreover, for a nonzero code that is multiple to the module q, the value of the remainder r is uniquely equal to the module q (r q). The fulfillment of the condition q q for nonzero codes is due to the fact that when summing the values of bits of an n-bit code with single-digit adders of subgroups, any combination of units in the code leads to the appearance of at least one unit at the outputs of A. or B with 1 4 1: t , moreover, for all I with 1 1 i N, i.e. and the outputs of A. or B. And at the outputs of the terminal t-bit adder 3, the zero result would be. is possible only when the adder overflows, but in this case the transfer unit is added, coming from adder 4.

The proposed device, in contrast to the known, uniquely forms the q code as a zero balance. for non-zero codes that are multiples of the module: q 2 -1, which allows to increase

31325484

Claims (1)

control efficiency In addition, (p-1) -th group, inputs –and subgroups for zero codes are formed by zero-one-bit adders (2 i ha) of the residual code, which can also be Q-th group connected to the outputs of the sums used to increase the effective - one-bit adders of the I-stack of controls. group (d-1) -th group,. k () input code bits - and the formula of the invention of the subgroup of one-digit adders A device for convolution modulo (C-O-th group (round to q 2 -1, containing N groups one-time integer down) and to output adders from m subgroups into single-digit transfer divisors, wires (-1) -th subgroup (p-1) -th group h each group (j) 2--, where n - razn, quantity the number of the rolled-up number and the first outputs of the one-digit adders the i-th new g-bit adder, and the group-15 subgroups of the N-th group are two), you are n - i + 1, the course of the sum of a one-bit adder pa from K --- inputs of the 1st sub-subgroup and the output of the transfer of the one group (1 i t) of the first group of the one (one accumulator of the third subgroup of the standard accumulators is the group of the Nth group connected to the first bits) the device inputs for connecting with 20 dami of the first and second, respectively, to the outputs of the collapsible number of components of the first t-bit sum the mass, m outputs of the sum of the first t-torus, -e bits of the first and second bit adders are output-summands of the first t-bit sums of the device, each i-subgroup of the torus are connected respectively to the first group of one-bit 25 summers of the adder and subgroups (1 41 N) contain Kf / 3 (round the Nth group and transfer the output of one to the whole down) of the one-bit adder (-1) adders, where K. are the number groups of the K-th group, which differs in the inputs of the i-th subgroup of one-bit digits e so that Adders of the 1st group, the inputs of the first 30 control validity, the second t-bit adder, the Q-th group (2 4 QN) are connected to the inputs of the first and second components to the outputs of the one-digit adders second, respectively, connected to the first subgroup (p-1) -th group, k (by the inputs of the first and second terms (/ 3) discharge the input code from the first o-bit adder, the input of the first subgroup (p-1) -th group ( the transfer of which is connected to the output of / 3) - to round up to a whole into a smaller transfer of t-bit sum-side) and to the outputs of transfers of the single, whose transfer input of the subcluster adders of the m-th subgroup of the check to the bus of zero potential. Editor V. Petrash Compiled by I.Ivanykin Tehred L.Sertsyukova Proofreader V. But ha Order 3111/45 Edition 672 Subscription VNIIPI USSR State Committee for inventions and discoveries 113035, Moscow, Zh-35, Raushsk nab., 4/5 Production and printing company, Uzhgorod, st. Project, 4 Fie.2