JPH03503351A - 可変長のコード化語の順序に従って同期語を認識するためのコード化方法 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるため要約のデータは記録されません。

Description

【発明の詳細な説明】 可変長のコード化語の順序に従って同期語を認識するためのコード化方法 本発明は、可変長のコード化語の順序に従って同期語を認識するための方法に係 る。本発明は特に流れ速度圧縮方式の構成に適用される。

流れ速度制限情報を送信機とディジタルテレビ受像機の間で伝送するためには、 しばしばハフマンの統計的コード化方法が援用される。しかしこの方法は制御で きない最大炎がコード化装置の構造を複雑化することになる可変長コード語の構 成を必要とする。他方ではコードは不平等長を持つから、コードが形成する２進 語はひずみを受ける恐れがあり、これが伝送誤差を引き起す。

これらの誤差の伝搬と影響を制限するため、誤差が生じた場合に受像機の同期を 保護するためブロック間に同期語を挿入することによって情報をブロックに分割 することが原則として必要である。この保護は異なる３つの方法により得ること ができる。第１の方法は伝送される情報の形式を無視し、伝送内で用いられた特 定数Ｎのビットの後に同期語を配置するというものである。この方法の興味深い 点は、ブロック長を固定し、同期語の位置を精密に決定している点にある。これ らの条件の下では、同期語を特に優先して保護するため自動修正型誤差コードを 用いることが可能である。第２の方法はＮ個のコード化事象の後に同期語を配置 することである。これらの条件の下では、同期化語の位置は知られてない。しか しＮ個の事象の後では常にブロック分離語が存在しなければならないから、誤差 検出の可能性が存在する。最後に第３の方法は、コード化事象数とブロック毎の ビット数輌≠が必ずしも知られていないコード化の実行である。これらの最後の ２つの場合では、誤差によって引き起こされる妨害を有効に位置決めするため同 期化語を保護するか又は少くとも認識することで優れている。しかし現行のコー ド修正器は同期化語の位置が知られていないときその保護をかなえてやることは できない。

従って本発明の目的はこの欠点を緩和することである。

このため本発明の主題は、可変長コード化語の順序に従って同期化語を認識する ためのコード化方法であって、各語コード井召イは出現の可能性を割当てられた 一連のメツセージからの特定メツセージ又は事象に対応し、この方法は２分法コ ード化木構造から成立しており、木の根から葉へ進むに従って減少していく順序 で分類された優先レベルをつけて分配された特定数の葉を含み、葉の数はコード 化されるべき事象数に等しく、本方法は葉を各レベルに互いに隣接させて並べ、 最も可能性の高い事象に対応する葉が各レベルの単一な右又は左端に配置される こと、さらにコード化語内では、ゼロ又は１の等しい値から成るＳ　ＩＩＩＩ　 ビットの順序を禁止することから成ることを特徴とする。

添付図面を参照した以下の説明から本発明はさらに良く理解され、またその他の 特徴も明らかとなるであろう。

第１Ａ、ＩＢ及びＩＣ図はビット列内に挿入された同期語の説明図、第２図は本 発明コード化アルゴリズム内に左完成コード化の木を生成した説明図、第３図は 左不完全の木構造の一例の説明図、第４図は２に等しいゼロの最大値を含む左完 全コード化の木の一例の説明図、第５図は従来形ハフマンコード化法の説明図、 第６図は本発明によって採用されたコード化法の説明図、第７図はコード化の深 さを制限することによって得られた本発明コード化方法の説明図、第８図は本発 明コード化方法を説明する流れ図、第９Ａ及び９Ｂ図は禁止された葉を置くとき 同期語の長さを制限するための先行コード化法の実施例の説明図である。

２進語の順序に従って同期語を位置決めするために用いられた従来法は、数個の 連続するビット列の重みを相互比較するというものであって、各ビット列は特定 ビット数を含んでいる。

この重みはビット列のすべての「１」ビットの合計によってビット列上で決定さ れるから、例えば同期語に対して「０」に等しい重みを与えたとき、この語は「 ０」より大きな重みを持つ他の列の間で完全に識別可能となる。

