JPH03253123A - 誤り訂正符号の復号方法 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 （産業上の利用分野） 本発明は、誤り訂正用線型符号器によって符号化されて
送信された系列に対し、受信側で、各々の復号情報ビッ
トの誤り率を最小化する誤り訂正符号の復号方式に関す
るものである。

（従来技術） 従来伝送路上で生じる誤りを効果的に取り除いて信頼度
の高い通信を行う手法の一つとして、あらかしめ送信側
において、ある一定の冗長度を含んだ符号化を行い、受
信側では逆にこの符号化された受信系列から、送信側で
送信されたと判断される情報系列の推定を行うことによ
り、伝送路で生じた誤りを訂正する方法かある。これは
ＦＥＣ（Ｆｏｒｗａｒｄ　Ｅｒｒｏｒ　Ｃｏｒｒｅｃｔ
ｉｏｎ）または前方誤り訂正方式と呼ばれている。

ＦＥＣに用いる符号化の方法としては大別してブロック
符号化によるものと、たたみ込み符号化によるものが存
在する。このうち、たたみ込み符号化は一定長のシフト
レジスタを用いて情報系列を連続的に符号化してゆく方
式である。一方、ブロック符号化は、ある一定長の情報
系列をひとまとめとして符号化を行う方式である。次に
、これらの符号に対する代表的な復号方式として、ビタ
ビ復号方式か存在する。ビタビ復号方式は、一般にはト
レリス構造を有する線型符号に対して適用可能であるか
、現在は主にたたみ込み符号に対して適用されている。

ビタビ復号は、記憶のない雑音通信路における有限状態
離散時間マルコフ過程の下で状態系列の最尤推定を行う
アルゴリズムであり、観測系列全体が与えられた下では
最も尤度か大きい状態系列すなわち符号語か必ず選び出
される。従ってビタビ復号はこの意味において、最適な
復号アルゴリズムであるといえる。ビタビ復号はまた軟
判定復号も比較的簡単に行えることから、現在衛星通信
システムを中心としてたたみ込み符号に対する有効な復
号アルゴリズムとして広く普及している。このビタビア
ルゴリズムについては文献（１）　（Ｇ、Ｄ、　Ｆｏｒ
ｎｅｙ、　Ｊｒ、　：“Ｔｈｅ　Ｖｉｔｅｒｂｉ　Ａｌ
ｇｏｒｉｔｈｍ”、　Ｐｒｏｃ、　ｏｆ　ＩＥＥＥ、　
Ｖｏｌ、　６１．　Ｎｏ、３．　ｐｐ、２６８−２７８
．　Ｍａｒｃｈ　１９７３）に詳しく述べられている。

一方、符号語としての誤り率を最小化するビタビ復号に
対し、符号語を構成するシンボルまたはビット毎の誤り
率を最小化する復号アルゴリズムか存在する（以下この
アルゴリズムを最小ビット誤り復号アルゴリズムと呼ぶ
）。以下このアルゴリズムについて簡単に説明する。

ここで表記は文献（１）に従う。符号拘束長をＶ時刻ｋ
における送信情報をＵｋ＋　その直前の符号器の状態を
Ｘ　＊　”　（Ｕ　ｋ−１＋　Ｕ　ｋ−２＋・・・、Ｕ
ｋ−ｖ）とする。また時刻０からｋまての受信側での観
測系列をＺ　ｏ””　（２１１１１２１１・・’　！　
Ｚ　ｋ　）　、これに対応した時刻０の初期状態から時
刻にの終端状態までの状態系列をＸ　６”’　−（Ｘ　
Ｏｒ　Ｘ　＋＋　”’　＋　Ｘ　ｈ＋＋）とする。

ｘ　ｏ”’に対する尤度は。

λ（ξ→＝　　ＩｎＰ　（Ｘ＋＋＋　ｌ　ｘ＋）　　Ｉ
ｎＰ　（ｚ＋　ｌ　ｘ＋）・・・（１） で与えられる。

但しξ＋　＝（Ｘ＋＋＋＋　Ｘ＋）は時刻ｉの遷移を、
また、Ｐ（％）は条件突き確率をそれぞれ表す。

符号語は符号化系列の最終時刻である時刻にの直後、あ
る状態Ｘ　Ｋ　＋　１で終端されるとする。その間の観
測系列ｚ　（＝　ｚ　ｏＫ）とＸ、との結合確率は、Ｐ
（ｘｋ、ｚ）＝Ｐ（ｘｋ、ｚｏｋ−’）Ｐ（ｚｋＫｌｘ
ｋ）　　　・−・（２）で与えられるか、これは、 Ｐ　（ｘｉ、　ｚｏ’−’）：：Σ Ｐ　（Ｌ−＋＋　ｚｏ’−２）ｅｘｐ（−λ（ξ、−１
）・・・（４） の繰り返し演算て求められる。Ｓ（ｕ、）を時刻ｋにお
けるＸ５，１のはしめの成分かｕ、ＥＥ　（ｏ、　１）
であるような状態の集合とする。このときＰ　（ｕｍ、
　　ｚ）＝　　Σ　Ｐ　（ｘｍ−＋、ｚ）ｋ＋１〔Ｓ（
ｕ工）　　　　　　　　・・（５）を計算することて時
刻にの情報ビットＵ、の結合確率か求まるｏ　Ｐ（ｕｍ
＝０．　ｚ）＞Ｐ（ｕｈ＝１．　ｚ）ならばｕ、＝０、
Ｐ（ｕｍ＝０．　ｚ）＜Ｐ（ｕｍ＝１．　ｚ）ならばｕ
ｂ　＝　Ｌ　Ｐ（ｕ＊＝０．　ｚ）＝Ｐ（ｕｈ＝ｌ、　
ｚ）ならばランダムにＵ、＝Ｏまたはｕｍ＝１を出力す
ることで復号を行う。なおこの最小ビット誤り復号アル
ゴリズムについては文献（２）　（Ｌ、Ｒ，Ｂａｈｌ。

