JPH0736717A - 単一記号エラーと単一ビット・エラー検出のためのエラー訂正方法及び装置 - Google Patents
単一記号エラーと単一ビット・エラー検出のためのエラー訂正方法及び装置Info
- Publication number
- JPH0736717A JPH0736717A JP6122178A JP12217894A JPH0736717A JP H0736717 A JPH0736717 A JP H0736717A JP 6122178 A JP6122178 A JP 6122178A JP 12217894 A JP12217894 A JP 12217894A JP H0736717 A JPH0736717 A JP H0736717A
- Authority
- JP
- Japan
- Prior art keywords
- matrix
- code
- parity check
- error
- type
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F11/00—Error detection; Error correction; Monitoring
- G06F11/07—Responding to the occurrence of a fault, e.g. fault tolerance
- G06F11/08—Error detection or correction by redundancy in data representation, e.g. by using checking codes
- G06F11/10—Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's
- G06F11/1008—Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's in individual solid state devices
- G06F11/1012—Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's in individual solid state devices using codes or arrangements adapted for a specific type of error
- G06F11/1028—Adjacent errors, e.g. error in n-bit (n>1) wide storage units, i.e. package error
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F11/00—Error detection; Error correction; Monitoring
- G06F11/07—Responding to the occurrence of a fault, e.g. fault tolerance
- G06F11/08—Error detection or correction by redundancy in data representation, e.g. by using checking codes
- G06F11/10—Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's
-
- H—ELECTRICITY
- H03—ELECTRONIC CIRCUITRY
- H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
- H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
- H03M13/03—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words
- H03M13/05—Error detection or forward error correction by redundancy in data representation, i.e. code words containing more digits than the source words using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits
- H03M13/13—Linear codes
- H03M13/15—Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes
Landscapes
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Quality & Reliability (AREA)
- General Engineering & Computer Science (AREA)
- Algebra (AREA)
- Mathematical Physics (AREA)
- Pure & Applied Mathematics (AREA)
- Probability & Statistics with Applications (AREA)
- Error Detection And Correction (AREA)
- Detection And Correction Of Errors (AREA)
- Techniques For Improving Reliability Of Storages (AREA)
Abstract
(57)【要約】
【目的】 メモリ・アレイの信頼性を向上する。
【構成】 本発明の好適な実施例によれば、大きなクラ
スのコードに対応するタイプＩＩの２進パリティ・チェ
ック・マトリクスを、１チップ当たり多重ビット出力ア
ーキテクチャを使用するメモリ・システムにおけるエラ
ー検出及び訂正により好適な、より大きなパリティ・チ
ェック・マトリクスに変換する機構が提供される。より
詳細には、本符号化方法はタイプＩＩコードで求められ
るよりは少ないが、タイプＩコードの場合よりは多いチ
ェック・ビット要求を示すコードを提供する。特に本発
明のコードは、単一記号エラーの全ての組合わせ及び単
一ビット・エラーを検出することができる。更に本発明
のコードはタイプＩコードにおける全ての訂正及び検出
特性を示すが、全ての単一記号エラーを訂正可能で、全
てのダブル記号エラーを検出可能なタイプＩＩコードの
機能または複雑化を生じない。特に、本発明は、ある記
号ビット・グループからの記号エラー及び異なる記号か
らの別のエラーが存在する状況において発生するタイプ
Ｉコードの弱点を回避する。
スのコードに対応するタイプＩＩの２進パリティ・チェ
ック・マトリクスを、１チップ当たり多重ビット出力ア
ーキテクチャを使用するメモリ・システムにおけるエラ
ー検出及び訂正により好適な、より大きなパリティ・チ
ェック・マトリクスに変換する機構が提供される。より
詳細には、本符号化方法はタイプＩＩコードで求められ
るよりは少ないが、タイプＩコードの場合よりは多いチ
ェック・ビット要求を示すコードを提供する。特に本発
明のコードは、単一記号エラーの全ての組合わせ及び単
一ビット・エラーを検出することができる。更に本発明
のコードはタイプＩコードにおける全ての訂正及び検出
特性を示すが、全ての単一記号エラーを訂正可能で、全
てのダブル記号エラーを検出可能なタイプＩＩコードの
機能または複雑化を生じない。特に、本発明は、ある記
号ビット・グループからの記号エラー及び異なる記号か
らの別のエラーが存在する状況において発生するタイプ
Ｉコードの弱点を回避する。
Description
【０００１】
【産業上の利用分野】本発明は一般にデジタル・コンピ
ュータ・システムのメモリ・アレイに関連して有用なエ
ラー訂正符号化方法に関する。特に、本発明はメモリ構
成がメモリ・アレイ・ユニットから読出される多重ビッ
トを含む状況に適用される。典型的には、こうしたメモ
リ・アレイ・ユニットは個々の回路チップを含む。
ュータ・システムのメモリ・アレイに関連して有用なエ
ラー訂正符号化方法に関する。特に、本発明はメモリ構
成がメモリ・アレイ・ユニットから読出される多重ビッ
トを含む状況に適用される。典型的には、こうしたメモ
リ・アレイ・ユニットは個々の回路チップを含む。
【０００２】
【従来の技術】コンピュータ・メモリ・チップに関連す
るエラー検出及び訂正機構は、チップ回路密度が増加す
るにつれ一層普及し、また望まれつつある。現在及び将
来における一層の回路密度の増加は、様々な種類のメモ
リ・エラーの発生状況を生じる。これらのエラーはα粒
子放射または他の放射により典型的に引起こされる "ソ
フト" 的なエラーと、ハード・メモリ故障状態の両方を
含む。両方のこれらの種類のエラーは、エラー指示とな
る。メモリ・システムにおけるこれらのエラー・リスク
の増加により、メモリ・アレイ構造に記憶されるデータ
の保全性及び信頼性を維持する試みがより重要となって
いる。これは特に、高密度半導体回路チップ・デバイス
にもとづくメモリ・システムにおいて言えることであ
る。
るエラー検出及び訂正機構は、チップ回路密度が増加す
るにつれ一層普及し、また望まれつつある。現在及び将
来における一層の回路密度の増加は、様々な種類のメモ
リ・エラーの発生状況を生じる。これらのエラーはα粒
子放射または他の放射により典型的に引起こされる "ソ
フト" 的なエラーと、ハード・メモリ故障状態の両方を
含む。両方のこれらの種類のエラーは、エラー指示とな
る。メモリ・システムにおけるこれらのエラー・リスク
の増加により、メモリ・アレイ構造に記憶されるデータ
の保全性及び信頼性を維持する試みがより重要となって
いる。これは特に、高密度半導体回路チップ・デバイス
にもとづくメモリ・システムにおいて言えることであ
る。
【０００３】メモリ密度は個々の回路チップ上に配置さ
れるメモリ・セル数を増加したため、単一ビットの情報
よりも多くの情報が１度に任意のメモリ・チップから提
供されるコンピュータ・メモリ・システムの構成がしば
しば望まれる。従って、１チップ当たり多重ビットのメ
モリ・システムがより普及しつつある。こうした状況に
おいて、多重ビットが"記号（symbol）"を表すものと見
なすことがしばしば望ましい。１チップ当たり４ビット
のモジュールを基本とする６４ビット幅のメモリでは、
出力は１６個の４ビット"記号チャンク（symbol chunk
s）" として供給されるものと見なされる。
れるメモリ・セル数を増加したため、単一ビットの情報
よりも多くの情報が１度に任意のメモリ・チップから提
供されるコンピュータ・メモリ・システムの構成がしば
しば望まれる。従って、１チップ当たり多重ビットのメ
モリ・システムがより普及しつつある。こうした状況に
おいて、多重ビットが"記号（symbol）"を表すものと見
なすことがしばしば望ましい。１チップ当たり４ビット
のモジュールを基本とする６４ビット幅のメモリでは、
出力は１６個の４ビット"記号チャンク（symbol chunk
s）" として供給されるものと見なされる。
【０００４】従来、エラー訂正及び検出方法がメモリ回
路及びメモリ構造に適用される場合、符号化方法は一般
にタイプＩ及びタイプＩＩの２つの一般的カテゴリに分
類された。タイプＩコードでは、コードが全ての単一エ
ラーを訂正可能で、全てのダブル・ビット・エラーを検
出可能で、また全ての単一記号エラーを検出可能なよう
に、符号化及び複合化機構が構成される。ここで記号エ
ラーは１チップ当たりｂビットのメモリ・システムから
の最大ｂビットのエラーである。こうしたコードはここ
ではタイプＩコードと呼ばれる。一方、タイプＩＩコー
ドはタイプＩコードが可能な全てのことを実行可能であ
るが、更に全ての単一記号エラーの訂正、及び全てのダ
ブル記号エラーの検出が可能である。
路及びメモリ構造に適用される場合、符号化方法は一般
にタイプＩ及びタイプＩＩの２つの一般的カテゴリに分
類された。タイプＩコードでは、コードが全ての単一エ
ラーを訂正可能で、全てのダブル・ビット・エラーを検
出可能で、また全ての単一記号エラーを検出可能なよう
に、符号化及び複合化機構が構成される。ここで記号エ
ラーは１チップ当たりｂビットのメモリ・システムから
の最大ｂビットのエラーである。こうしたコードはここ
ではタイプＩコードと呼ばれる。一方、タイプＩＩコー
ドはタイプＩコードが可能な全てのことを実行可能であ
るが、更に全ての単一記号エラーの訂正、及び全てのダ
ブル記号エラーの検出が可能である。
【０００５】このように、タイプＩコードでは、単一ビ
ット内で発生する全てのエラーを訂正し、２ビット位置
内において発生する全てのエラーを検出し、またエラー
がｂビットの単一のセット内で発生する限り、全てのエ
ラーを検出する機能を有する。それに対し、タイプＩＩ
コードでは、単一記号内で発生する全てのエラーを訂正
し、また２つの別々の記号内で発生する全てのエラーを
検出することができる。
ット内で発生する全てのエラーを訂正し、２ビット位置
内において発生する全てのエラーを検出し、またエラー
がｂビットの単一のセット内で発生する限り、全てのエ
ラーを検出する機能を有する。それに対し、タイプＩＩ
コードでは、単一記号内で発生する全てのエラーを訂正
し、また２つの別々の記号内で発生する全てのエラーを
検出することができる。
【０００６】しかしながら、タイプＩコードとタイプＩ
Ｉコードとの中間の機能を有する第３のタイプのコード
が必要とされる。こうしたコードはここではタイプＩＩ
Ｉコードと呼ばれる。従って、こうしたコードは単一ビ
ット位置内の全てのエラーを訂正し、２ビット位置内の
全てのエラーを検出し、単一記号（ｂビット）内で発生
する全てのエラーを検出し、更に単一記号エラーの全て
の組合わせ及び別のあるビット位置におけるエラーを検
出することが可能である。従って、ここで定義されるタ
イプＩＩＩコードは、単一記号エラーとある他のビット
位置におけるエラーとの全ての組合わせを検出すること
ができる。それに対し、完全なタイプＩＩコードは、全
ての単一記号エラーを訂正し、全てのダブル記号エラー
を検出することができる。
Ｉコードとの中間の機能を有する第３のタイプのコード
が必要とされる。こうしたコードはここではタイプＩＩ
Ｉコードと呼ばれる。従って、こうしたコードは単一ビ
ット位置内の全てのエラーを訂正し、２ビット位置内の
全てのエラーを検出し、単一記号（ｂビット）内で発生
する全てのエラーを検出し、更に単一記号エラーの全て
の組合わせ及び別のあるビット位置におけるエラーを検
出することが可能である。従って、ここで定義されるタ
イプＩＩＩコードは、単一記号エラーとある他のビット
位置におけるエラーとの全ての組合わせを検出すること
ができる。それに対し、完全なタイプＩＩコードは、全
ての単一記号エラーを訂正し、全てのダブル記号エラー
を検出することができる。
【０００７】タイプＩＩＩコードはＥＣＣ設計者に従来
なかった有力で柔軟なツールを提供するため、こうした
タイプのコードを利用する機能を有することが重要であ
る。特に、タイプＩＩＩコードの存在は、コード設計者
に対し、従来使用可能でなかった技術的判断選択を提供
する。コード設計者、及びメモリ回路保護分野のコード
設計者にとって、タイプＩコードは実施することは安価
ではあるが、メモリ・システムにおいて期待される程度
のエラー訂正及び検出を必ずしも提供しない。これは特
に、マルチユーザ環境がデータ保全性を一層クリティカ
ルなものとする大規模メインフレーム・コンピュータで
使用されるメモリ・システムにおいて言えることであ
る。同様にメモリ保護分野に従事するコード設計者にと
って、タイプＩＩコード化方法は、エラー訂正及び検出
機能を多大に向上するが、それにも関わらず、好適な量
のメモリ・チップ"資源（real estate）" よりも多くを
使用する複雑な回路を必要とする。更に、上述の議論か
ら、多重ビット・メモリ・アーキテクチャに大きく依存
して、あるビット位置における別の単一エラーと一緒
に、単一記号エラーの全ての組合わせを検出する機能が
極めて有利となることが理解される。要するに上述の議
論から、タイプＩＩＩエラー訂正符号化方法が多重ビッ
ト・メモリ・アーキテクチャに特に好適であることが理
解される。
なかった有力で柔軟なツールを提供するため、こうした
タイプのコードを利用する機能を有することが重要であ
る。特に、タイプＩＩＩコードの存在は、コード設計者
に対し、従来使用可能でなかった技術的判断選択を提供
する。コード設計者、及びメモリ回路保護分野のコード
設計者にとって、タイプＩコードは実施することは安価
ではあるが、メモリ・システムにおいて期待される程度
のエラー訂正及び検出を必ずしも提供しない。これは特
に、マルチユーザ環境がデータ保全性を一層クリティカ
ルなものとする大規模メインフレーム・コンピュータで
使用されるメモリ・システムにおいて言えることであ
る。同様にメモリ保護分野に従事するコード設計者にと
って、タイプＩＩコード化方法は、エラー訂正及び検出
機能を多大に向上するが、それにも関わらず、好適な量
のメモリ・チップ"資源（real estate）" よりも多くを
使用する複雑な回路を必要とする。更に、上述の議論か
ら、多重ビット・メモリ・アーキテクチャに大きく依存
して、あるビット位置における別の単一エラーと一緒
に、単一記号エラーの全ての組合わせを検出する機能が
極めて有利となることが理解される。要するに上述の議
論から、タイプＩＩＩエラー訂正符号化方法が多重ビッ
ト・メモリ・アーキテクチャに特に好適であることが理
解される。
【０００８】
【発明が解決しようとする課題】本発明の目的は、メモ
リ・アレイの信頼性を向上することである。
リ・アレイの信頼性を向上することである。
【０００９】本発明の別の目的は、複雑性及びコストの
点で、タイプＩコードとタイプＩＩコードの中間に位置
する２進情報のための符号化方法を提供することであ
る。
点で、タイプＩコードとタイプＩＩコードの中間に位置
する２進情報のための符号化方法を提供することであ
る。
【００１０】更に本発明の別の目的は、出力記号がｂビ
ットのチャンクにグループ化されるメモリ・アレイ構造
に特に好適なエラー訂正符号化方法を使用することであ
る。
ットのチャンクにグループ化されるメモリ・アレイ構造
に特に好適なエラー訂正符号化方法を使用することであ
る。
【００１１】更に本発明の別の目的は、Reed-Solomonコ
ードの特性を改良することである。
ードの特性を改良することである。
【００１２】更に本発明の別の目的は、タイプＩＩＩコ
ードにもとづくエラー訂正及び検出方法を提供すること
である。
ードにもとづくエラー訂正及び検出方法を提供すること
である。
【００１３】最後に本発明の目的は、単一記号エラーの
全ての組合わせを検出し、同時に、別のコードワード内
で発生する単一ビット・エラーを検出することである。
全ての組合わせを検出し、同時に、別のコードワード内
で発生する単一ビット・エラーを検出することである。
【００１４】
【課題を解決するための手段】本発明の好適な実施例に
よれば、Ｎビットのブロック内で発生し、各々がＭビッ
トのＳ個のサブブロックに更に分割される２進データを
符号化する方法が提供される。本方法はこれらのＮビッ
トのデータを、特定のパリティ・チェック・マトリクス
Ｈにより決定されるパリティ・チェック条件に掛けるス
テップを含む。このマトリクスは別の特定の２進マトリ
クスＨ* から導出される。特に、マトリクスＨ* はタイ
プＩＩコードに対応するパリティ・チェック・マトリク
スを表し、ここでは第１行がＭ×Ｍ識別マトリクスをＳ
列含み、マトリクスＨ* の他の行はＭ×Ｍゼロ・マトリ
クス、Ｍ×Ｍ識別マトリクス、及びＭ×ＭマトリクスＴ
iを含む。ここでｉは負でない指数を示し、ＴはGalois
Field ＧＦ（２） 上の原始多項式ｐ（ｘ）に関連する
コンパニオン・マトリクスである。本発明の２進パリテ
ィ・チェック・マトリクスＨが導出されるこのＨ* マト
リクスは、Ｍ×ＭサブマトリクスによるＰ行及びＳ列を
含み、このサブマトリクスの第１行は識別マトリクスで
ある。
よれば、Ｎビットのブロック内で発生し、各々がＭビッ
トのＳ個のサブブロックに更に分割される２進データを
符号化する方法が提供される。本方法はこれらのＮビッ
トのデータを、特定のパリティ・チェック・マトリクス
Ｈにより決定されるパリティ・チェック条件に掛けるス
テップを含む。このマトリクスは別の特定の２進マトリ
クスＨ* から導出される。特に、マトリクスＨ* はタイ
プＩＩコードに対応するパリティ・チェック・マトリク
スを表し、ここでは第１行がＭ×Ｍ識別マトリクスをＳ
列含み、マトリクスＨ* の他の行はＭ×Ｍゼロ・マトリ
クス、Ｍ×Ｍ識別マトリクス、及びＭ×ＭマトリクスＴ
iを含む。ここでｉは負でない指数を示し、ＴはGalois
Field ＧＦ（２） 上の原始多項式ｐ（ｘ）に関連する
コンパニオン・マトリクスである。本発明の２進パリテ
ィ・チェック・マトリクスＨが導出されるこのＨ* マト
リクスは、Ｍ×ＭサブマトリクスによるＰ行及びＳ列を
含み、このサブマトリクスの第１行は識別マトリクスで
ある。
【００１５】本発明によれば、所望のパリティ・チェッ
ク・マトリクスＨは、サブマトリクスの第１行内のＭ×
Ｍ識別マトリクスをｂ×ｂ識別マトリクスにより置換し
（ここでＭ＋１≦ｂ＜２M−１） 、Ｍ×Ｍゼロ・マトリ
クスをＭ×ｂゼロ・マトリクスにより置換し、最後にＭ
×ＭマトリクスＴiをＴiマトリクスに列を追加したＭ×
ｂ増補マトリクスにより置換することにより、Ｈ* マト
リクスから導出される。ここで増補マトリクスの各追加
列はあるｊ（１≦ｊ≦ｂ）に対する多項式ｘjモジュロ
ｐ（ｘ）のベクトルである。既知の符号化方法によれ
ば、ｐ（ｘ）は２進数領域における原始２進多項式であ
る。所望のパリティ・チェック・マトリクスＨの結果
は、Ｓｂ列及びＭｐ＋（ｂ−Ｍ）行を有するマトリクス
である。このようにマトリクスＨはマトリクスＨ* に対
し、（ｂ−Ｍ）Ｓ列及び（ｂ−Ｍ）行を追加される。こ
こで述べられるタイプＩＩＩコードの追加機能は、これ
らの追加された要素に起因する。
ク・マトリクスＨは、サブマトリクスの第１行内のＭ×
Ｍ識別マトリクスをｂ×ｂ識別マトリクスにより置換し
（ここでＭ＋１≦ｂ＜２M−１） 、Ｍ×Ｍゼロ・マトリ
クスをＭ×ｂゼロ・マトリクスにより置換し、最後にＭ
×ＭマトリクスＴiをＴiマトリクスに列を追加したＭ×
ｂ増補マトリクスにより置換することにより、Ｈ* マト
リクスから導出される。ここで増補マトリクスの各追加
列はあるｊ（１≦ｊ≦ｂ）に対する多項式ｘjモジュロ
ｐ（ｘ）のベクトルである。既知の符号化方法によれ
ば、ｐ（ｘ）は２進数領域における原始２進多項式であ
る。所望のパリティ・チェック・マトリクスＨの結果
は、Ｓｂ列及びＭｐ＋（ｂ−Ｍ）行を有するマトリクス
である。このようにマトリクスＨはマトリクスＨ* に対
し、（ｂ−Ｍ）Ｓ列及び（ｂ−Ｍ）行を追加される。こ
こで述べられるタイプＩＩＩコードの追加機能は、これ
らの追加された要素に起因する。
【００１６】述べられるコードの所望される利点の１つ
は、復号化の容易性である。特に、入力コード・ベクト
ル及びパリティ・チェック・マトリクスから計算される
シンドロームは、オール０のベクトルであり、エラー指
示は提供されない。しかしながら、シンドロームがオー
ル０のベクトルでない場合には、シンドロームはマトリ
クスＨの全てのＳｂ列に対応する列ベクトルｉと比較さ
れる。シンドロームが丁度Ｈの列ｉと同一の場合、コー
ドワードのビットｉがエラーであり、それによりビット
ｉがビット反転により訂正される。従って、訂正回路は
典型的には、その出力部分に条件インバータまたは排他
的論理和ゲートを含む。更に、非ヌルのシンドロームが
Ｈのどの列にも一致しないことがわかると、訂正不能な
エラーがメモリ・アレイから受信されたコードワード内
に存在する指示が提供される。
は、復号化の容易性である。特に、入力コード・ベクト
ル及びパリティ・チェック・マトリクスから計算される
シンドロームは、オール０のベクトルであり、エラー指
示は提供されない。しかしながら、シンドロームがオー
ル０のベクトルでない場合には、シンドロームはマトリ
クスＨの全てのＳｂ列に対応する列ベクトルｉと比較さ
れる。シンドロームが丁度Ｈの列ｉと同一の場合、コー
ドワードのビットｉがエラーであり、それによりビット
ｉがビット反転により訂正される。従って、訂正回路は
典型的には、その出力部分に条件インバータまたは排他
的論理和ゲートを含む。更に、非ヌルのシンドロームが
Ｈのどの列にも一致しないことがわかると、訂正不能な
エラーがメモリ・アレイから受信されたコードワード内
に存在する指示が提供される。
【００１７】
【実施例】本発明の理解のために、タイプＩＩＩコード
の構成は、その構成に関し、小記号サイズの任意のタイ
プＩＩコードから展開される。エラー訂正コードの設計
において使用される既知の記述に従い、（Ｎ、Ｋ）コー
ドはコード・ベクトルの長さを表すＮビット、及びコー
ド内に存在する合計Ｋビットの情報を有するコードであ
る。こうしたコードは典型的にはＮ列及びＮ−Ｋ行のパ
リティ・チェック・マトリクスを有する。Ｎ−Ｋは有効
なチェック・ビット数を表す。特に、１記号当たり３ビ
ットの記号サイズを有する（３０合計ビット、２１情報
ビット、９チェック・ビット）の（３０、２１）タイプ
ＩＩコードが、１記号当たり４ビットの記号サイズを有
する（４０、３０）タイプＩＩＩコードに変換される。
しかしながら、チェック・ビット及び情報ビットの概念
は、厳密には、パリティ・チェック・マトリクスが縮小
された梯形形式（echelon form）で表現される。すなわ
ち先行識別マトリクスをその最左端列に有する。しかし
ながら、識別マトリクスをパリティ・チェック・マトリ
クスの様々な列に分散することも可能である。コードま
たはその実施の特性に影響することなく、パリティ・チ
ェック・マトリクス内のこうした入替えは、単にコード
内のビット位置の異なるマッピングに対応する。
の構成は、その構成に関し、小記号サイズの任意のタイ
プＩＩコードから展開される。エラー訂正コードの設計
において使用される既知の記述に従い、（Ｎ、Ｋ）コー
ドはコード・ベクトルの長さを表すＮビット、及びコー
ド内に存在する合計Ｋビットの情報を有するコードであ
る。こうしたコードは典型的にはＮ列及びＮ−Ｋ行のパ
リティ・チェック・マトリクスを有する。Ｎ−Ｋは有効
なチェック・ビット数を表す。特に、１記号当たり３ビ
ットの記号サイズを有する（３０合計ビット、２１情報
ビット、９チェック・ビット）の（３０、２１）タイプ
ＩＩコードが、１記号当たり４ビットの記号サイズを有
する（４０、３０）タイプＩＩＩコードに変換される。
しかしながら、チェック・ビット及び情報ビットの概念
は、厳密には、パリティ・チェック・マトリクスが縮小
された梯形形式（echelon form）で表現される。すなわ
ち先行識別マトリクスをその最左端列に有する。しかし
ながら、識別マトリクスをパリティ・チェック・マトリ
クスの様々な列に分散することも可能である。コードま
たはその実施の特性に影響することなく、パリティ・チ
ェック・マトリクス内のこうした入替えは、単にコード
内のビット位置の異なるマッピングに対応する。
【００１８】議論を始めるための基本コードとして、図
１は（３０、２１）タイプＩＩReed-Solomon コードに
対応するパリティ・チェック・マトリクスを表す。各記
号Ｉ3 は３×３識別サブマトリクスを表す。各記号Ｏ3
は全要素が０の３×３マトリクスを表す。マトリクスＴ
i はコンパニオン・マトリクスＴの様々な累乗を表す。
Ｔのこれらの累乗は、図２により詳細に示されている。
この例の目的のためだけに対応して、マトリクスＴは３
次の原始多項式に関連するコンパニオン・マトリクスで
ある。例えば、ｐ（ｘ）＝１＋Ｘ＋Ｘ3 である。マトリ
クスＴの最左端部分は標準の２×２識別サブマトリクス
である。最右端列に相当するＴの最後の列は、原始多項
式の係数をリストし、低位の係数がＴの最上行の近くに
リストされ、最上位の係数はリストされる必要はない。
これはこの場合はＸ3 の係数に相当する。
１は（３０、２１）タイプＩＩReed-Solomon コードに
対応するパリティ・チェック・マトリクスを表す。各記
号Ｉ3 は３×３識別サブマトリクスを表す。各記号Ｏ3
は全要素が０の３×３マトリクスを表す。マトリクスＴ
i はコンパニオン・マトリクスＴの様々な累乗を表す。
Ｔのこれらの累乗は、図２により詳細に示されている。
この例の目的のためだけに対応して、マトリクスＴは３
次の原始多項式に関連するコンパニオン・マトリクスで
ある。例えば、ｐ（ｘ）＝１＋Ｘ＋Ｘ3 である。マトリ
クスＴの最左端部分は標準の２×２識別サブマトリクス
である。最右端列に相当するＴの最後の列は、原始多項
式の係数をリストし、低位の係数がＴの最上行の近くに
リストされ、最上位の係数はリストされる必要はない。
これはこの場合はＸ3 の係数に相当する。
【００１９】図１に示されるタイプＩＩコードの構造の
結果、このコードのパリティ・チェック・マトリクスは
Ｓ個のサブマトリクスの列を含み、各サブ列はＭ×Ｍマ
トリクスである。この構成では、１記号当たりＳビット
による合計Ｍ個の記号が存在し、合計ＳＭビットを含
む。図１のチェック・マトリクスに表されるコードに適
用されるように、ビット位置の合計数すなわちＨIIの列
の数ＮはＳＭに等しく、ここでＳは記号の数であり、Ｍ
は１記号当たりのビット数である。同様に、ＨII内には
（Ｎ−Ｋ）行が存在し、この数は１記号当たりのビット
数のＰ倍であり、従ってＮ−Ｋ＝ＰＭとなる。ここで表
されまた議論される特定のタイプＩＩコードにおいて
は、Ｎ＝３０、Ｓ＝１０、Ｍ＝３、及びＰ＝３である。
従って、Ｎ−Ｋ＝９、またＫ＝２１である。更に図１で
示されるコードは、図３で明示的に展開されるように、
Reed-Solomonコードとして一般的に記述することができ
る。
結果、このコードのパリティ・チェック・マトリクスは
Ｓ個のサブマトリクスの列を含み、各サブ列はＭ×Ｍマ
トリクスである。この構成では、１記号当たりＳビット
による合計Ｍ個の記号が存在し、合計ＳＭビットを含
む。図１のチェック・マトリクスに表されるコードに適
用されるように、ビット位置の合計数すなわちＨIIの列
の数ＮはＳＭに等しく、ここでＳは記号の数であり、Ｍ
は１記号当たりのビット数である。同様に、ＨII内には
（Ｎ−Ｋ）行が存在し、この数は１記号当たりのビット
数のＰ倍であり、従ってＮ−Ｋ＝ＰＭとなる。ここで表
されまた議論される特定のタイプＩＩコードにおいて
は、Ｎ＝３０、Ｓ＝１０、Ｍ＝３、及びＰ＝３である。
従って、Ｎ−Ｋ＝９、またＫ＝２１である。更に図１で
示されるコードは、図３で明示的に展開されるように、
Reed-Solomonコードとして一般的に記述することができ
る。
【００２０】本発明によれば、一般的に図４に示される
形式のタイプＩＩコードが変更され、タイプＩＩＩコー
ドを記述する新たなパリティ・チェック・マトリクスを
生成する。特にＨIIの第１行内のＳ個の識別マトリクス
が１つ増加され、ｂ×ｂ識別サブマトリクスを形成する
（図５参照）。ここでｂはＭよりも大きな整数であり、
２M −１よりも小さな整数である。従って、使用される
構成手順により、コード・ベクトル成分の数が（ｂ−
Ｍ）Ｓだけ増加される。この例では、Ｓ＝１０は元のコ
ード内の記号の数に対応する。
形式のタイプＩＩコードが変更され、タイプＩＩＩコー
ドを記述する新たなパリティ・チェック・マトリクスを
生成する。特にＨIIの第１行内のＳ個の識別マトリクス
が１つ増加され、ｂ×ｂ識別サブマトリクスを形成する
（図５参照）。ここでｂはＭよりも大きな整数であり、
２M −１よりも小さな整数である。従って、使用される
構成手順により、コード・ベクトル成分の数が（ｂ−
Ｍ）Ｓだけ増加される。この例では、Ｓ＝１０は元のコ
ード内の記号の数に対応する。
【００２１】更にｂ＝Ｍ＋１の場合に対応して、変更が
元々与えられるタイプＩＩパリティ・チェック・マトリ
クスの他の行に対して実行される。特に、Ｍ×Ｍゼロ・
マトリクスのサイズが０の１列を追加することにより増
加され、Ｍ行及び（Ｍ＋１）列を有するゼロ・マトリク
スが生成される。最後に、Ｔコンパニオン・マトリクス
の種々の累乗を表すマトリクスＴi が最右端列ベクトル
を追加することにより変更され、各マトリクスＴi はＭ
個の成分を追加される。しかしながら、（この場合）ｉ
は０乃至５まで変化するので、ｉの値に依存して異なる
列が追加される。一般に、各マトリクスＴi はＭ×ｂマ
トリクスに変換され、そのｊ番目の列は多項式ｘi+j-1
モジュロｐ（ｘ）のベクトルである。これは単一項多項
式ｘi+j-1が前述の原始多項式ｐ（ｘ）により除算さ
れ、対応する剰余多項式が生成されることを意味する。
この剰余多項式の係数は、前述のように、増補Ｔi マト
リクス（図６のＡＵＧ（Ｔi ））のセットを生成するた
めに使用される。構成されるタイプＩＩＩコードに対応
して、マトリクスＴの増補が図６に示されるように発生
し、増補は上述の意味において記号"ＡＵＧ"により示さ
れる。また、本発明のコード生成アプローチでは、混乱
を回避するため、Ｍ×ＭマトリクスＴ0 はここでは一般
にＭ×Ｍ識別マトリクスとして定義される。
元々与えられるタイプＩＩパリティ・チェック・マトリ
クスの他の行に対して実行される。特に、Ｍ×Ｍゼロ・
マトリクスのサイズが０の１列を追加することにより増
加され、Ｍ行及び（Ｍ＋１）列を有するゼロ・マトリク
スが生成される。最後に、Ｔコンパニオン・マトリクス
の種々の累乗を表すマトリクスＴi が最右端列ベクトル
を追加することにより変更され、各マトリクスＴi はＭ
個の成分を追加される。しかしながら、（この場合）ｉ
は０乃至５まで変化するので、ｉの値に依存して異なる
列が追加される。一般に、各マトリクスＴi はＭ×ｂマ
トリクスに変換され、そのｊ番目の列は多項式ｘi+j-1
モジュロｐ（ｘ）のベクトルである。これは単一項多項
式ｘi+j-1が前述の原始多項式ｐ（ｘ）により除算さ
れ、対応する剰余多項式が生成されることを意味する。
この剰余多項式の係数は、前述のように、増補Ｔi マト
リクス（図６のＡＵＧ（Ｔi ））のセットを生成するた
めに使用される。構成されるタイプＩＩＩコードに対応
して、マトリクスＴの増補が図６に示されるように発生
し、増補は上述の意味において記号"ＡＵＧ"により示さ
れる。また、本発明のコード生成アプローチでは、混乱
を回避するため、Ｍ×ＭマトリクスＴ0 はここでは一般
にＭ×Ｍ識別マトリクスとして定義される。
【００２２】本発明により実行される一般的な生成方法
によれば、（Ｍ×Ｍ）サブマトリクスのＳ列及びＰ行を
有するタイプＩＩパリティ・チェック・マトリクスが、
Ｓｂ列及びＭＰ＋（ｂ−Ｍ）行の２進フィールド要素を
有するマトリクスに変換される。これらの行及び列は第
１行の形式で発生し、ｂ×ｂ識別マトリクスがＳ列に配
列される。ほぼ同様に、他の（Ｐ−１）行のサブマトリ
クスがＭ×ｂサブマトリクスに変換され、増補（列数の
Ｍ乃至Ｍ＋１への増補）が上述のように実行される。従
って、本発明で実行される変換により、Ｎ＝ＳＭ列及び
ＰＭ＝（Ｎ−Ｋ）行のマトリクスが、Ｓｂ列及びＭＰ＋
（ｂ−Ｍ）行を有するタイプＩＩＩコードに対応するパ
リティ・チェック・マトリクスに変換される。これが図
５に表される。
によれば、（Ｍ×Ｍ）サブマトリクスのＳ列及びＰ行を
有するタイプＩＩパリティ・チェック・マトリクスが、
Ｓｂ列及びＭＰ＋（ｂ−Ｍ）行の２進フィールド要素を
有するマトリクスに変換される。これらの行及び列は第
１行の形式で発生し、ｂ×ｂ識別マトリクスがＳ列に配
列される。ほぼ同様に、他の（Ｐ−１）行のサブマトリ
クスがＭ×ｂサブマトリクスに変換され、増補（列数の
Ｍ乃至Ｍ＋１への増補）が上述のように実行される。従
って、本発明で実行される変換により、Ｎ＝ＳＭ列及び
ＰＭ＝（Ｎ−Ｋ）行のマトリクスが、Ｓｂ列及びＭＰ＋
（ｂ−Ｍ）行を有するタイプＩＩＩコードに対応するパ
リティ・チェック・マトリクスに変換される。これが図
５に表される。
【００２３】この変換例から生じるパリティ・チェック
・マトリクスが、その２進形式により図７に示され、Ｈ
III '' として定義される。これは４０＝１０×４列、及
び１０＝４＋（３−１）×３＝３×３＋（４−３）行の
マトリクスである。図７の破線は説明の都合上描かれて
おり、特に全体的なパリティ・チェック・マトリクスを
構成するサブマトリクスを詳細に示すことを目的とす
る。このマトリクスは図８に示されるマトリクスＨopt
を形成するために、更に行オペレーションにより変換さ
れる。
・マトリクスが、その２進形式により図７に示され、Ｈ
III '' として定義される。これは４０＝１０×４列、及
び１０＝４＋（３−１）×３＝３×３＋（４−３）行の
マトリクスである。図７の破線は説明の都合上描かれて
おり、特に全体的なパリティ・チェック・マトリクスを
構成するサブマトリクスを詳細に示すことを目的とす
る。このマトリクスは図８に示されるマトリクスＨopt
を形成するために、更に行オペレーションにより変換さ
れる。
【００２４】タイプＩＩＩコードのチェック・ビット及
びシンドローム・ビットは、パリティ・チェック・マト
リクスの行ベクトルにより指定されるデータ・ビットに
対する排他的論理和演算により生成される。これは他の
タイプの２進コードに対して実行される正則手順と同じ
である。
びシンドローム・ビットは、パリティ・チェック・マト
リクスの行ベクトルにより指定されるデータ・ビットに
対する排他的論理和演算により生成される。これは他の
タイプの２進コードに対して実行される正則手順と同じ
である。
【００２５】本発明の特徴の１つは、復号化の実行の相
対的な容易性である。特に、シンドローム・ビットが生
成されると（図１０のステップ１０参照）、次にシンド
ロームがヌルかどうかが判断される（ステップ２０）。
すなわち、オール０のベクトルかどうかがチェックされ
る。肯定の場合、エラー指示は提供されず（ステップ３
０）、受信される入力シーケンスが正しいシーケンスの
ビットとして解釈される。
対的な容易性である。特に、シンドローム・ビットが生
成されると（図１０のステップ１０参照）、次にシンド
ロームがヌルかどうかが判断される（ステップ２０）。
すなわち、オール０のベクトルかどうかがチェックされ
る。肯定の場合、エラー指示は提供されず（ステップ３
０）、受信される入力シーケンスが正しいシーケンスの
ビットとして解釈される。
【００２６】しかしながら、シンドローム・ビットがヌ
ルでない場合には、シンドロームがパリティ・チェック
・マトリクスの全ての列ベクトルと比較される（ステッ
プ４０）。次にパリティ・チェック・マトリクスの任意
の列がシンドロームに一致するかどうかが判断される
（ステップ５０）。一致が存在しない場合、訂正不能な
エラーが発生しており、この状況を示す信号が好適には
提供される（ステップ６０）。一致する列が見い出され
ると、訂正されたシーケンスを提供するために、対応す
る一致列のビットが反転される（ステップ７０）。しか
しながら、この訂正機能は単一ビット・エラーを訂正す
るまでに限られる。それにも関わらず、エラー訂正機能
は上述のタイプＩＩＩコードの機能である。
ルでない場合には、シンドロームがパリティ・チェック
・マトリクスの全ての列ベクトルと比較される（ステッ
プ４０）。次にパリティ・チェック・マトリクスの任意
の列がシンドロームに一致するかどうかが判断される
（ステップ５０）。一致が存在しない場合、訂正不能な
エラーが発生しており、この状況を示す信号が好適には
提供される（ステップ６０）。一致する列が見い出され
ると、訂正されたシーケンスを提供するために、対応す
る一致列のビットが反転される（ステップ７０）。しか
しながら、この訂正機能は単一ビット・エラーを訂正す
るまでに限られる。それにも関わらず、エラー訂正機能
は上述のタイプＩＩＩコードの機能である。
【００２７】図１１は、本発明の符号化方法及び装置を
メモリ・アレイ構造に関連する好適な実施例において利
用する場合を示す。典型的には、こうしたメモリ・アレ
イ構造１０は、個々のチップまたはチップ・アレイ１乃
至Ｓを含む。こうしたチップは典型的には出力ラッチ１
５のセットを含み、これらはアレイに供給されるアドレ
ス信号に応答して提供されるメモリ内容を記憶する。特
に、図示のシステムでは、各チップは４つの信号（ｂ＝
４）をＥＣＣ回路１００に供給する。ＥＣＣ回路１００
については図１２で詳細に述べられる。各チップはこの
時ｂビットをＥＣＣ回路に提供すると表現され、ＥＣＣ
回路は合計Ｓｂビットを受信する。ＥＣＣ回路１００
は、必要に応じこれらのビットを訂正したり、訂正不能
エラー（ＵＥ）が発生したことを示したりする。
メモリ・アレイ構造に関連する好適な実施例において利
用する場合を示す。典型的には、こうしたメモリ・アレ
イ構造１０は、個々のチップまたはチップ・アレイ１乃
至Ｓを含む。こうしたチップは典型的には出力ラッチ１
５のセットを含み、これらはアレイに供給されるアドレ
ス信号に応答して提供されるメモリ内容を記憶する。特
に、図示のシステムでは、各チップは４つの信号（ｂ＝
４）をＥＣＣ回路１００に供給する。ＥＣＣ回路１００
については図１２で詳細に述べられる。各チップはこの
時ｂビットをＥＣＣ回路に提供すると表現され、ＥＣＣ
回路は合計Ｓｂビットを受信する。ＥＣＣ回路１００
は、必要に応じこれらのビットを訂正したり、訂正不能
エラー（ＵＥ）が発生したことを示したりする。
【００２８】図１０に表される方法を実行する装置が図
１２により詳細に表される。特に、メモリ・ラッチ１５
からの出力信号が、シンドローム発生器１１０に供給さ
れる。この生成を実行する特定の回路はＥＣＣ技術では
既知であるため、ここではそれらについて説明しない。
シンドロームはそれがヌル（すなわちオール０）かどう
かを判断するために、シンドローム・テスタ１２０に供
給される。肯定の場合、続く処理の結果発生する反転を
禁止するために、ヌル信号標識が（条件）インバータ１
５０に供給される。シンドロームがヌルでない場合、比
較回路１４０は処理される信号シーケンス内の対応する
一致位置を決定するために、タイプＩＩＩ符号化パリテ
ィ・チェック・マトリクスの列をシンドロームと比較す
る。一致すると見い出される列に対し、対応する信号が
条件インバータ１５０に供給される。インバータは典型
的には別の排他的論理和ゲートのアレイを含む。こうし
たゲートは"排他的論理和ゲート"として述べられるが、
条件反転機能を実行する。エラー訂正オペレーション
は、出力ラッチ１５からのビット・シーケンスの条件反
転により実行される。それにも関わらず、シンドローム
・テスタ１２０からのヌル信号は、エラーが発生せずシ
ンドロームがヌルの状況において、列一致信号の供給を
禁止するために使用される。これは典型的な状況であ
る。更に、訂正不能エラー信号を提供するように動作す
る過剰一致テスタ１３０も提供される。これは例えば、
シンドロームに一致することが見い出される列数が、こ
こで述べられるタイプＩＩＩ符号化機能の限界を越える
場合に発生する。また、シンドローム・テスタ１２０か
ら過剰一致テスタ１３０にヌル信号標識を供給すること
により、訂正不能エラー信号の生成を禁止することが可
能である。
１２により詳細に表される。特に、メモリ・ラッチ１５
からの出力信号が、シンドローム発生器１１０に供給さ
れる。この生成を実行する特定の回路はＥＣＣ技術では
既知であるため、ここではそれらについて説明しない。
シンドロームはそれがヌル（すなわちオール０）かどう
かを判断するために、シンドローム・テスタ１２０に供
給される。肯定の場合、続く処理の結果発生する反転を
禁止するために、ヌル信号標識が（条件）インバータ１
５０に供給される。シンドロームがヌルでない場合、比
較回路１４０は処理される信号シーケンス内の対応する
一致位置を決定するために、タイプＩＩＩ符号化パリテ
ィ・チェック・マトリクスの列をシンドロームと比較す
る。一致すると見い出される列に対し、対応する信号が
条件インバータ１５０に供給される。インバータは典型
的には別の排他的論理和ゲートのアレイを含む。こうし
たゲートは"排他的論理和ゲート"として述べられるが、
条件反転機能を実行する。エラー訂正オペレーション
は、出力ラッチ１５からのビット・シーケンスの条件反
転により実行される。それにも関わらず、シンドローム
・テスタ１２０からのヌル信号は、エラーが発生せずシ
ンドロームがヌルの状況において、列一致信号の供給を
禁止するために使用される。これは典型的な状況であ
る。更に、訂正不能エラー信号を提供するように動作す
る過剰一致テスタ１３０も提供される。これは例えば、
シンドロームに一致することが見い出される列数が、こ
こで述べられるタイプＩＩＩ符号化機能の限界を越える
場合に発生する。また、シンドローム・テスタ１２０か
ら過剰一致テスタ１３０にヌル信号標識を供給すること
により、訂正不能エラー信号の生成を禁止することが可
能である。
【００２９】上述から、有益なエラー訂正機構が一般に
提供され、特に、例えばチップなどのメモリ・アレイ構
造からの多重ビットの読出しが存在する半導体メモリ・
システムまたは他のメモリ・システムに従事するメモリ
・システム設計者に提供される。特に、本発明は単一記
号エラーの全ての組合わせを、別の記号内の単一ビット
・エラーと一緒に実際に検出可能な符号化方法を提供す
ることが理解されよう。更に、本発明はタイプＩＩＩコ
ード（ここではこのように定義される）を提供し、これ
はタイプＩコードに対する要求よりも多いが、タイプＩ
Ｉコードに対する要求よりは少ないチェック・ビット要
求を有する。例えば、１記号当たりｂ＝８ビットの１２
８データ・ビットに対し要求されるチェック・ビットの
最小数は、タイプＩコードでは１１ビットであり、タイ
プＩＩコードでは２４ビットである。しかしながら、本
発明によるタイプＩＩＩコードは１６チェック・ビット
しか要求しない。従って、メモリ・システム設計者は貴
重な設計のトレード・オフ機構を提供される。更に、こ
のトレード・オフ機構は、単一チップから複数ビットを
読出すメモリ・システムにおいて特に有益である。従っ
て、ここで述べられるコードは、多重ビット読出しメモ
リ・システムにおいて見られる故障メカニズムに適応す
るエラー検出及び訂正機能を提供する点で、有益な利点
を提供する。
提供され、特に、例えばチップなどのメモリ・アレイ構
造からの多重ビットの読出しが存在する半導体メモリ・
システムまたは他のメモリ・システムに従事するメモリ
・システム設計者に提供される。特に、本発明は単一記
号エラーの全ての組合わせを、別の記号内の単一ビット
・エラーと一緒に実際に検出可能な符号化方法を提供す
ることが理解されよう。更に、本発明はタイプＩＩＩコ
ード（ここではこのように定義される）を提供し、これ
はタイプＩコードに対する要求よりも多いが、タイプＩ
Ｉコードに対する要求よりは少ないチェック・ビット要
求を有する。例えば、１記号当たりｂ＝８ビットの１２
８データ・ビットに対し要求されるチェック・ビットの
最小数は、タイプＩコードでは１１ビットであり、タイ
プＩＩコードでは２４ビットである。しかしながら、本
発明によるタイプＩＩＩコードは１６チェック・ビット
しか要求しない。従って、メモリ・システム設計者は貴
重な設計のトレード・オフ機構を提供される。更に、こ
のトレード・オフ機構は、単一チップから複数ビットを
読出すメモリ・システムにおいて特に有益である。従っ
て、ここで述べられるコードは、多重ビット読出しメモ
リ・システムにおいて見られる故障メカニズムに適応す
るエラー検出及び訂正機能を提供する点で、有益な利点
を提供する。
【００３０】まとめとして、本発明の構成に関して以下
の事項を開示する。 （１）各々がＭビットのＳ個のサブブロックを有するＮ
ビットのブロック内で発生する２進データの符号化方法
であって、前記Ｎビット・データを２進パリティ・チェ
ック・マトリクスＨにより決定されるパリティ・チェッ
ク条件に掛けるステップを含み、マトリクスＨを２進マ
トリクスＨ* から導出し、前記マトリクスＨ* はタイプ
ＩＩコードを表し、Ｍ×ＭサブマトリクスをＰ行及びＳ
列に配列し、前記Ｐ行の第１行がＭ×Ｍ識別マトリクス
であり、他の行のＭ×ＭマトリクスはＭ×Ｍゼロ・マト
リクス、Ｍ×Ｍ識別マトリクス及びＭ×ＭマトリクスＴ
i を含み、ここでｉは負でない指数を示し、ＴはＧＦ
（２）．上のＭ次の原始２進多項式ｐ（ｘ）に関連する
コンパニオン・マトリクスであり、前記Ｈマトリクスを
Ｓｂ列及びＭＰ＋（ｂ−Ｍ）行を有するマトリクスを生
成するために前記Ｈ* マトリクスから導出するステップ
であって、前記導出ステップが、前記マトリクスの前記
第１行内のＭ×Ｍ識別マトリクスをｂ×ｂ識別マトリク
スにより置換するステップと、前記Ｍ×Ｍゼロ・マトリ
クスをＭ×ｂゼロ・マトリクスにより置換するステップ
と、前記Ｍ×ＭマトリクスＴi をＭ×ｂ増補マトリクス
により置換するステップとを含み、ｊ番目列は多項式Ｘ
i+j-1 モジュロｐ（ｘ）のベクトルである、前記導出ス
テップとを含む方法。 （２）Ｎ＝３０、Ｓ＝１０、及びＭ＝３である、前記
（１）に記載の方法。 （３）前記原始２進多項式ｐ（ｘ）＝１＋Ｘ＋Ｘ3であ
る、前記（１）に記載の方法。 （４）前記コンパニオン・マトリクスＴが、
の事項を開示する。 （１）各々がＭビットのＳ個のサブブロックを有するＮ
ビットのブロック内で発生する２進データの符号化方法
であって、前記Ｎビット・データを２進パリティ・チェ
ック・マトリクスＨにより決定されるパリティ・チェッ
ク条件に掛けるステップを含み、マトリクスＨを２進マ
トリクスＨ* から導出し、前記マトリクスＨ* はタイプ
ＩＩコードを表し、Ｍ×ＭサブマトリクスをＰ行及びＳ
列に配列し、前記Ｐ行の第１行がＭ×Ｍ識別マトリクス
であり、他の行のＭ×ＭマトリクスはＭ×Ｍゼロ・マト
リクス、Ｍ×Ｍ識別マトリクス及びＭ×ＭマトリクスＴ
i を含み、ここでｉは負でない指数を示し、ＴはＧＦ
（２）．上のＭ次の原始２進多項式ｐ（ｘ）に関連する
コンパニオン・マトリクスであり、前記Ｈマトリクスを
Ｓｂ列及びＭＰ＋（ｂ−Ｍ）行を有するマトリクスを生
成するために前記Ｈ* マトリクスから導出するステップ
であって、前記導出ステップが、前記マトリクスの前記
第１行内のＭ×Ｍ識別マトリクスをｂ×ｂ識別マトリク
スにより置換するステップと、前記Ｍ×Ｍゼロ・マトリ
クスをＭ×ｂゼロ・マトリクスにより置換するステップ
と、前記Ｍ×ＭマトリクスＴi をＭ×ｂ増補マトリクス
により置換するステップとを含み、ｊ番目列は多項式Ｘ
i+j-1 モジュロｐ（ｘ）のベクトルである、前記導出ス
テップとを含む方法。 （２）Ｎ＝３０、Ｓ＝１０、及びＭ＝３である、前記
（１）に記載の方法。 （３）前記原始２進多項式ｐ（ｘ）＝１＋Ｘ＋Ｘ3であ
る、前記（１）に記載の方法。 （４）前記コンパニオン・マトリクスＴが、
【数２】 である、前記（１）に記載の方法。 （５）前記２進パリティ・チェック・マトリクスが図７
に示されるマトリクスである、前記（１）に記載の方
法。 （６）前記マトリクスＨがマトリクスを縮小梯形形式
（reduced echelon form）により配置する行オペレーシ
ョンにより変更される、前記（１）に記載の方法。 （７）エラー訂正及び検出機能を向上するために第１ポ
イントから第２ポイントにデジタル情報を伝送する方法
であって、前記方法が第１の複数（Ｋ）の情報ビット及
び第２の複数（Ｎ−Ｋ）のチェック・ビットを表す入力
電気信号を伝送するステップを含み、前記信号がＮ倍長
２進ベクトルと見なされる時、前記ベクトルがタイプＩ
ＩＩコードに対応するパリティ・チェック・マトリクス
である（Ｎ−Ｋ）×Ｎのパリティ・チェック・マトリク
スＨのヌル空間に配置されるように、前記信号が生成さ
れる方法。 （８）前記パリティ・チェック・マトリクスＨが図７に
示されるマトリクスである、前記（７）に記載の方法。 （９）各々が指定アドレスに応答してメモリ内容を示す
ｂビット幅の信号を生成する、個別のメモリ素子のアレ
イと、前記メモリ・アレイから前記Ｓｂ信号を受信し、
タイプＩＩＩ要求によりエラーを訂正及び検出する、タ
イプＩＩＩエラー訂正コード手段とを含む、メモリ・シ
ステム。 （１０）タイプＩＩＩパリティ・チェック・マトリクス
により符号化された受信された２進シーケンス内のエラ
ーを訂正及び検出する方法であって、シンドローム・ベ
クトルを生成するステップと、シンドロームがヌルかど
うかを判断するステップと、前記シンドロームがヌルで
ない時、前記シンドロームを前記タイプＩＩＩパリティ
・チェック・マトリクスの列と比較するステップと、前
記比較の結果一致する列に対応する前記受信シーケンス
内のビットを反転するステップと、を含む方法。 （１１）前記比較の結果一致する列が存在しない場合、
訂正不能エラー信号を供給するステップを含む、前記
（１０）に記載の方法。 （１２）タイプＩＩＩパリティ・チェック・マトリクス
により符号化された受信された２進シーケンス内のエラ
ーを訂正及び検出する装置であって、シンドローム・ベ
クトル発生器と、前記発生シンドロームがヌルかどうか
を判断する手段と、前記非ヌルのシンドロームを前記タ
イプＩＩＩパリティ・チェック・マトリクスの列と比較
する比較手段と、前記比較手段により提供される一致列
の指示に対応する前記受信シーケンス内のビットを反転
する反転手段と、を含む装置。 （１３）前記シンドロームがヌルでなく、前記比較手段
が列一致指示を提供しない場合、訂正不能エラー状態を
提供する手段を含む、前記（１２）に記載の装置。
に示されるマトリクスである、前記（１）に記載の方
法。 （６）前記マトリクスＨがマトリクスを縮小梯形形式
（reduced echelon form）により配置する行オペレーシ
ョンにより変更される、前記（１）に記載の方法。 （７）エラー訂正及び検出機能を向上するために第１ポ
イントから第２ポイントにデジタル情報を伝送する方法
であって、前記方法が第１の複数（Ｋ）の情報ビット及
び第２の複数（Ｎ−Ｋ）のチェック・ビットを表す入力
電気信号を伝送するステップを含み、前記信号がＮ倍長
２進ベクトルと見なされる時、前記ベクトルがタイプＩ
ＩＩコードに対応するパリティ・チェック・マトリクス
である（Ｎ−Ｋ）×Ｎのパリティ・チェック・マトリク
スＨのヌル空間に配置されるように、前記信号が生成さ
れる方法。 （８）前記パリティ・チェック・マトリクスＨが図７に
示されるマトリクスである、前記（７）に記載の方法。 （９）各々が指定アドレスに応答してメモリ内容を示す
ｂビット幅の信号を生成する、個別のメモリ素子のアレ
イと、前記メモリ・アレイから前記Ｓｂ信号を受信し、
タイプＩＩＩ要求によりエラーを訂正及び検出する、タ
イプＩＩＩエラー訂正コード手段とを含む、メモリ・シ
ステム。 （１０）タイプＩＩＩパリティ・チェック・マトリクス
により符号化された受信された２進シーケンス内のエラ
ーを訂正及び検出する方法であって、シンドローム・ベ
クトルを生成するステップと、シンドロームがヌルかど
うかを判断するステップと、前記シンドロームがヌルで
ない時、前記シンドロームを前記タイプＩＩＩパリティ
・チェック・マトリクスの列と比較するステップと、前
記比較の結果一致する列に対応する前記受信シーケンス
内のビットを反転するステップと、を含む方法。 （１１）前記比較の結果一致する列が存在しない場合、
訂正不能エラー信号を供給するステップを含む、前記
（１０）に記載の方法。 （１２）タイプＩＩＩパリティ・チェック・マトリクス
により符号化された受信された２進シーケンス内のエラ
ーを訂正及び検出する装置であって、シンドローム・ベ
クトル発生器と、前記発生シンドロームがヌルかどうか
を判断する手段と、前記非ヌルのシンドロームを前記タ
イプＩＩＩパリティ・チェック・マトリクスの列と比較
する比較手段と、前記比較手段により提供される一致列
の指示に対応する前記受信シーケンス内のビットを反転
する反転手段と、を含む装置。 （１３）前記シンドロームがヌルでなく、前記比較手段
が列一致指示を提供しない場合、訂正不能エラー状態を
提供する手段を含む、前記（１２）に記載の装置。
【００３１】
【発明の効果】以上説明したように、本発明によれば、
メモリ・アレイの信頼性を向上することができる。
メモリ・アレイの信頼性を向上することができる。
【図１】タイプＩＩコードに対応する典型的なReed-Sol
omonパリティ・チェック・マトリクスを示す図である。
omonパリティ・チェック・マトリクスを示す図である。
【図２】タイプＩＩパリティ・チェック・マトリクスを
２進形式で説明する、図１のマトリクスの代わりのコン
パニオン・マトリクスＴ及びその種々の累乗を示す図で
ある。
２進形式で説明する、図１のマトリクスの代わりのコン
パニオン・マトリクスＴ及びその種々の累乗を示す図で
ある。
【図３】図２に示されるＴの累乗を図１のマトリクス構
造に代用した結果を表す図である。
造に代用した結果を表す図である。
【図４】タイプＩＩパリティ・チェック・マトリクスを
その種々のサブ構造の点から示した全体構造及びサイズ
要求を示す図である。
その種々のサブ構造の点から示した全体構造及びサイズ
要求を示す図である。
【図５】本発明によるタイプＩＩＩコードのパリティ・
チェック・マトリクス構造を表す図である。
チェック・マトリクス構造を表す図である。
【図６】原始多項式ｐ（ｘ）＝１＋ｘ＋ｘ3 に関連する
コンパニオン・マトリクスＴに対応する種々の増補マト
リクスを表す図である。
コンパニオン・マトリクスＴに対応する種々の増補マト
リクスを表す図である。
【図７】（４０、３０）タイプＩＩＩコードに対応する
典型的なパリティ・チェック・マトリクスを表す図であ
る。
典型的なパリティ・チェック・マトリクスを表す図であ
る。
【図８】マトリクス内で発生する２進数の数を減らし最
適化を計った以外は図７と同じ形式の２進パリティ・チ
ェック・マトリクスを表す図である。
適化を計った以外は図７と同じ形式の２進パリティ・チ
ェック・マトリクスを表す図である。
【図９】図８のパリティ・チェック・マトリクスに関連
するチェック・ビット１に対応する排他的論理和ツリー
を表す図である。
するチェック・ビット１に対応する排他的論理和ツリー
を表す図である。
【図１０】本発明によるタイプＩＩＩコード化方法によ
り符号化されるシーケンスに関連するエラーを検出及び
訂正するためのステップを表す流れ図である。
り符号化されるシーケンスに関連するエラーを検出及び
訂正するためのステップを表す流れ図である。
【図１１】メモリ・システム内における本発明のアプリ
ケーションを表すブロック図である。
ケーションを表すブロック図である。
【図１２】タイプＩＩＩ符号化方法によりエラー訂正及
び検出を実行する装置を表すブロック図である。
び検出を実行する装置を表すブロック図である。
１０ メモリ・アレイ構造 １５ 出力ラッチ、メモリ・ラッチ １００ ＥＣＣ回路 １１０ シンドローム発生器 １２０ シンドローム・テスタ １３０ 過剰一致テスタ １４０ 比較回路 １５０ 条件インバータ
Claims (13)
- 【請求項１】各々がＭビットのＳ個のサブブロックを有
するＮビットのブロック内で発生する２進データの符号
化方法であって、 前記Ｎビット・データを２進パリティ・チェック・マト
リクスＨにより決定されるパリティ・チェック条件に掛
けるステップと、 マトリクスＨを２進マトリクスＨ*から導出し、前記マ
トリクスＨ*はタイプＩＩコードを表し、Ｍ×Ｍサブマ
トリクスをＰ行及びＳ列に配列し、前記Ｐ行の第１行が
Ｍ×Ｍ識別マトリクスであり、他の行のＭ×Ｍマトリク
スはＭ×Ｍゼロ・マトリクス、Ｍ×Ｍ識別マトリクス、
及びＭ×ＭマトリクスＴi を含み、ここでｉは負でない
指数を示し、Ｔはガロイス・フィールドＧＦ（２）上の
Ｍ次の原始２進多項式ｐ（ｘ）に関連するコンパニオン
・マトリクスであり、前記ＨマトリクスをＳｂ列及びＭ
Ｐ＋（ｂ−Ｍ）行を有するマトリクスを生成するために
前記Ｈ*マトリクスから導出するステップであって、前
記導出ステップが、 （１）前記マトリクスの前記第１行内のＭ×Ｍ識別マト
リクスをｂ×ｂ識別マトリクスにより置換するステップ
と、 （２）前記Ｍ×Ｍゼロ・マトリクスをＭ×ｂゼロ・マト
リクスにより置換するステップと、 （３）前記Ｍ×ＭマトリクスＴi をＭ×ｂ増補マトリク
スにより置換するステップとを含み、ｊ番目列は多項式
Ｘi+j-1 モジュロｐ（ｘ）のベクトルである、前記導出
ステップと、 を含む方法。 - 【請求項２】Ｎ＝３０、Ｓ＝１０、及びＭ＝３である、
請求項１記載の方法。 - 【請求項３】前記原始２進多項式ｐ（ｘ）＝１＋Ｘ＋Ｘ
3である、請求項１記載の方法。 - 【請求項４】前記コンパニオン・マトリクスＴが、 【数１】 である、請求項１記載の方法。
- 【請求項５】前記２進パリティ・チェック・マトリクス
が図７に示されるマトリクスである、請求項１記載の方
法。 - 【請求項６】前記マトリクスＨがマトリクスを縮小梯形
形式（reduced echelon form）により配置する行オペレ
ーションにより変更される、請求項１記載の方法。 - 【請求項７】エラー訂正及び検出機能を向上するために
第１ポイントから第２ポイントにデジタル情報を伝送す
る方法であって、前記方法が第１の複数（Ｋ）の情報ビ
ット及び第２の複数（Ｎ−Ｋ）のチェック・ビットを表
す入力電気信号を伝送するステップを含み、前記信号が
Ｎ倍長２進ベクトルと見なされる時、前記ベクトルがタ
イプＩＩＩコードに対応するパリティ・チェック・マト
リクスである（Ｎ−Ｋ）×Ｎのパリティ・チェック・マ
トリクスＨのヌル空間に配置されるように、前記信号が
生成される方法。 - 【請求項８】前記パリティ・チェック・マトリクスＨが
図７に示されるマトリクスである、請求項７記載の方
法。 - 【請求項９】各々が指定アドレスに応答してメモリ内容
を示すｂビット幅の信号を生成する、個別のメモリ素子
のアレイと、 前記メモリ・アレイから前記Ｓｂ信号を受信し、タイプ
ＩＩＩ要求によりエラーを訂正及び検出する、タイプＩ
ＩＩエラー訂正コード手段と、 を含む、メモリ・システム。 - 【請求項１０】タイプＩＩＩパリティ・チェック・マト
リクスにより符号化された受信された２進シーケンス内
のエラーを訂正及び検出する方法であって、 シンドローム・ベクトルを生成するステップと、 シンドロームがヌルかどうかを判断するステップと、 前記シンドロームがヌルでない時、前記シンドロームを
前記タイプＩＩＩパリティ・チェック・マトリクスの列
と比較するステップと、 前記比較の結果一致する列に対応する前記受信シーケン
ス内のビットを反転するステップと、 を含む方法。 - 【請求項１１】前記比較の結果一致する列が存在しない
場合、訂正不能エラー信号を供給するステップを含む、
請求項１０記載の方法。 - 【請求項１２】タイプＩＩＩパリティ・チェック・マト
リクスにより符号化された受信された２進シーケンス内
のエラーを訂正及び検出する装置であって、 シンドローム・ベクトル発生器と、 前記発生シンドロームがヌルかどうかを判断する手段
と、 前記非ヌルのシンドロームを前記タイプＩＩＩパリティ
・チェック・マトリクスの列と比較する比較手段と、 前記比較手段により提供される一致列の指示に対応する
前記受信シーケンス内のビットを反転する反転手段と、 を含む装置。 - 【請求項１３】前記シンドロームがヌルでなく、前記比
較手段が列一致指示を提供しない場合、訂正不能エラー
状態を提供する手段を含む、請求項１２記載の装置。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US087442 | 1993-07-02 | ||
| US08/087,442 US5425038A (en) | 1993-07-02 | 1993-07-02 | Error plus single bit error detection |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH0736717A true JPH0736717A (ja) | 1995-02-07 |
| JP2589957B2 JP2589957B2 (ja) | 1997-03-12 |
Family
ID=22205224
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP6122178A Expired - Lifetime JP2589957B2 (ja) | 1993-07-02 | 1994-06-03 | 単一サブブロック・エラーと単一ビット・エラー検出のための符号化方法及びメモリ・システム |
Country Status (2)
| Country | Link |
|---|---|
| US (1) | US5425038A (ja) |
| JP (1) | JP2589957B2 (ja) |
Families Citing this family (17)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5956351A (en) * | 1997-04-07 | 1999-09-21 | International Business Machines Corporation | Dual error correction code |
| US6307899B1 (en) * | 1998-06-16 | 2001-10-23 | Ameritech Corporation | Method and system for optimizing coding gain |
| FR2799592B1 (fr) * | 1999-10-12 | 2003-09-26 | Thomson Csf | Procede de construction et de codage simple et systematique de codes ldpc |
| US6968491B1 (en) * | 2002-04-08 | 2005-11-22 | Sanera Systems Inc. | Generating a check matrix for error correction |
| US6920601B1 (en) | 2002-04-08 | 2005-07-19 | Sanera Systems Inc. | Error correction for data communication |
| US7103818B2 (en) * | 2002-09-30 | 2006-09-05 | Mitsubishi Electric Research Laboratories, Inc | Transforming generalized parity check matrices for error-correcting codes |
| US7530008B2 (en) * | 2003-08-08 | 2009-05-05 | Sun Microsystems, Inc. | Scalable-chip-correct ECC scheme |
| US7788567B1 (en) | 2003-11-18 | 2010-08-31 | Apple Inc. | Symbol encoding for tolerance to single byte errors |
| US7171591B2 (en) * | 2003-12-23 | 2007-01-30 | International Business Machines Corporation | Method and apparatus for encoding special uncorrectable errors in an error correction code |
| US7243293B2 (en) * | 2003-12-23 | 2007-07-10 | International Business Machines Corporation | (18, 9) Error correction code for double error correction and triple error detection |
| KR100634414B1 (ko) * | 2004-09-06 | 2006-10-16 | 삼성전자주식회사 | 에러 검출용 패러티 발생기를 구비한 낸드 플래시 메모리 장치 및 그것의 에러 검출 방법 |
| US7934147B2 (en) * | 2005-08-03 | 2011-04-26 | Qualcomm Incorporated | Turbo LDPC decoding |
| US8196025B2 (en) | 2005-08-03 | 2012-06-05 | Qualcomm Incorporated | Turbo LDPC decoding |
| WO2007019187A2 (en) * | 2005-08-03 | 2007-02-15 | Novowave, Inc. | Systems and methods for a turbo low-density parity-check decoder |
| DE102009031310B4 (de) * | 2008-07-24 | 2019-12-19 | Atmel Corp. | Speichersystem, Leseverstärker, Verwendung und Verfahren zur Fehlerdetektion mittels Parity-Bits eines Blockcodes |
| KR20120059806A (ko) * | 2010-12-01 | 2012-06-11 | 한국전자통신연구원 | 에러 정정 부호의 생성방법, 복호 방법 및 그 장치 |
| KR20250135519A (ko) * | 2024-03-06 | 2025-09-15 | 에스케이하이닉스 주식회사 | Ecc 엔진을 포함하는 메모리 시스템 |
Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS6250943A (ja) * | 1985-08-30 | 1987-03-05 | Hitachi Ltd | 記憶装置 |
| JPS6279530A (ja) * | 1985-10-03 | 1987-04-11 | Fujitsu Ltd | 誤り訂正・検出装置 |
Family Cites Families (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4464753A (en) * | 1981-12-30 | 1984-08-07 | International Business Machines Corporation | Two bit symbol SEC/DED code |
| FR2582888B1 (fr) * | 1985-05-30 | 1987-08-21 | Dornstetter Jean Louis | Procede de transmission, avec possibilite de correction de paquets d'erreurs, de messages d'information et dispositifs de codage et de decodage pour la mise en oeuvre de ce procede. |
| US4998253A (en) * | 1988-03-11 | 1991-03-05 | Kokusai Denshin Denwa Co., Ltd. | Syndrome sequential decoder |
| FR2646975B1 (fr) * | 1989-05-10 | 1991-08-30 | Schlumberger Ind Sa | Generateur de donnees numeriques |
-
1993
- 1993-07-02 US US08/087,442 patent/US5425038A/en not_active Expired - Fee Related
-
1994
- 1994-06-03 JP JP6122178A patent/JP2589957B2/ja not_active Expired - Lifetime
Patent Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS6250943A (ja) * | 1985-08-30 | 1987-03-05 | Hitachi Ltd | 記憶装置 |
| JPS6279530A (ja) * | 1985-10-03 | 1987-04-11 | Fujitsu Ltd | 誤り訂正・検出装置 |
Also Published As
| Publication number | Publication date |
|---|---|
| US5425038A (en) | 1995-06-13 |
| JP2589957B2 (ja) | 1997-03-12 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP4036338B2 (ja) | 誤りバイト数を制限したバイト内複数スポッティバイト誤り訂正・検出方法及び装置 | |
| US5856987A (en) | Encoder and decoder for an SEC-DED-S4ED rotational code | |
| US7278085B1 (en) | Simple error-correction codes for data buffers | |
| US7370264B2 (en) | H-matrix for error correcting circuitry | |
| US6675349B1 (en) | Error correction coding of data blocks with included parity bits | |
| US8806295B2 (en) | Mis-correction and no-correction rates for error control | |
| JP2589957B2 (ja) | 単一サブブロック・エラーと単一ビット・エラー検出のための符号化方法及びメモリ・システム | |
| Bossen | b-Adjacent error correction | |
| US5537423A (en) | Modular multiple error correcting code system | |
| TWI782215B (zh) | 減少多位元錯誤校正碼的邏輯的系統與方法 | |
| US5251219A (en) | Error detection and correction circuit | |
| JPH03136524A (ja) | 長バースト誤りに対する誤り検出及び訂正システム | |
| CN102468855A (zh) | 用于纠正在编码比特序列中的至少单比特错误的设备和方法 | |
| US6539513B1 (en) | Dual functioning symbol error correction code | |
| US7093183B2 (en) | Symbol level error correction codes which protect against memory chip and bus line failures | |
| US7085988B1 (en) | Hashing system utilizing error correction coding techniques | |
| Bhargavi et al. | H-matrix based error correction codes for memory applications | |
| US5754562A (en) | Method and apparatus for encoding certain double-error correcting and triple-error detecting codes | |
| Wang et al. | Reliable MLC NAND flash memories based on nonlinear t-error-correcting codes | |
| US5805615A (en) | Method and apparatus for encoding certain double-error correcting and triple-error detecting codes | |
| EP0341851A2 (en) | Method and apparatus for interleaved encoding | |
| JP3743915B2 (ja) | スポッティバイト誤り訂正・検出方法及び装置 | |
| Fujiwara et al. | Optimal two-level unequal error control codes for computer systems | |
| US12261626B2 (en) | Coding circuit and memory device including the same | |
| US12218688B2 (en) | Error correction with fast syndrome calculation |