Method and a circuit for encoding a digital signal to determine the scalar product of two vectors, and corresponding DCT processing

• US 5,218,565 A
• Filed: 09/24/1991
• Issued: 06/08/1993
• Est. Priority Date: 09/24/1990
• Status: Expired due to Fees

• Current Assignee: Orange S.A.
• Original Assignee: Orange S.A.
• Inventors: Mou, Zhi-Jian, Jutand, Francis
• Primary Examiner(s): Malzahn, David H.
• Application Number:
  US07/765,001
• Time in Patent Office: 623 Days
• Field of Search: 364/750.5, 364/736, 364/754
• US Class Current: 708/603
• CPC Class Codes: G06F 17/16 Matrix or vector computation , e.g. matrix-matrix or matrix-vector multiplication, matrix factorization matrix transposition G06F7/78
• CPC Class Codes: G06F 7/5443 Sum of products for applications thereof, see the relevant places, e.g. G06F17/10, H03H17/00
• CPC Class Codes: G06T 9/007 Transform coding, e.g. discrete cosine transform

Abstract

The invention relates to encoding a digital signal to determine the scalar product of two vectors. For two vectors of the same dimension p, one having dedicated components {ak} and the other having variable components {xk}, the scalar product value ##EQU1## is reduced to partial sums fi of binary variables xki, which binary variables take one of the values of the fixed components ak depending on the values of the xki having m possible values. Dedicated logic encoding makes it possible to take the variables xki and generate a plurality of bit level elementary partial sums fij for each bit of rank j in fi, having 2^m possible values, by varying the binary values akj of the bits of rank j. A two-dimensional interconnection matrix causes each rank j bit akj to correspond to a single value of the elementary partial sums fij, and together these bits define the corresponding partial sum fi. The invention is applicable to circuits for image processing or for data compression by the discrete cosine transform.

Claims

1. A circuit for encoding a digital signal to determine the scalar product value of two vectors of the same dimension p, one of said vectors, {ak}₁^p including dedicated components of determined value and the other vector {xk}₁^p including variable components, said dedicated and variable components being encoded on N bits, said scalar product value being expressed in the form of encoded partial sums f_i of binary variables xk_i, xk_i designating the binary value of the bit of order i of said variable components xk and each of said encoded partial product sums f_i being expressed at the bit level as an encoded elementary partial sum f_ij for each bit of order j, wherein i and j are integers in the range 0 to N-1, each encoded elementary partial sum expressed as the product xk_i.ak_j taking one of the binary values ak_ij, where ak_j designates the binary values of the bit of order j of said dedicated component ak, said circuit comprising:

a logical encoding circuit for receiving as inputs said binary values of the bit of order i of said variable components, and for generating a logical combination of said binary values of order i; and

a plurality of N multiplexers, each of said multiplexers of order j including one input for receiving said logical combination of said binary values of order i of said variable component and a further input for receiving said binary values of order j of said dedicated component, together with a zero value, and each of said multiplexers delivering a corresponding partial sum f_ij, said partial sum f_i being obtained by concatenating each of said elementary partial sums f_ij.

2. A circuit as claimed in claim 1, wherein for vectors of dimension p=2, said one vector includes dedicated components a₁ =a, a₂ =b and said other vector includes variable components x₁ =x, x₂ =y, said encoded partial sums f_i being expressed in the form

3. A circuit as claimed in claim 1, wherein for vectors of dimension p=1, said one vector includes one dedicated component a₁ =a and said other vector includes one variable component x₁ =x, said variable component being encoded using a two complements code and said partial sum f_i being expressed as f_i =(-2x_i +x_i+1 +x_i+2).a, where i, i+1, i+2 designate bit orders of successive binary variables of said variable component x, said logical encoding circuit comprising a modified Booth encoder for receiving said successive binary variables of said variable component, and for generating and delivering to said multiplexers:

a shift check parameter S_i expressed as a logical combination of the form