Ｊ、　Ｃｏｃｋｅ、　Ｆ、　Ｊｅｌｉｎｅｋ　ａｎｄ　
Ｊ、　Ｒａｖｉｖ　：　”ＯｐｔｉｍａｌＤｅｃｏｄｉ
ｎｇ　ｏｆ　Ｌｉｎｅａｒ　Ｃｏｄｅｓ　ｆｏｒ　Ｍｉ
ｎｉｍｉｚｉｎｇ　ＳｙｍｂｏＩ　Ｅｒｒｏｒ　Ｒａｔ
ｅ″、ＩＥＥＥ　Ｔｒａｎｓ、　　Ｉｎｆ、　Ｔｈｅｏ
ｒｙ、　Ｖｏｌ。

ＩＴ−２０，ｐｐ、　２８４−２８７．　Ｍａｒｃｈ　
１９７４）に詳しく述べられている。最小ビット誤り復
号アルゴリズムはビット誤り率特性において最も優れた
特性を有すると同時に各ビットまたはシンボル単位にそ
の後号結果の確かさの尺度を与えられるという長所かあ
るか、反面、以下に述へるように本質的な欠点をいくつ
か持−っているためビタビ復号にとって代わる復号方式
とはなっていない。

ビタビ復号と比較を行ったとき、最小ビット誤り復号ア
ルゴリズＬの持つ欠点としては、復号中にビタビ復号て
必要な前方繰りかえし演算の他に後方繰りかえし演算か
要求されるところにある。

しかも後方繰りかえし演算の対象となる受信系列は、常
に復号対象としているビットの時刻から受信語の終わり
までの区間であるために、復号にあたっては、必ず符号
語全体を受信し終わった後に前方および後方繰りかえし
演算を行わねばならない。一方、ビタビ復号の場合には
、前方繰りかえし演算のみて復号を行うことか可能であ
る。しかもビットまたはシンボルか受信される毎に前方
繰りかえし演算を続けてゆけばよいのて、−括して受信
系列か与えられる必要もなく、連続モードての復号か可
能である。

また、最小ビット誤り復号の場合、さらに復号に際して
大きな記憶領域が必要となること、積和演算の繰りかえ
しか多数必要になる等の欠点かある。これらの理由によ
り現在ではビタヒ復号か特にたたみ込み符号の復号用に
ｆＩＪ広く用いられるすう勢にある。

（発明か解決しようとする課題） 最小ビット誤り復号アルゴリズムは従来技術の項でも述
べたように、演算量か多大な上、復号に要求される記憶
領域か非常に大きくなる。文献（２）に従えば、拘束長
■、符号化率Ｒ＝ｋｏ／ｎｏのたたみ込み符号を用い、
ＣＦ　（２）上で定義された符号長をτとすると、前方
繰りかえし演算に２×２ｋＯｖ・τの記憶領域が要求さ
れる。また後方繰りかえし演算も、直接演算を行えば前
方繰りかえし演算と同じだけの記憶領域か必要となるた
め、総数で２×２ｋＯｖ・τだけの記憶領域か必要とな
る。例えば符号長をτ＝１０００ビット、ｖ＝６、Ｒ＝
ｌ／２．１個の記憶領域に３２ビツトか割当てられると
すると総記憶領域は約４　Ｍｂｉｔとなり復号器にかか
る負担は大きい。また実際に前方および後方繰りかえし
演算を行う際には、構成されるトレリスに応し、初期処
理、定常処理、終端処理とその演算処理を変更する必要
かあるという欠点を持っている。

次に最小ビット誤り復号アルゴリズムを実際に実行する
際には尤度を実数値て取り扱うため、実数間での乗算か
必要になる。その結果ブロック長りか長くなると尤度の
値か極度に増加したり、極度に減少して演算器の演算可
能範囲を逸脱する可能性か非常に高くなる。また本アル
ゴリズムは前述の如く結合確率Ｐ　（ｕｍ　、　ｚ）を
求めているためにｕｍ＝０の確率とり、＝１の確率を加
えても１とはならない。従ってこの情報だけからは客観
的な信頼度が得られ難いという欠点を有している。

さらに最小ビット誤り復号アルゴリズムを用いて復号を
行う際には、適切な復号用の枝メトリックを用いること
か望ましいか、そのためにはあらかしめ通信路の遷移確
率を知っておく必要かある。

