JPH0795099A - 信号処理方法 - Google Patents

信号処理方法

Info

Publication number
JPH0795099A
JPH0795099A JP6014924A JP1492494A JPH0795099A JP H0795099 A JPH0795099 A JP H0795099A JP 6014924 A JP6014924 A JP 6014924A JP 1492494 A JP1492494 A JP 1492494A JP H0795099 A JPH0795099 A JP H0795099A
Authority
JP
Japan
Prior art keywords
value
path
sequence
metric
signal
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.)
Pending
Application number
JP6014924A
Other languages
English (en)
Inventor
Christiane G Nill
ガブリエル ニル クリスティアンヌ
Carl-Erik Wilhelm Sundberg
ウィルヘルム サンドバーグ カール−エリック
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
AT&T Inc
Original Assignee
American Telephone and Telegraph Co Inc
AT&T Inc
Priority date (The priority date 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 date listed.)
Filing date
Publication date
Application filed by American Telephone and Telegraph Co Inc, AT&T Inc filed Critical American Telephone and Telegraph Co Inc
Publication of JPH0795099A publication Critical patent/JPH0795099A/ja
Pending legal-status Critical Current

Links

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/4138—Sequence estimation, i.e. using statistical methods for the reconstruction of the original codes using the Viterbi algorithm or Viterbi processors soft-output Viterbi algorithm based decoding, i.e. Viterbi decoding with weighted decisions
    • H03M13/4146—Sequence estimation, i.e. using statistical methods for the reconstruction of the original codes using the Viterbi algorithm or Viterbi processors soft-output Viterbi algorithm based decoding, i.e. Viterbi decoding with weighted decisions soft-output Viterbi decoding according to Battail and Hagenauer in which the soft-output is determined using path metric differences along the maximum-likelihood path, i.e. "SOVA" decoding
    • 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/4115—Sequence estimation, i.e. using statistical methods for the reconstruction of the original codes using the Viterbi algorithm or Viterbi processors list output Viterbi decoding

Landscapes

  • Physics & Mathematics (AREA)
  • Probability & Statistics with Applications (AREA)
  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Error Detection And Correction (AREA)
  • Dc Digital Transmission (AREA)
  • Compression, Expansion, Code Conversion, And Decoders (AREA)

Abstract

(57)【要約】 【目的】 信号処理用ディジタル信号復号化アルゴリズ
ムの複雑度の改善。 【構成】 拡張汎用ビタビアルゴリズム（ＧＶＡ）及び
ソフト出力ビタビアルゴリズム（ＳＯＶＡ）の復号器フ
ァミリーが、例えば符号化システム内部復号器２５及び
外部復号器２７用として、開示される。本発明の一態様
によれば、ソフト出力ビタビアルゴリズム（ＳＯＶＡ）
の構造を用いて、直列汎用ビタビアルゴリズム（ＳＧＶ
Ａ）を新たに実現している。本発明の別の態様は、汎用
ビタビアルゴリズム（ＧＶＡ）のリスト出力を用いて、
復号化情報について信頼性尺度を計算する。本発明の更
に別の態様においては、ソフト出力ビタビアルゴリズム
（ＳＯＶＡ）からの信頼性情報を用いて、複雑度の低い
汎用ビタビアルゴリズム（ＧＶＡ）が開発される。

Description