space="preserve" listing-type="equation">S.sub.i =x.sub.i+1 ⊕

x.sub.i+2,

a non-zero check parameter N_i expressed as a logical combination of the form

space="preserve" listing-type="equation">N.sub.i =x.sub.i.x.sub.i+1.x.sub.i+2 +x.sub.i.x.sub.i+1.x.sub.i+2, and

a complement control parameter C_i expressed as a logical combination of the form C_i =x_i, each multiplexer of order j receiving said binary variable a_j of order j of said dedicated component so as to deliver a corresponding elementary partial sum f_ij.

4. A circuit for encoding a digital signal to determine the scalar product value of two vectors of the same dimension p, one of said vectors, {ak}₁^p including dedicated components of determined value and the other vector {xk}₁^p including variable components, said dedicated and variable components being encoded on N bits, said scalar product value being expressed in the form of encoded partial sums f_i of binary variables xk_i, xk_i designating the binary value of the bit of order i of said variable components xk and each of said encoded partial product sums f_i being expressed at the bit level as an encoded elementary partial sum f_ij for each bit of order j, wherein i and j are integers in the range 0 to N-1, each encoded elementary partial sum expressed as the product xk_i.ak_j taking one of the binary values ak_ij, where ak_j designates the binary values of the bit of order j of said dedicated component ak, said circuit comprising:

dedicated logic encoding means for generating a plurality of said encoded elementary partial sums f_ij on the basis of said binary values xk_i of said variable components xk, by evaluating 2^m possibilities wherein m=2^p -1 if p≧

2 or m=2 if p=1, by varying the binary values ak_j of the bits of the same order j of the said dedicated component ak, and

at least one two-dimensional interconnection matrix of dimension 2^m N, said at least one matrix having an input for receiving said encoded elementary partial sums f_ij and an input for receiving said binary values ak_j of the bits of the same order j of said dedicated components, and the at least one matrix comprising electrical connections causing each of said binary values of rank j of said dedicated components to correspond to one value and to one value only of said bit level encoded elementary partial sums f_ij, said sum f_i being obtained by concatenating each of said elementary partial sums.

5. A circuit as claimed in claim 4 wherein for vectors of dimensions p=2, one of said vectors including dedicated components a₁ =a, a₂ =b, and said other vector including variable components x₁ =x, y₂ =y, said encoded partial sums f_i being expressed in the form

6. A circuit as claimed in claim 4 wherein for vectors of dimension p=1, one of said vectors including a dedicated component a₁ =a and said other of said vectors including a variable component x₁ =x, said variable component being encoded using a two complements code and said partial sum f_i being expressed as f_i =(-2x_i +x_i +1+x_i +2).a where i, i+1, i+2 designate integer bit orders of binary values of said variable component x, said dedicated encoding circuit comprises:

an input circuit having an input for receiving said binary values x_i, x_i+1, x_i+2 of corresponding order of said variable component x, said input circuit including three inverters for generating complemented values x_i, x_i+1, x_i+2 of said binary values and an output for delivering said binary values and said complemented binary values, and

a plurality of logic gates for receiving said binary values and said complemented binary values and for delivering the corresponding values of said elementary partial sums f_ij.

7. A circuit as claimed in claim 4 in which said two dimensional matrix comprises a programmable mesh network connected between conductors connected to the input of said matrix and conductors connected to its output, an electrical connection being formed between an input and an output so as to enable each output to correspond to an input of corresponding value.

8. Apparatus for calculating the scalar product of two vectors of dimension 2q, with q>

1, wherein each vector is subdivided into q subvectors of dimension 2, said apparatus comprising a plurality of circuits each comprising a circuit for encoding a digital signal to determine the scalar product value of two vectors of the same dimension p, one of said vectors, {ak}₁^p including dedicated components of determined value and the other vector {xk}₁^p including variable components, said dedicated and variable components being encoded on N bits, said scalar product value being expressed in the form of encoded partial sums f_i of binary variables xk_i, xk_i designating the binary value of the bit of order i of said variable components xk and each of said encoded partial product sums f_i being expressed at the bit level as an encoded elementary partial sum f_ij for each bit of order j, wherein i and j are integers in the range 0 to N-1, each encoded elementary partial sum expressed as the product xk_i.ak_j taking one of the binary values ak_ij, where ak_j designates the binary values of the bit of order j of said dedicated component ak, said circuit comprising;

