JPH01501434A - 情報搬送シンボルの可逆圧縮方法および装置 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるため要約のデータは記録されません。

Description

【発明の詳細な説明】 情報搬送シンボルの可逆圧縮方法および装置技術分野 本発明は、Ｑ個の不連続値を取り得る情報搬送シンボルの列ｘ　（ｋ）の可逆圧 縮方法に関する。ｋは指標であって整数値を取る。この方法においては情報搬送 シンボルの列Ｘ　（ｋ）が、剰余ｗ　（ｋ）を形成するような手段において処理 され、また剰余ｗ　（ｋ）が符号化されて、陳列ｘ　（ｋ）と同じ情報を含む情 報搬送シンボルの圧縮列ｘ　（ｋ）・を形成するようになっている。

本発明はまた上記方法を実行するＶｉｔ置に関する。

ディジタル情報が取り扱われる全ての実際面では、多くの場合２進数字である文 字をできるだけ少なく用いて情報を表わすことが関心事となっている。例えば、 異なるメモリに情報を記憶するに際しては、所定のメモリ空間にできるだけ多く の情報を記憶することが望まれる。

また他の例として、ディジタル符号化音声情報や映像情報などの伝送に際し、で きるだけ少ないピットを用いてできるだけ多くの情報を伝送して転送レート要件 を緩和することが望まれる。

背景技術 公知のディジタル情報圧縮方法の１つに「予測符号化」と呼ばれる圧縮技術を用 いるものがあり、例えば、ビー・エリアスの予測符号化第工部、第■部、アイ・ アール・イー・トランザクション情報理論、第■−１巻、１９５５年３月、１６ 頁〜３３頁やシー・シー・カットラの米国特許第２６０５３６１号、１９５２年 に記載されている。この技術は、 （１）　ディジタル信号の陳列と同一かもしくは殆んど同一の情報を含む剰余の 列を作ること、 （り　例えば２進シンボルを用いて剰余列を符号化すること の２つの動作を含んでいる。

発明の開示 動作１の剰余列は、列内の先行ディジタル信号を用いて列内の後行ディジタル信 号の値を予測することによって形成される。実際のディジタル信号と予測信号と の門の差が剰余を構成する。剰余列を作成するのはディジタル信号の陳列での冗 長度を低減するためである。第２の動作で剰余が符号化されるが、この符号化は 可変長の符号器を用いて適宜性なわれるので、頻繁に発生する剰余は発生頻度の 少ない剰余よりも符号化する符号語が短かい。

本発明の目的は、可逆データ圧縮を改善し得る方法およびＩＩを提供するにある 。

この目的は、符号化に先立ち剰余において行なわれるモジュールＱで特徴づけら れる導入部記載の方法によって達成される。

また上記目的は、符号器の前に設けられモジュールＱ演算を行なう手段によって 特徴づけられる上記方法の実行装置によっても達成される。

このような方法および装置によれば、単なる可逆予測符号化において可能な圧縮 度よりも高い圧縮度を達成できる。すなわち、得られる圧縮度は、モジュールＱ 演算実行後のディジタル信号の列ｗ　（ｋ）のエントロピによって決定される。

１次エントロピは、ｋの順次値に対してｗ　（ｋ）を個別に符１号化する符号器 に相当し、Ｈ＾−一Σ　Ｐ＾（ｊ）ｌｏＯＰｇ（ｊ）Ｗ　Ｗ ｊ−。

に等しい。ここでＰｇ（」）はｗ　（ｋ）−ｊの相対頻度であってｊ−０，１、 ・・・・・・、Ｑ−１である。エントロピが低くなるのでＱ　（ｋ　）に対する 圧縮度はｗ　（ｋ）に対する圧縮度よりも高くなる。ｗ　（ｋ）の数個の値がｗ 　（ｋ）では同一値となるためこのような結果となるのである。

