信号置换

摘要

一种构建配置网络的方法。根据要置换的信号数N的一组整数因数以及预先选择类型的开关来为置换网络的层选择一种配置。根据所选择的配置通过使用预先选择类型的开关构建层中的置换网络。

权利要求

1.一种用于信号置换的方法，其特征在于，包括：

根据要置换的信号数N的一组整数因数以及预先选择类型的开关，为置换网络的层选择一种配置；以及根据所选择的配置，利用预先选择类型的开关来按层构建置换网络，

其中，所述构建置换网络包括向所述开关分配多维坐标，其中每个开关具有与下一层中的另一开关相同的坐标，且除了最后一层之外的每一层具有至少两个开关，这至少两个开关的坐标与下一层中的相应位置的开关的坐标不同。

2.如权利要求1所示的方法，其特征在于，每种类型的开关都能够从一定数量的信号中选择一个信号，对于不同类型的开关，该数量是不同的。

3.如权利要求2所述的方法，其特征在于，每个整数因数对应于一种类型的开关可以从其中进行选择的信号数量。

4.如权利要求1所述的方法，其特征在于，还包括选择所述一组整数因数w1，w2，...，wD，D为整数，以使N＝w1×w2×...×wD。

5.如权利要求4所述的方法，其特征在于，所述置换网络被配置成具有2D-1层的开关，这些开关包括w1：1，w2：1，...，和wD：1开关或者由w1：1，w2：1，...，和wD：1开关构成。

6.一种用于信号置换的方法，其特征在于，包括：

接收N个信号；

使用置换网络将这N个信号重新排序，其中该置换网络是由开关层构成的，且这些开关层具有基于N的一组整数因数以及预先选择类型的开关的配置；

向所述开关分配多维坐标，其中每个开关具有与下一层中的另一开关相同的坐标，其中除了最后一层之外的每一层具有至少两个开关，这至少两个开关的坐标与下一层中的相应位置的开关的坐标不同。

7.如权利要求6所述的方法，其特征在于，每层都具有N个相同类型的开关，每种开关都具有预定数量的输入端子和一个输出端子。

8.如权利要求7所述的方法，其特征在于，置换网络的每一层都将所述N个信号分成信号子集并置换信号子集的排序，子集中信号的数量等于层中每个开关拥有的输入端子数。

9.如权利要求7所述的方法，其特征在于，通过将多维坐标分配给所述开关来构建所述置换网络，层中的每个开关都具有不同的坐标，并配置所述开关从而当信号从一个层中的第一开关传播到下一个层中的第二开关时，这两个开关的坐标仅在一个维数上不同。

10.如权利要求6所述的方法，其特征在于，所述整数因数是w1，w2，...，wD，D是整数，以使N＝w1×w2×...×wD，且预先选择类型的开关包括w1：1，w2：1，...，和wD：1开关。

11.一种用于信号置换的装置，其特征在于，所述装置包括：

N个输入端子，N是整数；

N个输出端子；以及

置换网络，它被配置成形成以任意顺序将输入端子连接到输出端子的非阻断信号路径，所述置换网络由不同类型的开关的层构成，每层都具有同一类型的相同数量的开关，每个类型的开关都能从预定数量的信号中选择出一个信号，其中，层的数量和连续层的开关之间的连接是基于N的一组整数因数以及所使用的开关的类型，其中，通过向所述开关分配多维坐标来构建所述置换网络，每个开关具有与下一层中的另一开关相同的坐标，并配置所述开关以便当信号从一个层中的第一开关传播到下一层中的第二开关时，所述两个开关的坐标最多在一个维数上不同，其中除了最后一层之外的每一层具有至少两个开关，这至少两个开关的坐标与下一层中的相应位置的开关的坐标不同。

12.如权利要求11所述的装置，其特征在于，每个开关都具有输入端子和输出端子，第一层中开关的输入端子耦合到所述装置的N个输入端子，最后一层中开关的输出端子耦合到所述装置的N个输出端子，且对于最后一层以外的所有层，开关的输出端子都连接到下一层中开关的输入端子。

13.如权利要求11所述的装置，其特征在于，所述整数因数是w1，w2，...，wD，D是整数，以使N＝w1×w2×...×wD，且所使用开关的类型包括w1：1，w2：1，...，和wD：1开关。

14.如权利要求13所述的装置，其特征在于，所述置换网络被配置成具有2D-1层的开关，每一层都置换信号路径的不同子集的排序。

15.如权利要求14所述的装置，其特征在于，对于每个开关的第p层，p的范围从1到D，wp：1开关被配置成构成能置换wp个信号路径顺序的wp乘wp置换器，而对于每个开关的第q层，q的范围从D+1到2D-1，w2D-q：1开关被配置成构成能置换w2D-q个信号路径顺序的w2D-q乘w2D-q置换器。

16.如权利要求15所述的装置，其特征在于，第二层到第(2D-1)层中每个置换器的每个输入端子都连接到前一层中不同置换器的输出端子。

17.一种用于信号置换的装置，其特征在于，包括：

第一装置，它被配置成产生具有第一排序的N个信号；

第二装置，它被配置成接受第二排序的N个信号；以及

