Discreet Cosine Transform IV
N point DCT-IV with an N/2 point complex DFT
The DCT-IV is defined as
\[X_k = \sum_{n=0}^{N-1} x_{n} cos(\frac{\pi}{N}(n+\frac{1}{2})(k+\frac{1}{2}))\]It's possible to perform this calculation with the DFT using a transform on the inputs to the DFT and a transform on the outputs of the DFT. The derivation starts by first dividing the ouputs into even and reversed-odd series:
\[X_{2k} = \sum_{n=0}^{N-1} x_{n} cos(\frac{\pi}{N}(n+\frac{1}{2})(2k+\frac{1}{2}))\] \[X_{N-2k-1} = \sum_{n=0}^{N-1} x_{n} cos(\frac{\pi}{N}(n+\frac{1}{2})(N-2k-\frac{1}{2}))\] \[X_{N-2k-1} = \sum_{n=0}^{N-1} x_{n} cos(\pi (n+\frac{1}{2}) - \frac{\pi}{N}(n+\frac{1}{2})(2k+\frac{1}{2}))\]Next these series are written out as the sum of a series of the even inputs and a series of the reversed-odd inputs. For even outputs
\[X_{2k} = \sum_{n=0}^{N/2-1} x_{2n} cos(\frac{\pi}{N}(2n+\frac{1}{2})(2k+\frac{1}{2})) + \sum_{n=0}^{N/2-1} x_{N-2n-1} cos(\frac{\pi}{N}(N-2n-\frac{1}{2})(2k+\frac{1}{2}))\] \[X_{2k} = \sum_{n=0}^{N/2-1} x_{2n} cos(\frac{\pi}{N}(2n+\frac{1}{2})(2k+\frac{1}{2})) + \sum_{n=0}^{N/2-1} x_{N-2n-1} cos(\pi (2k+\frac{1}{2}) - \frac{\pi}{N}(2n+\frac{1}{2})(2k+\frac{1}{2}))\] \[X_{2k} = \sum_{n=0}^{N/2-1} x_{2n} cos(\frac{\pi}{N}(2n+\frac{1}{2})(2k+\frac{1}{2})) + \sum_{n=0}^{N/2-1} x_{N-2n-1} sin(\frac{\pi}{N}(2n+\frac{1}{2})(2k+\frac{1}{2}))\]And for odd outputs
\[X_{N-2k-1} = \sum_{n=0}^{N/2-1} x_{2n} cos(\pi (2n+\frac{1}{2}) - \frac{\pi}{N}(2n+\frac{1}{2})(2k+\frac{1}{2})) + \sum_{n=0}^{N/2-1} x_{N-2n-1} cos(\pi (N-2n-\frac{1}{2}) - \frac{\pi}{N}(N-2n-\frac{1}{2})(2k+\frac{1}{2}))\] \[X_{N-2k-1} = \sum_{n=0}^{N/2-1} x_{2n} cos(\frac{\pi}{2} - \frac{\pi}{N}(2n+\frac{1}{2})(2k+\frac{1}{2})) + \sum_{n=0}^{N/2-1} x_{N-2n-1} cos(-\frac{\pi}{2} - \pi (2k+\frac{1}{2}) - \frac{\pi}{N}(2n+\frac{1}{2})(2k+\frac{1}{2}))\] \[X_{N-2k-1} = \sum_{n=0}^{N/2-1} x_{2n} sin(\frac{\pi}{N}(2n+\frac{1}{2})(2k+\frac{1}{2})) - \sum_{n=0}^{N/2-1} x_{N-2n-1} cos(\frac{\pi}{N}(2n+\frac{1}{2})(2k+\frac{1}{2}))\]The last relations can be rewritten as
\[ X_{2k} = Re( \sum_{n=0}^{N/2-1} (x_{2n} + ix_{N-2n-1}) e^{\frac{\pi}{N}(2n+\frac{1}{2})(2k+\frac{1}{2})} ) \] \[ X_{N-2k-1} = -Im( \sum_{n=0}^{N/2-1} (x_{2n} + ix_{N-2n-1}) e^{\frac{\pi}{N}(2n+\frac{1}{2})(2k+\frac{1}{2})} ) \]Expanding the exponent and rearranging the terms, the series can be written as
\[ e^{-i \pi (k + \frac{1}{8}) / N} \sum_{n=0}^{N/2-1} (x_{2n} + ix_{N-2n-1}) e^{-i \pi (n + \frac{1}{8}) / N} e^{\frac{-i2\pi nk}{N/2}} \]And defining y and Y as the input and output of the DFT:
\[ y_n = (x_{2n} + ix_{N-2n-1}) e^{-i \pi (n + \frac{1}{8}) / N} \] \[ Y_k = \sum_{n=0}^{N/2-1} y_n e^{\frac{-i2\pi nk}{N/2}} \]The outputs can be written as
\[ X_{2k} = Re( e^{-i \pi (k + \frac{1}{8}) Y_k} ) \] \[ X_{N-2k-1} = -Im( e^{-i \pi (k + \frac{1}{8}) Y_k} ) \]So the algorithm involves reversing the odd inputs, then treating the input as N/2 complex numbers and multiplying by a chirp, performing the DFT, multiplying the output by a chirp, and reversing and negating the imaginary output components
References
- Uses javascript SyntaxHighlighter for syntax highlighting.
- Uses javascript MathJax for LateX rendering.
To the extent possible under law,
Craig Hughes
has waived all copyright and related or neighboring rights to
the text and source code in this example/tutorial.