2
$\begingroup$

I'm a newcomer to the DCT, DFT etc. I understand that they're intrinsically related, I understand that the DCT tends to "compress" the information in a signal towards the first few bins, leaving the rest relatively close to zero. I'm trying to learn more.

DCT has different "types". Based on reading wikipedia, the types mainly differ in adding 0.5 to either the input index, the output index, or both, when computing the matrix coefficients. Type 1 does neither, type 4 does both, and 2/3 do one or the other.

It's not clear why types 2, 3, or 4 would ever valuable. What benefit does shifting the input or output signal by half give? What are some examples of applications that are well-suited for DCT type 2,3 or 4, but are not well suited for DCT type 1? If I have an array of floats that I want to compute a DCT on, what factors should go into an educated decision on which type to use?

$\endgroup$
4
  • 2
    $\begingroup$ i think Wikipedia has a good page on this. $\endgroup$ Jun 19 '16 at 5:31
  • $\begingroup$ They don't. I looked. Thanks for the downvote though. $\endgroup$
    – Elliott M
    Jun 19 '16 at 8:12
  • $\begingroup$ What do you want to use them for? $\endgroup$ Jun 19 '16 at 11:38
  • 1
    $\begingroup$ i didn't downvote you (i very rarely downvote questions, only if i think they are extremely lame-o). see, i'll add one and move you from -2 to -1. $\endgroup$ Jun 20 '16 at 4:48
3
$\begingroup$

As you described correctly, DCT is closely related to DFT. The two main motivations behind DCT are it's being a real transform and its compaction of signal energy. The first makes it computationally simpler, while the second makes it a prime tool for transform based lossy data compression applications. As you understood correctly.

Then what remains is where the types come from and why is it the DCT-II as the most common choice for data compression? The answer is as follows:

Given a signal $x[n]$ of length $N$, The different DCTs are defined by forming even-symmetric extensions of shifted copies $x[n]$ in a number of possible ways, each different combination yielding a different type of DCT. Also the odd-symmetric extensions are called as the DST (Discrete Sine Transform).

The DCT-II , by virtue of its type of symmetry, has the most energy compaction among other DCT types and therefore is naturally the choice.

The DCT-II signal formation (based on A.Opp DTSP-2e) is as follows:

Consider a signal $x[n]$ of length N, whose DCT-II we want to compute. First extend $x[n]$ by padding $N$ zeros and create the extended signal $x_e[n]$

Then the DCT Type-II signal $\tilde{x}_2[n]$ is a periodic signal with period $2N$ and related to $x_e[n]$ as: $$\tilde{x}_2[n] = x_e[((n))_{2N}] + x_e[((-n-1))_{2N}]$$ whose base period $x_2[n]$ extends from $n=0$ to $n=2N-1$. And where the $((\cdot))_{N}$ operation here is the modulus operator, providing the periodicity of $\tilde{x}_2[n]$.

Eventually, it is shown that the $N$-Point unnormalised DCT-II, $X_{c2}[k]$, of the signal $x[n]$ is related to the $2N$-Point DFT, $X_2[k]$, of the signal $x_2[n]$ as: $$X_{c2}[k] = e^{-j\pi k/{2N}} X_2[k]$$ for $k=0$ to $k=N-1$

The following Matlab script creates the Type-II DCT signal $x_2[n]$ from $x[n]$ and finds DCT of x[n] from DFT of x2[n] for comparison

N=8;                            % Period for x[n]
n = [0:2*N-1];                  % A set of sequence indices of at least length 2N
x = [1:N];                      % A ramping test sequence for x[n] of period N
xe = [x zeros(1,N)];            % Extended sequence from x[n], by padding N zeros
x2 = xe(1 + mod(n,2*N)) + xe(1 + mod(-n-1,2*N));    % DCT-II type periodic signal
DFTx2 = fft(x2,2*N);            % 2N-Point DFT of x2[n]
Dft2Dct = real( exp(-j*pi*[0:N-1]./(2*N)).*DFTx2(1:N) );   % Create N-DCT of x[n] from 2N-DFT of x2[n]
DCTx = sqrt(2*N).*dct(x,N);     % N-POint DCT of x[n], for test purposes
DCTx(1)= sqrt(2)*DCTx(1);       % UNnormalise the Matlab's default normalised DCT-II
$\endgroup$
4
  • $\begingroup$ What does even vs odd symmetry refer to? If I had to guess it would be symmetry of the corresponding DFT output. Is that close? $\endgroup$
    – Elliott M
    Jun 19 '16 at 18:38
  • $\begingroup$ Or perhaps it means that each frequency which x[n] is scaled by before being added to X[k] is symmetric-even? $\endgroup$
    – Elliott M
    Jun 19 '16 at 20:34
  • $\begingroup$ The symmetry here means the same as in the ordinary sense such as $x[n]=x[-n]$ being an even symmetric signal and $x[n]=-x[-n]$ being odd. Keeping in mind also the inherent periodicty of the DFT/DCT signals. $\endgroup$
    – Fat32
    Jun 19 '16 at 20:53
  • $\begingroup$ Let me provide an example for DCT-II $\endgroup$
    – Fat32
    Jun 19 '16 at 20:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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