置换网络，它被配置成接收具有第一排序的N个信号并将这N个信号重新排序，从而所述N个信号具有第二装置可接受的第二排序，由不同类型的开关层构成所述置换网络，每个层都具有相同类型的相同数量的开关，每个类型的开关都能从预定数量的信号中选出一个信号，其中，所述置换网络的所述开关具有被分配的多维坐标，其中每个开关具有与下一层中的另一开关相同的坐标，且除了最后一层之外的每一层具有至少两个开关，这至少两个开关的坐标与下一层中的相应位置的开关的坐标不同。

18.如权利要求17所述的装置，其特征在于，层的数量和连续层的开关之间的连接是基于N的一组整数因数和所使用开关的类型。

19.如权利要求18所述的装置，其特征在于，所述第二装置是存储器。

20.如权利要求19所述的装置，其特征在于，所述第一装置是计算机主板。

21.如权利要求18所述的装置，其特征在于，所述整数因数是w1，w2，...，wD，D是整数，以使N＝w1×w2×...×wD，且所使用开关的类型包括w1：1，w2：1，...，和wD：1开关。

22.如权利要求21所述的装置，其特征在于，所述置换网络被配置成具有2D-1层的开关，每一层都具有N个相同类型的开关，每一层都置换N个信号的不同子集的顺序。

23.如权利要求17所述的装置，其特征在于，所述置换网络包括一现场可编程逻辑阵列。

24.一种用于将N个信号重新排序的装置，其特征在于，包括：

2D-1层的开关，D为整数，第n层和第(2D-n)层具有wn乘wn个开关，n的范围从1到D，且w1到wD是N的整数因数从而N＝w1×w2×...×wD，第一层开关将N个信号的顺序重新排序以产生第一组重新排序的信号，第i层开关将第(i-1)组的重新排序信号重新排序以产生第i组的重新排序信号，i的范围从2到2D-1，第(2D-1)组的重新排序信号与N个信号的目标排序相匹配，所述开关具有被分配的多维坐标，其中每个开关具有与下一层中的另一开关相同的坐标，且除了最后一层之外的每一层具有至少两个开关，这至少两个开关的坐标与下一层中的相应位置的开关的坐标不同。

25.如权利要求24所述的装置，其特征在于，N个信号中的每一个都被分配了D维坐标，第n坐标的范围从1到wn，第p层开关被配置成交换仅第p个坐标不同而其它维数中的坐标相同的信号，p的范围是从1到D，且第q层开关被配置成交换仅第(2D-q)个坐标不同而其它维数中的坐标相同的信号，q的范围从D+1到2D-1。

说明书

信号置换

技术领域

[0001] 本发明涉及信号置换。

[0002] 背景

[0003] 信号置换(signal permuting)用于改变信号的路由通路以连接具有不同顺序的信号线组的两个接口。例如，如图1A所示，如果连到输入电路11的接口10具有承载控制、数据1、数据2和接地信号的线L0到L3，而连到输出电路13的第二接口12具有承载数据
1、数据2、接地和控制信号的线L0到L3，则通过4乘4的置换网络14耦合输入和输出接口，该置换网络14将[L0，L1，L2，L3]映射到[L3，L0，L1，L2]。

[0004] 可以采用开关实现置换网络。在图1B中，一n：1开关16的输出可以反映其n个输入中的任何一个。通过采用在其输入处接收同组n个信号的多个n：1开关，就可以在其输出端子处将n个信号置换成任意顺序。图1C示出一个使用两个2：1开关20、22的2乘
2的置换网络，它置换两个信号S0和S1的顺序。

[0005] 可以使用n：1的多路复用器、写入其内容以反映单个地址输入的2n×1的随机访问存储器或者被编程为在输出处反映任何一个输入的现场可编程序的门阵列中的n输入
查找表实现一个n：1开关。对于每一种技术，可以最经济地实现的开关类型可能是不同的。

[0006] 附图概述

[0007] 图1A-1C是开关和置换网络的示意图。

[0008] 图2-3A和3B是置换网络的示意图。

[0009] 图4A是输入和输出端子之间映射的示图。

[0010] 图4B是示出信号的位置坐标转换的示图。

[0011] 图5A是具有置换网络的计算机的示意图。

[0012] 图5B是图5A的置换网络的输入和输出端子之间映射的示图。

[0013] 图6是置换网络的示意图。

[0014] 具体描述

[0015] 本发明针对使用预定组构件块(building block)的置换网络的构建。构件块是一种或多种可编程开关，每一种都能从几个信号中选择一个信号。置换网络被配置成多维开关阵列置换器(MSAP)，它可以通过编程开关来置换信号顺序以便根据置换算法选择信号。

[0016] 在附图中，每个置换器都在左边具有输入端子并在右边具有输出端子。参考图2，可以使用2D-1个层的开关(层L1到L2D-1)实现可置换N＝w1×w2×...×wD个信号的多维开关阵列置换器(MSAP)200。数字w1，w2，...，wD是整数。每个层包含相同数目(N)的同类开关，但不同层中开关的类型可以不同。对于λ＝1到D，层Lλ包括wλ：1开关，它们每一个都可以从wλ个信号中选择一个信号。例如，层L1包含w1：1开关，层L2包含w2：1开关，层LD包含wD：1开关。对于λ＝D+1到2D-1，层Lλ包括(2D-λ)：1开关。例如，层LD+1包括wD-1：1开关，而层L2D+1包括w1：1开关。通过将一个层中的开关输出端子适当地连接到下一个层中的开关输入端子，并且适当地将开关编程以便选择输入信号，MSAP200可以将其输入处的一组信号的顺序置换成其输出处的信号的任意顺序。

