JPH0359457B2 - - Google Patents

Description

【発明の詳細な説明】 本発明は、ｎ個の同期をとつて制御され、並列
に作動する計算機モジユールを具え、これらの計
算機モジユールの各々が自己の誤り分離区域内に
置かれ、各計算機モジユールが下記のもの、即
ち、 − プロセサモジユールと； − このプロセサモジユールの第１データ接続部
に接続されている第１データチヤネルと； − 受信されたデータ語から符号記号を形成する
ために前記第１データチヤネルに接続され、ｋ
個のデータ記号を具えるデータ語に基づいて、
２個以上の符号記号を同時に訂正できる能力を
具える符号のｋ＋１≦ｎ＜3k個の符号記号か
ら成る符号語を形成するリデユーシングエンコ
ーダと； − このリデユーシングエンコーダのデータ出力
端子に接続されたデータ入力端子と、前記プロ
セサモジユールに接続されたアドレス入力端子
と、データ出力端子とを具えるメモリモジユー
ルと； − 相互接続回路網を介して、前記メモリモジユ
ールの前記データ出力端子に接続され、各計算
機モジユールから符号語の関連符号記号を受取
り、これからデータ語を構成し、前記第１デー
タ接続部と前記データチヤネルとに接続される
データ出力端子を具え、前記第１データチヤネ
ルが外部のデータ入出力に対する第２データ接
続部も具えるデータ語再構成モジユール； とを具えるマルチプロセサ計算機装置に関するも
のである。

このような計算機装置は本願人の名による以前
のオランダ国特許願第8104342号明細書に開示さ
れている。このようなマルチプロセサ計算機装置
では、例えば、対応する数の誤り分離区域間に分
布されている全体で三重構成のプロセサ及びメモ
リの容量と比較して可成り小さい全体のメモリ容
量で可成り高いプロセサ容量に十分である。以前
のオランダ国特許願によれば、全三重構成を用い
る時と同じように、１個のこのような誤り分離区
域の全回路は、マルチプロセサ計算機装置の全体
としての動作が妨げられることなく、任意のデー
タ誤りを示す可能性がある。これ以前のオランダ
国特許願に係る計算機装置はいくつかの動作モー
ドを有する。而してこれらの動作モードの一つで
は、（どの記号が間違つているかが知られている
場合）１つの単一のビツト誤りに加えて任意の記
号誤りを訂正できる。別の動作モードでは、２個
の任意の１ビツト誤りを訂正できる。数個のビツ
ト誤りを訂正できる符号自体もいくつか知られて
いる。例えば、「フアイア」（Fire）符号である。
この「フアイア」符号を用いれば誤り位置は完全
に任意である。

前記オランダ国特許願の誤り訂正能力は本願人
の名によるそれ以前の欧州特許願第0031183A3号
に開示されている誤り訂正能力の拡張である。後
者はデータ入出力を実行するのに使用できるいく
つかの冗長レベルを提供している。十分な誤り訂
正能力を有する高度の冗長度がデータ入出力の接
続関係を計算機装置本体内での計算機モジユール
の多重化と同じように多重化することにより達成
される。この時関連する周辺装置も多重構造にす
ることができる。他方、周辺装置は冗長を持たず
単一にすることもできる。中間の冗長レベルも作
れる。これらの種々の冗長レベルはオランダ国特
許願第8104342号に開示されているマルチプロセ
サ計算機装置に組み入れることができる。多くの
場合は、例えば、データをバツフアし、再フオー
マツトするために入出力メモリを設ける必要があ
る。この場合、関連するデータ再構成セクタ、デ
ータ接続部等を伴なうｎ個の記号から成る符号語
を形成すべき時生ずるであろう他のコスト因子と
比較してコスト因子を考えた時記憶容量は通常は
可成り小さくなる。これはまた入出力メモリに加
えて、入出力プロセサモジユールと多くはこれに
関連する別の要素とを必要とする場合にもあては
まる。

この結果、入出力データは（誤り訂正符号との
関係で見た場合）符号化されない形態で受信され
る。

それ故、本発明の目的は、入出力過程におい
て、生起するビツト誤りがリデユーシングエンコ
ーダで多重ビツト記号誤りに変換されることがな
いように入出力データを処理できるようにするに
ある。このような多重記号誤りは多くの場合にも
う一つのビツト誤りが生起すると、符号の誤り訂
正能力がすぐ不十分になる。