通信路の状態が既知である場合には問題は生しないか、
そうでない場合には適当な通信路の状態を仮定するか、
もしくは他の何らかの手段を用いて遷移確率の情報を得
なければならない。

本発明は、上述した従来技術の問題点を解決するために
なされたものて、効率的にビット誤り率を減少すること
のできる誤り訂正符号の復号方式を提供するものである
。

（課題を解決するための手段） この目的を達成するための本発明の方式は、構成におい
て次のような特徴を有している。

すなわち、本発明の第１の特徴は、符号語がある長さで
終端された線型符号にたいして最小ビット誤り復号アル
ゴリズムを適用する際に、前方繰りかえし演算に要求さ
れる記憶領域のみを用いて、前方繰りかえし演算ならび
に後方繰りかえし演算を１度づつ行って、効率的に最小
ビット誤り復号アルゴリズムを実行し、メモリの削減を
図るものである。

本発明の第２の特徴は、前方繰りかえし演算で得た値の
逆数を後方繰りかえし演算の初期値として用いることに
より最大事後確率Ｐ　（ｕｌｚ）を求められるようにし
たことにある。

本発明の第３の特徴は、メトリックテーブルの規格化を
行うことにより演算器のオーバーフローを避けることに
ある。

本発明の第４の特徴は、軟判定復号を行う場合に受信さ
れた軟判定重み情報を利用して通信路の遷移確率を推定
し、この情報を用いて適切な枝メトリックを選び出し、
これを復号演算に用いることで精度の良い最小ビット誤
り復号を行うことにある。

（発明の構成および作用） 以下具体例により本発明の構成および作用を詳細に説明
する。なお本発明の実施例は、簡単のため符号化率Ｒ＝
１／２のたたみ込み符号を対象として述べる。

（実施例１） 第１図は本発明を用いて構成した最小ビット誤り復号器
である。図において受信された軟判定受信系列１００は
、−旦受信系列ＲＡＭｌｌ０中に格納される。この格納
データは、必要に応じて読み出され、ＲＯＭアドレス演
算部１４２を通じてメトリック用ＲＯＭＩＩＩの適当な
番地がアクセスされる。メトリック用ＲＯＭ１１１の中
には枝メトリックの値か格納されており、受信データと
、演算対象となるトレリス上の枝に応じた適切なメトリ
ック値かマルチプレクサ１３０を通じて乗算器に与えら
れる。

復号過程における途中の計算結果は、全て復号用演算Ｒ
ＡＭ１１２中に格納されている。復号を進める際には、
同ＲＡＭ１１２よりデータを読み出し、前述の枝メトリ
ツク値との積和演算を乗算器１４０、加減算器１４１．
アキュムレータ１２２によって行う。

アキュムレータ１２２に残された演算結果は復号用演算
ＲＡＭ１１２に格納されるか、あるいは必要に応じて後
に続く積和演算に利用される。またアキュムレータ１２
２の内容の正負に応じてステータスレジスタ１２３の内
部のフラグが変化する。アキュムレータ１２２中に最終
演算結果が得られた時には、ステータスレジスタ１２３
のフラグ内容が復号結果格納ＲＡＭ１１３中に書き込ま
れる。受信符号語に対する復号か全て終了したならばこ
の格納データが読み出され、復号データ１０１が得られ
る。

次に本復号器を用いて実際に復号か行われる過程が本発
明の中心であるので、以下これについて詳述する。

ここで復号対象とするたたみ込み符号は、符号化率Ｒ＝
１／２　　拘束長ｖ＝２の非組織符号とし、符号語長は
Ｌ＝６技とする。但し、この中には符号語を終端するた
めの２枝か含まれている。第２図にたたみ込み符号器の
結線図を、第３図にはこの符号器によって構成されるト
レリス線図を示す。

第３図において、状態から状態への遷移は一定時刻毎に
生じるとし、時刻ｔの遷移が生じる直前の状態の持つ時
刻を状態時刻を−と呼ぶこととする。

各状態は符号器のシフトレジスタの状態に対応しており
、００．０１１１０．１１の４状態を有する。枝上には
符号化された枝コードが示されている。また図中実線の
枝は情報ビット入力が０、点線は情報ビット入力がｌで
あることを示している。

表り、ｌ復号用演算ＲＡＭ１１２の初期状態状態時刻　
０ − − 一 表１．１は、復号を行うための最小ビット誤り復号用演
算ＲＡＭ１１２の構成および初期状態の内容を示してい
る。同ＲＡＭは２ｖ行Ｌ＋２列の２次元配列の構造を持
ち、ｉ行ｊ列のＲＡＭの内容をｒ（ｉ。

ｊ）で示す。本発明の例ではＶ＝２　　Ｌ＝６であるの
で０≦ｉ≦３．０≦ｊ≦７となる。またｉ＝０．１．２
．３　に対応する符号器の状態は０Ｏ１ｌＯ１０１、１
１とする。

復号は大別して、前方繰りかえし演算と後方繰りかえし
演算に分けられる。

前方繰りかえし演算においては、まず演算ＲＡＭ１１２
の内容をゼロクリアした後、初期状態ての状態時刻０−
の状態００の確率（１）をｒ　（０，０）に書き込む。

これが表１．１に示された状態である。ここで表の添字
ｊは状態時刻ｊ−に対応している。

