[發明專利]一種基于數字信號處理的高效并行處理優化方法

有效

• 申請號: 201410341689.4
• 申請日: 2014-07-18
• 公開（公告）號: CN104142811B
• 公開（公告）日: 2017-02-01
• 發明（設計）人: 王向前;方志紅;賈光帥;耿銳;郭二輝;洪一
• 申請（專利權）人: 中國電子科技集團公司第三十八研究所
• 主分類號: G06F9/38
• 分類號: G06F9/38
• 代理公司: 合肥金安專利事務所34114
• 代理人: 吳娜

1.一種基于數字信號處理的高效并行處理優化方法，其特征在于該方法包括下列順序的步驟：

（1）進行基于置換的原位逆序的除高/低part之外的部分逆序；

（2）三階/四階合并；

（3）中間的二階合并循環；

（4）最后兩階計算/最終逆序。

2.根據權利要求1所述的一種基于數字信號處理的高效并行處理優化方法，其特征在于：所述基于置換的原位逆序分為以下迭代步驟：

步驟一：把N個復數的輸入序列?(A(0),A(1),A(2),…，A(N-1))看成一個步長因子為1組成的1個子序列，把前N/2序列的奇數序列和后N/2序列的偶數序列對應置換，即前半部分序列(A(0),A(1),A(2),…，A(N/2-1))的奇數部分A(1),A(3),A(5)?，…，A(N/2-1)和后半部分序列A(N/2),A(N/2+1),?A(N/2+2),…，A(N-1)的偶數部分A(N/2),A(N/2+2),…，A(N-2)依次對應置換；

步驟二：把步驟一置換后的序列看成是一個步長因子為2組成的4個序列,其中前兩個子序列在前N/2位置上，兩個子序列交迭分布,即這兩個子序列為(A(0),A(2),…，A(N/2-2))和(A(1),A(3),…，A(N/2-1))；后兩個子序列在后N/2位置上，兩個序列交迭分布,即這兩個子序列為(A(N/2),A(N/2+2),…，A(N-2))和(A(N/2+1),A(N/2+3),…，A(N-1))；把4個子序列各自的前半部分的奇數部分和后半部分的偶數部分依次對應置換；

步驟三：把步驟二置換后的序列看成是一個步長因子為4組成的16個子序列，其中0～3個子序列在位置0～（N/4-1)上，四個子序列交迭分布,即這四個子序列為(A(0),A(0+4),?A(0+8)，…，)，?(A(1),A(1+4),?A(1+8),…，)，?(A(2),A(2+4),?A(2+8),…，)?，(A(3),A(3+4),?A(3+8),…，)；其中4～7個子序列在位置N/4～（N/2-1)上，四個子序列交迭分布,即這四個子序列為(A(N/4+0),A(N/4+0+4),?A(N/4+0+8)，…，)，?(A(N/4+1),A(N/4+1+4),?A(N/4+1+8),…，)，?(A(N/4+?2),A(N/4?+?2+4),?A(N/4?+?2?+?8),…，)?，(A(N/4?+?3),A(N/4?+?3?+?4),?A(N/4?+?3+8),…，)；其中8～11個子序列在位置N/2～（3*N/4-1)上，四個子序列交迭分布,即這4個子序列為(A(N/2+0),A(N/2+0+4),?A(N/2+0+8)，…，)，?(A(N/2+1),A(N/2+1+4),?A(N/2+1+8),…，)，?(A(N/2+?2),A(N/2+?2+4),?A(N/2+?2?+?8),…，)?，(A(N/2?+?3),A(N/2?+?3?+?4),?A(N/2?+?3+8),…，)；其中11～15個子序列在位置3*N/4～（N-1)上，四個子序列交迭分布,即這4個子序列為(A(3*N/4+0),A(3*N/4+0+4),?A(3*N/4+0+8)，…，)，?(A(3*N/4+1),A(3*N/4+1+4),?A(3*N/4+1+8),…，)，?(A(3*N/4+?2),A(3*N/4+?2+4),?A(3*N/4+?2?+?8),…，)?，(A(3*N/4+?3),A(3*N/4?+?3?+?4),?A(3*N/4?+?3+8),…，)；把16個子序列各自的前半部分的奇數部分和后半部分的偶數部分依次對應置換；

步驟四：把步驟三置換后的序列按照步長因子是上一次迭代步長因子的2倍、子序列個數是上一次迭代子序列個數的4倍的方法劃分出若干個子序列，依次對該若干個子序列進行各自的前半部分的奇數部分和后半部分偶數部分的進行置換；

步驟五：把整個序列的多個子序列每次所完成的置換作為一個迭代步驟，那么總迭代步驟為R/2次，該值向下取整，R為LogN。

3.根據權利要求1所述的一種基于數字信號處理的高效并行處理優化方法，其特征在于：所述原位部分逆序是指：首先把輸入序列按照高part位連續劃分成為幾個大塊；其次將低part位則作為一個整體小塊參與塊原位置換；最后，部分逆序轉化為求解(R-2*part)個中間位的逆序操作，此時則可利用原位逆序方法完成輸入序列的部分逆序過程。