この目的を達成するため、本発明は各計算機モ
ジユールがまた下記のもの、即ち、− 前記第２
データ接続部と直列に接続され、周辺装置に対
する第３データ接続部を具える第２データチヤ
ネルと； − 前記リデユーシングエンコーダの生成行列
（G_i）がデータビツトを２個以上の符号ビツト
に重ね合わせる時、第２の非リデユーシングエ
ンコーダと、この第２のエンコーダに関連する
デコーダとを介して第２データチヤネルに接続
され、少なくともリデユーシングエンコーダが
１個のデータビツトを２個以上の符号ビツトに
重ね合わせる場合は、このリデユーシングエン
コーダの生成行列（G_i）と、第２のエンコーダ
の生成行列（G_i ^*）と、デコーダの生成行列 （G_i ^*-1）との間に下記の関係、即ち、 ［G_i ^*］・［G_i ^*-1］＝［Ｉ］，恒等行列； ［Ｆ］＝［G_i］・［G_i ^*-1］ が存在し、ここにおいてビツトから成るものと
して書かれた［Ｆ］の各列が多くて１個の
「１」を有し、残りが全て「０」で、［Ｆ］の各
行が１個以上の「１」を有し、関連する計算機
モジユール内で入出力メモリで符号化されたデ
ータ語の一ビツトがこのデータ語から形成され
る得る符号記号の高々一ビツトの上に重ね合わ
される入出力メモリモジユール； とを具えることを特徴とする。

リデユーシングエンコーダが１個のデータビツ
トを「０」符号ビツトに重ねる限り、関連データ
ビツト内の誤りは関連するメモリモジユールに渡
されない。この重ね合せがリデユーシングエンコ
ーダ内で１個の符号ビツトに対して行なわれる限
り、第２のエンコーダ／デコーダで何の特別の手
段をとらない時でも、入出力メモリ内の１ビツト
誤りは関連するメモリモジユール内で唯一のビツ
ト誤りとして渡される。両方の場合とも、第２の
エンコーダの生成行列は関連データビツトに対す
る恒等行列（ビツトの順序を修正する転置行列が
乗算されることもあり、されないこともある）の
性質を有し得る。リデユーシングエンコーダが１
個のデータビツトを２個以上の符号ビツトに重ね
る場合は、関連する生成行列は一層厳しい要求を
満足しなければならない。

符号の誤り訂正能力が少なくとも１個の符号記
号内に少なくとも１個の任意の誤りベクトルを有
するようにすると好適である。前記の２個の特許
願の新しい方の「消去」モードとの関係で、この
本発明の思想は非常に魅力的なものである。

データ誤再構成モジユールが異なる訂正能力を
具える少なくとも２個の選択的に活性化できる動
作モードを有すると好適である。このようにする
と種々の誤りの原因を処理するフレキシビリテイ
が更に強くなる。

行列〔Ｆ〕の各行が正確に１個の「１」を具え
るようにすると好適である。この場合は、入出力
メモリの多くの誤りが主メモリの関連するメモリ
モジユールで現われず、主メモリでの誤りの確率
が小さくなる。

行列〔Ｆ〕の各列が正確に１個の「１」を具え
るようにすると好適である。この場合、入出力メ
モリの全ての誤りが主メモリの関連メモリモジユ
ールで現われ、従つて入出力メモリが容易にテス
トできる。

本発明はまた上述した種類のマルチプロセサ計
算機装置で使用される計算機モジユールにも関す
るもので、これは： マルチプロセサ計算機装置で使用される計算機
モジユールであつて、該モジユールが下記のも
の、即ち、 − プロセサモジユール２０と； − このプロセサモジユールによつてアドレスさ
れるメモリモジユール３０と； − ｋ個の記号データ語をプロセサモジユールと
双方向に通信するための第１データチヤネル７
０と； − この第１データチヤネルによつて供給される
ｋ個の記号データ語を受信し、この受信したデ
ータ語から２個以上の各符号記号の誤りを同時
に訂正できる能力を具える符号に基づいている
ｎ個（ここにｎ＞ｋ）の記号符号語の符号記号
を発生して前記メモリモジユールに与えるリデ
ユーシングエンコーダ４０と； − 前記メモリモジユールから、或る特定の符号
語を構成するｎ個の記号の内のいずれかを受信
するためのインターフエース手段５０を有して
いるデータ語再構成モジユール６０に至るチヤ
ネルであつて、前記データ語再構成モジユール
から前記第１データチヤネルに与える別のデー
タ語を発生させるために設けられる相互接続回
路網； とを具える計算機モジユールにおいて、当該モジ
ユールがまた下記のもの即ち、 − 周辺装置に対してインターフエースするため
に前記第１データチヤネルに直列に接続する第
２の双方向データチヤネル９０と； − 前記リデユーシングエンコーダの生成行列Ｇ
(i)がデータビツトを２個以上の符号ビツトに重
ね合わせる時、第２の非リデユーシングエンコ
ーダ１２０によつてデータが送り込まれ、次い
で第３デコーダ１３０を介してデータを第２デ
ータチヤネルに送り込む入出力メモリモジユー
ル； とを具え、第２エンコーダの生成行列［G_i ^*］と、
デコーダの生成行列［G_i ^*-1］との間に下記の関
係、即ち ［G_i ^*］・［G_i ^*-1］＝［Ｉ］，恒等行列； ［Ｆ］＝［G_i］・［G_i ^*-1］ が存在し、ここにおいてビツトから成るものとし
て書かれた［Ｆ］の各列が多くて１個の「１」を
有し、残りが全て「０」で、［Ｆ］の各行が１個
以上の「１」を有し、関連する計算機モジユール
内で入出力メモリで符号化されたデータ語の一ビ
ツトがこのデータ語から形成され得る符号記号の
一ビツトの上に重ね合わされるようにしたことを
特徴とする。このような計算機モジユールを用い
ると、誤りに耐えられるマルチプロセサ計算機装
置が容易に形成できる。

