Circuit for computing the quantized coefficient discrete cosine transform of digital signal samples

• US 4,849,922 A
• Filed: 12/11/1987
• Issued: 07/18/1989
• Est. Priority Date: 01/20/1987
• Status: Expired due to Fees

• Current Assignee: Cselt - Centro Studi E Laboratori Telecommunicazioni SPA
• Original Assignee: Cselt - Centro Studi E Laboratori Telecommunicazioni SPA
• Inventors: Riolfo, Benedetto
• Primary Examiner(s): Harkcom, Gary V.
• Assistant Examiner(s): Mai, Tan V.
• Application Number:
  US07/131,833
• Time in Patent Office: 585 Days
• Field of Search: 364/725, 364/726, 382/43
• US Class Current: 708/402
• CPC Class Codes: G06F 17/147 Discrete orthonormal transforms, e.g. discrete cosine transform, discrete sine transform, and variations therefrom, e.g. modified discrete cosine transform, integer transforms approximating the discrete cosine transform G06F17/145 takes precedence
• CPC Class Codes: G06F 7/5334 by using multiple bit scanning, i.e. by decoding groups of successive multiplier bits in order to select an appropriate precalculated multiple of the multiplicand as a partial product

Abstract

The circuit consists of two parallel branches which perform multiplication and accumulation operations for the even and odd lines of the transform coefficient matrix. Each branch includes: an input circuit (SEM1, SOT1) whereby the contributions of the opposing index columns of the matrix may be added; a multiplication circuit (ERM, ORM) which performs multiplication operations for each matrix column by an addition and shifting operation for each matrix coefficient; and an accumulation circuit for the intermediate products of each matrix column.

Claims

1. A circuit for computing a discrete cosine transform of f(j) sample vectors of dimension N(0<

j<

N-1), said transform having a square matrix base of dimensions N.N with coefficients which repeat in absolute value at each column but whose order and sign can differ, said circuit obtaining transformed F(k) sample vectors including vectors of dimension N(0<

K<

N-1), said circuit comprising two circuit branches working in parallel including a first circuit branch for operations relating to coefficients in even matrix lines and a second circuit branch for coefficients in odd matrix lines, said branches comprising;

a first adder and a first subtracter, belonging to the first and second branch respectively, which at inputs receive pairs of samples of an F(j) vector having index (j) and (N-j-1), with j increasing sequentially from 0 to NR-1;

first and second calculating units, belonging to the first and second branch respectively, which, for each addition or subtraction result received respectively from said first adder or first subtracter, calculate NR partial products referring to the matrix column coefficients in even and odd lines respectively, with sequential order, among the coefficients of a column, fixed for all columns, so as to produce each partial product through an addition and shifting operation which involves the previous partial products or input datum;

a first and second adder/subtracter belonging respectively to the first and second branch, which add or subtract a partial product received from a second input to or from a datum received from a first input of first and second calculating units respectively, and finding the sum in the case of a partial product referring to a positive coefficient or the difference in the case of a negative coefficient;

first and second memories, belonging to the first and second branch respectively, accumulating NR partial results each, for accumulating calculations performed by said first and second adder/subtracters, said first memories accumulating partial results R* (2K) relating to even matrix column lines, said second memories accumulating partial result R* (2K+1) relating to odd lines, said partial results being components of a transformed sample vector F(k) at the NR-1 index columns;

first addressing units which generate;

first control signals for said first and second calculating units, said first control signals determining said sequential order, among coefficients of a column, fixed for all columns;

addresses to be read in said first and second memories for accumulation of said partial results, supplied as data to said first input of first and second adder/subtracter respectively, and for re-writing said data updated in the same position, said addresses having a sequence which varies with the matrix column, such as to identify the partial result R* (2k) and R* (2k+1) whose index identifies the matrix line containing the coefficient for which said first and second calculating units perform said partial products;

operation selection signals for said first and second adder/subtracter.

2. A circuit as defined in claim 1 wherein for N=16 said first calculating units comprise:

a first and a second multiplexer which at a first input receive output of said first adder and at a second input receive output of a first register;

first and second shifting units which receive outputs of the first and second multiplexer respectively; and

a third adder/subtracter which receives outputs of said first and second shifting units, for subtraction subtracting the output of the second shifting units from that of the first shifting units, and whose output supplies said first register and is the output of said first calculating unit; and

wherein said second calculating units comprise;