こうして第１Ａ図に示すビット列内で、ＭＳと名付けられて数個の「１」ビット を含むＣと名付けられた２列の間に挿入された６個のｒＯＪ　ｍビット列はその 重みがゼロであり、また語ＭＳの左及び右への列の重みはそれぞれ３と４である から完全に認識される。逆にもし誤差が、例えば語Ｃの左への星印を付けた位置 に起これば、語ＭＳは第１Ｂ図に示すような位置誤差を伴って認識される。同じ ことが語Ｃがゼロで終わるたびごとにあてはまる。これらの問題は第１Ｃ図に示 すように、例えば同期語ＭＳの末尾に「１」ビットを加えることで解決すること ができる。さらにこの解決法は、任意の数のＴの誤差についてあてはまる。この 場合に同期語の位置は、少なくともＴ＋１の「１」ビットを含むことを条件に確 実化されることができる。事実、同期語内のＴ＋１の「１」ビットの位置を長さ をも考慮することなく、同期語内でＴの「１」ビットが消去されるならば、語Ｍ Ｓの位置は残りの「１」が存在するおかげで、ＭＳ語が「０」に先行されても保 持されることが注目される。

ＭＳについての同期語の検索過程は列Ｑ及びＭＳの相乗積から得られる。例えば Ｚが同期語ＭＳ及び次のようなコード化語の列Ｑから変化することを考慮すれば 、 （但ＬＫ＝０．Ｉ　、−３−１１，：ツイテＱｋ　＝ＭＳｋ　）　Ｑ　（Ｚ）　 及びＭＳ　（Ｚ）の相乗積は関係式 によって表わされる。但し式中のＰｌは列Ｅｉ　と同期語ＭＳとの間のハミング 距離Ｄ（Ｅｉ　　・ＭＳ）であって、この距離は同期語の左又は右に位置する任 意のビット列と同期語自体との間の「排他的論理和ＯＲＪによって測定されるこ とができる。そこで同期語ＭＳは、もし予め定められたハミング距離Ｐｉだけの 存在内で識別されるだろう。これは式ＰｉをＴ＋ｌより大きいか等しく、ｊを０ より小さく満足するζうに同期語ＭＳ内に「１」ビットを挿入すれば充分である 。

しかしながら、符号化されるべき事象数が大きければ、ハフマンコード化法は、 数多くのコード語縦続が観測されなければならないから発見の困難な長い同期語 を使用することになる。

同期語の検索を単純化するための第１の解決法はハフマンコード化木構造中の０ 又は１列を禁止することである。しかし流速内コストはこの方法によって非常に 大きくなり得る。何故ならば制約が最も可能性の高い事象においても介入してく るからである。

本発明によって実施される解決法は同期語の選択を容易化し、第２図に示すよう に各々左完全又は右完全木構造の非制約発生を可能にするアルゴリズムを規定す るというものである。左完全本構造とは各レベルの葉がすべて隣り合う、即ち単 一レベル上の葉を分離するため中間節点が全く存在しない木である。第２図から 第３図では、葉（Ｆｌ・・・Ｆ４）は円によって表され、中間節点は点によって 表わされる。

