JP3866687B2 - 可変長符号化方法及び装置 - Google Patents
可変長符号化方法及び装置 Download PDFInfo
- Publication number
- JP3866687B2 JP3866687B2 JP2003146489A JP2003146489A JP3866687B2 JP 3866687 B2 JP3866687 B2 JP 3866687B2 JP 2003146489 A JP2003146489 A JP 2003146489A JP 2003146489 A JP2003146489 A JP 2003146489A JP 3866687 B2 JP3866687 B2 JP 3866687B2
- Authority
- JP
- Japan
- Prior art keywords
- code
- length
- decoding
- decoded
- variable
- 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
Images
Landscapes
- Compression Or Coding Systems Of Tv Signals (AREA)
- Compression Of Band Width Or Redundancy In Fax (AREA)
- Compression, Expansion, Code Conversion, And Decoders (AREA)
Description
【０００１】
【発明の属する技術分野】
この発明は、可変長符号化方法及び装置に関する。
【０００２】
【従来の技術】
可変長符号は、シンボルの発生頻度に基づいて、頻繁に出現するシンボルは短い符号長の符号、希にしか出現しないシンボルは長い符号長の符号を割り当てることにより、平均的に短い符号長となるようにした符号系である。従って、可変長符号を用いると、符号化前のデータと比較して、データ量を大幅に圧縮することができる。このような可変長符号の構成方法としては、無記憶情報源で最適なハフマンのアルゴリズムが知られている。
【０００３】
可変長符号の一般的な問題として、符号化データに伝送路誤りその他の理由で誤りが混入した場合に、誤りが混入した以後のデータについては、その影響が伝搬することにより復号化装置で正しく復号することができなくなってしまうという点が挙げられる。そのため、伝送路において誤りが生じる可能性がある場合には、ある間隔で周期的に同期符号を挿入し、誤りの伝搬を防止する方法がとられるのが一般的である。同期符号には、可変長符号の組み合わせでは出現しないようなビットパターンが割り当てられる。この方法によれば、符号化データに誤りが生じ、復号できなくなったとしても、次の同期符号を見つけることにより、誤りの伝搬を防止し、正しく復号を行うことができる。しかし、このように同期符号を用いた場合でも、図３９（ａ）に示すように誤りが生じて正しく復号できない地点から、次の同期符号が見つかる地点までの間の符号化データについては、復号を行うことができない。
【０００４】
そこで、可変長符号を図４０に示す通常の構成から図４１に示すように変更して、図３９（ｂ）に示すように通常の順方向から復号可能な性質だけでなく、逆方向からも復号可能な符号の構成にする方法が知られている。また、このような符号は符号化データを逆方向からも読めることから、符号化データを蓄積するディスクメモリなどの蓄積媒体において逆転再生に用いることもできる。このような順方向のみならず逆方向からも復号可能な可変長符号のことを、ここではリバーシブル符号と呼ぶこととする。リバーシブル符号の一例は、例えば特開平５−３０００２７号公報「可逆可変長符号化方式」に記載されている。この公知例のリバーシブル符号は、図４０に示した順方向から復号可能な可変長符号であるハフマン符号の符号語の末尾に、図４１に示すようにそれぞれの符号語がそれより符号長の長い他の符号語の末尾と一致しない条件でビットを追加することによって、逆方向からも復号可能とした可変長符号である。
【０００５】
しかし、このリバーシブル符号は順方向からのみ復号可能な可変長符号の符号語の末尾にビットを付加するために、無駄なビットが多くなって平均符号長が長くなる。この結果、順方向からのみ復号可能な可変長符号と比較して符号化効率が大きく低下してしまう。
【０００６】
また、従来のリバーシブル符号のもう一つの問題点として、情報シンボル数が大きい場合には、可変長符号化／復号化装置で必要とされる記憶量が多くなるために、実用に適さないという点があった。情報シンボル数が大きい場合の例としては、動画像や静止画像の画像符号化でよく用いられるＤＣＴ係数の符号化がある。通常、画像符号化では８×８のＤＣＴ（離散コサイン変換）を行い、これにより得られたＤＣＴ係数と呼ばれる直交変換係数について８ビットの線形量子化を行う。さらに、量子化されたＤＣＴ変換係数について低域からジグザクスキャンを行い、零ランと非零の係数を組にして可変長符号化を行っている。
【０００７】
例えば、ＩＴＵ−Ｔ ＤＲＡＦＴ Ｒｅｃｏｍｍｅｎｄａｔｉｏｎ Ｈ．２６３（１９９５）では、量子化インデックス値は−１２７〜＋１２７（インデックス値０はランなので、インデックス数は２５３）、零ラン数は最大６３であり、またブロックの最後のＤＣＴ係数が非零の係数かどうかの区別をするような符号化を採用しているので、情報シンボル数は２５３×６４×２＝３２３８４と非常に大きな数になっている。そこで、Ｈ．２６３では出現確率の高いＤＣＴ係数については可変長符号で符号化するが、出現確率の低いＤＣＴ係数についてはブロックの最後の非零係数かどうかの区別を示す符号に１ビットの符号、零ランに６ビットの符号、量子化インデックスに８ビットの符号の計１５ビットの符号で固定長符号化を行い、この固定長符号の先頭にエスケープ符号と呼ばれる符号を付加する構成となっている。
【０００８】
全ての符号語を符号語テーブルとして持っていても符号化／復号化は可能であるが、上記のような符号構成になっていると、１５ビットの固定長符号の部分は可変長符号とは別個に符号化／復号化が可能であるため、出現確率の高いＤＣＴ係数とエスケープ符号の符号語テーブルを用意するだけでよい。従って、可変長符号の符号語テーブルを削減して記憶容量を低減することが可能となる。
【０００９】
しかし、従来のリバーシブル符号は前述したように順方向からのみ復号可能な可変長符号の符号語の末尾にビットを付加する必要があるために、エスケープ符号を付加することができない。従って、情報シンボル数が多い場合にも全ての情報シンボルに対応した符号語を用意する必要があり、記憶量が莫大なものとなってしまう。
【００１０】
【発明が解決しようとする課題】
上述したように、従来技術によるリバーシブル符号、すなわち順方向からも逆方向からも復号可能な可変長符号は、順方向からのみ復号可能な可変長符号の符号語の末尾にビットを付加することによってリバーシブル符号を構成するため、無駄なビットパターンが多くなって平均符号長が長くなり、順方向からのみ復号可能な可変長符号と比較して符号化効率の低下が著しくなるという問題があり、またこのようなリバーシブル符号を用いる可変長符号化／復号化装置では、何らかの形で全ての情報シンボルに対応した符号語を有する符号語テーブルを用意する必要があり、画像符号化のように情報シンボルの数が大きい場合、大きな記憶量を必要とするという問題があるため、いずれにしても実用に適さないという問題があった。
【００１１】
本発明は、順方向にも逆方向にも復号可能であって、実用性に富んだ可変長符号化方法及び装置を提供することを目的とする。
【００１２】
より具体的には、順方向にも逆方向にも復号可能であって、しかも情報シンボルの数が多い場合にも大きな記憶量を必要としない可変長符号化方法及び装置を提供することを目的とする。
【００１３】
【課題を解決するための手段】
上記の課題を解決するため、本発明では複数の情報シンボルに対して該情報シンボルの生起確率に応じた符号長を有する符号語をそれぞれ割り当て、入力された情報シンボルに対応した符号語を符号化データとして出力する可変長符号化において、入力された情報シンボルに対応して、順方向にも逆方向にも復号可能な複数の可変長符号のいずれかと、長さが等しい複数の等長符号のいずれかとの組み合わせからなる符号語を符号化データとして出力することを特徴とする。
【００１４】
言い換えれば、入力された情報シンボルに対応して、順方向にも逆方向にも復号可能な複数の可変長符号の先頭および末尾の少なくとも一方に、長さが等しい複数の等長符号のいずれかを付加して組み合わせ、該組み合わせ後の符号語を符号化データとして出力することを特徴とする。
【００１５】
さらには、入力された情報シンボルに対応して、順方向にも逆方向にも復号可能な複数の可変長符号の先頭および末尾の少なくとも一方に、組み合わせ後の符号語が順方向にも逆方向にも復号可能となるように長さが等しい複数の等長符号のいずれかを付加して組み合わせ、該組み合わせ後の符号語を符号化データとして出力することを特徴とする。
【００１６】
【発明の実施の形態】
以下、図面を参照して本発明の実施形態を説明する。
【００１７】
図１は、本発明の一実施形態に係る可変長符号化／復号化装置の構成を示すブロック図である。本実施形態の可変長符号化／復号化装置は、大きく分けて符号語テーブル作成部１０１、符号化部１１４、伝送系または蓄積系１０４および復号化部１１５からなる。まず、これら各部の機能について簡単に説明すると、符号語テーブル作成部１０１は情報シンボルの生起確率に基づいて符号語テーブルを作成し、符号化部１１４内の符号化テーブル１０２と、復号化部１１５内の順方向符号語テーブル１１０および逆方向符号語テーブル１１２に送る。符号化部１１４は、情報シンボルを可変長符号に符号化し、その可変長符号を符号化データとして伝送系または蓄積系１０４へ出力する。復号化部１１５は、伝送系または蓄積系１０４を介して入力されてきた符号化データを復号して元の情報シンボルを再生する。
【００１８】
次に、本実施形態の各部の詳細な構成と動作を説明する。符号化部１１４において、入力された情報シンボルは符号化器１０３に入力される。一方、符号語テーブル１０２は、符号語テーブル作成部１０１によって予め作成された情報シンボルと可変長符号の符号語とを対応させて格納している。符号化器１０３は符号語テーブル１０２に格納されている符号語の中から、入力された情報シンボルに対応した符号語を選択して符号化データとして出力する。この符号化データは、伝送系または蓄積系１０４を通して復号化部１１５に送られる。この際、符号化データには一定周期毎に同期コードが挿入される。
【００１９】
復号化部１１５では、伝送系または蓄積系１０４より入力された符号化データから同期コード検出部１０５で同期コードを検出し、同期コードと同期コードの間の符号化データをバッファ１０６に蓄積する。順方向復号化器１１０では、順方向復号木作成部１１１からの順方向復号木に基づいて、バッファ１０６に蓄積された符号化データの先頭から復号を開始し、逆方向復号化器１０８では、逆方向復号木作成部１１３からの逆方向復号木に基づいて、バッファ１０６に蓄積された符号化データの末尾から復号を開始する。
【００２０】
復号値判定部１０９では、順方向復号化器１０７によって得られた復号結果（順方向復号結果という）と、逆方向復号化器１０８によって得られた復号結果（逆方向復号結果という）から復号値を判定し、最終的な復号結果を出力する。すなわち、復号値判定部１０９では符号化データに誤りがあると、復号木に出現しないビットパターンが生じることから誤りの存在が分かるので、順方向復号結果と逆方向復号結果から図２に示すように復号値を判定する。図２は、同期コードと同期コードとの間の復号値判定方法を示している。
【００２１】
まず、図２（ａ）に示すように順方向復号結果と逆方向復号結果で誤りが検出される符号語の位置（誤り検出位置）が交差しない場合は、誤りが検出されなかった復号結果のみを復号値として使用し、二つの誤り検出位置の復号結果は復号値として使用せず、放棄する。
【００２２】
また、図２（ｂ）に示すように順方向復号結果と逆方向復号結果の誤り検出位置が交差する場合は、両方で誤りが検出されなかった復号結果を復号結果値として使用する。また、この場合には二つの誤り検出位置の符号語の間の復号結果は復号値として使用せず、放棄する。
【００２３】
また、図２（ｃ）に示すように順方向復号結果および逆方向復号結果のうち片方向の復号結果にしか誤りが検出されない場合（この例では、順方向復号結果にのみ誤りが検出されている）は、誤り検出位置の符号語に対する復号値を放棄し、それ以後の符号語に対する復号値は逆方向の復号結果を使用する。
【００２４】
さらに、図２（ｄ）に示すように同一の符号語について順方向復号結果および逆方向復号結果の両方に誤りが検出される場合は、図２（ｃ）と同様に誤り検出位置の符号語に対する復号値は放棄し、それ以後の符号語に対する復号値としては逆方向の復号結果を使用する。
【００２５】
符号語テーブル作成部１０１では、情報シンボルの生起確率に基づいて順方向にも逆方向にも復号可能な符号の符号語テーブルを作成する。符号語テーブル作成部１０１によって作成された符号語テーブルは、符号化部１１４内の符号語テーブル１０２と、復号化部１１５内の順方向符号語テーブル１１０および逆方向符号語テーブル１１２に送られる。順方向復号木作成部１１１では、順方向符号語テーブル１１０から順方向復号木を作成する。また、逆方向復号木作成部１１３では、逆方向符号語テーブル１１２から逆方向復号木を作成する。
【００２６】
図３は、符号語テーブル作成部１０１の構成を示すブロック図である。符号選択部２１は、情報シンボルの生起確率の情報を入力として、この情報に基づいて選択可能な符号系の中から最も平均符号長の小さいものを選択し、選択結果を符号語構成部２２に送る。符号語構成部２２では、符号語選択部２１で選択された符号の符号語を構成して、符号語テーブルを作成する。符号語構成部２２で作成された符号語テーブルは、符号化部１１４内の符号語テーブル１０２および復号化部１１５内の順方向符号語テーブル１１０に送られる。復号化部１１５内の逆方向符号語テーブル１１２には、順方向とは逆向きに記述された符号語テーブルが送られる。
【００２７】
符号選択部２１では、入力された情報シンボルを生起確率が大きい順に並べ替えてＳ＝｛Ｓ1 ，Ｓ2 ，…，Ｓn ｝とし、これらの情報シンボルＳの生起確率Ｐ＝｛ｐ1 ，ｐ2 ，…，ｐn ｝に基づいて、構成可能な符号の集合Ｃの中から、
【００２８】
【数１】
【００２９】
を満足する符号ｃを選択する。ここで、Ｌｉは符号語構成部２２より与えられる符号語の重みによって計算することができる符号長である。この場合の符号語の重みとは、符号語における“１”または“０”の数をいう。
【００３０】
以下、符号語構成部２２における符号語の構成方法について述べる。
【００３１】
図４は、本実施形態による可変長符号の基となる重みが一定の２進符号系列の作り方の例を示している。図４（ａ）に示すように、ｓｔａｒｔ地点からｅｎｄ地点に至る格子状の有向グラフを形成する。この有向グラフについてｓｔａｒｔ地点からｅｎｄ地点までの経路をたどる際、左側の経路を選択した時は“０”、右側の経路を選択した時は“１”をそれぞれ対応させることにより、図４（ｂ）に示す２進符号系列を生成する。この例では、符号長が５ビットで、重み（“１”の数）が２の２進符号系列を生成している。一般に、符号長がｎビットで重みがｗの２進符号系列は、ｎ個からｗ個を選択する組み合わせの数だけ存在する。ここでは、５個から２個を選択する組み合わせの数＝１０個の２進符号系列が存在することになる。
【００３２】
図５は、符号語構成部２２における順方向にも逆方向にも復号可能な可変長符号（以下、リバーシブル符号という）の符号語の第１の構成方法を示している。まず、図５の左側に示すように、符号長が短い順に（情報シンボル−１）個（この場合は、９個）だけ、図４の方法によって重み（“１”の数）が一定（この場合は、１個）の２進符号系列を作成する。次に、図５の右側に示すように、この２進符号系列のそれぞれの先頭と末尾に“１”を追加し、最も短い符号には０”を割り当てることによって、リバーシブル符号の符号語を構成する。このリバーシブル符号は、情報シンボルＡに対しては符号“０”、それ以外の情報シンボルＢ〜Ｊに対しては符号が“１”から必ず始まり、“１”が全部で３個出現したら符号が終わる符号構成、つまり符号の区切り（符号長）が分かる構成となっている。
【００３３】
可変長符号がリバーシブル符号、すなわち順方向にも逆方向にも復号可能な符号であるための必要十分条件は、全ての符号語が順方向の復号木の葉と逆方向の復号木の葉に割り当てられることである。復号木の葉とは、復号木の末端、つまりそれより先には何も無い個所をいう。例えば、図５の可変長符号は、全ての情報シンボルＡ〜Ｊに対応する符号語が図６（ａ）に示す順方向の復号木の葉にも、図６（ｂ）の逆方向の復号木の葉にも割り当てられることから、順方向にも逆方向にも復号可能であることが分かる。
【００３４】
図５の可変長符号の符号語構成方法のパラメータは、符号語中の“１”の数を重みとし、重みを２以上の自然数ｗとすることにより、様々な情報シンボルの生起確率に対応することができる。もちろん、ビットを反転させて、“０”の数を重みと考えて議論しても同様である。
【００３５】
図７は、符号語構成部２２におけるリバーシブル符号の符号語の第２の構成方法を示している。まず、図７の左側に示すように、符号長が短い順に（情報シンボル／２）個だけ、図４の方法によって重み（“１”の数）が一定（この場合は、１個）の２進符号系列を作成する。次に、図７の中央に示すように、この２進符号系列のそれぞれの先頭と末尾に“１”を追加し、さらに図７の右側に示すように、各符号語をビット反転させた符号語を追加する。
【００３６】
この可変長符号では、各符号の最初にあるシンボルの個数をカウントすることによって符号長が分かる。図７の例では、各符号の最初にあるシンボルが４つ出現したら符号が終わる符号構成、つまり符号の区切り（符号長）が分かる符号構成となっている。
【００３７】
この図７の可変長符号は、全ての情報シンボルＡ〜Ｊに対応する符号語が図８（ａ）に示す順方向の復号木の葉にも、図８（ｂ）の逆方向の復号木の葉にも割り当てられることから、順方向にも逆方向にも復号可能であることが分かる。
【００３８】
図９は、符号語構成部２２におけるリバーシブル符号の符号語の第３の構成方法を示している。このリバーシブル符号は、“０”と“１”の数が同じ数になることで、符号語の符号長が分かるような符号構成となっている。すなわち、図９（ａ）に示す格子状の有向グラフを考え、この有向グラフについてｓｔａｒｔ地点から出発して左側の経路を選択した時は“０”、右側の経路を選択した時は “１”をそれぞれ対応させ、ｓｔａｒｔ地点を通る対角線上の黒丸の点に到達する経路を符号語として生成する。
【００３９】
この場合、全ての情報シンボルＡ〜Ｊに対応する符号語が図１０（ａ）に示す順方向の復号木の葉にも、図１０（ｂ）の逆方向の復号木の葉にも割り当てられることから、順方向にも逆方向にも復号可能であることが分かる。
【００４０】
次に、本発明に係るリバーシブル符号の短縮化方法について説明する。情報シンボルの数、つまり可変長符号の符号数は有限であるため、可変長符号の一部の符号を短縮化することが可能である。ここで、短縮化とは他の符号の符号長を増やすことなく、一部の符号の符号長を縮めることをいう。図１１は、リバーシブル符号の短縮化方法の一例を示している。
【００４１】
例えば、図７に示したリバーシブル符号は情報シンボルＧ，Ｈ，Ｉ，Ｊに対応する符号語の末尾の１ビットを削除しても、順方向および逆方向のいずれの方向からも復号可能である。これを利用して、図１１では情報シンボルＧ，Ｈ，Ｉ，Ｊに対応する４つの符号語の符号長を短縮化している。
【００４２】
そして、この図１１に示す可変長符号は、全ての情報シンボルＡ〜Ｊに対応する符号語が図１２（ａ）に示す順方向の復号木の葉にも、図１２（ｂ）の逆方向の復号木の葉にも割り当てられることから、順方向にも逆方向にも復号可能であることが分かる。
【００４３】
次に、図１３を参照して本発明に係るリバーシブル符号の拡張化方法について説明する。リバーシブル符号の拡張化は、各符号の先頭および末尾の少なくとも一方に等長符号を付加して、同一の符号長の符号語数を拡大することで実現することができる。図１３の例では、左側に示すリバーシブル符号のそれぞれの末尾に２ビットの等長符号を付加している。この場合、リバーシブル符号の各符号は全体的に符号長が２ビット増加しているが、同じ符号長の符号語の数は４倍に拡大されている。一般に、ｎビットの等長符号を付加した場合、符号長は全体的にｎビット増加するが、同じ符号長の符号語の数を２n 倍にすることができる。等長符号は、明らかにリバーシブル符号なので、等長符号をリバーシブル符号の先頭や末尾に付加しても、やはりリバーシブル符号である。
【００４４】
図１４は、英語のアルファベットである情報シンボルに対して本発明により可変長符号化を行って得られたリバーシブル符号を公知例（特開平５−３０００２７号公報）に開示されているリバーシブル符号と比較して示したものである。図１４中に示される本発明に基づくリバーシブル符号は、図５で示した方法において符号語の重みを０とした時の符号を末尾に２ビットの等長符号を付加することによって拡張化した符号である。
【００４５】
この本発明に基づくリバーシブル符号は、順方向のみ復号可能な可変長符号の最適符号であるハフマン符号には劣るものの、公知例に開示されたリバーシブル符号と比較して平均符号長が短く、優れた性能を持っていることが分かる。これは、公知例のリバーシブル符号は順方向にのみ復号可能な可変長符号であるハフマン符号の末尾にビットを付加したものであるのに対して、本発明では余分なビットを付加することなく、初めからリバーシブル符号を構成するので、無駄なビットパターンが少ないことによる。
【００４６】
次に、本発明の他の実施形態を説明する。
図１５は、本発明の他の実施形態に係る可変長符号化／復号化装置の構成を示すブロック図である。本実施形態の可変長符号化／復号化装置は、大きく分けて符号語テーブル作成部２０１、符号化部２１３、伝送系または蓄積系２０５および復号化部２１４からなる。
【００４７】
これら各部の機能について簡単に説明すると、符号語テーブル作成部２０１は情報シンボルの生起確率に基づき符号語テーブルを作成して、符号化部２１３内の符号語テーブル２０２に送り、さらに作成した符号語テーブルの符号語のパラメータを復号化部２１４内の復号グラフ・復号値テーブル作成部２０８に送る。符号化部２１３は、情報シンボルを可変長符号に符号化し、その可変長符号を符号化データとして伝送系また蓄積系２０５へ出力する。復号化部２１４は、伝送系または蓄積系２０５を介して入力されてきた符号化データを復号して元の情報シンボルを再生する。
【００４８】
次に、本実施形態の各部の詳細な構成と動作を説明する。
【００４９】
符号化部２１３において、入力された情報シンボルは符号化器２０３に入力される。符号語テーブル２０２は、符号語テーブル作成部２０１によって予め作成された情報シンボルと可変長符号の符号語とを対応させて格納している。但し、符号語テーブル２０２には入力され得る情報シンボルの全てに対応する符号語が格納されているわけではなく、比較的出現頻度の高い一部の情報シンボルに対応した符号語のみが格納されているものとする。符号化器２０３は符号語テーブル２０２に格納されている符号語の中から、入力された情報シンボルに対応した符号語を選択して符号化データとして出力する。
【００５０】
一方、符号化部２１３に符号語テーブル２０２に対応する符号語が存在しない情報シンボル、つまり出現頻度の比較的低い情報シンボルが入力されたときは、その情報シンボルに対応した固定長符号を固定長符号符号化部２０４で作成し、さらに符号語テーブル２０２中のエスケープ符号を固定長符号の先頭と末尾に付加して符号語とし、これを符号化データとして出力する。
【００５１】
こうして符号化部２１３内の符号化器２０３から出力された符号化データは、伝送系または蓄積系２０５を通して復号化部２１４に送られる。この際、符号化データには一定周期毎に同期コードが挿入される。
【００５２】
復号化部２１４は、同期コード検出部２０６、バッファ２０７、復号グラフ・復号値テーブル作成部２０８、順方向復号化器２０９、固定長復号化部２１０、逆方向復号化器２１１および復号値判定部２１２からなり、まず伝送系または蓄積系２０５より入力された符号化データから同期コード検出部２０６で同期コードを検出し、同期コードと同期コードの間の符号化データをバッファ２０７に蓄積する。順方向復号化器２０９では、バッファ２０７に蓄積された符号化データの先頭から復号を開始し、逆方向復号化器２１１では、バッファ２０７に蓄積された符号化データの末尾から復号を開始する。復号値判定部２１２では、順方向復号化器２０９によって得られた復号結果（順方向復号値という）と、逆方向復号化器２１１によって得られた復号結果（逆方向復号値という）から復号値を判定し、最終的な復号結果を出力する。
【００５３】
図１６は、図１５中の符号語テーブル作成部２０１において、固定長符号の先頭と末尾にエスケープ符号を付加して符号語を構成する方法を示した図である。図１６（ａ）に示すように、符号語テーブル作成部２０１が作成する符号語は、情報シンボルが“Ａ”以外のときは、“１”の数が３つ出現することで符号の区切りがわかるリバーシブル符号を基本としている。このリバーシブル符号を符号（１）と呼ぶこととする。
【００５４】
一方、図１６（ｂ）に示す符号（２）は、符号（１）の情報シンボル“Ｃ”に対応する符号語“１０１１”を固定長符号の先頭と末尾を示すためのエスケープ符号として、３ビットの固定長符号の先頭と末尾に付加することにより構成された符号語を符号（１）に新たに加えたものとなっている。但し、符号（２）のうち符号（１）に相当するリバーシブル符号の部分は、符号（２）でエスケープ符号として用いた符号語“１０１１”は使用せず、符号（１）により１個少ない情報シンボルＡ〜Ｉに対応した符号語のみを用いている。図１６（ａ）（ｂ）を比較して明らかなように、符号（２）は符号化できる情報シンボルの数が符号（１）の「１０」から「１７」に増えている。
【００５５】
このような符号（２）を復号するためには、図１６（ａ）（ｂ）から分かるように順方向から復号する場合も逆方向から復号する場合も、必ず符号（１）を一度復号することになり、また固定長符号は順方向からも逆方向からも復号可能であるため、符号（１）が順方向からも逆方向からも復号可能ならば、符号（２）も順方向からも逆方向からも復号可能となる。
【００５６】
従来のリバーシブル符号の場合は、入力され得る情報シンボルに対応する符号語を全て符号語テーブルとして符号化部２１３および復号化部２１４において用意しておく必要があった。これに対し、符号（２）によると、固定長符号の部分については、３ビットの２進符号として別途に固定長符号符号化部２０４および固定長符号復号化部２１０として用意できるので、符号語テーブル２０２には符号（１）の符号語だけを格納しておけばよい。したがって、従来のリバーシブル符号と比較して、可変長符号化／復号化装置の記憶量を大幅に削減することが可能となる。
【００５７】
復号グラフ・復号値テーブル作成部２０８は、Ｓｈａｌｋｗｉｊｋのアルゴリズムを基にした復号グラフと、復号値テーブルを作成し、順方向復号化器２０９および逆方向復号化器２１１は、これらの復号グラフおよび復号値テーブルに基づいて復号化を行う。
【００５８】
図１７は、重み一定の２進符号系列の数え上げの方法を示している。重み一定の２進符号系列の数え上げを行うアルゴリズムとしては、J.P.M.Shalkwijk:“An algorithm for source coding”，IEEE Trans.Infrom Theory,vol.IT-18,no.3,pp.395-399,May 1972.がＳｈａｌｋｗｉｊｋのアルゴリズムとしてよく知られている。Ｓｈａｌｋｗｉｊｋのアルゴリズムでは、図１７（ａ）に示すように「パスカルの三角形」を基本とした、ＳＴＡＲＴ地点からＥＮＤ地点に至る格子状の有向グラフを形成する。各節点に数字で示された値は、ＳＴＡＲＴ地点の節点の値を１として、各節点に入ってくる２つの矢の起点にある節点の値の合計値となっている。すなわち、各節点の値はパスカルの三角形によって決定される。
【００５９】
そして、図１７（ａ）の有向グラフについて、入力される情報シンボルに従ってＳＴＡＲＴ地点からＥＮＤ地点までの経路をたどる際に、左側の経路（矢）を選択したときには符号語の“０”、右側の経路（矢）を選択したときには符号語の“１”をそれぞれ対応させることにより、重み２の２進符号系列を生成することができる。ここで、“０”を選択したときに矢の終点にある節点の値から矢の起点にある節点の値を引いた値を合計した値が、その２進符号系列の同一符号長の符号語についての順序値となる。例えば入力される情報シンボルが“０１００１”であれば、３つある“０”に対して節点の値の差分の合計である（１−１）＋（３−２）＋（４−３）＝２が順序値となる。ここで、順次値とは同一符号長の異なる符号語を順序付けるための値である。図１７（ｂ）は、この場合の情報シンボルと順序値との関係を示している。
【００６０】
このＳｈａｌｋｗｉｊｋのアルゴリズムを符号化に適用した例は公知であり、その場合は上記の順序値に相当する値を２進符号に変換することによって符号化を行う。これに対し、本実施形態ではこのアルゴリズムを以下に説明するように復号化に用いる。
【００６１】
すなわち、復号グラフ・復号値テーブル作成部２０８では、上述したＳｈａｌｋｗｉｊｋのアルゴリズムを基にして有向グラフを復号グラフとして作成する。すなわち、この復号グラフはパスカルの三角形によって決まる値を節点の値とし、符号語の“１”および“０”を矢とした有向グラフであり、その一例を図１８（ａ）に示す。図１８（ｂ）は、この復号グラフを用いた順方向復号化器２０８および逆方向復号化器２１１における復号値の計算方法の一例を示している。
【００６２】
図１６（ａ）に示した符号（１）は、先頭が“０”以外のときは“１”が３つ出現した地点で区切りが分かるリバーシブル符号である。この符号（１）のリバーシブル符号の復号値を計算する際には、順方向についてはリバーシブル符号の先頭が“０”ならば復号値を０とし、それ以外のときは先頭と末端の“１”を削除した後、Ｓｈａｌｋｗｉｊｋのアルゴリズムによって順序値を計算する。今、復号しようとしている符号語より符号長の短い符号語の数は、図１８（ａ）におけるＥＮＤ地点の右斜めの節点の値の合計＋１となるので、その値を順序値に足したものが復号値となる。
【００６３】
一方、逆方向については上述の順方向の場合と同様に、まずリバーシブル符号の先頭が“０”ならば復号値を０とし、それ以外のときは先頭と末端の“１”を削除し、さらに残りの部分を反転させた後、Ｓｈａｌｋｗｉｊｋのアルゴリズムで順序値を計算する。そして、この順序値にＥＮＤ地点の右斜め上にある節点の合計＋１を足したものを復号値とする。
【００６４】
図１８（ａ）（ｂ）を参照して具体的に説明すると、例えばリバーシブル符号の復号対象の符号語が“１０１０１”ならば、まず先頭と末端の“１”を削除して“０１０”とする。この“０１０”に対してＳｈａｌｋｗｉｊｋのアルゴリズムで順序値を求めると、２つある“０”に対して、（１−１）＋（３−２）＝１となる。この場合のＥＮＤ地点の斜め右上にある節点の値の合計は１＋２＝３なので、この値＋１（＝４）を順序値（＝１）に加えて、復号値が５として求まることになる。
【００６５】
このような復号グラフを用いて復号化を行うと、記憶量を大きく低減することができる。図１９（ａ）（ｂ）は、従来の復号木を用いる復号化方法と、本実施形態による復号グラフを用いる復号化方法で必要な記憶量の違いを示した図である。両者を節点の数で比較すると、各節点から出る矢の数は共に２つで同じであるが、各節点に入ってくる矢は図１９（ａ）の復号木の場合、必ず１つである。これに対して、図１９（ｂ）の復号グラフの場合は、各節点に２つの矢が入ってくるので、その分だけ同じ符号語で必要とする節点の総数が少なくなる。この例では、図１９（ａ）の復号木が１５個の節点を必要としているのに対し、図１９（ｂ）の復号グラフでは８個の節点で済む。従って、復号グラフを用いる本実施形態の復号化方法は、従来の復号木を用いる方法よりも必要な記憶量が少なくなるという利点がある。
【００６６】
また、本実施形態では図１６（ｂ）に示したエスケープ符号を付加した符号 （２）を復号するために、図２０（ａ）に示す符号（１）の復号値テーブルと、図２０（ｂ）に示す固定長符号の復号値テーブルの２つを用意し、符号（１）の復号値テーブルでエスケープ符号が復号されたときは、固定長符号の復号値テーブルを読みに行く。例えば、符号語が“１０１１００１１０１１”の場合、先頭の“１０１１”、すなわちエスケープ符号が復号されたら、次の３ビット“００１”は固定長符号であると見なして固定長符号復号化部２１０で復号を行う。この場合、“００１”の復号値として１が得られるので、図２０（ａ）の固定長符号の復号値テーブルから、復号結果は情報シンボル“Ｋ”となる。
【００６７】
次に、本発明を動画像符号化／復号化器に適用した一実施形態について説明する。図２１は、上述した可変長符号化／復号化装置が組み込まれた動画像符号化／復号化器の概略的構成を示すブロック図である。
【００６８】
図２１（ａ）に示す動画像符号化器７０９において、情報源符号化器７０２で符号化されたデータは、動画像多重化部７０３で可変長符号化、通信路符号化および多重化等が行われ、さらに伝送バッファ７０４で伝送速度の平滑化がなされた後に、符号化データとして伝送系または蓄積系７０５に送り出される。符号化制御部７０１は、伝送バッファ７０４のバッファ量を考慮して、情報源符号化器７０２および動画像多重化部７０３の制御を行う。
【００６９】
一方、図２１（ｂ）に示す動画像復号化器７１０においては、伝送系または蓄積系７０５からの符号化データが受信バッファ７０６に一旦溜められ、動画像多重化分離部７０７で符号化データの多重化分離、通信路符号復号化および可変長符号復号化が行われた後、情報源復号化器７０８に送られ、最終的に動画像が復号化される。
【００７０】
図２２は、図２１における動画像符号化器７０９および動画像多重化分離部７０７での動画像符号化方式のシンタックスを示している。図２２（ａ）に示すピクチャ階層のうち、上位階層にはマクロブロックのモード情報や動きベクトル情報やＩＮＴＲＡ ＤＣなどのＤＣＴ係数以外の情報を配し、下位階層にはＤＣＴ係数情報を配しており、下位階層部分に本発明によるリバーシブル符号を適用している。
【００７１】
図２３（ａ）（ｂ）は、図２１における動画像多重化部７０３および動画像多重化分離部７０７のより詳しい構成を示すブロック図である。図２３（ａ）に示す動画像多重化部７０３においては、図２１の情報源符号化器７０２からの符号化データのうち、マクロブロックのモード情報や動きベクトル情報やＩＮＴＲＡＤＣなどの、ＤＣＴ係数以外の情報は上位階層として、上位階層可変長符号化器９０１で通常の可変長符号化が行われた後、さらに上位階層通信路符号化器９０２で冗長度は大きいが訂正能力の高い誤り訂正検出符号により通信路符号化され、多重化部９０５に送られる。
【００７２】
一方、情報源符号化器７０２からの符号化データのうち、ＤＣＴ係数は下位階層可変長符号化器９０３でリバーシブル符号に符号化され、さらに下位階層通信路符号化器９０４で冗長度の少ない誤り訂正検出符号により通信路符号化された後、多重化部９０５に送られる。多重化部９０５では、上位階層の符号化データと下位階層の符号化データを多重化し、伝送バッファ７０４に送る。
【００７３】
図２３（ｂ）に示す動画像多重化分離部７０７においては、まず受信バッファ７０６からの符号化データが多重化分離部９０６で上位階層と下位階層に分離される。上位階層の符号化データは上位階層通信路復号化器９０７で復号され、その復号結果は上位階層可変長復号化器９０９に送られる。下位階層の符号化データは下位階層通信路復号化器９０８で復号され、その復号結果は下位階層可変長復号化器９１０に送られる。
【００７４】
下位階層可変長復号化器９１０はリバーシブル符号の復号を行い、復号結果を情報源復号化器７０８および上位階層可変長復号化器９０９に送る。上位階層可変長復号化器９０９は、上位階層の符号化データである可変長符号の復号を行うと共に、下位階層可変長復号化器９１０の復号結果を基に符号化結果の書き換えを行う。
【００７５】
ここで、図２３（ａ）中の下位階層可変長符号化器９０３は図１５中の符号化部２１３に、図２３（ｂ）中の下位階層可変長復号化器９１０は図１５中の復号化部２１４にそれぞれ対応している。
【００７６】
本実施形態の動画像符号化／復号化器に見られるように、符号化方式に図２２に示したようなシンタックスがある場合には、可変長符号そのものを両方向から復号できるのみでなく、シンタックス的にも両方向から復号できるようにする必要がある。本実施形態では、以下に説明する符号語テーブルを用いることによって、この要求を実現している。
【００７７】
図２４〜図２８は、下位階層可変長符号化器９０３で用いるＤＣＴ係数の可変長符号の符号語テーブルの一例を示している。また、図２９はエスケープ符号の符号語テーブルを示している。
【００７８】
情報源符号化器７０２では、量子化後の８×８のＤＣＴ係数のブロックについてはブロック内のスキャンを行って、ＬＡＳＴ（０：ブロックの最後でない非零係数、１：ブロックの最後の非零係数）、ＲＵＮ（非零係数までの零ランの数）およびＬＥＶＥＬ（係数の絶対値）を求め、動画像符号化器７０９に送る。
【００７９】
動画像符号化器７０９内の下位階層可変長符号化器９０３は、図２４〜図２５に示すＩＮＴＲＡおよびＩＮＴＥＲの非ＬＡＳＴ係数、ＲＵＮ、ＬＥＶＥＬにリバーシブル符号（ＶＬＣ＿ＣＯＤＥ）を対応させた非ＬＡＳＴ係数の符号語テーブル（第１の符号語テーブル）と、図２６〜図２７に示すＩＮＴＲＡおよびＩＮＴＥＲのＬＡＳＴ係数、ＲＵＮ、ＬＥＶＥＬにリバーシブル符号（ＶＬＣ＿ＣＯＤＥ）を対応させたＬＡＳＴ係数の符号語テーブル（第２の符号語テーブル）を持っている。そして、モード情報に基づいてＩＮＴＲＡのときはＩＮＴＲＡの非ＬＡＳＴ係数とＬＡＳＴ係数の符号語テーブル、ＩＮＴＥＲのときはＩＮＴＥＲの非ＬＡＳＴ係数とＬＡＳＴ係数の符号語テーブルをそれぞれ選択して符号化を行う。なお、図２６〜図２７においてＶＬＣ＿ＣＯＤＥの最終ビットの“Ｓ”はＬＥＶＥＬの符号を表し、“Ｓ”が“０”のときＬＥＶＥＬの符号は正、“１”のとき負である。
【００８０】
また、この符号語テーブルに存在しない係数は、図２９に示すようにＲＵＮとＬＥＶＥＬの絶対値を固定長符号に符号化し、この固定長符号の先頭と末端にエスケープ符号を付加し、エスケープ符号の最終ビットでＬＡＳＴ係数とＬＥＶＥＬの正負を区別できるように符号化する。図２８は、このエスケープ符号の符号語テーブルであり、エスケープ符号として用いられているＶＬＣ＿ＣＯＤＥの最終ビットの“ｔ”は、固定長符号の先頭に付加されたときはＬＡＳＴ係数か否かを表し、これが“０”のときは非ＬＡＳＴ係数、“１”のときはＬＡＳＴ係数である。また、“ｔ”は固定長符号の末尾に付加されたときはＬＥＶＥＬの符号を表し、これが“０”のときＬＥＶＥＬの符号は正、“１”のときは負である。
【００８１】
図３０は、本実施形態における符号化データの例を示している。同図に示されるように、下位階層において順方向から復号を行うときは、８×８画素のＤＣＴ係数のブロックの末尾に必ずＬＡＳＴ係数の符号が存在するため、ブロックの末尾を判定することができる。一方、逆方向から復号を行うときは、１つアドレスが前のブロックのＬＡＳＴ係数の符号が出現することにより、ブロックの先頭を判定できる。この符号は、ＬＡＳＴ係数がＩＮＴＲＡモードとＩＮＴＥＲモードで共通化されているため、マククロブロック毎にモードが存在していてもブロックの先頭を判定することができる。
【００８２】
下位階層の最初のブロックについては、予め下位階層可変長符号化器９０３で下位階層の先頭にダミーのＬＡＳＴ係数を符号化しておくか、あるいは、下位階層可変長復号化器９１０で、次のフレームの同期符号までのビット数から予め下位階層のビット数を計算しておき、これを復号したビット数と比較するか、あるいは、下位階層可変長復号化器９１０内のバッファで下位階層の先頭にダミーのＬＡＳＴ係数を挿入する方法をとることにより、逆方向に復号したときに下位階層の先頭を判定することができる。
【００８３】
図２４〜図２７に示した符号語テーブルに格納されたリバーシブル符号は、順方向の場合、先頭の１ビットが“０”ならば、“０”が２つ出現するまで読み、“１”ならば、“１”が２つ出現するまで読み、その次の１ビットがＬＥＶＥＬの正負を表す最終ビットとなることが分かる。逆方向の場合は、最初の１ビットがＬＥＶＥＬの正負を表しており、次の１ビットが“０”ならば、“０”が２つ出現するまで読み、“１”ならば、“１”が２つ出現するまで読めばよい。
【００８４】
図３１は、本実施形態における下位階層可変長符号化器９０３で用いるＤＣＴ係数の可変長符号に適用したリバーシブル符号を復号するための復号グラフを示している。順方向からみて符号語の先頭ビットと末尾の２ビットを除いた符号化データについて、この復号グラフによって復号値を計算することができる。
【００８５】
この復号グラフは、先頭のビットが“０”ならば、“０”が現れれば右の矢を進み、“１”が現れれば左の矢を進むこととする。先頭のビットが“１”ならば、“１”が現れれば右の矢を進み、“０”が現れれば左の矢を進むこととする。
【００８６】
同一の符号長の２進符号系列についての順序値を求めるには、先に説明したＳｈａｌｋｗｉｊｋのアルゴリズムに従って、左側の矢を選択したときに矢の終点の節点の値から起点の節点の値を引いた値の合計値をその符号長での順序値とすればよい。
【００８７】
一方、復号値を求めるには、先頭のビットが“０”ならば、終端の節点の右斜め上の節点の値の合計値の２倍を順序値に足した値を復号値とすればよい。先頭ビットが“１”ならば、終端の節点の右斜め上の節点の値の合計値の２倍＋終端の節点の値に順序値を足した値を復号値とればよい。
【００８８】
例えば、復号対象の符号列が“０１１０１０１”ならば、まず順方向からみて先頭の１ビットと末尾の２ビットを除いて、“１１０１”とする。先頭ビットが“０”なので、復号グラフで“０”が現れれば右の矢を進み、“１”が現れれば左の印を進むことになる。この場合、左の矢を進んだときの節点の差分は（１−１）＋（１−１）＋（４−３）＝１なので、順序値は１である。最上位ビットが“０”なので、終端の節点の右斜め上にある節点の合計の２倍（１＋２＋３）×２＝１２に順序１を加えると１３となり、この符号語の復号値は１３として求められることになる。
【００８９】
図３２〜図３４は、下位階層可変長復号化器９１０で用いる復号値テーブルの一例であり、図３２〜図３３はＩＮＴＲＡおよびＩＮＴＥＲの非ＬＡＳＴ係数、ＲＵＮ、ＬＥＶＥＬに復号値を対応させた非ＬＡＳＴ係数の復号値テーブルであり、図３４（ａ）（ｂ）はＩＮＴＲＡおよびＩＮＴＥＲのＬＡＳＴ係数、ＲＵＮ、ＬＥＶＥＬに復号値を対応させたＬＡＳＴ係数の復号値テーブルである。また、図３４（ｃ）はエスケープ符号の復号値テーブルである。
【００９０】
この例では、例えば復号値１３は図３４（ａ）で分かるように、ＬＡＳＴ係数で、ＲＵＮ数は３、ＬＥＶＥＬの絶対値が１であることが分かり、また最下位ビットが“１”であることから、ＬＥＶＥＬは負であることが分かる。さらに、図３４（ｃ）で分かるように、復号値４１が復号された場合は、エスケープ符号が復号されたと判定する。このエスケープ符号の最後のビットでＬＡＳＴ係数か非ＬＡＳＴ係数かの判定を行い、その後の１３ビットについて固定長符号復号化部２１０でＲＵＮとＬＥＶＥＬの絶対値を復号した後、再びエスケープ符号を復号し、最後のビットでＬＥＶＥＬの正負を決定する。
【００９１】
一例として、符号化対象の符号列が“１１０００００１００００１１１０００１０１１１１００００１０”の場合を考える。この場合、先頭のエスケープ符号“１１００００１０”の最終ビットが“０”なので、非ＬＡＳＴ係数であり、その後の１３ビットの固定長符号を計算する。この１３ビットのうち上位６ビットがＲＵＮを表すので、“０００１１１”でＲＵＮは７、下位７ビットがＬＥＶＥＬの絶対値を表すので、“０００１０１１”でＬＥＶＥＬの絶対値は１２、末尾のエスケープ符号“１１００００１０”の最終ビットが“０”なのでＬＥＶＥＬは正、というように復号を行うことができる。
【００９２】
復号値判定部２１２では、このようにして順方向復号化器２０９によって得られた復号結果（順方向復号結果という）と、逆方向復号化器２１１によって得られた復号結果（逆方向復号値という）から復号値を判定し、最終的な復号結果を出力する。すなわち、復号値判定部２１２では符号化データに誤りがあると、下位階層通信路復号化器９０８の復号結果、あるいは、符号語として存在しなかったビットパターンが生じることから、誤りの存在が分かるので、これらの順方向復号結果と逆方向復号結果から、図３６に示すようにして復号値を判定する。なお、図３６は下位階層の復号値判定方法を示している。
【００９３】
まず、図３６（ａ）に示すように順方向復号結果と逆方向復号結果で誤りが検出されるマクロブロックの位置（誤り検出位置）が交差しない場合は、誤りが検出されなかったマクロブロックの復号結果のみを復号値として使用し、二つの誤り検出位置の復号結果は復号値として使用しない。そして、上位階層のモード情報の復号結果に基づいて、ＩＮＴＲＡマクロブロックについては前フレームをそのまま表示するように、ＩＮＴＥＲマクロブロックについては前フレームより動き補償のみで表示するように、上位階層の復号結果を書き換える。
【００９４】
また、図３６（ｂ）に示すように順方向復号結果と逆方向復号結果で誤りが検出位置が交差する場合は、両方で誤りが検出されなかった復号結果を復号結果値として使用する。また、この場合には二つの誤り検出位置の符号語の間の復号結果は復号値として使用せず、上位階層のモード情報の復号結果に基づいて、ＩＮＴＲＡマクロブロックについては前フレームをそのまま表示するように、ＩＮＴＥＲマクロブロックについては前フレームより動き補償のみで表示するように、上位階層の復号結果を書き換える。
【００９５】
また、図３６（ｃ）に示すように順方向復号結果および逆方向復号結果のうち、片方向の復号結果にしか誤りが検出されない場合（この例では、順方向復号結果のみ誤りが検出されている）は、誤り検出位置のマクロブロックは復号値として使用せず、上位階層のモード情報の復号結果に基づいて、ＩＮＴＲＡマクロブロックについては前フレームをそのまま表示するように、ＩＮＴＥＲマクロブロックについては前フレームより動き補償のみで表示するように、上位階層の復号結果を書き換える。それ以後のマクロブロックに対する復号値は、逆方向の復号結果を使用する。
【００９６】
さらに、図３６（ｄ）に示すように同一のマクロブロックで順方向復号結果および逆方向復号結果の両方に誤りが検出される場合は、誤り検出位置のマクロブロックの復号値は放棄して復号値として使用せず、上位階層のモード情報の復号結果に基づいて、ＩＮＴＲＡマクロブロックについては前フレームをそのまま表示するように、ＩＮＴＥＲマクロブロックについては前フレームより動き補償のみで表示するように、上位階層の復号結果を書き換え、それ以後のマクロブロックに対する復号値は逆方向の復号結果を使用する。
【００９７】
マクロブロックの符号化／復号化の順序については、上記実施形態以外の方法でもよく、例えば誤りがあったときに、復号画像のうちより重要な画面中央部が救済されるように、図３７に示すような順序とする方法でもよい。すなわち、両方向から復号することを前提とすると、同期符号と同期符号の間の符号化データのうち、最初の方の部分と最後の方の部分が正しく復号される確率が高いので、これの部分が中央部にくるように順序を決めるのである。
【００９８】
なお、上記実施形態ではＤＣＴ係数の可変長符号化に本発明を適用したが、他の情報シンボルについても同様の可変長符号化を適用できることは、言うまでもない。
【００９９】
また、上記実施形態では２元符号のみの議論を示したが、多元符号にも拡張することが容易であり、同様な効果を得ることができる。
【０１００】
最後に、本発明の応用例として、本発明による可変長符号化／復号化装置を適用した画像送受信装置の実施形態を図３８を用いて説明する。パーソナルコンピュータ（ＰＣ）１００１に備えら付けられたカメラ１００２より入力された画像信号は、ＰＣ１００１に組み込まれた可変長符号化装置によって符号化される。この場合の情報シンボルは、これに限るものではないが、例えば入力画像信号または入力画像信号と予測画像信号との差である予測誤差信号をＤＣＴ回路によって離散コサイン変換し、さらに量子化回路により量子化して得られたＤＣＴ係数データなどである。可変長符号化装置から出力される符号化データは、他の音声やデータの情報と多重化された後、無線機１００３により無線で送信され、他の無線機１００４によって受信される。無線機１００４で受信された信号は、画像信号の符号化データおよび音声やデータの情報に分解される。これらのうち、画像信号の符号化データはワークステーション（ＥＷＳ）１００５に組み込まれた可変長符号復号化装置によって復号され、ＥＷＳ１００５のディスプレイに表示される。
【０１０１】
一方、ＥＷＳ１００５に備え付けられたカメラ１００６より入力された画像信号は、ＥＷＳ１００６に組み込まれた可変長符号化装置を用いて上記と同様に符号化される。符号化データは、他の音声やデータの情報と多重化され、無線機１００４により無線で送信され、無線機１００３によって受信される。無線機１００３によって受信された信号は、画像信号の符号化データおよび音声やデータの情報に分解される。これらのうち、画像信号の符号化データはＰＣ１００１に組み込まれた可変長符号復号化装置によって復号され、ＰＣ１００１のディスプレイに表示される。
【０１０２】
本発明の可変長符号化／復号化装置は、情報シンボルの出現頻度に応じた符号長を有し、従来と比較して無駄なビットパターンが少なくて効率がよく、しかも順方向にも逆方向にも復号が可能なリバーシブルの可変長符号を構成することができるので、図３８に示した無線伝送路のような誤りが多い伝送路を用いた送受信装置において特に有効である。
【０１０３】
以上実施形態で説明したように、本発明の可変長符号化／復号化装置は、従来と比較して、少ない記憶量で復号することができ、従来適用することのできなかったような情報シンボル数が大きな符号化に対しても適用することができる。具体的には、動画像符号化／復号化装置にも適用することが可能であり、誤りに強い動画像符号化／復号化装置を提供することができる。
【０１０４】
【発明の効果】
以上説明したように、本発明によれば順方向にも逆方向にも復号可能で、しかも符号化効率や装置に必要な記憶量などの点で実用性に富んだ可変長符号化方法及び装置を提供することができる。
【図面の簡単な説明】
【図１】本発明の一実施形態に係る可変長符号化／復号化装置の構成を示すブロック図
【図２】図１における復号値判定部の動作を説明するための図
【図３】図１における符号語テーブル作成部のブロック図
【図４】本発明に係る可変長符号の基となる重み一定の２進符号系列の作成方法を示す図
【図５】図３における符号語構成部での第１の符号語構成方法を示す図
【図６】第１の符号構成方法で構成した符号語から作成した順方向および逆方向の復号木を示す図
【図７】図３における符号語構成部での第２の符号語構成方法を示す図
【図８】第２の符号構成方法で構成した符号語から作成した順方向および逆方向の復号木を示す図
【図９】図３における符号語構成部での第３の符号構成方法を示す図
【図１０】第３の符号構成方法で構成した符号語から作成した順方向および逆方向の復号木を示す図
【図１１】図３における符号語構成部での符号短縮化方法を示す図
【図１２】符号短縮化方法で短縮化した符号語から作成した順方向および逆方向の復号木を示す図
【図１３】図３における符号語構成部での符号拡大化方法を示す図
【図１４】本実施形態で構成された可変長符号と公知例の可変長符号の特性を比較して示す図
【図１５】本発明の他の実施形態に係る可変長符号化／復号化装置の構成を示すブロック図
【図１６】図１５における符号語構成部での符号構成方法を示す図
【図１７】重み一定の２進系列を数え上げる方法を示す図
【図１８】図１５における順方向復号化器および逆方向復号化器の動作を示す図
【図１９】従来の復号木と本実施形態における復号グラフを比較して示す図
【図２０】本実施形態における復号値テーブルを説明するための図
【図２１】本発明による可変長符号化／復号化装置が組み込まれた動画像符号化／復号化器の概略構成を示すブロック図
【図２２】同実施形態に係る動画像符号化／復号化器における符号化データのシンタックスを示す図
【図２３】図２１における動画像多重化部および動画像多重化分離部の構成を示すブロック図
【図２４】同実施形態におけるＩＮＴＲＡおよびＩＮＴＥＲの非ＬＡＳＴ係数の符号語テーブルの一部を示す図
【図２５】同実施形態におけるＩＮＴＲＡおよびＩＮＴＥＲの非ＬＡＳＴ係数の符号語テーブルの他の一部を示す図
【図２６】同実施形態におけるＩＮＴＲＡおよびＩＮＴＥＲのＬＡＳＴ係数の符号語テーブルの一部を示す図
【図２７】同実施形態におけるＩＮＴＲＡおよびＩＮＴＥＲのＬＡＳＴ係数の符号語テーブルの他の一部を示す図
【図２８】同実施形態におけるエスケープ符号の符号語テーブルを示す図
【図２９】同実施形態における符号語テーブルにない符号語の符号化方法を示す図
【図３０】同実施形態における符号化データの例を示す図
【図３１】同実施形態における復号グラフを示す図
【図３２】同実施形態におけるＩＮＴＲＡおよびＩＮＴＥＲの非ＬＡＳＴ係数の復号値テーブルの一部を示す図
【図３３】同実施形態におけるＩＮＴＲＡおよびＩＮＴＥＲの非ＬＡＳＴ係数の復号値テーブルの他の一部を示す図
【図３４】同実施形態におけるＩＮＴＲＡおよびＩＮＴＥＲのＬＡＳＴ係数の復号値テーブルを示す図
【図３５】同実施形態におけるエスケープ符号の復号値テーブルを示す図
【図３６】図１５における復号値判定部の動作を説明するための図
【図３７】同実施形態におけるマクロブロックの符号化／復号化順序を示す図
【図３８】本発明による可変長符号化／復号化装置が組み込まれる装置の一例を示す図
【図３９】リバーシブル符号の一般的な復号方法を示す図
【図４０】通常の可変長符号の説明図
【図４１】従来のリバーシブル符号の説明図
【符号の説明】
１０１…符号語テーブル作成部
１０２…符号語テーブル
１０３…符号化器
１０４…伝送系または蓄積系
１０５…同期コード検出部
１０６…バッファ
１０７…順方向復号化器
１０８…逆方向復号化器
１０９…復号値判定部
１１０…順方向復号語テーブル
１１１…順方向復号木作成部
１１２…逆方向符号語テーブル
１１３…逆方向復号木作成部
１１４…符号化部
１１５…復号化部
２１…符号選択部
２２…符号語構成部
２０１…符号語テーブル作成部
２０２…符号語テーブル
２０３…符号化器
２０４…固定長符号符号化部
２０５…伝送系または蓄積系
２０６…同期コード検出部
２０７…バッファ
２０８…復号グラフ・復号値テーブル作成部
２０９…順方向復号化器
２２０…固定長符号復号化部
２１１…逆方向復号化器
２１２…復号値判定部
２１３…符号化部
２１４…復号化部
７０１…符号化制御部
７０２…情報源符号化器
７０３…動画像多重化部
７０４…伝送バッファ
７０５…伝送系または蓄積系
７０６…受信バッファ
７０７…動画像多重化分離部
７０８…情報源復号化器
７０９…動画像符号化器
７１０…動画像復号化器
９０１…下位階層可変長復号化器
９０２…上位階層通信路符号化器
９０３…下位階層可変長符号化器
９０４…下位階層通信路符号化器
９０５…多重化部
９０６…多重化分離部
９０７…上位階層通信路復号化器
９０８…下位階層通信路復号化器
９０９…上位階層可変長復号化器
９１０…下位階層可変長復号化器
１００１…パーソナルコンピュータ
１００２…ワークステーション
１００３…無線機
１００４…無線機
１００５…カメラ
１００６…カメラ
【発明の属する技術分野】
この発明は、可変長符号化方法及び装置に関する。
【０００２】
【従来の技術】
可変長符号は、シンボルの発生頻度に基づいて、頻繁に出現するシンボルは短い符号長の符号、希にしか出現しないシンボルは長い符号長の符号を割り当てることにより、平均的に短い符号長となるようにした符号系である。従って、可変長符号を用いると、符号化前のデータと比較して、データ量を大幅に圧縮することができる。このような可変長符号の構成方法としては、無記憶情報源で最適なハフマンのアルゴリズムが知られている。
【０００３】
可変長符号の一般的な問題として、符号化データに伝送路誤りその他の理由で誤りが混入した場合に、誤りが混入した以後のデータについては、その影響が伝搬することにより復号化装置で正しく復号することができなくなってしまうという点が挙げられる。そのため、伝送路において誤りが生じる可能性がある場合には、ある間隔で周期的に同期符号を挿入し、誤りの伝搬を防止する方法がとられるのが一般的である。同期符号には、可変長符号の組み合わせでは出現しないようなビットパターンが割り当てられる。この方法によれば、符号化データに誤りが生じ、復号できなくなったとしても、次の同期符号を見つけることにより、誤りの伝搬を防止し、正しく復号を行うことができる。しかし、このように同期符号を用いた場合でも、図３９（ａ）に示すように誤りが生じて正しく復号できない地点から、次の同期符号が見つかる地点までの間の符号化データについては、復号を行うことができない。
【０００４】
そこで、可変長符号を図４０に示す通常の構成から図４１に示すように変更して、図３９（ｂ）に示すように通常の順方向から復号可能な性質だけでなく、逆方向からも復号可能な符号の構成にする方法が知られている。また、このような符号は符号化データを逆方向からも読めることから、符号化データを蓄積するディスクメモリなどの蓄積媒体において逆転再生に用いることもできる。このような順方向のみならず逆方向からも復号可能な可変長符号のことを、ここではリバーシブル符号と呼ぶこととする。リバーシブル符号の一例は、例えば特開平５−３０００２７号公報「可逆可変長符号化方式」に記載されている。この公知例のリバーシブル符号は、図４０に示した順方向から復号可能な可変長符号であるハフマン符号の符号語の末尾に、図４１に示すようにそれぞれの符号語がそれより符号長の長い他の符号語の末尾と一致しない条件でビットを追加することによって、逆方向からも復号可能とした可変長符号である。
【０００５】
しかし、このリバーシブル符号は順方向からのみ復号可能な可変長符号の符号語の末尾にビットを付加するために、無駄なビットが多くなって平均符号長が長くなる。この結果、順方向からのみ復号可能な可変長符号と比較して符号化効率が大きく低下してしまう。
【０００６】
また、従来のリバーシブル符号のもう一つの問題点として、情報シンボル数が大きい場合には、可変長符号化／復号化装置で必要とされる記憶量が多くなるために、実用に適さないという点があった。情報シンボル数が大きい場合の例としては、動画像や静止画像の画像符号化でよく用いられるＤＣＴ係数の符号化がある。通常、画像符号化では８×８のＤＣＴ（離散コサイン変換）を行い、これにより得られたＤＣＴ係数と呼ばれる直交変換係数について８ビットの線形量子化を行う。さらに、量子化されたＤＣＴ変換係数について低域からジグザクスキャンを行い、零ランと非零の係数を組にして可変長符号化を行っている。
【０００７】
例えば、ＩＴＵ−Ｔ ＤＲＡＦＴ Ｒｅｃｏｍｍｅｎｄａｔｉｏｎ Ｈ．２６３（１９９５）では、量子化インデックス値は−１２７〜＋１２７（インデックス値０はランなので、インデックス数は２５３）、零ラン数は最大６３であり、またブロックの最後のＤＣＴ係数が非零の係数かどうかの区別をするような符号化を採用しているので、情報シンボル数は２５３×６４×２＝３２３８４と非常に大きな数になっている。そこで、Ｈ．２６３では出現確率の高いＤＣＴ係数については可変長符号で符号化するが、出現確率の低いＤＣＴ係数についてはブロックの最後の非零係数かどうかの区別を示す符号に１ビットの符号、零ランに６ビットの符号、量子化インデックスに８ビットの符号の計１５ビットの符号で固定長符号化を行い、この固定長符号の先頭にエスケープ符号と呼ばれる符号を付加する構成となっている。
【０００８】
全ての符号語を符号語テーブルとして持っていても符号化／復号化は可能であるが、上記のような符号構成になっていると、１５ビットの固定長符号の部分は可変長符号とは別個に符号化／復号化が可能であるため、出現確率の高いＤＣＴ係数とエスケープ符号の符号語テーブルを用意するだけでよい。従って、可変長符号の符号語テーブルを削減して記憶容量を低減することが可能となる。
【０００９】
しかし、従来のリバーシブル符号は前述したように順方向からのみ復号可能な可変長符号の符号語の末尾にビットを付加する必要があるために、エスケープ符号を付加することができない。従って、情報シンボル数が多い場合にも全ての情報シンボルに対応した符号語を用意する必要があり、記憶量が莫大なものとなってしまう。
【００１０】
【発明が解決しようとする課題】
上述したように、従来技術によるリバーシブル符号、すなわち順方向からも逆方向からも復号可能な可変長符号は、順方向からのみ復号可能な可変長符号の符号語の末尾にビットを付加することによってリバーシブル符号を構成するため、無駄なビットパターンが多くなって平均符号長が長くなり、順方向からのみ復号可能な可変長符号と比較して符号化効率の低下が著しくなるという問題があり、またこのようなリバーシブル符号を用いる可変長符号化／復号化装置では、何らかの形で全ての情報シンボルに対応した符号語を有する符号語テーブルを用意する必要があり、画像符号化のように情報シンボルの数が大きい場合、大きな記憶量を必要とするという問題があるため、いずれにしても実用に適さないという問題があった。
【００１１】
本発明は、順方向にも逆方向にも復号可能であって、実用性に富んだ可変長符号化方法及び装置を提供することを目的とする。
【００１２】
より具体的には、順方向にも逆方向にも復号可能であって、しかも情報シンボルの数が多い場合にも大きな記憶量を必要としない可変長符号化方法及び装置を提供することを目的とする。
【００１３】
【課題を解決するための手段】
上記の課題を解決するため、本発明では複数の情報シンボルに対して該情報シンボルの生起確率に応じた符号長を有する符号語をそれぞれ割り当て、入力された情報シンボルに対応した符号語を符号化データとして出力する可変長符号化において、入力された情報シンボルに対応して、順方向にも逆方向にも復号可能な複数の可変長符号のいずれかと、長さが等しい複数の等長符号のいずれかとの組み合わせからなる符号語を符号化データとして出力することを特徴とする。
【００１４】
言い換えれば、入力された情報シンボルに対応して、順方向にも逆方向にも復号可能な複数の可変長符号の先頭および末尾の少なくとも一方に、長さが等しい複数の等長符号のいずれかを付加して組み合わせ、該組み合わせ後の符号語を符号化データとして出力することを特徴とする。
【００１５】
さらには、入力された情報シンボルに対応して、順方向にも逆方向にも復号可能な複数の可変長符号の先頭および末尾の少なくとも一方に、組み合わせ後の符号語が順方向にも逆方向にも復号可能となるように長さが等しい複数の等長符号のいずれかを付加して組み合わせ、該組み合わせ後の符号語を符号化データとして出力することを特徴とする。
【００１６】
【発明の実施の形態】
以下、図面を参照して本発明の実施形態を説明する。
【００１７】
図１は、本発明の一実施形態に係る可変長符号化／復号化装置の構成を示すブロック図である。本実施形態の可変長符号化／復号化装置は、大きく分けて符号語テーブル作成部１０１、符号化部１１４、伝送系または蓄積系１０４および復号化部１１５からなる。まず、これら各部の機能について簡単に説明すると、符号語テーブル作成部１０１は情報シンボルの生起確率に基づいて符号語テーブルを作成し、符号化部１１４内の符号化テーブル１０２と、復号化部１１５内の順方向符号語テーブル１１０および逆方向符号語テーブル１１２に送る。符号化部１１４は、情報シンボルを可変長符号に符号化し、その可変長符号を符号化データとして伝送系または蓄積系１０４へ出力する。復号化部１１５は、伝送系または蓄積系１０４を介して入力されてきた符号化データを復号して元の情報シンボルを再生する。
【００１８】
次に、本実施形態の各部の詳細な構成と動作を説明する。符号化部１１４において、入力された情報シンボルは符号化器１０３に入力される。一方、符号語テーブル１０２は、符号語テーブル作成部１０１によって予め作成された情報シンボルと可変長符号の符号語とを対応させて格納している。符号化器１０３は符号語テーブル１０２に格納されている符号語の中から、入力された情報シンボルに対応した符号語を選択して符号化データとして出力する。この符号化データは、伝送系または蓄積系１０４を通して復号化部１１５に送られる。この際、符号化データには一定周期毎に同期コードが挿入される。
【００１９】
復号化部１１５では、伝送系または蓄積系１０４より入力された符号化データから同期コード検出部１０５で同期コードを検出し、同期コードと同期コードの間の符号化データをバッファ１０６に蓄積する。順方向復号化器１１０では、順方向復号木作成部１１１からの順方向復号木に基づいて、バッファ１０６に蓄積された符号化データの先頭から復号を開始し、逆方向復号化器１０８では、逆方向復号木作成部１１３からの逆方向復号木に基づいて、バッファ１０６に蓄積された符号化データの末尾から復号を開始する。
【００２０】
復号値判定部１０９では、順方向復号化器１０７によって得られた復号結果（順方向復号結果という）と、逆方向復号化器１０８によって得られた復号結果（逆方向復号結果という）から復号値を判定し、最終的な復号結果を出力する。すなわち、復号値判定部１０９では符号化データに誤りがあると、復号木に出現しないビットパターンが生じることから誤りの存在が分かるので、順方向復号結果と逆方向復号結果から図２に示すように復号値を判定する。図２は、同期コードと同期コードとの間の復号値判定方法を示している。
【００２１】
まず、図２（ａ）に示すように順方向復号結果と逆方向復号結果で誤りが検出される符号語の位置（誤り検出位置）が交差しない場合は、誤りが検出されなかった復号結果のみを復号値として使用し、二つの誤り検出位置の復号結果は復号値として使用せず、放棄する。
【００２２】
また、図２（ｂ）に示すように順方向復号結果と逆方向復号結果の誤り検出位置が交差する場合は、両方で誤りが検出されなかった復号結果を復号結果値として使用する。また、この場合には二つの誤り検出位置の符号語の間の復号結果は復号値として使用せず、放棄する。
【００２３】
また、図２（ｃ）に示すように順方向復号結果および逆方向復号結果のうち片方向の復号結果にしか誤りが検出されない場合（この例では、順方向復号結果にのみ誤りが検出されている）は、誤り検出位置の符号語に対する復号値を放棄し、それ以後の符号語に対する復号値は逆方向の復号結果を使用する。
【００２４】
さらに、図２（ｄ）に示すように同一の符号語について順方向復号結果および逆方向復号結果の両方に誤りが検出される場合は、図２（ｃ）と同様に誤り検出位置の符号語に対する復号値は放棄し、それ以後の符号語に対する復号値としては逆方向の復号結果を使用する。
【００２５】
符号語テーブル作成部１０１では、情報シンボルの生起確率に基づいて順方向にも逆方向にも復号可能な符号の符号語テーブルを作成する。符号語テーブル作成部１０１によって作成された符号語テーブルは、符号化部１１４内の符号語テーブル１０２と、復号化部１１５内の順方向符号語テーブル１１０および逆方向符号語テーブル１１２に送られる。順方向復号木作成部１１１では、順方向符号語テーブル１１０から順方向復号木を作成する。また、逆方向復号木作成部１１３では、逆方向符号語テーブル１１２から逆方向復号木を作成する。
【００２６】
図３は、符号語テーブル作成部１０１の構成を示すブロック図である。符号選択部２１は、情報シンボルの生起確率の情報を入力として、この情報に基づいて選択可能な符号系の中から最も平均符号長の小さいものを選択し、選択結果を符号語構成部２２に送る。符号語構成部２２では、符号語選択部２１で選択された符号の符号語を構成して、符号語テーブルを作成する。符号語構成部２２で作成された符号語テーブルは、符号化部１１４内の符号語テーブル１０２および復号化部１１５内の順方向符号語テーブル１１０に送られる。復号化部１１５内の逆方向符号語テーブル１１２には、順方向とは逆向きに記述された符号語テーブルが送られる。
【００２７】
符号選択部２１では、入力された情報シンボルを生起確率が大きい順に並べ替えてＳ＝｛Ｓ1 ，Ｓ2 ，…，Ｓn ｝とし、これらの情報シンボルＳの生起確率Ｐ＝｛ｐ1 ，ｐ2 ，…，ｐn ｝に基づいて、構成可能な符号の集合Ｃの中から、
【００２８】
【数１】
を満足する符号ｃを選択する。ここで、Ｌｉは符号語構成部２２より与えられる符号語の重みによって計算することができる符号長である。この場合の符号語の重みとは、符号語における“１”または“０”の数をいう。
【００３０】
以下、符号語構成部２２における符号語の構成方法について述べる。
【００３１】
図４は、本実施形態による可変長符号の基となる重みが一定の２進符号系列の作り方の例を示している。図４（ａ）に示すように、ｓｔａｒｔ地点からｅｎｄ地点に至る格子状の有向グラフを形成する。この有向グラフについてｓｔａｒｔ地点からｅｎｄ地点までの経路をたどる際、左側の経路を選択した時は“０”、右側の経路を選択した時は“１”をそれぞれ対応させることにより、図４（ｂ）に示す２進符号系列を生成する。この例では、符号長が５ビットで、重み（“１”の数）が２の２進符号系列を生成している。一般に、符号長がｎビットで重みがｗの２進符号系列は、ｎ個からｗ個を選択する組み合わせの数だけ存在する。ここでは、５個から２個を選択する組み合わせの数＝１０個の２進符号系列が存在することになる。
【００３２】
図５は、符号語構成部２２における順方向にも逆方向にも復号可能な可変長符号（以下、リバーシブル符号という）の符号語の第１の構成方法を示している。まず、図５の左側に示すように、符号長が短い順に（情報シンボル−１）個（この場合は、９個）だけ、図４の方法によって重み（“１”の数）が一定（この場合は、１個）の２進符号系列を作成する。次に、図５の右側に示すように、この２進符号系列のそれぞれの先頭と末尾に“１”を追加し、最も短い符号には０”を割り当てることによって、リバーシブル符号の符号語を構成する。このリバーシブル符号は、情報シンボルＡに対しては符号“０”、それ以外の情報シンボルＢ〜Ｊに対しては符号が“１”から必ず始まり、“１”が全部で３個出現したら符号が終わる符号構成、つまり符号の区切り（符号長）が分かる構成となっている。
【００３３】
可変長符号がリバーシブル符号、すなわち順方向にも逆方向にも復号可能な符号であるための必要十分条件は、全ての符号語が順方向の復号木の葉と逆方向の復号木の葉に割り当てられることである。復号木の葉とは、復号木の末端、つまりそれより先には何も無い個所をいう。例えば、図５の可変長符号は、全ての情報シンボルＡ〜Ｊに対応する符号語が図６（ａ）に示す順方向の復号木の葉にも、図６（ｂ）の逆方向の復号木の葉にも割り当てられることから、順方向にも逆方向にも復号可能であることが分かる。
【００３４】
図５の可変長符号の符号語構成方法のパラメータは、符号語中の“１”の数を重みとし、重みを２以上の自然数ｗとすることにより、様々な情報シンボルの生起確率に対応することができる。もちろん、ビットを反転させて、“０”の数を重みと考えて議論しても同様である。
【００３５】
図７は、符号語構成部２２におけるリバーシブル符号の符号語の第２の構成方法を示している。まず、図７の左側に示すように、符号長が短い順に（情報シンボル／２）個だけ、図４の方法によって重み（“１”の数）が一定（この場合は、１個）の２進符号系列を作成する。次に、図７の中央に示すように、この２進符号系列のそれぞれの先頭と末尾に“１”を追加し、さらに図７の右側に示すように、各符号語をビット反転させた符号語を追加する。
【００３６】
この可変長符号では、各符号の最初にあるシンボルの個数をカウントすることによって符号長が分かる。図７の例では、各符号の最初にあるシンボルが４つ出現したら符号が終わる符号構成、つまり符号の区切り（符号長）が分かる符号構成となっている。
【００３７】
この図７の可変長符号は、全ての情報シンボルＡ〜Ｊに対応する符号語が図８（ａ）に示す順方向の復号木の葉にも、図８（ｂ）の逆方向の復号木の葉にも割り当てられることから、順方向にも逆方向にも復号可能であることが分かる。
【００３８】
図９は、符号語構成部２２におけるリバーシブル符号の符号語の第３の構成方法を示している。このリバーシブル符号は、“０”と“１”の数が同じ数になることで、符号語の符号長が分かるような符号構成となっている。すなわち、図９（ａ）に示す格子状の有向グラフを考え、この有向グラフについてｓｔａｒｔ地点から出発して左側の経路を選択した時は“０”、右側の経路を選択した時は “１”をそれぞれ対応させ、ｓｔａｒｔ地点を通る対角線上の黒丸の点に到達する経路を符号語として生成する。
【００３９】
この場合、全ての情報シンボルＡ〜Ｊに対応する符号語が図１０（ａ）に示す順方向の復号木の葉にも、図１０（ｂ）の逆方向の復号木の葉にも割り当てられることから、順方向にも逆方向にも復号可能であることが分かる。
【００４０】
次に、本発明に係るリバーシブル符号の短縮化方法について説明する。情報シンボルの数、つまり可変長符号の符号数は有限であるため、可変長符号の一部の符号を短縮化することが可能である。ここで、短縮化とは他の符号の符号長を増やすことなく、一部の符号の符号長を縮めることをいう。図１１は、リバーシブル符号の短縮化方法の一例を示している。
【００４１】
例えば、図７に示したリバーシブル符号は情報シンボルＧ，Ｈ，Ｉ，Ｊに対応する符号語の末尾の１ビットを削除しても、順方向および逆方向のいずれの方向からも復号可能である。これを利用して、図１１では情報シンボルＧ，Ｈ，Ｉ，Ｊに対応する４つの符号語の符号長を短縮化している。
【００４２】
そして、この図１１に示す可変長符号は、全ての情報シンボルＡ〜Ｊに対応する符号語が図１２（ａ）に示す順方向の復号木の葉にも、図１２（ｂ）の逆方向の復号木の葉にも割り当てられることから、順方向にも逆方向にも復号可能であることが分かる。
【００４３】
次に、図１３を参照して本発明に係るリバーシブル符号の拡張化方法について説明する。リバーシブル符号の拡張化は、各符号の先頭および末尾の少なくとも一方に等長符号を付加して、同一の符号長の符号語数を拡大することで実現することができる。図１３の例では、左側に示すリバーシブル符号のそれぞれの末尾に２ビットの等長符号を付加している。この場合、リバーシブル符号の各符号は全体的に符号長が２ビット増加しているが、同じ符号長の符号語の数は４倍に拡大されている。一般に、ｎビットの等長符号を付加した場合、符号長は全体的にｎビット増加するが、同じ符号長の符号語の数を２n 倍にすることができる。等長符号は、明らかにリバーシブル符号なので、等長符号をリバーシブル符号の先頭や末尾に付加しても、やはりリバーシブル符号である。
【００４４】
図１４は、英語のアルファベットである情報シンボルに対して本発明により可変長符号化を行って得られたリバーシブル符号を公知例（特開平５−３０００２７号公報）に開示されているリバーシブル符号と比較して示したものである。図１４中に示される本発明に基づくリバーシブル符号は、図５で示した方法において符号語の重みを０とした時の符号を末尾に２ビットの等長符号を付加することによって拡張化した符号である。
【００４５】
この本発明に基づくリバーシブル符号は、順方向のみ復号可能な可変長符号の最適符号であるハフマン符号には劣るものの、公知例に開示されたリバーシブル符号と比較して平均符号長が短く、優れた性能を持っていることが分かる。これは、公知例のリバーシブル符号は順方向にのみ復号可能な可変長符号であるハフマン符号の末尾にビットを付加したものであるのに対して、本発明では余分なビットを付加することなく、初めからリバーシブル符号を構成するので、無駄なビットパターンが少ないことによる。
【００４６】
次に、本発明の他の実施形態を説明する。
図１５は、本発明の他の実施形態に係る可変長符号化／復号化装置の構成を示すブロック図である。本実施形態の可変長符号化／復号化装置は、大きく分けて符号語テーブル作成部２０１、符号化部２１３、伝送系または蓄積系２０５および復号化部２１４からなる。
【００４７】
これら各部の機能について簡単に説明すると、符号語テーブル作成部２０１は情報シンボルの生起確率に基づき符号語テーブルを作成して、符号化部２１３内の符号語テーブル２０２に送り、さらに作成した符号語テーブルの符号語のパラメータを復号化部２１４内の復号グラフ・復号値テーブル作成部２０８に送る。符号化部２１３は、情報シンボルを可変長符号に符号化し、その可変長符号を符号化データとして伝送系また蓄積系２０５へ出力する。復号化部２１４は、伝送系または蓄積系２０５を介して入力されてきた符号化データを復号して元の情報シンボルを再生する。
【００４８】
次に、本実施形態の各部の詳細な構成と動作を説明する。
【００４９】
符号化部２１３において、入力された情報シンボルは符号化器２０３に入力される。符号語テーブル２０２は、符号語テーブル作成部２０１によって予め作成された情報シンボルと可変長符号の符号語とを対応させて格納している。但し、符号語テーブル２０２には入力され得る情報シンボルの全てに対応する符号語が格納されているわけではなく、比較的出現頻度の高い一部の情報シンボルに対応した符号語のみが格納されているものとする。符号化器２０３は符号語テーブル２０２に格納されている符号語の中から、入力された情報シンボルに対応した符号語を選択して符号化データとして出力する。
【００５０】
一方、符号化部２１３に符号語テーブル２０２に対応する符号語が存在しない情報シンボル、つまり出現頻度の比較的低い情報シンボルが入力されたときは、その情報シンボルに対応した固定長符号を固定長符号符号化部２０４で作成し、さらに符号語テーブル２０２中のエスケープ符号を固定長符号の先頭と末尾に付加して符号語とし、これを符号化データとして出力する。
【００５１】
こうして符号化部２１３内の符号化器２０３から出力された符号化データは、伝送系または蓄積系２０５を通して復号化部２１４に送られる。この際、符号化データには一定周期毎に同期コードが挿入される。
【００５２】
復号化部２１４は、同期コード検出部２０６、バッファ２０７、復号グラフ・復号値テーブル作成部２０８、順方向復号化器２０９、固定長復号化部２１０、逆方向復号化器２１１および復号値判定部２１２からなり、まず伝送系または蓄積系２０５より入力された符号化データから同期コード検出部２０６で同期コードを検出し、同期コードと同期コードの間の符号化データをバッファ２０７に蓄積する。順方向復号化器２０９では、バッファ２０７に蓄積された符号化データの先頭から復号を開始し、逆方向復号化器２１１では、バッファ２０７に蓄積された符号化データの末尾から復号を開始する。復号値判定部２１２では、順方向復号化器２０９によって得られた復号結果（順方向復号値という）と、逆方向復号化器２１１によって得られた復号結果（逆方向復号値という）から復号値を判定し、最終的な復号結果を出力する。
【００５３】
図１６は、図１５中の符号語テーブル作成部２０１において、固定長符号の先頭と末尾にエスケープ符号を付加して符号語を構成する方法を示した図である。図１６（ａ）に示すように、符号語テーブル作成部２０１が作成する符号語は、情報シンボルが“Ａ”以外のときは、“１”の数が３つ出現することで符号の区切りがわかるリバーシブル符号を基本としている。このリバーシブル符号を符号（１）と呼ぶこととする。
【００５４】
一方、図１６（ｂ）に示す符号（２）は、符号（１）の情報シンボル“Ｃ”に対応する符号語“１０１１”を固定長符号の先頭と末尾を示すためのエスケープ符号として、３ビットの固定長符号の先頭と末尾に付加することにより構成された符号語を符号（１）に新たに加えたものとなっている。但し、符号（２）のうち符号（１）に相当するリバーシブル符号の部分は、符号（２）でエスケープ符号として用いた符号語“１０１１”は使用せず、符号（１）により１個少ない情報シンボルＡ〜Ｉに対応した符号語のみを用いている。図１６（ａ）（ｂ）を比較して明らかなように、符号（２）は符号化できる情報シンボルの数が符号（１）の「１０」から「１７」に増えている。
【００５５】
このような符号（２）を復号するためには、図１６（ａ）（ｂ）から分かるように順方向から復号する場合も逆方向から復号する場合も、必ず符号（１）を一度復号することになり、また固定長符号は順方向からも逆方向からも復号可能であるため、符号（１）が順方向からも逆方向からも復号可能ならば、符号（２）も順方向からも逆方向からも復号可能となる。
【００５６】
従来のリバーシブル符号の場合は、入力され得る情報シンボルに対応する符号語を全て符号語テーブルとして符号化部２１３および復号化部２１４において用意しておく必要があった。これに対し、符号（２）によると、固定長符号の部分については、３ビットの２進符号として別途に固定長符号符号化部２０４および固定長符号復号化部２１０として用意できるので、符号語テーブル２０２には符号（１）の符号語だけを格納しておけばよい。したがって、従来のリバーシブル符号と比較して、可変長符号化／復号化装置の記憶量を大幅に削減することが可能となる。
【００５７】
復号グラフ・復号値テーブル作成部２０８は、Ｓｈａｌｋｗｉｊｋのアルゴリズムを基にした復号グラフと、復号値テーブルを作成し、順方向復号化器２０９および逆方向復号化器２１１は、これらの復号グラフおよび復号値テーブルに基づいて復号化を行う。
【００５８】
図１７は、重み一定の２進符号系列の数え上げの方法を示している。重み一定の２進符号系列の数え上げを行うアルゴリズムとしては、J.P.M.Shalkwijk:“An algorithm for source coding”，IEEE Trans.Infrom Theory,vol.IT-18,no.3,pp.395-399,May 1972.がＳｈａｌｋｗｉｊｋのアルゴリズムとしてよく知られている。Ｓｈａｌｋｗｉｊｋのアルゴリズムでは、図１７（ａ）に示すように「パスカルの三角形」を基本とした、ＳＴＡＲＴ地点からＥＮＤ地点に至る格子状の有向グラフを形成する。各節点に数字で示された値は、ＳＴＡＲＴ地点の節点の値を１として、各節点に入ってくる２つの矢の起点にある節点の値の合計値となっている。すなわち、各節点の値はパスカルの三角形によって決定される。
【００５９】
そして、図１７（ａ）の有向グラフについて、入力される情報シンボルに従ってＳＴＡＲＴ地点からＥＮＤ地点までの経路をたどる際に、左側の経路（矢）を選択したときには符号語の“０”、右側の経路（矢）を選択したときには符号語の“１”をそれぞれ対応させることにより、重み２の２進符号系列を生成することができる。ここで、“０”を選択したときに矢の終点にある節点の値から矢の起点にある節点の値を引いた値を合計した値が、その２進符号系列の同一符号長の符号語についての順序値となる。例えば入力される情報シンボルが“０１００１”であれば、３つある“０”に対して節点の値の差分の合計である（１−１）＋（３−２）＋（４−３）＝２が順序値となる。ここで、順次値とは同一符号長の異なる符号語を順序付けるための値である。図１７（ｂ）は、この場合の情報シンボルと順序値との関係を示している。
【００６０】
このＳｈａｌｋｗｉｊｋのアルゴリズムを符号化に適用した例は公知であり、その場合は上記の順序値に相当する値を２進符号に変換することによって符号化を行う。これに対し、本実施形態ではこのアルゴリズムを以下に説明するように復号化に用いる。
【００６１】
すなわち、復号グラフ・復号値テーブル作成部２０８では、上述したＳｈａｌｋｗｉｊｋのアルゴリズムを基にして有向グラフを復号グラフとして作成する。すなわち、この復号グラフはパスカルの三角形によって決まる値を節点の値とし、符号語の“１”および“０”を矢とした有向グラフであり、その一例を図１８（ａ）に示す。図１８（ｂ）は、この復号グラフを用いた順方向復号化器２０８および逆方向復号化器２１１における復号値の計算方法の一例を示している。
【００６２】
図１６（ａ）に示した符号（１）は、先頭が“０”以外のときは“１”が３つ出現した地点で区切りが分かるリバーシブル符号である。この符号（１）のリバーシブル符号の復号値を計算する際には、順方向についてはリバーシブル符号の先頭が“０”ならば復号値を０とし、それ以外のときは先頭と末端の“１”を削除した後、Ｓｈａｌｋｗｉｊｋのアルゴリズムによって順序値を計算する。今、復号しようとしている符号語より符号長の短い符号語の数は、図１８（ａ）におけるＥＮＤ地点の右斜めの節点の値の合計＋１となるので、その値を順序値に足したものが復号値となる。
【００６３】
一方、逆方向については上述の順方向の場合と同様に、まずリバーシブル符号の先頭が“０”ならば復号値を０とし、それ以外のときは先頭と末端の“１”を削除し、さらに残りの部分を反転させた後、Ｓｈａｌｋｗｉｊｋのアルゴリズムで順序値を計算する。そして、この順序値にＥＮＤ地点の右斜め上にある節点の合計＋１を足したものを復号値とする。
【００６４】
図１８（ａ）（ｂ）を参照して具体的に説明すると、例えばリバーシブル符号の復号対象の符号語が“１０１０１”ならば、まず先頭と末端の“１”を削除して“０１０”とする。この“０１０”に対してＳｈａｌｋｗｉｊｋのアルゴリズムで順序値を求めると、２つある“０”に対して、（１−１）＋（３−２）＝１となる。この場合のＥＮＤ地点の斜め右上にある節点の値の合計は１＋２＝３なので、この値＋１（＝４）を順序値（＝１）に加えて、復号値が５として求まることになる。
【００６５】
このような復号グラフを用いて復号化を行うと、記憶量を大きく低減することができる。図１９（ａ）（ｂ）は、従来の復号木を用いる復号化方法と、本実施形態による復号グラフを用いる復号化方法で必要な記憶量の違いを示した図である。両者を節点の数で比較すると、各節点から出る矢の数は共に２つで同じであるが、各節点に入ってくる矢は図１９（ａ）の復号木の場合、必ず１つである。これに対して、図１９（ｂ）の復号グラフの場合は、各節点に２つの矢が入ってくるので、その分だけ同じ符号語で必要とする節点の総数が少なくなる。この例では、図１９（ａ）の復号木が１５個の節点を必要としているのに対し、図１９（ｂ）の復号グラフでは８個の節点で済む。従って、復号グラフを用いる本実施形態の復号化方法は、従来の復号木を用いる方法よりも必要な記憶量が少なくなるという利点がある。
【００６６】
また、本実施形態では図１６（ｂ）に示したエスケープ符号を付加した符号 （２）を復号するために、図２０（ａ）に示す符号（１）の復号値テーブルと、図２０（ｂ）に示す固定長符号の復号値テーブルの２つを用意し、符号（１）の復号値テーブルでエスケープ符号が復号されたときは、固定長符号の復号値テーブルを読みに行く。例えば、符号語が“１０１１００１１０１１”の場合、先頭の“１０１１”、すなわちエスケープ符号が復号されたら、次の３ビット“００１”は固定長符号であると見なして固定長符号復号化部２１０で復号を行う。この場合、“００１”の復号値として１が得られるので、図２０（ａ）の固定長符号の復号値テーブルから、復号結果は情報シンボル“Ｋ”となる。
【００６７】
次に、本発明を動画像符号化／復号化器に適用した一実施形態について説明する。図２１は、上述した可変長符号化／復号化装置が組み込まれた動画像符号化／復号化器の概略的構成を示すブロック図である。
【００６８】
図２１（ａ）に示す動画像符号化器７０９において、情報源符号化器７０２で符号化されたデータは、動画像多重化部７０３で可変長符号化、通信路符号化および多重化等が行われ、さらに伝送バッファ７０４で伝送速度の平滑化がなされた後に、符号化データとして伝送系または蓄積系７０５に送り出される。符号化制御部７０１は、伝送バッファ７０４のバッファ量を考慮して、情報源符号化器７０２および動画像多重化部７０３の制御を行う。
【００６９】
一方、図２１（ｂ）に示す動画像復号化器７１０においては、伝送系または蓄積系７０５からの符号化データが受信バッファ７０６に一旦溜められ、動画像多重化分離部７０７で符号化データの多重化分離、通信路符号復号化および可変長符号復号化が行われた後、情報源復号化器７０８に送られ、最終的に動画像が復号化される。
【００７０】
図２２は、図２１における動画像符号化器７０９および動画像多重化分離部７０７での動画像符号化方式のシンタックスを示している。図２２（ａ）に示すピクチャ階層のうち、上位階層にはマクロブロックのモード情報や動きベクトル情報やＩＮＴＲＡ ＤＣなどのＤＣＴ係数以外の情報を配し、下位階層にはＤＣＴ係数情報を配しており、下位階層部分に本発明によるリバーシブル符号を適用している。
【００７１】
図２３（ａ）（ｂ）は、図２１における動画像多重化部７０３および動画像多重化分離部７０７のより詳しい構成を示すブロック図である。図２３（ａ）に示す動画像多重化部７０３においては、図２１の情報源符号化器７０２からの符号化データのうち、マクロブロックのモード情報や動きベクトル情報やＩＮＴＲＡＤＣなどの、ＤＣＴ係数以外の情報は上位階層として、上位階層可変長符号化器９０１で通常の可変長符号化が行われた後、さらに上位階層通信路符号化器９０２で冗長度は大きいが訂正能力の高い誤り訂正検出符号により通信路符号化され、多重化部９０５に送られる。
【００７２】
一方、情報源符号化器７０２からの符号化データのうち、ＤＣＴ係数は下位階層可変長符号化器９０３でリバーシブル符号に符号化され、さらに下位階層通信路符号化器９０４で冗長度の少ない誤り訂正検出符号により通信路符号化された後、多重化部９０５に送られる。多重化部９０５では、上位階層の符号化データと下位階層の符号化データを多重化し、伝送バッファ７０４に送る。
【００７３】
図２３（ｂ）に示す動画像多重化分離部７０７においては、まず受信バッファ７０６からの符号化データが多重化分離部９０６で上位階層と下位階層に分離される。上位階層の符号化データは上位階層通信路復号化器９０７で復号され、その復号結果は上位階層可変長復号化器９０９に送られる。下位階層の符号化データは下位階層通信路復号化器９０８で復号され、その復号結果は下位階層可変長復号化器９１０に送られる。
【００７４】
下位階層可変長復号化器９１０はリバーシブル符号の復号を行い、復号結果を情報源復号化器７０８および上位階層可変長復号化器９０９に送る。上位階層可変長復号化器９０９は、上位階層の符号化データである可変長符号の復号を行うと共に、下位階層可変長復号化器９１０の復号結果を基に符号化結果の書き換えを行う。
【００７５】
ここで、図２３（ａ）中の下位階層可変長符号化器９０３は図１５中の符号化部２１３に、図２３（ｂ）中の下位階層可変長復号化器９１０は図１５中の復号化部２１４にそれぞれ対応している。
【００７６】
本実施形態の動画像符号化／復号化器に見られるように、符号化方式に図２２に示したようなシンタックスがある場合には、可変長符号そのものを両方向から復号できるのみでなく、シンタックス的にも両方向から復号できるようにする必要がある。本実施形態では、以下に説明する符号語テーブルを用いることによって、この要求を実現している。
【００７７】
図２４〜図２８は、下位階層可変長符号化器９０３で用いるＤＣＴ係数の可変長符号の符号語テーブルの一例を示している。また、図２９はエスケープ符号の符号語テーブルを示している。
【００７８】
情報源符号化器７０２では、量子化後の８×８のＤＣＴ係数のブロックについてはブロック内のスキャンを行って、ＬＡＳＴ（０：ブロックの最後でない非零係数、１：ブロックの最後の非零係数）、ＲＵＮ（非零係数までの零ランの数）およびＬＥＶＥＬ（係数の絶対値）を求め、動画像符号化器７０９に送る。
【００７９】
動画像符号化器７０９内の下位階層可変長符号化器９０３は、図２４〜図２５に示すＩＮＴＲＡおよびＩＮＴＥＲの非ＬＡＳＴ係数、ＲＵＮ、ＬＥＶＥＬにリバーシブル符号（ＶＬＣ＿ＣＯＤＥ）を対応させた非ＬＡＳＴ係数の符号語テーブル（第１の符号語テーブル）と、図２６〜図２７に示すＩＮＴＲＡおよびＩＮＴＥＲのＬＡＳＴ係数、ＲＵＮ、ＬＥＶＥＬにリバーシブル符号（ＶＬＣ＿ＣＯＤＥ）を対応させたＬＡＳＴ係数の符号語テーブル（第２の符号語テーブル）を持っている。そして、モード情報に基づいてＩＮＴＲＡのときはＩＮＴＲＡの非ＬＡＳＴ係数とＬＡＳＴ係数の符号語テーブル、ＩＮＴＥＲのときはＩＮＴＥＲの非ＬＡＳＴ係数とＬＡＳＴ係数の符号語テーブルをそれぞれ選択して符号化を行う。なお、図２６〜図２７においてＶＬＣ＿ＣＯＤＥの最終ビットの“Ｓ”はＬＥＶＥＬの符号を表し、“Ｓ”が“０”のときＬＥＶＥＬの符号は正、“１”のとき負である。
【００８０】
また、この符号語テーブルに存在しない係数は、図２９に示すようにＲＵＮとＬＥＶＥＬの絶対値を固定長符号に符号化し、この固定長符号の先頭と末端にエスケープ符号を付加し、エスケープ符号の最終ビットでＬＡＳＴ係数とＬＥＶＥＬの正負を区別できるように符号化する。図２８は、このエスケープ符号の符号語テーブルであり、エスケープ符号として用いられているＶＬＣ＿ＣＯＤＥの最終ビットの“ｔ”は、固定長符号の先頭に付加されたときはＬＡＳＴ係数か否かを表し、これが“０”のときは非ＬＡＳＴ係数、“１”のときはＬＡＳＴ係数である。また、“ｔ”は固定長符号の末尾に付加されたときはＬＥＶＥＬの符号を表し、これが“０”のときＬＥＶＥＬの符号は正、“１”のときは負である。
【００８１】
図３０は、本実施形態における符号化データの例を示している。同図に示されるように、下位階層において順方向から復号を行うときは、８×８画素のＤＣＴ係数のブロックの末尾に必ずＬＡＳＴ係数の符号が存在するため、ブロックの末尾を判定することができる。一方、逆方向から復号を行うときは、１つアドレスが前のブロックのＬＡＳＴ係数の符号が出現することにより、ブロックの先頭を判定できる。この符号は、ＬＡＳＴ係数がＩＮＴＲＡモードとＩＮＴＥＲモードで共通化されているため、マククロブロック毎にモードが存在していてもブロックの先頭を判定することができる。
【００８２】
下位階層の最初のブロックについては、予め下位階層可変長符号化器９０３で下位階層の先頭にダミーのＬＡＳＴ係数を符号化しておくか、あるいは、下位階層可変長復号化器９１０で、次のフレームの同期符号までのビット数から予め下位階層のビット数を計算しておき、これを復号したビット数と比較するか、あるいは、下位階層可変長復号化器９１０内のバッファで下位階層の先頭にダミーのＬＡＳＴ係数を挿入する方法をとることにより、逆方向に復号したときに下位階層の先頭を判定することができる。
【００８３】
図２４〜図２７に示した符号語テーブルに格納されたリバーシブル符号は、順方向の場合、先頭の１ビットが“０”ならば、“０”が２つ出現するまで読み、“１”ならば、“１”が２つ出現するまで読み、その次の１ビットがＬＥＶＥＬの正負を表す最終ビットとなることが分かる。逆方向の場合は、最初の１ビットがＬＥＶＥＬの正負を表しており、次の１ビットが“０”ならば、“０”が２つ出現するまで読み、“１”ならば、“１”が２つ出現するまで読めばよい。
【００８４】
図３１は、本実施形態における下位階層可変長符号化器９０３で用いるＤＣＴ係数の可変長符号に適用したリバーシブル符号を復号するための復号グラフを示している。順方向からみて符号語の先頭ビットと末尾の２ビットを除いた符号化データについて、この復号グラフによって復号値を計算することができる。
【００８５】
この復号グラフは、先頭のビットが“０”ならば、“０”が現れれば右の矢を進み、“１”が現れれば左の矢を進むこととする。先頭のビットが“１”ならば、“１”が現れれば右の矢を進み、“０”が現れれば左の矢を進むこととする。
【００８６】
同一の符号長の２進符号系列についての順序値を求めるには、先に説明したＳｈａｌｋｗｉｊｋのアルゴリズムに従って、左側の矢を選択したときに矢の終点の節点の値から起点の節点の値を引いた値の合計値をその符号長での順序値とすればよい。
【００８７】
一方、復号値を求めるには、先頭のビットが“０”ならば、終端の節点の右斜め上の節点の値の合計値の２倍を順序値に足した値を復号値とすればよい。先頭ビットが“１”ならば、終端の節点の右斜め上の節点の値の合計値の２倍＋終端の節点の値に順序値を足した値を復号値とればよい。
【００８８】
例えば、復号対象の符号列が“０１１０１０１”ならば、まず順方向からみて先頭の１ビットと末尾の２ビットを除いて、“１１０１”とする。先頭ビットが“０”なので、復号グラフで“０”が現れれば右の矢を進み、“１”が現れれば左の印を進むことになる。この場合、左の矢を進んだときの節点の差分は（１−１）＋（１−１）＋（４−３）＝１なので、順序値は１である。最上位ビットが“０”なので、終端の節点の右斜め上にある節点の合計の２倍（１＋２＋３）×２＝１２に順序１を加えると１３となり、この符号語の復号値は１３として求められることになる。
【００８９】
図３２〜図３４は、下位階層可変長復号化器９１０で用いる復号値テーブルの一例であり、図３２〜図３３はＩＮＴＲＡおよびＩＮＴＥＲの非ＬＡＳＴ係数、ＲＵＮ、ＬＥＶＥＬに復号値を対応させた非ＬＡＳＴ係数の復号値テーブルであり、図３４（ａ）（ｂ）はＩＮＴＲＡおよびＩＮＴＥＲのＬＡＳＴ係数、ＲＵＮ、ＬＥＶＥＬに復号値を対応させたＬＡＳＴ係数の復号値テーブルである。また、図３４（ｃ）はエスケープ符号の復号値テーブルである。
【００９０】
この例では、例えば復号値１３は図３４（ａ）で分かるように、ＬＡＳＴ係数で、ＲＵＮ数は３、ＬＥＶＥＬの絶対値が１であることが分かり、また最下位ビットが“１”であることから、ＬＥＶＥＬは負であることが分かる。さらに、図３４（ｃ）で分かるように、復号値４１が復号された場合は、エスケープ符号が復号されたと判定する。このエスケープ符号の最後のビットでＬＡＳＴ係数か非ＬＡＳＴ係数かの判定を行い、その後の１３ビットについて固定長符号復号化部２１０でＲＵＮとＬＥＶＥＬの絶対値を復号した後、再びエスケープ符号を復号し、最後のビットでＬＥＶＥＬの正負を決定する。
【００９１】
一例として、符号化対象の符号列が“１１０００００１００００１１１０００１０１１１１００００１０”の場合を考える。この場合、先頭のエスケープ符号“１１００００１０”の最終ビットが“０”なので、非ＬＡＳＴ係数であり、その後の１３ビットの固定長符号を計算する。この１３ビットのうち上位６ビットがＲＵＮを表すので、“０００１１１”でＲＵＮは７、下位７ビットがＬＥＶＥＬの絶対値を表すので、“０００１０１１”でＬＥＶＥＬの絶対値は１２、末尾のエスケープ符号“１１００００１０”の最終ビットが“０”なのでＬＥＶＥＬは正、というように復号を行うことができる。
【００９２】
復号値判定部２１２では、このようにして順方向復号化器２０９によって得られた復号結果（順方向復号結果という）と、逆方向復号化器２１１によって得られた復号結果（逆方向復号値という）から復号値を判定し、最終的な復号結果を出力する。すなわち、復号値判定部２１２では符号化データに誤りがあると、下位階層通信路復号化器９０８の復号結果、あるいは、符号語として存在しなかったビットパターンが生じることから、誤りの存在が分かるので、これらの順方向復号結果と逆方向復号結果から、図３６に示すようにして復号値を判定する。なお、図３６は下位階層の復号値判定方法を示している。
【００９３】
まず、図３６（ａ）に示すように順方向復号結果と逆方向復号結果で誤りが検出されるマクロブロックの位置（誤り検出位置）が交差しない場合は、誤りが検出されなかったマクロブロックの復号結果のみを復号値として使用し、二つの誤り検出位置の復号結果は復号値として使用しない。そして、上位階層のモード情報の復号結果に基づいて、ＩＮＴＲＡマクロブロックについては前フレームをそのまま表示するように、ＩＮＴＥＲマクロブロックについては前フレームより動き補償のみで表示するように、上位階層の復号結果を書き換える。
【００９４】
また、図３６（ｂ）に示すように順方向復号結果と逆方向復号結果で誤りが検出位置が交差する場合は、両方で誤りが検出されなかった復号結果を復号結果値として使用する。また、この場合には二つの誤り検出位置の符号語の間の復号結果は復号値として使用せず、上位階層のモード情報の復号結果に基づいて、ＩＮＴＲＡマクロブロックについては前フレームをそのまま表示するように、ＩＮＴＥＲマクロブロックについては前フレームより動き補償のみで表示するように、上位階層の復号結果を書き換える。
【００９５】
また、図３６（ｃ）に示すように順方向復号結果および逆方向復号結果のうち、片方向の復号結果にしか誤りが検出されない場合（この例では、順方向復号結果のみ誤りが検出されている）は、誤り検出位置のマクロブロックは復号値として使用せず、上位階層のモード情報の復号結果に基づいて、ＩＮＴＲＡマクロブロックについては前フレームをそのまま表示するように、ＩＮＴＥＲマクロブロックについては前フレームより動き補償のみで表示するように、上位階層の復号結果を書き換える。それ以後のマクロブロックに対する復号値は、逆方向の復号結果を使用する。
【００９６】
さらに、図３６（ｄ）に示すように同一のマクロブロックで順方向復号結果および逆方向復号結果の両方に誤りが検出される場合は、誤り検出位置のマクロブロックの復号値は放棄して復号値として使用せず、上位階層のモード情報の復号結果に基づいて、ＩＮＴＲＡマクロブロックについては前フレームをそのまま表示するように、ＩＮＴＥＲマクロブロックについては前フレームより動き補償のみで表示するように、上位階層の復号結果を書き換え、それ以後のマクロブロックに対する復号値は逆方向の復号結果を使用する。
【００９７】
マクロブロックの符号化／復号化の順序については、上記実施形態以外の方法でもよく、例えば誤りがあったときに、復号画像のうちより重要な画面中央部が救済されるように、図３７に示すような順序とする方法でもよい。すなわち、両方向から復号することを前提とすると、同期符号と同期符号の間の符号化データのうち、最初の方の部分と最後の方の部分が正しく復号される確率が高いので、これの部分が中央部にくるように順序を決めるのである。
【００９８】
なお、上記実施形態ではＤＣＴ係数の可変長符号化に本発明を適用したが、他の情報シンボルについても同様の可変長符号化を適用できることは、言うまでもない。
【００９９】
また、上記実施形態では２元符号のみの議論を示したが、多元符号にも拡張することが容易であり、同様な効果を得ることができる。
【０１００】
最後に、本発明の応用例として、本発明による可変長符号化／復号化装置を適用した画像送受信装置の実施形態を図３８を用いて説明する。パーソナルコンピュータ（ＰＣ）１００１に備えら付けられたカメラ１００２より入力された画像信号は、ＰＣ１００１に組み込まれた可変長符号化装置によって符号化される。この場合の情報シンボルは、これに限るものではないが、例えば入力画像信号または入力画像信号と予測画像信号との差である予測誤差信号をＤＣＴ回路によって離散コサイン変換し、さらに量子化回路により量子化して得られたＤＣＴ係数データなどである。可変長符号化装置から出力される符号化データは、他の音声やデータの情報と多重化された後、無線機１００３により無線で送信され、他の無線機１００４によって受信される。無線機１００４で受信された信号は、画像信号の符号化データおよび音声やデータの情報に分解される。これらのうち、画像信号の符号化データはワークステーション（ＥＷＳ）１００５に組み込まれた可変長符号復号化装置によって復号され、ＥＷＳ１００５のディスプレイに表示される。
【０１０１】
一方、ＥＷＳ１００５に備え付けられたカメラ１００６より入力された画像信号は、ＥＷＳ１００６に組み込まれた可変長符号化装置を用いて上記と同様に符号化される。符号化データは、他の音声やデータの情報と多重化され、無線機１００４により無線で送信され、無線機１００３によって受信される。無線機１００３によって受信された信号は、画像信号の符号化データおよび音声やデータの情報に分解される。これらのうち、画像信号の符号化データはＰＣ１００１に組み込まれた可変長符号復号化装置によって復号され、ＰＣ１００１のディスプレイに表示される。
【０１０２】
本発明の可変長符号化／復号化装置は、情報シンボルの出現頻度に応じた符号長を有し、従来と比較して無駄なビットパターンが少なくて効率がよく、しかも順方向にも逆方向にも復号が可能なリバーシブルの可変長符号を構成することができるので、図３８に示した無線伝送路のような誤りが多い伝送路を用いた送受信装置において特に有効である。
【０１０３】
以上実施形態で説明したように、本発明の可変長符号化／復号化装置は、従来と比較して、少ない記憶量で復号することができ、従来適用することのできなかったような情報シンボル数が大きな符号化に対しても適用することができる。具体的には、動画像符号化／復号化装置にも適用することが可能であり、誤りに強い動画像符号化／復号化装置を提供することができる。
【０１０４】
【発明の効果】
以上説明したように、本発明によれば順方向にも逆方向にも復号可能で、しかも符号化効率や装置に必要な記憶量などの点で実用性に富んだ可変長符号化方法及び装置を提供することができる。
【図面の簡単な説明】
【図１】本発明の一実施形態に係る可変長符号化／復号化装置の構成を示すブロック図
【図２】図１における復号値判定部の動作を説明するための図
【図３】図１における符号語テーブル作成部のブロック図
【図４】本発明に係る可変長符号の基となる重み一定の２進符号系列の作成方法を示す図
【図５】図３における符号語構成部での第１の符号語構成方法を示す図
【図６】第１の符号構成方法で構成した符号語から作成した順方向および逆方向の復号木を示す図
【図７】図３における符号語構成部での第２の符号語構成方法を示す図
【図８】第２の符号構成方法で構成した符号語から作成した順方向および逆方向の復号木を示す図
【図９】図３における符号語構成部での第３の符号構成方法を示す図
【図１０】第３の符号構成方法で構成した符号語から作成した順方向および逆方向の復号木を示す図
【図１１】図３における符号語構成部での符号短縮化方法を示す図
【図１２】符号短縮化方法で短縮化した符号語から作成した順方向および逆方向の復号木を示す図
【図１３】図３における符号語構成部での符号拡大化方法を示す図
【図１４】本実施形態で構成された可変長符号と公知例の可変長符号の特性を比較して示す図
【図１５】本発明の他の実施形態に係る可変長符号化／復号化装置の構成を示すブロック図
【図１６】図１５における符号語構成部での符号構成方法を示す図
【図１７】重み一定の２進系列を数え上げる方法を示す図
【図１８】図１５における順方向復号化器および逆方向復号化器の動作を示す図
【図１９】従来の復号木と本実施形態における復号グラフを比較して示す図
【図２０】本実施形態における復号値テーブルを説明するための図
【図２１】本発明による可変長符号化／復号化装置が組み込まれた動画像符号化／復号化器の概略構成を示すブロック図
【図２２】同実施形態に係る動画像符号化／復号化器における符号化データのシンタックスを示す図
【図２３】図２１における動画像多重化部および動画像多重化分離部の構成を示すブロック図
【図２４】同実施形態におけるＩＮＴＲＡおよびＩＮＴＥＲの非ＬＡＳＴ係数の符号語テーブルの一部を示す図
【図２５】同実施形態におけるＩＮＴＲＡおよびＩＮＴＥＲの非ＬＡＳＴ係数の符号語テーブルの他の一部を示す図
【図２６】同実施形態におけるＩＮＴＲＡおよびＩＮＴＥＲのＬＡＳＴ係数の符号語テーブルの一部を示す図
【図２７】同実施形態におけるＩＮＴＲＡおよびＩＮＴＥＲのＬＡＳＴ係数の符号語テーブルの他の一部を示す図
【図２８】同実施形態におけるエスケープ符号の符号語テーブルを示す図
【図２９】同実施形態における符号語テーブルにない符号語の符号化方法を示す図
【図３０】同実施形態における符号化データの例を示す図
【図３１】同実施形態における復号グラフを示す図
【図３２】同実施形態におけるＩＮＴＲＡおよびＩＮＴＥＲの非ＬＡＳＴ係数の復号値テーブルの一部を示す図
【図３３】同実施形態におけるＩＮＴＲＡおよびＩＮＴＥＲの非ＬＡＳＴ係数の復号値テーブルの他の一部を示す図
【図３４】同実施形態におけるＩＮＴＲＡおよびＩＮＴＥＲのＬＡＳＴ係数の復号値テーブルを示す図
【図３５】同実施形態におけるエスケープ符号の復号値テーブルを示す図
【図３６】図１５における復号値判定部の動作を説明するための図
【図３７】同実施形態におけるマクロブロックの符号化／復号化順序を示す図
【図３８】本発明による可変長符号化／復号化装置が組み込まれる装置の一例を示す図
【図３９】リバーシブル符号の一般的な復号方法を示す図
【図４０】通常の可変長符号の説明図
【図４１】従来のリバーシブル符号の説明図
【符号の説明】
１０１…符号語テーブル作成部
１０２…符号語テーブル
１０３…符号化器
１０４…伝送系または蓄積系
１０５…同期コード検出部
１０６…バッファ
１０７…順方向復号化器
１０８…逆方向復号化器
１０９…復号値判定部
１１０…順方向復号語テーブル
１１１…順方向復号木作成部
１１２…逆方向符号語テーブル
１１３…逆方向復号木作成部
１１４…符号化部
１１５…復号化部
２１…符号選択部
２２…符号語構成部
２０１…符号語テーブル作成部
２０２…符号語テーブル
２０３…符号化器
２０４…固定長符号符号化部
２０５…伝送系または蓄積系
２０６…同期コード検出部
２０７…バッファ
２０８…復号グラフ・復号値テーブル作成部
２０９…順方向復号化器
２２０…固定長符号復号化部
２１１…逆方向復号化器
２１２…復号値判定部
２１３…符号化部
２１４…復号化部
７０１…符号化制御部
７０２…情報源符号化器
７０３…動画像多重化部
７０４…伝送バッファ
７０５…伝送系または蓄積系
７０６…受信バッファ
７０７…動画像多重化分離部
７０８…情報源復号化器
７０９…動画像符号化器
７１０…動画像復号化器
９０１…下位階層可変長復号化器
９０２…上位階層通信路符号化器
９０３…下位階層可変長符号化器
９０４…下位階層通信路符号化器
９０５…多重化部
９０６…多重化分離部
９０７…上位階層通信路復号化器
９０８…下位階層通信路復号化器
９０９…上位階層可変長復号化器
９１０…下位階層可変長復号化器
１００１…パーソナルコンピュータ
１００２…ワークステーション
１００３…無線機
１００４…無線機
１００５…カメラ
１００６…カメラ
Claims (6)
- 順方向にも逆方向にも復号可能な複数の可変長符号の各々と、長さが等しく符号の異なる複数の等長符号の各々との全ての組み合わせからなる順方向にも逆方向にも復号可能な複数の符号語を用意しておき、前記入力された情報シンボルに対応して前記複数の符号語のいずれかを符号化データとして出力することを特徴とする可変長符号化方法。
- 複数の情報シンボルに対して該情報シンボルの生起確率に応じた符号長を有する符号語をそれぞれ割り当て、入力された情報シンボルに対応した符号語を符号化データとして出力する可変長符号化方法において、
順方向にも逆方向にも復号可能な複数の可変長符号の各々の先頭および末尾の少なくとも一方に、長さが等しく符号の異なる複数の等長符号の各々を付加して組み合わせた全ての組み合わせからなる順方向にも逆方向にも復号可能な複数の符号語を用意しておき、前記入力された情報シンボルに対応して前記複数の符号語のいずれかを符号化データとして出力することを特徴とする可変長符号化方法。 - 前記順方向にも逆方向にも復号可能な複数の可変長符号は、予め定められた“１”または“０”の数によって符号語の区切りが分かるように構成された符号語であることを特徴とする請求項１または２のいずれか１項記載の可変長符号化方法。
- 複数の情報シンボルに対して該情報シンボルの生起確率に応じた符号長を有する符号語をそれぞれ割り当て、入力された情報シンボルに対応した符号語を符号化データとして出力する可変長符号化装置において、
順方向にも逆方向にも復号可能な複数の可変長符号の各々と、長さが等しく符号の異なる複数の等長符号の各々との全ての組み合わせからなる順方向にも逆方向にも復号可能な複数の符号語を用意しておき、前記入力された情報シンボルに対応して前記複数の符号語のいずれかを符号化データとして出力する符号化手段を有することを特徴とする可変長符号化装置。 - 複数の情報シンボルに対して該情報シンボルの生起確率に応じた符号長を有する符号語をそれぞれ割り当て、入力された情報シンボルに対応した符号語を符号化データとして出力する可変長符号化装置において、
順方向にも逆方向にも復号可能な複数の可変長符号の各々の先頭および末尾の少なくとも一方に、長さが等しく符号の異なる複数の等長符号の各々を付加して組み合わせた全ての組み合わせからなる順方向にも逆方向にも復号可能な複数の符号語を用意しておき、前記入力された情報シンボルに対応して前記複数の符号語のいずれかを符号化データとして出力する符号化手段を有することを特徴とする可変長符号化装置。 - 前記順方向にも逆方向にも復号可能な複数の可変長符号は、予め定められた“１”または“０”の数によって符号語の区切りが分かるように構成された符号語であることを特徴とする請求項４または５のいずれか１項記載の可変長符号化装置。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP2003146489A JP3866687B2 (ja) | 1995-04-14 | 2003-05-23 | 可変長符号化方法及び装置 |
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP8977295 | 1995-04-14 | ||
| JP2003146489A JP3866687B2 (ja) | 1995-04-14 | 2003-05-23 | 可変長符号化方法及び装置 |
Related Parent Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2001117331A Division JP3748215B2 (ja) | 1995-04-14 | 2001-04-16 | 可変長符号化方法及び装置 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JP2004048723A JP2004048723A (ja) | 2004-02-12 |
| JP3866687B2 true JP3866687B2 (ja) | 2007-01-10 |
Family
ID=31718645
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2003146489A Expired - Lifetime JP3866687B2 (ja) | 1995-04-14 | 2003-05-23 | 可変長符号化方法及び装置 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JP3866687B2 (ja) |
-
2003
- 2003-05-23 JP JP2003146489A patent/JP3866687B2/ja not_active Expired - Lifetime
Also Published As
| Publication number | Publication date |
|---|---|
| JP2004048723A (ja) | 2004-02-12 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| EP0732855B1 (en) | Moving picture variable length coding system and method | |
| JP3431368B2 (ja) | 可変長符号化／復号化方法及び可変長符号化／復号化装置 | |
| JP3609814B2 (ja) | 可変長復号化方法及び装置 | |
| JP3766426B2 (ja) | 可変長符号化方法及び装置 | |
| JP3866687B2 (ja) | 可変長符号化方法及び装置 | |
| JP3609813B2 (ja) | 可変長符号化方法及び装置 | |
| JP3748215B2 (ja) | 可変長符号化方法及び装置 | |
| JP3944049B2 (ja) | 可変長復号化方法及び装置 | |
| JP3764466B2 (ja) | 可変長復号化方法及び装置 | |
| JP3612314B2 (ja) | 可変長符号化方法及び装置 | |
| JP3869342B2 (ja) | 可変長復号化方法及び装置 | |
| JP3822630B2 (ja) | 可変長復号化方法及び装置 | |
| JP3612315B2 (ja) | 可変長復号化方法及び装置 | |
| JP3822629B2 (ja) | 可変長符号化方法及び装置 | |
| JP3579409B2 (ja) | 可変長符号化方法及び装置 | |
| JP3579410B2 (ja) | 可変長符号化方法及び装置 | |
| JP3579411B2 (ja) | 可変長符号化方法及び装置 | |
| JP3579412B2 (ja) | 可変長復号化方法及び装置 | |
| JP3417933B2 (ja) | 可変長復号化方法及び装置 | |
| JP3417934B2 (ja) | 可変長符号化方法及び装置 | |
| JP3233360B2 (ja) | 可変長復号化方法及び装置 | |
| JP3164806B2 (ja) | 可変長符号化方法及び装置 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20040720 |
|
| A521 | Written amendment |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20040921 |
|
| A02 | Decision of refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A02 Effective date: 20041019 |
|
| A61 | First payment of annual fees (during grant procedure) |
Free format text: JAPANESE INTERMEDIATE CODE: A61 Effective date: 20061005 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20101013 Year of fee payment: 4 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20111013 Year of fee payment: 5 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20111013 Year of fee payment: 5 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20121013 Year of fee payment: 6 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20131013 Year of fee payment: 7 |
|
| EXPY | Cancellation because of completion of term |