JP5275398B2 - リードソロモン復号器及び受信装置 - Google Patents

Description

実施形態は、リードソロモン符号の復号に関する。

リードソロモン符号は、例えば地上波デジタル放送システムにおいて誤り訂正のために利用される。リードソロモン符号は、例えば複数の連続したビットを１つのシンボルとして扱うことができる。リードソロモン符号は、シンボル単位の誤り訂正を可能とする。リードソロモン符号語のベースサイズ（シンボル長）は、シンボルを定義する多元体に含まれる要素の総数によって決まる。実装上、ベースサイズよりも短い符号語（以降、短縮符号語と称される）が使用されることもある。

短縮符号語の復号を高速化する（即ち、復号レイテンシを低減する）ために、当該短縮符号語のサイズに応じた補正係数を利用することが知られている。一方、短縮符号語の復号過程において、係る補正係数を計算するための期間ならびにハードウェア（例えば、専用回路）を確保する必要がある。

特開２００５−２１８０９８号公報

実施形態は、リードソロモン符号語の復号レイテンシを低減することを目的とする。

実施形態によれば、リードソロモン復号器は、少なくとも２つのリードソロモン符号語を含むデータ部とデータ部のサイズを示す情報を含むヘッダー部とを含むデータフレームを復号する。リードソロモン復号器は、ヘッダー部に含まれる情報を用いて、データ部において末尾に配置される最終符号語のサイズを計算する解析部を含む。リードソロモン復号器は、データ部において最終符号語の１つ前に配置される符号語に関する誤り検出が開始するよりも前に、リードソロモン符号語のベースサイズと最終符号語のサイズとの差分に応じて最終符号語の誤り位置多項式の係数及び誤り数値多項式の係数を補正するための補正係数を最終符号語のサイズを用いて計算する係数計算部を含む。

少なくとも１つのリードソロモン符号語を含むデータフレームを例示する図。 第１の実施形態に係るリードソロモン復号器を例示するブロック図。 図２のリードソロモン復号器の動作を例示する図。 図２の補正計算部を例示する図。 図２の補正計算部を例示する図。 図２の誤り計算部を例示する図。 図２の誤り計算部を例示する図。 第１の実施形態に係るリードソロモン復号器を含む受信装置を例示するブロック図。

以下、図面を参照しながら実施形態についての説明が述べられる。尚、以降、説明済みの要素と同一または類似の要素には同一または類似の符号が付され、重複する説明は基本的に省略される。また、符号ＸＸＸによって参照される要素が複数存在する場合には、符号ＸＸＸ−Ａのように添え字Ａによって個別の要素が参照されたり、単に符号ＸＸＸによって係る要素が包括的に参照されたりする。

（第１の実施形態）
第１の実施形態に係るリードソロモン復号器は、例えば図１に示されるデータフレームに含まれるリードソロモン符号語を誤り訂正復号し、メッセージ（或いは、データとも称される）を復元する。

図１のデータフレームは、ヘッダー部とデータ部とを含む。ヘッダー部には、データフレーム或いはデータ部に関する種々の情報が含まれる。例えば、ヘッダー部には、データフレーム或いはデータ部のサイズを示す情報が含まれる。

データ部には、少なくとも１つの符号語が含まれる。具体的には、図１の例において、メッセージは、ガロア体（Ｇａｌｏｉｓ Ｆｉｅｌｄ；ＧＦ）（２^ｑ）上で定義されるリードソロモン符号（Ｎ，Ｋ，ｔ）によって符号化されている。即ち、符号語は、多くともＫ個のシンボルからなるメッセージに２ｔ個のシンボルからなるパリティを付加したリードソロモン符号語である。このリードソロモン符号語は、多くともＮ（＝Ｋ＋２ｔ）シンボルからなる。各シンボルは、ｑビットで表現され、２^ｑ通りの値を持ち得る。以降の説明において、シンボルの加算及び乗算は、ガロア体（２^ｑ）上の加算及び乗算を意味する。

このリードソロモン符号語のベースサイズは、（２^ｑ−１）シンボルである。仮に、Ｎが（２^ｑ−１）未満であるならば（即ち、Ｎシンボルの符号語が短縮符号語であるならば）、短縮符号語の先頭に（２^ｑ−１−Ｎ）個の零シンボル群をパディングすればよい。係る操作によれば、短縮符号語をベースサイズの符号語と数学的に同一に扱うことができる。但し、係る操作によってパディングされた零シンボル群は、伝送の必要がないので、データフレームには含まれない。

また、図１の例では、メッセージはＫシンボル単位で分割されて符号化されるので、データ部において末尾に配置される最終符号語を除く全ての符号語は固定サイズ（Ｎシンボル）を持つ。一方、最終符号語は、メッセージをＫシンボル単位で分割した余りのＪ（Ｊは１以上Ｋ以下の整数）シンボルが符号化されるので、メッセージのサイズに依存する可変サイズ（Ｍ（＝Ｊ＋２ｔ）シンボル）を持つ。尚、最終符号語も先頭への（２^ｑ−１−Ｍ）個の零シンボル群のパディングを通じて、ベースサイズの符号語と数学的に同一に扱うことができる。図１に示される典型的なデータフレームの構造を想定すると、１つのデータフレームにおいて符号語のサイズは多くとも２種類しか存在しない。

