(57)【特許請求の範囲】
【請求項１】
データを算術デコーディングする方法であって、
該データを算術デコーディングするために使用される、該データの求められた分布密度関数を変化させる、データを算術デコーディングする方法において、
チャネルコーディングされたデータをソフトアウトビタビアルゴリズムに従いチャネルデコーディングし（７）、第１の信頼度情報（Ｌｉ）を求め、
前記チャネルデコーディングされたデータをそれぞれのデータの時間クロック（ｉ）と一緒に記憶し、
前記チャネルデコーディングされたデータから算術デコーディングされたデータを求め（１０１）、
所定数の算術デコーティングされたデータからデータを予測し（１０２）、
前記予測されたデータを算術コーディングし、記憶された前記時間クロック（ｉ）と同じ時間クロックのチャネルデコーディングされた相応のデータと比較し（１０４）、
予測されたデータとチャネルデコーディングされたデータが一致する場合には、変化していない分布密度関数でもって算術デコーディングし、予測されたデータとチャネルデコーディングされたデータが一致しない場合には、変化された分布密度関数でもって算術デコーディング（１０５）することを特徴とする、データを算術デコーディングする方法。
【請求項２】
前記変化された分布密度関数（１０５）を、前記チャネルデコーディングされたデータの値が小さく且つ第１の信頼度情報（Ｌｉ）が小さい場合には、該チャネルデコーディングされたデータが入っている、前記分布密度関数の値領域の上側の値をより小さい値へと変化させ、
前記チャネルデコーディングされたデータの値が大きく且つ第１の信頼度情報（Ｌｉ）が小さい場合には、該チャネルデコーディングされたデータが入っている、前記分布密度関数の値領域の下側の値をより大きい値へと変化させることにより取得する、請求項１記載の方法。
【請求項３】
前記チャネルデコーディングされたデータをサイクリックなブロックコード（ＢＣＨ）を用いてコーディングし、該サイクリックなブロックコード（ＢＣＨ）を使用してデコーディングし、
サイクリックなブロックデコーディングの際に誤り検出を実施し、
算術デコーディングされたデータを、前記ブロックデコーディングに基づく前記誤り検出時に検出された誤りの数が所定の限界値を下回る場合のみ、判定データとして使用する、請求項１または２記載の方法。
【請求項４】
前記第１の信頼度情報（Ｌｉ）を所定数のデータに亘って平均化する、請求項１から３までのいずれか１項記載の方法。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は独立請求項の上位概念による、データを算術デコーディングする方法に関する。
【０００２】
【従来の技術】
米国特許第５０２５２５８号明細書から既に公知の算術デコーディング方法では伝送されるデータの分布密度関数の変化が伝送中行われる。このために、受信器側と送信器側の双方にて適応的な確率推定が行われ、換言すれば、伝送ないし受信されたデータの推定、分布密度関数の推定が実施され、推定された分布密度関数は算術コーディングないし算術デコーディングのため算術エンコーダないし算術デコーダに供給される。受信器側にて確率推定の際判定されたデータが考慮される。判定されたデータが伝送誤りに基づき誤って判定されたか否かの推定は行われない。それにより、算術デコーディングの際伝送誤りが考慮されない。それにより比較的高い誤り率を来す。
【０００３】
更にＲ．Ｍａｎｎ  Ｐｅｌｚ“Ｂｉｌｄ−  ｕｎｄ  Ｓｐｒａｃｈｕｅｂｅｒｔｒａｇｕｎｇ  ｉｎ  Ｍｏｂｉｌｆｕｎｋｋａｎａｅｌｅｎ”，Ｎａｃｈｒｉｃｈｔｅｎｔｅｃｈｎｉｋ，  Ｅｌｅｋｔｒｏｎｉｋ，Ｂｅｒｌｉｎ  ４２，１９９２，Ｓ．７  ｆｆ  によりチャネルコーディング及びチャネルデコーディングの際ソフトアウトビタビアルゴリズムを使用することが公知である。ソフトアウトビタビアルゴリズム（ＳＯＶＡ）によっては信頼度情報が与えられ、この信頼度情報は判定データが適正に判定された確率はどの位大きいかを表す。
【０００４】
【発明が解決すべき課題】
本発明の課題とするところは算術コーディングの信頼度を改善する算術デコーディング方法を提供することにある。
【０００５】
【課題解決のための手段】
上記課題は特許請求の範囲の構成要件により解決される。
【０００６】
【発明の効果】
本発明の独立請求項の構成要件により得られる利点とするところは、チャネルコーディングされたデータがソフトアウトビタビアルゴリズムに従ってチャネルデコーディングされ、従って、第１の信頼度情報が適正なチャネルデコーディングを介して得られる。更に、判定されるべきデータが先に伝送されたデータから予測されたデータと比較され、このデータが予測されたデータと一致しない場合には、算術デコーディングに用いられる分布密度関数の変化が実施され、チャネルデコーディングされたデータは変化された分布密度関数で算術デコーディングされる。そのようにして、例えば伝送誤りによって誤ってチャネルデコーディングされたデータがそれでも適正に算術デコーディングされることが達成される。それにより、高い信頼度情報を与えるロバストな算術デコーディング方法が可能になる。
【０００７】
引用請求項に示されている手段により、独立的請求項に示されている方法の有利な発展形態及び改善が可能である。特に有利にはチャネルデコーディングされたデータを変化されない分布密度関数をもって算術デコーディングし、算術デコーディングされたデータから時間的に次の（後続の）データを予測し、予測されたデータから第２の信頼度情報を推定する。そこで各データの第１の信頼度情報と第２の信頼度情報が相互に比較され、より大きい方の信頼度情報のデータ及びより大きい方の信頼度情報が選択される。並列的に、変化された分布密度関数により算術デコーディングされているデータから第３の信頼度情報が推定される。第３の信頼度情報は選択された信頼度情報と比較され、より大きい信頼度情報を有するデータが判定（された）情報として選択される。そのようにして、最大の信頼度情報を有するデータが判定データとして識別されることが達成される。それにより適正なデータを判定する確率が付加的に高められる。
【０００８】
更に、データに対してサイクリックなブロックコードを用いてチャネルコーディングを施すと有利である。そのようにしてチャネルコーディングの場合サイクリックなブロックコードを用いて誤り検出が実施されて、伝送の際誤りが生じているか否かの示唆が得られる。それにより信頼度は更に高められる。
【０００９】
【実施例】
次ぎに図示の実施例を図を用いて本発明を説明する。
【００１０】
図１は伝送区間を略示する。データ源１からは画像データがデジタル形態で供給される。データ源１から供給されたデータは他の情報、例えば音声情報を含み得る。画像データとしては例えば画素の輝度情報が伝送される。画像データはデータ源１から第１のデータ線路１０を介して算術コーダ２に導かれる。算術コーダ２は画像データの算術コーディングを実施する。
【００１１】
算術コーディング方法は既に公知であり、例えばＩ．Ｈ  Ｗｉｔｔｅｎ，ｅｔ  ａｌ．，  Ａｒｉｔｈｍｅｔｉｃ  Ｃｏｄｉｎｇ  ｆｏｒ  Ｄａｔａｃｏｍｐｒｅｓｓｉｏｎ”，Ｃｏｍｍｍｕｎｉｃａｔｉｏｎｓ  ｏｆ  ｔｈｅ  ＡＣＭ  ，Ｃｏｍｐｕｔｉｎｇ  Ｐｒａｃｔｉｃｅｓ，  Ｊｕｎｅ  １９８７，Ｖｏｌｎｍｅ  ３０，ＮＯ．６，Ｓ  ５２１  ｆｆに記載されている。
【００１２】
算術コーディングされた画像データは算術コーダ２から第１のコーダ線路１１を介してチャネルコーダ３へ導かれる。チャネルコーダ３は供給されるデータの畳込みコーディングを実施する。それに引き続いて、畳込みコーディングされたデータは第２のコーダ線路１２を介してインターリーブ回路４へ供給される。インターリーブ回路４は供給されるデータのインターリーブを実施し、処理されたデータを伝送チャネル５へ供給する。伝送チャネル５からはデータがデインターリーブ回路６に供給される。デインターリーブ回路６はインターリーブ回路４と逆のインターリーブプロセスを実施する。それに引き続いて、データは第３のコーダ線１３と介してチャネルデコーダ７へ導かれる。チャネルデコーダ７はソフトアウトビタビアルゴリズム（ＳＯＶＡ）を使用してチャネルデコーディングを実施する。
【００１３】
ソフトアウトビタビアルゴリズムは公知であり、例えばＨａｇｅｎａｕｅｒ  “Ａ  Ｖｉｔｅｒｂｉ  Ａｌｇｏｒｉｔｈｍ  ｗｉｔｈ  ＳｏｆｔーＤｅｃｉｓｉｏｎ  Ｏｕｔｐｕｔｓ  ａｎｄ  ｉｔｓ  Ａｐｐｌｉｃａｃｔｉｏｎｓ”  Ｇｌｏｂａｌ  Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎｓ  Ｃｏｎｆｅｒｅｎｃｅ  ，Ｄａｌｌａｓ，１９８９，Ｓ  １６８０  ｆｆ  に記載されている。チャネルデコ−ダ７は各チャネルデコーディングされたデータに対して判定データｕｉ及び信頼度情報Ｌｉを求める。判定デ−タｕｉは第４のコ−ダ線路１４を介して算術デコーダ８へ導かれる。付加的に、信頼度情報Ｌｉは第５のコーダ線路５を介して算術デコーダ８へ導かれる。算術デコーダ８は判定データ及び信頼度情報を使用してデータの算術デコーディングを実施する。算術デコーディングされたデータは第２のデータ線１６を介してデータシンク９へ供給される。データシンク９は例えば画像再生ユニットである。
【００１４】
データの実際の伝送の際、伝送チャネル５の障害が起こる。この障害は図１において乗算ユニットないし加算ユニットのところに矢印で示されている。この障害によって、チャネルデコーダ７において誤ったデータｕｉが判定されるおそれがある。その徴候は信頼度情報Ｌｉの小さな値である。算術デコーダ８の動作を図２を用いて説明する。
【００１５】
図２は算術デコーダ８の動作を略示したプログラムシーケンスの形で説明する。
【００１６】
以下においては、伝送されるデータはチャネルコーダ３の前でサイクリックなブロックコーディング処理を施されていることを基礎とする。
【００１７】
ブロックコーダとしては関数ｇ（Ｘ）＝１＋Ｘ＋Ｘ３を有する生成多項式が使用される。ここにおいて所定数のデータに対して３つのチェックビットが付加される。
【００１８】
従って、プログラム点１００においてはサイクリックなブロックコードの使用下でデコーディングが実施される。ここで、誤り検出が実施され、この誤り検出によって伝送されたデータが誤って伝送されたか否かの情報が得られ、誤りの数が所定の限界値を下回る際のみ判定データとして使用する。サイクリックなブロックコードは例えば  Ｓ．  Ｌｉｎ，  “Ｅｒｒｏｒ  Ｃｏｎｔｒｏｌ”，Ｐｒｅｎｔｉｃｅ−Ｈａｌｌ，  １９８３  に記載されている。伝送の際誤りが生じたか否かの情報はメモリ内にファイルされる。サイクリックにブロックコードデコーディングされたデータはメモリにファイルされる。それに引き続いてプログラム点１０１において、サイクリックにブロックコードデコーディングされたデータは算術デコーディング処理を施される。この算術デコーディングの場合、データ源１において先立って測定されたデータの分布密度関数が使用される。算術デコーディングされたデ−タＸｉはメモリ内にファイルされる。インデックスｉはデータの時間クロックを表す。プログラム点１０２にて算術デコーディングされたデータから時間的に順次連続するデータが予測される。
【００１９】
１つの画像の画像データの伝送の際例えば輝度値が、画素毎に左から右へ、行（ライン）ごとに上から下へ伝送される。図３は順次連続する画像ライン２０、２１からなる画像セクションを示す。第１の画像ライン２０は第１の画素Ｄ２１及び第２の画素Ｃ２３を有する。第２の画像ライン２１は第１の画素Ｂ２４及び第２の画素Ａ２５を有する。第１の画像ライン２０の第１の画素２２及び第２の画素２３並びに画像ライン２１の第１の画素Ｂ２４の輝度値が既知である場合、第２の画像ライン２１の第２の画素２５の輝度値は第１の画像ライン２０の第１の画素２２、第２の画素２３及び第２の画像ライン２１の第１の画素２４の輝度値から求められる。
【００２０】
ここにおいて、３次の空間的直線性予測が実施される。画素Ａは画素Ｂ、Ｃ、Ｄを用いて予測される。画素Ａにおける輝度値ＸＡは下式により計算される。
【００２１】
【数１】
0003746092.tif 000002
【００２２】
【数２】
0003746092.tif 000003
【００２３】
【数３】
0003746092.tif 000004
【００２４】
【数４】
0003746092.tif 000005
【００２５】
但しσｅは標準偏差を表す。
【００２６】
ラプラス分布ｐｅからは信頼度値Ｌｐｒｅａｄを次のように計算することができる。画素の所定数Ｎの予測を代表して平均値差が形成される
【００２７】
【数５】
0003746092.tif 000006
【００２８】
適正予測の確率は次の通りである。
【００２９】
Ｐｒ＝ｐｅ（ｅ）      （４）
その際信頼度はＬｏｇ尤度比の形態で計算される
Ｌｐｒａｅｄ＝ｌｏｇ［（１−Ｐｒ）／Ｐｒ］      （５）
【００３０】
【数６】
0003746092.tif 000007
【００３１】
【数１】
0003746092.tif 000008
【００３２】
分布密度関数の変化を図４を用いて説明する。図４ａは例えばデータ源１にて測定されたデータの分布密度関数を示す。ここで、０から１の値領域は個々の部分値領域に細分化されている。部分値領域の限界は累積的確率Ｐｉにより形成される。累積的確率Ｐｉは次のように計算される。
【００３３】
【数８】
0003746092.tif 000009
【００３４】
但しＰｊはデータ源１のシンボルｓｉの出現確率である。シンボルｓｉの各列は算術コーディングを用いて１つの実数Ｃに対応づけられる。実数Ｃは次の式
Ｃｉ＋１＝Ｃｉ＋Ｉｉ・Ｐｉ＋１
に従って計算される。
【００３５】
インターバルＩｉは０から１の値領域を成す。次のインターバルＩｉ＋１は、式Ｉｉ＋１＝Ｉｉ・Ｐｉにより求められる。
【００３６】
デコーディングのために実数Ｃｉは累積的確率Ｐｉと比較される。次の比較によりシンボルｓｉがデコーディングされた（Ｐｉ＜Ｃｉ＜Ｐｉ＋１の場合）。次いで
Ｃｉ＋１＝Ｃｉ−Ｐｉ  及び新たなインターバル
Ｉｉ＋１＝Ｉｉ／Ｐｉ
が形成される。但し、新たなインターバルは再び累積的確率に従って細分化されている。新たな実数Ｃｉ＋１は同じく新たなインターバルＩｉ＋１の累積的確率と比較され、更なるシンボルＳｉ＋１がデコーディングされる。
【００３７】
データ源１の２進シンボルを使用する際には２つの場合を区別することができる。判定データｕｊ＝０の場合、相応の信頼度情報Ｌｊは、送信された第２のシンボルの数Ｃ２が、受信された第１のシンボルの数Ｃ１より大きいという事項に対する信頼度情報を表す。何故ならば、ｕｊ＝１の代わりにｕｊ＝０が誤って検出されているおそれがあるからである。
【００３８】
受信された数Ｃ１を図４ｂに略示する。送信された数Ｃ２を図４ｃに略示する。この場合において、受信されたシンボルの数Ｃ１が分布密度関数のＰｉとＰｉ＋１との間の部分値領域内に入る場合、累積的確率Ｐｉ＋１に１つの新たな値Ｐｉ＋１が割付られ、ここで信頼度情報が考慮される。
【００３９】
反対に、判定データｕｊが１に等しい場合、相応の信頼度情報Ｌｊは送信されたシンボルｕｉの数Ｃ２が受信されたシンボルｕｉの数Ｃ１以下または等しいことを表す。何故ならば、１が検出されたけれども、０が送信されていることが起こり得るからである。つまり累積的な累積的確率Ｐｉは信頼度情報の考慮下で更新されなければならない。このケースを図４ｄからｆに示す。累積的確率ＰｉないしＰｉ＋１の更新は次の式により行われる。
【００４０】
【数９】
0003746092.tif 000010
【００４１】
ここでインデックスｊは動作可変量を表し、これによってはデータ源１のデータが所定データビット数内、例えば１画像の１ライン内において番号付けされている。
【００４２】
データｕｊが確実にデコーディングされた場合、信頼度情報Ｌｊに対して値１が生じ、換言すれば、累積的確率Ｐｉ及びＰｉ＋１はそれの値を維持する。極めて不確実なチャネルデコーディングな場合、信頼度情報Ｌｊは値０をとり、換言すれば式（７）、（８）により更新が行われる。この更新は２進データの場合１ビットないし整数個のデータビットの切換に相応する。信頼度情報Ｌｊが中間値をとる場合、上述の更新は非整数個のデータビットの切換に相応する。分布密度関数の更新によってはあり得ない事象の起こることのないようにしなければならない。累積的確率Ｐｉの値は大きさに従って配列されている；Ｐ１＜Ｐ２＜．．．Ｐｉ-１＜Ｐｉ＜Ｐｉ＋１＜Ｐｎ。この配列は更新後も維持されねばならない。この条件を常に充足するには０と１の間の値をとり得る中間変量ａが導入されている。中間変量を用いては式（７）を次のように書き換えることができる
【００４３】
【数１０】
0003746092.tif 000011
【００４４】
分布密度関数の更新のための上記式を適用例に従って異なった内容にすることが可能である。
【００４５】
【数１１】
0003746092.tif 000012
【００４６】
プログラム点１０６において変化された分布密度関数によるチャネルデコーディングされたデータｖｉの算術デコーディングが行われる。チャネルデコーディングされたデータが０を成す場合、算術デコーディングのもとで、式（８）又は（１０）に相応して新たな上限Ｐｉ＋１が使用される。チャネルデコーディングされたデータｖｉが１を成す場合、算術デコーディングにて式（７）又は（９）に相応して新たな下限Ｐｉが使用される。それに引き続いてプログラム点１０７において第１の判定データｕｉ（１）として算術デコーディングされたデータの記憶が行われる。
【００４７】
それに引き続いて、プログラム点１１５においてて第１の判定データの更なる処理が行われるべきであるか否か判定される。簡単な手法のもとで、第１の判定データの更なる処理が行われるべきでない場合にはプログラム点１００へと戻り分岐する。更なる処理が行われるべき場合にはプログラム点１０８にて記憶された予測されたデータｘｉから、式（５）により第２の信頼度情報Ｌｘｉが計算され、記憶される。
【００４８】
後続のプログラム点１０９では相応のデータの信頼度情報Ｌｉから所定データビット数Ｎの信頼度情報、すなわち誤り不発生率の尺度がエントロピＨ（Ｌ）の形で次の式を使用して求められる。
【００４９】
【数１２】
0003746092.tif 000013
【００５０】
但し、ｐ（Ｌｎ）は値Ｌｎの出現確率を表す。Ｌは式Ｌ＝（Ｌ１，Ｌ２，．．．，ＬＮ）に相応したベクトルを表す。この実施例では所定のデータビット数Ｎとして１つの画像の画素の表示のため必要なデータビット数が使用される。時間的に順次連続する画像ラインから１つの更新値Ｅが計算される。更新値は一時記憶される。
【００５１】
【数２】
0003746092.tif 000014
【００５２】
続くプログラム点１１１では第１の判定データｘｉからラプラス分布を使用して式（５）により第３の信頼度情報が求められる。引き続いて、プログラム点１１２において、第３の信頼度情報と、プログラム点１１０において選択された信頼度情報との比較が行われ、ここで、第３の判定データとして最大の信頼度情報を有するデータが選択される。引き続いて、プログラム点１１３にて、第３の判定データがデータシンク９へ転送され、プログラム点１００に向かって戻り分岐する。またこのプログラムシーケンスにおいて、第１の信頼度情報及び／又は第２の信頼度情報及び／又は第３の信頼度情報は所定数のデータに亘って平均化される。
【００５３】
簡単なチャネルコーディング手法の場合、サイクリックなブロックコーディングを省略することができる。
【００５４】
次の簡単な例を用いて算術コーディングの方式に就いて説明する。
【００５５】
Ｎ＝５のシンボル，Ａ，Ｂ，Ｃ，Ｄ，Ｅのアルファベットを次の出現確率ｐＡ及び累積確率ＰＡを以て考察する。
【００５６】
ｐＡ  ＝  ０．０７          ＰＡ  ＝  ０．００
ｐＢ  ＝  ０．３０          ＰＢ  ＝  ０．０７
ｐＣ  ＝  ０．０９          ＰＣ  ＝  ０．３７
ｐＤ  ＝  ０．４２          ＰＤ  ＝  ０．４６
ｐＥ  ＝  ０．１２          ＰＥ  ＝  ０．８８
さてシンボル列ＣＢＤに対する算術コードを形成する。
【００５７】
シンボルＣに対しては初期点Ｃｃとして、そして、インターバルＩｃとして、次の式により以下の結果が得られる。
【００５８】
Ｃｃ＝Ｃ０＋Ｉ０＊Ｐｃ
＝０．０＋１．０＊０．３７＝０．３７
Ｉｃ＝Ｉ０＊ｐｃ
＝１．０＊０．０９＝０．０９
初期値Ｃ０に対して０．０が代入され、初期インターバルＩ０に対しては１．０が代入された。
【００５９】
シンボルＣに続くシンボルＢに対して初期点ＣＣＢに対して、そしてインターバルＩＣＢに対しては次の値が得られる。
【００６０】
ＣＣＢ＝Ｃｃ＋Ｉｃ＊ＰＢ
＝０．３７＋０．０９＊０．０７＝０．３７６３
ＩＣＢ＝Ｉｃ＊ｐＢ
＝０．０９＊０．３０＝０．０２７
シンボルＣ及びＢに続くシンボルＤに対しては初期点ＣＣＢＤ及びインターバルＩＣＢＤに対して下記値が得られる。
【００６１】
ＣＣＢＤ＝ＣＣＢ＋ＩＣＢ＊ＰＤ
＝０．３７６３＋０．０２７＊０．４６＝０．３８８７２
ＩＣＢＤ＝ＩＣＢ＊ｐＤ
＝０．０２７＊０．４２＝０．０１１３４
上記例から明らかなようにエンド・オブ・ストリング（ＥＯＳ）コード語を導入することが必要である。ＣＣＢＤ＝０．３８８７２＝（０．０１１０００１１１．．）  の２進表示のものが伝送されねばならない。但し各実数は０．３８８７２と０．４０００６との間で同じ情報を成すので、２進数０１１０００１１１を伝送しさえすばよい。
【００６２】
受信器はビット列Ｃｅｍｐ＝０１１０００１１１．．．を受け取る。
【００６３】
インターバルサーチにより下記が得られる。
【００６４】
ＰＣ＜／＝Ｃｅｍｐ＝０．３８８７２＜ＰＤ→最初のシンボルは、Ｃである。
【００６５】
Ｃｎｅｕ＝（Ｃａｌｔ−ＰＣ）／ＰＤ＝０．０１８７２／０．０９＝０．２０８
ＰＢ＜／＝Ｃｎｅｗ＝０．２０８＜ＰＣ→２番目のシンボルはＢである。
【００６６】
Ｃｎｅｕ＝（Ｃａｌｔ−ＰＢ）／ｐＢ＝０．１３８／０．３＝０．４６
ＰＤ＜／＝Ｃｎｅｗ＝０．４６＜ＰＥ→最後のシンボルはＤである。
【００６７】
そのようにしてビット列Ｃｅｍｐ＝０１１０００１１１からシンボル列ＣＢＤが算術デコーディングにより求められる。
【図面の簡単な説明】
【図１】  伝送区間の構成経過を示す概略図である。
【図２】  算術デコーダの動作を説明するためのプログラム部分を示すフローチャートである。
【図３】  画素の様子を示す概略図である。
【図４】  算術デコーディングの様子を示す説明図である。
【符号の説明】
１    データ源
２    算術コーダ
３    チャネルコーダ
４    インターリーブ回路
５    伝送チャネル
６    デインターリーブ回路
７    チャネルデコーダ
８    算術デコーダ
９    データシンク
【図１】
0003746092.tif 000015
【図２】
0003746092.tif 000016
【図３】
0003746092.tif 000017
【図４】
0003746092.tif 000018