a third and fourth multiplexers which at a first input receive output of said first subtracter, said third multiplexer receiving at a second input the output of a second register, said fourth multiplexer also receiving the outputs of a third and fourth register at a third and fourth input;

third and fourth shifting units which receive outputs of the third and fourth multiplexers respectively; and

a fourth adder/subtracter which receives outputs of said third and fourth shifting units, for subtraction subtracting the output of the third shifting units from that of the fourth shifting units and whose output supplies said second, third and fourth registers and is the output of said second calculating units, said first, second, third and fourth registers being used for temporary storage of said previous partial products.

3. A circuit as defined in claim 2 wherein said first control signals generated by said first addressing units cause the following succession of operations to be performed by said first and second calculating units:

for the first partial product, the first, second, third and fourth multiplexers are switched on the first input, the first, second, third and fourth shifting units shift respectively by four, one, zero and three positions to the left, in the direction of multiplications by powers of two, the third and fourth adder/subtracter find the sum, said first and second registers memorize the input datum;

for the second partial product the first, second, third and fourth multiplexers are switched respectively on the second, first, second, first input, the first, second, third and fourth shifting units shift respectively by one, zero, one and three positions to the left, the third and fourth adder/subtracters find the sum and the difference respectively, said third register memorizes the input data;

for the third partial product the first, second, third and fourth multiplexers are switched on the second, first, second and third input, the first, second, third and fourth shifting units shift by zero, five, zero and one positions to the left, the third adder/subtracter finds the sum and the fourth the difference, said first and fourth registers memorize the input data;

for the fourth partial product the first, second and fourth multiplexers are switched on the first input, the third multiplexer on the second input, the first, second, third and fourth shifting units shift by five, five, three and one position to the left, the third adder/subtracter finds the sum and the fourth the difference;

for the fifth partial product the first and second multiplexers are switched on the second input, the third and fourth on the first input, the first shifting units shift by one position to the right in the direction of division by multiples of two, the third and fourth shifting units shift by six and four positions to the left, the third and fourth adder/subtracters find the sum, the second register memorizes the input datum;

for the sixth partial product the first, second, third and fourth multiplexers are switched on the second, first, second and third inputs, the first, second and fourth shifting units shift by one, four and one position to the left, the third shifting unit shifts by four positions to the right, the third adder/subtracter finds the difference and the fourth the sum;

for the seventh partial product the first, second, third and fourth multiplexers are switched on the second, first and fourth inputs, the first shifting units shift by one position to the right, the second and fourth shifting units shift by six and one position to the left, the third and fourth adder/subtracters find the sum; and

for the eighth partial product, the first, second and third multiplexers are switched on the first input, the fourth on the third input, the first, second and third shifting units shift by five, five and six positions to the left, the third and fourth adder/subtracters find the sum.

4. A circuit as defined in claim 2 wherein said shifting units consist of barrel shifters.

5. The circuit as defined in claim 1 wherein for N=16 said first and second calculating units include six and eight adders or subtracters respectively which produce an equal number of partial products through suitable justification of their two inputs, six and eighth registers which memorize the results thereof, and further register on input of said first circuit units and multiplexers which receive the outputs of said registers, said first control signals generated by said addressing units determining only the connection sequence of multiplexer inputs with outputs.

6. The circuit defined in claim 5 wherein said first calculating units make the following interconnection between said adders or subtracters, intercalated with said registers;

to a second adder is applied the output or said first adder shifted to the left by one and four positions;

to a third adder are brought the outputs of said first adder, shifted by five positions to the left, and of said second adder;

to a second subtracter are brought the outputs of the second adder, shifted by one position to the left, and of the first adder;

to a third subtracter are brought the outputs of the first adder, shifted by four positions to the left, and of the third adder, shifted by one position to the left;

to a fourth adder are connected to the outputs of the first adder, shifted by six positions to the left, and of the third adder, shifted by one position to the right;

to a fifth adder is applied the output of the third adder shifted by one position to the right at one input;

said further register receives the output of the first adder shifted by six positions to the left;

in addition, characterized in that said second circuit units feature the following interconnection between said adders and subtracters, intercalated with said registers;

to a sixth and seventh adder is applied the output of the first subtracter respectively shifted by six and four positions to the left and by three and zero positions to the left;

to an eighth adder are brought the outputs of the first subtracter, shifted by three positions to the left, and of the seventh adder, shifted by one position to the left;

to a fourth subtracter are brought the outputs of the first subtracter, shifted by one position to the left, and of the seventh adder, shifted by three positions to the left;

