JPS5885629A - 圧縮符号化システム - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔技術分野〕 本発明は圧縮？効率よく行なうための記号源の適応モデ
ル「ヒに係る。

〔背景技術〕

１−９８１年６月に刊行されたＩ　Ｅ　Ｅ　Ｅ　　Ｔｒ
ａｎａａｃｔｉｏｎｓｏｎ　Ｃｏｍｍｕｎｉｃａｔｉｏ
ｎｓの第２９巻第６号に掲載されているＬａｎｇｄｏｎ
及びＲ１５ｓａｎｅｎの論５ｉ：”Ｃｏｍｐｒｅｓｓｉ
ｏｎｏｆ　Ｂｌａｃｋ−Ｗｈｉｔｅ　Ｉｍａｇｅｓ　Ｗ
ｉｔｈ　Ａｒｉｔｈｍｅ目ＣＣｏｄｉｎｇ″には、モデ
ル及び符号ユニット音別々に備えた圧縮システムが紹介
されている。モデルは記号源の統計的性質？近似するも
のである。各記号はモデル及び符号ユニットへ同時に供
給される。符号ユニットは、モデルによる条件付けに従
って、後続の１以上の記号全符号ｆｌｌＳ″ｒる。

モデルは有限状態機械（以下Ｆ’ＳＭと略称）によって
構成され、それに記号源の統計が与えられる。符号ユニ
ットもＦＳＭである。モデル及び符号ユニットは成る符
号関数？実現させる。ここで云う符号関数と汀、源アル
ファベットにおける各ストリング（源ストリング）？符
号アルファベットにおける対しするストリング（符号ス
トリング）へ写像するものである、計算が複雑にならな
いようにするため、源ストリングが長い場合には、符号
ストリングへの写像は単一のステップでは完了されない
。殆んどの符号関数は、瞬間関数値、源記号及び他の属
性によって次の関数値が決まるという点で帰納的（ｒｅ
ｃｕｒｓｉｖｅ）である。一般に、符号関数は源ストリ
ングの連続する各記号に対して左から右に一連の演算？
遂行することによって実現きれる。ただ踵物理的に実現
可能ならしめるため、帰納的関数は有限記憶？もつもの
が選ばれる。

符号操作及び復号操作は共にＦＳＭで遂行される。ＦＳ
Ｍは、符号操作又は復号操作の各演算の度に、入力？受
取り、出カケ与え１．そして七の内部状態？変える。符
号器は源ストリング中の記号ｔ１つずつ受取り、七れら
に対し可逆変換？行なって符号ス）　ＩＪング？生成す
る。モデル及び符号器は別々のＦＳＭであるから、モデ
ルの状態は符号器の状態から区別できる８ 無損失のデータ圧縮システム？設計する場合、まず源が
モデル比され、次いでこのモデル比された源に対して符
号が案出される。例えば、８ビツトの２値記号即ち「バ
イト」によってストリングが構成される普通のアルファ
ベット？考えてみる。

どのようなシーケンスであっても、２５６種類−（２’
＝２５６）の記号がすべて現われることはめったにない
。記号源の性質にもよるが、普通は４０乃至８０個の少
数の記号が現われるだけである。

従って、内部状態及びメモリ・サイズ？節約することが
できる。

源記号の生起確率が前に生じ友源記号と全く無関係であ
るような源は０仄マルコフ源（記憶のない源）と呼ばれ
る。しかしながら記憶のない源はまれであり、記号間に
何らかの関係があることが多い、これは条件付きの事象
及び確率によって表わされる。より一般的な情報源とし
て、ｎ　ＹＭの区別可能な記号ケ持ち、各記号の生起が
先行するｍ個の記号によって影響ン受けるもの才考える
。

このような源はｍ久マルコフ源と呼ばれ、成る記号が生
起する条件付き確率はｍ個の先行記号によって決まる。

従って、ｍａマルコフ源においては、ｍ＠の先付記号が
そのときの源の状態ケ定めることになる。生起し得る記
号の数ｆｑとすると、ｍ次マルコフ源はｑ　種類の状態
ｒ持っている。例えばｑ＝２５６、ｍ＝２とすると、状
態の数は６５５３６に達する。従って、高次マルコフ源
のモデル比は実際には殆んど不可能であることがわかる
。