dedicated logic encoding means for generating a plurality of said encoded elementary partial sums f_ij on the basis of said binary values xk_i of said variable components xk, by evaluating 2^m possibilities wherein m=2^p -1 if p≧

2 or m=2 if p=1, by varying the binary values ak_j of the bits of the same order j of the said dedicated component ak, and

at least one two-dimentional interconnection matrix of dimension 2^m N, said at least one matrix having an input for receiving said encoded elementary partial sums f_ij and an input for receiving said binary values ak_j of the bits of the same order j of said dedicated components, and the at least one matrix comprising electrical connections causing each of said binary values of rank j of said dedicated components to correspond to one value and to one value only of said bit level encoded elementary partial sums f_ij, and said sum f_i being obtained by concatenating each of said elementary partial sums, one of said circuits using each pair of subvectors relating to dedicated components and to variable components to generate a corresponding partial sum ei, fi, gi, hi, and said apparatus further comprising summing means for receiving and summing together each partial sum ei, fi, gi, hi.

9. Apparatus according to claim 8, wherein said apparatus is adapted to perform a discrete cosine transform by multiplying a matrix of dimensions (nxp) by a vector of dimension p, said plurality of circuits being arranged so as to constitute:

a first channel for processing the sum of the variable components of ranks r and s where r+s=p; and

a second channel for processing the differences of the variable components of ranks r and s where r+s=p, each of the first and second channels being subdivided into a plurality of elementary channels formed by one of said circuits, the outputs from an array forming a two-dimensional matrix of said circuit constituting each elementary channel being interconnected with a summing circuit of said summing means.

10. Apparatus according to claim 9, wherein said apparatus is adapted to process a vector of dimension p=8 at a rate of one bit per clock cycle, each elementary channel on the first path including:

two parallel summing circuits receiving the variable components x0,x7;

x1,x6 and x2,x5;

x3,x4, respectively;

a circuit having four programmed arrays, each programmed array corresponding to the dedicated components constituted by the p/2 row components of the submatrices in the calculation; and

each elementary path of the second channel including;

two parallel substractors receiving the variable components x4,x3;

x2,x5; and

x1,x6;

x0,x7, respectively; and

a circuit having four programmed arrays, each programmed array corresponding to the dedicated components constituted by the p/2 row components of the calculation submatrices;

said first and second channels each including p/2=4 summing circuits each having its inputs connected to the outputs from one of the programmed arrays of each of the elementary channels of the corresponding path.

11. Apparatus according to claim 9, wherein said apparatus is adapted to process a vector of dimension of p=8 at a rate of 2 bits per clock cycle, each elementary channel of the first channel which comprises four elementary paths including two summing circuits in cascade receiving the variable components x0,x7;

x1,x6 and x2,x5;

x3,x4 respectively, said summing circuits in cascade delivering three bits of successive ranks in parallel relating to the corresponding sums x0+x7;

x1+x6;

x2+x5; and

x3+x4, and

a circuit having four programmed arrays, each programmed array corresponding to dedicated components constituted by the p/2 row components of the calculation submatrix;

each elementary channel of the second channel which comprises four elementary channels including;

two substractors in cascade delivering three bits of successive ranks in parallel relating to the corresponding differences x4-x3, x5-x2;

x1-x6;

x7-x0; and

a circuit having four programmable arrays, each programmable array corresponding to dedicated components constituted by p/2 components of the rows of the calculation submatrices; and

said first and second channels each including p/2=4 summing circuits whose inputs receive the outputs from one of the programmed arrays in each of the elementary channels of the corresponding channel.