JPH09232971A - ビタビ復号方法及びビタビ復号回路 - Google Patents
ビタビ復号方法及びビタビ復号回路Info
- Publication number
- JPH09232971A JPH09232971A JP8036294A JP3629496A JPH09232971A JP H09232971 A JPH09232971 A JP H09232971A JP 8036294 A JP8036294 A JP 8036294A JP 3629496 A JP3629496 A JP 3629496A JP H09232971 A JPH09232971 A JP H09232971A
- Authority
- JP
- Japan
- Prior art keywords
- state
- path
- error
- path trace
- bit string
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
- 238000000034 method Methods 0.000 title claims description 38
- 238000007476 Maximum Likelihood Methods 0.000 claims abstract description 43
- 230000015654 memory Effects 0.000 claims abstract description 43
- 125000004122 cyclic group Chemical group 0.000 claims description 12
- 238000004364 calculation method Methods 0.000 claims description 10
- 230000005540 biological transmission Effects 0.000 claims description 9
- 239000002131 composite material Substances 0.000 abstract 1
- 238000010586 diagram Methods 0.000 description 15
- 230000007704 transition Effects 0.000 description 9
- 238000004891 communication Methods 0.000 description 4
- 238000010295 mobile communication Methods 0.000 description 4
- 238000004422 calculation algorithm Methods 0.000 description 3
- 239000000470 constituent Substances 0.000 description 2
- 238000009825 accumulation Methods 0.000 description 1
- 230000000694 effects Effects 0.000 description 1
- 238000004088 simulation Methods 0.000 description 1
Classifications
-
- H—ELECTRICITY
- H03—ELECTRONIC CIRCUITRY
- H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
- H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
- H03M13/37—Decoding methods or techniques, not specific to the particular type of coding provided for in groups H03M13/03 - H03M13/35
- H03M13/39—Sequence estimation, i.e. using statistical methods for the reconstruction of the original codes
- H03M13/41—Sequence estimation, i.e. using statistical methods for the reconstruction of the original codes using the Viterbi algorithm or Viterbi processors
- H03M13/4161—Sequence estimation, i.e. using statistical methods for the reconstruction of the original codes using the Viterbi algorithm or Viterbi processors implementing path management
-
- H—ELECTRICITY
- H03—ELECTRONIC CIRCUITRY
- H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
- H03M13/00—Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes
- H03M13/37—Decoding methods or techniques, not specific to the particular type of coding provided for in groups H03M13/03 - H03M13/35
- H03M13/39—Sequence estimation, i.e. using statistical methods for the reconstruction of the original codes
- H03M13/41—Sequence estimation, i.e. using statistical methods for the reconstruction of the original codes using the Viterbi algorithm or Viterbi processors
- H03M13/4123—Sequence estimation, i.e. using statistical methods for the reconstruction of the original codes using the Viterbi algorithm or Viterbi processors implementing the return to a predetermined state
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L1/00—Arrangements for detecting or preventing errors in the information received
- H04L1/004—Arrangements for detecting or preventing errors in the information received by using forward error control
- H04L1/0045—Arrangements at the receiver end
- H04L1/0054—Maximum-likelihood or sequential decoding, e.g. Viterbi, Fano, ZJ algorithms
Landscapes
- Engineering & Computer Science (AREA)
- Physics & Mathematics (AREA)
- Probability & Statistics with Applications (AREA)
- Theoretical Computer Science (AREA)
- Artificial Intelligence (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- Error Detection And Correction (AREA)
Abstract
(57)【要約】
【課題】 処理時間を徒に長くしたり、構成を徒に複雑
にしたりすることなく、巡回入力畳み込み符号でなる受
信信号に対する最終的に出力された復号信号の精度（誤
り率）を向上させる。 【解決手段】 本発明では、ある状態を開始状態とした
パストレースによって得られた復号信号にエラーがあ
り、そのパストレースでの最終的な到達状態とその開始
状態とが異なるときに、最終的な到達状態を開始状態と
したパストレースを再度実行する。そして、この実行に
よる復号信号をも候補として最終的に出力する復号信号
を決定する。
にしたりすることなく、巡回入力畳み込み符号でなる受
信信号に対する最終的に出力された復号信号の精度（誤
り率）を向上させる。 【解決手段】 本発明では、ある状態を開始状態とした
パストレースによって得られた復号信号にエラーがあ
り、そのパストレースでの最終的な到達状態とその開始
状態とが異なるときに、最終的な到達状態を開始状態と
したパストレースを再度実行する。そして、この実行に
よる復号信号をも候補として最終的に出力する復号信号
を決定する。
Description
【０００１】
【発明の属する技術分野】本発明は、畳み込み符号をビ
タビアルゴリズムを用いて復号するビタビ復号回路及び
ビタビ復号方法に関し、例えば、移動通信システムや衛
星通信システム等で適用されているデジタル通信（ＴＤ
ＭＡ、ＣＤＭＡ）方式に従う受信装置に適用し得るもの
である。
タビアルゴリズムを用いて復号するビタビ復号回路及び
ビタビ復号方法に関し、例えば、移動通信システムや衛
星通信システム等で適用されているデジタル通信（ＴＤ
ＭＡ、ＣＤＭＡ）方式に従う受信装置に適用し得るもの
である。
【０００２】
【従来の技術】移動通信システムや衛星通信システム等
のデジタル通信システム（ＴＤＭＡ、ＣＤＭＡ）や、デ
ィスク装置等の中には、データを正しく再生させるため
の誤り訂正符号として畳み込み符号を用いたものが多
く、この畳み込み符号の復号方式としてはビタビ復号方
式が利用されることが多い。
のデジタル通信システム（ＴＤＭＡ、ＣＤＭＡ）や、デ
ィスク装置等の中には、データを正しく再生させるため
の誤り訂正符号として畳み込み符号を用いたものが多
く、この畳み込み符号の復号方式としてはビタビ復号方
式が利用されることが多い。
【０００３】従来のビタビ復号方式を説明する前に、図
２を用いて、符号側の構成である畳み込み符号回路の一
例を説明する。図２に示す畳み込み符号回路は、符号化
レートｒ＝１／２、拘束長ｋ＝３、２個の生成多項式が
それぞれ「１１１」（すなわちｘ2 ＋ｘ＋１）及び「１
０１」（ｘ2 ＋１）の場合を示している。
２を用いて、符号側の構成である畳み込み符号回路の一
例を説明する。図２に示す畳み込み符号回路は、符号化
レートｒ＝１／２、拘束長ｋ＝３、２個の生成多項式が
それぞれ「１１１」（すなわちｘ2 ＋ｘ＋１）及び「１
０１」（ｘ2 ＋１）の場合を示している。
【０００４】図２（Ａ）は、畳み込み符号回路の構成を
示すブロック図である。畳み込み符号回路は、入力ビッ
トＵを順次シフトさせる縦続接続された２個の１ビット
バッファメモリ（その保持値をそれぞれＢＦ１、ＢＦ０
で表す）１１、１２と、入力ビットＵとバッファメモリ
１２の出力ＢＦ０とのモジュロ２の加算処理（イクスク
ルーシブオア処理）を行なう加算器１４と、入力ビット
Ｕと両バッファメモリ１１、１２の出力ＢＦ１、ＢＦ０
とのモジュロ２の加算処理（イクスクルーシブオア処
理）を行なう加算器１３とからなる。
示すブロック図である。畳み込み符号回路は、入力ビッ
トＵを順次シフトさせる縦続接続された２個の１ビット
バッファメモリ（その保持値をそれぞれＢＦ１、ＢＦ０
で表す）１１、１２と、入力ビットＵとバッファメモリ
１２の出力ＢＦ０とのモジュロ２の加算処理（イクスク
ルーシブオア処理）を行なう加算器１４と、入力ビット
Ｕと両バッファメモリ１１、１２の出力ＢＦ１、ＢＦ０
とのモジュロ２の加算処理（イクスクルーシブオア処
理）を行なう加算器１３とからなる。
【０００５】かくして、加算器１３からは、入力ビット
Ｕの系列（ＢＦ０、ＢＦ１、Ｕ）に対して、生成多項式
「１１１」の畳み込み演算を行なった結果の出力ビット
Ｘ０が得られ、加算器１４からは、入力ビットＵの系列
（ＢＦ０、ＢＦ１、Ｕ）に対して、生成多項式「１０
１」の畳み込み演算を行なった結果の出力ビットＸ１が
得られる。
Ｕの系列（ＢＦ０、ＢＦ１、Ｕ）に対して、生成多項式
「１１１」の畳み込み演算を行なった結果の出力ビット
Ｘ０が得られ、加算器１４からは、入力ビットＵの系列
（ＢＦ０、ＢＦ１、Ｕ）に対して、生成多項式「１０
１」の畳み込み演算を行なった結果の出力ビットＸ１が
得られる。
【０００６】図２（Ｂ）に、この畳み込み符号回路の生
成規則を状態遷移図化したトレリス図を示す。縦方向は
バッファメモリ１１及び１２の内容ＢＦ１、ＢＦ０の組
（状態）を示し、この例では２2 ＝４の状態（一般に
は、バッファメモリ数がｋ個であれば２k-1 の状態）が
生じる。各状態には状態番号が与えられており、以下で
は状態０〜状態３と状態を状態番号で呼ぶこととする。
成規則を状態遷移図化したトレリス図を示す。縦方向は
バッファメモリ１１及び１２の内容ＢＦ１、ＢＦ０の組
（状態）を示し、この例では２2 ＝４の状態（一般に
は、バッファメモリ数がｋ個であれば２k-1 の状態）が
生じる。各状態には状態番号が与えられており、以下で
は状態０〜状態３と状態を状態番号で呼ぶこととする。
【０００７】図２（Ａ）より明らかなように、時刻ｔの
状態ｓ（実際上１個の状態である）において、Ｕ＝０が
入力された場合は、実線に沿って次の時刻ｔ＋１の状態
に移り、この実線上の２ビット信号Ｘ０、Ｘ１が符号回
路から出力される。また、時刻ｔの状態ｓにおいてにＵ
＝１が入力された場合は、点線に沿って次の時刻ｔ＋１
の状態に移り、この点線上の２ビット信号Ｘ０、Ｘ１が
符号回路から出力される。
状態ｓ（実際上１個の状態である）において、Ｕ＝０が
入力された場合は、実線に沿って次の時刻ｔ＋１の状態
に移り、この実線上の２ビット信号Ｘ０、Ｘ１が符号回
路から出力される。また、時刻ｔの状態ｓにおいてにＵ
＝１が入力された場合は、点線に沿って次の時刻ｔ＋１
の状態に移り、この点線上の２ビット信号Ｘ０、Ｘ１が
符号回路から出力される。
【０００８】図３は、初期時刻（ｔ＝０）で状態が状態
０である状況から、「０１０１１００」という入力ビッ
ト列が入力されたときの符号回路の内部状態（ＢＦ１、
ＢＦ０）と符号回路からの出力ビットＸ０、Ｘ１とを示
す状態遷移図である。すなわち、符号回路における状態
遷移は、初期時刻での状態（初期状態）と入力ビット列
とで定まるパス上で変化する。従って、復号回路におい
て、最も確からしいパスを決定することにより、入力ビ
ット列を再生することができる。
０である状況から、「０１０１１００」という入力ビッ
ト列が入力されたときの符号回路の内部状態（ＢＦ１、
ＢＦ０）と符号回路からの出力ビットＸ０、Ｘ１とを示
す状態遷移図である。すなわち、符号回路における状態
遷移は、初期時刻での状態（初期状態）と入力ビット列
とで定まるパス上で変化する。従って、復号回路におい
て、最も確からしいパスを決定することにより、入力ビ
ット列を再生することができる。
【０００９】ところで、以上のように複数の１ビットバ
ッファメモリを用いた畳み込み符号回路においては、出
力ビットを送出し始めるための符号回路の内部初期状態
（各バッファメモリの内容）を定められていることが多
い。
ッファメモリを用いた畳み込み符号回路においては、出
力ビットを送出し始めるための符号回路の内部初期状態
（各バッファメモリの内容）を定められていることが多
い。
【００１０】例えば、北米におけるＴＤＭＡ方式を採用
しているデジタル移動通信システムにおいて、音声信号
の伝送では、５ビットあるバッファメモリの全てを
「０」とした状態を初期状態としており、また、ＦＡＣ
ＣＨ信号と呼ばれる制御信号の伝送では、図４に示すよ
うに、送信しようとする入力ビット列Ｕ［０］〜Ｕ［ｎ
−１］のバッファメモリ数（５）に等しい先頭側の入力
ビット列Ｕ［０］〜Ｕ［４］が５ビットのバッファメモ
リにセットされた状態を初期状態としている。後者の場
合は、この初期状態から、入力ビット列Ｕ［５］〜Ｕ
［ｎ−１］を順次符号回路に入力させ、その後、先頭側
の入力ビット列Ｕ［０］〜Ｕ［４］も再度符号回路に入
力させ、これらの入力ビット列Ｕ［５］〜Ｕ［ｎ−
１］、Ｕ［０］〜Ｕ［４］の各ビットが符号回路に入力
される毎に出力ビットを送出するようになされている。
しているデジタル移動通信システムにおいて、音声信号
の伝送では、５ビットあるバッファメモリの全てを
「０」とした状態を初期状態としており、また、ＦＡＣ
ＣＨ信号と呼ばれる制御信号の伝送では、図４に示すよ
うに、送信しようとする入力ビット列Ｕ［０］〜Ｕ［ｎ
−１］のバッファメモリ数（５）に等しい先頭側の入力
ビット列Ｕ［０］〜Ｕ［４］が５ビットのバッファメモ
リにセットされた状態を初期状態としている。後者の場
合は、この初期状態から、入力ビット列Ｕ［５］〜Ｕ
［ｎ−１］を順次符号回路に入力させ、その後、先頭側
の入力ビット列Ｕ［０］〜Ｕ［４］も再度符号回路に入
力させ、これらの入力ビット列Ｕ［５］〜Ｕ［ｎ−
１］、Ｕ［０］〜Ｕ［４］の各ビットが符号回路に入力
される毎に出力ビットを送出するようになされている。
【００１１】なお、このように入力ビット列を巡回的に
使用する畳み込み符号は、巡回入力畳み込み符号と呼ば
れている。
使用する畳み込み符号は、巡回入力畳み込み符号と呼ば
れている。
【００１２】上述した図３に示した状態遷移図は、初期
時刻と最終時刻との状態が等しいので、見方を変えれ
ば、入力ビット列「０００１０１１」から巡回入力畳み
込み符号（出力ビット列）を生成する際の状態遷移図に
もなっている。
時刻と最終時刻との状態が等しいので、見方を変えれ
ば、入力ビット列「０００１０１１」から巡回入力畳み
込み符号（出力ビット列）を生成する際の状態遷移図に
もなっている。
【００１３】上述のような畳み込み符号に対する最尤復
号法としては、ビタビ復号方式（ビタビ復号アルゴリズ
ム）がよく知られている。ビタビ復号方式は、基本的に
は、トレリス図上で取り得るビット列と受信ビット列
（上述したＸ０、Ｘ１に対応する）とを照合し、復号時
に最も誤りの少ないパス（最尤パス）を選択することで
送信符号を推定するアルゴリズムである。
号法としては、ビタビ復号方式（ビタビ復号アルゴリズ
ム）がよく知られている。ビタビ復号方式は、基本的に
は、トレリス図上で取り得るビット列と受信ビット列
（上述したＸ０、Ｘ１に対応する）とを照合し、復号時
に最も誤りの少ないパス（最尤パス）を選択することで
送信符号を推定するアルゴリズムである。
【００１４】以下、ビタビ復号方式を適用した従来のビ
タビ復号回路における処理の流れを、図５のフローチャ
ートを参照しながら簡単に説明する。
タビ復号回路における処理の流れを、図５のフローチャ
ートを参照しながら簡単に説明する。
【００１５】パスの選択を行なうときには、メトリック
と呼ばれる基準値の比較を行なう。メトリックには、各
時刻の各状態で受信ビットに対応して計算された枝メト
リックと、この枝メトリックの累積であるパスメトリッ
クとがあり、各時刻においてある状態に達するパスのう
ち、より尤度（確からしさ）の大きいパスを選択し、そ
のパスのパスメトリック値がその状態の新たなパスメト
リック値として更新される。
と呼ばれる基準値の比較を行なう。メトリックには、各
時刻の各状態で受信ビットに対応して計算された枝メト
リックと、この枝メトリックの累積であるパスメトリッ
クとがあり、各時刻においてある状態に達するパスのう
ち、より尤度（確からしさ）の大きいパスを選択し、そ
のパスのパスメトリック値がその状態の新たなパスメト
リック値として更新される。
【００１６】この各時刻でのパスの選択、パスメトリッ
ク値の更新等の処理はＡＣＳ（Add-Compare-Select；加
算−比較−選択）演算処理と呼ばれ、このＡＣＳ演算処
理毎に、各状態について、その状態に達するどのパスを
選択したかという情報（パス選択信号）がパスメモリに
記憶される（ステップ２０１、２０２）。
ク値の更新等の処理はＡＣＳ（Add-Compare-Select；加
算−比較−選択）演算処理と呼ばれ、このＡＣＳ演算処
理毎に、各状態について、その状態に達するどのパスを
選択したかという情報（パス選択信号）がパスメモリに
記憶される（ステップ２０１、２０２）。
【００１７】ある定められた復号サイクル分の受信ビッ
ト列（多くの場合、全ての受信ビットれ）に対して、上
記ＡＣＳ演算処理の繰返し実行が終了すると、その時点
で最も尤度が大きいパスメトリック値を保持する状態
（以下、最尤状態と呼ぶ）が選択される（ステップ２０
３）。そして、この最尤状態を開始状態とし、パスメモ
リに記憶されたパス選択信号に基き、パスのトレースバ
ックが行なわれ、トレースされていく状態から復号ビッ
トが算出される（ステップ２０４）。全ての復号ビット
の算出が終了すると、復号ビット列のエラーチェックを
行ない、エラーの有無の判定を実行する（ステップ２０
５）。そして最後に、エラー判定結果に基いて、出力ビ
ット列として、得られた復号ビット列を使用するか、使
用しないか等が決定される（ステップ２０６）。
ト列（多くの場合、全ての受信ビットれ）に対して、上
記ＡＣＳ演算処理の繰返し実行が終了すると、その時点
で最も尤度が大きいパスメトリック値を保持する状態
（以下、最尤状態と呼ぶ）が選択される（ステップ２０
３）。そして、この最尤状態を開始状態とし、パスメモ
リに記憶されたパス選択信号に基き、パスのトレースバ
ックが行なわれ、トレースされていく状態から復号ビッ
トが算出される（ステップ２０４）。全ての復号ビット
の算出が終了すると、復号ビット列のエラーチェックを
行ない、エラーの有無の判定を実行する（ステップ２０
５）。そして最後に、エラー判定結果に基いて、出力ビ
ット列として、得られた復号ビット列を使用するか、使
用しないか等が決定される（ステップ２０６）。
【００１８】なお、畳み込み符号回路への入力ビット列
は、一般には、送信データ本体に、この送信データ本体
から作成されたエラーチェックビット（列）が付加され
たものとなされており、復号回路において、上述したよ
うにエラーチェックを行なうことができる。
は、一般には、送信データ本体に、この送信データ本体
から作成されたエラーチェックビット（列）が付加され
たものとなされており、復号回路において、上述したよ
うにエラーチェックを行なうことができる。
【００１９】
【発明が解決しようとする課題】上述したように、パス
トレースバックは、開始状態である最尤状態が決定され
ると、あとはパスメモリに格納されている情報に従って
一意的に実行される。そのため、トレースバックによっ
て得られた復号ビット列にエラーがあると判定された場
合、パストレースバックの開始時点の最尤状態の選択が
正しくないことが、そのエラーの原因になっていること
がある。
トレースバックは、開始状態である最尤状態が決定され
ると、あとはパスメモリに格納されている情報に従って
一意的に実行される。そのため、トレースバックによっ
て得られた復号ビット列にエラーがあると判定された場
合、パストレースバックの開始時点の最尤状態の選択が
正しくないことが、そのエラーの原因になっていること
がある。
【００２０】最尤状態が誤っている場合において、最尤
状態以外の尤度が低い状態を開始状態としてパストレー
スバックをするとエラーのない出力ビット列が得られる
ことがある。しかし、復号ビット列のエラー原因を、最
尤状態の選択誤りか、その他の原因かを切り分けること
は困難である。このような切分けが困難な状況におい
て、正しい復号ビット列を得ようとすると、正しい復号
ビット列を得られるまで、開始状態を変更しながらパス
トレースバックを繰返し実行することが考えられる。し
かし、このようにすると、正しい復号ビット列が得られ
るまでの時間が長くかかってしまう。特に、状態数が多
い場合にはこの時間の長期化は著しい。
状態以外の尤度が低い状態を開始状態としてパストレー
スバックをするとエラーのない出力ビット列が得られる
ことがある。しかし、復号ビット列のエラー原因を、最
尤状態の選択誤りか、その他の原因かを切り分けること
は困難である。このような切分けが困難な状況におい
て、正しい復号ビット列を得ようとすると、正しい復号
ビット列を得られるまで、開始状態を変更しながらパス
トレースバックを繰返し実行することが考えられる。し
かし、このようにすると、正しい復号ビット列が得られ
るまでの時間が長くかかってしまう。特に、状態数が多
い場合にはこの時間の長期化は著しい。
【００２１】これを避けようとすると、パストレースバ
ックの実行構成を複数設けて、複数の状態からのパスト
レースバックを並列して実行することが考えられる。し
かし、このようにすると、回路が複雑、大型のものとな
ってしまう。
ックの実行構成を複数設けて、複数の状態からのパスト
レースバックを並列して実行することが考えられる。し
かし、このようにすると、回路が複雑、大型のものとな
ってしまう。
【００２２】畳み込み符号回路における初期状態が入力
ビット列によって変化する巡回入力畳み込み符号の場合
には、初期状態が固定の場合より、最尤状態からのパス
トレースバックで得られた復号ビット列に対してエラー
という判定結果が得られることが多く、上述した課題は
特に問題となっている。
ビット列によって変化する巡回入力畳み込み符号の場合
には、初期状態が固定の場合より、最尤状態からのパス
トレースバックで得られた復号ビット列に対してエラー
という判定結果が得られることが多く、上述した課題は
特に問題となっている。
【００２３】
【課題を解決するための手段】上記課題を解決するため
に、第１の本発明においては、巡回入力畳み込み符号で
なる送信信号を受信し、受信信号に応じて、ＡＣＳ演算
処理を繰返し実行して各時刻でのパス選択情報をパスメ
モリに格納し、ＡＣＳ演算処理の完了時に、パスメモリ
に格納されている情報に基いてパストレースを実行して
復号信号を得るビタビ復号方法において、ある状態から
のパストレースによって得られた復号信号にエラーがあ
り、そのパストレースでの最終的な到達状態とその開始
時の状態とが異なる場合に、最終的な到達状態を開始状
態としたパストレースを実行し、この実行による復号信
号をも候補として最終的に出力する復号信号を決定する
ことを特徴とする。
に、第１の本発明においては、巡回入力畳み込み符号で
なる送信信号を受信し、受信信号に応じて、ＡＣＳ演算
処理を繰返し実行して各時刻でのパス選択情報をパスメ
モリに格納し、ＡＣＳ演算処理の完了時に、パスメモリ
に格納されている情報に基いてパストレースを実行して
復号信号を得るビタビ復号方法において、ある状態から
のパストレースによって得られた復号信号にエラーがあ
り、そのパストレースでの最終的な到達状態とその開始
時の状態とが異なる場合に、最終的な到達状態を開始状
態としたパストレースを実行し、この実行による復号信
号をも候補として最終的に出力する復号信号を決定する
ことを特徴とする。
【００２４】また、第２の本発明においては、巡回入力
畳み込み符号でなる送信信号を受信し、ＡＣＳ演算手段
が、受信信号に応じて、ＡＣＳ演算処理を繰返し実行し
て各時刻でのパス選択情報をパスメモリに格納し、ＡＣ
Ｓ演算処理の完了時に、パストレース制御手段が、パス
メモリに格納されている情報に基いてパストレースを実
行して復号信号を得るビタビ復号回路において、(1) あ
る状態からのパストレースによって得られた復号信号に
エラーがあるかをチェックするエラーチェック手段と、
(2) そのパストレースでの最終的な到達状態とその開始
時の状態とが異なるか否かを判定する状態一致判定手段
とを備え、(3) エラーチェック手段が、ある状態からの
パストレースによって得られた復号信号にエラーがある
ことを検出し、かつ、状態一致判定手段が、そのパスト
レースでの最終的な到達状態とその開始時の状態とが異
なることを検出したとき、パストレース制御手段が、最
終的な到達状態を開始状態としたパストレースを実行
し、この実行による復号信号をも候補として最終的に出
力する復号信号を決定することを特徴とする。
畳み込み符号でなる送信信号を受信し、ＡＣＳ演算手段
が、受信信号に応じて、ＡＣＳ演算処理を繰返し実行し
て各時刻でのパス選択情報をパスメモリに格納し、ＡＣ
Ｓ演算処理の完了時に、パストレース制御手段が、パス
メモリに格納されている情報に基いてパストレースを実
行して復号信号を得るビタビ復号回路において、(1) あ
る状態からのパストレースによって得られた復号信号に
エラーがあるかをチェックするエラーチェック手段と、
(2) そのパストレースでの最終的な到達状態とその開始
時の状態とが異なるか否かを判定する状態一致判定手段
とを備え、(3) エラーチェック手段が、ある状態からの
パストレースによって得られた復号信号にエラーがある
ことを検出し、かつ、状態一致判定手段が、そのパスト
レースでの最終的な到達状態とその開始時の状態とが異
なることを検出したとき、パストレース制御手段が、最
終的な到達状態を開始状態としたパストレースを実行
し、この実行による復号信号をも候補として最終的に出
力する復号信号を決定することを特徴とする。
【００２５】第１及び第２の本発明においては、ある状
態からのパストレースによって得られた復号信号にエラ
ーがあり、そのパストレースでの最終的な到達状態とそ
の開始時の状態とが異なるときに、最終的な到達状態を
開始状態としたパストレースを実行し、この実行による
復号信号をも候補として最終的に出力する復号信号を決
定するようにしたので、処理時間を徒に長くしたり、構
成を徒に複雑にしたりすることなく、最終的に出力され
た復号信号の精度（誤り率）を向上させることができ
る。
態からのパストレースによって得られた復号信号にエラ
ーがあり、そのパストレースでの最終的な到達状態とそ
の開始時の状態とが異なるときに、最終的な到達状態を
開始状態としたパストレースを実行し、この実行による
復号信号をも候補として最終的に出力する復号信号を決
定するようにしたので、処理時間を徒に長くしたり、構
成を徒に複雑にしたりすることなく、最終的に出力され
た復号信号の精度（誤り率）を向上させることができ
る。
【００２６】
【発明の実施の形態】以下、本発明によるビタビ復号方
法及び復号回路の実施形態を図面を参照しながら詳述す
る。なお、この実施形態は、巡回入力畳み込み符号を復
号するものである。
法及び復号回路の実施形態を図面を参照しながら詳述す
る。なお、この実施形態は、巡回入力畳み込み符号を復
号するものである。
【００２７】この実施形態のビタビ復号回路は、ハード
ウェアだけでなく、ソフトウェアやファームウェアによ
って実現可能であるが、機能ブロック図で示すと、図６
に示す通りである。
ウェアだけでなく、ソフトウェアやファームウェアによ
って実現可能であるが、機能ブロック図で示すと、図６
に示す通りである。
【００２８】図６において、この実施形態のビタビ復号
回路は、受信ビット列の単位入力毎に処理を行なう構成
部分と、全ての受信ビット列に対する処理の終了後に復
号ビット列を再生する構成部分とからなっている。前者
は、枝メトリック演算部２１、パスメトリックメモリ２
２、加算器２３、比較器２４、選択器２５及びパスメモ
リ２６が該当し、後者は、パスメモリ２６、パストレー
スバック制御部２７、第１の復号ビットレジスタ２８、
トレース到達状態レジスタ２９、エラーチェック部３０
及び第２の復号ビットレジスタ３１が該当するものであ
る。なお、加算器２３、比較器２４及び選択器２５は、
ＡＣＳ部２０を構成している。
回路は、受信ビット列の単位入力毎に処理を行なう構成
部分と、全ての受信ビット列に対する処理の終了後に復
号ビット列を再生する構成部分とからなっている。前者
は、枝メトリック演算部２１、パスメトリックメモリ２
２、加算器２３、比較器２４、選択器２５及びパスメモ
リ２６が該当し、後者は、パスメモリ２６、パストレー
スバック制御部２７、第１の復号ビットレジスタ２８、
トレース到達状態レジスタ２９、エラーチェック部３０
及び第２の復号ビットレジスタ３１が該当するものであ
る。なお、加算器２３、比較器２４及び選択器２５は、
ＡＣＳ部２０を構成している。
【００２９】枝メトリック演算部２１には、処理時刻毎
に、受信ビット列の１時刻での処理単位分のビット数が
入力される。例えば、上述した図３に示す符号回路に対
応するものであれば、各時刻毎に２ビット（Ｘ０、Ｘ１
に対応）の受信ビットが入力される。枝メトリック演算
部２１は、現時刻の受信ビットの内容に基いて、枝メト
リック値を計算して加算器２３に与える。
に、受信ビット列の１時刻での処理単位分のビット数が
入力される。例えば、上述した図３に示す符号回路に対
応するものであれば、各時刻毎に２ビット（Ｘ０、Ｘ１
に対応）の受信ビットが入力される。枝メトリック演算
部２１は、現時刻の受信ビットの内容に基いて、枝メト
リック値を計算して加算器２３に与える。
【００３０】パスメトリックメモリ２２は、各状態につ
いて、現時刻までのパスメトリック値を格納している。
いて、現時刻までのパスメトリック値を格納している。
【００３１】加算器２３は、パスメトリックメモリ２２
から読出した各状態についての現時刻までのパスメトリ
ック値に、枝メトリック演算部２１から与えられた枝メ
トリック値を加算して、次の時刻の各状態に至るパスの
メトリック値を求めて比較器２４及び選択器２５に与え
る。図２（Ｂ）に一例を示したように、現時刻のある状
態までのパスが１通りであっても、次の時刻のある状態
までのパスは複数形成され、加算器２３からのパスメト
リック値も各状態について複数出力される。
から読出した各状態についての現時刻までのパスメトリ
ック値に、枝メトリック演算部２１から与えられた枝メ
トリック値を加算して、次の時刻の各状態に至るパスの
メトリック値を求めて比較器２４及び選択器２５に与え
る。図２（Ｂ）に一例を示したように、現時刻のある状
態までのパスが１通りであっても、次の時刻のある状態
までのパスは複数形成され、加算器２３からのパスメト
リック値も各状態について複数出力される。
【００３２】比較器２４は、各状態について、複数のパ
スメトリック値を大小比較し、最も尤度が高いパスの選
択信号を選択器２５に出力すると共に、そのパス選択信
号をパスメモリ２６に格納させる。
スメトリック値を大小比較し、最も尤度が高いパスの選
択信号を選択器２５に出力すると共に、そのパス選択信
号をパスメモリ２６に格納させる。
【００３３】選択器２５は、各状態について、加算器２
３から与えられたそれぞれ複数のパスメトリック値の中
から、比較器２４からのパス選択信号に応じて、尤度が
最大なものを選択し、その選択した各状態のパスメトリ
ック値をパスメトリックメモリ２２に与えてメモリ内容
を更新させる。
３から与えられたそれぞれ複数のパスメトリック値の中
から、比較器２４からのパス選択信号に応じて、尤度が
最大なものを選択し、その選択した各状態のパスメトリ
ック値をパスメトリックメモリ２２に与えてメモリ内容
を更新させる。
【００３４】パスメモリ２６には、上述したように、各
時刻でのパス選択信号が格納される。このパスメモリ２
６に、全ての時刻のパス選択信号が格納されたとき、言
い換えると、受信ビット列の全てに対するＡＣＳ部２０
の処理が終了したとき、パストレースバック制御部２７
の処理が起動される。
時刻でのパス選択信号が格納される。このパスメモリ２
６に、全ての時刻のパス選択信号が格納されたとき、言
い換えると、受信ビット列の全てに対するＡＣＳ部２０
の処理が終了したとき、パストレースバック制御部２７
の処理が起動される。
【００３５】パストレースバック制御部２７は、処理が
起動されたとき、パスメトリックメモリ２２に格納され
ている各状態でのパスメトリック値に基き、尤度が最も
高い状態（最尤状態）を認識し、その最尤状態を開始状
態として、パスメモリ２６の格納内容に基き、パストレ
ースバックを実行するものである。
起動されたとき、パスメトリックメモリ２２に格納され
ている各状態でのパスメトリック値に基き、尤度が最も
高い状態（最尤状態）を認識し、その最尤状態を開始状
態として、パスメモリ２６の格納内容に基き、パストレ
ースバックを実行するものである。
【００３６】なお、パストレースバックの具体的方法に
ついては、例えば特開平８−８７６２号公報に詳述され
ている。
ついては、例えば特開平８−８７６２号公報に詳述され
ている。
【００３７】第１の復号ビットレジスタ２８は、このと
きのパストレースバックによって、得られた復号ビット
列を格納するものであり、トレース到達状態レジスタ２
９は、パストレースバックが終了したときに到達した状
態（符号回路でのバッファメモリの初期状態に対応す
る）を格納するものである。
きのパストレースバックによって、得られた復号ビット
列を格納するものであり、トレース到達状態レジスタ２
９は、パストレースバックが終了したときに到達した状
態（符号回路でのバッファメモリの初期状態に対応す
る）を格納するものである。
【００３８】エラーチェック部３０は、第１の復号ビッ
トレジスタ２８に格納された復号ビット列、又は、後述
する第２の復号ビットレジスタ３１に格納された復号ビ
ット列に対するエラーチェックを実行し、チェック結果
をパストレースバック制御部２７に与えるものである。
なお、この実施形態も、符号回路への入力ビット列に、
送信したいビット列だけでなくエラービット列部分が存
在することを前提としている。
トレジスタ２８に格納された復号ビット列、又は、後述
する第２の復号ビットレジスタ３１に格納された復号ビ
ット列に対するエラーチェックを実行し、チェック結果
をパストレースバック制御部２７に与えるものである。
なお、この実施形態も、符号回路への入力ビット列に、
送信したいビット列だけでなくエラービット列部分が存
在することを前提としている。
【００３９】上述したパストレースバック制御部２７は
また、エラーチェック部３０から、第１の復号ビットレ
ジスタ２８に格納された復号ビット列にエラーがあると
いうチェック結果が与えられたときには、最尤状態とト
レース到達状態レジスタ２９内の格納状態とを比較し、
これら状態が不一致のときには、トレース到達状態レジ
スタ２９内の格納状態を開始状態として、パスメモリ２
６の格納内容に基き、パストレースバックを実行するも
のである。
また、エラーチェック部３０から、第１の復号ビットレ
ジスタ２８に格納された復号ビット列にエラーがあると
いうチェック結果が与えられたときには、最尤状態とト
レース到達状態レジスタ２９内の格納状態とを比較し、
これら状態が不一致のときには、トレース到達状態レジ
スタ２９内の格納状態を開始状態として、パスメモリ２
６の格納内容に基き、パストレースバックを実行するも
のである。
【００４０】第２の復号ビットレジスタ３１は、このと
きのパストレースバックによって、得られた復号ビット
列を格納するものである。
きのパストレースバックによって、得られた復号ビット
列を格納するものである。
【００４１】上述したパストレースバック制御部２７
は、エラーチェック部３０から、第１の復号ビットレジ
スタ２８に格納された復号ビット列にエラーがないとい
うチェック結果が与えられたとき、エラーがあるという
チェック結果は与えられたが最尤状態とトレース到達状
態レジスタ２９内の格納状態とが一致したとき、又は、
エラーチェック部３０から、第２の復号ビットレジスタ
３１に格納された復号ビット列に対するエラーチェック
結果が与えられたときには、エラーチェック結果や復号
ビット列に基いて出力ビット列（ない場合を含む）を決
定して次段の処理回路に出力するものである。
は、エラーチェック部３０から、第１の復号ビットレジ
スタ２８に格納された復号ビット列にエラーがないとい
うチェック結果が与えられたとき、エラーがあるという
チェック結果は与えられたが最尤状態とトレース到達状
態レジスタ２９内の格納状態とが一致したとき、又は、
エラーチェック部３０から、第２の復号ビットレジスタ
３１に格納された復号ビット列に対するエラーチェック
結果が与えられたときには、エラーチェック結果や復号
ビット列に基いて出力ビット列（ない場合を含む）を決
定して次段の処理回路に出力するものである。
【００４２】次に、以上のような各機能部２１〜３１か
らなるビタビ復号回路の動作、すなわち、実施形態のビ
タビ復号方法の処理を、図１のフローチャートを参照し
ながら詳述する。
らなるビタビ復号回路の動作、すなわち、実施形態のビ
タビ復号方法の処理を、図１のフローチャートを参照し
ながら詳述する。
【００４３】ＡＣＳ演算処理を繰返し実行し、各時刻で
のパスの選択やパスメトリックの更新を行ない、このＡ
ＣＳ演算処理毎に、各状態について、その状態に達する
どのパスを選択したかという情報（パス選択信号）をパ
スメモリ２６に記憶する（ステップ１０１、１０２）。
のパスの選択やパスメトリックの更新を行ない、このＡ
ＣＳ演算処理毎に、各状態について、その状態に達する
どのパスを選択したかという情報（パス選択信号）をパ
スメモリ２６に記憶する（ステップ１０１、１０２）。
【００４４】全ての受信ビット列に対して、上記ＡＣＳ
演算処理の繰返し実行が終了すると、その時点で最も尤
度が大きいパスメトリックを保持する最尤状態Ｓｓを認
識する（ステップ１０３）。そして、この最尤状態Ｓｓ
を開始状態とし、パスメモリ２６に記憶されたパス選択
信号に基き、パスのトレースバックを行ない、トレース
される各時刻の状態から復号ビットを算出し、復号ビッ
ト列Ａを得る（ステップ１０４）。また、トレースバッ
クが終了したときに到達した状態Ｓｒを認識する（ステ
ップ１０５）。その後、復号ビット列Ａのエラーチェッ
クを行ない、エラーの有無の判定を実行する（ステップ
１０６、１０７）。
演算処理の繰返し実行が終了すると、その時点で最も尤
度が大きいパスメトリックを保持する最尤状態Ｓｓを認
識する（ステップ１０３）。そして、この最尤状態Ｓｓ
を開始状態とし、パスメモリ２６に記憶されたパス選択
信号に基き、パスのトレースバックを行ない、トレース
される各時刻の状態から復号ビットを算出し、復号ビッ
ト列Ａを得る（ステップ１０４）。また、トレースバッ
クが終了したときに到達した状態Ｓｒを認識する（ステ
ップ１０５）。その後、復号ビット列Ａのエラーチェッ
クを行ない、エラーの有無の判定を実行する（ステップ
１０６、１０７）。
【００４５】この判定により、復号ビット列Ａにエラー
が存在するという結果が得られると、最尤状態Ｓｓとト
レースバックで到達した状態Ｓｒとを比較する（ステッ
プ１０８）。両状態Ｓｓ及びＳｒが一致すれば、後述す
るステップ１１１に進む。一方、両状態Ｓｓ及びＳｒが
不一致であれば、状態Ｓｒを開始状態とし、パスメモリ
２６に記憶されたパス選択信号に基き、パスのトレース
バックを行ない、トレースされる各時刻の状態から復号
ビットを算出し、復号ビット列Ｂを得（ステップ１０
９）、その後、復号ビット列Ｂのエラーチェックを行な
い、エラーの有無の判定を実行する（ステップ１１
０）。
が存在するという結果が得られると、最尤状態Ｓｓとト
レースバックで到達した状態Ｓｒとを比較する（ステッ
プ１０８）。両状態Ｓｓ及びＳｒが一致すれば、後述す
るステップ１１１に進む。一方、両状態Ｓｓ及びＳｒが
不一致であれば、状態Ｓｒを開始状態とし、パスメモリ
２６に記憶されたパス選択信号に基き、パスのトレース
バックを行ない、トレースされる各時刻の状態から復号
ビットを算出し、復号ビット列Ｂを得（ステップ１０
９）、その後、復号ビット列Ｂのエラーチェックを行な
い、エラーの有無の判定を実行する（ステップ１１
０）。
【００４６】ステップ１０７の判定の結果が復号ビット
列Ａにエラーがないという結果のとき、ステップ１０８
の判定の結果が最尤状態Ｓｓとトレース最終到達状態Ｓ
ｒとが一致したという結果のとき、又は、復号ビット列
Ｂに対するエラーチェックが終了したときには、出力ビ
ット列として、得られた復号ビット列Ａ又はＢを使用す
るか、使用しないかや、得られた復号ビット列Ａ又はＢ
をエラー訂正して使用するか等を決定し、出力ビット列
を送出する（ステップ１１１）。例えば、復号ビット列
Ａにエラーがないときにはこの復号ビット列Ａを出力ビ
ット列とし、復号ビット列Ａにエラーがあり、復号ビッ
ト列Ｂにエラーがないときにはこの復号ビット列Ｂを出
力ビット列とし、復号ビット列Ａ及びＢに共にエラーが
あるときには所定ルールに従って出力ビット列を決定す
る。
列Ａにエラーがないという結果のとき、ステップ１０８
の判定の結果が最尤状態Ｓｓとトレース最終到達状態Ｓ
ｒとが一致したという結果のとき、又は、復号ビット列
Ｂに対するエラーチェックが終了したときには、出力ビ
ット列として、得られた復号ビット列Ａ又はＢを使用す
るか、使用しないかや、得られた復号ビット列Ａ又はＢ
をエラー訂正して使用するか等を決定し、出力ビット列
を送出する（ステップ１１１）。例えば、復号ビット列
Ａにエラーがないときにはこの復号ビット列Ａを出力ビ
ット列とし、復号ビット列Ａにエラーがあり、復号ビッ
ト列Ｂにエラーがないときにはこの復号ビット列Ｂを出
力ビット列とし、復号ビット列Ａ及びＢに共にエラーが
あるときには所定ルールに従って出力ビット列を決定す
る。
【００４７】図７は、パストレースバックの具体例を説
明するための状態遷移図であり、上述の図３に示した符
号回路での状態遷移図に対応するものである。
明するための状態遷移図であり、上述の図３に示した符
号回路での状態遷移図に対応するものである。
【００４８】今、最終時刻の状態である最尤状態とし
て、正しくない状態２が選択されたとする。この状態２
からパストレースバックを開始すると、まず、復号ビッ
トとして「１」が得られる。図２（Ａ）について説明し
たように、状態を（ＢＦ１、ＢＦ０）で定めているの
で、その状態を規定する２ビット中の上位ビット（バッ
ファメモリ１１に格納されているビット）はその時刻で
の入力ビットになっている。そのため、状態２（１０）
からのトレースバックで復号ビット「１」が得られる。
復号ビット（入力ビット）が「１」であって状態２に遷
移するので、前の時刻ｔ＝６での状態は状態１（０１）
である。従って、次の復号ビットとして、状態を規定す
る２ビット中の上位ビットの「０」が得られる。
て、正しくない状態２が選択されたとする。この状態２
からパストレースバックを開始すると、まず、復号ビッ
トとして「１」が得られる。図２（Ａ）について説明し
たように、状態を（ＢＦ１、ＢＦ０）で定めているの
で、その状態を規定する２ビット中の上位ビット（バッ
ファメモリ１１に格納されているビット）はその時刻で
の入力ビットになっている。そのため、状態２（１０）
からのトレースバックで復号ビット「１」が得られる。
復号ビット（入力ビット）が「１」であって状態２に遷
移するので、前の時刻ｔ＝６での状態は状態１（０１）
である。従って、次の復号ビットとして、状態を規定す
る２ビット中の上位ビットの「０」が得られる。
【００４９】以下、同様にして、次々と復号ビットが得
られ、時刻ｔ＝０までトレースバックしたときには、復
号ビット列として「０００１０１１０１」（トレースバ
ックの逆方向で並べている）が得られる。なお、先頭側
の２ビット「００」は、最終到達状態（この場合、状態
０）を表す２ビットであり、上述したように、巡回入力
畳み込み符号の場合、符号回路の全てのバッファメモリ
に入力ビット列を満たした状態を初期状態としているの
で、最終到達状態を表す２ビットを復号ビット列の先頭
に付加している。
られ、時刻ｔ＝０までトレースバックしたときには、復
号ビット列として「０００１０１１０１」（トレースバ
ックの逆方向で並べている）が得られる。なお、先頭側
の２ビット「００」は、最終到達状態（この場合、状態
０）を表す２ビットであり、上述したように、巡回入力
畳み込み符号の場合、符号回路の全てのバッファメモリ
に入力ビット列を満たした状態を初期状態としているの
で、最終到達状態を表す２ビットを復号ビット列の先頭
に付加している。
【００５０】このように、本来の状態ではない状態２を
最尤状態としてパストレースバックして得た復号ビット
列「０００１０１１０１」に対してエラーチェックを実
行すると、エラーという結果が得られる。
最尤状態としてパストレースバックして得た復号ビット
列「０００１０１１０１」に対してエラーチェックを実
行すると、エラーという結果が得られる。
【００５１】そのため、１回目のパストレースバックで
の最終到達状態（この場合、状態０）を、最終時刻ｔ＝
７の状態としたパストレースバックが実行される。パス
トレースバックの開始状態が状態０（００）であるの
で、まず、復号ビットとして「０」が得られる。時刻ｔ
＝７の状態が状態０であって、その状態０へ遷移させる
ビット（復号ビット）が「０」であるので、時刻ｔ＝６
の状態は状態１（０１）である。従って、次の復号ビッ
トとして「０」が得られる。以下、同様にして、次々と
復号ビットが得られ、時刻ｔ＝０までトレースバックし
たときには、復号ビット列として「０００１０１１０
０」が得られる。すなわち、符号回路への入力ビット列
に等しい復号ビット列が得られる。
の最終到達状態（この場合、状態０）を、最終時刻ｔ＝
７の状態としたパストレースバックが実行される。パス
トレースバックの開始状態が状態０（００）であるの
で、まず、復号ビットとして「０」が得られる。時刻ｔ
＝７の状態が状態０であって、その状態０へ遷移させる
ビット（復号ビット）が「０」であるので、時刻ｔ＝６
の状態は状態１（０１）である。従って、次の復号ビッ
トとして「０」が得られる。以下、同様にして、次々と
復号ビットが得られ、時刻ｔ＝０までトレースバックし
たときには、復号ビット列として「０００１０１１０
０」が得られる。すなわち、符号回路への入力ビット列
に等しい復号ビット列が得られる。
【００５２】以上のように、最尤状態を開始状態とした
パストレースバックで得られた復号ビット列がエラーと
判定された場合に、そのときのトレースバックでの最終
到達状態を開始状態としたパストレースバックを実行さ
せることとしたのは、以下の理由による。
パストレースバックで得られた復号ビット列がエラーと
判定された場合に、そのときのトレースバックでの最終
到達状態を開始状態としたパストレースバックを実行さ
せることとしたのは、以下の理由による。
【００５３】巡回入力畳み込み符号は、上述したように
入力ビット列の一部を巡回させて符号回路に入力させて
いるので、符号回路における初期状態と最終状態とは等
しくなる（以下、符号回路におけるこれらの状態と基準
状態と呼ぶ）という性質を有する。従って、復号回路に
おいても、トレースバックの最終到達状態（符号回路の
初期状態に対応）と、トレースバックの開始状態（符号
回路の最終状態に対応）とが等しいことが期待される。
そのため、パスメトリック値が示す尤度が最も高い最尤
状態からパストレースバックして得た復号ビット列にエ
ラーが生じても、最尤状態及び最終到達状態は最尤パス
に係るものであるので（言い換えると、図７からも分か
るように、パスのかなりの部分が本来のパスに等しい可
能性が高いので）、少なくとも一方が符号回路での基準
状態に等しくなっている確率は非常に大きい。
入力ビット列の一部を巡回させて符号回路に入力させて
いるので、符号回路における初期状態と最終状態とは等
しくなる（以下、符号回路におけるこれらの状態と基準
状態と呼ぶ）という性質を有する。従って、復号回路に
おいても、トレースバックの最終到達状態（符号回路の
初期状態に対応）と、トレースバックの開始状態（符号
回路の最終状態に対応）とが等しいことが期待される。
そのため、パスメトリック値が示す尤度が最も高い最尤
状態からパストレースバックして得た復号ビット列にエ
ラーが生じても、最尤状態及び最終到達状態は最尤パス
に係るものであるので（言い換えると、図７からも分か
るように、パスのかなりの部分が本来のパスに等しい可
能性が高いので）、少なくとも一方が符号回路での基準
状態に等しくなっている確率は非常に大きい。
【００５４】復号回路では、最尤状態及び最終到達状態
のいずれが基準状態になっているかを認識することがで
きない。ここで、認識はし得ないが最尤状態が基準状態
になっている場合には、最尤状態を開始状態とするパス
トレースバックは必ず実行されるので、エラーが生じて
もこれ以上の措置を講じることはできない。最尤状態が
基準状態になっていない場合には、最尤状態を開始状態
とするパストレースバックで得られた最終到達状態が基
準状態になっている可能性がかなり高い。
のいずれが基準状態になっているかを認識することがで
きない。ここで、認識はし得ないが最尤状態が基準状態
になっている場合には、最尤状態を開始状態とするパス
トレースバックは必ず実行されるので、エラーが生じて
もこれ以上の措置を講じることはできない。最尤状態が
基準状態になっていない場合には、最尤状態を開始状態
とするパストレースバックで得られた最終到達状態が基
準状態になっている可能性がかなり高い。
【００５５】そこで、最尤状態及び最終到達状態のいず
れが基準状態になっているかは認識できないが、最尤状
態からパストレースバックして得た復号ビット列にエラ
ーが生じた場合において最尤状態と最終到達状態とが異
なるときには、最終到達状態を開始状態としたパストレ
ースバックを実行し、正しい復号ビット列が得られる可
能性を高めることとした。
れが基準状態になっているかは認識できないが、最尤状
態からパストレースバックして得た復号ビット列にエラ
ーが生じた場合において最尤状態と最終到達状態とが異
なるときには、最終到達状態を開始状態としたパストレ
ースバックを実行し、正しい復号ビット列が得られる可
能性を高めることとした。
【００５６】最尤状態からパストレースバックして得た
復号ビット列にエラーが生じた場合において、従来のよ
うに、エラーがない復号ビット列が得られるまで、開始
状態を変えたパストレースバックを繰返し実行すること
は、処理時間や構成の面の課題は大きいが、この実施形
態では、パストレースバックを多くても２回しか実行し
ないので、処理時間や構成の面の不都合はほとんど生じ
ない。
復号ビット列にエラーが生じた場合において、従来のよ
うに、エラーがない復号ビット列が得られるまで、開始
状態を変えたパストレースバックを繰返し実行すること
は、処理時間や構成の面の課題は大きいが、この実施形
態では、パストレースバックを多くても２回しか実行し
ないので、処理時間や構成の面の不都合はほとんど生じ
ない。
【００５７】また、最尤状態からパストレースバックし
て得た復号ビット列にエラーが生じた場合において、パ
スメトリック値が示す尤度が２番目に大きいパスの最終
時刻の状態を開始状態としたパストレースバックを実行
し、正しい復号ビット列が得られる可能性を高めること
も考えられる。しかし、本来の論理レベルからの反転が
生じた受信ビット列の位置によっては、２番目以降の尤
度が近接した値となり、本来のパスと異なる部分が多い
パスが２番目の尤度のパスと選定されることもあり、巡
回入力畳み込み符号の性質を利用した実施形態の方法よ
り、復号ビット列の精度向上の度合いは劣ると考えられ
る。
て得た復号ビット列にエラーが生じた場合において、パ
スメトリック値が示す尤度が２番目に大きいパスの最終
時刻の状態を開始状態としたパストレースバックを実行
し、正しい復号ビット列が得られる可能性を高めること
も考えられる。しかし、本来の論理レベルからの反転が
生じた受信ビット列の位置によっては、２番目以降の尤
度が近接した値となり、本来のパスと異なる部分が多い
パスが２番目の尤度のパスと選定されることもあり、巡
回入力畳み込み符号の性質を利用した実施形態の方法よ
り、復号ビット列の精度向上の度合いは劣ると考えられ
る。
【００５８】図８は、北米におけるＴＤＭＡ方式を採用
しているデジタル移動通信システムにおいて、ＦＡＣＣ
Ｈ信号を復号した場合のシミュレーション結果を示した
特性図である。ここで、縦軸は誤り率（ＦＡＣＣＨ Ｗ
ＥＲ）を示し、横軸は隣接チャネルとの干渉の強さ（Ｃ
ＩＲ）を示している。
しているデジタル移動通信システムにおいて、ＦＡＣＣ
Ｈ信号を復号した場合のシミュレーション結果を示した
特性図である。ここで、縦軸は誤り率（ＦＡＣＣＨ Ｗ
ＥＲ）を示し、横軸は隣接チャネルとの干渉の強さ（Ｃ
ＩＲ）を示している。
【００５９】この図８からは、隣接チャネルとの干渉の
強さが同じ場合、この実施形態による誤り率（図面では
◆で示している）の方が、最尤状態を開始状態とするパ
ストレースバックだけを行なう従来での誤り率（図面で
は×で示している）より約４〜１０ｄＢ改善されている
が分かる。
強さが同じ場合、この実施形態による誤り率（図面では
◆で示している）の方が、最尤状態を開始状態とするパ
ストレースバックだけを行なう従来での誤り率（図面で
は×で示している）より約４〜１０ｄＢ改善されている
が分かる。
【００６０】以上のように、上記実施形態によれば、最
尤状態を開始状態としたパストレースバックで得られた
復号ビット列にエラーがあり、そのパストレースバック
により最終的に到達した状態と最尤状態とが異なるとき
に、最終到達状態を開始状態としたパストレースバック
を行ない、２回のパストレースバックによって得られた
２種類の復号ビット列に基き、最終的に出力する復号ビ
ット列を決定するようにしたので、処理時間の長期化や
構成の複雑化をほとんど生じさせることなく、最終的に
出力する復号ビット列の精度を従来に比較して格段的に
高めることができる。
尤状態を開始状態としたパストレースバックで得られた
復号ビット列にエラーがあり、そのパストレースバック
により最終的に到達した状態と最尤状態とが異なるとき
に、最終到達状態を開始状態としたパストレースバック
を行ない、２回のパストレースバックによって得られた
２種類の復号ビット列に基き、最終的に出力する復号ビ
ット列を決定するようにしたので、処理時間の長期化や
構成の複雑化をほとんど生じさせることなく、最終的に
出力する復号ビット列の精度を従来に比較して格段的に
高めることができる。
【００６１】特に、各時刻での状態数が多いシステムに
おいては、最尤状態を開始状態としたパストレースバッ
クで得られた復号ビット列にエラーが生じる可能性が大
きいので、上記実施形態は有効である。
おいては、最尤状態を開始状態としたパストレースバッ
クで得られた復号ビット列にエラーが生じる可能性が大
きいので、上記実施形態は有効である。
【００６２】なお、上記実施形態においては、パストレ
ース方式として、パストレースバック方式を採用してい
るビタビ復号方法及び回路について説明したが、パスト
レース方式として、パストレースフォワード方式を採用
しているビタビ復号方法及び回路に本発明を適用するこ
とができる。ここで、パストレースフォワード方式と
は、パストレースバック方式と受信ビットの順番を逆に
してＡＣＳ演算処理を各時刻毎に行ない、ＡＣＳ演算処
理の完了時に、前方からパストレースを行なう方式であ
る。
ース方式として、パストレースバック方式を採用してい
るビタビ復号方法及び回路について説明したが、パスト
レース方式として、パストレースフォワード方式を採用
しているビタビ復号方法及び回路に本発明を適用するこ
とができる。ここで、パストレースフォワード方式と
は、パストレースバック方式と受信ビットの順番を逆に
してＡＣＳ演算処理を各時刻毎に行ない、ＡＣＳ演算処
理の完了時に、前方からパストレースを行なう方式であ
る。
【００６３】また、上記実施形態においては、パストレ
ースを多くても２回行なうものを示したが、最大実行回
数が３回以上であっても良い。但し、２回目以上のパス
トレースは、直前のパストレースによる復号ビット列に
エラーが生じていること、直前のパストレースでの最終
到達状態が今までパストレースの開始状態にされたこと
がないものであることを条件に実行される。
ースを多くても２回行なうものを示したが、最大実行回
数が３回以上であっても良い。但し、２回目以上のパス
トレースは、直前のパストレースによる復号ビット列に
エラーが生じていること、直前のパストレースでの最終
到達状態が今までパストレースの開始状態にされたこと
がないものであることを条件に実行される。
【００６４】
【発明の効果】以上のように、本発明によれば、ある状
態を開始状態としたパストレースによって得られた復号
信号にエラーがあり、そのパストレースでの最終的な到
達状態とその開始状態とが異なるときに、最終的な到達
状態を開始状態としたパストレースを再度実行し、この
実行による復号信号をも候補として最終的に出力する復
号信号を決定するようにしたので、処理時間を徒に長く
したり、構成を徒に複雑にしたりすることなく、最終的
に出力された復号信号の精度（誤り率）を向上させるこ
とができる。
態を開始状態としたパストレースによって得られた復号
信号にエラーがあり、そのパストレースでの最終的な到
達状態とその開始状態とが異なるときに、最終的な到達
状態を開始状態としたパストレースを再度実行し、この
実行による復号信号をも候補として最終的に出力する復
号信号を決定するようにしたので、処理時間を徒に長く
したり、構成を徒に複雑にしたりすることなく、最終的
に出力された復号信号の精度（誤り率）を向上させるこ
とができる。
【図１】実施形態のビタビ復号方法を示すフローチャー
トである。
トである。
【図２】畳み込み符号回路の構成例及び単位時間での状
態遷移を示す説明図である。
態遷移を示す説明図である。
【図３】畳み込み符号回路の全期間の状態遷移を示す説
明図である。
明図である。
【図４】巡回入力畳み込み符号の説明図である。
【図５】従来のビタビ復号方法を示すフローチャートで
ある。
ある。
【図６】実施形態のビタビ復号回路を示すブロック図で
ある。
ある。
【図７】実施形態のパストレースバックの説明図であ
る。
る。
【図８】実施形態の効果の説明図である。
２０…ＡＣＳ部、２１…枝メトリック演算部、２２…パ
スメトリックメモリ、２６…パスメモリ、２７…パスト
レースバック制御部、２８、３１…復号ビットレジス
タ、２９…トレース到達状態レジスタ、３０…エラーチ
ェック部。
スメトリックメモリ、２６…パスメモリ、２７…パスト
レースバック制御部、２８、３１…復号ビットレジス
タ、２９…トレース到達状態レジスタ、３０…エラーチ
ェック部。
Claims (4)
- 【請求項１】 巡回入力畳み込み符号でなる送信信号を
受信し、受信信号に応じて、ＡＣＳ演算処理を繰返し実
行して各時刻でのパス選択情報をパスメモリに格納し、
上記ＡＣＳ演算処理の完了時に、上記パスメモリに格納
されている情報に基いてパストレースを実行して復号信
号を得るビタビ復号方法において、 ある状態からのパストレースによって得られた復号信号
にエラーがあり、そのパストレースでの最終的な到達状
態とその開始時の状態とが異なる場合に、上記最終的な
到達状態を開始状態としたパストレースを実行し、この
実行による復号信号をも候補として最終的に出力する復
号信号を決定することを特徴としたビタビ復号方法。 - 【請求項２】 パストレースの実行回数が多くても２回
であり、２回目のパストレースは、最尤状態からの１回
目のパストレースによって得られた復号信号にエラーが
あり、そのパストレースでの最終的な到達状態とその開
始時の最尤状態とが異なる場合に、上記最終的な到達状
態を開始状態として実行することを特徴とした請求項１
に記載のビタビ復号方法。 - 【請求項３】 巡回入力畳み込み符号でなる送信信号を
受信し、ＡＣＳ演算手段が、受信信号に応じて、ＡＣＳ
演算処理を繰返し実行して各時刻でのパス選択情報をパ
スメモリに格納し、上記ＡＣＳ演算処理の完了時に、パ
ストレース制御手段が、上記パスメモリに格納されてい
る情報に基いてパストレースを実行して復号信号を得る
ビタビ復号回路において、 ある状態からのパストレースによって得られた復号信号
にエラーがあるかをチェックするエラーチェック手段
と、 そのパストレースでの最終的な到達状態とその開始時の
状態とが異なるか否かを判定する状態一致判定手段とを
備え、 上記エラーチェック手段が、ある状態からのパストレー
スによって得られた復号信号にエラーがあることを検出
し、かつ、上記状態一致判定手段が、そのパストレース
での最終的な到達状態とその開始時の状態とが異なるこ
とを検出したとき、上記パストレース制御手段が、上記
最終的な到達状態を開始状態としたパストレースを実行
し、この実行による復号信号をも候補として最終的に出
力する復号信号を決定することを特徴としたビタビ復号
回路。 - 【請求項４】 上記パストレース制御手段によるパスト
レースの実行回数が多くても２回であり、上記パストレ
ース制御手段は、２回目のパストレースを、最尤状態か
らの１回目のパストレースによって得られた復号信号に
エラーがあり、そのパストレースでの最終的な到達状態
とその開始時の最尤状態とが異なる場合に、上記最終的
な到達状態を開始状態として実行することを特徴とした
請求項３に記載のビタビ復号回路。
Priority Applications (3)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP03629496A JP3233847B2 (ja) | 1996-02-23 | 1996-02-23 | ビタビ復号方法及びビタビ復号回路 |
| US08/799,826 US5887007A (en) | 1996-02-23 | 1997-02-13 | Viterbi decoding method and viterbi decoding circuit |
| CA002198194A CA2198194A1 (en) | 1996-02-23 | 1997-02-21 | Viterbi decoding method and viterbi decoding circuit |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP03629496A JP3233847B2 (ja) | 1996-02-23 | 1996-02-23 | ビタビ復号方法及びビタビ復号回路 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH09232971A true JPH09232971A (ja) | 1997-09-05 |
| JP3233847B2 JP3233847B2 (ja) | 2001-12-04 |
Family
ID=12465798
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP03629496A Expired - Fee Related JP3233847B2 (ja) | 1996-02-23 | 1996-02-23 | ビタビ復号方法及びビタビ復号回路 |
Country Status (3)
| Country | Link |
|---|---|
| US (1) | US5887007A (ja) |
| JP (1) | JP3233847B2 (ja) |
| CA (1) | CA2198194A1 (ja) |
Cited By (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| KR19990077972A (ko) * | 1998-03-18 | 1999-10-25 | 이데이 노부유끼 | 비터비복호장치및복호방법 |
| US7450667B2 (en) | 2000-11-10 | 2008-11-11 | Samsung Electronics Co., Ltd. | Apparatus and method for decoding data of unknown frame length |
| EP2075919A2 (en) | 2007-12-27 | 2009-07-01 | NEC Electronics Corporation | Decoding apparatus and decoding method |
Families Citing this family (9)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| EP0851591B1 (en) * | 1996-12-24 | 2001-09-12 | Matsushita Electric Industrial Co., Ltd. | Data processor and data processing method |
| TW377427B (en) * | 1998-05-26 | 1999-12-21 | Koninklijke Philips Electronics Nv | Transmission system having a simplified channel decoder applicable to mobile phone systems for better reliability in serial transmission |
| US6460161B1 (en) * | 1998-06-01 | 2002-10-01 | Her Majesty The Queen In Right Of Canada, As Represented By The Minister Of Industry Through The Communications Research Centre | Processing of state histories in Viterbi decoding |
| US6597743B1 (en) | 1999-12-07 | 2003-07-22 | Ericsson Inc. | Reduced search symbol estimation algorithm |
| WO2004019498A1 (en) * | 2002-08-08 | 2004-03-04 | Telefonaktiebolaget Lm Ericsson (Publ) | Convolutional decoder and method for decoding demodulated values |
| US7272748B1 (en) * | 2004-03-17 | 2007-09-18 | Symantec Corporation | Method and apparatus to detect and recover from a stack frame corruption |
| US7607073B1 (en) * | 2004-08-04 | 2009-10-20 | Marvell International Ltd. | Methods, algorithms, software, circuits, receivers and systems for iteratively decoding a tailbiting convolutional code |
| US7480852B2 (en) * | 2006-10-13 | 2009-01-20 | Cisco Technology, Inc. | Method and system for improving decoding efficiency in wireless receivers |
| ATE476792T1 (de) * | 2008-04-30 | 2010-08-15 | Ericsson Telefon Ab L M | Verfahren und anordnung zur decodierung eines mittels tail-biting-codes kodierten signals |
Family Cites Families (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP3120342B2 (ja) | 1991-04-30 | 2000-12-25 | 日本無線株式会社 | ビタビ復号器 |
| US5349589A (en) * | 1991-07-01 | 1994-09-20 | Ericsson Ge Mobile Communications Inc. | Generalized viterbi algorithm with tail-biting |
| JP3241210B2 (ja) * | 1994-06-23 | 2001-12-25 | 沖電気工業株式会社 | ビタビ復号方法及びビタビ復号回路 |
-
1996
- 1996-02-23 JP JP03629496A patent/JP3233847B2/ja not_active Expired - Fee Related
-
1997
- 1997-02-13 US US08/799,826 patent/US5887007A/en not_active Expired - Lifetime
- 1997-02-21 CA CA002198194A patent/CA2198194A1/en not_active Abandoned
Cited By (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| KR19990077972A (ko) * | 1998-03-18 | 1999-10-25 | 이데이 노부유끼 | 비터비복호장치및복호방법 |
| US7450667B2 (en) | 2000-11-10 | 2008-11-11 | Samsung Electronics Co., Ltd. | Apparatus and method for decoding data of unknown frame length |
| EP2075919A2 (en) | 2007-12-27 | 2009-07-01 | NEC Electronics Corporation | Decoding apparatus and decoding method |
| JP2009159482A (ja) * | 2007-12-27 | 2009-07-16 | Nec Electronics Corp | 復号装置及び復号方法 |
| US8230308B2 (en) | 2007-12-27 | 2012-07-24 | Renesas Electronics Corporation | Decoding apparatus and decoding method using an additional add-compare-select operation on decoded data in the event of an error in the decoded data |
Also Published As
| Publication number | Publication date |
|---|---|
| JP3233847B2 (ja) | 2001-12-04 |
| US5887007A (en) | 1999-03-23 |
| CA2198194A1 (en) | 1997-08-24 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US5802116A (en) | Soft decision Viterbi decoding with large constraint lengths | |
| JP3239870B2 (ja) | データ誤り訂正システム | |
| US7765459B2 (en) | Viterbi decoder and viterbi decoding method | |
| JP3196835B2 (ja) | ビタビ復号法及びビタビ復号器 | |
| JP3233847B2 (ja) | ビタビ復号方法及びビタビ復号回路 | |
| US5838697A (en) | Bit error counting method and counting technical field | |
| US7765458B1 (en) | Error pattern generation for trellis-based detection and/or decoding | |
| KR100387089B1 (ko) | 브랜치 메트릭 계산 처리에서 감소된 비트수를 갖는비터비 디코더 | |
| JP2917177B2 (ja) | 誤り検出方法、装置ならびに識別方法 | |
| JPWO1995001008A1 (ja) | 誤り検出方法、装置ならびに識別方法 | |
| US7861146B2 (en) | Viterbi decoding apparatus and Viterbi decoding method | |
| JP2008118327A (ja) | ビタビ復号方法 | |
| US20040190651A1 (en) | Decoding a signal encoded with a convolutional code | |
| JP3753822B2 (ja) | ビタビ復号方法および装置 | |
| KR101212856B1 (ko) | 통신 시스템에서 데이터를 복호하는 방법 및 장치 | |
| US20050138535A1 (en) | Method and system for branch metric calculation in a viterbi decoder | |
| JP5370487B2 (ja) | 復号方法および復号装置 | |
| JP2591332B2 (ja) | 誤り訂正復号装置 | |
| JP3337950B2 (ja) | 誤り訂正復号化方法及び誤り訂正復号化装置 | |
| KR100564757B1 (ko) | 저전력 비터비 복호기 및 역추적 방법 | |
| US11108415B2 (en) | Method of Viterbi algorithm and receiving device | |
| JP3120342B2 (ja) | ビタビ復号器 | |
| JP3235333B2 (ja) | ビタビ復号方法およびビタビ復号化装置 | |
| JPH09247002A (ja) | ビタビ復号化装置およびビタビ復号化方法 | |
| JP3530451B2 (ja) | ビタビ復号装置 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| S111 | Request for change of ownership or part of ownership |
Free format text: JAPANESE INTERMEDIATE CODE: R313113 |
|
| R350 | Written notification of registration of transfer |
Free format text: JAPANESE INTERMEDIATE CODE: R350 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20070921 Year of fee payment: 6 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20080921 Year of fee payment: 7 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20090921 Year of fee payment: 8 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20090921 Year of fee payment: 8 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20100921 Year of fee payment: 9 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20100921 Year of fee payment: 9 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20110921 Year of fee payment: 10 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20110921 Year of fee payment: 10 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20120921 Year of fee payment: 11 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20120921 Year of fee payment: 11 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20130921 Year of fee payment: 12 |
|
| LAPS | Cancellation because of no payment of annual fees |