(57)【要約】【課題】  簡易な構成であるとともにデータの劣化を抑制しつつ必要に応じて迅速にデータの圧縮を行うデータ圧縮装置を提供する。【解決手段】  データ圧縮装置１は、入力データを成すビットの一部または全部を第１入力部分データとして生成し残余のビットを第２入力部分データとして生成する入力データ分割部１０と、指定されたアドレスにビットを書き込む記憶部１１と、第１入力部分データを成すビットが記憶部１１の隣接したアドレスに順次書き込まれていくようにアドレスを順次指定する第１アドレス指定部１２と、第２入力部分データを成すビットが記憶部１１の隣接したアドレスに順次書き込まれていくようにアドレスを順次指定する第２アドレス指定部１３と、第１アドレス指定部１２の指定するアドレスが第２アドレス指定部１３の指定するアドレスよりも優先されるように両者を制御する調停部１４と、を備える。【選択図】  図１
2013172357.tif 000002
【特許請求の範囲】
【請求項１】
入力データを成すビットの一部または全部を第１入力部分データとして生成し、前記入力データの一部のビットを前記第１入力部分データとして生成する場合は、その残余のビットを第２入力部分データとして生成する入力データ分割部と、
前記第１入力部分データを成すビット及び前記第２入力部分データを成すビットを、指定されたアドレスに順次書き込む記憶部と、
前記第１入力部分データを成すビットが、前記記憶部の隣接した前記アドレスに順次書き込まれていくように、前記アドレスを順次指定する第１アドレス指定部と、
前記第２入力部分データを成すビットが、前記記憶部の隣接した前記アドレスに順次書き込まれていくように、前記アドレスを順次指定する第２アドレス指定部と、
前記記憶部に書き込もうとする前記第１入力部分データ及び前記第２入力部分データに応じて、前記第１アドレス指定部及び前記第２アドレス指定部を制御する調停部と、を備え、
前記入力データ分割部が、ｋ個（ｋは自然数）の前記入力データから前記第１入力部分データ及び前記第２入力部分データまたは前記第１入力部分データを順次生成し、前記記憶部が、連続した前記アドレスを有する記憶領域に、前記第１入力部分データ及び前記第２入力部分データまたは前記第１入力部分データを順次書き込むとき、
前記調停部は、
前記第１アドレス指定部が指定しようとする前記アドレスが、前記第２アドレス指定部が既に指定した前記アドレスまたは現に指定しようとしている前記アドレスと重複する場合、前記第１アドレス指定部に当該アドレスの指定を許可し、
前記第２アドレス指定部が指定しようとする前記アドレスが、前記第１アドレス指定部が既に指定した前記アドレスまたは現に指定しようとしている前記アドレスと重複する場合、前記第２アドレス指定部に当該アドレスの指定を許可しないことを特徴とするデータ圧縮装置。
【請求項２】
前記第１アドレス指定部は、前記記憶領域の先頭アドレス及び最終アドレスの一方を起点として前記第１入力部分データを成すビットが書き込まれるように、前記記憶領域の前記アドレスを指定し、
前記第２アドレス指定部は、前記記憶領域の前記先頭アドレス及び前記最終アドレスの他方を起点として前記第２入力部分データを成すビットが書き込まれるように、前記記憶領域の前記アドレスを指定することを特徴とする請求項１に記載のデータ圧縮装置。
【請求項３】
前記記憶領域の前記先頭アドレス及び前記最終アドレスの一方から他方まで、前記第１入力部分データを成すビットが書き込まれると、それ以降は、前記記憶部に前記第１入力部分データを成すビットが書き込まれないことを特徴とする請求項２に記載のデータ圧縮装置。
【請求項４】
前記ｋ個の前記入力データの少なくとも１つが、二進数で表現された数値を示すビット列を含み、前記数値を示すビット列中のＭＳＢ（Most Significant Bit）が前記入力データの上位側、前記数値を示すビット列中のＬＳＢ（Least Significant Bit）が前記入力データの下位側となり、
前記入力データ分割部が、前記入力データの上位側のビットから成る前記第１入力部分データを生成するとともに、前記入力データの下位側のビットから成る前記第２入力部分データを生成することを特徴とする請求項１〜３のいずれか１項に記載のデータ圧縮装置。
【請求項５】
前記ｋ個の前記入力データの少なくとも１つが、当該入力データを成すビットの総数である総ビット数を示すビット列を含み、
前記入力データ分割部が、前記総ビット数を示すビット列を含む前記第１入力部分データを生成することを特徴とする請求項１〜４のいずれか１項に記載のデータ圧縮装置。
【請求項６】
前記入力データ分割部が、新たに前記第１入力部分データを生成するとき、
それまでに生成した前記第１入力部分データの数をｎ（ｎは０以上ｋ未満の整数）、前記記憶領域が有する前記アドレスの総数を前記ｋで除算して得られる値をｒ（ｒは１以上の数）、それまでに生成した前記第１入力部分データを成すビットの総数をｖ（ｖは自然数）、とすると、
前記入力データ分割部は、新たに生成する前記第１入力部分データを成すビットの数を、（ｎ＋１）×ｒ−ｖ個以下にすることを特徴とする請求項１〜５のいずれか１項に記載のデータ圧縮装置。
【請求項７】
前記入力データ分割部は、前記第１入力部分データを成すビットの数を、前記記憶領域の前記アドレスの総数を前記ｋで除算して得られる値以下の数にすることを特徴とする請求項１〜５のいずれか１項に記載のデータ圧縮装置。
【請求項８】
前記ｋ個の前記入力データが前記入力データ分割部に処理される順番を、所定の順番に入れ替える入力データ順番入替部を、さらに備えることを特徴とする請求項１〜７のいずれか１項に記載のデータ圧縮装置。
【請求項９】
前記入力データ分割部が生成した前記第１入力部分データを、前記記憶部に書き込まれる前に一時的に蓄積し、所定量以上の前記第１入力部分データを蓄積すると前記記憶部に転送する第１バッファと、
前記入力データ分割部が生成した前記第２入力部分データを、前記記憶部に書き込まれる前に一時的に蓄積し、所定量以上の前記第２入力部分データを蓄積すると前記記憶部に転送する第２バッファと、
をさらに備えることを特徴とする請求項１〜８のいずれか１項に記載のデータ圧縮装置。
【請求項１０】
前記第１入力部分データに対応する第１出力部分データ及び前記第２入力部分データに対応する第２出力部分データが前記記憶部から読み出される場合、前記第１出力部分データを成すビット及び前記第２出力部分データを成すビットを結合するとともにその結合したビットを含む出力データを生成し、前記第１出力部分データのみが前記記憶部から読み出される場合、前記第１出力部分データを成すビットを含む前記出力データを生成する出力データ結合部を、さらに備え、
前記記憶部が、前記第１出力部分データを成すビット及び前記第２出力部分データを成すビットを、指定された前記アドレスから順次読み出し、
前記第１アドレス指定部が、前記第１出力部分データを成すビットが、前記記憶部の隣接した前記アドレスから順次読み出されていくように、前記記憶部の前記アドレスを順次指定し、
前記第２アドレス指定部が、前記第２出力部分データを成すビットが、前記記憶部の隣接した前記アドレスから順次読み出されていくように、前記記憶部の前記アドレスを順次指定し、
前記調停部が、前記第１入力部分データ及び前記第２入力部分データの前記記憶部への書き込み状態に応じて、前記第１アドレス指定部及び前記第２アドレス指定部を制御し、
前記記憶部が、前記記憶領域から前記第１出力部分データ及び前記第２出力部分データを順次読み出し、前記出力データ結合部が前記出力データを順次生成するとき、
前記調停部が、
前記記憶領域から読み出される前記第１出力部分データを成すビットと、前記記憶領域から読み出される前記第２出力部分データを成すビットとが、元は同じ前記入力データを成していたものとなるように、前記第１アドレス指定部及び前記第２アドレス指定部を制御することを特徴とする請求項１〜９のいずれか１項に記載のデータ圧縮装置。
【請求項１１】
前記出力データ結合部は、
前記第１出力部分データ及び前記第２出力部分データが前記記憶部から読み出される場合における前記第１出力部分データを成すビット及び前記第２出力部分データを成すビットを結合して成るビットの数、または、前記第１出力部分データのみが前記記憶部から読み出される場合における前記第１出力部分データを成すビットの数が、元の前記入力データを成していたビットの数と同数であるときの前記出力データの生成方法と、
前記第１出力部分データ及び前記第２出力部分データが前記記憶部から読み出される場合における前記第１出力部分データを成すビット及び前記第２出力部分データを成すビットを結合して成るビットの数、または、前記第１出力部分データのみが前記記憶部から読み出される場合における前記第１出力部分データを成すビットの数が、元の前記入力データを成していたビットの数に対して不足しているときの前記出力データの生成方法と、
が異なることを特徴とする請求項１０に記載のデータ圧縮装置。
【請求項１２】
前記出力データ結合部は、
前記第１出力部分データ及び前記第２出力部分データが前記記憶部から読み出される場合における前記第１出力部分データを成すビット及び前記第２出力部分データを成すビットを結合して成るビットの数、または、前記第１出力部分データのみが前記記憶部から読み出される場合における前記第１出力部分データを成すビットの数が、元の前記入力データを成していたビットの数と同数であるとき、
前記第１出力部分データを成すビット及び前記第２出力部分データを成すビットを結合して成るビット、または、前記第１出力部分データを成すビットから成る前記出力データを生成し、
前記第１出力部分データ及び前記第２出力部分データが前記記憶部から読み出される場合における前記第１出力部分データを成すビット及び前記第２出力部分データを成すビットを結合して成るビットの数、または、前記第１出力部分データのみが前記記憶部から読み出される場合における前記第１出力部分データを成すビットの数が、元の前記入力データを成していたビットの数に対して不足しているとき、
前記第１出力部分データを成すビット及び前記第２出力部分データを成すビットを結合して成るビット、または、前記第１出力部分データを成すビットに、その不足している数のビットを結合させることで、前記出力データを生成することを特徴とする請求項１１に記載のデータ圧縮装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、必要に応じてデータを圧縮するデータ圧縮装置に関する。
【背景技術】
【０００２】
データの圧縮方法として、圧縮率は低いが伸張後のデータを圧縮前のデータに完全に一致させることができる可逆圧縮と、圧縮に伴い一部のデータが失われるために伸張後のデータを圧縮前のデータに完全に一致させることはできないが高い圧縮率を実現することができる非可逆圧縮と、がある。所定のデータ量以下となるように圧縮する必要がある場合や、元のデータ量が非常に大きく高い圧縮率を確保する必要がある場合などでは、非可逆圧縮が採用されることが多い。また、圧縮率をより向上させる観点から、データによらず符号長を一定とする固定長符号化よりも、データに応じて符号長を短くすることができる可変長符号化が採用されることが多い。
【０００３】
例えば、データ量が大きい音声データや画像データなどを圧縮する場合、非可逆圧縮かつ可変長符号化となる処理が行なわれることが多い。このとき、人が認識し難い部分のデータが失われるように圧縮されるが、それでも圧縮によるデータの劣化は小さい方が好ましい。そこで、圧縮によるデータの劣化を抑制する方法が、種々検討されている。
【０００４】
特許文献１では、順次入力される画素ブロックに対して、可逆圧縮及び非可逆圧縮をそれぞれ行い、得られた双方の符号化データの符号長に基づいて、いずれか一方の符号化データを選択的にメモリに記憶する画像符号化装置が提案されている。この画像符号化装置では、画素ブロックをメモリに順次記憶している途中で、それまでに得られた符号化データの全体の符号量が目標符号量を超えた場合、それまでメモリに記憶した符号化データを破棄する。そして、それまでに得られた符号化データのうち、非可逆圧縮によって得られた符号化データの全体の符号量が、可逆圧縮によって得られた符号化データの全体の符号量よりも大きければ（非可逆圧縮が支配的であれば）、より高い圧縮率で非可逆圧縮が行われるように、非可逆圧縮の量子化マトリクスを変更した上で、全ての画素ブロックを再圧縮する。一方、それまでに得られた符号化データのうち、非可逆圧縮によって得られた符号化データの全体の符号量が、可逆圧縮によって得られた符号化データの全体の符号量以下であれば（可逆圧縮が支配的であれば）、メモリに記憶する符号化データとして、非可逆圧縮された符号化データがより選択されやすくなるように、符号化データの選択方法を変更した上で、全ての画素ブロックを再圧縮する。
【０００５】
また、特許文献２では、動画データ中の一定区間の入力画像データを、事前に解析することで、それぞれの入力画像データに割り当てる符号量を決定して、符号化バッファのオーバーフローまたはアンダーフローを防止する動画符号化装置が提案されている。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００７−２３５７５７号公報
【特許文献２】特開２００２−２３２８８２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、特許文献１で提案されている画像符号化装置では、入力される一連の画素ブロックを順次圧縮しながら最適な条件を探すために、圧縮率が最も低くなる方法（圧縮率が最も低くなる非可逆圧縮の量子化マトリクスを採用、かつ、メモリに記憶する符号化データとして可逆圧縮された符号化データが最も選択されやすい選択方法を採用）で圧縮を開始し、非可逆圧縮の量子化マトリクス及び符号化データの選択方法を細かく変更しながら、メモリに記憶した符号化データの破棄及び再圧縮を何度も繰り返す必要がある。そのため、結果的に無駄になる圧縮が多く行われることで処理が煩雑になるとともに、一連の処理に多大な時間がかかる。
【０００８】
一方、特許文献２で提案されている動画符号化装置では、一定区間に含まれる複数の入力画像データの圧縮をする前に、これらの全体を解析してそれぞれの入力画像に適した符号量を割り当てるため、無駄な圧縮が行われることはない。しかしながら、この動画符号化装置では、一定区間に含まれる複数の入力画像データの全てを一時的に保持する必要があるために、容量が大きい記憶装置が別途必要になる。さらに、この動画符号化装置では、全ての入力画像データの解析が終了するまで、入力画像データの圧縮を開始することができないため、特許文献１で提案されている画像符号化装置と同様に、一連の処理に多大な時間がかかる。
【０００９】
そこで、本発明は、簡易な構成であるとともにデータの劣化を抑制しつつ必要に応じて迅速にデータの圧縮を行うデータ圧縮装置を提供することを目的とする。
【課題を解決するための手段】
【００１０】
上記目的を達成するため、本発明は、入力データを成すビットの一部または全部を第１入力部分データとして生成し、前記入力データの一部のビットを前記第１入力部分データとして生成する場合は、その残余のビットを第２入力部分データとして生成する入力データ分割部と、前記第１入力部分データを成すビット及び前記第２入力部分データを成すビットを、指定されたアドレスに順次書き込む記憶部と、前記第１入力部分データを成すビットが、前記記憶部の隣接した前記アドレスに順次書き込まれていくように、前記アドレスを順次指定する第１アドレス指定部と、前記第２入力部分データを成すビットが、前記記憶部の隣接した前記アドレスに順次書き込まれていくように、前記アドレスを順次指定する第２アドレス指定部と、前記記憶部に書き込もうとする前記第１入力部分データ及び前記第２入力部分データに応じて、前記第１アドレス指定部及び前記第２アドレス指定部を制御する調停部と、を備え、前記入力データ分割部が、ｋ個（ｋは自然数）の前記入力データから前記第１入力部分データ及び前記第２入力部分データまたは前記第１入力部分データを順次生成し、前記記憶部が、連続した前記アドレスを有する記憶領域に、前記第１入力部分データ及び前記第２入力部分データまたは前記第１入力部分データを順次書き込むとき、前記調停部は、前記第１アドレス指定部が指定しようとする前記アドレスが、前記第２アドレス指定部が既に指定した前記アドレスまたは現に指定しようとしている前記アドレスと重複する場合、前記第１アドレス指定部に当該アドレスの指定を許可し、前記第２アドレス指定部が指定しようとする前記アドレスが、前記第１アドレス指定部が既に指定した前記アドレスまたは現に指定しようとしている前記アドレスと重複する場合、前記第２アドレス指定部に当該アドレスの指定を許可しないことを特徴とするデータ圧縮装置を提供する。
【００１１】
このデータ圧縮装置によれば、第１入力部分データを成すビットを、第２入力部分データを成すビットよりも優先的に記憶領域に書き込むことで、第２入力部分データを成すビットを欠落させ、入力データを圧縮することが可能になる。また、入力データの圧縮を、第１入力部分データを成すビットを書き込むアドレスと第２入力部分データを成すビットを書き込むアドレスとが重複する場合に、限定することが可能になる。
【００１２】
さらに、上記特徴のデータ圧縮装置において、前記第１アドレス指定部は、前記記憶領域の先頭アドレス及び最終アドレスの一方を起点として前記第１入力部分データを成すビットが書き込まれるように、前記記憶領域の前記アドレスを指定し、前記第２アドレス指定部は、前記記憶領域の前記先頭アドレス及び前記最終アドレスの他方を起点として前記第２入力部分データを成すビットが書き込まれるように、前記記憶領域の前記アドレスを指定すると、好ましい。
【００１３】
このデータ圧縮装置によれば、第１入力部分データを成すビットを書き込むアドレスと第２入力部分データを成すビットを書き込むアドレスとが重複することを、極力避けることが可能になる。したがって、入力データの圧縮による劣化を、最も抑制することが可能になる。
【００１４】
さらに、上記特徴のデータ圧縮装置において、前記記憶領域の前記先頭アドレス及び前記最終アドレスの一方から他方まで、前記第１入力部分データを成すビットが書き込まれると、それ以降は、前記記憶部に前記第１入力部分データを成すビットが書き込まれないようにすると、好ましい。
【００１５】
このデータ圧縮装置によれば、圧縮後の入力データが、記憶領域以上のデータ量になることを抑制することができる。また、記憶領域の内外で第１入力部分データによる上書きが発生することを、防止することが可能になる。
【００１６】
さらに、上記特徴のデータ圧縮装置において、前記ｋ個の前記入力データの少なくとも１つが、二進数で表現された数値を示すビット列を含み、前記数値を示すビット列中のＭＳＢ（Most Significant Bit）が前記入力データの上位側、前記数値を示すビット列中のＬＳＢ（Least Significant Bit）が前記入力データの下位側となり、前記入力データ分割部が、前記入力データの上位側のビットから成る前記第１入力部分データを生成するとともに、前記入力データの下位側のビットから成る前記第２入力部分データを生成すると、好ましい。
【００１７】
このデータ圧縮装置によれば、数値を示すビット列の中でも上位の桁を示すビットほど、第１入力部分データに含まれやすくなる。そのため、数値を示すビット列の上位の桁を示すビットが圧縮によって失われることが抑制され、入力データの圧縮による劣化を効果的に抑制することが可能になる。
【００１８】
さらに、上記特徴のデータ圧縮装置において、前記ｋ個の前記入力データの少なくとも１つが、当該入力データを成すビットの総数である総ビット数を示すビット列を含み、前記入力データ分割部が、前記総ビット数を示すビット列を含む前記第１入力部分データを生成すると、好ましい。
【００１９】
このデータ圧縮装置によれば、入力データの総ビット数を示すビット列が圧縮によって失われることを、防止することができる。そのため、例えば記憶領域からビットを読み出して入力データを復元する（出力データを生成する）際に、元の入力データの総ビット数を確実に把握することが可能になる。
【００２０】
さらに、上記特徴のデータ圧縮装置において、前記入力データ分割部が、新たに前記第１入力部分データを生成するとき、それまでに生成した前記第１入力部分データの数をｎ（ｎは０以上ｋ未満の整数）、前記記憶領域が有する前記アドレスの総数を前記ｋで除算して得られる値をｒ（ｒは１以上の数）、それまでに生成した前記第１入力部分データを成すビットの総数をｖ（ｖは自然数）、とすると、前記入力データ分割部は、新たに生成する前記第１入力部分データを成すビットの数を、（ｎ＋１）×ｒ−ｖ個以下にしてもよい。
【００２１】
このデータ圧縮装置によれば、第１入力部分データを成すビットの全てを、記憶領域に書き込むことが可能になる。そのため、例えば序盤で生成される第１入力部分データを成すビット数が多くなりすぎて、終盤に生成される第１入力部分データを成すビットを記憶領域に書き込むことができなくなることを、防止することが可能になる。さらに、記憶領域に余裕があれば、第１入力部分データのビット数を大きくすることが可能になる。
【００２２】
また、上記特徴のデータ圧縮装置において、前記入力データ分割部は、前記第１入力部分データを成すビットの数を、前記記憶領域の前記アドレスの総数を前記ｋで除算して得られる値以下の数にしてもよい。
【００２３】
このデータ圧縮装置によれば、第１入力部分データを成すビットの全てを、記憶領域に書き込むことが可能になる。そのため、例えば序盤で生成される第１入力部分データを成すビット数が多くなりすぎて、終盤に生成される第１入力部分データを成すビットを記憶領域に書き込むことができなくなることを、防止することが可能になる。さらに、第１入力部分データ及び第２入力部分データを、簡易的に生成することが可能になる。
【００２４】
さらに、上記特徴のデータ圧縮装置において、前記ｋ個の前記入力データが前記入力データ分割部によって処理される順番を、所定の順番に入れ替える入力データ順番入替部を、さらに備えると、好ましい。
【００２５】
このデータ圧縮装置によれば、入力データ順番入替部によって、重要な入力データほど記憶領域に先に書き込まれるようにすることで、重要な入力データの劣化を効果的に抑制することが可能になる。
【００２６】
さらに、上記特徴のデータ圧縮装置において、前記入力データ分割部が生成した前記第１入力部分データを、前記記憶部に書き込まれる前に一時的に蓄積し、所定量以上の前記第１入力部分データを蓄積すると前記記憶部に転送する第１バッファと、前記入力データ分割部が生成した前記第２入力部分データを、前記記憶部に書き込まれる前に一時的に蓄積し、所定量以上の前記第２入力部分データを蓄積すると前記記憶部に転送する第２バッファと、をさらに備えると、好ましい。
【００２７】
このデータ圧縮装置によれば、第１入力部分データ及び第２入力部分データを、記憶部に安定して書き込むことが可能になる。
【００２８】
さらに、上記特徴のデータ圧縮装置において、前記第１入力部分データに対応する第１出力部分データ及び前記第２入力部分データに対応する第２出力部分データが前記記憶部から読み出される場合、前記第１出力部分データを成すビット及び前記第２出力部分データを成すビットを結合するとともにその結合したビットを含む出力データを生成し、前記第１出力部分データのみが前記記憶部から読み出される場合、前記第１出力部分データを成すビットを含む前記出力データを生成する出力データ結合部を、さらに備え、前記記憶部が、前記第１出力部分データを成すビット及び前記第２出力部分データを成すビットを、指定された前記アドレスから順次読み出し、前記第１アドレス指定部が、前記第１出力部分データを成すビットが、前記記憶部の隣接した前記アドレスから順次読み出されていくように、前記記憶部の前記アドレスを順次指定し、前記第２アドレス指定部が、前記第２出力部分データを成すビットが、前記記憶部の隣接した前記アドレスから順次読み出されていくように、前記記憶部の前記アドレスを順次指定し、前記調停部が、前記第１入力部分データ及び前記第２入力部分データの前記記憶部への書き込み状態に応じて、前記第１アドレス指定部及び前記第２アドレス指定部を制御し、前記記憶部が、前記記憶領域から前記第１出力部分データ及び前記第２出力部分データを順次読み出し、前記出力データ結合部が前記出力データを順次生成するとき、前記調停部が、前記記憶領域から読み出される前記第１出力部分データを成すビットと、前記記憶領域から読み出される前記第２出力部分データを成すビットとが、元は同じ前記入力データを成していたものとなるように、前記第１アドレス指定部及び前記第２アドレス指定部を制御すると、好ましい。
【００２９】
このデータ圧縮装置によれば、入力データを復元して成る出力データを、得ることが可能になる。
【００３０】
さらに、上記特徴のデータ圧縮装置において、前記出力データ結合部は、前記第１出力部分データ及び前記第２出力部分データが前記記憶部から読み出される場合における前記第１出力部分データを成すビット及び前記第２出力部分データを成すビットを結合して成るビットの数、または、前記第１出力部分データのみが前記記憶部から読み出される場合における前記第１出力部分データを成すビットの数が、元の前記入力データを成していたビットの数と同数であるときの前記出力データの生成方法と、前記第１出力部分データ及び前記第２出力部分データが前記記憶部から読み出される場合における前記第１出力部分データを成すビット及び前記第２出力部分データを成すビットを結合して成るビットの数、または、前記第１出力部分データのみが前記記憶部から読み出される場合における前記第１出力部分データを成すビットの数が、元の前記入力データを成していたビットの数に対して不足しているときの前記出力データの生成方法と、が異なると、好ましい。
【００３１】
このデータ圧縮装置によれば、圧縮による入力データの劣化に応じた適切な復元方法を選択して、出力データを生成することが可能になる。
【００３２】
さらに、上記特徴のデータ圧縮装置において、前記出力データ結合部は、前記第１出力部分データ及び前記第２出力部分データが前記記憶部から読み出される場合における前記第１出力部分データを成すビット及び前記第２出力部分データを成すビットを結合して成るビットの数、または、前記第１出力部分データのみが前記記憶部から読み出される場合における前記第１出力部分データを成すビットの数が、元の前記入力データを成していたビットの数と同数であるとき、前記第１出力部分データを成すビット及び前記第２出力部分データを成すビットを結合して成るビット、または、前記第１出力部分データを成すビットから成る前記出力データを生成し、前記第１出力部分データ及び前記第２出力部分データが前記記憶部から読み出される場合における前記第１出力部分データを成すビット及び前記第２出力部分データを成すビットを結合して成るビットの数、または、前記第１出力部分データのみが前記記憶部から読み出される場合における前記第１出力部分データを成すビットの数が、元の前記入力データを成していたビットの数に対して不足しているとき、前記第１出力部分データを成すビット及び前記第２出力部分データを成すビットを結合して成るビット、または、前記第１出力部分データを成すビットに、その不足している数のビットを結合させることで、前記出力データを生成すると、好ましい。
【００３３】
このデータ圧縮装置によれば、圧縮により欠落したビットと同数のビットを、出力データの生成時に補充することが可能になる。
【発明の効果】
【００３４】
上記特徴のデータ圧縮装置によれば、記憶領域内に書き込まれたビット数（データ量）が大きくなった場合に限定して、入力データの圧縮を行うことが可能になる。そのため、入力データの圧縮を必要最小限に留め、入力データの劣化を抑制することが可能になる。また、上記特徴のデータ圧縮装置は、記憶領域に書き込んだまたは書き込もうとする入力データを、適応的に圧縮するものであるため、複数の入力データの全てを別途保持するメモリを備えたり、既に記憶領域に書き込んだ入力データを破棄して再圧縮を行ったりする必要がない。したがって、簡易な構成で迅速に入力データを圧縮することが可能になる。
【図面の簡単な説明】
【００３５】
【図１】本発明の実施形態に係るデータ圧縮装置の概略構造例を示すブロック図。
【図２】本発明の実施形態に係るデータ圧縮装置の概略動作例を示す図。
【図３】本発明の実施形態に係るデータ圧縮装置の具体的な動作例（動作例１）を示す図。
【図４】本発明の実施形態に係るデータ圧縮装置の具体的な動作例（動作例２）を示す図。
【図５】本発明の実施形態に係るデータ圧縮装置の具体的な動作例（動作例３）を示す図。
【図６】本発明の実施形態に係るデータ圧縮装置の具体的な動作例（動作例４）を示す図。
【図７】本発明の実施形態に係るデータ圧縮装置の具体的な動作例（別動作例）を示す図。
【図８】本発明の実施形態に係るデータ圧縮装置の概略構造の別例を示すブロック図。
【図９】本発明の実施形態に係るデータ圧縮装置の概略構造の別例を示すブロック図。
【発明を実施するための形態】
【００３６】
＜＜概略構造及び概略動作＞＞
最初に、本発明の実施形態に係るデータ圧縮装置の概略構造例について、図１を参照して説明する。図１は、本発明の実施形態に係るデータ圧縮装置の概略構造例を示すブロック図である。
【００３７】
図１に示すように、データ圧縮装置１は、入力データ分割部１０と、記憶部１１と、第１アドレス指定部１２と、第２アドレス指定部１３と、調停部１４と、出力データ結合部１５と、を備える。
【００３８】
入力データ分割部１０は、入力データを成すビットの一部または全部を第１入力部分データとして生成する（書き込み時）。また、入力データ分割部１０は、入力データの一部を第１入力部分データとして生成する場合は、その残余のビットを第２入力部分データとして生成する（書き込み時）。なお、入力データ分割部１０が、第１入力部分データを成すビットとして入力データを成すどのビットを選択するかの詳細については、具体例を挙げて後述する。
【００３９】
記憶部１１は、第１入力部分データを成すビット及び第２入力部分データを成すビットを、指定されたアドレスに１ビットずつ順次書き込む（書き込み時）。また、記憶部１１は、第１出力部分データを成すビット及び第２出力部分データを成すビットを、指定された前記アドレスから１ビットずつ順次読み出す（読み出し時）。
【００４０】
第１アドレス指定部１２は、第１入力部分データを成すビットが、記憶部１１の隣接したアドレスに１ビットずつ順次書き込まれていくように、１ビットに対して１アドレスを順次指定する（書き込み時）。また、第１アドレス指定部１２は、第１出力部分データを成すビットが、記憶部１１の隣接したアドレスから１ビットずつ順次読み出されていくように、１ビットに対して１アドレスを順次指定する（読み出し時）。
【００４１】
第２アドレス指定部１３は、第２入力部分データを成すビットが、記憶部１１の隣接したアドレスに１ビットずつ順次書き込まれていくように、１ビットに対して１アドレスを順次指定する（書き込み時）。また、第２アドレス指定部１３は、第２出力部分データを成すビットが、記憶部１１の隣接したアドレスから１ビットずつ順次読み出されていくように、１ビットに対して１アドレスを順次指定する（読み出し時）。
【００４２】
調停部１４は、記憶部１１に書き込もうとする第１入力部分データ及び第２入力部分データに応じて、第１アドレス指定部１２及び第２アドレス指定部１３を制御する（書き込み時）。また、調停部１４は、第１入力部分データ及び第２入力部分データの記憶部１１への書き込み状態に応じて、第１アドレス指定部１２及び第２アドレス指定部１３を制御する（読み出し時）。なお、調停部１４による第１アドレス指定部１２及び第２アドレス指定部１３の詳細な制御方法については、具体例を挙げて後述する。
【００４３】
出力データ結合部１５は、第１出力部分データ及び第２出力部分データが記憶部１１から読み出される場合、第１出力部分データを成すビット及び第２出力部分データを成すビットを結合するとともにその結合したビットを含む出力データを生成する（読み出し時）。また、出力データ結合部１５は、第１出力部分データのみが記憶部１１から読み出される場合、第１出力部分データを成すビットを含む出力データを生成する（読み出し時）。
【００４４】
次に、本発明の実施形態に係るデータ圧縮装置の概略動作例について、図２を参照して説明する。図２は、本発明の実施形態に係るデータ圧縮装置の概略動作例を示す図である。
【００４５】
図２は、データ圧縮装置１が、ｋ個（ｋは自然数）の入力データＰ１，Ｐ２，・・・，Ｐｋを、入力データＰ１、入力データＰ２、・・・、入力データＰ（ｋ−１）、入力データＰｋの順番で処理する場合を例示したものである。図２では、入力データＰ１，Ｐ２，・・・，Ｐｋについて、上位のビットが左側、下位のビットが右側となるように示している。なお、上述のように、入力データ分割部１０は、入力データを分割せずに第１入力部分データのみを生成する場合もあるが、図２では説明の簡易化のため、入力データ分割部１０が全ての入力データＰ１，Ｐ２，・・・，Ｐｋを分割して、第１入力部分データＸ１ａ，Ｘ２ａ，・・・，Ｘｋａ及び第２入力部分データＸ１ｂ，Ｘ２ｂ，・・・，Ｘｋｂのそれぞれを生成する場合について例示する。また、入力データ分割部１０が、入力データを分割せずに第１入力部分データのみを生成し得る場合については、具体例を挙げて後述する。
【００４６】
また、記憶部１１は、第１入力部分データＸ１ａ，Ｘ２ａ，・・・，Ｘｋａを成すビット及び第２入力部分データＸ１ｂ，Ｘ２ｂ，・・・，Ｘｋｂを成すビットを、連続したアドレスを有する記憶領域１１１に書き込もうとする。最初に、第１アドレス指定部１２が、記憶領域１１１の先頭アドレスＡＳを起点として、第１入力部分データＸ１ａを成すビットが上位から順に書き込まれるように、記憶領域１１１のアドレスを指定する。同様に、第２アドレス指定部１３が、記憶領域１１１の最終アドレスＡＥを起点として、第２入力部分データＸ１ｂを成すビットが上位から順に書き込まれるように、記憶領域１１１のアドレスを指定する。これにより、記憶領域１１１の先頭部分に第１入力部分データＸ１ａが書き込まれ、記憶領域１１１の最終部分に第２入力部分データＸ１ｂが書き込まれる。
【００４７】
次に、第１アドレス指定部１２は、第１入力部分データＸ１ａを成す最下位のビットが書き込まれた記憶領域１１１のアドレスに隣接して、第１入力部分データＸ２ａをなすビットが上位から順に書き込まれるように、記憶領域１１１のアドレスを指定する。以降同様に、前回第１入力部分データを成す最下位のビットが書き込まれた記憶領域１１１のアドレスに隣接して、次回の第１入力部分データをなすビットが上位から順に書き込まれるように、記憶領域１１１のアドレスを順次指定する。これにより、記憶領域１１１の先頭アドレスＡＳから順に、第１入力部分データＸ１ａ，Ｘ２ａ，Ｘ３ａ，・・・，Ｘｓａが書き込まれる（ｓはｋ未満の自然数）。
【００４８】
同様に、第２アドレス指定部１３は、第２入力部分データＸ１ｂを成す最下位のビットが書き込まれた記憶領域１１１のアドレスに隣接して、第１入力部分データＸ２ｂをなすビットが上位から順に書き込まれるように、記憶領域１１１のアドレスを指定する。以降同様に、前回第２入力部分データを成す最下位のビットが書き込まれた記憶領域１１１のアドレスに隣接して、次回の第２入力部分データをなすビットが上位から順に書き込まれるように、記憶領域１１１のアドレスを順次指定する。これにより、記憶領域１１１の最終アドレスＡＥから順に、第２入力部分データＸ１ｂ，Ｘ２ｂ，Ｘ３ｂ，・・・，Ｘｓｂが書き込まれる。
【００４９】
次に、第１アドレス指定部１２は、第１入力部分データＸｓａを成す最下位のビットが書き込まれた記憶領域１１１のアドレスに隣接して、第１入力部分データＸ（ｓ＋１）ａを成すビットが上位から順に書き込まれるように、記憶領域１１１のアドレスを指定しようとする。また、第２アドレス指定部１３は、第２入力部分データＸｓｂを成す最下位のビットが書き込まれた記憶領域１１１のアドレスに隣接して、第２入力部分データＸ（ｓ＋１）ｂを成すビットが上位から順に書き込まれるように、記憶領域１１１のアドレスを指定しようとする。
【００５０】
しかし、この時点で、記憶領域１１１には、第１入力部分データＸ（ｓ＋１）ａ及び第２入力部分データＸ（ｓ＋１）ｂを成す全てのビットを書き込めるだけの、十分なアドレスが残っていない。そこで、調停部１４が、第１アドレス指定部１２及び第２アドレス指定部１３の制御を行う。
【００５１】
調停部１４は、記憶領域１１１のアドレスの総数と、記憶領域１１１に書き込まれた第１入力部分データＸ１ａ，Ｘ２ａ，・・・，Ｘｓａを成すビットの総数と、記憶領域１１１に書き込まれた第２入力部分データＸ１ｂ，Ｘ２ｂ，・・・，Ｘｓｂを成すビットの総数と、をそれぞれ把握しており、第１アドレス指定部１２が指定しようとするアドレスが、第２アドレス指定部１３が既に指定したアドレスまたは現に指定しようとしているアドレスと重複するか否か、第２アドレス指定部１３が指定しようとするアドレスが、第１アドレス指定部１２が既に指定したアドレスまたは現に指定しようとしているアドレスと重複するか否か、の双方を確認することができる。
【００５２】
調停部１４は、第１アドレス指定部１２が指定しようとするアドレスが、第２アドレス指定部１３が既に指定したアドレスまたは現に指定しようとしているアドレスと重複する場合でも、第１アドレス指定部１２に当該アドレスの指定を許可する。一方、調停部１４は、第２アドレス指定部１３が指定しようとするアドレスが、第１アドレス指定部１２が既に指定したアドレスまたは現に指定しようとしているアドレスと重複する場合、第２アドレス指定部１３に当該アドレスの指定を許可しない。
【００５３】
その結果、第１アドレス指定部１２が、第１入力部分データＸ（ｓ＋１）ａを書き込むアドレスとして、既に第２入力部分データＸｓｂが書き込まれているアドレスを指定するため、第１入力部分データＸ（ｓ＋１）ａが第２入力部分データＸｓｂの一部を上書きすることになり、第２入力部分データＸｓｂを成す一部のビットが欠落する（なお、図２では、ビットの一部が欠落した第２入力部分データを、「＊」を付して表示している）。また、第２入力部分データＸ（ｓ＋１）ｂは、第２アドレス指定部１３によって書き込むべきアドレスが指定されないため、記憶領域１１１に書き込まれない。
【００５４】
そして、以降同様に、第１入力部分データＸ（ｓ＋２）ａ，Ｘ（ｓ＋３）ａ，・・・，Ｘｋａが、記憶領域１１１に順次書き込まれる。これにより、既に記憶領域１１１に書き込まれていた第２入力部分データ＊Ｘｓｂ，Ｘ（ｓ−１）ｂ，・・・，Ｘ（ｔ−１）ｂと、第２入力部分データＸｔｂの一部のビットと、が上書きされることで欠落する（ｔはｓ未満の自然数）。また、第２入力部分データＸ（ｓ＋２）ｂ，Ｘ（ｓ＋３）ｂ，・・・，Ｘｋｂは、記憶領域１１１に書き込まれない。なお、この間、調停部１４が、第２アドレス指定部１３を停止させてもよい。
【００５５】
このように、データ圧縮装置１は、第１入力部分データを成すビットを、第２入力部分データを成すビットよりも優先的に記憶領域１１１に書き込むことで、第２入力部分データを成すビットを欠落させ、入力データＰ１，Ｐ２，・・・，Ｐｋを圧縮することが可能になる。また、入力データＰ１，Ｐ２，・・・，Ｐｋの圧縮を、第１入力部分データを成すビットを書き込むアドレスと第２入力部分データを成すビットを書き込むアドレスとが重複する場合に、限定することが可能になる。
【００５６】
次に、データ圧縮装置１は、記憶領域１１１に書き込んだビットを読み出すことで、出力データＱ１，Ｑ２，・・・，Ｑｋを生成する。このとき、記憶部１１は、第１アドレス指定部１２が指定する記憶領域１１１のアドレスに書き込まれているビットから成る、第１出力部分データＸ１ａ，Ｘ２ａ，・・・，Ｘ（ｋ−１）ａ，Ｘｋａを順次読み出す。また、記憶部１１は、第２アドレス指定部１３が指定する記憶領域１１１のアドレスに書き込まれているビットから成る、第２出力部分データＸ１ｂ，Ｘ２ｂ，・・・，Ｘ（ｔ−１）ｂ，＊Ｘｔｂを順次読み出す。なお、図２では、ビットの対応関係を明確化するために、第１入力部分データと第１出力部分データとで同じ符号を使用し、第２入力部分データと第２出力部分データとで同じ符号を使用している。
【００５７】
調停部１４は、第１入力部分データＸ１ａ，Ｘ２ａ，・・・，Ｘｋａ及び第２入力部分データＸ１ｂ，Ｘ２ｂ，・・・，Ｘｋｂの記憶領域１１１への書き込み状態（それぞれを成すビットの境界や、欠落したビットなど）を、書き込み時に把握している。これに基づき、調停部１４は、記憶領域１１１から読み出される第１出力部分データＸ１ａ，Ｘ２ａ，・・・，Ｘ（ｔ−１）ａ，Ｘｔａを成すビットと、記憶領域１１１から読み出される第２出力部分データＸ１ｂ，Ｘ２ｂ，・・・，Ｘ（ｔ−１）ｂ，Ｘｔｂを成すビットとが、元は同じ入力データＰ１，Ｐ２，・・・，Ｐ（ｔ−１），Ｐｔを成していたものとなるように、第１アドレス指定部１２及び第２アドレス指定部１３を制御する。
【００５８】
上述のように、第１入力部分データＸ１ａ，Ｘ２ａ，・・・，Ｘ（ｋ−１）ａ，Ｘｋａを成すビットが全て記憶領域１１１に記憶されているため、第１出力部分データＸ１ａ，Ｘ２ａ，・・・，Ｘ（ｋ−１）ａ，Ｘｋａは、第１入力部分データＸ１ａ，Ｘ２ａ，・・・，Ｘ（ｋ−１）ａ，Ｘｋａと等しくなる。これに対して、第２入力部分データＸ１ｂ，Ｘ２ｂ，・・・，Ｘ（ｋ−１）ｂ，Ｘｋｂは、上述のように、その一部または全部が記憶領域１１１内で上書きされることで欠落したり、その一部または全部が記憶領域１１１に書き込まれないことで欠落したりする。そのため、第２出力部分データＸ１ｂ，Ｘ２ｂ，・・・，Ｘ（ｔ−１）ｂは、第２入力部分データＸ１ｂ，Ｘ２ｂ，・・・，Ｘ（ｔ−１）ｂと等しくなるが、第２出力部分データ＊Ｘｔｂは、第２出力部分データＸｔｂの一部のビットから成る。また、第２入力部分データＸ（ｔ＋１）ｂ，Ｘ（ｔ＋２）ｂ，・・・，Ｘｋｂに対応する第２出力部分データは、存在しない。
【００５９】
出力データ結合部１５は、第１出力部分データＸ１ａを成すビット及び第２出力部分データＸ１ｂを成すビットを結合させることで、入力データＰ１と同じビットから成る出力データＱ１を生成する。同様に、出力データ結合部１５は、入力データＰ２，Ｐ３，・・・，Ｐ（ｔ−１）と同じビットから成る、出力データＱ２，Ｑ３，・・・，Ｑ（ｔ−１）を、それぞれ生成する。
【００６０】
次に、出力データ結合部１５は、第１入力部分データＸｔｂを成すビット及び第２出力部分データ＊Ｘｔｂを成すビットを結合するが、これは元の入力データＰｔを成していたビットの一部であるため、ビットの数が不足している。そこで、出力データ結合部１５は、第１入力部分データＸｔｂを成すビット及び第２出力部分データ＊Ｘｔｂを成すビットを結合し、さらに不足している数のビット＃を結合することで、出力データＱｔを生成する。なお、ビット＃は、固定値であってもよいし可変値であってもよい。
【００６１】
また、結合させるべき第２出力部分データが存在しない第１出力部分データＸ（ｔ＋１）ｂ，Ｘ（ｔ＋２）ｂ，・・・，Ｘｋａを成すビットは、元の入力データＰ（ｔ＋１），Ｐ（ｔ＋２），・・・，Ｐｋを成していたビットの一部であるため、ビットの数が不足している。そこで、出力データ結合部１５は、第１出力部分データＸ（ｔ＋１）ｂ，Ｘ（ｔ＋２）ｂ，・・・，Ｘｋａを成すそれぞれのビットに、それぞれに不足している数のビット＃を結合することで、出力データＱ（ｔ＋１），Ｑ（ｔ＋２），・・・，Ｑｋを生成する。
【００６２】
以上のように、データ圧縮装置１は、記憶領域１１１内に書き込まれたビット数（データ量）が大きくなった場合に限定して、入力データの圧縮を行うことが可能になる。そのため、入力データの圧縮を必要最小限に留め、入力データの劣化を抑制することが可能になる。また、このデータ圧縮装置１は、記憶領域１１１に書き込んだまたは書き込もうとする入力データを、適応的に圧縮するものであるため、複数の入力データの全てを別途保持するメモリを備えたり、既に記憶領域１１１に書き込んだ入力データを破棄して再圧縮を行ったりする必要がない。したがって、簡易な構成で迅速に入力データを圧縮することが可能になる。
【００６３】
また、上述のように、第１アドレス指定部１２が、記憶領域１１１の先頭アドレスＡＳを起点として第１入力部分データを成すビットが書き込まれるように、記憶領域１１のアドレスを指定し、第２アドレス指定部１３が、記憶領域１１１の最終アドレスＡＥを起点として第２入力部分データを成すビットが書き込まれるように、記憶領域１１１のアドレスを指定すると、好ましい。
【００６４】
このように構成すると、第１入力部分データを成すビットを書き込むアドレスと第２入力部分データを成すビットを書き込むアドレスとが重複することを、極力避けることが可能になる。したがって、入力データの圧縮による劣化を、最も抑制することが可能になる。なお、上述の例では、記憶領域１１１の先頭アドレスＡＳを起点として第１入力部分データを成すビットが書き込まれ、記憶領域１１１の最終アドレスＡＥを起点として第２入力部分データを成すビットが書き込まれる場合について説明したが、記憶領域１１１の最終アドレスＡＥを起点として第１入力部分データを成すビットが書き込まれ、記憶領域１１１の先頭アドレスＡＳを起点として第２入力部分データを成すビットが書き込まれるようにしてもよい。
【００６５】
また、図２に示す例は、第１入力部分データを成すビットが書き込まれるアドレスが、記憶領域１１１の最終アドレスＡＥに至らないものであるが、第１入力部分データを成すビットが書き込まれるアドレスが最終アドレスＡＥに至る場合もあり得る。このように、第１入力部分データを成すビットが最終アドレスＡＥまで書き込まれた場合、それ以降、記憶部１１に第１入力部分データを成すビットが書き込まれないようにすると、好ましい。
【００６６】
このように構成すると、圧縮後の入力データが、記憶領域１１１以上のデータ量になることを抑制することができる。また、記憶領域１１１の内外で第１入力部分データによる上書きが発生することを、防止することが可能になる。なお、このような場合であっても、第１入力部分データＸ１ａ，Ｘ２ａ，・・・，Ｘｋａのそれぞれを成すビットの少なくとも一部が記憶領域１１１に記憶されていると、全ての出力データＱ１，Ｑ２，・・・，Ｑｋを復元することが可能になるため、好ましい（詳細は後述する）。
【００６７】
また、入力データＰ１，Ｐ２，・・・，Ｐｋの少なくとも１つが、二進数で表現された数値を示すビット列を含み、その数値を示すビット列中のＭＳＢ（Most Significant Bit）が入力データの上位側、ＬＳＢ（Least Significant Bit）が入力データの下位側となる場合、第１入力部分データが入力データの上位側のビットから成り、第２入力部分データが入力データの下位側のビットから成ると、好ましい。
【００６８】
このように構成すると、数値を示すビット列の中でも上位の桁を示すビットほど、第１入力部分データに含まれやすくなる。そのため、数値を示すビット列の上位の桁を示すビットが圧縮によって失われることが抑制され、入力データの圧縮による劣化を効果的に抑制することが可能になる。
【００６９】
また、入力データＰ１，Ｐ２，・・・，Ｐｋの少なくとも１つが、当該入力データを成すビットの総数である総ビット数を示すビット列を含む場合、その総ビット数を示すビット列が第１入力部分データに含まれるようにすると、好ましい。
【００７０】
このように構成すると、入力データの総ビット数を示すビット列が圧縮によって失われることを、防止することができる。そのため、例えば上述のように、出力データ結合部１５が記憶領域１１１から読み出した、第１出力部分データを成すビット及び第２出力部分データを成すビットを用いて、または、第１出力部分データを成すビットを用いて、入力データを復元する（出力データを生成する）際に、元の入力データの総ビット数を確実に把握することが可能になる。
【００７１】
なお、図２では、出力データ結合部１５が、出力データＱ１，Ｑ２，・・・，Ｑｋを生成する際に、元の入力データに対して不足する数のビット＃を必要に応じて補充する場合について例示したが、これ以外の方法で入力データの復元を行ってもよいし、復元を行わなくてもよい。また、出力データ結合部１５が、必要に応じて入力データの復元を行う場合、入力データの復元の要否に応じて、異なる回路を使用して出力データの生成を行ってもよい。
【００７２】
＜＜動作例＞＞
次に、図１に示したデータ圧縮装置の具体的な動作例について、図３〜６を参照して説明する。図３〜６は、本発明の実施形態に係るデータ圧縮装置の具体的な動作例を示す図であり、図２に示した動作例を具体化したものである。
【００７３】
また、以下において説明するそれぞれの動作例１〜４では、入力データ分割部１０が、新たに第１入力部分データを生成するときに、当該第１入力部分データを成すビットの数を（ｎ＋１）×ｒ−ｖ個以下にするものとする。なお、ｎは、それまでに生成した第１入力部分データの数であり、０以上かつ入力データの総数ｋ未満の整数である。また、ｒは、記憶領域１１１が有するアドレスの総数であり、１以上の数である。また、ｖは、それまでに生成した第１入力部分データを成すビットの総数であり、自然数である。
【００７４】
図３〜６に示す例では、入力データＡ〜Jの総数ｋが１０、記憶領域１１１が有するアドレスの総数が４０であり、ｒ＝４である。なお、図３〜６に示す破線は、それぞれの時点における（ｎ＋１）×ｒを示しており、記憶領域１１１内で第１入力部分データを成すビットが書き込まれ得る限界のアドレスを示したものである。
【００７５】
このように構成すると、後述の動作例１〜４において具体的に示すように、第１入力部分データを成すビットの全てを、記憶領域１１１に書き込むことが可能になる。そのため、例えば序盤で生成される第１入力部分データを成すビット数が多くなりすぎて、終盤に生成される第１入力部分データを成すビットを記憶領域１１１に書き込むことができなくなることを、防止することが可能になる。さらに、記憶領域１１１に余裕があれば、第１入力部分データのビット数を大きくすることが可能になる。
【００７６】
また、図３〜６では、入力データＡ〜Jを成すビットについて、例えばＡ１のように、そのビットの位置を添字で表現する。添字の０が最も下位のビットを示し、添字が大きいビットほど上位のビットを示すこととする。
【００７７】
＜動作例１＞
図３に示す動作例１は、入力データＡ〜Ｊのそれぞれを成すビットの数が少ないために、入力データＡ〜Ｊを成すビットの総数が、記憶領域１１１が有するアドレスの総数よりも少なくなる場合における、データ圧縮装置１の動作を示すものである。具体的に例えば、入力データＡ〜Ｊが、全体的に簡素な画像データを構成する場合である。
【００７８】
最初に、３ビットの入力データＡが、記憶領域１１１に書き込まれる。上記式より求められる第１入力部分データの最大のビット数は４であるため、ここでは３ビット全てが第１入力部分データとなる。そして、記憶領域１１１の先頭アドレスから、ビットＡ２、ビットＡ１、ビットＡ０の順に書き込まれる。
【００７９】
次に、４ビットの入力データＢが、記憶領域１１１に書き込まれる。上記式より求められる第１入力部分データの最大のビット数は５であるため、ここでは４ビット全てが第１入力部分データとなる。そして、記憶領域１１１に書き込まれているビットＡ０の直後のアドレスから、ビットＢ３、ビットＢ２、ビットＢ１、ビットＢ０の順に書き込まれる。
【００８０】
次に、３ビットの入力データＣが、記憶領域１１１に書き込まれる。上記式より求められる第１入力部分データの最大のビット数は５であるため、ここでは３ビット全てが第１入力部分データとなる。そして、記憶領域１１１に書き込まれているビットＢ０の直後のアドレスから、ビットＣ２、ビットＣ１、ビットＣ０の順に書き込まれる。
【００８１】
次に、５ビットの入力データＤが、記憶領域１１１に書き込まれる。上記式より求められる第１入力部分データの最大のビット数は６であるため、ここでは５ビット全てが第１入力部分データとなる。そして、記憶領域１１１に書き込まれているビットＣ０の直後のアドレスから、ビットＤ４、ビットＤ３、ビットＤ２、ビットＤ１、ビットＤ０の順に書き込まれる。
【００８２】
次に、５ビットの入力データＥが、記憶領域１１１に書き込まれる。上記式より求められる第１入力部分データの最大のビット数は５であるため、ここでは５ビット全てが第１入力部分データとなる。そして、記憶領域１１１に書き込まれているビットＤ０の直後のアドレスから、ビットＥ４、ビットＥ３、ビットＥ２、ビットＥ１、ビットＥ０の順に書き込まれる。
【００８３】
次に、４ビットの入力データＦが、記憶領域１１１に書き込まれる。上記式より求められる第１入力部分データの最大のビット数は４であるため、ここでは４ビット全てが第１入力部分データとなる。そして、記憶領域１１１に書き込まれているビットＥ０の直後のアドレスから、ビットＦ３、ビットＦ２、ビットＦ１、ビットＦ０の順に書き込まれる。
【００８４】
次に、３ビットの入力データＧが、記憶領域１１１に書き込まれる。上記式より求められる第１入力部分データの最大のビット数は４であるため、ここでは３ビット全てが第１入力部分データとなる。そして、記憶領域１１１に書き込まれているビットＦ０の直後のアドレスから、ビットＧ２、ビットＧ１、ビットＧ０の順に書き込まれる。
【００８５】
次に、６ビットの入力データＨが、記憶領域１１１に書き込まれる。上記式より求められる第１入力部分データの最大のビット数は５であるため、ここではビットＨ５、ビットＨ４、ビットＨ３、ビットＨ２、ビットＨ１の５ビットが第１入力部分データとなり、残余のビットＨ０は第２入力部分データとなる。そして、記憶領域１１１に書き込まれているビットＧ０の直後のアドレスから、ビットＨ５、ビットＨ４、ビットＨ３、ビットＨ２、ビットＨ１の順に書き込まれる。また、ビットＨ０が、最終アドレスに書き込まれる。
【００８６】
次に、３ビットの入力データＩが、記憶領域１１１に書き込まれる。上記式より求められる第１入力部分データの最大のビット数は４であるため、ここでは３ビット全てが第１入力部分データとなる。そして、記憶領域１１１に書き込まれているビットＨ１の直後のアドレスから、ビットＩ２、ビットＩ１、ビットＩ０の順に書き込まれる。
【００８７】
最後に、３ビットの入力データＪが、記憶領域１１１に書き込まれる。上記式より求められる第１入力部分データの最大のビット数は５であるため、ここでは３ビット全てが第１入力部分データとなる。そして、記憶領域１１１に書き込まれているビットＩ０の直後のアドレスから、ビットＪ２、ビットＪ１、ビットＪ０の順に書き込まれる。
【００８８】
以上の動作例１に示すように、データ圧縮装置１は、入力データＡ〜Ｊを成すビットの総数が、記憶領域１１１が有するアドレスの総数よりも少なくなる限り、記憶領域１１１に書き込まれた第２入力部分データを成すビットを上書きしない。そのため、データ圧縮装置１は、入力データの劣化を極力防止することが可能になる。
【００８９】
＜動作例２＞
図４に示す動作例２は、前半に処理される入力データＡ〜Ｅのそれぞれを成すビットの数は多いが、後半に処理される入力データＦ〜Ｊのそれぞれを成すビットの数が極端に少なくなるために、入力データＡ〜Ｊを成すビットの総数が、記憶領域１１１が有するアドレスの総数よりも少なくなる場合における、データ圧縮装置１の動作を示すものである。具体的に例えば、入力データＡ〜Ｊが、一部（例えば上半分）は複雑であるが他の部分（例えば下半分）は簡素である画像データを構成する場合である。
【００９０】
最初に、７ビットの入力データＡが、記憶領域１１１に書き込まれる。上記式より求められる第１入力部分データの最大のビット数は４であるため、ここではビットＡ６、ビットＡ５、ビットＡ４、ビットＡ３の４ビットが第１入力部分データとなり、残余のビットＡ２、ビットＡ１、ビットＡ０は第２入力部分データとなる。そして、記憶領域１１１の先頭アドレスから、ビットＡ６、ビットＡ５、ビットＡ４、ビットＡ３の順に書き込まれ、記憶領域１１１の最終アドレスから、ビットＡ２、ビットＡ１、ビットＡ０の順に書き込まれる。
【００９１】
次に、６ビットの入力データＢが、記憶領域１１１に書き込まれる。上記式より求められる第１入力部分データの最大のビット数は４であるため、ここではビットＢ５、ビットＢ４、ビットＢ３、ビットＢ２の４ビットが第１入力部分データとなり、残余のビットＢ１、ビットＢ０は第２入力部分データとなる。そして、記憶領域１１１に書き込まれているビットＡ３の直後のアドレスから、ビットＢ５、ビットＢ４、ビットＢ３、ビットＢ２の順に書き込まれ、記憶領域１１１に書き込まれているビットＡ０の直前のアドレスから、ビットＢ１、ビットＢ０の順に書き込まれる。
【００９２】
次に、６ビットの入力データＣが、記憶領域１１１に書き込まれる。上記式より求められる第１入力部分データの最大のビット数は４であるため、ここではビットＣ５、ビットＣ４、ビットＣ３、ビットＣ２の４ビットが第１入力部分データとなり、残余のビットＣ１、ビットＣ０は第２入力部分データとなる。そして、記憶領域１１１に書き込まれているビットＢ２の直後のアドレスから、ビットＣ５、ビットＣ４、ビットＣ３、ビットＣ２の順に書き込まれ、記憶領域１１１に書き込まれているビットＢ０の直前のアドレスから、ビットＣ１、ビットＣ０の順に書き込まれる。
【００９３】
次に、７ビットの入力データＤが、記憶領域１１１に書き込まれる。上記式より求められる第１入力部分データの最大のビット数は４であるため、ここではビットＤ６、ビットＤ５、ビットＤ４、ビットＤ３の４ビットが第１入力部分データとなり、残余のビットＤ２、ビットＤ１、ビットＤ０は第２入力部分データとなる。そして、記憶領域１１１に書き込まれているビットＣ２の直後のアドレスから、ビットＤ６、ビットＤ５、ビットＤ４、ビットＤ３の順に書き込まれ、記憶領域１１１に書き込まれているビットＣ０の直前のアドレスから、ビットＤ２、ビットＤ１、ビットＤ０の順に書き込まれる。
【００９４】
次に、７ビットの入力データＥが、記憶領域１１１に書き込まれる。上記式より求められる第１入力部分データの最大のビット数は４であるため、ここではビットＥ６、ビットＥ５、ビットＥ４、ビットＥ３の４ビットが第１入力部分データとなり、残余のビットＥ２、ビットＥ１、ビットＥ０は第２入力部分データとなる。そして、記憶領域１１１に書き込まれているビットＤ３の直後のアドレスから、ビットＥ６、ビットＥ５、ビットＥ４、ビットＥ３の順に書き込まれ、記憶領域１１１に書き込まれているビットＣ０の直前のアドレスから、ビットＥ２、ビットＥ１、ビットＥ０の順に書き込まれる。
【００９５】
次に、１ビットの入力データＦが、記憶領域１１１に書き込まれる。上記式より求められる第１入力部分データの最大のビット数は４であるため、ここでは１ビット全てが第１入力部分データとなる。そして、記憶領域１１１に書き込まれているビットＥ３の直後のアドレスに、ビットＦ０が書き込まれる。
【００９６】
次に、２ビットの入力データＧが、記憶領域１１１に書き込まれる。上記式より求められる第１入力部分データの最大のビット数は７であるため、ここでは２ビット全てが第１入力部分データとなる。そして、記憶領域１１１に書き込まれているビットＦ０の直後のアドレスから、ビットＧ１、ビットＧ０の順に書き込まれる。
【００９７】
次に、１ビットの入力データＨが、記憶領域１１１に書き込まれる。上記式より求められる第１入力部分データの最大のビット数は９であるため、ここでは１ビット全てが第１入力部分データとなる。そして、記憶領域１１１に書き込まれているビットＧ０の直後のアドレスに、ビットＨ０が書き込まれる。
【００９８】
次に、１ビットの入力データＩが、記憶領域１１１に書き込まれる。上記式より求められる第１入力部分データの最大のビット数は１２であるため、ここでは１ビット全てが第１入力部分データとなる。そして、記憶領域１１１に書き込まれているビットＨ０の直後のアドレスに、ビットＩ０が書き込まれる。
【００９９】
最後に、１ビットの入力データＩが、記憶領域１１１に書き込まれる。上記式より求められる第１入力部分データの最大のビット数は１５であるため、ここでは１ビット全てが第１入力部分データとなる。そして、記憶領域１１１に書き込まれているビットＩ０の直後のアドレスに、ビットＪ０が書き込まれる。
【０１００】
以上の動作例２に示すように、データ圧縮装置１は、入力データＡ〜Ｊのそれぞれを成すビットの数が極端にばらつく場合であっても、入力データＡ〜Ｊを成すビットの総数が、記憶領域１１１が有するアドレスの総数よりも少なくなる限り、記憶領域１１１に書き込まれた第２入力部分データを成すビットを上書きしない。そのため、データ圧縮装置１は、入力データの劣化を極力防止することが可能になる。
【０１０１】
＜動作例３＞
図５に示す動作例３は、入力データＡ〜Ｊを成すビットの総数が、記憶領域１１１が有するアドレスの総数よりもやや多い場合における、データ圧縮装置１の動作を示すものである。具体的に例えば、入力データＡ〜Ｊが、全体的にやや複雑な画像データを構成する場合である。
【０１０２】
最初に、３ビットの入力データＡが、記憶領域１１１に書き込まれる。上記式より求められる第１入力部分データの最大のビット数は４であるため、ここでは３ビット全てが第１入力部分データとなる。そして、記憶領域１１１の先頭アドレスから、ビットＡ２、ビットＡ１、ビットＡ０の順に書き込まれる。
【０１０３】
次に、４ビットの入力データＢが、記憶領域１１１に書き込まれる。上記式より求められる第１入力部分データの最大のビット数は５であるため、ここでは４ビット全てが第１入力部分データとなる。そして、記憶領域１１１に書き込まれているビットＡ０の直後のアドレスから、ビットＢ３、ビットＢ２、ビットＢ１、ビットＢ０の順に書き込まれる。
【０１０４】
次に、３ビットの入力データＣが、記憶領域１１１に書き込まれる。上記式より求められる第１入力部分データの最大のビット数は５であるため、ここでは３ビット全てが第１入力部分データとなる。そして、記憶領域１１１に書き込まれているビットＢ０の直後のアドレスから、ビットＣ２、ビットＣ１、ビットＣ０の順に書き込まれる。
【０１０５】
次に、６ビットの入力データＤが、記憶領域１１１に書き込まれる。上記式より求められる第１入力部分データの最大のビット数は６であるため、ここでは６ビット全てが第１入力部分データとなる。そして、記憶領域１１１に書き込まれているビットＣ０の直後のアドレスから、ビットＤ５、ビットＤ４、ビットＤ３、ビットＤ２、ビットＤ１、ビットＤ０の順に書き込まれる。
【０１０６】
次に、６ビットの入力データＥが、記憶領域１１１に書き込まれる。上記式より求められる第１入力部分データの最大のビット数は４であるため、ビットＥ５、ビットＥ４、ビットＥ３、ビットＥ２の４ビットが第１入力部分データとなり、残余のビットＥ１、ビットＥ０は第２入力部分データとなる。そして、記憶領域１１１に書き込まれているビットＤ０の直後のアドレスから、ビットＥ５、ビットＥ４、ビットＥ３、ビットＥ２の順に書き込まれ、記憶領域１１１の最終アドレスから、ビットＥ１、ビットＥ０の順に書き込まれる。
【０１０７】
次に、４ビットの入力データＦが、記憶領域１１１に書き込まれる。上記式より求められる第１入力部分データの最大のビット数は４であるため、ここでは４ビット全てが第１入力部分データとなる。そして、記憶領域１１１に書き込まれているビットＥ２の直後のアドレスから、ビットＦ３、ビットＦ２、ビットＦ１、ビットＦ０の順に書き込まれる。
【０１０８】
次に、４ビットの入力データＧが、記憶領域１１１に書き込まれる。上記式より求められる第１入力部分データの最大のビット数は４であるため、ここでは４ビット全てが第１入力部分データとなる。そして、記憶領域１１１に書き込まれているビットＦ０の直後のアドレスから、ビットＧ３、ビットＧ２、ビットＧ１、ビットＧ０の順に書き込まれる。
【０１０９】
次に、７ビットの入力データＨが、記憶領域１１１に書き込まれる。上記式より求められる第１入力部分データの最大のビット数は４であるため、ここではビットＨ６、ビットＨ５、ビットＨ４、ビットＨ３の４ビットが第１入力部分データとなり、残余のビットＨ２、ビットＨ１、ビットＨ０は第２入力部分データとなる。そして、記憶領域１１１に書き込まれているビットＧ０の直後のアドレスから、ビットＨ６、ビットＨ５、ビットＨ４、ビットＨ３の順に書き込まれ、記憶領域１１１に書き込まれているビットＥ０の直前のアドレスから、ビットＨ２、ビットＨ１、ビットＨ０の順に書き込まれる。
【０１１０】
次に、４ビットの入力データＩが、記憶領域１１１に書き込まれる。上記式より求められる第１入力部分データの最大のビット数は４であるため、ここでは４ビット全てが第１入力部分データとなる。そして、記憶領域１１１に書き込まれているビットＨ３の直後のアドレスから、ビットＩ３、ビットＩ２、ビットＩ１、ビットＩ０の順に書き込まれる。ただし、このとき、第２入力部分データを成すビットとして記憶領域１１１に書き込まれていたビットＨ０のアドレスに、ビットＩ０が書き込まれるため、ビットＨ０は上書きされて欠落する。
【０１１１】
最後に、３ビットの入力データＪが、記憶領域１１１に書き込まれる。上記式より求められる第１入力部分データの最大のビット数は４であるため、ここでは３ビット全てが第１入力部分データとなる。そして、記憶領域１１１に書き込まれているビットＩ０の直後のアドレスから、ビットＪ２、ビットＪ１、ビットＪ０の順に書き込まれる。ただし、このとき、第２入力部分データを成すビットとして記憶領域１１１に書き込まれていたビットＨ１、ビットＨ２、ビットＥ０のアドレスに、ビットＪ２、ビットＪ１、ビットＪ０が書き込まれるため、ビットＨ１、ビットＨ２、ビットＥ０は上書きされて欠落する。
【０１１２】
以上の動作例３に示すように、データ圧縮装置１は、入力データＡ〜Ｊを成すビットの総数が、記憶領域１１１が有するアドレスの総数を超えた分だけ、第２入力部分データを欠落させる。そのため、データ圧縮装置１は、入力データの圧縮を必要最小限に留め、入力データの劣化を抑制することが可能になる。
【０１１３】
＜動作例４＞
図６に示す動作例４は、入力データＡ〜Ｊを成すビットの総数が、記憶領域１１１が有するアドレスの総数よりも多い場合における、データ圧縮装置１の動作を示すものである。具体的に例えば、入力データＡ〜Ｊが、全体的に複雑な画像データを構成する場合である。
【０１１４】
最初に、７ビットの入力データＡが、記憶領域１１１に書き込まれる。上記式より求められる第１入力部分データの最大のビット数は４であるため、ここではビットＡ６、ビットＡ５、ビットＡ４、ビットＡ３の４ビットが第１入力部分データとなり、残余のビットＡ２、ビットＡ１、ビットＡ０は第２入力部分データとなる。そして、記憶領域１１１の先頭アドレスから、ビットＡ６、ビットＡ５、ビットＡ４、ビットＡ３の順に書き込まれ、記憶領域１１１の最終アドレスから、ビットＡ２、ビットＡ１、ビットＡ０の順に書き込まれる。
【０１１５】
次に、７ビットの入力データＢが、記憶領域１１１に書き込まれる。上記式より求められる第１入力部分データの最大のビット数は４であるため、ここではビットＢ６、ビットＢ５、ビットＢ４、ビットＢ３の４ビットが第１入力部分データとなり、残余のビットＢ２、ビットＢ１、ビットＢ０は第２入力部分データとなる。そして、記憶領域１１１に書き込まれているビットＡ３の直後のアドレスから、ビットＢ６、ビットＢ５、ビットＢ４、ビットＢ３の順に書き込まれ、記憶領域１１１に書き込まれているビットＡ０の直前のアドレスから、ビットＢ２、ビットＢ１、ビットＢ０の順に書き込まれる。
【０１１６】
次に、７ビットの入力データＣが、記憶領域１１１に書き込まれる。上記式より求められる第１入力部分データの最大のビット数は４であるため、ここではビットＣ６、ビットＣ５、ビットＣ４、ビットＣ３の４ビットが第１入力部分データとなり、残余のビットＣ２、ビットＣ１、ビットＣ０は第２入力部分データとなる。そして、記憶領域１１１に書き込まれているビットＢ３の直後のアドレスから、ビットＣ６、ビットＣ５、ビットＣ４、ビットＣ３の順に書き込まれ、記憶領域１１１に書き込まれているビットＢ０の直前のアドレスから、ビットＣ２、ビットＣ１、ビットＣ０の順に書き込まれる。
【０１１７】
次に、７ビットの入力データＤが、記憶領域１１１に書き込まれる。上記式より求められる第１入力部分データの最大のビット数は４であるため、ここではビットＤ６、ビットＤ５、ビットＤ４、ビットＤ３の４ビットが第１入力部分データとなり、残余のビットＤ２、ビットＤ１、ビットＤ０は第２入力部分データとなる。そして、記憶領域１１１に書き込まれているビットＣ３の直後のアドレスから、ビットＤ６、ビットＤ５、ビットＤ４、ビットＤ３の順に書き込まれ、記憶領域１１１に書き込まれているビットＣ０の直前のアドレスから、ビットＤ２、ビットＤ１、ビットＤ０の順に書き込まれる。
【０１１８】
次に、７ビットの入力データＥが、記憶領域１１１に書き込まれる。上記式より求められる第１入力部分データの最大のビット数は４であるため、ここではビットＥ６、ビットＥ５、ビットＥ４、ビットＥ３の４ビットが第１入力部分データとなり、残余のビットＥ２、ビットＥ１、ビットＥ０は第２入力部分データとなる。そして、記憶領域１１１に書き込まれているビットＤ３の直後のアドレスから、ビットＥ６、ビットＥ５、ビットＥ４、ビットＥ３の順に書き込まれ、記憶領域１１１に書き込まれているビットＤ０の直前のアドレスから、ビットＥ２、ビットＥ１、ビットＥ０の順に書き込まれる。
【０１１９】
次に、７ビットの入力データＦが、記憶領域１１１に書き込まれる。上記式より求められる第１入力部分データの最大のビット数は４であるため、ここではビットＦ６、ビットＦ５、ビットＦ４、ビットＦ３の４ビットが第１入力部分データとなり、残余のビットＦ２、ビットＦ１、ビットＦ０は第２入力部分データとなる。このとき、第１入力部分データを成すビットＦ６、ビットＦ５、ビットＦ４、ビットＦ３については、記憶領域１１１に書き込まれているビットＥ３の直後のアドレスから、ビットＦ６、ビットＦ５、ビットＦ４、ビットＦ３の順に書き込まれる。一方、第２入力部分データを成すビットＦ２、ビットＦ１、ビットＦ０については、記憶領域１１１のビットＥ０が書き込まれているアドレスの直前の１つのアドレスしか空いていない（それよりも前の２つのアドレスには、現に第１入力部分データを成すビットＦ４、ビットＦ３が書き込まれようとしている）ため、この１つの空いているアドレスにビットＦ２が書き込まれるのみで、他のビットＦ１、ビットＦ０は記憶領域１１１に書き込まれず欠落する。
【０１２０】
次に、７ビットの入力データＧが、記憶領域１１１に書き込まれる。上記式より求められる第１入力部分データの最大のビット数は４であるため、ここではビットＧ６、ビットＧ５、ビットＧ４、ビットＧ３の４ビットが第１入力部分データとなり、残余のビットＧ２、ビットＧ１、ビットＧ０は第２入力部分データとなる。このとき、第１入力部分データを成すビットＧ６、ビットＧ５、ビットＧ４、ビットＧ３については、記憶領域１１１に書き込まれているビットＦ３の直後のアドレスから、ビットＧ６、ビットＧ５、ビットＧ４、ビットＧ３の順に書き込まれる。ただし、このとき、第２入力部分データを成すビットとして記憶領域１１１に書き込まれていたビットＦ２、ビットＥ０、ビットＥ１、ビットＥ２のアドレスに、ビットＧ６、ビットＧ５、ビットＧ４、ビットＧ３が書き込まれるため、ビットＦ２、ビットＥ０、ビットＥ１、ビットＥ２は上書きされて欠落する。さらに、第２入力部分データを成すビットＧ２、ビットＧ１、ビットＧ０については、もはや記憶領域１１１に空いているアドレスが存在しないため、ビットＧ２、ビットＧ１、ビットＧ０は記憶領域１１１に書き込まれず欠落する。
【０１２１】
次に、７ビットの入力データＨが、記憶領域１１１に書き込まれる。上記式より求められる第１入力部分データの最大のビット数は４であるため、ここではビットＨ６、ビットＨ５、ビットＨ４、ビットＨ３の４ビットが第１入力部分データとなり、残余のビットＨ２、ビットＨ１、ビットＨ０は第２入力部分データとなる。このとき、第１入力部分データを成すビットＨ６、ビットＨ５、ビットＨ４、ビットＨ３については、記憶領域１１１に書き込まれているビットＧ３の直後のアドレスから、ビットＨ６、ビットＨ５、ビットＨ４、ビットＨ３の順に書き込まれる。ただし、このとき、第２入力部分データを成すビットとして記憶領域１１１に書き込まれていたビットＤ０、ビットＤ１、ビットＤ２、ビットＣ０のアドレスに、ビットＨ６、ビットＨ５、ビットＨ４、ビットＨ３が書き込まれるため、ビットＤ０、ビットＤ１、ビットＤ２、ビットＣ０は上書きされて欠落する。さらに、第２入力部分データを成すビットＨ２、ビットＨ１、ビットＨ０については、もはや記憶領域１１１に空いているアドレスが存在しないため、ビットＨ２、ビットＨ１、ビットＨ０は記憶領域１１１に書き込まれず欠落する。
【０１２２】
次に、７ビットの入力データＩが、記憶領域１１１に書き込まれる。上記式より求められる第１入力部分データの最大のビット数は４であるため、ここではビットＩ６、ビットＩ５、ビットＩ４、ビットＩ３の４ビットが第１入力部分データとなり、残余のビットＩ２、ビットＩ１、ビットＩ０は第２入力部分データとなる。このとき、第１入力部分データを成すビットＩ６、ビットＩ５、ビットＩ４、ビットＩ３については、記憶領域１１１に書き込まれているビットＨ３の直後のアドレスから、ビットＩ６、ビットＩ５、ビットＩ４、ビットＩ３の順に書き込まれる。ただし、このとき、第２入力部分データを成すビットとして記憶領域１１１に書き込まれていたビットＣ１、ビットＣ２、ビットＢ０、ビットＢ１のアドレスに、ビットＩ６、ビットＩ５、ビットＩ４、ビットＩ３が書き込まれるため、ビットＣ１、ビットＣ２、ビットＢ０、ビットＢ１は上書きされて欠落する。さらに、第２入力部分データを成すビットＩ２、ビットＩ１、ビットＩ０については、もはや記憶領域１１１に空いているアドレスが存在しないため、ビットＩ２、ビットＩ１、ビットＩ０は記憶領域１１１に書き込まれず欠落する。
【０１２３】
最後に、７ビットの入力データＪが、記憶領域１１１に書き込まれる。上記式より求められる第１入力部分データの最大のビット数は４であるため、ここではビットＪ６、ビットＪ５、ビットＪ４、ビットＪ３の４ビットが第１入力部分データとなり、残余のビットＪ２、ビットＪ１、ビットＪ０は第２入力部分データとなる。このとき、第１入力部分データを成すビットＪ６、ビットＪ５、ビットＪ４、ビットＪ３については、記憶領域１１１に書き込まれているビットＩ３の直後のアドレスから、ビットＪ６、ビットＪ５、ビットＪ４、ビットＪ３の順に書き込まれる。ただし、このとき、第２入力部分データを成すビットとして記憶領域１１１に書き込まれていたビットＢ２、ビットＡ０、ビットＡ１、ビットＡ２のアドレスに、ビットＪ６、ビットＪ５、ビットＪ４、ビットＪ３が書き込まれるため、ビットＢ２、ビットＡ０、ビットＡ１、ビットＡ２は上書きされて欠落する。さらに、第２入力部分データを成すビットＪ２、ビットＪ１、ビットＪ０については、もはや記憶領域１１１に空いているアドレスが存在しないため、ビットＪ２、ビットＪ１、ビットＪ０は記憶領域１１１に書き込まれず欠落する。
【０１２４】
以上の動作例４に示すように、データ圧縮装置１は、入力データＡ〜Ｊを成すビットの総数が、記憶領域１１１が有するアドレスの総数を大幅に上回る場合であっても、入力データＡ〜Ｊを成すビットの総数が、記憶領域１１１が有するアドレスの総数を超えた分だけ、第２入力部分データを欠落させる。そのため、データ圧縮装置１は、入力データの圧縮を必要最小限に留め、入力データの劣化を抑制することが可能になる。さらに、データ圧縮装置１は、少なくとも第１入力部分データを成すビットについては、欠落させることなく確実に記憶領域１１１に書き込むことが可能になる。
【０１２５】
＜別動作例＞
次に、図１に示したデータ圧縮装置の具体的な動作例であって、上述した動作例１〜４とは異なる別動作例について、図７を参照して説明する。図７は、本発明の実施形態に係るデータ圧縮装置の具体的な動作例を示す図であり、図２に示した動作例を具体化したものである。
【０１２６】
また、以下において説明する別動作例では、入力データ分割部１０が、第１入力部分データを成すビットの数を、記憶領域１１１のアドレスの総数を入力データの総数ｋで除算して得られる値以下の数にするものとする。図７に示す例では、入力データＡ〜Jの総数ｋが１０、記憶領域１１１が有するアドレスの総数が４０である。そのため、入力データ分割部１０は、第１入力部分データを成すビットの数を４以下とする。なお、図７に示す破線は、入力データの上位４ビットを示しており、第１入力部分データを成すビットの最大数を示したものである。
【０１２７】
このように構成すると、第１入力部分データを成すビットの全てを、記憶領域１１１に書き込むことが可能になる。そのため、例えば序盤で生成される第１入力部分データを成すビット数が多くなりすぎて、終盤に生成される第１入力部分データを成すビットを記憶領域１１１に書き込むことができなくなることを、防止することが可能になる。さらに、第１入力部分データ及び第２入力部分データを、簡易的に生成することが可能になる。
【０１２８】
また、動作例１〜４について示した図３〜６と同様に、別動作例について示す図７でも、入力データＡ〜Jを成すビットの位置を添字で表現し、添字の０が最も下位のビットを示し、添字が大きいビットほど上位のビットを示すこととする。
【０１２９】
図７に示す別動作例は、入力データＡ〜Ｊを成すビットの総数が、記憶領域１１１が有するアドレスの総数よりもやや多い場合における、データ圧縮装置１の動作を示すものである。具体的に例えば、入力データＡ〜Ｊが、全体的にやや複雑な画像データを構成する場合である。
【０１３０】
最初に、３ビットの入力データＡが、記憶領域１１１に書き込まれる。第１入力部分データの最大のビット数は４であるため、ここでは３ビット全てが第１入力部分データとなる。そして、記憶領域１１１の先頭アドレスから、ビットＡ２、ビットＡ１、ビットＡ０の順に書き込まれる。
【０１３１】
次に、６ビットの入力データＢが、記憶領域１１１に書き込まれる。第１入力部分データの最大のビット数は４であるため、ここではビットＢ５、ビットＢ４、ビットＢ３、ビットＢ２の４ビットが第１入力部分データとなり、残余のビットＢ１、ビットＢ０は第２入力部分データとなる。そして、記憶領域１１１に書き込まれているビットＡ０の直後のアドレスから、ビットＢ５、ビットＢ４、ビットＢ３、ビットＢ２の順に書き込まれ、記憶領域１１１の最終アドレスから、ビットＢ１、ビットＢ０の順に書き込まれる。
【０１３２】
次に、３ビットの入力データＣが、記憶領域１１１に書き込まれる。第１入力部分データの最大のビット数は４であるため、ここでは３ビット全てが第１入力部分データとなる。そして、記憶領域１１１に書き込まれているビットＢ２の直後のアドレスから、ビットＣ２、ビットＣ１、ビットＣ０の順に書き込まれる。
【０１３３】
次に、６ビットの入力データＤが、記憶領域１１１に書き込まれる。第１入力部分データの最大のビット数は４であるため、ここではビットＤ５、ビットＤ４、ビットＤ３、ビットＤ２の４ビットが第１入力部分データとなり、残余のビットＤ１、ビットＤ０は第２入力部分データとなる。そして、記憶領域１１１に書き込まれているビットＢ２の直後のアドレスから、ビットＤ５、ビットＤ４、ビットＤ３、ビットＤ２の順に書き込まれ、記憶領域１１１に書き込まれているビットＢ０の直前のアドレスから、ビットＤ１、ビットＤ０の順に書き込まれる。
【０１３４】
次に、６ビットの入力データＥが、記憶領域１１１に書き込まれる。第１入力部分データの最大のビット数は４であるため、ここではビットＥ５、ビットＥ４、ビットＥ３、ビットＥ２の４ビットが第１入力部分データとなり、残余のビットＥ１、ビットＥ０は第２入力部分データとなる。そして、記憶領域１１１に書き込まれているビットＤ２の直後のアドレスから、ビットＥ５、ビットＥ４、ビットＥ３、ビットＥ２の順に書き込まれ、記憶領域１１１に書き込まれているビットＤ０の直前のアドレスから、ビットＥ１、ビットＥ０の順に書き込まれる。
【０１３５】
次に、３ビットの入力データＦが、記憶領域１１１に書き込まれる。第１入力部分データの最大のビット数は４であるため、ここでは３ビット全てが第１入力部分データとなる。そして、記憶領域１１１に書き込まれているビットＥ２の直後のアドレスから、ビットＦ２、ビットＦ１、ビットＦ０の順に書き込まれる。
【０１３６】
次に、４ビットの入力データＧが、記憶領域１１１に書き込まれる。第１入力部分データの最大のビット数は４であるため、ここでは４ビット全てが第１入力部分データとなる。そして、記憶領域１１１に書き込まれているビットＦ０の直後のアドレスから、ビットＧ３、ビットＧ２、ビットＧ１、ビットＧ０の順に書き込まれる。
【０１３７】
次に、７ビットの入力データＨが、記憶領域１１１に書き込まれる。第１入力部分データの最大のビット数は４であるため、ここではビットＨ６、ビットＨ５、ビットＨ４、ビットＨ３の４ビットが第１入力部分データとなり、残余のビットＨ２、ビットＨ１、ビットＨ０は第２入力部分データとなる。そして、記憶領域１１１に書き込まれているビットＧ０の直後のアドレスから、ビットＨ６、ビットＨ５、ビットＨ４、ビットＨ３の順に書き込まれ、記憶領域１１１に書き込まれているビットＥ０の直前のアドレスから、ビットＨ２、ビットＨ１、ビットＨ０の順に書き込まれる。
【０１３８】
次に、４ビットの入力データＩが、記憶領域１１１に書き込まれる。第１入力部分データの最大のビット数は４であるため、ここでは４ビット全てが第１入力部分データとなる。そして、記憶領域１１１に書き込まれているビットＨ３の直後のアドレスから、ビットＩ３、ビットＩ２、ビットＩ１、ビットＩ０の順に書き込まれる。ただし、このとき、第２入力部分データを成すビットとして記憶領域１１１に書き込まれていたビットＨ０、ビットＨ１のアドレスに、ビットＩ１、ビットＩ０が書き込まれるため、ビットＨ０、ビットＨ１は上書きされて欠落する。
【０１３９】
最後に、３ビットの入力データＪが、記憶領域１１１に書き込まれる。第１入力部分データの最大のビット数は４であるため、ここでは３ビット全てが第１入力部分データとなる。そして、記憶領域１１１に書き込まれているビットＩ０の直後のアドレスから、ビットＪ２、ビットＪ１、ビットＪ０の順に書き込まれる。ただし、このとき、第２入力部分データを成すビットとして記憶領域１１１に書き込まれていたビットＨ２、ビットＥ０、ビットＥ１のアドレスに、ビットＪ２、ビットＪ１、ビットＪ０が書き込まれるため、ビットＨ２、ビットＥ０、ビットＥ１は上書きされて欠落する。
【０１４０】
以上に示す別動作例でも、データ圧縮装置１は、入力データＡ〜Ｊを成すビットの総数が、記憶領域１１１が有するアドレスの総数を超えた分だけ、第２入力部分データを欠落させる。そのため、データ圧縮装置１は、入力データの圧縮を必要最小限に留め、入力データの劣化を抑制することが可能になる。
【０１４１】
＜＜変形等＞＞
［１］  上述のデータ圧縮装置１において、入力データ分割部１０に処理される入力データの順番を、入れ替え可能としてもよい。このようなデータ圧縮装置について、図８を参照して説明する。図８は、本発明の実施形態に係るデータ圧縮装置の概略構造の別例を示すブロック図であり、データ圧縮装置１について示した図１に対応するものである。なお、図８に示すデータ圧縮装置２において、図１に示すデータ圧縮装置１と同様となる部分については、同じ符号を付すとともに詳細な説明を省略する。
【０１４２】
図８に示すデータ圧縮装置２は、入力データ分割部１０と、記憶部１１と、第１アドレス指定部１２と、第２アドレス指定部１３と、調停部１４と、出力データ結合部１５と、入力データ順番入替部２０と、出力データ順番入替部２１と、を備える。
【０１４３】
入力データ順番入替部２０は、入力データ分割部１０に処理される入力データの順番を、所定の順番に入れ替える。例えば、入力データ順番入替部２１は、重要な入力データほど先に入力データ分割部１０に処理されるように、入力データの順番を入れ替える。
【０１４４】
出力データ順番入替部２１は、出力データ結合部１５から出力される出力データを、所定の順番に入れ替えた上で、データ圧縮装置２から出力させる。例えば、出力データ順番入替部２１は、データ圧縮装置２が出力する出力データの順番が、入力データ順番入替部２０が順番を入れ替える前の入力データの順番に対応するように、出力データ結合部１５から出力される出力データの順番を入れ替える。
【０１４５】
動作例１〜４や別動作例（図３〜７参照）に示したように、入力データ分割部１０で先に処理される入力データを成すビット（特に、第２入力部分データを成すビット）ほど、欠落しにくくなる。したがって、入力データ順番入替部２１によって、重要な入力データほど入力データ分割部１０で先に処理されるようにすることで、重要な入力データの劣化を効果的に抑制することが可能になる。
【０１４６】
［２］  上述のデータ圧縮装置１において、第１入力部分データ及び第２入力部分データを記憶部１１に書き込む前に、第１入力部分データ及び第２入力部分データを一時的に保持可能としてもよい。このようなデータ圧縮装置について、図９を参照して説明する。図９は、本発明の実施形態に係るデータ圧縮装置の概略構造の別例を示すブロック図であり、データ圧縮装置１について示した図１に対応するものである。なお、図９に示すデータ圧縮装置２において、図１に示すデータ圧縮装置１と同様となる部分については、同じ符号を付すとともに詳細な説明を省略する。
【０１４７】
図９に示すデータ圧縮装置３は、入力データ分割部１０と、記憶部１１と、第１アドレス指定部１２と、第２アドレス指定部１３と、調停部１４と、出力データ結合部１５と、第１バッファ３０と、第２バッファ３１と、を備える。
【０１４８】
第１バッファ３０は、入力データ分割部１０が生成した第１入力部分データが、記憶部１１に書き込まれる前に一時的に蓄積し、所定量以上の第１入力部分データを蓄積すると、記憶部１１に転送する。同様に、第２バッファ３１は、入力データ分割部１０が生成した第２入力部分データが、記憶部１１に書き込まれる前に一時的に蓄積し、所定量以上の第２入力部分データを蓄積すると、記憶部１１に転送する。
【０１４９】
このような第１バッファ３０及び第２バッファ３１を備えることで、第１入力部分データ及び第２入力部分データを、記憶部１１に安定して書き込むことが可能になる。
【０１５０】
［３］  ［１］及び［２］に示した本発明の実施形態に係るデータ圧縮装置の概略構造の別例は、組み合わせて実施することができる。具体的に例えば、図９に示すデータ圧縮装置３に、図８に示した入力データ順番入替部２０及び出力データ順番入替部２１（図８参照）を設けてもよい。
【０１５１】
［４］  第１アドレス指定部１２及び第２アドレス指定部１３は、第１入力部分データ及び第２入力部分データを記憶領域１１１に書き込む、または、記憶領域１１１から第１出力部分データ及び第２出力部分データを読み出す際に、どのように記憶領域１１１のアドレスを指定してもよい。具体的に例えば、書き込みまたは読み出しのアドレスをビット単位で指定してもよいし、書き込みまたは読み出しの起点となるアドレスと終点となるアドレスとの双方を指定してもよいし、書き込みまたは読み出しの起点となるアドレスと書き込むまたは読み出すべきビットの数との双方を指定してもよい。
【産業上の利用可能性】
【０１５２】
本発明に係るデータ圧縮装置は、可変長符号化されたデータを必要に応じて圧縮するデータ圧縮装置に、好適に利用され得る。また、本発明に係るデータ圧縮装置は、画像データのフレームメモリのような、入力データを一時的に保持するための記憶装置としても利用され得る。
【符号の説明】
【０１５３】
１〜３  ：  データ圧縮装置
１０    ：  入力データ分割部
１１    ：  記憶部
１１１  ：  記憶領域
１２    ：  第１アドレス指定部
１３    ：  第２アドレス指定部
１４    ：  調停部
１５    ：  出力データ結合部
２０    ：  入力データ順番入替部
２１    ：  出力データ順番入替部
３０    ：  第１バッファ
３１    ：  第２バッファ
【図１】
2013172357.tif 000003
【図２】
2013172357.tif 000004
【図３】
2013172357.tif 000005
【図４】
2013172357.tif 000006
【図５】
2013172357.tif 000007
【図６】
2013172357.tif 000008
【図７】
2013172357.tif 000009
【図８】
2013172357.tif 000010
【図９】
2013172357.tif 000011