7.1.2 互连函数

　　为了反映不同互连网络的连接特性，每种互连网络可用一组互连函数来描述。如果将互连网络的N个输入端和N个输出端分别用整数0，1，…，N-1来表示，则互连函数表示相互连接的输出端号和输入端号之间的一一对应关系。或者说，存在互连函数f，在它的作用下，输入i应与输出f(i)相连，。当互连网络用来实现处理器与处理器之间的数据变换时，互连函数也反映了网络输入数组与输出数组间对应的置换关系或称排列关系。所以互连函数有时也称为置换函数或排列函数。
　　表示互连函数通常用两种方法：一种是函数表示法，另一种是输入输出对应表示法。
　　函数表示法用x表示输入端变量，用f(x)表示互连函数。x还常用几位二进制形式来表示，写成。互连函数则对应地表示为。例如下面将具体介绍的均匀洗牌函数可表示为，左端括号内是输入端变量的二进制表达式，即为均匀洗牌函数，等式右端是该函数的具体表达式。
　　输入输出对应表示法把互连函数表示为： 这就是说0变换为f(0)，1变换为f(1)，…，N-1变换成f(N-1)。f是互连函数。例如，N＝8均匀洗牌函数的这种表示形式为： 有时还把互连函数f(x)表示为：,所谓"循环"表示，则代表对应关系为：,…,称为该循环的长度。
　　下面介绍常用的基本互连函数、它们的函数表达式和主要的特征。
　　1. 恒等置换
　　相同编号的输入端与输出端一一对应互连所实现的置换即为恒等置换，其表达式为：
　　　
　　其中等式左边括号内的 和等式右边的 均为网络输入端和输出端的二进制地址编号。这种置换完成的变换图形如7.3所示。图的左部为输入端，右部为输出端。
　　2. 交换置换
　　交换置换是实现二进制地址编号中第0位位值不同的输入端和输出端之间的连接。其表达式为：
　　
　　它所实现的输入端与输出端的互连图形见图7.4。