信号圧縮方法、信号復元方法、それら装置、プログラム並びにそれらプログラムを記録した記録媒体
【課題】一人の送信者から複数の受信者への信号伝送の際、各受信者へ異なるマルチメディア信号を同時に送信し、トラフィックを低減する圧縮及び復元方法を提供する。
【解決手段】本発明の信号圧縮方法は、設定された一定の長さの系列長を有する任意の2つの信号系列（以下、系列）対に対し、系列対に対応する圧縮系列を設定し、系列対及び圧縮系列の関係を示す圧縮系列表を生成する圧縮系列表作成過程と、第1及び第2信号系列各々を系列長の系列に分割し、第1及び第2分割系列の対の分割系列対の集合を抽出する系列分割過程と、分割系列対の経験確率分布を求める分割系列対経験分布導出過程と、分割系列対毎に対応する経験確率分布及び圧縮系列表を参照し、分割系列対に対応する圧縮部分系列を定める圧縮部分系列決定過程と、圧縮部分系列の集合から、圧縮部分系列を統合し、第1系列及び第2系列に対応する圧縮系列を生成する圧縮系列生成過程とから構成される。
【解決手段】本発明の信号圧縮方法は、設定された一定の長さの系列長を有する任意の2つの信号系列（以下、系列）対に対し、系列対に対応する圧縮系列を設定し、系列対及び圧縮系列の関係を示す圧縮系列表を生成する圧縮系列表作成過程と、第1及び第2信号系列各々を系列長の系列に分割し、第1及び第2分割系列の対の分割系列対の集合を抽出する系列分割過程と、分割系列対の経験確率分布を求める分割系列対経験分布導出過程と、分割系列対毎に対応する経験確率分布及び圧縮系列表を参照し、分割系列対に対応する圧縮部分系列を定める圧縮部分系列決定過程と、圧縮部分系列の集合から、圧縮部分系列を統合し、第1系列及び第2系列に対応する圧縮系列を生成する圧縮系列生成過程とから構成される。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、音楽、静止画像、動画像及びテキストファイルなどのコンテンツを送受信する際の圧縮及び復元を行う信号圧縮方法、信号復元方法、それら装置、プログラム並びにそれらプログラムを記録した記録媒体に関する。
【背景技術】
【０００２】
近年、音楽・映像を取得あるいは生成するデバイスの普及、また大容量ネットワークの普及などにより、音楽・静止画像・動画像・テキストなどを含む多様なコンテンツのマルチメディア信号がネットワーク上を流通し、それらコンテンツを各個人のレベルにて蓄積する機会が増大している。
しかし、パーソナルコンピュータにおける記憶媒体の大容量化・低価格化、及びネットワークにおける伝送の大容量化に対し、それを上回る速度にて、取り扱う情報量が増大してきている。
【０００３】
このため、記憶媒体の容量不足やネットワークトラフィックの過度の増大を避けるための手段の一つとして、信号を再度復元可能な形にて圧縮する技術が必須となってきている。
特に、携帯端末や衛星を介した信号伝送において、通信容量の制限及びネットワーク構成の複雑性などの理由から、上記マルチメディア信号を圧縮して伝送する技術が求められている。
【０００４】
上述した携帯端末や衛星を介した信号伝送は、複数の信号提供者（＝送信者）と複数の信号被提供者（＝受信者）との存在を仮定している。
さらに、圧縮及び復元を行う実用上の観点から、伝送されるマルチメディア信号がどのような確率構造に基づいて発生するかの知識がなくても、それら知識を持っている場合と同等の効率にて圧縮が行えて伝送できることが望ましい。
【０００５】
このような信号伝送における信号圧縮技術として、例えば、非特許文献１に記載された圧縮方法が知られている。
【非特許文献１】T. Uyematsu, "An algebraic construction of codes for Slepian-Wolf source networks,"IEEE Transactions on Information Theory, Vol. 47, No. 7, pp. 3082-3088, November 2001.
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、非特許文献１に記載の方法においては、複数の送信者と１人の受信者とを想定した信号伝送に対する信号圧縮技術のみについてが記載されている。
そのため、非特許文献１に記載の方法は、一人の送信者が複数の受信者に対して信号伝送を行うことができない。
一方、非特許文献１とは逆に、一人の送信者が複数の受信者に対して、それぞれ異なる情報を同時に行う信号伝送に対応する信号圧縮技術が確立されることが望まれている。特に、衛星を用いた放送型通信はその典型例である。
【０００７】
本発明は、このような事情に鑑みてなされたもので、一人の送信者と複数の受信者とにおける信号伝送において、各受信者に対してそれぞれ異なるマルチメディア信号を同時に送信する場合、ネットワークにおけるトラフィックを低減し、各受信者が受信する信号を効率的に圧縮復元が可能な信号圧縮方法及び信号復元方法を提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明の信号圧縮方法は、伝送の対象となる２つの信号系列である第１信号系列及び第２信号系列について、これら信号系列を、２つの信号系列のうちいずれかの信号系列を所有する複数の受信者へ伝送する信号伝送に用いる、上記信号系列を圧縮する信号圧縮方法であり、圧縮信号系列表作成部が、設定された一定の長さの系列長を有する任意の２つの信号系列からなる信号系列対に対し、該信号系列対の経験確率分布を用いて、信号系列対に対応する圧縮信号系列を設定し、信号系列対と圧縮信号系列との対応関係を示す圧縮信号系列表を生成し、該圧縮信号系列表を記憶部に記憶する圧縮信号系列表作成過程と、信号系列分割部が、入力される第１信号系列及び第２信号系列各々を、前記系列長の信号系列に分割し、第１分割信号系列及び第２分割信号系列の対である分割信号系列対の集合を抽出する信号系列分割過程と、分割信号系列対経験分布導出部が、前記分割信号系列対の各々の経験確率分布を求める分割信号系列対経験分布導出過程と、圧縮信号部分系列決定部が、前記分割信号系列対の各々に対応する前記経験確率分布及び前記圧縮信号系列表を参照し、該分割信号系列対に対応する圧縮信号系列である圧縮信号部分系列を定める圧縮信号部分系列決定過程と、圧縮信号系列生成部が、前記圧縮信号部分系列の集合から、それら圧縮信号部分系列を統合することにより、第１信号系列及び第２信号系列に対応する圧縮信号系列を生成する圧縮信号系列生成過程とから構成されることを特徴とする。
【０００９】
本発明の信号圧縮方法は、前記圧縮信号系列表作成過程は、信号系列対分類部が前記系列長を有する任意の信号系列の信号系列対に対し、該信号系列対の経験確率分布にて分類する信号系列対分類過程と、経験分布別圧縮信号系列表作成が前記信号系列対分類過程で得られた分類各々に対し、それぞれの分類に含まれる信号系列対各々に対応する圧縮信号系列を定め、信号系列対と圧縮信号系列との対応関係を示す圧縮信号系列表である経験分布別圧縮信号系列表を作成して記憶部に記憶する経験分布別圧縮信号系列表作成過程とから構成されることを特徴とする。
【００１０】
本発明の信号圧縮方法は、前記圧縮信号部分系列決定過程は、圧縮信号部分系列先頭決定部が、前記分割信号系列対の各々に対し、それぞれの分割信号系列対の経験確率分布に対応する番号もしくはその番号に対応する系列を、圧縮信号部分系列の先頭部分として設定する圧縮信号部分系列先頭部決定過程と、圧縮信号部分系列後続部決定部が、前記分割信号系列対の各々について、それぞれの分割信号系列対の経験確率分布に対応する経験分布別圧縮信号系列表を参照し、分割信号系列対に対応する圧縮信号系列を導出し、該圧縮信号系列を圧縮信号部分系列の後続部分として設定する圧縮信号部分系列後続部決定過程とから構成されることを特徴とする。
【００１１】
本発明の信号圧縮方法は、信号系列対分類選択部が前記信号系列対分類過程にて得られた分類の集合から、該分類に所属する信号系列対に対応する圧縮信号系列の長さが、あらかじめ設定された閾値である圧縮系列長閾値を下回る分類のみを選択する信号系列対分類選択過程をさらに有し、前記経験分布別圧縮信号系列表作成過程が、前記信号系列対分類選択過程にて選択された前記分類に対して圧縮信号系列表を作成し、前記圧縮信号部分系列後続部決定過程において、圧縮信号部分系列後続部が、圧縮信号系列表が作成されていない分類に対し、任意の系列を圧縮信号部分系列の後続部分として決定することを特徴とする。
【００１２】
本発明の信号復元方法は、複数の受信者へ信号系列を伝送する際、予め受信者が有する信号系列と、伝送の対象となる他の信号系列との２つの信号系列からなる圧縮された圧縮信号系列を復元する信号復元方法であり、圧縮信号系列分割部が、前記圧縮信号系列を分割し、復元圧縮信号部分系列を生成する圧縮信号系列分割過程と、圧縮信号系列表同定部が、前記圧縮信号系列分割過程にて得られた復元圧縮信号部分系列の各々に対し、それぞれの圧縮信号部分系列に対応する圧縮信号系列表を、圧縮信号部分系列に対応して圧縮信号系列表が記憶されている記憶部から同定する圧縮信号系列表同定過程と、分割信号系列復元部が、前記復元圧縮信号部分系列各々と、前記予め受信者が有する信号系列を予め設定された系列長にて分割して生成した第２分割信号系列とにより、その復元圧縮信号部分系列に対応して前記圧縮信号系列表同定過程にて得られた圧縮信号系列表である復元圧縮信号系列表から、前記第２分割信号系列の対である分割信号系列を読み出し、復元第１分割信号系列とする分割信号系列復元過程と、復元信号系列生成部が、前記分割信号系列復元にてえられた前記復元第１分割信号系列の集合から、それら復元第１分割信号系列を統合することにより、予め受信者が有する信号系列と対をなす伝送の対象となる他の信号系列を復元する復元信号系列生成過程とから構成されることを特徴とする。
【００１３】
本発明の信号復元方法は、前記圧縮信号系列表同定過程において、前記圧縮信号系列表同定部が前記圧縮信号系列分割過程にて得られた復元圧縮信号部分系列各々について、それぞれの圧縮信号部分系列の先頭部分から、その圧縮信号部分系列を生成した経験分布別圧縮信号系列表を同定し、前記先頭部分がそれぞれの分割信号系列対の経験確率分布に対応する番号もしくはその番号に対応する系列であることを特徴とする。
【００１４】
本発明の信号圧縮装置は、伝送の対象となる２つの信号系列である第１信号系列及び第２信号系列について、これら信号系列を、２つの信号系列のうちいずれかの信号系列を所有する複数の受信者へ伝送する信号伝送に用いる、上記信号系列を圧縮する信号圧縮装置であり、設定された一定の長さの系列長を有する任意の２つの信号系列からなる信号系列対に対し、該信号系列対の経験確率分布を用いて、信号系列対に対応する圧縮信号系列を設定し、信号系列対と圧縮信号系列との対応関係を示す圧縮信号系列表を生成し、該圧縮信号系列表を記憶部に記憶する圧縮信号系列表作成部と、入力される第１信号系列及び第２信号系列各々を、前記系列長の信号系列に分割し、第１分割信号系列及び第２分割信号系列の対である分割信号系列対の集合を抽出する信号系列分割部と、前記分割信号系列対の各々の経験確率分布を求める分割信号系列対経験分布導出部と、前記分割信号系列対の各々に対応する前記経験確率分布及び前記圧縮信号系列表を参照し、該分割信号系列対に対応する圧縮信号系列である圧縮信号部分系列を定める圧縮信号部分系列決定部と、前記圧縮信号部分系列の集合から、それら圧縮信号部分系列を統合することにより、第１信号系列及び第２信号系列に対応する圧縮信号系列を生成する圧縮信号系列生成部とから構成されることを特徴とする。
【００１５】
本発明の信号復元装置は、複数の受信者へ信号系列を伝送する際、予め受信者が有する信号系列と、伝送の対象となる他の信号系列との２つの信号系列からなる圧縮された圧縮信号系列を復元する信号復元装置であり、前記圧縮信号系列を分割し、復元圧縮信号部分系列を生成する圧縮信号系列分割部と、前記圧縮信号系列分割部にて得られた復元圧縮信号部分系列の各々に対し、それぞれの圧縮信号部分系列に対応する圧縮信号系列表を、圧縮信号部分系列に対応して圧縮信号系列表が記憶されている記憶部から同定する圧縮信号系列表同定部と、前記復元圧縮信号部分系列各々と、前記予め受信者が有する信号系列を予め設定された系列長にて分割して生成した第２分割信号系列とにより、その復元圧縮信号部分系列に対応して前記圧縮信号系列表同定部にて得られた圧縮信号系列表である復元圧縮信号系列表から、前記第２分割信号系列の対である分割信号系列を読み出し、復元第１分割信号系列とする分割信号系列復元部と、前記分割信号系列復元にてえられた前記復元第１分割信号系列の集合から、それら復元第１分割信号系列を統合することにより、予め受信者が有する信号系列と対をなす伝送の対象となる他の信号系列を復元する復元信号系列生成部とから構成されることを特徴とする。
【００１６】
本発明のプログラムは、コンピュータに上記いずれかに記載の信号圧縮方法を実行させるためのコンピュータが実行可能なプログラムである。
【００１７】
本発明のプログラムは、コンピュータに上記いずれかに記載の信号復元方法を実行させるためのコンピュータが実行可能なプログラムである。
【００１８】
本発明のコンピュータ読み取り可能な記録媒体は、上記いずれかに記載のプログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の効果】
【００１９】
本発明によれば、１人の送信者と複数の受信者を想定した場合、マルチメディア信号を各受信者の端末に送信する際、２つの信号系列を１つの圧縮信号系列として送信するため、ネットワークにおけるトラフィックを低減することができる。
また、本発明によれば、２つの信号系列対と圧縮系列信号との対応を示す圧縮信号系列表を、圧縮側と復元側とがそれぞれの記憶部に共通に記憶しているため、圧縮信号系列と信号系列対の一方の信号系列とにより、上記圧縮信号系列表から他方の信号系列を抽出することにより、効率的に圧縮及び復元が可能である。
【発明を実施するための最良の形態】
【００２０】
本発明で言及する信号伝送においては、図１に示すように、１人の送信者と複数の受信者を想定する際、送信者が所有する２つの信号のうちいずれか１つの信号を各受信者が所有している場合、各受信者が所有していない信号を受信できるように、送信者が信号を圧縮し、全ての受信者に対して同一の圧縮信号を送信者から伝送する。図１は本発明の実施形態による伝送システムの構成を示す概念図である。
本発明の信号伝送においては、通常、送信者が所有する信号を受信者が正しく受信できない確率が無視できる程度に小さくすることが要求される。
【００２１】
このとき、信号の圧縮率をエントロピーを用いて表現したときの理論的限界値、及び圧縮率がその理論的限界値に漸近する信号圧縮方法の存在が、以下の非特許文献２及び３に示されている。
（非特許文献2）A・ D. Wyner, J. K. Wolf, and F・ M. J. Willems“Communicating via a processing broadcast satellite,”IEEE Transactions on Information Theory, Vol・ 48, N0. 6, pp. 1243-1249, June 2002.
（非特許文献3) A. Kimura and T. Uyematsu, "Multiterminal source coding with complementary delivery,”Proc. International Symposium on Information Theory and its Applications(ISITA), pp. 189-194,October 2006.
【００２２】
上述したように、本発明においては、伝送すべき信号が従う確率構造についての知識がなくても、圧縮率が上記非特許文献２及び３に示される理論的限界値に漸近する信号圧縮方法を示すものである。
そのため、本発明においては、後に詳述するが、以下のａ及びｂの２点により、上記の理論的限界値に漸近する信号圧縮を行い信号伝送方法を実現している。
ａ．与えられた２つの信号系列のみから得られる経験的な確率分布（以下、同時経験分布）を用いることにより、信号系列がどのような確率構造に基づいて生成されたかについての知識がなくても、圧縮率が理論的限界値に漸近する信号圧縮を可能にする。
ｂ．与えられた２つの信号系列を圧縮する際に、その同時経験分布に基づき、信号系列対と圧縮系列信号との対応関係を示す表を作成することにより、受信者が所有している情報を基に、受信者が所有していない情報を復元する操作を容易に行う。
【００２３】
＜第１の実施形態＞
本実施形態における信号系列の伝送を行う伝送システムとしては、図１の概念図に示すように、信号系列を圧縮する信号系列圧縮部１が信号系列を送信する送信側装置に設けられ、圧縮された信号系列（圧縮信号系列）を復元する系列復元部２（あるいは３）が受信側端末に設けられている。
【００２４】
ここで、送信側装置１００は伝送の対象となる２つの信号系列である第１信号系列Ｘｎ及び第２信号系列Ｙｎを入力し、これら信号系列から圧縮信号系列Ｚを生成し、この圧縮信号系列Ｚを２つの信号系列Ｘｎ及びＹｎのいずれかの信号系列を所有する（端末の記憶部に記憶されている）複数の受信側端末２０１、２０２、…へ伝送する。
一方、受信側端末２０１、２０２、…各々は、自身が所有している信号系列を用いて、上記圧縮信号系列から、自身の所有していない信号系列を、それぞれの系列復元部により復元し、その復元した信号系列である復元信号系列Ｘ〜ｎあるいはＹ〜ｎを出力する。
【００２５】
以下の説明において、簡単化のため、全ての信号系列を文字系列であるとし、信号系列を単に系列と呼ぶ。第１信号系列、第２信号系列及び復元信号系列についても、同様に、それぞれを第１系列、第２系列、復元系列と呼ぶ。
また、第１系列と第２系列とは、特に断らない限りにおいて、同一の長さｎを持つと仮定する。
また、第１系列ｘｎの各文字列ｘｉ（ｉ＝１，２，…，ｎ）は有限文字集合である。
【００２６】
上記信号系列圧縮部１は、第１系列ｘｎ及び第２系列ｙｎを入力し、これら系列を複合して圧縮した圧縮系列を抽出し、その抽出された圧縮系列を出力する。
圧縮系列の抽出方法は特に限定されるものではないが、本実施形態においては、例えば以下に示す構成により行う。
信号系列圧縮部１は、図２に示すように、圧縮系列表作成部１１と、系列分割部１２と、系列経験分布導出部１３と、圧縮部分系列決定部１４と、圧縮系列生成部１５とを有している。図２は信号系列圧縮部１の構成例を示すブロック図である。
【００２７】
上記圧縮系列表作成部１１は、以下に示す図３のフローチャートの流れに従い、ある一定の長さを持つ任意の系列の対について、その系列対の同時経験分布を用い、その系列対に対応する圧縮系列を定め、系列対と圧縮系列との対応関係を示す表である圧縮系列表を作成し、その圧縮系列表を出力する。上記図３は、圧縮系列表作成部１１における圧縮系列表の生成処理の動作例を示すフローチャートである。
圧縮系列表作成部１１による圧縮系列表の作成方法は特に限定されるものではないが、本実施形態においては、例えば以下に示す構成によって作成する。
圧縮系列表作成部１１は、例えば、系列対分類部１１１と、経験分布別圧縮系列表作成部１１２とによって構成される作成方法について、図３のフローの処理に従って述べる。
【００２８】
系列対分類部１１１は、ある一定の長さを持つ任意の系列対を同時経験分布、すなわち、同一の経験確率分布を有する系列対の集合により分類し、その分類の集合を経験分布共有系列対集合として出力する。本実施形態において、系列対分類部１１１は、系列対を以下のようにして分類する。
系列対分類部１１１は、分類に用いる系列の長さである系列長ｍを設定する。ここで設定される系列長ｍは、ユーザが入力しても良いし、あるいは系列対分類部１１１が第１系列及び第２系列の文字数にて決定してもよい。この系列長ｍは、第１系列及び第２系列の系列長ｎと同一である必要はないが、ｍ≦ｎを満たす必要がある。
【００２９】
次に、系列対分類部１１１は、系列長ｍである系列の系列対(ｘ〜ｍ，ｙ〜ｍ)が入力されると、この任意の系列対について、その経験的な確率分布である同時経験分布Ｑx〜ｍ,y〜ｍ∈Ｐm(Ｖ×Ｗ)を、以下の（１）式から求める。
【００３０】
【数１】
【００３１】
上記（１）式において、Ｎ(ａ，ｂ／ｘ〜ｍ,ｙ〜ｍ)は系列対(ｘ〜ｍ，ｙ〜ｍ)の中で文字対（ａ，ｂ）が生起する回数である。また、Ｐm(Ｖ×Ｗ)は、直積文字集合Ｘ×Ｙからなる系列長ｍの系列についての同時経験分布全体の集合である。ここで、系列対分類部１１１は、同時経験分布全体の集合、すなわち系列対(ｘ〜ｍ，ｙ〜ｍ)における文字の同時経験分布の組み合わせの全てを含む集合を生成し、内部の記憶部に記憶する（ステップＳ１、ステップＳ２）。例えば、系列長ｍ＝４の２元系列の対(ｘ〜ｍ，ｙ〜ｍ)＝（００１０，０００１）について、同時経験分布は、以下の（２）式のように算出される。
【００３２】
【数２】
【００３３】
そして、系列対分類部１１１は、内部に記憶した同時経験分布各々について、その同時経験分布Ｑを有する系列長ｍの系列対の集合ＴｍＱを求める。ＴｍＱは以下の（３）式によって表現される。この同一のＱを有する系列長ｍの系列対の分類した集合を、経験分布共有系列対集合として、順次、経験分布別圧縮系列表作成部１１２に対して出力する（ステップＳ３）。
【００３４】
【数３】
【００３５】
たとえば、上述した系列長ｍ＝４の場合における（２）式に示す同時経験分布Ｑに対して、その経験分布共有系列対集合は、以下の（４）式に示すように文字対（ｘｉ，ｙｊ）からなる系列の組の集合であり、この例では（０，０）の組が２回、（１，０）及び（０，１）の組がそれぞれ１回出現する。
【００３６】
【数４】
【００３７】
そして、経験分布別圧縮系列表作成部１１２は、以下のステップＳ４以降の処理において、上記系列対分類部１１１から出力される経験分布共有系列対集合が入力されると、各経験分布共有系列対集合に含まれる系列対各々に対して圧縮系列を対応させ、それぞれの分類について系列対と圧縮系列との対応関係を示す圧縮系列表である経験分布別圧縮系列表を作成し、この分類毎の経験分布別圧縮系列表を圧縮系列表集合として出力する。ここで、経験分布別圧縮系列表作成部１１２は、図示しない記憶部に、生成した上記経験分布別圧縮系列表の圧縮系列表集合を記憶させる。
【００３８】
ここで、経験分布別圧縮系列表作成部１１２は、分類毎の経験分布別圧縮系列表を、以下のようにして作成する。この作成の過程を、経験分布別圧縮系列行の概念図である図４を用いて説明する。
経験分布別圧縮系列表作成部１１２は、同時経験分布Ｑ各々から、その同時経験分布Ｑに対応する経験分布共有系列対集合ＴｍＱを構成する系列ｘ〜ｍ及びｙ〜ｍの集合、すなわち以下の（５）式に示す系列集合ＴｍＱ；Ｘ、及び（６）式に示す系列集合ＴｍＱ；Ｙをそれぞれ抽出する。
【００３９】
【数５】
【００４０】
【数６】
【００４１】
上述の（２）式にて示した同時経験分布の例において、上記系列集合ＴｍＱ；Ｘ、及び系列集合ＴｍＱ；Ｙを各々は、ぞれぞれ以下の（７）、（８）式に示す集合となる。
【００４２】
【数７】
【００４３】
【数８】
【００４４】
次に、経験分布別圧縮系列表作成部１１２は、図４（ａ）に示すように、抽出した系列対における系列ｘ〜ｍの集合である系列集合ＴｍＱ；Ｘを行の要素とし、系列ｙ〜ｍの集合である系列集合ＴｍＱ；Ｙを列の要素として表を生成し、内部の記憶部に記憶する（ステップＳ４）。
【００４５】
また、経験分布別圧縮系列表作成部１１２は、図４（ｂ）に示すように、該当の同時経験分布を有する系列対に対してに対応する枠（列及び行の交点の座標にある枠）を、それぞれの経験分布共有系列対集合に含まれる同時経験分布と一致するものを抽出し、抽出した枠に対してマークを付与、例えば丸印を書き込む。
すなわち、経験分布別圧縮系列表作成部１１２は、実際にＴｍＱの要素となっている系列対(ｘ〜ｍ，ｙ〜ｍ)を抽出する。図４（ｂ）は、系列対に対するこのような印（「○」マーク）の与え方の１例である。
例えば、経験分布別圧縮系列表作成部１１２は、（１）式にて示した同時経験分布の例において、ｘ１の行を例に取ると、同一の同時経験分布の組み合わせを有する（０００１，００１０）、（０００１，０１００）、（０００１，１０００）に対して印を付加する。
ここで、以下の（９）式が成り立つことから、図４（ａ）の表の枠に対して全て印が与えられるとは限らない。
【００４６】
【数９】
【００４７】
そして、経験分布別圧縮系列表作成部１１２は、（１）式にて示した同時経験分布に対応する経験分布共有系列対集合に対しての処理が終了した後、順次、他の同時経験分布の組み合わせである経験分布共有系列対集合に対応する図４（ｂ）の経験分布別圧縮系列表をそれぞれ生成し、一時的に内部の記憶部に記憶する。
上述したように、経験分布別圧縮系列表作成部１１２は、系列対分類部１１１から入力される経験分布共有結合対集合各々に対応する経験分布別圧縮系列表を生成し、内部の記憶部に記憶する（ステップＳ５）。
【００４８】
次に、経験分布別圧縮系列表作成部１１２は、図４（ｃ）に示すように、上述したように、内部の記憶部に記憶されている経験分布別圧縮系列表を順次読み出し、各経験分布別圧縮系列表毎に印が与えられた枠（抽出された系列対）に対し、圧縮系列対それぞれに対応する識別番号を割り当てる（ステップＳ６及びＳ７）。
このとき、経験分布別圧縮系列表作成部１１２は、後に説明する方法にて、各行及び各列の中において全て相異なる識別番号が割り当てられるようにする。図４（ｃ）は、このような識別番号の割り当て方の１例である。具体的な識別番号の割り当て方法については後述する。
【００４９】
経験分布別圧縮系列表作成部１１２は、上記のようにして作成された|ＴｍＱ；Ｘ|行、｜ＴｍＱ；Ｙ｜列の表を、同時経験分布Ｑについての経験分布別圧縮系列表として出力し、上記記憶部に記憶させる。ここで、個々で用いている｜ＴｍＱ；Ｘ ｜及び｜ＴｍＱ；Ｙ｜各々は、それぞれ集合ＴｍＱに含まれる系列ｘ〜ｍまたは系列ｙ〜ｍの数を示すものである。上記経験分布別圧縮系列表は、後に説明する識別番号の割り当て方法により以下の性質を有するよう形成されている。
１．全ての行について、印が与えられている枠（系列対）の数は同一、例えば図４においては３つずつであり、その枠の数は同時経験分布のみに依存している(ｍｘ（Ｑ）と表す)。
２．全ての列について、印が与えられている枠の数は同一であり、例えば図４においては３つずつであり、その枠の数は同時経験分布のみに依存している（ｍｙ（Ｑ）と表す)。
３．上記のように各系列対に対する識別番号の割り当てを可能とするには、max（ｍｘ（Ｑ），ｍｙ（Ｑ）)種類の相異なる識別番号が必要となる。
【００５０】
上記第３の性質は、経験分布別圧縮系列表が２部グラフ(グラフの頂点を２つの集合に分類でき、同一分類内の頂点の間に辺が存在しないグラフ)と等価であり、その２部グラフの一方の頂点集合について要素数が｜ＴｍＱ；Ｘ ｜かつ各頂点に連結される辺数がｍｘ（Ｑ）、もう一方の頂点集合について要素数が｜ＴｍＱ；Ｙ｜かつ各頂点に連結される辺数がｍｙ（Ｑ）となることによるものである。
【００５１】
上述したことから、経験分布別圧縮系列表作成部１１２による各経験分布別圧縮系列表への識別番号の割り当ては、上記２部グラフに対する辺彩色と等価である。この辺彩色とは、隣り合った辺同士を異なる色で塗ることをいう。
上述したように、経験分布別圧縮系列表作成部１１２は、同時経験分布の分類である経験分布共有系列対集合毎に 経験分布別圧縮系列表を生成する。
【００５２】
上記２部グラフに対する辺彩色の方法としては、どのような方法を用いても良いが、例えば、以下に示す非特許文献４もしくは非特許文献５に記載の方法を用いることができる。
・A. Schrijver: “Bipartite edge coloring in Ｏ(Δｍ) time,” SIAM Journal on Computing,Vol.28, pp.841-846, :1998.(非特許文献４)
・R. Cole, K. Ost, S. Schirra: “Edge coloring bipartite multigraphs in Ｏ(ＥlogＤ）time,”Combinatorica. Vol.21, pp.5-12, 2001.(非特許文献５)
【００５３】
例えば、本実施形態にてはいずれの辺彩色の方法を用いても良いが、上記非特許文献４における方法について以下に説明する。
ここで、図３（ｃ）における枠に対する識別番号の付与処理と等価な２部グラフを図５に示す。
この図において、頂点は各系列対を形成する系列ｘ〜ｍ及びｙ〜ｍに対応しており、２部グラフにおける行（系列ｘ〜ｍに対応）におけるグラフと列（系列ｙ〜ｍに対応）におけるグラフとにおいて、系列ｘ〜ｍ及びｙ〜ｍのそれぞれ系列対を形成している各頂点（すなわち、２部グラフそれぞれの系列）を結ぶ辺（図５における実線Ａ１〜Ａ４、破線Ｂ１〜Ｂ４、破線Ｃ１〜Ｃ４）が、この系列対の識別番号（Ａ１〜Ａ４：識別番号「１」，Ｂ１〜Ｂ４：識別番号「２」，Ｃ１〜Ｃ４：識別番号「３」）に対応している。
【００５４】
１．２部グラフＧの各頂点の次数(当該頂点に連結する辺の数)を揃える。このように、２部グラフの各頂点の次数が全て同一であるときに、この２部グラフを正則２部グラフと呼ぶ。ここで、頂点の次数は、以下のようにして揃える。
Ａ．グラフＧのコピーＧ〜を生成する。
Ｂ．グラフＧの次数の最大値をｋとした場合、グラフＧの各頂点と、コピーされたグラフＧ〜とにおける対応する頂点との間、当該頂点の次数がｋとなるように適切な本数の辺を作成する。
【００５５】
２．上記の手順で生成された正則２部グラフＧ’について、以下の方法により、各辺に対する辺彩色を行う。
Ａ．グラフＧ'の次数が偶数であるとき
ａ．グラフＧ’のオイラー回路を検出する。
ここで、オイラー回路とは、重複する辺を持たないようにある頂点から、他の頂点を辿りある頂点に戻る経路のうち、グラフの全ての辺を含む経路を指している。このオイラー回路検出問題は、いわゆる「一筆書き」問題としてよく知られている。
【００５６】
上記オイラー回路を作成するアルゴリズムとしては、例えば、以下に示すFleuryのアルゴリズムがよく知られている。
すなわち、
ｉ．出発する頂点を任意に選ぶ。
ii．他に選択肢がない場合を除き、取り除くことでグラフが不連結になるような辺を避け、それ以外の辺を辿る。(他に選択肢がない場合には、不連結になっても良い。)
iii．辿った辺をグラフから除去し、この辺の除去により、辺が１つも連結していない頂点が生じる場合、その頂点もグラフから除去する。(手順２.Ａ.ａ.ｉにおいてグラフが不連結になっても、この手順により不連結状態は解消されることになる。)
iv．グラフが空になるまで、上記２.Ａ.ａ.ｉから２.Ａ.ａ.iiiの手順を繰り返す。
【００５７】
ｂ．グラフＧ’の各頂点について、上記の手順で発見したオイラー回路を辿ったときに、当該頂点に到達する辺のみを取り出し、部分グラフＧ１を生成する。
また、当該頂点から出発する辺のみを取り出し、別途、部分グラフＧ２を生成する。オイラー回路の性質から、部分グラフＧ１及びＧ２は、いずれも正則２部グラフであり、その次数はＧの半分である。
ｃ．部分グラフＧ１及びＧ２について、再帰的に上記２の方法により辺彩色を行う。
【００５８】
Ｂ．グラフＧ'の次数が奇数であるとき（図５の例に該当（ｋ＝３））
ａ．グラフＧ’の完全マッチングＭを求める。このマッチングとは、グラフの辺の部分集合のうち、属する辺の両端の頂点が全て異なるものを指し、かつ完全マッチングとは、グラフの全ての頂点を辺の両端として含むマッチングを指すこととする。
以下に、この完全マッチングを求める方法を示す。
ｉ．辺ｅに対応する重み係数ω（ｅ）を定義し、この重み係数の初期状態として、グラフの全ての辺について、ω（ｅ）＝１とする。
また、グラフの辺のある部分集合Ｆについて、その部分集合Ｆに対応する重み係数ω（Ｆ）を、ω（Ｆ）＝Σｅ∈Ｆω（ｅ）によって定義する。
さらに、グラフの辺の部分集合Ｆについて、ＵＦを以下の（１０）に示すように定義する。
【００５９】
【数１０】
【００６０】
ii．重みが０ではない辺のみから構成される閉路を、グラフから任意に検出し、この閉路を２つのマッチングＭとＮとに分割する。ただし、ω（Ｍ）≧ω(Ｎ)とする。
対象とするグラフは２部グラフであることから、検出される上記閉路は全て偶数本の辺から構成される。
したがって、当該の２つのマッチングは、閉路を辿りながら交互に辺を選択していくことで得られる。
iii．グラフの全ての辺について、以下の（１１）式により重みを更新する。
【００６１】
【数１１】
【００６２】
iv．グラフの全ての辺の重みが、グラフの次数もしくは０になるまで、２.Ｂ.ａ.ｉ〜２.Ｂ.ａ.iiiの手順を繰り返す。
ｂ．上記の手順で得られた完全マッチングＭの各辺に同一の色を与え、グラフＧ’から取り除く。マッチングを取り除いたグラフについて、再帰的に上記２の方法で辺彩色を行う。
すなわち、図５に示すように、辺Ａ１〜Ａ４，Ｂ１〜Ｂ４，Ｃ１〜Ｃ４各々の両端の頂点が全て異なるものを指し（例えば、row（０００１）は同様の頂点column（０００１）と共有する辺を有さず、頂点column（００１０）、（０１００）、（１０００）と辺を共有している）、かつ完全マッチングとは、グラフの全ての頂点を辺の両端として含むマッチングを指している。
【００６３】
上述のようにして、経験分布別圧縮系列表の各枠（各系列対）に割り当てられた識別番号を、ｃ２＝ｃ２（Ｑ）桁の｜Ｚ｜進表現することにより、各枠に対応する系列対(ｘ〜ｍ，ｙ〜ｍ)に割り当てられる圧縮系列ｚ〜ｃ２が得られる。ここで、Ｚは圧縮系列を構成する文字の集合であり、ｃ２（Ｑ）は以下の（１２）式により経験分布別圧縮系列表作成部１１２が求め、｜Ｚ｜は上記文字の集合Ｚの文字数である。
上述したステップＳ１からステップＳ８の処理により、圧縮系列表作成部１１は、経験分布共有系列対集合毎に生成した上記経験分布別圧縮系列表の集合を圧縮系列表として出力し、内部の記憶部に記憶する。
【００６４】
【数１２】
【００６５】
次に、系列分割部１２は、受信側端末に対する伝送対象の第１系列及び第２系列を入力し、それら系列各々を、前記圧縮系列表作成部１１で定められた系列長の系列に分割することにより、それぞれ第１分割系列及び第２分割系列を抽出し、それら分割系列の対である分割系列対について、その集合を出力する。
本実施形態において、系列分割部１２は、第１系列ｘｎ及び第２系列ｙｎを、系列対分類部１１１により定めた系列長ｍを用いて、以下の（１３）式、（１４）式及び（１５）式を用いて分割する。
【００６６】
【数１３】
【００６７】
【数１４】
【００６８】
【数１５】
【００６９】
ここで、ｘｊｉ は系列ｘｎの第ｉ成分から第ｊ成分までを切り出した部分系列、すなわちｘｊｉ＝ｘｉｘｉ＋１…ｘｊである。また、floor（ｔ）は実数ｔ以下の最大の整数を求める関数である。上記の分割方法は、すなわち、系列の先頭から順に系列長ｍの部分系列を切り出し、系列長ｍの部分系列が切り出せなくなったところで系列の分割処理を終了し、残りの部分系列（系列長がｍ未満）をそのまま出力する方法である。
上述したように、系列分割部１２は、以下に示す（１６）式及び（１７）式に示すように、分割系列対を抽出し、これら分割系列対の集合を出力する。
【００７０】
【数１６】
【００７１】
【数１７】
【００７２】
系列経験分布導出部１３は、系列分割部１２から上記分割系列対の集合を入力し、それら分割系列対の各々から同時経験分布を導出し、その同時経験分布の集合を出力する。
ここで、系列経験分布導出部１３は、各分割系列対(ｘ〜ｍ（ｊ），ｙ〜ｍ（ｊ）)についての同時経験分布Ｑｍｘ〜ｍ（ｊ），ｙ〜ｍ（ｊ）を、上記系列対分類部１１１で説明した方法と同様にして求める。
また、系列経験分布導出部１３は、ｌ＋１番目、すなわち系列長ｍに満たない余りの分割系列対(ｘ〜ｍ（ｌ＋１），ｙ〜ｍ（ｌ＋１）)については、同時経験分布を抽出しない。
【００７３】
圧縮部分系列決定部１４は、上記経験分布別圧縮系列表の集合、上記分割系列対の集合及び同時経験分布Ｑｍｘ〜ｍ（ｊ），ｙ〜ｍ（ｊ）の集合を記憶部から入力し、それら分割系列対の各々について、対応する同時経験分布Ｑｍｘ〜ｍ（ｊ），ｙ〜ｍ（ｊ）及び経験分布別圧縮系列表を用いて、その分割系列対に対応する圧縮系列である圧縮部分系列を定め、その圧縮部分系列の集合を出力する。
ここで、圧縮部分系列の決定方法は特に限定されるものではないが、本実施例において、圧縮部分系列決定部１４は、例えば圧縮部分系列先頭部決定部１４１ と、圧縮部分系列後続部決定部１４２とによって構成されている。以下、この圧縮部分系列決定部１４による圧縮部分系列の生成方法について述べる。
【００７４】
圧縮部分系列先頭部決定部１４１は、上記分割系列対の集合及び同時経験分布Ｑｍｘ〜ｍ（ｊ），〜ｙｍ（ｊ）の集合を入力し、それら分割系列対の各々について、その分割信号系列の同時経験分布Ｑｍｘ〜ｍ（ｊ），ｙ〜ｍ（ｊ）に対応する識別番号もしくはその識別番号に対応する系列を、圧縮部分系列の先頭部分とし、その圧縮部分系列の先頭部分の集合を出力する。
本実施形態において、圧縮部分系列先頭部決定部１４１は、圧縮部分系列の先頭部分を、以下のようにして決定する。
ここで、同時経験分布全体の集合Ｐm（Ｖ×Ｗ）の各要素に対して異なる識別番号があらかじめ与えられているとする。このとき、集合Ｐm（Ｖ×Ｗ）の要素数が以下の（１８）式により、（ｍ＋１）｜Ｖ×Ｗ｜より等しいか小さいため、この識別番号を高々（ｍ＋１）｜Ｖ×Ｗ｜種類の識別番号を用意すれば良い。
【００７５】
【数１８】
【００７６】
そこで、圧縮部分系列先頭部決定部１４１は、分割系列対（ｘ〜ｍ（ｊ），ｙ〜ｍ（ｊ））（ｊ＝１，２，…，ｌ）に対して、その同時経験分布Ｑｍｘ〜ｍ（ｊ），ｙ〜ｍ（ｊ）に対応する識別番号を割り当てる。
そして、圧縮部分系列先頭部決定部１４１は、各分割系列対に割り当てられた識別番号を、ｃ1＝｜Ｖ×Ｗ｜log｜Ｚ｜（ｍ＋１）桁の｜Ｚ｜進表現（以下の（１９）式）に変換し、この｜Ｚ｜進表現を、分割系列対（ｘ〜ｍ（ｊ），ｙ〜ｍ（ｊ））に対応する圧縮部分系列の先頭部分として決定する。
【００７７】
【数１９】
【００７８】
圧縮部分系列後続部決定部１４２は、上記経験分布別圧縮系列表の集合、分割系列対の集合、及び同時経験分布Ｑｍｘ〜ｍ（ｊ），ｙ〜ｍ（ｊ）の集合を入力する。このとき、圧縮部分系列後続部決定部１４２は、経験分布別圧縮系列表の集合を上記記憶部から読み出す。
そして、圧縮部分系列後続部決定部１４２は、入力された分割系列対の各々について、その分割系列対の同時経験分布Ｑｍｘ〜ｍ（ｊ），ｙ〜ｍ（ｊ）に対応する経験分布別圧縮系列表から、その分割系列対（ｘ〜ｍ（ｊ），ｙ〜ｍ（ｊ））に対応する圧縮系列を導出し、これを圧縮部分系列の後続部として決定し、その圧縮部分系列の後続部の集合を出力する。
【００７９】
本実施形態において、圧縮部分系列後続部決定部１４２は、圧縮部分系列の後続部を、以下のように決定する。
この決定の際、圧縮部分系列後続部決定部１４２は、分割系列対（ｘ〜ｍ（ｊ），ｙ〜ｍ（ｊ））（ｊ＝１，２，…，ｌ）に対して、その同時経験分布Ｑｍｘ〜ｍ（ｊ），ｙ〜ｍ（ｊ）に対応する経験分布別圧縮系列表を選択する。
次に、圧縮部分系列後続部決定部１４２は、選択された上記経験分布別圧縮系列表の中から、分割系列対（ｘ〜ｍ（ｊ），ｙ〜ｍ（ｊ））に対応する枠（図４（ｃ））を検出し、その枠に割り当てられた（２０）式に示す圧縮系列を導出（抽出）する。
【００８０】
【数２０】
【００８１】
ここで、ｃ2（ｊ）は、ｊ番目の分割系列対に対応する圧縮系列の長さである。上記経験分布別圧縮系列表作成部１１２は、ｃ2（ｊ）を、ｊ番目の分割系列対の同時経験分布Ｑj＝Ｑｍｘ〜ｍ（ｊ），ｙ〜ｍ（ｊ）によって決定、すなわち、以下の（２１）式にて求める。
【００８２】
【数２１】
【００８３】
そして、経験分布別圧縮系列表作成部１１２は、この圧縮系列Ｚ〜ｃ２（ｊ）（ｊ；２）を、分割系列対（ｘ〜ｍ（ｊ），ｙ〜ｍ（ｊ））に対応する圧縮部分系列の後続部とする。
上述したように、圧縮部分系列決定部１４は、抽出された圧縮部分系列の先頭部ｚ〜ｃ１（ｊ；１）と後続部ｚ〜ｃ２（ｊ；２）とを連結した（２２）式に示す系列ｚ〜ｃ（ｊ）を圧縮部分系列とし、これら系列対を分割した分割系列各々に対応する圧縮部分系列の集合を出力する。
ここで、＊は系列の連接を表す演算子であり、ｃ（ｊ）＝ｃ1＋ｃ2(j)はｊ番目の分割系列対に対応する圧縮部分系列の長さである。
【００８４】
【数２２】
【００８５】
圧縮系列生成部１５は、上記圧縮部分系列決定部１４から出力される圧縮部分系列の集合を入力し、その集合における圧縮部分系列を統合することにより、第１系列及び第２系列に対応する圧縮系列を生成し、この生成した圧縮系列を出力する。
本実施形態において、第１系列ｘｎ及び第２系列ｙｎに対応する圧縮系列ｚｃ＊（ｘｎ，ｙｎ）は、以下の（２３）及び（２４）式に示すように決定される。
【００８６】
【数２３】
【００８７】
【数２４】
【００８８】
上記（２３）及び（２４）式において、ｃ＊は第１系列ｘｎ及び第２系列ｙｎに対応する圧縮系列の長さを示している。
この圧縮系列の構成は、最終的に、圧縮系列生成部１５において、各圧縮部分系列を連結した後に、最後に上記系列分割部１２で系列長ｍ未満の系列長を有する余った部分系列を圧縮せずにそのまま連結したものである。
上述したように、系列圧縮部１は、入力される第１系列ｘｎ及び第２系列ｙｎから、上記圧縮系列ｚｃ＊（ｘｎ，ｙｎ）を生成して出力する。
【００８９】
次に、系列圧縮部１が圧縮した圧縮系列を復元する復元部２及び復元部３の説明を行う。この説明において、復元部２及び復元部３における復元処理は、復元の際に用いる系列（第１系列あるいは第２系列）が異なるのみで、同様な復元処理が行われるため、代表として、第２系列ｙｎを有する復元部２を用いて説明する。
復元部２は、系列圧縮部１から出力された圧縮系列ｚｃ＊（ｘｎ，ｙｎ）と、予め端末２０１の記憶部に記憶されている第２系列とを入力し、これら圧縮系列ｚｃ＊（ｘｎ，ｙｎ）と第２系列ｙｎとから第１系列ｘｎを復元し、復元された第１系列である復元第１系列を出力する。
【００９０】
上記復元部２は、系列の復元方法、すなわち復元処理を行う構成として特に限定されるものではないが、本実施形態において、例えば図６に示すように、圧縮系列分割部２１と、圧縮系列表同定部２２と、分割系列復元部２３と、復元系列生成部２４とから構成されている。
圧縮系列分割部２１は、上記圧縮系列ｚｃ＊（ｘｎ，ｙｎ）を入力し、圧縮系列を分割することで圧縮部分系列を復元し、復元した圧縮部分系列である復元圧縮部分系列についてその集合を出力する。
【００９１】
すなわち、本実施形態において、圧縮系列分割部２１は、圧縮部分系列を、以下の処理にして復元する。
説明上において、圧縮系列分割部２１が、入力された圧縮系列ｚｃ＊（ｘｎ，ｙｎ）から、すでに以下の（２５）式に示すように、ｊ−１番目までの復元圧縮部分系列を復元しているものとする。この（２５）式において、ｃ＾（ｊ）は、ｊ番目の復元圧縮部分系列の系列長である。
【００９２】
【数２５】
【００９３】
ここで、圧縮系列分割部２１は、圧縮系列ｚｃ＊（ｘｎ，ｙｎ）におけるσｊ番目の文字を先頭としてｃ１個の文字を切り出し、このｃ１個の文字をｊ番目の復元圧縮部分系列の先頭部ｚ＾ｃ１（ｊ；１）する。ここで、σｊは以下の（２６）式により求められる。また、ｃ1はすでに圧縮処理にて述べたように、第１系列及び第２系列のデータに依存せずに、定数（＝｜Ｖ×Ｗ｜log｜Ｚ｜（ｍ＋１））である。
【００９４】
【数２６】
【００９５】
上記圧縮系列分割部２１は、すでに述べた圧縮部分系列先頭部決定部１４１と同様の処理により、上述した処理において、圧縮系列ｚｃ＊（ｘｎ，ｙｎ）から切り出した復元圧縮部分系列の先頭部ｚ＾ｃ１（ｊ）から、ｊ番目の分割系列対の同時経験分布Ｑ＾ｊを復元できる。 さらに、圧縮系列分割部２１は、上記圧縮部分系列後続部決定部１４２と同様の処理により、復元された同時経験分布である復元同時経験分布Ｑ＾ｊから、ｊ番目の圧縮部分系列の後続部の系列長ｃ２＾(j)を算出（同定）することができる。
【００９６】
上述したように、圧縮系列分割部２１は、圧縮系列ｚｃ＊（ｘｎ，ｙｎ）のσｊ＋ｃ1番目の文字を先頭とするｃ2＾（ｊ）個の文字を切り出すことで、ｊ番目の復元圧縮部分系列の後続部ｚ＾ｃ２＾（ｊ）（ｊ；２）を生成する。
そして、圧縮系列分割部２１は、先頭部ｚ＾ｃ１（ｊ）と後続部ｚ＾ｃ２＾（ｊ）（ｊ；２）とを連結することにより、ｊ番目の復元圧縮部分系列ｚ＾ｃ＾（ｊ）（ｊ）を生成する。ここで、c＾(j)＝ｃ1＋ｃ２＾（ｊ）である。
上記の操作を、圧縮系列分割部２１がｊ＝１，…，ｌのｌ回繰り返して実行することにより、ｌ番目までの復元圧縮部分系列ｚ＾ｃ＾（ｊ）（ｊ）（ｊ＝１，…，ｌ）が復元される。
そして、圧縮系列分割部２１は、圧縮系列から切り出されなかった残りのｃ＊−σｌ個の文字を、ｌ＋１番目の復元圧縮部分系列ｚ＾ｃ＾（ｌ＋１）（ｌ＋１）として出力する。ここで、ｃ＾（ｌ＋１）＝ｃ＊−σｌである。
【００９７】
上記圧縮系列表同定部２２は、圧縮系列分割部２１が出力する上記復元圧縮部分系列の集合を入力し、その復元圧縮部分系列の各々について、その圧縮部分系列を生成した圧縮系列表を、予め記憶部に記憶されている圧縮系列表集合から同定（抽出）し、その同定された圧縮系列表である復元圧縮系列表の集合を出力する。
ここで、圧縮系列表同定部２２は、上記圧縮系列表として、すでに系列圧縮部１の経験分布別圧縮系列表作成部１１２にて生成されたものと同一の経験分布別圧縮系列表の圧縮系列表集合を予め内部の記憶部に記憶している。たとえば、送信側端末１００がこの圧縮系列表を作成し、この圧縮系列表が所定の周期にて送信側端末１００から受信側端末２０１，２０２，…に対して周期的に送信され、系列圧縮部１と各系列復元部との間にて同期が取られている。
この圧縮系列表同定部２２は、本実施形態において、復元圧縮系列表を、以下のようにして同定する。
圧縮系列表同定部２２は、ｊ番目の復元圧縮部分系列ｚ＾ｃ＾（ｊ）（ｊ）の先頭ｃ1個の文字、すなわち先頭部ｚ＾ｃ１（ｊ）を切り出す。
【００９８】
そして、圧縮系列表同定部２２は、この先頭部ｚ＾ｃ１（ｊ）からｊ番目の分割系列対の復元同時経験分布必を同定するとともに、この同時経験分布に対応する経験分布別圧縮系列表も同定する。この同定される経験分布別圧縮系列表を、ｊ番目の分割系列対の復元に用いる復元圧縮系列表とする。
圧縮系列表同定部２２は、上述した操作を、ｊ＝１，…，ｌについて繰り返すことにより、ｊ個の表からなる集合を得る。ただし、圧縮系列表同定部２２は、ｌ＋１番目の分割系列対については、圧縮が行われていないため上述した処理を行わない。
【００９９】
上記分割系列復元部２３は、上記復元部分系列の集合、復元圧縮系列表の集合、及び第２系列を入力し、復元圧縮部分系列の各々、及び各復元圧縮系列に対応して第２系列から得られる第２分割系列の集合を用い、その復元圧縮部分系列に対応して得られた復元圧縮系列表から第１分割系列を復元して、この復元された分割系列である復元第１分割系列の集合を出力する。
分割系列復元部２３は、本実施形態において、復元第１分割系列を、以下のようにして求めている。
【０１００】
このとき、分割系列復元部２３は、系列分割部１２と同様の処理により、第２系列ｙｍを第２分割系列の集合ｙ〜ｍ（ｊ）（ｊ＝１，２，…，ｌ）に分割する。
分割する。
次に、分割系列復元部２３は、ｊ番目の復元圧縮部分系列ｚ＾ｃ＾（ｊ）（ｊ）の後続ｃ2 ＾（ｊ）個の文字を抽出してｚ＾ｃ２＾（ｊ）（ｊ）として切り出す。
そして、分割系列復元部２３は、ｊ番目の復元圧縮系列表を参照して、ｊ番目の復元圧縮系列表における第２分割系列ｙ〜ｍ（ｊａ）に対応する列を検出する。
【０１０１】
次に、分割系列復元部２３は、その検出した列から、復元圧縮部分系列の後続部ｚ＾ｃ２＾（ｊ）（ｊ）が存在する枠を検出する。
そして、分割系列復元部２３は、検出された上記枠の存在する行を検出し、この枠に対応する行の第１分割系列を、ｊ番目の復元第１分割系列ｘ＾ｍ（ｊ）とする。
分割系列復元部２３は、上述した処理をｊ＝１，…，ｌについて、すなわちｌ回繰り返し実行することにより、ｌ番目までの復元第１分割系列ｘ＾ｍ（ｊ）（ｊ＝１，…，ｌ）が復元される。
また、分割系列復元部２３は、ｌ＋１番目の復元圧縮部分系列ｚ＾ｃ＾（ｌ＋１）（ｌ＋１）に対し、その前半部分ｚ１＾（ｌ＋１）／２（ｌ＋１）を切り出し、それをｌ＋１番目の復元第１分割系列ｘ＾ｌ＋１とする（後半部分はｚ１＾（ｌ＋２）／２（ｌ＋１）は第２分割系列ｙ＾ｌ＋１に対応）。
【０１０２】
本第１の実施形態においては、どのような第１系列及び第２系列が入力として与えられても、必ず同一の系列を復元することができる。すなわち、第１系列と第１復元系列とは、また第２系列と第２復元系列とは同一である。このとき、ｃ＾（ｌ＋１）＝ｃ＊−σｌが２mod（ｎ，ｍ）と一致する。
後述する第２の実施形態においては、詳細は後述するが、必ずしも同一の系列を復元できるとは限らないが、ｃ＊−σｌと２mod（ｎ，ｍ）とが一致するように構成される。詳細は第２の実施例にて記述する。
【０１０３】
復元第１系列生成部２４は、上記復元第１分割系列の集合を入力し、それら復元第１分割系列を統合することにより、第１系列を復元し、復元した系列である復元第１系列を出力する。
そして、復元第１系列生成部２４は、（２７）式に示すように上記復元第１分割系列を連結することにより、復元第１系列ｘ＾ｎを復元する。このようにして、第１系列復元部２は、送信側端末１００から、自身に対して送信された送信信号として上記復元第１系列ｘ＾ｎを出力する。
【０１０４】
【数２７】
【０１０５】
次に、第２系列復元部３は、第１の系列復元部２と同様な構成及び処理により、圧縮系列の復元を行うため詳細な説明を省略するが、予め記憶部に第１系列が記憶された受信側端末２０２に設けられているため、この第１系列と入力される圧縮系列ｚｃ＊（ｘｎ，ｙｎ）とから、第１系列復元部２と同様な構成及び処理により、以下の（２８）式に示す第２系列を求める。
【０１０６】
【数２８】
【０１０７】
このとき、第２系列復元部３における分割系列復元部２３は、ｌ＋１番目の復元圧縮部分系列ｚ＾ｃ＾（ｌ＋１）（ｌ＋１）に対し、以下の（２９）式に示す前半部分を切り出し、それをｌ＋１番目の復元第１分割系列ｙ＾ｌ＋１とする。
【０１０８】
【数２９】
【０１０９】
＜第２の実施形態＞
本実施形態における信号系列の伝送を行う伝送システムとしては、第１の実施形態と同様に図１の概念図に示すように、信号系列を圧縮する信号系列圧縮部１が信号系列を送信する送信側装置に設けられ、圧縮された信号系列（圧縮信号系列）を復元する系列復元部２（あるいは３）が受信側端末に設けられている。以下、第１の実施形態と同様の処理を行う処理部については説明を省略し、第１の実施形態と異なる部分のみを説明する。
【０１１０】
系列対分類選択部１１３は、すでに述べた系列対分類部１１１から出力される分類の集合を入力する。
そして、系列対分類選択部１１３は、入力された分類の集合の中から、分類に所属する系列に対応する圧縮系列の長さが、あらかじめ定められた閾値である圧縮系列長閾値を下回る（未満の）分類のみを選択し、この選択された分類の集合を出力する。
また、第１の実施形態における圧縮部分系列決定部１４に示した処理と同様に、ある同時経験分布Ｑについて、その同時経験分布Ｑに対応する分類（すなわち、その同時経験分布を有する系列対の集合）ＴｍＱに含まれる分割系列対から得られる圧縮部分系列の長さが、ｃ1＋ｃ2（Ｑ）であることがわかる。
【０１１１】
ここで、圧縮系列長閾値ｒを導入し、経験分布別圧縮系列表作成部１１２は、以下に示す（３０）式を満たす同時経験分布Ｑ、及びその同時経験分布Ｑに対応するＴｍＱを選択し、選択された分類の集合を出力する。
【０１１２】
【数３０】
【０１１３】
経験分布別圧縮系列表作成部１１２は、上記系列対分類選択部１１３から出力された分類の集合を入力し、入力した各分類に含まれる系列対各々に対応する圧縮系列を定め、系列対と圧縮系列との対応関係を示す圧縮系列表である経験分布別圧縮系列表を作成し、この経験分弁別圧縮系列表の集合を出力する。
ここで、経験分布別圧縮系列表作成部１１２の処理において、上記系列対分類選択部１１３にて選択された分類については、すでに述べた第１の実施形態における処理と同様である。しかしながら、本第２の実施形態においては、系列対分類選択部１１３により選択されなかった分類については、経験分布別圧縮系列表を作成しない。このような処理により、上記系列対分類選択部１１２で選択されなかった分類については、特定の圧縮系列が割り当てられないこととなる。
【０１１４】
圧縮部分系列後続部決定部１４２は、すでに第１の実施形態にて述べた圧縮系列表作成部１１から出力された経験分布別圧縮系列表の集合、系列分割部１２から出力された分割系列対の集合、及び系列経験分布導出部１３から出力された同時経験分布の集合を入力する。
そして、圧縮部分系列後続部決定部１４２は、入力された分割系列対の各々について、その分割系列対の同時経験分布に対応する経験分布別圧縮系列表から、その分割系列対に対応する圧縮系列を導出（抽出）し、これを圧縮部分系列の後続部として決定し、その圧縮部分系列の後続部の集合を出力する。
【０１１５】
このとき、圧縮部分系列後続部決定部１４２は、上記経験分布別圧縮系列表作成部１１３で経験分布別圧縮系列表が作成されている同時分布を有する分割系列対に対し、第１の実施形態と同様の処理を行う。
一方、圧縮部分系列後続部決定部１４２は、経験分布別圧縮系列表が作成されていない同時分布を有する分割系列対に対し、系列長ｃ2（ｊ）のランダムな系列を割り当て、これを圧縮部分系列の後続部とする。
【０１１６】
またさらに別の実施形態として、圧縮部分系列後続部決定部１４２は、圧縮系列長を全て一定にすることも可能である。
このとき、元々の圧縮系列長が圧縮系列長閾値に満たないとき、圧縮系列に適切な数の文字を埋めることにより、系列長をｒとして揃えることができる。経験分布別圧縮系列表が作成されていない同時分布を有する分割系列対に対しては、系列長ｒのランダムな系列を割り当てる。
この第２及び別の実施形態においては、前記系列対分類選択部１１２で選択されなかった分類に含まれる分割系列対については、上記第１系列復元部２及び第２系列復元部３において、必ずしも第１系列及び第２系列を復元できるとは限らないことに注意する。
【０１１７】
なお、図１における信号系列圧縮部１，系列復元部２，系列復元部３それぞれの機能を実現するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、それぞれのシステムにおいて圧縮または復元を行うプロセスとして実行することにより各機能の処理を行ってもよい。なお、ここでいう「コンピュータシステム」とは、ＯＳや周辺機器等のハードウェアを含むものとする。また、「コンピュータシステム」は、ホームページ提供環境（あるいは表示環境）を備えたＷＷＷシステムも含むものとする。また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムが送信された場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリ（ＲＡＭ）のように、一定時間プログラムを保持しているものも含むものとする。
【０１１８】
また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されてもよい。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。また、上記プログラムは、前述した機能の一部を実現するためのものであっても良い。さらに、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるもの、いわゆる差分ファイル（差分プログラム）であっても良い。
【図面の簡単な説明】
【０１１９】
【図１】本発明の第１及び第２の実施形態による信号圧縮装置及び信号復元装置を用いた信号伝送システムの概念図である。
【図２】本発明の第１及び第２の実施形態による信号圧縮装置の構成例を示すブロック図である。
【図３】図２における圧縮系列表作成部１１の圧縮系列表作成処理の動作を説明する圧縮系列表の概念図である。
【図４】図２における圧縮系列表作成部１１の圧縮系列表生成における動作を示すフローチャートである。
【図５】経験分布別圧縮系列表作成部１１３による各経験分布別圧縮系列表への識別番号の割り当て処理を説明するための２部グラフの概念図である。
【図６】本発明の第１及び第２の実施形態による信号復元装置の構成例を示すブロック図である。
【符号の説明】
【０１２０】
１…信号系列圧縮部
２，３…系列復元部
１１…圧縮系列表作成部
１２…系列分割部
１３…系列経験分布導出部
１４…圧縮部分系列決定部
１５…圧縮系列生成部
２１…圧縮系列分割部
２２…圧縮系列表同定部
２３…分割系列復元部
２４…復元系列生成部
１００…送信側端末
１１１…系列対分類部
１１２…経験分布別圧縮系列表作成部
１１３…系列対分類選択部
１４１…圧縮部分系列先頭部決定部
１４２…圧縮部分系列後続部決定部
２０１，２０２…受信側端末
【技術分野】
【０００１】
本発明は、音楽、静止画像、動画像及びテキストファイルなどのコンテンツを送受信する際の圧縮及び復元を行う信号圧縮方法、信号復元方法、それら装置、プログラム並びにそれらプログラムを記録した記録媒体に関する。
【背景技術】
【０００２】
近年、音楽・映像を取得あるいは生成するデバイスの普及、また大容量ネットワークの普及などにより、音楽・静止画像・動画像・テキストなどを含む多様なコンテンツのマルチメディア信号がネットワーク上を流通し、それらコンテンツを各個人のレベルにて蓄積する機会が増大している。
しかし、パーソナルコンピュータにおける記憶媒体の大容量化・低価格化、及びネットワークにおける伝送の大容量化に対し、それを上回る速度にて、取り扱う情報量が増大してきている。
【０００３】
このため、記憶媒体の容量不足やネットワークトラフィックの過度の増大を避けるための手段の一つとして、信号を再度復元可能な形にて圧縮する技術が必須となってきている。
特に、携帯端末や衛星を介した信号伝送において、通信容量の制限及びネットワーク構成の複雑性などの理由から、上記マルチメディア信号を圧縮して伝送する技術が求められている。
【０００４】
上述した携帯端末や衛星を介した信号伝送は、複数の信号提供者（＝送信者）と複数の信号被提供者（＝受信者）との存在を仮定している。
さらに、圧縮及び復元を行う実用上の観点から、伝送されるマルチメディア信号がどのような確率構造に基づいて発生するかの知識がなくても、それら知識を持っている場合と同等の効率にて圧縮が行えて伝送できることが望ましい。
【０００５】
このような信号伝送における信号圧縮技術として、例えば、非特許文献１に記載された圧縮方法が知られている。
【非特許文献１】T. Uyematsu, "An algebraic construction of codes for Slepian-Wolf source networks,"IEEE Transactions on Information Theory, Vol. 47, No. 7, pp. 3082-3088, November 2001.
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、非特許文献１に記載の方法においては、複数の送信者と１人の受信者とを想定した信号伝送に対する信号圧縮技術のみについてが記載されている。
そのため、非特許文献１に記載の方法は、一人の送信者が複数の受信者に対して信号伝送を行うことができない。
一方、非特許文献１とは逆に、一人の送信者が複数の受信者に対して、それぞれ異なる情報を同時に行う信号伝送に対応する信号圧縮技術が確立されることが望まれている。特に、衛星を用いた放送型通信はその典型例である。
【０００７】
本発明は、このような事情に鑑みてなされたもので、一人の送信者と複数の受信者とにおける信号伝送において、各受信者に対してそれぞれ異なるマルチメディア信号を同時に送信する場合、ネットワークにおけるトラフィックを低減し、各受信者が受信する信号を効率的に圧縮復元が可能な信号圧縮方法及び信号復元方法を提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明の信号圧縮方法は、伝送の対象となる２つの信号系列である第１信号系列及び第２信号系列について、これら信号系列を、２つの信号系列のうちいずれかの信号系列を所有する複数の受信者へ伝送する信号伝送に用いる、上記信号系列を圧縮する信号圧縮方法であり、圧縮信号系列表作成部が、設定された一定の長さの系列長を有する任意の２つの信号系列からなる信号系列対に対し、該信号系列対の経験確率分布を用いて、信号系列対に対応する圧縮信号系列を設定し、信号系列対と圧縮信号系列との対応関係を示す圧縮信号系列表を生成し、該圧縮信号系列表を記憶部に記憶する圧縮信号系列表作成過程と、信号系列分割部が、入力される第１信号系列及び第２信号系列各々を、前記系列長の信号系列に分割し、第１分割信号系列及び第２分割信号系列の対である分割信号系列対の集合を抽出する信号系列分割過程と、分割信号系列対経験分布導出部が、前記分割信号系列対の各々の経験確率分布を求める分割信号系列対経験分布導出過程と、圧縮信号部分系列決定部が、前記分割信号系列対の各々に対応する前記経験確率分布及び前記圧縮信号系列表を参照し、該分割信号系列対に対応する圧縮信号系列である圧縮信号部分系列を定める圧縮信号部分系列決定過程と、圧縮信号系列生成部が、前記圧縮信号部分系列の集合から、それら圧縮信号部分系列を統合することにより、第１信号系列及び第２信号系列に対応する圧縮信号系列を生成する圧縮信号系列生成過程とから構成されることを特徴とする。
【０００９】
本発明の信号圧縮方法は、前記圧縮信号系列表作成過程は、信号系列対分類部が前記系列長を有する任意の信号系列の信号系列対に対し、該信号系列対の経験確率分布にて分類する信号系列対分類過程と、経験分布別圧縮信号系列表作成が前記信号系列対分類過程で得られた分類各々に対し、それぞれの分類に含まれる信号系列対各々に対応する圧縮信号系列を定め、信号系列対と圧縮信号系列との対応関係を示す圧縮信号系列表である経験分布別圧縮信号系列表を作成して記憶部に記憶する経験分布別圧縮信号系列表作成過程とから構成されることを特徴とする。
【００１０】
本発明の信号圧縮方法は、前記圧縮信号部分系列決定過程は、圧縮信号部分系列先頭決定部が、前記分割信号系列対の各々に対し、それぞれの分割信号系列対の経験確率分布に対応する番号もしくはその番号に対応する系列を、圧縮信号部分系列の先頭部分として設定する圧縮信号部分系列先頭部決定過程と、圧縮信号部分系列後続部決定部が、前記分割信号系列対の各々について、それぞれの分割信号系列対の経験確率分布に対応する経験分布別圧縮信号系列表を参照し、分割信号系列対に対応する圧縮信号系列を導出し、該圧縮信号系列を圧縮信号部分系列の後続部分として設定する圧縮信号部分系列後続部決定過程とから構成されることを特徴とする。
【００１１】
本発明の信号圧縮方法は、信号系列対分類選択部が前記信号系列対分類過程にて得られた分類の集合から、該分類に所属する信号系列対に対応する圧縮信号系列の長さが、あらかじめ設定された閾値である圧縮系列長閾値を下回る分類のみを選択する信号系列対分類選択過程をさらに有し、前記経験分布別圧縮信号系列表作成過程が、前記信号系列対分類選択過程にて選択された前記分類に対して圧縮信号系列表を作成し、前記圧縮信号部分系列後続部決定過程において、圧縮信号部分系列後続部が、圧縮信号系列表が作成されていない分類に対し、任意の系列を圧縮信号部分系列の後続部分として決定することを特徴とする。
【００１２】
本発明の信号復元方法は、複数の受信者へ信号系列を伝送する際、予め受信者が有する信号系列と、伝送の対象となる他の信号系列との２つの信号系列からなる圧縮された圧縮信号系列を復元する信号復元方法であり、圧縮信号系列分割部が、前記圧縮信号系列を分割し、復元圧縮信号部分系列を生成する圧縮信号系列分割過程と、圧縮信号系列表同定部が、前記圧縮信号系列分割過程にて得られた復元圧縮信号部分系列の各々に対し、それぞれの圧縮信号部分系列に対応する圧縮信号系列表を、圧縮信号部分系列に対応して圧縮信号系列表が記憶されている記憶部から同定する圧縮信号系列表同定過程と、分割信号系列復元部が、前記復元圧縮信号部分系列各々と、前記予め受信者が有する信号系列を予め設定された系列長にて分割して生成した第２分割信号系列とにより、その復元圧縮信号部分系列に対応して前記圧縮信号系列表同定過程にて得られた圧縮信号系列表である復元圧縮信号系列表から、前記第２分割信号系列の対である分割信号系列を読み出し、復元第１分割信号系列とする分割信号系列復元過程と、復元信号系列生成部が、前記分割信号系列復元にてえられた前記復元第１分割信号系列の集合から、それら復元第１分割信号系列を統合することにより、予め受信者が有する信号系列と対をなす伝送の対象となる他の信号系列を復元する復元信号系列生成過程とから構成されることを特徴とする。
【００１３】
本発明の信号復元方法は、前記圧縮信号系列表同定過程において、前記圧縮信号系列表同定部が前記圧縮信号系列分割過程にて得られた復元圧縮信号部分系列各々について、それぞれの圧縮信号部分系列の先頭部分から、その圧縮信号部分系列を生成した経験分布別圧縮信号系列表を同定し、前記先頭部分がそれぞれの分割信号系列対の経験確率分布に対応する番号もしくはその番号に対応する系列であることを特徴とする。
【００１４】
本発明の信号圧縮装置は、伝送の対象となる２つの信号系列である第１信号系列及び第２信号系列について、これら信号系列を、２つの信号系列のうちいずれかの信号系列を所有する複数の受信者へ伝送する信号伝送に用いる、上記信号系列を圧縮する信号圧縮装置であり、設定された一定の長さの系列長を有する任意の２つの信号系列からなる信号系列対に対し、該信号系列対の経験確率分布を用いて、信号系列対に対応する圧縮信号系列を設定し、信号系列対と圧縮信号系列との対応関係を示す圧縮信号系列表を生成し、該圧縮信号系列表を記憶部に記憶する圧縮信号系列表作成部と、入力される第１信号系列及び第２信号系列各々を、前記系列長の信号系列に分割し、第１分割信号系列及び第２分割信号系列の対である分割信号系列対の集合を抽出する信号系列分割部と、前記分割信号系列対の各々の経験確率分布を求める分割信号系列対経験分布導出部と、前記分割信号系列対の各々に対応する前記経験確率分布及び前記圧縮信号系列表を参照し、該分割信号系列対に対応する圧縮信号系列である圧縮信号部分系列を定める圧縮信号部分系列決定部と、前記圧縮信号部分系列の集合から、それら圧縮信号部分系列を統合することにより、第１信号系列及び第２信号系列に対応する圧縮信号系列を生成する圧縮信号系列生成部とから構成されることを特徴とする。
【００１５】
本発明の信号復元装置は、複数の受信者へ信号系列を伝送する際、予め受信者が有する信号系列と、伝送の対象となる他の信号系列との２つの信号系列からなる圧縮された圧縮信号系列を復元する信号復元装置であり、前記圧縮信号系列を分割し、復元圧縮信号部分系列を生成する圧縮信号系列分割部と、前記圧縮信号系列分割部にて得られた復元圧縮信号部分系列の各々に対し、それぞれの圧縮信号部分系列に対応する圧縮信号系列表を、圧縮信号部分系列に対応して圧縮信号系列表が記憶されている記憶部から同定する圧縮信号系列表同定部と、前記復元圧縮信号部分系列各々と、前記予め受信者が有する信号系列を予め設定された系列長にて分割して生成した第２分割信号系列とにより、その復元圧縮信号部分系列に対応して前記圧縮信号系列表同定部にて得られた圧縮信号系列表である復元圧縮信号系列表から、前記第２分割信号系列の対である分割信号系列を読み出し、復元第１分割信号系列とする分割信号系列復元部と、前記分割信号系列復元にてえられた前記復元第１分割信号系列の集合から、それら復元第１分割信号系列を統合することにより、予め受信者が有する信号系列と対をなす伝送の対象となる他の信号系列を復元する復元信号系列生成部とから構成されることを特徴とする。
【００１６】
本発明のプログラムは、コンピュータに上記いずれかに記載の信号圧縮方法を実行させるためのコンピュータが実行可能なプログラムである。
【００１７】
本発明のプログラムは、コンピュータに上記いずれかに記載の信号復元方法を実行させるためのコンピュータが実行可能なプログラムである。
【００１８】
本発明のコンピュータ読み取り可能な記録媒体は、上記いずれかに記載のプログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の効果】
【００１９】
本発明によれば、１人の送信者と複数の受信者を想定した場合、マルチメディア信号を各受信者の端末に送信する際、２つの信号系列を１つの圧縮信号系列として送信するため、ネットワークにおけるトラフィックを低減することができる。
また、本発明によれば、２つの信号系列対と圧縮系列信号との対応を示す圧縮信号系列表を、圧縮側と復元側とがそれぞれの記憶部に共通に記憶しているため、圧縮信号系列と信号系列対の一方の信号系列とにより、上記圧縮信号系列表から他方の信号系列を抽出することにより、効率的に圧縮及び復元が可能である。
【発明を実施するための最良の形態】
【００２０】
本発明で言及する信号伝送においては、図１に示すように、１人の送信者と複数の受信者を想定する際、送信者が所有する２つの信号のうちいずれか１つの信号を各受信者が所有している場合、各受信者が所有していない信号を受信できるように、送信者が信号を圧縮し、全ての受信者に対して同一の圧縮信号を送信者から伝送する。図１は本発明の実施形態による伝送システムの構成を示す概念図である。
本発明の信号伝送においては、通常、送信者が所有する信号を受信者が正しく受信できない確率が無視できる程度に小さくすることが要求される。
【００２１】
このとき、信号の圧縮率をエントロピーを用いて表現したときの理論的限界値、及び圧縮率がその理論的限界値に漸近する信号圧縮方法の存在が、以下の非特許文献２及び３に示されている。
（非特許文献2）A・ D. Wyner, J. K. Wolf, and F・ M. J. Willems“Communicating via a processing broadcast satellite,”IEEE Transactions on Information Theory, Vol・ 48, N0. 6, pp. 1243-1249, June 2002.
（非特許文献3) A. Kimura and T. Uyematsu, "Multiterminal source coding with complementary delivery,”Proc. International Symposium on Information Theory and its Applications(ISITA), pp. 189-194,October 2006.
【００２２】
上述したように、本発明においては、伝送すべき信号が従う確率構造についての知識がなくても、圧縮率が上記非特許文献２及び３に示される理論的限界値に漸近する信号圧縮方法を示すものである。
そのため、本発明においては、後に詳述するが、以下のａ及びｂの２点により、上記の理論的限界値に漸近する信号圧縮を行い信号伝送方法を実現している。
ａ．与えられた２つの信号系列のみから得られる経験的な確率分布（以下、同時経験分布）を用いることにより、信号系列がどのような確率構造に基づいて生成されたかについての知識がなくても、圧縮率が理論的限界値に漸近する信号圧縮を可能にする。
ｂ．与えられた２つの信号系列を圧縮する際に、その同時経験分布に基づき、信号系列対と圧縮系列信号との対応関係を示す表を作成することにより、受信者が所有している情報を基に、受信者が所有していない情報を復元する操作を容易に行う。
【００２３】
＜第１の実施形態＞
本実施形態における信号系列の伝送を行う伝送システムとしては、図１の概念図に示すように、信号系列を圧縮する信号系列圧縮部１が信号系列を送信する送信側装置に設けられ、圧縮された信号系列（圧縮信号系列）を復元する系列復元部２（あるいは３）が受信側端末に設けられている。
【００２４】
ここで、送信側装置１００は伝送の対象となる２つの信号系列である第１信号系列Ｘｎ及び第２信号系列Ｙｎを入力し、これら信号系列から圧縮信号系列Ｚを生成し、この圧縮信号系列Ｚを２つの信号系列Ｘｎ及びＹｎのいずれかの信号系列を所有する（端末の記憶部に記憶されている）複数の受信側端末２０１、２０２、…へ伝送する。
一方、受信側端末２０１、２０２、…各々は、自身が所有している信号系列を用いて、上記圧縮信号系列から、自身の所有していない信号系列を、それぞれの系列復元部により復元し、その復元した信号系列である復元信号系列Ｘ〜ｎあるいはＹ〜ｎを出力する。
【００２５】
以下の説明において、簡単化のため、全ての信号系列を文字系列であるとし、信号系列を単に系列と呼ぶ。第１信号系列、第２信号系列及び復元信号系列についても、同様に、それぞれを第１系列、第２系列、復元系列と呼ぶ。
また、第１系列と第２系列とは、特に断らない限りにおいて、同一の長さｎを持つと仮定する。
また、第１系列ｘｎの各文字列ｘｉ（ｉ＝１，２，…，ｎ）は有限文字集合である。
【００２６】
上記信号系列圧縮部１は、第１系列ｘｎ及び第２系列ｙｎを入力し、これら系列を複合して圧縮した圧縮系列を抽出し、その抽出された圧縮系列を出力する。
圧縮系列の抽出方法は特に限定されるものではないが、本実施形態においては、例えば以下に示す構成により行う。
信号系列圧縮部１は、図２に示すように、圧縮系列表作成部１１と、系列分割部１２と、系列経験分布導出部１３と、圧縮部分系列決定部１４と、圧縮系列生成部１５とを有している。図２は信号系列圧縮部１の構成例を示すブロック図である。
【００２７】
上記圧縮系列表作成部１１は、以下に示す図３のフローチャートの流れに従い、ある一定の長さを持つ任意の系列の対について、その系列対の同時経験分布を用い、その系列対に対応する圧縮系列を定め、系列対と圧縮系列との対応関係を示す表である圧縮系列表を作成し、その圧縮系列表を出力する。上記図３は、圧縮系列表作成部１１における圧縮系列表の生成処理の動作例を示すフローチャートである。
圧縮系列表作成部１１による圧縮系列表の作成方法は特に限定されるものではないが、本実施形態においては、例えば以下に示す構成によって作成する。
圧縮系列表作成部１１は、例えば、系列対分類部１１１と、経験分布別圧縮系列表作成部１１２とによって構成される作成方法について、図３のフローの処理に従って述べる。
【００２８】
系列対分類部１１１は、ある一定の長さを持つ任意の系列対を同時経験分布、すなわち、同一の経験確率分布を有する系列対の集合により分類し、その分類の集合を経験分布共有系列対集合として出力する。本実施形態において、系列対分類部１１１は、系列対を以下のようにして分類する。
系列対分類部１１１は、分類に用いる系列の長さである系列長ｍを設定する。ここで設定される系列長ｍは、ユーザが入力しても良いし、あるいは系列対分類部１１１が第１系列及び第２系列の文字数にて決定してもよい。この系列長ｍは、第１系列及び第２系列の系列長ｎと同一である必要はないが、ｍ≦ｎを満たす必要がある。
【００２９】
次に、系列対分類部１１１は、系列長ｍである系列の系列対(ｘ〜ｍ，ｙ〜ｍ)が入力されると、この任意の系列対について、その経験的な確率分布である同時経験分布Ｑx〜ｍ,y〜ｍ∈Ｐm(Ｖ×Ｗ)を、以下の（１）式から求める。
【００３０】
【数１】
【００３１】
上記（１）式において、Ｎ(ａ，ｂ／ｘ〜ｍ,ｙ〜ｍ)は系列対(ｘ〜ｍ，ｙ〜ｍ)の中で文字対（ａ，ｂ）が生起する回数である。また、Ｐm(Ｖ×Ｗ)は、直積文字集合Ｘ×Ｙからなる系列長ｍの系列についての同時経験分布全体の集合である。ここで、系列対分類部１１１は、同時経験分布全体の集合、すなわち系列対(ｘ〜ｍ，ｙ〜ｍ)における文字の同時経験分布の組み合わせの全てを含む集合を生成し、内部の記憶部に記憶する（ステップＳ１、ステップＳ２）。例えば、系列長ｍ＝４の２元系列の対(ｘ〜ｍ，ｙ〜ｍ)＝（００１０，０００１）について、同時経験分布は、以下の（２）式のように算出される。
【００３２】
【数２】
【００３３】
そして、系列対分類部１１１は、内部に記憶した同時経験分布各々について、その同時経験分布Ｑを有する系列長ｍの系列対の集合ＴｍＱを求める。ＴｍＱは以下の（３）式によって表現される。この同一のＱを有する系列長ｍの系列対の分類した集合を、経験分布共有系列対集合として、順次、経験分布別圧縮系列表作成部１１２に対して出力する（ステップＳ３）。
【００３４】
【数３】
【００３５】
たとえば、上述した系列長ｍ＝４の場合における（２）式に示す同時経験分布Ｑに対して、その経験分布共有系列対集合は、以下の（４）式に示すように文字対（ｘｉ，ｙｊ）からなる系列の組の集合であり、この例では（０，０）の組が２回、（１，０）及び（０，１）の組がそれぞれ１回出現する。
【００３６】
【数４】
【００３７】
そして、経験分布別圧縮系列表作成部１１２は、以下のステップＳ４以降の処理において、上記系列対分類部１１１から出力される経験分布共有系列対集合が入力されると、各経験分布共有系列対集合に含まれる系列対各々に対して圧縮系列を対応させ、それぞれの分類について系列対と圧縮系列との対応関係を示す圧縮系列表である経験分布別圧縮系列表を作成し、この分類毎の経験分布別圧縮系列表を圧縮系列表集合として出力する。ここで、経験分布別圧縮系列表作成部１１２は、図示しない記憶部に、生成した上記経験分布別圧縮系列表の圧縮系列表集合を記憶させる。
【００３８】
ここで、経験分布別圧縮系列表作成部１１２は、分類毎の経験分布別圧縮系列表を、以下のようにして作成する。この作成の過程を、経験分布別圧縮系列行の概念図である図４を用いて説明する。
経験分布別圧縮系列表作成部１１２は、同時経験分布Ｑ各々から、その同時経験分布Ｑに対応する経験分布共有系列対集合ＴｍＱを構成する系列ｘ〜ｍ及びｙ〜ｍの集合、すなわち以下の（５）式に示す系列集合ＴｍＱ；Ｘ、及び（６）式に示す系列集合ＴｍＱ；Ｙをそれぞれ抽出する。
【００３９】
【数５】
【００４０】
【数６】
【００４１】
上述の（２）式にて示した同時経験分布の例において、上記系列集合ＴｍＱ；Ｘ、及び系列集合ＴｍＱ；Ｙを各々は、ぞれぞれ以下の（７）、（８）式に示す集合となる。
【００４２】
【数７】
【００４３】
【数８】
【００４４】
次に、経験分布別圧縮系列表作成部１１２は、図４（ａ）に示すように、抽出した系列対における系列ｘ〜ｍの集合である系列集合ＴｍＱ；Ｘを行の要素とし、系列ｙ〜ｍの集合である系列集合ＴｍＱ；Ｙを列の要素として表を生成し、内部の記憶部に記憶する（ステップＳ４）。
【００４５】
また、経験分布別圧縮系列表作成部１１２は、図４（ｂ）に示すように、該当の同時経験分布を有する系列対に対してに対応する枠（列及び行の交点の座標にある枠）を、それぞれの経験分布共有系列対集合に含まれる同時経験分布と一致するものを抽出し、抽出した枠に対してマークを付与、例えば丸印を書き込む。
すなわち、経験分布別圧縮系列表作成部１１２は、実際にＴｍＱの要素となっている系列対(ｘ〜ｍ，ｙ〜ｍ)を抽出する。図４（ｂ）は、系列対に対するこのような印（「○」マーク）の与え方の１例である。
例えば、経験分布別圧縮系列表作成部１１２は、（１）式にて示した同時経験分布の例において、ｘ１の行を例に取ると、同一の同時経験分布の組み合わせを有する（０００１，００１０）、（０００１，０１００）、（０００１，１０００）に対して印を付加する。
ここで、以下の（９）式が成り立つことから、図４（ａ）の表の枠に対して全て印が与えられるとは限らない。
【００４６】
【数９】
【００４７】
そして、経験分布別圧縮系列表作成部１１２は、（１）式にて示した同時経験分布に対応する経験分布共有系列対集合に対しての処理が終了した後、順次、他の同時経験分布の組み合わせである経験分布共有系列対集合に対応する図４（ｂ）の経験分布別圧縮系列表をそれぞれ生成し、一時的に内部の記憶部に記憶する。
上述したように、経験分布別圧縮系列表作成部１１２は、系列対分類部１１１から入力される経験分布共有結合対集合各々に対応する経験分布別圧縮系列表を生成し、内部の記憶部に記憶する（ステップＳ５）。
【００４８】
次に、経験分布別圧縮系列表作成部１１２は、図４（ｃ）に示すように、上述したように、内部の記憶部に記憶されている経験分布別圧縮系列表を順次読み出し、各経験分布別圧縮系列表毎に印が与えられた枠（抽出された系列対）に対し、圧縮系列対それぞれに対応する識別番号を割り当てる（ステップＳ６及びＳ７）。
このとき、経験分布別圧縮系列表作成部１１２は、後に説明する方法にて、各行及び各列の中において全て相異なる識別番号が割り当てられるようにする。図４（ｃ）は、このような識別番号の割り当て方の１例である。具体的な識別番号の割り当て方法については後述する。
【００４９】
経験分布別圧縮系列表作成部１１２は、上記のようにして作成された|ＴｍＱ；Ｘ|行、｜ＴｍＱ；Ｙ｜列の表を、同時経験分布Ｑについての経験分布別圧縮系列表として出力し、上記記憶部に記憶させる。ここで、個々で用いている｜ＴｍＱ；Ｘ ｜及び｜ＴｍＱ；Ｙ｜各々は、それぞれ集合ＴｍＱに含まれる系列ｘ〜ｍまたは系列ｙ〜ｍの数を示すものである。上記経験分布別圧縮系列表は、後に説明する識別番号の割り当て方法により以下の性質を有するよう形成されている。
１．全ての行について、印が与えられている枠（系列対）の数は同一、例えば図４においては３つずつであり、その枠の数は同時経験分布のみに依存している(ｍｘ（Ｑ）と表す)。
２．全ての列について、印が与えられている枠の数は同一であり、例えば図４においては３つずつであり、その枠の数は同時経験分布のみに依存している（ｍｙ（Ｑ）と表す)。
３．上記のように各系列対に対する識別番号の割り当てを可能とするには、max（ｍｘ（Ｑ），ｍｙ（Ｑ）)種類の相異なる識別番号が必要となる。
【００５０】
上記第３の性質は、経験分布別圧縮系列表が２部グラフ(グラフの頂点を２つの集合に分類でき、同一分類内の頂点の間に辺が存在しないグラフ)と等価であり、その２部グラフの一方の頂点集合について要素数が｜ＴｍＱ；Ｘ ｜かつ各頂点に連結される辺数がｍｘ（Ｑ）、もう一方の頂点集合について要素数が｜ＴｍＱ；Ｙ｜かつ各頂点に連結される辺数がｍｙ（Ｑ）となることによるものである。
【００５１】
上述したことから、経験分布別圧縮系列表作成部１１２による各経験分布別圧縮系列表への識別番号の割り当ては、上記２部グラフに対する辺彩色と等価である。この辺彩色とは、隣り合った辺同士を異なる色で塗ることをいう。
上述したように、経験分布別圧縮系列表作成部１１２は、同時経験分布の分類である経験分布共有系列対集合毎に 経験分布別圧縮系列表を生成する。
【００５２】
上記２部グラフに対する辺彩色の方法としては、どのような方法を用いても良いが、例えば、以下に示す非特許文献４もしくは非特許文献５に記載の方法を用いることができる。
・A. Schrijver: “Bipartite edge coloring in Ｏ(Δｍ) time,” SIAM Journal on Computing,Vol.28, pp.841-846, :1998.(非特許文献４)
・R. Cole, K. Ost, S. Schirra: “Edge coloring bipartite multigraphs in Ｏ(ＥlogＤ）time,”Combinatorica. Vol.21, pp.5-12, 2001.(非特許文献５)
【００５３】
例えば、本実施形態にてはいずれの辺彩色の方法を用いても良いが、上記非特許文献４における方法について以下に説明する。
ここで、図３（ｃ）における枠に対する識別番号の付与処理と等価な２部グラフを図５に示す。
この図において、頂点は各系列対を形成する系列ｘ〜ｍ及びｙ〜ｍに対応しており、２部グラフにおける行（系列ｘ〜ｍに対応）におけるグラフと列（系列ｙ〜ｍに対応）におけるグラフとにおいて、系列ｘ〜ｍ及びｙ〜ｍのそれぞれ系列対を形成している各頂点（すなわち、２部グラフそれぞれの系列）を結ぶ辺（図５における実線Ａ１〜Ａ４、破線Ｂ１〜Ｂ４、破線Ｃ１〜Ｃ４）が、この系列対の識別番号（Ａ１〜Ａ４：識別番号「１」，Ｂ１〜Ｂ４：識別番号「２」，Ｃ１〜Ｃ４：識別番号「３」）に対応している。
【００５４】
１．２部グラフＧの各頂点の次数(当該頂点に連結する辺の数)を揃える。このように、２部グラフの各頂点の次数が全て同一であるときに、この２部グラフを正則２部グラフと呼ぶ。ここで、頂点の次数は、以下のようにして揃える。
Ａ．グラフＧのコピーＧ〜を生成する。
Ｂ．グラフＧの次数の最大値をｋとした場合、グラフＧの各頂点と、コピーされたグラフＧ〜とにおける対応する頂点との間、当該頂点の次数がｋとなるように適切な本数の辺を作成する。
【００５５】
２．上記の手順で生成された正則２部グラフＧ’について、以下の方法により、各辺に対する辺彩色を行う。
Ａ．グラフＧ'の次数が偶数であるとき
ａ．グラフＧ’のオイラー回路を検出する。
ここで、オイラー回路とは、重複する辺を持たないようにある頂点から、他の頂点を辿りある頂点に戻る経路のうち、グラフの全ての辺を含む経路を指している。このオイラー回路検出問題は、いわゆる「一筆書き」問題としてよく知られている。
【００５６】
上記オイラー回路を作成するアルゴリズムとしては、例えば、以下に示すFleuryのアルゴリズムがよく知られている。
すなわち、
ｉ．出発する頂点を任意に選ぶ。
ii．他に選択肢がない場合を除き、取り除くことでグラフが不連結になるような辺を避け、それ以外の辺を辿る。(他に選択肢がない場合には、不連結になっても良い。)
iii．辿った辺をグラフから除去し、この辺の除去により、辺が１つも連結していない頂点が生じる場合、その頂点もグラフから除去する。(手順２.Ａ.ａ.ｉにおいてグラフが不連結になっても、この手順により不連結状態は解消されることになる。)
iv．グラフが空になるまで、上記２.Ａ.ａ.ｉから２.Ａ.ａ.iiiの手順を繰り返す。
【００５７】
ｂ．グラフＧ’の各頂点について、上記の手順で発見したオイラー回路を辿ったときに、当該頂点に到達する辺のみを取り出し、部分グラフＧ１を生成する。
また、当該頂点から出発する辺のみを取り出し、別途、部分グラフＧ２を生成する。オイラー回路の性質から、部分グラフＧ１及びＧ２は、いずれも正則２部グラフであり、その次数はＧの半分である。
ｃ．部分グラフＧ１及びＧ２について、再帰的に上記２の方法により辺彩色を行う。
【００５８】
Ｂ．グラフＧ'の次数が奇数であるとき（図５の例に該当（ｋ＝３））
ａ．グラフＧ’の完全マッチングＭを求める。このマッチングとは、グラフの辺の部分集合のうち、属する辺の両端の頂点が全て異なるものを指し、かつ完全マッチングとは、グラフの全ての頂点を辺の両端として含むマッチングを指すこととする。
以下に、この完全マッチングを求める方法を示す。
ｉ．辺ｅに対応する重み係数ω（ｅ）を定義し、この重み係数の初期状態として、グラフの全ての辺について、ω（ｅ）＝１とする。
また、グラフの辺のある部分集合Ｆについて、その部分集合Ｆに対応する重み係数ω（Ｆ）を、ω（Ｆ）＝Σｅ∈Ｆω（ｅ）によって定義する。
さらに、グラフの辺の部分集合Ｆについて、ＵＦを以下の（１０）に示すように定義する。
【００５９】
【数１０】
【００６０】
ii．重みが０ではない辺のみから構成される閉路を、グラフから任意に検出し、この閉路を２つのマッチングＭとＮとに分割する。ただし、ω（Ｍ）≧ω(Ｎ)とする。
対象とするグラフは２部グラフであることから、検出される上記閉路は全て偶数本の辺から構成される。
したがって、当該の２つのマッチングは、閉路を辿りながら交互に辺を選択していくことで得られる。
iii．グラフの全ての辺について、以下の（１１）式により重みを更新する。
【００６１】
【数１１】
【００６２】
iv．グラフの全ての辺の重みが、グラフの次数もしくは０になるまで、２.Ｂ.ａ.ｉ〜２.Ｂ.ａ.iiiの手順を繰り返す。
ｂ．上記の手順で得られた完全マッチングＭの各辺に同一の色を与え、グラフＧ’から取り除く。マッチングを取り除いたグラフについて、再帰的に上記２の方法で辺彩色を行う。
すなわち、図５に示すように、辺Ａ１〜Ａ４，Ｂ１〜Ｂ４，Ｃ１〜Ｃ４各々の両端の頂点が全て異なるものを指し（例えば、row（０００１）は同様の頂点column（０００１）と共有する辺を有さず、頂点column（００１０）、（０１００）、（１０００）と辺を共有している）、かつ完全マッチングとは、グラフの全ての頂点を辺の両端として含むマッチングを指している。
【００６３】
上述のようにして、経験分布別圧縮系列表の各枠（各系列対）に割り当てられた識別番号を、ｃ２＝ｃ２（Ｑ）桁の｜Ｚ｜進表現することにより、各枠に対応する系列対(ｘ〜ｍ，ｙ〜ｍ)に割り当てられる圧縮系列ｚ〜ｃ２が得られる。ここで、Ｚは圧縮系列を構成する文字の集合であり、ｃ２（Ｑ）は以下の（１２）式により経験分布別圧縮系列表作成部１１２が求め、｜Ｚ｜は上記文字の集合Ｚの文字数である。
上述したステップＳ１からステップＳ８の処理により、圧縮系列表作成部１１は、経験分布共有系列対集合毎に生成した上記経験分布別圧縮系列表の集合を圧縮系列表として出力し、内部の記憶部に記憶する。
【００６４】
【数１２】
【００６５】
次に、系列分割部１２は、受信側端末に対する伝送対象の第１系列及び第２系列を入力し、それら系列各々を、前記圧縮系列表作成部１１で定められた系列長の系列に分割することにより、それぞれ第１分割系列及び第２分割系列を抽出し、それら分割系列の対である分割系列対について、その集合を出力する。
本実施形態において、系列分割部１２は、第１系列ｘｎ及び第２系列ｙｎを、系列対分類部１１１により定めた系列長ｍを用いて、以下の（１３）式、（１４）式及び（１５）式を用いて分割する。
【００６６】
【数１３】
【００６７】
【数１４】
【００６８】
【数１５】
【００６９】
ここで、ｘｊｉ は系列ｘｎの第ｉ成分から第ｊ成分までを切り出した部分系列、すなわちｘｊｉ＝ｘｉｘｉ＋１…ｘｊである。また、floor（ｔ）は実数ｔ以下の最大の整数を求める関数である。上記の分割方法は、すなわち、系列の先頭から順に系列長ｍの部分系列を切り出し、系列長ｍの部分系列が切り出せなくなったところで系列の分割処理を終了し、残りの部分系列（系列長がｍ未満）をそのまま出力する方法である。
上述したように、系列分割部１２は、以下に示す（１６）式及び（１７）式に示すように、分割系列対を抽出し、これら分割系列対の集合を出力する。
【００７０】
【数１６】
【００７１】
【数１７】
【００７２】
系列経験分布導出部１３は、系列分割部１２から上記分割系列対の集合を入力し、それら分割系列対の各々から同時経験分布を導出し、その同時経験分布の集合を出力する。
ここで、系列経験分布導出部１３は、各分割系列対(ｘ〜ｍ（ｊ），ｙ〜ｍ（ｊ）)についての同時経験分布Ｑｍｘ〜ｍ（ｊ），ｙ〜ｍ（ｊ）を、上記系列対分類部１１１で説明した方法と同様にして求める。
また、系列経験分布導出部１３は、ｌ＋１番目、すなわち系列長ｍに満たない余りの分割系列対(ｘ〜ｍ（ｌ＋１），ｙ〜ｍ（ｌ＋１）)については、同時経験分布を抽出しない。
【００７３】
圧縮部分系列決定部１４は、上記経験分布別圧縮系列表の集合、上記分割系列対の集合及び同時経験分布Ｑｍｘ〜ｍ（ｊ），ｙ〜ｍ（ｊ）の集合を記憶部から入力し、それら分割系列対の各々について、対応する同時経験分布Ｑｍｘ〜ｍ（ｊ），ｙ〜ｍ（ｊ）及び経験分布別圧縮系列表を用いて、その分割系列対に対応する圧縮系列である圧縮部分系列を定め、その圧縮部分系列の集合を出力する。
ここで、圧縮部分系列の決定方法は特に限定されるものではないが、本実施例において、圧縮部分系列決定部１４は、例えば圧縮部分系列先頭部決定部１４１ と、圧縮部分系列後続部決定部１４２とによって構成されている。以下、この圧縮部分系列決定部１４による圧縮部分系列の生成方法について述べる。
【００７４】
圧縮部分系列先頭部決定部１４１は、上記分割系列対の集合及び同時経験分布Ｑｍｘ〜ｍ（ｊ），〜ｙｍ（ｊ）の集合を入力し、それら分割系列対の各々について、その分割信号系列の同時経験分布Ｑｍｘ〜ｍ（ｊ），ｙ〜ｍ（ｊ）に対応する識別番号もしくはその識別番号に対応する系列を、圧縮部分系列の先頭部分とし、その圧縮部分系列の先頭部分の集合を出力する。
本実施形態において、圧縮部分系列先頭部決定部１４１は、圧縮部分系列の先頭部分を、以下のようにして決定する。
ここで、同時経験分布全体の集合Ｐm（Ｖ×Ｗ）の各要素に対して異なる識別番号があらかじめ与えられているとする。このとき、集合Ｐm（Ｖ×Ｗ）の要素数が以下の（１８）式により、（ｍ＋１）｜Ｖ×Ｗ｜より等しいか小さいため、この識別番号を高々（ｍ＋１）｜Ｖ×Ｗ｜種類の識別番号を用意すれば良い。
【００７５】
【数１８】
【００７６】
そこで、圧縮部分系列先頭部決定部１４１は、分割系列対（ｘ〜ｍ（ｊ），ｙ〜ｍ（ｊ））（ｊ＝１，２，…，ｌ）に対して、その同時経験分布Ｑｍｘ〜ｍ（ｊ），ｙ〜ｍ（ｊ）に対応する識別番号を割り当てる。
そして、圧縮部分系列先頭部決定部１４１は、各分割系列対に割り当てられた識別番号を、ｃ1＝｜Ｖ×Ｗ｜log｜Ｚ｜（ｍ＋１）桁の｜Ｚ｜進表現（以下の（１９）式）に変換し、この｜Ｚ｜進表現を、分割系列対（ｘ〜ｍ（ｊ），ｙ〜ｍ（ｊ））に対応する圧縮部分系列の先頭部分として決定する。
【００７７】
【数１９】
【００７８】
圧縮部分系列後続部決定部１４２は、上記経験分布別圧縮系列表の集合、分割系列対の集合、及び同時経験分布Ｑｍｘ〜ｍ（ｊ），ｙ〜ｍ（ｊ）の集合を入力する。このとき、圧縮部分系列後続部決定部１４２は、経験分布別圧縮系列表の集合を上記記憶部から読み出す。
そして、圧縮部分系列後続部決定部１４２は、入力された分割系列対の各々について、その分割系列対の同時経験分布Ｑｍｘ〜ｍ（ｊ），ｙ〜ｍ（ｊ）に対応する経験分布別圧縮系列表から、その分割系列対（ｘ〜ｍ（ｊ），ｙ〜ｍ（ｊ））に対応する圧縮系列を導出し、これを圧縮部分系列の後続部として決定し、その圧縮部分系列の後続部の集合を出力する。
【００７９】
本実施形態において、圧縮部分系列後続部決定部１４２は、圧縮部分系列の後続部を、以下のように決定する。
この決定の際、圧縮部分系列後続部決定部１４２は、分割系列対（ｘ〜ｍ（ｊ），ｙ〜ｍ（ｊ））（ｊ＝１，２，…，ｌ）に対して、その同時経験分布Ｑｍｘ〜ｍ（ｊ），ｙ〜ｍ（ｊ）に対応する経験分布別圧縮系列表を選択する。
次に、圧縮部分系列後続部決定部１４２は、選択された上記経験分布別圧縮系列表の中から、分割系列対（ｘ〜ｍ（ｊ），ｙ〜ｍ（ｊ））に対応する枠（図４（ｃ））を検出し、その枠に割り当てられた（２０）式に示す圧縮系列を導出（抽出）する。
【００８０】
【数２０】
【００８１】
ここで、ｃ2（ｊ）は、ｊ番目の分割系列対に対応する圧縮系列の長さである。上記経験分布別圧縮系列表作成部１１２は、ｃ2（ｊ）を、ｊ番目の分割系列対の同時経験分布Ｑj＝Ｑｍｘ〜ｍ（ｊ），ｙ〜ｍ（ｊ）によって決定、すなわち、以下の（２１）式にて求める。
【００８２】
【数２１】
【００８３】
そして、経験分布別圧縮系列表作成部１１２は、この圧縮系列Ｚ〜ｃ２（ｊ）（ｊ；２）を、分割系列対（ｘ〜ｍ（ｊ），ｙ〜ｍ（ｊ））に対応する圧縮部分系列の後続部とする。
上述したように、圧縮部分系列決定部１４は、抽出された圧縮部分系列の先頭部ｚ〜ｃ１（ｊ；１）と後続部ｚ〜ｃ２（ｊ；２）とを連結した（２２）式に示す系列ｚ〜ｃ（ｊ）を圧縮部分系列とし、これら系列対を分割した分割系列各々に対応する圧縮部分系列の集合を出力する。
ここで、＊は系列の連接を表す演算子であり、ｃ（ｊ）＝ｃ1＋ｃ2(j)はｊ番目の分割系列対に対応する圧縮部分系列の長さである。
【００８４】
【数２２】
【００８５】
圧縮系列生成部１５は、上記圧縮部分系列決定部１４から出力される圧縮部分系列の集合を入力し、その集合における圧縮部分系列を統合することにより、第１系列及び第２系列に対応する圧縮系列を生成し、この生成した圧縮系列を出力する。
本実施形態において、第１系列ｘｎ及び第２系列ｙｎに対応する圧縮系列ｚｃ＊（ｘｎ，ｙｎ）は、以下の（２３）及び（２４）式に示すように決定される。
【００８６】
【数２３】
【００８７】
【数２４】
【００８８】
上記（２３）及び（２４）式において、ｃ＊は第１系列ｘｎ及び第２系列ｙｎに対応する圧縮系列の長さを示している。
この圧縮系列の構成は、最終的に、圧縮系列生成部１５において、各圧縮部分系列を連結した後に、最後に上記系列分割部１２で系列長ｍ未満の系列長を有する余った部分系列を圧縮せずにそのまま連結したものである。
上述したように、系列圧縮部１は、入力される第１系列ｘｎ及び第２系列ｙｎから、上記圧縮系列ｚｃ＊（ｘｎ，ｙｎ）を生成して出力する。
【００８９】
次に、系列圧縮部１が圧縮した圧縮系列を復元する復元部２及び復元部３の説明を行う。この説明において、復元部２及び復元部３における復元処理は、復元の際に用いる系列（第１系列あるいは第２系列）が異なるのみで、同様な復元処理が行われるため、代表として、第２系列ｙｎを有する復元部２を用いて説明する。
復元部２は、系列圧縮部１から出力された圧縮系列ｚｃ＊（ｘｎ，ｙｎ）と、予め端末２０１の記憶部に記憶されている第２系列とを入力し、これら圧縮系列ｚｃ＊（ｘｎ，ｙｎ）と第２系列ｙｎとから第１系列ｘｎを復元し、復元された第１系列である復元第１系列を出力する。
【００９０】
上記復元部２は、系列の復元方法、すなわち復元処理を行う構成として特に限定されるものではないが、本実施形態において、例えば図６に示すように、圧縮系列分割部２１と、圧縮系列表同定部２２と、分割系列復元部２３と、復元系列生成部２４とから構成されている。
圧縮系列分割部２１は、上記圧縮系列ｚｃ＊（ｘｎ，ｙｎ）を入力し、圧縮系列を分割することで圧縮部分系列を復元し、復元した圧縮部分系列である復元圧縮部分系列についてその集合を出力する。
【００９１】
すなわち、本実施形態において、圧縮系列分割部２１は、圧縮部分系列を、以下の処理にして復元する。
説明上において、圧縮系列分割部２１が、入力された圧縮系列ｚｃ＊（ｘｎ，ｙｎ）から、すでに以下の（２５）式に示すように、ｊ−１番目までの復元圧縮部分系列を復元しているものとする。この（２５）式において、ｃ＾（ｊ）は、ｊ番目の復元圧縮部分系列の系列長である。
【００９２】
【数２５】
【００９３】
ここで、圧縮系列分割部２１は、圧縮系列ｚｃ＊（ｘｎ，ｙｎ）におけるσｊ番目の文字を先頭としてｃ１個の文字を切り出し、このｃ１個の文字をｊ番目の復元圧縮部分系列の先頭部ｚ＾ｃ１（ｊ；１）する。ここで、σｊは以下の（２６）式により求められる。また、ｃ1はすでに圧縮処理にて述べたように、第１系列及び第２系列のデータに依存せずに、定数（＝｜Ｖ×Ｗ｜log｜Ｚ｜（ｍ＋１））である。
【００９４】
【数２６】
【００９５】
上記圧縮系列分割部２１は、すでに述べた圧縮部分系列先頭部決定部１４１と同様の処理により、上述した処理において、圧縮系列ｚｃ＊（ｘｎ，ｙｎ）から切り出した復元圧縮部分系列の先頭部ｚ＾ｃ１（ｊ）から、ｊ番目の分割系列対の同時経験分布Ｑ＾ｊを復元できる。 さらに、圧縮系列分割部２１は、上記圧縮部分系列後続部決定部１４２と同様の処理により、復元された同時経験分布である復元同時経験分布Ｑ＾ｊから、ｊ番目の圧縮部分系列の後続部の系列長ｃ２＾(j)を算出（同定）することができる。
【００９６】
上述したように、圧縮系列分割部２１は、圧縮系列ｚｃ＊（ｘｎ，ｙｎ）のσｊ＋ｃ1番目の文字を先頭とするｃ2＾（ｊ）個の文字を切り出すことで、ｊ番目の復元圧縮部分系列の後続部ｚ＾ｃ２＾（ｊ）（ｊ；２）を生成する。
そして、圧縮系列分割部２１は、先頭部ｚ＾ｃ１（ｊ）と後続部ｚ＾ｃ２＾（ｊ）（ｊ；２）とを連結することにより、ｊ番目の復元圧縮部分系列ｚ＾ｃ＾（ｊ）（ｊ）を生成する。ここで、c＾(j)＝ｃ1＋ｃ２＾（ｊ）である。
上記の操作を、圧縮系列分割部２１がｊ＝１，…，ｌのｌ回繰り返して実行することにより、ｌ番目までの復元圧縮部分系列ｚ＾ｃ＾（ｊ）（ｊ）（ｊ＝１，…，ｌ）が復元される。
そして、圧縮系列分割部２１は、圧縮系列から切り出されなかった残りのｃ＊−σｌ個の文字を、ｌ＋１番目の復元圧縮部分系列ｚ＾ｃ＾（ｌ＋１）（ｌ＋１）として出力する。ここで、ｃ＾（ｌ＋１）＝ｃ＊−σｌである。
【００９７】
上記圧縮系列表同定部２２は、圧縮系列分割部２１が出力する上記復元圧縮部分系列の集合を入力し、その復元圧縮部分系列の各々について、その圧縮部分系列を生成した圧縮系列表を、予め記憶部に記憶されている圧縮系列表集合から同定（抽出）し、その同定された圧縮系列表である復元圧縮系列表の集合を出力する。
ここで、圧縮系列表同定部２２は、上記圧縮系列表として、すでに系列圧縮部１の経験分布別圧縮系列表作成部１１２にて生成されたものと同一の経験分布別圧縮系列表の圧縮系列表集合を予め内部の記憶部に記憶している。たとえば、送信側端末１００がこの圧縮系列表を作成し、この圧縮系列表が所定の周期にて送信側端末１００から受信側端末２０１，２０２，…に対して周期的に送信され、系列圧縮部１と各系列復元部との間にて同期が取られている。
この圧縮系列表同定部２２は、本実施形態において、復元圧縮系列表を、以下のようにして同定する。
圧縮系列表同定部２２は、ｊ番目の復元圧縮部分系列ｚ＾ｃ＾（ｊ）（ｊ）の先頭ｃ1個の文字、すなわち先頭部ｚ＾ｃ１（ｊ）を切り出す。
【００９８】
そして、圧縮系列表同定部２２は、この先頭部ｚ＾ｃ１（ｊ）からｊ番目の分割系列対の復元同時経験分布必を同定するとともに、この同時経験分布に対応する経験分布別圧縮系列表も同定する。この同定される経験分布別圧縮系列表を、ｊ番目の分割系列対の復元に用いる復元圧縮系列表とする。
圧縮系列表同定部２２は、上述した操作を、ｊ＝１，…，ｌについて繰り返すことにより、ｊ個の表からなる集合を得る。ただし、圧縮系列表同定部２２は、ｌ＋１番目の分割系列対については、圧縮が行われていないため上述した処理を行わない。
【００９９】
上記分割系列復元部２３は、上記復元部分系列の集合、復元圧縮系列表の集合、及び第２系列を入力し、復元圧縮部分系列の各々、及び各復元圧縮系列に対応して第２系列から得られる第２分割系列の集合を用い、その復元圧縮部分系列に対応して得られた復元圧縮系列表から第１分割系列を復元して、この復元された分割系列である復元第１分割系列の集合を出力する。
分割系列復元部２３は、本実施形態において、復元第１分割系列を、以下のようにして求めている。
【０１００】
このとき、分割系列復元部２３は、系列分割部１２と同様の処理により、第２系列ｙｍを第２分割系列の集合ｙ〜ｍ（ｊ）（ｊ＝１，２，…，ｌ）に分割する。
分割する。
次に、分割系列復元部２３は、ｊ番目の復元圧縮部分系列ｚ＾ｃ＾（ｊ）（ｊ）の後続ｃ2 ＾（ｊ）個の文字を抽出してｚ＾ｃ２＾（ｊ）（ｊ）として切り出す。
そして、分割系列復元部２３は、ｊ番目の復元圧縮系列表を参照して、ｊ番目の復元圧縮系列表における第２分割系列ｙ〜ｍ（ｊａ）に対応する列を検出する。
【０１０１】
次に、分割系列復元部２３は、その検出した列から、復元圧縮部分系列の後続部ｚ＾ｃ２＾（ｊ）（ｊ）が存在する枠を検出する。
そして、分割系列復元部２３は、検出された上記枠の存在する行を検出し、この枠に対応する行の第１分割系列を、ｊ番目の復元第１分割系列ｘ＾ｍ（ｊ）とする。
分割系列復元部２３は、上述した処理をｊ＝１，…，ｌについて、すなわちｌ回繰り返し実行することにより、ｌ番目までの復元第１分割系列ｘ＾ｍ（ｊ）（ｊ＝１，…，ｌ）が復元される。
また、分割系列復元部２３は、ｌ＋１番目の復元圧縮部分系列ｚ＾ｃ＾（ｌ＋１）（ｌ＋１）に対し、その前半部分ｚ１＾（ｌ＋１）／２（ｌ＋１）を切り出し、それをｌ＋１番目の復元第１分割系列ｘ＾ｌ＋１とする（後半部分はｚ１＾（ｌ＋２）／２（ｌ＋１）は第２分割系列ｙ＾ｌ＋１に対応）。
【０１０２】
本第１の実施形態においては、どのような第１系列及び第２系列が入力として与えられても、必ず同一の系列を復元することができる。すなわち、第１系列と第１復元系列とは、また第２系列と第２復元系列とは同一である。このとき、ｃ＾（ｌ＋１）＝ｃ＊−σｌが２mod（ｎ，ｍ）と一致する。
後述する第２の実施形態においては、詳細は後述するが、必ずしも同一の系列を復元できるとは限らないが、ｃ＊−σｌと２mod（ｎ，ｍ）とが一致するように構成される。詳細は第２の実施例にて記述する。
【０１０３】
復元第１系列生成部２４は、上記復元第１分割系列の集合を入力し、それら復元第１分割系列を統合することにより、第１系列を復元し、復元した系列である復元第１系列を出力する。
そして、復元第１系列生成部２４は、（２７）式に示すように上記復元第１分割系列を連結することにより、復元第１系列ｘ＾ｎを復元する。このようにして、第１系列復元部２は、送信側端末１００から、自身に対して送信された送信信号として上記復元第１系列ｘ＾ｎを出力する。
【０１０４】
【数２７】
【０１０５】
次に、第２系列復元部３は、第１の系列復元部２と同様な構成及び処理により、圧縮系列の復元を行うため詳細な説明を省略するが、予め記憶部に第１系列が記憶された受信側端末２０２に設けられているため、この第１系列と入力される圧縮系列ｚｃ＊（ｘｎ，ｙｎ）とから、第１系列復元部２と同様な構成及び処理により、以下の（２８）式に示す第２系列を求める。
【０１０６】
【数２８】
【０１０７】
このとき、第２系列復元部３における分割系列復元部２３は、ｌ＋１番目の復元圧縮部分系列ｚ＾ｃ＾（ｌ＋１）（ｌ＋１）に対し、以下の（２９）式に示す前半部分を切り出し、それをｌ＋１番目の復元第１分割系列ｙ＾ｌ＋１とする。
【０１０８】
【数２９】
【０１０９】
＜第２の実施形態＞
本実施形態における信号系列の伝送を行う伝送システムとしては、第１の実施形態と同様に図１の概念図に示すように、信号系列を圧縮する信号系列圧縮部１が信号系列を送信する送信側装置に設けられ、圧縮された信号系列（圧縮信号系列）を復元する系列復元部２（あるいは３）が受信側端末に設けられている。以下、第１の実施形態と同様の処理を行う処理部については説明を省略し、第１の実施形態と異なる部分のみを説明する。
【０１１０】
系列対分類選択部１１３は、すでに述べた系列対分類部１１１から出力される分類の集合を入力する。
そして、系列対分類選択部１１３は、入力された分類の集合の中から、分類に所属する系列に対応する圧縮系列の長さが、あらかじめ定められた閾値である圧縮系列長閾値を下回る（未満の）分類のみを選択し、この選択された分類の集合を出力する。
また、第１の実施形態における圧縮部分系列決定部１４に示した処理と同様に、ある同時経験分布Ｑについて、その同時経験分布Ｑに対応する分類（すなわち、その同時経験分布を有する系列対の集合）ＴｍＱに含まれる分割系列対から得られる圧縮部分系列の長さが、ｃ1＋ｃ2（Ｑ）であることがわかる。
【０１１１】
ここで、圧縮系列長閾値ｒを導入し、経験分布別圧縮系列表作成部１１２は、以下に示す（３０）式を満たす同時経験分布Ｑ、及びその同時経験分布Ｑに対応するＴｍＱを選択し、選択された分類の集合を出力する。
【０１１２】
【数３０】
【０１１３】
経験分布別圧縮系列表作成部１１２は、上記系列対分類選択部１１３から出力された分類の集合を入力し、入力した各分類に含まれる系列対各々に対応する圧縮系列を定め、系列対と圧縮系列との対応関係を示す圧縮系列表である経験分布別圧縮系列表を作成し、この経験分弁別圧縮系列表の集合を出力する。
ここで、経験分布別圧縮系列表作成部１１２の処理において、上記系列対分類選択部１１３にて選択された分類については、すでに述べた第１の実施形態における処理と同様である。しかしながら、本第２の実施形態においては、系列対分類選択部１１３により選択されなかった分類については、経験分布別圧縮系列表を作成しない。このような処理により、上記系列対分類選択部１１２で選択されなかった分類については、特定の圧縮系列が割り当てられないこととなる。
【０１１４】
圧縮部分系列後続部決定部１４２は、すでに第１の実施形態にて述べた圧縮系列表作成部１１から出力された経験分布別圧縮系列表の集合、系列分割部１２から出力された分割系列対の集合、及び系列経験分布導出部１３から出力された同時経験分布の集合を入力する。
そして、圧縮部分系列後続部決定部１４２は、入力された分割系列対の各々について、その分割系列対の同時経験分布に対応する経験分布別圧縮系列表から、その分割系列対に対応する圧縮系列を導出（抽出）し、これを圧縮部分系列の後続部として決定し、その圧縮部分系列の後続部の集合を出力する。
【０１１５】
このとき、圧縮部分系列後続部決定部１４２は、上記経験分布別圧縮系列表作成部１１３で経験分布別圧縮系列表が作成されている同時分布を有する分割系列対に対し、第１の実施形態と同様の処理を行う。
一方、圧縮部分系列後続部決定部１４２は、経験分布別圧縮系列表が作成されていない同時分布を有する分割系列対に対し、系列長ｃ2（ｊ）のランダムな系列を割り当て、これを圧縮部分系列の後続部とする。
【０１１６】
またさらに別の実施形態として、圧縮部分系列後続部決定部１４２は、圧縮系列長を全て一定にすることも可能である。
このとき、元々の圧縮系列長が圧縮系列長閾値に満たないとき、圧縮系列に適切な数の文字を埋めることにより、系列長をｒとして揃えることができる。経験分布別圧縮系列表が作成されていない同時分布を有する分割系列対に対しては、系列長ｒのランダムな系列を割り当てる。
この第２及び別の実施形態においては、前記系列対分類選択部１１２で選択されなかった分類に含まれる分割系列対については、上記第１系列復元部２及び第２系列復元部３において、必ずしも第１系列及び第２系列を復元できるとは限らないことに注意する。
【０１１７】
なお、図１における信号系列圧縮部１，系列復元部２，系列復元部３それぞれの機能を実現するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、それぞれのシステムにおいて圧縮または復元を行うプロセスとして実行することにより各機能の処理を行ってもよい。なお、ここでいう「コンピュータシステム」とは、ＯＳや周辺機器等のハードウェアを含むものとする。また、「コンピュータシステム」は、ホームページ提供環境（あるいは表示環境）を備えたＷＷＷシステムも含むものとする。また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムが送信された場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリ（ＲＡＭ）のように、一定時間プログラムを保持しているものも含むものとする。
【０１１８】
また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されてもよい。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。また、上記プログラムは、前述した機能の一部を実現するためのものであっても良い。さらに、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるもの、いわゆる差分ファイル（差分プログラム）であっても良い。
【図面の簡単な説明】
【０１１９】
【図１】本発明の第１及び第２の実施形態による信号圧縮装置及び信号復元装置を用いた信号伝送システムの概念図である。
【図２】本発明の第１及び第２の実施形態による信号圧縮装置の構成例を示すブロック図である。
【図３】図２における圧縮系列表作成部１１の圧縮系列表作成処理の動作を説明する圧縮系列表の概念図である。
【図４】図２における圧縮系列表作成部１１の圧縮系列表生成における動作を示すフローチャートである。
【図５】経験分布別圧縮系列表作成部１１３による各経験分布別圧縮系列表への識別番号の割り当て処理を説明するための２部グラフの概念図である。
【図６】本発明の第１及び第２の実施形態による信号復元装置の構成例を示すブロック図である。
【符号の説明】
【０１２０】
１…信号系列圧縮部
２，３…系列復元部
１１…圧縮系列表作成部
１２…系列分割部
１３…系列経験分布導出部
１４…圧縮部分系列決定部
１５…圧縮系列生成部
２１…圧縮系列分割部
２２…圧縮系列表同定部
２３…分割系列復元部
２４…復元系列生成部
１００…送信側端末
１１１…系列対分類部
１１２…経験分布別圧縮系列表作成部
１１３…系列対分類選択部
１４１…圧縮部分系列先頭部決定部
１４２…圧縮部分系列後続部決定部
２０１，２０２…受信側端末
【特許請求の範囲】
【請求項１】
伝送の対象となる２つの信号系列である第１信号系列及び第２信号系列について、これら信号系列を、２つの信号系列のうちいずれかの信号系列を所有する複数の受信者へ伝送する信号伝送に用いる、上記信号系列を圧縮する信号圧縮方法であり、
圧縮信号系列表作成部が、設定された一定の長さの系列長を有する任意の２つの信号系列からなる信号系列対に対し、該信号系列対の経験確率分布を用いて、信号系列対に対応する圧縮信号系列を設定し、信号系列対と圧縮信号系列との対応関係を示す圧縮信号系列表を生成し、該圧縮信号系列表を記憶部に記憶する圧縮信号系列表作成過程と、
信号系列分割部が、入力される第１信号系列及び第２信号系列各々を、前記系列長の信号系列に分割し、第１分割信号系列及び第２分割信号系列の対である分割信号系列対の集合を抽出する信号系列分割過程と、
分割信号系列対経験分布導出部が、前記分割信号系列対の各々の経験確率分布を求める分割信号系列対経験分布導出過程と、
圧縮信号部分系列決定部が、前記分割信号系列対の各々に対応する前記経験確率分布及び前記圧縮信号系列表を参照し、該分割信号系列対に対応する圧縮信号系列である圧縮信号部分系列を定める圧縮信号部分系列決定過程と、
圧縮信号系列生成部が、前記圧縮信号部分系列の集合から、それら圧縮信号部分系列を統合することにより、第１信号系列及び第２信号系列に対応する圧縮信号系列を生成する圧縮信号系列生成過程と
から構成されることを特徴とする信号圧縮方法。
【請求項２】
前記圧縮信号系列表作成過程は、
信号系列対分類部が前記系列長を有する任意の信号系列の信号系列対に対し、該信号系列対の経験確率分布にて分類する信号系列対分類過程と、
経験分布別圧縮信号系列表作成が前記信号系列対分類過程で得られた分類各々に対し、それぞれの分類に含まれる信号系列対各々に対応する圧縮信号系列を定め、信号系列対と圧縮信号系列との対応関係を示す圧縮信号系列表である経験分布別圧縮信号系列表を作成して記憶部に記憶する経験分布別圧縮信号系列表作成過程と
から構成されることを特徴とする請求項１に記載の信号圧縮方法。
【請求項３】
前記圧縮信号部分系列決定過程は、
圧縮信号部分系列先頭決定部が、前記分割信号系列対の各々に対し、それぞれの分割信号系列対の経験確率分布に対応する番号もしくはその番号に対応する系列を、圧縮信号部分系列の先頭部分として設定する圧縮信号部分系列先頭部決定過程と、
圧縮信号部分系列後続部決定部が、前記分割信号系列対の各々について、それぞれの分割信号系列対の経験確率分布に対応する経験分布別圧縮信号系列表を参照し、分割信号系列対に対応する圧縮信号系列を導出し、該圧縮信号系列を圧縮信号部分系列の後続部分として設定する圧縮信号部分系列後続部決定過程と
から構成されることを特徴とする請求項１または請求項２に記載の信号圧縮方法。
【請求項４】
信号系列対分類選択部が前記信号系列対分類過程にて得られた分類の集合から、該分類に所属する信号系列対に対応する圧縮信号系列の長さが、あらかじめ設定された閾値である圧縮系列長閾値を下回る分類のみを選択する信号系列対分類選択過程をさらに有し、
前記経験分布別圧縮信号系列表作成過程が、前記信号系列対分類選択過程にて選択された前記分類に対して圧縮信号系列表を作成し、
前記圧縮信号部分系列後続部決定過程において、圧縮信号部分系列後続部が、圧縮信号系列表が作成されていない分類に対し、任意の系列を圧縮信号部分系列の後続部分として決定する
ことを特徴とする請求項３に記載の信号圧縮方法。
【請求項５】
複数の受信者へ信号系列を伝送する際、予め受信者が有する信号系列と、伝送の対象となる他の信号系列との２つの信号系列からなる圧縮された圧縮信号系列を復元する信号復元方法であり、
圧縮信号系列分割部が、前記圧縮信号系列を分割し、復元圧縮信号部分系列を生成する圧縮信号系列分割過程と、
圧縮信号系列表同定部が、前記圧縮信号系列分割過程にて得られた復元圧縮信号部分系列の各々に対し、それぞれの圧縮信号部分系列に対応する圧縮信号系列表を、圧縮信号部分系列に対応して圧縮信号系列表が記憶されている記憶部から同定する圧縮信号系列表同定過程と、
分割信号系列復元部が、前記復元圧縮信号部分系列各々と、前記予め受信者が有する信号系列を予め設定された系列長にて分割して生成した第２分割信号系列とにより、その復元圧縮信号部分系列に対応して前記圧縮信号系列表同定過程にて得られた圧縮信号系列表である復元圧縮信号系列表から、前記第２分割信号系列の対である分割信号系列を読み出し、復元第１分割信号系列とする分割信号系列復元過程と、
復元信号系列生成部が、前記分割信号系列復元にてえられた前記復元第１分割信号系列の集合から、それら復元第１分割信号系列を統合することにより、予め受信者が有する信号系列と対をなす伝送の対象となる他の信号系列を復元する復元信号系列生成過程と
から構成されることを特徴とする信号復元方法。
【請求項６】
前記圧縮信号系列表同定過程において、前記圧縮信号系列表同定部が前記圧縮信号系列分割過程にて得られた復元圧縮信号部分系列各々について、それぞれの圧縮信号部分系列の先頭部分から、その圧縮信号部分系列を生成した経験分布別圧縮信号系列表を同定し
前記先頭部分がそれぞれの分割信号系列対の経験確率分布に対応する番号もしくはその番号に対応する系列であることを特徴とする請求項５に記載の信号復元方法。
【請求項７】
伝送の対象となる２つの信号系列である第１信号系列及び第２信号系列について、これら信号系列を、２つの信号系列のうちいずれかの信号系列を所有する複数の受信者へ伝送する信号伝送に用いる、上記信号系列を圧縮する信号圧縮装置であり、
設定された一定の長さの系列長を有する任意の２つの信号系列からなる信号系列対に対し、該信号系列対の経験確率分布を用いて、信号系列対に対応する圧縮信号系列を設定し、信号系列対と圧縮信号系列との対応関係を示す圧縮信号系列表を生成し、該圧縮信号系列表を記憶部に記憶する圧縮信号系列表作成部と、
入力される第１信号系列及び第２信号系列各々を、前記系列長の信号系列に分割し、第１分割信号系列及び第２分割信号系列の対である分割信号系列対の集合を抽出する信号系列分割部と、
前記分割信号系列対の各々の経験確率分布を求める分割信号系列対経験分布導出部と、
前記分割信号系列対の各々に対応する前記経験確率分布及び前記圧縮信号系列表を参照し、該分割信号系列対に対応する圧縮信号系列である圧縮信号部分系列を定める圧縮信号部分系列決定部と、
前記圧縮信号部分系列の集合から、それら圧縮信号部分系列を統合することにより、第１信号系列及び第２信号系列に対応する圧縮信号系列を生成する圧縮信号系列生成部と
から構成されることを特徴とする信号圧縮装置。
【請求項８】
複数の受信者へ信号系列を伝送する際、予め受信者が有する信号系列と、伝送の対象となる他の信号系列との２つの信号系列からなる圧縮された圧縮信号系列を復元する信号復元装置であり、
前記圧縮信号系列を分割し、復元圧縮信号部分系列を生成する圧縮信号系列分割部と、
前記圧縮信号系列分割部にて得られた復元圧縮信号部分系列の各々に対し、それぞれの圧縮信号部分系列に対応する圧縮信号系列表を、圧縮信号部分系列に対応して圧縮信号系列表が記憶されている記憶部から同定する圧縮信号系列表同定部と、
前記復元圧縮信号部分系列各々と、前記予め受信者が有する信号系列を予め設定された系列長にて分割して生成した第２分割信号系列とにより、その復元圧縮信号部分系列に対応して前記圧縮信号系列表同定部にて得られた圧縮信号系列表である復元圧縮信号系列表から、前記第２分割信号系列の対である分割信号系列を読み出し、復元第１分割信号系列とする分割信号系列復元部と、
前記分割信号系列復元にてえられた前記復元第１分割信号系列の集合から、それら復元第１分割信号系列を統合することにより、予め受信者が有する信号系列と対をなす伝送の対象となる他の信号系列を復元する復元信号系列生成部と
から構成されることを特徴とする信号復元装置。
【請求項９】
コンピュータに請求項１〜請求項４のいずれかに記載の信号圧縮方法を実行させるためのコンピュータが実行可能なプログラム。
【請求項１０】
コンピュータに請求項５または請求項６に記載の信号復元方法を実行させるためのコンピュータが実行可能なプログラム。
【請求項１１】
請求項９または請求項１０に記載のプログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項１】
伝送の対象となる２つの信号系列である第１信号系列及び第２信号系列について、これら信号系列を、２つの信号系列のうちいずれかの信号系列を所有する複数の受信者へ伝送する信号伝送に用いる、上記信号系列を圧縮する信号圧縮方法であり、
圧縮信号系列表作成部が、設定された一定の長さの系列長を有する任意の２つの信号系列からなる信号系列対に対し、該信号系列対の経験確率分布を用いて、信号系列対に対応する圧縮信号系列を設定し、信号系列対と圧縮信号系列との対応関係を示す圧縮信号系列表を生成し、該圧縮信号系列表を記憶部に記憶する圧縮信号系列表作成過程と、
信号系列分割部が、入力される第１信号系列及び第２信号系列各々を、前記系列長の信号系列に分割し、第１分割信号系列及び第２分割信号系列の対である分割信号系列対の集合を抽出する信号系列分割過程と、
分割信号系列対経験分布導出部が、前記分割信号系列対の各々の経験確率分布を求める分割信号系列対経験分布導出過程と、
圧縮信号部分系列決定部が、前記分割信号系列対の各々に対応する前記経験確率分布及び前記圧縮信号系列表を参照し、該分割信号系列対に対応する圧縮信号系列である圧縮信号部分系列を定める圧縮信号部分系列決定過程と、
圧縮信号系列生成部が、前記圧縮信号部分系列の集合から、それら圧縮信号部分系列を統合することにより、第１信号系列及び第２信号系列に対応する圧縮信号系列を生成する圧縮信号系列生成過程と
から構成されることを特徴とする信号圧縮方法。
【請求項２】
前記圧縮信号系列表作成過程は、
信号系列対分類部が前記系列長を有する任意の信号系列の信号系列対に対し、該信号系列対の経験確率分布にて分類する信号系列対分類過程と、
経験分布別圧縮信号系列表作成が前記信号系列対分類過程で得られた分類各々に対し、それぞれの分類に含まれる信号系列対各々に対応する圧縮信号系列を定め、信号系列対と圧縮信号系列との対応関係を示す圧縮信号系列表である経験分布別圧縮信号系列表を作成して記憶部に記憶する経験分布別圧縮信号系列表作成過程と
から構成されることを特徴とする請求項１に記載の信号圧縮方法。
【請求項３】
前記圧縮信号部分系列決定過程は、
圧縮信号部分系列先頭決定部が、前記分割信号系列対の各々に対し、それぞれの分割信号系列対の経験確率分布に対応する番号もしくはその番号に対応する系列を、圧縮信号部分系列の先頭部分として設定する圧縮信号部分系列先頭部決定過程と、
圧縮信号部分系列後続部決定部が、前記分割信号系列対の各々について、それぞれの分割信号系列対の経験確率分布に対応する経験分布別圧縮信号系列表を参照し、分割信号系列対に対応する圧縮信号系列を導出し、該圧縮信号系列を圧縮信号部分系列の後続部分として設定する圧縮信号部分系列後続部決定過程と
から構成されることを特徴とする請求項１または請求項２に記載の信号圧縮方法。
【請求項４】
信号系列対分類選択部が前記信号系列対分類過程にて得られた分類の集合から、該分類に所属する信号系列対に対応する圧縮信号系列の長さが、あらかじめ設定された閾値である圧縮系列長閾値を下回る分類のみを選択する信号系列対分類選択過程をさらに有し、
前記経験分布別圧縮信号系列表作成過程が、前記信号系列対分類選択過程にて選択された前記分類に対して圧縮信号系列表を作成し、
前記圧縮信号部分系列後続部決定過程において、圧縮信号部分系列後続部が、圧縮信号系列表が作成されていない分類に対し、任意の系列を圧縮信号部分系列の後続部分として決定する
ことを特徴とする請求項３に記載の信号圧縮方法。
【請求項５】
複数の受信者へ信号系列を伝送する際、予め受信者が有する信号系列と、伝送の対象となる他の信号系列との２つの信号系列からなる圧縮された圧縮信号系列を復元する信号復元方法であり、
圧縮信号系列分割部が、前記圧縮信号系列を分割し、復元圧縮信号部分系列を生成する圧縮信号系列分割過程と、
圧縮信号系列表同定部が、前記圧縮信号系列分割過程にて得られた復元圧縮信号部分系列の各々に対し、それぞれの圧縮信号部分系列に対応する圧縮信号系列表を、圧縮信号部分系列に対応して圧縮信号系列表が記憶されている記憶部から同定する圧縮信号系列表同定過程と、
分割信号系列復元部が、前記復元圧縮信号部分系列各々と、前記予め受信者が有する信号系列を予め設定された系列長にて分割して生成した第２分割信号系列とにより、その復元圧縮信号部分系列に対応して前記圧縮信号系列表同定過程にて得られた圧縮信号系列表である復元圧縮信号系列表から、前記第２分割信号系列の対である分割信号系列を読み出し、復元第１分割信号系列とする分割信号系列復元過程と、
復元信号系列生成部が、前記分割信号系列復元にてえられた前記復元第１分割信号系列の集合から、それら復元第１分割信号系列を統合することにより、予め受信者が有する信号系列と対をなす伝送の対象となる他の信号系列を復元する復元信号系列生成過程と
から構成されることを特徴とする信号復元方法。
【請求項６】
前記圧縮信号系列表同定過程において、前記圧縮信号系列表同定部が前記圧縮信号系列分割過程にて得られた復元圧縮信号部分系列各々について、それぞれの圧縮信号部分系列の先頭部分から、その圧縮信号部分系列を生成した経験分布別圧縮信号系列表を同定し
前記先頭部分がそれぞれの分割信号系列対の経験確率分布に対応する番号もしくはその番号に対応する系列であることを特徴とする請求項５に記載の信号復元方法。
【請求項７】
伝送の対象となる２つの信号系列である第１信号系列及び第２信号系列について、これら信号系列を、２つの信号系列のうちいずれかの信号系列を所有する複数の受信者へ伝送する信号伝送に用いる、上記信号系列を圧縮する信号圧縮装置であり、
設定された一定の長さの系列長を有する任意の２つの信号系列からなる信号系列対に対し、該信号系列対の経験確率分布を用いて、信号系列対に対応する圧縮信号系列を設定し、信号系列対と圧縮信号系列との対応関係を示す圧縮信号系列表を生成し、該圧縮信号系列表を記憶部に記憶する圧縮信号系列表作成部と、
入力される第１信号系列及び第２信号系列各々を、前記系列長の信号系列に分割し、第１分割信号系列及び第２分割信号系列の対である分割信号系列対の集合を抽出する信号系列分割部と、
前記分割信号系列対の各々の経験確率分布を求める分割信号系列対経験分布導出部と、
前記分割信号系列対の各々に対応する前記経験確率分布及び前記圧縮信号系列表を参照し、該分割信号系列対に対応する圧縮信号系列である圧縮信号部分系列を定める圧縮信号部分系列決定部と、
前記圧縮信号部分系列の集合から、それら圧縮信号部分系列を統合することにより、第１信号系列及び第２信号系列に対応する圧縮信号系列を生成する圧縮信号系列生成部と
から構成されることを特徴とする信号圧縮装置。
【請求項８】
複数の受信者へ信号系列を伝送する際、予め受信者が有する信号系列と、伝送の対象となる他の信号系列との２つの信号系列からなる圧縮された圧縮信号系列を復元する信号復元装置であり、
前記圧縮信号系列を分割し、復元圧縮信号部分系列を生成する圧縮信号系列分割部と、
前記圧縮信号系列分割部にて得られた復元圧縮信号部分系列の各々に対し、それぞれの圧縮信号部分系列に対応する圧縮信号系列表を、圧縮信号部分系列に対応して圧縮信号系列表が記憶されている記憶部から同定する圧縮信号系列表同定部と、
前記復元圧縮信号部分系列各々と、前記予め受信者が有する信号系列を予め設定された系列長にて分割して生成した第２分割信号系列とにより、その復元圧縮信号部分系列に対応して前記圧縮信号系列表同定部にて得られた圧縮信号系列表である復元圧縮信号系列表から、前記第２分割信号系列の対である分割信号系列を読み出し、復元第１分割信号系列とする分割信号系列復元部と、
前記分割信号系列復元にてえられた前記復元第１分割信号系列の集合から、それら復元第１分割信号系列を統合することにより、予め受信者が有する信号系列と対をなす伝送の対象となる他の信号系列を復元する復元信号系列生成部と
から構成されることを特徴とする信号復元装置。
【請求項９】
コンピュータに請求項１〜請求項４のいずれかに記載の信号圧縮方法を実行させるためのコンピュータが実行可能なプログラム。
【請求項１０】
コンピュータに請求項５または請求項６に記載の信号復元方法を実行させるためのコンピュータが実行可能なプログラム。
【請求項１１】
請求項９または請求項１０に記載のプログラムを記録したコンピュータ読み取り可能な記録媒体。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図２】
【図３】
【図４】
【図５】
【図６】
【公開番号】特開２００８−２４４６４８（Ｐ２００８−２４４６４８Ａ）
【公開日】平成２０年１０月９日（２００８．１０．９）
【国際特許分類】
【出願番号】特願２００７−７９８３８（Ｐ２００７−７９８３８）
【出願日】平成１９年３月２６日（２００７．３．２６）
【新規性喪失の例外の表示】特許法第３０条第１項適用申請有り ２００６年１１月２８日 第２９回情報理論とその応用シンポジウム実行委員会発行の「第２９回情報理論とその応用シンポジウム予稿集」に発表
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２０年１０月９日（２００８．１０．９）
【国際特許分類】
【出願日】平成１９年３月２６日（２００７．３．２６）
【新規性喪失の例外の表示】特許法第３０条第１項適用申請有り ２００６年１１月２８日 第２９回情報理論とその応用シンポジウム実行委員会発行の「第２９回情報理論とその応用シンポジウム予稿集」に発表
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]