JPH06334697A - 誤り検出方法 - Google Patents
誤り検出方法Info
- Publication number
- JPH06334697A JPH06334697A JP5118176A JP11817693A JPH06334697A JP H06334697 A JPH06334697 A JP H06334697A JP 5118176 A JP5118176 A JP 5118176A JP 11817693 A JP11817693 A JP 11817693A JP H06334697 A JPH06334697 A JP H06334697A
- Authority
- JP
- Japan
- Prior art keywords
- error detection
- error
- path
- block
- 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.)
- Pending
Links
Classifications
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L1/00—Arrangements for detecting or preventing errors in the information received
- H04L1/004—Arrangements for detecting or preventing errors in the information received by using forward error control
- H04L1/0045—Arrangements at the receiver end
- H04L1/0052—Realisations of complexity reduction techniques, e.g. pipelining or use of look-up tables
-
- 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/29—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 combining two or more codes or code structures, e.g. product codes, generalised product codes, concatenated codes, inner and outer codes
-
- 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
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L1/00—Arrangements for detecting or preventing errors in the information received
- H04L1/004—Arrangements for detecting or preventing errors in the information received by using forward error control
- H04L1/0045—Arrangements at the receiver end
- H04L1/0054—Maximum-likelihood or sequential decoding, e.g. Viterbi, Fano, ZJ algorithms
-
- H—ELECTRICITY
- H04—ELECTRIC COMMUNICATION TECHNIQUE
- H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
- H04L1/00—Arrangements for detecting or preventing errors in the information received
- H04L1/004—Arrangements for detecting or preventing errors in the information received by using forward error control
- H04L1/0056—Systems characterized by the type of code used
- H04L1/0061—Error detection codes
Landscapes
- Engineering & Computer Science (AREA)
- Physics & Mathematics (AREA)
- Probability & Statistics with Applications (AREA)
- Computer Networks & Wireless Communication (AREA)
- Signal Processing (AREA)
- Theoretical Computer Science (AREA)
- Artificial Intelligence (AREA)
- Error Detection And Correction (AREA)
- Digital Transmission Methods That Use Modulated Carrier Waves (AREA)
- Detection And Prevention Of Errors In Transmission (AREA)
Abstract
(57)【要約】
【目的】 畳み込み符号をビタビ復号するときに求めら
れるメトリックと、誤り検出符号とを組み合わせて、複
数個の誤り検出ブロックを独立して効率よく誤り検出を
行う。 【構成】 入力データは、誤り検出符号を付加された後
に畳み込み符号化して送信する。受信側では、ビタビ復
号により誤り訂正復号を行い、その際に求められるブラ
ンチメトリックまたはパスメトリックを記憶しておく。
そして誤り検出符号により誤りが検出された場合には、
記憶したメトリックを用いて、複数個の誤り検出ブロッ
クを独立して誤り検出を行う。
れるメトリックと、誤り検出符号とを組み合わせて、複
数個の誤り検出ブロックを独立して効率よく誤り検出を
行う。 【構成】 入力データは、誤り検出符号を付加された後
に畳み込み符号化して送信する。受信側では、ビタビ復
号により誤り訂正復号を行い、その際に求められるブラ
ンチメトリックまたはパスメトリックを記憶しておく。
そして誤り検出符号により誤りが検出された場合には、
記憶したメトリックを用いて、複数個の誤り検出ブロッ
クを独立して誤り検出を行う。
Description
【発明の詳細な説明】
【０００１】
【産業上の利用分野】本発明はディジタル・データ伝送
等において、誤り訂正符号である畳み込み符号およびそ
の復号器であるビタビ復号器を使用した場合の誤り検出
方法に関する。
等において、誤り訂正符号である畳み込み符号およびそ
の復号器であるビタビ復号器を使用した場合の誤り検出
方法に関する。
【０００２】
【従来の技術】ビタビ信号とは、畳み込み符号方法の一
つである。このビタビ復号について、図３に示す畳み込
み符号化回路３０で生成される拘束長Ｋ＝３、符号化率
Ｒ＝１／２の畳み込み符号Ｃを具体例にして説明する。
つである。このビタビ復号について、図３に示す畳み込
み符号化回路３０で生成される拘束長Ｋ＝３、符号化率
Ｒ＝１／２の畳み込み符号Ｃを具体例にして説明する。
【０００３】図３に示したシフトレジスタＦ０、Ｆ１の
状態により畳み込み符号化回路３０の状態Ｓはつぎの４
つの状態、すなわち、 Ｓ0＝（０，０）、Ｓ1＝（１，０）、Ｓ2＝（０，
１）、Ｓ3＝（１，１） のいずれかの状態をとる。
状態により畳み込み符号化回路３０の状態Ｓはつぎの４
つの状態、すなわち、 Ｓ0＝（０，０）、Ｓ1＝（１，０）、Ｓ2＝（０，
１）、Ｓ3＝（１，１） のいずれかの状態をとる。
【０００４】最初に状態Ｓ0にあった畳み込み符号化回
路器を時々刻々、すなわち情報信号が入力される度に各
状態を遷移していく模様を表現したものがトレリス線図
であり、符号Ｃのトレリス線図を図４に示す。なお、こ
こでは入力情報信号系列長はＪ−Ｋ＋１であり、さらに
Ｋ−１個の０が続くものとする。また、トレリス線図の
枝状の部分をブランチ、２個以上のブランチの連なりを
部分パスと称する。
路器を時々刻々、すなわち情報信号が入力される度に各
状態を遷移していく模様を表現したものがトレリス線図
であり、符号Ｃのトレリス線図を図４に示す。なお、こ
こでは入力情報信号系列長はＪ−Ｋ＋１であり、さらに
Ｋ−１個の０が続くものとする。また、トレリス線図の
枝状の部分をブランチ、２個以上のブランチの連なりを
部分パスと称する。
【０００５】図４に示したトレリス線図において、点線
のブランチは入力信号が０であることを示し、実線は入
力信号が１であることを示すものとする。さらにブラン
チ部分に符号器１１の出力ａ，ｂ，ｃ，ｄを示す。ただ
し、ａ＝（０，０）、ｂ＝（１，０）、ｃ＝（０，
１）、ｄ＝（１，１）、とし、左側の成分がＣi(1)を、
また右側の成分がＣi(2)を表すものとする。
のブランチは入力信号が０であることを示し、実線は入
力信号が１であることを示すものとする。さらにブラン
チ部分に符号器１１の出力ａ，ｂ，ｃ，ｄを示す。ただ
し、ａ＝（０，０）、ｂ＝（１，０）、ｃ＝（０，
１）、ｄ＝（１，１）、とし、左側の成分がＣi(1)を、
また右側の成分がＣi(2)を表すものとする。
【０００６】時刻ｔ＝ｔ0における状態Ｓ0（ｔ＝ｔ0）
からｔ＝ｔjにおける状態Ｓ0（ｔ＝ｔj）に至るブラン
チの連なりをパスという。このパスは畳み込み符号Ｃの
符号語に対するパスである。部分パスとの混同を避ける
必要がある場合には符号語パスと呼ぶことにする。
からｔ＝ｔjにおける状態Ｓ0（ｔ＝ｔj）に至るブラン
チの連なりをパスという。このパスは畳み込み符号Ｃの
符号語に対するパスである。部分パスとの混同を避ける
必要がある場合には符号語パスと呼ぶことにする。
【０００７】図５に符号Ｃのトレリス線図における部分
パスを示す。この部分パスに対応する符号語の部分集合
を便宜上 ＣS1＝（００ ００ １１）、ＣS2＝（１１ １０ ０
０） とする。ビタビ復号ではパスＣS1とパスＣS2のメトリッ
ク（尤度）を比較して、例えば、ＣS1のメトリックの方
がパスＣS2のメトリックよりも大きければＣS2を棄却す
る。このときパスＣS2を部分パスとして含む全ての符号
語パスが送信符号語の候補から棄却されたことになる。
ＣS1のように棄却されずに残った部分パスを生き残りパ
スという。
パスを示す。この部分パスに対応する符号語の部分集合
を便宜上 ＣS1＝（００ ００ １１）、ＣS2＝（１１ １０ ０
０） とする。ビタビ復号ではパスＣS1とパスＣS2のメトリッ
ク（尤度）を比較して、例えば、ＣS1のメトリックの方
がパスＣS2のメトリックよりも大きければＣS2を棄却す
る。このときパスＣS2を部分パスとして含む全ての符号
語パスが送信符号語の候補から棄却されたことになる。
ＣS1のように棄却されずに残った部分パスを生き残りパ
スという。
【０００８】図４のトレリス線図を見ると、各状態には
図５に示したような分岐状態を同一とする２本の部分パ
スが存在することが認められる。したがって、符号語の
両端の状態を除いた定常状態においては、各時刻におい
て常に２k-1個の生き残りパスが存在することがわか
る。そして、時刻ｔj-k+2以降は生き残りパスは１／２
ずつ減少し、時刻ｔjにおいてはただ１個の生き残りパ
スとなる。そして、この生き残りパスが、トレースバッ
クにより送信符号語として復号される。
図５に示したような分岐状態を同一とする２本の部分パ
スが存在することが認められる。したがって、符号語の
両端の状態を除いた定常状態においては、各時刻におい
て常に２k-1個の生き残りパスが存在することがわか
る。そして、時刻ｔj-k+2以降は生き残りパスは１／２
ずつ減少し、時刻ｔjにおいてはただ１個の生き残りパ
スとなる。そして、この生き残りパスが、トレースバッ
クにより送信符号語として復号される。
【０００９】図６は畳み込み符号＋誤り検出符号によっ
て構成された誤り訂正及び誤り検出符号化装置の概略ブ
ロック図であり、図７は畳み込み符号化される情報デー
タの符号器入力順序の一例を示す図である。また、図８
は従来のビタビ復号＋誤り検出復号によって構成された
誤り訂正および誤り検出復号化装置の概略ブロック図で
ある。
て構成された誤り訂正及び誤り検出符号化装置の概略ブ
ロック図であり、図７は畳み込み符号化される情報デー
タの符号器入力順序の一例を示す図である。また、図８
は従来のビタビ復号＋誤り検出復号によって構成された
誤り訂正および誤り検出復号化装置の概略ブロック図で
ある。
【００１０】まず、図６に示す誤り訂正符号化装置３１
では、誤り検出符号化回路３２において、入力データに
ＣＲＣ（Ｃｙｃｌｉｃ Ｒｅｄｕｎｄａｓｎｃｙ Ｃｈ
ｅｃｋ）符号等の検出符号（図７において符号３４で示
すＣＲＣ１、符号３５で示すＣＲＣ２）が付加される。
図７の例では、入力データはデータ１〜３の３つに分割
され、データ１およびデータ３に対し１個のＣＲＣが付
加され、検査ビットをＣＲＣ１およびＣＲＣ２に分割し
て配置している。また、誤り訂正符号化回路３３におい
ては、図７のような入力順序で畳み込み符号化される。
では、誤り検出符号化回路３２において、入力データに
ＣＲＣ（Ｃｙｃｌｉｃ Ｒｅｄｕｎｄａｓｎｃｙ Ｃｈ
ｅｃｋ）符号等の検出符号（図７において符号３４で示
すＣＲＣ１、符号３５で示すＣＲＣ２）が付加される。
図７の例では、入力データはデータ１〜３の３つに分割
され、データ１およびデータ３に対し１個のＣＲＣが付
加され、検査ビットをＣＲＣ１およびＣＲＣ２に分割し
て配置している。また、誤り訂正符号化回路３３におい
ては、図７のような入力順序で畳み込み符号化される。
【００１１】次に、図８に示す誤り訂正復号化装置３６
では、受信データを誤り訂正復号回路３７でビタビ復号
を行う。そして、その復号結果を基に誤り検出復号回路
３８でＣＲＴ誤り検出を行い、復号データと共に誤り検
出結果を出力する。例えば、誤りを検出した場合には誤
り検出フラグを１、検出しないときは０と出力する。
では、受信データを誤り訂正復号回路３７でビタビ復号
を行う。そして、その復号結果を基に誤り検出復号回路
３８でＣＲＴ誤り検出を行い、復号データと共に誤り検
出結果を出力する。例えば、誤りを検出した場合には誤
り検出フラグを１、検出しないときは０と出力する。
【００１２】
【発明が解決しようとする課題】しかし、上記従来の誤
り検出方法では、ＣＲＣをデータ１および３の両方のデ
ータから符号化しているために、ＣＲＣによる誤り検出
だけでは、もしデータ１には誤りがなく、データ３にの
み誤りが集中している場合でも、データ１とデータ３を
独立して誤り検出することは不可能であった。このた
め、ビタビ復号では復号データにおける誤りがバースト
的（この例の場合、データ１〜３の内１つまたは２つに
誤りが集中すること）に発生する確立が高いにもかかわ
らず、データ１、３共に誤った場合と区別できないた
め、効率的な誤り検出ができないという問題点があっ
た。また、データ１と３とで、それぞれ独立したＣＲＣ
符号を付加すれば、独立した誤り検出が可能になるが、
そのために冗長ビットが増えてしまうという問題点があ
った。
り検出方法では、ＣＲＣをデータ１および３の両方のデ
ータから符号化しているために、ＣＲＣによる誤り検出
だけでは、もしデータ１には誤りがなく、データ３にの
み誤りが集中している場合でも、データ１とデータ３を
独立して誤り検出することは不可能であった。このた
め、ビタビ復号では復号データにおける誤りがバースト
的（この例の場合、データ１〜３の内１つまたは２つに
誤りが集中すること）に発生する確立が高いにもかかわ
らず、データ１、３共に誤った場合と区別できないた
め、効率的な誤り検出ができないという問題点があっ
た。また、データ１と３とで、それぞれ独立したＣＲＣ
符号を付加すれば、独立した誤り検出が可能になるが、
そのために冗長ビットが増えてしまうという問題点があ
った。
【００１３】本発明は、このような従来の問題点を解決
するものであり、誤り検出符号に加えて、ビタビ復号に
おいて記憶したブランチメトリックまたはパスメトリッ
クを用いることにより、複数個の誤り検出ブロックを独
立して効率よく誤り検出することができる誤り検出方法
を提供することを目的とする。
するものであり、誤り検出符号に加えて、ビタビ復号に
おいて記憶したブランチメトリックまたはパスメトリッ
クを用いることにより、複数個の誤り検出ブロックを独
立して効率よく誤り検出することができる誤り検出方法
を提供することを目的とする。
【００１４】
【課題を解決するための手段】本発明は上記目的を達成
するために、誤り訂正復号化装置でのビタビ復号におい
て、受信系列ごとに求められるブランチメトリックまた
はＡＣＳ演算で各状態ごとに求められるパスメトリック
を記憶しておき、その上で、誤り検出符号の復号を行
い、誤りが検出された際には、誤り検出符号とビタビ復
号において記憶しておいたブランチメトリックまたはパ
スメトリックを用いることにより、ブロック単位による
誤り検出を行うものである。
するために、誤り訂正復号化装置でのビタビ復号におい
て、受信系列ごとに求められるブランチメトリックまた
はＡＣＳ演算で各状態ごとに求められるパスメトリック
を記憶しておき、その上で、誤り検出符号の復号を行
い、誤りが検出された際には、誤り検出符号とビタビ復
号において記憶しておいたブランチメトリックまたはパ
スメトリックを用いることにより、ブロック単位による
誤り検出を行うものである。
【００１５】
【作用】したがって、本発明によれば、受信側では、誤
り検出符号およびビタビ復号によるメトリックを用い
て、誤り検出符号化したビット数よりも少ないビット数
を誤り検出のための単位（ブロック）として、複数個の
誤り検出ブロックを独立して誤り検出することができ
る。
り検出符号およびビタビ復号によるメトリックを用い
て、誤り検出符号化したビット数よりも少ないビット数
を誤り検出のための単位（ブロック）として、複数個の
誤り検出ブロックを独立して誤り検出することができ
る。
【００１６】
【実施例】図１は、本発明方法の実施例における誤り訂
正および誤り検出復号化装置を示す概略ブロック図であ
る。
正および誤り検出復号化装置を示す概略ブロック図であ
る。
【００１７】図１において、全体符号１で示す誤り訂正
および誤り検出復号化装置は、受信データをビタビ復号
により誤り訂正復号を行う誤り訂正復号回路２、この復
号結果を基にＣＲＣ誤り検出を行う誤り復号回路３、ビ
タビ復号において受信系列毎に求められうるブランチメ
トリックまたはＡＣＳ演算で各状態毎に求められるパス
メトリックを記憶するメトリック記憶回路４、および誤
り検出復号回路３で復号された誤り検出符号（ＣＲＣ誤
り検出フラグ）とメトリック記憶回路４のブランチメト
リックまたはパスメトリックを用いて誤り検出を行うメ
トリック誤り検出回路５とから構成される。
および誤り検出復号化装置は、受信データをビタビ復号
により誤り訂正復号を行う誤り訂正復号回路２、この復
号結果を基にＣＲＣ誤り検出を行う誤り復号回路３、ビ
タビ復号において受信系列毎に求められうるブランチメ
トリックまたはＡＣＳ演算で各状態毎に求められるパス
メトリックを記憶するメトリック記憶回路４、および誤
り検出復号回路３で復号された誤り検出符号（ＣＲＣ誤
り検出フラグ）とメトリック記憶回路４のブランチメト
リックまたはパスメトリックを用いて誤り検出を行うメ
トリック誤り検出回路５とから構成される。
【００１８】なお、本実施例における誤り訂正符号化装
置は図６に示す従来例と同様であり、畳み込み符号化さ
れる情報データも図７に示すものと同様である。
置は図６に示す従来例と同様であり、畳み込み符号化さ
れる情報データも図７に示すものと同様である。
【００１９】図７において、誤り検出符号化したビット
数よりも少ないビット数を誤り検出のための単位（ブロ
ック）として、３個の誤り検出ブロックを定義する。
数よりも少ないビット数を誤り検出のための単位（ブロ
ック）として、３個の誤り検出ブロックを定義する。
【００２０】 ブロック１：ＣＲＣ１＋データ１ ブロック２：データ３ ブロック３：データ２＋ＣＲＣ２ この例では、ブロック１〜３のビット数をほぼ同程度
（必ずしも同ビット数である必要はない）とする。ま
た、テールビット部分については、誤り検出の対象とし
ない。
（必ずしも同ビット数である必要はない）とする。ま
た、テールビット部分については、誤り検出の対象とし
ない。
【００２１】メトリックによる誤り検出に用いるパラメ
ータとして以下の５つを定義する。 （ｉ＝１〜３） Ｍｆ ：最終生き残りパスのパスメトリック Ｍｐｉ ：最終生き残りパスの各ブロックｉでの部分
パスメトリック Ｍａｘ ｉ：各ブロックｉの最終受信系列におけるパス
メトリックの最大値 Ｍｉｎ ｉ：各ブロックｉの最終受信系列におけるパス
メトリックの最小値 Ｍｄｉ ：各ブロックｉの最終受信系列におけるパス
メトリックの最大値−最小値 また、誤り検出アルゴリズムにおけるしきい値として、
以下の４つを定義する。
ータとして以下の５つを定義する。 （ｉ＝１〜３） Ｍｆ ：最終生き残りパスのパスメトリック Ｍｐｉ ：最終生き残りパスの各ブロックｉでの部分
パスメトリック Ｍａｘ ｉ：各ブロックｉの最終受信系列におけるパス
メトリックの最大値 Ｍｉｎ ｉ：各ブロックｉの最終受信系列におけるパス
メトリックの最小値 Ｍｄｉ ：各ブロックｉの最終受信系列におけるパス
メトリックの最大値−最小値 また、誤り検出アルゴリズムにおけるしきい値として、
以下の４つを定義する。
【００２２】 ＭＦ：Ｍｆに関するしきい値 Ａ ：Ｍｄｉに関するしきい値 Ｂ ：Ｍｐｉに関するしきい値１ Ｃ ：Ｍｐｉに関するしきい値２ さらに、各ブロックにおける部分パスメトリックＭｐｉ
（ｉ＝１〜３）をメトリックの大きい順に（Ｍｐｓ，Ｍ
ｐｔ，Ｍｐｕ）とし（但し、ｓ，ｔ，ｕ＝１〜３）、誤
り検出フラグをフラグｉ（ｉ＝１〜３）とする。
（ｉ＝１〜３）をメトリックの大きい順に（Ｍｐｓ，Ｍ
ｐｔ，Ｍｐｕ）とし（但し、ｓ，ｔ，ｕ＝１〜３）、誤
り検出フラグをフラグｉ（ｉ＝１〜３）とする。
【００２３】図２は、本実施例における誤り訂正復号化
装置１のメトリック誤り検出回路５の動作手順を示すフ
ローチャートである。
装置１のメトリック誤り検出回路５の動作手順を示すフ
ローチャートである。
【００２４】図２において、ステップＳ１ではＣＲＣに
よる誤り検出が行われたかを判断し、ＯＫ（誤りなし）
と判断されたならばステップＳ２でフラグ１〜３を全て
０にして出力する。ＮＧ（誤りあり）と判断された場合
には、ステップＳ３においてＭｆがしきい値（ＭＦ）以
上であるかを判断する。ここで、Ｍｆがしきい値未満の
場合はステップＳ２１に進み、全てのフラグを１にして
出力する。また、Ｍｆがしきい値以上の場合はステップ
Ｓ４に進み、Ｍｄｉの値がＡ以上であるブロックの数を
カウントする。そして、ステップＳ５において、ステッ
プＳ４でのカウンタ値が１かを判断し、１個の場合はス
テップＳ６でＭｐｓおよびＭｄｓの値が共にしきい値
Ｂ，Ａ以上かを判定する。
よる誤り検出が行われたかを判断し、ＯＫ（誤りなし）
と判断されたならばステップＳ２でフラグ１〜３を全て
０にして出力する。ＮＧ（誤りあり）と判断された場合
には、ステップＳ３においてＭｆがしきい値（ＭＦ）以
上であるかを判断する。ここで、Ｍｆがしきい値未満の
場合はステップＳ２１に進み、全てのフラグを１にして
出力する。また、Ｍｆがしきい値以上の場合はステップ
Ｓ４に進み、Ｍｄｉの値がＡ以上であるブロックの数を
カウントする。そして、ステップＳ５において、ステッ
プＳ４でのカウンタ値が１かを判断し、１個の場合はス
テップＳ６でＭｐｓおよびＭｄｓの値が共にしきい値
Ｂ，Ａ以上かを判定する。
【００２５】ステップＳ６において、Ｍｐｓ＞Ｂ、Ｍｄ
ｓ≧Ａであると判定されたときは、ステップＳ７に移行
してｓが１かを判定し、ｓ＝１のときはステップＳ８に
進み、ｓ＝１でないときはステップＳ９に進む。ステッ
プＳ８では、ＭｐｓがＭａｘ１に等しいかを判定し、Ｍ
ｐｓ＝Ｍａｘ１の場合はステップＳ９においてフラグｓ
を０に、他のフラグｔ，ｕを１にして出力する。また、
ステップＳ６およびＳ８において否定判定されたときは
ステップＳ２１に進み、いずれのフラグも全て１にして
出力する。
ｓ≧Ａであると判定されたときは、ステップＳ７に移行
してｓが１かを判定し、ｓ＝１のときはステップＳ８に
進み、ｓ＝１でないときはステップＳ９に進む。ステッ
プＳ８では、ＭｐｓがＭａｘ１に等しいかを判定し、Ｍ
ｐｓ＝Ｍａｘ１の場合はステップＳ９においてフラグｓ
を０に、他のフラグｔ，ｕを１にして出力する。また、
ステップＳ６およびＳ８において否定判定されたときは
ステップＳ２１に進み、いずれのフラグも全て１にして
出力する。
【００２６】一方、ステップＳ５において、カウント値
が１でないと判定された場合はステップＳ１０に進み、
カウント値が０かを判定する。ここで、カウント値が０
の場合はステップＳ２１に進み、全てのフラグを１にし
て出力する。また、カウント値が０でないと判定された
場合は、ステップＳ１１において、Ｍｐｔ＞Ｂか、Ｍｐ
ｓ＝Ｍｐｔか、Ｍｄｓ≧Ａか、Ｍｄｔ≧Ａかを判定す
る。ここで、否定判定されたときは、次のステップＳ１
２に移行してＭｐｔ＞Ｃか、Ｍｐｓ≠Ｍｐｔか、Ｍｄｓ
≧Ａ、Ｍｄｔ≧Ａかを判定する。このステップＳ１２で
否定判定された場合は、ステップＳ１３に移行してＭｐ
ｓ＞Ｂか、Ｍｄｓ≧Ａかを判定し、これらの条件が共に
満足されたときはステップＳ９にすすみ、ｓ＝０、ｔ，
ｕ＝１にして出力する。またステップＳ１３で否定判定
されたときはステップＳ２１の処理を実行する。
が１でないと判定された場合はステップＳ１０に進み、
カウント値が０かを判定する。ここで、カウント値が０
の場合はステップＳ２１に進み、全てのフラグを１にし
て出力する。また、カウント値が０でないと判定された
場合は、ステップＳ１１において、Ｍｐｔ＞Ｂか、Ｍｐ
ｓ＝Ｍｐｔか、Ｍｄｓ≧Ａか、Ｍｄｔ≧Ａかを判定す
る。ここで、否定判定されたときは、次のステップＳ１
２に移行してＭｐｔ＞Ｃか、Ｍｐｓ≠Ｍｐｔか、Ｍｄｓ
≧Ａ、Ｍｄｔ≧Ａかを判定する。このステップＳ１２で
否定判定された場合は、ステップＳ１３に移行してＭｐ
ｓ＞Ｂか、Ｍｄｓ≧Ａかを判定し、これらの条件が共に
満足されたときはステップＳ９にすすみ、ｓ＝０、ｔ，
ｕ＝１にして出力する。またステップＳ１３で否定判定
されたときはステップＳ２１の処理を実行する。
【００２７】ステップＳ１１またはステップＳ１２にお
いて肯定判定された場合はステップＳ１４に進み、ｕ＝
２かを判定する。ここで、ｕ＝２でないと判定されたと
きはスッテプＳ１５に進み、フラグｓ＝０、フラグｔ＝
０、フラグｕ＝１して出力する。また、ｕ＝２のとき
は、ＣＲＣによる誤り検出の対象であるデータ１および
３が共にＯＫになるはずがないと判定してステップＳ１
６に進み、Δ１＝Ｍｐ１−Ｍａｘ１、Δ２＝Ｍｐ３−Ｍ
ａｘ３＋Ｍａｘ２の演算を行うことにより、最終生き残
りパスの部分メトリックの値と各ブロックの部分パスメ
トリックの最大値との差を求める。そして、次のステッ
プＳ１７においてΔ１＞Δ２かを判定し、Δ１＞Δ２の
ときはステップＳ１８に移行して、フラグ１＝０、フラ
グ２、３＝１にして出力する。
いて肯定判定された場合はステップＳ１４に進み、ｕ＝
２かを判定する。ここで、ｕ＝２でないと判定されたと
きはスッテプＳ１５に進み、フラグｓ＝０、フラグｔ＝
０、フラグｕ＝１して出力する。また、ｕ＝２のとき
は、ＣＲＣによる誤り検出の対象であるデータ１および
３が共にＯＫになるはずがないと判定してステップＳ１
６に進み、Δ１＝Ｍｐ１−Ｍａｘ１、Δ２＝Ｍｐ３−Ｍ
ａｘ３＋Ｍａｘ２の演算を行うことにより、最終生き残
りパスの部分メトリックの値と各ブロックの部分パスメ
トリックの最大値との差を求める。そして、次のステッ
プＳ１７においてΔ１＞Δ２かを判定し、Δ１＞Δ２の
ときはステップＳ１８に移行して、フラグ１＝０、フラ
グ２、３＝１にして出力する。
【００２８】また、ステップＳ１７においてΔ１＞Δ２
でないと判定された場合はステップＳ１９に進み、Δ１
＜Δ２かを判定する。ここで、Δ１＜Δ２と判定された
ときはステップＳ２０において、フラグ３＝０、フラグ
１，２＝１にして出力する。また、Δ１＜Δ２でないと
判定されたときはステップＳ２１に進み、全てのフラグ
１，２，３を１にして出力する。
でないと判定された場合はステップＳ１９に進み、Δ１
＜Δ２かを判定する。ここで、Δ１＜Δ２と判定された
ときはステップＳ２０において、フラグ３＝０、フラグ
１，２＝１にして出力する。また、Δ１＜Δ２でないと
判定されたときはステップＳ２１に進み、全てのフラグ
１，２，３を１にして出力する。
【００２９】上記のような本実施例においては、図２の
フローチャートから明らかなように、受信側においてビ
タビ復号により誤り訂正復号を行い、このとき、受信系
列毎に求められるブランチメトリックの値、またはＡＣ
Ｓ演算で各状態毎に求められるパスメトリックの値を記
憶回路４に記憶しておき、この記憶したブランチメトリ
ックとパスメトリックの値と、誤り検出復号回路３から
のＣＲＣ誤り検出符号と組み合わせることにより、復号
データにおいて誤り検出符号化したビット数よりも少な
いビット数を誤り検出のためのブロックとして、複数の
誤り検出ブロックを独立して誤り検出することができ、
これに伴い冗長ビットが減少し、しかも従来のように複
数の誤り検出ブロックが共に誤った場合でも、これを区
別することができ、より効率的な誤り検出が可能にな
る。
フローチャートから明らかなように、受信側においてビ
タビ復号により誤り訂正復号を行い、このとき、受信系
列毎に求められるブランチメトリックの値、またはＡＣ
Ｓ演算で各状態毎に求められるパスメトリックの値を記
憶回路４に記憶しておき、この記憶したブランチメトリ
ックとパスメトリックの値と、誤り検出復号回路３から
のＣＲＣ誤り検出符号と組み合わせることにより、復号
データにおいて誤り検出符号化したビット数よりも少な
いビット数を誤り検出のためのブロックとして、複数の
誤り検出ブロックを独立して誤り検出することができ、
これに伴い冗長ビットが減少し、しかも従来のように複
数の誤り検出ブロックが共に誤った場合でも、これを区
別することができ、より効率的な誤り検出が可能にな
る。
【００３０】尚、本発明においては、上記した各しきい
値ＭＦ，Ａ，Ｂ，Ｃは必ずしも固定値である必要はな
く、回線状態やＣＲＣ誤り検出率や車速等に応じて制御
しても構わないことは明らかである。
値ＭＦ，Ａ，Ｂ，Ｃは必ずしも固定値である必要はな
く、回線状態やＣＲＣ誤り検出率や車速等に応じて制御
しても構わないことは明らかである。
【００３１】また、本実施例では、図６のように入力デ
ータ１および３に対してＣＲＣ符号化を行っているが、
入力データ全体に対しＣＲＣ符号化を行っても構わない
ことは明白である。
ータ１および３に対してＣＲＣ符号化を行っているが、
入力データ全体に対しＣＲＣ符号化を行っても構わない
ことは明白である。
【００３２】
【発明の効果】本発明は上記実施例より明らかなよう
に、送信側では、入力データの全体または一部のデータ
を誤り検出符号化し、さらにこの符号化データを情報ビ
ットとして畳み込み符号により訂正符号化して伝送し、
受信側では、ビタビ復号において記憶したブランチメト
リックまたはパスメトリックの値と、誤り検出符号の復
号結果を組み合わせることにより、復号データにおいて
誤り検出符号化したビット数よりも少ないビット数を誤
り検出のための単位（ブロック）として、複数個の誤り
検出ブロックを独立して誤り検出することができるとい
う効果を有する。
に、送信側では、入力データの全体または一部のデータ
を誤り検出符号化し、さらにこの符号化データを情報ビ
ットとして畳み込み符号により訂正符号化して伝送し、
受信側では、ビタビ復号において記憶したブランチメト
リックまたはパスメトリックの値と、誤り検出符号の復
号結果を組み合わせることにより、復号データにおいて
誤り検出符号化したビット数よりも少ないビット数を誤
り検出のための単位（ブロック）として、複数個の誤り
検出ブロックを独立して誤り検出することができるとい
う効果を有する。
【図１】本発明の一実施例における誤り訂正復号化装置
の概略ブロック図
の概略ブロック図
【図２】本発明の一実施例におけるメトリック誤り検出
回路の動作を示すブローチャート
回路の動作を示すブローチャート
【図３】従来における誤り訂正符号化回路の一例を示す
図
図
【図４】従来例におけるトレリス線図の一例を示す図
【図５】従来例における再合流する２本の部分パスの一
例を示す図
例を示す図
【図６】誤り訂正符号化装置の概略ブロック図
【図７】畳み込み符号化される情報データの符号器入力
順序の一例を示す図
順序の一例を示す図
【図８】従来の実施例における誤り訂正復号化装置のブ
ロック図
ロック図
１ 誤り訂正復号化装置 ２ 誤り訂正復号回路 ３ 誤り検出復号化装置 ４ メトリック記憶回路 ５ メトリック誤り検出回路 ９〜２９ 図２のフローチャートにおける動作ステップ ３０ 符号Ｃの符号化回路 ３１ 誤り訂正符号化装置 ３２ 誤り検出符号化回路 ３３ 誤り訂正符号化回路 ３４ ＣＲＣ１ ３５ ＣＲＣ２ ３６ 誤り訂正復号化装置 ３７ 誤り訂正復号回路 ３８ 誤り検出復号回路
Claims (5)
- 【請求項１】 送信側では、入力データの全体または一
部のデータを誤り検出符号化し、さらにこの符号化デー
タを情報ビットとして畳み込み符号により誤り訂正符号
化して伝送し、 受信側では、受信データをビタビ復号により誤り訂正復
号を行い、受信系列ごとに求められるブランチメトリッ
クまたはＡｄｄ−Ｃｏｍｐａｒｅ−Ｓｅｌｅｃｔ演算で
各状態ごとに求められるパスメトリックを記憶してお
き、その上で、誤り検出符号の復号を行い、誤りが検出
された際には、前記記憶したブランチメトリックまたは
パスメトリックを用いることにより、復号データにおい
て誤り検出符号化したビット数よりも少ないビット数を
誤り検出のためのブロックとして、複数個の誤り検出ブ
ロックを独立して誤り検出することを特徴とする誤り検
出方法。 - 【請求項２】 受信側において、ビタビ復号において連
続する複数個の受信系列を誤り検出のためのブロックと
して、受信系列を複数のブロックに分割しておき、最終
的な生き残りパスの前記ブロックごとの部分パスのパス
メトリックを記憶しておき、誤り検出符号により誤りが
検出された場合には、前記パスメトリックの値を用い
て、誤り検出ブロックごとの誤り検出を行うことを特徴
とする請求項１記載の誤り検出方法。 - 【請求項３】 受信側において、ビタビ復号において連
続する複数個の受信系列を誤り検出のためのブロックと
して、受信系列を複数のブロックに分割しておき、その
ブロックごとに最終系列の各状態におけるパスメトリッ
クの中の最大値および最小値または両者の差を記憶して
おき、誤り検出符号により誤りが検出された場合には、
前記記憶した値を用いて、誤り検出ブロックごとの誤り
検出を行うことを特徴とする請求項１記載の誤り検出方
法。 - 【請求項４】 受信側において、ビタビ復号において連
続する複数個の受信系列を誤り検出のためのブロックと
して、受信系列を複数のブロックに分割しておき、最終
的な生き残りパスの上記ブロックごとの部分パスのパス
メトリックおよびブロック単位ごとの最終系列での各状
態におけるパスメトリックの中の最大値および最小値ま
たは両者の差を記憶しておき、誤り検出符号により誤り
が検出された場合に、前記記憶した値を用いて、誤り検
出ブロックごとの誤り検出を行うことを特徴とする請求
項１記載の誤り検出方法。 - 【請求項５】 受信側において、ビタビ復号における最
終的な生き残りパスのパスメトリックを記憶しておき、
誤り検出符号により誤りが検出された場合には、前記パ
スメトリックの値をも用いて、誤り検出ブロックごとの
誤り検出を行うことを特徴とする請求項２、３又は４に
記載の誤り検出方法。
Priority Applications (4)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP5118176A JPH06334697A (ja) | 1993-05-20 | 1993-05-20 | 誤り検出方法 |
| US08/243,782 US5530708A (en) | 1993-05-20 | 1994-05-17 | Error detection method using convolutional code and viterbi decoding |
| EP94107799A EP0632612B1 (en) | 1993-05-20 | 1994-05-19 | Error detection method using convolutional code and viterbi decoding |
| DE69429133T DE69429133T2 (de) | 1993-05-20 | 1994-05-19 | Verfahren zur Fehlererkennung mit Faltungskode und Viterbi-Dekodierung |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP5118176A JPH06334697A (ja) | 1993-05-20 | 1993-05-20 | 誤り検出方法 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH06334697A true JPH06334697A (ja) | 1994-12-02 |
Family
ID=14730017
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP5118176A Pending JPH06334697A (ja) | 1993-05-20 | 1993-05-20 | 誤り検出方法 |
Country Status (4)
| Country | Link |
|---|---|
| US (1) | US5530708A (ja) |
| EP (1) | EP0632612B1 (ja) |
| JP (1) | JPH06334697A (ja) |
| DE (1) | DE69429133T2 (ja) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2000269826A (ja) * | 1999-03-15 | 2000-09-29 | Fujitsu Ltd | 誤り検出装置及び方法 |
Families Citing this family (10)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| FR2737824B1 (fr) * | 1995-08-08 | 1997-10-31 | Tortelier Patrick | Procede de decodage a sorties ponderees mettant en oeuvre l'algorithme de viterbi en fonctionnement par blocs |
| FR2738427B1 (fr) * | 1995-08-31 | 1997-11-21 | Sgs Thomson Microelectronics | Decodeur convolutif utilisant l'algorithme de viterbi |
| JPH10107649A (ja) * | 1996-09-30 | 1998-04-24 | Sanyo Electric Co Ltd | 符号誤り訂正／検出デコーダ |
| JP3154679B2 (ja) * | 1996-10-18 | 2001-04-09 | 三菱電機株式会社 | 連接符号の誤り訂正復号装置及び復号方法 |
| US6094465A (en) * | 1997-03-21 | 2000-07-25 | Qualcomm Incorporated | Method and apparatus for performing decoding of CRC outer concatenated codes |
| US6281929B1 (en) * | 1997-09-23 | 2001-08-28 | Zenith Electronics Corporation | Testing arrangement for decoders |
| US6418549B1 (en) | 1998-10-30 | 2002-07-09 | Merunetworks, Inc. | Data transmission using arithmetic coding based continuous error detection |
| US6606726B1 (en) * | 2000-06-13 | 2003-08-12 | Telefonaktiebolaget L M Ericsson (Publ) | Optimization of acceptance of erroneous codewords and throughput |
| JP3815543B2 (ja) * | 2000-12-27 | 2006-08-30 | 日本電気株式会社 | 記録状態検出装置およびこれを備えた情報記録再生装置 |
| GB2441164A (en) * | 2006-08-22 | 2008-02-27 | Iti Scotland Ltd | Segmenting packets and providing error check portions for each segment |
Family Cites Families (11)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS61164352A (ja) * | 1985-01-17 | 1986-07-25 | Oki Electric Ind Co Ltd | バ−スト誤り検出方法 |
| US5005189A (en) * | 1989-01-23 | 1991-04-02 | Hackett Jr Charles M | Detection of digital signals received from multipath channels |
| US5014276A (en) * | 1989-02-06 | 1991-05-07 | Scientific Atlanta, Inc. | Convolutional encoder and sequential decoder with parallel architecture and block coding properties |
| US5073940A (en) * | 1989-11-24 | 1991-12-17 | General Electric Company | Method for protecting multi-pulse coders from fading and random pattern bit errors |
| JP2591242B2 (ja) * | 1990-04-02 | 1997-03-19 | 松下電器産業株式会社 | 誤り検出方法 |
| JP2591332B2 (ja) * | 1990-11-09 | 1997-03-19 | 松下電器産業株式会社 | 誤り訂正復号装置 |
| GB9105101D0 (en) * | 1991-03-11 | 1991-04-24 | British Telecomm | Error burst detection |
| US5233629A (en) * | 1991-07-26 | 1993-08-03 | General Instrument Corporation | Method and apparatus for communicating digital data using trellis coded qam |
| US5204874A (en) * | 1991-08-28 | 1993-04-20 | Motorola, Inc. | Method and apparatus for using orthogonal coding in a communication system |
| JPH05199124A (ja) * | 1992-01-21 | 1993-08-06 | Nec Corp | 音声通信方式 |
| JPH05316053A (ja) * | 1992-05-07 | 1993-11-26 | Matsushita Electric Ind Co Ltd | 誤り訂正符号化方法 |
-
1993
- 1993-05-20 JP JP5118176A patent/JPH06334697A/ja active Pending
-
1994
- 1994-05-17 US US08/243,782 patent/US5530708A/en not_active Expired - Lifetime
- 1994-05-19 EP EP94107799A patent/EP0632612B1/en not_active Expired - Lifetime
- 1994-05-19 DE DE69429133T patent/DE69429133T2/de not_active Expired - Fee Related
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2000269826A (ja) * | 1999-03-15 | 2000-09-29 | Fujitsu Ltd | 誤り検出装置及び方法 |
Also Published As
| Publication number | Publication date |
|---|---|
| EP0632612A1 (en) | 1995-01-04 |
| EP0632612B1 (en) | 2001-11-21 |
| US5530708A (en) | 1996-06-25 |
| DE69429133D1 (de) | 2002-01-03 |
| DE69429133T2 (de) | 2002-06-20 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US5349589A (en) | Generalized viterbi algorithm with tail-biting | |
| US8370730B2 (en) | Soft output viterbi detector with error event output | |
| JP3120511B2 (ja) | ビタビ復号装置 | |
| US6148431A (en) | Add compare select circuit and method implementing a viterbi algorithm | |
| JP2000196469A (ja) | デ―タ誤り訂正システム | |
| JP2000216689A (ja) | 反復式ターボ符号復号装置及び該装置の性能を最適化する方法 | |
| JPH10178355A (ja) | 連接符号の誤り訂正復号装置及び復号方法 | |
| JPH06334697A (ja) | 誤り検出方法 | |
| CN1100393C (zh) | 采用固定长度的判定窗口对数据信号进行译码的方法 | |
| JPS60180222A (ja) | 符号誤り訂正装置 | |
| US7237180B1 (en) | Symbol-level soft output Viterbi algorithm (SOVA) and a simplification on SOVA | |
| JP3512176B2 (ja) | ターボ復号装置およびターボ復号における復号の繰返し回数の制御方法 | |
| JPH06284018A (ja) | ビタビ復号方法および誤り訂正復号化装置 | |
| JP3497399B2 (ja) | ビタビ復号器 | |
| WO1995001008A1 (en) | Bit error counting method and counter | |
| JPWO1995001008A1 (ja) | 誤り検出方法、装置ならびに識別方法 | |
| JP2757473B2 (ja) | ヴィタビ復号器 | |
| JP2008118327A (ja) | ビタビ復号方法 | |
| US8099657B2 (en) | Error correcting Viterbi decoder | |
| JP2591332B2 (ja) | 誤り訂正復号装置 | |
| JP7835619B2 (ja) | 誤り訂正装置、誤り訂正方法、及び、誤り訂正プログラム | |
| JP3117757B2 (ja) | たたみ込み符号・ビタビ復号データ判定システム | |
| JP3337950B2 (ja) | 誤り訂正復号化方法及び誤り訂正復号化装置 | |
| KR100431162B1 (ko) | 코드레이트 검출장치 | |
| JP3236979B2 (ja) | ビタビ復号装置 |