JPH0728238B2 - 多重化自動切替装置 - Google Patents

Description

【発明の詳細な説明】 （発明の属する技術分野） 本発明はｋ−out−of−ｎ構成を有する装置において、
その装置中に生じた故障を自動的に切替えて救済するこ
とのできる多重化自動切替装置に関するものである。

（従来の技術） 第１図は従来の２−out−of−４構成切替装置の構成を
示すものであり、１は同一構成のユニットX₀〜X₃からな
るブロック、２は同一構成のユニットY₀〜Y₃からなるブ
ロックである。

本切替装置はこれらの２つのブロックで各々正常な２個
のユニットを選択し、１対１に接続する機能を有し、１
対１に接続されたブロック１のユニット１個とブロック
２のユニット１個をユニットペアと称す。

このユニットペアは２個のユニットが共に正常であると
き、正常に動作する。３はブロック１のユニットとブロ
ック２のユニットを接続する切替回路であり、MU₀,MU₁,
DU₀,DU₁からなる。MU₀,MU₁はブロック１の３個のユニッ
トのデータ出力から１個を選択するマルチプレクサユニ
ットであり、DU₀,DU₁はマルチプレクサユニットの出力
をブロック２の３個のユニットのいずれかに選択して加
えるデマルチプレクサユニットである。Ｑは切替制御信
号であり、マルチプレクサユニットとデマルチプレクサ
ユニットの入出力の選択を決定する信号である。

ブロック１とブロック２において、各々２個以上のユニ
ットが正常であれば、切替制御信号によりユニット間の
接続を制御することにより、正常なユニットペアが少な
くとも２組得られる。しかし、本切替装置には切替回路
の故障を救済できない欠点がある。

この欠点を除くために、切替回路を多重化した切替装置
が、特願昭58−232683号に提案された多重化切替装置で
ある。

第２図は２−out−of−４構成に対する多重化切替装置
の構成を示すものである。４は切替回路であり、同一構
成の切替回路ユニットS₀〜S₃からなる。

切替回路ユニットは、ブロック１の３個のユニットのデ
ータ出力から１個を選択して、ブロック２のユニットに
加える回路である。Ｐは切替制御信号であり、切替回路
ユニットの入力を選択する信号である。第１図の切替装
置と同様に、本多重化切替装置はブロック１とブロック
２において、各々２個以上のユニットが正常であれば、
正常なユニットペアを２組以上生成できる。

例えば、第３図に示すように、ブロック１のX₀,X₃とブ
ロック２のY₁,Y₂が故障した例について考えよう。図
中、正常なユニットを０、故障したユニットをＸで表わ
す。

この例では、（x₁,Y₃）と（x₂,Y₀）なる２組の正常なペ
アを形成する。ところで、切替回路ユニットの故障は、
接続するブロック２のユニットの故障と等価であり、救
済可能である。例えば、S₁とS₂が故障した場合にはY₁と
Y₂の故障と等価であり、本例のユニット間接続により救
済できる。

このように、本多重化切替装置は故障救済能力が高い。
しかし、ユニットの故障状況に応じて、使用者がユニッ
ト間接続を決定するため、切替操作が複雑であり、切替
時間が大きい欠点があった。

（発明の目的） 本発明の目的は、ユニットと切替回路の故障を救済でき
る多重化切替装置に対して、ユニット間接続を使用者が
求める欠点を解決し、自動的にユニット間接続を決定す
る機能を付与することにある。

（発明の構成） 本発明の、多重化自動切替装置は、同一構成のｎ（ｎ≧
２）個のユニットX₀,X₁,…,Xn_-1からなるブロック１と
同一構成のｎ個のユニットY₀,Y₁,…,Yn_-1からなるブロ
ック２についてそれぞれ正常なｋ（１≦ｋ＜ｎ）個のユ
ニットを自動的に１対１接続するために次のような検査
回路、切替回路および切替制御回路を備えたことを最も
主要な特徴とする。

各ユニットに対して検査回路を設け、その検査出力より
ユニットの正常性を判定できるようにする。切替回路を
ｎ個の切替回路ユニットSU₀,SU₁,…,SUn_-1により構成す
る。

なお、切替回路ユニットSUiはブロック１のユニットの
データ出力と検査出力を共に切替えることにより、選択
したブロック１のユニットの正常性を表示できるように
する。

即ち、切替回路ユニットSUiはユニットXiのデータ出力D
XiとCXiをペアとして、（ｎ−ｋ＋１）組のペア（DXi,C
Xi），（DXi₊₁,CXi₊₁），…，（DXi₊j,CXi₊j），…，
（DXi₊n_-k,CXi₊n_-k）から選択した１組のペア（DXSi,CX
Si）を出力する。（ここで、ｉ＝0,1,…,n−１。ｊ＝0,
1,…,n−ｋ。ｉ＋ｊはmod nの和。） また、切替制御回路はCXS₀,CXS₁,…,CXSn_-1と、ユニッ
トY₀,Y₁,…,Yn_-1の検査出力から、正常なユニットペア
がｋ組以上生成されたことを判定し、その結果により切
替回路ユニットによる切替を制御する。

