does the current DCT/IDCT hardware use the same architecture for both DCT and IDCT?

Dear all,

I came across an interesting problem: for a device both encodes and decodes
video, do the designers seperately design circuit for DCT and another
circuit for IDCT? I suspect that they have one universal transform circuit,
then with some modification, IDCT can be computed using the DCT circuit(the
universal circuit). Is that true? If so, how does that work? How to modify a
little bit the DCT circuit to compute IDCT?

Regards and thanks!

-Walala

Hello Walala,

The DCT is an example of an orthonormal transform. As such when formulated
as a matrix multiply, the inverse transform becomes just the transpose of
the forward transform. So using the same hardware for both directions would
barely be more effort than doing the transform in only one direction.

-- 
Clay S. Turner, V.P.
Wireless Systems Engineering, Inc.
Satellite Beach, Florida 32937
(321) 777-7889
www.wse.biz
csturner@wse.biz



"walala" <mizhael@yahoo.com> wrote in message
news:bvcfjg$1jm$1@mozo.cc.purdue.edu...
> Dear all,
>
> I came across an interesting problem: for a device both encodes and
decodes
> video, do the designers seperately design circuit for DCT and another
> circuit for IDCT? I suspect that they have one universal transform
circuit,
> then with some modification, IDCT can be computed using the DCT
circuit(the
> universal circuit). Is that true? If so, how does that work? How to modify
a
> little bit the DCT circuit to compute IDCT?
>
> Regards and thanks!
>
> -Walala
>
>

> I came across an interesting problem: for a device both encodes and decodes
> video, do the designers seperately design circuit for DCT and another
> circuit for IDCT? I suspect that they have one universal transform circuit,
> then with some modification, IDCT can be computed using the DCT circuit(the
> universal circuit). Is that true? If so, how does that work? How to modify a
> little bit the DCT circuit to compute IDCT?

What DCT are you using, there are four types I think.
The DCT-IV is the same in both directions: ie. the IDCT-IV
is the same as the DCT-IV. For image processing purposes I
think the type-II is most common, but I dont think that is
the same in both directions.

"Clay S. Turner" <CSTurner@WSE.Biz> wrote in message
news:cQkSb.3722$pk.1008@bignews3.bellsouth.net...
> Hello Walala,
>
> The DCT is an example of an orthonormal transform. As such when formulated
> as a matrix multiply, the inverse transform becomes just the transpose of
> the forward transform. So using the same hardware for both directions
would
> barely be more effort than doing the transform in only one direction.
>
> -- 
> Clay S. Turner, V.P.
> Wireless Systems Engineering, Inc.
> Satellite Beach, Florida 32937
> (321) 777-7889
> www.wse.biz
> csturner@wse.biz
>
>
>
> "walala" <mizhael@yahoo.com> wrote in message
> news:bvcfjg$1jm$1@mozo.cc.purdue.edu...
> > Dear all,
> >
> > I came across an interesting problem: for a device both encodes and
> decodes
> > video, do the designers seperately design circuit for DCT and another
> > circuit for IDCT? I suspect that they have one universal transform
> circuit,
> > then with some modification, IDCT can be computed using the DCT
> circuit(the
> > universal circuit). Is that true? If so, how does that work? How to
modify
> a
> > little bit the DCT circuit to compute IDCT?
> >
> > Regards and thanks!
> >
> > -Walala
> >

Dear Clay,

If you write Y=DCT(X) into the form:

Y=AXA' is the forward transform, where all variables are square matrices, A
is the forward DCT matrix.

The inverse transform Y=IDCT(X) shoulde be Y=A'XA,

