JPH0420530B2 - - Google Patents
Info
- Publication number
- JPH0420530B2 JPH0420530B2 JP60073109A JP7310985A JPH0420530B2 JP H0420530 B2 JPH0420530 B2 JP H0420530B2 JP 60073109 A JP60073109 A JP 60073109A JP 7310985 A JP7310985 A JP 7310985A JP H0420530 B2 JPH0420530 B2 JP H0420530B2
- Authority
- JP
- Japan
- Prior art keywords
- data signal
- metric
- bit
- path metric
- circuit
- 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.)
- Expired - Lifetime
Links
Landscapes
- Error Detection And Correction (AREA)
Description
【発明の詳細な説明】
〔産業上の利用分野〕
この発明は、加算比較選択（ACS：Add−
Compare−Select）回路に係り、特に、例えばデ
イジタル通信装置で用いられるヴイタビ復号器に
含まれる加算比較選択回路に関するものである。
Compare−Select）回路に係り、特に、例えばデ
イジタル通信装置で用いられるヴイタビ復号器に
含まれる加算比較選択回路に関するものである。
通常、デイジタル通信装置で用いられるヴイタ
ビ復号器は、畳み込み符号化されたデータ系列を
受信して、最尤復号の手法によつてこれを復号
し、送信データを再生するものである。すなわ
ち、ヴイタビ復号器では、第１に、符号化の規則
を満足するようなすべての可能なデータ系列の中
から、受信データに基づいて判断して確からしい
と考えられる幾つかのデータ系列を残存パスとし
て選び、データを受信する度にこれらの残存パス
を更新しながら保存し続ける。第２に、データを
１シンボル受信する度に残存パスの中で最も確か
らしいものを選択して、この選択したパスから復
号データを１シンボルだけ出力する。このヴイタ
ビ復号器において、確からしさはパスメトリツク
で表現されるが、これは、データの１シンボルご
とに供給されるブランチメトリツクをデータ系列
のブランチに沿つて加算して得られるものであ
る。したがつて、ヴイタビ復号器では、保存され
ているパスメトリツクと受信データのブランチメ
トリツクとを幾つかの組み合わせで加算し、その
加算結果を比較して新しいパスメトリツクを選択
し、同時に、選択された新しいパスメトリツクの
中で最小のものを選択して最尤状態を決定すると
いう信号処理が行われる。
ビ復号器は、畳み込み符号化されたデータ系列を
受信して、最尤復号の手法によつてこれを復号
し、送信データを再生するものである。すなわ
ち、ヴイタビ復号器では、第１に、符号化の規則
を満足するようなすべての可能なデータ系列の中
から、受信データに基づいて判断して確からしい
と考えられる幾つかのデータ系列を残存パスとし
て選び、データを受信する度にこれらの残存パス
を更新しながら保存し続ける。第２に、データを
１シンボル受信する度に残存パスの中で最も確か
らしいものを選択して、この選択したパスから復
号データを１シンボルだけ出力する。このヴイタ
ビ復号器において、確からしさはパスメトリツク
で表現されるが、これは、データの１シンボルご
とに供給されるブランチメトリツクをデータ系列
のブランチに沿つて加算して得られるものであ
る。したがつて、ヴイタビ復号器では、保存され
ているパスメトリツクと受信データのブランチメ
トリツクとを幾つかの組み合わせで加算し、その
加算結果を比較して新しいパスメトリツクを選択
し、同時に、選択された新しいパスメトリツクの
中で最小のものを選択して最尤状態を決定すると
いう信号処理が行われる。
従来、加算比較選択回路（ACS回路）として
は、例えばA.Shenoy and P.Johnson、「Serial
implementation Of Viterbi decoders」
COMSAT Tech.Rev.、vol.13、pp.315〜330、
Fall、1983.に開示されたものが知られている。
第６図は従来のACS回路の一例を示すブロツク
構成図である。図において、１は受信データから
求めたブランチメトリツクλ、２はブランチメト
リツクλ1を蓄えておくブランチメトリツクレジ
スタ、３はブランチメトリツクレジスタ２から出
力されるブランチメトリツクλ、４は残存パスの
パスメトリツクΓを蓄えておくパスメトリツクレ
ジスタ、５はパスメトリツクレジスタ４から出力
されるパスメトリツクΓ、６はパスメトリツク
Γ5とブランチメトリツクλ3とから新しいパスメ
トリツクΓ′を作るACSユニツト、７は新しいパ
スメトリツクΓ′、８は新しいパスメトリツクΓ′7
の中で最小のパスメトリツクを検出する最小パス
メトリツク検出回路、９は最小パスメトリツク検
出回路８の出力である最小パスメトリツクΓnio、
１０はすべてのパスメトリツクΓ′7から最小パス
メトリツクΓnio９を減算する減算回路、１１は減
算回路１０の出力であるパスメトリツクΓ、１２
はパスメトリツクΓ11から最尤状態を選択する最
尤状態選択回路、１３は選択された最尤状態を表
わす最尤状態信号である。
は、例えばA.Shenoy and P.Johnson、「Serial
implementation Of Viterbi decoders」
COMSAT Tech.Rev.、vol.13、pp.315〜330、
Fall、1983.に開示されたものが知られている。
第６図は従来のACS回路の一例を示すブロツク
構成図である。図において、１は受信データから
求めたブランチメトリツクλ、２はブランチメト
リツクλ1を蓄えておくブランチメトリツクレジ
スタ、３はブランチメトリツクレジスタ２から出
力されるブランチメトリツクλ、４は残存パスの
パスメトリツクΓを蓄えておくパスメトリツクレ
ジスタ、５はパスメトリツクレジスタ４から出力
されるパスメトリツクΓ、６はパスメトリツク
Γ5とブランチメトリツクλ3とから新しいパスメ
トリツクΓ′を作るACSユニツト、７は新しいパ
スメトリツクΓ′、８は新しいパスメトリツクΓ′7
の中で最小のパスメトリツクを検出する最小パス
メトリツク検出回路、９は最小パスメトリツク検
出回路８の出力である最小パスメトリツクΓnio、
１０はすべてのパスメトリツクΓ′7から最小パス
メトリツクΓnio９を減算する減算回路、１１は減
算回路１０の出力であるパスメトリツクΓ、１２
はパスメトリツクΓ11から最尤状態を選択する最
尤状態選択回路、１３は選択された最尤状態を表
わす最尤状態信号である。
第７図は、第６図のACS回路に含まれる最小
パスメトリツク検出回路の一例を示すブロツク構
成図である。図において、１４ないし１７は４種
類のパスメトリツクΓ′（０）、…、Γ′(3)の入力端
子、４８は各パスメトリツクΓ′（０）とΓ′(1)とを
比較する比較器、４９は各パスメトリツクΓ′(2)と
Γ′(3)とを比較する比較器、５０は比較器４８の出
力信号によつて各パスメトリツクΓ′（０）とΓ′(1)
との小さい方を選択する選択器、５１は比較器４
９の出力信号によつて各パスメトリツクΓ′(2)と
Γ′(3)との小さい方を選択する選択器、５２は各選
択器５０と５１との出力を比較する比較器、５３
は比較器５２の出力信号によつて最小パスメトリ
ツクΓnio９を出力する選択器、５４は最小パスメ
トリツクΓnio９の出力端子である。
パスメトリツク検出回路の一例を示すブロツク構
成図である。図において、１４ないし１７は４種
類のパスメトリツクΓ′（０）、…、Γ′(3)の入力端
子、４８は各パスメトリツクΓ′（０）とΓ′(1)とを
比較する比較器、４９は各パスメトリツクΓ′(2)と
Γ′(3)とを比較する比較器、５０は比較器４８の出
力信号によつて各パスメトリツクΓ′（０）とΓ′(1)
との小さい方を選択する選択器、５１は比較器４
９の出力信号によつて各パスメトリツクΓ′(2)と
Γ′(3)との小さい方を選択する選択器、５２は各選
択器５０と５１との出力を比較する比較器、５３
は比較器５２の出力信号によつて最小パスメトリ
ツクΓnio９を出力する選択器、５４は最小パスメ
トリツクΓnio９の出力端子である。
次に、上記第６図に示す従来のACS回路の動
作について説明する。ブランチメトリツクレジス
タ２に蓄えられているブランチメトリツクλ3は、
パスメトリツクレジスタ４に蓄えられているパス
メトリツクΓ5と共にACSユニツト６に供給され
る。ACSユニツト６ではあらかじめ定められた
組み合わせにおいて、パスメトリツクΓ5とブラ
ンチメトリツクλ3とを加算して、新しいパスメ
トリツクのための候補を作り、これらの中から確
からしいパスを選択してパスメトリツクΓ′7を出
力する。
作について説明する。ブランチメトリツクレジス
タ２に蓄えられているブランチメトリツクλ3は、
パスメトリツクレジスタ４に蓄えられているパス
メトリツクΓ5と共にACSユニツト６に供給され
る。ACSユニツト６ではあらかじめ定められた
組み合わせにおいて、パスメトリツクΓ5とブラ
ンチメトリツクλ3とを加算して、新しいパスメ
トリツクのための候補を作り、これらの中から確
からしいパスを選択してパスメトリツクΓ′7を出
力する。
一例を挙げて、上記ACSユニツト６の機能を
より詳細に説明する。取り上げるのは
Ungerboeckの提案によるところの拘束長が３で
ある畳み込み符号の場合である。この時、00、
20、01、21、10、30、11、31として表現される８
つの状態に対応して８個の残存パスと、それらの
パスメトリツク｛Γ（00）、Γ（20）、Γ（01）、Γ
（21）、Γ（10）、Γ（30）、Γ（11）、Γ（31）｝が
存在
する。一方ブランチメトリツクにも８個のブラン
チメトリツク｛λ（０）、…、λ(7)｝が存在する。
ここで、新しいパスメトリツクΓ′（00）が作られ
る過程に注目する。最初に、４種類の加算が行わ
れて、Γ（00）＋λ（０）、Γ（20）＋λ(4)、Γ（01
）＋
λ(2)、Γ（21）＋λ(6)が作られ、次に、これらのう
ちの最小のものが選択されてΓ′（00）となる。そ
の他のパスメトリツクについても、同様な加算、
比較、及び選択が行われる。
より詳細に説明する。取り上げるのは
Ungerboeckの提案によるところの拘束長が３で
ある畳み込み符号の場合である。この時、00、
20、01、21、10、30、11、31として表現される８
つの状態に対応して８個の残存パスと、それらの
パスメトリツク｛Γ（00）、Γ（20）、Γ（01）、Γ
（21）、Γ（10）、Γ（30）、Γ（11）、Γ（31）｝が
存在
する。一方ブランチメトリツクにも８個のブラン
チメトリツク｛λ（０）、…、λ(7)｝が存在する。
ここで、新しいパスメトリツクΓ′（00）が作られ
る過程に注目する。最初に、４種類の加算が行わ
れて、Γ（00）＋λ（０）、Γ（20）＋λ(4)、Γ（01
）＋
λ(2)、Γ（21）＋λ(6)が作られ、次に、これらのう
ちの最小のものが選択されてΓ′（00）となる。そ
の他のパスメトリツクについても、同様な加算、
比較、及び選択が行われる。
以上のようにして作られた新しいパスメトリツ
クΓ′7は最小パスメトリツク検出回路８と減算回
路１０とに入力される。受信信号に雑音がない場
合には、通常はブランチメトリツクλ1には最小
のブランチメトリツクとして、その値が０に等し
いものが含まれており、その結果、パスメトリツ
クΓ′7にも最小のものとして、その値が０に等し
いものが含まれている。そして、この場合にはパ
スメトリツクΓ′7の最大のものも一定値を越えな
いことが分かつている。しかし、実際には受信信
号の雑音のためにブランチメトリツクλ1の最小
値は０より大きく、このことに起因してパスメト
リツクΓ′7は時間と共に除々に、そして限りなく
増加する傾向になる。最小パスメトリツク検出回
路８と減算回路１０とはこの現象を防止するため
に備えられている。最初に、最小パスメトリツク
検出回路８において、入力されるパスメトリツク
Γ′7のうちの最小値である最小パスメトリツク
Γnio９を検出して出力する。次に、減算回路１０
では、パスメトリツクΓ′7のすべてから一定値の
最小パスメトリツクΓnio９を減算する。こうして
作られるパスメトリツクΓ11においては、その最
小のものの値は０に等しくなる。なお、最小パス
メトリツク検出回路８を備えずに、パスメトリツ
クΓ′7のうちの任意のパスメトリツクをもつて最
小パスメトリツクΓnio９に代える手法が、例えば
特開昭59−19453号公報などによつて知られてい
る。この手法を用いる場合には、パスメトリツク
Γ11のうちの最小のものの値は必ずしも０とはな
らず、正、負、０のいずれの値をもとり得ること
となる。
クΓ′7は最小パスメトリツク検出回路８と減算回
路１０とに入力される。受信信号に雑音がない場
合には、通常はブランチメトリツクλ1には最小
のブランチメトリツクとして、その値が０に等し
いものが含まれており、その結果、パスメトリツ
クΓ′7にも最小のものとして、その値が０に等し
いものが含まれている。そして、この場合にはパ
スメトリツクΓ′7の最大のものも一定値を越えな
いことが分かつている。しかし、実際には受信信
号の雑音のためにブランチメトリツクλ1の最小
値は０より大きく、このことに起因してパスメト
リツクΓ′7は時間と共に除々に、そして限りなく
増加する傾向になる。最小パスメトリツク検出回
路８と減算回路１０とはこの現象を防止するため
に備えられている。最初に、最小パスメトリツク
検出回路８において、入力されるパスメトリツク
Γ′7のうちの最小値である最小パスメトリツク
Γnio９を検出して出力する。次に、減算回路１０
では、パスメトリツクΓ′7のすべてから一定値の
最小パスメトリツクΓnio９を減算する。こうして
作られるパスメトリツクΓ11においては、その最
小のものの値は０に等しくなる。なお、最小パス
メトリツク検出回路８を備えずに、パスメトリツ
クΓ′7のうちの任意のパスメトリツクをもつて最
小パスメトリツクΓnio９に代える手法が、例えば
特開昭59−19453号公報などによつて知られてい
る。この手法を用いる場合には、パスメトリツク
Γ11のうちの最小のものの値は必ずしも０とはな
らず、正、負、０のいずれの値をもとり得ること
となる。
このようにして作られたパスメトリツクΓ11は
分岐されて、その一方はパスメトリツクレジスタ
４にフイードバツクされて、その値を更新するの
に用いられ、他方は最尤状態選択回路１２に供給
される。最尤状態選択回路１２ではパスメトリツ
クΓ11のうちの最小のものを見い出して、それに
対応する状態信号を最尤状態信号１３として出力
する。
分岐されて、その一方はパスメトリツクレジスタ
４にフイードバツクされて、その値を更新するの
に用いられ、他方は最尤状態選択回路１２に供給
される。最尤状態選択回路１２ではパスメトリツ
クΓ11のうちの最小のものを見い出して、それに
対応する状態信号を最尤状態信号１３として出力
する。
次に、上記第７図に示す最小パスメトリツク検
出回路８の動作をより詳細に説明する。ここでは
簡単のために０、１、２、３として表現される４
つの状態が存在して、したがつてΓ′（０）、…、
Γ′(3)という４種類のパスメトリツクが存在する場
合を考える。比較器４８と選択器５０との組み合
わせにおいて、各パスメトリツクΓ′（０）とΓ′(1)
のうちでより小さいもの、すなわちMin｛Γ′（０）、
Γ′(1)｝が選択される。同様にして、比較器４９と
選択器５１との組み合わせではMin｛Γ′(2)、Γ′(3)
｝
が選択される。したがつて、比較器５２と選択器
５３との組み合わせから出力端子５４に出力され
る最小パスメトリツクΓnio９はMin｛Γ′（０）、
Γ′(1)、Γ′(2)、Γ′(3)｝、すなわち入力された４
個の
パスメトリツクのうちの最小のものである。
出回路８の動作をより詳細に説明する。ここでは
簡単のために０、１、２、３として表現される４
つの状態が存在して、したがつてΓ′（０）、…、
Γ′(3)という４種類のパスメトリツクが存在する場
合を考える。比較器４８と選択器５０との組み合
わせにおいて、各パスメトリツクΓ′（０）とΓ′(1)
のうちでより小さいもの、すなわちMin｛Γ′（０）、
Γ′(1)｝が選択される。同様にして、比較器４９と
選択器５１との組み合わせではMin｛Γ′(2)、Γ′(3)
｝
が選択される。したがつて、比較器５２と選択器
５３との組み合わせから出力端子５４に出力され
る最小パスメトリツクΓnio９はMin｛Γ′（０）、
Γ′(1)、Γ′(2)、Γ′(3)｝、すなわち入力された４
個の
パスメトリツクのうちの最小のものである。
上記のような従来のACS回路は以上のように
構成されているので、状態数が多く、したがつて
パスメトリツクの数が多い場合には、最小パスメ
トリツク検出回路８のハードウエアが増大するだ
けでなく、その信号処理時間が長くなるために、
パスメトリツクレジスタ４を含むパスメトリツク
のフイードバツクループが、高速のデータ伝送に
対応できないという問題点があつた。なお、最小
パスメトリツク検出回路８を備えずに、任意のパ
スメトリツクをもつて最小パスメトリツクに代え
る手法を採用すると、減算後のパスメトリツク
Γ11は負の値をとり得ることになり、フイードバ
ツクされて次の時刻にはパスメトリツクΓ5とし
てブランチメトリツクλ3と加算された結果が負
になることも起こり得る。従つて、この手法では
ACSユニツト６における加算処理及び比較処理
において正、負両方の数を扱う必要が生じるため
に、ACSユニツト６のハードウエア構成が煩雑
化し、その結果、ACSユニツト６のフイードバ
ツクループとを含む加算比較選択回路の全体の動
作速度が低下するという問題点があつた。
構成されているので、状態数が多く、したがつて
パスメトリツクの数が多い場合には、最小パスメ
トリツク検出回路８のハードウエアが増大するだ
けでなく、その信号処理時間が長くなるために、
パスメトリツクレジスタ４を含むパスメトリツク
のフイードバツクループが、高速のデータ伝送に
対応できないという問題点があつた。なお、最小
パスメトリツク検出回路８を備えずに、任意のパ
スメトリツクをもつて最小パスメトリツクに代え
る手法を採用すると、減算後のパスメトリツク
Γ11は負の値をとり得ることになり、フイードバ
ツクされて次の時刻にはパスメトリツクΓ5とし
てブランチメトリツクλ3と加算された結果が負
になることも起こり得る。従つて、この手法では
ACSユニツト６における加算処理及び比較処理
において正、負両方の数を扱う必要が生じるため
に、ACSユニツト６のハードウエア構成が煩雑
化し、その結果、ACSユニツト６のフイードバ
ツクループとを含む加算比較選択回路の全体の動
作速度が低下するという問題点があつた。
この発明は、かかる問題点を解決するためにな
されたもので、パスメトリツクの減算という信号
処理を簡略化して、簡単なハードウエア構成とな
し、高速のデータ伝送に対応できるACS回路を
得ることを目的とする。
されたもので、パスメトリツクの減算という信号
処理を簡略化して、簡単なハードウエア構成とな
し、高速のデータ伝送に対応できるACS回路を
得ることを目的とする。
この発明に係るACS回路は、最小パスメトリ
ツク検出回路の代わりにメトリツク発生回路を備
えて、そのメトリツク発生回路において、それぞ
れのパスメトリツクをあらかじめ一定の法則にし
たがつて変換しておき、その変換されたパスメト
リツクに簡単な論理演算を施して、パスメトリツ
クの最小値に近く、かつその最小値を越えないよ
うな値のメトリツクを発生することによつて、パ
スメトリツクからその最小値を見い出して、減算
するのとほとんど等価な信号処理をより簡単な論
理演算で実現するようにしたものである。
ツク検出回路の代わりにメトリツク発生回路を備
えて、そのメトリツク発生回路において、それぞ
れのパスメトリツクをあらかじめ一定の法則にし
たがつて変換しておき、その変換されたパスメト
リツクに簡単な論理演算を施して、パスメトリツ
クの最小値に近く、かつその最小値を越えないよ
うな値のメトリツクを発生することによつて、パ
スメトリツクからその最小値を見い出して、減算
するのとほとんど等価な信号処理をより簡単な論
理演算で実現するようにしたものである。
この発明のACS回路においては、パスメトリ
ツクから減算すべき一定値が簡単な論理演算によ
つて得られ、多く比較器や選択器を用いる必要が
ないために、パスメトリツクの減算のためのハー
ドウエア構成が簡単化され、同時に、その信号処
理時間が短縮され、ACS回路の動作速度が向上
する。
ツクから減算すべき一定値が簡単な論理演算によ
つて得られ、多く比較器や選択器を用いる必要が
ないために、パスメトリツクの減算のためのハー
ドウエア構成が簡単化され、同時に、その信号処
理時間が短縮され、ACS回路の動作速度が向上
する。
第１図はこの発明の一実施例であるACS回路
を示すブロツク構成図で、各符号１〜７，１０〜
１３は上記従来回路と同一のものである。図にお
いて、８ａはメトリツク発生回路、９ａはメトリ
ツク発生回路８ａの出力であるメトリツクΓnで
あり、その値はメトリツク発生回路８ａに入力さ
れるパスメトリツクΓ′7の最小のものの値に近く、
かつその値を越えない。
を示すブロツク構成図で、各符号１〜７，１０〜
１３は上記従来回路と同一のものである。図にお
いて、８ａはメトリツク発生回路、９ａはメトリ
ツク発生回路８ａの出力であるメトリツクΓnで
あり、その値はメトリツク発生回路８ａに入力さ
れるパスメトリツクΓ′7の最小のものの値に近く、
かつその値を越えない。
第２図は、第１図のACS回路に含まれるメト
リツク発生回路の一例を示すブロツク構成図であ
る。図において、１８〜２１はそれぞれのパスメ
トリツクのためのパスメトリツク変換回路、２２
は変換されたパスメトリツクの各桁ごとに論理演
算を施してメトリツクΓnを作る論理回路、２３
〜２７は論理積ゲート、２８は排他的論理和ゲー
ト、２９〜３２はメトリツクΓnの各ビツトのた
めの出力端子である。
リツク発生回路の一例を示すブロツク構成図であ
る。図において、１８〜２１はそれぞれのパスメ
トリツクのためのパスメトリツク変換回路、２２
は変換されたパスメトリツクの各桁ごとに論理演
算を施してメトリツクΓnを作る論理回路、２３
〜２７は論理積ゲート、２８は排他的論理和ゲー
ト、２９〜３２はメトリツクΓnの各ビツトのた
めの出力端子である。
第３図は、第２図のメトリツク発生回路に含ま
れるパスメトリツク変換回路を示す回路図であ
る。図において、３３〜３６は１つのパスメトリ
ツクΓ′(j)の各ビツトの入力端子、３７，３８，４
０は論理積ゲート、３９，４１〜４３は論理和ゲ
ート、４４〜４７は変換されたパスメトリツクＧ
(j)の各ビツトの出力端子である。
れるパスメトリツク変換回路を示す回路図であ
る。図において、３３〜３６は１つのパスメトリ
ツクΓ′(j)の各ビツトの入力端子、３７，３８，４
０は論理積ゲート、３９，４１〜４３は論理和ゲ
ート、４４〜４７は変換されたパスメトリツクＧ
(j)の各ビツトの出力端子である。
第４図は、第２図のメトリツク発生回路におけ
るメトリツクの発生過程を説明するための図であ
る。
るメトリツクの発生過程を説明するための図であ
る。
次に、上記第１図に示すこの発明の一実施例で
あるACS回路の動作について説明する。パスメ
トリツクΓ′7に基づいて、メトリツク発生回路８
ａではそれら各々から減算すべき値のメトリツク
Γn9aを出力する。ここで、メトリツクΓn9aの値
はパスメトリツクΓ′7の最小値に近く、かつその
最小値を越えない。
あるACS回路の動作について説明する。パスメ
トリツクΓ′7に基づいて、メトリツク発生回路８
ａではそれら各々から減算すべき値のメトリツク
Γn9aを出力する。ここで、メトリツクΓn9aの値
はパスメトリツクΓ′7の最小値に近く、かつその
最小値を越えない。
次に、上記第２図に示すメトリツク発生回路８
ａの動作をより詳細に説明する。ただし、ここで
は４個のパスメトリツクΓ′（０）、…、Γ′(3)が存
在
する場合を考え、かつそれぞれのパスメトリツク
は４ビツトの正値で表現されているものとする。
それぞれのパスメトリツクΓ′（０）、…、Γ′(3)は
、
まず、各パスメトリツク変換回路１８〜２１にお
いて一定の法則にしたがつて変換される。次い
で、論理回路２２において変換されたパスメトリ
ツクのそれぞれ桁ごとに論理演算が行われて、そ
の結果、メトリツクΓnが各出力端子２９〜３２
に出力される。
ａの動作をより詳細に説明する。ただし、ここで
は４個のパスメトリツクΓ′（０）、…、Γ′(3)が存
在
する場合を考え、かつそれぞれのパスメトリツク
は４ビツトの正値で表現されているものとする。
それぞれのパスメトリツクΓ′（０）、…、Γ′(3)は
、
まず、各パスメトリツク変換回路１８〜２１にお
いて一定の法則にしたがつて変換される。次い
で、論理回路２２において変換されたパスメトリ
ツクのそれぞれ桁ごとに論理演算が行われて、そ
の結果、メトリツクΓnが各出力端子２９〜３２
に出力される。
次に、上記第３図に示すパスメトリツク変換回
路の動作をより詳細に説明する。１つのパスメト
リツクをΓ′(j)＝（γ3、γ2、γ1、γ0）とし、変換
さ
れたパスメトリツクをＧ(j)＝（g3、g2、g1、g0）
とする。パスメトリツクΓ′(j)と変換されたパスメ
トリツクＧ(j)との各ビツトは、それぞれ各入力端
子３３〜３６と各出力端子４４〜４７とに与えら
れている。ここで、変換の法則は次の論理演算で
与えられる。
路の動作をより詳細に説明する。１つのパスメト
リツクをΓ′(j)＝（γ3、γ2、γ1、γ0）とし、変換
さ
れたパスメトリツクをＧ(j)＝（g3、g2、g1、g0）
とする。パスメトリツクΓ′(j)と変換されたパスメ
トリツクＧ(j)との各ビツトは、それぞれ各入力端
子３３〜３６と各出力端子４４〜４７とに与えら
れている。ここで、変換の法則は次の論理演算で
与えられる。
g3＝γ3・（γ2＋γ1γ0）
g2＝γ3＋γ2γ1γ0
g1＝γ3＋γ2＋γ1γ0
g0＝γ3＋γ2＋γ1＋γ0
したがつて、各パスメトリツクΓ′(j)とＧ(j)との
値を10進表現すると、次の関係である。
値を10進表現すると、次の関係である。
Ｇ（ｊ）＝
０、Γ′(j)＝０の時
１、Γ′(j)＝１、２の時
３、３≦Γ′(j)≦６の時
７、７≦Γ′(j)≦10の時
15、11≦Γ′(j)≦15の時
が成立する。
変換されたパスメトリツクＧ(j)の２進表現は、
その上位数ビツトが０の連読であり、その下位数
ビツトが１の連続であるという特長を有する。し
たがつて、変換されたパスメトリツクＧ(j)のうち
の最小のものの値は、すべてのＧ(j)の各桁のビツ
トについて論理積をとることによつて容易に決定
できる。ただし、11≦Γ′(j)≦15の時には、Ｇ(j)の
値がΓ′(j)の値よりも大きいので、このことを論理
演算に反映させておく必要がある。論理回路２２
はこのような論理演算を行つてメトリツクΓnを
作る。
その上位数ビツトが０の連読であり、その下位数
ビツトが１の連続であるという特長を有する。し
たがつて、変換されたパスメトリツクＧ(j)のうち
の最小のものの値は、すべてのＧ(j)の各桁のビツ
トについて論理積をとることによつて容易に決定
できる。ただし、11≦Γ′(j)≦15の時には、Ｇ(j)の
値がΓ′(j)の値よりも大きいので、このことを論理
演算に反映させておく必要がある。論理回路２２
はこのような論理演算を行つてメトリツクΓnを
作る。
第４図は、各パスメトリツクΓ′（０）、…、Γ′(3
)
の最小値のパスメトリツクΓ′(j)に対して、変換さ
れたパスメトリツクＧ(j)とメトリツクΓn、及び
減算結果Γ′(j)−Γnの関係を示したものである。
第４図に示す表から明らかなように、減算結果
Γ′(j)−Γnの値は４を越えない。また、最小のパ
スメトリツクの初期値が０であり、かつブランチ
メトリツクの最大値が７であれば、この実施例に
よるACS回路において、上記減算結果の最小値
は３を越えないことが分かる。実際に、最悪ケー
スとして、最小のパスに対応するブランチメトリ
ツクの値が６、７、７、７、…であれば、最小の
パスメトリツクはΓ＝０から出発して、順次にΓ
＋λ−Γn＝０＋６−３＝３、３＋７−７＝３、
３＋７−７＝３、３＋７−７＝３、…となる。こ
のように、この発明によるメトリツク発生回路８
ａは、減算回路１０と組み合わせてパスメトリツ
クΓ11の値が時間と共に限りなく増大する現象を
防止して、パスメトリツクを小さな値に保つてお
くことができるという点において、上記従来例の
最小パスメトリツク検出回路８と同等の機能を行
う。
)
の最小値のパスメトリツクΓ′(j)に対して、変換さ
れたパスメトリツクＧ(j)とメトリツクΓn、及び
減算結果Γ′(j)−Γnの関係を示したものである。
第４図に示す表から明らかなように、減算結果
Γ′(j)−Γnの値は４を越えない。また、最小のパ
スメトリツクの初期値が０であり、かつブランチ
メトリツクの最大値が７であれば、この実施例に
よるACS回路において、上記減算結果の最小値
は３を越えないことが分かる。実際に、最悪ケー
スとして、最小のパスに対応するブランチメトリ
ツクの値が６、７、７、７、…であれば、最小の
パスメトリツクはΓ＝０から出発して、順次にΓ
＋λ−Γn＝０＋６−３＝３、３＋７−７＝３、
３＋７−７＝３、３＋７−７＝３、…となる。こ
のように、この発明によるメトリツク発生回路８
ａは、減算回路１０と組み合わせてパスメトリツ
クΓ11の値が時間と共に限りなく増大する現象を
防止して、パスメトリツクを小さな値に保つてお
くことができるという点において、上記従来例の
最小パスメトリツク検出回路８と同等の機能を行
う。
以上の説明から明らかなように、この発明の
ACS回路におけるメトリツク発生回路８ａは、
従来例の最小パスメトリツク検出回路８と同等の
機能をより簡単な論理演算によつて実現するもの
である。このことは、メトリツク発生回路８ａが
最小パスメトリツク検出回路８よりも簡単なハー
ドウエアで実現できるだけでなく、その信号処理
時間がより短く、したがつてACS回路の高速動
作に対応し得ることを示している。このことは、
状態数が多く、パスメトリツクの数が多い場合に
は、さらに顕著となる。例えば、上記第７図に示
す最小パスメトリツク検出回路において、パスメ
トリツクが４個の場合には、比較器と選択器との
組み合わせは３個で良く、パスメトリツクの入力
端子から最小パスメトリツクの出力端子に至るま
でには比較器と選択器をそれぞれ２回だけ通過す
れば良い。しかし、パスメトリツクが16個となる
と、比較器と選択器との組み合わせは15個必要と
なり、また、パスメトリツクの入力端子から最小
パスメトリツクの出力端子に至るまでには比較器
と選択器をそれぞれ４回通過しなければならず、
このために信号処理時間が増大する。これに対し
て、第２図に示すメトリツク発生回路において
は、状態数が増加しても、これに対応してそれぞ
れのパスメトリツクのためにパスメトリツク変換
回路を備えておけば良く、このために信号処理時
間は状態数にはほとんど依存しない。
ACS回路におけるメトリツク発生回路８ａは、
従来例の最小パスメトリツク検出回路８と同等の
機能をより簡単な論理演算によつて実現するもの
である。このことは、メトリツク発生回路８ａが
最小パスメトリツク検出回路８よりも簡単なハー
ドウエアで実現できるだけでなく、その信号処理
時間がより短く、したがつてACS回路の高速動
作に対応し得ることを示している。このことは、
状態数が多く、パスメトリツクの数が多い場合に
は、さらに顕著となる。例えば、上記第７図に示
す最小パスメトリツク検出回路において、パスメ
トリツクが４個の場合には、比較器と選択器との
組み合わせは３個で良く、パスメトリツクの入力
端子から最小パスメトリツクの出力端子に至るま
でには比較器と選択器をそれぞれ２回だけ通過す
れば良い。しかし、パスメトリツクが16個となる
と、比較器と選択器との組み合わせは15個必要と
なり、また、パスメトリツクの入力端子から最小
パスメトリツクの出力端子に至るまでには比較器
と選択器をそれぞれ４回通過しなければならず、
このために信号処理時間が増大する。これに対し
て、第２図に示すメトリツク発生回路において
は、状態数が増加しても、これに対応してそれぞ
れのパスメトリツクのためにパスメトリツク変換
回路を備えておけば良く、このために信号処理時
間は状態数にはほとんど依存しない。
なお、上記実施例では、メトリツク発生回路８
ａの出力であるメトリツクΓn9aを、パスメトリ
ツクΓ′7から減算するようにACS回路を構成した
場合について説明したが、高速のデータ伝送に対
応する目的で、この発明の出願人が先に出願した
ACS回路の構成と合わせて、第５図に示すよう
に、ブランチメトリツクλ1からメトリツクΓn9a
の値を、減算回路１０ａによつて減算してブラン
チメトリツクレジスタ２ａに供給し、このブラン
チメトリツクレジスタ２ａからブランチメトリツ
クλ3aを出力するようにしても良く、上記実施例
と同様の効果を奏する。
ａの出力であるメトリツクΓn9aを、パスメトリ
ツクΓ′7から減算するようにACS回路を構成した
場合について説明したが、高速のデータ伝送に対
応する目的で、この発明の出願人が先に出願した
ACS回路の構成と合わせて、第５図に示すよう
に、ブランチメトリツクλ1からメトリツクΓn9a
の値を、減算回路１０ａによつて減算してブラン
チメトリツクレジスタ２ａに供給し、このブラン
チメトリツクレジスタ２ａからブランチメトリツ
クλ3aを出力するようにしても良く、上記実施例
と同様の効果を奏する。
この発明は以上説明したとおり、ACS回路に
おいて、最小パスメトリツク検出回路の代わりに
メトリツク発生回路を備えて、最小パスメトリツ
クの値に近く、かつその値を越えないような一定
値を簡単な論理演算によつて発生するように構成
したので、状態数の多い場合にも、この種の従来
例のACS回路と比べて、ハードウエア構成が簡
単にできると共に、高速のデータ伝送に容易に対
応できるACS回路が得られるという優れた効果
を奏するものである。
おいて、最小パスメトリツク検出回路の代わりに
メトリツク発生回路を備えて、最小パスメトリツ
クの値に近く、かつその値を越えないような一定
値を簡単な論理演算によつて発生するように構成
したので、状態数の多い場合にも、この種の従来
例のACS回路と比べて、ハードウエア構成が簡
単にできると共に、高速のデータ伝送に容易に対
応できるACS回路が得られるという優れた効果
を奏するものである。
第１図はこの発明の一実施例であるACS回路
を示すブロツク構成図、第２図は、第１図の
ACS回路に含まれるメトリツク発生回路の一例
を示すブロツク構成図、第３図は、第２図のメト
リツク発生回路に含まれるパスメトリツク変換回
路を示す回路図、第４図は、第２図のメトリツク
発生回路におけるメトリツクの発生過程を説明す
るための図、第５図はこの発明の他の実施例であ
るACS回路を示すブロツク構成図、第６図は従
来のACS回路の一例を示すブロツク構成図、第
７図は、第６図のACS回路に含まれる最小パス
メトリツク検出回路の一例を示すブロツク構成図
である。 図において、１，３，３ａ……ブランチメトリ
ツクλ、２，２ａ……ブランチメトリツクレジス
タ、４……パスメトリツクレジスタ、５，１１…
…パスメトリツクΓ、６……ACSユニツト、７
……減算される以前のパスメトリツクΓ′、８……
最小パスメトリツク検出回路、８ａ……メトリツ
ク発生回路、９……最小パスメトリツクΓnio、９
ａ……メトリツクΓn、１０，１０ａ……減算回
路、１２……最尤状態選択回路、１３……最尤状
態信号、１４〜１７……パスメトリツクΓ′の入力
端子、１８〜２１……パスメトリツク変換回路、
２２……論理回路、２３〜２７，３７，３８，４
０……論理積ゲート、２８……排他的論理和ゲー
ト、２９〜３２……メトリツクΓnの各ビツトの
出力端子、３３〜３６……パスメトリツクΓ′(j)の
各ビツトの入力端子、３９，４１〜４３……論理
和ゲート、４４〜４７……変換されたパスメトリ
ツクＧ(j)の各ビツトの出力端子、４８，４９，５
２……比較器、５０，５１，５３……選択器、５
４……最小パスメトリツクΓnioの出力端子であ
る。 なお、各図中、同一符号は同一、又は相当部分
を示す。
を示すブロツク構成図、第２図は、第１図の
ACS回路に含まれるメトリツク発生回路の一例
を示すブロツク構成図、第３図は、第２図のメト
リツク発生回路に含まれるパスメトリツク変換回
路を示す回路図、第４図は、第２図のメトリツク
発生回路におけるメトリツクの発生過程を説明す
るための図、第５図はこの発明の他の実施例であ
るACS回路を示すブロツク構成図、第６図は従
来のACS回路の一例を示すブロツク構成図、第
７図は、第６図のACS回路に含まれる最小パス
メトリツク検出回路の一例を示すブロツク構成図
である。 図において、１，３，３ａ……ブランチメトリ
ツクλ、２，２ａ……ブランチメトリツクレジス
タ、４……パスメトリツクレジスタ、５，１１…
…パスメトリツクΓ、６……ACSユニツト、７
……減算される以前のパスメトリツクΓ′、８……
最小パスメトリツク検出回路、８ａ……メトリツ
ク発生回路、９……最小パスメトリツクΓnio、９
ａ……メトリツクΓn、１０，１０ａ……減算回
路、１２……最尤状態選択回路、１３……最尤状
態信号、１４〜１７……パスメトリツクΓ′の入力
端子、１８〜２１……パスメトリツク変換回路、
２２……論理回路、２３〜２７，３７，３８，４
０……論理積ゲート、２８……排他的論理和ゲー
ト、２９〜３２……メトリツクΓnの各ビツトの
出力端子、３３〜３６……パスメトリツクΓ′(j)の
各ビツトの入力端子、３９，４１〜４３……論理
和ゲート、４４〜４７……変換されたパスメトリ
ツクＧ(j)の各ビツトの出力端子、４８，４９，５
２……比較器、５０，５１，５３……選択器、５
４……最小パスメトリツクΓnioの出力端子であ
る。 なお、各図中、同一符号は同一、又は相当部分
を示す。
Claims (1)
- 【特許請求の範囲】 １ 入力された複数個から成る第１のデータ信号
と、既に入力された前記第１のデータ信号に基づ
いて作られている第２のデータ信号とに対して、
加算、比較、及び選択の信号処理を行つて第３の
データ信号を作り、この第３のデータ信号に減算
操作を行つて第４のデータ信号を作り、この第４
のデータ信号と前記第２のデータ信号とを置換し
て、この第２のデータ信号の内容を更新すると共
に、前記第４のデータ信号のうちで最小値を持つ
ものを選択する回路において、前記減算操作にお
ける前記第３のデータ信号から減算すべき一定値
として、この第３のデータ信号のうちの最小値に
近く、かつその最小値を越えないような一定値を
論理演算によつて発生する手段を設けることによ
つて、前記減算操作の結果が常に零以上となるよ
うにしたことを特徴とする加算比較選択回路。 ２ 前記第３のデータ信号から一定値を得る手段
として、この第３のデータ信号をあらかじめ一定
の法則にしたがつて変換する手段と、この変換さ
れた第３のデータ信号の各桁のビツトの論理積を
とつて１つの第５のデータ信号を作る手段と、こ
の第５のデータ信号の最上位の２ビツトの論理積
によつて第６のデータ信号の最上位ビツトを作る
手段と、それらの排他的論理和によつて前記第６
のデータ信号の次の上位ビツトを作る手段と、以
下の桁については前記第５のデータ信号の各ビツ
トを前記第６のデータ信号の各ビツトとする手段
を備え、また、前記第６のデータ信号を前記の一
定値とする手段を備えたことを特徴とする特許請
求の範囲第１項記載の加算比較選択回路。 ３ 前記の一定の法則として、１つの前記第３の
データ信号が４ビツトで構成されている場合、こ
の第３のデータ信号の下位の２ビツトの論理積で
得られる第１のビツトを作る手段と、前記第３の
データ信号の上位から２番目のビツトと前記第１
のビツトとの論理積及び論理和を作つて、これら
をそれぞれ第２のビツト及び第３のビツトとする
手段と、この第３のビツトと前記第３のデータ信
号の最上位ビツトとの論理積及び論理和を作つ
て、これらをそれぞれ第７のデータ信号の最上位
ビツト及びその最上位ビツトから３番目のビツト
とする手段と、前記第２のビツトと前記第３のデ
ータ信号の最上位ビツトとの論理和を作つて前記
第７のデータ信号の上位から２番目のビツトとす
る手段と、前記第３のデータ信号のすべてのビツ
トの論理和を前記第７のデータ信号の最下位ビツ
トとする手段とを有することにより、前記第３の
データ信号に対する変換手段を備えたことを特徴
とする特許請求の範囲第２項記載の加算比較選択
回路。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP7310985A JPS61230430A (ja) | 1985-04-04 | 1985-04-04 | 加算比較選択回路 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP7310985A JPS61230430A (ja) | 1985-04-04 | 1985-04-04 | 加算比較選択回路 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPS61230430A JPS61230430A (ja) | 1986-10-14 |
| JPH0420530B2 true JPH0420530B2 (ja) | 1992-04-03 |
Family
ID=13508787
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP7310985A Granted JPS61230430A (ja) | 1985-04-04 | 1985-04-04 | 加算比較選択回路 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPS61230430A (ja) |
Families Citing this family (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2563961B2 (ja) * | 1988-03-03 | 1996-12-18 | 三菱電機株式会社 | ビタビ復号器 |
| EP0682414B1 (en) * | 1993-11-29 | 2001-11-21 | Oki Electric Industry Company, Limited | Device for estimating soft judgement value and device for estimating maximum likelihood system |
Family Cites Families (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS5919453A (ja) * | 1982-07-23 | 1984-01-31 | Nec Corp | メトリツク演算回路 |
-
1985
- 1985-04-04 JP JP7310985A patent/JPS61230430A/ja active Granted
Also Published As
| Publication number | Publication date |
|---|---|
| JPS61230430A (ja) | 1986-10-14 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US4606027A (en) | Error correction apparatus using a Viterbi decoder | |
| US5715470A (en) | Arithmetic apparatus for carrying out viterbi decoding at a high speed | |
| JP3285354B2 (ja) | 最大値探索回路 | |
| US4614933A (en) | Viterbi decoder with the pipeline processing function | |
| US5446746A (en) | Path memory apparatus of a viterbi decoder | |
| JPH10107651A (ja) | ビタビ復号装置 | |
| JPH0453128B2 (ja) | ||
| US5150369A (en) | High-speed convolutional decoder | |
| US6070263A (en) | Circuit for use in a Viterbi decoder | |
| US5617089A (en) | Huffman code decoding circuit | |
| JPH0316046B2 (ja) | ||
| US6792570B2 (en) | Viterbi decoder with high speed processing function | |
| JP3259725B2 (ja) | ビタビ復号装置 | |
| JPH0420530B2 (ja) | ||
| US7225393B2 (en) | Viterbi decoder and Viterbi decoding method | |
| JP3987153B2 (ja) | マンハッタンあるいはハミングメトリックスキームに基づくビタビデコーダのための信号のデコード | |
| JPS63299412A (ja) | シ−ケンシャル復号装置 | |
| JPH03154521A (ja) | 軟判定復号情報出力機能付ビタビ復号器 | |
| JP3191442B2 (ja) | ビタビ復号用演算装置 | |
| KR100268831B1 (ko) | 고속 처리 가변 길이 코덱 장치 | |
| JP3235333B2 (ja) | ビタビ復号方法およびビタビ復号化装置 | |
| KR100531840B1 (ko) | 비터비 디코더의 가지 메트릭 계산 방법 및 그 회로 | |
| JPH0510850B2 (ja) | ||
| JP3351414B2 (ja) | ビタビ復号装置 | |
| KR100210385B1 (ko) | 트렐리스 디코더 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| LAPS | Cancellation because of no payment of annual fees |