(57)【特許請求の範囲】
【請求項１】
複数の異なる情報源から各々出力された複数のデータ系列の少なくとも１つのデータ系列を可逆圧縮可能に符号化した第１符号語系列を、該第１符号語系列の符号化方式に対応した方式で復号する第１復号手段と、
前記第１復号手段による第１符号語系列の復号結果に基づいて、前記複数のデータ系列の他のデータ系列の条件付き平均情報量を低下させるためのデータ系列を作成する作成手段と、
Ｓｌｅｐｉａｎ−Ｗｏｌｆ理論により、前記他のデータ系列の条件付き平均情報量に基づいて設定されたサイズの検査行列を用いて、該他のデータ系列をＬＤＰＣ符号化またはＬＤＰＣ−ＣＣ符号化した第２符号語系列を、前記作成手段により作成されたデータ系列を用いて復号する第２復号手段と、
を含む復号装置。
【請求項２】
前記第２復号手段は、前記作成手段により作成されたデータ系列、前記検査行列、及び前記作成手段により作成されるデータ系列に応じて予め定められた確率変数を用いて、ｓｕｍ−ｐｒｏｄｕｃｔ法により、前記第２符号系列を復号する請求項１記載の復号装置。
【請求項３】
前記作成手段は、前記他のデータ系列の条件付き平均情報量を低下させるためのデータ系列を、前記第１符号語系列の復号結果を時間方向にシフトさせて作成する請求項１または請求項２記載の復号装置。
【請求項４】
複数の異なる情報源から各々出力された複数のデータ系列の一のデータ系列を可逆圧縮可能な第１符号語系列に符号化する少なくとも１つの第１符号化装置と、
Ｓｌｅｐｉａｎ−Ｗｏｌｆ理論により、前記複数のデータ系列の他のデータ系列の条件付き平均情報量に基づいて設定されたサイズの検査行列を用いて、該他のデータ系列を第２符号語系列にＬＤＰＣ符号化またはＬＤＰＣ−ＣＣ符号化する少なくとも１つの第２符号化装置と、
請求項１〜請求項３のいずれか１項記載の復号装置と、
を含む符号化復号システム。
【請求項５】
前記第１符号化装置及び前記第２符号化装置は、前記複数のデータ系列各々を、変換後のデータ系列の平均情報量が低下するように変換し、変換したデータ系列を符号化する請求項４記載の符号化復号システム。
【請求項６】
第１符号化装置と、第２符号化装置と、復号装置とを含む符号化復号システムにおける符号化復号方法であって、
前記第１符号化装置は、複数の異なる情報源から各々出力された複数のデータ系列の一のデータ系列を可逆圧縮可能な第１符号語系列に符号化し、
前記第２符号化装置は、Ｓｌｅｐｉａｎ−Ｗｏｌｆ理論により、前記複数のデータ系列の他のデータ系列の条件付き平均情報量に基づいて設定されたサイズの検査行列を用いて、該他のデータ系列を第２符号語系列にＬＤＰＣ符号化またはＬＤＰＣ−ＣＣ符号化し、
前記復号装置は、前記第１符号語系列を前記第１符号化装置の符号化方式に対応した方式で復号すると共に、該第１符号語系列の復号結果に基づいて、前記他のデータ系列の条件付き平均情報量を低下させるためのデータ系列を作成し、該作成されたデータ系列を用いて、前記第２符号語系列を復号する
符号化復号方法。
【請求項７】
コンピュータを、請求項１〜請求項３のいずれか１項記載の復号装置を構成する各手段として機能させるための復号プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、センサネットワークに代表される、二つ以上の情報源がある通信路におけるデータ系列の符号化及び復号を行う復号装置、符号化復号システム、符号化復号方法、及び復号プログラムに関する。
【背景技術】
【０００２】
センサネットワークは、複数のセンサで観測したデータ（デジタル信号）を、集積サーバまで無線通信を用いて送信するネットワークである。センサネットワークを構成するセンサノードは、搭載するバッテリ容量が小さいことから、通信にかかるコストを削減し、バッテリの使用量、すなわち消費電力を削減することが重要な技術的課題となっている。通信コストの削減方法のひとつとして、符号化手法を用いてデータの圧縮を行う方法が用いられる。
【０００３】
センサネットワークでは、センサノードを情報源とみなすと、複数の情報源で符号化を行い、一つの集積サーバで復号を行う通信路と見ることができる。このような、複数の情報源が存在する通信路における、通信レートの下限を与える理論としてＳｌｅｐｉａｎ−Ｗｏｌｆ理論がある（例えば、非特許文献１参照）。Ｓｌｅｐｉａｎ−Ｗｏｌｆ理論は、複数の情報源が発生するデジタル信号に対し、それぞれのデジタル信号を分散符号化した場合において、無歪状態で復号できる通信レート領域を与えたものである。この理論が与える通信レートを実現できる符号としてＬＤＰＣ符号（低密度パリティ検査符号、ｌｏｗ−ｄｅｎｓｉｔｙ  ｐａｒｉｔｙ−ｃｈｅｃｋ  ｃｏｄｅ）がある。さらに、ＬＤＰＣ符号の一つとして、畳込みＬＤＰＣ符号（ＬＤＰＣ−ＣＣ）がある。ＬＤＰＣ−ＣＣはＬＤＰＣに比べ、符号化の演算に必要となるメモリ容量が少ない。ＬＤＰＣ−ＣＣは搭載メモリ量が少ない計算装置上でも、符号化処理を行うことができる。このＬＤＰＣ符号の性能は、符号語の長さが長いほど理論が与える下限値に近いレートで伝送ができるという性質がある。以降、通信レートの下限値により近いレートで無歪通信ができることを、圧縮性能が高い、あるいは圧縮性能が良いと表現する。
【０００４】
以下、このＳｌｅｐｉａｎ−Ｗｏｌｆ理論及びＬＤＰＣ符号の説明に必要な記号及び用語の定義を行う。
【０００５】
ｎ個の情報源をＸ１，・・・，Ｘｎとする。情報源の出力するデジタル信号の系列は、０か１の数値の列として量子化されているものとする。情報源Ｘｉが出力するデジタル信号の平均情報量をＨ（Ｘｉ）とする。ｎ個全ての情報源の平均情報量の和は、Σi=1nＨ（Ｘｉ）である。Ｓｌｅｐｉａｎ−Ｗｏｌｆ符号を用いず、情報源毎に符号化を行い、集積サーバでそれぞれの情報源から得た符号を無歪で復号する場合、情報源Ｘｉと集積サーバ間に必要な通信レートＲｉは、Ｒｉ＝Ｈ（Ｘｉ）で与えられる。情報源Ｘｉがセンサノードであり、１ビットのデジタル信号を集積サーバまで無線通信を用いてデータの送受信を行う場合の消費電力（単位消費電力）をＷｉとする。このとき、各センサノードが観測するデータを集積サーバまで送信するための平均通信コストＣｉは、Ｃｉ＝Ｒｉ×Ｗｉで与えられる。また、センサネットワーク全体の平均通信コストの総和は、Σi=1nＣｉ＝Σi=1nＨ（Ｘｉ）×Ｗｉで与えられる。
【０００６】
なお、単位消費電力Ｗｉは、センサノードのハードウェア、及びセンサノードと集積サーバ間の無線通信距離に依存する値であり、物理的に決定される値である。以降、説明を簡単にするために、列挙するセンサノードの順序は、それらの単位消費電力について昇順に並んでいるものとする。すなわち、二つのセンサノードＸｉ，Ｘｊについてｉ＜ｊであればＷｉ≦Ｗｊである。
【０００７】
全てのセンサノードに対してＳｌｅｐｉａｎ−Ｗｏｌｆ符号を用いて符号化を行う場合で、かつＷ＝Ｗ１＝Ｗ２＝・・・＝Ｗｎであるとき、センサネットワーク全体の平均通信コストの総和は、Ｓｌｅｐｉａｎ−Ｗｏｌｆ理論により次の式で与えられる。
【０００８】
【数１】
0005642651.tif 000002
【０００９】
さらに、Ｗ１≦Ｗ２≦・・・≦Ｗｎであるとき、Ｌｉｕらによってセンサネットワーク全体の平均通信コストの総和は次式で与えられることが示されている（例えば、非特許文献２参照）。
【００１０】
【数２】
0005642651.tif 000003
【００１１】
各Ｘｉについて、明らかにＨ（Ｘｉ｜Ｘｉ−１，Ｘｉ−２，・・・，Ｘ１）≦Ｈ（Ｘｉ）であることから、Ｓｌｅｐｉａｎ−Ｗｏｌｆ符号を用いた方が平均通信コストの総和が小さくなる。すなわち、Ｓｌｅｐｉａｎ−Ｗｏｌｆ符号を用いた方が消費電力を低減できる。
【００１２】
上記のように、複数の系列のデジタル信号を独立した符号装置で符号化し、一つの復号装置で復号する方式が提案されている（例えば、非特許文献３参照）。非特許文献３の方式では、独立した複数のデジタル信号に対してＳｌｅｐｉａｎ−Ｗｏｌｆ理論を利用し、線形符号であるＬＤＰＣ符号を用いて符号化を行っている。
【００１３】
また、複数の系列のデジタル信号を独立した符号装置で符号化する課程で、Ｓｌｅｐｉａｎ−Ｗｏｌｆ符号かエントロピー符号の二つの符号化法から、より圧縮率が高くなる方法を選択して符号化を行う方式が提案されている（例えば、特許文献１参照）。特許文献１の方法では、Ｓｌｅｐｉａｎ−Ｗｏｌｆ符号を用いる場合にＬＤＰＣやターボ符号を用いている。
【００１４】
また、畳込みＬＤＰＣ（ＬＤＰＣ−ＣＣ）符号の検査行列の構成法が提案されている（例えば、非特許文献４及び５参照）。
【先行技術文献】
【特許文献】
【００１５】
【特許文献１】特開２００９−２９６２７７号公報
【非特許文献】
【００１６】
【非特許文献１】David Slepian and Jack K. Wolf: Noiseless Coding of Correlated Information Sources, IEEE Transactions on Information Theory, Volume: 19, Number 4, pp. 471--480 (1973).
【非特許文献２】Junning Liu, Micah Adler, Don Towsley, and Chun Zhang.: On optimal communication cost for gathering correlated data through wireless sensor networks. In Proceedings of the 12th annual international conference on Mobile computing and networking, pp. 310--321 (2006).
【非特許文献３】Liveris, A.D., Zixiang Xiong, Georghiades, C.N.: Compression of binary sources with side information at the decoder using LDPC codes, Communications Letters, IEEE, Volume: 6 Issue:10 ,pp.440 -- 442 (2002).
【非特許文献４】Jimenez Felstrom, A., Zigangirov, K.S.: Time-varying periodic convolutional codes with low-density parity-check matrix, IEEE Transactions on Information Theory, Volume: 45 Issue:6, pp. 2181 - 2191 (1999).
【非特許文献５】笠井健太、坂庭好一：有界な重みのパリティ検査行列を有し通信路容量を達成する符号の空間結合、The 33rd Symposium on Information Theory and its Applications (SITA2010).
【発明の概要】
【発明が解決しようとする課題】
【００１７】
しかしながら、非特許文献３の方法では、条件付き平均情報量を低下させることで圧縮率を高める方法については記されていないため、圧縮率が高くならない、あるいは圧縮できない場合がある、という問題がある。
【００１８】
また、特許文献１には、符号の具体的な構成法については記されていないため、上記と同様に、圧縮率が高くならない、あるいは圧縮できない場合がある、という問題がある。
【００１９】
また、非特許文献４及び５の方法では、Ｓｌｅｐｉａｎ−Ｗｏｌｆ理論を用いる方法については記述されておらず、複数の情報源の出力するデータ系列の相関を利用して圧縮を行うことができない、という問題がある。
【００２０】
本発明は、上記の課題を解決するためになされたもので、複数の情報源が出力するデジタル信号をＳｌｅｐｉａｎ−Ｗｏｌｆ理論に基づきＬＤＰＣ符号またはＬＤＰＣ−ＣＣ符号を用いて符号化及び復号を行う場合において、圧縮率を高めることができる復号装置、符号化復号システム、符号化復号方法、及び復号プログラムを提供することを目的とする。
【課題を解決するための手段】
【００２１】
上記目的を達成するために、本発明の復号装置は、複数の異なる情報源から各々出力された複数のデータ系列の少なくとも１つのデータ系列を可逆圧縮可能に符号化した第１符号語系列を、該第１符号語系列の符号化方式に対応した方式で復号する第１復号手段と、前記第１復号手段による第１符号語系列の復号結果に基づいて、前記複数のデータ系列の他のデータ系列の条件付き平均情報量を低下させるためのデータ系列を作成する作成手段と、Ｓｌｅｐｉａｎ−Ｗｏｌｆ理論により、前記他のデータ系列の条件付き平均情報量に基づいて設定されたサイズの検査行列を用いて、該他のデータ系列をＬＤＰＣ符号化またはＬＤＰＣ−ＣＣ符号化した第２符号語系列を、前記作成手段により作成されたデータ系列を用いて復号する第２復号手段と、を含んで構成されている。
【００２２】
本発明の復号装置によれば、第１復号手段が、複数の異なる情報源から各々出力された複数のデータ系列の少なくとも１つのデータ系列を可逆圧縮可能に符号化した第１符号語系列を、第１符号語系列の符号化方式に対応した方式で復号する。そして、作成手段が、第１復号手段による第１符号語系列の復号結果に基づいて、複数のデータ系列の他のデータ系列の条件付き平均情報量を低下させるためのデータ系列を作成する。そして、第２復号手段が、Ｓｌｅｐｉａｎ−Ｗｏｌｆ理論により、他のデータ系列の条件付き平均情報量に基づいて設定されたサイズの検査行列を用いて、他のデータ系列をＬＤＰＣ符号化またはＬＤＰＣ−ＣＣ符号化した第２符号語系列を、作成手段により作成されたデータ系列を用いて復号する。
【００２３】
このように、Ｓｌｅｐｉａｎ−Ｗｏｌｆ理論に基づいてＬＤＰＣ符号化またはＬＤＰＣ−ＣＣ符号化される他のデータ系列の条件付き平均情報量を低下させるためのデータ系列を作成し、このデータ系列を用いて他のデータ系列を符号化した第２符号語系列の復号を行うため、複数の情報源が出力するデジタル信号をＳｌｅｐｉａｎ−Ｗｏｌｆ理論に基づきＬＤＰＣ符号またはＬＤＰＣ−ＣＣ符号を用いて符号化及び復号を行う場合において、圧縮率を高めることができる。
【００２４】
また、前記第２復号手段は、前記作成手段により作成されたデータ系列、前記検査行列、及び前記作成手段により作成されるデータ系列に応じて予め定められた確率変数を用いて、ｓｕｍ−ｐｒｏｄｕｃｔ法により、前記第２符号系列を復号することができる。
【００２５】
また、前記作成手段は、前記他のデータ系列の条件付き平均情報量を低下させるためのデータ系列を、前記第１符号語系列の復号結果を時間方向にシフトさせて作成することができる。
【００２６】
また、本発明の符号化復号システムは、複数の異なる情報源から各々出力された複数のデータ系列の一のデータ系列を可逆圧縮可能な第１符号語系列に符号化する少なくとも１つの第１符号化装置と、Ｓｌｅｐｉａｎ−Ｗｏｌｆ理論により、前記複数のデータ系列の他のデータ系列の条件付き平均情報量に基づいて設定されたサイズの検査行列を用いて、該他のデータ系列を第２符号語系列にＬＤＰＣ符号化またはＬＤＰＣ−ＣＣ符号化する少なくとも１つの第２符号化装置と、上記の復号装置と、を含んで構成されている。
【００２７】
また、本発明の符号化復号システムにおいて、前記第１符号化装置及び前記第２符号化装置は、前記複数のデータ系列各々を、変換後のデータ系列の平均情報量が低下するように変換し、変換したデータ系列を符号化することができる。
【００２８】
また、本発明の符号化復号方法は、第１符号化装置と、第２符号化装置と、復号装置とを含む符号化復号システムにおける符号化復号方法であって、前記第１符号化装置は、複数の異なる情報源から各々出力された複数のデータ系列の一のデータ系列を可逆圧縮可能な第１符号語系列に符号化し、前記第２符号化装置は、Ｓｌｅｐｉａｎ−Ｗｏｌｆ理論により、前記複数のデータ系列の他のデータ系列の条件付き平均情報量に基づいて設定されたサイズの検査行列を用いて、該他のデータ系列を第２符号語系列にＬＤＰＣ符号化またはＬＤＰＣ−ＣＣ符号化し、前記復号装置は、前記第１符号語系列を前記第１符号化装置の符号化方式に対応した方式で復号すると共に、該第１符号語系列の復号結果に基づいて、前記他のデータ系列の条件付き平均情報量を低下させるためのデータ系列を作成し、該作成されたデータ系列を用いて、前記第２符号語系列を復号する方法である。
【００２９】
また、本発明の復号プログラムは、コンピュータを、上記の復号装置を構成する各手段として機能させるためのプログラムである。
【発明の効果】
【００３０】
以上説明したように、本発明の復号装置、符号化復号システム、符号化復号方法、及び復号プログラムによれば、Ｓｌｅｐｉａｎ−Ｗｏｌｆ理論に基づいてＬＤＰＣ符号化またはＬＤＰＣ−ＣＣ符号化される他のデータ系列の条件付き平均情報量を低下させるためのデータ系列を作成し、このデータ系列を用いて他のデータ系列を符号化した第２符号語系列の復号を行うため、複数の情報源が出力するデジタル信号をＳｌｅｐｉａｎ−Ｗｏｌｆ理論に基づきＬＤＰＣ符号またはＬＤＰＣ−ＣＣ符号を用いて符号化及び復号を行う場合において、圧縮率を高めることができる、という効果が得られる。
【図面の簡単な説明】
【００３１】
【図１】本実施の形態のセンサネットワークシステムの構成を示す概略図である。
【図２】本実施の形態の原理を説明するための概略図である。
【図３】本実施の形態のセンサネットワークシステムにおける初期化処理ルーチンの内容を示すフローチャートである。
【図４】本実施の形態のセンサネットワークシステムにおける符号化処理ルーチンの内容を示すフローチャートである。
【図５】本実施の形態のセンサネットワークシステムにおける復号処理ルーチンの内容を示すフローチャートである。
【図６】本実施の形態の復号処理において、ｓｕｍ−ｐｒｏｄｕｃｔ法で用いるファクターグラフの作成方法を説明するための図である。
【図７】従来手法において、ｓｕｍ−ｐｒｏｄｕｃｔ法で用いるファクターグラフの作成方法を説明するための参考図である。
【発明を実施するための形態】
【００３２】
以下、図面を参照して本発明の実施の形態を詳細に説明する。本実施の形態では、センサネットワークシステムに、本発明の符号化復号システムを適用した例について説明する。なお、本発明では、Ｓｌｅｐｉａｎ−Ｗｏｌｆ理論に基づく符号は、ＬＤＰＣ符号であってもＬＤＰＣ−ＣＣ符号であってもよいが、本実施の形態ではＬＤＰＣ符号を用いる場合について説明する。
＜本実施の形態の構成＞
図１に示すように、本実施の形態のセンサネットワークシステム１は、観測装置１１及び１２と、符号化装置２１及び２２と、送信装置３１及び３２と、受信装置４０と、復号装置５０とを含んで構成されている。
【００３３】
観測装置１１及び１２は、温度、湿度、照度、加速度などの物理量を観測するためのセンサを含んで構成されており、センサで観測された観測値をデジタル信号の系列に変換して出力する。
【００３４】
符号化装置２１及び２２は、観測装置１１及び１２各々から出力されたデジタル信号の系列に前処理を行って、符号化する。符号化装置２１及び２２は、デジタル信号の可逆圧縮が可能な符号化の手段をもつ。符号化装置２１及び２２の一方は、少なくともＬＤＰＣ符号化法を符号化の手段として持つ。符号化装置２１及び２２の他方の符号化の手段は、ハフマン符号、算術符号、ターボ符号、ＬＺＷ（Ｌｅｍｐｅｌ−Ｚｉｖ−Ｗｅｌｃｈ）、ＬＺ７７（Ｌｅｍｐｅｌ−Ｚｉｖ７７）などでもよい。
【００３５】
送信装置３１及び３２は、符号化装置２１及び２２各々で符号化された符号を、有線または無線通信により送信する。受信装置４０は、送信装置３１及び３２から送信された符号を受信し、復号装置５０へ出力する。
【００３６】
復号装置５０は、符号化装置２１及び２２で符号化された符号を復号し、デジタル信号の系列を出力する。復号装置５０は、符号化装置２１及び２２がもつ符号化手段に対応する復号手段をもつ。復号装置５０は、複数の符号語を受け取り、それらを同時に復号し、複数のデジタル信号の系列として出力する手段をもつ。ＬＤＰＣ符号の復号アルゴリズムとして、少なくともｓｕｍ−ｐｒｏｄｕｃｔ法による復号手段をもつ。
【００３７】
本実施の形態のセンサネットワークシステム１では、図１に示すように、情報源が二つの場合について説明するが、情報源が三つ以上の場合は、情報源一つにつき観測装置、符号化装置、及び送信装置を一つずつ設置する。
【００３８】
符号化装置２１及び２２、並びに復号装置５０はそれぞれ、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）と、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）と、後述する初期化処理、符号化処理、復号処理を実行するためのプログラムを記憶したＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）とを備えたコンピュータで構成することができる。また、各々のＲＯＭには、ＬＤＰＣを用いて符号化及び復号するときに必要となる行列式等の情報が、予め記憶される。
＜本実施の形態の原理＞
ここで、本実施の形態により圧縮率を高めることができる原理について説明する。本実施の形態では、（ｉ）デジタル信号の系列を平均情報量が低下するように前処理を行ってから符号化すること、（ｉｉ）Ｓｌｅｐｉａｎ−Ｗｏｌｆ理論に基づく通信レートの設定に必要な条件付き平均情報量を低下させることにより、圧縮率を高める。
【００３９】
まず、上記（ｉ）について説明する。ここでは、情報源が二つの場合について説明する。
【００４０】
情報源Ｘ１及びＸ２があるとき、それぞれの情報源に対応する送信装置と受信装置との間で歪みなくデジタル信号を伝送するためには、ＬＤＰＣ符号の符号化処理で用いる検査行列のサイズを、Ｓｌｅｐｉａｎ−Ｗｏｌｆ理論に基づいて予め求めておく必要がある。情報源Ｘ１及びＸ２について、それぞれ符号化するときに用いる検査行列をＡ１及びＡ２とする。Ａ１はｍ１×ｎ１行列であり、Ａ２はｍ２×ｎ２行列であるとする。このとき、それぞれの情報源の出力するデジタル信号を歪みなく送信するためには、検査行列のサイズの比率ｎ１／ｍ１＝Ｒ１、ｎ２／ｍ２＝Ｒ２を下記（１）式のように決める必要がある。
【００４１】
【数３】
0005642651.tif 000004
【００４２】
（１）式は、Ｓｐｅｌｉａｎ−Ｗｏｌｆ理論によって与えられる。なお、Ｒ１及びＲ２は伝送路の通信レートと同義である。以降は、Ｒ１及びＲ２をもって通信レートと称する。
【００４３】
（１）式に基づくと、Ｈ（Ｘ２，Ｘ１）が低ければ低いほど、通信レートを低く決めることができる。このＨ（Ｘ２，Ｘ１）という値は、Ｘ１及びＸ２のデジタル信号の間のビットの対応の取り方や、データの並び順によって値が異なる。例えば、Ｘ１及びＸ２が時区間Ｔ＝［ｔ，ｔ＋１９］に出力したデジタル信号の系列Ｘ１（Ｔ）＝｛ｘ１（ｔ），ｘ１（ｔ＋１），・・・，ｘ１（ｔ＋１９）｝、Ｘ２（Ｔ）＝｛ｘ２（ｔ），ｘ２（ｔ＋１），・・・，ｘ２（ｔ＋１９）｝であり、下記（２）式及び（３）式のようであったとする。
【００４４】
【数４】
0005642651.tif 000005
【００４５】
このとき、Ｈ（Ｘ２（Ｔ），Ｘ１（Ｔ））は、下記（４）式となる。
【００４６】
【数５】
0005642651.tif 000006
【００４７】
この値に基づいて通信レートを設定すると、下記（５）式となる。
【００４８】
【数６】
0005642651.tif 000007
【００４９】
つまり、情報源Ｘ１及びＸ２の出力するデジタル信号の系列を歪みなく伝送するためには、合計で２ビット以上の通信レートが必要となることを意味する。この通信レートに基づいて通信を行おうとすると、圧縮率の上限は１（ｂｉｔ）−２（ｂｉｔ）／２（情報源の数）＝０である。つまり、このデジタル信号は圧縮して伝送することができないことを意味する。
【００５０】
情報源がセンサであるとき、センサから得られた数値データをそのままデジタル信号の系列として用いると、前記のＸ１（Ｔ），Ｘ２（Ｔ）の例に示したように、圧縮率が高くならない、あるいは圧縮できないことがある。
【００５１】
圧縮率を高めるためには、時区間Ｔ＝［ｔ，ｔ＋ｎ］の二つのデジタル信号Ｘ１（Ｔ）及びＸ２（Ｔ）に対して可逆な変換を行うことで求められる、不等式Ｈ（Ｙ１（Ｔ），Ｙ２（Ｔ））≦Ｈ（Ｘ１（Ｔ），Ｘ２（Ｔ））を満たすようなデジタル信号の系列Ｙ１（Ｔ）及びＹ２（Ｔ）を求めることが必要となる。本実施の形態では、このような条件を満たす可逆変換の手順を、符号化の前処理として導入する。
【００５２】
ここでＹ（Ｔ）＝｛ｙ（ｔ），ｙ（ｔ＋１），・・・，ｙ（ｔ＋１９）｝を、下記（６）式のように定義する。ただしｘ（ｔ−１）＝０であるものとする。
【００５３】
【数７】
0005642651.tif 000008
【００５４】
（６）式のように定義すると、Ｙ１（Ｔ）及びＹ２（Ｔ）は、下記（７）式及び（８）式のようになる。
【００５５】
【数８】
0005642651.tif 000009
【００５６】
このとき、Ｈ（Ｙ２（Ｔ），Ｙ１（Ｔ））は、下記（９）式となる。
【００５７】
【数９】
0005642651.tif 000010
【００５８】
Ｙ１（Ｔ）からＸ１（Ｔ）への変換は一意に可能であるので、情報としてはＹ１（Ｔ）とＸ１（Ｔ）とは等しい。しかし、以上に示したようにＨ（Ｘ２（Ｔ），Ｘ１（Ｔ））≠Ｈ（Ｙ２（Ｔ），Ｙ１（Ｔ））である。この数値に基づいて通信レートを設定すると、下記（１０）式となる。
【００５９】
【数１０】
0005642651.tif 000011
【００６０】
Ｘ１及びＸ２のデジタル信号を歪みなく送信するためには２ｂｉｔ必要であるのに対し、Ｙ１及びＹ２のデジタル信号は０．７４７５８４６８ｂｉｔで送信できる。０．７４７５８４６８／２＝０．３７３７９２３４であるから、Ｘ１及びＸ２を直接送信する場合に比べて、約３７．４％の通信レートでデータを転送できる。このように、デジタル信号の系列の表現方法、言い換えれば量子化の方法によって、理論的に求められる圧縮率が変化する。
【００６１】
上記の前処理を一般化すると、下記（１１）式及び（１２）式のようになる。以下、記述の煩雑化を防ぐために、Ｙ１（Ｔ）及びＹ２（Ｔ）を単にＹ１及びＹ２と記述する。
【００６２】
【数１１】
0005642651.tif 000012
【００６３】
次に、上記（ｉｉ）について説明する。
【００６４】
上記（ｉ）で述べた前処理後のＹ１から、Ｙ１’を下記（１４）式で求める。
【００６５】
【数１２】
0005642651.tif 000013
【００６６】
（１５）式のＺ（１，ｌ）は、Ｙ１を時間方向にｌだけシフトして作ったデジタル信号の列であり、復号したＹ１から容易に作成可能である。復号したＹ１からＹ１’を作成することにより、復号したＹ１を、あたかも複数の情報源から受け取ったデジタル信号の系列であるかのように扱う。
【００６７】
このとき、通信レートＲ１＋Ｒ２は下記（１６）式で与えられる。
【００６８】
【数１３】
0005642651.tif 000014
【００６９】
例えばＷ２＞Ｗ１であるとき、この式に基づいて、Ｒ１及びＲ２を下記（１７）式及び（１８）式のように決めることで、通信コストを最小化することができる。
【００７０】
【数１４】
0005642651.tif 000015
【００７１】
一般に、デジタル信号の系列Ｘ１、Ｘ２、Ｘ３に対してＨ（Ｘ１｜Ｘ２）≧Ｈ（Ｘ１｜Ｘ２，Ｘ３）が成り立つので、Ｈ（Ｙ２｜Ｙ１）≧Ｈ（Ｙ２｜Ｙ１’）である。すなわちＨ（Ｘ２｜Ｘ１）≧Ｈ（Ｙ２｜Ｙ１）が成り立つとき、Ｈ（Ｘ２｜Ｘ１）≧Ｈ（Ｙ２｜Ｙ１’）が成り立つ。これは、Ｒ１＋Ｒ２の値をより小さく設定できる可能性があることを意味する。仮に（１３）式を用いた場合に、Ｈ（Ｘ２｜Ｘ１）≦Ｈ（Ｙ２｜Ｙ１）となるときは、（１３）式の代わりにｙ１（ｔ）＝ｘ１（ｔ）、ｙ２（ｔ）＝ｘ２（ｔ）としてＹ２及びＹ１’を決める。このときもＨ（Ｘ２｜Ｘ１）≧Ｈ（Ｙ２｜Ｙ１’）が成り立つため、Ｒ１＋Ｒ２の値をより小さく設定できる可能性がある。
【００７２】
以上の方法で求めたＹ１及びＹ２から導出される通信レートＲ１＋Ｒ２で、符号化を行った符号語を歪みなく復号するためには、Ｘ２から生成した符号語を復号するときに使用する、ｓｕｍ−ｐｒｏｄｕｃｔアルゴリズム（非特許文献６「和田山 正、“誤り訂正技術の基礎”，森北出版 (2010)」参照）のファクターグラフで、通常はｐ（Ｘ２｜Ｘ１）の値を使用する定数ノードの値の代わりに、下記（１９）式で与えられる値を用いる。  
【００７３】
【数１５】
0005642651.tif 000016
【００７４】
上記の本実施の形態の原理の概念図を図２に示す。情報源からのデジタル信号Ｘ１及びＸ２に、（１１）式及び（１２）式による前処理を行い（図１中「φ」）、出力されたＹ１及びＹ２を符号化装置ｃ１及びｃ２で、Ｓｌｅｐｉａｎ−Ｗｏｌｆ理論に基づきＬＤＰＣ符号化する。符号化された符号語ｃ１（Ｙ１）及びｃ'２（Ｙ２）を、通信路を介して復号装置ｃ−１へ送る。通信レートＲ１及びＲ２は、（１７）式及び（１８）式により設定されている。復号装置ｃ−１では、符号語ｃ１（Ｙ１）を復号してＹ１を得る。そして、このＹ１から、（１４）式により、Ｙ１’を作成する（同図中「φ’」）。復号装置ｃ−１では、符号語ｃ２（Ｙ２）を、予め（１９）式により定めたｐ（Ｙ２｜Ｙ１’）、作成したＹ１’、Ｒ１及びＲ２に基づいて予め定められた検査行列を用いて、ｓｕｍ−ｐｒｏｄｕｃｔアルゴリズムにより復号してＹ２を得る。
【００７５】
デジタル信号の系列が三つ以上（ｋ個）の場合、通信レートの総和Σi=1kＲｉは下記（２０）式で決める。
【００７６】
【数１６】
0005642651.tif 000017
【００７７】
デジタル信号の系列Ｘｉに対応する符号語を復号するときは、ｐ（Ｘｉ｜Ｘｉ−１，・・・，Ｘ１）の値の代わりに、下記（２１）式で求めるｐ（Ｙｉ｜Ｙｉ−１’，・・・，Ｙ１’）の値を用いる。
【００７８】
【数１７】
0005642651.tif 000018
【００７９】
上記のように、ＬＤＰＣ符号をｓｕｍ−ｐｒｏｄｕｃｔアルゴリズムで復号するときに、ｐ（Ｘ２｜Ｘ１）の値を用いる代わりに、ｐ（Ｙ２｜Ｙ１’）を用いることで、デジタル信号の圧縮率を高められる。ｐ（Ｘ２｜Ｘ１）を用いた場合は、歪みなく圧縮できる通信レートの下限は（１）式で与えられる。一方、本実施の形態のようにｐ（Ｙ２｜Ｙ１’）を用いた場合の下限は（１６）式で与えられる。（１６）式で与えられる下限値の方が、（１）式の値より理論的に低くなることが保証される。本実施の形態を用いると従来法より歪みなく圧縮できる通信レートを下げることができる。すなわち、圧縮率を高めることができる。
＜本実施の形態の作用＞
次に、本実施の形態のセンサネットワークシステム１の作用について説明する。まず、後述する初期化処理を実行することにより、符号化及び復号処理に必要な情報を符号化装置２１及び２２、並びに復号装置５０に設定する。そして、符号化装置２１及び２２において、後述する符号化処理を実行し、復号装置５０において、後述する復号処理を実行する。
【００８０】
ここで、ＬＤＰＣ符号は、与えられた行列サイズ（通信レート）が、符号化するデータの平均情報量を下回ると、復号したときに歪みが生じることがある。このため、符号化処理を実行する前に、デジタル信号の通信レートが既知でなければならない。すなわち、Ｓｌｅｐｉａｎ−Ｗｏｌｆ理論に基づいた通信レートを設定する場合は、本実施の形態の原理で説明した図２中のＨ（Ｙ１）及びＨ（Ｙ２｜Ｙ１’）の値の両方を通信前に知っておく必要がある。ただし、通信レートを完全に事前に知ることは不可能であることから、過去のデータから通信レートを予想する。この処理が初期化処理である。以下、図３を参照して、初期化処理について説明する。なお、初期化処理は、符号化装置２１、２２、または復号装置５０で実行されてもよいし、他のコンピュータ等で実行してもよい。
【００８１】
ステップ１００で、観測装置１１及び１２各々から出力されたデジタル信号の系列Ｘ１及びＸ２を取得する。
【００８２】
次に、ステップ１０２で、（１１）式、（１２）式、及び（１４）式を用いて、上記ステップ１００で取得したＸ１及びＸ２から、Ｙ１、Ｙ１’、Ｙ２、Ｙ２’を求める。Ｙ１’を求めるときに用いる数値ｌは、システム設計時に予め定めておく。Ｗ１≦Ｗ２であるとき、通信レートを  Ｒ１≧Ｈ（Ｙ１）、Ｒ２≧Ｈ（Ｙ２｜Ｙ１’）となるように決める。Ｗ１≧Ｗ２であるときは、Ｒ２≧Ｈ（Ｙ２）、Ｒ１≧Ｈ（Ｙ１｜Ｙ２’）となるように決める。以下はＷ１≦Ｗ２のケースについて説明する。
【００８３】
次に、ステップ１０４で、符号化装置２１及び２２でＬＤＰＣ符号を用いて符号化するときに使用する検査行列Ａ１及びＡ２のサイズｎ１×ｍ及びｎ２×ｍを、上記ステップ１０２で決定したＲ１及びＲ２に基づいて、ｎ１／ｍ＝Ｒ１、ｎ２／ｍ＝Ｒ２となるように決める。ｍはシステム設計時に予め定めておく定数である。
【００８４】
次に、ステップ１０６で、上記ステップ１０４で決定したサイズに基づいて、検査行列Ａ１及びＡ２を生成する。検査行列の生成方法は特に限定されるものではないが、復号法としてｓｕｍ−ｐｒｏｄｕｃｔ法を用いる場合には、各列の１の数の合計値が等しく、かつ各行の１の数の合計値が等しくなるような行列式を生成することが好ましい。生成した検査行列Ａ１をＸ１に対応する符号化装置２１内の記憶装置に保存し、検査行列Ａ２をＸ２に対応する符号化装置２２内の記憶装置に保存し、Ａ１及びＡ２を復号装置５０内の記憶装置に保存する。
【００８５】
次に、ステップ１０８で、（１９）式により、ｐ（Ｙ２｜Ｙ１’）を計算し、復号装置５０内の記憶装置に保存して、初期化処理を終了する。
【００８６】
次に、図４を参照して、符号化装置２１及び２２において実行される符号化処理について説明する。なお、符号化装置２１において、図４の左側のフローが実行され、符号化装置２２において、図４の右側のフローが実行される。
【００８７】
ステップ２１０で、観測装置１１において、時刻ｔからｔ＋ｍの間に観測されて出力されたデジタル信号の系列Ｘ１を取得する。また、ステップ２２０で、観測装置１２において、時刻ｔからｔ＋ｍの間に観測されて出力されたデジタル信号の系列Ｘ２を取得する。
【００８８】
次に、ステップ２１２で、前処理として、（１１）式により、上記ステップ２１０で取得したＸ１からＹ１を計算する。また、ステップ２２２で、（１２）式により、上記ステップ２２０で取得したＸ２からＹ２を計算する。
【００８９】
次に、ステップ２１４で、上記ステップ２１２で計算したＹ１、及び上記初期化処理のステップ１０６で符号化装置２１内の記憶装置に保存された検査行列Ａ１を用いて、ＬＤＰＣ符号ｃ（Ｙ１）＝Ａ１Ｙ１Ｔを計算する。また、ステップ２２５で、上記ステップ２２２で計算したＹ２、及び上記初期化処理のステップ１０６で符号化装置２２内の記憶装置に保存された検査行列Ａ２を用いて、ＬＤＰＣ符号ｃ（Ｙ２）＝Ａ２Ｙ２Ｔを計算する。
【００９０】
次に、ステップ２１６で、上記ステップ２１４で符号化されたｃ（Ｙ１）を、送信装置３１を経由して受信装置４０に送信する。また、ステップ２２６で、上記ステップ２２５で符号化されたｃ（Ｙ２）を、送信装置３２を経由して受信装置４０に送信して、符号化処理を終了する。
【００９１】
なお、上記では、符号化装置２１におけるＹ１の符号化をＬＤＰＣで行う場合について説明したが、Ｙ１の符号化にはＬＺＷ、ハフマン符号、ｇｚｉｐなどの他の可逆圧縮符号を用いてもよい。後述する復号処理において、Ｙ１の復号は、他の情報を用いずに単独で復号するからである。ＬＺＷやハフマン符号の方が、歪みの発生を防止できる効果が高い。
【００９２】
次に、図５を参照して、復号装置５０において実行される復号処理について説明する。
【００９３】
ステップ５００で、符号化装置２１及び２２から送信装置３２を経由して送信され、受信装置４０で受信したｃ（Ｙ１）及びｃ（Ｙ２）を取得する。
【００９４】
次に、ステップ５０２で、符号化装置２１の符号化方式に応じた復号アルゴリズムを用いて、上記ステップ５００で取得したｃ（Ｙ１）を復号し、Ｙ１を得る。ここでは、ＬＤＰＣ符号化方式に従って、上記初期化処理のステップ１０６で復号装置５０の記憶装置に保存された検査行列Ａ１を用いて復号する。
【００９５】
次に、ステップ５０４で、上記ステップ５０２で得たＹ１から、（１４）式によりＹ１’を作成する。
【００９６】
次に、ステップ５０６で、上記初期化処理のステップ１０６及び１０８で復号装置５０の記憶装置に保存された検査行列Ａ２及びｐ（Ｙ２｜Ｙ１’）と、上記ステップ５０４で作成したＹ１’と、上記ステップ５００で取得したｃ（Ｙ２）とを用いて、ｓｕｍ−ｐｒｏｄｕｃｔ法で用いるファクターグラフを作成する。
【００９７】
ここで、ファクターグラフの作成例を図６に示す。また、従来法によるファクターグラフの作成法を、参考として図７に示す。比較を容易にするため、この例ではＸ１＝Ｙ１、Ｘ２＝Ｙ２としている。
【００９８】
ファクターグラフは、復号装置５０が記憶媒体中に保持する検査行列Ａ２から生成する。ＬＤＰＣ符号化された符号語を復号するために、ｓｕｍ−ｐｒｏｄｕｃｔアルゴリズムが用いるファクターグラフは、変数ノード（符号語）、関数ノード（確率変数）、変数ノード（復号語）、及び関数ノード（確率演算）の四種類のノードで構成される。
【００９９】
変数ノード（符号語）は、符号語のビット値を定数値として与えるノードである。図６及び７では、グラフの最も左の列のノードである。グラフの上部からｃ（ｙ２（１））、ｃ（ｙ２（２））、・・・  の順で、符号語のビットを初期値として割り当てる。図６及び７の例では、ｃ（Ｙ２）＝“０、１”であるからｃ（ｙ２（１））＝“０”、ｃ（ｙ２（２））＝“１”であり、上部のノードから順に０、１の値が割り当てられる。
【０１００】
関数ノード（確率変数）は、従来のファクターグラフにおいては、ｐ（Ｙ２｜Ｙ１）の値（実数値）を初期値として与える関数ノードである。図６及び７では、グラフの最も右の列のｐ１、ｐ２、・・・で表されるノードである。従来のファクターグラフでは、ノードｐｉの値は、ｐ（ｙ２＝１｜ｙ１（ｉ））を与える。例えばｐ１は、Ｙ１＝１，１，０であるから、ｙ１（１）＝１であり、ｐ（ｙ２＝１｜ｙ１＝１）を初期値として与える。本実施の形態では、この関数ノードに、ｐ（Ｙ２｜Ｙ１’）の値を用いる。
【０１０１】
変数ノード（復号語）は、復号語のｉ番目のビットが１である確率を格納する変数ノードである。図中Ｘｉで示されたノードである。Ｘｉの値は、ｓｕｍ−ｐｒｏｄｕｃｔアルゴリズムによって変動する。
【０１０２】
関数ノード（確率演算）は、検査行列Ａ２のビット構造を表すために用いられるノードである。図中ｆｉで示されたノードである。値はｓｕｍ−ｐｒｏｄｕｃｔアルゴリズムの計算過程で使用される。
【０１０３】
関数ノードｆｉと変数ノードｃ（ｙ２（ｉ））とは１本の辺で結ばれる。同様に、関数ノードｐｉと変数ノードＸｉとは１本の辺で結ばれる。ｆｉとＸｊとの間の辺については、ｉ列ｊ行の検査行列Ａ２の要素ａｉ,ｊについて、ａｉ,ｊ＝１である場合、ｆｉとＸｊとの間を辺で結ぶ。図６及び７の例では、ａ１,１＝ａ２,１＝ａ３,１＝１であるから、ｆ１とＸ１、Ｘ２、Ｘ３との間を辺で結ぶ。ｆ２については、ａ１,２＝０であり、ａ２,１＝ａ３,１＝１であるからｆ２はＸ２、Ｘ３との間のみ辺で結ぶ。
【０１０４】
次に、ステップ５０８で、上記ステップ５０６で作成したファクターグラフに基づき、ｓｕｍ−ｐｒｏｄｕｃｔ法を用いて復号し、Ｙ２を得て、復号処理を終了する。
【０１０５】
従来法で用いるファクターグラフである図７の例では、右側の変数ノードｐ１、ｐ２、ｐ３の値として、前述のとおりｐ（ｙ２＝１｜ｙ１（ｔ））の値を用いている。一方、本実施の形態では、これらの値としてｐ（ｙ２＝１｜ｚ１（ｔ），ｚ２（ｔ））を用いている。この結果、図７ではｐ２＝ｐ３となっているが、図６ではｐ１、ｐ２、ｐ３とも異なる数値となっている。このようにｐ（Ｙ２｜Ｙ１’）の値を用いることで、ｐｉの数字のバリエーションが豊富になる。このことが、ｓｕｍ−ｐｒｏｄｕｃｔ法による復号性能を向上させ、結果的により高い圧縮率で圧縮することを可能にする。
【０１０６】
なお、上記実施の形態では、情報源が二つの場合について説明したが、情報源が三つ以上の場合にも適用可能である。情報源がｋ個あり、Ｗ１≦Ｗ２≦・・・≦Ｗｉ−１≦Ｗｉ≦・・・≦Ｗｋであるとき、通信レートを次の条件を満たすように決める。
【０１０７】
【数１８】
0005642651.tif 000019
【０１０８】
このとき、Ｙ１及びＹ２に関する処理手順は、情報源が二つの場合と同じである。Ｙｉについては以下の処理を行う。
１．初期化処理の段階で、予めｐ（Ｙｉ｜Ｙｉ−１’，Ｙｉ−２’，・・・，Ｙ１’）を計算し、復号装置５０に保存しておく。
２．復号装置５０は予め保存しておいたｐ（Ｙｉ｜Ｙｉ−１’，Ｙｉ−２’，・・・，Ｙ１’）及び検査行列Ａ２と、Ｙｉ−１’，Ｙｉ−２’，・・・，Ｙ１’と、ｃ（Ｙｉ）とを用いてファクターグラフを作る。
３．ファクターグラフに基づき、ｓｕｍ−ｐｒｏｄｕｃｔ法を用いて復号し、Ｙｉを得る。
【０１０９】
この処理をｃ（Ｙ３）に適用すると、復号されたＹ３が得られる。このＹ３と、すでに復号済のＹ１、Ｙ２、及びｃ（Ｙ４）を用いて上記の処理を行うことで、Ｙ４を復号できる。以下、同様にＹｉ−１までの復号結果とｃ（Ｙｉ）とを用いて、Ｙｉの復号を行うことができる。
【０１１０】
以上説明したように、本実施の形態のセンサネットワークシステムによれば、デジタル信号の系列を平均情報量が低下するように前処理を行ってから符号化すること、及びＳｌｅｐｉａｎ−Ｗｏｌｆ理論に基づく通信レートの設定に必要な条件付き平均情報量を低下させることにより、複数の情報源が出力するデジタル信号をＳｌｅｐｉａｎ−Ｗｏｌｆ理論に基づきＬＤＰＣ符号またはＬＤＰＣ−ＣＣ符号を用いて符号化及び復号を行う場合において、圧縮率を高めることができる。
【０１１１】
なお、本発明は、上述した実施形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【０１１２】
また、本願明細書中において、プログラムが予めインストールされている実施形態として説明したが、当該プログラムを、コンピュータ読み取り可能な記録媒体に格納して提供することも可能である。
【符号の説明】
【０１１３】
１     符号化復号システム
１１、１２    観測装置
２１、２２    符号化装置
３１、３２    送信装置
４０   受信装置
５０   復号装置
【図１】
0005642651.tif 000020
【図２】
0005642651.tif 000021
【図３】
0005642651.tif 000022
【図４】
0005642651.tif 000023
【図５】
0005642651.tif 000024
【図６】
0005642651.tif 000025
【図７】
0005642651.tif 000026