吳朋庭，李 軍，何衛(wèi)國(guó)，王明東

（成都三零嘉微電子有限公司，四川 成都 610041）

0 引 言

Butterfly網(wǎng)絡(luò)廣泛應(yīng)用于比特?cái)U(kuò)散、比特循環(huán)移位等動(dòng)態(tài)比特置換運(yùn)算模塊的硬件實(shí)現(xiàn)。以往的研究主要集中于挖掘其數(shù)據(jù)通路的遞歸特性[1-6]。例如，比特?cái)U(kuò)散運(yùn)算。在每一層置換參數(shù)求解的過程中，Lee發(fā)現(xiàn)了一些Butterfly置換網(wǎng)絡(luò)的遞歸特性，并利用這些特性對(duì)部分運(yùn)算過程進(jìn)行了簡(jiǎn)化[1]。簡(jiǎn)化的過程非常精妙甚至有些偶然，然而在數(shù)學(xué)的世界里面，偶然現(xiàn)象一定存在其必然的數(shù)學(xué)理論。所以，無論研究人員歸納出的Butterfly置換網(wǎng)絡(luò)結(jié)構(gòu)的遞歸特性多么精妙，都是建立在它的數(shù)學(xué)理論基礎(chǔ)之上的衍生特征。只要充分利用其數(shù)學(xué)理論對(duì)運(yùn)算進(jìn)行推導(dǎo)，就可能獲得優(yōu)化程度不低于現(xiàn)有遞歸算法的方案。

本文旨在研究Butterfly網(wǎng)絡(luò)的置換數(shù)學(xué)理論及其應(yīng)用。首先采用數(shù)字與符號(hào)對(duì)Butterfly網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行定義，其次利用這些定義總結(jié)歸納Butterfly網(wǎng)絡(luò)結(jié)構(gòu)的數(shù)學(xué)理論并予以證明，最后利用Butterfly網(wǎng)絡(luò)的數(shù)學(xué)理論重新分析比特?cái)U(kuò)散和循環(huán)移位等特殊的置換運(yùn)算，以期得到優(yōu)化程度更好的硬件實(shí)現(xiàn)方案或者更加簡(jiǎn)單的置換參數(shù)求解過程，為研究人員進(jìn)一步分析其他置換運(yùn)算提供新的思路。

1 Butterfly網(wǎng)絡(luò)的數(shù)學(xué)理論

圖1為一個(gè)Butterfly置換網(wǎng)絡(luò)結(jié)構(gòu)，N（N=2n）比特?cái)?shù)據(jù)對(duì)應(yīng)的Butterfly置換網(wǎng)絡(luò)的寬度為N，路由深度為n。

為了描述它的結(jié)構(gòu)特征，需要引入一些定義。

原始數(shù)據(jù)從右到左第jn比特稱為起點(diǎn)s(jn)，目標(biāo)數(shù)據(jù)從右到左第j0比特稱為終點(diǎn)e(j0)，中間第i層數(shù)據(jù)從右到左第ji比特稱為路由點(diǎn)r(i,ji)，第i+1層路由點(diǎn)r(i+1,ji+1)到第i層路由點(diǎn)r(i,ji)之間的路線稱為路由線l(i,ji+1→ji)，路由線l(i,ji+1→ji)在橫坐標(biāo)上投影的最大距離稱為路由權(quán)重w(i)，且w(i)=2i。

以權(quán)重w(i)為寬度，第i層數(shù)據(jù)被劃分的2n-i個(gè)區(qū)間稱為路由區(qū)間 b(i,k)=[(k+1)×2i-1,k×2i]，(0≤k≤2n-i-1)。當(dāng)k為奇數(shù)時(shí)，b(i,k)為奇區(qū)間ob(i,k)；當(dāng)k為偶數(shù)時(shí)，b(i,k)為偶區(qū)間eb(i,k)。路由線l(i,ji+1→ji)從上而下劃過的方向在橫坐標(biāo)上的投影稱為路由方向d(i,ji+1→ji)，且當(dāng)ji∈ob(i,k)時(shí) d(i,ji+1→ji)∈ {0,1}，當(dāng) ji∈ eb(i,k)時(shí) d(i,ji+1→ji)∈{-1,0}，其中“1”“-1”“0”分別表示向左、向右和保持。

