JPH05211447A - ビタビ復号装置およびその方法 - Google Patents

Abstract

(57)【要約】 【目的】例えば、ＨＤＴＶ放送等において使用される３
０Ｍｂｐｓ以上の情報量を持つたたみ込み符号を復号す
ることができるビタビ復号装置を提供することを目的と
している。 【構成】 本発明のビタビ復号装置は、スワップ・イン
バータ回路１と、パンクチャド処理回路２と、ブランチ
メトリック計算回路３と、ＡＣＳ・ＳＭ正規化回路４
と、正規化指令回路５と、ステートメトリック記憶回路
６と、パスメモリ回路７と、多数決復号決定回路８と、
送信復号回路９と、同期判定制御回路１０とを備え、２
タイムスロットごとに各状態節点に合流するパスに対し
て、受信符号との距離が最小になるパスを選択する演算
を行い、各パスの選択処理時間を２タイムスロットに１
回の割合にし、これによって２タイムスロット分の処理
時間を従来の約半分とする。これとともに、入力される
データについて送信側のエンコータから生成され得る符
号系列のなかから受信された符号系列に最も近い系列を
選んで、この選択内容に基づいて復号データを生成す
る。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は衛星放送等で使用される
ビタビ復号装置およびその方法に関する。

【０００２】

【従来の技術】たたみ込み符号化とは、過去の情報系列
をある数のビットごとに区切ったタイムスロットの情報
を現在のブロックに影響を及ぼさせながら符号化を行う
方法であり、短いタイムスロット長でも高い誤り訂正能
力を持つため、通信等の分野で広く用いられている。こ
のたたみ込み符号を復号する方式の１つとして、ビタビ
復号方式が知られている。このビタビ復号方式はたたみ
込み符号に対する最尤復号方式であり、送信側のエンコ
ーダから生成され得る符号系列のなかから、受信された
符号系列に最も近い系列（これを最尤パスという）を選
ぶことで誤り訂正を行う。

【０００３】この最尤パスの選択方法は全てのパスを比
較して確かめるのではなく、送信側で生成され得る全て
の符号列と受信符号列とのハミング距離を求め、最も小
さいもの（すなわち、尤度が最も高いもの）を選んで、
それ以後は復号に必要なパス（生き残りパス）だけを調
べていくことを基本にしており、パスの長さを十分に長
くとると、生き残りパスの先（根元）は合流して同じ値
になり、どの生き残りパスであっても、遡れば、同じ値
を復号していることになる。したがって、復号誤り率が
高くならない程度のパス長を調べ、その長さ分だけ遡っ
た時点のデータを復号データとすることができる。

【０００４】図５はこのようなビタビ復号方法を用いた
ビタビ復号装置の一例を示すブロック図である。この図
に示すビタビ復号装置はブランチメトリック計算回路１
０１と、ＡＣＳ（Ａｄｄ Ｃｏｍｐａｒｅ Ｓｅｌｅｃ
ｔ）回路１０２と、正規化回路１０３と、ステートメト
リック記憶回路１０４と、パスメモリ回路１０５と、最
尤復号判定回路１０６とを備えており、送信側から出力
されたデータ（入力データ）が入力されたとき、送信側
のエンコーダから生成され得る符号系列のなかから、受
信された符号系列に最も近い系列を選んで、この選択内
容に基づいて復号データを生成する。

【０００５】ブランチメトリック計算回路１０１は入力
データが入力されたとき、この入力データのブランチメ
トリック（受信符号とパスとのハミング距離）を計算し
てこの計算結果（ブランチメトリック）をＡＣＳ回路１
０２に供給する。

【０００６】ＡＣＳ回路１０２は、前記ブランチメトリ
ック計算回路１０１から供給されるブランチメトリック
と、前記ステートメトリック記憶回路１０４から供給さ
れるステートメトリック（累積和）とに基づいて、ある
状態に合流する２本のそれぞれのパスに対し、このパス
のブランチメトリックと、それまでのブランチメトリッ
クの累積和（ステートメトリック）を加算する。

【０００７】さらに、ＡＣＳ回路１０２はこれらの各加
算結果を比較し、この比較結果に基づいて尤度の高いも
のを選択して、この選択内容をパスメモリ回路１０５に
供給するとともに、尤度が高い方の加算結果を新たに得
られた累積和（ステートメトリック）として正規化回路
１０３に供給する。

【０００８】この場合、拘束長が（７）で状態数（６
４）のとき、各タイムスロットごとに図６の遷移ダイア
グラムに示すように、ある状態に合流する２本のそれぞ
れのパスに対し、受信符号とパスとのハミング距離（ブ
ランチメトリック）と、それまでのブランチメトリック
の累積和（ステートメトリック）が加算されるととも
に、これらの各加算結果が比較され、この比較結果に基
づいて尤度の高いものが選択される。

【０００９】ここで、拘束長とは、あるタイムスロット
の情報が影響を及ぼす、そのタイムスロットの後のタイ
ムスロット数をさす。

【００１０】正規化回路１０３は、前記ＡＣＳ回路１０
２から出力されるステートメトリックを正規化して予め
設定されている範囲内の値にし、これをステートメトリ
ック記憶回路１０４に供給する。

【００１１】ステートメトリック記憶回路１０４は前記
正規化回路１０３から供給される正規化されたステート
メトリックを記憶するとともに、記憶している各ステー
トメトリックを前記ＡＣＳ回路１０２に帰還する。

【００１２】また、パスメモリ回路１０５は前記ＡＣＳ
回路１０２から出力される選択内容を記憶してこの選択
内容を最尤復号判定回路１０６に供給する。

【００１３】最尤復号判定回路１０６は前記パスメモリ
回路１０５に記憶されている選択内容に基づいて最尤の
パスを判定して復号データを生成し、これを出力する。

【００１４】

【発明が解決しようとする課題】ところで、従来技術と
して示したようなビタビ復号装置においては、前復号過
程のステートメトリックの値を現復号過程で加算するた
めに、ステートメトリック記憶回路１０４からＡＣＳ回
路１０２内に設けられた加算器（図示は省略する）まで
がループ状につながっている。そして、ループ内の演算
は情報速度内で行われる必要があるため、情報速度を上
げるために、ループ部分で要する時間の上限を小さくす
ることが必要である。

