(57)【要約】本発明は、可変長誤り訂正（ＶＬＥＣ）符号技術に関し、その主要なステップは、必要なすべてのパラメータを確定し、固定長Ｌ１を有するコードを生成し、取得された集合Ｗにコードワードから最小発散距離ｄ［ｍｉｎ］の距離の可能なすべてのＬ１項を格納し（取得された新たな集合が空でない場合、１ビットの追加ビットがすべてのワードの終わりに付加される）、すべてのコードワードにより距離基準を満足しないＷのすべてのワードを削除し、最終的な集合Ｗのすべてのワードが他の距離基準を満たすことを検証することからなる。良好なコードの大部分が長さのジャンプを持たないと仮定すると、本発明による方法は、チェックされたＶＬＥＣコードの集合を減らすことができる。この仮説に従って、ｎｏ  ｈｏｌｅ最適化と呼ばれる新たな生成方法が規定され、集合Ｗの各ワードの終わりに１より大きなビットを追加することが回避される。この新たなアルゴリズムは、可能性の低い符号構成を考慮しないことにより、複雑さにおいて効果を得ることができる。
2006504316.tif 000002
【特許請求の範囲】
【請求項１】
可変長誤り符号を生成する方法であって、
（１）コードワードの最小長Ｌ１及び最大長Ｌｍａｘと、ＶＬＥＣコードＣに対する任意の拡張されたコードすべての集合における最小ハミング距離である各コードワード間のフリー距離ｄｆｒｅｅと、必要数のコードワードＳからなる必要とされるパラメータを初期化するステップと、
（２）長さＬ１と最小距離ｂｍｉｎ（ここで、ｂｍｉｎ＝ｍｉｎ｛ｂｋ；ｋ＝１，２，．．．，Ｒ｝、ｂｋはコードＣのコードワード長Ｌｋに関する距離であり、長さＬｋを有するＣのすべてのコードワード間の最小ハミング距離として定義され、ＲはＣにおける相異なるコードワード長の個数である）の固定長コードＣを生成し、距離ｄのｎビット長ワードの集合を生成するステップと、
（３）前記Ｃのコードワードからｄｍｉｎ（ｄｍｉｎは、ＶＬＥＣコードＣに対し、Ｃの相異なる長さのコードワードのすべての可能なペア間のすべての発散距離の最小値である）の距離におけるすべての可能なＬ１項を列挙し、前記集合Ｗに格納し、該集合Ｗが空でない場合、すべてのワードの終わりに１ビットを付加することによりＷのワード数を２倍にし、前記集合Ｗを以前のワードの２倍のワード数と前記ワードの各々の長さがＬ１＋１である新たな集合と置換するステップと、
（４）ＣのすべてのコードワードによるコードＣの最小収束距離であるｃｍｉｎを満足しない前記集合Ｗのすべてのワードを削除するステップと、
（５）ワードが検出されない場合、あるいは最大ビット数に達した場合、さらなるワードを検出するため距離の制約を軽減するステップと、
（６）前記集合Ｗのすべてのワードがｂｍｉｎの距離となるよう制御し、前記検出されたワードを前記コードＣに追加するステップと、
（７）コードワードの必要数に達しない場合、さらに継続する可能性がなくなるまで、またはコードワードの必要数が検出されるまで、前記ステップ（１）〜（６）を繰り返すステップと、
（８）Ｃのコードワード数がＳより多い場合、前記ＶＬＥＣコードの構成に基づき、前記ソースの確率により各コードワード長を重み付けすることにより取得される平均長ＡＬを計算し、該ＡＬがＡＬｍｉｎ（ＡＬｍｉｎは、ＡＬの最小値である）より小さい場合、前記ＡＬを前記ＡＬｍｉｎとし、対応するコード構成をメモリに保持するステップと、
を有し、
該生成方法はさらに、高々１ビットが前記集合Ｗの各ワードの終わりに追加されることを特徴とする方法。
【請求項２】
請求項１記載の可変長誤り符号を生成する方法を実行するための装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、可変長誤り符号を生成する方法に関し、該方法は  （１）コードワードの最小長Ｌ１及び最大長Ｌｍａｘと、ＶＬＥＣコードＣに対する任意の拡張されたコードすべての集合における最小ハミング距離である各コードワード間のフリー距離ｄｆｒｅｅと、必要数のコードワードＳからなる必要とされるパラメータを初期化するステップと、
（２）長さＬ１と最小距離ｂｍｉｎ（ここで、ｂｍｉｎ＝ｍｉｎ｛ｂｋ；ｋ＝１，２，．．．，Ｒ｝、ｂｋはコードＣのコードワード長Ｌｋに関する距離であり、長さＬｋを有するＣのすべてのコードワード間の最小ハミング距離として定義され、ＲはＣにおける相異なるコードワード長の個数である）の固定長コードＣを生成し、距離ｄのｎビット長ワードの集合を生成するステップと、
（３）前記Ｃのコードワードからｄｍｉｎ（ｄｍｉｎは、ＶＬＥＣコードＣに対し、Ｃの相異なる長さのコードワードのすべての可能なペア間のすべての発散距離の最小値である）の距離におけるすべての可能なＬ１項を列挙し、前記集合Ｗに格納し、該集合Ｗが空でない場合、すべてのワードの終わりに１ビットを付加することによりＷのワード数を２倍にし、前記集合Ｗを以前のワードの２倍のワード数と前記ワードの各々の長さがＬ１＋１である新たな集合と置換するステップと、
（４）ＣのすべてのコードワードによるコードＣの最小収束距離であるｃｍｉｎを満足しない前記集合Ｗのすべてのワードを削除するステップと、
（５）ワードが検出されない場合、あるいは最大ビット数に達した場合、さらなるワードを検出するため距離の制約を軽減するステップと、
（６）前記集合Ｗのすべてのワードがｂｍｉｎの距離となるよう制御し、前記検出されたワードを前記コードＣに追加するステップと、
（７）コードワードの必要数に達しない場合、さらに継続する可能性がなくなるまで、またはコードワードの必要数が検出されるまで、前記ステップ（１）〜（６）を繰り返すステップと、
（８）Ｃのコードワード数がＳより多い場合、前記ＶＬＥＣコードの構成に基づき、前記ソースの確率により各コードワード長を重み付けすることにより取得される平均長ＡＬを計算し、該ＡＬがＡＬｍｉｎ（ＡＬｍｉｎは、ＡＬの最小値である）より小さい場合、前記ＡＬを前記ＡＬｍｉｎとし、対応するコード構成をメモリに保持するステップと、
を有し、
該生成方法はさらに、高々１ビットが前記集合Ｗの各ワードの終わりに追加されることを特徴とする方法に関する。
【背景技術】
【０００２】
図１に示される従来の通信系列は、ソースＳから入力される信号を符号化するのに、ソースコーダ１（ＳＣＯＤ）と、それに後続するチャネルコーダ２（ＣＣＯＤ）と、チャネル３を開始取得される符号化信号の送信後のため、チャネルデコーダ４（ＣＤＥＣ）とソースデコーダ５（ＳＤＥＣ）とを有する。復号化信号は、受信機に送信される。従来、可変長符号（ＶＬＣ）は、その圧縮機能のためソース符号化において利用され、関連するチャネル符号化技術が実際の送信チャネルの効果（フェーディングやノイズなど）に対抗してきた。しかしながら、ソース符号化は冗長さを取り除くためのものであり、それを再導入するためのチャネル符号化であるため、複雑さを許容されるレベルに維持しながらシステム全体を向上させるために、上記技術を効率的に組み合わせる方法が研究されてきた。
【０００３】
このようなアプローチにおいて提案される解決策の中で、可変長誤り訂正（ＶＬＥＣ）符号は、誤り訂正機能を与えながら、可変長である効果を提供するものであるが、これらの符号の生成は、短いアルファベットに対してでさえ時間のかかる作業であり（また、より長いアルファベットソースに対してはかなり時間のかかるものとなる）、以下に示されるように、この生成の複雑さが欠点となる。
【０００４】
まず、従来のＶＬＣの定義及び性質を説明する必要がある。コードＣは、Ｓ個のコードワードの集合｛ｃ１，ｃ２，ｃ３，．．．，ｃｉ，．．．，ｃＳ｝であり、各コードワードに対し、長さｌｉ＝｜ｃｉ｜が定義される。ここで一般性を失うことなく、ｌ１≦ｌ２≦ｌ３≦．．．≦ｌｉ≦．．．≦ｌＳとすることができる。コードＣの相異なるコードワード長の個数はＲと定義される。このとき、Ｒ≦Ｓとなるのは明らかであろう。これらの長さは、Ｌ１，Ｌ２，Ｌ３，．．．，Ｌｉ，．．．，ＬＲと記され、Ｌ１＜Ｌ２＜Ｌ３．．．＜ＬＲとなる。このとき、可変長符号、すなわちＶＬＣは、（ｓ１＠Ｌ１，ｓ２＠Ｌ２，ｓ３＠Ｌ３，．．．，ｓＲ＠ＬＲ）により記される構成であり、これは、長さＬ１のｓ１コードワード、長さＬ２のｓ２コードワード、長さＬ３のｓ３コードワード、．．．、及び長さＬＲのｓＲコードワードに対応する。ＶＬＣを用いるとき、所与のソースに対する圧縮効率は、当該ソースからシンボルを送信するのに必要とされるビット数に関連する。この効率性を推定するのに利用される測度は、しばしばコードの平均長ＡＬ（すなわち、ワードを送信するのに必要とされる平均ビット数）であり、各シンボルａｉがコードワードｃｉにマッピングされるとき、この平均長は以下の式（１）により与えられる。
【０００５】
【数１】
2006504316.tif 000003
上記式は式（２）に等しい。
【０００６】
【数２】
2006504316.tif 000004
ただし、データソースＡに対し、Ｓ個のソースシンボルが｛ａ１，ａ２，ａ３，．．．，ａＳ｝により記され、Ｐ（ａｉ）は上記シンボルの各々の出現確率である（ここで、ΣＰ（ａｉ）＝１）。ＡＬｍｉｎが平均長ＡＬの最小値を表すとすると、ＡＬｍｉｎとなるとき、上記シンボルは、Ｐ（ａ１）≧Ｐ（ａ２）≧Ｐ（ａ３）≧．．．≧Ｐ（ａｉ）≧．．．≧Ｐ（ａＳ）となることは容易にわかるであろう。受信機がこの符号化情報を復号することが可能となるように当該データを符号化するため、ＶＬＣは以下の性質を満足する必要がある。すなわち、非単一性（すべてのコードワードが相異なるものであり、複数のソースシンボルが１つのコードワードに割当てられない）と一意的復号可能性（すなわち、任意のコードワード文字列を誤りなく正しいソースシンボルに明確にマッピングすることができる）である。
【０００７】
ここで、ＶＬＣコードのいくつかの一般的性質を参照するとき有用ないくつかの距離を紹介及び提示することは、ＶＬＣ符号理論において利用される誤り訂正性質の概念を説明するのに役立つであろう。
【０００８】
（ａ）ハミングウェート及び距離：ｗをｗ＝（ｗ１，ｗ２，．．．，ｗｎ）による長さｎのワードとすると、ｗのハミングウェート、単にウェートは、ｗの非零シンボルの個数Ｗ（ｗ）、
【０００９】
【数３】
2006504316.tif 000005
となり、ｗ１とｗ２をｗｉ＝（ｗｉ１，ｗｉ２，．．．，ｗｉｎ）（ｉ＝１，２）による等しい長さｎの２つのワードとすると、ｗ１とｗ２のハミング距離（または単に距離）は、ｗ１とｗ２が異なるポジションの個数である（例えば、２進数の場合、
【００１０】
【数４】
2006504316.tif 000006
ただし、加算はモジュロ−２となることは容易にわかるであろう）。しかしながら、ハミング距離は、その定義により固定長のコードであり、ＶＬＥＣコードを考慮するとき他の定義が与えられるであろう。
【００１１】
（ｂ）ｆｉ＝ｗ１ｉｗ２ｉ．．．ｗｎｉをＶＬＥＣコードＣのｎ個のワードを連結したものとすると、集合ＦＮ＝｛ｆｉ：｜ｆｉ｜＝Ｎ｝は、オーダＮのＣの拡張コードと呼ばれる。
【００１２】
（ｃ）最小ブロック距離及び全体最小ブロック距離：ＶＬＥＣコードＣのコードワード長Ｌｋに関する最小ブロック距離ｂｋは、同じ長さＬｋを有するＣの相異なるすべてのコードワード間の最小はミング距離として定義される。すなわち、
【００１３】
【数５】
2006504316.tif 000007
そして、すべての可能な長さＬｋに対する最小ブロック距離である当該ＶＬＥＣコードＣの全体最小ブロック距離ｂｍｉｎは、
【００１４】
【数６】
2006504316.tif 000008
として定義される。
【００１５】
（ｄ）発散距離及び最小発散距離：ＶＬＥＣコードＣの互いに異なる長さの２つのコードワードｃｉ＝ｘｉ１ｘｉ２．．．ｘｉｌｉとｃｊ＝ｘｊ１ｘｊ２．．．ｘｊｌｊ（ｃｉ，ｃｊ∈Ｃ，ｌｉ＝｜ｃｉ｜，ｌｊ＝｜ｃｊ｜，ｌｉ＞ｌｊ）との間の発散距離は、
【００１６】
【数７】
2006504316.tif 000009
により定義される。すなわち、それはｌｊ長のコードワードとより長いコードワードのｌｊ長のプリフィックスとの間のハミング距離である。当該ＶＬＥＣコードＣの最小発散距離ｄｍｉｎは、異なる長さを有するＣのコードワードのすべての可能なペア間のすべての発散距離の最小値である。すなわち、
【００１７】
【数８】
2006504316.tif 000010
（ｅ）収束距離及び最小収束距離：ＶＬＥＣコードＣの互いに異なる長さの２つのコードワードｃｉ＝ｘｉ１ｘｉ２．．．ｘｉｌｉとｃｊ＝ｘｊ１ｘｊ２．．．ｘｊｌｊ（｜ｃｉ｜＝ｌｉ＞｜ｃｊ｜＝ｌｊ）との間の収束距離は、
【００１８】
【数９】
2006504316.tif 000011
により定義される。すなわち、それはｌｊ長のコードワードとより長いコードワードのｌｊ長のサフィックスとの間のハミング距離である。当該ＶＬＥＣコードＣの最小収束距離ｃｍｉｎは、異なる長さを有するＣのコードワードのすべての可能なペア間のすべての収束距離の最小値である。すなわち、
【００１９】
【数１０】
2006504316.tif 000012
（ｆ）フリー距離：あるコードのフリー距離ｄｆｒｅｅとは、ある共通状態Ｓｉから発散し、他の共通状態Ｓｊ（ｊ＞ｉ）に再び収束する任意の長さのすべてのパスの集合における最小ハミング距離である。すなわち、
【００２０】
【数１１】
2006504316.tif 000013
ＶＬＣに用いられる構成モデルに従うと、ＶＬＥＣコードＣの構成を
【００２１】
【数１２】
2006504316.tif 000014
により記述することが可能となる。ただし、すべてのｉ（ｉ＝１，２，．．．，Ｒ）に対して、最小ブロック距離ｂｉを有する長さＬｉのｓｉコードワードと（ここで、Ｒは相異なるコードワード長の個数）、最小発散及び収束距離ｄｍｉｎ及びｃｍｉｎが存在する。ＶＬＥＣコードの最も重要なパラメータは、そのフリー距離ｄｆｒｅｅであり、これは誤り訂正機能に関するそのパフォーマンスに大きな影響を与え、ＶＬＥＣコードのフリー距離は、
【００２２】
【数１３】
2006504316.tif 000015
により制限されるということを示すことができる。
【００２３】
上記定義が説明されると、最新のＶＬＥＣ符号構成が容易に説明されるであろう。α−プロンプトコードと呼ばれ、１９７４年に紹介された第１のタイプのＶＬＥＣコードと、αｔ１，ｔ２，．．．，ｔＲ−プロンプトコードと呼ばれるこの系の拡張は、何れも同じ基本的性質を有する。すなわち、α（ｃｉ）により任意のコードワードｃｊよりｃｉ（ｊ≠ｉ）に近いワードの集合を表すとき、α（ｃｉ）のシーケンスの何れもが他のα（ｃｉ）のシーケンスのプリフィックスとならない。これらのコードの構成は大変シンプルなものであり、その生成アルゴリズムは、各長さでのコードワードの個数により調整可能であり、所与のソースと所与のｄｆｒｅｅに対して最善のプロンプトコードを求めることが可能である。しかしながら、この最善のコードは、圧縮性能に関しては良好には実行されない。
【００２４】
固定長線形ブロックコードの生成行列からのＶＬＥＣコードの生成を可能にする最近の生成方法がＶ．Ｂｕｔｔｉｇｉｅｇによる１９９５年の英国のマンチェスター大学の博士論文「Ｖａｒｉａｂｌｅ−ｌｅｎｇｔｈ  ｅｒｒｏｒ−ｃｏｒｒｅｃｔｉｎｇ  ｃｏｄｅｓ」において提案された。コード−アンチコード（ｃｏｄｅ−ａｎｔｉｃｏｄｅ）生成と呼ばれるこのアルゴリズムは、最右カラムにアンチコードを生成するため、ラインの組み合わせとカラムの順列に拠るものである。コード−アンチコード生成行列が取得されると、ＶＬＥＣコードは単に行列の乗算により取得される。
【００２５】
しかしながら、この技術はいくつかの問題点を有する。まず、アンチコードを取得するのに必要とされるライン組み合わせとカラム順列を求める明示的方法が存在しない。さらに、この生成はソースの統計量を考慮に入れておらず、このためしばしば、それ自身次善的であることが明らかにされている（ＶＬＥＣコードに対する後処理によって、より短い平均長を有するコードを求めることが可能である）。同じ文献において著者は、指定されたソースと所与のエラーに対するプロテクションに対しより良好な既知の圧縮率を与えるＶＬＥＣコード、すなわち、選ばれたフリー距離と指定されたソースに対する最小平均コードワード長を取得するため、フリー指定された全体最小ブロック、発散及び収束距離と、ソース統計量に一致したコードワード長を有するコードＣを生成するコンピュータ探索に基づく発見的（Ｈｅｕｒｉｓｔｉｃ）方法と呼ばれる向上した方法を提案している（実際、ｂｍｉｎ＝ｄｍｉｎ＋ｃｍｉｎかつｄｍｉｎ＝［ｄｆｒｅｅ/２］とされる）。
【００２６】
図２〜４のフローチャートを参照して、コードワードの最小の長さＬ１、コードワードの最大の長さＬｍａｘ、各コードワード間のフリー距離ｄｆｒｅｅ及び必要とされるコードワード数Ｓのパラメータを利用した発見的方法の主要なステップが説明される。
【００２７】
コンピュータ探索を開始するため（「スタート」）、Ｌ１（少なくとも必要とされる最小発散距離以上であることが必要とされる最小コードワード長）、Ｌｍａｘ（最大コードワード長）、コードワード間の各種距離（ｄｆｒｅｅ，ｂｍｉｎ，ｄｍｉｎ，ｃｍｉｎ）及びＳ（所与のソースにより求められるコードワード数）のすべての必要なパラメータがまず指定され、上記パラメータを選ぶ際、いくつかの関係が設定される。すなわち、
Ｌｌ≧ｄｍｉｎ
ｂｍｉｎ＝ｄｆｒｅｅ
ｄｍｉｎ＋ｃｍｉｎ＝ｄｆｒｅｅ
その後、ステップ１１により参照されるアルゴリズムの第１段階が実行される。当該段階は、最大数のコードワードによる最小距離ｂｍｉｎと長さＬ１の固定長コード（初期的にはＣにおける）の生成から構成される。実際、この段階は初期化であり、図５に与えられるグリーディーアルゴリズム（ＧＡ）、図７に与えられる多数決アルゴリズム（ＭＶＡ）、あるいは上記２つの変形からなるＧＡＳ（Ｇｒｅｅｄｙ  Ａｌｇｏｒｉｔｈｍ  ｂｙ  Ｓｔｅｐ）により表される新しく提案された変形（ＧＡＳは、ＧＡにおいて用いられる検索方法から構成され、コードワードの半分を削除する代わりに、当該グループの最後のコードワードのみが削除される）などにより実行される。これら２つのアルゴリズムは、ｄだけ離れたｎビット長のワードの集合Ｗを生成するのに有用であるが（実際、ＭＶＡはＧＡより多くのワードを検出する）、図６及び８の表に示されるように、わずかな圧縮機能の向上のために、ＧＡとＭＶＡのそれぞれに対し、図９の表に規定される２６シンボルの英語ソースに対する異なるｄｆｒｅｅの値により取得される最善のコード構成と比較して、過度な時間が要求される。
【００２８】
図２のステップ２１〜２４に対応するアルゴリズムの第２段階は（２１＋２２＝処理「Ａ０」、２３＋２４＝処理「Ａ２」）、集合ＷにおいてＣのコードワードからのｄｍｉｎの距離にあるすべての可能なＬ１項を列挙及び格納することからなる。ｄｍｉｎ≧ｂｍｉｎである場合、Ｗは空となる。現在コードに対する最小発散距離を満たすすべてのワードの集合Ｗは空でない場合（テスト２２の｜Ｗ｜＝？に対してＮＯ）、最大ビット数を超過する場合を除き（テスト２３に対してＹＥＳ）、Ｗのすべてのワードの最右ポジションにまず「０」を付加し、その後に「１」を付加することにより（ステップ２４）、ワードの長さを１ビットだけ増やすことによって、Ｗのワード数を２倍にする。ステップ２４の出力において、この変更された集合Ｗは、もとのＷの２倍のワードを有し、各ワードの長さはＬ１＋１となる。
【００２９】
ステップ３１〜３５（＝図２の処理「Ａ３」）に対応するアルゴリズムの第３段階は、Ｃのすべてのコードワードによるｃｍｉｎ距離（最小収束距離）を満足しない集合Ｗのすべてのワードを削除する（すなわち、最小収束距離を満足するワードのみを新たなＷに保持及び格納し、その他のワードを破棄する）ことからなる（ステップ３１）。この時点で、新しい集合Ｗは、Ｃのコードワードと比較するとき、Ｃのコードワードにより必要とされる最小発散及び収束距離（ｄｍｉｎ及びｃｍｉｎ）を満足するワードの集合となっている。この新たな集合Ｗが空でない場合（テスト３２の｜Ｗ｜＝０？に対しＮＯ）、同じ長さを有する集合Ｗのすべてのワードがｂｍｉｎに少なくとも等しい最小距離を有することを保証するため、Ｗにおいて最小ブロック距離を満足する最大数のワードを選択する（ステップ３３）。ＧＡまたはＭＶＡにより実現されるステップ３３の終わりで（この場合、ＧＡまたはＭＶＡに対し用いられる初期集合は、現在のＷであり、ｎ項の集合ではない）、取得されるワードは、Ｃにすでにあるコードワードに追加される（ステップ３４）。
【００３０】
ステップ２１の終わりでワードが検出されない場合（すなわち、Ｗが空である）（テスト２２の｜Ｗ｜＝０？に対しＹＥＳ）、あるいは最大ビット数に到達または超過した場合（テスト２３に対しＹＥＳ）、アルゴリズムの第４段階に進み（図３に示され、処理「Ａ１」により示されるステップ４１〜４６）、新たなグループが古いグループより多くのビットを含むように、より詳細にはＷのすべてのワードに追加的ビット（同時に複数のビット）を付加することにより、より多くの選択の自由度を挿入することにより当該プロセスを修正する。最後のグループに十分なコードワードが存在する場合（最後のグループのコードワード数を検証するための連続するテスト４１と４２、及び以前のグループがある場合）、それの一部が当該グループから削除される。このような削除は距離の制約を減少させ、以前より多くのコードワードを検出することを可能にする。従って実際問題として、上述した従来の発見的方法は、短い長さを有する最大数のコードワードから開始され、それらを高確率シンボルにマッピングし、良好な圧縮率の獲得を試みるが、ときどき小さな長さ集合のサイズは必要とされる個数のコードワードＳと両立しない。この観点では、少数のコードワードを解放することはより大きな自由度を提供し、距離やコードのシンボル数に関する初期的要求が満足されうるポジションに到達することを可能にする。この削除プロセスは、各長さに対し最大１つのコードワードが残るまで繰り返される。ステップ３１の終わりでＷが空となる場合（テスト３２の｜Ｗ｜＝０？に対しＹＥＳ）、ステップ２３、２４、３１及び３２が繰り返される。必要な個数のコードワードに達しない場合（第３段階の終わりで与えられるテスト３５に対しＮＯ）、ステップ２１〜２４及び３１〜３５が、検出対象のさらなる可能性のあるワードが存在しないか、あるいは必要とされる個数のコードワードに達したとわかるまで繰り返される。
【００３１】
コードワードの必要な個数に達すると、すなわち、Ｃのコードワード数がＳ以上である場合（テスト３５に対しＹＥＳ）、取得されるＶＬＥＣコードの構成は、平均長を計算するため、ステップ５１〜５６（図４に示され、処理「Ａ４」として示される）を含む第５段階で利用される。これは、各コードワード長をソースの確率により重み付けし、それを現在の最善のものと比較することにより実行される。このＶＬＥＣコードの平均長ＡＬがＡＬの最小値（＝ＡＬｍｉｎ）より小さい場合、当該ＡＬがＡＬｍｉｎとなり、この新しいＡＬ値と対応するコード構成がメモリに保持される（ステップ５１）。ステップ５１と以下のステップ（処理「Ａ４」の第５段階）は、アルゴリズムのその他の段階が常に現在のグループに対し実行されるのに対して、以前のグループに戻ることを可能にしている。このようなフィードバック動作のステップサイズは１であり、すなわち、当該フィードバック動作は網羅的とみなすことができる。
【００３２】
最善のＶＬＥＣコードの検索を続けるため、アルゴリズムにおけるループを発生させるような同一の構成を維持することを回避する必要がある。現在のコードの最後に追加されるグループが削除され（ステップ５２，５３）、より短いコードワードの削除がより多くのより長いコードワードの検出を可能にし（テスト５４におけるグループのコードワード数は１より多いか？）、ステップ２１の始めにアルゴリズムを再ループさせるため（ステップ５６）、前のグループの一部のコードワード（ＧＶＡの半分、ＭＶＡの最善のもの）が削除され（ステップ５５）、異なるＶＬＥＣ構成を検出する（削除されるコードワード数は、ワードを選択するのに利用される方法に依存する。すなわち、ＧＡ法が利用され、線形コードの取得が所望される場合、コードワードの半分を削除する必要があるのに対し、ＭＶＡ法では１つのみの最善のコードワードが削除される。すなわち、次のグループでより多くのコードワードを検出する可能にするものが削除される。）。
【００３３】
しかしながら、上述の発見的方法はしばしば、可能性の低いコード構成を考えているか、あるいはより大きな複雑さが当該方法を実現するとき観察される注意と共に進行し（何かをミスしないようにするため）、さらなる時間を要し、過度なものとなりうる。
【発明の開示】
【発明が解決しようとする課題】
【００３４】
従って、本発明の課題は、上記問題点を回避することにより複雑さを克服することが可能な向上した生成方法を提供することである。
【００３５】
このため、本説明の導入部で定義されたような、高々１ビットが集合Ｗの各ワードの終わりに追加される可変長誤り符号の生成方法に関する。
【００３６】
本発明のさらなる課題は、このような可変長誤り符号生成方法を実行する装置を提案することである。
【発明を実施するための最良の形態】
【００３７】
従来の発見的方法によると、取得された最善のコードのほとんどすべてがホール、すなわち、その構成の長さのジャンプを持たないことがシミュレーションにより示されている。本発明によると、大部分の良好なコードが長さのジャンプを持たないということを考慮し、これにより調べられたＶＬＥＣコードの集合を減らす（この結果、ＡＬを大きく変更することなく、シミュレーション時間と当該方法の実現の複雑さを軽減する）ことが提案される。この仮説に従って、本発明による方法は、集合Ｗの各ワードの終わりに１より多くのビットを追加することを回避することにより変更される。
【００３８】
対応する実現形態（ホール最適化のない向上した発見的生成方法）が、本発明による向上した方法を実行することを可能にするシステムに対応するフローチャートの２つの部分を示す図１０と１１に示される（図２〜４に示されるものと同一の要素は、同一の参照番号により示される）。
【００３９】
図２〜４のフローチャートとの主な相違点は、以下の点である。
【００４０】
（ａ）まず、この向上した方法の実現形態に不要な従来の発見的技術に関する部分が削除される。
【００４１】
（ｂ）ステップ３１の終わりでＷが空となる場合（テスト３２の｜Ｗ｜＝０？に対しＹＥＳ）、次の段階はステップ２３、２４、３１及び３２の繰り返しでなく、処理５５（ステップ２１〜２４お呼び３１〜３５の繰り返しの前にいくつかのコードワードまたは最善のコードワードの削除）を実行する回路の（図１１の）入力に対する直接的接続９１が確立され（繰り返しの代わりに）、これにより、処理５５は以前のように処理２１と以下に続く。
【００４２】
（ｃ）本方法の第４段階が「最後のグループのコードワード数＝１？」のテストである１ステップの処理４１（図１１）に減らされる。テスト結果がＮＯである場合、処理５５の実行に関してステップ５５の入力により直接的なリンク１０１が確立され、その後、処理２１と以下に続く。テスト結果がＹＥＳである場合、処理５２〜５４の集合の入力との接続１０２が確立される。
【００４３】
この解法により得られる結果（「ｎｏＨｏｌｅ最適化方法」と呼ばれる）が、コードワードを選択するのにＧＡＳ方法を利用するとき、２６シンボルの英語ソースに対する図１２の表に与えられる。図１３に与えられた結果と比較するとき、当該結果がｄｆｒｅｅ＝３（コード構成は長さＬ＝１１においてホールを有する）に対して完全には最適なものではないが、その他のｄｆｒｅｅの値に対する劣化と２、５及び４との間の時間のゲインがないと考えるとき、ＡＬの増加は実際に許容されるということが示されうる。同様の注意が、ＭＶＡの複雑さの影響が明らかな図７に示されるものと本手段とを比較するときに適用可能である。同様に、ｎｏＨｏｌｅ最適化をコードワードを選択するためのＧＡ方法に適用することは、ｄｆｒｅｅ＝３に対するわずかなＡＬの増加を犠牲にするだけで、時間のゲインをもたらす。最後に他方、図５は、現在の手段が時間の許容されるゲインに対するより良いＡＬを提供し、ｎｏＨｏｌｅ最適化によりＧＡＳにより導かれる複雑さのほとんど全体が補償される。
【図面の簡単な説明】
【００４４】
【図１】図１は、従来の通信チャネルを示す。
【図２】図２は、発見的方法と呼ばれるＶＬＥＣコードを生成するのに利用される従来の方法の主要なステップを示すフローチャートの一部である。
【図３】図３は、発見的方法と呼ばれるＶＬＥＣコードを生成するのに利用される従来の方法の主要なステップを示すフローチャートの一部である。
【図４】図４は、発見的方法と呼ばれるＶＬＥＣコードを生成するのに利用される従来の方法の主要なステップを示すフローチャートの一部である。
【図５】図５は、図２〜４の方法の初期化に利用されるアルゴリズム（グリーディーアルゴリズム、すなわちＧＡと呼ばれる）を示す。
【図６】図６は、図５のアルゴリズムを利用した発見的生成により構成されるソースに対する様々なＶＬＥＣコードを与える表である。
【図７】図７は、図２〜４の方法の初期化に利用される他のアルゴリズム（多数決アルゴリズム、すなわちＭＶＡと呼ばれる）を示す。
【図８】図８は、図７のアルゴリズムを利用した発見的生成により構成されるソースに対する様々なＶＬＥＣコードを与える他の表である。
【図９】図９は、２６シンボルの英語ソースに対し、ソースシンボルとそれの確率との間の対応を与える表である。
【図１０】図１０は、図２〜４に示される従来の方法を向上させる実現形態を示す本発明によるフローチャートの一部である。
【図１１】図１１は、図２〜４に示される従来の方法を向上させる実現形態を示す本発明によるフローチャートの一部である。
【図１２】図１２は、図６と８の表で考えられるものと同じ２６シンボルの英語ソースに対する様々なＶＬＥＣコードを与え、ＧＡＳを利用した他の表である。
【図１３】図１３は、図１２と同様のソースに対する様々なＶＬＥＣコードを与え、上述のＧＡＳと本発明による生成方法を利用した他の表である。
【図１】
2006504316.tif 000016
【図２】
2006504316.tif 000017
【図３】
2006504316.tif 000018
【図４】
2006504316.tif 000019
【図５】
2006504316.tif 000020
【図６】
2006504316.tif 000021
【図７】
2006504316.tif 000022
【図８】
2006504316.tif 000023
【図９】
2006504316.tif 000024
【図１０】
2006504316.tif 000025
【図１１】
2006504316.tif 000026
【図１２】
2006504316.tif 000027
【図１３】
2006504316.tif 000028
【国際調査報告】
2006504316.tif 000029
2006504316.tif 000030
2006504316.tif 000031