図２に示されるように、本実施形態に係るリードソロモン復号器は、フレーム解析部１０１、誤り計算部１０２、補正係数記憶部１０３、データ記憶部１０４、シンドローム計算部１０５、誤り多項式係数計算部１０６、補正計算部１０７及びガロア体加算器１０８を含む。図２のリードソロモン復号器は、例えば図１のものと同一または類似の構造を持つデータフレームを入力する。具体的には、フレーム解析部１０１はデータフレームのヘッダー部（或いは、データフレーム或いはデータ部のサイズを示す情報）を入力し、シンドローム計算部１０５はデータフレームのデータ部を入力する。また、データフレームのデータ部は、データ記憶部１０４に記憶される。図２のリードソロモン復号器は、符号語に生じた誤りを例えばチェンサーチ（Ｃｈｉｅｎ ｓｅａｒｃｈ）＆フォーニー法（Ｆｏｒｎｅｙ ａｌｇｏｒｉｔｈｍ）によって検出し、これを訂正して復元メッセージ（出力データ）を得る。

フレーム解析部１０１は、例えばデータフレームのヘッダー部を入力し、データフレーム或いはデータ部のサイズを示す情報を解析する。フレーム解析部１０１は、係る情報に基づいて、データフレームの最終符号語のサイズを計算する。尚、最終符号語のサイズは、符号語全体のサイズＭである必要はなく、符号語全体からパリティシンボルを除いたサイズＪであってもよい。

また、フレーム解析部１０１は、図２のリードソロモン復号器が処理対象の符号語は最終符号語であるか否かを判定可能とするために、データフレームに含まれる符号語数Ｗを解析或いは計算してもよい。例えば、図２のリードソロモン復号器は、処理済みの符号語数が（Ｗ−１）未満であれば処理対象の符号語は最終符号語でないと判定し、処理済みの符号語数が（Ｗ−１）に一致すれば処理対象の符号語は最終符号語であると判定する。

フレーム解析部１０１は、上記解析を通じてパラメータＳを得る。パラメータＳは、最終符号語のサイズを一意に決定するものであればよい。即ち、パラメータＳは、データ部を構成する総シンボル数（図１の例では、２Ｎ＋Ｍ）であってもよいし、データ部の誤り訂正復号を通じて復元されるメッセージを構成する総シンボル数（図１の例では、２Ｋ＋Ｊ）であってもよい。

パラメータＳがデータ部を構成する総シンボル数を表すならば、フレーム解析部１０１は最終符号語のサイズＭを下記の数式（１）によって計算できる。前述の通り、最終符号語のサイズは、Ｍに代えてＪによって定義されてもよい。フレーム解析部１０１は、最終符号語のサイズＪを下記の数式（２）によって計算できる。更に、フレーム解析部１０１は、符号語数Ｗを下記の数式（３）によって計算できる。

ここで、ｍｏｄ（Ａ，Ｂ）はＢを法とするＡの剰余を表し、ｃｅｉｌ（Ａ）はＡ以上の最小の整数値を表す。
一方、パラメータＳがデータ部の誤り訂正復号を通じて復元されるメッセージを構成する総シンボル数を表すならば、フレーム解析部１０１は最終符号語のサイズＭを下記の数式（４）によって計算できる。前述の通り、最終符号語のサイズは、Ｍに代えてＪによって定義されてもよい。フレーム解析部１０１は、最終符号語のサイズＪを下記の数式（５）によって計算できる。更に、フレーム解析部１０１は、符号語数Ｗを下記の数式（６）によって計算できる。

尚、Ｎ（或いは、Ｋ）の値はデータフレームのヘッダー部の解析を通じて得られるかもしれないし、これらはフレーム解析部１０１において既知であるかもしれない。

誤り計算部１０２は、２つの動作モードを備える。これら２つの動作モードは、便宜的に、初期化モード及び誤り検出モードと称される。誤り計算部１０２は、初期化モードにおいて、処理対象のデータフレームの最終符号語に関する補正係数β_ｉ（ｉ＝１，・・・，ｔ）を計算する。また、誤り計算部１０２は、誤り検出モードにおいて、処理対象のデータフレームの各符号語の誤り検出を例えばチェンサーチ＆フォーニー法によって実行する。誤り計算部１０２は、初期化モード及び誤り検出モードを時分割で実行する。従って、誤り計算部１０２は、補正係数β_ｉの計算と各符号語の誤り検出との両方を共有のハードウェアによって実現できる。尚、誤り計算部１０２のハードウェア構成例ならびに初期化モード及び誤り検出モードにおける動作の詳細は後述される。

