JP4041219B2 - Maximum likelihood decoder - Google Patents

Description

で与えられる組織符号として与えられると仮定する。
【０００６】
このような構成の最尤復号器では、プロセッサ７２は、図１４に示すように、上述した受信系列に含まれ、かつ個別に情報記号と検査記号とを含む受信語（誤り訂正対象符号）ｘが蓄積されるべき記憶領域の集合からなる受信語レジスタ８１と、図１５に示すように、受信語ｘに正規に含まれ得る情報記号と検査記号との全ての対からなる符号語Ｃが予め登録された符号語テーブル８２とを主記憶の特定の記憶領域に有する。
【０００７】
プロセッサ７２は、受信語レジスタ８１の領域管理を行い、かつ入力インタフェース部７１を介して受信系列として与えられる受信語をその領域管理の下で受信語レジスタ８１の空いている領域に順次格納する。
さらに、プロセッサ７２は、このようにして受信語レジスタ８１に格納された個々の受信語について、符号語テーブル８２に予め登録された全ての符号語との距離を算出し、これらの語の内、算出された距離が最小である語を最尤解とすると共に、その最尤解を出力インタフェース部７３を介して順次復号系列として出力する。
【０００８】
すなわち、受信語ｘに含まれる情報記号は、その受信語ｘに付帯するビット誤りの程度が上述した組織符号に固有の誤り訂正能力を超えない限り、この組織符号の性質に何ら関係がない単純な演算手順に基づいて、伝送、あるいは書き込みや読み出しの過程で生じたビット誤りが訂正されると共に、正規の情報記号として得られる。
【０００９】
【発明が解決しようとする課題】
ところで、上述した従来例では、個々の受信語ｘに対してプロセッサ７２が距離を算出すべき回数Ｎと算出された距離を比較すべき回数Ｎとは、共に情報記号の語長（ビット数）Ｌに対して
Ｎ＝２^L
の式で示されるように、大きな値となる。
【００１０】
したがって、実際の復号化処理については、例えば、組織符号として線形符号である巡回符号が適用された場合における「受信語ｘを示す受信多項式が生成多項式で除算し切れるか否かの判別」のように、符号語の性質に適応した演算が適用されることによって達成されなければならなかった。
さらに、このような演算の手順には、例えば、巡回符号としてＢＣＨ符号が適用された場合には、Peterson法やBerlekamp-Massey法の適用が可能である。
【００１１】
しかし、これらの演算の手順は、適用されるべき組織符号が線形符号であっても、例えば、Golay 符号のような異なる符号に対しては適応しない。
したがって、性質が異なる複数の符号が適用されるべき装置やシステムに適用される復号器については、これらの符号の全てに適応した演算の手順が組み込まれなければならず、ソフトウエアの規模が大きくなる場合が高かった。
【００１２】
本発明は、多様な組織符号に柔軟に適応し、かつ処理量が大幅に削減されると共に、確度高く復号化が行われる最尤復号器を提供することを目的とする。
【００１３】
【課題を解決するための手段】
図１は、本発明に係る第１、４、７の技術の原理ブロック図である。
【００１４】
本発明に係る第１の技術は、組織符号として与えられた受信語から情報記号を抽出する情報抽出手段１１と、情報抽出手段１１によって抽出された情報記号の真の値であり得る全ての予測情報記号を求め、これらの予測情報記号について、個別に組織符号に適応した検査記号との対からなる推定受信語を求める推定手段１２と、推定手段１２によって求められた推定受信語の内、組織符号として与えられた受信語との距離が最小である推定受信語の一部もしくは全てを復号結果として出力する受信語判定手段１３とを備えたことを特徴とする。
【００１５】
図２は、本発明に係る第２、５、７の技術の原理ブロック図である。
本発明に係る第２の技術は、組織符号として与えられた受信語から情報記号を抽出する情報抽出手段１１と、受信語に重畳され得る誤り系列の非零の元を含む部分系列である全ての誤りパターンについて、個別に組織符号に適応した検査記号との対からなる仮想誤り系列を与える仮想誤り系列供給手段２１と、情報抽出手段１１によって抽出された情報記号に対して組織符号に適応した検査記号を生成し、これらの情報記号および検査記号からなる仮想正規受信語を生成する仮想正規受信語生成手段２２と、仮想正規受信語生成手段２２によって生成された仮想正規受信語と、仮想誤り系列供給手段２１によって与えられる個々の仮想誤り系列との和をとることによって推定受信語を求める推定手段２３と、推定手段２３によって求められた推定受信語の内、組織符号として与えられた受信語との距離が最小である推定受信語の一部もしくは全てを復号結果として出力する受信語判定手段２４とを備えたことを特徴とする。
【００１６】
図３は、本発明に係る第３、６、７の技術の原理ブロック図である。
本発明に係る第３の技術は、組織符号として与えられた受信語から情報記号と検査記号とを個別に抽出する記号抽出手段３１と、受信語に重畳され得る誤り系列の非零の元を含む部分系列である全ての誤りパターンについて、個別に組織符号に適応した仮想検査記号を与える仮想検査記号供給手段３２と、情報抽出手段３１によって抽出された情報記号に対して組織符号に適応した仮想正規検査記号を生成する仮想正規検査記号生成手段３３と、仮想正規検査記号生成手段３３によって生成された仮想正規検査記号と、仮想検査記号供給手段３２によって与えられる個々の検査記号との和をとることによって推定検査記号を求める推定手段３４と、推定手段３４によって求められた推定検査記号の内、記号抽出手段３１によって抽出された検査記号との距離が最小である推定検査記号に対して組織符号に適応する誤りパターンと、その記号抽出手段３１によって抽出された情報記号との和との双方あるいは何れか一方を復号結果として出力する受信語判定手段３５とを備えたことを特徴とする。
【００１７】
本発明に係る第４の技術は、本発明に係る第１の技術の最尤復号器において、推定手段１２は、情報抽出手段１１によって抽出された情報記号の真の値であり得る全ての予測情報記号を組織符号の誤り訂正能力の範囲で求めることを特徴とする。
本発明に係る第５の技術は、本発明に係る第２の技術の最尤復号器において、仮想誤り系列供給手段２１は、組織符号の誤り訂正能力の範囲で訂正が可能である誤り系列の非零の元を含む部分系列である全ての誤りパターンについて、個別にその組織符号に適応した検査記号との対からなる仮想誤り系列を与えることを特徴とする。
【００１８】
本発明に係る第６の技術は、本発明に係る第３の技術の最尤復号器において、仮想検査記号供給手段３２は、組織符号の誤り訂正能力の範囲で訂正が可能である誤り系列の非零の元を含む部分系列である全ての誤りパターンについて、個別にその組織符号の方式に適応した仮想検査記号を与えることを特徴とする。
本発明に係る第７の技術は、本発明に係る第１ないし第６の技術の何れか１の技術の最尤復号器において、最小距離が既知である符号が組織符号として適用され、受信語判定手段１３、２４、３５は、距離が最小距離以下か否かを判別し、その判別の結果が真であるときに、後続する距離の算出と、その算出された距離にかかわる判別との何れかを取り止め、かつ復号結果を確定して出力することを特徴とする。
【００１９】
本発明に係る第１の技術にかかわる最尤復号器では、情報抽出手段１１は組織符号として与えられた受信語から情報記号を抽出し、かつ推定手段１２はその情報記号の真の値であり得る全ての予測情報記号を求め、これらの予測情報記号について、個別にこの組織符号に適応した検査記号との対からなる推定受信語を求める。
【００２０】
これらの推定受信語については、上述した予測情報記号と受信語に含まれる情報記号との相違がその情報記号に実際に伴う誤りに等しい場合には、この予測情報記号を含み、かつ推定手段１２によって求められた推定受信語の何れかは誤りが何ら伴わない受信語として与えられるべき真の符号に該当する。
受信語判定手段１３は、推定手段１２によって求められた推定受信語の内、組織符号として与えられた受信語との距離が最小である推定受信語の一部もしくは全てを復号結果として出力する。
【００２１】
すなわち、復号結果を得るために上述した距離が個別に求められ、かつ比較されるべき推定受信語の数は、適用された組織符号として与えられ得る全ての符号語の数に比べて確実に小さな値となるので、最尤復号化に要する処理量の削減がはかられる。
本発明に係る第２の技術にかかわる最尤復号器では、情報抽出手段１１は、組織符号として与えられた受信語から情報記号を抽出する。仮想誤り系列供給手段２１は、その受信語に重畳され得る誤り系列の非零の元を含む部分系列である全ての誤りパターンについて、個別にこの組織符号に適応した検査記号との対からなる仮想誤り系列を与える。仮想正規受信語生成手段２２は、情報抽出手段１１によって抽出された情報記号に対して組織符号に適応した検査記号を生成し、これらの情報記号および検査記号からなる仮想正規受信語を生成する。推定手段２３は、このようにして生成された仮想正規受信語と、仮想誤り系列供給手段２１が与える個々の仮想誤り系列との和をとることによって推定受信語を求める。
【００２２】
これらの推定受信語については、上述した仮想正規受信語と受信語に伴い得る誤りを示す誤りパターンとの和に該当し、その誤りパターンは仮想誤り系列供給手段２１によって与えられる仮想誤り系列に相当する。
すなわち、推定手段２３によって与えられる推定受信語の何れかは誤りが何ら伴わない受信語として与えられるべき真の符号に該当するので、受信語判定手段２４は、これらの推定受信語の内、組織符号として与えられた受信語との距離が最小である推定受信語の一部もしくは全てを復号結果として出力することができる。
【００２３】
また、仮想正規情報生成手段２２は情報抽出手段１１によって抽出された単一の情報記号のみに適応した検査記号を生成するので、このような検査記号が全ての推定受信語について個別に生成されなければならない本発明に係る第１の技術の最尤復号器に比べて、処理量の削減が可能となる。
本発明に係る第３の技術にかかわる最尤復号器では、記号抽出手段３１は組織符号として与えられた受信語から情報記号と検査記号とを個別に抽出し、かつ仮想検査記号供給手段３２はその受信語に重畳され得る誤り系列の非零の元を含む部分系列である全ての誤りパターンについて、個別に組織符号に適応した仮想検査記号を与える。仮想正規検査記号生成手段３３は情報抽出手段３１によって抽出された情報記号に対して組織符号に適応した仮想正規検査記号を生成し、かつ推定手段３４はその仮想正規検査記号と、仮想検査記号供給手段３２によって与えられる個々の検査記号との和をとることによって推定検査記号を求める。
【００２４】
受信語判定手段３５は、これらの推定検査記号の内、記号抽出手段３１によって抽出された検査記号との距離を求める。
ところで、このような距離は、何らかの誤りが伴い得る受信語に実際に含まれる検査記号と、その受信語に含まれる情報記号に対して正規である検査記号に上述した誤りパターンで示される誤りが伴う検査記号との間における第一の距離と、この誤りパターンのみの関数として与えられる第二の距離との和に等しい。
【００２５】
しかし、その第二の距離が一定であり、あるいは一定でなくても要求される最尤復号化の精度が確保される程度に小さな値となる組織符号の採用が可能であるので、受信語判定手段３５は、上述したように求めた距離が最小である推定検査記号に対して適応する誤りパターンと、その記号抽出手段３１によって抽出された情報記号との和との双方あるいは何れか一方を復号結果として出力することによって、最尤復号化を達成することができる。
【００２６】
また、上述した距離を求め、かつ比較する処理が受信語に比べて語長が短い検査記号のみについて行われるので、本発明にかかわる最尤復号器は、復号化の確度が低下することなく本発明に係る第１、２の技術の最尤復号器より少ない処理量で実現される。
本発明に係る第４の技術にかかわる最尤復号器では、本発明に係る第１の技術の最尤復号器において、推定手段１２は、情報抽出手段１１によって抽出された情報記号の真の値であり得る全ての予測情報記号を組織符号の誤り訂正能力の範囲で求める。
【００２７】
すなわち、誤り訂正が不可能であるにもかかわらず、受信語判定手段１３が無用に距離を求めることが回避されるので、本発明に係る第１の技術の最尤復号器に比べて、最尤復号に要する処理の処理量が削減される。
本発明に係る第５の技術にかかわる最尤復号器では、本発明に係る第２の技術の最尤復号器において、仮想誤り系列供給手段２１は、組織符号の誤り訂正能力の範囲で訂正が可能である誤り系列の非零の元を含む部分系列である全ての誤りパターンについて、個別にこの組織符号に適応した検査記号との対からなる仮想誤り系列を与える。
【００２８】
すなわち、誤り訂正が不可能であるにもかかわらず、受信語判定手段２４が無用に距離を求めることが回避されるので、本発明に係る第２の技術の最尤復号器に比べて、最尤復号に要する処理の処理量が削減される。
本発明に係る第６の技術にかかわる最尤復号器では、本発明に係る第３の技術の最尤復号器において、仮想検査記号供給手段３２は、組織符号の誤り訂正能力の範囲で訂正が可能である誤り系列の非零の元を含む部分系列である全ての誤りパターンについて、個別にその組織符号に適応した仮想検査記号を与える。
【００２９】
すなわち、誤り訂正が不可能であるにもかかわらず、受信語判定手段３５が無用に距離を求めることが回避されるので、本発明に係る第３の技術の最尤復号器に比べて、最尤復号に要する処理の処理量が削減される。
本発明に係る第７の技術にかかわる最尤復号器では、本発明に係る第１ないし第６の技術の何れか１の技術の最尤復号器において、組織符号として最小距離が既知である符号が適用されると共に、受信語判定手段１３、２４、３５は、距離がその最小距離以下であるか否かを判別し、その判別の結果が真であるときに、後続する距離の算出と、その算出された距離にかかわる判別との何れかを取り止め、かつ復号結果を確定して出力する。
【００３０】
すなわち、符号ブロック毎に行われるべき最尤復号化の処理が上述した最小距離を基準として的確に打ち切られるので、本発明に係る第１ないし第６の技術より処理の効率化がはかられる。
【００３１】
【発明の実施の形態】
以下、図面に基づいて本発明の実施形態について詳細に説明する。
【００３２】
図４は、本発明に係る第１〜７の技術に対応した実施形態を示す図である。
図において、図１３に示すものと機能および構成が同じものについては、同じ符号を付与して示し、ここではその説明を省略する。
本実施形態と図１３に示す従来例との構成の相違点は、プロセッサ７２に代えてプロセッサ４１が備えられた点にある。
【００３３】
なお、本実施形態と図１に示すブロック図との対応関係については、入力インタフェース部７１およびプロセッサ４１は情報抽出手段１１に対応し、プロセッサ４１は推定手段１２に対応し、プロセッサ４１および出力インタフェース部７４は受信語判定手段１３に対応する。
図５は、本発明に係る第１、４、７の技術に対応した本実施形態の動作フローチャートである。
【００３４】
図６は、本発明に係る第１、４、７の技術に対応した本実施形態の動作を説明する図である。
以下、図４〜図６および図１４を参照して本発明に係る第１、４の技術に対応した本実施形態の動作を説明する。
プロセッサ４１の主記憶の特定の記憶領域には、受信語ｘに含まれる情報記号に組織符号の誤り訂正能力の範囲でビット誤りが生じた場合に生成され得る全ての推定情報記号について、図７に示すように、個別に正規の検査記号である推定検査記号との対として定義される推定受信語が格納されるべき推定受信語レジスタ５１が配置される。
【００３５】
また、プロセッサ４１は、受信語レジスタ８１の領域管理を行い、その領域管理の下でこの受信語レジスタ８１の空いている領域に、入力インタフェース部７１を介して受信系列として与えられた受信語ｘを順次格納する。
さらに、プロセッサ４１は、このようにして受信語レジスタ８１に格納された個々の受信語ｘについて、以下の(1)〜(4)に示す一連の処理を行う。
【００３６】
(1) この受信語ｘに含まれる情報記号に重畳され得る誤り系列の内、組織符号の誤り訂正能力の下で誤り訂正が可能である全ての誤り系列について、
▲１▼ 受信語ｘに含まれる情報記号と該当する誤り系列との和をとる（例えば、組織符号の誤り訂正能力が１ビットである場合には、その情報記号を構成する個々のビットの論理値を１ビットずつ反転させる）ことによって推定情報記号を求め（図５(1))、
▲２▼ その推定情報記号に適応した正規の検査記号である推定検査記号を求める（図５(2))。
【００３７】
(2) 個々の誤り系列に対してこのようにして求められた推定情報記号と推定検査記号とからなる推定受信語を推定受信語レジスタ５１に蓄積する（図５(3 )、図６(1))。
(3) これらの推定受信語の全てについて、受信語レジスタ８１に格納された受信語ｘとの距離を算出し（図５(4)、図６(2))、
(4) これらの推定受信語の内、算出された距離が最小である推定受信語を最尤解とすると共に、出力インタフェース部７３を介してその最尤解を復号系列として順次出力する（図５(5)、図６(3))。
【００３８】
ところで、推定受信語レジスタ５１に格納されるべき推定受信語については、
(a) 受信語ｘの情報源（送信元）によってその受信語ｘで示される真の符号（以下、単に「真の符号」という。）に含まれるべき情報記号ｘ_i と検査記号Ｐ(ｘ_i) とに対して、その真の符号が（ｘ_i、Ｐ(ｘ_i)) で表され、
(b) これらの情報記号ｘ_i と検査記号Ｐ(ｘ_i) とにそれぞれ生じた誤りｅ_i 、ｅ_P に対して、この真の符号の全体に生じた誤りが（ｅ_i、ｅ_P）で示され、
(c) その情報記号ｘ_i に生じ得る誤りの態様を示す誤りパターンｅⁿ に対して真の符号の全体に生じる誤りの態様を示す誤りパターンが(ｅⁿ、Ｐ(ｅⁿ))で表されると共に、
(d) 受信語ｘが
【数２】