続けて１−〜５−にわたる状態時刻ｊ−の状態の確率Ｐ
（ｘ＋−、ｚｏ’−’）を以下のように１≦ｊ≦５まで
の繰りかえし演算で求め、これをｒ’　（ＸＩ−＋ｊ）
の値とする。

状態時刻ｊ− 状態００　：　ｒ（０，ｊ）＝ｒ’（０，ｊ−１）”λ
＋−＋（００）＋　ｒ　（２，ｊ−１）”　λ＋−＋（
１１）状態１０　：　ｒ（１，Ｄ＝ｒ（０，ｊ−１）”
λ＋−＋（０）＋ｒ（２，ｊ−１）”λｒ　−１（ｏｏ
）状態０１　：　ｒ（２，ｊ）＝ｒ（１，ｊ−１）”　
λ、−＋（Ｏｆ）＋ｒ（３，ｊ−１）”λ＋−１（１０
）状態１１　：　ｒ（３，Ｄ＝ｒ（１，ｊ−１）”λ＋
−＋（１０）＋　ｒ　（３，ｊ−１）”　λｔ−＋（０
１）ここで　λｒ　（ｏｏ）とは時刻ｊにおける枝コー
ド００の枝に対応する枝メトリックを示している。以上
のステップは、復号器中において次のように行われる。

第１にアキュムレータ１２２の内容をクリアする。

続いて時刻ｊ−１における受信語を受信系列格納ＲＡＭ
ｌｌ０より取り出し、ＲＯＭアドレス演算部１４２内に
ラッチしておく。マルチプレクサ１３０はＲＯＭＩＩＩ
からの入力を選択するようにしておく。

第２に以下の様にして状態００から状態１１に至るまで
の状態時刻ｊ−に対するｒの更新を行う。

状態００を例にとれば、まずＲＡＭ１１２からｒ’　（
０゜ｊ−１）を取り出しレジスタ１２１　　にロードす
る。

同時にＲＯＭアドレス演算部１４２を通じメトリック用
ＲＯＭＩＩＩよりλＪ　−１（００）を求める。次のタ
イミングで乗算器１４０は両者間の乗算を行い、その結
果ｒ（０，ｊ−１）”　λ＋−＋（００）かアキュムレ
ータ１２２に残る。次のタイミングでＲＡＭ１１２より
ｒ　（２，ｊ−１）を取り出し同じくレジスタ１２１に
ロードする。

このとき、同時にＲＯＭアドレス演算部１４２を通じメ
トリック用ＲＯＭＩＩＩよりλ＋−＋（１１）かロード
される。次のタイミングでｒ’　（２，ｊ−１）”　λ
＋−＋（１１）か乗算器１４０により求められ、最終的
に加減算器１４１で加算か行われてアキュムレータ１２
２内にｒ（０，Ｊ　　１）”　　λ＋−＋　（００）十
ｒ　　（２，Ｊ　　１）”　　λ４−１（１１）の値が
残る。最後にこの計算値かＲＡＭ１１２内のｒ’　（０
，ｊ）に格納され、アキュムレータ１２２はクリアされ
る。この動作を全ての状態に対して行うことにより、時
刻ｊにおける受信語に対する演算か終了したので、引続
き時刻ｊ＋１に対応する受信語を受信系列格納ＲＡＭｌ
ｌ０より取り出し、同様の動作を繰り返す。

状態時刻　０−　１−　２−　３−　４−　５−　６前
方繰りかえし演算が終わった時点でのＲＡＭＩＩ２の内
容を表１．２に示す。図中斜線を引いた部分か計算が行
われた部分である。なお斜線を引いた部分て０が書き込
まれているのは演算結果が必ず０であることを示してい
る。このことは特に例外処理を行うことなく初期処理か
行われたことを示している。また特別な終端処理も特に
行われていないか、後に示すように後方繰りかえし演算
終了時には自動的に等価な処理が行われることになる。

０−　　１−　　２−　　３−　　４−　　５−　　６
状態時刻 続いて後方演算を行う。まず演算ＲＡＭ１１２において
Ｉ’　（０，７）　＝１とおいて後方探索の初期値をセ
ットする。表１．３にこの時点のＲＡＭ１１２の状態を
示す。０≦ｊ≦５までは前方繰りかえし演算で得られた
結果が格納されている。なお、後方繰りかえし演算にお
いては状態時刻ｊ−に対する状態Ｘ、−の演算結果は ｒ’　　（ｘ＋　、　Ｊ＋１）　　に格納される。

続けて、５−〜１−にわたる状態時刻ｊ−の状態の確率
Ｐ　（ｚ＋５１　ｘ＋−）を以下のように計算した後、
前に求めたＰ　（ＸＩ−＋　Ｚｏ’−’）との積をとり
Ｐ（ｘ＋。

２）を求める。

