JP2009100369A - 誤り検出訂正回路、半導体メモリコントローラ、および誤り検出訂正方法 - Google Patents

Abstract

【課題】効率の良い誤り訂正が可能な誤り検出訂正回路、前記誤り検出訂正回路を有する半導体メモリコントローラ、および誤り訂正方法を提供する。
【解決回路】誤り検出訂正回路３は、入力された誤り訂正符号を有する受信情報のシンドロームを算出するシンドローム算出回路７と、誤り位置多項式の導出を行う多項式導出回路８と、受信情報の誤り位置を求めるチェン探索回路９と、受信情報の誤りを訂正する誤り訂正回路１０とを備え、誤り訂正回路１０は、チェン探索回路９が一の誤り位置を特定する度に、直ちに一の誤り位置の受信情報の誤りを訂正し、出力する。
【選択図】図２

Description

本発明は、受信情報の誤りを訂正し復号する誤り検出訂正回路、前記誤り検出訂正回路を有する半導体メモリコントローラ、および受信情報の誤り検出訂正方法に関し、特に、チェン探索を用いる誤り検出訂正回路等に関する。

誤り検出訂正技術は、ノイズまたは保存媒体の損傷のような様々な理由によって、データを伝送する過程またはデータを保存あるいは再生する過程でエラーが発生する恐れがあるデータ通信またはストレージメディア等の多くの分野で使用されている。

例えば、書き換え可能なであるＮＡＮＤ型フラッシュメモリは、書き換え回数の増加に従ってエラー率が大きくなる傾向がある。特に、ＮＡＮＤ型フラッシュメモリは、大容量化すなわち、回路微細化が進むと、エラー率は上昇する傾向がある。このため、特許文献１には、フラッシュメモリチップ内に或いはこれを制御する半導体メモリコントローラに、特定の処理を行う誤り検出訂正回路（ＥＣＣ回路：Ｅｒｒｏｒ Correcting Ｃｏｄｅ）を搭載することが記載されている。

誤り符号生成回路により保存前に誤り訂正符号、例えば、ＢＣＨ（Ｂｏｓｅ−Ｃｈａｕｄｈｕｒｌ−Ｈｏｃｑｕｅｎｇｈｅｍ）符号あるいはＢＣＨ符号の線形ブロックコードであるリードソロモン（Ｒｅｅｄ Ｓｏｌｏｍｏｎ；ＲＳ）符号が付加された情報の誤りを検出して訂正する回路が誤り検出訂正回路である。そして、誤り検出訂正回路は、保存した情報データを読み出す際に、誤り訂正符号が付加された情報データが入力されると、入力情報データの誤りを検出し訂正する。誤り訂正可能な情報データの誤りの数は、付加されている誤り訂正符号により異なり、ｔ重誤り訂正符号が付加されている情報データでは、ｔ個の誤りが訂正可能である。すなわち、ｔ重誤りＢＣＨ符号が付加されている情報データではｔビットの、１シンボルが１バイトのｔ重誤りリードソロモン符号が付加されている情報データではｔバイトの、誤りが訂正可能である。

ＢＣＨ符号およびリードソロモン符号は、いずれも、ガロア体上の原始多項式とその根の性質を使って構成される符号である。しかし、ＢＣＨ符号が、１ビットを単位として情報を取り扱い、また、誤り訂正符号もビット単位で生成されるのに対して、リードソロモン符号は、たとえば８ビット＝１バイトを単位として情報を取り扱い、また、誤り訂正符号もバイト単位で生成される点で異なる。情報と誤り訂正符号がバイト単位で表されるリードソロモン符号では、符号を通信して再生し、これを復号する誤り訂正を行う際にもバイト単位で処理がなされる。そのため、情報の誤りはバイト単位で認識されるため、リードソロモン符号はバイト単位で複数の誤りが生じる可能性の高い場合の誤り訂正に適している。

誤り検出訂正回路は、ＢＣＨ符号またはリードソロモン符号を有する受信信号を、（１）誤りの有無の確認ステップ、（２）誤りの数の算出ステップ（誤り位置多項式導出ステップ）、（３）誤りの位置の算出ステップ、（４）誤りの訂正ステップの順で処理を行う。

