JPH0453328B2

JPH0453328B2 -

Info

Publication number: JPH0453328B2
Application number: JP28060585A
Authority: JP
Inventors: Michio Shimada
Original assignee: Nippon Electric Co Ltd
Current assignee: NEC Corp
Priority date: 1985-12-12
Filing date: 1985-12-12
Publication date: 1992-08-26
Also published as: JPS62139416A

Description

【発明の詳細な説明】〈産業上の利用分野〉本発明はデイジタルデータの伝送あるいは蓄積
の際に伝送時間や蓄積容量を節約する目的で冗長
度を除いて圧縮されたデータから、もとのデータ
を復元するデータ圧縮復号化装置に関するもので
ある。

〈従来の技術〉冗長データを圧縮する方法及び圧縮されたデー
タからもとの冗長データを復元する方法として従
来一般によく知られ利用されているものに、算術
符号を用いる方法がある。算術符号のデータ圧縮
符号化装置（データを圧縮する装置、以下では単
に符号化装置とも言う）及びデータ圧縮復号化装
置（データを復元する装置。以下では単に復号化
装置とも言う）の詳細については例えば米国のイ
ンターナツシヨナルビジネスマシンズコーポレー
シヨン（International Business Machines
Corporation）から1976年に発行された論文誌ア
イビーエムジヤーナルオブリサーチアンドベロツ
プメント（IBM Journal of Research and
Development）の第20巻３号の198〜203ページ
や1984年に発行された同誌第28巻２号135〜149ペ
ージや米国のスタンフオード大学（Stanford
University）で1976年に発行されたリチヤードク
ラークパスコ（Richard Clark Pasco）による
博士論文「ソースコーデイングアルゴリスムフオ
ーフアーストデータコンプレツシヨン（Source
coding algorithms fast data compression）」
に詳しく述べられている。これらの方法のうちデ
ータ圧縮する方法について簡潔に述べれば、情報
デイジツト列X₁，X₂…，X_Nは、その冗長度に応
じて長さの異なる符号デイジツト列W₁，W₂…，
W_Lに例えば次のようにして変更され、情報デイ
ジツト列の冗長度が取除かれる。

まずＦをあらかじめ決められた数直線上の区間
（０以上１未満とする）の小さい方の端の値（す
なわち０）とし、Ｔをその区間の幅（すなわち
１）とする。次に以下の手順A₁）〜A₅）を実行
する。なお以下ではＸＹはＸにＹの値を代入す
ることを表わすものとする。また演算はすべてｂ
進法で行なうものとする。

A₁ ｉの値を１とする。

A₂ 第ｉ番目の情報デイジツトXiを入力する。

A₃ 第ｉ番目の情報デイジツトXiの出現確率q_i
（x_i）と累積出現確率 C_i（X_i）＝ Σ^y <^xiq_i（ｙ）を求める。

A₄ ＦＦ＋C_i（X_i）・ＴＴq_i（X_i）・Ｔとし、Ｔを予め決められた有効数字Ｋ桁で打ち
切る。

A₅ ｉ＜Ｎならｉの値を１増やしてA₂へ移る。

ｉ＝Ｎなら終了。

最後にＦとＴの最終値で決定される区間に含まれ
る実数のうちから数値表現したときのデイジツト
数が少ない実数を選び、選ばれた実数の表現デイ
ジツトＯ・W₁W₂……W_Lを符号デイジツト列
W₁，W₂，……，W_Lとして定める。なお、以下
では説明の都合上次のような記法を用いるものと
する。

Ｔ＝Ａ・b^-〓Ａ＝C.t₁t₂……t_l(A) Ｆ＝（F1＋F2）・b^-〓｛F1＝f₁，₁f₁，₂……f₁、_l(F1) F2＝Ｏ・f₂、₁……f₂、(二)……f₂、_l(F2) ここでｌ(A)、ｌ（F₁）、ｌ（F₂）はそれぞれＡ、
F1、F2の表現デイジツト数を表わす。また初期
状態（すなわちＦとＯとし、Ｔを１として符号化
装置の初期化を行なつたとき）においてはt₁≠０
と設定しておくものとする。すると前述の手順
A4）は次のように表わされる。

