米国特許情報 | 欧州特許情報 | 国際公開(PCT)情報 | Google の米国特許検索
 
     特許分類
A 農業
B 衣類
C 家具
D 医学
E スポ−ツ;娯楽
F 加工処理操作
G 机上付属具
H 装飾
I 車両
J 包装;運搬
L 化学;冶金
M 繊維;紙;印刷
N 固定構造物
O 機械工学
P 武器
Q 照明
R 測定; 光学
S 写真;映画
T 計算機;電気通信
U 核技術
V 電気素子
W 発電
X 楽器;音響


  ホーム -> 電気素子 -> 株式会社日立製作所

発明の名称 誤り訂正符号化復号化方法
発行国 日本国特許庁(JP)
公報種別 公開特許公報(A)
公開番号 特開平6−204898
公開日 平成6年(1994)7月22日
出願番号 特願平5−1591
出願日 平成5年(1993)1月8日
代理人 【弁理士】
【氏名又は名称】小川 勝男
発明者 ▲高▼島 卓 / 淺川 吉章 / 関根 英敏 / 大西 誠
要約 目的
バースト的にデータを伝送する通信システムで、誤り検出記号が付加された畳み込み符号を適用した場合の終結ビットの付加による実効符号化率の低下を防止する。

構成
畳み込みされる情報系列のうち誤り検出符号化されたものを最終状態を決定する最後の(K-k)個の位置に配置して符号化して終結ビットを省略して伝送し、復号器63で最尤状態及びそれに準ずる状態から誤りが検出されない状態を選択して復号する。
特許請求の範囲
【請求項1】k個の情報記号をn個の符号記号に符号化する符号化率R=k/n、拘束長Kの畳み込み符号をヴィタビ復号器によって最尤復号する誤り訂正符号化復号化方法において、M個のバースト情報系列にm個の誤り検出検査記号を付加した(M+m)個のバースト情報系列に終結情報を付加せずにn(M+m)/k個の符号系列に符号化し送出することを特徴とする誤り訂正符号化復号化方法。
【請求項2】特許請求の範囲請求項1記載の誤り訂正符号化復号化方法において、前記誤り検出検査記号を用いて、前記バースト符号系列の終端状態を推定し、前記バースト符号系列から、バースト情報系列を復号することを特徴とする誤り訂正符号化復号化方法。
【請求項3】特許請求の範囲請求項2記載の誤り訂正符号化復号化方法において、前記誤り検出検査記号誤成立を回避するために、該誤り検出検査記号による終端状態推定に制限を加えることを特徴とする誤り訂正符号化復号化方法。
発明の詳細な説明
【0001】
【産業上の利用分野】本発明は、誤り訂正方法に係わり、特にバースト伝送を行う通信システムに適用する誤り検出を付加した畳み込み符号と最尤復号を用いた誤り訂正符号化復号化方法に関する。
【0002】
【従来の技術】近年、データ転送の信頼性を高めるため、伝送途中で生ずる伝送データの誤りを訂正する誤り訂正技術が多方面で良く用いられている。特に畳み込み符号を用いて符号化し、ヴィタビ復号により最尤復号する方法は、誤り訂正能力が大きく各方面に適用されている。更に、復号データ中に誤りが存在する場合の影響が深刻なものとなることが予想される場合、畳み込み符号化されるデータにCRC(Cyclic Redundancy Check)による誤り検出を付加するということも行われる。本発明の説明の準備として、4次の生成多項式によるCRCと、符号化率1/2、拘束長k=3の畳み込み符号を例にとってヴィタビ復号の原理を説明しておく。4次のCRCの生成多項式は【0003】
【数1】

【0004】で表される。
【数1】のCRC符号器は図1の様に構成される。図1において1,2,3,4は遅延素子で、5,6,7は排他的論理和ゲートである。情報ビットX(x)が入力される度に符号器の状態が遷移し、生成多項式による除算が行われる。最終的に、全情報ビットの入力が終了した時点で生じる剰余を検査記号として情報ビットに付加して情報系列とする。図3-bの情報系列は、図中の情報ビットをCRC符号化器に入力して得られた検査ビットを付加したものである。受信側では、復号系列を生成多項式で除算し、剰余が生じなければ誤りが存在しないと判断される(このことを以後、CRCが成立する、と呼ぶことにする)。
【0005】符号化率R=1/2、拘束長k=3の畳み込み符号の生成多項式は【0006】
【数2】