But how can you write Y=A'XA in terms of (AX)? because in computing DCT in
hardware, you only have 1D transform circuit, you do Y=(A(AX)')'=AXA' for
DCT(X). The circuit outputs Y in columnwise form and you first compute AX,
then take transposition, then do A(AX)' again, then output Y in
columnwise(transposed) form.

Now suppose you only have the circuit for computing a matrix right multiply
wiht a vector in the form of Y=AX. How do you express IDCT, Y=A'XA in this
form too to reuse the structure?

-Thanks,

Wlala

"walala" <mizhael@yahoo.com> wrote in message
news:bvebrc$ht$1@mozo.cc.purdue.edu...
>
> "Clay S. Turner" <CSTurner@WSE.Biz> wrote in message
> news:cQkSb.3722$pk.1008@bignews3.bellsouth.net...
> > Hello Walala,
> >
> > The DCT is an example of an orthonormal transform. As such when
formulated
> > as a matrix multiply, the inverse transform becomes just the transpose
of
> > the forward transform. So using the same hardware for both directions
> would
> > barely be more effort than doing the transform in only one direction.
> >
> > -- 
> > Clay S. Turner, V.P.
> > Wireless Systems Engineering, Inc.
> > Satellite Beach, Florida 32937
> > (321) 777-7889
> > www.wse.biz
> > csturner@wse.biz
> >
> >
> >
> > "walala" <mizhael@yahoo.com> wrote in message
> > news:bvcfjg$1jm$1@mozo.cc.purdue.edu...
> > > Dear all,
> > >
> > > I came across an interesting problem: for a device both encodes and
> > decodes
> > > video, do the designers seperately design circuit for DCT and another
> > > circuit for IDCT? I suspect that they have one universal transform
> > circuit,
> > > then with some modification, IDCT can be computed using the DCT
> > circuit(the
> > > universal circuit). Is that true? If so, how does that work? How to
> modify
> > a
> > > little bit the DCT circuit to compute IDCT?
> > >
> > > Regards and thanks!
> > >
> > > -Walala
> > >
>
> Dear Clay,
>
> If you write Y=DCT(X) into the form:
>
> Y=AXA' is the forward transform, where all variables are square matrices,
A
> is the forward DCT matrix.
>
> The inverse transform Y=IDCT(X) shoulde be Y=A'XA,
>
> But how can you write Y=A'XA in terms of (AX)? because in computing DCT in
> hardware, you only have 1D transform circuit, you do Y=(A(AX)')'=AXA' for
> DCT(X). The circuit outputs Y in columnwise form and you first compute AX,
> then take transposition, then do A(AX)' again, then output Y in
> columnwise(transposed) form.
>
> Now suppose you only have the circuit for computing a matrix right
multiply
> wiht a vector in the form of Y=AX. How do you express IDCT, Y=A'XA in this
> form too to reuse the structure?
>
> -Thanks,
>
> Wlala



I mean, you can only use A right multiply with some matrix: X or X', but you
cannot write A' right multiply with some matrix. Your circuit can only
compute  Y=AX, nor Y=A'X...

"walala" <mizhael@yahoo.com> wrote in message
news:bvec19$nm$1@mozo.cc.purdue.edu...
>
> "walala" <mizhael@yahoo.com> wrote in message
> news:bvebrc$ht$1@mozo.cc.purdue.edu...
> >
> > "Clay S. Turner" <CSTurner@WSE.Biz> wrote in message
> > news:cQkSb.3722$pk.1008@bignews3.bellsouth.net...
> > > Hello Walala,
> > >
> > > The DCT is an example of an orthonormal transform. As such when
> formulated
> > > as a matrix multiply, the inverse transform becomes just the transpose
> of
> > > the forward transform. So using the same hardware for both directions
> > would
> > > barely be more effort than doing the transform in only one direction.
> > >
> > > -- 
> > > Clay S. Turner, V.P.
> > > Wireless Systems Engineering, Inc.
> > > Satellite Beach, Florida 32937
> > > (321) 777-7889
> > > www.wse.biz
> > > csturner@wse.biz
> > >
> > >
> > >
> > > "walala" <mizhael@yahoo.com> wrote in message
> > > news:bvcfjg$1jm$1@mozo.cc.purdue.edu...
> > > > Dear all,
> > > >
> > > > I came across an interesting problem: for a device both encodes and
> > > decodes
> > > > video, do the designers seperately design circuit for DCT and
another
> > > > circuit for IDCT? I suspect that they have one universal transform
> > > circuit,
> > > > then with some modification, IDCT can be computed using the DCT
> > > circuit(the
> > > > universal circuit). Is that true? If so, how does that work? How to
> > modify
> > > a
> > > > little bit the DCT circuit to compute IDCT?
> > > >
> > > > Regards and thanks!
> > > >
> > > > -Walala
> > > >
> >
> > Dear Clay,
> >
> > If you write Y=DCT(X) into the form:
> >
> > Y=AXA' is the forward transform, where all variables are square
matrices,
> A
> > is the forward DCT matrix.
> >
> > The inverse transform Y=IDCT(X) shoulde be Y=A'XA,
> >
> > But how can you write Y=A'XA in terms of (AX)? because in computing DCT
in
> > hardware, you only have 1D transform circuit, you do Y=(A(AX)')'=AXA'
for
> > DCT(X). The circuit outputs Y in columnwise form and you first compute
AX,
> > then take transposition, then do A(AX)' again, then output Y in
> > columnwise(transposed) form.
> >
> > Now suppose you only have the circuit for computing a matrix right
> multiply
> > wiht a vector in the form of Y=AX. How do you express IDCT, Y=A'XA in
this
> > form too to reuse the structure?
> >
> > -Thanks,
> >
> > Wlala
>
>
>
> I mean, you can only use A right multiply with some matrix: X or X', but
you
> cannot write A' right multiply with some matrix. Your circuit can only
> compute  Y=AX, nor Y=A'X...
>

No, even you are allowed to use XA' circuit, you still cannot represent
IDCT, Y=A'XA, in terms of (XA') or (AX) form...

Hello Walala,

There are two approaches to the problem. First I know of 8 types of DCTs
where 4 are symmetric. So here the transform is self inverting. Thus no
hardware changes are needed. Second the hardware can use multiplexors to
swap the rows and columns for nonsymmetric formulations of the DCT.

-- 
Clay S. Turner, V.P.
Wireless Systems Engineering, Inc.
Satellite Beach, Florida 32937
(321) 777-7889
www.wse.biz
csturner@wse.biz



> > Dear Clay,
> >
> > If you write Y=DCT(X) into the form:
> >
> > Y=AXA' is the forward transform, where all variables are square
matrices,
> A
> > is the forward DCT matrix.
> >
> > The inverse transform Y=IDCT(X) shoulde be Y=A'XA,
> >
> > But how can you write Y=A'XA in terms of (AX)? because in computing DCT
in
> > hardware, you only have 1D transform circuit, you do Y=(A(AX)')'=AXA'
for
> > DCT(X). The circuit outputs Y in columnwise form and you first compute
AX,
> > then take transposition, then do A(AX)' again, then output Y in
> > columnwise(transposed) form.
> >
> > Now suppose you only have the circuit for computing a matrix right
> multiply
> > wiht a vector in the form of Y=AX. How do you express IDCT, Y=A'XA in
this
> > form too to reuse the structure?
> >
> > -Thanks,
> >
> > Wlala
>
>
>
> I mean, you can only use A right multiply with some matrix: X or X', but
you
> cannot write A' right multiply with some matrix. Your circuit can only
> compute  Y=AX, nor Y=A'X...
>
>

"Clay S. Turner" <CSTurner@WSE.Biz> wrote in message
news:yqzSb.72511$lh3.1599@bignews5.bellsouth.net...
> Hello Walala,
>
> There are two approaches to the problem. First I know of 8 types of DCTs
> where 4 are symmetric. So here the transform is self inverting. Thus no
> hardware changes are needed. Second the hardware can use multiplexors to
> swap the rows and columns for nonsymmetric formulations of the DCT.
>
> -- 
> Clay S. Turner, V.P.
> Wireless Systems Engineering, Inc.
> Satellite Beach, Florida 32937
> (321) 777-7889
> www.wse.biz
> csturner@wse.biz
>
>
>
> > > Dear Clay,
> > >
> > > If you write Y=DCT(X) into the form:
> > >
> > > Y=AXA' is the forward transform, where all variables are square
> matrices,
> > A
> > > is the forward DCT matrix.
> > >
> > > The inverse transform Y=IDCT(X) shoulde be Y=A'XA,
> > >
> > > But how can you write Y=A'XA in terms of (AX)? because in computing
DCT
> in
> > > hardware, you only have 1D transform circuit, you do Y=(A(AX)')'=AXA'
> for
> > > DCT(X). The circuit outputs Y in columnwise form and you first compute
> AX,
> > > then take transposition, then do A(AX)' again, then output Y in
> > > columnwise(transposed) form.
> > >
> > > Now suppose you only have the circuit for computing a matrix right
> > multiply
> > > wiht a vector in the form of Y=AX. How do you express IDCT, Y=A'XA in
> this
> > > form too to reuse the structure?
> > >
> > > -Thanks,
> > >
> > > Wlala
> >
> >
> >
> > I mean, you can only use A right multiply with some matrix: X or X', but
> you
> > cannot write A' right multiply with some matrix. Your circuit can only
> > compute  Y=AX, nor Y=A'X...
> >


Dear Clay,

I tried the type 2 DCT for image compression, which is the same as the
matlab dct and dct2 command.

If you try to use matlab dct2 command to get Y=dct2(X), which is essentially
Y=A*X*A'; you cannot get X=dct2(Y) by using the dct2 command again, no
matter how you transpose your data.

"walala" <mizhael@yahoo.com> wrote in message
news:bvgltt$1su$1@mozo.cc.purdue.edu...
>> Dear Clay,
>
> I tried the type 2 DCT for image compression, which is the same as the
> matlab dct and dct2 command.
>
> If you try to use matlab dct2 command to get Y=dct2(X), which is
essentially
> Y=A*X*A'; you cannot get X=dct2(Y) by using the dct2 command again, no
> matter how you transpose your data.
>
>

Hello Walala,
The type II DCT is not symmetric, so it won't be self inverting. Types I,
IV, V, and VIII are the symmetric ones. But only type II has a DC basis
vector, so I think this is why a lot of people use it for image processing.
Also it was the 1st type published. However for 2-D DCT transforms we have:

Y=A*X*A' where ' denotes matrix transposition

so after operating on both the left and right sides with A' and A
respectively we find

A'*Y*A = X where we exploited the property of A'A and AA' being simply the
identity matrices. This comes from the transform being orthonormal. For
nonorthonormal systems, the change of basis requires the use of A and A
inverse, but orthonormality makes A inverse simply A'.

So in comparison we find

Y=A*X*A'  (analysis)

X=A'*Y*A (synthesis)

So for the four types of DCTs mentioned above, A and A' are identical. So
the hardware encoder/decoder would be the same for these 4 cases. But for
the other four you just let your hardware just swap rows and columns on the
A and A' matrices. As I stated before, this ca be done with multiplexers.

Try using a type IV DCT. For order N, it is defined as

let j=0,1,2,...N-1 and k=0,1,2,...,N-1

Then

Aj,k = sqrt(2/N)* cos(  (j+1/2)(k+1/2)(pi/n)  )

You should be able to see that it is self inverting (i.e., it is symmetric
in its use of j and k in the defn.).  In fact when you build your DCT
matrix, try testing its orthonormality by finding the product of A and A'.
It should yield the identity matrix. Also calculate A inverse minus A
transpose. The result will be the zero matrix.

Choosing a symmetric DCT (like type IV)  and noting that A' = A, we have

Y=A*X*A  (analysis)

X=A*Y*A (synthesis)

for the forward and reverse transformations which as you can see is the same
for both encoding and decoding.

I hope this helps to clear things up.
-- 
Clay S. Turner, V.P.
Wireless Systems Engineering, Inc.
Satellite Beach, Florida 32937
(321) 777-7889
www.wse.biz
csturner@wse.biz

"Clay S. Turner" <CSTurner@WSE.Biz> wrote in message
news:q62Tb.11694$Vg3.3494@bignews5.bellsouth.net...
> "walala" <mizhael@yahoo.com> wrote in message
> news:bvgltt$1su$1@mozo.cc.purdue.edu...
> >> Dear Clay,
> >
> > I tried the type 2 DCT for image compression, which is the same as the
> > matlab dct and dct2 command.
> >
> > If you try to use matlab dct2 command to get Y=dct2(X), which is
> essentially
> > Y=A*X*A'; you cannot get X=dct2(Y) by using the dct2 command again, no
> > matter how you transpose your data.
> >
> >
>
> Hello Walala,
> The type II DCT is not symmetric, so it won't be self inverting. Types I,
> IV, V, and VIII are the symmetric ones. But only type II has a DC basis
> vector, so I think this is why a lot of people use it for image
processing.
> Also it was the 1st type published. However for 2-D DCT transforms we
have:
>
> Y=A*X*A' where ' denotes matrix transposition
>
> so after operating on both the left and right sides with A' and A
> respectively we find
>
> A'*Y*A = X where we exploited the property of A'A and AA' being simply the
> identity matrices. This comes from the transform being orthonormal. For
> nonorthonormal systems, the change of basis requires the use of A and A
> inverse, but orthonormality makes A inverse simply A'.
>
> So in comparison we find
>
> Y=A*X*A'  (analysis)
>
> X=A'*Y*A (synthesis)
>
> So for the four types of DCTs mentioned above, A and A' are identical. So
> the hardware encoder/decoder would be the same for these 4 cases. But for
> the other four you just let your hardware just swap rows and columns on
the
> A and A' matrices. As I stated before, this ca be done with multiplexers.
>
> Try using a type IV DCT. For order N, it is defined as
>
> let j=0,1,2,...N-1 and k=0,1,2,...,N-1
>
> Then
>
> Aj,k = sqrt(2/N)* cos(  (j+1/2)(k+1/2)(pi/n)  )
>
> You should be able to see that it is self inverting (i.e., it is symmetric
> in its use of j and k in the defn.).  In fact when you build your DCT
> matrix, try testing its orthonormality by finding the product of A and A'.
> It should yield the identity matrix. Also calculate A inverse minus A
> transpose. The result will be the zero matrix.
>
> Choosing a symmetric DCT (like type IV)  and noting that A' = A, we have
>
> Y=A*X*A  (analysis)
>
> X=A*Y*A (synthesis)
>
> for the forward and reverse transformations which as you can see is the
same
> for both encoding and decoding.
>
> I hope this helps to clear things up.
> -- 
> Clay S. Turner, V.P.
> Wireless Systems Engineering, Inc.
> Satellite Beach, Florida 32937
> (321) 777-7889
> www.wse.biz
> csturner@wse.biz
>
Hi Clay,

That really helped a lot! Thank you!

-Walala