A4.1 F2＋C_i（X_i）Ａ・１ならば F1F1＋１を実行する。

A4.2 F2frac（F2＋C_i（X_i）・Ａ）とする。ここ
でfrac（Ｘ）はＸの小数点以下の値を与える
関数である。

A4.3 Ａq_i（X_i）・Ａとする。

A4.4 もしt₁＝０ならば F1ｂ・F1＋f₂、₁ F2frac（ｂ・F2）Ａｂ・Ａ ττ＋１とする。

A4.5 もしt₁＝０ならばA4.4）へ移る、さもな
くば次へ移る。

A4.6 Ａの小数点第Ｋ＋１位以下t_k+1、t_k+2 …を打ち切る。

上記手順A1）〜A5）に従えば符号語の長さＬは
情報デイジツト列の長さＮより一般に小さくなつ
てデータ圧縮できることが前記文献に示されてい
る。一方、データを復元する方法について簡潔に
述べれば、符号デイジツト列W₁，W₂，……，
W_Lは例えば次のようにして変換され、もとの情
報デイジツト列X₁，X₂，……，X_Nが復元され
る。

まず、ＷにO.W₁W₂……W_Lを代入しＳに１を
代入する。次に以下の手順B1）〜B5）を実行す
る。なお以下ではＸＹはＸにＹの値を代入する
ことを表わすものとする。また演算はすべてｂ進
法で行なうものとする。

B1 ｉの値を１とする。

B2 c_i（Ｙ）Ｗ／Ｓを満たすＹのうちで最大の
デイジツトをX_iとする。

B3 X_iを復元された情報デイジツトとして出力
する B4 ＷＷ−C_i（X_i）・ＳＳq_i（X_i）・Ｓとし、Ｓを予め決められた有効数字Ｋ桁で打ち
切る。

B5 ｉ＜Ｎならｉの値を１増やしてB2）へ移
る。

ｉ＝Ｎなら終了。

なお以下では説明の都合上次のような記法を用い
るものとする。

Ｓ＝Ｂ・b^-〓Ｂ＝O.S₁S₂……S_l(B) Ｗ＝（W1＋W2）・b^-〓｛W1＝W₁、1W₁、₂……W₁l（W₁） W2＝O.W₂、₁W₂、₂……W₂、_(W2) ここでｌ(B)、ｌ（W1）、ｌ（W2）はそれぞれＢ、
W1、W2の表現デイジツト数を表わす。また初期
状態（すなわちＷをO.W₁W₂……W_Lとし、Ｓを
１として復号化装置の初期化を行なつたとき）に
おいてはS₁≠Ｏと設定しておくものとする。する
と前述の手順B2）は次のようになる。

B2 Ci（Ｙ）（W1＋W2）／Ｂを満たすＹのう
ちで最大のデイジツトをX_iとする。

また手順B4）は次のように表わされる。

B4.1 W2−C_i（X_i）・Ｂ＜Ｏならば W1W1−１ W2（1.0＋W2）−C_i（X_i）・Ｂを実行する。さもなくば W2W2−C_i（X_i）・Ｂを実行する。

B4.2 Ｂq_i（X_i）・Ｂとする。

B4.3 もしS₁＝Ｏならば W1ｂ・W1＋W2、₁ W2frac（ｂ・W2）Ｂｂ・Ｂ δδ＋１とする。

B4.4 もしS₁＝ＯならばB4.3）へ移る。

さもなくば次へ移る。

B4.5 Ｂの小数点第Ｋ＋１位以下S_k+1、S_k+2、
……を打ち切る。

上記手順B1）〜B5）に従えば符号デイジツト列
W₁，W₂，……，W_Lからもとの情報デイジツト
列X₁，X₂，……，X_Nが誤りなく復元できること
が前記文献に示されている。

