(57)【要約】【課題】トレリス線図の所定の時点における複数のステートの中に、同じパスメトリックを有するステートや、あるいは似通ったパスメトリックを有するステートが多数存在するような場合にも最尤のパスに基づいた復号化を実施することができるビタビ復号器を提供することを目的とする。【解決手段】畳み込み符号化されて伝送された符号化信号のうちの復号後のデータビット長よりも短いトレースバック長連続する信号の、トレリス線図上の複数のパスのパスメトリックを求めるＡＣＳ回路２２２と、このパスメトリックに基づいて複数のパスのうちのいずれか１つのパスを選択するとともに、このパスメトリックに基づいてはいずれか１つのパスを選択することが不能な場合に、直前のパスメトリックに基づいていずれか１つのパスを選択するＭＡＸパスメトリック信頼度判定器２２５とを備えた。【選択図】        図５
2004193892.tif 000002
【特許請求の範囲】
【請求項１】
畳み込み符号化されて伝送された符号化信号を、復号後のデータビット長よりも短いトレースバック長を単位として復号化するビタビ復号器において、
前記符号化信号のうちの前記トレースバック長連続する信号の、トレリス線図上の複数のパスのパスメトリックを求めるパスメトリック算出部と、
前記パスメトリック算出部で算出されたパスメトリックに基づいて前記複数のパスのうちのいずれか１つのパスを選択するとともに、該パスメトリックに基づいてはいずれか１つのパスを選択することが不能な場合に、該パスメトリックから直前のブランチメトリックを除いた直前のパスメトリックに基づいていずれか１つのパスを選択するパス選択部とを備えたことを特徴とするビタビ復号器。
【請求項２】
前記パス選択部は、前記直前のブランチメトリックの信頼度の高低を判定し、該信頼度が低い場合に前記直前のパスメトリックに基づいていずれか１つのパスを選択するものであることを特徴とする請求項１記載のビタビ復号器。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、畳み込み符号化されて伝送された符号化信号を、復号語のデータビット長よりも短いトレースバック長を単位として復号化するビタビ復号器に関する。
【０００２】
【従来の技術】
デジタル信号で表された情報を伝送する場合、伝送途中のノイズなどの影響により、正確な情報が伝送されなくなることが予想される。従来、伝送途中にノイズなどの影響をうけても、情報を正確に伝送できるようにするために、情報を表すデジタル信号を各種アルゴリズムを使用して符号語に変換することにより冗長性を持たせた符号化信号を生成し、この符号化信号を伝送することが実施されている。また、受信側では伝送されてきた符号化信号を復号化することにより、符号化信号の一部がノイズなど影響により変わってしまっていたとしても、正確な情報を得ることができる。
【０００３】
送信側で符号語を生成する符号器の１例として、畳み込み符号器があり、畳み込み符号器によって畳み込み符号化されて伝送されて来た符号化信号を、受信側で復号化する復号器として、従来からビタビ復号器が利用されている。
【０００４】
図１は、畳み込み符号器とビタビ復号器の関係を模式的に示す図である。
【０００５】
図１に示されている畳み込み符号器１００には、伝送される情報を１ビットの情報信号の羅列で表現した情報信号系列ａ１ａ２ａ３…が入力される。
【０００６】
畳み込み符号器１００に入力された情報信号系列ａ１ａ２ａ３…は、１ビット毎に所定数のビットからなる符号語に変換され、この符号語の系列である符号化信号が畳み込み符号器１００から出力される。この符号化信号は伝送路を経由してビタビ復号器２００に入力される。ビタビ復号器２００は、伝送路上のノイズの影響を受けている可能性のある符号化信号を復号化し、畳み込み符号器１００によって符号化される以前の情報信号系列と同じ内容の復号信号系列ａ１ａ２ａ３…を出力する。
【０００７】
ここで、符号化信号を復号化するにあたって、この符号化信号を生成した畳み込み符号器１００に対応するトレリス線図（図３にて後述）を利用するビタビアルゴリズムと呼ばれる復号化プロセスを、デジタル回路で実現したものがビタビ復号器２００である。
【０００８】
上記のトレリス線図には、所定のデータビット長の情報信号に基づいて畳み込み符号器１００が生成するであろう符号化信号の全てが、畳み込み符号器１００の回路構成に基づいて求められ示されている。このトレリス線図に示されている符号化信号の中から、ビタビ復号器２００が受け取った符号化信号と最も近いデータ構造を有する符号化信号を選択し、この選択された符号化信号から、符号化される以前の情報信号を推定するという復号化プロセスがビタビアルゴリズムである。
【０００９】
前述したように、ビタビ復号器２００が受け取る符号化信号はノイズなど影響により一部が変わってしまっている可能性がある。一方、トレリス線図に示されている符号化信号は、畳み込み符号器から理論的に求められたものであるから正確である。ビタビアルゴリズムでは、トレリス線図に示されている正確な符号化信号に基づいて情報信号を推定するので、伝送途中のノイズなどの影響が排除された正確な復号化を実施することができる。
【００１０】
ここで、ビタビ復号器について説明する前に、まず畳み込み符号器について説明する。
【００１１】
図２は、畳み込み符号器の一例を示すブロック図である。
【００１２】
図２に示されている畳み込み符号器１１０は、互いに直列に接続された２つのシフトレジスタ１１１，１１２と、排他的論理和を実行する５つの演算器１１３，１１４，１１５，１１６，１１７とで構成されている。
【００１３】
図２では、畳み込み符号器１１０のシフトレジスタ１１１，１１２には既に１番目の情報信号ａ１と２番目の情報信号ａ２が格納されており、３番目の情報信号ａ３が入力された時点での３ビットの符号語Ｇ１Ｇ２Ｇ３が出力された、２時点目の状態にある畳み込み符号器１１０が示されている。
【００１４】
図２に示されている畳み込み符号器１１０のステートはａ２ａ１である。この畳み込み符号器１１０のシフトレジスタ１１１に情報信号ａ３が格納されると同時に、１段目のシフトレジスタ１１１からの情報信号ａ２が２段目のシフトレジスタ１１２に格納される。その後入力される新たな情報信号（図示せず）と２つの情報信号ａ２ａ３に基づいて新たな３ビットの符号語が生成され出力される。つまり、情報信号ａ３の畳み込み符号器１１０のシフトレジスタ１１１への格納により、畳み込み符号器１１０のステートは、ａ２ａ１からａ３ａ２に遷移する。
【００１５】
以上に説明したように図２に示されている畳み込み符号器１１０では、情報信号が１ビット入力される毎に３ビットの符号語が１つ生成されるとともに、そのステートが遷移する。
【００１６】
次に、トレリス線図について説明する。
【００１７】
図３は、図２に示す畳み込み符号器におけるトレリス線図である。
【００１８】
図３に示すトレリス線図には、７ビットのデータビット長の情報信号系列に基づいて畳み込み符号器１１０（図２参照）が生成する符号語とそのときのステートの遷移が全て示されている
畳み込み符号器１１０のステートは２つのビットの組み合わせで表現される。従って、畳み込み符号器１１０には、４通りのステート００，１０，０１，１１がある。また図３の例では、０時点目に初期状態にあるときの、畳み込み符号器１１０の初期ステートは００に設定されている。
【００１９】
また、図３の例では、畳み込み符号器１１０に入力される情報信号系列のデータビット長は７ビットである。従って、この情報信号系列の最後の情報信号が入力され、この情報信号に基づいて畳み込み符号器１１０が最後の符号語の生成を完了する時点は７時点目である。また、図３の例では、畳み込み符号器１１０が符号化信号の生成を完了したときにそのステートが初期ステートと同じ００となるように、情報信号系列の末尾の２ビットが００に設定されている。従って畳み込み符号器１１０の７時点目のステートは００である。
【００２０】
図３に示すトレリス線図では、各時点のステートを黒丸で表し、ある時点のステートから次の時点のステートへの遷移を矢印で表している。また個々の矢印の近傍には、その矢印が示すステートの遷移に対応する符号語が付記されている。
【００２１】
ここで、個々の矢印をブランチ、ある時点のステートから１時点以上離れた別の時点のステートへの遷移をブランチの組み合わせで表現したものをパスと称する。例えば、０時点目のステート００から１時点目のステート１０への遷移は、ブランチｂ１で表される。また、０時点目のステート００から２時点目のステート１１への遷移は、２本のブランチｂ１，ｂ２を組み合わせたパスＰで表される。また、各ブランチに付記されている符号語は、畳み込み符号器１１０の回路構成から推定されたものであるので、ここでは推定符号語と称する。
【００２２】
さらに、説明の便宜上、トレリス線図において、ある時点のステートに向かってくるブランチをその時点のブランチと称する。例えば、図３に示されているトレリス線図において、１時点目のステート００に向かってくるブランチｂ３と、１時点目のステート１０に向かってくるブランチｂ１は１時点目のブランチである。
【００２３】
このようなトレリス線図を利用し、符号化信号を復号化する復号化プロセスがビタビアルゴリズムであり、ビタビアルゴリズムによる復号化をデジタル回路で実現したものがビタビ復号器である。
【００２４】
ここで、畳み込み符号化されて伝送された符号化信号に対して、復号後のデータビット長よりも短いトレースバック（図４にて後述）長を単位としてビタビアルゴリズムによる復号化を施すビタビ復号器が提案されている（例えば、特許文献１参照。）。
【００２５】
【特許文献１】
特開平１１−３５５１５０号公報（段落番号００１１−００７１、第６図、第１１図）
【００２６】
【発明が解決しようとする課題】
図４は、特許文献１に示されたビタビ復号器を示すブロック図である。
【００２７】
ここで、図４に示されているビタビ復号器２１０を説明するにあたり、符号化信号を生成する符号器は図２に示された畳み込み符号器１１０であり、ビタビ復号器２１０で実現されている復号化プロセスには、畳み込み符号器１１０に対応する図３に示されたトレリス線図が利用されているものとする。これは後述する図５の説明においても同様である。
【００２８】
図４に示すビタビ復号器２１０に伝送される符号化信号は、畳み込み符号器１１０によって生成された符号語が、生成された時点順に連なったものである。この符号化信号がビタビ復号器２１０のブランチメトリック計算器２１１に入力される。ブランチメトリック計算器２１１が実行するブランチメトリック計算プロセスでは、符号化信号を構成する符号語が１つ入力される毎に、この符号語が生成された時点と、トレリス線図（図３参照）の時点が一致するブランチのブランチメトリックが計算される。ここで、ブランチメトリックとは、ブランチに付記されている推定符号語と、ビタビ復号器２１０に入力された符号語とを桁毎に比較したとき、対応する桁の値が一致しないものの個数である。例えば、１時点目に生成された符号語が００１であったとする。トレリス線図の１時点目には２本のブランチｂ１，ｂ３がある。ブランチｂ１に付記されている推定符号語は１１１である。推定符号語１１１と符号語００１とを桁毎に比較すると、対応する桁の値が一致しないものの個数は２個であるから、ブランチｂ１のブランチメトリックは２になる。また同様に計算すると、ブランチｂ３のブランチメトリックは１になる。ブランチメトリック計算器２１１で得られたブランチメトリックを示す情報は、ＡＣＳ（Ａｄｄ  Ｃｏｍｐａｒｅ  Ｓｅｌｅｃｔ）回路２１２に供給される。
【００２９】
ＡＣＳ回路２１２では、ブランチメトリック計算器２１１から供給された、ブランチメトリックを示す情報に基づいて、以下のＡＣＳプロセスを実行する。
【００３０】
まずステートのパスメトリックが計算される。ここで、ステートのパスメトリックとは、トレリス線図（図３参照）上のあるステートに至るパスに対して、このパスを構成するブランチのブランチメトリックの累積値を計算したものである。ＡＣＳプロセスでは、あるステートにつながるブランチのブランチメトリックを示す情報がブランチメトリック計算器２１１から供給されたとき、トレリス線図上で、このブランチによって結ばれる１時点前のステートのパスメトリックを示す情報がパスメトリックメモリ２１３から読み出される。この情報が示す１時点前のステートのパスメトリックに、ブランチメトリック計算器２１１から供給された情報が示すブランチメトリックを加えてパスメトリックを計算する。計算されたパスメトリックを示す情報は、パスメトリックメモリ２１３に格納され、次の時点でのパスメトリックの計算に用いられる。
【００３１】
ここで、例えば、トレリス線図の３時点目のステート００には、２時点目のステート００からのブランチｂ４と、２時点目のステート０１からのブランチｂ５との２本のブランチがつながっている。これは０時点目のステート００から３時点目のステート００に至るパスには、２時点目のステート００を経由するパスと、２時点目のステート０１を経由するパスとの２種類のパスが存在することを意味する。このように、あるステートに至るパスが２種類存在するときには、ＡＣＳプロセスでは、２種類のパスに対するパスメトリックを計算し、その値が小さい方のパスをこのステートに至るパスとして選択する。ここで、選択されたパスを生き残りパスと称する。この生き残りパスを示す情報は、生き残りパスメモリ２１４に格納される。また、生き残りパスのパスメトリックを示す情報がパスメトリックメモリ２１３に格納される。
【００３２】
ＡＣＳプロセスでは、パスメトリックの計算とパスの選択を、トレリス線図の各時点における全てのステートに対して実施する。
【００３３】
ＡＣＳ回路２１２において実行されているＡＣＳプロセスが、トレリス線図の所定の時点まで実行されると、ＭＡＸパスメトリック判定器２１５は、その時点におけるステートの中から、最も小さいパスメトリックを有するステートを１つ選択するという選択プロセスを実行する。この選択プロセスによって得られたステートを示す情報がトレースバック回路２１６に供給される。
【００３４】
ＭＡＸパスメトリック判定器２１５から、ステートを示す情報を受け取ったトレースバック回路２１６は、このステートに至るパスを示す情報を、生き残りパスメモリ２１４から読み出す。
【００３５】
ここで、この情報が示すパスに従って、このパスを構成するブランチに付記されている推定符号語を羅列した推定符号語列は、トレリス線図において、０時点目から上記の所定の時点までの間に示されている全てのパスに対して同様に作成される推定符号語列の中で、ビタビ復号器２１０に伝送されて来た符号化信号に最も近いデータ構造を有する推定符号語列である。ここで、この推定符号語列に対応するパスを最尤のパスと称する。
【００３６】
トレースバック回路２１６は、この最尤のパスに基づいて、畳み込み符号器１１０に入力された情報信号系列を推定するプロセスを実行し、推定された結果を復号信号系列として出力する。推定は１時点目の直前に入力された情報信号ａ１から時点順に、ＭＡＸパスメトリック判定器２１５によってステートの選択が行なわれた所定の時点まで行なわれる。この推定プロセスをトレースバックと呼び、１回のトレースバックによって得られる復号信号系列のデータビット長をトレースバック長と称する。
【００３７】
また、ビタビ復号器２１０の各部の動作は制御回路２１７によって制御されている。
【００３８】
ここで、本来のビタビアルゴリズムによる復号化では、ＡＣＳプロセスにおけるパスメトリックの計算とパスの選択をトレリス線図（図３参照）の最後の時点まで繰り返すことにより、０時点目のステート００から最終時点のステート００に至る最尤のパスを１本決定する。しかしながら、この本来のビタビアルゴリズムによる復号化をデジタル回路で実現しようとすると、復号化中に得られるパスメトリックや生き残りパスの情報などを格納しておくパスメトリックメモリ２１３や生き残りパスメモリ２１４として大規模なメモリ回路が必要となってしまう。そこで、図４に示されているビタビ復号器２１０では、ＭＡＸパスメトリック判定器２１５によって、ＡＣＳ回路２１２におけるＡＣＳプロセスを所定の時点で１度中断し、復号後のデータビット長よりも短いトレースバック長を単位として復号化を行なうことにより、パスメトリックメモリ２１３や生き残りパスメモリ２１４の回路規模を抑えている。
【００３９】
図４に示すビタビ復号器２１０では、トレースバックが終了すると、ＡＣＳプロセスを再開する。ここで、再開時の初期ステートは、トレースバックの前に、ＭＡＸパスメトリック判定器２１５で実行された選択プロセスによって得られたステートである。このようにして、ビタビ復号器２１０はトレースバック長単位の復号化を繰り返し、全ての情報信号系列の復号化を行なう。
【００４０】
以上に説明したように、図４に示されているビタビ復号器２１０では、ＭＡＸパスメトリック判定器２１５で実行された選択プロセスによって、所定の時点における複数のステートの中から、最も小さいパスメトリックを有するステートを１つ選択し、このステートに至るパスを最尤のパスとして、この最尤のパスに基づいてトレースバックを実行している。
【００４１】
しかしながら、図４に示すビタビ復号器２１０には、上記の所定の時点における複数のステートの中に、同じパスメトリックを有するステートや、あるいは似通ったパスメトリックを有するステートが多数存在するような場合、間違ったパスを選択し、このパスに基づいて間違った復号化を行なってしまうおそれがある。
【００４２】
本発明は、上記事情に鑑み、トレリス線図の所定の時点における複数のステートの中に、同じパスメトリックを有するステートや、あるいは似通ったパスメトリックを有するステートが多数存在するような場合にも、最尤のパスに基づいた復号化を実行することができるビタビ復号器を提供することを目的とする。
【００４３】
【課題を解決するための手段】
上記目的を達成する本発明のビタビ復号器は、畳み込み符号化されて伝送された符号化信号のうちの復号後のデータビット長よりも短いトレースバック長連続する信号の、トレリス線図上の複数のパスのパスメトリックを求めるパスメトリック算出部と、このパスメトリック算出部で算出されたパスメトリックに基づいて複数のパスのうちのいずれか１つのパスを選択するとともに、このパスメトリックに基づいてはいずれか１つのパスを選択することが不能な場合に、このパスメトリックから直前のブランチメトリックを除いた直前のパスメトリックに基づいていずれか１つのパスを選択するパス選択部とを備えたことを特徴とする。
【００４４】
本発明のビタビ復号器は、トレリス線図上の複数のパスの中から、パスのパスメトリックから直前のブランチメトリックを除いた直前のパスメトリックに基づいていずれか１つのパスを選択するパス選択部を備えている。従って、例えば同じパスメトリックを有するパスや、あるいは似通ったパスメトリックを有するパスが多数存在し、これらのパスメトリックに基づいては、トレリス線図上の複数のパスの中から最尤のパスを１つ選択することが不能な場合にも、上記のパス選択部によって最尤のパスを選択することができる。
【００４５】
ここで、本発明のビタビ復号器において、上記パス選択部は、上記直前のブランチメトリックの信頼度の高低を判定し、この信頼度が低い場合に上記直前のパスメトリックに基づいていずれか１つのパスを選択するものであることが好ましい。
【００４６】
このようなビタビ復号器では、上記直前のブランチメトリックの信頼度が低い場合にのみ、直前のパスメトリックに基づいたパスの選択を実施するので、復号化処理の効率化が図られる。
【００４７】
【発明の実施の形態】
以下、本発明の実施形態について説明する。
【００４８】
図５は、本発明のビタビ復号器の一実施形態を示す図である。
【００４９】
図５に示されているビタビ復号器２２０は、ブランチメトリック計算プロセスを実行するブランチメトリック計算器２２１、ＡＣＳプロセスを実行するＡＣＳ回路２２２、パスメトリックを示す情報を格納するパスメトリックメモリ２２３、生き残りパスを示す情報を格納する生き残りパスメモリ２２４、トレリス線図の所定の時点の複数のステートの中からいずれか１つのステートを選択する選択プロセスを実行するＭＡＸパスメトリック信頼度判定器２２５、トレースバックを実行するトレースバック回路２２６、およびビタビ復号器２２０の各部の動作を制御する制御回路２２７で構成されている。
【００５０】
ここで、図５に示されているビタビ復号器２２０の構成や動作は、ＭＡＸパスメトリック信頼度判定器２２５を除いて、図４に示すビタビ復号器２１０の構成や動作と同一である。そこで、ここでは図４に示されたビタビ復号器２１０との同一点については説明を省略し、相違点であるＭＡＸパスメトリック信頼度判定器２２５について説明する。
【００５１】
ＭＡＸパスメトリック信頼度判定器２２５は、ＡＣＳ回路２２２におけるＡＣＳプロセスが、トレリス線図上でトレースバック長に対応した所定の時点まで終了したとき、その時点における複数のステートの中から、以下の手順を経ていずれか１つのステートを選択する選択プロセスを実行する。
【００５２】
まず、複数のステートの中で、最小のパスメトリックを有するステートを選択する。
【００５３】
次に、この最小のパスメトリックに所定の数値を加算した上限値を計算する。さらに、複数のステートの中から、上記の最小のパスメトリックから上記の上限値までの範囲に入るパスメトリックを有するステートを選択する。
【００５４】
選択されたステートが１つである場合には、このステートを示す情報をトレースバック回路２２６に出力する。
【００５５】
選択されたステートが複数である場合には、これらのステートにつながるブランチのブランチメトリックを、ブランチメトリック計算器２２１から読み出し、これらのブランチメトリックの信頼度を判定する。判定の結果、この信頼度が高いと判定された場合には、選択された複数のステートの中で、最小のパスメトリックを有するステートを選択する。また、この最小のパスメトリックを有するステートが複数存在している場合には、これらの同じパスメトリックを有する複数のステートの中から、所定の規則によって１つのステートを選択し、このステートを示す情報をトレースバック回路２２６に供給する。
【００５６】
ブランチメトリックの信頼度の判定の結果、信頼度が低いと判定された場合には、まず、選択された複数のステートそれぞれに対して、これらのステートのパスメトリックから直前のブランチメトリックを除いた１時点前のパスメトリックを、パスメトリックメモリ２２３から読み出す。次に、選択された複数のステートの中から、１時点前のパスメトリックが最小となるステートを１つ選択する。選択された１つのステートを示す情報がトレースバック回路２２６に出力される。
【００５７】
このように、ＭＡＸパスメトリック信頼度判定器２２５は、トレリス線図の所定の時点における複数のステートの中に、同じパスメトリックを有するステートや、あるいは似通ったパスメトリックを有するステートが多数存在するような場合にも、１つのステートを選択することができる。
【００５８】
本実施形態のビタビ復号器２２０は、このようにして選択されたステートにつながる最尤のパスに基づいてトレースバックを行ない、復号信号系列を出力するものであるため、復号利得の向上が可能となる。
【００５９】
【発明の効果】
以上説明したように、本発明のビタビ復号器によれば、トレリス線図の所定の時点における複数のステートの中に、同じパスメトリックを有するステートや、あるいは似通ったパスメトリックを有するステートが多数存在するような場合にも、最尤のパスに基づいた復号化を実施することができる。従って、復号利得の向上が可能となる。
【図面の簡単な説明】
【図１】畳み込み符号器とビタビ復号器の関係を模式的に示す図である。
【図２】畳み込み符号器の１例を示すブロック図である。
【図３】畳み込み符号器に対応するトレリス線図である。
【図４】従来のビタビ復号器を示すブロック図である。
【図５】本発明のビタビ復号器の一実施形態を示す図である。
【符号の説明】
１００，１１０    畳み込み符号器
１１１，１１２    シフトレジスタ
１１３，１１４，１１５，１１６，１１７    演算器
２００，２１０，２２０    ビタビ符号器
２１１，２２１    ブランチメトリック計算器
２１２，２２２    ＡＣＳ回路
２１３，２２３    パスメトリックメモリ
２１４，２２４    生き残りパスメモリ
２１５    ＭＡＸパスメトリック判定器
２１６，２２６    トレースバック回路
２１７，２２７    制御回路
２２５    ＭＡＸパスメトリック信頼度判定器
【図１】
2004193892.tif 000003
【図２】
2004193892.tif 000004
【図３】
2004193892.tif 000005
【図４】
2004193892.tif 000006
【図５】
2004193892.tif 000007