そして、誤りの位置の算出ステップにおいては、チェン探索法が採用されている。チェン探索法では、Ｎ次の誤り位置多項式の変数Ｘに、あり得る全ての値（例えば、０〜Ｍ：Ｍは最終ビット位置または最終バイト位置）を順次、代入して、誤り位置多項式を満たすかどうかを探索していく。そして、Ｎ個の解の全てが特定された時点、すなわちＮ個の誤り全ての位置が特定された時点で、一括して誤っていたデータを訂正し、訂正後の受信情報を出力する。

このため、誤りの位置が受信データの最終部（チェン探索で代入する最後の値）であった場合には、チェン探索で最後の値が代入後において、はじめてデータ訂正および出力が行われる。このため、データが出力されるまでに時間を要していた。さらに、出力インターフェイスの転送バスの容量および速度には制限があるため、大量のデータを一度には出力できない。このため、誤り訂正後の情報出力にも時間を要することがある。

このように、公知の誤り検出訂正回路、前記誤り検出訂正回路を有する半導体メモリコントローラ、および誤り検出訂正方法は効率が悪いことがあった。
特開２００７−１９３９１０号公報

本発明は、効率の良い誤り訂正が可能な誤り訂正回路、前記誤り訂正回路を有する半導体メモリコントローラ、および誤り検出訂正方法を提供することを目的とする。

本願発明の一態様の誤り検出訂正回路は、入力された誤り訂正符号を有する受信情報のシンドロームを算出するシンドローム算出回路と、前記シンドロームに基づいて生成された誤り位置多項式の導出を行う多項式導出回路と、前記誤り位置多項式から前記受信情報の誤り位置を求めるチェン探索回路と、前記誤り位置の前記受信情報の誤りを訂正する誤り訂正回路とを備えており、前記誤り訂正回路は、前記チェン探索回路が、一の位置の前記受信情報に誤りがないと判断した場合は、直ちに、前記一の位置の前記受信情報を出力し、他の一の位置の前記受信情報に誤りがあると判断した場合は、直ちに、前記他の一の誤り位置の前記受信情報の誤りを訂正し、出力することを特徴とする。

また、本願発明の別の一態様の半導体メモリコントローラは、前記誤り検出訂正回路を有することを特徴とする。

また、本願発明の別の一態様の誤り検出訂正方法は、誤り訂正符号を有する受信情報の誤りを訂正し復号する誤り訂正方法であって、入力された前記受信情報のシンドロームを算出するシンドローム算出ステップと、前記シンドロームに基づいて生成された誤り位置多項式の導出を行う多項式導出ステップと、前記誤り位置多項式から前記受信情報の誤り位置を求めるチェン探索ステップと、前記誤り位置の前記受信情報の誤りを訂正する誤り訂正ステップとを行い、前記誤り訂正ステップは、前記チェン探索ステップが一の前記誤り位置を特定する度に、前記一の誤り位置の前記受信情報の誤りを訂正し、出力することを特徴とする。

本発明は効率の良い誤り訂正が可能な誤り検出訂正回路、前記誤り検出訂正回路を有する半導体メモリコントローラ、および誤り訂正方法（以下、「誤り訂正回路等」という。）を提供するものである。

以下、図面を参照して本発明の実施の形態を説明する。
＜第１の実施の形態＞
図１は、本願発明の第１の実施の形態にかかる半導体メモリ媒体１の構成を示す構成図である。半導体メモリ媒体１は、パソコンまたはデジタルカメラ等のホスト１３から受信したデータを記憶し、記憶したデータをホスト１３に送信する記憶媒体であり、例えば、ＮＡＮＤ型フラッシュメモリ媒体である。

半導体メモリ媒体１は、メモリアレイ４と半導体メモリコントローラ２とから構成されている。そして、半導体メモリコントローラ２は、ＣＰＵ６の制御に従い、ホストインターフェイス（I/F）１２を介してホスト１３とのデータ送受信を、メモリインターフェイス５を介してメモリアレイ４とのデータ送受信を行う。また、誤り符号生成回路１１はホストからのデータに誤り訂正符号を生成し、冗長領域に誤り訂正符号を付加する。そして、誤り検出訂正回路３は、メモリアレイからの誤り訂正符号が付加された受信情報の処理に以下の順序で用いられる、シンドロームを算出するシンドローム算出回路７、誤り多項式を導出する多項式導出回路８、誤り位置を探索するチェン探索回路および特定された誤りを訂正する誤り訂正回路１０とを有する。