また、上記手順A1）〜A5）及びB1）〜B5）
には、例えば次に述べられるような装置化に都合
のよい性質のあることが前記文献に示されてい
る。まず第一点は使用目的に応じた柔軟な設がで
きる点である。すなわち上記手順では情報デイジ
ツト列の長さＮを予め決められた一定値とし、一
方符号デイジツト列の長さＬを情報デイジツト列
の冗長度に依存して決まる値としたが、逆にＬを
予め決められた一定値とし、Ｎを情報デイジツト
列の冗長度に依存して決まる値とすることもでき
る。そのためには前記手順A5）及びB5）をそれ
ぞれ次のように変更すればよい。

A5′ τ＜Ｌ−Ｊならｉの値を１増やしてA2）へ
移る。τ＝Ｌ−Ｊなら終了。

B5′ δ＜Ｌ−Ｊならｉの値を１増やしてB2）へ
移る。δ＝Ｌ−Ｊなら終了。

ここでＪはq_i（・）、C_i（・）の有効桁数である。
しかし、どちらも符号化・復号化を終了する基準
が異なるだけで装置の構成は同様であるから、以
下の説明では便宜上情報デイジツト列の長さＮを
一定値とし、一方符号デイジツトの長さＬを情報
デイジツト列の冗長度に依存して決まる値として
おく。第二点は、情報デイジツト列の長さＮを十
分大きくすると圧縮の効率が良くなり、ほとんど
理論的限界に達する点である。最後に第三点は上
記手順A1）〜A5）において符号デイジツトを遂
次的に出力し得る点である。すなわち前記文献に
よれば、手順A4.1）の演算F1F1＋１において
桁上りが一旦生じると、桁上りが伝播した範囲よ
り高位のデイジツトに仕上りが再度伝播すること
はない（例えばｂ＝２でF1＝10101111のときは
桁上りはF1の上位３ビツト１０１へは決して伝
播しない）から、すべての情報デイジツトに対す
る符号化が完了しないうちに桁上りの伝播しない
高位の符号デイジツトを遂次的に出力してゆけ
る。例えばｂ＝２でF1＝10101111のときにはF1
の上位３ビツト１０１へは桁上りは決して伝播し
ないので上位３ビツト１０１は符号デイジツトと
して出力できる。

さて上記のようなデータ圧縮及びデータの復元
を実行するためのデータ圧縮符号化装置及びデー
タ圧縮復号化装置は、例えば米国のインターナシ
ヨナルビジネスマシンズコーポレーシヨンの米国
特許第4122440号などに記されているような加
算・乗算などの算桁演算回路を含む回路で実現で
きる。

もつとも、符号デイジツトを遂次的に出力でき
ると言つても、例えばF1＝0111111のときに手順
A1）においてF1F1＋１が実行されると最上位
デイジツトまで桁上りが伝播するので符号デイジ
ツトを遂次的に出力できない。すなわち桁上りの
伝播の長さが一定でないので、符号デイジツトに
１が連続して出現した場合には符号化遅延が大き
くなつてしまう。

このため、符号化遅延が小さいことを要求され
る用途で算術符号を応用するには桁上りの伝播の
制御が必要で、従来は符号ビツトにｂ−１が一定
数以上連続して表われた時には区間の幅をｂで割
ることによつて、上記手順B4.1）の演算F1F1
＋１が実行されることを防ぎ、桁上りの伝播の長
さを一定長以下に制御する方法が用いられてい
た。具体的には符号化法として、前述の手順A4）
とA5）の間に以下のような手順を加えたものが
用いられていた。

Ａイ F1の下位Ｍデイジツトがすべてｂ−１
ならば次にさもなくばＡ、ニ）へ移る。

Ａロ F1ｂ・F1＋f₂、₁ F2frac（ｂ・F2） ττ＋１ＡハＡ、イ）へ移る。

Ａニ次へ移る。