從起點(diǎn)s(jn)出發(fā)，途經(jīng)各層路由點(diǎn)r(i,ji)并最終到達(dá)終點(diǎn)e(j0)劃過的所有路由線l(i,ji+1→ji)的首尾相連的組合稱為s(jn)到r(i,ji)的路由路徑p(jn,j0)。將路由路徑經(jīng)過的所有路由點(diǎn)對(duì)應(yīng)的路由方向剝離符號(hào)后得到的元素d[i]組成路由向量d={d[n-1],d[n-2],…,d[1],d[0]}。

綜上所述，存在以下路由等式：

由于位移主要發(fā)生在橫坐標(biāo)上，僅考慮橫坐標(biāo)上的投影，則有：

定理1從任一起點(diǎn)s(jn)出發(fā)到任一終點(diǎn)e(j0)的路由路徑僅有一條。

證明：假設(shè)從起點(diǎn)s(jn)出發(fā)到任一終點(diǎn)e(j0)的路由路徑有兩條，則有：

由于兩條路由路徑的終點(diǎn)相等，那么這兩條路徑在終點(diǎn)或者終點(diǎn)之前必定存在一個(gè)交點(diǎn)，且在此之后匯聚成一條路徑。

假設(shè)交點(diǎn)存在于第t層，則有：

由于兩條路徑在路由點(diǎn)r(t,jt)處匯聚，因此d2(t)≠ d1(t)。

當(dāng) r(t,jt)∈ ob(i,k)時(shí)，d2(t)、d1(t)∈ {0,1}， 則|d2(t)-d1(t)|=1。

當(dāng) r(t,jt)∈ eb(i,k)時(shí)，d2(t)、d1(t)∈ {-1,0}，則|d2(t)-d1(t)|=1。

因此，有：

等式的左側(cè)為偶數(shù)，等式的右側(cè)為奇數(shù)，產(chǎn)生矛盾，定理1得證。

定理2任一起點(diǎn)s(jn)出發(fā)到任一終點(diǎn)e(j0)的路由傳遞過程是兩點(diǎn)橫坐標(biāo)的異或運(yùn)算。

證明：將起點(diǎn)s(jn)和終點(diǎn)e(j0)的橫坐標(biāo)做二進(jìn)制數(shù)展開，得：

根據(jù)式（2），有：

根據(jù)定理1，有：

當(dāng)j0[i]=1時(shí)，表示路由點(diǎn)落在第i層的奇區(qū)間，d(i)的符號(hào)為“+”，有：

當(dāng)j0[i]=0時(shí)，表示路由點(diǎn)落在第i層的偶區(qū)間，d(i)的符號(hào)為“-”，有：

對(duì)于不含進(jìn)位的單比特加減法，有：

因此，定理2得證。

由于Butterfly置換網(wǎng)絡(luò)的數(shù)學(xué)理論本質(zhì)就是初始坐標(biāo)與目標(biāo)坐標(biāo)的二進(jìn)制展開式的按位異或運(yùn)算。因此，只要知道輸入數(shù)據(jù)的初始坐標(biāo)和目標(biāo)坐標(biāo)，就能通過異或運(yùn)算快速得到該數(shù)據(jù)的路由向量d，從而為求解Butterfly置換參數(shù)做好準(zhǔn)備。

如圖2所示，初始坐標(biāo)為“5”和“3”的數(shù)據(jù)需要通過Butterfly網(wǎng)絡(luò)分別置換到“2”和“5”的目標(biāo)位置。它的各層置換參數(shù)與路由向量元素的數(shù)值相等，位置正好處于各層的路由點(diǎn)r(i,ji)上。

因此，求出路由路徑各層路由點(diǎn)的橫坐標(biāo)就能快速得到Butterfly網(wǎng)絡(luò)的置換參數(shù)。根據(jù)路由路徑的定義和異或運(yùn)算的交換特性，可得遞歸算法：

由于已知終點(diǎn)e(j0)，因此可以選擇從終點(diǎn)橫坐標(biāo)j0出發(fā)逐層推導(dǎo)出路徑上各路由點(diǎn)的橫坐標(biāo)ji，然后將各層的路由元素放置到該位置，得到置換參數(shù)。

綜上所述，如圖3所示，求解某置換運(yùn)算的Butterfly置換參數(shù)的算法步驟可以分解為：

（1）根據(jù)已知條件求解數(shù)據(jù)的起始地址；

（2）根據(jù)已知條件求解數(shù)據(jù)的目標(biāo)地址；