好適な実施例の説明 図面につき本発明を詳細に説明する。

第１図は本発明に係るマルチプロセサ計算機装
置のブロツク図である。この図面の一部は前に引
用した欧州特許願第0031183号の第３図に対応し、
この欧州特許願をここに参考文献として含める。
このマルチプロセサ計算機は４個の同期をとつて
制御される計算機モジユールを具え、これらの計
算機モジユールが全て同じ指令を実行する。同期
機構（図示せず）は４個の相互に同期をとつたク
ロツクのシステムとすることができるが、図面を
簡単ならしめるため省略してある。第１の計算機
モジユールはプロセサモジユール２０、列えば、
適当なマイクロプロセサを具える。このプロセサ
モジユール２０のアドレス出力端子は局所メモリ
３０のアドレス入力端子に接続する。データはデ
ータチヤネル７０とリデユーシングエンコーダ
（reducing encoder）４０とを経て局所メモリ３
０のデータ入力端子に加える。これにより16ビツ
トのデータ語は８ビツトの符号記号に変換され
る。局所メモリ３０が読出される時は、この符号
記号は32ビツトの幅を有するレジスタ５０に加え
られる。各サブ計算機はこのようなレジスタを具
え、全てのレジスタが全てで４個の８ビツト符号
記号で充たされる。符号語レジスタ５０の出力端
子はデータ語再構成モジユール６０に接続する。
このデータ語再構成モジユールは任意の（位置の
点でも誤りの点でも任意）間違つている符号記号
を訂正することができ、（４個の）サブ計算機の
一つが任意の態様で（但し、故障自体が他のサブ
計算機の動作に悪影響を及ぼさないものとする）
で失敗しても大丈夫である。前述したように、あ
る場合には異なる符号記号内のビツトも訂正でき
る（２ビツト、これらの各々は異なる符号記号内
に位置する又は消去モードでの１符号記号、この
符号記号はこの時無視され、値の符号記号に１ビ
ツトを加える）。上記の方法は４ビツト符号に基
づく符号に適用できるが、各データ語及び各符号
語は本当は２個の半部から成り、斯して各半部は
夫々２個及び４個の記号を具える。符号化回路は
可成り短い記号を用いるため簡単である。最左端
の計算機モジユールでは、関係するラインを介し
て語（データ語又は符号語）当り送られるビツト
の数が示されている。記号の数及び長さを異なる
ように選択した場合は、各記号が少なくとも２個
のビツトを含むならば、対応する状態が生ずる。

計算機はまたデータ入出力装置を具えるが、こ
こでも１個の計算機モジユールに対する入出力装
置の関連部分だけを説明する。接続要素80を設け
る。これは、例えば、プロセサモジユール２０に
より活性化される双方向３状態バツフア又は制御
ライン（図示せず）を介する関連制御要素であ
る。接続要素はまた完全に受動的な要素、例え
ば、バス接続とすることもできるが、この場合は
全ての接続要素（データ送受信機）を選択的に活
性化する。データチヤネル９０は16ビツトの幅を
有し、第２の接続要素１４０により終端してい
る。また入出力プロセサ１００を設けるが、これ
は或る場合には省略することができる。この入出
力プロセサ１００のアドレス出力端子はメモリ１
１０のアドレス入力端子に接続する。入出力プロ
セサがない場合は、このメモリは、例えば、外部
からのアドレツシングを必要としない先入れ先出
し（FIFO）バツフアとする。プロセサが必要な
場合は、例えば、データを磁気デイスメモリに蓄
わえるためにフオーマツトする必要がある時に生
ずる。この時は、メモリ１１０のバツフア機能に
加えて、同期情報、表示情報及び空きスペース情
報の付加又は除去も必要となる。このような磁気
デイスクメモリは前記特許願に開示されている方
法の一つで接続することができる。同じことは他
の入出力状況にもあてはまる。ほとんど冗長を含
まないセツトアツプでは、送信のためには接続要
素１４０，１４２，１４４，１４６の一つだけが
活性化され、受信のためには全ての接続要素が並
列に活性化され、全ての接続要素が同じ情報を受
取る。高い冗長を含むセツトアツプでは、関連周
辺装置も多重構造（例えば、ｎ重構造）を有する
ようにし、類似のリデユーシングエンコーダを要
素40〜46と同り態様で、送信のためにも受信のた
めにも接続要素１４０〜１４６に接続し、接続要
素１４０〜１４６の各々はそれ自身のデータ語再
構成モジユールを具え、これが符号語の全ての符
号記号を受取る。これらの２個の両極端の間には
バラエテイに富む多数の方法が存在する。