で表される場合には、上述した推定情報記号ｘ_i ⁿは、
【数３】

の式で表される。
【００３９】
また、その推定情報記号ｘ_i ⁿを含む推定受信語は、（ｘ_i ⁿ、Ｐ(ｘ_i ⁿ)）で表記され、具体的には、
【数４】

の式で示される。
しかし、情報記号ｘ_i に実際に生じた誤りｅ_i が上述した誤りパターンｅⁿ に等しい場合には、一般に、
【数５】

の式で示されるビット列に含まれる全てのビットの論理値は「０」となる。
【００４０】
したがって、このような場合には、上式(1) で示される推定受信語は既述の真の符号（ｘ_i、Ｐ(ｘ_i)）に相当し、かつ既述の手順(4) によれば、従来例と同様の最尤解が確度高く得られる。
また、受信語レジスタ８１に格納された受信語ｘに対する距離の算出と、これらの距離の比較とが行われるべき推定受信語の数Ｎは、その受信語ｘに含まれる情報記号に組織符号の誤り訂正能力を超えない程度のビット誤りが生じた場合に限って得られる受信語の数に等しいので、従来例において、符号語テーブル８２に予め登録された推定符号語の数（情報記号ｘ_i の語長Ｌ、上述した誤り訂正能力の範囲で誤り訂正が可能である最大のビット数ｍに対して
【数６】