ここでＭは予め決められた値で、もし桁上りの
伝播の長さを10デイジツト以下にしたければＭ＝
10としておく。この操作はF1，F2の表現デイジ
ツトが格納されているるレジスタの内容をＭ個の
ｂ−１が連続しなくなるまで高位の方へシフトさ
せることと等価である。

一方、この符号化法に対する復号化法として
は、前述の手順Ｂ・３）とＢ・４）の間に以下の
ような手順を加えたものが用いられていた。

ＢイＦＦ＋C_i（X_i）・Ｓを実行する。

すなわちF2＋C_i（X_i）・Ｂ１ならば F1F1＋１、F2frac（F2＋C_i（X_i）・Ｂ）
をさもなければF2frac（F2＋C_i（X_i）・Ｂ
を実行する。

Ｂロ F1の下位Ｍデイジツトがすべてｂ−１
ならば次に、さもなくばＢ・ホ）へ移る。

Ｂハ F1ｂ・F1＋f₂、₁ F2frac（ｂ・F2） W1ｂ・W1＋W₂、₁ W2frac（ｂ・W₂） ττ＋１、δδ＋１を実行する。

Ｂ・ニＢ・ロ）へ移る。

Ｂ・ホ次へ移る。

ここでF1、F2は対応する符号器が用いている
ものに等しいもので、初期値も符号器と同一とし
ておく。以上のような桁上りの伝播制御を取り入
れることによつて、符号化遅延の小さなことが要
求される用途でも算術符号がデータ圧縮のために
応用されていた。

〈発明が解決しようとする問題点〉しかしながら、従来の桁上りの伝播制御方式で
はｂ−１が一定数以上連続して表われた場合に区
間の幅をちようどｂ分の１にしていた（すなわち
Ｆの表現デイジツトを高位デイジツトの方へ１デ
イジツトシフトさせていた）ので、桁上りの伝播
制御操作１回につき、平均約ｂ／（ｂ−１）デイ
ジツトの冗長デイジツトが符号デイジツトに付加
された。なぜなら、レジスタF2の上位デイジツ
トにｂがｊ個連続する確率は（ｂ−１）／b^j+1で
あり、F2の上位にｂがｊ個連続していれば、１
回の桁上りの伝播制御についてｊ＋１回のシフト
が実行されるので、桁上りの伝播制御１回に伴な
うシフト回数の平均は約_∞ Σ^j=0 （ｊ＋１）・（ｂ−
１）／b^j+1＝ｂ／（ｂ−１）回となるからであ
る。特にｂ＝２の場合には従来の桁上りの伝播制
御方式では１回の操作につき平均ｂ／（ｂ−１）
＝２ビツトも符号ビツト列の長さが増加してしま
うという欠点があつた。

本発明の目的は従来のデータ圧縮符号化装置と
データ圧縮復号化装置の上記欠点を取り除き、桁
上りの伝播制御に伴なう符号デイジツト列の長さ
の増加が小さな新規な桁上り伝播制御法を取り入
れたデータ圧縮符号化装置に対応するデータ圧縮
復号化装置を提供することにある。

