比特置换与数学理论的数学理论融合研究.docx

比特置换与数学理论的数学理论融合研究 摘要：针对当前比特置换运算研究主要聚焦于Butterfly网络结构的递归特性的现状，提出了一种利用Butterfly网络结构的数学理论进行比特置换运算研究的新思路。首先采用数字与符号对Butterfly网络结构进行定义，其次利用这些定义总结归纳出Butterfly网络结构的数学理论，最后利用Butterfly网络的数学理论重新分析比特扩散和循环移位等特殊的置换运算，以期得到优化程度更好的硬件实现方案或者更加简单的置换参数求解过程，为研究人员进一步分析其他置换运算提供理论支撑。 0引言Butterfly网络广泛应用于比特扩散、比特循环移位等动态比特置换运算模块的硬件实现。以往的研究主要集中于挖掘其数据通路的递归特性本文旨在研究Butterfly网络的置换数学理论及其应用。首先采用数字与符号对Butterfly网络结构进行定义，其次利用这些定义总结归纳Butterfly网络结构的数学理论并予以证明，最后利用Butterfly网络的数学理论重新分析比特扩散和循环移位等特殊的置换运算，以期得到优化程度更好的硬件实现方案或者更加简单的置换参数求解过程，为研究人员进一步分析其他置换运算提供新的思路。1 Butterfly网络的数学理论图1为一个Butterfly置换网络结构，N(N=2为了描述它的结构特征，需要引入一些定义。原始数据从右到左第j以权重w(i)为宽度，第i层数据被划分的2从起点s(j综上所述，存在以下路由等式：由于位移主要发生在横坐标上，仅考虑横坐标上的投影，则有：定理1从任一起点s(j证明：假设从起点s(j由于两条路由路径的终点相等，那么这两条路径在终点或者终点之前必定存在一个交点，且在此之后汇聚成一条路径。假设交点存在于第t层，则有：由于两条路径在路由点r(t,j当r(t,j当r(t,j因此，有：等式的左侧为偶数，等式的右侧为奇数，产生矛盾，定理1得证。定理2任一起点s(j证明：将起点s(j根据式（2），有：根据定理1，有：当j当j对于不含进位的单比特加减法，有：因此，定理2得证。由于Butterfly置换网络的数学理论本质就是初始坐标与目标坐标的二进制展开式的按位异或运算。因此，只要知道输入数据的初始坐标和目标坐标，就能通过异或运算快速得到该数据的路由向量d，从而为求解Butterfly置换参数做好准备。如图2所示，初始坐标为“5”和“3”的数据需要通过Butterfly网络分别置换到“2”和“5”的目标位置。它的各层置换参数与路由向量元素的数值相等，位置正好处于各层的路由点r(i,j因此，求出路由路径各层路由点的横坐标就能快速得到Butterfly网络的置换参数。根据路由路径的定义和异或运算的交换特性，可得递归算法：由于已知终点e(j综上所述，如图3所示，求解某置换运算的Butterfly置换参数的算法步骤可以分解为：(1）根据已知条件求解数据的起始地址；(3）初始地址和目标地址异或得到路由向量集合，设置i=0;(4）使用路由向量第i层元素d[i],，修正其上所有层路由向量元素d[i+1]～d[n-1]的位置，i++;(5）重复步骤（4）直到i=n-1，即得到Butterfly置换参数。可以选择目标地址为参照坐标系，由此合并步骤（1）和步骤（2），调整为根据已知条件求解目标地址上数据来源的起始地址。2 Butterfly网络数学理论的应用2.1 PDEP运算如图4所示，PDEP运算是一种比特扩散运算。它根据置换掩码数据中“1”的数量m，选中输入数据最低m比特数据，然后将选中的这些数据从右至左第j比特移位到掩码数据中从右至左第j个“1”对应的位置上，0≤j≤m-1。Lee等人发表的论文证明了PDEP运算可以采用Butterfly置换网络结构实现，并提出了置换递归算法来对置换参数进行求解。整个求解过程在硬件实现时被分解为3个步骤：(1）计算置换掩码mask在位置区间[j,0],(0≤j≤N-1）中“1”的数量POPCNT(mask[j:0]);(2）在第i行，对k(i)=2(3）将（2）中计算的结果按照左对齐的方式放在第i行第(2t+1)×k(i)-1列的位置，从而得到完整的置换参数作为对比，本文采用第一章提出的Butterfly网络的置换数学理论对PDEP运算的置换参数求解过程进行推导。为了方便描述，以下采用8 bit PDEP运算进行分析，如图5所示。根据Butterfly置换网络数学理论求解置换参数的标准流程如下。(1）根据已知条件求解各目标位置上数据的起始位置。该运算的已知条件