计算二维数字卷积的二维重叠保留法

AN OVERLAP SAVE METHOD FOR THE CALCULATION OF THE TWO DIMENSIONAL DIGITAL CONVOLUTION

设ｈｋ２，ｋ２代表滤波器的系数（ｋ１＝０，１，…，ｌ２－１，ｋ２＝０，１，…，ｍ２－１），ｘｎ１，ｎ２和ｎ１，ｎ２（ｎ１＝０，１，…，ｌ１－１，ｎ２＝０，１，…，ｍ１－１）分别代表滤波器的输入和输出，本文给出了计算ｙｎ１，ｎ２（它是ｘｎ１，ｎ２和ｈｎ１，ｎ２的线性卷积）的二维重叠保留法，这是一维重叠保留法的推广和发展．在许多应用中，输入和输出的长度很长，相比之下，滤波器的系数长度较短．如果用直接的方法计算ｙｎ１，ｎ２，其乘法运算的个数将很大．本文指出在数字信号处理领域中用重叠保留法计算ｙｎ１，ｎ２是有效的．这一方法通过计算一系列长为Ｎ和Ｍ的循环卷积来计算ｙｎ１，ｎ２（ｎ１＝０，１，…，ｌ１－１，ｎ２＝０，１，…，ｍ１－１），这里Ｎ＝２ｄ，Ｍ＝２ｄ′，Ｎ＝Ｎ′＋ｌ２－１＜ｌ１，Ｍ＝Ｍ′＋ｍ２－１＜ｍ１．所以能够用快速数论变换（ＦＮＴＴ）或快速付里叶变换（ＦＦＴ）计算循环卷积．这有可能使我们用这一方法处理一个无限输入序列ｘｎ１，ｎ２和有限滤波器系数ｈｋ１。

The authors give an Overlap save algorithm for the calculation of the two dimensional digital convolution by supposing that h k 1,k 2 are the filter coefficients ( k 1 =0,1,…, l 2-1,k 2=0,1,…,m 2-1 ), x n 1,n 2 and y n 1,n 2 ( n 1=0,1,…,l 1,n 2=0,1,…,m 1-1) are the input and output of the filter,respectively.In many DSP applications the lengths l 1 and m 1 are very long but lengths l 2 and m 2 are short.So, if using overlap save method to calculate y n 1,n 2 which is the convolution of two 2 dimensional sequence x n 1,n 2 and h n 1,n 2 ,then the number of multiplication is small in many particular cases.