对于互联网络的设计,通常是希望其结构不要过分复杂以降低成本,能提供连接的很大灵活性以满足算法以及应用的需要,提高其性能。同时还希望这种互联网络又可以通过使用一系列规整单一的基本构件组合而成, 或者经多次通过, 或者经多级连接来实现复杂的互联,模块性好,以便于用大规模集成电路来实现。
7.2.1 互联函数的表示
为了反映不同互联网络的连接特性,每种互联网络可用一组互联函数来定义。如果把互联网络的N个入端和N个出端分别用整数0,1,…,N-1来表示, 则互联函数就是表示互联网络的出端号和入端号的一一对应关系。 令互联函数为f,则它的作用是:对于所有的0≤j≤N-1,同时存在入端j连至出端f(j)的对应关系。当互联函数用来实现处理机之间数据变换时,互联函数也反映了网络输入数组与输出数组间对应的排列关系或者为置换关系。互联函数有三种表示法,一种是输入输出对应表示法,一种是循环表示法,另一种是函数表示法。
1.输入输出对应表示法
这种表示法把互联函数表示为:
这就是说0变换为f(0), 1变换为f(1),…,N-1变换成f(N-1), f是互联函数。例如,N=8,均匀洗牌函数的这种表示形式为:
2.循环表示法
把互联函数函数f(x)表示为(X0X1X2…Xj…Xk-1)其中k≤N, 循环表示有下列对应的函数关系f(X0)=X1,f(X1)=X2,……,f(Xj)=Xj+1,……f(Xk-1)=X0
其中Xi为结点编号,这里k为循环长度。
3.函数表示法
这里用x表示输入变量,用f(x)表示互联函数,常常把输入端x和输出端f(x)都用二进制编码表示,从中看出对应的函数关系和规模,写出表达式。
如x:{bn-1bn-2…bi…b0}互联函数对应地表示为f(bn-1bn-2…bi…b0)。
例如交换置换写为
它表示实现式二进制地址编号中第0位位值不同的输入端和输出端之间连接。
直接画出输入结点和输出结点互联拓扑结构图,称为互联结构图法,后面将介绍。
7.2.2 几种基本的互联函数
下面介绍常用的基本互联函数、它们的函数表达式以及主要的特征。以下例子中,用N表示节点数目, 当用二进制表示这些节点号码时,将用n位二进制数表示,其中n=LOG2N
1.恒等置换
相同编号的输入端与输出端一一对应互联所实现的置换即为恒等置换,其表达式为:
其中等式左边括号内的Xn-1Xn-2…X1X0和等式右边的Xn-1Xn-2…X1X0均为网络输入端和输出端的二进制地址编号。这种置换完成的变换图形如7.2.1所示。图的左部为输入端,右部为输出端。
2.交换置换
交换置换是实现二进制地址编号中第0位位值不同的输入端和输出端之间的连接。其表达式为:
它所实现的输入端与输出端的互联图形见图7.2.2。
3.方体置换
方体置换是实现二进制地址编号中第k位位值不同的输入端输出端之间的连接。其表达式为:
这是上述交换置换的一般情形。它应有n个方体置换,如以N=8为例,则有
这里是实现二进制第0位的方体变换
这里是实现二进制第1位的方体变换
这里是实现二进制第2位的方体变换
其变换图形见图7.2.3,其中即C0为交换置换。
4.均匀洗牌置换
均匀洗牌置换是将输入端分成数目相等的两半,前一半和后一半按序一个隔一个地从头至尾依次与输出端相连,这好比洗扑克牌时,将整副牌分成相等的两叠来洗,以达到理想的一张隔着一张的均匀情况, 故称为均匀洗牌置换,或简称为洗牌置换, 其函数关系可表示为:
由此表达式可见,洗牌变换是将输入端二进制地址循环左移一位即得到对应的输出端二进制地址。
逆均匀洗牌是均匀洗牌的逆函数, 它完成的变换图形如图7.2.4所示。两者的输入端和输出端正好互换了位置,其函数表达式为:
这就说明逆洗牌是将输入端二进制地址编号循环右移一位即得到相应的输出端地址。均匀洗牌与逆均匀洗牌是两种十分有用的互联函数,以它们代表的链路与以交换置换代表的开关多级组合起来可构成Omega(Ω)网与逆Omega(Ω-1)网络。σ函数在实现多项式求值、矩阵转置和FFT等并行运算以及并行排序等方面都得到广泛的应用。
5.蝶式置换
蝶式置换的名称源于FFT 变换的实现时图形的形状如蝴蝶式样。它被定义为:
这种置换是将输入端二进制地址的最高位和最低位互换位置即可求得相应输出端的地址。同样, 可定义子蝶式(subbutterfly)β(k)置换和超蝶式置换β(k)如下:
β(k)置换将输入端二进制地址第k位和最低位互换位置求得输出端地址。而β(k)是将输入端第n-k-1位和最高位互换位置求得输出端地址,图7.2.5给出N=8的蝶式β(2)、β(2)变换图。
6.移数置换
移数置换是将输入端数组循环移动一定的位置向输出端传输。其函数表达式无需用二进制编号来写,可表达如下:
a(X)=(X+k)mod N,0≤X≤N
k为常数, 指移动的位置值,也可以将整个输入数组分成若干个子数组,在子数组内进行循环移数置换,这种段内循环移数的表达式可写成为两个式子如下:
a(X)(r-1):0=((X)(r-1):0+k) mod 2r
a(X)(n-1):r=(X)(n-1):r
其中下标(n-1):r和(r-1):0分别指从n-1位到r位和从r-1到0位。
循环移数的变换图形见图7.2.6, 这种变换在实现并行计算和图像处理中很有用。
7.加减2i(PM2I)置换
加减2i置换实际上是一种移数置换包含2N个互联函数,其表达式为:
图7.2.7给出了这一函数的变换图像, 它是构成数据变换网络的基础。
分享到:
相关推荐
ICN2053集成了“Noise Free TM”技术,具有极佳的抗干扰特性,使恒流及低灰效果不受PCB板的影响。并可选用不同的外挂电阻对输出级电流大小进行调节,精确控制LED的发光亮度。 ICN2053会缓存输入的16位数据并转化为...
icn6211数据转换工具
icn6202寄存器配置工具,icn6202参考电路设计,彩条,icn6202参考i2c代码,icn6202调试文档
驱动芯片ICN2038s
mipi转rgb转换ic icn6211寄存器配置工具,可以用于生成icn6211初始化参数;icn6211 datesheet资料;
ICN9707 MIPI屏驅動IC調試指南
ICN2038 是一款专为 LED 显示屏设计的驱动 IC,采用 16 路恒流灌电流输出。
可以用来安卓程序调试6211屏参 LCM
mipi转RGB芯片ICN6211的使用说明以及根据porch值和CLK 生成初始化ICN6211的初始化程序。
ICN6201 is a bridge chip which receives MIPI ® DSI inputs and sends LVDS outputs. ICN6201 is primarily targeted for portable applications such as tablets and smart phones that utilize the MIPI DSI ...
ICN6202为mipi转LVDS芯片,笔者已经在高通平台上成功批量使用,效果不错,值得向大家推荐
ICN6211芯片是将MIPI信号转换为RGB信号的一颗芯片
使用icn6211转RGB 的显示屏
MIPI转RGB
ICN2595 16路恒流输出LED驱动芯片介绍
MINI DSI转LVDS
ICN2053芯片指令详细较少,包括寄存器...ICN2053集成了“Noise Free TM”技术,具有极佳的抗干扰特性,使恒流及低灰效果不受PCB板的影响。并可选用不同的外挂电阻对输出级电流大小进行调节,精确控制LED的发光亮度。
面向负载均衡的ICN内容路由研究,谢建涛,徐明伟,目前,信息中心网络(ICN)是一种以内容为中心的下一代互联网体系结构,并且成为研究人员关注的焦点。但是由于互联网内容的爆炸性
ISDN low-level module for the ICN active ISDN-Card.
ICN6211所有资料集,调试说明,原理图,参考设计,配置工具等等