JP3774425B2 - Data encoding / decoding method and apparatus, data encoding / decoding program, and recording medium recording the program - Google Patents

Description

【０００６】
を求め、これを算術復号器１３へ伝える。次に、算術復号器１３は、バッファ１１に格納されたもっとも古いデータを取り出し、これを元に符号語選択装置１２から与えられた分布｛Ｑ(ｈ|ｖ)｝_{h ∈ H}を仮定して復号を行い、変換後のデータｈを多値情報源符号器１４に伝える。取り出されたデータは、バッファ１１から削除される。次に、多値情報源符号器１４は、その入力(ｖ,ｈ)（入力データ１５ ｖ及び算術復号器から出力されるｈ）に対して、可変長の記号列を与えて、これをバッファ１１に格納する。多値情報源符号器１４は、一対の入力(ｖ,ｈ)に対して、可変長の記号列（これをｂ^*とする）を与える全単射の写像で記述されるものであるので、ｂ^*に対して、対応する(ｖ,ｈ)が存在すれば、それは一意に定まる。上記の動作をあらかじめ定められた個数の入力データに関して行い、入力データがなくなって時点で、バッファ１１に残されたデータを復号器２０（図２参照）に伝える。
【０００７】
図２に示すように、復号器２０は、バッファ２１、符号語選択装置２２、算術復号器２３および多値情報源復号器２４より構成されている。ここで、バッファ２１の初期状態として、相手側の符号器１０の動作が終了した時点でのその符号器１０のバッファ１１の状態を与える。なお、バッファ２１内のデータ新しさとは、バッファ１１に格納された時間で決まるものとする。多値情報源復号器２４は、多値情報源符号器１４での写像の逆写像を実行するものであり、可変長の記号列ｂ^*に対して一意に定まる(ｖ,ｈ)を出力する。
【０００８】
復号を行う場合、最初に多値情報源復号器２４は、バッファ２１にある最も新しいデータを取り出し、これから(ｖ,ｈ)を出力する。多値情報源復号器２４から出力されるデータのうち、ｖは、再生データ２５として外部にも出力される。取り出されたデータは、バッファ２１から削除される。(ｖ,ｈ)のうち、ｈは算術符号器２３へ伝えられる。ｖは、再生データ２５として出力されるとともに、符号語選択装置２２へも伝えられる。符号語選択装置２２は、入力データｖに対して、あらかじめ定められた条件つき確率分布｛Ｑ(ｈ|ｖ)｝_{h ∈ H}を求め、これを算術符号器２３へ伝える。算術符号器２３は、多値情報源復号器２４から送られたｖをもとに、符号語選択装置２２から与えられた分布｛Ｑ(ｈ|ｖ)｝_{h ∈ H}を仮定して符号化を行う。変換後のデータはバッファ２１に格納される。上記の動作をあらかじめ定められた回数行う。このようにして再生データ２５が逐次得られるが、再生データ２５は、入力データ１５とは逆順の時系列として出力される。
【０００９】
図１、図２に示すような従来の符号化装置および復号化装置について、参考文献[1]、pp. 104-128に詳しく記されている。
【００１０】
なお、この技術分野に関する参考文献としては、例えば、
[1] B. J. Frey, Graphical models for machine learning and digital communication, MIT Press, 1998.
[2] J. Rissanen and G. G. Langdon, "Arithmetic coding," IBM Journal of Research and Development, vol. 23, pp. 149-162, 1976.
[3] S. Arimoto, "An algorithm for calculating the capacity of an arbitrary discrete memoryless channel," IEEE Trans. Inform. Theory, vol. IT-18, pp. 14-20, Jan. 1972.
[4] R. E. Blahut, "Comptation of channel capacity and rate-distortion functions," IEEE Trans. Inform. Theory, vol. IT-18, pp. 460-473, Jul. 1972.
[5] N. Tishby, F. C. Pereira, and W. Bialek," The information bottleneck method," Proc. of the 37-th Annual Allerton Conference on Comunication, Control and Computing, pp. 368-377, 1999.がある。
【００１１】
【発明が解決しようとする課題】
上述した従来の符号化システムでは、符号器１０内の多値情報源符号器１４と復号器２０内の多値情報源復号器２４とが互いに逆写像の関係にあり、また、符号器１０内の算術復号器１３と復号器２０内の算術符号器２３が互いに逆写像の関係にあることから、復号器のバッファ２１の状態は、符号器のバッファ１１の状態を、逆順の時間で完全に再現する。したがって、上述した従来の符号化システムでは、入力データと再生データの間に歪み（データの食い違い）が全くないことを前提としており、入力データと再生データの間に歪みを許す場合の動作は保証されていない。
【００１２】
ところが、より短い符号語長を実現するために、入力データと再生データとの間に歪みを許す必要がある場合がある。例えば、以下に述べるような多端子情報源符号化、有歪み情報源符号化、復号器に部分補助情報を伴う情報源符号化などにおいては、入力データと再生データとの間に歪みを許す必要がある。
【００１３】
多端子情報源符号化：
多端子情報源符号化では、離れたところにある複数の入力データをそれぞれ別々の符号器を用いて符号化して、復号器はそれらの符号語を元に、入力データの組を再生する。図３は、２つの入力データＸ，ＺをそれぞれレートＲ_X，Ｒ_Zで符号化する装置を表している。すなわち、ｆ_X、ｆ_Zでそれぞれ表される符号器３０_X、３０_Zが設けられており、これらからの符号語が、ｇで表されている復号器３１に入力し、入力データの組(Ｘ，Ｚ)を出力する。ここでは、Ｘ，Ｚは、入力データもしくは再生データを表す確率変数である。また、Ｈ(Ｘ｜Ｚ)、Ｈ(Ｚ｜Ｘ)はそれぞれ条件つきエントロピーであり、Ｈ(ＸＺ)はエントロピーであって、いずれもアルゴリズムが達成する符号化レート下限を表している。そして、この多端子情報源符号化のシステムにおいては、Ｒ_X≧Ｈ(Ｘ｜Ｚ)、Ｒ_Z≧Ｈ(Ｚ｜Ｘ)、Ｒ_X＋Ｒ_Z≧Ｈ(ＸＺ)の関係が成り立っている。多端子情報源符号化では、入力データと再生データの間の歪みをできる限り小さく、それぞれの符号器の符号化レートをできる限り小さくすることが望ましい。
【００１４】
有歪み情報源符号化：
有歪み情報源符号化では、入力データＹと再生データＺの間に、歪み尺度ρで計ることのできるあらかじめ定められた歪みを許容したうえで、符号化レートをできる限り小さくする符号化を行う。図４は、入力データＹをレートＲ_Yで符号化して、再生データＺの間の歪みがＥ_YZρ(Ｙ,Ｚ)（Ｅは平均を表す）以下となるような装置を表している。すなわち、ｆ_Yで表される符号器４０が設けられており、これからの符号語が、ｇで表されている復号器４１に入力して、再生データＺが得られるようになっている。ここでは、Ｙは入力データを表す確率変数であり、Ｚは再生データを表す確率変数であり、Ｉ(Ｙ;Ｚ)は相互情報量すなわちアルゴリズムが達成する符号化レートであり、Ｅ_YZρ(Ｙ,Ｚ)はアルゴリズムが達成する平均歪みである。
【００１５】
復号器に部分補助情報を伴う情報源符号化：
復号器に部分補助情報を伴う情報源符号化では、復号器においてもう一つの情報Ｙが利用できることを前提として、入力データＸを再生する。図５は補助情報ＹをレートＩ(Ｙ;Ｚ)で符号化し、入力データＸをレートＨ(Ｘ|Ｚ)で符号化してＸを再生する装置を表している。Ｘ，Ｙを入力データもしくは出力データを表す確率変数、Ｚを事前に与える確率変数として、ｆ_X、ｆ_Yでそれぞれ表される符号器５０_X、５０_Yが設けられており、符号器５０_Xからは条件付エントロピーH(Ｘ|Ｚ)、すなわちアルゴリズムが達成する符号レートで符号語が出力され、符号器５０_Yからは相互情報量Ｉ(Ｙ;Ｚ)、すなわちアルゴリズムが達成する符号化レートで符号語が出力され、ｇで表される復号器５１はこれらの符号語に基づいて再生データを出力する。ここでも、入力データと再生データの間の歪みをできる限り小さく、それぞれの符号器の符号化レートをできる限り小さくすることが望ましい。
【００１６】
本発明は、上記の従来システムの欠点に鑑みてなされたものであり、歪みを許す符号化を行うことを可能とすることによって、より小さい符号化レートを実現することができる、データ符号化・復号化方法及び装置を提供することを目的とする。
【００１７】
【課題を解決するための手段】
本発明のデータ符号化方法は、入力データを符号化する方法であって、複数のブロックに分割された入力データの一つのブロックを、符号化写像生成ブロックと符号化対象ブロックに分割するステップと、符号器バッファに格納された符号化写像生成ブロックと符号化対象ブロックから符号化写像を用いて符号化対象ブロックの符号語を得るステップと、無歪み符号器によって符号化写像生成ブロックを用いて符号化写像生成ブロックの符号語を得るステップと、符号器バッファに残るもっとも古い符号化写像生成ブロックを破棄し、符号化写像生成ブロックを新たに符号器バッファに蓄積するステップと、これらの各ステップを複数のブロックがなくなるまで繰り返し実行するステップと、を有する。
【００１８】
本発明のデータ復号化方法は、例えば上述のようにして生成された符号化対象ブロックの符号語と符号化写像生成ブロックの符号語とから再生データを獲得する復号化方法であって、符号化対象ブロックの符号語を取り出し、その符号化対象ブロックの符号語と復号器バッファに格納された符号化写像生成ブロックとに基づいて復号化写像によって符号化対象ブロックの再生データを得るステップと、符号化写像生成ブロックの符号語を取り出して無歪み復号器によって符号化写像生成ブロックを得るステップと、復号器バッファに残るもっとも古い符号化写像生成ブロックを破棄し、復号した符号化写像生成ブロックを新たに復号器バッファに蓄積するステップと、符号化対象ブロックの再生データと復号した符号化写像生成ブロックを連結して出力するステップと、これらの各ステップを全ての符号語がなくなるまで繰り返し実行するステップと、を有する。
【００１９】
本発明のデータ符号化装置は、入力データを符号化するデータ符号化装置であって、複数のブロックに分割された入力データの各ブロックを、符号化写像生成ブロックと符号化対象ブロックに分割するブロック分割装置と、符号化写像生成ブロックを一時的に格納する符号器バッファと、符号器バッファの内容と符号化対象ブロックから符号化写像を用いて符号化対象ブロックの符号語を得る符号化写像部と、符号化写像生成ブロックから符号化写像生成ブロックの符号語を得る無歪み符号器と、を有し、新たな符号化写像生成ブロックが入力するつど符号器バッファにおいて最も古い符号化写像生成ブロックが破棄され、その新たな符号化写像生成ブロックが符号器バッファに蓄積される。
【００２０】
本発明のデータ復号化装置は、
符号化対象ブロックの符号語と符号化写像生成ブロックの符号語とから再生データを獲得するデータ復号化装置であって、符号化写像生成ブロックの符号語を一時的に格納する復号器バッファと、符号化対象ブロックの符号語を取り出し、その符号化対象ブロックの符号語と復号器バッファの内容とに基づいて復号化写像によって符号化対象ブロックの再生データを得る復号化写像部と、符号化写像生成ブロックの符号語を取り出して符号化写像生成ブロックを得る無歪み復号器と、符号化対象ブロックの再生データと復号した符号化写像生成ブロックを連結して出力するブロック連結装置と、を有し、新たな符号化写像生成ブロックが復号されるつど復号器バッファにおいて最も古い符号化写像生成ブロックが破棄され、その新たな符号化写像生成ブロックが復号器バッファに蓄積される。
【００２１】
最適な符号化レートを達成するために符号をランダムに構成しているが、その場合には、符号器と復号器の間で、同期した乱数が必要となる。そこで本発明では、乱数を得るために、過去に符号化した系列の一部をバッファに蓄えておき、そこから符号をランダムに構成する。さらに、乱数の同期を取るために、観測データを符号化する際に、「符号化対象ブロック」と「符号化写像生成ブロック」の２つに分割して、別々の符号化を行う。
【００２２】
本発明による符号化・復号化方法と従来法との違いは以下の点である。
【００２３】
従来法では、符号語の全てがバッファに蓄えられていたが、本発明では、効率よく符号化されるデータとバッファに蓄えるデータとに入力データを分割して別々に符号化することによって、バッファの同期を保ちつつ、より小さな符号化レートを持つ歪みを許す符号化を実現している。
【００２４】
また、従来法では、固定された符号化写像・復号化写像（従来法では多値情報源符号器・多値情報源復号器が該当する）を用いて、バッファの内容を無歪みで符号化していたが、本発明では、バッファの内容を用いて符号化写像・復号化写像を動的に変更させることによって、より小さな符号化レートを持つ歪みを許す符号化を実現している。
【００２５】
【発明の実施の形態】
次に、本発明の好ましい実施の形態について、図面を参照して説明する。図６は、本発明の実施の一形態の符号化・復号化装置における符号化装置（符号器）の構成を示すブロック図であり、図７は図６の符号化装置と組み合わされて使用される復号化装置（復号器）の構成を示すブロック図である。以下の説明では、説明を分かりやすくするために、一つの情報源出力に関して記述しているが、実際には以下に述べる操作は複数の情報源出力に関して行われる。
【００２６】
図６に示す符号器６０は、入力データ６５が入力し入力データ６５をブロックに分割して各ブロックを符号化対象ブロック６６と符号化写像生成ブロック６７に分割するブロック分割装置６１と、符号化写像生成ブロック６７を一時的に格納するバッファ（すなわち符号器バッファ）６２と、バッファ６２の内容及び符号化対象ブロック６６に基づいて符号化対象ブロックの符号語６８を計算して出力する符号化写像部６３と、符号化写像生成ブロック６７から符号化写像生成ブロックの符号語６９を計算して出力する無歪み符号器６４と、から構成されている。ここで、符号化写像部６３は、後述するような符号化写像を実行するものであり、無歪み符号器６４とは、単射の写像で表されるものである。また、バッファ６２には、適当な初期値が格納されている。
【００２７】
次に、この符号器６０の動作を説明する。最初に、ブロック分割装置６１は、入力データ６５をブロックに分割し、各ブロックを符号化対象ブロック６６と符号化写像生成ブロック６７とに分割する。次に、符号化写像部６３は、バッファ６２の内容を読み取り、情報源に即した符号化写像を用いて符号化対象ブロック６６を符号化して符号化対象ブロックの符号語６８を出力し、これを図７に示す復号器７０に送信する。また、無歪み符号器６４は、符号化写像生成ブロック６７を符号化して符号化写像生成ブロック符号語６９を出力し、これを復号器７０に送信する。最後に、バッファ６２は、その記録しているもっとも古いデータを破棄し、ブロック分割装置６１から送られてきた符号化写像生成ブロック６７を記録する。これらの処理は、入力データにおける処理すべきブロックがなくなるまで、繰り返して実行される。
【００２８】
実際に符号化・復号化システムを構成する場合には、上述したような符号器６０を必要な数だけ用意する。
【００２９】
次に、復号器７０について説明する。図７に示す復号器７０は、複数の符号器６０のそれぞれから符号化対象ブロックの符号語６８及び符号化写像生成ブロックの符号語６９を受け入れることができるようになっている。もちろん、単一の符号器６０のみから符号化対象ブロックの符号語６８及び符号化写像生成ブロックの符号語６９が復号器７０に入力してもよい。そして復号器７０は、バッファ（すなわち復号器バッファ）７１と、符号化対象ブロックの符号語６８とバッファ７１の内容とに基づき、復号化写像によって符号化対象ブロックの再生データ７５を得る復号化写像部７２と、符号化写像生成ブロックの符号語６９を再生して符号化写像生成ブロック６７を得る無歪み復号器７３と、符号化対象ブロックの再生データ７５と符号化写像生成ブロック６７とを連結して再生データ７６を得るブロック連結装置７４と、から構成されている。ここで、無歪み復号器７３は、図６で示される各符号器６０の無歪み符号器６４の表す写像の逆写像の集合体である。また、バッファ７１は、各符号器６０に対応するバッファ６２の集合体として構成されており、各符号器のバッファ６２と同じ初期値が格納され、初期値が格納された後は、無歪み復号器７３から入力する符号化写像生成ブロック６７を格納するようになっている。実際には、後述するように、符号器６０のバッファ６２に格納される初期値と復号器７０のバッファ７１に格納される初期値が一致するように、符号器６０と復号器７０の間で初期化処理が行われることになる。
【００３０】
次に、この復号器７０の動作を説明する。復号化写像部７２は、バッファ７１の内容を読み取り、図６に示すような各符号器６０より符号化対象ブロックの符号語６８を受信し、これらを用いて復号化写像により符号化対象ブロックの再生データ７５を出力する。一方、無歪み復号器７３は、各符号器６０より符号化写像生成ブロック符号語６９を受信し、これらより各符号器６０の符号化写像生成ブロック６７を再生する。続いて、ブロック連結装置７４は、符号化対象ブロックの再生データ７５と無歪み復号器から送られてきた符号化写像生成ブロック６７を連結して、再生データ７６とする。最後に、バッファ７１は、その記録しているもっとも古いデータを破棄し、無歪み復号器７３から送られてきた符号化写像生成ブロック６７を記録する。
【００３１】
以下、本発明の符号化・復号化方法及び装置について、多端子情報源符号化、有歪み情報源符号化、復号器に部分補助情報を伴う情報源符号化のそれぞれについて応用した場合を説明することにより、さらに詳しく説明する。最初に、以下の説明中に現れる記号の説明をする。
【００３２】
集合
【００３３】
【数２】

