JP2512666B2

JP2512666B2 - 誤り検査／訂正機能を有するコンピュ―タ・システム

Info

Publication number: JP2512666B2
Application number: JP4243293A
Authority: JP
Inventors: ケヴィン・ジー・クレイマー; ジーン・ジェイ・ガウデンツィ; ティモシー・ジェイ・ルイ; ダリル・シー・クローマー; ポール・シー・キング
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 1991-10-31
Filing date: 1992-09-11
Publication date: 1996-07-03
Anticipated expiration: 2011-07-03
Also published as: EP0540450A1; DE69220452D1; US5313475A; EP0540450B1; JPH06324951A

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、全般的には、デジタル
・コンピュータ用の誤り検出／訂正方式に関し、具体的
には、パーソナル・コンピュータ（ＰＣ）のメモリ・シ
ステムに特に有用な誤り訂正コード（ＥＣＣ）機能と、
ＥＣＣとパリティ・プロトコルの間の変換能力をもたら
すパリティ・インターフェース方式とに関する。

【０００２】

【従来の技術】データ保全性とシステム信頼性は、すべ
てのコンピュータ・システムにとって重要な問題であ
る。その結果、許容可能な水準のデータの誤り検出また
は誤り訂正またはその両方を確実に行うための様々な方
式が開発されてきた。たとえば、パリティ・ビットを使
用して、有限の数のデータ・ビット中に発生する単一ビ
ットの誤りを検出することができる。様々なデータ保全
性方式は、コンピュータ・システム内の特定の分野に特
に適している。たとえば、誤り訂正コード（ＥＣＣ）方
式は、ＥＣＣの訂正能力が半導体メモリに関連する誤り
の確率の高さと結合されているために、メモリとのイン
ターフェースに非常に有用である。ＥＣＣ方式は、しば
らくの間メインフレーム・コンピュータ・システムで使
用されてきた。

【０００３】データ保全性を高める必要が生じるにつれ
て、パーソナル・コンピュータ（ＰＣ）などの小型シス
テムが、データを記憶しメモリから検索する際のパリテ
ィ方式に代わって、独立型誤り訂正コード（ＥＣＣ）機
能を使用するようになってきた。ＥＣＣは、データをメ
モリに記憶する前に複数の検査ビットをデータに追加す
ることによって、単一（または複数）の誤り訂正と、複
数の誤りの検出という追加の保護を与える。これらの検
査ビットは、データ・ビットと共に、メモリから読取り
の後に復号されて、データ保全性を高める。

【０００４】メモリに対するＥＣＣバッファの既存の方
法では、通常は３２ビットである大きなデータ・ワード
に対する検査ビットの生成と検査を行う。ところが、Ｐ
Ｃの多くの構成要素は、８ビットまたは１６ビット単位
のデータしか送受できず、３２ビットのマイクロプロセ
ッサでも、通常はメモリと３２ビット・セグメントで通
信することはしない。したがって、関連する検査ビット
の保全性を維持しながら、可変８ビット（バイト）長の
ワードを書き込むことが必要である。

【０００５】３２ビットＥＣＣ方式では、データと共に
記憶される検査ビットは、３２ビット全体に基づいて生
成される。このため、データ・ビットが１ビットだけ変
更された場合でも、検査ビットのすべてを再生成する必
要がある。したがって、１バイトのデータをメモリに書
き込む必要がある場合には、まず４バイトのダブル・ワ
ード全体を読み取り、検査し、訂正しなければならず、
新規の８ビットを置換した後に、４バイトをすべて、適
当な新規検査ビットと共にメモリに再書込みしなければ
ならない。２バイトまたは３バイトのデータをメモリに
書き込む必要がある場合も同様である。これを、部分書
込みまたは読取／修正／書込動作と称する。

【０００６】米国特許第４８８４２７１号明細書には、
誤り発生時訂正方式を使用した、読取／修正／書込の問
題を処理する方法が記載されている。この方法では、未
訂正のデータに基づいて検査ビットを生成した後に、そ
のデータが誤っていることが判った場合には検査ビット
を再生成する。これには、誤りのあるデータを処理する
ために"長"、誤りのないデータを処理するために"短"の
読取／修正／書込サイクル、ならびに２種類の読取りサ
イクルが必要である。この手法には、動作が比較的複雑
であるという問題がある。さらに、誤り発生時訂正方式
を用いると、誤りが存在するか否かをＥＣＣ論理回路が
判断している間に、データ処理が開始できる。これに
は、誤りが発生した時には、プロセッサがバックアップ
して、破壊されたデータを捨てなければならないという
欠点がある。

【０００７】米国特許第４３１９３５６号明細書には、
周期的に検査を行い、それ自体から誤りを除去するメモ
リが記載されている。この発明は、異なる数のバイトか
らなるワードで通信する可能性のある様々な他の構成要
素とメモリのインターフェースという問題に対処してい
ない。

