Recursive DCT implementation

Question

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:

Normal Matrix-Vector DCT-formula

Recursive DCT-formula:

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}$.

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.