（3）初始地址和目標(biāo)地址異或得到路由向量集合，設(shè)置i=0；

（4）使用路由向量第i層元素d[i],，修正其上所有層路由向量元素d[i+1]～d[n-1]的位置，i++；

（5）重復(fù)步驟（4）直到i=n-1，即得到Butterfly置換參數(shù)。

可以選擇目標(biāo)地址為參照坐標(biāo)系，由此合并步驟（1）和步驟（2），調(diào)整為根據(jù)已知條件求解目標(biāo)地址上數(shù)據(jù)來源的起始地址。

2 Butterfly網(wǎng)絡(luò)數(shù)學(xué)理論的應(yīng)用

2.1 PDEP運(yùn)算

如圖4所示，PDEP運(yùn)算是一種比特?cái)U(kuò)散運(yùn)算。它根據(jù)置換掩碼數(shù)據(jù)中“1”的數(shù)量m，選中輸入數(shù)據(jù)最低m比特?cái)?shù)據(jù)，然后將選中的這些數(shù)據(jù)從右至左第j比特移位到掩碼數(shù)據(jù)中從右至左第j個(gè)“1”對(duì)應(yīng)的位置上，0≤j≤m-1。

Lee等人發(fā)表的論文證明了PDEP運(yùn)算可以采用Butterfly置換網(wǎng)絡(luò)結(jié)構(gòu)實(shí)現(xiàn)，并提出了置換遞歸算法來對(duì)置換參數(shù)進(jìn)行求解。

整個(gè)求解過程在硬件實(shí)現(xiàn)時(shí)被分解為3個(gè)步驟：

（1）計(jì)算置換掩碼mask在位置區(qū)間[j,0]，(0≤j≤N-1）中“1”的數(shù)量 POPCNT(mask[ j:0])；

（2）在第i行，對(duì)k(i)=2i個(gè)“1”執(zhí)行LROT C(1k(i),POPCNT[mask[(2t+1)×k(i)-1:0])]運(yùn) 算 ，其 中0 ≤ i≤ log2N-1，0 ≤t≤ 2n-i-1；

（3）將（2）中計(jì)算的結(jié)果按照左對(duì)齊的方式放在第i行第(2t+1)×k(i)-1列的位置，從而得到完整的置換參數(shù)[1]。

作為對(duì)比，本文采用第一章提出的Butterfly網(wǎng)絡(luò)的置換數(shù)學(xué)理論對(duì)PDEP運(yùn)算的置換參數(shù)求解過程進(jìn)行推導(dǎo)。

為了方便描述，以下采用8 bit PDEP運(yùn)算進(jìn)行分析，如圖5所示。

根據(jù)Butterfly置換網(wǎng)絡(luò)數(shù)學(xué)理論求解置換參數(shù)的標(biāo)準(zhǔn)流程如下。

（1）根據(jù)已知條件求解各目標(biāo)位置上數(shù)據(jù)的起始位置。該運(yùn)算的已知條件包括置換掩碼和輸入數(shù)據(jù)，輸入數(shù)據(jù)作為被置換的對(duì)象，本身并不包含任何位置信息，因此可以利用的已知條件只有置換掩碼。

PDEP運(yùn)算的定義是將輸入數(shù)據(jù)從右至左的第js比特din[js]置換到輸出數(shù)據(jù)中對(duì)應(yīng)置換掩碼從右至左的第js個(gè)“1”的位置上。把定義反向推導(dǎo)即可得知，置換到輸出數(shù)據(jù)第je比特dout[je]的數(shù)據(jù)來源是置換掩碼mask[je]對(duì)應(yīng)位置的“1”是其從右至左的第幾個(gè)“1”，也就是mask[je]對(duì)應(yīng)位置的“1”在整個(gè)置換掩碼中的編號(hào)。

如圖6所示，置換掩碼從右至左第1個(gè)“1”編號(hào)為0，因此其je位置上的“1”的編號(hào)是je位置右邊所有“1”的數(shù)量和，即POPCNT(mask[ je:0])。所以，比特?cái)U(kuò)散的輸出有效位，對(duì)應(yīng)的數(shù)據(jù)來源位置即為POPCNT(mask[ je:0])。由于其他非擴(kuò)散有效位的數(shù)據(jù)在輸出時(shí)將統(tǒng)一被置換掩碼過濾為“0”，其運(yùn)算中間結(jié)果是多少并不重要。為了簡(jiǎn)化運(yùn)算，可以與有效位的數(shù)據(jù)來源算法保持一致。