前述した異なる訂正機能は装置の異なるタイプ
の故障に関係する。プロセサ、例えば、プロセサ
モジユール２０又は入出力プロセサモジユール１
００が故障している時は、このような故障は通常
恒久性で（多数の順次のプロセササイクルを有す
る）、間違つたデータ語に基づいて形成された
（例えばリデユーシングエンコーダ４０により）
符号記号に多数の多重ビツト誤りを生ずる。デー
タ語再構成モジユール６０内の記号訂正符号によ
り提供される方法を用いる以外にこの状況に対す
る治療法はない。これはデータ語内の誤りがしば
しば数ビツトを含むからである。

第２のカテゴリーの誤りはメモリモジユールに
より生ずる。これらの誤りの一部は、例えば、ア
ドレスデコーダが故障しているために生ずるもの
で、恒久性であり、データ語内（モジユール１４
０）又は符号記号内（モジユール３０）内の数ビ
ツトを含む。単一ビツトの誤りは一層しばしば生
ずる。これらの誤りはしばしば一時的な故障とし
て現われる。一方ではこのような誤りは、例え
ば、電荷の漏洩を誘起するα線粒子によりデータ
ビツトが乱されることによるもので真に一時的な
ものである。他方では、データビツト誤りが恒久
的である（例えば、ビツト値が連続してゼロであ
る）が、他のデータビツトに悪影響を及ぼさず、
同じアドレスが時間間隔をおいてアドレスされる
だけであるために、一時的な単一ビツト誤りのよ
うに見える。また、例えば、メモリがビツト構成
になつている時、集積回路の一つが「０」だけを
出力することがある。これは、例えば、関連する
語又は記号の第ｊ番目のビツト位置に半永久的な
誤りがあることに関する。重要なことは、メモリ
モジユール１１０で生ずるこのような単一ビツト
誤りは、リデユーシングエンコーダ４０を通り、
しかも多くはメモリ３０で中間記憶された後、デ
ータ語再構成モジユール６０に提供された時多重
ビツト誤りとして明らかにならないことである。
別の計算機モジユールでの記号誤りと組み合わさ
つているため、このような多重ビツト誤りは通常
は訂正不可能である。このようにして、モジユー
ル１１０内での単一ビツト誤りはエンコーダの出
力側に多くて１ビツト誤りをひき起こす可能性が
ある。また、エンコーダ１２０は更に冗長を導入
することはない。

このようにして符号は各々４ビツトを具える記
号に基づいて定義され、従つて２×４＝８ビツト
から成るデータ語の半分と、４×４＝16ビツトか
ら成る符号語の半分とだけ考慮すればよい。これ
から直接結論されることは、リデユーシングエン
コーダ４０−−−−−４６の生成行列（G₀−−
−−−G₃）はいつも４×８個の行列であり、関
連デコーダ１３０−−−−−１３６の生成行列
〔G₀ ^*-1−−−G₃ ^*-1〕はいつも８×８個の行列で
あることである。第２のエンコーダ１２０−−−
−−１２６での符号化とデコーダ１３０−−−−
−１３６での復号化の時情報が変更されたり、失
なわれたりすることはない。これから結論される
ことは、生成行列〔G₀ ^*−−−G₃ ^*〕は特異であ
つてはならず、積〔G₀ ^*-1〕・〔G₀ ^*〕＝〔Ｉ〕 は恒等行列〔Ｉ〕に等しいことである（他のモジ
ユールにおいても同じようなことが云える）。

我々はまた 〔Ｆ〕＝〔G_i〕・〔G_i ^*-1〕 を定義するが、ここで〔Ｆ〕は式 ａ→＝〔Ｆ〕・ｂ→ に従つてメモリモジユール（１１０_-----１１６）
の内容から関連する符号記号を形成するための生
成行列である。