【発明の詳細な説明】
【０００１】
【産業上の利用分野】本発明は、通信路上を伝送される
ディジタル情報の符号化及び復号化に関し、詳しくは汎
用ビタビ（Viterbi）アルゴリズムとソフト出力ビタビ
アルゴリズムの拡張版アルゴリズムグループ（ファミ
リ）に関する。
【０００２】
【従来の技術】従来の技術によるディジタル通信システ
ムのモデルを図１に示す。情報源（ソース）１０は、ア
ナログ又は離散的情報のいずれかを生成し、この情報を
ソース符号器１１が情報の列（シーケンス）ｘに符号化
する。チャンネル符号器１２が、この情報列を「チャン
ネル符号化」として知られるプロセスによって新しい情
報列に変換する。変調器１３が、振幅変調、周波数変
調、位相変調、又はパルス変調のような、標準的変調方
法を用いて、チャンネル符号器１２の符号化された出力
（符号化出力）から、伝送路（チャンネル）１４上での
伝送用にチャンネル信号を生成する。
【０００３】概して、伝送チャンネル１４には、雑音及
び他の障害、例えば周波数ひずみ、位相ひずみ、及び種
々のフェーディング（信号強度の時間的変動現象）特
性、が発生する。ディジタルの復調器１５は、伝送され
た信号を復調して符号化情報列の推定列を生成する。そ
れから、チャンネル復号器１６がこの推定列を入力とし
て受け入れ、冗長ビットを用いて情報列の再現を企図す
る。
【０００４】最後に、ソース復号器１７が、再構築され
た情報列（ｘの上に＾を付けるか、又はｘの前に＾を付
けるか（＾ｘ）して表す）を情報の宛先１８での使用に
適した形式に変換する。（概略的には、マイケルソン
（A.M. Michelson）及びレベスク（A.H. Levesque） の
著書「ディジタル通信についてのエラー制御技術」（ジ
ョン・ウィリー・アンド・サンズ社（米国ニューヨー
ク）１９８５年）を参照されたい。）
【０００５】チャンネル符号化は、伝送の信頼性を上げ
るために冗長をデータ列中に効率的に導入する手段であ
る。冗長情報を用いて受信情報の精度又は信頼性を改善
する方法には少なくとも次に示す３種類がある。
【０００６】まず１）誤り（エラー）検出、この場合、
復号器は受信データ列が正しいかどうか又は誤りが発生
しているかどうかだけを定める。次に２）誤り補正。こ
の場合、復号器は冗長情報を用いて受信データ列内の誤
りの検出と補正との両方を行う。そして最後に３）自動
反復要求、この場合、誤りの検出によって、データの繰
り返しについての要求が自動的に起こされる。
【０００７】符号化メッセ−ジ内の誤りを単に検出する
だけよりも、誤りを補正する方がより多くの冗長を必要
とする（マスリン（Nicholas Maslin） の著書「高周波
通信、そのシステムアプローチ」（プレナムプレス社
（ニューヨーク）１９８７年）参照）。
【０００８】冗長の導入に用いられる主たる技術として
は、「ブロック符号化」及び「畳込み符号化」の２つが
ある（例えば、リン（S. Lin）及びコステロ（D.J Cost
ello, Jr.） の著書「誤り制御符号化、その基礎及び応
用」（プレンティスホール社（米国ニュージャージー州
エングルウッド・クリフ）１９８３年）参照）。
【０００９】（ｎ，ｋ）ブロック符号は、ｋ個の情報ビ
ットのブロックを取り、予め規定された符号化規則に基
づいてｎ−ｋパリティビットを加えることにより、この
ブロックをｎビットの符号語（コ−ドワード）に変換す
る。それから、このｎビットのブロックは、通信路（チ
ャンネル）上を伝送される。符号レート、Ｒが、Ｒ＝ｋ
／ｎとして定義される。
【００１０】チャンネルの受信端において、復号器が、
ｎ−ｋパリティビットによって導入された冗長を含む受
信データ列を用いて、当初のｋ個の情報ビットの推定を
行う。ブロック符号は、復号器からの各ｎビット符号群
出力が現在のｋビット情報ブロックにだけ依存するとい
う点で、メモリレスである。
【００１１】畳込み符号は概して、情報ビットのストリ
ーム上で作動する。ストリームは、ｋビットのブロック
に分割される。情報ビットは、ｋビットのブロック内の
シフトレジスタへ送られる。シフトレジスタのステージ
には、各ｋビットのブロックからなるｖ個のブロックグ
ループのが記憶される。ステージは、線形代数機能生成
器に接続される。そして線形代数機能生成器の出力は、
選択的に組み合わされて、ｎビットの符号化出力を生成
する。
【００１２】各符号化出力は、シフトレジスタへの現在
のｋビットメッセ−ジブロック入力に依るだけでなく、
前のｖ個のメッセ−ジブロックにも依る。したがって、
畳込み符号は、ｖのオーダのメモリを有する。畳込み符
号の符号レート、Ｒは、Ｒ＝ｋ／ｎで、符号の制約長さ
はｖ＋１である。一般に、ｋ及びｎは、小さい整数で、
冗長は、シフトレジスタの長さを増加することによって
付加される。
【００１３】周知のように、畳込み符号器及び復号器の
動作は、格子図（ダイヤグラム）又は状態図（ダイヤグ
ラム）若しくは状態テーブルによって完全に記述できる
（上記マイケルソン及びレベスクの著書参照）。
【００１４】ビタビアルゴリズム（ＶＡ）は、畳込み符
号の復号化用として周知の方法である（ビタビ（A.J. V
iterbi) の論文「畳込み符号に対する誤りの限界及び漸
近的に最適な復号化アルゴリズム」（ＩＥＥＥ会報、情
報理論、第ＩＴ−１３巻、２６０−２６９、１９６７年
４月）参照）。このアルゴリズムは、フォーニー（G.D.
Forney, Jr.）の論文「ビタビアルゴリズム」（ＩＥＥ
Ｅ論文集、第６１巻第３号、２６８−２７８、１９７３
年３月）にも詳述されている。
【００１５】ビタビアルゴリズムは、メモリレス・チャ
ンネル上を伝送される畳込み符号化されたビタビデータ
列についての、「近似可能性」の最も高い推定という意
味での、最適復号化アルゴリズムである。ビタビアルゴ
リズムの基本的な理論的概念は、可能性ある（あり得
る）全ての伝送符号列を受信符号列と相関させ、それか
ら相関関係が最大である符号列、すなわち最良の計量値
を有するパス、を「残存列」として選択すること、とし
て説明できる。
【００１６】連続データ伝送に畳込み符号が用いられる
場合、復号化格子内で扱いやすいウインドウ又は長さ、
δ、になるように、残存列を切り捨てる必要がある。し
たがって、ビタビアルゴリズムは、時点ｉ−δまでの格
子ノードを通る最良のパスについて決定しなければなら
なくなる。
【００１７】しかし、データをブロックに構成すること
により、又シフトレジスタの内容を消去する目的で最後
の情報ビットにいくつもの「０」ビットを付けてブロッ
クを終結させることにより、ビタビアルゴリズムを用い
て長さ「Ｎ」の非系統的ブロック符号を設計することが
できる。この場合、格子は知られている状態の ｓ0＝
（０．．．０）及びｓN＝（０．．．０）で始まり、終
る。状態ｓN＝（０．．．０）における終結は、各情報
ブロックの終止時点ごとににｖ個の「０」を伝送するこ
とで得られる。
【００１８】したがって、ブロックとしてのデータ伝送
についての符号レート、ＲBLは、次の数式で与えられ
る。 ＲBL＝Ｒ・（Ｎ−ｖ）／Ｎ ここに、Ｎはブロック長さ、ｖはメモリ、Ｒは符号レー
トである。
【００１９】ここで述べるビタビアルゴリズム及び拡張
ビタビアルゴリズムの説明は、４個の状態を有するＲ＝
１／２の２進畳込み符号について行う。他のｆへの一般
化は容易である。全体を通して説明は、ブロック化した
畳込み符号を用いて（一般性を失うことなく）行う。畳
込み符号に付随する格子は、１個の知られている状態に
終結する。
【００２０】メモリｖ＝２を有する、符号レートＲ＝１
／２の畳込み符号の格子の１個のセグメントを図２に示
す。符号がメモリｖ＝２であるので、それぞれビットパ
ターン、ｕ1ｕ2，００，０１，１０及び１１が付随す
る、可能性ある４つの状態の、ｓi＝０，１，２，３が
存在する。格子内のノード３０−３３の各々が与えられ
た時点ｉにおける個別の状態ｓi に対応し、ノード３４
−３７が、時点ｉ＋１における状態に対応する。
【００２１】枝（ブランチ）４０−４７の各々は、状態
ｓi から次の時点における次の状態であるｓi+1 への遷
移を表し、次の数式で表示される。 ξi＝（ｓi+1，ｓi） 格子内の各状態ｓi は、現時点ｉにおける符号器シフト
レジスタの、可能性ある内容に対応する。各状態から出
る２個のブランチは、可能性ある伝送情報ビットｘi
【数２】 に対応する。
【００２２】上側ブランチ４０−４３は、「０」が伝送
されることを、又、下側ブランチ４４−４７は、「１」
が伝送されることを表示する。したがって、可能性ある
遷移ξi＝（ｓi+1，ｓi） に付けられたビットは、状態
ｓiからｓi+1へのシフトすなわちｓi→ｓi+1、によって
生成されるｎ個の符号化ビット（ｕi,1，．．．ｕi,n）
と同等である。
【００２３】各時点ｉ＋１において、又状態ｓi+1 にお
いて、ビタビアルゴリズムは、その時点までの累積計量
値Γ（ｓi+1，ｓi）を計算する。この値は、可能性ある
全ての遷移ξi＝（ｓi+1，ｓi） に対して、次の数式で
表される。 Γ（ｓi+1，ｓi）＝Γ（ｓi）＋λ［ξi＝（ｓi+1，ｓi）］ Γ（ｓi）は時点ｉまでの累積計量値、λ［ξi＝（ｓ
i+1，ｓi）］はこの遷移についての計量値増値分であ
る。
【００２４】図２において考えられている２進符号に対
しては、全ての状態の各々、ｓi+1において必ず２つの
道（パス）が合流する。次の復号化ステップについて可
能性ある２個の候補のうち、最大累積計量値
【数３】 を有する候補が選択され、Γ（ｓi+1）と、対応する残
存パス、＾ｘ（ｓi+1）とが、後の計算のために記憶さ
れる。
【００２５】各復号化ステップの後、時点パラメータｉ
が値「１」だけ増値され、ｉ＝Ｎになるまで計算プロセ
スが繰り返される。時点ｉ＝Ｎにおいては、最高近似パ
ス、＾ｘ、すなわち最良累積計量値を有するパス、だけ
が残る。
【００２６】格子を通る最良のパスを定める際にハード
又はソフト決定要綱が用いられる。ハード決定要綱にお
いては、計量値は、受信された語と符号語（コ−ドワー
ド）との間のハミング距離として定義される。ソフト決
定要綱においては、ハミング距離を計量値とはせず、代
わりに、復号器への入力における受信データの確率配分
の知識を与えられて候補パスの近似性を計算する、等の
ソフト決定計量値を用いる。
【００２７】一般的には、クラーク（J.C. Clark, J
r.） 及びケイン（J.B. Cain） の著書「ディジタル通
信のための誤り補正符号化」（プレナムプレス社（ニュ
ーヨーク）１９８２年）、及び上記マイケルソン及びレ
ベスクの著書の３０３〜３０５を参照されたい。加法ガ
ウス雑音チャンネル上では、復調器出力のソフト決定復
号化は、ハード決定復号化に比べると約２〜３ｄＢの性
能改善が得られる（上記リン及びコステロの著書の３２
９、及び上記クラーク及びケインの著書の２２７を参
照）。
【００２８】ビタビアルゴリズムにおける最高近似性の
アプローチとソフト復号化能力とから、ビタビアルゴリ
ズムは、広範囲の用途に用いられるようになった。実際
にビタビアルゴリズムによって復号化された畳込み符号
は、しばしば、同等の複雑さを有するブロック符号より
も優れている。
【００２９】チャンネル符号化の用途のほかに、ビタビ
アルゴリズムは、記号間干渉を有するチャンネル間を等
価するためにも用いられる（フォーニー（G.D. Forney,
Jr.）の論文「記号間干渉の存在下におけるディジタル
信号の、最高近似性方式の列推定」（ＩＥＥＥ会報、情
報理論、第ＩＴ−１８巻、第３号、３６３−３７８、１
９７２年５月）参照）。
【００３０】ビタビアルゴリズムは、部分応答連続位相
変調の復調にも用いられ（アンダーソン（J.B. Anderso
n）、オーリン（T. Aulin）、及びサンドバーグ（C-E.
Sundberg）の著書「ディジタル位相変調」（プレナムプ
レス社（ニューヨーク）１９８６）参照）、又同様に、
格子符号化変調の復調にも用いられてきた（アンガーボ
ック（G. Ungerbock）の論文「マルチレベル位相／信号
でのチャンネル符号化」（ＩＥＥＥ会報、情報理論、第
ＩＴ−２８巻、第１号、５５−６７、１９８２年１月）
参照）。
【００３１】ビタビアルゴリズムは、又テキスト及びパ
ターン認識の問題にも適用可能である。前に述べたよう
に、畳込み符号を用いて非系統的ブロック符号を設計す
ることができ、このブロック符号はビタビアルゴリズム
を用いて最適に復号化できる。このように、畳込み符号
の復号化だけでなく、他の種々の符号及び伝送技術にお
いても、ビタビアルゴリズムを用いることで有利とな
る。これらの用途は全て、格子状の構造を特徴としてい
る。
【００３２】ブロック符号と異なり、畳込み符号及び他
の格子を主とする構造に対する最高近似性方式復号器
は、全ての受信列（シーケンス）をそれぞれ復号化する
という点で完全である。したがって、畳込み符号用の復
号器は一般に、潜在的復号化誤りに対して警告信号を発
する能力に欠ける。
【００３３】もし内部復号器として用いた場合にビタビ
アルゴリズムが潜在的復号化誤りについて警告信号を外
部処理ステージへ発することができれば、連結符号化シ
ステム（すなわち、マルチレベルの符号化を有するシス
テム）の性能が改善される。いい別の言い方をすれば、
もしビタビアルゴリズムが復号化の信頼性の表示のよう
な付加情報を外部処理ステージへ与えることができれ
ば、システム性能が改善される。これは、外部符号器が
音声（ソース）符号器である場合に特に真実であるとい
える。
【００３４】セシャドリ（N. Seshadri） 及びサンドバ
ーグ（C-E.W. Sundberg） の論文「畳込み符号での誤り
検出のための汎用ビタビアルゴリズム」（会議録ＩＥＥ
Ｅ、ＧＬＯＢＥＣＯＭ'８９、 １５３４〜１５３８、米
国テキサス州ダラス、１９８９年１１月）、及びセシャ
ドリ（N. Seshadri） 及びサンドバーグ（C-E.W. Sundb
erg） の論文「サブバンド符号化音声における信頼不能
パケットの推定」（会議録ＩＥＥＥ、ＧＬＯＢＥＣＯ
Ｍ'９０、 １９７９〜１９８３、米国カリフォルニア州
サンディエゴ、１９９０年１２月）を参照されたい。
【００３５】連結符号化アーキテクチャを用いる、従来
技術による通信システムのブロック図を図３に示す。こ
のシステムにおいて、情報源（ソース）２０は、アナロ
グ又は離散的情報のいずれかを生成する。外部符号器２
１が、情報ソース２０からの信号を情報ビットの列に変
換し、この列を符号化する。インタリーブ器２２が、フ
ェーディングや雑音バーストのようなチャンネル障害を
複数のブロックに分配する作業を行い、この分配によっ
て、どれか１個のブロックへの障害の影響を減少させ
る。
【００３６】インタリーブ器２２は、矩形アレイを用い
て信号を処理する要素と考えることができる。符号化さ
れたデータは、横列によりアレイへ読み込まれ、縦列に
よって読み出される。内部符号器２３は、インタリーブ
器２２からの列出力を符号化し、変調信号を生成する。
この変調信号は、チャンネル２４上を伝送される。
【００３７】次に、内部復号器２５が、受信信号を復調
し、復号化プロセス中の第１ステージを行う。逆インタ
リーブ器２６が、内部復号器２４からの出力列の順序を
並べ替える。外部復号器２７が、逆インタリーブされた
列を当初の情報列を推定した推定列に変換し、この推定
列を宛先２８に伝送する。
【００３８】１９６７年以降、並行並列又は直列処理ユ
ニットをビタビ復号器に付加することによって古典的ビ
タビアルゴリズムを拡張する提案が、いくつも発表され
て来た。これらのユニットにおいては、最良の計量値を
有するパスだけを選択することによって失われた情報が
考慮に入れられ、付加情報が外部処理ステージに与えら
れている。拡張されたビタビアルゴリズムプロセッサに
は２つの総括的グループがある。
【００３９】第１のグループは、ソフト記号出力ビタビ
アルゴリズムとして知られるもので、伝送される情報列
の信頼性の尺度として各状態において合流する２つのパ
スの累積計量値の間の差を用いる。第２のグループは、
リスト又は一般出力アルゴリズムとして知られるもの
で、最良のパス又は残存物を見出すのに加えて、最良の
パスの次に最良の（Ｌ−１）個のパスを計算する。
【００４０】最初のプロセッサグループは、クラーク
（Clark） 及びデービス（Davis） によって１９７１年
に紹介された。彼らは、拡張ビタビアルゴリズムの一例
について述べ、そこには、復号化情報列に加えて、２値
方式の信頼性表示子＾Ｌが含まれていた。この＾Ｌは、
次の数式で表される。
【数４】
【００４１】（クラーク（G. Clark）及びデービス（R.
Davis）の論文「誤り補正符号化の通信システム設計へ
の最近の２適用例」（ＩＥＥＥ会報通信、第ＣＯＭ−１
９、第５号、８５６〜８６３、１９７１年１０月）参
照。）
【００４２】上記のフォーニーの初期の論文「ビタビア
ルゴリズム」に基づいて、シャウブ（Shaub） 及びモデ
スティーノ（Modestino） によって、抹消宣言ビタビ復
号化アルゴリズム（ＥＤＶＡ）が紹介された。これは、
１個の状態における全ての合流パスについて、それらの
計量値と残存パスの計量値との間の差を計算するもので
ある。もしこの差が定義されたしきい値より小さかった
場合、残存パス内の、これら２つのパスの間に差のある
位置は全て抹消された。
【００４３】（シャウブ（T. Shaub）及びモデスティー
ノ（J.W. Modestino）の論文「抹消復号化ビタビ復号器
及びその連結符号化システムへの適用」（ＩＣＣ '８
６、ＩＥＥＥ会議録Ｎｏ．ＣＨ２３１４−３／１８６、
１６１２〜１６１６、１９８６年）参照。）
【００４４】ハーゲナウエル（Hagenauer）及びヘーエ
ル（Hoeher） は、ソフト出力ビタビアルゴリズム（Ｓ
ＯＶＡ）を開発した（ハーゲナウエル（J. Hagenauer）
及びヘーエル（P. Hoeher） の論文「連結ビタビ復号
化」（情報理論についての第４回共同スエーデン／ソ連
国際ワークショップ、スエーデン国、ゴットランド、ス
テュデントリテラツール（ルント）１９８９年８月）参
照）。
【００４５】このアルゴリズムは、復号化情報ビットの
各々について、アナログの信頼性値＾Ｌを与える。これ
は次の数式で表される。
【数５】
【００４６】残存パス＾ｘ（ｓi） の全てについて、信
頼性ベクトル＾Ｌ（ｓi） が存在し、これは全ての位置
において高い値に初期設定される。全ての時点ｉにおい
て、又どの状態ｓi においても、この点において合流す
る２つのパスの累積計量値の間の絶対差△i（ｓi）が計
算される。
【００４７】信頼性ベクトル＾Ｌ（ｓi） 内の位置であ
って、選択されたアップデートウインドウδup内の２つ
のパスの間に差があるような位置の全て、及び現存する
信頼性値、＾Ｌi（ｓi）が△i（ｓi）よりも大きい
（ｍｉｎ｛△i（ｓi），Ｌi（ｓi）｝→＾Ｌi（ｓi））
ような位置の全てに絶対差△i（ｓi） が記憶される。
【００４８】このアップデート（更新）プロセスによっ
て、復号化情報ビット、＾ｘi の全てについて、最も小
さい信頼性値、＾Ｌi が外部処理ステージに与えられる
ことが保証される。ここで重要なのは、ソフト出力ビタ
ビアルゴリズム（ＳＯＶＡ）が、出力ビットの相関関係
を避けるために、常にインタリーブユニット及び逆イン
タリーブユニットを必要とすることである。
【００４９】第２のプロセッサグループは、リスト出力
ビタビアルゴリズム（ＬＶＡ）又は汎用ビタビアルゴリ
ズム（ＧＶＡ）として知られるグループで、上記のフォ
ーニーによって１９７３年に初めて紹介され、そこで彼
は、単一の最良パスでなくＬ個の最良パスを生成するよ
うにビタビアルゴリズムを改変することを提案した。
【００５０】又、１９８７年に、各復号化ステップにお
ける候補リストのうちの各リストからＬ個の最良残存候
補を選択するビタビアルゴリズムが、ハシモトによって
紹介された（ハシモト（T. Hashimoto）の論文「ビタビ
アルゴリズムのリスト形式縮小制約汎用化」（ＩＥＥＥ
会報、情報理論、第ＩＴ−３３巻、第６号、８６６−８
７６、１９８６年１１月）参照）。
【００５１】セシャドリ（Seshadri）及びサンドバーグ
（Sundberg）は、汎用ビタビアルゴリズムの（ＧＶＡ）
バージョンとして、格子の探索（サーチ）後、Ｌ個のグ
ローバルに最良の候補パスのランク順位付けしたリスト
を生成するバージョンを提供した。並列バージョン（Ｐ
ＧＶＡ）においては、Ｌ個の残存候補が、２・Ｌ個の候
補（２進符号と仮定）のうちから各復号化ステップにお
いて同時に選択される。これらＬ個の残存候補は、次の
復号化ステップにおいて拡張される。
【００５２】ブロックが伝送された後、外部復号器が、
Ｌ個の残存候補のリストから最適候補を選択する。別の
バージョンである直列汎用ビタビアルゴリズム（ＳＧＶ
Ａ）においては、前に見出された（ｔ−１）個の最良パ
ス（１＜ｔ≦Ｌ）の知識に基づいて「ｔ番目に最良」の
パスが繰り返し見出される。これについての特許がセシ
ャドリ及びサンドバーグによって１９９２年３月１１日
に米国で出願され（シリアル番号第０７／８５０,２３
９） 本発明の被譲渡人に譲渡された。
【００５３】汎用ビタビアルゴリズム（ＧＶＡ）を引用
する際に、最近はより正確な名称「リスト出力ビタビア
ルゴリズム（ＬＶＡ）が用いられてきている。ここで
は、文献に引用されているような、より一般的な名称
「汎用ビタビアルゴリズム」（ＧＶＡ）を用いることと
する。
【００５４】
【発明が解決しようとする課題】ビタビアルゴリズム
（ＶＡ）の拡張バージョンであるソフト出力ビタビアル
ゴリズム（ＳＯＶＡ）及び汎用ビタビアルゴリズム（Ｇ
ＶＡ）は、いずれも復号化の性能を改善するものである
が、しかしこれらを用いることによって、復号化システ
ムに複雑さとコストとが更に付加されることになる。
【００５５】本発明の目的は、これら従来のバージョン
の欠点の多くを回避できるような、ソフト出力ビタビア
ルゴリズム（ＳＯＶＡ）及び汎用ビタビアルゴリズム
（ＧＶＡ）の修正拡張バージョンのファミリーを提供す
ることにある。
【００５６】
【課題を解決するための手段】本発明では、汎用ビタビ
アルゴリズム（ＧＶＡ）における、複雑性を低くしたバ
ージョンを実現するために、ソフト出力ビタビアルゴリ
ズム（ＳＯＶＡ）を活用する。又、ソフト出力ビタビア
ルゴリズム（ＳＯＶＡ）における、複雑性を低くしたバ
ージョンを実現するために、汎用ビタビアルゴリズム
（ＧＶＡ）を活用する。これら拡張バージョンは、ブロ
ック符号及び他の形式の符号、種々の変調技術、及び他
の格子構造にも適用できるが、ここでは、畳込み符号へ
の適用について説明する。
【００５７】本発明の一態様によれば、ソフト出力ビタ
ビアルゴリズム（ＳＯＶＡ）の、伝送された可能性のあ
る列（シーケンス）のリストＬの長さが適応可能又は制
御可能な構造を用いて、直列汎用ビタビアルゴリズム
（ＳＧＶＡ）を新たに実現している。この実現例におい
ては、格子のノードにおけるパスの累積計量値の間の絶
対差を用いて、復号化格子を通るＬ個の最良のパスを繰
り返し見出す。前に見出されたｔ個の最良のパスに基づ
いて「（ｔ＋１）番目に最も近似」するパスを計算する
のに、最小絶対差と最良のパスの累積計量値の値とが用
いられる。
【００５８】本発明の別の態様においては、汎用ビタビ
アルゴリズム（ＧＶＡ）に基づく、複雑性の低い、ソフ
ト出力ビタビアルゴリズム（ＳＯＶＡ）が提供される。
この「ソフトＧＶＡ」は、汎用ビタビアルゴリズム（Ｇ
ＶＡ）のリスト出力を受け入れて、各復号化記号（シン
ボル）について出力記号信頼性尺度を計算する。最良の
パスの累積計量値とｔ番目に最良のパスの累積計量値と
の間の絶対差が、信頼性尺度のソフト初期設定に用いら
れるので有利である。
【００５９】本発明の更に別の態様によれば、サイズＬ
のリストを生成するのに、ソフト出力ビタビアルゴリズ
ム（ＳＯＶＡ）の信頼性情報を用いるので有利な、より
長い同一リストサイズについてのＧＶＡよりも複雑度の
低い、汎用ビタビアルゴリズム（ＧＶＡ）が開示され
る。この、単一状態の汎用ビタビアルゴリズム（ＧＶ
Ａ）は、Ｌ個の最良のパスを計算するために、単一状態
の格子においてソフト出力ビタビアルゴリズム（ＳＯＶ
Ａ）によって計算される信頼性値を用いる。
【００６０】
【実施例】Ｉ．前書き 連結符号化システムにおいて内部復号器２３として作動
するので有利な、本発明の一実施例としての復号器を図
３に示す。この第Ｉ項は、拡張リスト出力ビタビアルゴ
リズム及びソフト記号出力ビタビアルゴリズムの技術へ
の導入部となる。次の第ＩＩ項は、直列汎用ビタビアル
ゴリズム（ＳＧＶＡ）の実現についての実施例を詳しく
述べる。又、第ＩＩＩ項及第ＩＶ項においては、汎用ビ
タビアルゴリズム（ＧＶＡ）及びソフト出力ビタビアル
ゴリズム（ＳＯＶＡ）にそれぞれ基づく拡張ビタビアル
ゴリズムの実施例について説明する。
【００６１】ソフト出力ビタビアルゴリズム（ＳＯＶ
Ａ）（又は、ソフト出力ＶＡ）及び汎用ビタビアルゴリ
ズム（ＧＶＡ）（又は、汎用ＶＡ）は、ビタビアルゴリ
ズムを拡張又は修正するのに用いられる２種類のプロセ
ッサ又は復号器である。ソフト出力ＶＡは、復号化され
た出力記号（復号化出力記号）、＾ｘi、 についての信
頼性情報、＾Ｌ、を外部処理ステージへ渡す。
【００６２】ソフト出力ＶＡの機能は、誤り率を下げる
ことではなく、復号化出力記号の各々についての信頼性
情報＾Ｌを渡すことにより外部符号に対して相対的な信
号対雑音比を改善することである。これは、連結符号化
システムにおける最適外部プロセッサ（復号器）がソフ
ト入力データを受け入れること、又は信頼性値＾Ｌiを
後処理する能力を有すること、を意味する。したがっ
て、畳込み符号のような誤り補正符号は、外部符号とみ
なされる。
【００６３】これと対照的に、汎用ＶＡにおいては、外
部処理ステージに、伝送されたデータ列のＬ個の最良推
定値のリストを与える。したがって、外部ステージプロ
セッサは、可能性あるＬ個の候補のリストから最適の候
補を選択するというタスクを果たさなければならない。
汎用ＶＡについての、可能性ある外部符号は、パリティ
チェックコ−ドのような誤り検出符号である。又、音声
通信システムにおいては、音声予測装置によってこのタ
スクが処理可能である。
【００６４】このように、ここでの考慮対象の汎用ＶＡ
（ＧＶＡ）とソフト出力ＶＡ（ＳＯＶＡ）とは、構造が
異なるだけでなく、外部処理ステージへ供給する情報も
異なる。
【００６５】しかし、汎用ＶＡとソフト出力ＶＡとの間
の概念的及び構造的差にも拘らず、いずれのアルゴリズ
ムも、ビタビ復号器の決定の誤りについての情報を有す
る。ソフト出力ＶＡについては、格子のノードにおける
２つのパスの累積計量値間の絶対差、△i（ｓi）が、ビ
タビアルゴリズムの復号化決定の信頼性の表示子であ
る。この絶対差は、次の数式で定義される。 △i（ｓi）＝ｍａｘΓ（ｓi+1，ｓi）−ｍｉｎΓ（ｓi+1，ｓi）≧０
【００６６】絶対差の値が小さいことは、時点ｉ及び状
態ｓi におけるビタビアルゴリズムの決定の信頼性が低
いことを表示する。これらの差△i（ｓi）によって計算
される、ソフト出力ＶＡの信頼性値＾Ｌは、伝送された
データ列のＬ個の最良候補についての間接的情報を含
み、したがって、サイズＬのリストを生成するために用
いることが可能である。同様に、別の実施例において
は、記号ごとに信頼性情報を渡すために汎用ＶＡのリス
ト出力が用いられる。本発明のこの実施例は、ソフト汎
用ＶＡ（ソフトＧＶＡ）と称する。
【００６７】ここで注記したいのは、リストソフト出力
ＶＡすなわちリストＳＯＶＡ（ソフトＧＶＡ）が、ソフ
ト出力ＶＡすなわちＳＯＶＡ（ＧＶＡ）と同じデータ伝
送フォーマット及び構造を有することである。元のバー
ジョンとの差異は、出力フォーマットをソフト出力から
リスト出力へ、又はリスト出力からソフト出力へ変える
直列−後処理ユニット、だけである。
【００６８】本発明のこの実施例における復号化作業に
は、ソフト汎用ＶＡ（ソフトＧＶＡ）とリストソフト出
力ＶＡ（リストＳＯＶＡ）との技術が用いられるので有
利である。次の第ＩＩ項の説明では、直列汎用ビタビア
ルゴリズムの新たな実現について述べる。第ＩＩＩ項
は、汎用ＶＡに基づく、ソフト記号出力ビタビアルゴリ
ズムの実施例を扱う。
【００６９】符号化に関する他の説明において格子構造
についての説明の便宜上通常行われているように、オー
ルゼロの列を一般的とみなすと便利である。その場合で
も、それから得られる結果は一般性の点で制限されるも
のではない。本明細書ではその全体を通して、例示の目
的で２進符号を用いるが、ここに述べる実施例について
非２進符号への一般化が容易であることは、当業者に明
かである。
【００７０】ＩＩ．ＳＧＶＡ実現 本項では、「直列汎用ビタビアルゴリズム」（ＳＧＶ
Ａ）の実施例について述べる。本発明のこの態様では、
ＳＯＶＡ復号化によって計算される各状態において合流
するパス間の絶対差△i（ｓi）を有利に用いて、復号化
格子を通る伝送されたパス列のＬ個の最良のパスを繰り
返し見出す。まず、処理すべき列（シーケンス）が最大
自由距離２進畳込み符号を用いて符号化されているとき
に便利な、簡単化された計算技術について説明する。次
に、列を総体的に処理するのに便利な、ＳＧＶＡの実施
例について述べる。
【００７１】便利なように畳込み符号を２進構造と仮定
したので、図２の各状態ｓi において合流し又離れる２
個のブランチには、相補的遷移ビットｕi＝
（ｕi,1，．．．ｕi,n） が付随する。このことと、符
号の線形性とは、各状態において合流し又離れる２個の
ブランチの計量値増値分λ［ξi＝（ｓi+1，ｓi）］ も
反転されることを意味する。
【００７２】この、２進畳込み符号の対称性を用いて、
必要な計量値増値分の数を減少することができ、２v+1
個の代わりに２v-1個の計量値増値分λだけを計算しさ
えすればよい。これは、計算プロセスにおいては１／４
に減少することに相当する。
【００７３】メモリｖ＝２、符号レートＲ＝１／２、状
態総数Ｓ＝４の符号について、図４に示す状態 ｓsym＝Ｓ／２＝２v-1 において、図２の格子ステージを通る対称線５０が導入
される。この対称線５０は、状態ｓi+1 を２つのグルー
プに分割する。
【００７４】２v-1 個の最上部の状態ｓi+1 について
は、「０」が伝送され、他については、伝送される情報
ビットは「１」である。この事実は、ビタビアルゴリズ
ム復号器に必要とされる記憶を制限するのに用いられ
る。ビタビアルゴリズムの順方向計算の間、状態ｓi
（現在の残存パス＾ｘ（ｓi+1） がそこから得られたそ
この状態）の整数値だけを記憶しさえすればよい。
【００７５】後に、決定プロセスにおいて、状態値ｓi
が、対称線ｓsym と比較され、受信情報ビット＾ｘi が
次のように定められる。 ｓi＜ｓsym→＾ｘi＝０ ｓi≧ｓsym→＾ｘi＝１
【００７６】各状態を離れる２個のブランチは、逆情報
ビットのため、図４に示すように、計量値増値分λ［ξ
i＝（ｓi+1，ｓi）］ を反転した。したがってこの場
合、状態ｓi＜ｓsymについての計量値増値分λ［ξi＝
（ｓi+1，ｓi）］ だけを計算しさえすればよい。状態
ｓi≧ｓsymについては、計量値増値分は、つぎのように
反転される。 λ（ｓi+1）＝−λ（ｓi+1−ｓsym，ｓi） これによって計算プロセスは１／２に減少する。
【００７７】シフトレジスタｓi の内容は最下桁のビッ
トが異なるだけなので、各状態ｓi+ 1 において合流する
２個のパスの計量値増値分λ［ξi＝（ｓi+1，ｓi）］
は反転される。
【００７８】したがって、計量値増値分、及び累積計量
値について、それぞれ次の新定義が得られる。
【数６】 上記（１）式において、伝送情報ビット「０」について
の計量値増値分だけが考慮される（ｓi＝０，２，
４，．．．，Ｓ−２）。
【００７９】各復号化ステップにおいて２v+1個の計量
値増値分λ［ξi＝（ｓi+1，ｓi）］を計算する代わり
に、２v-1 個の計量値増値分λ（ｓi+1） だけを計算し
さえすればよい。基本的なシフトレジスタ構造を有する
最適２進符号について１／４の減少が得られる。この新
技術を、メモリｖ＝２，符号レートＲ＝１／２の符号の
場合について図５に示す。
【００８０】汎用ビタビアルゴリズムの直列バージョン
（ＳＧＶＡ）が１回に１個づつＬ個の最良の候補を見出
す。前に見出された（ｔ−１）個の最良の候補の知識を
用いて、ＳＧＶＡがｔ番目に最も近似性の高い候補を繰
り返し計算する。
【００８１】２進符号についてのＳＧＶＡの新しい実現
技術について次に説明する。これは、「次に最良」の候
補を識別するのに、各状態ｓi において合流する２個の
パスの累積計量値間の絶対差△i（ｓi）を用いる技術で
ある。長さＮの終結データ列｛ｘi｝ （ブロックによる
データ伝送）だけを考慮すると有利であることが判って
いる。
【００８２】各時点ｉ及び各状態ｓi についての標準的
なビタビアルゴリズム順位計算の間、計量値増値分λ
（ｓi）、 累積計量値Γ（ｓi）、 又はオプションとし
て絶対差△i+1（ｓi+1）、が便利に記憶されると仮定す
る。又、主パス状態アレイが利用可能であると仮定する
のも有利であることが判っている。
【００８３】時点ｉにおける２個の累積計量値Γ
(m)（ｓi）の知識と時点ｉ＋１における計量値増値分λ
（ｓi+1） の知識とから、各状態ｓi+1について、絶対
差△i+1（ｓi+1） が計算できる。上側ブランチに関連
する累積計量値Γ(1)（ｓi）に、ｍ＝１のラベルを付け
るものとする。前に用いられた計量値増値分の表示法と
対称線ｓsym＝２v-1とを用いて、各状態ｓi+1 における
絶対差△i+1（ｓi+1）は、次のように計算される。
【数７】
【００８４】この計算ステップを図６に示す。このステ
ップは、結果としてストリームライン化した計算が得ら
れるオプションである。短リスト高信号対雑音比又は、
高複雑度符号（高符号メモリ）については、順位計算の
間、計量値増値分と累積計量値とを記憶し、「次に最
良」のパスが必要とされるときにだけ絶対差を計算する
ことが望ましい。
【００８５】絶対差△i（ｓi）は、グローバルに「２番
目に最良」のパス、「３番目に最良」のパス、等につい
ての、次のような間接情報を含んでいる。
【００８６】まず、メモリｖ＝２及びブロック長さＮ＝
１０を有する符号について、伝送データ列｛ｘi｝ の最
良の推定が、図７に示すようなオールゼロのパス６０で
あると仮定する。各時点ｉについて、最良のパスに沿っ
ての絶対差△i（ｓi）が知られている。これらのことか
ら、主パス状態アレイは、パス列を識別するのと、上に
述べたように△i（ｓi）を計算するのとに用いられ、又
は、△i（ｓi）値を記憶するのに用いられる。ここで、
最良のパス６０に沿って最小差
【数８】 がサーチされる。
【００８７】図７中、時点ｉ＝５における最小差△min
は、「２番目に最良」のパス６１が最良のパスと時点ｉ
＝５において再合流することを意味する。図７における
絶対差△i（ｓi）の値は任意である。主パス状態アレイ
を用いて、「２番目に最良」のパス６１が、形成され
る。再合流の位置（ｉ＝５）が記憶される。
【００８８】次に、「３番目に最良」のパス６２を生成
するために、図８に示すように、「２番目に最良」のパ
スに沿う絶対差値△i（ｓi） が、最良のパスの絶対差
値△i（ｓi）を用いて初期設定される。これに加えて、
再合流点（ｉ＝５） から合流点（ｉ＝２）までの差だ
けを計算すればよい。図７と対比されたい。それから、
「３番目に最良」のパスについて別の候補６３が、最良
のパスから識別、特定される。
【００８９】更に、両方の差列における再合流点が高い
値、△i=5（ｓi=5）＝＋∞、にセットされる。これは、
この点が、再合流点として識別されるべき両方のパス列
において除外されていることを意味する（図９参照）。
両方のパス列について、最小差△min が見出される。こ
れは、「３番目に最良」のパスについて今、２つの可能
性ある候補、６２及び６３、が存在することを意味す
る。
【００９０】候補を選択するために、可能性ある両方の
候補について、状態 ｓN＝（０．．．０）における累積
計量値が計算される。それから、状態ｓN＝（０．．．
０）における高い方の計量値Γ（ｓN＝０） を有する方
の候補が、伝送データ列の「３番目に最良」の推定候補
として選択される。関連する情報列は、主パス状態アレ
イを用いることにより計算できる。
【００９１】最小差△min の知識と、状態ｓNにおける
最良のパスの累積計量値Γbest（ｓN＝０） の値とか
ら、時点ｓN＝（０．．．０） における「２番目に最
良」のパスの累積計量値Γ2nd best（ｓN＝０） が次の
数式によって計算される。 Γ2nd best（ｓN＝０）＝Γbest（ｓN＝０）−△min （２） 尚、このステップは、「ｔ番目に最良のパスの次に最
良」の候補について容易に一般化できる。
【００９２】「３番目に最良」の候補６３が、図９に示
すように時点ｉ＝７において最良パス６０と再合流した
と仮定する。「４番目に最良」のパスを識別するため
に、「３番目に最良」のパスに沿う差が、最良のパスの
絶対差で初期設定され、それから合流点と再合流点との
間の差が計算され、両方のパス列における再合流点が除
外される。更に、最良パスと「３番目に最良」のパスと
について、最小差 △minが計算される。これは、「４番
目に最良」のパスについての次に可能性ある候補の再合
流点を意味する。
【００９３】数式（２）に基づき、これら２つの候補に
ついて、状態ｓN＝（０．．．０）における累積計量値
が計算される。グローバルに「２番目に最良」のパスに
基づく「４番目に最良」のパスについての最終候補は、
「３番目に最良」のパスの前候補６２である。この候補
パスは既に存在する。したがって、このパスについての
累積計量値は、計算の必要がない。「４番目に最良」の
パスが、最大計量値を有する候補パスである。
【００９４】ここで注記したいのは、新しいリスト要素
の各々について、可能性ある２つの新しい候補だけを計
算すればよいことである。したがって、「ｔ番目に最
良」のパスは、前に見出された（ｔ−１）個の最良のパ
スについて「次に最良」の候補と状態ｓN＝（０．．．
０） におけるその累積計量値とを推定することによっ
て見出される。可能性ある候補のリスト既に存在するパ
スと同一である候補パスは、削除される。
【００９５】直列汎用ビタビアルゴリズム（直列ＧＶＡ
（ＳＧＶＡ））の形成手順の一例は、図１０の流れ図に
示すように、次のステップから構成される。
【００９６】・ステップ１ サイズ２v×Ｎの主パス状態アレイ、サイズ２v-1×Ｎの
計量値増値分アレイ、及びサイズ２×Ｎの累積計量値ア
レイを形成する。主パス状態アレイにおけるエントリＥ
ijは、時点ｊにおいて状態ｓi-1 で終結する最良のパス
の履歴の集約である。更に、サイズＬ×ＮのＬ個の最良
のパスの蓄積記憶としてのアレイ、及びサイズＬ×Ｎの
Ｌ個の最良のパスに沿っての絶対差、についてのアレイ
を形成する。
【００９７】又、各々サイズＬ×ｔを有する３つの補助
アレイを形成する。その第１、ｚ（ｔ）は、「ｔ番目に
最良」のパス及びその次の候補パスの再合流点を記憶す
るためのアレイである。第２の補助アレイは、次に可能
性ある候補の状態 ｓN＝（０．．．０）における累積計
量値についての記憶用として用いられる。又、第３の補
助アレイは、Ｌ個のパスの状態ｓN＝（０．．．０） に
おける累積計量値を記憶する。
【００９８】・ステップ２ ビタビアルゴリズムを実行する。そして、各時点ｉにお
いて又各状態ｓi について、パスの履歴、累積計量値、
及び計量値増値分を記憶する。
【００９９】・ステップ３ 見出された候補の数、ｔをｔ＝１に初期設定する。ｔ’
をｔ’＝１に初期設定する。ここに、ｔ’は、「（ｔ＋
１）番目に最良」のパスが再合流する相手のパスのリス
ト番号である。最後の再合流点をＮに初期設定する、す
なわちｚ（１）をＮにセットする。ｍを１にセットす
る。ここに、ｍは補助パラメータである。
【０１００】・ステップ４ 絶対差を計算して、「ｍ番目に最良」のパスに沿って記
憶する。 ・ステップ５ 前に見出された再合流点ｚ（ｍ）を除外する（例えば、
△（ｓi=z(m)）＝＋∞にセットする）。
【０１０１】・ステップ６ 「ｍ番目に最良」のパスに沿って最小絶対差△min＝ｍ
ｉｎN｛△（ｓi）｝ を見出し、位置を、ｚ（ｍ）に、
そして与えられたアレイに記憶する。 ・ステップ７ ステップ６に述べた再合流点ｚ（ｍ）を通るパスｍ、の
「次に最良」の候補パスの状態ｓN＝（０．．．０）に
おける累積計量値Γ（ｓN＝０）を計算して記憶する。
【０１０２】・ステップ８ 候補パスｍが「（ｔ＋１）番目に最良」のパスについて
提案された候補のリストに存在するかどうかを点検す
る。もし存在する場合、ステップ５からステップ８まで
を繰り返す。 ・ステップ９ もしｔ≧２の場合、ｍ＝ｔ’を有するパスｔ’につい
て、ステップ５からステップ８までを繰り返す。
【０１０３】・ステップ１０ 「（ｔ＋１）番目に最良」のパスについての可能性ある
ｔ個の候補の全てに対して、状態ｓN＝（０．．．０）
における最高の累積計量値Γ（ｓN＝０） を選択する。
この候補は、伝送されたデータ列の「（ｔ＋１）番目に
最良」のパスである。「（ｔ＋１）番目に最良」のパス
が再合流する相手のパスのリスト番号を、ｔ’として記
憶する。再合流点を、ｚ（ｔ）及びｚ（ｔ’）に記憶す
る。ｍをｍ＝１にセットする。
【０１０４】・ステップ１１ ｔをｔ＋１にセットし、ステップ４からステップ１１ま
でを、ｔ＝Ｌになるまで繰り返す。
【０１０５】ＩＩＩ．ＧＶＡに基づくソフト記号出力ビ
タビアルゴリズム（ソフトＧＶＡ） この項では、複雑度の低い、ソフト記号出力ビタビアル
ゴリズムの実施例を説明する。本アルゴリズムは、汎用
ビタビアルゴリズム（ＧＶＡ）のリスト出力を受け入れ
て、復号化情報ビットの各々について信頼性値を計算す
るものである。本実施例を、ソフトＧＶＡと称する。本
アルゴリズムは、最良パスと「ｔ番目に最良」のパス
（１＜ｔ≦Ｌ）との累積計量値における差を、復号化情
報ビットの各々の信頼性の計測値として用いる。
【０１０６】汎用ビタビアルゴリズムに基づく、ソフト
記号出力ビタビアルゴリズムの原理説明用ブロック図を
図１１に示す。上記セシャドリほかによって記述されて
いるような、汎用ビタビアルゴリズム（ＧＶＡ）１００
が、計量値と可能性ある列のリストＬとを出力する。ソ
フト記号ユニット１０１が、このリストを用いて、復号
化された記号及びその記号についての信頼性計測値を生
成する。
【０１０７】又、ここで説明するソフトＧＶＡについて
は、当初に符号化されたデータ列が、（Ｎ−ｖ）個の情
報ビットとブロックを終結するために用いられるｖ個の
ビットとからなるＮ個のビットのブロックであることを
注記したい。
【０１０８】上記のＳＧＶＡにおいては、絶対差△
i（ｓi）の知識を用い、（ｔ−１）個（１≦ｔ≦Ｌ）の
提案された候補について状態ｓN＝（０．．．０） にお
ける累積計量値 Γ（ｓN＝０）を求めることによって、
「ｔ番目に最良」のパスが識別された。Ｌ個の最良パス
列と、対応するそれらの累積計量値との知識を用いるこ
とによって、ソフト記号出力ビタビアルゴリズム（ソフ
トＧＶＡ）をＧＶＡに基づいて構築できる。
【０１０９】ソフト出力ビタビアルゴリズム（ＳＯＶ
Ａ）においては、状態ｓi において合流する２つのパス
の累積計量値間の絶対差△i（ｓi）が、ビタビアルゴリ
ズム復号器の決定の信頼性の計測値である。汎用ビタビ
アルゴリズム（ＧＶＡ）については、ビタビアルゴリズ
ム復号器の決定の信頼性の計測値は、最良パスと「ｔ番
目に最良」のパス（２≦ｔ≦Ｌ）との状態ｓN＝
（０．．．０） における累積計量値 Γ（ｓN＝０）間
の差に見出される。この差を、△t *と名付ける。ここ
に、２≦ｔ≦Ｌである。
【０１１０】尚、最良のパスと「２番目に最良」のパス
との間の差、△2 *も、ブロックでのデータ伝送において
ＳＯＶＡによって得られる。復号化された情報ビットに
ついての信頼性値は、次の方法で得られる。同方法にお
いて、ステップ１は、初期設定手順を示し、ステップ２
からステップ５までは、その更新手順を示す。
【０１１１】１．長さ（Ｎ−ｖ）の信頼性ベクトル、
Ｌ、の全ての位置を定数値Ｃ1 で初期設定する。ここ
に、Ｃ1 は次の式で表される。
【数９】 ２．パスｔについて、状態ｓN＝（０．．．０） におけ
る累積計量値 Γ（ｓN＝０）が利用可能なことに留意す
る（上記ＳＧＶＡ実現の項参照）。
【０１１２】３．「ｔ番にの最良」のパスについて、状
態ｓN におけるその累積計量値を状態ｓN における最良
のパスの累積計量値から差し引いた差を計算する（次
式）。ここに、２≦ｔ≦Ｌである。 △t *＝Γbest（ｓN＝０）−Γt-th best（ｓN＝０） 得られた差△t *は常に、正の実数の要素である（次
式）。
【数１０】
【０１１３】４．それから、「ｔ番にの最良」のパスの
情報ビット列を、最良のパスの情報ビット列と比較し
て、これら２つのパスの間に差のある情報ビットの位置
を定める。 ５．最良のパスと「ｔ番にの最良」のパスとの間に差の
あるこれらの位置の全てにおいて、現存する信頼性値が
差△t *よりも大きいときを記憶する（すなわち、＾Ｌ←
ｍｉｎ｛＾Ｌ，△t *｝）。
【０１１４】６．１＜ｔ≦Ｌに対して、ステップ２から
ステップ５までを繰り返す。これは、サイズＬのリスト
に対して、復号化された情報ビット当り最高（Ｌ−１）
回の更新を意味する。
【０１１５】定数Ｃ1 を用いて初期設定するのに反し、
ソフト初期設定を用いることにより、性能が改善され
る。ＳＧＶＡが、伝送されたデータ列の「次ぎに最良」
の推定を見出すのに絶対差△i（ｓi）を用いることを想
起して頂きたい。「２番目に最良」のパスについてのサ
ーチの間、これらの絶対差△i（ｓi）は、図１２に示す
ように、補助アレイに記憶させておくことができる。
【０１１６】ソフト初期設定を得るために、この補助ア
レイが、伝送された末尾ビット（ν）の数だけシフトさ
れ、それから信頼性ベクトルが、これらシフトされた値
で初期設定される。図１２は、ν＝２を有する符号につ
いてのシフトを示す。
【０１１７】このプロセスは、長さδup＝ν＋１の更新
ウインドウを用いるＳＯＶＡの場合と同等である。信頼
性ベクトルをこれらシフトされたソフト値で初期設定の
後、上記ステップ２からステップ５までを用いて信頼性
ベクトルが更新され、各記号についての信頼性値が生成
される。こお初期設定方法を、「１ー更新ＳＯＶＡ」と
称する。
【０１１８】尚、他の初期設定方法も可能である。例え
ば、正規化された値での更新プロセスも用いられる。本
実施例においては、差△t *は、上記のように計算され
る。長さＮの信頼性ベクトルは、全ての位置において、
値「１」に初期設定される。次に、最良のパスと「ｔ番
目に最良」のパス（２≦ｔ≦Ｌ）との情報ビット間に差
が存在する位置が定められる。それから、差は次式のよ
うに正規化される。
【数１１】
【０１１９】更新プロセスは、△t *の代わり正規化値
（△t *の上又は前にオーバライン￣を置いて表す）を代
入した固定の初期設定値を用いるソフトＧＶＡの場合と
同じである。同様に、可変初期設定値技術も用いられ
る。この技術は、各データブロックについて最大累積計
量値を用い、累積計量値が、ブロックを伝送している間
のチャンネル品質についての間接情報を含むことを認識
する。より高い相関関係（より高いΓbest（ｓN＝
０）） は、ブロックの動作がより高い信頼性を有する
ことを示すものである。
【０１２０】しかし、各ブロックを、チャンネル品質に
無関係に個々に、 初期設定値＝ΓL（ｓN＝０）＋Ｃ2 を用いて初期設定することが可能である。ここに、定数
Ｃ2 は、正の実数の要素である。信頼性ベクトルの初期
設定値は、ブロックによって異なる。ソフトＧＶＡを得
るための手順は、△t *を用いた固定初期設定値の場合と
同じである。インタリーブ処理の後、もし逆インタリー
ブ器が十分大きく選択されていれば、出力ビットは各
々、異なる信頼性値を有する。
【０１２１】ＩＶ．ＳＯＶＡを用いるリスト出力ビタビ
アルゴリズム（リストＳＯＶＡ） この項は、リスト出力ビタビアルゴリズムについて説明
する。このアルゴリズムは、ＳＯＶＡに比較的複雑度の
低いリスト生成ユニットを有利なように付加したもの
で、サイズＬのリストを生成するために、信頼性値＾Ｌ
を用いる。ＳＯＶＡは単独で、ソフト出力記号＾Ｌi を
順次に且つ連続的に生成する。ここにおいて、各記号の
振幅には、その記号についての信頼性情報が含まれる。
ＳＯＶＡは、かなり複雑度の高いアルゴリズムである。
【０１２２】しかし、複雑度の低いリスト生成ユニット
を付加することによって、リストＳＯＶＡ（ＳＯＶＡ及
びリスト生成ユニット）の複雑度は、サイズＬを有する
より長いリストについては、対応するＧＶＡよりも複雑
度が一般に低い。ＳＯＶＡ出力を用いてサイズＬのリス
トを生成するリスト生成ユニットの、考えられる２つの
技術について述べる。複雑度の低いリスト生成ユニット
を実現するためには、次に述べる事項が重要である。
【０１２３】１．ＧＶＡは一般に、長さＮを有する終結
されたデータ列上で作動するが、終結されたデータ列以
外のデータ列も使用できることは、当業者には容易に認
識される。すなわち、ＧＶＡ出力の各リスト要素は長さ
Ｎを有する。
【０１２４】２．上記１項の結果として、リスト生成ユ
ニットは、各々長さＮを有するＬ個の出力列を生成する
ことになる。連続データ伝送システムにおいては、ブロ
ック方式のデータ伝送におけるＮビットには、情報を持
たず状態 ｓN＝（０．．．０） においてデータ列を終
結するために用いられるｖ個の末尾ビットを有するの
で、長さは又Ｎ−ｖともなり得る。
【０１２５】３．ＳＯＶＡは、連続データ伝送に適用さ
れるので、インタリーブユニット（及び逆インタリーブ
ユニット）を必要とする。これは、図１３に示すよう
に、ＳＯＶＡ８０とリスト生成ユニット８２との間にイ
ンタリーブ器８１を付加することを意味する。逆インタ
リーブ器の程度は、任意であるが、各長さＮの数ブロッ
クにわたって誤りバーストを拡散させるに十分な大きさ
が望ましい。これに対応するインタリーブ器が、畳込み
符号器の前に付加される。
【０１２６】長さＮの終結されたデータ列（ブロック方
式のデータ伝送）上で作動するリストＳＯＶＡを見出す
ために、前記２つの技術のうちの１つとして、 「２k方
法」と称する技術が開発された。この技術においては、
リストＬ上の生成されたリスト要素の各々が、ブロック
方式、又はインタリーブされた連続方式のデータ伝送に
おけるＳＯＶＡ出力の特定の誤りパターンを反映する。
「２k方法」 は、次のステップから構成される。
【０１２７】・ステップ１ 次のパラメータが定義される。 −−最小振幅αk。ここに、１≦ｋ≦Ｌ。 −−２進ビットフリッピングアレイｚk（Ｌ*）の要素。
ここに、
【数１２】 且つ、０≦Ｌ*≦Ｌ−１。
【０１２８】・ステップ２ 図１３におけるリスト生成ユニット８２への入力列、＾
ｙは長さＮで、ここに、各要素は、信頼性値（振幅）＾
Ｌj （次式で表す）
【数１３】 と、復号化された情報ビットの値を表す符号値＾ｘj＝
符号（＾ｙj）とからなる（１≦ｊ≦Ｎ）。振幅＾Ｌj
は、便利なように順位付けされ、対応する情報ビット値
＾ｘj が最低値からＬ番目に低い値まで次のように並べ
られる。
【数１４】
【０１２９】・ステップ３ サイズ８のリストについて定義された、２進ビットフリ
ッピング方式 （２k方法）を「表１」に示す。ここで、
第１のリスト要素についてＬ*＝０、 第８のリスト要素
についてＬ*＝７ として表記される。理由は、この表記
法においては、Ｌ* の整数値が２進ビットフリッピング
方式、ｚ（Ｌ*） に直接対応するからである。
【０１３０】この方式において、要素ｚk（Ｌ*）＝１
は、ｋ番目に最小の振幅を有するビットが、リスト要素
Ｌ* を生成するためにフリップされなければならないこ
とを意味する。言い替えれば、リスト要素Ｌ*は、ｋ番
目に最小の振幅αk、
【数１５】 に対応する情報ビット値＾ｘjを、 ＋１から−１に、又
は−１から＋１に変化させること（ビットフリッピン
グ）により生成される。
【０１３１】例えば、「表１」のリスト要素Ｌ*＝５
は、ｚ（５）が位置「１」及び「３」に値「１」を有す
るので、最小の振幅α1 及び３番目に最小の振幅α3 を
有する情報ビットをフリップすることによって生成され
る。
【表１】
【０１３２】・ステップ４ 注記したいのは、 ２k方法（２進ビットフリッピング方
式）には、各リスト要素Ｌ* の整数値が、長さＮの出力
列内の誤りのあるビットの振幅値を直接に反映するとい
う利点があることである。例えば、もしリスト要素Ｌ*
＝５ が成功である場合、最小の振幅（α1） 及び３番
目に最小の振幅（α3） を有する情報ビットが、出力に
おける２ビットの誤りを識別することが判る。
【０１３３】逆インタリーブ後のＳＯＶＡ出力は、誤り
事象発生の場合、長さＮのブロックにおいて主として単
一または２重の誤りから構成される。これらの誤りは、
高い信号対雑音比（ＳＮＲ）について特に、そのブロッ
クの他の情報ビットよりも小さい振幅を有する。複雑度
の低いリスト生成ユニットを構築するための第２の技術
（「単一状態ＧＶＡ」と称される）は、この知識を用い
てサイズＬのリストを生成するもので、以下にその手順
を説明する。
【０１３４】・ステップ１ ２k方法 のステップ１及びステップ２に基づき、各ブロ
ック内のＬ個の最低信頼性値＾Ｌが、識別、特定され、
ランク順に並べられる。最小振幅αk （１≦ｋ≦Ｌ）
が、長さＮのブロックのＬ個の最も小さい信頼性値を有
すると仮定する。ここで、指標１（α1） が最小の振幅
に対応し、指標Ｌが「Ｌ番目に最小」の振幅を示す。
【０１３５】・ステップ２ 図１４に示すように、これらの最小振幅αk は、単一状
態格子に付随する。それから、ＳＧＶＡは、前に述べた
ように、受信されたデータ列のＬ個の最良のパスを計算
するのに有利に用いられる。計量値増値分λ（ｓi）
は、最小振幅αkである（ｋはｉに等しい）。
【０１３６】格子の上部ブランチは、「＋１」に対応す
る。これはビットフリッピングがないことを意味する。
そして下部のブランチにおいて、「−１」の伝送は、ビ
ットフリッピングを意味する。尚、最小振幅αk の値
は、常に正である（次式）。
【数１６】
【０１３７】受信されたデータ列のＬ個の最良のパスに
は、ビットフリッピング方式が次のように含まれる。
「ｔ番目 に最良」のパス列内の位置ｋにおける「−
１」は、「ｋ番目に最小」の振幅が、リスト要素ｔを生
成するためにフリップされなければならないことを示
す。尚、４番目のリスト要素の後、ビットフリッピング
方式は２k方法 と異なり、「ｔ番目に最良」のパスが最
良の計量値を有する候補パスとして選択される。
【０１３８】したがって、「単一状態ＧＶＡ」技術は、
長さＮのブロックについて「Ｌ番目に最良」の最大累積
計量値を見出すものとして次式で表現できる。
【数１７】
【０１３９】この技術は、逆インタリーブされたＳＯＶ
Ａ出力から長さＬのリストを生成するのに便利に使用で
きる。この方法は、Ｌ個の最良のパスについてＬ個の最
小振幅だけを見出せばよいので、複雑度が低い。リスト
は、考慮対象のリスト要素の番号を表すＬを表記に用い
る。ＳＯＶＡとインタリーブ器とは、効果的に符号を除
去する。「単一状態ＧＶＡ」は、符号化されないデータ
についてのリスト出力ＧＶＡである。
【０１４０】以上、方法及びアルゴリズムについて、具
体的なハードウエア又はソフトウエアを引用せずに述べ
た。その代わりに、個々のステップを、特定の適用につ
いて利用可能な又は好ましいハードウエア又はソフトウ
エアを当業者がすぐに採用できるような仕方で説明し
た。
【０１４１】又、上記の説明は、本発明に係るＳＧＶ
Ａ、リストＳＯＶＡ、及びソフトＧＶＡを、可能性ある
適用例の１つとして、畳込み符号の復号化について行っ
たが、本発明は、畳込み符号以外に、復号化のプロセス
中の関連時点の各々における処理状態を記述するのに格
子構造を用いる他の事例、にも適用できることを強調し
たい。同様に、上に述べた２進符号も、本発明の適用範
囲を制限するものではない。
【０１４２】以上の説明は、本発明の一実施例に関する
もので、この技術分野の当業者であれば、本発明の種々
の変形例を考え得るが、それらはいずれも本発明の技術
的範囲に包含される。
【０１４３】
【発明の効果】以上述べたごとく、本発明によれば、ビ
タビアルゴリズムの拡張バージョンであるソフト出力ビ
タビアルゴリズム（ＳＯＶＡ）及び汎用ビタビアルゴリ
ズム（ＧＶＡ）にソフト記号ユニット、又はリスト生成
ユニット等を組み合わせたので、従来より複雑度の低い
ＳＯＶＡ及びＧＶＡの修正拡張バージョンアルゴリズム
が得られ、ディジタル通信における復号化プロセスの効
率が改善される。
【図面の簡単な説明】
【図１】ディジタル通信システムの一般的ブロック図で
ある。
【図２】符号レートＲ＝１／２の畳込み符号を復号化す
るための格子構造の１個のセグメントを示す説明図であ
る。
【図３】連結符号化を用いる通信システムについての構
造を示すブロック図である。
【図４】縮小計量計算についての対称線を用いて符号レ
ートＲ＝１／２の畳込み符号を復号化するための格子構
造の１個のセグメントを示す説明図である。
【図５】より効率的な累積計量計算を用いて符号レート
Ｒ＝１／２の畳込み符号を復号化するための格子構造の
１個のセグメントを示す説明図である。
【図６】直列汎用ビタビアルゴリズムを実現するために
絶対差を定める際の計算ステップを示す説明図である。
【図７】格子内の最小絶対差を有する点を識別すること
による格子を通る２番目に最良のパスを示す説明図であ
る。
【図８】合流点と再合流点との間の絶対差を計算するこ
とによる２番目に最良のパスに基づく格子構造を通る３
番目に最良のパスについての、可能性ある１個の候補を
示す説明図である。
【図９】最小絶対差を有する点を識別することによる最
良のパスに基づく格子を通る３番目に最良のパスについ
ての、可能性ある別の候補を示す説明図である。
【図１０】ソフト記号出力ビタビアルゴリズムに基づい
て直列汎用ビタビアルゴリズムを形成するために必要な
ステップを示す流れ図である。
【図１１】ソフト汎用ビタビアルゴリズムのブロック図
である。
【図１２】ソフト汎用ビタビアルゴリズムについてのソ
フト初期設定の原理を示す説明図である。
【図１３】リストソフト記号出力ビタビアルゴリズムの
ブロック図である。
【図１４】単一状態汎用ビタビアルゴリズムを示す説明
図である。
【符号の説明】
１０、２０ 情報源（ソース） １１、 ソース符号器 １２ チャンネル符号器 １３ 変調器 １４ 伝送路（チャンネル） １５ 復調器 １６ チャンネル復号器 １７ ソース復号器 １８、２８ 宛先 ２１ 外部符号器 ２２ インタリーブ器 ２３ 内部符号器 ２４ チャンネル ２５ 内部復号器 ２６ 逆インタリーブ器 ２７ 外部復号器 ３０〜３７ ノード ４０〜４７ 枝（ブランチ） ５０ 対称線 ６０ 最良のパス ６１ ２番目に最良のパス ６２、６３ ３番目に最良のパス ８０ ＳＯＶＡ ８１ インタリーブ器 ８２ リスト生成ユニット １００ 汎用ビタビアルゴリズム（ＧＶＡ） １０１ ソフト記号ユニット
フロントページの続き (72)発明者 カール−エリック ウィルヘルム サンド バーグ アメリカ合衆国、07928 ニュージャージ ー、チャットハム、エー11、ヒッコリー プレイス 25

