(57)【要約】【課題】  複数ビットの復号語を一括して演算処理してビタビ復号する場合に、復号性能が劣化する問題を解決する。【解決手段】  畳み込み符号である復号語について、各ステートでのステートメトリック値とブランチメトリック値に基づいて、最尤パスを選択する処理を、復号語の最後の時刻まで行い、０ステートからトレースバックさせて復号を行う場合に、最尤パスを選択する処理を、ｎビット（ｎは２以上の整数）単位で演算し、復号語の総ビット数がｎの倍数でない場合のトレースバック開始時に、選択の候補となるパスを、ｎビット以下のビット数で候補となり得る特定のパスｐ，ｑなどに制限させるようにした。【選択図】      図４
2005323197.tif 000002
【特許請求の範囲】
【請求項１】
畳み込み符号である復号語について、各ステートでのステートメトリック値とブランチメトリック値に基づいて、最尤パスを選択する処理を、復号語の最後の時刻まで行い、０ステートからトレースバックさせて復号を行うビタビ復号方法において、
前記最尤パスを選択する処理を、ｎビット（ｎは２以上の整数）単位で演算し、
前記復号語の総ビット数がｎの倍数でない場合のトレースバック開始時に、選択の候補となるパスを、前記ｎビット以下のビット数で候補となり得る特定のパスに制限させる
ビタビ復号方法。
【請求項２】
請求項１記載のビタビ復号方法において、
前記ｎの値は２であり、
前記復号語の総ビット数が奇数である場合に、トレースバック開始時に選択の候補となるパスを、１ビットだけトレースバックさせる際に候補となり得る特定のパスに制限させる
ビタビ復号方法。
【請求項３】
請求項１又は２記載のビタビ復号方法において、
前記復号語の総ビット数がｎの倍数でなく、その総ビット数がｎの倍数でないために余るビットの演算時には、ダミービットを付加してｎビットにして演算を行う
ビタビ復号方法。
【請求項４】
畳み込み符号である復号語について、各ステートでのステートメトリック値とブランチメトリック値を計算し、その計算結果に基づいて、最尤パスを選択する処理を、ｎビット（ｎは２以上の整数）単位で行う計算部と、
前記計算部で計算されたステートメトリック値とブランチメトリック値を記憶するメモリと、
復号語の最後の時刻まで前記メモリに記憶された値を使用してトレースバックを行って、復号結果を得ると共に、前記復号語の総ビット数がｎの倍数でない場合のトレースバック開始時に、選択の候補となるパスを、前記ｎビット以下のビット数で候補となり得る特定のパスに制限させる結果出力部とを備えた
ビタビ復号装置。
【請求項５】
請求項４記載のビタビ復号装置において、
前記ｎの値は２であり、
前記結果出力部は、復号語の総ビット数が奇数である場合に、トレースバック開始時に選択の候補となるパスを、１ビットだけトレースバックさせる際に候補となり得る特定のパスに制限させる
ビタビ復号装置。
【請求項６】
請求項４又は５記載のビタビ復号装置において、
前記復号語の総ビット数がｎの倍数でなく、その総ビット数がｎの倍数でないために余るビットの前記計算部での計算時には、ダミービットを付加してｎビットにして計算を行う
ビタビ復号装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、例えば畳み込み符号で符号化されたデータを受信して最尤復号する通信端末に適用して好適なビタビ復号方法及び装置に関する。
【背景技術】
【０００２】
畳み込み符号を復号する方式の１つとして、ビタビ復号方式が知られている。このビタビ復号方式は畳み込み符号に対する最尤復号方式であり、送信側のエンコーダから生成され得る符号系列のなかから、受信された符号系列に最も近い系列（これを最尤パスという）を選ぶことで誤り訂正を行なう。
【０００３】
この最尤パスの選択方法は全てのパスを比較して確かめるのではなく、送信側で生成され得る全ての符号列と受信符号列とのハミング距離を求め、このハミング距離の累積値が最も小さいもの（すなわち、尤度が最も高いもの）を選んで、それ以降は復号に必要なパス（生き残りパス）だけを調べていくことを基本にしており、パスの長さを十分に長くとると、生き残りパスの先（根元）は合流して同じ値になり、どの生き残りパスであっても、遡れば、同じ値を復号していることになる。
【０００４】
したがって、復号誤り率が高くならない程度のパス長を調べ、その長さ分だけ遡った時点のデータを復号語とすることで、正しい復号語を再生することができる。
【０００５】
図６はこのようなビタビ復号方式を用いたビタビ復号装置の一例を示すブロック図である。この図に示すビタビ復号装置は、ブランチメトリック計算回路１０１と、ＡＣＳ(add,compare,select)回路１０２と、正規化回路１０３と、ステートメトリック記憶回路１０４と、パスメモリ回路１０５と、最尤復号判定回路１０６とを備えており、送信側から出力されたデータ（入力データ）が入力されたとき、送信側のエンコーダから生成され得る符号系列のなかから、受信された符号系列に最も近い系列（最尤パス）を選んで、この選択内容に基づいて復号データを生成する。
【０００６】
ブランチメトリック計算回路１０１は入力データが入力されたとき、この入力データのブランチメトリックを計算してこの計算結果（ブランチメトリック）をＡＣＳ回路１０２に供給する。
【０００７】
加算と比較と選択（いわゆるＡＣＳ演算）を行う回路であるＡＣＳ回路１０２は、ブランチメトリック計算回路１０１から供給されるブランチメトリックと、ステートメトリック記憶回路１０４から供給されるステートメトリック（累積和）とに基づいて、ある状態に合流する２本のそれぞれのパスに対し、受信符号とパスとのハミング距離（ブランチメトリック）と、それまでのブランチメトリックの累積和（ステートメトリック）を加算して比較し、この比較結果に基づいて尤度の高いものを選択し、この選択内容をパスメモリ回路１０５に供給するとともに、新たに得られた累積和（ステートメトリック）を正規化回路１０３に供給する。
【０００８】
この場合、拘束長が“３”のとき、各タイムスロット毎に図７の遷移ダイアグラムに示す如くある状態に合流する２本のそれぞれのパスに対し、受信符号とパスとのハミング距離（ブランチメトリック）と、それまでのブランチメトリックの累積和（ステートメトリック）とが加算されて比較され、この比較結果に基づいて尤度の高いものが選択される。
【０００９】
正規化回路１０３はＡＣＳ回路１０２から出力されるステートメトリックを正規化して予め設定されている範囲内の値にし、これをステートメトリック記憶回路１０４に供給する。
【００１０】
ステートメトリック記憶回路１０４は前記正規化回路１０３から供給される正規化されたステートメトリックを記憶し、これを前記ＡＣＳ回路１０２に戻す。
【００１１】
また、パスメモリ回路１０５は、複数のパスメモリセルを備えており、ＡＣＳ回路１０２から出力される選択信号に基づいて各パスメモリセルで入力データを選択して一時記憶することにより、ＡＣＳ回路１０２から出力される選択内容を記憶してこの選択内容を最尤復号判定回路１０６に供給する。
【００１２】
最尤復号判定回路１０６は、パスメモリ回路１０５に記憶されている選択内容に基づいて、最尤のパスを判定して復号データを生成し、これを出力する。
【００１３】
なお、送信側のエンコーダにおいては、符号化されるデータの末尾にテールビットを付加し、符号化が必ずゼロステートで終わるようにすることが一般的である。
【００１４】
特許文献１には、ビタビ復号装置の例についての開示がある。
【特許文献１】特開平５−１３６７００号公報
【発明の開示】
【発明が解決しようとする課題】
【００１５】
ところで、上述したように、トレリス計算の過程で得られるパス選択情報及び各ステートのメトリック値をメモリに格納して、ビタビ復号を行う構成とした場合に、１タイムスロット毎にメモリに格納して演算処理するようにすると、復号結果を得るためにメモリにアクセスする回数が多く、復号演算の高速化を阻害する要因になっている。このため、上述した特許文献１では、トレリス演算を複数の時間（即ち複数ビットの復号語）にわたって一括して行うことが提案されている。
【００１６】
例えば、トレリス演算を２ビットの復号語にわたって一括して行うようにする。このように一括してトレリス演算を行うことで、それだけメモリにアクセスする回数が少なくなり、復号演算の高速化につながる。
【００１７】
ところが、このように複数ビットの復号語を一括して演算処理するようにすると、復号状態によっては、復号性能が劣化する場合がある。具体的には、例えば復号語の総ビット数が、１回のＡＣＳ演算の復号語の倍数でない場合に、復号性能が劣化する場合がある。
【００１８】
以下、このことを図８、図９を参照して説明する。図８は、１回のＡＣＳ演算で処理する復号語のビット数が１の場合（即ち複数ビットの復号語を一括して演算処理しない場合）の、一般的なトレリス線図である。ここでは、拘束長＝３（４ステート）としてあり、時刻ｔにおける４つの状態［０］，［１］，［２］，［３］から、時刻ｔ＋２で状態［０］になるパスとしては、時刻ｔから時刻ｔ＋１へのパスとして、パスａ，ｂ，ｃ，ｄがあり、時刻ｔ＋１から時刻ｔ＋２へのパスとして、パスｅ，ｆがある。図８において、時刻ｔ＋２がトレースバックの開始点であるとすると、時刻ｔ＋２での状態［０］から、これらのパスａ〜ｆの何れかを選択することを、各ステートのメトリック値に基づいて行うことで、正しく復号される。
【００１９】
次に、１回のＡＣＳ演算で処理する復号語のビット数が２の場合の例を、図９に示す。この場合には、時刻ｔ＋２をトレースバックの開始点であるとすると、１回のＡＣＳ演算で、時刻ｔの４つの状態［０］，［１］，［２］，［３］の何れかが選択されることになる。
【００２０】
ここで、時刻ｔが偶数である場合には、図８に示した１ビットずつのトレースバックと、図９に示した２ビットずつのトレースバックとで、復号結果は全く等価である。しかしながら、図９の２ビット処理を行う構成の場合には、パスメモリが必ず２ビット単位で追記されるので、復号語の総ビット数が奇数の場合には、パンクチャビット相当のダミービットを１ビット付加して、処理の単位を偶数にする等の対策が必要になる。即ち、本来の時刻ｔ＋１のパスメモリから行うトレースバック処理を、時刻ｔ＋２から行うことになる。
【００２１】
このように、時刻ｔ＋１のパスメモリから行うはずのトレースバック処理を、時刻ｔ＋２から行うようにすると、本来選択されるはずのないパスが選択される可能性があり、そのような場合に復号性能が劣化してしまう。
【００２２】
本発明はかかる点に鑑みてなされたものであり、複数ビットの復号語を一括して演算処理してビタビ復号する場合に、復号性能が劣化する問題を解決することを目的とする。
【課題を解決するための手段】
【００２３】
本発明は、畳み込み符号である復号語について、各ステートでのステートメトリック値とブランチメトリック値に基づいて、最尤パスを選択する処理を、復号語の最後の時刻まで行い、０ステートからトレースバックさせて復号を行う場合に、最尤パスを選択する処理を、ｎビット（ｎは２以上の整数）単位で演算し、復号語の総ビット数がｎの倍数でない場合のトレースバック開始時に、選択の候補となるパスを、ｎビット以下のビット数で候補となり得る特定のパスに制限させるようにしたものである。
【００２４】
このようにしたことで、復号処理を少ないメモリアクセスで行える複数ビット単位で処理するようにした場合であっても、その処理単位の複数ビット以下のビット数を扱う必要がある際には、その処理単位の複数ビット以下のビット数での精度でパスが選択されることになる。
【発明の効果】
【００２５】
本発明によると、復号処理を少ないメモリアクセスで行える複数ビット単位で処理するようにした場合であっても、その処理単位の複数ビット以下のビット数を扱う必要がある際には、その処理単位の複数ビット以下のビット数での精度でパスが選択されることになり、誤ったパスを選択することがなくなる。従って、高速処理などが可能な複数ビット単位でビタビ復号処理を行う場合であっても、処理精度を１ビット単位で行う場合と同じに維持できる。
【発明を実施するための最良の形態】
【００２６】
以下、本発明の一実施の形態を、図１〜図５を参照して説明する。
本例においては、携帯電話端末などの各種通信機器で、畳み込み符号を受信して復号する場合に適用したものである。即ち、例えば図１に示すように、アンテナ１が接続されたＲＦ（高周波）部２で、所定の周波数帯の信号を受信して、その受信信号を復調器３に供給して復調して、畳み込み符号で符号化された復調信号を得る。この復調信号を復号器４に供給して復号する。本例においては、復号器４としてビタビ復号器を使用し、ビタビ復号を行う。ビタビ復号器４の具体的構成については、後述する。
【００２７】
ビタビ復号器４で復号された結果のデータは、受信データ処理部５に供給して、受信データのデータ処理を行う。データ処理部では、例えばエラー訂正などについても必要により行う。
【００２８】
図２は、このような受信系が備えるビタビ復号器４の本例の構成例を示した図である。ここでは、拘束長＝３（４ステート）の畳み込み符号の復号を行うものとする。図２に従って構成を説明すると、受信信号入力端子１１に得られる受信信号を、ＡＣＳ計算部１２に供給する。ＡＣＳ計算部１２は、加算と比較と選択（いわゆるＡＣＳ演算）を行う回路である。
【００２９】
具体的には、ＡＣＳ計算部１２で、受信信号のブランチメトリックを計算し、そのブランチメトリックと、メモリに記憶されたステートメトリック（累積和）とに基づいて、ある状態に合流する２本のそれぞれのパスに対し、受信符号とパスとのハミング距離（ブランチメトリック）と、それまでのブランチメトリックの累積和（ステートメトリック）を加算して比較し、この比較結果に基づいて尤度の高いものを選択し、この選択内容をメモリ（パスメモリ）に記憶させるとともに、新たに得られた累積和（ステートメトリック）を正規化してメモリ（ステートメトリックメモリ）に記憶させる。ＡＣＳ計算部１２での計算処理は、制御部３０内のトレリス計算処理制御部３１からの制御信号３１ａによる制御で実行される。
【００３０】
ＡＣＳ計算部１２での結果を記憶するメモリとしては、ここでは４ステートの畳み込み符号を扱うので、図２に示すように、ステート数に対応した第１〜第４の４つのメモリ２１〜２４を用意し、それぞれのメモリ２１〜２４に、パスメモリ２１ａ〜２４ａとステートメトリックメモリ２１ｂ〜２４ｂを設ける。各ステートメトリックメモリ２１ｂ〜２４ｂに記憶されたステートメトリック値は、ＡＣＳ計算部１２に戻す。また、各パスメモリ２１ａ〜２４ａに記憶されたパス選択データは、結果出力部１３に供給する。各メモリ２１〜２４でのデータ記憶及び読み出しは、制御部３０内のメモリ制御部３２による制御で実行される。なお、図２では、第１〜第４の４つのメモリ２１〜２４を個別のメモリとして示してあるが、例えば１つのメモリの記憶エリアを分割して、４つのメモリ２１〜２４を構成させてもよい。
【００３１】
結果出力部１３では、メモリ２１〜２４のパスメモリ２１ａ〜２４ａに記憶されたパス選択データを使用して、トレースバック処理を行い、復号語毎に復号結果を得、その復号結果を復号結果出力端子１４から出力させる。結果出力部１３でのトレースバック処理は、制御部３０内のトレリス計算処理制御部３１からの制御信号３２ａによる制御で実行される。
【００３２】
この場合、本例においては、ＡＣＳ計算部１２での計算処理及び結果出力部１３でのトレースバック処理として、所定ビット数の復号語を扱う場合に、２ビット単位で処理するようにしてある。この２ビット単位で処理することで、メモリ２１〜２４にアクセスさせる回数などがそれだけ減ることになり、ビタビ復号時の処理負担が減るとともに、復号処理速度の高速化につながる。
【００３３】
そして、２ビット単位で処理する上で、復号語の総ビット数が奇数ビットである場合に、最後に余る１ビットについは、パンクチャビット相当のダミービットを１ビット付加して、常に２ビットずつ処理できるようにしてある。なお、トレースバック処理時には、逆方向にたどる処理であるので、最初の処理時に、ダミービットが１ビット付加されたデータを扱うことになる。そして本例においては、このダミービットが１ビット付加されたデータについてトレースバックを行う際には、選択可能なパスを、４つのパスの内の特定のパスに制限するようにしたものである。
【００３４】
この点について、図３、図４を参照して説明すると、１回のＡＣＳ演算で処理する復号語のビット数が１ビットである場合の、最終の２ビットのトレリス線図を図３に示す。この例では、時刻ｔ＋２が最終ビット位置（即ちトレースバック開始位置）であり、１ビットずつ処理する場合には、時刻ｔ＋１、時刻ｔ…とたどっていくトレースバック処理が行われる。ここで、ビタビ復号におけるトレースバック開始位置でのステートは、必ず０ステートである。従って、時刻ｔ＋２の０ステートでのトレースバックで選択できるパスは、０ステートに繋がったパスｅと、１ステートに繋がったパスｆの２つである。同様に、時刻ｔ＋１の０ステート又は１ステートで選択できるパスは、パスａ，ｂ，ｃ，ｄの４つであり、時刻ｔ＋２から２ビット前の時刻ｔでは、４つの全てのステートが選択できる。
【００３５】
次に、１回のＡＣＳ演算で処理する復号語のビット数が２ビットである場合の、最終の２ビットのトレリス線図を図４に示す。この例では、時刻ｔ＋２が最終ビット位置（即ちトレースバック開始位置）であり、２ビットずつ処理するので、時刻ｔ＋２、時刻ｔ、時刻ｔ−２…とたどっていくトレースバック処理が行われる。上述した図３の例から判るように、時刻ｔ＋２から時刻ｔにトレースバックする場合には、トレースバック開始位置である０ステートから、全てのステート０，１，２，３が選択可能であり、２ビットずつ扱う図４の例では、この４つのステート０，１，２，３につながったパスｐ，ｑ，ｒ，ｓが、選択可能であり、この４つのパスｐ，ｑ，ｒ，ｓの中から、最も尤度が高いものが選択される。
【００３６】
これに対して、そのときにトレースバック処理される復号語の総ビット数が奇数ビットである場合には、トレースバック処理の開始時の２ビットは、パンクチャビット相当のダミービットが１ビット付加されたデータであり、図３に当て嵌めると、時刻ｔ＋２から時刻ｔ＋１へのトレースバック処理が行われることに相当し、パスｅ又はパスｆに相当するトレースバックしか存在しない。従って、復号語の総ビット数が奇数ビットである場合のトレースバック処理の開始時には、図４に示した４つのパスｐ，ｑ，ｒ，ｓの内の、パスｐ，ｑしか存在せず、そのパスｐ，ｑの中から、最も尤度が高いものを選ぶことで、誤りのない正しいトレースバック処理が行われる。トレースバック処理の開始時以外では、このようなパスの制限は必要ない。
【００３７】
本例での処理をまとめると、図５のフローチャートに示す制御が行われることになる。即ち、復号語のビット数が奇数ビットであるか否か判断し（ステップＳ１）、奇数ビットでない場合には、トレースバック時のパスを制限させずに、メモリの記憶データに基づいて最適なパスを選定しながらトレースバック処理を行う（ステップＳ２）。そして、奇数ビットである場合には、トレースバック開始時に、メモリの記憶データに基づいて選択されるパスを、パスｐ又はｑのいずれかとする制限を行い、それ以後のトレースバック処理では、メモリの記憶データに基づいて最適なパスを選定しながらトレースバック処理を行う（ステップＳ３）。
【００３８】
このようにしてビタビ復号を行うことで、２ビット単位で処理するためにビタビ復号時の処理負担が減る等の効果があるが、さらに本例では、そのように複数ビットまとめて処理することで、最後に余るビットがある場合に、トレースバック開始時のパス選択が、存在しないパス選択となることがなく、ビタビ復号精度が劣化することを防止できる。
【００３９】
なお、ここまでの説明では、２ビットごとに演算を行う場合に、復号語の総ビット数が奇数ビットである場合の処理例について説明したが、２ビット以外の複数ビット処理時にも適用可能である。即ち、ｎビット（ｎは２以上の整数）ごとに演算を行うようにして、復号語の総ビット数がｎの倍数でない場合に、トレースバック開始時に、ｎビットよりも少ないビット数の演算を行う際に、上述した実施の形態と同様に、選択の候補となるパスを、そのビット数で候補となり得るパスに制限させるようにすれば良い。
【００４０】
また、本発明のビタビ復号が適用される機器としては、畳み込み符号を受信する機器であれば、携帯電話端末などの無線通信端末や、有線の通信機器など、各種機器に適用可能である。
【００４１】
また、上述した実施の形態では、図１や図２に示したビタビ復号処理を行う専用の回路が組み込まれた受信装置として構成させる他に、例えば、パーソナルコンピュータ装置などのデータ処理装置に、受信処理を行うカードやボードなどを装着させて、ビタビ復号については、データ処理装置に組み込まれたソフトウェア（プログラム）により、演算処理で実行するようにしてもよい。
【図面の簡単な説明】
【００４２】
【図１】本発明の一実施の形態による端末の受信構成例を示したブロック図である。
【図２】本発明の一実施の形態によるビタビ復号器の構成例を示したブロック図である。
【図３】ビタビ復号のトレリス線図であり、１回のＡＣＳ演算で処理する復号語のビット数が１である場合の最終の２ビットの例である。
【図４】ビタビ復号のトレリス線図であり、１回のＡＣＳ演算で処理する復号語のビット数が２である場合の最終の２ビットの例である。
【図５】ビタビ復号のトレリス線図であり、１回のＡＣＳ演算で処理する復号語のビット数が２である場合の最終の２ビットの例である。
【図６】従来のビタビ複合器の一例を示したブロック図である。
【図７】ビタビ復号のトレリス線図の一例である。
【図８】ビタビ復号のトレリス線図であり、１回のＡＣＳ演算で処理する復号語のビット数が１である場合の例である。
【図９】ビタビ復号のトレリス線図であり、１回のＡＣＳ演算で処理する復号語のビット数が２である場合の例である。
【符号の説明】
【００４３】
１…アンテナ、２…ＲＦ部、３…復調器、４…復号器、５…受信データ処理部、１１…受信信号入力端子、１２…ＡＣＳ計算部、１３…結果出力部、１４…復号結果出力端子、２１〜２４…メモリ、３０…制御部、３１…トレリス計算処理制御部、３２…メモリ制御部
【図１】
2005323197.tif 000003
【図２】
2005323197.tif 000004
【図３】
2005323197.tif 000005
【図４】
2005323197.tif 000006
【図５】
2005323197.tif 000007
【図６】
2005323197.tif 000008
【図７】
2005323197.tif 000009
【図８】
2005323197.tif 000010
【図９】
2005323197.tif 000011