図３を参照すると、図２のリードソロモン復号器の各要素の動作タイミングが例示されている。後述のように、誤り計算部１０２の初期化モードにおいて最終符号語のサイズを参照する必要があるので、フレーム解析部１０１による最終符号語のサイズＭ（或いはＪ）の計算は、少なくとも誤り計算部１０２が初期化モードを終了するよりも前に終了している必要がある。但し、図３にも示されているが、後述の中間値を計算するなどの理由で、フレーム解析部１０１が最終符号語のサイズの計算を終了するよりも前に、誤り計算部１０２が初期化モードを開始することはあり得る。

また、後述のように、補正計算部１０７による最終符号語に関する補正計算において補正係数β_ｉが必要となる。従って、補正計算部１０７が最終符号語に関する補正計算を開始するよりも前に、誤り計算部１０２は初期化モードを終了する必要がある。例えば、図３に示されるように、誤り計算部１０２は、データ部において先頭に配置される先頭符号語に関する誤り検出モードを開始するよりも前に、初期化モードを終了する。尚、誤り計算部１０２は、少なくとも、データ部において最終符号語の１つ前に配置される符号語に関する誤り検出モードを開始するよりも前に初期化モードを終了する。係る制約が満たされるならば、補正係数β_ｉの計算は復号レイテンシの増加を伴わない。

ところで、実装条件、最終符号語のサイズなどの種々の要因により、先頭符号語に関する誤り検出モードが開始可能となった時点では、誤り計算部１０２が初期化モードを終了していない状況が想定される。係る状況において、誤り計算部１０２は、初期化モードを終了するまで先頭符号語に関する誤り検出モードを待機させてもよい。或いは、誤り計算部１０２は、所与の符号語に関する誤り検出モードを終了してから次の符号語に関する誤り検出モードを開始するまでの隙間期間において、初期化モードの残余の計算を実行してもよい。係る間欠動作によれば、待機に起因する復号レイテンシの増加を回避または抑制できる。

誤り計算部１０２は、初期化モードを通じて計算した補正係数β_ｉを補正係数記憶部１０３に記憶させる。補正係数記憶部１０３に記憶された補正係数β_ｉは、最終符号語に関する補正計算のために補正計算部１０７によって読み出される。

シンドローム計算部１０５は、データフレームのデータ部を入力し、このデータ部に含まれる符号語毎にシンドロームσ_ｉ（ｉ＝０，・・・，２ｔ−１）を計算する。シンドローム計算部１０５は、計算したシンドロームσ_ｉを誤り多項式係数計算部１０６へ出力する。

シンドロームσ_ｉは、生成多項式Ｇ（ｘ）の根α^ｉ（ｉ＝０，・・・２ｔ−１）を処理対象の符号語を表す多項式Ｒ（ｘ）に代入することによって計算される。即ち、シンドローム計算部１０５は、シンドロームσ_ｉを下記の数式（７）に従って計算する。尚、生成多項式Ｇ（ｘ）は、下記の数式（８）で表される。

符号語に誤りが含まれていなければ、全てのシンドロームσ_ｉは零となる。一方、符号語に誤りが含まれていれば、シンドロームσ_ｉは誤りのパターン（誤りの位置及び誤りの数値）のみに依存する非零値となる。換言すれば、シンドロームσ_ｉは符号化前のデータ（メッセージ）には依存しない。

誤り多項式係数計算部１０６は、シンドローム計算部１０５からのシンドロームσ_ｉを入力する。誤り多項式係数計算部１０６は、入力したシンドロームσ_ｉに基づいて、誤り位置多項式Λ（ｘ）の係数λ_ｉ（ｉ＝０，１，２，・・・ｔ）と誤り数値多項式Ω（ｘ）の係数ω_ｉ（ｉ＝０，１，２，・・・，ｔ−１）とを計算する。誤り多項式係数計算部１０６は、例えばＢｅｒｌｅｋａｍｐ−Ｍａｓｓｅｙアルゴリズム、ユークリッド法などの公知の計算手法によって、係数λ_ｉ及び係数ω_ｉを計算できる。誤り多項式係数計算部１０６は、計算した係数λ_ｉ及び係数ω_ｉを補正計算部１０７へ出力する。

補正計算部１０７は、誤り多項式係数計算部１０６からの係数λ_ｉ及び係数ω_ｉを入力する。補正計算部１０７は、入力した係数λ_ｉ及び係数ω_ｉに補正係数を乗算し、補正済み係数λ_ｉ’及び補正済み係数ω_ｉ’を得る。補正計算部１０７は、計算した補正済み係数λ_ｉ’及び補正済み係数ω_ｉ’を誤り計算部１０２へ出力する。

補正計算は、短縮符号の誤り検出を高速化するために実行される。具体的には、短縮符号の先頭には零シンボル群がパディングされているので、これらを無視して当該短縮符号の先頭シンボルから誤り検出を開始するために、符号語のサイズに応じた補正係数が係数λ_ｉ及び係数ω_ｉに乗算される。

前述の通り、最終符号語を除く全ての符号語は固定サイズ（Ｎシンボル）を持つ。従って、最終符号語を除く全ての符号語に関する補正係数もまた固定である。そこで、最終符号語を除く全ての符号語に関する補正係数γ_ｉ（ｉ＝０，１，２，・・・，ｔ）を予め計算し、図示しない記憶部に記憶させておくことによって、復号過程において最終符号語を除く全ての符号語に関する補正係数の計算を省略できる。また、前述の通り、最終符号語に関する補正係数β_ｉは誤り計算部１０２の初期化モードによって計算され、補正係数記憶部１０３に記憶されている。尚、β_０＝１である。

