JPS636172B2 - - Google Patents

Description

請求の範囲 １ ｎビツト長（ｍは任意の正の整数）の2ⁿ個の
実現可能な２進シンボル・ストリングa_i＝ｂ(1)、
ｂ(2)、……、ｂ(n)（ただしｉ＝１、２、……、
2ⁿ）を順序付けし、一番目の２進シンボル・スト
リングa₁から任意の順序位置の直前の２進シンボ
ル・ストリングa_i-1までの各２進シンボル・スト
リングの生起確率を累積して累積確率を求めてい
くと、上記任意の順序位置の２進シンボル・スト
リングa_iと上記累積確率とが一対一に対応するこ
とを利用し、上記累積確率に対応するストリング
を上記２進シンボル・ストリングa_iの符号として
出力する算術的圧縮符号化方法において、 上記２進シンボル・ストリングa_iの部分ストリ
ングｓ＝ｂ(1)、ｂ(2)、……、ｂ(j)（ただしｊ＝
１、２、……、ｎ、ｓはa_iにもなりうる）に対す
る累積確率に対応するストリングをＣ(s)、上記
部分ストリングｓの生起確率に対応する補助量を
Ｔ(s)とし、 Ｃ（ｓ、MPS）＝Ｃ(s)＋2^-k Ｔ（ｓ、MPS）＝Ｔ(s)−2^-k Ｃ（ｓ、LPS）＝Ｃ(s) Ｔ（ｓ、LPS）＝2^-k （ただしMPSは最も生起確率の大きいシンボル、
LPSは最も生起確率の小さいシンボル、ｋはシン
ボルLPSの生起確率を2^-kとして表わすパラメー
タ、（ｓ、MPS）および（ｓ、LPS）は上記部分
ストリングｓにそれぞれｂ（ｊ＋１）としてMPS
およびLPSを連結してなる２進シンボル・ストリ
ングである） の規則に基づいてｊ＝１、２、……、ｎの部分ス
トリングｓについて順次ストリングＣ(s)を決定
していく際に、 ストリングＣ(s)のｑ個の最下位ビツトをスト
アする第１シフト・レジスタおよび補助量Ｔ(s)
をストアする第２シフト・レジスタを用意し、 ｂ（ｊ＋１）がMPSの場合は、第１シフト・レ
ジスタの内容を2^-k増加する動作と第２シフト・
レジスタの内容を2^-k減少する動作とを同時に実
行し、第２シフト・レジスタが先頭に０を含をで
いれば前記両レジスタの内容を左シフトして先頭
に１が位置するようにし、 ｂ（ｊ＋１）がLPSの場合は、第１シフト・レ
ジスタの内容をｋ桁左シフトし、第２シフト・レ
ジスタの内容を１にセツトするようにすることを
特徴とする算術的圧縮符号化方法。 技術分野 本発明は予定ソース確率間隔に対応する値を有
するパラメータによつて制御される条件付き２進
ソースの算術的圧縮符号化に係る。 背景技術 FIFO算術的ストリング符号化の先行技術は米
国特許出願第098285号（1979年11月28日）に詳細
に記述されている。また、FIFO算術的符号スト
リングにおけるキヤリー制御方法は米国特許出願
第048319号（1979年６月14日）およびIBM
Technical Disclosure Bulletin、Vol.23、ペー
ジ310〜312（1980年６月発行）に詳細に説明され
ている。 算術的符号化において、前の２進ソース記号の
符号化から生じる前の符号ストリングに被加数を
加えることによつて現在の符号ストリングが反復
して生成されることがRissanen and Langdon、
“Arithmetic Coding”IBM Journal of
Research and Development、Vol.23、No.２、
March1979に開示されている。解読は符号スト
リングの最上位部分の検査と、その大きさから前
記符号ストリングの数値を越えない最大被加数の
決定を含む。前記被加数は次々と差引かれる。解
読された記号は差引かれた被加数に対応するソー
ス英字記号である。 Rissanen and Langdon、“Universal
Modeling and Coding”、IEEE、Trans.
Information Theory、Vol.IT―27、No.１、
January1981において、データ圧縮問題はモデル
化部分および符号化部分に区分される。本発明は
圧縮の符号化面のみを取扱う。間隔（０、１）、
すなわち０を含むが１を含まない数列上の半開き
間隔における数としてFIFO算術的符号によつて
生成される符号ストリングについても前記資料に
記述されている。符号はこの間隔に沿つて有理数
を取扱うように拘束される。ソース・ストリング
は１回に１つのソース記号ｂずつ、反復して符号
化される。実際には、算術的符号化は前記間隔を
次々と細分する。それまでに符号化されたソー
ス・ストリングｓ＝ｂ(1)、ｂ(2)……ｂ(j)に対応す
る小間隔は間隔の下位境界Ｃ(s)および間隔の大
きさを規定する数Ｔ(s)によつて規定される。重
要なことは、小間隔の大きさは一定精度で表わさ
れ、Ｔ(s)の２進表示における有効桁数の長さは
予定されたｑビツトである。このように規定され
た小間隔は〔Ｃ(s)、Ｃ(s)＋Ｔ(s)〕と表示し得る。
間隔は下位境界Ｃ(s)を含み、数Ｃ(s)＋Ｔ(s)まで
の範囲（Ｃ(s)＋Ｔ(s)を含まず）に及ぶ。 前記米国特許出願第098285号における先行技術
によれば、次の記号を符号化するため、間隔長Ｔ
（ｓ）はソース記号値がある部分の数と同数の部分
に細分されなければならない。２進数の場合、
各々のソース記号は２つの記号値の１つだけをと
る。これは間隔が２つの対応する大きさの値Ｔを
有する２つの部分に区分されることを必要とす
る。値Ｔは整数値の制御パラメータｋによつて計
算される。こうして、区分すなわち細分動作から
生じる２つの大きさＴは、それぞれMPS（最も生
起確率の多い記号）およびLPS（最も生起確率の
少ない記号）に割当てられる。先行技術で開示さ
れた細分動作では： 大きさ１：Ｔ(s)×（１−2^-k） (1a) 大きさ２：Ｔ(s)×2^-k (1b) 新しい小間隔は次のように符号化される： 次の場合がMPSの場合： 〔Ｃ(s)、Ｃ(s)＋大きさ１〕 (2a) 次の記号がLPSの場合： 〔Ｃ(s)＋大きさ１、Ｃ(s)＋大きさ２〕 (2b) 数式2bで、大きさ１がＣ(s)に加えられて新し
い下位境界を形成するので、大きさ１は被加数と
呼ばれる。 また、符号化される１および０のストリームは
LPSによつて終了されたMPSの続きとして表示
可能である。エンコーダの動作は符号ストリング
値Ｃ(s)および現在の小間隔の大きさＴ(s)の変更
を必要とする。記号ｂの反復符号化に続くこれま
での符号化ストリングをs.bで示すと、先行技術
は次のように表わされる： 各々のMPSに対して： Ｃ（s.MPS）＝Ｃ(s) (3a) Ｔ（s.MPS）＝Ｔ(s)×（１−2^-k） (3b) 各々のLPSに対して： Ｃ（s.LPS）＝Ｃ(s)＋Ｔ（s.MPS） (3c) Ｔ（s.LPS）＝Ｔ(s)×2^-k (3d) これは、２進記号ストリングで各々のLPSの生
起によつて、最悪事態のサイクル・タイムは４つ
の動作を実行するエンコーダを必要とする。これ
らは下記ステツプを含む。 (1) Ｔ（s.MPS）を形成するために制御パラメー
タｋの関数としての内部変数Ｔ(s)をシフトと
減算によつて減少させる。 (2) この変数をＣ(s)のｑ最下位ビツトに加える。 (3) 両者を予定の量だけ左シフトする。 各々のMPSの生起によつて、エンコーダは (1) 前記のように、内部変数を減少させる。 (2) 先行する１がない場合に、Ｃ(s)およびＴ(s)
の双方の正規化左シフトを実行する。 重要なことは、前のステツプ（ステツプ１）か
ら生じるＴを次のステツプ（ステツプ２）で使用
しなければならないので、現在値だけを使用する
同時更新の可能性はないことである。 発明の説明 本発明によつて解決を求められる技術的問題
は、各々の符号化および解読のサイクルにおいて
動作の同時性を増加することによつて、FIFO算
術的エンコーダのスループツトを増大する問題で
ある。これについて、本発明は最初、式２の内部
の細分の順序を逆にすることを前提とする。先
ず、圧縮された符号ストリームＣ(s)の大きさの
変更が、LPSに代つて各々のMPSにおいて生じ
る。２番目に、内部変数Ｔ(s)の関数によつてＣ
（ｓ）を増加する代りに、各々のLPSの生起によつ
てＣ(s)を予定量左シフトすることが決定される。
正規化されない内部変数は2^-kとなり、単に左シ
フトによつて正規化される。３番目に、前のＴ
（ｓ）の値と無関係な制御パラメータｋの関数とし
てＣ(s)およびＴ(s)の双方を更新することによつ
て同時性が得られる。その結果、１つの２進記号
を符号化するのに必要な順次動作数は、ｋビツト
の単一シフト（LPS）、または加算時間とそれに
続く判断および１ビツト・シフト（MPS）のい
ずれかに減少する。 本発明は各々のMPSに対して予定されたソー
ス英字確率間隔に対応する値を有するパラメータ
の関数が、Ｃ(s)およびＴ(s)のいずれの過去の状
態の関数ではなかつたことから、Ｃ(s)およびＴ
（ｓ）双方を同時に増加させるのに使用可能であつ
たという予想外の観測結果による進歩であると見
ることができる。これは、各々のLPSの生起によ
つて、最初にＴ(s)の更新を、次にＣ(s)の更新を
必要とした先行技術におけるFIFO算術的符号化
技術と対照的である。 本発明は、２進記号ストリングｓ＝ｂ(1)、ｂ(2)
……ｂ(j)、……ｂ(n)からの連続記号ｂ(j)に応じ
る位置の高低を大きさの順序とする算術的圧縮２
進ストリームＣ（s.b）を反復して発生するための
方法および装置として理解される。本発明は次の
ステツプを含む。 (1) Ｃ(s)のｑ最下位ビツトおよび内部変数Ｔ(s)
をそれぞれの第１および第２レジスタに書込
む。 (2) 各々のｂ(j)について、ｂ(j)がMPSを構成す
るかどうかを検査し、LPSの期待値約2^-kに対
する整数パラメータ近似値ｋを受取る。 (3) ｂ(j)がMPSならば、第１レジスタの内容を
2^-k増加し、かつ第２レジスタの内容を2^-k減少
し、第２レジスタが先行する０を含むならば、
両方のレジスタの内容を左シフト正規化する。 (4) ｂ(j)がLPSならば、第１レジスタの内容をｋ
桁だけ左シフトし、かつ第２レジスタの内容を
１にセツトする。 本発明の概略の説明を終えるにあたつて、従前
の算術符号化および本発明の算術符号化について
補足的な説明を加えることとする。 算術符号化の本質はシンボル・ストリングの生
起確率と、順序化された多数のシンボル系列の累
積確率とで把握することができる。３ビツト長の
シンボル・ストリングを考えてみよう。このシン
ボル・ストリングは８個（＝2³）あり、それぞれ
を表のようにｉ＝０〜７に順序付けることができ
る。

