基于Inverse Butterfly/Butterfly網(wǎng)絡的置換-逆序與置換-移位選路算法
發(fā)布時間：2022-01-01 00:24
本文利用Inverse Butterfly/Butterfly多級動態(tài)互連網(wǎng)絡的自路由和可重排特性,提出了基于該網(wǎng)絡的置換-逆序和置換-移位選路算法.它們都能夠對所有一次通過該網(wǎng)絡的任意置換結果動態(tài)地完成逆序和移位操作,且算法復雜度低,硬件實現(xiàn)簡潔.進一步,將本文提出的算法對基于該網(wǎng)絡設計的置換操作進行了功能擴展,分別構建了置換-逆序、置換-移位以及置換-逆序-移位硬件單元.并將它們在SMIC 65nm工藝下進行了綜合,結果表明:當在以往研究成果上擴展逆序操作時,硬件電路面積僅增加約6%且?guī)缀醪挥绊懺軜嫷难舆t;當在以往研究成果上擴展移位和逆序-移位操作時,原架構以18%和21%的面積增加值和30%的延遲增加值,實現(xiàn)了功能性2倍的提升.
【文章來源】：電子學報. 2017,45(11)北大核心EICSCD
【文章頁數(shù)】：10 頁
【部分圖文】：
InverseHuttertlvlHutterHv網(wǎng)絡拓撲結構
電子學報2017年性質3若N-bit數(shù)據(jù)M={aN－1，aN－2，…，a0}一次通過InverseButterfly網(wǎng)絡實現(xiàn)置換P，記P=aN－1aN－2…a0a0aN－1…aN{}－2，通過調(diào)整初始置換各級的控制信息，該網(wǎng)絡還能夠實現(xiàn)其結果的逆序置換～P，記～P=aN－1aN－2…a0aN－2…aN－1a{}0．證明:根據(jù)性質2知，若需完成網(wǎng)絡最后一級初始輸出數(shù)據(jù)的逆序，可以通過將最后一級初始輸入數(shù)據(jù)按照左、右兩部分分別逆序，同時調(diào)整初始控制信息實現(xiàn)．如圖5(a)所示，通過將網(wǎng)絡最后一級初始輸入端左L、右Ｒ兩部分數(shù)據(jù)(位寬為N/2-bit)逆序，同時調(diào)整初始控制信息，那么就可以完成最后一級數(shù)據(jù)的逆序(位寬為N-bit)．對比圖5(a)、(b)中倒數(shù)第二級輸出(即最后一級的輸入)數(shù)據(jù)可以發(fā)現(xiàn)，圖5(b)中倒數(shù)第二級的輸出數(shù)據(jù)(ＲeversedL、ＲeversedＲ)是圖5(a)初始網(wǎng)絡中該級輸出數(shù)據(jù)(L、Ｒ)的逆序．然后，將圖5(a)中L、Ｒ兩部分數(shù)據(jù)分別逆序，根據(jù)性質2可知，這樣的操作可以通過將該級各簇內(nèi)輸入數(shù)據(jù)逆序，同時調(diào)整簇內(nèi)初始控制信息實現(xiàn)．以此方式向上遞推，當數(shù)據(jù)到達該網(wǎng)絡第一級時，初始輸出數(shù)據(jù)的逆序，也可以通過將該級初始輸入數(shù)據(jù)逆序，同時調(diào)整初始控制信息實現(xiàn)．而第一級數(shù)據(jù)的初始輸入位寬為1-bit，它逆序與否，其結果均與初始第一級初始輸入數(shù)據(jù)序列相同．因此，從圖5(b)中初始輸入端出發(fā)，整個網(wǎng)絡就相當于完成了任意置換P下的逆序置換～P．2688
電子學報2017年性質3若N-bit數(shù)據(jù)M={aN－1，aN－2，…，a0}一次通過InverseButterfly網(wǎng)絡實現(xiàn)置換P，記P=aN－1aN－2…a0a0aN－1…aN{}－2，通過調(diào)整初始置換各級的控制信息，該網(wǎng)絡還能夠實現(xiàn)其結果的逆序置換～P，記～P=aN－1aN－2…a0aN－2…aN－1a{}0．證明:根據(jù)性質2知，若需完成網(wǎng)絡最后一級初始輸出數(shù)據(jù)的逆序，可以通過將最后一級初始輸入數(shù)據(jù)按照左、右兩部分分別逆序，同時調(diào)整初始控制信息實現(xiàn)．如圖5(a)所示，通過將網(wǎng)絡最后一級初始輸入端左L、右Ｒ兩部分數(shù)據(jù)(位寬為N/2-bit)逆序，同時調(diào)整初始控制信息，那么就可以完成最后一級數(shù)據(jù)的逆序(位寬為N-bit)．對比圖5(a)、(b)中倒數(shù)第二級輸出(即最后一級的輸入)數(shù)據(jù)可以發(fā)現(xiàn)，圖5(b)中倒數(shù)第二級的輸出數(shù)據(jù)(ＲeversedL、ＲeversedＲ)是圖5(a)初始網(wǎng)絡中該級輸出數(shù)據(jù)(L、Ｒ)的逆序．然后，將圖5(a)中L、Ｒ兩部分數(shù)據(jù)分別逆序，根據(jù)性質2可知，這樣的操作可以通過將該級各簇內(nèi)輸入數(shù)據(jù)逆序，同時調(diào)整簇內(nèi)初始控制信息實現(xiàn)．以此方式向上遞推，當數(shù)據(jù)到達該網(wǎng)絡第一級時，初始輸出數(shù)據(jù)的逆序，也可以通過將該級初始輸入數(shù)據(jù)逆序，同時調(diào)整初始控制信息實現(xiàn)．而第一級數(shù)據(jù)的初始輸入位寬為1-bit，它逆序與否，其結果均與初始第一級初始輸入數(shù)據(jù)序列相同．因此，從圖5(b)中初始輸入端出發(fā)，整個網(wǎng)絡就相當于完成了任意置換P下的逆序置換～P．2688
【參考文獻】：
期刊論文
[1]A Novel Combinatorics-Based Reconfigurable Bit Permutation Network and Its Circuit Implementation[J]. SHAN Weiwei,CHEN Xin,LU Yinchao,LI Jie. Chinese Journal of Electronics. 2015(03)
本文編號：3561277
【文章來源】：電子學報. 2017,45(11)北大核心EICSCD
【文章頁數(shù)】：10 頁
【部分圖文】：
InverseHuttertlvlHutterHv網(wǎng)絡拓撲結構
電子學報2017年性質3若N-bit數(shù)據(jù)M={aN－1，aN－2，…，a0}一次通過InverseButterfly網(wǎng)絡實現(xiàn)置換P，記P=aN－1aN－2…a0a0aN－1…aN{}－2，通過調(diào)整初始置換各級的控制信息，該網(wǎng)絡還能夠實現(xiàn)其結果的逆序置換～P，記～P=aN－1aN－2…a0aN－2…aN－1a{}0．證明:根據(jù)性質2知，若需完成網(wǎng)絡最后一級初始輸出數(shù)據(jù)的逆序，可以通過將最后一級初始輸入數(shù)據(jù)按照左、右兩部分分別逆序，同時調(diào)整初始控制信息實現(xiàn)．如圖5(a)所示，通過將網(wǎng)絡最后一級初始輸入端左L、右Ｒ兩部分數(shù)據(jù)(位寬為N/2-bit)逆序，同時調(diào)整初始控制信息，那么就可以完成最后一級數(shù)據(jù)的逆序(位寬為N-bit)．對比圖5(a)、(b)中倒數(shù)第二級輸出(即最后一級的輸入)數(shù)據(jù)可以發(fā)現(xiàn)，圖5(b)中倒數(shù)第二級的輸出數(shù)據(jù)(ＲeversedL、ＲeversedＲ)是圖5(a)初始網(wǎng)絡中該級輸出數(shù)據(jù)(L、Ｒ)的逆序．然后，將圖5(a)中L、Ｒ兩部分數(shù)據(jù)分別逆序，根據(jù)性質2可知，這樣的操作可以通過將該級各簇內(nèi)輸入數(shù)據(jù)逆序，同時調(diào)整簇內(nèi)初始控制信息實現(xiàn)．以此方式向上遞推，當數(shù)據(jù)到達該網(wǎng)絡第一級時，初始輸出數(shù)據(jù)的逆序，也可以通過將該級初始輸入數(shù)據(jù)逆序，同時調(diào)整初始控制信息實現(xiàn)．而第一級數(shù)據(jù)的初始輸入位寬為1-bit，它逆序與否，其結果均與初始第一級初始輸入數(shù)據(jù)序列相同．因此，從圖5(b)中初始輸入端出發(fā)，整個網(wǎng)絡就相當于完成了任意置換P下的逆序置換～P．2688
電子學報2017年性質3若N-bit數(shù)據(jù)M={aN－1，aN－2，…，a0}一次通過InverseButterfly網(wǎng)絡實現(xiàn)置換P，記P=aN－1aN－2…a0a0aN－1…aN{}－2，通過調(diào)整初始置換各級的控制信息，該網(wǎng)絡還能夠實現(xiàn)其結果的逆序置換～P，記～P=aN－1aN－2…a0aN－2…aN－1a{}0．證明:根據(jù)性質2知，若需完成網(wǎng)絡最后一級初始輸出數(shù)據(jù)的逆序，可以通過將最后一級初始輸入數(shù)據(jù)按照左、右兩部分分別逆序，同時調(diào)整初始控制信息實現(xiàn)．如圖5(a)所示，通過將網(wǎng)絡最后一級初始輸入端左L、右Ｒ兩部分數(shù)據(jù)(位寬為N/2-bit)逆序，同時調(diào)整初始控制信息，那么就可以完成最后一級數(shù)據(jù)的逆序(位寬為N-bit)．對比圖5(a)、(b)中倒數(shù)第二級輸出(即最后一級的輸入)數(shù)據(jù)可以發(fā)現(xiàn)，圖5(b)中倒數(shù)第二級的輸出數(shù)據(jù)(ＲeversedL、ＲeversedＲ)是圖5(a)初始網(wǎng)絡中該級輸出數(shù)據(jù)(L、Ｒ)的逆序．然后，將圖5(a)中L、Ｒ兩部分數(shù)據(jù)分別逆序，根據(jù)性質2可知，這樣的操作可以通過將該級各簇內(nèi)輸入數(shù)據(jù)逆序，同時調(diào)整簇內(nèi)初始控制信息實現(xiàn)．以此方式向上遞推，當數(shù)據(jù)到達該網(wǎng)絡第一級時，初始輸出數(shù)據(jù)的逆序，也可以通過將該級初始輸入數(shù)據(jù)逆序，同時調(diào)整初始控制信息實現(xiàn)．而第一級數(shù)據(jù)的初始輸入位寬為1-bit，它逆序與否，其結果均與初始第一級初始輸入數(shù)據(jù)序列相同．因此，從圖5(b)中初始輸入端出發(fā)，整個網(wǎng)絡就相當于完成了任意置換P下的逆序置換～P．2688
【參考文獻】：
期刊論文
[1]A Novel Combinatorics-Based Reconfigurable Bit Permutation Network and Its Circuit Implementation[J]. SHAN Weiwei,CHEN Xin,LU Yinchao,LI Jie. Chinese Journal of Electronics. 2015(03)
本文編號：3561277
本文鏈接：http://sikaile.net/kejilunwen/dianzigongchenglunwen/3561277.html
教材專著