綜上所述，目標(biāo)位置je上數(shù)據(jù)的起始位置求解算法為POPCNT(mask[ je:0])。

（2）初始排序和目標(biāo)排序異或得到路由向量集合。根據(jù)（1）中的算法，可以計(jì)算得到N比特PDEP運(yùn)算輸出數(shù)據(jù)的初始排序?yàn)椋?/p>

只需將其與目標(biāo)排序{N-1,N-2,…,2,1,0}做異或操作，就可以得到Butterfly網(wǎng)絡(luò)的路由向量集合，如圖7所示。

（3）對(duì)路由向量集合進(jìn)行修正得到置換參數(shù)。該步驟的一般處理辦法是利用路由向量集合中第i層的元素，對(duì)第i+1層到第n-1層的元素進(jìn)行置換修正，然而將額外引入一個(gè)Butterfly網(wǎng)絡(luò)的硬件開銷，也沒有進(jìn)一步優(yōu)化運(yùn)算復(fù)雜度，不符合利用Butterfly置換網(wǎng)絡(luò)數(shù)學(xué)理論求解問題的預(yù)期。正確的做法是進(jìn)一步挖掘置換的本質(zhì)就是異或帶來的運(yùn)算特性，如圖8所示。

從步驟（1）化簡(jiǎn)后的PDEP運(yùn)算結(jié)果可以發(fā)現(xiàn)，第i層奇區(qū)間eb(i,2k+1)和偶區(qū)間ob(i,2k)中的對(duì)應(yīng)路由點(diǎn)的起始位置js1和js2相差小于等于2i，因此兩個(gè)起始位置的二進(jìn)制展開式在第i層的組合(js1[i],js2[i])可能有 4種情況——(0,0)、(0,1)、(1,0)和(1,1)。同時(shí)，它的對(duì)應(yīng)目標(biāo)位置的二進(jìn)制展開式在第i層互為相反數(shù)，且其組合(je1[i],je2[i])只有一種情況(1,0)。因此，兩者異或運(yùn)算后得到的路由向量在第i層的組合(jd1[i],jd2[i])也有(1,0)、(1,1)、(0,0)和(0,1)這4種情況。

(jd1[i],jd2[i])的4種組合決定了路由向量在第i層以上的路由元素，相應(yīng)對(duì)應(yīng)著4種不同的修正可能性，其中(0,0)對(duì)應(yīng)位置保持，(0,1)對(duì)應(yīng)左側(cè)位置保持，(1,0)對(duì)應(yīng)右側(cè)位置保持，(1,1)對(duì)應(yīng)位置交換。至此，路由向量修正算法可以簡(jiǎn)化為：當(dāng)jd1[i]＆jd2[i]=1時(shí)執(zhí)行位置交換，否則執(zhí)行位置保持。

進(jìn)一步分析發(fā)現(xiàn)，當(dāng)(jd1[i],jd2[i])為(1,0)、(0,0)、(0,1)這3種組合時(shí)，對(duì)應(yīng)的起始位置組合(js1[i],js2[i])分別為 (0,0)、(1,0)、(1,1)。由于 js1和 js2相差小于等于2i，因此這3種組合對(duì)應(yīng)的兩個(gè)起始位置的二進(jìn)制展開式在第i+1層到第n-1層的組合(js1[n-1:i+1],js2[n-1:i+1])只有 (0n-i-2,0n-i-2)和 (1n-i-2,1n-i-2)兩種，即js1[n-1:i+1]=js2[n-1:i+1]。同時(shí)，由于(jd1[i],jd2[i])來源于第i+1層到第n-1層相同的路由區(qū)間，其對(duì)應(yīng)的目標(biāo)位置二進(jìn)制展開式在第i+1層到第n-1層有：

由此可得：

這意味著當(dāng) (jd1[i],jd2[i])為(1,0)、(0,0)、(0,1)這3種組合時(shí)，其i+1層到n-1層的待修正路由向量是相等的，因此執(zhí)行“位置交換”還是執(zhí)行“位置保持”并不影響結(jié)果。此時(shí)，路由向量修正算法可以進(jìn)一步簡(jiǎn)化為：無論(jd1[i],jd2[i])是什么值，都對(duì)第i+1層到n-1層的路由向量執(zhí)行奇偶區(qū)間對(duì)應(yīng)位置的交換修正，如圖9所示。