の式で示される。）に比べて小さな値となる。
【００４１】
このように本実施形態によれば、所要する処理量が大幅に削減されるので、高速の演算を可能とするデバイスが適用され、あるいは並列演算を実現するためにハードウエアの規模が大きくなることなく、従来例に比べて多様な組織符号（非線形符号であってもよい。）に柔軟に適応した最尤復号化が効率的に実現される。
【００４２】
なお、本実施形態では、プロセッサ４１は、既述の手順(1)、(2)に示すように、受信語ｘに含まれる情報記号に重畳され得る誤り系列の内、適用された組織符号の誤り訂正能力の下で誤り訂正が可能である全ての誤り系列のみに対応した推定受信語を生成し、これらの推定受信語を推定受信語レジスタ５１に蓄積している。
【００４３】
しかし、このような推定受信語レジスタ５１には、既述の距離の比較の対象となるべき推定受信語の数が増加することに起因する応答性の低下が許容される場合には、受信語ｘに含まれ得る情報記号に実際に重畳され得る誤り系列の全てに対応した推定受信語が蓄積されてもよい。
また、本実施形態では、個々の受信語について推定受信語の全てが一括して生成され、かつ推定受信語レジスタ５１に蓄積された後に、既述の距離の算出および比較が行われているが、このような距離の算出および比較は、例えば、個々の推定受信語が生成される度に逐次行われてもよい。
【００４４】
以下、本発明に係る第２、５の技術に対応した実施形態について説明する。
本実施形態と本発明に係る第１の技術に対応した実施形態との構成の相違点は、図４に示すように、プロセッサ４１に代えてプロセッサ４１Ａが備えられた点にある。
なお、本実施形態と図２に示すブロックとの対応関係については、入力インタフェース部７１およびプロセッサ４１Ａは情報抽出手段１１に対応し、プロセッサ４１Ａは仮想誤り系列供給手段２１、仮想正規受信語手段２２および推定手段２３に対応し、プロセッサ４１Ａおよび出力インタフェース部７４は受信語判定手段２４に対応する。
【００４５】
図８は、本発明に係る第２、５、７の技術に対応した本実施形態の動作フローチャートである。
図９は、本発明に係る第２、５、７の技術に対応した本実施形態の動作を説明する図である。
以下、図４、図８〜図９および図１４を参照して本発明に係る第２、５の技術に対応した本実施形態の動作を説明する。
【００４６】
プロセッサ４１Ａの主記憶の特定の記憶領域には、図１０に示すように、受信語ｘに含まれる情報記号について、組織符号の誤り訂正能力の範囲で誤り訂正が可能であるビット誤りの全ての態様を個別に示す誤りパターンと、その誤りパターンに対する正規の検査記号である仮想検査記号との対として定義される仮想誤り系列が予め格納された仮想誤り系列テーブル６１が配置される。
【００４７】
また、プロセッサ４１Ａは、受信語レジスタ８１の領域管理を行い、その領域管理の下で受信語レジスタ８１の空いている領域に、入力インタフェース部７１を介して受信系列として与えられた受信語ｘを順次格納する。
さらに、プロセッサ４１Ａは、このようにして受信語レジスタ８１に格納された個々の受信語ｘについて、以下の<1>〜<4>に示す一連の処理を行う。
【００４８】
<1> 受信語ｘに含まれる情報記号を抽出し（図８(1)、図９(1))、組織記号に適応したこの情報記号の正規の検査記号を求める（図９(2))と共に、これらの情報記号および検査記号が連結されることによってなる仮想受信語（図９(3 ))を生成する（図８(2))。
<2> 仮想誤り系列テーブル６１に格納された個々の仮想誤り系列（図９(4))について、上述した仮想受信語との和をとることによって複数の推定受信語を生成し、これらの推定受信語を推定受信語レジスタ５１に蓄積する（図８(3 )、図９(5))。
【００４９】
<3> 推定受信語レジスタ５１にこのようにして蓄積された全ての推定受信語について、符号語テーブル８２に格納された受信語ｘとの距離を算出し（図８ (4)、図９(6))、
<4> これらの推定受信語の内、算出された距離が最小である推定受信語を最尤解とすると共に、出力インタフェース部７３を介してその最尤解を復号系列として順次出力する（図８(5)、図９(7))。
【００５０】
ところで、既述の推定受信語は、本発明に係る第１、４の技術に対応した実施形態と同様の条件の下で上式(1) で示され、その式の右辺については、一般に、
【数７】

の式に展開できる。
また、上述した仮想受信語は上式(2) の右辺の第１項である
【数８】

に相当し、かつ仮想誤り系列テーブル６１に格納された仮想誤り系列はその右辺の第２項である(ｅⁿ、Ｐ(ｅⁿ))に相当する。
【００５１】
したがって、上式(2) で示される推定受信語は既述の真の符号（ｘ_i、Ｐ(ｘ_i)）に等しいビット列に相当し、かつ既述の手順<4> によれば、本発明に係る第１、４の技術に対応した実施形態と同様に最尤解が確度高く得られる。
さらに、本実施形態では、検査記号を生成する処理は、既述の仮想受信語に含まれるべき検査記号のみについて行われる。
【００５２】
したがって、本実施形態によれば、推定受信語の全てに個別に含まれるべき検査記号が生成される本発明に係る第１、４、７の技術に対応した実施形態に比べて、ハードウエアの規模の削減と構成の簡略化とに併せて、処理量の削減が達成され、かつ最尤復号化の効率が高められる。
なお、本実施形態では、仮想誤り系列テーブル６１には、仮想誤り系列が組織符号の誤り訂正能力の範囲で予め格納されている。
【００５３】
しかし、このような仮想誤り系列テーブル６１については、既述の距離の比較の対象となるべき仮想受信語の数が増加することによる応答性の低下が許容される場合には、受信語ｘに含まれる情報記号について実際に生じる得るビット誤りの全てに対応した仮想誤り系列が予め格納されてもよい。
以下、本発明に係る第３、６の技術に対応した実施形態について説明する。
【００５４】
本実施形態と本発明に係る第２の技術に対応した実施形態との構成の相違点は、図４に示すように、プロセッサ４１Ａに代えてプロセッサ４１Ｂが備えられた点にある。
【００５５】
なお、本実施形態と図３に示すブロック図との対応関係については、入力インタフェース部７１およびプロセッサ４１Ｂは記号抽出手段３１に対応し、プロセッサ４１Ｂは仮想検査記号供給手段３２、仮想正規検査記号生成手段３３および推定手段３４に対応し、プロセッサ４１Ｂおよび出力インタフェース部７４は受信語判定手段３５に対応する。
【００５６】
図１１は、本発明に係る第３、６、７の技術に対応した本実施形態の動作フローチャートである。
図１２は、本発明に係る第３、６、７の技術に対応した本実施形態の動作を説明する図である。
以下、図４、図７、図１０〜図１２および図１４を参照して本発明に係る第３、６の技術に対応した本実施形態の動作を説明する。
【００５７】
プロセッサ４１Ｂの主記憶の特定の記憶領域には、図１０に点線で示すように、受信語ｘに含まれる情報記号について、組織符号の誤り訂正能力の範囲で誤り訂正が可能であるビット誤りの全ての態様を個別に示す誤りパターンに対して、正規の検査記号を示す仮想検査記号のみが予め格納された仮想誤り系列テーブル６１Ａが配置される。
【００５８】
また、プロセッサ４１Ｂは、受信語レジスタ８１の領域管理を行い、その領域管理の下でこの受信語レジスタ８１の空いている領域に、入力インタフェース部７１を介して受信系列として与えられた受信語ｘを順次格納する。
さらに、プロセッサ４１Ｂは、このようにして受信語レジスタ８１に格納された個々の受信語ｘについて、以下の[1]〜[4]に示す一連の処理を行う。
【００５９】
[1] 受信語ｘに含まれる情報記号を抽出し（図１２(1))、組織記号に適応したこの情報記号の正規の検査記号を求める（図１１(1)、図１２(2))。
[2] 仮想誤り系列テーブル６１Ａに格納された個々の仮想検査記号（図１２(3 ))について、上述した正規の検査記号（図１２(4))との和をとることによって複数の推定検査記号を生成し（図１１(2))、これらの推定検査記号を推定受信語レジスタ５１の対応するフィールドに蓄積する（図１１(3)、図１２(5 ))。
【００６０】
[3] 推定受信語レジスタ５１にこのようにして蓄積された全ての推定検査記号について、符号語テーブル８２に格納された受信語ｘに含まれる検査記号との距離を算出し（図１１(4)、図１２(6))、
[4] これらの推定受信語の内、算出された距離が最小である推定受信語を最尤解とすると共に、出力インタフェース部７３を介してその最尤解を復号系列として順次出力する（図１１(5)、図１２(7))。
【００６１】
ところで、既述の受信語ｘと推定受信語との距離ｄについては、２つの符号Ｘ、Ｙ間の距離が関数dist(Ｘ、Ｙ)で示される場合には、
【数９】

