JP5525498B2 - 誤り検出装置 - Google Patents

Description

本発明の実施形態は、誤り検出装置に関する。

フラッシュメモリ等の半導体記憶装置では、読み出された値にエラーが含まれることがある。そのため、半導体記憶装置のコントローラには誤り検出装置が搭載されることが多い。近年、半導体記憶装置の記憶容量が大幅に増加しており、これに伴って、誤り検出装置の消費電流も増大している。そのため、低消費電流で動作する誤り検出装置が必要とされている。

特開平８−１３０４８０号公報

低消費電流で動作する誤り検出装置を提供する。

実施形態によれば、誤り検出装置は、シンドローム処理部と、位置多項式生成部と、探索処理部とを備える。前記シンドローム処理部は、受信データに基づいてシンドローム値を生成する。前記位置多項式生成部は、前記シンドローム値に基づいて誤り位置多項式の係数を生成する。前記探索処理部は、前記誤り位置多項式の根を算出して誤り位置を検出する。前記探索処理部は、クロック制御部と、バッファと、多項式生成部と、判定部とを有する。前記クロック制御部は、前記係数の値に応じてクロック信号を出力または停止する。前記バッファは、前記クロック制御部から出力されたクロック信号を駆動する。前記多項式生成部は、前記バッファにより駆動されたクロック信号に同期して前記誤り位置多項式の一部を算出する。前記判定部は、前記誤り位置多項式の一部に基づいて、前記誤り位置多項式の根を算出する。

第１の実施形態に係る誤り検出装置１００の概略ブロック図。 エラー数の見積もり値とシグマ値σ_１〜σ_ｔとの関係を示す図。 チェン探索処理部３の内部構成の一例を示す図。 第１の実施形態に係るチェン探索処理部３の入力部３１ｋの概略構成を模式的に示すブロック図。 シグマ値σ_ｋが０でない場合の、入力部３１ｋの各部の信号波形図。 シグマ値σ_ｋが０である場合の、入力部３１ｋの各部の信号波形図。 第２の実施形態に係るチェン探索処理部３の入力部３１Ｎ’〜３１Ｍ’の概略構成を模式的に示す図。 第３の実施形態に係るチェン探索処理部３の入力部３１Ｎ’’〜３１Ｍ’’の概略構成を模式的に示す図。 誤り検出装置を有するメモリシステムの概略構成を示すブロック図。

以下、実施形態について、図面を参照しながら具体的に説明する。

（第１の実施形態）
図１は、第１の実施形態に係る誤り検出装置１００の概略ブロック図である。誤り検出装置１００は、シンドローム処理部１と、誤り位置多項式生成部２と、チェン（Ｃｈｉｅｎ）探索処理部３とを備えている。以下、図１の誤り検出装置１００が訂正可能な最大ビット数をｔとする。

シンドローム処理部１は元データおよびパリティを含む受信データを復号して、２ｔ個のシンドローム値ｓ_１〜ｓ_２ｔを生成する。シンドローム値ｓ_１〜ｓ_２ｔがすべてゼロであればエラーはないが、ゼロでないシンドローム値があれば受信データにエラーが含まれることを意味する。

誤り位置多項式生成部２は、シンドローム値ｓ_１〜ｓ_２ｔを用いて、例えばピーターソン法、ユークリッド法あるいはＢＭ法などによりシグマ値σ_１〜σ_ｔを算出し、誤り位置多項式σ（ｚ）を生成する。シグマ値σ_１〜σ_ｔは、下記（１）式で表される誤り位置多項式σ（ｚ）の係数である。
σ（ｚ）＝１＋σ_１ｚ＋σ_２ｚ^２＋ ・・・ ＋σ_ｔｚ^ｔ ・・・（１）
＝１＋Σσ_ｋｚ^ｋ ・・・（１’）
また、誤り位置多項式生成部２は、誤り位置多項式σ（ｚ）の最高次数に基づいて、受信データにおけるエラー数を見積もることもできる。エラー数の見積もり値はチェン探索処理部３に供給される。

図２は、エラー数の見積もり値とシグマ値σ_１〜σ_ｔとの関係を示す図である。図示のように、エラー数の見積もり値がｋ（ｋはｔ以下の整数）であれば、σ値σ_１〜σ_ｋは０以外の値となり、σ_ｋ＋１〜σ_ｔは０となる。