すなわち、ホスト１３から、に受信された情報は、誤り訂正符号生成回路１１により誤り訂正符号が付加され、メモリインターフェイス（I/F）５を介してメモリアレイ４に記憶される。

メモリアレイ４に記憶された情報は、メモリインターフェイス５を介して半導体メモリコントローラ２に受信され、誤り検出訂正回路３において、誤りの訂正が行われ、ホストインターフェイス１２を介してホスト１３に出力される。

すなわち、誤り検出訂正回路３においては、最初にシンドローム算出回路７においてシンドロームが算出される。シンドローム算出値がゼロの場合には、誤りの個数Ｎがゼロであることを意味しており、誤り訂正を行う必要はないため、受信された情報は、図１の（Ａ）の経路に従い、当該位置の情報は、ホストインターフェイス１２を介してホスト１３に出力される。シンドローム算出値がゼロでない場合、シンドロームを基に、多項式導出回路８において、誤り位置多項式が導出される。ここで、誤り位置多項式の係数がＮ次の多項式で表された場合には、Ｎ個の誤りがあることを意味している。

誤り位置多項式導出により、Ｎ個の誤りがあることが発見された場合には、次のステップとして、チェン探索回路９において、順に、誤り位置が特定される。チェン探索回路９においては、情報データのある位置の順に、誤りがあるか無いかが順に特定されていく。本実施の形態の誤り検出訂正回路３においては、誤りがないと判断された位置のデータは、次の位置のデータの誤りの有無を判断する前に、直ちに、図１の（Ｃ）の経路に従い、ホストインターフェイス１２を介してホスト１３に出力される。一方、チェン探索回路９において、誤りがあることが特定された誤り位置の情報は、誤り訂正回路１０において誤りが訂正され、図１の（Ｂ）の経路に従い、直ちに、ホストインターフェイス１２を介してホスト１３に出力される。すなわち、本実施の形態の誤り検出訂正回路３においては、チェン検索において、全ての誤り位置が特定されてから一括して訂正および全データの出力が行われていた公知の誤り検出回路と全く異なる処理を行う。

なお、誤り訂正回路における誤り訂正は、具体的には、ＢＣＨ符号を有するビット信号の場合には、ビット信号のビット反転を行い、リードソロモン符号を有するバイト信号の場合には、さらに連立一次方程式を用いて８ビットのデータとして誤り訂正後の値を算出する。

また、誤り検出訂正回路３または半導体メモリコントローラ２は、図示しないメモリ回路を有していてもよい。メモリ回路は、ホストインターフェイス１２へ出力する情報等を一時的に記憶しておくメモリである。メモリ回路を有する誤り検出訂正回路３または半導体メモリコントローラ２では、チェン探索回路９において、誤りが無いと判断された一の情報、あるいは、誤り訂正回路１０において誤りが訂正された一の情報または誤りが無かった一の情報を、その一の情報毎に、その一の情報の単位（例えば、１ビットまたは１バイト）で直ちに出力するが、その出力された情報を直ちにホスト１３に送信しない場合もある。すなわち、順に出力された一の情報を１ビットまたは１バイト単位でホスト１３に送信しないで、ホストインターフェイス１２との調整を取りながら、ホストインターフェイス１２のバス容量未満の単位であれば、複数まとめて送信することも可能である。例えば、ホストインターフェイス１２バスが８ビットであれば、８ビットの誤りが訂正された一の情報（１ビット）または誤りが無かった一の情報情報（１ビット）を出力後に、順にメモリ回路に記憶しておき、８ビット分の情報が記憶された時点で単位で８ビットをまとめてホスト１３に送信することもできる。

次に、図２を用いて、第１の実施の形態の誤り検出訂正回路３における処理の流れを、より詳細に説明する。図２は、第１の実施の形態の誤り検出訂正回路における処理の流れを説明するためのフローチャートである。