【０００８】米国特許第４８５２１００号明細書には、
米国特許第４８８４２７１号明細書と同様に、誤り発生
時訂正方式に多重ＥＣＣサブブロックを組み込んだ、誤
り訂正／検出方法が記載されている。米国特許第４８５
２１００号明細書は、米国特許第４３１９３５６号明細
書と同様に、異なる数のバイトからなるワードで通信す
る可能性のある様々な他の構成要素とメモリのインター
フェースという問題には対処していない。さらに、米国
特許第４８５２１００号明細書は、単一のＥＣＣユニッ
トを使用して、様々な数のバイトからなるデータを処理
する。米国特許第４８５２１００号明細書の第５欄に
は、様々な理由から、１つのＥＣＣユニットをデータの
各サブブロック専用にすることが記載されている。米国
特許第４８５２１００号明細書の手法は、バイト数の変
化するワードを記憶するという問題に対処するのに使用
できるはずではあるが、ビット経路の数に関する過度の
オーバーヘッド、したがってコストと空間の故に、通常
は実行不可能である。

【０００９】ＥＣＣ機能は、メモリへの読み書きのため
に実施することができるが、多くのコンピュータ・シス
テム、特にＰＣでは、他の用途（システム・バスが特に
顕著）にパリティ検査を使用する。１つのシステム内で
複数の保全性プロトコルを使用する時には、インターフ
ェースが、異なるプロトコル間の変換能力を提供しなけ
ればならない。通常、このようなインターフェースに
は、別々のパリティとＥＣＣ排他的論理和（ＸＯＲ）ツ
リーが必要であり、その結果、信号遅延がもたらされ、
高価なシリコン表面積を消費することになる。

【００１０】

【発明が解決しようとする課題】本発明の目的は、余分
な構成要素なしに、高速で、システム・バスを最小限し
か使用しない部分書込み機能を、ＥＣＣモジュール内で
実現することである。

【００１１】本発明の他の目的は、改良されたパリティ
／ＥＣＣプロトコル・インターフェースを提供すること
である。

【００１２】

【課題を解決するための手段】本発明の１態様によれ
ば、従来技術の解決策のオーバーヘッドなしに、システ
ム・バスを最小限しか使用しないで、バイト長の変化す
るデータをメモリに書込めるようにする、改良されたＥ
ＣＣシステムが提供される。

【００１３】部分書込み機能は、無修正データの処理が
最小限になるように内部多重化を使用することによって
達成される。これは、ＥＣＣ論理回路内で、メモリから
読み取られたデータのうちの選択されたバイトを新規バ
イトで直接にオーバーレイすることによって行われる。

【００１４】本発明の別の態様によれば、パリティの生
成と検査を簡単にするのに適したＥＣＣコードが選択さ
れる。これは、所望のパリティ方式に対応するデータ・
ビットのグループ化を含むコードを選択することによっ
て行われる。ＥＣＣＸＯＲツリーを、パリティ検査と
誤り訂正復号を同時に行えるように修正し、これによっ
て、インターフェース内に２組のＸＯＲツリーが必要で
はないようにする。

【００１５】

【実施例】ここで図面、具体的には図１を参照すると、
パリティ・プロトコルがシステム・バス上で実施され、
ＥＣＣプロトコルがメモリ・バス上で実施される、コン
ピュータ・システムが示されている。具体的に言うと、
Intel 80386、80486またはMotorola 68030、68040など
の３２ビットのマイクロプロセッサ１０が、３２ビット
・システム・バス１２に接続される。たとえばフロッピ
・ディスク制御ボードなどの８ビット構成要素１４は、
システム・バス１２に接続され、たとえばビデオ・ディ
スプレイ・アダプタなどの１６ビット構成要素１６は、
やはりシステム・バス１２に接続される。また、ファク
シミリ／モデム複合アダプタやハード・ドライブ制御装
置など、８ビットまたは１６ビットの他の構成要素（図
示せず）も、システム・バス１２に接続できる。

【００１６】システム・バス１２は、専用の３２ビット
・メモリ・バス１８に接続され、これによって、ランダ
ム・アクセス・メモリ（ＲＡＭ）２０へのデータの読み
書きが行われる。これら２本のバスの間の接続は、パリ
ティ・インターフェース２２と３２ビットＥＣＣ論理回
路２４を介する。以下の説明から明らかになるように、
本発明は、パリティ・インターフェース２２の機能とＥ
ＣＣ論理回路２４の機能を単一のユニット内で組み合わ
せ、冗長な論理回路とオーバーヘッドを取り除き、これ
によって、高価なシリコン表面積を節約し、動作速度を
向上させる。

