JPH0258813B2 - - Google Patents

Info

Publication number
JPH0258813B2
JPH0258813B2 JP20200787A JP20200787A JPH0258813B2 JP H0258813 B2 JPH0258813 B2 JP H0258813B2 JP 20200787 A JP20200787 A JP 20200787A JP 20200787 A JP20200787 A JP 20200787A JP H0258813 B2 JPH0258813 B2 JP H0258813B2
Authority
JP
Japan
Prior art keywords
value
bit
bits
event
mps
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Expired
Application number
JP20200787A
Other languages
English (en)
Other versions
JPS6376525A (ja
Inventor
Jooji Ranguden Junia Guren
Rauane Mitsucheru Jon
Boon Penabaakaa Uiriamu
Johanesu Risanen Joma
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
International Business Machines Corp
Original Assignee
International Business Machines Corp
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by International Business Machines Corp filed Critical International Business Machines Corp
Publication of JPS6376525A publication Critical patent/JPS6376525A/ja
Publication of JPH0258813B2 publication Critical patent/JPH0258813B2/ja
Granted legal-status Critical Current

Links

Classifications

    • HELECTRICITY
    • H03ELECTRONIC CIRCUITRY
    • H03MCODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M7/00Conversion of a code where information is represented by a given sequence or number of digits to a code where the same, similar or subset of information is represented by a different sequence or number of digits
    • H03M7/30Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
    • H03M7/40Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code
    • H03M7/4006Conversion to or from arithmetic code
    • GPHYSICS
    • G06COMPUTING OR CALCULATING; COUNTING
    • G06TIMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T9/00Image coding
    • G06T9/005Statistical coding, e.g. Huffman, run length coding

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Multimedia (AREA)
  • Physics & Mathematics (AREA)
  • General Physics & Mathematics (AREA)
  • Compression, Expansion, Code Conversion, And Decoders (AREA)
  • Error Detection And Correction (AREA)

Description

【発明の詳細な説明】
A 産業上の利用分野 本発明は、算術符号化法によつて入力データを
符号化して圧縮するとともに、算術符号化方法に
基く復号によつてオリジナルのデータを復元する
技術に関する。 B 従来技術およびその問題点 所望のデータ転送速度を得るため、または限ら
れたメモリ・スペースにデータを記憶するため
に、データを圧縮してビツト数を減らすことが必
要になる。圧縮されたデータは後で復元される。
このステツプをデータの圧縮解除(de−
compressing)と呼ぶ。 データ圧縮/同解除技術の応用分野の1つとし
て、光学式イメージングが挙げられる。該分野で
は、画素の暗さや影のような情報を大量に扱わな
ければならず、しかもそれらを高速で転送した
り、将来の使用に備えて記憶したりしなければな
らない。 算術符号化法は、データの圧縮/同解除を達成
する1つの技術である。算術符号化では、判断
(decision)が次々に符号化されると、数直線に
沿つた、より小さな、しかも前に規定された区間
に包含される区間が規定されていく。算術符号化
法に関しては、本発明の発明者によつていくつか
の論文が著されている。G.G.Langdon、Jr.著の
“An Introduction to Arithmetic Coding”、
IBM Journal of Research and Development、
vol.28、n.2、1984年3月、pp.135−149、および
D.R.Helman、G.G.Langdon、Jr.、J.J.Rissanen
著“Arithmetic Compression code Control
Parameters Approximation”、involume 23、
No.11、1981年4月、pp.5112−5114がその例であ
る。これらを引用して、従来技術を説明する。 上記論文で述べられているように、算術符号化
法によれば、各判断は、可能性のある複数個の排
他的な結果(outcome、または事象、event)を
持つ。各結果つまり事象は、シンボル化してデー
タの形で表わされる。例えば、光学式イメージン
グ環境では、各判断はある与えられた画素が黒か
否かに対応する。そして、判断の結果は、該画素
が黒ならばY(つまりTES)シンボルで表わさ
れ、該画素が黒でないならN(つまりNO)シン
ボルで表わされる。したがつて、複数の判断を、
例えばYNYYN・・・・のようなシンボル列に
よつて表わすことができる。 従来の符号化技術によると、確率直線に沿つて
ある現在区間が規定される。第1番目の現在区間
は0から1である。該現在区間はセグメントに分
割される。このとき、各セグメントが、後続の判
断についての可能性のある1つの結果に対応す
る。各判断について2つの結果しか可能性がない
ならば、現在区間は2つのセグメントに分割され
る。各セグメントの長さは、各自の関連する確率
に基づいている。それぞれの確率は固定されてい
てもよいし、判断データの入力とともに適応化さ
せてもよい。 より発生頻度の高いシンボルにより大きなセグ
メントを関係づけることによつて、圧縮効率が向
上する。上記文献のうちの前者(“An
Introduction to Arithmetic Encoding”)では、
4シンボルの算術符号化の1例が説明されてい
る。そこでは、各判断が、“a”事象(確率50
%)、“b”事象(確率25%)、“c”事象(確率
12.5%)、または“d”事象(確率12.5%)に帰
着され得る。これら4個の事象を2進数で表現す
ると各事象について2ビツトが必要となり、それ
ぞれが00、01、10、11によつて表わされる。3個
の事象、例えばきわめて起こりやすいaabの場
合、符号化を行わない正直なデータは、00 00 01
となり、6ビツトが必要である。しかしながら、
上記論文のページ137に見受けられるように、算
術符号化法によればシーケンスaabは数値.001
によつて表わされる。6ビツトの代りに、情報を
3ビツトで表現することができる。比較的高い確
率の関連する事象が連続して発生すると、このよ
うにビツトが保存される。 しかしながら、確率の低い、つまり比較的線セ
グメントの短い事象が数多く生じると、保存効果
が低下する。上記確率を用いた場合、事象列dd
は、未符号化データの形で11 11として表わされ
るのに対し、算術符号化法によると111111として
表わされる。大きなセグメントほど発生頻度の高
い事象に事実上対応するならば、蓋然性の高いシ
ンボルが発生するときに達成される保存効果は、
蓋然性の低いシンボルについて余分にビツトが必
要であるという欠点を補つて余りある。したがつ
て、(事象に)関連する確率(およびそれに対応
するセグメントの長さ)が、個々の事象の実際の
確率を適度に追跡することの保証が重要である。 従来、判断データの履歴をたくさん集めながら
事象確率を推定するための様々な技術が提案され
ている。このような技術を記載する文献として、
G.G.Langdon、JrおよびJ.J.Rissanenらによる
“Method for Coding cunts to Coding
Parameters”(IBM Technical Disclosure
Bulletin第22巻第7号、1979年12月、第2880頁な
いし第2882頁)がある。この文献によれば、カウ
ンタが用いら、監視されるシンボルの発生からそ
のシンボルの確率の変化が検出されこれに応じて
蓋然性の低いシンボル(LPS)の確率qが修正さ
れる。特に、1つのシンボルストリングの間にカ
ウントされたシンボルの総数で一方のシンボルの
カウント数を割つたものをあらわすようにqが変
更される。すなわち、kが一方のシンボルのカウ
ントでnが両シンボルのカウント数であるとすれ
ば、シンボルの確率はk/nに基づいて変化す
る。 LangdonおよびRissanenらによる他の文献
“Compression of Black White Imaqes With
Arithmetic Coely”(IEEE Transactions on
Communications、COM−29巻、第6号、1981
年6月)には算術符号化における確率の適応化に
ついての記載がある。非定常的な統計への適応化
を論ずるにあたり、この文献ではその第865頁で
次のように始めている: “或る状態zにおいてr個の連続する0を受け
取つてシンボルS(i)が0である確率について
の現在の推定値がp=c0/cと仮定する。ただ
し、c0は、c(0|z、s(0)、…、s(t))と
定義されるカウント値であり、cはc(z、s
(0)、…、s(t)と定義されるカウント値であ
る。ここでシンボルs(i)を受け取る。もしs
(i)が0なら、p′(r+1)0.2となつている
かどうかをみる。もしそうならこの観測がpにつ
いての推定と矛盾しないと考えて、c0およびcを
1だけ更新して新しい推定を行う。…しかしなが
らp′(r+1)<0.2の場合は、この観測が、おそ
らく、変更された統計をあらわすものであるか
ら、推定を大きめのp値に変更するようにしなけ
ればならない。これは、カウントc0およびcを1
だけ更新する前にこれらを半減することによつて
行われる。受け取つたシンボルs(i)が1なら
ば、確率p(r)を使つて同じ信頼性テストを行
う。…実際には、実現容易化のため、LPSのカウ
ントに対して上限および下限を設け、各々のスキ
ユー値Q(s)がカウントを半減すべきかどうか
を示すようにする。” この文献には、LPSの確率2-Q(s)の最も近い値
で近似することが記載されている。ここで、Q
(s)は整数であり、“スキユー値
(skewnumber)”と呼ばれている。 特別な確率適応化方法に関しては、特開昭60−
196014号公報、および本出願人による特願昭61−
286891号明細書に記載がある。 一般的でかつ新規な確率推定器の適応化方法
が、本出願人による本願と同時に出願された特許
出願(発明の名称:算術符号化システムにおける
確率適応化方法)にも記載がある。本明細書で
は、本発明の環境を説明するのに必要な程度に引
用する。上記特許出願では、ある事象のとり得る
確率値Qeが、例えばテーブルのような形で、指
定されている。上記出願に係る発明によると、規
定された被加数値Aが、判断が行われる度に減少
していく。被加数値の減少量は事象に依存する。
すなわち、各判断の結果が、現在の確率推定値
Qeを持つLPS(less probable symbol)の入力ま
たはMPS(more probable symbol、蓋然性の高
いシンボル)の入力に帰着される2進アプリケー
シヨンでは、LPSが入力されると被加数値が現在
のQe値に減少する一方、MPSが入力されると被
加数値Aは(A−Qe)に減少する。更新された
Aの数値が予め規定しておいた最小値AMIN(こ
れは、Qeの最高値よりも大きい)未満になると、
再びAが少なくともAMINになるまで、更新さ
れた数値の再正規化が行われる(2倍することが
好ましい)。上記出願に係る発明の基本概念は、
Aが再正規化される度にQを再正規化することで
ある。再正規化がLPS事象に続いて起こる場合
は、(LPS事象の推定確率を表わす)Qe値が増加
する。再正規がMPS事象に続く場合は、Qe値が
減少する。Qeの変更と被加数値の再正規化をリ
ンクさせることによつて、カウンタが必要なくな
り、Qeの変更に要する時間が容易に減少するの
で、従来技術と比べて、Qe値のレンジ全体にわ
たつて現実の確率値に密接した追跡が可能とな
る。さらに、上記出願においては、ある特定の
「悪い(bad)」値において、更新プロシージヤが
トラツプされ得ることが認識されている。例え
ば、1回以上倍増されるとAMINと等しいかま
たはそれに近くなる数値の場合、以下のような面
倒なシーケンスを引き起こす。 (1) LPS事象の後で、Aが(悪い)Qeに等しく
なるようにセツトされる。 (2) Aが少なくともAMIN以上になるまで、(1)
で更新されたAが倍増(必要ならばさらに倍
増)される。そして、今までより高いQe値が
選択される。 (3) (2)で更新されたAはAMINに等しいかまた
はそれに近いので、MPS事象がただ1回生じ
ても、AがAMINより小さな値に下降する。
その結果、再生規化が必要になり、Qe値が減
らされて(悪い)Qe値となる。 (4) 現実のLPS確率が推定値Qeよりもずつと大
きいならば、LPS事象が再度発生しやすく、そ
の結果Qeが現在より高い値に戻る。 (5) 再びMPSが1回生じて再正規化を引き起こ
し、Qe値が悪いQe値に戻る。以下同様。 上記出願の教示するところによれば、「トラツ
ピング」問題は「悪い」値を許さないことによつ
て処理される。しかしながら、この解決策の欠点
は、「トラツピング」の観点から言えば「悪い」
特定の数値が、全体の効率の観点から言えば良い
数値であることである。 更新された判断の履歴に基づいて確率の適応化
を図ることに加えて、算術符号化のインプレメン
テーシヨンには、他の問題事項が関係してくる。
例えば「キヤリー伝播」「ボロウ伝播」がそれで
ある。「キヤリー伝播」の問題は、判断入力の連
続に伴つてコード・ストリームCを下記の取決に
従つて更新する算術符号化用符号器の場合に注意
すべきである。 (1) 符号化されつつあるシンボルがLPSならば、
Cの値は変わらず、新しい現在区間はA(new)
=Qeになる。 (2) 符号化されつつあるシンボルがMPSならば、
Cは更新されてC+Qeになり、新しい現在区
間はA(new)=A(previous)−Qe、つまり従
前の区間からQeを引いたものになる。 区間Aはどんどん小さくなり、その小さくなつ
た区間がCに加算されるので、Cの精度(つま
り、コード・ストリームの長さ)が増加する。符
号化されるべく判断データが入力される限り、精
度は無制限に拡張してもよい。Cは(そして精度
も)不定の長さになり得るけれども、コード・ス
トリーム情報を収容するメモリには限りがあるの
で、キヤリーが発生すると問題になる場合があ
る。特に、コード・ストリーム値が連続した数百
の1であるにもかかわらず、Cの最も新しいいく
つかのビツトしかシフト・レジスタに収容されて
いない場合に、ある数AがCに加えられると、問
題が生じる。数百個の1のビツトを経てキヤリー
が伝播するのは不可能である。なぜなら、最新の
ビツトしかアクセスできないからである。キヤリ
ー伝播の1つの好ましい解決策はビツト・スタツ
フイング(ビツト充填)と呼ばれ、文献でもその
概要が述べられている。従来法のビツト・スタツ
フイングでは、1のビツトが所定数並んだ後に少
なくとも1つのキヤリー受信ビツトを挿入するこ
とが示唆されている。 本出願人により本願と同時に出願された特許出
願(発明の名称:データ圧縮システル)では、
「最適な」ソフトウエア用符号器が記載されてい
る。それによると、判断が符号化される度に、符
号点の値はそのままか、または減少する。したが
つて、コード・ストリームCsが0のビツトのス
トリングを含み、かつ減算が必要とされる場合、
ボロウが、該コード・ストリームの最新の部分し
か収容していないシフト・レジスタの長さを越え
て伝播する可能性がある。このような「ボロウ伝
播」は上記特許出願において、符号化済コード・
ストリームの中のすべてのHex‘00'バイトを
Hex‘FF'とキヤリー・ビツトに変換することに
よつて処理されている。このように、ボロウ伝播
はキヤリー伝播の状況になる。符号化の能率を犠
牲にせず、かつ余分のビツトを多数必要とするこ
となしに、キヤリーとボロウを生じさせること
は、望まれる目的である。 算術符号化法の他の局面として、コード・スト
リーム中に制御語を挿入することが望まれてい
る。すなわち、外部の制御装置がコード・ストリ
ームに割り込んで制御語を挿入できるようにする
ことが望まれている。復号器側の端部では、もう
1つの制御装置が制御語を検出し、かつこれを受
信したデータ・ストリングから取り除くことがで
きるようにすべきである。制御語の挿入に関して
は、(a)可能性ある多数の制御語を準備すると
ともに、(b)符号化効率を実質的に減少させる
ことなく制御語の存在を識別することが望まれ
る。上記特許出願では、バツフアへ行く途中にコ
ード・ストリームの一部を収容する32ビツト・レ
ジスタが用意されている。下位側の12ビツト(0
から11まで)が、Aの現在値と位置合わせされる
コード・ストリームの「小数」部である。ビツト
12はスペーサ・ビツトに相当する。ビツト13
〜20は、次にバツフアへ送り出されるべき8ビ
ツト(1バイト)のコード・ストリーム・データ
を表わす。ビツト21はキヤリー・レシーバ・ビ
ツトである。ビツト21に先行する2つのビツト
のうち、ビツト22は制御語が挿入されたか否か
を識別するのに用いられる。ビツト31〜24は
フラグ・ビツトであり、ビツト0からデータが入
力されるにつれて、左へシフトしていく。(8回
シフトした後、フラグ・ビツトは、1バイトのデ
ータがバツフアへ送られる状態になつたことを表
示するビツト位置にある。)単一のスペーサ・ビ
ツトを使うと、ある状態では2ビツトの挿入が必
要とされることもある。 C 問題点を解決するための手段 本発明による算術符号化の符号器と復号器は、
上記特許出願(発明の名称:算術符号化システム
における確率適応化方法)で説明されているよう
な確率適応化を取り上げる。特にそこでは、符号
器と復号器の性能を高める可能なQe値を選択す
ることによつて、確率適応化が促進されている。 この点に関し、本発明は、算術符号化プロセス
に確率推定器が組み込まれた2進算術コーダーに
関連することを述べておく。すなわち、本発明に
おいて、被加数の値は数直線に沿う現在区間に対
するとともに、Qeの値は、A、つまり現在区間
の値の再正規化に応答して更新される。被加数値
(つまり、現在区間の値)Aが最小値AMINを下
回つてQeの更新が求められる時機を決定するた
め、本発明では、AMINの値を表わすビツトの
うち、1番最初のビツトがセツトされ、これに続
くビツトはセツトされていない。例えば、
AMINはHex‘1000'、つまり1 0000 0000
0000(2進数)によつて表わされる。こうすると、
先頭ビツトが0に変化すると、再正規化とQe更
新が示される。このように、再正規化テストは単
一ビツトのテストになる。したがつて、本発明に
よれば、再正規化が求められる時機に加えてQe
を変更すべき時機を決定するのに簡単なテストを
すればよいことになる。米国特許第4467317号明
細書によれば、被加数再正規化について1ビツト
をテストすることが示唆されている。しかしなが
ら、確率適応化と再正規化についての単一ビツ
ト・テストを統合することによつて、従来技術に
比べて顕著な利益がもたらされる。 換言すると、上記シングル・ビツト・テストを
実現するためには、AMINの値を選択し、次い
でこれをスケール・フアクタによつて変更し、
AMINの最上位の桁(Aと同じn桁)のビツト
が1で他の桁のビツトが0で表わされるようにす
る。このスケーリングに準じて、その他の数値も
スケーリングされる。好適な実施例ではAは0.75
と1.5の間にあるようにしているが、これは0.75
と1.5の間であつても、1.0と2.0の間であつてもか
まわない。要するに、シングル・ビツト・テスト
が実現できるようにAMINを表現できればAの
範囲は適当であつてよい。 さらに、本発明は、上記特許出願で開示されて
いる確率適応化方法を、いくつかの面でさらに強
化している。まず、Qe値が含まれるテーブルは、
次のような特徴を持つ。 1 Qeテーブルの各エントリは、6ビツトのコ
ーデイング・パラメータを持つ。そのうちの1
ビツトはMPSのセンスを表示する。残りの5
ビツトからなるQインデツクスによつて、対応
するQe値が識別される。 2 各エントリについて、Qe値の長さは好まし
くは12ビツトである。どのQe値も5ビツトだ
けがセツトされる。各Qe値の最下位ビツトは
常にセツトされている(これは、ハードウエア
によるインプレメンテーシヨンを容易にする)。
様々なQe値についてセツトするビツトの選択
は、ある程度、QインデツクスからQe値を得
るために通過しなければならないゲート数を少
ない数に制限することを考慮して決定される。 6ビツトのコーデイング・パラメータを使うこ
とは、既存のマクロおよび事前に規定されたセル
に従う点で、重要である。さらに、もしコーデイ
ング・パラメータとして使われるビツト数が6よ
り少なければ、テーブルはきわめて粗いものにな
り、定常的統計についての結果の低下を招く。コ
ーデイング・パラメータとして7ビツト以上を用
いれば、さらにチツプ・エリアを増大させねばな
らず、費用が上昇する。Qe値を適切に選択する
ことによつて、必要とされるQeエントリの数を
比較的少ない数(例えば30)に保たれるととも
に、符号化の能率の向上とインプレメンテーシヨ
ンの相当な単純化を達成することができる。 さらに、Qe値の「トラツピング」の問題を避
けるために、本発明は以下のようなことを提唱す
る。上述の特許出願(発明の名称:算術符号化シ
ステムにおける確率適応化方法)で述べられてい
るように、AMIN/2nを形をしたある「悪い
(bad)」値が禁止される。しかしながら、本発明
では、「トラツピング」を捉す点を除けば性能に
貢献する「悪い」値をテーブルに含むことが許さ
れる。このような保留された「悪い」値について
の「トラツピング」効果を避けるため、「悪い」
Qe値の下でのLPS再正規化に応答して、Qe値は、
該悪いQe値に戻るには2回以上のMPS再正規化
を必要とするような所定のテーブル値に増加され
る。本発明は、このようにしなければ「トラツピ
ング」を引き起こすQe値を保留することを目的
としている。 さらに、本発明による符号器と復号器のソフト
ウエアによるインプレメンテーシヨンを容易にす
るため、負のQe表現はMPSのセンスが1である
ことを表示し、正のQe表現はMPS=0であるこ
とを表示する。特にこの方法を用いると、サイ
ン・ビツトをマスクする必要がなく、処理サイク
ルが節約される。 本発明のさらに他の目的は、バツフア・メモリ
へ至る途中でコード・ストリームを収容するシフ
ト・レジスタにおけるビツトの割当を改善するこ
とにある。この点に関して、コード・ストリーム
の小数部と送り出されるべき「バイト」を分離す
るために、スペーサ・ビツトが2ビツト以上設定
される。2以上のスペーサ・ビツトを包含するこ
とにより、Hex‘FF'シーケンスの後に別のHex
‘FF'シーケンスが続く可能性がなくなる。さら
に、スペーサ・ビツトを多くすることによつて、
1ビツトを充填するだけで、該ビツトがキヤリー
を受け取つたり、制御語用にエスケープ・コード
を作つたりする役目を果たすことができる。 本発明の一具体例によると、コード・ストリー
ム・データを収容するXレジスタは、最初、ビツ
トを次のように割り当てる。 X=0000000f 00000000 ss.xxxxxx xxxxxx00 1バイトがバツフアへ送られ得る状態になると、
Xレジスタは次のように構成される。 X=f←0000000c bbbbbbbb ss.xxxxxx
xxxxxx00 1つではなくて(“ss”として示される)2つ
のスペーサ・ビツトを用いることによつて、2以
上の充填ビツトが必要になり得る虞が取り除かれ
る。したがつて、2つのスペーサ・ビツトを使う
ことによつて、余分なビツトを送信する必要がな
くなり、符号化の能率が向上する。さらに、本発
明によれば、符号化および送信の前に、外部の制
御装置によつて制御語をコード・ストリームに挿
入でき、かつ復号の前に送信済ストリームから制
御語を撤回できるような、効率的なエスケープが
実現される。 さらに、本発明は、コード・ストリームの最初
の2ビツトが00であることを提唱する。この結
果、復号の容易化という目的が達成される。 最後に、本発明は、符号および復号の少なくと
も一方が、異なる取決に従うハードウエアまたは
ソフトウエアによつて交換可能に実行され得るよ
うな算術符号化システムにおいて、上記目的を取
り上げる。 ここで、今一度スペーサ・ビツトの概念を述べ
ておく。キヤリー伝播を防止するには、通常バイ
トとバイトの間に0が1ビツト分だけ挿入され
る。これに対し、本願では、キヤリー伝播の可能
性の有無に関係なく、コード・ストリームのビツ
トを、 (a) 2値事象の何れに応じて現在の値のままであ
るか、あるいは現在区間の数値に基づく計算の
対象となつて変更されてしまう、そのようなコ
ード・ストリームを保持する小数部と、 (b) 記憶手段へ向けて送り出されるべきバイトを
保持する後続バイト部と、 (c) 上記(a)と(b)の両部の間に挿入される少なくと
も1つのスペーサ・ビツト に割り振るのである。 そして、判断事象の符号化に応答して、該シフ
ト・レジスタを通じてコード・ストリーム・デー
タをシフトさせる手段と、 記憶手段へデータを一時に1バイト(nビツ
ト)送り出す手段 とを備えておく。 こういう構成によつて、バイト単位での処理が
容易になる。 特に、スペーサ・ビツトとして2ビツト00を割
り当てると、通常はキヤリーが生じても該2ビツ
トは01にしか変更されない。したがつて、スペー
サ・ビツトの部分に00と01以外、つまり11または
10をエスケープ・コードとして出現させることに
よつて、算術符号システムの復号器に、一旦復号
を中止することを指示することができる。復号器
の方では、例えば現在もつている中間のデータを
適当な記憶手段へ送り出した後、新たな指示を待
つ。この指示は、例えばエラー訂正であつてもよ
い。このようなエスケープ・コードを備えておく
ことは、算術符号化システムでマルチ・タスクを
行わせる場合にきわめて重要なものとなる。 D 実施例 符号化取決の異なる符号器を用いる、同一の
コード・ストリーム、コンパチブルなコード・
ストリームの生成 第1図には、算術符号化器102とそれに対応
する算術復号器104を含む、データの圧縮およ
び圧縮解除用の全体装置100が示されている。
データ圧縮の際、装置100は、まず入力データ
(DATAIN)を受け取る。入力データは、2値判
断(binaary decision)の列(YN)として表現
できる。ここで、結果、すなわち事象のそれぞれ
は確率を持つている。次に、装置100は、該列
を、符号化されたビツト列に変えることによつて
キヤラクタライズする。内蔵された確率情報を含
めて判断列を符号化することによつて、圧縮済ビ
ツト列をオリジナルの入力データよりも迅速に転
送できるし、圧縮済データの記憶スペースも少な
くてすむ。 データの大部分をある転送装置または媒体(例
えば、要素105)によつて高速度で転送しなけ
ればならない、あるいはデータの大部分を限られ
たメモリに記憶しなければならないような(また
は、大部分のデータを記憶し、その後で低変調速
度で転送が行われるような)アプリケーシヨンに
おいて、データを圧縮して用いることは非常に重
要である。このような圧縮が特に重要な環境の1
つとして、ビデオ・データ処理の分野、さらに詳
しく言えばテレコンフアレンスを挙げることがで
きる。テレコンフアレンスでは、ピクチヤー等の
情報を伝達するために、大量の情報をある場所か
ら別の場所へ迅速に通信しなければならない。 所望の宛先へ符号化済データが転送された後、
該データは圧縮解除される。つまり、復号器10
4によつて、オリジナル・データまたはそれに関
連したある表現が復元される。実際、復号器10
4は、符号化されたコード・ストリームを一時に
1バイトずつ吟味して、符号器102の行つたプ
ロシージヤを取り消す。 第1図では、入力データDATAINが、まずモ
デル106によつて処理される。 従来、様々なタイプのモデルが議論されてい
る。モデルは、Qコーダー102による符号化の
ために、文脈状態Sと2値判断BITINを発生す
る。特定の文脈Sについての過去のBITIN判断
に基づいて、Qコーダーは、BITIN判断が1ま
たは0である推定確率を既に生成しており、該推
定はBITINの符号化に用いられる。例えば、フ
アクシミリでは、入力データの1つ1つは、所与
の画素が黒であるかそれとも非黒であるかに対応
する。ある与えられた画素が黒または白であるこ
とのどちらを期待できるかについての推定は、一
般に、既に符号化済である近隣の画素値から得ら
れる。QコーダーおよびQデコーダーは、所与の
画素が黒または非黒である確率の推定を、同一の
近隣画素値についての以前の画素値に基づいて行
う。連続してデータが処理されていく際に、蓋然
性の高い状態(MPSまたは非Qe事象と呼ぶ)と
蓋然性の低い状態(LPSまたはQe事象と呼ぶ)
の相対的な確率の値が変化することもあるし、あ
るいは入れ換わつてしまうことさえもある。つま
り、MPSが黒である場合に非黒の事実
(instance)が数多く発生したとすると、非黒状
態の方の蓋然性が高くなる、つまり優勢になるこ
とがある。その場合、MPSは黒状態から非黒状
態に変化する。 Qオーダー102は、算術符号化法を用いて、
モデル106からの状態SとBITIN情報を圧縮
済データに変換する。算術符号化法では、Qコー
ダーが既に生成し、状態Sについての過去の
BITIN判断に続いて適当な形で記憶された、推
定確率が用いられる。 第2および第3図は、それぞれ符号化の概要を
示す。第2図は、ハードウエア用に最適な符号器
を示す。第3図は、ソフトウエア用に最適な符号
器を示す。 第2図において、符号点(code point)は、最
初、所与の区間の下限(の数値)に位置してい
る。LPS事象の生起に関連するQセグメントも区
間の下側にある。MPS事象に関連するPセグメ
ントは区間の上側にある。C(n)は、時間nに
おけるコード・ストリーム値に対応する。A(n)
は、時間nにおける現在の区間の値に対応する。 各判断毎に、最適のハードウエア符号器(第2
図に示す)は、次のような取決に従う。 つまり、判断事象(図ではYNとして示す)が
MPS事象ならば、 (a) C(n)←C(n−1)+Q (b) A(n)←[A(n−1)−Q] となる。 事象がLPS事象ならば、 (a) C(n)←C(n−1) (b) A(n)←Q MPS事象であれ、LPS事象であれ、ハードウ
エアは区間(つまりレンジ)の値Aを再指定する
処理サイクルに時間を費す。さらに、MPSの場
合は、符号点は値Qだけ増分、つまり移動され
る。ハードウエアはAとCの更新を並行して処理
し得るので、かかるハードウエアはどの判断につ
いても1処理サイクルだけを費す必要がある。他
方、ハードウエアLPSが事象の度に符号点を動か
すように構成されたならば、符号点を動かさなけ
ればならない度に、C←C+(A−Q)を決定す
るのに処理サイクルが2つ必要になる。処理サイ
クルの数を制限することはハードウエア操作にお
いてクリテイカルであること、およびLPS事象の
場合に符号点を動かすことは結果として多くのサ
イクル時間を費してしまうことを考慮すると、ハ
ードウエアにとつてはMPS事象の場合に符号点
を移すことが最適であるとわかる。 第3図の符号化プロセスは、PセグメントとQ
セグメントの順序付を同じにした状態で、好適な
「ソフトウエア」用スキームを表わしている。も
つとも、LPS事象に応答すると、符号点は下向き
に(つまり、小さな数値の方へ)へ移動する。こ
のスキームではコード・ストリームがによつて
表わされている。C(n)+A(n)は(n)に
等しい。 最終区間のある部分がCiから引かれるならば、
単一のデコーダーによつて、C(n)または
(n)をデコードして、入力判断事象の同一のセ
ツトを復元することができる。すなわち、デコー
ダー(第1図のデコーダー104参照)に対し
て、どの状態がMPS事象に対応するかを示す第
1の入力と、デコードされつつあるコード・スト
リームについての現在のQ値を示す第2の入力と
が与えられると、デコーダーは、C(n)または
C(n)から最終区間のある部分を引いたものを
処理して、コーダー102へのYN入力列に対応
するYN出力列を生成することができる。YN判
断は、モデル106にマツチするモデル110に
入力され、そしてオリジナル・データまたはその
レプリカが出力DATAOUTとして生成される。 第3図に示す案ではLPS事象の際に符号点が移
動するので、ソフトウエア処理に要するサイクル
の数は少なく保たれる。 第4図には4個の符府器200,202,20
4,206が示されている。符号器200,20
4は、各MPS事象毎に符号点を動かす最適ハー
ドウエア・ルールに従つて符号化を行う。このう
ち、前者はP/Qシンボル順でインプリメントさ
れ、後者はQ/P(逆)シンボル順でインプリメ
ントされている。符号器202,206は、各
LPS事象毎に符号点が移動する最適ソフトウエ
ア・ルールに従つて符号化を行う。このうち、前
者はP/Qシンボル順でインプリメントされ、後
者はQ/P(逆)シンボル順でインプリメントさ
れている。符号器200,202によつて生成さ
れるコード・ストリーム同士は同じ(または少な
くともコンパチブル)にすることができる。それ
は、Cとして表わされている。また、本発明によ
れば、符号器204,206によつて生成される
コード・ストリーム同士は同じ(または少なくと
もコンパチブル)にすることができる。それは、
Zとして表わされている。ZとCは、C=A(o)
−Zなる式によつて一方から他方を導くことがで
きる。この式の計算は、インバータ208におい
てA(o)の数値を1にして説明されている。コ
ード・ストリームCは、ハードウエアの場合の最
適化を考慮した(例えば不都合でない
(unawkward)の計算に基づく)復号器210に
よつて直にデコードされる。また、コード・スト
リームZは、ソフトウエアの場合の最適化を考慮
した復号器212によつて直にデコードされる。
4個の符号器200〜206が生成したどのコー
ド・ストリームであつても、デコードする際には
復号器210,212のどちらも使い得ることが
わかる。コード・ストリームのあるものは、復号
器に至る途中でインバータ208によつて処理さ
れる。 ここで、他の2つの復号器、すなわわちQ/P
ハードウエア復号器とP/Qソフトウエア復号器
もインプリメントできることを念のために述べて
おく。これらの様々な具体例は、上記特許出願
(発明の名称:データ圧縮システム)においても
説明されている。 有限の精度で行う連続事象の符号化と復号 このセクシヨンの記載をわかりよくするため
に、以下のような定義を行う。ほとんどの場合、
変数名を同じ意味を持つ。 定義 C=コード・ストリーム、つまり現在の区間を指
すポインタ(符号点) Cd=基底線(base line)を調整した、復号器コ
ード・ストリーム X=コード・ストリームのうちの、レジスタの中
にあつて送出されていない部分 Qe(i)=i番目に符号化されるシンボルのため
のLPS事象推定確率 Pe(i)=i番目に符号化されるシンボルのため
のMPS事象推定確率 A(i)=i番目のシンボルについての被加数(つ
まり、区間) Si=i番目のシンボル n(i)=シンボルSiの符号化に至るまでの再正規
化の累積カウント R(i)=i番目のシンボルのための再正規化フア
クタ δ(c)=クロネツカーのデルタ関数と等価(条件
が真のとき1、偽のとき0) ε=現在のQ値についての可能な最小の変更 上記定義の下で、次のような関係が適用され
る。 Pe(i)=A(i)−(A(i)×Qe(i)) R(i)=1/2n(i) δ=R(i)2-12(12ビツト精度用) A P/Qハードウエア符号器および同復号器 シンボルの順序付がP/Qである場合に、最適
なハードウエア符号器は現在の区間の底を指す。
コード・ストリームCは次の式で表わされる。 C= 〓i R(i)A(i)Qe(i)δ(Si=M) 換言すれば、値Cは連続する判断事象(つまり
シンボル)の各々を検討することによつて決定さ
れる。サブジエクト・シンボルがLPS事象に相当
するならば、該サブジエクト・シンボルの時点で
のQe値が再正規化フアクタと掛け合わされる。
再正規化フアクタは、区間サイズが所定の範囲、
例えば0.75と1.5の間に維持されるという事実に
関連する。つまり、区間サイズは被加数(Aと記
す)として表わされ、その値は所定の範囲内に留
まるように調整されるのである。i番目の被加数
の値、つまりA(i)が0.75より小さくなると、
上記所定の範囲内に戻るのに必要な回数だけ2が
掛け合わされる(あるいは、他の方法でA(i)
が改められる)。 Aの値を1またはそれに近い値に保持すること
によつて、掛算のフアクタA×QをAとして近似
でき、AとCについての計算が簡単になる。 シンボルが符号化される度に、再正規化は起こ
り得る。なるほど、区間サイズがA×QeQe
(これは、定義により、A×Pe以下であり、した
がつて0.75以下である)にセツトされる度に、A
(i)の値は(少なくとも1回2を掛け合わせて)
再正規化され、例えば上記のような範囲内に戻さ
れる。 MPS事象に応答すると、現在区間A(i)のサ
イズが[A(i−1)−Qe]として概算される。
この値は0.75より小さいこともあるし、そうでな
いこともある。このように、MPS事象に際して
は、再正規化の必要な場合とそうでない場合とが
ある。現在区間の再正規化回数は累積されて、R
(i)、すなわち上記のようにR(i)=1/2n(i)
して 表わされる。再正規化フアクタによつて、C値も
区間値と同じように(例えば同じ回数倍増され
て)変化することが保証される。したがつて、シ
ンボルSiが符号化されるときのC値は、P/Qハ
ードウエア符号器の場合であつてかつMPS事象
の際には増分されるが、その増分は、先行するす
べてのシンボルについての再正規化フアクタおよ
びQe値によつて決定される。 P/Qハードウエア復号器は、次の式に従つて
上記プロセスを解いていく。 Cd=C− 〓i R(i)A(i)Qe(i)δ(Si=M) ここで、Cdはある事象の影響が取り除かれた
後のコード・ストリーム値である。 P/Qハードウエア復号器は、 Cd<A(i)Qe(i)ならば、LPSを解読する。 B P/Qソフトウエア符号器および同復号器 P/Qソフトウエア符号器は、各現在区間の頂
を指す。ソフトウエア・コード・ストリームC〓
は、次の式によつて決定される。 C〓=A(O)− 〓i R(i)A(i)Pe(i)δ(Si=
L)C〓値の評価はA(O)からスタートし、A
(O)から上式の和の項をひいていく。和の項の
加数は、A、現在のP値、および先行するLPS事
象についての再正規化フアクタの積である。 結果C〓から最終区間値A(f)を引くと、P/
Qハードウエア・コード・ストリームで導かれる
通りのCが得られる。 P/Qソフトウエア復号器は次の式に従う。 Cd=C+ 〓i R(i)A(i)Pe(i)δ(Si=L) しかしながら、LPSシンボルを復号するのに必
要な比較は扱いにくい。すなわち、 Cd<A(O)−A(i)+A(i)×Qe(i) または、上記関係式の両辺からA(O)を引い
て Cd−A(O)<−A(i)+A(i)×Qe(i) となる。 C′d=Cd−A(O)とすると、 C′d<[−A(i)×(1−Qe(i))] となることがわかる。 C′dも[−A(i)×(1−Qe(i))]もともに負
であるが、絶対値は0から|A(i)|までの範囲
にある。したがつて、復号器のための演算は、固
定精度演算である。ソフトウエア復号器の処理を
まとめると下記の第8表のようになる。 第
8表 T←A×Qe A←A−T If C′d<A (LPS decoded) Cd←C′d−A A←T renormalize A and C′d else (MPS decoded) renormalize A and C′d if needed. endif 上記計算は、A(i)の値を約1にセツトする
ことによつて、適宜簡略化される。 符号器用レジスタおよび復号器用レジスタ 第5図には、コード・ストリーム情報を記憶す
るのに好適なXメモリ・レジスタ300が示され
ている。レジスタ300は32ビツトを含むが、こ
れらは以下のように割り当てられる。つまり、ビ
ツト31〜24の8ビツトはラフグ・ビツトであ
る。31番目のビツトは「サイン」ビツトを表わ
す。ビツト24は、次のバイトを送り出す準備を
するプロセスにおいて「キヤリー」が生じたなら
それを受け取る役目も果たす。通常の各8シフト
の場合、(bbbbbbbbとして識別される)ビツト2
3〜16は、バツフア・メモリへ送り出されるべ
きバイトを表わす。先行するバイトが‘FF'であ
る場合は、7つのシフトだけが必要とされ、ビツ
ト24〜17が送り出される。ビツト位置14,
15にはスペーサ・ビツトが割り当てられ、送出
されるべきバイトについてのビツト位置とさらに
被加数との計算を行うデータのビツト位置との間
で遅延をもたらす。ビツト13〜2は、コード・
ストリーム・データの最新の部分を表わす。現在
区間(被加数)の値を収容するレジスタの数値に
よる加算(または減算)の対象となるのはこの部
分である。ビツト13〜2は、コード・ストリー
ムの「小数部」と呼ばれ、ビツト24〜14は該
コード・ストリームの「整数部」に相当する。レ
ジスタ300はXレジスタと呼ばれ、コード・ス
トリームCSの最新の符号化済部分を収容する。
Xレジスタの中のビツトが符号化される前に、何
千ものビツトが符号化されていた場合もある。そ
ういつた早くに符号化されたビツトはXレジスタ
の小数部を通つて同整数部へ入り、さらにそこか
らバツフア・メモリへ移動する。該バツフア・メ
モリは、このように先行するバイトを記憶するわ
けだが、そのバイト数には限りがある。希望に応
じて、バツフア・メモリから出たバイトは記憶装
置へ転送してもよいし、復号が行われつつある他
の場所へ転送してもよい。 上記記載に示されるように、データはバイトと
して構成され、かつバイトとして送り出される。
これはフラグ・ビツトによつて達成される。8個
のフラグ・ビツトを00000001に初期設定すること
により、相次いでbビツトがレジスタ300の整
数部にシフトしてくるにつれて、1のビツトがシ
フトする。そして、最も左に位置するフラグ・ビ
ツトが1になると、Xレジスタの内容は「ネガテ
イブ(負)」であると判断される。次にシフトが
生じるときには、Xレジスタ300の整数がバツ
フア・メモリに入力される。 好ましくは、(図示しない)バツフア・メモリ
は、例えば256バイトを記憶するメモリである。
バツフア・ポインタBPは、バツフア・メモリに
最も新しく入力されたバイトを識別する。 Xレジスタに加えて、現在の区間値を記憶する
ためのAレジスタがある。上述したように、現在
の区間は所定の範囲、例えば0.75と1.5の間に維
持される。Aレジスタは、Xレジスタの小数部
(2つの0ビツトが添えられる)と位置合わせら
れる12ビツトの「小数」部(2つの0ビツトが添
えられる)を含み、整数部も含む。 AレジスタとXレジスタの小数部を位置合わせ
することによつて、コード・ストリームを更新す
る際に実行される様々な計算が促進される。区間
が再正規化されて所定の範囲内に戻される度に、
コード・ストリームは同じように再正規化され
て、その相対的な数値が保持されることを再び述
べておく。区間サイズが0.75ないし1.5にセツト
されている場合、再正規化は単に左側へいくつか
シフトすること(すなわち、2を掛け合わせるこ
と)を意味することを思い出されたい。 コード・バイトがセツトされた後(かつキヤリ
ーがない場合に)、Xレジスタ300の内容と適
当な16進数のANDが計算され、コード・バイト
のビツトが取去される。また、Xレジスタは(16
進で記述した)1000000とのXORを計算するため
にセツトされるので、(フラグ・ビツトの)ビツ
ト24は1に確実にセツトされる。 第6図には、P/Qハードウエア・インプリメ
ンテーシヨンで用いられる32ビツトの復号器用レ
ジスタ400が示されている。ビツト割当は次の
通りである。まず、先頭に2つの0ビツト、続い
て12の「小数」ビツトがあり、2つのmmビツト位
置と8個の新しいデータ・ビツト位置はこれに続
く。最も下位の8ビツトはフラグ・ビツトに対応
する。レジスタ400は、フル・ワード、ハー
フ・ワード、またはバイトのように、様々に分割
することがきる。小数部の12ビツトは、復号器の
Aレジスタに記憶されている。被加数の小数ビツ
トと位置合わせされる。 新しいデータ・バイトがXC(ビツト31〜1
6)にシフトされてきた後、該新しいデータは
XNEW(ビツト15〜0)の高位側ビツトへ入力
されるとともに、キヤリーが発生していないなら
ば、XFLAGは1にセツトされる。 すなわち、以下の式の通りになる。 XNEW=SLL B 8 XFLAG=1 低位側のバイトXFLAGが0になると、新しい
圧縮済データ・バイトが求められる。 D キヤリーおよびボロウ 符号器と復号器についての上記説明からわかる
ように、コード・ストリームに違いが生じるとす
れば、それは与えられたP,Q取決のためにキヤ
リーまたはボロウが生じる箇所である。 ここで、キヤリーおよびボロウはバイトの境界
において、1以上のビツト(ただし1バイトより
は小さい)を適宜挿入することによつて準備され
ることを述べておく。この結果、任意のキヤリー
またはボローの結果が直前に送出されたバイトを
越えて伝播することはない。したがつて、バツフ
アのポインタが過去のバイトまで戻る必要は全く
ない。該ポインタは、後続の各バイトがバツフ
ア・メモリに入力されるのに判つて、該後続のバ
イトを指し進めていけばよい。 キヤリー伝播の問題は、コード・ストリームの
値が増加されて更新される場合であつて、既に符
号化済の連続した1からなるバイトが1つ以上連
続してある場合である。この場合、加算の結果キ
ヤリーの伝播が生じる。このような状態を避ける
ため、本発明では、発生し得るキヤリーを受け取
るためにバイト中にビツトを詰め込むようにして
いる。例えば、一連のバイトBo-1、Bo、Bo+1
あり、そのうちのBo-1がバツフアメモリにあつ
て、バツフア・ポインタがバイトBo-1を識別し
ているとしよう。そして、バイトBoはXレジス
タの整数部にあり、バイトBo+1は同じレジスタ
の小数部にあるとする。 バイトBoの値が(16進数の)“FF”ならば、後
続バイトBo+1の先頭(最上位ビツト)位置にビ
ツトが充填される。Bo、Bo+1がそれぞれ
11111111(“FF”)であるならば、本発明により
Bo+1の先頭にビツトが挿入される結果、新しい
符号化済データの例は11111111、01111111、1…
となる。このように、必要ならば、キヤリーを受
け取るために0のビツトが挿入されるのである。
復号器が全部のビツトが1であるバイトを検出す
ると、該復号器は後続の下位ビツトが挿入ビツト
であることを認識し、適切なコード・ストリーム
が生成されるよう処理を行う。 ボロウの問題は、全部のビツトが0のビツトで
あるバイトを含むコード・ストリームについて減
分を行うときに生じる。例えば、3つの連続する
バイトBo-1、Bo、Bo+1のうち、中央のバイトの
ビツトがすべて0であるとしよう。 このとき、1がBo-1バイトからプレボロウ
(pre−borrow、前借)され、Boバイトの8個の
ビツトがすべて1のビツトに変換される。充填さ
れるビツトは、バイトBo+1の新しい先頭ビツト
として挿入される。この新しい先頭ビツトは、セ
ツト・キヤリー・ビツトの役目を果す。したがつ
て、符号器から転送されるデータ・ストリーム
は、次のようになる。 Bo-1−1、1111、1111、1(Bo+1の先頭7ビツ
ト)Bo+1バイト・セグメントから落とされたビ
ツトは、データの後続バイト・セグメントにおい
てピツク・アツプされる。ボロウは充填された
(セツト)ビツトによつて事実上キヤリーに変化
する。何れにしても、復号器は上述したように述
填されたビツトを検出すると、該充填ビツトをキ
ヤリーとして処理する。ビツト・スタツフイング
を含むP/Qハードウエア・コード・ストリーム
とコンパチブルなP/Qソフトウエア・コード・
ストリームを生成することが目標であるから、該
コード・ストリームも2つの拘束に従つて生成さ
れなければならない。まず、16進の“FF”の後
には必ずビツトが充填されなければならない。そ
うでなければ、ハードウエア復号器には不適式な
バイト・パターンが生成されるからである。次
に、現(present)バイトからボロウを取り出す
必要のあるときはいつでも(当然)取り出せるよ
うにコード・ストリームを構成しなければならな
い。(ここで、現バイトとは、以前のコード・バ
イト・サイクルにおいてコード・レジスタからコ
ード・バツフアへ転送されたバイトを言う。)借
りてくるのは1単位なので、桁借りの対象するこ
との不可能なバイト値はゼロである。 一般に、コード・レジスタにおいて新しいバイ
トの開始点に高位の「プレボロウ」ビツトをセツ
トすることによつて、現バイトから桁借りを行う
必要のあることが検出される。便宜上、該プレボ
ロウ・ビツトはビツト位置Pにてセツトされ、後
続のバイトが書込可能になつたならばそれはサイ
ン・ビツトとなる。例えば、32ビツトのコード
(X)レジスタの中身が次の通りであるとする。 Xレジスタ: 00000000、P0000000、xxxxxxxx、
xxxxxxxx Aレジスタ: 000aaaaa、aaaaaaaa 新しいバイトが完成すると、内容は次のようにな
る。 Xレジスタ: P0000000、nnnnnnnn、xxxxxxxx、
xxxxxxxx Aレジスタ: 000aaaaa、aaaaaaaa コード・レジスタがポジテイブ(P=0)なら
ば、プレボロウが使われたのであつて、現バイト
からのボロウが必要である。したがつて、新しい
バイトnnnnnnnnがコード・レジスタからバツフ
ア・レジスタへ転送される前に、現バイトからボ
ロウが取られる。プレボロウを用いると、コー
ド・レジスタの値は常にAレジスタより大きくな
り、将来のボロウは該コード・レジスタの内容か
ら取ることが可能になる。コード・レジスタがネ
ガテイブ(P=1)ならば、現バイトからの桁借
りの必要はなく、未使用のプレボロウPは除去さ
れる。 コード(X)レジスタの内容は、Aレジスタの
内容と比較される。コード・レジスタの方が小さ
いならば、2つの事項が検出されている。まず、
次に送出されるバイト(nnnnnnnn)はゼロであ
ること、第2に、現バイトからの桁借りの必要性
があり得ることである。したがつて、ボロウは現
バイトから取られ、レジスタの中のゼロ・バイト
を経て伝播する。この結果、ゼロであつたバイト
が“FF”に変換される。この“FF”をコード・
バツフアに送りコード・レジスタの内容をシフト
させた後で、2つのプレボロウがセツトされる。
1つはサイン・ビツトとなる位置にセツトされ、
もう1つは後続バイトについての「キヤリー」ビ
ツト位置となるビツト位置にセツトされる。した
がつて、コード・レジスタの内容の方がAレジス
タよりも小さいならば、 Xレジスタ: 00000000、P0000000、00Px、xxxx、
xxxxxxxx Aレジスタ: 000aaaaa、aaaaaaaa である。 後続のバイトが完成すると、 Xレジスタ: P0000000、Pnnnnnnn、xxxxxxxx、
xxxxxxxx Aレジスタ: 000aaaaa、aaaaaaaa となる。 バツフア中の16進数“FF”はビツト・スタツ
フイング(充填)のトリガになるので、プレボロ
ウ・ビツトはスタツフ・ビツト(キヤリー・レシ
ーバ)位置に書き込まれる。ゆえに、未使用のプ
レボロウはハードウエア・コード・ストリームの
キヤリーと等価になる。 コード・レジスタの内容がAレジスタの内容以
外ならば、コード・レジスタの現在の内容はどん
なボロウの要請にも応えられるだけの大きさを持
つていることになる。現バイトがチエツクされ
て、それが“FF”であるならば、ビツト・スタ
ツフイングが引き起こされる。この場合、プレボ
ロウは要請されなかつたので、挿入されたキヤリ
ー・ビツトは常にクリア(clear)である。 上記シーケンスはすべての要請を満たす。すな
わち、ボロウ伝播を阻止し、ハードウエアとコン
パチブルなコード・ストリームを生成する。すべ
てのゼロ・バイトが単純に“FF”に変換された
場合でも、ハードウエア復号器は結果として生じ
たコード・ストリームをデコードすることができ
る。しかしながら、送出されるべきバイトがゼロ
であるときにボロウが必要になるだろうか否かを
先読みして知ることによつて、結果として生じる
コード・ストリームがハードウエア・コード・ス
トリームと同一になる。実際、このように先読み
することによつて、ハードウエア・コード・スト
リーム中の“FF”の存在が検出される。 確率適応化 (a) 算術符号化法と統合される確率適応化 上記のLangdon,Rissannenによる論文は、算
術符号化について詳しく論じており、ここでも引
用することにする。 算術符号化はデータ・シンボルを圧縮符号化す
る強力な方法であるが、それは次の2つの属性に
由来するものである。 (1) 符号化能率の点で、エントロピー限界に接近
できる能力。 (2) 符号化されつつあるシンボルの確率を動的に
変更できる能力。 上記記載に示されるように、複数の判断が符号
化されて数直線上の点が表現される。該点は、特
定の判断列を一意的に表現する数直線上のある区
間に関連する。そのような符号化法は、数直線上
の2つの点で境界を形成されたある現在区間をは
じめに規定することによつて達成される。次に該
現在区間はセグメントに分割される。ここで、各
セグメントは、判断の結果生じ得る事象のうちの
1つに対応する。可能性のある事象は排他的でな
ければならない。つまりどのセグメントもオーバ
ーラツプしない。多シンボル環境では、何れの判
断も、m(≧2)個の事象のうちの1つに帰着し
得る。各セグメントの長さは、対応する判断事象
の相対的な確率によつて決まる。すなわち、判断
事象の確率が大きければ、対応するセグメントも
それだけ大きくなる。これは重要なことである。
なぜなら、大きなセグメントを表わすビツトの数
は少なくできるからである。このため、頻繁に符
号化されるべき事象ほど少ないビツト数で表現さ
れる。 m=2である2値算術符号化法では、LPS事象
は、与えられたYES/NO(Y/N)判断につい
て、YESまたはNOどちらかのシンボルに対応す
る。そして、もう1つの事象がMPS事象に対応
することになる。通常、LPSに対応するセグメン
トはQセグメントと呼ばれ、MPSに対応するセ
グメントはPセグメントと呼ばれる。Qセグメン
トの長さはLPS事象についての推定確率Qeに対
応し、Pセグメントの長さは、確率(1−Qe)
に対応する。 Aを0.75から1.5の範囲に維持すると、値Aを
約1.0として近似できる。すると、上記最適なハ
ードウエア・スキームについてCとAを決定する
ための計算は次のように簡略化できる。 すなわち、MPSが符号される場合、 C←C+Qe A←A−Qe となり、LPSが符号化される場合、 A←Qe となる。 ある事象を符号化した後にA<0.75になつた場
合、AとCの再正規化が行われる。Aだけでなく
Cも再正規化することによつて、符号点の数値と
区間の数値の比は変わらない。 P/Qスキームに従つて生成された符号化済デ
ータを復号するときは、以下の操作が実行され
る。 CQeならば、MPSが復号され、次のような
計算が行われる。 C←C−Qe A←A−Qe 上記条件が成立しないならば、LPSが復号され
て、 A←Qe となる。 上記簡略化された符号器(および復号器)は、
ハードウエアによるインプレメンテーシヨンにと
つて理想的である。なぜなら、レンジの減算(加
算)とコード・ストリームの加算(減算)を並列
に実行できるからである。しかしながら、ソフト
ウエアによるインプレメンテーシヨンにコード・
ストリームの規定と変更について上記ハードウエ
アの場合と同一の取決を採用しても、効率の点で
劣る。なぜなら、もつとも頻繁にとられるパス
(path)において、算術演算が2回必要となるか
らである。したがつて、ソフトウエアによるもつ
と効率のよい符号器のインプレメンテーシヨン
は、コード・ストリームCを現在区間の下端では
なくて上端に向けることによつて実現される。ソ
フトウエアのための符号化プロセスは次の通りで
ある。すなわち、MPS事象ならば、 A←A−Qe となり、LPS事象ならば、 C←C−(A−Qe) A←Qe となる。 最適ハードウエア・スキームまたは最適ソフト
ウエア・スキームのどちらの場合も、A<0.75に
なると、AとCの再正規化およびQeの更新が行
われる。 上記取決を検討する際、どの具体例でもA<
0.75のときにAとCが再正規化され、かつQeが
これに対応して更新されることに注意されたい。 本発明に従つてQeがどのように更新されるか
を次に説明する。 (b) 確率推定器の更新 1 被加数を再正規化する度にQeを更新する 第7図は、連続する事象が符号化され、再正規
化が行われる際の確率推定値Qeの更新を説明す
る図である。第7図において、縦座標は被加数A
の値を表わし、横座標は(後述する)Qeテーブ
ルに含まれているQeの許容値を表わす。Qeの許
容値が0.42208から始まつたとすると、LPS事象
が符号化された結果、被加数の値は0.42208にな
る。LPS事象の符号化の結果、被加数の値は0.75
より小さくなるので、LPS(が引き起こす)再正
規化(“LPS renovm”)が行われる。その結果、
Qe値は0.46896に増加するとともに、Aの値は再
正規化されて0.84416になる。今の具体例では、
2を掛けることによつて、AとCの再正規化が行
われることに注意されたい。この操作は、単純に
レジスタのシフトだけで実行できるから簡単であ
るという利点だけではなく、再正規化の実行回数
を数え続けるのに簡単であるという利点も持つ。
続いてMPS事象が起こると、次の簡単な式に従
つてAの値は0.37520になる。 A←A−Qe すなわち、A=(0.84416−0.46896)=0.37520 Aは0.75より小さいので、MPS(が引き起こ
す)再正規化(“MPS renorm”)が生じる。Qe
はより小さな値0.42208をとり、Aは0.75040に再
正規化される。(Aをさらに再正規化する必要は
ない。なぜなら、Aはもはや0.75未満ではないか
らである。)次にMPS事象が生じると、Aは0.75
未満である0.32833に減少する。Qeとしてはより
小さな値0.32833が選択される。Aを2倍にして
も0.65666であり、まだ0.75未満である。Aをさ
らに2倍にすると1.31332になる。続いてMPS事
象が起こると、被加数は0.98499に減るが、これ
は0.75より大きいので、再正規化は生じない。さ
らにMPS事象が生じると、Aは0.65666まで減少
するので、MPS再正規化が行われる。Qeとして
はより小さな値、つまり0.30489が選択されると
ともに、被加数Aは2が掛け合わされて1.3133に
なる。その後MPS事象が2回続くと、MPS再正
規化が必要になる。 2 Qeテーブル 本発明によれば、第7図に示されるようなQe
値がテーブル(表)の形で記憶されている。第1
表の左側の列には、Qeの複数個の許容値が16進
数の形で示されている。テーブルの各Qe値は、
12ビツトで示される値であることが好ましく、2
つのバイトを占めるように規定されている。Qe
値を5461(16進数では1555)で割ると、N−10進
小数による表現に変換される。Qe値を一意的に
識別するには、5ビツトのインデツクスで十分で
ある。テーブルの隣接するエントリに移るには、
2バイト分のシフトが必要である。第1表の第2
番目の列には、各リストされた確率値をLPS再正
規化に続いてシフトさせる際に、何バイト分シフ
トされるべきかがを示されている。LPS再正規化
の結果、場合に応じてテーブル中のインデツクス
位置の1つ分、2つ分、あるいは3つ分だけ確率
値が増加されることがわかる。 第1表を吟味すると、その中のエントリは第7
図で説明したQe値に対応していることがわかる。
すなわち、10進数の0.46896は第1表中の16進数
0a81に対応する。その後にリストされた3つの
エントリ、すなわち0a01、0901、および0701は、
それぞれ第7図の0.42208、0.32833、および
0.30489に対応する。MPSが1の場合、Qeの負数
が用いられる。 第1表の代りの表が第2表に示されている。第
2表には、Qeの許容値に関して、qi0値が示され
ている。これは、LPS再正規化に関連している。
第1表のQe値に4を掛けることによつて、q0値
が得られる。さらに、MPSが1ならば、q0値は
否定(negate)される。第2表中のqi0項はqilps
(i0)と呼ばれる。これは、後続のQe値(q0)
(MPSが0、つまりQeが正のときとMPSが1、
つまりQeが負のときの両方の場合について)と
そのためにLPS再正規化が起こつたときに当ては
まるインデツクス(i0)とに関連する情報をイン
デツクスが持つことを示す。第2表では、後続の
Qe値とそれに関連するi0値の両方が先行するイ
ンデツクスにおいて見つかる。しかしながら、第
1表では、後続のインデツクスがまず決定されて
から、それに基づいて後続のQe値が決定される。
よつて、第2表のテーブル索引(ルツクアツプ)
プロシージヤの方が簡単である。 第3表は、MPS再正規化の場合を意図してい
る点を除き、第2表と同様である。特に、MPS
再正規化の場合、第3表によれば、テーブル中の
各Qe値について、後続の確率値q0および後続の
インデツクスi0が示される。第2表では選択され
る数値が大きくなつていくのに対し、第3表では
選択される数値が小さくなつていく。 また、表に含まれるQe値は0から0.5までの範
囲に限られることも注意すべきである。0.5にお
いては、LPSを表わす2値事象がMPSになるし、
その逆も成り立つ。したがつて、Qeに対応する
事象が変わる。例えば、自画素の事象がLPS事象
を表わすならば、Qe値は白画素事象の確率の推
定値を表わす。しかしながら、Qe値が0.5に到達
し、これを越えると、今度は黒画素事象がQeに
よつて識別されるLPS事象になる。Qeテーブル
は、LPSとMPSの定義が変わる変換点に関して
対称的にながめることができる。 Qeの許容値の選択は、いくつかのフアクタに
応じて決定される。まず、ある値が「悪い
(bad)」値として認識される。特に、Qe値の「ト
ラツピング(trapping)」を生じさせ得る値は許
されない。値AMIN/2、AMIN/4、…、
AMIN/2n(ここでnはある正の整数)そのもの
またはこれらに近い確率値が「悪い」値だと考え
られる。このような値のときは、次のようなサイ
クルが推定プロセスをトラツプしかねない。 (1) LPS再正規化。 (2) 第1のQe値への移行。 (3) 蓋然性のあるMPS事象がただ1回生じた後
でのMPS再正規化。(Aが既にAMINに等しい
かまたはこれに近い値になつていたことに注意
されたい。)対応してQe値を(今より小さい)
第2の値(悪い値)へ移す。 (4) もう1回LPSが生じ、LPS再正規化が生じ
る。 (5) 第1のQe値へ戻る。 したがつて、Qeの値は、LPS再正規化に続い
てMPS再正規化を行う確率が高すぎることのな
いように、所定の値δだけAMIN/2nよりも大き
くなるように選択することが好ましい。この目的
を達成する1つの方法は、再正規化後に小さくな
るすべてのQe値を、16進数の“1000”とかけ離
れた数値にすることによつて、LPS再正規化が1
回生じた後でMPS再正規化が生じるのは、複数
回MPS事象が続いた後になるようにすることで
ある。Qe値が0.5に近いと、この条件は緩和され
る。Qeがきわめて小さい場合、再正規化済のQe
とAMINの間隔は、MPS再正規化の確率とLPS
の確率が同じオーダーの大きさになるほどに、十
分大きくなければならない。 再正規化されたQe値がAMINまたはそれに値
い数値になるのを避ける上記方策に加えて、本発
明は、LPS再正規化に応答するインデツクス位置
のジヤンプがMPS再正規化に応答するインデツ
クス位置の下降よりも相対的に大きいならば、
「悪い」Qe値を包含できることを教える。例え
ば、第1表のQeの最小値は「悪い」値である。
しかしながら、LPS再正規化が起こると、Qe値
に対するインデツクスは、2エントリ(4バイ
ト)シフトされる。したがつて、上記Qeの最小
値に戻るには、MPS再正規化が2回続けて起き
なければならない。このため、LPS再正規化の直
後にMPS再正規化が極めて起こりやすくても、
推定器がトラツプされることはない。 テーブルの値を選択する際に考慮すべき第2の
点は、符号化の非能率性に関係する。この点に関
しては、Qeの許容値の範囲全体にわたつて符号
化の非能率を最小限にすることが望ましい。第8
図のグラフは、符号化の非能率性とlog2Qの大き
さの関係が示されている。Qe値は第1表に含ま
れている値である。円は実験結果を表わし、実線
は単一文脈の場合の符号化の1具体例(セクシヨ
ン、参照)についての理論計算の結果を表わ
す。符号化の非能率性は、エントロピー、特定状
態(つまりQeテーブル中の特定のエントリ)に
ついてのビツト伝送速度/シンボル、および該特
定状態についての占有(occupation)確率に基
づく。なお、エントロピーHは、 H=−( 〓i Pr(i)logPr(i))によつて定義さ
れる。Pr(i)が第i番目の判断事象の確率を表
わし、和は所与の判断についてのすべての判断事
象にわたつて求めるものとする。与えられたテー
ブルの細分性(granularity)と符号化の際に用
いる算術的な概算の下で、最も一様な曲線が望ま
しいが、そうであることが必須ではない。 本発明によると、インデツクス位置の密度は、
確率の2のべき乗のセツトと比較して、テーブル
のうちの高エントロピーのQe値部分において高
められる。2のべき乗セツトにおいて、1/4〜
1/2のレンジは0.1のQe値に、1/8〜1/4
は0.01に、1/16〜1/8は0.001にそれぞれ対
応する。続くインデツクス位置についても同様で
ある。1/4〜1/2レンジの近くでは、例えば
上述のスキユー・コーダーに比べて、比較的多く
のエントリが存在している。低エントロピーの
Qe値では、密度は比較的疎である。 第3に、システムの応答性、すなわち、見当外
れの数値から適切なQe値に到達するのにどれだ
けの時間がかかるかを考慮しなければならない。
この目的を促進するために、隣接するQe値の間
でより大きな増分と減分が選択される。もつと
も、これは、かかる大きな微分が定常的な結果に
悪影響を与えない場合にあてはまる。定常的な結
果は、固定された確率に従つて、例えば疑似乱数
発生器によつて与えられるデータに基づいて生成
される。非定常的な結果は、確率が時間とともに
変動する可能性のある現実のデータに基づいてい
る。 第1表は上記の事項を考慮して決定したもので
あつて、簡単さ、各文脈に要する記憶が最小とな
ること(例えば、1ビツトをMPSシンボルのセ
ンス用に、5ビツトをQe値のインデツクス用に
して、合計6ビツトにする。)、固定された(つま
り、定常的な)統計についての符号化の能率の妥
当性、および異なるデータ圧縮モデル(例えば、
フアクシミリ圧縮モデルと連続トーン・イメージ
圧縮モデル)から得られる複数文脈データについ
ての性能の間での妥協の産物である。 以上の説明で、符号化能率と変化する確率の迅
速な推定の間の妥協について記した。 第9図には、ゲーテイング回路が示されてい
る。複数の入力線と複数の出力線が備わつてい
る。入力線を、0と1の信号の所定のパターンに
セツトすることによつて、対応するqインデツク
スが該ゲーテイング回路に入力される。各qイン
デツクス毎に、該デーテイング回路は、対応する
Qe値を表わす信号パターンを出力線に供給する。
本発明によると、Qe値は、ゲート、およびqイ
ンデツクス入力に対応してQe値を出力するのに
必要なゲーテイングの数を少ない数に制限できる
ように選択されている。Qe値は、(a)Qe値の最下
位のビツト(LSB)が常に(1に)セツトされ、
かつ(b)どのQe値についても、Qe値の12ビツトの
うちの5ビツトのみがセツトされるように、選択
されている。 したがつて、ハードウエアを容易なものにする
一方、上述の目的も達成される。 3 単一文脈適応化と文脈適応化 第10図には、文脈テーブルが示されている。
特に、3つの文脈(context)C0、C1、および
C2が掲載されている。各文脈は異なるセツテイ
ングに対応し、そのそれぞれで判断が行われる。
例えば、異なる文脈は、光学データのフレームの
中の異なる領域を表わす。該フレームの中には黒
が優勢の領域もあれば、白が優勢の領域もあるか
もしれない。また別の領域は各タイプの事象がか
なり均衡して表現されているかもしれない。した
がつて、各文脈毎に、MPS識別子、すなわち、
黒(つまりYES)の判断がMPSであるか、また
は白(つまりNO)の判断がMPSであるかに関す
る標識が存在する。これは、第10図のテーブル
ではMPSの列に2進数で表記されており、C0と
C2の文脈では0事象がMPS事象を表わす一方、
C1の文脈では1事象がMPS事象を表わしている。 テーブルの隣の列はQeインデツクス・テーブ
ルであり、個々の文脈について現在指示されてい
るQeエントリを表示する。C0文脈では、0番目
のエントリが指示されている。同様に、C1、C2
文脈では、それぞれ、12番目と29番目のエントリ
が指示されている。最後の列には、個々のQe値
がそれぞれ0.5、0.10、0.001であることが示され
ている。MPS識別子とQeインデツクスは6ビツ
トで表現されることが好ましく、この具体例では
Qeインデツクスが好適な5ビツトで表現されて
いる。しかしながら、ビツト数は変更可能であ
る。 本発明の1具体例によれば、単一の被加数値が
記憶され、考慮する文脈に無関係に用いられる。
各文脈において判断が入力され、各文脈について
再正規化が行われる際に、共通の被加数が処理さ
れる。 1例として、それぞれが対応する文脈に関連す
る0と1のビツトのストリングを示す。ストリン
グ01100は、C0−C1−C0−C0−C2文脈における
ビツトをそれぞれ表現する。第10図のテーブル
より、該ビツト列は、(C0について)MPS、(C1
について)MPS、(C0について)LPS、(C0につ
いて)MPS、および(C2について)MPSを表現
する。この例のために、最初のビツトが符号化さ
れる前のAの初期値が1.0であるとしよう。上記
P/Q符号化スキームの下では、ビツト・ストリ
ング01100に応答して、次のような操作が行われ
る。 1番目のビツトについて、 A←A−Qe(C0)=1.0−0.5=0.5となる。A
が0.75未満になるので、Aは1.0に再正規化さ
れ、Qe(C0)の値は0.48に減らされる。 2番目のビツトはC1文脈のMPSを表現して
いるので、被加数Aは、下記の式に従つて減少
する。 A←A−Qe(C1)=1.0−0.1=0.90 再正規化もQeの更新も行われない。 3番目のビツトは文脈C0のLPSを表現して
いるので、LPS再正規化を起こす。被加数の値
は0.90からQe(C0)、つまり0.48に変化する。A
の値は再正規化(2倍に)して0.96にしなけれ
ばならない。C0文脈についてのQe値はインク
レメントされる。この例では、0番目のエント
リの方へ1エントリ戻ることによつてQe(C0)
値が増加することにする。後述するように、本
発明は、1エントリ以上離れた単一の値へQe
値を上昇させることも考慮している。本発明に
よる他の方法では、Qe値が現実の確率からど
れだけ離れてみえるかに応じて、後続のいくつ
か可能性のあるQe値の中から選択された1つ
までQe値を増加させる可能性も考慮している。
後者の方法は、上記特許出願(発明の名称:算
術符号化システムにおける確率適応化方法)の
明細書中で、多レートの例として説明されてい
る。 4番目のビツトは、C0文脈でのMPSである。
Aは(0.96−0.5)=0.46に変更され、MPS再正
規化が必要になる。Aの値は2倍されて0.92に
なり、Qe(C0)は0.48に減少する。 5番目のビツトは、文脈C2でのMPSに相当
する。被加数Aの値は、(0.96−Qe(C2))=0.92
−0.001=0.919になる。これは0.75より大きい
ので、再正規化は行われない。 5ビツトの後で、テーブルは次のようなエント
リを持つ。すなわち、文脈C0については、MPS
=0、Qe(C0)インデツクスは1、およびQe
(C0)の値は0.48。文脈C1については、すべての
データに変化はない。文脈C2については、すべ
てのデータに変化しない。次に符号化される判断
事象のための現在の被加数Aは、判断の文脈に関
係なく0.919である。 単一文脈の例と比較すると、多文脈の例では、
複数の判断文脈を一緒に処理することができる。 4 単一レート適応化 単一レート推定器によれば、ある特定のQeに
ついて、LPS再正規化に関しては、次の確率とし
て選択されるべき今よりも大きな値が1つだけ指
定され、MPS再正規化に関しては、今よりも小
さな値が1つだけ指定される。単一レート推定器
の1例は、有限状態機械としてセクシヨン5で説
明する。 5 Qeテーブルの有限状態機械表現 第12図は、単一レート、かつ単一文脈の推定
器の有限精度推定器によるインプレメンテーシヨ
ンが示されている。数値kexは、MPS事象とLPS
事象の定義が入れ換わる状態を表わす。第12図
では、各状態は、MPS再正規化に対応して1つ
の外向きのパス(path)を持つとともに、LPS
再正規化に対応して1つの外向きのパスを持つ。
knaxの場合は、MPS再正規化ゆえに更新を行つ
ても、同一の状態に戻る。 各状態は、特定のQe値を表わす1つのテーブ
ル・エントリであると考えてよい。各エントリ
は、それに続く2つの可能なエントリと結ばれて
いる。好ましくは、MPS再正規化の結果、knax
により近くなる次の状態への移行が起こる。LPS
再正規化時には、可能性のある次の単一の状態へ
のパパスを通つて、状態位置が1つ、2つ、ある
いはそれ以上変化し得ることに注意すべきであ
る。 V Qコーダー・システムのフローチヤートの説
明 以下のフローチヤートでは、上記「ハードウエ
ア」と「ソフトウエア」の具体例が、フローチヤ
ートに即して記載されている。符号器、複号器の
例で両者の違いを示すときは、−Hまたは−Sを
つけることにする。 第13図は、本発明の算術符号化法圧縮/同解
除システムによるコーダとデコーダを示すフロー
チヤートである。(第1図と対比されたい)。第1
図では、BITINが符号化される2値事象であり、
BITOUTが復号された2値事象である。第13
図のフローチヤートでは、エンコーダー、デコー
ダーともに2値判断のことをYNと呼んでいる。
一般的に説明すると、第14図、第15図の
INITENCは、ハードウエア、スキーム、ソフト
ウエア、スキームのそれぞれの圧縮システムを初
期化する。モデル・プロセスは、「S、YNの獲
得」というステートメントによつて表わされてい
る。INITSTATE(第16図)は、すべての文脈
状態Sについて、qインデツクスの初期値とQe
値を設定する。ENCODEブロツク(第17図)
では、文脈状態SとYN値を用いて、圧縮済デー
タ・ストリームが生成される。すべてのシンボル
の符号化がいつ完了したかに関する判断は、外部
の手段によつてもたらされる。例えば、グレイス
ケールTVには、512画素/ライン×480ラインの
ような固定されたフオーマツトがある。取決に関
して合意しなければ、符号器は、該情報を、外的
な手段により、または圧縮済データの1部とし
て、そのどちらかによつて、復号器に送る。 すべてのシンボルが符号化されると、ブロツク
FLUSH(第33図、第34図)の働きにより最
後のバイトが出力される。したがつて、復号器に
は確実にすべてのシンボルを完全に復号するのに
充分なデータが与えられる。ブロツク「送信」
は、記憶または送信を表現している。この図で
は、送信または記憶の前に完全な圧縮データが生
成されるかのように思われる。しかしながら、ど
のバイトも、後続のバイトが生成された直後に送
信することができる。復号器を初期設定するため
に、INITDECブロツク(第39図、第40図)
が1回呼ばれる。復号器では、モデルが文脈状態
Sの値を与える。DECODEブロツク(第41図)
は、YN判断を取り戻す。復号がいつ完了したか
に関する判断は、外的に、または圧縮済データ・
ストリームの一部としてもたらされる。 (a) 符号器動作の詳細な説明 以下の定義は、フローチヤートとその説明にあ
てはまる。 定義 QO(S)は、プログラムおよびフローチヤー
トにおいて、16ビツトを持つ少数点の固定された
少数として定義される。正の数にもなれるし、負
の数にもなれる。 IO(S)は、Qe確率値を更新するための
QIMPSテーブルまたはQILPSテーブルのインデ
ツクスである。これは、QO(S)の直後に2バ
イトの形で記憶される。QIMPSテーブルまたは
QILPSテーブルからの4バイトが、次のQO、IO
のペアになる。 Aは16ビツトの整数だが、12の少数ビツトと、
それに続く2つのゼロと2つの先頭整数ビツトと
に分ける2進少数点を持つ2進少数として考える
ことができる。 Xは、符号器については第5図に、復号器につ
いては第6図にそれぞれ示されるような構造を持
つ32ビツトの数である。 XCは、復号器におけるXの最上位ビツトを含
む上位側の16ビツトである。 XNEWは、復号器におけるXの最下位ビツト
を含む下位側の16ビツトである。 XFLAGは、復号器におけるXの最下位ビツト
を含む下位側の8ビツトである。 LENはコード・ストリームのためのバツフア
の長さである。これは(任意だが便宜上)256バ
イトにセツトされる。LENは1にセツトするこ
ともできる。 BPSTは圧縮済データ・バツフアの始まりを指
示する。 BEは圧縮済データ・バツフアを越えた最初の
バイトを指示する。 BPは圧縮済データの現在バイトを示すポイン
タである。 BはBPによつて指示された圧縮済データ・バ
イトである。 AMINは再正規化が必要となる時機を決定す
る。AMINは、(0.75と等価である)Hex“4000”
にセツトされる。ただし、ソフトウエア復号器に
ついてだけは、マイナスHex“4000”にセツトさ
れる。これもやはり0.75と等価である。 INITENC(第14図および第15図)が符号
器の初期設定を行う。インプリメントされるバー
ジヨンが第2図に示すハードウエア・バージヨン
(−H)か、第3図に示すソフトウエア・バージ
ヨン(−S)かに従つて、2つのバージヨンの
INITECがインプリメントされている。テーブル
がセツト・アツプされた後、INITSTATE(第1
6図)が文脈記憶領域を初期設定する。2つのバ
ージヨンに共通して、LENは256バイトに初期設
定され、BEは圧縮済データ・バツフアの終末に
位置づけられるとともに、BPはBPST(つまり送
るべきバツフアの実際の始まり)の1バイト手前
に位置づけられている。1つのバイトが書き込ま
れる前に、ポインタが更新される。このため、1
のオフセツトが必要になる。(BPによつてアドレ
ス指定される)バイトBは“80”に初期設定され
る。これは、圧縮済データ・ストリームにおける
最初のバイトとしてB=0またはB=“FF”とい
う特別な場合にトリガがかからないようにするた
めである。レンジAは“4000”に、そして
AMINもそれと同じ値に、それぞれ初期設定さ
れる。 バージヨン間の違いが現れるのは、Xの初期設
定においてである。すべてのバージヨンにおい
て、8個の圧縮済ビツトがレデイになつたことを
フラグで知らすために、8番目のmsbが1にセツ
トされる。ソフトウエア・バージヨンでは、Xの
フラグ、ビツトの直後にボロウ・ビツトが挿入さ
れるとともに、低位側のビツトはAとのOR操作
が施される。このボロウ・ビツトは、ボロウ伝播
がフラグ・ビツトへ至るのをブロツクする。 ENCODE(第17図)は、YNが1または0に
応じてとられる2つのパスを示す。 CODEYN1(第18図、第19図)は、YN=
1を符号化する。Q0(S)<0ならば、MPS=1
であり、MPSシンボルを符号化しなければなら
ない。負であるQ0を加算することにより、Aは
減らされる。ハードウエア・バージヨンは、負の
Q0を引くことによつて、Xを増加させる。MPS
パスにおいてAがAMIN未満ならば、
UPDATENPS(第22図)によつてQ0を減らす
ことができる。RENORMブロツク(第24図)
では、AとXの両方が再正規化される。Q0が正
(ゼロは許されていない)ならば、MPS=0であ
り、LPSシンボルがが符号化されなければならな
い。ソフトウエア・バージヨンの場合、MPSレ
ンジを計算せねばならず、かつXは新しいAの分
だけ減らさねばならない。どちらの場合も、Aは
Q0(S)にセツトされ、そしてLPSの場合につい
ての確率の更新がUPDATELPS(第23図)に
おいて行われる。Q0は常にAMIN未満であるか
ら、再正規化が必要になる。 CODEYNO(第20図、第21図)は、YN=
0になるパスについて、第18図および第19図
と同じ操作を示す。この場合、MPSパスについ
てはQ0が正であり、LPSパスについてはQ0が負
である。 UPDATEMPS(第22図)は、MPSパスでの
確率更新を行う。新しいQeおよびインデツクス
(合計4バイト)が、QIMPSテーブルの中の古い
IO(S)の場所で発見される。第3表は、
QIMPSテーブルの1例である。 UPDATELPS(第23図)は、LPSパスでの
確率更新を行う。新しいQeおよびインデツクス
(合計4バイト)が、QILPSテーブルの中の古い
IO(S)の場所で見つけられる。第2表は、
QILPSテーブルの1例である。 RENORME(第24図)は、A値とX値の正
規化を、一度に1ビツトずつ行う。Aがまずシフ
トされた後、Xについて最上位ビツトがセツトさ
れたか否かの試験が行われる。セツトされている
場合、Xの次のシフトによつてそのフラグ・ビツ
トが取り除かれるとともに、1バイトが
BYTEOUT(バイト・アウト、第25図、および
第26図参照)によつて出力される。セツトされ
ていない場合、Xは単に1ビツト分シフトされる
だけである。このプロセスは、AがAMIN未満
である限り続く。 BYTEOUT(第25図および第26図)によれ
ば、復号器は、各“FF”バイトの直後において、
後続のバイトの先頭にビツトが1つ挿入されるこ
とを予期している。先頭ビツトはキヤリー・ビツ
トとなるであろう。 第25図では、ハードウエア・バージヨンがま
ず最初に最後のバイトBを見て、Bが“FF”な
らば、直後にSHIP7−H(第27図)において6
ビツトだけを出力する。どんなキヤリーでも、新
しいバイトの1番目に大きな桁のビツトに現われ
るであろう。Bが“FF”未満ならば、キヤリー
についてXのテストが行われる。キヤリーがない
ならば、8ビツトの出力をSHIP8−H(第29
図)によつて行うことができる。キヤリーがあれ
ば、最後のバイトBについて1だけ増分する必要
があり、結果について“FF”となつたか否かの
テストが行われる。結果が“FF”であれば、既
にBに加算済のXにおけるキヤリーを、後続の7
ビツトを出力する前にクリアしなければならな
い。結果が“FF”でないならば、8ビツトを新
しいバイトへ出力してもよい。 ソフトウエア用のバージヨンである
BYTEOUT−S(第26図)は、Xが正であるか
否かをテストする。Xが正ならば、ボロウ・ビツ
トが使用されたのであり、8ビツトを出力する前
にBを1だけ減分しなければならない。ボロウ・
ビツトが使用されていなかつたならば、AがXと
比較される前にXからボロア・ビツトがクリアさ
れる。XがAより小さいならば、将来ボロウが必
要になる可能性があるが、新しいバイトがゼロと
して出力される場合には、ボロウを入手できなく
なる。(Aはせいぜい“7FFC”であり、Xは8
個の出力ビツトのうちにゼロだけを持つている。)
SHIP8FF−S(第31図)はプレ・ボロウを行つ
て新しいバイトを“FF”に変換し、借りたビツ
トをXにセーブする。Bが“FF”ならば、
SHIP8−S(第30図)によつて8ビツトが送出
される代りに、SHIP7−S(第28図)によつて
7ビツトだけが送出される。 SHIP7−H(第27図)は、NEXTBYTE(第
32図)における出力バイト・ポインタを増分
し、Xからの新しいBビツト24〜17に保持す
る。先頭ビツトはどんなキヤリーも含む。7番目
に大きなビツトにてフラグが挿入される前、後続
の17ビツトだけがXに残される。この結果、7個
の新しいビツトが準備されると、次のバイトが出
力される。なぜなら、1個のビツトがXに残つて
いるからである。SHIP7−S(第26図)は、フ
ラグ・ビツトをすぐ追うようにボロウ・ビツトが
セツトされる点を除いて、SHIP7−Hと同じで
ある。 SHIP8(第29図および第30図参照)は、ど
ちらのバージヨンも似通つている。ポインタを後
続の出力バイトBに増分した後、Xの中のビツト
23〜16にある8ビツトがBにて保持される。
Xの中で、最下位側の13ビツトを除くすべてのビ
ツトがクリアされて、フラグは上位から8番目の
ビツトにて挿入される。ソフトウエア用バージヨ
ンでは、フラグの後にボロウ・ビツトも挿入され
る。 ソフトウエア符号器用バージヨンにおいては、
必要ならばBについて減分を施すことが可能であ
ることが保証されなければならない。「書き込ま
れるべき後続のバイトがゼロであり、これからボ
ロウを取る必要が生じかねないときに、
SHIP8FF−S(第31図)が実行される。したが
つて、Bを1だけ減少させて後続バイトをHex
“FF”に変換して、直ちにボロウがとられる。こ
れら2つのバイトから取られたボロウはXの中に
挿入される。そこでは、該ボロウが必要とされな
いなら、該ボロウは後続バイトの中でキヤリーと
して出力される。」 NEXTBYTE(第32図)は、BPを動かして
圧縮済データ用バツフアの後続バイトをアドレス
する。インクレメントされた後、BPがバツフア
の終端以上の値になるならば、該バツフアを転送
しなければならず、BPもバツフアの先頭に戻る
ようリセツトしなければならない。必要ならば
BPSTとBEが適当に変化することが想定されて
いる。 最後のシンボルが符号化された後、まだXの中
にある22個の圧縮済ビツトについてはフラツシ
ユ・アウトする必要がある。FLUSH−H(第3
3図)では、CTが22に初期設定され、そしてフ
ラグが最上位のビツトに来るまで、Xの中での各
シフトに対応してデイクレメントされる。もう1
回シフトされると出力ビツトがバイト境界に位置
される。そうすると、FINALBYTES−H(第3
5図)によるこれらの最後のバイトの出力が可能
になる。 FLUSH−S(第34図)はXを区間の底へ移
動させる。これによつて、ハードウエア・バージ
ヨンによつて生成される値に正確に位置づけられ
る。ビツトのバイト位置合せの後、ボロウが使用
済の場合、FINALBYTES−S(第36図)にお
いて最終バイトが出力される前に最後のバイトを
デイクレメントしなければならない。 FINALBYTES−H(第35図)は、すべてビ
ツトがフラツシユ・アウトされてしまうので、ル
ープの中で、BYTEOUT−H(第25図)と同じ
タイプの動作を行う。FLUSH7(第37図)と
FLUSH8(第38図)のブロツクは、CTを7ビ
ツトまたは8ビツトだけ適当にデイクレメントす
ることを含む。それが完了すると、記憶されてい
る最後のバイトを越すまでBPがインクレメント
されて、バツフアの最後の内容が送出可能にな
る。 ソフトウエア式符号器用のバージヨン
FINALBYTES−S(第36図)は、先行するバ
イトが“FF”であるか否かに応じて7ビツトま
たは8ビツトを送出するだけでよい。プレボロウ
の処理はすでにFLUSH−Sにて行われている。
Xは区間の底に動かされたので、BYTEOUT−
SにおけるAを用いたテストは無関係である。 FLUSH7(第37図)では、ハードウエア・バ
ージヨンとソフトウエア・バージヨンのどちらの
場合でも、新しいバイトを指し、ビツト24〜1
7を記憶し、Xの下位側の17ビツトだけをセーブ
し、かつ7だけCTをデイクレメントすることに
よつて、6ビツトが出力される。 FLUSH8(第38図)では、ハードウエア・バ
ージヨンとソフトウエア・バージヨンのどちらの
場合でも、新しいバイトを指し、ビツト23〜1
6を記憶し、Xの下位側の16ビツトだけをセーブ
し、かつCTを8だけデイクレメントすることに
よつて、8ビツトが出力される。 (b) 復号器動作の詳細な説明 INITDEC(第39図および第40図)が復号
器を初期化する。復号器がハードウエアに最適な
もの(H)、ソフトウエアに最適なもの(S)の
何れに関連するかに応じて、INITDECの2つの
バージヨンがインプリメントされている。テーブ
ルがセツトアツプされた後、符号器の場合のよう
にすべての状態が初期化される。Xの初期化は圧
縮済データのバツフアからである。しかしなが
ら、Aの大きさは、符号器にマツチするように初
期化されることを述べておく。どちらのバージヨ
ンも、圧縮済データの新しいバツフアを獲得する
ことから始まる。これは、BPSTとLENの初期
化を想定している。BEは圧縮済バツフアの終端
に向けられ、かつBPはバツフアの先頭を指すよ
うに初期化される。「バージヨン間の違いは、X、
A、およびAMINの初期設定において現れる。
ハードウエア・バージヨンについては、レンジA
が“4000”に、AMINが“4000”にそれぞれ初
期設定される。ソフトウエア・バージヨンでは、
これらの数は負になる。INITDEC−Hでは、最
初の2バイトがビツト31〜16に配置される。
初期化の便宜を図つて、圧縮済データ・ストリー
ムの先頭の2ビツトは0であると規定されてい
る。この結果、初期化の際に、コード・バイトと
Xレジスタのバイトのバイト位置合せが簡単にな
る。第1のバイトが位置31〜24へシフトされ、か
つポインタBPがGETBYTE(第49図)にてイ
ンクレメントされると、第2のバイトがビツト2
3〜16へ加算される。先頭バイトは“FF”に
ならないよう保証されており、テストの必要はな
い。復号プロセスはXCの中のビツト、つまりX
の高位の2バイト(ビツト31〜16)に注意す
るだけである。BYTEINを用いて、第3のバイ
トがビツト15〜8に配置される。(ただし、こ
れは、第2のバイトが“FF”でなかつたときの
話である。2のバイトが“FF”だつたならば、
第3のバイトはビツト16〜7へ加算される。)
BYTEINは、新しいバイトが必要になつたとき
を表示するフラグをセツトする。ソフトウエア・
バージヨンのINITDEC−S(第40図)は、XC
の中で“C000”であるAを0から引くことから
始まる。最初の2バイトはこの開始点に加算され
る。BYTEINは、第3のバイトの関係する加算
とフラグのセツトに使われる。 DECODE(第41図)は、MPSが1か0かに
応じてとられる2つのパスを示す。 DECODEMPS1(第42図、第43図)は、
MPS=1のときの復号の2つのインプレメンテ
ーシヨンを示す。ハードウエア・バージヨンで
は、負であるQ0(S)がXCに加算される。結果
が0以上ならば、MPSパスが続く。YNが1にセ
ツトされるとともに、負であるQ0(S)を加算す
ることによつてAが減少させられる。Aが
AMIN未満であるためにMPSパス上でAの再正
規化が必要ならば、UPDATEMPSにおいてQ0
(S)の大きさも減らされる。LPSパスでは、
YNが0にセツトされるとともに、負のQ0(S)
を引くことによつてXCが回復され、さらにAは
Q0(S)の負数にセツトされる。LPSパスでは再
正規化が常に求められ、Q0(S)の大きさは
UPDATELPSにて増加される。第43図のソフ
トウエア・バージヨンでは、XCをAと比較する
前に、負であるQ0(S)を引くことによつてAの
大きさを減らしている。Aは負のMPSレンジを
持つ。XCがA以上ならば、LPSが復号される。
そうでない場合は、MPSが復号される。LPSが
復号される場合、ソフトウエア・バージヨンは、
負のMPSレンジAを引くことによつて、XCを増
加させる。MPSパスでは、AとAMINの両方が
負なので、AがAMINより大きいことはAの大
きさ(絶対値)がAMINの大きさ(絶対値)よ
り小さく、再正規化が必要であることを示す。 DECODEMPS0(第44図、第45図)は、
MPS=0なるパスについて、第42図および第
43図と同じ操作を示す。この場合、Q0は正で
ある。 RENORMD(第46図、第47図)は、A値
とX値を一時に1ビツトずつ正規化する。AとX
の両方がシフトされた後、XFLAG、つまりXの
最下位のバイトについて、セツトされているビツ
トの有無がテストされる。そのようなビツトがな
いならば、新しいバイトの獲得に移る。このプロ
セスは、(ハードウエアについては)AがAMIN
未満である限り続き、(ソフトウエアについては)
AがAMINより大きい限り続く。 BYTEIN(第48図)に示されるような新しい
バイトをXに移すプロセスの際、GETBYTE(第
49図)が次のバイトに移る前に、最後のバイト
Bについて、これが“FF”バイトであつたか否
かのテストが行われる。“FF”に続くどのバイト
の先頭のビツトも符号化の際に挿入されたものだ
から、復号の際に適切に考慮しなければならな
い。“FF”があつたならば、XNEW(Xの最下位
の2バイト)が値2にセツトされる。XFLAGに
おいてフラグ・ビツトを1だけシフトするためで
ある。通常2番目に下位のバイトに配置される次
のバイトは、エキストラのビツトの方へ送り出さ
れ、Xに加算される。最後のバイトBが“FF”
でないならば、XNEWの最下位のビツトがセツ
トされるとともに、新しいバイトBがXNEWの
高位のバイトに加算される。 GETBYTE(第49図)は、BPを動かして、
圧縮済データ・バツフアの中の次のバイトをアド
レスする。インクレメントされた後のBPが少な
くともバツフアの終端である場合は、新しいバツ
フアを獲得せねばならず、かつBPを該バツフア
の始端へリセツトしなければならない。必要なら
ば、BPSTとBEは適当に変更されるものと想定
する。 上述のソフトウエア型符号器用のプロシージヤ
は、通常のメインフレーム・コンピユータ、例え
ばIBM(登録商標)3370、あるいはパーソナル・
コンピユータ、例えばIBMPC−XT、PC−AT
においてインプリメント可能である。プロシージ
ヤのインプリメントは、PASCAL等の高級言語
を用いて行うことができる。 ハードウエアの具体例の説明 第50図に示されるように、Qコーダー500
には、2値事象BITINが符号化される度に、符
号器側状態発生器モデル(第1図参照)によりN
ビツトの状態Sが供給される。Qコーダー500
の出力は圧縮済データのバイトである。これら
は、Qデコーダー(第54図参照)に入力される
前に、送信されたり貯蔵されたりする。Qデコー
ダーは、復号器側状態発生器モデルからのNビツ
トの入力状態Sに基づいて、2値事象BITOUT
の論理値を決定する。この復号されたBITOUT
値は、復号器側状態発生器(図示省略)にフイー
ドバツクされる。 Qコーダー/Qデコーダー・システムは、符号
化されるべき2値事象の1つについて、1つのメ
ジヤー・サイクルを営む。タイミングは、エツ
ジ・トリガ型のフリツプ・フロツプおよび単一の
位相クロツク・システムによつて決定される。ク
ロツク・エツジ間の時間は充分長く、したがつて
最悪の場合の伝播の遅延およびセツト・アツプ時
間の要請にかなつている。 ここでは、各メジヤー・サイクルで起ることを
説明する。第50図は、Qコーダー500ブロツ
ク図である。新たなサイクル毎に、Qコーダー5
00には、2値事象値BITINと確率についての
情報の記憶場所を指定する状態Sとが主要な入力
として供給される。サイクルの終りでは、キヤリ
ー・オーバー(C/OVER)出力バツフアから
の出力制御(OUTPUT CONTROL)が、コー
ドストリング(CODESTRING)の16ビツトの
中に準備されたバイトの数が0、1、2の何れで
あるかを指定する。 統計ユニツト502への1つの入力は、Nビツ
トの状態Sである。これは、MPS値
(MPSVAL)および現在の2値判断BITINのた
めのQインデツクスを得るために、条件付け文脈
記憶装置をアドレスするのに用いられる。Qイン
デツクスは一連の整数であり、LPSの確率推定値
セツトのインデツクスである。具体例では、Qイ
ンデツクスは0から29の範囲である。統計ユニツ
ト502は、MPS値とQインデツクスをサイク
ルの早朝に出力する。このため、これらのパラメ
ータを符号器ユニツト504と適応化ユニツト5
06の両方に入力することが可能である。サイク
ルの遅くには、入力Aバス<0>(Aバスの最上
位ビツト)が該サイクルのある期間の間0でなか
つたならば、統計ユニツト502が、状態Sによ
つて指定される場所に新MPS値と新Qインデツ
クスを記憶する。統計ユニツト502の動作は、
符号器と復号器のどちらについても同じである。 適応化ユニツト506も、符号器と復号器の両
方について同じである。このユニツトの動作は第
4表に示されている。同じ機能は離散形論理を使
つて達成できる。 2値事象BITINは、MPS値およびQインデツ
クスとともに符号器ユニツト504に入力され
る。符号器ユニツト504からの出力の1つは、
2進(ブーリアン)信号Aバス<0>、つまりA
バスの最上位ビツトである。これによつて、統計
ユニツト502に対し、Qインデツクスまたは
MPS値を変更するときが知らされる。適応化ユ
ニツト506は、符号器ユニツト504から
“MPSOP”ブーリアン信号を受け取る。これは、
現在の判断がMPS操作か否かを表示する。適応
化ユニツト506の出力は、統計ユニツト502
からの2つの入力についての新たな値になる。統
計ユニツト502は、Aバス<0>がゼロであつ
た場合のみ、新たな値を記憶する。 C/OVER出力バツフア508は、符号器ユ
ニツト504および適応化ユニツト506と同一
のサイクルにおいてキヤリー用のビツト・スタツ
フイングを行う。あるいは、パイプライン式で動
作することもできる。パイプラインの1ユニツト
として、サイクル“n”ではシステムがサイクル
“n−1”の符号器ユニツト504の出力に基づ
いてC/OVER出力バツフア508を機能させ
るというようなサイクルのそれぞれで、フリツ
プ・フロツプが符号器の出力を記憶する。 メジヤー・サイクルには2つのタイプがある。
すなわち、MPS操作とLPS操作であり、それぞ
れMPSOPイコール1、MPSOPイコール0と表
示される。BITIN値とMPS値が同じならばMPS
操作、異なる場合はLPS操作になる。第51図の
BITINとMPS値に従うエクスクルーシブORゲ
ートは、該メジヤー・サイクルについての操作の
タイプを決定する。 1つのサイクルの間に、符号器ユニツト504
は、C/OVER出力バツフア508に対して、
2値キヤリー・アウト値C/OUT、13ビツトの
正規化されていないコード・ストリームC−
UNNORM、およびコード・ストリームをどれ
だけシフトすべきかを示す4ビツトの制御信号
SHIFTAMTを出力する。バツフア508は、
1または2バイトの数および送り出されるバイト
数が0、1、または2の何れであるかを表示する
制御信号を出力する。 統計ユニツト502および適応化ユニツト50
6は、QコーダーとQデコーダーの両方で同一で
ある。 第51図は、符号器ユニツト504の詳細なブ
ロツク図である。ここで論じるタイプの算術符号
化法は、加算とシフトによつて符号を形成する。
加算される数(量)は被加数である。入力Qイン
デツクスは被加数に関連する。Q値
(QVALUE)は、Qインデツクスの数値と一対
一で対応している。ここで、Q値は、ハードウエ
アによるQコーダーの具体例では算術符号化プロ
セスにおける被加数である。符号器ユニツトはQ
値だけを求め、Qインデツクス求めない。この具
体例では、Q値が5ビツトの数であり、かつQ値
は12の有意(signficamt)ビツトに先行する0を
プラスしたものであるから、Qインデツクスを貯
蔵する方が経済的である。また、適応化ユニツト
506にとつてもQインデツクスの方が操作しや
すい。 符号器と復号器のどちらの場合も、Qインデツ
クスをQ値に変換するのはQ論理510である。
変換は、第5表を使つたり、あるいは現在の教科
書に登場する真理値表を用いる組合せ回路を使つ
たりして実行することができる。Q値の最上位ビ
ツトは常に0であり、かつ最下位ビツトは常に1
であることに注意されたい。 Qコーダーは、Aレジスタ528とCレジスタ
534という2つのレジスタを用いる。Cレジス
タは、ソフトウエア・フローチヤートで使われる
Xレジスタと機能的に等価である。第52図はA
レジスタ528の内容を修正するA論理の詳細な
説明図である。入力MPSOPに応じて、Aマルチ
プレクサ(A−MUX)522は、LPS操作
(0)に対応するQ値またはAレジスタ528か
ら引かれるMPS操作(1)に対応するQ値を選
択する。優先順位符号器524は、Aバス上の先
行するゼロの数をカウントし、Aバスの最上位ビ
ツトに1を回復するのに必要なシフト量
SHIFTAMTを生成する。このシフトは、Aレ
ジスタ526にて行われる。最下位側のビツト
は、必要に応じて0が充填される。第6表は、
SHIFTAMTの値をAバスの関数として示す。
ダツシユは、「無視(don”t care)」ビツトで
あることを示す。Aレジスタ528がクロツクさ
れるのはサイクルの遅くであり、すべての値が安
定化した後である。その内容はA減算器529へ
供給される。 コード・ストリームからのシフテイング、特に
Cレジスタ534を介してのシフテイングは、A
レジスタ528によつて次のように制御される。
Aレジスタ528が所与数のビツト位置だけ左へ
シフトする必要があるときは、Cレジスタ534
も同じビツト数だけシフトされる。各メジヤー・
サイクルの始まりにおいて、Aレジスタは正規化
されなければならない。すなわち、Aレジスタの
中の数値は、下限の値以上でなければならない。
上述のように、この条件が満たされないと、Aは
(左へのシフトによつて)再正規化される。(Aは
下限LBに初期設定される。)Aレジスタ528の
シフトが発生するのは、Aレジスタ528に対す
る操作の結果Aレジスタの値が上記下限未満とな
るメジヤー・サイクルにおいてである。下限未満
になつたことは、Aバスの最上位ビツト、つまり
Aバス<0>が0になつたことに基づいて検知さ
れる。 MPS操作では、Q値がAレジスタ528から
引かれ、必要ならば再正規を施した後の差をAレ
ジスタ528に戻す。LPS操作では、正規化され
たQ値がAレジスタ528に置かれる。第52図
では、Q値をAレジスタ528から引く減算がA
減算器のユニツトで行われる。その出力は、Aマ
ルチプレクサと呼ばれる2対1のデータ・セレク
タを通過する。LPSOPでは、Q値がデータ・セ
レクタA−MUX522を通過する。A−MUX
522の出力はAバスと呼ばれる。減算の結果に
よれば、その結果であるAバスの値がLB未満と
なり得る。この例では、LBの値は、Aバス<0
>が0ならば少なくとも1回の再正規化シフトが
起こらざるをえないような値に選択されている。
実際、Aバスが受けなければならない再正規化シ
フトの数は、Aバスの上の(減算の)結果におけ
る先行ゼロの数である。Aバスの再正規化はAシ
フタ526のユニツトで行われる。Aシフタ52
6は、ゼロ充填機能を持つバレル・レフト・シフ
タである。Aバスからシフト・アウトさせるビツ
ト位置の数は、Aバス上の先行するゼロの数に依
存する。Aシフタの制御信号である
SHIFTAMT(シフト量)は、0と12の間の4ビ
ツトの数である。Aバスが再正規化を必要としな
いとき、SHIFTAMTは0であり、Aバスはま
つすぐに通り抜ける。シフタに供給される制御信
号SHIFTAMTは、優先順位符号器524によ
つて決定される。該符号器524は、Aバス上の
先行する0の数を符号化する。MPSOPの際に、
Aマルチプレクサ522は、AレジスタからQ値
を引いた差をAバスに出力する。LPSOPの際、
データ・セレクタA−MUX522はQ値を出力
する。SHIFTAMTの数値は、符号器のCレジ
スタ534の部分も制御するし、C/OVER出
力バツフア508ユニツトの制御信号にもなる。
MPSOPでは、Cレジスタ534とQ値がC加算
器536にて加算され、CバスについてのMPS
結果をもたらす。LPSOPでは、Cマルチプレク
サ(C−MUX)534がCレジスタ532の値
をCバスへ供給する。C/OUTはC/OVER出
力バツフア508のユニツトへも供給される。
(この例のように)Q値のCレジスタ534への
加算は、Aレジスタ528からのQ値の減算と並
行して行い得る。Cバスは、Aバスと同じ
SHIFTAMT(シフト量)だけシフトされなけれ
ばならない。このため、ユニツト優先順位符号器
524の出力SHIFTAMTは、Cシフタへも供
給される。MPSOPサイクルでは、2対1デー
タ、セレクタC−MUXが、CバスをCシフタへ
通過させる。CシスタはAシフタと対をなすもの
であつて、左シフトのバレル・シスタである。C
シフタの出力はCレジスタ534へ送り戻され
る。C−MUXの(シフトされていない)出力
は、C−UNNORMと呼ばれ、SHIFTAMTの
ようにC/OVER出力バツフア508のユニツ
トへ送られる。SHIFTAMTによつて、C/
OVER出力バツフア508のユニツトは、C−
UNNORMの先行ビツトをいくつ取るべきかを
知る。 LPSOPでは、Cレジスタ534への加算は行
われず、シフトが行われるだけである。LPSOP
サイクルでは、C−MUX制御信号がCレジスタ
534自体を選択してCシフタへ送る。そこでC
レジスタの値がSHIFTAMTビツト分の左シフ
トが行われた後、Cレジスタ534に戻る。既述
したように、SHIFTAMTとC−UNNORM(C
−MUXの出力)は、C/OVER出力バツフア5
08のユニツトへも入力される。ここでは、C/
OUTは0でなければならない。なぜなら、Cに
は何も加えられないからである。 適応化ユニツト506の目的は、入力されてく
る0と1の相対的な確率に基づいて、特定の文脈
で用いられる符号化パラメータを調整することで
ある。 説明したコードでは、Aレジスタ528とCレ
ジスタ534の長さがともに13ビツトであり、ビ
ツト位置を0、1、…、12と表わす。ここで、位
置0が最上位、位置12が最下位である。位置0と
1の間に基点(radix point)があるのが好都合
である。そうすると、ビツトA<0>が1なら
ば、Aレジスタの値は1.0以上2.0未満である。LB
の値は1.0である。Q値はすべて1.0未満である
が、そのうちのいくつかは0.5に近い。したがつ
て、Q値のレンジは12の有意ビツトを持つ。ビツ
ト位置C<0>は、直接加えられることがない。
なぜなら、Q値の対応するビツト位置が0である
とわかつているからである。したがつて、C<0
>が変更され得るのは、MPSOPサイクルの際に
キヤリーが持ち込まれたときである。算術符号化
の性質により、どのメジヤー・サイクルの後で
も、コードストリングの値が、現在のAレジスタ
528の値とコードストリングの和を越えて現在
のCレジスタ534の数値を包含することはあり
得ない。したがつて、C<0>からのキヤリー・
アウトが1度生じると、コードストリングの該ビ
ツト位置へ別のキヤリーが来ることはない。第5
3図には、符号器のC論理530のブロツクが示
される。Cマルチプレクサ532への入力
MPSPOPによつて、LPS操作(0)については
Cレジスタ534の内容が選択される一方、
MPS操作(1)については加算器536による
Cレジスタ534の内容とQ値の和が選択され
る。C−MUX532からの13ビツトの出力は、
(再正規化される前の)C/UNNORM信号とし
て出力される。Cバス上の同じデータはCシフタ
538へ入力されるので、サイクルの遅くにおい
てCレジスタ534にクロツクされてしまう前
に、SHIFTMATの分だけシフトされ得る。必
要に応じてシフテイング・プロセスの間に、最下
位側のビツトにはゼロが挿入される。 第54図のQデコーダーには、統計ユニツト6
02、適応化ユニツト604、復号器ユニツト6
06、およびコード・ストリーム中のキヤリーを
アカウントするC/INバツフア608が含まれ
る。要素602,604はQコーダー500にお
いて同様の名前をつけられたユニツトと同一であ
る。第55図は、復号器ユニツト606の詳細を
示す。復号器ユニツト606には、CD論理60
8、Q論理610、およびA論理612が含まれ
る。 第56図には、復号器CD論理が示される。(常
に1である)Q値の最下位ビツトからキヤリー・
インC/INを引いた差は、C/INが0ならば1
となり、C/INが1ならば0となる。したがつ
て、Q値マイナスC/INは、Q値の最下位ビツ
トをC/INの反転値に代えることによつて得ら
れる。CD減算器620において、Q値マイナス
C/INからCDレジスタ624の内容を引いた結
果が正である場合は、MPSが復号されたのであ
つて、その結果はCDバスを経てCDシフタ622
へ送られる。MSPOP信号は1である。そうでな
い場合は、LPSが生起したのであつて、CDレジ
スタ624の内容と加算器626のC/IN出力
の和が、CDマルチプレクサ(CD−MUX)62
8において0であるMPSOPによつて選択され
る。MSPOP信号とMPS値のエクスクルーシブ
ORを求めることによつて、BITOUT値が得られ
る。シフト量SHIFTAMTは、CDレジスタ62
4に貯蔵可能となる前にCDバス値がいくらシフ
トされなければならないかを決定する。シフテイ
ングの間に、最下位側のビツトがインストリング
(INSTRING)の最上位側のビツトによつて充た
される。 実際、CDレジスタ624は、現在区間の底
(下端)に関係する現在のコードを収容する。13
ビツトのQ値(最上位ビツトはゼロ)の上位12ビ
ツトはCD減算器620へ送られる。Q値の最下
位ビツトは、C/INから由来するビツトによつ
て置換される。Q値の最下位ビツトは常に1なの
で、C/INが0である(つまりキヤリーがない)
とき、値が反転されてCD減算器620のための
Q値の最下位ビツトとなるとともに、反転される
ことなくC/IN加算器に直に供給される。この
ように、キヤリーは並列にコード・ストリームに
加算されるとともにQ値から取り除かれ、それか
らQ値がコード値から引かれる。CD減算器62
0からのボロウは、復号されたMPS/LPS判断、
MPSOPである。続いて、MPSOPとMPS値のエ
クスクルーシブORをとることによつて、
BITOVTの値が得られる。第56図は、CDレジ
スタ624のデータ・パスも示す。CDバス<0
>のビツトは直接引かれないけれども、これは存
在しなければならない。なぜなら、シフト操作に
よつて“1”の値がCDバス<0>にシフトする
場合があるからである。A論理回路から得られた
SHIFTAMTは、左シフトを行うCDシフタ62
2の制御入力となる。シフタのための低位側の
「充填」ビツトは、C/IN入力バツフア・ユニツ
トから出力されるバスINSTRINGから由来する。 復号器ユニツト606(第55図)は、
INSTRINGからの12個までのビツトにプラスし
てキヤリー入力C/IN信号を用い、データの圧
縮解除を行う。MPS値とQインデツクス値も、
出力ビツトBITOUTを復号するための入力とし
て必要である。符号器の場合のように、復号器ユ
ニツト606は統計ユニツトにAバス<0>信号
を与える。 算術コード・ストリームからのエスケープ 多くの符号化環境において、算術デコーダから
独立して検出可能なコード・ストリームからのエ
スケープを与えることが望ましい。以下では、符
号器のコード・ストリーム・レジスタXにスペー
サー・ビツト位置を割り当てることに基づくエス
ケープについて論じる。実際、スペーサ・ビツト
を含めることによつて、XXX…ビツトがビツト
位置bbb…によつて識別されるXレジスタの後続
バイト部へシフトされる時間に遅延が生じる。ス
ペーサ・ビツトを含めることにより、Hex“FF”
の後のあるビツト・パターンが不適式なものとな
つて、コード・ストリームからのエスケープと制
御語の挿入が示唆される。(通常、復号に先立つ
て、制御語が制御装置によつて撤回される。)さ
らに、スペーサ・ビツトを用いることによつて、
コード・ストリーム・レジスタの後続バイト部の
中のバイトを越えて2以上のキヤリーがもたらさ
れる可能性がなくなる。 コード・ストリームの部分的に完成された後続
バイトを保持するXレジスタのビツト・パターン
は、現在区間の値を持つ(被加数)レジスタAと
ビツト位置合せがなされる。確率の12ビツト整数
表現のために、符号器レジスタのビツト割当の1
例は次のようになり得る。 X=00000000 0cbbbbbb bbss.xxxx xxxxxxxx A=00000000 00000000 000a.aaaa aaaaaaaa ここで、“0”はゼロのビツトを表わし、Cは
キヤリー・レシーバ・ビツトである。“b”は後
続のバイトが生成される位置のビツトを示す。
“s”はキヤリー伝播を制限するのに必要なスペ
ーサ・ビツトを示す。XはまだXレジスタの中で
展開中の2進小数を表わす。Aレジスタの中の
“a”ビツトのうちの1つは整数ビツトであり、
他は小数ビツトである。先行するコード・バイト
がHex“FF”ならば、ビツト位置付は1ビツトだ
けシフトされる。このため、キヤリー・ビツト
は、後続バイトの充填ビツト位置を占める。この
特別な場合では、 X=00000000 00cbbbbb bbss.xxxx xxxxxxxx となる。ここで、この特別な場合では、“b”ビ
ツトが7個だけ規定されることに注意されたい。 完全に展開されたコード・バイトの除去に続い
て、ビツト位置決めおよび再正規化についての規
則が、2つのレジスタにおける値の上限を指令す
る。すなわち、 X=00000000 00000000 0011.1111 11111111 A=00000000 00000000 0001.1111 11111110 となる。 将来の事象が符号化されても、Xレジスタの値
は、現在のX値と(どのような再正規化フアクタ
が掛け合わされた場合でも)A値の和には及ばな
いことに注意されたい。したがつて、コード・レ
ジスタの上限は、 X=SLL(00000000 00000000 0101.1111
11111101)Nとなる。ここで、Nは再正規化シフ
ト・カウントである。SLLは「左シフト論理」操
作(“shift left logical”operation)を意味す
る。該バイトが完成したときのNは、先行バイト
が“FF”でない場合は8になり、先行バイトが
“FF”である場合は7になる。したがつて、
“FF”の次では、Xレジスタの上限は次のように
なる。 X=00000000 00101111 1111.1110 10000000 X=00000000 00cbbbbb bbss.xxxx xxxxxxxx したがつて、スペーサ・ビツトを2つ含める場
合、Hex“FF”に続くデータ・バイトの最大値は
Hex“BF”になる。ちなみに、スペーサ・ビツト
が1つだけ許容される場合、“FF”バイトの後の
バイトの最大値は“FF”バイトの後のバイトの
最大値は“9F”となる。このように、2以上の
スペーサ・ビツトを設けると、“FF”バイトに続
く不適式な符号が、算術コード・ストリームから
のエスケープをもたらす。 (フローチヤートと第2表、第3表に示されるよ
うに、)AレジスタとXレジスタの位置合せにお
ける2ビツトのシフトによつて、コード・レジス
タから除去すべきバイトがXレジスタのバイト境
界にシフトされる。このシフトによつて、エスケ
ープ・コード構造が変化することはない。 小さなデータ・セツトについてのテスト・シ
ーケンス テスト・フアイルの生成は、2進シーケンスに
かける0の確率が0.1875である乱数発生器を使つ
て行つた。フアイルの中の実際のゼロの数は、予
期した通り、48であつた。Q値は“OAC1”に初
期設定された。これは、2桁シフトされると
“2b04”と表わされる。正のQeは、MPS値が0
であることを示す。 下記第7表に示す符号器テストでは、まず事象
カウンタecが示される。サイクルの終りでのQe
値とYNシンボルとがこれに続く。再正規化の合
計回数を「ビツト」の欄に示している。「コード
バイト」は出力された通りに掲載してある。この
欄に2つのバイトが掲載されていることがある
が、それは新しいバイトと、変更された先行バイ
トを両方示しているのである。 テスト・データを16進数で表示すると次のよう
になる。
EBB7FAFEBFEFD6C7F7FFFDFE7FFBDFF3
FDFFFF97F6F5F7FEB97BDF76E
DD7E7FF このフアイルの場合、符号化されたビツト・カ
ウントは、最終データをフラツシユするためのオ
ーバーヘツドも含めて208である。実際に圧縮さ
れたコード・ストリームは、どちらの符号器のど
の場合も、16進数で表示すると次のようになる。
23CA08826F7E20151C267BA0AB606CD63AA26
E71C197A80A07C0
【表】
【表】
【表】
【表】
【表】
【表】
【表】
【表】
【表】
【表】
【表】
【表】
【表】
【表】
【表】
【表】
【表】
【表】
【表】
【表】
【表】
【表】
【表】
【表】
【表】
【表】
【表】
【表】
【表】
【表】
【表】
【表】
【表】
【表】
【表】
【表】
【表】
【表】
【表】
【表】
【表】
【表】 E 発明の効果 本発明によれば、トラツピングを生じさせやす
い数値であつてもこれを推定確率値Qeの候補と
して選択できるので、Qe値の分析をより均一に
することができ、したがつて符号化の能率を一層
向上させることが可能になるという優れた効果が
得られる。
【図面の簡単な説明】
第1図は、本発明によるQコーダーとQデコー
ダーを含む一般的な算術符号化システムのブロツ
ク図である。第2図は、ハードウエアによる好適
な符号化、同復号によつて1つの区間が2つのセ
グメントに分割される確率数直線の説明図であ
る。第3図は、ソフトウエアによる好適な符号
化、同復号によつて1つの区間が2つのセグメン
トに分割される確率数直線の説明図である。第4
図は、複数の互いに異なる符号器を示すととも
に、その何れもが複数の互いに異なる復号器の何
れと結づけても使用し得ることを説明するための
ブロツク図である。第5図は、データ・ストリー
ムを圧縮符号化する際に用いられる32ビツトのコ
ード・レジスタ(Xレジスタ)におけるビツトの
割当の説明図である。第6図は、圧縮されたデー
タ・ストリームを復号する際に用いられる32ビツ
ト・レジスタにおけるビツトの割当の説明図であ
る。第7図は、確率Qeの更新と被加数の再正規
化の統合を示す説明図である。第8図は、符号化
の際の非能率性を示すグラフである。第9図は、
入力されたqインデツクスからQe値の出力を導
くのに用いられるデーテイング回路に説明図であ
る。第10図は、それぞれが推定確率を持つ複数
個の文脈を示すテーブルである。第11図は、ビ
ツトのストリングが文脈に基づいて解釈される様
子の説明図である。第12図は、単一レート符号
化システムの有限状態機械表現の説明図である。
第13図ないし第49図は、それぞれ、Qコーダ
ー、Qデコーダーの動作を示すフローチヤートで
ある。第50図は、本発明によるハードウエアの
Qコーダーの主要な構成要素を示す一般的なブロ
ツク図である。第51図ないし第53図は、Qコ
ーダーの要素(エレメント)の詳細な説明図であ
る。第54図は、本発明によるハードウエアのQ
デコーダーの主要な構成要素を示す一般的なブロ
ツク図である。第55図および第56図は、Qデ
コーダーの要素の詳細な説明図である。

Claims (1)

  1. 【特許請求の範囲】 1 2値判断事象の系列を符号化する際、新たな
    判断事象が入力される度に、数直線上の直前に識
    別されていた区間に包含されるような新たな区間
    と該区間に含まれる1つの点を識別し、該識別さ
    れた点に対応する数値をもつて入力された判断事
    象の系列を符号化したコード・ストリームとする
    算術符号化システムにおいて、 判断事象のうちの第1の事象の生起確率の推定
    値Qeの候補を予め複数個選択しておき、 上記新たな区間を識別するステツプでは、上記
    複数個の候補のうちの1つをQeの現在値として
    用いて、区間の長さと関連づけられた数値Aを、
    新たに入力された判断事象が上記第1の事象であ
    るかそれとも第2の事象であるかに応じて異なる
    けれどもそれぞれQeの現在値に関連する数値に
    更新し、 数値Aが所定値AMINより小さくなると、該
    数値AをAMIN以上の数値になるように2m(mは
    正の整数)倍して再正規化し、 上記再正規化が上記第1の事象の入力に起因し
    て起きた場合は、上記Qeの現在値を上記複数個
    の候補の中の今よりも大きな数値に更新し、 上記再正規化が上記第2の事象の入力に起因し
    て起きた場合は、上記Qeの現在値を上記複数個
    の候補の中の今よりも小さな数値に更新し、 上記Qeの現在値がAMIN/2n(nは正の整数)
    またはこれに近似する値であるときに上記第1の
    事象の入力に起因して再正規化が起きた場合は、
    新たなQeの現在値として、該Qeの現在値の更新
    の直後に上記第2の事象に起因する再正規化が起
    きても再び上記Qeの現在値に戻ることのないよ
    う、十分大きな数値を選択する ことを特徴とする算術符号化システムにおける確
    率適応化方法。
JP20200787A 1986-09-15 1987-08-14 算術符号化システムにおける確率適応化方法 Granted JPS6376525A (ja)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US90771486A 1986-09-15 1986-09-15
US907714 1986-09-15

Publications (2)

Publication Number Publication Date
JPS6376525A JPS6376525A (ja) 1988-04-06
JPH0258813B2 true JPH0258813B2 (ja) 1990-12-10

Family

ID=25424528

Family Applications (1)

Application Number Title Priority Date Filing Date
JP20200787A Granted JPS6376525A (ja) 1986-09-15 1987-08-14 算術符号化システムにおける確率適応化方法

Country Status (7)

Country Link
EP (1) EP0260461B1 (ja)
JP (1) JPS6376525A (ja)
AU (1) AU600972B2 (ja)
BR (1) BR8704623A (ja)
CA (1) CA1291821C (ja)
DE (1) DE3751372T2 (ja)
ES (1) ES2074977T3 (ja)

Families Citing this family (14)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2651209B2 (ja) * 1988-08-30 1997-09-10 キヤノン株式会社 画像の符号化方法及び装置
JP2651210B2 (ja) * 1988-08-30 1997-09-10 キヤノン株式会社 画像の符号化方法
JPH0834432B2 (ja) * 1989-01-31 1996-03-29 三菱電機株式会社 符号化装置及び符号化方法
IL91158A (en) * 1989-07-28 1993-01-31 Ibm Israel Method and system for arithmetic coding and decoding
US5764804A (en) * 1993-10-14 1998-06-09 Seiko Epson Corporation Data encoding and decoding system
CA2156889C (en) * 1994-09-30 1999-11-02 Edward L. Schwartz Method and apparatus for encoding and decoding data
GB2306281B (en) * 1994-09-30 1997-10-22 Ricoh Kk nethod for decoding data
JPH08116534A (ja) * 1994-10-18 1996-05-07 Seiko Epson Corp 画像データ符号化装置およびその方法並びに画像データ復号化装置およびその方法
JP3269359B2 (ja) * 1995-11-13 2002-03-25 セイコーエプソン株式会社 データ符号化装置およびその方法ならびにデータ復号化装置およびその方法
US6014133A (en) * 1996-06-14 2000-01-11 Seiko Epson Corporation Data transmitter/receiver apparatus, data transmitter, data receiver, and data compression method
US6327383B2 (en) 1997-01-14 2001-12-04 Seiko Epson Corporation Multi-color image encoding apparatus and method, multi-color image decoding apparatus and method
US6219445B1 (en) 1997-01-14 2001-04-17 Seiko Epson Corporation Multi-color image encoding and/or decoding apparatus containing color order table and the method thereof
JPH11161782A (ja) 1997-11-27 1999-06-18 Seiko Epson Corp カラー画像の符号化方法およびその符号化装置ならびにカラー画像の復号化方法およびその復号化装置
JP6322180B2 (ja) 2015-12-16 2018-05-09 本田技研工業株式会社 テールゲート構造

Family Cites Families (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4467317A (en) * 1981-03-30 1984-08-21 International Business Machines Corporation High-speed arithmetic compression coding using concurrent value updating

Also Published As

Publication number Publication date
EP0260461A2 (en) 1988-03-23
AU7836687A (en) 1988-03-17
CA1291821C (en) 1991-11-05
EP0260461A3 (en) 1990-10-31
JPS6376525A (ja) 1988-04-06
DE3751372D1 (de) 1995-08-03
ES2074977T3 (es) 1995-10-01
AU600972B2 (en) 1990-08-30
DE3751372T2 (de) 1996-02-15
BR8704623A (pt) 1988-04-26
EP0260461B1 (en) 1995-06-28

Similar Documents

Publication Publication Date Title
US4905297A (en) Arithmetic coding encoder and decoder system
US5801650A (en) Decoding apparatus and method
JPH0258812B2 (ja)
US6885319B2 (en) System and method for generating optimally compressed data from a plurality of data compression/decompression engines implementing different data compression algorithms
US6819271B2 (en) Parallel compression and decompression system and method having multiple parallel compression and decompression engines
US5675332A (en) Plural-step chunk-at-a-time decoder for variable-length codes of Huffman type
JP3227292B2 (ja) 符号化装置、符号化方法、復号化装置、復号化方法、符号化復号化装置及び符号化復号化方法
US6798833B2 (en) Video frame compression/decompression hardware system
JPH0258813B2 (ja)
KR100748485B1 (ko) 가변 길이 코드워드 디코더 및 가변 길이 코드워드 디코딩 방법
JPH0253329A (ja) 圧縮符号化方法及び復号方法
JP3684128B2 (ja) 算術符号化/復号化方法ならびに算術符号化/復号化装置
WO1996031008A1 (en) Syntax based arithmetic coding circuit
TWI273779B (en) Method and apparatus for optimized lossless compression using a plurality of coders
JP3748003B2 (ja) 符号化方法及び圧縮/伸長システム
JPH03503707A (ja) 統計的にコード化されたデジタル・データを復号するシステム
JP3801501B2 (ja) 符号化装置及び復号装置及び符号化・復号装置及び符号化方法及び復号方法及び符号化・復号方法及びプログラム
JP3459759B2 (ja) 算術復号化装置
KR100207428B1 (ko) 허프만 코드 변환에 적응적인 고속 가변장 복호화 장치 및 방법
CN1119867C (zh) 可变长译码方法及其装置
JPH09247466A (ja) 符号化装置
JP3247052B2 (ja) 画像データ変換処理方法及び装置
JPH07249995A (ja) データ符号化装置
JP3336537B2 (ja) 符号化装置、復号化装置、符号化・復号化装置及び算術符号化装置
JPH06104769A (ja) ハフマン符号復号装置

Legal Events

Date Code Title Description
EXPY Cancellation because of completion of term
FPAY Renewal fee payment (prs date is renewal date of database)

Free format text: PAYMENT UNTIL: 20071210

Year of fee payment: 17