前述の論文に開示されているモデル比によれば、「文脈
」が識別される。文脈は、現ベルが与えられると、符号
【ヒされるべき次のベルの条件付き確率分布？識別する
。文脈或いは条件付はクラスという概念は「状態」？一
般比したものである。いずれにしても、分布？決定する
実際の統計量や計数直に大力ベル・ストリームから導出
される。記号源の条件付はクラス或いは文脈については
固定されたモデルが使用され、１つのデータ・バス内の
各文脈における条件性キ確率分布については適しモデル
比が行なわ扛る。

１次マルコフ・モデルの取扱いには様々な方法がある。

例えば１９７４年１１月２６日付のＩＢＭ　　Ｒｅｐｏ
ｒｔ　ＲＣ５１５０に掲載されているＭｏｍｍｅｎｓ　
及びＲａｖｉｖ　（７）”　Ｃｏｄｉｎｇ　Ｆｏｒ　Ｄ
ａｔａＣｏｍｐａｃ　ｔｉ　ｏｎ　”によれば、１次マ
ルコフ・モデルを用いることによって、１つの高次文字
ス）　ＩＪ　−ムが複数の低次又γストリームへ分解さ
れる。これには複数のパスが含まれる。最初のノξスは
、記号ストリームの最初の完全１次マルコフ・モデルの
条件付き確率ケ得るためのものである。状態数は、はぼ
等しい条件付き確率分布？持った同値類ケ作成すること
によって減らされる。次いで、各開鎖類についてモ縮符
号が生成される。ｌＥ縮符号ｒ記号に割当てるためには
２番目のバスが必要である。米国特許第４０９９２５７
号には、固定さｊｕｔ部分１次マルコフ・モデルｒ用い
て、文字？文脈的に符号「ヒする技術が開示されている
。例えば、文字゛Ｌ″が常に小文字である場合、その先
行記号がピリオド、′であれば、そｔ′Ｌは大文字とし
て符号比さ扛る。

〔本発明の概要〕

文脈或いは条件付はクラスの数？増やせば、源記号の統
計に対するモテルの忠実度ｒ向上させられることは知ら
れていたが、本発明者は、２レベルの適応モテルが記号
源（７ｐ　完全１　次−ｒルコ７　侭モデル？十分に近
似し得ること？見出した。第１ンベ次で汀、条件付は文
脈自体が適応方式で生成される。第２・ノベルでは、選
択された各条件付は文脈について、ストリングの符号「
ヒ時に記号統計が適応方式で決定される。予め決めらｎ
ている特徴は、条件付は状態の最大数だけである。各状
態は次記号のための確率分布に対しする。この確率分布
は当該状態にのみ依存している。状態の選択は、次のよ
うにして１つのバスで行なわれる。まず、条件付はケ目
的として、すべての記号が単一の「団塊」状態に割当て
られ、次いで選択基準に満たすことの結果として、生起
頻度の高い記号又はそのストリングが付加的な条件付は
状態として加えられる。成る状態が作り出されると直ち
に、条件付は状態に従属する確率分布ケ決定するための
第２の適応プロセス？開始することができる。状態従属
確率のインディケータは必要なときに符号ユニットへ送
らｎる。

より具体的に云うと、本発明にテータ王縮のために予め
選択された帰大数の状態？用いて、臓欠マルコフ源の適
応モデル１６フ行なう。その際のステップとして、（１
）予め選択された回数Ｍだけ生じる最初のに一１岡の記
号が確定され（パラメータｋｆｆアルファベット・サイ
ズＮ？超えない）　、（２）ｋ−１＠の異なった記号及
び団塊状態によって形成されるｋ　ｆｌｆｆｉの状態の
各々が次記号と対にされ且つそれに関連する条件付＠確
率分布が決定され、そして（３）この分布７表わすパラ
メータが外部の王縮符号比プロセスに与えられる。