【００１７】メモリ・バス１８用のＥＣＣプロトコル
は、３２ビットのデータ・ビットと７ビットの検査ビッ
トであり、一方、システム・バス１２用のパリティ・プ
ロトコルは、３２ビットのデータ・ビットと４ビットの
パリティ・ビットである。このシステムでは、システム
・バス１２に接続された各構成要素は、パリティ・イン
ターフェース２２を含めて、システム・バス１２にデー
タを送る時にパリティを生成し、システム・バス１２か
らデータを受け取る時にパリティを検査しなければなら
ない。

【００１８】３２ビット・バスの場合、通常は、４つの
３段排他的論理和（ＸＯＲ）ツリーを使用して、データ
の１バイト毎に１ビットずつ計４ビットのパリティ・ビ
ットを生成し、検査する。このようなツリーの１つを図
２に示す。このツリーは、７つのＸＯＲゲートと、いく
つかの追加の制御論理回路（図示せず）を含む。このよ
うなパリティ回路は、当業者には周知であり、したがっ
て、詳細に説明する必要はない。ここでは、データ・ビ
ットのグループに対するパリティのオーバーヘッドが、
追加の論理回路に必要なシリコン面積と、ＸＯＲゲート
・ツリーによるパリティ・ビットの生成および検査の際
の遅延であることだけを指摘しておく。

【００１９】図３は、３２ビットのデータ・ビットと７
ビットの検査ビットからなるＥＣＣコードの実施態様を
示す図である。このコードは、すべての単一ビット誤り
を訂正する能力と、すべての２ビット誤りを検出する能
力を有する。これを達成するため、７つの４段ＸＯＲツ
リー２６を使用して、７ビットの検査ビットを生成す
る。各ＸＯＲツリーは、３２ビットのデータ・ビットの
重なり合うサブセットからの入力を有する。このサブセ
ットは、各ビットごとに独自の包含パターンをもたら
す。メモリからの読取り中に、７つのＸＯＲゲート２７
内で、７ビットの受け取った検査ビットを７つの４段Ｘ
ＯＲツリー２６の出力と比較して、誤りが存在するか否
かを判定する。ＸＯＲゲート２７は、図を簡単にするた
めそのうちの１つだけを図示してある。その後、シンド
ロームと称するこの結果と、インバータ群２８（やは
り、そのうちの１つだけを図示）からのその補数を、３
９個の７入力ＡＮＤゲート３０₀〜３０₃₈によって復号
して、正確なビット誤りを突きとめる。誤りのあるデー
タ・ビットは、復号中の１つのＡＮＤゲート３０_i（０
≦ｉ≦３１）の出力の論理"１"で識別され、当該の訂正
用ＸＯＲゲート３２0〜３２31によってビット反転され
る。訂正用ＸＯＲゲート３２0〜３２31の出力は、訂正
済みのデータである。

【００２０】７つのＸＯＲゲート２７の出力は、７入力
のＯＲゲート３３に入力される。このＯＲゲート３３
は、訂正可能であるか否かにかかわらず、誤りが検出さ
れたことをシステムに知らせる出力を供給する。したが
って、全ビット０のシンドロームは、誤りがないことを
示す。

【００２１】ＡＮＤゲート３０₀〜３０₃₈の出力は、３
９ビット（３２ビットのデータ・ビットと７ビットの検
査ビット）のＮＯＲゲート３４に入力される。ＮＯＲゲ
ート３４からの論理"１"出力は、一致する訂正可能な誤
り復号パターンが検出されなかった（すなわち、ＡＮＤ
ゲート３０_i（０≦ｉ≦３８）のどれも、論理"１"を出
力しなかった）ことを反映する。ＮＯＲゲート３４から
の論理"１"出力は、ＡＮＤゲート３６をイネーブルす
る。その後、誤りが検出されたことがＯＲゲート３３の
論理"１"出力によって示された場合、ＡＮＤゲート３６
は、論理"１"を出力して、訂正不能誤りをシステムに報
告する。メモリへの書込み中は、検査ビットが、７つの
４段ＸＯＲツリー２６によって生成され、データと組み
合わされるだけである。

【００２２】図４は、パリティを使用するシステム・バ
スと、ＥＣＣを実施したメモリ・バスの間でインターフ
ェースを行う従来の方法を示す図である。システム・バ
ス１２（図４ではバス"１"と記す）とメモリ・バス１８
（図４ではバス"２"と記す）の間に、２組のＸＯＲツリ
ーがある。パリティ論理回路４０は、図２に示した種類
の４つのＸＯＲツリーと、関連する論理回路とを備え
る。３２ビットがデータ、４ビットがパリティの３６ビ
ットが、システム・バス１２とパリティ論理回路４０の
間で転送される。ＥＣＣ論理回路４２は、７つのＸＯＲ
ツリーと、図３に示した種類の関連する論理回路とを備
える。３２ビットがデータ、７ビットが検査ビットの３
９ビットが、メモリ・バス１８とＥＣＣ論理回路４２の
間で転送される。