従来の技術では、個々のユニットをテストした結果に基
づいて使用者がユニット間接続を決定した。これに対
し、多重化切替装置はユニット間接続を自動的に求める
ことができる。

（実施例の説明） ここで提案する多重化自動切替装置の構成を２−out−o
f−４なる具体例に基づいて説明する。一般的なｋ−out
−of−ｎ切替構成の切替装置については、以下の説明か
ら容易に拡張できる。

第４図は２−out−of−４切替構成の多重化自動切替装
置の説明図である。X₀〜X₃はブロック１のユニット、Y₀
〜Y₃はブロック２のユニットであり、切替対象となる回
路である。

DX₀〜DX₃は各々X₀〜X₃の出力、DY₀〜DY₃は各々Y₀〜Y₃の
出力である。CKX₀〜CKX₃はX₀〜X₃に設けた検査回路であ
り、CX₀〜CX₃はその検査出力である。

また、CKY₀〜CKY₃はY₀〜Y₃に設けた検査回路であり、CY
₀〜CY₃はその検査出力である。検査回路CKX₀〜CKX₃,CKY
₀〜CKY₃は検査対象回路の出力を監視することによって
故障を検出する機能を持つ。検査出力CX₀〜CX₃,CY₀〜CY
₃により、検査結果は次のように表示される。

Xiが正常（故障）のとき CXi＝１（０） Yiが正常（故障）のとき CYi＝１（０） ただし、ｉ＝0,1,2,3。なお、検査回路の具体例につい
ては後述する。

５は切替回路であり、切替回路ユニットSU₀〜SU₃からな
る。切替回路はX₀〜X₃とY₀〜Y₃を第２図に示したように
接続する。ただし、第２図ではブロック１と切替回路２
の間はデータ出力の配線であったが、ここではデータ出
力と検査出力のペアによる配線である。すなわち、切替
ユニットSUiは（DXi,CXi），（DXi₊₁,CXi₊₁），（DX
i₊₂,CXi₊₂）の３組のベアを入力し、そのうち１組のベ
アを（DXSi,CXSi）に出力する。ここで、＋はmod ４の
加算を表す。

６は切替制御回路であり、切替制御信号Ｐを発生して、
ユニット間の接続方法を決定する回路である。また、７
はX₀〜X₃の入力信号、８はY₀〜Y₃の出力信号である。

第４図の多重化自動切替装置の動作は次のように行なわ
れる。

（１） 信号INITにパルスを加え、切替制御回路６を初
期状態に設定する。

（２） テスト入力を７から加え、検査回路CKY₀〜CKX₃
とCKY₀〜CKY₃により、各々X₀〜X₃とY₀〜Y₃のテストを行
なう。

（３） 検査結果CXS₀〜CXS₃とCY₀〜CY₃、および切替制
御信号Ｐが接続条件を満足しているか否かを切替制御回
路６で判定する。

（４） 接続条件を満足すれば、現在のユニット間接続
を固定する。満足しなければ、信号CLOCKにクロックパ
ルスを入力すると、切替制御回路６は新たに切替制御信
号を発生する。この切替制御信号に対応する新たなユニ
ット間接続に対して、（３）を繰り返す。

なお、接続条件については後述する。

この多重化自動切替装置はブロック１とブロック２にお
いて正常なユニットが各々２個以上あれば、必ず正常な
ユニットベアを２組以上作る接続方法が見つけることが
できる。

もし、切替制御回路６に全ての接続方法を発生するのに
充分な個数のクロックパルスを加えても、上記の切替操
作が終了しなければ、この故障を救済できないことを意
味する。

さて、検査回路の具体例として第５図に１−out−of−
４デコーダに対する検査回路を示す。

A,Bは１−out−of−４デコーダの入力、G₀,G₁,G₂,G₃は
出力である。検査対象回路が正常であるときには、A,B
の入力値に応じて、D₀〜D₃のいずれか１つの出力が“1"
となる。このときＣは“1"を出力する。ところが、検査
対象回路に故障が発生し、G₀〜G₃のうち偶数個の出力が
“1"となるとき、Ｃが“0"となる。したがって、Ｃを監
視することにより、検査対象回路の故障を検出できる。

ところで、第４図では図の簡単のため、切替回路ユニッ
トには検査回路を付与しなかった。

切替回路ユニットについては、例えばデータ信号に対し
てパリティチェック、切替制御信号に対して1/nチェッ
クによる検査回路を設けることができる。切替回路ユニ
ットSUiの検査回路の出力とブロック２のユニットの検
査出力CYiの論理和を、改めてCYiと定めれば、切替回路
ユニットの故障も自動的に救済できる。

次に、切替制御回路６の構成について説明する。切替制
御回路６には総当り法と順列法の２種類の実現方法があ
る。総当り法は接続する全てのユニット間の接続方法を
カウンターによりしらみつぶしに発生する方法である。
また、順列法はブロック１とブロック２のユニットが１
対１に接続する接続方法のみを、順列発生回路により発
生する方法である。

