JPH02501788A - 組合わせ設計を用いて構成された再配置可能なマルチコネクション交換ネットワーク - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるため要約のデータは記録されません。

Description

【発明の詳細な説明】 組合わせ設計を用いて構成された再配置可能なマルチコネクション交換ネットワ ーク 技術分野 本発明は交換ネットワーク、特に呼損を防止するために再配置できるマルチコネ クションのブロードキャスト交換ネットワークに関する。

背景技術 多段交換ネットワークに接続された顧客設備が、所望の接続を実行できないよう な方法でネットワークが動作しているために望みどうりの接続が阻害されること が時としである。これはもちろん望ま・しくない状況であり、ひとつあるいはそ れ以上の存在する接続を取り除いて、新らしい要求を満足するために相互接続路 を再配置することによって解決することができる。このような再配置が可能であ れば、設定を望まれる新らしい相互接続の集合である新らしい割付けが可能であ ると言われる。既存の接続を再配置することなくすべての割当を実現できる交換 ネットワークは非閉塞であると言われ、一方、時には既存の接続を再配置するこ とによってすべての割当を実現できる交換ネットワークは再配置可能であると呼 ばれる。再配置可能ネットワークは非閉塞のネットワークに比べて一般に少数の クロスポイントで実現できる。再配置可能ネットワークの一例はその共通制御装 置と共に１９６４年４月１４日のＭ、Ｃ，ポール（Ｍ、　Ｃ，Ｐａｕｌｌ）の米 国特許３．１２９．４０７に開示されている。他の再配置可能なネットワークと してはベルシステムテクニカルジャーナル誌第４１巻第５号（１９６２年９月） の頁１４８１−１４９２のＶ、Ｅ、ベネシュ（Ｖ、Ｅ、　Ｂｅｎｅｓ）の“再配 置可能な３段接続ネットワークについて”（Ｏｎ　Ｒｅａｒｒａｎｇｅａｂｌｅ 　Ｔｈｒｅｅ−５ｔａｇｅ　Ｃｏｎｎｅｃｉｔｎｇ　Ｎｅｔｗｏｒｋｓ）と題す る論文と１９７７年７月２６日のＦ、に、ホワン（Ｆ、　Ｋ、　Ｈｗａｒｇ）の 米国特許４．０３８．６３８に開示されている。しかしこれらの周知の交換ネッ トワークは再配置可能なマルチコネクションネットワークではなく、再配置可能 なポイントッーポイントネットワークである。さらにこれらのネットワークの各 々は３段あるいはそれ以上の段から成っている。与えられた接続を実現するとき に必要なりロスポイントの数がネットワークの歪みと遅延パラメータに直接関連 しているような応用では、このような３段ネットワークで得られる特性には限界 がある。

１９８６年１月２１日のＧ、Ｗ、リチャードソン（Ｇ、貰。

Ｒｉｃｈａｒｄｓ）の米国特許４，５５６．００７には各々のネットワークの入 力チャネルを予め定められたパターンで多数の第１段スイッチの入力に永久的に 接続するような新規な接Ｍ装置を含む２段マルチコネクション交換ネットワーク を開示している。入力チャネルを第２段スイッチに接続されたネットワークの出 力チャネルに接続する任意の割当てについて、ネットワークは常に各入力チャネ ルが異る第１段スイッチによって第２段スイッチに従ってその人力チャネルに割 当てられた出力チャネルに接続されるように構成されている。従って、交換ネッ トワークは呼損が生じない再配置可能なマルチコネクションネットワークとなる 。この新規なる接続パターンによって追加の交換段の必要がなくなり、これによ ってネットワークのクロスポイントの総数を減少すると共に各々の相互の接続を 実現するのに使用されるクロスポイントの数を減らすことができる。

上述したリチャードの特許は接続装置を設計するための唯一の明白な設計法を示 している。この設計法は再配置可能な２段ネットワークを構成するには有効であ るが、他のもっと一般的な設計法が存在しないので、ネットワークの設計者が回 路パッケージ当りの端子の最大数、回路パッケージ当りの電力消費、故障グルー プの大きさΦ制約、各入力チャネルが接続される第１段スイッチの数ネットワー クの入力および出力チャネルの数の制約（例えば、２のべきにしたいというよう な）のような実際のネットワーク構成パラメータの観点から設計を最適化しよう とするときの自由が制約されることになる。

このようなことを考えれば、存在する問題は既知の再配置可能な２段ネットワー クの種類が限定されているということである。

発明の要約 本発明の原理に従えば、数学の分野で周知である組合せ設計の大きなりラスをネ ットワークの入力チャネルと、例えば２段の再配置可能なネットワークの接続装 置のような初期ネットワーククロスポイントの間で実現される永久コネクション のパターンを規定するために初めて有利に応用することによって上述した問題が 解決されて、技術上の進歩が達成される１組合わせ設計のクラスは３つのタイプ の設計を含んでいる。それはｌ）ブロック設計、２）直交配列、３）差集合であ る。これらの各々については本明細書において詳述し、これを新規なる方法で使 用して永久接続の有利なパターンを誘導する。

本発明に従う２段の再配置可能なマルチコネクション交換ネットワークはＮ３個 の入力チャネルを０２個の出力チャネルに接続し、Ｍ個の第１段スイッチと、例 えば矩形配列である第２Ｅ！ｊのスイッチから成る。各々の第１段スイッチは高 々ｒ個の入力と少くとも１個の出力を有する。単一のリンクによって与えられた 第１段スイッチを第２段スイッチに接続する。第２段スイッチはｎ２個の出力を 持ち各々はｎ２個の出力チャネルの各々に接続されている。ｔａ続装置は第１段 スイッチの入力の各々を５個のパラメータｂ、ｃ、ｒ、Ｍ、ｗを持つブロック設 計に従って関連する入力チャネルに接続する。（ｂ、ｃ、ｒ、Ｍ、ｗ）のブロッ ク設計は要素として第１段スイッチの一義的なスイッチ番号を持ち、ブロック設 計の与えられた行のスイッチ番号が与えられた行に関連する与えられた入力チャ ネルに接続された第１段スイッチを規定するような行列である。

本発明の他の実施例に従えば、！！装置の接続パターンはＭ×Ｎ２の接続行列に 従い、行列の行ｉの要素は次数Ｎの深さＭの直交配列の対応する要素にｉＮを加 えることによって得られる。配列は要素としてシンボル０，１．−−−−Ｎ−１ を持つ０行列は要素としてｄ。、ｄ、、−−−−−ｄｖ−□を持ち、行列の各列 は入力チャネルの内の高々Ｗに対応する０行列の与えられた列の各々の要素は与 えられた列に関連した入力チャネルがスイッチ番号ｄｅを持つ第１段スイッチに 接続されることを示す。

木発明の第３の実施例においては、接続装置によって実現される接続はＭ−１（ ｕ、ｒ、ｗ）の差集合り、＝　（ａｉ、−−−ａ’ｒ−１）　１≦ｉ≦Ｍ−１か ら誘導されるＭｕＸｒの接続行列に従う、（添字ｉはべき乗を示すものではなく 、差集合り五に属するａｉ。のような要素を示す、）差集合は３つのパラメータ ｕ、ｒおよびＷを持つ、接続行列はＭ、行を持ち、その各々がＵ行を持つＳｏ　 、５ｌ−−一−Ｓアー１のＭ個の集合から成る。入力チャネルの一義的なチャネ ル番号は集合Ｓ。に１個だけ現われる。任意の整数ｔ、１≦ｉ≦Ｍ−１．整数ｊ 、０≦ｊ≦ｒ−１、について集合Ｓｉの列ｊは集合Ｓ０の列ｊをａ”、たけ回転 して得られる２０行列の与えられた行で生ずるチャネル番号は与えられた行に関 連する与えられた第１段スイッチに接続された入力チャネルを規定する。

上述したネットワークの各々について、次のような性質が成り立つ、入力チャネ ルの内の任意のｎ２個のグループについて、０２個の入力チャネルのグループの 内の異るものに接続された１個の入力を各々が持つｎ２個の第１段スイッチのグ ループが存在する。ｎＲ個の第１段スイッチのグループ内部の接続はｎ２個の入 力チャネルのグループの異るものを第２段スイッチに接続するためにいつでも再 配置することができる。第２段スイッチによる接続は従って、これらの入力チャ ネルを０２個の出力チャネルのグルー・ブに接続するのに再配置することができ る。このためこのネットワークは０２個の入力チャネルのグループを１２個の出 力チャネルに接続するに際して再配置して呼損を避けることができる。さらに、 任意の入力チャネルはｎ２個の出力チャネルのすべてに接続することができる。

この方法は各々の第１段スイッチと第２段スイッチの間に多重リンクを持つよう にすることによって任意の数の出力チャネルを持つ大きなネットワークに対して 容易に拡張できる。この方法はまた第２段スイッチを追加し各々の第１段に対し て各々の追加の第２段スイッチを接続することによって拡張することができる。

上述したネットワークの各々において、接続装置と第１段スイッチは行と列を持 つ部分コンセントレートに置換できる。（行と列は第１段スイッチの出力と入力 に対応する。）ある行と列の交叉点のクロスポイントのパターンは組合わせ設計 によって類似した方法で規定される。

区夏立固皇皇碧ｌ 第１図は第２図に示したブロック設計法にもつすいて構成された２段の再配置可 能なブロードカストネットワークのブロック図： 第３図は第１図のネットワークと等価なネットワークの他の構成例； 第４図乃至第６図は第１図のネットワークの拡張と一般化であるネットワークの ブロック図； 第７図は第８図に示した直交配列にもとすく２段の再配置可使なブロードカスト ネットワークのブロック図：第９図は第７図のネットワークの構成の中間の段階 として用いられる接続行列： 第１Ｏ図は第７図のネットワークと等価なネットワークの代替構成のブロック図 ： 第１１図乃至第１３図は＄７図のネットワークの拡張と一般化であるネットワー クのブロック図： 第１４図は第１５図に示した二つの差集合にもとすいて構成された２段の再配置 可能なブロードキャストネットワークのブロック図： 第１６図は第１５図の差集合のひとつについての差表：第１７図は第１４図のネ ットワークの構成の中間ステップとして使われる接続行列： 第１８図は第１４図のネットワークと等価なネットワークの他の構成のブロック 図： 第１９図乃至第２１図は第１４図のネットワークの拡張と一般化であるネットワ ークのブロック図： 第２２図乃至第２７図はそれぞれ第４図、第５図、第１１図。

第１２図、第１９図および第２０図のネットワークにそれぞれ等価なネットワー クの他の構成のブロック図である。

第１図はブロック設計と呼ばれる組合わせ設計にもとすく２段再配置可能なブロ ードカストネットワーク１００のブロック図である。第２図はネットワーク１０ ０を構成するのに使われる特定のブロック設計を図示している。ブロック設計は ５つのパラメータｂ、ｃ、ｒ、Ｍ、ｗによって特徴付けられる。（ｂ、ｃ、ｒ、 Ｍ、ｗ）のブロック設計において、ｂ個の要素行あるいはブロックを構成するの に用いられ、全部で０行があり、０行の中で各々の要素は全部でｒ回現われ、各 行にＭ要素を持ち、２要素の各部分集合は正確にＷ行に現われるようになってい る。第２図の（６、ｌ０１５．３．２）のブロック設計においては、６種類の要 素（０，１，２，３，４，５）が行を形成するのに使用され、全部で１０行があ り、各要素は１０行の中で全部で５回現われ。

各行は３要素を持ち、２要素の各部分集合は正確に２つの行に現われる。ブロッ ク設計は周知の組合わせ構造である。

ネットワーク１００（第１図）は１０のビデオベンダ例えば、１５１．１５２か ら５つの顧客設備１７１乃至１７５に対してビデオ信号をブロードカストするの に使用される。ネットワーク゛　１００は１０個の入力チャネルＩＣＯ乃至ＩＣ ９からビデオ信号を受信し、各々が顧客設備１７１乃至１７５のひとつに接続さ れた５個の出力チャネルＯＣＯ乃至ＯＣ４にビデオ信号を送信する。顧客設備１ ７１乃至１７５の各々は出力チャネルの出力ビデオ信号を受信するための受信機 例えば、１７１−Ｒとネットワーク１００に含まれたネットワークコントローラ １８０に対して通信路１８１を経由して接続要求を送信するチャネルセレクタ、 例えば、ｌ　７１−Ｃ３とを有している。

ネットワーク１００は各々が５人力と１出力を有する５個の５×１の第１段スイ ッチ１１０−０乃至１１０−５と、その６個の入力の各々が第１段スイッチ１１ ０−０乃至１１０−５の関連するものに接続された６個の入力と、出力チャネル ＯＣＯ乃至ＯＣ４の各々に接続された５個の出力を持つ１個の６Ｘ５の第２段ス イッチを含んでいる。１２の入力チャネルは接続装置１８０によって３０個の第 １段スイッチの入力に接続されている。接続装置１４０は各々の第１段スイッチ の入力を、第２図の１６．　・１０．５．３．２）のブロック設計に従って入力 チャネルＩＣＯ乃至ＩＣ９の内の関連するものに接続する。（第１図には入力チ ャネルＩＣＯからの接続だけを明白に示している。）ブロック設計では、第１段 スイッチ１１０−０乃至１１０−５はそれぞれ一義的なスイッチ番号を持ってい る。ブロック設計の与えられた行におけるスイッチ番号は与えられた行に関連す る与えられた入力チャネルに接続される第１段スイッチを指定する０例えば、行 Ｏはスイッチ番号０、ｌおよび２を持つスイッチ１１０−０．１１（１−１，１ １０−２が入力チャネルＩＣＯに接続されることを示す。

