可逆可変長符号化方式
【目的】 シンボルの生起確率に基づき、順逆両方向より瞬時復号可能な効率的可変長符号を生成する。
【構成】 入力部（１）より入力したシンボルとその生起確率に基づき、非可逆符号生成部（２）で一旦非可逆符号化し、該符号化により得た結果で、非対称形可逆可変長符号生成部（３）ではビットパターンが非対称形の可逆可変長符号を生成し、対称形可逆可変長符号生成部（４）ではビットパターンが対称形である可逆可変長符号を生成し、可逆可変長符号出力部（５）では、該生成符号のいずれか、若しくは両方を、逆順両方向より瞬時復号可能な可変長符号として出力する。
【構成】 入力部（１）より入力したシンボルとその生起確率に基づき、非可逆符号生成部（２）で一旦非可逆符号化し、該符号化により得た結果で、非対称形可逆可変長符号生成部（３）ではビットパターンが非対称形の可逆可変長符号を生成し、対称形可逆可変長符号生成部（４）ではビットパターンが対称形である可逆可変長符号を生成し、可逆可変長符号出力部（５）では、該生成符号のいずれか、若しくは両方を、逆順両方向より瞬時復号可能な可変長符号として出力する。
【発明の詳細な説明】
【産業上の利用分野】本発明は、情報を０と１のパターンとして符号化・伝送する画像・音声・データなどのデジタル通信に関する。
【従来の技術】従来、符号のプリフィックス条件（短い符号語が長い符号語の前の一部分［プリフィックス］と一致しない）及びサフィックス条件（短い符号語が長い符号語の後ろの一部分［サフィックス］と一致しない）を同時に満たし、順逆両方向より瞬時復号可能な符号の代表的なものとして、固定長符号とＢ２符号 [IWP CMTT/2, Revised version of Draft Report AD/CMTT:Digital Transmission of Component-Coded Television Signal at 30-34 Mbit/s and 45 Mbit/s. June 1989.]が挙げられる。固定長符号は、全ての符号語に対して等しいビット長を割り当てるため、順逆両方向に関して、符号語間の同期が確立される。固定長符号の例を表１、表２に示す。表１中P1は英語のアルファベット（シンボルS1）に対して、表２中P2は画像符号化におけるフレーム間動ベクトル（シンボルS2）に対しての各シンボルの生起確率である。C11 、C21 は、各々P1、P2に基づいた参照のための順方向のみから瞬時復号可能な可変長符号である。C12 、C22 は各々P1、P2に対する固定長符号である。一方、Ｂ２符号は、連続フラグビット（０が終端を１が連続を表す）と情報ビットの２ビットの組合わせを単位として構成される偶数ビット長の符号語から成る符号（図４参照）であるが、連続フラグビットが符号語の終端を表すため、逆方向からも瞬時（厳密には２ビット遅れの）復号が可能である。表１、表２中C13 、C23 は、各々P1、P2に対するＢ２符号である。
【表１】
【表２】
【課題を解決するための手段】本発明の特徴は、シンボルの生起確率に基づいてビット長を割り当てる可変長符号化方式において、入力されたシンボル及びシンボルの生起確率分布に基づき、該シンボルを一旦非可逆符号化し、該符号化により得た符号語、ビット長ベクトル及び前記シンボル、前記生起確率分布により対称形可逆可変長符号化、非対称形可逆可変長符号化し、該対称形可逆可変長符号、該非対称形可逆可変長符号いずれかまたは両者を順逆両方向より瞬時復号可能な可逆可変長符号として用いる可逆可変長符号化方式にある。上記構成により、シンボルの生起確率に基づいてビット長を割り当てる可変長符号において、短い符号語がより長い符号語のプリフィックスと一致せず、同時に短い符号語が、より長い符号語のサフィックスとも一致しない、順逆両方向より瞬時復号可能な可逆可変長符号を生成することができる。
【実施例】図１は、本発明による可逆可変長符号生成方式の構成図であり、1 はシンボル及び生起確率の入力部、2 は生起確率に基づいて、平均符号長の短い順方向のみから瞬時復号可能な符号（例えばハフマン符号[D. Huffman, "A method for theconstruction of minimum redundancy codes," in Proc. Inst. Radio Eng., vol. 40, pp.1098-1101, Sept. 1952.]）を生成する非可逆符号生成部、3 は全ての符号語が対称な０、１パターンを持つ対称形可逆可変長符号生成部、4 は符号語の０、１パターンが非対称な非対称形可逆可変長符号生成部、5 は可逆可変長符号の出力部である。対称形可逆可変長符号生成部3 は、さらに図２に示される構成を持つ。6 はビット長ベクトル検査部であり、7 はビット長ベクトル変更部、8 は対称符号語割り当て部である。 一方、非対称形可逆可変長符号生成部4 は、図３に示される構成を持つ。9 は平均符号長を保存しながら、０と１のパターンを変更する等価変換部、10は逆方向からの復号を行う符号を作成するための逆木作成部、11は逆方向からの瞬時復号性を検査するためのサフィックス検査部、12は逆方向からの瞬時復号性を実現するためのビット付加部、13は生起確率の順に短い符号語から割り当てを行うソーティング部である。以上の構成に基づき、本発明は以下のように動作する。（表３に示すシンボルS3ならびに生起確率P3を例に説明する。）
【表３】
入力部1 では、信号源のシンボルならびにその生起確率が入力される。非可逆符号生成部2 では、シンボルの生起確率分布を基に平均符号長の短い順方向のみから瞬時復号可能な符号C31 ならびにそのビット長ベクトルBLV3（表４）を生成する。ビット長ベクトルBLV3は可変長符号の符号語の数をビット長ごとに表現したものである。シンボル（S3）、生起確率（P3）、非可逆可変長符号（C31 ）、ビット長ベクトル（BLV3）は、対称形可逆可変長符号生成部3 および非対称形可逆可変長符号生成部4 に送られ、各々で可逆可変長符号C32 、C34 を生成する。出力部5 では、用途に応じて、生成された符号C32 またはC34 あるいは両方を出力する。
【表４】
対称形可逆可変長符号生成部3 では、以下のようにして符号C32 が生成される。ビット長ベクトル検査部6 において、まず目的の可逆可変長符号のビット長ベクトルを非可逆可変長符号のビット長ベクトルで初期化する。
ｎrev(i)＝ ｎ(i) −(1) 但し、ｎ(i) : 非可逆符号のビット長ベクトル中で、長さi ビットの符号語の数ｎrev(i): 可逆符号のビット長ベクトル中で、長さi ビットの符号語の数次に、短いビット長から順に、ビット長ベクトルの要素ｎrev(i)が下の条件式を満たすか検査する。ビット長i の符号語（シンボルについて）、
【数１】
式(2) が満たされた場合、対称符号語割り当て部8 において、ビット長がi のシンボル全てに対して、０と１のパターンが対称な符号語を順に割り当てる。（対称な符号語の分布は、図５の通り。順にプリフィックス条件を満たしながら、符号語を割り当てる。）一方、式(2) が満たされない場合、i ビットで割り当てられないシンボルはビット長を１増やし、それに伴い、ビット長ベクトル変更部7 においてビット長ベクトルを変更する。すなわち、 ｎrev(i+1) ＝ ｎrev(i+1) ＋ ｎrev(i) − ｍ(i) −(6) ｎrev(i) ＝ ｍ(i) −(7) とし、ｎrev(i)個のビット長i のシンボルに対して、対称符号語割り当て部8 において対称な符号語を割り当てる。ビット長i+1 のシンボルに関し、再びビット長ベクトル検査部6 で検査を行い、以後同様の処理を繰り返す。全てのシンボルに符号語が割り当てられたら、出力部5 へ符号C32 を出力する。一方、非対称形可逆可変長符号生成部4 では、以下のようにして符号が生成される。非可逆符号生成部2 より得られた符号C31 に関して、長い符号語のサフィックスがより短い符号語になるべく一致しないように、平均符号長を変化させずに０と１のパターンを変更する等価変換（図６参照）を反復的に等価変換部9 で行う。等価変換は符号の木表現上で同じレベルにあるノードまたはリーフを交換する処理である。サフィックスの一致を減らすことにより、後述のように逆木作成過程において、付加ビットの量を減らすことができる。こうして得られた符号C33 に対し、短い符号語より順に逆木作成部10で逆方向から復号を行うための逆木が作成される（図７参照）。符号を２分木で表現することにより、プリフィックス条件の満足性が明確となるが、サフィックス条件の満足性について確認を行うため、逆方向に伸びる逆木を作成することが有効となる。すなわち、順方向木におけるリーフ（図７(a) の□印）をルートに置き、上方へ伸びる木を作成する（図７(b) 、(c) 、(d) ）。ここで、サフィックス検査部11において、サフィックスが、すでに逆木に割り当てられた、より短い符号語と一致した場合（図７において、ＤのサフィックスがＣと一致）、逆木への割り当てをいったん中止し、同じビット長の他の符号語を先に逆木へ割り当てる（図７(e) ）。同じビット長の他の符号語の割り当てが全て終了した後（Ｅの割り当て終了後）、ビット付加部12にて割り当てが中止された符号語（Ｄ）の末尾に必要最小限のビットを付加し、サフィックスが他の短い符号語と一致しないように逆木に割り当てる（図７(f) ）。ここで、サフィックスへのビットの付加は、プリフィックス条件には影響を与えない。同じビット長の符号語が全て割り当てられたら、次に長い符号語の割り当てを逆木作成部10で行い、これを繰り返す。全ての符号語が作成された後、ソーティング部13で生起確率の高いシンボルより、順に短い符号語を再び割り当て（図７(f) ）、出力部5 へ符号C34 を出力する。
【発明の効果】以上のように本発明は、シンボルの生起確率を考慮して、対称形ならびに非対称形の可逆可変長符号を生成することにより、従来より平均符号長の短い符号を得ることができる。この効果を確認するため、表１、２にS1、P1ならびにS2、P2に対する対称形可逆可変長符号（C14 、C24 ）及び、非対称形可逆可変長符号（C15 、C25 ）を従来の符号とならべて示す。尚、対称形可逆可変長符号は、順逆両方向とも同一のコードテーブルを使用することが可能なため、メモリの節約、復号処理の簡素化が実現でき、一方非対称形可逆可変長符号は、一層平均符号長が短く、高い伝送効率を実現する。
【図面の簡単な説明】
【図１】本発明の全体構成図
【図２】本発明中、対称形可逆可変長符号生成部の構成図
【図３】本発明中、非対称形可逆可変長符号生成部の構成図
【図４】従来方式のＢ２符号の構成
【図５】本発明中、符号の木表現での対称な符号語の分布
【図６】本発明中、等価変換の基本原理
【図７】本発明中、逆木作成の過程
【符号の説明】
1 シンボル、生起確率の入力部
2 非可逆符号生成部
3 対称形可逆可変長符号生成部
4 非対称形可逆可変長符号生成部
5 可逆可変長符号出力部
6 ビット長ベクトル検査部
7 ビット長ベクトル変更部
8 対称符号語割当部
9 等価変換部
10 逆木作成部
11 サフィックス検査部
12 ビット付加部 13 ソーティング部
【産業上の利用分野】本発明は、情報を０と１のパターンとして符号化・伝送する画像・音声・データなどのデジタル通信に関する。
【従来の技術】従来、符号のプリフィックス条件（短い符号語が長い符号語の前の一部分［プリフィックス］と一致しない）及びサフィックス条件（短い符号語が長い符号語の後ろの一部分［サフィックス］と一致しない）を同時に満たし、順逆両方向より瞬時復号可能な符号の代表的なものとして、固定長符号とＢ２符号 [IWP CMTT/2, Revised version of Draft Report AD/CMTT:Digital Transmission of Component-Coded Television Signal at 30-34 Mbit/s and 45 Mbit/s. June 1989.]が挙げられる。固定長符号は、全ての符号語に対して等しいビット長を割り当てるため、順逆両方向に関して、符号語間の同期が確立される。固定長符号の例を表１、表２に示す。表１中P1は英語のアルファベット（シンボルS1）に対して、表２中P2は画像符号化におけるフレーム間動ベクトル（シンボルS2）に対しての各シンボルの生起確率である。C11 、C21 は、各々P1、P2に基づいた参照のための順方向のみから瞬時復号可能な可変長符号である。C12 、C22 は各々P1、P2に対する固定長符号である。一方、Ｂ２符号は、連続フラグビット（０が終端を１が連続を表す）と情報ビットの２ビットの組合わせを単位として構成される偶数ビット長の符号語から成る符号（図４参照）であるが、連続フラグビットが符号語の終端を表すため、逆方向からも瞬時（厳密には２ビット遅れの）復号が可能である。表１、表２中C13 、C23 は、各々P1、P2に対するＢ２符号である。
【表１】
【表２】
【課題を解決するための手段】本発明の特徴は、シンボルの生起確率に基づいてビット長を割り当てる可変長符号化方式において、入力されたシンボル及びシンボルの生起確率分布に基づき、該シンボルを一旦非可逆符号化し、該符号化により得た符号語、ビット長ベクトル及び前記シンボル、前記生起確率分布により対称形可逆可変長符号化、非対称形可逆可変長符号化し、該対称形可逆可変長符号、該非対称形可逆可変長符号いずれかまたは両者を順逆両方向より瞬時復号可能な可逆可変長符号として用いる可逆可変長符号化方式にある。上記構成により、シンボルの生起確率に基づいてビット長を割り当てる可変長符号において、短い符号語がより長い符号語のプリフィックスと一致せず、同時に短い符号語が、より長い符号語のサフィックスとも一致しない、順逆両方向より瞬時復号可能な可逆可変長符号を生成することができる。
【実施例】図１は、本発明による可逆可変長符号生成方式の構成図であり、1 はシンボル及び生起確率の入力部、2 は生起確率に基づいて、平均符号長の短い順方向のみから瞬時復号可能な符号（例えばハフマン符号[D. Huffman, "A method for theconstruction of minimum redundancy codes," in Proc. Inst. Radio Eng., vol. 40, pp.1098-1101, Sept. 1952.]）を生成する非可逆符号生成部、3 は全ての符号語が対称な０、１パターンを持つ対称形可逆可変長符号生成部、4 は符号語の０、１パターンが非対称な非対称形可逆可変長符号生成部、5 は可逆可変長符号の出力部である。対称形可逆可変長符号生成部3 は、さらに図２に示される構成を持つ。6 はビット長ベクトル検査部であり、7 はビット長ベクトル変更部、8 は対称符号語割り当て部である。 一方、非対称形可逆可変長符号生成部4 は、図３に示される構成を持つ。9 は平均符号長を保存しながら、０と１のパターンを変更する等価変換部、10は逆方向からの復号を行う符号を作成するための逆木作成部、11は逆方向からの瞬時復号性を検査するためのサフィックス検査部、12は逆方向からの瞬時復号性を実現するためのビット付加部、13は生起確率の順に短い符号語から割り当てを行うソーティング部である。以上の構成に基づき、本発明は以下のように動作する。（表３に示すシンボルS3ならびに生起確率P3を例に説明する。）
【表３】
入力部1 では、信号源のシンボルならびにその生起確率が入力される。非可逆符号生成部2 では、シンボルの生起確率分布を基に平均符号長の短い順方向のみから瞬時復号可能な符号C31 ならびにそのビット長ベクトルBLV3（表４）を生成する。ビット長ベクトルBLV3は可変長符号の符号語の数をビット長ごとに表現したものである。シンボル（S3）、生起確率（P3）、非可逆可変長符号（C31 ）、ビット長ベクトル（BLV3）は、対称形可逆可変長符号生成部3 および非対称形可逆可変長符号生成部4 に送られ、各々で可逆可変長符号C32 、C34 を生成する。出力部5 では、用途に応じて、生成された符号C32 またはC34 あるいは両方を出力する。
【表４】
対称形可逆可変長符号生成部3 では、以下のようにして符号C32 が生成される。ビット長ベクトル検査部6 において、まず目的の可逆可変長符号のビット長ベクトルを非可逆可変長符号のビット長ベクトルで初期化する。
ｎrev(i)＝ ｎ(i) −(1) 但し、ｎ(i) : 非可逆符号のビット長ベクトル中で、長さi ビットの符号語の数ｎrev(i): 可逆符号のビット長ベクトル中で、長さi ビットの符号語の数次に、短いビット長から順に、ビット長ベクトルの要素ｎrev(i)が下の条件式を満たすか検査する。ビット長i の符号語（シンボルについて）、
【数１】
式(2) が満たされた場合、対称符号語割り当て部8 において、ビット長がi のシンボル全てに対して、０と１のパターンが対称な符号語を順に割り当てる。（対称な符号語の分布は、図５の通り。順にプリフィックス条件を満たしながら、符号語を割り当てる。）一方、式(2) が満たされない場合、i ビットで割り当てられないシンボルはビット長を１増やし、それに伴い、ビット長ベクトル変更部7 においてビット長ベクトルを変更する。すなわち、 ｎrev(i+1) ＝ ｎrev(i+1) ＋ ｎrev(i) − ｍ(i) −(6) ｎrev(i) ＝ ｍ(i) −(7) とし、ｎrev(i)個のビット長i のシンボルに対して、対称符号語割り当て部8 において対称な符号語を割り当てる。ビット長i+1 のシンボルに関し、再びビット長ベクトル検査部6 で検査を行い、以後同様の処理を繰り返す。全てのシンボルに符号語が割り当てられたら、出力部5 へ符号C32 を出力する。一方、非対称形可逆可変長符号生成部4 では、以下のようにして符号が生成される。非可逆符号生成部2 より得られた符号C31 に関して、長い符号語のサフィックスがより短い符号語になるべく一致しないように、平均符号長を変化させずに０と１のパターンを変更する等価変換（図６参照）を反復的に等価変換部9 で行う。等価変換は符号の木表現上で同じレベルにあるノードまたはリーフを交換する処理である。サフィックスの一致を減らすことにより、後述のように逆木作成過程において、付加ビットの量を減らすことができる。こうして得られた符号C33 に対し、短い符号語より順に逆木作成部10で逆方向から復号を行うための逆木が作成される（図７参照）。符号を２分木で表現することにより、プリフィックス条件の満足性が明確となるが、サフィックス条件の満足性について確認を行うため、逆方向に伸びる逆木を作成することが有効となる。すなわち、順方向木におけるリーフ（図７(a) の□印）をルートに置き、上方へ伸びる木を作成する（図７(b) 、(c) 、(d) ）。ここで、サフィックス検査部11において、サフィックスが、すでに逆木に割り当てられた、より短い符号語と一致した場合（図７において、ＤのサフィックスがＣと一致）、逆木への割り当てをいったん中止し、同じビット長の他の符号語を先に逆木へ割り当てる（図７(e) ）。同じビット長の他の符号語の割り当てが全て終了した後（Ｅの割り当て終了後）、ビット付加部12にて割り当てが中止された符号語（Ｄ）の末尾に必要最小限のビットを付加し、サフィックスが他の短い符号語と一致しないように逆木に割り当てる（図７(f) ）。ここで、サフィックスへのビットの付加は、プリフィックス条件には影響を与えない。同じビット長の符号語が全て割り当てられたら、次に長い符号語の割り当てを逆木作成部10で行い、これを繰り返す。全ての符号語が作成された後、ソーティング部13で生起確率の高いシンボルより、順に短い符号語を再び割り当て（図７(f) ）、出力部5 へ符号C34 を出力する。
【発明の効果】以上のように本発明は、シンボルの生起確率を考慮して、対称形ならびに非対称形の可逆可変長符号を生成することにより、従来より平均符号長の短い符号を得ることができる。この効果を確認するため、表１、２にS1、P1ならびにS2、P2に対する対称形可逆可変長符号（C14 、C24 ）及び、非対称形可逆可変長符号（C15 、C25 ）を従来の符号とならべて示す。尚、対称形可逆可変長符号は、順逆両方向とも同一のコードテーブルを使用することが可能なため、メモリの節約、復号処理の簡素化が実現でき、一方非対称形可逆可変長符号は、一層平均符号長が短く、高い伝送効率を実現する。
【図面の簡単な説明】
【図１】本発明の全体構成図
【図２】本発明中、対称形可逆可変長符号生成部の構成図
【図３】本発明中、非対称形可逆可変長符号生成部の構成図
【図４】従来方式のＢ２符号の構成
【図５】本発明中、符号の木表現での対称な符号語の分布
【図６】本発明中、等価変換の基本原理
【図７】本発明中、逆木作成の過程
【符号の説明】
1 シンボル、生起確率の入力部
2 非可逆符号生成部
3 対称形可逆可変長符号生成部
4 非対称形可逆可変長符号生成部
5 可逆可変長符号出力部
6 ビット長ベクトル検査部
7 ビット長ベクトル変更部
8 対称符号語割当部
9 等価変換部
10 逆木作成部
11 サフィックス検査部
12 ビット付加部 13 ソーティング部
【特許請求の範囲】
【請求項１】 シンボルの生起確率に基づいてビット長を割り当てる可変長符号化方式において、入力されたシンボル及びシンボルの生起確率分布に基づき、該シンボルを一旦非可逆符号化し、該符号化により得た符号語、ビット長ベクトル及び前記シンボル、前記生起確率分布により対称形可逆可変長符号化、非対称形可逆可変長符号化し、該対称形可逆可変長符号、該非対称形可逆可変長符号いずれかまたは両者を順逆両方向より瞬時復号可能な可逆可変長符号として用いることを特徴とする可逆可変長符号化方式。
【請求項２】 自符号語が自符号語より長い符号語のサフィックスと一致しないように、順方向より瞬時復号可能な可変長符号の符号語の末尾にビットを付加することにより生成されることを特徴とする請求項１記載の非対称形可逆可変長符号化方式。
【請求項３】 全ての符号語が、０と１の対称なビットパターンにより構成されることを特徴とする請求項１記載の対称形可逆可変長符号化方式。
【請求項１】 シンボルの生起確率に基づいてビット長を割り当てる可変長符号化方式において、入力されたシンボル及びシンボルの生起確率分布に基づき、該シンボルを一旦非可逆符号化し、該符号化により得た符号語、ビット長ベクトル及び前記シンボル、前記生起確率分布により対称形可逆可変長符号化、非対称形可逆可変長符号化し、該対称形可逆可変長符号、該非対称形可逆可変長符号いずれかまたは両者を順逆両方向より瞬時復号可能な可逆可変長符号として用いることを特徴とする可逆可変長符号化方式。
【請求項２】 自符号語が自符号語より長い符号語のサフィックスと一致しないように、順方向より瞬時復号可能な可変長符号の符号語の末尾にビットを付加することにより生成されることを特徴とする請求項１記載の非対称形可逆可変長符号化方式。
【請求項３】 全ての符号語が、０と１の対称なビットパターンにより構成されることを特徴とする請求項１記載の対称形可逆可変長符号化方式。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【公開番号】特開平５−３０００２７
【公開日】平成５年（１９９３）１１月１２日
【国際特許分類】
【出願番号】特願平４−１２２８２２
【出願日】平成４年（１９９２）４月１７日
【出願人】（０００００１２１４）国際電信電話株式会社 (10)
【公開日】平成５年（１９９３）１１月１２日
【国際特許分類】
【出願日】平成４年（１９９２）４月１７日
【出願人】（０００００１２１４）国際電信電話株式会社 (10)
[ Back to top ]