【００３４】
の補集合と要素数をそれぞれ
【００３５】
【数３】

【００３６】
と書き、集合
【００３７】
【数４】

【００３８】
の差集合を
【００３９】
【数５】

【００４０】
と書く。集合
【００４１】
【数６】

【００４２】
を有限集合とし、
【００４３】
【数７】

【００４４】
とする。
【００４５】
【数８】

【００４６】
のｉ番目の要素をｘ_iもしくは[ｘⁿ]_iと記す。またｘⁿ≡ｘ₁＊…＊ｘ_nに対してｘ_i ^j≡ｘ_i＊…＊ｘ_jとする。 文字列の結合を与える演算を＊とする。例えば、ｘⁿ＝(ｘ₁,...,ｘ_n)，ｙ^m＝(ｙ₁,...,ｙ_m)に対してｘⁿ＊ｙ^m≡(ｘ₁,...,ｘ_n,ｙ₁,...,ｙ_m)である。符号器
【００４７】
【数９】

【００４８】
、復号器
【００４９】
【数１０】

【００５０】
、の復号誤り文字数ｄ(ｘⁿ)を次のように定義する。
【００５１】
【数１１】

【００５２】
これは、系列ｘⁿと再生された系列φ_n ^-1(φ_n(ｘⁿ))との間の異なる文字の個数を表す。
【００５３】
【数１２】

【００５４】
を
【００５５】
【数１３】

【００５６】
桁で２進数表記したものとその逆写像とを、それぞれ、
【００５７】
【数１４】

【００５８】
と記述する。同様に、
【００５９】
【数１５】

【００６０】
を
【００６１】
【数１６】

【００６２】
桁で２進数表記したものとその逆写像とを、それぞれ、
【００６３】
【数１７】

【００６４】
と記述する。
【００６５】
【数１８】

【００６６】
値の確率変数Ｘが与えられた時、対応する確率分布をμ_Xと書く。また
【００６７】
【数１９】

【００６８】
と書く。ＸのエントロピーＨ(Ｘ)を
【００６９】
【数２０】

【００７０】
と定義する。Ｘ，Ｙの結合エントロピーをＨ(ＸＹ)、Ｙが与えられたときのＸの条件つきエントロピーをＨ(Ｘ｜Ｙ)≡Ｈ(ＸＹ)−Ｈ(Ｙ)、Ｘ，Ｙの相互情報量をＩ(Ｘ;Ｙ)≡Ｈ(Ｘ)＋Ｈ(Ｙ)−Ｈ(ＸＹ)とする。
【００７１】
【数２１】

【００７２】
上の確率分布ν、μのダイバージェンスＤ(ν‖μ)を以下のように定義する。
【００７３】
【数２２】

【００７４】
【数２３】

【００７５】
から得られる経験分布
【００７６】
【数２４】

【００７７】
を次のように定義する。
【００７８】
【数２５】

【００７９】
これは、
【００８０】
【数２６】

【００８１】
が、系列ｘⁿ中のａの出現頻度を表すことを意味する。
【００８２】
【数２７】

【００８３】
から得られる条件つき経験分布
【００８４】
【数２８】

【００８５】
は任意の
【００８６】
【数２９】

【００８７】
に対して、
【００８８】
【数３０】

【００８９】
を満たす条件つき確率分布として定義される。これはｙ_i＝ｂが成り立つようなｉであってさらにｘ_i＝ａが成り立つｉの頻度を表す。
【００９０】
実数０＜α＜∞，γ＞０、自然数ｋに対して、ζ(α,γ)，λ(α,ｋ)を次のように定義する。これらは数式の記述を簡潔にするために用いられる。
【００９１】
【数３１】

【００９２】
ｉをｎで割った余りをｉ％ｎ，０≦ｉ％ｎ≦ｎ−１とする。ここでｉは２進数で表現されている場合もあることを注意しておく．
《多端子情報源符号化への応用》
ここで、本実施形態による符号化・復号化方法を多端子情報源符号化に適用した例を説明する。相関のある複数の情報源Ｘ，ＺをそれぞれレートＲ_X，Ｒ_Zで独立に符号化して復号器に送り、復号器がＸとＺを復号するものとする。システム構成としては、上述の図３に示したようなシステムを使用し、符号器３０_X、３０_Zとして、それぞれ、図６に示した符号器６０を使用して情報源Ｘ，Ｙの符号化を行わせ、復号器３１として図７に示した復号器７０を使用してＸとＹとの復号を行わせるようにする。
【００９３】
以下では、
【００９４】
【数３２】

【００９５】
を仮定し、次の定義を用いる。
【００９６】
【数３３】

【００９７】
【数３４】

【００９８】
を次のように定義する。
【００９９】
【数３５】

【０１００】
そして
【０１０１】
【数３６】

【０１０２】
に適当な順序を与えたときの
【０１０３】
【数３７】

【０１０４】
の番号を
【０１０５】
【数３８】

【０１０６】
と記す。
【０１０７】
【数３９】

【０１０８】
を簡単に計算する方法として、算術符号（参考文献[2]参照）のアルゴリズム等が挙げられる。実際には、並べる順序は、性能の解析に影響しないので、任意に取ることができる。関数
【０１０９】
【数４０】

【０１１０】
を以下のように定義する。
【０１１１】
【数４１】

【０１１２】
π_kは、
【０１１３】
【数４２】

【０１１４】
の元を
【０１１５】
【数４３】

【０１１６】
個ずつ束にして数字を割り当て、
【０１１７】
【数４４】

【０１１８】
の元にはそれらとは異なる数字を割り当てる写像である。大雑把に言うと、
【０１１９】
【数４５】

【０１２０】
等分されている。同様に
【０１２１】
【数４６】

【０１２２】
を定義し、
【０１２３】
【数４７】

【０１２４】
を用いてπ_k'を同様に定義する。
【０１２５】
ｑ_k≡Ｍ_k＋ｋ²２^kとする。全体の系列長
【０１２６】
【数４８】

【０１２７】
に対して
【０１２８】
【数４９】

【０１２９】
を、それぞれ重なりのない、長さｋ＋２のサブブロックに分割する。サブブロック
【０１３０】
【数５０】

【０１３１】
を次のように定義する。
【０１３２】
【数５１】

【０１３３】
【数５２】

【０１３４】
についても同様に定義する。
【０１３５】
【数５３】

【０１３６】
の要素を
【０１３７】
【数５４】

【０１３８】
桁の２進数で表記する写像をＮ_Xとし、その逆写像をＮ_X ^-1とする。同様に、
【０１３９】
【数５５】

【０１４０】
の要素を
【０１４１】
【数５６】

【０１４２】
桁の２進数で表記する写像をＮ_Zとし、その逆写像をＮ_Z ^-1とする。
【０１４３】
ここで、情報源Ｘを符号化する符号器（図３での符号器３０_X）での処理を説明する。上述したようにこの符号器には、図６に示した本発明による符号器６０が使用される。図８は、符号化処理を説明するフローチャートである。なお、後述するように、情報源Ｚを符号化する符号器の動作も情報源Ｘを符号化する符号器の動作とほぼ同じであるから、図８は両方の符号器の動作を示しており、この図では、ステップＡ１〜Ａ１２は情報源Ｘを符号化する符号器の動作を表し、ステップＢ１〜Ｂ１２は情報源Ｚを符号化する符号器の動作を表している。
【０１４４】
符号器６０は、
【０１４５】
【数５７】

【０１４６】
で表されるバッファ６２を持っているものとする。ステップＡ１〜Ａ６は、符号器６０のバッファ６２及び復号器７０のバッファ７１を初期化するために符号器６０で実施されるステップであり、初めてステップＡ８を実行する時点（ｉ＝０）では、符号器のバッファ６２と復号器のバッファ７１の内容が同一となる。ステップＡ７〜Ａ１２は、本発明の方法による符号化のステップである。
【０１４７】
まず、ステップＡ１においてｉ←−Ｍ_kとし、ステップＡ２において、情報源Ｘに対応した集合を用いてバッファ６２の全てに適当な初期値を格納する。そして、ステップＡ３において、ｉ番目のサブブロックについての符号語を復号器７０に送り、ステップＡ４において、ｉ番目のサブブロック（ただし符号化写像生成ブロックに対応する部分）を用いてバッファ６２を更新する。その後、ｉをインクリメントし（ステップＡ５）、ステップＡ６においてｉ＝０であるかどうかを判断し、ｉ＝０であればステップＡ７に移行するものとし、ｉ＜０であればステップＡ３に戻る。
【０１４８】
ステップＡ７において、ブロック分割装置６１は入力データ６５のブロックを符号化写像生成ブロック６７と符号化対象ブロック６６に分割し、ステップＡ８において、符号化写像部６３は、情報源Ｘに対応した符号化写像を用いることにより、バッファ６２の内容と符号化対象ブロック６６とに基づいて、符号化対象ブロックの符号語６８を計算し、復号器７０に送信する。一方、無歪み符号器６４は情報源Ｘに対応する単射写像で表されており、ステップＡ９において無歪み符号器６４は、符号化写像生成ブロックの符号語６９を計算して復号器７０に送信する。その後、ステップＡ１０において、ｉ番目のサブブロックの符号化写像生成ブロックを使用して、バッファ６２内の最も古いデータを破棄してバッファ６２を更新する。その後、ｉをインクリメントし（ステップＡ１１）、ステップＡ１２において、処理対象のブロック（入力データ６５）がなくなったかどうかを判断するためにｉ＝ｑ_k−Ｍ_kかどうかを判断し、ｉ＝ｑ_k−Ｍ_kならば処理を終了し、そうでなければステップＡ７へ戻る。
【０１４９】
下表に、アルゴリズムとして、以上説明したＸを符号化する符号器での処理を詳細に示す。
【０１５０】
【表１】

【０１５１】
次に、情報源Ｚを符号化する符号器（図３での符号器３０_Z）での処理を説明する。上述したようにこの符号器には、図６に示した本発明による符号器６０が使用される。実際には、Ｚの符号化に用いられる符号器での処理とＸの符号器に用いられる符号器での処理は、情報源がＸであるかＺであるかの違いを除けばほとんど同じである。
【０１５２】
符号器６０は、
【０１５３】
【数５８】

【０１５４】
を持っているものとする。図８におけるステップＢ１〜Ｂ６は、符号器６０のバッファ６２及び復号器７０のバッファ７１を初期化するために符号器６０で実施されるステップであり、初めてステップＢ８を実行する時点（ｉ＝０）では、符号器のバッファ６２と復号器のバッファ７１の内容が同一となる。ステップＢ７〜Ｂ１２は、本発明の方法による符号化のステップである。
【０１５５】
下表に、アルゴリズムとして、以上説明したＺを符号化する符号器での処理を詳細に示す。ここで、Ｘの符号器でのアルゴリズムとの本質的な相違点は、バッファの更新に[ｘ(i)]₁を用いていた代わりに[ｚ(i)]₂を用いている点である。これは、
【０１５６】
【数５９】

【０１５７】
の独立性を保つためである。
【０１５８】
【表２】

【０１５９】
次に、Ｘの符号語とＺの符号語とが入力してこれらを復号して出力する復号器（図３での復号器３１）での処理を説明する。上述したようにこの復号器には、図７に示した本発明による復号器７０が使用される。図９は復号化処理を説明するフローチャートである。
【０１６０】
最初に、
【０１６１】
【数６０】

【０１６２】
を次のように定義する。
【０１６３】
【数６１】

【０１６４】
復号器のバッファ７１は、
【０１６５】
【数６２】