[0017] 层L1中开关的输入信号是MSAP的N个输入信号。层L1中的w1：1开关被配置成形成大量w1乘w1置换器202，数量是N/w1。每个w1乘w1置换器202包括多个w1：1开关，
数量是w1。每个w1乘w1置换器202从输入端子204接收w1信号，并在输出端子206上输
出一组重新排序的w1信号。置换器202的输出端子206被发送到层L2中的置换器输入端
子。层L2中的w2：1开关被配置成形成大量w2乘w2置换器208，数量是N/w2。每个w2乘w2
置换器208在输入端子210处接收w2信号，并在输出端子212处输出一组重新排序的w2信
号。置换器208的输出信号被发送到层L3中置换器的输入端子，等等。

[0018] 通常，层Lλ(λ＝1到D)中的开关被分组成wλ乘wλ置换器，每个置换器都从前一层接收wλ信号并在其输出处产生一组重新排序的wλ信号。层Lλ(λ＝D+1到2D-1)中的开关被分组成w2D-λ乘w2D-λ置换器，每个置换器都从前一层接收w2D-λ信号并在其输出处产生一组重新排序的w2D-λ信号。最末层L2D-1中的开关输出是MSAP的输出，它是一组重新排序的N信号。

[0019] 一层的输出端子和下一层的输入端子之间的连接是固定的(例如，硬连接的)。该连接可以通过虚线中围绕的区域214表示。配置每个层之间的连接，从而置换器的每一个输出信号都被发送到下一层中的不同置换器。因此，每个wλ乘wλ置换器从前一层中的wλ不同置换器接收wλ输入信号，置换该wλ信号的顺序，并将重新排序的wλ信号发送到下一层中的wλ不同置换器。

[0020] 本发明的优点在于可以根据哪种类型是可得的来使用各种类型的开关设计和构建MSAP。例如，为了设计可以置换N个信号的MSAP，可以首先确定N的因数wi。通常，可以以许多方法将数量N化为因数，每一种都对应于不同的设计。例如，假定选择因数wi从而N＝w1×w2×...×wD，随后，可以设计具有D维的MSAP，其中wλ是第λ维的宽度。通过以下
的描述将使“宽度”和“维”的意思变得显而易见。

[0021] 例如，有几个可以置换48个信号的MSAP结构：

[0022] ●可以通过选择N＝48，D＝2，w1＝6和w2＝8来设计二维MSAP。通过采用具有6：1开关的第一层、具有8：1开关的第二层和具有6：1开关的第三层来构成该48乘48
的MSAP。

[0023] ●可以通过选择N＝48，D＝3，w1＝3、w2＝4和w3＝4来设计三维MSAP。通过采用具有3：1开关的第一层、具有4：1开关的第二、第三、第四层和具有3：1开关的第五层来构成该48乘48的MSAP。

[0024] 可以通过选择N＝48，D＝5，w1＝2、w2＝2、w3＝2、w4＝2和w5＝3来设计五维MSAP。通过采用具有2：1开关的第一到四层、具有3：1开关的第五层和具有2：1开关的第六到九层来构成该48乘48的MSAP。

[0025] 当不同环境(例如，用于实现开关的不同技术，或者相同技术的不同商标的产品)提供不同类型的开关，或者允许最经济地实现不同类型的开关时，优点是很明显的。例如，在一种环境中，基本构件块可以是2：1开关，且所有其它n：1开关都可以由2：1开关构成。在另一种环境中，基本构件块可以包括2：1和3：1两种开关，且更大的开关可以由这两种类型的开关构成。可以使用对特定环境最经济的构件块来构成N乘N的MSAP。

[0026] 接着之前的实例，为了置换48个信号，还可能选择MSAP的结构，其中N被选为大于48，从而某些MSAP输入和输出是不使用的。该结构使用更多逻辑电路，但可以使特定MSAP结构可得。例如，通过选择N＝64，以下的三种配置可以用于构成64乘64的MSAP：

[0027] ●N＝64，D＝2，w1＝8，w2＝8。

[0028] ●N＝64，D＝3，w1＝4，w2＝4，w3＝4。

[0029] ●N＝64，D＝6，w1＝2，w2＝2，w3＝2，w4＝2，w5＝2，w6＝2。

[0030] 通常，对于特殊环境，如果必须从更小的开关构建更大的开关，则为了置换相同数量(N)的信号，使用较小开关的较高维MSAP将使用更少的逻辑电路。在上述实例中，如果必须通过2：1开关构建8：1和4：1的开关，则在这三种配置中，使用2：1开关的六维MSAP是更加经济的(即，将使用最少数目的全部开关)。因为维宽度wk与开关的大小成比例，通过将w1，w2，...，wD选为数值上尽可能接近将可以使用较小的开关和较少的逻辑电路。例如，D当N＝n 时，最经济的配置是选择w1＝w2＝...＝wD＝n。例如，如果必须通过2：1的开
关构成更大的开关，则MSAP的最有效率的设计是选择n＝2和使用2：1的开关作为MSAP
的基本构件块。参见以下的表1以便比较用各种大小的开关构成MSAP的效率。