行ｌはスイッチ番号０．１．５を持つスイッチ１１０−０．　ｌ　１０−１．１ １０−５が入力チャネルＩＣＩに接続されることを示す０行２はスイッチ番号０ ．２．４を持つスイッチ１１０−０．１１０−２，１１０−４が入力チャネルＩ Ｃ２に接続されていることを示し、以下同様である。接続装置１４０に関連して はいくつかの観測をすることができる。第１に、入力チャネルＩＣＯ乃至ＩＣ９ の各々は正確に３個の第１段スイッチの入力に接続されている。第２に、第１段 スイッチの対で二つを越える入力チャネルが交わっているものはない、（もし入 力チャネルがスイッチに接続されていれば、そのスイッチは入力チャネルが入射 しているという、もし二つのスイッチに同一の入力チャネルが入射すれば、この スイッチはその入力チャネルで交わっていると言う、）例えば、第１段スイッチ １１０−０と１１０−１は入力チャネルＩＣＯとＩＣＩだけで交わっている。接 続装置１４０の重要な特性は以下のように述べることができる。入力チャネルＩ ＣＯ乃至ＩＣ９の内の５個の任意のグループについて、その各々のひとつの入力 が入力チャネルのそのグループの異るものに接続された第１段スイッチｌ　１０ −０乃至１１０−５の内の５個のグループが存在する０例えば、入力チャネルＩ Ｃ０１ＩＣ２，ＩＣ５、ＩＣ？およびＩＣ８のグループを考える。第１８スイツ チ１１０−０゜１１０−−２，１１０−３，１１０−４，１１０−５のグループ の各スイッチではひとつの入力が入力チャネルのそのグループの異るものに接続 されている。スイッチ１１０−０の入力は入力チャネルＩＣＯに、スイッチ１１ ０−２の入力チャネルＩＣ２に、スイッチｌ　１０−３の入力は入力チャネルＩ Ｃ５にスイッチ１１０−４の入力は入力チャネルＩＣ７に、スイッチ１１０−５ の入力は入力チャネルＩＣ８にそれぞれ接続されている。顧客設備１７１乃至１ ７５から入力チャネルＩＣ０１ＩＣ２、ＩＣ５、ＩＣ７、ＩＣ８への接続要求が ある順序で与えられたときには、ネットワーク１００が一時的に要求された入力 チャネルのひとつあるいはそれ以上について接続ができないことがある。しかし スイッチ１１０−０．１　Ｉ　Ｏ−２，１１０−３、ｌ　１０−４．１　Ｉ　Ｏ −５がそれぞれ人力チャネルＩＣ０１ＩＣ２、ＩＣ５、ＩＣ７、ＩＣ８を第２段 スイッチ１９０の入力に接続するように第１段スイッチの接続を再配置すること ができる。第２段スイッチ１９０の中の接続が次に再配置されて、入力チャネル ＩＣＯ，ＩＣ２、ＩＣ５゜ＩＣ？、ＩＣ８が接続要求に従って顧客膜（１１１７ １乃至１７５に接続される。入力チャネルＩＣＯ乃至ＩＣ９の５つのグループの 内の任意のものについてこのことが可能であるから、ネットワーク１００は再配 置可能なブロードカストネットワークである。６個の第１段スイッチ１１０−０ 乃至１１０−５および第２段スイッチ１９０の中の接続の配置は通信路１８２ｊ ５よび１８３を経由してネットワークコントローラ１８０によって制御される。

第３図はネットワーク１００に等価な２段の再配置可能なブロードカストネット ワーク２００のブロック図である。ネットワーク２００の６×５の第２段スイッ チ２９０はネットワーク１００の第２段スイッチ１９０と同等である。しかし、 ネットワーク１００の接続装置１４０と第１段スイッチ１１０−０乃至１１０− ５はネットワーク２００の部分コンセントレータに置換されている０部分コンセ ントレータ２５０ではその１０個の列が入力チャネルＩＣＯ乃至ＩＣ９に接続さ れており、６個の行が第２段スイッチ２９０の６個の入力に接続されている０部 分コンセントレータではもし交叉点にクロスポイントが存在すれば、列は行に入 射しているという、同様に、交叉点にクロスポイントが存在すれば、行は列に入 射しているという、コンセントレータ２５０では、列の各々は第２図の（６，１ ０，５，３，２）のブロック設計の対応する行によって規定される行に入射する ６例えば、入力チャネルＩＣＯに接続された行は行０、ｌ、２に入射し、入力チ ャネルＩ　Ｃ１−に入射する列は行０、ｌ、５に入射し、以下同様である。

第４図は先に述べたネットワーク１００を拡張して形成される２段の再配置可能 なブロードカストネットワーク３００のブロック図である。ネットワーク３００ は１０個の人力チャネルＩＣＯ乃至ＩＣ９を１５個の出力チャネルＯＣＯ乃至０ Ｃ１４に接続するのに用いられる。ネットワーク３００の接続装置３４０はネッ トワーク１００の接続装置１４０と同等である。６個の第１段スイッチ３１０− ０乃至３１０−５は各々５×３の矩形スイッチであって、ネットワーク１００の ６個の５×１の第１段スイッチとは異っている。ネットワーク３００はまた３個 の６Ｘ５の矩形の第２段スイッチ３９０−０．３９０−１．３９０−２を含み、 各々はネットワーク１００のひとつの第２段スイッチ１９０と等価になっている 。

第５図はネットワーク１００の構成の他の拡張を表わす２段の再配置可能なブロ ードカストネットワーク４００のブロック図である。ネットワーク４００は１０ 個の入力チャネルＩＣＯ乃至ＩＣ９をｎ１個の出力チャネルＯＣＯ乃至ＱＣ（ｎ ｉ−１）に接続するのに使用される。ネットワーク４００の接続装置４４０はネ ットワーク１００の接続装置１４０１３よびネットワーク３００の接続装置３４ ０と同等である。ネットワーク４００の６個の５×３の第１段スイッチ４１０− ０乃至４１０−５はネットワーク３００の第１段スイッチ３１０−０乃至３１０ −５と同等である。しかし、ネットワーク４００においては、各々の第１段スイ ッチの３出力のすべてはｌ　８　Ｘ　ｎ　ｚの矩形の第２段スイッチ４９０に接 続されている。各々の第１段スイッチから第２段スイッチ４９０に対して多重リ ンクを作ることによって、ネットワーク４００は５個以上の出力チャネルを取扱 い、呼損を避けるために再配置することができるようになる。より一般的には、 各々の第１段スイッチが第２段スイッチに対してＸ本のリンクを持つことができ るようになる。

第６図は（ｂ、ｃ、ｒ、Ｍ、ｗ）のブロック設計から構成された一般化された２ 段のブロードカストネットワーク５００のブロック図である。ネットワーク５０ ０はＮ、本の入力チャネルＩＣＵ乃至ＩＣ（Ｎ、−１）を０２本の出力チャネル ＯＣＯ乃至０Ｃ（ｎｘｌ）に接続するようになっている。ネットワーク５００は ７個のｒｘρの第１段スイッチ、例えば、５０１．５０２と１個のＶ　Ｘ　ｎ　 ｚの第２段スイッチ５９０と、接続装置５４０とを含んでいる。接続装置５４０ は第１段スイッチの入力の各々を（ｂ、ｃ、ｒ、Ｍ、ｗ）ブロック設計に従って 入力チャネルの内の予め定められたものに接続する。第１段スイッチの各々は一 義的なスイッチ番号を有している。ブロック設計の要素は第１段スイッチのスイ ッチ番号であり、ブロック設計の与えられた行のスイッチ番号が、与えられた行 に関連した与えられた入力チャネルに接続される第１段スイッチのひとつを規定 する。ネットワーク５００の構成パラメータは第１表にまとめられている。

第　１　表 すは少くとも第１段スイッチの数であるＶに等しく、Ｃは少くとも入力チャネル の数Ｎｌに等しいことに注目していただきたい、ネットワークはブロック設計の 行を除去することによって入力チャネルを取扱かうようにネットワーク５００か ら誘導することができ、もしできれば第１段スイッチを除去することができる。

入力チャネルＩＣＯ乃至ＩＣ（Ｎｌ−１）の各々は正確にＭ個の第１段スイッチ の入力に接続されている。第１段スイッチのいずれの対もＷ個以上の入力チャネ ルで交わることはない、（この性質はＷ交わりの性質と呼ばれる。）入力チャネ ルＩＣＯ乃至ＩＣ（Ｎ、−１）の任意のｎ２個のグループについて、各々が入力 チャネルのグループの異るものに接続された１本の入力を持つ０８個の第１段ス イッチのｎ８個のグループ例えば５０１．５０２が存在する。数学的解析によっ て、ネットワーク５００はもしｎ２が高々 ’−ＣＭ”−１）／ｗ　’＋１　ｉｌｌに等しければ、再配置可能なブロードカ ストネットワークであると判定できる。ここで「ｙｌはｙより小さくない最小の 整数である。ネットワーク４００（第５図）のように各々の第１段スイッチと第 ２段スイッチの間に多重リンクを設置することによって、ネットワーク５００は もっと多数の出力チャネルの数ｎｔを取扱かうように拡張することができる。も し各々の第１段スイッチと第２段スイッチの間にＸ本のリンクがあれば、ｎ２が 高々Ｘ　［”（ＸＭ＋　１　）　（Ｍ　−１）　／ｗ’　］　（２］に等しけれ ば、ネットワークは再配置可能なブロードカストネットワークである。ネットワ ーク５００はネットワーク３００におけると同様に多数の第２段スイッチを持つ ように拡張することができる。（第９図） 第２２図はネットワーク３００（第４図）に等価な２段の再配置可能なブロード カストネットワーク５３００のブロック図である。６×５の矩形スイッチ５３９ ０−０．５３９０−１．５３９０−２はネットワーク３００の第２段スイッチ３ ９０−０．３９０−１．３９０−２と同等である。しかしネットワーク３００の 接続装置３４０と第１段スイッチ３１０−０乃至３１０−５はネットワーク５３ ００の３個の同等の部分コンセントレータ５３５０−０．５３５０−１．５３５ ０−２に置換されている。もちろん３個の部分コンセントレータ５３５０−０． ５３５０−１．５３５０−２はまた単一の大きな部分コンセントレータによって 表わすことができる。さらに単一の大きな部分コンセントレータの行を実際の設 計上の考慮によって順序を変更して例えば、同等な行が連続するようにしてもよ い。

第２３図はネットワーク４００　（第５図）に等価な２段の再配置可能なブロー ドカストネットワーク５４００のブロック図である＃　１８　×ｎ　＊の矩形ス イッチ５４９０はネットワーク４００の第２段スイッチ４９０と同等である。し かしネットワーク４００の接続装置４４０と第１段スイッチ４１０−０乃至４１ ０−５はネットワーク５４００では３個の（より一般的にはＸ個の）同等な部分 コンセントレータ５４５０−０．５４５０−１．５４５０−２で置換されている ０部分コンセントレータ５４５０−０．５４５０−１．５４５０−２の各々はネ ットワーク２００　（第３図）の部分コンセントレータ２５０と同等である。

−グにもと　くネットワーク 第７図は直交配列に呼ばれる組合わせ設計に従って構成された２段の再配置可能 なブロードカストネットワーク１１００のブロック図である。第８図はネットワ ーク１１００を作るのに用いられた特定の直交配列を示している。Ｎ次の深さＭ の直交配列はセルがＮ個の別個のシンボルで占有されたＭ行とＮ２個の列を有し 、セルがＮ種の別々のシンボルで占有され、行の多対が直交しているような行列 である。すなわちこれらのＮ２個の列は任意の２行からのＮ２対の要素を生じ、 これらのＮ２対はＮ個の別々のシンボルのすべてのＮ２個の順序対を含んでいる 。第８図の直交配列は４次で深さ３の行列であり、４種の別々のシンボル０゜１ ．２，３を有している１例えば１行Ｏおよび２は１６列が（０，０）、（０、ｌ ）、（０，２）、（０，３）、（１，１）、（１、Ｏ）、（１，３）、（１，２ ）、（２，２）、（２，３）、（２，０）、（２，１）、（３，３）、（３，２ ）、（３，１）、（３，０）の１６種の順序対を有しているから直交である。同 様に行０と１は直交であり、行１とても直交である。直交配列は周知の組合わせ 構造である。

第９図に示した３×１６の接続行列はネットワーク１１００を構成する中間スイ ップとして使用される。第９図の行列は行１の各々の要素に４を加え、行２の各 々の要素に８を加えることによって第８図の直交配列から得られる。一般に行ｉ の各々の要素にはｉＮが加えられる。