状態時刻ｊ− 状態　００：　ｒ’（０，ｊ＋１）＝ｒ（０，ｊ＋２）
”　λｊ（００）十ｒ（１，ｊ＋２）”　λｊ（１１） 状態　１０：　ｒ’（１，ｊ＋１）＝ｒ（２，ｊ＋２）
”　λｊ（０１）＋　ｒ　（３，ｊ＋２）”　　λ　ｊ
（１０）状態　０１　：　ｒ　（２，ｊ＋１）＝　ｒ　
（０，ｊ＋２）”　λｊ（１１）十ｒ’　（１，ｊ＋２
）”λｊ（ＯＯ）状態　１１　：　ｒ’（３，ｊ＋１）
＝ｒ’（２，ｊ＋２）”λｊ（１０）＋ｒ（３，ｊ＋２
）”　λｊ（０１） ある状態時刻ｊ−に対して実際に復号器内で演算か行わ
れる過程は前方繰りかえし演算と全く同様であるので省
略する。Ｊ−における上記繰りかえし演算が終了した時
点で、１”（ＸＩ−＋　ｊ）には状態時刻ｊ−の状態Ｘ
、−の前方繰りかえし演算結果、ｒ（ｘ＋−１Ｊ＋１）
には同状態時刻の状態Ｘの後方繰りかえし演算結果か格
納されている。ｒ’　（ＸＩ−＋　Ｊ）”ｒ（ｘ＋−、
ｊ＋１）を計算することによりＰ　（ＸＩ−＋　Ｚ）を
得る。この後、時刻ｊ−１の情報ビットが０であるよう
な枝が繋がっている状態Ｐ　（Ｌ−、ｚ）の和、および
情報ビットが１であるような枝が繋がっているＰ（ｘ＋
−、ｚ）の和をそれぞれ求め、両者の大小を比較し、確
率の大なる方を選択することにより時刻ｊ−１における
復号を行うことができる。この動作を時刻０まで繰りか
えせば全ての受信語に対する復号が完了する。ここで後
方繰りかえし演算において、状態時刻５−ではｒ　（２
，６）、　ｒ　（３゜６）が０となり、この結果Ｐ　（
ｘｓ　＝２．　ｚ）、Ｐ（ｘｓ＝３．　ｚ）がそれぞれ
０となる。このことは特に例外処理を行うことなく終端
処理が行われたことを示している。また同様にＰ　（ｘ
＋　＝２．　Ｚ）　、Ｐ　（ｘ＋＝３．　ｚ）もそれぞ
れ０となり、初期処理も完了している。

本実施例の符号器を用いる場合には第３図のトレリス線
図より明らかなように状態００．０１には情報ビット−
〇の枝の先端が、状態１０．１１には情報ビット−１の
枝の先端が対応している。すなわちＲＡＭ１１２におい
てｉ＝　０．２が情報ビット＝０の枝の先端に、ｉ＝１
．３が情報ビット＝１の枝の先端に対応する。これらよ
り復号の実際例は以下のように行われる。

まずアキュムレータ１２２をクリアし、マルチプレクサ
１３０をＲＡＭ１１２に選択しておく。ＲＡＭ１１２よ
りＩ”　（０，ｊ＋１）をレジスタ１２１にロードする
。続イテ同じ＜　ＲＡＭ１１２よりｒ’（０，３）　　
を読み出し、レジスタ１２１との間で乗算を行い、その
結果をアキュムレータ１２２に格納する。次にＲＡＭ１
１２より（１，ｊ＋１）をレジスタにロードする。続い
て同じくＲＡＭ１１２よりｒ’（１，ｊ）を読み出し、
レジスタ１２１との間で乗算を行うが、この結果は情報
ビット■に対応する状態に対する結果であるのて、加減
算器１４１　　によりアキュムレータ１２２から乗算結
果を減じる演算を行う。さらに次の１＝＝２の状態に対
しては乗算を上記と同様に実施した後、加減算器１４１
によりアキュムレータ１２２に乗算結果を加える。最後
にｉ＝３の状態に対して加減算器１４１を用いて減算処
理を行う。これらの演算を行った結果は、Ｐ　（ｕｋ＝
Ｑ、　ｚ）　　Ｐ　（ｕｈ　＝１．　ｚ）となっている
。すなわちこれは、時刻ｊにおける情報ビット＝０の尤
度から情報ビット＝１の尤度を減じたものであり、この
値が正ならば０を、負ならばｌを、０ならばランダムに
Ｏまたは１を復号結果とする。この場合、アキュムレー
タ１２２の内容の正負の情報はステータスレジスタ１２
３に格納されているので、これを復号結果格納ＲＡＭ１
１３に書き込む。以上の演算処理により時刻ｊ−１にお
ける復号が完了する。この時点でｊ列の前方繰りかえし
演算結果は不要となるので、これを時刻ｊ−２の後方繰
りかえし演算用の記憶領域として使用する。この演算、
記憶領域の使用を繰りかえし行い、時刻０に至るまでの
復号か完了したならば、最終的に端末からの要求により
復号結果格納ＲＡＭ１１３の情報を復号データ１０１と
して出力する。

なお本例では、メモリの最初と最後の列に固定した初期
値を書き込んでいるか、オペレーションの工夫によりこ
の２列は省略か可能である。この時には２ｖ行り列の２
次元配列の構造を持ったメモリで本発明が実施できる。