メモリアレイ４に記憶された情報は、メモリインターフェイス５を介して、受信情報として半導体メモリコントローラ２に入力される（ステップＳ３１）。そして、受信情報から、シンドローム算出回路７においてシンドロームが算出される（ステップＳ３２）。もし、シンドローム算出値がゼロの場合には、誤りの個数Ｎがゼロであることを意味しており、ステップＳ３３においてＹｅｓと判断され、受信信号は図１の（Ａ）の経路により、ホストインターフェイス１２を介して直ちにホスト１３に送信される。シンドローム算出値がゼロ以外の場合には、ステップＳ３３においてＮｏと判断され、次に、シンドロームを基に、多項式導出回路８において、誤り位置多項式が導出される（ステップＳ３４）。ここで、誤り位置多項式は、例えば以下の式で示される。

ａ_ＮＸ^Ｎ＋ａ_Ｎ−１Ｘ^Ｎ−１＋・・・・・・＋ａ_２Ｘ^２＋ａ_１Ｘ^１＋ａ_０＝０
誤り位置多項式の次数Ｎは、受信信号にＮ個の誤りが存在していることを示しており、誤り位置多項式を満たすＸの値が受信信号内の誤りビットまたはバイトの位置を示している。

そして、以下のステップにおいて、チェン探索回路９においてチェン探索により、誤り位置の特定が行われる。

チェン探索においては、想定される全ての値を誤り位置多項式のＸに代入し誤り位置多項式を満たすか否かを検討する。このため、Ｘに代入していくｎの初期値として０を設定する（ステップＳ３６）。そして、ｎをＸに代入し、誤り位置多項式を満たすか否かを判断する（ステップＳ３８）。代入したｎが、誤り位置多項式を満たさない場合には、位置ｎの情報には誤りが無いことを意味する。従って、ステップＳ３８においてＮｏとなる。

すると、本実施の形態の誤り検出訂正回路においては、Ｍ個の全ての情報の誤りの有無の判断結果はもちろん、次の位置ｎ＋１の情報の誤りの有無の判断結果を待つことなく、直ちにステップＳ４０において、位置ｎの情報は図１の（Ｃ）に示す経路により、出力される。

反対に、ステップＳ３８において、代入したｎが、誤り位置多項式を満たした場合には、位置ｎの情報に誤りがあることを意味する。すなわち、ステップＳ３８においてＹｅｓとなり、その場合にも、全ての位置の情報の誤りの有無の判断結果を待つことなく、直ちにステップＳ３９において、まず誤り訂正回路１０により位置ｎの情報のみの誤りが訂正され、次にステップＳ４０において、誤り訂正後の位置ｎの情報は図１の（Ｂ）に示す経路により、出力される。

そして、ステップＳ３７においてＮ個の誤り位置の全てが特定されるまで、あるいは、ステップＳ４１においてＸに代入していくｎの最大値であるＭに至るまで、ステップＳ４２においてｎを１づつ増加していく。

本実施の形態の誤り検出訂正回路３は、チェン探索回路において、受信情報の中の一の位置に誤りが無いことを確認する度に、誤りの無いことが確認された一の位置の受信情報を直ちに出力する。

また、本実施の形態の誤り検出訂正回路３は、チェン探索回路において、一の誤り位置を特定する度に、特定された一の誤り位置の受信情報の誤りのみを訂正し、直ちに出力する。このため、本実施の形態の誤り検出訂正回路３は、Ｍ個の情報の中の全ての誤りが訂正された後に、一括してＭ個の情報を送信する公知の誤り検出訂正回路と比べて、効率の良い誤り訂正を行うことができる。

すなわち、本実施の形態の誤り検出訂正回路３は、位置Ｍの受信情報までのチェン探索が終了するのを待たないで、順に処理された情報を出力するため、出力インターフェイスの転送バスの容量および速度の制限の影響を受けにくい。また、ホスト１３は全ての誤りが訂正された情報（データ）の出力を待つ必要はなく、順に出力されてきたデータを処理することができる。