[0031] 在图3A所示的实例中，12乘12的MSAP 300由两层的3：1开关和一层的4：1开关构成。MSAP 300包括层L1到L3。层L1包括3：1的开关，它被配置成形成3乘3的置换器
302、304、306和308。层L2包括4：1开关，它被配置成构成4乘4置换器310、312和314。
层L3包括3：1开关，它被配置成构成3乘3置换器316、318、320和322。在每个置换器内，不同的开关选择不同的输入信号，从而在它们的选择中没有重叠，导致置换器输出端子处出现输入信号的重新排序。

[0032] 层L1中的每个3乘3置换器在其输入端子处接收三个信号，置换这三个信号的顺序，并将重新排序的三个信号发送到层L2中的三个不同的置换器。例如，置换器302的第一输出端子连接到置换器310的第一输入端子。置换器302的第二输出连接到置换器312
的第一输入。置换器302的第三输出连接到置换器314的第一输入，等等。在这种方式中，层L1中置换器的三个输出信号中的每一个都将由层L2中的不同置换器重新排序。

[0033] 同样，层L2中置换器的每个输出都连接到层L3中不同置换器的输入。因此，层L2中置换器的四个输出信号中的每一个都将由层L3中的不同置换器重新排序。通过用每个置换器将信号合适地重新排序，12乘12的MSAP可以将12个输入信号重新排序成任一顺序
的12个输出信号。

[0034] 作为置换器如何将信号重新排序的说明，在每个置换器内示出虚线，表示从输入端子到输出端子的信号路由。具有顺序[S1，S2，...，S12]的12个输入信号在MSAP300的输出处被重新排序成顺序[S7，S5，S3，S9，S8，S1，S10，S2，S6，S12，S11，S4]。以下说明信号S3如何从图左边的输入端子处的线#3被重新排序成图右边的输出端子处的线#6。置换器302将信号S3从输入#3重新排序到输出#1，该输出#1连接到置换器310的输入#1。置换器310
将信号S3从输入#1重新排序到输出#2，该输出#2连接到置换器318的输入#4。随后，置
换器318将信号S3从输入#4重新排序到输出#6。图中从上到下将每一层中置换器的输入
和输出编号为#1到#12。

[0035] 以下描述一个层中开关的输出端子和下一个层中开关的输入端子之间的连接。这些连接是固定的(例如，硬连接的)。为了描述的目的，假定MSAP每一层中的开关形成D维阵列。层Lλ中的开关被表示成S[λ][x1，x2，...，xD]，其中1≤xk≤wk，k从1到D。数字x1表示开关的第一维坐标，数字x2表示第二维坐标，等等。通过在开关名称的末端添加下标来表示这些开关的输入。例如，开关S[1][2，3，4]具有输入S[1][2，3，4]1，S[1][2，3，4]2*等等。通过添加星号表示输出(例如S[1][2，3，4])。

[0036] MSAP的输出信号是最末层L2D-1的输出，即对于x1，x2，...，xD的各种组合，MSAP输*出是S[2D-1][x1，x2，...，xD]。为了简化开关符号的描述，使用虚构层L0，从而MSAP输入是*
L0输出。因此，对于x1，x2，...，xD的各种组合，MSAP输入是S[0][x1，x2，...，xD]。虽然不*
存在开关S[0][1，...，1]，但有信号S[0][1，...，1]，它是MSAP输入。

[0037] 对于λ＝1，2，...D，层Lλ中置换器仅沿着维数λ任意地置换前一层中置换器的输出。这意味着层Lλ中置换器中的开关仅从具有不同维数λ的标记的前一层中的开关接收信号，并仅置换这些信号。层Lλ中(λ≤D)每个wλ：1开关，表示成S[λ][x1，x2，...，xD]，具有wλ输入，即S[λ][x1，x2，...，xD]1，S[λ][x1，x2，...，xD]2，...，S[λ][x1，x2，...，xD](wλ)。这些输入映射到前一层的所有输出，其中开关坐标仅有维数λ不同：

[0038] S[λ][x1，x2，...，xλ，...，xD]1＝S[λ-1][x1，x2，...，1，...，xD]*

[0039] S[λ][x1，x2，...，xλ，...，xD]2＝S[λ-1][x1，x2，...，2，...，xD]*

[0040] S[λ][x1，x2，...，xλ，...，xD](wλ)＝S[λ-1][x1，x2，...，wλ，...，xD]*[0041] (1≤λ≤D；任何x1，x2，...，xD)

[0042] 对于λ＝D+1，D+2，...，2D-1，层Lλ仅沿维数2D-λ任意置换前一层的输出。这意味着层Lλ中置换器中的开关仅从具有不同维数2D-λ的标记的前一层中的开关接收信号，并仅置换这些信号。层Lλ中(λ＞D)每个w2D-λ：1开关，表示成S[λ][x1，x2，...，xD]，具有w2D-λ输入，即S[λ][x1，x2，...，xD]1，S[λ][x1，x2，...，xD]2，...，S[λ][x1，x2，...，xD](w2D-λ)。这些输入映射到前一层的所有输出，其中开关坐标仅有维数2D-λ不同：

[0043] S[λ][x1，x2，...，x2D-λ，...，xD]1＝S[λ-1][x1，x2，...，1，...，xD]*[0044] S[λ][x1，x2，...，x2D-λ，...，xD]2＝S[λ-1][x1，x2，...，2，...，xD]*[0045] S[λ][x1，x2，...，x2D-λ，...，xD](w2D-λ)＝S[λ-1][x1，x2，...，w2D-λ，...，xD]*[0046] (D+1≤λ≤2D-1；任何x1，x2，...，xD)