行列〔Ｆ〕は次のようにして見出されることが
知られている。全ての可能なデータ語（ベクト
ル）ｂ→と各関連する符号ａ→とについての表が知ら
れている時、１個のビツト「１」だけを含む基底
ベクトルｂ→が行列〔Ｆ〕を作る。この時、行例
〔Ｆ〕の各列はこのような基底ベクトルｂ→に関連
する符号記号ａ→により形成される。ｂ→の誤りは
高々ａ→の１個の１ビツト誤りをひき起こすだけで
ある。それ故、行列｛Ｆ｝の各列は１個の「１」
より多くは含まない。

現在の技術状態による装置では、ｋ個（本例で
はｋ＝２）の計算機モジユールの任意の選択の関
連符号記号から各データ語を再構成することがで
きる。リデユーシングエンコーダの生成行列
〔G₀〕−−−〔G_o〕の場合は行列のｋ個の行の各選
択 〔Ｇ〕＝G₀ G₁ 〓 G_o は正方非特異行列を生ずる。

このような行列を 〔G_abc-----〕＝G_a G_b G_c 〓 と称する。

この行列はｋ×ｋ個の係数から成り、これらの
係数はガロア体GF（2^b）の要素であり、ここでｂ
はGF(2)の要素で表わされた記号の長さである
（ビツト）。

行列〔G_abc---〕は逆行列〔G^-1 _abc---〕を有し、
積〔G_abc---〕・〔G^-1 _abc---〕＝〔Ｉ〕は恒等行列に等
しい。明らかに、 〔a^oφφ−−−〕・〔G_abc---〕＝〔G_a〕 であり、ここで〔a^oφφ−−−〕はガロア体GF
（2^bのｋ個の要素から成り、a^oは単位元であり、
φはゼロ元である。これから次式が成立する。

〔G_a〕・〔G^-1 _abc---〕＝〔a^oφ−−−〕 これは次のようにも書ける。

〔G_a〕・〔Ｉ〕・〔G^-1 _abc---〕＝〔a^oφ−−−〕 〔G_i ^*-1〕・〔G_i ^*〕＝〔Ｉ〕であるから次式が成立
する。

〔a_a〕・〔G_i ^*-1〕・〔G_i ^*〕・〔G^-1 _abc---〕＝〔a^o
φ−−
−〕 ここで〔G_i ^*〕・〔G^-1 _abc---〕＝（Ｐ〕と定義する
と、前に〔Ｆ〕＝〔G_a〕・〔G_i ^*-1〕と定義したから 〔Ｆ〕・〔Ｐ〕＝〔a^oφ−−−〕 〔G_i ^*〕と〔G^-1 _abc---〕とは両方とも非特異であ
り、〔P^-1〕も存在し、〔P^-1〕・〔Ｐ〕＝〔Ｉ〕であ
るから、 〔Ｆ〕＝〔a^oφ−−−〕・〔P^-1〕 ここ迄は、〔Ｐ〕はガロア体GF（2^b）（今の場合
ｂ＝４）の要素を形成するｋ×ｋ個（今の場合ｋ
＝２）の係数の行列として考えてきた。しかし、
何等一般性を損なうことなしに、行列〔Ｐ〕及び
他の行列は二項行列と考えることができる（この
場合係数はビツトで形成される）。蓋し、GF（2^b）
の係数はGF(2)の係数を有する随伴行列により置
き換えられるからである。

〔Ｆ〕＝１ ０ ０ ０ ０ ０ ０ ０ ０ １ ０ ０ ０ ０ ０ ０ ０ ０ １ ０ ０ ０ ０ ０ ０ ０ ０ １ ０ ０ ０ ０・〔P^-1〕 行列〔Ｆ〕が係数「０」だけを具える一行を含
む時は、行列〔P^-1〕もこのような行（即ち、最
初の４個の行の一つ）を含む。しかし、これは
〔P^-1〕が特異になるであろうことを意味する。
そして、それは当を得ないことが判明している。
それ故、行列〔Ｆ〕の各行は少なくとも１個の
「１」を含む。いくつかの〔Ｆ〕の自明な選択は
下記の通りである。

〔Ｆ〕＝〔a^o φ〕 (1) 〔Ｆ〕＝〔φ a^o〕 (2) 〔Ｆ〕＝〔a^oa^o〕 (3) (1)の場合は、関連する第２のエンコーダにより
符号化されたデータ語の最初の半分が入出力メモ
リで関連する計算機モジユールのリデユーシング
エンコーダにより形成さるべき符号記号にコピー
されることを意味する。