言い換えれば、本実施の形態の誤り検出訂正回路３から、出力される情報は、ＢＣＨ符号処理情報ではビット単位、リードソロモン符号処理情報ではシンボル単位である。従来の誤り検出訂正回路３から出力される情報がＭビット、またはＭバイトであったのに対して、本実施の形態の誤り検出訂正回路３から、出力される情報の単位は最小では、１ビットまたは１シンボル（例えば１バイト）と極めて小さいため、効率良く、ホストインターフェイス１２およびホスト１３に出力することができる。

このように、本実施の形態の誤り検出訂正回路３を有する半導体メモリコントローラ２は、上記のように誤り検出訂正回路の効率が良いため、ホストインターフェイス１２およびホスト１３の待ち時間および負荷が少ない。また、本実施の形態の誤り訂正方法は誤り訂正の効率が良い。

なお、一の誤り訂正符号で処理される情報の数、すなわち、上記のＭ（厳密にはＭ＋１）、はシステムにより異なるが、２５０〜１６０００程度であることが多い。

＜第２の実施の形態＞
次に、図３および図４を用いて、第２の実施の形態の誤り検出訂正回路における処理の流れを、説明する。図３および図４は、本実施の形態の誤り検出訂正回路における処理の流れを説明するためのフローチャートである。本実施の形態の誤り検出訂正回路等の基本的な構成は、図１に示す第１の実施の形態の構成と同様である。

図３に示す本実施の形態の誤り検出訂正回路のフローチャートは、図２に示した第１の実施の形態の誤り検出訂正回路のフローチャートと類似しており、異なる処理についてのみ説明する。

誤り検出訂正回路３が訂正可能な誤りの個数には限界がある。すなわち、誤り訂正符号付与回路１１において付与された誤り訂正符号により、訂正可能な誤りの個数 ｔ は決まっている。このため、ステップＳ３４において発見された誤りの個数Ｎが、誤り訂正可能な誤りの個数 ｔ に対して同数または（ｔ−１）等のように、多い場合には、誤り訂正を正しく行うことができない場合がある。すなわち、チェン探索において、想定される全ての値をＮ次の誤り位置多項式のＸに代入しても、Ｎ個の解が得られないことがある。この場合には、たとえ、チェン探索の途中でＮ個の未満の解が得られていても、その解を信頼することができない。また、誤り訂正を正しく行うことができない状況であることは、誤り位置多項式のＸに最後の値Ｍを代入するまで解らない。

このため、一の位置の前記受信情報に誤りがない場合には、前記一の位置の前記受信情報を出力し、他の一の位置の前記受信情報に誤りがある場合には、前記他の一の誤り位置の前記受信情報の誤りを訂正し、出力するする第１の実施の形態の訂正回路では、間違った情報を出力してしまう可能性、すなわちシステムの信頼性が低下する可能性があった。

本実施の形態の誤り検出訂正回路３の処理においては、図３に示した最初のステップＳ３０において、誤りの個数の上限許容値 ｋ が入力される。なお、上限許容値 ｋ の入力は毎回行う必要はなく、誤り検出訂正回路３の作成時に入力され固定された値でもよい。

上限許容値 ｋ は、訂正可能な誤りの個数 ｔ を参酌し、システムに要求される信頼性により決定される。上限許容値 ｋ には、１以上の整数が入力され、より高信頼性が要求される場合には小さな値を入力し、逆に、比較的、信頼性の許容範囲が広い場合には、訂正可能な誤りの個数 ｔ と同数でも構わない。なお、経験的にはｔ重の誤り訂正符号（ｔ個の誤り訂正が可能）が付与された情報の場合、（ｔ―１）個以上の誤りがあると判断された場合、すなわち誤り位置多項式が（ｔ−１）次以上の次数の場合には、誤り訂正を正しく行うことができない場合がありうる。逆に言えば、ｔ重の誤り訂正符号が付与された情報の場合で、誤り位置多項式が（ｔ―１）個未満の次数の場合、すなわち誤りの個数が（ｔ−１）個未満の場合には、誤り訂正を正しく行うことができない場合は極めて希である。