【表】

【表】 この表においてＴ(a_i)はストリングa_iが生起す
る確率である。シンボル１、０が生起する確率を
それぞれ0.3、0.7とした。したがつてたとえばＴ
（000）＝0.7³＝0.343である。またＣ(a_i)は累積確率
であり、たとえばＣ(a₂)はＴ(a₀)、Ｔ(a₁)の和であ
る。一般化すると となる。定義および具体的な例からも理解できる
ように０＜Ｃ(a₀)＜Ｃ(a₁)＜Ｃ(a₂)＜……＜１であ
り、ストリングa_iと累積確率Ｃ(a_i)とは一対一で
関係付けることができ、累積確率Ｃ(a_i)を用いて
符号化が可能である。もちろんこのままでは伝送
効率が悪いのでＣ(a_i)の情報のうち必要なものだ
けを送ればよい。表の例では２進小数化した累積
確率Ｃ(a_i)₂の一部のみを送つている。たとえばa_i
では010を送る。 さてつぎにどのようにして累積確率Ｃ(a_i)を得
るかについて考えよう。いま符号化すべきシンボ
ル・ストリングをｎビツトとしておく。そしてそ
のシンボル・ストリングの部分ストリングｓまで
累積確率が得られているとする。ところで部分シ
ンボル・ストリングｓに続いて最も生起確率の小
さいシンボルLPS、たとえば１が発生して構成さ
れるシンボル・ストリングの累積確率は Ｃ（ｓ、LPS）＝Ｃ(s)＋Ｔ（ｓ、MPS） で表わされる。なお、MPSは最も生起確率の大
きいシンボルたとえば０である。この式では、
ｓ、LPSの前の順位にｓ、MPSがあり、Ｃ（ｓ、
LPS）はＣ（ｓ、MPS）にＴ（ｓ、MPS）すなわ
ちｓ、MPSのシンボル・ストリングの生起確率
を足したものとなることを前提としている。そし
てＣ（ｓ、MPS）としてはＣ(s)を用いる。結局 Ｃ（ｓ、LPS）＝Ｃ(s)＋Ｔ（ｓ、MPS） Ｔ（ｓ、LPS）＝Ｔ(s)×ｐ Ｃ（ｓ、MPS）＝Ｃ(s) Ｔ（ｓ、MPS）＝Ｔ(s)×(1-p) である。ただし、ｐはLPSの生起確率であり、ｐ
＝2^-Qと表わすことができる。 以上の規則を用いてＣ(0)＝０、Ｔ(0)＝１から
順次ビツト数を伸ばしていけば所望のｎビツト長
のシンボル・ストリングの符号Ｃ(a_i)を得ること
ができる。 なお、上述の規則ではＴ（ｓ、CPS）でｐ＝2^-Q
を掛けるためＴ(s)がそのままでは急激に小さな
ものとなつてしまう。そこでＴ（ｓ、LPS）はＴ
（ｓ）のままとし、逆にＣ（ｓ、LPS）に2^Qを掛けて
全体として等価となるようにしている。このよう
にするとＴ（ｓ、LPS）を所定のレジスタにスト
アし続けるのが容易となる。また、2^Qの乗算はＣ
（ｓ）をＱビツトだけ左にシフトさせればよい。 本発明の工夫は、より簡易な計算で符号化しよ
うという課題に応えるものである。この工夫はシ
ンボル・ストリングの順序付けを変更することに
ある。すなわち、従前ではｓ、MPSのつぎにｓ、
LPSが位置するようにしているためｓ、LPSの累
積確率Ｃ（ｓ、LPS）はＣ(s)にｓ、MPSの生起確
率をさらに足したものとなつている。Ｃ（ｓ、
MPS）はＣ(s)と等しい。本発明ではこれを逆に
してＣ（ｓ、LPS）のつぎにＣ（ｓ、MPS）が位
置するようにしている。したがつて原理的には Ｃ（ｓ、MPS）＝Ｃ(s)＋Ｔ（ｓ、LPS） Ｔ（ｓ、MPS）＝Ｔ(s)×（１−2^-k） Ｃ（ｓ、LPS）＝Ｃ(s) Ｔ（ｓ、LPS）＝Ｔ(s)×2^-k という規則を用いる。ところで、この場合Ｔ（ｓ、
LPS）では2^-kの乗算があり、この乗算が繰り返
されるとＴ(s)が大変小さくなつてレジスタに有
意の情報を保持するのが困難となる。そこで、Ｔ
（ｓ、LPS）＝１と強制的にセツトし、これにあわ
せてＣ（ｓ、LPS）に2^kを乗算する。すなわちｋ
ビツトだけ左シフトを行う。他方、到来ビツトが
MPSの場合にはＴ（ｓ、MPS）はそう小さい値
にならないので、そのような処理は行わず、単に
近似計算する。Ｔ(s)はほぼ１であるから、Ｔ
（ｓ、MPS）＝Ｔ(s)×（１−2^-k）＝Ｔ(s)−Ｔ(s)2^-k
＝Ｔ(s)−2^-kとする。また、Ｃ（ｓ、MPS）＝Ｃ(s)
＋Ｔ（ｓ、LPS）＝Ｃ(s)＋2^-kとする。 以上を整数するとつぎのようになる。 Ｃ（ｓ、MPS）＝Ｃ(s)＋2^-k Ｔ（ｓ、MPS）＝Ｔ(s)−2^-k Ｃ（ｓ、LPS）＝Ｃ(s)→×2^k Ｔ（ｓ、LPS）＝2^-k→１ 以上の処理によればMPSに対しては2^-kを求
め、これをＣ(s)、およびＴ(s)から同時に＋また
は−処理すればよく、LPSに対してはＴを１にセ
ツトし、Ｃ(s)をｋビツトだけ左にシフトさせれ
ばよい。極めて簡単に処理を行うことができる。 なおＴ（ｓ、MPS）＝Ｔ(s)−2^-kで最上位にゼロ
がくることがあるが、この場合保持レジスタが有
効に利用できないので、Ｔ（ｓ、MPS）の内容を
左に１ビツトシフトする（正規化）。この場合Ｃ
（ｓ、MPS）も１ビツトだけシフトさせて帳尻を
合わせる。