(2)の場合は他方の半分のデータ語が入出力メモ
リで関連する符号記号にコピーされる。これらの
２個の場合はコピーされた半分内のビツト誤りが
符号記号内のビツト誤りに変換されるが、コピー
されない半分内のビツト誤りは符号記号内の情報
に影響しない。従つて、関連するプロセサモジユ
ールはコピーされない半分に周期的なテストを行
なうことができない。同じように、変数ｎ（モジ
ユールの数、本例では４）、ｋ（データ語内のデー
タ記号の数）、及びｂ（記号内のビツトの数、本例
では４）の他の値に対し、行列〔Ｆ〕の他の構成
も見出すことができる。

上述したところから明らかなように〔G_i〕行列
は第２のエンコーダ生成行列を満足する。この行
列に対しては 〔G_i ^*〕が非特異で、 〔G_i ^*-1〕・〔G_i〕＝〔Ｆ〕 であり、ここで〔Ｆ〕はガロア体GF(2)の係数を
有する行列であり、各行が少なくとも１個の
「１」を含み、各列が高々１個の「１」を含む。
この場合我々は「随伴行列」という用語を用いる
が、その要素はガロア体GF(2)から選択される。

ここで(1)の場合の一連の生成行列を一例として
与える。(2)の場合の対応する行列を導き出すこと
は極めて初等的である。第２図は関連する符号に
対する生成行列〔Ｇ〕の一例を示す。この生成行
列は既に一例として前の本願人のオランダ国特許
願第8104342号に挙げられており、この特許顔明
細書を参考文献としてここに含める。第３図は関
連するリデユーシングエンコーダ、第２のエンコ
ーダ及びデコーダに対する個々の生成行列を示
す。

上述したところから結論されることは〔G_i〕・
〔G_i ^*-1〕＝〔a^o φ〕である。これから行列〔G_i ^*〕
の第１行は行列〔G_i〕の第１列に等しくなければ
ならないことが結論される。行列〔G_i ^*〕の一段
下（第２）の列はこの行列が特異にならないよう
に選ばねばならない。しかし、これは前述したオ
ランダ国特許願で列〔a^o φ〕又は〔φ a^o〕に
より定義されている符号の範囲内で達成できるこ
とが判明している。しかし、注意すべきことはこ
れらが唯一つの方法ではないことである。しか
し、上述した方法は容易に実行できる。そしてこ
れから直接デコーダの生成行列が導びかれる。

次に前記(3)の場合を考察する。ここでは、符号
記号がビツト形式で、入出力メモリで語の第１の
半部と第２の半部との内容をモジユロー２加算す
ることにより形成される。このようにして入出力
メモリ内の各ビツト誤りが関連する符号記号に重
ね合わされる。しかし、今度は全入出力メモリが
プロセサモジユール２０−−−−−２６によりテ
ストできるという利点を有する。第４図はリデユ
ーシングエンコーダ、第２のエンコーダ及びデコ
ーダの生成行列を示す。そして下記のことがあて
はまる。

〔G_i〕・〔G_i ^*-1〕＝〔a^oa^o〕又は 〔G_i〕＝〔a^oa^o〕・〔G_i ^*〕 部品を節約するために、行列〔G_i ^*〕の第１行
は再び〔φ a^o〕及び〔a^o φ〕から選ぶことが
できる。第２の場合は 〔G_i〕＝〔G_i1G_i0〕 ＝〔a^oa^o〕・a^o φ aⁱ a^j であり、これから次のことが結論される。

G_i1＝a^o＋aⁱ aⁱ＝G_i1＋a^o G_i0＝a^j a^j≠０であれば、〔G_i〕は特異ではなく、何の
問もない。他方、G_i0＝φの時は、値〔φ a^o〕
を〔G_i ^*〕の上側に行に対し選択しなければなら
ない。

第５図は変数ｎ，ｋ，ｂの同じ値に対する行列
〔Ｆ〕、従つて生成行列のためのもう一つの方法を
示したものである。行列〔Ｆ〕の場合は、ガロア
体GF（2⁴）の２個の要素に関連する２個の副行列
を具えるだけではない構成を入念に選ぶ。第５図
の第１行の行列〔Ｆ〕は前述した要求を満足す
る。生成行列〔G_i ^*〕の関連する組は下記のよう
にして関連する行列〔G_i ^*-1〕により見出される。

〔G_i〕・〔G_i ^*-1〕＝〔Ｆ〕 これは次のように実行される。〔G_i〕と〔Ｆ〕
とは非特異である〔G_i′〕及び〔F′〕を拡張した
ものであるから、確かに 〔G_i ^*-1〕＝〔G_i′^-1〕・〔F′〕 である。こうして見出された〔G_i ^*-1〕は通常可
能な解の一つにすぎない。ここで〔G₃′〕＝〔a^o
φ〕と仮定する。この行列は前に示したものであ
る。この時〔G₃′〕と〔F′〕とは第５図の第２行
に示したような形となる。〔G₃′〕＝〔G₃′^-1〕であ
り、 〔G₃ ^*-1〕＝〔G₃′^-1〕・〔Ｆ〕であるから、〔F′〕
と同じ行列が得られる。