補正計算部１０７は、最終符号語を除く全ての符号語に関して、下記の数式（９）に従って係数λ_ｉ及び係数ω_ｉを補正する。補正計算部１０７は、最終符号語に関して、下記の数式（１０）に従って係数λ_ｉ及び係数ω_ｉを補正する。

尚、補正係数γ_ｉは下記の数式（１１）によって計算できる。

尚、補正計算部１０７は、補正係数γ_ｉ＝１に固定してもよい（即ち、最終符号語を除く全ての符号語に関する補正計算を省略してもよい）。補正計算を省略すると、短縮符号の先頭シンボルからではなく、パディングされた零シンボル群の先頭から誤り検出が開始する。Ｎが２^ｑに近い値であれば、補正計算の省略による復号レイテンシの増加は限定的となる。

補正計算部１０７は、図４に示されるように、（２ｔ−１）個のガロア体乗算器２０１−１，・・・，２０１−（ｔ−１），２０２−１，・・・，２０２−ｔと、ｔ個のマルチプレクサ２０３−１，・・・，２０３−ｔとを含むように実装することができる。具体的には、ガロア体乗算器２０１−ｉは、係数ω_ｉの補正計算を行う。ガロア体乗算器２０２−ｉは、係数λ_ｉの補正計算を行う。マルチプレクサ２０３−ｉ（ｉ＝１，・・・，ｔ）は、処理対象の符号語が最終符号語であるか否かに応じて補正係数β_ｉ及び補正係数γ_ｉのいずれか一方を選択し、ガロア体乗算器２０１−ｉ及びガロア体乗算器２０２−ｉに供給する。但し、係数ω_ｔは存在しない。故に、マルチプレクサ２０３−ｔは、処理対象の符号語が最終符号語であるか否かに応じて補正係数β_ｔ及び補正係数γ_ｔのいずれか一方を選択し、ガロア体乗算器２０２−ｔに供給する。

また、補正計算部１０７は、図５に示されるように、パラレル／シリアル変換部２１１と、１個のガロア体乗算器２１２と、補正係数選択部２１３と、シリアル／パラレル変換部２１４とを含むように実装することもできる。パラレル／シリアル変換部２１１は、係数ω_ｉ及び係数λ_ｉにパラレル／シリアル変換を行って、係数系列をガロア体乗算器２１２に供給する。補正係数選択部２１３は、上記係数系列と対応するように、補正係数１（＝γ_０＝β_０），γ_１，・・・，γ_ｔ，β_１・・・，β_ｔから１つずつ順次選択し、補正係数系列をガロア体乗算器２１２に供給する。ガロア体乗算器２１２は、パラレル／シリアル変換部２１１からの係数系列と補正係数選択部２１３からの補正係数系列とを順次乗算することによって、補正計算を行う。ガロア体乗算器２１２は、補正済み係数系列をシリアル／パラレル変換部２１４に供給する。シリアル／パラレル変換部２１４は、ガロア体乗算器２１２からの補正済み係数系列にシリアル／パラレル変換を行って、補正済み係数ω_ｉ’及び補正済み係数λ_ｉ’を出力する。

更に、図４及び図５を組み合わせることにより、補正計算部１０７は、２個乃至（２ｔ−２）個のガロア体乗算器を含むように実装することもできる。従って、補正計算部１０７は、１乃至（２ｔ−１）個のガロア体乗算器を含むように実装することができる。尚、補正計算部１０７を実装するために必要とされるガロア体乗算器は少なくとも１つなので、補正計算部１０７は誤り多項式係数計算部１０６に含まれる複数のガロア体乗算器の一部または全部を共有して実装されてもよい。

誤り計算部１０２は、誤り検出モードにおいて、補正計算部１０７からの補正済み係数λ_ｉ’及び補正済み係数ω_ｉ’を入力する。誤り計算部１０２は、チェンサーチによって誤り位置を計算すると共に、フォーニー法によって誤り数値を計算する。誤り計算部１０２は、誤り数値を検出する。誤り計算部１０２は、検出した誤り数値をガロア体加算器１０８へ出力する。

具体的には、チェンサーチは、Λ（α^ｉ）の値が零であるか否かによって、第Ｎ−ｉ番目（最終符号語に関しては第Ｍ−ｉ番目）のシンボルに誤りがあるか否かを判定する手法である。フォーニー法は、Ω（α^ｉ）／Λ^{（ｏｄｄ）}（α^ｉ）の値に基づいて誤り数値を計算する手法である。尚、Λ^{（ｏｄｄ）}（ｘ）は、誤り位置多項式Λ（ｘ）に含まれる奇数次の項のみからなる部分多項式である。