（実施例２） 第４図は本発明に基づく第２の実施例を示した図である
。第１図と異なる点は、受信語を格納するＲＡＭ４１０
からのＭＳＢを除く軟判定重みデータかマルチプレクサ
４３１を通じて加減算器４４１に接続されていることと
、アキュムレータ４２２の演算結果がレジスタ４２４に
格納されることである。このレジスタ４２４はＲＯＭア
ドレス演算部４２２へ与える値を保持する機能を持つ。

またメトリックＲＯＭ４１１中には異なる伝送路の状態
にして最適化されたメトリックテーブルか複数個格納さ
れている。このテーブルの１例を示したのが表２．１で
ある。

表２．１ （Ｅ、ＡＯ＝０．ＯｄＢ用ＲＡＭ） 表２．１はＥ、／Ｎ、（伝送路における１ビツトあたり
のエネルギ／片側雑音電力密度）　＝０．０ｄＢの伝送
路を想定して作られた８値軟判定用のメトリックテーブ
ルＲＯＭの内容を示している。表２．１においてアドレ
スは８ビツトであり、うち上位２ビツトが復号器か想定
するトレリス枝上の枝コード、下位３ビツト×２かそれ
ぞれの技コードに対応する８値軟判定受信データである
。

表２．２ （Ｅ　、／Ｎ　ｏ　＝　ｏ、　ｏｄＢ）軟判定受信領域 ０　　（０１１） ］、　　　（０１０） ２　　（００１） ３　　（０００） ４　　（１００） ５　　（１０１） ６　　（１１０） ７　　（１１１） 領域確率 ０．４６５８ ０．１９４８ ０．１５９１ ０．１０１７ ０．０５０９ ０．０１９９ ０．００６１ ０．００１７ 例えば枝コードか００で軟判定受信ビットｌ、２かそれ
ぞれ０００．００１のとき、表２．２の領域遷移確率を
参照して枝メトリツク値は ０、１０１７Ｘ　０．１５９１＝　０．０１６１８とな
る。

この値が本来の枝メトリツク値である。

しかしながら、このような小さな値を枝メトリツク値と
して採用し、乗算の実行を繰りかえすと計算かアンダー
フローする可能性が高い。そこで本来の枝メトリック値
全てにある一定の値をあらかじめ乗算しておいて復号を
行うと、アンダーフローおよびオーバーフローの問題を
解決することができる。そこで領域確率そのものを確率
変数とみてその平均をとると、この場合０．２９３６が
得られる。従って受信ビット１ビツトあたりメトリック
値を０．２９３６−　’　＝　３．４０６０倍あればメ
トリックの平均増分は１となり発散を抑制できる。ここ
では受信２ビツトの規格化のため本来のメトリック値を
３゜４０６０２　＝１１．６００８倍した値を枝メトリ
ツクデータとして用いる。ＲＯＭ４１１中には各種のＥ
、／Ｎ、値に応じたこのような枝メトリツクテーブルが
複数用意される。

次に第４図に基づき動作の概要について述べる。

まず受信された軟判定受信系列４００は一旦受信語格納
ＲＡＭ４１０中に格納される。初期値としてマルチプレ
クサ４３１はＲＡＭ４１０側に接続されており、アキュ
ムレータ４２２の内容は０にリセットされている。

受信系列格納ＲＡＭ４１０中に格納された軟判定データ
のうちＭＳＢを除いた受信データ重み情報は順にマルチ
プレクサ４３１を通じて加減算器４４１に入力され、ア
キュムレータ４２２の内容と加算され、その結果がアキ
ュムレータ４２２に残る。この演算を受信したデータ全
てについて実施すれば、受信給金てにわたる受信軟判定
重みの総和がアキュムレータ４２２に得られる。これを
レジスタ４２４に格納する。軟判定の重み分布は、伝送
路の雑音状態と密接に関連しているため、レジスタ４２
４の値から伝送路の状態を推定することが可能である。

ＲＯＭアドレス演算部４４２は、この情報を受けて伝送
路の雑音状態に最も整合したメトリックテーブルを複数
の伝送路用に最適化されたグループの中から選び、その
ＲＯＭアドレスをＲＯＭ４１１に与える。

この後マルチプレクサ４３１は乗算器４４０側に接続さ
れる。またレジスタ４２４の内容は受信系列全体が復号
されるまでの間保持される。

以降最小ビット誤り復号アルゴリズムに基づく復号動作
は実施例１の場合と同様である。なお本実施例では、受
信軟判定重みの総和より伝送路状態を推定して、その後
、その伝送路に最適化されたメトリックテーブルを選ぶ
手段を述べたか、メトリックテーブル−つしか存在せず
、規格化を各符号語の復号毎に行う場合には、受信軟判
定重みの分布を求め、この分布より最適な規格化の値を
決定して復号を行えば、効果的にオーバーフローおよび
アンダフローを防止することができる。

（実施例３） 第５図は最小ビット誤り復号アルゴリズムを用いて、復
号情報ビットをそれぞれ０．１とした時の確度情報を与
える復号器の構成を示したものである。同図の動作につ
いて説明する。

