JPH10200421A - ビタビデコーダにおける加算／比較／選択処理器 - Google Patents

ビタビデコーダにおける加算／比較／選択処理器

Info

Publication number
JPH10200421A
JPH10200421A JP9226267A JP22626797A JPH10200421A JP H10200421 A JPH10200421 A JP H10200421A JP 9226267 A JP9226267 A JP 9226267A JP 22626797 A JP22626797 A JP 22626797A JP H10200421 A JPH10200421 A JP H10200421A
Authority
JP
Japan
Prior art keywords
meters
meter
decision
state
path
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
JP9226267A
Other languages
English (en)
Inventor
Eibai Sai
榮培 崔
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.)
WiniaDaewoo Co Ltd
Original Assignee
Daewoo Electronics Co Ltd
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 Daewoo Electronics Co Ltd filed Critical Daewoo Electronics Co Ltd
Publication of JPH10200421A publication Critical patent/JPH10200421A/ja
Pending legal-status Critical Current

Links

Classifications

    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M7/00—Conversion of a code where information is represented by a given sequence or number of digits to a code where the same, similar or subset of information is represented by a different sequence or number of digits
    • 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

Landscapes

  • Physics & Mathematics (AREA)
  • Probability & Statistics with Applications (AREA)
  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Error Detection And Correction (AREA)
  • Detection And Correction Of Errors (AREA)

Abstract

(57)【要約】 【課題】 ＡＳＩＣの設計時にハードウエアの面積効率
を向上させることができるビタビデコーダにおける加算
／比較／選択処理器を提供する。 【解決手段】 グルーピング部４１０により、二つの経
路メートルと二つのブランチメートルを相互比較して比
較結果に応じる二つの判定ビット及び状態メートルを出
力するプロセシング要素４３０を同一な状態メートル及
びブランチメートルを用いるプロセシング要素にグルー
プ化し、多重化部４２０によりグルーピング結果に応じ
て供給される経路メートルをクロック信号に応じて二つ
の経路メートルに多重化してプロセシング要素４３０に
出力し、第１逆多重化部４４０によりプロセシング要素
４２０から出力される二つの判定ビットを逆多重化する
とともに、第２逆多重化部４５０によりプロセシング要
素４３０から出力される二つの状態メートルを逆多重化
する。

Description

