Converter circuit for converting 1-redundant representation of an integer
View Patent ↗A fixed-point arithmetic unit comprises a plurality of full-adders and half-adders arranged in at least an input row and an output row. A plurality of inputs to the input row is arranged to receive bits comprising a sparse-redundant representation of the integer. A converter converts 1-redundant representations of the integer to the space (1/K)-redundant representations. A process is described to design rows of a multiplier by identifying a distribution of multiplication product groups, and transforming the distribution of multiplication product groups to adders to occupy a highest unoccupied row of the multiplier.
1. A converter circuit for converting a 1-redundant representation of an N-bit integer to a (1/K)-redundant representation in the form
2 N−1 y N−1 + . . . +4 y 2 +2 y 1 +y 0 +2 K z K +2 2K z 2K + . . . +2 [(N−1)/K]K z [(N−1)/K]K , where
y 0 , . . . y N−1 and z K , z 2K , . . . , z [(N−1)/K]K are sets of binary values, the converter circuit comprising:
a (K−1)-bit adder receiving (K−1) least significant bits of the 1-redundant representation, the (K−1)-bit adder providing a group of K least significant bits of the (1/K)-redundant representation, where K is an integer greater than 1 and less than N;
a K′-bit adder receiving K′ most significant bits of the 1-redundant representation, the K′-bit adder providing a group of K′+1 most significant bits of the (1/K)-redundant representation, wherein K′ is an integer not greater than K; and
at least one K-bit adder receiving a group of K bits of the 1-redundant representation between the K′ most significant bits and the K−1 least significant bits, each K-bit adder providing a group K+1 bits of the (1/K)-redundant representation between the group of most significant bits and the group of least significant bits.
2. The converter circuit of claim 1 , wherein the converter comprises circuit approximately N/K−2 K-bit adders.
3. A converter circuit comprising:
a 1-redundant input for receiving a 1-redundant representation of an N-bit integer;
a (1/K)-redundant output for providing a (1/K)-redundant representation of the N-bit integer, where K is an integer greater than 1 and less than N, and wherein each K-th position of the representation forms a two-bit signal having a respective binary significance;
a (K−1)-bit adder receiving (K−1) least significant bits of the 1-redundant representation, the (K−1)-bit adder providing a group of K least significant bits of the (1/K)-redundant representation to the output;
a K′-bit adder receiving K′ most significant bits of the 1-redundant representation, the K′-bit adder providing a group of K′+1 most significant bits of the (1/K)-redundant representation to the output, wherein K′ is an integer not greater than K, and
at least one K-bit adder receiving a group of K bits of the 1-redundant representation between the K′ most significant bits and the K−1 least significant bits, each K-bit adder providing to the output a group K+1 bits of the (1/K)-redundant representation between the group of most significant bits and the group of least significant bits.
4. The converter circuit of claim 3 , wherein the (1/K)-redundant representation of the integer is in the form
2 N−1 y N−1 + . . . +4 y 2 +2 y 1 +y 0 +2 K z K +2 2K z 2K + . . . +2 [(N−1)/K]K z [(N−1)/K]K , where
y 0 , . . . , y N−1 and z K , z 2K , . . . , z [(N−1)/K]K are sets of binary values.
5. The converter circuit of claim 3 , wherein the converter circuit comprises approximately N/K−2 K-bit adders.