[0047] 参考图3B，MSAP 300中的开关被标为S[λ][x1，x2]，λ从1到3，x1从1到3且x2从1到4。为了符号的方便，MSAP输入信号被描述成层L0的输出信号，并标记成S[0][i，*
j]，i从1到3而j从1到4。层L1沿第一维数置换信号。这意味着层L0中开关的输出连
接到层L1中开关的输入，该层L0中开关具有第一维数中的不同坐标而第二维数中相同坐标的标记。例如，开关S[1][2，3]的三个输入连接到层L0中开关的输出，具体如下：

[0048] S[1][2，3]1＝S[0][1，3]*

[0049] S[1][2，3]2＝S[0][2，3]*

[0050] S[1][2，3]3＝S[0][3，3]*

[0051] 层L2沿第二维数置换信号。这意味着层L1中开关的输出连接到层L2中开关的输入，该层L1中开关具有第二维数中的不同坐标而第一维数中相同坐标的标记。例如，开关S[2][2，3]的四个输入如下连接：

[0052] S[2][2，3]1＝S[1][2，1]*

[0053] S[2][2，3]2＝S[1][2，2]*

[0054] S[2][2，3]3＝S[1][2，3]*

[0055] S[2][2，3]4＝S[1][2，4]*

[0056] 层L3沿第一维数置换信号。例如，开关S[3][2，3]的三个输入如下连接：

[0057] S[3][2，3]1＝S[2][1，3]*

[0058] S[3][2，3]2＝S[2][2，3]*

[0059] S[3][2，3]3＝S[2][3，3]*

[0060] MSAP 300的输出信号是来自层L3的12个开关输出，即S[3][1，1]*到S[3][3，4]*。

[0061] MSAP开关拓扑具有递归结构。如果从维数D＞1的MSAP中除去开关的第一和最末层(L1和L2D-1)，则剩余部分是多个具有维数D-1的更小MSAP，数量是w1。通常，在维数D＞1的MSAP中，对于第一维中1和w1之间的每一个固定坐标c，开关的子集{S[λ][c，x2，x3，...，xD]}(λ从2到2D-2且每个xk从1到wk)形成维数D-1的子MSAP，其维宽度是w2，
w3，...，wD。每个子MSAP都具有其自己的子MSAP等等，直到一维MSAP的水平。在以下描述的MSAP切换算法中反映了该MSAP的递归结构。

[0062] 根据切换算法配置MSAP中的开关，从而MSAP可以以任何选择的顺序置换信号。为了便于描述该算法，MSAP的每个输入信号都被描述成具有起始位置和目标位置。特定层中信号的位置写作[x1，x2，...，xD]并对应于开关的标记，它选择信号作为输出。例如，图3B中，输入线#3处的信号具有[3，1]的起始位置，因为该信号由开关S[0][3，1]选择并在其输出处反映。如前所述，层L0是虚构层并仅为了描述方便。当信号传播到层L1时，其位置变成[1，1]因为该信号由开关S[1][1，1]选择。当信号传播到层L2时，其位置变成[1，2]因为该信号由开关S[2][1，2]选择。随后在层L3中，信号的位置变成[3，2]因为该信号由开关S[3][3，2]选择。

[0063] 在三维(D＝3)MSAP中，假定输入信号具有起始位置[2，5，3]和目标位置[4，1，*6]。这意味着必须以一定的方式设置MSAP开关从而输入信号S[0][2，5，3] 被路由到输出*
信号S[5][4，1，6]。当信号通过MSAP传播时，在每个开关层中调整信号位置，反映信号传播经过的开关。因为每层仅在一个维数中置换信号，所以在一层中仅调整信号位置的一个坐标。例如，在D＝3的MSAP中，信号可以遵循以下位置路径：

[0064] L0：[2，5，3]

[0065] L1：[8，5，3]

[0066] L2：[8，7，3]

[0067] L3：[8，7，6]

[0068] L4：[8，1，6]

[0069] L5：[4，1，6]

[0070] 该位置路径确定如何设置每个层中的一个开关。为使信号从L0位置[2，5，3]传播到L1位置[8，5，3]，开关S[1][8，5，3]必须被设定为位置2。为使信号从L1位置[8，5，3]传播到L2位置[8，7，3]，开关S[2][8，7，3]必须被设定为位置5，等等。当用于MSAP输入信号的所有位置路径都确定下来时，就可以设置MSAP中的所有开关，从而所有的输入信号都被路由到MSAP的合适输出端子。因此，N位置路径(或信号路径)的集合可以用于确
定MSAP的开关设置配置。

[0071] MSAP切换算法

[0072] MSAP切换算法提供了一种配置MSAP以便在输出端子处实现所有可能的信号置换的方法。但是，切换算法提供的配置不是仅有的配置MSAP以置换信号的方法。还可以使用“强力(brute-force)”方法，通过以某些智能(例如，递归)检查所有可能的切换组合以找到解决方案。

