It has long been an outstanding conjecture that any(2^(n)×2^(n))-stage shuffle exchange network(Omega net-work)is rearrangeable for 2n 62n.Many researchers have failed to prove this conjecture,including a recent ...It has long been an outstanding conjecture that any(2^(n)×2^(n))-stage shuffle exchange network(Omega net-work)is rearrangeable for 2n 62n.Many researchers have failed to prove this conjecture,including a recent one established by Hasan.However,nobody has pointed out its fallacy.Therefore,as one of the objectives,this paper shall clarify this fact.Since the case of n 53 has been proven by many researchers[1,2],this paper uses a con-structive approach to prove that when n 54,the 7-stage 16616 shuffle exchange network is also rearrangeable.The paper also presents the model of a balanced tree to avoid internal conflict,the representation of permutations using a connection graph and loop graph,and the con-cepts of symmetry graph and identical transform.Based on graphic composition and bipartition,the permutations 16×16 are divided into five classes,with five assignment algorithms proposed.These algorithms are simpler,clearer and easier to program.The techniques used for n=4 may provide hints for the general case of n>4.展开更多
基金supported by the National Science Foundation of USA(Grant No.9810692)University of Missouri-Kansas City Faculty Research Grant(UMKC FRG)(No.K-2-11678).
文摘It has long been an outstanding conjecture that any(2^(n)×2^(n))-stage shuffle exchange network(Omega net-work)is rearrangeable for 2n 62n.Many researchers have failed to prove this conjecture,including a recent one established by Hasan.However,nobody has pointed out its fallacy.Therefore,as one of the objectives,this paper shall clarify this fact.Since the case of n 53 has been proven by many researchers[1,2],this paper uses a con-structive approach to prove that when n 54,the 7-stage 16616 shuffle exchange network is also rearrangeable.The paper also presents the model of a balanced tree to avoid internal conflict,the representation of permutations using a connection graph and loop graph,and the con-cepts of symmetry graph and identical transform.Based on graphic composition and bipartition,the permutations 16×16 are divided into five classes,with five assignment algorithms proposed.These algorithms are simpler,clearer and easier to program.The techniques used for n=4 may provide hints for the general case of n>4.