例えば、次のディジタル信号すなわちｘ（ｋ）が先のディジタル信号すなわちｘ （ｋ−１）と同一値を持つように予測され、このときの剰余がｗ　（ｋ）　−ｘ 　（ｋ）　−Ｘ（ｋ−１）であり、かつ、Ｑ−２５６である場合を仮定すると、 剰余ｗ（ｋ）は区間（−２５５，２５５）内で整数の値を持つ。２５６を法とす る縮少は、ｗ（ｋ）が区間（Ｏ１２５５）に制限されることを意味するから、例 えり、ｆｗ（ｋ）−−１７、Ｗ　（ｋ）＝２３９は共にｗ　（ｋ）−２３９を与 える。

もしＷｌ　（ｋ）＝Ｊ１　、Ｗ２　（ｋ）−Ｊ２とすると、これらは共にｗ　（ ｋ）−ｊとなりｗ　（ｋ）に対するエントロピは次のように２項を含むことにな る。

−［Ｐｗ（ｊｌ）１ｏｇＰｗ（ｊｌ）＋８ｗ（ｊ２）１ｏｇＰＷ（ｊ２）］これ はＷに対するエントロピＨ−ｇ（ｋ）における項−ＰＱ　（ｊ　＞　ｌｏｇ　Ｐ Ｑ　＜ｊ＞に相当するから Ｐ△（ｊ）−ＰＷ（ｊｌ）＋ＰＷ（ｊ２　）となる。

ａ、ｂ＞Ｑに対し、 （ａ＋ｂ）Ｉｏａ　（ａ＋ｂ）＞ａｔｏｇ　（ａ）＋ｂｌｏｏ　（ｂ）であるか ら、ＨＱ≦ＨＷが成り立ち、Ｑを法とする演算を施こしたディジタル信号列に対 する圧縮度は、このような演算を施さないディジタル信号列に対する圧縮度より も大きくなる。

高圧縮度の利点以外にも、本発明の方法および装置ではｗ　（ｋ）はｗ　（ｋ＞ よりもシンボル文字が少ないので、符号語の数が少なくなる分だけ符合器が単純 化されるという利点が得られる。さらに、本発明によれば予測手段の実現が簡単 になる。

図面の簡単な説明 以下、本発明の種々の実施例を添付図面を参照して説明する。図中、第１図は本 発明による装置を示すブロック図、第２Ａ図、第２Ｂ図は、第１図中のブロック Ｒ５Ｒ−１に含まれる手段の全体構成を示すブロック図、第３Ａ図、第３Ｂ図は 、ブロックＲが横形フィルタの場合における本発明のｌｉ：ｉｉの構成を示すブ ロック図である。

発明を実施するための最良の形態 第１図は本発明の装置の全体的構成を示し、剰余を形成する手段１と、Ｑを法と する演算を行なう手段２と、符号器３とを備えている。装置のこの部分は、装置 への入力信号を形成するディジタル信号の列ｘ（ｋ）、ｋ−・・・・・・−１， ０，１，２・・・の圧縮を実行する。ディジタル信号はアナログ信号の標本であ り、これらの標本はＯとＱ−１との間でＱ個の不連続値を取る。列ｘ　（ｋ）は 手段１へ供給され、この手段１はに−・・・−１，０，１，２として剰余ｗ　（ ｋ）を形成し、手段２において剰余はＱを法として縮少されて列ｗ　（ｋ）が形 成される。この列は、例えばハフマン符号化のような公知方法を用いて列ｗ　（ ｋ）を符号化する符号器３へ供給され、陳列ｘ　（ｋ）と同じ情報を含む符号器 の列ｎ　（ｋ）が形成される。しかして符号語列ｎ　（ｋ）は圧縮列を構成し、 メモリに記憶されるか他の装置へ送られる。

