(57)【要約】【課題】情報源からのデジタル信号が、非定常性が高いデジタル信号であっても、デジタル信号がもつ非定常性が符号化レートに与える影響を抑制することができるようにする。【解決手段】デジタル信号の系列ＸiをＸi（Ｕ）とＸi（Ｖ）とに分割したときの系列Ｘi（Ｕ）に対して符号装置１４により可逆圧縮符号化を行って生成された符号語ψ（Ｘi（Ｕ））を、復号装置１６によってＸi（Ｕ）に復号する。エントロピー計算部３６によって、暗号データ記憶部３２に記憶された、Ｘiと時区間の長さが同じ系列Ｘjを分割して得られるＸj（Ｕ’）に基づく条件付きエントロピーＨ（Ｘi（Ｕ）｜Ｘj（Ｕ’））を算出し、Ｈ（Ｘi（Ｕ）｜Ｘj（Ｕ’））の最小値に基づいて、ＬＤＰＣ行列の行列サイズを決定する。第２復号化部３８によって、ＬＤＰＣ行列及び補助情報を用いて符号語φ（Ｘi（Ｖ））を、Ｘi（Ｖ）に復号する。【選択図】図１
2014220713.tif 000002
【特許請求の範囲】
【請求項１】
通信部と、
情報源から出力されたデジタル信号の系列Ｘiを、第１の系列Ｘi（Ｕ）と第２の系列Ｘi（Ｖ）とに分割する分割部と、
前記分割部による分割により得られた前記第１の系列Ｘi（Ｕ）に対して、可逆圧縮符号化を行って、第１符号化データを生成し、前記生成された前記第１符号化データを、前記情報源又は他の情報源から出力されたデジタル信号の系列Ｘjを分割して得られる前記第１の系列Ｘj（Ｕ）と前記第１の系列Ｘi（Ｕ）とに基づく条件付きエントロピーＨ（Ｘi（Ｕ）｜Ｘj（Ｕ））を計算するために、前記通信部を用いて復号装置へ送信する第１符号化部と、
前記分割部による分割により得られた前記第２の系列Ｘi（Ｖ）に対して、前記条件付きエントロピーＨ（Ｘi（Ｕ）｜Ｘj（Ｕ））の計算結果に基づいて行列サイズが決定されたＬＤＰＣ（Low Density Parity Check）行列を用いて圧縮符号化を行って、第２符号化データを生成し、前記生成された前記第２符号化データを、前記通信部を用いて前記復号装置へ送信する第２符号化部と、
を含む符号装置。
【請求項２】
前記分割部は、予め定められた自然数ｋを用いて、前記デジタル信号の系列Ｘiから、ｋｎ番目の要素（ｎ＝１，…，ｌ）を集めた前記第１の系列Ｘi（Ｕ）と、前記ｋｎ番目の要素（ｎ＝１，…，ｌ）以外の要素を集めた前記第２の系列Ｘi（Ｖ）とに分割する請求項１記載の符号装置。
【請求項３】
前記分割部は、前記デジタル信号の系列Ｘiから、予め定められた複数の要素を集めた前記第１の系列Ｘi（Ｕ）と、前記予め定められた複数の要素以外の要素を集めた前記第２の系列Ｘi（Ｖ）とに分割する請求項１記載の符号装置。
【請求項４】
前記分割部は、自然数を出力する予め定められた関数ｆ（ｚ）を用いて、前記デジタル信号の系列Ｘiから、ｆ（ｚ）番目の要素（ｚ＝１，２，…）を集めた前記第１の系列Ｘi（Ｕ）と、前記ｆ（ｚ）番目の要素（ｚ＝１，２，…）以外の要素を集めた前記第２の系列Ｘi（Ｖ）とに分割する請求項１記載の符号装置。
【請求項５】
前記第１符号化部は、前記分割部による分割により得られた前記第１の系列Ｘi（Ｕ）に対して、ハフマン符号、算術符号、ブロックソーティング法、ＰＰＭ（Prediction by Partial Matching）法、ＣＳＥ（Compression by Substring Enumeration）法、ＬＺＷ（Lempel Ziv Welch）法、ランレングス符号、及びＬＺ（Lempel Ziv）７７符号の少なくとも１つを用いた可逆圧縮符号化を行って、前記第１符号化データを生成する請求項１〜請求項４の何れか１項記載の符号装置。
【請求項６】
前記情報源から出力されたデジタル信号の系列Ｘiを変調する変調部を更に含み、
前記分割部は、前記変調部によって変調された前記デジタル信号の系列Ｘiを、前記第１の系列Ｘi（Ｕ）と前記第２の系列Ｘi（Ｖ）とに分割する請求項１〜請求項５の何れか１項記載の符号装置。
【請求項７】
前記変調部は、前記情報源から出力されたデジタル信号の系列Ｘiに対して、時間差分、離散フーリエ変換、及びウェーブレット変換の何れか一つを行って、前記デジタル信号の系列Ｘiを変調する請求項６記載の符号装置。
【請求項８】
通信部と、
複数の情報源の各々について過去に復号された前記デジタル信号の系列を記憶する記憶部と、
前記通信部により符号装置から受信した、前記情報源から出力されたデジタル信号の系列Ｘiのうちの第１の系列Ｘi（Ｕ）に対して可逆圧縮符号化を行って生成された第１符号化データψ（Ｘi（Ｕ））を、前記第１の系列Ｘi（Ｕ）に復号する第１復号化部と、
前記第１符号化部によって得られた前記第１の系列Ｘi（Ｕ）と、前記記憶部に記憶された、前記デジタル信号の系列Ｘiと時区間の長さが同じ前記デジタル信号の系列Ｘjのうちの前記第１の系列Ｘj（Ｕ’）とに基づく条件付きエントロピーＨ（Ｘi（Ｕ）｜Ｘj（Ｕ’））を、前記記憶部に記憶された前記デジタル信号の系列Ｘjの各々について算出し、前記条件付きエントロピーＨ（Ｘi（Ｕ）｜Ｘj（Ｕ’））の最小値に基づいて、ＬＤＰＣ行列の行列サイズを決定し、前記決定した前記行列サイズを、前記第１符号化データψ（Ｘi（Ｕ））を送信した前記符号装置へ前記通信部を用いて送信するエントロピー計算部と、
前記決定した前記行列サイズのＬＤＰＣ行列を用いると共に、前記条件付きエントロピーＨ（Ｘi（Ｕ）｜Ｘj（Ｕ’））の最小値に対応する前記デジタル信号の系列Ｘjを補助情報として用いて、前記通信部により前記符号装置から受信した、前記決定した前記行列サイズのＬＤＰＣ行列を用いて前記デジタル信号の系列Ｘiのうちの第２の系列Ｘi（Ｖ）に対して圧縮符号化を行って生成された第２符号化データφ（Ｘi（Ｖ））を、前記第１の系列Ｘi（Ｖ）に復号する第２復号化部と、
前記第１復号化部によって復号された前記第１の系列Ｘi（Ｕ）と、前記第２復号化部によって復号された前記第１の系列Ｘi（Ｖ）とを連結して、前記第１の系列Ｘiを生成して出力する出力部と、
を含む復号装置。
【請求項９】
前記エントロピー計算部は、前記第１符号化部によって得られた前記第１の系列Ｘi（Ｕ）と、前記記憶部に記憶された、前記デジタル信号の系列Ｘiと時区間の長さが同じ複数の前記デジタル信号の系列Ｘj,1、・・・、Ｘj,kの各々のうちの前記第１の系列Ｘj,1（Ｕ’）、・・・、Ｘj,k（Ｕ’）とに基づく条件付きエントロピーＨ（Ｘi（Ｕ）｜Ｘj,1（Ｕ’）、・・・、Ｘj,k（Ｕ’））を、前記記憶部に記憶された前記デジタル信号の系列Ｘj,1、・・・、Ｘj,kの組み合わせの各々について算出し、前記条件付きエントロピーＨ（Ｘi（Ｕ）｜Ｘj,1（Ｕ’）、・・・、Ｘj,k（Ｕ’））の最小値に基づいて、ＬＤＰＣ行列の行列サイズを決定し、
前記第２復号化部は、前記条件付きエントロピーＨ（Ｘi（Ｕ）｜Ｘj,1（Ｕ’）、・・・、Ｘj,k（Ｕ’））の最小値に対応する前記デジタル信号の系列Ｘj,1、・・・、Ｘj,kの組み合わせを補助情報として用いて、前記符号装置から受信した第２符号化データφ（Ｘi（Ｖ））を、前記第１の系列Ｘi（Ｖ）に復号する請求項８記載の復号装置。
【請求項１０】
前記第１復号化部は、前記通信部により符号装置から受信した、前記第１の系列Ｘi（Ｕ）に対して、ハフマン符号、算術符号、ブロックソーティング法、ＰＰＭ（Prediction by Partial Matching）法、ＣＳＥ（Compression by Substring Enumeration）法、ＬＺＷ（Lempel Ziv Welch）法、ランレングス符号、及びＬＺ（Lempel Ziv）７７符号の少なくとも１つを用いた可逆圧縮符号化を行って生成された第１符号化データψ（Ｘi（Ｕ））を、前記第１の系列Ｘi（Ｕ）に復号する請求項８又は９記載の復号装置。
【請求項１１】
前記第２復号化部は、前記ＬＤＰＣ行列及び前記補助情報を用いて、前記符号装置から受信した第２符号化データφ（Ｘi（Ｖ））を、ｓｕｍ−ｐｒｏｄｕｃｔ法及び線形計画（ＬＰ）復号法の何れか一方により、前記第１の系列Ｘi（Ｖ）に復号する請求項８〜請求項１０の何れか１項記載の復号装置。
【請求項１２】
前記第１復号化部は、前記通信部により符号装置から受信した、前記情報源から出力され、かつ、変調された前記デジタル信号の系列Ｘiを前記第１の系列Ｘi（Ｕ）と前記第２の系列Ｘi（Ｖ）とに分割したときの前記第１の系列Ｘi（Ｕ）に対して、可逆圧縮符号化を行って生成された前記第１符号化データψ（Ｘi（Ｕ））を、前記第１の系列Ｘi（Ｕ）に復号し、
前記出力部は、前記第１復号化部によって復号された前記第１の系列Ｘi（Ｕ）と、前記第２復号化部によって復号された前記第１の系列Ｘi（Ｖ）とを連結して、前記第１の系列Ｘiを生成し、前記生成した前記第１の系列Ｘiを逆変調して出力する請求項８〜請求項１１の何れか１項記載の復号装置。
【請求項１３】
分割部によって、情報源から出力されたデジタル信号の系列Ｘiを、第１の系列Ｘi（Ｕ）と第２の系列Ｘi（Ｖ）とに分割し、
第１符号化部によって、前記分割部による分割により得られた前記第１の系列Ｘi（Ｕ）に対して、可逆圧縮符号化を行って、第１符号化データを生成し、
通信部によって、前記第１符号化部によって生成された前記第１符号化データを、前記情報源又は他の情報源から出力されたデジタル信号の系列Ｘjを分割して得られる前記第１の系列Ｘj（Ｕ）と前記第１の系列Ｘi（Ｕ）とに基づく条件付きエントロピーＨ（Ｘi（Ｕ）｜Ｘj（Ｕ））を計算するために、復号装置へ送信し、
第２符号化部によって、前記分割部による分割により得られた前記第２の系列Ｘi（Ｖ）に対して、前記条件付きエントロピーＨ（Ｘi（Ｕ）｜Ｘj（Ｕ））の計算結果に基づいて行列サイズが決定されたＬＤＰＣ（Low Density Parity Check）行列を用いて圧縮符号化を行って、第２符号化データを生成し、
前記通信部によって、前記第２符号化部によって生成された前記第２符号化データを、前記復号装置へ送信する
符号方法。
【請求項１４】
複数の情報源の各々について過去に復号されたデジタル信号の系列を記憶する記憶部を備えた復号装置における復号方法であって、
通信部によって、前記情報源から出力されたデジタル信号の系列Ｘiのうちの第１の系列Ｘi（Ｕ）に対して、可逆圧縮符号化を行って生成された第１符号化データψ（Ｘi（Ｕ））を符号装置から受信し、
第１復号化部によって、前記符号装置から受信した第１符号化データψ（Ｘi（Ｕ））を、前記第１の系列Ｘi（Ｕ）に復号し、
エントロピー計算部によって、前記第１符号化部によって得られた前記第１の系列Ｘi（Ｕ）と、前記記憶部に記憶された、前記デジタル信号の系列Ｘiと時区間の長さが同じ前記デジタル信号の系列Ｘjのうちの前記第１の系列Ｘj（Ｕ’）とに基づく条件付きエントロピーＨ（Ｘi（Ｕ）｜Ｘj（Ｕ’））を、前記記憶部に記憶された前記デジタル信号の系列Ｘjの各々について算出し、前記条件付きエントロピーＨ（Ｘi（Ｕ）｜Ｘj（Ｕ’））の最小値に基づいて、ＬＤＰＣ行列の行列サイズを決定し、
前記通信部によって、前記エントロピー計算部によって決定した前記行列サイズを、前記第１符号化データψ（Ｘi（Ｕ））を送信した前記符号装置へ送信し、
前記通信部によって、前記決定した前記行列サイズのＬＤＰＣ行列を用いて前記デジタル信号の系列Ｘiのうちの第２の系列Ｘi（Ｖ）に対して圧縮符号化を行って生成された第２符号化データφ（Ｘi（Ｖ））を前記符号装置から受信し、
第２復号化部によって、前記決定した前記行列サイズのＬＤＰＣ行列を用いると共に、前記条件付きエントロピーＨ（Ｘi（Ｕ）｜Ｘj（Ｕ’））の最小値に対応する前記デジタル信号の系列Ｘjを補助情報として用いて、前記符号装置から受信した第２符号化データφ（Ｘi（Ｖ））を、前記第１の系列Ｘi（Ｖ）に復号し、
出力部によって、前記第１復号化部によって復号された前記第１の系列Ｘi（Ｕ）と、前記第２復号化部によって復号された前記第１の系列Ｘi（Ｖ）とを連結して、前記第１の系列Ｘiを生成して出力する
復号方法。
【請求項１５】
請求項１〜請求項７の何れか１項に記載の符号装置を構成する各部として、コンピュータを機能させることを特徴とするプログラム。
【請求項１６】
請求項８〜請求項１２の何れか１項に記載の復号装置を構成する各部として、コンピュータを機能させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の情報源の各々から出力されたデジタル信号の系列に対して符号化を行う符号装置、方法、及びプログラム、並びに、復号化を行う復号装置、方法、及びプログラムに関する。
【背景技術】
【０００２】
センサネットワークは、複数のセンサで観測したデータ(デジタル信号)を、集積サーバまで無線通信を用いて送信するネットワークである。センサネットワークを構成するセンサノードは、搭載するバッテリ容量が小さいことから、通信にかかるコストを削減し、バッテリの使用量、すなわち消費電力を削減することが重要な技術的課題となっている。通信コストの削減方法のひとつとして、符号化手法を用いてデータの圧縮を行う方法が用いられる。センサネットワークでは、センサノードを情報源とみなすと、複数の情報源で符号化を行い、ひとつの集積サーバで復号を行う通信路と見ることができる。このような、複数の情報源が存在する通信路における、符号化レートの下限を与える研究としてSlepianとWolfの示した理論(非特許文献１を参照)がある。これは、複数の情報源が出力するデジタル信号に対し、それぞれのデジタル信号を分散符号化した場合において、無歪状態で復号できる符号化レート領域を与えたものである。この理論が与える符号化レートを実現できる符号としてLDPC符号がある。
【０００３】
以下、このSlepianらの示した理論とLDPC符号の説明に必要な記号と用語の定義を行う。p個の情報源をX1,...,Xpとする。情報源の出力するデジタル信号は、量子化されて離散的な値をとるものとする。情報源Xiの出力するデジタル信号の平均情報量をH(Xi)とする。p個全ての情報源の平均情報量の和はΣpi=1H(Xi)である。Slepian-Wolf Codingを用いず、各情報源毎に符号化を行い、集積サーバでそれぞれの情報源から得た符号を無歪で復号する場合、情報源Xiと集積サーバ間に必要な符号化レートRiはRi=H(Xi)で与えられる。情報源Xiがセンサノードであり、１ビットのデジタル信号を集積サーバまで無線通信を用いてデータの送受信を行う場合の消費電力（単位消費電力）をWiとする。このとき、各センサノードが観測するデータを集積サーバまで送信するための、平均通信コストCiはCi=Ri×Wiで与えられる。このとき、センサネットワーク全体の平均通信コストの総和はΣpi=1Ci=Σpi=1H(Xi)×Wiで与えられる。
【０００４】
なお、単位消費電力Wiはセンサノードのハードウェア、およびセンサノードと集積サーバ間の無線通信距離に依存する値であり、物理的に決定される値である。以降、説明を簡単にするために、列挙するセンサノードの順序は、それらの単位消費電力について昇順に並んでいるものとする。すなわち、ふたつのセンサノードXi,Xjについてi<jであればWi≦Wjである。すべてのセンサノードに対してSlepianらの理論に基づき設計した通信路で符号化を行う場合で、なおかつW=W1=W2=...=Wpであるとき、 センサネットワーク全体の平均通信コストの総和は、次の式で与えられる(非特許文献１を参照)。
【０００５】
W×ｐ×H（X１,X2,...,Xp）
【０００６】
さらに、W1<W2<Wpであるとき、Liuらによってセンサネットワーク全体の平均通信コストの総和は次式で与えられることが示されている(非特許文献２を参照)。
【０００７】
【数１】
2014220713.tif 000003
【０００８】
各Xiについて、明らかにH(Xi|Xi-1,Xi-2,...,X1)<H(Xi)であることから、複数の情報源のデジタル信号を同時に圧縮したほうが、平均通信コストの総和が小さくなる。通信コストの総和が低いほど、電力消費量は下がる。すなわち当該理論に基づき符号化を行いデータの圧縮をすることで、従来よりバッテリ消費量を低減できる。
【０００９】
また、Slepian-Wolf CodingとLDPC-CC符号を用いて複数の情報源のデータを圧縮する方法が知られている（特許文献１）。
【先行技術文献】
【特許文献】
【００１０】
【特許文献１】特開2012-054989号公報
【非特許文献】
【００１１】
【非特許文献１】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)。
【発明の概要】
【発明が解決しようとする課題】
【００１２】
上記の特許文献１には、デジタル信号の非定常性に起因する、符号化レートが増大する問題に対する解決法は記述されていない。
【００１３】
また、情報源の数が二つ以上のときに、観測したデジタル信号に対して、LDPC符号を用いて符号化および復号を行う場合において、符号化レートとして理論的に求められる値を使用した場合、復号したデジタル信号に歪みが発生する可能性がある。歪みなくデジタル信号を復号するためには、理論的に計算される値よりも、大きな符号化レートを用いる必要がある。しかし、大きな符号化レートを用いると、圧縮性能が低下するという問題が生じる。この問題について説明する。
【００１４】
＜データの非定常性に起因する問題＞
情報源がp個存在し、それぞれの情報源をX1,...,Xpとする。情報源Xiが出力する、時区間T=[t,t+1,t+2,...,t+n-1]のデジタル信号の系列をXi(T)とする。以降、記述の簡易化のためにXi(T)を単にXiと表記し、デジタル信号の系列を単に「デジタル信号」を表記する。LDPC符号を用いてXi(T)を符号化して得た符号語をφ(Xi)と表記する。情報源XiにおいてLDPCの符号化に用いる検査行列Aのサイズをm×n(m行n列)とする。nはデジタル信号の長さであり、固定の値である。情報源Xiの検査行列の行の数miは次の条件を満たすように決定される。
【００１５】
【数２】
2014220713.tif 000004
【００１６】
条件付きエントロピーH(Xi|Xi-1,Xi-2,..., X1)が、圧縮しようとするデジタル信号に対して一定である場合、すなわちデジタル信号中に出現するシンボルの生起確率の定常性が仮定できる場合においてのみ、上記（１）式で与えられる符号化レートは、歪みなく復号ができる下限値を示している。しかし、現実のセンサから観測されるデータに含まれるシンボルの生起確率について、定常性を仮定することは難しい。定常性が保証されないデジタル信号に対しては、上記（１）式で与えられる符号化レートRiで信号を送信した場合であっても、歪みなく復号できることは保証されない。データに含まれるシンボルの生起確率について、定常性を仮定することは難しい現実のデータの符号化データを歪みなく復号できるようにするためには、条件付きエントロピーH(Xi|Xi-1,Xi-2,...,X1)の変動に対応できるように、符号化レートを上記（１）式で与えられるRiよりも高く設定する必要がある。
【００１７】
具体的には、符号化レートがH(Xi|Xi-1,Xi-2,...,X1)よりも小さく設定された場合は、復号器がXiを誤って復号する確率が極めて大きくなる。符号化レートの増大を防ぐためには、H(Xi|Xi|Xi-2,...,X1)が小さくなることが好ましい。
【００１８】
＜データ間の同時性が保証されない問題＞
LDPC符号では、符号化されたデジタル信号φ(Xi(T))の復号時に、補助情報としてXi-1(T);Xi-2(T),...,X1(T)を用いる。しかし、同じ時区間Tに取得したそれぞれのデジタル信号Xi(T),Xi-1(T),Xi-2(T),...,X1(T)について、必ずしも相関性が高い、すなわち条件付きエントロピーH(Xi|Xi-1,Xi-2,...,X1)が低い値となるとは限らない。これは、たとえばデジタル信号の観測時に機械的な時差が生じる場合や、観測する信号が空間上をゆるやかに伝播するため、相関性が時差を伴って現れる場合などがあるからである。
【００１９】
このような、データの同時性が保証されない場合は、同じ時区間のデジタル信号を補助情報として用いても、小さな符号化レートが得られないことがある。
【００２０】
本発明は、情報源からのデジタル信号が、非定常性が高いデジタル信号であっても、デジタル信号がもつ非定常性が符号化レートに与える影響を抑制することができる符号装置、復号装置、方法、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００２１】
上記の目的を達成するために第１の発明に係る符号装置は、通信部と、情報源から出力されたデジタル信号の系列Ｘiを、第１の系列Ｘi（Ｕ）と第２の系列Ｘi（Ｖ）とに分割する分割部と、前記分割部による分割により得られた前記第１の系列Ｘi（Ｕ）に対して、可逆圧縮符号化を行って、第１符号化データを生成し、前記生成された前記第１符号化データを、前記情報源又は他の情報源から出力されたデジタル信号の系列Ｘjを分割して得られる前記第１の系列Ｘj（Ｕ）と前記第１の系列Ｘi（Ｕ）とに基づく条件付きエントロピーＨ（Ｘi（Ｕ）｜Ｘj（Ｕ））を計算するために、前記通信部を用いて復号装置へ送信する第１符号化部と、前記分割部による分割により得られた前記第２の系列Ｘi（Ｖ）に対して、前記条件付きエントロピーＨ（Ｘi（Ｕ）｜Ｘj（Ｕ））の計算結果に基づいて行列サイズが決定されたＬＤＰＣ（Low Density Parity Check）行列を用いて圧縮符号化を行って、第２符号化データを生成し、前記生成された前記第２符号化データを、前記通信部を用いて前記復号装置へ送信する第２符号化部と、を含んで構成されている。
【００２２】
第２の発明に係る符号方法は、分割部によって、情報源から出力されたデジタル信号の系列Ｘiを、第１の系列Ｘi（Ｕ）と第２の系列Ｘi（Ｖ）とに分割し、第１符号化部によって、前記分割部による分割により得られた前記第１の系列Ｘi（Ｕ）に対して、可逆圧縮符号化を行って、第１符号化データを生成し、通信部によって、前記第１符号化部によって生成された前記第１符号化データを、前記情報源又は他の情報源から出力されたデジタル信号の系列Ｘjを分割して得られる前記第１の系列Ｘj（Ｕ）と前記第１の系列Ｘi（Ｕ）とに基づく条件付きエントロピーＨ（Ｘi（Ｕ）｜Ｘj（Ｕ））を計算するために、復号装置へ送信し、第２符号化部によって、前記分割部による分割により得られた前記第２の系列Ｘi（Ｖ）に対して、前記条件付きエントロピーＨ（Ｘi（Ｕ）｜Ｘj（Ｕ））の計算結果に基づいて行列サイズが決定されたＬＤＰＣ（Low Density Parity Check）行列を用いて圧縮符号化を行って、第２符号化データを生成し、前記通信部によって、前記第２符号化部によって生成された前記第２符号化データを、前記復号装置へ送信する。
【００２３】
第３の発明に係る復号装置は、通信部と、複数の情報源の各々について過去に復号された前記デジタル信号の系列を記憶する記憶部と、前記通信部により符号装置から受信した、前記情報源から出力されたデジタル信号の系列Ｘiのうちの第１の系列Ｘi（Ｕ）に対して可逆圧縮符号化を行って生成された第１符号化データψ（Ｘi（Ｕ））を、前記第１の系列Ｘi（Ｕ）に復号する第１復号化部と、前記第１符号化部によって得られた前記第１の系列Ｘi（Ｕ）と、前記記憶部に記憶された、前記デジタル信号の系列Ｘiと時区間の長さが同じ前記デジタル信号の系列Ｘjのうちの前記第１の系列Ｘj（Ｕ’）とに基づく条件付きエントロピーＨ（Ｘi（Ｕ）｜Ｘj（Ｕ’））を、前記記憶部に記憶された前記デジタル信号の系列Ｘjの各々について算出し、前記条件付きエントロピーＨ（Ｘi（Ｕ）｜Ｘj（Ｕ’））の最小値に基づいて、ＬＤＰＣ行列の行列サイズを決定し、前記決定した前記行列サイズを、前記第１符号化データψ（Ｘi（Ｕ））を送信した前記符号装置へ前記通信部を用いて送信するエントロピー計算部と、前記決定した前記行列サイズのＬＤＰＣ行列を用いると共に、前記条件付きエントロピーＨ（Ｘi（Ｕ）｜Ｘj（Ｕ’））の最小値に対応する前記デジタル信号の系列Ｘjを補助情報として用いて、前記通信部により前記符号装置から受信した、前記決定した前記行列サイズのＬＤＰＣ行列を用いて前記デジタル信号の系列Ｘiのうちの第２の系列Ｘi（Ｖ）に対して圧縮符号化を行って生成された第２符号化データφ（Ｘi（Ｖ））を、前記第１の系列Ｘi（Ｖ）に復号する第２復号化部と、前記第１復号化部によって復号された前記第１の系列Ｘi（Ｕ）と、前記第２復号化部によって復号された前記第１の系列Ｘi（Ｖ）とを連結して、前記第１の系列Ｘiを生成して出力する出力部と、を含んで構成されている。
【００２４】
第４の発明に係る復号方法は、複数の情報源の各々について過去に復号されたデジタル信号の系列を記憶する記憶部を備えた復号装置における復号方法であって、通信部によって、前記情報源から出力されたデジタル信号の系列Ｘiのうちの第１の系列Ｘi（Ｕ）に対して、可逆圧縮符号化を行って生成された第１符号化データψ（Ｘi（Ｕ））を符号装置から受信し、第１復号化部によって、前記符号装置から受信した第１符号化データψ（Ｘi（Ｕ））を、前記第１の系列Ｘi（Ｕ）に復号し、エントロピー計算部によって、前記第１符号化部によって得られた前記第１の系列Ｘi（Ｕ）と、前記記憶部に記憶された、前記デジタル信号の系列Ｘiと時区間の長さが同じ前記デジタル信号の系列Ｘjのうちの前記第１の系列Ｘj（Ｕ’）とに基づく条件付きエントロピーＨ（Ｘi（Ｕ）｜Ｘj（Ｕ’））を、前記記憶部に記憶された前記デジタル信号の系列Ｘjの各々について算出し、前記条件付きエントロピーＨ（Ｘi（Ｕ）｜Ｘj（Ｕ’））の最小値に基づいて、ＬＤＰＣ行列の行列サイズを決定し、前記通信部によって、前記エントロピー計算部によって決定した前記行列サイズを、前記第１符号化データψ（Ｘi（Ｕ））を送信した前記符号装置へ送信し、前記通信部によって、前記決定した前記行列サイズのＬＤＰＣ行列を用いて前記デジタル信号の系列Ｘiのうちの第２の系列Ｘi（Ｖ）に対して圧縮符号化を行って生成された第２符号化データφ（Ｘi（Ｖ））を前記符号装置から受信し、第２復号化部によって、前記決定した前記行列サイズのＬＤＰＣ行列を用いると共に、前記条件付きエントロピーＨ（Ｘi（Ｕ）｜Ｘj（Ｕ’））の最小値に対応する前記デジタル信号の系列Ｘjを補助情報として用いて、前記符号装置から受信した第２符号化データφ（Ｘi（Ｖ））を、前記第１の系列Ｘi（Ｖ）に復号し、出力部によって、前記第１復号化部によって復号された前記第１の系列Ｘi（Ｕ）と、前記第２復号化部によって復号された前記第１の系列Ｘi（Ｖ）とを連結して、前記第１の系列Ｘiを生成して出力する。
【００２５】
第５の発明に係るプログラムは、上記の符号装置の各部としてコンピュータを機能させるためのプログラムである。
【００２６】
第６の発明に係るプログラムは、上記の復号装置の各部としてコンピュータを機能させるためのプログラムである。
【発明の効果】
【００２７】
本発明に係る符号装置、方法、及びプログラムによれば、情報源から出力されたデジタル信号の系列Ｘiのうちの第１の系列Ｘi（Ｕ）に対して、可逆圧縮符号化を行って、第１符号化データを生成し、情報源又は他の情報源から出力されたデジタル信号の系列Ｘjのうちの第１の系列Ｘj（Ｕ）と第１の系列Ｘi（Ｕ）とに基づく条件付きエントロピーＨ（Ｘi（Ｕ）｜Ｘj（Ｕ））に基づいて行列サイズが決定されたＬＤＰＣ行列を用いて、第１の系列Ｘi（Ｖ）に対して圧縮符号化を行って、第２符号化データを生成することにより、情報源からのデジタル信号が、非定常性が高いデジタル信号であっても、デジタル信号がもつ非定常性が符号化レートに与える影響を抑制することができる。
【００２８】
本発明に係る復号装置、方法、及びプログラムによれば、情報源から出力されたデジタル信号の系列Ｘiのうちの第１の系列Ｘi（Ｕ）に対して可逆圧縮符号化を行って生成された第１符号化データψ（Ｘi（Ｕ））を第１の系列Ｘi（Ｕ）に復号し、記憶部に記憶された、デジタル信号の系列Ｘiと時区間の長さが同じデジタル信号の系列Ｘjのうちの第１の系列Ｘj（Ｕ’）に基づく条件付きエントロピーＨ（Ｘi（Ｕ）｜Ｘj（Ｕ’））を算出し、条件付きエントロピーＨ（Ｘi（Ｕ）｜Ｘj（Ｕ’））の最小値に基づいて、ＬＤＰＣ行列の行列サイズを決定し、決定した行列サイズのＬＤＰＣ行列を用いて第２の系列Ｘi（Ｖ）に対して圧縮符号化を行って生成された第２符号化データφ（Ｘi（Ｖ））を、第１の系列Ｘi（Ｖ）に復号することにより、情報源からのデジタル信号が、非定常性が高いデジタル信号であっても、デジタル信号がもつ非定常性が符号化レートに与える影響を抑制することができる。
【図面の簡単な説明】
【００２９】
【図１】本発明の第１の実施の形態に係るセンサネットワークシステムの構成を示す概略図である。
【図２】本発明の第１の実施の形態に係る符号装置における符号化処理ルーチンの内容を示すフローチャートである。
【図３】デジタル信号の系列の分割方法を説明するための図である。
【図４】本発明の第１の実施の形態に係る暗号装置における符号化処理ルーチンの内容を示すフローチャートである。
【図５】本発明の第２の実施の形態に係るセンサネットワークシステムの構成を示す概略図である。
【発明を実施するための形態】
【００３０】
以下、図面を参照して本発明の実施の形態を詳細に説明する。
【００３１】
＜発明の概要＞
本実施の形態では、デジタル信号の条件付きエントロピーH(Xi|Xi-1,Xi-2,...,X1)を小さくするために、下記の（１）、（２）の手法を導入する。
【００３２】
（１）デジタル信号を、エントロピーを計算するために従来法で圧縮して送信するデータ列と、LDPC符号を用いて圧縮して送信するデータ列とに二分割する。
【００３３】
（２）LDPC符号で符号化された符号語を復号するときに、従来法で圧縮して送信されたデータを利用して、過去に受信したデータ列からもっとも条件付きエントロピーが小さくなるデータ列を検索し、そのデータ列を補助情報として用いて復号する。
【００３４】
＜システム構成＞
図１に示すように、本発明の第１の実施の形態に係るセンサネットワークシステム１０は、複数の観測装置１２、複数の符号装置１４、復号装置１６、及びネットワーク１８を備えている。なお、観測装置１２は、情報源の一例である。
【００３５】
複数の観測装置１２の各々は、対応する符号装置１４と接続されており、各符号装置１４は、ネットワーク１８に接続されている。復号装置１６と複数の符号装置１４とは、ネットワーク１８を介して相互に接続されている。
【００３６】
複数の観測装置１２の各々は、温度、湿度、照度、加速度、地磁気、ガス濃度、放射線量、イオン濃度、ＰＨなどの物理量を逐次観測し、観測した物理量をデジタル信号に変換し、符号装置１４へ逐次出力する。
【００３７】
符号装置１４は、観測装置１２から入力されたデジタル信号の系列を符号化する。符号装置１４は、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）と、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）と、後述する符号化処理ルーチンを実行するためのプログラムを記憶したＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）とを備えたコンピュータで構成され、機能的には次に示すように構成されている。図１に示すように、符号装置１４は、分割部２０、第１符号化部２２、第２符号化部２４、及び通信部２６を備えている。なお、通信部２６は、第１送信部及び第２送信部の一例である。
【００３８】
分割部２０は、観測装置１２から入力されたデジタル信号の系列を、２つのデジタル信号の系列に分割する。
【００３９】
第１符号化部２２は、分割された一方のデジタル信号の系列に対して、可逆圧縮が可能な符号化を行う。可逆圧縮手段としては、ハフマン符号、算術符号、ブロックソーティング法、PPM法、CSE法、LZW、ランレングス、LZ77などがある。第２符号化部２４は、少なくともLDPC符号化器を持ち、ＬＤＰＣ行列を用いて、分割された他方のデジタル信号の系列に対して符号化を行う。
【００４０】
通信部２６は、ネットワーク１８を介してデータの送受信を行う。通信は有線もしくは無線で行う。通信部２６は、第１符号化部２２によって符号化された符号語を、復号装置１６へ送信する。また、通信部２６は、第２符号化部２４によって符号化された符号語を、復号装置１６へ送信する。
【００４１】
復号装置１６は、各符号装置１４から送信された符号語を復号化し、デジタル信号の系列を出力する。復号装置１６は、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）と、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）と、後述する復号化処理ルーチンを実行するためのプログラムを記憶したＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）とを備えたコンピュータで構成され、機能的には次に示すように構成されている。図１に示すように、復号装置１６は、通信部３０、復号データ記憶部３２、第１復号化部３４、エントロピー計算部３６、第２復号化部３８、補助情報取得部４０、及び出力部４２を備えている。なお、通信部３０は、第１受信部、第２受信部、及び送信部の一例である。
【００４２】
通信部３０は、ネットワーク１８を介してデータの送受信を行う。通信は有線もしくは無線で行う。通信部３０は、各符号装置１４によって符号化された符号語を受信する。
【００４３】
復号データ記憶部３２は、複数の観測装置１２の各々について、過去に復号されたデジタル信号の系列を記憶している。
【００４４】
第１復号化部３４は、第１符号化部２２に対応する復号方法により、第１符号化部２２によって符号化された符号語に対して復号化を行い、分割により得られた一方のデジタル信号の系列に復号する。
【００４５】
エントロピー計算部３６は、第１復号化部３４によって復号されたデジタル信号の系列と、復号データ記憶部３２に記憶された各デジタル信号の系列とに基づいて、条件付きエントロピーを計算し、復号データ記憶部３２に記憶された各デジタル信号の系列から、条件付きエントロピーの最小値を与えるデジタル信号の系列を探索すると共に、条件付きエントロピーの最小値に基づいて、ＬＤＰＣ行列の大きさを決定する。エントロピー計算部３６は、探索した条件付きエントロピーの最小値を与えるデジタル信号の系列と、決定したＬＤＰＣ行列の大きさを、補助情報取得部４０へ出力する。
【００４６】
第２復号化部３８は、補助情報取得部４０によって取得した補助情報及びエントロピー計算部３６で決定された大きさに応じたＬＤＰＣ行列を用いて、LDPC符号の復号手段として、sum-product法により、第２符号化部２４によって符号化された符号に対して復号化を行い、分割により得られた他方のデジタル信号の系列に復号する。
【００４７】
補助情報取得部４０は、エントロピー計算部３６によって探索された、条件付きエントロピーの最小値を与えるデジタル信号の系列を、第２復号化部３８による復号で用いる補助情報として、復号データ記憶部３２から取得する。また、補助情報取得部４０は、エントロピー計算部３６で決定された大きさに応じたＬＤＰＣ行列を取得する。
【００４８】
出力部４２は、第１復号化部３４によって復号されたデジタル信号の系列と、第２復号化部３８によって復号されたデジタル信号の系列とを連結して出力すると共に、復号データ記憶部３２に格納する。
【００４９】
＜センサネットワークシステムの動作＞
次に、本実施の形態に係るセンサネットワークシステム１０の動作について説明する。
【００５０】
観測装置１２が観測したデジタル信号の系列を符号装置１４で符号化して符号語を生成し、ネットワーク１８を介して復号装置１６に符号語を送信し、復号装置１６で符号語をデジタル信号に歪みなく復号する手順について記述する。なお、復号装置１６の復号データ記憶部３２には予め長さnの時区間Tnの複数のデジタル信号の系列X={X1(Tn),X2(Tn),...Xi-1(Tn)}が保存されているとする。符号装置１４と復号装置１６は、あらかじめ各m,n(m,nは整数)に対応するm×nのLDPC行列をひとつずつ保持しているものとする。m×n行列をAと記す。
【００５１】
まず、観測装置１２が観測したデジタル信号の系列Xi(T)が、符号装置１４へ入力されると、符号装置１４において、図２に示す符号化処理ルーチンが実行される。以下、混乱のない限りXi(T)をXiと記述する。Xiの時区間の長さをn(nは自然数)とする。
【００５２】
まず、ステップＳ１００において、分割部２０は、観測装置１２から入力されたデジタル信号の系列Xiを取得する。そして、ステップＳ１０２において、分割部２０は、上記ステップＳ１００で取得したデジタル信号の系列Xiを二分割し、それぞれXi(U),Xi(V)(U,V⊂TかつU∩V=0（空集合）である)とする。Xi(U)の長さをnUとし、Xi(V)の長さをnVとする。nU+nV=nである。nU,nVの値は、あらかじめ決めておき、符号装置１４と復号装置１６で共有しておく。
【００５３】
本実施の形態では、以下のように、単純分割により、デジタル信号の系列Xiを二分割する。
【００５４】
自然数kを予め決めておく。たとえばT={1,2,...,n}であり、U={k,2k,3k,...，lk}であるとき、Vを、TのうちUに含まれていない要素をすべて含む集合とする。たとえばk=2であれば、図３に示すように、Xの要素のうち2,4,6,8,...番目の要素を集めたものがUであり、Xi(U)=(x2,x4,x6,...)である。このときXi(V)=(x1,x3,...)である。またk=5であれば、Tの要素のうち5,10,15,20,...番目の要素を集めたものをUとし、それ以外のT中の要素の集合をVとする。なお、V={xk,x2k,...}とし、Uを、Tの要素からVの要素をその除いた集合として使用してもよい。
【００５５】
そして、ステップＳ１０４において、第１符号化部２２は、上記ステップＳ１０２による分割で得られたデジタル信号の系列Xi(U)を符号化し、符号語ψ（Xi(U)）を得る。このとき利用する符号化器は、第１符号化部２２がもつ符号化器の中で最も大きな符号化レートで可逆圧縮ができる符号化器である。なお、符号語ψ（Xi(U)）が第１符号化データの一例である。
【００５６】
なお、第１符号化部２２は、Xi(U)を符号化した後の符号語ψ(Xi(U))の先頭、末尾、もしくはあらかじめ決められた位置に、符号化に使用した符号化器の種類を示す記号を付与するようにしてもよい。この場合、復号装置１６で当該の記号を識別し、復号に使用する復号器を選ぶ。
【００５７】
次のステップＳ１０６では、通信部２６によって、上記ステップＳ１０４で符号化された符号語ψ(Xi(U))を、ネットワーク１８を介して復号装置１６へ送信する。
【００５８】
ステップＳ１０８において、復号装置１６から、ＬＤＰＣ行列のサイズを示す変数ｍの値を受信したか否かを判定する。通信部２６により、復号装置１６から、変数ｍの値を受信すると、ステップＳ１１０へ進み、第２符号化部２４は、上記ステップＳ１０８で受信した変数ｍの値に基づいて、m,nVの値に対応するm×nV行列AVを選択し、行列AVを使って、上記ステップＳ１０２の分割により得られたデジタル信号の系列Xi(V)を符号化する。符号語はφ(Xi(V))=AVXi(V)で与えられる。R=m/nVが信号の符号化レートとなる。なお、なお、符号語φ(Xi(V))が第２符号化データの一例である。
【００５９】
そして、ステップＳ１１２において、通信部２６により、上記ステップＳ１１０で符号化された符号語φ(Xi(Ｖ))を、ネットワーク１８を介して復号装置１６へ送信して、符号化処理ルーチンを終了する。
【００６０】
また、復号装置１６において、符号装置１４から送信された、デジタル信号の系列Xi(U)を符号化した符号語ψ（Xi(U)）を受信すると、図４に示す復号化処理ルーチンが実行される。
【００６１】
ステップＳ１２０において、第１復号化部３４によって、符号装置１４から受信した、分割により得られた一方のデジタル信号の系列Xi(U)を符号化した符号語ψ（Xi(U)）から、第１符号化部２２に対応する復号方法により、分割により得られた一方のデジタル信号の系列Xi(U)を復号する。
【００６２】
そして、ステップＳ１２２では、エントロピー計算部３６によって、復号データ記憶部３２に記憶された複数のデジタル信号の系列から、デジタル信号の系列Xiと時区間の長さが同じ時区間ｎの複数のデジタル信号の系列の集合Ｘ={X1(Tn),X2(Tn),...Xi-1(Tn)}を取得する。そして、エントロピー計算部３６によって、上記ステップＳ１２０で得られたデジタル信号の系列Xi(U)と、取得したデジタル信号の系列Xj(Tn)を分割して得られる一方のデジタル信号の系列Xi(U’)とについて、条件付きエントロピーH(Xi(U)|Xj(U'))を計算し、集合Ｘの中から、arg minXj∈XH(Xi(U)|Xj(U'))となるような、長さnUのデジタル信号Xj(U')を探す。
【００６３】
なお、Xj(U)は、次の手順で生成される。
【００６４】
(a)  集合Xの中から、時区間の長さがデジタル信号の系列Xi の長さTと等しい時区間T'=[t',t',1,t'+2,...t'+n-1]であるようなデジタル信号Xj(T')をひとつ選択する。
【００６５】
(b)  Xj(T')を、それぞれ長さがU、Vと等しい時区間U'、V'に分割し、Xj(U'),Xj(V')を得る。|U'|=|U|=nU,|V'|=|V|=nV,U'∩V'＝0（空集合）である。分割の方法は、Xi(U),Xi(V)の分割方法と同様である。
【００６６】
そして、ステップＳ１２４において、エントロピー計算部３６は、上記ステップＳ１２２で計算された条件付きエントロピーH(Xi(U)|Xj(U'))の最小値に基づいて、m/nV≧（H(Xi(U)|Xj(U'))の最小値）を満足するようにmの値を選択し、選択したｍの値を、通信部３０により、ネットワーク１８を介して符号装置１４へ送信する。これによって、符号装置１４は、上記ステップＳ１１０において、デジタル信号の系列Xi(V)を符号化する。
【００６７】
ステップＳ１２６では、通信部３０により、上記ステップＳ１２４でｍの値を送信した送信先の符号装置１４から、分割により得られたデジタル信号の系列Xi(V)を符号化した符号語φ(Xi(V))を受信したか否かを判定する。符号装置１４から、符号語φ(Xi(V))を受信すると、ステップＳ１２８へ進み、補助情報取得部４０によって、上記ステップＳ１２２で計算された条件付きエントロピーH(Xi(U)|Xj(U'))の最小値を与えるデジタル信号の系列Xj(U')の元となるデジタル信号の系列Xj(T')を、復号データ記憶部３２から取得し、上記ステップＳ１２４で選択されたｍの値に基づくm×nV行列AVを用いると共に、取得したデジタル信号の系列Xj(T')を補助情報として用いて、上記ステップＳ１２６で受信した符号語φ(Xi(V))から、デジタル信号の系列X'i(V)を復号する。なお、補助情報として、条件付きエントロピーH(Xi(U)|Xj(U'))の最小値を与えるデジタル信号の系列Xj(U')を用いるようにしてもよい。
【００６８】
そして、ステップＳ１３０において、第２復号化部３８は、上記ステップＳ１２４で選択されたｍの値に基づくm×nV行列AVを用いて、上記ステップＳ１２８により復号されたデジタル信号の系列X'i(V)を符号化し、上記ステップＳ１２６で受信した符号語φ(Xi(V))と比較して、AVX'i(V)=φ(X'i(V))が成り立つかを検査することにより、復号に成功したか否かを判定する。AVX'i(V)=φ(X'i(V))が成り立つ場合、復号に成功したと判定し、X'i(V)を復元信号Xi(V)として、ステップＳ１３６へ移行する。一方、成り立たない場合、復号に失敗したと判定し、ステップＳ１３２において、通信部３０により、符号装置１４に対して、可逆圧縮ができる符号化器ψでXi(V)を符号化して再送するように要求する。
【００６９】
このとき、符号装置１４は、復号装置１６から上記の再送要求を受信すると、第１符号化部２２によって、分割により得られた一方のデジタル信号の系列Xi(U)の符号化と同様に、可逆圧縮法で、分割により得られた他方のデジタル信号の系列Xi(V)を符号化し、得られた符号語ψ(Xi(V))を、通信部２６を介して復号装置１６に送信する。
【００７０】
そして、ステップＳ１３４において、第１復号化部３４によって、符号装置１４から受信した符号語ψ（Xi(V)）から、第１符号化部２２に対応する復号方法により、分割により得られた他方のデジタル信号の系列Xi(V)を得る。
【００７１】
次のステップＳ１３６では、上記ステップＳ１２０で得られたデジタル信号の系列Xi(U)と、上記ステップＳ１２８又はステップＳ１３４で得られたデジタル信号の系列Xi(V)とを連結して、デジタル信号の系列Xi(T)を生成し、復号データ記憶部３２に格納すると共に、出力し、復号化処理ルーチンを終了する。
【００７２】
次に、上記ステップＳ１２８における補助情報を用いた復号方法について説明する。
【００７３】
補助情報を利用した情報源符号化では、符号器φに対して復号器を
【００７４】
【数３】
2014220713.tif 000005
【００７５】
で定義する。ここで、μXn|Ynは(Xn,Yn)の同時分布より定まる条件付き確率分布である。また、誤り率を
【００７６】
【数４】
2014220713.tif 000006
【００７７】
で定義した。これは長さnのブロックを復号するときの誤り確率を示しているのでブロック復号誤り率と呼ばれる。上記の復号器は符号器φが与えられたときにブロック復号誤り率をもっとも小さくする復号器である。一般に、このような復号を行うためには^Xnの全ての要素の確率を調べる必要があるため、nとともに指数的に大きくなってしまう。これでは現実的ではないので、次のように各成分毎に復号を行う。
【００７８】
xn≡(x1,x2,...,xn)のj番目の成分xjを復号する関数δjを
【００７９】
【数５】
2014220713.tif 000007
【００８０】
で定義し、 文字復号誤り率を
【００８１】
【数６】
2014220713.tif 000008
【００８２】
で定義すると、{δj}nj=1は平均文字復号誤り率を最小にする復号器になる。これはシンボル(復号)誤り率と呼ばれる。特に^X≡{0,1}の時はビット誤り率(BER,Bit Error Rate)と呼ばれる。これでもδjの右辺の周辺分布を求めるところでは加算の回数はnとともに指数的に増大してしまう。そこで、疎行列の構造を生かして実用的な時間で近似的に周辺分布を求めるのが以下で説明するsum-productアルゴリズムである。
【００８３】
上記から、復号器の目的は、bnR,ynが観測されたときの条件付確率Prob(Xj=xj|BnR=bnR、Yn=yn)の最も大きな文字xjを求めることになる。(Xn,Yn)が無記憶情報源であることを仮定すると、
【００８４】
【数７】
2014220713.tif 000009
【００８５】
となる。また、行列A=(ai,j)に対して
【００８６】
【数８】
2014220713.tif 000010
【００８７】
として、符号語bnR≡(b1,b2,...,bnR)に対して
【００８８】
【数９】
2014220713.tif 000011
【００８９】
とすると、上記(２)式の最大化に現れる目的関数は
【００９０】
【数１０】
2014220713.tif 000012
【００９１】
と変形できる。ここで、
【００９２】
【数１１】
2014220713.tif 000013
【００９３】
は、ベクトルxnに現れる変数xt以外の全てのxnの値を動かした時の総和である。
【００９４】
ファクターグラフを考えるとき、{xt}nt=1と対応するノードは変数ノードと呼ばれ、{^X(・,bi)}nRi=1と対応するノードはチェックノードと呼ばれる。
【００９５】
和操作はチェックノードから変数ノードへのメッセージの計算、積操作は変数ノードからチェックノードへのメッセージの計算となる。補助情報を利用した復号器の具体処理は以下のようになる。以下では、yj,biは既知であることを仮定し、パリティチェック^X(x^T(i),bi)と対応するノードを^Xiと書く。^I≡{1,2,...,nR},^J≡{1,2,...,n}とする。
【００９６】
以下にsum-productアルゴリズム（非特許文献（F. R. Kschischang, B. J. Frey and H.A. L. Loeliger, “Factor graphs and the sum-product algorithm,” IEEE Trans. Inform. Theory, vol.IT-47, pp. 498−519, Feb. 2001.）参照）を記述する。
【００９７】
sum-productアルゴリズムを用いた復号の具体処理は、以下のStep1〜Step1８で実現される。
【００９８】
Step1：  初期設定においてk=1として、繰り返し回数k'を定める。
【００９９】
Step2：  各j∈^JでMXj→^Xi(xj)≡1/|^X|と初期化する。
【０１００】
Step3(和操作)：  j∈^T(i)を満たしている全てのi∈^I,j∈^Jに対して
【０１０１】
【数１２】
2014220713.tif 000014
【０１０２】
によってM^Xi→xt(xt)を求める。ここで、
【０１０３】
【数１３】
2014220713.tif 000015
【０１０４】
は全ての
【０１０５】
【数１４】
2014220713.tif 000016
【０１０６】
を動かした時の総和である。
【０１０７】
Step 4(積操作)：  j∈^T(i)を満たしている全てのi∈^I,j∈^Jに対して
【０１０８】
【数１５】
2014220713.tif 000017
【０１０９】
によって
【０１１０】
【数１６】
2014220713.tif 000018
【０１１１】
を求める。
【０１１２】
Step 5(周辺化)：  各j∈Nで次の関数を求める。
【０１１３】
【数１７】
2014220713.tif 000019
【０１１４】
Step 6 (シンボルの推定)：
【０１１５】
【数１８】
2014220713.tif 000020
【０１１６】
を求めることによりxnの推定値^xn=(x1,x2,...,xn)を得る。
【０１１７】
Step 7：k=k'であるか、またはA^xn=bnRを満たしていれば、^xnを出力して終了する。
【０１１８】
Step 8：k<k'ならばkの値を1増やしてStep5に戻る。
【０１１９】
なお、上記Step 7においてA^xn=bnRを満たしているかどうかの判断を省略してもよい。なおこの場合はStep 5、6はk=k'の時にのみ実行すれば良い。
【０１２０】
以上説明したように、第１の実施の形態に係るセンサネットワークシステムの符号装置は、情報源から出力されたデジタル信号の系列Ｘiを、一方のデジタル信号の系列Ｘi（Ｕ）と他方のデジタル信号の系列Ｘi（Ｖ）とに分割し、分割により得られた一方のデジタル信号の系列Ｘi（Ｕ）に対して、可逆圧縮符号化を行って、符号語ψ（Ｘi（Ｕ））を生成し、復号装置へ送信する。また、符号装置は、過去に復号されたデジタル信号の系列Ｘjを分割して得られる一方のデジタル信号の系列Ｘj（Ｕ）と系列Ｘi（Ｕ）とに基づく条件付きエントロピーＨ（Ｘi（Ｕ）｜Ｘj（Ｕ））に基づいて行列サイズが決定されたＬＤＰＣ行列を用いて圧縮符号化を行って、符号語φ(Ｘi(Ｖ))を生成することにより、情報源からのデジタル信号が、非定常性が高いデジタル信号であっても、デジタル信号がもつ非定常性が符号化レートに与える影響を抑制することができる。
【０１２１】
また、第１の実施の形態に係るセンサネットワークシステムの復号装置は、情報源から出力されたデジタル信号の系列Ｘiを分割して得られた一方のデジタル信号の系列Ｘi（Ｕ）に対して可逆圧縮符号化を行って生成された符号語ψ（Ｘi（Ｕ））をデジタル信号の系列Ｘi（Ｕ）に復号し、復号データ記憶部に記憶された、デジタル信号の系列Ｘiと時区間の長さが同じデジタル信号の系列Ｘjを分割して得られるデジタル信号の系列Ｘj（Ｕ’）に基づく条件付きエントロピーＨ（Ｘi（Ｕ）｜Ｘj（Ｕ’））を算出し、条件付きエントロピーＨ（Ｘi（Ｕ）｜Ｘj（Ｕ’））の最小値に基づいて、ＬＤＰＣ行列の行列サイズを決定し、符号装置へ送信する。また、復号装置は、分割により得られた他方のデジタル信号の系列Ｘi（Ｖ）に対して圧縮符号化を行って生成された符号語φ（Ｘi（Ｖ））を、符号装置から受信し、決定した行列サイズのＬＤＰＣ行列を用いると共に、条件付きエントロピーＨ（Ｘi（Ｕ）｜Ｘj（Ｕ’））の最小値に対応するデジタル信号の系列Ｘjを補助情報として用いて、デジタル信号の系列Ｘi（Ｖ）に復号することにより、情報源からのデジタル信号が、非定常性が高いデジタル信号であっても、デジタル信号がもつ非定常性が符号化レートに与える影響を抑制することができる。
【０１２２】
また、非定常性が高いデジタル信号について、定常性が最大限保たれるようにデジタル信号の系列を二分し、その一方のデジタル信号の系列を使って条件付きエントロピーを計算する方法を用いることで、デジタル信号のもつ非定常性が符号化レートに与える影響を抑制することができる。
【０１２３】
また、過去のデジタル信号の系列から条件付きエントロピーが最小となるデジタル信号の系列を探索し、それを補助情報として用いて復号化を行うことで、符号化レートを小さく保つことができる。さらに、過去に受信したデジタル信号が多ければ多いほど、より条件付きエントロピーが低い系列を見つけることができる確率が上昇するため、多数の情報源が存在し、なおかつ長期にわたってデジタル信号を受信し続けるほど、符号化レートを小さくできる可能性が増大する。
【０１２４】
また、温度、湿度、照度、加速度、地磁気、ガス濃度、放射線量、イオン濃度、ＰＨ等の時間あたりの値の変化量が小さく、非定常性が高いセンサデータの圧縮に効果的である。
【０１２５】
なお、上記の実施の形態では、予め決めておく自然数ｋを用いて、デジタル信号の系列を二分割する場合を例に説明したが、これに限定されるものではない。例えば、分割する要素を予め定めておいてもよい。この場合には、予め、Xi(U)として抽出する要素を固定の集合Uとして保持しておき、その集合に従って要素を抽出することにより、デジタル信号の系列を分割する。たとえばn=10でテーブルがU={1,5,8}であれば、Xi(U)=(x1,x5,x8)であり、Xi(V)=(x2,x3,x4,x6,x7,x9,x10)とする。
【０１２６】
また、予め定めた関数を用いて、分割する要素を決めてもよい。この場合には、Xi(U)として抽出する要素の集合Uを与える関数fを用意する。たとえば
【０１２７】
【数１９】
2014220713.tif 000021
【０１２８】
であり、z=2とした場合、U={2,4,8,16,...}であり、V={1,3,5,6,...}である。fとしては、たとえば前述のようなzに関する多項式関数、z個の重複のない自然数の疑似乱数を与える関数がある。
【０１２９】
次に、第２の実施の形態について説明する。なお、第１の実施の形態と同様の構成となる部分については、同一符号を付して説明を省略する。
【０１３０】
第２の実施の形態では、観測装置から入力されたデジタル信号に変調を加えた信号を使用している点が、第１の実施の形態と異なっている。
【０１３１】
図５に示すように、センサネットワークシステム２１０の符号装置２１４は、変調部２２０、分割部２０、第１符号化部２２、第２符号化部２４、及び通信部２６を備えている。
【０１３２】
変調部２２０は、観測装置１２から入力されたデジタル信号の系列Xi(T)に対して、変調を加え、変調したデジタル信号の系列Yi(T)を出力する。変調方法としては、時間差分、離散フーリエ変換、離散コサイン変換、及びウェーブレット変換の何れか一つを用いればよい。
【０１３３】
分割部２０は、変調部２２０から出力されたデジタル信号の系列Yi(T)を、２つのデジタル信号の系列に分割する。第１符号化部２２及び第２符号化部２４も同様に、デジタル信号Xi(T)の代わりに、デジタル信号に変調を加えた信号Yi(T)を使用する。また、Xの代わりに、変調を行った信号の集合Y={Y1(Tn),Y2(Tn),...Yi-1(Tn)}を用いる。
【０１３４】
復号装置２１６は、通信部３０、復号データ記憶部３２、第１復号化部３４、エントロピー計算部３６、第２復号化部３８、補助情報取得部４０、出力部４２、及び逆変調部２４２を備えている。
【０１３５】
逆変調部２４２は、復号の最終過程で、出力部４２により得られた復号信号Yi(T)をXi(T)に逆変調する操作を行い、得られたデジタル信号の系列Xi(T)を出力する。なお、逆変調部２４２による逆変調は、必要に応じて行えばよい。
【０１３６】
なお、第２の実施の形態に係るネットワークセンサシステムの他の構成及び作用については、第１の実施の形態と同様であるため、説明を省略する。
【０１３７】
次に、第３の実施の形態について説明する。なお、第３の実施の形態に係るネットワークセンサシステムは、第１の実施の形態と同様の構成となるため、同一符号を付して説明を省略する。
【０１３８】
第３の実施の形態では、ｋ個のデジタル信号の系列を補助情報として用いて復号化を行っている点が、第１の実施の形態と異なっている。
【０１３９】
第３の実施の形態では、第２復号化部３８は、単独のデジタル信号Xj(T)を補助情報として用いる代わりに、k個の複数のデジタル信号
【０１４０】
【数２０】
2014220713.tif 000022
【０１４１】
を補助情報として用いる。
【０１４２】
エントロピー計算部３６は、第１復号化部３４によって復号されたデジタル信号の系列と、復号データ記憶部３２に記憶されたデジタル信号の系列の各組み合わせとに基づいて、条件付きエントロピーを計算し、復号データ記憶部３２に記憶されたデジタル信号の系列の各組み合わせから、以下の（３）式に示すような、条件付きエントロピーの最小値を与える、時区間の長さnUの複数のデジタル信号Xj,1(U'1),Xj,2(U'2),...，Xj,k(U'k)の組み合わせの元となる、複数のデジタル信号Xj,1(T'1),Xj,2(T'2),...，Xj,k(T'k)の組み合わせを探索すると共に、以下の（４）式を満足するように、ＬＤＰＣ行列の大きさを示す値ｍを決定する。
【０１４３】
【数２１】
2014220713.tif 000023
【０１４４】
第２復号化部３８は、補助情報としてXj,ｉ(T'1),Xj,2(T'2),...,Xj,k(T'k)を用いて、第２符号化部２４によって符号化された符号に対して復号を行い、分割された他方のデジタル信号の系列に復号する。
【０１４５】
なお、第３の実施の形態に係るネットワークセンサシステムの他の構成及び作用については、第１の実施の形態と同様であるため、説明を省略する。
【０１４６】
このように、過去のデジタル信号の系列から、条件付きエントロピーが最小となるデジタル信号の系列の組み合わせを探索し、それを補助情報として用いて復号化を行うことで、符号化レートを更に小さく保つことができる。
【０１４７】
なお、本発明は、上述した実施形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【０１４８】
例えば、ＬＤＰＣ符号の復号方法として、線形計画（LP）法により、ＬＤＰＣ行列及び補助情報を用いて復号化を行ってもよい。線形計画（LP）法については、特許文献（特開2010-278782号公報）に記載の手法を用いればよく、詳細な説明を省略する。
【０１４９】
また、Slepian-Wolf 符号を用いて、他方のデジタル信号の系列Xi(V)の符号化及び復号化を行うようにしてもよい。
【０１５０】
また、本願明細書中において、プログラムが予めインストールされている実施形態として説明したが、当該プログラムを、コンピュータ読み取り可能な記録媒体に格納して提供することも可能である。
【符号の説明】
【０１５１】
１０、２１０  センサネットワークシステム
１２   観測装置
１４、２１４  符号装置
１６、２１６  復号装置
１８   ネットワーク
２０   分割部
２２   第１符号化部
２４   第２符号化部
２６、３０    通信部
３２   復号データ記憶部
３４   第１復号化部
３６   エントロピー計算部
３８   第２復号化部
４０   補助情報取得部
４２   出力部
２２０ 変調部
２４２ 逆変調部
【図１】
2014220713.tif 000024
【図２】
2014220713.tif 000025
【図３】
2014220713.tif 000026
【図４】
2014220713.tif 000027
【図５】
2014220713.tif 000028