【００２３】バス"２"（すなわちメモリ・バス１８）か
らバス"１"（すなわちシステム・バス１２）への転送中
に、下記のことが行われる。

【００２４】１）３２ビットのデータ・ビットと７ビッ
トの検査ビットを、バス"２"から取り、ＥＣＣ論理回路
４２を構成するＸＯＲツリーのグループおよび論理回路
に送る。ＸＯＲツリー群は、検出可能な誤りがそのデー
タ内に存在するか否かを判定する。

【００２５】２）単一ビット誤りを訂正する。誤りフラ
グを用いて、バス"２"からのデータに含まれる、単一ビ
ット誤りと２ビット誤りのすべてならびに検出可能な多
重ビット誤りについて、システムに知らせる。

【００２６】３）３２ビットの訂正済みデータ・ビット
を、パリティ論理回路４０を構成するＸＯＲツリーの第
２の組に経路指定する。その後、データの８ビット（１
バイト）毎に、１ビットのパリティ・ビットを生成す
る。

【００２７】４）３２ビットのデータ・ビットと４ビッ
トのパリティ・ビットを、バス"１"に送る。

【００２８】バス"１"からバス"２"への転送に、同様の
手順が必要である。ただし、この場合は、パリティ誤り
フラグを用いて、検出されたパリティ誤りについてシス
テムに知らせる。図４に示すように、この従来の手法で
は、２組のＸＯＲツリーが必要であり、各ＸＯＲツリー
に関連して有限の遅延が生じる。

【００２９】本発明には、基本的に２つの態様がある。
第１の態様は、図１に示したコンピュータ・システムで
の部分書込み機能または読取／修正／書込機能の問題で
ある。図５は、部分書込み機能を実施する従来技術の方
法の例を示す。システム・バス１２とメモリ・バス１８
の間のインターフェースは、４つの８ビット両方向（Ｂ
ＩＤＩ）バッファ４４、４６、４８、５０を備える。さ
らに、３２ビットのＥＣＣ論理回路２４は、前述したよ
うにメモリ・バス１８に接続される。ＥＣＣ論理回路２
４は、たとえば、メモリから４バイトを読み取り、誤り
を訂正または指示し、変更中でないデータだけを専用の
メモリ・バス１８に送り返す。１バイトのデータを書き
込もうとする８ビット構成要素１４は、このデータをシ
ステム・バス１２の適当な線上に置く。４つの８ビット
ＢＩＤＩバッファ４４、４６、４８、５０は、その後、
活動モードに置かれ、あるいはトライステート・モード
に保持され、その結果、データの新規バイトが、無変更
の３バイトと共に、ＥＣＣ論理回路２４の入出力（Ｉ／
Ｏ）ポートに現れる。ＥＣＣ論理回路は、その後、その
データを読み込み、新規の検査ビットを生成し、その組
合せをＲＡＭ２０に書き込む。マイクロプロセッサ１０
から、またはたとえばシステム・バス１２に接続された
１６ビット構成要素によって、変更中の２バイトまたは
３バイトのデータについてにも、同じことが行える。

【００３０】この従来技術の欠点の１つは、４つの８ビ
ットＢＩＤＩバッファ４４、４６、４８、５０によるコ
ストと遅延の増加である。これらは不要であると主張す
ることもできるが、この例でこれらの構成要素がない
と、どのメモリ・アクセスの間にも、システム・バス１
２の長時間の停止が発生するはずである。また、この方
式には、訂正済みのデータ・バイトをＥＣＣ論理回路２
４に読み込めるようにするため、専用のメモリ・バス１
８まで移動する際に追加の遅延が生じる。

【００３１】図６は、本発明の第１の態様による改良さ
れたＥＣＣ論理回路の好ましい実施例を詳細に示す。両
方向性メモリ・バス１８の３２本のデータ・ビット線
が、レシーバ・ブロック５２とドライバ・ブロック５４
に接続される。レシーバ・ブロック５２からの３２本の
データ・ビット線は、１組のＸＯＲツリー５８と復号訂
正論理回路６０に接続される。以下で詳細に説明するよ
うに、ＸＯＲツリー５８は、７つのツリーを備え、その
うち４つはパリティ・ビットと検査ビットの両方を生成
し、残りの３つは検査ビットだけを生成する。