圧縮列ｎ　（ｋ）から陳列ｘ　（ｋ）を再構成しようとするときは、第１図の下 側部分に示す装置を用いる。この装置は、復号器４と、剰余形成手段１が行なう 演算に対して反転演算を行なう反転手段５と、Ｑを法とする演算を行なう手段６ とを備えている。装置のこの部分では、圧縮列ｎ　（ｋ）が復号器４において復 号化されて符号器３への入力信号列ｗ　（ｋ）が再形成される。この列ｗ　（ｋ ）は、列ｙ　（ｋ）を形成する反転手段５へ供給される。列ｙ（ｋ）が供給され ると、手段６はその列についてＱを法とする演算を実行し、陳列ｘ　（ｋ）の回 復が達成される。

第１図のブロック図に示す剰余形成用の反転手段５および手段１の全体的構成を 第２Ａ図、第２Ｂ図に示す。

手段１は予測器２１を有し、この予測器の入力には圧縮されるディジタル信号の 列ｘ　（ｋ）が供給され、出力からは加算器２３への否定予ｍｍが送出される。

列ｘ　（ｋ）は乗算器２２への入力信号としても接続されていて、乗算器２２に おいて列ｘ　（ｋ）に係数ｆ。が掛は合せられる０乗算器２２からの出力は加算 器２３に接続し、加算器２３の出力から剰余ｗ　（ｋ）が送出される。

反転手段５は第２Ｂ図に示す構成を有し、この反転手段の予測器２５の入力には 当該回路からの出力信号ｙ　（ｋ）が供給され、出力からは加算器２６の入力へ の予測値が送出される。加算器２６の第２人力は復号化列ｗ（ｋ）を受け、出力 は乗算器２７へ接続する。乗算器力信号は当該回路からの出力信号ｙ　（ｋ）と 同じである。

予測器２１は値の列ｘ　（ｋ）から値 ｏ　（ｋ）−ｐ［ｘ　（ｋ−１）、ｘ　（ｋ−２）、ｘ　（ｋ−３）、・・・・ ・・］ を発生する手段である。

関数ｐ［ｘｌは直線性、非直線性、反復性のものなどいずれでもよい。発生値（ ｋ）が正または負の整数であることが唯一の条件である。予測器２５は予測器２ １と同様に機能する。予測器２１．２５は例えば全く一般的な関数ｓ　［ｘｌ　 −ｓ　［ｘ　（ｋ−１）、ｘ　（ｋ−２）、−・・・］として実現でき、これら に量子化装置を後置させることもできる。

圧縮および再構成の開始たとえばに−Ｑにおいては、ｐ　（ｋ）を計算するため にに−−１、−２、−３・・・・・・に対するｘ　（ｋ）およびＶ（ｋ）を知る 必要がある。この問題はこれらの値を零に等しくするか他の任意に定めた値の列 に等しくすることによって解決される。しかして、手段１と反転手段５とを同じ 状態から開始させることができる。

以下、手段１が横形フィルタである場合について本発明のＩＩＩの構成を第３Ａ 図、第３Ｂ図により説明する。

この場合、剰余ｗ（ｋ）は ｗ（ｋ）−−Σ　ｆ、ｘ（ｋ−ｉ） ｗＯ となる。但しｆ、は重み係数であってｉ−Ｑ、１、・・・・・・、Ｎであり、本 発明の方法では重み係数ｆ、が整数であると仮定している。この場合に使用可能 なフィルタの例はＮ−１ｆ　−１、ｆｌ−−１ Ｎ−２ｆｏ−１、ｆｌ−−２、ｆ２−１Ｎ−３ｆｏ−１、ｆ、−−３、ｆ２−３ 、ｆ３−−１であり、列ｘ　（ｋ）の第１、第２、第３の誤差を形成する。