図１に戻り、チェン探索処理部３はチェン探索処理を行って誤り位置多項式σ（ｚ）の根を算出し、誤り位置を検出する。チェン探索処理とは、誤り位置多項式σ（ｚ）にαのべき乗α^ｉ（ｉ＝１〜ｔ）を逐次代入し、誤り位置多項式σ（α^ｉ）がゼロになるかどうかを調べる手法である。α^ｉと誤り位置は１対１に対応しているため、誤り位置多項式σ（ｚ）の根を算出すれば、誤り位置を検出できる。なお、αはガロア体ＧＦ（ｍ^ｑ）の原始元である。

図３は、チェン探索処理部３の内部構成の一例を示す図である。チェン探索処理部３は、シグマ値σ_１〜σ_ｔにそれぞれ対応して設けられる入力部３１１〜３１ｔと、判定部３２とを有する。入力部３１ｋ（ｋ＝１〜ｔ）は誤り位置多項式σ（α^ｉ）の各項σ_ｋα^ｉｋを計算する。判定部３２は、まず、各項σ_ｋα^ｉｋを加算してΣσ_ｋα^ｉｋ、つまり、上記（１’）式の誤り位置多項式σ（α^ｉ）の２項目を生成する。そして、Σσ_ｋα^ｉｋ＝−１であれば、判定部３２はα^ｉが誤り位置多項式σ（ｚ）の根であると判定する。上記（１’）式よりΣσ_ｋα^ｉｋ＝−１のときσ（α^ｉ）＝０となるためである。

チェン探索処理では、入力部３１ｋが各項σ_ｋα^ｉｋをｉ＝０，１・・・ｔの順に逐次計算し、その都度、判定部３２はα^ｉが誤り位置多項式σ（ｚ）の根であるか否かを判定する。なお、ｉ＝ｔまで逐次計算し、根がエラー数の見積もり値未満の回数しか得られなかった場合には、訂正能力ｔを超える誤りがあったものと判断され、訂正不可として処理される。

以下、本実施形態の特徴の１つであるチェン探索処理部３について詳しく説明する。なお、入力部３１１〜３１ｔの内部構成は同様なので、入力部３１ｋについて説明する。

図４は、第１の実施形態に係るチェン探索処理部３の入力部３１ｋの概略構成を模式的に示すブロック図である。チェン探索処理部３の入力部３１ｋは、クロック制御部１１ｋと、バッファ１２ｋと、多項式生成部１３ｋとを有する。

クロック制御部１１ｋは、シグマ値σ_ｋの値に応じて、クロック信号ＣＬＫを停止または出力して、バッファ１２ｋに供給する。

より具体的には、クロック制御部１１ｋは、σ値判定部１１１ｋと、セレクタ１１２ｋと、フリップフロップ１１３ｋと、ゲーテッドクロック生成部１１４ｋとを有する。

σ値判定部１１１ｋは、シグマ値σ_ｋが０であればハイを、０でなければロウを出力する。セレクタ１１２ｋは、スタート信号ＳＴがハイであればσ値判定部１１１ｋの出力信号を選択し、ロウであればフリップフロップ１１３ｋの出力信号を選択して、出力する。フリップフロップ１１３ｋは、クロック信号ＣＬＫに同期してセレクタ１１２ｋの出力信号を保持し、クロック停止信号ＣＬＫ Ｄｉｓａｂｌｅとして出力する。ゲーテッドクロック生成部１１４ｋは、クロック停止信号ＣＬＫ Ｄｉｓａｂｌｅがロウであれば所定の周期でスイッチングするクロック信号ＣＬＫをゲーテッドクロック信号Ｇ−ＣＬＫとして出力し、クロック停止信号ＣＬＫ Ｄｉｓａｂｌｅがハイであればゲーテッドクロック信号Ｇ−ＣＬＫを停止する。

なお、スタート信号ＳＴおよびクロック信号ＣＬＫは、入力部３１１〜３１ｔ内のクロック制御部１１１〜１１ｔに共通して入力される。

バッファ１２ｋは、多項式生成部１３ｋ内の複数のフリップフロップが同期して動作するよう、クロック制御部１１ｋから出力されたゲーテッドクロック信号Ｇ−ＣＬＫを駆動するＣＴＳ（Clock Tree Synthesis）用の回路である。ゲーテッドクロック信号Ｇ−ＣＬＫのスイッチングにより、バッファ１２ｋには消費電流が流れる。

