1.什么是傅里叶变换
傅里叶变换能将满足一定条件的某个函数表示成三角函数（正弦和/或余弦函数）或者它们的积分的线性组合。在不同的研究领域，傅里叶变换具有多种不同的变体形式，如连续傅里叶变换和离散傅里叶变换。最初傅里叶分析是作为热过程的解析分析的工具被提出的。(摘抄自百度百科）
连续傅里叶变换的公式
连续傅里叶变换的逆变换的公式
通过公式可以看出一个函数，可以用复指数函数的积分来表示，如果通过欧拉公式变换，也可以用三角函数的积分来表示，其中 F(w)表示的是在某频率下的幅值，而 w为基波频率，iw表示频率，一般的傅里叶函数的曲线表示为iw为横轴，F(w)为纵轴。
傅里叶变换可以把一个函数从t域，也就是时域，变换到w域，也就是频域。通过傅里叶变换可以很方便的看出当前信号的频域特性。
2.什么是离散余弦变换
图像的各个像素点之间的变化都是平滑变化的，所以每个像素点和相邻像素点之间都是相关的，而这种相关性对图像的熵编码很不利，详细请查看信息熵的一些资料。所以我们必须通过某种变换，将图像的各个像素之间的相关性去除，其中去相关最好的算法，目前为K-L变换，但是缺乏快速算法，并且变换矩阵不固定，详细可以查看相关资料。目前常用的是离散余弦变换（DCT），由于其良好的去相关效果，可以较快的变换算法，在多媒体编码算法中得到了广泛的使用。
二维DCT变换及其逆变换的公式如下图：
DCT变换不是傅里叶变换，只是其形式有点像傅里叶变换而已。
3.DCT的整数变换
由于三角函数中会有很多小数的部分，不利于计算机处理，所以将小数部分提取出来，在量化中进行处理。具体如下图
前面三个矩阵的运算都为加法，减法，和移位（ *2)运算。
4.蝶形算法
两个4x4矩阵的乘法分解开来会有12次加法和16次乘法运算，而根据DCT变换举证的特性，如果我们合并一些中间结果，就可以减少为8次加法，2次乘法运算。这就是著名的蝶形算法,如下图所示：
5.汇编代码分析
DCT的算法和hadamard变换的算法基本相同，只是某一些系数稍微有点不同，如上图所示。
所以我们只分析hadamard的变换
;-----------------------------------------------------------------------------
; void x264_idct4x4dc_mmx( int16_t d[4][4] )
;-----------------------------------------------------------------------------
;DC分量的hadamard逆变换
cglobal x264_idct4x4dc_mmx, 1,1
movq m3, [r0+24]
movq m2, [r0+16]
movq m1, [r0+ 8]
movq m0, [r0+ 0] ;矩阵中每一个元素都是16bit,所以每一行都是8个字节
WALSH4_1D 0,1,2,3,4 ;一维harmand变换在x86util.asm中有定义，下面会有详细说明
TRANSPOSE4x4W 0,1,2,3,4 ;转置
WALSH4_1D 0,1,2,3,4 ;继续做一维harmand变换
movq [r0+ 0], m0
movq [r0+ 8], m1
movq [r0+16], m2
movq [r0+24], m3
RET
%macro WALSH4_1D 5
SUMSUB_BADC m%4, m%3, m%2, m%1, m%5 ; 蝶形算法的前半部分
SUMSUB_BADC m%4, m%2, m%3, m%1, m%5 ; 蝶形算法的后半部分
SWAP %1, %4, %3
%endmacro
%macro SUMSUB_BADC 4-5
%if %0==5
SUMSUB_BA %1, %2, %5 ;第一行和第二行的加法和减法结果
SUMSUB_BA %3, %4, %5 ;第三行和第四行的加法和减法结果
%else
paddw %1, %2
paddw %3, %4
paddw %2, %2
paddw %4, %4
psubw %2, %1
psubw %4, %3
%endif
%endmacro
%macro SUMSUB_BA 2-3 ;对两行做加法和减法，并保存结果
%if %0==2
paddw %1, %2
paddw %2, %2
psubw %2, %1
%else
mova %3, %1
paddw %1, %2
psubw %2, %3
%endif
%endmacro