明らかに、本発明に従う二重適応に、完全１次モデルで
必要な記憶よりも少ない記憶で、単一バス圧縮及び部分
１次モデル比？可能にする。もしＮ＠の記号の１次モデ
ルがｎＸｎ個の確率？保持できる大きさのテーブルｒ必
要とするのであれば、本発明は１ｃｘｎしか必要としな
い。例えば、各記号が８ビツト（１バイト）である源は
２５６種類の記号ｒ発生し得るが、区別町ｑｒな記号７
４９種類しか持っていなければｎ＝２５６、ｋ＝５０と
なり、従ってｋＸｎは１２８００であるが、ｎ×ｎば６
５５３６に達する。

本発明の特長は、ｋの値ｒ固定し、ｋ−１個の１最も有
用な」文字？見２けてそれらン状態（５２″脈）として
働かせることにある。ｋ番目の状態は、残りすべての文
字が−固まりになっている状態（団塊状態）である。あ
とで説明する特殊なラン状態のために、幾つかの付加的
な状態ｒ利用してもよい。

成る状態が「有用」であるというために汀、その状態は
頻繁に生起しなければならず、更に矢記号のための゛ス
キューされた”条件付き確率分布？持っていなければな
らない。この後者の要求は、次記号に対して低い条件付
きエントロビーン与える。これら２つの要求は競合する
かも知れないが、実験によれば、１次マルコフ・モデル
？用いて圧縮７行える場合には、般も頻繁に生じる記号
はまた低い条件付きエントロピー？持つ傾向がある。

「記号」及び「状態」という用語は幾つかの意味で使用
さｎる。まず記号はモテルの状態？選択する。少なくと
も記号は団塊状態の一員である。

次に、記号は自身の権利ｒ持った符号比目的物である。

記号のこの役割７表わ丁ため、「仄」記号という用語ｒ
使用することがある。また、選択された記号によって決
まる状態にｉいて記号が生起する、ともいう。

〔実施例の説明〕

Ａ、＠論的考察 モデルは構造及び１組の確率パラメータから成る。構造
は有限個の文脈によって定義さｎる。アルファベラ）Ｓ
における記号のすべての有限ストリングａ＝ｘ　（１）
、ｘ（２）・・・・・・の集合は文脈或いは条件付はク
ラスへ分割される。「文脈」という考え方は「状態」？
一般比したものである。

各ス）　ＩＪングＳ？その文脈ｖ　＝　ｆ　（ｓ　）へ
写像する一般帰納的関数ｆが存在する。各文脈２に関連
する確率パラメータの集合ｉ［（ｉ／ｚ）］で表わすこ
とにする。この集合に含丑れる各確率パラメータは０は
上の（直？持っており、それらｒ合計すると１になる。

これらのパラメータは集合的に「統計」と呼ばれる。文
脈ｚ＝ｆ（ｓ）が与えられると、ストリングＳに続く記
号がｉである条件付き確率Ｐ（−ｉ／ｆ　（ａ　）　）
がモデル統計関数によって割当てられる。文脈の集合、
より正確には一般帰納的関数（構造関数）ｆは、Ｐ（ｉ
／ｆ（ｓ））が文脈ｆ（３）及び記号ｉにのみ依存して
いれば、集合（Ｐ（ｉ／ｚ））と共に、定常モデル？定
義する。

文脈２において生じるストリン１グＳの相次ぐ記号ｗ　
ｓ　Ｃｚ　］で表わす。適応関数アルファは、ストリン
グ８における文脈２の過去の記゛号生起に基いて条件付
き確率Ｐ（ｉ／ｚ、ｓ［ｚ　］　）′＋ｒ生成する。

適応統計：アルファ：（１、ｓ、ｒ（ｓ））Ｐ（ｉ／ｚ
、ｓ［ｚ］） この定式比は２ステツプのプロセスである。第１ステツ
プでは、各記号について文脈２？決定するモデル構造関
数ｆが評価される。第２ステツプでに、記号ｉ及びその
文脈における過去の状態について条件付き確率Ｐ（ｉ／
ｚ、ｓ［ｚ〕）ｋ決定するモデル統計関数が評価される
。モデル統計関数のための適応は先行ストリング８から
の情報？含む。殆んどの場合、アルファは記号の相対的
生起頻度？決定するための計数機構ン含む。ストリング
がピッ）１１位であれば、適し統計ン二者択一式に変え
てもよい。