誤り計算部１０２は、図６に示されるように、制御部３０１と、ｔ個のマルチプレクサ３０２−１，・・・，３０２−ｔと、（２ｔ＋１）個のフリップフロップ３０３−０，・・・，３０３−（ｔ−１），３０５−０，・・・，３０５−ｔと、（２ｔ−１）個のガロア体乗算器３０４−１，・・・，３０４−（ｔ−１），３０６−１，・・・，３０６−ｔと、加算部３０７と、ガロア体乗算器３０８と、マルチプレクサ３０９と、偶数項加算部３１０と、奇数項加算部３１１と、ガロア体加算器３１２と、誤り検出部３１３と、逆元計算部３１４とを含むように実装することができる。

制御部３０１は、初期化モードにおいて、マルチプレクサ３０２−１，・・・，３０２−ｔの第１の入力端子に初期値φ_１，・・・，φ_ｔを供給すると共に、マルチプレクサ３０２−１，・・・，３０２−ｔに第１の入力端子を選択させるための選択信号を供給する。初期値φ_ｉは、下記の数式（１２）で表される。尚、数式（１２）において、Ｐは初期値を決定するためのパラメータである。

また、制御部３０１は、誤り検出モードにおいて、マルチプレクサ３０２−１，・・・，３０２−ｔに第２の入力端子を選択させるための選択信号を供給する。また、制御部３０１は、フリップフロップ３０５−０，・・・，３０５−ｔに第１ロード信号を供給し、フリップフロップ３０３−０，・・・，３０３−（ｔ−１）に第２ロード信号を供給する。

マルチプレクサ３０２−１，・・・，３０２−ｔは、第１の入力端子において制御部３０１からの初期値φ_１，・・・，φ_ｔを入力し、第２の入力端子において補正計算部１０７からの補正済み係数λ_１’，・・・，λ_ｔ’を入力する。マルチプレクサ３０２−１，・・・，３０２−ｔは、初期化モードにおいて、制御部３０１からの選択信号に従って第１の入力端子を選択し、初期値φ_１，・・・，φ_ｔを出力する。マルチプレクサ３０２−１，・・・，３０２−ｔは、誤り検出モードにおいて、制御部３０１からの選択信号に従って第２の入力端子を選択し、補正済み係数λ_１’，・・・，λ_ｔ’を出力する。

フリップフロップ３０３−０は、誤り検出モードにおいて、補正計算部１０７からの補正済み係数ω_０’を加算部３０７へ供給する。フリップフロップ３０３−１，・・・，３０３−（ｔ−１）及びガロア体乗算器３０４−１，・・・，３０４−（ｔ−１）は、誤り検出モードにおいて、補正計算部１０７からの補正済み係数ω_１’，・・・，ω_ｔ−１’に乗算因子α^１，・・・，α^ｔ−１を乗算し、乗算結果を加算部３０７へ供給する。

フリップフロップ３０５−０は、誤り検出モードにおいて、補正計算部１０７からの補正済み係数λ_０’を偶数項加算部３１０へ供給する。フリップフロップ３０５−１，・・・，３０５−ｔ及びガロア体乗算器３０６−１，・・・，３０６−ｔは、誤り検出モードにおいて、補正計算部１０７からの補正済み係数λ_１’，・・・，λ_ｔ’に乗算因子α^１，・・・，α^ｔを乗算し、乗算結果を偶数項加算部３１０及び奇数項加算部３１１のうちの一方へ供給する。

また、フリップフロップ３０５−１，・・・，３０５−ｔ及びガロア体乗算器３０６−１，・・・，３０６−ｔは、初期化モードにおいて、マルチプレクサ３０２−１，・・・，３０２−ｔからの初期値φ_１，・・・，φ_ｔに乗算因子α^１，・・・，α^ｔをｍｏｄ（Ｐ−Ｍ，２^ｑ）サイクルだけ反復して乗算し、補正係数β_１，・・・，β_ｔを計算する。即ち、補正係数β_ｉ＝α^−ｉＭ（ｉ＝１，・・・，ｔ）である。フリップフロップ３０５−１，・・・，３０５−ｔは、計算された補正係数β_１，・・・，β_ｔを補正係数記憶部１０３へ供給する。

加算部３０７は、誤り検出モードにおいて、フリップフロップ３０３−０，・・・，３０３−（ｔ−１）からの信号を入力し、これらを加算して誤り数値多項式を形成する。偶数項加算部３１０は、誤り検出モードにおいて、フリップフロップ３０５−０，・・・，３０５−ｔからの信号のうち誤り位置多項式の偶数項に相当するものを入力し、これらを加算する。奇数項加算部３１１は、誤り検出モードにおいて、フリップフロップ３０５−１，・・・，３０５−ｔからの信号のうち誤り位置多項式の奇数項に相当するものを入力し、これらを加算する。