の式で示される。さらに、上述した組織符号が線形符号である場合には、距離ｄは、
【数１０】

の式で示される。しかし、上式の第１項の値は、ｅⁿ、すなわち実際に生じる誤りを示す誤りパターンのみによって決定され、かつ既知である。
【００６２】
すなわち、距離ｄは、ハミング距離として与えられる場合には、ｅⁿ として与えられるビットの内、論理値が「１」であるビットの数（ユークリッド距離として与えられるべき場合にはｎ^1/2)として与えられる値value(ｅⁿ)に対して、
【数１１】

の式で示される。
【００６３】
したがって、上述した手順[3] で算出される距離は、上式の第二項の値に相当するので、value（ｅⁿ）の値が定数である場合には、大小関係を確度高く示す「最尤復号化の基準」となる。
このように本実施形態によれば、検査記号を生成する処理は、本発明に係る第２、５の技術に対応した実施形態と同様にして仮想受信語に含まれるべき検査記号のみについて行われ、かつ上述した距離の算出および比較は、検査記号のみについて行われる。
【００６４】
したがって、これらの距離の算出および比較が受信語に含まれる情報記号についても行われる本発明に係る第１、２、４、５の技術に対応した実施形態に比べて、ハードウエアの規模の削減と構成の簡略化とに併せて、処理量の削減が達成され、かつ最尤復号化の効率が高められる。
なお、本実施形態では、仮想誤り系列テーブル６１Ａには、仮想検査記号が誤り訂正能力の範囲で予め格納されている。
【００６５】
しかし、このような仮想誤り系列テーブル６１Ａについては、既述の距離の比較の対象となるべき仮想検査記号の数が増加することによる応答性の低下が許容される場合には、受信語ｘに含まれる情報記号について実際に生じる得るビット誤りの全てに対応した仮想検査記号が予め格納されてもよい。
また、本実施形態では、value（ｅⁿ）の値が一定であるために検査記号のみの距離が最尤復号化の基準として算出されているが、その値が一定でない場合であっても、例えば、情報記号の全ての態様について ビット誤りパターンｅⁿ 毎に予め求められた値が登録されたテーブルが距離ｄの算出の過程で適宜参照されることによって、その距離ｄの算出にかかわる演算手順の煩雑化が回避されてもよい。
【００６６】
以下、図４〜図６、図８、図９、図１１および図１２を参照して本発明に係る第７の技術に対応した本実施形態の動作を説明する。
本実施形態では、最小距離ｋが既知の値であって、受信語ｘに対する（ハミング）距離がｋ以下である符号の数が「１」である組織符号が適用される。
【００６７】
プロセッサ４１、４１Ａ、４１Ｂは、それぞれこのような最小距離ｋが予め与えられ、かつ算出した（図５(4)、図８(4)、図１１(3))距離がその最小距離ｋ以下であるか否かを判別する。
さらに、プロセッサ４１、４１Ａ、４１Ｂは、その判別の結果が偽である場合には、既述の通りの処理を行うことによって最尤復号化処理を行うが、反対に真である場合には、その判別の結果が得られた推定受信語を最尤解として出力インタフェース部７３を介して出力すると共に、該当する受信語に関する限り、後続する推定受信語に対する距離の算出と比較とを省略する（図８(a)、図８(a)、図１１(a))。
【００６８】
すなわち、本実施形態では、適用された組織符号に固有の最小距離ｋに基づいて距離の算出および比較にかかわる処理が的確に省略されるので、本発明に係る第１〜６の技術に対応した実施形態に比べて最尤復号化処理に要する処理量が削減され、かつ最尤解が精度よく効率的に得られる。
なお、本実施形態では、本発明に係る第３、６の技術に対応した実施形態に本発明に係る第７の技術が適用されているが、この本発明に係る第７の技術は、図５および図８に点線で示すように、本発明に係る第１、２、４、５の技術に対応した実施形態にも同様に適用可能である。
【００６９】
また、本発明に係る第２、３、５、６の技術に対応した各実施形態では、仮想誤り系列テーブル６１、６１Ａに予め格納された誤りパターンとその誤りパターンに個別に対応した仮想検査記号とが適宜参照されているが、これらの誤りパターンおよび仮想検査記号については、最尤復号化の効率の低下や所要する処理量の増加が許容されるならば、その最尤復号化の対象となるべき組織符号に適応して適宜あるいは一括して生成されてもよい。
【００７０】
さらに、上述した各実施形態では、最尤復号化を実現する処理が専用のプロセッサ４１、４１Ａ、４１Ｂによって行われているが、これらの処理の一部もしくは全ては、呼設定、チャネル設定その他の何らかの処理を行うプロセッサの余剰の処理量が適用されることによって行われてもよく、ＤＳＰが行う信号処理、あるいは専用のハードウエア（ＬＳＩ化されてもよい。）が行う演算として行われてもよい。
【００７１】
また、このような処理を実現するソフトウエアや専用のハードウエアについては、如何なる形態で負荷分散や機能分散がはかられてもよい。
さらに、上述した各実施形態については、適用されるべき装置およびシステムが何ら示されていないが、本願発明は、通信系や伝送系に限らず、ハードディスクドライブのように記録媒体に組織符号化されて記録された情報を読み取る装置その他の多様な装置に適用可能である。
【００７２】
【発明の効果】
上述したように本発明に係る第１の技術では、最尤復号に要する処理量の削減がはかられる。
また、本発明に係る第２の技術では、本発明に係る第１の技術に比べて、処理量の削減がはかられる。
【００７３】
さらに、本発明に係る第３の技術では、復号化の確度が低下することなく本発明に係る第１、２の技術より処理量の削減がはかられる。
また、本発明に係る第４〜６の技術では、それぞれ本発明に係る第１〜３の技術に比べて、処理量の削減がはかられる。
さらに、本発明に係る第７の技術では、本発明に係る第１〜６の技術に比べて処理の効率化がはかられる。
【００７４】
したがって、これらの発明が適用されたシステムや装置では、信頼性が低下することなく、安価に多様な組織符号に対する柔軟な適応が可能となり、かつ応答性および性能が高められる。
【図面の簡単な説明】
【図１】 本発明に係る第１、４、７の技術の原理ブロック図である。
【図２】 本発明に係る第２、５、７の技術の原理ブロック図である。
【図３】 本発明に係る第３、６、７の技術の原理ブロック図である。
【図４】 本発明に係る第１〜７の技術に対応した実施形態を示す図である。
【図５】 本発明に係る第１、４、７の技術に対応した本実施形態の動作フローチャートである。
【図６】 本発明に係る第１、４、７の技術に対応した本実施形態の動作を説明する図である。
【図７】 推定受信語レジスタの構成を示す図である。
【図８】 本発明に係る第２、５、７の技術に対応した本実施形態の動作フローチャートである。
【図９】 本発明に係る第２、５、７の技術に対応した本実施形態の動作を説明する図である。
【図１０】 仮想誤り系列テーブルの構成を示す図である。
【図１１】 本発明に係る第３、６、７の技術に対応した本実施形態の動作フローチャートである。
【図１２】 本発明に係る第３、６、７の技術に対応した本実施形態の動作を説明する図である。
【図１３】 組織符号を最尤復号化する最尤復号器の構成例を示す図である。
【図１４】 受信語レジスタの構成を示す図である。
【図１５】 符号語テーブルの構成を示す図である。[0001]
BACKGROUND OF THE INVENTION
The present invention relates to a maximum likelihood decoder that generates a systematic code and performs maximum likelihood decoding on a received word that may be accompanied by some bit error.
[0002]
[Prior art]
In recent years, there has been a remarkable progress in computerization of society, and not only information that is sent and received via the communication system, but also information that should be subjected to some processing via the information processing system and information given as a result of that processing, High reliability is required.
In addition, as a technique for ensuring the reliability of this information, some redundant additional information given to the information based on a known rule is added to the desired information to be transmitted or recorded, and Many error correction codes are used in which it is determined whether or not information to be received or read is adapted to the rule, and further, bit errors are appropriately corrected based on this rule.
[0003]
Furthermore, there are various types of such error correction codes.
(a) Decoding is performed for each code block;
(b) An information block is arranged at a specific position of each code block, and a check symbol generated as a known function for the information symbol indicating the information block is arranged in the remaining code blocks
A systematic code characterized by points is widely applied to various fields because it has high accuracy and enables efficient code / decoding processing.
[0004]
FIG. 13 is a diagram illustrating a configuration example of a maximum likelihood decoder that performs maximum likelihood decoding of a systematic code.
In the figure, the input interface unit 71 is provided with a reception sequence consisting of a sequence of received words that should be systematic codes, and the processor 72 and the output interface unit 73 are connected to a bus 74 together with the input interface unit 71. At the output of the output interface unit 73, a decoded sequence is obtained as a result of maximum likelihood decoding.
[0005]
In the following, for the sake of simplicity, for example, when there is no bit error, a check symbol is configured for 3-bit logical values x1, x2, and x3 that configure an information symbol. 3 bits of logical value each
[Expression 1]