本発明によれば同期語の長さを制限するため、５Ｉ１１！の「０」（それぞれＳ 　ｍｔｘの「１」）より大きい列はコード語内で禁止されている。例えば第４図 では、２個以上の引続く０午呻はコード化木構造内では禁止され、３個の「０」 は同期語については保存されている。こうしてＳ１ｔ＋ｌの「０」　（それぞれ Ｓｍｔｘ＋ｌの「１」）で終わる２進列のすべては禁止葉へ達する。禁止葉の一 例は第４図に三角形で示されている。先行アルゴリズムから同期語ＭＳに与えら れるべき長さの検索が一方で考慮されなければならず、Ｔ又はそれ以上の誤差の 存在内への語ＭＳの配置を確実にするため語はＴ＋１の「１」ビットを含有せね ばならない。他方では式［１）によって規定される「排他的論理和ＯＲＪ操作の 結果ＰＫの、同期語ＭＳをもつ長さＳの任意の列上で実行されるＴ＋１の「１」 ビットを語が含むべきことを考慮しなければならない。事実、誤差が無いことが 明らかであれば、結果ＰＫはゼロで、同期語は誤差無しに位置方向に認識される 。しかし、Ｔより小さいか又は等しいＶの誤差があれば、結果ＰＫはＴより小さ いか又は等しく、従ってＭＳはＶの誤差の存在で位置方向に認識される。従って ＭＳに関する（ｓｉＣ）　Ｃの列の最小／１ミング距離ＰＫ（Ｐａｉｎ）は少な くともＴの誤差の存在時にＴ＋１に等しくなければならない。もしＳビットの同 期語がせいぜいＴの誤差の存在を許容するならば、Ｓビットの任意の列上で多く てＴ１差があり、少くてＴの「１」ビットが列Ｃから消去されるであろう。Ｐ上 の結合寄与はＭＳｚＯについて、以下となる。

Ｐ町Ｐｍ１ｎ　＋Ｔ＋Ｄ＝２Ｔ＋１＋Ｄ実際同期語はＴ＋１の「１」ビットを含 むから、もし最悪の場合でも任意の列のＴ＋１の「１」ビットが同期語のＴ＋１ の１≠初ビツトと一致すれば、結果ＰＫへのこれらのビットの寄与はゼロである 。一般に、もしＣに属する任意列のＴの「１」ビットが同期語のＴ＋１の「１」 ビットのＢに多くても一致するならば、これらのビットの寄与はゼロである。こ れらを考慮すれば、Ｔの誤差に対して防護するためには長さＳの０列に対して与 えられるべき重みＰの決定ができる。この重みは次の式を介して決定される。

Ｐ　＝　Ｂ　＋　Ｔ　＋　１　＋　Ｔ　　　　　　　　　（２）但しＢはＴ＋１ より小さいか又は等しい。ＭＳ以外の任意のコード列の最大重みは従って３Ｔ＋ ２に等しい。従って、「１」の重みはコード化語内の俗語（ＳｌＩＩ＋１）ごと に発見されることが確実であると仮定すれば、同期語の全長を表わすＳの値は次 の式を満足する。

即ち、 ＳｍＰ、　　（Ｓｗｓｘ＋１）　　　　　　　　　（３）又は再び Ｓｍ　（３Ｔ＋２）６　（Ｓｍｉｔ　＋１）　　　　　　　（４）要約すれば、 同期語ＭＳは（３Ｔ＋２）（Ｓｍｓｘ　＋ｌ）に等しい長さＳを持ち、さらにＴ ＋１の１≠（ロ）ビットを持たなければならない。

左完全、右完全木構造をそれぞれ形成するため本発明の実施するアルゴリズムは 従来式ハフマン法から借用される。ハフマン法によれば、コード化すべきＮ事象 の各組はＮの２進語又はメツセージの１組内でコード化され、後者は第１コード 化メツージが常に最も可能性の高い事象に対応し、さらに最終メツセージＮが出 現の可能性の最も低い事象に対応するような番号付は方式を与えられている。１ からＮまでのメツセージはこうして次のような優先順位で分類される。

Ｐ（１）≧Ｐ（２）≧Ｐ（３）・・・≧Ｐ　（Ｎｌ　　　　　　　＋５１これら のアルゴリズムでは、コード化木構造は、空白であるか又は根によって、左すブ 木（Ｌ、　Ｓ、　Ｔ、　ｌと呼ばれる２進木構造によってか又は右すブ木（Ｒ， Ｓ、　Ｔ、　）と呼ばれる２進木構造によって形成されるかする２進構造を所有 している。

慣例によって、空白木は葉と同じである。左すブ木には０を割当てられた枝を横 切ることによって到達でき、右すブ木には１を割当てられた枝を横切ることによ って到達できる。この構造は２進木構造によってＮメツセージを表わすことを可 能にする。コードは根から出発して葉に到達するときまで木の枝を上に横切るこ とによって読出され、各葉はＮ事象から１事象を表わす。葉に到達することを可 能にする枝に割当てられたビット列はこうして対応する事象コードを形成する。