ガロア体加算器３１２は、偶数項加算部３１０及び奇数項加算部３１１からの信号を加算し、誤り位置多項式を計算する。誤り検出部３１３は、ガロア体加算器３１２から誤り位置多項式を入力し、誤り検出を行う。逆元計算部３１４は、奇数項加算部３１１から誤り位置多項式の奇数項部分を入力し、この逆元を計算する。逆元計算部３１４は、計算した誤り位置多項式の奇数項部分の逆元をガロア体乗算器３０８に与える。ガロア体乗算器３０８は、加算部３０７からの誤り数値多項式と、逆元計算部３１４からの誤り位置多項式の奇数項部分の逆元とを乗算し、乗算結果（即ち、Ω（α^ｉ）／Λ^{（ｏｄｄ）}（α^ｉ））をマルチプレクサ３０９の第１の入力端子に供給する。マルチプレクサ３０９は、第２の入力端子において零を入力する。マルチプレクサ３０９は、誤り検出部３１３からの誤り検出結果に応じて、零及びガロア体乗算器３０８からの信号のいずれか一方を選択し、誤り数値として出力する。

図６の誤り計算部１０２によれば、最終符号語に関する補正係数の計算が、チェンサーチのためのフリップフロップ３０５−１，・・・，３０５−ｔ及びガロア体乗算器３０６−１，・・・，３０６−ｔを共有して実現される。

また、誤り計算部１０２は、図７に示されるように、制御部３２１と、ｔ個のマルチプレクサ３２２−１，・・・，３２２−ｔと、（２ｔ＋１）個のフリップフロップ３２３−０，・・・，３２３−（ｔ−１），３２５−０，・・・，３２５−ｔと、（２ｔ−１）個のガロア体乗算器３２４−１，・・・，３２４−（ｔ−１），３２６−１，・・・，３２６−ｔと、加算部３０７と、ガロア体乗算器３０８と、マルチプレクサ３０９と、偶数項加算部３１０と、奇数項加算部３１１と、ガロア体加算器３１２と、誤り検出部３１３と、逆元計算部３１４とを含むように実装することもできる。

尚、誤り検出モードにおいて、フリップフロップ３２３−０，・・・，３２３−（ｔ−１），３２５−０，・・・，３２５−ｔ及びガロア体乗算器３２４−１，・・・，３２４−（ｔ−１），３２６−１，・・・，３２６−ｔの動作は、フリップフロップ３０３−０，・・・，３０３−（ｔ−１），３０５−０，・・・，３０５−ｔ及びガロア体乗算器３０４−１，・・・，３０４−（ｔ−１），３０６−１，・・・，３０６−ｔのものと同じである。

制御部３２１は、初期化モードにおいて、マルチプレクサ３２２−１，・・・，３２２−ｔの第１の入力端子に初期値φ_１，・・・，φ_ｔを供給すると共に、マルチプレクサ３２２−１，・・・，３２２−ｔに第１の入力端子を選択させるための選択信号を供給する。また、制御部３２１は、誤り検出モードにおいて、マルチプレクサ３２２−１，・・・，３２２−ｔに第２の入力端子を選択させるための選択信号を供給する。また、制御部３２１は、フリップフロップ３２５−０，・・・，３２５−ｔに第１ロード信号を供給し、フリップフロップ３２６−０，・・・，３２６−（ｔ−１）に第２ロード信号を供給する。

マルチプレクサ３２２−１，・・・，３２２−（ｔ−１）は、第１の入力端子において制御部３２１からの初期値φ_１，・・・，φ_ｔ−１を入力し、第２の入力端子において補正計算部１０７からの補正済み係数ω_１’，・・・，ω_ｔ−１’を入力する。マルチプレクサ３２２−１，・・・，３２２−（ｔ−１）は、初期化モードにおいて、制御部３２１からの選択信号に従って第１の入力端子を選択し、初期値φ_１，・・・，φ_ｔ−１を出力する。マルチプレクサ３２２−１，・・・，３２２−（ｔ−１）は、誤り検出モードにおいて、制御部３２１からの選択信号に従って第２の入力端子を選択し、補正済み係数ω_１’，・・・，ω_ｔ−１’を出力する。

マルチプレクサ３２２−ｔは、第１の入力端子において制御部３２１からの初期値φ_ｔを入力し、第２の入力端子において補正計算部１０７からの補正済み係数λ_ｔ’を入力する。マルチプレクサ３２２−ｔは、初期化モードにおいて、制御部３２１からの選択信号に従って第１の入力端子を選択し、初期値φ_ｔを出力する。マルチプレクサ３２２−ｔは、誤り検出モードにおいて、制御部３２１からの選択信号に従って第２の入力端子を選択し、補正済み係数λ_ｔ’を出力する。

フリップフロップ３２３−１，・・・，３２３−（ｔ−１）及びガロア体乗算器３２４−１，・・・，３２４−（ｔ−１）は、初期化モードにおいて、マルチプレクサ３２２−１，・・・，３２２−（ｔ−１）からの初期値φ_１，・・・，φ_ｔ−１に乗算因子α^１，・・・，α^ｔ−１をｍｏｄ（Ｐ−Ｍ，２^ｑ）サイクルだけ反復して乗算し、補正係数β_１，・・・，β_ｔ−１を計算する。フリップフロップ３２３−１，・・・，３２３−（ｔ−１）は、計算された補正係数β_１，・・・，β_ｔ−１を補正係数記憶部１０３へ供給する。また、フリップフロップ３２５−ｔ及びガロア体乗算器３２６−ｔは、初期化モードにおいて、マルチプレクサ３２２−ｔからの初期値φ_ｔに乗算因子α^ｔをｍｏｄ（Ｐ−Ｍ，２^ｑ）サイクルだけ反復して乗算し、補正係数β_ｔを計算する。フリップフロップ３２５−ｔは、計算された補正係数β_ｔを補正係数記憶部１０３へ供給する。