[0073] MSAP切换算法包括算法1，它调用算法2。在以下算法1的描述中，在信号位置路径而非MSAP切换设置的方面描述MSAP切换程序。有N个信号，每个信号都具有D维起始位置和D维目标位置。算法1为所有信号确定位置路径，以MSAP拓扑允许的方式给出每个
信号在从L0到L2D-1每层中的位置坐标。两个信号不能占据任一层中的相同位置。每个信号的L0位置是其起始位置。通过算法1生成的每个信号的L2D-1位置将与信号的目标位置
相匹配。

[0074] 算法1

[0075] 算法1递归地调用其自身。每次调用算法1时，表示输入信号子集的参数∑就被传递给算法1。当初始调用算法1时，参数∑＝{所有信号}被传递给算法1。在随后的递
归调用中，参数∑将包含信号的连续的较小子集。算法1通过传递水平参数λ保持跟踪其递归的深度。当初始调用算法1时，将参数λ＝1提供给该算法。当算法1再次调用其自
身时，传递参数λ＝2，等等。

[0076] 对于任何给定的N，D，w1，w2，...，和wD从而N＝w1×w2×...×wD，算法1用参数λ表示递归深度和用∑表示信号的子集来执行以下步骤从而进行操作。开始，设置λ＝1。

[0077] 步骤1：如果λ＝D，跳到步骤5。

[0078] 步骤2：将∑中每个信号的Lλ-1位置复制到其Lλ位置。

[0079] 步骤3：调用算法2来置换∑中信号的Lλ位置，仅改变每个信号的第λ位置坐标，其中具有相同第λ位置坐标的∑中的两个信号不能具有相同的第(λ+1)至第D目标
坐标。

[0080] 步骤4：对于每个c，范围从1到wλ，递归地调用算法1，传递参数：

[0081] ∑＝∑中信号的子集，它具有等于层Lλ中的c的第λ位置坐标；以及

[0082] λ＝λ+1。

[0083] 步骤5：通过将每个信号的第λ位置坐标变成其第λ目标坐标，将∑中的信号从其L2d-λ-1中的位置置换成L2D-λ中的新位置。

[0084] 算法1的步骤3和5中执行的置换仅沿该层允许的特定维数置换信号。例如，层Lk中的开关仅沿维数k置换信号。算法1还遵循两个信号不能占据给定层中同一位置的规
则。可以确保该规则，因为如下所述，算法2通过交换信号对移动信号从而防止了信号的冲突(即，两个信号由同一开关选择)。

[0085] 算法2

[0086] 以下是算法2的描述，它由算法1的步骤3调用。由于算法1的递归性质，在层Lλ中，∑中的所有信号都将具有相同的第1到第(λ-1)位置坐标。另一方面，它们的第λ到第D位置坐标将经过所有可能的组合。因此，虽然每个信号仍具有D位置坐标，但∑实际上是根据层Lλ中位置的信号的(D-λ+1)维阵列。∑中每个信号的第λ位置坐标确定信号所在的阵列的“片(slice)”。每个信号的第(λ+1)到第D位置坐标确定信号所在的阵列
的“列(column)”。“片”和“列”的定义在下面给出。具有相同第λ位置坐标的两个信号处于相同片中，且具有相同第(λ+1)到第D位置坐标的两个信号处于相同列中。因此，∑中的信号阵列被分成wλ个不同片，从1标号到wλ。该阵列还被分成wλ+1×wλ+2×...×wD个不同列，不加以标号。算法1的步骤3仅改变每个信号的第λ位置坐标，从而信号仅在
其列中移动。

[0087] 以下是术语“片”和“列”的描述。片是包含由算法2处理的信号∑子集的可得位置坐标的子集。例如，考虑D＝5，w1＝6，w2＝5，w3＝4，w4＝3和w5＝2的WSAP。在这种情况中，总共6×5×4×3×2＝720个信号被置换，每个都具有5维的起始位置坐标和5
维的目标位置坐标。例如，一个位置[1，1，1，1，1]中开始的信号可以具有目标位置[6，5，4，
3，2]。假定当λ＝3，这表示算法1中递归的第三级时，调用算法2。在这种情况中，∑是具有维数1和2中恒定L2位置坐标的信号的子集。例如，∑中所有的信号都具有L2位置坐
标，其形式是[4，2，_，_，_]，从而∑正好包含4×3×2＝24个信号：[4，2，1，1，1]，...，[4，
2，4，3，2]。

[0088] 在算法1的步骤2中，∑中信号的L2位置被复制到它们的L3位置，从而这24个信号的L3位置也是[4，2，_，_，_]的形式。调用算法2以便重新排列L3位置内∑中的24个
信号，即算法2改变∑中24的信号的L3位置坐标。算法2根据其位置坐标将∑中的24个
信号分层4“片”和6“列”。4个片中的每一个都有6个信号，且6个列中的每一个都有4
个信号。

[0089] 4个片都包含具有给定的第三(由于λ＝3)L3位置坐标的那些信号。存在4个片，因为λ＝3且w3＝4。这些片被称作“片1”到“片4”。片k包含∑中第三L3位置坐
标是k的那些信号。例如，片3包含6个信号，它们的L3位置坐标是[4，2，3，1，1]，[4，2，3，
1，2]，[4，2，3，2，1]，[4，2，3，2，2]，[4，2，3，3，1]，和[4，2，3，3，2]。在调用算法2期间，片3中的信号具有这些六个L3位置，虽然占据这些位置的特定信号可以改变。