【０１６６】
で表されるＸの符号器のバッファ６２と、
【０１６７】
【数６３】

【０１６８】
で表されるＺの符号器のバッファ６２と、で構成されている。さらに復号器７０は、データベース
【０１６９】
【数６４】

【０１７０】
を持っているとする。
【０１７１】
ステップＣ１〜Ｃ７は、バッファ７１の初期化するために復号器７０で実施されるステップであり、初めてステップＣ８を実行する時点（ｉ＝０）では、符号器６０のバッファ６２と復号器７０のバッファ７１の内容が同一となる。ステップＣ８〜Ｃ１５は、本発明の方法による復号化のステップである。
【０１７２】
まず、ステップＣ１においてｉ←−Ｍ_kとし、ステップＣ２において情報源Ｘ，Ｚのそれぞれごとにバッファ７１に符号器６０のバッファ６２で用いたものと同じ集合の元を用いて初期値を格納する。そして、ステップＣ３において、ＸとＺについてのそれぞれのｉ番目のサブブロックについての符号語を各符号器６０から受信し、これを復号する。ステップＣ４では、ＸとＺについて正しく復号されたサブブロック（符号化写像生成ブロックに対応する部分）を用いてバッファ７１を更新する。さらにステップＣ５においては、情報源ごとにそのときのｉの値に関してデータベースに対応する項目がある場合に、データベースも更新する。その後、ｉをインクリメントし（ステップＣ６）、ステップＣ７においてｉ＝０であるかどうかを判断し、ｉ＝０であればステップＣ８に移行するものとし、ｉ＜０であればステップＣ３に戻る。
【０１７３】
ステップＣ８において、復号化写像部７２は、ステップＣ５またはステップＣ１０〜Ｃ１２においてバッファ７１から計算されたデータベースを用いて、符号化対象ブロックの再生データ７５を計算する。すなわち、情報源ごとに符号化対象ブロックの符号語６８を受信し、これに、その情報源に応じた復号化写像を適用して結果を求め、それらの結果に応じてデータベースを検索して符号化対象ブロックの再生データ７５を決定する。
【０１７４】
ステップＣ９において、無歪み復号器７３は、Ｘの符号器においてステップＡ９で符号化された符号化写像生成ブロックの符号語６９を受信して、符号化写像生成ブロック６７を復号し、同様に、Ｚの符号器においてステップＢ９で符号化された符号化写像生成ブロックの符号語６９を受信して、符号化写像生成ブロック６７を復号する。これらは常に正しく復号される。
【０１７５】
ステップＣ１０においては、ステップＣ１１におけるバッファ７１の更新に先立って、その更新に関係する項目をデータベースから削除し、ステップＣ１１においては、ＸとＺについての正しく復号された符号化写像生成ブロックを用いて、バッファ７１内の最も古いデータを破棄してバッファ７１の更新を行い、ステップＣ１２では、バッファ７１での更新値に基づいてデータベースの更新を行う。その後、ステップＣ１３において、ブロック連結装置７４は、ステップＣ８で得られた符号化対象ブロックの再生データ７５とステップＣ９で得られた符号化写像生成ブロック６７を連結して再生データ７６を得る。続いて、ｉをインクリメントし（ステップＣ１４）、ステップＣ１５において、処理対象のブロックがなくなったかどうかを判断するためにｉ＝ｑ_k−Ｍ_kかどうかを判断し、ｉ＝ｑ_k−Ｍ_kならば処理を終了し、そうでなければステップＣ８へ戻る。
【０１７６】
下表に、アルゴリズムとして、以上説明した復号器での処理を詳細に示す。
【０１７７】
【表３】

【０１７８】
【表４】

【０１７９】
次に、上述した多端子情報源符号化への応用の一例について説明する。
【０１８０】
全体の系列
【０１８１】
【数６５】

【０１８２】
に対する符号器の総符号長をそれぞれ
【０１８３】
【数６６】

【０１８４】
とする。そして、復号誤り文字数を
【０１８５】
【数６７】

【０１８６】
とする。
【０１８７】
その結果、Ｘ，Ｚを上述の条件(1)〜(3)を満たす相関のある定常無記憶情報源とする。このとき、次の性質が成り立つ。
【０１８８】
【数６８】

【０１８９】
《有歪み情報源符号化への応用》
次に、本実施形態による符号化・復号化方法を有歪み情報源符号化に適用した例を説明する。ここでは、情報源ＹをレートＲ_Yで符号化し復号後に生じる歪みを許容するものとする。システム構成としては、上述の図４に示したようなシステムを使用し、符号器４０として図６に示した符号器６０を使用し、復号器４１として図７に示した復号器７０を使用するものとする。
【０１９０】
ここでは、歪み関数を
【０１９１】
【数６９】

【０１９２】
として、
【０１９３】
【数７０】

【０１９４】
を仮定する。そして、
【０１９５】
【数７１】

【０１９６】
とする。
【０１９７】
【数７２】

【０１９８】
を満たす結合分布
【０１９９】
【数７３】

【０２００】
を取る。そして、Ｚを周辺分布
【０２０１】
【数７４】

【０２０２】
と対応する確率変数としたとき、Ｉ(ｙ;ｚ)＞０を満たしていると仮定する。
【０２０３】
以下では、
【０２０４】
【数７５】

【０２０５】
とする。
【０２０６】
【数７６】

【０２０７】
を次のように定義する。
【０２０８】
【数７７】

【０２０９】
【数７８】

【０２１０】
を辞書式順序に並べた順序を与える関数をそれぞれ
【０２１１】
【数７９】

【０２１２】
とする。
【０２１３】
そして関数
【０２１４】
【数８０】

【０２１５】
を以下のように定義する。
【０２１６】
【数８１】

【０２１７】
σ_kは、
【０２１８】
【数８２】

【０２１９】
の元を
【０２２０】
【数８３】

【０２２１】
個ずつ束にして割り当てた数字を
【０２２２】
【数８４】

【０２２３】
によって
【０２２４】
【数８５】

【０２２５】
の元に移し、
【０２２６】
【数８６】

【０２２７】
の元にはあらかじめ定めた
【０２２８】
【数８７】

【０２２９】
を割り当てる写像である。ここで、
【０２３０】
【数８８】

【０２３１】
は以後の解析に影響しない。
【０２３２】
ｑ_k≡Ｍ_k＋ｋ²２^kとする。全体の系列長
【０２３３】
【数８９】

【０２３４】
に対して、
【０２３５】
【数９０】

【０２３６】
を重なりのない長さｋ＋１のサブブロックに分割し、サブブロック
【０２３７】
【数９１】

【０２３８】
を次のように定義する。
【０２３９】
【数９２】

【０２４０】
【数９３】

【０２４１】
の要素を
【０２４２】
【数９４】

【０２４３】
桁の２進数で表記する写像をＮ_Yとし、その逆写像をＮ_Y ^-1とする。
【０２４４】
ここで符号器（図４での符号器４０）での処理を説明する。上述したようにこの符号器には、図６に示した本発明による符号器６０が使用される。図１０は、符号化処理を説明するフローチャートである。
【０２４５】
符号器６０は、
【０２４６】
【数９５】

【０２４７】
で表されるバッファ６２を持っているものとする。ステップＦ１〜Ｆ６は、符号器６０のバッファ６２及び復号器７０のバッファ７１を初期化するために符号器６０で実施されるステップであり、初めてステップＦ８を実行する時点（ｉ＝０）では、符号器のバッファ６２と復号器のバッファ７１の内容が同一となる。ステップＦ７〜Ｆ１２は、本発明の方法による符号化のステップである。
【０２４８】
まず、ステップＦ１においてｉ←−Ｍ_kとし、ステップＦ２において情報源Ｙに対応する集合を用いてバッファ６２の全てに適当な初期値を格納する。そして、ステップＦ３において、ｉ番目のサブブロックについての符号語を復号器７０に送り、ステップＦ４において、ｉ番目のサブブロック（ただし符号化写像生成ブロックに対応する部分）を用いてバッファ６２を更新する。その後、ｉをインクリメントし（ステップＦ５）、ステップＦ６においてｉ＝０であるかどうかを判断し、ｉ＝０であればステップＦ７に移行するものとし、ｉ＜０であればステップＦ３に戻る。
【０２４９】
ステップＦ７において、ブロック分割装置６１は入力データ６５のブロックを符号化写像生成ブロック６７と符号化対象ブロック６６に分割し、ステップＦ８において、符号化写像部６３は、情報源Ｙに対応した符号化写像を用いることにより、バッファ６２の内容と符号化対象ブロック６６とに基づいて、符号化対象ブロックの符号語６８を計算し、復号器７０に送信する。一方、無歪み符号器６４は情報源Ｙに対応する単射写像で表されるから、ステップＦ９においてこの無歪み符号器６４は、符号化写像生成ブロックの符号語６９を計算して復号器７０に送信する。その後、ステップＦ１０において、ｉ番目のサブブロックの符号化写像生成ブロックを使用して、バッファ６２内の最も古いデータを破棄してバッファ６２を更新する。その後、ｉをインクリメントし（ステップＦ１１）、ステップＦ１２において、処理対象のブロック（入力データ６５）がなくなったかどうかを判断するためにｉ＝ｑ_k−Ｍ_kかどうかを判断し、ｉ＝ｑ_k−Ｍ_kならば処理を終了し、そうでなければステップＦ７へ戻る。
【０２５０】
下表に、アルゴリズムとして、以上説明した符号器での処理を詳細に示す。
【０２５１】
【表５】

【０２５２】
次に、復号器（図３での復号器３１）での処理を説明する。上述したようにこの復号器には、図７に示した本発明による復号器７０が使用される。図１１は復号化処理を説明するフローチャートである。
【０２５３】
復号器のバッファ７１は、
【０２５４】
【数９６】

【０２５５】
で表される符号器のバッファ６２で構成されている。
【０２５６】
ステップＧ１〜Ｇ６は、バッファ７１の初期化するために復号器７０で実施されるステップであり、初めてステップＧ８を実行する時点（ｉ＝０）では、符号器６０のバッファ６２と復号器７０のバッファ７１の内容が同一となる。ステップＧ７〜Ｇ１２は、本発明の方法による復号化のステップである。
【０２５７】
まず、ステップＧ１においてｉ←−Ｍ_kとし、ステップＧ２においてバッファ７１に符号器６０のバッファ６２で用いたものと同じ集合の元を用いて初期値を格納する。そして、ステップＧ３において、ｉ番目のサブブロックについての符号語を各符号器６０から受信し、これを復号する。ステップＧ４では、正しく復号されたサブブロック（符号化写像生成ブロックに対応する部分）を用いてバッファ７１を更新する。その後、ｉをインクリメントし（ステップＧ５）、ステップＧ６においてｉ＝０であるかどうかを判断し、ｉ＝０であればステップＧ７に移行するものとし、ｉ＜０であればステップＧ３に戻る。
【０２５８】
ステップＧ７において、復号化写像部７２は、符号器６０のステップＦ８で符号化された符号化対象ブロックの符号語６８を受信し、この符号語とバッファ７１の内容とに基づいて、情報源Ｙの復号化写像を用い、符号化対象ブロックの再生データ７５を計算する。ステップＧ８において、無歪み復号器７３は、符号器６０においてステップＦ９で符号化された符号化写像生成ブロックの符号語６９を受信して、符号化写像生成ブロック６７を復号する。これは常に正しく復号される。ステップＧ９において、正しく復号された符号化写像生成ブロックを用いて、バッファ７１内の最も古いデータを破棄してバッファ７１の更新を行う。その後、ステップＧ１０において、ブロック連結装置７４は、ステップＧ７で得られた符号化対象ブロックの再生データ７５とステップＧ８で得られた符号化写像生成ブロック６７を連結して再生データ７６を得る。続いて、ｉをインクリメントし（ステップＧ１１）、ステップＧ１２において、処理対象のブロックがなくなったかどうかを判断するためにｉ＝ｑ_k−Ｍ_kかどうかを判断し、ｉ＝ｑ_k−Ｍ_kならば処理を終了し、そうでなければステップＧ７へ戻る。
【０２５９】
下表に、アルゴリズムとして、以上説明した復号器での処理を詳細に示す。
【０２６０】
【表６】

【０２６１】
次に、上述した有歪み情報源符号化への応用の一例について説明する。
【０２６２】
全体の系列
【０２６３】
【数９７】

【０２６４】
に対する符号器の総符号長を
【０２６５】
【数９８】

【０２６６】
とする。そして、復号の際に生じた歪みを
【０２６７】
【数９９】

【０２６８】
とする。このとき、次の性質が成り立つ。
【０２６９】
性質：Ｉ(Ｙ;Ｚ)＞０を満たす任意の分布ｐ_YZを取れば、
【０２７０】
【数１００】

【０２７１】
ところで、レートと歪みはトレードオフの関係があり、最適な組合せは、レート歪み曲線と呼ばれる次の曲線上にある。
【０２７２】
【数１０１】

【０２７３】
分布ｐ_YZをArimoto-Blahutのアルゴリズム(参考文献[3]，[4])を用いて、（Ｉ(Ｙ;Ｚ)，Ｅ_YZρ(Ｙ,Ｚ)）がレート歪み曲線（歪みレート曲線）上にあるように取れば、次の性質が成立する。
【０２７４】
性質：（Ｉ(Ｙ;Ｚ)，Ｅ_YZρ(Ｙ,Ｚ)）がレート歪み曲線（歪みレート曲線）上にあるように分布ｐ_YZを取れば、本実施形態によるアルゴリズムは漸近的に最適な有歪符号となる。
【０２７５】
《復号器に部分補助情報を伴う情報源符号化への応用》
次に、本実施形態による符号化・復号化方法を復号器に部分補助情報を伴う情報源符号化に適用した例を説明する。ここでは、情報源Ｙを部分補助情報としてレートＲ_Yで復号器に送り、Ｙと相関のある情報源ＸをレートＲ_Xで復号器に送って再生するものとする。システム構成としては、上述の図５に示したようなシステムを使用し、符号器５０_X、５０_Yとして、それぞれ、図６に示した符号器６０を使用して情報源Ｘ，Ｙの符号化を行わせ、復号器５１として図７に示した復号器７０を使用してＸの復号を行わせるようにする。
【０２７６】
ここでは、次の条件１〜４を満たす同時確率分布
【０２７７】
【数１０２】

【０２７８】
を用意する。
【０２７９】
【表７】

【０２８０】
【数１０３】

【０２８１】
を以下のように定義する。
【０２８２】
【数１０４】

【０２８３】
全体の系列長
【０２８４】
【数１０５】

【０２８５】
に対して、
【０２８６】
【数１０６】