【0007】で表される。数2でDは単位時間の遅延を表し、加算は排他的論理和で行われる。xは情報ビットである。数2の畳み込み符号器は図2の様に構成される。図2において21,22は遅延素子で、2ビットのシフトレジスタを構成している。23,24,25は排他的論理和ゲートである。シフトレジスタの記憶内容 l,mの2ビットによって、符号器の動作状態が表される。情報ビットxがシフトレジスタに入力される度に、符号器の状態が遷移し、かつ送信符号として(g0,g1)の2ビットが送出される。伝送路において、これに誤り系列が加わり、受信系列となる。復号器では、この受信系列から符号器の遷移状態を推定し、最も確からしい(最尤)状態遷移を選んで、これから情報系列を推定する。
【0008】ヴィタビ復号器の動作原理を図3を用いて更に詳細に説明する。図3-bはトレリス線図と言われるもので、状態遷移の時間的変化を表現したものである。時刻tmとtm+1の間での遷移は図3-aの様に表される。ここで、遷移の枝に表記したx/g0,g1は、符号器がその遷移をしたときの情報ビットxと、出力する符号系(g0,g1)の値を示している。例えば、状態10から情報ビット0が入力されると、符号系列11を出力して、状態00に遷移する。今、情報ビット系列xとして、1,1,0,0,1,0,1,1,0,1,0,"0,0"がシフトレジスタに順次入力されるとする。シフトレジスタの初期値は"0,0"とし、また情報ビット系列の最後にシフトレジスタをクリヤする為の終結ビット"0,0"を付加してある。図2を参照して符号系列を求めると、11,10,10,…の様になる。この状態遷移に対するパスを図3-bの太い実線で示す。受信側では、この符号系列に伝送路における誤り系列が加わった受信系列11,00,10,…が受信される。復号器では受信系列を参照して、符号器が取りうる全ての状態遷移を追跡し、符号器の状態遷移を推定する。
【0009】ここで状態遷移の確からしさを数量的に表す為、尤度を定義する。すなわち、受信系列r0,r1と(候補)符号系列とのハミング距離をその枝の尤度とする。例えば受信系列が01であるとき各符号系列の(枝)尤度は、【0010】
【表1】