〔実施例１〕 第６図に総当り法による切替制御回路６の構成を示す。
切替制御回路６は切替先決定回路11、重複選択検出回路
12、正常ユニットペア検出回路13、正常ユニットペア閾
値回路14、クロック制御回路15からなる。11〜15までの
関係を第６図を用いて説明しよう。

第７図に切替先決定回路11の回路例を示す。この回路は
継続接続した４個の３進カウンタCTR₀〜CTR₃よりなる。

総当り法ではCTRiの内容aiに従って、切替回路ユニット
SUiはユニットXi₊aiとユニットYiを接続する（ただし、
ｉ＝0,1,2,3。ai＝0,1,2）。

すなわち、切替先決定回路11は切替制御信号Ｐ＝（a₀,a
₁,a₂,a₃）を生成し、切替回路５を制御する。

第８図は切替制御回路で用いる３進カウンタの例であ
り、601,602はＴ型フリップフロップである。

601,602の内容を各々U₀,U₁とし、これらをまとめて、
（U₀,U₁）と表記することにする。

信号INITにパルスを加えると、601と602はリセットさ
れ、（U₀,U₁）は（0,0）となる。

続いて、信号CINに次々とパルスを加えると、（0,0）→
（0,1）→（1,0）→（0,0）と遷移し、以後これを繰り
返す。

（U₀,U₁）が（1,0）であるとき、信号COUTはパルスを次
段の３進カウンタに出力する。

（U₀,U₁）が（0,0），（0,1），（1,0）であるとき、各
々信号D₀,D₁,D₂が“1"となる。

すなわち、カウンタCTRiの内容aiは信号Daiが“1"を出
力することにより表示される。このとき、YiとXi₊aiが
接続されるので、この信号Daiを以後▲Ｐ^ｉ＋ai _ｘ▼と
称す。ただし、Ｔはmod.4の加算である。

ここで、ブロック１とブロック２のユニット間接続を次
のように整数列で表記しよう。

ユニットYiに接続するユニットをXbiとし、４個のユニ
ットY₀〜Y₃に接続するユニットを整数列〔b₀,b₁,b₂,
b₃〕で表す。

総当り法ではb₁＝ｉ＋aiが成り立つ。ただし、＋はmod
4の加算である。

切替先決定回路11は切替制御信号Ｐ＝（0,0,0,0），
（1,0,0,0），（2,0,0,0），…，（2,2,2,2）に応じ
て、各々〔0123〕，〔1123〕，〔2123〕，…，〔2301〕
なる3⁴個の接続方法を発生する。

なお、初期状態（整数列〔0123〕の想到する接続方法）
には信号INITにパルスを送り、全てのカウンタをリセッ
トすることにより設定する。

ところで、総当り法ではブロック１の同一のユニット
が、ブロック２の複数のユニットを重複して選択する場
合がある。例えば〔1123〕の想到する接続方法では、ユ
ニットX₁をユニットY₀とY₁が重複して選択する。

多重化自動切替装置の各ユニットペアは、異なるデータ
入力に対する独立な処理を行なう。

従って、この例では３つのユニットX₁,Y₀,Y₁が全て正常
であっても、２個のユニットペア（X₁,Y₀），（X₁,Y₁）
のうち、いずれか一方しか使用できない。従って、ブロ
ック１の同一のユニットをブロック２の正常な複数のユ
ニットが重複選択する接続方法を禁止する必要がある。
このために重複選択を検出する回路が重複選択検出回路
12である。

第９図は重複選択検出回路12の回路である。THC₀〜THC₃
は閾値回路であり、３個の入力E₀,E₁,E₂のうち２個以上
が“1"となる回路である。第10図に閾値回路の回路例を
示す。THClは３個の信号▲Ｐ^ｌ _ｌ−ｊ▼を入力する（こ
こで、ｌ＝0,1,2,3。ｊ＝0,1,2。ｌ−ｊはmod ４の差
である）。

従って、THClはユニットXlがブロック２の正常なユニッ
トに重複選択される場合に、Ｔに“1"を出力する。ま
た、重複選択検出信号HSはX₀〜X₃のいずれかのユニット
が重複選択されるときに“1"を出力する。

第11図に正常ユニットペア検出回路13の回路例を示す。
良ユニットペア検出回路13はユニットペアが正常である
か否かを判定する回路である。正常ユニットペア検出GP
はGP＝（GP₀,GP₁,GP₂,GP₃）と表わされる。ここで、GPi
はブロック１のユニットの検査結果CXSiとブロック２の
検査結果CYiより、Yiを含むユニットペアが正常である
と判断したとき“1"を出力する信号である。

第12図に正常ユニットペア閾値回路14の回路例を示す。

正常ユニットペア閾値回路14は正常なユニットペアが２
組以上あること（一般のｋ−out−of−ｎ構成切替回路
ではｋ組以上であること）を判定する回路であり、正常
ユニットペア検出信号GPを入力し、閾値判定信号GEKを
出力する。

