快速傅里叶变换蝶形公式如何理解

Question

// 采用蝶形算法进行快速傅里叶变换
for(k = 0; k < r; k++)
{
for(j = 0; j < 1 << k; j++)
{
bfsize = 1 << (r-k);
for(i = 0; i < bfsize / 2; i++)
{
p = j * bfsize;
X2[i + p] = X1[i + p] + X1[i + p + bfsize / 2];
X2[i + p + bfsize / 2] = (X1[i + p] - X1[i + p + bfsize / 2])
* W[i * (1<<k)];

}
}
X = X1;
X1 = X2;
X2 = X;
}
————————————
其中
X2[i + p] = X1[i + p] + X1[i + p + bfsize / 2];
X2[i + p + bfsize / 2] = (X1[i + p] - X1[i + p + bfsize / 2])
* W[i * (1<<k)];
这两句不太明白,看蝶形图,不是应该
X2[i+p] = X1[i+p] + x1[i+p+bfsize/2]*W;
X2[i + p + bfsize / 2] = X1[i + p] - X1[i + p + bfsize / 2]*W;
哪位大神能帮帮看下，初学，分少

Answer 1

http://wenku.baidu.com/link?url=wl7ybYV9fniv7KMEJZ1bc_FhzFWJ2ncHlXcfbX-eW9Lz_pisEtUH9-DW1NAWk8y7nEm03QVGQ14hi7GElC39VOW59XT6GRYkFFXge816lTS