上述の如き適応の定式ｒヒにおいては、各文脈は独立記
号源として扱われる。２以外の文脈に生じた過去の記号
は、−において条件付けられる確率の割当てに影響？及
ぼさない。

定常モデル及び適応統計モデルのいずれにおいても、確
率の総数ｋ（ｎ−１）はモデルの複雑さ會示す。ｋは文
脈の数、ｎは区別可能な記号σ）数である。明らかに、
モデルの複雑さというのは、符号ストリングが処理され
るときに符号器及び復号器が共にアクセスしなければな
らない作業テーブルの大きさに関係する。この情報は、
各々がｎ−１個のワード（符号比パラメータン含む）か
ら成るに飼のサブテーブルへ組織比されるものと考えて
よく、これ１で考察してきた定常モデル及び適応モデル
の複雑さは、アルファベット及び文脈の集合の濃度に関
係する。これは源記号ストリングから独立している。構
造関数ｆはＦＳＭ（有限状態“機械）によって実施され
得る。その場合は、状態と文脈とデ区別するのが望捷し
い。しかしながら、モデルの複雑さは、ＦＳＭの内部状
態の数より少ないこともある条件付は文脈の数に依存す
る。

Ｂ、　５ｃ脈の適応 以前は、適応というの１１常に条件付き確率Ｐ（１／ｚ
、ｓ［ｚ〕）の推定に限られていた。これは統計関数の
一般（’Ｃと考えられる。

各記号が１バイト幅である源記号アルファベット（７’
３１　次？　／Ｉ／コフ・モデルは２５６種類の条件付
は状態？持っている。任意のストリングに生じ得る文脈
め数にはｋ＜２５６に制限される。云い換えれば、ｋは
モデル構造関数ｆの範囲の濃度である。ストリングが符
号ｆヒされるときに、最大に個の「最良」又脈７決定す
ることができる。これは、モデルの実質的な複雑さが１
（（ｎ−１）であることケ意味する。完全１次マルコフ
・モデルσ）場合はｎ（ｎ−１）である。

バイトの各１直は、深さが８の完全に平衡１ヒされ几２
進樹における葉と考えることができる０各′ゝイト直に
対し、根から対しする葉に至る一意的な経路が存在する
、ｉ番目のビットの（直はｉ番目の「枝」？選択する。

所与のバイトによって定められた経路？根のところから
たどっていけば、各々の内部節？通過するときに対応す
る枝の計数値の保持及び更新が０Ｔ能である。ＦＳＭ７
構成するため、内部節は状態に対応させられ゛る。１９
７５年にＡｄｄｉ　５ｏｎ−Ｗｅｓｌｅｙ　　社から出
版されｆｃＤ、Ｋｎｕｔｈの”　Ｔｈｅ　Ａｒｔ　ｏｆ
　Ｃｏｍｐｕｔｅｒ　Ｐｒｏｇｒａｍｍｉｎｇ　ｓ。

Ｖｏｌ、　１、Ｆｕｎｄａｍｅｎｔａｌ　Ａｌｇｏｒｉ
ｔｈｍｓ　（第２版）に記載されているように、成る節
への経路はその節のアトＶス？定め、その子アドレスは
、一方の子について族アドレス７倍にし、他方の子につ
いて倍の親アトＶスン１だけ増すことによって与えられ
る。各ビットの統計は、２つの成分から成る連合文脈上
で条件付けられる。第１の成分は、文脈或いは条件付は
クラス７表わす構造関数ｆによって決定される、各文脈
２に対応するワード・サブテーブルが存在する。第２の
成分は、深さが８の２進樹の内部節である。節はバイト
内のビット位置及びそれまでのビットの値に一意的に対
応する。かくして、２進事象が条件付けられる総合文脈
は、適応式に決定された記号文脈２及び処理されている
バイトの接頭部から成る。

文脈上の各２進記号の統計を更新し維持する友め、ス）
　Ｉ／ソング中各２進記号についイ２つのカる。小さい
方のカラン）ｃ（Ｌ／ａ）の直？制御すると都合がよい
。確率が小さい記号ｉＬで表わし、確率が大きい記号ｗ
　Ｌ　ｌで表わすことにする。

