吴朋庭，李 军，何卫国，王明东

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

0 引 言

Butterfly网络广泛应用于比特扩散、比特循环移位等动态比特置换运算模块的硬件实现。以往的研究主要集中于挖掘其数据通路的递归特性[1-6]。例如，比特扩散运算。在每一层置换参数求解的过程中，Lee发现了一些Butterfly置换网络的递归特性，并利用这些特性对部分运算过程进行了简化[1]。简化的过程非常精妙甚至有些偶然，然而在数学的世界里面，偶然现象一定存在其必然的数学理论。所以，无论研究人员归纳出的Butterfly置换网络结构的递归特性多么精妙，都是建立在它的数学理论基础之上的衍生特征。只要充分利用其数学理论对运算进行推导，就可能获得优化程度不低于现有递归算法的方案。

本文旨在研究Butterfly网络的置换数学理论及其应用。首先采用数字与符号对Butterfly网络结构进行定义，其次利用这些定义总结归纳Butterfly网络结构的数学理论并予以证明，最后利用Butterfly网络的数学理论重新分析比特扩散和循环移位等特殊的置换运算，以期得到优化程度更好的硬件实现方案或者更加简单的置换参数求解过程，为研究人员进一步分析其他置换运算提供新的思路。

1 Butterfly网络的数学理论

图1为一个Butterfly置换网络结构，N（N=2n）比特数据对应的Butterfly置换网络的宽度为N，路由深度为n。

为了描述它的结构特征，需要引入一些定义。

原始数据从右到左第jn比特称为起点s(jn)，目标数据从右到左第j0比特称为终点……