【００３２】メモリ・バス１８の７本の検査ビット線
も、同様に、レシーバ・ブロック６２とドライバ・ブロ
ック６４の両方に接続される。レシーバ・ブロック６２
の出力は、ＸＯＲツリー５８に供給され、ＸＯＲツリー
５８の出力は、復号訂正論理回路６０に供給される。復
号訂正論理回路６０は、５つの出力を有する。１本の出
力は、トライステート・レシーバ・ブロック６６への３
２本のデータ・ビット線を含む。第２の出力は、ドライ
バ・ブロック６４への７本の検査ビット線を含む。さら
に、単一誤りドライバ７０への誤り出力と、多重誤りド
ライバ７２への誤り出力の、２つの誤り出力がある。ま
た、パリティ生成検査論理回路７５からの出力に応答し
てシステム・バス１２にパリティ誤りフラグを出力す
る、パリティ誤りドライバ７４がある。パリティ生成検
査論理回路７５については、以下で図１０を参照して詳
細に説明する。パリティ生成検査論理回路７５は、復号
訂正論理回路６０からの４つのパリティ訂正出力と、Ｘ
ＯＲツリー５８からの４つのパリティ出力を受け取り、
レシーバ・ブロック７６およびドライバ・ブロック７７
を介して、システム・バス１２上の４本のパリティ線と
通信する。

【００３３】システム・バス１２側では、両方向性シ
ステム・バス１２の３２本のデータ・ビット線がトライ
ステート・レシーバ・ブロック７８の入力およびトライ
ステート・ドライバ・ブロック７９の出力に、各々、接
続される。このドライバ・ブロック７９の入力は、前記
レシーバ・ブロック６６（内部レシーバとも呼ぶ）の出
力に接続される。システム・バス１２に接続されたレシ
ーバ・ブロック７８の出力からの３２本のデータ・ビッ
ト線は、メモリ・バス１８に接続されたレシーバ・ブロ
ック５２からの３２本のデータ・ビット線と並列にＸＯ
Ｒツリー５８に接続される。さらに、レシーバ・ブロッ
ク７８の出力は、メモリ・バス１８に接続されたドライ
バ・ブロック５４の入力にも接続される。

【００３４】部分書込み機能は、下記に従って、メモリ
から読み取ったデータのうちの選択されたバイトを新規
バイトで直接にオーバーレイすることにより内部多重化
を用いて行われる。

【００３５】１）３２ビット幅のデータは、メモリ・
バス１８からレシーバ・ブロック５２を介してＸＯＲツ
リー５８および復号訂正論理回路６０に読み込まれ、そ
こで、システム・バス上に転送されるべきデータ・ビッ
トに対して１バイト当り１ビットの割合でｉ（実施例で
は４）ビットのパリティ・ビット（ＩＢＰ）を発生する
と同時にエラー検出／訂正処理を行なって３２ビット幅
の訂正済データを内部レシーバ・ブロック６６の入力端
に供給する。システム・バス１２に接続されたレシーバ
・ブロック７８および内部レシーバ・ブロック６６の各
出力に接続された３２ビット幅の内部バス８０が設けら
れ、この内部バス上に到来するデータは８ビット（すな
わちバイト）幅のグループでレシーバ・ブロック７８ま
たは６６により排他的に制御される。すなわち、これら
の各レシーバ・ブロック７８および６６は、バイト幅単
位での活動状態に制御するための制御信号の下に、動作
する。したがって、部分書込み動作の間、内部レシーバ
・ブロック６６が、その入力端に到来した訂正済のメモ
リ読み取りデータのうち変更（すなわち更新）を必要と
しないバイト位置に対して、活動状態に制御されゲート
する一方、他のレシーバ・ブロック７８が、前記データ
のうち変更を必要とするバイト位置（すなわち、システ
ム・バス１２から書込むべきバイト）に対して、活動状
態に制御されゲートする。

【００３６】この結果、更新された３２ビット・デー
タがＸＯＲツリー５８および復号訂正論理回路６０へ転
送され、そこでメモリ・バス１８から到来したメモリ読
取りデータの場合と同様に、ｉビット（たとえば４ビッ
ト）のパリティ・ビット（ＩＢＰ）およびｎビット（た
とえば７ビット）のＥＣＣ検査ビットが生成される。こ
の生成されたパリティ・ビット（ＩＢＰ）は、パリティ
・ビット・レシーバ・ブロック７６により受信されたシ
ステム・バス１２からの受信パリティ・ビットに対し
て、パリティ生成検査論理回路７５において比較され、
不一致のときパリティ誤りドライバ７４を介してシステ
ムに対して誤り信号を供給する。他方、比較結果、一致
信号が生成されると、前記生成されたＥＣＣ検査ビット
が検査ビット・ドライバ・ブロック６４を介してメモリ
・バス１８上に出力され、同時に、内部バス８０上の更
新データ・ビットがデータ・ドライバ・ブロックを介し
てメモリ・バス１８上に出力される。

