(57)【特許請求の範囲】
【請求項１】
符号化器によって発生されるテイルバイティング格子コードがＭ個の符号化器状態を持つときに、時刻ｔにおける符号化器状態Ｓtがｍであり且つ値Ｙ1L＝｛ｙ1，．．．，ｙL｝を持つＬ個のチャネル出力のシーケンスが受信される結合確率λt（ｍ）＝Ｐ｛Ｓt＝ｍ；Ｙ1L｝を決定することにより、テイルバイティング格子コードを復号する復号器であって、当該復号器がＬ個の格子レベルの各々に１つずつあるＬ個の確率行列Γtを決定し、この確率行列の要素は、ｊ＝０，１，．．．，（Ｍ−１）に対して、次の式
Γt（ｉ，ｊ）＝Ｐ｛時刻ｔの状態ｊ；ｙt／時刻（ｔ−１）の状態ｉ｝
によって定義され、また、次の式
αt（ｊ）＝Ｐ｛時刻ｔの状態ｊ；ｙ1，．．．，ｙt｝
によって定義されるＭ個の結合確率要素を持つ行ベクトルαtを決定すると共に、次の式
βt（ｊ）＝Ｐ｛ｙt+1，．．．ｙL／時刻ｔの状態ｊ｝
によって定義されるＭ個の条件付き確率要素を持つ列ベクトルβtを決定するように作用する当該復号器において、
前記チャネル出力と、チャネル遷移確率Ｒ（Ｙt，Ｘ）と、時刻ｔに符号化器が状態ｍ′からｍに遷移する確率ｐt（ｍ／ｍ′）と、符号化器の前の状態がｍ′であり且つ符号化器の現在の状態がｍであるとして、符号化器の出力記号がＸである確率ｑt（Ｘ／ｍ′，ｍ）とを受け取って、前記確率行列Γtのスカラー要素を決定するΓt計算器と、
前記Γt計算器から前記スカラー要素を受取って、行列積Γ1Γ2．．．ΓLを計算するΓt行列積計算器と、
前記行列積Γ1Γ2．．．ΓLを受取って、該行列積の最大の固有値Ｐ｛Ｙ1L｝に対応する正規化固有ベクトルα0を計算する正規化固有ベクトル・コンピュータと、
前記正規化固有ベクトルα0受取って、次の式
αt＝αt-1Γt          ；ｔ＝１，．．．，Ｌ
に示すような前向きの再帰法によって相次ぐαtを形成するαt行列積計算器と、
前記確率行列Γt及び前記行ベクトルαtを記憶するメモリと、
βL＝（１，１，．．．，１）Tを初期設定すると共に、次の式
βt＝Γt+1βt+1；ｔ＝Ｌ−１、．．．、１
によって示す後ろ向き再帰法により、先行するβtを形成することによって、前記列ベクトルを発生するβt行列積計算器と、
次の式
λt（ｉ）＝αt（ｉ）βt（ｉ）；全てのｉ及びｔ＝１，．．，Ｌに対し
に示すように前記行ベクトルの要素に前記列ベクトルの要素を乗算することによって、その要素が結合確率λt（ｉ、ｊ）である結合確率ベクトルλtを形成する要素毎の積の計算器と、
時刻ｔに符号化器に入力される所定のデータ・ビットがｋデータ・ビットの内のｍ番目であるとして、このデータ・ビットが０に等しい確率をλtから決定すると共に、該確率の関数としてソフト出力を発生する復号ビット値確率計算器と、を有している復号器。
【請求項２】
符号化器によって発生されるテイルバイティング格子コードがＭ個の符号化器状態を持つときに、時刻ｔにおける符号化器状態Ｓtがｍであり且つ値Ｙ1L＝｛ｙ1，．．．，ｙL｝を持つＬ個のチャネル出力のシーケンスが受信される結合確率λt（ｍ）＝Ｐ｛Ｓt＝ｍ；Ｙ1L｝を決定することにより、テイルバイティング格子コードを復号する復号器であって、当該復号器がＬ個の格子レベルの各々に１つずつあるＬ個の確率行列Γtを決定し、この確率行列の要素は、ｊ＝０，１，．．．，（Ｍ−１）に対して、次の式
Γt（ｉ，ｊ）＝Ｐ｛時刻ｔの状態ｊ；ｙt／時刻（ｔ−１）の状態ｉ｝
によって定義され、また、次の式
αt（ｊ）＝Ｐ｛時刻ｔの状態ｊ；ｙ1，．．．，ｙt｝
によって定義されるＭ個の結合確率要素を持つ行ベクトルαtを決定すると共に、次の式
βt（ｊ）＝Ｐ｛ｙt+1，．．．ｙL／時刻ｔの状態ｊ｝
によって定義されるＭ個の条件付き確率要素を持つ列ベクトルβtを決定するように作用する当該復号器において、
前記チャネル出力と、チャネル遷移確率Ｒ（Ｙt，Ｘ）と、時刻ｔに符号化器が状態ｍ′からｍに遷移する確率ｐt（ｍ／ｍ′）と、符号化器の前の状態がｍ′であり且つ符号化器の現在の状態がｍであるとして、符号化器の出力記号がＸである確率ｑt（Ｘ／ｍ′，ｍ）とを受け取って、前記確率行列Γtのスカラー要素を決定するΓt計算器と、
前記Γt計算器から前記スカラー要素を受取って、前記行ベクトルαtを発生するαt行列積計算器と、
前記列ベクトルβtを発生するβt行列積計算器と、
その要素が結合確率λt（ｉ、ｊ）である結合確率ベクトルλtを形成する要素毎の積の計算器とを有し、
前記αt行列積計算器、前記βt行列積計算器、及び前記要素毎の積の計算器は、それぞれ次に示すように前記ベクトルαt、βt及びλtを計算し、すなわち、
（ｉａ）（１／Ｍ，．．．，１／Ｍ）に等しい最初のα0から出発して、下記の再帰法
αt＝αt-1Γt          ；ｔ＝１，．．，Ｌ
をＬ回計算し、その結果を正規化して、各々のαtの要素の和が１になるようにし、Ｌ個の全てのαtベクトルを残し、
（ｉｂ）α0をステップ（ｉａ）からのαLに等しいとして、ｔ＝１から出発して、Ｌwminを格子の段の予定の最小数として、次の式
αt＝αt-1Γt          ；ｔ＝１，．．．，Ｌwmin
を計算し、その結果を正規化して、各々のαtの要素の和が１になるようにし、ステップ（ｉａ）及び（ｉｂ）における再帰法によって見いだされた最も最近の１組のＬ個のαt並びにステップ（ｉａ）で見いだされたαLwminだけを残し、
（ｉｃ）ステップ（ｉｂ）からのαLwminをステップ（ｉａ）で見いだされたαLwminと比較して、許容範囲内であればステップ（ｉｉ）へ進み、そうでなければステップ（ｉｄ）へ続き、
（ｉｄ）ｔ＝ｔ＋１として、αt＝αtΓtを計算し、再帰法の結果を正規化して、各々のαtの要素の和が１になるようにし、計算されたＬ個のαtの一番最近の組だけ並びに前にステップ（ｉａ）で見いだされたαtだけを残し、
（ｉｅ）前記αtを、ステップ（ｉａ）、（ｉｂ）及び（ｉｄ）で前に計算された一番最近のαtと比較し、許容範囲内であればステップ（ｉｉ）へ進み、一番最近の２つのベクトルが前記許容範囲内で一致しないで再帰法の回数が予定の最大値を超えない場合はステップ（ｉｄ）に続き、それ以外の場合はステップ（ｉｉ）へ進み、
（ｉｉ）βL＝（１，１，．．．，１）Tと初期設定し、次の式
βt＝Γt+1βt+1          ；ｔ＝Ｌ−１，．．．，１
に示す後ろ向き再帰法により先行するβtを形成し、その再帰法の結果を正規化して、各々のβtの要素の和が１になるようにし、Ｌ個のβtベクトルの全部を残し、
（ｉｉｉ）前記行ベクトルの要素と前記列ベクトルの要素を次の式
λt（ｉ）＝αt（ｉ）βt（ｉ）；全てのｉ及びｔ＝１，．．．．．，Ｌに対し
に示すように乗算することにより、その要素が前記結合確率λtである結合確率ベクトルλtを形成し、
更に、前記確率行列及び前記行ベクトルを記憶するメモリと、
時刻ｔに符号化器に入力される所定のデータ・ビットがｋデータ・ビットの内のｍ番目であるとして、この所定のデータ・ビットが０に等しい確率を前記λtから決定して、該確率の関数としてソフト出力を発生する復号ビット値確率計算器と、を有している復号器。
【請求項３】
符号化器によって発生されるテイルバイティング格子コードがＭ個の符号化器状態を持つときに、時刻ｔにおける符号化器状態Ｓtがｍであり且つ値Ｙ1L＝｛ｙ1，．．．，ｙL｝を持つＬ個のチャネル出力のシーケンスが受信される結合確率λt（ｍ）＝Ｐ｛Ｓt＝ｍ；Ｙ1L｝を決定することにより、テイルバイティング格子コードを復号する復号器であって、当該復号器がＬ個の格子レベルの各々に１つずつあるＬ個の確率行列Γtを決定し、この確率行列の要素は、ｊ＝０，１，．．．，（Ｍ−１）に対して、次の式
Γt（ｉ，ｊ）＝Ｐ｛時刻ｔの状態ｊ；ｙt／時刻（ｔ−１）の状態ｉ｝
によって定義され、また、次の式
αt（ｊ）＝Ｐ｛時刻ｔの状態ｊ；ｙ1，．．．，ｙt｝
によって定義されるＭ個の結合確率要素を持つ行ベクトルαtを決定すると共に、次の式
βt（ｊ）＝Ｐ｛ｙt+1，．．．ｙL／時刻ｔの状態ｊ｝
によって定義されるＭ個の条件付き確率要素を持つ列ベクトルβtを決定するように作用する当該復号器において、
前記チャネル出力と、チャネル遷移確率Ｒ（Ｙt，Ｘ）と、時刻ｔに符号化器が状態ｍ′からｍに遷移する確率ｐt（ｍ／ｍ′）と、符号化器の前の状態がｍ′であり且つ符号化器の現在の状態がｍであるとして、符号化器の出力記号がＸである確率ｑt（Ｘ／ｍ′，ｍ）とを受け取って、前記確率行列Γtのスカラー要素を決定するΓt計算器と、
前記Γt計算器から前記スカラー要素を受取って、前記行ベクトルαtを発生するαt行列積計算器と、
前記列ベクトルβtを発生するβt行列積計算器と、
結合確率ベクトルλtを計算する要素毎の積の計算器とを有し、
前記αt行列積計算器、前記βt行列積計算器、及び前記要素毎の積の計算器は、それぞれ次に示すように前記ベクトルαt、βt及びλtを計算し、すなわち、
（ｉａ）（１／Ｍ，．．．，１／Ｍ）に等しい最初のα0から出発して、下記の前向きの再帰法
αt＝αt-1Γt          ；ｔ＝１，．．，Ｌ
をＬ回計算し、その結果を正規化して、各々のαtの要素の和が１になるようにし、Ｌ個の全てのαtベクトルを残し、
（ｉｂ）α0をステップ（ｉａ）からのαLに等しいとして、ｔ＝１から出発して、ラップ深さＬwを格子の段の所定の最小数として、次の式
αt＝αt-1Γt          ；ｔ＝１，．．．，Ｌw
を計算し、その結果を正規化して、各々のαtの要素の和が１になるようにし、ｔ＝１，．．．，Ｌwに対し、ステップ（ｉａ）で計算したαtをステップ（ｉｂ）で計算されたαtに置き換え、
（ｉｉａ）βL＝（１，１，１，．．．，１）Tと初期設定し、次の式
βt＝Γt+1βt+1          ；ｔ＝Ｌ−１，．．．，１
で示す後ろ向き再帰法により、先行するβtを計算し、この再帰法の結果を正規化して、各々のβtの要素の和が１になるようにし、Ｌ個の全てのβtベクトルを残し、
（ｉｉｂ）βL+1をステップ（ｉｉａ）からのβ1に等しいとすると共に、ΓL+1＝Γ1と置いて、ｔ＝Ｌから開始して、ラップ深さＬwを格予段の所定の数として、次の式
βt＝Γt+1βt+1          ；ｔ＝Ｌ，（Ｌ−１），．．．，Ｌ−（Ｌw＋１）
を計算し、この再帰法の結果を正規化して、各々のβtの要素の和を１にし、ｔ＝Ｌ，（Ｌ−１），．．．，Ｌ−（Ｌw＋１）に対し、ステップ（ｉｉａ）で計算されたβｔをステップ（ｉｉｂ）で計算されたβtに置き換え、
（ｉｉｉ）次の式
λt（ｉ）＝αt（ｉ）βt（ｉ）；全てのｉ及びｔ＝１，．．．．．，Ｌに対して
に示すように行ベクトルの要素と列ベクトルの要素を乗算することにより、その要素が結合確率λt（ｉ、ｊ）である結合確率ベクトルλtを形成し、
更に、前記確率行列及び前記行ベクトルを記憶するメモリと、
時刻ｔに符号化器に入力される所定のデータ・ビットが、ｋデータ・ビットの内のｍ番目であるとして、該所定のデータ・ビットが０に等しい確率をλtから決定すると共に、該確率の関数としてソフト出力を発生する復号ビット値確率計算器と、
を有している復号器。
【請求項４】
符号化器によって発生されるテイルバイティング格子コードがＭ個の符号化器状態を持つときに、時刻ｔにおける符号化器状態Ｓtがｍであり且つ値Ｙ1L＝｛ｙ1，．．．，ｙL｝を持つＬ個のチャネル出力のシーケンスが受信される結合確率λt（ｍ）＝Ｐ｛Ｓt＝ｍ；Ｙ1L｝を決定することにより、テイルバイティング格子コードを復号する復号方法であって、当該復号方法がＬ個の格子レベルの各々に１つずつあるＬ個の確率行列Γtを決定し、この確率行列の要素は、ｊ＝０，１，．．．，（Ｍ−１）に対して、次の式
Γt（ｉ，ｊ）＝Ｐ｛時刻ｔの状態ｊ；ｙt／時刻（ｔ−１）の状態ｉ｝
によって定義され、また、次の式
αt（ｊ）＝Ｐ｛時刻ｔの状態ｊ；ｙ1，．．．，ｙt｝
によって定義されるＭ個の結合確率要素を持つ行ベクトルαtを決定すると共に、
次の式
βt（ｊ）＝Ｐ｛ｙt+1，．．．ｙL／時刻ｔの状態ｊ｝
によって定義されるＭ個の条件付き確率要素を持つ列ベクトルβtを決定するステップを含んでいる当該復号方法において、
符号化器の前の状態がｍ′であり且つ符号化器の現在の状態がｍであるとして、前記チャネル出力と、チャネル遷移確率Ｒ（Ｙt，Ｘ）と、時刻ｔに符号化器が状態ｍ′からｍに遷移する確率ｐt（ｍ／ｍ′）と、符号化器の出力記号がＸである確率ｑt（Ｘ／ｍ′，ｍ）とを受け取って、前記確率行列Γtのスカラー要素を決定し、
前記Γtのスカラー要素から行列積Γ1Γ2．．．ΓLを計算し、
前記行列積Γ1Γ2．．．ΓLの最大の固有値Ｐ｛Ｙ1L｝に対応する正規化固有ベクトルα0を計算し、
次の式
αt＝αt-1Γt          ；ｔ＝１，．．．，Ｌ
に示すような前向きの再帰法によって相次ぐαｔを形成し、
βL＝（１，１，．．．，１）Tを初期設定すると共に、次の式
βt＝Γt+1βt+1          ；ｔ＝Ｌ−１、．．．、１
によって示す後ろ向き再帰法により、先行するβtを形成することによって、前記列ベクトルを発生し、
次の式
λt（ｉ）＝αt（ｉ）βt（ｉ）    ；全てのｉ及びｔ＝１，．．．．．，Ｌに対して
に示すように前記行ベクトルの要素に前記列ベクトルの要素を乗算することによって、その要素が結合確率λt（ｉ、ｊ）である結合確率ベクトルλtを形成し、時刻ｔに符号化器に入力される所定のデータ・ビットが、ｋデータ・ビットの内のｍ番目であるとして、このデータ・ビットが０に等しい確率をλtから決定すると共に、該確率の関数としてソフト出力を発生するステップを含んでいる復号方法。
【請求項５】
符号化器によって発生されるテイルバイティング格子コードがＭ個の符号化器状態を持つときに、時刻ｔにおける符号化器状態Ｓtがｍであり且つ値Ｙ1L＝｛ｙ1，．．．，ｙL｝を持つＬ個のチャネル出力のシーケンスが受信される結合確率λt（ｍ）＝Ｐ｛Ｓt＝ｍ；Ｙ1L｝を決定することにより、テイルバイティング格子コードを復号する復号方法であって、当該復号方法がＬ個の格子レベルの各々に１つずつあるＬ個の確率行列Γtを決定し、この確率行列の要素は、ｊ＝０，１，．．．，（Ｍ−１）に対して、次の式
Γt（ｉ，ｊ）＝Ｐ｛時刻ｔの状態ｊ；ｙt／時刻（ｔ−１）の状態ｉ｝
によって定義され、また、次の式
αt（ｊ）＝Ｐ｛時刻ｔの状態ｊ；ｙ1，．．．，ｙt｝
によって定義されるＭ個の結合確率要素を持つ行ベクトルαtを決定すると共に、次の式
βt（ｊ）＝Ｐ｛ｙt+1，．．．ｙL／時刻ｔの状態ｊ｝
によって定義されるＭ個の条件付き確率要素を持つ列ベクトルβtを決定するステップを含んでいる当該復号方法において、
符号化器の前の状態がｍ′であり且つ符号化器の現在の状態がｍであるとして、前記チャネル出力と、チャネル遷移確率Ｒ（Ｙt，Ｘ）と、時刻ｔに符号化器が状態ｍ′からｍに遷移する確率ｐt（ｍ／ｍ′）と、符号化器の出力記号がＸである確率ｑt（Ｘ／ｍ′，ｍ）とを受け取って、前記確率行列Γtのスカラー要素を決定し、
それぞれ次に示すようにベクトルαt、β、及びλtを計算し、すなわち、
（ｉａ）（１／Ｍ，．．．，１／Ｍ）に等しい最初のα0から出発して、下記の前向きの再帰法
αt＝αt-1Γt          ；ｔ＝１，．．，Ｌ
をＬ回計算し、その結果を正規化して、各々のαtの要素の和が１になるようにし、Ｌ個の全てのαtベクトルを残し、
（ｉｂ）α0をステップ（ｉａ）からのαLに等しいとして、ｔ＝１から出発して、Ｌwminを格子の段の予定の最小数として、次の式
αt＝αt-1Γt          ；ｔ＝１，．．．，Ｌwmin
を計算し、その結果を正規化して、各々のαtの要素の和が１になるようにし、ステップ（ｉａ）及び（ｉｂ）における再帰法によって見いだされた最も最近の１組のＬ個のαt並びにステップ（ｉａ）で見いだされたαLwminだけを残し、
（ｉｃ）ステップ（ｉｂ）からのαLwminをステップ（ｉａ）で見いだされたαLwminと比較して、許容範囲内であればステップ（ｉｉ）へ進み、そうでなければステップ（ｉｄ）へ続き、
（ｉｄ）ｔ＝ｔ＋１として、αt＝αt-1Γtを計算し、再帰法の結果を正規化して、各々のαtの要素の和が１になるようにし、計算されたＬ個のαtの一番最近の組だけ並びに前にステップ（ｉａ）で見いだされたαtだけを残し、
（ｉｅ）前記αtを、ステップ（ｉａ）、（ｉｂ）及び（ｉｄ）で前に計算された一番最近のαtと比較し、許容範囲内であればステップ（ｉｉ）へ進み、一番最近の２つのベクトルが前記許容範囲内で一致しないで再帰法の回数が予定の最大値を超えない場合はステップ（ｉｄ）に続き、それ以外の場合はステップ（ｉｉ）へ進み、
（ｉｉ）βL＝（１，１，．．．，１）Tと初期設定し、次の式
βt＝Γt+1βt+1          ；ｔ＝Ｌ−１，．．．，１
に示す後ろ向き再帰法により先行するβtを形成し、その再帰法の結果を正規化して、各々のβtの要素の和が１になるようにし、Ｌ個のβtベクトルの全部を残し、
（ｉｉｉ）前記行ベクトルの要素と前記列ベクトルの要素を次の式
λt（ｉ）＝αt（ｉ）βt（ｉ）；全てのｉ及びｔ＝１，．．．．．，Ｌに対し
に示すように乗算することにより、その要素が結合確率λt（ｉ，ｊ）である結合確率ベクトルλtを形成し、
更に、時刻ｔに符号化器に入力される所定のデータ・ビットがｋデータ・ビットの内のｍ番目であるとして、この所定のデータ・ビットが０に等しい確率を前記λtから決定して、該確率の関数としてソフト出力を発生するステップを含んでいる復号方法。
【請求項６】
符号化器によって発生されるテイルバイティング格子コードがＭ個の符号化器状態を持つときに、時刻ｔにおける符号化器状態Ｓtがｍであり且つ値Ｙ1L＝｛ｙ1，．．．、ｙL｝を持つＬ個のチャネル出力のシーケンスが受信される結合確率λt（ｍ）＝Ｐ｛Ｓt＝ｍ；Ｙ1L｝を決定することにより、テイルバイティング格子コードを復号する復号方法であって、当該復号方法がＬ個の格子レベルの各々に１つずつあるＬ個の確率行列Γtを決定し、この確率行列の要素は、ｊ＝０，１，．．．，（Ｍ−１）に対して、次の式
Γt（ｉ，ｊ）＝Ｐ｛時刻ｔの状態ｊ；ｙt／時刻（ｔ−１）の状態ｉ｝
によって定義され、また、次の式
αt（ｊ）＝Ｐ｛時刻ｔの状態ｊ；ｙ1，．．．，ｙt｝
によって定義されるＭ個の結合確率要素を持つ行ベクトルαtを決定すると共に、次の式
βt（ｊ）＝Ｐ｛ｙt+1，．．．ｙL／時刻ｔの状態ｊ｝
によって定義されるＭ個の条件付き確率要素を持つ列ベクトルβtを決定するステップを含んでいる当該復号方法において、
符号化器の前の状態がｍ′であり且つ符号化器の現在の状態がｍであるとして、前記チャネル出力と、チャネル遷移確率Ｒ（Ｙt，Ｘ）と、時刻ｔに符号化器が状態ｍ′からｍに遷移する確率ｐt（ｍ／ｍ′）と、符号化器の出力記号がＸである確率ｑt（Ｘ／ｍ′，ｍ）とを受け取って、前記確率行列Γtのスカラー要素を決定し、
それぞれ次に示すようにベクトルαt、β、及びλtを計算し、すなわち、
（ｉａ）（１／Ｍ，．．．，１／Ｍ）に等しい最初のα0から出発して、下記の前向きの再帰法
αt＝αt-1Γt          ；ｔ＝１，．．，Ｌ
をＬ回計算し、その結果を正規化して、各々のαtの要素の和が１になるようにし、Ｌ個の全てのαtベクトルを残し、
（ｉｂ）α0をステップ（ｉａ）からのαLに等しいとして、ｔ＝１から出発して、ラップ深さＬwを格予の段の所定の最小数として、次の式
αt＝αt-1Γt          ；ｔ＝１，．．．，Ｌw
を計算し、その結果を正規化して、各々のαtの要素の和が１になるようにし、ｔ＝１，．．．，Ｌwに対し、ステップ（ｉａ）で計算したαtをステップ（ｉｂ）で計算されたαtに置き換え、
（ｉｉａ）βL＝（１，１，１，．．．，１）Tと初期設定し、次の式
βt＝Γt+1βt+1          ；ｔ＝Ｌ−１，．．．，１
で示す後ろ向き再帰法により、先行するβtを計算し、この再帰法の結果を正規化して、各々のβtの要素の和が１になるようにし、Ｌ個の全てのβtベクトルを残し、
（ｉｉｂ）βL+1をステップ（ｉｉａ）からのβ1に等しいとすると共に、ΓL+1＝Γ1と置いて、ｔ＝Ｌから開始して、ラップ深さＬwを格子段の所定の数として、次の式
βt＝Γt+1βt+1    ；ｔ＝Ｌ，（Ｌ−１），．．．，Ｌ−（Ｌw＋１）
を計算し、この再帰法の結果を正規化して、各々のβtの要素の和を１にし、ｔ＝Ｌ，（Ｌ−１），．．．，Ｌ−（Ｌw＋１）に対し、ステップ（ｉｉａ）で計算されたβtをステップ（ｉｉｂ）で計算されたβtに置き換え、
（ｉｉｉ）次の式
λt（ｉ）＝αt（ｉ）βt（ｉ）；全てのｉ及びｔ＝１，．．．．．，Ｌに対して
に示すように行ベクトルの要素と列ベクトルの要素を乗算することにより、その要素が結合確率λtである結合確率ベクトルλtを形成し、
更に、時刻ｔに符号化器に入力される所定のデータ・ビットがｋデータ・ビットの内のｍ番目であるとして、該所定のデータ・ビットが０に等しい確率をλtから決定すると共に、該確率の関数としてソフト出力を発生するステップを含んでいる復号方法。
【発明の詳細な説明】
発明の分野
本発明は全般的に誤り訂正コードに対する復号器に関し、更に具体的に云えば、テイルバイティング格子（ｔａｉｌ−ｂｉｔｉｎｇ  ｔｒｅｌｌｉｓ）コードに対する復号器に関する。
発明の背景
ビテルビ・アルゴリズム（ＶＡ：Ｖｉｔｅｒｂｉ  ａｌｇｏｒｉｔｈｍ）は、相加的ホワイト・ガウスチャネル雑音の場合に最も確率の高いデータ・シーケンス又はワードを決定する最大尤度復号法であり、復号ワード誤りの確率を最小にする。この方式は、本質的には、受信したチャネル出力のシーケンスに最も近いコード格子内のパス（ｐａｔｈ）を見つけるダイナミック・プログラムである。
他方、記号（ｓｙｍｂｏｌ）又はビット誤り確率が、いわゆる最大帰納的（ＭＡＰ：ｍａｘｉｍｕｍ  ａ  ｐｏｓｔｅｒｉｏｒｉ）復号器を使うことによって最小にされる。ＭＡＰ復号器は最初にＩＥＥＥ・トランザクションズ・オン・インフォーメーション・セオリ誌１９７４年３月号、２８４−２８７頁所載のバール、コック、ジェリネク及びラビブ（その頭文字を取ってＢＣＪＲアルゴリズムとも云う）の論文「記号誤り率を最小にする線形コードの最適復号（Ｏｐｔｉｍａｌ  Ｄｅｃｏｄｉｎｇ  ｏｆ  Ｌｉｎｅａｒ  Ｃｏｄｅｓ  ｆｏｒ  Ｍｉｎｉｍｉｚｉｎｇ  Ｓｙｍｂｏｌ  Ｅｒｒｏｒ）」」に公式に記載されている。ＭＡＰ復号器又はＢＣＪＲアルゴリズムという名称は、ここでは、格子の各段に於ける状態の確率分布を出すデータ復号器を意味するものとして用いるが、この復号器はデータ・ビット統計の先験的情報をも取り入れることが出来る。ＭＡＰ復号器は、完全な精度で状態確率又は「ソフト出力」を発生するという意味で最適であり、これに対して、これより簡単である他の復号器も存在するが、それはこういう確率の近似しか得ることが出来ない。このアルゴリズムの変形が、各段におけるデータ記号の確率分布又は各段における符号化器出力信号の分布のような関連する情報を出す。
ＭＡＰ復号器は、格子コードの送信の出発状態が判っていることを必要とし、用途によっては終端状態も判っていることを必要とする。その為、都合の悪いことに、ＭＡＰ復号器はテイルバイティングような格子コード、すなわち符号化器の出発状態及び終端状態を前もって知ることが出来ないようなコードを復号する為に使うことが出来ない。詳しく云うと、入力ビットの所定ブロックに対し、符号化器の出発状態が最終的な終端状態と同一であるとき、格子コードの伝送は「テイルバイティング（ｔａｉｌ−ｂｉｔｉｎｇ）」という。前送り（フィードフォワード）符号化器では、終端状態がどうなるかはデータ・ビットから簡単に判る。それは単に、ｋを符号化器の入力記号当たりのビット数、ｍをコードのメモリとして、メッセージ・ブロックの最後のｋｍビットである。テイルバイティング符号化器は、出発状態が予め決められた状態であって、普通は全部０の状態である普通の符号化器と区別しなければならない。普通の符号化器も、入力メッセージ・ブロックにｋｍビットの「テイル（ｔａｉｌ）」を付け加えることにより、予め決められた状態で終了することが出来る。テイルバイティング復号器が区別されるのは、それが他の機能の他に、符号化器の出発状態を推定しなければならないことである。テイルバイティング符号化器は円筒形格子を持っているから、この符号化器によって発生されたコードワードは、記号の円として視覚化することが出来る。符号化器は円上の任意の点から出発して、ある程度の同期を達成し、その後にデータ・ビットを復号しなければならない。
ＶＡ復号器と類似した多数のテイルバイティング復号器が提案されている、すなわち、これらは円形格子コードワードの最大尤度推定値を発生する。他方、ソフト出力復号器は、円筒形格子に沿った状態確率を推定しなければならないが、今日、このような復号器は利用出来ない。特に、前に説明したように、ソフト出力ＭＡＰ復号器は、格子内の出発状態が判っていることを必要とすると共に、用途によっては終端状態も判っていることを必要とする。従って、ＭＡＰ復号器の応用は、テイルバイティングことがない普通のコードに制限されており、この為、真のソフト出力を必要とするとき、短いデータ・ブロックを送信する装置（例えばパケット伝送）の誤り訂正性能を改善する上でのテイルバイティング特徴の利点を達成することが出来ない。
従って、テイルバイティング格子コードに対する正確で複雑さの少ないソフト出力復号器を提供することが望ましい。
発明の概要
本発明による、テイルバイティング特徴を用いた誤り訂正格子コードに対する円形ＭＡＰ復号器は、ソフト判定出力を発生する。この円形ＭＡＰ復号器は、格子の第１段における状態の確率の推定値を発生し、これらの確率は従来のＭＡＰ復号器における出発状態の先験的情報の代わりとなるものである。本発明では、円形ＭＡＰ復号器は、２通りの方法の何れかで初期状態確率分布を発生する。その１番目は、その結果として得られる固有ベクトルが所望の初期状態確率分布であるような固有値問題を解くことである。出発状態が判っていると、円形ＭＡＰ復号器は残りの復号をＭＡＰ復号アルゴリズムに従って遂行する。２番目は、繰返しが出発状態の分布に収斂する再帰法に基づく。十分な繰返しをすれば、状態の円形シーケンス上の状態が高い確率で判り、円形ＭＡＰ復号器は残りの復号をＭＡＰ復号アルゴリズムに従って遂行する。
本発明の特徴及び利点は、以下図面について本発明を詳しく説明するところから明らかになろう。
【図面の簡単な説明】
第１図は、２進入力記号を持つ４状態のテイルバイティング格子コードに対する円筒形格子を示す。
第２図は、テイルバイティング格子コードに対する円形符号化器の状態及び符号化器の出力シーケンスを示す。
第３図は、本発明による１実施態様の円形ＭＡＰ復号器の簡略ブロック図である。
第４図は、本発明による円形ＭＡＰ復号器に対する時間線図である。
第５図は、本発明の好ましい実施態様による円形ＭＡＰ復号器の時間線図である。
第６図は、本発明に従ってレート＝１／２、メモリ＝６のテイルバイティング・コンボルーション・コードを復号するときの円形ＭＡＰ復号器のビット誤り率対信号対雑音比を示すグラフである。
第７図は、本発明に従ってレート＝１／２、メモリ＝６のテイルバイティング・コンボルーション・コードを復号する時の円形ＭＡＰ復号器に対するバイアス源統計を用いたビット誤り率対信号対雑音比を示すグラフである。
第８図は、本発明の好ましい実施態様の円形ＭＡＰ復号器の簡略ブロック図である。
発明の詳しい説明
テイルバイティング符号化器は円筒形格子を有する。この為、この符号化器によって発生されるコードワードは記号の円として視覚化することが出来る。第１図は、４つの状態及び２進入力記号を持つテイルバイティング格子符号化器に対する一例の円筒形格子を示す。このようなテイルバイティング格子コードの場合、符号化器の初期状態に関する先験的情報がない為、受信メッセージの最初の部分では、標準的なＭＡＰ復号アルゴリズム（すなわち、ＢＣＪＲアルゴリズム）による復号の信頼性が劣化する。
テイルバイティング格子コードに対する符号化器出力シーケンスは、第２図に示すような円形パターンを形成する。符号化器の状態は、円に沿って配置されているものとして視覚化されている。これらの状態の内の１つの状態がＳ0とすると、符号化器は時刻ｔ0にシフトレジスタの状態Ｓ0から符号化過程を開始し、一連の状態遷移で円に沿って進んだ後、同じ状態Ｓ0で終わる。このように円としての符号化シーケンスで動作して、各々の符号化器状態が円に沿って次の状態に続くような復号器は、テイルバイティング復号器又は円形復号器である。
本発明による、テイルバイティング形式の誤り訂正格子コードに対する円形ＭＡＰ復号器は、ソフト判定出力を発生する。対照的に、従来のＭＡＰ復号器では、復号器に出発状態又は格子コードが与えられ、その後、復号器がこの状態から下降する符号化器格子パスを復号する。然し、テイルバイティング復号器では、復号器は最初に符号化器状態シーケンス内の状態を確認しなければならない。そうして初めて復号を開始することが出来る。本発明の円形ＭＡＰ復号器は格子の第１段における状態の確率の推定値を発生する。こういう確率が、従来のＭＡＰ復号器における出発状態の先験的情報に代るものである。本発明の円形ＭＡＰ復号器は、２通りの方法の何れかで、初期状態確率分布を発生する。その１番目は、その結果として得られる固有ベクトルが所望の初期状態確率分布となるような固有値問題を解くことである。出発状態が判れば、円形ＭＡＰ復号器は残りの復号を従来のＭＡＰ復号アルゴリズム（すなわち、ＢＣＪＲアルゴリズム）に従って遂行する。２番目は、繰返しが出発状態分布に収斂するようなある再帰法に基づく方法である。十分な繰返しの後、状態の円形シーケンス上の状態が高い確率で判り、円形ＭＡＰ復号器が残りの復号を従来のＭＡＰ復号アルゴリズム（すなわち、ＢＣＪＲアルゴリズム）に従って遂行する。
従来のＭＡＰ復号アルゴリズム（すなわち、ＢＣＪＲアルゴリズム）の目的は、下記の条件付き確率を見つけることである。
Ｐ｛時刻ｔの状態ｍ／受信チャネル出力ｙ1，．．．，ｙL｝
この表式の項目Ｌは、符号化器の記号数を単位として表したデータ・ブロックの長さを表す。（ｎ，ｋ）コードに対する符号化器は、ｋビット入力記号に作用して、ｎビット出力記号を作成する。項ｙtは時刻ｔにおけるチャネル出力（記号）である。
ＭＡＰ復号アルゴリズムは実際には最初に下記の確率を見つける。
λt（ｍ）＝Ｐ｛Ｓt＝ｍ；Ｙ1L｝                      （１）
すなわち、時刻ｔの符号化器の状態Ｓtがｍであって、１組のチャネル出力Ｙ1L＝｛ｙ1，．．．，ｙL｝を受信する結合確率を見つける。これは、所望の確率に定数（Ｐ｛Ｙ1L｝、１組のチャネル出力｛ｙ1，．．．，ｙL｝を受信する確率）を乗じたものである。。
次に、行列Γtの要素を次のように定義する。
Γt（ｉ，ｊ）＝Ｐ｛時刻ｔの状態ｊ；ｙt／時刻（ｔ−１）の状態ｉ｝
行列Γtは、チャネル遷移確率Ｒ（Ｙt，Ｘ）、符号化器が時刻ｔに状態ｍ′からｍに遷移する確率ｐt（ｍ／ｍ′）、及び符号化器の前の状態がｍ′であり且つ符号化器の現在の状態がｍであるとして、符号化器の出力記号がＸである確率ｑt（Ｘ／ｍ′，ｍ）の関数として計算される。特に、Γtの各々の要素は、下に示すように、考えられる全ての符号化器の出力Ｘに亘って加算することによって計算される。
0003801211.tif 000002
ＭＡＰ復号器は、格子の各段毎に１つづつ、こういう行列のＬを計算する。それらは、受信したチャネル出力信号と、所定のコードに対する格子の枝路の性質から形成される。
次に行ベクトルαtのＭ個の結合確率要素を次のように定義する。
αt（ｊ）＝Ｐ｛時刻ｔの状態ｊ；ｙ1，．．．，ｙt｝            （３）
列ベクトルβtのＭ個の条件付き確率要素を次のように定義する。
βt（ｊ）＝Ｐ｛ｙt+1，．．．ｙL／時刻ｔの状態ｊ｝          （４）
ここでｊ＝０，１，．．．，（Ｍ−１）であり、Ｍは符号化器の状態の数である。
（なお、行列及びベクトルは太字を用いて表していることに注意されたい。）
ＭＡＰ復号アルゴリズム（すなわち、ＢＣＪＲアルゴリズム）のステップは次の通りである。
（ｉ）前向き再帰法により、α1，．．．，αLを計算する。
αt＝αt-1Γt      ；ｔ＝１，．．．，Ｌ                      （５）
（ii）後ろ向き再帰法により、β1，．．．，βL-1を計算する。
βt＝Γt+1βt+1    ；ｔ＝Ｌ−１，．．．，１                  （６）
（iii）次の式により、λtの要素を計算する。
λt（ｉ）＝αt（ｉ）βt（ｉ）
；全てのｉに対し、ｔ＝Ｌ−１，．．．，１    （７）
（iv）必要に応じて関係する量を見つける。例えば、Ａtjを状態Ｓt＝｛Ｓt1，Ｓt2，．．．，Ｓtkm｝の集合とし、Ｓtのｊ番目の要素Ｓtjが０に等しいとする。従来の非再帰型格子コードでは、Ｓtj＝ｄtj、すなわち時刻ｔにおけるｊ番目のデータ・ビットである。従って、復号器のソフト判定出力は次のようになる。
0003801211.tif 000003
但し、
0003801211.tif 000004
であり、
ｍは状態Ｓtに対応する指数である。
復号器のハード判定又は復号ビット出力は、Ｐ｛ｄtj＝０／ＹlL｝を下記の判定規則に適応することによって得られる。
0003801211.tif 000005
すなわち、Ｐ｛ｄtj＝０／ＹlL｝＞（１／２）であれば、
0003801211.tif 000006
Ｐ｛ｄtj＝０／ＹlL｝＜（１／２）であれば
0003801211.tif 000007
それ以外の場合は、ｄtjにランダムに０又は１の値を割り当てる。
上記のステップ（iv）に対する関連する量の別の例として、確率の行列σtは下記に定義する要素で構成される。
σt（ｉ，ｊ）＝Ｐ｛Ｓt-1＝ｉ；Ｓt＝ｊ；Ｙ1L｝
＝αt-1（ｉ）γt（ｉ，ｊ）βt（ｊ）
これらの確率は符号化器の出力ビットの帰納的確率（ａ  ｐｏｓｔｅｒｉｏｒｉ  ｐｒｏｂａｂｉｌｉｔｙ）を決定したいときに役に立つ。
ＭＡＰ復号アルゴリズムを標準的に適用する場合、ベクトルα0＝（１，０，．．．０）によって前向き再帰法を初期設定し、βL＝（１，０，．．．０）Tによって後ろ向き再帰法を初期設定する。これらの初期条件は符号化器の初期状態Ｓ0＝０及びその終期状態ＳL＝０という仮定に基づいている。
本発明の１実施態様による円形ＭＡＰ復号器は、次に述べるように固有値問題を解くことにより、初期状態確率分布を決定する。αt、βt、Γt及びλtを前の通りとし、初期のα0及びβLを次のようにとる。
βLを列ベクトル（１１１．．．１）Tとする。
α0を未知の（ベクトル）変数とする。
次に
（ｉ）式（２）に従って、ｔ＝１，２，．．．Ｌに対し、Γtを計算する。
（ii）行列積Γ1Γ2．．．ΓLの最大の固有値を見つける。対応する固有ベクトルを正規化して、その成分の和が１になるようにする。このベクトルがα0に対する解である。固有値はＰ｛Ｙ1L｝である。
（iii）式（５）に示す前向きの再帰法により、次のαtを形成する。
（iv）前に述べたように初期設定したβLから出発して、式（６）に示す後ろ向き再帰法により、βtを形成する。
（ｖ）式（７）に示すようにλtを形成すると共に、例えば前に述べたソフト判定出力Ｐ｛ｄtj＝０／Ｙ1L｝又は確率行列σtのようなその他の所望の変数を形成する。
本発明者は、未知の変数α0が次の行列式を満たすことを示した。
0003801211.tif 000008
この式が確率の間の関係を表す事実から、右辺のΓt行列の積は、Ｐ｛Ｙ1L｝に等しい最大の固有値を持つこと、並びに対応する固有ベクトルが確率ベクトルでなければならないことが判る。
最初のβL＝（１１１．．．１）Tを用いて、式（６）からβL-1が得られる。従って、この後ろ向き再帰法を繰り返して適用すれば、全てのβtが得られる。一旦α0が判り、βLが設定されると、本発明の円形ＭＡＰ復号器の全ての計算は、従来のＭＡＰ復号アルゴリズムに従う。
第３図は、前に述べた固有ベクトル方法に従って、誤り訂正のテイルバイティング格子コードを復号する円形ＭＡＰ復号器１０を示す簡略ブロック図である。復号器１０は、チャネル出力ｙtの関数としてΓtを計算するΓt計算器１２を有する。Γt計算器はメモリ３０から入力として次に述べるものを受け取る。すなわち、入力として、チャネル遷移確率Ｒ（Ｙt，Ｘ）と、符号化器が時刻ｔに状態ｍ′からｍに遷移する確率ｐt（ｍ／ｍ′）と、符号化器の前の状態がｍ′であり且つ符号化器の現在の状態がｍであるとして、符号化器の出力記号がＸである確率ｑt（Ｘ／ｍ′，ｍ）とを受取る。Γt計算器は、式（２）に従って、考えられる全ての符号化器の出力Ｘに亘って計算することにより、Γtの各々の要素を計算する。
Γtの計算された値を行列積計算機１４に供給して、例えばメモリから受け取った恒等行列１６、スイッチ１８及び遅延回路２０を使用して、行列積Γ1Γ2．．．ΓLが形成される。時刻ｔ＝１に、恒等行列は行列積計算器に対する１つの入力として印加される。
ｔ＝２乃至ｔ＝Ｌまでのこの後の各々の時刻に行列積
0003801211.tif 000009
が遅延回路を介して行列計算器にフィードバックされる。
その後、時刻ｔ＝Ｌに、こうして得られた行列積がスイッチ２１を介して正規化固有ベクトル・コンピュータ２２に供給される。このコンピュータは、それに入力された行列積の最も大きい固有値に対応する正規化された固有ベクトルを計算する。このようにしてα0を初期設定すると、すなわち、このように正規化された固有ベクトルが得られると、それに続くαtベクトルは、図示のように遅延回路２６及びスイッチ２８の回路を使用し、行列積計算器２４で式（５）を用いて再帰的に決定される。Γtの適当な値が、メモリ３０から検索され、この結果得られたαtがメモリ３０に記憶される。
βtの値が、式（６）に従って、スイッチ３４及び遅延回路３６を使って、行列積計算器３２で決定される。その後、式（７）に従って、要素毎の積の計算器４０により、確率λtがαt及びβtの値から計算される。λtの値が復号ビット値確率計算器５０に供給される。この計算器は、時刻ｔにおけるｊ番目の復号ビットｄtjが０に等しい確率を決定する。この確率が閾値判定装置５２に供給される。この判定装置は、次の判定規則を実施する。すなわち、計算器５０からの確率が１／２より大きければ、復号ビットが０であると判定する。確率が１／２より小さければ、復号ビットが１であると判定する。それが１／２に等しければ、復号ビットにランダムに０又は１の値を割り当てる。閾値判定装置の出力が復号器の時刻ｔにおける出力ビットである。
また第３図に示されているように、復号ビットが０に等しい確率Ｐ｛ｄtj＝０｝もソフト出力関数ブロック５４に供給されて、復号器のソフト判定出力として、例えば
0003801211.tif 000010
のような確率関数すなわちｆ（Ｐ｛ｄtj＝０｝）を発生する。Ｐ｛ｄtj＝０｝の役に立つもう１つの関数は
0003801211.tif 000011
である。この代わりに、ブロック１５４に対して役に立つ関数は、恒等関数であって、ソフト出力が単にＰ｛ｄtj＝０｝になるようにしてもよい。
本発明の別の実施態様による円形ＭＡＰ復号器は、再帰法により、状態確率分布を決定する。特に、１実施態様（ダイナミック収斂方法）では、復号器の収斂が検出されるまで、再帰法が続けられる。この再帰法（又はダイナミック収斂）では、前に述べた固有ベクトル方法のステップ（ii）及び（iii）は次のように置き換えられる。
（iiａ）Ｍを格子の中にある状態の数として、（１／Ｍ，．．．，１／Ｍ）に等しい最初のα0から出発して、前向き再帰法でＬ回計算する。その結果を正規化して、各々の新しいαtの要素の和が１になるようにする。Ｌ個のαtベクトルの全てを保持する。
（iiｂ）α0を前のステップからのαLに等しいとし、ｔ＝１から出発して、最初のＬwminαt確率ベクトルを再び計算する。すなわち、Ｌwminを格子の適当な最小段数として、ｍ＝０，１，．．．，Ｍ−１及びｔ＝１，２，．．．，Ｌwminに対し
0003801211.tif 000012
を計算する。前と同じ様に正規化を行う。ステップ（iiａ）及び（iiｂ）の再帰法で見つけられた最も最近の１組のＬ個のα、並びに前にステップ（iiａ）で見つけられたαLwminだけを残す。
（iiｃ）ステップ（iiｂ）からのαLwminをステップ（iiａ）からの前に見つけられた組と比較する。新しいαLwmin及び古いαLwminのＭ個の対応する要素が許容範囲内であれば、前に述べたステップ（iv）に進む。そうでなければ、ステップ（iiｄ）に続ける。
（iiｄ）ｔ＝ｔ＋１とし、αt＝αt-1Γtを計算する。前と同じ様に正規化する。計算された１番最近のＬ個のαの集合並びにステップ（iiａ）で前に見いだしたαtだけを残す。
（iiｅ）新しいαtを、前に見つけた組と比較する。Ｍ個の新しいαt及び古いαtが許容範囲内であれば、ステップ（iv）に進む。そうでない場合、１番最近の２つのベクトルが許容範囲内で一致せず、再帰法の回数が特定された最大値（典型的には２Ｌ）を越えなければ、ステップ（iiｄ）を続け、それ以外の場合、ステップ（iv）に進む。
第４図の円形「時間線」は、円形ＭＡＰ復号器に対しｔ＝１，２，．．．，Ｌに対するαtを計算する上に述べたステップ（iiａ）−（iiｅ）の過程をまとめたものであり、この結果、Ｌ個の全てのαtベクトルが推定される。次に、この方法は、固有ベクトル方法について前に述べたステップ（iv）及び（ｖ）に続き、円形ＭＡＰ復号器のソフト判定出力及び復号出力ビットを発生する。
円形ＭＡＰ復号器では、α0は、α0＝（１／Ｍ，．．．，１／Ｍ）と初期設定されていることに注意されたい。これは、符号化器の初期状態が未知であるからである。全てのＭ個の初期状態が同じ尤度であると仮定する。（もしこれが真でなければ、初期出発状態の確率に関する先験的な情報に従って、初期値α0（ｍ）を割り当てることが出来る。従って、ここで説明する復号器は、部分的にテイルバイティング格子コードにも有利に適用し得る。）
本発明の円形ＭＡＰ復号器の動作の説明は、αt（ｍ）の定義を考えると判り易い。項αt（ｍ）は、符号化器が時刻ｔに状態ｍにあり、復号器がチャネルからの記号シーケンス｛ｙ1，．．．，ｙt｝を観察した結合確率である。αtを再帰的に計算する式（５）を検討すれば、テイルバイティング格子符号化器の初期状態が判らない影響が明らかになる。式（５）から、テイルバイティング格子符号化器の初期状態が判らないと、符号化器が時刻ｔ＝１に状態ｍにあり、復号器がチャネル出力ｙ1を観察する計算された結合確率が、不正確な初期状態の子孫（ｄｅｅｓｃｅｄｅｎｔ）に対する実際の場合より大きく、正しい初期状態の子孫に対する実際の場合よりも小さいという意味で、α1（ｍ）がバイアスされることは明らかである。このバイアスは、αt（ｍ）の再帰的な計算の為に伝搬する傾向があるが、幸いなことに、より多くのチャネル出力記号を観察するにつれて減少する傾向がある。従って、メッセージ・ブロック長Ｌが十分大きければ、αL（ｍ）は、α0（ｍ）よりずっと正確になる。これは、このとき復号器がチャネルからの記号の全シーケンスを観察する有利さを持っているからである。そこで、αL（ｍ）は、前に述べたステップ（iiｂ）に示す２回目の復号の繰返しにおけるα0（ｍ）として使うことが出来る。
本発明による再帰法（又はダイナミック収斂法）は、毎回の繰返しから得られた値を比較し、収斂が検出されたときに、αtの再帰法による計算を終了させることが有利である。従って、この方式は、Ｌ個の格子段全部に対するαtを再び計算することを必要としない場合が多いので、必要な計算の数を少なくする。
本発明の別の実施例では、上に説明した再帰法を用いる円形ＭＡＰ復号器が、２回目には、所定の一定数の格子段を処理すればよいように、すなわち所定のラップ深さを持つように変更される。これは、ことごとくの符号化されたメッセージ・ブロックに対し、復号に要する計算の数が同じであるから、実施する上で有利である。その為、ハードウェア及びソフトウェアの複雑さが低下する。
ここで云うラップ深さ（ｗｒａｐ  ｄｅｐｔｈ）は、観察長Ｌobsの格子レベルで起るｅ又はそれより少ない誤りの任意の組合わせを訂正する復号器である有限距離復号器の場合に認められる。これは、復号器の誤り確率を最小限にするというようなこの他の判定基準を達成するように組立てられた復号器にも直接的に及ぶ。
テイルバイティング・コンボルーション・コードのＭＡＰ復号に必要なラップ深さを推定する１つの方法は、ハードウェア又はソフトウェアの実験からそれを決定することであり、これは、可変ラップ深さを持つ円形ＭＡＰ復号器を構成すること、並びに相次いで増加するラップ深さに対し、復号ビット誤り率対Ｅb／Ｎ0を測定する為の実験を行うことを必要とする。ラップ深さをそれ以上増加しても、誤りの確率が減少しない時、特定のＥb／Ｎ0に対する復号ビット誤りの最小確率をもたらす最小復号器ラップ深さが見つかる。
特定のＥb／Ｎ0で達成し得る最小値より大きな復号ビット誤り率が許容できれば、円形ＭＡＰ復号器によって処理される格子段の必要な数を減らすことが可能である。特に、上に述べたラップ深さ探索は、ビット誤りの所望の平均確率が達成された時、単純に終了することが出来る。
所定のコードに対するラップ深さを決定する別の方法は、コードの距離特性を使うことである。この目的の為には、２つの別異の復号器判定深さを定義することが必要である。この明細書で云う「正しいパス」という用語は、データ・ビットのブロックを符号化することによって生じる状態のシーケンス又は格子の中のパスを指す。「節の不正確な部分集合」という用語は、正しいパスの節（ｎｏｄｅ）及びその子孫から出た全ての不正確な（格子の）枝路の集合を指す。これから定義する両方の判定深さは、コンボルーション符号化器に関係する。（例として、本発明のこの実施態様をコンボルーション符号化器について説明するが、本発明がコンボルーション・コードに制限されないことを承知されたい。）
判定深さは次のように定義される。
（ｉ）ｅ−誤り訂正に対する前向き判定深さＬＦ（ｅ）を、後で正しいパスに合流（ｍｅｒｇｅ）してもしなくても、正しいパスの最初の節の不正確な部分集合内にある全てのパスが、正しいパスからハミング距離２ｅより遠い所にあるような格子内の第１の深さと定義する。ＬＦ（ｅ）の意味は、最初の節より前向きにｅ又は更に少ない誤りがあって、符号化がそこで始まったと判っている場合、復号器が正しく復号しなければならないことである。コンボルーション・コードに対する前向き判定深さの公式の表が、ＩＥＥＥ・トランザクションズ・オン・インフォメーション・セオリ誌、ＩＴ−３５巻、１９８９年３月号、４５５−５９頁所載のＪ．Ｂ．アンダーソン及びＫ．バラカンドランの論文「コンボルーション・コードの判定深さ（Ｄｅｃｉｓｉｏｎ  Ｄｅｐｔｈ  ｏｆ  Ｃｏｎｖｏｌｕｔｉｎａｌ  Ｃｏｄｅｓ）」に記載されている。ＬＦ（ｅ）の多数の性質が、この文献と１９９１年にミネソタ州ノーウェルのクルワー・パブリッシャーズから出版されたＪ．Ｂ．アンダーソン及びＳ．モーハンの著書「源及びチャネル符号化−アルゴリズム方式（Ｓｏｕｒｃｅ  ａｎｄ  Ｃｈａｎｎｅｌ  Ｃｏｄｉｎｇ−Ａｌｇｏｒｉｔｈｍｉｃ  Ａｐｐｒｏａｃｈ）」に記載されている。こういう性質の中で主なものは、ＬＦとｅの間に、単純な線形関係が存在することである。例えば、レート１／２のコードでは、ＬＦは約９．０８ｅである。
（ii）次に、ｅ−誤り訂正に対する合流しない場合の判定深さＬｕ（ｅ）を、正しいパスに接触することのなかった格子内の全てのパスが、正しいパスからハミング距離２ｅより遠く離れているような格子内の最初の深さと定義する。
ソフト判定円形ＭＡＰ復号に対するＬＵ（ｅ）の意味は、復号器が格子のＬＵ（ｅ）段を処理した後、実際に送信されたパスにおける状態を確認する確率が高いということである。従って、円形ＭＡＰ復号に対する最小ラップ深さがＬＵ（ｅ）である。深さＬＵ（ｅ）の計算では、それが常にＬＦ（ｅ）より大きいが、同じ近似則に従うことを示している。これは、コードの合流しない場合の判定深さが判っていなくても、最小ラップ深さを前向き判定深さＬＦ（ｅ）として推定することが出来ることを意味する。
所定の符号化器に対する最小の合流しなかった場合の判定深さを見つけることにより、ソフト判定出力を発生する実際の円形復号器によって処理しなければならない格子の最も少ない段数が判る。前向き判定深さＬＦ（ｅ）を見つけるアルゴリズムが、上に引用したＪ．Ｂ．アンダーソン及びＫ．バラカンドランの著書「コンボルーション・コードの判定深さ」に記載されている。ＬＵ（ｅ）を見つけるには、
（ｉ）ゼロ状態を除いて、格子の全ての節から同時に出発して、コード格子を左から右へ進む。
（ii）各々のレベルで、正しい（全部ゼロの）パスに合流するパスがあれば、それを全て削除し、正しい（ゼロの）状態の節からのパスを延ばさない。
（iii）レベルｋで、このレベルの節で終端するパスの中で、最小のハミング距離又は重みを見つける。
（iv）この最小の距離が２ｅを越える場合、停止する。この時、ＬＵ（ｅ）＝ｋである。
前に引用した米国特許出願に記載されているように、コンピュータ・シミュレーションによる実験で、予想外の２つの結果が得られた。（１）βtのラップ処理が復号器の性能を改善する。（２）ＬＵ（ｅ）＋ＬＦ（ｅ）≒２ＬＦ（ｅ）のラップ深さを使うと、性能がかなり改善される。これらの予想外の結果により、再帰法に基づくテイルバイティング格子コードに対する円形ＭＡＰ復号器の修正が早められた。従って、再帰法に基づく好ましい実施態様の円形ＭＡＰ復号器のアルゴリズムは、次のステップで構成される。
（ｉ）式（２）に従って、ｔ＝１，２，．．．Ｌに対し、Γtを計算する。
（ii）Ｍを格子内の状態の数として、（１／Ｍ，．．．，１／Ｍ）に等しい最初のα0から出発して、Ｌwを復号器のラップ深さとして、ｕ＝１，２，．．．（Ｌ＋Ｌw）に対し、式（５）の前向き再帰法を（Ｌ＋Ｌw）回計算する。格子−レベル指数ｔは（（ｕ−１）ｍｏｄ Ｌ）＋１の値をとる。復号器がチャネルからの受信した信号のシーケンスで折り返す時、αLはα0として取り扱う。結果を正規化し、各々の新しいαtの要素の合計が１になるようにする。この再帰法によって見いだされたＬ個の最も最近のαベクトルを残す。
（iii）（１，．．．，１）Tに等しい最初のＢLから出発して、ｕ＝１，２，．．．．（Ｌ＋Ｌw）に対し、式（６）の後ろ向き再帰法を（Ｌ＋Ｌw）回計算する。格子−レベル指数ｔはＬ−（ｕ  ｍｏｄ  Ｌ）の値をとる。復号器が受信したシーケンスで折り返すとき、新しいβLを計算するのに、β1をβL+1として使い、Γ1をΓL+1として使う。結果を正規化し、各々の新しいβtの要素の合計が１になるようにする。この場合も、この再帰法によって見いだされたＬ個の最も最近のβベクトルを残す。
好ましい再帰法の次のステップは、円形ＭＡＰ復号器によってソフト判定及び復号ビット出力を発生する為の固有ベクトル方法について前に述べたステップ（ｖ）と同じである。
第５図の円形「時間線」は、好ましい再帰法による円形ＭＡＰ復号器でｕ＝１，２，．．．．（Ｌ＋Ｌw）に対するαt及びβtを計算する過程をまとめたものである。
２進対せき点信号方式（例えば２進移相キーイング）を想定したコンピュータ・シミュレーションにより、ソフト判定、相加的なホワイト・ガウス雑音（ＡＷＧＮ）チャネルに対し、この好ましい実施態様の円形ＭＡＰ復号器の性能を試験した。このシミュレーションは、判っている最善のレート＝１／２、メモリ＝６のコンボルーション・コードを用いて実行した。（自由距離が最大という意味で最善である。）ここに示す全てのシミュレーション結果は、コードの前向き判定深さの２倍に等しいラップ深さ（４０格子段）を利用する復号器によって発生した。このシミュレーションでは、４８ビットで構成される短いメッセージ・ブロックを使った。
第６図は復号ビット誤りの平均確率対Ｅb／Ｎ0を示すグラフである。源（ｓｏｕｒｃｅ）ビットは同じ尤度で０又は１であった。然し、先験的に復号器に判っているバイアス源統計で繰返した時、所定のＥb／Ｎ0における円形ＭＡＰ復号器のビット誤りの平均確率は目立って減少した。第７図は、次の３つの場合に対するビット誤り率対Ｅb／Ｍ0を比較したグラフである。すなわち、同じ尤度の源ビットで、Ｐ｛源ビットが１｝＝０．６７、及びＰ｛源ビットが１｝＝０．９１の場合、２番目の場合は、Ｐ｛源ビットが１｝＝２Ｐ｛源ビットが０｝であり、３番目の場合、Ｐ｛源ビットが１｝＝１０Ｐ｛源ビットが０｝である。
第８図は、本発明の好ましい実施例による円形ＭＡＰ復号器８０を示す簡略ブロック図である。復号器８０は、チャネル出力ｙtの関数としてΓtを計算するΓt計算器８２を有する。チャネル出力ｙ1，．．，ｙLがスイッチ８４を介してΓt計算器に供給される。このスイッチが下側位置にある時、Ｌ個のチャネル出力信号が１度に１つづつ、Γt計算器８２及びシフトレジスタ８６にロードされる。その後、スイッチ８４を上側位置に切り替えて、シフトレジスタが、最初のＬw個の受取った信号を再びΓt計算器へシフトさせる、すなわち円形処理を行うことが出来るようにする。Γt計算器が、メモリ９６からの入力として、チャネル遷移確率Ｒ（Ｙt，Ｘ）、時刻ｔに符号化器が状態ｍ′からｍへ遷移する確率ｐt（ｍ／ｍ′）、及び符号化器の前の状態がｍ′であり且つ符号化器の現在の状態がｍであるとして、符号化器の出力信号がＸである確率ｑt（Ｘ／ｍ′，ｍ）を受取る。Γt計算器が、式（２）に従って、考えられる全ての符号化器の出力Ｘに亘って加算することにより、Γtの各々の要素を計算する。
Γtの計算された値が、行列積計算器９０に供給され、この計算器は、Γt行列にαt-1行列を乗算する。αt-1行列は、遅延回路９２及びデマルチプレクサ９４の回路を介して再帰的に供給される。制御信号ＣＮＴＲＬ１により、ｔ＝１の時、デマルチプレクサ９４が行列積計算器９０に対する１つの入力としてメモリ９６からのα0を選ぶ。２≦ｔ≦Ｌの時、制御信号ＣＮＴＲＬ１により、デマルチプレクサ９４が、行列積計算器９０に対する１つの入力として、遅延回路９２からのαt-1を選択する。必要に応じて、Γt及びαtの値をメモリ９６に記憶する。
βtベクトルが、遅延回路１０２及びデマルチプレクサ１０４の回路を通じて再帰的に行列積計算器１００で計算される。制御信号ＣＮＴＲＬ２により、ｔ＝Ｌ−１の時、デマルチプレクサ１０４が行列積計算器１００に対する１つの入力として、メモリ９６からのβLを選択する。Ｌ−２≧ｔ≧１の時、制御信号ＣＮＴＲＬ２により、デマルチプレクサ１０４が行列積計算器１００に対する１つの入力として、遅延回路１０２からのβt+1を選択する。この結果得られたβtの値に、要素毎の積の計算器１０６でαtの値を乗算して、前に述べた確率λtを発生する。前に第３図について述べたのと同様に、λtの値が復号ビット値確率計算器５０に供給され、その出力が閾値判定装置５２に供給され、その結果として復号器の復号出力ビットが得られる。
第８図にはまた、復号ビットが０に等しい確率Ｐ｛ｄtj＝０／Ｙtj｝が、ソフト出力関数ブロック１５４に供給されることが示されている。ソフト出力関数ブロック１５４は、復号器のソフト判定出力として、例えば
0003801211.tif 000013
のような確率関数すなわちｆ（Ｐ｛ｄtj＝０／Ｙtj｝）を発生する。Ｐ｛ｄtj＝０／Ｙtj｝の役に立つもう１つの関数は
0003801211.tif 000014
である。この代わりに、ブロック１５４に対して役に立つ関数は、恒等関数であって、ソフト出力が単にＰ｛ｄtj＝０／Ｙtj｝になるようにしてもよい。
いくつかの実用的な強力な符号化方法は、ＭＡＰ復号器のソフト出力情報、例えば直列連結符号化方法によって臨界的に左右される。外側復号器が誤り及び消去復号を利用するこのような１つの方法では、復号ビットに０又は１の値を割当てることができ又は消去を宣言することができる３元判定装置により、ＭＡＰ内側復号器のソフト判定出力を復号信頼性の表示子として処理することが出来る。更に、ソフト復号器出力は、音声又は画像復号器のような、次に続く処理装置で有利に使うことが出来る場合が多い。例えば、ボコーダ（ｖｏｃｏｄｅｒ）の音声合成器は、ソフト判定出力を利用して、非常に雑音の多いチャネルを介して動作する装置で音声の品質を改善するように誤り抑制方法を発動する為に、受信音声フレームで同じ様な伝送の誤りを確認することが出来る。
本発明以前には、テイルバイティング・コードを用いたＭＡＰ復号は出来なかった。テイルバイティングの意義は、大きな符号化利得を達成することが困難な短いコードワードから、究極的な誤り訂正性能を抽出することである。短いコードワードは、パケット・データ・システム並びに速度の遅い音声符号化を用いる音声通信装置で自然に起こる。
更に、本発明は、極く小さい開口の端末（ＶＳＡＴ）衛星通信及び移動無線通信における共通の特性であるフェージングを持つチャネル又は信号対雑音エネルギ比が小さいチャネルに役立つ。
本発明の好ましい実施態様を図示し説明したが、これらの実施態様が例に過ぎないことは云うまでもない。本発明の範囲を逸脱することなく、当業者であれば、種々の変更及び置換が考えられよう。従って、本発明は請求の範囲によって限定されることを承知されたい。
【図１】
0003801211.tif 000015
【図２】
0003801211.tif 000016
【図３】
0003801211.tif 000017
【図４】
0003801211.tif 000018
【図５】
0003801211.tif 000019
【図６】
0003801211.tif 000020
【図７】
0003801211.tif 000021
【図８】
0003801211.tif 000022