JPH0144058B2 - - Google Patents
Info
- Publication number
- JPH0144058B2 JPH0144058B2 JP59028488A JP2848884A JPH0144058B2 JP H0144058 B2 JPH0144058 B2 JP H0144058B2 JP 59028488 A JP59028488 A JP 59028488A JP 2848884 A JP2848884 A JP 2848884A JP H0144058 B2 JPH0144058 B2 JP H0144058B2
- Authority
- JP
- Japan
- Prior art keywords
- path
- output
- selector
- internal state
- path metric
- 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
Classifications
-
- 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
- H03M13/41—Sequence estimation, i.e. using statistical methods for the reconstruction of the original codes using the Viterbi algorithm or Viterbi processors
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)
Description
【発明の詳細な説明】
発明の技術分野
本発明は、畳み込み符号の最尤復号法を適用し
たビタビ復号器に於いて、高速処理を可能とした
パイプライン処理ビタビ復号器に関するものであ
る。
たビタビ復号器に於いて、高速処理を可能とした
パイプライン処理ビタビ復号器に関するものであ
る。
従来技術と問題点
ビタビ（viterbi）復号器は、畳み込み符号の
最尤復号法（maximum likelihood decoding）
に使用されるものであり、既知の複数個の符号系
列のうち、受信符号系列に最も符号距離が近いパ
スを最尤パスとして選択し、そのパスに対応する
復号データを得る復号器である。又畳み込み符号
（convolutional codes）は、或るシンボルを入力
した時の出力が、その時点から何シンボルか前ま
での入力全体の影響を受けて生成される符号であ
り、或るシンボル自体を含めて、何グループの出
力に影響を与えるかを拘束長と称するものであ
る。この拘束長が大きくなる程、誤り訂正能力が
向上するものであるが、復号器の回路規模が指数
関数的に増大する。
最尤復号法（maximum likelihood decoding）
に使用されるものであり、既知の複数個の符号系
列のうち、受信符号系列に最も符号距離が近いパ
スを最尤パスとして選択し、そのパスに対応する
復号データを得る復号器である。又畳み込み符号
（convolutional codes）は、或るシンボルを入力
した時の出力が、その時点から何シンボルか前ま
での入力全体の影響を受けて生成される符号であ
り、或るシンボル自体を含めて、何グループの出
力に影響を与えるかを拘束長と称するものであ
る。この拘束長が大きくなる程、誤り訂正能力が
向上するものであるが、復号器の回路規模が指数
関数的に増大する。
この拘束長をＫとし、Ｋ＝３の畳み込み符号を
生成する符号器の一例を第１図に示す。同図に於
いて、１は入力端子、２は３段のシフトレジス
タ、３，４は法２の加算器、５は切換スイツチ、
６は出力端子である。情報系列の１ビツトが入力
端子１からシフトレジスタ２に加えられると、そ
れ以前に入力された２ビツトが加算器３，４の出
力に影響を与えることになり、従つて、入力シン
ボルは３グループの出力に影響を与えるので、拘
束長Ｋは３となる。又加算器３，４の出力は、切
換スイツチ５の切換えにより出力端子６へ出力さ
れ、情報系列の１ビツト入力に対して、符号系列
の２ビツトが出力されることになる。例えば、シ
フトレジスタ２の各段が“０”の場合に、情報系
列が“1001”であると、符号系列は“11101111”
となる。
生成する符号器の一例を第１図に示す。同図に於
いて、１は入力端子、２は３段のシフトレジス
タ、３，４は法２の加算器、５は切換スイツチ、
６は出力端子である。情報系列の１ビツトが入力
端子１からシフトレジスタ２に加えられると、そ
れ以前に入力された２ビツトが加算器３，４の出
力に影響を与えることになり、従つて、入力シン
ボルは３グループの出力に影響を与えるので、拘
束長Ｋは３となる。又加算器３，４の出力は、切
換スイツチ５の切換えにより出力端子６へ出力さ
れ、情報系列の１ビツト入力に対して、符号系列
の２ビツトが出力されることになる。例えば、シ
フトレジスタ２の各段が“０”の場合に、情報系
列が“1001”であると、符号系列は“11101111”
となる。
符号器に、一度に入力される情報系列のビツト
数をｂ、一度に出力される符号系列のビツト数を
ｎ、ｂ／ｎを符号化率（code ratio）Ｒとする
と、第１図に示す符号器は、ｂ＝１、ｎ＝２であ
るから、Ｒ＝１／２となる。この符号化率を大き
くする程、誤り訂正能力は低下するが、情報転送
レートは高くなる。
数をｂ、一度に出力される符号系列のビツト数を
ｎ、ｂ／ｎを符号化率（code ratio）Ｒとする
と、第１図に示す符号器は、ｂ＝１、ｎ＝２であ
るから、Ｒ＝１／２となる。この符号化率を大き
くする程、誤り訂正能力は低下するが、情報転送
レートは高くなる。
第２図は、第１図の符号器の格子状表現による
内部状態遷移説明図であり、白矢印は入力ビツト
が“０”、黒矢印は入力ビツトが“１”の場合の
遷移方向を示し、その入力ビツトが３段シフトレ
ジスタ２の第１段に入力された時、第２段と第３
段とに前に入力された情報系列の２ビツトが残つ
ているので、この残存している２ビツトにより、
内部状態が表され、“00”、“10”、“01”、“11”の
４種類となる。又括弧内は、入力ビツトが“１”
か“０”かにより出力される２ビツトの符号出力
を示す。
内部状態遷移説明図であり、白矢印は入力ビツト
が“０”、黒矢印は入力ビツトが“１”の場合の
遷移方向を示し、その入力ビツトが３段シフトレ
ジスタ２の第１段に入力された時、第２段と第３
段とに前に入力された情報系列の２ビツトが残つ
ているので、この残存している２ビツトにより、
内部状態が表され、“00”、“10”、“01”、“11”の
４種類となる。又括弧内は、入力ビツトが“１”
か“０”かにより出力される２ビツトの符号出力
を示す。
例えば、内部状態が“00”のａに於いて、入力
ビツトが“１”であると、符号出力は（１、１）
として示すように、“11”が出力され、内部状態
は“00”から“10”のｂに遷移する。次の入力ビ
ツトが“０”であると、符号出力は“10”とな
り、内部状態は“10”から“01”のｃに遷移す
る。次に“０”が入力されると、符号出力は
“11”となり、内部状態は“01”から“00”のｄ
に遷移する。次に“１”が入力されると、符号出
力は“11”となり、内部状態は、“00”から“10”
のｆに遷移する。従つて、情報系列の“1001”
は、符号系列の“11101111”に変換されることに
なる。
ビツトが“１”であると、符号出力は（１、１）
として示すように、“11”が出力され、内部状態
は“00”から“10”のｂに遷移する。次の入力ビ
ツトが“０”であると、符号出力は“10”とな
り、内部状態は“10”から“01”のｃに遷移す
る。次に“０”が入力されると、符号出力は
“11”となり、内部状態は“01”から“00”のｄ
に遷移する。次に“１”が入力されると、符号出
力は“11”となり、内部状態は、“00”から“10”
のｆに遷移する。従つて、情報系列の“1001”
は、符号系列の“11101111”に変換されることに
なる。
又入力ビツトが“０”の連続の場合は、符号出
力は“00”となり、内部状態はａ，ｇ，ｈ，ｄの
ように同じ状態の遷移となる。
力は“00”となり、内部状態はａ，ｇ，ｈ，ｄの
ように同じ状態の遷移となる。
第３図は、前述の符号系列を復号するビタビ復
号器のブロツク図であり、１１は分配器、１２ａ
〜１２ｄは演算回路、１３ａ〜１３ｄはパスメモ
リ、１４はパスセレクタ、１５ａ〜１５ｄはパス
メトリツク値を転送するデータ線、１６ａ〜１６
ｄはパス選択情報を転送する信号線である。受信
符号は分配器１１により各演算回路１２ａ〜１２
ｄに分配される。各演算回路１２ａ〜１２ｄは、
加算器（Adder）、比較器（Comparator）、セレ
クタ（Selector）を含むものであり、ACS回路と
称され、前述の符号器の内部状態の“00”、“10”、
“01”、“11”に対応するものである。従つて、各
演算回路１２ａ〜１２ｄは、第２図の内部状態遷
移説明図に於けるパスに対応した相互の接続が行
われている。
号器のブロツク図であり、１１は分配器、１２ａ
〜１２ｄは演算回路、１３ａ〜１３ｄはパスメモ
リ、１４はパスセレクタ、１５ａ〜１５ｄはパス
メトリツク値を転送するデータ線、１６ａ〜１６
ｄはパス選択情報を転送する信号線である。受信
符号は分配器１１により各演算回路１２ａ〜１２
ｄに分配される。各演算回路１２ａ〜１２ｄは、
加算器（Adder）、比較器（Comparator）、セレ
クタ（Selector）を含むものであり、ACS回路と
称され、前述の符号器の内部状態の“00”、“10”、
“01”、“11”に対応するものである。従つて、各
演算回路１２ａ〜１２ｄは、第２図の内部状態遷
移説明図に於けるパスに対応した相互の接続が行
われている。
内部状態の遷移径路をパスと称し、そのパスの
受信符号系列との符号距離（ハミング距離
Hamming distance）をパスメトリツク（path
metric）と称するものであり、受信符号系列に
最も近い方のパスを生き残りパスとして選択し、
この生き残りパスの選択情報を信号線１６ａ〜１
６ｄを介してパスメモリ１３ａ〜１３ｄに転送し
て記憶させておき、各演算回路１２ａ〜１２ｄが
選択した生き残りパスのうちの最も受信符号系列
に近いもの、即ちパスメトリツク値が最小のパス
がパスセレクタ１４により選択され、パスセレク
タ１４から復号出力が得られるものである。
受信符号系列との符号距離（ハミング距離
Hamming distance）をパスメトリツク（path
metric）と称するものであり、受信符号系列に
最も近い方のパスを生き残りパスとして選択し、
この生き残りパスの選択情報を信号線１６ａ〜１
６ｄを介してパスメモリ１３ａ〜１３ｄに転送し
て記憶させておき、各演算回路１２ａ〜１２ｄが
選択した生き残りパスのうちの最も受信符号系列
に近いもの、即ちパスメトリツク値が最小のパス
がパスセレクタ１４により選択され、パスセレク
タ１４から復号出力が得られるものである。
第４図は、従来の演算回路１２ａ〜１２ｄのブ
ロツク図であり、２１，２２は加算器、２３は比
較器、２４はセレクタ、２５はメトリツクメモ
リ、２６はフリツプフロツプ、２７はクロツクで
あり、又１１は分配器、１２は演算回路、１５は
データ線、１６は信号線にそれぞれ接続されるこ
とを示す。加算器２１，２２に於いてパスメトリ
ツク値を加算し、比較器２３に於いて加算された
パスメトリツク値の大小を比較し、小さい方を選
択するようにセレクタ２４を制御し、且つ選択情
報をフリツプフロツプ２６のデータ端子Ｄに加
え、クロツク端子Ｃに加えられるクロツクにより
セツトし、出力端子Ｑからパス選択情報として信
号線に送出する。又セレクタ２４で選択されたパ
スメトリツク値は、メトリツクメモリ２５にクロ
ツクのタイミングにより書込まれ、データ線にパ
スメトリツク値として出力され、パスセレクタ１
４及び次段の演算回路へ転送されるものである。
ロツク図であり、２１，２２は加算器、２３は比
較器、２４はセレクタ、２５はメトリツクメモ
リ、２６はフリツプフロツプ、２７はクロツクで
あり、又１１は分配器、１２は演算回路、１５は
データ線、１６は信号線にそれぞれ接続されるこ
とを示す。加算器２１，２２に於いてパスメトリ
ツク値を加算し、比較器２３に於いて加算された
パスメトリツク値の大小を比較し、小さい方を選
択するようにセレクタ２４を制御し、且つ選択情
報をフリツプフロツプ２６のデータ端子Ｄに加
え、クロツク端子Ｃに加えられるクロツクにより
セツトし、出力端子Ｑからパス選択情報として信
号線に送出する。又セレクタ２４で選択されたパ
スメトリツク値は、メトリツクメモリ２５にクロ
ツクのタイミングにより書込まれ、データ線にパ
スメトリツク値として出力され、パスセレクタ１
４及び次段の演算回路へ転送されるものである。
例えば、受信符号系列が“11101111”の場合、
第２図を参照すると、最初は内部状態ａから内部
状態ｂ，ｇに遷移することになるが、受信符号系
列の“11”については、内部状態ｂへ遷移するパ
スのメトリツク値は０、内部状態ｇへ遷移するパ
スのメトリツク値は２となる。次の受信符号系列
の“10”については、内部状態ｂから内部状態ｃ
へ遷移するパスのメトリツク値は０であるが、内
部状態ｇから内部状態ｈに遷移するパスのメトリ
ツク値は１となる。又次の受信符号系列の“11”
については、内部状態ｃから内部状態ｄに遷移す
るパスのメトリツク値は０であるが、内部状態ｈ
から内部状態ｄに遷移するパスのメトリツク値は
２となる。
第２図を参照すると、最初は内部状態ａから内部
状態ｂ，ｇに遷移することになるが、受信符号系
列の“11”については、内部状態ｂへ遷移するパ
スのメトリツク値は０、内部状態ｇへ遷移するパ
スのメトリツク値は２となる。次の受信符号系列
の“10”については、内部状態ｂから内部状態ｃ
へ遷移するパスのメトリツク値は０であるが、内
部状態ｇから内部状態ｈに遷移するパスのメトリ
ツク値は１となる。又次の受信符号系列の“11”
については、内部状態ｃから内部状態ｄに遷移す
るパスのメトリツク値は０であるが、内部状態ｈ
から内部状態ｄに遷移するパスのメトリツク値は
２となる。
この場合、同一の内部状態ｄとなるものである
が、パスによつてメトリツク値が相違し、加算さ
れたパスメトリツク値は、ａ，ｂ，ｃ，ｄのパス
については０であるが、ａ，ｇ，ｈ，ｄのパスに
ついては５となる。従つて、パスメトリツク値の
最小のパスが受信符号系列に最も近いパスである
から、このパスａ，ｂ，ｃ，ｄを辿つて内部状態
ａに戻つた時、内部状態ａに於ける復号出力は、
内部状態ｂに遷移させる“１”であるとして、パ
スセレクタ１４から出力されることになる。
が、パスによつてメトリツク値が相違し、加算さ
れたパスメトリツク値は、ａ，ｂ，ｃ，ｄのパス
については０であるが、ａ，ｇ，ｈ，ｄのパスに
ついては５となる。従つて、パスメトリツク値の
最小のパスが受信符号系列に最も近いパスである
から、このパスａ，ｂ，ｃ，ｄを辿つて内部状態
ａに戻つた時、内部状態ａに於ける復号出力は、
内部状態ｂに遷移させる“１”であるとして、パ
スセレクタ１４から出力されることになる。
次の受信符号系列の“11”については、内部状
態ｄから内部状態ｆに遷移することになる。この
場合も他のパスについてのメトリツク値を演算し
て、パスメトリツク値の最小のパスを逆に辿つ
て、例えば、内部状態ｂに於ける復号出力を、内
部状態ｃに遷移させる“０”として出力すること
になる。
態ｄから内部状態ｆに遷移することになる。この
場合も他のパスについてのメトリツク値を演算し
て、パスメトリツク値の最小のパスを逆に辿つ
て、例えば、内部状態ｂに於ける復号出力を、内
部状態ｃに遷移させる“０”として出力すること
になる。
前述のように、１復号サイクルに於いて、二つ
のパスのパスメトリツク値を計算し、その計算結
果を比較して、パスメトリツク値の小さい方を生
き残りパスとして選択し、選択したパスのパスメ
トリツク値をメトリツクメモリ２５に記憶させる
ものであり、この記憶されたパスメトリツク値
は、次の復号サイクルで、パスメトリツク値の計
算に使用されるものである。従つて、１復号サイ
クル内にパスメトリツク値の計算と比較とを終了
させなければならないので、加算器と比較器との
遅延によつて、ビタビ復号器のスループツトが制
限される欠点があつた。
のパスのパスメトリツク値を計算し、その計算結
果を比較して、パスメトリツク値の小さい方を生
き残りパスとして選択し、選択したパスのパスメ
トリツク値をメトリツクメモリ２５に記憶させる
ものであり、この記憶されたパスメトリツク値
は、次の復号サイクルで、パスメトリツク値の計
算に使用されるものである。従つて、１復号サイ
クル内にパスメトリツク値の計算と比較とを終了
させなければならないので、加算器と比較器との
遅延によつて、ビタビ復号器のスループツトが制
限される欠点があつた。
発明の目的
本発明は、パスメトリツクの計算と比較とを並
列的に実行させて、スループツトを向上させるこ
とを目的とするものである。
列的に実行させて、スループツトを向上させるこ
とを目的とするものである。
発明の構成
本発明は、パスメトリツク値の演算を行う複数
の演算回路と、該演算回路でパスメトリツク値の
小さいパスを選択したパス選択情報を記憶するパ
スメモリと、該パスメモリの内容及び前記演算回
路の出力のパスメトリツク値とにより復号信号を
出力するパスセレクタとを備えたビタビ復号器に
於いて、前記演算回路は、パスメトリツク値の加
算を行う加算器と、加算出力を選択するセレクタ
と、前記加算器により次のパスメトリツク値の加
算を行つている時に前記セレクタで選択された加
算出力のパスメトリツク値を比較してパス選択情
報を出力する比較器とを備えているものであり、
以下実施例について詳細に説明する。
の演算回路と、該演算回路でパスメトリツク値の
小さいパスを選択したパス選択情報を記憶するパ
スメモリと、該パスメモリの内容及び前記演算回
路の出力のパスメトリツク値とにより復号信号を
出力するパスセレクタとを備えたビタビ復号器に
於いて、前記演算回路は、パスメトリツク値の加
算を行う加算器と、加算出力を選択するセレクタ
と、前記加算器により次のパスメトリツク値の加
算を行つている時に前記セレクタで選択された加
算出力のパスメトリツク値を比較してパス選択情
報を出力する比較器とを備えているものであり、
以下実施例について詳細に説明する。
発明の実施例
第５図は、本発明の一実施例のビタビ復号器の
１個の演算回路のブロツク図であり、３１〜３４
は加算器、３５，３６は比較器、３７，３８はセ
レクタ、３９，４０はメトリツクメモリ、４１は
比較器、４２はフリツプフロツプ、４３はクロツ
ク、４４，４５はパスメトリツク値出力、４６は
パス選択情報であつて、演算回路１２ｉ，１２ｊ
からのパスが合流するものとすると、加算器３
１，３２は分配器１１と演算回路１２ｉとから入
力され、加算器３３は分配器１１と演算回路１２
ｊとから入力されて、パスメトリツク値の加算が
行われる。この時、比較器３５，３６に於いて、
それぞれ演算回路１２ｉ，１２ｊからのパスメト
リツク値が比較され、小さい方を選択する。即
ち、加算器３１〜３４でパスメトリツク値の加算
を行うと同時に加算器３１〜３４へ入力されるパ
スメトリツク値の比較を比較器３５，３６で行
い、比較結果によりセレクタ３７，３８が制御さ
れて生き残りパスの選択が行われ、生き残りパス
のパスメトリツク値がメトリツクメモリ３９，４
０に加えられ、クロツク４３のタイミングで書込
まれる。
１個の演算回路のブロツク図であり、３１〜３４
は加算器、３５，３６は比較器、３７，３８はセ
レクタ、３９，４０はメトリツクメモリ、４１は
比較器、４２はフリツプフロツプ、４３はクロツ
ク、４４，４５はパスメトリツク値出力、４６は
パス選択情報であつて、演算回路１２ｉ，１２ｊ
からのパスが合流するものとすると、加算器３
１，３２は分配器１１と演算回路１２ｉとから入
力され、加算器３３は分配器１１と演算回路１２
ｊとから入力されて、パスメトリツク値の加算が
行われる。この時、比較器３５，３６に於いて、
それぞれ演算回路１２ｉ，１２ｊからのパスメト
リツク値が比較され、小さい方を選択する。即
ち、加算器３１〜３４でパスメトリツク値の加算
を行うと同時に加算器３１〜３４へ入力されるパ
スメトリツク値の比較を比較器３５，３６で行
い、比較結果によりセレクタ３７，３８が制御さ
れて生き残りパスの選択が行われ、生き残りパス
のパスメトリツク値がメトリツクメモリ３９，４
０に加えられ、クロツク４３のタイミングで書込
まれる。
メトリツクメモリ３９，４０の記憶内容は、次
段の演算回路へパスメトリツク値として出力さ
れ、且つ比較器４１により比較されて、パス選択
情報が出力され、フリツプフロツプ４２のデータ
端子Ｄに加えられる。このフリツプフロツプ４２
のクロツク端子Ｃにはクロツク４３が加えられ、
セツトされたパス選択情報は出力端子Ｑから出力
されて、パスメモリ（第３図の符号１３ａ〜１３
ｄ参照）に転送されて記憶される。このパス選択
情報４６を出力する為の比較動作が比較器４１に
於いて行われている時、次のパスメトリツク値の
加算が加算器３１〜３４に於いて行われるもので
ある。
段の演算回路へパスメトリツク値として出力さ
れ、且つ比較器４１により比較されて、パス選択
情報が出力され、フリツプフロツプ４２のデータ
端子Ｄに加えられる。このフリツプフロツプ４２
のクロツク端子Ｃにはクロツク４３が加えられ、
セツトされたパス選択情報は出力端子Ｑから出力
されて、パスメモリ（第３図の符号１３ａ〜１３
ｄ参照）に転送されて記憶される。このパス選択
情報４６を出力する為の比較動作が比較器４１に
於いて行われている時、次のパスメトリツク値の
加算が加算器３１〜３４に於いて行われるもので
ある。
第６図は動作説明図であり、ａはクロツク４３
を示し、周期ｔ１，ｔ２，ｔ３，…の各１周期が
１復号サイクルとなる。又ｂは分配器出力、ｃは
パスメトリツク値入力、ｄは加算器３１〜３４の
出力、ｅはパスメトリツク値出力、ｆは比較器４
１の出力を示す。従来は、この１復号サイクル内
で加算及び比較を行うものであるが、本発明に於
いては、１復号サイクルで、或る受信符号系列に
ついてのパスメトリツク値の加算を行うと同時
に、他の受信符号系列についてのパスメトリツク
値の比較を行うものであり、次の復号サイクルで
加算結果の比較を行つて、パス選択情報を出力す
るものである。即ち、パイプライン処理的に、加
算と比較とが実行されるものである。
を示し、周期ｔ１，ｔ２，ｔ３，…の各１周期が
１復号サイクルとなる。又ｂは分配器出力、ｃは
パスメトリツク値入力、ｄは加算器３１〜３４の
出力、ｅはパスメトリツク値出力、ｆは比較器４
１の出力を示す。従来は、この１復号サイクル内
で加算及び比較を行うものであるが、本発明に於
いては、１復号サイクルで、或る受信符号系列に
ついてのパスメトリツク値の加算を行うと同時
に、他の受信符号系列についてのパスメトリツク
値の比較を行うものであり、次の復号サイクルで
加算結果の比較を行つて、パス選択情報を出力す
るものである。即ち、パイプライン処理的に、加
算と比較とが実行されるものである。
例えば、ｔ１の周期に於いて、斜線を施した受
信符号系列の分配器出力と演算回路の出力のパス
メトリツク値入力とを加算器３１〜３４で加算す
ることによりｄに示すように加算器出力が得られ
る。この加算器出力は、次の周期ｔ２に於いてメ
トリツクメモリ３９，４０を介してｅに示すよう
に出力される。このパスメトリツク値出力は比較
器４１により比較され、ｆに示すように比較器出
力がパス選択情報PSとして出力される。即ち斜
線部分を矢印のように経由してパス選択情報PS
が出力され、２復号サイクルを用いてパス選択情
報PSが出力され、パスメモリに記憶されること
になる。
信符号系列の分配器出力と演算回路の出力のパス
メトリツク値入力とを加算器３１〜３４で加算す
ることによりｄに示すように加算器出力が得られ
る。この加算器出力は、次の周期ｔ２に於いてメ
トリツクメモリ３９，４０を介してｅに示すよう
に出力される。このパスメトリツク値出力は比較
器４１により比較され、ｆに示すように比較器出
力がパス選択情報PSとして出力される。即ち斜
線部分を矢印のように経由してパス選択情報PS
が出力され、２復号サイクルを用いてパス選択情
報PSが出力され、パスメモリに記憶されること
になる。
第７図は、本発明の他の実施例のビタビ復号器
の１個の演算回路のブロツク図であり、比較器を
１個で済むようにしたものである。同図に於い
て、５１〜５４は加算器、５５，５６はセレク
タ、５７，５８はメトリツクメモリ、５９は比較
器、６０はフリツプフロツプ、６１はクロツク、
６２，６３はパスメトリツク値出力、６４はパス
選択情報、６５は次のパスメトリツク値の演算回
路へ加える比較出力である。
の１個の演算回路のブロツク図であり、比較器を
１個で済むようにしたものである。同図に於い
て、５１〜５４は加算器、５５，５６はセレク
タ、５７，５８はメトリツクメモリ、５９は比較
器、６０はフリツプフロツプ、６１はクロツク、
６２，６３はパスメトリツク値出力、６４はパス
選択情報、６５は次のパスメトリツク値の演算回
路へ加える比較出力である。
この実施例に於いても、演算回路１２ｉ，１２
ｊからのパスが合流され、分配器１１と演算回路
１２ｉとから加算器５１，５２に入力されてパス
メトリツク値の加算が行われ、加算出力はセレク
タ５５に加えられ、演算回路１２ｉからの比較出
力がセレクタ５５の制御信号として加えられてパ
ス選択が行われる。
ｊからのパスが合流され、分配器１１と演算回路
１２ｉとから加算器５１，５２に入力されてパス
メトリツク値の加算が行われ、加算出力はセレク
タ５５に加えられ、演算回路１２ｉからの比較出
力がセレクタ５５の制御信号として加えられてパ
ス選択が行われる。
又分配器１１と演算回路１２ｊとから加算器５
３，５４に入力されてパスメトリツク値の加算が
行われ、加算出力はセレクタ５６に加えられ、演
算回路１２ｊからの比較出力がセレクタ５６に制
御信号として加えられてパス選択が行われる。
３，５４に入力されてパスメトリツク値の加算が
行われ、加算出力はセレクタ５６に加えられ、演
算回路１２ｊからの比較出力がセレクタ５６に制
御信号として加えられてパス選択が行われる。
加算器５１〜５４に於けるパスメトリツク値の
加算を実行している時、その前に演算されたパス
メトリツク値出力６２，６３を比較器５９で比較
し、パスメトリツク値の小さい方を選択し、比較
出力６５を次の加算器出力の選択の為の制御信号
として、次の演算を行う演算回路へ転送し、その
演算回路のセレクタ５５，５６に加えるものであ
り、前述の実施例と同様にパイプライン処理によ
り、パスメトリツク値の加算と比較とが実行され
ることになる。
加算を実行している時、その前に演算されたパス
メトリツク値出力６２，６３を比較器５９で比較
し、パスメトリツク値の小さい方を選択し、比較
出力６５を次の加算器出力の選択の為の制御信号
として、次の演算を行う演算回路へ転送し、その
演算回路のセレクタ５５，５６に加えるものであ
り、前述の実施例と同様にパイプライン処理によ
り、パスメトリツク値の加算と比較とが実行され
ることになる。
この実施例と前述の第５図の実施例とを比較す
ると、第５図の実施例では、前段のパスメトリツ
ク値が入力されて比較器３５，３６で比較し、セ
レクタ３７，３８を制御するものであつたが、第
７図の実施例では、前段のパスメトリツク値出力
６２，６３の比較が比較器５９で行われるので、
その比較出力を次段の演算回路に於けるセレクタ
５５，５６の制御を行うように転送するものであ
り、比較器が１個で済む利点がある。なお前述の
実施例にのみ限定されるものではなく、種々付加
変更し得るものであり、例えば、前述と異なる符
号化率の復号にも適用することが可能である。
ると、第５図の実施例では、前段のパスメトリツ
ク値が入力されて比較器３５，３６で比較し、セ
レクタ３７，３８を制御するものであつたが、第
７図の実施例では、前段のパスメトリツク値出力
６２，６３の比較が比較器５９で行われるので、
その比較出力を次段の演算回路に於けるセレクタ
５５，５６の制御を行うように転送するものであ
り、比較器が１個で済む利点がある。なお前述の
実施例にのみ限定されるものではなく、種々付加
変更し得るものであり、例えば、前述と異なる符
号化率の復号にも適用することが可能である。
発明の効果
以上説明したように、本発明は、パスメトリツ
ク値の演算を行う複数の演算回路１２ａ〜１２ｄ
と、演算回路１２ａ〜１２ｄでパスメトリツク値
の小さいパスを選択したパス選択情報を記憶する
パスメモリ１３ａ〜１３ｄと、パスメモリ１３ａ
〜１３ｄの内容及び前記演算回路１２ａ〜１２ｄ
の出力のパスメトリツク値とにより復号信号を出
力するパスセレクタ１４とを備えたビタビ復号器
に於いて、演算回路１２ａ〜１２ｄを、パスメト
リツク値の加算を行う加算器３１〜３４，５１〜
５４と、加算出力を選択するセレクタ３７，３
８，５５，５６と、前記加算器３１〜３４，５１
〜５４により次のパスメトリツク値の加算を行つ
ている時に前記セレクタ３７，３８，５５，５６
で選択された加算出力のパスメトリツク値を比較
してパス選択情報を出力する比較器４１，５９と
により構成して、加算器で加算している復号サイ
クルでは、比較器で前の加算出力のパスメトリツ
ク値の比較を行うようにしたもので、パイプライ
ン処理となるので、ビタビ復号器のスループツト
を向上することができるものである。
ク値の演算を行う複数の演算回路１２ａ〜１２ｄ
と、演算回路１２ａ〜１２ｄでパスメトリツク値
の小さいパスを選択したパス選択情報を記憶する
パスメモリ１３ａ〜１３ｄと、パスメモリ１３ａ
〜１３ｄの内容及び前記演算回路１２ａ〜１２ｄ
の出力のパスメトリツク値とにより復号信号を出
力するパスセレクタ１４とを備えたビタビ復号器
に於いて、演算回路１２ａ〜１２ｄを、パスメト
リツク値の加算を行う加算器３１〜３４，５１〜
５４と、加算出力を選択するセレクタ３７，３
８，５５，５６と、前記加算器３１〜３４，５１
〜５４により次のパスメトリツク値の加算を行つ
ている時に前記セレクタ３７，３８，５５，５６
で選択された加算出力のパスメトリツク値を比較
してパス選択情報を出力する比較器４１，５９と
により構成して、加算器で加算している復号サイ
クルでは、比較器で前の加算出力のパスメトリツ
ク値の比較を行うようにしたもので、パイプライ
ン処理となるので、ビタビ復号器のスループツト
を向上することができるものである。
又複数復号サイクル毎にパス選択を行う並列処
理方式に於いては、ACS回路の周辺のブランチ
メトリツク計算回路やパスメモリ回路が複雑とな
るが、本発明に於いては、パイプライン処理を行
うものであるから、従来例のブランチメトリツク
計算回路やパスメモリ回路をそのまま使用するこ
とが可能となり、経済的な構成により復号速度の
向上を図ることができる。
理方式に於いては、ACS回路の周辺のブランチ
メトリツク計算回路やパスメモリ回路が複雑とな
るが、本発明に於いては、パイプライン処理を行
うものであるから、従来例のブランチメトリツク
計算回路やパスメモリ回路をそのまま使用するこ
とが可能となり、経済的な構成により復号速度の
向上を図ることができる。
第１図は畳み込み符号の符号器のブロツク図、
第２図は符号器の内部状態遷移説明図、第３図は
ビタビ復号器のブロツク図、第４図は従来のビタ
ビ復号器の演算回路のブロツク図、第５図は本発
明の一実施例のビタビ復号器の演算回路のブロツ
ク図、第６図は動作説明図、第７図は本発明の他
の実施例のビタビ復号器の演算回路のブロツク図
である。 １１は分配器、１２ａ〜１２ｄは演算回路、１
３ａ〜１３ｄはパスメモリ、１４はパスセレク
タ、３１〜３４，５１〜５４は加算器、３５，３
６，４１，５９は比較器、３７，３８，５５，５
６はセレクタ、３９，４０，５７，５８はメトリ
ツクメモリ、４２，６０はフリツプフロツプであ
る。
第２図は符号器の内部状態遷移説明図、第３図は
ビタビ復号器のブロツク図、第４図は従来のビタ
ビ復号器の演算回路のブロツク図、第５図は本発
明の一実施例のビタビ復号器の演算回路のブロツ
ク図、第６図は動作説明図、第７図は本発明の他
の実施例のビタビ復号器の演算回路のブロツク図
である。 １１は分配器、１２ａ〜１２ｄは演算回路、１
３ａ〜１３ｄはパスメモリ、１４はパスセレク
タ、３１〜３４，５１〜５４は加算器、３５，３
６，４１，５９は比較器、３７，３８，５５，５
６はセレクタ、３９，４０，５７，５８はメトリ
ツクメモリ、４２，６０はフリツプフロツプであ
る。
Claims (1)
- １ パスメトリツク値の演算を行う複数の演算回
路と、該演算回路でパスメトリツク値の小さいパ
スを選択したパス選択情報を記憶するパスメモリ
と、該パスメモリの内容及び前記演算回路の出力
のパスメトリツク値とにより復号信号を出力する
パスセレクタとを備えたビタビ復号器に於いて、
前記演算回路は、パスメトリツク値の加算を行う
加算器と、加算出力を選択するセレクタと、前記
加算器により次のパスメトリツク値の加算を行つ
ている時に前記セレクタで選択された加算出力の
パスメトリツク値を比較してパス選択情報を出力
する比較器とを備えていることを特徴とするパイ
プライン処理ビタビ復号器。
Priority Applications (5)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP59028488A JPS60173930A (ja) | 1984-02-20 | 1984-02-20 | パイプライン処理ビタビ復号器 |
| US06/701,504 US4614933A (en) | 1984-02-20 | 1985-02-14 | Viterbi decoder with the pipeline processing function |
| CA000474471A CA1248236A (en) | 1984-02-20 | 1985-02-15 | Viterbi decoder with the pipeline processing function |
| EP85101836A EP0152947B1 (en) | 1984-02-20 | 1985-02-20 | Viterbi decoder with the pipeline processing function |
| DE8585101836T DE3578289D1 (de) | 1984-02-20 | 1985-02-20 | Viterbi-dekoder mit pipeline-verarbeitungsfunktion. |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP59028488A JPS60173930A (ja) | 1984-02-20 | 1984-02-20 | パイプライン処理ビタビ復号器 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPS60173930A JPS60173930A (ja) | 1985-09-07 |
| JPH0144058B2 true JPH0144058B2 (ja) | 1989-09-25 |
Family
ID=12250049
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP59028488A Granted JPS60173930A (ja) | 1984-02-20 | 1984-02-20 | パイプライン処理ビタビ復号器 |
Country Status (5)
| Country | Link |
|---|---|
| US (1) | US4614933A (ja) |
| EP (1) | EP0152947B1 (ja) |
| JP (1) | JPS60173930A (ja) |
| CA (1) | CA1248236A (ja) |
| DE (1) | DE3578289D1 (ja) |
Families Citing this family (32)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS60199240A (ja) * | 1984-03-23 | 1985-10-08 | Mitsubishi Electric Corp | たたみ込み符号化ヴイタビ復号回路 |
| JPS62101128A (ja) * | 1985-10-29 | 1987-05-11 | Fujitsu Ltd | ビタビ復号器の試験方法 |
| CA1260143A (en) * | 1986-02-24 | 1989-09-26 | Atsushi Yamashita | Path trace viterbi decoder |
| JPS62233933A (ja) * | 1986-04-03 | 1987-10-14 | Toshiba Corp | ヴイタビ復号法 |
| GB8609711D0 (en) * | 1986-04-21 | 1986-05-29 | Clark A P | Channel estimation & detection |
| US4707681A (en) * | 1986-04-24 | 1987-11-17 | International Business Machines Corporation | Method and apparatus for implementing optimum PRML codes |
| DE3721884A1 (de) * | 1987-07-02 | 1989-01-12 | Meyr Heinrich Prof Dr | Verfahren zur ausfuehrung des viterbi-algorithmus mit hilfe parallelverarbeitender strukturen |
| DE3911999A1 (de) * | 1989-04-12 | 1990-10-18 | Philips Patentverwaltung | Uebertragungssystem |
| US5448583A (en) * | 1989-08-28 | 1995-09-05 | Fujitsu Limited | Apparatus and method using analog viterbi decoding techniques |
| US5136593A (en) * | 1989-10-30 | 1992-08-04 | Carnegie-Mellon University | Apparatus and method for fixed delay tree search |
| DE69232647T2 (de) * | 1991-03-20 | 2002-11-28 | Sony Corp., Tokio/Tokyo | Demodulator zur Demodulierung eines pi/4-umgetasteten DQPSK-Signals |
| JPH04358364A (ja) * | 1991-06-05 | 1992-12-11 | Sony Corp | 最尤復号装置 |
| US5377133A (en) * | 1992-04-07 | 1994-12-27 | Digital Equipment Corporation | System for enhanced implementation of add-compare-select (ACS) functions |
| WO1994000843A1 (en) * | 1992-06-26 | 1994-01-06 | Digital Equipment Corporation | Alternative system and method to viterbi detection |
| FR2718865B1 (fr) * | 1994-04-15 | 1996-07-19 | Texas Instruments France | Procédé et dispositif à processeur de signaux numériques pour la mise en Óoeuvre d'un algorithme de Viterbi. |
| CA2147087A1 (en) * | 1995-04-13 | 1996-10-14 | Guy Begin | Method and apparatus for correcting and decoding a sequence of branches representing encoded data bits into estimated information bits |
| JP3280834B2 (ja) * | 1995-09-04 | 2002-05-13 | 沖電気工業株式会社 | 符号化通信方式における信号判定装置および受信装置ならびに信号判定方法および通信路状態推定方法 |
| US5857002A (en) * | 1996-08-16 | 1999-01-05 | International Business Machines Corporation | PRML channel with EPR4 equalization and clocking |
| JPH10107651A (ja) | 1996-09-27 | 1998-04-24 | Nec Corp | ビタビ復号装置 |
| US5987638A (en) * | 1997-04-22 | 1999-11-16 | Lsi Logic Corporation | Apparatus and method for computing the result of a viterbi equation in a single cycle |
| JP3266182B2 (ja) | 1997-06-10 | 2002-03-18 | 日本電気株式会社 | ビタビ復号器 |
| JP3338374B2 (ja) | 1997-06-30 | 2002-10-28 | 松下電器産業株式会社 | 演算処理方法および装置 |
| SG73483A1 (en) * | 1997-12-04 | 2000-06-20 | Motorola Inc | Method and apparatus for maximum likelihood sequence detection |
| US6700881B1 (en) * | 1998-03-02 | 2004-03-02 | Samsung Electronics Co., Ltd. | Rate control device and method for CDMA communication system |
| KR100268450B1 (ko) * | 1998-03-02 | 2000-10-16 | 윤종용 | 테스트기능을 갖는 비터비 디코더 |
| US6148431A (en) * | 1998-03-26 | 2000-11-14 | Lucent Technologies Inc. | Add compare select circuit and method implementing a viterbi algorithm |
| US20050264906A1 (en) * | 2004-05-25 | 2005-12-01 | Haratsch Erich F | Method and apparatus for reduced-state Viterbi detection in a read channel of a magnetic recording system |
| US7185268B2 (en) * | 2003-02-28 | 2007-02-27 | Maher Amer | Memory system and method for use in trellis-based decoding |
| US7050817B2 (en) * | 2003-04-24 | 2006-05-23 | Locus Location Systems, Llc | Locating method and system |
| DE102004038754A1 (de) * | 2004-08-09 | 2006-02-23 | Micronas Gmbh | Decoder und Verfahren zum Durchführen eines Viterbi-Algorithmus |
| CN101390293B (zh) * | 2005-12-22 | 2011-06-08 | 创达特（苏州）科技有限责任公司 | 基于四阶段并行处理的vdsl2维特比代码解码器 |
| US8898552B2 (en) * | 2012-04-24 | 2014-11-25 | Samsung Electronics Co., Ltd. | Communication system with blind decoding mechanism and method of operation thereof |
Family Cites Families (8)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US3789360A (en) * | 1972-10-13 | 1974-01-29 | Harris Intertype Corp | Convolutional decoder |
| US3872432A (en) * | 1974-04-10 | 1975-03-18 | Itt | Synchronization circuit for a viterbi decoder |
| US4087677A (en) * | 1976-09-29 | 1978-05-02 | International Telephone & Telegraph Corporation | Digital PSK modem |
| US4087787A (en) * | 1977-04-19 | 1978-05-02 | Bell Telephone Laboratories, Incorporated | Decoder for implementing an approximation of the Viterbi algorithm using analog processing techniques |
| US4240156A (en) * | 1979-03-29 | 1980-12-16 | Doland George D | Concatenated error correcting system |
| NZ198844A (en) * | 1980-11-14 | 1984-05-31 | Plessey Overseas | Digital information transmission: two dimensional code |
| GB8315363D0 (en) * | 1983-06-03 | 1983-07-06 | Gordon J A | Decoding errorcorrecting codes |
| JPS6081925A (ja) * | 1983-10-12 | 1985-05-10 | Nec Corp | 誤り訂正装置 |
-
1984
- 1984-02-20 JP JP59028488A patent/JPS60173930A/ja active Granted
-
1985
- 1985-02-14 US US06/701,504 patent/US4614933A/en not_active Expired - Lifetime
- 1985-02-15 CA CA000474471A patent/CA1248236A/en not_active Expired
- 1985-02-20 EP EP85101836A patent/EP0152947B1/en not_active Expired
- 1985-02-20 DE DE8585101836T patent/DE3578289D1/de not_active Expired - Lifetime
Also Published As
| Publication number | Publication date |
|---|---|
| EP0152947B1 (en) | 1990-06-13 |
| EP0152947A2 (en) | 1985-08-28 |
| JPS60173930A (ja) | 1985-09-07 |
| CA1248236A (en) | 1989-01-03 |
| EP0152947A3 (en) | 1987-03-11 |
| US4614933A (en) | 1986-09-30 |
| DE3578289D1 (de) | 1990-07-19 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| EP0152947B1 (en) | Viterbi decoder with the pipeline processing function | |
| KR100426712B1 (ko) | 비터비 복호기 | |
| US5446746A (en) | Path memory apparatus of a viterbi decoder | |
| JPH05327524A (ja) | ビット・シリアル・ヴィタービ（ｖｉｔｅｒｂｉ）デコーダの加算／比較／選択アレイ | |
| JPH10107651A (ja) | ビタビ復号装置 | |
| US6523146B1 (en) | Operation processing apparatus and operation processing method | |
| JPH10117149A (ja) | ビタービ復号化器用トレースバック装置及びトレースバック方法 | |
| WO2005011129A1 (ja) | ビタビ復号器 | |
| US5887007A (en) | Viterbi decoding method and viterbi decoding circuit | |
| US6697442B1 (en) | Viterbi decoding apparatus capable of shortening a decoding process time duration | |
| US5878060A (en) | Viterbi decoding apparatus and viterbe decoding method | |
| US6910177B2 (en) | Viterbi decoder using restructured trellis | |
| JP3260714B2 (ja) | ビタビ復号化装置およびビタビ復号化方法 | |
| JP2904271B2 (ja) | ビタビ復号器用パスメモリユニットおよび復号方法 | |
| JP2622014B2 (ja) | ビタビデコーダ | |
| JP3120342B2 (ja) | ビタビ復号器 | |
| JPH0361375B2 (ja) | ||
| KR100531840B1 (ko) | 비터비 디코더의 가지 메트릭 계산 방법 및 그 회로 | |
| JPS60235529A (ja) | ヴイタビ復号装置 | |
| JP3231647B2 (ja) | ビタビ復号器 | |
| JPS59153350A (ja) | ビタビ復号回路 | |
| JP2004120791A (ja) | ビタビ復号器 | |
| JPH07131359A (ja) | ビタビ復号装置 | |
| JPH07288478A (ja) | ビタビ復号方法およびビタビ復号化装置 | |
| JPH10341170A (ja) | 高速ビタビ復号装置 |