前方繰りかえし演算および後方繰りかえし演算によって
状態時刻ｊ−ての状態ｘ１−に対する前方繰りかえし演
算結果Ｉ’（ｘ＋−、ｊ）と同状態時刻での後方繰りか
えし演算結果ｒ’（ｘ＋　、　ｊ＋１）か得られるまで
の過程は実施例１と同一である。全てのＸｌ−について
上記のｒ’　（ＸＩ−＋　Ｊ）とｒ’　（ｘ＋−２Ｊ＋
１）か求められたならば、時刻ｊ−ｔの情報ビットが０
であるような枝が繋がっている状態Ｐ（ｘ＋−、ｚ）の
和を求め、Ｐ（ｕ＋−＋　＝０．　ｚ）としてこの値を
確度情報納ＲＡＭ５１３に保存する。全く同様にして、
Ｐ（ＩＪ＋−＋＝１．ｚ）をＲＡＭ５１３に保存する。

このための積和乗算が行われる過程は実施例１と同一で
ある。全ての時刻にわたり確度情報か計算され、ＲＡＭ
５１３に格納されたならばこの値は確度情報５０１とし
て端末側にわたされる。

（実施例４） 表３．１と３．２は本発明に基づき、第５図の回路構成
を用いて、復号中にｕｋ＝０とｕ、＝１をとる確率の和
がｌとなる規格化か自動的に行われるような第４の実施
例を示したものである。

状態時刻 〇− − − ０″′ − 一 −６ 状態時刻 以下実施例３と異なる点について述へる。本実施例では
前方繰りかえし演算をｊ＝６のレベル、あるいは少なく
ともｒ　（０，６）の値か求まるまで行う。ｊ＝６に対
する前方繰りかえし演算が終了した時点のＲＡＭ１１２
の状態を表３．１に示す。ｒ（０，６）にはＰ　（ｚ）
の値が格納されている。

次にＰ　（ｚ）から、除算を行うことにより１／Ｐ（ｚ
）の値を求め、ｒ’（０，７）に格納する。ｒ’（０，
７）を初期値として後方繰り返し演算を開始する。この
時点のＲＡＭ１１２の状態を示したのが表３．２である
ｊ＝６の値は不要なので、この領域を状態時刻５−に対
する作業領域とし、実施例３と同様に後方繰りかえし演
算を実行する。これにより時刻ｊの復号結果として得ら
れる確度情報はＰ（ｕ、　、　ｚ）／Ｐ（ｚ）＝Ｐ（ｕ
＋ｌｚ）となる。これはｕ　ｊ＝１である確率と、０で
ある確率の和が常に１となることを意味する。

従って特に規格化等を施すことなく、直ちに当該ビット
の信頼度を評価することか可能である。また本演算処理
によってトレリスの初期処理、終端処理に影響が及ぶこ
とはない。

（応用例） 次に本発明の応用例について述べる。実施例１゜２は最
小ビット誤り復号アルゴリズムに基づいた、・情報ビッ
トを決定する復号器を、実施例３は同アルゴリズムを用
いて情報ビットを決定したとき、その確度情報を与える
復号器を示した。この２者は容易に組み合せることがで
きる。その際には、情報ビットを決定した上にどの程度
当該ビットに関する確度が高いかの情報を含んだ復号器
を構成することができる。また本実施例では簡単のため
、符号化率Ｒ＝　１／２の時不変たたみ込み符号による
実現例のみを示したか、他の符号化率を有するたたみ込
み符号や、時変のたたみ込み符号、さらにはパンクチャ
ド符号に対しても本発明は全く同様に適用できる他、線
型ブロック符号に値しても本発明の適用は容易である。

このように本発明は、符号語が終端されていること以外
にはほとんど符号に対する拘束が存在しない。従って、
既に存在している通信システムに対しても、システムの
符号仕様、送信側の装置に何ら変更を行うことなく、受
信側の装置変更のみて本発明の実現か可能であるので、
本発明は極めて容易、円滑に既システムに導入できる。

また、本発明による誤り訂正復号方式は、同一発明者か
同日出願している「二重復号方式」の最小ビット誤り復
号器に適用すれば極めて有効である。

（発明の効果） 本発明方式を用いると、受信系列の全ての時刻に対して
同一のアルゴリズムを繰りかえし行うだけで復号が行え
るため、ハードウェア実現が容易になる。また本発明に
よる復号方式は、本来なら前方繰りかえし演算、後方繰
りかえし演算に別々のメモリを用いる必要があったもの
が一個のメモリにより復号を行うことができるのでメモ
リの削減効果が大きい。また復号に用いるメトリックテ
ーブルの規格化を行うことにより、実数積和演算に伴う
レジスタのオーバーフローやアンダーフローの発生を抑
えることができる。さらに本発明により、最小ビット誤
り復号アルゴリズムを実施する上で、伝送路の状態に最
も合致したメトリックのパラメータを選び出すことかて
きるという効果を持つ。さらに本発明では全復号ステッ
プ中に除算を１回加えるだけで、任意の時刻ｉにおける
復号結果の信頼度情報Ｐ（ｕ、　ｌ　ｚ）を正しく得ら
れる。

従ってこの値に基づき消失判定や軟判定情報を後段の復
号器や端末に容易に渡すことかできる。本発明により実
現される復号器は、与えられた受信系列の下ではビット
誤り率を最も小さくする復号器であることが文献（１）
により明らかにされている。このような復号器の実現に
より通信の信頼性を向上させる効果は大きいと考えられ
る。