【００３７】この機能のもう１つの改善点は、レシーバ
・ブロック５２、６２、７６およびトライステート・レ
シーバ・ブロック７８がそれぞれ、非常に短い時間の間
に外部のシステム・バスとメモリ・バスを解放するのに
使用できる透過伝送ラッチを含むことである。したがっ
て、本発明の第１の態様は、通常のＥＣＣ読み書きの性
能に全く影響を及ぼさずに、外部の構成要素と遅延の節
約をもたらす。

【００３８】本発明の第２の態様は、パリティ検査プロ
トコルを実施するシステム・バスと、ＥＣＣプロトコル
を実施するメモリ・バスの間のインターフェースに関す
る。３２ビット・データ・バスの場合、通常は、４つの
３段ＸＯＲツリーを使用して、データの１バイト毎に１
ビットずつ計４つのパリティ・ビットを生成し、検査す
る。誤り訂正コード用に７ビットの検査ビットを使用す
ると、図４に示した従来技術の手法では、さらに７つの
４段ＸＯＲツリーを使用しなければならない。したがっ
て、１グループのデータ・ビットに対するパリティとＥ
ＣＣのオーバーヘッドは、追加の論理回路に必要なシリ
コン面積と、ＸＯＲゲート・ツリーによるパリティ・ビ
ットの生成および検査の際の遅延である。この理由か
ら、本発明の第２の態様は、パリティの生成と検査用の
１組と検査ビットの生成と検査用の１組の計２組のＸＯ
Ｒツリーという固有の冗長性を取り除くことを意図した
ものである。

【００３９】本発明の第２の態様によれば、ＥＣＣ検
査ビットの生成に必要な７つのＸＯＲツリーのうち、４
つの各ＸＯＲツリーを共用して、４つのパリティ・ビッ
トと４つの検査ビットをそれぞれ生成し、残りの３つの
ＸＯＲツリーを使用して、検査ビットの残り３ビットを
生成する。４つの組合せＥＣＣ検査ビットのうちの１つ
とパリティ・ビットを生成するＸＯＲツリーの例を、図
７に示す。第１段は、８つのＸＯＲゲート８２₁〜８２₈
を含む。これらのＸＯＲゲートへの入力を、文字Ａない
しＰで示す。第２段は、４つのＸＯＲゲート８４₁〜８
４₄を含み、ＸＯＲゲート８２₁〜８２₈の各対が、ＸＯ
Ｒゲート８４₁〜８４₄に入力を供給する。第３段は、２
つのＸＯＲゲート８６₁および８６₂を含み、やはり、Ｘ
ＯＲゲート８４₁〜８４₄の各対が、ＸＯＲゲート８６₁
および８６₂に入力を供給する。この一方のＸＯＲゲー
ト８６₁の出力は、４バイトのデータのうちの１バイト
に対するパリティ・ビットＩＢＰ（ｉ）（０≦ｉ≦３）
である。したがって、データ入力ＡないしＨがその生成
に関与するパリティ・ビットは、このＸＯＲツリーから
生成されるものだけである。このＸＯＲツリーの第４段
には、１つのＸＯＲゲート８８だけを含む。このＸＯＲ
ゲート８８は、入力としてＸＯＲゲート８６₁と８６₂の
出力を受け取る。ＸＯＲゲート８８の出力は、データ入
力ＡないしＰに対するＥＣＣ検査ビットＴ_n（０≦ｎ≦
６）である。

【００４０】両方の組のＸＯＲツリーの必要をなくすた
め、パリティの生成と検査の作業を簡単にすることがで
きる適当なＥＣＣの組を選択する。これは、所望のパリ
ティ方式に対応する、ＸＯＲツリー内のデータ・ビット
のグループ化を含むコードを選択することによって行わ
れる。図８は、インターナショナル・ビジネス・マシー
ンズ・コーポレーションのチェン（C. L. Chen）および
シャオ（M.Y. Hsiao）によって開発された、そのような
コードの例を示す。

【００４１】図８の各行は、１つのＸＯＲツリーを表
す。"Ｘ"は、対応するツリーに入力されるデータ・ビッ
トを示す。ＸＯＲツリー"１"は、その入力のうちにデー
タ・ビット０〜７を有することに留意されたい。これら
の８ビットは、訂正された後に、システム・バス用のパ
リティ・ビット０を生成するのに使用される。ツリー"
２"は、データ・ビット８〜１５からの入力を有し、こ
れらはパリティ・ビット１に対応する。同様に、ツリ
ー"４"は、パリティ・ビット２を生成するのに必要なビ
ットを含み、ツリー"５"には、パリティ・ビット３を生
成するのに必要なビットを含む。このようなコードが与
えられているものとすると、ＸＯＲツリーのうちのいく
つかを、図７に示すように、それらのそれぞれの中間ノ
ードがデータの所与のバイトに対するパリティ・ビット
を表すように構成することができる。