【０２８７】
を、それぞれ重なりのない長さｋ＋２のサブブロックに分割する。サブブロック
【０２８８】
【数１０７】

【０２８９】
を次のように定義する。
【０２９０】
【数１０８】

【０２９１】
【数１０９】

【０２９２】
についても上記と同様に定義する。
【０２９３】
【数１１０】

【０２９４】
の要素を
【０２９５】
【数１１１】

【０２９６】
桁の２進数で表記する写像をＮ_Xとし、その逆写像をＮ_X ^-1とする。
【０２９７】
【数１１２】

【０２９８】
の要素を
【０２９９】
【数１１３】

【０３００】
桁の２進数で表記する写像をＮ_Yとし、その逆写像をＮ_Y ^-1とする。
【０３０１】
ここで、情報源Ｘを符号化する符号器（図５での符号器５０_X）での処理を説明する。上述したようにこの符号器には、図６に示した本発明による符号器６０が使用される。図１２は、符号化処理を説明するフローチャートである。
【０３０２】
上記と同様に、
【０３０３】
【数１１４】

【０３０４】
を定義する。Ｘの符号器は、Slepian-Wolfの符号器とほとんど同じである。
【０３０５】
符号器は、
【０３０６】
【数１１５】

【０３０７】
で表されるバッファ６２を持っているものとする。ステップＰ１〜Ｐ６は、符号器６０のバッファ６２及び復号器７０のバッファ７１を初期化するために符号器６０で実施されるステップであり、初めてステップＰ８を実行する時点（ｉ＝０）では、符号器のバッファ６２と復号器のバッファ７１の内容が同一となる。ステップＰ７〜Ｐ１２は、本発明の方法による符号化のステップである。
【０３０８】
まず、ステップＰ１においてｉ←−Ｍ_kとし、ステップＰ２において情報源Ｘに対応する集合を用いてバッファ６２の全てに適当な初期値を格納する。そして、ステップＰ３において、ｉ番目のサブブロックについての符号語を復号器７０に送り、ステップＰ４において、ｉ番目のサブブロック（ただし符号化写像生成ブロックに対応する部分）を用いてバッファ６２を更新する。その後、ｉをインクリメントし（ステップＰ５）、ステップＰ６においてｉ＝０であるかどうかを判断し、ｉ＝０であればステップＰ７に移行するものとし、ｉ＜０であればステップＰ３に戻る。
【０３０９】
ステップＰ７において、ブロック分割装置６１は入力データ６５のブロックを符号化写像生成ブロック６７と符号化対象ブロック６６に分割し、ステップＰ８において、符号化写像部６３は、情報源Ｘに対応した符号化写像を用いることにより、バッファ６２の内容と符号化対象ブロック６６とに基づいて、符号化対象ブロックの符号語６８を計算し、復号器７０に送信する。一方、情報源Ｘに対応する単射写像で表される無歪み符号器６４は、ステップＰ９において、符号化写像生成ブロックの符号語６９を計算して復号器７０に送信する。その後、ステップＰ１０において、ｉ番目のサブブロックの符号化写像生成ブロックを使用して、バッファ６２内の最も古いデータを破棄してバッファ６２を更新する。その後、ｉをインクリメントし（ステップＰ１１）、ステップＰ１２において、処理対象のブロック（入力データ６５）がなくなったかどうかを判断するためにｉ＝ｑ_k−Ｍ_kかどうかを判断し、ｉ＝ｑ_k−Ｍ_kならば処理を終了し、そうでなければステップＰ７へ戻る。
【０３１０】
下表に、アルゴリズムとして、以上説明した情報源Ｘを符号化する符号器での処理を詳細に示す。
【０３１１】
【表８】

【０３１２】
次に、部分補助情報源Ｙを符号化する符号器（図５での符号器５０_Y）での処理を説明する。上述したようにこの符号器には、図６に示した本発明による符号器６０が使用される。実際には、この符号器での処理は、上述した有歪み情報源符号化での符号器での処理と、ほとんど同じである。図１３は復号化処理を説明するフローチャートである。
【０３１３】
有歪み情報源符号化の場合と同様に、
【０３１４】
【数１１６】

【０３１５】
を定義し、さらに、
【０３１６】
【数１１７】

【０３１７】
を次のように定義する。
【０３１８】
【数１１８】

【０３１９】
符号器６０は、
【０３２０】
【数１１９】

【０３２１】
で表されるバッファ６２を持っているものとする。ステップＱ１〜Ｑ６は、符号器６０のバッファ６２を初期化するために符号器６０で実施されるステップであり、初めてステップＱ８を実行する時点（ｉ＝０）では、符号器のバッファ６２と復号器のバッファ７１の内容が同一となる。ステップＱ７〜Ｑ１２は、本発明の方法による符号化のステップである。
【０３２２】
まず、ステップＱ１においてｉ←−Ｍ_kとし、ステップＱ２において部分補助情報源Ｙに対応する集合を用いてバッファ６２の全てに適当な初期値を格納する。そして、ステップＱ３において、ｉ番目のサブブロックについての符号語を復号器７０に送り、ステップＱ４において、ｉ番目のサブブロックを用いてバッファ６２を更新する。その後、ｉをインクリメントし（ステップＱ５）、ステップＱ６においてｉ＝０であるかどうかを判断し、ｉ＝０であればステップＱ７に移行するものとし、ｉ＜０であればステップＱ３に戻る。
【０３２３】
ステップＱ７において、ブロック分割装置６１は入力データ６５のブロックを符号化写像生成ブロック６７と符号化対象ブロック６６に分割し、ステップＱ８において、符号化写像部６３は、部分補助情報源Ｙに応じた符号化写像を用いることにより、バッファ６２の内容と符号化対象ブロック６６とに基づいて、符号化対象ブロックの符号語６８を計算し、復号器７０に送信する。一方、ステップＱ９において、部分補助情報源Ｙに対応する単射写像で表される無歪み符号器６４は、符号化写像生成ブロックの符号語６９を計算して復号器７０に送信する。その後、ステップＱ１０において、ｉ番目のサブブロックを使用して、バッファ６２内の最も古いデータを破棄してバッファ６２を更新する。その後、ｉをインクリメントし（ステップＱ１１）、ステップＱ１２において、処理対象のブロック（入力データ６５）がなくなったかどうかを判断するためにｉ＝ｑ_k−Ｍ_kかどうかを判断し、ｉ＝ｑ_k−Ｍ_kならば処理を終了し、そうでなければステップＱ７へ戻る。
【０３２４】
下表に、アルゴリズムとして、以上説明した部分補助情報源Ｙを符号化する符号器での処理を詳細に示す。
【０３２５】
【表９】

【０３２６】
次に、復号器（図３での復号器３１）での処理を説明する。上述したようにこの復号器には、図７に示した本発明による復号器７０が使用される。図１４は復号化処理を説明するフローチャートである。
【０３２７】
【数１２０】

【０３２８】
を次のように定義する。
【０３２９】
【数１２１】

【０３３０】
復号器７０のバッファ７１は、
【０３３１】
【数１２２】

【０３３２】
で表されるＸの符号器のバッファ６２と、
【０３３３】
【数１２３】

【０３３４】
で表されるＹの符号器のバッファ６２と、で構成される。さらに復号器７０は、データベース
【０３３５】
【数１２４】

【０３３６】
を持っているとする。このデータベースは情報源Ｘに関するものである。
【０３３７】
ステップＲ１〜Ｒ７は、バッファ７１の初期化するために復号器７０で実施されるステップであり、初めてステップＲ８を実行する時点（ｉ＝０）では、符号器６０のバッファ６２と復号器７０のバッファ７１の内容が同一となる。ステップＲ８〜Ｒ１５は、本発明の方法による復号化のステップである。
【０３３８】
まず、ステップＲ１においてｉ←−Ｍ_kとし、ステップＲ２において、情報源Ｘ及び部分補助情報源Ｙの双方に関しバッファ７１に符号器６０のバッファ６２で用いたものと同じ集合の元を用いて初期値を格納する。そして、ステップＲ３において、ＸとＹについてのそれぞれのｉ番目のサブブロックについての符号語を各符号器６０から受信し、これを復号する。ステップＲ４では、ＸとＹについて正しく復号されたサブブロックを用いてバッファ７１を更新する。さらにステップＲ５においては、そのときのｉの値に関して情報源Ｘについてのデータベースに対応する項目がある場合に、そのデータベースも更新する。その後、ｉをインクリメントし（ステップＲ６）、ステップＲ７においてｉ＝０であるかどうかを判断し、ｉ＝０であればステップＲ８に移行するものとし、ｉ＜０であればステップＲ３に戻る。
【０３３９】
ステップＲ８において、復号化写像部７２は、ステップＲ５またはステップＲ１０〜Ｒ１２においてバッファ７１から計算されたデータベースを用いて、符号化対象ブロックの再生データ７５を計算する。すなわち、情報源Ｘと部分補助情報源Ｙのそれぞれの符号化対象ブロックの符号語６８を受信し、これに、それぞれに応じた復号化写像を適用して結果を求め、Ｘについての結果に応じてデータベースを検索し、これらから符号化対象ブロックの再生データ７５を決定する。
【０３４０】
ステップＲ９において、無歪み復号器７３は、Ｘの符号器においてステップＰ９で符号化された符号化写像生成ブロックの符号語６９を受信して、符号化写像生成ブロック６７を復号し、同様に、Ｙの符号器においてステップＱ９で符号化された符号化写像生成ブロックの符号語６９を受信して、符号化写像生成ブロック６７を復号する。これらは常に正しく復号される。
【０３４１】
ステップＲ１０においては、ステップＲ１１におけるバッファ７１の更新に先立って、その更新に関係する項目を情報源Ｘについてのデータベースから削除し、ステップＲ１１においては、ＸとＹについての正しく復号された符号化写像生成ブロックを用いて、バッファ７１内の最も古いデータを破棄してバッファ７１の更新を行い、ステップＲ１２では、バッファ７１での更新値に基づいて情報源Ｘについてのデータベースの更新を行う。その後、ステップＲ１３において、ブロック連結装置７４は、ステップＲ８で得られた符号化対象ブロックの再生データ７５とステップＲ９で得られた符号化写像生成ブロック６７を連結して再生データ７６を得る。続いて、ｉをインクリメントし（ステップＲ１４）、ステップＲ１５において、処理対象のブロックがなくなったかどうかを判断するためにｉ＝ｑ_k−Ｍ_kかどうかを判断し、ｉ＝ｑ_k−Ｍ_kならば処理を終了し、そうでなければステップＲ８へ戻る。
【０３４２】
下表に、アルゴリズムとして、以上説明した復号器での処理を詳細に示す。
【０３４３】
【表１０】

【０３４４】
【表１１】

【０３４５】
次に、上述した復号器に部分補助情報を伴う情報源符号化への応用の一例について説明する。
【０３４６】
全体の系列
【０３４７】
【数１２５】

【０３４８】
に対するＸの符号器の総符号長とＹの符号器の総符号長とをそれぞれ
【０３４９】
【数１２６】

【０３５０】
する。そして、復号誤り文字数を
【０３５１】
【数１２７】

【０３５２】
とする。このとき、次の性質が成り立つ。
【０３５３】
性質：Ｘ，Ｙを相関のある定常無記憶情報源として、同時分布ｐ_XYZは上述の条件１〜４を満たしているとする。このとき、
【０３５４】
【数１２８】

【０３５５】
一般に、最適なＲ_XとＲ_Yの選択にはトレードオフの関係があり、双方を自由に小さくすることはできない。最適な(Ｒ_X,Ｒ_Y)は、以下の関数の曲線上にある。
【０３５６】
【数１２９】

【０３５７】
ここでinfの中のｐ_XYZは、条件１〜４のうちの条件１〜３を満たしているものとする。
【０３５８】
このとき、次の性質が成り立つ。
【０３５９】
性質：Ｒ_X＞０，Ｒ_Y＞０に対して（Ｈ(X|Z),Ｉ(Y;Z)）が曲線Ｒ_X(Ｒ_Y)，Ｒ_Y(Ｒ_X)上にあるように分布ｐ_XYZを取れば、本実施形態のアルゴリズムは漸近的に最適な復号器に部分情報を伴う情報源符号化アルゴリズムとなる。
【０３６０】
なお、既知の分布μ_XYから上記曲線上にあるｐ_XYZを見つける方法として、参考文献[5]による近似解法がある。
【０３６１】
以上説明した本発明の手法による符号器と復号器とは、いずれも、それらを実現するためのコンピュータプログラムをマイクロプロセッサなどのコンピュータに読み込ませ、そのプログラムを実行させることによっても実現できる。本発明の手法によってデータの符号化や復号化を行うためのプログラムは、ＣＤ−ＲＯＭやフラッシュメモリなどの記録媒体によって、コンピュータに読み込まれる。
【０３６２】
このようなコンピュータは、一般に、ＣＰＵ（中央処理装置）と、プログラムやデータを格納するためのハードディスク装置あるいは不揮発性メモリなどの外部記憶装置と、主メモリと、キーボードやマウスや各種スイッチなどの入力装置と、ＣＲＴや各種表示ランプなどの表示装置と、ＣＤ−ＲＯＭやフラッシュメモリなどの記録媒体を読み取る読み取り装置と、入力データを受け付けるともに符号語などを復号器に送信するために使用される（符号器を構成する場合）、あるいは符号語などを符号器から受け付けるとともに再生データを出力するために使用される（復号器を構成する場合）インタフェースと、を備えている。外部記憶装置、主メモリ、入力装置、表示装置、読み取り装置及びインタフェースは、いずれもＣＰＵに接続している。このコンピュータでは、上述した符号化手順あるいは復号化手順を行うためのプログラムを格納した記録媒体を読み取り装置に装着し、記録媒体からプログラムを読み出して外部記憶装置に格納し、外部記憶装置に格納されたプログラムをＣＰＵが実行することにより、上述した符号器あるいは復号器として機能して上述の符号化手順あるいは復号化手順が実行される。
【０３６３】
【発明の効果】
以上述べたように本発明は、入力データを分割してそれぞれ別の符号化を行い、分割されたデータの一方を符号化写像の構成に利用することにより、従来のシステムでは実現できなかった、復号誤りを許す符号化にも適用でき、過去の系列の乱雑さを利用した符号化効率の良い符号化システムを実現できる、という効果がある。
【図面の簡単な説明】
【図１】ビッツバック符号器の構成を示すブロック図である。
【図２】ビッツバック復号器の構成を示すブロック図である。
【図３】多端子情報源符号化によるシステムの構成を示すブロック図である。
【図４】有歪み情報源符号化によるシステムの構成を示すブロック図である。
【図５】復号器に部分補助情報を伴う情報源符号化によるシステムの構成を示すブロック図である。
【図６】本発明に基づく符号化方法を実行する符号器の構成を示すブロック図である。
【図７】本発明に基づく復号化方法を実行する復号器の構成を示すブロック図である。
【図８】多端子情報源符号化に適用した場合の符号化手順を説明するフローチャートである。
【図９】多端子情報源符号化に適用した場合の復号化手順を説明するフローチャートである。
【図１０】有歪み情報源符号化に適用した場合の符号化手順を説明するフローチャートである。
【図１１】有歪み情報源符号化に適用した場合の復号化手順を説明するフローチャートである。
【図１２】復号器に部分補助情報を伴う情報源符号化に適用した場合の情報源の符号化手順を説明するフローチャートである。
【図１３】復号器に部分補助情報を伴う情報源符号化に適用した場合の部分補助情報源の符号化手順を説明するフローチャートである。
【図１４】復号器に部分補助情報を伴う情報源符号化に適用した場合の復号化手順を説明するフローチャートである。
【符号の説明】
１０、３０_X、３０_Z、４０、５０_X、５０_Y、６０ 符号器
１１、２１、６２、７１ バッファ
１２、２２ 符号語選択装置
１３ 算術復号器
１４ 多値情報源符号器
１５、６５ 入力データ
２０、３１、４１、５１、７０ 復号器
２３ 算術符号器
２４ 多値情報源復号器
２５、７６ 再生データ
６１ ブロック分割装置
６３ 符号化写像部
６４ 無歪み符号器
６６ 符号化対象ブロック
６７ 符号化写像生成ブロック
６８ 符号化対象ブロックの符号語
６９ 符号化写像生成ブロックの符号語
７２ 復号化写像部
７３ 無歪み復号器
７４ ブロック連結装置
７５ 符号化対象ブロックの再生データ[0001]
BACKGROUND OF THE INVENTION
The present invention relates to a data encoding / decoding method and apparatus used in communication that guarantees a given quality standard, and in particular, data that achieves the shortest possible code length by using the randomness of past sequences. The present invention relates to an encoding / decoding method and apparatus.
[0002]
[Prior art]
In data communication, various data encoding / decoding methods and apparatuses that perform information source encoding are used to compress the amount of data transferred over a communication network and reduce the bandwidth required for the transfer. Yes.
[0003]
One such information source coding is a technique called “bitsback coding with feedback”. Hereinafter, a conventional coding system using “bitsback coding with feedback” will be described. FIG. 1 shows an outline of a configuration of an encoder that performs Bitsback encoding with feedback, and FIG. 2 shows an outline of a configuration of a decoder used in a pair with the encoder.
[0004]
As shown in FIG. 1, the encoder 10 includes a buffer 11, a codeword selection device 12, an arithmetic decoder 13, and a multilevel information source encoder 14. Here, an appropriate initial value is stored in the buffer 11 in advance. In the encoding by this encoder, first, the code word selection device 12 performs a predetermined conditional probability distribution on the input data 15 v.
[0005]
[Expression 1]