もし反対の記号Ｌ′が観測されると、大きい方のカラン
）ｃ（Ｌ’／ｓ）が１だけ更新されて、カワントｃ　（
Ｌ’　／ｓ、　　Ｌ’　　）が生成される。３．Ｌ′は
、ス）　ＩＪングＳに連結される記号Ｌ′に意味する。

小さい方のカウントは１の１まである。もし次の記号が
Ｌであれば、ｃ（Ｌ／ｓＬ）は更新されない。その□代
り、この同じ比はｃ（Ｌ’ｓＬ）デ半分にすることによ
って得られる。それによってｅ（Ｌ’／ａＬ）が１より
も小さくなると、その直は１に丸められ、そして記号り
及びＬ′の役割が切替えられる。最後に、遍心統計関数
アルファは、大きい方のカラ７）ｃ（Ｌ’／ｓ）ｙスキ
ュー数Ｋ（Ｂ）としてまとめる。スキュー数はモデル・
ユニットの第２ステージから出力されて符号器へ供給さ
れる整数の制御パラメータである。

こｎは、１９８１年４月に発行されたＩＢＭＴｅｃｈｎ
ｉｃａｌ　Ｄｉｓｃｌｏｓｕｒｅ　Ｂｕｌｌｅｔｉｎ　
　第２３巻Ｎ第１１号の第５１１２〜５１１’４ｍに掲
載されているＨｅ１ｍａｎ他の−Ａｒｉｔｈｍｅｔｉｃ
　ＣｏｍｐｒｅｓｓｉｏｎＣｏｄｅ　Ｃｏｎｔｒｏｌ　
Ｐａｒａｍｅｔｅｒ　ＡｐｐｒｏｘＩｍａ目ｏｎ”に記
載されている。スキュー数はカラン″Ｆｃ（Ｌ’／８）
の対数に比例して増加する。例えば、カウント１はスキ
ュー数１？与え、カウント２及び３はスキュー数２ヶ与
え、カウント４．５．６及び７けスキュー数３に与える
。適応策は推定された比ｃ（Ｌ／ｓ）／（ｃ（Ｌ／ｓ）
＋ｃ（Ｌ’／５））−Ｋ（ｓ） ？特別の確率２　　　で近似し、符号比されるべき記号
の統計？スキュー（Ｌ（ａ　）、Ｋ（ｓ））の形で与え
る。

Ｃ，ラン・モード 記号が繰返すか否かの事象？記述するため牟−スキュー
？用いてランｒ符号ｔＥする場合には、そのための文脈
？定義する必要がある。成る記号が連続してｒ回生じた
ときにはラン・七−ドｒ定めてよい。ｒの代表的な饋は
３である。符号ｒヒされた最後の３つの記号が同じ圃７
持っているとラン・モードに入り、符号ｒヒされる次の
事象はランの「継続」又は「停止」？示す。「継続」事
象が符号ｆヒされ２と、最後の１個の記号は同じ値？持
っており、次の事象はラン・モードのもとで生じる。

カラン）ｃ（Ｌ’／ｓ）はその度に更新される。

ラン・モードのための符号比プロセスは、「停止」事象
が符号比されるまで、記号の各繰返しの間続けられる。

「停止」事象後は、ラン・カワントＣ（Ｌ’／ｓ）は早
発にされ、欠いて記号モードに入る。ラン會停正させた
記号に、前のラン記号の文脈のもとて符号比される。

ラン・モードへＱ〕入り方及び記号の各繰返し會符号比
する方法は前述のとおりであるが、ラン・モードにおい
ては、カワントｃ（Ｌ’／ｓ）の場所？示す必要がある
。例えば、符号比パラメータ・テーブルのアドレスが８
ビツトであれば、２５６個のワードが使用される。ただ
し、テーブルのワード０は不使用でもよい。従って、各
記号文脈のためのサブテーブルにおける予備ワード７ラ
ン・モードに割当てることができる。そのため、記号モ
ードにおいてげ、ワード１から始まる２５５飼のワード
のうち内部節に対６するワードがアドレス指定される。

前に述べたアドレス指定倍にする技法は、２進樹の節？
下っていくのに用いられる。ラン−モードにおいてはテ
ーブルのワードＯがアドレス指定される。