Claims (25)

    【特許請求の範囲】
  1. 【請求項１】 候補信号列の各々が長さＮの列を表すＬ
    個の最良の候補信号列からなる信号列セット、を定める
    ために信号列を処理する、信号処理方法において、 前記Ｌ個の最良の候補信号列からなる信号列セットのう
    ちの各要素ｔ（１≦ｔ≦Ｌ）が、各々複数の状態を有す
    るＮ個のステージを設けた１個の格子構造を通る１個の
    パスに対応し、 （ｔ＋１）番目に最良の候補信号列が、最初のｔ個の最
    良の候補信号列の知識から導かれ、 前記格子を通る（ｔ＝１）の最良のパスが知られてお
    り、 各ステージにおける各状態に入る各パスが、そのパスに
    付随する累積計量値を有し、 各ステージにおける各状態に入る各パスが、次のステー
    ジにおける別の状態への遷移に付随する計量値増値分を
    有し、 各パスについての各ステージにおける状態が知られてお
    り、 ｔ’が、（ｔ＋１）番目に最良のパスの再合流相手のパ
    スの番号であり、 前記（ｔ＋１）番目に最良のパスが前記ｔ’番目のパス
    と再合流するステージが、再合流点であり、 前記再合流点が、前記格子のＮ番目のステージに等しく
    初期セットされ、そこにおいてｔ＝ｔ’＝１である、 信号列を処理する、信号処理方法であって、 ａ．そのステージにおいて合流するパスの累積計量値の
    差の大きさを各ステージにおいて表す複数の絶対差を、
    ｔ’番目に最良のパスに沿って計算し記憶するステップ
    と、 ｂ．前に見出された再合流点を排除するステップと、 ｃ．前記ｔ’番目に最良のパスに沿って最小絶対差を見
    出して、その最小絶対差の位置を記憶するステップと、 ｄ．前記合流点を通るｔ番目のパスに次いで最良の候補
    の最後の状態において累積計量値を計算し記憶するステ
    ップと、 ｅ．もし候補ｔが、（ｔ＋１）番目に最良のパスについ
    ての提案候補者リストに存在する場合に、前記ｂからｄ
    までのステップを繰り返すステップと、 ｆ．もしｔ≧２である場合に、パスｔ’について前記ｂ
    からｄまでのステップを繰り返すステップと、 ｇ．ｔ個の候補パスのうちの、最終状態において最良の
    累積計量値を有する１個の候補パスを、（ｔ＋１）番目
    に最良のパスとして選択し、（ｔ＋１）番目に最良のパ
    スの再合流相手のパスをｔ’として記憶し、その再合流
    点を記憶するステップと、 ｈ．ｔを１だけ増値するステップと、 ｉ．ｔ＝Ｌになるまで前記ａからｈまでのステップを繰
    り返すステップと、 からなる、 ことを特徴とする信号列を処理する、信号処理方法。
  2. 【請求項２】 前記信号列が畳込み符号によって符号化
    されていることを特徴とする請求項１の方法。
  3. 【請求項３】 前記畳込み符号器が、連結符号化要綱内
    の内部復号器であることを特徴とする請求項２の方法。
  4. 【請求項４】 前記（ｔ＝１）の最良のパス、前記累積
    計量値、及び前記増値分計量値が、ビタビアルゴリズム
    を用いて計算されることを特徴とする請求項１の方法。
  5. 【請求項５】 前記信号列が、最大自由距離２進畳込み
    符号化信号列であることを特徴とする請求項１の方法。
  6. 【請求項６】 前記計量値増値分が、Ｓを前記格子にお
    ける状態の総数とした場合に状態ｓsym＝Ｓ／２ におけ
    る対称線ｓsym を用いて計算され、この計算手法におい
    ては、計量値増値分λ［εi＝（ｉ＋１，ｉ）］ が、ｓ
    i+1＜ｓsymの状態においてのみ計算を要し、ｓi+1≧ｓ
    symの状態においては計量値増値分が、λ（ｓi+1，
    ｓi）＝−λ（ｓi+1−ｓsym，ｓi） となるように反転
    される、ことを特徴とする請求項５の方法。
  7. 【請求項７】 累積計量値が、次の数式 【数１】 に示す規則を用いて計算されることを特徴とする請求項
    ５の方法。
  8. 【請求項８】 前記絶対差が、ソフト記号出力ビタビア
    ルゴリズムによって計算されることを特徴とする請求項
    １の方法。
  9. 【請求項９】 第２の信号列における各記号についての
    信頼性基準を定めるために第１の信号列を処理する、信
    号処理方法において、 前記第２の信号列のＬ個の最良の推定値のセットが知ら
    れており、 前記Ｌ個の最良の推定値のうちの各要素ｔ（１≦ｔ≦
    Ｌ）が、各ステージにおいて複数の状態を有する複数の
    ステージを設けた１個の２進格子構造を通るｔ番目に最
    良のパスに対応し、 ｔ個（１≦ｔ≦Ｌ）の最良のパスの各々が、そのパスに
    付随する累積計量値を有する、 信号列を処理する、信号処理方法であって、 信頼性ベクトルのｉ番目の要素を、状態ｉで合流する２
    個のパスの累積計量値間の差に等しい第１の差の値で初
    期設定するステップと、 前記信頼性ベクトル中の要素を、指定された個数νの要
    素だけ左へ変位させ、その指定された個数の最も右側の
    要素を、１個の一定の高い値に入れ換えるステップと、 各パスｔ（１≦ｔ≦Ｌ）について、このパスの累積計量
    値と最良のパスの累積計量値との間の差に等しい第２の
    差の値を計算するステップと、 各パスについて、ｔ番目に最良のパスのビット列を最良
    のパスのビット列と比較し、パス間に差のあるような位
    置をマーク付けするステップと、 前記信頼性ベクトル中の、前記パス間に差のあるような
    位置に、前記第１の差の値と前記第２の差の値とのうち
    の小さい方の値を記憶するステップと、 からなる、 ことを特徴とする信号列を処理する、信号処理方法。
  10. 【請求項１０】 前記第１の信号列が、畳込み符号を用
    いて符号化され、 個数νが、前記畳込み符号のメモリに等しい、 ことを特徴とする請求項９の方法。
  11. 【請求項１１】 第２の信号列における各記号について
    の信頼性基準を定めるために第１の信号列を処理する、
    信号処理方法において、 前記第２の信号列のＬ個の最良の推定値のセットが知ら
    れており、 前記Ｌ個の最良の推定値のうちの各要素ｔ（１≦ｔ≦
    Ｌ）が、各ステージにおいて複数の状態を有する複数の
    ステージを設けた１個の格子構造を通るｔ番目に最良の
    パスに対応し、 ｔ個（１≦ｔ≦Ｌ）の最良のパスの各々が、そのパスに
    付随する累積計量値を有する、 信号列を処理する、信号処理方法であって、 前記方法が、 前記第２の信号列における記号の数に等しい長さを有す
    る信頼性ベクトルを、第１の定数で初期設定するステッ
    プと、 ｔ個（２≦ｔ≦Ｌ）の最良のパスについて第２の値を選
    択するステップと、 ｔ番目に最良のパスの記号列を（ｔ＝１）の最良のパス
    の記号列と比較し、それらの記号列間に差のあるような
    位置を定めるステップと、 （ｔ＝１）の最良のパスとｔ番目に最良のパスとの間に
    差のあるような位置に、前記差の値と前記信頼性ベクト
    ル中の前記位置における値とのうちの大きい方の値を記
    憶するステップと、 からなる、 ことを特徴とする信号列を処理する、信号処理方法。
  12. 【請求項１２】 前記第２の値が、前記ｔ番目（２≦ｔ
    ≦Ｌ）に最良のパスについての累積計量値と前記最良の
    パスについての累積計量値との間の差として選択される
    ことを特徴とする請求項１１の方法。
  13. 【請求項１３】 前記第１の定数が、１に等しく、 前記第２の値が更に、前記最良のパスの累積計量値によ
    って分割される、ことを特徴とする請求項１２の方法。
  14. 【請求項１４】 前記第２の値が、Ｌ番目に最良のパス
    の累積計量値に定数を加えた値に等しく選択され、その
    定数が正の実数であり且つ前記第１の信号列の信号対雑
    音比に依存する値である、ことを特徴とする請求項１１
    の方法。
  15. 【請求項１５】 符号化情報信号列を処理する、信号処
    理方法であって、 復号化情報記号のセットのうちの各復号化情報記号が信
    頼性値のセットのうちの対応する信頼性値を有するよう
    なＮ個の復号化情報記号のセットを生成するために前記
    情報信号列を復号化するステップと、 順位付けされた信頼性値のセットを形成するために前記
    信頼性値の大きさを、最小値から最大値へ向かって順位
    付けするステップと、 前記順位付けされた信頼性値のセットにおける前記信頼
    性値のうちの最初のｔ個（ｔ≦Ｎ）の信頼性値を、ｔ個
    のステージを有する単一状態の格子構造に、前記順位付
    けされた信頼性値のセットにおけるｉ番目の信頼性値が
    この単一状態格子構造のｉ番目のステージに割り当てら
    れるという規則（１≦ｉ≦ｔ）に基づいて、割り当てる
    ステップと、 復号化情報記号列に対するｔ個の最良の候補を定めるス
    テップと、 からなり、 前記ｔ個の最良の候補の各々が前記単一状態格子構造を
    通るパスに対応し、 前記単一状態格子構造を通るパスの各々がそのパスに付
    随する累積計量値を有し、 前記ｔ個の最良の候補が、それぞれｔ個の最良の累積計
    量値を有するパスである、 ことを特徴とする信号列を処理する、信号処理方法。
  16. 【請求項１６】 値の列からなる情報信号を処理する、
    信号処理方法であって、 最初のｔ個の最良の候補値列を表す信号に基づいて、前
    記情報信号を表す（ｔ＋１）番目に最良の候補値列を定
    めるステップと、 前記ｔ個の最良のパスのうちで最小計量値が最も小さい
    状態にある、前記ｔ個の最良のパスのうちの１個のパス
    と合流するパスを、（ｔ＋１）番目に最良の候補パスと
    して識別特定するステップと、 からなり、 前記定めるステップにおいて、 前記候補値列の各々が、各々複数の状態を有する複数の
    ステージを設けた１個の格子構造を通る１個のパスに対
    応し、 前記ステージの各々における前記状態の各々が、候補値
    列のうちの１個の値に対応し、 前記状態の各々が、それに付随する計量値を有し、 前記計量値が、前記値に対応する信頼性基準であり、 前記定めるステップが更に、 前記ｔ個の最良のパスの各々に沿って最小計量値を有す
    る状態を見出すステップからなる、 ことを特徴とする、値の列からなる情報信号を処理す
    る、信号処理方法。
  17. 【請求項１７】 （ｔ＝１）の最良の候補値列が、ソフ
    ト出力ビタビアルゴリズムによって生成されることを特
    徴とする請求項１６の方法。
  18. 【請求項１８】 前記（ｔ＋１）番目に最良のパスに沿
    った前記計量値が、前記（ｔ＋１）番目に最良のパスが
    前記最も小さい最小計量値を有する前記状態において合
    流した相手のパスの計量値で初期設定される、 ことを特徴とする請求項１６の方法。
  19. 【請求項１９】 前記最も小さい最小計量値を高い値
    に置き換えるステップをさらに有することを特徴とする
    請求項１６の方法。
  20. 【請求項２０】 情報信号に含まれる要素列中の各要素
    について信頼性値を定める、信号処理方法であって、 前記要素列を表すＬ個の最良の候補要素列からなる要素
    列セットを表す信号を受信するステップと、 前記Ｌ個の最良の候補要素列からなる要素列セットのう
    ちの各候補要素列についての、その候補要素列と前記Ｌ
    個の最良の候補要素列のうちの各候補要素列との間の相
    対的類似性を表示する計量値、を表す信号を受信するス
    テップと、 信頼性ベクトルを初期値で初期設定するステップと、 最良のパスとｔ番目（ｔ＞１）に最良のパスとの互いに
    対応する要素間に差のあるような位置に、前記信頼性ベ
    クトル中の前記初期値と差の値とのうちの大きい方の値
    を記憶するステップと、 からなる、 ことを特徴とする、情報信号に含まれる要素列中の各要
    素について信頼性値を定める、信号処理方法。
  21. 【請求項２１】 前記Ｌ個の最良の候補要素列からなる
    要素列セットを表す前記信号が、汎用ビタビアルゴリズ
    ムによって生成されることを特徴とする請求項２０の方
    法。
  22. 【請求項２２】 前記差の値が、前記ｔ番目（ｔ＞１）
    に最良のパスの計量値と前記最良のパスの計量値との関
    数であることを特徴とする請求項２０の方法。
  23. 【請求項２３】 前記初期値がソフト初期設定値である
    ことを特徴とする請求項２０の方法。
  24. 【請求項２４】 値の列からなる情報信号を処理する、
    信号処理方法であって、 １個の最良の候補値列とこの最良の候補値列内の個々の
    ビットについての信頼性値とを含む信号に基づいて、前
    記情報信号を表すＬ個（＞１）の最良の候補値列のセッ
    トを定めるステップを有し、この決定ステップは、 更に、順位付けされた信頼性値のセットを形成するため
    に前記信頼性値の大きさを、最小値から最大値へ向かっ
    て順位付けするステップと、 前記情報信号を表すＬ個（＞１）の最良の候補値列のセ
    ット、を定めるステップと、 前記順位付けされた信頼性値のセットにおける要素を、
    １個の単一状態の格子構造における互いに連続するステ
    ージについての計量値として割り当てるステップと、 前記単一状態の格子構造を通る、前後に連続するＬ個
    （＞１）の最良のパスのセットを見出すステップと か
    らなり、 前記パスの各々が、前記値列についての１個の候補値列
    に対応し、 前記最良のパスの品質が、前記計量値の和であり、 前記前後に連続する最良のパスの各々の、相対的品質
    が、前記最良のパスの前記和から、前記ｔ個（＞１）の
    最良のパスの各々と前記最良のパスとの間に差のあるよ
    うなステージ、に対応する計量値を差し引くことによっ
    て計測される、 ことを特徴とする、値の列からなる情報信号を処理す
    る、信号処理方法。
  25. 【請求項２５】 前記情報信号が、ソフト出力ビタビア
    ルゴリズムによって生成されることを特徴とする請求項
    ２４の方法。