生成行列〔G₂〕も同じように決められる。

〔G₂〕＝〔φ a^o〕 〔G₂′〕は第５図の第３列に従つて、置換され
た恒等行列として見出すことができる。〔G₂′^-1〕
＝〔G₂′〕であり、前に求まつている行列〔F′〕を
用いて〔G₂ ^*-1〕は第５図の第４列に従つて求め
ることができる。これから第５図の第２行に示し
たような〔G₂ ^*〕を求めることができる。

行列G₁は〔a⁷a¹¹〕である。前に述べた基準、
即ち簡易化の目的に従えば、 〔G₁′〕＝a⁷ a¹¹ a^o φ これから次の逆行列が導びける。

〔G′^-1〕＝φ a^o a⁴ a¹¹ 行列〔Ｆ〕については、前に求めてある値を再
び用いることができる。従つて、行列〔G₁ ^*-1〕
は第６図の第１行に従つて求めることができる。
この第６図は第５図の続きである。生成行列
〔G₁ ^*〕は第６図の第２行に従つて〔G₁ ^*〕＝
〔F′^-1〕・〔G₁′〕として計算される。

最後に行列〔G₀〕＝〔a¹¹a⁷〕であり、 簡単にするためG₀′＝a¹¹ a⁷ a^o φであり、 ここで〔G₀′^-1〕＝φ a^o a⁸ a⁴である。

関連生成行列は、夫々第６図の第３行及び第４
行に示すように 〔G₀ ^*-1〕＝〔G₁′^-1〕・〔Ｆ〕及び 〔G₀ ^*〕＝〔F′^-1〕・〔G₀′〕 から見出される。

【図面の簡単な説明】

第１図は本発明に係るマルチプロセサ計算機装
置のブロツク図、第２図は第１図に示した装置で
使用される誤り訂正符号の生成行列の一例を示す
説明図、第３図は第１の場合の第２図に示した、
リデユーシングエンコーダ、第２のエンコーダ及
びデコーダの別個の生成行列を示す説明図、第４
図は第２の場合のこれらの生成行列の説明図、第
５図及び第６図は行列〔Ｆ〕及びその結果生成行
列を示す説明図である。 ２０，２２，２４，２６…プロセサモジユー
ル、３０，３２，３４，３６…局所メモリ（モジ
ユール）、４０，４２，４４，４６…リデユーシ
ングエンコーダ、５０，５２，５４，５６…レジ
スタ、６０，６２，６４，６６…データ語再構成
モジユール、８０，８２，８４，８６…接続要
素、９０，９２，９４，９６…データチヤネル、
１００，１０２，１０４，１０６…入出力プロセ
サ、１１０，１１２，１１４，１１６…メモリ、
１４０，１４２，１４４，１４６…接続要素。

Claims (1)