多項式生成部１３ｋは、バッファ１２ｋにより駆動されたゲーテッドクロック信号Ｇ−ＣＬＫに同期して、誤り位置多項式σ（ｚ）の一部を算出する。

より具体的には、多項式生成部１３ｋは、セレクタ１３１ｋと、フリップフロップ１３２ｋと、乗算器１３３ｋと、フリップフロップ１３４ｋとを有する。セレクタ１３１ｋは、スタート信号ＳＴがハイであればシグマ値σ_ｋを選択し、ロウであれば乗算器１３３ｋの出力信号を選択して、出力する。フリップフロップ１３２ｋは、バッファ１２ｋにより駆動されたゲーテッドクロック信号Ｇ−ＣＬＫに同期して、入力される値を保持する。乗算器１３３ｋは入力される値にα^ｋを乗じる。フリップフロップ１３４ｋは、バッファ１２ｋにより駆動されたゲーテッドクロック信号Ｇ−ＣＬＫに同期して、乗算器１３３ｋの出力信号を判定部３２に出力する。

以下、シグマ値σ_ｋが０でない場合と０である場合とに分けて、チェン探索処理部３の処理動作を説明する。

図５は、シグマ値σ_ｋが０でない場合の、入力部３１ｋの各部の信号波形図である。シグマ値σ_ｋが０でないため、σ値判定部１１１ｋはロウを出力している。よって、クロック停止信号ＣＬＫ Ｄｉｓａｂｌｅはロウのままであり、ゲーテッドクロック生成部１１４ｋはクロック信号ＣＬＫをゲーテッドクロック信号Ｇ−ＣＬＫとして出力する。

これにより、フリップフロップ１３２ｋが動作し、乗算器１３３ｋはσ_ｋにα^ｋを乗じてまずσ_ｋα^ｋを生成する。σ_ｋα^ｋは図３の判定部３２へ出力され、判定部３２はα^ｋが誤り位置多項式σ（ｚ）の根であるか否かを判定する。

続いて、乗算器１３３ｋから出力されるσ_ｋα^ｋがセレクタ１３１ｋおよびフリップフロップ１３２ｋを介して乗算器１３３ｋへ入力され、乗算器１３３ｋはさらにα^ｋを乗じてσ_ｋα^２ｋを生成する。そして、判定部３２はα^２ｋが誤り位置多項式σ（ｚ）の根であるか否かを判定する。以下同様にして、α^ｉ（ｉ＝１〜ｔ）が誤り位置多項式σ（ｚ）の根であるか否かが順繰りに判定される。上述のように、α^ｉは誤り位置と１対１に対応しているため、誤り位置多項式σ（ｚ）の根から誤り位置を検出できる。

次に、シグマ値σ_ｋが０である場合の入力部３１ｋの処理動作について説明する。シグマ値σ_ｋの値が０である場合、多項式生成部１３ｋは０を出力し続ければよい。しかしながら、仮に入力部３１ｋにクロック制御部１１ｋを設けないと、シグマ値σ_ｋの値が０であっても図５と同様にバッファ１２ｋにスイッチングするゲーテッドクロック信号Ｇ−ＣＬＫが入力され、バッファ１２ｋに無駄な消費電流が流れてしまう。

これに対し、本実施形態の入力部３１ｋは以下のように動作して、無駄な消費電流の低減を図る。

図６は、シグマ値σ_ｋが０である場合の、入力部３１ｋの各部の信号波形図である。シグマ値σ_ｋが０であるため、σ値判定部１１１ｋはハイを出力している。スタート信号ＳＴがハイになると、セレクタ１１２ｋはσ値判定部１１１ｋが出力するハイを、フリップフロップ１１３ｋに出力する。次いで、クロック信号ＣＬＫ（図６には不図示）が立ち上がると、フリップフロップ１１３ｋはクロック停止信号ＣＬＫ Ｄｉｓａｂｌｅをハイに設定する。その後、ゲーテッドクロック信号Ｇ−ＣＬＫは停止する。

その結果、ゲーテッドクロック信号Ｇ−ＣＬＫがスイッチングしなくなり、バッファ１２ｋの消費電流を低減できる。