ネットワーク１１００（第７図）は６個の顧客設備１１７１乃至１１７６に対し て３２個のビデオベンダ、例えば、１１５１Ｊよび１１５２からのビデ信号を放 送するのに使用される。ネットワーク１１００は３２本の入力チャネルＩＣＯ乃 至ＩＣ３２から・　ビデオ信号を受信し、各々が顧客設備１１７１乃至１１７６ のひとつに接続された６個の出力チャネルＯＣＯ乃至ＯＣ５にビデオ信号を送出 する。顧客設備１１７１乃至１１７６の各々は出力チャネルのビデオ信号を受信 するための受信機例えば、１１７１−Ｒとチャネルセレクタ、例えば１１７１− Ｃ５を含み、これによって通信路１１８１を経由してネットワーク１１００に含 まれたネットワークコントローラ１１８０に対して接続要求を送信する、　ネッ トワーク１．１００は１２個の８Ｘ１の第１Ｐｊスイ°ツチ１１００−０乃至１ １００−１１を含み、その各々は８個の入力と１個の出力を持つ、第２段スイッ チ１１９０は１２×６であり、これはその１２個の入力の各々が第１段スイッチ １１００−０乃至１１００−１１の内の関連するものに接続されており、６本の 出力の各々は出力チャネルＯＣＯ乃至ＯＣ５のひとつに接続されている。３２本 の入力チャネルは接続装置１１４０によって９６個の第１段スイッチの入力に接 続されている。接続装置１１４０は１段スイッチの入力の各々を第９図の３×１ ６の接続行列に従　・って大力チャネルＩＣＯ乃至ＩＣ３１の内の予め定められ たものに接続する。接続行列の１６列の各々は入力チャネルＩＣＯ乃至ＩＣ３１ の内の２つに関連している０例えば、列０は入力チャネルＩＣＯおよびＩＣ１６ に関連し、列ｌは入力チャネルＩＣＩおよびＩＣ１７に関連し、列２は入力チャ ネルＩＣ２ｊ１５よびＩＣｌ３に関連し、以下同様になっている。第１段スイッ チの各々は一義的なスイッチ番号０．１．２、−−−−１１を持っている。接続 行列の与えられた列は与えられた列に関連した入力チャネルが、与えられた列の 番号を持つ第１段スイッチに接続されることを規定する０列０は入力チャネルＩ Ｃ０ＪよびＩＣ１６がそれぞれ番号０，４．８を持つ第１段スイッチｌ　ｌ　１ ０−０．１１１０−４、ｌ　１１０−８に接続されることを示す０列１は入力チ ャネルＩＣ１１３よびＩＣ１７がそれぞれ番号０．５．９を持つ第１段スイッチ １１１０−１，１１１０−５．１１１０−９に接続されることを示す１列２は入 力チャネルＩＣ２およびＩＣｌ３がそれぞれ番号０．６、ｌＯを持つ第１段スイ ッチ１１１０−０．１１００−６．１１１０−１０に接続されることを示す、接 続装置１１４０に関してはいくつかの見方ができる。第１に、入力チャネルＩＣ Ｏ乃至ＩＣ３１の各々は正確に３個の第１段スイッチに接続されている０例えば 、入力チャネルＩＣＯは第１段スイッチ１１１０−０．１１００−４、ｌ　１１ ０−８に接続されている。第２に第１段スイッチのどの対も２つを越える入力チ ャネルで交わることはない、接続装置１１４０の重要な特性は次のように述べる ことができる。入力チャネルＩＣＯ乃至ＩＣ３１の任意の６本のグループについ て、各々についてその一方の入力が入力チャネルのそのグループの異るものに接 続された６個の第１段スイッチ１１１０・　−０乃至Ｉ　Ｚｏｏ−１１のグルー プが存在する０例えば、入力チャネルＩＣ０１ＩＣ４、ＩＣ８、ＩＣｌ２．ＩＣ １６、ＩＣｌ３のグループを考えよう、第１段スイッチ１１１０−０．１１１０ −１．１１１０−２．１１１０−３．１１１０−４．１１１０−６のグループの 各スイッチのひとつの入力は入力チャネルのそのグループの異るものに接続され ている。スイッチ１１１０−０の入力は入力チャネルＩＣＯに、スイッチ１１１ ０−１の入力は入力チャネルＩＣ４に、スイッチｌ　１１０−２の入力は大力チ ャネルＩＣ８に、スイッチ１１１０−３の入力は入力チャネルＩＣ１２に、スイ ッチ］　ｌ　１０−４の入力は入力チャネルＩＣ１６に、スイッチ１１１０−６ の入力は入力チャネルＩＣｌ３に接続されている。１１客設備１１７１乃至１１ ７６から入力チャネルＩＣＯ％ＩＣ４、ＩＣ８、ＩＣ１２，ＩＣ１６に対して送 られる接続要求のあるものについては、ネットワーク１１００は要求された入力 チャネルのひとつあるいはそれ以上は閉塞してしまうことがある。しかし、入力 チャネルＩＣ０１ＩＣ４、ＩＣ８，ＩＣ１２゜ＩＣ１６，ＩＣｌ３をそれぞれ第 ２段スイッチ１１９０の入力に接続するようにスイッチ１１１０−０．１１１０ −１、Ｉｌｌ、０−２．１１１０−３．１１１０−４．１１１０−６を制御して 第１段スイッチを再配置することができる０次に接続要求に従って入力チャネル ＩＣＯ，ＴＣ４，ＩＣ８、ＩＣ１２，ＩＣ１６、ＩＣｌ３が顧客設備１１７１乃 至１１７６に接続されるように第２段スイッチ１１９０による接続を再配置する ことができる。入力チャネルＩＣＯ乃至ＩＣ３１の６個のグループの内の任意の ものについて、ネットワーク１１００は再配置可能なブロードカストネットワー クである。１２個の第１段スイッチｌ　１１０−０乃至１１１０−１１！３よび 第２段スイッチ１１９０による接続は２本の通信路１１８２および１１８３によ ってネットワークコントローラ１１８０によって制御される。

第１０図はネットワーク１１００に等価な２段の再配置可能なブロードカストネ ットワークのブロック図である。ネットワーク１２００の１２×６の第２段スイ ッチ１２９０はネットワーク１１００の第２段スイッチ１１９０と同等である。

しかし、ネットワーク１２００ではネットワーク１１００の接続装置１１４０と 第１段スイッチ１１１０−０乃至１１１０−５は部分コンセントレータ１２５０ に１換されている０部分コンセントレータ１２５０は入力チャネルＩＣＯ乃至Ｉ Ｃ３１に接続された３２列と第２段スイッチ１２９０の１２個の入力に接続され た１２人力を有する０部分コンセントレータ１２５０は１６列の部分コンセント レータを２個コピーしたものである。１２行は４行の集合３個から成る。任意の 整数ｉ、０≦ｉ≦３ｊ５よび任意の整数ｊ、０≦ｊ≦３について、第８図の直交 配列の列で配列の行ｊが行ｉを示すシンボルを含んでいる列に対応して集合ｊの 行ｉはその列に入射する０例えば、第８図の直交配列の列Ｏ１１，２および３で は行０にシンボル０が入っているから、集合０の行０は列０．１．２゜３に入射 する。同様に集合ｉの行３は、直交配列の列３．７．１１．１５で行１にはシン ボル３が入っているので１列３１．７．１１．１５に入射する０部分コンセント レータ１２５０の列１６乃至列３１のクロスポイントのパターンは列Ｏ乃至１５ のそれと同等であることに注意していただきたい。

部分コンセントレータはもしその行がその各列が各グループの正確に１個の行に 入射するようになっているときにＭグループに分割できるときに分解可能である と言われる０部分コンセントレータ１２５０はその行が３グループに分割でき、 各列は各グループの正確にひとつの行に入射しているので１分解可能である。

第１１図は先に述べたネットワーク１１００を拡張することによって構成される ２段の再配置可能なブロードカストネットワークのブロック図である。ネットワ ーク１３００は３２本の入力チャネルＩＣＯ乃至ＩＣ３１を１８本の出力チャネ ルＯＣＯ乃至０Ｃ１７に接続するのに用いられる。ネットワーク１３００の接続 装置１３４０はネットワーク１１００の接続装置１１４０と同等である。１２個 の第１段スイッチｌ　３１０−０乃至１３１０−１１の各々は８×３の矩形スイ ッチである。これに対してネットワーク１１００では第１段スイッチは１２個の ８×１のスイッチ１１　］　０−０乃至１１１０−１１であった。ネットワーク １３００はまた３個の１２×６の矩形の第２段スイッチｌ　３９０−０．１３９ ０−１．１３９０−２を含み、その各々はネットワーク１１００の１個の第２段 スイッチ１１９０と同等である。

第１２図はネットワーク１１００の構造の他の拡張を表わす２段の再配置可能な ブロードカストネットワーク１４００のブロック図である。ネットワーク１４０ ０は３２個の入力チャネルＩＣＯ乃至ＩＣ３１を０２個の出力チャネルＯＣＯ乃 至０Ｃ（ｎｔ−１）に相互接続するのに使用される。ネットワーク１４００の接 続装置１４４０はネットワーク１１００の接続装置１１４０ならびにネットワー ク１３００．の接続装置１３４０と同等である。

１２個の８×３の第１段スパツチ１４１０−０乃至１４１０−１１はネットワー ク１３００の第１段スイッチ１３１０−０乃至１３１０−１１と同等である。し かし、ネットワーク１４００においては、第１段スイッチのすべての３本の出力 は３６　Ｘ　ｎ　＊の矩形の第２段スイッチ１４９０に接続されている。第１段 スイッチから第２段スイッチ１４９０に対して多重リンクを持たせることによっ て、ネットワーク１４００は６個以上の出力チャネルを取扱い再配置によって呼 損を避けることができる。もっと一般的には、各々の第１段スイッチは第２段ス イッチに対してχ本のリンクを持つことができる。

第１３図は一般化された２段のブロードカストネットワーク１５００であり、深 さＭでＮ次の直交配列から構成される。ネットワーク１５００はＮ、個の入力チ ャネルＩＣＯ乃至ＩＣ（Ｎ。

−１）を０１個の出力チャネルＯＣＯ乃至ＯＣ（ｎ　ｚ　−１）に接続するのに 使用される。ネットワーク１５００は７個のｒｘ１２の第１段スイッチ例えば１ ５０１．１５０２と１個のｖ　Ｘ　ｎ　ｚ　（Ｄ第２段スイッチ１５９０それに 接続装置１５４０で構成されている。接続装置１５４０は第１段スイッチの入力 の各々をＭＸＮ”の接続行列に従って入力チャネルの関連する予め定められた１ つに接続する。第１段スイッチは一義的なスイッチ番号ｄ、、ｄ、、−−−−ｄ ｖ−＋を持つ、任意の整数ｉ、０≦ｉ≦Ｍ−１について、接続行列の行ｉの要素 は次数Ｎで深さＭの直交配列の対応する要素にｉＮを加算することによって得ら れる。直交配列はシンボル０．１．−−−−１Ｎ−１を有している０行列の各列 は入力チャネルのＷに関連している０行列の与えられた列における各要素ｅは。

与えられた列に関連した入力チャネルがスイッチ番号ｄ、を持っ第１段スイッチ に接続されることを規定する。ネットワーク１５ｏ８の接続パラメータを第２表 に要約する。

第２表 接続行列の列を除去し、もしできれば第１段スイッチを除去することによって、 も）と小数の入力チャネルを取り扱うネットワークをネットワーク１５００から 誘導できる。入力チャネルＩＣＯ乃至ＩＣ（Ｎｌ−１）の各々は正確にＭ個の第 １段スイッチの入力に接続される。第１段スイッチの対でＷを越える入力チャネ ルで交わるものはない、（ｗ交わり特性）、入力チャネルＩＣＯ乃至ＩＣ（Ｎｌ −１）の任意のｎ２のグループについて、その各々１本の入力がその入力チャネ ルのグループの１つの異るチャネルに接続された第１段スイッチのｎ２個のグル ープ例えば１５０１゜１５０２が存在する。数学的解析によって、ネットワーク １５００は高々 （Ｍ−１）　（ＬＭ／ｗＪ　＋　１　）　＋　”Ｍ／ｗ’　（３）に等しいｎ２ を有する再配置可能なブロードカストネットワークであることが保証される。こ こでｒｙｍはｙより小さくない最小の整数であり１−ＺＪはＺを越えることがな い最大の整数である。

もちろん、ネットワーク１５００はネットワーク１４００（第１２図）と同様に 各第１段スイッチと第２段スイッチの間に多重リンクを設けることによってより 多数の出力チャネルｎ２を取り扱うことができる。もし第１段スイッチと第２段 スイッチの間にχ本のリンクが存在すれば、ネットワークは再配置可能なブロー ドカストネットワークとなる、ここでｎ２は高々ＸＬＡ／Ｂ＋ｌＪ であり、Ａ＝ｗ　（Ｍ−１）（ＬｘＭ／ｗ」＋１）”Ｂ＝ｗ　（ＬｚＭ／ｗ」＋ １　）　−Ｘである。ネットワーク１５００はネットワーク１３００（第１１図 ）と同様に多重の第２段スイッチを用いることによって拡張できる。

第２４図はネットワーク１３００（第１Ｉ図）に等価な２段の再配置可能なブロ ードカストネットワークのブロック図である。

１２×６の矩形スイッチ６３９０−０．６３９０−１．６３９０−２はネットワ ーク１３００の第２段スイッチ１３９０−０．１３９０−１．１３９０−２と同 様である。しかしネットワーク１３００の接続装置１３４０と第１段スイッチｌ 　３１０−０乃至１３１０−１１はネットワーク６３００では３個の部分コンセ ントレータ６３５０−０．６３５０−１．６３５０−２に置換されている０部分 コンセントレータ６３５０−０．６３５０−１．６３５０−２の各々はネットワ ーク１２００（第１０図）の部分コンセントレータ１２５０と同等である。もち ろん３個の部分コンセントレータ６３５０−０，６３５０−１．６３５０−２は 単一の大きな部分コンセントレータで代表してもよい、さらに単一の部分コンセ ントレータの行を実験的な設計の配慮に従って、例えば同様の行が連続するよう に、並べ変えてもよい。

＠２５図はネットワーク１４００（第２図）と等価な２段の再配置可能なブロー ドカストネットワーク６４００のブロック図である。３６Ｘｎ、の矩形スイッチ ６４９０はネットワーク１４００の第２段スイッチ１４９０と同等である。しか しネットワーク１４００の接続装置１４４０と第１段スイッチ１４１０−０乃至 １４１０−１１はネットワーク６４００では３個（あるいはそれ以上のχ個）の 同等の部分コンセントレエータ６４５０−０．６４５０−１．６４５０−２に置 換されている０部分コンセントレータ６４５〇−〇、６４５０−１．６４５Ｏ− ２の各々はネットワーク１２００（第１０図）の部分コンセントレータと同等で ある。