【００１５】この場合、このループの中でも、動作速度
に最も大きい影響力を持つのが、ある状態に合流する２
本のそれぞれのパスに対し、受信符号とパスとのハミン
グ距離（ブランチメトリック）と、それまでのブランチ
メトリックの累積和（ステートメトリック）を加算して
比較し、尤度の高いものを選択するＡＣＳ回路１０２で
ある。

【００１６】しかしながら、このようなビタビ復号装置
で用いられる従来のＡＣＳ回路１０２は、図７に示す如
く１タイムスロットごとにパスの遷移情報に当たるパス
選択信号Ｓ_(t) 、Ｓ_(t+1) 、・・・を出力するとき、演
算時間として次式に示す時間Ｔ_T を必要とする。

【数１】

【００１７】また、このとき、情報速度が上がることに
よってクロックの同期の正確さが厳しく要求される。こ
のため、従来の回路構成のままで情報速度を上げれば、
回路動作上、遷移時刻がずれるなどの問題が起こり易
く、またクロックの制御も困難になってしまうという問
題が生じる。

【００１８】また、上記ループの中ではＡＣＳ回路１０
２と同様に、このＡＣＳ回路１０２から出力されるステ
ートメトリックを正規化する正規化回路１０３の動作速
度も最も大きい影響力を持つ。

【００１９】この正規化回路１０３では、正規化判定処
理や正規化タイミング処理、正規化処理等の各種処理を
行わなければならないので、正規化のためのある程度の
処理時間を必要とする。

【００２０】したがって、この処理時間を短くしなけれ
ば、ループ部分の速度を短縮することができなくなっ
て、情報速度を上げることができなくなってしまう。

【００２１】また、従来のビタビ復号装置、特に拘束長
の長いパンクチャド符号を扱うビタビ復号装置のように
回路規模が大きいものでは、ステートメトリックのビッ
ト数をなるべく少なくして回路規模を小さくすることが
必要である。

【００２２】しかしながら、このようなビタビ復号装置
では、ＡＣＳ回路１０２によって選択されたステートメ
トリックの値が生き残りパスのブランチメトリックの総
和であるから、時間とともに常に増大するため、ＡＣＳ
回路１０２の後に設けられた正規化回路１０３によって
ＡＣＳ回路１０２によって選択されたステートメトリッ
クの値を予め設定されている条件で正規化するようにし
ている。

【００２３】このとき、正規化の方法として、もっとも
良いのは、全てのステートメトリックからその最小値を
引いてやることであるが、このような方法でＡＣＳ回路
１０２から出力されるステートメトリックの値を正規化
すると、ループ全体の処理速度が低下してしまう。

【００２４】したがって、従来の構成では、動作速度の
上限は１タイムスロットにおけるループの演算速度によ
って決定されてしまい、拘束長（７）で符号化率（７／
８）であるとすると、現在の技術レベルでは、２５Ｍｂ
ｐｓが限界になってしまう。このため、ＨＤＴＶ放送等
において使用されるたたみ込み符号を復号するときのよ
うに、３０Ｍｂｐｓ以上の情報量を処理することができ
ないという問題があった。

【００２５】本発明は以上に述べた従来技術の問題点に
鑑みてなされたものであり、例えば、ＨＤＴＶ放送等に
おいて使用される３０Ｍｂｐｓ以上の情報量を持つたた
み込み符号を復号することができるビタビ復号装置を提
供することを目的としている。

【００２６】

【課題を解決するための手段】上記目的を達成するため
に、本発明のビタビ復号装置およびその方法は、複数の
タイムスロットのデータについて、複数のパスとのブラ
ンチメトリックをそれぞれ算出するブランチメトリック
算出手段と、前記複数のタイムスロットごとに、前記複
数のタイムスロット分のブランチメトリックとこれらの
ブランチメトリックに対応するステートメトリックとを
加算し、この加算結果を相互に比較し、この比較結果に
基づいて最も尤度の高いパスを求める処理を一括して行
う加算・比較・選択手段と、前記複数のタイムスロット
ごとに前記加算・比較・選択手段によって得られたパス
内容に基づいて入力データを復号する最尤復号判定手段
とを有する。

【００２７】また、複数のタイムスロットのデータにつ
いて、複数のパスとのブランチメトリックをそれぞれ算
出するブランチメトリック算出手段と、ステートメトリ
ックを算出し、記憶するステートメトリック算出記憶手
段と、前記複数のタイムスロットごとに、前記複数のタ
イムスロット分のブランチメトリックとこれらのブラン
チメトリックに対応するステートメトリックとを加算
し、この加算結果を相互に比較し、この比較結果に基づ
いて最も尤度の高いパスを求める処理を一括して行う加
算・比較・選択手段と、前記複数のタイムスロットごと
に前記加算・比較・選択手段によって得られたパス内容
に基づいて入力データを復号する最尤復号判定手段とを
有する。

【００２８】また、前記加算・比較・選択手段は、前記
複数のタイムスロットごとに、前記複数のパスのそれぞ
れとの現処理段階における前記複数タイムスロット分の
ブランチメトリックと、前記ステートメトリック算出記
憶手段に記憶されている前処理段階までのこれらのブラ
ンチメトリックに対応するステートメトリックとをそれ
ぞれ加算する複数の加算手段と、これら複数の加算手段
の加算結果を相互に比較する複数の比較手段と、これら
複数の比較手段の比較結果から、最も尤度の高いパスを
選択する選択手段とから構成されることを特徴とする。

【００２９】また、２タイムスロットのデータについ
て、複数のパスとのブランチメトリックをそれぞれ算出
するブランチメトリック算出手段と、ステートメトリッ
クを算出し、記憶するステートメトリック算出記憶手段
と、前記２タイムスロットごとに、一つの状態節点合流
する４本のパスのそれぞれとの、現処理段階における前
記２タイムスロット分のブランチメトリックとこれらの
ブランチメトリックに対応するステートメトリックとを
加算し、この加算結果を相互に比較し、この比較結果に
基づいて最も尤度の高いパスを求める処理を一括して行
う加算・比較・選択手段と、前記２タイムスロットごと
に前記加算・比較・選択手段によって得られたパス内容
に基づいて入力データを復号する最尤復号判定手段とを
有する。