Is given as a systematic code given by
[0006]
In the maximum likelihood decoder having such a configuration, as shown in FIG. 14, the processor 72 includes a received word (error correction target code) x included in the above-described reception sequence and individually including an information symbol and a check symbol. And a received word register 81 consisting of a set of storage areas to be stored, and a code word C consisting of all pairs of information symbols and check symbols that can be normally included in the received word x as shown in FIG. The registered codeword table 82 is stored in a specific storage area of the main memory.
[0007]
The processor 72 manages the area of the received word register 81 and sequentially stores the received words given as a received sequence via the input interface unit 71 in an empty area of the received word register 81 under the area management.
Further, the processor 72 calculates distances from all the code words registered in advance in the code word table 82 for the individual received words stored in the received word register 81 in this manner, and among these words, The word having the smallest calculated distance is set as the maximum likelihood solution, and the maximum likelihood solution is sequentially output as a decoded sequence via the output interface unit 73.
[0008]
That is, the information symbol included in the received word x is a simple code that has nothing to do with the nature of the systematic code as long as the degree of bit errors attached to the received word x does not exceed the error correction capability inherent to the systematic code described above. On the basis of a simple calculation procedure, a bit error generated in the process of transmission, writing or reading is corrected and obtained as a normal information symbol.
[0009]
[Problems to be solved by the invention]
By the way, in the above-described conventional example, the number N of times that the processor 72 should calculate the distance for each received word x and the number of times N that the calculated distance should be compared are both the word length (number of bits) of the information symbol. For L
N = 2^L
As shown in the equation, the value is large.
[0010]
Therefore, as for the actual decoding process, for example, when a cyclic code that is a linear code is applied as a systematic code, “determination of whether or not the reception polynomial indicating the reception word x can be divided by the generator polynomial” Furthermore, it has to be achieved by applying an operation adapted to the nature of the codeword.
Furthermore, for example, when a BCH code is applied as a cyclic code, the Peterson method or the Berlekamp-Massey method can be applied to such a calculation procedure.
[0011]
However, these calculation procedures do not apply to different codes such as Golay codes, even if the systematic codes to be applied are linear codes.
Therefore, for a decoder applied to an apparatus or system to which a plurality of codes having different properties are to be applied, an operation procedure adapted to all of these codes must be incorporated, and the software scale is large. The case was high.
[0012]
It is an object of the present invention to provide a maximum likelihood decoder that can be flexibly adapted to various systematic codes, can greatly reduce the processing amount, and can perform decoding with high accuracy.
[0013]
[Means for Solving the Problems]
  FIG.According to the present invention1, 4, 7TechnologyIt is a principle block diagram of.
[0014]
  According to the present invention1TechnologyObtains all the prediction information symbols that can be the true values of the information symbols extracted by the information extraction means 11 and the information extraction means 11 that extract the information symbols from the received words given as systematic codes. For information symbols, estimation means 12 for obtaining an estimated received word consisting of a pair of check symbols individually adapted to the system code, and among the estimated received words obtained by the estimation means 12, a received word given as a system code And a received word determining means 13 for outputting a part or all of the estimated received word having the smallest distance as a decoding result.
[0015]
  FIG.According to the present invention2, 5, 7TechnologyIt is a principle block diagram of.
  According to the present invention2TechnologyThe information extraction means 11 for extracting information symbols from received words given as systematic codes, and all error patterns that are partial sequences including non-zero elements of error sequences that can be superimposed on the received words are individually organized A virtual error sequence supply means 21 for providing a virtual error sequence consisting of a pair with a check symbol adapted to the code; and a check symbol adapted to the systematic code for the information symbol extracted by the information extraction means 11; Virtual regular received word generating means 22 for generating virtual regular received words composed of information symbols and check symbols, virtual regular received words generated by virtual regular received word generating means 22, and individual given by virtual error sequence supplying means 21 An estimation means 23 for obtaining an estimated received word by taking the sum of the virtual error sequence and an organization code among the estimated received words obtained by the estimation means 23 The distance between the received word given as is characterized in that a received word determination means 24 output as a decoding result a part or all of the estimated received word is minimal.
[0016]
  FIG.According to the present invention3, 6, 7TechnologyIt is a principle block diagram of.
  According to the present invention3TechnologyAre symbol extraction means 31 for individually extracting information symbols and check symbols from received words given as systematic codes, and all errors that are partial sequences including non-zero elements of error sequences that can be superimposed on received words A virtual check symbol supply means 32 that gives virtual check symbols individually adapted to the tissue code for the pattern, and a virtual normal that generates a virtual normal check symbol adapted to the tissue code for the information symbols extracted by the information extraction means 31 Estimating the estimated check symbol by taking the sum of the check symbol generating means 33, the virtual normal check symbol generated by the virtual normal check symbol generating means 33, and the individual check symbols given by the virtual check symbol supplying means 32 The distance between the means 34 and the check symbol extracted by the symbol extraction means 31 among the estimated check symbols obtained by the estimation means 34 is the smallest. A received word determining means 35 for outputting the error pattern adapted to the systematic code for the estimated check symbol and the sum of the information symbol extracted by the symbol extracting means 31 as a decoding result. It is characterized by having.
[0017]
  According to the present invention4TechnologyIsAccording to the present invention1TechnologyIn the maximum likelihood decoder, the estimation means 12 obtains all prediction information symbols that can be the true values of the information symbols extracted by the information extraction means 11 within the range of the error correction capability of the systematic code. .
  According to the present invention5TechnologyIsAccording to the present invention2TechnologyIn the maximum likelihood decoder, the virtual error sequence supply means 21 individually applies all error patterns that are partial sequences including non-zero elements of error sequences that can be corrected within the range of error correction capability of the systematic code. A virtual error sequence consisting of a pair with a check symbol adapted to the systematic code is given.
[0018]
  According to the present invention6TechnologyIsAccording to the present invention3TechnologyIn the maximum likelihood decoder, the virtual check symbol supply means 32 individually determines all error patterns that are partial sequences including non-zero elements of error sequences that can be corrected within the range of error correction capability of systematic codes. A virtual check symbol adapted to the systematic code system is provided.
  According to the present invention7TechnologyIsAccording to the present invention1 toFirst6TechnologyAny one ofTechnologyIn the maximum likelihood decoder, a code whose minimum distance is known is applied as a systematic code, and the received word determination means 13, 24, and 35 determine whether or not the distance is less than the minimum distance, and the result of the determination is true. In this case, either the calculation of the subsequent distance or the determination related to the calculated distance is canceled, and the decoding result is fixed and output.
[0019]
  According to the present invention1TechnologyIn the maximum likelihood decoder, the information extraction means 11 extracts information symbols from the received word given as a systematic code, and the estimation means 12 obtains all prediction information symbols that can be true values of the information symbols. For these prediction information symbols, an estimated received word consisting of a pair with a check symbol adapted to this systematic code is obtained individually.
[0020]
For these estimated received words, if the difference between the prediction information symbol described above and the information symbol contained in the received word is equal to the error that actually accompanies the information symbol, this estimated information symbol is included, and the estimation means 12 Any of the estimated received words obtained by the above corresponds to a true code to be given as a received word without any error.
The received word determination unit 13 outputs a part or all of the estimated received words having the shortest distance from the received word given as the systematic code among the estimated received words obtained by the estimating unit 12 as a decoding result.
[0021]
  That is, the number of estimated received words to be compared individually is obtained in order to obtain a decoding result, and the number of estimated received words to be compared is definitely smaller than the number of all code words that can be given as an applied systematic code. Therefore, the amount of processing required for maximum likelihood decoding can be reduced.
  According to the present invention2TechnologyIn the maximum likelihood decoder according to the above, the information extracting means 11 extracts information symbols from the received word given as a systematic code. The virtual error sequence supply means 21 is a virtual that consists of pairs of check symbols individually adapted to this systematic code for all error patterns that are partial sequences including non-zero elements of error sequences that can be superimposed on the received word. Gives an error sequence. The virtual regular reception word generation unit 22 generates a check symbol adapted to the tissue code for the information symbol extracted by the information extraction unit 11, and generates a virtual normal reception word including the information symbol and the check symbol. The estimating means 23 obtains an estimated received word by taking the sum of the virtual regular received word generated in this way and the individual virtual error sequences given by the virtual error sequence supplying means 21.
[0022]
These estimated received words correspond to the sum of the above-mentioned virtual regular received word and an error pattern indicating an error that can accompany the received word, and the error pattern corresponds to the virtual error sequence given by the virtual error sequence supply means 21. To do.
That is, since any of the estimated received words given by the estimating means 23 corresponds to a true code that should be given as a received word without any error, the received word determining means 24 includes the organization of the estimated received words. A part or all of the estimated received word having the minimum distance from the received word given as a code can be output as a decoding result.
[0023]
  Further, since the virtual normal information generation means 22 generates check symbols adapted only to a single information symbol extracted by the information extraction means 11, such check symbols must be generated individually for all estimated received words. MustAccording to the present invention1TechnologyCompared with the maximum likelihood decoder, the amount of processing can be reduced.
  According to the present invention3TechnologyIn the maximum likelihood decoder, the symbol extracting means 31 individually extracts information symbols and check symbols from received words given as systematic codes, and the virtual check symbol supplying means 32 is an error that can be superimposed on the received words. For all error patterns that are partial sequences including non-zero elements of sequences, virtual check symbols adapted to systematic codes are given individually. The virtual normal check symbol generating means 33 generates a virtual normal check symbol adapted to the tissue code for the information symbol extracted by the information extracting means 31, and the estimating means 34 supplies the virtual normal check symbol and the virtual check symbol. An estimated test symbol is determined by taking the sum of the individual test symbols provided by means 32.