to a fifth subtracter are applied the outputs of the seventh adder and the eighth adder, shifted by one position to the left;

to a ninth adder are brought the outputs of the first subtracter, shifted by six positions to the left, and of the eighth adder;

to a tenth adder are applied the outputs of the sixth adder, shifted by four positions to the right and of the eighth adder, shifted by one position to the left;

to an eleventh adder are brought the outputs of the first subtracter, and of the fifth subtracter, shifted by one position to the left;

said output multiplexers connecting inputs to outputs in the following order;

for the first partial product, the outputs of the second and seventh adder;

for the second partial product, the outputs of the second subtracter and the eighth adder;

for the third partial product, the outputs of the third adder and the fifth subtracter;

for the fourth partial product, the outputs of the further register and the fourth subtracter;

for the fifth partial product, the outputs of the fifth and sixth adder;

for the sixth partial product, the outputs of the third subtracter and the tenth adder;

for the seventh partial product, the outputs of the fourth and eleventh adder; and

for the eighth partial product, the outputs of the further register and the ninth adder.

7. The circuit as defined in claim 1 wherein for N=8 said first calculating units include:

a fifth and a sixth multiplexer which receives at a first input output of said first adder, at a second input output of a fifth register;

said sixth multiplexer receiving at a third input output of a sixth register shifted by one position to the left, and with the outputs applied to its first and second inputs shifted by three positions to the left;

fifth scaling units which receive output of the fifth multiplexer; and

a sixth subtracter which subtracts the output of the fifth shifting units from that of the sixth multiplexer, and whose output supplies said fifth and sixth registers and is the output of said first circuit units; and

said calculating units include;

a seventh and an eighth multiplexer which receive at a first input output of said first subtracter, and at a second input outputs of a seventh and an eight register respectively;

sixth and seventh shifting units which receive respectively the outputs of said seventh and eighth multiplexers; and

a sixth adder/subtracter which receives the outputs of said sixth and seventh shifting units, for subtraction subtracting the output of the sixth shifting units from that of the seventh, and whose output supplies and seventh and eighth registers and is the output of said second circuit units said fifth, sixth, seventh, eighth registers being used for temporary storage of said previous partial products.

8. The circuit defined in claim 7 wherein said first control signals generated by said addressing units cause the following succession of operations by said first and second calculating units:

for the first partial product, the fifth, sixth, seventh and eighth multiplexers are switched on the first input, the fifth, sixth, and seventh shifting units shift by zero, zero and three positions to the left, and sixth adder/subtracter performs subtraction, the fifth and seventh registers memorize the input datum;

for the second partial product, the fifth, sixth, seventh multiplexers are switched on the second input, the eighth multiplexer on the first input, the fifth, sixth and seventh shifting units shift by zero, zero and five positions, the sixth adder/subtracter performs subtraction, the sixth and eighth registers memorize the input datum;

for the third partial product, the fifth, sixth, seventh and eighth multiplexers are switched respectively on the second, third, second and fifth inputs, the fifth, sixth and seventh shifting units shift by zero, zero and six positions to the left, the sixth adder/subtracter finds the sum;

for the fourth partial product, the fifth, sixth, seventh and eighth multiplexers are switched respectively on the second, third, second and second inputs, the fifth, sixth and seventh shifting units shift by zero, three and one position to the left, the sixth adder/subtracter finds the sum, the seventh register memorizes the input datum and;

for the fifth partial product, the fifth, sixth, seventh and eighth multiplexers are switched on the first, third, first and first input, the fifth, sixth and seventh shifting units shift by six, one and seven positions to the left, and the sixth adder/subtracter performs subtraction.

9. A circuit as defined in claim 7 wherein said first control signals generated by said first addressing units cause the following succession of operations to be performed by said first and second calculating units:

for the first partial product, the first, second, third and fourth multiplexers are switched on the first input, the first, second, third and fourth shifting units shift respectively by four, one, zero and three positions to the left, in the direction of multiplications by powers of two, the third and fourth adder/subtracter find the sum, said first and second registers memorize the input datum;

for the second partial product the first, second, third and fourth multiplexers are switched respectively on the second, first, second, first input, the first, second, third and fourth shifting units shift respectively by one, zero, one and three positions to the left, the third and fourth adder/subtracters find the sum and the difference respectively, said third register memorizes the input data;

for the third partial product the first, second, third and fourth multiplexers are switched on the second, first, second and third input, the first, second, third and fourth shifting units shift by zero, five, zero and one positions to the left, the third adder/subtracter finds the sum and the fourth the difference, said first and fourth registers memorize the input data;

