(57)【特許請求の範囲】
【請求項１】
複数のデータ系列のデータが入力され、任意のデータ系列のデータを選択して出力するセレクタと、
ｎ個（ｎは自然数）のデータを記憶する記憶領域を有し、この記憶領域の１番目からｎ−Ｌｓ番目（Ｌｓは１より大きくｎより小さい自然数）の領域を第一の領域、ｎ−Ｌｓ＋１番目からｎ番目の領域を第二の領域とし、前記第二の領域には前記セレクタにより選択されたデータ系列の各データが順次記録されるバッファと、
前記バッファの前記第一の領域に予め記録されている第一のデータと、前記バッファの前記第二の領域に記録された第二のデータとを比較し、前記第一の領域及び第二の領域のいずれにも記録される部分データを検索し、前記部分データを所定の形式のストリームに符号化して出力する演算器と、
前記記憶領域に記憶されているｎ個のデータを前記部分データに基づき決められるデータ数だけ前記記憶領域の１番目の領域側へシフトして前記バッファに記録された前記第一のデータ及び第二のデータを更新し、前記セレクタの選択を切り替え、前記データ系列とは異なるデータ系列のデータを順次前記バッファの前記第二の領域に記録するよう制御する制御部と、
を備えたことを特徴とする符号化器。
【請求項２】
制御部は、部分データの長さ分だけ、バッファの記憶領域に記憶されたｎ個のデータのうち最も古いデータを削除し、この一部が削除された前記記憶領域に記録された各データを前記記憶領域の１番目の領域側へシフトさせ、前記記憶領域内の前記削除によって空いた部分に、セレクタによって切り替えられたデータ系列のデータを記録する
ことを特徴とする請求項１に記載の符号化器。
【請求項３】
制御部は、第一の領域内で検索された部分データ又は第二の領域内で検索された部分データの一方をバッファの記録から削除し、この一部が削除された前記記憶領域に記録された各データを前記記憶領域の１番目の領域側へシフトさせ、前記記憶領域内の前記削除によって空いた部分に、セレクタによって切り替えられたデータ系列のデータを記録する
ことを特徴とする請求項１に記載の符号化器。
【請求項４】
演算器は、所定の形式のストリームに同期コードを付することを特徴とする請求項１〜３のいずれかに記載の符号化器。
【請求項５】
前記所定の形式は、少なくとも検索された部分データの第一の領域における開始位置と該部分データの長さとを示す形式であることを特徴とする請求項１〜４のいずれかに記載の符号化器。
【請求項６】
請求項１〜４のいずれかに記載の符号化器から出力された複数のデータ系列が符号化されたストリームを入力し、予め復号されたデータに基づき、前記ストリームを復号して部分データを得る演算器と、
前記演算器に接続されるとともに前記復号されたデータが記憶され、前記演算器によってデータが復号されると記憶されたデータが更新されるバッファと、
前記演算器に接続され、順番にデータ系列を切り替え、前記演算器によって復号された部分データを前記複数のデータ系列毎に分配する分配器と
を備えたことを特徴とする復号器。
【請求項７】
複数のデータ系列から、任意のデータ系列を選択するステップと、
ｎ個（ｎは自然数）のデータを記憶する記憶領域を有するバッファに対し、この記憶領域の１番目からｎ−Ｌｓ番目（Ｌｓは１より大きくｎより小さい自然数）の領域を第一の領域、ｎ−Ｌｓ＋１番目からｎ番目の領域を第二の領域とし、前記第二の領域に選択されたデータ系列の各データを順次記録するステップと、
前記バッファの前記第一の領域に予め記録されている第一のデータと、前記バッファの前記第二の領域に記録された第二のデータとを比較し、前記第一の領域及び第二の領域のいずれにも記録される部分データを検索するステップと、
前記検索により得られた部分データを所定の形式のストリームに符号化して出力するステップと、
前記記憶領域に記憶されているｎ個のデータを前記部分データに基づき決められるデータ数だけ前記記憶領域の１番目の領域側へシフトして前記バッファに記録された前記第一のデータ及び第二のデータを更新するステップと、
前記データ系列とは異なるデータ系列に切り替え、この切り替えられたデータ系列のデータを順次バッファの前記第二の領域に記録するステップと
を有することを特徴とする符号化方法。
【請求項８】
前記所定の形式は、少なくとも検索された部分データの第一の領域における開始位置と該部分データの長さとを示す形式であることを特徴とする請求項７に記載の符号化方法。
【請求項９】
請求項７に記載の符号化方法で複数のデータ系列が符号化されたストリームを入力し、予め復号されバッファに記憶されたデータに基づき、前記ストリームを復号して部分データを得る復号ステップと、
前記復号ステップによってデータが復号されるとバッファに記憶されたデータを更新する更新ステップと、
順番にデータ系列を切り替え、前記復号ステップによって復号された部分データを前記複数のデータ系列毎に分配する分配ステップと
を有することを特徴とする復号方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、テレビ放送の送受信機、立体テレビの送受信機、またはそれらの蓄積装置などに関し、特に、全文の字幕とその要約字幕、立体視の左右画像など複数の同期したデータ系列に対する符号化器と復号器、及び、符号化方法と復号方法に関するものである。
【０００２】
【従来の技術】
データ系列を可逆的に符号化する方法として、ZivとLempelによって提案されたユニバーサル符号化方法がある。
【０００３】
このユニバーサル符号化方法を実現する従来の符号化器について、図４を用いて説明する。図４は、従来の符号化器の構成を示す構成図である。
図４において、４０はバッファである。４１はバッファ４０に接続された演算器である。
【０００４】
次に、図４に示す従来の符号化器の動作について説明する。
まず、データ系列を構成する各シンボルは、バッファ４０に入力される。このバッファ４０に入力された各シンボルは、演算器４１で符号化される。なお、一度に符号化されるシンボルの数は、バッファ４０の容量や内容に依存する。その後、バッファ４０に入力された各シンボルは、符号化されたシンボルの数だけシフトされ、この空いた部分に次のシンボルが書き込まれる。
以後、入力されるデータ系列が全て符号化されるまで、バッファ４０の更新とシンボルの符号化とが繰り返し行われる。
【０００５】
次に、図４に示す従来の符号化器の動作について、図５を用いて詳細に説明する。
図5は、IEEE トランザクション オン インフォメーション セオリー(Transactions on Information Theory)誌の１９７７年５月号、337〜343ページに掲載された論文"A universal algorithm for sequential data compression"(J. Ziv and A. Lempel)に開示されたデータ符号化アルゴリズムの流れ図である。なお、符号化されるデータ系列をＳとし、このデータ系列Ｓのうちｐ番目の位置から始まりｑ番目の位置で終わるデータ系列Ｓの部分列をＳ（ｐ、ｑ）とする。
また、バッファをＢとし、このバッファＢ内に記録されたｐ番目の部分列をＢ（ｐ）とする。また、バッファＢ内に記録されたｐ番目からｑ番目の部分列をＢ（ｐ、ｑ）とする。また、バッファＢに記憶可能なシンボル数をｎとする。なお、ｎは容量であってもよい。
【０００６】
まず、ステップ５０では、バッファＢの初期化が行われる。つまり、バッファＢの最初から（ｎ−Ｌｓ）番目までのシンボルを０とし、残りの（ｎ−Ｌｓ＋１）番目からｎ番目までのＬｓ個にはデータ系列Ｓの部分列Ｓ（１、Ｌｓ）のシンボルを入力する。
なお、バッファＢの最初から（ｎ−Ｌｓ）番目までを、バッファの第一の領域とし、この第一の領域に記録されるデータを第一のデータとする。また、バッファＢの（ｎ−Ｌｓ＋１）番目からｎ番目までを、バッファの第二の領域とし、この第二の領域に記録されるデータを第二のデータとする。
また、Ｌｓは適当なシンボル数である。しかし、Ｌｓはｎに対応して容量であってもよい。
【０００７】
以後、バッファＢの最初から（ｎ−Ｌｓ）番目までには、以前に符号化処理されたシンボルが入り、（ｎ−Ｌｓ＋１）番目以降には、これから符号化されるシンボルが入る。
【０００８】
仮に、ｎ＝１８、Ｌｓ＝９、Ｓ＝００１０１０２１０２１０２１２０２１０２１２００とする。なお、この各シンボルは３進法で表現されているものとする。この例における、現時点でのバッファＢの内容（Ｂ１）は、Ｂ１＝０００００００００００１０１０２１０となる。
このステップ５０を終了すると、ステップ５１に進む。
【０００９】
次に、ステップ５１では、バッファＢ内に見られる同一文字列を検索する。つまり、バッファＢ内に残っている過去のデータ系列であるＢ（１、ｎ−Ｌｓ）から、バッファＢ（ｎ−Ｌｓ＋１、ｎ−Ｌｓ＋ｘ）と一致する部分列を検索する。なお、より正確には、検索される部分列は、その先頭のシンボルが既に符号化されたシンボル（Ｂ（１、ｎ−Ｌｓ）の中）から始まればよく、その検索される部分列の最後のシンボルはこれから符号化されるデータ（Ｂ（ｎ−Ｌｓ＋１）以降）の中にあってもよい。なお、ｘは適当な整数値である。
【００１０】
このような検索される部分列のうち、整数値ｘが最大となる最長の部分列をＬｃ、その長さをｃ（＝ｍａｘ（ｘ））とする。部分列ＬｃがバッファＢのｐ番目の位置から始まるとすれば、Ｌｃ＝Ｂ（ｐ、ｐ＋ｃ−１）＝Ｂ（ｎ−Ｌｓ＋１、ｎ−Ｌｓ＋ｃ）が成り立つ。この例では、Ｌｃ＝００となる。
この部分列Ｌｃのはじまる位置ｐは複数考えられるが、仮にｐ＝９とする。この部分列Ｌｃに、Ｂ（ｎ−Ｌｓ＋ｃ＋１）番目のシンボルを追加した文字列をＳｉとする。このシンボルは、過去のシンボルと一致しない新しいシンボルにおける最初のシンボルである。なお、文字列Ｓｉの長さをｌｉとすると、ｌｉ＝ｃ＋１である。また、Ｓｉ＝Ｂ（ｎ−Ｌｓ＋１、ｎ−Ｌｓ＋ｌｉ）である。上述の例では、Ｓｉ＝００１となる。
ステップ５１が終了すると、ステップ５２に進む。
【００１１】
次に、ステップ５２では、得られた文字列Ｓｉを符号化する。このステップ５２での符号化とは、文字列Ｓｉを、バッファＢ内での位置や長さ等を示すビットストリームＣｉに変換するものである。このビットストリームＣｉは、ビットストリームＣｉ（１）、ビットストリームＣｉ（２）、及びビットストリームＣｉ（３）からなり、Ｃｉ＝（Ｃｉ（１）、Ｃｉ（２）、Ｃｉ（３））と表現される。そして、このビットストリームＣｉ（１）は、バッファＢ内における文字列Ｓｉの始点であり、Ｃｉ（１）＝ｐ−１で求められる。また、ビットストリームＣｉ（２）は、文字列Ｓｉにおける部分列Ｌｃの長さであり、Ｃｉ（２）＝ｌｉ−１で求められる。さらに、ビットストリームＣｉ（３）は文字列Ｓｉの最後のシンボルである。
【００１２】
そして、これらの各ビットストリームＣｉ（ｍ）を表現するために必要なシンボル数（桁数）は、以下のように定められる。なお、ｍは自然数である。ビットストリームＣｉ（１）はｌｏｇ（ｎ−Ｌｓ）で求められ、ビットストリームＣｉ（２）はｌｏｇ（Ｌｓ）で求められ、ビットストリームＣｉ（３）は１である。なお、対数の底はシンボルが取り得る値の数であり、例えば、シンボルが２進数の場合は２、シンボルが３進数の場合は３となる。また、計算結果が整数でない場合には、最も近い整数に切り上げられる。
【００１３】
なお、上述の例では、ビットストリームＣ１（１）及びビットストリームＣ１（２）の桁数は、それぞれ２シンボルとなる。ゆえに、上述の算式で、現時点で得られた計算値を所定の桁数で表現すると、Ｃ１（１）＝２２、Ｃ１（２）＝０２、Ｃ１（３）＝１となり、Ｃ１＝２２０２１となる。なお、この例の各ビットストリームＣ１（ｍ）は３進法で表現されている。
この符号化により得られたビットストリームＣ１は、演算器４１から出力される。
ステップ５２が終了すると、ステップ５３に進む。
【００１４】
ステップ５３では一連の処理を終了するか否か終了判定を行う。つまり、データ系列の全てのシンボルが符号化されたかどうか判定する。そして、全てのシンボルが符号化された場合には、一連の処理を終了し、そうでなければ、ステップ５４に進む。
【００１５】
ステップ５４では、バッファＢの内容を更新する。まずはバッファＢの内容を、文字列Ｓｉの長さｌｉだけシフトする。これによって、長さｌｉ個の最も古いシンボルがバッファＢから廃棄される。そして、シフトによって空いた部分には、データ系列Ｓの新しいシンボルが入力される。
【００１６】
なお、上の例でＢ１に続く現時点でのバッファの内容をＢ２とする。上述の例では、まずバッファＢの内容を左に３シンボルシフトして、Ｂ２＝００００００００１０１０２１０ＸＸＸとなる。そして、ＸＸＸの部分には、データ系列Ｓの次のシンボル２１０が入力される。ゆえに、Ｂ２＝００００００００１０１０２１０２１０となる。
ステップ５４を終了すると、ステップ５１に戻る。
【００１７】
以後、全てのシンボルの符号化が終わるまで、ステップ５０〜５４が繰り返される。上述の例では、Ｃ２＝２１１０２、Ｂ３＝００００１０１０２１０２１０２１２０、Ｃ３＝２０２１２、Ｂ４＝２１０２１０２１２０２１０２１２００、Ｃ４＝０２２２０…となる。なお、演算器４１からは、ビットストリームＣ１、ビットストリームＣ２、ビットストリームＣ３、ビットストリームＣ４、…が出力される。
【００１８】
【発明が解決しようとする課題】
従来のＺｉｖ−Ｌｅｍｐｅｌ符号化器は、以上のように構成されており、単一のデータ系列を符号化することはできたが、複数のデータ系列を符号化することはできなかった。
【００１９】
本発明は、このような問題点を解決するためになされたものであり、複数のデータ系列を効率よく符号化する符号化器及びこの符号化器に対応する復号器を得ることを目的とするものである。
【００２０】
【課題を解決するための手段】
この発明にかかる符号化器は、複数のデータ系列のデータが入力され、任意のデータ系列のデータを選択して出力するセレクタと、ｎ個（ｎは自然数）のデータを記憶する記憶領域を有し、記憶領域の１番目からｎ−Ｌｓ番目（Ｌｓは１より大きくｎより小さい自然数）の領域を第一の領域、ｎ−Ｌｓ＋１番目からｎ番目の領域を第二の領域とし、第二の領域にはセレクタにより選択されたデータ系列の各データが順次記録されるバッファと、バッファの第一の領域に予め記録されている第一のデータと、バッファの第二の領域に記録された第二のデータとを比較し、第一の領域及び第二の領域のいずれにも記録される部分データを検索し、部分データを所定の形式のストリームに符号化して出力する演算器と、記憶領域に記憶されているｎ個のデータを部分データに基づき決められるデータ数だけ記憶領域の１番目の領域側へシフトしてバッファに記録された第一のデータ及び第二のデータを更新し、セレクタの選択を切り替え、データ系列とは異なるデータ系列のデータを順次バッファの第二の領域に記録するよう制御する制御部とを備えたものである。
【００２１】
また、この発明にかかる符号化器の制御部は、部分データの長さ分だけ、バッファの記憶領域に記憶されたｎ個のデータのうち最も古いデータを削除し、この一部が削除された記憶領域に記録された各データを記憶領域の１番目の領域側へシフトさせ、記憶領域内の削除によって空いた部分に、セレクタによって切り替えられたデータ系列のデータを記録するものである。
【００２２】
さらに、この発明にかかる符号化器の制御部は、第一の領域内で検索された部分データ又は第二の領域内で検索された部分データの一方をバッファの記録から削除し、この一部が削除された記憶領域に記録された各データを記憶領域の１番目の領域側へシフトさせ、記憶領域内の削除によって空いた部分に、セレクタによって切り替えられたデータ系列のデータを記録するものである。
【００２３】
また、この発明にかかる符号化器の演算器は、所定の形式のストリームに同期コードを付するものである。
【００２４】
この発明にかかる復号器は、所定の形式が、少なくとも検索された部分データの第一の領域における開始位置と該部分データの長さとを示す形式であるものである。
【００２５】
また、この発明にかかる復号器は、符号化器から出力された複数のデータ系列が符号化されたストリームを入力し、予め復号されたデータに基づき、ストリームを復号して部分データを得る演算器と、演算器に接続されるとともに復号されたデータが記憶され、演算器によってデータが復号されると記憶されたデータが更新されるバッファと、演算器に接続され、順番にデータ系列を切り替え、演算器によって復号された部分データを複数のデータ系列毎に分配する分配器を有するものである。
【００２６】
この発明にかかる符号化方法は、複数のデータ系列から、任意のデータ系列を選択するステップと、ｎ個（ｎは自然数）のデータを記憶する記憶領域を有するバッファに対し、この記憶領域の１番目からｎ−Ｌｓ番目（Ｌｓは１より大きくｎより小さい自然数）の領域を第一の領域、ｎ−Ｌｓ＋１番目からｎ番目の領域を第二の領域とし、第二の領域に選択されたデータ系列の各データを順次記録するステップと、バッファの第一の領域に予め記録されている第一のデータと、バッファの第二の領域に記録された第二のデータとを比較し、第一の領域及び第二の領域のいずれにも記録される部分データを検索するステップと、検索により得られた部分データを所定の形式のストリームに符号化して出力するステップと、記憶領域に記憶されているｎ個のデータを部分データに基づき決められるデータ数だけ記憶領域の１番目の領域側へシフトしてバッファに記録された第一のデータ及び第二のデータを更新するステップと、データ系列とは異なるデータ系列に切り替え、この切り替えられたデータ系列のデータを順次バッファの第二の領域に記録するステップとを有するものである。
【００２７】
この発明にかかる復号方法は、所定の形式が、少なくとも検索された部分データの第一の領域における開始位置と該部分データの長さとを示す形式であるものである。
この発明にかかる復号方法は、符号化方法で複数のデータ系列が符号化されたストリームを入力し、予め復号されバッファに記憶されたデータに基づき、ストリームを復号して部分データを得る復号ステップと、復号ステップによってデータが復号されるとバッファに記憶されたデータを更新する更新ステップと、順番にデータ系列を切り替え、復号ステップによって復号された部分データを複数のデータ系列毎に分配する分配ステップとを有するものである。
【００２８】
【発明の実施の形態】
実施の形態１．
本発明による複数のデータ系列の符号化方法を実現する符号化器の一実施形態について、図１を用いて説明する。図１は、本実施形態の複数のデータ系列の符号化方法を実現する符号化器の構成を示す構成図である。
図１において、１０はセレクタである。１１はセレクタ１０に接続されたバッファである。１２はバッファ１１に接続された演算器である。
【００２９】
次に、図１に示す本実施形態の複数のデータ系列の符号化方法を実現する符号化器の動作について説明する。
複数のデータ系列はセレクタ１０に並列に入力され、このうちひとつが選択されてバッファ１１に送られる。バッファ１１に送られたデータ系列の内容は演算器１２に読み込まれ、従来例の場合と同様に、符号化が行われ、得られたビットストリームＣｉが演算器から出力される。そして、あるビットストリームＣｉが演算器から出力されると、セレクタ１０は、バッファ１１に入力されるデータ系列を異なる次順のデータ系列に切り替える。
【００３０】
次順のデータ系列のシンボルが入力されたバッファ１１は、このデータ系列を用いて、バッファ１１の記録内容を更新する。そして、演算器１２は、更新されたバッファ１１の内容を読み込み、そのバッファ１１に記録されたデータ系列のシンボルを符号化する。
以下、全てのデータ系列のシンボルが符号化されるまで、セレクタ１０による切替えと、バッファ１１の内容の更新と、各データ系列のシンボルの符号化が繰り返される。
【００３１】
次に、図１に示す本実施形態の複数のデータ系列の符号化方法を実現する符号化器の動作について、図２を用いて詳細に説明する。図２は、図１に示す本実施形態の複数のデータ系列の符号化方法を実現する符号化器の動作を示す流れ図である。なお、一連の処理の制御は、図示されていない制御部により行われる。また、初期状態において、セレクタ１０は１番目のデータ系列１を選択するものとする。
【００３２】
まず、ステップ２０では、データ系列１（Ｓ（１））を用いて、バッファ１１の初期化を行う。なお、ｎ＝１８、Ｌｓ＝９、Ｓ（１）＝００１０１０２１０２１０２１２０２１０２１２００とする。この時点でのバッファ１１の内容は、Ｂ１＝０００００００００００１０１０２１０となる。また、データ系列１とは異なる次順のデータ系列２（Ｓ（２））を、Ｓ（２）＝００１０１０２１０２１２０２１１２００とする。
このステップ２０が終了すると、ステップ２１に進む。
【００３３】
ステップ２１では、バッファ１１内に繰り返し見られる部分列Ｌｃを検索する。そして、演算器１２は、バッファ１１内に見られた最長の部分列Ｌｃを検索し、それに続く１シンボルを付加して文字列Ｓｉを算出する。この時点での文字列Ｓｉ（Ｓ１）は、Ｓ１＝００１となる。なお、文字列Ｓｉは、部分データともいう。
このステップ２１が終了すると、ステップ２２に進む。
【００３４】
次に、ステップ２２では、得られた文字列Ｓｉを符号化して、ビットストリームＣｉを得る。なお、Ｃｉ＝（Ｃｉ（１）、Ｃｉ（２）、Ｃｉ（３））である。この時点でのビットストリームＣｉ（Ｃ１）は、Ｃ１＝２２０２１となる。
ステップ２２が終了すると、ステップ２３に進む。
【００３５】
ステップ２３では、全てのデータ系列の全てのシンボルが符号化されたかどうか終了判定を行う。
全てのデータ系列の全てのシンボルが符号化された場合には一連の処理を終了し、そうでなければ、ステップ２４に進む。
【００３６】
ステップ２４では、データ系列の切り替えを行う。つまり、あるデータ系列の文字列Ｓｉに対応するビットストリームＣｉが演算器１２から出力されても、まだ符号化されるべきデータ系列のシンボルが残っているか判断し、残っている場合には、セレクタ１０を切り替え、あるデータ系列の残っているシンボルをバッファ１１に入力するよう準備する。
ステップ２４が終了すると、ステップ２５に進む。
【００３７】
ステップ２５では、切り替えられたデータ系列のシンボルの入力に際してバッファ１１を更新する。まずは、現在のバッファ１１の内容を、文字列Ｓｉの長さｌｉだけシフトする。これにより、長さｌｉ個の最も古いシンボルがバッファ１１から消去される。なお、このシフトは、新たなデータ系列が書き込まれる前に行われる。
上述の例では、バッファ１１は３シンボルだけシフトされるから、Ｂ１＝０００００００１０１０２１０ＸＸＸとなる。なお、Ｘの部分は任意のシンボルである（例えば０）。
【００３８】
そして、このバッファ１１のＢ（ｎ−Ｌｓ＋１、ｎ）部分は、次順の異なるデータ系列のまだ符号化されていない最初の部分列に置き換えられ、バッファ１１の更新が終了する。
上述の例の場合においては、更新された時点でのバッファ１１の内容をＢ２とすれば、Ｂ２＝００００００００１００１０１０２１０となる。つまり、バッファ１１の内容Ｂ１の後ろ９シンボルが、データ系列Ｓ（２）の最初の９シンボルに置き換えられている。
【００３９】
そして、Ｂ１におけるＢ（ｎ−Ｌｓ＋１、ｎ）部分（＝０１０２１０ＸＸＸ）は、再びデータ系列１に切り替えられた時に、（０１０２１０）に継続する（×××）部分をデータ系列Ｓ（１）の次なるシンボルで補った上で、バッファ１１に入力され、一連の処理が施される。
ステップ２５が終了すると、ステップ２１に戻る。
【００４０】
以後、全てのデータ系列の符号化が終わるまで、ステップ２１からステップ２５が繰り返される。
上述の例の場合、以後、Ｃ２＝２０１１１、Ｂ３＝０００１００１０１０１０２１０２１０、Ｃ３＝２１１０２、Ｂ４＝００１０１０１０２０２１０２１２０２、Ｃ４＝２１０２１、Ｂ５＝０１０１０２０２１１０２１０２１２０、Ｃ５＝１０１０１…となる。
なお、ビットストリームＣ１、ビットストリームＣ２、ビットストリームＣ３、ビットストリームＣ４、…は演算器１２から出力される。
また、本実施形態の符号化器における文字列Ｓｉの検出方法、及びビットストリームＣｉへの符合化方法については、従来例と同様であり、その説明を簡略化した。
【００４１】
このように、本実施形態の符号化器は、複数のデータ系列が順次切り替えられて符号化されるので、互いに相手のデータ系列で検索された一致文字列を用いて符号化することができ、複数の類似データ系列を効率よく符号化することができる。
【００４２】
実施の形態２．
次に、本発明の他の実施形態について説明する。
本実施形態の符号化器のバッファ１１は、同じ文字列が重複して記憶されないように、重複する文字列は削除している。つまり、バッファ１１に記憶された過去のデータのうち、新しく入力されたデータと一致する部分は消去され、バッファ１１がシフトされる。なお、消去されるデータは、過去のデータ（シンボル）でも、新しく入力されたデータ（シンボル）でもよい。
【００４３】
以下に、例を述べる。データ系列Ｓ（１）は、Ｓ（１）＝００１０１０２１０２１０２１２０２１０２１２００であるとする。また、データ系列Ｓ（１）とは異なるデータ系列Ｓ（２）は、Ｓ（２）＝００１０１０２１０２１２０２１１２００であるとする。なお、バッファの初期化から、文字列Ｓｉの検索、そして得られた文字列Ｓｉを符号化するまでは、実施形態１と同じであり、その説明を省略する。
その後、ビットストリームＣｉを出力し、バッファ１１を更新する時点で、バッファ（Ｂ１）はＢ１＝０００００００００００１０１０２１０であり、文字列（Ｓ１）はＳ１＝００１であり、位置（ｐ）はｐ＝９であり、文字列の長さ（ｌ１）はｌ１＝３が得られている。
【００４４】
この文字列Ｓ１のうち、最初の２シンボル（００）は、バッファの中で繰り返し用いられた文字列Ｌｃである。しかし、ｐ＝９であるから、（００）のうち、最初の０は過去に符号化されたシンボルであり、２番目の０は符号化する文字列が自分自身と一致したシンボルである。なお、いまの場合、最初の０は初期化のステップで入力された０であるから厳密には過去に符号化されたシンボルではないが、符号化が進むと、バッファのこの部分には過去に符号化されたシンボルが入力される。
【００４５】
そこで、バッファの更新ステップ（ステップ２５）では、過去に符号化されたシンボル（例では最初の０）をバッファから削除し、その削除したデータの分だけシフトする。つまり、上述の例の場合では、バッファＢ１はＢ１＝００００００００００１０１０２１０Ｘとなり、１シンボル分左にシフトする。なお、Ｘは任意である。また、このとき削除されたシンボルの数をｄとする。
【００４６】
そして、次に、文字列Ｓｉに相当する部分を、過去に符号化されたバッファの記録領域に入るように、残りの（ｌｉ−ｄ）シンボルだけシフトする。上述の例では、Ｂ１＝００００００００１０１０２１０ＸＸＸとなる。以降は、実施形態１と同様に、バッファのＢ（ｎ−Ｌｓ＋１、ｎ）部分を新しいデータ系列（上述の例ではデータ系列Ｓ（２））の先頭の文字列で置き換え、バッファが更新ｓれる。つまり、Ｂ２＝００００００００１００１０１０２１０となる。
【００４７】
上述の例の場合、以降、以下のように進む。Ｃ２＝２０１１１、Ｂ３＝００００００１０１０１０２１０２１０、Ｃ３＝２１１０２、Ｂ４＝００００１０１０２０２１０２１２０２、Ｃ４＝２１０２１、Ｂ５＝０００１０１０２１１０２１０２１２０、Ｃ５＝１２１１０…。なお、Ｂ５（２、８）は、データ系列Ｓ（１）又はデータ系列Ｓ（２）の最初の７シンボルと一致する。
【００４８】
バッファの更新を上述のように行うことにより、複数のデータ系列間の重複するデータが削除されるので、一致する文字列が長くなり、符号化効率が向上する場合がある。また、複数のデータ系列間の重複するデータを削除できるので、バッファの使用効率が向上する。さらに、複数のデータ系列間の重複するデータを削除してバッファを更新するので、バッファの大きさを小さくすることができる。
【００４９】
また、複数のデータ系列が順次切り替えられて符号化されるので、互いに相手のデータ系列で検索された一致文字列を用いて符号化することができ、複数のデータ系列を効率よく符号化することができる。また、異なる系列間で重複する文字列をバッファから削除するようにしたので、共通する文字列はその生起順に記憶される確率が高くなり、一致文字列の長さが長くなって、符号化効率を向上することができる。
【００５０】
実施の形態３．
次に、本発明の他の実施形態について説明する。
本実施形態の符号化器は、複数のデータ系列間で同期をとるために、各データ系列に同期信号を付加して符号化するものである。なお、本実施形態の符号化方法は、実施形態１又は実施形態２と併用してもよい。なお、同期信号（同期コード）とは、複数のデータ系列間のあるシンボルが同時に生じるべきものであることを示す情報である。
【００５１】
例えば、ステレオ画像の右画像のデータ系列と左画像のデータ系列とにおいて、空間的に近い位置を示すデータ同士は時間的にも近い時点で生じるべきものであり、同期をとる必要がある。また、字幕情報における全文の字幕データのデータ系列とその要約版のデータ系列とでは、意味的に近いデータ同士であり、時間的に近い時点で生じさせるべきものであり、同期をとる必要がある。これらの同期は、各データ系列間の適当な時点で、強制的に同期信号の発生させ、一致させることによって実現される。
【００５２】
なお、同期信号は、ビットストリームＣｉ（１）、ビットストリームＣｉ（２）、ビットストリームＣｉ（３）のいずれに多重してもよい。この同期コードのため、ビットストリームＣｉ（１）はシンボル数ｎ、ビットストリームＣｉ（２）はシンボル数Ｌｓを制限し、空いたところに同期コードを割り当てる。
【００５３】
実施形態１や実施形態２の例では、シンボル数ｎはｎ＝１８であったが、これを１７（シンボル数ＬｓはＬｓ＝９のまま）にすることにより、ビットストリームＣｉ（１）＝２２を同期コードとすることができる。また、データ系列が文字系列であるときは、文字として使用されないコード（例えばＡＳＣＩＩの￥（円記号）など）をビットストリームＣｉ（３）に多重して同期コードとしてもよい。
【００５４】
この同期コードを用いることにより、複数のデータ系列間の任意のブロックにおいて、全てのデータ系列と同じブロックが全て符号化し終えたかどうか知ることができる。なお、ブロックとは、各データ系列における同意の部分であり、ある同期点から次の同期点までのデータ系列の集合のことである。つまり、あるデータ系列におけるあるブロックのデータの符号化が終了しても、他のデータ系列の対応するブロックの符号化が終了しない限り、セレクタ１０によって選択されず、次のブロックの符号化ができない。それゆえ、相互データ系列間で、ブロック単位での同期を図ることができる。
【００５５】
このように、本実施形態の符号化器は、複数のデータ系列を同期するための情報を符号化するようにしたので、バッファ内のデータに一致文字列を発見する確率が高くなり、符号化効率を向上することができる。
また、同期信号を各データ系列間で同様のタイミングで付加することにより、類似するデータ系列間において、時間的に対応する部分を、互いのデータ系列を参照しながら符号化することができ、一致する文字列Ｓｉが長くなり、符号化効率が向上する。
【００５６】
実施の形態４．
本発明による複数のデータ系列の符号化方法で符号化された複数のデータ系列を復元する復号器の一実施形態について、図３を用いて説明する。図３は、本実施形態の複数のデータ系列の符号化方法で符号化された複数のデータ系列を復号する復号器の構成を示す構成図である。
図３において、３０は演算器である。３１は演算器３０に接続されたバッファである。３２は演算器３０に接続された分配器である。
【００５７】
次に、図３に示す本実施形態の複数のデータ系列の符号化方法で符号化されたデータ系列を復号する復号器の動作について説明する。
符合器で符号化され出力されたビットストリームＣｉは、演算器３０に順次入力される。入力されたビットストリームＣｉを用いて、文字列Ｓｉは、一意に復号される。すなわち、ビットストリームＣｉ（１）に示されたバッファ内のアドレス位置ｐのシンボルから、ビットストリームＣｉ（２）に示された長さ（ｌｉ−１）の文字列を、Ｂ（ｎ−Ｌｓ＋１）から順番に復元し、最後にビットストリームＣｉ（３）を付加することによって、文字列Ｓｉを得る。
【００５８】
なお、ビットストリームＣｉは、Ｃｉ＝（Ｃｉ（１）、Ｃｉ（２）、Ｃｉ（３））であり、ビットストリームＣｉ（１）はＣｉ（１）＝ｐ−１であり、ビットストリームＣｉ（２）はＣｉ（２）＝ｌｉ−１であり、ビットストリームＣｉ（３）は文字列Ｓｉの最後のシンボルである。
演算器３０は、バッファ３１を参照しながらこの処理を行い、文字列Ｓｉを分配器３２に与える。分配器３２は、得られた文字列Ｓｉを、もとのデータ系列に分配する。
【００５９】
文字列Ｓｉが復号される毎にバッファ３１は更新される。バッファ３１の更新は、符号化器におけるバッファ３１のＢ（１、ｎ−Ｌｓ）の部分が再現されるように行われる。すなわち、実施形態１の符号化方法の場合には、復元された文字列Ｓｉを順番にバッファ３１に記憶していく。実施形態２の符号化方法の場合には、バッファ３１内の一致する文字列Ｓｉは廃棄した後、新しく復号されたシンボルをバッファ３１に書き込む。
【００６０】
このように、本実施形態の復号器は、データを復号する演算器の後段にこのデータを複数の系列に切り替えて出力する分配器を設けたので、実施形態１又は実施形態２に示す符号化器で符号化されたビットストリームを効率よく復号することができる。また、本実施形態の復号器は、類似する複数のデータ系列を全て復元することができる。
なお、符合器と復号器との間で伝送されるデータ系列の数は、あらかじめ合意されているものとする。この符合器と復号器との合意に基づき、分配器３２は、順番にデータ系列を切り替え、複数のデータ系列を正しく復号することができる。
【００６１】
実施の形態５．
次に、本発明の他の実施形態について説明する。
本実施形態の復号器は、複数の類似するデータ系列のうちから、一部のデータ系列だけを選択的に復元するものである。つまり、本実施形態の復号器の演算器３０は、復号の要求がないデータ系列に対して、バッファの更新にのみ必要な信号処理を行うだけで、文字列Ｓｉを算出しない。
【００６２】
例えば、実施形態２で符号化されたデータでは、ｐ＋ｌｉ−２＝ｎ−Ｌｓの時、つまり一致部分列Ｌｃがもっとも最近に符号化された部分列である時、文字列Ｓｉを復号することなく、バッファ３１を左に１シンボルだけシフトし、ビットストリームＣｉ（３）を空いた部分に書き込む。このことによりバッファ３１の更新だけが完了する。
【００６３】
このように、本実施形態の復号器は、データを復号する演算器の後段にこのデータを複数の系列に選択的に切り替えて出力する分配器を設けたので、実施形態１又は実施形態２に示す符号化器で符号化されたビットストリームから一部のデータ系列を効率よく復号することができる。
【００６４】
実施の形態６．
次に、本発明の他の実施形態について説明する。
本実施形態の復号器は、複数のデータ系列間の同期をとるために付加された同期信号を含む各データ系列を復号するものである。本実施形態の復号器の分配器３２は、検出された同期信号に応じて、その出力を切り替えるようにしてもよい。この場合、分配器３２は、同期信号が検出されたデータ系列に対しては、他のデータ系列の該当するブロックの復号が終了するまで、次のブロックの出力が禁止される。
【００６５】
このように、本実施形態の復号器は、データを復号する演算器の後段に、伝送された同期信号に基づいて複数の系列に切り替えて出力する分配器を設けたので、実施形態３に示す符号化器で符号化されたビットストリームを効率よく復号することができる。
また、この復号器は、符号化器で符号化されたビットストリームＣｉを、各データ系列間で同期させた上で、正しく復号することができる。
なお、本実施形態の復号器は、実施形態３の符合器に対応するものであり、実施形態４又は実施形態５と併用してもよい。
【００６６】
【発明の効果】
この発明にかかる符号化器は、複数のデータ系列のデータが入力され、任意のデータ系列のデータを選択して出力するセレクタと、ｎ個（ｎは自然数）のデータを記憶する記憶領域を有し、記憶領域の１番目からｎ−Ｌｓ番目（Ｌｓは１より大きくｎより小さい自然数）の領域を第一の領域、ｎ−Ｌｓ＋１番目からｎ番目の領域を第二の領域とし、第二の領域にはセレクタにより選択されたデータ系列の各データが順次記録されるバッファと、バッファの第一の領域に予め記録されている第一のデータと、バッファの第二の領域に記録された第二のデータとを比較し、第一の領域及び第二の領域のいずれにも記録される部分データを検索し、部分データを所定の形式のストリームに符号化して出力する演算器と、記憶領域に記憶されているｎ個のデータを部分データに基づき決められるデータ数だけ記憶領域の１番目の領域側へシフトしてバッファに記録された第一のデータ及び第二のデータを更新し、セレクタの選択を切り替え、データ系列とは異なるデータ系列のデータを順次バッファの第二の領域に記録するよう制御する制御部とを備えたものであり、複数のデータ系列が順次切り替えられて符号化されるので、互いのデータ系列で検索された一致文字列を用いて符号化することができ、複数の類似データ系列を効率よく符号化することができる。
【００６７】
また、この発明にかかる符号化器の演算器は、所定の形式のストリームに同期コードを付するものであり、複数のデータ系列で同期をとることができるため、バッファ内のデータに一致文字列を発見する確率が高くなり、符号化効率を向上させることができる。
【００６８】
また、この発明にかかる復号器は、複数のデータ系列が符号化されたストリームを入力し、予め復号されたデータに基づき、ストリームを復号して部分データを得る演算器と、演算器に接続されるとともに復号されたデータが記憶され、演算器によってデータが復号されると記憶されたデータが更新されるバッファと、演算器に接続され、順番にデータ系列を切り替え、演算器によって復号された部分データを複数のデータ系列毎に分配する分配器を備えたものであり、複数のデータ系列のストリームを効率よく復号することができる。
【００６９】
この発明にかかる符号化方法は、複数のデータ系列から、任意のデータ系列を選択するステップと、この選択されたデータ系列のデータをバッファに記録するステップと、バッファの第一の領域に記録された第一のデータと、バッファの第二の領域に記録された第二のデータとを比較し、第一の領域及び第二の領域のいずれにも記録される部分データを検索するステップと、検索により得られた部分データを所定の形式のストリームに符号化して出力するステップと、部分データに基づき、バッファに記録された第一のデータ及び第二のデータを更新するステップと、データ系列とは異なるデータ系列に切り替え、この切り替えられたデータ系列のデータを、その記録内容が更新されたバッファに記録するステップとを有するものであり、複数のデータ系列が順次切り替えられて符号化されるので、互いのデータ系列で検索された一致文字列を用いて符号化することができ、複数の類似データ系列を効率よく符号化することができる。
【００７０】
この発明にかかる復号方法は、符号化方法で複数のデータ系列が符号化されたストリームを入力し、予め復号されバッファに記憶されたデータに基づき、ストリームを復号して部分データを得る復号ステップと、復号ステップによってデータが復号されるとバッファに記憶されたデータを更新する更新ステップと、順番にデータ系列を切り替え、復号ステップによって復号された部分データを複数のデータ系列毎に分配する分配ステップとを有するものであり、複数のデータ系列のストリームを効率よく復号することができる。
【図面の簡単な説明】
【図１】  本発明の実施形態１の複数のデータ系列の符号化方法を実現する符号化器の構成を示す構成図である。
【図２】  図１に示す本発明の実施形態１の複数のデータ系列の符号化方法を実現する符号化器の動作を示す流れ図である。
【図３】  本発明の実施形態４の複数のデータ系列の符号化方法で符号化された複数のデータ系列を復号する復号器の構成を示す構成図である。
【図４】  従来の符号化器の構成を示す構成図である。
【図５】  IEEE トランザクション オン インフォメーション セオリー誌に開示されたデータ符号化アルゴリズムの流れ図である。
【符号の説明】
１０  セレクタ、１１  バッファ、１２  演算器、３０  演算器、３１  バッファ、３２  分配器、４０  バッファ、４１  演算器。
【図１】
0003812289.tif 000002
【図２】
0003812289.tif 000003
【図３】
0003812289.tif 000004
【図４】
0003812289.tif 000005
【図５】
0003812289.tif 000006