JP6014924A 1993-01-14 1994-01-14 信号処理方法 Pending JPH0795099A (ja)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US004360 1993-01-14
US08/004,360 US5537444A (en) 1993-01-14 1993-01-14 Extended list output and soft symbol output viterbi algorithms

Publications (1)

Publication Number Publication Date
JPH0795099A true JPH0795099A (ja) 1995-04-07

Family

ID=21710403

Family Applications (1)

Application Number Title Priority Date Filing Date
JP6014924A Pending JPH0795099A (ja) 1993-01-14 1994-01-14 信号処理方法

Country Status (7)

Country Link
US (1) US5537444A (ja)
EP (1) EP0606724A1 (ja)
JP (1) JPH0795099A (ja)
KR (1) KR940019106A (ja)
CA (1) CA2110244C (ja)
FI (1) FI940175L (ja)
NO (1) NO940081L (ja)

Cited By (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6556632B1 (en) 1997-07-23 2003-04-29 Mitsubishi Denki Kabushiki Kaisha Sequence estimation method and sequence estimator
KR100580160B1 (ko) * 1999-09-14 2006-05-15 삼성전자주식회사 변형된 역추적 방식의 2단 연출력 비터비 알고리즘 복호화기
JP2015039156A (ja) * 2013-08-19 2015-02-26 富士通株式会社 復号化装置、及び、復号化方法

Families Citing this family (72)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
DE4431237A1 (de) * 1994-09-02 1996-03-07 Bosch Gmbh Robert Verfahren zur Gewinnung von bitspezifischen Zuverlässigkeitsinformationen
JP3498964B2 (ja) * 1994-10-31 2004-02-23 コーニンクレッカ フィリップス エレクトロニクス エヌ ヴィ 簡単な誤り補正付きのディジタル伝送兼記録システム
FI950843L (fi) * 1995-02-23 1996-08-24 Nokia Telecommunications Oy Menetelmä yhteyden laadun määrittämiseksi sekä vastaanotin
US5684811A (en) * 1995-09-01 1997-11-04 Motorola, Inc. Method and apparatus for decoding convolutionally encoded information
US6028899A (en) * 1995-10-24 2000-02-22 U.S. Philips Corporation Soft-output decoding transmission system with reduced memory requirement
DE69601343T2 (de) * 1995-10-25 1999-07-15 Nec Corp., Tokio/Tokyo Maximalwahrscheinlichkeitsdekodierung mit weichen Entscheidungen
US5889823A (en) * 1995-12-13 1999-03-30 Lucent Technologies Inc. Method and apparatus for compensation of linear or nonlinear intersymbol interference and noise correlation in magnetic recording channels
US5802116A (en) * 1996-04-04 1998-09-01 Lucent Technologies Inc. Soft decision Viterbi decoding with large constraint lengths
US5822340A (en) * 1996-05-10 1998-10-13 Telefonaktiebolaget Lm Ericsson Method for decoding data signals using fixed-length decision window
DE69717412T2 (de) * 1996-09-17 2003-07-17 Koninklijke Philips Electronics N.V., Eindhoven Übertragungssystem mit verbesserter verriegelungserkennung
US5809043A (en) * 1996-10-08 1998-09-15 Ericsson Inc. Method and apparatus for decoding block codes
JP3310185B2 (ja) * 1996-11-21 2002-07-29 松下電器産業株式会社 誤り訂正装置
US5881093A (en) * 1997-02-10 1999-03-09 Motorola, Inc. Method of interleaving a convolutionally coded signal in a spread spectrum communication system
FI102230B (fi) * 1997-02-28 1998-10-30 Nokia Telecommunications Oy Vastaanottomenetelmä ja vastaanotin
US5930272A (en) * 1997-06-10 1999-07-27 Efficient Channel Coding, Inc. Block decoding with soft output information
US6081562A (en) * 1997-10-22 2000-06-27 Hitachi Ltd. Implementing reduced-state viterbi detectors
JP3567067B2 (ja) * 1997-11-04 2004-09-15 株式会社日立グローバルストレージテクノロジーズ ディジタル磁気記録再生装置
US6029267A (en) * 1997-11-25 2000-02-22 Lucent Technologies Inc. Single-cycle, soft decision, compare-select operation using dual-add processor
US6105158A (en) * 1998-04-03 2000-08-15 Lucent Technologies, Inc. Screening for undetected errors in data transmission systems
US6108386A (en) * 1998-04-03 2000-08-22 Lucent Technologies Inc. List Viterbi algorithms for continuous data transmission
US6272660B1 (en) 1998-04-03 2001-08-07 Agere Systems Guardian Corp. Screening for errors in data transmission systems
US6161210A (en) * 1998-04-03 2000-12-12 Lucent Technologies Inc. List Viterbi algorithms for tailbiting convolutional codes
US6334202B1 (en) * 1998-07-22 2001-12-25 Telefonaktiebolaget Lm Ericsson (Publ) Fast metric calculation for Viterbi decoder implementation
US6381728B1 (en) * 1998-08-14 2002-04-30 Qualcomm Incorporated Partitioned interleaver memory for map decoder
US6643338B1 (en) * 1998-10-07 2003-11-04 Texas Instruments Incorporated Space time block coded transmit antenna diversity for WCDMA
US6418549B1 (en) * 1998-10-30 2002-07-09 Merunetworks, Inc. Data transmission using arithmetic coding based continuous error detection
FI106416B (fi) * 1999-02-09 2001-01-31 Nokia Mobile Phones Ltd Menetelmä ja laite dekoodatun symbolisarjan luotettavuuden määrittämiseksi
FI106493B (fi) 1999-02-09 2001-02-15 Nokia Mobile Phones Ltd Menetelmä ja järjestelmä pakettimuotoisen datan luotettavaksi siirtämiseksi
US6499128B1 (en) 1999-02-18 2002-12-24 Cisco Technology, Inc. Iterated soft-decision decoding of block codes
US7031406B1 (en) 1999-08-09 2006-04-18 Nortel Networks Limited Information processing using a soft output Viterbi algorithm
US6405342B1 (en) 1999-09-10 2002-06-11 Western Digital Technologies, Inc. Disk drive employing a multiple-input sequence detector responsive to reliability metrics to improve a retry operation
EP1085661B1 (en) * 1999-09-14 2005-03-02 Lucent Technologies Inc. Channel decoder and method of channel decoding
US6400290B1 (en) 1999-11-29 2002-06-04 Altera Corporation Normalization implementation for a logmap decoder
JP2001251200A (ja) * 2000-03-03 2001-09-14 Nec Corp 符号化方法
US6888897B1 (en) 2000-04-27 2005-05-03 Marvell International Ltd. Multi-mode iterative detector
US7184486B1 (en) 2000-04-27 2007-02-27 Marvell International Ltd. LDPC encoder and decoder and method thereof
US6594393B1 (en) * 2000-05-12 2003-07-15 Thomas P. Minka Dynamic programming operation with skip mode for text line image decoding
US7000177B1 (en) 2000-06-28 2006-02-14 Marvell International Ltd. Parity check matrix and method of forming thereof
US7072417B1 (en) 2000-06-28 2006-07-04 Marvell International Ltd. LDPC encoder and method thereof
US6965652B1 (en) 2000-06-28 2005-11-15 Marvell International Ltd. Address generator for LDPC encoder and decoder and method thereof
US20020034269A1 (en) * 2000-07-28 2002-03-21 Victor Demjanenko Use of soft-decision or sum-product inner coders to improve the performance of outer coders
US7117418B2 (en) 2000-09-11 2006-10-03 Comtech Aha Corporation Soft input-soft output forward error correction decoding for turbo codes
US7099411B1 (en) 2000-10-12 2006-08-29 Marvell International Ltd. Soft-output decoding method and apparatus for controlled intersymbol interference channels
US7020185B1 (en) 2000-11-28 2006-03-28 Lucent Technologies Inc. Method and apparatus for determining channel conditions in a communication system
US6865711B2 (en) * 2000-12-15 2005-03-08 Conexant Systems, Inc. System of and method for decoding trellis codes
US6973615B1 (en) 2000-12-15 2005-12-06 Conexant Systems, Inc. System of and method for decoding trellis codes
EP1410513A4 (en) 2000-12-29 2005-06-29 Infineon Technologies Ag CHANNEL CODEC PROCESSOR CONFIGURABLE FOR MULTIPLE WIRELESS COMMUNICATION STANDARDS
US6708308B2 (en) 2001-01-10 2004-03-16 International Business Machines Corporation Soft output viterbi algorithm (SOVA) with error filters
US6823027B2 (en) 2001-03-05 2004-11-23 Telefonaktiebolaget Lm Ericsson (Publ) Method for enhancing soft-value information
US6691263B2 (en) * 2001-05-03 2004-02-10 Agere Systems Inc. Interative decoding based on dominant error events
EP1425859A4 (en) * 2001-08-09 2009-01-07 Adaptive Networks Inc ERROR CORRECTION METHOD AND MECHANISM
JP2005510113A (ja) * 2001-11-13 2005-04-14 コーニンクレッカ　フィリップス　エレクトロニクス　エヌ　ヴィ 可変長コードワード・シーケンスの復号方法
JP2003152553A (ja) * 2001-11-13 2003-05-23 Ntt Docomo Inc 復号方法及び通信装置
KR101143695B1 (ko) * 2002-10-30 2012-05-09 에스티 에릭슨 에스에이 트렐리스-기반 수신기와 이를 위한 프로세서 시스템, 방법 및 컴퓨터 판독가능 매체
US7346833B2 (en) * 2002-11-05 2008-03-18 Analog Devices, Inc. Reduced complexity turbo decoding scheme
US7103831B1 (en) 2003-01-22 2006-09-05 Conexant Systems, Inc. Burst reliability and error locator for trellis codes
US7577892B1 (en) 2005-08-25 2009-08-18 Marvell International Ltd High speed iterative decoder
US7861131B1 (en) 2005-09-01 2010-12-28 Marvell International Ltd. Tensor product codes containing an iterative code
US20080123210A1 (en) * 2006-11-06 2008-05-29 Wei Zeng Handling synchronization errors potentially experienced by a storage device
WO2008071189A2 (en) * 2006-12-12 2008-06-19 Vestas Wind Systems A/S A multiprotocol wind turbine system and method
ES2281309B2 (es) * 2007-04-19 2008-03-01 Universidad Politecnica De Madrid Procedimiento y arquitectura electronica para la deteccion sova optimabasado en el rastreo de puntos de fusion.
US20090016469A1 (en) * 2007-07-11 2009-01-15 The Hong Kong University Of Science And Technology Robust joint erasure marking and list viterbi algorithm decoder
US7752531B2 (en) * 2007-09-12 2010-07-06 Seagate Technology Llc Defect sensing Viterbi based detector
US20090132894A1 (en) * 2007-11-19 2009-05-21 Seagate Technology Llc Soft Output Bit Threshold Error Correction
US8127216B2 (en) * 2007-11-19 2012-02-28 Seagate Technology Llc Reduced state soft output processing
US8321769B1 (en) 2008-11-06 2012-11-27 Marvell International Ltd. Multi-parity tensor-product code for data channel
EP2302811B1 (en) * 2009-08-18 2013-03-27 Telefonaktiebolaget L M Ericsson (Publ) Soft output viterbi algorithm method and decoder
US9312986B2 (en) * 2009-09-17 2016-04-12 Orange Method of transmitting a digital signal for a marc system with a full-duplex relay, a corresponding program product and relay device
US9362933B1 (en) 2011-07-12 2016-06-07 Marvell International Ltd. Noise-predictive detector adaptation with corrected data
US9286894B1 (en) * 2012-01-31 2016-03-15 Google Inc. Parallel recognition
KR102375951B1 (ko) 2015-07-29 2022-03-17 삼성전자주식회사 오류 감소를 위한 디코딩 장치 및 방법
WO2019234903A1 (ja) 2018-06-08 2019-12-12 日本電気株式会社 復号装置、復号方法、及び非一時的なコンピュータ可読媒体

Family Cites Families (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4660214A (en) * 1985-08-01 1987-04-21 Infinet, Inc. QANI Trellis-coded signal structure
DE3910739C3 (de) * 1989-04-03 1996-11-21 Deutsche Forsch Luft Raumfahrt Verfahren zum Verallgemeinern des Viterbi-Algorithmus und Einrichtungen zur Durchführung des Verfahrens
US5208816A (en) * 1989-08-18 1993-05-04 At&T Bell Laboratories Generalized viterbi decoding algorithms
CA2020899C (en) * 1989-08-18 1995-09-05 Nambirajan Seshadri Generalized viterbi decoding algorithms
US5263033A (en) * 1990-06-22 1993-11-16 At&T Bell Laboratories Joint data and channel estimation using fast blind trellis search

Cited By (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6556632B1 (en) 1997-07-23 2003-04-29 Mitsubishi Denki Kabushiki Kaisha Sequence estimation method and sequence estimator
US6996196B2 (en) 1997-07-23 2006-02-07 Mitsubishi Denki Kabushiki Kaisha Sequence estimation method and sequence estimator
KR100580160B1 (ko) * 1999-09-14 2006-05-15 삼성전자주식회사 변형된 역추적 방식의 2단 연출력 비터비 알고리즘 복호화기
JP2015039156A (ja) * 2013-08-19 2015-02-26 富士通株式会社 復号化装置、及び、復号化方法

Also Published As

Publication number Publication date
EP0606724A1 (en) 1994-07-20
KR940019106A (ko) 1994-08-19
CA2110244C (en) 1998-09-22
FI940175A7 (fi) 1994-07-15
FI940175A0 (fi) 1994-01-13
US5537444A (en) 1996-07-16
FI940175L (fi) 1994-07-15
NO940081D0 (no) 1994-01-10
NO940081L (no) 1994-07-15
CA2110244A1 (en) 1994-07-15

Similar Documents

Publication Publication Date Title
US5537444A (en) Extended list output and soft symbol output viterbi algorithms
JP3652701B2 (ja) デコーダ最適化方法及び装置
US4583078A (en) Serial Viterbi decoder
JP2595372B2 (ja) 広汎性ビテルビ復号化アルゴリズム
KR101143695B1 (ko) 트렐리스-기반 수신기와 이를 위한 프로세서 시스템, 방법 및 컴퓨터 판독가능 매체
US5802116A (en) Soft decision Viterbi decoding with large constraint lengths
JP3549519B2 (ja) 軟出力復号器
KR20010023315A (ko) 연결 코드에서 순환 중복 검사를 선택하는 장치 및 방법
US6374387B1 (en) Viterbi decoding of punctured convolutional codes without real-time branch metric computation
KR100779782B1 (ko) 비터비 디코더 용 고속 ａｃｓ 유닛
JP2000244336A (ja) 復号されたシンボル・シーケンスの信頼度を推定するための方法および装置
CN1100393C (zh) 采用固定长度的判定窗口对数据信号进行译码的方法
JP2000209106A (ja) 高速ビタビ復号器の最小量のメモリによる実現
JP3233847B2 (ja) ビタビ復号方法及びビタビ復号回路
CN110995279B (zh) 一种极化码联合scf球形列表翻转译码方法
KR20020006022A (ko) 중첩 코드를 디코딩하기 위한 방법 및 장치
JPH06284018A (ja) ビタビ復号方法および誤り訂正復号化装置
JP2917177B2 (ja) 誤り検出方法、装置ならびに識別方法
JP3497399B2 (ja) ビタビ復号器
Ahmed et al. Viterbi algorithm performance analysis for different constraint length
JP2859535B2 (ja) 最適な復号経路を有する復号方法及びその装置
JP3337950B2 (ja) 誤り訂正復号化方法及び誤り訂正復号化装置
JP3425625B2 (ja) 冗長パリティ検査を用いたブロック符号化変調方法
WO2001069796A1 (en) Viterbi decoder
JP3235333B2 (ja) ビタビ復号方法およびビタビ復号化装置