〈発明の構成〉本発明のデータ圧縮復号化装置は、ｂ進数値
（ｂ≧２）を格納する第１のレジスタと第２のレ
ジスタと、予め登録された確率パラメータを入力
デイジツトに応じて出力する確率パラメータ発生
器と、前記第２のレジスタの内容と確率パラメー
タ発生器の出力とを乗算する乗算器と、前記乗算
器の出力と前記第１のレジスタの内容を加算する
加算器と、前記第１のレジスタの上位一定長のデ
イジツトがすべてｂ−１になつたときに桁上り警
報信号を発生する警報回路を具備し、情報が入力
されるごとに、前記加算器の出力及び前記乗算器
の出力をそれぞれ前記第１レジスタ及び第２のレ
ジスタに保持し、前記第２のレジスタの最上位デ
イジツトが０になつたならば０でなくなるまで前
記第１のレジスタと第２のレジスタを上位デイジ
ツト方向にシフトし、一方、桁上り警報信号が発
生したならば、前記第２のレジスタの内容をすべ
てｂ−１にし、警報信号が発生しなくなるまで第
１のレジスタを上位デイジツトの方へシフトさ
せ、前記第１のレジスタからシフトされて溢れ出
たデイジツト列を、入力された情報デイジツト列
に対応する符号デイジツト列として出力するデー
タ圧縮符号化装置に対応するデータ圧縮復号化装
置において、入力された符号デイジツトを保持す
る第３のレジスタと、前記データ圧縮符号化装置
の複製と、０からｂ−１までのデイジツトを発生
して前記確率パラメータ発生器に供給する発生回
路と、第３のレジスタの内容を第２のレジスタの
内容で除算する除算器と、前記除算器の出力と前
記確率パラメータ発生器の出力を比較する比較器
と、前記第３のレジスタから乗算器の出力を減じ
る減算回路を具備し、前記発生回路の出力を変化
させ、前記比較器の出力が一致したときに、前記
加算器の出力、前記乗算器の出力及び前記減算回
路の出力をそれぞれ前記第１のレジスタ、第２の
レジスタ及び第３のレジスタに保持し、前記第２
のレジスタの最上位デイジツトが０になつたなら
ば０でなくなるまで前記第１のレジスタ、第２の
レジスタ及び第３のレジスタを上位デイジツト方
向にシフトするとともに符号デイジツトを前記第
３のレジスタの最下位デイジツトに保持し、一
方、前記桁上り警報信号が発生したならば、前記
第２のレジスタの内容をすべてｂ−１にし、前記
桁上り警報信号が発生しなくなるまで前記第１の
レジスタ及び第３のレジスタを上位デイジツトの
方へシフトさせるとともに符号デイジツトを前記
第３のレジスタの最下位デイジツトに保持し、前
記発生回路の出力を、入力された符号デイジツト
に対応する情報デイジツトとして出力することを
特徴とする。

〈作用〉前記文献によれば符号デイジツト列の長さは最
終的に得られた区間の幅が小さければ長く、逆に
大きければ短い。従つて、桁上りの伝播制御によ
る区間の縮少率が小さいほど桁上りの伝播制御に
伴なう冗長デイジツトの増加が小さく抑えられ
る。ここで縮少率とは変更前の区間の幅を変更後
の区間の幅で割つた値である。ただし前記文献に
よれば符号デイジツト列からもとの情報デイジツ
ト列が誤りなく復元できるためには、変更後の区
間が変更前の区間に含まれていることが必要であ
る。

本発明では前記手順Ａ・ロ）とＡ・ハ）の間に
次の手順を付け加える。

Ａ・ａ）t₁，t₂，……，t_kをｂ−１とする。

また、前記手順Ｂ・ハ）とＢ・ニ）の間に次の手
順を付け加える。

Ｂ・ａ）S₁，S₂，……，S_kをｂ−１とする。

すなわち本発明では手順Ａ・ロ）及びＢ・ハ）実
行後に区間の幅を拡大するわけである。もつとも
手順Ａ・ロ）とＡ・ｚ）及び手順Ｂ・ハ）とＢ・
ｚ）で行われる操作は互いに独立な操作であるか
ら手順Ａ・ａ）、Ｂ・ａ）を実行するのはＡ・
ロ）、Ｂ・ハ）の前あるいは同時であつてもかま
わない。このようにすれば従来のように区間の幅
を単にｂで割つていたのに比べて縮少率が小さく
なるので、符号デイジツト付加されるる冗長デイ
ジツトの数が小さく抑えられる。また、手順Ａ・
ａ）、Ｂ・ａ）を実行しても実行後の区間は明ら
かに桁上り伝播制御前の区間に含まれているの
で、符号デイジツト列からもとの情報デイジツト
を誤りなく復元することができる。なお、手順
Ａ・ａ）、Ｂ・ａ）において、手順実行後のＴ、
Ｓの値が実行前のＴ、Ｓの値よりも大きくなるの
であればt₁、t₂、……、t_kS₁、S₂……、S_kの値は
ｂ−１以外の値にしてもかまわないが、装置化の
容易さの点ですべてのデイジツトを等しく＜ｂ−
１にするのが好ましい。

