(57)【特許請求の範囲】
【請求項１】
組織符号として与えられた受信語から情報記号を抽出する情報抽出手段と、
前記情報抽出手段によって抽出された情報記号の真の値であり得る全ての予測情報記号を、組織符号の誤り訂正能力の範囲で求め、これらの予測情報記号について、個別に前記組織符号に適応した検査記号との対からなる推定受信語を求める推定手段と、
前記推定手段によって求められた推定受信語の内、前記組織符号として与えられた受信語との距離が最小である推定受信語の一部もしくは全てを復号結果として出力する受信語判定手段と
を備えたことを特徴とする最尤復号器。
【請求項２】
組織符号として与えられた受信語から情報記号を抽出する情報抽出手段と、
前記受信語に重畳され得る誤り系列の非零の元を含む部分系列である全ての誤りパターンについて、個別に前記組織符号に適応した検査記号との対からなる仮想誤り系列を与える仮想誤り系列供給手段と、
前記情報抽出手段によって抽出された情報記号に対して前記組織符号に適応した検査記号を生成し、これらの情報記号および検査記号からなる仮想正規受信語を生成する仮想正規受信語生成手段と、
前記仮想正規受信語生成手段によって生成された仮想正規受信語と、前記仮想誤り系列供給手段によって与えられる個々の仮想誤り系列との和をとることによって推定受信語を求める推定手段と、
前記推定手段によって求められた推定受信語の内、前記組織符号として与えられた受信語との距離が最小である推定受信語の一部もしくは全てを復号結果として出力する受信語判定手段と
を備えたことを特徴とする最尤復号器。
【請求項３】
組織符号として与えられた受信語から情報記号と検査記号とを個別に抽出する記号抽出手段と、
前記受信語に重畳され得る誤り系列の非零の元を含む部分系列である全ての誤りパターンについて、個別に前記組織符号に適応した仮想検査記号を与える仮想検査記号供給手段と、
前記情報抽出手段によって抽出された情報記号に対して前記組織符号に適応した仮想正規検査記号を生成する仮想正規検査記号生成手段と、
前記仮想正規検査記号生成手段によって生成された仮想正規検査記号と、前記仮想検査記号供給手段によって与えられる個々の検査記号との和をとることによって推定検査記号を求める推定手段と、
前記推定手段によって求められた推定検査記号の内、前記記号抽出手段によって抽出された検査記号との距離が最小である推定検査記号に対して前記組織符号に適応する誤りパターンと、その記号抽出手段によって抽出された情報記号との和との双方あるいは何れか一方を復号結果として出力する受信語判定手段と
を備えたことを特徴とする最尤復号器。
【請求項４】
請求項２に記載の最尤復号器において、
仮想誤り系列供給手段は、
組織符号の誤り訂正能力の範囲で訂正が可能である誤り系列の非零の元を含む部分系列である全ての誤りパターンについて、個別にその組織符号に適応した検査記号との対からなる仮想誤り系列を与える
ことを特徴とする最尤復号器。
【請求項５】
請求項３に記載の最尤復号器において、
仮想検査記号供給手段は、
組織符号の誤り訂正能力の範囲で訂正が可能である誤り系列の非零の元を含む部分系列である全ての誤りパターンについて、個別にその組織符号の方式に適応した仮想検査記号を与える
ことを特徴とする最尤復号器。
【請求項６】
請求項１ないし請求項５の何れか１項に記載の最尤復号器において、
最小距離が既知である符号が組織符号として適用され、
受信語判定手段は、
距離が前記最小距離以下か否かを判別し、その判別の結果が真であるときに、後続する距離の算出と、その算出された距離にかかわる判別との何れかを取り止め、かつ復号結果を確定して出力する
ことを特徴とする最尤復号器。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、組織符号として生成され、かつ何らかのビット誤りが伴い得る受信語を最尤復号化する最尤復号器に関する。
【０００２】
【従来の技術】
近年、社会の情報化が著しく進み、通信系を介して送受される情報だけではなく、情報処理系を介して何らかの処理が施されるべき情報とその処理の結果として与えられる情報とには、高い信頼性が要求されている。
また、この情報の信頼性を確保する技術としては、送信され、あるいは記録されるべき所望の情報にその情報に対して既知の規則に基づいて与えられる何らかの冗長な付加情報が付加されると共に、受信され、あるいは読み出されるべき情報がその規則に適応しているか否かを判別し、さらに、ビット誤りがこの規則に基づいて適宜訂正される誤り訂正符号が多く適用されている。
【０００３】
さらに、このような誤り訂正符号には、多様なものがあるが、特に、
(a) 復号化が符号ブロック毎に行われ、
(b) 個々の符号ブロックの特定の位置に情報ブロックが配置され、残りの符号ブロックにその情報ブロックを示す情報記号に対する既知の関数として生成された検査記号が配置される
点に特徴がある組織符号は、確度が高く、かつ効率的な符・復号化処理が可能であるために、多様な分野に広く適用されている。
【０００４】
図１３は、組織符号を最尤復号化する最尤復号器の構成例を示す図である。
図において、入力インタフェース部７１には組織符号であるべき受信語の列からなる受信系列が与えられ、その入力インタフェース部７１に併せて、プロセッサ７２および出力インタフェース部７３はバス７４に接続される。出力インタフェース部７３の出力には、最尤復号化の結果として復号系列が得られる。
【０００５】
なお、受信語については、以下では、簡単のため、例えば、ビット誤りが何ら伴わない場合には、情報記号を構成する３ビットの論理値ｘ１、ｘ２、ｘ３に対して、検査記号を構成する３ビットの論理値がそれぞれ
【数１】
0004041219.tif 000002
で与えられる組織符号として与えられると仮定する。
【０００６】
このような構成の最尤復号器では、プロセッサ７２は、図１４に示すように、上述した受信系列に含まれ、かつ個別に情報記号と検査記号とを含む受信語（誤り訂正対象符号）ｘが蓄積されるべき記憶領域の集合からなる受信語レジスタ８１と、図１５に示すように、受信語ｘに正規に含まれ得る情報記号と検査記号との全ての対からなる符号語Ｃが予め登録された符号語テーブル８２とを主記憶の特定の記憶領域に有する。
【０００７】
プロセッサ７２は、受信語レジスタ８１の領域管理を行い、かつ入力インタフェース部７１を介して受信系列として与えられる受信語をその領域管理の下で受信語レジスタ８１の空いている領域に順次格納する。
さらに、プロセッサ７２は、このようにして受信語レジスタ８１に格納された個々の受信語について、符号語テーブル８２に予め登録された全ての符号語との距離を算出し、これらの語の内、算出された距離が最小である語を最尤解とすると共に、その最尤解を出力インタフェース部７３を介して順次復号系列として出力する。
【０００８】
すなわち、受信語ｘに含まれる情報記号は、その受信語ｘに付帯するビット誤りの程度が上述した組織符号に固有の誤り訂正能力を超えない限り、この組織符号の性質に何ら関係がない単純な演算手順に基づいて、伝送、あるいは書き込みや読み出しの過程で生じたビット誤りが訂正されると共に、正規の情報記号として得られる。
【０００９】
【発明が解決しようとする課題】
ところで、上述した従来例では、個々の受信語ｘに対してプロセッサ７２が距離を算出すべき回数Ｎと算出された距離を比較すべき回数Ｎとは、共に情報記号の語長（ビット数）Ｌに対して
Ｎ＝２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 に生じ得る誤りの態様を示す誤りパターンｅn に対して真の符号の全体に生じる誤りの態様を示す誤りパターンが(ｅn、Ｐ(ｅn))で表されると共に、
(d) 受信語ｘが
【数２】
0004041219.tif 000003
で表される場合には、上述した推定情報記号ｘinは、
【数３】
0004041219.tif 000004
の式で表される。
【００３９】
また、その推定情報記号ｘinを含む推定受信語は、（ｘin、Ｐ(ｘin)）で表記され、具体的には、
【数４】
0004041219.tif 000005
の式で示される。
しかし、情報記号ｘi に実際に生じた誤りｅi が上述した誤りパターンｅn に等しい場合には、一般に、
【数５】
0004041219.tif 000006
の式で示されるビット列に含まれる全てのビットの論理値は「０」となる。
【００４０】
したがって、このような場合には、上式(1) で示される推定受信語は既述の真の符号（ｘi、Ｐ(ｘi)）に相当し、かつ既述の手順(4) によれば、従来例と同様の最尤解が確度高く得られる。
また、受信語レジスタ８１に格納された受信語ｘに対する距離の算出と、これらの距離の比較とが行われるべき推定受信語の数Ｎは、その受信語ｘに含まれる情報記号に組織符号の誤り訂正能力を超えない程度のビット誤りが生じた場合に限って得られる受信語の数に等しいので、従来例において、符号語テーブル８２に予め登録された推定符号語の数（情報記号ｘi の語長Ｌ、上述した誤り訂正能力の範囲で誤り訂正が可能である最大のビット数ｍに対して
【数６】
0004041219.tif 000007
の式で示される。）に比べて小さな値となる。
【００４１】
このように本実施形態によれば、所要する処理量が大幅に削減されるので、高速の演算を可能とするデバイスが適用され、あるいは並列演算を実現するためにハードウエアの規模が大きくなることなく、従来例に比べて多様な組織符号（非線形符号であってもよい。）に柔軟に適応した最尤復号化が効率的に実現される。
【００４２】
なお、本実施形態では、プロセッサ４１は、既述の手順(1)、(2)に示すように、受信語ｘに含まれる情報記号に重畳され得る誤り系列の内、適用された組織符号の誤り訂正能力の下で誤り訂正が可能である全ての誤り系列のみに対応した推定受信語を生成し、これらの推定受信語を推定受信語レジスタ５１に蓄積している。
【００４３】
しかし、このような推定受信語レジスタ５１には、既述の距離の比較の対象となるべき推定受信語の数が増加することに起因する応答性の低下が許容される場合には、受信語ｘに含まれ得る情報記号に実際に重畳され得る誤り系列の全てに対応した推定受信語が蓄積されてもよい。
また、本実施形態では、個々の受信語について推定受信語の全てが一括して生成され、かつ推定受信語レジスタ５１に蓄積された後に、既述の距離の算出および比較が行われているが、このような距離の算出および比較は、例えば、個々の推定受信語が生成される度に逐次行われてもよい。
【００４４】
以下、本発明に係る第２、５の技術に対応した実施形態について説明する。
本実施形態と本発明に係る第１の技術に対応した実施形態との構成の相違点は、図４に示すように、プロセッサ４１に代えてプロセッサ４１Ａが備えられた点にある。
なお、本実施形態と図２に示すブロックとの対応関係については、入力インタフェース部７１およびプロセッサ４１Ａは情報抽出手段１１に対応し、プロセッサ４１Ａは仮想誤り系列供給手段２１、仮想正規受信語手段２２および推定手段２３に対応し、プロセッサ４１Ａおよび出力インタフェース部７４は受信語判定手段２４に対応する。
【００４５】
図８は、本発明に係る第２、５、７の技術に対応した本実施形態の動作フローチャートである。
図９は、本発明に係る第２、５、７の技術に対応した本実施形態の動作を説明する図である。
以下、図４、図８〜図９および図１４を参照して本発明に係る第２、５の技術に対応した本実施形態の動作を説明する。
【００４６】
プロセッサ４１Ａの主記憶の特定の記憶領域には、図１０に示すように、受信語ｘに含まれる情報記号について、組織符号の誤り訂正能力の範囲で誤り訂正が可能であるビット誤りの全ての態様を個別に示す誤りパターンと、その誤りパターンに対する正規の検査記号である仮想検査記号との対として定義される仮想誤り系列が予め格納された仮想誤り系列テーブル６１が配置される。
【００４７】
また、プロセッサ４１Ａは、受信語レジスタ８１の領域管理を行い、その領域管理の下で受信語レジスタ８１の空いている領域に、入力インタフェース部７１を介して受信系列として与えられた受信語ｘを順次格納する。
さらに、プロセッサ４１Ａは、このようにして受信語レジスタ８１に格納された個々の受信語ｘについて、以下の<1>〜<4>に示す一連の処理を行う。
【００４８】
<1> 受信語ｘに含まれる情報記号を抽出し（図８(1)、図９(1))、組織記号に適応したこの情報記号の正規の検査記号を求める（図９(2))と共に、これらの情報記号および検査記号が連結されることによってなる仮想受信語（図９(3    ))を生成する（図８(2))。
<2> 仮想誤り系列テーブル６１に格納された個々の仮想誤り系列（図９(4))について、上述した仮想受信語との和をとることによって複数の推定受信語を生成し、これらの推定受信語を推定受信語レジスタ５１に蓄積する（図８(3    )、図９(5))。
【００４９】
<3> 推定受信語レジスタ５１にこのようにして蓄積された全ての推定受信語について、符号語テーブル８２に格納された受信語ｘとの距離を算出し（図８    (4)、図９(6))、
<4> これらの推定受信語の内、算出された距離が最小である推定受信語を最尤解とすると共に、出力インタフェース部７３を介してその最尤解を復号系列として順次出力する（図８(5)、図９(7))。
【００５０】
ところで、既述の推定受信語は、本発明に係る第１、４の技術に対応した実施形態と同様の条件の下で上式(1) で示され、その式の右辺については、一般に、
【数７】
0004041219.tif 000008
の式に展開できる。
また、上述した仮想受信語は上式(2) の右辺の第１項である
【数８】
0004041219.tif 000009
に相当し、かつ仮想誤り系列テーブル６１に格納された仮想誤り系列はその右辺の第２項である(ｅn、Ｐ(ｅn))に相当する。
【００５１】
したがって、上式(2) で示される推定受信語は既述の真の符号（ｘi、Ｐ(ｘi)）に等しいビット列に相当し、かつ既述の手順<4> によれば、本発明に係る第１、４の技術に対応した実施形態と同様に最尤解が確度高く得られる。
さらに、本実施形態では、検査記号を生成する処理は、既述の仮想受信語に含まれるべき検査記号のみについて行われる。
【００５２】
したがって、本実施形態によれば、推定受信語の全てに個別に含まれるべき検査記号が生成される本発明に係る第１、４、７の技術に対応した実施形態に比べて、ハードウエアの規模の削減と構成の簡略化とに併せて、処理量の削減が達成され、かつ最尤復号化の効率が高められる。
なお、本実施形態では、仮想誤り系列テーブル６１には、仮想誤り系列が組織符号の誤り訂正能力の範囲で予め格納されている。
【００５３】
しかし、このような仮想誤り系列テーブル６１については、既述の距離の比較の対象となるべき仮想受信語の数が増加することによる応答性の低下が許容される場合には、受信語ｘに含まれる情報記号について実際に生じる得るビット誤りの全てに対応した仮想誤り系列が予め格納されてもよい。
以下、本発明に係る第３、６の技術に対応した実施形態について説明する。
【００５４】
本実施形態と本発明に係る第２の技術に対応した実施形態との構成の相違点は、図４に示すように、プロセッサ４１Ａに代えてプロセッサ４１Ｂが備えられた点にある。
【００５５】
なお、本実施形態と図３に示すブロック図との対応関係については、入力インタフェース部７１およびプロセッサ４１Ｂは記号抽出手段３１に対応し、プロセッサ４１Ｂは仮想検査記号供給手段３２、仮想正規検査記号生成手段３３および推定手段３４に対応し、プロセッサ４１Ｂおよび出力インタフェース部７４は受信語判定手段３５に対応する。
【００５６】
図１１は、本発明に係る第３、６、７の技術に対応した本実施形態の動作フローチャートである。
図１２は、本発明に係る第３、６、７の技術に対応した本実施形態の動作を説明する図である。
以下、図４、図７、図１０〜図１２および図１４を参照して本発明に係る第３、６の技術に対応した本実施形態の動作を説明する。
【００５７】
プロセッサ４１Ｂの主記憶の特定の記憶領域には、図１０に点線で示すように、受信語ｘに含まれる情報記号について、組織符号の誤り訂正能力の範囲で誤り訂正が可能であるビット誤りの全ての態様を個別に示す誤りパターンに対して、正規の検査記号を示す仮想検査記号のみが予め格納された仮想誤り系列テーブル６１Ａが配置される。
【００５８】
また、プロセッサ４１Ｂは、受信語レジスタ８１の領域管理を行い、その領域管理の下でこの受信語レジスタ８１の空いている領域に、入力インタフェース部７１を介して受信系列として与えられた受信語ｘを順次格納する。
さらに、プロセッサ４１Ｂは、このようにして受信語レジスタ８１に格納された個々の受信語ｘについて、以下の[1]〜[4]に示す一連の処理を行う。
【００５９】
[1] 受信語ｘに含まれる情報記号を抽出し（図１２(1))、組織記号に適応したこの情報記号の正規の検査記号を求める（図１１(1)、図１２(2))。
[2] 仮想誤り系列テーブル６１Ａに格納された個々の仮想検査記号（図１２(3    ))について、上述した正規の検査記号（図１２(4))との和をとることによって複数の推定検査記号を生成し（図１１(2))、これらの推定検査記号を推定受信語レジスタ５１の対応するフィールドに蓄積する（図１１(3)、図１２(5    ))。
【００６０】
[3] 推定受信語レジスタ５１にこのようにして蓄積された全ての推定検査記号について、符号語テーブル８２に格納された受信語ｘに含まれる検査記号との距離を算出し（図１１(4)、図１２(6))、
[4] これらの推定受信語の内、算出された距離が最小である推定受信語を最尤解とすると共に、出力インタフェース部７３を介してその最尤解を復号系列として順次出力する（図１１(5)、図１２(7))。
【００６１】
ところで、既述の受信語ｘと推定受信語との距離ｄについては、２つの符号Ｘ、Ｙ間の距離が関数dist(Ｘ、Ｙ)で示される場合には、
【数９】
0004041219.tif 000010
の式で示される。さらに、上述した組織符号が線形符号である場合には、距離ｄは、
【数１０】
0004041219.tif 000011
の式で示される。しかし、上式の第１項の値は、ｅn、すなわち実際に生じる誤りを示す誤りパターンのみによって決定され、かつ既知である。
【００６２】
すなわち、距離ｄは、ハミング距離として与えられる場合には、ｅn として与えられるビットの内、論理値が「１」であるビットの数（ユークリッド距離として与えられるべき場合にはｎ1/2)として与えられる値value(ｅn)に対して、
【数１１】
0004041219.tif 000012
の式で示される。
【００６３】
したがって、上述した手順[3] で算出される距離は、上式の第二項の値に相当するので、value（ｅn）の値が定数である場合には、大小関係を確度高く示す「最尤復号化の基準」となる。
このように本実施形態によれば、検査記号を生成する処理は、本発明に係る第２、５の技術に対応した実施形態と同様にして仮想受信語に含まれるべき検査記号のみについて行われ、かつ上述した距離の算出および比較は、検査記号のみについて行われる。
【００６４】
したがって、これらの距離の算出および比較が受信語に含まれる情報記号についても行われる本発明に係る第１、２、４、５の技術に対応した実施形態に比べて、ハードウエアの規模の削減と構成の簡略化とに併せて、処理量の削減が達成され、かつ最尤復号化の効率が高められる。
なお、本実施形態では、仮想誤り系列テーブル６１Ａには、仮想検査記号が誤り訂正能力の範囲で予め格納されている。
【００６５】
しかし、このような仮想誤り系列テーブル６１Ａについては、既述の距離の比較の対象となるべき仮想検査記号の数が増加することによる応答性の低下が許容される場合には、受信語ｘに含まれる情報記号について実際に生じる得るビット誤りの全てに対応した仮想検査記号が予め格納されてもよい。
また、本実施形態では、value（ｅn）の値が一定であるために検査記号のみの距離が最尤復号化の基準として算出されているが、その値が一定でない場合であっても、例えば、情報記号の全ての態様について  ビット誤りパターンｅn 毎に予め求められた値が登録されたテーブルが距離ｄの算出の過程で適宜参照されることによって、その距離ｄの算出にかかわる演算手順の煩雑化が回避されてもよい。
【００６６】
以下、図４〜図６、図８、図９、図１１および図１２を参照して本発明に係る第７の技術に対応した本実施形態の動作を説明する。
本実施形態では、最小距離ｋが既知の値であって、受信語ｘに対する（ハミング）距離がｋ以下である符号の数が「１」である組織符号が適用される。
【００６７】
プロセッサ４１、４１Ａ、４１Ｂは、それぞれこのような最小距離ｋが予め与えられ、かつ算出した（図５(4)、図８(4)、図１１(3))距離がその最小距離ｋ以下であるか否かを判別する。
さらに、プロセッサ４１、４１Ａ、４１Ｂは、その判別の結果が偽である場合には、既述の通りの処理を行うことによって最尤復号化処理を行うが、反対に真である場合には、その判別の結果が得られた推定受信語を最尤解として出力インタフェース部７３を介して出力すると共に、該当する受信語に関する限り、後続する推定受信語に対する距離の算出と比較とを省略する（図８(a)、図８(a)、図１１(a))。
【００６８】
すなわち、本実施形態では、適用された組織符号に固有の最小距離ｋに基づいて距離の算出および比較にかかわる処理が的確に省略されるので、本発明に係る第１〜６の技術に対応した実施形態に比べて最尤復号化処理に要する処理量が削減され、かつ最尤解が精度よく効率的に得られる。
なお、本実施形態では、本発明に係る第３、６の技術に対応した実施形態に本発明に係る第７の技術が適用されているが、この本発明に係る第７の技術は、図５および図８に点線で示すように、本発明に係る第１、２、４、５の技術に対応した実施形態にも同様に適用可能である。
【００６９】
また、本発明に係る第２、３、５、６の技術に対応した各実施形態では、仮想誤り系列テーブル６１、６１Ａに予め格納された誤りパターンとその誤りパターンに個別に対応した仮想検査記号とが適宜参照されているが、これらの誤りパターンおよび仮想検査記号については、最尤復号化の効率の低下や所要する処理量の増加が許容されるならば、その最尤復号化の対象となるべき組織符号に適応して適宜あるいは一括して生成されてもよい。
【００７０】
さらに、上述した各実施形態では、最尤復号化を実現する処理が専用のプロセッサ４１、４１Ａ、４１Ｂによって行われているが、これらの処理の一部もしくは全ては、呼設定、チャネル設定その他の何らかの処理を行うプロセッサの余剰の処理量が適用されることによって行われてもよく、ＤＳＰが行う信号処理、あるいは専用のハードウエア（ＬＳＩ化されてもよい。）が行う演算として行われてもよい。
【００７１】
また、このような処理を実現するソフトウエアや専用のハードウエアについては、如何なる形態で負荷分散や機能分散がはかられてもよい。
さらに、上述した各実施形態については、適用されるべき装置およびシステムが何ら示されていないが、本願発明は、通信系や伝送系に限らず、ハードディスクドライブのように記録媒体に組織符号化されて記録された情報を読み取る装置その他の多様な装置に適用可能である。
【００７２】
【発明の効果】
上述したように本発明に係る第１の技術では、最尤復号に要する処理量の削減がはかられる。
また、本発明に係る第２の技術では、本発明に係る第１の技術に比べて、処理量の削減がはかられる。
【００７３】
さらに、本発明に係る第３の技術では、復号化の確度が低下することなく本発明に係る第１、２の技術より処理量の削減がはかられる。
また、本発明に係る第４〜６の技術では、それぞれ本発明に係る第１〜３の技術に比べて、処理量の削減がはかられる。
さらに、本発明に係る第７の技術では、本発明に係る第１〜６の技術に比べて処理の効率化がはかられる。
【００７４】
したがって、これらの発明が適用されたシステムや装置では、信頼性が低下することなく、安価に多様な組織符号に対する柔軟な適応が可能となり、かつ応答性および性能が高められる。
【図面の簡単な説明】
【図１】  本発明に係る第１、４、７の技術の原理ブロック図である。
【図２】  本発明に係る第２、５、７の技術の原理ブロック図である。
【図３】  本発明に係る第３、６、７の技術の原理ブロック図である。
【図４】  本発明に係る第１〜７の技術に対応した実施形態を示す図である。
【図５】  本発明に係る第１、４、７の技術に対応した本実施形態の動作フローチャートである。
【図６】  本発明に係る第１、４、７の技術に対応した本実施形態の動作を説明する図である。
【図７】  推定受信語レジスタの構成を示す図である。
【図８】  本発明に係る第２、５、７の技術に対応した本実施形態の動作フローチャートである。
【図９】  本発明に係る第２、５、７の技術に対応した本実施形態の動作を説明する図である。
【図１０】  仮想誤り系列テーブルの構成を示す図である。
【図１１】  本発明に係る第３、６、７の技術に対応した本実施形態の動作フローチャートである。
【図１２】  本発明に係る第３、６、７の技術に対応した本実施形態の動作を説明する図である。
【図１３】  組織符号を最尤復号化する最尤復号器の構成例を示す図である。
【図１４】  受信語レジスタの構成を示す図である。
【図１５】  符号語テーブルの構成を示す図である。
【図１】
0004041219.tif 000013
【図２】
0004041219.tif 000014
【図３】
0004041219.tif 000015
【図４】
0004041219.tif 000016
【図５】
0004041219.tif 000017
【図６】
0004041219.tif 000018
【図７】
0004041219.tif 000019
【図８】
0004041219.tif 000020
【図９】
0004041219.tif 000021
【図１０】
0004041219.tif 000022
【図１１】
0004041219.tif 000023
【図１２】
0004041219.tif 000024
【図１３】
0004041219.tif 000025
【図１４】
0004041219.tif 000026
【図１５】
0004041219.tif 000027