【発明の詳細な説明】
【０００１】
【発明の属する技術分野】本発明はビタビデコーダにお
ける加算／比較／選択処理器に関し、特にＮ個の状態に
対するＮ個のプロセシング要素を同一な状態メートル(s
tate metric)及び同一なブランチメートル(branch metr
ic)を用いる所定単位のプロセシング要素にグループ化
させて、一つのプロセシング要素で複数個の状態に対す
る加算／比較／選択処理を行うように具現化した加算／
比較／選択処理器に関するものである。
【０００２】
【従来の技術】一般に、重畳符号の最尤復号(maximum l
ikelihood decoding)のための高実用かつ高効率の方法
としては、ビタビ(viterbi)復号化アルゴリズムがもっ
とも広く用いられている。ビタビ復号化アルゴリズムで
はトレリス図を用いるが、任意の状態で遭遇する相異な
る二つの経路に対して経路の長さを比較し、そのうち短
い経路、すなわちエラー発生確率の低い経路を選択して
生存経路（survivor path）として設定する。このよう
なビタビ復号化アルゴリズムを用いるビタビデコーダは
非常に優れたランダムエラー訂正能力を有するので、例
えば衛星通信システムにおけるエラーの訂正に用いられ
ている。
【０００３】前述したビタビ復号化アルゴリズムを図１
に基づき更に詳細に説明する。図１の（ａ）はノード
数、すなわち状態数が２であるトレリス図を示したもの
であり、垂直方向は状態(Ｓi、ここでｉは１,２)、水平
方向は時間(ｔ／Ｔ：ここで１／Ｔは伝送率のことを示
す)、Ｓi,kは時間ｋにおけるｉ番目の状態をそれぞれ示
す。有限状態機械は図１の（ａ）に示されたトレリス図
を通して任意の経路を選択し、観察される状態の遷移に
応じて時間間隔(ｋ,ｋ+１)に対するブランチメートル
(λ)を計算する。すなわち、トレリス図によると、時間
ｋにおける状況(Ｓ1,k,Ｓ2,k)は時間間隔(ｋ,ｋ+１)に
対する各ブランチにより時間(ｋ+１)における状況(Ｓ
1,k+1,Ｓ2,k+1)と連結される。ビタビ復号化の時、受信
信号に対応するブランチにおけるコード間の距離、すな
わちブランチメートルを計算するが、前記ブランチメー
トルは硬判定復号(hard decision decoding)の場合にハ
ミング距離(hamming distance)となり、軟判定復号(sof
t decision decoding)の場合にユークリッド距離(eucli
dean distance)となる。
【０００４】このように計算されたブランチメートルを
用いて、時間(ｋ+１)における各ノードに対する新たな
経路メートル(path metric)が、時間ｋにおける経路メ
ートル(γ)と時間間隔(ｋ,ｋ+１)に対するブランチメー
トル(λ)により計算されるが、これを図１の（ｂ）に基
づき説明する。
【０００５】図１の（ｂ）において、時間ｋのノードＳ
1,k,Ｓ2,kがブランチメートルを累積した値である経路
メートルγ1,k,γ2,kをそれぞれ有し、時間間隔(ｋ,ｋ+
１)に対するブランチメートルをλ11,k,λ12,k,λ21,k,
λ22,kとする場合、時間(ｋ+１)におけるノード
Ｓ1,k+1,Ｓ2,k+1の新たな経路メートルγ1,k+1,γ2,k+1
は下記の式１により求められる。
【０００６】[ 式１ ] γ1,k+1 ＝ max [λ11,k＋γ1,k, λ12,k＋γ2,k] γ2,k+1 ＝ max [λ21,k＋γ1,k, λ22,k＋γ2,k] すなわち、時間(ｋ+１)にあるノードに来れる経路の種
類は時間ｋに存在する状態の変化に応じて複数個が存在
するので、確率情報のブランチメートルを用いて経路メ
ートルを探す。このような経路メートルを計算する過程
を各時間ｋに対して循環的に行い最終的な生存経路を探
す。
【０００７】一方、生存経路をトレースバックすると、
図１の（ｂ）に示されたように、任意の時点で経路が非
常に高い確率で合流するが、前記非常に高い確率で合流
する時間段階の数を生存深さといい、前記生存深さによ
りビタビ復号化の待ち時間が左右される。すなわち、各
ノード毎に前記式１により経路メートル(γ)を更新する
と、生存深さの以前に当たる各経路の状態は同一にな
る。従って、このようなトレースバックにより得られる
生存深さの以前の状態変化をビタビ復号化データとして
出力する。
【０００８】図２は一般的なビタビデコーダを示すブロ
ック図であり、ブランチメートル生成部100と、加算／
比較／選択処理部200と、生存メモリ部300とから構成さ
れる。
【０００９】図２において、ブランチメートル生成部10
0は受信される重畳符号化されたデータを入力して受信
信号に対応する各ブランチにおけるコード間の距離であ
るブランチメートル(λij,k )を計算して出力する。こ
の際、ブランチメートル生成部100の複雑度は受信され
る符号語の長さと直接的な関係があり、符号語を構成す
るビット数が多いほど回路が複雑になる。例えば、符号
語が２ビットから構成されると、受信された符号語２ビ
ットを比較するために必要な比較符号語は２2個、すな
わち四つである。一方、符号語が３ビットから構成され
ると、一つの受信された符号語を比較してブランチメー
トルを計算するためには２3個、すなわち八つの比較符
号語が必要になる。かつ、符号語が長くなると、符号語
が短い場合に比べて計算されたブランチメートル値が大
きくなる。結局、比較符号語の数が増加しブランチメー
トル値が大きくなった分だけ該ブランチメートルを記憶
するためのメモリの記憶容量が大きくなるため、次段の
加算／比較／選択処理部200が複雑になる。
【００１０】加算／比較／選択処理部200はブランチメ
ートル生成部100からブランチメートルを入力して直前
の経路メートルに加算して複数個の候補経路を設定す
る。次に、複数個の候補経路を比較して最短経路メート
ルを有する経路を選択した後、前記選択された新たな経
路メートルと比較結果である判定ビットを出力する。加
算／比較／選択処理部200では、各復号サイクル毎にブ
ランチメートル生成部100から提供されたブランチメー
トルを用いて経路メートルを更新した後、Ｎビットの判
定ビットを次段の生存メモリ部300に出力する。全部で
Ｎ個の状態からなるトレリス図を仮定する場合、各復号
サイクル毎にＮビットを得るようになる。
【００１１】生存メモリ部300は加算／比較／選択処理
部200から提供された判定ビットを格納し、前記格納さ
れた判定ビットを用いて元の情報シーケンスを復元して
ビタビ復号化されたデータとして出力する。
【００１２】図３は図２に示された加算／比較／選択処
理部200を構成するプロセシング要素310を示したブロッ
ク図であり、プロセシング要素310は第１処理部320と第
２処理部340とから構成される。ここで、第１処理部320
は第１加算器322と、第２加算器324と、第１比較器326
と、第１選択器328とから構成され、第２処理部340は第
３加算器342と、第４加算器344と、第２比較器346と、
第２選択器348とから構成される。
【００１３】図３において、γX ,γY はプロセシング
要素310に入力される経路メートルであり、ここでは６
ビットから構成されるものを例に挙げる。このうち、γ
X は第１処理部320の第１加算器322と第２処理部340の
第３加算器342に入力され、γYは第１処理部320の第２
加算器324と第２処理部340の第４加算器344に入力され
る。かつ、λX ,λY はブランチメートル生成部100(図
２参照)から提供されるブランチメートルであり、ここ
では４ビットから構成されるものを例に挙げる。このう
ち、λX は第１処理部320の第１加算器322と第２処理部
340の第４加算器344に入力され、λY は第１処理部320
の第２加算器324と第２処理部340の第３加算器342に入
力される。一方、第１処理部320の第１比較器326と第２
処理部340の第２比較器346から出力された第１判定ビッ
トと第２判定ビットは次段の生存メモリ部300(図２参
照)に供給される。
【００１４】次いで、図３に基づき加算／比較／選択処
理部200を構成する一つのプロセシング要素310に対する
動作を説明すると次の通りである。
【００１５】まず、第１処理部320に対して説明する
と、第１加算器322では経路メートルγX とブランチメ
ートルλX を加算して、その加算値をそれぞれ第１比較
器326と第１選択器328に出力し、第２加算器324では経
路メートルγY とブランチメートルλY を加算して、そ
の加算値をそれぞれ第１比較器326と第１選択器328に出
力する。
【００１６】第１比較器326では、第１加算器322からの
加算値と第２加算器324からの加算値とを比較して、前
記比較結果の第１判定ビットを生存メモリ部 300(図２
参照)に出力する一方、第１選択器328の選択信号として
供給する。例えば、第１比較器326における比較結果と
して、第１加算器322からの加算値が第２加算器324から
の加算値より大きい場合には第１判定ビットが“０”
で、その逆の場合には“１”で出力される。
【００１７】第１選択器328では、選択信号に応じて第
１加算器322からの加算値又は第２加算器324からの加算
値を選択的に出力する。すなわち、第１選択器328は第
１判定ビットが“０”の場合に第２加算器324からの加
算値を選択して状態メートルとして出力し、第１判定ビ
ットが“１”の場合には第１加算器322からの加算値を
選択して状態メートルとして出力する。
【００１８】一方、第２処理部340について説明する
と、第３加算器342では経路メートルγX とブランチメ
ートルλY を加算して、前記加算値をそれぞれ第２比較
器346と第２選択器348に出力し、第４加算器344では経
路メートルγY とブランチメートルλX を加算して、前
記加算値をそれそれ第２比較器346と第２選択器348に出
力する。
【００１９】第２比較器346では、第３加算器342からの
加算値と第４加算器344からの加算値とを比較して、前
記比較結果の第２判定ビットを生存メモリ部 300(図２
参照)に出力する一方、第２選択器348の選択信号として
供給する。例えば、第２比較器346における比較結果、
第３加算器342からの加算値が第４加算器344からの加算
値より大きい場合には第２判定ビットが“０”で、その
逆の場合には“１”で出力される。
【００２０】第２選択器348では、選択信号に応じて第
３加算器342の加算値又は第４加算器344の加算値を選択
的に出力する。すなわち、第２選択器348は第２判定ビ
ットが“０”の場合に第４加算器344からの加算値を選
択して状態メートルとして出力し、第２判定ビットが
“１”の場合には第３加算器 342からの加算値を選択し
て状態メートルとして出力する。
【００２１】図３に示したように、同一な状態メートル
を用いる二つのプロセシング要素はグループ化して一つ
のプロセシング要素に束ねることができる。すなわち、
一つのプロセシング要素で二つの状態に対する加算／比
較／選択処理が行われるので、６４個の状態モードの場
合には３２個のプロセシング要素(ＰＥ０〜ＰＥ３１)で
加算／比較／選択処理器を具現化することができる。
【００２２】前述したような加算／比較／選択処理器
は、一つのプロセシング要素で一つの状態を処理するよ
うに具現化されたものの更に改善する必要がある。すな
わち、最近、特定用途集積回路(ＡＳＩＣ)又は専用集積
回路の製造技術が急速に発展するにつれて、一つのプロ
セシング要素で少なくとも二つ以上の状態が処理できる
ハードウエアを具現化することによりＡＳＩＣ設計時の
面積効率を更に向上させる必要性が高まりつつある。
【００２３】
【発明が解決しようとする課題】本発明は前記の問題点
を解決するために案出されたものであり、本発明の目的
は、一つのプロセシング要素で複数個の状態に対する加
算／比較／選択処理が行われるように具現化することに
より、ＡＳＩＣ設計時の面積効率を向上することができ
る加算／比較／選択処理器を提供することにある。
【００２４】
【課題を解決するための手段】前記目的を達成するため
に本発明による加算／比較／選択処理器は、重畳符号に
対する最尤復号を行うためのビタビデコーダにおいて、
二つの経路メートルと二つのブランチメートルを入力し
て、それぞれ加算した値を相互比較し、前記比較結果に
応じる二つの判定ビットと二つの状態メートルを出力す
るＮ個のプロセシング要素と、Ｎ個の状態に対する前記
Ｎ個のプロセシング要素を同一な状態メートルと同一な
ブランチメートルを用いるＫ単位のプロセシング要素に
グループ化させるためのグルーピング部と、前記グルー
ピング結果に応じて供給されるＬ(ここで、Ｌは２Ｋ)個
の経路メートルを所定のクロック信号に応じて二つの経
路メートルに多重化して対応するプロセシング要素に出
力するための多重化部と、前記対応するプロセシング要
素から出力される二つの判定ビットを入力して、前記ク
ロック信号に応じてＬ個の判定ビットに逆多重化して出
力する第１逆多重化部と、前記対応するプロセシング要
素から出力される二つの状態メートルを入力して、前記
クロック信号に応じてＬ個の状態メートルに逆多重化し
て出力する第２逆多重化部とを含むことを特徴とする。
【００２５】
【発明の実施の形態】以下、本発明の一実施形態を添付
した図面に基づき更に詳細に説明する。
【００２６】図４はビタビデコーダにおいて本発明の一
実施形態による加算／比較／選択処理器を示したブロッ
ク図であり、加算／比較／選択処理器は複数個のプロセ
シング要素から構成されているが、説明の便宜上一つの
プロセシング要素のみについて説明することにする。
【００２７】図４に示された加算／比較／選択処理器
は、グルーピング部410と、多重化部（マルチプレクサ
ー）420と、プロセシング要素430と、第１逆多重化部
（第１ディマルチプレクサー）440と、第２逆多重化部
（第２ディマルチプレクサー）450と、制御部460とから
構成される。ここで、各構成要素の入出力信号に対して
説明すると、ＰＡ０,ＰＡ１,ＰＢ０,ＰＢ１は多重化部4
20に入力される６ビット単位の経路メートルであり、γ
X ,γY は多重化部 420から出力される６ビット単位の
経路メートルであり、λX ,λY はプロセシング要素430
に入力される４ビット単位のブランチメートルであり、
ＤＡ０,ＤＡ１,ＤＢ０,ＤＢ１は第１逆多重化部440から
出力される判定ビットであり、ＳＡ０,ＳＡ１,ＳＢ０,
ＳＢ１は第２逆多重化部450から出力される６ビット単
位の状態メートルである。
【００２８】図４において、グルーピング部410はＮ個
の状態に対するＮ個のプロセシング要素を、同一な状態
メートル及び同一なブランチメートルを用いる所定単位
のプロセシング要素にグループ化させるためのものであ
り、ここでは６４個の状態モードの場合、一つのプロセ
シング要素で処理できる状態数、すなわちグループ化単
位が四つである場合を例示することにする。
【００２９】多重化部420には、四つの経路メートル(Ｐ
Ａ０,ＰＡ１,ＰＢ０,ＰＢ１)が入力され、多重化部420
は、クロック信号(ＣＬＫ)に応じて二つの経路メートル
(γX,γY＝ＰＡ０,ＰＡ１又はＰＢ０,ＰＢ１)を選択し
てプロセシング要素430に出力する。
【００３０】プロセシング要素430は、図３に示された
一般的なプロセシング要素310と同一なものであり、多
重化部420から供給される二つの経路メートル(γX ,γY
)とブランチメートル生成部100(図１参照)から供給さ
れる二つのブランチメートル(λX ,λY )を入力して二
つの判定ビット(第１判定ビット、第２判定ビット)及び
二つの状態メートルを出力する。更に詳細な説明は従来
の技術で前述したため、ここでは省略することにする。
【００３１】第１逆多重化部440には、プロセシング要
素430から出力された二つの判定ビット(第１判定ビッ
ト、第２判定ビット)が入力され、第１逆多重化部440
は、クロック信号に応じて四つの判定ビット(ＤＡ０,Ｄ
Ａ１,ＤＢ０,ＤＢ１)に逆多重化して出力する。
【００３２】第２逆多重化部450には、プロセシング要
素430から出力された二つの状態メートルが入力され、
第２逆多重化部450は、クロック信号に応じて四つの状
態メートル(ＳＡ０,ＳＡ１,ＳＢ０,ＳＢ１)に逆多重化
して出力する。
【００３３】次いで、前述したような本発明の加算／比
較／選択処理器の作用及び効果に対して図３及び図４に
基づき更に詳細に説明する。
【００３４】まず、６４個の状態モードの場合、図３の
ような構造のプロセシング要素からなる加算／比較／選
択処理器をＡＳＩＣ化するためのプログラムは次の通り
である。ここで用いられたプログラム言語はＶＨＤＬ(V
ery High Definition Language)である。
【００３５】 component T_ACS52 port( bmet_x,bmet_y ：in,std_logic_vector(Bit_Branch-1 downto 0): pmet_x,pmet_y :in,std_logic_vector(Bit_State-1 downto 0): over_flag：out,std_logic: …overflow indicator a,b decision_a,decision_b：out,std_logic: …decision bit smet_a,smet_b：out,std_logic_vector(Bit_State-1 downto 0) ); end component; begin PE_ASSIGN：process(bmet0,bmet1,bmet2,bmet3,pmet) …begin PE0：T_ACS52 port Map(bmet0,bmet3,pmet(0),pmet(1), over_flag(0),decision_a(0),decision_b(0),smet(0),smet(32)); PE1：T_ACS52 port Map(bmet1,bmet2,pmet(2),pmet(3), over_flag(1),decision_a(1),decision_b(1),smet(1),smet(33); PE2：T_ACS52 port Map(bmet0,bmet3,pmet(4),pmet(5), over_flag(2),decision_a(2),decision_b(2),smet(2),smet(34)); PE3：T_ACS52 port Map(bmet1,bmet2,pmet(6),pmet(7), over_flag(3),decision_a(3),decision_b(3),smet(3),smet(35)); PE4：T_ACS52 port Map(bmet3,bmet0,pmet(8),pmet(9), over_flag(4),decision_a(4),decision_b(4),smet(4),smet(36)); PE5：T_ACS52 port Map(bmet2,bmet1,pmet(10),pmet(11), over_flag(5),decision_a(5),decision_b(5),smet(5),smet(37)); PE6：T_ACS52 port Map(bmet3,bmet0,pmet(12),pmet(13), over_flag(6),decision_a(6),decision_b(6),smet(6),smet(38)); PE7：T_ACS52 port Map(bmet2,bmet1,pmet(14),pmet(15), over_flag(7),decision_a(7),decision_b(7),smet(7),smet(39)); PE8：T_ACS52 port Map(bmet3,bmet0,pmet(16),pmet(17), over_flag(8),decision_a(8),decision_b(8),smet(8),smet(40)); PE9：T_ACS52 port Map(bmet2,bmet1,pmet(18),pmet(19), over_flag(9),decision_a(9),decision_b(9),smet(9),smet(41)); PE10：T_ACS52 port Map(bmet3,bmet0,pmet(20),pmet(21), over_flag(10),decision_a(10),decision_b(10),smet(10),smet(42)); PE11：T_ACS52 port Map(bmet2,bmet1,pmet(22),pmet(23), over_flag(11),decision_a(11),decision_b(11),smet(11),smet(43)); PE12：T_ACS52 port Map(bmet0,bmet3,pmet(24),pmet(25), over_flag(12),decision_a(12),decision_b(12),smet(12),smet(44)); PE13：T_ACS52 port Map(bmet1,bmet2,pmet(26),pmet(27), over_flag(13),decision_a(13),decision_b(13),smet(13),smet(45)); PE14：T_ACS52 port Map(bmet0,bmet3,pmet(28),pmet(29), over_flag(14),decision_a(14),decision_b(14),smet(14),smet(46)); PE15：T_ACS52 port Map(bmet1,bmet2,pmet(30),pmet(31), over_flag(15),decision_a(15),decision_b(15),smet(15),smet(47)); PE16：T_ACS52 port Map(bmet2,bmet1,pmet(32),pmet(33), over_flag(16),decision_a(16),decision_b(16),smet(16),smet(48)); PE17：T_ACS52 port Map(bmet3,bmet0,pmet(34),pmet(35), over_flag(17),decision_a(17),decision_b(17),smet(17),smet(49)); PE18：T_ACS52 port Map(bmet2,bmet1,pmet(36),pmet(37), over_flag(18),decision_a(18),decision_b(18),smet(18),smet(50)); PE19：T_ACS52 port Map(bmet3,bmet0,pmet(38),pmet(39), over_flag(19),decision_a(19),decision_b(19),smet(19),smet(51)); PE20：T_ACS52 port Map(bmet1,bmet2,pmet(40),pmet(41), over_flag(20),decision_a(20),decision_b(20),smet(20),smet(52)); PE21：T_ACS52 port Map(bmet0,bmet3,pmet(42),pmet(43), over_flag(21),decision_a(21),decision_b(21),smet(21),smet(53)); PE22：T_ACS52 port Map(bmet1,bmet2,pmet(44),pmet(45), over_flag(22),decision_a(22),decision_b(22),smet(22),smet(54)); PE23：T_ACS52 port Map(bmet0,bmet3,pmet(46),pmet(47), over_flag(23),decision_a(23),decision_b(23),smet(23),smet(55)); PE24：T_ACS52 port Map(bmet1,bmet2,pmet(48),pmet(49), over_flag(24),decision_a(24),decision_b(24),smet(24),smet(56)); PE25：T_ACS52 port Map(bmet0,bmet3,pmet(50),pmet(51), over_flag(25),decision_a(25),decision_b(25),smet(25),smet(57)); PE26：T_ACS52 port Map(bmet1,bmet2,pmet(52),pmet(53), over_flag(26),decision_a(26),decision_b(26),smet(26),smet(58)); PE27：T_ACS52 port Map(bmet0,bmet3,pmet(54),pmet(55), over_flag(27),decision_a(27),decision_b(27),smet(27),smet(59)); PE28：T_ACS52 port Map(bmet2,bmet1,pmet(56),pmet(57), over_flag(28),decision_a(28),decision_b(28),smet(28),smet(60)); PE29：T_ACS52 port Map(bmet3,bmet0,pmet(58),pmet(59), over_flag(29),decision_a(29),decision_b(29),smet(29),smet(61)); PE30：T_ACS52 port Map(bmet2,bmet1,pmet(60),pmet(61), over_flag(30),decision_a(30),decision_b(30),smet(30),smet(62)); PE31：T_ACS52 port Map(bmet3,bmet0,pmet(62),pmet(63), over_flag(31),decision_a(31),decision_b(31),smet(31),smet(63)); …end process：…End of PE_ASSIGN 前記プログラムにおいて、T_ACS52はＡＳＩＣの設計時
のプロセシング要素の名前であり、pmetとsmetはそれぞ
れ経路メートルと状態メートルのことを示す。すなわ
ち、状態メートル(smet)は加算／比較／選択処理器のプ
ロセシング要素内で計算され出力される該状態が有する
メートルであり、前記状態メートルが次のクロックでは
経路メートル(pmet)として該プロセシング要素に印加さ
れる。例えば、０番目のプロセシング要素(ＰＥ０)の出
力値のうち一つの状態メートルは０番目のプロセシング
要素(ＰＥ０)の入力値のうち一つの経路メートルとして
入力され、出力値のうちもう一つの状態メートルは１６
番目のプロセシング要素(ＰＥ１６)の入力値のうち一つ
の経路メートルとして入力される。かつ、１番目のプロ
セシング要素(ＰＥ１)の出力値のうち一つの状態メート
ルは０番目のプロセシング要素(ＰＥ０)の入力値のうち
もう一つの経路メートルとして入力され、出力値のうち
もう一つの状態メートルは１６番目のプロセシング要素
(ＰＥ１６)の入力値のうちもう一つの経路メートルとし
て入力される。同じく、残りのプロセシング要素(ＰＥ
２〜ＰＥ３１)も前述したように相互複雑に連結されて
いる。
【００３６】一方、前記プログラムにおいて、各プロセ
シング要素の入力値を説明すると、ＰＥ０,ＰＥ２,ＰＥ
１２,ＰＥ１４,ＰＥ２１,ＰＥ２３,ＰＥ２７,ＰＥ２９
は共通的に(bmet0,bmet3)をブランチメートルとして用
い、ＰＥ１,ＰＥ３,ＰＥ１３,ＰＥ１５,ＰＥ２０,ＰＥ
２２,ＰＥ２４,ＰＥ２６は共通的に(bmet1,bmet2)をブ
ランチメートルとして用い、ＰＥ４,ＰＥ６,ＰＥ８,Ｐ
Ｅ１０,ＰＥ１７,ＰＥ１９,ＰＥ２９,ＰＥ３１は共通的
に(bmet3,bmet0)をブランチメートルとして用い、ＰＥ
５,ＰＥ７,ＰＥ９,ＰＥ１１,ＰＥ１６,ＰＥ１８,ＰＥ２
８,ＰＥ３０は共通的に(bmet2,bmet1)をブランチメート
ルとして用いる。すなわち、状態０,２,１２,１４,２
１,２３,２７,２９,３２,３４,４４,４６,５３,５５,５
７,５９は(bmet0,bmet3)を用い、状態１,３,１３,１５,
２０,２２,２４,２６,３３,３５,４５,４７,５２,５４,
５６,５８は(bmet1,bmet2)を用い、状態４,６,８,１０,
１７,１９,２９,３１,３６,３８,４０,４２,４９,５１,
６１,６３は(bmet3,bmet0)を用い、状態５,７,９,１１,
１６,１８,２８,３０,３７,３９,４１,４３,４８,５０,
６０,６２は(bmet2,bmet1)を用いる。
【００３７】本発明による加算／比較／選択処理器にお
いて、グルーピング部410ではグループ化単位を該シス
テムの動作最高速度とＡＳＩＣセルライブラリーの特性
に応じて決定する。例えば、チップのサイズが０.５ミ
クロンであるＡＳＩＣセルライブラリーを用い、動作最
高速度を８０ＭＨｚ以上に仮定する場合、(bmet0,bmet
3)を用いる八つのプロセシング要素を四つのグループ
に、(bmet1,bmet2)を用いる八つのプロセシング要素を
四つのグループに、(bmet3,bmet0)を用いる八つのプロ
セシング要素を四つのグループに、(bmet2,bmet1)を用
いる八つのプロセシング要素を四つのグループに束ね
る。
【００３８】多重化部420ではグルーピング部410でグル
ープ化された二単位のプロセシング要素の入力である四
つの６ビット経路メートルＰＡ０,ＰＡ１,ＰＢ０,ＰＢ
１を入力して、クロック信号(ＣＬＫ)に応じて経路メー
トルＰＡ０とＰＡ１又は経路メートルＰＢ０とＰＢ１を
選択して出力する。ここで、クロック信号(ＣＬＫ)は制
御部460から供給され、多重化部420の選択信号として動
作する。すなわち、クロック(ＣＬＫ)が“ハイ”論理レ
ベルの場合には経路メートルＰＡ０とＰＡ１が選択さ
れ、クロック(ＣＬＫ)が“ロー”論理レベルの場合には
経路メートルＰＢ０とＰＢ１が選択されてプロセシング
要素430に供給される。同じく、これと逆の場合も成り
立つ。
【００３９】プロセシング要素430では、多重化部420か
ら選択され出力された経路メートル(γX ,γY ＝ＰＡ
０,ＰＡ１又はＰＢ０,ＰＢ１)と、ブランチメートル生
成部100(図２参照)からのブランチメートル(λX ,λY )
を入力して、二つの判定ビット(すなわち、第１判定ビ
ットと第２判定ビット)と二つの状態メートルを出力す
る。前記プロセシング要素430では同一な状態メートル
を用いる二つの状態を処理するので、それぞれ二つずつ
の結果値が発生する。すなわち、経路メートルγXとブ
ランチメートルλX が加算された後に第１加算値が出力
され、経路メートルγY とブランチメートルλY が加算
された後に第２加算値が出力される。一方、経路メート
ルγX とブランチメートルλY が加算された後に第３加
算値が出力され、経路メートルγY とブランチメートル
λX が加算された後に第４加算値が出力される。第１加
算値と第２加算値、第３加算値と第４加算値はそれぞれ
比較された後、前記比較結果に応じて第１判定ビットと
第２判定ビットが“０”又は“１”で出力される。第１
判定ビット又は第２判定ビットはそれぞれの二つの加算
値のうち一つの加算値を選択する信号として用いられる
が、第１判定ビット又は第２判定ビットに応じて一つの
加算値が選択されて状態メートルとして出力される。
【００４０】第１逆多重化部440では、プロセシング要
素430から出力された第１判定ビットと第２判定ビット
を入力して、クロック信号(ＣＬＫ)に応じて逆多重化を
行い四つの判定ビット(ＤＡ０,ＤＡ１,ＤＢ０,ＤＢ１)
を出力する。すなわち、クロック信号(ＣＬＫ)が“ハ
イ”論理レベルである間に第１判定ビットと第２判定ビ
ットをＤＡ０とＤＡ１で出力し、“ロー”論理レベルで
ある間には第１判定ビットと第２判定ビットをＤＢ０と
ＤＢ１で出力する。同じく、これと逆の場合も成り立
つ。この際、一つのクロック周期当り出力された四つの
判定ビット(ＤＡ０,ＤＡ１,ＤＢ０,ＤＢ１)は次段の生
存メモリ部300(図２参照)に格納され、生存メモリ部300
では前記判定ビットを用いて元の情報シーケンスを復元
する。
【００４１】第２逆多重化部450では、プロセシング要
素430から出力された第１状態メートルと第２状態メー
トルを入力して、クロック信号(ＣＬＫ)に応じて逆多重
化を行い四つの状態メートル(ＳＡ０,ＳＡ１,ＳＢ０,Ｓ
Ｂ１)を出力する。すなわち、クロック信号(ＣＬＫ)が
“ハイ”論理レベルである間に第１状態メートルと第２
状態メートルをＳＡ０とＳＡ１で出力し、“ロー”論理
レベルである間に第１状態メートルと第２状態メートル
をＳＢ０とＳＢ１で出力する。同じく、これと逆の場合
も成り立つ。この際、一つのクロック周期当り出力され
た四つの状態メートル(ＳＡ０,ＳＡ１,ＳＢ０,ＳＢ１)
は対応するプロセシング要素に供給される。
【００４２】制御部460では、多重化部420、第１逆多重
化部440と第２逆多重化部450の動作を制御するためのク
ロック信号(ＣＬＫ)を生成して出力し、１クロック周期
当りの多重化部420と第１及び第２逆多重化部440,450の
動作回数を制御する。ここでは、クロック信号(ＣＬＫ)
の一周期当り２回の動作を行うように設定されたが、よ
り小さいＡＳＩＣセルライブラリー技術を用いたり又は
欧州のディジタル画像放送(ＤＶＢ)規格の８０ＭＨｚよ
り低い周波数で動作させる場合には４回以上の動作を行
うこともできる。
【００４３】結局、６４個の状態モードの場合、従来に
は同一な状態メートルを用いる二つの状態を一つのプロ
セシング要素で処理したため、３２個のプロセシング要
素が必要であったが、本発明によると、同一な状態メー
トルを用いる３２個のプロセシング要素に対して同一な
ブランチメートルを用いるプロセシング要素を二つの単
位でグループ化させることにより、１６個のプロセシン
グ要素のみが必要になり、ハードウエアの面積を５０％
程度縮められる。これは、単にプロセシング要素の数を
減らして面積を縮めたことではない。すなわち、ＡＳＩ
Ｃはセル領域と接続領域とから構成されるが、プロセシ
ング要素におけるブランチメートルの共有を通して接続
領域を大幅に減らしたものである。
【００４４】
【発明の効果】以上、本発明によると、Ｎ個の状態モー
ドの場合、同一な状態メートルを用いるＮ／２個のプロ
セシング要素に対して同一なブランチメートルを用いる
Ｌ個単位のプロセシング要素にグループ化させることに
より、Ｎ／２Ｌ個のプロセシング要素のみが必要にな
り、ＡＳＩＣに所要されるハードウエアの面積を著しく
縮めることができる。
【００４５】本発明は前記実施形態に限られず、本発明
が属した技術的思想内で当分野において通常の知識を有
する者により多くの変形が可能であることは明らかであ
る。
【図面の簡単な説明】
【図１】ビタビ復号化アルゴリズムに用いられるトレリ
ス図を示す図である。
【図２】一般的なビタビデコーダを示したブロック図で
ある。
【図３】図２に示された加算／比較／選択処理器を構成
するプロセシング要素を示したブロック図である。
【図４】ビタビデコーダにおいて本発明の一実施形態に
よる加算／比較／選択処理器を示したブロック図であ
る。
【符号の説明】
４１０ グルーピング部 ４２０ 多重化部 ４３０ プロセシング要素 ４４０ 第１逆多重化部 ４５０ 第２逆多重化部

Claims (5)

    【特許請求の範囲】
  1. 【請求項１】 重畳符号に対する最尤復号を行うための
    ビタビデコーダにおいて、 二つの経路メートルと二つのブランチメートルを入力し
    て、それぞれ加算した値を相互比較し、前記比較結果に
    応じる二つの判定ビットと二つの状態メートルを出力す
    るＮ個のプロセシング要素と、 Ｎ個の状態に対する前記Ｎ個のプロセシング要素を同一
    な状態メートルと同一なブランチメートルを用いるＫ単
    位のプロセシング要素にグループ化させるためのグルー
    ピング部と、 前記グルーピング結果に応じて供給されるＬ(ここで、
    Ｌは２Ｋ)個の経路メートルを所定のクロック信号に応
    じて二つの経路メートルに多重化して前記Ｎ個のプロセ
    シング要素のうち対応するプロセシング要素に出力する
    ための多重化部と、 前記対応するプロセシング要素から出力される二つの判
    定ビットを入力して、前記クロック信号に応じてＬ個の
    判定ビットに逆多重化して出力する第１逆多重化部と、 前記対応するプロセシング要素から出力される二つの状
    態メートルを入力して、前記クロック信号に応じてＬ個
    の状態メートルに逆多重化して出力する第２逆多重化部
    とを含むことを特徴とするビタビデコーダにおける加算
    ／比較／選択処理器。
  2. 【請求項２】 前記加算／比較／選択処理器は、前記ク
    ロック信号を発生させ、１クロック周期当り前記多重化
    部と前記第１及び第２逆多重化部の動作回数を制御する
    制御部を更に備えることを特徴とする請求項１に記載の
    ビタビデコーダにおける加算／比較／選択処理器。
  3. 【請求項３】 前記グルーピング部では全部で６４個の
    状態に対するグルーピング単位を四つの状態にすること
    を特徴とする請求項１に記載のビタビデコーダにおける
    加算／比較／選択処理器。
  4. 【請求項４】 前記多重化部では前記クロック信号の１
    クロック周期に対して、“ハイ”論理レベルである区間
    と“ロー”論理レベルである区間に応じて多重化が行わ
    れることを特徴とする請求項１に記載のビタビデコーダ
    における加算／比較／選択処理器。
  5. 【請求項５】 前記第１逆多重化部と第２逆多重化部で
    は前記クロック信号の１クロック周期に対して、“ハ
    イ”論理レベルである区間と“ロー”論理レベルである
    区間に応じて逆多重化が行われることを特徴とする請求
    項１に記載のビタビデコーダにおける加算／比較／選択
    処理器。
JP9226267A 1996-08-23 1997-08-22 ビタビデコーダにおける加算／比較／選択処理器 Pending JPH10200421A (ja)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
KR1019960035229A KR100195745B1 (ko) 1996-08-23 1996-08-23 비터비 복호화기의 가산 비교 선택 장치
KR1996-35229 1996-08-23

Publications (1)

Publication Number Publication Date
JPH10200421A true JPH10200421A (ja) 1998-07-31

Family

ID=19470598

Family Applications (1)

Application Number Title Priority Date Filing Date
JP9226267A Pending JPH10200421A (ja) 1996-08-23 1997-08-22 ビタビデコーダにおける加算／比較／選択処理器

Country Status (5)

Country Link
US (1) US5928378A (ja)
JP (1) JPH10200421A (ja)
KR (1) KR100195745B1 (ja)
CN (1) CN1183681A (ja)
GB (1) GB2316587A (ja)

Families Citing this family (26)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
EP0851591B1 (en) * 1996-12-24 2001-09-12 Matsushita Electric Industrial Co., Ltd. Data processor and data processing method
JP3338374B2 (ja) * 1997-06-30 2002-10-28 松下電器産業株式会社 演算処理方法および装置
US6070263A (en) * 1998-04-20 2000-05-30 Motorola, Inc. Circuit for use in a Viterbi decoder
US6219389B1 (en) * 1998-06-30 2001-04-17 Motorola, Inc. Receiver implemented decoding method of selectively processing channel state metrics to minimize power consumption and reduce computational complexity
US6343368B1 (en) 1998-12-18 2002-01-29 Telefonaktiebolaget Lm Ericsson (Publ) Method and system for fast maximum a posteriori decoding
JP2002533991A (ja) * 1998-12-18 2002-10-08 テレフォンアクチーボラゲット エル エム エリクソン（パブル） 高速帰納的最大復号化のための方法及び装置
DE19937506A1 (de) * 1999-08-09 2001-04-19 Infineon Technologies Ag ACS-Einheit für einen Viterbi-Decodierer
US6415415B1 (en) 1999-09-03 2002-07-02 Infineon Technologies North America Corp. Survival selection rule
US6333954B1 (en) * 1999-10-21 2001-12-25 Qualcomm Incorporated High-speed ACS for Viterbi decoder implementations
US6769090B1 (en) 2000-08-14 2004-07-27 Virata Corporation Unified technique for multi-rate trellis coding and decoding
EP1220455A1 (en) * 2000-12-29 2002-07-03 Motorola, Inc. Viterbi decoder, method and unit therefor
US6693975B2 (en) 2001-01-26 2004-02-17 Virata Corporation Low-order HDSL2 transmit filter
WO2003055195A2 (en) * 2001-12-18 2003-07-03 Globespan Virata Incorporated System and method for rate enhanced shdsl
US7127667B2 (en) * 2002-04-15 2006-10-24 Mediatek Inc. ACS circuit and viterbi decoder with the circuit
US7020223B2 (en) * 2002-04-16 2006-03-28 Intel Corporation Viterbi decoder and method using sequential two-way add-compare-select operations
GB2389020B (en) * 2002-05-23 2006-02-01 Ubinetics Ltd Blind transport format detection for transmission link
US7463702B2 (en) * 2002-11-12 2008-12-09 Agere Systems Inc. System and method for one-pass blind transport format detection
UA89162C2 (ru) * 2003-02-18 2010-01-11 Квелкомм Инкорпорейтед Команды мультиплексирования с кодовым разделением в мультиплексном канале с кодовым разделением
DE10310812B4 (de) * 2003-03-12 2007-11-22 Infineon Technologies Ag Dekodiervorrichtung, Trellis-Prozessor und Verfahren
US20040255230A1 (en) * 2003-06-10 2004-12-16 Inching Chen Configurable decoder
DE102004003096B3 (de) * 2004-01-21 2005-11-24 Infineon Technologies Ag Schaltung zur Durchführung der Add-Compare-Select-Operation mit darüber hinausgehender Funktionalität
US8185810B1 (en) * 2007-04-13 2012-05-22 Link—A—Media Devices Corporation Low power viterbi trace back architecture
US7847626B2 (en) * 2008-03-04 2010-12-07 Micron Technology, Inc. Structure and method for coupling signals to and/or from stacked semiconductor dies
CN101321035B (zh) * 2008-07-09 2012-03-21 上海华为技术有限公司 差值上限获取方法、定点方法及装置
TWI422165B (zh) * 2009-10-16 2014-01-01 Mstar Semiconductor Inc 解碼方法及其裝置
KR102025338B1 (ko) * 2011-12-28 2019-09-26 삼성전자 주식회사 신호 처리 장치, 이를 구비한 디스플레이 장치 및 신호 처리 방법

Family Cites Families (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5291499A (en) * 1992-03-16 1994-03-01 Cirrus Logic, Inc. Method and apparatus for reduced-complexity viterbi-type sequence detectors
US5414738A (en) * 1993-11-09 1995-05-09 Motorola, Inc. Maximum likelihood paths comparison decoder
US5530707A (en) * 1994-03-09 1996-06-25 At&T Corp. Area-efficient decoders for rate-k/n convolutional codes and other high rate trellis codes

Also Published As

Publication number Publication date
KR19980015791A (ko) 1998-05-25
KR100195745B1 (ko) 1999-06-15
GB9717810D0 (en) 1997-10-29
GB2316587A (en) 1998-02-25
US5928378A (en) 1999-07-27
CN1183681A (zh) 1998-06-03

Similar Documents

Publication Publication Date Title
JPH10200421A (ja) ビタビデコーダにおける加算／比較／選択処理器
US4905317A (en) Path memory control method in Viterbi decoder
EP0896436B1 (en) Viterbi decoder
US4606027A (en) Error correction apparatus using a Viterbi decoder
CN1099165C (zh) 维特比译码器
EP1102408B1 (en) Viterbi decoder
JP5618247B2 (ja) 複数ステップ・トレリスを使用するソフト出力ビタビ検出の方法および装置
JP2996615B2 (ja) ビタビ復号装置及びその方法
KR100212836B1 (ko) 비터비 디코더의 트레이스백 진행 구조
JP2000209106A (ja) 高速ビタビ復号器の最小量のメモリによる実現
KR100195741B1 (ko) 가변 레이트 비터비 복호화기
US5802115A (en) Convolution decoder using the Viterbi algorithm
KR0135796B1 (ko) 비터비복호기에서 트레이스백 수행장치
US7035356B1 (en) Efficient method for traceback decoding of trellis (Viterbi) codes
EP1089441A2 (en) Viterbi decoder and Viterbi decoding method
US6263473B1 (en) Viterbi decoder and Viterbi decoding method
JP2575854B2 (ja) ビタビ復号回路
EP1192719A1 (en) Viterbi decoder
KR20040031323A (ko) 비터비 복호기의 경로 메트릭 저장 장치 및 방법
KR100410995B1 (ko) 즉시역추적 알고리즘을 이용한 비터비 복호기용 생존경로메모리 관리 방법 및 그 장치
KR0148060B1 (ko) Viterbi 복호기의 ACS를 위한 메모리 최적 구조
US20100185925A1 (en) Differential Locally Updating Viterbi Decoder
JPH1056389A (ja) ビタビ復号器用パスメモリユニットおよび復号方法
KR100359805B1 (ko) 비터비 디코더 및 비터비 디코더의 디코딩 방법
JP2004120791A (ja) ビタビ復号器