Full Text:   <1835>

Summary:  <1127>

CLC number: TP331.2

On-line Access: 2018-01-12

Received: 2016-05-17

Revision Accepted: 2016-09-14

Crosschecked: 2017-11-20

Cited: 0

Clicked: 3877

Citations:  Bibtex RefMan EndNote GB/T7714

-   Go to

Article info.
Open peer comments

Frontiers of Information Technology & Electronic Engineering  2017 Vol.18 No.11 P.1784-1794


A highly efficient reconfigurable rotation unit based on an inverse butterfly network

Author(s):  Chao Ma, Zi-bin Dai, Wei Li, Hai-juan Zang

Affiliation(s):  Department of Electrical Engineering, Zhengzhou Institute of Information Science and Technology, Zhengzhou 450004, China; more

Corresponding email(s):   wenlu_ma@163.com, Daizb2004@126.com

Key Words:  Rotation operations, Self-routing, Control-bit generation algorithm, Inverse butterfly network

Chao Ma, Zi-bin Dai, Wei Li, Hai-juan Zang. A highly efficient reconfigurable rotation unit based on an inverse butterfly network[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(11): 1784-1794.

@article{title="A highly efficient reconfigurable rotation unit based on an inverse butterfly network",
author="Chao Ma, Zi-bin Dai, Wei Li, Hai-juan Zang",
journal="Frontiers of Information Technology & Electronic Engineering",
publisher="Zhejiang University Press & Springer",

%0 Journal Article
%T A highly efficient reconfigurable rotation unit based on an inverse butterfly network
%A Chao Ma
%A Zi-bin Dai
%A Wei Li
%A Hai-juan Zang
%J Frontiers of Information Technology & Electronic Engineering
%V 18
%N 11
%P 1784-1794
%@ 2095-9184
%D 2017
%I Zhejiang University Press & Springer
%DOI 10.1631/FITEE.1601265

T1 - A highly efficient reconfigurable rotation unit based on an inverse butterfly network
A1 - Chao Ma
A1 - Zi-bin Dai
A1 - Wei Li
A1 - Hai-juan Zang
J0 - Frontiers of Information Technology & Electronic Engineering
VL - 18
IS - 11
SP - 1784
EP - 1794
%@ 2095-9184
Y1 - 2017
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/FITEE.1601265

We propose a reconfigurable control-bit generation algorithm for rotation and sub-word rotation operations. The algorithm uses a self-routing characteristic to configure an inverse butterfly network. In addition to being highly parallelized and inexpensive, the algorithm integrates the rotation-shift, bi-directional rotation-shift, and sub-word rotation-shift operations. To our best knowledge, this is the first scheme to accommodate a variety of rotation operations into the same architecture. We have developed the highly efficient reconfigurable rotation unit (HERRU) and synthesized it into the Semiconductor Manufacturing International Corporation (SMIC)’s 65-nm process. The results show that the overall efficiency (relative area×relative latency) of our HERRU is higher by at least 23% than that of other designs with similar functions. When executing the bi-directional rotation operations alone, HERRU occupies a significantly smaller area with a lower latency than previously proposed designs.

基于Inverse Butterlfy网络的高效可重构循环移位单元

概要:本文提出了一种利用inverse butterfly网络的自路由特性完成循环移位、短字循环移位等操作的可重构控制信息生成算法。该算法具有高并行度和低成本,此外还支持循环移位、双向循环移位以及短字循环移位操作。据我们所知,这是首个将多种不同类型的循环移位操作统一在一个硬件架构中的算法。本文进一步设计了一种高效可重构循环移位单元,并在SMIC 65-nm工艺下实现了逻辑综合。结果表明:与以往具有相似功能的设计相比,该单元的效能至少提升了23%;当仅支持双向循环移位操作时,该单元具有更小的面积和更低的延迟。

关键词:循环移位操作;自路由;控制信息生成算法;Inverse butterfly网络

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article


[1]Bansod, G., Raval, N., Pisharoty, N., 2014. Implementation of a new lightweight encryption design for embedded security. IEEE Trans. Inform. Forens. Secur. 10(1):142-151.

[2]Belazi, A., El-Latif, A., Belghith, S., 2016. A novel image encryption scheme based on substitution-permutation network and chaos. Signal Process., 128:155-170.

[3]Chang, Z., Hu, J., Zheng, C., et al., 2013. Research on shifter based on iButterfly network. Commun. Comput. Inform. Sci., 396:92-100.

[4]Dai, H., Shen, X., 2007. Rearrageability of the 7-stage 16×16 shuffle exchange network. Acta Electron. Sin., 35(10): 1875-1891 (in Chinese).

[5]Hilewitz, Y., Lee, R.B., 2006. Fast bit compression and expansion with parallel extract and parallel deposit instructions. IEEE Int. Conf. on Application-Specific Systems, p.65-72.

[6]Hilewitz, Y., Lee, R.B., 2007. Performing advanced bit manipulations efficiently in general-purpose processors. IEEE Symp. on Computer Arithmetic, p.251-260.

[7]Hilewitz, Y., Lee, R.B., 2008. Fast bit gather, bit scatter and bit permutation instructions for commodity microprocessors. J. Signal Process. Syst., 53(2):145-169.

[8]Hilewitz, Y., Lee, R.B., 2009. A new basis for shifters in general-purpose processors for existing and advanced bit manipulations. IEEE Trans. Comput., 58(8):1035-1048.

[9]Hilewitz, Y., Shi, Z.J., Lee, R.B., 2004. Comparing fast implementations of bit permutation instructions. Proc. 38th Annual Asilomar Conf. on Signals, Systems, and Computers, p.1856-1863.

[10]Intel Corporation, 2006. Intel Itanium Architecture Software Developer’s Manual, Vol. 3, Rev. 2.2. [https://www.intel.com/content/www/us/en/processors/itanium/itanium-architecture-vol-3-manual.html [Accessed on April 5, 2016].

[11]Intel Corporation, 2015. Intel® 64 and IA-32 Architectures Software Developer’s Manual. https://software.intel.com/ sites/default/files/managed/39/c5/325462-sdm-vol-1-2abcd-3abcd.pdf [Accessed on April 10, 2016].

[12]Jolfaei, A., Wu, X., Muthukkumarasamy, V., 2015. On the security of permutation-only image encryption schemes. IEEE Trans. Inform. Forens. Secur., 11(2):235-246.

[13]Lee, R.B., Shi, Z.J., Yin, Y.L., et al., 2004. On permutation operations in cipher design. Int. Conf. on Information Technology: Coding and Computing, p.569-577.

[14]Nassimi, D., Sahni, S., 1981. A self-routing benes network and parallel permutation algorithm. IEEE Trans. Comput., 30(8):332-340.

[15]Pillmeier, M.R., 2002. Barrel Shifter Design, Optimization, and Analysis. MS Thesis, Lehigh University, Bethlehem, Pennsylvania.

[16]Pillmeier, M.R., Schulte, M.J., Walters, E.G.III, 2002. Design alternatives for barrel shifters. Proc. Advanced Signal Processing Algorithms, Architectures, and Implementations, p.436-447.

[17]Rajkumar, S., Goyal, N.K., 2014. Design of 4-disjoint gamma interconnection network layouts and reliability analysis of gamma interconnection networks. J. Supercomput., 69(1):468-491.

[18]Saraswathi, P.V., Venkatesulu, M., 2014. A block cipher based on Boolean matrices using bit level operations. IEEE/ ACIS 13th Int. Conf. on Computer and Information Science, p.59-63.

[19]Sayilar, G., Chiou, D., 2015. Cryptoraptor: high-throughput reconfigurable cryptographic processor. IEEE/ACM Int. Conf. on Computer-Aided Design, p.155-161.

[20]Semiconductor Manufacturing International Corporation, 2012. SMIC 55nm Low Leakage Logic Process Standard Cell Library Databook v2.0. http://www.smics.com/eng/design/libraries_smic.php

[21]Shi, Z.J., Yang, X., Lee, R.B., 2008. Alternative application-specific processor architectures for fast arbitrary bit permutations. Int. J. Embed. Syst., 3(4):219-228.

Open peer comments: Debate/Discuss/Question/Opinion


Please provide your name, email address and a comment

Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - 2022 Journal of Zhejiang University-SCIENCE