第３Ａ図に示す例は、剰余ｗ　（ｋ）形成用手段１がＮ−３の場合どのように構 成されるかを表わしている。手段１は、圧縮用入力信号として列ｘ　（ｋ）を受 ける遅延装置１３１を備え゛、各遅延装置は単位時間だけ入力信号を遅延させる ので、遅延装置の入力にｘ　（ｋ）が現われると出力にはｘ（ｋ−１）が生じる 。さらに、乗算器３２を設け、その一方の入力で各遅延装置３１からの信号を受 け他方の入力で整数の係数ｆ、を受ける。Ｘ値はこの係数ｆ、と掛は合せられる 。乗算器の出力が加算器３３の入力に接続され、この加算器の出力に剰余ｗ　（ ｋ）が得られる。加算器３３からの出力は第１図の手段１からの出力と同じであ る。この装置の残りの部分は第１図の装置の対応部分と同一であるので詳細な説 明を省略する。

他の実施例では、Ｑを法とする演算がフィルタ内、とくに本例のようにフィルタ が直線性の場合は、Ｑを法とする乗算器として形成された乗算器３２と、Ｑを法 とする加算器として形成された加算器３３とによって実行さる。このような回路 は、Ｑが２の箒であるときとくに実現が容易となる。

再構成は、演算 −１△ Ｖ　（ｋ）　−ｆ　［ｗ　（ｋ）−Σ　ｆ、Ｖ（ｋ−ｉ）コｉ＝１ を実行する反転フィルタを用いて行なう。ここでｆｏはｆ。に対するＱを法とす る反転である。

第３Ｂ図に示す例は、上記仮定Ｎ−３の場合に反転フィルタがどのように構成さ れるかを表わしている。フィルタは加算器３５を備え、この加算器の一つの入力 には復号された列ｗ（ｋ）が供給され、この列ｗ　（ｋ）は他の入力上の各項に 加算される。加算器３５からの出力は乗算器３６に接続し、乗算器３６の第２人 力は係数ｆｏ　を受け、出力信号Ｖ　（ｋ）はフィルタの出力信号をなすと共に 遅延装置！３７への入力信号をなす。遅延装置ではｙ値が単位時間だけ遅延され るので、遅延Ｓｉ＠の入力にｙ　（ｋ）が生じるとその出力にＹ（ｋ−１＞が生 じる。遅延装置３７からの出力は乗算器３８に接続し、各乗算器３８の第２人力 は係数−ｆ　、−ｆ２、−ｆ３を受け、出力は加算器３５に接続する。Ｑを法と する演算を行なう復号器４と手段６は第１図のものと同じである。

したがって、陳列ｘ　（ｋ）はＸ（ｋ）−Ｑを法とするｙ　（ｋ）となる。

再構成によって正しい結果が得られるようにするには、ｆｏ−１が存在しなけれ ばならない。これは式％式％ ・・・、（Ｑ−１）に対して解を持たなければならないことを意味する。

もしｆｏとＱとが相互に素数であるように、すなわち、１以外の共通因数がない ように選ばれていれば解を持つこととなる。上記したフィルタはｆｏ−１を有す るから、任意のＱに対してこれらの要件を全て満たす。

第３Ａ図の場合の他の実施例では、Ｑを法とする演算がフィルタ内、とくにＱを 法とする乗算器として形成された乗算器３６．３８とＱを法、とする加算器とし て形成された加算器３５とによって実行される。

なお、本発明はハードウェアでもソフトウェアでも実現できる。

最後に、本発明をディジタル信号に適用したものとして説明したが、本発明は、 加算、減算、乗算、Ｑを法とする演算を定義しうるすべての情報搬送シンボルの 可逆圧縮をカバーするものである。

Ｆｉｇ、１ 国際調査報失

Claims (1)

