在7级混洗交换网络中实现16×16的可重排性  

Rearrageability of the 7-Stage 16×16 Shuffle Exchange Network

作　　者：戴浩 沈孝钧 

机构地区：[1]中国电子设备系统工程公司研究所,北京100036 [2]密苏里州立大学堪萨斯分校计算机与工程学院

出　　处：《电子学报》2007年第10期1875-1885,共11页Acta Electronica Sinica

基　　金：NSF Grant(No.9810692);UMKCFRG Grant(No.K-2-11678)

摘　　要：长期以来,人们猜想(2n-1)级的均匀混洗交换网络Ω对置换2n×2n是可重排的.若干论文企图从理论上给出其充分性证明,但都没有成功,包括最近的一次证明[24],仍然是错误的,但还没有人指出.本文的目的之一是澄清这一点.当n=3时已有学者给出了证明[1,2].本文针对n=4时的7级Ω网络,给出了实现16×16可重排性的构造性证明.论文提出了避免内部冲突的平衡树模型,置换的连接图、回路图表示和对称图形、同解变换等概念,并基于图形压缩、图形剖分等方法,将16×16置换分为五种情况,共给出五种赋值算法.这些算法比较简洁,易于编程实现.本文提出的思想对研究高阶网络的可重排性也有一定参考价值.It is a long outstanding conjecture that any （2n - 1）-stage shuffle-exchange network （Omega network） is rearrageability for 2^n × 2^n. Since then many researchers have attempted to solve this conjecture without success. A new result on the suf- ficiency proof has been established by Hasan. however, nobody have pointed out this proof to be incorrect. To clarify this fact is one of the objectives of this paper. The case n = 3 was proved by many researchers. Using a constructive approach, this paper also proves that when n = 4 the 7-stage 16 × 16 shuffle exchange network is rearrageability. The model of the balanced tree to avoid intemal conflict, the repetition of permutations using connective graph and cycle graph, the concept of symmetry graph and equivalent transform are also presented in this paper. Based on the graph composition and bipartition the pennutations 16 × 16 are divided into five classes, and total five assignment algorithms are proposed. These algorithms are more simple and clear and to be programmed. The techniques used for n = 4 may provide useful hints for general case n 〉 4.

关 键 词：多级互连网络 混洗交换网络 内部冲突 可重排性 同解变换 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]