zadoff 码的超级快速的傅立叶变换

(录制的视频：https://www.bilibili.com/video/BV1EY4y1T7DY/）

一般的 zadoff 码, 其数学表达式可以写成:  

这个函数是以 L 为周期的
证明:  

zadoff 码长一般为质数，L>2 时 L 一定为奇数, 所以, L+1 一定为偶数  
所以  

证毕.  

对 ZC 序列做 DFT：  

把  的表达式代入上式：

找一个自然数 v, 使得 uv mod L = 1, 构造一个表达式：

把公式 (1) 中提取出上式:  

因为 uv 模 L 余 1, 所以，可以把 uv 乘在分子的任何一项上，容易证明，乘完之后不改变原等式.  

其中  

所以  

上式中的求和项, 也是一个 zadoff 码, 因为 zadoff 码是以 L 为周期的周期函数, 所以，第二个求和项可以等价替换:  

当 k=0 时:

当 k = 1 时,

其中  表示 的共轭  
可以看到，Y[k] 可以用 Y[0] 和 某一个 的共轭相乘即可得到, 这要比 DFT 的计算量要少很多，即使与 FFT 比较也计算量要少不少

依次类推，

当 k = 2 时,

一般化：