US 4,949,294 AGrant
Computation Circuit Using Residual Arithmetic
Issue Date:1990-08-14
•7 Claims
•8 Drawing Sheets
Abstract
A computing circuit using residual arithmetic, particularly on complex numbers. The computation circuit uses residual notation. In residual notation, the computations can be done independently on each digit. It is therefore advantageous to perform the computations simultaneously on all the digits. Advantageously, the arithmetic is built on a unitary commutative ring for which the number 1 is not a quadratic residue. In this case, it is possible to perform a complex multiplication by adding two indices. The embodiment of the invention takes the form of a computer, electronic card or integrated circuit.
Metadata
Assignee
- Thomson-CSF
Inventor
- Claude Wambergue
Application Information
Application Number:US 2642441
Filing Date:1988-10-28
Priority Date:1987-10-30
Art Unit:231
Classifications
IPC:
G06F 738
Field of Search:
364746;754;746.1
Patent Drawings (8 sheets)
Description
Background of the Invention
1. Field of the Invention
The invention is chiefly a computation circuit or computer using a residual arithmetic, especially on complex numbers.
2. Description of the Prior Art
There are known methods for making computation circuits using positional notation bases. In a base of this type, any whole number is factorized in a single way on the base elements which are generally the successive powers of a whole number. Any whole number A may be written in a base b in the form:
There is a one-to-one correspondence between the numbers and the sets of coefficients a.sub.i of their factorization in a given base.
For technological reasons, computation circuits using semiconductor components use mainly the base 2.
Residual arithmetic is known and has been described, in particular, in H. L. Garner, "The Residue Number System", IRE Trans. Elect. Comp., June 1959.
The device according to the present invention uses residual arithmetic to perform computations. In the device according to the invention, the residual arithmetic is adapted and optimized to perform computations and, especially, complex multiplications. Through the choices made in building the most efficient device according to the invention, a complex multiplication amounts to the addition of two whole numbers.
To perform the desired computations, the device according to the present invention converts the data of the positional base into a residual base, performs the operations and reconverts the results into the desired positional notation.
Furthermore, the residual notation enables the performance of computations independently on each digit without any spread of carried-over values. Thus, the device according to the present invention performs computations simultaneously on all the digits.
Summary of the Invention
A main object of the invention is a computation device comprising an encoding module capable of encoding numbers in residual notation, a computation module capable of performing computations in residual notation, and a decoding module capable of transcoding numbers from the residual notation into a desired notation.
Another object of the invention is a computing device wherein, in the notation used, the residues are computed modulo the numbers m.sub.i of the form m.sub.i =4k+3 where k is a whole number.
Another object of the invention is a device wherein the computation module has means used to associate, with each complex number, an index such that a multiplication of two complex numbers corresponds biuniquely to an addition of said indices.
Another object of the invention is a computing device comprising a control module capable of modifying the exchanges of external and internal data of said computing device as well as the computations performed by the computing module.
Another object of the invention is a computing device with a control module having a bus capable of giving it the instructions needed for the desired sequencing of the computations.
Another object of the invention is a computing device comprising buses capable of connecting the computing module to internal or external memories capable of containing numbers written in residual notation.
Another object of the invention is a computing device wherein the computing module is connected by a bus to a read-only memory.
Another object of the invention is a computing device wherein said device is capable of performing convolutions.
Another object of the invention is a computing device comprising read-only memories in which tabulated functions are stored.
Another object of the invention is a device capable of performing correlations.
Another object of the invention is a device comprising read-only memories in which tabulated functions are stored.
Another object of the invention is a device wherein the encoding and/or decoding modules comprise data paths used to perform the addition of the carried-over value at the end of the computation on each digit of the transcoding operation.
Another object of the invention is a device made in the form of an electronic card.
Another object of the invention is a computing device made in the form of an integrated circuit.
Brief Description of the Drawings
The invention will be better understood from the following description and the figures, appended as non-restrictive examples, of which:
FIG. 1 is a diagram of the first alternative embodiment of the device according to the invention;
FIG. 2 is a diagram of a second alternative embodiment of the device according to the invention;
FIG. 3 is a diagram of a third alternative embodiment of the device according to the invention;
FIG. 4 is a fourth exemplary embodiment of the device according to the invention;
FIG. 5 is a diagram of a detail of the embodiment of the devices according to the invention;
FIG. 6 is a diagram of a detail of the embodiment of the device shown in FIG. 5;
FIG. 7 is a diagram of the devices according to the invention;
FIG. 8 is a diagram of a prior art principle implemented in the device according to the invention;
FIG. 9 is a diagram of a detail of an embodiment of the device according to the invention;
FIG. 10 is a diagram of a detail of an embodiment of the device according to the invention;
FIG. 11 is a diagram of a detail of an embodiment of the device according to the invention.
In FIGS. 1 to 11, the same references are used to designate the same elements.
Description of Preferred Embodiments
We shall now recall notations and definitions commonly used in mathematics.
It is taken that Z, the set of rational whole numbers, is an ordered set.
Let us define the division of whole numbers known as Euclidian division.
Let a and b be two whole numbers where b is a positive whole number. The division of a by b is defined by:
where q is the quotient and r is the remainder.
When r is null, b and q are factors or divisors of a, and b is said to divide a. When there are no other divisors other than 1 and a, a is a prime number. In all other cases, a is a composite number.
The greatest positive whole number d which divides two whole numbers a and b is called the PGCD of a and b, marked d=(a, b).
The fundamental theorem of arithmetic stipulates that any number can be factorized into a product of powers of whole numbers. ##EQU1## where c.sub.i is a whole number, and that this factorization is unique.
When two numbers a and b have no common factors other than 1, they are said to be relatively prime numbers:
Let us define congruence and residues.
The division of a whole number a by a whole number b produces a remainder r.
All whole numbers which give the same remainder when they are divided by b may be considered to belong to the same class of equivalence for the equivalence relation:
Two whole numbers, a.sub.1 and a.sub.2, belonging to the same class are said to be congruent modulo b and the equivalence is written:
In fact, we are concerned only with the remainder r of the division of a by b, and this remainder is called the residue of a modulo b, written r.ident.a modulo b.
With congruences, the division is not defined. However, it is possible to define something that approaches it by considering the congruence:
It is shown that x exists only if d divides c where d is the PGCD of a and b.
In particular, if a and b are relatively prime numbers (d=1), the congruence:
has a solution, and x is called the converse of:
When the PGCD of a and b equals 1, a is said to be a quadratic residue of b if:
allows a solution. If this congruence has no solution, a is a quadratic non-residue of b.
Let us define groups:
Let A be a set of elements a, b, c . . .
Let us assume that the elements are related by the operation (or binary relation), T:
Thus, any set A is called a group if it fulfils the following conditions:
associativity: Va, b.epsilon.A,
identity: e.epsilon.A,
converse: Va.epsilon.A, a.epsilon.A,
When the operation T is commutative, (a T b=b T a, Va, b.epsilon.A), the group is called an Abelian group. The order of a group is the number of elements of this group.
Let us define cyclic groups:
Consider a finite group (having a finite number of elements) and the successive operations:
Each of these operations produces an element of the group. Since this group is finite, the sequence will necessarily repeat itself with a period r.
r is called the order of the element a.
If the order of an element g is the same as the order of the group, all the elements of the group are generated by g with the operations:
In this case, g is called a generating element of the group. The group is a cyclic group.
Let us define a ring and a field:
A set A is a ring for the two operations T and o if the following conditions are met:
A is an Abelian group for the law T:
if c=a o b, V a and b.epsilon.A, then c.epsilon.A;
associativity: a o (b o c)=(a o b) o c;
distributivity: a o (b T c)=(a o b) T (a o c) and (b T c) o a=(b o a) T (c o a).
The ring is commutative if the law o is commutative. The ring is a unitary ring if there is one (and only one) identity element u for the law o.
It is easily ascertained that the set of whole numbers is a ring with respect to addition and multiplication.
If we add the condition that every element a has one (and only one) converse a, (a o a=u), then the unitary ring becomes a field.
It is easily ascertained that, for any whole prime number p, the set of whole numbers (0, 1, 2, . . . , p-1) constitutes a field for addition and multiplication modulo p.
Any finite field is called a Galois field marked GF(p).
It can be shown that, in any Galois field, there are g primitive roots (or generating elements) which generate all the elements of the field (except e) by the successive operations: g o g, g o g o g, . . .
Let K be a commutative field. It is said that L is an extension of K, if L is an extension field of K (namely a field for which K is a subfield) for which every element is a root of an equation of a fixed degree n with coefficients in K. n is the degree of L with respect to K.
For example, the field of complex numbers C is a degree 2 extension field of the field of real numbers R for any complex number Z=a+ib is the root of a second degree equation with real coefficients.
When K is a finite body GF (p) the order d extensions of GF(p) are written: GF (p.sup.d). These fields have a number of elements equal to p.sup.d, where p is a prime number and d is a positive whole number.
Let us define the ideal of a ring.
An ideal I of a commutative ring A is a sub-ring of A such that if we take any element y of I and any element a of A, the element a.y still belongs to I.
Let A be a unitary commutative ring. The subset of A, formed from multiples of an arbitrary element of A, is called the principal ideal of A. A ring having only principal ideals is called a principal ring.
The intersection of two ideals contains at least one null element (e) and is still an ideal.
The sum of two ideals is one ideal.
The product of two principal ideals I (a) and I (b) is the principal ideal I (a.b).
Two ideals are said to be comaximal or relatively prime numbers if their sum is the ring itself.
A non-trivial ideal (different from {e} or (A) is a maximal or an absolute prime or a prime ideal, if it is not contained in any ideal other than the ring A itself.
The product of two prime ideals is their intersection.
Given an ideal I in a commutative ring A and an element x of A, the set of elements of the form y=x where y is any element of I is called the coset of I, characterized by x.
If two cosets have an element in common, they coincide. This means that each element of A belongs to one and only one coset of I. The sum and the product of two cosets both belong to one and the same coset called the sum or product of two cosets. The cosets of the ideal I, with reference to these sum and product operations, constitute a ring which is called the quotient ring of A with respect to the ideal I, written A/I. For an ideal I to be maximal, it is necessary and sufficient for the ring quotient A/I to be a body.
Morphisms are the applications between structures.
The study of any algebraic structure includes that of the morphisms for this structure.
The term morphism (or homomorphism) implies an application of one set in another which preserves the "form", namely is compatible with the structures. Thus, there are morphisms among groups, rings, vector spaces, algebras, modules etc.
The definition of morphism is extended to include the case of sets provided with algebraic structures: let E and F be two sets provided with algebraic structures (S) and (T). The following are taken as being given: an application associating an internal law T relative to (T) with each internal law .perp. relative to (S) and an application associating an external law on F with each external law on E. These two laws have the same operator set, the applications considered being bijective. It is said then that an application f of E in F is a morphism in relation to the structures (S) and (T) if, for each law on E, and for any pair (x, y) of elements of E,
and if, for each external law of E, of the operator set .OMEGA., and for every element (.alpha.,x), of .OMEGA..times.E.
A bijective morphism of E on F is an isomorphism: the properties of E are "transported" to F (and reciprocally).
Let us define the bases of a vector space.
Let E be a vector space defined on a commutative body K and (a.sub.i), i=1, . . . , n a family of vectors of E. This family is a base of E if it is free and generating which amounts to saying that any vector a of E is written uniquely:
The definition of a base is closely related to the notion of a sum and a direct sum of vector sub-spaces.
It is said that this sum E.sub.1 +E.sub.2 of two vector sub-spaces E.sub.1 and E.sub.2 of E is direct, and it is written E.sub.1 +E.sub.2 if, for any vector of this sum, the factorization of:
x=x.sub.1 +x.sub.2, x.sub.1 .epsilon.E.sub.1, x.sub.2 .epsilon.E.sub.2 is unique.
The value of the notion of the base appears in the following result:
let E and F be two vector spaces on K, B=(e.sub.j) j=1, . . . , n
a base of E, and (y.sub.j), j=1, 2 . . . , n
a group of elements of F. There is then one and only one linear application f of E such that for all j=1, 2, . . . n.
f(e.sub.j)=y.sub.j.
If, moreover, F is provided with a base C=(g.sub.i), i=1, 2, . . . k, the vectors y.sub.j can be defined by their components in the base C: ##EQU2##
Thus, a linear application is defined by the datum of the family .alpha..sub.ij, for i=1, 2, . . . , k and j=1, 2, . . . , n.
This is the principle of matrix computation.
Let us define an algebra on a commutative field.
This frequently encountered algebraic structure is closely related to the notion of vector space.
Let K be a commutative field. The term algebra on K designates a vector space E on K provided with a bilinear application of E.times.E in E. Since an application of E.times.E in E is what is called an internal law of composition, the set E is therefore provided with an algebraic structure defined by the given facts of three laws of composition:
an internal law of composition, the application of E.times.E in E, written +;
a second internal law of composition, the application of E.times.E in E, written (x,y).fwdarw.xy;
an external law of composition, the application of K.times.E in E written (.alpha., x).fwdarw..alpha.x).
These three laws meet the following conditions:
provided with the first and third relationship, E is a vector space on K;
for any triplet (x, y, z) of elements of E,
for any pair (x,y) of elements of E and for any pair (.alpha., .beta.) of elements of K.
The definitions relating to vector spaces apply, of course, to algebras. Furthermore, certain properties are related to the second internal law of composition. Thus, an algebra is commutative or associative if the multiplication is so. The algebra is unitary if the multiplication allows a neutral element.
An associated algebra may be considered as a ring (for both internal laws of composition).
Let us define the modules and algebras on a unitary commutative ring.
We shall now go from the notion of vector space to that of the modulus in simply replacing the commutative field K by a unitary commutative ring A. The essential value of this extension is that any unitary commutative ring may be considered to be a modulus on itself. Similarly, any commutative group may be considered to be a modulus on the ring Z of rational whole numbers. Thus, the methods of linear algebra apply to the theory of groups and to the theory of rings.
Equally, the notion of algebra on a commutative body can be extended to that as algebra defined on a unitary commutative ring.
The theory of moduli diverges appreciably from that of vector spaces, for certain theorems of existence may be shown to be at fault. This comes from the fact that a part reduced to a non-null element is not necessarily free.
It is said that a modulus is free if it has at least one base.
It is possible to represent any number in residual notation by using the Chinese remainder theorem.
Let m.sub.1 m.sub.2, . . . m.sub.k be whole numbers which are relatively prime two by two:
Then the system of linear congruences:
has a unique solution x modulo q, given by: ##EQU3## and where M.sub.i.sup.-1 uniquely (modulo m.sub.i) meets the congruence:
Representation of numbers:
The Chinese remainder theorem thus formulated warrants the existence of a one-to-one correspondence between the one-dimensional representation of a whole number x, and the multi-dimensional representation which forms its residual expression (x.sub.1, x.sub.2, . . . , x.sub.k):
However, the residual notation can hardly be exploited when a number is to be interpreted or its sign is to be tested, or, again, it has to be compared with another number.
Let us define the combined base positional notation: ##EQU4## With: 0.ltoreq..sub.i <b.sub.i for any i.
This notation is used especially when working with whole numbers.
Thus, for the example envisaged, in assuming: ##EQU5##
It can also be ascertained that this notation is unique and ordered.
Thus, in the device according to the invention, the numbers of the positional notation are converted into residual notation. The desired additions, subtractions and multiplications are made, and then the results are converted into positional notation or combined base notation for display and/or for their later use. It is advantageous to perform a maximum number of operations before the conversion to limit the number of conversions needed to perform a given computation.
The remarkable property of the residual notation comes from the fact that the addition and multiplication operations are performed independently on each digit (residue). ##EQU6##
Take x, y for which we adopt the following residual notation: ##EQU7## x.sub.1 being the residue modulo m.sub.1, x.sub.2 being the residue modulo m.sub.2 and x.sub.k being the residue modulo m.sub.k. ##EQU8## But it is possible to write, for any i:
And hence: ##EQU9## since, by definition, q=m.sub.j.M.sub.i. ##EQU10## where
where K' is a constant.
Furthermore, it is possible to write:
Then, ##EQU12## and since q=m.sub.i.M.sub.i, we get: ##EQU13## where K is a constant. ##EQU14## where
(we might note that uniqueness implies 0.ltoreq.x, y, z, t<q).
Hence
It is observed that there is no carry over in residual arithmetic and this is the major contrast with standard traditional arithmetic. For, it is well known that, in this latter representation, the adding and multiplication operations cannot be done separately on each digit since a major piece of information, the carryover, should be transmitted from digit to digit from the less significant value to the more significant value.
Advantageously, a complex arithmetic is defined on a ring. In this case, in addition to the independence of the sum on each residue, the computations are simplified by the fact that a complex multiplication amounts to an index addition, namely, an addition of two whole numbers.
Until now, we have remained at the elementary level of the operations, in building appropriate arithmetics in the manner in which numbers are represented. We shall now use algebraic language and leave the operation level to make a closer examination of structural relationships between sets of numbers provided with laws of composition such as addition and multiplication.
Let R.sub.1, R.sub.2, . . . , R.sub.k be unitary commutative rings.
The direct sum (also called the Cartesian product) of R.sub.1, . . . , R.sub.k written: ##EQU15## is the set of k-uplets: ##EQU16## R constitutes a unitary commutative ring for the addition and multiplication operations component by component.
Let R be a finite, commutative and unitary ring.
R allows a unique factorization in direct sums of local rings.
A local ring is a unitary commutative ring which has one (and only one) maximal ideal M. In a local finite ring, M contains all the divisor elements of zero and the element zero.
The factorization into local rings is based on the Chinese remainder theorem which we can formulate thus:
Let Y be a unitary commutative ring and let A be an ideal of Y which can be factorized into a product of relatively prime ideals:
then, the quotient ring Y/A is isomorphous with the direct sum of local rings.
The ring of whole number residual cosets modulo q R(q), can be factorized into the direct sum: ##EQU17##
The factorization of a ring R into local finite rings takes place naturally when R is the homomorphic image of a ring I with respect to an ideal which can be factorized in a product of maximal ideals: this is the case, especially, when Y is the ring of whole numbers of a field of algebraic numbers.
A Dedekind domain has the property wherein every ideal can be factorized into a product of maximal ideals and, in fact, every non-null prime ideal is maximal (the ring is Noetherian): the ring of whole numbers of a field of algebraic numbers is a Dedekind domain and is Noetherian.
Take k whole numbers m.sub.1, m.sub.2, . . . mk for which (-1) is a quadratic non-residue.
Let ##EQU18## and let R (q) be the unitary commutative ring of whole numbers modulo q.
Then (-1) is a quadratic non-residue of q.
Let1 be a solution of x.sup.2 .ident.-1 found in R (q.sup.2), where:
Let us define the addition and multiplication operations in R(q.sup.2) by:
The set R(q.sup.2) consists of Gaussian whole numbers similar to the ordinary complex numbers with 1.sup.2 =-1.
Then, R(q.sup.2) is a commutative and unitary finite ring.
Take k prime whole numbers m.sub.1, m.sub.2, . . . m.sub.k, such that (-1) is a quadratic non-residue of each, and assume: ##EQU19##
Let R(q.sup.2)={a+1b, 0.ltoreq.a,b<q} be the ring defined above.
Then the direct sum of the Galois field:
where the addition and multiplication operations are defined by:
is a ring of q.sup.2 elements, isomorphous at the ring R(q.sup.2).
Every Galois field GF (m.sub.i.sup.n) has generating elements g generating all the elements of the field except the element 0 by successive multiplication operations:
The set {0, 1, 2, . . . m.sub.i.sup.2 -2} provided with the addition modulo (m.sup.2.sub.i -1) is an Abelian group, isomorphous with the cyclic group [GF(m.sub.i.sup.2)-{o+10}] generated by g with the multiplicative law.
Thus, we see that a judicious choice of the whole number q can be used to build diverse algebraic structures on the ring R(q) provided with very valuable properties which can be transposed by isomorphism:
the ring R(q.sup.2) considered as an algebra defined on R(q) (or as a modulus on R(q)), has an orthogonal base enabling component-by-component operation on the elements of R(q.sup.2) expressed in this canonical base.
Through the isomorphism between the group of indices and the cyclic group of the Galois field GF(m.sub.i.sup.2), there is remarkably simple means available to perform a complex multiplication in a single operation of real addition on the indices of the elements;
the ring R(q), considered as an algebra (or a modulus) on itself, also has an orthogonal basis. Consequently, the elements of R(q), which are also the real and imaginary components of complex whole numbers of R(q.sup.2) can be factorized on this basis and can be worked separately by component.
In an algebra defined on a field (or a vector space on a field), the associated bases all have the same dimensions. This is no longer true with an algebra or a modulus defined on a ring. A modulus is free if it has a basis. In the case of R(q) and R(q.sup.2), there is at least one base (the algebraic interpretation of the Chinese remainder theorem). In particular, for R(q), the standard formulation of the theorem gives the orthogonal canonic base (b.sub.i =M.sub.i M.sub.i.sup.-1). For: ##EQU20##
The positional notations, in base b (or in combined bases) define other bases which do not necessarily have the "dimension" k.
A problem of processing on complex data, where the real and imaginary parts are written in a non-orthogonal base (binary positional notation for the computer, and decimal notation for man) is conventionally performed without changing the base (the positional notation is kept). Consequently, it becomes necessary to use a heavy arithmetic with a spreading of carry-over.
The complex residual arithmetic proposed therefore consists in transposing the problem in an orthogonal base (residual notation) to benefit from the "orthogonal" arithmetic. We even go further than that in reducing the complex multiplication operation to an indices addition operation. Once the operation entails assessing the amplitude of a result or comparing results, the base is again changed to return to a positional notation (preferably one with combined bases, since it has the same dimension as the residual notation). Finally, an additional transcription is done in binary notation if this proves to be necessary.
To build a complex arithmetic on a ring, it is necessary to choose, as elements of the residual base, the numbers m.sub.i for which the number -1 is a quadratic non-residue. The numbers are given by the formula:
where k is a whole number.
FIG. 1 shows a first embodiment of a computer 7 according to the invention. The computer 7 has an encoding module 21, a computing module 1 and a decoding module 22. The encoding module 21 is connected to at least one data bus 33 and/or 34. The encoding module 21 is connected to the computing module 1 by at least one data bus 35 and/or 36. The computing module 1 is connected to the decoding module 22 by a data bus 33. The decoding module 22 is connected to a data bus 39.
The encoding module 21 receives successively, through a single bus, or simultaneously, through both buses 33 and 34, two items of digital data in positional notation.
The encoding module 21 converts the digital data from the positional notation into residual notation.
For example, the items of digital data are received in binary form by the encoding module 21 and are encoded in residual notation where the digits are encoded in binary form for technological reasons.
The computing module 1 receives successively, through a single bus, or simultaneously, through both buses 35 and 36, two items of digital data in positional notation. The computing module 1 performs, on both items of data, the computation for which it has been designed, for example, addition, subtraction or multiplication. In an alternative embodiment, the subtraction of a number is replaced by the addition of its opposite.
The decoding module 22 receives the result of the computation performed by the computing module 1 through the bus 33. This result is received in positional notation. The decoding module 22 converts this result of the computation in residual notation into a notation which can be more easily used, such as, for example, the combined base notation, binary notation, hexadecimal or decimal notation.
The result, having been made easy to use, is emitted on the bus 39.
Advantageously, the computing module is connected to a control bus 37. In this case, one and the same computing module 1 can be used depending on the command it receives through the bus 37, to perform an addition, a subtraction or a multiplication or even a division if this operation is possible in residual notation.
Advantageously, the computing module 7 is a pipeline device. At the k.sup.th clock cycle, the encoding module 21 performs a conversion of two order k data from the positional notation into residual notation, the computing module 1 performs an operation, for example, addition, on two order k-1 digital data while the decoding module 22 converts the order k-2 result from the residual notation into positional notation.
FIG. 2 shows a particularly efficient embodiment of the computing device according to the invention. This device is especially well suited to complex computations, sequences of computations as well as computations repeatedly using the same data. This type of computation is used notably in digital filtering.
The computing device of FIG. 2 comprises, in addition to the encoding module 21, the computing module 1 and the decoding module 22, a control module 6.
The control module 6 enables the successive execution of several computations using, for example, the same piece of data in residual notation several times or using the result of a computation as a piece of data for one of the following computations.
The computing device 7 according to the invention has means 41, 42, 382, 402, 403, used to provide a same piece of data several times to the computing module 1 without its being necessary to pass from the positional notation to the residual notation several times.
The computing device according to the invention comprises, for example, two memories 41 and 42 connected betwen the encoding module 21 and the computation module 1.
For example, the memory 41 receives data from the encoding module 21 through a bus 35 and sends data to the computing module 1 through a bus 31.
For example, the memory 42 receives data from the encoding module 21 through a bus 36 and sends data to the computing module 1 through a bus 32.
Advantageously, the results of computation by the computing module 1 can be given to the input of said computing module 1, for example, through a bus 380, a bus 378 and a bus 32.
Advantageously, the results of computation by the computation module 1 are capable of being given to the input of one of the memories 41, 42, for example, through the bus 380, a bus 360 and the bus 36.
Advantageously, the results of computation by the computing module 1 are capable of being given to a random access memory 403, for example, a memory external to the computing device 7, for example, through the bus 33, the bus 380 and the bus 381.
Advantageously, the digital data in residual notation are capable of being given to the computing module 1, for example, through a bus 381, the bus 378 and the bus 32 from a read-only memory 402 or the random-access memory 403.
In one exemplary embodiment of the device according to the invention, the read-only memory 402 is external to the computing device 7.
In a second exemplary embodiment, the read-only memory 402, included in the computing device 7, is a programmable read-only memory (PROM, EPROM or EEPROM).
Advantageously, the digital data in residual notation can be given to one of the memories 41 or 42 by the random-access memory 403 and/or the read-only memory 402, for example, through the bus 381, the bus 360 and the bus 36.
Advantageously, the digital data are capable of being given by the encoding module 21 to the random-access memory 403, for example, through the bus 36, the bus 360 and the bus 381.
Of course, no combination of data paths specified above goes beyond the scope of the present invention.
In a first exemplary embodiment, the memories 41 and 42 are buffer memories capable each of storing a piece of digital data in residual notation. Each new piece of data erases the old one.
In a second exemplary embodiment of the device according to the invention, the memories 41 and/or 42 are shift registers capable of storing n data simultaneously. In response to each control signal 60, the digital values stored are shifted by one rank, the rank n digital values being emitted to the bus 31 or 32.
Advantageously, upon a command 60 emitted by the control module 6, a digital value can be stored by means of the bus 61 in any of the shift registers comprising memory 41 and/or 42. For example, if it is desired to have, at one of the inputs of the computation module 1, a digital value in two computation cycles, said digital value is stored in the index register n-2 of the memory 41 or 42 connected to said input of the computing module 1.
In a third embodiment of the device according to the invention, the memories 41 and/or 42 are random-access memories (RAMs). The control module 6 controls and addresses the memories 41 and 42.
Advantageously, the decoding module 22 is connected to a buffer memory 43 by means of a bus 370. The buffer memory 43 enables the computation results to be given by means of a bus 39.
The read-only memory 402 is used to store coefficients which may be used during the computation. The coefficients are converted into residual notation only once, before the memory 402 is programmed.
The random-access memory 43 is used to store intermediate results and/or data which are liable to be used several times in residual notation. Furthermore, when the encoding module 21 is free, it is possible to store in residual notation, in the memory 403, as an when available, digital values coming, for example, from a data acquisition device (not shown) connected, for example, to the bus 34.
Advantageously, a memory 404 is connected by means of a bus 37 to the control module 6. The memory 404 can store instructions of the program enabling the computing device 7 be made to perform to the desired computations. The instructions stored in the memory 404 enable the control module 6 to shunt the flow of data, to perform activation tasks in reading or in writing and to give an address to the memories 41, 42, 402 and 403 and to control the operation to be executed by the computation module 1.
The memory 404 is, for example, addressed by a counter 600 by means of a bus 405. The counter 600 is, for example, included in the control module 6 memory.
The architecture of the control module 6 is adapted to the computations which it is desired that the device 7 should be capable of performing, and it is adapted to the modules 1, 21, 22, as well as the memories 41, 42, 402 and 403.
The control module is made in a known way. For example, it has sequencers. These sequencers are made in the form of programmable logic devices (PLD or EPLD) or micro-programmed logic devices.
Advantageously, the instructions of the program stored in the memory 404 are obtained from an appropriate assembler or compiler made in a known way.
For the clarity of the figures, the connection of the control lines 60 have not been shown.
FIG. 3 shows an alternative embodiment of the computing device 7. The alternative embodiment shown in FIG. 3 has simplified data paths.
In FIG. 3, the encoding module 21 is shown in the form of two devices 21, respectively charged with converting digital data in positional notation into digital data in residual notation on the buses 33 and 34.
The first of the two encoding devices 21 is connected by a bus 391 to the memory 41 and to a first input of the computing module 1.
The second of the two encoding devices 21 is connected by a bus 392 to the memory 42, the decoding module 22 and the second input of the computing module 1.
The bus 391 enables the first encoding device 21 to give data to the computing module 1 and/or to the memory 41 and also enables two-directional exchanges of data between the memory 41 and the computing module 1.
The bus 392 enables the second encoding device 21 to provide data to the computing module 1 and/or to the memory 42, two-directional exchanges of data between the memory 42 and the computing module 1 as well as the transmission of results of the computing module 1 to the decoding module 22.
The control module 6 supervises exchanges of data and the operations performed by the computing module 1.
FIG. 4 shows an especially efficient example of an embodiment of the computing device 7 as regards exchanges of data.
A first encoding device 21 is capable of receiving, through the bus 33, a first flow of data to be processed. The first device 21 is connected by the bus 35 to the memory 41. The memory 41 is connected by a bus 31 to a first input of the computing module 1. To the bus 31, there is connected, through a bus 385, a read-only memory 402. A second encoding device 21 is capable of receiving a second flow of data to be processed through the bus 34.
The second encoding device 21 is connected by a bus 36 to the memory 42. The memory 42 is connected by a bus 32 to a second input of the computing module 1. The output of the computing module 1 is connected by the bus 33 to the decoding module 22. The decoding module 22 is connected by the bus 370 to the buffer memory 43. The buffer memory 43 is connected to a bus 39.
A bus 380 connects the bus 33 to the bus 32 and to the memory 42.
A bus 383 connects a random-access memory 403 to the bus 380 bidirectionally.
A bus 384 connects bus 36 to the bus 380 and to the bus 383.
The computing device 7, shown in FIG. 4, enables simultaneous exchanges of data, notably between:
the output of the computing module 1 and the second input of the computing module 1 through the buses 33, 380 and 32, and between the encoding device 21 and the random-access memory 403 through the buses 36, 384 and 383;
the output of the computing module 1 and the second input of the computing module 1 through the buses 33, 380 and 32 and between the encoding device 21 and the memory 42 through the bus 36;
the output of the computing module 1 and the second input of the computing module 1 through the buses 33, 380 and 32 and between the random-access memory 403 and the memory 42 through the buses 383, 384 and 36;
the output of the computing module 1 and the decoding module 22 and the various exchanges among the encoding devices 21, the memory 42 and the memory 403.
The possibilities of exchanging data supervised by the control module 6 first enable the use of an encoding device 21 to convert, as and when they become available, digital data in positional notation coming, for example, from a data acquisition device through the bus 34, into digital data in residual notation, and further enables their storage in the random-access memory 403. Second they enable the computing device 7 to directly perform complex computations which are highly useful in digital filtering such as, for example, in convolution computation, correlation computations or weighting computations. The computations are supervised by the module 6 in performing a suitable program stored in the program memory 404.
In an alternative embodiment of the device according to the invention (not shown), the computing device has means to transcode the residual notation into a notation with combined bases (and vice versa) as well as comparators. The transcoding to a combined base (and vice versa) is easier than transcoding between residual notation and positional notation. For, when transcoding in combined base notation, the spatial dimension used is preserved. The combined base notation enables comparison. Thus, during a computation, it is possible to ascertain that a number is greater than another number or that it is below a given threshold. For the remaining computations, the number tested is transcoded in residual notation.
Advantageously, the number tested is stored in a random-access memory before being transcoded. In the rest of the computations, the value which had been stored is used.
FIG. 5 shows an exemplary embodiment of the computing module 1 of FIGS. 1 to 4. The computing module 1 uses the fact that, in a residual arithmetic, the computations can be performed independently on each digit, without any spreading of carry-over values. Thus, the computing module 1 has several elementary computers 11 capable of performing a computation on a digit in residual notation.
The computation module 1 is connected to two buses 31 and 32. Inside the computation module 1, each of the said buses is divided in order to give elementary computer 11 the desired digit. Each elementary computer 11 receives two digits.
In a first embodiment of the device according to the invention, each elementary computer 11 can perform a single type of operation, for example, multiplication.
Advantageously, the elementary computers 11 are capable of performing the desired operation on receiving a command on lines 60 from the control module 6. For example, the elementary computers 11 are capable of performing, on command, an addition, a subtraction or a multiplication.
Each elementary computer 11 gives the bus 33 the result of the computation made.
In an alternative embodiment, the elementary computer 11 has combinational logic circuits capable of performing the desired computations.
Advantageously, inasmuch as the computations are done independently on each digit, the results of each operation are tabulated. It is possible, in residual arithmetic, to obtain a wide range (on each digit) while, at the same time, using read-only memories of standard capacity, for example, ROMs with 14 address bits.
An example of an elementary computer using tabulated functions is used in FIG. 5, the principle of the computation using tables stored in the read-only memory being shown in FIG. 8.
Each elementary computer 11 performs the computations separately on a digit.
The computation module 1 has a number of elementary computers 11 which is sufficient to enable the processing of all the digits of the greatest numbers in which it is sought to make computations.
Table 1 gives an example of a computation module 1 comprising 16 elementary processors. These 16 elementary processors can be made by using ROMs with 14 address bits. The numbers m.sub.i of the table I have the form m.sub.i =4k+1 where k is a positive whole number.
It is clear that a computing module 1 having a greater number of elementary computers 11 is not beyond the scope of the present invention.
Depending on the range of the problem considered, an appropriate modulus will be chosen: ##EQU21##
To ensure the uniqueness of the result, each of its components should be smaller than q, thus imposing constraints on the range of data.
FIG. 6 shows an exemplary embodiment of an elementary computer 11 capable of performing, on a command from lines 60 from the control module 6, a multiplication, addition or subtraction.
A multiplication consists of an association, with each digit of an order index in the group GF (m.sub.i.sup.2) and in a summation of the indices obtained.
To obtain the result of a multiplication, it then suffices to convert the index into the number associated with it.
Advantageously, the index association is tabulated in a read-only memory 57.
The adder 55 is a modulo m.sub.i.sup.2 -1 adder.
Advantageously, one and the same adder 55 is used to do the "adding" operation and to add the indices during a multiplication.
Advantageously, the addition is tabulated in a read-only memory of the adder 55.
However, when the addition modulo m.sub.i.sup.2 -1 is performed, it is important to deduct m.sub.i.sup.2 -1 from the result so long as this result is greater than or equal to m.sub.i.sup.2 -1.
The example of the modulo 8 addition is given in Table III.
An example of a modulo m.sup.2.sub.i=3 -1, namely 11.sup.2 -1=120 is shown in FIG. 7.
Advantageously, the buses 31, 313, 314, 315, 316, 32, 323, 324, 325, 326 and 33 are capable of parallel transmission of both components, namely the real component and the imaginary component, of a digit.
The bus 31 is connected first to a bus 313, and second to a bus 314.
The bus 32 is connected first to a bus 323 and second to a bus 324.
The buses 313 and 323 constitute the address buses of a read-only memory 57. The read-only memory 57 comprises the tabulated indices to be associated in GF(m.sub.i.sup.2) with a complex number with a view to its multiplication by another complex number.
An example of indexing is given by Table II for the first three elementary computers 11. For each computer, the table is arranged in the rising order of numbers and then in the rising order of indices.
Re signifies: real part.
Im signifies: imaginary part.
The element (0+10) is given an index *, for it does not belong to the cyclic group and must be processed separately. A simple logic test device makes it possible to grasp the multiplication by the absorbent element (0+10), the result of which is, of course, this same null element (0+10).
FIG. 7 shows an embodiment of a modulo 120 adder. The modulo 120 comprises an adder 551 on seven bits and a table 557. The adder 551 receives the number to be added, for example on seven bits, through two buses 33. The adder 551 has seven result output lines with significance values of 0 to 6 as well as R, with the line R spreading the carry-over. The lines with significance values of 3 to 6 as well as the carry-over are connected to the input of the 2.sup.5 .times.4 byte table. The results are present on the lines with significance values of 0 to 2, directly coming from the adder 551, and on the lines with significance values 3 to 6, coming from the table 557.
FIG. 8 shows the principle of computation, by tabulation, of a function used in the device according to the invention. Two data buses 321 and 322 form the address bus 33 of a read-only memory 57. The desired function, for example, the addition or subtraction, is tabulated in the memory 57. The result of the operation is emitted by the read-only memory 57 on the data bus 323.
Some examples of tabulated operations, which can be implemented, are given in the tables III to VI.
Table III contains the modulo 8 addition.
Table IV contains the modulo 3 addition.
Table V contains the modulo 7 addition.
Table VI contains the modulo 11 addition.
To make the tabulated transcodings, a single data bus 333 is used. The value to be transcoded is present at the bus 33. The desired transcoding value is stored in the read-only memory 57 at the address equal to the value to be transcoded.
Table 7 gives the transcoding values for the first three Galois groups.
The use of the tabulation is, however, restricted by the size of the read-only memories available.
To have numbers in positional notation again, it is possible to formalize what happens in the base changing operation, independently of the manner in which it will be achieved.
Let: (bj) be the orthogonal base of the module R(Q) where ##EQU22##
(bi), a non-orthogonal base of the module R(Q) where:
(q1), another non-orthogonal base, that of the combined bases: ##EQU23## and q.sub.1 =1.
Any element of R(q) therefore allows a single factorization in these bases. ##EQU24##
The conversion of the coordinates (the change of the base) is done by writing the old base in terms of the new one and then in substituting these expressions in the old factorization.
In a first case, the (bi) base positional notation is transcoded into the (bj) base residual notation: ##EQU25## By the Chinese remainder theorem, we get: ##EQU26##
The unique writing of x in base (g.sub.j) lays down:
And therefore, we write:
Since the transfer of the carry-over value is unnecessary in base (b.sub.j), therefore: ##EQU27##
If the digits c.sub.i are bits (b=2), then the transcoding of the binary notation into decimal notation amounts to a sequence of additions of terms .alpha..sub.ij modulo m.sub.j. For ranges which allow it, for example, for n=13, it is advantageous to tabulate the transcoding from the code c.sub.i.
It is always possible to do the transcoding by using modulo m.sub.j adders.
In a second case, the base (b.sub.j) residual notation is transcoded into base (q.sub.1) positional notation with combined bases.
This is the transcoding most used for residual arithmetic and the one which will be used during processing in order to compare intermediate results, for example, because it uses only modulo mj operators.HERE ##EQU28##
Now, the unicity of the writing in x lays down:
Consequently:
Only the arithmetic associated with the positional notation requires the transfer of a carry-over value from one digit to the other. The algorithm therefore takes the following form: ##EQU29##
The transcoding therefore uses the modular arithmetic (modulo m.sub.j) but must preserve the carry-over information to make it go successively to the following digit.
The transcoding algorithm proposed by Szabo can be broken down as follows:
First iteration:
a.sub.1 is deducted from the two members of the above equation. But it is known that it is possible to operate on each residual digit independently,
Now x.sub.1 -a.sub.1 =0.
The right-hand member of the equation can be divided by m.sub.1 since each product a.sub.1.q.sub.1 contains it, and for the left-hand member, since m.sub.1 is relatively prime with m.sub.j, j.noteq.1, the converse of m.sub.1 exists modulo m.sub.j, j.noteq.1; let it be written as m.sub.1j.sup.-1, j.noteq.1.
Then we obtain:
This equation taken modulo m.sub.2, gives:
Second iteration:
The same process is started again by deducting a2 on either side of the equation:
A division by m.sub.2 is done at the right-hand and a multiplication is done at the left-hand by the converse of m.sub.2 mod.m.sub.j, j.noteq.2:
The equation modulo m.sub.3, gives:
And so on until a.sub.k is obtained.
The algorithm requires (k-1) iterations, but suffers from a dependence among the residues at each iteration because the digit a.sub.1, just found, must be transmitted to the other residues in order to subtract it.
FIG. 9 shows an example of an encoding module 21, using Szabo's algorithm. The module 21 has k lines 81 to 8k, capable of giving the digits to be processed. The first line 81 is connected, first, to a line 811 giving a first result Q.sub.1 and, second, to first inputs of k-1 subtractors/multipliers 59. The lines 82 to 8k are connected to second inputs of subtractors/multipliers 59.
The output of the multiplier/subtractor connected to the line 82 is connected, first, to a line 812 capable of giving a second result Q.sub.2 and, second, to first inputs of k-2 subtractors/multipliers 59.
This interconnection is repeated until a final stage comprising only one subtractor/multiplier 59 is reached, the output of which is connected to a line 81k.
FIG. 10 shows a transcoding module 21 or 22 in which the transfer of the carry-over is postponed to the end. Thus, by a parallel architecture, the transcoding module 21 or 22 uses the independence of the results on each digit to reduce the computing time.
We have seen earlier that the conversion comprises two steps:
computation of a'.sub.1 : with: ##EQU31## shaping: (a'.sub.1).fwdarw.(a.sub.1) during which the remainder is transmitted to the following digit.
It is easy to set up the following relationships: ##EQU32##
In view of the complex arithmetic without multiplication performed until now, there is an advantage in not performing the operations indicated. Moreover, the carry-over has to be preserved.
The new method is based on the following observation:
It is possible to memorize the combined base code of: ##EQU33## which would be thus addressed by x.sub.j. In doing so, the large carry-over value associated with the multiplication is avoided. ##EQU34##
The algorithm is then simplified: ##EQU35##
The task that remains is that of performing additions with carry-over and to transmit the carry-over to the following digit. Now, it is clear that the carry-over information of the term a.sub.1, to be transmitted, is available before the end of the computation of the term a'.sub.1+1, and that this carry-over value is small.
The transcoding module 21 or 22 has k input lines 81 to 8k capable of spreading the digits x.sub.1 to x.sub.k to be transcoded. The input line is connected to k read-only memories 57. The input line 82 is connected to k-1 read-only memories 57. The input line 83 is connected to k-2 read-only memories 57. The number of read-only memories decreases by one unit at each new input line. The input line 8k is connected to a single read-only memory 57.
The first read-only memory 57, connected to the input line 81, is connected to the output line 811 capable of giving a transcoded digit a.sub.1.
The second read-only memory 57, connected to the input line 81, is connected to a first input of an adder 55, performing the modulo m.sub.2 addition with carry-over.
The third read-only memory 57, connected to the input line 81, is connected to one of the four inputs of an adder 55 performing the modulo m.sub.3 addition with carry-over.
The fourth read-only memory 57, connected to the input line 81, is connected to one of the five inputs of an adder 55 performing the modulo m.sub.4 addition with carry-over.
This is continued until the k.sup.th read-only memory 57, connected to the input line 81 and connected to one of the k-1 inputs of an adder 55 performing the modulo m.sub.k addition.
The carry-over of the modulo m.sub.2 adder 55 is connected to one of the inputs of the modulo m.sub.3 adder 55.
The carry-over of the modulo m.sub.3 adder 55 is connected to one of the inputs of the modulo m.sub.4 adder 55.
This continues until the carry-over of the modulo m.sub.k-1 adder 55, which is connected to one of the inputs of the modulo m.sub.k adder 55.
A first read-only memory 57 connected to the input line 82 is connected to an input of the modulo m.sub.2 adder 55.
A second read-only memory 57 connected to the input line 82 is connected to one of the inputs of the modulo m.sub.3 adder 55.
This is continued until the k.sup.th read-only memory 57, connected to the input line 82, is connected to one of the inputs of the modulo m.sub.k adder 55.
The read-only memories 57, connected to the i.sup.th input line (8i) are connected to the adder 55, performing the modulo m.sub.i addition up to the adder 55 performing the modulo m.sub.k addition.
The output lines 812 to 81k are respectively connected to the outputs of the modulo m.sub.2 to modulo m.sub.k adders 55.
In FIG. 10, the input values are marked x.sub.i, from x.sub.1 to x.sub.k ; the values obtained from a read-only memory are marked x'.sub.ij, from x'.sub.11 to x'.sub.kk, the carry-over values are marked r.sub.i from r.sub.2 to r.sub.k-1 ; the results are marked a.sub.i, from a.sub.1 to a.sub.k.
The modulo m.sub.i adders are, for example, made by tabulation.
Advantageously, for the transcoding, use is made of arborescent structured adders 55 in which the carry-over of the previous branch is added to the last stage of said adders. An example of a modulo m.sub.4 adder with an arborescent structure is shown in FIG. 11. FIG. 11 uses the same notation as FIG. 10.
The modulo m.sub.4 adder 550 of FIG. 11 has four elementary adders which are also marked 55.
Each elementary adder 55 receives two digits to be added and gives a result. The first two elementary adders 55 respectively receive x'.sub.14, x'.sub.24 and x'.sub.34, x'.sub.44. The third elementary adder 55 adds up the results of the first two elementary adders 55. The fourth elementary adder 55 adds the remainder r.sub.3 of the previous branch to the results obtained by the third elementary adder 55. The result a.sub.4 of the summation performed by the fourth elementary adder 55 is emitted on a line 814.
The total conversion time is reduced to the summation time a.sub.k, namely (1+[log 2(k=1)]) times the elementary addition period, where [x] signifies the whole number immediately greater than x.
The throughput rate is then determined by the converse of the longest period, between the period of a memory reading and the conversion period.
This method is, as can be seen, considerably faster than the classical Szabo method.
Transcoding: positional notation (q.sub.1) into base (b.sub.1) positional notation.
This conversion concerns only the final result to return, if desired, to standard positional notation: ##EQU36##
The conversion also implies the manipulation of a carry-over value but if the task is done in binary notation (which is what should happen most usually) .tau..sub.1i assumes the values 0 or 1, and the conversion requires only adders, of a maximum number of k per branch, with a maximum bits field of the order of log 2 q. Recomposition of Z=AX+BY in R(q.sup.2). The transcoding into base (q1) is given by table VIII.
The device according to the present invention is used to perform very fast digital computations. Depending on the type of computation needed, the device according to the invention will form a coprocessor of a standard computer, a computer comprising a front computer (not shown) or an entirely independent computer.
Thus, the device according to the invention can be made in various forms depending on the computing power desired and the technology used.
In a first embodiment, the device according to the invention has several electronic cards.
In a second embodiment, the device according to the invention is made in the form of a printed circuit.
In a third embodiment, the device according to the invention is made in the form of a printed circuit, for example, a circuit with very large scale integration (VLSI).
The invention advantageously has one or more fast circuits made of gallium arsenide.
The invention can be applied especially to digital computation.
The invention can be applied chiefly to the processing of signals and to digital filtering.
Claims
What is claimed is:
1. A computation device comprising: a numeral encoding module converting numbers from positional notation into residual notation on a ring so that a complex multiplication corresponds to an index addition; a computation module connected to the output of the number encoding module performing complex computations in residual notation using residual computed modulo the numbers m.sub.i of the form m.sup.i =4k+3, where k is a whole number, said module including means used to associate, with each complex number, an index, such that a multiplication of two complex numbers corresponds biuniquely to an addition of said complex number indices; and, a decoding module connected to the output of the computing module, converting numbers from residual notation into positional notation.
2. A computing device according to claim 1, comprising buses capable of connecting the computation module to internal or external memories containing numbers written in residual notation.
3. A computing device according to claim 2, wherein the computation module is connected by a bus to a read-only memory.
4. A computing device according to claim 1, wherein said device is capable of performing convolutions.
5. A computing device according to claim 1, capable of performing correlations.
6. A computing device according to claim 1, comprising read-only memories in which tabulated functions are stored.
7. A device according to claim 1, wherein the encoding and decoding modules comprise data paths used to perform the addition of carried-over values computed for each digit during encoding and decoding operations.
Patent Citations (4)
Non-Patent Literature (2)
- 1986 IEEE International Symposium on Circuits and Systems, San Jose, CA, May 5-7, 1986, vol. 1 of 3, pp. 117-120, IEEE, New York; M. A. Bayoumi, "Wafer Scale Integration for Generic RNS Structures".
- Nineteenth Asilomar Conference on Circuits, Systems & Computers, Nov. 6-8, 1985, Pacific Grove, CA, pp. 48-52, IEEE Computer Society Press, New York; M. A. Bayoumi, "Implementation of RNS Multiplication in VLSI".