JPH08242177A - 入力シンボルの２進算術符号化方法及びその装置 - Google Patents
入力シンボルの２進算術符号化方法及びその装置Info
- Publication number
- JPH08242177A JPH08242177A JP7306753A JP30675395A JPH08242177A JP H08242177 A JPH08242177 A JP H08242177A JP 7306753 A JP7306753 A JP 7306753A JP 30675395 A JP30675395 A JP 30675395A JP H08242177 A JPH08242177 A JP H08242177A
- Authority
- JP
- Japan
- Prior art keywords
- context
- binary
- bit
- symbol
- contexts
- 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.)
- Pending
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
- G06F7/38—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation
-
- 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)
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Computational Mathematics (AREA)
- Computing Systems (AREA)
- Mathematical Analysis (AREA)
- Mathematical Optimization (AREA)
- Pure & Applied Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- Compression, Expansion, Code Conversion, And Decoders (AREA)
Abstract
(57)【要約】
【課題】 入力シンボルの統計的特性を十分用いる２
進算術符号化方法及びその装置を提供する。 【解決手段】 入力シンボルをＭビットの２進シンボ
ルに変換する過程と、複数のコンテキストのうちで、Ｍ
ビットの２進シンボルの各々に対応し、２進シンボルの
異なる確率的モデルを各々表すＭ個のコンテキストを選
択する過程と、２進算術符号化方法を用いて、対応する
コンテキストに応じて、Ｍビットの２進シンボルの各々
を順次的に符号化する過程とからなる。
進算術符号化方法及びその装置を提供する。 【解決手段】 入力シンボルをＭビットの２進シンボ
ルに変換する過程と、複数のコンテキストのうちで、Ｍ
ビットの２進シンボルの各々に対応し、２進シンボルの
異なる確率的モデルを各々表すＭ個のコンテキストを選
択する過程と、２進算術符号化方法を用いて、対応する
コンテキストに応じて、Ｍビットの２進シンボルの各々
を順次的に符号化する過程とからなる。
Description
【０００１】
【発明の属する技術分野】本発明は、データの圧縮のた
めに２進算術符号化を採用する装置及びその方法に関
し、特に、ツリー構造の２進算術符号化方法を用いて多
重値の入力シンボルを符号化するための装置及びその方
法に関する。
めに２進算術符号化を採用する装置及びその方法に関
し、特に、ツリー構造の２進算術符号化方法を用いて多
重値の入力シンボルを符号化するための装置及びその方
法に関する。
【０００２】
【従来の技術】一般に、算術符号化方法は、理想的な符
号化方法においてシンボル当たり平均符号の長さを表す
エントローピ限界に近接する可変長符号化方法のうちの
一つである。この算術符号化方法においては、入力シン
ボルは０から１までの確率区間にエンコーダ、デコーダ
の両方にて公知の順番で整列される。算術符号化の目的
は、符号化されるべき入力シンボルに対応する区間を表
す２進の符号ストリームを作り出すことである。複数の
シンボルを符号化することは、確率区間を特定シンボル
の確率に比例して、だんだん小さいサブ区間に細分化し
て行く過程である。符号ストリームが対応するシンボル
に割り当てられたサブ区間の外側を指さない限り、デコ
ーダは元の入力シンボルを復元することができる。サブ
区間に細分化する過程が続ければ続くほど、サブ区間の
長さはだんだん小さくなり、サブ区間の長さ（通常、Ａ
と称する）及び符号ストリームを指す現在の位置（通
常、Ｃと称する）に対して更に高い精度が要求される。
その結果、Ａがある最小値以下に落ちるたびに、区間再
調整またはＡ及びＣの再標準化が行われる。
号化方法においてシンボル当たり平均符号の長さを表す
エントローピ限界に近接する可変長符号化方法のうちの
一つである。この算術符号化方法においては、入力シン
ボルは０から１までの確率区間にエンコーダ、デコーダ
の両方にて公知の順番で整列される。算術符号化の目的
は、符号化されるべき入力シンボルに対応する区間を表
す２進の符号ストリームを作り出すことである。複数の
シンボルを符号化することは、確率区間を特定シンボル
の確率に比例して、だんだん小さいサブ区間に細分化し
て行く過程である。符号ストリームが対応するシンボル
に割り当てられたサブ区間の外側を指さない限り、デコ
ーダは元の入力シンボルを復元することができる。サブ
区間に細分化する過程が続ければ続くほど、サブ区間の
長さはだんだん小さくなり、サブ区間の長さ（通常、Ａ
と称する）及び符号ストリームを指す現在の位置（通
常、Ｃと称する）に対して更に高い精度が要求される。
その結果、Ａがある最小値以下に落ちるたびに、区間再
調整またはＡ及びＣの再標準化が行われる。
【０００３】一般的に、算術符号化器への入力は多重値
のシンボルである。一方、ＪＰＥＧ（Joint Photograpi
c Experts Group)のような標準映像処理方式において
は、２進算術符号化方法が採択された。２進算術符号化
方法は入力シンボルが２つの値のみを有することを除い
ては、前述したもののように同一に行われる。この２進
算術符号化方法は、より効率的実施のため選択される。
例えば、２進入力シンボルを用いることは、掛け算を行
うことなく区間再調整を簡単に実現することができる。
のシンボルである。一方、ＪＰＥＧ（Joint Photograpi
c Experts Group)のような標準映像処理方式において
は、２進算術符号化方法が採択された。２進算術符号化
方法は入力シンボルが２つの値のみを有することを除い
ては、前述したもののように同一に行われる。この２進
算術符号化方法は、より効率的実施のため選択される。
例えば、２進入力シンボルを用いることは、掛け算を行
うことなく区間再調整を簡単に実現することができる。
【０００４】入力が二つの値を有するシンボルに限定さ
れる場合、多重値のシンボルを一連の２進シンボルに変
換する必要がある。
れる場合、多重値のシンボルを一連の２進シンボルに変
換する必要がある。
【０００５】２進算術符号化方法を用いる従来のエンコ
ーダにおいては、多重値のの入力シンボルが一連の２進
シンボルに変換された後、２進算術符号化方法を用いて
符号化される。
ーダにおいては、多重値のの入力シンボルが一連の２進
シンボルに変換された後、２進算術符号化方法を用いて
符号化される。
【０００６】図１には、その入力が多重値のシンボルの
場合、２進算術符号化器を用いる従来のエンコーダ１を
説明するためのブロック図が示されている。下記の表１
には、図１のエンコーダ１に用いられる入力シンボル値
と、変換された一連の２進シンボル値とが示されてい
る。
場合、２進算術符号化器を用いる従来のエンコーダ１を
説明するためのブロック図が示されている。下記の表１
には、図１のエンコーダ１に用いられる入力シンボル値
と、変換された一連の２進シンボル値とが示されてい
る。
【０００７】
【表１】
【０００８】上記表１に示したように、入力シンボル
は、０〜６の範囲にある整数値であると仮定して、この
入力シンボルは３ビットの２進シンボルに変換される。
入力シンボル値の可能な場合の数がＮ個である場合（Ｎ
は２M-1＜Ｎ＜２Mの範囲にある）、多重値の入力シンボ
ルはＭビットの２進シンボルに変換される。ここで、各
々のビットは２進算術符号化方法を用いて符号化され
る。
は、０〜６の範囲にある整数値であると仮定して、この
入力シンボルは３ビットの２進シンボルに変換される。
入力シンボル値の可能な場合の数がＮ個である場合（Ｎ
は２M-1＜Ｎ＜２Mの範囲にある）、多重値の入力シンボ
ルはＭビットの２進シンボルに変換される。ここで、各
々のビットは２進算術符号化方法を用いて符号化され
る。
【０００９】与えられた入力シンボルに対する実際の符
号化またはマッピング過程は、該入力シンボルの統計的
な特性に依存する。即ち、符号化過程に用いられるパラ
メータは、入力シンボルの特性に応じて変わる。一つの
多重値の入力シンボルを表す一連の２進シンボルにおい
て、各々のビットは互いに異なる統計的な特性を有し、
各々の２進シンボルには各々異なる符号化過程が適用さ
れる。従って、３ビット（Ｂ2，Ｂ1，Ｂ0）の各々は、
２進算術符号化器にて、互いに異なる統計的なモデルま
たはコンテキストによって符号化される。このコンテキ
ストは、２進算術符号化器で用いられる決定確率のテー
ブルに対するインデックスを指称するものであって、区
間長さＡに関連されている。
号化またはマッピング過程は、該入力シンボルの統計的
な特性に依存する。即ち、符号化過程に用いられるパラ
メータは、入力シンボルの特性に応じて変わる。一つの
多重値の入力シンボルを表す一連の２進シンボルにおい
て、各々のビットは互いに異なる統計的な特性を有し、
各々の２進シンボルには各々異なる符号化過程が適用さ
れる。従って、３ビット（Ｂ2，Ｂ1，Ｂ0）の各々は、
２進算術符号化器にて、互いに異なる統計的なモデルま
たはコンテキストによって符号化される。このコンテキ
ストは、２進算術符号化器で用いられる決定確率のテー
ブルに対するインデックスを指称するものであって、区
間長さＡに関連されている。
【００１０】図１においては、多重値の入力シンボル
は、２進変換器１０にて３ビットの２進シンボルに変換
され、２進算術符号化器のＢＡＣ３０へ順次に入力され
る。三つの異なるコンテキスト（例えば、０、１、２）
は３ビットＢ2，Ｂ1，Ｂ0を各々符号化するに用いられ
る。即ち、第１ビットＢ2は、コンテキスト０にて符号
化される。
は、２進変換器１０にて３ビットの２進シンボルに変換
され、２進算術符号化器のＢＡＣ３０へ順次に入力され
る。三つの異なるコンテキスト（例えば、０、１、２）
は３ビットＢ2，Ｂ1，Ｂ0を各々符号化するに用いられ
る。即ち、第１ビットＢ2は、コンテキスト０にて符号
化される。
【００１１】前述した従来のエンコーダ１においては、
ビットＢ1に対するコンテキストはビットＢ2に関係なく
予め定められている。つまり、ビットＢ2が０であるか
１であるかは、ビットＢ1及びＢ0に対するコンテキスト
には関連がない。しかし、映像信号のような一般的な入
力データに対して、この３ビットは互いに相関関係を有
している。従って、符号化効率の見地では、他の２進シ
ンボルに関係なく同じコンテキストを用いる代わりに、
その相関関係が利用できる符号化方法を用いることが好
ましいといえよう。
ビットＢ1に対するコンテキストはビットＢ2に関係なく
予め定められている。つまり、ビットＢ2が０であるか
１であるかは、ビットＢ1及びＢ0に対するコンテキスト
には関連がない。しかし、映像信号のような一般的な入
力データに対して、この３ビットは互いに相関関係を有
している。従って、符号化効率の見地では、他の２進シ
ンボルに関係なく同じコンテキストを用いる代わりに、
その相関関係が利用できる符号化方法を用いることが好
ましいといえよう。
【００１２】
【発明が解決しようとする課題】従って、本発明の主な
目的は、入力シンボルの統計的特性を十分用いる２進算
術符号化方法を採用する符号化装置及びその方法を提供
することである。
目的は、入力シンボルの統計的特性を十分用いる２進算
術符号化方法を採用する符号化装置及びその方法を提供
することである。
【００１３】
【課題を解決するための手段】上記の目的を達成するた
めに、本発明によれは、Ｎ個の値を有する入力シンボル
を符号化する方法（Ｎは２M-1＜Ｎ＜２Mの範囲にあり、
Ｍは正の整数である）であって、
めに、本発明によれは、Ｎ個の値を有する入力シンボル
を符号化する方法（Ｎは２M-1＜Ｎ＜２Mの範囲にあり、
Ｍは正の整数である）であって、
【００１４】前記入力シンボルをＭビットの２進シンボ
ルに変換する第１過程と、
ルに変換する第１過程と、
【００１５】複数のコンテキストのうちで、前記Ｍビッ
トの２進シンボルの各々に対応し、前記２進シンボルの
異なる確率的モデルを各々表すＭ個のコンテキストを選
択する過程であって、前記複数のコンテキストはＭ個の
コンテキストグループに分けられ、ｋ番目の前記コンテ
キストグループは２K-1個のコンテキストを有し（ｋは
１〜Ｍの範囲にある任意の整数）、より大きいｋ値は前
記２進シンボルの上位ビットを表し、前記２進シンボル
の１番目のビットに対応するコンテキストは１番目のコ
ンテキストグループに含まれて、Ｌ番目（Ｌは２〜Ｍの
範囲にある任意の整数）のビットに対応するコンテキス
トを前記Ｌ番目のビットの上位ビットに応じて、Ｌ番目
のコンテキストグループのうちで選択する第２過程と、
トの２進シンボルの各々に対応し、前記２進シンボルの
異なる確率的モデルを各々表すＭ個のコンテキストを選
択する過程であって、前記複数のコンテキストはＭ個の
コンテキストグループに分けられ、ｋ番目の前記コンテ
キストグループは２K-1個のコンテキストを有し（ｋは
１〜Ｍの範囲にある任意の整数）、より大きいｋ値は前
記２進シンボルの上位ビットを表し、前記２進シンボル
の１番目のビットに対応するコンテキストは１番目のコ
ンテキストグループに含まれて、Ｌ番目（Ｌは２〜Ｍの
範囲にある任意の整数）のビットに対応するコンテキス
トを前記Ｌ番目のビットの上位ビットに応じて、Ｌ番目
のコンテキストグループのうちで選択する第２過程と、
【００１６】２進算術符号化方法を用いて、前記対応す
るコンテキストに応じて、前記Ｍビットの２進シンボル
の各々を順次的に符号化する第３過程とを含むことを特
徴とする。
るコンテキストに応じて、前記Ｍビットの２進シンボル
の各々を順次的に符号化する第３過程とを含むことを特
徴とする。
【００１７】
【発明の実施の形態】以下、本発明の好適な実施例につ
いて図面を参照しながらより詳しく説明する。
いて図面を参照しながらより詳しく説明する。
【００１８】図２には、図１（または、表１）に示した
ような多重値の入力シンボルが用いられる本発明のエン
コーダ２を説明するためのブロック図が示されている。
本発明のエンコーダ２においては、多重値の入力シンボ
ルを２進シンボルに変換することは、グループ分けブロ
ック１００にて行われる。このグループ分け過程は、表
１に示された２進変換と根本的に類似である。多様な形
態の入力シンボルに対しては異なるグループ分け方法が
用いられる。要するに、入力シンボルをグループインデ
ックスビットに写像する過程であって、第１のグループ
分け過程にて全ての可能な入力シンボル値は２つのサブ
グループに分られ、その中の上位グループはグループイ
ンデックスビット１と示され、下位グループはグループ
インデックスビット０と示される。後続するグループ分
け過程にて、一つのサブグループに含まれたシンボル値
はサブグループ当たり、一つ以下のシンボル値が含まれ
るように更に細分化される。図２に示されたエンコーダ
２では３グループインデックスビット（Ｂ2，Ｂ1，
Ｂ0）が用いられる。第１グループインデックスビット
Ｂ2は、第１のグループ分け過程にて入力シンボルが上
位グループに属するかまたは下位グループに属するかを
示す。他のグループインデックスビットは、後続するグ
ループ分け過程に連関される。
ような多重値の入力シンボルが用いられる本発明のエン
コーダ２を説明するためのブロック図が示されている。
本発明のエンコーダ２においては、多重値の入力シンボ
ルを２進シンボルに変換することは、グループ分けブロ
ック１００にて行われる。このグループ分け過程は、表
１に示された２進変換と根本的に類似である。多様な形
態の入力シンボルに対しては異なるグループ分け方法が
用いられる。要するに、入力シンボルをグループインデ
ックスビットに写像する過程であって、第１のグループ
分け過程にて全ての可能な入力シンボル値は２つのサブ
グループに分られ、その中の上位グループはグループイ
ンデックスビット１と示され、下位グループはグループ
インデックスビット０と示される。後続するグループ分
け過程にて、一つのサブグループに含まれたシンボル値
はサブグループ当たり、一つ以下のシンボル値が含まれ
るように更に細分化される。図２に示されたエンコーダ
２では３グループインデックスビット（Ｂ2，Ｂ1，
Ｂ0）が用いられる。第１グループインデックスビット
Ｂ2は、第１のグループ分け過程にて入力シンボルが上
位グループに属するかまたは下位グループに属するかを
示す。他のグループインデックスビットは、後続するグ
ループ分け過程に連関される。
【００１９】グループインデックスビット（Ｂ2，Ｂ1，
Ｂ0）は、順次的にＢＡＣ１１０へ供給される。本発明
において、ビットＢ1及びＢ0に対するコンテキストは、
図１の従来のエンコーダ１でのように予め定められたも
のではなく、コンテキスト選択ブロック１２０にて決定
される。このコンテキストは、対応するグループインデ
ックスビットＢ1、Ｂ0と共にＢＡＣ１１０へ供給され
る。
Ｂ0）は、順次的にＢＡＣ１１０へ供給される。本発明
において、ビットＢ1及びＢ0に対するコンテキストは、
図１の従来のエンコーダ１でのように予め定められたも
のではなく、コンテキスト選択ブロック１２０にて決定
される。このコンテキストは、対応するグループインデ
ックスビットＢ1、Ｂ0と共にＢＡＣ１１０へ供給され
る。
【００２０】図２のエンコーダ２においては、Ｂ2は予
め定められたコンテキスト（例えば、０）によってＢＡ
Ｃ１１０にて符号化される。しかし、２番目のビットＢ
1を符号化するためのコンテキストは、Ｂ1の上位ビット
のＢ2に応じて、コンテキスト選択ブロック１２０にて
決定される。例えば、Ｂ2が１であれば、Ｂ1のコンテキ
ストは４で、Ｂ2が０であれば、Ｂ1のコンテキストは１
である。第３のビットＢ0も同様である。第３のビット
Ｂ0を符号化するためのコンテキストは、Ｂ0の上位ビッ
トのＢ2及びＢ1に応じてコンテキスト選択ブロック１２
０にて決定される。図３は、前述したコンテキスト選択
方法を説明するためのツリー構造の模式図である。Ｂ1
に対するコンテキストが１であれば、２または３がＢ0
のコンテキストとして選択され得るし、５または６は選
択され得ない。反対に、Ｂ1に対するコンテキストが４
であれば、５または６がＢ0のコンテキストとして選択
され得るし、２または３は選択され得ない。要するに、
ある入力ビットに対するコンテキストは、該入力ビット
の上位ビットによって図３に示したように階層的に決定
される。
め定められたコンテキスト（例えば、０）によってＢＡ
Ｃ１１０にて符号化される。しかし、２番目のビットＢ
1を符号化するためのコンテキストは、Ｂ1の上位ビット
のＢ2に応じて、コンテキスト選択ブロック１２０にて
決定される。例えば、Ｂ2が１であれば、Ｂ1のコンテキ
ストは４で、Ｂ2が０であれば、Ｂ1のコンテキストは１
である。第３のビットＢ0も同様である。第３のビット
Ｂ0を符号化するためのコンテキストは、Ｂ0の上位ビッ
トのＢ2及びＢ1に応じてコンテキスト選択ブロック１２
０にて決定される。図３は、前述したコンテキスト選択
方法を説明するためのツリー構造の模式図である。Ｂ1
に対するコンテキストが１であれば、２または３がＢ0
のコンテキストとして選択され得るし、５または６は選
択され得ない。反対に、Ｂ1に対するコンテキストが４
であれば、５または６がＢ0のコンテキストとして選択
され得るし、２または３は選択され得ない。要するに、
ある入力ビットに対するコンテキストは、該入力ビット
の上位ビットによって図３に示したように階層的に決定
される。
【００２１】例えば、ビット「００１」を符号化するた
めには、コンテキスト０、１及び２が用いられる。ま
た、「１０１」に対してはコンテキスト０、４及び５が
用いられる。表２には表１に示したように、入力シンボ
ルに対して対応するグループインデックスビットとコン
テキストとの組み合わせが示されている。
めには、コンテキスト０、１及び２が用いられる。ま
た、「１０１」に対してはコンテキスト０、４及び５が
用いられる。表２には表１に示したように、入力シンボ
ルに対して対応するグループインデックスビットとコン
テキストとの組み合わせが示されている。
【００２２】
【表２】
【００２３】第２のビットＢ1は、入力シンボル１に対
してはコンテキスト１を、入力シンボル５に対してはコ
ンテキスト４を各々用いて符号化される。本発明のエン
コーダ２で用いられるコンテキストの総数は、図１に示
した従来のエンコーダ１のものより多い。
してはコンテキスト１を、入力シンボル５に対してはコ
ンテキスト４を各々用いて符号化される。本発明のエン
コーダ２で用いられるコンテキストの総数は、図１に示
した従来のエンコーダ１のものより多い。
【００２４】しかしながら、多様なコンテキストを用い
ることによって入力シンボルの統計的な特性を十分用い
ることができ、これによって、より一層効果的な符号化
が得られる。
ることによって入力シンボルの統計的な特性を十分用い
ることができ、これによって、より一層効果的な符号化
が得られる。
【００２５】グループインデックスビットは、前述した
ように決定されたコンテキストに応じてＢＡＣ１１０に
て符号化される。後続する入力シンボルは、本発明のエ
ンコーダ２で前述したような方式にて符号化されること
によって、符号化された出力シンボルを供給する。
ように決定されたコンテキストに応じてＢＡＣ１１０に
て符号化される。後続する入力シンボルは、本発明のエ
ンコーダ２で前述したような方式にて符号化されること
によって、符号化された出力シンボルを供給する。
【００２６】図４〜図６には、図２に示した本発明のエ
ンコーダ２にて行われる符号化過程を説明するためのフ
ローチャートが示されている。
ンコーダ２にて行われる符号化過程を説明するためのフ
ローチャートが示されている。
【００２７】サブルーチンＴＳＡＣ＿ＥＮＣＯＤＥ（Ｖ
ＡＬＵＥ、ＨＡＬＦ、ＣＯＮＴＥＸＴ）は、一つの多重
値の入力シンボルを符号化するための過程を示すもので
あって、ＶＡＬＵＥは、入力シンボルの値を、ＣＯＮＴ
ＥＸＴは第１グループインデックスビットを符号化する
ための初期コンテキストを各々表す。簡略化のため、初
期コンテキスト値を０と仮定した。入力シンボルは複数
の整数値（例えば、０〜６）を有することと仮定した。
しかし、入力シンボルが例えば、０．００１、０．０１
３、０．０２５などのように整形化されていない値を有
する場合に、各々の値を０からＮ−１までの任意の整数
にマッピングすることによって同一の過程を適用するこ
とができる。ここで、Ｎは可能な入力値の個数である。
ＡＬＵＥ、ＨＡＬＦ、ＣＯＮＴＥＸＴ）は、一つの多重
値の入力シンボルを符号化するための過程を示すもので
あって、ＶＡＬＵＥは、入力シンボルの値を、ＣＯＮＴ
ＥＸＴは第１グループインデックスビットを符号化する
ための初期コンテキストを各々表す。簡略化のため、初
期コンテキスト値を０と仮定した。入力シンボルは複数
の整数値（例えば、０〜６）を有することと仮定した。
しかし、入力シンボルが例えば、０．００１、０．０１
３、０．０２５などのように整形化されていない値を有
する場合に、各々の値を０からＮ−１までの任意の整数
にマッピングすることによって同一の過程を適用するこ
とができる。ここで、Ｎは可能な入力値の個数である。
【００２８】入力値の個数が２M-1より大きく２Mより小
さい場合、変数ＨＡＬＦは２Mー1を表す。０〜６の入力
シンボルに対してＨＡＬＦは４である。全コンテキスト
の個数は（２＊ＨＡＬＦ−１）である。図４〜図６に示
された過程は入力シンボル１及び５に対して説明され
る。
さい場合、変数ＨＡＬＦは２Mー1を表す。０〜６の入力
シンボルに対してＨＡＬＦは４である。全コンテキスト
の個数は（２＊ＨＡＬＦ−１）である。図４〜図６に示
された過程は入力シンボル１及び５に対して説明され
る。
【００２９】図５及び図６において、ＣＯＤＥ＿０（Ｃ
ＯＮＴＥＸＴ）は入力シンボル値０のグループインデッ
クスビットを与えられたコンテキストにて符号化するサ
ブルーチンを、ＣＯＤＥ＿１（ＣＯＮＴＥＸＴ）は、入
力シンボル値１のグループインデックスビットを与えら
れたコンテキストにて符号化するサブルーチンを各々表
し、ＣＯＤＥ＿０１（ＶＡＬＵＥ、ＣＯＮＴＥＸＴ）
は、ＶＡＬＵＥが０の場合はＣＯＤＥ＿０（ＣＯＮＴＥ
ＸＴ）を呼出し、ＶＡＬＵＥが１の場合にはＣＯＤＥ＿
１（ＣＯＮＴＥＸ）を呼出すサブルーチンを表す。
ＯＮＴＥＸＴ）は入力シンボル値０のグループインデッ
クスビットを与えられたコンテキストにて符号化するサ
ブルーチンを、ＣＯＤＥ＿１（ＣＯＮＴＥＸＴ）は、入
力シンボル値１のグループインデックスビットを与えら
れたコンテキストにて符号化するサブルーチンを各々表
し、ＣＯＤＥ＿０１（ＶＡＬＵＥ、ＣＯＮＴＥＸＴ）
は、ＶＡＬＵＥが０の場合はＣＯＤＥ＿０（ＣＯＮＴＥ
ＸＴ）を呼出し、ＶＡＬＵＥが１の場合にはＣＯＤＥ＿
１（ＣＯＮＴＥＸ）を呼出すサブルーチンを表す。
【００３０】最初に、ステップＳ２０においては、入力
シンボル値が上位グループに属するか下位グループに属
するかが判定される。第１のグループ分け過程にて下位
グループに属する入力シンボル１に対して、ＶＡＬＵＥ
はＨＡＬＦより小さく、ステップＳ２２ではサブルーチ
ンＴＳＡＣ＿ＥＮＣＯＤＥ＿０（１、２、０）がＨＡＬ
Ｆ値が２つの値に分けられて呼出される。ＴＳＡＣ＿Ｅ
ＮＣＯＤＥ＿０（１、２、０）において、第１グループ
インデックスビットはステップＳ３０にてＣＯＤＥ＿０
（０）によって符号化される。ステップＳ３２において
は、グループ分け過程が引き続いて必要であるかを判定
される。ＨＡＬＦが１の場合、ＶＡＬＵＥは二つの値
（即ち、０及び１）の中の何れか一つのみを有し、ステ
ップＳ３４にてサブルーチンＣＯＤＥ＿０１（ＶＡＬＵ
Ｅ、ＣＯＮＴＥＸＴ＋１）を用いて符号化される。しか
し、現在のＨＡＬＦの値は２であるため、ステップＳ３
６にてＶＡＬＵＥは再びＨＡＬＦと比較されて、サブル
ーチンＴＳＡＣ＿ＥＮＣＯＤＥ＿０（１、１、１）はス
テップＳ３８にて再度呼出される。以後過程は、ステッ
プＳ３０へ進んで、第２グループインデックスビットを
符号化するＣＯＤＥ＿０（１）が呼出された後、ステッ
プＳ３２へ進む。ここでＨＡＬＦは１であって、ステッ
プＳ３４にて第３グループインデックスビットを符号化
するＣＯＤＥ＿０１（１、２）が呼出されて符号化過程
が終了される。
シンボル値が上位グループに属するか下位グループに属
するかが判定される。第１のグループ分け過程にて下位
グループに属する入力シンボル１に対して、ＶＡＬＵＥ
はＨＡＬＦより小さく、ステップＳ２２ではサブルーチ
ンＴＳＡＣ＿ＥＮＣＯＤＥ＿０（１、２、０）がＨＡＬ
Ｆ値が２つの値に分けられて呼出される。ＴＳＡＣ＿Ｅ
ＮＣＯＤＥ＿０（１、２、０）において、第１グループ
インデックスビットはステップＳ３０にてＣＯＤＥ＿０
（０）によって符号化される。ステップＳ３２において
は、グループ分け過程が引き続いて必要であるかを判定
される。ＨＡＬＦが１の場合、ＶＡＬＵＥは二つの値
（即ち、０及び１）の中の何れか一つのみを有し、ステ
ップＳ３４にてサブルーチンＣＯＤＥ＿０１（ＶＡＬＵ
Ｅ、ＣＯＮＴＥＸＴ＋１）を用いて符号化される。しか
し、現在のＨＡＬＦの値は２であるため、ステップＳ３
６にてＶＡＬＵＥは再びＨＡＬＦと比較されて、サブル
ーチンＴＳＡＣ＿ＥＮＣＯＤＥ＿０（１、１、１）はス
テップＳ３８にて再度呼出される。以後過程は、ステッ
プＳ３０へ進んで、第２グループインデックスビットを
符号化するＣＯＤＥ＿０（１）が呼出された後、ステッ
プＳ３２へ進む。ここでＨＡＬＦは１であって、ステッ
プＳ３４にて第３グループインデックスビットを符号化
するＣＯＤＥ＿０１（１、２）が呼出されて符号化過程
が終了される。
【００３１】第１のグループ分け過程にて上位グループ
に属する入力シンボル５に対して、ＶＡＬＵＥはＨＡＬ
Ｆより大きく、ステップＳ２４にて、サブルーチンＴＳ
ＡＣ＿ＥＮＣＯＤＥ＿１（１、２、０）がＶＡＬＵＥ値
からＨＡＬＦ値を減算してＨＡＬＦ値は２で割られる。
サブルーチンＴＳＡＣ＿ＥＮＣＯＤＥ＿１（１、２、
０）において、第１グループインデックスビットは、ス
テップＳ４０にてＣＯＤＥ＿１（０）を呼出すことによ
って符号化される。現在のＨＡＬＦの値が２であるの
で、ＶＡＬＵＥはステップＳ４６にてＨＡＬＦと再度比
較されて、サブルーチンＴＳＡＣ＿ＥＮＣＯＤＥ＿０
（１、１、４）はステップＳ４８にて再び呼出される。
以後過程はステップＳ３０へ進んで、サブルーチンＴＳ
ＡＣ＿ＥＮＣＯＤＥ＿０（１、１、４）内部で第２グル
ープインデックスビットを符号化するＣＯＤＥ＿０
（４）が呼び出された後、ステップＳ３２へ再び進む。
ここで、ＨＡＬＦは１であって、ステップＳ３４にて第
３グループインデックスビットを符号化するＣＯＤＥ＿
０１（１、５）が呼出されて、符号化過程が終了され
る。
に属する入力シンボル５に対して、ＶＡＬＵＥはＨＡＬ
Ｆより大きく、ステップＳ２４にて、サブルーチンＴＳ
ＡＣ＿ＥＮＣＯＤＥ＿１（１、２、０）がＶＡＬＵＥ値
からＨＡＬＦ値を減算してＨＡＬＦ値は２で割られる。
サブルーチンＴＳＡＣ＿ＥＮＣＯＤＥ＿１（１、２、
０）において、第１グループインデックスビットは、ス
テップＳ４０にてＣＯＤＥ＿１（０）を呼出すことによ
って符号化される。現在のＨＡＬＦの値が２であるの
で、ＶＡＬＵＥはステップＳ４６にてＨＡＬＦと再度比
較されて、サブルーチンＴＳＡＣ＿ＥＮＣＯＤＥ＿０
（１、１、４）はステップＳ４８にて再び呼出される。
以後過程はステップＳ３０へ進んで、サブルーチンＴＳ
ＡＣ＿ＥＮＣＯＤＥ＿０（１、１、４）内部で第２グル
ープインデックスビットを符号化するＣＯＤＥ＿０
（４）が呼び出された後、ステップＳ３２へ再び進む。
ここで、ＨＡＬＦは１であって、ステップＳ３４にて第
３グループインデックスビットを符号化するＣＯＤＥ＿
０１（１、５）が呼出されて、符号化過程が終了され
る。
【００３２】前述した過程を検討すると、入力シンボル
１及び５に対して用いられたコンテキストは上記の表２
に示したものと一致することが分かる。
１及び５に対して用いられたコンテキストは上記の表２
に示したものと一致することが分かる。
【００３３】本発明のエンコーダが７つの値を有する入
力シンボルに対して述べたが、若干の変形を加えて様々
な入力モデルも扱うことができる。
力シンボルに対して述べたが、若干の変形を加えて様々
な入力モデルも扱うことができる。
【００３４】上記に於いて、本発明の特定の実施例につ
いて説明したが、本明細書に記載した特許請求の範囲を
逸脱することなく、当業者は種々の変更を加え得ること
は勿論である。
いて説明したが、本明細書に記載した特許請求の範囲を
逸脱することなく、当業者は種々の変更を加え得ること
は勿論である。
【００３５】
【発明の効果】従って、本発明によれば、多重値の入力
シンボルの統計的特性を十分用いることによって、符号
化効率をより一層高めることができる。
シンボルの統計的特性を十分用いることによって、符号
化効率をより一層高めることができる。
【図１】多重値の入力シンボルを符号化する従来のエン
コーダを説明するための概略的なブロック図である。
コーダを説明するための概略的なブロック図である。
【図２】図１の多重値の入力シンボルに対する本発明の
エンコーダを説明するための概略的なブロック図であ
る。
エンコーダを説明するための概略的なブロック図であ
る。
【図３】ツリー構造の選択方式を説明するための模式図
である。
である。
【図４】図２の本発明のエンコーダにて行われる符号化
過程を説明するためのフローチャートである。
過程を説明するためのフローチャートである。
【図５】図２の本発明のエンコーダにて行われる符号化
過程を説明するためのフローチャートである。
過程を説明するためのフローチャートである。
【図６】図２の本発明のエンコーダにて行われる符号化
過程を説明するためのフローチャートである。
過程を説明するためのフローチャートである。
１０ ２進変換器 ３０ ２進算術符号化器（ＢＡＣ） １００ グループ分けブロック １１０ ＢＡＣ １２０ コンテキスト選択ブロック
Claims (2)
- 【請求項１】 Ｎ個の値を有する入力シンボルを符号
化する方法（Ｎは２M-1＜Ｎ＜２Mの範囲にあり、Ｍは正
の整数である）であって、 前記入力シンボルをＭビットの２進シンボルに変換する
第１過程と、 複数のコンテキストのうちで、前記Ｍビットの２進シン
ボルの各々に対応し、前記２進シンボルの異なる確率的
モデルを各々表すＭ個のコンテキストを選択する過程で
あって、前記複数のコンテキストはＭ個のコンテキスト
グループに分けられ、ｋ番目の前記コンテキストグルー
プは２K-1個のコンテキストを有し（ｋは１〜Ｍの範囲
にある任意の整数）、より大きいｋ値は前記２進シンボ
ルの上位ビットを表し、前記２進シンボルの１番目のビ
ットに対応するコンテキストは１番目のコンテキストグ
ループに含まれて、Ｌ番目（Ｌは２〜Ｍの範囲にある任
意の整数）のビットに対応するコンテキストを前記Ｌ番
目のビットの上位ビットに応じて、Ｌ番目のコンテキス
トグループのうちで選択する第２過程と、 ２進算術符号化方法を用いて、前記対応するコンテキス
トに応じて、前記Ｍビットの２進シンボルの各々を順次
的に符号化する第３過程とを含むことを特徴とする入力
シンボルの２進算術符号化方法。 - 【請求項２】 Ｎ個の値を有する入力シンボルを符号
化する装置（Ｎは２M-1＜Ｎ＜２Mの範囲にあり、Ｍは正
の整数である）であって、 前記入力シンボルをＭビットの２進シンボルに変換する
変換手段と、 複数のコンテキストのうちで前記Ｍビットの２進シンボ
ルの各々に対応し、前記２進シンボルの異なる確率的モ
デルを各々表すＭ個のコンテキストを選択する手段であ
って、前記複数のコンテキストはＭ個のコンテキストグ
ループに分けられ、ｋ番目の前記コンテキストグループ
は２K-1個のコンテキストを有し（ｋは１〜Ｍの範囲に
ある任意の整数）、より大きいｋ値は前記２進シンボル
の上位ビットを表し、前記２進シンボルの１番目のビッ
トに対応するコンテキストは１番目のコンテキストグル
ープに含まれて、Ｌ番目（Ｌは２〜Ｍの範囲にある任意
の整数）のビットに対応するコンテキストを前記Ｌ番目
のビットの上位ビットに応じて、Ｌ番目のコンテキスト
グループのうちで選択するコンテキスト選択手段と、 ２進算術符号化方法を用いて、前記対応するコンテキス
トに応じて、前記Ｍビットの２進シンボルの各々を順次
的に符号化する２進算術符号化手段とを含むことを特徴
とする入力シンボルの２進算術符号化装置。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| KR1994/28306 | 1994-10-31 | ||
| KR1019940028306A KR960015195A (ko) | 1994-10-31 | 1994-10-31 | 트리 구조 이원 연산 코딩 장치 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH08242177A true JPH08242177A (ja) | 1996-09-17 |
Family
ID=19396652
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP7306753A Pending JPH08242177A (ja) | 1994-10-31 | 1995-10-31 | 入力シンボルの２進算術符号化方法及びその装置 |
Country Status (4)
| Country | Link |
|---|---|
| US (1) | US5694128A (ja) |
| JP (1) | JPH08242177A (ja) |
| KR (1) | KR960015195A (ja) |
| CN (1) | CN1132966A (ja) |
Cited By (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| KR19980081236A (ko) * | 1997-04-09 | 1998-11-25 | 바카앤쏘니제이 | 데이터 압축/복원 방법 및 압축 장치 |
| JP2007228582A (ja) * | 2006-02-22 | 2007-09-06 | Samsung Electronics Co Ltd | 圧縮率の向上のために改善されたコンテキストモデル選択を使用するｃａｂａｃ符号化方法及び装置、並びにｃａｂａｃ復号化方法及び装置 |
| WO2009059067A3 (en) * | 2007-10-30 | 2009-06-18 | Hewlett Packard Development Co | Data sequence compression |
| JP2010520696A (ja) * | 2007-03-08 | 2010-06-10 | サムスン エレクトロニクス カンパニー リミテッド | ツリー構造を基にしたエントロピ符号化及び復号化の装置及び方法 |
| JP2012226375A (ja) * | 2004-02-27 | 2012-11-15 | Samsung Electronics Co Ltd | 無損失オーディオ復号化方法及び無損失オーディオ復号化装置 |
Families Citing this family (16)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| EP0855803B1 (en) * | 1997-01-24 | 2000-01-19 | Koninklijke KPN N.V. | Method and system for compressing data based upon context tree algorithm |
| KR100281321B1 (ko) * | 1998-03-26 | 2001-02-01 | 전주범 | 적응적인 산술 부호화 및 그 복호화 방법 |
| US6879988B2 (en) | 2000-03-09 | 2005-04-12 | Pkware | System and method for manipulating and managing computer archive files |
| US8959582B2 (en) | 2000-03-09 | 2015-02-17 | Pkware, Inc. | System and method for manipulating and managing computer archive files |
| US8230482B2 (en) | 2000-03-09 | 2012-07-24 | Pkware, Inc. | System and method for manipulating and managing computer archive files |
| US7844579B2 (en) | 2000-03-09 | 2010-11-30 | Pkware, Inc. | System and method for manipulating and managing computer archive files |
| US20050015608A1 (en) | 2003-07-16 | 2005-01-20 | Pkware, Inc. | Method for strongly encrypting .ZIP files |
| KR20010095569A (ko) * | 2000-04-11 | 2001-11-07 | 장병탁 | 프로세스 분할을 이용한 유전자 프로그래밍법 및 그이용시스템 |
| KR100405819B1 (ko) * | 2001-01-15 | 2003-11-14 | 한국과학기술원 | 이진 영상의 데이터 압축 및 복원방법 |
| US6492916B1 (en) * | 2001-03-30 | 2002-12-10 | Ricoh Co., Ltd. | Method and apparatus for generating multiple selectable contexts |
| JP3853710B2 (ja) * | 2002-07-15 | 2006-12-06 | Ｎｅｃアクセステクニカ株式会社 | ディジタル画像符号化装置およびディジタル画像符号化方法 |
| KR100612015B1 (ko) | 2004-07-22 | 2006-08-11 | 삼성전자주식회사 | 컨텍스트 적응형 이진 산술 부호화 방법 및 그 장치 |
| KR101385956B1 (ko) * | 2007-08-31 | 2014-04-17 | 삼성전자주식회사 | 미디어 신호 인코딩/디코딩 방법 및 장치 |
| EP2239852A1 (en) * | 2009-04-09 | 2010-10-13 | Thomson Licensing | Method and device for encoding an input bit sequence and corresponding decoding method and device |
| CA2798125C (en) * | 2010-07-28 | 2016-04-05 | Research In Motion Limited | Method and device for compression of binary sequences by grouping multiple symbols |
| WO2016210400A2 (en) * | 2015-06-25 | 2016-12-29 | Diebold, Incorporated | Automated banking machine firmware flow control |
Family Cites Families (7)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4295125A (en) * | 1980-04-28 | 1981-10-13 | International Business Machines Corporation | Method and means for pipeline decoding of the high to low order pairwise combined digits of a decodable set of relatively shifted finite number of strings |
| US4494108A (en) * | 1981-11-09 | 1985-01-15 | International Business Machines Corporation | Adaptive source modeling for data file compression within bounded memory |
| US4633490A (en) * | 1984-03-15 | 1986-12-30 | International Business Machines Corporation | Symmetrical optimized adaptive data compression/transfer/decompression system |
| US5045852A (en) * | 1990-03-30 | 1991-09-03 | International Business Machines Corporation | Dynamic model selection during data compression |
| US5550540A (en) * | 1992-11-12 | 1996-08-27 | Internatioal Business Machines Corporation | Distributed coding and prediction by use of contexts |
| US5381145A (en) * | 1993-02-10 | 1995-01-10 | Ricoh Corporation | Method and apparatus for parallel decoding and encoding of data |
| US5414423A (en) * | 1993-04-29 | 1995-05-09 | International Business Machines Corporation | Stabilization of probability estimates by conditioning on prior decisions of a given context |
-
1994
- 1994-10-31 KR KR1019940028306A patent/KR960015195A/ko not_active Ceased
-
1995
- 1995-10-31 JP JP7306753A patent/JPH08242177A/ja active Pending
- 1995-10-31 US US08/551,055 patent/US5694128A/en not_active Expired - Fee Related
- 1995-10-31 CN CN95118237A patent/CN1132966A/zh active Pending
Cited By (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| KR19980081236A (ko) * | 1997-04-09 | 1998-11-25 | 바카앤쏘니제이 | 데이터 압축/복원 방법 및 압축 장치 |
| JP2012226375A (ja) * | 2004-02-27 | 2012-11-15 | Samsung Electronics Co Ltd | 無損失オーディオ復号化方法及び無損失オーディオ復号化装置 |
| JP2007228582A (ja) * | 2006-02-22 | 2007-09-06 | Samsung Electronics Co Ltd | 圧縮率の向上のために改善されたコンテキストモデル選択を使用するｃａｂａｃ符号化方法及び装置、並びにｃａｂａｃ復号化方法及び装置 |
| JP2010520696A (ja) * | 2007-03-08 | 2010-06-10 | サムスン エレクトロニクス カンパニー リミテッド | ツリー構造を基にしたエントロピ符号化及び復号化の装置及び方法 |
| WO2009059067A3 (en) * | 2007-10-30 | 2009-06-18 | Hewlett Packard Development Co | Data sequence compression |
| US7623047B2 (en) | 2007-10-30 | 2009-11-24 | Hewlett-Packard Development Company, L.P. | Data sequence compression |
Also Published As
| Publication number | Publication date |
|---|---|
| US5694128A (en) | 1997-12-02 |
| CN1132966A (zh) | 1996-10-09 |
| KR960015195A (ko) | 1996-05-22 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JPH08242177A (ja) | 入力シンボルの２進算術符号化方法及びその装置 | |
| US7043088B2 (en) | Adaptive variable length decoding method | |
| JP5221047B2 (ja) | 圧縮率の向上のために改善されたコンテキストモデル選択を使用するｃａｂａｃ符号化方法及び装置、並びにｃａｂａｃ復号化方法及び装置 | |
| CN1126268C (zh) | 编码数字信息信号的方法和装置 | |
| JPH04223717A (ja) | データ圧縮モデル選択方法及びシステム | |
| JPH09130810A (ja) | 符号化・復号化装置及び符号化・復号化方法 | |
| JPS6126737B2 (ja) | ||
| CN107481295A (zh) | 基于动态字节长度分配的卷积神经网络的图像压缩系统 | |
| JP2977570B2 (ja) | 可変長符号化方法および可変長復号方法を実施するための装置 | |
| JP2006157678A (ja) | 可変長符号化装置及び可変長符号化方法 | |
| US6055273A (en) | Data encoding and decoding method and device of a multiple-valued information source | |
| JP3808241B2 (ja) | データ圧縮方法および装置並びに記録媒体 | |
| CN116505952A (zh) | 红外码压缩方法、装置、智能设备及存储介质 | |
| Hung et al. | New irregular sampling coding method for transmitting images progressively | |
| JPH07212243A (ja) | 可変長符号の符号化方法およびその装置 | |
| JP2014506759A (ja) | 異種ネットワークを介したコンテンツ配信のクリフ効果を軽減するシステムおよび方法 | |
| JPH08340258A (ja) | 可変長符号化／復号化装置 | |
| CN114095127A (zh) | 一种针对卫星链路的时效性分级传输喷泉编码方法 | |
| CN114429200A (zh) | 规范化哈夫曼编解码方法及神经网络计算芯片 | |
| CN115865098A (zh) | 基于Huffman编码的数据压缩方法 | |
| JP6707045B2 (ja) | 二値算術復号器および二値算術復号装置 | |
| CN1098565C (zh) | 译码变长码的方法和设备 | |
| JP2606583B2 (ja) | ベクトル画像符号化装置 | |
| KR0148152B1 (ko) | 영상데이타의 적응가변장부호화 및 복호화방법과 그 장치 | |
| RU2801163C1 (ru) | Устройство для многоуровневого кодирования |