基于雙調(diào)排序算法的蝶形圖，我們可以得到地址的變化規(guī)律。這里以長(zhǎng)度為16的雙調(diào)序列為例，其地址變化規(guī)律入下圖所示。由于長(zhǎng)度為16，故總共需要4個(gè)Stage。圖中每個(gè)Stage顏色的個(gè)數(shù)表明該Stage可分為的組數(shù)。例如Stage 0可分為1組，Stage 1可分為2組，Stage 2可分為4組，Stage 3可分為8組。

每組的起始地址和對(duì)應(yīng)的Stage緊密相關(guān)，例如Stage 1第0組起始地址為0，即(16/2^1)*0，第1組起始地址為8，即(16/2^1)*1。每組的地址個(gè)數(shù)也由Stage決定。例如Stage 1每組地址長(zhǎng)度為4，即16/2^(1+1)，Stage 2每組地址長(zhǎng)度為2，即16/2^(2+1)。同一組內(nèi)，相鄰地址的間距為1，例如Stage 1第0組的4個(gè)地址為[0,1,2,3]，相鄰地址間距為1，第1組的4個(gè)地址為[8,9,10,11]，相鄰地址間距為1。

一旦確定了op1的地址就很容易確定op2的地址，因?yàn)閮烧咧睿ㄓ胐iff表示）也是由Stage決定的。例如：Stage 0兩者之差為8，即16/2^(0+1)，Stage 1兩者之差為4，即16/2^(1+1)。

我們將地址規(guī)律總結(jié)為如下圖所示形式。這里一個(gè)重要的數(shù)據(jù)是Stage，其與序列長(zhǎng)度的關(guān)系可表示為Stage=log2(N)；另一個(gè)重要數(shù)據(jù)為diff，其與Stage關(guān)系可表示為diff=N/2^(Stage+1)。

在此基礎(chǔ)上我們就很容易借助C++或Matlab生成兩個(gè)操作數(shù)的地址。這里采用Matlab，相應(yīng)的Matlab函數(shù)如下圖所示。代碼第5行用于判斷序列長(zhǎng)度是否為2的整數(shù)次冪。

有了地址關(guān)系也就有了數(shù)據(jù)之間的關(guān)系。通常情況下，數(shù)據(jù)是按時(shí)間順序串行進(jìn)入的，所以我們也期望每次排序之后也是串行輸出的。根據(jù)數(shù)據(jù)流的關(guān)系，我們可以采用單路徑延遲反饋（Single-pathDelay Feedback, SDF）運(yùn)算單元流水結(jié)構(gòu)，SDF單元如下圖所示。

圖中butterfly為蝶形運(yùn)算單元，(2^P)D為延遲單元，延遲級(jí)數(shù)與所在Stage相關(guān)。仍以長(zhǎng)度為16的雙調(diào)序列為例，Stage 為0時(shí)，延遲級(jí)數(shù)為8，Stage 為1時(shí)，延遲級(jí)數(shù)為4，Stage為2時(shí)，延遲級(jí)數(shù)為2，Stage為3時(shí)延遲級(jí)數(shù)為1。圖中sel為分頻信號(hào)，仍與Stage相關(guān)，Stage為0時(shí)，sel為時(shí)鐘的8分頻信號(hào)，不難看出，分頻系數(shù)與延遲級(jí)數(shù)是一致的。

在此基礎(chǔ)上，將4個(gè)SDF相連即可實(shí)現(xiàn)串行輸入/串行輸出的雙調(diào)排序。下圖給出了Stage 0對(duì)應(yīng)的SDF結(jié)構(gòu)。

下圖顯示了相應(yīng)的仿真結(jié)果。

? 審核編輯：黃飛

?