计算机体系结构课后习题原版答案_张晨曦著

开关模块数为N/k，网络的开关模块总数为（N/k）logkN。

一个k×k开关一对一连接的合法状态只有k种，所有开关都是一对一连接的合法状态才能实现一种一次使用网络的无冲突置换连接。因此，由（N/k）logkN个k×k开关组成的Omega网络一次使用的无冲突置换连接函数为：

kNlogkNk?(klogkNN)k?NNk

网络可以实现的置换连接数即为N个输出端的不同排序的排序数，即为N！，所以，Omega网使用一次实现的无冲突置换连接数占可以实现的置换连接数的比例为：

NNk/N!

若采用2×2开关模块构造的64个输入端的Omega网络，即有k=2，N=64，则Omega网使用一次实现置换连接的比例为：

6432?4.95?10-32 64！（3）若采用8×8开关模块构造64个输入端的Omega网络，即有k=8，N=64，则Omega

网使用一次实现置换连接的比例为：

648?3.85?10-16 64！（4）若采用8×8开关模块构造512个输入端的Omega网络，即有k=8，N=512，则

Omega网使用一次实现置换连接的比例为：

51264/512！

word文档 可自由复制编辑