GP₀〜GP₃のうち２個以上の信号が“1"であるとGEKは
“1"をとる。

第13図はクロック制御回路15の回路例である。これは、
次に示す接続条件が成立するとき、切替先決定回路11の
クロックを停止する機能を有する。

〔総当り法の接続条件〕

（１） 正常なユニットペアが２組以上存在する（この
とき、GEK＝“1"）。

（２） ブロック１の同一のユニットが、ブロック２の
複数の正常なユニットに重複選択されない（このとき、
MS＝“0"）。

なお、条件（１）または（２）が成立しないときには、
信号CLOCKに入力されたクロックパルスが、信号CLOCK1
に伝幡し、切替先決定回路11のカウンタがインクリメン
トする。その結果、新たに切替制御信号Ｐが生成され、
接続方法が更新される。

〔実施例２〕 順列法による切替制御回路６について述べる。まず、順
列について説明しよう。

第14図は4!を例にとった順列の説明図である。集合｛0,
1,2,3｝の４個の要素を１度づつ使用してできる整数列
を〔b₀,b₁,b₂,b₃〕とする。ここで、bi（ｉ＝0,1,2,3）
は整数列を構成する左から（ｉ＋１）番目の要素であ
る。

さて、〔b₀,b₁,b₂,b₃〕を第14図の矢印に従って、次の
ように求める。

b₀は0,1,2,3のいずれかである。

b₁はb₀で選んだ要素を除く３つの要素のいずれかであ
る。

b₂はb₀とb₁で選んだ要素を除く残りの２つの要素のいず
れかである。

b₃はb₀,b₁,b₂で選んだ要素を除く残りの１つの要素であ
る。

この規則によれば、〔b₀,b₁,b₂,b₃〕として〔0123〕，
〔0132〕，…，〔3012〕の4!＝24個の整数列を作れる。
このように要素の配置を変えて得られる整数列の集合を
順列と呼ぶ。

一般に集合｛0,1,…,n−１｝のｎ個の要素を１回だけ使
用して並べてできる長さｎの整数列〔b₀,b₁,…,bn_-1〕
はn!個生成できることから、これをn!個生成できること
から、これれをn!の順列と呼ぶことにする。

さて、前に述べたように、ユニット間接続を整数列
〔b₀,b₁,b₂,b₃〕によって表記すると、X₀〜X₃とY₀〜Y₃
を１対１に接続する全ての接続方法を4!の順列により表
わすことができる。

逆に4!の順列を発生すれば、上記ユニットを１対１に接
続する全ての接続方法を発生すことができる。このよう
な観点から順列によりユニット間接続を定める方法が順
列法である。

第15図に順列法による切替制御回路６の構成を示す。な
お、既出の信号名は特に記さない限り、総当り法と同一
の機能を持つ。この切替制御回路６は順列発生回路21、
正常ユニットペア検出回路22、正常ユニットペア閾値回
路14、クロック制御回路23からなる。

正常ユニットペア閾値回路14と回路21〜23の関係を第15
図をもとに説明する。

順列発生回路21は整数列に対応する切替制御信号Ｐを発
生する。従って、この回路は総当り法での切替先決定回
路11に相当する回路である。順列発生回路21の構成と動
作については後述する。

順列法ではユニット間の１対１接続を保証しているの
で、総当り法のようにブロック１の同一のユニットを重
複選択することはない。従って、重複選択検出回路は不
要である。

ところが4!の順列にはユニット間接続に置き換えられな
い整数列が含まれている。例えば、第４図に示すように
Y₀とX₃は接続関係がないため、整数列〔3012〕に対応す
る接続方法は存在しない。従って、順列法では整数列に
対応する接続方法が存在するか否かを判断することが必
要である。

第16図に正常ユニットペア検出回路22の回路例を示す。
これは整数列に対応する接続方法が存在することと、生
成されたユニットペアが正常であることを確認するため
の回路である。前者の機能を有する点が総当り法の正常
ユニットペア検出回路と異なる。図中の信号GPi（ｉ＝
0,1,2,3）はユニットYiにユニットXbiが接続しており、
しかもユニットペアが正常であるとき、“1"を出力す
る。

正常ユニットペア閾値回路14は〔実施例１〕で述べた第
12図の回路である。

第17図にクロック制御回路23の回路例を示す。正常ユニ
ットペア閾値回路14の閾値判定信号GEKが“1"のとき、
この回路は信号CLOCKに加わるクロックパルスから信号C
LOCK1と信号CLOCK2に２相クロックを生成し、GEKが“0"
のとき２相クロックを停止する。なお、この２相クロッ
クにより順列発生回路21の順列表示部と巡回モード制御
部を交互に動作させる。

さて、順列法の接続条件は次のとおりである。

〔順列法の接続条件〕

（１） 整数列に対応する接続方法が存在する。

（２） 正常なユニットペアが２組以上存在する。

