(57)【特許請求の範囲】
【請求項１】
少なくとも２つのリードソロモン符号語を含むデータ部と前記データ部のサイズを示す情報を含むヘッダー部とを含むデータフレームのうち前記ヘッダー部を解析し、前記データ部において末尾に配置される最終符号語のサイズを計算する解析部と、
前記データ部において前記最終符号語の１つ前に配置される符号語に関する誤り検出が開始するよりも前に、前記リードソロモン符号語のベースサイズと前記最終符号語のサイズとの差分に応じて前記最終符号語の誤り位置多項式の係数及び誤り数値多項式の係数を補正するための補正係数を前記最終符号語のサイズに基づいて計算する係数計算部と、
少なくとも１つの乗算器を用いて、チェンサーチによる誤り位置計算及びフォーニー法による誤り数値計算を行う誤り計算部と
を具備し、
前記係数計算部及び前記誤り計算部は、前記少なくとも１つの乗算器を共有する、
リードソロモン復号器。
【請求項２】
前記係数計算部は、前記データ部において先頭に配置される符号語の誤り検出が開始するよりも前に、前記補正係数を前記最終符号語のサイズに基づいて計算する、請求項１のリードソロモン復号器。
【請求項３】
前記係数計算部は、前記解析部が前記最終符号語のサイズの計算を終了するよりも前に初期値に対して乗算因子を第２の回数だけ反復して乗算することによって中間値を計算し、前記解析部が前記最終符号語のサイズの計算を終了してから、（Ａ）前記最終符号語のサイズが前記第２の回数に対応する閾値以下であれば前記中間値に対して前記乗算因子を前記最終符号語のサイズに応じた第１の回数と前記第２の回数との差分だけ反復して乗算することによって前記補正係数を計算し、（Ｂ）前記最終符号語のサイズが前記閾値を超えるならば前記初期値に対して前記乗算因子を前記第１の回数だけ反復して乗算することによって前記補正係数を計算する、請求項１のリードソロモン復号器。
【請求項４】
前記係数計算部は、前記最終符号語のサイズが閾値を超えるならば第１の初期値に対して乗算因子を前記最終符号語のサイズに応じた第１の回数だけ反復して乗算することによって前記補正係数を計算し、前記最終符号語のサイズが前記閾値以下であれば第２の初期値に対して前記乗算因子を前記最終符号語のサイズに応じた第２の回数だけ反復して乗算することによって前記補正係数を計算する、請求項１のリードソロモン復号器。
【請求項５】
前記データフレームを受信する無線受信部と、
請求項１のリードソロモン復号器と
を具備する、受信装置。
【発明の詳細な説明】
【技術分野】
【０００１】
実施形態は、リードソロモン符号の復号に関する。
【背景技術】
【０００２】
リードソロモン符号は、例えば地上波デジタル放送システムにおいて誤り訂正のために利用される。リードソロモン符号は、例えば複数の連続したビットを１つのシンボルとして扱うことができる。リードソロモン符号は、シンボル単位の誤り訂正を可能とする。リードソロモン符号語のベースサイズ（シンボル長）は、シンボルを定義する多元体に含まれる要素の総数によって決まる。実装上、ベースサイズよりも短い符号語（以降、短縮符号語と称される）が使用されることもある。
【０００３】
短縮符号語の復号を高速化する（即ち、復号レイテンシを低減する）ために、当該短縮符号語のサイズに応じた補正係数を利用することが知られている。一方、短縮符号語の復号過程において、係る補正係数を計算するための期間ならびにハードウェア（例えば、専用回路）を確保する必要がある。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００５−２１８０９８号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
実施形態は、リードソロモン符号語の復号レイテンシを低減することを目的とする。
【課題を解決するための手段】
【０００６】
実施形態によれば、リードソロモン復号器は、少なくとも２つのリードソロモン符号語を含むデータ部とデータ部のサイズを示す情報を含むヘッダー部とを含むデータフレームを復号する。リードソロモン復号器は、ヘッダー部に含まれる情報を用いて、データ部において末尾に配置される最終符号語のサイズを計算する解析部を含む。リードソロモン復号器は、データ部において最終符号語の１つ前に配置される符号語に関する誤り検出が開始するよりも前に、リードソロモン符号語のベースサイズと最終符号語のサイズとの差分に応じて最終符号語の誤り位置多項式の係数及び誤り数値多項式の係数を補正するための補正係数を最終符号語のサイズを用いて計算する係数計算部を含む。
【図面の簡単な説明】
【０００７】
【図１】少なくとも１つのリードソロモン符号語を含むデータフレームを例示する図。
【図２】第１の実施形態に係るリードソロモン復号器を例示するブロック図。
【図３】図２のリードソロモン復号器の動作を例示する図。
【図４】図２の補正計算部を例示する図。
【図５】図２の補正計算部を例示する図。
【図６】図２の誤り計算部を例示する図。
【図７】図２の誤り計算部を例示する図。
【図８】第１の実施形態に係るリードソロモン復号器を含む受信装置を例示するブロック図。
【発明を実施するための形態】
【０００８】
以下、図面を参照しながら実施形態についての説明が述べられる。尚、以降、説明済みの要素と同一または類似の要素には同一または類似の符号が付され、重複する説明は基本的に省略される。また、符号ＸＸＸによって参照される要素が複数存在する場合には、符号ＸＸＸ−Ａのように添え字Ａによって個別の要素が参照されたり、単に符号ＸＸＸによって係る要素が包括的に参照されたりする。
【０００９】
（第１の実施形態）  
第１の実施形態に係るリードソロモン復号器は、例えば図１に示されるデータフレームに含まれるリードソロモン符号語を誤り訂正復号し、メッセージ（或いは、データとも称される）を復元する。
【００１０】
図１のデータフレームは、ヘッダー部とデータ部とを含む。ヘッダー部には、データフレーム或いはデータ部に関する種々の情報が含まれる。例えば、ヘッダー部には、データフレーム或いはデータ部のサイズを示す情報が含まれる。
【００１１】
データ部には、少なくとも１つの符号語が含まれる。具体的には、図１の例において、メッセージは、ガロア体（Ｇａｌｏｉｓ  Ｆｉｅｌｄ；ＧＦ）（２ｑ）上で定義されるリードソロモン符号（Ｎ，Ｋ，ｔ）によって符号化されている。即ち、符号語は、多くともＫ個のシンボルからなるメッセージに２ｔ個のシンボルからなるパリティを付加したリードソロモン符号語である。このリードソロモン符号語は、多くともＮ（＝Ｋ＋２ｔ）シンボルからなる。各シンボルは、ｑビットで表現され、２ｑ通りの値を持ち得る。以降の説明において、シンボルの加算及び乗算は、ガロア体（２ｑ）上の加算及び乗算を意味する。
【００１２】
このリードソロモン符号語のベースサイズは、（２ｑ−１）シンボルである。仮に、Ｎが（２ｑ−１）未満であるならば（即ち、Ｎシンボルの符号語が短縮符号語であるならば）、短縮符号語の先頭に（２ｑ−１−Ｎ）個の零シンボル群をパディングすればよい。係る操作によれば、短縮符号語をベースサイズの符号語と数学的に同一に扱うことができる。但し、係る操作によってパディングされた零シンボル群は、伝送の必要がないので、データフレームには含まれない。
【００１３】
また、図１の例では、メッセージはＫシンボル単位で分割されて符号化されるので、データ部において末尾に配置される最終符号語を除く全ての符号語は固定サイズ（Ｎシンボル）を持つ。一方、最終符号語は、メッセージをＫシンボル単位で分割した余りのＪ（Ｊは１以上Ｋ以下の整数）シンボルが符号化されるので、メッセージのサイズに依存する可変サイズ（Ｍ（＝Ｊ＋２ｔ）シンボル）を持つ。尚、最終符号語も先頭への（２ｑ−１−Ｍ）個の零シンボル群のパディングを通じて、ベースサイズの符号語と数学的に同一に扱うことができる。図１に示される典型的なデータフレームの構造を想定すると、１つのデータフレームにおいて符号語のサイズは多くとも２種類しか存在しない。
【００１４】
図２に示されるように、本実施形態に係るリードソロモン復号器は、フレーム解析部１０１、誤り計算部１０２、補正係数記憶部１０３、データ記憶部１０４、シンドローム計算部１０５、誤り多項式係数計算部１０６、補正計算部１０７及びガロア体加算器１０８を含む。図２のリードソロモン復号器は、例えば図１のものと同一または類似の構造を持つデータフレームを入力する。具体的には、フレーム解析部１０１はデータフレームのヘッダー部（或いは、データフレーム或いはデータ部のサイズを示す情報）を入力し、シンドローム計算部１０５はデータフレームのデータ部を入力する。また、データフレームのデータ部は、データ記憶部１０４に記憶される。図２のリードソロモン復号器は、符号語に生じた誤りを例えばチェンサーチ（Ｃｈｉｅｎ  ｓｅａｒｃｈ）＆フォーニー法（Ｆｏｒｎｅｙ  ａｌｇｏｒｉｔｈｍ）によって検出し、これを訂正して復元メッセージ（出力データ）を得る。
【００１５】
フレーム解析部１０１は、例えばデータフレームのヘッダー部を入力し、データフレーム或いはデータ部のサイズを示す情報を解析する。フレーム解析部１０１は、係る情報に基づいて、データフレームの最終符号語のサイズを計算する。尚、最終符号語のサイズは、符号語全体のサイズＭである必要はなく、符号語全体からパリティシンボルを除いたサイズＪであってもよい。
【００１６】
また、フレーム解析部１０１は、図２のリードソロモン復号器が処理対象の符号語は最終符号語であるか否かを判定可能とするために、データフレームに含まれる符号語数Ｗを解析或いは計算してもよい。例えば、図２のリードソロモン復号器は、処理済みの符号語数が（Ｗ−１）未満であれば処理対象の符号語は最終符号語でないと判定し、処理済みの符号語数が（Ｗ−１）に一致すれば処理対象の符号語は最終符号語であると判定する。
【００１７】
フレーム解析部１０１は、上記解析を通じてパラメータＳを得る。パラメータＳは、最終符号語のサイズを一意に決定するものであればよい。即ち、パラメータＳは、データ部を構成する総シンボル数（図１の例では、２Ｎ＋Ｍ）であってもよいし、データ部の誤り訂正復号を通じて復元されるメッセージを構成する総シンボル数（図１の例では、２Ｋ＋Ｊ）であってもよい。
【００１８】
パラメータＳがデータ部を構成する総シンボル数を表すならば、フレーム解析部１０１は最終符号語のサイズＭを下記の数式（１）によって計算できる。前述の通り、最終符号語のサイズは、Ｍに代えてＪによって定義されてもよい。フレーム解析部１０１は、最終符号語のサイズＪを下記の数式（２）によって計算できる。更に、フレーム解析部１０１は、符号語数Ｗを下記の数式（３）によって計算できる。
【数１】
0005275398.tif 000002
【００１９】
【数２】
0005275398.tif 000003
【００２０】
【数３】
0005275398.tif 000004
【００２１】
ここで、ｍｏｄ（Ａ，Ｂ）はＢを法とするＡの剰余を表し、ｃｅｉｌ（Ａ）はＡ以上の最小の整数値を表す。  
一方、パラメータＳがデータ部の誤り訂正復号を通じて復元されるメッセージを構成する総シンボル数を表すならば、フレーム解析部１０１は最終符号語のサイズＭを下記の数式（４）によって計算できる。前述の通り、最終符号語のサイズは、Ｍに代えてＪによって定義されてもよい。フレーム解析部１０１は、最終符号語のサイズＪを下記の数式（５）によって計算できる。更に、フレーム解析部１０１は、符号語数Ｗを下記の数式（６）によって計算できる。
【数４】
0005275398.tif 000005
【００２２】
【数５】
0005275398.tif 000006
【００２３】
【数６】
0005275398.tif 000007
【００２４】
尚、Ｎ（或いは、Ｋ）の値はデータフレームのヘッダー部の解析を通じて得られるかもしれないし、これらはフレーム解析部１０１において既知であるかもしれない。
【００２５】
誤り計算部１０２は、２つの動作モードを備える。これら２つの動作モードは、便宜的に、初期化モード及び誤り検出モードと称される。誤り計算部１０２は、初期化モードにおいて、処理対象のデータフレームの最終符号語に関する補正係数βｉ（ｉ＝１，・・・，ｔ）を計算する。また、誤り計算部１０２は、誤り検出モードにおいて、処理対象のデータフレームの各符号語の誤り検出を例えばチェンサーチ＆フォーニー法によって実行する。誤り計算部１０２は、初期化モード及び誤り検出モードを時分割で実行する。従って、誤り計算部１０２は、補正係数βｉの計算と各符号語の誤り検出との両方を共有のハードウェアによって実現できる。尚、誤り計算部１０２のハードウェア構成例ならびに初期化モード及び誤り検出モードにおける動作の詳細は後述される。
【００２６】
図３を参照すると、図２のリードソロモン復号器の各要素の動作タイミングが例示されている。後述のように、誤り計算部１０２の初期化モードにおいて最終符号語のサイズを参照する必要があるので、フレーム解析部１０１による最終符号語のサイズＭ（或いはＪ）の計算は、少なくとも誤り計算部１０２が初期化モードを終了するよりも前に終了している必要がある。但し、図３にも示されているが、後述の中間値を計算するなどの理由で、フレーム解析部１０１が最終符号語のサイズの計算を終了するよりも前に、誤り計算部１０２が初期化モードを開始することはあり得る。
【００２７】
また、後述のように、補正計算部１０７による最終符号語に関する補正計算において補正係数βｉが必要となる。従って、補正計算部１０７が最終符号語に関する補正計算を開始するよりも前に、誤り計算部１０２は初期化モードを終了する必要がある。例えば、図３に示されるように、誤り計算部１０２は、データ部において先頭に配置される先頭符号語に関する誤り検出モードを開始するよりも前に、初期化モードを終了する。尚、誤り計算部１０２は、少なくとも、データ部において最終符号語の１つ前に配置される符号語に関する誤り検出モードを開始するよりも前に初期化モードを終了する。係る制約が満たされるならば、補正係数βｉの計算は復号レイテンシの増加を伴わない。
【００２８】
ところで、実装条件、最終符号語のサイズなどの種々の要因により、先頭符号語に関する誤り検出モードが開始可能となった時点では、誤り計算部１０２が初期化モードを終了していない状況が想定される。係る状況において、誤り計算部１０２は、初期化モードを終了するまで先頭符号語に関する誤り検出モードを待機させてもよい。或いは、誤り計算部１０２は、所与の符号語に関する誤り検出モードを終了してから次の符号語に関する誤り検出モードを開始するまでの隙間期間において、初期化モードの残余の計算を実行してもよい。係る間欠動作によれば、待機に起因する復号レイテンシの増加を回避または抑制できる。
【００２９】
誤り計算部１０２は、初期化モードを通じて計算した補正係数βｉを補正係数記憶部１０３に記憶させる。補正係数記憶部１０３に記憶された補正係数βｉは、最終符号語に関する補正計算のために補正計算部１０７によって読み出される。
【００３０】
シンドローム計算部１０５は、データフレームのデータ部を入力し、このデータ部に含まれる符号語毎にシンドロームσｉ（ｉ＝０，・・・，２ｔ−１）を計算する。シンドローム計算部１０５は、計算したシンドロームσｉを誤り多項式係数計算部１０６へ出力する。
【００３１】
シンドロームσｉは、生成多項式Ｇ（ｘ）の根αｉ（ｉ＝０，・・・２ｔ−１）を処理対象の符号語を表す多項式Ｒ（ｘ）に代入することによって計算される。即ち、シンドローム計算部１０５は、シンドロームσｉを下記の数式（７）に従って計算する。尚、生成多項式Ｇ（ｘ）は、下記の数式（８）で表される。
【数７】
0005275398.tif 000008
【００３２】
【数８】
0005275398.tif 000009
【００３３】
符号語に誤りが含まれていなければ、全てのシンドロームσｉは零となる。一方、符号語に誤りが含まれていれば、シンドロームσｉは誤りのパターン（誤りの位置及び誤りの数値）のみに依存する非零値となる。換言すれば、シンドロームσｉは符号化前のデータ（メッセージ）には依存しない。
【００３４】
誤り多項式係数計算部１０６は、シンドローム計算部１０５からのシンドロームσｉを入力する。誤り多項式係数計算部１０６は、入力したシンドロームσｉに基づいて、誤り位置多項式Λ（ｘ）の係数λｉ（ｉ＝０，１，２，・・・ｔ）と誤り数値多項式Ω（ｘ）の係数ωｉ（ｉ＝０，１，２，・・・，ｔ−１）とを計算する。誤り多項式係数計算部１０６は、例えばＢｅｒｌｅｋａｍｐ−Ｍａｓｓｅｙアルゴリズム、ユークリッド法などの公知の計算手法によって、係数λｉ及び係数ωｉを計算できる。誤り多項式係数計算部１０６は、計算した係数λｉ及び係数ωｉを補正計算部１０７へ出力する。
【００３５】
補正計算部１０７は、誤り多項式係数計算部１０６からの係数λｉ及び係数ωｉを入力する。補正計算部１０７は、入力した係数λｉ及び係数ωｉに補正係数を乗算し、補正済み係数λｉ’及び補正済み係数ωｉ’を得る。補正計算部１０７は、計算した補正済み係数λｉ’及び補正済み係数ωｉ’を誤り計算部１０２へ出力する。
【００３６】
補正計算は、短縮符号の誤り検出を高速化するために実行される。具体的には、短縮符号の先頭には零シンボル群がパディングされているので、これらを無視して当該短縮符号の先頭シンボルから誤り検出を開始するために、符号語のサイズに応じた補正係数が係数λｉ及び係数ωｉに乗算される。
【００３７】
前述の通り、最終符号語を除く全ての符号語は固定サイズ（Ｎシンボル）を持つ。従って、最終符号語を除く全ての符号語に関する補正係数もまた固定である。そこで、最終符号語を除く全ての符号語に関する補正係数γｉ（ｉ＝０，１，２，・・・，ｔ）を予め計算し、図示しない記憶部に記憶させておくことによって、復号過程において最終符号語を除く全ての符号語に関する補正係数の計算を省略できる。また、前述の通り、最終符号語に関する補正係数βｉは誤り計算部１０２の初期化モードによって計算され、補正係数記憶部１０３に記憶されている。尚、β０＝１である。
【００３８】
補正計算部１０７は、最終符号語を除く全ての符号語に関して、下記の数式（９）に従って係数λｉ及び係数ωｉを補正する。補正計算部１０７は、最終符号語に関して、下記の数式（１０）に従って係数λｉ及び係数ωｉを補正する。
【数９】
0005275398.tif 000010
【００３９】
【数１０】
0005275398.tif 000011
【００４０】
尚、補正係数γｉは下記の数式（１１）によって計算できる。  
【数１１】
0005275398.tif 000012
【００４１】
尚、補正計算部１０７は、補正係数γｉ＝１に固定してもよい（即ち、最終符号語を除く全ての符号語に関する補正計算を省略してもよい）。補正計算を省略すると、短縮符号の先頭シンボルからではなく、パディングされた零シンボル群の先頭から誤り検出が開始する。Ｎが２ｑに近い値であれば、補正計算の省略による復号レイテンシの増加は限定的となる。
【００４２】
補正計算部１０７は、図４に示されるように、（２ｔ−１）個のガロア体乗算器２０１−１，・・・，２０１−（ｔ−１），２０２−１，・・・，２０２−ｔと、ｔ個のマルチプレクサ２０３−１，・・・，２０３−ｔとを含むように実装することができる。具体的には、ガロア体乗算器２０１−ｉは、係数ωｉの補正計算を行う。ガロア体乗算器２０２−ｉは、係数λｉの補正計算を行う。マルチプレクサ２０３−ｉ（ｉ＝１，・・・，ｔ）は、処理対象の符号語が最終符号語であるか否かに応じて補正係数βｉ及び補正係数γｉのいずれか一方を選択し、ガロア体乗算器２０１−ｉ及びガロア体乗算器２０２−ｉに供給する。但し、係数ωｔは存在しない。故に、マルチプレクサ２０３−ｔは、処理対象の符号語が最終符号語であるか否かに応じて補正係数βｔ及び補正係数γｔのいずれか一方を選択し、ガロア体乗算器２０２−ｔに供給する。
【００４３】
また、補正計算部１０７は、図５に示されるように、パラレル／シリアル変換部２１１と、１個のガロア体乗算器２１２と、補正係数選択部２１３と、シリアル／パラレル変換部２１４とを含むように実装することもできる。パラレル／シリアル変換部２１１は、係数ωｉ及び係数λｉにパラレル／シリアル変換を行って、係数系列をガロア体乗算器２１２に供給する。補正係数選択部２１３は、上記係数系列と対応するように、補正係数１（＝γ０＝β０），γ１，・・・，γｔ，β１・・・，βｔから１つずつ順次選択し、補正係数系列をガロア体乗算器２１２に供給する。ガロア体乗算器２１２は、パラレル／シリアル変換部２１１からの係数系列と補正係数選択部２１３からの補正係数系列とを順次乗算することによって、補正計算を行う。ガロア体乗算器２１２は、補正済み係数系列をシリアル／パラレル変換部２１４に供給する。シリアル／パラレル変換部２１４は、ガロア体乗算器２１２からの補正済み係数系列にシリアル／パラレル変換を行って、補正済み係数ωｉ’及び補正済み係数λｉ’を出力する。
【００４４】
更に、図４及び図５を組み合わせることにより、補正計算部１０７は、２個乃至（２ｔ−２）個のガロア体乗算器を含むように実装することもできる。従って、補正計算部１０７は、１乃至（２ｔ−１）個のガロア体乗算器を含むように実装することができる。尚、補正計算部１０７を実装するために必要とされるガロア体乗算器は少なくとも１つなので、補正計算部１０７は誤り多項式係数計算部１０６に含まれる複数のガロア体乗算器の一部または全部を共有して実装されてもよい。
【００４５】
誤り計算部１０２は、誤り検出モードにおいて、補正計算部１０７からの補正済み係数λｉ’及び補正済み係数ωｉ’を入力する。誤り計算部１０２は、チェンサーチによって誤り位置を計算すると共に、フォーニー法によって誤り数値を計算する。誤り計算部１０２は、誤り数値を検出する。誤り計算部１０２は、検出した誤り数値をガロア体加算器１０８へ出力する。
【００４６】
具体的には、チェンサーチは、Λ（αｉ）の値が零であるか否かによって、第Ｎ−ｉ番目（最終符号語に関しては第Ｍ−ｉ番目）のシンボルに誤りがあるか否かを判定する手法である。フォーニー法は、Ω（αｉ）／Λ（ｏｄｄ）（αｉ）の値に基づいて誤り数値を計算する手法である。尚、Λ（ｏｄｄ）（ｘ）は、誤り位置多項式Λ（ｘ）に含まれる奇数次の項のみからなる部分多項式である。
【００４７】
誤り計算部１０２は、図６に示されるように、制御部３０１と、ｔ個のマルチプレクサ３０２−１，・・・，３０２−ｔと、（２ｔ＋１）個のフリップフロップ３０３−０，・・・，３０３−（ｔ−１），３０５−０，・・・，３０５−ｔと、（２ｔ−１）個のガロア体乗算器３０４−１，・・・，３０４−（ｔ−１），３０６−１，・・・，３０６−ｔと、加算部３０７と、ガロア体乗算器３０８と、マルチプレクサ３０９と、偶数項加算部３１０と、奇数項加算部３１１と、ガロア体加算器３１２と、誤り検出部３１３と、逆元計算部３１４とを含むように実装することができる。
【００４８】
制御部３０１は、初期化モードにおいて、マルチプレクサ３０２−１，・・・，３０２−ｔの第１の入力端子に初期値φ１，・・・，φｔを供給すると共に、マルチプレクサ３０２−１，・・・，３０２−ｔに第１の入力端子を選択させるための選択信号を供給する。初期値φｉは、下記の数式（１２）で表される。尚、数式（１２）において、Ｐは初期値を決定するためのパラメータである。
【数１２】
0005275398.tif 000013
【００４９】
また、制御部３０１は、誤り検出モードにおいて、マルチプレクサ３０２−１，・・・，３０２−ｔに第２の入力端子を選択させるための選択信号を供給する。また、制御部３０１は、フリップフロップ３０５−０，・・・，３０５−ｔに第１ロード信号を供給し、フリップフロップ３０３−０，・・・，３０３−（ｔ−１）に第２ロード信号を供給する。
【００５０】
マルチプレクサ３０２−１，・・・，３０２−ｔは、第１の入力端子において制御部３０１からの初期値φ１，・・・，φｔを入力し、第２の入力端子において補正計算部１０７からの補正済み係数λ１’，・・・，λｔ’を入力する。マルチプレクサ３０２−１，・・・，３０２−ｔは、初期化モードにおいて、制御部３０１からの選択信号に従って第１の入力端子を選択し、初期値φ１，・・・，φｔを出力する。マルチプレクサ３０２−１，・・・，３０２−ｔは、誤り検出モードにおいて、制御部３０１からの選択信号に従って第２の入力端子を選択し、補正済み係数λ１’，・・・，λｔ’を出力する。
【００５１】
フリップフロップ３０３−０は、誤り検出モードにおいて、補正計算部１０７からの補正済み係数ω０’を加算部３０７へ供給する。フリップフロップ３０３−１，・・・，３０３−（ｔ−１）及びガロア体乗算器３０４−１，・・・，３０４−（ｔ−１）は、誤り検出モードにおいて、補正計算部１０７からの補正済み係数ω１’，・・・，ωｔ−１’に乗算因子α１，・・・，αｔ−１を乗算し、乗算結果を加算部３０７へ供給する。
【００５２】
フリップフロップ３０５−０は、誤り検出モードにおいて、補正計算部１０７からの補正済み係数λ０’を偶数項加算部３１０へ供給する。フリップフロップ３０５−１，・・・，３０５−ｔ及びガロア体乗算器３０６−１，・・・，３０６−ｔは、誤り検出モードにおいて、補正計算部１０７からの補正済み係数λ１’，・・・，λｔ’に乗算因子α１，・・・，αｔを乗算し、乗算結果を偶数項加算部３１０及び奇数項加算部３１１のうちの一方へ供給する。
【００５３】
また、フリップフロップ３０５−１，・・・，３０５−ｔ及びガロア体乗算器３０６−１，・・・，３０６−ｔは、初期化モードにおいて、マルチプレクサ３０２−１，・・・，３０２−ｔからの初期値φ１，・・・，φｔに乗算因子α１，・・・，αｔをｍｏｄ（Ｐ−Ｍ，２ｑ）サイクルだけ反復して乗算し、補正係数β１，・・・，βｔを計算する。即ち、補正係数βｉ＝α−ｉＭ（ｉ＝１，・・・，ｔ）である。フリップフロップ３０５−１，・・・，３０５−ｔは、計算された補正係数β１，・・・，βｔを補正係数記憶部１０３へ供給する。
【００５４】
加算部３０７は、誤り検出モードにおいて、フリップフロップ３０３−０，・・・，３０３−（ｔ−１）からの信号を入力し、これらを加算して誤り数値多項式を形成する。偶数項加算部３１０は、誤り検出モードにおいて、フリップフロップ３０５−０，・・・，３０５−ｔからの信号のうち誤り位置多項式の偶数項に相当するものを入力し、これらを加算する。奇数項加算部３１１は、誤り検出モードにおいて、フリップフロップ３０５−１，・・・，３０５−ｔからの信号のうち誤り位置多項式の奇数項に相当するものを入力し、これらを加算する。
【００５５】
ガロア体加算器３１２は、偶数項加算部３１０及び奇数項加算部３１１からの信号を加算し、誤り位置多項式を計算する。誤り検出部３１３は、ガロア体加算器３１２から誤り位置多項式を入力し、誤り検出を行う。逆元計算部３１４は、奇数項加算部３１１から誤り位置多項式の奇数項部分を入力し、この逆元を計算する。逆元計算部３１４は、計算した誤り位置多項式の奇数項部分の逆元をガロア体乗算器３０８に与える。ガロア体乗算器３０８は、加算部３０７からの誤り数値多項式と、逆元計算部３１４からの誤り位置多項式の奇数項部分の逆元とを乗算し、乗算結果（即ち、Ω（αｉ）／Λ（ｏｄｄ）（αｉ））をマルチプレクサ３０９の第１の入力端子に供給する。マルチプレクサ３０９は、第２の入力端子において零を入力する。マルチプレクサ３０９は、誤り検出部３１３からの誤り検出結果に応じて、零及びガロア体乗算器３０８からの信号のいずれか一方を選択し、誤り数値として出力する。
【００５６】
図６の誤り計算部１０２によれば、最終符号語に関する補正係数の計算が、チェンサーチのためのフリップフロップ３０５−１，・・・，３０５−ｔ及びガロア体乗算器３０６−１，・・・，３０６−ｔを共有して実現される。
【００５７】
また、誤り計算部１０２は、図７に示されるように、制御部３２１と、ｔ個のマルチプレクサ３２２−１，・・・，３２２−ｔと、（２ｔ＋１）個のフリップフロップ３２３−０，・・・，３２３−（ｔ−１），３２５−０，・・・，３２５−ｔと、（２ｔ−１）個のガロア体乗算器３２４−１，・・・，３２４−（ｔ−１），３２６−１，・・・，３２６−ｔと、加算部３０７と、ガロア体乗算器３０８と、マルチプレクサ３０９と、偶数項加算部３１０と、奇数項加算部３１１と、ガロア体加算器３１２と、誤り検出部３１３と、逆元計算部３１４とを含むように実装することもできる。
【００５８】
尚、誤り検出モードにおいて、フリップフロップ３２３−０，・・・，３２３−（ｔ−１），３２５−０，・・・，３２５−ｔ及びガロア体乗算器３２４−１，・・・，３２４−（ｔ−１），３２６−１，・・・，３２６−ｔの動作は、フリップフロップ３０３−０，・・・，３０３−（ｔ−１），３０５−０，・・・，３０５−ｔ及びガロア体乗算器３０４−１，・・・，３０４−（ｔ−１），３０６−１，・・・，３０６−ｔのものと同じである。
【００５９】
制御部３２１は、初期化モードにおいて、マルチプレクサ３２２−１，・・・，３２２−ｔの第１の入力端子に初期値φ１，・・・，φｔを供給すると共に、マルチプレクサ３２２−１，・・・，３２２−ｔに第１の入力端子を選択させるための選択信号を供給する。また、制御部３２１は、誤り検出モードにおいて、マルチプレクサ３２２−１，・・・，３２２−ｔに第２の入力端子を選択させるための選択信号を供給する。また、制御部３２１は、フリップフロップ３２５−０，・・・，３２５−ｔに第１ロード信号を供給し、フリップフロップ３２６−０，・・・，３２６−（ｔ−１）に第２ロード信号を供給する。
【００６０】
マルチプレクサ３２２−１，・・・，３２２−（ｔ−１）は、第１の入力端子において制御部３２１からの初期値φ１，・・・，φｔ−１を入力し、第２の入力端子において補正計算部１０７からの補正済み係数ω１’，・・・，ωｔ−１’を入力する。マルチプレクサ３２２−１，・・・，３２２−（ｔ−１）は、初期化モードにおいて、制御部３２１からの選択信号に従って第１の入力端子を選択し、初期値φ１，・・・，φｔ−１を出力する。マルチプレクサ３２２−１，・・・，３２２−（ｔ−１）は、誤り検出モードにおいて、制御部３２１からの選択信号に従って第２の入力端子を選択し、補正済み係数ω１’，・・・，ωｔ−１’を出力する。
【００６１】
マルチプレクサ３２２−ｔは、第１の入力端子において制御部３２１からの初期値φｔを入力し、第２の入力端子において補正計算部１０７からの補正済み係数λｔ’を入力する。マルチプレクサ３２２−ｔは、初期化モードにおいて、制御部３２１からの選択信号に従って第１の入力端子を選択し、初期値φｔを出力する。マルチプレクサ３２２−ｔは、誤り検出モードにおいて、制御部３２１からの選択信号に従って第２の入力端子を選択し、補正済み係数λｔ’を出力する。
【００６２】
フリップフロップ３２３−１，・・・，３２３−（ｔ−１）及びガロア体乗算器３２４−１，・・・，３２４−（ｔ−１）は、初期化モードにおいて、マルチプレクサ３２２−１，・・・，３２２−（ｔ−１）からの初期値φ１，・・・，φｔ−１に乗算因子α１，・・・，αｔ−１をｍｏｄ（Ｐ−Ｍ，２ｑ）サイクルだけ反復して乗算し、補正係数β１，・・・，βｔ−１を計算する。フリップフロップ３２３−１，・・・，３２３−（ｔ−１）は、計算された補正係数β１，・・・，βｔ−１を補正係数記憶部１０３へ供給する。また、フリップフロップ３２５−ｔ及びガロア体乗算器３２６−ｔは、初期化モードにおいて、マルチプレクサ３２２−ｔからの初期値φｔに乗算因子αｔをｍｏｄ（Ｐ−Ｍ，２ｑ）サイクルだけ反復して乗算し、補正係数βｔを計算する。フリップフロップ３２５−ｔは、計算された補正係数βｔを補正係数記憶部１０３へ供給する。
【００６３】
図７の誤り計算部１０２によれば、最終符号語に関する補正係数の計算が、フォーニー法のためのフリップフロップ３２３−１，・・・，３２３−（ｔ−１）及びガロア体乗算器３２４−１，・・・，３２４−（ｔ−１）と、チェンサーチのためのフリップフロップ３２５−ｔ及びガロア体乗算器３２６−ｔとを共有して実現される。
【００６４】
尚、図６及び図７の例によれば、誤り計算部１０２は、初期化モードのための全てのハードウェア構成を誤り検出モードのためのものと共有している。しかしながら、誤り計算部１０２は、初期化モードのための一部のハードウェア構成を誤り検出モードのためのものと共有し、残余のハードウェア構成を別途設けてもよい。
【００６５】
前述の通り、初期化モードにおける補正係数の計算は、ｍｏｄ（Ｐ−Ｍ，２ｑ）サイクルを必要とする。例えば、Ｐ＝０（即ち、φｉ＝１）であって、かつ、最終符号語のサイズＭ＝１であれば、補正係数βｉを計算するために２ｑ−１サイクルが必要となる。以降、補正係数βｉの計算に伴う復号レイテンシの増加を回避または抑制するための手法が述べられる。
【００６６】
パラメータＰに対して複数の異なる値を与えることによって、複数の異なる初期値φｉ（＝α−ｉＰ）を用意することができる。誤り計算部１０２は、係る複数の異なる初期値を最終符号語のサイズに応じて切り替えて使用することによって、補正係数βｉを計算するために必要なサイクル数を削減できる。例えば、誤り計算部１０２は、パラメータＰに０，２ｑ−１を与えて第１の初期値及び第２の初期値を用意する。そして、誤り計算部１０２は、最終符号語のサイズＭが閾値２ｑ−１以下であれば第２の初期値を使用し、最終符号語のサイズＭが閾値２ｑ−１を超えるならば第１の初期値を使用する。係る動作によれば、補正係数βｉを計算するために必要なサイクル数を最大で２ｑ−１に抑制できる。
【００６７】
また、誤り計算部１０２は、フレーム解析部１０１が最終符号語のサイズＭの計算を終了するよりも前に補正係数βｉの計算を開始することによって、補正係数βｉの中間値を予め計算してもよい。例えば、誤り計算部１０２は、最終符号語のサイズＭが計算される前に、初期値φｉ＝１（即ち、Ｐ＝０）として２ｑ−１サイクル分の計算を終了させておくとする。誤り計算部１０２は、最終符号語のサイズＭが閾値２ｑ−１以下であれば中間値を使用して補正係数βｉの計算を続行し、最終符号語のサイズＭが閾値２ｑ−１を超えるならば再び初期値φｉ＝１から補正係数βｉの計算を開始すればよい。係る動作によれば、最終符号語のサイズＭの計算が終了してから補正係数βｉの計算が終了するまでに必要なサイクル数を最大で２ｑ−１に抑制できる。
【００６８】
ガロア体加算器１０８は、データ記憶部１０４から処理対象の符号語と、誤り計算部１０２からの誤り数値とを入力する。ガロア体加算器１０８は、処理対象の符号語と誤り数値とを加算（即ち、排他的論理和）することによって誤りを訂正し、出力データを得る。
【００６９】
以上説明したように、第１の実施形態に係るリードソロモン復号器は、最終符号語に関する補正係数の計算を最終符号語の１つ前の符号語の誤り検出が開始するよりも前に終了する。従って、本実施形態に係るリードソロモン復号器によれば、最終符号語に関する補正係数の計算に伴う復号レイテンシの増加が回避される（或いは、抑制される）。また、本実施形態に係るリードソロモン復号器は、誤り計算部のハードウェアを時分割で使用して最終符号語に関する補正係数の計算及び各符号語の誤り検出を実行する。従って、本実施形態に係るリードソロモン復号器によれば、最終符号語に関する補正計算のために専用のハードウェアを設ける必要がないので、回路規模及び消費電力の増大を抑制できる。
【００７０】
第１の実施形態に係るリードソロモン復号器は、例えば受信装置に組み込まれ得る。係る受信装置は、図８に示されるように、無線受信部４０２、Ａ／Ｄ変換部４０３、データ復調部４０４、リードソロモン復号部４０５及びＭＡＣ（Ｍｅｄｉａ  Ａｃｃｅｓｓ  Ｃｏｎｔｒｏｌ）層処理部４０６を含む。図８の受信装置は、アンテナ４０１を介して無線信号を受信する。
【００７１】
無線受信部４０２は、アンテナ４０１によって受信された無線信号をベースバンドのアナログ信号へと変換する。Ａ／Ｄ変換部４０３は、ベースバンドのアナログ信号をデジタル信号へと変換する。データ復調部４０４は、Ａ／Ｄ変換部４０３からのデジタル信号に等化処理、周波数オフセット処理など（即ち、通信路及びアナログ回路の歪補正処理）を行って、ＢＰＳＫ（Ｂｉｎａｒｙ  Ｐｈａｓｅ  Ｓｈｉｆｔ  Ｋｅｙｉｎｇ）、ＱＰＳＫ（Ｑｕａｄｒａｔｕｒｅ  Ｐｈａｓｅ  Ｓｈｉｆｔ  Ｋｅｙｉｎｇ）などの変調信号点を復元し、復元した変調信号点に対応するビット値を推定する。
【００７２】
リードソロモン復号部４０５として、第１の実施形態に係るリードソロモン復号器が組み込まれる。リードソロモン復号部４０５は、データ復調部４０４からのビット値（前述のデータフレームに相当する）に対して前述の誤り訂正復号を行い、誤り訂正済みの受信データを得る。リードソロモン復号部４０５は、誤り訂正済みの受信データを例えばＭＡＣ層処理部４０６に供給する。ＭＡＣ層処理部４０６は、リードソロモン復号部４０５から誤り訂正済みの受信データを入力して所与のＭＡＣ処理を行い、これを上位レイヤへと供給する。
【００７３】
本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【００７４】
１０１・・・フレーム解析部
１０２・・・誤り計算部
１０３・・・補正係数記憶部
１０４・・・データ記憶部
１０５・・・シンドローム計算部
１０６・・・誤り多項式係数計算部
１０７・・・補正計算部
１０８・・・ガロア体加算器
２０１，２０２，２１２・・・ガロア体乗算器
２０３・・・マルチプレクサ
２１１・・・パラレル／シリアル変換部
２１３・・・補正係数選択部
２１４・・・シリアル／パラレル変換部
３０１，３２１・・・制御部
３０２，３０９，３２２・・・マルチプレクサ
３０３，３０５，３２３，３２５・・・フリップフロップ
３０４，３０６，３０８，３２４，３２６・・・ガロア体乗算器
３０７・・・加算部
３１０・・・偶数項加算部
３１１・・・奇数項加算部
３１２・・・ガロア体加算器
３１３・・・誤り検出部
３１４・・・逆元計算部
４０１・・・アンテナ
４０２・・・無線受信部
４０３・・・Ａ／Ｄ変換部
４０４・・・データ復調部
４０５・・・リードソロモン復号部
４０６・・・ＭＡＣ層処理部
【図１】
0005275398.tif 000014
【図２】
0005275398.tif 000015
【図３】
0005275398.tif 000016
【図４】
0005275398.tif 000017
【図５】
0005275398.tif 000018
【図６】
0005275398.tif 000019
【図７】
0005275398.tif 000020
【図８】
0005275398.tif 000021