1. 中国电子设备系统工程公司研究所,北京,100036
2. 密苏里州立大学堪萨斯分校计算机与工程学院,MO,美国,64110
3. 中国电子设备系统工程公司研究所北京,100036
4. 密苏里州立大学堪萨斯分校计算机与工程学院MO 64110美国
纸质出版:2007
移动端阅览
戴浩, 沈孝钧. 在7级混洗交换网络中实现16×16的可重排性[J]. 电子学报, 2007,35(10):1875-1885.
DAI Hao, SHEN Xiao-jun. Rearrageability of the 7-Stage 16×16 Shuffle Exchange Network[J]. Acta Electronica Sinica, 2007, 35(10): 1875-1885.
长期以来
人们猜想(2
n
-1)级的均匀混洗交换网络Ω对置换2
emn×2
emn是可重排的.若干论文企图从理论上给出其充分性证明
但都没有成功
包括最近的一次证明
[24]
仍然是错误的
但还没有人指出.本文的目的之一是澄清这一点.当
n
=3时已有学者给出了证明
.本文针对
n
=4时的7级Ω网络
给出了实现16×16可重排性的构造性证明.论文提出了避免内部冲突的平衡树模型
置换的连接图、回路图表示和对称图形、同解变换等概念
并基于图形压缩、图形剖分等方法
将16×16置换分为五种情况
共给出五种赋值算法.这些算法比较简洁
易于编程实现.本文提出的思想对研究高阶网络的可重排性也有一定参考价值.
It is a long outstanding conjecture that any (2
n
-1)-stage shuffle-exchange network (Omega network) is rearrageability for 2
emn×2
emn.Since then many researchers have attempted to solve this conjecture without success.A new result on the sufficiency 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 internal conflict
the repetition of permutations using connective graph and cycle grap
h
the concept of symmetry graph and equivalent transform are also presented in this paper.Based on the graph composition and bipartition the permutations 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.
0
浏览量
1246
下载量
7
CSCD
关联资源
相关文章
相关作者
相关机构
京公网安备11010802024621