【図面の簡単な説明】

第１図は本発明による第１の実施例を示すブロック図、
第２図は拘束長■＝２．符号化率Ｒ＝　１／またたみ込
み非組織符号器の例を示すブロック図、第３図は第２図
の符号器によって構成されるトレリス線図、第４図は本
発明の第２の実施例を示すブロック図、第５図は本発明
による第３の実施例を示すブロック図である。 １００・・・軟判定受信系列、 １０１・・・復号データ出力、 １１０・・・受信系列格納ＲＡＭ、 ｉｌｌ・・・メトリック用ＲＯＭ。 １１２・・・復号用演算ＲＡＭ、 １１３・・・復号結果格納ＲＡＭ、 １２０・・・アドレス用補助レジスタ、１２１・・・乗
算器入力用レジスタ、 １２２・・・アキュムレータ、 １２３・・・ステータスレジスタ １３０・・・マルチプレクサ、 １４０・・・乗算器、 １４１・・・加減算器、 １４２・・・ＲＯＭアドレス演算部、 ２００・・・情報ビット入力端子、 ２１０・・・符号化出力端子１． ２１１・・・符号化出力端子２． ２１３・・・１タイムスロツト遅延素子、２１４・・・
１タイムスロツト遅延素子、１５ １６ ００ ０１ １０ １１ １２ １３ ２０ ２１ ２２ ２３ ２４ ３０ ３１ ４０ ４１ ４２ ５０ ５１ ・・・モジュロ２加算回路、 ・・・モジュロ２加算回路、 ・・・軟判定受信系列、 ・・・復号データ出力、 ・・・受信系列格納ＲＡＭ、 ・・・メトリック用ＲＯＭ。 ・・・復号用演算ＲＡＭ、 ・・・復号結果格納ＲＡＭ、 ・・・アドレス用補助レジスタ、 ・・・乗算器入力用レジスタ、 ・・・アキュムレータ、 ・・・ステータスレジスタ、 ・・・レジスタ、 ・・・マルチプレクサ、 ・・・マルチプレクサ、 ・・・乗算器、 ・・・加減算器、 ・・・ＲＯＭアドレス演算部、 ・・・軟判定重み情報（ＭＳＢを除く）、・・・軟判定
情報（ＭＳＢを含む）、 ００ ０１ １０ １１ １２ １３ ２０ ２１ ２２ ３０ ４０ ４１ ４２ ・・・軟判定受信系列、 ・・・確度情報系列、 ・・・受信系列格納ＲＡＭ、 ・・・メトリック　用ＲＯＭ。 ・・・復号用演算ＲＡＭ、 ・・・確度情報格納ＲＡＭ、 ・・・アドレス用補助レジスタ、 ・・・乗算器入力用レジスタ、 ・・・アキュムレータ、 ・・・マルチプレクサ、 ・・・乗算器、 ・・・加減算器、 ・・・ＲＯＭアドレス演算部。

Claims (1)

1. 【特許請求の範囲】 （１）各トレリス上の尤度計算を受信時刻の早いビット
   から受信時刻の遅いビットの方向に前方繰りかえし演算
   により行った後に逆方向に後方繰りかえし演算を行うか
   、または該後方繰りかえし演算を行った後に該前方繰り
   かえし演算を行うことによってビット誤りを最小とする
   誤り訂正符号の復号方式において、 前記前方あるいは後方の繰りかえし演算を行った際用い
   た作業用記憶領域を逆方向の繰りかえし演算において再
   度使用して復号を行うことを特徴とする誤り訂正符号の
   復号方式。（２）前記尤度計算に用いるための枝メトリ
   ックの全ての要素に、ある一定値をあらかじめ乗算して
   規格化しておくことにより、復号演算器のオーバーフロ
   ーおよびアンダーフローを防ぐことを特徴とする請求項
   （１）記載の誤り訂正符号の復号方式。 （３）前記受信系列に対する軟判定復調データが与えら
   れている場合に、該復号すべき受信系列の重み情報より
   伝送路状態を推定し、この推定値に基づいて前記の規格
   値を決定して、復号演算器のオーバーフローおよびアン
   ダーフローを防ぐことを特徴とする請求項（２）記載の
   誤り訂正符号の復号方式。 （４）前記受信系列に対する軟判定復調データが与えら
   れている場合に、該復号すべき受信系列の重み情報より
   伝送路状態を推定し、この推定値に基づいて適切なメト
   リック表を選択して、精度の良い復号を行うことを特徴
   とする請求項（１）記載の誤り訂正符号の復号方式。 （５）前記前方あるいは後方の繰りかえし演算が終了し
   た時点で、当該受信系列の生起確率の推定を行い、この
   値の逆数を初期値として逆方向の繰りかえし演算を行う
   ことを特徴とする請求項（１）記載の誤り訂正符号の復
   号方式。 （６）前記前方あるいは後方の繰りかえし演算が終了し
   た時点で、当該受信系列の生起確率の推定を行い、この
   値の逆数を初期値として逆方向の繰りかえし演算を行い
   、これによって得られる復号ビットの確度情報を出力す
   ることを特徴とする請求項（１）記載の誤り訂正符号の
   復号方式。