に　と　〈ネ・・　ト　−ク」１酸 第１４図は差集合と呼はれる組合わせ設計に従う２段再配置可能なブロードカス トネットワーク２１００である。第１５図はネットワーク２１００を構成するの に用いられる二つの特定の差集合Ｄ　ｓ　、　Ｄ　ｔを示す。モジュロＵのｒ（ ＩＩの剰余の集合の集合Ｄ＝　（ａ　ｓ　−−−−ａ　ｒ　）はもしすべてのｄ ％ｏ　（モジュロＵ）について、正確にＷ個の順序対（ａｉ　、ａｉ　）か存在 し、ａｉとａｊはａｉ−ａＪ＝ａ　（モジュロＵ）であるようなりの要素である ときに（ｕ、ｒ、ｗ）差集合であると呼ばれる。（７，４，２）の差集合Ｄ８に ついての差表を第１６図に示す、差表の行と列にはり、の要素０．２．３．４で ラベル付けされている。差表の各セルの内容は列の番号を行の番号から引いたも ののモジュロ７て形成されている。第１６図の差表ては、１から６の間の各数字 は正確に２回現われている。一般に、（ｕ、ｒ、ｗ）の差集合における差表の内 容はモジュロＵて計算され、ｌからｕ−１までのすべての数字は差表で正確にＷ 回現われ、差集合はｒ要素を持つ、差２）羨集合り、およびＤ２から構成される 。Ｄ２はり、のス素の各々をモジュロ７で２倍することによって得られる。第１ ７図に示した２１×４の接続行列はネットワーク２１００を構成する中間ステラ ブとして利用される。第１７図の行列は差集合Ｄ　１．　Ｄ　２、から次のよう にして得られる０行列の２１個の行は各々か７行を持つ３つの集合Ｓｏ　、Ｓｊ 、Ｓｓを含む８番号０．１　、−−−−２７の各々が集合Ｓｏでは任意に置かれ ているｅｓｌの列は次のようにしてり、＝（Ｏ１２，３，４）から得られるｔ、 Ｓｌ　の列Ｏ３ｏの列Ｏと同一である。Ｓ、の列１はＳｏの列ｌを２位置だけ回 転することによって得られる。Ｓｌの列２はＳ。の列２を３位置たけ回転して得 られるａｓＩの列３はＳｏの列３を４位看たけ回転することによって得られる。

Ｓ、の列は次のようにして］）、＝　（０，４，６，１）から決定される。Ｓ２ ゛の列０はＳｏの列０と同じである。Ｓ２の列ｌはＳｏの列１を４位置たけ回転 することによって得られる。Ｓ２の列２はＳｏの列を６位置だけ回転することに よって得られる。Ｓ２の列３はＳｏの列３を１ｍ置たけ回転することによって得 られる。

ネットワーク２１００　（第１４図）は２８個のビデオベンダ例えば２１５１お よび２１５２からのビデオ信号を１３個の顧客設＠２１６１乃至２１７３にブロ ードカストするのに使用される。

ネットワーク２１００は２８個の入力チャネルＩＣＯ乃至ＩＣ２７のビデオ信号 を受信し、各々か顧客設＠２１６１乃至２１７３のひとつに接続された１３個の 出力チャネルＯＣＯ乃至０Ｃ１２を通してビデオ信号を送信する。顧客設備２１ ６１乃至２１７３の各々は出力チャネルのビデオ信号を受信する受信機例えば２ １６１−Ｒと、ネットワーク２１００に含まれたネットワークコントローラ２１ ８０に対して通信路２１８１を通して接続要求を送信するチャネルセレクタ例え ば２１６１−Ｃ３を含んでいる。

ネットワーク２１００は各々が４人力と１出力を有する。２１個の４Ｘｌの第１ 段スイッチ２１１０−０乃至２１１０−２０と、各々が第１段スイッチ２１１０ −０乃至２１１０−２０の内の関連するものに、接続された２１個の入力と出力 チャネルＯＣＯ乃至０Ｃ１２のひとつに接続された１３個の出力を有する単一の ２１×１３の第２段スイッチ２１９０とを含んでいる。２８個の入力チャネルは 接続装置２１４８によって８４個の第１段スイッチの入力に接続されている。接 続装置２１４０は各々の第１段スイッチの入力を第１７図の２４×４の接続行列 に従って関連する予め定められた入力チャネルＩＣＯ乃至ＩＣ２７に接続する０ 行列の要素は入力チャネルＩＣＯ乃至ＩＣ２７のチャネル番号０゜ｌ、−−−− ２７である１行列の２１行の各々は２１個の第ｉｐｊスイッチのひとつに関連し ている０行列の与えられた行で生ずるチャネル番号は与えられた行に関連した第 １段スイッチの入力に接続された入力チャネルのひとつを規定する０例えば、行 ０は入力チャネルＩＣ０１ＩＣ？、ＩＣ１４およびＩＣ２１が第１段スイッチ２ １００−０に接続されることを示す０行ｌは入力チャネルＩＣＩ、ＩＣ８、ＩＣ ｌ３、ＩＣ２２が第１段スイッチ２１１０−１に接続されることを示す０行２は 入力チャネルＩＣ２、ＩＣ９゜１Ｃ１６、ＩＣ２３が第り段スイッチ２１１０− ２に接続されることを示す、接続装置２１４０に関してはいくつかの観測が可能 である。第１に入力チャネルＩＣＯ乃至ＩＣ２７の各々は正確に３個の第１段ス イッチの入力に接続されている１例えば入力チャネルＩＣＯは第１段スイッチ２ ］１０−０．２１１０−７．２１１０−１４に接続されている。第２に３つのグ ループの第１段スイッチ２１１０−０〜２１１０−６．２１１０−７〜２１１０ −１３．２１１０−１４〜２１１０−２０を考えると、与えられたグループの任 意の２つの第１段スイッチについて、与えられたグループの２つの第１段スイッ チの両方と変わる各々の他のグループで、高々２つの第１段スイッチが存在する 。接続装置２１４０の重要な特性は次のように述べることができる。入力チャネ ルＩＣＯ乃至ＩＣ２７の１３の任意のグループについて、各々が入力チャネルの グループの異るものに接続されたひとつの入力を持つ第１段スイッチ２１１０− ０乃至２１１０−２０の１３のグループが存在する１例えば、入力チャネルＩＣ Ｏ乃至ＩＣ１２のグループを考えよう、１３個の第１段スイッチのグループの各 スイッチ２１１〇−〇〜２１１０−６．２１１０−９〜２１１０−１３および２ １１０−１６は入力チャネルのグループの異るものに接続されたひとつの入力が 存在する。顧客設備２１６１から２１７３から入力チャネルＩＣＯ乃至ＩＣ１２ に対して与えられる接続要求のある種のシーケンスについては、ネットワーク２ １００がひとつあるいはそれ以上の要求された入力チャネルを一時的に接続でき ないことがあり得る。しかしスイッチ２１１０−０〜２１１０−６．２１１０− ９〜２１１０−１３．２１１０−１６が入力チャネルＩＣＯ〜ＩＣＩ　２を第２ 段スイッチ２１９０の入力に接続するように接続を再配置することは常に可能で ある。第２段スイッチ２１９０の中の接続も次に再配置され、入力チャネルＩＣ Ｏ乃至ＩＣ１２が接続要求に従って顧客設備に接続されることになる。これは入 力チャネルＩＣＯ乃至ＩＣ２７の任意の１３本のグループについて可能であるか ら、ネットワーク２１００は再配置可能なブロードカストネットワークである。

２１個の第１段スイッチ２１１０−０乃至２１１０−２０および第２段スイッチ ２１９０の中の接続は２本の通信路２１０２ｇよび２１８３を経由してネットワ ークコントローラ２１８０によって制御される。

第１８図はネットワーク２１００と等価な２段の再配置可能なブロードカストネ ットワークのブロック図である。ネットワーク２２００の２１Ｘ１３の第２段ス イッチ２２９０はネットワーク２１００の第２段スイッチ２１９０と同等である 。しかしネットワーク２１００の接続装置２１４０と第１段スイッチ２１１０− ０乃至２１１０−２０はネットワーク２２００では部分コンセントレータ２２５ ０に置換されている。Ｓ分コンセントレータ２２５０は入力チャネルＩＣＯ乃至 Ｉ　Ｃ２７に接続された２８列と、第２段スイッチ２２９０の２１個の入力に接 続された２１行とを有する０部分コンセントレータ２２５０は２１行の各々は第 １７図の２１×４の接続行列の対応する行によって規定される２８列のひとつに 入射する０例えば、行０は列Ｏ１７，１４１３よび２１に入射する０行１は列ｌ 、８．１５および２２に入射する０行２は列２．９．１６および２３に入射・シ 、以下同様である０部分コンセントレータ２２５０の２１行は、各々が７行を有 する３つの集合から成る。与えられた集合の任意の２行について、他の集合の高 々２行で、与えられた集合の２行の両方と交わるようになって部分コンセントレ ータ２２５０は、行を３つのグループに分け、各列が各グループでは正確にひと つの行に入射するようになっているので分割可能である１分割できるコンセント レータはもし与えられたグループの任意の２つの行で、与えられたグループの２ 行の両方に交わる行が他のグループの各々で高々Ｗ行存在すれば、Ｗ−ダブル交 叉性と呼ばれる０部分コンセントレータ２２５０は−か２に等しいＷ−ダブル交 叉性を有する。

第１９図は先に述べたネットワーク２１００を拡張して得られる２段の再配置可 能なブロードカストネットワークのブロック図である。ネットワーク２３００は ２８個の入力チャネルＩＣＯ乃至ＩＣ２７を２６個の出力チャネルＯＣＯ乃至０ Ｃ２５にｖｔ統するのに使用される。ネットワーク２３００の接続装置２３４０ はネットワーク２１００の接続装置２１４０と同等である。２１個の第１段スイ ッチ２３１０−０乃至２３１０−２０の各々は４ｘ２の矩形スイッチであるが、 これはネットワーク２１００では２１個の４×１の第１段スイッチであるのと異 っている。ネットワーク２３００はまた２個の２１Ｘ１３の矩形の第２段スイッ チ２３７０−０と２３７０−１を含み、その各々はネットワーク２１００の１個 の第２段スイッチ２１９０と同等である。

第２０図はネットワーク２１００の構成の他の拡張を表わす２段の再配置可能な ブロードカストネットワーク２４００のブロック図である。ネットワーク２４０ ０は２８個の入力チャネルＩＣＯ乃至ＩＣ２７をｎａ個の出力チャネルＯＣＯ乃 至０Ｃ（ｎｔ−１）に接続するのに使用される。ネットワーク２４００の接続装 置２４４０はネットワーク２１００の接続装置２１４０１よびネットワーク２３ ００の接続装置２３４０と同等である。

２１個の４Ｘ２の第１段スイッチ２４１０−０乃至２４１０−２０はネットワー ク２３００の第１段スイッチ２３１０−０乃至２３１Ｏ−２０と同等である。し かし、ネットワーク２４００においては、各々の第１段スイッチの両方の出力は ４２Ｘｎ、の矩形の第２段スイッチに接続されている。第１段スイッチから第２ 段スイッチに対して多重リンクを設置することによって、ネットワーク２４００ は１３個以上の出力チャネルを取り扱ってなお呼損を避けるために再配置できる ことになる。もつと一般的には、各々の第１段スイッチは第２段スイッチに対し てχ本のリンクを持つようにすることができる。

第２１図はＭ−１個の（ｕ、ｒ、ｗ）の差集合から構成された一般化された２段 のブロードカストネットワーク２５００である。ネットワーク２５００はＮ１本 の入力チャネルＩＣＯ乃至ＩＣ（Ｎ、−１）を０２本の出力チャネルＯＣＯ乃至 ＱＣ（ｎ。

−１）に接続するのに使用される。ネットワーク２５００はＶ個のｒ×゛２の第 １段スイッチ、例えば、２５０１．２５０２と、１個のＶＸｎｌの第１段スイッ チ２５９０と接続装置２５４０とを含んでいる。接続装置２５４０は第１段スイ ッチの入力の各々をＭ　ｕ　Ｘ　ｒの接続行列に従って入力チャネルの内の関連 する予め定められたものに接続する。入力チャネルの各々は一義的なチャネル番 号を有している。接続行列はＭ−１の（ｕ、ｒ、ｗ）の差集合Ｄ＋　、Ｄｙ＝　 、−−−−、Ｄｍ−＋から誘導される。まず（ｕ、ｒ、Ｗ）の差集合り、を構成 する。Ｄ、以外の差集合の各々はり、の要素にモジュロＵで、Ｕに対して素であ るようなモジュロＵの剰余を乗することによって誘導される。接続行列のＭ１行 は各々がＵ行を持つＭ個の集合Ｓ　、、　Ｓ　、、−−−一、Ｓ　Ｍ−１から成 る。入力チャネルのチャネル番号の各々は集合Ｓ０で正確に１回だけ現われる。

任意の整数ｉ、１≦ｉ≦Ｍ−１．任意の整数ｊ、０≦ｊ≦ｒ−１，Ｍ−１個の（ ｕ、ｒ、ｗ）差集合Ｄ　Ｈ＝　（ａ’＋、−−−−１ａ・ｒ−１）について、集 合Ｓ、の列ｊは集合Ｓ０の列ｊをａ″、位置だけ回転することによって得られる 。（添字ｉはべき乗を表わすのではなく、ａ゛。のような要素が差集合り、に属 することを示す、）接続行列の与えられた行に現われるチャネル番号は、与えら れた行に関連した第１段スイッチの入力に接続される入力チャネルを指定する。

ネットワーク２５００構成パラメータを第３表に要約する。

