JPH10209882A - ビタビ復号方法 - Google Patents
ビタビ復号方法Info
- Publication number
- JPH10209882A JPH10209882A JP9010832A JP1083297A JPH10209882A JP H10209882 A JPH10209882 A JP H10209882A JP 9010832 A JP9010832 A JP 9010832A JP 1083297 A JP1083297 A JP 1083297A JP H10209882 A JPH10209882 A JP H10209882A
- Authority
- JP
- Japan
- Prior art keywords
- path
- time
- metric
- state
- memory
- 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
Links
Landscapes
- Detection And Correction Of Errors (AREA)
- Error Detection And Correction (AREA)
- Dc Digital Transmission (AREA)
Abstract
(57)【要約】
【課題】 ＡＣＳ処理におけるパスメトリック用メモリ
へのアクセス回数を減らし、消費電力を低減する。 【解決手段】 ＡＣＳ回路を並列化し（３，４）、同一
状態を遷移元とする枝については異なるＡＣＳ回路にて
ＡＣＳ処理を実行させることにより、パスメトリック用
メモリ５からのパスメトリック読出回数を半減させる。
へのアクセス回数を減らし、消費電力を低減する。 【解決手段】 ＡＣＳ回路を並列化し（３，４）、同一
状態を遷移元とする枝については異なるＡＣＳ回路にて
ＡＣＳ処理を実行させることにより、パスメトリック用
メモリ５からのパスメトリック読出回数を半減させる。
Description
【０００１】
【発明の属する技術分野】本発明は、畳込み符号を最尤
復号する方法の一つであるビタビ復号に関し、特にその
効率的な実現方法に関する。
復号する方法の一つであるビタビ復号に関し、特にその
効率的な実現方法に関する。
【０００２】
【従来の技術及びその問題点】その品質がさほど高くな
い通信路を用いて通信を行うには、最尤又はそれに近い
復号が可能な復号方法と、その復号方法を実行可能にす
る符号化方式とが必要である。例えば移動体通信では、
通信端末の移動に伴い通信路の状態が変化するため、符
号化方式として畳込み符号を、また復号方法としてビタ
ビ復号をそれぞれ採用するのが好ましい。ビタビ復号
は、受信した符号系列の尤度関数値を最大値とする系列
即ち最尤系列を、メトリック値に基づくパスの取捨選択
によって、検出する復号方法であり、一般的には、概略
次の各段階を追って実行される。
い通信路を用いて通信を行うには、最尤又はそれに近い
復号が可能な復号方法と、その復号方法を実行可能にす
る符号化方式とが必要である。例えば移動体通信では、
通信端末の移動に伴い通信路の状態が変化するため、符
号化方式として畳込み符号を、また復号方法としてビタ
ビ復号をそれぞれ採用するのが好ましい。ビタビ復号
は、受信した符号系列の尤度関数値を最大値とする系列
即ち最尤系列を、メトリック値に基づくパスの取捨選択
によって、検出する復号方法であり、一般的には、概略
次の各段階を追って実行される。
【０００３】第１の段階は、枝メトリックの算出であ
る。まず、時刻ｎ−１におけるｉ番目の状態をＳ(n-1)
i、時刻ｎにおけるｊ番目の状態をＳnjと表し、更に、
状態Ｓ(n-1)iからＳnjに遷移する枝をｂ(n-1)ijと表す
とする。図２の例は、拘束長＝４、符号化率＝１／２の
例であり、時刻ｎ−１において発生可能な状態Ｓ(n-1)i
は０００，００１，…１１１の８通りあり（即ちｉ＝０
〜７）、時刻ｎにおいて発生可能な状態Ｓnjも０００，
００１，…１１１の８通りある（即ちｊ＝０〜７）。こ
こでは０／１の２値のシンボルを例示しているから、状
態Ｓ(n-1)0＝“０００”から遷移可能な状態は、Ｓn0＝
“０００”及びＳn1＝“００１”の２通り、状態Ｓ(n-
1)1＝“００１”から遷移可能な状態は、Ｓn2＝“０１
０”及びＳn3＝“０１１”の２通り、…というように、
枝ｂ(n-1)ijは時刻ｎ−１での状態Ｓ(n-1)i毎に２本ず
つ、合計で２本×８状態＝１６本ある。枝メトリックλ
(n-1)ijは、枝ｂ(n-1)ijの尤もらしさを評価する指標で
あり、枝メトリックλ(n-1)ijが小さい枝ほど、尤もら
しい枝であるといえる。
る。まず、時刻ｎ−１におけるｉ番目の状態をＳ(n-1)
i、時刻ｎにおけるｊ番目の状態をＳnjと表し、更に、
状態Ｓ(n-1)iからＳnjに遷移する枝をｂ(n-1)ijと表す
とする。図２の例は、拘束長＝４、符号化率＝１／２の
例であり、時刻ｎ−１において発生可能な状態Ｓ(n-1)i
は０００，００１，…１１１の８通りあり（即ちｉ＝０
〜７）、時刻ｎにおいて発生可能な状態Ｓnjも０００，
００１，…１１１の８通りある（即ちｊ＝０〜７）。こ
こでは０／１の２値のシンボルを例示しているから、状
態Ｓ(n-1)0＝“０００”から遷移可能な状態は、Ｓn0＝
“０００”及びＳn1＝“００１”の２通り、状態Ｓ(n-
1)1＝“００１”から遷移可能な状態は、Ｓn2＝“０１
０”及びＳn3＝“０１１”の２通り、…というように、
枝ｂ(n-1)ijは時刻ｎ−１での状態Ｓ(n-1)i毎に２本ず
つ、合計で２本×８状態＝１６本ある。枝メトリックλ
(n-1)ijは、枝ｂ(n-1)ijの尤もらしさを評価する指標で
あり、枝メトリックλ(n-1)ijが小さい枝ほど、尤もら
しい枝であるといえる。
【０００４】第２の段階は、パスメトリックλ(n-1)iと
枝メトリックλ(n-1)ijの加算（Ａ）、加算値同士の比
較（Ｃ）及び比較結果に基づく状態Ｓnjについての生残
りパスの選択（Ｓ）という一連の処理即ちＡＣＳ処理で
ある。パスメトリックλ(n-1)iとは、そのパスが時刻ｎ
−１で状態Ｓ(n-1)iに至るまでに経由してきた全ての枝
の枝メトリックの累積加算値であり、パスメトリックが
小さいほど尤もらしいパスであるといえる。更に、状態
Ｓnjについての生残りパスとは、時刻ｎにおいて状態Ｓ
njに至る複数本のパス（図２の例では２本）のうち、そ
のパスメトリックλnj即ちλ(n-1)i＋λ(n-1)ijが最小
になるものをいう。ここで、図２の例では、状態Ｓn0＝
“０００”に至るパスには、状態Ｓ(n-1)0からの枝ｂ(n
-1)0を含むパス及び状態Ｓ(n-1)4からの枝ｂ(n-1)4を含
むパスの２本ある。ＡＣＳ処理においては、まず、状態
Ｓ(n-1)0に至るパスのパスメトリックλ(n-1)0と、枝ｂ
(n-1)00の枝メトリックλ(n-1)00とが加算され、同様に
状態Ｓ(n-1)4に至るパスのパスメトリックλ(n-1)4と、
枝ｂ(n-1)40の枝メトリックλ(n-1)40とが加算される
（Ａ）。次に、得られた和λ(n-1)0＋λ(n-1)00と和λ
(n-1)4＋λ(n-1)40とが比較され、いずれか小さいもの
が選択される（Ｃ）。そして、小さな和を与えたパス
が、状態Ｓn0についての生残りパスとして選択される
（Ｓ）。
枝メトリックλ(n-1)ijの加算（Ａ）、加算値同士の比
較（Ｃ）及び比較結果に基づく状態Ｓnjについての生残
りパスの選択（Ｓ）という一連の処理即ちＡＣＳ処理で
ある。パスメトリックλ(n-1)iとは、そのパスが時刻ｎ
−１で状態Ｓ(n-1)iに至るまでに経由してきた全ての枝
の枝メトリックの累積加算値であり、パスメトリックが
小さいほど尤もらしいパスであるといえる。更に、状態
Ｓnjについての生残りパスとは、時刻ｎにおいて状態Ｓ
njに至る複数本のパス（図２の例では２本）のうち、そ
のパスメトリックλnj即ちλ(n-1)i＋λ(n-1)ijが最小
になるものをいう。ここで、図２の例では、状態Ｓn0＝
“０００”に至るパスには、状態Ｓ(n-1)0からの枝ｂ(n
-1)0を含むパス及び状態Ｓ(n-1)4からの枝ｂ(n-1)4を含
むパスの２本ある。ＡＣＳ処理においては、まず、状態
Ｓ(n-1)0に至るパスのパスメトリックλ(n-1)0と、枝ｂ
(n-1)00の枝メトリックλ(n-1)00とが加算され、同様に
状態Ｓ(n-1)4に至るパスのパスメトリックλ(n-1)4と、
枝ｂ(n-1)40の枝メトリックλ(n-1)40とが加算される
（Ａ）。次に、得られた和λ(n-1)0＋λ(n-1)00と和λ
(n-1)4＋λ(n-1)40とが比較され、いずれか小さいもの
が選択される（Ｃ）。そして、小さな和を与えたパス
が、状態Ｓn0についての生残りパスとして選択される
（Ｓ）。
【０００５】このような段階を追って実行されるビタビ
復号は、強力な誤り訂正能力を有している。反面、ＡＣ
Ｓ処理の段階で、時刻ｎにおける様々な状態Ｓnjそれぞ
れについてかつ様々なパスの間で網羅的に、パスメトリ
ック枝メトリック加算値同士の比較をしなければならな
い、という問題点を有している。特に、加算の対象とな
るパスメトリックλ(n-1)i即ち前の時刻にて生残りパス
として選択されたパスのパスメトリックを、前の時刻で
のメモリへの書込／後の時刻でのメモリからの読出とい
う手順で時刻間で引き渡すように復号器を設計してある
ときには、ＡＣＳ処理を実行する際のメモリからのパス
メトリック値の読出の回数が、１時刻あたり、その時刻
ｎで採りうる状態の個数×各状態への遷移を示す枝の本
数、という多数に上る。
復号は、強力な誤り訂正能力を有している。反面、ＡＣ
Ｓ処理の段階で、時刻ｎにおける様々な状態Ｓnjそれぞ
れについてかつ様々なパスの間で網羅的に、パスメトリ
ック枝メトリック加算値同士の比較をしなければならな
い、という問題点を有している。特に、加算の対象とな
るパスメトリックλ(n-1)i即ち前の時刻にて生残りパス
として選択されたパスのパスメトリックを、前の時刻で
のメモリへの書込／後の時刻でのメモリからの読出とい
う手順で時刻間で引き渡すように復号器を設計してある
ときには、ＡＣＳ処理を実行する際のメモリからのパス
メトリック値の読出の回数が、１時刻あたり、その時刻
ｎで採りうる状態の個数×各状態への遷移を示す枝の本
数、という多数に上る。
【０００６】
【発明の概要】本発明の目的の一つは、ＡＣＳ処理の実
行形式に改善を施すことにより、パスメトリックを記憶
するためのメモリ即ちパスメトリック用メモリの使用態
様を変更し、従来に比べメモリアクセスの回数が少なく
従ってメモリ消費電力の小さなビタビ復号器を、実現可
能にすることにある。
行形式に改善を施すことにより、パスメトリックを記憶
するためのメモリ即ちパスメトリック用メモリの使用態
様を変更し、従来に比べメモリアクセスの回数が少なく
従ってメモリ消費電力の小さなビタビ復号器を、実現可
能にすることにある。
【０００７】本発明の好適な実施形態の一つは、枝メト
リック計算ステップ及びＡＣＳステップを有するビタビ
復号方法の改善である。枝メトリック計算ステップで
は、離散化された時刻ｎ−１から時刻ｎにかけての状態
遷移を示す枝の枝メトリックλ(n-1)ijを、遷移元と遷
移先の状態の組合せのうち生じうるもの全てについて、
計算する。また、ＡＣＳステップでは、時刻ｎ−１での
生残りパスのパスメトリックλ(n-1)iをパスメトリック
用メモリから読みだし、読み出したパスメトリックλ(n
-1)iと枝メトリック計算ステップにて計算した枝メトリ
ックλ(n-1)ijとの加算値を各遷移先毎にかつ当該遷移
先に至るパス同士で比較し、比較により得られた最小の
加算値を、時刻ｎでの生残りパスのパスメトリックλnj
としてパスメトリック用メモリ上に書き込む。この実施
形態においては、更に、時刻ｎ−１で同一の状態を経由
しかつ時刻ｎで相異なる状態に至る複数のパスについ
て、ＡＣＳステップを並列的に実行する。
リック計算ステップ及びＡＣＳステップを有するビタビ
復号方法の改善である。枝メトリック計算ステップで
は、離散化された時刻ｎ−１から時刻ｎにかけての状態
遷移を示す枝の枝メトリックλ(n-1)ijを、遷移元と遷
移先の状態の組合せのうち生じうるもの全てについて、
計算する。また、ＡＣＳステップでは、時刻ｎ−１での
生残りパスのパスメトリックλ(n-1)iをパスメトリック
用メモリから読みだし、読み出したパスメトリックλ(n
-1)iと枝メトリック計算ステップにて計算した枝メトリ
ックλ(n-1)ijとの加算値を各遷移先毎にかつ当該遷移
先に至るパス同士で比較し、比較により得られた最小の
加算値を、時刻ｎでの生残りパスのパスメトリックλnj
としてパスメトリック用メモリ上に書き込む。この実施
形態においては、更に、時刻ｎ−１で同一の状態を経由
しかつ時刻ｎで相異なる状態に至る複数のパスについ
て、ＡＣＳステップを並列的に実行する。
【０００８】このように、ＡＣＳステップを並列的に実
行することにより（或いはそのような実行が可能なよう
にＡＣＳ回路を並列配設することにより）、パスメトリ
ック用メモリへのアクセスの回数を低減できる。例え
ば、時刻ｎ−１で同一の状態を経由するけれども時刻ｎ
では相異なる状態に至る２本のパスがあるとする。これ
らのパスについてＡＣＳを実行する際、時刻ｎ−１に至
るパスのパスメトリックが、共通して必要になる。上記
実施形態では、異なるパスについてのＡＣＳ処理に共通
して必要になるパスメトリックの読出が、複数回ではな
く１回で済むよう、ＡＣＳ処理を並列化している。従っ
て、本実施形態によれば、メモリアクセス回数の低減ひ
いてはメモり消費電力の低減を、達成できる。また、Ａ
ＣＳステップのみでなく、その前段たる枝メトリック計
算ステップや、後段たるパスメモリ選択ステップをも、
ＡＣＳステップの並列化に応じて並列化してもよい。こ
こでいうパスメモリ選択ステップとは、ＡＣＳステップ
にて最小の加算値を与えたパスを特定する情報を、パス
メモリ用メモリに書き込むステップである。
行することにより（或いはそのような実行が可能なよう
にＡＣＳ回路を並列配設することにより）、パスメトリ
ック用メモリへのアクセスの回数を低減できる。例え
ば、時刻ｎ−１で同一の状態を経由するけれども時刻ｎ
では相異なる状態に至る２本のパスがあるとする。これ
らのパスについてＡＣＳを実行する際、時刻ｎ−１に至
るパスのパスメトリックが、共通して必要になる。上記
実施形態では、異なるパスについてのＡＣＳ処理に共通
して必要になるパスメトリックの読出が、複数回ではな
く１回で済むよう、ＡＣＳ処理を並列化している。従っ
て、本実施形態によれば、メモリアクセス回数の低減ひ
いてはメモり消費電力の低減を、達成できる。また、Ａ
ＣＳステップのみでなく、その前段たる枝メトリック計
算ステップや、後段たるパスメモリ選択ステップをも、
ＡＣＳステップの並列化に応じて並列化してもよい。こ
こでいうパスメモリ選択ステップとは、ＡＣＳステップ
にて最小の加算値を与えたパスを特定する情報を、パス
メモリ用メモリに書き込むステップである。
【０００９】
【発明の実施の形態】以下、本発明の好適な実施形態に
関し図面に基づき説明する。図１に示すように、本発明
の一実施形態に係るビタビ復号器には、枝メトリック計
算器を２個（１，２）、ＡＣＳ回路を２個（３，４）、
更にパスメモリ選択器を２個（６，７）設けてあり、枝
メトリック計算器１、ＡＣＳ回路３及びパスメモリ選択
器６にて第１の系統を、枝メトリック計算器２、ＡＣＳ
回路４及びパスメモリ選択器７にて第２の系統を、それ
ぞれ構成している。枝メトリック計算器１及び２は、受
信した符号系列に基づき枝メトリックλ(n-1)ijを計算
する。ＡＣＳ回路３及び４は、各々、その前段の枝メト
リック計算器にて計算された枝メトリックλ(n-1)ij
と、読出経路９を介してパスメトリック用メモリ５から
読み出したパスメトリックλ(n-1)iとに基づき、ＡＣＳ
処理を実行し、それにより“その枝メトリックパスメト
リック加算値が最小値を与える”パス即ち生残りパスの
パスメトリックλnj＝λ(n-1)i＋λ(n-1)ijを、パスメ
トリック用メモリ５に書き込む。パスメモリ選択器６及
び７は、各々、読出経路１０を経てパスメモリ用メモリ
８から時刻ｎ−１における生残りパスを特定する情報を
読み出し、その前段のＡＣＳ回路での処理の結果に基づ
き、時刻ｎにおける生残りパスを特定する情報をパスメ
モリ用メモリ８に書き込む。
関し図面に基づき説明する。図１に示すように、本発明
の一実施形態に係るビタビ復号器には、枝メトリック計
算器を２個（１，２）、ＡＣＳ回路を２個（３，４）、
更にパスメモリ選択器を２個（６，７）設けてあり、枝
メトリック計算器１、ＡＣＳ回路３及びパスメモリ選択
器６にて第１の系統を、枝メトリック計算器２、ＡＣＳ
回路４及びパスメモリ選択器７にて第２の系統を、それ
ぞれ構成している。枝メトリック計算器１及び２は、受
信した符号系列に基づき枝メトリックλ(n-1)ijを計算
する。ＡＣＳ回路３及び４は、各々、その前段の枝メト
リック計算器にて計算された枝メトリックλ(n-1)ij
と、読出経路９を介してパスメトリック用メモリ５から
読み出したパスメトリックλ(n-1)iとに基づき、ＡＣＳ
処理を実行し、それにより“その枝メトリックパスメト
リック加算値が最小値を与える”パス即ち生残りパスの
パスメトリックλnj＝λ(n-1)i＋λ(n-1)ijを、パスメ
トリック用メモリ５に書き込む。パスメモリ選択器６及
び７は、各々、読出経路１０を経てパスメモリ用メモリ
８から時刻ｎ−１における生残りパスを特定する情報を
読み出し、その前段のＡＣＳ回路での処理の結果に基づ
き、時刻ｎにおける生残りパスを特定する情報をパスメ
モリ用メモリ８に書き込む。
【００１０】本実施形態の特徴は、しかしながら、枝メ
トリック計算器、ＡＣＳ回路及びパスメモリ選択器を複
数系統化したことのみにあるのではない。本実施形態の
特徴の一つは、パスメトリック用メモリ５へのアクセス
の回数が減るよう、複数のＡＣＳ回路３及び４を利用し
たことにある。例えば、図２の例でいえば、状態Ｓn0＝
“０００”に遷移するのは、状態Ｓ(n-1)0からの枝ｂ(n
-1)00を含むパスと、状態Ｓ(n-1)4からの枝ｂ(n-1)40を
含むパスの、合計２本である。従って、状態Ｓn0＝“０
００”に遷移する枝を含むパスの中から生き残りパスを
決定するのに必要な情報は、パスメトリックλ(n-1)0及
びλ(n-1)4並びに枝メトリックλ(n-1)00及びλ(n-1)40
である。他方、状態Ｓn1＝“００１”に遷移するのは、
状態Ｓ(n-1)0からの枝ｂ(n-1)00を含むパスと、状態Ｓ
(n-1)4からの枝ｂ(n-1)40を含むパスの、合計２本であ
る。従って、状態Ｓn1＝“００１”に遷移する枝を含む
パスの中から生き残りパスを決定するのに必要な情報
も、パスメトリックλ(n-1)0及びλ(n-1)4並びに枝メト
リックλ(n-1)00及びλ(n-1)40である。そこで、本実施
形態では、状態Ｓn0に係るＡＣＳ処理を例えばＡＣＳ回
路３にやらせ、これと並列に、状態Ｓn1に係るＡＣＳ処
理をＡＣＳ回路４にやらせることにより、パスメトリッ
ク用メモリ５からのλ(n-1)0及びλ(n-1)4の読出を各１
回に抑制している。従って、ＡＣＳ処理を実行する際の
メモリからのパスメトリック値の読出の回数は、従来は
１時刻あたりその時刻ｎで採りうる状態の個数×各状態
への遷移を示す枝の本数という多数に上っていたもの
を、本実施形態によれば、その時刻ｎで採りうる状態の
個数×各状態への遷移を示す枝の本数／系統の個数（こ
こでは２）に低減できる。これによって、メモリ消費電
力も減る。
トリック計算器、ＡＣＳ回路及びパスメモリ選択器を複
数系統化したことのみにあるのではない。本実施形態の
特徴の一つは、パスメトリック用メモリ５へのアクセス
の回数が減るよう、複数のＡＣＳ回路３及び４を利用し
たことにある。例えば、図２の例でいえば、状態Ｓn0＝
“０００”に遷移するのは、状態Ｓ(n-1)0からの枝ｂ(n
-1)00を含むパスと、状態Ｓ(n-1)4からの枝ｂ(n-1)40を
含むパスの、合計２本である。従って、状態Ｓn0＝“０
００”に遷移する枝を含むパスの中から生き残りパスを
決定するのに必要な情報は、パスメトリックλ(n-1)0及
びλ(n-1)4並びに枝メトリックλ(n-1)00及びλ(n-1)40
である。他方、状態Ｓn1＝“００１”に遷移するのは、
状態Ｓ(n-1)0からの枝ｂ(n-1)00を含むパスと、状態Ｓ
(n-1)4からの枝ｂ(n-1)40を含むパスの、合計２本であ
る。従って、状態Ｓn1＝“００１”に遷移する枝を含む
パスの中から生き残りパスを決定するのに必要な情報
も、パスメトリックλ(n-1)0及びλ(n-1)4並びに枝メト
リックλ(n-1)00及びλ(n-1)40である。そこで、本実施
形態では、状態Ｓn0に係るＡＣＳ処理を例えばＡＣＳ回
路３にやらせ、これと並列に、状態Ｓn1に係るＡＣＳ処
理をＡＣＳ回路４にやらせることにより、パスメトリッ
ク用メモリ５からのλ(n-1)0及びλ(n-1)4の読出を各１
回に抑制している。従って、ＡＣＳ処理を実行する際の
メモリからのパスメトリック値の読出の回数は、従来は
１時刻あたりその時刻ｎで採りうる状態の個数×各状態
への遷移を示す枝の本数という多数に上っていたもの
を、本実施形態によれば、その時刻ｎで採りうる状態の
個数×各状態への遷移を示す枝の本数／系統の個数（こ
こでは２）に低減できる。これによって、メモリ消費電
力も減る。
【００１１】
【補遺】なお、上述の効果を得るには、並列化する回路
の系統数を、復号すべき符号の設計に応じて定める必要
があることに留意されたい。このことは、本実施形態の
特徴が、単純な並列化にあるのではないことを裏付けて
いる。また、枝メトリックの具体的内容は例えば通信路
の性質に応じて定めればよく、状態Ｓ(n-1)iから状態Ｓ
njへの遷移の条件付き確率密度にて定義される基本枝メ
トリックの他、状態Ｓ(n-1)iと状態Ｓnjのユークリッド
距離の自乗値（通信路が白色ガウス通信路であると
き）、状態Ｓ(n-1)iと状態Ｓnjのハミング距離（通信路
が二次元対称通信路であるとき）等を採用できる。更
に、以上の説明では枝メトリックの算出手法については
言及しなかったが、本発明は、従来周知の各種の手法に
て実現できるものとする。また、本発明に係る方法にて
復号可能な符号は、図２に示した拘束長＝４、符号化率
＝１／２の例には、限定されない。更に、以上の説明で
は本発明を「ビタビ復号方法」に関する発明と述べた
が、当業者にとっては、本願の開示に基づき本発明を
「ビタビ復号器」「ＡＣＳ回路」等に表現変更するのは
容易であろう。
の系統数を、復号すべき符号の設計に応じて定める必要
があることに留意されたい。このことは、本実施形態の
特徴が、単純な並列化にあるのではないことを裏付けて
いる。また、枝メトリックの具体的内容は例えば通信路
の性質に応じて定めればよく、状態Ｓ(n-1)iから状態Ｓ
njへの遷移の条件付き確率密度にて定義される基本枝メ
トリックの他、状態Ｓ(n-1)iと状態Ｓnjのユークリッド
距離の自乗値（通信路が白色ガウス通信路であると
き）、状態Ｓ(n-1)iと状態Ｓnjのハミング距離（通信路
が二次元対称通信路であるとき）等を採用できる。更
に、以上の説明では枝メトリックの算出手法については
言及しなかったが、本発明は、従来周知の各種の手法に
て実現できるものとする。また、本発明に係る方法にて
復号可能な符号は、図２に示した拘束長＝４、符号化率
＝１／２の例には、限定されない。更に、以上の説明で
は本発明を「ビタビ復号方法」に関する発明と述べた
が、当業者にとっては、本願の開示に基づき本発明を
「ビタビ復号器」「ＡＣＳ回路」等に表現変更するのは
容易であろう。
【図１】 本発明の一実施形態に係るビタビ復号器の構
成を示すブロック図である。
成を示すブロック図である。
【図２】 拘束長＝４、符号化率＝１／２の例により時
刻ｎ−１から時刻ｎにかけての状態遷移を示す概念図で
ある。
刻ｎ−１から時刻ｎにかけての状態遷移を示す概念図で
ある。
１，２ 枝メトリック計算器、３，４ ＡＣＳ回路、５
パスメトリック用メモリ、６，７ パスメモリ選択
器、８ パスメモリ用メモリ、９，１０ 読出経路。
パスメトリック用メモリ、６，７ パスメモリ選択
器、８ パスメモリ用メモリ、９，１０ 読出経路。
Claims (3)
- 【請求項１】 離散化された時刻ｎ−１から時刻ｎにか
けての状態遷移を示す枝の枝メトリックを、遷移元と遷
移先の状態の組合せのうち生じうるもの全てについて、
計算する枝メトリック計算ステップと、時刻ｎ−１での
生残りパスのパスメトリックをパスメトリック用メモリ
から読みだし、読み出したパスメトリックと枝メトリッ
ク計算ステップにて計算した枝メトリックとの加算値を
各遷移先毎にかつ当該遷移先に至るパス同士で比較し、
比較により得られた最小の加算値を、時刻ｎでの生残り
パスのパスメトリックとしてパスメトリック用メモリ上
に書き込むＡＣＳステップと、を有するビタビ復号方法
において、 時刻ｎ−１で同一の状態を経由しかつ時刻ｎで相異なる
状態に至る複数のパスについて、上記ＡＣＳステップを
並列的に実行することを特徴とするビタビ復号方法。 - 【請求項２】 請求項１記載のビタビ復号方法におい
て、更に、遷移元が同一で遷移先が異なる複数の枝につ
いて、上記枝メトリック計算ステップを並列的に実行す
ることを特徴とするビタビ復号方法。 - 【請求項３】 請求項１又は２記載のビタビ復号方法に
おいて、更に、上記ＡＣＳステップにて最小の加算値を
与えたパスを特定する情報を、パスメモリ用メモリに書
き込むパスメモリ選択ステップを有し、且つ、時刻ｎ−
１で同一の状態を経由しかつ時刻ｎで相異なる状態に至
る複数のパスについて、上記パスメモリ選択ステップを
並列的に実行することを特徴とするビタビ復号方法。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP9010832A JPH10209882A (ja) | 1997-01-24 | 1997-01-24 | ビタビ復号方法 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP9010832A JPH10209882A (ja) | 1997-01-24 | 1997-01-24 | ビタビ復号方法 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH10209882A true JPH10209882A (ja) | 1998-08-07 |
Family
ID=11761340
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP9010832A Pending JPH10209882A (ja) | 1997-01-24 | 1997-01-24 | ビタビ復号方法 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH10209882A (ja) |
Cited By (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6477661B2 (en) | 1997-06-30 | 2002-11-05 | Matsushita Electric Industrial Co., Ltd. | Processing unit and processing method |
| US6792570B2 (en) | 2000-05-12 | 2004-09-14 | Nec Corporation | Viterbi decoder with high speed processing function |
| KR100834663B1 (ko) * | 2002-03-11 | 2008-06-02 | 삼성전자주식회사 | 직접 메모리 접근을 이용한 비터비 복호기 및 비터비 복호 방법 |
| US7392463B2 (en) | 2003-06-06 | 2008-06-24 | Fujitsu Limited | Data reproducing apparatus avoiding selection of incorrect path |
-
1997
- 1997-01-24 JP JP9010832A patent/JPH10209882A/ja active Pending
Cited By (7)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6477661B2 (en) | 1997-06-30 | 2002-11-05 | Matsushita Electric Industrial Co., Ltd. | Processing unit and processing method |
| US6735714B2 (en) | 1997-06-30 | 2004-05-11 | Matsushita Electric Industrial Co., Ltd. | Processing unit and processing method |
| US7139968B2 (en) | 1997-06-30 | 2006-11-21 | Matsushita Electric Industrial Co., Ltd. | Processing unit and processing method |
| US7325184B2 (en) | 1997-06-30 | 2008-01-29 | Matsushita Electric Industrial Co., Ltd. | Communications digital signal processor and digital signal processing method |
| US6792570B2 (en) | 2000-05-12 | 2004-09-14 | Nec Corporation | Viterbi decoder with high speed processing function |
| KR100834663B1 (ko) * | 2002-03-11 | 2008-06-02 | 삼성전자주식회사 | 직접 메모리 접근을 이용한 비터비 복호기 및 비터비 복호 방법 |
| US7392463B2 (en) | 2003-06-06 | 2008-06-24 | Fujitsu Limited | Data reproducing apparatus avoiding selection of incorrect path |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| EP1156588B1 (en) | Method and apparatus for maximum a posteriori probability decoding | |
| US7234100B1 (en) | Decoder for trellis-based channel encoding | |
| JP2005045727A (ja) | ビタビ復号器 | |
| US6601215B1 (en) | Traceback buffer management for VLSI Viterbi decoders | |
| US6792570B2 (en) | Viterbi decoder with high speed processing function | |
| US7062701B2 (en) | Method for storing path metrics in a viterbi decoder | |
| JPH10209882A (ja) | ビタビ復号方法 | |
| US8489972B2 (en) | Decoding method and decoding device | |
| KR100262303B1 (ko) | 비터비알고리즘을적용하는복호과정에서의생존경로역추적방법및그장치 | |
| JP2798123B2 (ja) | ビタビ復号装置 | |
| US7263653B2 (en) | Algorithm for a memory-based Viterbi decoder | |
| JPH06284018A (ja) | ビタビ復号方法および誤り訂正復号化装置 | |
| US20040190651A1 (en) | Decoding a signal encoded with a convolutional code | |
| US7231586B2 (en) | Multi-rate viterbi decoder | |
| CN102282771B (zh) | 解码方法 | |
| US6904105B1 (en) | Method and implemention of a traceback-free parallel viterbi decoder | |
| JP3231647B2 (ja) | ビタビ復号器 | |
| JP3235333B2 (ja) | ビタビ復号方法およびビタビ復号化装置 | |
| JP4295871B2 (ja) | 誤り訂正復号器 | |
| JP5196567B2 (ja) | 演算装置、復号化装置およびメモリ制御方法ならびにプログラム | |
| JP2004153319A (ja) | ビタビ復号装置 | |
| JP3288328B2 (ja) | ビタビ復号器のトレースバック処理の高速化装置およびその高速化方法 | |
| US20070168845A1 (en) | Viterbi decoder | |
| JP2002076924A (ja) | ビタビ復号器 | |
| JPH06303153A (ja) | ビタビ復号器 |