図７の誤り計算部１０２によれば、最終符号語に関する補正係数の計算が、フォーニー法のためのフリップフロップ３２３−１，・・・，３２３−（ｔ−１）及びガロア体乗算器３２４−１，・・・，３２４−（ｔ−１）と、チェンサーチのためのフリップフロップ３２５−ｔ及びガロア体乗算器３２６−ｔとを共有して実現される。

尚、図６及び図７の例によれば、誤り計算部１０２は、初期化モードのための全てのハードウェア構成を誤り検出モードのためのものと共有している。しかしながら、誤り計算部１０２は、初期化モードのための一部のハードウェア構成を誤り検出モードのためのものと共有し、残余のハードウェア構成を別途設けてもよい。

前述の通り、初期化モードにおける補正係数の計算は、ｍｏｄ（Ｐ−Ｍ，２^ｑ）サイクルを必要とする。例えば、Ｐ＝０（即ち、φ_ｉ＝１）であって、かつ、最終符号語のサイズＭ＝１であれば、補正係数β_ｉを計算するために２^ｑ−１サイクルが必要となる。以降、補正係数β_ｉの計算に伴う復号レイテンシの増加を回避または抑制するための手法が述べられる。

パラメータＰに対して複数の異なる値を与えることによって、複数の異なる初期値φ_ｉ（＝α^−ｉＰ）を用意することができる。誤り計算部１０２は、係る複数の異なる初期値を最終符号語のサイズに応じて切り替えて使用することによって、補正係数β_ｉを計算するために必要なサイクル数を削減できる。例えば、誤り計算部１０２は、パラメータＰに０，２^ｑ−１を与えて第１の初期値及び第２の初期値を用意する。そして、誤り計算部１０２は、最終符号語のサイズＭが閾値２^ｑ−１以下であれば第２の初期値を使用し、最終符号語のサイズＭが閾値２^ｑ−１を超えるならば第１の初期値を使用する。係る動作によれば、補正係数β_ｉを計算するために必要なサイクル数を最大で２^ｑ−１に抑制できる。

また、誤り計算部１０２は、フレーム解析部１０１が最終符号語のサイズＭの計算を終了するよりも前に補正係数β_ｉの計算を開始することによって、補正係数β_ｉの中間値を予め計算してもよい。例えば、誤り計算部１０２は、最終符号語のサイズＭが計算される前に、初期値φ_ｉ＝１（即ち、Ｐ＝０）として２^ｑ−１サイクル分の計算を終了させておくとする。誤り計算部１０２は、最終符号語のサイズＭが閾値２^ｑ−１以下であれば中間値を使用して補正係数β_ｉの計算を続行し、最終符号語のサイズＭが閾値２^ｑ−１を超えるならば再び初期値φ_ｉ＝１から補正係数β_ｉの計算を開始すればよい。係る動作によれば、最終符号語のサイズＭの計算が終了してから補正係数β_ｉの計算が終了するまでに必要なサイクル数を最大で２^ｑ−１に抑制できる。

ガロア体加算器１０８は、データ記憶部１０４から処理対象の符号語と、誤り計算部１０２からの誤り数値とを入力する。ガロア体加算器１０８は、処理対象の符号語と誤り数値とを加算（即ち、排他的論理和）することによって誤りを訂正し、出力データを得る。

以上説明したように、第１の実施形態に係るリードソロモン復号器は、最終符号語に関する補正係数の計算を最終符号語の１つ前の符号語の誤り検出が開始するよりも前に終了する。従って、本実施形態に係るリードソロモン復号器によれば、最終符号語に関する補正係数の計算に伴う復号レイテンシの増加が回避される（或いは、抑制される）。また、本実施形態に係るリードソロモン復号器は、誤り計算部のハードウェアを時分割で使用して最終符号語に関する補正係数の計算及び各符号語の誤り検出を実行する。従って、本実施形態に係るリードソロモン復号器によれば、最終符号語に関する補正計算のために専用のハードウェアを設ける必要がないので、回路規模及び消費電力の増大を抑制できる。

第１の実施形態に係るリードソロモン復号器は、例えば受信装置に組み込まれ得る。係る受信装置は、図８に示されるように、無線受信部４０２、Ａ／Ｄ変換部４０３、データ復調部４０４、リードソロモン復号部４０５及びＭＡＣ（Ｍｅｄｉａ Ａｃｃｅｓｓ Ｃｏｎｔｒｏｌ）層処理部４０６を含む。図８の受信装置は、アンテナ４０１を介して無線信号を受信する。