由于本步驟的修正運(yùn)算是固定的，對(duì)于硬件實(shí)現(xiàn)來說無需引入額外的運(yùn)算模塊，只需要將步驟2中計(jì)算結(jié)果的相應(yīng)比特位利用拼接符“{}”指定固定的硬連線就可以實(shí)現(xiàn)。相對(duì)于Lee提出的遞歸算法，將POPCNT+LROTC運(yùn)算轉(zhuǎn)化為POPCNT+XOR運(yùn)算，存在優(yōu)化的可能性。

采用synopsys_design compiler-2018.06-SP1工具，結(jié)合UMC28nm工藝12track混合標(biāo)準(zhǔn)單元庫(sc12mcpp140z_l28hpc_hpk_lvt_c30_ssg_cworst_max_0p81v_125c.db)，對(duì)兩種算法實(shí)現(xiàn)的32 bit PDEP運(yùn)算的置換參數(shù)產(chǎn)生模塊進(jìn)行綜合對(duì)比。結(jié)果在時(shí)序約束為0.5 ns的情況下，獲得了15%的面積優(yōu)化，如表1所示。

表1 32 bit PDEP運(yùn)算置換參數(shù)產(chǎn)生模塊對(duì)比

2.2 ROT運(yùn)算

ROT運(yùn)算是一種特殊的移位運(yùn)算，根據(jù)移位方向d和移位位數(shù)m，選中輸入數(shù)據(jù)的最低/最高n比特?cái)?shù)據(jù)，然后將選中的這些數(shù)據(jù)移位到剩余數(shù)據(jù)的左側(cè)/右側(cè)，d∈{-1,1}，0≤m≤N-1。為了方便描述和推導(dǎo)，本文主要考慮RROT運(yùn)算，如圖10所示。

Lee等人發(fā)表的論文證明了RROT運(yùn)算也可以采用Butterfly置換網(wǎng)絡(luò)結(jié)構(gòu)實(shí)現(xiàn)，同時(shí)提出了置換遞歸算法來對(duì)置換參數(shù)進(jìn)行求解。

整個(gè)求解過程在硬件實(shí)現(xiàn)的時(shí)候被分解為兩個(gè)步驟：

（1）對(duì)第 i行執(zhí)行LROTC(0k(i),(m)mod2i+1)運(yùn)算，其中k(i)=2i，0≤i≤log2N-1；

（2）將2n-i-1個(gè)LROTC(0m(i),(m)mod2i+1)拼接在一起得到第i層置換參數(shù)[1]。

作為對(duì)比，本文采用第一章提出的Butterfly網(wǎng)絡(luò)的置換數(shù)學(xué)理論對(duì)RROT運(yùn)算的置換參數(shù)求解過程進(jìn)行推導(dǎo)。

為了方便描述，以下采用8 bit RROT運(yùn)算進(jìn)行分析。圖11為一個(gè)8 bit的RROT置換運(yùn)算。

根據(jù)Butterfly置換網(wǎng)絡(luò)數(shù)學(xué)理論求解置換參數(shù)的標(biāo)準(zhǔn)流程如下。

（1）根據(jù)已知條件求解各目標(biāo)位置上數(shù)據(jù)的起始位置。RROT運(yùn)算的定義是根據(jù)移位位數(shù)m把輸入數(shù)據(jù)最右側(cè)m比特din[m-1:0]置換到輸出數(shù)據(jù)中最左側(cè)的m比特dout[N-1:m]的位置上，把輸入數(shù)據(jù)最左側(cè)N-m比特din[N-1:m]置換到輸出數(shù)據(jù)中最右側(cè)的m比特dout[N-m-1:0]的位置上。因此，有dout={din[m-1:0],din[N-1:m]}，輸出數(shù)據(jù)各比特對(duì)應(yīng)的起始位置為：

綜上所述，目標(biāo)位置je上數(shù)據(jù)的起始位置求解算法為(je+m)mod2n，如圖12所示。

（2）初始排序和目標(biāo)排序異或得到路由向量集合。根據(jù)（1）中的算法，可以得到N比特RROT運(yùn)算輸出數(shù)據(jù)的初始排序?yàn)椋?/p>

只需將其與目標(biāo)排序{N-1,N-2,…,2,1,0}做異或操作，就可以得到Butterfly網(wǎng)絡(luò)的路由向量集合，如圖13所示。

