拟带宽 Toeplitz 系统的秩 1 修正算法

本文以带宽Ｔｏｅｐｌｉｔｚ系统的快速并行解法为基础,通过建立秩１的修正格式讨论了拟带宽Ｔｏｅｐｌｉｔｚ系统的一种快速并行算法,其串行运算量为９ｎｈ＋Ｏ（ｈ）．设ｐ为处理机台数,当ｐ≤ｎ时,并行运算量为　;当ｐ＝３ｎ时,运算量为２ｈ￣２ｌｏｇ２ｎ＋Ｏ（１）,其中ｈ表示拟带宽宽度。     

多元多项式乘积的 FPT算法

本文详细讨论了多元多项式乘积的多项式变换(FPT)算法。首先给出了二元的情况,然后推广到了一般多元多项式,最后给出了这种算法在计算二维循环卷积中的应用,由此可见,这种算法在计算多维卷积和多维DFT 时是很有效的。     

具有循环卷积特性(CCP)的矩形变换

本文提出了一个计算卷积的新方法,它是Cook-Toom法的改进,但比后者简便,且可利用已知短卷积的结果,所需乘法次数与Cook-Toom一样为2N-1;然后一般地讨论了矩形变换y=C{(Ah)(?)(Bx)}具有CCP的条件,并且用此条件证明DFT及NTT具有CCP;再给矩形变换更多的限制,证明了变换A具有CCP的充要条件,并证明了这时必有逆,同时给出了逆的形式;最后将上面讨论的结果推广到整数环Z_p中去,得出了Z_p中具有CCP的可逆变换的一般形式。     

复数数论变换

一、引言通常的离散福里哀变换(DFT)是将时域信号变换为谱,或将谱反变换为时域信号。在信号处理及传递中,利用谱进行研究往往比利用时域信号更为方便。随着计算技术的不断进步,在信号处理中使用变换法更为大家所关心。数论变换是近几年才发展起来的一种新型变换。Pollard在[1]中对于由有限域(Galois field)或以一自然数为模的整数环中的元素所构成的序列的循环卷积给出了结果。Rader[2],Agarwal和Burrus[3],