【００４２】図９は、図３に示したＥＣＣコード実施態
様を修正して、図７に示した４つのＸＯＲツリーを含む
図６のＸＯＲツリー５８で置換したものを示す。３９ウ
ェイのＮＯＲゲート３４が、５つのＮＯＲゲート９０、
９２、９４、９６、９８で置換されていることに留意さ
れたい。最初の４つのＮＯＲゲートはそれぞれ、所与の
バイトの復号機能を実行する８つのＡＮＤゲートからの
入力を有する。

【００４３】図７に示した４つのＸＯＲツリーの出力Ｉ
ＢＰ（ｉ）（０≦ｉ≦３）は、パリティ・ビットでもあ
る。ただし、これらのパリティ・ビットは、必ずしも正
しいとは限らない。データ・ビットのうちのどれかが誤
っている場合には、対応するパリティ・ビットは、未訂
正のデータに基づいて生成され、やはり誤っていること
になる。データは、ＥＣＣＸＯＲツリーに入る時には
まだ訂正されていないことを想起されたい。したがっ
て、データ中の単一ビット誤りが後で訂正される時、パ
リティは、もはやそのデータを正しく反映していない。

【００４４】幸いなことに、ＥＣＣ誤り論理回路のいく
つかの些細な変更によって、別のツリーを使用せずに正
しいパリティを決定することができる。ＮＯＲゲート出
力のそれぞれの論理的な意味は、各出力が、訂正可能な
誤りがデータのそのバイト内で発生したことを示すとい
うことである。その場合には、この信号を使用して、シ
ステム・バス１２上に送出される訂正済みデータを正し
く反映するためにどのパリティ・ビットをビット反転し
なければならないかを決定することができる。

【００４５】図１０は、パリティ生成を完了するのに必
要な論理回路を示す図である。図１０では、ＮＯＲゲー
ト９０、９２、９４、９６から出力される信号ＢＰＥ
（ｉ）（０≦ｉ≦３）を、当該のＸＯＲゲート１００
（図を簡単にするためそのうちの１つだけを図示）によ
って、ＥＣＣＸＯＲツリーからの内部パリティ・ノー
ドＩＢＰ（ｉ）（０≦ｉ≦３）（図７参照）と比較し
て、メモリ・バス１８からシステム・バス１２に転送さ
れる正しいパリティ・ビット出力を生成する。

【００４６】前の議論では、全般的に図１に示したよう
に、メモリ・バス１８からシステム・バス１２への転送
について論じた。１組のＸＯＲツリーだけを使用した、
システム・バス１２からメモリ・バス１８へのデータの
転送は、下記のように要約される。

【００４７】１）３２ビットのデータ・ビットと４ビッ
トのパリティ・ビットをシステム・バスから取り、７つ
のＸＯＲツリーに送る。

【００４８】２）７ビットのＥＣＣ検査ビットと４ビッ
トの内部パリティ・ビットを、同じツリーで同時に生成
する。図７を参照されたい。

【００４９】３）図１０のＸＯＲゲート１０２によっ
て、内部パリティ・ビットと受け取ったパリティ・ビッ
トを比較する。ＸＯＲゲート１０２（やはり４つのうち
の１つだけを図示）は、ＩＢＰ（ｉ）入力と、システム
・バス１２から受け取った対応するパリティ・ビットと
を受け取り、これら２つが同じでない場合には、システ
ム・バス１２からメモリ・バス１８に転送されるパリテ
ィ誤りを生成する。

【００５０】４）ＥＣＣ検査ビットを、３２ビットのデ
ータ・ビットと共にメモリ・バス１８へ送出する。

【００５１】本発明の第２の態様によるパリティ・ルッ
ク・アヘッド機構を使用すると、図４のパリティ論理回
路内に示したＸＯＲツリーが、完全に不要となる。この
結果、インターフェースの性能が大幅に向上し、シリコ
ン表面積および電力の明らかな節約が得られる。別の見
方をすれば、通常のパリティ・システムだけに使用され
るＸＯＲツリーより３つ余分にＸＯＲツリーを設けるだ
けで、完全なＥＣＣ機能を実行することができる。

【００５２】

【発明の効果】従来技術の解決策のオーバーヘッドなし
に、システム・バスを最小限しか使用しないで、バイト
長が変化するデータをメモリに書き込める、改良された
ＥＣＣシステムが提供された。

【図面の簡単な説明】

【図１】本発明がその中で実施される種類の典型的なコ
ンピュータ・システムを示す、一般化したブロック図で
ある。

【図２】典型的な従来技術の排他的論理和（ＸＯＲ）パ
リティ・ツリーを示す論理図である。

【図３】典型的な従来技術のＥＣＣ実施態様を示す、ブ
ロック図兼論理図である。

【図４】典型的な従来技術のパリティ／ＥＣＣインター
フェースを示すブロック図である。