至此，N（N=2n）比特RROT運(yùn)算置換參數(shù)的求解算法轉(zhuǎn)化為N路并行“n比特加法+異或”運(yùn)算。雖然邏輯深度由2n降為n，但是N個(gè)n比特加法器消耗的硬件資源不容忽視。值得注意的是，第j路n比特加法的其中一個(gè)輸入是常數(shù)je，因此n比特加法邏輯可以進(jìn)一步化簡(jiǎn)。

根據(jù)路由向量d(je)的求解算法[(je+m)⊕je]mod2n，由于mod2n屬于硬件運(yùn)算模塊的附加屬性，為了簡(jiǎn)化，在后續(xù)推導(dǎo)過程將其省略。

令A(yù)=je、B=m，則可將原算法轉(zhuǎn)化為：

代入全加器的邏輯表達(dá)式：

得到：

代入進(jìn)位產(chǎn)生函數(shù)和進(jìn)位傳遞函數(shù)：

當(dāng)je[i]=0時(shí)，有：

當(dāng)je[i]=1時(shí)，有：

因此，得到遞歸函數(shù)：

（3）對(duì)路由向量集合進(jìn)行修正得到置換參數(shù)。從步驟（1）化簡(jiǎn)后的RROT運(yùn)算結(jié)果可以發(fā)現(xiàn)，第i層奇區(qū)間eb(i,2k+1)和偶區(qū)間ob(i,2k)中的對(duì)應(yīng)路由點(diǎn)的起始位置js1和js2相差始終等于2i，因此兩個(gè)起始位置的二進(jìn)制展開式在第i層的組合(js1[i],js2[i])可能有兩種情況(1,0)和(0,1)。同時(shí)，它的對(duì)應(yīng)目標(biāo)位置的二進(jìn)制展開式在第i層互為相反數(shù)，且其組合(je1[i],je2[i])只有一種情況(1,0)。因此，兩者異或運(yùn)算后得到的路由向量在第i層的組合(jd1[i],jd2[i])只有(0,0)和(1,1)兩種情況，如圖14所示。

(jd1[i],jd2[i])的兩種組合決定了路由向量在第i層以上的路由元素，相應(yīng)的對(duì)應(yīng)著兩種不同的修正可能性，其中(0,0)對(duì)應(yīng)位置保持，(1,1)對(duì)應(yīng)位置交換。至此，路由向量修正算法可以簡(jiǎn)化為：當(dāng)jd1[i]＆jd2[i]=1時(shí)執(zhí)行位置交換，否則執(zhí)行位置保持。

這意味著當(dāng)(jd1[i],jd2[i])為(0,0)組合時(shí)，其i+1層到n-1層的待修正路由向量是相等的，因此執(zhí)行“位置交換”還是執(zhí)行“位置保持”并不影響結(jié)果。此時(shí)，路由向量修正算法可以進(jìn)一步簡(jiǎn)化為：無論(jd1[i],jd2[i])是什么組合，都對(duì)第i+1層到n-1層的路由向量執(zhí)行奇偶區(qū)間對(duì)應(yīng)位置的交換修正，如圖15所示。

最終得到：

由此可見，利用Butterfly網(wǎng)絡(luò)的數(shù)學(xué)理論直接推導(dǎo)的結(jié)果與Lee提出的遞歸算法相同，因此兩種算法實(shí)現(xiàn)的置換參數(shù)產(chǎn)生模塊的優(yōu)化程度一致，如圖16所示。

3 結(jié) 語

本文通過數(shù)字表示的方法定義了Butterfly網(wǎng)絡(luò)結(jié)構(gòu)，通過數(shù)學(xué)方法深入研究網(wǎng)絡(luò)結(jié)構(gòu)的性質(zhì)和特征，歸納總結(jié)出Butterfly網(wǎng)絡(luò)的置換數(shù)學(xué)理論。此外，利用該數(shù)學(xué)理論重新分析了PDEP運(yùn)算和RROT運(yùn)算。對(duì)于32 bit PDEP運(yùn)算，在時(shí)序約束同為0.5 ns的情況下，置換參數(shù)產(chǎn)生模塊的硬件實(shí)現(xiàn)方案獲得了15%的面積優(yōu)化。對(duì)于RROT運(yùn)算，獲得了更加直觀的置換參數(shù)推算過程。研究可為研究人員進(jìn)一步分析開發(fā)Butterfly網(wǎng)絡(luò)在其他比特置換運(yùn)算中的應(yīng)用提供了新思路。