I am trying to understand the recursive implementation of the DCT on the input signal (used for LMS filtering) according to the pictures below.

The pictures and formulas are taken from the paper: "Adaptive Inverse Control: A Signal Processing Approach", by Bernard Widrow and Eugene Walach

Block diagram of DCT structure: enter image description here

Normal Matrix-Vector DCT-formula enter image description here

Recursive DCT-formula:

enter image description here

What bothers me is how can this recursive DCT implementation yield the same result as the normal computation by using matrix-vector multiplication when the recursive formula uses the signal $x_{k-n}$?

But on the other hand the normal computation only uses signals up to $x_{k-n+1}$.


1 Answer 1


It is possible to decompose DCT8 into a combination of DCT4 and DST4 of interleaved inputs. Let's say our input is a vector {x0,x1,x2,x3,x4,x5,x6,x7}. Then let's compute the DCT4 and DST4 of interleaved inputs:

{y00,y10,y20,y30} = DCT4({x0,x2,x4,x6})
{y01,y11,y21,y31} = DCT4({x1,x3,x5,x7})
{z00,z10,z20,z30} = DST4({x0,x2,x4,x6})
{z01,z11,z21,z31} = DST4({x1,x3,x5,x7})

Then DCT8 would be:

DCT8({x0,x1,x2,x3,x4,x5,x6,x7}) = {
  cos(pi/32)  *(y00 + y01) + sin(pi/32) *(z00 - z01)
  cos(3pi/32) *(y10 + y11) + sin(3pi/32)*(z10 - z11)
  cos(5pi/32) *(y20 + y21) + sin(5pi/32)*(z20 - z21)
  cos(7pi/32) *(y30 + y31) + sin(7pi/32)*(z30 - z31)
  cos(9pi/32) *(y40 + y41) + sin(9pi/32)*(z40 - z41)
  cos(11pi/32)*(y50 + y51) + sin(11pi/32)*(z50 - z51)
  cos(13pi/32)*(y60 + y61) + sin(13pi/32)*(z60 - z61)
  cos(15pi/32)*(y70 + y71) + sin(15pi/32)*(z70 - z71)

The same way you can decompose any DCT N into a combination of DCT N/2 and DST N/2.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.