[0090] 当算法2交换两个信号时，这两个信号将交换片，这意味着它们将交换它们的第三L3位置坐标。同时，6个列包含具有第四和第五L3位置坐标(λ＝3以上的坐标)的给定组合的这些信号。因此，存在一列，其信号具有L3位置坐标[4，2，1，1，1]，[4，2，2，1，1]，[4，2，3，1，1]和[4，2，4，1，1]。存在另一个列，其信号具有L3位置坐标[4，2，1，3，2]，[4，2，
2，3，2]，[4，2，3，3，2]和[4，2，4，3，2]。该实例中使用的术语“列”表示一组L3位置坐标，其第四和第五维坐标是固定的。因此，具有L3位置坐标[4，2，2，3，1]和[4，2，4，3，1]的信号被称为是“同一列”，因为它们的第四和第五坐标[3，1]相匹配。在算法2中，列总是在置换后保持同组信号，因为交换操作仅交换同一列中的两个信号。

[0091] 已经描述了术语“片”和“列”的定义，以下是算法2执行的步骤的描述：

[0092] 1.FOR S＝1 TO wλ-1 DO：

[0093] 2. WHILE slice S contains at least 2 signals with identical(λ+1)st thto D target

[0094] coordinates DO：

[0095] 3. SET X0＝one of these signals

[0096] 4. FOR K＝0，1，2，...DO：

[0097] 5. Look for a signal Z in slices S+1 through wλ and in the same

[0098] column as XK(selected in Step 3 or 6)with the following

[0099] property：Z’s(λ+1)st to Dth target coordinates are not

[0100] identical to the(λ+1)st to Dth targetcoordinates of any

[0101] signal in slice S.IF found THEN BREAK from the“FOR

[0102] K”loop.

[0103] 6. Select a pair of signals signal YK+1 and XK+1 with the following

[0104] properties：

[0105] YK+1 is in slices S+1 through wλand in the same column as

[0106] X0，X1，...，or XK；

[0107] XK+1 is in slice S，and is different from X0，X1，...，and XK；

[0108] YK+1 and XK+1 have identical(λ+1)st to Dth target

[0109] coordinates.

[0110] There will always be such a pair of signals.[0111] 7. END FOR K

[0112] 8. LOOP：

[0113] 9. Swap signal Z with signal XK

[0114] 10. IF K＝0 THEN BREAK from the LOOP

[0115] 11. SET Z＝YK

[0116] 12. Zis now in the same column as some XJ.SET K to this J.

[0117] 13. END LOOP

[0118] 14. END WHILE

[0119] 15.END FORS

[0120] (

[0121] 1.FOR S＝1 TO wλ-1 DO：

[0122] 2. WHILE片S包含至少具有相同的第(λ+1)至第D目标坐标DO：

[0123] 3. SET X0＝这些信号之一

[0124] 4. FOR K＝0，1，2，...DO：

[0125] 5. 在片S+1至wλ并且在与XK相同的列中(在步骤3或6中选择的)查找具有下列属性的信号Z:Z的第(λ+1)至第D目标坐标与在片S中任何信号的第(λ+1)
至第D目标坐标相同.IF找到THEN BREAK“FOR K”循环.

[0126] 6. 选择具有下列属性的一对信号YK+1和XK+1：

[0127] YK+1是在片S+1至wλ并且在与X0，X1，...，或XK相同的列中；

[0128] XK+1是在片S中，并且不同于X0，X1，...，或XK；

[0129] YK+1和XK+1具有相同的第(λ+1)至第D目标坐标.

[0130] 将总是存在这样的一对信号.

[0131] 7. END FOR K

[0132] 8. LOOP：

[0133] 9. 将信号Z与信号XK交换

[0134] 10. IF K＝0 THEN BREAK从LOOP

[0135] 11. SET Z＝YK

[0136] 12. Z现在在与XJ相同的列中.SETK为这个J.

[0137] 13. END LOOP

[0138] 14. END WHILE

[0139] 15.END FOR S

[0140] )

[0141] 通过每次“固定”一个片来进行算法2，即一旦固定一片，在连续调用该算法时不改变其信号。步骤2的WHILE条件检查当前片的属性，该属性是算法2试图除去的。当不再发现该属性时，就固定了该片。经过步骤3-13的相当少的次数总是固定了一片。

[0142] 步骤3-13的目的在于将具有“重复的”第(λ+1)到第D目标坐标的信号移出层S，用来自在层S上的某些其它信号代替之，在层S中缺少其中所述的某些其它信号的第
(λ+1)到第D目标坐标。在这两个信号处于同一列中的理想情况下，算法2仅交换这两个
信号。但是，这对信号可以不在同一列中，从而执行一交换链，其中每一个都在不同的列中进行操作。第一个交换操作将缺少第(λ+1)到第D目标坐标的信号移动入层S，而最末的
交换操作将具有重复的(λ+1)到第D目标坐标的信号移出层S。

[0143] 图4A示出MSAP 300的输入和输出端子之间映射的实例。图4B示出12乘12 MSAP的输入信号的位置坐标如何从其开始位置坐标变成其目标位置坐标的实例。用以上的算法
1和算法2确定位置坐标的变化。层L1仅改变第一维的坐标，层L2仅改变第二维的坐标，
而层L3仅改变第一维的坐标。

