I'm having trouble figuring out how to follow the fast 8x8 DCT algorithm diagrams found in the following two papers:
(1) A Fast Computational Algorithm for the Discrete Cosine Transform by Chen et al.
and
(2) Practical Fast 1-D DCT Algorithms With 11 Multiplications by Loeffler et al.
In particular, the second diagram that shows the algorithm in (2) looks like the following:
The description of the operations in this algorithm are:
There are a few questions I have about this formulation, and I'm not sure where to find the answers:
(2) suggests that this algorithm generates a DCT that is scaled by some value $C = \sqrt{2}$. It mentions that this $C$ was chosen arbitrarily to avoid any multiplications in computing the DC coefficient. Really the only requirement is that $C_{DCT} * C_{IDCT} = \frac{4}{N^2}$. So my question is this: What is the scaling factor of the output coefficients using this algorithm? It seems like they are different than the original definition of the DCT, but I don't know by how much (mostly because I don't actually see any relationship between this diagram and the original formulation of the DCT): $$ F(k) = \frac{2c(k)}{N}\sum_{n = 0}^{N - 1}f(n)\cos\left(\frac{\left(2n + 1\right)\pi k}{2N}\right)$$ where $c(k) = \frac{1}{\sqrt{2}}$ for $k = 0$ and $c(k) = 1$ for $k \neq 0$.
The paper states that performing the IDCT can be done using the exact same algorithm but transforming outputs to inputs and vice versa. First, should the DCT coefficients be ordered in bit-reverse order prior to running them through the IDCT? Second, for the rotation blocks (the squares in the diagram), shouldn't the inverse operation be: $$ \begin{align} O_0 = I_0 \cdot k \cdot \cos\frac{n\pi}{2N} - I_1 \cdot k \cdot \sin\frac{n\pi}{2N} \\ O_1 = I_1 \cdot k \cdot \sin\frac{n\pi}{2N} + I_1 \cdot k \cdot \cos\frac{n\pi}{2N} \\ \end{align} $$ My reasoning is this: The inverse of a rotation by $\theta$ is a rotation by $-\theta$. Hence, we just replace the angle by its inverse and use the identities $\cos(-\theta) = \cos(\theta)$ and $\sin(-\theta) = -\sin(\theta)$. Third, what is the scaling factor of the transformed values after the IDCT? (2) says $\frac{2}{N^2}$, but empirically, this hasn't produced correct results.
Suppose after I run the algorithm, I have the result of each lane stored in the values
d0 ... d7
. Which of the following is correct:output[0] = d0 or output[0] = d0 output[4] = d1 output[1] = d4 output[2] = d2 output[2] = d2 output[6] = d3 output[3] = d6 output[7] = d4 output[4] = d7 output[3] = d5 output[5] = d3 output[5] = d6 output[6] = d5 output[1] = d7 output[7] = d1
If there are any ways to improve this question, or if I should ask elsewhere, please let me know.