そして、ステップＳ３５において、発見された誤りの個数Ｎが、上限許容値 ｋ 以下の場合には、図３に示すように、図２に示した第１の実施の形態と同様の処理が行われるが、発見された誤りの個数Ｎが、上限許容値 ｋ を超える場合には、図４に示すフローチャート（Ｉ）からの処理が行われる。

発見された誤りの個数Ｎが、上限許容値 ｋ 超えた場合には、図３のステップＳ３５から、（Ｉ）すなわち、図４のステップＳ１５からの処理が行われる。図４に示す誤り検出訂正回路の処理においては、ステップＳ１７で誤り位置が特定された場合、その誤り位置および全情報を図１に図示しないメモリ回路に一時記憶しておく（ステップＳ１９）。そして、Ｎ個の誤り位置の全てが特定された段階（ステップＳ２０）で、Ｎ個の誤り位置全てのデータを一括訂正し（ステップＳ２１）、修正後のＮ個の誤り位置のデータを含めたＭ個の全データを一括して出力する（、ステップＳ２２）。なお、図４に示したフローチャートの全体（ステップＳ１１〜）は、公知のチェン検索による誤り検出訂正方法である。

一方、図４のステップＳ１６において、想定される全ての値（０からＭ）をＸに代入しても、Ｎ個の解が得られなかった場合には、誤り検出訂正回路は訂正不能と判断する（ステップＳ２３）。これは、最大Ｎ個の誤り訂正が可能な誤り訂正符号が付与されている情報にＮ＋１個以上の誤りが存在していたためであり、この場合には既に得られていた解も正しいとは保証されないためである。

本実施の形態の誤り検出訂正回路３等は、第１の実施の形態で得られた効果に加えて、多くの誤りが発生しても、正しい誤り訂正が可能となり出力情報の信頼性が高い。かつ、誤り発生が少ない場合には本実施の形態の誤り検出訂正回路３を用いた等は、効率の良い誤り訂正を行うことができるため、ホストインターフェイス１２およびホスト１３の待ち時間および負荷が少ない。

＜第３の実施の形態＞
次に、図５を用いて、第３の実施の形態の誤り検出訂正回路３における処理の流れを、説明する。図５は、本実施の形態の誤り検出訂正回路３における処理の流れを説明するためのフローチャートである。本実施の形態の誤り検出訂正回路等の基本的な構成は、図１に示す第１の実施の形態の構成と同様である。

メモリアレイ４に記憶されている情報は、Ｍ個の集合体として誤り訂正符号が付与されている。このため、公知の誤り検出訂正回路においては、Ｍ個の受信情報の中の一部の情報のみを必要とする場合においても、Ｍ個の受信情報の全ての誤り訂正が完了するまで、情報が出力されない。例えば、先頭の位置の１個の情報のみを必要とする場合にもＭ個の誤り訂正処理が完了するまで、情報は出力されない。このため、公知の誤り検出訂正回路は誤り訂正の効率が悪い場合があった。

これに対して、本実施の形態の誤り検出訂正回路３においては、Ｍ個の受信情報の中から予め指定された範囲の受信情報のみの誤り訂正を行い、情報を出力する。すなわち、受信情報内に定義された属性フラグ値等の一部の情報のみを必要とする場合には、その必要な情報のみの誤り訂正を行い、誤り訂正後の情報をすみやかに出力することができる。

図５に示す本実施の形態の誤り検出訂正回路のフローチャートは、図３に示した第２の実施の形態の誤り検出訂正回路のフローチャートと類似しているため、異なる処理についてのみ説明する。

図５に示すように、本実施の形態の誤り検出訂正回路３の処理においては、最初のステップＳ４９において、第２の実施の形態の誤り検出訂正回路と同じく、誤りの個数の上限許容値 ｋ が入力される。

なお、ステップＳ５５において、発見された誤りの個数Ｎが、上限許容値 ｋ を超える場合には、図４に示すフローチャート（Ｉ）からの処理が行われる。発見された誤りの個数Ｎ、すなわち、誤り位置多項式の次数が上限許容値 ｋ を超える場合にはチェン探索回路３が、一の位置の前記受信情報に誤りがないと判断しても、全ての位置の誤りが特定されるまでは、チェン探索回路３の判断が正しいか否か確定できないことが経験的にあるからである。