1. 【特許請求の範囲】 １．整数の値を取る指標ｋに関してＱ個の不連続値を取る情報搬送シンポルの列 ｘ（ｋ）を可逆圧縮する方法であつて、情報搬送シンポル列ｘ（ｋ）を手段１で 処理して剰余ｗ（ｋ）を形成し、この剰余ｗ（ｋ）が符号化されて原則ｘ（ｋ） と同じ情報を含む情報搬送シンポルの圧縮列ｎ（ｋ）を形成する前記方法におい て、符号化に先立ちＱを法とする演算を剰余ｗ（ｋ）について行なつて、剰余に 対するエントロピを減少させ可能な圧縮度を増大させたことを特徴とする情報搬 送シンポルの可逆圧縮方法。 ２．請求の範囲第１項において、剰余ｗ（ｋ）を形成する手段１は、加算および 乗算によつて剰余ｗ（ｋ）を形成する直線性フィルタであつて、Ｑを法とする加 算として上記加算を実行し、Ｑを法とする乗算として上記乗算を実行することを 特徴とする情報搬送シンポルの可逆圧縮方法。 ３．請求の範囲第１項または第２項において、Ｑは２の器であることを特徴とす る情報搬送シンポルの可逆圧縮方法。 ４．前掲の請求の範囲のうちの１つに従つて圧縮された情報搬送シンポルの列Ｘ （ｋ）を再構成する方法であつて、再構成においては圧縮列ｎ（ｋ）を復号し複 号化列ｗ（ｋ）を反転手段（５）で処理して列ｙ（ｋ）を形成する前記方法にお いて、反転手段（５）からの列ｙ（ｋ）についてＱを法とする演算を行なつて原 列ｘ（ｋ）を得ることを特徴とする情報搬送シンポルの再構成方法。 ５．請求の範囲第４項において、列ｙ（ｋ）を形成する手段（５）は、加算およ び乗算によつて列ｙ（ｋ）を形成する直線性反転フィルタであつて、Ｑを法とす る加算として上記加算を実行し、Ｑを法とする乗算として上記乗算を実行するこ とを特徴とする情報搬送シンポルの再構成方法。 ６．請求の範囲第４項または第５項において、Ｑは２の器であることを特徴とす る情報搬送シンポルの再構成方法。 ７．整数の値を取る指標ｋに関してＱ個の不連続値を取る情報搬送シンポルの列 ｘ（ｋ）を圧縮する装置であつて、情報搬送シンポル列ｘ（ｋ）内のある開始点 を用いて剰余ｗ（ｋ）を形成する手段（１）と、剰余ｗ（ｋ）を符号化して原列 ｘ（ｋ）と同じ情報を含む情報搬送シンポルの圧縮列ｎ（ｋ）を形放する符号器 （３）とを備えた前記装置において、手段２を設けて剰余ｗ（ｋ）についてＱを 法とする演算を行ない剰余に対するエントロピを減少させ可能な圧縮度を増大さ せたことを特徴とする情報搬送シンポルの圧縮装置。 ８．請求の範囲第７項において、乗余ｗ（ｋ）を形成する手段（１）は、加算器 および乗算器を用いて乗余ｗ（ｋ）を形成する直線性フィルタであつて、上記加 算器はＱを法とする加算器であり、上記乗算器はＱを法とする垂算器であること を特徴とする情報搬送シンポルの圧縮装置。 ９．請求の範囲第７項または第８項の装置を用いて圧縮された情報搬送シンポル の列ｘ（ｋ）を再構成する装置であつて、圧縮列ｎ（ｘ）を復号して復号化列ｗ （ｋ）を形成する複号器（４）と、列ｗ（ｋ）についての反転演算によつて列ｙ （ｋ）を形成する反転手段（５）とを備えた前記装置において、反転手段（５） からの列ｙ（ｋ）についてＱを法とする演算を行なつて原列ｘ（ｋ）を得る手段 （６）を設けたことを特徴とする情報搬送シンポルの再構成装置。 １０．請求の範囲第９項において、列ｙ（ｋ）を形成する手段（５）は、加算器 および乗算器を用いて列ｙ（ｋ）を形成する直線性反転フィルタであつて、上記 加算器はＱを法とする加算器であり、上記乗算器はＱを法とする乗算器であるこ とを特徴とする情報搬送シンポルの再構成装置。