無線受信部４０２は、アンテナ４０１によって受信された無線信号をベースバンドのアナログ信号へと変換する。Ａ／Ｄ変換部４０３は、ベースバンドのアナログ信号をデジタル信号へと変換する。データ復調部４０４は、Ａ／Ｄ変換部４０３からのデジタル信号に等化処理、周波数オフセット処理など（即ち、通信路及びアナログ回路の歪補正処理）を行って、ＢＰＳＫ（Ｂｉｎａｒｙ Ｐｈａｓｅ Ｓｈｉｆｔ Ｋｅｙｉｎｇ）、ＱＰＳＫ（Ｑｕａｄｒａｔｕｒｅ Ｐｈａｓｅ Ｓｈｉｆｔ Ｋｅｙｉｎｇ）などの変調信号点を復元し、復元した変調信号点に対応するビット値を推定する。

リードソロモン復号部４０５として、第１の実施形態に係るリードソロモン復号器が組み込まれる。リードソロモン復号部４０５は、データ復調部４０４からのビット値（前述のデータフレームに相当する）に対して前述の誤り訂正復号を行い、誤り訂正済みの受信データを得る。リードソロモン復号部４０５は、誤り訂正済みの受信データを例えばＭＡＣ層処理部４０６に供給する。ＭＡＣ層処理部４０６は、リードソロモン復号部４０５から誤り訂正済みの受信データを入力して所与のＭＡＣ処理を行い、これを上位レイヤへと供給する。

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

１０１・・・フレーム解析部
１０２・・・誤り計算部
１０３・・・補正係数記憶部
１０４・・・データ記憶部
１０５・・・シンドローム計算部
１０６・・・誤り多項式係数計算部
１０７・・・補正計算部
１０８・・・ガロア体加算器
２０１，２０２，２１２・・・ガロア体乗算器
２０３・・・マルチプレクサ
２１１・・・パラレル／シリアル変換部
２１３・・・補正係数選択部
２１４・・・シリアル／パラレル変換部
３０１，３２１・・・制御部
３０２，３０９，３２２・・・マルチプレクサ
３０３，３０５，３２３，３２５・・・フリップフロップ
３０４，３０６，３０８，３２４，３２６・・・ガロア体乗算器
３０７・・・加算部
３１０・・・偶数項加算部
３１１・・・奇数項加算部
３１２・・・ガロア体加算器
３１３・・・誤り検出部
３１４・・・逆元計算部
４０１・・・アンテナ
４０２・・・無線受信部
４０３・・・Ａ／Ｄ変換部
４０４・・・データ復調部
４０５・・・リードソロモン復号部
４０６・・・ＭＡＣ層処理部

Claims (5)

1. 少なくとも２つのリードソロモン符号語を含むデータ部と前記データ部のサイズを示す情報を含むヘッダー部とを含むデータフレームのうち前記ヘッダー部を解析し、前記データ部において末尾に配置される最終符号語のサイズを計算する解析部と、
   前記データ部において前記最終符号語の１つ前に配置される符号語に関する誤り検出が開始するよりも前に、前記リードソロモン符号語のベースサイズと前記最終符号語のサイズとの差分に応じて前記最終符号語の誤り位置多項式の係数及び誤り数値多項式の係数を補正するための補正係数を前記最終符号語のサイズに基づいて計算する係数計算部と、
   少なくとも１つの乗算器を用いて、チェンサーチによる誤り位置計算及びフォーニー法による誤り数値計算を行う誤り計算部と
   を具備し、
   前記係数計算部及び前記誤り計算部は、前記少なくとも１つの乗算器を共有する、
   リードソロモン復号器。
2. 前記係数計算部は、前記データ部において先頭に配置される符号語の誤り検出が開始するよりも前に、前記補正係数を前記最終符号語のサイズに基づいて計算する、請求項１のリードソロモン復号器。
3. 前記係数計算部は、前記解析部が前記最終符号語のサイズの計算を終了するよりも前に初期値に対して乗算因子を第２の回数だけ反復して乗算することによって中間値を計算し、前記解析部が前記最終符号語のサイズの計算を終了してから、（Ａ）前記最終符号語のサイズが前記第２の回数に対応する閾値以下であれば前記中間値に対して前記乗算因子を前記最終符号語のサイズに応じた第１の回数と前記第２の回数との差分だけ反復して乗算することによって前記補正係数を計算し、（Ｂ）前記最終符号語のサイズが前記閾値を超えるならば前記初期値に対して前記乗算因子を前記第１の回数だけ反復して乗算することによって前記補正係数を計算する、請求項１のリードソロモン復号器。
4. 前記係数計算部は、前記最終符号語のサイズが閾値を超えるならば第１の初期値に対して乗算因子を前記最終符号語のサイズに応じた第１の回数だけ反復して乗算することによって前記補正係数を計算し、前記最終符号語のサイズが前記閾値以下であれば第２の初期値に対して前記乗算因子を前記最終符号語のサイズに応じた第２の回数だけ反復して乗算することによって前記補正係数を計算する、請求項１のリードソロモン復号器。
5. 前記データフレームを受信する無線受信部と、
   請求項１のリードソロモン復号器と
   を具備する、受信装置。

Images