【0011】の様に与えられる。状態尤度は遷移間の枝尤度を積算したものである。
【0012】各状態に至る枝は2本ずつあるので、遷移の度に尤度の小さい(確からしい)枝が選ばれる。図3-bでは、選択された枝を実線で、捨てられた枝を破線で表してある。また状態を示す白丸の脇につけた数字は各時点での状態尤度を表す。例えば、時点4の状態00には、時点3の状態00及び状態10から遷移してくるが、各々の状態尤度は3,0となり、尤度の小さい状態10からの遷移が選ばれ、時点4での状態00の尤度は、0となる。こうして最終的に選ばれた枝の連なり(生き残りパス)が、ヴィタビ復号器が最尤推定した符号系列である。
【0013】CRCによる誤り検出を付加したヴィタビ復号器の構成を図4に示す。図4で、41は枝尤度計算回路、42は加算比較選択回路、43は状態尤度メモリ、44はパスメモリ、45は最尤判定回路である。46はCRC入力多項式生成回路、47は生成多項式による除算回路である。
【0014】枝尤度計算回路41は表1に示した方法により、受信信号から状態遷移の確からしさ(枝尤度)を求める。加算比較選択回路42は状態尤度メモリ43に記憶されている直前状態の状態尤度に、枝尤度を加算して、新しい状態尤度を求め、1つの状態に至る複数の状態遷移の状態尤度を比較し、その中から最大の尤度を持つ遷移を選択して、選択された遷移の状態尤度を新しい状態尤度として状態メモリ43を更新する。また同時に選択された遷移の情報J(i)(状態j=J(i)から状態iに遷移したことを表す)をパスメモリ44に送る。パスメモリ44は、この遷移情報あるいは、遷移した状態番号を系列的に記憶しておき、最尤判定部45で、最終時点で選択されて残った状態遷移から復号結果を得る。CRC入力多項式生成回路46では、復号結果のなかでCRCによる誤り検出がかけられているビットを送信側でのCRC符号化器への入力順と同じ順序に並べ換え、生成多項式による除算回路47に送る。生成多項式による除算回路では、CRC入力多項式を生成多項式で除算して剰余を検査し、復号結果中CRCによる誤り検出を付加されているビットの誤りに関する情報を得る。
【0015】
【発明が解決しようとする課題】上記従来技術で述べたCRC誤り検出付加の畳み込み符号-ヴィタビ復号方法を、バースト的に情報を伝送する通信システムの誤り訂正符号化復号化方法として用いると、バースト毎に符号器のシフトレジスタをクリヤする為の終結ビットを付加して伝送しなければならない。符号化率をk/nとすると、終結ビットは拘束長Kに対してK-kビット必要となる。CRCの次数をmとし、情報ビットがMビットとすると、バースト当たりの送信符号ビット長はn{(M+m)+(K-k)}/kであり、実効的な符号化率はkM/[n{(M+m)+(K-k)}]となって、畳み込み符号の符号化率k/nより低くなる。すなわち、バースト長Mが小さく、拘束長Kが大きく、CRCの次数が大きいほど実効的な符号化率の低下は著しい。バースト長は伝送システムに依存するものであり変更できないため、実効符号化率を上げるには、拘束長Kを小さくするか、もとの符号の符号化率を上げるか、CRCの次数を低くする必要がある。拘束長を小さくすると、畳み込み符号の訂正能力は下がる傾向にあり、符号化率を上げるには、puncture符号を用いる等の方法があるが、構成が複雑になり、訂正能力の若干の低下が避けられなかった。またCRCの次数を下げると、誤りの検出能力が低下する。
【0016】本発明の目的は、バースト伝送する通信システムにおいて、誤り検出を付加した畳み込み符号を用いて誤り訂正を行う際に、終結ビットによる実効符号化率の低下を防止できる誤り訂正符号化復号化方法を提供することである。
【0017】
【課題を解決するための手段】上記目的を達成するために、畳み込み符号化される情報系列にCRCによる誤り検出が付加されていることを利用して、送信符号の削減を図る。図3を用いてこれを説明する。図3のトレリス線図を見ると、最終的なパスの決定には、時点 t=11での状態が指定されればよいことが分かる。畳み込み符号器の構成から、時点t=11の状態は、シフトレジスタに記憶されるビット列を表すものであり、 t=10,11の情報系列によって決定されるのは明らかである。よって、終結ビットを付加しなくともt=10,11の情報系列を正しく推定することができれば、復号できることが分かる。図3-b に示した送信符号のうち、終結ビットによる符号系列4bitを除いた場合のトレリス線図を図5に示す。終結ビットを用いない場合、図5のt=11の状態のように状態10,11の2状態が最尤状態となる場合もあり、最尤復号を行った場合、終端状態近傍の誤り率が増大する傾向にある。しかし、図5の情報系列のように、t=10,11の情報系列にCRCによる誤り検出が付加されている場合には、複数の最尤状態パスのうち、CRCが成立する復号系列の状態を選択することで、正しい状態を推定することが可能となる。これは、CRCによる誤り検出の付加で生じた冗長度の一部を、終結ビットを省いた場合の最終状態の推定に用いているためと考えられる。
【0018】上記のCRC付加による冗長度を利用して終結ビットを省略するためには、以下のような条件が必要となる。まず、CRC符号化されたビットが最終状態を決定できる(K-k)ビット、最低でも存在しなければならない。また、初期のシフトレジスタ状態と、最終状態を決定するための情報系列がCRC符号化されたビットとなるようなビット配置を、前もって送受信間で決めておく必要がある。符号化率R=k/n、拘束長Kの畳み込み符号を用いて、m次のCRCによる誤り検出をM 個のバースト情報記号の一部もしくは全体に付加して符号化する場合、従来の方法では、(K-k)個の終結ビットを付加してR=k/nの符号化を行うので、n{(M+m)+(K-k)}/k個のバースト符号となるが、このうち、終結ビットによる符号n(K-k)/k個を除いたn(M+m)/k個の符号ビットを送信する。受信側では、最尤もしくはそれに準ずる状態に至るパスから復号される系列から、送信側と同じCRC 入力多項式を生成してCRCの成立を検査し、最終状態を推定する。ここで、最尤もしくはそれに準ずる状態に限定してCRCの成立を検査するのは、CRCの誤成立を防ぐためである。こうして、送信符号系列のビット数を26から22に削減することができる。この場合、実効符号化率は従来の7/26に対して7/22となる。
【0019】
【作用】以上説明したように、本発明の誤り訂正符号化復号化方法の採用により、従来のCRCによる誤り検出を付加する畳み込み符号において、終結ビットを加えることに起因する実効符号化率の低下を抑えることができる。符号化率R=k/n、拘束長K の畳み込み符号を用いて、m次のCRCをによる誤り検出をM 個のバースト情報記号の一部もしくは全体に付加して符号化する場合、実効符号化率Reは、【0020】
【数3】