こうしてコード語Ｉの長さＬ（１）が（Ｉは１からＮの組の事象に属する）事象 に含まれるビット数によって決定されるならば、コードの平均長は以下の方程式 から得られる。即ち、そして次の不等式 ％式％（８） が満足されなければならない。

従来形ハフマン法は木の根の方へ戻るためには、葉から事象をコード化するとい うものである。ハフマンのアルゴリズムによれば、メツセージ又は葉のＮ個の可 能性は増加方向に分類され、そして２つの最低可能性は、これら２つの可能性の 合計を抱えた木の根を形成するため脇へ置かれる。残りのＮ−１の可能性はここ で増加方向に再び並べられ、次に先行の操作が実行中の選択の可能性の数がゼロ になるまで再度開始される。

こうして例えば次の出現可能性、０．１；０．１８；　　０．１．　０．１．［ １１巾；＃；　Ｇ、［１６；　０．０６；　０．Ｇ４；　０．０４；　Ｇ、０４ ；　０．０４；　０．０３；及び００１と、葉番号（１，２，・・・１３）とが それぞれ割当てられたメツセージＡ、Ｂ、Ｃ，Ｄ、Ｅ、Ｆ、Ｇ、Ｈ，Ｉ、Ｊ、に 、Ｌ。

Ｍのコード化が、前記アルゴリズムを用いることによって第５図に示す木構造を 与える。

しかしながら、コード化が葉から根への動きによって決定されるから、木の深さ は最低可能性語のビット数に一致する深さでもあり、後者が形成されるまでは知 られない。この事実はコード化及びデコード化にかなう低複雑性を得るためには 不利であるかもしれない。

本発明方法は、葉から根へ向かってコード化木構造を横切ることによってではな く、逆に葉の方へ下降するため根から出発することによって事象のコード化を可 能にする、後述するアルゴリズムを介してこの欠点を是正する。

「トップダウン」と呼ばれる第１の方法は、左（それぞれ右）完全木構造を構成 し、一方で毎回１からに−１までのメツセージの葉が水内に置かれることをチェ ックし、第６図に示すように深さＢに右へ（それぞれ左へ）できる限り遠くまで メツセージ葉Ｋを置き、そして深さＢ＋１の木の根又は葉の数Ｍは次の式によっ て決定される。即ち、 ハフマンのアルゴリズムにおいてのように、Ｋ＋１からに＋根に関しては可能性 の合計−一を持つ。左完全木構造を形成しようとする試みは、深さＢ＋１で可能 性の増加する方向に選択シュミレーションを実行するため降下する。

可能性はもし次の式（１０）が満足すれば選択されたと見なされるから、葉Ｆ　 （Ｋ）は正しい位置に置かれたと見なしてもよい。

逆の場合には、式 が満足すれば、可能性Ｐ　（Ｋ）を、葉に＋Ｍ−１及びに＋Ｍ−２の可能性Ｐ　 （Ｍ＋に−４）及びＰ　（Ｍ＋に−２）の合計と比較することが必要である。

もしＰ　（Ｍ＋に−１）　＋Ｐ　（Ｍ＋に−２）が可能性Ｐ　（Ｋ）（１２）よ り小さければ、葉Ｆ　（Ｋ）は位置に無゛く、メツセージにのコードの長さは１ だけ増やされなければならない。逆に、もしＰ　（Ｍ＋に−１）＋Ｐ　（Ｍ＋に −２）が可能性Ｐ　（Ｋ）　（１３）より大きいか又は等しいかであれば、唯一 の解決法は２本の木を構成し、第１の木では葉Ｆ　（Ｋ）をこの位置に置き、第 ２の木ではコード語にの長さが１だけ増やされるようにすることである。

