Circuit for the fast calculation of the direct or inverse cosine transform of a discrete signal

Claim 1

A circuit for the fast calculation of the cosine transform (X i ), 0≦i≦N-1, in which N=2 n , n≧4 of a discretized signal defined by a sequence (x i ), 0≦i≦N-1, wherein said circuit receives a sequence (x j ), 0≦j≦N-1, and comprises: a first adder stage which receives said sequence (x j ), 0≦j≦N-1, and supplies a first sequence (x j o ), 0≦j≦(N/2)-1, in which x j o =x j +x N-1-j , and a second sequence (y j ), 0≦j≦(N/2)-1, in which y j =x j -x N-1-j ; a group of upper half-stages connected in series, a first upper half-stage connected to the first adder stage and receiving the first sequence (x j o ), 0≦j≦(N/2)-1, and a last upper half-stage supplying a sequence (X 2q ), 0≦q≦(N/2)-1, of even index components of the cosine transform, a signal supplied on each output of each upper half-stage being obtained by linear combination of at most two signals applied to each of its inputs, said group of upper half-stages being defined by recurrence on the size N and constituting a cosine transform circuit for N/2 points, said group of upper half-stages comprising in series, for N=8, an adder stage, a multiplier stage, an adder stage and a multiplier stage; a group of lower half-stages connected in series, a first lower half-stage connected to the first adder stage and receiving the second sequence (y j ), 0≦j≦(N/2)-1, and a final lower half-stage supplying a sequence (X 2q+1 ), 0≦q≦(N/2)-1, of odd index components of the cosine transform, the signal supplied on each output of each lower half-stage being obtained by linear combination of at most two signals applied to each of its inputs, the group of lower half-stages comprising in series: (a) a first lower adder half-stage supplying a third sequence (x j 3 ), 0≦j≦(N/8)-1, in which x j 3 =y 4j+2 +Y 4j+1 , a fourth sequence (x j 1 ), 0≦j≦(N/4)-1, in which x j 1 =y 4j for j≦(N/8)-1 and x j 1 =-y N-4j-1 for j≧(N/8)-1, and a fifth sequence (x j 2 ), 0≦j≦(N/8)-1 in which x j 2 =y 4j+2 -y 4j+1 , (b) a sequence of lower adder ∠ multiplier half-stages supplying a sixth sequence (α 2q+1 ), 0≦q≦(N/8)-1, equal to the real parts of the odd index components of a Fourier transform of order N/2 of the fourth sequence, a seventh sequence (β 2q+1 ), 0≦q≦(N/8)-1 equal to the imaginary parts of the odd index components of the Fourier transform of order N/2 of the fourth sequence, an eighth sequence (δ 2q+1 ), 0≦q≦(N/8)-1 equal to the odd index components of the sine transform of order N/4 of the fifth sequence, a ninth sequence (γ 2q+1 ), 0≦q≦(N/8)-1 equal to the odd index components of the cosine transform of order N/4 of the third sequence, (c) a second lower adder half-stage for supplying the sequences (α 2q+1 +γ 2q+1 ), 0≦q≦(N/8)-1, (α 2q+1 -γ 2q+1 ), 0≦q≦(N/8)-1, (β 2q+1 +δ 2q+1 ), 0≦q≦(N/8)-1, and (β 2q+1 -δ 2q+1 ), 0≦q≦(N/8)-1, and (d) a lower multiplier half-stage supplying the sequence (X 2q+1 ), 0≦q≦(N/2)-1, of odd index components of the cosine transform of order N of the sequence (x j ), 0≦j≦N-1.