[0006]
Is transmitted to the arithmetic decoder 13. Next, the arithmetic decoder 13 takes out the oldest data stored in the buffer 11, and based on this, the distribution {Q (h | v)} given from the codeword selector 12_{h ∈ H}And the converted data h is transmitted to the multi-level information source encoder 14. The extracted data is deleted from the buffer 11. Next, the multilevel information source encoder 14 gives a variable-length symbol string to the input (v, h) (input data 15 v and h output from the arithmetic decoder), and buffers it. 11. The multi-level information source encoder 14 receives a variable-length symbol string (which is expressed as b) for a pair of inputs (v, h).^*B), it is described by a bijective map that gives^*On the other hand, if there is a corresponding (v, h), it is uniquely determined. The above operation is performed on a predetermined number of input data, and when there is no input data, the data remaining in the buffer 11 is transmitted to the decoder 20 (see FIG. 2).
[0007]
As shown in FIG. 2, the decoder 20 includes a buffer 21, a codeword selection device 22, an arithmetic decoder 23, and a multilevel information source decoder 24. Here, as the initial state of the buffer 21, the state of the buffer 11 of the encoder 10 at the time when the operation of the partner encoder 10 is completed is given. The data freshness in the buffer 21 is determined by the time stored in the buffer 11. The multi-level information source decoder 24 executes the inverse mapping of the mapping in the multi-level information source encoder 14, and a variable length symbol string b.^*(V, h) that is uniquely determined is output.
[0008]
When performing decoding, first, the multilevel information source decoder 24 takes out the newest data in the buffer 21 and outputs (v, h) from this. Of the data output from the multilevel information source decoder 24, v is also output to the outside as reproduced data 25. The extracted data is deleted from the buffer 21. Among (v, h), h is transmitted to the arithmetic encoder 23. v is output as reproduction data 25 and is also transmitted to the codeword selection device 22. The code word selection device 22 performs a predetermined conditional probability distribution {Q (h | v)} for the input data v._{h ∈ H}Is transmitted to the arithmetic encoder 23. The arithmetic encoder 23 uses the distribution {Q (h | v)} given from the codeword selector 22 based on v sent from the multilevel information source decoder 24._{h ∈ H}Assuming that The converted data is stored in the buffer 21. The above operation is performed a predetermined number of times. In this way, the reproduction data 25 is obtained sequentially, but the reproduction data 25 is output as a time series in reverse order to the input data 15.
[0009]
The conventional encoding device and decoding device shown in FIGS. 1 and 2 are described in detail in Reference [1], pp. 104-128.
[0010]
In addition, as a reference regarding this technical field, for example,
[1] B. J. Frey, Graphical models for machine learning and digital communication, MIT Press, 1998.
[2] J. Rissanen and G. G. Langdon, "Arithmetic coding," IBM Journal of Research and Development, vol. 23, pp. 149-162, 1976.
[3] S. Arimoto, "An algorithm for calculating the capacity of an arbitrary discrete memoryless channel," IEEE Trans. Inform. Theory, vol. IT-18, pp. 14-20, Jan. 1972.
[4] R. E. Blahut, "Comptation of channel capacity and rate-distortion functions," IEEE Trans. Inform. Theory, vol. IT-18, pp. 460-473, Jul. 1972.
[5] N. Tishby, F. C. Pereira, and W. Bialek, "The information bottleneck method," Proc. Of the 37-th Annual Allerton Conference on Comunication, Control and Computing, pp. 368-377, 1999.
[0011]
[Problems to be solved by the invention]
In the conventional coding system described above, the multilevel information source encoder 14 in the encoder 10 and the multilevel information source decoder 24 in the decoder 20 are in a reverse mapping relationship with each other. Since the arithmetic decoder 13 and the arithmetic encoder 23 in the decoder 20 are in inverse mapping relation to each other, the state of the decoder buffer 21 is completely the same as the state of the encoder buffer 11 in the reverse order. Reproduce. Therefore, the conventional coding system described above is based on the premise that there is no distortion (data discrepancy) between the input data and the reproduction data, and the operation when the distortion is allowed between the input data and the reproduction data is guaranteed. It has not been.
[0012]
However, in order to realize a shorter codeword length, it may be necessary to allow distortion between input data and reproduced data. For example, in multi-terminal information source coding, distortion information source coding, and information source coding with partial auxiliary information in the decoder as described below, it is necessary to allow distortion between input data and reproduction data. There is.
[0013]
Multi-terminal source coding:
In multi-terminal information source coding, a plurality of input data located at different locations are encoded using different encoders, and the decoder reproduces a set of input data based on these codewords. FIG. 3 shows that the two input data X and Z are each given a rate R_X, R_ZRepresents an encoding device. That is, f_X, F_ZRespectively represented by encoders 30_X, 30_ZThe codewords from these are input to the decoder 31 represented by g, and an input data set (X, Z) is output. Here, X and Z are random variables representing input data or reproduction data. H (X | Z) and H (Z | X) are conditional entropies, and H (XZ) is entropy, both of which represent the lower limit of the encoding rate achieved by the algorithm. In this multi-terminal information source coding system, R_X≧ H (X | Z), R_Z≧ H (Z | X), R_X+ R_ZThe relationship of ≧ H (XZ) is established. In multi-terminal information source coding, it is desirable that the distortion between input data and reproduction data is as small as possible, and the coding rate of each encoder is as small as possible.
[0014]
Distorted source coding:
In the distortion information source encoding, encoding is performed so as to make the encoding rate as small as possible after allowing a predetermined distortion that can be measured by the distortion measure ρ between the input data Y and the reproduction data Z. . FIG. 4 shows that input data Y is rate R_YAnd the distortion between the reproduction data Z is E_YZThis represents a device that is equal to or less than ρ (Y, Z) (E represents an average). That is, f_YThe code word from now is input to the decoder 41 represented by g, and the reproduction data Z is obtained. Here, Y is a random variable representing input data, Z is a random variable representing reproduced data, I (Y; Z) is a mutual information amount, that is, an encoding rate achieved by the algorithm, and E_YZρ (Y, Z) is the average distortion achieved by the algorithm.
[0015]
Source coding with partial auxiliary information in the decoder:
In the information source encoding with partial auxiliary information in the decoder, the input data X is reproduced on the assumption that another information Y can be used in the decoder. FIG. 5 shows an apparatus for reproducing X by encoding auxiliary information Y at a rate I (Y; Z) and encoding input data X at a rate H (X | Z). Assuming that X and Y are random variables representing input data or output data, and Z is a random variable given in advance, f_X, F_YRespectively represented by encoders 50_X, 50_YThe encoder 50 is provided._XCodewords are output at conditional entropy H (X | Z), that is, at the code rate achieved by the algorithm._YCodewords are output at mutual information I (Y; Z), that is, at a coding rate achieved by the algorithm, and a decoder 51 represented by g outputs reproduction data based on these codewords. Here again, it is desirable to reduce the distortion between the input data and the reproduction data as much as possible and to make the encoding rate of each encoder as small as possible.
[0016]
The present invention has been made in view of the drawbacks of the above-described conventional system, and enables data encoding / encoding that can realize a smaller encoding rate by enabling encoding that allows distortion. An object is to provide a decoding method and apparatus.
[0017]
[Means for Solving the Problems]
  The data encoding method of the present invention is a method for encoding input data, and a step of dividing one block of input data divided into a plurality of blocks into an encoding map generation block and an encoding target block; , Encoder bufferEncoded map generation block stored inAnd obtaining a codeword of the encoding target block using the encoding mapping from the encoding target block, and obtaining a codeword of the encoding mapping generation block using the encoding mapping generation block by a distortion-free encoder, Discarding the oldest encoded map generation block remaining in the encoder buffer, accumulating the encoded map generation block in the encoder buffer, and repeatedly executing each of these steps until there are no more blocks; Have
[0018]
  The data decoding method of the present invention is a decoding method for acquiring reproduction data from, for example, a codeword of a block to be encoded generated as described above and a codeword of an encoded mapping generation block. The code word of the target block is extracted, and the code word of the target block and the decoder bufferEncoded map generation block stored inAnd a step of obtaining reproduction data of a block to be encoded by decoding mapping, a step of obtaining a code word of the encoding mapping generation block and obtaining an encoding mapping generation block by a distortion-free decoder, and a decoder buffer A step of discarding the remaining old encoded map generation block, newly storing the decoded encoded map generation block in the decoder buffer, and connecting the reproduction data of the encoding target block and the decoded encoded map generation block; A step of outputting, and a step of repeatedly executing each of these steps until all codewords are exhausted.