次の操作は、もし葉Ｆ　（Ｋ）が正しい位置に置かれるとすれば、葉Ｆ　（Ｋ＋ １）を葉Ｆ　（Ｋ）と同じ深さＢに置こうと試みることである。しかしながら、 コード語にの長さが１だけ増やときまで再び実行される。２つの木は、構成され る場合には、葉が置かれるべき木が完成され、そして他の木の構成の続行に必要 な条件がスタックされる。

前記アルゴリズムの実施を可能ならしめる対応するプログラムは次の通りである 。

（初期設定位相が考慮されたか？） −葉ＦＫを置く 一１１＝ｔ＝＃ｔだけ増やされたメツセージにの長さくスタック条件） あるいは　　メツセージにの長さを１だけ増す（初期化位相終了） （木が未完成であれば処理が続行する）完了： 最良の木が保存され、最後のスタック条件に一致する木が構成される。スタック が空白であれば終了せよ。

先行アルゴリズムはコード化深さを制限することによって完成されることができ る。実際、ＰＨ１が最大許可コード化深さを示し、さらにもし事象Ｎの数が２Ｐ １１より小さいか又は等し＋ｉれば、深さＰｍＪｘを持つ最適水を発見すること が可能である。

この木を得るためには、メツセージ数字には１だけ増やされた長さを持つことを 強調すれば充分であり、もし順位Ｐｍｘｘで可能な葉の数が置かれるべき残りの メツセージ数Ｎ−により少なければ、変数Ｉ　＝Ｍ＋Ｋが置かれるべき葉数Ｎよ り少ないので、先行する制約は最も厳しい。この方法は、深さの厳密な制限に必 要な最少制約に対応し、さらに平均流速内の損失の最小化を可能にするから興味 深い。そこで深さＰ　ＩＩＩにおいて可能な葉数は次の式によって与えられる。

第８図の流れ図によって段階１から１８までが図解されている対応プログラムは 次の通りである。

（第１木の第１葉Ｆ１のための初期設定）すべての木がまだ構成されおらなけれ ば寒互：木が完成されていなければ実行。

（初期設定位相が考慮されたか？） −ＦＰＩＩＩ！の修正 一葉ＦＫを置く −ＦｐＨ１！の修正 一メッセージにの長さを１だけ増やす （スタック条件） コード語にの長さを１だけ増やす必要がある（初期設定位相の終了） −ＦＰｍ暑Ｉの修正 最良の木が残され、そして最後のスタック条件に一致する木が構成される。スタ ックが空白であれば終了せよ。

同期語のための検索によって課せられた制約の満足は、即ち木のＳ　ｗｔｘの「 ０」以上の列が禁止されそして禁止された葉が木に挿入されるならば、２次元表 に従って特定表現の助けをかりて行われることができ、表中では第１垂直寸法は 木のレベルを表わし、第２水平寸法は中間節点−葉及び禁止葉の分布を特徴づけ る。

第９Ａ図及び第９Ｂ図が示す通り、正数は木の中に横に並べられた葉の数、負数 は横に並べられた中間節点の数を表わし、さらに「０」の表示は禁止葉を特徴づ ける。各レベルの最後の要素は常に配置された最後の要素のアドレスを示すポイ ンタである。このポインタは積重ね条件に属する。これは不完全水の葉の脱落の 際、有用な葉の計算の続行を可能にする。もしＳｌが５ＩＤＥ！より小さく又は 等しい■の「０」　（それぞれ■の「１」）の列を表わすとすれば、「０」の列 上の条件を形成するため、アルゴリズムの実施の間じゆう現在のレベルＢ及び続 くレベルＢ＋１の列Ｓｌの値の組合せを知っていることが必要である。列Ｓｔは 「０」の列で、この上に葉、中間節点、禁止葉を置くことが試みられる。ＳＩＫ で表わされた木の「０」の列はこの中に数字にの現行葉を置くことが試みられ、 そして深さ制限にあわせて、ＳＩＫ、ＬＫ（現在コード語の長さ）及びｐＨｌ！ Ｉの関数としてＦＰｍａｘの変化を常時計算する必要がある。