そして、本実施の形態の誤り検出訂正回路３の処理においては、ステップＳ５０において、誤り訂正を行う範囲、すなわち、Ｎ１およびＮ２が入力される。Ｎ１およびＮ２は、０以上で、かつ全情報の個数Ｍ以下の整数であり、出力したい所望の情報が存在する位置である。

そして、ステップＳ５６においてチェン探索の誤り位置多項式に代入していくｎの初期値としてＮ１が設定される。そして、チェン探索回路９は、ステップＳ６１においてｎがＮ２になるまでチェン探索を行う。

本実施の形態の誤り検出訂正回路３のチェン探索回路９においては、必要な範囲の情報のみを探索する。このため、本実施の形態の誤り検出訂正回路３等は、第１の実施および第２の実施の形態の誤り検出訂正回路３等で得られた効果に加えて、さらに、効率の良い誤り訂正を行うことができるため、ホストインターフェイス１２およびホスト１３の待ち時間および負荷が少ない。

本発明は、上述した実施の形態に限定されるものではなく、本発明の要旨を変えない範囲において、種々の変更、改変等が可能である。

第１の実施の形態にかかる半導体メモリ媒体の構成を説明するための構成図である。 第１の実施の形態の誤り検出訂正回路の処理の流れを説明するためのフローチャートである。 第２の実施の形態の誤り検出訂正回路の処理の流れを説明するためのフローチャートである。 第２の実施の形態の誤り検出訂正回路の処理の流れを説明するためのフローチャートであり、かつ、その全体は公知の誤り検出訂正回路の処理の流れを説明するフローチャートである。 第３の実施の形態の誤り検出訂正回路の処理の流れを説明するためのフローチャートである。

符号の説明

１…半導体メモリ媒体、２…半導体メモリコントローラ、３…誤り検出訂正回路、４…メモリアレイ、６…ＣＰＵ、７…シンドローム算出回路、８…多項式導出回路、９…チェン探索回路、１０…誤り訂正回路、１１…訂正符号生成回路、１３…ホスト

Claims (5)

1. 入力された誤り訂正符号を有する受信情報のシンドロームを算出するシンドローム算出回路と、
   前記シンドロームに基づいて生成された誤り位置多項式の導出を行う多項式導出回路と、
   前記誤り位置多項式から前記受信情報の誤り位置を求めるチェン探索回路と、
   前記誤り位置の前記受信情報の誤りを訂正する誤り訂正回路とを備え、
   前記誤り訂正回路は、前記チェン探索回路が、
   一の位置の前記受信情報に誤りがないと判断した場合は、直ちに前記一の位置の前記受信情報を出力し、
   他の一の位置の前記受信情報に誤りがあると判断した場合は、直ちに前記他の一の誤り位置の前記受信情報の誤りを訂正し、出力することを特徴とする誤り検出訂正回路。
2. 前記チェン探索回路は、前記誤り位置多項式の次数が所定の次数を超える場合には、全ての前記誤り位置の前記受信情報の誤りを訂正した後、前記受信情報を一括して出力することを特徴とする誤り検出訂正回路。
3. 前記チェン探索回路は、前記受信情報の一部の範囲の前記誤り位置のみを特定することを特徴とする請求項１または請求項２に記載の誤り検出訂正回路。
4. 請求項１から請求項３の何れか１項に記載の誤り検出訂正回路を有することを特徴とする半導体メモリコントローラ。
5. 誤り訂正符号を有する受信情報の誤りを訂正し復号する誤り検出訂正方法であって、
   入力された前記受信情報のシンドロームを算出するシンドローム算出ステップと、
   前記シンドロームに基づいて生成された誤り位置多項式の導出を行う多項式導出ステップと、
   前記誤り位置多項式から前記受信情報の誤り位置を求めるチェン探索ステップと、
   前記誤り位置の前記受信情報の誤りを訂正する誤り訂正ステップとを行い、
   前記誤り訂正ステップは、前記チェン探索ステップが一の前記誤り位置を特定する度に、前記一の誤り位置の前記受信情報の誤りを訂正し、出力することを特徴とする誤り検出訂正方法。

Images