[0019]
A data encoding apparatus according to the present invention is a data encoding apparatus that encodes input data, and divides each block of the input data divided into a plurality of blocks into an encoded map generation block and an encoding target block. A block division device, an encoder buffer for temporarily storing an encoded map generation block, and an encoded map for obtaining a codeword of the target block using the encoded map from the content of the encoder buffer and the target block for encoding And an undistorted encoder that obtains a codeword of the encoded map generation block from the encoded map generation block, and the oldest encoded map generation in the encoder buffer each time a new encoded map generation block is input The block is discarded and the new encoded map generation block is stored in the encoder buffer.
[0020]
The data decoding apparatus of the present invention
A data decoding device for acquiring reproduction data from a codeword of a coding target block and a codeword of a coded map generation block, a decoder buffer for temporarily storing the codeword of the coded map generation block; A decoding mapping unit that extracts a code word of a block to be encoded and obtains reproduction data of the block to be encoded by decoding mapping based on the code word of the block to be encoded and the contents of the decoder buffer; A distortion-free decoder that extracts a code word of the generated block and obtains an encoded mapping generation block; and a block concatenation apparatus that connects the reproduced data of the encoding target block and the decoded encoded mapping generation block and outputs the result. Each time a new encoded map generation block is decoded, the oldest encoded map generation block is discarded in the decoder buffer and the new encoding is generated. Image generation block is accumulated in the decoder buffer.
[0021]
In order to achieve an optimal encoding rate, codes are randomly configured. In this case, synchronized random numbers are required between the encoder and the decoder. Therefore, in the present invention, in order to obtain a random number, a part of a sequence encoded in the past is stored in a buffer, and the code is randomly constructed therefrom. Furthermore, in order to synchronize the random numbers, when the observation data is encoded, it is divided into two, “encoding target block” and “encoded mapping generation block”, and separate encoding is performed.
[0022]
The difference between the encoding / decoding method according to the present invention and the conventional method is as follows.
[0023]
In the conventional method, all of the codewords are stored in the buffer. However, in the present invention, the input data is divided into data to be efficiently encoded and data to be stored in the buffer, and encoded separately. Encoding that allows distortion with a smaller encoding rate is realized.
[0024]
Also, in the conventional method, the content of the buffer is encoded without distortion using a fixed encoding map / decoding map (in the conventional method, a multi-level information source encoder / multi-level information source decoder is applicable). However, in the present invention, the encoding mapping / decoding mapping is dynamically changed using the contents of the buffer, thereby realizing encoding that allows distortion with a smaller encoding rate.
[0025]
DETAILED DESCRIPTION OF THE INVENTION
Next, a preferred embodiment of the present invention will be described with reference to the drawings. FIG. 6 is a block diagram showing a configuration of an encoding device (encoder) in the encoding / decoding device according to the embodiment of the present invention, and FIG. 7 is used in combination with the encoding device of FIG. It is a block diagram which shows the structure of the decoding apparatus (decoder). In the following description, in order to make the explanation easy to understand, a single information source output is described. However, in practice, the operations described below are performed for a plurality of information source outputs.
[0026]
The encoder 60 shown in FIG. 6 receives input data 65, divides the input data 65 into blocks, and divides each block into an encoding target block 66 and an encoded map generation block 67, and an encoding A buffer 62 (that is, an encoder buffer) for temporarily storing the mapping generation block 67, and a coding map for calculating and outputting a code word 68 of the coding target block based on the contents of the buffer 62 and the coding target block 66 And a non-distortion encoder 64 that calculates and outputs a code word 69 of the encoded map generation block from the encoded map generation block 67. Here, the encoding mapping unit 63 executes encoding mapping as will be described later, and the distortion-free encoder 64 is represented by a bijection mapping. The buffer 62 stores appropriate initial values.
[0027]
Next, the operation of the encoder 60 will be described. First, the block dividing device 61 divides the input data 65 into blocks, and divides each block into an encoding target block 66 and an encoded mapping generation block 67. Next, the encoding mapping unit 63 reads the contents of the buffer 62, encodes the encoding target block 66 using the encoding mapping according to the information source, and outputs the code word 68 of the encoding target block. Is transmitted to the decoder 70 shown in FIG. The distortionless encoder 64 encodes the encoded map generation block 67 and outputs an encoded map generation block codeword 69, which is transmitted to the decoder 70. Finally, the buffer 62 discards the oldest recorded data and records the encoded map generation block 67 sent from the block dividing device 61. These processes are repeatedly executed until there is no block to be processed in the input data.
[0028]
When actually configuring an encoding / decoding system, a necessary number of encoders 60 as described above are prepared.
[0029]
Next, the decoder 70 will be described. The decoder 70 shown in FIG. 7 can receive the code word 68 of the encoding target block and the code word 69 of the encoded mapping generation block from each of the plurality of encoders 60. Of course, the code word 68 of the encoding target block and the code word 69 of the encoded mapping generation block may be input to the decoder 70 only from the single encoder 60. Then, the decoder 70 obtains reproduction data 75 of the encoding target block by decoding mapping based on the buffer (that is, decoder buffer) 71, the code word 68 of the encoding target block, and the contents of the buffer 71. The unit 72, the distortion-free decoder 73 for reproducing the code word 69 of the encoded map generation block to obtain the encoded map generation block 67, the reproduction data 75 of the encoding target block and the encoded map generation block 67 are connected. And a block connecting device 74 for obtaining reproduction data 76. Here, the distortion-free decoder 73 is a collection of inverse mappings of mappings represented by the distortion-free encoder 64 of each encoder 60 shown in FIG. The buffer 71 is configured as an aggregate of buffers 62 corresponding to the encoders 60. The same initial values as the buffers 62 of the encoders are stored. After the initial values are stored, the distortion-free decoding is performed. The encoded map generation block 67 input from the device 73 is stored. Actually, as will be described later, the initial value stored in the buffer 62 of the encoder 60 and the initial value stored in the buffer 71 of the decoder 70 are matched between the encoder 60 and the decoder 70. Initialization processing is performed.
[0030]
  Next, the operation of the decoder 70 will be described. The decoding mapping unit 72 reads the contents of the buffer 71, receives the codeword 68 of the block to be encoded from each encoder 60 as shown in FIG. 6, and uses these to decode the block to be encoded by decoding mapping. Playback data 75 is output. On the other hand, the distortionless decoder 73 receives the encoded map generation block codeword 69 from each encoder 60, and reproduces the encoded map generation block 67 of each encoder 60 from these. Subsequently, the block concatenation device 74 concatenates the reproduction data 75 of the encoding target block and the encoded map generation block 67 sent from the distortion-free decoder, to obtain reproduction data 76. Finally, the buffer 71 discards the oldest recorded data, and the code sent from the undistorted decoder 73Conversion mapA generation block 67 is recorded.
[0031]
In the following, the encoding / decoding method and apparatus of the present invention will be described in the case of applying each of multi-terminal information source encoding, distortion information source encoding, and information source encoding with partial auxiliary information to the decoder. This will be described in more detail. First, the symbols appearing in the following explanation will be explained.
[0032]
set
[0033]
[Expression 2]

[0034]
The complementary set and the number of elements
[0035]
[Equation 3]

[0036]
Write, set
[0037]
[Expression 4]

[0038]
The difference set of
[0039]
[Equation 5]

[0040]
Write. set
[0041]
[Formula 6]

[0042]
Is a finite set,
[0043]
[Expression 7]

[0044]
And
[0045]
[Equation 8]

[0046]
The i th element of x_iOr [xⁿ]_i. Xⁿ≡x₁* ... * x_nFor x_i ^j≡x_i* ... * x_jAnd The operation that gives the concatenation of character strings is *. For example, xⁿ= (X₁, ..., x_n), Y^m= (Y₁, ..., y_m) For xⁿ* Y^m≡ (x₁, ..., x_n, y₁, ..., y_m). Encoder
[0047]
[Equation 9]

[0048]
, Decoder
[0049]
[Expression 10]

[0050]
, D (xⁿ) Is defined as follows.
[0051]
## EQU11 ##

[0052]
This is the series xⁿAnd regenerated series φ_n ^-1(φ_n(xⁿ)) Represents the number of different characters.
[0053]
[Expression 12]

[0054]
The
[0055]
[Formula 13]

[0056]
The binary representation in digits and its inverse map, respectively,
[0057]
[Expression 14]

[0058]
Is described. Similarly,
[0059]
[Expression 15]

[0060]
The
[0061]
[Expression 16]

[0062]
The binary representation in digits and its inverse map, respectively,
[0063]
[Expression 17]

[0064]
Is described.
[0065]
[Formula 18]

[0066]
Given a random variable X of values, the corresponding probability distribution_XWrite. Also
[0067]
[Equation 19]

[0068]
Write. X entropy H (X)
[0069]
[Expression 20]

[0070]
It is defined as The combined entropy of X and Y is H (XY), and the conditional entropy of X when Y is given is H (X | Y) ≡H (XY) -H (Y), and the mutual information of X and Y is Let I (X; Y) ≡H (X) + H (Y) −H (XY).
[0071]
[Expression 21]

[0072]
The divergence D (ν‖μ) of the above probability distribution ν and μ is defined as follows.
[0073]
[Expression 22]

[0074]
[Expression 23]

[0075]
Distribution from experience
[0076]
[Expression 24]

[0077]
Is defined as follows.
[0078]
[Expression 25]

[0079]
this is,
[0080]
[Equation 26]

[0081]
Is the series xⁿIt means to express the appearance frequency of a.
[0082]
[Expression 27]

[0083]
Conditional experience distribution obtained from
[0084]
[Expression 28]

[0085]
Any
[0086]
[Expression 29]

[0087]
Against
[0088]
[30]

[0089]
Defined as a conditional probability distribution that satisfies This is y_i= I such that = b and x_i= Represents the frequency of i for which a holds.
[0090]
For a real number 0 <α <∞, γ> 0 and a natural number k, ζ (α, γ) and λ (α, k) are defined as follows. These are used to simplify the formula description.
[0091]
[31]

[0092]
Let i% n, 0 ≦ i% n ≦ n−1 be the remainder of dividing i by n. Note that i may be expressed in binary.
<Application to multi-terminal source coding>
Here, an example in which the encoding / decoding method according to the present embodiment is applied to multi-terminal information source encoding will be described. A plurality of correlated information sources X and Z, each with a rate R_X, R_ZAre independently encoded and sent to the decoder, and the decoder decodes X and Z. As a system configuration, the system as shown in FIG._X, 30_Z6 to encode the information sources X and Y using the encoder 60 shown in FIG. 6, and to decode the X and Y using the decoder 70 shown in FIG. To do.
[0093]
Below,
[0094]
[Expression 32]

[0095]
And the following definitions are used:
[0096]
[Expression 33]

[0097]
[Expression 34]

[0098]
Is defined as follows.
[0099]
[Expression 35]

[0100]
And
[0101]
[Expression 36]

[0102]
When given an appropriate order
[0103]
[Expression 37]

[0104]
Number
[0105]
[Formula 38]

[0106]
.
[0107]
[39]

[0108]
As a method for easily calculating, an algorithm of an arithmetic code (see reference [2]) and the like can be mentioned. Actually, the arrangement order does not affect the performance analysis, and can be arbitrarily set. function
[0109]
[Formula 40]

[0110]
Is defined as follows.
[0111]
[Expression 41]

[0112]
π_kIs
[0113]
[Expression 42]

[0114]
The origin of
[0115]
[Equation 43]

[0116]
Assign numbers in bundles,
[0117]
(44)

[0118]
It is a mapping that assigns different numbers to them. Roughly speaking,
[0119]
[Equation 45]

[0120]
It is equally divided. As well
[0121]
[Equation 46]

[0122]
Define
[0123]
[Equation 47]

[0124]
Using π_kDefine 'as well.
[0125]
q_k≡M_k+ K²2^kAnd Overall series length
[0126]
[Formula 48]

[0127]
Against
[0128]
[Formula 49]

[0129]
Are divided into sub-blocks of length k + 2 that do not overlap each other. Sub-block
[0130]
[Equation 50]

[0131]
Is defined as follows.
[0132]
[Formula 51]

[0133]
[Formula 52]

[0134]
Is defined in the same way.
[0135]
[53]

[0136]
Elements of
[0137]
[Formula 54]

[0138]
N is a mapping expressed in binary digits._XAnd its inverse map is N_X ^-1And Similarly,
[0139]
[Expression 55]

[0140]
Elements of
[0141]
[56]

[0142]
N is a mapping expressed in binary digits._ZAnd its inverse map is N_Z ^-1And
[0143]
Here, an encoder for encoding the information source X (the encoder 30 in FIG. 3)._X) Will be described. As described above, the encoder 60 according to the present invention shown in FIG. 6 is used for this encoder. FIG. 8 is a flowchart for explaining the encoding process. As will be described later, since the operation of the encoder that encodes the information source Z is almost the same as the operation of the encoder that encodes the information source X, FIG. 8 shows the operation of both encoders. In this figure, steps A1 to A12 represent the operation of the encoder that encodes the information source X, and steps B1 to B12 represent the operation of the encoder that encodes the information source Z.
[0144]
The encoder 60
[0145]
[Equation 57]

[0146]
It is assumed that a buffer 62 represented by Steps A1 to A6 are steps performed by the encoder 60 to initialize the buffer 62 of the encoder 60 and the buffer 71 of the decoder 70. At the time when the step A8 is executed for the first time (i = 0), The contents of the encoder buffer 62 and the decoder buffer 71 are the same. Steps A7 to A12 are encoding steps according to the method of the present invention.
[0147]
First, in step A1, i ← −M_kIn step A2, appropriate initial values are stored in all the buffers 62 using a set corresponding to the information source X. In step A3, the code word for the i-th sub-block is sent to the decoder 70, and in step A4, the buffer 62 is updated using the i-th sub-block (the portion corresponding to the encoded mapping generation block). To do. Thereafter, i is incremented (step A5). In step A6, it is determined whether i = 0. If i = 0, the process proceeds to step A7. If i <0, the process returns to step A3.
[0148]
In step A7, the block dividing device 61 divides the block of the input data 65 into an encoded map generation block 67 and an encoding target block 66, and in step A8, the encoding map unit 63 performs encoding corresponding to the information source X. By using the mapping, based on the contents of the buffer 62 and the encoding target block 66, the code word 68 of the encoding target block is calculated and transmitted to the decoder 70. On the other hand, the distortion-free encoder 64 is represented by a bijection map corresponding to the information source X. Send. Thereafter, in step A10, the oldest data in the buffer 62 is discarded using the encoded map generation block of the i-th sub-block, and the buffer 62 is updated. Thereafter, i is incremented (step A11). In step A12, i = q to determine whether or not there is no block to be processed (input data 65)._k-M_kI = q_k-M_kIf so, the process ends. If not, the process returns to step A7.
[0149]
The following table shows in detail the processing in the encoder that encodes X described above as an algorithm.
[0150]
[Table 1]

[0151]
Next, an encoder for encoding the information source Z (the encoder 30 in FIG. 3)._Z) Will be described. As described above, the encoder 60 according to the present invention shown in FIG. 6 is used for this encoder. In practice, the processing at the encoder used for encoding Z and the processing at the encoder used for the X encoder are almost the same except for the difference of whether the information source is X or Z. is there.
[0152]
The encoder 60
[0153]
[Formula 58]

[0154]
Suppose you have Steps B1 to B6 in FIG. 8 are steps performed by the encoder 60 in order to initialize the buffer 62 of the encoder 60 and the buffer 71 of the decoder 70. When the step B8 is executed for the first time (i = 0). ), The contents of the encoder buffer 62 and the decoder buffer 71 are the same. Steps B7 to B12 are encoding steps according to the method of the present invention.
[0155]
The following table shows in detail the processing in the encoder that encodes Z described above as an algorithm. Here, the essential difference from the algorithm in the X encoder is that [x (i)]₁Instead of using [z (i)]₂It is a point using. this is,
[0156]
[Formula 59]

[0157]
This is in order to maintain the independence.
[0158]
[Table 2]

[0159]
Next, processing in a decoder (decoder 31 in FIG. 3) that inputs X codewords and Z codewords, decodes them, and outputs them will be described. As described above, the decoder 70 according to the present invention shown in FIG. 7 is used for this decoder. FIG. 9 is a flowchart for explaining the decoding process.
[0160]
At first,
[0161]
[Expression 60]

[0162]
Is defined as follows.
[0163]
[Equation 61]

[0164]
The decoder buffer 71 is
[0165]
[62]

[0166]
An X encoder buffer 62 represented by:
[0167]
[Equation 63]

[0168]
And a buffer 62 of the Z encoder represented by Furthermore, the decoder 70 has a database
[0169]
[Expression 64]