このように、第１の実施形態では、クロック制御部１１ｋを設けて、シグマ値σ_ｋが０でない場合はクロック信号をバッファ１２ｋに供給して誤り位置多項式σ（ｚ）の根を判定する一方、シグマ値σ_ｋが０である場合はバッファ１２ｋに供給するゲーテッドクロック信号Ｇ−ＣＬＫを停止する。そのため、バッファ１２ｋに流れる消費電流を低減できる。

（第２の実施形態）
上述した第１の実施形態は、１つの入力部３１ｋに対して１つのクロック制御部１１ｋを設けるものであったが、以下に説明する第２の実施形態では、複数の入力部に対して１つのクロック制御部を設けるものである。

本実施形態では、シグマ値σ_１〜σ_ｔを、それぞれが複数のシグマ値を含むいくつかの係数群にグループ化する。例えば、係数群のそれぞれが、４つずつのシグマ値σ_１〜σ_４，σ_５〜σ_８等を含むようにする。そして、１つの係数群につき１つのクロック制御部を設ける。以下、シグマ値σ_Ｎ〜σ_Ｍ（Ｎ＜Ｍ≦ｔ）を含む係数群に対応する入力部３１Ｎ’〜３１Ｍ’について説明する。

図７は、第２の実施形態に係るチェン探索処理部３の入力部３１Ｎ’〜３１Ｍ’の概略構成を模式的に示す図である。なお、図７では、図４と共通する構成部分には同一または類似の符号を付しており、以下では相違点を中心に説明する。また、図７では、便宜上、入力部３１Ｎ’内にクロック制御部１１Ｎ’を設けている。

クロック制御部１１Ｎ’は、σ値判定部１１１Ｎ〜１１１Ｍと、ＡＮＤ回路１１５Ｎと、セレクタ１１２Ｎと、フリップフロップ１１３Ｎと、ゲーテッドクロック生成部１１４Ｎとを有する。ＡＮＤ回路１１５Ｎはσ値判定部１１１Ｎ〜１１１Ｍの出力信号の論理積を出力する。すなわち、ＡＮＤ回路１１５Ｎは、シグマ値σ_Ｎ〜σ_Ｍのすべてが０であればハイを、少なくとも１つが０でなければロウを出力する。その他の動作は図４と同様である。

シグマ値σ_Ｎ〜σ_Ｍのすべてが０である場合、多項式生成部１３Ｎ〜１３Ｍはいずれも０を出力し続ければよい。したがって、クロック制御部１１Ｎ’がバッファ１２Ｎ〜１２Ｍに供給されるゲーテッドクロック信号Ｇ−ＣＬＫを停止することにより、消費電流を低減できる。

一方、シグマ値σ_Ｎ〜σ_Ｍの少なくとも１つが０でない場合、多項式生成部１３Ｎ〜１３Ｍが動作して、判定部３２は誤り位置多項式σ（ｚ）の根を判定する。ここで、例えばシグマ値σ_Ｎ〜σ_Ｍ−１が０でなくσ_Ｍが０である場合、シグマ値σ_ｋごとにクロック制御部１１ｋを設ける第１の実施形態比べると、０を出力し続ければよいシグマ値σ_Ｍに対応するバッファ１２Ｍには無駄な消費電流が流れてしまうが、誤り検出装置の面積を小型化できる。

なお、係数群に含まれるシグマ値の数は任意でよい。例えば係数群に含まれるシグマ値の数を多くすれば、誤り検出装置の面積をより小型化できる。

このように、第２の実施形態では、複数のシグマ値に対して１つのクロック制御部を設ける。そのため、より小型な誤り検出装置１００で消費電流を低減できる。

（第３の実施形態）
上述した第１および第２の実施形態は、各シグマ値σ_ｋが０か否かに基づいてバッファ１２ｋに入力されるゲーテッドクロック信号Ｇ−ＣＬＫを制御するものであった。これに対し、以下に説明する第３の実施形態は、エラー数の見積もり値に基づいてゲーテッドクロック信号Ｇ−ＣＬＫを制御する。

本実施形態は、第２の実施形態と同様にシグマ値σ_１〜σ_ｔを、それぞれが複数のシグマ値を含むいくつかの係数群にグループ化し、図２の関係に着目して誤り検出装置１０１の消費電力を削減するものである。