[0024]
The received word determination unit 35 obtains a distance from the estimated test symbols extracted by the symbol extraction unit 31 among these estimated test symbols.
By the way, such a distance means that a check symbol that is actually included in a received word that may be accompanied by some error and a check symbol that is normal with respect to an information symbol included in the received word have errors indicated by the error pattern described above. It is equal to the sum of the first distance between the accompanying check symbols and the second distance given as a function of this error pattern only.
[0025]
However, even if the second distance is constant or not constant, it is possible to employ a systematic code that is small enough to ensure the required maximum likelihood decoding accuracy. The means 35 decodes the error pattern adapted to the estimated check symbol having the minimum distance obtained as described above and / or the sum of the information symbols extracted by the symbol extraction means 31. By outputting as a result, maximum likelihood decoding can be achieved.
[0026]
  In addition, since the above-described processing for obtaining and comparing the distance is performed only for a check symbol having a word length shorter than that of the received word, the maximum likelihood decoder according to the present invention does not decrease the decoding accuracy.According to the present invention1, 2TechnologyThis is realized with a smaller processing amount than the maximum likelihood decoder.
  According to the present invention4TechnologyIn the maximum likelihood decoder forAccording to the present invention1TechnologyIn the maximum likelihood decoder, the estimation unit 12 obtains all prediction information symbols that can be true values of the information symbols extracted by the information extraction unit 11 within the range of the error correction capability of the systematic code.
[0027]
  That is, it is avoided that the received word determination means 13 unnecessarily obtains the distance even though error correction is impossible.According to the present invention1TechnologyCompared to the maximum likelihood decoder, the amount of processing required for maximum likelihood decoding is reduced.
  According to the present invention5TechnologyIn the maximum likelihood decoder forAccording to the present invention2TechnologyIn the maximum likelihood decoder, the virtual error sequence supply means 21 individually applies all error patterns that are partial sequences including non-zero elements of error sequences that can be corrected within the range of error correction capability of the systematic code. A virtual error sequence consisting of a pair of check symbols adapted to the systematic code is given.
[0028]
  That is, it is avoided that the received word determination unit 24 unnecessarily obtains the distance even though error correction is impossible.According to the present invention2TechnologyCompared to the maximum likelihood decoder, the amount of processing required for maximum likelihood decoding is reduced.
  According to the present invention6TechnologyIn the maximum likelihood decoder forAccording to the present invention3TechnologyIn the maximum likelihood decoder, the virtual check symbol supply means 32 individually outputs all error patterns that are partial sequences including non-zero elements of error sequences that can be corrected within the range of error correction capability of the systematic code. A virtual check symbol adapted to the tissue code is given.
[0029]
  That is, it is avoided that the received word determination means 35 unnecessarily obtains the distance even though error correction is impossible.According to the present invention3TechnologyCompared to the maximum likelihood decoder, the amount of processing required for maximum likelihood decoding is reduced.
  According to the present invention7TechnologyIn the maximum likelihood decoder forAccording to the present invention1 toFirst6TechnologyAny one ofTechnologyIn the maximum likelihood decoder, a code whose minimum distance is known is applied as a systematic code, and the received word determination means 13, 24, 35 determines whether the distance is equal to or less than the minimum distance, and When the determination result is true, either the subsequent calculation of the distance or the determination related to the calculated distance is canceled, and the decoding result is fixed and output.
[0030]
  That is, since the maximum likelihood decoding process to be performed for each code block is accurately terminated based on the minimum distance described above,According to the present invention1 toFirst6TechnologyMore efficient processing can be achieved.
[0031]
DETAILED DESCRIPTION OF THE INVENTION
Hereinafter, embodiments of the present invention will be described in detail with reference to the drawings.
[0032]
  FIG.According to the present invention1-7TechnologyIt is a figure which shows embodiment corresponding to.
  In the figure, components having the same functions and configurations as those shown in FIG. 13 are given the same reference numerals, and description thereof is omitted here.
  A difference between the present embodiment and the conventional example shown in FIG. 13 is that a processor 41 is provided instead of the processor 72.
[0033]
  As for the correspondence relationship between the present embodiment and the block diagram shown in FIG. 1, the input interface unit 71 and the processor 41 correspond to the information extraction unit 11, the processor 41 corresponds to the estimation unit 12, and the processor 41 and the output interface. The unit 74 corresponds to the received word determination unit 13.
  FIG.According to the present invention1, 4, 7TechnologyIt is the operation | movement flowchart of this embodiment corresponding to these.
[0034]
  FIG.According to the present invention1, 4, 7TechnologyIt is a figure explaining the operation | movement of this embodiment corresponding to.
  Hereinafter, referring to FIG. 4 to FIG. 6 and FIG.According to the present invention1, 4TechnologyThe operation of this embodiment corresponding to the above will be described.
  In the specific storage area of the main memory of the processor 41, all estimated information symbols that can be generated when a bit error occurs in the error correction capability range of the systematic code in the information symbols included in the received word x are shown in FIG. As shown in FIG. 4, an estimated received word register 51 in which estimated received words that are individually defined as pairs with estimated check symbols that are regular check symbols are stored.
[0035]
Further, the processor 41 performs area management of the received word register 81, and the received word x given as a received sequence via the input interface unit 71 to an empty area of the received word register 81 under the area management. Are stored sequentially.
Further, the processor 41 performs a series of processes shown in the following (1) to (4) for each received word x stored in the received word register 81 in this way.
[0036]
(1) Among all error sequences that can be superimposed on the information symbols included in the received word x, all error sequences that can be corrected under the error correction capability of the systematic code,
(1) The sum of the information symbol contained in the received word x and the corresponding error sequence is taken (for example, if the error correction capability of the systematic code is 1 bit, the logic of the individual bits constituting the information symbol) The estimated information symbol is obtained by inverting the value bit by bit (Fig. 5 (1)),
{Circle around (2)} An estimated check symbol that is a normal check symbol adapted to the estimated information symbol is obtained (FIG. 5 (2)).
[0037]
(2) The estimated received word composed of the estimated information symbol and the estimated check symbol obtained in this way for each error sequence is stored in the estimated received word register 51 (FIG. 5 (3), FIG. 6 (1)). )).
(3) For all of these estimated received words, the distance from the received word x stored in the received word register 81 is calculated (FIG. 5 (4), FIG. 6 (2)),
(4) Among these estimated received words, the estimated received word having the smallest calculated distance is set as the maximum likelihood solution, and the maximum likelihood solution is sequentially output as a decoded sequence via the output interface unit 73 (FIG. 5 (5), FIG. 6 (3)).
[0038]
By the way, regarding the estimated received word to be stored in the estimated received word register 51,
(a) Information symbol x to be included in the true code (hereinafter simply referred to as “true code”) indicated by the received word x by the information source (sender) of the received word x_i And inspection symbol P (x_i) And its true sign is (x_i, P (x_i))
(b) These information symbols x_i And inspection symbol P (x_i) And errors e_i , E_P For the true code as a whole (e_i, E_P)
(c) Information symbol x_i An error pattern e indicating the mode of errors that can occur inⁿ An error pattern indicating the mode of errors occurring in the entire true code is (eⁿ, P (eⁿ)) And
(d) The received word x is
[Expression 2]

Is represented by the estimated information symbol x described above._i ⁿIs
[Equation 3]

It is expressed by the following formula.
[0039]
  The estimated information symbol x_i ⁿThe estimated received word containing is (x_i ⁿ, P (x_i ⁿ)), Specifically,
[Expression 4]

It is shown by the formula of
  However, the information symbol x_i The actual error e_i Is the above-mentioned error pattern eⁿ Is generally equal to
[Equation 5]