【図面の簡単な説明】

第１図はソースおよびモデルの両方に対する符
号化されたインターフエースを示すブロツク図、 第２図は符号化アルゴリズムの流れ図、 第３図は本発明の方法を実施する２つのALU
ループの符号化装置を示すブロツク図である。 発明を実施するための最良の形態 下記の式は本発明による符号化動作（後で説明
する正規化を除く）を定義するものである。 各々のMPSに対して Ｃ（s.MPS）＝Ｃ(s)＋2^-k (4a) Ｔ（s.MPS）＝Ｔ−2^-k (4b) 各々のLPSに対して Ｃ（s.LPS）＝Ｃ(s) (4c) Ｔ（s.LPS）＝2^-k (4d) 被加数を正しい場所に加えるためにＣ(s)の動
作限界に対する小間隔サイズＴの有効ビツトの調
整を維持することが必要であると認められる。こ
の付加に続いて、符号ストリングＣ（s.b）の動作
限界を再調整する必要がある。再正規化および符
号ストリング再調整の動作は次のステツプを必要
とする。記号LPSが符号化されるならば、正規化
されない大きさは0.00……0100の形式の2^-kであ
る。先行する０の数は“ｋ”である。これは正規
化内部変数Ｔ（s.LPS）＝1.00……０であることを
意味する。コード・ストリングＣ（s.LPS）の正
規化されない動作限界は前の符号化サイクルで見
つかるものと同じであり、ｋビツトのシフトだけ
を必要とする。しかしながら、符号化される記号
がMPSであれば、正規化されない内部変数はＴ
（ｓ）−2^-kである。正規化されない符号ストリング
はＣ(s)＋2^-kである。これらの動作は同時に実行
可能であるが、前記米国特許出願第048319号にお
いて処理し得るＣ(s)のキヤリーが生じることも
ある。しかしながら、再調整は、必要であつて
も、１ビツトのシフトだけである。 圧縮システムの装置の論理ブロツク図を示す第
１図で、２進記号のソース１は経路３によつてエ
ンコーダ１３にビツト列を与える。ソース・モデ
ル５はソース・ストリングの経歴に基づいて機械
動作する有限状態で、経路９上にソース英字確率
間隔を表わす制御パラメータｋを発生し、符号化
される記号がMPSまたはLPSのいずれであるか
について経路７上に表示する。符号化されるビツ
トが4a、4bの関係および4c、4dの関係によつて
定義されるMPSまたはLPSのいずれであるかに
よつて、エンコーダ１３は符号ストリングＣ(s)
の動作限界を変更し、かつその内部変数Ｔ(s)を
変更する。エンコーダ１３の出力はバツフア１５
に送られる。バツフア１５は最新発生符号ストリ
ングのセグメントを保持する。更に、エンコーダ
１３はＣ(s)から固定幅のワードをアセンブルし、
出力バス１７で媒体に送る。エンコーダ１３とバ
ツフア１５のインターフエースは固定線路並列経
路によつて実施可能である。経路１９の信号は符
号化された記号値がMPSまたはLPSのいずれで
あつたかをバツフア１５に知らせる。記号が
MPSであつた場合は、バツフア１５は経路２１
上に現われる値ｋからのシフト量を決定する。そ
の結果、バツフア１５は経路２３によつてエンコ
ーダ１３からｋビツトを受取る。ｋビツトはビツ
ト〔０、（ｋ−１）〕である。これらのビツトはバ
ツフアされている符号ストリング・セグメントに
移される。その結果、バツフア１５はバス１７に
よつて固定長セグメントを出力するとともに、例
えば前記米国特許出願第048319号に記述されてい
るキヤリー伝播を防止するビツト・スタツフイン
グ動作を実行することができる。 エンコーダ１３によつて操作されるビツトが
LPSであることが経路１９によつて示される場
合、バツフア１５は経路２７上の“Ｃ／OUT”
の値をバツフアされた符号ストリング・セグメン
トに加える。経路２９上に現われる正規化に関す
る値“NORM”がアクテイブでない場合は、再
正規化は要求されていない。それに対し、経路２
９上のビツトがアクテイブであれば、ビツト値Ｃ
（０）をバツフアされた符号ストリング・セグメン
トにシフトすることによつて“１”ビツト再正規
化シフトが実行される。固定長出力またはビツ
ト・スタツフイングのバツフア動作は圧縮符号化
されたビツトが恰かもMPSであつたかのように
行われる。 第２図は式4a、4bおよび式4c、4dを実行する
ための計算についての流れ図を示す。Ｃ(s)の動
作限界（ｑビツト）および内部変数Ｔ(s)に対し、
一対のシフト・レジスタＣおよびＴをそれぞれ指
定することによつて、これらのシフト・レジスタ
のみが装置で符号化動作に関連するメモリである
ことが明白である。最初に、シフト・レジスタＣ
およびＴがそれぞれｑビツトの値0.00……０およ
び1.00……０にセツトされる。各々符号化サイク
ルの間に、エンコーダ１５はパラメータｋを供給
し、かつ記号がMPSまたはLPSのいずであるか
の表示を供給する。記号がLPSであれば、シフ
ト・レジスタＴの内容は1.00にセツトされ、符号
ストリング・レジスタ内容Ｃは右側のビツト位置
に挿入される０によつてｋビツトだけ左シフトさ
れる。記号がMPSであれば、Ｔレジスタの内容
は2^-k減分されるが、Ｃレジスタの内容2^-k増分さ
れる。Ｃレジスタの最上位の桁の内容はバツフア
１５に転送される。次の問題はＴレジスタのＴ
（０）の桁に先行する０が存在するかどうかである。
それが存在しない場合、エンコーダ１３は次の符
号化サイクルに進む。先行する０がある場合は、
Ｔを再正規化し、符号ストリングの動作限界を再
調整する必要がある。これはＴおよびＣレジスタ
の内容をそれぞれ１ビツト左シフトするステツプ
と、最下位ビツトに０を挿入するステツプを含
む。Ｃ(0)、すなわちＣレジスタの最上位ビツト
の内容は、経路２５によつてバツフア１５に転送
される。その後、次の符号化サイクルの処理が可
能になる。 次に本発明の符号化応答の例について説明す
る。 記号０はMPSを、記号１はLPSを示すものと
する。また、５つの記号ｂ(1)、ｂ(2)、ｂ(3)、ｂ(4)
およびｂ(5)から成るソース・ストリングはその順
番にそれぞれ ０、１、０、０、１ の値を有するものとする。 更に、これらのビツト位置のスキユー番号を表
わすｋ(1)、ｋ(2)、ｋ(3)、ｋ(4)およびｋ(5)はその順
番にそれぞれ ２、４、４、３、２ を示すものとする。演算は精度５ビツト（ｑ＝
５）で実行される。 エンコーダ１３に対し、ソース・モデル５はｋ
の値を与える。この値から、非ゼロの被加数は
2^-kとして形成される。MPSの場合、被加数はＣ
に加えられてC′を生じ、Ｔから差引かれてT′を
生じる。キヤリーはエンコーダ１３からバツフア
１５に送られる。T′における先行ビツトが１の
場合、Ｔの再正規化またはＣの再調整は不要であ
る。T′における先行ビツトが０の場合、Ｔは再
正規化され、C′はゼロ充填１ビツト左シフトによ
つてＣに再調整される。 最初の状態：Ｃ＝0.0000 Ｔ＝1.0000 注：ステツプ(a)は正規化せずにC′を生じる細分
動作を実行する。ステツプ(b)はＴが正規化される
ときのデータ処理部分を示す。ＣおよびＴの同時
操作は両者を同じラインに乗せることによつて行
われる。 ｋ(1)＝２、ｂ(1)＝０：被加数＝．01 (a) C′＝0.0000＋0.01＝0.0100 T′＝1.0000−．0100＝0.1100 (b) Ｃ＝00.1000（再調整） Ｔ＝1.1000 ｋ(2)＝４、ｂ(2)＝１：被加数＝０ (a) C′＝00.1000（４桁シフトされる） T′＝0.0001 (b) Ｃ＝001000.0000（再調整） Ｔ＝1.0000 ｋ(3)＝４、ｂ(3)＝０：被加数＝0001 (a) C′＝001000.0000＋．0001＝001000.0001 T′＝1.0000−．0001＝0.1111 (b) Ｃ＝001 0000.0010（再調整） Ｔ＝1.1110 ｋ(4)＝３、ｂ(4)＝０：被加数＝．0010 (a) C′＝0010000.0010＋0010＝0010000.0100 T′＝1.1110−．0010＝1.1100 (b) Ｃ＝001 0000.0100（再調整不要） Ｔ＝1.100 ｋ(5)＝２、ｂ(5)＝１：被加数＝０ (a) C′＝001 0000.0100＋０ T′＝0.0100 (b) Ｃ＝０ 0100 0001.0000 Ｔ＝1.0000 （左２シフトによる再調整） デコーダ６９（第３図）はストリング
0010000010000＃を受取るものとする。＃はスト
リング終了標識である。 第３図に示すエンコーダ１３のブロツク図で
は、符号ストリームＣ(s)および内部変数Ｔ(s)の
新しい値を独自にかつ同時に計算すること、およ
びこれらの新しい値について符号ストリングの動
作限界を再調整することが行なわれる。そのた
め、エンコーダ１３の実施例として一対の計算ル
ープが使用される。第１のループはシフト・レジ
スタＣ４１、加算器４９、マルチプレクサ５３お
よび経路３７を含む。第２のループはシフト・レ
ジスタＴ５９、減算器６３、マルチプレクサ５５
および経路５７を含む。従つて、エンコーダ１３
におけるメモリ素子はシフト・レジスタＣ４１お
よびＴ５９のみである。これらのシフト・レジス
タは反復サイクルの終了でクロツクされるエン
ジ・トリガＤ型フリツプフロツプによつて構成さ
れる。連続するクロツクの能動的転移の間の持続
時間はループにおいて各レジスタに与えられる最
悪事態組合せ回路の遅延時間を越える。ジフト・
レジスタＴ５９の場合、エツジ・トリガ信号と対
照的にレベル感知信号に応答する“CLEAR”入
力がある。“CLEAR”入力ラインのアクテイ
ブ・レベルは大低のＤ型フリツプフロツプの場合
のようにエツジ・トリガ入力に優先する。 排他的ORゲートXOR３１は経路７によつてソ
ース・モデル５から送られたMPS／LPS表示と、
経路３によつてソース１から送られた０または１
の２進記号値を終了する。XOR３１の出力は符
号化される記号をMPSまたはLPSのどちらかに
特徴づける。これは加算器４９が経路４３からの
シフト・レジスタＣ４１の内容と他の加算器入力
からのオペランド2^-kを組合せることによつて行
われる。シフト・レジスタＣ４１の内容は符号ス
トリングＣ(s)のｑ最下位ビツト（動作限界）を
構成する。前記組合せの結果（和）によつて生じ
たアクテイブなキヤリー出力信号“Ｃ／OUT”
は経路２７によつてバツフア１５に送られる。
MPSサイクルの符号化において、１ビツト再正
規化シフトを必要とすることがある。これはシフ
ト・レジスタＴ５９における最上位ビツトが０の
ときに生じる。次に、経路２９上の信号はマルチ
プレクサ５３および５５の出力を適当に選択する
とともに、経路２９によつてバツフア１５に送ら
れる。これに関して、Ｃ(s)の動作限界の最調整
はマルチプレクサ５３の機能であり、シフト・レ
ジスタＣ４１の最上位ビツト、すなわちＣ(0)は
バツフア２５への経路２５に現われる。マルチプ
レクサ５３の左入力は左シフト出力から形成さ
れ、右入力は経路５１からの加算器４９のもとの
ままの出力である。マルチプレクサ５３はマルチ
プレクサ３５の右入力に結合される出力バス３７
を有する。マルチプレクサ３５の出力はシフト・
レジスタＣ４１のデータ入力となり、クロツク・
サイクルの終りで前記レジスタにロードされる。 経路３３の信号がLPSであれば、経路３９を介
してマルチプレクサ３５に作用するシフト・ネツ
トワーク４７の制御の下にシフト・レジスタＣ４
１の内容は左シフトされるソース・モデル５から
の４ビツト幅の経路９を介してシフト・ネツトワ
ーク４７に送られた制御パラメータｋによつてシ
フトの大きさは制御される。シフト・ネツトワー
ク４７を制御するほか、パラメータｋはまた経路
２１を介してバツフア１５に送られる。経路３３
のLPS表示と同時に、クリア信号がシフト・レジ
スタＴ５９に送られる。それによつて最上位ビツ
トが１にセツトされる。その場合、シフト・レジ
スタＣ４１からバツフア１５に送られるのはビツ
ト位置Ｃ(0)からＣ(k-1) に送られるｋ最上位ビ
ツトである。これはＣ(s)の値は不変であるが、
符号ストリングの動作限界はｋビツトの左シフト
によつて再調整されることを意味する。この動作
を実行するシフト・ネツトワーク４７はゼロ充填
高速シフト型である。シフト・ネツトワーク４７
の出力は経路３９からマルチプレクサ３５の左入
力を経てシフト・レジスタＣ４１に送られる。制
御信号がLPSのアクテイブを示すとき、マルチプ
レクサ３５で右入力が選択される。シフト・ネツ
トワーク４７の出力はシフト・レジスタＣ４１に
送られ、サイクルの終りでシフト・レジスタＣ４
１にロードされる。このサイクルで、バツフア１
５はシフト・レジスタＣ４１の先行ｋビツトを受
取らなければならない。経路２３はシフト・レジ
スタＣ４１の全ビツトをバツフア１５に送る。バ
ツフア１５は経路２１を介して送られる値ｋの制
御の下に正しい量を選択しなければならない。 経路３３の信号がMPSであれば、デコーダ６
９から得られる2^-kおよび経路６１を介して得ら
れるシフト・レジスタＴ５９の内容をオペランド
入力として減算器６３に加えることによつて正規
化されない値Ｔが計算される。正規化されない差
は経路６５に現われる。減算器６３から得られた
差の先行ビツトはそれが先行０であるかどうか検
査される。前記最上位ビツトが先行０であれば、
１ビツト位置の左シフトがマルチプレクサ５５の
左入力で実行される。先行０がない場合、減算器
６３の出力は経路６５からマルチプレクサ５５を
変更なしに通り、シフト・レジスタＴ５９に戻
る、すなわちサイクルの終りでシフト・レジスタ
Ｔ５９にロードされる。 解読は符号化と双対であることは広く認められ
ている。前に述べたように、符号ストリングの最
上位部を検査し、その大きさから符号ストリング
の値を越えない最大の被加数を決定することによ
つて解読は行われる。この被加数は差引かれ、解
読された記号はその被加数に相当するものであ
る。符号ストリームＣ(s)の最上位部に加えて、
デコーダ６９が受取らなければならない２つの情
報は制御パラメータｋおよびMPS値である。デ
コーダ６９は前記情報によつて、その点で前に符
号化された記号を解読しなければならない。本発
明の原理によつて、第３図に示すエンコーダ装置
の簡単な変更によつて、前記解読は次に説明する
ように実行可能である。 次の説明において、MPS値は０とする。記号
ｂ(i)のどれが符号化されたか分らないが、符号化
パラメータｋ(i)は既知であるので、非ゼロの被加
数を形成できる。ｂ(i)を決定するには、試行被加
数2^-kを形成し、Ｃから2^-kを差引いて試行結果Ｒ
を形成する。同時にＴから試行被加数を差引いて
T′を形成する。試行結果Ｒが負であればｂ(i)＝
LPS、すなわち本実施例では１である。前記Ｒが
負でない場合はｂ(i)＝MPS、すなわち本実施例
では０である。Ｒは再調整されない新しいＣの値
である。その結果によつて反復変数Ｔを調整す
る。下記において、ステツプ(a)は試行減算を示
し、その結果はＲ（Ｃの試行値）になる。ステツ
プ(b)で記号は解読される。ステツプ(C)で、Ｔはそ
れに応じて調整され、ＴおよびＣは再調整され
る。 初期状態： Ｃ＝0.0100 0001 0000＃ Ｔ＝1.0000 ｋ(1)＝２：試行被加数＝．01 (a) Ｒ＝0.0100 001 000−．01 ＝0.0000 0001 0000 T′＝1.0000−．01＝．1100 (b) Ｒ０：ｂ(1)＝0.結果を保持し、正規化と再
調整を行なう。 (c) Ｃ＝00.0000 0010 000＃ Ｔ＝1.1000 ｋ(2)＝４：試行被加数＝．0001 (a) Ｒ＝00.0000 0010 000−．0001＝負 T′＝1.0111 (b) Ｒ＜０：ｂ(2)＝1. Ｃをｋ＝４ビツト左シフ
トし、 Ｔを１にリセツトする。 (c) Ｃ＝0.0010 000＃ Ｔ＝1.0000 ｋ(3)＝４：試行被加数＝．0001 (a) Ｒ＝0.000100 000＃−．0001 ＝0.0001 000 T′＝1.0000−．0001＝0.1111 (b) Ｒ０：ｂ(3)＝0.試行結果を保持する。正規
化と再調整を行なう。 (c) Ｒ＝0.0010 00＃ Ｔ＝1.1110 ｋ(4)＝３：試行被加数＝．0010 (a) Ｒ＝0.0010 00＃−．0010＝0.0000 00＃ T′＝1.1110−．0010＝1.1100 (b) Ｒ０：ｂ(4)＝0.試行結果を保持する。再正
規化せず。 (c) Ｃ＝0.0000 00＃ Ｔ＝1.1100 ｋ(5)＝２：試行被加数＝．0100 (a) Ｒ＝0.0000 001＃−．0100＝負 T′＝1.1100−0100＝1.1000 (b) Ｒ＜０：ｂ(5)＝1. Ｃをｋ＝２ビツト左シフ
トし、 Ｔを１にリセツトする。 (c) Ｃ＝0.0000＃ Ｔ＝1.0000 符号ストリングの終りはＣの上位５ビツトに達
し、Ｃはゼロである。解解処理は終了である。 デコーダはエンコーダと同じように実施される
が、それにはソース・モデルが含まれ、連続して
解読された記号ｂ(i)がソース・モデルに送られて
ｋ(i)が得られる。その外に、いくつかの追加があ
る。第一に、Ｃから2^-kを差引く能力が必要であ
る。第二に、キヤリー出力値は解読サイクルに対
しｂ(i)＝０またはｂ(i)＝１を示す制御入力とな
る。第三に、エンコーダ１３では、正規化左シフ
トおよびＣのLPS左シフトは“ゼロ充填”を伴な
う。デコーダでは、Ｃに対するこれらのシフトは
デコーダ入力バツフアにおける次の先行ビツトか
ら“充填”を受取る。