for the fourth partial product the first, second and fourth multiplexers are switched on the first input, the third multiplexer on the second input, the first, second, third and fourth shifting units shift by five, five, three and one position to the left, the third adder/subtracter finds the sum and the fourth the difference;

for the fifth partial product the first and second multiplexers are switched on the second input, the third and fourth on the first input, the first shifting units shift by one position to the right in the direction of division by multiples of two, the third and fourth shifting units shift by six and four positions to the left, the third and fourth adder/subtracter find the sum, the second register memorizes the input datum;

for the sixth partial product the first, second, third and fourth multiplexers are switched on the second, first, second and third inputs, the first, second and fourth shifting units shift by one, four and one position to the left, the third shifting unit shifts by four positions to the right, the third adder/subtracter finds the difference and the fourth the sum;

for the seventh partial product the first, second, third and fourth multiplexers are switched on the second, first and fourth inputs, the first shifting units shift by one position to the right, the second and fourth shifting units shift by six and one position to the left, the third and fourth adder/subtracters find the sum; and

for the eighth partial product, the first, second and third multiplexers are switched on the first input, the fourth on the third input, the first, second and third shifting units shift by five, five and six positions to the left, the third and fourth adder/subtracters find the sum.

10. The circuit as defined in claim 1 wherein for N=8, said first and second calculating units include respectively four and five adders or subtracters which produce an equal number of partial products through suitable justification of their two inputs, four and five registers which memorize the results thereof, and an output multiplexer which receives the outputs of said registers, said first control signals generated by said addressing units determining only the connection sequence of multiplexer inputs with outputs.

11. The circuit defined in claim 10 wherein said first calculating units effect the following interconnection between said adders or subtracters, intercalated with said registers:

to a seventh subtracter is applied the output of the first adder shifted by three positions to the left at one input;

to an eighth subtracter is applied the output of the seventh subtracter shifted at an input by three positions;

to a ninth subtracter are applied the outputs of the seventh subtracter, and of the eighth subtracter scaled by one position to the left; and

to a tenth subtracter are brought the outputs of the first adder, shifted by six positions to the left, and of the ninth subtracter shifted by one position to the left; and

wherein said second calculating units effect the following interconnection between said adders or subtracters, intercalated with said registers;

to an eleventh and twelfth subtracter is applied the output of said first subtracter respectively shifted by three, zero, seven and one position to the left;

to a thirteenth subtracter are applied the outputs of the first adder, shifted by five positions to the left, and the eleventh subtracter;

to a twelfth adder are applied the outputs of the first subtracter, shifted by six positions to the left, and of the eleventh subtracter;

to a thirteenth subtracter are applied the outputs of the eleventh subtracter shifted by three positions to the left, and of the thirteenth subtracter, shifted by one position to the left;

said output multiplexer connecting inputs to outputs in the following order;

for the first partial product, the outputs of the eighth and thirteenth subtracters;

for the second partial product, the outputs of the ninth subtracter and the twelfth adder;

for the third partial product, the outputs of the ninth subtracter and the thirteenth adder; and

for the fourth partial product, the outputs of the tenth and twelfth subtracter.

12. A circuit as defined in claim 1 wherein said first addressing units supply to outside a data-ready (DR) signal at the beginning of the operations relating to the NR-1 index column;

on the basis of said signal, the partial results R* (k) at the outputs of said first and second adder/subtracters are available at outputs as components of a transformed F(k) sample vector.

13. A circuit as defined in claim 1 wherein said first addressing units (ADR2) supply, at the end of calculations relating to the index NR-1 column, addresses to said first and second accumulation memories for sequential reading and forwarding to the outputs of R* (k) partial results, there memorized, as components of a transformed F(k) sample vector.

14. A circuit as defined in claim 1 wherein the data at the outputs of said first adder, first subtracter, first and second calculating units and first and second accumulation memories are synchronized by registers.

15. A circuit for computing the two-dimensional discrete cosine transform using a plurality of transform computing circuits as defined in claim 1 and which includes a first of said transform computing circuits followed by a matrix-structured intermediate memory and by a second of such circuits, and second addressing units for said intermediate memory which determine writing of N vectors of transformed F(k) samples, calculated by the first circuit, and reading in a direction orthogonal to that of writing, of N vectors of f(j) samples to be transformed, each consisting for the K-nth component of said F(k) vectors present in said intermediate memory, for forwarding to a second of said transform computing circuit.