Ｄ、構成 本発明に従う圧縮サブシステムの構成？第１図に示す。

記号は源２から発生され、モデル構造ユニット１及び符
号ユニット１７へ同時に供給される。モデル構造ユニッ
ト１は受取った記号からその条件付は状態ケ決定する。

この情報は記号と共に適応統計ユニット３へ送られる。

適応統計ユニット３は各状態についての統計（条件付き
確率分布）ｒビット単位での適応性ｒもって維持する。

記号は、１９８０年１１月に発行さ、ｐたＩＢＭＴｅｃ
ｈｎｉｃａｌ　Ｄｉａｅｌｏｓｕｒｅ　Ｂｕｌｌｅｔｉ
ｎ第２３巻、第６号の第２５２８〜２５２９頁に掲載さ
れているＬａｎｇｄｏｎ　他の”Ｄｅｂｌｏｃｋｉｎｇ
　Ｍｅｔｈｏｄ　ＦｏｒＵａｅ　　Ｗｉｔｈ　　Ａｎ　
　Ａｄａｐｔｉｖｅ　　Ａｒｉｔｈｍｅｔｉｃ　　ｇｎ
ｃｏｄｅｒ／Ｄｅｃｏｄｅｒ”に記載の如き線形ｆヒさ
れた樹構造によって１ビツトずつ符号イヒされる。

この樹構造は、前述のＨｅ　１ｍａｎ他の論文に述べら
れている適応スキュー情報？与える。樹構造のエン）　
ＩＪけ、確率の大きい記号Ｌ′についてのカウント・フ
ィールドｃ（Ｌ’／ｓ）及びＬ／Ｉ直７表わ丁ビットか
ら成る。カウント・フィールドの先頭の、ビット〕の位
置がスキュー直ｒ示す。符号ｆヒされるべき記号中のビ
ット直はＬ直と比較され、それによりバス１５へ信号Ｉ
　５ＬＰＳが出力されて符号ユニット１７へ供給される
。符号ユニット１７は、米国特許第４２８６２５６号の
方法に従って、ピッ）ｋ符号ストリームの作業端へ〜符
号比し、その結果の可変長ストリングＶＬＳ（バス２１
）？ストローブ直（バス１９）、桁上ケ（ハス２３）及
びシフト量（バス２５）と共に可変長−固定長変換バッ
ファ２７へ供給する。バッファ２７は、符号比されたス
トリングケブロック比するための論ａｈ含んでいるのが
好ましい。桁上げは例えば特願昭５５−６０７６８号の
明細書に記載の如くに制御される。

第２図は、第１適応ステージ即ちモデル構造ユニット１
の一構成例７示したものである。カワント・テーブル３
５は異なった記号饋毎に１つのワード（全部で２５６）
？含み、圧縮のための条件付は文脈ｒ決定するのに使用
される。既に述べたように、第１図の適し統計ユニット
３は各条件付は文脈に対応する条件付き確率分布ｒ保持
している。しかしながら、モデル構造ユニット１は条件
付は状態ｒ識別するパラメータｒ′４し統計ユニット３
へ送らなければなら−ない。現記号に続く記号？符号「
ヒするための状態は、カウント・チー７−ル３５ｒアト
Ｖス指定する記号直によって決定される。

カウント・テーブル３５の各ワードはカウント・フィー
ルド及び状態フィールド忙含む。カウント・フィールド
は、当該アドレスに対応する記号の生起カランｌ”ｒ表
わす。状態フィールドは記号のための状態指示子？含む
。ワードが読暇られるとき、これらのフィールドはカウ
ント・Ｖラスタ４５及び状態レジスタ４３へ各々ロード
される。

カウント・Ｖラスタ４５は並列ロード形のレジスタで、
カウント直の増分がｏ［Ｑである。カウント・フィール
ドは、よりポピユラーな記号ｒ決定するために記号例ｒ
カウントするのに用いられる。

前述の団塊状態ば“０″の状態指示子ｒ持っており、す
べての記号は最初にこの状態で圧縮される。