第２図は手順Ａ・ａ）を実行する符号化装置の
基本構成図である。図において入力端子１０１よ
り入力された情報デイジツトX_iは確率パラメータ
発生器１０２に順に入力され、確率パラメータ発
生器１０２はX_iの値に応じて確率パラメータC_i
（X_i）、q_i（X_i）をそれぞれライン１０４、ライン
１０３に出力する。加算器、乗算器は前述の符号
化手順Ａ・４）に従つてF1，F2，Ａの値を更新
し、それをレジスタ１０８，１０６，１０５に格
納する。なおライン１０７へはF2＋C_i（X_i）・Ａ
１のときには１それ以外ときには０が出力され
ている。F1の値うち下位Ｍデイジツトより上位
のデイジツトは順に出力端子１０９から出力され
てゆく。一方F1の下位Ｍデイジツトは警報回路
１１０にも供給され、Ｍデイジツトより長い桁上
り伝播が発生しそうになるとすなわちＭデイジツ
トがすべてｂ−１になると桁上り警報信号を区間
短縮回路１１１へ送る。区間短縮回路は桁上り警
報信号を受け取るとＡレジスタ１０５の内容をす
べてｂ−１にする一方、桁上り警報信号が発生し
なくなるまでレジスタ１０８，１０６の内容を高
位デイジツトの方へシフトさせて、ライン１０７
に１が出力されるのを防止する。すなわち手順
Ａ・イ）〜Ａ・ニ）とＡ・ａ）を実行。

第１図は本発明の基本構成図である。図におい
てF1レジスタ２０７、F2レジスタ２０８、警報
回路２０９確率パラメータ発生器２０４は対応す
る符号化装置が具備しているものと同一のもので
ある。入力端子２０１よ入力された符号デイジツ
トW_iはW1，W2の表現デイジツトが格納されて
いるレジスタ２０２に順に入力され、X_i発生器２
０３は確率パラメータ発生器２０４に供給されて
いる出力を変化させることによつてC_i（ｙ）
（W1＋W2）／Ｂを満たすｙのうちで最大のデイ
ジツトX_iを見つけ出し、それを最終的な出力とす
る。なおライン２１１にはX_i発生器２０３の出力
がｙのときにはC_i（ｙ）と（W1＋W2）／Ｂとの
比較結果が供給されている。X_i発生器２０３の出
力が確定すると、加算器、乗算器は前述の復号化
手順Ｂ・４）に従つてＷ、Ｂの値を変更し、それ
ぞれレジスタ２０２，２０６に格納する。また
F1レジスタ２０７、F2レジスタ２０８の内容を
前述の復号化手順Ｂ・イ）に従つて変更する。X_i
発生器２０３の出力は出力端子２０５にも供給さ
れており、X_iの値が確定すると順に出力端子２０
５から出力されてゆく。一方F1レジスタ２０７
の内容は警報回路２０９にも供給されており、警
報回路はＭデイジツトより長い桁上り伝播が発生
しそうになると桁上り警報信号を区間補正回路２
１０に送る。区間補正回路２１０は桁上り警報信
号を受け取るとＢレジスタ２０６内容をすべてｂ
−１にする一方、桁上り警報信号が発生しなくな
るまでレジスタ２０２、２０６、２０７、２０８
の内容を高位デイジツトの方へシフトさせるすな
わち手順Ｂ・イ）〜Ｂ・ホ）〜とＢ・ａ）を実行
する。

〈実施例〉一実施例として、本発明に従つて構成したデー
タ圧縮復号化装置を第３図に、また対応するデー
タ圧縮符号化装置を第４図に示す。