[0170]
Suppose you have
[0171]
Steps C1 to C7 are steps performed by the decoder 70 to initialize the buffer 71. At the time when the step C8 is executed for the first time (i = 0), the buffer 62 of the encoder 60 and the decoder 70 The contents of the buffer 71 are the same. Steps C8 to C15 are decoding steps according to the method of the present invention.
[0172]
First, in step C1, i ← −M_kIn step C2, the initial values are stored in the buffer 71 for each of the information sources X and Z using the same set elements as used in the buffer 62 of the encoder 60. In step C3, the codeword for each i-th sub-block for X and Z is received from each encoder 60 and decoded. In step C4, the buffer 71 is updated using the sub-blocks correctly decoded for X and Z (part corresponding to the encoded map generation block). Furthermore, in step C5, when there is an item corresponding to the database regarding the value of i at that time for each information source, the database is also updated. Thereafter, i is incremented (step C6). In step C7, it is determined whether i = 0. If i = 0, the process proceeds to step C8. If i <0, the process returns to step C3.
[0173]
In step C8, the decoding mapping unit 72 calculates reproduction data 75 of the encoding target block using the database calculated from the buffer 71 in step C5 or steps C10 to C12. That is, the code word 68 of the block to be encoded is received for each information source, and a decoding map corresponding to the information source is applied to the code word 68 to obtain a result. The reproduction data 75 of the conversion target block is determined.
[0174]
In step C9, the distortion-free decoder 73 receives the codeword 69 of the encoded map generation block encoded in step A9 in the X encoder, decodes the encoded map generation block 67, and similarly, The code word 69 of the encoded map generation block encoded in step B9 is received by the encoder of Z, and the encoded map generation block 67 is decoded. These are always decoded correctly.
[0175]
In step C10, prior to updating the buffer 71 in step C11, items related to the update are deleted from the database, and in step C11, a correctly decoded encoded mapping generation block for X and Z is used. The oldest data in the buffer 71 is discarded and the buffer 71 is updated. In step C12, the database is updated based on the updated value in the buffer 71. Thereafter, in step C13, the block concatenation device 74 concatenates the reproduction data 75 of the encoding target block obtained in step C8 and the encoded map generation block 67 obtained in step C9 to obtain reproduction data 76. Subsequently, i is incremented (step C14). In step C15, i = q to determine whether or not there is no block to be processed._k-M_kI = q_k-M_kIf so, the process ends. If not, the process returns to Step C8.
[0176]
The following table shows the processing in the decoder described above in detail as an algorithm.
[0177]
[Table 3]

[0178]
[Table 4]

[0179]
Next, an example of application to the above-described multi-terminal information source encoding will be described.
[0180]
Whole series
[0181]
[Equation 65]

[0182]
The total code length of the encoder for
[0183]
[Equation 66]

[0184]
And And the number of decoding error characters
[0185]
[Expression 67]

[0186]
And
[0187]
As a result, X and Z are set as correlated steady memoryless information sources satisfying the above conditions (1) to (3). At this time, the following properties hold.
[0188]
[Equation 68]

[0189]
<Application to distortion source coding>
Next, an example in which the encoding / decoding method according to the present embodiment is applied to distortion information source encoding will be described. Here, information source Y is rate R_YThe distortion that occurs after encoding and decoding is allowed. As the system configuration, the system shown in FIG. 4 is used, the encoder 60 shown in FIG. 6 is used as the encoder 40, and the decoder 70 shown in FIG. 7 is used as the decoder 41. Shall.
[0190]
Here, the distortion function
[0191]
[Equation 69]

[0192]
As
[0193]
[Equation 70]

[0194]
Assuming And
[0195]
[Equation 71]

[0196]
And
[0197]
[Equation 72]

[0198]
Connection distribution satisfying
[0199]
[Equation 73]

[0200]
I take the. And Z is the marginal distribution
[0201]
[Equation 74]

[0202]
, It is assumed that I (y; z)> 0 is satisfied.
[0203]
Below,
[0204]
[75]

[0205]
And
[0206]
[76]

[0207]
Is defined as follows.
[0208]
[77]

[0209]
[Formula 78]

[0210]
Function to give the order of lexicographic order
[0211]
[79]

[0212]
And
[0213]
And function
[0214]
[80]

[0215]
Is defined as follows.
[0216]
[Formula 81]

[0217]
σ_kIs
[0218]
[Formula 82]

[0219]
The origin of
[0220]
[Formula 83]

[0221]
Numbers assigned in bundles
[0222]
[Expression 84]

[0223]
By
[0224]
[Expression 85]

[0225]
Moved to
[0226]
[86]

[0227]
Pre-determined
[0228]
[Expression 87]

[0229]
Is a mapping that assigns here,
[0230]
[Equation 88]

[0231]
Does not affect subsequent analysis.
[0232]
q_k≡M_k+ K²2^kAnd Overall series length
[0233]
[Expression 89]

[0234]
Against
[0235]
[90]

[0236]
Is divided into non-overlapping sub-blocks of length k + 1 and sub-blocks
[0237]
[91]

[0238]
Is defined as follows.
[0239]
[Equation 92]

[0240]
[Equation 93]

[0241]
Elements of
[0242]
[Equation 94]

[0243]
N is a mapping expressed in binary digits._YAnd its inverse map is N_Y ^-1And
[0244]
Here, the processing in the encoder (encoder 40 in FIG. 4) will be described. As described above, the encoder 60 according to the present invention shown in FIG. 6 is used for this encoder. FIG. 10 is a flowchart for explaining the encoding process.
[0245]
The encoder 60
[0246]
[95]

[0247]
It is assumed that a buffer 62 represented by Steps F1 to F6 are steps performed by the encoder 60 to initialize the buffer 62 of the encoder 60 and the buffer 71 of the decoder 70. At the time when the step F8 is executed for the first time (i = 0), The contents of the encoder buffer 62 and the decoder buffer 71 are the same. Steps F7 to F12 are encoding steps according to the method of the present invention.
[0248]
First, in step F1, i ← −M_kIn step F2, appropriate initial values are stored in all the buffers 62 using the set corresponding to the information source Y. In step F3, the code word for the i-th sub-block is sent to the decoder 70, and in step F4, the buffer 62 is updated using the i-th sub-block (the portion corresponding to the encoded mapping generation block). To do. Thereafter, i is incremented (step F5). In step F6, it is determined whether i = 0. If i = 0, the process proceeds to step F7. If i <0, the process returns to step F3.
[0249]
In step F7, the block dividing device 61 divides the block of the input data 65 into an encoded map generation block 67 and an encoding target block 66, and in step F8, the encoding map unit 63 encodes corresponding to the information source Y. By using the mapping, based on the contents of the buffer 62 and the encoding target block 66, the code word 68 of the encoding target block is calculated and transmitted to the decoder 70. On the other hand, since the distortion-free encoder 64 is represented by a bijective map corresponding to the information source Y, the distortion-free encoder 64 calculates the code word 69 of the encoded map generation block in step F9 and decodes the decoder 70. Send to. Thereafter, in step F10, the oldest data in the buffer 62 is discarded and the buffer 62 is updated using the encoded map generation block of the i-th sub-block. Thereafter, i is incremented (step F11). In step F12, i = q to determine whether or not there is no block to be processed (input data 65)._k-M_kI = q_k-M_kIf so, the process ends. If not, the process returns to Step F7.
[0250]
The table below shows the processing in the encoder described above in detail as an algorithm.
[0251]
[Table 5]

[0252]
Next, processing in the decoder (decoder 31 in FIG. 3) will be described. As described above, the decoder 70 according to the present invention shown in FIG. 7 is used for this decoder. FIG. 11 is a flowchart for explaining the decoding process.
[0253]
The decoder buffer 71 is
[0254]
[Equation 96]

[0255]
It is comprised by the buffer 62 of the encoder represented by these.
[0256]
Steps G1 to G6 are steps performed by the decoder 70 to initialize the buffer 71. At the time when the step G8 is executed for the first time (i = 0), the buffer 62 of the encoder 60 and the decoder 70 The contents of the buffer 71 are the same. Steps G7 to G12 are decoding steps according to the method of the present invention.
[0257]
First, in step G1, i ← −M_kIn step G2, the initial value is stored in the buffer 71 using the same set of elements as used in the buffer 62 of the encoder 60. In step G3, the code word for the i-th sub-block is received from each encoder 60 and decoded. In step G4, the buffer 71 is updated using the correctly decoded sub-block (the part corresponding to the encoded map generation block). Thereafter, i is incremented (step G5). In step G6, it is determined whether i = 0. If i = 0, the process proceeds to step G7. If i <0, the process returns to step G3.
[0258]
In step G7, the decoding mapping unit 72 receives the code word 68 of the block to be encoded encoded in step F8 of the encoder 60, and based on the code word and the contents of the buffer 71, the information source Y The reproduction data 75 of the block to be encoded is calculated using the decoded map. In step G8, the distortion-free decoder 73 receives the code map 69 of the encoded map generation block encoded in step F9 by the encoder 60, and decodes the encoded map generation block 67. This is always correctly decoded. In step G9, the oldest data in the buffer 71 is discarded using the encoded map generation block that has been correctly decoded, and the buffer 71 is updated. Thereafter, in step G10, the block concatenation device 74 concatenates the reproduction data 75 of the encoding target block obtained in step G7 and the encoded map generation block 67 obtained in step G8 to obtain reproduction data 76. Subsequently, i is incremented (step G11). In step G12, i = q to determine whether or not there is no block to be processed._k-M_kI = q_k-M_kIf so, the process ends. If not, the process returns to step G7.
[0259]
The following table shows the processing in the decoder described above in detail as an algorithm.
[0260]
[Table 6]

[0261]
Next, an example of application to the above-described distortion information source coding will be described.
[0262]
Whole series
[0263]
[Equation 97]

[0264]
The total code length of the encoder for
[0265]
[Equation 98]

[0266]
And And the distortion that occurred during decoding
[0267]
[99]

[0268]
And At this time, the following properties hold.
[0269]
Property: Arbitrary distribution p satisfying I (Y; Z)> 0_YZIf you take
[0270]
[Expression 100]

[0271]
By the way, there is a trade-off relationship between rate and distortion, and the optimum combination is on the following curve called a rate distortion curve.
[0272]
## EQU1 ##

[0273]
Distribution p_YZUsing the Arimoto-Blahut algorithm (references [3], [4]), (I (Y; Z), E_YZIf ρ (Y, Z)) is on the rate distortion curve (distortion rate curve), the following properties are established.
[0274]
Properties: (I (Y; Z), E_YZThe distribution p so that ρ (Y, Z)) is on the rate distortion curve (distortion rate curve)._YZIf this is taken, the algorithm according to the present embodiment is asymptotically the optimal distorted code.
[0275]
<< Application to source coding with partial auxiliary information in decoder >>
Next, an example in which the encoding / decoding method according to the present embodiment is applied to information source encoding with partial auxiliary information in a decoder will be described. Here, rate R with information source Y as partial auxiliary information_YThe information source X correlated with Y is sent to the decoder at the rate R_XAnd sent to the decoder for playback. As the system configuration, the system as shown in FIG._X, 50_Y6, each of the information sources X and Y is encoded using the encoder 60 shown in FIG. 6, and X is decoded using the decoder 70 shown in FIG. 7 as the decoder 51. Like that.
[0276]
Here, the joint probability distribution satisfying the following conditions 1 to 4
[0277]
## EQU10 ##

[0278]
Prepare.
[0279]
[Table 7]

[0280]
[Formula 103]

[0281]
Is defined as follows.
[0282]
[Formula 104]

[0283]
Overall series length
[0284]
[Formula 105]

[0285]
Against
[0286]
[Formula 106]

[0287]
Are divided into sub-blocks of length k + 2 that do not overlap each other. Sub-block
[0288]
[Expression 107]

[0289]
Is defined as follows.
[0290]
[Formula 108]

[0291]
[Formula 109]

[0292]
Is defined in the same manner as described above.
[0293]
## EQU1 ##

[0294]
Elements of
[0295]
[Formula 111]

[0296]
N is a mapping expressed in binary digits._XAnd its inverse map is N_X ^-1And
[0297]
## EQU1 ##

[0298]
Elements of
[0299]
[Formula 113]

[0300]
N is a mapping expressed in binary digits._YAnd its inverse map is N_Y ^-1And
[0301]
Here, an encoder for encoding the information source X (the encoder 50 in FIG. 5)._X) Will be described. As described above, the encoder 60 according to the present invention shown in FIG. 6 is used for this encoder. FIG. 12 is a flowchart for explaining the encoding process.
[0302]
As above,
[0303]
[Formula 114]

[0304]
Define The X encoder is almost the same as the Slepian-Wolf encoder.
[0305]
The encoder is
[0306]
[Expression 115]

[0307]
It is assumed that a buffer 62 represented by Steps P1 to P6 are steps performed by the encoder 60 to initialize the buffer 62 of the encoder 60 and the buffer 71 of the decoder 70. At the time when the step P8 is executed for the first time (i = 0), The contents of the encoder buffer 62 and the decoder buffer 71 are the same. Steps P7 to P12 are encoding steps according to the method of the present invention.
[0308]
First, in step P1, i ← −M_kIn step P2, appropriate initial values are stored in all the buffers 62 using the set corresponding to the information source X. In step P3, the code word for the i-th sub-block is sent to the decoder 70. In step P4, the buffer 62 is updated using the i-th sub-block (the portion corresponding to the encoded mapping generation block). To do. Thereafter, i is incremented (step P5). In step P6, it is determined whether i = 0. If i = 0, the process proceeds to step P7. If i <0, the process returns to step P3.
[0309]
In step P7, the block dividing device 61 divides the block of the input data 65 into the encoded map generation block 67 and the encoding target block 66. By using the mapping, based on the contents of the buffer 62 and the encoding target block 66, the code word 68 of the encoding target block is calculated and transmitted to the decoder 70. On the other hand, the undistorted encoder 64 represented by the bijective map corresponding to the information source X calculates the codeword 69 of the encoded map generation block and transmits it to the decoder 70 in step P9. Thereafter, in step P10, the oldest data in the buffer 62 is discarded using the encoded map generation block of the i-th sub-block, and the buffer 62 is updated. Thereafter, i is incremented (step P11). In step P12, i = q to determine whether or not the block to be processed (input data 65) is gone._k-M_kI = q_k-M_kIf so, the process ends. If not, the process returns to Step P7.
[0310]
The following table shows in detail the processing in the encoder that encodes the information source X described above as an algorithm.
[0311]
[Table 8]

[0312]
Next, an encoder for encoding the partial auxiliary information source Y (the encoder 50 in FIG. 5)._Y) Will be described. As described above, the encoder 60 according to the present invention shown in FIG. 6 is used for this encoder. Actually, the processing in this encoder is almost the same as the processing in the encoder in the distortion information source encoding described above. FIG. 13 is a flowchart for explaining the decoding process.
[0313]
As with distortion source coding,
[0314]
[Formula 116]

[0315]
Define
[0316]
[Expression 117]

[0317]
Is defined as follows.
[0318]
[Formula 118]

[0319]
The encoder 60
[0320]
[Formula 119]