状態はポピユラーな記号に指示子ｒ割当てることによっ
て作り出される。圧縮されるべき各記号はカウント・テ
ーブル３５ケアクセスするのに用いられる。カウント・
Ｖラスタ４５へ読出された饋は増分されたｖｔｔ、Ｎレ
ジスタ４９にあるシステム制御パラメータＮ（例えば５
０）と比較される。

両者が等しいことが比較器５１で検出さ九ると、割当て
Ｖジスタロ１から次に使用可ｑ目な未割当ての状態指示
子が割当てられる。割当てＶジスタロ１は″１＃に初期
設定される。これに、選択された条件付は記号に割当て
られるべ＠仄の状態指示子である。記号のための状態指
示子は、カウント・テーブル６５から読出された値であ
る。カウントの増分及び割当てＶジスタロ１からの新し
い指示子の選択に続いて、新しいカウント及び状態指示
子がカウント・テーブル３５に書戻される。

新しい東件付は状態の作成に続いて割当てＶジスタロ１
が増分される。割当てＶジスタロ１が許容可能な条件付
は状態の最大数ン越えて増分されると、カウント及び割
当て機構に減勢される。カウント・テーブル３５中の状
態指示子或、その時点から記号シーケンスの終りまで、
そのままに保たれる。代替策として、カウント及び割当
て機構ケ例えば４０００バイト毎に再初期設定するよう
にしてもよい。

次ニ、ラン・モードについて考察する。新しい記号が記
号レジスタ３３に書込まれるときは、前の記号値は前記
号Ｖジスタ３４に書込まれる。現記号及び前記号は比較
器３６て比較され、もし跡しければラン・カウント・レ
ジスタ５８が増分さｎる。この増分された値は、比較器
４０で所定の値ｒ（例えば５）と比較され、もしｒｔｌ
上であればラン・モードに入る。ラン・モードに入ると
、記号レジスタ３３にあってラン・モードへＣ〕切替え
ケ行わせた記号に続く記号のところから、符号比された
ラン事象が開始する。

記褥の新しいＩｔｆｆｌ記号サイクルの開始時に到着す
る。これは適応統計ユニット３グ〕方へ送られる。

この記号は、前の記号によって決定された状態指示子或
いに文脈のもとて符号ｆヒされる。記号レジスタ３３に
あった前の１直に、現記号のための状態？決定するため
に力うント・テーブル３５ンアクセスするのに使用され
ている。ラン・モート°についての条件が満足されると
、記号モードからの切替えが行われる。しかしながら、
適し統計ユニット５はランのスキューのために、なおり
ラント・テーブル３５のワードＯｒ使用する。

適し統計ユニット３で汀、モデル構造ユニット１の各記
号サイクル毎に８サイクルが必要である。

即ち、８ピツ′１の記号の各ビット毎に１サイクル−１
ｉｔトラｎる。ラン・モードにおいてに、適応統計ユニ
ット３け、比較器３６からバス１１土に一致信号が発生
さ：ｎ、ると１サイクルしかとらず、発生されなければ
９サイクルとる。後者の場合、最初のサイクルはランの
終りケ示し、残り８サイクルで、ラン？停止ｇ−ｔｒた
記号の値が符号「ヒされる。

モデル構造ユニット１け記号レジスタ３３にある記号？
バス５ヶ介して適応統計ユニット３へ送る。バス９は比
較器４０からのラン状態情報？送り、バス７に状態レジ
スタ４３の内容（次が非ラン状態であること？示す）？
送る。カウント・テーブル６５には論理要素５７の出力
が書戻される。

−論理要素５７ば、マルチプレクサ（ＭＵＸ）５３ケ介
して供給される４ビツトの状ｑｖレジスタ３及び割当て
レジスタ６１の内容と６ビツトのカウント−レジスタ４
５の内容とｒ連結して、１０ビツトの更新されたワード
ｒバス５９へ出力する。

第６図は伸張サブシステムの一構成例ケ示したものであ
る。バス２９及び３１７介して受嘔られた符号ストリン
グは固定長−可変長変換バツファ７５に累積される。バ
ッファ７５は圧縮された符号ス）　Ｉ）ングの作業端を
復号ユニット７９に供給する。復号ユニット７９は遍心
統計ユニット８１からのビット毎のスキューも受取る。

