(57)【特許請求の範囲】
【請求項１】
ｎがｎ≧１を満たす整数であるようなｎビットシンボルの直列系列を有するデジタル情報信号を、Ａパラメータ及びＣパラメータを各々記憶する有限サイズの第１及び第２のレジスタを用いて算術的に符号化する方法であって、前記Ｃパラメータが或る値区間の境界と関係を有する一方、前記Ａパラメータが該区間のサイズと関係を有し、該方法が、
（ａ）符号化のために、前記情報信号のシンボルと、関連するシンボルの少なくとも１つの対応する確率値とを入力するステップと、
（ｂ）前記Ａ及びＣパラメータに関する値を、前記第１及び第２のレジスタから各々取り出すステップと、
（ｃ）前記第１のレジスタから取り出された値に対応する前記値区間を前記少なくとも１つの確率値に対応する副区間に分割すると共に、これら副区間のうちの１つを前記シンボルに応答して選択するステップと、
（ｄ）少なくとも前記Ａパラメータを、該Ａパラメータの値が前記選択された副区間のサイズに従うように更新して、前記情報信号における次のシンボルを符号化するための区間の新たなサイズとなるようにするステップと、
（ｅ）前記Ａパラメータに関する前記更新された値を前記第１のレジスタに記憶するステップと、
（ｆ）前記次のシンボルを符号化するために、該方法を前記ステップ（ａ）で継続するステップと、
を有するような方法において、
前記ステップ（ｂ）が、前記Ａパラメータの値0.b0b1…bi-1bi…をビットbi-1までで切り捨て、biが‘１’に等しい場合に、前記Ａの切り捨て処理された値にビットbi-1の位置で‘１’を加算するような副ステップを更に有していることを特徴とする方法。
【請求項２】
ｎがｎ≧１を満たす整数であるようなｎビットシンボルの直列系列を有するデジタル情報信号を、Ａパラメータ及びＣパラメータを各々記憶する有限サイズの第１及び第２のレジスタを用いて算術的に符号化する方法であって、前記Ｃパラメータが或る値区間の境界と関係を有する一方、前記Ａパラメータが該区間のサイズと関係を有し、該方法が、
（ａ）符号化のために、前記情報信号のシンボルと、関連するシンボルの少なくとも１つの対応する確率値とを入力するステップと、
（ｂ）前記Ａ及びＣパラメータに関する値を、前記第１及び第２のレジスタから各々取り出すステップと、
（ｃ）前記第１のレジスタから取り出された値に対応する前記値区間を前記少なくとも１つの確率値に対応する副区間に分割すると共に、これら副区間のうちの１つを前記シンボルに応答して選択するステップと、
（ｄ）少なくとも前記Ａパラメータを、該Ａパラメータの値が前記選択された副区間のサイズに従うように更新して、前記情報信号における次のシンボルを符号化するための区間の新たなサイズとなるようにするステップと、
（ｅ）前記Ａパラメータに関する前記更新された値を前記第１のレジスタに記憶するステップと、
（ｆ）前記次のシンボルを符号化するために、該方法を前記ステップ（ａ）で継続するステップと、
を有するような方法において、
前記ステップ（ｂ）が、前記Ａパラメータの値0.b0b1…bi-1bi…をビットbi-1までで切り捨て、bi-1＝‘0’且つbi＝‘1’の場合に、bi-1を‘１’に引き上げるような副ステップを更に有していることを特徴とする方法。
【請求項３】
ｎがｎ≧１を満たす整数であるようなｎビットシンボルの直列系列を有するデジタル情報信号を、Ａパラメータ及びＣパラメータを各々記憶する有限サイズの第１及び第２のレジスタを用いて算術的に符号化する方法であって、前記Ｃパラメータが或る値区間の境界と関係を有する一方、前記Ａパラメータが該区間のサイズと関係を有し、該方法が、
（ａ）符号化のために、前記情報信号のシンボルと、関連するシンボルの少なくとも１つの対応する確率値とを入力するステップと、
（ｂ）前記Ａ及びＣパラメータに関する値を、前記第１及び第２のレジスタから各々取り出すステップと、
（ｃ）前記第１のレジスタから取り出された値に対応する前記値区間を前記少なくとも１つの確率値に対応する副区間に分割すると共に、これら副区間のうちの１つを前記シンボルに応答して選択するステップと、
（ｄ）少なくとも前記Ａパラメータを、該Ａパラメータの値が前記選択された副区間のサイズに従うように更新して、前記情報信号における次のシンボルを符号化するための区間の新たなサイズとなるようにするステップと、
（ｅ）前記Ａパラメータに関する前記更新された値を前記第１のレジスタに記憶するステップと、
（ｆ）前記次のシンボルを符号化するために、該方法を前記ステップ（ａ）で継続するステップと、
を有するような方法において、
前記ステップ（ｂ）が、前記Ａパラメータの値0.b0b1…bi-1bi…をビットbi-1までで切り捨て、該ビットbi-1を‘１’に等しくするような副ステップを更に有していることを特徴とする方法。
【請求項４】
請求項１、２又は３に記載の方法において、前記更新するステップが、前記Ｃ値を該Ｃパラメータの値が前記選択された副区間の境界と対応する関係となるように更新して、前記情報信号における次のシンボルを符号化するための新たなＣパラメータとなるようにするステップも有し、前記記憶するステップが前記Ｃパラメータの前記更新された値を前記第２のレジスタに記憶するステップを更に有していることを特徴とする方法。
【請求項５】
請求項１、２、３又は４に記載の方法であって、前記更新するステップが前記Ａ及びＣパラメータに関する再正規化された値を前記第１及び第２のレジスタに各々記憶するに先立ち、これらＡ及びＣパラメータに関する値を再正規化する副ステップを有するような方法において、前記再正規化副ステップが、
（g1）前記Ａに関する値と第１の２進値とを比較し、前記Ａに関する値が前記第１の２進値以上である場合は該再正規化副ステップを離脱し、前記Ａに関する値が前記第１の２進値未満である場合は、次いで、
（g2）前記Ａに関する値を第１の整数値で乗算し、
（g3）前記（g1）に戻る、
ようなステップを有していることを特徴とする方法。
【請求項６】
請求項５に記載の方法において、前記（g1）においてＡが前記第１の２進値未満である場合に、
（g4）前記Ｃに関する値を第２及び第３の２進値と比較し、ここで前記第２の２進値は前記第３の２進値より大きいものとし、もし、前記Ｃに関する値が前記第２の２進値よりは小さいが、前記第３の２進値より大きいか又は該第３の２進値に等しい場合は、次いで、
（g5）前記Ｃに関する値から第４の２進値を減算して、Ｃに関する中間値を得、
（g6）前記Ｃに関する中間値を第２の整数で乗算する、
ことを特徴とする方法。
【請求項７】
請求項５に記載の方法において、前記第１の２進値が0.100…0に等しいことを特徴とする方法。
【請求項８】
請求項５に記載の方法において、前記第２の２進値が1.000…0に等しいことを特徴とする方法。
【請求項９】
請求項５に記載の方法において、前記第１の整数値が２に等しいことを特徴とする方法。
【請求項１０】
請求項６に記載の方法において、前記第３の２進値が0.100…0に等しいことを特徴とする方法。
【請求項１１】
請求項６に記載の方法において、前記第４の２進値が0.1000…0に等しいことを特徴とする方法。
【請求項１２】
請求項６に記載の方法において、前記第２の整数値が２に等しいことを特徴とする方法。
【請求項１３】
請求項１ないし１２の何れか一項に記載の方法において、前記符号化された情報信号をチャンネル符号化された信号にチャンネル符号化するステップを更に有していることを特徴とする方法。
【請求項１４】
請求項１３に記載の方法において、前記チャンネル符号化された信号を記録担体上に記録するステップを更に有していることを特徴とする方法。
【請求項１５】
請求項１ないし１４の何れか一項に記載の方法を実施する装置。
【請求項１６】
ｎがｎ≧１を満たす整数であるｎビットシンボルの直列系列を有するデジタル情報信号を算術的に符号化するような請求項１５に記載の装置であって、該装置が、
−  Ａパラメータ及びＣパラメータを各々記憶するための有限サイズの第１及び第２のレジスタであって、前記Ｃパラメータが或る値区間の境界と関係を有する一方、前記Ａパラメータが前記区間のサイズと関係を有するようなレジスタと、
−  符号化のために、前記情報信号のシンボルと、関連するシンボル用の少なくとも１つの対応する確率値とを入力する入力手段と、
−  前記Ａ及びＣパラメータに関する値を、前記第１及び第２のレジスタから各々取り出す取出手段と、
−  前記第１のレジスタから取り出された値に対応する前記値区間を前記少なくとも１つの確率値に対応する副区間に分割すると共に、これら副区間のうちの１つを前記シンボルに応答して選択する手段と、
−  少なくとも前記Ａパラメータを、該Ａパラメータの値が前記選択された副区間のサイズに従うように更新して、前記情報信号における次のシンボルを符号化するための区間の新たなサイズとなるようにする手段と、
−  前記Ａパラメータに関する前記更新された値を前記第１のレジスタに記憶する手段と、
を有するような装置において、
前記取出手段が、前記Ａパラメータの値0.b0b1…bi-1bi…をビットbi-1までで切り捨て、biが‘１’に等しい場合に、前記Ａの切り捨て処理された値に前記ビットbi-1の位置で‘１’を加算するような手段を更に有していることを特徴とする装置。
【請求項１７】
ｎがｎ≧１を満たす整数であるｎビットシンボルの直列系列を有する情報信号を算術的に符号化するような請求項１５に記載の装置であって、該装置が、
−  Ａパラメータ及びＣパラメータを各々記憶するための有限サイズの第１及び第２のレジスタであって、前記Ｃパラメータが或る値区間の境界と関係を有する一方、前記Ａパラメータが前記区間のサイズと関係を有するようなレジスタと、
−  符号化のために、前記情報信号のシンボルと、関連するシンボル用の少なくとも１つの対応する確率値とを入力する入力手段と、
−  前記Ａ及びＣパラメータに関する値を、前記第１及び第２のレジスタから各々取り出す取出手段と、
−  前記第１のレジスタから取り出された値に対応する前記値区間を前記少なくとも１つの確率値に対応する副区間に分割すると共に、これら副区間のうちの１つを前記シンボルに応答して選択する手段と、
−  少なくとも前記Ａパラメータを、該Ａパラメータの値が前記選択された副区間のサイズに従うように更新して、前記情報信号における次のシンボルを符号化するための区間の新たなサイズとなるようにする手段と、
−  前記Ａパラメータに関する前記更新された値を前記第１のレジスタに記憶する手段と、
を有するような装置において、
前記取出手段が、前記Ａパラメータの値0.b0b1…bi-1bi…をビットbi-1までで切り捨て、bi-1＝‘0’且つbi＝‘1’の場合に、bi-1を‘１’に引き上げるような手段を更に有していることを特徴とする装置。
【請求項１８】
ｎがｎ≧１を満たす整数であるｎビットシンボルの直列系列を有する情報信号を算術的に符号化するような請求項１５に記載の装置であって、該装置が、
−  Ａパラメータ及びＣパラメータを各々記憶するための有限サイズの第１及び第２のレジスタであって、前記Ｃパラメータが或る値区間の境界と関係を有する一方、前記Ａパラメータが前記区間のサイズと関係を有するようなレジスタと、
−  符号化のために、前記情報信号のシンボルと、関連するシンボル用の少なくとも１つの対応する確率値とを入力する入力手段と、
−  前記Ａ及びＣパラメータに関する値を、前記第１及び第２のレジスタから各々取り出す取出手段と、
−  前記第１のレジスタから取り出された値に対応する前記値区間を前記少なくとも１つの確率値に対応する副区間に分割すると共に、これら副区間のうちの１つを前記シンボルに応答して選択する手段と、
−  少なくとも前記Ａパラメータを、該Ａパラメータの値が前記選択された副区間のサイズに従うように更新して、前記情報信号における次のシンボルを符号化するための区間の新たなサイズとなるようにする手段と、
−  前記Ａパラメータに関する前記更新された値を前記第１のレジスタに記憶する手段と、
を有するような装置において、
前記取出手段が、前記Ａパラメータの値0.b0b1…bi-1bi…をビットbi-1までで切り捨て、前記ビットbi-1を‘１’に等しくするような手段を更に有していることを特徴とする装置。
【請求項１９】
請求項１６、１７又は１８に記載の装置であって、前記Ａ及びＣパラメータに関する再正規化された値を前記第１及び第２のレジスタに各々記憶するに先立ち、これらＡ及びＣパラメータに関する値を再正規化する手段を更に有するような装置において、前記再正規化する手段が、
（g1）前記Ａに関する値と第１の２進値とを比較し、前記Ａに関する値が前記第１の２進値以上である場合は該再正規化ステップを離脱し、前記Ａに関する値が前記第１の２進値未満である場合は、次いで、
（g2）前記Ａに関する値を第１の整数値で乗算する、
ような手段を有していることを特徴とする装置。
【請求項２０】
請求項１９に記載の装置において、前記再正規化手段が、
（g4）前記Ｃに関する値を第２及び第３の２進値と比較し、ここで前記第２の２進値は前記第３の２進値より大きく、
（g5）前記Ｃに関する値から第４の２進値を減算して、Ｃに関する中間値を得、
（g6）前記Ｃに関する中間値を第２の整数で乗算する、
ような手段を更に有していることを特徴とする装置。
【請求項２１】
請求項１５ないし２０の何れか一項に記載の装置において、前記符号化された情報信号をチャンネル符号化された信号にチャンネル符号化する手段を更に有していることを特徴とする装置。
【請求項２２】
請求項２１に記載の装置において、前記チャンネル符号化された信号を記録担体上に記録する記録手段を更に有していることを特徴とする装置。
【請求項２３】
算術的に符号化された情報信号を、ｎがｎ≧１を満たす整数であるｎビットシンボルの直列系列を有する情報信号に算術的に復号するような装置であって、該装置が、
−  前記算術的に符号化された情報信号を入力する入力手段と、
−  有限サイズの第１及び第２のレジスタであって、前記第１のレジスタはＡパラメータを記憶するためのものであり、該Ａパラメータは値区間のサイズと関係を有し、前記第２のレジスタはＣパラメータを記憶するためのものであり、復号ステップ前の該第２のレジスタの内容は、前記算術的に符号化された情報信号のｍビットを前記第２のレジスタにシフト入力することにより、前の復号ステップにおいて得られた前記第２のレジスタの内容から得られ、ここでｍはｍ≧０を満たすような可変整数であるようなレジスタと、
−  復号されるべき関連するシンボルに関する少なくとも１つの確率値を発生する発生手段と、
−  前記Ａ及びＣパラメータに関する値を、前記第１及び第２のレジスタから各々取り出す取出手段と、
−  前記少なくとも１つの確率値に応答し、且つ、Ａに関する値及びＣに関する値に応答して、シンボルを導出する導出手段と、
−  少なくとも前記Ａパラメータを更新して、前記情報信号における次のシンボルを復号するための区間の新たなサイズとなるようにする手段と、
−  前記導出されたシンボルを出力する手段と、
−  前記Ａパラメータに関する前記更新された値を前記第１のレジスタに記憶する手段と、
を有するような装置において、
前記取出手段が、前記Ａパラメータの値0.b0b1…bi-1bi…をビットbi-1までで切り捨て、biが‘１’に等しい場合に、前記Ａの切り捨て処理された値に前記ビットbi-1の位置で‘１’を加算するような手段を更に有していることを特徴とする装置。
【請求項２４】
算術的に符号化された情報信号を、ｎがｎ≧１を満たす整数であるｎビットシンボルの直列系列を有する情報信号に算術的に復号するような装置であって、該装置が、
−  前記算術的に符号化された情報信号を入力する入力手段と、
−  有限サイズの第１及び第２のレジスタであって、前記第１のレジスタはＡパラメータを記憶するためのものであり、該Ａパラメータは値区間のサイズと関係を有し、前記第２のレジスタはＣパラメータを記憶するためのものであり、復号ステップ前の該第２のレジスタの内容は、前記算術的に符号化された情報信号のｍビットを前記第２のレジスタにシフト入力することにより、前の復号ステップにおいて得られた前記第２のレジスタの内容から得られ、ここでｍはｍ≧０を満たすような可変整数であるようなレジスタと、
−  復号されるべき関連するシンボルに関する少なくとも１つの確率値を発生する発生手段と、
−  前記Ａ及びＣパラメータに関する値を、前記第１及び第２のレジスタから各々取り出す取出手段と、
−  前記少なくとも１つの確率値に応答し、且つ、Ａに関する値及びＣに関する値に応答して、シンボルを導出する導出手段と、
−  少なくとも前記Ａパラメータを更新して、前記情報信号における次のシンボルを復号するための区間の新たなサイズとなるようにする手段と、
−  前記導出されたシンボルを出力する手段と、
−  前記Ａパラメータに関する前記更新された値を前記第１のレジスタに記憶する手段と、
を有するような装置において、
前記取出手段が、前記Ａパラメータの値0.b0b1…bi-1bi…をビットbi-1までで切り捨て、bi-1＝‘0’且つbi＝‘1’の場合に、bi-1を‘１’に引き上げるような手段を更に有していることを特徴とする装置。
【請求項２５】
算術的に符号化された情報信号を、ｎがｎ≧１を満たす整数であるｎビットシンボルの直列系列を有する情報信号に算術的に復号するような装置であって、該装置が、
−  前記算術的に符号化された情報信号を入力する入力手段と、
−  有限サイズの第１及び第２のレジスタであって、前記第１のレジスタはＡパラメータを記憶するためのものであり、該Ａパラメータは値区間のサイズと関係を有し、前記第２のレジスタはＣパラメータを記憶するためのものであり、復号ステップ前の該第２のレジスタの内容は、前記算術的に符号化された情報信号のｍビットを前記第２のレジスタにシフト入力することにより、前の復号ステップにおいて得られた前記第２のレジスタの内容から得られ、ここでｍはｍ≧０を満たすような可変整数であるようなレジスタと、
−  復号されるべき関連するシンボルに関する少なくとも１つの確率値を発生する発生手段と、
−  前記Ａ及びＣパラメータに関する値を、前記第１及び第２のレジスタから各々取り出す取出手段と、
−  前記少なくとも１つの確率値に応答し、且つ、Ａに関する値及びＣに関する値に応答して、シンボルを導出する導出手段と、
−  少なくとも前記Ａパラメータを更新して、前記情報信号の次のシンボルを復号するための区間の新たなサイズとなるようにする手段と、
−  前記導出されたシンボルを出力する手段と、
−  前記Ａパラメータに関する前記更新された値を前記第１のレジスタに記憶する手段と、
を有するような装置において、
前記取出手段が、前記Ａパラメータの値0.b0b1…bi-1bi…をビットbi-1までで切り捨て、前記ビットbi-1を‘１’に等しくするような手段を更に有していることを特徴とする装置。
【請求項２６】
請求項２３、２４又は２５に記載の復号装置において、算術復号の前に、前記算術的に符号化された情報信号をチャンネル復号するチャンネル復号手段を更に有していることを特徴とする装置。
【請求項２７】
請求項２６に記載の装置において、前記チャンネル符号化された算術的に符号化された情報信号を記録担体から読み取る読取手段を更に有していることを特徴とする装置。
【発明の詳細な説明】
技術分野
本発明は、情報信号を算術符号化する方法、情報信号を算術符号化する装置及び該算術的に符号化された情報信号を復号する装置に関する。
背景技術
算術符号化は無損失符号化用の良く知られた技術であり、概要は現在のどの様なソース符号化ブックにおいても見付けることができる。本件に最も関連のある算術符号化の構成を完全に理解するには、［Lang84］を参照されたい。算術符号化の歴史に関しては、本明細書の巻末付録によく記載されている。更に、［Howard94］は算術符号化の詳細な説明を行っている。
本発明の主題である算術符号化の構成は２つの有限サイズのレジスタを使用し、これらレジスタは、通常、Ｃ及びＡと呼ばれる。エンコーダの動作のフローチャートは第１図に示されている。該区間が副区間に分割され、各副区間は符号化されるべきシンボルに対応し、各副区間のサイズは関連するシンボルの確率に対応する。シンボルを実際に符号化するために、Ｃレジスタは該シンボルに対応する副区間の底を指し示すように調整され、Ａレジスタは選択された副区間のサイズに設定される。次いで、Ａレジスタ（及びＣ）は、次のシンボルが符号化される前に正規化（左シフト）される。通常、再正規化（re-normalization）の後、Ａの値は値ｋと２ｋとの間にある。即ち、ｋ≦Ａ＜２ｋである。本例では、ｋ＝1/2が用いられるであろう。
例えば、２進の場合は、符号化されるべきビットが最もありそうなシンボル（ＭＰＳ）であるか又は最もありそうにないシンボル（ＬＰＳ）であるかに応じて、２つの副区間、従ってＣ及びＡレジスタの２つの可能性のある更新が存在する。ＭＰＳは低い方の区間に割り付けられると仮定する。第１図の“Ａ及びＣを更新する”なるブロックは、２進の場合に関して第２図に示されている。入力ビットがＬＰＳである確率はｐにより示されている（ＭＰＳの確率は≧1/2であるので、ｐ≦1/2であることに注意）。符号化されるべき入力ビットはｂにより示されている。ｂ及びｐの値は“…を読み取る”なるブロックにより供給される。さて、ＭＰＳが符号化されるべき場合は、Ｃは変化しない。何故なら、低い方の区間が選択され、Ｃが既にこの区間を指し示しているからである。しかしながら、Ａは変化し、その更新はＡ＝Ａ−Ａ・ｐである（ＭＰＳの確率が１−ｐに等しいという事実を利用する）。ＬＰＳが符号化されるべき場合は、Ｃ及びＡの両方が変化される。即ち、ＣはＣ＝Ｃ＋Ａ−Ａ・ｐのように更新され、新たな区間サイズはＡ＝Ａ・ｐとなる。更に、前及び後処理により、ＭＰＳが常に例えば“０”ビットであり、ＬＰＳが常に“１”ビットであることを保証することができることに注意すべきである。最後に、乗算Ａ・ｐは僅かな性能損失において低精度で実行することができるので、第２図は“近似乗算”ブロックを示しており、かくしてハードウェアの複雑さを低減する。該近似乗算を行う技術は後述する。
２進でない場合は、第１図の“Ａ及びＣを更新する”ブロックは、第３図に示される。ここでは、“…を読み取る”ブロックは、符号化されるべきシンボル、ｓ、並びに２つの確率値、即ちシンボルｓの確率ｐs及びシンボルｓより下位の全てのシンボルの累積確率ｐtを供給する。第３図か分かるように、正確にＡを“満たす”ために、シンボルＭは他のものとは異なるように取り扱われる。［Riss89］には、ＭＰＳをシンボルＭに割り当てるのが有利であることが示されている。
復号することができるためには、デコーダはＣの値を知らなければならない。何故なら、これが、符号化されたシンボルを決定するからである。従って、デコーダに送られるものは、Ｃレジスタの値である。実際には、Ａレジスタが再正規化処理（renormalization process）において左シフトされる毎に、ＣのＭＳＢ（“キャリービット”とも呼ばれる）がデコーダへの伝送のために処理される。Ｃに対して有限サイズのレジスタを使用することによる問題は、Ｃから既にシフト出力されたビットが、Ｃをインクリメントすることにより生ずるキャリーにより、後に調整されねばならないことにある。これを処理するために、キャリーオーバー制御が必要とされる。現状技術は該問題をエンコーダにおいて完全に解決するので、デコーダはこれにより影響されることはない。デコーダの複雑さを最小化するこれらの解決策も、後述する。
デコーダのフローチャートは第４図に示されている。２進の場合に関しては、“シンボルを出力し…”ブロックは第５図に示されている。２進でない場合は、デコーダはもっと複雑である。何故なら、ｓの値を知ることなしに、“Ｃ＝Ｃ＋Ｄ”の逆数を見付けなければならないからである。
発明の開示
本発明は、上述した算術コーダに関する改善を提供することを目指すものである。本発明によれば、当該符号化方法は、ｎがｎ≧１を満たす整数であるようなｎビットシンボルの直列系列を有し、Ａパラメータ及びＣパラメータを各々記憶する有限サイズの第１及び第２のレジスタを用い、前記Ｃパラメータが或る値区間の境界と関係を有する一方、前記Ａパラメータが該区間のサイズと関係を有し、該方法が、
（ａ）符号化のために、前記情報信号のシンボルと、関連するシンボルの少なくとも１つの対応する確率値とを入力するステップと、
（ｂ）前記Ａ及びＣパラメータに関する値を、前記第１及び第２のレジスタから各々取り出すステップと、
（ｃ）前記第１のレジスタから取り出された値に対応する前記値区間を前記少なくとも１つの確率値に対応する副区間に分割すると共に、これら副区間のうちの１つを前記シンボルに応答して選択するステップと、
（ｄ）少なくとも前記Ａパラメータを、該Ａパラメータの値が前記選択された副区間のサイズに従うように更新して、前記情報信号における次のシンボルを符号化するための区間の新たなサイズとなるようにするステップと、
（ｅ）前記Ａパラメータに関する前記更新された値を前記第１のレジスタに記憶するステップと、
（ｆ）前記次のシンボルを符号化するために、該方法を前記ステップ（ａ）で継続するステップと、
を有するような方法において、
前記ステップ（ｂ）が、前記Ａパラメータの値0.b0b1…bi-1bi…をビットbi-1までで切り捨て、biが‘１’に等しい場合に、前記Ａの切り捨て処理された値にビットbi-1の位置で‘１’を加算するような副ステップを更に有していることを特徴とする。他の入念例においては、当該符号化方法は、ｎがｎ≧１を満たす整数であるようなｎビットシンボルの直列系列を有し、Ａパラメータ及びＣパラメータを各々記憶する有限サイズの第１及び第２のレジスタを用い、前記Ｃパラメータが或る値区間の境界と関係を有する一方、前記Ａパラメータが該区間のサイズと関係を有し、該方法が、
（ａ）符号化のために、前記情報信号のシンボルと、関連するシンボルの少なくとも１つの対応する確率値とを入力するステップと、
（ｂ）前記Ａ及びＣパラメータに関する値を、前記第１及び第２のレジスタから各々取り出すステップと、
（ｃ）前記第１のレジスタから取り出された値に対応する前記値区間を前記少なくとも１つの確率値に対応する副区間に分割すると共に、これら副区間のうちの１つを前記シンボルに応答して選択するステップと、
（ｄ）少なくとも前記Ａパラメータを、該Ａパラメータの値が前記選択された副区間のサイズに従うように更新して、前記情報信号における次のシンボルを符号化するための区間の新たなサイズとなるようにするステップと、
（ｅ）前記Ａパラメータに関する前記更新された値を前記第１のレジスタに記憶するステップと、
（ｆ）前記次のシンボルを符号化するために、該方法を前記ステップ（ａ）で継続するステップと、
を有するような方法において、
前記ステップ（ｂ）が、前記Ａパラメータの値0.b0b1…bi-1bi…をビットbi-1までで切り捨て、bi-1＝‘0’且つbi＝‘1’の場合に、bi-1を‘１’に引き上げるような副ステップを更に有していることを特徴とする。また、他の入念例においては、当該符号化方法は、ｎがｎ≧１を満たす整数であるようなｎビットシンボルの直列系列を有し、Ａパラメータ及びＣパラメータを各々記憶する有限サイズの第１及び第２のレジスタを用い、前記Ｃパラメータが或る値区間の境界と関係を有する一方、前記Ａパラメータが該区間のサイズと関係を有し、
該方法が、
（ａ）符号化のために、前記情報信号のシンボルと、関連するシンボルの少なくとも１つの対応する確率値とを入力するステップと、
（ｂ）前記Ａ及びＣパラメータに関する値を、前記第１及び第２のレジスタから各々取り出すステップと、
（ｃ）前記第１のレジスタから取り出された値に対応する前記値区間を前記少なくとも１つの確率値に対応する副区間に分割すると共に、これら副区間のうちの１つを前記シンボルに応答して選択するステップと、
（ｄ）少なくとも前記Ａパラメータを、該Ａパラメータの値が前記選択された副区間のサイズに従うように更新して、前記情報信号における次のシンボルを符号化するための区間の新たなサイズとなるようにするステップと、
（ｅ）前記Ａパラメータに関する前記更新された値を前記第１のレジスタに記憶するステップと、
（ｆ）前記次のシンボルを符号化するために、該方法を前記ステップ（ａ）で継続するステップと、
を有するような方法において、
前記ステップ（ｂ）が、前記Ａパラメータの値0.b0b1…bi-1bi…をビットbi-1までで切り捨て、該ビットbi-1を‘１’に等しくするような副ステップを更に有していることを特徴とする。
本発明において提示される改善は、近似乗算ブロック（これは、エンコーダ及びデコーダの両方において使用される）、及びエンコーダ内のみで“…再正規化し…”ブロックにおいて生じるキャリーオーバー制御に関するものである。
【図面の簡単な説明】
以下、本発明の、これら及び他の特徴を詳細に説明するが、添付図面において、
第１図は、算術エンコーダのフローチャートを示し、
第２図は、第１図のエンコーダブロック“Ａ及びＣを更新する”の２進の場合に関するフローチャートを示し、ここでＬＰＳ確率はｐであり、符号化されるべきビットの値はｂにより示されており、
第３図は、第１図のエンコーダブロック“Ａ及びＣを更新する”の２進でない場合に関するフローチャートを示し、ここで符号化されるべきシンボルの値はｓにより示され、その確率はｐsにより示され、Ｍ＋１のシンボルは０，…Ｍの番号が付され、ｐt＝ｐ0＋ｐ1＋…＋ｐs-1はシンボルｓより下位の全シンボルの累積確率であり、
第４図は、デコーダのフローチャートを示し、
第５図は、第４図におけるデコーダブロック“シンボルを出力し…”の２進の場合に関するフローチャートを示し、ここでＬＰＳの確率はｐであり、復号されるべきビットの値はｂで示されており、
第６図は、第１図における“…再正規化し…”で示されるエンコーダブロックのフローチャートを示し、
第７図は、第１図における“初期化する”で示されるエンコーダブロックのフローチャートを示し、
第８図は、第１図における“終了”で示されるエンコーダブロックのフローチャートを示し、
第９図は、第４図における“初期化する”で示されるデコーダブロックのフローチャートを示し、
第１０図は、第４図における“…再正規化し…”で示されるデコーダブロックのフローチャートを示し、
第１１図は、エンコーダ装置の実施例を示し、
第１２図は、デコーダ装置の実施例を示す。
発明を実施するための最良の形態
乗算の改善に関しては、次のことが言える。乗算Ａ・ｐを“避ける”という問題は、［Lang81］においては、２exp{-Q}によりｐを近似することにより解決されており、ここでＱは整数である。この場合、ｐによる乗算は、単純に、Ｑ位置だけの右シフトに対応する。Ｑはスキュー値（skew number）と呼ばれる。後に、［Riss89］におけるように、Ａレジスタは０．７５≦Ａ＜１．５のように正規化される。この場合、
0004179640.tif 000002
と仮定され、従って、
0004179640.tif 000003
となる。
もっと良好な性能は、［Chev91a］及び［Chev91b］で得られた。これらは、所定の２進１桁より重要でない全ての２進桁を削除することによりＡを近似することを主張しており、それらの好ましい実施例は２番目の最も重要な２進１桁を使用することである。このように、該好ましい実施例では、Ａの値は２つの零でないビットを含む２進数により近似され、これは、乗算が単一のシフト及び加算演算を用いて実行することができることを意味している。最後に、［Feyg93］は、これも単一のシフト及び加算演算により実施することが可能なＡの改善された近似を説明している。
乗算を近似するために本発明において実際に使用される方法（又は複数の方法）は、以下の通りである。確率（ｐ）が、ＮＰビットを用いて記載されるとする。例えば、ＮＰ＝８なら、ｐ＝1/4＝2exp{-2}＝0.01（２進）は２進01000000により表される。即ち、“0.1”は含まれない。何故なら、これは全ての確率に対して同一であるからである。ＡレジスタのサイズはＮＡ＝ＮＰ＋ＮＸビットに選定され、ここでＮＸは乗算に用いられるＡの値を近似するために使用されるビット数を表す。例えば、ＮＸ＝３及びＡ＝3/4＝0.11とすると、Ａは11000000000を含む８＋３＝１１ビットのレジスタである（ここでも、“0.1”は除去されている。何故ならＡを常に１より小となるように正規化するからである）。乗算に関しては、Ａを３ビットの数で近似する。この場合、最良の近似は１１０であることは明らかである。かくして、近似乗算Ａ・ｐの結果は00110000000、即ち、ここでも１１ビットの数となる。このような近似乗算の構成は、なかでも、［Feyg93］で提案されている。
以下では、ＮＡビット数Ａがどの様にしてＮＸビットにより近似されるべきかを説明する。
Ａを近似する最初の方法（方法Ｐ１）は、Ａを切り捨てる（truncate）代わりにＮＸビットに丸める（round）手段を有する。丸めるとは、Ａの(NX+1)番目のビットが０であればＡをＮＸビットまでで切り捨て、(N+1)番目のビットが１である場合は該切り捨て処理された表現に１が加算されることを意味する。例えば、Ａ＝1101…であれば、３ビット近似は１１１となる。適用される丸めは複雑さを増加させる。何故なら、約半分の場合において、切り捨て処理された表現に１が加算されねばならず、これは加算演算又はテーブルのルックアップの何れかがなされなければならないことを意味するからである。
代替え例（方法Ｐ２）として、“部分的丸め”と呼ばれるものを採用することが提案される。部分的丸めによれば、(NX+1)番目のビットが‘１’であり、且つ、NX番目のビットが‘０’である場合にのみ、１が上記の切り捨て処理された表現に加算される。実施化においては、これは、Ａの近似のNX番目のビットは、元のＡのNX番目のビットと(NX+1)番目のビットとの論理和に等しいことを意味する。例えば、Ａ＝1011…は101により近似され、Ａ＝1001…も同様に101により近似されるが、Ａ＝1000…は100により近似される。部分的丸めは、約７５％の場合において、“完全な丸め”と同一の近似になることに注意されたい。
他の代替え例（方法Ｐ３）においては、ＡをＮＸビットまでで切り捨てると共に該近似のNX番目のビットを常に１に設定することによりＡを近似することが提案される。これは、Ａに対する可能性のある近似値の半分を除くので、該例はハードウェアによる実施化の複雑さを更に減少させるという考えに基づいている。
幾つかの既知の方法の性能が、上述した３つの新たな方法と比較された。種々の方法の性能が表に掲載されている。該表に上述した３つの近似方法（Ｐ１、Ｐ２及びＰ３）に加えて示されている方法は、‘基準’により示された、完全なＮＡｘＮＰビットの乗算を計算し、ＡをＮＡビットまでで切り捨てるのみの基準方法、［Moff95］の方法、［Chev91a］の方法、Feyg93(1)により示されるFeyg93の第３節に記載された方法、Feyg93(2)により示されるFeyg93の第４節に記載された方法である。
0004179640.tif 000004
掲載された数値は圧縮されたファイルの相対サイズであり、100は乗算の不完全な近似による“損失無し”に相当する。例えば、100.57なる数値は、圧縮されたファイルのサイズが近似乗算のため0.57％だけ増加されたことを意味する。
予期したように、方法Ｐ２の性能はMoff95の方法のものよりは良好であるが、方法Ｐ１のもののようには良好ではない。
方法Ｐ２は良い妥協点である。即ち、ＮＸ＝３及びＮＸ＝４に対するＰ２は、性能と複雑さとの間の良い取り引きをもたらしている。何故なら、その性能は少ない複雑さで方法Ｐ１のものと実際上同じであるからである（上記表参照）。ＮＸ＝２に対しては、方法Ｐ１は好ましい方法である一方、方法Ｐ３はＮＸ＝５及びそれより大きいものに対して使用することができる。
２進でない場合は、Ａの値を丸めにより近似することができる方法は、アルファベットサイズが増加する場合に、ＭＰＳに対して残される“余裕”がないという潜在的な問題がある［Feyg93］。Feyg93(2)の方法に関しては、アルファベットサイズに対する最悪の限界は、１１である［Feyg93］。ここで提案されている新たな近似方法は、Ａが丸めにより増加され得る量が、ＮＸが増加されるにつれて減少するという利点を有している。従って、確率の分布がアルファベットサイズが制限される（及び切り捨てのみ又は切り下げのみが可能な方法の性能では不十分である）ようなアプリケーションが存在するなら、ＮＸを増加させることにより大きなアルファベットを扱うことができる。
エンコーダにおける再正規化ステップでのキャリーオーバー制御の問題は、元々、“ビット詰め込み（bit stuffing）”と呼ばれる技術により解決されていた［Lang81］。この技術は、一連の１ビットに出会った場合、符号化されたストリームに０詰め込みビットを挿入することによりキャリーを“捕捉”する。この技術の欠点は、余分な詰め込みビットにより圧縮効率を低減してしまい、デコーダにおいて特別な処理を必要とする点にある。
圧縮性能に影響を与えることなくキャリーオーバーを防止する方法が［Witt87］に記載されている。この方法は、デコーダの複雑さが幾らか増加するという欠点を有している。［Witt87］のアイデアは［Cham90］に、デコーダの複雑さを増加させることなく使用することができるように適用された。
ここでは、デコーダの複雑さを増加させることのない別の解決策を提案する。本発明によるエンコーダ再正規化処理のフローチャートが第６図に示されている。主な改良点は、C<0.10…0?なるブロックである。この同じブロックに関して、従来技術はC+A<=1.0…?を使用し、従って本提案に較べて余分な加算演算を必要とする。
エンコーダについての説明を完全にするために、初期化及び終了ブロックが第７図及び第８図に各々示されている。カウンタ変数は、第６図に示したエンコーダの再正規化ブロックで使用されるものと同一である。Ｃのサイズは(NA+1)ビットであるので（エンコーダにおいて）、ＣはＮＡの分数ビット（“小数点以降のビット”）を有し、これらは第８図に示されるように終了時に出力される。
デコーダの初期化は第９図に示されている。Ｃレジスタは、ストリームから(NA+1)ビットを読み取ることにより満たされる。読み取られる最初のビットは“ダミー”である。何故なら、該ビットは常に“０”ビットであるからである。デコーダにおけるＣレジスタのサイズはＮＡビットのみであり、従ってエンコーダにおけるより１だけ少ない。デコーダにおいては、特別な終了は存在しない（第４図の“終了”ブロックは空である）。デコーダにおける再正規化（第４図における“…を再正規化し…”ブロック）は第１０図に示されている。
第１１図は、本発明によるエンコーダ装置の一実施例を示している。該装置は、情報信号及び確率信号を各々入力する入力端子100及び102を有している。上記情報信号はｂビットシンボルの直列系列を有し、ｎはｎ≧１が成り立つ整数である。入力端子102に供給される確率信号は、上記情報信号における各シンボルに対し１以上の確率を有している。２進シンボルに対しては、該確率信号は各シンボルに対して１つの確率を有する。Ａパラメータ及びＣパラメータを記録するために、有限のサイズの第１及び第２のレジスタ104及び106が存在する。
上記情報信号に対して算術符号化を実行するために、処理ユニット108が利用可能である。該処理ユニット108についての詳細に立ち入ることなく、このユニットは、Ａ及びＣパラメータに関する値を上記第１及び第２のレジスタから取り出す回路、並びにシンボルを符号化した後、Ａ及びＣに関する更新され且つ再正規化された値を第１及び第２のレジスタ104及び106に各々記憶する回路を有すると理解されたい。更に、ユニット108は、第１のレジスタ104から取り出された値に対応する値の区間を、入力端子102に供給された前記の少なくとも１つの確率値に対応する副区間に分割する回路、及び入力端子100に供給された前記シンボルに応答して上記副区間のうちの１つを選択する回路を有している。
Ａ及びＣパラメータを更新する回路は、斯かる回路が、Ａ値を上記の選択された副区間のサイズに従がわせ、且つ、Ｃ値を該副区間の境界に従わせるために必要な場合は、存在する。
出力端子110は、符号化されたシンボルに応答して符号化されたビットを出力するために利用可能である。
Ａ及びＣパラメータを、それらの対応するレジスタから取り出す取出手段は、計算Ａ・ｐを実行するに先立ち、該Ａパラメータの値を切り捨てる手段を更に有している。即ち、この切り捨ては以下のようであり得る。Ａの値が0.b0b1…bi-1bi…のように表されると仮定する。この値はビットbi-1までで切り捨てられ、biが‘１’に等しい場合は、Ａの該切り捨て処理された値にビットbi-1の位置で‘１’が加算される。
他の入念例では、Ａパラメータの値はビットbi-1までで切り捨てられ、bi-1＝‘０’且つbi＝‘１’の場合はビットbi-1は‘１’に増加される。更に他の入念例では、Ａパラメータはビットbi-1までで切り捨てられ、ビットbi-1は‘１’に等しくされる。
処理ユニット108が第１、２、３、６、７及び８図に示された方法を実行することができることは分かるであろう。
好ましくは、該エンコーダ装置には更に、上記符号化された情報信号をチャンネル符号化された情報信号にチャンネル符号化する（必要なら、及び誤り訂正符号化する）既知のチャンネル符号化ユニット112、及び該チャンネル符号化された信号を磁気記録担体116又は光学記録担体118のような記録担体上に書き込む書込ユニット114が設けられる。
第１２図は、本発明によるデコーダ装置の一実施例を示している。該デコーダ装置は、符号化された情報信号を入力するための入力端子120を有している。Ａパラメータ及びＣパラメータを各々記憶するために、有限のサイズの第１及び第２のレジスタ122及び124が存在する。
処理ユニット126が設けられ、該処理ユニットは、入力端子134を介して該処理ユニット126に供給される確率信号に応答して、入力端子120を介して入力される上記符号化された情報信号に算術復号を実施する。上記確率信号は既知の方法で得ることができる。１ビットオーディオ信号に対する確率を導出する一例が、［Bruek97］に示されている。本例では、確率は、出力端子128に供給される復号された出力信号から、即ち予測フィルタ136において該復号された出力信号に予測フィルタ処理を実行すると共に、確率決定ユニット138において該予測フィルタ136の出力信号に応答して確率信号を発生することにより、導出される。処理ユニット126の詳細に立ち入ることなく、このユニットは、第１及び第２のレジスタからＡ及びＣパラメータに関する値を取り出す回路、並びにシンボルを復号した後Ａ及びＣに関する更新され且つ再正規化された値を第１及び第２のレジスタ122及び124に各々記憶する回路を有していると理解されたい。更に、上記ユニット126は第４、５、９及び１０図に示されるステップを実行する回路も有している。
Ａパラメータの値をレジスタ122から取り出す上記回路は、更に、計算Ａ・ｐを実行するに先立ちＡパラメータの値を切り捨てる手段も有している。この切り捨てはエンコーダに関して前述したのと同じ方法であるので、これ以上の説明は行わない。
好ましくは、上記デコーダ装置には、更に、前記チャンネル符号化された情報信号を算術デコーダ126用の算術的に符号化された情報信号にチャンネル復号する（必要なら、及び誤りを訂正する）既知のチャンネル復号ユニット132、及び上記チャンネル符号化された信号を磁気記録担体116又は光学記録担体118のような記録担体から読み取る読取ユニット130が設けられる。
算術符号化は、ビデオ及びオーディオ用の極最近の無損失及び損失のある符号化方法に適用される。該符号化は、コンピュータデータ（例えば、テキストファイルのような）の圧縮にも適用することができる。ここで目論まれた応用例は、１ビットオーディオ信号の無損失符号化である。この点に関しては、ヨーロッパ特許出願第97201680.2号（出願人整理番号：PHN16405）に対応する米国特許出願第08/966375号、及び国際特許出願第IB97/01156号（出願人整理番号：PHN16452）に対応する米国特許出願第08/937435号を参照されたい。
本発明は、その好ましい実施例に関して説明したが、これらは限定するような例ではないと理解されたい。従って、当業者にとっては、請求項に記載される本発明の範囲から逸脱することなく、種々の変形が明らかであろう。
更に、本発明は各々の及び全ての新規な特徴又は特徴の組合せにも存在する。
参考文献：
［Lang81］１９８１年６月のIEEE Trans. on Com.、第COM-29巻、第８５８〜６７頁、G.G. Langdon他による“算術符号化による白黒画像の圧縮”
［Witt87］１９８７年６月のCommunications ACM、第３０巻、第５２０〜５４０頁、I.H. Witten他による“データ圧縮用の算術符号化”
［Lang84］１９８４年３月のIBM J. Res. Develop.、第２８巻、第１３５〜１４９頁、G.G. Langdonによる“算術符号化の概説”
［Penn88］１９８８年１１月のIBM J. Res. Develop.、第３２巻、第７１７〜２６頁、W.B. Pennebaker他による“Ｑコーダ適応型２進算術コーダの基本原理の概要”
［Riss89］１９８９年２月のIEEE Trans. on Com.、第３７巻、第９３〜８頁、J. Rissanen他による“乗算無し多重アルファベット算術コード”
［Cham90］米国特許第４９７３９６１号
［Chev91a］１９９１年のデータ圧縮会議（ＤＣＣ’９１）、第４３〜５２頁、D. Chevion他による“算術符号化の高効率乗算無し近似”
［Chev91b］米国特許第４９８９０００号
［Feyg93］１９９３年３月３０日〜４月１日のデータ圧縮会議（ＤＣＣ’９３）、第１１８〜１２７頁、G. Feygin他による“算術符号化の乗算無し近似における誤り及びＶＬＳＩ複雑さの最小化”
［Howard94］１９９４年６月のProc. IEEE、第８２巻、第６号、第８５７〜６５頁、P.G. Howard他による“データ圧縮用の算術符号化”
［Moff95］１９９５年のデータ圧縮会議（ＤＣＣ’９５）、第２０２〜１１頁、A. Moffat他による“算術符号化再訪問”
［Bruek97］１９９７年９月２６〜２９日のＡＥＳ第１０３回会議で提示された、F. Buekers他による“１ビットオーディオ信号の改善された無損失符号化”、予稿4563(I-6)
【図１】
0004179640.tif 000005
【図２】
0004179640.tif 000006
【図３】
0004179640.tif 000007
【図４】
0004179640.tif 000008
【図５】
0004179640.tif 000009
【図６】
0004179640.tif 000010
【図７】
0004179640.tif 000011
【図８】
0004179640.tif 000012
【図９】
0004179640.tif 000013
【図１０】
0004179640.tif 000014
【図１１】
0004179640.tif 000015
【図１２】
0004179640.tif 000016