What is the maximum value that can result from a 2D DCT?

Assuming that I have an 8x8 matrix of 8 bit unsigned values and carry out a 2D DCT on them, what is the biggest value that can result from it? This will help be decide how many bits to use. I am aware that the output coefficients are signed.

• well, I think you can solve this yourself. What's the formula of any term of the 2D DCT? Sep 6 '17 at 20:49

As suggested in the comments by Marcus Müller, you have to start from the equation of the DCT:

$$S_{uv} = \frac{1}{4} C_u C_v \sum_{y=0}^7 \sum_{x=0}^7 s_{xy} \cos\frac{(2x+1)u\pi}{16} \cos\frac{(2y+1)v\pi}{16}$$

The argument of the summation is of the magnitude of $$s_{xy}$$ times two values which are at most 1 (absolute value). So still 8 bits. You are summing $$8 \times 8 = 64$$ of those values, so $$2^6 \times 2^8 = 2^{14}$$. But you also divide this by $$\frac{1}{4}$$ so the maximum value requires 12 bits. You also have to consider that this value is obtained only when u anv v are 0, and in that case $$C_u=C_v=\frac{1}{\sqrt{2}}$$, so $$C_uC_v=\frac{1}{2}$$, that is another bit is unneeded. Some other checks are required when only $$u=0$$ or $$v=0$$, but overall you will need 11 bits at most.

This is exactly seen in the JPEG category tables for encoding the DCT coefficients.

For the skeptics, as you can see in the table below, when the input is in [0,255] the maximum values are always below 2048, thus 11 bits are enough. If your input is in [-255,255] you will need 12 bits.

0 1 2 3 4 5 6 7
0 2040 924,25 942,3571 924,25 1020 924,25 942,3571 924,25
1 924,25 837,4883 853,8957 837,4883 924,25 837,4883 853,8957 837,4883
2 942,3571 853,8957 870,6245 853,8957 942,3571 853,8957 870,6245 853,8957
3 924,25 837,4883 853,8957 837,4883 924,25 837,4883 853,8957 837,4883
4 1020 924,25 942,3571 924,25 1020 924,25 942,3571 924,25
5 924,25 837,4883 853,8957 837,4883 924,25 837,4883 853,8957 837,4883
6 942,3571 853,8957 870,6245 853,8957 942,3571 853,8957 870,6245 853,8957
7 924,25 837,4883 853,8957 837,4883 924,25 837,4883 853,8957 837,4883

You still have to add one more bit for the sign to the 11 bits correctly caclulated above, because DCT is signed, in fact you have to consider the situation when one of the cosines is positive and the other negative, hence you have to add 1 more bit and arrive to the 12 bits used by the MPEG standard in the fixed (Run,Level) codes (Level, the DCT value is ranged between -2047 and +2047, using 12 bits).

• No, you're wrong. The OP asked "Assuming that I have an 8x8 matrix of 8 bit unsigned values" and, as in my answer, you see that the range will be from 0 to 2040 for the DC coefficient and from -1020 to 1020 for the AC coefficients, meaning that 11 bits are enough. MPEG has to use 12 bits because in P and B pictures you encode differences, so the input value is from -255 to 255 effectively adding one more bit. Dec 8 '20 at 9:20