JPH06112848A - ビタビ復号用演算装置 - Google Patents
ビタビ復号用演算装置Info
- Publication number
- JPH06112848A JPH06112848A JP25956392A JP25956392A JPH06112848A JP H06112848 A JPH06112848 A JP H06112848A JP 25956392 A JP25956392 A JP 25956392A JP 25956392 A JP25956392 A JP 25956392A JP H06112848 A JPH06112848 A JP H06112848A
- Authority
- JP
- Japan
- Prior art keywords
- data
- shift
- register
- viterbi decoding
- 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.)
- Granted
Links
Landscapes
- Error Detection And Correction (AREA)
- Dc Digital Transmission (AREA)
Abstract
(57)【要約】
【目的】 ビタビ復号を行うディジタル信号プロセッサ
において、少ないハードウェアを追加することによって
ビタビ復号処理を高速に、しかも少ないメモリ量で行う
ことができる演算装置を提供する。 【構成】 ビタビ復号におけるトレースバック操作を行
うために、データメモリ１から読み出したパスメモリデ
ータをバレルシフタ３でシフトすることにより選択する
パスセレクト信号を、シフトレジスタ４に入力するだけ
で１つ前の状態を求めることができ、シフトレジスタ４
の特定のレジスタの出力を反転するインバータ５により
バレルシフタ３の次のシフトビット数が決定でき、さら
にシフトレジスタ４に格納されていくパスセレクト信号
を復号データとすることができる構成であり、ビタビ復
号演算を少ない演算ステップ数と少ないデータメモリ量
で行うことができる。
において、少ないハードウェアを追加することによって
ビタビ復号処理を高速に、しかも少ないメモリ量で行う
ことができる演算装置を提供する。 【構成】 ビタビ復号におけるトレースバック操作を行
うために、データメモリ１から読み出したパスメモリデ
ータをバレルシフタ３でシフトすることにより選択する
パスセレクト信号を、シフトレジスタ４に入力するだけ
で１つ前の状態を求めることができ、シフトレジスタ４
の特定のレジスタの出力を反転するインバータ５により
バレルシフタ３の次のシフトビット数が決定でき、さら
にシフトレジスタ４に格納されていくパスセレクト信号
を復号データとすることができる構成であり、ビタビ復
号演算を少ない演算ステップ数と少ないデータメモリ量
で行うことができる。
Description
【０００１】
【産業上の利用分野】本発明は、誤り訂正用畳込み符号
化データのビタビ復号を行うディジタル信号処理プロセ
ッサ内部のビタビ復号用演算装置に関する。
化データのビタビ復号を行うディジタル信号処理プロセ
ッサ内部のビタビ復号用演算装置に関する。
【０００２】
【従来の技術】近年、ディジタル信号処理プロセッサ
（以下ＤＳＰと略称する）は、移動通信分野におけるデ
ィジタル化の動きに伴い、例えば携帯電話等の機器に組
込まれる用途のプロセッサとして注目されている。移動
無線回線におけるデータ通信ではビット誤りが頻繁に発
生し、誤り訂正処理を行う必要がある。誤り訂正の手法
には畳込み符号にビタビ復号を用いるものがあり、この
誤り訂正処理にＤＳＰを使用することがある。
（以下ＤＳＰと略称する）は、移動通信分野におけるデ
ィジタル化の動きに伴い、例えば携帯電話等の機器に組
込まれる用途のプロセッサとして注目されている。移動
無線回線におけるデータ通信ではビット誤りが頻繁に発
生し、誤り訂正処理を行う必要がある。誤り訂正の手法
には畳込み符号にビタビ復号を用いるものがあり、この
誤り訂正処理にＤＳＰを使用することがある。
【０００３】ビタビ復号は、加算，比較，選択という単
純な処理の繰り返しと、最終的にデータを復号するトレ
ースバック操作で畳込み符号の最尤復号（最ゆう復号）
を実現するものである。このビタビ復号では、情報ビッ
ト１ビットに対応する符号化データ（受信データ系列）
を得るごとに、その時点での各状態のパスの信号間距離
（メトリック）を計算し、生き残りパスを求める。
純な処理の繰り返しと、最終的にデータを復号するトレ
ースバック操作で畳込み符号の最尤復号（最ゆう復号）
を実現するものである。このビタビ復号では、情報ビッ
ト１ビットに対応する符号化データ（受信データ系列）
を得るごとに、その時点での各状態のパスの信号間距離
（メトリック）を計算し、生き残りパスを求める。
【０００４】図４は拘束長ｋの畳込み符号器にいて、あ
る時点における状態Ｓ2n（ｎは正整数）に対し、１つ前
の時点の状態Ｓnと状態（数１）から状態遷移を表す２
本のパスがのびている様子を示している
る時点における状態Ｓ2n（ｎは正整数）に対し、１つ前
の時点の状態Ｓnと状態（数１）から状態遷移を表す２
本のパスがのびている様子を示している
【０００５】
【数１】
【０００６】パスメトリックａは、状態Ｓ2nに入力する
パスの出力シンボルと受信データ系列との信号間距離
（ブランチメトリック）と１つ前の時点の状態Ｓnまで
の生き残りパスのブランチメトリックの総和であるパス
メトリックとの和である。同様にパスメトリックｂは、
状態Ｓ2nに入力するパスの出力シンボルと受信データ系
列との距離（ブランチメトリック）と、１つ前の時点の
状態（数１）までの生き残りパスのブランチメトリック
の総和であるパスメトリックとの和である。
パスの出力シンボルと受信データ系列との信号間距離
（ブランチメトリック）と１つ前の時点の状態Ｓnまで
の生き残りパスのブランチメトリックの総和であるパス
メトリックとの和である。同様にパスメトリックｂは、
状態Ｓ2nに入力するパスの出力シンボルと受信データ系
列との距離（ブランチメトリック）と、１つ前の時点の
状態（数１）までの生き残りパスのブランチメトリック
の総和であるパスメトリックとの和である。
【０００７】状態Ｓ2nに入力するパスメトリックａ，ｂ
を比較し、小さい方を生き残りパスとして選択する。こ
のようにパスメトリックを求めるための加算、パスメト
リックの比較、パスの選択の各処理を各時点で２k-1個
の状態に対して行う。さらにパスの選択においてどちら
を選択したかという履歴をパスセレクト信号ＰＳ
［Ｓ i］，（ｉ＝０〜｛２k-1−１｝）として残しておく
必要がある。選ばれたパスの１つ前の状態の添え字が他
方よりも小さければＰＳ［Ｓi］＝０、小さくなければ
ＰＳ［Ｓi］＝１とする。最終的にトレースバックによ
り復号する際に、このパスセレクト信号をもとに生き残
りパスを遡りながらデータが復号される。
を比較し、小さい方を生き残りパスとして選択する。こ
のようにパスメトリックを求めるための加算、パスメト
リックの比較、パスの選択の各処理を各時点で２k-1個
の状態に対して行う。さらにパスの選択においてどちら
を選択したかという履歴をパスセレクト信号ＰＳ
［Ｓ i］，（ｉ＝０〜｛２k-1−１｝）として残しておく
必要がある。選ばれたパスの１つ前の状態の添え字が他
方よりも小さければＰＳ［Ｓi］＝０、小さくなければ
ＰＳ［Ｓi］＝１とする。最終的にトレースバックによ
り復号する際に、このパスセレクト信号をもとに生き残
りパスを遡りながらデータが復号される。
【０００８】図５はある時点における状態Ｓ2n（ｎは正
整数）に対し、パスセレクト信号ＰＳ［Ｓ2n］をもとに
１つ前の時点の状態Ｓnまたは状態（数１）へパスを遡
る様子を示している。
整数）に対し、パスセレクト信号ＰＳ［Ｓ2n］をもとに
１つ前の時点の状態Ｓnまたは状態（数１）へパスを遡
る様子を示している。
【０００９】一般に状態Ｓiとパスセレクト信号ＰＳ
［Ｓi］から１つ前の状態は（数２）で表せる。
［Ｓi］から１つ前の状態は（数２）で表せる。
【００１０】
【数２】
【００１１】この時、末尾ビットで終端されている畳込
み符号を使用している場合は、パスセレクト信号を復号
データとしてよい。
み符号を使用している場合は、パスセレクト信号を復号
データとしてよい。
【００１２】図６は従来のビタビ復号用ＤＳＰ内部の演
算装置のブロック図を示すものである。
算装置のブロック図を示すものである。
【００１３】図６において、１はデータメモリであり、
パスメトリック，パスセレクト信号，復号データなどを
記憶する。３はバレルシフタであり、データメモリ１か
ら読み出されたデータをシフトする。６は第１のバスで
あり、データメモリ１に接続されてデータの供給や演算
結果の格納等を行う。７は第１のレジスタであり、バレ
ルシフタ３でシフトする時のシフトビット数を保持す
る。８は算術理論演算回路（以下ＡＬＵと略称する）で
あり、算術理論演算を行う。９は第１のラッチであり、
ＡＬＵ８の左側入力の値を一時記憶する。１０は第２の
ラッチであり、ＡＬＵ８の右側入力の値を一時記憶す
る。１１，１２はそれぞれ第２のレジスタであり、複数
で構成されており、演算結果を一時記憶する。１３は第
２のバスであり、レジスタ１１またはレジスタ１２から
のデータ供給を行う。バレルシフタ３のシフトビット数
は２の補数体系で示し、正の数の時は右シフトとなり、
負の数の時は左シフトとなる。
パスメトリック，パスセレクト信号，復号データなどを
記憶する。３はバレルシフタであり、データメモリ１か
ら読み出されたデータをシフトする。６は第１のバスで
あり、データメモリ１に接続されてデータの供給や演算
結果の格納等を行う。７は第１のレジスタであり、バレ
ルシフタ３でシフトする時のシフトビット数を保持す
る。８は算術理論演算回路（以下ＡＬＵと略称する）で
あり、算術理論演算を行う。９は第１のラッチであり、
ＡＬＵ８の左側入力の値を一時記憶する。１０は第２の
ラッチであり、ＡＬＵ８の右側入力の値を一時記憶す
る。１１，１２はそれぞれ第２のレジスタであり、複数
で構成されており、演算結果を一時記憶する。１３は第
２のバスであり、レジスタ１１またはレジスタ１２から
のデータ供給を行う。バレルシフタ３のシフトビット数
は２の補数体系で示し、正の数の時は右シフトとなり、
負の数の時は左シフトとなる。
【００１４】以上のように構成された演算装置につい
て、末尾ビットで終端する畳込み符号化を行った符号化
データをビタビ復号する時のトレースバック操作の動作
について示す。条件は畳込み符号の拘束長をｋ、符号化
されている情報ビット数をｎ、データメモリ１、第１の
バス６、第２のバス１３、第１のラッチ９、第２のラッ
チ１０、ＡＬＵ８、第２のレジスタ１１，１２のビット
幅をそれぞれ２k-1ビットとする。さらに時点ｔのパス
セレクト信号ＰＳt［Ｓi］，（ｔ＝０〜｛（ｎ−１）＋
（ｋ−１）｝，ｉ＝０〜｛２k-1−１｝）はパスメモリ
（数３）のように１ワードに詰めてＰＭ［ｔ］，（ｔ＝
０〜｛（ｎ−１）＋（ｋ−１）｝）の形でデータメモリ
に格納されているとする。
て、末尾ビットで終端する畳込み符号化を行った符号化
データをビタビ復号する時のトレースバック操作の動作
について示す。条件は畳込み符号の拘束長をｋ、符号化
されている情報ビット数をｎ、データメモリ１、第１の
バス６、第２のバス１３、第１のラッチ９、第２のラッ
チ１０、ＡＬＵ８、第２のレジスタ１１，１２のビット
幅をそれぞれ２k-1ビットとする。さらに時点ｔのパス
セレクト信号ＰＳt［Ｓi］，（ｔ＝０〜｛（ｎ−１）＋
（ｋ−１）｝，ｉ＝０〜｛２k-1−１｝）はパスメモリ
（数３）のように１ワードに詰めてＰＭ［ｔ］，（ｔ＝
０〜｛（ｎ−１）＋（ｋ−１）｝）の形でデータメモリ
に格納されているとする。
【００１５】
【数３】
【００１６】復号されたデータＹ［ｉ］，（ｉ＝０〜
｛ｎ−１｝）は１ビット１ワードでデータメモリ１に格
納する。
｛ｎ−１｝）は１ビット１ワードでデータメモリ１に格
納する。
【００１７】次にトレースバックの動作をステップに分
けて説明する。 （１）固定値［０］を第２のラッチ１０に格納する。Ａ
ＬＵ８は第２のラッチ１０の値をそのまま第２のレジス
タ１１に格納する。
けて説明する。 （１）固定値［０］を第２のラッチ１０に格納する。Ａ
ＬＵ８は第２のラッチ１０の値をそのまま第２のレジス
タ１１に格納する。
【００１８】［状態０から開始する。］次のステップ
（２）〜（１０）についてｉを｛（ｎ−１）＋（ｋ−
１）｝〜（ｋ−１）でダウンカウントしながらｎ回繰り
返す。
（２）〜（１０）についてｉを｛（ｎ−１）＋（ｋ−
１）｝〜（ｋ−１）でダウンカウントしながらｎ回繰り
返す。
【００１９】（２）第２のレジスタ１１の値を第２のバ
ス１３を介して、第１のラッチ９に格納する。ＡＬＵ８
で第１のラッチ９の値の２の補数を求め、第２のレジス
タ１２に格納する。
ス１３を介して、第１のラッチ９に格納する。ＡＬＵ８
で第１のラッチ９の値の２の補数を求め、第２のレジス
タ１２に格納する。
【００２０】（３）第２のレジスタ１２の値を第１のバ
ス６を介して、第１のレジスタ７に格納する。
ス６を介して、第１のレジスタ７に格納する。
【００２１】［次のパスセレクト信号を選択するための
シフトビット数となる。］ （４）データメモリ１よりパスメモリＰＭ［ｉ］を読み
出し、バレルシフタ３で第１のレジスタ７が指定するシ
フトビット数分シフトし、第２のラッチ１０に格納す
る。ＡＬＵ８は第２のラッチ１０の値をそのまま第２の
レジスタ１２に格納する。
シフトビット数となる。］ （４）データメモリ１よりパスメモリＰＭ［ｉ］を読み
出し、バレルシフタ３で第１のレジスタ７が指定するシ
フトビット数分シフトし、第２のラッチ１０に格納す
る。ＡＬＵ８は第２のラッチ１０の値をそのまま第２の
レジスタ１２に格納する。
【００２２】［選択するパスセレクト信号を最下位ビッ
ト（ＬＳＢ）に寄せる。］ （５）第２のレジスタ１２の値を第２のバス１３を介し
て第１のラッチ９に格納し、固定値［１］を第２のラッ
チ１０に格納する。ＡＬＵ８において第１のラッチ９と
第２のラッチ１０との論理積を求め、第２のレジスタ１
２に格納する。
ト（ＬＳＢ）に寄せる。］ （５）第２のレジスタ１２の値を第２のバス１３を介し
て第１のラッチ９に格納し、固定値［１］を第２のラッ
チ１０に格納する。ＡＬＵ８において第１のラッチ９と
第２のラッチ１０との論理積を求め、第２のレジスタ１
２に格納する。
【００２３】［ＬＳＢのみを抜き出す。］ （６）第２のレジスタ１２の値を復号データＹ［ｉ−
（ｋ−１）］としてデータメモリに格納する。
（ｋ−１）］としてデータメモリに格納する。
【００２４】［ＬＳＢが復号データとなる。］ （７）第１のレジスタ７に固定値［ｋ］を格納する。
【００２５】（８）レジスタ１２の値を第２のバス１３
を介して第１のラッチ９に格納し、第２のレジスタ１２
の値を第１のバス６を介してバレルシフタ３で第１のレ
ジスタ７が指定するシフトビット数の分シフトした出力
を第２のラッチ１０に格納する。ＡＬＵ８において第１
のラッチ９と第２のラッチ１０との論理和を求め、第２
のレジスタ１２に格納する。
を介して第１のラッチ９に格納し、第２のレジスタ１２
の値を第１のバス６を介してバレルシフタ３で第１のレ
ジスタ７が指定するシフトビット数の分シフトした出力
を第２のラッチ１０に格納する。ＡＬＵ８において第１
のラッチ９と第２のラッチ１０との論理和を求め、第２
のレジスタ１２に格納する。
【００２６】（９）第１のレジスタ７に固定値［−１］
を格納する。 （１０）第２のレジスタ１２の値をバレルシフタ３で第
１のレジスタ７が指定するシフトビット数の分シフトし
た出力を第２のラッチ１０に格納する。ＡＬＵ８は第２
のラッチ１０の値をそのままレジスタ１２に格納する。
を格納する。 （１０）第２のレジスタ１２の値をバレルシフタ３で第
１のレジスタ７が指定するシフトビット数の分シフトし
た出力を第２のラッチ１０に格納する。ＡＬＵ８は第２
のラッチ１０の値をそのままレジスタ１２に格納する。
【００２７】［ステップ（６）〜（１０）で１つ前の状
態を計算する。］このように上記従来の演算装置では、
バレルシフタ３とＡＬＵ８を組み合わせて演算すること
により、ｎビットの情報ビットのビタビ復号におけるト
レースバック操作を（９ｎ＋１）ステップかけて行うこ
とができる。
態を計算する。］このように上記従来の演算装置では、
バレルシフタ３とＡＬＵ８を組み合わせて演算すること
により、ｎビットの情報ビットのビタビ復号におけるト
レースバック操作を（９ｎ＋１）ステップかけて行うこ
とができる。
【００２８】なお、演算ビット幅が状態数２k-1より小
さい場合、または末尾のビットで終端せず連続で畳込み
符号を使用する場合のトレースバック操作も同様に行え
る。
さい場合、または末尾のビットで終端せず連続で畳込み
符号を使用する場合のトレースバック操作も同様に行え
る。
【００２９】
【発明が解決しようとする課題】しかしながら、上記従
来の演算装置では、１つ前の状態を求めるのに要する演
算ステップが多く、また復号データを１ビット１ワード
で格納していくので、データメモリの容量が大きくなる
という問題があった。
来の演算装置では、１つ前の状態を求めるのに要する演
算ステップが多く、また復号データを１ビット１ワード
で格納していくので、データメモリの容量が大きくなる
という問題があった。
【００３０】本発明はこのような従来の問題点を解決す
るものであり、少ない演算ステップ数と少ないデータメ
モリでビタビ復号におけるトレースバック操作を行うこ
とができる優れた演算装置を提供することを目的とする
ものである。
るものであり、少ない演算ステップ数と少ないデータメ
モリでビタビ復号におけるトレースバック操作を行うこ
とができる優れた演算装置を提供することを目的とする
ものである。
【００３１】
【課題を解決するための手段】本発明は上記目的を達成
するために、データを記憶するメモリと、そのメモリか
ら読み出された前記データをシフトするバレルシフタ
と、そのバレルシフタの出力信号であるデータの特定の
１ビットをシフト入力として前記メモリからのデータロ
ードおよび前記メモリへのデータ格納の機能も持つシフ
トレジスタと、そのシフトレジスタの特定のレジスタの
出力を反転するインバータとを備え、前記インバータの
出力信号であるデータを前記バレルシフタのシフトビッ
ト数とし、前記メモリから読み出された前記データを前
記バレルシフタで前記インバータの出力であるデータで
示されるシフトビット数でシフトしながら、前記バレル
シフタの出力信号であるデータを前記シフトレジスタに
入力するようにしたものである。
するために、データを記憶するメモリと、そのメモリか
ら読み出された前記データをシフトするバレルシフタ
と、そのバレルシフタの出力信号であるデータの特定の
１ビットをシフト入力として前記メモリからのデータロ
ードおよび前記メモリへのデータ格納の機能も持つシフ
トレジスタと、そのシフトレジスタの特定のレジスタの
出力を反転するインバータとを備え、前記インバータの
出力信号であるデータを前記バレルシフタのシフトビッ
ト数とし、前記メモリから読み出された前記データを前
記バレルシフタで前記インバータの出力であるデータで
示されるシフトビット数でシフトしながら、前記バレル
シフタの出力信号であるデータを前記シフトレジスタに
入力するようにしたものである。
【００３２】
【作用】したがって本発明によれば、データメモリから
読み出したパスメモリをバレルシフタでシフトすること
により選択するパスセレクト信号をシフトレジスタに入
力するだけで１つ前の状態を求めることができ、また次
のバレルシフタのシフトビット数が決定でき、さらにシ
フトレジスタに格納されていくパスセレクト信号を復号
データとすることができるので、少ない演算ステップ数
と少ないデータメモリによってビタビ復号におけるトレ
ースバック操作が行われる。
読み出したパスメモリをバレルシフタでシフトすること
により選択するパスセレクト信号をシフトレジスタに入
力するだけで１つ前の状態を求めることができ、また次
のバレルシフタのシフトビット数が決定でき、さらにシ
フトレジスタに格納されていくパスセレクト信号を復号
データとすることができるので、少ない演算ステップ数
と少ないデータメモリによってビタビ復号におけるトレ
ースバック操作が行われる。
【００３３】
【実施例】図１は本発明の一実施例におけるビタビ復号
用演算装置の構成を示すブロック図である。
用演算装置の構成を示すブロック図である。
【００３４】図１において、１はデータメモリであり、
パスメトリック，パスセレクト信号，復号データなどを
記憶する。２はバスであり、データメモリ１に接続され
データの供給や演算結果の格納等を行う。３はバレルシ
フタであり、データメモリ１から読み出されたデータを
シフトする。４はシフトレジスタであり、バレルシフタ
３の出力の特定の１ビットをシフト入力でき、かつバス
２を介してデータメモリ１からのデータロードまたはデ
ータメモリ１へのデータ格納を行う。５はインバータで
あり、シフトレジスタ４の特定のレジスタの値を反転し
てバレルシフタ３にシフトビット数を与える。バレルシ
フタ３のシフトビット数は２の補数体系で示し、正の数
の時右シフトとなり、負の数の時左シフトとなる。シフ
トレジスタ４はシフト入力側を最上位ビット（ＭＳＢ）
とする。
パスメトリック，パスセレクト信号，復号データなどを
記憶する。２はバスであり、データメモリ１に接続され
データの供給や演算結果の格納等を行う。３はバレルシ
フタであり、データメモリ１から読み出されたデータを
シフトする。４はシフトレジスタであり、バレルシフタ
３の出力の特定の１ビットをシフト入力でき、かつバス
２を介してデータメモリ１からのデータロードまたはデ
ータメモリ１へのデータ格納を行う。５はインバータで
あり、シフトレジスタ４の特定のレジスタの値を反転し
てバレルシフタ３にシフトビット数を与える。バレルシ
フタ３のシフトビット数は２の補数体系で示し、正の数
の時右シフトとなり、負の数の時左シフトとなる。シフ
トレジスタ４はシフト入力側を最上位ビット（ＭＳＢ）
とする。
【００３５】以上のように構成された演算装置につい
て、末尾ビットで終端する畳込み符号を行った符号化デ
ータをビタビ復号する時のトレースバック操作の動作に
ついて説明する。条件は畳込み符号の拘束長をｋ、符号
化されている情報ビット数をｎ、データメモリ１、バス
２、シフトレジスタ４のビット幅を２k-1ビットとす
る。シフトレジスタ４のシフト入力にはバレルシフタ３
の出力のＭＳＢが入力するようにし、インバータ５はシ
フトレジスタ４の上位（ｋ−１）ビットを反転し、その
出力（ｋ−１）ビットにＭＳＢに０を付加したｋビット
でバレルシフタ３のシフトビット数となるようにする。
さらに時点ｔのパスセレクト信号ＰＳt［Ｓi］，（ｔ＝
０〜｛（ｎ−１）＋（ｋ−１）｝，ｉ＝０〜｛２k-1−
１｝）はパスメモリ（数３）のように１ワードに詰めて
ＰＭ［ｔ］，（ｔ＝０〜｛（ｎ−１）＋（ｋ−１）｝）
の形でメモリに１に格納されているとする。
て、末尾ビットで終端する畳込み符号を行った符号化デ
ータをビタビ復号する時のトレースバック操作の動作に
ついて説明する。条件は畳込み符号の拘束長をｋ、符号
化されている情報ビット数をｎ、データメモリ１、バス
２、シフトレジスタ４のビット幅を２k-1ビットとす
る。シフトレジスタ４のシフト入力にはバレルシフタ３
の出力のＭＳＢが入力するようにし、インバータ５はシ
フトレジスタ４の上位（ｋ−１）ビットを反転し、その
出力（ｋ−１）ビットにＭＳＢに０を付加したｋビット
でバレルシフタ３のシフトビット数となるようにする。
さらに時点ｔのパスセレクト信号ＰＳt［Ｓi］，（ｔ＝
０〜｛（ｎ−１）＋（ｋ−１）｝，ｉ＝０〜｛２k-1−
１｝）はパスメモリ（数３）のように１ワードに詰めて
ＰＭ［ｔ］，（ｔ＝０〜｛（ｎ−１）＋（ｋ−１）｝）
の形でメモリに１に格納されているとする。
【００３６】復号されたデータＹ［ｉ］，（ｉ＝０〜
｛ｎ−１｝）は２k-1ビットを１ワードに詰め、データ
メモリ１に格納する。次にトレースバックの動作をステ
ップに分けて説明する。
｛ｎ−１｝）は２k-1ビットを１ワードに詰め、データ
メモリ１に格納する。次にトレースバックの動作をステ
ップに分けて説明する。
【００３７】（１）シフトレジスタ４に固定値［０］を
格納する。 ［状態０から開始する。］次のステップ（２）〜（３）
についてｉを｛（ｎ−１）＋（ｋ−１）｝〜（ｋ−１）
でダウンカウントしながらｎ回繰り返す。
格納する。 ［状態０から開始する。］次のステップ（２）〜（３）
についてｉを｛（ｎ−１）＋（ｋ−１）｝〜（ｋ−１）
でダウンカウントしながらｎ回繰り返す。
【００３８】（２）データメモリ１より、パスメモリＰ
Ｍ［ｉ］を読み出し、バレルシフタ３でインバータ５の
出力ｋビットが指定するシフトビット数分シフトし、バ
レルシフタ３出力のＭＳＢをシフトレジスタ４にシフト
入力する。
Ｍ［ｉ］を読み出し、バレルシフタ３でインバータ５の
出力ｋビットが指定するシフトビット数分シフトし、バ
レルシフタ３出力のＭＳＢをシフトレジスタ４にシフト
入力する。
【００３９】［選択するパスセレクト信号をＭＳＢに寄
せる。］ ［シフト入力後上位（ｋ−１）ビットが１つ前の状態を
示す。］［同時に上位（ｋ−１）ビットの反転が次のパ
スセレクト信号を選択するためのシフトビット数のもと
となる。］ （３）２k-1ビット復号されるごとに１回、シフトレジ
スタ４の内容をデータメモリに格納する。
せる。］ ［シフト入力後上位（ｋ−１）ビットが１つ前の状態を
示す。］［同時に上位（ｋ−１）ビットの反転が次のパ
スセレクト信号を選択するためのシフトビット数のもと
となる。］ （３）２k-1ビット復号されるごとに１回、シフトレジ
スタ４の内容をデータメモリに格納する。
【００４０】［選択されたパスセレクト信号が復号デー
タとなる。］以上のように本実施例によれば、ステップ
（２）でパスセレクト信号の選択および１つ前の状態の
計算が行えるので、ｎビットの情報ビットのビタビ復号
におけるトレースバック操作を｛ｎ＋（ｎ／２k-1）＋
１｝ステップで行うことができる。
タとなる。］以上のように本実施例によれば、ステップ
（２）でパスセレクト信号の選択および１つ前の状態の
計算が行えるので、ｎビットの情報ビットのビタビ復号
におけるトレースバック操作を｛ｎ＋（ｎ／２k-1）＋
１｝ステップで行うことができる。
【００４１】図２，図３は本発明の他の実施例における
演算装置の構成を示すブロック図である。図２，図３
は、図１に示す構成に第１のレジスタ７、ＡＬＵ８、第
１のラッチ９、第２のラッチ１０、第２のラッチ１１，
１２、第２のバス１３を加えたものであり、ビタビ復号
のトレースバック操作以外の処理を行うにはこれらの構
成が必要である。
演算装置の構成を示すブロック図である。図２，図３
は、図１に示す構成に第１のレジスタ７、ＡＬＵ８、第
１のラッチ９、第２のラッチ１０、第２のラッチ１１，
１２、第２のバス１３を加えたものであり、ビタビ復号
のトレースバック操作以外の処理を行うにはこれらの構
成が必要である。
【００４２】なお、演算ビット幅が状態数２k-1より小
さい場合、または末尾のビットで終端せず連続で畳込み
符号を使用する場合のトレースバック操作も同様に行う
ことができる。
さい場合、または末尾のビットで終端せず連続で畳込み
符号を使用する場合のトレースバック操作も同様に行う
ことができる。
【００４３】
【発明の効果】本発明は上記実施例より明らかなよう
に、データメモリから読み出したパスメモリをバレルシ
フタでシフトすることにより選択するパスセレクト信号
を、シフトレジスタに入力するだけで１つ前の状態を求
めることができ、次のバレルシフタのシフトビット数が
決定でき、さらにシフトレジスタに格納されて行くパス
セレクト信号を復号データとすることができるので、ビ
タビ復号におけるトレースバック操作を行うために、少
ない演算ステップ数と少ない容量のデータメモリで行う
ことができる。
に、データメモリから読み出したパスメモリをバレルシ
フタでシフトすることにより選択するパスセレクト信号
を、シフトレジスタに入力するだけで１つ前の状態を求
めることができ、次のバレルシフタのシフトビット数が
決定でき、さらにシフトレジスタに格納されて行くパス
セレクト信号を復号データとすることができるので、ビ
タビ復号におけるトレースバック操作を行うために、少
ない演算ステップ数と少ない容量のデータメモリで行う
ことができる。
【図１】本発明の一実施例におけるビタビ復号用演算装
置の構成を示すブロック図
置の構成を示すブロック図
【図２】同じく他の実施例におけるビタビ復号用演算装
置の構成を示すブロック図
置の構成を示すブロック図
【図３】同じくさらに他の実施例におけるビタビ復号用
演算装置の構成を示すブロック図
演算装置の構成を示すブロック図
【図４】ビタビ復号における畳込み符号器の状態遷移の
パスを示す状態遷移図（トレリス線図）
パスを示す状態遷移図（トレリス線図）
【図５】ビタビ復号におけるトレースバック時のパスの
遡りを示す状態遷移図（トレリス線図）
遡りを示す状態遷移図（トレリス線図）
【図６】従来のビタビ復号用演算装置の構成を示すブロ
ック図
ック図
１ データメモリ ２ バス ３ バレルシフタ ４ シフトレジスタ ５ インバータ
Claims (1)
- 【請求項１】 データを記憶するメモリと、そのメモリ
から読み出された前記データをシフトするバレルシフタ
と、そのバレルシフタの出力信号であるデータの特定の
１ビットをシフト入力として前記メモリからのデータロ
ードおよび前記メモリへのデータ格納を行うシフトレジ
スタと、そのシフトレジスタの特定のレジスタの出力を
反転するインバータとを備え、前記インバータの出力信
号であるデータを前記バレルシフタのシフトビット数と
し、前記メモリから読み出された前記データを前記バレ
ルシフタで前記インバータの出力信号であるデータで指
定されるシフトビット数でシフトしながら前記バレルシ
フタの出力信号であるデータを前記シフトレジスタに入
力することを特徴とするビタビ復号用演算装置。
Priority Applications (9)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP25956392A JP3191442B2 (ja) | 1992-09-29 | 1992-09-29 | ビタビ復号用演算装置 |
| AU47598/93A AU652896B2 (en) | 1992-09-29 | 1993-09-27 | Arithmetic apparatus |
| US08/126,563 US5715470A (en) | 1992-09-29 | 1993-09-27 | Arithmetic apparatus for carrying out viterbi decoding at a high speed |
| EP93115631A EP0590597B1 (en) | 1992-09-29 | 1993-09-28 | Arithmetic apparatus |
| DE69331568T DE69331568T2 (de) | 1992-09-29 | 1993-09-28 | Arithmetisches Gerät |
| EP00113488A EP1049001B1 (en) | 1992-09-29 | 1993-09-28 | Arithmetic apparatus |
| DE69333460T DE69333460T2 (de) | 1992-09-29 | 1993-09-28 | Arithmetisches Gerät |
| CN93118166A CN1049778C (zh) | 1992-09-29 | 1993-09-29 | 用于实现误码纠错用卷积码的维特比译码的运算装置 |
| CN99106651.0A CN1237046A (zh) | 1992-09-29 | 1999-05-18 | 用于实现误码纠错用卷积码的维特比译码的运算装置 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP25956392A JP3191442B2 (ja) | 1992-09-29 | 1992-09-29 | ビタビ復号用演算装置 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH06112848A true JPH06112848A (ja) | 1994-04-22 |
| JP3191442B2 JP3191442B2 (ja) | 2001-07-23 |
Family
ID=17335867
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP25956392A Expired - Fee Related JP3191442B2 (ja) | 1992-09-29 | 1992-09-29 | ビタビ復号用演算装置 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JP3191442B2 (ja) |
Cited By (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6337890B1 (en) | 1997-08-29 | 2002-01-08 | Nec Corporation | Low-power-consumption Viterbi decoder |
| KR100439211B1 (ko) * | 1996-10-15 | 2004-10-26 | 마쯔시다덴기산교 가부시키가이샤 | 연산처리장치 |
| JP2008541498A (ja) * | 2005-01-20 | 2008-11-20 | マーベル ワールド トレード リミテッド | 高記憶効率スライディングウィンドウ加算 |
-
1992
- 1992-09-29 JP JP25956392A patent/JP3191442B2/ja not_active Expired - Fee Related
Cited By (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| KR100439211B1 (ko) * | 1996-10-15 | 2004-10-26 | 마쯔시다덴기산교 가부시키가이샤 | 연산처리장치 |
| US6337890B1 (en) | 1997-08-29 | 2002-01-08 | Nec Corporation | Low-power-consumption Viterbi decoder |
| JP2008541498A (ja) * | 2005-01-20 | 2008-11-20 | マーベル ワールド トレード リミテッド | 高記憶効率スライディングウィンドウ加算 |
Also Published As
| Publication number | Publication date |
|---|---|
| JP3191442B2 (ja) | 2001-07-23 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| EP0590597B1 (en) | Arithmetic apparatus | |
| US5946361A (en) | Viterbi decoding method and circuit with accelerated back-tracing and efficient path metric calculation | |
| KR100439211B1 (ko) | 연산처리장치 | |
| JPH10107651A (ja) | ビタビ復号装置 | |
| JP3274668B2 (ja) | 演算処理装置及び演算処理方法 | |
| US7131055B2 (en) | Fast bit-parallel Viterbi decoder add-compare-select circuit | |
| JP3191442B2 (ja) | ビタビ復号用演算装置 | |
| US6910177B2 (en) | Viterbi decoder using restructured trellis | |
| JP2917577B2 (ja) | 演算装置 | |
| JP2000311096A (ja) | 演算処理装置 | |
| JPH0722969A (ja) | 演算装置 | |
| JP3235333B2 (ja) | ビタビ復号方法およびビタビ復号化装置 | |
| JP3259343B2 (ja) | ビタビ復号器 | |
| JP3250363B2 (ja) | 演算装置 | |
| KR100414152B1 (ko) | 프로그래머블 프로세서에서의 비터비 디코딩 연산방법 및그 연산방법을 실행하기 위한 연산회로 | |
| JP3269845B2 (ja) | ヴィタビ復号器 | |
| JP3351414B2 (ja) | ビタビ復号装置 | |
| JP3996858B2 (ja) | 演算処理装置 | |
| JPH0746145A (ja) | 演算装置 | |
| JP3634333B2 (ja) | ディジタル信号処理プロセッサ | |
| WO2002056480A1 (fr) | Decodeur de viterbi | |
| Jamal et al. | Design and FPGA Implementation of Low Power Punctured Soft Decision Viterbi Decoder | |
| JPH10178356A (ja) | 演算処理装置及びそれを用いた無線局装置 | |
| JP2001094443A (ja) | Ａｃｓ演算装置及びビタビ復号装置 | |
| JPH06204894A (ja) | 多数決回路及びビタビ復号器 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| LAPS | Cancellation because of no payment of annual fees |