有限域上傅立叶变换的一种新的快速算法

摘要

本文提出了一种计算任意有限域GF（Pm）上n=Pm-1点傅立叶变换的快速算法。其运算规则,适于串行流水处理,GF（Pm）上乘和加运算量都是O（n log~2n）,在某些域上乘法可减到O（n log n）。文中给出了此算法的流图和硬件实现框图,并估计了其运算量和硬件实现速度。这种算法对于利用谱技术进行纠错码的编译码有重要的意义,也可用于有限域上多项式的快速求值。