【００３０】また、前記加算・比較・選択手段は、２タ
イムスロットごとに、一つの状態節点合流する４本のパ
スのそれぞれとの現処理段階における前記２タイムスロ
ット分のブランチメトリックと、前記ステートメトリッ
ク算出記憶手段に記憶される前処理段階までのこれらの
ブランチメトリックに対応するステートメトリックとを
それぞれ加算する４個の加算手段と、これら４個の加算
手段の加算結果を相互に比較する６個の比較手段と、こ
れら６個の比較手段の比較結果から、最も尤度の高いパ
スを選択する選択手段とから構成されることを特徴とす
る。

【００３１】また、ブランチメトリックを算出するブラ
ンチメトリック算出手段と、ステートメトリックを算出
し、記憶するステートメトリック算出記憶手段と、現処
理段階におけるブランチメトリックと、前記ステートメ
トリック算出記憶手段に記憶されている前処理段階まで
のこれらのブランチメトリックに対応するステートメト
リックとに基づいて、次のステートメトリックを算出す
るステートメトリック算出手段と、前記次のステートメ
トリックを記憶するワードの内、少なくともいずれかの
ＭＳＢがアサートされた時点から前記ステートメトリッ
クを記憶するワードがオーバーフローする寸前までの最
大時間間隔を予測計算して正規化タイミングを決定し、
この決定に基づいて正規化指令信号を出力する正規化指
令手段と、前記正規化指令手段から正規化指令信号がア
サートされている期間においては、前記演算手段によっ
て得られた前記次のステートメトリックをＬＳＢ側にシ
フトし、正規化し、このステートメトリックを新たなス
テートメトリックとして前記ステートメトリック算出記
憶手段に記憶させ、前記正規化指令手段からの正規化指
令信号がネゲートされている期間においては、前記次の
ステートメトリックについて前記正規化せずに、これを
新たなステートメトリックとして前記ステートメトリッ
ク算出記憶手段に記憶させる選択・正規化手段と、前記
新たなステートメトリックに基づいて入力データを復号
する最尤復号判定手段とを有することを特徴とする。

【００３２】また、入力されるデータについてスワップ
・インバータ処理を行うスワップ・インバータ手段をさ
らに有することを特徴とする。

【００３３】また、複数のタイムスロットのデータにつ
いて、複数のパスとのブランチメトリックをそれぞれ算
出し、前記複数のタイムスロットごとに、前記複数のタ
イムスロット分のブランチメトリックとこれらのブラン
チメトリックに対応するステートメトリックとを加算
し、この加算結果を相互に比較し、この比較結果に基づ
いて最も尤度の高いパスを求める処理を一括して行い、
前記処理によって得られたパス内容に基づいて入力デー
タを復号する。

【００３４】

【作用】上記の構成において、ブランチメトリック算出
手段によって複数タイムスロット分のブランチメトリッ
クが一括して計算される。これとともに、複数タイムス
ロットごとに、加算・比較・選択（ＡＣＳ演算）手段に
よって前記ブランチメトリック計算回路で得られた複数
タイムスロット分のブランチメトリックとそれまでのス
テートメトリックとに基づいてＡＣＳ演算が行なわれ、
最尤復号判定回路によって前記ＡＣＳ演算で得られたパ
ス内容から入力データが復号される。

【００３５】また、上記の構成において、前記ステート
メトリック算出手段によって前記入力データに対するブ
ランチメトリックとそれまでのステートメトリックとに
基づいて新たなステートメトリックが演算される。これ
とともに、この前記ステートメトリック算出手段によっ
て得られた各ステートメトリックのうち、これを記憶す
るワードの少なくともいずれかのＭＳＢが論理値１であ
る（アサートされている）とき、前記正規化指令手段に
よってこれが検出されて前記各ステートメトリックを記
憶するワードがオーバーフローしない時間の長さが予測
計算されて正規化タイミングが決定され、この決定に基
づいて正規化指令信号が出力される。

【００３６】また、この動作と並行して、選択・正規化
手段によって前記ステートメトリック算出手段によって
得られた次のステートメトリックがＬＳＢ側にシフトさ
れて正規化された済みの次のステートメトリックと正規
化前の次のステートメトリックとが生成される。これと
とともに、前記正規化指令手段からの正規化指令信号が
出力されている（アサートされている）ときには、正規
化済みの次のステートメトリックが選択され、これが新
たなステートメトリックとしてステートメトリック算出
記憶手段に記憶される。また、前記正規化指令回路から
の正規化指令が出力されていない（ネゲートされてい
る）ときには、正規化前の次のステートメトリックが選
択されこれが新たなステートメトリックとして前記ステ
ートメトリック算出記憶手段に記憶されながら、最尤復
号判定回路によって前記演算回路のステートメトリック
演算処理で得られるパス内容から入力データが復号され
る。

【００３７】

【実施例】以下、第一の実施例について説明する。ま
ず、第一の実施例の詳細な説明に先立って、図８を参照
しながら本発明のビタビ復号装置およびその方法の基本
原理を説明する。今、入力データの拘束長が（７）で状
態数が（６４）であると仮定する。従来の方法において
は、図６に示すように各タイムスロットごとに各状態節
点に合流するパスに対して、受信符号との距離が最小に
なるパスを選択する演算を行なう。

【００３８】一方、本発明のビタビ復号装置およびその
方法では図８に示すように、２タイムスロットごとに各
状態節点に合流するパスに対して、受信符号との距離が
最小になるパスを選択する演算を行なうようにする。こ
のようにして、従来の方法においては各タイムスロット
ごとに必要だったステートメトリック（パスメトリッ
ク）とブランチメトリックとの加算処理時間、各加算結
果の比較処理時間、各パスの選択処理時間を２タイムス
ロットに１回の割合にし、これによって２タイムスロッ
ト分の処理時間を次式の値にする。

【数２】

【００３９】図８に示す本発明のビタビ復号装置および
その方法の方法によっても、状態は４状態から４状態の
遷移にかわりなく、また、図６における中央の状態がな
くなっても、必要となる情報は選ばれたパスの復号語
と、その遷移情報だけである。よって、２タイムスロッ
トおきにＡＣＳ（加算・比較・選択）計算を行なっても
パスメモリ回路の復号語を２ビット単位で２タイムスロ
ット用の遷移図にしたがって遷移させれば、従来の１タ
イムスロットごとの計算と全く同じ結果を得ることがで
きる。

