3n-1级混洗交换网络的重排性研究

Study on the rearrangeability of 3n-1 stages shuffle-exchange network

可重排性是混洗网络研究和应用的核心问题,针对当前n>4的混洗交换网络尚无实用的重排解决方案这一现实,提出了3n-1级Omega网络的重排性实现策略。该策略将无冲突路由确定问题解析为路由入线重组和路由序列分解问题,给出了通过冲突节点调整与路由无冲突扩充重组入线的方法。对于路由无冲突扩充,不仅从理论上证明了其可行性,并给出了具体的扩充算法,首次解决了n=5时Omega网络的重排性实现问题。如果关于路由序列分解的Ge猜想能以构造性方法获证,那么,策略将彻底解决3n-1级Omega网络的重排性实现问题。

Rearrangeability is an essential issue in study of SE（shuffle-exchange） network and its application.Currently,there are no practical methods to realize rearrangeability of SE networks when n4.Based on the fact,a policy to realize the rearrangeability was proposed in 3n-1 stages Omega network.In the policy,the problem of constructing no conflict routing was translated into how to rearrange routing inputs and decompose routing sequence.A method to rearrange routing inputs by adjusting conflict nodes and expanding routings without conflict was offered.The feasibility of ex-panding routings without conflict was proved,and an algorithm of expanding routings was provided.The rearrangeability of Omega network was first realized when n=5.If Ge conjecture on decomposing routing sequence is constructively proved,how to realize the rearrangeability of the 3n-1 Omega network would be perfectly solved by the policy.