DCT快速变换

核心提示：DCT变换过程可分为两部分：前向追底和后向回根前向追底：void dct_forward(double *f,int deg){// f中存储DCT数据int i_deg, i_halfwing, total, wing, wings, winglen, halfwing;double temp1,temp2;tota

DCT变换过程可分为两部分：前向追底和后向回根

前向追底：

void dct_forward(double *f,int deg)
{
　　　// f中存储DCT数据
　　　int i_deg, i_halfwing, total, wing, wings, winglen, halfwing;
　　　double temp1,temp2;
　　　total = 1 << deg;
　　　for(i_deg = 0; i_deg < deg; i_deg++)
　　　{
　　　　　　 wings = 1 << i_deg;
　　　　　　 winglen = total >> i_deg;
　　　　　　 halfwing = winglen >> 1;
　　　　　　 for(wing = 0; wing < wings; wing++)
　　　　　　 {
　　　　　　　　　　for(i_halfwing = 0; i_halfwing < halfwing; i_halfwing++)
　　　　　　　　　　{
　　　　　　　　　　　　　 temp1 = f[wing*winglen+i_halfwing];
　　　　　　　　　　　　　 temp2 = f[(wing+1)*winglen-1-i_halfwing];
　　　　　　　　　　　　　 if(wing%2)
　　　　　　　　　　　　　　　　　swap(temp1,temp2); // 交换temp1与temp2的值
　　　　　　　　　　　　　 f[wing*winglen+i_halfwing] = temp1+temp2;
　　　　　　　　　　　　　 f[(wing+1)*winglen-1-i_halfwing] =
　　　　　　　　　　　　　　　　(temp1-temp2)*C[winglen-1-i_halfwing];
　　　　　　　　　　}
　　　　　　 }
　　　}
}

后向回根：

void dct_backward(double *f,int deg)
{
　　　// f中存储DCT数据
　　　int total,i_deg,wing,wings,halfwing,winglen,i_halfwing,temp1,temp2;
　　　total = 1 << deg;
　　　for(i_deg = deg-1; i_deg >= 0; i_deg--)
　　　{
　　　　　　 wings = 1 << i_deg;
　　　　　　 winglen = 1 << (deg-i_deg);
　　　　　　 halfwing = winglen >> 1;
　　　　　　 for(wing = 0; wing < wings; wing++)
　　　　　　 {
　　　　　　　　　　for(i_halfwing = 0; i_halfwing < halfwing; i_halfwing++)
　　　　　　　　　　{
　　　　　　　　　　　　　 //f[i_halfwing+wing*winglen] = f[i_halfwing+wing*winglen];
　　　　　　　　　　　　　 if(i_halfwing == 0)
　　　　　　　　　　　　　 {
　　　　　　　　　　　　　　　　　　f[halfwing+wing*winglen+i_halfwing] =
　　　　　　　　　　　　　　　　　　　　0.5*f[halfwing+wing*winglen+i_halfwing];
　　　　　　　　　　　　　　}
　　　　　　　　　　　　　 else
　　　　　　　　　　　　　 {
　　　　　　　　　　　　　　　　　temp1=bitrev(i_halfwing,deg-i_deg-1);　 // bitrev为位反序
　　　　　　　　　　　　　　　　　temp2=bitrev(i_halfwing-1,deg-i_deg-1); // 第一参数为要变换的数
　　　　　　　　　　　　　　　　 // 第二参数为二进制长度
　　　　　　　　　　　　　　　　　f[halfwing+wing*winglen+temp1] =
　　　　　　　　　　　　　　　　　　　 f[halfwing+wing*winglen+temp1]-f[halfwing+wing*winglen+temp2];
　　　　　　　　　　　　　 }
　　　　　　　　　　}
　　　　　　 }
　　　}
}