第　３　表 Ｍ、は少くとも第１段スイッチの数Ｖに等しく、ｕｒは少くとも入力チャネルの 数Ｎ、に等しいことに注意していただきたい、もっと少い数の入力チャネルを扱 かうネットワークは、接続行列からセルを削除し、もしできれば、第１段スイッ チを削除することによってネットワーク２５００から誘導することができる。入 力チャネルＩＣＯ乃至ＩＣ（Ｎｌ−１）の各々は正確にＭ個の第１段スイッチの 入力に接続されている０Ｍグループ中の第１段スイッチを考えると、与えられた グループ中の任意の２つの第１段スイッチについて、与えられたグループの２つ の第１段スイッチの両方と交わる第１段スイッチが他のグループの各々に高々Ｗ 個存在する（Ｗダブル交わり特性）、入力チャネルＩＣＯ乃至ＩＣ（Ｎ、−１） の０２個のグループの任意のものについて、各々が入力チャネルのそのグループ の異るものに接続されたひとつの入力を持つ第１段スイッチのｎ２個のグループ 例えば、２５０１．２５０２が存在する。数学的な解析によって０２が高々Ｌ（ Ｍ　”　Ｍ　’　）　／ＷＪ　十Ｍ＋　１　（５）に等しいともにネットワーク ２５００は再配置可能なブロードカストネットワークであることが判定される。

ここでＬＺヨはＺを越えない最大の整数を表わす、もちろんネットワーク２５０ ０は、ネットワーク２４００　（第２０図）と同様に各々の第１段スイッチと第 ２段スイッチの間に多重リンクを設けることによって、もつと多数の１２個の出 力チャネルを取扱かうように拡張することができる。もし各々の第１段スイッチ と第２段スイッチの間にχ本のリンクを設けることによって、ｎａが高々 Ｌ（Ｘ”Ｍ”−Ｘ”Ｍ”）／ｗ、＋ＸＭ＋１　（６）に等しいまでは、ネットワ ークは再配置可能なブロードカストネットワークとなる。ネットワーク２５００ はまたネットワーク２３００　（第１９図）と同様に多数の第２段スイッチを取 扱かうように拡張することができる。

第２６図はネットワーク２３００　（第１９図）に等価な２段の再配置可能なブ ロードカストネットワーク７３００のブロック図である。２１Ｘ１３の矩形スイ ッチ７３９０−０．７３９０−１はネットワーク２３００の第２段スイッチ７３ ９０−０．７３９０−１と等価である。しかしネットワーク２３００の接続装置 ２３４０と第１段スイッチ２３１０−０乃至２３１０−２０はネットワーク７３ ００では２つの同等な部分コンセントレータ７３５０−０および７３’　５０− １に置換されている０部分コンセントレータ７３５０−０．７３５０−１の各々 はネットワーク２２００　（第１８図）の部分コンセントレータ２２５０と同等 である。もちろん、二つの部分コンセントレータ７３５０−０．７３５０−１は 単一の大きな部分コンセントレータで代表することができる。さらに単一の大規 模な部分コンセントレータの行は実際上の設計上の配慮に従って任意に順序を変 更し、例えば同等の行が連続するようにすることもできる。

第２７図はネットワーク２４００　（第２０図）と等価な２段の再配置可能なブ ロードカストネットワークのブロック図である。

４２　Ｘ　ｎ　＊の矩形スイッチ７４９０はネットワーク２４００の第２段スイ ッチ２４９０と同等である。しかし、ネットワーク２４００の接続装置２４４０ と第１段スイッチ２４１０−０乃至２４１０−２０は、ネットワーク７４００で は二つの（一般にはχ個）の同等な部分コンセントレータ７４５０−Ｏ１３よび ７４５０−１に置換されている０部分コンセントレータ７４５０−０乃至７４５ ０−１の各々はネットワーク２２００　（第１８図）の部分コンセントレータと 同等である。

２駆凍ムム拉１ヌ古 ＦＩＧ、１５ ＦＩＯ，１６ ＦＩＧ、１７ 国際調査報告 ｍｅ＋ＭｗＩＩｍ喝ム＊１１４ｍ１ｌｆｉ１１６．？Ｃ：：二／ＩｊＳ８７７０ ３０６３国際調査報告

Claims (60)

