学士学位论文
Y?k??C?k??2m?1?kC2M??2Y?k?M （3-17）
2m?1?k???cos2M如果把式（3-16）的Y?k?分解成偶数序列和奇数序列，则式（3-15）改写成
x?m??g?m??h??m?x?M?1?m??g?m??h??m?,m?0,1,其中
（3-18） M?12g?m??h??m??由于
M?12?m?0?Y?2k?C2?MM?12?m?02m?1?2k （3-19）
2m?1??2k?1?2M?Y?2k?1?C??2m?1?2k?2m?1?k?2m?1?kC2?CM?C2M?M2? （3-20）
g?m?构成了一个
M点的IDCT。 2但对h??m?来说，还不是IDCT的表达式，还需要作一点修改，利用三角函数式：
2cos?cos??cos??????cos?????
得到如下关系：
2m?1?2C2MC2M2m?1??2k?1???C2M2m?1?2k??C2M2m?1?2?k?1? （3-21）
2m?1对式（3-19）中的h??m?两边乘以2C2M，得
M?12?k?0M?12?k?02m?1?2C2Mh?m???2m?1?2k?2m?1?2?k?1? （3-22） Y2k?1C?Y2k?1C??????2M2M若定义
Y?2k?1?|由于
?C2M2k?1?2?M2??k?0?0 （3-23）
2k?1???C2?0
M?12?k?0可将式（3-22）右边的第二项改写为
M?12?k?0?Y?2k?1?2M?2m?1?2?k?1???Y?2k?1?2M?2m?1?2k
于是，式（3-22）可以进一步化简为
12
学士学位论文
M?12h?m??2C显然h?m?为
2m?1M????h??m????Y?2k?1??Y?2k?1???2Mk?0??2m?1?2k （3-24）
M点的IDCT。 2将式（3-24）代入式（3-18），一个M点的IDCT就由两个
?2m?1??x?m??g?m???2C?2M?h?m??1M的IDCT来表示。即 2x?M?1?m??g?m????2C?2m?1?2M?h?m?,m?0,1,2,??1M,?12 （3-25）
及
g?m??M?12?k?0?Y2kC???2?M2m?1?k2??????2m?1?kh?m????Y?2k?1??Y?2k?1??C2?M2??k?0?M?12 （3-26）
类似于FFT，重复上述步骤，便可以进一步分解IDCT，直至2点的IDCT。由于DCT和IDCT的变换核一样，所以分解了IDCT，DCT的算法也自然就可以得到了。
3.3.3 代数分解法
仿效FFT的FDCT方法显然有与DCT毫无关系的复数运算部分，因此，要寻找一些更快的算法是十分必要的，代数分解法是快速DCT算法中的一种。
代数分解法直接对式（3-5）寻找类似于FFT的蝶形关系。其方法如下： （1）蝶形图用小圆圈表示操作数，用连接圆圈的直线表示操作数的流动，用直线上方或下方的函数表达式表示操作数在流向前方时需乘的加权因子。根据FFT要求，M是2的幂，且蝶形图的级数为2log2M。
?M（2）将x?0?，x?1?，?，x?M?1?以x??2?U1??x?0?,x?1?,???MU2??x???2??为界分为两个集合： ??M??,x??1???2???,x?M?1?????M?,x?1???,2???
分别称U1，U2为上半区和下半区。
（3）第一级的M个操作数分别为x?0?，x?1?，?，x?M?1?，第一级到第二级同行的圆圈用直线连接；下半区的直线上带有负号，第一级到第二级的另一组连接由第一级第i行到第二级的第M?i行连接，i?0,1,2,
13
,M?1。
学士学位论文
（4）第二级到第三级的连接，上半区采用（3）中的连接方法，但此时的操作数已减少了一半。重复运行这个操作直到log2M级为止。
（5）余下的操作数流向用加权因子确定具体的代数分解来做。 下面以M?8为例说明代数分解的过程： 根据式（3-5）可得M?8的DCT表达式为
7?2m?1?k?,k?0,1,1Y?k??C?k??x?m?cos216m?0,7
因此得到各分量的表达式为
Y?0?? ?Y?1??2?x?0??x?1??x?2??x?3??x?4??x?5??x?6??x?7???4?1?x0?x1?x2?x3?x4?x5?x6?x7cos???????????????????2?41??3?5?7?x0cos?x1cos?x2cos?x3cos????????2?16161616?9?11?13?15???x?5?cos?x?6?cos?x?7?cos16161616??
?x?4?cos ?1??3?x0?x7cos?x1?x6cos???????????????2??16?165?7????x3?x4cos???????16?16?
???x?2??x?5???cosY?2??1??3?5?7?x0cos?x1cos?x2cos?x3cos????????2?8888?9?11?13?15???x?5?cos?x?6?cos?x?7?cos8888?? ?x?4?cos ?
1??3??x0?x7?x3?x4cos?x1?x6?x2?x5cos????????????????????????2??8?8?Y?3??1?3?9?15?21?x0cos?x1cos?x2cos?x3cos????????2?16161616?27?33?39?45???x?5?cos?x?6?cos?x?7?cos16161616?? ?x?4?cos ?1?3?7?x0?x7cos?x1?x6cos???????????????2??16?16
???x?2??x?5???cos?16???x?3??x?4???cos5???16? 14
学士学位论文
Y?4??1??3?5?7?x0cos?x1cos?x2cos?x3cos????????2?4444?9?11?13?15???x?5?cos?x?6?cos?x?7?cos4444??
?x?4?cos ?1?x0?x7?x3?x4?x1?x6?x2?x5cos???????????????????????????????2?41?5?15?25?35?Y?5???x?0?cos?x?1?cos?x?2?cos?x?3?cos2?16161616?? ?x?4?cos ?45?55?65?75???x?5?cos?x?6?cos?x?7?cos16161616??1?5??x0?x7cos?x1?x6cos???????????????2??16?167?3????x3?x4cos???????16?16?
???x?2??x?5???cosY?6??1?3?9?15?21?x0cos?x1cos?x2cos?x3cos????????2?8888?27?33?39?45???x?5?cos?x?6?cos?x?7?cos8888?? ?x?4?cos ?
1?3???x0?x7?x3?x4cos?x1?x6?x2?x5cos????????????????????????2??8?8?Y?7??1?7?21?35?49?x0cos?x1cos?x2cos?x3cos????????2?16161616?63?77?91?105???x?5?cos?x?6?cos?x?7?cos16161616?? ?x?4?cos ?1?7?5?x0?x7cos?x1?x6cos???????????????2??16?163?????x3?x4cos???????16?16?
???x?2??x?5???cos由上述分解可以画出M?8时的DCT的蝶形图，如图 3.2所示。
15
学士学位论文
x?0? x?7? x?3? x?4? x?1?x?0? x?6? x?2? x?5? C7 C7 C1 1 2Y?1?
C1 C3 1 2C5 C5 C3 C3 C3 C5 Y?7?
C1 C1 C5 C7 C7 C6 C6 12121C2 212C2 1C4 212C4 Y?3?
Y?5?
Y?2?
Y?6?
Y?0?
Y?4?
图 3.2 M?8时的DCT的蝶形图
由此看到DCT蝶形操作与FFT一样，也导致了比特逆序，但在量化、解码时立即又可将这种逆序变为正序。图 3.3中表述了图 3.2中每一级输出与输入以及各级系数的关系。
I0 I1 Cm2 Cm3 Cm1 O0
O0?I0Cm1?I1Cm3 O1?I0Cm2?I1Cm4
Cm4 O1
图 3.3 算法中输出和输入的关系
3.4 DCT系数的量化
系数量化是一个十分重要的过程，它将每个DCT系数除以各自的量化步长并取整值，从而得到量化系数，是造成DCT编解码信息损失或失真的根源。
DCT是一个无损变换，只要正、反变换所用的设备计算精度足够高，且未经过量化，那么原始的样值能精确地恢复。其实经DCT变换后并没有压缩数据，反而使原本是整
16