遍心統計ユニット８１に、復号されるべき次の記号の状
態ｒ決定するモデル構造ユニット８３からの状態指示子
７使用する。各サブサイクルにおいて復号ユニット７９
σ別のピッ）？復号する。記号モートノ場合、８（２）
のビットが復号される度に、適応統計ユニット８１で使
用される条件付は状態が変１ヒされる。

モデル構造ユニット中で実施される本発明は、記号モー
ド又はラン・モードの表示？辱え、どの２５６ワード・
サブテーブルが適応統計ユニットによって使用されるか
ン指示する。記号モードにおいては、適応統計ユニット
は指示されたサブテーブル？用いて処理ケ進め、前述Ｌ
ニア）ようにして各サブテーブル・ワードン検索し、更
新する。サブテーブル・ワードけ、子線符号器へ送られ
るスキュー（Ｌ（ａ　）、Ｋ（ｓ））ン決定するＣ）に
用いられる。ラン・モードにおいては、適旧統計ユニッ
トは指示されたサブテーブルのワード０を検索し、更新
する。

本発明は、パラメータの制御のもとに事象を符号ｆヒす
るどのような子線符号器でも実施可能である。−例とし
て、１９７８年１１月に発行されたＩ　Ｅ　Ｅ　ＥＴｒ
ａｎａａｃ口ｏｎｓ　ｏｎ　ＩｎｆｏｒｍａｔｉｏｎＴ
ｈｅｏｒｙの第６７１〜６７３頁に掲載されているＧａ
ｌｌａｇｅｒＩ７）”　Ｖａｒｉａｔｉｏｎｓ　ｏｎ　
ａ　Ｔｈｅｍｅ　ｂｙＨｕ　ｆ　ｆｍａｎ”に記載の如
き適応ハフマン符号ユニットを挙げておく。復号は、符
号器側のものと同じ適応統計ユニットから供給される符
号パラメータを用いて、事象毎に実行される。上記の論
文によれば、符号パラメータは一組の符号ワードから成
シ、同じ２ステツプ＝プロセスによつそ決定サレる。即
ち、構造関数ｆが各バイトを文脈ｆ（８）に及び記号モ
ード又はラン・モ）−ドに割当て、次いで統計関数アル
ファが符号パラメータを決定するために適切なサブテー
ブルをアクセスシ、更新する。

既に述べたように、本発明は予め決められた統もポピユ
ラーな記号を用いることにより、効率のよい圧縮が達成
される。更に、本発明に従えばデ、−夕を１回通過させ
るだけでよい。これは前述の如き二重適応にもかかわら
すｐｌ［である。二重適応とは、モデル構造ユニット及
び適巴統計ユニットの適応を意味する。１０ち、（１）
モデル適らユニットはポピユラーな記号を条件性は文脈
として選択し使用することによって適応し、ｒ２＋　適
Ｇｆ＆　計ユニットは各ビット毎のスキュー数に適しす
る。

【図面の簡単な説明】

第１図は本発明を実施し得る子細システムのブロック図
、第２図はモデル構造ユニットの詳細を示すブロック図
、第３図は伸張サブシステムのブロック図である。 出願人インタ慴ル・ヒ谷ス・マシ叩ンズ・コ刊セーカン
代理人　弁理士　　頓　　　宮　　　孝　　　−（外１
名）

Claims (1)

【特許請求の範囲】
1. Ｎ種類の記号音発生し得る記号源と、該記号源から記号
   ？受取って圧縮符号ｒヒのための制御パラメータ？生成
   する適応手段と、該適応手段からの制御パラメータに従
   って前記記号源からの記号？圧縮符号比する符号「上手
   投と？具備し、前記適応手段は所定回数だけ生じる最初
   のに−１（＜Ｎ）個の記号？確定して、該に一１個の記
   号によって決まるに一１ｆ［ｉｉｌの状態と残りの記号
   に共通の１個の状態とから成るｋｉｌｌの状態の各々を
   各記号と対にして関連する条件付き記号確率分布？決定
   し、該分布７表わすパラメータ？前記制御パラメータと
   して前記符号「上手投へ供給することｒ特徴とする圧縮
   符号比システム。