【特許請求の範囲】
1. １．Ｎ１とｎ２を１より大きい正の整数であり、ｎ２は高々Ｎ１に等しいとして 、Ｎ１個の入力チャネルをｎ２個の出力チャネルに対して選択的に接続する交換 ネットワークにおいて、該交換ネットワークは、 ｖを少くともｎ２に等しい正の整数として、ｒを１より大きい正の整数として、 該第１段スイッチの各々の入力のひとつを該各々の第１段スイッチの少くともひ とつの出力に選択的に接続する手段を各々が有する、高々ｒ個の入力と少くとも ひとつの出力を各々が持つｖ個の第１段スイッチと、各々が該出力チャネルの内 の異るものに接続されたｎ２個の出力と、各々が該第１段スイッチの異るものに 関連し、各々が該関連した第１段スイッチの少くともひとつの出力に接続された 複数個の入力とを持ち、該第２段スイッチは該第２段スイッチの該出力は該第２ 段スイッチの該入力に選択的に接続する機能を有する１個の第２段スイッチと、 該第１段スイッチの各々は一義的なスイッチ番号を持ち、ｂ、ｃ、Ｍは各々が１ より大きい正の整数、ｗは正の整数、Ｍ＋ｗは３より大、ｂは少くともｖに等し い数、ｃは少くともＮ１に等しい数とし、（ｂ、ｃ、ｒ、Ｍ、ｗ）のブロック設 計に従って該入力のチャネルの内の予め定められたものを該第１段スイッチの該 入力に接続するための接続手段であって、該ブロック設計の要素は該第１段スイ ッチのスイッチ番号であり、該ブロック設計の与えられた行のスイッチ番号に該 与えられた行に関連した与えられた入力チャネルに接続された該第１段スイッチ のひとつを規定するようになった接続手段とを 含むことを特徴とする交換ネットワーク。
2. ２．請求の範囲第１項に記載の交換ネットワークにおいて、ｎ２は高々「（Ｍ２ −１）／ｗ」＋１に等しいことを特徴とする交換ネトワーク。
3. ３．請求の範囲第１項に記載の交換ネットワークにおいて、該接続手段は該第１ 段スイッチの該入力の各々を、該入力チャネルのｎ２のグループの任意のものに ついて、各々のひとつの入力が該入力チャネルのｎ２のグループの異るものに接 続されるようになっていることを特徴とする交換ネットワーク。
4. ４．請求の範囲第１項に記載の交換ネットワークにおいて、該第１段スイッチの 各々は少くともＸ個の出力を有し、ｘを１より大きい正の整数として該第１段ス イッチの各々の出力を該各々の第１段スイッチの入力に選択的に接続する手段を 含み、該第２段スイッチの該複数個の入力は複数のｘ個の入力を有し、ｘ入力の 各グループは該第１段スイッチの内の異るものに接続されており、ｘ入力の各グ ループは関連する第１段スイッチの少くともｘ個のグループに接続されているこ とを特徴とする交換ネットワーク。
5. ５．請求の範囲第４項に記載の交換ネットワークにおいて、ｎ２は高々Ｘ［「（ ｘＭ＋１）（Ｍ−１）／ｗ」＋１］であることを特徴とする交換ネットワーク。
6. ６．請求の範囲第１項に記載の交換ネットワークにおいて、該第１段スイッチと 該第２段スイッチの各々はクロスポイントの矩形の配列であることを特徴とする 交換ネットワーク。
7. ７．Ｎ１とｎ２は１より大きく、ｎ２は高々Ｎ１に等しいような正の整数である としたとき、Ｎ１個の入力チャネルをｎ２個の出力チャネルに選択的に接続する 交換ネットワークであって、該交換ネットワークは ｖを少くともｎ２に等しい正の整数、Ｘとｒを１より大きい正の整数として、各 々がｒ個の入力と少くともＸ個の出力を有し、各々が該第１段スイッチの出力を 該第１段スイッチの出力に選択的に接続する手段を含むｖ個の第１段スイッチと 、Ｘ入力の各グループは該第１段スイッチの内の異るものに関連しており、ｘ入 力の各グループは関連する第１段スイッチの少くともｘ個の出力に接続されてお り、該第２段スイッチは該第２段スイッチの該出力を該第２段スイッチの該入力 に選択的に接続するための手段を含む、各々が該出力チャネルに接続されたｎ２ 個の出力とｘ入力の複数個のグループを形成する複数の入力を有する第２段スイ ッチと、 該第１段スイッチの該入力の各々を（ｂ、ｃ、ｒ、Ｍ、ｌ）のブロック設計に従 って該入力チャネルの内の予め定められた関連するものであって、該第１段スイ ッチの各々は一義的なスイッチ番号を有し、ｂ、ｃ、Ｍは各々が１より大きい正 の整数であり、ｂは少くともｖに等しく、ｃは少くともＮ１に等しく、ブロック 設計の要素は該第１段スイッチのスイッチ番号であり、該ブロック設計の与えら れた行のスイッチ番号は該与えられた行に関連する与えられた入力チャネルに接 続された該第１段スイッチのひとつを規定するような接続手段と を含むことを特徴とする交換ネットワーク。
8. ８．Ｎ１とＮ２は各々１より大きい正の整数であり、Ｎ１個の入力チャネルをＮ ２個の出力チャネルに選択的に接続する交換ネットワークにおいて、該交換ネッ トワークは、ｎ２をＮ２より小で、高々Ｎ１に等しい正の整数とし、ｖを少くと もｎ２に等しい正の整数とし、ｒを１より大きい正の整数として、各々が第１段 スイッチの入力と第１段スイッチの出力を選択的に接続することができる手段を 含む高々ｒ個の入力と複数個の出力を有するｖ個の第１段スイッチと、各々が該 複数個の該第１段スイッチの異るものの内の異るものに関連し、各々が関連する 該第１段スイッチに接続された複数の入力と、各々が該出力チャネルの異るもの に接続されたｎ２個の出力とを有し、該第２段スイッチの出力と該第２段スイッ チの入力を選択的に接続する手段を含む複数個の第２段スイッチと、該第１段ス イッチの各々は一義的なスイッチ番号を持ち、ｂ、ｃおよびＭは各々が１より大 きな正の整数とし、ｗは正の整数とし、Ｍ＋ｗは３より大であり、ｂは少くとも ｖに等しく、ｃは少くともＮ１に等しく（ｂ、ｃ、ｒ、Ｍ、ｗ）のブロック設計 に従って該入力チャネルの内の関連する予め定められたものを該第１段スイッチ の該入力に接続するための接続手段であって、該ブロック設計の要素は該第１段 スイッチの宛先であり、該ブロック設計の与えられた行は該与えられた行に関連 した与えられた入力チャネルに接続される該第１段スイッチのひとつを規定する ような接続手段とを 含むことを特徴とする交換ネットワーク。
9. ９．請求の範囲第８項に記載の交換ネットワークにおいて、ｎ２は高々「（Ｍ２ −１）／ｗ」＋１に等しいことを特徴とする交換ネットワーク。
10. １０．請求の範囲第８項に記載の交換ネットワークにおいて、該接続手段は該第 １段スイッチの該入力の各々を、該入力チャネルのｎ２個のグループの任意のも のについて、各々が該入力チャネルのｎ２個のグループの異るものに接続された ひとつの入力を各々が持つような第１段スイッチのｎ２個のグループが存在する ように、該入力チャネルの内の予め定められた関連するものに接続するようにな っていることを特徴とする交換ネットワーク。
11. １１．請求の範囲第８項に記載の交換ネットワークにおいて、Ｘを１より大きい 正の整数として該第１段スイッチの各々は少くともＸ個の出力を有し、該第１段 スイッチの出力を該第１段スイッチの入力に選択的に接続する手段を有し、該第 ２段スイッチの各々の複数個の入力は、複数のＸ入力のグループを有し、Ｘ入力 の各グループは該第１段スイッチの異るものに関連しており、Ｘ入力の各グルー プは関連する第１段スイッチの少くともＸ個の出力に接続されていることを特徴 とする交換ネットワーク。
12. １２．請求の範囲第１１項に記載の交換ネットワークにおいて、ｎ２は高々Ｘ［ 「（ＸＭ＋１）（Ｍ−１）／ｗ」＋１］に等しいことを特徴とする交換ネットワ ーク。
13. １３．請求の範囲第８項に記載の交換ネットワークにおいて、該第１段および該 第２段スイッチの各々はクロスポイントの矩形配列であることを特徴とする交換 ネットワーク。
14. １４．Ｎ１とＮ２を１より大きい正の整数であるとし、Ｎ１個の入力チャネルと Ｎ２個の出力チャネルを選択的に接続する交換ネットワークであって、 該交換ネットワークは ｎ２をＮ２より小さくＮ１より大きい正の整数とし、ｖを少くともｎ２に等しい 正の整数とし、Ｘとｒは各々が１より大きい正の整数であるとし、高々ｒ入力と 少くともＸ出力とを有し、該第１段スイッチの出力を該第１段スイッチの入力に 選択的に接続する手段を有するｖ個の第１段スイッチと、Ｘ入力の各グループは 該第１段スイッチの異るものに関連しており、Ｘ入力の各グループは該関連する 第１段スイッチの少くともＸ個の出力に接続されており、該複数個の第２段スイ ッチは該各々の第２段スイッチの出力を該各々の第２段スイッチの入力に選択的 に接続するための手段を含む各々が該出力チャネルの内の異るものに接続された ｎ２個の出力と、複数個のＸ入力のクループを形成する複数個の入力とを有する 複数個の第２段スイッチと、 該第１段スイッチの各々は一義的なスイッチ番号を有し、ｂ、ｃ、Ｍは各々１よ り大きい正の整数であり、ｂは少くともｖに等しく、ｃは少くともＮ１に等しく 、該ブロック設計の要素は該第１段スイッチのスイッチ番号であり、該ブロック 設計における与えられた行には、該与えられた行に関連した与えられた入力チャ ネルに接続された該第１段スイッチのひとつを規定するような（ｂ、ｃ．ｒ、Ｍ 、ｌ）のブロック設計に従う該入力チャネルの予め定められた関連するものと、 該第１段スイッチの該入力の各々を接続する接続手段と を含むことを特徴とする交換ネットワーク。
15. １５．Ｎ１個の入力チャネルをｎ２個の出力チャネルに選択的に接続する交換ネ ットワークであって、Ｎｌとｎ２は各々が１より大きい正の整数であり、ｎ２は 高々Ｎ１に等しく、該交換ネットワークは 各々が該Ｎ１個の入力チャネルの内の異るものに接続されたＮ１列と、ｖ行とを 含み、ｖは少くともｎ２に等しい正の整数とし、該部分コンセントレータは該列 を該行に選択的に接続する手段を含む部分コンセントレークと、 各々が該出力チャネルのひとつに接続されたｎ２個の出力と、各々が該行の異る ものに接続されたｖ個の入力を持ち、該スイッチは該出力を該入力に選択的に接 続する手段を含むスイッチを有し、 該ｃ列の各々は一義的な列番号を持ち、該ブロック設計の要素は該ｃ列の列番号 であり、ｂ、ｃ、ｒ、Ｍは各々が１より大きい正の整数であり、ｗは正の整数で あり、Ｍ＋ｗは３より大きく、ｂは少くともｖに等しく、ｃは少くともＮ１に等 しいようなｃ列とｂ行を持ち、該ｃ列の各々は（ｂ、ｃ、ｒ、Ｍ、ｗ）のブロッ ク設計の対応する行によって規定される該ｂ行のひとつに入射するような部分コ ンセントレータから該部分コンセントレータが誘導される ことを特徴とする交換ネットワーク。
16. １６．請求の範囲第１５項に記載の交換ネットワークにおいて、ｎ２は高々「（ Ｍ２−１）／ｗ」＋１に等しいことを特徴とする交換ネットワーク。
17. １７．Ｎ１とｎ２を各々が１より大きい正の整数とし、ｎ２は高々Ｎ１に等しい とし、Ｎ１個の入力チャネルｎ２個の出力チャネルを選択的に接続する交換ネッ トワークにおいて、各々が該Ｎ１個の入力チャネルの内の異るものに接続された Ｎ１列と、ｖ行とを有し、該部分コンセントレータの各々はｘを１より大きい正 の整数、ｖを少くともｎ２に等しい正の整数とし、該列を該行のひとつに選択的 に接続する手段を含む複数個のｘ個の部分コンセントレータと、 各々が該出力チャネルの内の異るものに接続されたｎ２個の出力と、各々が該ｘ 個の部分コンセントレータの該行の内の異るものに接続されたｘｖ個の入力を有 し、該スイッチは該出力を該入力に選択的に接続する手段を含むスイッチと、該 ｃ列は一義的なスイッチ番号を持ち、該ブロック設計の要素は該ｃ列の列番号で あり、ｂ、ｃ、ｒ、Ｍは各々が１より大きい正の整数であり、ｗは正の整数であ り、Ｍ＋ｗは３より大きく、ｂは少くともｖに等しく、ｃは少くともＮ１に等し く、該部分コンセントレータは、該ｃ列の各々は（ｂ、ｃ、ｒ、Ｍ、ｗ）のブロ ック設計の対応する行によって規定される該ｂ行のひとつに入射するようなｂ列 ｃ行を有する部分コンセントレータから該各々の部分コンセントレータが誘導さ れるようになっていることを特徴とする交換ネットワーク。
18. １８．請求の範囲第１７項に記載の交換ネットワークにおいて、ｎ２は高々［「 （ｘＭ＋１）（Ｍ−１）／ｗ」＋１］に等しいことを特徴とする交換ネットワー ク。
19. １９．Ｎ１とｎ２は１より大きい正の整数であり、ｎ２は高々Ｎ１に等しいよう なＮ１個の入力チャネルｎ２個の出力チャネルを選択的に接続する交換ネットワ ークにおいて、各々が該Ｎ１個の入力チャネルの内の異るものに接続されたＮ１ 列と、ｖ行を有し、該部分コンセントレータは該列のひとつを該行のひとつに選 択的に接続する手段を含み、ｘは１より大きい正の整数であり、ｖは少くともｎ ２に等しい正の整数であるような複数個のｘ個の部分コンセントレータと、各々 が該出力チャネルの内の異るものに接続されたｎ２出力と、各々が該ｘ個の部分 コンセントレータの該行の異るものに接続されたｘｖ入力とを有し、該スイッチ は該出力を該入力に対して選択的に接続する手段を有するスイッチとを含み、該 部分コンセントレータは、該ｃ列の各々は一義的な列番号を有し、議ブロック設 計の要素は該ｃ列の列番号であり、ｂ、ｃ、ｒ、Ｍは各々が１より大である正の 整数であり、ｂは少くともｖに等しく、ｃは少くともＮ１に等しく、該ｃ列の各 々が（ｂ、ｃ、ｒ、Ｍ、１）のブロック設計の対応する行によって定義される該 ｂ行の内のひとつに入射するような、ｃ列とｂ行を持つ部分コンセントレータか ら誘導される ことを特徴とする交換ネットワーク。
20. ２０．Ｎ１とＮ２を１より大きい正の整数とし、Ｎ１個の入力チャネルをＮ２個 の出力チャネルに対して選択的に接続するための交換ネットワークにおいて、 各々が該Ｎ１個のチャネルの内の異るものに接続されたＮ１列とｖ行とを有し、 該各々の部分コンセントレータは、ｎ２をＮ２より小さく高々Ｎ１に等しい正の 整数とし、ｖを少くともｎ２に等しい正の整数として、該列のひとつを該行のひ とつに選択的に接続するための手段を含む複数個の部分コンセントレータと、各 々が該部分コンセントレータの内の異るものに関連しており、各々が該出力チャ ネルの内の異るものに接続されたｎ２個の出力と、各々が関連する部分コンセン トレータのｖ行の内の異るものに接続されたｖ個の入力と、該各々のスイッチに 該各々のスイッチの出力と該各々のスイッチの出力を選択的に接続する手段を含 む複数個のスイッチを含み、 ｃ列の各々は一義的な列番号を持ち、該ブロック設計の要素は該ｃ列の列番号で あり、ｂ、ｃ、ｒ、Ｍは各々が１より大きい正の整数であり、ｗは正の整数であ り、Ｍ＋ｗは３より大きく、ｂは少くともｖに等しく、ｃは少くともＮ１に等し いような（ｂ、ｃ、ｒ、Ｍ、ｗ）のブロック設計の対応する行によって規定され る該ｂ行のひとつに対して該ｃ列の各々が入射するようなｃ列とｂ行を持つ部分 コンセントレータから各々の部分コンセントレータが誘導できる ことを特徴とする交換ネットワーク。
21. ２１．Ｎｌとｎ２は各々が１より大きい正の整数であり、ｎ２は高々Ｎ１に等し いようなＮ１個の入力チャネルをｎ２個の出力チャネルに選択的に接続する交換 ネットワークにおいて、ｖを少くともｎ２に等しい１より大きい正の整数とし、 ｒを１より大きい正の整数とし、各々が高々ｒ個の入力と少くともひとつの出力 を持ち、該各々の第１段スイッチの入力を該各々の第１段スイッチの少くとも１ 個の出力に選択的に接続する手段を各々が含むｖ個の第１段スイッチと、 該出力チャネルの内の異るものに各々が接続されたｎ２個の出力と、該第１段ス イッチの異るものに、各々が関連して、各々が該第１段スイッチの関連するもの の少くともひとつの出力に接続された複数の入力を有し、該第２段スイッチは該 ２段スイッチの該出力を該第２段スイッチの該入力に選択的に接続する手段を有 する第２段スイッチと、 該第１段スイッチは一義的なスイッチ番号をｄ０、ｄ１、−−−−ｄｖ−１を有 し、任意のｉ、０≦ｉ≦Ｍ−１に対して、該行列の第ｉ行の要素は次数Ｎ、深さ Ｍの直交配列の対応する要素にｉＮを加えることによって求められ、該配列はシ ンボル０、１、−−−−Ｎ−１を持ち、該行列の各列は高々ｗ個の入力チャネル に関連しており、該行列の与えられた列の要素ｅは該与えられた列に関連する入 力チャネルがスイッチ番号ｄ■を持つ該第１段スイッチの内のひとつに接続され ることを規定し、Ｍ、Ｎ、ｖは１より大きい正の整数であり、ｗＮ２は少くとも Ｎ１に等しく、ＭＮは少くともｖに等しく、ｗＮはｒに等しいような該第１段ス イッチの該入力の各々をＭＸＮ２の接続行列に従って該入力チャネルの予め定め られた関達するものに接続する接続手段とを含むことを特徴とする交換ネットワ ーク。
22. ２２．請求の範囲第２１項に記載の交換ネットワークにおいて、ｎ２は高々（Ｍ −１）（「Ｍ／ｗ」＋１）＋「Ｍ／ｗ」に等しいことを特徴とする交換ネットワ ーク。
23. ２３．請求の範囲第２１項に記載の交換ネットワークにおいて、該接続手段は該 入力チャネルのｎ２個の任意のグループに対して、各々が該入力チャネルのｎ２ 個のグループの異るものに接続されたような該第１段スイッチのｎ２個のグルー プが存在するように該接続手段が該第１段スイッチの該入力を該入力チャネルの 内の予め定められた関連するものに接続することを特徴とする交換ネットワーク 。
24. ２４．請求の範囲第２１項に記載の交換ネットワークにおいて、ｘを１より大き い正の整数として、該第１段スイッチの各々は少くともｘ個の出力を有し、該各 々の第１段スイッチの出力を該各々の第１段スイッチの入力に選択的に接続する 手段を含み、該第２段スイッチの該複数個の入力は複数個のＸ入力のグループを 形成し、各々のＸ個の入力のグループは該第１段スイッチの異るものに関連して 、ｘ入力の各グループは関連した第１段スイッチの少くともｘ個の出力に接続さ れていることを特徴とする交換ネットワーク。
25. ２５．請求の範囲第２４項に記載の交換ネットワークにおいて、Ａ＝ｗ（Ｍ−１ ）〔「ＸＭ／ｗ」＋１）２Ｂ＝ｗ（「ｘＭ／ｗ」＋１）−ｘとしてｎ２は高々ｘ 「Ａ／Ｂ＋１」に等しいことを特徴とする交換ネットワーク。
26. ２６．請求の範囲第２１項に記載の交換ネットワークにおいて、該第１段スイッ チと該第２段スイッチの各々はクロスポイントの矩形配列を形成することを特徴 とする交換ネットワーク。
27. ２７．Ｎ１とｎ２を各々１より大きい正の整数、ｎ２を高々Ｎ１に等しい数とし 、Ｎ１個の入力チャネルをｎ２個の出力チャネルに選択的に接続する交換ネット ワークにおいて、該交換ネットワークは、 ｖを少くともｎ２に等しい正の整数、Ｘとｒを各々１より大きい正の整数とし、 高々ｒ個の入力と少くともＸ個の出力を有し、各々該第１段スイッチの出力を該 第１段スイッチの入力に選択的に接続する手段を含むｖ個の第１段スイッチと、 各々が該出力チャネルの内の異るものに接続されたｎ２個の出力を有し、各々の ｘ個の入力が該第１段スイッチの内の異るものに関連し、ｘ入力の各グループが 関連した第１段スイッチの少くともｘ出力に接続されている、複数個のＸ入力の グループを形成する複数個の入力を、該第２段スイッチは該第２段スイッチの該 出力を該第２段スイッチの該入力に選択的に接続する手段を含む第２段スイッチ と、 該第１段スイッチは一義的なスイッチ番号ｄ０、ｄ１、−−−−ｄｖ−１を持ち 、任意の整数ｉ、０≦ｉ≦Ｍ−１に対して、該行列の第ｉ行の要素はＮ次で深さ Ｍの直交配列の対応する要素にｉＮを加算することによって得られ、該配列はシ ンボル０、１、−−−−Ｎ−１を有し、該行列の各列は該入力チャネルのひとつ に関連しており、該行列の与えられた列の各要素は該与えられた列に関連した入 力チャネルがスイッチ番号ｄ■を持つ該第１段スイッチのひとつに接続されるこ とを規定し、ＭとＮは各々が１より大きい正の整数であり、Ｎ２は少くともＮ１ に等しく、ＭＮは少くともｖに等しく、Ｎはｒに等しいようなＭＸＮ２の接続行 列に従って、該第１段スイッチの該入力を該入力チャネルの内の予め定められた 関連するものに接続するための接続手段とを含むことを特徴とする交換ネットワ ーク。
28. ２８．Ｎ１とＮ２を各々が１より大きい正の整数とし、Ｎ１個の入力チャネルを Ｎ２個の出力チャネルに選択的に接続する交換ネットワークにおいて、 ｎ２をＮ２より小さく、高々Ｎ１に等しい正の整数、ｖを少くともｎ２に等しい 正の整数、ｒを１より大きい正の整数とし、高々ｒ個の入力と、複数個の出力を 有し、該第１段スイッチの出力を該第２段スイッチの入力に対して選択的に接続 するための手段を各々が有するｖ個の第１段スイッチと、各々が該出力チャネル の異るものに接続されたｎ２個の出力と各々が複数個の該第１段スイッチの異る ものに関連しており、各々が該第１段スイッチの関連するものの出力に接続され た複数個の入力を有し、該複数個の第２段スイッチの各々が該第２段スイッチの 各々の出力を該第２段スイッチの各々の入力に選択的に接線する手段を含む複数 個の第２段スイッチと、該第１段スイッチは一義的なスイッチ番号ｄ０、ｄ１、 −−−−−−ｄｖ−１を持ち、任意の整数ｉ、０≦ｉ≦Ｍ−１に対して、該行列 の第ｉ行は次数Ｎ、深さＭの直交配列の対応する要素にｉＮを加算することによ って得られ、該配列はシンボル０、１、−−−−Ｎ−１を持ち、該行列の各々の 列は該入力チャネルの内の高々ｗ個に関連しており、与えられた列の各要素ｅは 該与えられた列に関連した入力チャネルがスイッチ番号ｄ■を持つ該第１段スイ ッチに接続されていることを示し、Ｍ、Ｎ、ｗは各々１より大きい正の整数であ り、ｗＮ２は少くともＮ１に等しく、ＭＮは少くともｖに等しく、ｗＮはｒに等 しいようなＭＸＮ２の接続行列に従って該第１段スイッチの入力を該入力チャネ ルの内の予め定められた関連するものに接続する接続手段とを含むことを特徴と する交換ネットワーク。
29. ２９．請求の範囲第２８項に記載の交換ネットワークにおいて、ｎ２は高々（Ｍ −１）（「Ｍ／ｗ」＋１）＋「Ｍ／ｗ」に等しいことを特徴とする交換ネットワ ーク。
30. ３０．請求の範囲第２８項に記載の交換ネットワークにおいて、該接続手段は該 第１段スイッチの該入力の各々を、該入力チャネルのｎ２個のグループの任意の ものについて、各々が該入力チャネルのｎ２個のグループの異るものに接続され たひとつの入力を持つｎ２個の第１段スイッチが存在するように、該入力チャネ ルの内の予め定められたものに接続することを特徴とする交換ネットワーク。
31. ３１．請求の範囲第２８項に記載の交換ネットワークにおいて、ｘを１より大き い正の整数として、該第１段スイッチの各々は少くともｘ個の出力を有し、該各 々の第１段スイッチの出力を該各々の第１段スイッチの入力に選択的に接続する 手段を含み、該各々の第２段スイッチの該複数個の入力はＸ入力の複数個のグル ープを含み、ｘ入力の各グループは該第１段スイッチの異るものに関連しており 、Ｘ入力の各グループは関連する第１段スイッチの少くともｘ個の出力に接続さ れていることを特徴とする交換ネットワーク。
32. ３２．請求の範囲第３１項に記載の交換ネットワークにおいて、ｎ２は高々ｘ「 Ａ／Ｂ＋１」に等しく、Ａ＝ｗ（Ｍ−１）（ｘＭ／ｗ」＋１）２Ｂ＝ｗ（「ｘＭ ／ｗ」＋１〕−ｘであることを特徴とする交換ネットワーク。
33. ３３．請求の範囲第２８項に記載の交換ネットワークにおいて、該第１段スイッ チと該第２段スイッチの各々はクロスポイントの矩形のを列を含むことを特徴と する交換ネットワーク。
34. ３４．ＮｌとＮ２を各々が１より大きい正の整数とし、Ｎ１個の入力チャネルと Ｎ２個の出力チャネルを選択的に接続するための交換ネットワークにおいて、 ｎ２をＮ２より小さく、高々Ｎ１に等しい正の整数とし、ｖを少くともｎ２に等 しい正の整数とし、ｘとｒを１より大きい正の整数とし、高々ｒ個の入力と少く ともＸ個の出力を有し、各々が該第１段スイッチの出力を該第１段スイッチの入 力に選択的に接続するための手段を含むｖ個の第１段スイッチと、各々が該出力 チャネルの内の異るものに接続されたｎ２個の出力と、複数のｘ入力のグループ を形成する複数個の入力を持ち、Ｘ入力の各グループは該第１段スイッチの内の 異るものに関連しており、ｘ入力の各グループは関連する第１段スイッチの少く ともｘ出力に接続されており、該複数個の第２段スイッチの各々は該各々の第２ 段スイッチの出力を該各々の第２段スイッチの入力に選択的に接続する手段を含 む複数の第２段スイッチと、該第１段スイッチは一義的なスイッチ番号ｄ０、ｄ １、−−−−−−ｄｖ−１を有し、任意の整数ｉ、０≦ｉ≦Ｍ−１について、該 行列の行ｉの要素は次数Ｎ、深さＭの直交配列の対応する要素にｉＮを加算する ことによって得られ、該配列はシンボル０．１、−−−−Ｎ−１を持ち、該行列 の各列は該入力チャネルのひとつに関連しており、該行列の与えられた列の各要 素ｅは該与えられた列に関連した入力チャネルがスイッチ番号ｄ■を持つ該第１ 段スイッチの内のひとつに接続されることを規定し、ＭとＮは各々１より大きい 正の整数であり、Ｎ２は少くともＮｌに等しく、ＭＮは少くともｖに等しく、Ｎ はｒに等しいようなＭＸＮ２の接続行列に従って該第１段スイッチの該入力の各 々を該入力チャネルの内の予め定められたものに接続する接続手段を有すること を特徴とする交換ネットワーク。
35. ３５．Ｎ１とｎ２を１より大きい正の整数、ｎ２を高々Ｎ１に等しい数として、 Ｎ１個の入力チャネルをｎ２個の出力チャネルに選択的に接続する交換ネットワ ークにおいて、該交換ネットワークはｖを少くともｎ２に等しい正の整数とし、 各々が該Ｎ１個の入力チャネルの異るものに接続されたＮ１列とｖ行とを持ち、 該列のひとつを該行のひとつに選択的に接続する部分コンセントレータと、 各々が該出力チャネルの内の異るものに接続されたｎ２個の出力と、各々が該行 のひとつに接続されたｖ入力を持ち、該出力を該入力に選択的に接続する手段を 含むスイッチとを含み、任意の整数ｉ、０≦ｉ≦Ｎ−１、任意の整数ｊ、０≦ｊ ≦Ｍ−１に対して該各々のコピーの集合ｊの第ｉ行は、その配列の行ｊに行ｉを 規定するシンボルを持つような次数Ｎ、深さＭの直交配列の列に対応する該各々 のコピー列に入射するような該コピーの各々はＮ２列を持ち、Ｎ行の集合をＭ個 持つような部分コンセントレータのｗ個のコピーを行ごとに併合することによっ て該部分コンセントレータが誘導できるようになっており、Ｍ、Ｎ、ｗは各々が １より大きい正の整数で、ｗＮ２は少くともＮ，に等しく、ＭＮは少くともｖに 等しいようになったことを特徴とする交換ネットワーク。
36. ３６．請求の範囲第３５項に記載の交換ネットワークにおいて、ｎ２は高々（Ｍ −１）（Ｍ／ｗ」＋１）＋「Ｍ／ｗ」に等しいことを特徴とする交換ネットワー ク。
37. ３７．Ｎ１とｎ２を各々が１より大きい正の整数、ｎ２を高々Ｎ１に等しい数と し、Ｎ１個の入力チャネルをｎ２個の出力チャネルに選択的に接続する交換ネッ トワークにおいて、ｘを１より大きい正の整数、ｖを少くともｎ２に等しい正の 整数とし、各々が該Ｎ１個の入力チャネルの内の異るものに接続されたＮ１列と 、各々が該部分コンセントレータに接続されたｖ行を持ち、該列のひとつを該行 のひとつに選択的に接続する手段を含むｘ個の部分コンセントレータと、 各々が該出力チャネルの内の異るものに接続されたｎ２個の出力と、各々が該ｘ 個の部分コンセントレータの該行の内の異るものに接続されたｘｖ個の入力を有 し、該スイッチは該出力を該入力に選択的に接続する手段を含むスイッチとを含 み、該各々の部分コンセントレータは部分コンセントレータのｗ個のコピーの行 ごとの併合から誘導できるようになっており、該コピーの各々はＮ２列とＮ行の Ｍ個の集合を持ち、任意の整数ｉ、０≦ｉ≦Ｎ−１、任意の整数ｊ、０≦ｊ≦Ｍ −１について、該コピーの集合ｊの行ｉは、該配列の行ｊが行ｉを規定するシン ボルを含む次数Ｎ、深さＭの直交配列の列に対応する該各々のコピーの列に入射 するようになっており、Ｍ、Ｎ、ｗは各々が１より大きい正の整数、ｗＮ２は少 くともＮ１に等しい数、ＭＮは少くともｖに等しい数となっているような交換ネ ットワーク。
38. ３８．請求の範囲第３７項に記載の交換ネットワークにおいて、ｎ２は高々ｘ「 Ａ／Ｂ＋１」に等しく、Ａ＝ｗ（Ｍ−１）（「ｘＭ／ｗ」＋１）２Ｂ＝ｗ（「ｘ Ｍ／ｗ」＋１）−ｘであることを特徴とする交換ネットワーク。
39. ３９．Ｎ１とｎ２は各々が１より大きい正の整数、ｎ２は少くともＮ１に等しい 数として、Ｎ１個の入力チャネルをｎ２個の出力チャネルに選択的に接続する交 換ネットワークにおいて、ｘを１より大きい正の整数、ｖを少くともｎ２に等し い正の整数とし、各部分コンセントレータが該列のひとつを該行のひとつに選択 的に接続する手段を有する、各々が該Ｎ１個の入力チャネルの内の異るものに接 続されたＮ１個の列と、ｖ行とを有する複数個のｘ個の部分コンセントレータと 、各々が該出力チャネルの内の異るものに接続されたｎ２個の出力と、各々が該 ｘ個の部分コンセントレータの該行の内の異るものに接続されたｘｖ個の入力を 有し、該スイッチは該出力を該入力に接続するスイッチとを含み、 各部分コンセントレータはＮ２列とＮ行のＭ個の集合を持ち、任意の整数ｉ、０ ≦ｉ≦Ｎ−１、任意の整数ｊ、０≦ｊ≦Ｍ−１について、各部分コンセントレー タの集合ｊの行ｉは、該配列の行ｊに行ｉを規定するシンボルを含む次数Ｎ、深 さＭの直交配列の列に対応する該各々の部分コンセントレータの列に入射するよ うになっており、ＭとＮは各々が１より大きい正の整数であり、Ｎ２は少くとも Ｎ１に等しく、ＭＮは少くともｖに等しいようになっていることを特徴とする交 換ネットワーク。
40. ４０．Ｎ１とＮ２を各々が１より大きい正の整数とし、Ｎ１個の入力チャネルを Ｎ２個の出力チャネルに選択的に接続する交換ネットワークにおいて、 ｎ２をＮ２より小さく、高々Ｎ１に等しい正の整数とし、ｖを少くともｎ２に等 しい正の整数とし、各々が該Ｎ１個の入力チャネルの内の異るものに接続された Ｎ１列とｖ行とを含み、該各々の部分コンセントレータは該列を該行のひとつに 選択的に接続する手段を有する複数個の部分コンセントレータと、各々が該部分 コンセントレータの内の異るものに関連しており、各々が該出力チャネルの内の 異るものに接続されたｎ２個の出力と各々が関連する部分コンセントレータのｖ 行の内の異るものに接続されたｖ個の入力を持ち、各スイッチが該各々のスイッ チの該出力を該各々のスイッチの該入力に選択的に接続する手段を含む複数個の スイッチとを含み、 該各々の部分コンセントレータは部分コンセントレータのｗ個のコピーを行ごと に併合したものから誘導でき、該コピーの各々はＮ２列とＮ行の集合Ｍ個を含み 、任意の整数ｉ、０≦ｉ≦Ｎ−１、任意の整数ｊ、０≦ｊ≦Ｍ−１について該各 々のコピーの集合ｊの行ｉは、その配列の行ｊが行ｉを規定しているような次数 Ｎ、深さＭの直交配列の列に対応する該各々のコピーの列に入射するようになっ ており、Ｍ、Ｎ、ｗは各々が１より大きい正の整数であり、ｗＮ２は少くともＮ １に等しく、ＭＮは少くともｖに等しいことを特徴とする交換ネットワーク。
41. ４１．Ｎ１とｎ２を各々１より大きい正の整数、ｎ２を少くともＮｌに等しい数 とし、Ｎ１個の入力チャネルをｎ２個の出力チャネルに選択的に接続するための 交換ネットワークにおいて、ｖを少くともｎ２に等しい正の整数、ｒを１より大 きい正の整数とし、各々が高々ｒ個の入力と少くとも１個の出力とを有し、各々 が該第１段スイッチの入力の内の任意のものを該各々の第１段スイッチの少くと もひとつの出力に選択的に接続する手段を有するｖ個の第１段スイッチと、 各々が該出力チャネルの内の異るものに接続されたｎ２個の出力と、各々が該第 １段スイッチの内の異るものに関連しており、関連した第１段スイッチの少くと も、ひとつの出力に接続され、該第２段スイッチの該出力を該第２段スイッチの 該入力に選択的に接続するための手段を含む第２段スイッチと、該入力チャネル の各々は一義的なチャネル番号を有し、該行列は各行がｕ行を有するＭ個の集合 Ｓ０、Ｓ１−−−−Ｓｍ−１を含むＭｕ行を有し、集合Ｓ０では該入力チャネル の各々のチャネル番号は正確に１回発生し、任意の整数ｉ、１≦ｉ≦Ｍ−１、任 意の整数ｊ、０≦ｊ≦ｒ−１、Ｍ−１（ｕ、ｒ、ｗ）の差集合Ｄｊ＝｛ａｉ０、 −−−−ａｉｒ−１｝について、集合Ｓｉの列ｊは集合Ｓ０の列ｊをａｉｊ位置 だけ回転することによって得られ、該行列の与えられた行では該与えられた行に 関連した与えられた第１段スイッチの入力に接続された該入力チャネルのひとつ を定義するチャネル番号を持ち、ｗは正の整数であり、ＭとＵは各々が１より大 きい整数であり、ｕｒは少くともＮ１に等しく、Ｍｕは少くともｖに等しいよう な、Ｍｕｘｒの接線行列に従って該入力チャネルの内の関連した予め定められた ものを該複数個の第１段スイッチの該入力の各々に接続する接続手段と を含むことを特徴とする交換ネットワーク。
42. ４２．請求の範囲第４１項に記載の交換ネットワークにおいて、２より大きい正 の整数であり、Ｄ１以外の該差集合の各々はＤ１の要素をｕに対して素であるモ ジュロｕの剰余によってモジュロｕで乗ずることによって得られることを特徴と する交換ネットワーク。
43. ４３．請求の範囲第４１項に記載の交換ネットワークにおいて、ｎ２は高々「Ｍ ■−Ｍ２）／ｗ」＋Ｍ＋１に等しいことを特徴とする交換ネットワーク。
44. ４４．請求の範囲第４１項に記載の交換ネットワークにおいて、該接続手段は、 該入力チャネルの任意のｎ２個のグループに対して、各々が該入力チャネルのｎ ２個のグループの内の異るものに接続された１個の入力を有する該第１段スイッ チのｎ２個のグループが存在するように該第１段スイッチの該入力の各々を該入 力チャネルの内の関連した予め定められたものに接続するようになっていること を特徴とする交換ネットワーク。
45. ４５．請求の範囲第４１項に記載の交換ネットワークにおいて、ｘを１より大き い正の整数とし、該第１段スイッチの各々は少くともｘ個の出力を有し、該各々 の第１段スイッチの出力を該各々の第１段スイッチの入力に選択的に接続する手 段を有し、該第２段スイッチの該複数個の入力は、ｘ入力の複数個のグループを 形成し、ｘ入力の各グループは該第１段スイッチの異るものに関連しており、ｘ 入力の各グループは、関連する第１段スイッチの少くともｘ個の出力に接続され ていることを特徴とする交換ネットワーク。
46. ４６．請求の範囲第４５項に記載の交換ネットワークにおいて、ｎ２は高々「（ ｘ３Ｍ３−ｘ２Ｍ２）／ｗ」＋ｘＭ＋１に等しいことを特徴とする交換ネットワ ーク。
47. ４７．請求の範囲第４１項に記載の交換ネットワークにおいて、該第１段スイッ チと該第２段スイッチの各々はクロスポイントの矩形の配列を含むことを特徴と する交換ネットワーク。
48. ４８．Ｎ１とＮ２を各々が１より大きい正の整数として、Ｎ１個の入力チャネル をＮ２個の出力チャネルに接続する交換ネットワークにおいて、該交換ネットワ ークは、ｎ２をＮ２より小さい高々Ｎ１に等しい正の整数、ｖを少くともｎ２に 等しい正の整数、ｒを１より大きい正の整数とし、高々ｒ個の入力と複数個の出 力とを有し、各々が該第１段スイッチの出力を該第１段スイッチの入力に選択的 に接続する手段を有するｖ個の第１段スイッチと、 各々該出力チャネルの異るものに接続されたｎ２個の出力と、各々が複数個の該 第１段スイッチの内の異るものに関連しており、各々が関連した第１段スイッチ の出力の内のひとつに接続された複数個の入力を有し、該複数個の第２段スイッ チの各々は該第２段スイッチの出力を該第２段スイッチの入力に選択的に接続す る手段を含む複数個の第２段スイッチと、該入力チャネルの各々は一義的なチャ ネル番号を持ち、該行列はＳ０、Ｓ１−−−−Ｓｍ−１を形成する各々がｕ行を 持つＭ個の集合から成るＭｕ行を持ち、該入力チャネルの各々のチャネル番号は 集合Ｓ０では正確に１回現われ、任意の整数ｉ、１≦ｉ≦Ｍ−１、任意の整教ｊ 、０≦ｊ≦ｒ−１およびＭ−１（ｕ、ｒ、ｗ）の差集合Ｄｊ＝｛ａｉ０、−−− −ａｉｒ−１｝について、集合Ｓ■の列ｊは集合Ｓ０の列ｊをａｉｊ位置だけ回 転することによって得られ、該行列の与えられた行に生ずるチャネル番号は該与 えられた行に関連した与えられた第１段スイッチの入力に接線された該入力チャ ネルのひとつを規定し、ｗは正の整数を表わし、Ｍとｕは各々が１より大きい正 の整数を表わし、ｕｒは少くともＮｌに等しく、Ｍｕは少くともｖに等しいよう なＭｕ×ｒの接続行列に従って該複数個の第１段スイッチの該入力の各々を該入 力チャネルの関連した予め定められたものに接続する接続手段とを含むことを特 徴とする交換ネットワーク。
49. ４９．請求の範囲第４８項に記載の交換ネットワークにおいて、Ｍは２より大き い正の整数であり、Ｄ１以外の該差集合はＤ１の要素をｕに対して素であるモジ ュロもの剰余でモジュロｕの乗算をすることによって誘導されることを特徴とす る交換ネットワーク。
50. ５０．請求の範囲第４８項に記載の交換ネットワークにおいて、ｎ２は高々（Ｍ ３−Ｍ２）／ｗ」＋Ｍ＋１に等しいことを特徴とする交換ネットワーク。
51. ５１．請求の範囲第４８項に記載の交換ネットワークにおいて、該入力チャネル の任意のｎ２個のグループに対して、各々のひとつの入力が該入力チャネルのｎ ２個のグループの異るものに接続されているような該第１段スイッチのｎ２個の グループが存在するように接続手段が該第１段スイッチの該入力の各々を該入力 チャネルの関連した予め定められたものに接続するようになっていることを特徴 とする交換ネットワーク。
52. ５２．請求の範囲第４８項に記載の交換ネットワークにおいて、ｘを正の整数と して該第１段スイッチは少くともｘ個の出力を有し、該第１段スイッチの各々の 出力を該第１段スイッチの各々の入力に選択的に接続する手段を含み、該第２段 スイッチの該複数個の入力は、ｘ入力の複数個のグループを形成し、ｘ入力の各 グループは該第１段スイッチの内の異るものに関連しており、ｘ入力の各グルー プは関連する第１段スイッチの少くともｘ個の出力に接続されていることを特徴 とする交換ネットワーク。
53. ５３．請求の範囲第５０項に記載の交換ネットワークにおいて、ｎ２は高々「ｘ ３Ｍ３−ｘ２Ｍ２）／ｗ」＋ｘＭ＋１に等しいことを特徴とする交換ネットワー ク。
54. ５４．請求の範囲第４８項に記載の交換ネットワークにおいて、該第１段および 該第２段スイッチの各々はクロスポイントの矩形の配列を形成することを特徴と する交換ネットワーク。
55. ５５．Ｎ１とｎ２を１より大きい正の整数、ｎ２を高々Ｎ１に等しいものとし、 Ｎ１個の入力チャネルとｎ２個の出力チャネルを選択的に接続する交換ネットワ ークにおいて、ｖを少くともｎ２に等しい正の整数として、各々が該Ｎ１個の入 力チャネルの内の異るものに接続されたＮ１列とｖ行とを有し、該列を該行のひ とつに選択的に接続するための手段を含む部分コンセントレータと、 各々が該出力チャネルの異るものに接続されたｎ２個の出力と、各々が該行の異 るものに接続されたｖ個の入力とを有し、該出力と該入力を選択的に接続する手 段を有するスイッチとを含み、 該部分コンセントレータはｕｒ列とＭｕ行を持つ部分コンセントレータから誘導 され、該Ｍｕ行の各々はＭｕｘｒの接続行列の対応する行によって規定される該 ｕｒ列のひとつに入射し、該ｕｒ列の各々は一義的な列番号を有し、該行列はＭ 個の集合Ｓ０、Ｓ１、−−−−Ｓｍ−１を含むＭｕ行を持ち、該ｕｒ列の各々の 列番号は集合Ｓ０で正確に１回だけ生じ、任意の整数ｉ、１≦ｉ≦Ｍ−１、任意 の整数ｊ、０≦ｊ≦ｒ−１、Ｍ−１（ｕ、ｒ、ｗ）の差集合Ｄｉ＝｛ａｉ０、− −−−ａｉｒ−１｝について、集合Ｓｊの列ｊは集合Ｓ０の列ｊをａｉｊ位置だ け回転することによって得られ、ｗは正の整数であり、Ｍ、ｒ、ｕは各々が１よ り大きい正の整数であり、ｕｒは少くともＮ１に等しく、Ｍｕは少くともｖに等 しいことを特徴とする交換ネットワーク。
56. ５６．請求の範囲第５５項に記載の交換ネットワークにおいて、Ｍは２より大き い正の整数であり、Ｄ１以外の該差集合はｕに対して素であるモジュロｕの剰余 をＤ１の要素にモジュロｕで乗ずることによって誘導されることを特徴とする交 換ネットワーク。
57. ５７．請求の範囲第５５項に記載の交換ネットワークにおいて、ｎ２は高々（Ｍ ３−Ｍ２）／ｗ」＋Ｍ＋１に等しいことを特徴とする交換ネットワーク。
58. ５８．Ｎ１個の入力チャネルをｎ２個の出力チャネルに選択的に接続する交換ネ ットワークにおいて、Ｎ１とｎ２は各々が１より大きい正の整数であり、ｎ２は 高々Ｎ１に等しく、該交換ネットワークは、 ｘを１より大きい正の整数、ｖを少くともｎ２に等しい正の整数として、各々が 該Ｎ１個の入力チャネルの内の異るものに接続されたＮ１個の列と、ｖ行とを含 み、該各々の部分コンセントレータは該列のひとつを該行のひとつに選択的に接 続する手段を含むｘ個の部分コンセントレータと、 各々が該出力チャネルの内の異るものに接続されたｎ２個の出力と、各々が該ｘ 個の部分コンセントレータの該行の内の異るものに接続されたｘｖ個の入力とを 有し、該出力を該入力に選択的に接線する手段を含むスイッチとを含み該各々の 部分コンセントレータはＭｕ行の各々がＭｕｘｒの接続行列の対応する行によっ て規定される該ｕｒ列のひとつに入射するようなｕｒ列とＭｕ行を持つ部分コン セントレータから誘導でき、該ｕｒ列の各々は一義的な列番号を持ち、該行列は 各々がｕ行を持つＭ個の集合Ｓ０、Ｓ１、−−−−Ｓｍ−１を含むＭｕ行を持ち 、該ｕｒ列の各々の列番号は集合Ｓ０中で正確に１回だけ生じ、任意の整数ｉ、 １≦ｉ≦Ｍ−１、任意の整数ｊ、０≦ｊ≦ｒ−１、Ｍ−１（ｕ、ｒ、ｗ）の差集 合Ｄｊ＝｛ａｉ０、−−−−ａｉｒ−１｝について、集合Ｓｉの列ｊは集合Ｓ０ の列ｊをａｉｊ位置だけ回転することによって得られ、ｗは正の整数であり、Ｍ 、ｒ、ｕは各々が１より大きい正の整数であり、ｕｒは少くともＮ１に等しく、 Ｍｕは少くともｖに等しいことを特徴とする交換ネットワーク。
59. ５９．請求の範囲第５８項に記載の交換ネットワークについて、ｎ２は高々「（ ｘ３Ｍ３−ｘ２Ｍ２）／ｗ」＋ｘＭ＋１に等しいことを特徴とする交換ネットワ ーク。
60. ６０．Ｎ１とＮ２を１より大きい正の整数として、Ｎ１個の入力チャネルをＮ２ 個の出力チャネルに選択的に接続する交換ネットワークにおいて、該交換ネット ワークは、各々がＮ１個の入力チャネルの異るものに接続されたＮ１個の列と、 ｖ行とを有し、該列のひとつを該行のひとつに選択的に接続する手段を含み、ｎ ２はＮ２より小さく高々Ｎ１に等しい正の整数であり、ｖは少くともｎ２に等し いような複数個の部分コンセントレータと、 各々が該部分コンセントレータの内の異るものに関連しており、各々が該出力チ ャネルの内の異るものに接続されたｎ２個の出力と、各々が関連した部分コンセ ントレータのｖ行の内の異るものに接続されたｖ個の入力を有し、各々が該各々 のスイッチの出力を該各々のスイッチの入力に選択的に接続する手段を有する複 数個のスイッチを含み、 該部分コンセントレータの各々はｕｒ列とＭｕ行を持つ該Ｍｕ行の各々はＭｕｘ ｒの接続行列の対応する行によって規定される該ｕｒ列のひとつに入射するよう な部分コンセントレータから誘導され、該ｕｒ列の各々は一義的な列番号を有し 、該行列は各々がｕ行を持つＭ個の集合Ｓ０、Ｓ１、−−−−Ｓｍ−１を含むＭ ｕ行を持ち、該ｕｒ列の各々の列番号は集台Ｓ０中で正確に１回だけ生じ、任意 の整数ｉ、１≦ｉ≦Ｍ−１、任意の整数ｊ、０≦ｊ≦ｒ−１、Ｍ−１（ｕ、ｒ、 ｗ）の差集合Ｄ１＝｛ａｉ０、−−−−ａｉｒ−１｝について、集合Ｓｉの列ｊ は集合Ｓ０の列ｊをａｉｊ位置だけ回転することによって得られるようになって おり、ｗは正の整教であり、Ｍ、ｒ、ｕは各々が１より大きい正の整数であり、 ｕｒは少くともＮ１に等しく、Ｍｕは少くともｖに等しいようになっている ことを特徴とする交換ネットワーク。