JPH07123228B2 - 桁上げ制御を用いた適応符号化装置及びその方法 - Google Patents
桁上げ制御を用いた適応符号化装置及びその方法Info
- Publication number
- JPH07123228B2 JPH07123228B2 JP3038954A JP3895491A JPH07123228B2 JP H07123228 B2 JPH07123228 B2 JP H07123228B2 JP 3038954 A JP3038954 A JP 3038954A JP 3895491 A JP3895491 A JP 3895491A JP H07123228 B2 JPH07123228 B2 JP H07123228B2
- Authority
- JP
- Japan
- Prior art keywords
- signal
- carry
- supplying
- indicator
- input signal
- 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 - Lifetime
Links
Classifications
-
- H—ELECTRICITY
- H03—ELECTRONIC CIRCUITRY
- H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
- H03M7/00—Conversion 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/02—Conversion to or from weighted codes, i.e. the weight given to a digit depending on the position of the digit within the block or code word
- H03M7/12—Conversion to or from weighted codes, i.e. the weight given to a digit depending on the position of the digit within the block or code word having two radices, e.g. binary-coded-decimal code
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G06T9/00—Image coding
- G06T9/005—Statistical coding, e.g. Huffman, run length coding
-
- H—ELECTRICITY
- H03—ELECTRONIC CIRCUITRY
- H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
- H03M7/00—Conversion 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/30—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
- H03M7/40—Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code
- H03M7/4006—Conversion to or from arithmetic code
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)
Description
【０００１】
【産業上の利用分野】本発明は、信号の符号化における
桁上げの制御に関し、特に、算術エントロピー符号化に
おける桁上げの制御に関する。
桁上げの制御に関し、特に、算術エントロピー符号化に
おける桁上げの制御に関する。
【０００２】
【従来の技術】高次及び低次の２進数ストリングを結合
する際に行う桁上げ制御は周知である。例えば算術符号
化及び復号化に用いられる従来の桁上げ技術は、米国特
許第４,４６３,３４２号（１９８４年７月３１日発
行）、及び「２層イメージの適応データ圧縮用多目的Ｖ
ＬＳＩチップ」と題する論文（ＩＢＭ研究開発ジャーナ
ル、第３２巻第６号、１９８８年１１月、７７５〜７９
５ページ）に述べられている。又、別の桁上げ制御技術
が「データ圧縮用算術符号化」と題する論文（ＡＣＭ通
信、１９８７年６月、第３０巻第６号、５２０〜５４０
ページ）に述べられている。
する際に行う桁上げ制御は周知である。例えば算術符号
化及び復号化に用いられる従来の桁上げ技術は、米国特
許第４,４６３,３４２号（１９８４年７月３１日発
行）、及び「２層イメージの適応データ圧縮用多目的Ｖ
ＬＳＩチップ」と題する論文（ＩＢＭ研究開発ジャーナ
ル、第３２巻第６号、１９８８年１１月、７７５〜７９
５ページ）に述べられている。又、別の桁上げ制御技術
が「データ圧縮用算術符号化」と題する論文（ＡＣＭ通
信、１９８７年６月、第３０巻第６号、５２０〜５４０
ページ）に述べられている。
【０００３】
【発明が解決しようとする課題】上記の米国特許第４,
４６３,３４２号及びＩＢＭジャーナルの論文に開示さ
れている技術の欠点は、トランスミッタ（送信機）／エ
ンコーダ（符号器）における圧縮性能に難点のあること
と、対応するレシーバ（受信機）／デコーダ（復号器）
の複雑さが増すことである。これらの欠点は、送信機／
エンコーダ・ビットストリームにいわゆる制御文字、す
なわちビットを挿入する必要と、対応する受信機／デコ
ーダにおいてこれら制御文字を除去する必要とから生じ
る。
４６３,３４２号及びＩＢＭジャーナルの論文に開示さ
れている技術の欠点は、トランスミッタ（送信機）／エ
ンコーダ（符号器）における圧縮性能に難点のあること
と、対応するレシーバ（受信機）／デコーダ（復号器）
の複雑さが増すことである。これらの欠点は、送信機／
エンコーダ・ビットストリームにいわゆる制御文字、す
なわちビットを挿入する必要と、対応する受信機／デコ
ーダにおいてこれら制御文字を除去する必要とから生じ
る。
【０００４】上記「データ圧縮用算術符号化」論文に開
示されている技術は、エンコーダ／デコーダの演算上の
複雑さを顕著に増加させる欠点がある。この欠点は、エ
ンコーダ／デコーダにおいてビットごとの情報処理が必
要とされるために生じる。
示されている技術は、エンコーダ／デコーダの演算上の
複雑さを顕著に増加させる欠点がある。この欠点は、エ
ンコーダ／デコーダにおいてビットごとの情報処理が必
要とされるために生じる。
【０００５】
【課題を解決するための手段】算術エントロピー符号化
に用いられる上記のような従来の桁上げ技術の欠点ある
いは問題点は、本発明により次のようにすることで回避
できる。すなわち、算術符号化ユニットの出力として与
えられる連続指定論理信号の集まりのカウント数を維持
し、それにより非実際的なほど多数のステージを有する
レジスタ（いわゆる「無限」レジスタ）をエミュレート
するのである。
に用いられる上記のような従来の桁上げ技術の欠点ある
いは問題点は、本発明により次のようにすることで回避
できる。すなわち、算術符号化ユニットの出力として与
えられる連続指定論理信号の集まりのカウント数を維持
し、それにより非実際的なほど多数のステージを有する
レジスタ（いわゆる「無限」レジスタ）をエミュレート
するのである。
【０００６】このカウント数を用いて、第１の種類の連
続指定論理信号又は第２の種類の連続指定論理信号のい
ずれかの信号の集まりをカウント数と同数だけ出力させ
る。第１又は第２のいずれの種類にするかは、エミュレ
ートする対象のいわゆる「無限」レジスタのステージを
通して桁上げが伝搬するかどうかによる。
続指定論理信号又は第２の種類の連続指定論理信号のい
ずれかの信号の集まりをカウント数と同数だけ出力させ
る。第１又は第２のいずれの種類にするかは、エミュレ
ートする対象のいわゆる「無限」レジスタのステージを
通して桁上げが伝搬するかどうかによる。
【０００７】本発明の一実施例において、信号の集まり
は各々、複数のビットからなる１バイトである。又、第
１の種類の連続指定論理信号は論理数１からなり、第２
の種類の連続指定論理信号は論理数０からなる。
は各々、複数のビットからなる１バイトである。又、第
１の種類の連続指定論理信号は論理数１からなり、第２
の種類の連続指定論理信号は論理数０からなる。
【０００８】
【実施例】図１は本発明の好ましい実施例のシステム配
置を簡略に示すブロック図である。図中に、記号源１０
１、エンコーダ１０３とインタフェース１０４とを含む
送信機１０２、伝送及び、又は記憶媒体１０５、インタ
フェース１０８とデコーダ１０７とを含む受信機１０
６、及び復号化した記号のユニット１０９を示す。
置を簡略に示すブロック図である。図中に、記号源１０
１、エンコーダ１０３とインタフェース１０４とを含む
送信機１０２、伝送及び、又は記憶媒体１０５、インタ
フェース１０８とデコーダ１０７とを含む受信機１０
６、及び復号化した記号のユニット１０９を示す。
【０００９】まず、符号化すべき信号すなわちデータ記
号ｓk が、記号源１０１から送信機１０２に、そしてそ
の内部のエンコーダ１０３に供給される。データ記号ｓ
k は、どのようなデータ源からも得られるし、例えば画
像を表すデータ記号でもよい。データ記号ｓk が表すこ
とができる異なる値の数Ａ、すなわち記号アルファベッ
ト、の大きさには概して制限はないが、多くの場合アル
ファベットは２進でＡ＝２である。
号ｓk が、記号源１０１から送信機１０２に、そしてそ
の内部のエンコーダ１０３に供給される。データ記号ｓ
k は、どのようなデータ源からも得られるし、例えば画
像を表すデータ記号でもよい。データ記号ｓk が表すこ
とができる異なる値の数Ａ、すなわち記号アルファベッ
ト、の大きさには概して制限はないが、多くの場合アル
ファベットは２進でＡ＝２である。
【００１０】本実施例では、エンコーダ１０３は算術エ
ントロピーエンコーダで、データ記号を圧縮した形に符
号化するのに用いられる。圧縮されたデータ記号は、符
号化データとして、インタフェースユニット１０４を経
て伝送及び、又は記憶媒体１０５に送信される。インタ
フェースユニット１０４の実際の装置を何にするかは、
インタフェースされる媒体、すなわち個々の伝送媒体及
び、又は個々の記憶媒体によって決まる。このようなイ
ンタフェースユニットは技術的に周知である。
ントロピーエンコーダで、データ記号を圧縮した形に符
号化するのに用いられる。圧縮されたデータ記号は、符
号化データとして、インタフェースユニット１０４を経
て伝送及び、又は記憶媒体１０５に送信される。インタ
フェースユニット１０４の実際の装置を何にするかは、
インタフェースされる媒体、すなわち個々の伝送媒体及
び、又は個々の記憶媒体によって決まる。このようなイ
ンタフェースユニットは技術的に周知である。
【００１１】符号化したデータは、伝送及び、又は記憶
媒体１０５から受信機１０６に、そしてその内部のイン
タフェースユニット１０８とデコーダ１０７に供給され
る。インタフェースユニット１０８の実際の個々の装置
は符号化データを供給する伝送及び、又は記憶媒体１０
５の両方に適合するものでなければならない。しかし、
符号化データは伝送媒体を経て遠隔のデコーダおよび、
又はどれかの記憶媒体に伝送してもよい。
媒体１０５から受信機１０６に、そしてその内部のイン
タフェースユニット１０８とデコーダ１０７に供給され
る。インタフェースユニット１０８の実際の個々の装置
は符号化データを供給する伝送及び、又は記憶媒体１０
５の両方に適合するものでなければならない。しかし、
符号化データは伝送媒体を経て遠隔のデコーダおよび、
又はどれかの記憶媒体に伝送してもよい。
【００１２】デコーダ１０７は、本実施例ではエンコー
ダ１０３に適合する形式の算術エントロピーデコーダ
で、符号化データを復号化して、記号源１０１から供給
された本来の記号ｓk を復号化した形の記号を得る。復
号化した記号ｓk は、復号化記号ユニットに供給されて
所要の用途に供される。用途の一例は、画像の定義であ
る。
ダ１０３に適合する形式の算術エントロピーデコーダ
で、符号化データを復号化して、記号源１０１から供給
された本来の記号ｓk を復号化した形の記号を得る。復
号化した記号ｓk は、復号化記号ユニットに供給されて
所要の用途に供される。用途の一例は、画像の定義であ
る。
【００１３】図２は、エンコーダ１０３の詳細を簡単な
ブロック図で示す。図中に、算術エンコーダユニット２
０２と出力ユニット２０３とを含む算術エンコーダ２０
１、文脈抽出器２０４、及び確率推定器２０５を示す。
ブロック図で示す。図中に、算術エンコーダユニット２
０２と出力ユニット２０３とを含む算術エンコーダ２０
１、文脈抽出器２０４、及び確率推定器２０５を示す。
【００１４】符号化すべきデータ記号ｓk が、この符号
化すべきデータ記号ｓk に対する確率推定値「 ｐk→」
と共に、算術エンコーダ２０１に、そしてその内部の算
術エンコーダユニット２０２に供給される（図２、図
３、図４、及び図５、並びに後に説明する式１、式２、
式３においては確率推定値「ｐ→」を、「ｐの上に右向
きの矢印を付けた記号」で表す）。算術エンコーダユニ
ット２０２は、出力ユニットと共に、本発明により、供
給された記号を符号化して符号化データを生成する。
化すべきデータ記号ｓk に対する確率推定値「 ｐk→」
と共に、算術エンコーダ２０１に、そしてその内部の算
術エンコーダユニット２０２に供給される（図２、図
３、図４、及び図５、並びに後に説明する式１、式２、
式３においては確率推定値「ｐ→」を、「ｐの上に右向
きの矢印を付けた記号」で表す）。算術エンコーダユニ
ット２０２は、出力ユニットと共に、本発明により、供
給された記号を符号化して符号化データを生成する。
【００１５】確率推定器２０５は、供給されたデータ記
号ｓk と文脈抽出器２０４から得られた文脈とに応答し
て、求める確率推定値を生成する。文脈抽出器２０４は
周知の方法で文脈を生成する。しかし、文脈は希望通り
に作成供給できるものである。生成された確率推定値は
入力記号ｓk 及びその関連文脈に対して、 ｐk→＝（ｐ
1ｐ2ｐ3・・・ｐA）である。
号ｓk と文脈抽出器２０４から得られた文脈とに応答し
て、求める確率推定値を生成する。文脈抽出器２０４は
周知の方法で文脈を生成する。しかし、文脈は希望通り
に作成供給できるものである。生成された確率推定値は
入力記号ｓk 及びその関連文脈に対して、 ｐk→＝（ｐ
1ｐ2ｐ3・・・ｐA）である。
【００１６】算術エンコーダユニット、文脈抽出器、及
び確率推定器は技術的に周知であり、本発明の算術エン
コーダユニット２０２、文脈抽出器２０４、及び確率推
定器２０５にはこれらの周知のユニットを用いてよい。
周知の算術エンコーダユニットの例については、上記の
米国特許第４,４６３,３４２号及びＩＢＭジャーナルの
論文を参照されたい。又、エンコーダ１０３用の文脈抽
出器、及び確率推定器も適当なものならどのようなユニ
ットを用いてもよい。
び確率推定器は技術的に周知であり、本発明の算術エン
コーダユニット２０２、文脈抽出器２０４、及び確率推
定器２０５にはこれらの周知のユニットを用いてよい。
周知の算術エンコーダユニットの例については、上記の
米国特許第４,４６３,３４２号及びＩＢＭジャーナルの
論文を参照されたい。又、エンコーダ１０３用の文脈抽
出器、及び確率推定器も適当なものならどのようなユニ
ットを用いてもよい。
【００１７】出力ユニット２０３は、算術エンコーダユ
ニット２０２から出力された連続指定論理信号に応答し
て、本発明により、いわゆる「無限」レジスタをエミュ
レートする。算術エンコーダユニット２０２、出力ユニ
ット２０３、及びこれらの作動については以下に更に詳
細に説明する。
ニット２０２から出力された連続指定論理信号に応答し
て、本発明により、いわゆる「無限」レジスタをエミュ
レートする。算術エンコーダユニット２０２、出力ユニ
ット２０３、及びこれらの作動については以下に更に詳
細に説明する。
【００１８】図３は、デコーダ１０７の詳細を簡単なブ
ロック図で示す。図中に、算術デコーダユニット３０２
を含む算術デコーダ３０１、文脈抽出器３０３、及び確
率推定器３０４を示す。デコーダに含まれるこれらのユ
ニットも技術的に周知である。算術デコーダユニット３
０２は算術エンコーダユニット２０２に適合するもので
なければならない。同様に、文脈抽出器３０３及び確率
推定器３０４は、文脈抽出器２０４及び確率推定器２０
５とそれぞれ同一のものである。
ロック図で示す。図中に、算術デコーダユニット３０２
を含む算術デコーダ３０１、文脈抽出器３０３、及び確
率推定器３０４を示す。デコーダに含まれるこれらのユ
ニットも技術的に周知である。算術デコーダユニット３
０２は算術エンコーダユニット２０２に適合するもので
なければならない。同様に、文脈抽出器３０３及び確率
推定器３０４は、文脈抽出器２０４及び確率推定器２０
５とそれぞれ同一のものである。
【００１９】図３において、デコーダ１０７の算術デコ
ーダ３０１は、符号化したデータと確率推定器３０４か
らの確率推定値との供給を受け、本来のデータ記号ｓk
を復号化した記号を生成する。本発明ではその独特の符
号化により、デコーダ１０７も、したがって算術デコー
ダ３０１も、桁上げ制御に用いる制御文字等の処理にお
いて従来のデコーダでは必要としていた特別な処理装置
を一切必要としない、という利点がある。その結果、デ
コーダ１０７も、したがって算術デコーダ３０１もその
複雑さが従来の装置に比較して格段に減少している。
ーダ３０１は、符号化したデータと確率推定器３０４か
らの確率推定値との供給を受け、本来のデータ記号ｓk
を復号化した記号を生成する。本発明ではその独特の符
号化により、デコーダ１０７も、したがって算術デコー
ダ３０１も、桁上げ制御に用いる制御文字等の処理にお
いて従来のデコーダでは必要としていた特別な処理装置
を一切必要としない、という利点がある。その結果、デ
コーダ１０７も、したがって算術デコーダ３０１もその
複雑さが従来の装置に比較して格段に減少している。
【００２０】図４は、「無限」レジスタ４０３からなる
出力ユニット２０３を含むエントロピーエンコーダを簡
単に示す概念図で、エンコーダ１０３の中の算術エンコ
ーダ２０１の算術エンコーダユニット２０２と出力ユニ
ット２０３とを図示してある。
出力ユニット２０３を含むエントロピーエンコーダを簡
単に示す概念図で、エンコーダ１０３の中の算術エンコ
ーダ２０１の算術エンコーダユニット２０２と出力ユニ
ット２０３とを図示してある。
【００２１】算術エンコーダユニット２０２は、データ
記号ｓk とこれに対応する確率推定値ｐk→ との供給を
受けてこれらに応答し、データ記号を周知の方法で算術
的に符号化する。データ記号ｓk とこれに対応する確率
推定値ｐk→ とが、先入れ先出し方式（ＦＩＦＯ）で供
給される。説明を簡単且つ明確にするため、算術エンコ
ーダユニット２０２の内、符号化レジスタ４０１とその
「桁上げ」ステージ４０２のみを図４に示してある。こ
れら算術エンコーダのユニット類の例については、同じ
く上記の米国特許第４,４６３,３４２号及びＩＢＭジャ
ーナルの論文を参照されたい。
記号ｓk とこれに対応する確率推定値ｐk→ との供給を
受けてこれらに応答し、データ記号を周知の方法で算術
的に符号化する。データ記号ｓk とこれに対応する確率
推定値ｐk→ とが、先入れ先出し方式（ＦＩＦＯ）で供
給される。説明を簡単且つ明確にするため、算術エンコ
ーダユニット２０２の内、符号化レジスタ４０１とその
「桁上げ」ステージ４０２のみを図４に示してある。こ
れら算術エンコーダのユニット類の例については、同じ
く上記の米国特許第４,４６３,３４２号及びＩＢＭジャ
ーナルの論文を参照されたい。
【００２２】図４において、算術エンコーダユニット２
０２は、「桁上げ」ステージ４０２の桁上げ状態を示す
「桁上げ」（ＣＡＲＲＹ）表示子、すなわち第１の「桁
上げ」表示子と、符号化レジスタ４０１から出力され読
み取られるべきビットを示す「新ビット」（ＮＥＷ＿Ｂ
ＩＴ）表示子と、算術エンコーダユニット２０２の符号
化レジスタ４０１から出力された新ビットの読み取り準
備ができたことを示す「新ビット読取」（ＲＥＡＤ＿Ｎ
ＥＷ＿ＢＩＴ）表示子とを生成する。
０２は、「桁上げ」ステージ４０２の桁上げ状態を示す
「桁上げ」（ＣＡＲＲＹ）表示子、すなわち第１の「桁
上げ」表示子と、符号化レジスタ４０１から出力され読
み取られるべきビットを示す「新ビット」（ＮＥＷ＿Ｂ
ＩＴ）表示子と、算術エンコーダユニット２０２の符号
化レジスタ４０１から出力された新ビットの読み取り準
備ができたことを示す「新ビット読取」（ＲＥＡＤ＿Ｎ
ＥＷ＿ＢＩＴ）表示子とを生成する。
【００２３】「桁上げ」、「新ビット」、及び「新ビッ
ト読取」の表示子は出力ユニット２０３のいわゆる「無
限」レジスタ４０３に供給される。図４の出力ユニット
２０３に概念化して示した「無限」レジスタ４０３は、
前にも述べたように、有効に実現できないほどにそのス
テージ数が多すぎて実際的でないものである。出力ユニ
ット２０３の、この「無限」レジスタ４０３を作動させ
るには、「桁上げ」表示子をステージ１の論理信号に加
え、これをシフトし、次に「新ビット」表示子をステー
ジ１に入れる。
ト読取」の表示子は出力ユニット２０３のいわゆる「無
限」レジスタ４０３に供給される。図４の出力ユニット
２０３に概念化して示した「無限」レジスタ４０３は、
前にも述べたように、有効に実現できないほどにそのス
テージ数が多すぎて実際的でないものである。出力ユニ
ット２０３の、この「無限」レジスタ４０３を作動させ
るには、「桁上げ」表示子をステージ１の論理信号に加
え、これをシフトし、次に「新ビット」表示子をステー
ジ１に入れる。
【００２４】本発明は、「無限」レジスタ４０３内に現
存するデータ出力｛ｃ1，ｃ2，ｃ3， ．．．，ｃm｝、
算術エンコーダユニット２０２へのデータ記号｛ｓ1，
ｓ2，ｓ3，．．．，ｓk｝の入力、及び対応する確率推
定値 ｛ｐ1→，ｐ2→，ｐ3→，．．．，ｐk→｝が、い
わゆる「復号化特性」を満足するという事実に基づいて
いる。この特性については以下にその概略を説明する
が、更に詳しくは上記の米国特許第４,４６３,３４２号
に述べられている。
存するデータ出力｛ｃ1，ｃ2，ｃ3， ．．．，ｃm｝、
算術エンコーダユニット２０２へのデータ記号｛ｓ1，
ｓ2，ｓ3，．．．，ｓk｝の入力、及び対応する確率推
定値 ｛ｐ1→，ｐ2→，ｐ3→，．．．，ｐk→｝が、い
わゆる「復号化特性」を満足するという事実に基づいて
いる。この特性については以下にその概略を説明する
が、更に詳しくは上記の米国特許第４,４６３,３４２号
に述べられている。
【００２５】ここに、（Ｓ，Ｐ→）によって一組の入力
記号（Ｓ）と対応する確率推定値（Ｐ→）、すなわち連
接｛ｓ1，ｓ2，ｓ3，．．．，ｓk｝，｛ｐ1→，ｐ2→，
ｐ3→，．．．，ｐk→｝ を表し、Ｃ（Ｓ，Ｐ→）によ
って、これに対応して「無限」レジスタ４０３内に現存
する２進データ出力｛ｃ1，ｃ2，ｃ3，．．．，ｃm｝を
表すこととする。Ｃ（Ｓ，Ｐ→）は２進小数部として解
釈され、次の数１で表される。
記号（Ｓ）と対応する確率推定値（Ｐ→）、すなわち連
接｛ｓ1，ｓ2，ｓ3，．．．，ｓk｝，｛ｐ1→，ｐ2→，
ｐ3→，．．．，ｐk→｝ を表し、Ｃ（Ｓ，Ｐ→）によ
って、これに対応して「無限」レジスタ４０３内に現存
する２進データ出力｛ｃ1，ｃ2，ｃ3，．．．，ｃm｝を
表すこととする。Ｃ（Ｓ，Ｐ→）は２進小数部として解
釈され、次の数１で表される。
【００２６】
【数１】
【００２７】又、Ｌ（Ｃ（Ｓ，Ｐ→））によって、｛ｃ
1，ｃ2，ｃ3，．．．，ｃm｝の長さを次の数２で表すこ
ととする。
1，ｃ2，ｃ3，．．．，ｃm｝の長さを次の数２で表すこ
ととする。
【００２８】
【数２】
【００２９】更に（Ｓ',Ｐ'→） によって（Ｓ，Ｐ→）
の連続ストリングを表し、Ｓ Ｓ’によってストリング
ＳとＳ’との連接を表し、Ｐ→Ｐ'→ によってこれらに
対応するストリングＰ→とＰ'→との連接を表すことと
する。ここにおいて、次の数３は、有効で、算術エンコ
ーダの復号化特性として定義される。
の連続ストリングを表し、Ｓ Ｓ’によってストリング
ＳとＳ’との連接を表し、Ｐ→Ｐ'→ によってこれらに
対応するストリングＰ→とＰ'→との連接を表すことと
する。ここにおいて、次の数３は、有効で、算術エンコ
ーダの復号化特性として定義される。
【００３０】
【数３】
【００３１】復号化特性（上記数３）から得られる一つ
の重要な帰結は、算術エンコーダユニット２０２によっ
て生成されたビットは多くて１回の桁上げしか経験でき
ないことである。これは又、算術エンコーダユニット２
０２において一旦論理数０が生成されるとこれより先に
生成されていたビットにはもはや桁上げがないというこ
とを意味する。いいかえれば、先に生成されたビットの
状態は、論理数０の生成後に発生する桁上げによって変
更されることはない。このようにして、これらの生成さ
れたビットは伝送及び、又は記憶媒体１０５（図１）に
供給できることとなる。しかし、出力ユニット２０３
（図４）の「無限」レジスタ４０３は、論理数１がどの
ように連続していてもこれを記憶収納できるような十分
な長さ、すなわち十分なステージ数を有していなければ
ならない。その場合、このステージ数は、多すぎて実現
できない数になる。
の重要な帰結は、算術エンコーダユニット２０２によっ
て生成されたビットは多くて１回の桁上げしか経験でき
ないことである。これは又、算術エンコーダユニット２
０２において一旦論理数０が生成されるとこれより先に
生成されていたビットにはもはや桁上げがないというこ
とを意味する。いいかえれば、先に生成されたビットの
状態は、論理数０の生成後に発生する桁上げによって変
更されることはない。このようにして、これらの生成さ
れたビットは伝送及び、又は記憶媒体１０５（図１）に
供給できることとなる。しかし、出力ユニット２０３
（図４）の「無限」レジスタ４０３は、論理数１がどの
ように連続していてもこれを記憶収納できるような十分
な長さ、すなわち十分なステージ数を有していなければ
ならない。その場合、このステージ数は、多すぎて実現
できない数になる。
【００３２】すなわち、図４を概念的に実現する際の顕
著な問題点は、このようないわゆる「無限」レジスタ４
０３の実現には非実際的な数のステージを必要とし、有
効な実現ができないということである。
著な問題点は、このようないわゆる「無限」レジスタ４
０３の実現には非実際的な数のステージを必要とし、有
効な実現ができないということである。
【００３３】図５は、非実際的な大きさのレジスタの必
要性を回避した、本発明の実施例としての算術エンコー
ダユニット２０２及び出力ユニット２０３の詳細を簡略
に示す。
要性を回避した、本発明の実施例としての算術エンコー
ダユニット２０２及び出力ユニット２０３の詳細を簡略
に示す。
【００３４】上記のように、算術エンコーダユニット２
０２には、符号化レジスタ４０１と桁上げステージ４０
２を含み、「桁上げ」、「新ビット」、及び「新ビット
読取」の表示子を生成する。これらの表示子は出力ユニ
ット２０３に供給される。出力ユニット２０３は論理信
号の集まりを記憶するためのＮ個のステージを含む第１
のバッファメモリ５０１（バッファ１）を有する。ここ
に、Ｎ≧１で、本実施例においてはＮ＝８、すなわち１
バイトである。
０２には、符号化レジスタ４０１と桁上げステージ４０
２を含み、「桁上げ」、「新ビット」、及び「新ビット
読取」の表示子を生成する。これらの表示子は出力ユニ
ット２０３に供給される。出力ユニット２０３は論理信
号の集まりを記憶するためのＮ個のステージを含む第１
のバッファメモリ５０１（バッファ１）を有する。ここ
に、Ｎ≧１で、本実施例においてはＮ＝８、すなわち１
バイトである。
【００３５】出力ユニット２０３には桁上げステージ５
０２（桁上げ１）も含まれる。この桁上げステージ５０
２は、第１のバッファメモリ５０１に記憶されたビット
に桁上げが発生したかどうかを示す第２の桁上げ表示子
を記憶する。本実施例においては、論理数１は「桁上げ
あり」を示し、論理数０は「桁上げなし」を示す。
０２（桁上げ１）も含まれる。この桁上げステージ５０
２は、第１のバッファメモリ５０１に記憶されたビット
に桁上げが発生したかどうかを示す第２の桁上げ表示子
を記憶する。本実施例においては、論理数１は「桁上げ
あり」を示し、論理数０は「桁上げなし」を示す。
【００３６】同じくＮ個のステージを含む第２のバッフ
ァメモリ５０３（バッファ２）が、符号化データ、すな
わち｛ｃ1，ｃ2，ｃ3， ．．．，ｃm｝ を出力するため
に用いられる。カウンタ５０４（カウンタ１）は、バッ
ファメモリ５０１におけるビット数をカウントするのに
用いられる。カウンタ５０５（カウンタ２）は、本発明
の態様として、バッファメモリ５０１に供給されてい
る、例えば論理数１のような第１の種類の連続論理信号
の集まりのカウント数を維持するために用いられる。本
実施例においては、カウンタ５０５はバッファメモリ５
０３から出力すべき指定論理信号の集まりの数を表示す
る。
ァメモリ５０３（バッファ２）が、符号化データ、すな
わち｛ｃ1，ｃ2，ｃ3， ．．．，ｃm｝ を出力するため
に用いられる。カウンタ５０４（カウンタ１）は、バッ
ファメモリ５０１におけるビット数をカウントするのに
用いられる。カウンタ５０５（カウンタ２）は、本発明
の態様として、バッファメモリ５０１に供給されてい
る、例えば論理数１のような第１の種類の連続論理信号
の集まりのカウント数を維持するために用いられる。本
実施例においては、カウンタ５０５はバッファメモリ５
０３から出力すべき指定論理信号の集まりの数を表示す
る。
【００３７】次いで、カウンタ５０５におけるカウント
数を用いて、本発明により、桁上げステージ５０２にお
ける「桁上げ１」表示子が「桁上げなし」（論理数０）
又は「桁上げあり」（論理数１）のいずれを示すかによ
り、例えば論理数１のような第１の種類の連続指定論理
信号、又は、例えば論理数０のような第２の種類の連続
指定論理信号のいずれかの信号の集まりをカウント数と
同数だけバッファメモリ５０３から出力させる。このよ
うにして本発明により、出力ユニット２０３がいわゆる
「無限」レジスタをエミュレートする。
数を用いて、本発明により、桁上げステージ５０２にお
ける「桁上げ１」表示子が「桁上げなし」（論理数０）
又は「桁上げあり」（論理数１）のいずれを示すかによ
り、例えば論理数１のような第１の種類の連続指定論理
信号、又は、例えば論理数０のような第２の種類の連続
指定論理信号のいずれかの信号の集まりをカウント数と
同数だけバッファメモリ５０３から出力させる。このよ
うにして本発明により、出力ユニット２０３がいわゆる
「無限」レジスタをエミュレートする。
【００３８】説明を簡単且つ明確にするため、バッファ
メモリ５０１（バッファ１）（図５）を算術エンコーダ
ユニット２０２とは別のユニットとして説明した。しか
し、バッファメモリ５０１と桁上げステージ５０２とは
一般に、算術エンコーダユニット２０２の符号化レジス
タ４０１と合体できることは当業者には明らかである。
そして、算術エンコーダユニット２０２（図５）に示し
た桁上げステージ４０２も、符号化レジスタ４０１と合
体できる。（上記のＩＢＭジャーナルの論文を参照され
たい。）
メモリ５０１（バッファ１）（図５）を算術エンコーダ
ユニット２０２とは別のユニットとして説明した。しか
し、バッファメモリ５０１と桁上げステージ５０２とは
一般に、算術エンコーダユニット２０２の符号化レジス
タ４０１と合体できることは当業者には明らかである。
そして、算術エンコーダユニット２０２（図５）に示し
た桁上げステージ４０２も、符号化レジスタ４０１と合
体できる。（上記のＩＢＭジャーナルの論文を参照され
たい。）
【００３９】本発明による図５の出力ユニット２０３の
作動を、図６及び図７のＡとＡ、ＢとＢを連結したフロ
ーチャートに示すステップを参照して説明する。これら
のステップは、本発明をソフトウエアとハードウエアと
の両面で具体化することによって得られる作動を示すも
のである。作動の流れはまず開始ステップ６０１から始
まる。
作動を、図６及び図７のＡとＡ、ＢとＢを連結したフロ
ーチャートに示すステップを参照して説明する。これら
のステップは、本発明をソフトウエアとハードウエアと
の両面で具体化することによって得られる作動を示すも
のである。作動の流れはまず開始ステップ６０１から始
まる。
【００４０】その後、ステップ６０２において、カウン
タ１（５０４）、カウンタ２（５０５）、バッファ１
（５０１）、及びバッファ２（５０３）の各ステージの
初期値を論理数０に設定する。
タ１（５０４）、カウンタ２（５０５）、バッファ１
（５０１）、及びバッファ２（５０３）の各ステージの
初期値を論理数０に設定する。
【００４１】次に、条件付き分岐点６０３において算術
エンコーダユニット２０２から「新ビット読取」が表明
されているか（論理数１か）どうかを検査する。検査結
果がＮＯならこのステップ６０３を繰り返す。このステ
ップ６０３の検査結果がＹＥＳなら、ステップ６０４に
おいて、算術エンコーダユニット２０２の桁上げステー
ジ４０２から「桁上げ」をバッファ１の第１のステージ
のビットに加える。すなわち、「バッファ１＝バッファ
１＋桁上げ」となる。
エンコーダユニット２０２から「新ビット読取」が表明
されているか（論理数１か）どうかを検査する。検査結
果がＮＯならこのステップ６０３を繰り返す。このステ
ップ６０３の検査結果がＹＥＳなら、ステップ６０４に
おいて、算術エンコーダユニット２０２の桁上げステー
ジ４０２から「桁上げ」をバッファ１の第１のステージ
のビットに加える。すなわち、「バッファ１＝バッファ
１＋桁上げ」となる。
【００４２】次にステップ６０５において、算術エンコ
ーダユニット２０２の出力レジスタから「新ビット」を
読み取り、ステップ６０６において、バッファ１のビッ
トをシフトする。すなわち、「バッファ１＝シフト（バ
ッファ１）＋新ビット」となる。ステップ６０７におい
ては、カウンタ１を増加して「カウンタ１＝カウンタ１
＋１」となる。
ーダユニット２０２の出力レジスタから「新ビット」を
読み取り、ステップ６０６において、バッファ１のビッ
トをシフトする。すなわち、「バッファ１＝シフト（バ
ッファ１）＋新ビット」となる。ステップ６０７におい
ては、カウンタ１を増加して「カウンタ１＝カウンタ１
＋１」となる。
【００４３】条件付き分岐点６０８において、カウンタ
１におけるビット充填数がＮに等しいかどうかを検査す
る。ここに、Ｎ≧１で、本実施例ではＮ＝８である。検
査結果がＮＯならステップ６０３に戻り、ステップ６０
８の結果がＹＥＳになるまで６０３から６０８までのス
テップを繰り返す。この結果のＹＥＳはバッファ１が充
填満了したことを示す。これで、ステップ６０９におい
て「カウンタ１＝０」にリセットされ、ステップ６１０
において、バッファ２を「バッファ２＝バッファ２＋桁
上げ１」にセットする。すなわち、桁上げ１からの「桁
上げ」がバッファ２に加えられたことになる。
１におけるビット充填数がＮに等しいかどうかを検査す
る。ここに、Ｎ≧１で、本実施例ではＮ＝８である。検
査結果がＮＯならステップ６０３に戻り、ステップ６０
８の結果がＹＥＳになるまで６０３から６０８までのス
テップを繰り返す。この結果のＹＥＳはバッファ１が充
填満了したことを示す。これで、ステップ６０９におい
て「カウンタ１＝０」にリセットされ、ステップ６１０
において、バッファ２を「バッファ２＝バッファ２＋桁
上げ１」にセットする。すなわち、桁上げ１からの「桁
上げ」がバッファ２に加えられたことになる。
【００４４】次に、条件付き分岐点６１１において、
「バッファ１」がＯＮＥかどうか、すなわちそのＮ個の
ステージにすべて論理数１が入っているかを検査する。
検査結果がＹＥＳなら論理数１はすべてバッファ１のス
テージにあることになり、ステップ６１２において、カ
ウンタ２を「カウンタ２＝カウンタ２＋１」とする。そ
してステップ６１３において、「バッファ１＝ＺＥＲ
Ｏ］（Ｎ個のステージにすべて論理数０がある）にセッ
トし、「桁上げ１＝０」にセットする。その後はステッ
プ６０３にもどる。
「バッファ１」がＯＮＥかどうか、すなわちそのＮ個の
ステージにすべて論理数１が入っているかを検査する。
検査結果がＹＥＳなら論理数１はすべてバッファ１のス
テージにあることになり、ステップ６１２において、カ
ウンタ２を「カウンタ２＝カウンタ２＋１」とする。そ
してステップ６１３において、「バッファ１＝ＺＥＲ
Ｏ］（Ｎ個のステージにすべて論理数０がある）にセッ
トし、「桁上げ１＝０」にセットする。その後はステッ
プ６０３にもどる。
【００４５】ステップ６１１において検査結果がＮＯの
場合は、バッファ１の内容は「すべて論理数１」以外の
状態であり、ステップ６１４においてはバッファ２のビ
ット内容を出力として供給することになる。
場合は、バッファ１の内容は「すべて論理数１」以外の
状態であり、ステップ６１４においてはバッファ２のビ
ット内容を出力として供給することになる。
【００４６】次に条件付き分岐点６１５において、「カ
ウンタ２＝０」かどうかを検査する。検査結果がＹＥＳ
なら、ステップ６１６においてバッファ２の内容をバッ
ファ１の内容にセットする。すなわち、「バッファ２＝
バッファ１」である。その後ステップ６１３を繰り返
し、ステップ６０３に戻る。ステップ６１５の検査結果
がＮＯの場合は、バッファ２から出力として供給すべき
第１又は第２の種類の指定論理信号が、少なくとも１グ
ループ（本実施例では１バイト）はあることになる。
ウンタ２＝０」かどうかを検査する。検査結果がＹＥＳ
なら、ステップ６１６においてバッファ２の内容をバッ
ファ１の内容にセットする。すなわち、「バッファ２＝
バッファ１」である。その後ステップ６１３を繰り返
し、ステップ６０３に戻る。ステップ６１５の検査結果
がＮＯの場合は、バッファ２から出力として供給すべき
第１又は第２の種類の指定論理信号が、少なくとも１グ
ループ（本実施例では１バイト）はあることになる。
【００４７】ここで条件付き分岐点６１７において、桁
上げ１が論理数０かどうかを検査する。もし検査結果が
ＹＥＳなら、「桁上げなし」である。すなわち「桁上げ
１」には論理数０があり、論理数１の集まりを出力とし
て供給する必要がある。
上げ１が論理数０かどうかを検査する。もし検査結果が
ＹＥＳなら、「桁上げなし」である。すなわち「桁上げ
１」には論理数０があり、論理数１の集まりを出力とし
て供給する必要がある。
【００４８】それで、条件付き分岐点６１８において、
「カウンタ２」が０かどうかを検査する。すなわち論理
信号の集まりを出力として供給すべきかどうかを検査す
る。
「カウンタ２」が０かどうかを検査する。すなわち論理
信号の集まりを出力として供給すべきかどうかを検査す
る。
【００４９】もしステップ６１８の検査結果がＮＯな
ら、ステップ６１９において、論理数１の集まり１組
（すなわちＯＮＥ１個）をバッファ２を経て出力として
供給する。ステップ６２０において、カウンタ２を減少
させ、すなわち、「カウンタ２＝カウンタ２−１」とし
て、ステップ６１８に戻る。カウンタ２が０となり、第
１の種類の指定論理信号がなくなり、論理数１をバッフ
ァ２を経て出力として供給する必要が出るまで、ステッ
プ６１８から６２０までを繰り返す。
ら、ステップ６１９において、論理数１の集まり１組
（すなわちＯＮＥ１個）をバッファ２を経て出力として
供給する。ステップ６２０において、カウンタ２を減少
させ、すなわち、「カウンタ２＝カウンタ２−１」とし
て、ステップ６１８に戻る。カウンタ２が０となり、第
１の種類の指定論理信号がなくなり、論理数１をバッフ
ァ２を経て出力として供給する必要が出るまで、ステッ
プ６１８から６２０までを繰り返す。
【００５０】ステップ６１８の検査結果がＹＥＳの場合
は、ステップ６１６と６１３とを繰り返してステップ６
０３に戻る。
は、ステップ６１６と６１３とを繰り返してステップ６
０３に戻る。
【００５１】ステップ６１７の検査結果がＮＯの場合
は、「桁上げ１」に「桁上げ」すなわち論理数１がある
ことになるので、論理数１をすべて論理数０とする。
は、「桁上げ１」に「桁上げ」すなわち論理数１がある
ことになるので、論理数１をすべて論理数０とする。
【００５２】条件付き分岐点６２１において、カウンタ
２が０かどうかを検査する。検査結果がＮＯなら、ステ
ップ６２２において論理数０の集まりを１組、すなわち
ＺＥＲＯ１個をバッファ２を経て出力として供給する。
ステップ６２３において、カウンタ２を減少させ、すな
わち、「カウンタ２＝カウンタ２−１」として、ステッ
プ６２１に戻る。カウンタ２が０となり、第２の種類の
指定論理信号がなくなり、論理数０をバッファ２を経て
出力として供給する必要が出るまで、ステップ６２１か
ら６２３までを繰り返す。このステップ６２１の検査結
果がＹＥＳなら、ステップ６１６と６１３とを繰り返
し、ステップ６０３に戻る。
２が０かどうかを検査する。検査結果がＮＯなら、ステ
ップ６２２において論理数０の集まりを１組、すなわち
ＺＥＲＯ１個をバッファ２を経て出力として供給する。
ステップ６２３において、カウンタ２を減少させ、すな
わち、「カウンタ２＝カウンタ２−１」として、ステッ
プ６２１に戻る。カウンタ２が０となり、第２の種類の
指定論理信号がなくなり、論理数０をバッファ２を経て
出力として供給する必要が出るまで、ステップ６２１か
ら６２３までを繰り返す。このステップ６２１の検査結
果がＹＥＳなら、ステップ６１６と６１３とを繰り返
し、ステップ６０３に戻る。
【００５３】ここで次のことに留意されたい。すなわ
ち、もし「桁上げ１」が論理数１なら、第１の種類の指
定論理信号の連続した集まりのすべてに波及し、第２の
種類の指定論理信号の集まりが出力として供給される。
またもし「桁上げ１」が論理数０の場合は、第１の種類
の指定論理信号の集まりが出力として供給される。すな
わち、本実施例においては、「桁上げ１」が論理数１の
場合は論理数０の集まりが出力として供給される。ま
た、「桁上げ１」が論理数０の場合は論理数１の集まり
が出力として供給される。いい替えると、出力として供
給される集まりにおける指定論理信号は、「桁上げ１」
の表示を補完するものである。
ち、もし「桁上げ１」が論理数１なら、第１の種類の指
定論理信号の連続した集まりのすべてに波及し、第２の
種類の指定論理信号の集まりが出力として供給される。
またもし「桁上げ１」が論理数０の場合は、第１の種類
の指定論理信号の集まりが出力として供給される。すな
わち、本実施例においては、「桁上げ１」が論理数１の
場合は論理数０の集まりが出力として供給される。ま
た、「桁上げ１」が論理数０の場合は論理数１の集まり
が出力として供給される。いい替えると、出力として供
給される集まりにおける指定論理信号は、「桁上げ１」
の表示を補完するものである。
【００５４】以上のようにして、本発明において、この
独特の方法によりいわゆる「無限」レジスタがエミュレ
ートされる。
独特の方法によりいわゆる「無限」レジスタがエミュレ
ートされる。
【００５５】以上の説明は、本発明の一実施例に関する
もので、この技術分野の当業者であれば、本発明の種々
の変形例を考え得るが、それらはいずれも本発明の技術
的範囲に包含される。
もので、この技術分野の当業者であれば、本発明の種々
の変形例を考え得るが、それらはいずれも本発明の技術
的範囲に包含される。
【００５６】
【発明の効果】以上述べたごとく、本発明によれば、非
実際的なほど多数のステージを有するレジスタ（いわゆ
る「無限」レジスタ）をエミュレートするので、信号の
圧縮性能における難点や、装置の複雑さと演算上の複雑
さの増大等の、従来の桁上げ技術の欠点と問題点を回避
できる。
実際的なほど多数のステージを有するレジスタ（いわゆ
る「無限」レジスタ）をエミュレートするので、信号の
圧縮性能における難点や、装置の複雑さと演算上の複雑
さの増大等の、従来の桁上げ技術の欠点と問題点を回避
できる。
【図１】本発明の好ましい実施例のシステム配置を示す
ブロック図である。
ブロック図である。
【図２】図１のシステムに用いられるような、本発明の
態様を含むエンコーダを示す説明ブロック図である。
態様を含むエンコーダを示す説明ブロック図である。
【図３】図１のシステムに用いられるような、本発明の
態様を含むデコーダを示す説明ブロック図である。
態様を含むデコーダを示す説明ブロック図である。
【図４】本発明の出力ユニットにおけるいわゆる「無
限」レジスタを含むエンコーダの概念図である。
限」レジスタを含むエンコーダの概念図である。
【図５】図２のエンコーダの算術エンコーダユニット及
び出力ユニットにおける本発明の実施態様を簡略に示す
説明図である。
び出力ユニットにおける本発明の実施態様を簡略に示す
説明図である。
【図６】図５に示す本発明の実施例ユニットの一連の作
動ステップを示すフローチャートの一部で、図６のＡ，
Ｂを図７のＡ，Ｂにそれぞれ連結して一つのフローチャ
ートを構成する。
動ステップを示すフローチャートの一部で、図６のＡ，
Ｂを図７のＡ，Ｂにそれぞれ連結して一つのフローチャ
ートを構成する。
【図７】図５に示す本発明の実施例ユニットの一連の作
動ステップを示すフローチャートの一部で、図７のＡ，
Ｂを図６のＡ，Ｂにそれぞれ連結して一つのフローチャ
ートを構成する。
動ステップを示すフローチャートの一部で、図７のＡ，
Ｂを図６のＡ，Ｂにそれぞれ連結して一つのフローチャ
ートを構成する。
１０１ 記号源 １０２ 送信機 １０３ エンコーダ １０４ インタフェースユニット １０５ 伝送及び、又は記憶媒体 １０６ 受信機 １０７ デコーダ １０８ インタフェースユニット １０９ 復号化した記号ユニット ２０１ 算術エンコーダ ２０２ 算術エンコーダユニット ２０３ 出力ユニット ２０４，３０３ 文脈抽出器 ２０５，３０４ 確率推定器 ３０１ 算術デコーダ ３０２ 算術デコーダユニット ４０１ 符号化レジスタ ４０２ 桁上げステージ ４０３ 「無限」レジスタ ５０１ バッファメモリ１ ５０２ 桁上げステージ１（桁上げ１） ５０３ バッファメモリ２ ５０４ カウンタ１ ５０５ カウンタ２
───────────────────────────────────────────────────── フロントページの続き (56)参考文献 米国特許4973961（ＵＳ，Ａ) 欧州特許出願公開443255（ＥＰ，Ａ)
Claims (17)
- 【請求項１】 符号化対象入力信号の信号源と、 前記入力信号の確率推定値の供給手段と、 前記入力信号と前記確率推定値との供給を受けて、前記
入力信号を符号化した信号を発生させる算術符号化手段
であって、前記入力信号を圧縮データ化した信号と第１
の桁上げ表示子とを発生させるための算術符号化レジス
タと出力処理ユニットとを有する算術符号化手段と、 前記入力信号の前記符号化した信号を伝送及び、又は記
憶媒体に供給する手段と、 からなる、複数の記号値を有する入力信号の適応符号化
装置において、 前記圧縮データ化した信号の供給を受けるとともに前記
第１の桁上げ表示子に応答して、前記算術符号化レジス
タから供給される第１の種類の連続指定論理信号の集ま
りのカウント数を累計する手段と、 第１の桁上げが前記カウントされた前記論理信号の集ま
りを通して伝搬するかどうかを表す第２の桁上げ表示子
を得る手段と、 前記の集まりのカウント数の累計前及び累計後に発生し
た前記算術符号化レジスタから得られる論理信号の集ま
りを出力として記憶し供給する手段と、 前記記憶し供給する手段に前記第２の桁上げ表示子を加
える手段と、 前記第１の種類の連続指定論理信号又は前記第２の桁上
げ表示子に依存する第２の種類の連続指定論理信号を含
む前記累計カウント数に等しい数の集まりを出力として
供給する手段と、 からなることを特徴とする複数の記号値を有する入力信
号の適応符号化装置。 - 【請求項２】 前記第１の種類の連続指定論理信号が論
理数１であり、前記第２の種類の連続指定論理信号が論
理数０であることを特徴とする請求項１の装置。 - 【請求項３】 前記出力として供給する手段が、前記カ
ウント数に等しい数の集まりを出力として供給する手段
を含み、これらの数の集まりの各々は前記第２の桁上げ
表示子を補完する指定論理信号を含むことを特徴とする
請求項１の装置。 - 【請求項４】 前記第２の桁上げ表示子が、論理数１で
ある場合には桁上げありを示し、論理数０である場合に
は桁上げなしを示すことを特徴とする請求項３の装置。 - 【請求項５】 前記カウント数を累計するための手段
が、前記供給された圧縮データ化した信号のビットを記
憶するための予め定めた数のステージを有する第１のバ
ッファ手段と、前記第１のバッファ手段において第１の
種類の連続指定論理信号の集まりのカウント数を得るた
めのカウント手段を含み、前記第１の桁上げ表示子が、
前記第１のバッファ手段の第１のステージに加えられ、
前記供給された圧縮データ化した信号の前記ビットが前
記予め定めた数のステージに移動されることを特徴とす
る請求項１の装置。 - 【請求項６】 前記予め定めたステージの数が前記の集
まりの各々におけるビットの数に等しいことを特徴とす
る請求項５の装置。 - 【請求項７】 前記記憶し供給する手段が、予定数のス
テージを有する第２のバッファ手段を含み、この第２の
バッファ手段には、前記第１のバッファ手段からの前記
第１の種類の連続指定論理信号を含むがその全ては含ま
ないビットの集まりが供給され且つ記憶され、前記第２
の桁上げ表示子がこの第２のバッファ手段の第１のステ
ージに加えられることを特徴とする請求項６の装置。 - 【請求項８】 前記出力として供給する手段が、前記カ
ウント数に等しい数の前記の集まりを前記第２のバッフ
ァ手段を通して供給するための手段を含むことを特徴と
する請求項７の装置。 - 【請求項９】 前記第１の種類の連続指定論理信号が論
理数１であり、前記第２の種類の連続指定論理信号が論
理数０であることを特徴とする請求項８の装置。 - 【請求項１０】 前記第１のバッファ手段及び前記第２
のバッファ手段の前記ステージの数が同一であり且つ一
つの集まりにおけるビット数に等しいことを特徴とする
請求項９の装置。 - 【請求項１１】 前記集まりの各々が、複数のビットか
らなる１つのバイトを含むことを特徴とする請求項１０
の装置。 - 【請求項１２】 符号化対象入力信号を信号源から供給
するステップと、 前記入力信号の確率推定値を供給するステップと、 符号化した信号を発生させるために、前記供給を受けた
入力信号を前記確率推定値に応じて算術的に符号化する
ステップであって、前記入力信号を圧縮データ化した信
号と第１の桁上げ表示子とを発生させるサブステップ
と、前記第１の桁上げ表示子に応じて前記圧縮データ化
した信号を処理するサブステップとを含む、算術的に符
号化するステップと、 前記入力信号の前記符号化した信号を伝送及び、又は記
憶媒体に供給するステップと、 からなる、複数の記号値を有する入力信号の適応符号化
の方法において、 前記処理するサブステップが、 前記第１の桁上げ表示子によって修正された前記圧縮デ
ータ化した信号における第１の種類の連続指定論理信号
の集まりのカウント数を累計するサブステップと、 第１の桁上げが前記カウントされた集まりにおける前記
第１の種類の連続指定論理信号を通して伝搬するかどう
かを表す第２の桁上げ表示子を得るサブステップと、 前記の集まりのカウント数の累計前及び累計後に前記第
１の桁上げによって修正された圧縮データ論理信号の集
まりを出力として記憶し供給するサブステップと、 前記の集まりのカウント数の累計前及び累計後に発生さ
せた前記集まりに前記第２の桁上げ表示子を加えるサブ
ステップと、 前記累計カウント数に等しい数の集まりであってこれら
の集まりの各々が前記第１の種類の連続指定論理信号又
は前記第２の桁上げ表示子に依存する第２の種類の連続
指定論理信号を含むような集まりを出力として供給する
サブステップと、 からなることを特徴とする、複数の記号値を有する入力
信号の適応符号化の方法。 - 【請求項１３】 前記第１の種類の連続指定論理信号が
論理数１であり、前記第２の種類の連続指定論理信号が
論理数０であることを特徴とする請求項１２の方法。 - 【請求項１４】 前記出力として供給するサブステップ
が、前記カウント数に等しい数の集まりを出力として供
給することを含み、これらの数の集まりの各々は前記第
２の桁上げ表示子を補完する指定論理信号を含むことを
特徴とする請求項１３の方法。 - 【請求項１５】 前記第２の桁上げ表示子が、論理数１
である場合には桁上げありを示し、論理数０である場合
には桁上げなしを示すことを特徴とする請求項１４の方
法。 - 【請求項１６】 前記集まりの各々が、予定のビット数
を含むことを特徴とする請求項１５の方法。 - 【請求項１７】 前記予定のビット数が１バイトである
ことを特徴とする請求項１６の方法。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US478335 | 1990-02-12 | ||
| US07/478,335 US4973961A (en) | 1990-02-12 | 1990-02-12 | Method and apparatus for carry-over control in arithmetic entropy coding |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH04227337A JPH04227337A (ja) | 1992-08-17 |
| JPH07123228B2 true JPH07123228B2 (ja) | 1995-12-25 |
Family
ID=23899520
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP3038954A Expired - Lifetime JPH07123228B2 (ja) | 1990-02-12 | 1991-02-12 | 桁上げ制御を用いた適応符号化装置及びその方法 |
Country Status (6)
| Country | Link |
|---|---|
| US (1) | US4973961A (ja) |
| EP (1) | EP0443255B1 (ja) |
| JP (1) | JPH07123228B2 (ja) |
| KR (1) | KR940003199B1 (ja) |
| CA (1) | CA2032127C (ja) |
| DE (1) | DE69029194T2 (ja) |
Families Citing this family (48)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4973961A (en) | 1990-02-12 | 1990-11-27 | At&T Bell Laboratories | Method and apparatus for carry-over control in arithmetic entropy coding |
| KR950013404B1 (ko) * | 1991-11-15 | 1995-11-08 | 미쯔비시덴끼 가부시끼가이샤 | 부호전송장치 |
| CA2077271C (en) * | 1991-12-13 | 1998-07-28 | David J. Craft | Method and apparatus for compressing data |
| US5396228A (en) * | 1992-01-16 | 1995-03-07 | Mobile Telecommunications Technologies | Methods and apparatus for compressing and decompressing paging data |
| DE69320147T2 (de) * | 1992-11-13 | 1999-01-14 | Canon K.K., Tokio/Tokyo | Vorrichtung zur Bildkodierung |
| US5357250A (en) * | 1992-11-20 | 1994-10-18 | International Business Machines Corporation | Adaptive computation of symbol probabilities in n-ary strings |
| JPH06197084A (ja) * | 1992-12-25 | 1994-07-15 | Takayama:Kk | 音声転送方法 |
| JPH06202694A (ja) * | 1992-12-25 | 1994-07-22 | Takayama:Kk | 音声圧縮方法 |
| US5717394A (en) * | 1993-02-10 | 1998-02-10 | Ricoh Company Ltd. | Method and apparatus for encoding and decoding data |
| US5381145A (en) * | 1993-02-10 | 1995-01-10 | Ricoh Corporation | Method and apparatus for parallel decoding and encoding of data |
| US5583500A (en) * | 1993-02-10 | 1996-12-10 | Ricoh Corporation | Method and apparatus for parallel encoding and decoding of data |
| US5533051A (en) * | 1993-03-12 | 1996-07-02 | The James Group | Method for data compression |
| US5563595A (en) * | 1993-12-23 | 1996-10-08 | International Business Machines Corporation | Method and apparatus for compressing data |
| US5471207A (en) * | 1994-02-23 | 1995-11-28 | Ricoh Company Ltd. | Compression of palettized images and binarization for bitwise coding of M-ary alphabets therefor |
| JP3302229B2 (ja) | 1994-09-20 | 2002-07-15 | 株式会社リコー | 符号化方法、符号化／復号方法及び復号方法 |
| US6549666B1 (en) | 1994-09-21 | 2003-04-15 | Ricoh Company, Ltd | Reversible embedded wavelet system implementation |
| US5881176A (en) | 1994-09-21 | 1999-03-09 | Ricoh Corporation | Compression and decompression with wavelet style and binary style including quantization by device-dependent parser |
| US6873734B1 (en) | 1994-09-21 | 2005-03-29 | Ricoh Company Ltd | Method and apparatus for compression using reversible wavelet transforms and an embedded codestream |
| US6229927B1 (en) | 1994-09-21 | 2001-05-08 | Ricoh Company, Ltd. | Reversible embedded wavelet system implementation |
| JP3409552B2 (ja) * | 1995-12-27 | 2003-05-26 | 三菱電機株式会社 | ディジタル情報符号化装置、ディジタル情報復号化装置、及びディジタル情報符号化・復号化装置 |
| US5818369A (en) * | 1996-03-07 | 1998-10-06 | Pegasus Imaging Corporation | Rapid entropy coding for data compression or decompression |
| JPH09298668A (ja) * | 1996-05-07 | 1997-11-18 | Mitsubishi Electric Corp | ディジタル情報符号化装置、ディジタル情報復号化装置、ディジタル情報符号化・復号化装置、ディジタル情報符号化方法、及びディジタル情報復号化方法 |
| JP3621512B2 (ja) * | 1996-06-19 | 2005-02-16 | 株式会社ルネサステクノロジ | ディジタル情報符号化装置、ディジタル情報復号化装置、ディジタル情報符号化・復号化装置、ディジタル情報符号化方法、及びディジタル情報復号化方法 |
| US6055338A (en) * | 1996-08-22 | 2000-04-25 | Sumitomo Metal Industries Limited | Bi-level adaptive coding using a dual port memory and a context comparator |
| US6058216A (en) * | 1996-09-03 | 2000-05-02 | Sumitomo Metal Industries Limited | Apparatus for encoding image data |
| KR100316783B1 (ko) * | 1996-11-09 | 2002-01-12 | 윤종용 | 산술부호화 비트스트림 분할방법 및 부호화 방식 혼용 비트스트림 생성방법 |
| US5955977A (en) * | 1997-03-31 | 1999-09-21 | Sharp Laboratories Of America, Inc. | System for avoiding start code emulation and long carry-over propagation |
| CN1249473A (zh) | 1998-09-30 | 2000-04-05 | 朗迅科技公司 | 无乘法的算术编码 |
| JP2002064715A (ja) | 2000-08-14 | 2002-02-28 | Canon Inc | データ処理装置および方法 |
| CN100459489C (zh) * | 2000-11-29 | 2009-02-04 | 朗迅科技公司 | 可变大小的密钥以及使用该密钥的方法和装置 |
| KR100405819B1 (ko) * | 2001-01-15 | 2003-11-14 | 한국과학기술원 | 이진 영상의 데이터 압축 및 복원방법 |
| US6898323B2 (en) * | 2001-02-15 | 2005-05-24 | Ricoh Company, Ltd. | Memory usage scheme for performing wavelet processing |
| US6859563B2 (en) | 2001-03-30 | 2005-02-22 | Ricoh Co., Ltd. | Method and apparatus for decoding information using late contexts |
| US6950558B2 (en) * | 2001-03-30 | 2005-09-27 | Ricoh Co., Ltd. | Method and apparatus for block sequential processing |
| US7062101B2 (en) | 2001-03-30 | 2006-06-13 | Ricoh Co., Ltd. | Method and apparatus for storing bitplanes of coefficients in a reduced size memory |
| US7006697B1 (en) | 2001-03-30 | 2006-02-28 | Ricoh Co., Ltd. | Parallel block MQ arithmetic image compression of wavelet transform coefficients |
| US6895120B2 (en) | 2001-03-30 | 2005-05-17 | Ricoh Co., Ltd. | 5,3 wavelet filter having three high pair and low pair filter elements with two pairs of cascaded delays |
| US7581027B2 (en) | 2001-06-27 | 2009-08-25 | Ricoh Co., Ltd. | JPEG 2000 for efficent imaging in a client/server environment |
| US7280252B1 (en) | 2001-12-19 | 2007-10-09 | Ricoh Co., Ltd. | Error diffusion of multiresolutional representations |
| US7095907B1 (en) | 2002-01-10 | 2006-08-22 | Ricoh Co., Ltd. | Content and display device dependent creation of smaller representation of images |
| US7120305B2 (en) | 2002-04-16 | 2006-10-10 | Ricoh, Co., Ltd. | Adaptive nonlinear image enlargement using wavelet transform coefficients |
| US6714145B1 (en) | 2002-09-26 | 2004-03-30 | Richard Marques | Method and apparatus for integer-based encoding and decoding of bits |
| US8176155B2 (en) * | 2003-11-26 | 2012-05-08 | Riip, Inc. | Remote network management system |
| US7161507B2 (en) * | 2004-08-20 | 2007-01-09 | 1St Works Corporation | Fast, practically optimal entropy coding |
| US7265691B2 (en) * | 2005-06-23 | 2007-09-04 | 1Stworks Corporation | Modeling for enumerative encoding |
| CN108683916B (zh) | 2012-01-20 | 2021-09-07 | 韩国电子通信研究院 | 使用量化矩阵的视频编解码方法 |
| US8779950B2 (en) | 2012-03-05 | 2014-07-15 | Dcba, Llc | Command encoded data compression |
| US9543980B2 (en) | 2014-10-10 | 2017-01-10 | Massachusettes Institute Of Technology | Systems and methods for model-free compression and model-based decompression |
Citations (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4973961A (en) | 1990-02-12 | 1990-11-27 | At&T Bell Laboratories | Method and apparatus for carry-over control in arithmetic entropy coding |
Family Cites Families (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4463342A (en) * | 1979-06-14 | 1984-07-31 | International Business Machines Corporation | Method and means for carry-over control in the high order to low order pairwise combining of digits of a decodable set of relatively shifted finite number strings |
| US4437087A (en) * | 1982-01-27 | 1984-03-13 | Bell Telephone Laboratories, Incorporated | Adaptive differential PCM coding |
| US4549304A (en) * | 1983-11-28 | 1985-10-22 | Northern Telecom Limited | ADPCM Encoder/decoder with signalling bit insertion |
-
1990
- 1990-02-12 US US07/478,335 patent/US4973961A/en not_active Expired - Lifetime
- 1990-12-12 CA CA002032127A patent/CA2032127C/en not_active Expired - Lifetime
- 1990-12-13 DE DE69029194T patent/DE69029194T2/de not_active Expired - Lifetime
- 1990-12-13 EP EP90313602A patent/EP0443255B1/en not_active Expired - Lifetime
-
1991
- 1991-02-07 KR KR1019910002066A patent/KR940003199B1/ko not_active Expired - Lifetime
- 1991-02-12 JP JP3038954A patent/JPH07123228B2/ja not_active Expired - Lifetime
Patent Citations (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4973961A (en) | 1990-02-12 | 1990-11-27 | At&T Bell Laboratories | Method and apparatus for carry-over control in arithmetic entropy coding |
Also Published As
| Publication number | Publication date |
|---|---|
| EP0443255B1 (en) | 1996-11-20 |
| CA2032127C (en) | 1995-04-18 |
| US4973961A (en) | 1990-11-27 |
| EP0443255A3 (ja) | 1994-01-19 |
| KR940003199B1 (ko) | 1994-04-15 |
| JPH04227337A (ja) | 1992-08-17 |
| DE69029194T2 (de) | 1997-03-20 |
| DE69029194D1 (de) | 1997-01-02 |
| EP0443255A2 (en) | 1991-08-28 |
| KR910016155A (ko) | 1991-09-30 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JPH07123228B2 (ja) | 桁上げ制御を用いた適応符号化装置及びその方法 | |
| JP7545406B2 (ja) | エントロピコーディングにおいて等確率シンボルをハンドリングするための方法およびデバイス | |
| JP2915568B2 (ja) | テープドライブシステムのための適応データ圧縮装置 | |
| TW315547B (ja) | ||
| JPS6261178B2 (ja) | ||
| JPH04280516A (ja) | エンコード方法及び装置 | |
| Slattery et al. | The qx-coder | |
| US5404166A (en) | Variable-length to fixed-length data word reformatting apparatus | |
| TWI273779B (en) | Method and apparatus for optimized lossless compression using a plurality of coders | |
| US6094151A (en) | Apparatus and method for finite state machine coding of information selecting most probable state subintervals | |
| EP0260461B1 (en) | Arithmetic coding encoding and decoding method | |
| EP0783225A3 (en) | Digital information encoding/decoding apparatus and method | |
| JPH11511306A (ja) | 大ギャップを有するスライド窓データ圧縮システム | |
| CN113141508B (zh) | 算术编码器及实现算术编码的方法和图像编码方法 | |
| CN110191341B (zh) | 一种深度数据的编码方法和解码方法 | |
| CA2392644C (en) | Coding and decoding apparatus of key data for graphic animation and method thereof | |
| JPS6352812B2 (ja) | ||
| JPS60251763A (ja) | フアクシミリ情報の拡大縮小回路 | |
| JP2891818B2 (ja) | 符号化装置 | |
| KR0178891B1 (ko) | 실시간 가변장 부호화 회로 | |
| JP3868148B2 (ja) | 符号データ出力装置 | |
| Cena et al. | A Q-Coder algorithm with carry free addition | |
| JP2719222B2 (ja) | 算術符号化装置 | |
| CN117857837A (zh) | 一种实现8k 120fpssdi信号传输的方法及系统 | |
| JP2790755B2 (ja) | ファクシミリ装置 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20071225 Year of fee payment: 12 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20081225 Year of fee payment: 13 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20081225 Year of fee payment: 13 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20091225 Year of fee payment: 14 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20101225 Year of fee payment: 15 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20101225 Year of fee payment: 15 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20111225 Year of fee payment: 16 |
|
| EXPY | Cancellation because of completion of term | ||
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20111225 Year of fee payment: 16 |