(57)【特許請求の範囲】
【請求項１】
複数の情報シンボルに対して該情報シンボルの生起確率に応じた符号語長を有する符号語をそれぞれ割り当て、入力された情報シンボルに対応した符号語を符号化データとして出力する可変長符号化方法において、
複数の対応方法から選択された一つの対応方法に従って、入力された情報シンボルに符号語を対応付け、該対応付けられた符号語の値を表す符号値を出力するステップと、
複数の生成方法から選択された一つの生成方法に従って、前記符号値から計算によって（ａ）予め定められた０と１の数によって符号語の区切りが分かる、（ｂ）複数の符号語を語尾を揃えて並べたときに各符号語が一致しない、及び（ｃ）同一の符号語長を有する各符号語間のハミング距離が２以上、という条件を満たすように構成された前記符号語を生成するステップと
を具備する可変長符号化方法。
【請求項２】
複数の情報シンボルに対して該情報シンボルの生起確率に応じた符号語長を有する符号語をそれぞれ割り当て、入力された情報シンボルに対応した符号語を符号化データとして出力する可変長符号化装置において、
複数の対応方法から選択された一つの対応方法に従って、入力された情報シンボルに符号語を対応付け、該対応付けられた符号語の値を表す符号値を出力する情報シンボル対応部と、
複数の生成方法から選択された一つの生成方法に従って、前記符号値から計算によって（ａ）予め定められた０と１の数によって符号語の区切りが分かる、（ｂ）複数の符号語を語尾を揃えて並べたときに各符号語が一致しない、及び（ｃ）同一の符号語長を有する各符号語間のハミング距離が２以上、という条件を満たすように構成された前記符号語を生成する符号語生成部と
を具備する可変長符号化装置。
【請求項３】
情報シンボルに対応した（ａ）予め定められた０と１の数によって符号語の区切りが分かる、（ｂ）複数の符号語を語尾を揃えて並べたときに各符号語が一致しない、及び（ｃ）同一の符号語長を有する各符号語間のハミング距離が２以上、という条件を満たすように構成された符号語により構成される可変長符号化データを復号して復号結果を出力する可変長復号化方法であって、
複数の生成方法から選択された一つの生成方法に従って、前記可変長符号化データに含まれる各符号語から計算によって復号値を生成するステップと、
複数の対応方法から選択された一つの対応方法に従って、前記復号値に情報シンボルに対応付け、該対応付けられた情報シンボルを前記復号結果として出力するステップと
を具備する可変長復号化方法。
【請求項４】
情報シンボルに対応した（ａ）予め定められた０と１の数によって符号語の区切りが分かる、（ｂ）複数の符号語を語尾を揃えて並べたときに各符号語が一致しない、及び（ｃ）同一の符号語長を有する各符号語間のハミング距離が２以上、という条件を満たすように構成された符号語により構成される可変長符号化データを復号して復号結果を出力する可変長復号化装置であって、
複数の生成方法から選択された一つの生成方法に従って、前記可変長符号化データに含まれる各符号語から計算によって復号値を生成する復号値生成部と、
複数の対応方法から選択された一つの対応方法に従って、前記復号値に情報シンボルに対応付け、該対応付けられた情報シンボルを前記復号結果として出力する情報シンボル対応部と
を具備する可変長復号化装置。
【請求項５】
前記復号値生成部は、さらに前記可変長符号化データについて検出された所定の区間毎に各符号語の符号語長をチェックして誤りを検出する請求項４記載の可変長復号化装置。
【請求項６】
複数の情報シンボルに対して該情報シンボルの生起確率に応じた符号語長を有する符号語をそれぞれ割り当て、入力された情報シンボルに対応した符号語を符号化データとして出力する可変長符号化処理をコンピュータに行わせるためのプログラムであって、
複数の対応方法から選択された一つの対応方法に従って、入力された情報シンボルに符号語を対応付け、該対応付けられた符号語の値を表す符号値を出力する処理と、
複数の生成方法から選択された一つの生成方法に従って、前記符号値から計算によって（ａ）予め定められた０と１の数によって符号語の区切りが分かる、（ｂ）複数の符号語を語尾を揃えて並べたときに各符号語が一致しない、及び（ｃ）同一の符号語長を有する各符号語間のハミング距離が２以上、という条件を満たすように構成された前記符号語を生成する処理とを前記コンピュータに行わせるためのプログラム。
【請求項７】
情報シンボルに対応した（ａ）予め定められた０と１の数によって符号語の区切りが分かる、（ｂ）複数の符号語を語尾を揃えて並べたときに各符号語が一致しない、及び（ｃ）同一の符号語長を有する各符号語間のハミング距離が２以上、という条件を満たすように構成された符号語により構成される可変長符号化データを復号して復号結果を出力する可変長復号化処理をコンピュータに行わせるためのプログラムであって、
複数の生成方法から選択された一つの生成方法に従って、前記可変長符号化データに含まれる各符号語から計算によって復号値を生成する処理と、
複数の対応方法から選択された一つの対応方法に従って、前記復号値に情報シンボルに対応付け、該対応付けられた情報シンボルを復号結果として出力する処理とを前記コンピュータに行わせるためのプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、可変長符号化／復号化方法及び装置に関する。
【０００２】
【従来の技術】
可変長符号化は、入力された情報シンボルに対応した符号長の符号語を符号化データとして出力する技術である。可変長符号化に際しては、各情報シンボルの出現頻度（生起確率）に基づき、頻繁に出現する情報シンボルに対しては短い符号長の符号、希にしか出現しない情報シンボルに対しては長い符号長の符号をそれぞれ割り当てることにより、符号化データとして出力される符号語が平均的に短い符号長とされる。その結果、符号化前と比較して情報のデータ量を大幅に圧縮することができる。このような可変長符号の構成方法としては、無記憶情報源で最適なハフマンのアルゴリズムが知られている。
【０００３】
一般に、可変長符号化は情報シンボルに可変長符号の符号語を対応付ける符号語テーブルを用いて行われる。符号語テーブルを用いる方法では、例えば動画像符号化における変換係数のように、可変長符号化の符号化対象となる情報シンボルの数が非常に多い場合には、符号語テーブルのサイズが過大になるという問題がある。
【０００４】
符号語テーブルを用いず、情報シンボルに対して計算で符号語を生成する方法も提案されている。計算で符号語を生成する手法として、正整数に対する符号化である図９に示されるEliasのδ符号（IEEE Trans. IT vol.IT-21,no.2.pp.194-203,1975）や、Golombの幾何分布に対する符号化（IEEE Trans. IT vol.IT-12,no.3.pp.399-401,1966）などが以前より知られているが、いずれも適用できる情報シンボルの出現確率分布が限定され、符号化効率が低いという問題がある。
【０００５】
さらに可変長符号の一般的な問題としては、符号化データに何らかの理由で誤りが混入した場合に、誤りが混入した以後のデータについては、その影響が伝搬して正しく復号化装置で復号することができない上に、誤りが検出されないということが挙げられる。この現象は自己同期と呼ばれ、誤りが伝搬している時に誤って復号された符号語が正しい符号語の語尾と一致することで、符号語自体の同期は回復するために生じる。
【０００６】
図８に、この様子を示す。図８（ａ）に示される符号化データの符号語ｃ（＝００１）の先頭ビットに誤りが生じて符号語ｂと同じとなり、図８（ｂ）に示される復号データでは、符号語ｃの語尾が符号語ｂと一致している。このとき、復号データにおいては誤りが生じた符号語ｃの次の符号語ａで同期が回復しているが（自己同期）、復号データの符号語数が１つ増加してしまっている。自己同期が生じると、符号語の同期が回復するため符号語自体は正しく復号される。
【０００７】
しかし、動画像符号化などに見られる実際の符号化では、符号語より上位のレベルで予測が行われていたり、ある種の文法に基づいて符号化されていたりするため、自己同期が生じた場合には文法的あるいは意味的に正しい復号ができず、しかも誤りが検出されない。従って、誤り対策をとることができず、誤りの影響が復号結果に現れてしまうという問題がある。
【０００８】
【発明が解決しようとする課題】
上述したように、従来技術に基づく可変長符号化のうち符号語テーブルを用いる方法は、情報シンボル数が大きい場合にテーブルのサイズが過大となり、計算により符号語を生成する方法では情報シンボルの出現確率分布によっては符号化効率が低下するという問題点がある。
【０００９】
さらに、従来技術に基づく可変長符号では、自己同期が生じやすいために正しい復号ができず、また誤りを検出できないという問題点がある。
【００１０】
本発明は、大きなテーブルを用いることなく、高い符号化効率を実現できる可変長符号化／復号化方法及び装置を提供することを目的とする。
【００１１】
さらに、本発明の他の目的は誤りの検出が可能な可変長符号化／復号化方法及び装置を提供することにある。
【００１２】
【課題を解決するための手段】
上記課題を解決するため、本発明では複数の情報シンボルに対して該情報シンボルの生起確率に応じた符号語長を有する符号語をそれぞれ割り当て、入力された情報シンボルに対応した符号語を符号化データとして出力する可変長符号化に際して、複数の対応方法から選択された一つの対応方法に従って、入力された情報シンボルに符号語を対応付け、該対応付けられた符号語の値を表す符号値を出力し、複数の生成方法から選択された一つの生成方法に従って、符号値から計算によって符号語を生成する。
【００１３】
一方、こうして得られた情報シンボルに対応した符号語により構成される可変長符号化データを復号して復号結果を出力する可変長復号化に際しては、複数の生成方法から選択された一つの生成方法に従って、可変長符号化データに含まれる各符号語から計算によって復号値を生成し、複数の対応方法から選択された一つの対応方法に従って復号値に情報シンボルに対応付け、該対応付けられた情報シンボルを復号結果として出力する。
【００１４】
このように本発明においては、情報シンボルに符号語を対応させ、これによって得られる符号値から計算によって符号語を生成するようにした上で、対応方法及び生成方法を切り替え可能としていることから、情報シンボルの生起確率の変動に対しても対応することが可能となる。また、計算によって符号語を生成するため、これらの切り替えを行っても情報シンボルと符号語を対応させる場合に必要なメモリ量や符号語テーブルのためのメモリ量は増加しない。
【００１５】
また、所定の区間毎に符号化データの長さがわかる場合、符号化データに誤りが混入したときに自己同期が生じていないならば、復号したデータの長さに違いが生じることから、そのデータ長をチェックすることで、その区間の誤りが混入しているかどうかが判定することができる。
【００１６】
ここで、計算によって符号語を生成する際に、（ａ）予め定められた０と１の数によって符号語の区切りが分かる、（ｂ）複数の符号語を語尾を揃えて並べたときに各符号語が一致しない、及び（ｃ）同一の符号語長を有する各符号語間のハミング距離が２以上、という条件を満たすように構成された符号語を生成することが望ましい。
【００１７】
このように符号語を生成すると、ある符号語に１ビットの誤りが生じたとしても、同一符号語長の他の符号語と同じ符号語に変化することはない。従って、このように構成された符号語は非常に自己同期しにくい性質を有するため、符号化データの長さが予めわかっている場合、誤りが符号化データに混入しても、自己同期することなく、使用していないビットパターンを発見することで誤りを検出できるか、あるいは、符号化データの最後で復号できないデータが生じることで、誤りを検出できる可能性が高くなる。
【００１８】
また、本発明によると複数の情報シンボルに対して該情報シンボルの生起確率に応じた符号語長を有する符号語をそれぞれ割り当て、入力された情報シンボルに対応した符号語を符号化データとして出力する可変長符号化処理をコンピュータに行わせるためのプログラムであって、複数の対応方法から選択された一つの対応方法に従って、入力された情報シンボルに符号語を対応付け、該対応付けられた符号語の値を表す符号値を出力する処理と、複数の生成方法から選択された一つの生成方法に従って、前記符号値から計算によって（ａ）予め定められた０と１の数によって符号語の区切りが分かる、（ｂ）複数の符号語を語尾を揃えて並べたときに各符号語が一致しない、及び（ｃ）同一の符号語長を有する各符号語間のハミング距離が２以上、という条件を満たすように構成された前記符号語を生成する処理とを前記コンピュータに行わせるためのプログラムを提供できる。
【００１９】
さらに、本発明によると情報シンボルに対応した（ａ）予め定められた０と１の数によって符号語の区切りが分かる、（ｂ）複数の符号語を語尾を揃えて並べたときに各符号語が一致しない、及び（ｃ）同一の符号語長を有する各符号語間のハミング距離が２以上、という条件を満たすように構成された符号語により構成される可変長符号化データを復号して復号結果を出力する可変長復号化処理をコンピュータに行わせるためのプログラムであって、複数の生成方法から選択された一つの生成方法に従って、前記可変長符号化データに含まれる各符号語から計算によって復号値を生成する処理と、複数の対応方法から選択された一つの対応方法に従って、前記復号値に情報シンボルに対応付け、該対応付けられた情報シンボルを復号結果として出力する処理とを前記コンピュータに行わせるためのプログラムを提供できる。
【００２０】
【発明の実施の形態】
以下、図面を参照して本発明の実施の形態を説明する。図１には、本発明の一実施形態に係る可変長符号化／復号化装置を含む符号化／復号化システムの構成を示す。符号化／復号化システムは、大きく分けて入力される情報シンボル１０を符号化して可変長符号化データを出力する符号化システム１００と、可変長符号化データの伝送または蓄積を行う伝送／蓄積系１０３、及び伝送／蓄積系１０３から入力される可変長符号化データを復号化して、復号結果２４及び誤り検出結果２６を生成する復号化システム１０４から構成される。
【００２１】
符号化システム１００は、入力された情報シンボル１０を可変長符号化する可変長符号化部１０１と区間設定部１０２を有する。可変長符号化部１０１は、予め用意された符号語テーブルを用いずに、入力された情報シンボル１０の値に対応した可変長符号の符号語を生成し、これを可変長符号化データ１４として出力する。
【００２２】
可変長符号化部１０１においては、情報シンボル１０と符号語との対応付けに関して複数の方法（対応方法）が用意され、また符号語の生成に関して複数の方法（符号語生成方法）に関して複数の方法（対応方法）が用意されており、外部より供給される切り替え信号１１，１２に応じて一つの対応方法及び符号語生成方法が選択される。切り替え信号１１，１２は、別途符号化された後に復号化システム１０４に送られるか、あるいは復号化システム１０４において他の符号化パラメータの値によって求めることができるものとする。
【００２３】
可変長符号化部１０１から出力される可変長符号化データ１４は、区間設定部１０２より所定の区間に分けられ（区間設定という）、符号化システム１００から出力される。区間設定部１０２からの区間設定後の符号化データ１５は伝送／蓄積系１０３に入力され、伝送蓄積系１０３から出力される可変長符号化データ１６は復号化システム１０４に入力される。
【００２４】
復号化システム１０４は、区間検出部１０５と可変長復号化部１０６及び長さ判定部１０７を有する。区間検出部１０５では、入力される可変長符号化データ１６から区間設定部１０２で設定された区間が検出される。可変長符号化データ１６は、区間検出部１０５で検出された区間毎の可変長符号化データ２０として可変長復号化部１０６に入力される。可変長復号化部１０６は、予め用意された符号語テーブルを用いずに、入力された可変長符号化データ２０に含まれる各符号語から計算によって復号値を生成し、該復号値に情報シンボルを対応付けて復号結果２４として出力する。
【００２５】
可変長復号化部１０６においては、復号値の生成に関して複数の方法（復号値生成方法）が用意され、また復号値と情報シンボルとの対応付けに関して複数の方法（対応方法）が用意されており、例えば前述のように符号化システム１００より供給されるか、あるいは前述のように復号化システム１０４内で他の符号化パラメータの値に基づいて生成される切り替え信号２１，２２に応じて一つの対応方法及び符号語生成方法が選択される。
【００２６】
また、可変長復号化部１０６では後述するように誤り検出が行われ、誤り検出結果２６が出力されると共に、可変長符号化データ２０に含まれる符号語の長さを示す符号語長情報２５が生成され、長さ判定部１０７に送られる。長さ判定部１０７においては、区間検出部１０５で検出された区間毎に符号語長情報２５がチェックされることにより、誤り検出が行われる。
【００２７】
図２に可変長符号化部１０１の構成を示す。可変長符号化部１０１は、情報シンボル対応部２０１と符号語生成部２０２を有する。情報シンボル対応部２０１は、入力された情報シンボル１０の値に対応する符号値１３を出力する。情報シンボル対応部２０１は複数の対応テーブル、言い換えれば複数の対応方法を備えており、これらが情報シンボル対応切り替え信号１１により切り替えられ、一つの対応テーブルが選択される。
【００２８】
符号語生成部２０２は、情報対応部２０１からの符号値１３を入力として、符号毎に予め決められた計算方法によって符号語１４を計算により生成する。符号語生成部２０２は複数の符号語生成方法を備えており、これらが符号語生成切り替え信号１２によって切り替えられ、一つの符号語生成方法が選択される。
【００２９】
図３には、可変長復号化部１０４の構成を示す。可変長復号化部１０４は、復号値生成部３０１と情報シンボル対応部３０２を有する。復号値生成部３０１では、図１中に示した区間検出部１０５で検出された区間毎に、入力される可変長符号化データ２０から符号毎に予め決められた計算方法によって復号値２３を計算により生成する。復号値生成部３０１は複数の生成方法を備えており、これらが復号値生成切り替え信号２１によって切り替えられ、一つの復号値生成方法が選択される。さらに、復号値生成部３０１は区間検出部１０５で検出された区間毎の可変長符号化データ２０の長さをチェックし、そのチェック結果から誤りを検出して誤り検出結果２６を出力する機能を有する。
【００３０】
情報シンボル対応部３０２は、復号値生成部３０１で生成された復号値２３を入力として、対応する情報シンボルを復号結果２４として出力する。情報シンボル対応部３０２は複数の対応テーブル、言い換えれば複数の対応方法を備えており、これらが情報シンボル対応切り替え信号２１により切り替えられ、一つの対応テーブルが選択される。
【００３１】
次に、図４を用いて区間設定部１０２における可変長符号化データに対する区間設定方法の例について説明する。図４（ａ）の区間設定方法では、ヘッダの直後に可変長符号化データの長さ情報が存在し、ここには可変長符号化データのビット数が記述されている。区間検出部１０５では、符号化データの長さ情報を復号することで、符号化データのビット数が判明する。図４（ｂ）の区間設定方法は、同期符号を用いている。この場合、区間検出部１０５では次の同期符号までのビット数をカウントし、ヘッダとスタッフィングのビット数を差し引くことによって符号化データのビット数が判明される。
【００３２】
図５は、図２中の情報シンボル対応部２０１及び図３中の情報シンボル対応部３０２で使用される対応テーブルの例と、各対応テーブルにおける情報シンボルと符号値との対応関係の例を示している。この例は、動画像符号化において画像信号をブロック毎に直交変換して得られた係数（例えば、ＤＣＴ係数）を量子化した後の値をランレングス符号化によて可変長符号化した場合である。情報シンボルは、この例ではブロックに以後非ゼロ係数がないことを示すＥＯＢ（End Of Block）記号と、ラン（Run）とレベル（Level）の組み合わせである。ここではシンボル対応テーブルはＡとＢの２種類があり、情報シンボル対応切り替え信号によって情報シンボルと符号値との対応を切り替えることができる。
【００３３】
次に、図６を用いて符号語生成部２０２における符号語生成のための計算手法の具体例について説明する。まず、符号値ｎに対して次の不等式を満足する１以上の整数値ｍを求める。
【数１】
0003673222.tif 000002
【００３４】
次に、これらの整数値ｍと符号値ｎから次式の計算によって符号語Ｃ（ｎ）を得る。
まず、ｎの値が左辺(1/2)ｍ（ｍ−１）と等しい場合は、符号語Ｃ（ｎ）は次のようにする。
【数２】
0003673222.tif 000003
それ以外の場合は、
【数３】
0003673222.tif 000004
として、次の符号語を生成する。
【数４】
0003673222.tif 000005
【００３５】
一方、復号値生成部３０１では次のような操作を行う。最初のビットが０ならば、それに続く連続する１の数ｒをカウントし、次式で計算される値を復号値ｎとする。
【数５】
0003673222.tif 000006
【００３６】
もし、最初のビットが１ならば、１が合計３回に出現するまでＬビットの符号化データを読み込み、２番目の１が出現した位置をＳビット目とすると、復号値ｎは次の式で計算される。
【数６】
0003673222.tif 000007
【００３７】
上述した符号語生成方法によって得られる符号語では、図６に示されるように予め定められた０と１の数によって符号語の区切りが分かり、また同一の符号語長の符号語間のハミング距離が必ず２以上になる。ハミング距離とは周知のように、同一の符号語長の符号語間で０と１が一致しないビットの数のことを指す。さらに、これらの符号語は複数の符号語を語尾を揃えて並べたときに各符号語が一致することがない。したがって、符号語のビットに誤りが入った場合でも自己同期しない性質をもっている。
【００３８】
次に、図７を用いて符号語生成部２０２における符号語生成のための計算手法の他の具体例について説明する。まず、符号値ｎに対して次の不等式を満足する１以上の整数値ｍを求める。
【数７】
0003673222.tif 000008
【００３９】
次に、この整数値ｍと符号値ｎから次の数式の計算によって符号語Ｃ（ｎ）を得る。
【数８】
0003673222.tif 000009
ここで、β（ｎ、ｍ）は、整数ｎのｍビット表現である。
一方、復号値生成部３０１では次のような操作を行う。符号化データを２進系列ｂ1 ｂ2 …ｂL を次の不等式がはじめて成り立つＬビットまで読み込む。
【数９】
0003673222.tif 000010
次に、得られた２進系列ｂ1 ｂ2 …ｂL とＬの値から、次式の計算により復号値ｎを計算する。
【数１０】
0003673222.tif 000011
【００４０】
図６と図７によって生成される符号語は、いずれも最も短い符号語が２ビットであり、それから符号語長は１ビットづつ増加し、同一の符号語長の符号語数は１、２、３、４…と増加してゆく。つまり、幾何分布よりも確率分布の裾が長い分布に対して最適な符号となっている。そのような確率分布は、画像符号化の変換係数の量子化値をランレングス符号化した場合や、動きベクトルの差分値などにおいてしばしば見受けられることから、実用的にも効果が高い。
【００４１】
なお、情報シンボルの生起確率に応じて、符号語生成切り替え信号を使うことで、図６または図７に示した符号とＥｌｉａｓのδ符号と切り替えて使用してもよい。
【００４２】
上述した本発明の可変長符号化及び復号化の処理は、ハードウェアにより実現してもよいし、処理の一部または全部をコンピュータを用いてソフトウェアにより実行することも可能である。
【００４３】
【発明の効果】
以上説明したように本発明によれば、より符号化効率の高い符号語を生成及び復号でき、さらに誤りを検出することができる。
【図面の簡単な説明】
【図１】  本発明の一実施形態に係る可変長符号化／復号化装置を含む符号化／復号化システムの構成を示すブロック図
【図２】  同実施形態における可変長符号化部の構成を示すブロック図
【図３】  同実施形態における可変長復号化部の構成を示すブロック図
【図４】  区間設定の例を示す図
【図５】  情報シンボル対応表の例を示す図
【図６】  同実施形態における符号語生成結果の例を示す図
【図７】  同実施形態における符号語生成結果の他の例を示す図
【図８】  従来の可変長符号での自己同期の例を示す図
【図９】  従来のＥｌｉａｓのδ符号の例を示す図
【符号の説明】
１００…符号化システム
１０１…可変長符号化部
１０２…区間設定部
１０３…伝送／蓄積系
１０４…復号化システム
１０５…区間検出部
１０６…可変長復号化部
１０７…長さ判定部
２０１…情報シンボル対応部
２０２…符号語生成部
３０１…復号値生成部
３０２…情報シンボル対応部
【図１】
0003673222.tif 000012
【図２】
0003673222.tif 000013
【図３】
0003673222.tif 000014
【図４】
0003673222.tif 000015
【図５】
0003673222.tif 000016
【図６】
0003673222.tif 000017
【図７】
0003673222.tif 000018
【図８】
0003673222.tif 000019
【図９】
0003673222.tif 000020