JPS638652B2 - - Google Patents
Info
- Publication number
- JPS638652B2 JPS638652B2 JP57128453A JP12845382A JPS638652B2 JP S638652 B2 JPS638652 B2 JP S638652B2 JP 57128453 A JP57128453 A JP 57128453A JP 12845382 A JP12845382 A JP 12845382A JP S638652 B2 JPS638652 B2 JP S638652B2
- Authority
- JP
- Japan
- Prior art keywords
- metric
- path
- circuit
- memory
- update
- 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
Links
Landscapes
- Error Detection And Correction (AREA)
Description
【発明の詳細な説明】
本発明はビタビ復号器、特に複数の候補パタン
の選択を時分割処理で行なうビタビ復号器の最適
パス判定回路に関する。
の選択を時分割処理で行なうビタビ復号器の最適
パス判定回路に関する。
従来、ビタビ復号器は畳み込み符号を復号する
のに最もパフオーマンスの良い復号器として知ら
れているが反面ハードウエアの規模が大きくなる
という欠点がる。例えば良く用いられる符号化率
１／２の畳み込み符号で符号器の拘束長をＫとする
と、ビタビ復号器では常に2K―1個の候補パタン
を考えその候補パタンと受信系列を比較してパス
メトリツクといわれる相関値を計算し新たな候補
パタンを選択しているため、パス・メトリツクの
計算と候補パタンを記憶するメモリ（これは通常
パス・メモリと呼ばれる）には2K―1個の回路が
必要となる。この回路を小さくするために上述の
2K―1個の回路のうち同じ処理をする部分を単一
の回路で置き換え時分割処理することで回路規模
を小さくする方式が考えられている。この時分割
処理をするビタビ復号器においては、判定出力は
最適パス判定回路によつて得られる。最適パス判
定回路では、全ての候補パタンに対する処理の終
了後に対応するパス・メトリツクが最大のパタン
を選択しそのパタンの最終ビツトを判定出力とし
ている。しかし、この方式では候補パタンの選択
の他に判定出力を得るための動作が加わるため一
定時間内に処理すべき動作数が増す、いいかえる
と信号の処理速度が遅れるという欠点があつた。
のに最もパフオーマンスの良い復号器として知ら
れているが反面ハードウエアの規模が大きくなる
という欠点がる。例えば良く用いられる符号化率
１／２の畳み込み符号で符号器の拘束長をＫとする
と、ビタビ復号器では常に2K―1個の候補パタン
を考えその候補パタンと受信系列を比較してパス
メトリツクといわれる相関値を計算し新たな候補
パタンを選択しているため、パス・メトリツクの
計算と候補パタンを記憶するメモリ（これは通常
パス・メモリと呼ばれる）には2K―1個の回路が
必要となる。この回路を小さくするために上述の
2K―1個の回路のうち同じ処理をする部分を単一
の回路で置き換え時分割処理することで回路規模
を小さくする方式が考えられている。この時分割
処理をするビタビ復号器においては、判定出力は
最適パス判定回路によつて得られる。最適パス判
定回路では、全ての候補パタンに対する処理の終
了後に対応するパス・メトリツクが最大のパタン
を選択しそのパタンの最終ビツトを判定出力とし
ている。しかし、この方式では候補パタンの選択
の他に判定出力を得るための動作が加わるため一
定時間内に処理すべき動作数が増す、いいかえる
と信号の処理速度が遅れるという欠点があつた。
本発明の目的は上述の従来のビタビ復号器の最
適パス判定回路の欠点を取り除き、全ての候補パ
タンに対する処理が終了すると同時に判定出力の
得られる最適パス判定回路を得ることにある。
適パス判定回路の欠点を取り除き、全ての候補パ
タンに対する処理が終了すると同時に判定出力の
得られる最適パス判定回路を得ることにある。
本発明によれば受信信号と複数の受信候補信号
との相関を計算する相関回路と、該相関回路出力
を用いて時分割処理によつて複数の受信パタンに
対応した複数のパスメトリツク値を更新するとと
もにパス選択情報を出力するメトリツク更新回路
と、前記パス選択情報に基いて、時分割処理によ
つて複数の復号候補パタンを選択するパスメモリ
とから構成されるビタビ復号器において、前記メ
トリツク更新回路で順次得られる新たなメトリツ
ク値の各時点での最大値を記憶する最大メトリツ
ク・メモリと、該最大メトリツク・メモリと新た
に得られたメトリツク値を比較し新たに得られた
メトリツク値がより大きい場合には最大メトリツ
クの内容を更新する最大値更新パルスを送出する
比較回路と、前記最大値更新パルスが到着したと
きの順次選択される前記パスメモリの最終ビツト
を記憶する判定出力記憶回路から構成され、前記
パルスメモリが全てのパスに対して更新された時
点での判定出力記憶回路の内容を最適パスによる
復号結果として出力することを特徴としたビタビ
復号器の最適パス判定回路を提供することができ
る。
との相関を計算する相関回路と、該相関回路出力
を用いて時分割処理によつて複数の受信パタンに
対応した複数のパスメトリツク値を更新するとと
もにパス選択情報を出力するメトリツク更新回路
と、前記パス選択情報に基いて、時分割処理によ
つて複数の復号候補パタンを選択するパスメモリ
とから構成されるビタビ復号器において、前記メ
トリツク更新回路で順次得られる新たなメトリツ
ク値の各時点での最大値を記憶する最大メトリツ
ク・メモリと、該最大メトリツク・メモリと新た
に得られたメトリツク値を比較し新たに得られた
メトリツク値がより大きい場合には最大メトリツ
クの内容を更新する最大値更新パルスを送出する
比較回路と、前記最大値更新パルスが到着したと
きの順次選択される前記パスメモリの最終ビツト
を記憶する判定出力記憶回路から構成され、前記
パルスメモリが全てのパスに対して更新された時
点での判定出力記憶回路の内容を最適パスによる
復号結果として出力することを特徴としたビタビ
復号器の最適パス判定回路を提供することができ
る。
以下説明の都合上まずビタビ復号法について詳
細に説明し、その後本発明と従来の回路との違い
について説明する。
細に説明し、その後本発明と従来の回路との違い
について説明する。
第１図は畳み込み符号器の実施例を示すブロツ
ク図である。第１図の畳み込み符号器は拘束長
３、符号化率1/2の符号器を構成している。入力
端子１００から入力された１又は０の信号はレジ
スタ１および２に順次蓄えられる。入力信号とレ
ジスタ１の内容と、レジスタ２の内容の２を法と
した加算が排他論理和３で求められ、出力端子１
０１から出力される。また入力信号とレジスタ２
の２を法とした加算が排他論理和４で求められ出
力端子１０２から出力される。このようにして１
ビツトの入力信号が２ビツトに変換されて送信さ
れる。出力の２ビツトはレジスタ１および２の内
容と入力信号で決定されるのでこの符号器の状態
遷移図は第２図のようになる。第２図で４つの状
態（00）、（10）、（01）、（11）はそれぞれレジスタ
１，２の内部状態に対応しておりそれぞれの状態
と次の状態を結ぶ線は入力信号の値によつて次に
異つた状態に移ることを意味している。また結線
上の（00）、（11）、（10）、（01）の表現は端子１０
１および端子１０２から出力される値を表現して
いる。例えばレジスタ１，２の初期値が（０，
０）であつて信号“１”が入力されたとすると出
力は（１，１）となりレジスタ１，２の状態は
（１，０）に変わる。
ク図である。第１図の畳み込み符号器は拘束長
３、符号化率1/2の符号器を構成している。入力
端子１００から入力された１又は０の信号はレジ
スタ１および２に順次蓄えられる。入力信号とレ
ジスタ１の内容と、レジスタ２の内容の２を法と
した加算が排他論理和３で求められ、出力端子１
０１から出力される。また入力信号とレジスタ２
の２を法とした加算が排他論理和４で求められ出
力端子１０２から出力される。このようにして１
ビツトの入力信号が２ビツトに変換されて送信さ
れる。出力の２ビツトはレジスタ１および２の内
容と入力信号で決定されるのでこの符号器の状態
遷移図は第２図のようになる。第２図で４つの状
態（00）、（10）、（01）、（11）はそれぞれレジスタ
１，２の内部状態に対応しておりそれぞれの状態
と次の状態を結ぶ線は入力信号の値によつて次に
異つた状態に移ることを意味している。また結線
上の（00）、（11）、（10）、（01）の表現は端子１０
１および端子１０２から出力される値を表現して
いる。例えばレジスタ１，２の初期値が（０，
０）であつて信号“１”が入力されたとすると出
力は（１，１）となりレジスタ１，２の状態は
（１，０）に変わる。
第２図にはこれに続いて１，０，１と信号が入
力されたときの状態の変化を太線で示す。このよ
うに各データ系列に１対１に対応して状態遷移図
上の折線が形成される。この折線のことを通常パ
スと呼んでいる。ビタビ復号器は各パスに対応し
た送信系列と、受信系列の相関を計算し、相関の
最大になるパスを判定して復号を行つている。受
信系列と各パスとの相関は通常パス・メトリツク
と呼ばれている。ビタビ復号器は第２図の４通り
の状態に対応するパス・メトリツクを記憶してお
き、１ビツトの情報に対応する２シンボルが受信
される毎にパス・メトリツクを更新する。
力されたときの状態の変化を太線で示す。このよ
うに各データ系列に１対１に対応して状態遷移図
上の折線が形成される。この折線のことを通常パ
スと呼んでいる。ビタビ復号器は各パスに対応し
た送信系列と、受信系列の相関を計算し、相関の
最大になるパスを判定して復号を行つている。受
信系列と各パスとの相関は通常パス・メトリツク
と呼ばれている。ビタビ復号器は第２図の４通り
の状態に対応するパス・メトリツクを記憶してお
き、１ビツトの情報に対応する２シンボルが受信
される毎にパス・メトリツクを更新する。
第２図から明らかなように、４通りの各状態は
送信信号に対応して２本の枝を出し再び４通りの
いずれかの状態になる。新たな状態の側から見れ
ば、以前の状態のうち２つの状態から異つた符号
を送信した結果として新たな状態が得られてい
る。例えば（１，０）という状態は（０，０）と
いう状態に“１”が加えられて（１，１）を出力
し（１，０）に達する場合と（０，１）という状
態に“１”が加えられて（０，０）を出力し
（１，０）に達する場合とがある。今ｋ番目のデ
ータに対応するビタビ復号器ではこの２通りの場
合について前回のパス・メトリツク値に受信信号
と各枝に対応する受信候補信号との相関を加え、
大きい方を新たなパス・メトリツクとするという
方法でパス・メトリツクの更新を行なう。このパ
ス・メトリツクの更新動作をより詳しく説明す
る。
送信信号に対応して２本の枝を出し再び４通りの
いずれかの状態になる。新たな状態の側から見れ
ば、以前の状態のうち２つの状態から異つた符号
を送信した結果として新たな状態が得られてい
る。例えば（１，０）という状態は（０，０）と
いう状態に“１”が加えられて（１，１）を出力
し（１，０）に達する場合と（０，１）という状
態に“１”が加えられて（０，０）を出力し
（１，０）に達する場合とがある。今ｋ番目のデ
ータに対応するビタビ復号器ではこの２通りの場
合について前回のパス・メトリツク値に受信信号
と各枝に対応する受信候補信号との相関を加え、
大きい方を新たなパス・メトリツクとするという
方法でパス・メトリツクの更新を行なう。このパ
ス・メトリツクの更新動作をより詳しく説明す
る。
今ｋ番目のデータに対応するパス・メトリツク
を今の状態に合せて kM0０， kM10， kM01， k
M11，と表現し、ｋ＋１番目の２ビツトの受信信
号と各枝に対応した２ビツトの受信候補信号との
相関を受信候補信号をi1，i2としたときに k+1
Ri1,i2と表現したとするとｋ＋１番目のパスメト
リツク k+1M10は kM00＋ k+1R11と kM01＋ k+1
R00の大きい方となる。従つて k+1M00， k+1
M10， k+1M01， k+1M11を式で表現すると k+1M00＝Max（ kM00＋ k+1R00， kM01＋ k+1R
11） k+1M10＝Max（ kM00＋ k+1R11， kM01＋ k+1R00） k+1M01＝Max（ kM10＋ k+1R10， kM11＋ k+1R01） k+1M01＝Max（ kM10＋ k+1R10， kM11＋ k+1R01） k+1M11＝Max（ kM10＋ k+1R01， kM11＋ k+1R10）
(1) となる。２本の枝のうち、どちらを選択したか
でどのようなパスをとつたかがわかるのでその選
択信号をもとにビタビ復号器は常に４通りのパス
を記憶してゆく。このパスを記憶する回路は通常
パス・メモリと呼ばれる。
を今の状態に合せて kM0０， kM10， kM01， k
M11，と表現し、ｋ＋１番目の２ビツトの受信信
号と各枝に対応した２ビツトの受信候補信号との
相関を受信候補信号をi1，i2としたときに k+1
Ri1,i2と表現したとするとｋ＋１番目のパスメト
リツク k+1M10は kM00＋ k+1R11と kM01＋ k+1
R00の大きい方となる。従つて k+1M00， k+1
M10， k+1M01， k+1M11を式で表現すると k+1M00＝Max（ kM00＋ k+1R00， kM01＋ k+1R
11） k+1M10＝Max（ kM00＋ k+1R11， kM01＋ k+1R00） k+1M01＝Max（ kM10＋ k+1R10， kM11＋ k+1R01） k+1M01＝Max（ kM10＋ k+1R10， kM11＋ k+1R01） k+1M11＝Max（ kM10＋ k+1R01， kM11＋ k+1R10）
(1) となる。２本の枝のうち、どちらを選択したか
でどのようなパスをとつたかがわかるのでその選
択信号をもとにビタビ復号器は常に４通りのパス
を記憶してゆく。このパスを記憶する回路は通常
パス・メモリと呼ばれる。
第３図はパス・メモリに記憶されるパスの例を
示す図である。第３図には選択されたパスのみが
記されている。第３図において時刻Ａにおいてパ
ス・メモリに記憶されている全てのパスを逆にた
どると時刻Ｂ以前の部分は全て同一のパスに帰着
していることがわかる。従つて今後どのような信
号が受信されようと時刻Ｂ以前のパス（太線の部
分）から外れることはあり得ない。この現象はマ
ージと言われるが、マージが起れば、それ以前に
受信された系列は一意的に決定されるのでこれか
ら判定出力を得ることができる。一般にマージン
するまでのパスの長さは伝送路誤りのパタンによ
つて異り、誤りパタンによつては無限にマージン
しない場合もあり得る。現実の回路では無限の長
さのパスを記憶することは不可能なのでどこかで
パスの長さを打切ることになる。この場合には４
本のパスがマージンしないうちに判定をしなくて
はならない場合が生じる。パスがマージンしてな
いときの判定誤りを少なするには現在（判定時
刻）で最も確からしいパスを正しいパスとする方
法が用いられる。従つて通常のビタビ復号器では
一定長のパスメモリを用い、各判定時刻で最大の
パス・メトリツクを持つパスの最も前のシンボル
に対応する値を判定出力としている。
示す図である。第３図には選択されたパスのみが
記されている。第３図において時刻Ａにおいてパ
ス・メモリに記憶されている全てのパスを逆にた
どると時刻Ｂ以前の部分は全て同一のパスに帰着
していることがわかる。従つて今後どのような信
号が受信されようと時刻Ｂ以前のパス（太線の部
分）から外れることはあり得ない。この現象はマ
ージと言われるが、マージが起れば、それ以前に
受信された系列は一意的に決定されるのでこれか
ら判定出力を得ることができる。一般にマージン
するまでのパスの長さは伝送路誤りのパタンによ
つて異り、誤りパタンによつては無限にマージン
しない場合もあり得る。現実の回路では無限の長
さのパスを記憶することは不可能なのでどこかで
パスの長さを打切ることになる。この場合には４
本のパスがマージンしないうちに判定をしなくて
はならない場合が生じる。パスがマージンしてな
いときの判定誤りを少なするには現在（判定時
刻）で最も確からしいパスを正しいパスとする方
法が用いられる。従つて通常のビタビ復号器では
一定長のパスメモリを用い、各判定時刻で最大の
パス・メトリツクを持つパスの最も前のシンボル
に対応する値を判定出力としている。
第４図は従来のビタビ復号器の一構成例を示す
ブロツク図である。第４図のビタビ復号器は式(1)
の４通りのパス・メトリツクの更新を時分割処理
で実現している。
ブロツク図である。第４図のビタビ復号器は式(1)
の４通りのパス・メトリツクの更新を時分割処理
で実現している。
入力端子１０３，１０４からは２シンボルの受
信信号が入力され相関回路５へ入力される。一
方、受信候補信号は端子１０６から入力される高
速クロツクに基いて生成されるアドレス・発生回
路９で作られるアドレス信号に基いてリード・オ
ンリ・メモリROM６から受信候補信号を読み出
す。アドレス・発生回路９の出力は第２図の４通
りの状態のいずれかに対応している。状態が決る
とそれに対応した候補信号が決まりROM６から
受信候補信号が出力される。相関回路５では受信
シンボルと受信候補信号をビツト毎に比較し、一
致していれば“１”を加え一致していなければ
“１”を減ずる。従つて相関回路の出力は＋２，
０，−２のいずれかになる。これがRi1,i2に相当す
る。メトリツク更新回路はランダム・アクセス・
メモリ（RAM）で構成され式(1)のM00，M10，
M01，M11を記憶するメトリツク・メモリ８と式
(1)の加算および比較を行う演算回路７で構成され
ている。メトリツク・メモリではアドレス発生回
路９で生成されるアドレス信号に基いてメトリツ
ク・メモリ８から kMj1,j2が読出され相関回路５
からの k+1Ri1,i2との加算および比較が演算回路７
で行なわれる。式(1)より書き込みアドレスは読出
しアドレスとは異つたものにしなくてはならな
い。書込みアドレスは書込みアドレス生成器１０
で生成される。読出しアドレスと書込みアドレス
は異つているため式１内の４式を上から順に実行
してゆくと下の方の式を実行するときにはメトリ
ツク・メモリの内容が既に書き換えられたものに
なつてしまつている場合が生じる。これを避ける
ために、２組のメトリツク・メモリを用いてある
時点では第１のメトリツク・メモリから読出して
第２のメトリツク・メモリへ書込み次のシンボル
を復号するときには第２のメトリツク・メモリか
ら読出して第１のメトリツク・メモリへ書込む、
というように交互に読出しと書込みを繰り返すよ
うになつている。このメモリ切換信号は端子１０
５から入力される。演算回路７はパス・メトリツ
クを更新すると同時にどちらのパスが選択される
かというパス選択信号を出力する。パス・メモリ
は状態数だけのパスを記憶している必要があるた
めワード数が状態数でワード長がパスの長さに相
当するRAMで構成される。RAMの各ワードに
はそのアドレスに対応する状態に達するパスに相
当した復号結果が記憶されている。パス・メモリ
もメモリ切換信号により切換えられる２つのメモ
リを有している。例として第３図の時刻Ｃにおけ
るパスの内容を示す。今、パス・メモリ長は４と
する。状態（０，０）に達するパスは常に状態
（０，０）を経ている。従つてこのパスに相当す
るワードは（０，０，０，０）である。（左側が
古い状態に対応している）状態（１，０）に達す
るパスは状態（０，０）から状態（１，０）に最
後で変つている。これは信号としては０が続いて
最後に１が来たことに相当する。従つてこのパス
は（０，０，０，１）と表現される。状態（０，
１）に達するパスは状態（０，０）から状態
（１，０）を経て状態（０，１）に達している。
このパスは（０，０，１，０）となる。最後に状
態（１，１）は状態（０，０）から状態（１，
０）を経て状態（１，１）に達している。従つて
このパスは（０，０，１，１）となる。
信信号が入力され相関回路５へ入力される。一
方、受信候補信号は端子１０６から入力される高
速クロツクに基いて生成されるアドレス・発生回
路９で作られるアドレス信号に基いてリード・オ
ンリ・メモリROM６から受信候補信号を読み出
す。アドレス・発生回路９の出力は第２図の４通
りの状態のいずれかに対応している。状態が決る
とそれに対応した候補信号が決まりROM６から
受信候補信号が出力される。相関回路５では受信
シンボルと受信候補信号をビツト毎に比較し、一
致していれば“１”を加え一致していなければ
“１”を減ずる。従つて相関回路の出力は＋２，
０，−２のいずれかになる。これがRi1,i2に相当す
る。メトリツク更新回路はランダム・アクセス・
メモリ（RAM）で構成され式(1)のM00，M10，
M01，M11を記憶するメトリツク・メモリ８と式
(1)の加算および比較を行う演算回路７で構成され
ている。メトリツク・メモリではアドレス発生回
路９で生成されるアドレス信号に基いてメトリツ
ク・メモリ８から kMj1,j2が読出され相関回路５
からの k+1Ri1,i2との加算および比較が演算回路７
で行なわれる。式(1)より書き込みアドレスは読出
しアドレスとは異つたものにしなくてはならな
い。書込みアドレスは書込みアドレス生成器１０
で生成される。読出しアドレスと書込みアドレス
は異つているため式１内の４式を上から順に実行
してゆくと下の方の式を実行するときにはメトリ
ツク・メモリの内容が既に書き換えられたものに
なつてしまつている場合が生じる。これを避ける
ために、２組のメトリツク・メモリを用いてある
時点では第１のメトリツク・メモリから読出して
第２のメトリツク・メモリへ書込み次のシンボル
を復号するときには第２のメトリツク・メモリか
ら読出して第１のメトリツク・メモリへ書込む、
というように交互に読出しと書込みを繰り返すよ
うになつている。このメモリ切換信号は端子１０
５から入力される。演算回路７はパス・メトリツ
クを更新すると同時にどちらのパスが選択される
かというパス選択信号を出力する。パス・メモリ
は状態数だけのパスを記憶している必要があるた
めワード数が状態数でワード長がパスの長さに相
当するRAMで構成される。RAMの各ワードに
はそのアドレスに対応する状態に達するパスに相
当した復号結果が記憶されている。パス・メモリ
もメモリ切換信号により切換えられる２つのメモ
リを有している。例として第３図の時刻Ｃにおけ
るパスの内容を示す。今、パス・メモリ長は４と
する。状態（０，０）に達するパスは常に状態
（０，０）を経ている。従つてこのパスに相当す
るワードは（０，０，０，０）である。（左側が
古い状態に対応している）状態（１，０）に達す
るパスは状態（０，０）から状態（１，０）に最
後で変つている。これは信号としては０が続いて
最後に１が来たことに相当する。従つてこのパス
は（０，０，０，１）と表現される。状態（０，
１）に達するパスは状態（０，０）から状態
（１，０）を経て状態（０，１）に達している。
このパスは（０，０，１，０）となる。最後に状
態（１，１）は状態（０，０）から状態（１，
０）を経て状態（１，１）に達している。従つて
このパスは（０，０，１，１）となる。
ここで時刻Ｃから時刻Ａに移つたときのパスの
変化からパス・メモリがどのように更新されるか
を説明する。まずアドレス発生回路９では状態
（０，０）と状態（０，１）に相当するアドレス
（０，０）と状態（０，１）に相当するアドレス
（０，０）と（０，１）を出力するROM６では
このアドレスに基いて受信候補信号（０，０）と
（１，１）を相関回路５へ出力し、相関回路５で
は k+1R00と k+1R11を計算する。一方メトリツ
ク・メモリ８ではアドレス（０，０）と（０，
１）に基いて、 kM00と kM01を読出す。演算回
路では相関回路５の出力とメトリツク・メモリ８
の出力から式(1)の１行目の式を計算する。第３図
は kM00＋ k+1R00が大きかつたため、 k+1M00＝
kM00＋ k+1R00となりパス選択信号としては
（０，０）を選択したことを示す“０”が出る。
パス・メモリではアドレス・レジスタ１１にアド
レス（０，０）と（０，１）を記憶しておきパス
選択信号に基いてアドレス（０，０）が選択され
る。このアドレスに基いてRAM１２から状態
（０，０）に相当するパス（０，０，０，０）が
読み出されシフト・レジスタ１３で１ビツト左へ
シフトされて、最も右には新ビツト生成回路１４
によつて生成される新たなビツトが入力される。
k+1M00が求まつたため書込みアドレス生成器
１０によつて決まる書込みアドレス（０，０）へ
は k+1M00が書込まれ、パス・メモリのRAM１
２へもアドレス（０，０）に（０，０，０，０）
が書込まれる。式(1)を上から順に実行してゆくと
すると、書込みアドレスは（０，０）、（１，０）、
（０，１）、（１，１）に順に変わる。同様にして
ｋ＋１M10には kM00＋ k+1R11が書き込まれRAM１
２のアドレス（１，０）にはアドレス（０，０）
の内容（０，０，０，０）を１ビツト左へシフト
して右端へ“１”を入れ（０，０，０，１）とな
る。また k+1M01には kM10＋ k+1R10が書込まれ、
RAM１２のアドレス（０，１）はアドレス
（１，０）の内容（０，０，０，１）を１ビツト
左へシフトして右端へ“０”を入れ（０，０，
０，１）となる。最後に k+1M11には kM11＋ k+1
R10が書込まれ、RAM１２のアドレス（１，１）
はアドレス（１，１）の内容（０，０，１，１，）
を１ビツト左へシフトして右端へ“１”を入れ
（０，１，１，１）となる。本実施例では右端へ
入れるべき最新ビツトは書込みアドレスの左側の
ビツトになつている。
変化からパス・メモリがどのように更新されるか
を説明する。まずアドレス発生回路９では状態
（０，０）と状態（０，１）に相当するアドレス
（０，０）と状態（０，１）に相当するアドレス
（０，０）と（０，１）を出力するROM６では
このアドレスに基いて受信候補信号（０，０）と
（１，１）を相関回路５へ出力し、相関回路５で
は k+1R00と k+1R11を計算する。一方メトリツ
ク・メモリ８ではアドレス（０，０）と（０，
１）に基いて、 kM00と kM01を読出す。演算回
路では相関回路５の出力とメトリツク・メモリ８
の出力から式(1)の１行目の式を計算する。第３図
は kM00＋ k+1R00が大きかつたため、 k+1M00＝
kM00＋ k+1R00となりパス選択信号としては
（０，０）を選択したことを示す“０”が出る。
パス・メモリではアドレス・レジスタ１１にアド
レス（０，０）と（０，１）を記憶しておきパス
選択信号に基いてアドレス（０，０）が選択され
る。このアドレスに基いてRAM１２から状態
（０，０）に相当するパス（０，０，０，０）が
読み出されシフト・レジスタ１３で１ビツト左へ
シフトされて、最も右には新ビツト生成回路１４
によつて生成される新たなビツトが入力される。
k+1M00が求まつたため書込みアドレス生成器
１０によつて決まる書込みアドレス（０，０）へ
は k+1M00が書込まれ、パス・メモリのRAM１
２へもアドレス（０，０）に（０，０，０，０）
が書込まれる。式(1)を上から順に実行してゆくと
すると、書込みアドレスは（０，０）、（１，０）、
（０，１）、（１，１）に順に変わる。同様にして
ｋ＋１M10には kM00＋ k+1R11が書き込まれRAM１
２のアドレス（１，０）にはアドレス（０，０）
の内容（０，０，０，０）を１ビツト左へシフト
して右端へ“１”を入れ（０，０，０，１）とな
る。また k+1M01には kM10＋ k+1R10が書込まれ、
RAM１２のアドレス（０，１）はアドレス
（１，０）の内容（０，０，０，１）を１ビツト
左へシフトして右端へ“０”を入れ（０，０，
０，１）となる。最後に k+1M11には kM11＋ k+1
R10が書込まれ、RAM１２のアドレス（１，１）
はアドレス（１，１）の内容（０，０，１，１，）
を１ビツト左へシフトして右端へ“１”を入れ
（０，１，１，１）となる。本実施例では右端へ
入れるべき最新ビツトは書込みアドレスの左側の
ビツトになつている。
第４図の実施例ではシフト・レジスタ１３でシ
フトして出される左端のビツトを復号結果として
いる。これは第３図の例のようにパス・メモリの
長さ以内でマージンしている場合には良いがマー
ジンしていない場合には判定結果が定まらず正し
い復号ができない。この誤りを減少させるために
は書き込まれた新たなメトリツクのうちの最大メ
トリツクの書込みアドレスを記憶しておきこの最
大メトリツクのアドレスの左端のビツトを判定出
力とする方法がある。しかし、この方法を用いる
と式(1)に対応する４通りの計算が終了した後で再
びアドレスを設定して読み出さねばならないた
め、シンボル周期内で実行する演算数が増大し回
路の高速化が要求される。いいかえると、同じ回
路でも適用可能なビツトレートの最大値が小さく
なる。本発明ではこれを避けかつ最大メトリツク
のアドレスのパスから読み出す回路を実現する。
フトして出される左端のビツトを復号結果として
いる。これは第３図の例のようにパス・メモリの
長さ以内でマージンしている場合には良いがマー
ジンしていない場合には判定結果が定まらず正し
い復号ができない。この誤りを減少させるために
は書き込まれた新たなメトリツクのうちの最大メ
トリツクの書込みアドレスを記憶しておきこの最
大メトリツクのアドレスの左端のビツトを判定出
力とする方法がある。しかし、この方法を用いる
と式(1)に対応する４通りの計算が終了した後で再
びアドレスを設定して読み出さねばならないた
め、シンボル周期内で実行する演算数が増大し回
路の高速化が要求される。いいかえると、同じ回
路でも適用可能なビツトレートの最大値が小さく
なる。本発明ではこれを避けかつ最大メトリツク
のアドレスのパスから読み出す回路を実現する。
次に図面を参照して本発明について詳細に説明
する。
する。
第５図は本発明の一実施例を示すブロツク図で
ある。入力端子１１０からは第４図のメトリツク
更新回路の出力として得られる更新されたメトリ
ツク値、つまりメトリツク・メモリ８への書込み
データ１０８が入力される。式(1)に基いた演算が
始まると、まず入力端子１０５からのモード切換
信号で最大メトリツク・メモリ２１が初期設定さ
れる。新たなメトリツク値が入力端子１１０から
入力されると比較器２０で最大メトリツク・メモ
リの値と新たなメトリツク値とが比較され、比較
器２０は新たなメトリツク値の方が大きい場合に
のみ最大値更新パルスである書込みパルスを最大
メトリツク・メモリ２１へ出力し、端子１１０か
らの入力を最大メトリツク・メモリへ書込む。こ
のようにすれば式(1)の演算をメトリツク更新回路
が終了する時点ではメトリツク・メモリの最大値
が最大メトリツクに記憶される。比較器２０の出
力の最大値更新パルスは同時に判定出力記憶回路
２２へのラツチ信号として供給されている。入力
端子１１１は第４図の端子１０７に接続されてお
り、第４図のシフト・レジスタ１３の最終出力が
入力される。判定出力記憶回路２２はラツチ回路
で実現され、最大値更新パルスが到着したときの
端子１１１からの値を記憶している。こうする
と、式(1)の全ての演算が終了したときの判定出力
記憶回路の内容は最後に最大値更新パルスが出力
されたときのパス・メモリの最終ビツトつまりメ
トリツクが最大のときのパス・メモリの最終ビツ
トが記憶されることになり、パスがマージしてい
ないときにも、誤り率の小さい判定結果を得るこ
とができる。
ある。入力端子１１０からは第４図のメトリツク
更新回路の出力として得られる更新されたメトリ
ツク値、つまりメトリツク・メモリ８への書込み
データ１０８が入力される。式(1)に基いた演算が
始まると、まず入力端子１０５からのモード切換
信号で最大メトリツク・メモリ２１が初期設定さ
れる。新たなメトリツク値が入力端子１１０から
入力されると比較器２０で最大メトリツク・メモ
リの値と新たなメトリツク値とが比較され、比較
器２０は新たなメトリツク値の方が大きい場合に
のみ最大値更新パルスである書込みパルスを最大
メトリツク・メモリ２１へ出力し、端子１１０か
らの入力を最大メトリツク・メモリへ書込む。こ
のようにすれば式(1)の演算をメトリツク更新回路
が終了する時点ではメトリツク・メモリの最大値
が最大メトリツクに記憶される。比較器２０の出
力の最大値更新パルスは同時に判定出力記憶回路
２２へのラツチ信号として供給されている。入力
端子１１１は第４図の端子１０７に接続されてお
り、第４図のシフト・レジスタ１３の最終出力が
入力される。判定出力記憶回路２２はラツチ回路
で実現され、最大値更新パルスが到着したときの
端子１１１からの値を記憶している。こうする
と、式(1)の全ての演算が終了したときの判定出力
記憶回路の内容は最後に最大値更新パルスが出力
されたときのパス・メモリの最終ビツトつまりメ
トリツクが最大のときのパス・メモリの最終ビツ
トが記憶されることになり、パスがマージしてい
ないときにも、誤り率の小さい判定結果を得るこ
とができる。
このようにすれば判定出力は式(1)の演算終了と
同時に得られるもので回路の動作速度を特に上げ
る必要もない。
同時に得られるもので回路の動作速度を特に上げ
る必要もない。
以上記したように本発明によれば受信信号と複
数の受信候補信号との相関を計算する相関回路
と、該相関回路出力を用いて時分割処理よつて複
数の受信パタンに対応した複数のパスメトリツク
値を更新するとともにパス選択情報を出力するメ
トリツク更新回路と、前記パス選択情報に基いて
時分割処理によつて複数の復号候補パタンを選択
するパスメモリとから構成されるビタビ復号器に
おいてパスがマージしない場合にも誤り率が小さ
くしかも回路の動作速度に余裕のある最適パス判
定回路を得ることができる。
数の受信候補信号との相関を計算する相関回路
と、該相関回路出力を用いて時分割処理よつて複
数の受信パタンに対応した複数のパスメトリツク
値を更新するとともにパス選択情報を出力するメ
トリツク更新回路と、前記パス選択情報に基いて
時分割処理によつて複数の復号候補パタンを選択
するパスメモリとから構成されるビタビ復号器に
おいてパスがマージしない場合にも誤り率が小さ
くしかも回路の動作速度に余裕のある最適パス判
定回路を得ることができる。
第１図は畳み込み符号器の例を示すブロツク
図、第２図は畳み込み符号の構造を示す状態遷移
図、第３図はビタビ復号器の内部状態を示す図、
第４図は従来のビタビ復号器の実施例を示すブロ
ツク図である。第５図は本発明の一実施例を示す
ブロツク図で、参照数字２０，２１，２２はそれ
ぞれ比較回路、最大メトリツク・メモリ、判定出
力記憶回路を示す。
図、第２図は畳み込み符号の構造を示す状態遷移
図、第３図はビタビ復号器の内部状態を示す図、
第４図は従来のビタビ復号器の実施例を示すブロ
ツク図である。第５図は本発明の一実施例を示す
ブロツク図で、参照数字２０，２１，２２はそれ
ぞれ比較回路、最大メトリツク・メモリ、判定出
力記憶回路を示す。
Claims (1)
- １ 受信信号と複数の受信候補信号との相関を計
算する相関回路と、該相関回路出力を用いて時分
割処理によつて複数の受信パタンに対応した複数
のパスメトリツク値を更新するとともにパス選択
情報を出力するメトリツク更新回路と、前記パス
選択情報に基いて、時分割処理によつて複数の復
号候補パタンを選択するパスメモリとから構成さ
れるビタビ復号器において、前記メトリツク更新
回路で順次得られる新たなメトリツク値の各時点
での最大値を記憶する最大メトリツク・メモリ
と、該最大メトリツク・メモリと新たに得られた
メトリツク値を比較し新たに得られたメトリツク
値がより大きい場合には最大メトリツクの内容を
更新する最大値更新パルスを送出する比較回路
と、前記最大値更新パルスが到着したときの順次
選択される前記パスメモリの最終ビツトを記憶す
る判定出力記憶回路から構成され、前記パスメモ
リが全てのパスに対して更新された時点での判定
出力記憶回路の内容を最適パスによる復号結果と
して出力することを特徴としたビタビ復号器の最
適パス判定回路。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP12845382A JPS5919455A (ja) | 1982-07-23 | 1982-07-23 | ビタビ復号器の最適パス判定回路 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP12845382A JPS5919455A (ja) | 1982-07-23 | 1982-07-23 | ビタビ復号器の最適パス判定回路 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPS5919455A JPS5919455A (ja) | 1984-01-31 |
| JPS638652B2 true JPS638652B2 (ja) | 1988-02-24 |
Family
ID=14985081
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP12845382A Granted JPS5919455A (ja) | 1982-07-23 | 1982-07-23 | ビタビ復号器の最適パス判定回路 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPS5919455A (ja) |
Families Citing this family (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS62233933A (ja) * | 1986-04-03 | 1987-10-14 | Toshiba Corp | ヴイタビ復号法 |
| CA2115445A1 (en) * | 1992-06-22 | 1994-01-06 | Masami Abe | Device for and method of continuing bit errors and device for and method of identifying signals |
Family Cites Families (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS5542440A (en) * | 1978-09-20 | 1980-03-25 | Chiyou Lsi Gijutsu Kenkyu Kumiai | Decoding device for convolutional code |
-
1982
- 1982-07-23 JP JP12845382A patent/JPS5919455A/ja active Granted
Also Published As
| Publication number | Publication date |
|---|---|
| JPS5919455A (ja) | 1984-01-31 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| KR100426712B1 (ko) | 비터비 복호기 | |
| US4777636A (en) | Path trace viterbi decoder | |
| US4905317A (en) | Path memory control method in Viterbi decoder | |
| KR100538730B1 (ko) | 비터비디코딩장치및비터비디코딩방법 | |
| US4606027A (en) | Error correction apparatus using a Viterbi decoder | |
| KR940010435B1 (ko) | 비터비 복호기의 경로기억장치 | |
| KR100528424B1 (ko) | 비터비디코딩장치및비터비디코딩방법 | |
| JPH0144058B2 (ja) | ||
| US5257263A (en) | Circuit for decoding convolutional codes for executing the survivor path storage and reverse scanning stage of a Viterbi algorithm | |
| US6697442B1 (en) | Viterbi decoding apparatus capable of shortening a decoding process time duration | |
| US5878060A (en) | Viterbi decoding apparatus and viterbe decoding method | |
| JP3784896B2 (ja) | ビタビデコーダの論理ブロック | |
| KR100311504B1 (ko) | 비터비디코더의스태이트메트릭메모리및이를이용한복호화방법 | |
| JPS638652B2 (ja) | ||
| JP4580927B2 (ja) | ビタビ復号装置、およびビタビ復号方法 | |
| JP4047697B2 (ja) | ビタビ復号装置 | |
| JP2904271B2 (ja) | ビタビ復号器用パスメモリユニットおよび復号方法 | |
| JPS6319097B2 (ja) | ||
| KR100205547B1 (ko) | 비터비 디코더의 트레이스 백 장치 | |
| KR960001471B1 (ko) | 바이터비 복호기 | |
| KR100240663B1 (ko) | 가산 비교 선택 회로를 갖는 비터비 디코더 | |
| KR100359805B1 (ko) | 비터비 디코더 및 비터비 디코더의 디코딩 방법 | |
| JP2004120791A (ja) | ビタビ復号器 | |
| JPH07288478A (ja) | ビタビ復号方法およびビタビ復号化装置 | |
| KR20010008761A (ko) | 병렬 가산비교선택회로 및 트레이스백 구조를 채용한 이동국용고속 비터비 디코더 |