第３図、第４図のうちそれぞれ第１図、第２図と
同一の機能を有するブロツクなしいラインには同
一の番号を付して示してある。この実施例におい
てはｂ＝２である。すなわち符号化装置、復号化
装置での演算は２進法で行ない、また数値は２進
法で表示するものとする。

第４図の符号化装置において、入力端子より入
力された情報ビツトX_iは確率パラメータ発生器１
０２（これは例えばリードオンメモリや適応予測
器によつて構成できる）に順に入力され、確率パ
ラメータ発生器１０２はX_iの値に応じて確率パラ
メータC_i（X_i）、q_i（X_i）をそれぞれライン１０３
に出力する。加加算器、乗算器は前述の符号化手
順Ａ・４）に従つてF1，F2，Ａの値を更新し、
それをレジスタ１０８，１０６，１０５に格納す
る。なおライン１０７へはF2＋C_i（X_i）・Ａ１
のとき１それ以外のときは０が出されている。
F1の値のうち予め決められた下位Ｍビツトより
上位のビツトは順に出力端子１０９からら出力さ
れてゆく。一方F1の下位ビツトは警報回路１１
０にも供給され、Ｍビツトより長い桁上り伝播が
発生しそうになると、すなわちＭビツトがすべて
１になると桁上り警報信号を区間短縮回路１１１
へ送る。警報回路はF1の下位Ｍビツトがすべて
１になつたときに桁上り警報信号を発生するわけ
であるから、警報回路はこれらＭビツトのアンド
（論理積）をとることによつて構成できる。区間
短縮回路１１１は桁上り警報信号を受け取るとＡ
レジスタ１０５は内容をすべて１にする一方、桁
上り警報信号が発生しなくなるまでレジスタ１０
８，１０６の内容を高位ビツトの方へシフトさせ
て、ライン１０７に１が出力されるのを防止す
る。すなわち手順Ａ・イ）〜Ａ・ニ）、Ａ・ａ）
を実行する。

第３図の復号化装置において、F1レジスタ２
０７、F2レジスタ２０８、警報回路２０９、確
率パラメータ発生器２０４は対応する符号化装置
が具備しているものと同一のものである。入力端
子２０１より入力された符号ビツトW_iはW1，
W2の表現ビツトが格納されているレジスタ２０
２に順に入力され、X_i発生器２０３は確率パラメ
ータ発生器２０４に供給されている出力をまず１
とする、そしてライン２１１に供給されているC_i
(1)と（W1＋W2）／Ｂとの比較結果を調べて、も
しC_i(1)（W1＋W2）／ＢならばX_i＝１さもなく
ばX_i＝０とし、X_iを最終的な出力とする。なおラ
イン２１１にはX_i発生器２０３の出力がｙのとき
ににはC_i（ｙ）と（W1＋W2）／Ｂとの比較結果
が供給されている。X_i発生器２０３の出力が確定
すると加算器、乗算器は前述の復号化手順Ｂ・
４）に従つて、Ｗ、Ｂの値を変更し、それぞれレ
ジスタ２０２，２０６に格納する。またF1レジ
スタ２０７，F2レジスタ２０８の内容を前述の
復号化手順Ｂ・イ）に従つて変更する。X_iの発生
器２０３の出力は出力端子２０５にも供給されて
おりり、X_iの値が確定すると順に出力端子２０５
から出力されてゆく。一方F1レジスタ２０７の
内容は警報回路２０９にも供給されており、警報
回路はＭビツトより長い桁上り伝播が発生しそう
になると、すなわちＭビツトがすべて１になると
桁上り警報信号を区間補正回路２１０へ送る。区
間補正回路２１０は桁上り警報信号を受け取ると
Ｂレジスタ２０６の内容をすべて１にする一方、
桁上り警報信号が発生しなくなるまでレジスタ２
０２，２０６，２０７，２０８の内容を高位ビツ
トの方へシフトさせる。すなわち手順Ｂ・イ）〜
Ｂ・ホ）とＢ・ａ）実行する。