1. 【特許請求の範囲】 １ ｎ個の同期をとつて制御され、並列に作動す
   る計算機モジユールを具え、これらの計算機モジ
   ユールの各々が自己の誤り分離区域内に置かれ、
   各計算機モジユールが下記のもの、即ち、 − プロセサモジユールと； − このプロセサモジユールの第１データ接続部
   に接続されている第１データチヤネルと； − 受信されたデータ語から符号記号を形成する
   ために前記第１データチヤネルに接続され、ｋ
   個のデータ記号を具えるデータ語に基づいて、
   ２個以上の符号記号を同時に訂正できる能力を
   具える符号のｋ＋１≦ｎ＜3k個の符号記号か
   ら成る符号語を形成するリデユーシングエンコ
   ーダと； − このリデユーシングエンコーダのデータ出力
   端子に接続されたデータ入力端子と、前記プロ
   セサモジユールに接続されたアドレス入力端子
   と、データ出力端子とを具えるメモリモジユー
   ルと； − 相互接続回路網を介して、前記メモリモジユ
   ールの前記データ出力端子に接続され、各計算
   機モジユールから符号語の関連符号記号を受取
   り、これからデータ語を構成し、前記第１デー
   タ接続部と前記データチヤネルとに接続される
   データ出力端子を具え、前記第１データチヤネ
   ルが外部のデータ入出力に対する第２データ接
   続部も具えるデータ語再構成モジユール； とを具えるマルチプロセサ計算機装置において、
   各計算機モジユールがまた下記のもの、即ち、 − 前記第２データ接続部と直列に接続され、周
   辺装置に対する第３データ接続部を具える第２
   データチヤネルと； − 前記リデユーシングエンコーダの生成行列
   （G_i）がデータビツトを２個以上の符号ビツト
   に重ね合わせる時、第２の非リデユーシングエ
   ンコーダと、この第２のエンコーダに関連する
   デコーダとを介して第２データチヤネルに接続
   され、少なくともリデユーシングエンコーダが
   １個のデータビツトを２個以上の符号ビツトに
   重ね合わせる場合は、このリデユーシングエン
   コーダの生成行列（G_i）と、第２のエンコーダ
   の生成行列（G_i ^*）と、デコーダの生成行列
   （G_i）と、デコーダの生成行列（G_i ^*-1）との間
   に下記の関係、即ち、［G_i ^*］・［G_i ^*-1］＝［Ｉ］，
   恒等行列； ［Ｆ］＝［G_i］・［G_i ^*-1］ が存在し、ここにおいてビツトから成るものと
   して書かれた［Ｆ］の各列が多くて１個の
   「１」を有し、残りが全て「０」で、［Ｆ］の各
   行が１個以上の「１」を有し、関連する計算機
   モジユール内で入出力メモリで符号化されたデ
   ータ語の一ビツトがこのデータ語から形成され
   る得る符号記号の高々一ビツトの上に重ね合わ
   される入出力メモリモジユール； とを具えることを特徴とするマルチプロセサ計算
   機装置。 ２ 符号の誤り訂正能力が１個以上の符号記号内
   に１個以上の任意の誤りベクトルを有するように
   したことを特徴とする特許請求の範囲第１項記載
   のマルチプロセサ計算機装置。 ３ データ語再構成モジユールが異なる訂正能力
   を具える２個以上の選択的に活性化できる動作モ
   ードを有することを特徴とする特許請求の範囲第
   １項又は第２項に記載のマルチプロセサ計算機装
   置。 ４ 行列［Ｆ］の各行が正確に１個の「１」を具
   えるようにしたことを特徴とする特許請求の範囲
   第１，２又は３項のいずれかに記載のマルチプロ
   セサ計算機装置。 ５ 行列［Ｆ］の各列が正確に１個の「１」を具
   えるようにしたことを特徴とする特許請求の範囲
   第１項ないし第３項のいずれかに記載のマルチプ
   ロセサ計算機装置。 ６ マルチプロセサ計算機装置で使用される計算
   機モジユールであつて、該モジユールが下記のも
   の、即ち、 − プロセサモジユール２０と； − このプロセサモジユールによつてアドレスさ
   れるメモリモジユール３０と； − ｋ個の記号データ語をプロセサモジユールと
   双方向に通信するための第１データチヤネル７
   ０と； − この第１データチヤネルによつて供給される
   ｋ個の記号データ語を受信し、この受信したデ
   ータ語から２個以上の各符号記号の誤りを同時
   に訂正できる能力を具える符号に基づいている
   ｎ個（ここにｎ＞ｋ）の記号符号語の符号記号
   を発生して前記メモリモジユールに与えるリデ
   ユーシングエンコーダ４０と； − 前記メモリモジユールから、或る特定の符号
   語を構成するｎ個の記号の内のいずれかを受信
   するためのインターフエース手段５０を有して
   いるデータ語再構成モジユール６０に至るチヤ
   ネルであつて、前記データ語再構成モジユール
   から前記第１データチヤネルに与える別のデー
   タ語を発生させるために設けられる相互接続回
   路網； とを具える計算機モジユールにおいて、当該モジ
   ユールがまた下記のもの即ち、 − 周辺装置に対してインタフエースするために
   前記第１データチヤネルに直列に接続する第２
   の双方向データチヤネル９０と； − 前記リデユーシングエンコーダの生成行列Ｇ
   (i)がデータビツトを２個以上の符号ビツトに重
   ね合わせる時、第２の非リデユーシングエンコ
   ーダ１２０によつてデータが送り込まれ、次い
   で第３デコーダ１３０を介してデータを第２デ
   ータチヤネルに送り込む入出力メモリモジユー
   ル； とを具え、第２エンコーダの生成行列［G_i ^*］と、
   デコーダの生成行列［G_i ^*-1］との間に下記の関
   係、即ち ［G_i ^*］・［G_i ^*-1］＝［Ｉ］，恒等行列； ［Ｆ］＝［G_i］・［G_i ^*-1］ が存在し、ここにおいてビツトから成るものとし
   て書かれた［Ｆ］の各列が多くて１個の「１」を
   有し、残りが全て「０」で、［Ｆ］の各行が１個
   以上の「１」を有し、関連する計算機モジユール
   内で入出力メモリで符号化されたデータ語の一ビ
   ツトがこのデータ語から形成され得る符号記号の
   一ビツトの上に重ね合わされるようにしたことを
   特徴とするマルチプロセサ計算機装置で使用され
   る計算機モジユール。