(57)【特許請求の範囲】
【請求項１】
リードソロモン符号の生成多項式の根を用いて、複数のシンボルからなる入力シンボル列に対するシンドロームを算出するシンドローム算出部と、
前記シンドローム算出部により算出されたシンドロームを用いて、前記入力シンボル列に含まれる誤りシンボルの数および誤り位置多項式の係数を算出する誤り位置多項式係数算出部と、
前記算出された係数を有する誤り位置多項式に基づき、前記入力シンボル列に含まれる誤りシンボルの位置である誤り位置を探索する誤り位置探索部と、
前記探索された誤り位置における誤りシンボルを訂正する誤り訂正部と、
を含んで構成されたリードソロモン符号・復号化回路であって、
前記誤り位置探索部は、
前記入力シンボル列のシンボルの位置を表す位置データを順次変更して、前記誤り位置多項式の値が０になる誤り位置を探索する複数のチェン探索回路と、
前記複数のチェン探索回路のそれぞれに１つずつ対応するように設けられ、前記位置データが順次変更されていくとき、前記複数のチェン探索回路のそれぞれによって探索される前記誤り位置の数をそれぞれカウントする複数のカウンタと、
前記複数のカウンタの値を加算して出力する加算器と、
前記複数のチェン探索回路の動作を制御する探索制御回路と、
を備え、
前記探索制御回路は、
前記入力シンボル列のそれぞれ異なるシンボルの位置についての誤り位置の探索を、前記複数のチェン探索回路に互いに独立に並行して実行させ、
前記加算器の出力が前記誤りシンボルの数と等しくなったとき、前記チェン探索回路における前記誤り位置の探索を終了させること
を特徴とするリードソロモン符号・復号化回路。
【請求項２】
リードソロモン符号の生成多項式の根を用いて、複数のシンボルからなる入力シンボル列に対するシンドロームを算出するシンドローム算出部と、
前記シンドローム算出部により算出されたシンドロームを用いて、前記入力シンボル列に含まれる誤りシンボルの数および誤り位置多項式の係数を算出する誤り位置多項式係数算出部と、
前記入力シンボル列のシンボルの位置を表す位置データを順次変更して、前記算出された係数を有する誤り位置多項式の値が０になるシンボルの位置を誤り位置として探索する複数のチェン探索回路、前記複数のチェン探索回路のそれぞれに１つずつ対応するように設けられ、前記位置データが順次変更されていくとき、前記複数のチェン探索回路のそれぞれによって探索される前記誤り位置の数をそれぞれカウントする複数のカウンタ、前記複数のカウンタの値を加算して出力する加算器、および、前記複数のチェン探索回路の動作を制御する探索制御回路を有し、前記入力シンボル列に含まれる誤り位置を探索する誤り位置探索部と、
前記探索された誤り位置における誤りシンボルを訂正する誤り訂正部と、
を含んで構成されたリードソロモン符号・復号化回路におけるリードソロモン符号・復号化方法であって、
前記誤り位置探索部において前記探索制御回路は、
前記入力シンボル列のそれぞれ異なるシンボルの位置についての誤り位置の探索を、前記複数のチェン探索回路に互いに独立に並行して実行させ、
前記加算器の出力が前記誤りシンボルの数と等しくなったとき、前記チェン探索回路における前記誤り位置の探索を終了させること
を特徴とするリードソロモン符号・復号化方法。
【請求項３】
書き込みデータを符号化するリードソロモン符号・符号化回路と、読み出しデータを復号化するリードソロモン符号・復号化回路と、を備えた記憶装置であって、
前記リードソロモン符号・復号化回路は、
リードソロモン符号の生成多項式の根を用いて、複数のシンボルからなる入力シンボル列に対するシンドロームを算出するシンドローム算出部と、
前記シンドローム算出部により算出されたシンドロームを用いて、前記入力シンボル列に含まれる誤りシンボルの数および誤り位置多項式の係数を算出する誤り位置多項式係数算出部と、
前記算出された係数を有する誤り位置多項式に基づき、前記入力シンボル列に含まれる誤りシンボルの位置である誤り位置を探索する誤り位置探索部と、
前記探索された誤り位置における誤りシンボルを訂正する誤り訂正部と、
を含んで構成され、
前記誤り位置探索部は、
前記入力シンボル列のシンボルの位置を表す位置データを順次変更して、前記誤り位置多項式の値が０になる誤り位置を探索する複数のチェン探索回路と、
前記複数のチェン探索回路のそれぞれに１つずつ対応するように設けられ、前記位置データが順次変更されていくとき、前記複数のチェン探索回路のそれぞれによって探索される前記誤り位置の数をそれぞれカウントする複数のカウンタと、
前記複数のカウンタの値を加算して出力する加算器と、
前記複数のチェン探索回路の動作を制御する探索制御回路と、
を備え、
前記探索制御回路は、
前記入力シンボル列のそれぞれ異なるシンボルの位置についての誤り位置の探索を、前記複数のチェン探索回路に互いに独立に並行して実行させ、
前記加算器の出力が前記誤りシンボルの数と等しくなったとき、前記チェン探索回路における前記誤り位置の探索を終了させること
を特徴とする記憶装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、リードソロモン符号復号化回路、リードソロモン符号復号化方法、および、リードソロモン符号復号化回路を備えた記憶装置に関する。
【背景技術】
【０００２】
近年、ハードディスク記憶装置を代替する記憶装置として、半導体のフラッシュメモリで構成されたＳＳＤ（Solid State Drive）記憶装置が注目を集めている。ＳＳＤ記憶装置は、可動部品を含まないため、動作の信頼性が高い、アクセス時間が短い、小型化し易い、など多くの長所を有している。一方で、ＳＳＤ記憶装置は、その構成要素であるフラッシュメモリが超微細加工技術を駆使して製造されているため、一部のビット欠けを除去できない、あるいは、データ書き込み・消去に伴う疲労現象のために、データの書き込み回数に制限（例えば、１０万回）がある、などの欠点も有している。そこで、ＳＳＤ記憶装置においては、これらの欠点をカバーするために、データの誤り訂正技術やデータの書き込み回数の平準化技術など様々な技術が導入されている。
【０００３】
ＳＳＤ記憶装置における誤り訂正のための符号としては、いわゆるリードソロモン符号が用いられている。リードソロモン符号は、複数ワードの誤りを訂正することが可能な、訂正能力に優れた符号であり、すでに、ＤＶＤ（Digital Versatile Disk）、衛星通信、地上波ディジタル放送などの分野で広く応用されている。一方、リードソロモン符号における、とくに、復号化の手順や回路は、決して簡単といえるものではなく、それゆえ、その復号化に要する時間が長くなるという弱点も有している。
【０００４】
リードソロモン符号の符号化・復号化の手順や回路については、符号理論やその応用を解説した教科書（例えば、非特許文献１）などに示されている。また、特許文献１には、リードソロモン符号の復号化回路の中でもとくに複雑とされているチェン探索回路（チェン・サーチ回路）の回路構成を簡略化する技術が開示されている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開平６−３１４９７８号公報
【非特許文献】
【０００６】
【非特許文献１】金子敏信、外９名、「誤り訂正符号とその応用」、第１版、オーム社、平成８年１２月２５日、ｐ．１０７−１２２，ｐ．１７７−１８９
【発明の概要】
【発明が解決しようとする課題】
【０００７】
ＳＳＤ記憶装置においてリードソロモン符号の復号化に時間が掛かることは、ＳＳＤ記憶装置に記憶されたデータのアクセス時間が増大することを意味し、そのアクセス時間の増大は、ＳＳＤ記憶装置の主たる性能を低下させることを意味する。多くの場合、ＳＳＤ記憶装置は、ハードディスク記憶装置と同様に、コンピュータの補助記憶装置として用いられるが、コンピュータの多くのユーザにとって、ＳＳＤ記憶装置などの補助記憶装置のアクセス時間は短いほうが好ましい。コンピュータの処理能力は、しばしば、補助記憶装置の性能に制約される場合があるからである。
【０００８】
そこで、本発明の目的は、リードソロモン符号の復号化時間を短縮することができるリードソロモン符号・復号化回路、リードソロモン符号・復号化方法、および、そのリードソロモン符号・復号化回路を備えた記憶装置を提供することにある。
【課題を解決するための手段】
【０００９】
本発明に係るリードソロモン符号・復号化回路は、リードソロモン符号の生成多項式を用いて、複数のシンボルからなる入力シンボル列に対するシンドロームを算出するシンドローム算出部と、そのシンドローム算出部により算出されたシンドロームを用いて、前記入力シンボル列に含まれる誤りシンボルの数および誤り位置多項式の係数を算出する誤り位置多項式係数算出部と、その算出された係数を有する誤り位置多項式に基づき、前記入力シンボル列に含まれる誤りシンボルの位置である誤り位置を探索する誤り位置探索部と、その探索された誤り位置における誤りシンボルを訂正する誤り訂正部と、を含んで構成される。
【００１０】
そして、その誤り位置探索部は、前記入力シンボル列のシンボルの位置を表す位置データを順次変更して、前記誤り位置多項式の値が０になる誤り位置を探索する複数のチェン探索回路と、前記複数のチェン探索回路のそれぞれに１つずつ対応するように設けられ、前記位置データが順次変更されていくとき、前記複数のチェン探索回路のそれぞれによって探索される前記誤り位置の数をそれぞれカウントする複数のカウンタと、前記複数のカウンタの値を加算して出力する加算器と、前記複数のチェン探索回路の動作を制御する探索制御回路と、を備え、その探索制御回路は、前記入力シンボル列のそれぞれ異なるシンボルの位置についての誤り位置の探索を、前記複数のチェン探索回路に互いに独立に並行して実行させ、前記加算器の出力が前記誤りシンボルの数と等しくなったとき、前記チェン探索回路における前記誤り位置の探索を終了させることを特徴とする。
【００１１】
本発明のリードソロモン符号・復号化回路では、誤り位置の探索が複数のチェン探索回路により互いに独立に並行して行われるので、誤り位置探索時間が短縮される。しかも、その複数のチェン探索回路により検知された誤り位置の数が誤り位置多項式係数算出部で求められていた誤りシンボルの数と同じになったとき、その複数のチェン探索回路における誤り位置の探索は終了されるので、誤り位置探索時間は、さらに短縮される。以上のようにして、誤り位置探索時間が短縮される結果として、本発明のリードソロモン符号・復号化回路における復号化時間が短縮される。
【発明の効果】
【００１２】
本発明によれば、リードソロモン符号の復号化時間を短縮することができるリードソロモン符号・復号化回路、リードソロモン符号・復号化方法、および、そのリードソロモン符号・復号化回路を備えた記憶装置が提供される。
【図面の簡単な説明】
【００１３】
【図１】本発明の実施形態に係るＳＳＤ記憶装置の機能ブロックの構成の例を示した図。
【図２】本発明の実施形態に係るＮＦＣ（ＮＡＮＤ型フラッシュメモリチップ）におけるブロック、ページおよびセクタの構成の例を示した図。
【図３】本発明の実施形態に係るＲＳ符号・復号化回路の構成の例を示した図。
【図４】本発明の実施形態に係るＲＳ符号・復号化回路における誤り位置探索の処理の流れの例を示した図。
【発明を実施するための形態】
【００１４】
以下、本発明の実施形態について、図面を参照して詳細に説明する。
【００１５】
図１は、本発明の実施形態に係るＳＳＤ記憶装置の機能ブロックの構成の例を示した図である。
図１に示すように、ＳＳＤ記憶装置２は、ホストバス３を介してホスト装置１に接続されて用いられる。ここで、ホスト装置１は、ＳＳＤ記憶装置２にデータやプログラムを記憶するコンピュータ、またはコンピュータを応用した様々な制御装置などである。このとき、ホスト装置１とＳＳＤ記憶装置２とを接続するホストバス３としては、通常、ＳＣＳＩ（Small Computer System Interface）バス、ＩＤＥ（Integrated Drive Electronics）バスなどが用いられる。
【００１６】
また、図１において、ＳＳＤ記憶装置２は、ＳＳＤ制御部４およびＳＳＤ記憶媒体部５により構成される。そして、ＳＳＤ制御部４は、ホストインタフェース部４１、コマンド処理制御部４２、ページデータ書込部４３、ページデータ読出部４５、ブロック状態管理部４７などを含んで構成される。ページデータ書込部４３は、リードソロモン符号（以下、ＲＳ符号と略称）・符号化回路４４を備え、また、ページデータ読出部４５は、ＲＳ符号・復号化回路４６を備えている。一方、ＳＳＤ記憶媒体部５は、複数のＮＡＮＤ型フラッシュメモリチップ（以下、ＮＦＣと略称）５１を含んで構成される。図１の例では、ＳＳＤ記憶媒体部５は、２４個のＮＦＣ５１により構成されている。なお、図１において、矢印付きの太線は、データの流れを示し、矢印付きの破線は、概略の制御信号の流れを示す。
【００１７】
図２は、本発明の実施形態に係るＮＦＣ５１におけるブロック、ページおよびセクタの構成の例を示した図である。図２（ａ）および（ｂ）に示すように、ＮＦＣ５１は、Ｎｂ個のブロック５２により構成され、また、１つのブロック５２は、Ｎ個のページ５３により構成される。なお、ＮＦＣ５１において、ブロック５２は、データ消去の単位であり、また、ページ５３は、データの書き込みまたは読み出しの単位である。
【００１８】
続いて、図２（ｃ）に示すように、１つのページ５３には、ヘッダ（２６Ｂ）と８つのセクタ（各５３６Ｂ）とからなるページデータが記憶される（以下、Ｂは、バイトの略、ｂは、ビットの略とし、１Ｂ＝８ｂであるとする）。さらに、図２（ｄ）に示すように、１つのセクタは、データ（５１２Ｂ）と、ＣＲＣ（Cyclic Redundancy Check）検査符号（４Ｂ）と、ＲＳ訂正符号（２０Ｂ）と、によって構成される。
【００１９】
従って、１つのページ５３には、４ｋＢのデータが記憶される。このとき、１つのブロック５２を構成するページ５３の数Ｎを、Ｎ＝６４とすれば、１つのブロック５２には、２５６ｋＢのデータが記憶されることになる。そして、１つのＮＦＣ５１の記憶容量が、例えば、４ＧＢである場合には、１つのＮＦＣ５１を構成するブロック５２の数Ｎｂは、１６ＫＢ（Ｎｂ＝１６，３８４）となる。
【００２０】
再び、図１戻って、ＳＳＤ制御部４の動作について説明する。
図１において、ホストインタフェース部４１は、ホストバス３に対する電気的なインタフェースを整合させるとともに、ホストバス３に定義された通信のプロトコルに従って、ホスト装置１との間でコマンドやデータなどの送受信を行う。
【００２１】
コマンド処理制御部４２は、ホストインタフェース部４１を介して、ホスト装置１から送信される各種のコマンド（例えば、ページデータ書き込みコマンド、ページデータ読み出しコマンドなど）を受信し、それぞれのコマンドに応じてあらかじめ定められた処理を実行する。
【００２２】
例えば、コマンド処理制御部４２がホスト装置１からページデータ書き込みコマンドを受信した場合には、コマンド処理制御部４２は、ホストインタフェース部４１に対し、そのページデータ書き込みコマンドに付属または後続してホスト装置１から送信されるページアドレスおよびデータを受信し、その受信したページアドレスおよびデータを図示しない一時データ記憶部に格納することを指示する。さらに、ページデータ書込部４３に対し、その一時データ記憶部に格納されたデータを、前記ページアドレスで指定されるＮＦＣ５１内のページ５３へ書き込むことを指示する。
【００２３】
ページデータ書込部４３は、コマンド処理制御部４２からページデータの書き込み指示を受けると、図示しない一時データ記憶部に格納されたデータを、図２（ｃ）に示した形式のページデータに整形する。ページデータ書込部４３は、そのページデータへの整形に際しては、セクタデータごとに、図示しないＣＲＣ生成回路を用いてＣＲＣ検査符号（４Ｂ）を生成し、また、ＲＳ符号・符号化回路４４を用いてＲＳ訂正符号（２０Ｂ）を生成する。
【００２４】
さらに、ページデータ書込部４３は、当該ページデータ書き込みコマンドに付属したページアドレス（論理アドレス）を、所定の変換規則に従って、ＳＳＤ記憶媒体部５内のすべてのＮＦＣ５１に含まれるページ５３を一意に識別可能な物理アドレスに変換し、前記整形したページデータを、その物理アドレスによって識別されるＮＦＣ５１内のページ５３へ書き込む。
【００２５】
また、コマンド処理制御部４２は、ホスト装置１からページデータの読み出しコマンドを受信した場合には、ページデータ読出部４５に対し、そのコマンドに付属したページアドレスで指定されるＮＦＣ５１内のページ５３からページデータを読み出すことを指示する。さらに、コマンド処理制御部４２は、ページデータ読出部４５によって、そのページデータがＮＦＣ５１から読み出されたときには、ホストインタフェース部４１に対し、その読み出されたページデータからヘッダ、ＣＲＣ検査符号およびＲＳ訂正符号を除去したデータをホスト装置１へ送信することを指示する。
【００２６】
ページデータ読出部４５は、コマンド処理制御部４２からページデータの読み出し指示を受けると、当該ページデータ読み出しコマンドに付属したページアドレス（論理アドレス）を、所定の変換規則に従って、ＳＳＤ記憶媒体部５内のすべてのＮＦＣ５１に含まれるページ５３を一意に識別可能な物理アドレスに変換し、その物理アドレスによって識別されるＮＦＣ５１内のページ５３からページデータを読み出す。
【００２７】
また、ページデータ読出部４５は、読み出したページデータからヘッダ、ＣＲＣ検査符号およびＲＳ訂正符号を除去するに際しては、ＲＳ符号・復号化回路４６を用いて、図２（ｄ）に示したセクタデータの内のデータおよびＣＲＣ検査符号部分におけるデータ誤りを訂正し、さらに、図示しないＣＲＣ検査回路を用いて、データ部分におけるデータ誤りの有無（すなわち、誤訂正の有無）を検査する。
【００２８】
また、ブロック状態管理部４７は、図示しない欠陥ブロックテーブルなどを有し、その欠陥ブロックテーブルに、欠陥ブロックを識別するブロックのアドレス（物理アドレス）を記憶しておき、ページデータ書込部４３によるページデータの書き込みに際し、その欠陥ブロックが使用されないように管理する。なお、欠陥ブロックとは、ブロックデータを消去できないようなブロック５２、ページデータの書き込みができないページ５３や読み出したページデータに訂正不可能な誤りが生じるようなページ５３が所定数以上含まれるようなブロック５２などをいう。
【００２９】
なお、ＳＳＤ制御部４は、以上の他にも、各ページ５３へのページデータの書き込み回数を平準化するような機能を有する機能ブロックなど、様々な機能ブロックを含んでいるが、ここでは、それらの機能ブロックの説明を省略する。
【００３０】
続いて、本実施形態で用いられるＲＳ符号の概要について説明する。ＲＳ符号は、複数のシンボル誤りを訂正することが可能な符号としてよく知られている。ここで、シンボルとは、例えば、ｍビットのデータであり、誤り訂正は、シンボルを単位として行われる。なお、シンボルがｍビットである場合、ＲＳ符号により訂正可能な符号長（追加される訂正用の冗長シンボルを含む）の最大値は、２ｍ−１シンボルとされている。
【００３１】
一般には、１シンボルを１バイトのデータに対応させることが多いが、本実施形態の場合、図２（ｄ）に示したように、１つのセクタデータは、５３６Ｂであるので、５３６Ｂのデータにおける誤り訂正を可能にするために、ｍ＝１０とする。すなわち、本実施形態では、１シンボルは、１０ビットのデータであるとする。そのため、セクタを構成する各バイトのデータ（８ビット）には、例えば、“００”など、所定の２ビットのデータが追加されて、１０ビットのデータ、つまり、シンボルとして取り扱われる。
【００３２】
また、ＲＳ符号においては、ｔ個のシンボル誤りを訂正するには、２ｔ個の冗長シンボルを追加する必要がある。ｔの値は、訂正対象のデータに含まれる誤り率などに応じて、適宜定めることができるが、ここでは、例えば、ｔ＝８であるとする。従って、冗長シンボルの総ビット数は、１０ビット×２×８＝１６０ビットとなり、この１６０ビットの冗長シンボルのデータを記憶するために、図２（ｄ）に示したセクタデータでは、ＲＳ訂正符号２０Ｂ（＝１６０ビット）が用意されている。
【００３３】
すなわち、本実施形態では、ＲＳ符号・符号化回路４４（図１参照）は、セクタデータ（図２参照）の内、５１２Ｂのデータおよび４ＢのＣＲＣ検査符号の各バイトのデータを１０ビット化した５１６シンボルを入力シンボル列として、１６シンボルのＲＳ訂正符号を生成し、入力シンボル列に追加する。
【００３４】
ここで、ＲＳ符号の定義によれば、１６シンボルのＲＳ訂正符号を生成する生成多項式Ｇ（Ｘ）は、次に示す式（１）で表される。
Ｇ（Ｘ）＝（Ｘ−α）（Ｘ−α２）（Ｘ−α３）・・・（Ｘ−α１６）    式（１）
ここで、αは、いわゆるガロア拡大体ＧＦ（２１０）の元であり、１０次の原始多項式（例えば、Ｘ１０＋Ｘ３＋１＝０）の根である。
【００３５】
また、ＲＳ符号・符号化回路４４への入力シンボル列（以下、入力メッセージという）によって表されるメッセージ多項式Ｍ（Ｘ）は、（入力メッセージのシンボル数−１）次の多項式で表される（本実施形態の場合、５１５次の多項式となる）。そして、そのメッセージ多項式の係数は、各シンボルに対応するガロア拡大体ＧＦ（２１０）の元で表される。
【００３６】
ここで、ＲＳ訂正符号を表す多項式（以下、パリティ多項式という）をＰ（ｘ）と表すと、パリティ多項式Ｐ（ｘ）は、次に示す式（２）により求めることができる。
Ｐ（Ｘ）＝Ｘ１６Ｍ（Ｘ）moduloＧ（Ｘ）                            式（２）
ここで、Ｘ１６Ｍ（Ｘ）moduloＧ（Ｘ）は、多項式Ｘ１６Ｍ（Ｘ）を多項式Ｇ（Ｘ）で割った剰余を表す。
【００３７】
従って、パリティ多項式Ｐ（Ｘ）は、高々１５次の多項式であり、具体的には、次の式（３）で表すことができる。
Ｐ（Ｘ）＝ａ１５Ｘ１５＋ａ１４Ｘ１４＋・・・＋ａ１Ｘ＋ａ０        式（３）
ここで、パリティ多項式Ｐ（Ｘ）の係数ａ１５，ａ１４，・・・，ａ１，ａ０は、いずれも、ガロア拡大体ＧＦ（２１０）の元である。これらの１６個の係数は、入力メッセージに付加される１６シンボル（＝１６０ビット＝２０Ｂ）のＲＳ訂正符号に他ならない。
【００３８】
従って、入力メッセージにＲＳ訂正符号が追加されて得られる符号化多項式Ｃ（Ｘ）は、次の式（４）で表すことができる。
Ｃ（Ｘ）＝Ｘ１６Ｍ（Ｘ）＋Ｐ（Ｘ）
＝Ｑ（Ｘ）Ｇ（Ｘ）                                    式（４）
すなわち、符号化多項式Ｃ（Ｘ）は、生成多項式Ｇ（Ｘ）で割り切ることができる。そして、Ｑ（Ｘ）は、そのときの商を表す多項式である。
【００３９】
以上の説明から分かるように、ＲＳ符号・符号化回路４４は、式（２）に従ってパリティ多項式Ｐ（Ｘ）の係数を算出する回路によって構成される。なお、そのパリティ多項式Ｐ（Ｘ）の係数を算出する回路は、一般に周知の回路であるので、ここでは、その詳細な説明を省略する。
【００４０】
次に、複数シンボルの誤りを訂正するＲＳ符号の復号化手順の概略について説明する。本実施形態では、ＲＳ符号の復号化、すなわち、ＳＳＤ記憶媒体部５からの読み出しデータの誤り訂正は、ＮＦＣ５１のページ５３から読み出されたページデータのセクタデータ（図２（ｄ）参照）を単位として行われる。
【００４１】
なお、セクタデータの復号化においては、符号化（ＲＳ訂正符号の生成）の場合と同様に、読み出されたページデータのセクタデータの内、データ（５１２Ｂ）＋ＣＲＣ検査符号（４Ｂ）については、各バイトのデータ（８ビット）に、例えば、“００”など、所定の２ビットのデータが追加されて、１０ビットのデータ、つまり、シンボルとして取り扱われる。また、２０Ｂ（１６０ビット）のＲＳ訂正符号は、１０ビットの１６個のシンボルに変換される。
【００４２】
従って、ＲＳ符号・復号化回路４６（図１参照）には、全５３２シンボルが入力されることになる。そこで、ＲＳ符号・復号化回路４６へ入力されるシンボルを係数とする多項式を、以下、慣用に従って受信多項式Ｒ（Ｘ）と呼ぶことにすると、受信多項式Ｒ（Ｘ）は、Ｘの５３１次の多項式で表される。
【００４３】
以下、ＲＳ符号・復号化回路４６では、次の手順に従って、復号化すなわち誤りシンボルの訂正が行われる。
（手順１）受信多項式Ｒ（Ｘ）に基づき、シンドローム（Ｓ１，Ｓ２，・・・，Ｓ１６）を算出する。
（手順２）算出されたシンドローム（Ｓ１，Ｓ２，・・・，Ｓ１６）を用いて、誤り位置多項式σ（Ｘ）の最高次数（以下、単に、次数という）と係数を求める。
（手順３）誤り位置多項式σ（Ｘ）を用いて、誤りシンボルの位置を求める。
（手順４）誤りシンボルを訂正する。
【００４４】
図３は、本発明の実施形態に係るＲＳ符号・復号化回路４６の構成の例を示した図である。図３に示すように、ＲＳ符号・復号化回路４６は、シンドローム算出部４６１、誤り位置多項式係数算出部４６２、誤り位置探索部４６３、および、誤り訂正部４６４によって構成される。なお、これらのブロックの機能は、前記の（手順１）〜（手順４）にほぼ対応している。また、図３において、ＲＳ符号・復号化回路４６に入力される入力シンボル列は、ＮＦＣ５１のページ５３から読み出されたページデータのセクタデータに基づく全５３２シンボルにより構成され、受信多項式Ｒ（Ｘ）の係数に相当する。
【００４５】
シンドローム算出部４６１は、（手順１）を実現するための周知のシンドローム算出回路によって構成される。ここで、シンドロームＳｉ（ｉ＝１，２，・・・，１６）とは、次の式（５）によって算出される値である。
Ｓｉ＝Ｒ（αｉ）      （ｉ＝１，２，・・・，１６）            式（５）
なお、αｉ（ｉ＝１，２，・・・，１６）は、生成多項式Ｇ（Ｘ）＝０の根である。つまり、シンドロームＳｉ（ｉ＝１，２，・・・，１６）とは、受信多項式Ｒ（Ｘ）に生成多項式（Ｇ（Ｘ）＝０）の根を代入することにより得られた値ということができる。
【００４６】
なお、ここで、受信多項式Ｒ（Ｘ）に誤りがなかった場合には、受信多項式Ｒ（Ｘ）と符号化多項式Ｃ（Ｘ）は同じ、つまり、Ｒ（Ｘ）＝Ｃ（Ｘ）となる。このとき、式（４）および式（１）を参照すると容易に分かるように、すべてのシンドロームＳｉは０、すなわち、Ｓｉ＝０（ｉ＝１，２，・・・，１６）となる。逆にいえば、すべてのシンドロームＳｉ（ｉ＝１，２，・・・，１６）が０となった場合には、訂正すべき誤りは存在しないことになるので、その後の誤り訂正の処理（（手順２）〜（手順４））を行う必要はない。
【００４７】
一方、シンドロームＳｉ（ｉ＝１，２，・・・，１６）の内、１つでも０でないものがあった場合には、受信多項式Ｒ（Ｘ）に誤りが存在することを意味する。そこで、次に、（手順２）の処理として、誤り位置多項式係数算出部４６２は、誤り位置多項式σ（Ｘ）の次数と係数を求める。
【００４８】
誤り位置多項式σ（Ｘ）は、次の式（６）によって定義される。
σ（Ｘ）＝１＋σ１Ｘ＋σ２Ｘ２＋・・・＋σｋＸｋ              式（６）
ここで、誤り位置多項式σ（Ｘ）の次数ｋは、誤りシンボルの数である。また、誤り位置多項式σ（Ｘ）の係数σｊ（ｊ＝１，２，・・・，ｋ）は、次の式（７）によって定義される。
【数１】
0005667408.tif 000002
【００４９】
まず、誤り位置多項式係数算出部４６２は、式（７）から誤り位置多項式σ（Ｘ）の次数ｋを求める。誤り位置多項式係数算出部４６２は、まず、仮の次数ｋ’の初期値としてｋ’＝ｔ（ｔ＝８：訂正可能なシンボル数の最大値）とおき、シンドロームＳｉ（ｉ＝１，２，・・・，２ｋ−１）で構成された式（７）の左辺の行列式の値を求める。そして、その行列式の値が０でなかった場合には、次数ｋ＝ｋ’＝ｔと定める。
【００５０】
一方、式（７）の左辺の行列式の値が０であった場合には、誤り位置多項式係数算出部４６２は、ｋ’＝ｋ’−１として、同様に、式（７）の左辺の行列式の値を求め、以下、その行列式の値が０でなくなるまで、ｋ’を１つずつ減じながら、同様の処理を繰り返す。そして、式（７）の左辺の行列式の値が０でなくなったときのｋ’の値を、誤り位置多項式σ（Ｘ）の次数ｋと定める（すなわち、ｋ＝ｋ’）。こうして求められた誤り位置多項式σ（Ｘ）の次数ｋは、受信多項式Ｒ（Ｘ）に存在する誤りシンボルの数である（以下、誤りシンボルの数もｋと表記する）。
【００５１】
以上のようにして、誤り位置多項式σ（Ｘ）の次数ｋが定められると、誤り位置多項式係数算出部４６２は、式（７）に基づき、誤り位置多項式σ（Ｘ）の係数σｊ（ｊ＝１，２，・・・，ｋ）を求める。
【００５２】
なお、誤り位置多項式σ（Ｘ）の係数σｊ（ｊ＝１，２，・・・，ｋ）を求める具体的なアルゴリズムとしては、バーレカンプ・マッシイ法（ＢＭ法）など各種のアルゴリズムが開発され、また、そのアルゴリズムに基づく回路も開発されている。従って、そのような周知の回路を用いて誤り位置多項式係数算出部４６２を構成することができるので、ここでは、その説明を省略する。
【００５３】
次に、誤り位置探索部４６３は、（手順３）の処理として、誤り位置多項式σ（Ｘ）を用いて、誤りシンボルの位置を求める。式（６）で表された誤り位置多項式σ（Ｘ）は、ｋ個の誤り位置をβｊ（ｊ＝１，２，・・・，ｋ）とした場合には、次の式（８）が成り立つことが知られている。
σ（Ｘ）＝（１＋β１Ｘ）（１＋β２Ｘ）・・・（１＋βｋＸ）        式（８）
すなわち、式（８）によれば、誤り位置βｊ（ｊ＝１，２，・・・，ｋ）は、誤り位置多項式（σ（Ｘ）＝０）の根の逆数によって与えられる。
【００５４】
誤り位置多項式（σ（Ｘ）＝０）の根の逆数である誤り位置βｊ（ｊ＝１，２，・・・，ｋ）を求める具体的な回路としてチェン探索回路が知られている。チェン探索回路は、式（６）を計算する回路であり、その回路にすべての誤り位置βｊの逆数（１／βｊ）を代入してみて、σ（Ｘ）＝０となるときのβｊを探索するものである。
【００５５】
ここで、本実施形態の場合、誤り位置多項式（σ（Ｘ）＝０）の根になりえるのは、ガロア拡大体ＧＦ（２１０）の１０２３個の元（α０，α１，α２，・・・，α１０２２）のうちのいずれかである。従って、チェン探索回路を用いて誤り位置βｊ（ｊ＝１，２，・・・，ｋ）を求めようとすると、チェン探索回路による１０２３回の演算が必要となり、誤り位置の探索時間が長くなる。そこで、本実施形態では、チェン探索回路を複数用い、かつ、誤り位置の個数ｋがこの時点で既知であることを利用して、すなわち、図３に示す誤り位置探索部４６３を用いることにより、誤り位置の探索時間の短縮を図る。
【００５６】
図３に示すように、誤り位置探索部４６３は、探索制御回路４６３１と、２つのチェン探索回路４６３２（ＣＳ＃０，ＣＳ＃１）と、その２つのチェン探索回路４６３２（ＣＳ＃０，ＣＳ＃１）で誤り位置が検知されたことをそれぞれカウントする２つのエラーカウンタ４６３３（ＥＣ＃０，ＥＣ＃１）と、２つのチェン探索回路４６３２（ＣＳ＃０，ＣＳ＃１）で検知された誤り位置のデータを格納する誤り位置格納レジスタ４６３４と、２つのエラーカウンタ４６３３（ＥＣ＃０，ＥＣ＃１）の内容を加算する加算器４６３５と、を含んで構成される。
【００５７】
図４は、本発明の実施形態に係るＲＳ符号・復号化回路４６における誤り位置探索の処理の流れの例を示した図である。ここでは、図３を参照しつつ、図４を用いて、誤り位置探索部４６３で行われる誤り位置探索の処理の流れについて説明する。
【００５８】
図４に示すように、誤り位置探索部４６３における誤り位置探索処理は、誤り位置多項式係数算出部４６２から、所定の起動指示信号を受信することによって開始される。なお、誤り位置多項式係数算出部４６２からその起動信号が供給されるときには、誤り位置多項式係数算出部４６２で求められた、誤りシンボル数ｋおよび誤り位置多項式σ（Ｘ）の係数σｊ（ｊ＝１，２，・・・，ｋ）が併せて供給される。
【００５９】
そこで、探索制御回路４６３１は、誤り位置多項式係数算出部４６２からの起動指示信号を受信すると、まず、誤り位置探索部４６３に含まれるカウンタ類を初期化する（ステップＳ１１）。ここで、カウンタ類とは、２つのエラーカウンタ４６３３（ＥＣ＃０，ＥＣ＃１）および２つのチェン探索回路４６３２（ＣＳ＃０，ＣＳ＃１）にそれぞれ含まれる誤り位置カウンタ（図示せず、以下では、その値をｊ０，ｊ１で表す）を指す。従って、カウンタ類の初期化とは、２つのエラーカウンタ４６３３（ＥＣ＃０，ＥＣ＃１）をゼロクリアし、一方のチェン探索回路４６３２（ＣＳ＃０）に含まれる誤り位置カウンタに値２６６をセットし（ｊ０＝２６６）、他方のチェン探索回路４６３２（ＣＳ＃１）に含まれる誤り位置カウンタに値５３２をセットする（ｊ１＝５３２）ことを意味する。
【００６０】
なお、値５３２は、本実施形態における１０ビット化されたセクタデータ（ＣＲＣ検査符号およびＲＳ訂正符号をふくむ）のデータ長、つまり、入力シンボル列のシンボル数を意味している。また、値２６６は、入力シンボル列のシンボル数の１／２の値である。すなわち、本実施形態では、チェン探索回路４６３２（ＣＳ＃０）により、入力シンボル列の前半部分における誤り位置を探索し、チェン探索回路４６３２（ＣＳ＃１）により、入力シンボル列の後半部分における誤り位置を探索する。
【００６１】
次に、２つのチェン探索回路４６３２（ＣＳ＃０，ＣＳ＃１）は、探索制御回路４６３１からの誤り位置の探索開始の指示を受けると、与えられた誤り位置（ｊ０，ｊ１）に対する誤り位置多項式σ（Ｘ）の値を、それぞれ互いに独立に並行して算出し（ステップＳ１２，Ｓ１２ａ）、その誤り位置多項式σ（Ｘ）の値が０であるか否かを、それぞれ独立に判定する（ステップＳ１３，Ｓ１３ａ）。
【００６２】
そして、その判定の結果、誤り位置多項式σ（Ｘ）の値が０となった場合には（ステップＳ１３，Ｓ１３ａでＹｅｓ）、チェン探索回路４６３２（ＣＳ＃０，ＣＳ＃１）は、エラーカウンタ４６３３（ＥＣ＃０，ＥＣ＃１）をカウントアップし（ステップＳ１４，Ｓ１４ａ）、さらに、そのときの誤り位置カウンタの値（ｊ０，ｊ１）を誤り位置格納レジスタ４６３４に格納する（ステップＳ１５，Ｓ１５ａ）。一方、ステップＳ１３，Ｓ１３ａにおける判定で、誤り位置多項式σ（Ｘ）の値が０とならなかった場合には（ステップＳ１３，Ｓ１３ａでＮｏ）チェン探索回路４６３２（ＣＳ＃０，ＣＳ＃１）は、ステップＳ１４，Ｓ１４ａ〜ステップＳ１５，Ｓ１５ａの処理をスキップする。
【００６３】
次に、探索制御回路４６３１は、加算器４６３５を介して、２つのエラーカウンタ４６３３（ＥＣ＃０，ＥＣ＃１）のカウント値の合計を取得し、そのカウント値の合計が誤り位置多項式係数算出部４６２から与えられた誤りシンボル数ｋと等しいか否かを判定する（ステップＳ１６）。そして、その判定の結果、２つのエラーカウンタ４６３３（ＥＣ＃０，ＥＣ＃１）のカウント値の合計が誤りシンボル数ｋと等しかった場合には（ステップＳ１６でＹｅｓ）、探索制御回路４６３１は、その誤りシンボル数ｋと同数の誤り位置を取得したことになるので、チェン探索回路４６３２（ＣＳ＃０，ＣＳ＃１）に対して誤り位置の探索終了を指示し、誤り位置探索部４６３における当該誤り位置探索処理を終了する。
【００６４】
一方、２つのエラーカウンタ４６３３（ＥＣ＃０，ＥＣ＃１）のカウント値の合計が誤りシンボル数ｋと等しくなかった場合には（ステップＳ１６でＮｏ）、探索制御回路４６３１は、さらに、誤り位置カウンタの値（ｊ０）が１に到達しているか否かを判定する（ステップＳ１７）。そして、その判定において、誤り位置カウンタの値（ｊ０）が１に到達していた場合には（ステップＳ１７でＹｅｓ）、２つのチェン探索回路４６３２（ＣＳ＃０，ＣＳ＃１）によりすべての誤り位置について誤り位置多項式σ（Ｘ）の値が０であるか否かの判定がされたことになるので、探索制御回路４６３１は、チェン探索回路４６３２（ＣＳ＃０，ＣＳ＃１）に対して誤り位置の探索終了を指示し、誤り位置探索部４６３における当該誤り位置探索処理を終了する。
【００６５】
また、ステップＳ１７の判定で、誤り位置カウンタの値（ｊ０）が１に到達していなかった場合には（ステップＳ１７でＮｏ）、探索制御回路４６３１および２つのチェン探索回路４６３２（ＣＳ＃０，ＣＳ＃１）は、それぞれの誤り位置カウンタをカウントダウンした（ｊ０＝ｊ０−１，ｊ１＝ｊ１−１：ステップＳ１８）後、ステップＳ１２，Ｓ１２ａへ戻って、ステップＳ１２，Ｓ１２ａ以下の処理を繰り返して実行する。
【００６６】
以上の誤り位置探索処理が終了すると、誤り位置格納レジスタ４６３４には、既知の誤りシンボル数の数ｋと同じ個数の誤り位置のデータが格納されたことになる。誤り位置探索部４６３は、誤り訂正部４６４に対し、その旨を通知する起動信号を送信する。
【００６７】
誤り訂正部４６４は、その起動信号を受信すると、誤り位置格納レジスタ４６３４に格納されている誤り位置のデータと、シンドローム算出部４６１から供給されるシンドロームＳｉ（ｉ＝１，２，・・・，１６）と、を用いて誤りパターンを算出し、その誤りパターンに基づき、当該ＲＳ符号・復号化回路４６に入力された入力シンボル列に含まれる誤りシンボルを訂正し、訂正済みシンボル列を出力する。
【００６８】
なお、誤り訂正部４６４における誤りパターンの算出処理は、周知のフォーネイアルゴリズムなどを用いて実現することができる。また、その算出回路も周知であるので、ここでは、その説明を省略する。
【００６９】
以上、本実施形態によれば、ＲＳ符号・復号化回路４６は、２つのチェン探索回路４６３２が独立に並行して誤り位置を探索するので、誤り位置の探索時間を半減させることができる。また、本実施形態では、誤り位置を探索するときには、誤りシンボル数ｋが既知であることを利用して、誤り位置が誤りシンボル数ｋと同数探索された時点で、探索処理を終了させる、すなわち、探索処理を途中で打ち切るようにしている。従って、探索処理を早めに打ち切る分だけ探索時間は、短縮されることになる。その短縮効果は、確率的なものであるが、その確率を単純に平均すれば、１／２となる。
【００７０】
以上の通り、本実施形態におけるＲＳ符号・復号化回路４６では、チェン探索回路４６３２を２個並列に動作させて使用し、かつ、誤り位置が既知の誤りシンボル数ｋと同数探索し次第、探索処理を打ち切ることによって誤り位置の探索時間を、従来のチェン探索回路を１つ用いた場合に比べ、１／４程度まで短縮することができる。よって、ＲＳ符号・復号化回路４６におけるＲＳ符号の復号化時間を短縮することができる。さらに、このようなＲＳ符号・復号化回路４６を有するＳＳＤ記憶装置２においては、そのページデータの読み出し時間が短縮されるので、ＳＳＤ記憶装置２の平均的なアクセス時間が短縮される。
【００７１】
なお、以上に説明した実施形態では、ＲＳ符号・復号化回路４６は、２つのチェン探索回路４６３２を含むとしているが、例えば、４個や５個など、さらに多くのチェン探索回路４６３２を含むとしても構わない。その場合には、その分だけ、誤り位置の探索時間を短縮することができる。ただし、チェン探索回路４６３２自体は、かなりの回路規模を有する回路であるので、チェン探索回路４６３２の数をむやみに増やすことができないことにも注意すべきである。
【００７２】
また、以上に説明した実施形態では、ＲＳ符号・復号化回路４６を適用した記憶装置の例として、ＳＳＤ記憶装置２について説明しているが、ＲＳ符号・復号化回路４６を適用する記憶装置は、ＳＳＤ記憶装置２に限定されるものではなく、例えば、ハード磁気ディスク記憶装置、ＤＶＤ記憶装置、ブルーレイディスク（登録商標）記憶装置などであっても構わない。
【符号の説明】
【００７３】
１      ホスト装置
２      ＳＳＤ記憶装置
３      ホストバス
４      ＳＳＤ制御部
５      ＳＳＤ記憶媒体部
４１    ホストインタフェース部
４２    コマンド処理制御部
４３    ページデータ書込部
４４    ＲＳ符号・符号化回路
４５    ページデータ読出部
４６    ＲＳ符号・復号化回路
４７    ブロック状態管理部
５１    ＮＦＣ
５２    ブロック
５３    ページ
４６１  シンドローム算出部
４６２  誤り位置多項式係数算出部
４６３  誤り位置探索部
４６４  誤り訂正部
４６３１  探索制御回路
４６３２  チェン探索回路
４６３３  エラーカウンタ
４６３４  誤り位置格納レジスタ
４６３５  加算器
【図１】
0005667408.tif 000003
【図２】
0005667408.tif 000004
【図３】
0005667408.tif 000005
【図４】
0005667408.tif 000006