〈発明の効果〉以上述べてきたように、本発明に従えば従来の
データ圧縮符号化・復号化装置に比べて圧縮効率
が高いデータ圧縮符号化、復号化装置が容易に構
成できる。

しかも実施例で示したようなデータ圧縮符号
化・復号化装置の場合には簡単な回路で構成でき
るから、高速なデータ伝達システムにも対応でき
る。

これらが今後の高速デイジタル通信回路網の展
開や大容量記憶装置の普及において、効率向上や
性能向上という点で効果を発揮できることは明ら
かである。

【図面の簡単な説明】

第１図は本発明の基本構成図、第２図は本発明
とともに用いられる符号化装置の基本構成図を示
す図、第３図は本発明の一実施例を示す図、第４
図は第３図の符号化装置とともに用いられる復号
化装置の構成例を示す図である。図において、１０２，２０４……確率パラメー
タ発生器、１０６，１０８，１０５，２０２，２
０６，２０７，２０８……レジスタ、１１０，２
０９……警報回路、１１１……区間短縮回路、２
０３……X_i発生器、、２１０……区間補正回路、
１１２，２１３……セレクタ。

Claims

【特許請求の範囲】

１ｂ進数値（ｂ≧２）を格納する第１のレジス
タと第２のレジスタと、予め登録された確率パラ
メータを入力デイジツトに応じて出力する確率パ
ラメータ発生器と、前記第２のレジスタの内容と
確率パラメータ発生器の出力とを乗算する乗算器
と、前記乗算器の出力と前記第１のレジスタの内
容を加算する加算器と、前記第１のレジスタの上
位一定長のデイジツトがすべてｂ−１になつたと
きに桁上り警報信号を発生する警報回路を具備
し、情報が入力されるごとに、前記加算器の出力
及び前記乗算器の出力をそれぞれ前記第１レジス
タ及び第２のレジスタに保持し、前記第２のレジ
スタの最上位デイジツトが０になつたならば０で
なくなるまで前記第１のレジスタと第２のレジス
タを上位デイジツト方向にシフトし、一方、桁上
り警報信号が発生したならば、前記第２のレジス
タの内容をすべてｂ−１にし、警報信号が発生し
なくなるまで第１のレジスタを上位デイジツトの
方へシフトさせ、前記第１のレジスタからシフト
されて溢れ出たデイジツト列を、入力された情報
デイジツト列に対応する符号デイジツト列として
出力するデータ圧縮符号化装置に対応するデータ
圧縮復号化装置において、入力された符号デイジ
ツト保持する第３のレジスタと、前記データ圧縮
符号化装置の複製と、０からｂ−１までのデイジ
ツトを発生して前記確率パラメータ発生器に供給
する発生回路と、第３のレジスタの内容を第２の
レジスタの内容で除算する除算器と、前記除算器
の出力と前記確率パラメータ発生器の出力を比較
する比較器と、前記第３のレジスタから乗算器の
出力を減じる減算回路を具備し、前記発生回路の
出力を変化させ、前記比較器の出力が一致したと
きに、前記加算器の出力、前記乗算器の出力及び
前記減算回路の出力をそれぞれ前記第１のレジス
タ、第２のレジスタ及び第３のレジスタに保持
し、前記第２のレジスタの最上位デイジツトが０
になつたならば０でなくなるまで前記第１のレジ
スタ、第２のレジスタ及び第３のレジスタを上位
デイジツト方向にシフトするとともに符号デイジ
ツトを前記第３のレジスタの最下位デイジツトに
保持し、一方、前記桁上り警報信号が発生したな
らば、前記第２のレジスタの内容はすべてｂ−１
にし、前記桁上り警報信号が発生しなくなるまで
前記第１のレジスタ及び第３のレジスタを上位デ
イジツトの方へシフトさせるとともに符号デイジ
ツトを前記第３のレジスタの最下位デイジツトに
保持し、前記発生回路の出力を、入力された符号
デイジツトに対応する情報デイジツトとして出力
することを特徴とするデータ圧縮復号化装置。