(57)【特許請求の範囲】
【請求項１】
パイプラインリード-ソロモンデコーダにおいて、
入力リード-ソロモンコードワードを受信し、前記入力コードワードに含まれたエラー位置及びエラー値を求めるために計算を行う多数のパイプライン処理部と、
前記多数のパイプライン処理部により前記計算を行う間に前記入力コードワードを一時貯蔵するバッファ回路と、
を含み、
前記バッファ回路は、
多数個の二重バンクＲＡＭと、
前記多数個の二重バンクＲＡＭと連結され、前記二重バンクＲＡＭの各バンクが所定個数のフレーム周期ごとに読出され、前記所定個数のフレーム周期ごとに書込まれるようにし、読出しバンクは各々の連続的なフレーム周期で前記多数の二重バンクＲＡＭのうち書込みバンクとは異なる一つに含まれるように、各々の連続的なフレーム周期中に前記多数の二重バンクＲＡＭへのデータ書込み及び前記二重バンクＲＡＭからのデータ読出しをイネーブルするメモリ制御回路と、
を備えることを特徴とするパイプラインリード-ソロモンデコーダ。
【請求項２】
パイプラインリード-ソロモンデコーダにおいて、
入力リード-ソロモンコードワードを受信し、前記入力コードワードに含まれたエラー位置及びエラー値を求めるために計算を行う多数のパイプライン処理部と、
前記多数のパイプライン処理部により前記計算を行う間に前記入力コードワードを一時貯蔵するバッファ回路と、
を含み、
前記バッファ回路は、
第１バンク及び第２バンクを有する第１二重バンクＲＡＭと、
第３バンク及び第４バンクを有する第２二重バンクＲＡＭと、
第５バンク及び第６バンクを有する第３二重バンクＲＡＭと、
前記第１、第２及び第３二重バンクＲＡＭと連結され、前記第１ないし第６データバンクのうちの各々一つが６フレーム周期ごとに読出されるように連続的なフレーム周期中に前記第１ないし第６データバンクから順次データの読出しをイネーブルし、前記第１ないし第６データバンクのうちの各々一つが６フレームごとに書込まれるように前記連続的なフレーム周期中に前記第１ないし第６データバンクに順次データの書込みをイネーブルするメモリ制御回路と、
を備え、
前記各フレーム周期中に前記メモリ制御回路により読出しがイネーブルされる第１ないし第６データバンクのうちの一つは前記第１ないし第３二重バンクＲＡＭのうち前記メモリ制御回路により書込みがイネーブルされる前記第１ないし第６データバンクのうちの一つとは異なる一つのＲＡＭに含まれることを特徴とするパイプラインリード-ソロモンデコーダ。
【請求項３】
前記多数個のパイプライン処理部は５つのパイプライン処理段階で構成され、各フレーム周期中に、読出しがイネーブルされるデータバンクから書込みがイネーブルされるデータバンクまでのオフセットは４つのデータバンクとして設定され、ａ（ここで、ａは整数）のフレーム周期で書込まれる前記第１ないし第６データバンクの各々はａ+４のフレーム周期で後から読出されることを特徴とする請求項２に記載のパイプラインリード-ソロモンデコーダ。
【請求項４】
前記多数個のパイプライン処理部は４つのパイプライン処理段階で構成され、各フレーム周期中に、読出しがイネーブルされるデータバンクから書込みがイネーブルされるデータバンクまでのオフセットは３つのデータバンクとして設定され、ａ（ここで、ａは整数）のフレーム周期で書込まれる前記第１ないし第６データバンクの各々はａ+３フレーム周期で後から読出されることを特徴とする請求項２に記載のパイプラインリード-ソロモンデコーダ。
【請求項５】
前記多数個のパイプライン処理部は、エラー及び消去訂正が行われ、５つのパイプライン処理段階が動作できる第１モード及びエラー訂正だけが実行され、４つのパイプライン処理段階が動作できる第２モードで動作可能であり、
前記第１モードの各フレーム周期中に、読出しがイネーブルされるデータバンクから書込みがイネーブルされるデータバンクまでのオフセットは４つのデータバンクとして設定され、ａ（ここで、ａは整数）のフレーム周期で書込まれる前記第１ないし第６データバンクの各々はａ+４フレーム周期で後から読出され、
前記第２モードの各フレーム周期中に、読出しがイネーブルされるデータバンクから書込みがイネーブルされるデータバンクまでのオフセットは３つのデータバンクとして設定され、ａのフレーム周期で書込まれる前記第１ないし第６データバンクの各々はａ+３フレーム周期で後から読出されることを特徴とする請求項２に記載のパイプラインリード-ソロモンデコーダ。
【請求項６】
前記多数個のパイプライン処理部及び前記バッファ回路は同一のクロック信号速度に応答して動作することを特徴とする請求項２に記載のパイプラインリード-ソロモンデコーダ。
【請求項７】
各コードワードはｎ（ここで、ｎは正数）バイトを含み、前記第１ないし第６バンクの各々はｎバイトの容量を有することを特徴とする請求項２に記載のパイプラインリード-ソロモンデコーダ。
【請求項８】
前記多数のパイプライン処理部の各々の最大レイテンシがｎサイクルであり、前記フレーム周期の各々はｎサイクルであることを特徴とする請求項７に記載のパイプラインリード-ソロモンデコーダ。
【請求項９】
外部から受信されたデータをデコーディングしてエラーを訂正するブロックパイプライン構造のリード-ソロモンデコーダで前記受信されたデータを書込み及び読出しするためのメモリ装置において、
内部に各々２つのバンクを含み、
書込み／読出し命令及びイネーブル信号によって活性化される複数のメモリと、
前記複数のメモリに前記書込み／読出し命令と、該当メモリを選択するための前記イネーブル信号とを印加し、データのフレームごとに前記データ書込み及び読出しのためのバンクが所定のオフセットをもって相異なるメモリから選択されるように書込みバンクポインタ及び読出しバンクポインタを設定する循環バッファ制御部と、
を備えることを特徴とするメモリ装置。
【請求項１０】
前記複数のメモリは、
各々２つのバンクを備える３つのＲＡＭで実現し、前記各バンクは１フレームのデータを貯蔵することを特徴とする請求項９に記載のメモリ装置。
【請求項１１】
前記循環バッファ制御部は、
前記リード-ソロモンデコーダがエラー／消去訂正を行う場合に、前記オフセットを４として設定することを特徴とする請求項９に記載のメモリ装置。
【請求項１２】
前記循環バッファ制御部は、
前記リード-ソロモンデコーダがエラー訂正だけを行う場合に、前記オフセットを３として設定することを特徴とする請求項９に記載のメモリ装置。
【請求項１３】
外部から受信されるデータをデコーディングしてエラーを訂正するブロックパイプライン構造のリード-ソロモンデコーダに具備され、各々２つのバンクを有する複数のメモリよりなるメモリ装置のメモリアクセス方法において、
（ａ）エラー訂正モードによって、所定のオフセットだけの差をおいて書込みバンクポインタ及び読出しバンクポインタが増加するように設定する段階と、
（ｂ）データ書込み命令及び読出し命令が印加されるかどうかを判断する段階と、
（ｃ）前記（ｂ）段階において前記書込み命令が印加されれば、前記複数のメモリのうちイネーブルされた一つのメモリから前記書込みバンクポインタに相応するバンクを選択してデータを書込む段階と、
（ｄ）前記（ｂ）段階において前記読出し命令が印加されれば、前記複数のメモリのうちイネーブルされた他のメモリから前記読出しバンクポインタに相応するバンクを選択して前記書込まれたデータを読出す段階と、
前記（ｃ）段階及び前記（ｄ）段階は同時に行われ、前記デコーディングが終わるまで（ｂ）ないし（ｄ）段階を繰り返し行うことを特徴とするメモリアクセス方法。
【請求項１４】
前記（ａ）段階は、
（ａ１）エラー／消去訂正を行うかどうかを判断する段階と、
（ａ２）前記エラー／消去訂正を行うとすれば、前記書込みバンクポインタと前記読出しバンクポインタとの間の前記オフセットを４として設定する段階と、
（ａ３）前記エラー／消去訂正を行おうとするのでなければ、エラー訂正だけを行うかどうかを判断する段階と、
（ａ４）前記（ａ３）段階で前記エラー訂正だけを行おうとするのであれば、前記書込みバンクポインタと前記読出しバンクポインタとの間の前記オフセットを３として設定する段階と、
を備えることを特徴とする請求項１３に記載のメモリアクセス方法。
【請求項１５】
外部から受信されるデータをデコーディングしてエラーを訂正するブロックパイプライン構造のリード-ソロモンデコーダにおいて、
前記受信されるデータからシンドロームを生成するシンドローム生成部と、
各々２つのバンクを有する複数のメモリからなり、前記受信されるデータを前記複数のメモリのうちのいずれか一つの選択されたバンクに書込み、前記複数のメモリのうちの他のメモリの選択されたバンクからデータを読出すメモリ装置と、
前記生成されたシンドロームから各々エラー位置多項式及びエラー値多項式の係数を生成する多項式係数生成部と、
前記生成された係数を用い、前記エラー位置多項式及び前記エラー値多項式からエラー位置及びエラー値を求めるエラー位置／エラー値測定部と、
前記エラー位置／エラー値測定部で求められた前記エラー値及び前記エラー位置に応答して前記メモリ装置から読出されたデータのエラーを訂正するエラー訂正部と、
を備えることを特徴とするリード-ソロモンデコーダ。
【請求項１６】
前記メモリ装置は、
各々２つのバンクを備える３つのＲＡＭからなり、前記受信されたデータの毎フレーム処理時に相異なるメモリの該当バンクがイネーブルされることを特徴とする請求項１５に記載のリード-ソロモンデコーダ。
【請求項１７】
前記メモリ装置は、
前記受信されるデータのフレームごとにデータ書込み及び読出しのためのバンクが第１オフセット差をもって選択されるように書込みバンクポインタ及び読出しバンクポインタを設定することを特徴とする請求項１６に記載のリード-ソロモンデコーダ。
【請求項１８】
前記リード-ソロモンデコーダは、
前記入力データに同期される消去フラグをカウントし、前記消去フラグをバッファリングするフラグカウンタ及びバッファと、
前記バッファリングされた消去フラグに応答して消去位置多項式を生成する消去位置多項式生成部と、
前記シンドローム生成部で生成された前記シンドロームを前記バッファリングされた消去フラグにより変形し、前記変形されたシンドロームを前記多項式係数生成部に印加するシンドローム変形部と、
をさらに備え、
前記多項式係数生成部は、前記変形されたシンドローム及び前記消去位置多項式に応答して前記エラー位置多項式及び前記エラー値多項式の係数を生成することを特徴とする請求項１５に記載のリード-ソロモンデコーダ。
【請求項１９】
前記メモリ装置は、
前記受信されるデータのフレームごとにデータ書込み及び読出しのためのバンクが第２オフセット差をもって選択されるように書込みバンクポインタ及び読出しバンクポインタを設定することを特徴とする請求項１８に記載のリード-ソロモンデコーダ。
【請求項２０】
前記リード-ソロモンデコーダは、
前記メモリ装置にデータを書込むためのデータ入力クロック信号と、前記リード-ソロモンデコーダの各ブロックを動作させるのに要求されるシステムクロック信号とを同一のクロック信号として使用することを特徴とする請求項１５に記載のリード-ソロモンデコーダ。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はリード-ソロモンデコーダに係り、特に、高速ブロックパイプライン構造のリード-ソロモンデコーダに適用するためのメモリ装置及びメモリアクセス方法並びにそのメモリ装置を備えたリード-ソロモンデコーダに関する。
【０００２】
【従来の技術】
近年、ディジタル信号処理技術が発達するに伴い、チャネルやメディアで生成されるエラーの復元技術も発達してきている。今まで、様々なエラー訂正技術が報告され、開発されてきた。中でも、線形ブロックコードの一種であるリード-ソロモンコードが汎用されている。一般に、リード-ソロモンエンコーダは２ｔのパリティ記号をｋ個のデータ記号に加えることによりｎ（例えば、８-バイト）個の記号を含むコードワードを形成する。ここで、２ｔ=ｎ-ｋで表わされる。
また、リードソロモンコードワードは、共通的に、ＲＳ（ｎ，ｋ）と表わされる。
リード-ソロモンコードが汎用される理由は、リード-ソロモンデコーダの強力なエラー訂正能力及び効率良いエンコーディング／デコーディング処理によるためであると言える。リード-ソロモンデコーダにおいてなされるデコーディング過程はエンコーディング過程に比べてやや複雑である。また、高速のディジタルデータプロセッシングを要求するシステムが増加するのに伴い、デコーディングハードウェアでも高速のディジタルプロセッシングが可能な構造が要求されている。
【０００３】
一般に、リード-ソロモンデコーダは５段階または４段階の過程を行う処理ブロックで構成される。すなわち、エラー訂正及び消去訂正がいずれも可能である場合には５段階に区分でき、エラー訂正だけが可能である場合には４段階に区分できる。
【０００４】
まず、エラー／消去訂正がいずれも可能である場合、リード-ソロモンデコーダは下記のような段階を通じてデコーディングを行う。
まず、第１段階の処理ブロックでは入力データによりシンドロームを生成し、入力データに同期されて印加される消去フラグをカウント及びバッファリングする。
第２段階ではバッファリングされた消去フラグによりシンドロームを変形し、消去位置多項式を生成する。
第３段階では、変形されたシンドローム及び消去位置多項式によってエラー位置多項式と、エラー値多項式の係数を求めることになる。ここで、ユークリッドアルゴリズムなどの所定のアルゴリズムが多項式の係数を求めるのに用いられる。
第４段階では、第３段階で求められた多項式の係数を有するエラー位置多項式及びエラー値多項式から、チエン検索アルゴリズムを用いてエラー値及びエラーの位置が求められる。
第５段階では、求められたエラー位置及びエラー値により入力データのエラーが訂正される。
このようなリード-ソロモンデコーディング過程においてエラー訂正だけがなされる場合には、第２段階の過程が省かれるため、全体的なデコーディング過程は４段階で構成される。
【０００５】
このようなリード-ソロモンデコーディング過程において、第１及び第５段階（エラー訂正だけがなされる場合には第４段階）はメモリアクセスを要求する。
すなわち、第１段階では入力されるデータを貯蔵するのにメモリが用いられ、第５段階ではメモリに貯蔵されたデータを読出してエラーを訂正するために用いられる。したがって、メモリアクセスに要求される時間は各デコーディング段階を行うのに影響を及ぼすことになる。
【０００６】
最近では多くのシステムが高速の動作を要求し、これにより、リード-ソロモンデコーダの各段階を行うブロックはパイプライン構造を用いて実現されている。この場合、各段階のレイテンシのうち最も高いレイテンシを要する段階が、１フレームのデータを処理するに当たっての妨害要素として作用する。最近では、１フレームのデータ長をｎとしたとき、各段階別の最大レイテンシはｎサイクル以内になるように実現されている。
【０００７】
しかし、１フレームのデータをデコーディングする過程において、前記第１段階及び第５段階における複数回のメモリアクセスのため２ｎサイクル以上の時間を要求する。結果的に、メモリアクセスに要求される時間が、各段階のブロックレイテンシに比べて２倍以上となって、全体回路の動作速度を落とすことになる。
このような問題点を解決するために、従来は、メモリにデータを書込むのに用いるデータ入力クロック信号の速度に比べ、各デコーディング段階の動作のためのシステムクロック信号の速度を２倍以上速める方法が用いられていた。
【０００８】
【発明が解決しようとする課題】
しかし、この方法は、システムクロック信号の速度が２倍以上速くなるのに伴い、パワー消耗が増してしまうという問題が生じる。
また、データ入力クロック信号の速度が速い場合には、システムクロック信号を一定の速度以上に高め難いという短所がある。
また、リード-ソロモンデコーダの速度がメモリアクセス時間に影響されるため、動作速度に制限があるという問題がある。
本発明は上記事情に鑑みてなされたものであり、その目的は、高速ブロックパイプライン構造のリード-ソロモンデコーダにおいて、メモリアクセス速度を速めて高速動作を可能にするメモリ装置及びメモリアクセス方法並びにそのメモリ装置を備えたリード-ソロモンデコーダを提供することである。
【０００９】
【課題を解決するための手段】
前記目的を達成するために、本発明の一面によれば、二重バンクＲＡＭの各バンクが所定個数のフレーム周期ごとに読出され、所定個数のフレーム周期ごとに書込まれるようにし、読出しバンクは各々の連続的なフレーム区間で多数の二重バンクＲＡＭのうち書込みバンクとは異なる一つに含まれるように、各々の連続的なフレーム周期中に多数の二重バンクＲＡＭへのデータ書込み及び二重バンクＲＡＭからのデータ読出しがイネーブルされる。
【００１０】
前記目的を達成するために、本発明の他の一面によれば、メモリは第１バンク及び第２バンクを有する第１二重バンクＲＡＭ、第３バンク及び第４バンクを有する第２二重バンクＲＡＭ及び第５バンク及び第６バンクを有する第３二重バンクＲＡＭを含む。第１ないし第６データバンクのうちの各々一つが６フレーム周期ごとに読出されるように連続的なフレーム周期中に、第１ないし第６データバンクから順次データ読出しがイネーブルされ、第１ないし第６データバンクのうちの各々一つが６フレーム周期ごとに書込まれるように連続的なフレーム周期中に第１ないし第６データバンクに順次データの書込みがイネーブルされる。
また、各フレーム周期中に読出しがイネーブルされる第１ないし第６データバンクのうちの一つは、第１ないし第３二重バンクＲＡＭのうち書込みがイネーブルされる第１ないし第６データバンクのうちの一つとは異なる一つのＲＡＭに含まれる。
【００１１】
前記目的を達成するために、本発明のさらに他の一面によれば、各フレーム周期中に、読出しがイネーブルされるデータバンクから書込みがイネーブルされるデータバンクまでのオフセットは４つ（または３つ）のデータバンクとして設定され、ａ（ここで、ａは整数）のフレーム周期で書込まれる第１ないし第６データバンクの各々はａ+４（またはａ+３）のフレーム周期で後から読出されることを特徴とする。
【００１２】
前記目的を達成するために、本発明のさらに他の一面によれば、二重バンクメモリは入力リード-ソロモンコードワードを受信し、入力コードワードに含まれたエラー位置及びエラー値を求めるために計算を行う多数のパイプライン処理部と結合されて用いられる。望ましくは、多数個のパイプライン処理部及びメモリは同一のクロック信号速度に応答して動作する。
【００１３】
前記目的を達成するために、本発明のさらに他の一面によれば、各コードワードはｎ（ここで、ｎは正数）バイトを含む。望ましくは、多数個のパイプライン処理部の各最大レイテンシはｎサイクルであり、各々のメモリアクセスフレーム周期はｎサイクルである。
【００１４】
【発明の実施の形態】
以下、本発明による高速ブロックパイプライン構造のリード-ソロモンデコーダと、高速ブロックパイプライン構造のリード-ソロモンデコーダに適用するためのメモリ装置及びメモリアクセス方法とについて、添付図面を参照して説明する。
【００１５】
図１は、本発明によるメモリ装置が適用される高速ブロックパイプライン構造のリード-ソロモンデコーダを説明するための実施例のブロック図である。図１を参照すれば、リード-ソロモンデコーダはシンドローム生成部１００、フラグカウンタ及びフラグバッファ１２０、消去位置多項式生成部１３０、シンドローム変形部１４０、多項式係数生成部１５０、エラー値測定部１６０、エラー位置検索部１７０、二重バンク３ＲＡＭメモリ１８０及びエラー訂正部１９０で構成される。
図１に示されたリード-ソロモンデコーダは、エラー訂正及び消去訂正がいずれも可能である場合に対する実施例を示す。したがって、図１に示されたリード-ソロモンデコーダは各々のブロックによって前記第１ないし第５段階（ｓ１〜ｓ５）がパイプライン処理される。エラー訂正だけがなされる場合のリード-ソロモンデコーダは、図１に示された１１０ブロックを含まないものとなる。
【００１６】
シンドローム生成部１００は、外部から受信される入力データＤＩＮ、すなわち、コードワードＲ（ｘ）からシンドロームＳ（ｘ）を生成する。
フラグカウンタ＆フラグバッファ１２０は、入力データＤＩＮに同期されて印加される消去フラグＥｒａ_Ｆｌａｇのフラグの個数をカウントし、消去フラグＥｒａ_Ｆｌａｇをバッファリングする。ここで、入力データＤＩＮに含まれたエラー成分のうちエラー値は知っていないが、エラーの位置を知っている場合の成分が消去となる。これに対し、エラーはその値及び位置をいずれも知っていない場合である。
したがって、消去の訂正が要求される場合には消去フラグＥｒａ_Ｆｌａｇが入力され、その個数がカウントされる。もし、入力されるフラグの個数が訂正可能な許容範囲を超える場合には、単にエラーデコーディング過程だけが行われる。ここで、許容可能範囲は、例えば、消去フラグが１０個以上である場合として設定できる。また、フラグの数が０である場合にも、エラーデコーディング過程だけが行われる。
【００１７】
図１において、シンドローム生成部１００と、フラグカウンタ＆フラグバッファ１２０はリード-ソロモンデコーダの第１段階（ｓ１）を行うブロックであると言える。基本的に、エラー訂正だけがなされるリード-ソロモンデコーダの場合には、フラグカウンタ＆フラグバッファ１２０が用いられない。
【００１８】
図１に示されたリード-ソロモンデコーダは入力データＤＩＮ、すなわち、コードワードＲ（ｘ）を一時貯蔵するための二重バンク３ＲＡＭメモリ１８０を備える。このメモリ１８０は各々二つのバンクを有する３つのＲＡＭで構成される。また、二重バンク３ＲＡＭメモリ１８０はデータ入力クロック信号ＣＬＫに応答して書込み／読出し動作を行うために循環的な制御構造を採用する。二重バンク３ＲＡＭメモリ１８０は、３つのＲＡＭのうちのいずれか一つの選択されたバンクに書込み、読出し時に３つのＲＡＭのうち他のＲＡＭの選択されたバンクからデータを読出す。ここで、二重バンク３ＲＡＭメモリ１８０は書込み及び読出し時にデータ入力クロック信号ＣＬＫに応答して動作する。この二重バンク３ＲＡＭメモリ１８０の具体的な構成及び動作については、図３を参照して後で説明する。
【００１９】
シンドローム変形部１４０は、シンドローム生成部１００で生成されたシンドロームＳ（ｘ）をバッファリングされた消去フラグを用いて変形し、これを変形されたシンドロームＴ（ｘ）として出力する。もし、エラーデコーディングだけが行われる場合には、シンドローム変形がなされず、シンドローム生成部１００で生成されたシンドロームＳ（ｘ）がそのまま多項式係数生成部１５０に伝達される。
【００２０】
消去位置多項式生成部１３０は、バッファリングされた消去フラグにより消去位置多項式を生成する。また、エラーデコーディングだけがなされる場合には、消去位置多項式生成部１３０の出力は多項式の形ではなく、一定の定数値、例えば、"１"を有するように設定される。すなわち、消去フラグＥｒａ_Ｆｌａｇの個数が０である場合、或いは許容可能範囲を超える場合に、消去位置多項式の代わりに定数"１"として設定される。図１を参照すれば、シンドローム変形部１４０及び消去位置多項式生成部１３０はリード-ソロモンデコーディング過程の第２段階（ｓ２）を行うブロックである。もし、エラー訂正だけがなされる場合には、第２段階（ｓ２）が省かれる。
【００２１】
多項式係数生成部１５０は、変形されたシンドロームＴ（ｘ）及び消去位置多項式によりエラー位置を求めるためのエラー位置多項式σ（ｘ）と、エラー値を計算するためのエラー値多項式ｅ（ｘ）の係数とを求める。図１の実施例において、多項式係数生成部１５０は広く知られているユークリッドアルゴリズムを用いると仮定している。しかし、ユークリッドアルゴリズムのほかに、他のアルゴリズムを用いることも可能であり、場合によっては、エラー位置多項式の係数だけを求めることもある。多項式係数生成部１５０はリード-ソロモンデコーディング過程の第３段階（ｓ３）を行うブロックであると言える。もし、エラー訂正のためのデコーディングだけがなされる場合には、ブロック１１０に含まれる構成要素が用いられないため、シンドロームＳ（ｘ）及び定数値"１"によってエラー位置多項式σ（ｘ）及びエラー値多項式ｅ（ｘ）の係数が求められる。
【００２２】
エラー位置検索部１７０は、多項式係数生成部１５０で生成された係数値を有するエラー位置多項式からチエン検索アルゴリズムを用いてエラーの位置を求める。ここで、チエン検索アルゴリズムはエラー位置多項式の根を求めるために用いられるアルゴリズムであり、他の適切なアルゴリズムが用いられる場合もある。このとき、求められた根は再び多項式の形に変換される。このように、変換されたエラー位置多項式はΩ（ｘ）で表わされ、変換されたエラー位置多項式Ω（ｘ）によりエラーの位置が求められる。
【００２３】
エラー値測定部１６０は、多項式係数生成部１５０で生成された係数を有するエラー値多項式e（ｘ）を用いてエラー値を測定する。これは、エラー位置検索部１７０で求められたエラー位置におけるエラー値であると言える。エラー位置検索部１７０及びエラー値測定部１６０は、前述したリード-ソロモンデコーディング過程の第４段階（ｓ４）を行うブロックとして定義される。本発明において、エラー位置検索部１７０及びエラー値測定部１６０はエラー位置／エラー値測定部として統合されて名づけられる。
【００２４】
エラー訂正部１９０は、二重バンク３ＲＡＭメモリ１８０にアクセスしてメモリに書込まれているデータを読出し、エラー位置検索部１７０で求められたエラー位置と、エラー値測定部１６０で測定されたエラー値とによって、読出されたデータに含まれているエラーを訂正する。すなわち、エラー訂正部１９０はメモリ１８０から読出された元のデータ及び求められたエラー値を足してエラー訂正を行う。
【００２５】
また、具体的には示していないが、図１に示されたリード-ソロモンデコーダの各ブロックは第１ないし第５段階（ｓ１〜ｓ５）を行うためにシステムクロック信号によって動作する。
【００２６】
図２は、図１に示されたデコーダにおいてブロックパイプライニングのための各実行段階（ｓ１〜ｓ５）のレイテンシを示した図である。図２を参照すれば、各々の段階（ｓ１〜ｓ５）を行うブロックの最大レイテンシは、入力されるデータの１フレームの長さをｎとしたとき、ｎサイクル以内に設定できる。本発明においては、二重バンク３ＲＡＭを有する循環メモリ構造を採用することにより第１段階（ｓ１）及び第５段階（ｓ５）を行うのに要求されるメモリアクセス時のタイミング損失を最小化できる。
【００２７】
図３は、本発明の実施例による二重バンク３ＲＡＭメモリ１８０を説明するためのブロック図である。図３を参照すれば、二重バンク３ＲＡＭメモリ１８０は循環バッファ制御部３００及び第１ないし第３ＲＡＭ３１０〜３３０で構成される。
【００２８】
循環バッファ制御部３００は、第１ないし第３ＲＡＭ３１０〜３３０に読出し／書込み命令ＲＥ／ＷＲを印加し、該当ＲＡＭを選択するためのイネーブル信号ＥＮＡＢＬＥを印加する。また、循環バッファ制御部３００は、データのフレームごとにデータ書込み及び読出しのためのバンクが所定のオフセットをもって相異なるＲＡＭから選択されるように、書込みバンクポインタ及び読出しバンクポインタを設定する。すなわち、循環バッファ制御部３００は、３つのＲＡＭのうち該当ＲＡＭをイネーブルするためにイネーブル信号ＥＮＡＢＬＥを印加し、イネーブルされたＲＡＭから該当バンクを選択するためにバンク選択信号ＢＫ_ＳＥＬを印加する。ここで、バンク選択信号ＢＫ_ＳＥＬは１ビットで表わされ、８ビットのアドレスバス３４０（ＡＤＤＲ[７：０]）に加えられて最上位ビット（Ｍｏｓｔ Ｓｉｇｎｉｆｉｃａｎｔ Ｂｉｔ、以下、ＭＳＢ）となる。したがって、全体アドレスＡＤＤＲは９ビットとなって各ＲＡＭ３１０〜３３０に印加され、ここで、バンク選択信号ＢＫ_ＳＥＬはバンクポインタとして作用する。例えば、バンク選択信号ＢＫ_ＳＥＬが０であれば、各ＲＡＭの両バンクのうち第１番目のバンクが選択され、１であれば、第２番目のバンクが選択されるように動作する。
【００２９】
第１ＲＡＭ３１０は内部に二つのバンク、バンク０ ＢＡＮＫ０及びバンク１ ＢＡＮＫ１を備え、イネーブル信号ＥＮＡＢＬＥが活性化された状態でバンクポインタによりバンク０ ＢＡＮＫ０またはバンク１ ＢＡＮＫ１を選択する。このとき、第１ＲＡＭ３１０は循環バッファ制御部３００から印加される読出し／書込み命令ＲＥ／ＷＲによって、選択されたバンクの所定位置にデータを書込んだり、所定位置に書込まれたデータを読出したりする。ここで、ＲＡＭ ３１０はＳＲＡＭ（Ｓｔａｔｉｃ Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）で実現でき、各バンクは１フレームのデータを貯蔵できる容量を有することが望ましい。
図３のメモリ構造において、貯蔵されるデータの個数はガロアフィールドＧＦ（２８）を使用する最大２５６バイトの長さを有する場合として仮定する。
【００３０】
第２ＲＡＭ ３２０及び第３ＲＡＭ ３３０も各々二つのバンク、すなわちバンク２ ＢＡＮＫ２、バンク３  ＢＡＮＫ３、及びバンク４ ＢＡＮＫ４、バンク５ＢＡＮＫ５を備え、読出しまたは書込み命令ＲＥまたはＷＲと、イネーブル信号ＥＮＡＢＬＥとにより活性化される。他の動作は第１ＲＡＭ３１０と同一なため、具体的な説明は省略する。
また、第１ないし第３ＲＡＭ３１０〜３３０はデータ入力クロック信号ＣＬＫにより８ビットの入力データＤＩＮ[７：０]を書込み、システムクロック信号と同一のクロック信号を入力クロック信号ＣＬＫとして使用する。図３の実施例において、各ＲＡＭ ３１０〜３３０の出力信号は８ビットの並列信号ＭＯＵＴ[７：０]で表わされ、これは図１のエラー訂正部１９０に印加される。
【００３１】
図４は、図３に示された二重バンク３ＲＡＭメモリ１８０のアクセス方法を説明するためのフローチャートである。
図３及び図４を参照し、本発明による二重バンク３ＲＡＭメモリ１８０の動作及びメモリアクセス方法について具体的に説明する。
【００３２】
先ず、表１は一般的な（ｎ，ｋ）コードを使用し、有限フィールドがＧＦ（２ｍ）である場合のＲＡＭ及びバンクサイズを表わす。前記（ｎ，ｋ）コードにおいて、ｎは符号長さを表わし、ｋは情報長さを表わす。表１を参照すれば、ガロアフィールドＧＦ（２ｍ）を使用する長さのデータを貯蔵するとき、各ＲＡＭ ３１０〜３３０のバンクサイズはｎで表わされ、二重バンクを有するＲＡＭサイズは２ｎで表わされる。
【表１】
0003862062.tif 000002
このとき、データ幅、すなわち、データビット数はｍで表わされ、アドレス幅はｌｏｇ２ｎ≦ｐを満足する最小整数ｐに１を加えた値として定義される。ここで、１を加えるのは、前述したように、アドレスの最上位ビットＭＳＢでバンクを選択するためである。表１に示されたように、ｎが２５６であり、ｍは８である場合、バンクサイズは２５６バイトとなり、ＲＡＭサイズは５１２バイトとなる。また、データ幅は８ビットとなり、アドレス幅は９ビットとなる。
【００３３】
このようなバンクサイズ及びＲＡＭサイズを有するメモリにアクセスするのに当たって、先ず、リード-ソロモンデコーダのエラー訂正モードが区分されなければならない。図４を参照すれば、エラー／消去訂正がいずれも可能である場合と、エラー訂正だけが可能である場合に対し、書込みバンクポインタ及び読出しバンクポインタが相異なるように設定される（ステップ４００及びステップ４１０）。
具体的に、ステップ４００では、エラー／消去訂正を行うかどうかが判断される（ステップ４０２）。ここで、エラー／消去訂正を行うかどうかを判断するのは、入力データＤＩＮに同期される消去フラグＥｒａ_Ｆｌａｇが入力されるかどうかを判断することによりなされる。
【００３４】
ステップ４０２において、エラー訂正及び消去訂正をいずれも行おうとするのであれば、循環バッファ制御部３００はフレームごとに書込みバンクポインタ及び読出しバンクポインタが４のオフセット差をもって増加するように設定する（ステップ４０４）。すなわち、図３の二重バンク３ＲＡＭメモリ１８０の構造において、各ＲＡＭ ３１０〜３３０のバンクを選択するためのバンクポインタは書込み時及び読出し時に所定のオフセットだけの差がある。前述したように、エラー／消去訂正がいずれも可能である場合、オフセットが４として設定されるのは、全体デコーディングに要求される処理段階が５つの段階に分けられるからである。例えば、読出しのためのバンクポインタをＢＡＮＫ#で表わせば、書込みのためのバンクポインタはＢＡＮＫ（#+４）ＭＯＤ６で表わされる。ここで、モジュロ６ ＭＯＤ６演算を行う理由は、全体バンク数が６つであるからである。
また、本発明において、二重バンクを使用するのは、６つの２５６バイトの別々のメモリを使用する方よりは、５１２バイトの個別メモリを３つ使用する方が面積の点で有利であるからである。それだけでなく、５１２バイトの個別メモリを３つ使用しつつも、メモリアクセス時の衝突を防止できるという利点がある。
【００３５】
ステップ４０４において、書込みバンクポインタ及び読出しバンクポインタが設定されれば、循環バッファ制御部３００から書込み命令ＷＲが印加されたかどうかが判断され（ステップ４２０）、同時に読出し命令が印加されたかどうかが判断される（ステップ４４０）。すなわち、メモリアクセス過程において、データ書込み及び読出しは同時になされる。ステップ４２０において、書込み命令ＷＲが印加されたなら、イネーブルされた一つのＲＡＭにおいて、設定された書込みバンクポインタに相応するバンクを選択して入力データを書込む（ステップ４３０）。
【００３６】
図５は、図３のメモリにおいて、エラー／消去訂正がいずれも可能である場合に対し、毎フレームが進行するときに書込み／読出し時のバンク選択動作を示した図である。図５を参照すれば、毎フレームが進行する区間において、書込みフレームポインタはバンク単位に増加する。例えば、図５に示すように、第１番目のフレームＴ５０で書込みフレームポインタが第３ＲＡＭ ３３０のバンク４ ＢＡＮＫ４を指定すれば、バンク４ ＢＡＮＫ４が選択されてデータの書込みがなされる。
【００３７】
また、 ステップ４４０において、読出し命令ＲＥが印加されれば、図５に示すように、書込みフレームポインタに対して４つのバンク差をおいて読出しフレームポインタが増加する。すなわち、読出し命令ＲＥが印加されればイネーブルされる他のＲＡＭにおいて、設定された読出しバンクポインタに相応するバンクを選択してデータを読出す（ステップ４５０）。図５を参照すれば、区間Ｔ５０において読出しフレームポインタに相応する第１ＲＡＭ ３１０のバンク０ ＢＡＮＫ０が選択され、選択されたバンク０ ＢＡＮＫ０に貯蔵されているデータが読出される（ステップ４５０）。このとき、読出されたデータは図１のエラー訂正部１９０に伝達されてエラー訂正がなされる（ステップ４６０）。
【００３８】
前述したように、図４の書込み命令及び読出し命令によるメモリアクセス過程はリード-ソロモンデコーダのデコーディング過程がなされる間に繰り返される。すなわち、図４において、デコーディングが終わったかどうかが判断され（ステップ４７０）、終わってないなら、ステップ４２０及びステップ４３０に進んで以降の過程が繰り返される。
図５に示すように、初期に書込みバンクポインタ及び読出しバンクポインタは４つのバンク差を有するように設定される。したがって、毎フレーム進行時に書込みフレームポインタと、読出しフレームポインタとは互いにバンク単位に増加するが、同一のＲＡＭがアクセスされないため、メモリアクセス時に衝突が起こらない。したがって、システムクロックによりメモリにアクセスすることが可能であり、メモリアクセスによる時間的な損失がないので、高速動作が可能である。
【００３９】
一方、図４のステップ４００において、エラー／消去訂正を行わない場合には、エラー訂正だけを行うと判断される。エラー訂正だけを行う場合は、消去フラグＥｒａ_Ｆｌａｇの個数が０であるか、或いはカウントされたフラグの個数が許容範囲を超える場合である。
図６は、エラー訂正だけが可能である場合に対し、毎フレームが進行するときに書込み／読出し時のバンク選択動作を示した図である。図１のリード-ソロモンデコーダにおいて、エラー訂正だけがなされる場合には、書込みバンクポインタ及び読出しバンクポインタが３だけのオフセット差をもって増加するように設定される（ステップ４１４）。これは、全体デコーディングに要求される処理段階が４つに分けられるからである。例えば、読出しのためのバンクポインタをＢＡＮＫ#として設定すれば、書込みのためのバンクポインタはＢＡＮＫ（#+２）３ＭＯＤ６として設定される。ステップ４１４において、各々の書込み／読出しバンクポインタが設定されれば、ステップ４２０に進んで前述した過程と同一に書込み及び読出し過程がなされる。
【００４０】
図６を参照すれば、毎フレームが進行する区間で書込みフレームポインタはバンク単位に増加する。例えば、図６に示したように、第１番目のフレームＴ６０で書込みフレームポインタが第２ ＲＡＭ ３２０のバンク３ ＢＡＮＫ３を指定すれば、バンク３ ＢＡＮＫ３が選択されてデータの書込みがなされる。このとき、３つのバンク差をおいて読出しフレームポインタが増加する。すなわち、読出しフレームポインタにより第１ ＲＡＭ３１０のバンク０ ＢＡＮＫ０が選択され、選択されたバンク０ ＢＡＮＫ０に貯蔵されているデータが読出されて図１のエラー訂正部１９０に伝達される。
前述したように、エラー訂正だけがなされる場合であっても、書込みバンクポインタ及び読出しバンクポインタが３つのバンク差を有するように設定されるため、書込み及び読出し時に同一のＲＡＭがアクセスされず、その結果、メモリ衝突が起こらない。
【００４１】
次に、表２には、一般的な一つの循環ＲＡＭを使用する従来の場合と、３つの循環ＲＡＭを使用する本発明の場合に各々必要なサイクルを示している。
【表２】
0003862062.tif 000003
表２を参照すれば、書込み及び読出しの場合に各々必要なサイクルはｎサイクルであるが、フレーム当たり要求されるメモリアクセスは１ＲＡＭの場合に２ｎサイクルであるのに対し、３ＲＡＭの場合にはｎサイクルだけを必要とする。また、１ＲＡＭを使用する場合にはデータ入力クロックと比較した場合のシステムクロック速度が２倍以上増加されなければならないが、本発明の場合にはデータ入力クロックと同一の速度のクロック信号をシステムクロック信号として使用できる。結果的に、低い速度のシステムクロック信号を用いつつも、入力と同一の処理結果が得られる。
【００４２】
また、本発明による二重バンク３ＲＡＭメモリを適用するリード-ソロモンデコーダは各々面積及び速度の面で従来の場合と比較するとき、下記のような利点がある。表３は、コードワードの長さが２５６の場合のＳＲＡＭサイズを比較するためのものである。
【表３】
0003862062.tif 000004
すなわち、表３に示されたように、コードワードの長さが２５６である場合、１５３６バイトのＳＲＡＭ一つを使用する場合の面積は、５１２バイトのＳＲＡＭ３つを使用した場合に比べて０．６６倍となる。
しかし、３つのＳＲＡＭを使用する場合の速度は１つのＳＲＡＭを使用する場合に比べて２倍となって、面積の損失よりも速度の利得が相対的に大きいということが分かる。高速動作を要求する応用分野においては、速度に対する要求が先立つため、ある程度の面積に対する損失は無視できる。
【００４３】
図７は、本発明によるブロックパイプライン構造を有するリード-ソロモンデコーダのプロセスタイミングを示した図である。図７を参照すれば、メモリアクセス時の衝突が起こらないため、各ブロック段階はいずれもｎサイクル以内に動作が完了する。また、各サイクルにおいてデータＤＩＮは連続的に印加されてシンドロームＳ（ｘ）が形成される。各段階において得られた結果はｎサイクルごとに下位ブロックに伝達される。すなわち、第２番目のｎサイクルにおいてはシンドローム生成Ｓ（ｘ）と変形されたシンドロームＴ（ｘ）とが生成され、第３番目のｎサイクルにおいてはエラー位置多項式σ（ｘ）及びエラー値多項式e（ｘ）の係数が生成される。第４番目及び第５番目のｎサイクルの場合も同様である。また、図７に示したように、全体レイテンシ遅延Ｔ７０は４*ｎサイクルであり、４ｎサイクル後には各ｎサイクルごとにエラー訂正されたデータＤＯＵＴ、すなわち、Ｒ'（ｘ）が出力される。また、図７の区間Ｔ７５はレイテンシ遅延ではなく、出力を得るための実際の処理過程における遅延である。
【００４４】
前述した過程による本発明の二重バンク３ＲＡＭ構造のメモリと、これを採用するリード-ソロモンデコーダとは各種の分野に適用できる。例えば、高画質のディジタル多機能ディスク（ＨＤ-ＤＶＤ）システムを含む光ディスクシステム、高画質テレビ（ＨＤ-ＴＶ）、衛星通信、ＩＭＴ２０００などの無線通信分野、及びギガイーサネットなどのネットワーク分野などを含んで、リード-ソロモンデコーダを用いる多くの超高速システムに適用できる。
【００４５】
【発明の効果】
本発明によれば、メモリアクセスのためのデータ入力クロックをシステムクロックと同一に使用できるので、半導体製造工程を簡素化でき、電力消耗を減らしつつ、高速の動作が可能であるという効果がある。また、メモリアクセスによるタイミング損失を最小化でき、システムクロック速度がメモリアクセス時間に影響されることを減らすことにより、システム設計時にタイミングマージンに対する自由度を増加できるという効果がある。また、高速の伝送が可能なので、高速のブロックパイプライン構造のリード-ソロモンデコーダと、これを用いる超高速システムとに適しているという効果がある。
【００４６】
以上、図面及び明細書において最適の実施例を開示した。ここで、特定の用語が使用されたが、これは単に本発明を説明するための目的で使用されたものであり、意味の限定や特許請求の範囲上に記載された本発明の範囲を制限するために使用されたものではない。よって、この技術分野の通常の知識を有した者なら、これより各種の変形及び均等な他の実施例が可能であるという点は言うまでもない。したがって、本発明の真の技術的な保護範囲は特許請求の範囲上の技術的な思想によって定まるべきである。
【図面の簡単な説明】
【図１】本発明による二重バンク３ＲＡＭメモリが適用されるブロックパイプライン構造のリード-ソロモンデコーダを示したブロック図。
【図２】図１に示されたリード-ソロモンデコーダの各ブロック間レイテンシを説明するための図。
【図３】本発明の実施例による二重バンク３ＲＡＭメモリを説明するためのブロック図。
【図４】本発明の実施例による二重バンク３ＲＡＭメモリアクセス方法を説明するためのフローチャート。
【図５】図３に示された二重バンク３ＲＡＭメモリにおいて、書込み／読出し時のバンク選択動作を説明するための図。
【図６】図３に示された二重バンク３ＲＡＭメモリにおいて、書込み／読出し時のバンク選択動作を説明するための図。
【図７】図１に示されたリード-ソロモンデコーダのプロセスタイミングを示した図。
【符号の説明】
１８０    二重バンク３ＲＡＭメモリ
３００    循環バッファ制御部
３１０    第１ＲＡＭ
３２０    第２ＲＡＭ
３３０    第３ＲＡＭ
３４０    アドレスバス
【図１】
0003862062.tif 000005
【図２】
0003862062.tif 000006
【図３】
0003862062.tif 000007
【図４】
0003862062.tif 000008
【図５】
0003862062.tif 000009
【図６】
0003862062.tif 000010
【図７】
0003862062.tif 000011