正常ユニットペア検出回路22とユニットペア閾値回路14
が上記の条件（１），（２）を判定する。条件（１），
（２）を共に満足すれば、GEKは“0"となり、順列発生
回路21に２相クロックを供給させる。その結果、切替回
路５は現在の接続方法を保持する。

条件（１）または条件（２）を満足しないときには、GE
Kは“1"となり、順列発生回路21に２相クロックが供給
される。その結果、切替回路５は接続方法を更新する。
以上が、順列法による切替制御回路の説明である。

次に２−out−of−４構成の多重化自動切替装置に適用
される4!の順列発生回路21について述べる。この順列発
生回路21はLondon G.Gにより提案されたアルゴリズム
（An Algorithm for generating permutations CACM 1
0,p298−299,1967）を専用ハードウェア化した回路であ
る。

第18図に4!の順列発生回路21の構成を示し、31は順列表
示部、32は巡回モード制御部、33は3wayのマルチプレク
サ、34はクロック生成回路である。

R₀〜R₃は各々要素b₀〜b₃を記憶するレジスタであり、こ
の出力が切替制御信号となる。

順列表示部31は整数列〔b₀b₁b₂b₃〕を表示し、これから
新たに整数列〔b₀′b₁′b₂′b₃′〕を発生する機能を持
つ。

長さｉ（ｉ＝2,3,4）の部分整数列〔b₀…bi_-1〕を右巡
回し、残りの部分整数列〔bi…b₃〕を連結して、上記の
整数列〔b₀′b₁′b₂′b₃′〕を得るとき、巡回モードMi
による導出と呼ぶことにする。すなわち、このとき整数
列〔b₀′b₁′b₂′b₃′〕は〔b₀b₁b₂b₃〕を用いて、次の
ように記述できる。

まず、右巡回する部分整数列は b₀′←bi_-1 b₁′←b₀ b₂′←b₁ ‥‥ ｂ′i_-1←bi_-2 残りの更新されない部分整数列は bi′←bi ｂ′i₊₁←bi₊₁ ‥‥ b₃′←b₃ 従って、順列表示部31は次のように動作する。

レジスタR₀,R₁,…,Ri_-1に記憶されるデータは右巡回
し、レジスタRi,Ri₊₁,…,R₃に記憶されるデータは更新
しない。

また、マレチプレクサ33は、レジスタR₁,R₂,R₃の中から
Ri_-1となる出力を選択し、レジスタR₀に入力する。クロ
ック生成回路34は右巡回するデータを記憶するレジスタ
R₀,R₁,…,Ri_-1にクロックを供給する。

第19図にクロック生成回路34の回路例を示す。信号CLK1
はレジスタR₀とR₁に供給するクロック信号であり、信号
CLK2,CLK3は各々レジスタR₂,R₃に供給するクロック信号
である。

巡回モードがMj₊₁,Mj₊₂,…,M₄のとき、CLKjにCLOCK2か
らのクロックパルスが伝幡する。その結果、レジスタRj
の内容が更新される。

巡回モード制御部32は巡回モードMiを決定する回路であ
る。この内部構成については後述する。

第18図の順列発生回路21の動作に当っては、まず順列表
示部31と巡回モード制御部32を初期状態に設定する。な
お、初期状態については後述する。

次にクロック制御回路23により信号CLOCK1,CLOCK2の順
に交互にクロックパルスを発生する。クロックパルスが
加わる度に巡回モード制御部32は巡回モードを設定し、
これに基づいて順列表示部31が順次新たな整数列を発生
する。このようにして、順列発生回路21は4!の順列を発
生することができる。

次に、順列発生回路21の順列発生手順について第19図に
基づいて説明する。

〔4!の順列の発生手順〕 （１） 整数列Ａ＝〔0123〕を初期状態とする。M₂モー
ドを２回繰り返すと、その過程で整数列〔0123〕をを発
生して、元の整数列Ａに戻る。（「１」，「２」）（以
下「１」〜「40」は発生順序を示す） （２） M₃モードでＡの左の３要素を右巡回して、新た
に整数列Ｂ＝〔2013〕を得る。（「３」） （３） Ｂに上記（１），（２）の操作を行ない、その
結果、新たに整数列〔0213〕と〔1203〕を得る。
（「４」，「５」，「６」） （４） Ｃに上記（１），（２）の操作を行ない、その
結果、新たに整数列〔2103〕を得て、Ａに戻る。
（「７」，「８」，「９」） （５） M₄モードにより、Ａの全ての要素を右巡回し
て、新たに整数列Ｄ＝〔3012〕を得る。（「10」） （６） Ｄに上記（１）〜（５）の操作を行ない、〔03
21〕，〔1302〕，〔3102〕，〔0132〕，〔1032〕なる５
個の整数列を得て、整数列Ｅ＝〔2301〕を発生する。
（「11」〜「20」） （７） Ｅに上記（１）〜（５）の操作を行ない、〔32
01〕，〔0231〕，〔2031〕，〔3021〕，〔0321〕なる５
個の整数列を得て、整数列Ｆ＝〔1230〕を発生する。
（「21」〜「30」） （８） Ｆに上記（１）〜（５）の操作を行ない、〔21
30〕，〔3120〕，〔1320〕，〔2310〕，〔3210〕，〔12
30〕なる整数列を得て、Ａに戻る。（「31」，〜「4
0」） 本アルゴリズムを再帰的に表現すると、次のようにな
る。

