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

长期以来,人们猜想(2n-1)级的均匀混洗交换网络Ω对置换2^<em>n×2^<em>n是可重排的.若干论文企图从理论上给出其充分性证明,但都没有成功,包括最近的一次证明^24],仍然是错误的,但还没有人指出.本文的目的之一是澄清这一点.当n=3时已有学者给出了证明 .本文针对n=4时的7级Ω网络,给出了实现16×16可重排性的构造性证明.论文提出了避免内部冲突的平衡树模型,置换的连接图、回路图表示和对称图形、同解变换等概念,并基于图形压缩、图形剖分等方法,将16×16置换分为五种情况,共给出五种赋值算法.这些算法比较简洁,易于编程实现.本文提出的思想对研究高阶网络的可重排性也有一定参考价值.

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

It is a long outstanding conjecture that any (2n-1)-stage shuffle-exchange network (Omega network) is rearrageability for 2^<em>n×2^<em>n.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 graph,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.