[0144] MSAP的优点在于，它有效地使用预先选择的开关作为基本构件块。最简单且最有D效的MSAP仅使用n：1开关(n是整数)来置换N＝n 个信号。在这种情况中，有2D-1层，
每层都包含N个开关。由于D＝lognN，总共有N×(2lognN-1)个n：1开关。因此，用预先
选择的开关构建MSAP所需的逻辑电路量约为NlogN，其中该预先选择的开关具有固定的开关尺寸。

[0145] 以下在表1中给出了使用各种尺寸的开关构建的MSAP的效率比较。这里，假定较大开关是由较小开关构成的。表1示出，使用较大开关尺寸的MSAP需要更多的逻辑电路。例如，如果2：1开关是可得的，则用11个2：1开关的6维层构建N＝64的MSAP是最有效
的。使用5个4：1开关的3维层多需要36％的逻辑电路。使用3个8：1开关的2维层多
需要91％的逻辑电路。使用1个64：1开关的1维层多需要473％的逻辑电路。

[0146] 表1

[0147]对
相
2
＝
n与 差的 ％0 ％63 ％19 ％374

对
相
2
＝n与 率比的 ％001 ％631 ％191 ％375

总 关
的效 开1： 40 06 443 230
等 2 7 9 1 4
：
2
的
关
开1： )1-n
n ＝
个 (
每 关
成组 开1 1 3 7 36
1：
n
的 关 40 02 29 4
总 开 7 3 1 6
1
层 1 5 3 1
关
开
1：n 层每 46 46 46 46
N 2 4 8 46

[0148] MSAP的应用是在计算机的主板和子板之间置换信号。参考图5A，计算机500包括经由具有信号线#1到#12的接口504耦合到主板502的子板506。子板506包括存储器512，它可以由主板502访问。子板506和主板502由不同的公司制造，从而主板502在接
口504的信号线上以与存储器512识别的顺序不同的顺序发送信号。

[0149] 子板506包括置换网络508，它具有连接到接口504的输入端子和连接到接口510的输出端子，它顺次连接到存储器512。置换网络508将接口504的信号线中的信号路由到接口510的信号线，它具有存储器512可接受的新顺序。图5B示出接口504的信号线和接
口510的信号线之间的映射。作为实例，接口504的线#1上的信号s1映射到接口510的
线#7，而接口504的线#12上的信号s12映射到接口510的线#4。同样，从存储器512发
送的信号由置换网络508重新排序，随后传递到主板502上。

[0150] 使用现场可编程序的逻辑阵列(FPGA)实现置换网络508。FPGA包括可配置的逻辑部件，它们每一个都可以被编程以便接收大量输入并将任何一个输入传递到其输出，就象一个n：1开关。当首先引导计算机500时，子板506与主板502通信以便确定所需的置
换。子板506上的处理器(未示出)执行MSAP切换算法以便将可配置逻辑部件编程从而
构建实现所需置换的MSAP。

[0151] 在图6所示的实例中，18乘18的MSAP 600由4层的3：1开关和1层2：1开关构成。在该实例中，N＝18＝3×3×2，D＝3，w1＝3，w2＝3，且w3＝3。MSAP 600包括层
L1到L5。层L1，L2，L4，和L5包括被配置成形成3乘3置换器的3：1开关。层L3包括被配置成形成2乘2置换器的2：1开关。在每个置换器内，不同的开关选择不同的输入信号，从而在它们的选择中没有重叠。这使得在置换器的输出端子处呈现重新排序的输入信号。

[0152] 图6中，在置换器内示出开关标记。层L1的置换器602中的三个开关具有相同的第二和第三坐标和不同的第一坐标。因此，置换器602在第一维中置换输入信号的位置坐标。同样，层L1中的其它置换器也在第一维中置换输入信号的位置坐标。层L2的置换器
604中的三个开关具有相同的第一和第三坐标和不同的第二坐标。因此，置换器604在第二维中置换输入信号的位置坐标。同样，层L2中的其它置换器也在第二维中置换输入信号的位置坐标。

[0153] 以类似的方式，层L3中的置换器在第三维中置换输入信号的位置坐标。层L4中的置换器在第二维中置换输入信号的位置坐标。层L5中的置换器在第一维中置换输入信
号的位置坐标。层L1中的置换器的每个输出信号都被发送到层L2中的不同置换器，层L2
中的置换器的每个输出信号都被发送到层L3中的不同置换器，等等。

[0154] MSAP 600被设计成允许18个输入信号中的任何一个被路由到18个输出端子中的任何一个。在操作中，执行MSAP切换算法以便为18个输入信号确定转换路径。该转换路径经过5层开关，从而每个信号被路由到所需的输出端子且两个信号不会占据同一开关。随后，将开关编程以便根据MSAP切换算法确定的信号路径选择输入信号。

[0155] 其它实施例也在以下权利要求书的范围之内。例如，可以使用FPGA以外的装置实现开关。可以通过主板上的处理器而非通过子板上的处理器将开关编程。开关的配置(即，从其输入选择哪个信号和在输出处反映哪个信号)可以是动态可编程的，或者是可编程一次随后是永久固定的。执行位置换的MSAP可以被用作编码/解码消息的编码器/解码器的构件块。MSAP可以用来构建远程通信网络以便以非块的方式将来自一个位置处的节点的信号路由到其它位置的节点。MSAP还可以用于大量并行或超级计算应用中以在不同的处理器间路由信号。