〔操作▲Ｇ^４ _３▼〕 （１） 部分整数列〔b₀,b₁〕を２回右巡回する。（M₂
モード） （２） 部分整数列〔b₀,b₁,b₂〕を１回右巡回する。
（M₃モード） 〔操作▲Ｇ^４ _４▼〕 （１） 操作▲Ｇ^４ _３▼を３回繰り返す。

（２） 整数列〔b₀,b₁,b₂,b₃〕を１回右巡回する。（M
₄モード） 以上の準備のもとに求めるアルゴリズムは 〔4!の順列発生アルゴリズム〕 初期状態〔0123〕に対して、操作▲Ｇ^４ _４▼を４回繰り
返す。

以上のことから、長さ２から４までの部分整数列を右巡
回する第18図の順列発生回路は4!の順序を発生する機能
を持つことが分る。なお、本アルゴリズムでは部分整数
列を右巡回することによって順列を導出したが、左巡回
によっても同様に導出できることは明らかである。

さて、4!の順序を発生する過程で現われる巡回モードは
次のとおりである。

M₂,M₂,M₃ M₂,M₂,M₃ M₂,M₂,M₃,M₄ M₂,M₂,M₃ M₂,M₂,M₃ M₂,M₂,M₃,M₄ M₂,M₂,M₃ M₂,M₂,M₃ M₂,M₂,M₃,M₄ M₂,M₂,M₃ M₂,M₂,M₃ M₂,M₂,M₃,M₄ この巡回モード系列を４（３（2M₂,M₃）,M₄）と表記す
ることにする。ここで、巡回モードMiの記号の前の整数
はMiの繰返し回数を示す。また、左括弧の前の整数は括
弧で囲まれた部分の繰返し回数を示す。

上記の巡回モード系列では、2M₂はM₂を２回繰返すこと
を、３（2M₂,M₃）は系列2M₂,M₃を３回繰返すことを、ま
た４（３（2M₂,M₃）,M₄）は系列３（（2M₂,M₃）,M₄）を
４回繰返すことを意味する。

上記の巡回モード系列は次の規則によって生成される。

（１） 2M₂,M₃なる巡回モード系列を発生する。

（２） M₃モードが３回現われると、この３回目のM₂モ
ードの後に、M₄モードを発生する。

第21図にこの規則に基づいて動作する巡回モード制御部
32の回路例を示す。なお、巡回モードM₂,M₃,M₄の発生は
各々信号線M₂,M₃,M₄を“1"にすることにより示す。

Ｄ型フリップフロップ701〜704による巡回シフトレジス
タは、巡回モード系列2M₂,M₃,M₄を発生するとき、長さ
３の巡回ループを、巡回モード系列2M₂,M₃,M₄を発生す
るとき、長さ４の巡回ループを形成する。CTRは４進カ
ウンタであり、規則（２）に基づいてM₄モードに発生す
る。

第22図にCTRの構成例を示す。

第21図の巡回モード制御部32の回路動作は次のとおりで
ある。

（１） 信号INITにパルスを加え、初期状態に設定す
る。すなわち、巡回シフトレジスタにおいて、701の内
容を“1",702〜704の内容を“0"に設定する。また、CTR
の内容を“0"に設定する。（このとき、M₂モードを発生
する。） （２） 信号CLOCK1にクロックパルスを加える度に、巡
回シフトレジスタでデータ“1"がシフトする。３回目の
クロックパルスで、巡回シフトレジスタの長さ３のルー
プにおいて、データ“1"が巡回し、CTRに最初のクロッ
クパルスが加わる。（M₂,M₃を発生する。） （３） （２）と同様に巡回シフトレジスタの長さ３の
ループにおいて、データ“1"が巡回し、CTRにクロック
パルスが加わる。（2M₂,M₃を発生する。） （４） 巡回シフトレジスタの長さ４のループにおい
て、データ“1"が巡回し、CTRにクロックパルスが加わ
る。このとき、CTRはM₄を発生する。（2M₂,M₃,M₄を発生
する。） （５） 上記の（２）〜（４）の操作を３回繰返すと初
期状態に戻る。

以上が４（３（2M₂,M₃）,M₄）なる巡回モード系列を発
生する第21図の巡回モード制御部32の説明であった。

この他にも4!の順列を発生する巡回モード系列として、 ４（２（3M₃,M₂）,M₄） ３（４（2M₂,M₄）,M₃） ３（２（4M₄,M₂）,M₃） ３（２（4M₄,M₂）,M₃） ２（４（3M₃,M₄）,M₂） ２（３（4M₄,M₃）,M₂） がある。