図８は、第３の実施形態に係るチェン探索処理部３の入力部３１Ｎ’’〜３１Ｍ’’の概略構成を模式的に示す図である。以下、図７との相違点を中心に説明する。

クロック制御部１１Ｎ’’は、σ値判定部に代えて、見積もり値判定部１１６Ｎを有する。見積もり値判定部１１６Ｎは、エラー数の見積もり値がＮより小さければハイを、Ｎ以上であればロウを出力する。

エラー数の見積もり値がＮより小さい場合、図２よりシグマ値σ_Ｎ〜σ_Ｍはいずれも０となる。そのため、第２の実施形態と同様に、ゲーテッドクロック信号Ｇ−ＣＬＫを停止して、消費電流を低減する。

一方、エラー数の見積もり値がＮ以上の場合、図２よりシグマ値σ_Ｎ〜σ_Ｍのうちの少なくとも１つは０でない。そのため、第２の実施形態と同様に、スイッチングするゲーテッドクロック信号Ｇ−ＣＬＫを生成して、誤り位置多項式の根を算出する。

このように、第３の実施形態では、エラー数の見積もり値に応じて、ゲーテッドクロック信号Ｇ−ＣＬＫを制御する。そのため、バッファ１２ｋに流れる消費電流を低減できる。

各実施形態で説明した誤り検出装置１００は、例えばメモリシステムに用いることができる。図９は、誤り検出装置を有するメモリシステムの概略構成を示すブロック図である。メモリシステムは、記憶装置５０と、そのコントローラ６０とを備えている。記憶装置５０は、例えばＮＡＮＤ型フラッシュメモリ等の半導体記憶装置である。コントローラ６０は記憶装置５０への書き込みおよび読み出しを制御する。また、コントローラ６０は、上述した誤り検出装置を有し、記憶装置５０から読み出された値のエラーを検出する。

記憶装置５０の記憶容量が大きい場合でも、誤り検出装置は低消費電力でエラーを検出できる。

その他、誤り検出装置を通信システム等に用いることもできる。

本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれると同様に、特許請求の範囲に記載された発明とその均等の範囲に含まれるものである。

１ シンドローム処理部
２ 誤り位置多項式生成部
３ チェン探索処理部
３１１〜３１ｔ 入力部
３２ 判定部
１１ｋ クロック制御部
１２ｋ バッファ
１３ｋ 多項式生成部
１００ 誤り検出装置

Claims (5)

1. 受信データに基づいてシンドローム値を生成するシンドローム処理部と、
   前記シンドローム値に基づいて誤り位置多項式の係数を生成する誤り位置多項式生成部と、
   前記誤り位置多項式の根を算出して誤り位置を検出する探索処理部と、を備え、
   前記探索処理部は、
   前記係数の値に応じてクロック信号を出力または停止するクロック制御部と、
   前記クロック制御部から出力されたクロック信号を駆動するバッファと、
   前記バッファにより駆動されたクロック信号に同期して前記誤り位置多項式の一部を算出する多項式生成部と、
   前記誤り位置多項式の一部に基づいて、前記誤り位置多項式の根を算出する判定部と、を有することを特徴とする誤り検出装置。
2. 前記クロック制御部は、前記係数の値がゼロであれば前記クロック信号を停止し、前記係数がゼロでなければ前記クロック信号を出力することを特徴とする請求項１に記載の誤り検出装置。
3. 前記クロック制御部は、前記係数のそれぞれに対応して設けられることを特徴とする請求項１または２に記載の誤り検出装置。
4. 前記クロック制御部は、前記係数のうち２以上の前記係数を含む係数群に対応して設けられ、前記係数群に含まれる前記係数の全てがゼロである場合は前記クロック信号を停止することを特徴とする請求項１または２に記載の誤り検出装置。
5. 前記誤り位置多項式生成部は、ｔ個の前記係数を生成するとともに、前記受信データにおけるエラー数を見積もり、
   前記クロック制御部は、前記係数のうちＮ〜Ｍ番目（Ｎ，ＭはＮ，Ｍ≦ｔを満たす任意の正の整数）の前記係数を含む係数群に対応して設けられ、前記見積もられたエラー数がＮより小さい場合は、前記Ｎ〜Ｍ番目の前記係数を含む係数群に対する前記クロック信号を停止することを特徴とする請求項１に記載の誤り検出装置。

Images