The logical values of all the bits included in the bit string represented by the formula are “0”.
[0040]
Therefore, in such a case, the estimated received word represented by the above equation (1) is the true code (x_i, P (x_iAccording to the procedure (4) described above, the maximum likelihood solution similar to the conventional example can be obtained with high accuracy.
Further, the number N of estimated received words that should be calculated for the distance to the received word x stored in the received word register 81 and the comparison of these distances is expressed in the system code in the information symbol included in the received word x. Since the number of received words is equal to the number of received words obtained only when a bit error that does not exceed the error correction capability occurs, in the conventional example, the number of estimated code words registered in the code word table 82 (information symbol x_i For the maximum number of bits m that can be corrected within the range of the error correction capability described above
[Formula 6]

It is shown by the formula of ) Is smaller than
[0041]
As described above, according to the present embodiment, the required processing amount is greatly reduced, so that a device capable of high-speed computation is applied, or the hardware scale is increased to realize parallel computation. In addition, maximum likelihood decoding that is flexibly adapted to various systematic codes (may be non-linear codes) as compared with the conventional example is efficiently realized.
[0042]
In the present embodiment, as shown in the above-described procedures (1) and (2), the processor 41 uses the applied system code among the error sequences that can be superimposed on the information symbols included in the received word x. Estimated received words corresponding to only all error sequences that can be corrected with error correction capability are generated, and these estimated received words are stored in the estimated received word register 51.
[0043]
However, in such an estimated received word register 51, when a decrease in responsiveness due to an increase in the number of estimated received words to be compared with the above-described distance is allowed, the received word is Estimated received words corresponding to all error sequences that can actually be superimposed on information symbols that can be included in x may be accumulated.
In the present embodiment, the estimated distances are calculated and compared as described above after all the estimated received words are collectively generated and stored in the estimated received word register 51 for each received word. Such calculation and comparison of distances may be performed sequentially each time each estimated received word is generated, for example.
[0044]
  Less than,According to the present invention2, 5TechnologyAn embodiment corresponding to the above will be described.
  This embodiment andAccording to the present invention1Technology4 is that a processor 41A is provided in place of the processor 41, as shown in FIG.
  2, the input interface unit 71 and the processor 41A correspond to the information extraction unit 11, and the processor 41A includes the virtual error sequence supply unit 21 and the virtual regular received word unit 22. The processor 41 </ b> A and the output interface unit 74 correspond to the received word determination unit 24.
[0045]
  FIG.According to the present invention2, 5, 7TechnologyIt is the operation | movement flowchart of this embodiment corresponding to these.
  FIG.According to the present invention2, 5, 7TechnologyIt is a figure explaining the operation | movement of this embodiment corresponding to.
  Hereinafter, referring to FIG. 4, FIG. 8 to FIG. 9 and FIG.According to the present invention2, 5TechnologyThe operation of this embodiment corresponding to the above will be described.
[0046]
In a specific storage area of the main memory of the processor 41A, as shown in FIG. 10, all the bit errors that can be corrected within the error correction capability of the systematic code for the information symbols included in the received word x are stored. A virtual error sequence table 61 in which a virtual error sequence defined as a pair of an error pattern individually indicating an aspect and a virtual check symbol that is a normal check symbol for the error pattern is stored.
[0047]
Further, the processor 41A performs area management of the reception word register 81, and the received word x given as a reception sequence via the input interface unit 71 is assigned to an empty area of the reception word register 81 under the area management. Store sequentially.
Further, the processor 41A performs a series of processes shown in the following <1> to <4> for each received word x stored in the received word register 81 in this way.
[0048]
<1> The information symbol contained in the received word x is extracted (FIG. 8 (1), FIG. 9 (1)), and a normal check symbol of this information symbol adapted to the organization symbol is obtained (FIG. 9 (2)). At the same time, a virtual received word (FIG. 9 (3)) formed by concatenating these information symbols and check symbols is generated (FIG. 8 (2)).
<2> For each virtual error sequence (FIG. 9 (4)) stored in the virtual error sequence table 61, a plurality of estimated received words are generated by summing with the virtual received word described above, and these estimated The received words are stored in the estimated received word register 51 (FIG. 8 (3), FIG. 9 (5)).
[0049]
<3> For all estimated received words stored in the estimated received word register 51 in this way, the distances from the received word x stored in the codeword table 82 are calculated (FIG. 8 (4), FIG. 6)),
<4> Among these estimated received words, the estimated received word having the smallest calculated distance is set as the maximum likelihood solution, and the maximum likelihood solution is sequentially output as a decoded sequence via the output interface unit 73 (FIG. 8 (5), FIG. 9 (7)).
[0050]
  By the way, the above estimated received word isAccording to the present invention1, 4TechnologyIs expressed by the above equation (1) under the same conditions as in the embodiment corresponding to the above.
[Expression 7]

Can be expanded to
  The virtual received word mentioned above is the first term on the right side of the above equation (2).
[Equation 8]

And the virtual error sequence stored in the virtual error sequence table 61 is the second term on the right side (eⁿ, P (eⁿ)).
[0051]
  Therefore, the estimated received word represented by the above equation (2) is the true code (x_i, P (x_i)), And according to the procedure <4> described above,According to the present invention1, 4TechnologyAs in the embodiment corresponding to, the maximum likelihood solution can be obtained with high accuracy.
  Furthermore, in the present embodiment, the process of generating check symbols is performed only for check symbols that should be included in the above-described virtual received words.
[0052]
  Therefore, according to the present embodiment, check symbols to be individually included in all estimated received words are generated.According to the present invention1, 4, 7TechnologyCompared to the embodiment corresponding to the above, a reduction in processing amount is achieved together with a reduction in the size of hardware and a simplification of the configuration, and the efficiency of maximum likelihood decoding is increased.
  In this embodiment, the virtual error sequence table 61 stores virtual error sequences in advance within the range of error correction capability of systematic codes.
[0053]
  However, for such a virtual error sequence table 61, if a decrease in responsiveness due to an increase in the number of virtual received words to be compared with the above-described distance is allowed, the received error x is stored in the received word x. A virtual error sequence corresponding to all of the bit errors that can actually occur with respect to the included information symbols may be stored in advance.
  Less than,According to the present invention3, 6TechnologyAn embodiment corresponding to the above will be described.
[0054]
  This embodiment andAccording to the present invention2Technology4 is that a processor 41B is provided in place of the processor 41A, as shown in FIG.
[0055]
As for the correspondence relationship between the present embodiment and the block diagram shown in FIG. 3, the input interface unit 71 and the processor 41B correspond to the symbol extraction means 31, and the processor 41B includes the virtual check symbol supply means 32, the virtual normal check symbol generation. Corresponding to the means 33 and the estimating means 34, the processor 41B and the output interface unit 74 correspond to the received word determining means 35.
[0056]
  FIG.According to the present invention3, 6, 7TechnologyIt is the operation | movement flowchart of this embodiment corresponding to these.
  FIG.According to the present invention3, 6, 7TechnologyIt is a figure explaining the operation | movement of this embodiment corresponding to.
  Hereinafter, referring to FIG. 4, FIG. 7, FIG. 10 to FIG. 12 and FIG.According to the present invention3, 6TechnologyThe operation of this embodiment corresponding to the above will be described.
[0057]
In a specific storage area of the main memory of the processor 41B, as indicated by a dotted line in FIG. 10, bit errors that can be corrected within the error correction capability of the systematic code for the information symbols included in the received word x are stored. A virtual error sequence table 61A in which only virtual check symbols indicating normal check symbols are stored in advance is arranged for error patterns individually indicating all aspects.
[0058]
Further, the processor 41B performs area management of the reception word register 81, and the received word x given as a reception sequence via the input interface unit 71 to an empty area of the reception word register 81 under the area management. Are stored sequentially.
Further, the processor 41B performs a series of processes shown in the following [1] to [4] for each received word x stored in the received word register 81 in this way.
[0059]
[1] The information symbol contained in the received word x is extracted (FIG. 12 (1)), and a normal check symbol of this information symbol adapted to the organization symbol is obtained (FIG. 11 (1), FIG. 12 (2)). .
[2] For each virtual check symbol (FIG. 12 (3)) stored in the virtual error sequence table 61A, a plurality of estimated checks are obtained by taking the sum of the above-mentioned regular check symbols (FIG. 12 (4)). Symbols are generated (FIG. 11 (2)), and these estimated check symbols are stored in the corresponding fields of the estimated received word register 51 (FIG. 11 (3), FIG. 12 (5)).
[0060]
[3] For all the estimated check symbols accumulated in this way in the estimated received word register 51, the distances from the check symbols included in the received word x stored in the code word table 82 are calculated (FIG. 11 (4)). ), Fig. 12 (6)),
[4] Among these estimated received words, the estimated received word having the smallest calculated distance is set as the maximum likelihood solution, and the maximum likelihood solution is sequentially output as a decoded sequence via the output interface unit 73 (FIG. 11 (5), FIG. 12 (7)).
[0061]
By the way, for the distance d between the received word x and the estimated received word as described above, when the distance between the two codes X and Y is indicated by the function dist (X, Y),
[Equation 9]

It is shown by the formula of Furthermore, when the above-described systematic code is a linear code, the distance d is
[Expression 10]

It is shown by the formula of However, the value of the first term in the above equation is eⁿThat is, it is determined and known only by the error pattern indicating the error that actually occurs.
[0062]
That is, when the distance d is given as a Hamming distance, eⁿ The number of bits whose logical value is “1” among the bits given as n (n should be given as Euclidean distance^1/2) Value (e) given asⁿ)
## EQU11 ##

It is shown by the formula of
[0063]
  Therefore, the distance calculated in the above-described procedure [3] corresponds to the value of the second term of the above equation, so value (eⁿ) Is a constant, it is a “maximum likelihood decoding criterion” that indicates the magnitude relationship with high accuracy.
  As described above, according to the present embodiment, the process of generating the inspection symbol is as follows.According to the present invention2, 5TechnologyAs in the embodiment corresponding to the above, only the check symbols to be included in the virtual received word are performed, and the above-described distance calculation and comparison is performed only for the check symbols.
[0064]
  Therefore, the calculation and comparison of these distances are also performed for information symbols included in the received word.According to the present invention1, 2, 4, 5TechnologyCompared to the embodiment corresponding to the above, a reduction in processing amount is achieved together with a reduction in the size of hardware and a simplification of the configuration, and the efficiency of maximum likelihood decoding is increased.
  In the present embodiment, virtual check symbols are stored in advance within the range of error correction capability in the virtual error sequence table 61A.