以上の巡回モード系列t₄は、次のようにまとめて表現で
きる。

t₂＝r₂・Mr₂ t₃＝r₃・（t₂,Mr₂） t₄＝r₄・（t₃,Mr₄） ただし、集合｛2,3,4｝の３個の要素を１度づつ使用し
てできる3!＝６個の整数列〔r₂,r₃,r₄〕を要素として、
r₂,r₃,r₄を定義する。上記の具体例ではr₂＝2,r₃＝3,r₄
＝４である。

以上が4!の順列発生回路の説明であった。この順列発生
回路を利用して、順列法による切替制御回路を作ること
ができる。

本提案の多重化自動切替装置を、２−out−of−４切替
構成に基づいて説明した。一般のｋ−out−of−ｎ切替
構成における多重化自動切替装置は本具体例より容易に
類推できる。

（発明の効果） 以上説明したように、本発明はユニットおよび、切替回
路自身の故障を救済する切替構成を与える利点を有し、
次のように応用される。

LSIの製造に当って、切替対象回路を多重化し、本発明
に基づく多重化自動切替装置を設ければ、欠陥の生じた
ユニットを検査回路により検出し、これを正常なユニッ
トに切替えて使用することにより、高い歩留りを有する
LSIを製造できる。

また、通常処理中の回路に対して、本発明による多重化
自動切替装置は固定故障および間欠故障を検査回路によ
り検出し、正常なユニットに切替えることにより、装置
の高信頼化を実現できる。

以上の欠陥と故障は自動的に切替えられるので、使用者
を煩らわせず、迅速に修復される。

【図面の簡単な説明】

第１図は従来の切替装置の２−out−of−４切替構成の
適用例を示す図、第２図は特願昭58−232683号に提案さ
れた多重化切替装置の２−out−of−４切替構成の適用
例を示す図、第３図は第２図の多重化切替装置の故障に
対する救済方法を示す図、第４図は本発明の多重化切替
装置の２−out−of−４切替構成の適用例を示す図、第
５図は１−out−of−４デコーダとその検査回路を示す
図、第６図は総当り法の切替制御回路６の構成図、第７
図は切替先決定回路11の実施例を示す図、第８図は３進
カウンタ（CTR₀〜CTR₃）の実施例を示す図、第９図は重
複選択検出回路12の実施例を示す図、第10図は閾値回路
（THC₀〜THC₃）の実施例を示す図、第11図は総当り法の
正常ユニットペア検出回路13の実施例を示す図、第12図
は正常ユニットペア閾値回路14の実施例を示す図、第13
図は総当り法のクロック制御回路15の実施例を示す図、
第14図は4!の順列の説明図、第15図は順列法の切替制御
回路６の構成図、第16図は順列法の正常ユニットペア検
出回路22の実施例を示す図、第17図は順列法のクロック
制御回路23の実施例を示す図、第18図は4!の順列発生回
路21の構成図、第19図はクロック生成回路34の実施例を
示す図、第20図は4!の順列発生手順の例を示す図、第21
図は4!の順列発生回路の巡回モード制御部32の実施例を
示す図、第22図は４進カウンタの実施例を示す図であ
る。 1,2……ブロック、3,4,5……切替回路、６……切替制御
回路、７……ブロック１の入力、８……ブロック２の出
力、９……１−out−of−４デコーダの検査回路、11…
…切替先決定回路、12……重複選択検出回路、13……総
当り法の正常ユニットペア検出回路、14……正常ユニッ
トペア閾値回路、15……総当り法のクロック制御回路、
21……順列発生回路、22……順列法の正常ユニットペア
検出回路、23……順列法のクロック制御回路、31……順
列表示部、32……巡回モード制御部、33……3wayマルチ
プレクサ、34……クロック生成回路、101〜198……AND
ゲート、201〜272……ORゲート、301〜341……反転ゲー
ト、401……EXORゲート、501……NORゲート、601〜622
……Ｔ型フリップフロップ、701〜704……Ｄ型フリップ
フロップ、X₀〜X₃……ブロック１のユニット、Y₀〜Y₃…
…ブロック２のユニット、MU₀,MU₁……マルチプレクサ
ユニット、DU₀,DU₁……デマルチプレクサユニット、S₀
〜S₃……多重化切替装置の切替回路ユニット、SU₀〜SU₃
……多重化自動切替装置の切替回路ユニット、P,Q……
切替制御信号、▲Ｐ^０ _０▼，▲Ｐ^１ _０▼，▲Ｐ^２ _０▼，
▲Ｐ^１ _１▼，▲Ｐ^２ _１▼，▲Ｐ^３ _１▼，▲Ｐ^２ _２▼，▲
Ｐ^３ _２▼，▲Ｐ^０ _２▼，▲Ｐ^３ _３▼，▲Ｐ^０ _３▼，▲Ｐ
^１ _３▼……切替制御信号Ｐの要素、A,B……デコーダ入
力、G₀〜G₃……デコーダ出力、Ｃ……デコーダ検査出
力、MS……重複選択検出信号、GEK……閾値判定信号、G
P……正常ユニットペア検出信号、GP₀〜GP₃……正常ユ
ニットペア検出信号GPの要素、INIT……初期設定信号、
CLOCK,CLOCK1,CLOCK2……クロック信号、CTR₀〜CTR₃…
…３進カウンタ、D₀〜D₃……３進カウンタの出力、CIN
……クロック入力、COUT……クロック出力、T₁CK……ク
ロック入力、CLR……リセット入力、PR……プリセット
入力、Ｄ……データ入力、Q,……データ出力、THC₀〜
THC₃……閾値回路、E₀〜E₃……閾値回路入力、Ｆ……閾
値回路出力、R₀〜R₃……整数列〔b₀,b₁,b₂,b₃〕を記憶
するレジスタ、CLK1〜CLK3……クロック信号、M₂〜M₄…
…巡回モード信号、CTR……４進カウンタ。

