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

作者：葛方斌; 张涛; 宋金玉; 赵敏; 陈维华

来源：通信学报, 2011, (10): 10-18.

• 混洗交换网络
• Omega网络
• 可重排性
• 入线重组
• 无冲突路由扩充 shuffle-exchange network
• Omega network
• rearrangeability
• rearranging inputs
• expanding routing without conflict

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

• 单位
  中国人民解放军陆军工程大学