[0065]
However, with regard to such a virtual error sequence table 61A, if a decrease in responsiveness due to an increase in the number of virtual check symbols to be compared with the above-described distance is allowed, Virtual check symbols corresponding to all bit errors that may actually occur for the included information symbols may be stored in advance.
In this embodiment, value (eⁿ) Is constant, the distance of only the check symbol is calculated as a criterion for maximum likelihood decoding. However, even if the value is not constant, for example, bit errors may occur for all aspects of the information symbol. Pattern eⁿ By referring to a table in which values obtained in advance for each time are registered as appropriate in the process of calculating the distance d, it is possible to avoid complication of the calculation procedure related to the calculation of the distance d.
[0066]
  Hereinafter, referring to FIGS. 4 to 6, FIG. 8, FIG. 9, FIG. 11 and FIG.According to the present invention7TechnologyThe operation of this embodiment corresponding to the above will be described.
  In the present embodiment, a systematic code in which the minimum distance k is a known value and the number of codes whose (Hamming) distance with respect to the received word x is equal to or less than k is “1” is applied.
[0067]
Each of the processors 41, 41A, 41B is given such a minimum distance k in advance and calculated (FIG. 5 (4), FIG. 8 (4), FIG. 11 (3)). It is determined whether or not there is.
Further, when the determination result is false, the processors 41, 41A, and 41B perform the maximum likelihood decoding process by performing the process as described above. On the contrary, when the determination result is true, The estimated received word from which the determination result is obtained is output as the maximum likelihood solution via the output interface unit 73, and as far as the corresponding received word is concerned, the calculation and comparison of the distance to the subsequent estimated received word are omitted ( FIG. 8A, FIG. 8A, and FIG. 11A).
[0068]
  That is, in the present embodiment, the processing related to the calculation and comparison of the distance is accurately omitted based on the minimum distance k unique to the applied tissue code.According to the present invention1-6TechnologyCompared to the embodiment corresponding to the above, the processing amount required for the maximum likelihood decoding process is reduced, and the maximum likelihood solution can be obtained accurately and efficiently.
  In this embodiment,According to the present invention3, 6TechnologyIn the embodiment corresponding toAccording to the present invention7TechnologyHas been applied, but thisAccording to the present invention7TechnologyAs shown by the dotted lines in FIG. 5 and FIG.According to the present invention1, 2, 4, 5TechnologyThe embodiment corresponding to the above can be similarly applied.
[0069]
  Also,According to the present invention2, 3, 5, 6TechnologyIn the embodiments corresponding to the above, error patterns stored in advance in the virtual error sequence tables 61 and 61A and virtual check symbols individually corresponding to the error patterns are appropriately referred to. Symbols are generated as appropriate or collectively according to the systematic code to be subjected to the maximum likelihood decoding, if a decrease in the efficiency of maximum likelihood decoding and an increase in required processing amount are allowed. Also good.
[0070]
Further, in each of the above-described embodiments, the processing for realizing maximum likelihood decoding is performed by the dedicated processors 41, 41A, and 41B. However, some or all of these processing may be performed for call setting, channel setting, and the like. It may be performed by applying an excessive amount of processing by a processor that performs some processing, or may be performed as signal processing performed by a DSP or calculation performed by dedicated hardware (which may be implemented as an LSI). Good.
[0071]
In addition, with regard to software for realizing such processing and dedicated hardware, load distribution and function distribution may be applied in any form.
Further, although no device or system to be applied is shown for each of the above-described embodiments, the present invention is not limited to a communication system or a transmission system, but is systematically encoded on a recording medium like a hard disk drive. The present invention can be applied to a device that reads information recorded in this manner and other various devices.
[0072]
【The invention's effect】
  As mentioned aboveAccording to the present invention1TechnologyThus, the amount of processing required for maximum likelihood decoding can be reduced.
  Also,According to the present invention2TechnologyThenAccording to the present invention1TechnologyCompared with, the amount of processing can be reduced.
[0073]
  further,According to the present invention3TechnologySo, without reducing the accuracy of decodingAccording to the present invention1, 2TechnologyThe amount of processing can be further reduced.
  Also,According to the present invention4-6TechnologyThen, eachAccording to the present invention1-3TechnologyThe amount of processing can be reduced compared to
  further,According to the present invention7TechnologyThenAccording to the present invention1-6TechnologyCompared with, the processing efficiency can be improved.
[0074]
Therefore, in the system and apparatus to which these inventions are applied, the flexibility can be flexibly applied to various system codes at a low cost without reducing the reliability, and the responsiveness and performance can be improved.
[Brief description of the drawings]
[Figure 1]According to the present invention1, 4, 7TechnologyIt is a principle block diagram of.
[Figure 2]According to the present invention2, 5, 7TechnologyIt is a principle block diagram of.
[Fig. 3]According to the present invention3, 6, 7TechnologyIt is a principle block diagram of.
[Fig. 4]According to the present invention1-7TechnologyIt is a figure which shows embodiment corresponding to.
[Figure 5]According to the present invention1, 4, 7TechnologyIt is the operation | movement flowchart of this embodiment corresponding to these.
[Fig. 6]According to the present invention1, 4, 7TechnologyIt is a figure explaining the operation | movement of this embodiment corresponding to.
FIG. 7 is a diagram illustrating a configuration of an estimated received word register.
[Fig. 8]According to the present invention2, 5, 7TechnologyIt is the operation | movement flowchart of this embodiment corresponding to these.
FIG. 9According to the present invention2, 5, 7TechnologyIt is a figure explaining the operation | movement of this embodiment corresponding to.
FIG. 10 is a diagram showing a configuration of a virtual error sequence table.
FIG. 11According to the present invention3, 6, 7TechnologyIt is the operation | movement flowchart of this embodiment corresponding to these.
FIG.According to the present invention3, 6, 7TechnologyIt is a figure explaining the operation | movement of this embodiment corresponding to.
FIG. 13 is a diagram illustrating a configuration example of a maximum likelihood decoder that performs maximum likelihood decoding of a systematic code.
FIG. 14 is a diagram illustrating a configuration of a received word register.
FIG. 15 is a diagram illustrating a configuration of a codeword table.

Claims (6)

Information extracting means for extracting an information symbol from a received word given as a tissue code;
All prediction information symbols that can be true values of information symbols extracted by the information extraction means are obtained within the range of error correction capability of the systematic code , and these prediction information symbols are individually adapted to the systematic code. An estimation means for obtaining an estimated received word consisting of a pair with a check symbol;
Receiving word determination means for outputting a part or all of the estimated received words having the shortest distance from the received word given as the systematic code among the estimated received words obtained by the estimating means as a decoding result. A maximum likelihood decoder. Information extracting means for extracting an information symbol from a received word given as a tissue code;
Virtual error sequence supply that provides a virtual error sequence consisting of a pair of check symbols individually adapted to the systematic code for all error patterns that are partial sequences including non-zero elements of error sequences that can be superimposed on the received word Means,
Virtual regular reception word generation means for generating a check symbol adapted to the systematic code for the information symbol extracted by the information extraction means, and generating a virtual normal reception word composed of the information symbol and the check symbol;
Estimating means for obtaining an estimated received word by taking the sum of the virtual regular received word generated by the virtual regular received word generating means and the individual virtual error sequences given by the virtual error sequence supplying means;
Receiving word determination means for outputting a part or all of the estimated received words having the shortest distance from the received word given as the systematic code among the estimated received words obtained by the estimating means as a decoding result. A maximum likelihood decoder. Symbol extraction means for individually extracting information symbols and check symbols from received words given as tissue codes;
Virtual check symbol supply means for individually giving virtual check symbols adapted to the systematic code for all error patterns that are partial sequences including non-zero elements of error sequences that can be superimposed on the received word;
Virtual normal check symbol generation means for generating a virtual normal check symbol adapted to the tissue code for the information symbol extracted by the information extraction means;
Estimating means for obtaining an estimated check symbol by taking the sum of a virtual normal check symbol generated by the virtual normal check symbol generating means and individual check symbols given by the virtual check symbol supplying means;
An error pattern adapted to the systematic code for the estimated check symbol having the smallest distance from the check symbol extracted by the symbol extracting means among the estimated check symbols obtained by the estimating means, and the symbol extracting means And a received word determination means for outputting either or both of the sum and the information symbol extracted as a decoding result. The maximum likelihood decoder of claim 2,
The virtual error sequence supply means
Virtual errors consisting of pairs of check symbols individually adapted to the systematic code for all error patterns that are subsequences including non-zero elements of the error series that can be corrected within the error correction capability of the systematic code A maximum likelihood decoder characterized by providing a sequence. The maximum likelihood decoder of claim 3,
The virtual inspection symbol supply means
For each error pattern that is a partial sequence including a non-zero element of an error sequence that can be corrected within the error correction capability of the systematic code, a virtual check symbol that is individually adapted to the systematic code system is given. Feature maximum likelihood decoder. The maximum likelihood decoder according to any one of claims 1 to 5 ,
A code with a known minimum distance is applied as a systematic code,
The received word determination means is
It is determined whether or not the distance is equal to or less than the minimum distance, and when the determination result is true, either the subsequent calculation of the distance or the determination related to the calculated distance is canceled, and the decoding result is determined. A maximum likelihood decoder characterized in that it is determined and output.

Images