Claims (3)

【特許請求の範囲】
1. 【請求項１】同一構成のｎ（ｎ≧２）個のユニットX₀,X
   ₁,・・・,Xn_-1からなるブロック１と同一構成のｎ個の
   ユニットY₀,Y₁,・・・,Yn_-1からなるブロック２に関
   し，それぞれから正常なｋ（１≦ｋ＜ｎ）個のユニット
   を選択して，自動的に１対１接続するｋ−out−of−ｎ
   構成電子装置において， 各ユニットに付与され，その正常性を判定する検査回路
   と， 任意のユニットXiのデータ出力DXiと前記検査回路の出
   力CXiをペアとして，（ｎ−ｋ＋１）組のペア（DXi,CX
   i），（DXi₊₁,CXi₊₁），・・，（DXi₊j,CXi₊j），・・
   ・，（DXi₊n_-k,CXi₊n_-k）から選択した１組のペア（DXS
   i,CXSi）を出力するｎ個の切替回路ユニットSUi（但し,
   i＝0,1,・・・,n−１。ｊ＝0,1,・・・,n−ｋ。ｉ＋ｊ
   はmod ｎの和）と， 前記切替回路ユニットの出力CXS₀,CXS₁,・・・,CXSn_-1
   と前記ユニットY₀,Y₁,・・・,Yn_-1の検査回路の出力か
   らブロック１とブロック２の正常なユニットを１対１接
   続するように切替回路ユニットを制御する切替制御回路
   から構成されることを特徴とする多重化自動切替装置。
2. 【請求項２】前記切替制御回路として，継続接続するｎ
   個の（ｎ−ｋ＋１）進カウンタCTRiの内容aiに基づき，
   ユニットXi₊aiとユニットYiを接続するように切替回路
   ユニットを制御する切替先決定回路（但し,i＝0,1,・・
   ・,n−１。ai＝0,1,・・・,n−ｋ。ｉ＋aiはmod ｎの
   和）と， これらの接続されたユニット２個からなるユニットペア
   が正常であることを前記検査出力より表示する正常ユニ
   ットペア検出回路と， 正常ユニットペア検出回路の出力から正常なユニットペ
   アがｋ組以上存在することを表示する正常ユニットペア
   閾値回路と， 切替先決定回路の出力とブロック１のユニットの検査出
   力からブロック１の同一のユニットがブロック２の複数
   の正常なユニットに接続しないことを表示する重複選択
   検出回路と， 正常ユニットペア閾値回路と重複選択検出回路の出力か
   らｋ組以上の正常なユニット同士が１対１接続すること
   を判定し，このとき前記の切替決定回路のカウンタのク
   ロックを停止するクロック制御回路とから構成される切
   替制御回路を用いたことを特徴とする特許請求の範囲第
   （１）項記載の多重化自動切替装置。
3. 【請求項３】前記切替制御回路として，それぞれ整数０
   〜ｎ−１を表示できるレジスタR₀,R₁,・・・,Rn_-1にお
   いて,R₀からR₁,R₁からR₂,・・・,Rn_-2からRn_-1への転送
   バスとR₂からR₀,R₃からR₀,・・・,Rn_-1からR₀への巡回
   バスを設け，クロックが加わる度にこれらのレジスタの
   内容を巡回させることにより，整数｛0,1,・・・,n−
   １｝を並べかえてできる整列数を，レジスタRiの内容bi
   により表わされる整列数［b₀,b₁,・・・,bn_-1］として
   表示し，これによりユニットXbiとユニットYiを接続さ
   せる順列発生回路と， 正常なユニットペアが存在することを順列発生回路の出
   力と前記検査回路の出力より表示する正常ユニットペア
   検出回路と， 正常ユニットペア検出回路の出力より正常なユニットペ
   アがｋ組以上存在することを表示する正常ユニットペア
   閾値回路と， 正常なユニットペアがｋ組以上存在するとき，前記順列
   発生回路へのクロックを停止するクロック制御回路とか
   ら構成される切替制御回路を用いたことを特徴とする特
   許請求の範囲第（１）項記載の多重化自動切替装置。