【0021】とすることが可能となる。数3と従来の方法による実効符号化率kM/[n{(M+m)+(K-k)}]を比較するとわかるように、この方法は、バースト長Mが小さく、拘束長Kが大きく符号化率R=k/nが小さいほうが効果が大きくなる。
【0022】畳み込み符号は情報記号をその前後K-1個の情報記号と畳み込んで符号化し、その情報量を前後に分散して伝送する方法と考えられるが、情報記号の最初と最後のビットはその前後に初期状態ビット、終結ビットを持ち、他のビットよりも冗長度が大きい。また、CRCによる誤り検出を付加した情報記号を畳み込み符号化する場合には、誤り検出を付加された情報記号は、大きな冗長度を持つことになる。終結ビットを削減することで減少した情報記号の最後のビットの冗長性をCRCによる誤り検出による冗長性で補うのが本発明の方法と言える。そのため、情報系列の最初のビットに関しては従来の方法と同じく他のビットよりも冗長度の高いビットとなり、より重要なビットをこの位置に配することで、誤りによる影響を軽減することが期待できる。
【0023】
【実施例】以下、図面を用いて本発明の実施例を説明する。図6は、図1に示す4次のCRC生成多項式によるCRC符号器、図2に示す符号化率R=1/2、拘束長K=3の畳み込み符号器と、図4のヴィタビ復号器を用いる、誤り訂正符号復号方法に本発明を適用した実施例である。図6において、60はCRC 符号化器及び畳み込み符号器、61は信号伝送路、62は伝送路で誤り系列が加算される機能を図示した加算器、64は各最終状態に至るパスによる復号系列からCRC入力多項式を生成する回路、65は64で生成されたCRC入力多項式を検査する回路、66は最尤もしくはそれに準ずる状態のなかからCRCが成立する状態を選択しその状態に至るパスによる復号系列を出力する回路である。41〜44は図4中のヴィタビ復号器の構成要素と同様の機能を有するものであり、同一番号を付けてある。62の加算器は、実際にものとして存在するのではなく、伝送路において送信信号に雑音が加わり、その結果誤りが発生する過程を模式的に図示したものである。また、事前情報67は、符号器のシフトレジスタの初期状態、情報ビットのうちCRC符号化されるビットの畳み込み符号での配置の情報からなる。
【0024】符号器60では、まず情報ビットのうち、CRCによる誤り検出を付加するビットを、CRC符号化器に順次入力して検査ビットを生成する。畳み込み符号化器では、初期状態にシフトレジスタをセットし、CRC符号化されたビットが最終状態を決定するビットとなるような配置順で情報系列が入力されて符号系列を出力し、伝送路に送出する。図5で説明した例に従えば、7ビットの情報ビットからCRCによる検査ビット4ビットを求めたのち、畳み込み符号器の初期状態を"0,0" として、情報ビットと検査ビットを合計11ビット入力する。こうして得られた22ビットの符号系列を送出する。
【0025】復号器では、事前情報67を用いて、パスメモリを初期化する。その後受信系列をヴィタビ復号して最終状態に達したならば、各最終状態に至るパスから推定される復号系列と、事前情報を用いてCRC符号語を構成する。そして、最尤もしくはそれに準ずる状態に対してCRC成立を検査し、成立する状態を選択して復号出力を行う。最終状態を決定するビットがCRC符号化されているため、複数の状態で最尤もしくはそれに準ずる状態となっていてもCRCが成立する状態を選択することで高い確度で正しく復号することが可能となる。この、CRC成立検査による状態推定の過程において、CRCが成立する状態が存在しない場合、及び複数の状態で成立する場合は、正しい復号ができないと見なし、誤り情報を出力する。
【0026】こうして、本発明による誤り訂正方法により、CRC誤り検出付加畳み込み符号化において、終結ビットを省くことによる実効符号化率の改善と、その時の誤り率を改善できる。図5で説明した例に従えばバースト長は11であり、実効符号化率は従来の7/26に対し、7/22となる。
【0027】CRC誤り検出を付加する畳み込み符号が用いられる代表的な例に、低ビットレートの音声符号化による無線通信等の誤り訂正が挙げられる。低ビットレートの音声符号化では、符号化されたビットの誤り感度に大きな偏在が存在する。そのため、誤りが存在すると聴覚上の劣化が著しいビットにCRCによる誤り検出を付加して、畳み込み符号化を行うという方法がとられている。そこで、本発明の他の実施例として、低ビットレートの音声符号化による通信に適用した場合を説明する。
【0028】この場合の符号器復号器の構成を図示したのが図7である。図中、701は音声符号器から出力される重要な符号ビットの経路、702はその中でも聴覚的に最重要なビットの経路、703は重要度の低いビットの経路である。また、71は7ビットCRC符号器、72はレート1/2の畳み込み符号器、73は重要な符号ビットの畳み込み符号系列と非重要ビットとを多重化してインタリーブをかけて伝送路に送りだすインタリーブ回路、74は事前情報、75は伝送路、76は誤り系列加算回路、78はデインタリーブ回路、791は重要ビットの復号出力経路、792は聴覚上最重要なビットに関する誤り情報伝送経路、そして、793は重要度の低いビットの経路である。また、77は図6と同様の構成の本方法の復号器である。
【0029】音声符号器からの符号ビットは、まず、重要なビットと重要度の低いビットに分けられる。重要度の低いビットは経路703で誤り訂正の符号化を受けずにインタリーブ回路73に送られる。重要ビットは更に聴覚的に最重要なビットとそれ以外のものに分けられる。聴覚的に最重要なビットは経路702にそってCRC符号化器71に送られ、誤り検出符号化される。そして、その他の重要な符号ビットと共に畳み込み符号器に入力される。この畳み込み符号器において、CRC符号化された最重要なビットは畳み込み符号の最終状態決定の為のビット位置に一部配置する。また、本発明による方法では、畳み込み符号の最初の部分の冗長度は高い状態に保たれており、最終状態決定ビット以外の最重要ビットを畳み込み符号の最初の部分に配置することで最重要ビットに対する誤り率を改善することも可能となる。このようにして符号化された重要な符号ビットの符号系列はインタリーブ回路に送られ、703を経由して送られた非重要ビットと共に伝送路75に送出される。
【0030】伝送路で誤り系列が付加された後、伝送系列は、デインタリーブ回路78に送られる。ここで、再び重要なビットの符号系列と、非重要ビットに分離され、非重要ビットはそのまま、経路793を経由して音声復号器に入力される。重要なビットは、ヴィタビ復号と、最尤及びそれに準ずる状態に対するCRC成立検査によって最終状態を推定して復号し、経路791より音声復号器に入力する。この過程で、最尤及びそれに準ずる状態に対してCRCが成立しなかった場合は、聴覚的に最重要なビットに誤りが存在するものとして誤り情報を経路792より音声復号器に入力する。この方法を用いることにより、従来の方法よりも多くのビットを保護することが可能となり、誤り時の音質劣化が抑さえられた。
【0031】以上本発明を、R=1/2,K=3の畳み込み符号にm=4のCRC誤り検出を付加した場合と、音声符号器に適用した場合について説明した。本発明は、これらの場合以外でも、誤り訂正だけでなく、検出を必要とする場合には有効な方法である。
【0032】
【発明の効果】本発明によれば、バースト的にデータを伝送する通信システムにおいて、CRC等による誤り検出を付加した畳み込み符号による誤り訂正符号化復号化方法を採用した場合の終結ビットによる実効符号化率の低下を抑え、かつ、誤り率の劣化を抑制することができる。誤り検出を付加した畳み込み符号では、一般に情報ビットの信頼度は向上するが、訂正、及び誤り検出が可能な情報ビット数が少なくなってしまう。これに対し、本発明は、多くのビットの信頼度向上をもたらす効果を持つ。本発明では、CRC符号化されたビットが最終状態を決定するビット数(K-k)ビット必要となるが、実際にCRCによる誤り検出を付加して畳み込み符号を行う際にこれ以下のビット数しかCRC符号化されないことはまずないためほとんど制約とはならない。処理的には、CRC成立検査を行う部分が若干増加するが、極くわずかなものである。




 

 


     NEWS
会社検索順位 特許の出願数の順位が発表

URL変更
平成6年
平成7年
平成8年
平成9年
平成10年
平成11年
平成12年
平成13年


 
   お問い合わせ info@patentjp.com patentjp.com   Copyright 2007-2013