【００４０】そして、（式２）で示される加算時間
Ｔ_A2' 、比較時間Ｔ_C2' 、選択時間Ｔ_S2' は次式に示す
従来の方式において各タイムスロットごとに必要な加算
時間Ｔ_A、比較時間Ｔ_C 、選択時間Ｔ_S とそれぞれ、ほ
ぼ同じ値になる。

【数３】

【００４１】従来の方法では、図７に示すように２タイ
ムスロット分の処理を行なうのに（２Ｔ_T ）時間必要な
のに対して本発明のビタビ復号装置およびその方法で
は、図９に示すように従来のほぼ半分の時間（Ｔ_r ’）
( 但し、Ｔ_r ' ≒Ｔ_r ）で２タイムスロット分の処理を
行なうことができる。

【００４２】図１は、上述した基本原理を用いた本発明
のビタビ復号装置の一実施例を示すブロック図である。
この図に示すビタビ復号装置は、スワップ・インバータ
回路１と、パンクチャド処理回路２と、ブランチメトリ
ック計算回路３と、ＡＣＳ・ＳＭ正規化回路４と、正規
化指令回路５と、ステートメトリック記憶回路６と、パ
スメモリ回路７と、多数決復号決定回路８と、差動復号
回路９と、同期判定制御回路１０とを備えている。この
ビタビ復号装置において、送信側からのデータ（入力デ
ータ）が入力されたとき、送信側のエンコータから生成
され得る符号系列のなかから、受信された符号系列に最
も近い系列を選んで、この選択内容に基づいて復号デー
タを生成する。

【００４３】スワップ・インバータ回路１は、前記同期
判定制御回路１０からの制御指令に基づいて入力データ
を取り込むとともに、入力データにスワップ・インバー
タ処理を行なった後、処理済みの入力データをパンクチ
ャド処理回路２に供給する回路である。ここで、スワッ
プ・インバータ回路１は、無線回線、特に通信衛生を介
した通信を行う際に用いられるものであり、スワップ・
インバータ処理とは、衛星から送られてくる信号の位相
不確定を除去する処理である。

【００４４】パンクチャド処理回路２は、前記同期判定
制御回路１０からの制御指令に基づいて前記スワップ・
インバータ回路１から出力される入力データを取り込む
とともに、これらの入力データにパンクチャド処理を行
なった後、処理済みの入力データをブランチメトリック
計算回路３に供給する回路である。ここで、パンクチャ
ド処理とは、たたみ込み符号化処理された信号を送信す
る際に間引かれた消去ビットにヌル（ｎｕｌｌ）信号を
挿入し、補間する処理である。

【００４５】ブランチメトリック計算回路３は前記パン
クチャド処理回路２から出力される入力データを取り込
むとともに、この入力データのブランチメトリックを計
算してこの結果（ブランチメトリック）をＡＣＳ・ＳＭ
正規化回路４に供給する回路である。

【００４６】上記入力データのブランチメトリックと
は、ある時点において、情報系列（ｘ）をたたみ込み符
号化した送信系列（ｙ₁ ｙ₂ ）が、伝送路上で誤り（誤
り系列（ｅ₁ ｅ₂ ）を受けた入力データ（ｚ₁ ｚ₂ ）
（＝（ｙ₁ ＋ｅ₁ ，ｙ₂ ＋ｅ₂ ））と各パス（ｉ）のハ
ミング距離である。このハミング距離（ブランチメトリ
ック）ＢＭＸ_j は、次式で定義される。

【数４】

【００４７】ＡＣＳ・ＳＭ（Ａｄｄ Ｃｏｍｐａｒｅ
Ｓｅｌｅｃｔ・Ｓｔａｔｅ Ｍｅｔｒｉｃ）正規化回路
４は、ステートメトリックの演算および正規化、パスの
選択を行う回路である。ＡＣＳ・ＳＭ正規化回路４での
処理は以下に述べる通りである。ＡＣＳ・ＳＭ正規化回
路４は６４個の単位処理回路１１₁ 〜１１₆₄を備えてい
る。この単位処理回路１１₁ 〜１１₆₄において、前記ブ
ランチメトリック計算回路３から供給されるブランチメ
トリックと、前記ステートメトリック記憶回路６から供
給されるステートメトリック（累積和）とに基づいて、
ある状態に合流する４本のそれぞれのパスに対し、受信
符号とパスとのハミング距離（ブランチメトリック）
と、それまでのブランチメトリックの累積和（ステート
メトリック）を加算して加算値を求める。

【００４８】その後、これらの各加算値を比較し、この
比較結果に基づいて尤度の高いもの（ステートメトリッ
クの値が小さいパス）を選択してこの選択内容をパスメ
モリ回路７に供給する。これとともに、正規化指令回路
５からの正規化指令信号（論理値０の信号）が出力され
ていないときには、前記加算値を新たに得られた累積和
（ステートメトリック）としてそのまま正規化指令回路
５とステートメトリック記憶回路６とに供給する。

【００４９】また、正規化指令回路５からの正規化指令
信号が出力されているときには、前記加算値を正規化し
て予め設定されている範囲内の値にしてこれを新たに得
られた累積和（ステートメトリック）として正規化指令
回路５とステートメトリック記憶回路５とに供給する。

【００５０】前記各単位処理回路１１₁ 〜１１₆₄は、図
２に示すように加算部１２と、比較部１３と、エンコー
ダ部１４と、選択・正規化部１５とを備えている。各単
位処理回路１１₁ 〜１１₆₄はそれぞれ、前記ブランチメ
トリック計算回路３から供給されるブランチメトリック
と、前記ステートメトリック記憶回路６から供給される
ステートメトリックとに基づいて、ある状態に合流する
４本のそれぞれのパスに対し、受信符号とパスとのハミ
ング距離（ブランチメトリック）と、それまでのブラン
チメトリックの累積和（ステートメトリック）を加算し
て比較する。

【００５１】この比較結果に基づいて尤度の高いものを
選択しこの選択内容をパスメモリ回路７に供給する。こ
れとともに、正規化指令回路５からの正規化指令信号が
出力されていないときには、新たに得られた累積和（ス
テートメトリック）をそのまま正規化指令回路５とステ
ートメトリック記憶回路６とに供給する。

【００５２】また、正規化指令回路５から正規化指令信
号が出力されているときには、新たに得られたステート
メトリックに対して正規化処理を行って予め設定されて
いる範囲内の値にし、これを正規化指令回路５とステー
トメトリック記憶回路６とに供給する。

【００５３】ここで、ステートメトリックの正規化処理
とは、ステートメトリックは、ブランチメトリックが順
次累加算されて算出されるので、時間経過とともに値が
増大してゆく。したがって、ステートメトリックのビッ
ト長に記憶しきれなくなる（オーバーフローする）こと
があり得る。

【００５４】一方、ステートメトリックは絶対値に意味
があるわけではなく、各パスのステートメトリック相互
の値の大小関係に意味がある。このため、ステートメト
リックの値が一定値をこえたとき、例えば、ステートメ
トリックの最大ビット（ＭＳＢ）に論理値１が立ったと
きに、例えば第一の実施例におけるように、各ステート
メトリックを最小ビット（ＬＳＢ）側に１ビットシフト
して、上記予め設定されている範囲内の値にして供給す
る処理である。

【００５５】加算部１２は、前記ブランチメトリック計
算回路３から供給される２タイムスロット分のブランチ
メトリックと、前記ステートメトリック記憶回路６から
供給されるステートメトリックとをそれぞれ加算して加
算値を生成する４つの加算器１６₁ 〜１６₄ を備えてお
り、この加算動作によって得られた４つの加算値ＡＳ₁
〜ＡＳ₄ を比較部１３と選択・正規化部１５とに供給す
る。

【００５６】この場合、単位処理回路１１₁ 〜１１₆₄の
計算対象となっている状態節点がステートメトリックＳ
Ｍ₀₀、ＳＭ₁₆、ＳＭ₃₂、ＳＭ₄₈であり、ブランチメトリ
ックが、ＢＭＸ₁ 、ＢＭＸ_2,、ＢＭＸ₃ 、ＢＭＸ₄ であ
れば、加算部１２から次式に示す値の加算値（新たなス
テートメトリック）ＡＳ₁ 、ＡＳ₂ 、ＡＳ₃ 、ＡＳ₄が
生成されてこれが比較部１３と、選択・正規化部１５と
に供給される。

【数５】

【００５７】比較部１３は、前記各加算器１６₁ 〜１６
₄ から出力される４つの加算器ＡＳ₁ 、ＡＳ₂ 、Ａ
Ｓ₃ 、ＡＳ₄ を２つずつ組にして尤度の高い方を選択す
る６つの比較器１７₁ 〜１７₆ を備えており、前記各加
算器１６₁ 〜１６₄ から出力される４つの加算値Ａ
Ｓ₁ 、ＡＳ₂ 、ＡＳ₃ 、ＡＳ₄ を２つずつ組にして値を
比較して尤度が高い方を示す信号を生成してエンコーダ
部１４に供給する。

【００５８】エンコーダ部１４は、前記比較部１３を構
成する各比較器１７₁ 〜１７₆ から出力される信号をエ
ンコードして前記加算部１２から出力される加算値ＡＳ
₁ 、ＡＳ₂ 、ＡＳ₃ 、ＡＳ₄ のいずれかを指定するため
に必要な４ビットの選択信号を生成する第１エンコーダ
１８と、この第１エンコーダ１８から出力される４ビッ
トの選択信号をエンコードして２ビットの選択信号を生
成する第２エンコーダ１９とを備いる。

【００５９】このエンコーダ部１４は、前記各比較器１
７₁ 〜１７₆ から出力される信号をエンコードして前記
加算部１３から出力される加算値ＡＳ₁ 、ＡＳ₂ 、ＡＳ
₃ 、ＡＳ₄ のいずれかを指定する４ビットの選択信号を
生成し、この４ビットの選択信号を選択・正規化部１５
に供給する。また、これとともに、この選択信号を更に
エンコードして２ビットの選択信号を生成してこれをパ
スメモリ回路７に供給する。

【００６０】選択・正規化部１５は、図３に示すよう
に、割算器２０₁ 〜２０₄ と、アンドゲート２１₁ 〜２
１₄ と、アンドゲート２２₁ 〜２２₄ と、インバータ２
３およびオアゲート２６とを備えている。また、アンド
ゲート２１₁ 〜２１₄ は第１選択部２４を、アンドゲー
ト２２₁〜２２₄ およびインバータ２３は第２選択部２
５を構成する。

【００６１】ここで、４つの割算器２０₁ 〜２０₄ は、
前記加算部１２から選択・正規化部１５に出力される加
算値ＡＳ₁ 、ＡＳ₂ 、ＡＳ₃ 、ＡＳ₄ をＬＳＢ側にシフ
トして値を（１／２）にする。第１選択部２４は、４つ
のアンドゲート２１₁ 〜２１₄ を有し、前記正規化指令
回路５から正規化指令が出力されていないとき、前記加
算部１２から出力される加算値ＡＳ₁ 、ＡＳ₂ 、Ａ
Ｓ₃ 、ＡＳ₄ のうち、前記エンコーダ部１４から出力さ
れる４ビットの選択信号によって指定された加算値を選
択する。

【００６２】第２選択部２５は、４つのアンドゲート２
２₁ 〜２２₄ およびインバータ２３を有し、前記正規化
指令回路５から正規化指令が出力されているとき、前記
各割算器２０₁ 〜２０₄ から出力される正規化された加
算値ＡＳ₁ 、ＡＳ₂ 、ＡＳ₃、ＡＳ₄ のうち、前記エン
コーダ部１４から出力される４ビットの選択信号によっ
て指定された加算値を選択する。

【００６３】オアゲート２６は、これら第１選択部２４
および第２選択部２５のいずれかによって選択された加
算値を取り込んでこれを新たなステートメトリックとし
て出力する。

【００６４】そして、選択・正規化部１５は、前記加算
部１２から出力される加算値ＡＳ₁、ＡＳ₂ 、ＡＳ₃ 、
ＡＳ₄ を正規化して正規化済みの加算値ＡＳ₁ 、Ａ
Ｓ₂ 、ＡＳ₃ 、ＡＳ₄ と、正規化しない加算値ＡＳ₁ 、
ＡＳ₂ 、ＡＳ₃ 、ＡＳ₄ とを生成する。これとともに、
このとき前記正規化指令回路５から正規化指令が出力さ
れていなければ、第１選択部２４によって正規化しない
加算値ＡＳ₁ 、ＡＳ₂ 、ＡＳ₃、ＡＳ₄ のうち、前記エ
ンコーダ部１４から出力される４ビットの選択信号で指
定された加算値を選択してこれを正規化指令回路５とス
テートメトリック記憶回路６とに供給する。

【００６５】また、前記正規化指令回路５から正規化指
令が出力されていれば、第２選択部２５によって正規化
済みの加算値ＡＳ₁ 、ＡＳ₂ 、ＡＳ₃ 、ＡＳ₄ のうち、
前記エンコーダ部１４から出力される４ビットの選択信
号で指定された加算値を選択してこれを正規化指令回路
５とステートメトリック記憶回路６とに供給する。

【００６６】正規化指令回路５は、図４に示すように、
オアゲート３０₁ 〜３０₈ と、Ｄ型フリップフロップ３
１₁ 〜３１₈ と、オアゲート３２と、正規化指令生成回
路３３とを備えている。

【００６７】ここで、８つのオアゲート３１₁ 〜３１₈
は、前記ＡＣＳ・ＳＭ正規化回路４から出力される新た
なステートメトリックを取り込んで８つ単位で論理和を
とる。１つのオアゲート３２は、これら各Ｄ型フリップ
フロップ３１₁ 〜３１₈ から出力される論理和データの
論理和をとる。正規化指令生成回路３３は、シフトレジ
スタを有し前記オアゲート３２から出力される論理和デ
ータを予め設定されているタイムスロット分だけ遅延さ
せてそのＭＳＢが論理値１であるとき、正規化指令（論
理値０の信号）を生成する。

【００６８】正規化指令回路５は、前記ＡＣＳ・ＳＭ正
規化回路４から出力される新たなステートメトリックの
いずれかのＭＳＢが論理値１であるとき、所定タイムス
ロット後に、正規化指令を生成してこれをＡＣＳ・ＳＭ
正規化回路４に供給する。

【００６９】例えば、ステートメトリックのビット数が
最大７ビットで、入力データが８値軟判定入力である場
合、ステートメトリックの値が１タイムスロットごとに
ブランチメトリックのとり得る最大値（１４）で増加し
てそのＭＳＢが論理値１になってからオーバーフロー寸
前までの時間が（３．５）タイムスロットである。

【００７０】ここで、８つのオアゲート３０₁ 〜３０₈
と１つのオアゲート３２によって０．５タイムスロット
遅延され、８つのＤ型フリップフロップ３１₁ 〜３１₈
によって１タイムスロット遅延され、シフトレジスタ３
３によって２タイムスロット遅延される。これによって
前記ＡＣＳ・ＳＭ正規化回路４から出力される新たなス
テートメトリックのいずれかのＭＳＢが論理値１になっ
たときから、（３．５）タイムスロット後に、正規化指
令が生成されてこれがＡＣＳ・ＳＭ正規化回路４に供給
される。

【００７１】また、ステートメトリック記憶回路６は前
記ＡＣＳ・ＳＭ正規化回路４から供給されるステートメ
トリックを記憶するとともに、記憶している各ステート
メトリックを前記ＡＣＳ・ＳＭ正規化回路４に供給す
る。

【００７２】また、パスメモリ回路７は前記ＡＣＳ・Ｓ
Ｍ正規化回路４から出力される選択内容を記憶してこの
選択内容を多数決復号決定回路８に供給する。

【００７３】多数決復号決定回路８は前記パスメモリ回
路７に記憶されている選択内容に基づいて最尤のパスを
判定して復号データを生成し、これを差動復号回路９と
同期判定制御回路１０とに供給する。

【００７４】差動復号回路９は前記多数決復号決定回路
８から出力される復号データを取り込むとともに、この
復号データの差動復号化処理を行って復号データを生成
し、これを次段回路（図示は省略）に出力する。

【００７５】同期判定制御回路１０は前記多数決復号決
定回路８から出力される復号データに基づいて同期を判
定してこの判定内容に基づいて前記スワップ・インバー
タ回路１と、パンクチャド処理回路２との同期を制御す
る。

【００７６】このように、第一の実施例においては、２
タイムスロット単位でＡＣＳ演算を行なうようにしてい
るので、１タイムスロットごとにＡＣＳ演算を行なうと
きに比べて、２タイムスロット分のＡＣＳ演算に要する
時間を約半分にすることができ、これによってＨＤＴＶ
放送等において使用される３０Ｍｂｐｓ以上の情報量を
持つたたみ込み符号を復号することができる。

【００７７】また、第一の実施例においては、ＡＣＳ・
ＳＭ正規化回路４とステートメトリック記憶回路６とに
よって構成されたループ外に正規化指令回路５を設け、
前記ループの外で正規化処理の必要有無判定、正規化タ
イミングの処理等を行なう。これとともに、正規化の必
要があると判定されたとき、ステートメトリックの少な
くともいずれか１つがオーバーフローする前に、ＡＣＳ
・ＳＭ正規化回路４によって正規化されたステートメト
リックを選択させこれを新たなステートメトリックとし
て出力させるようにしている。よって、従来のようにＡ
ＣＳ回路内に設けられた加算器と、正規化回路と、ステ
ートメトリック記憶回路とがループ上につながっている
回路に比べて、ループ全体をさらに高速で動作させるこ
とができる。

【００７８】また、第一の実施例においては、ＡＣＳ・
ＳＭ正規化回路４内に６つの比較器１７₁ 〜１７₆ を設
け、各加算器１６₁ 〜１６₄ から出力される４つの加算
値ＡＳ₁ 、ＡＳ₂ 、ＡＳ₃ 、ＡＳ₄ を１度に比較判定す
ることができ、これによって最小の遅れ時間で最尤の加
算値を得ることができる。

【００７９】また、第一の実施例においては、２タイム
スロット単位でＡＣＳ演算を行なうようにしているの
で、１タイムスロットごとにＡＣＳ演算を行なうときに
比べて、２タイムスロット分のＡＣＳ演算に要する時間
を約半分にすることができ、これによってＨＤＴＶ放送
等において使用される３０Ｍｂｐｓ以上の情報量を持つ
たたみ込み符号を復号することができる。

【００８０】また、第一の実施例においては、ＡＣＳ・
ＳＭ正規化回路４内に６つの比較器１７₁ 〜１７₆ を設
け、各加算器１６₁ 〜１６₄ から出力される４つの加算
値ＡＳ₁ 、ＡＳ₂ 、ＡＳ₃ 、ＡＳ₄ を２組ずつ組にして
値を比較して尤度が高い方を選択するようにしている。
よって、これら各加算値ＡＳ₁ 、ＡＳ₂ 、ＡＳ₃ 、ＡＳ
₄ を１度に比較判定することができ、これによって最小
の遅れ時間で最尤の加算値を得ることができる。

【００８１】以下、第二の実施例について説明する。第
二の実施例は、第二の実施例において２タイムスロット
ごと行われていた各状態節点に合流するパスに対して、
受信符号との距離が最小になるパスを選択する演算を、
ｎタイムスロット（ｎ＞２、ｎは整数）、例えば、３タ
イムスロットごとに行うものである。

【００８２】従来の方法においては、第一の実施例にお
いて説明したように各タイムスロットごとに各状態節点
に合流するパスに対して、受信符号との距離が最小にな
るパスを選択する演算を行なう。

【００８３】一方、第二の実施例のビタビ復号装置にお
いては、第一の実施例においては２タイムスロットごと
に行われた各状態節点に合流するパスに対して、受信符
号との距離が最小になるパスを選択する演算を、３タイ
ムスロットごとに演算を行なうようにする。このように
して、従来の方法においては各タイムスロットごとに必
要だったステートメトリックとブランチメトリックとの
加算処理時間、各加算結果の比較処理時間、各パスの選
択処理時間を３タイムスロットに１回の割合にし、これ
によって３タイムスロット分の処理時間を次式の値にす
る。

【数６】

【００８４】３タイムスロットおきにＡＣＳ（加算・比
較・選択）計算を行なっても、従来の１タイムスロット
ごとの計算と全く同じ結果を得ることができる。そし
て、（式６）で示される加算時間Ｔ_A3' 、比較時間
Ｔ_C3' 、選択時間Ｔ_S3' は次式に示す従来の方式におい
て各タイムスロットごとに必要な加算時間Ｔ_A、比較時
間Ｔ_C 、選択時間Ｔ_S とそれぞれ、ほぼ同じ値になる。

【数７】 このように、第二の実施例においては、ｎタイムスロッ
ト単位でＡＣＳ演算を行なうようにしているので、１タ
イムスロットごとにＡＣＳ演算を行なうときに比べて、
ｎタイムスロット分のＡＣＳ演算に要する時間を約（１
／ｎ）にすることができ、第一の実施例のビタビ復号装
置よりもさらに高速なたたみ込み符号の復号を実現する
ことができる。

【００８５】以下、第三の実施例について説明する。第
一の実施例においては、ＡＣＳ・ＳＭ正規化回路４で一
括してＡＣＳ演算とステートメトリックの正規化処理を
行っていたが、これらを別の回路により行うように構成
したものである。ここで説明しない第三の実施例におけ
るビタビ復号装置の各部分の構成および動作は第一の実
施例で述べた通りである。

【００８６】図１０に、第三の実施例におけるビタビ復
号装置の構成を示す。ステートメトリック計算回路４０
は、ブランチメトリック計算回路３が出力するブランチ
メトリックに基づいてステートメトリックを計算する回
路である。ＡＣＳ回路４１は、ＡＣＳ演算を行う回路で
ある。このように構成しても、第一の実施例におけるビ
タビ復号装置およびその方法１同様な効果を得ることが
できる。

【００８７】以下、第四の実施例について説明する。第
四の実施例は、ＡＣＳ・ＳＭ正規化回路４の変形例であ
る。第一の実施例においては、ＡＣＳ・ＳＭ正規化回路
４はステートメトリックの正規化方法として、ステート
メトリックのＭＳＢが論理値１である場合に、ステート
メトリックをＬＳＢ側に１ビットシフトすることによ
り、正規化を行っていたが、本実施例においては、最も
小さい値のステートメトリックの値を、そのステートメ
トリック自身および他のステートメトリックから減算す
ることによりステートメトリックの正規化を行う。

【００８８】第四の実施例のステートメトリック正規化
方法によれば、ステートメトリックの相互の値の大小
を、より正確に正規化後も保存することが可能である。
また、第一の実施例で述べたステートメトリックの正規
化と、第一の実施例および第三の実施例で述べたｎタイ
ムスロット単位でのＡＣＳ計算は不可分でなく、それぞ
れ別々に用いることも可能である。

【００８９】以上述べた構成の他、本発明のビタビ復号
装置およびその方法は種々の構成をとることができる。
以上述べた各実施例は例示である。

【００９０】

【発明の効果】以上説明したように本発明によれば、非
常に高速な情報速度を有するたたみ込み符号を復号する
ことができる。

【図面の簡単な説明】

【図１】本発明によるビタビ復号装置の一実施例を示す
ブロック図である。

【図２】図１に示すＡＣＳ・ＳＭ正規化回路の詳細な構
成例を示すブロック図である。

【図３】図２に示す選択・正規化部の詳細な構成例を示
す回路図である。

【図４】図１に示す正規化指令回路の詳細な構成例を示
す回路図である。

【図５】従来から知られているビタビ復号装置の一例を
示すブロック図である。

【図６】図５に示すＡＣＳ回路の動作例を示す２タイム
スロット分の遷移ダイヤグラムである。

【図７】図５に示すＡＣＳ回路の演算に要する時間を示
す模式図である。

【図８】本発明によるビタビ復号装置の基本原理を示す
２タイムスロット分の遷移ダイヤグラムである。

【図９】本発明によるＡＣＳ演算に要する時間を示す模
式図である。

【図１０】本発明のビタビ復号装置におけるＡＣＳ・Ｓ
Ｍ正規化回路の変形例を示す図である。

【符号の説明】

３・・・ブランチメトリック計算回路 ４・・・ＡＣＳ・ＳＭ正規化回路（ＡＣＳ計算回路） ５・・・正規化指令回路 ６・・・ステートメトリック記憶回路 ７・・・バスメモリ回路 ８・・・多数決復号決定回路

Claims (8)

【特許請求の範囲】
1. 【請求項１】複数のタイムスロットのデータについて、
   複数のパスとのブランチメトリックをそれぞれ算出する
   ブランチメトリック算出手段と、 前記複数のタイムスロットごとに、前記複数のタイムス
   ロット分のブランチメトリックとこれらのブランチメト
   リックに対応するステートメトリックとを加算し、この
   加算結果を相互に比較し、この比較結果に基づいて最も
   尤度の高いパスを求める処理を一括して行う加算・比較
   ・選択手段と、 前記複数のタイムスロットごとに前記加算・比較・選択
   手段によって得られたパス内容に基づいて入力データを
   復号する最尤復号判定手段とを有するビタビ復号装置。
2. 【請求項２】複数のタイムスロットのデータについて、
   複数のパスとのブランチメトリックをそれぞれ算出する
   ブランチメトリック算出手段と、 ステートメトリックを算出し、記憶するステートメトリ
   ック算出記憶手段と、 前記複数のタイムスロットごとに、前記複数のタイムス
   ロット分のブランチメトリックとこれらのブランチメト
   リックに対応するステートメトリックとを加算し、この
   加算結果を相互に比較し、この比較結果に基づいて最も
   尤度の高いパスを求める処理を一括して行う加算・比較
   ・選択手段と、 前記複数のタイムスロットごとに前記加算・比較・選択
   手段によって得られたパス内容に基づいて入力データを
   復号する最尤復号判定手段とを有するビタビ復号装置。
3. 【請求項３】請求項２記載のビタビ復号装置において、 前記加算・比較・選択手段は、前記複数のタイムスロッ
   トごとに、前記複数のパスのそれぞれとの現処理段階に
   おける前記複数タイムスロット分のブランチメトリック
   と、前記ステートメトリック算出記憶手段に記憶されて
   いる前処理段階までのこれらのブランチメトリックに対
   応するステートメトリックとをそれぞれ加算する複数の
   加算手段と、 これら複数の加算手段の加算結果を相互に比較する複数
   の比較手段と、 これら複数の比較手段の比較結果から、最も尤度の高い
   パスを選択する選択手段とから構成されることを特徴と
   するビタビ復号装置。
4. 【請求項４】２タイムスロットのデータについて、複数
   のパスとのブランチメトリックをそれぞれ算出するブラ
   ンチメトリック算出手段と、 ステートメトリックを算出し、記憶するステートメトリ
   ック算出記憶手段と、 前記２タイムスロットごとに、一つの状態節点合流する
   ４本のパスのそれぞれとの、現処理段階における前記２
   タイムスロット分のブランチメトリックとこれらのブラ
   ンチメトリックに対応するステートメトリックとを加算
   し、この加算結果を相互に比較し、この比較結果に基づ
   いて最も尤度の高いパスを求める処理を一括して行う加
   算・比較・選択手段と、 前記２タイムスロットごとに前記加算・比較・選択手段
   によって得られたパス内容に基づいて入力データを復号
   する最尤復号判定手段とを有するビタビ復号装置。
5. 【請求項５】請求項４記載のビタビ復号装置において、 前記加算・比較・選択手段は、２タイムスロットごと
   に、一つの状態節点合流する４本のパスのそれぞれとの
   現処理段階における前記２タイムスロット分のブランチ
   メトリックと、前記ステートメトリック算出記憶手段に
   記憶される前処理段階までのこれらのブランチメトリッ
   クに対応するステートメトリックとをそれぞれ加算する
   ４個の加算手段と、 これら４個の加算手段の加算結果を相互に比較する６個
   の比較手段と、 これら６個の比較手段の比較結果から、最も尤度の高い
   パスを選択する選択手段とから構成されることを特徴と
   するビタビ復号装置。
6. 【請求項６】ブランチメトリックを算出するブランチメ
   トリック算出手段と、 ステートメトリックを算出し、記憶するステートメトリ
   ック算出記憶手段と、 現処理段階におけるブランチメトリックと、前記ステー
   トメトリック算出記憶手段に記憶されている前処理段階
   までのこれらのブランチメトリックに対応するステート
   メトリックとに基づいて、次のステートメトリックを算
   出するステートメトリック算出手段と、 前記次のステートメトリックを記憶するワードの内、少
   なくともいずれかのＭＳＢがアサートされた時点から前
   記ステートメトリックを記憶するワードがオーバーフロ
   ーする寸前までの最大時間間隔を予測計算して正規化タ
   イミングを決定し、この決定に基づいて正規化指令信号
   を出力する正規化指令手段と、 前記正規化指令手段から正規化指令信号がアサートされ
   ている期間においては、前記演算手段によって得られた
   前記次のステートメトリックをＬＳＢ側にシフトし、正
   規化し、このステートメトリックを新たなステートメト
   リックとして前記ステートメトリック算出記憶手段に記
   憶させ、前記正規化指令手段からの正規化指令信号がネ
   ゲートされている期間においては、前記次のステートメ
   トリックについて前記正規化せずに、これを新たなステ
   ートメトリックとして前記ステートメトリック算出記憶
   手段に記憶させる選択・正規化手段と、 前記新たなステートメトリックに基づいて入力データを
   復号する最尤復号判定手段とを有することを特徴とする
   ビタビ復号装置。
7. 【請求項７】請求項１〜６のいずれかに記載のビタビ復
   号装置において、 入力されるデータについてスワップ・インバータ処理を
   行うスワップ・インバータ手段をさらに有することを特
   徴とするビタビ復号装置。
8. 【請求項８】複数のタイムスロットのデータについて、
   複数のパスとのブランチメトリックをそれぞれ算出し、 前記複数のタイムスロットごとに、前記複数のタイムス
   ロット分のブランチメトリックとこれらのブランチメト
   リックに対応するステートメトリックとを加算し、この
   加算結果を相互に比較し、この比較結果に基づいて最も
   尤度の高いパスを求める処理を一括して行い、 前記処理によって得られたパス内容に基づいて入力デー
   タを復号するビタビ復号方法。