[0321]
It is assumed that a buffer 62 represented by Steps Q1 to Q6 are steps performed by the encoder 60 to initialize the buffer 62 of the encoder 60. When the step Q8 is executed for the first time (i = 0), the decoding is performed with the buffer 62 of the encoder. The contents of the buffer 71 of the container are the same. Steps Q7 to Q12 are encoding steps according to the method of the present invention.
[0322]
First, in step Q1, i ← −M_kIn step Q2, appropriate initial values are stored in all the buffers 62 using the set corresponding to the partial auxiliary information source Y. In step Q3, the code word for the i-th sub-block is sent to the decoder 70, and in step Q4, the buffer 62 is updated using the i-th sub-block. Thereafter, i is incremented (step Q5). In step Q6, it is determined whether i = 0. If i = 0, the process proceeds to step Q7. If i <0, the process returns to step Q3.
[0323]
In step Q7, the block dividing device 61 divides the block of the input data 65 into the encoded map generation block 67 and the encoding target block 66, and in step Q8, the encoded mapping unit 63 responds to the partial auxiliary information source Y. By using the encoding map, the code word 68 of the encoding target block is calculated based on the contents of the buffer 62 and the encoding target block 66 and transmitted to the decoder 70. On the other hand, in step Q 9, the distortion-free encoder 64 represented by a bijective map corresponding to the partial auxiliary information source Y calculates the code word 69 of the encoded map generation block and transmits it to the decoder 70. Thereafter, in step Q10, the oldest data in the buffer 62 is discarded using the i-th sub-block, and the buffer 62 is updated. Thereafter, i is incremented (step Q11). In step Q12, i = q to determine whether or not there is no block to be processed (input data 65)._k-M_kI = q_k-M_kIf so, the process ends. If not, the process returns to step Q7.
[0324]
The following table shows in detail the processing in the encoder that encodes the partial auxiliary information source Y described above as an algorithm.
[0325]
[Table 9]

[0326]
Next, processing in the decoder (decoder 31 in FIG. 3) will be described. As described above, the decoder 70 according to the present invention shown in FIG. 7 is used for this decoder. FIG. 14 is a flowchart for explaining the decoding process.
[0327]
[Expression 120]

[0328]
Is defined as follows.
[0329]
[Equation 121]

[0330]
The buffer 71 of the decoder 70 is
[0331]
[Equation 122]

[0332]
An X encoder buffer 62 represented by:
[0333]
[Formula 123]

[0334]
Y encoder buffer 62 represented by Furthermore, the decoder 70 has a database
[0335]
[Expression 124]

[0336]
Suppose you have This database relates to the information source X.
[0337]
Steps R1 to R7 are steps performed by the decoder 70 to initialize the buffer 71. At the time when the step R8 is executed for the first time (i = 0), the buffer 62 of the encoder 60 and the decoder 70 The contents of the buffer 71 are the same. Steps R8 to R15 are decoding steps according to the method of the present invention.
[0338]
First, in step R1, i ← −M_kIn step R2, initial values are stored in the buffer 71 for both the information source X and the partial auxiliary information source Y using the same set of elements as used in the buffer 62 of the encoder 60. In step R3, the codeword for each i-th sub-block for X and Y is received from each encoder 60 and decoded. In step R4, the buffer 71 is updated using sub-blocks correctly decoded for X and Y. Further, in step R5, if there is an item corresponding to the database for the information source X regarding the value of i at that time, the database is also updated. Thereafter, i is incremented (step R6). In step R7, it is determined whether i = 0. If i = 0, the process proceeds to step R8. If i <0, the process returns to step R3.
[0339]
In step R8, the decoding mapping unit 72 calculates reproduction data 75 of the encoding target block using the database calculated from the buffer 71 in step R5 or steps R10 to R12. That is, the codeword 68 of each encoding target block of the information source X and the partial auxiliary information source Y is received, and a decoding map corresponding to the codeword 68 is applied thereto to obtain a result. Then, the database is searched, and the reproduction data 75 of the encoding target block is determined from these.
[0340]
In step R9, the distortion-free decoder 73 receives the codeword 69 of the encoded map generation block encoded in step P9 in the X encoder, decodes the encoded map generation block 67, and similarly, The encoded map generation block 67 is decoded by receiving the code word 69 of the encoded map generation block encoded in step Q9 in the Y encoder. These are always decoded correctly.
[0341]
In step R10, prior to updating the buffer 71 in step R11, items related to the update are deleted from the database for the information source X, and in step R11, the correctly decoded encoded maps for X and Y are deleted. Using the generated block, the oldest data in the buffer 71 is discarded and the buffer 71 is updated. In step R12, the database for the information source X is updated based on the updated value in the buffer 71. Thereafter, in step R13, the block concatenation device 74 concatenates the reproduction data 75 of the block to be encoded obtained in step R8 and the encoded map generation block 67 obtained in step R9 to obtain reproduction data 76. Subsequently, i is incremented (step R14). In step R15, i = q to determine whether or not there is no block to be processed._k-M_kI = q_k-M_kIf so, the process ends. If not, the process returns to step R8.
[0342]
The following table shows the processing in the decoder described above in detail as an algorithm.
[0343]
[Table 10]

[0344]
[Table 11]

[0345]
Next, an example of application to information source coding with partial auxiliary information in the above-described decoder will be described.
[0346]
Whole series
[0347]
[Expression 125]

[0348]
The total code length of the X encoder and the total code length of the Y encoder for
[0349]
[Expression 126]

[0350]
To do. And the number of decoding error characters
[0351]
[Expression 127]

[0352]
And At this time, the following properties hold.
[0353]
Property: Simultaneous distribution p with X and Y as correlated steady memoryless information sources_XYZAssume that the above conditions 1 to 4 are satisfied. At this time,
[0354]
[Expression 128]

[0355]
In general, optimal R_XAnd R_YThere is a trade-off relationship between the choices, and both cannot be reduced freely. Optimal (R_X, R_Y) Is on the curve of the following function.
[0356]
[Expression 129]

[0357]
P in inf here_XYZSatisfies the conditions 1-3 of the conditions 1-4.
[0358]
At this time, the following properties hold.
[0359]
Property: R_X> 0, R_Y(H (X | Z), I (Y; Z)) is curve R for> 0_X(R_Y), R_Y(R_X) Distribution p as above_XYZIf this is taken, the algorithm of this embodiment will be an information source encoding algorithm with partial information in an asymptotically optimal decoder.
[0360]
The known distribution μ_XYTo p on the above curve_XYZThere is an approximate solution according to the reference [5].
[0361]
Both the encoder and the decoder according to the method of the present invention described above can be realized by reading a computer program for realizing them into a computer such as a microprocessor and executing the program. A program for encoding and decoding data by the method of the present invention is read into a computer by a recording medium such as a CD-ROM or a flash memory.
[0362]
Such a computer generally has a CPU (central processing unit), an external storage device such as a hard disk device or a nonvolatile memory for storing programs and data, a main memory, and inputs such as a keyboard, a mouse, and various switches. It is used to display a device, a display device such as a CRT or various display lamps, a reading device that reads a recording medium such as a CD-ROM or a flash memory, and accepts input data and transmits a code word or the like to a decoder ( An interface for receiving a code word or the like from the encoder and outputting reproduction data (for configuring a decoder). The external storage device, main memory, input device, display device, reading device, and interface are all connected to the CPU. In this computer, a recording medium storing a program for performing the above-described encoding procedure or decoding procedure is loaded into a reading device, the program is read from the recording medium, stored in an external storage device, and stored in the external storage device. When the program is executed by the CPU, the above-described encoding procedure or decoding procedure is executed by functioning as the above-described encoder or decoder.
[0363]
【The invention's effect】
As described above, the present invention divides the input data and performs separate encoding, and one of the divided data is used for the configuration of the encoded map, which cannot be realized in the conventional system. The present invention can also be applied to encoding that allows decoding errors, and has an effect of realizing an encoding system with high encoding efficiency that uses the randomness of past sequences.
[Brief description of the drawings]
FIG. 1 is a block diagram showing a configuration of a Bitsback encoder.
FIG. 2 is a block diagram showing a configuration of a Bitsback decoder.
FIG. 3 is a block diagram showing a system configuration based on multi-terminal information source encoding.
FIG. 4 is a block diagram showing a system configuration based on distortion information source coding.
FIG. 5 is a block diagram showing the configuration of a system based on information source coding with partial auxiliary information in a decoder.
FIG. 6 is a block diagram showing a configuration of an encoder that executes an encoding method according to the present invention.
FIG. 7 is a block diagram showing a configuration of a decoder that executes a decoding method according to the present invention.
FIG. 8 is a flowchart illustrating an encoding procedure when applied to multi-terminal information source encoding.
FIG. 9 is a flowchart illustrating a decoding procedure when applied to multi-terminal information source encoding.
FIG. 10 is a flowchart illustrating an encoding procedure when applied to distortion information source encoding.
FIG. 11 is a flowchart illustrating a decoding procedure when applied to distortion information source encoding.
FIG. 12 is a flowchart for explaining an information source encoding procedure when applied to information source encoding with partial auxiliary information in a decoder;
FIG. 13 is a flowchart illustrating an encoding procedure of a partial auxiliary information source when applied to information source encoding with partial auxiliary information in a decoder.
FIG. 14 is a flowchart for explaining a decoding procedure when the decoder is applied to information source coding with partial auxiliary information.
[Explanation of symbols]
10, 30_X, 30_Z, 40, 50_X, 50_Y60 encoder
11, 21, 62, 71 buffer
12, 22 Codeword selection device
13 Arithmetic decoder
14 Multi-level information source encoder
15, 65 Input data
20, 31, 41, 51, 70 Decoder
23 Arithmetic encoder
24 Multi-level information source decoder
25, 76 Playback data
61 Block divider
63 Coding map part
64 Undistorted encoder
66 Encoding target block
67 Encoded Map Generation Block
68 Codeword of the encoding target block
69 Codeword of encoded map generation block
72 Decoding mapping unit
73 Undistorted decoder
74 Block connecting device
75 Playback data of encoding target block

Claims (14)

A method for encoding input data, comprising:
Dividing one block of input data divided into a plurality of blocks into an encoding map generation block and an encoding target block;
Obtaining a codeword of the encoding target block from the encoding mapping generation block stored in the encoder buffer and the encoding target block using the encoding mapping;
Obtaining a codeword of the encoded map generation block using the encoded map generation block by a distortion-free encoder;
Discarding the oldest encoded mapping generation block remaining in the encoder buffer and newly storing the encoded mapping generation block in the encoder buffer;
Repeatedly executing each step until the plurality of blocks disappears;
A data encoding method comprising: The encoder buffer is initialized, and data is transmitted to the decoder in order to match the contents of the decoder buffer provided in the decoder to which each code word is input with the contents of the buffer. The data encoding method according to claim 1, further comprising a step. A decoding method for acquiring reproduction data from a codeword of a block to be encoded and a codeword of an encoded map generation block,
A step of taking out a code word of the encoding target block and obtaining reproduction data of the encoding target block by decoding mapping based on the code word of the encoding target block and the encoded mapping generation block stored in the decoder buffer When,
Extracting a codeword of the encoded map generation block and obtaining an encoded map generation block by a distortion-free decoder;
Discarding the oldest encoded map generation block remaining in the decoder buffer and newly storing the decoded encoded map generation block in the decoder buffer;
Concatenating and outputting the reproduction data of the encoding target block and the decoded encoded mapping generation block;
Repeatedly executing each step until all codewords are exhausted;
A data decoding method comprising: The data decoding method according to claim 3, wherein reproduction data is obtained from a codeword of the encoding target block encoded by a plurality of different encoders and a codeword of the encoded mapping generation block. For initialization of the decoder buffer, from the encoder that has encoded the codeword of the block to be encoded and the codeword of the encoded mapping generation block, the content of the decoder buffer is changed to the code of the encoder. 5. The data decoding method according to claim 3 or 4, further comprising a step of receiving information for matching the contents of the storage buffer. The codeword of the encoding target block and the codeword of the encoded mapping generation block are encoded by the data encoding method according to any one of claims 1 and 2. 6. The data decoding method according to any one of 5 above. A data encoding device for encoding input data,
A block dividing device that divides each block of input data divided into a plurality of blocks into an encoded mapping generation block and an encoding target block;
An encoder buffer for temporarily storing the encoded map generation block;
An encoding mapping unit that obtains a codeword of an encoding target block using an encoding mapping from the content of the encoder buffer and the encoding target block;
A distortionless encoder for obtaining a codeword of the encoded map generation block from the encoded map generation block;
Have
A data encoding apparatus, wherein each time a new encoded map generation block is input, the oldest encoded map generation block in the encoder buffer is discarded, and the new encoded map generation block is stored in the encoder buffer. A data decoding device for acquiring reproduction data from a codeword of a block to be encoded and a codeword of an encoded mapping generation block,
A decoder buffer for temporarily storing codewords of the encoded map generation block;
A decoding mapping unit that extracts a code word of the encoding target block and obtains reproduction data of the encoding target block by decoding mapping based on the code word of the encoding target block and the content of the decoder buffer;
A distortion-free decoder that obtains an encoded map generation block by extracting a codeword of the encoded map generation block;
A block concatenation device for concatenating and outputting the reproduction data of the encoding target block and the decoded encoded map generation block;
Have
A data decoding device in which each time a new encoded map generation block is decoded, the oldest encoded map generation block is discarded in the decoder buffer, and the new encoded map generation block is stored in the decoder buffer. . The codeword of the encoding target block and the codeword of the encoded mapping generation block are input from a plurality of encoders, and the decoder buffer is configured corresponding to each of the plurality of encoders, and an initialization process The data decoding device according to claim 8, wherein the content of the decoder buffer corresponding to the content of the encoder buffer in the encoder is matched. The codeword of the encoding target block and the codeword of the encoded mapping generation block are those transmitted from the data encoding device according to claim 7, according to any one of claims 8 and 9. The data decoding device described. On the computer,
A process of dividing one block of input data divided into a plurality of blocks into an encoding map generation block and an encoding target block;
A process of obtaining a code word of the encoding target block using the encoding mapping from the encoding mapping generation block stored in the encoder buffer and the encoding target block;
A process of obtaining a codeword of the encoded map generation block using the encoded map generation block by a distortion-free encoder;
Discarding the oldest encoded map generation block remaining in the encoder buffer and newly storing the encoded map generation block in the encoder buffer;
A process of repeatedly executing each of the processes until the plurality of blocks disappear;
A data encoding program for executing On the computer,
A process of receiving a codeword of an encoding target block and a codeword of an encoding mapping generation block;
Processing for extracting a code word of the encoding target block and obtaining reproduction data of the encoding target block by decoding mapping based on the code word of the encoding target block and the encoded mapping generation block stored in the decoder buffer When,
A process of taking a codeword of the encoded map generation block and obtaining an encoded map generation block by a distortion-free decoder;
Discarding the oldest encoded map generation block remaining in the decoder buffer and newly storing the decoded encoded map generation block in the decoder buffer;
A process of concatenating and outputting the reproduction data of the encoding target block and the decoded encoded mapping generation block;
A process of repeatedly executing each process until all codewords are exhausted;
A data decryption program for executing A computer-readable recording medium storing the data encoding program according to claim 11. A recording medium readable by a computer and storing the data decoding program according to claim 12.

Images