常忠祥，戴紫彬，李 伟，陈 帆，马 超

（信息工程大学，河南 郑州450001）

0 引 言

通用微处理器大多以字为单位进行操作，不能很好支持比特置换功能，极大制约了密码算法在处理中的运算性能，因此如何提高比特置换操作在处理器中的执行效率，成为了人们研究的热点。比特置换实现主要有数据选择器、互连网络、基本单元组合3种实现方式，采用数据选择器方式以北京科技大学曲英杰的实现方式为主，可以支持1－1、1－n（n为输入数据位宽）等置换，灵活性强。但存在着资源占用大，配置信息量大，功能冗余等问题，同时，由于其配置信息量大，若采用动态生成的方式，其延时和资源均难以接受，只能采用对配置信息提前配置的方式，不支持动态更换置换种类的功能；采用互连网络实现，以PALMS（princeton architecture laboratory for multimedia and security）的Ruby B.Lee等人提出的PPERM、CROSS、OM－FLIP［1］等指令为主，支持1－1的比特置换，减少了部分冗余功能，但也存在着配置信息量大，只能采用配置信息提前配置的方式，不支持动态更换置换种类；基本单元组合实现主要以通用处理器中移位、异或等基本单元组合为主，可以实现任何一种比特置换操作，但需要的基本单元次数较多，效率较低。

基于此，本文通过分析互连网络的拓扑结构和互连函数，结合归并排序算法的特点，提出了多次通过互连网络的方式实现比特置换，能够动态更换比特置换的种类，有效降低资源的消耗，具有较高的灵活性和处理性能。

1 相关知识

1.1 归并排序算法

归并排序算法［2］可以实现任意序列到固定升序或降序的功能，过程如下：