【図５】図１に類似の、典型的な従来技術のパリティ書
込み実施態様を示す、一般化したブロック図である。

【図６】本発明の好ましい実施例による、改良された部
分書込み機能を実施するＥＣＣシステムの詳細なブロッ
ク図である。

【図７】本発明に従って修正されたＥＣＣＸＯＲツリ
ーを示す論理図である。

【図８】本発明の好ましい実施例に従って改良されたイ
ンターフェースを実施するのに使用される、パリティ・
グループ化を伴うＥＣＣコードを示す図表である。

【図９】図８に示したＥＣＣコードに基づく、本発明の
好ましい実施例に従って改良されたＥＣＣ実施態様のブ
ロック図兼論理図である。

【図１０】本発明の好ましい実施例による、パリティの
生成と検査を完了する回路の論理図である。

【符号の説明】

１０マイクロプロセッサ１２システム・バス１４８ビット構成要素１６１６ビット構成要素１８メモリ・バス２０ランダム・アクセス・メモリ（ＲＡＭ）２２パリティ・インターフェース２４ＥＣＣ論理回路２６７つの４段ＸＯＲツリー２７７つのＸＯＲゲート２８インバータ３０７入力ＡＮＤゲート３２訂正用ＸＯＲゲート４０パリティ論理回路４２ＥＣＣ論理回路５８ＸＯＲツリー６０復号訂正論理回路７５パリティ生成検査論理回路

───────────────────────────────────────────────────── フロントページの続き (72)発明者ジーン・ジェイ・ガウデンツィアメリカ合衆国10578、ニューヨーク州パーディス、オークリッジ・ロード（番地なし) (72)発明者ティモシー・ジェイ・ルイアメリカ合衆国33487、フロリダ州ボカ・ラトン、ブランディーワイン・ドライブ 4519番地 (72)発明者ダリル・シー・クローマーアメリカ合衆国33433、フロリダ州ボカ・ラトン、パシフィック・ブールバード 5581番地 3708号 (72)発明者ポール・シー・キングアメリカ合衆国33434、フロリダ州ボカ・ラトン、27番アベニュー、ノース・ウェスト 3198番地 (56)参考文献特開昭61−139846（ＪＰ，Ａ) 特開昭57−203299（ＪＰ，Ａ) 特公昭52−26104（ＪＰ，Ｂ２)

Claims

(57)【特許請求の範囲】

【請求項１】システム・バスに接続されたプロセッサ
と、前記システム・バスと同じデータ幅を有するメモリ
・バスに接続されたメモリと、前記メモリ・バスとの間
で所定バイト数のデータ・ビットおよびｎ桁の誤り検査
・訂正（ＥＣＣと略称する）ビットの送受を行う第１の
ドライバ手段およびレシーバ手段ならびに前記システム
・バスとの間で前記所定バイト数のデータ・ビットおよ
びｉ（ただし、ｎ＞ｉ）桁のパリティ・ビットの送受を
行う第２のドライバ手段およびレシーバ手段を含むイン
ターフェース手段とより成るＥＣＣ機能を有するコンピ
ュータ・システムにおいて、前記インターフェース手段は、前記メモリから読取られたデータ・ビットに対して誤り
検査・訂正処理を行い訂正済データ・ビットを前記第２
のドライバ手段に向けて出力する一方、前記メモリに書
込むべきデータ・ビットに対してｎ桁のＥＣＣビットを
発生して前記第１のドライバに向けて出力する単一のＥ
ＣＣ論理手段と、前記ＥＣＣ論理手段からの訂正済データ・ビットを受信
して前記第２のドライバ手段へ転送するための内部レシ
ーバ手段と、前記内部レシーバ手段および前記第２のレシーバ手段に
接続され、前記メモリに書込むべきデータ・ビットを前
記第１のドライバ手段および前記ＥＣＣ論理手段へ転送
するための内部バスとを含み、前記ＥＣＣ論理手段は、前記内部バスおよび前記第１の
レシーバ手段からの前記所定バイト数のデータ・ビット
のうちの所定の複数のデータ・ビットをそれぞれ受信し
てｎ桁のＥＣＣビットを発生するためのｎ個の排他的論
理和ツリー構造を含み、そのうちのｉ個の各排他的論理
和ツリー構造が、前記所定バイト数のデータ・ビットの
異なるバイトのデータ・ビットおよび他の所定のデータ
・ビットをそれぞれ受信して、前記ＥＣＣビットの発生
と同時に、バイト毎のパリティ・ビットを発生するよう
に接続されており、前記ＥＣＣ論理手段の排他的論理和ツリー構造をパリテ
ィ・ビット発生のためのツリー構造として共用すること
を特徴とする単一のＥＣＣ論理手段を有するコンピュー
タ・システム。