そこで２つの関数が用いられる。第１の関数ＦＰ（ＳＩＫ。

ＬＫ、Ｐｍ＊ｘ）は、葉Ｋが置かれるべきとき、レベルＰＷｓ＊で可能な葉数内 で修正を計算する。葉１からに−１はすでに木の中に置かれている。第２の関数 ＰＮＰ　（Ｓ　ｒ　Ｋ、　　ＬＫ、　　Ｐｍ５ｘ）はレベルＰｍ１ｔにおいて可 能な葉数の修正を計算することを可能にする。葉１からに−１はすでに木の中に 置かれており、葉には１だけ増やされたその長さを見て置かれる。レベルＰ　Ｉ ＩＫの葉数の変化がもし必要であれば１回だけ計算され、対応する結果はアルゴ リズムの操作過程で数回用いられる。コード語数字Ｋが１だけ増やされたその長 さを見れば、現在レベルＢの禁止葉はもはや除去されることはできず、そしてそ れ（ｓｉｃ）はコードの平均長さ内の損失を分担し、しかしそれにもかかわらず 、誤差の検索のために役立つことができる。逆に、レベルＢ＋１における可能禁 止葉は削除される。事実、葉数に−１が置かれれば、０のＳｍｘｒ列上の同じレ ベルに葉数Ｋを置くことが試みられ、禁止葉は消失する。アルゴリズムの操作中 にすべての可能禁止葉が考慮されなければならない。

ＦＩＧ、ＩＡ ０１００ＨＩＯＩ　　００００００口０１００１ハフマンン入 ＦＩＧ、９Ａ 国際調査報告 −惰−−〜−一一−ｐｃｒ／Ｆ′Ｒ８９１００５２１国際調査報告　　　ＰＣＴ ／ＦＲ８９１００５２１

Claims (4)

【特許請求の範囲】
1. １．可変長コード化語の順序に従って同期語を認識するためのコード化方法であ って、各コード化語は出現の可能性をそれぞれ割当てられた一連のメッセージか らの特定メッセージ又は事象に対応し、この方法は２分法コード化木構造から成 立しており、木の根から葉へ進むに従って減少していく順序で分類された優先レ ベル（ｎ１…ｎ４）をつけて分配した特定数の葉（Ｆ１…Ｆ４）を含み、葉の数 はコード化されるべき事象数に等しく、本方法は、葉を各レベルに互いに隣接さ せて並べて最も可能性の高い事象に対応する葉が各レベルの単一な右又は左端に 配置されること、さらにコード化語内ではゼロ又は１の等しい値から成るＳｍａ ｘビット列を禁止することから成ることを特徴とする方法。
2. ２．同期語の長さがビット数Ｓｍａｘ＋１の（３Ｔ＋２）倍に等しいことを特徴 とするもので、Ｔは容認されるビット伝送誤差の最大数を表わす請求の範囲１に 記載の方法。
3. ３．葉Ｆ（Ｋ）をコード化木内の優先レベル（ｎｉ）の所定位置に配置するため に、その可能性Ｐ（Ｋ）を配置されるべき残りの葉の可能性の合計Ｓ ▲数式、化学式、表等があります▼ に比較すること、またもし可能性Ｐ（Ｋ）（ｓｉｃ）がＳより大きいか又は等 しいならばこの位置に葉Ｆ（Ｋ）を置くために、逆の場合でその可能性Ｐ（Ｋ） と、メッセージＫの長さを１だけ増やし、あるいはこの位置に葉ＦＫを保持する ため低い可能性レベルに位置決めされた葉Ｆ（Ｍ＋Ｋ−１）及びＦ（Ｍ＋Ｋ−２ ）の可能性の合計Ｐ（Ｍ＋Ｋ−１）＋Ｐ（Ｍ＋Ｋ−２）とを比較することから成 ることを特徴とする請求の範囲１または２に記載の方法。
4. ４．事象コードを木の根から出発することによって、さらに葉に出合うときまで 木の枝を横切ることによって事象コード読出すことから成ることを特徴とする請 求の範囲３に記載の方法。