(57)【要約】【課題】符号語長の長短に関わらず効率的にタイプ一定符号を生成する符号化およびその復号化を行うこと。【解決手段】記憶部が、第１の疎行列、第２の疎行列、所定のハミング重みを有する１行の横行列および所定のタイプを記憶し、最適化実行部が、符号語と第１の疎行列との積がタイプと等値であるとする第１の制約式、符号語と第２の疎行列との積が２値メッセージと等値であるとする第２の制約式、および、符号語の符号語長とタイプとの積であるハミング重みが符号語の要素が１である桁の個数と等値であるとする第３の制約式を用い、第１の制約式、第２の制約式および第３の制約式を緩和法によって実数体上の線形制約条件へ変換したうえで、これらの線形制約条件をすべて満たす符号語を線形計画法で求解するように符号化装置を構成する。【選択図】        図２
2011041081.tif 000002
【特許請求の範囲】
【請求項１】
２値メッセージからハミング重みが一定である通信路符号を生成する符号化装置であって、
第１の疎行列、第２の疎行列、所定のハミング重みを有する１行の横行列および所定のタイプを記憶する記憶手段と、
符号語と前記第１の疎行列との積が前記タイプと等値であるとする第１の制約式、前記符号語と前記第２の疎行列との積が前記２値メッセージと等値であるとする第２の制約式、および、前記符号語の符号語長と前記タイプとの積である前記ハミング重みが前記符号語の要素が１である桁の個数と等値であるとする第３の制約式を用い、前記第１の制約式、前記第２の制約式および前記第３の制約式を緩和法によって実数体上の線形制約条件へ変換したうえで、該線形制約条件をすべて満たす前記符号語を線形計画法で求解する最適化実行手段と
を備えたことを特徴とする符号化装置。
【請求項２】
通信路出力から符号化前の２値メッセージを生成する復号化装置であって、
符号化に用いられた第１の疎行列、第２の疎行列、所定のハミング重みを有する１行の横行列および所定のタイプを記憶する記憶手段と、
符号化された前記２値メッセージをあらわす符号語と前記第１の疎行列との積が前記タイプと等値であるとする第１の制約式、前記符号語の符号語長と前記タイプとの積である前記ハミング重みが前記符号語の要素が１である桁の個数と等値であるとする第２の制約式、前記符号語の要素と前記通信路出力の要素とが双方とも１である桁の個数が所定の自然数と等値であるとする第３の制約式、および、前記符号語に関して線形な目的関数を用い、前記第１の制約式、前記第２の制約式および前記第３の制約式を緩和法によって実数体上の線形制約条件へ変換したうえで、該線形制約条件をすべて満たす前記符号語のうち、前記目的関数を最小とする前記符号語を線形計画法で求解し、当該符号語と前記第２の疎行列との積を前記２値メッセージとする最適化実行手段と
を備えたことを特徴とする復号化装置。
【請求項３】
前記最適化実行手段が用いる前記目的関数は、
前記符号語をｘｎ、前記通信路出力をｙｎ、前記符号語長をｎ、前記タイプをＰ、Ｈｂ（δ）をＨｂ（δ）＝−δｌｏｇδ−（１−δ）ｌｏｇ（１−δ）、系列ｒｎにおけるａの出現回数をＮ（ａ｜ｒｎ）、前記所定の自然数ｍを０≦ｍ≦ｍｉｎ｛ｎＰ，Ｎ（１｜ｙｎ）｝とした場合に、
（Ｎ（０｜ｙｎ）／ｎ）Ｈｂ（（ｎＰ−ｍ）／Ｎ（０｜ｙｎ））＋
（Ｎ（１｜ｙｎ）／ｎ）Ｈｂ（ｍ／Ｎ（１｜ｙｎ））
とあらわされることを特徴とする請求項２に記載の復号化装置。
【請求項４】
前記所定の自然数は、
０以上、かつ、前記ハミング重みまたは前記通信路出力の要素が１である桁の個数のうち小さいほうの値以下であって、
前記最適化実行手段は、
それぞれの前記所定の自然数について、前記第１の制約式、前記第２の制約式および前記第３の制約式をすべて満たす前記符号語についての実行可能解が存在するか否かについて判定し、前記実行可能解が存在すると判定した場合に、前記目的関数の値を算出することを特徴とする請求項２または３に記載の復号化装置。
【請求項５】
情報源出力から求めた復号化器出力に基づいてハミング重みが一定である有歪み情報源符号を生成する符号化装置であって、
第１の疎行列、第２の疎行列、所定のハミング重みを有する１行の横行列および所定のタイプを記憶する記憶手段と、
前記復号化器出力と前記第１の疎行列との積が前記タイプと同値であるとする第１の制約式、前記復号化器出力の符号語長と前記タイプとの積である前記ハミング重みが前記復号化器出力の要素が１である桁の個数と等値であるとする第２の制約式、前記情報源出力の要素と前記復号化器出力の要素とが双方とも１である桁の個数が所定の自然数と等値であるとする第３の制約式、および、前記復号化器出力に関して線形な目的関数を用い、前記第１の制約式、前記第２の制約式および前記第３の制約式を緩和法によって実数体上の線形制約条件へ変換したうえで、該線形制約条件すべて満たす前記復号化器出力のうち、前記目的関数を最小とする前記復号化器出力を線形計画法で求解し、当該復号化器出力と前記第２の疎行列との積を前記有歪み情報源符号とする最適化実行手段と
を備えたことを特徴とする符号化装置。
【請求項６】
前記最適化実行手段が用いる前記目的関数は、
前記情報源出力をｘｎ、前記復号化器出力をｙｎ、前記符号語長をｎ、前記タイプをＰ、ｐを０＜ｐ＜１、ｑを０＜ｑ＜１、Ｄ（ｐ‖ｑ）をＤ（ｐ‖ｑ）＝ｐｌｏｇ（ｐ／ｑ）＋（１−ｐ）ｌｏｇ（（１−ｐ）／（１−ｑ））、系列ｒｎにおけるａの出現回数をＮ（ａ｜ｒｎ）、所定の条件付確率をＷＹ｜Ｘとした場合に、
（Ｎ（０｜ｙｎ）／ｎ）Ｄ（（ｎＰ−ｍ）／Ｎ（０｜ｘｎ）‖ＷＹ｜Ｘ（１｜０））＋
（Ｎ（１｜ｙｎ）／ｎ）Ｄ（ｍ／Ｎ（１｜ｙｎ）‖ＷＹ｜Ｘ（１｜１））
とあらわされることを特徴とする請求項５に記載の符号化装置。
【請求項７】
前記所定の自然数は、
０以上、かつ、前記ハミング重みまたは前記情報源出力の要素が１である桁の個数のうち小さいほうの値以下であって、
前記最適化実行手段は、
それぞれの前記所定の自然数について、前記第１の制約式、前記第２の制約式および前記第３の制約式をすべて満たす前記復号化器出力についての実行可能解が存在するか否かについて判定し、前記実行可能解が存在すると判定した場合に、前記目的関数の値を算出することを特徴とする請求項５または６に記載の符号化装置。
【請求項８】
有歪み情報源符号から復号化器出力を生成する復号化装置であって、
符号化に用いられた第１の疎行列、第２の疎行列、所定のハミング重みを有する１行の横行列および所定のタイプを記憶する記憶手段と、
前記復号化器出力と前記第１の疎行列との積が前記タイプと等値であるとする第１の制約式、前記復号化器出力と前記第２の疎行列との積が前記有歪み情報源符号と等値であるとする第２の制約式、および、前記復号化器出力の符号語長と前記タイプとの積である前記ハミング重みが前記復号化器出力の要素が１である桁の個数と等値であるとする第３の制約式を用い、前記第１の制約式、前記第２の制約式および前記第３の制約式を緩和法によって実数体上の線形制約条件へ変換したうえで、該線形制約条件をすべて満たす前記復号化器出力を線形計画法で求解する最適化実行手段と
を備えたことを特徴とする復号化装置。
【請求項９】
２値メッセージからハミング重みが一定である通信路符号を生成する符号化方法であって、
第１の疎行列、第２の疎行列、所定のハミング重みを有する１行の横行列および所定のタイプを記憶部へ記憶させる記憶工程と、
符号語と前記第１の疎行列との積が前記タイプと等値であるとする第１の制約式、前記符号語と前記第２の疎行列との積が前記２値メッセージと等値であるとする第２の制約式、および、前記符号語の符号語長と前記タイプとの積である前記ハミング重みが前記符号語の要素が１である桁の個数と等値であるとする第３の制約式を用い、前記第１の制約式、前記第２の制約式および前記第３の制約式を緩和法によって実数体上の線形制約条件へ変換したうえで、該線形制約条件をすべて満たす前記符号語を線形計画法で求解する最適化実行工程と
を含んだことを特徴とする符号化方法。
【請求項１０】
通信路出力から符号化前の２値メッセージを生成する復号化方法であって、
符号化に用いられた第１の疎行列、第２の疎行列、所定のハミング重みを有する１行の横行列および所定のタイプを記憶部へ記憶させる記憶工程と、
符号化された前記２値メッセージをあらわす符号語と前記第１の疎行列との積が前記タイプと等値であるとする第１の制約式、前記符号語の符号語長と前記タイプとの積である前記ハミング重みが前記符号語の要素が１である桁の個数と等値であるとする第２の制約式、前記符号語の要素と前記通信路出力の要素とが双方とも１である桁の個数が所定の自然数と等値であるとする第３の制約式、および、前記符号語に関して線形な目的関数を用い、前記第１の制約式、前記第２の制約式および前記第３の制約式を緩和法によって実数体上の線形制約条件へ変換したうえで、該線形制約条件をすべて満たす前記符号語のうち、前記目的関数を最小とする前記符号語を線形計画法で求解し、当該符号語と前記第２の疎行列との積を前記２値メッセージとする最適化実行工程と
を含んだことを特徴とする復号化方法。
【請求項１１】
情報源出力から求めた復号化器出力に基づいてハミング重みが一定である有歪み情報源符号を生成する符号化方法であって、
第１の疎行列、第２の疎行列、所定のハミング重みを有する１行の横行列および所定のタイプを記憶部へ記憶させる記憶工程と、
前記復号化器出力と前記第１の疎行列との積が前記タイプと同値であるとする第１の制約式、前記復号化器出力の符号語長と前記タイプとの積である前記ハミング重みが前記復号化器出力の要素が１である桁の個数と等値であるとする第２の制約式、前記情報源出力の要素と前記復号化器出力の要素とが双方とも１である桁の個数が所定の自然数と等値であるとする第３の制約式、および、前記復号化器出力に関して線形な目的関数を用い、前記第１の制約式、前記第２の制約式および前記第３の制約式を緩和法によって実数体上の線形制約条件へ変換したうえで、該線形制約条件をすべて満たす前記復号化器出力のうち、前記目的関数を最小とする前記復号化器出力を線形計画法で求解し、当該復号化器出力と前記第２の疎行列との積を前記有歪み情報源符号とする最適化実行工程と
を含んだことを特徴とする符号化方法。
【請求項１２】
有歪み情報源符号から復号化器出力を生成する復号化方法であって、
符号化に用いられた第１の疎行列、第２の疎行列、所定のハミング重みを有する１行の横行列および所定のタイプを記憶部へ記憶させる記憶工程と、
前記復号化器出力と前記第１の疎行列との積が前記タイプと等値であるとする第１の制約式、前記復号化器出力と前記第２の疎行列との積が前記有歪み情報源符号と等値であるとする第２の制約式、および、前記復号化器出力の符号語長と前記タイプとの積である前記ハミング重みが前記復号化器出力の要素が１である桁の個数と等値であるとする第３の制約式を用い、前記第１の制約式、前記第２の制約式および前記第３の制約式を緩和法によって実数体上の線形制約条件へ変換したうえで、該線形制約条件をすべて満たす前記復号化器出力を線形計画法で求解する最適化実行工程と
を含んだことを特徴とする復号化方法。
【請求項１３】
請求項１に記載の符号化装置の動作手順をコンピュータに実行させることを特徴とする符号化プログラム。
【請求項１４】
請求項２、３または４に記載の復号化装置の動作手順をコンピュータに実行させることを特徴とする復号化プログラム。
【請求項１５】
請求項５、６または７に記載の符号化装置の動作手順をコンピュータに実行させることを特徴とする符号化プログラム。
【請求項１６】
請求項８に記載の復号化装置の動作手順をコンピュータに実行させることを特徴とする復号化プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、ハミング重みが一定であるタイプ一定符号を生成する符号化およびその復号化に関し、特に、符号語長の長短に関わらず効率的にタイプ一定符号を生成する符号化およびその復号化を行うことができる符号化装置、復号化装置、符号化方法、復号化方法、符号化プログラムおよび復号化プログラムに関する。
【背景技術】
【０００２】
従来、通信路符号や有歪み情報源符号が符号語長（ブロック長）に関して漸近的にシャノン限界に近づく性質をもつ場合、これらの符号としては一般的に典型系列が用いられていた（たとえば、特許文献１および特許文献２参照）。ここで、典型系列とは、符号語のハミング重みが所定の一定値の周りに分布する、すなわち、ハミング重みに幅をもたせた系列を指す。また、ハミング重みとは符号語における０以外のシンボルの個数を指す。
【０００３】
ところで、ハミング重みが一定の符号語（以下、「タイプ一定符号（Constant  Composition  Code，Constant  Weight  Code）」と記載する）は、シャノン限界への到達性の証明に用いられるなど（たとえば、非特許文献１参照）、理論解析においてしばしば用いられている。
【０００４】
また、タイプ一定符号は、無線システム技術（たとえば、非特許文献２参照）や、検索技術（たとえば、非特許文献３参照）にも用いられている。なお、非特許文献４には、有限体上の拘束条件を実数体上の線形制約条件へ変換する技術が開示されている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００８−１７７８９２号公報
【特許文献２】特開２００９−０６０２８８号公報
【非特許文献】
【０００６】
【非特許文献１】I. Csiszar and J. Korner, Information Theory: Coding Theorems for Discrete Memoryless Systems, Academic Press, 1981
【非特許文献２】D. H. Smith, L. A. Hughes and S. Perkins, "A New Table of Constant Weight Codes of Length Greater than 28," The Electronic Journal of Combinatorics 13， 2006
【非特許文献３】三宅, “全文検索システムのインデックス構成に関する情報理論的アプローチ,” 電子情報通信学会技術報告, PRMU2008-108 (IT-2008-65) ,2009年3月, P137-141
【非特許文献４】J. Feldman, M. J. Wainwright, and D. R. Karger, “Using linear programming to decode binary linear codes,”IEEE Trans. Inform. Theory, vol. 51, pp. 954-972, 2005
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、タイプ一定符号を実際にどのように構成するかは未だ明らかになっておらず、符号語長（ブロック長）ｎが１００より小さい場合に、あらかじめ用意したテーブルに従ってタイプ一定符号が生成されているにすぎない（たとえば、非特許文献２参照）。
【０００８】
すなわち、従来におけるタイプ一定符号は、理論解析の分野で用いられているものの、その適用範囲は、符号語長（ブロック長）ｎが小さい場合に限られており、適用分野が限定されるという問題があった。
【０００９】
また、符号語長（ブロック長）ｎが大きくなると、従来のタイプ一定符号の生成手法では、計算量がｎに関して指数的に増加してしまうため、長い符号語長に対応したタイプ一定符号を効率よく生成することは困難であった。
【００１０】
これらのことから、符号語長の長短に関わらず効率的にタイプ一定符号を生成する符号化およびその復号化を行うことができる符号化装置、復号化装置、符号化方法、復号化方法、符号化プログラムあるいは復号化プログラムをいかにして実現するかが大きな課題となっている。
【００１１】
本発明は、上述した従来技術による問題点を解消するためになされたものであって、符号語長の長短に関わらず効率的にタイプ一定符号を生成する符号化およびその復号化を行うことができる符号化装置、復号化装置、符号化方法、復号化方法、符号化プログラムおよび復号化プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１２】
上述した課題を解決し、目的を達成するため、本発明は、２値メッセージからハミング重みが一定である通信路符号を生成する符号化装置であって、第１の疎行列、第２の疎行列、所定のハミング重みを有する１行の横行列および所定のタイプを記憶する記憶手段と、符号語と前記第１の疎行列との積が前記タイプと等値であるとする第１の制約式、前記符号語と前記第２の疎行列との積が前記２値メッセージと等値であるとする第２の制約式、および、前記符号語の符号語長と前記タイプとの積である前記ハミング重みが前記符号語の要素が１である桁の個数と等値であるとする第３の制約式を用い、前記第１の制約式、前記第２の制約式および前記第３の制約式を緩和法によって実数体上の線形制約条件へ変換したうえで、該線形制約条件をすべて満たす前記符号語を線形計画法で求解する最適化実行手段とを備えたことを特徴とする。
【００１３】
また、本発明は、通信路出力から符号化前の２値メッセージを生成する復号化装置であって、符号化に用いられた第１の疎行列、第２の疎行列、所定のハミング重みを有する１行の横行列および所定のタイプを記憶する記憶手段と、符号化された前記２値メッセージをあらわす符号語と前記第１の疎行列との積が前記タイプと等値であるとする第１の制約式、前記符号語の符号語長と前記タイプとの積である前記ハミング重みが前記符号語の要素が１である桁の個数と等値であるとする第２の制約式、前記符号語の要素と前記通信路出力の要素とが双方とも１である桁の個数が所定の自然数と等値であるとする第３の制約式、および、前記符号語に関して線形な目的関数を用い、前記第１の制約式、前記第２の制約式および前記第３の制約式を緩和法によって実数体上の線形制約条件へ変換したうえで、該線形制約条件をすべて満たす前記符号語のうち、前記目的関数を最小とする前記符号語を線形計画法で求解し、当該符号語と前記第２の疎行列との積を前記２値メッセージとする最適化実行手段とを備えたことを特徴とする。
【００１４】
また、本発明は、上記の発明において、前記最適化実行手段が用いる前記目的関数は、前記符号語をｘｎ、前記通信路出力をｙｎ、前記符号語長をｎ、前記タイプをＰ、Ｈｂ（δ）をＨｂ（δ）＝−δｌｏｇδ−（１−δ）ｌｏｇ（１−δ）、系列ｒｎにおけるａの出現回数をＮ（ａ｜ｒｎ）、前記所定の自然数ｍを０≦ｍ≦ｍｉｎ｛ｎＰ，Ｎ（１｜ｙｎ）｝とした場合に、（Ｎ（０｜ｙｎ）／ｎ）Ｈｂ（（ｎＰ−ｍ）／Ｎ（０｜ｙｎ））＋（Ｎ（１｜ｙｎ）／ｎ）Ｈｂ（ｍ／Ｎ（１｜ｙｎ））とあらわされることを特徴とする。
【００１５】
また、本発明は、上記の発明において、前記所定の自然数は、０以上、かつ、前記ハミング重みまたは前記通信路出力の要素が１である桁の個数のうち小さいほうの値以下であって、前記最適化実行手段は、それぞれの前記所定の自然数について、前記第１の制約式、前記第２の制約式および前記第３の制約式をすべて満たす前記符号語についての実行可能解が存在するか否かについて判定し、前記実行可能解が存在すると判定した場合に、前記目的関数の値を算出することを特徴とする。
【００１６】
また、本発明は、情報源出力から求めた復号化器出力に基づいてハミング重みが一定である有歪み情報源符号を生成する符号化装置であって、第１の疎行列、第２の疎行列、所定のハミング重みを有する１行の横行列および所定のタイプを記憶する記憶手段と、前記復号化器出力と前記第１の疎行列との積が前記タイプと同値であるとする第１の制約式、前記復号化器出力の符号語長と前記タイプとの積である前記ハミング重みが前記復号化器出力の要素が１である桁の個数と等値であるとする第２の制約式、前記情報源出力の要素と前記復号化器出力の要素とが双方とも１である桁の個数が所定の自然数と等値であるとする第３の制約式、および、前記復号化器出力に関して線形な目的関数を用い、前記第１の制約式、前記第２の制約式および前記第３の制約式を緩和法によって実数体上の線形制約条件へ変換したうえで、該線形制約条件すべて満たす前記復号化器出力のうち、前記目的関数を最小とする前記復号化器出力を線形計画法で求解し、当該復号化器出力と前記第２の疎行列との積を前記有歪み情報源符号とする最適化実行手段とを備えたことを特徴とする。
【００１７】
また、本発明は、上記の発明において、前記最適化実行手段が用いる前記目的関数は、前記情報源出力をｘｎ、前記復号化器出力をｙｎ、前記符号語長をｎ、前記タイプをＰ、ｐを０＜ｐ＜１、ｑを０＜ｑ＜１、Ｄ（ｐ‖ｑ）をＤ（ｐ‖ｑ）＝ｐｌｏｇ（ｐ／ｑ）＋（１−ｐ）ｌｏｇ（（１−ｐ）／（１−ｑ））、系列ｒｎにおけるａの出現回数をＮ（ａ｜ｒｎ）、所定の条件付確率をＷＹ｜Ｘとした場合に、（Ｎ（０｜ｙｎ）／ｎ）Ｄ（（ｎＰ−ｍ）／Ｎ（０｜ｘｎ）‖ＷＹ｜Ｘ（１｜０））＋（Ｎ（１｜ｙｎ）／ｎ）Ｄ（ｍ／Ｎ（１｜ｙｎ）‖ＷＹ｜Ｘ（１｜１））とあらわされることを特徴とする。
【００１８】
また、本発明は、上記の発明において、前記所定の自然数は、０以上、かつ、前記ハミング重みまたは前記情報源出力の要素が１である桁の個数のうち小さいほうの値以下であって、前記最適化実行手段は、それぞれの前記所定の自然数について、前記第１の制約式、前記第２の制約式および前記第３の制約式をすべて満たす前記復号化器出力についての実行可能解が存在するか否かについて判定し、前記実行可能解が存在すると判定した場合に、前記目的関数の値を算出することを特徴とする。
【００１９】
また、本発明は、有歪み情報源符号から復号化器出力を生成する復号化装置であって、符号化に用いられた第１の疎行列、第２の疎行列、所定のハミング重みを有する１行の横行列および所定のタイプを記憶する記憶手段と、前記復号化器出力と前記第１の疎行列との積が前記タイプと等値であるとする第１の制約式、前記復号化器出力と前記第２の疎行列との積が前記有歪み情報源符号と等値であるとする第２の制約式、および、前記復号化器出力の符号語長と前記タイプとの積である前記ハミング重みが前記復号化器出力の要素が１である桁の個数と等値であるとする第３の制約式を用い、前記第１の制約式、前記第２の制約式および前記第３の制約式を緩和法によって実数体上の線形制約条件へ変換したうえで、該線形制約条件すべて満たす前記復号化器出力を線形計画法で求解する最適化実行手段とを備えたことを特徴とする。
【００２０】
また、本発明は、２値メッセージからハミング重みが一定である通信路符号を生成する符号化方法であって、第１の疎行列、第２の疎行列、所定のハミング重みを有する１行の横行列および所定のタイプを記憶部へ記憶させる記憶工程と、符号語と前記第１の疎行列との積が前記タイプと等値であるとする第１の制約式、前記符号語と前記第２の疎行列との積が前記２値メッセージと等値であるとする第２の制約式、および、前記符号語の符号語長と前記タイプとの積である前記ハミング重みが前記符号語の要素が１である桁の個数と等値であるとする第３の制約式を用い、前記第１の制約式、前記第２の制約式および前記第３の制約式を緩和法によって実数体上の線形制約条件へ変換したうえで、該線形制約条件をすべて満たす前記符号語を線形計画法で求解する最適化実行工程とを含んだことを特徴とする。
【００２１】
また、本発明は、通信路出力から符号化前の２値メッセージを生成する復号化方法であって、符号化に用いられた第１の疎行列、第２の疎行列、所定のハミング重みを有する１行の横行列および所定のタイプを記憶部へ記憶させる記憶工程と、符号化された前記２値メッセージをあらわす符号語と前記第１の疎行列との積が前記タイプと等値であるとする第１の制約式、前記符号語の符号語長と前記タイプとの積である前記ハミング重みが前記符号語の要素が１である桁の個数と等値であるとする第２の制約式、前記符号語の要素と前記通信路出力の要素とが双方とも１である桁の個数が所定の自然数と等値であるとする第３の制約式、および、前記符号語に関して線形な目的関数を用い、前記第１の制約式、前記第２の制約式および前記第３の制約式を緩和法によって実数体上の線形制約条件へ変換したうえで、該線形制約条件をすべて満たす前記符号語のうち、前記目的関数を最小とする前記符号語を線形計画法で求解し、当該符号語と前記第２の疎行列との積を前記２値メッセージとする最適化実行工程とを含んだことを特徴とする。
【００２２】
また、本発明は、情報源出力から求めた復号化器出力に基づいてハミング重みが一定である有歪み情報源符号を生成する符号化方法であって、第１の疎行列、第２の疎行列、所定のハミング重みを有する１行の横行列および所定のタイプを記憶部へ記憶させる記憶工程と、前記復号化器出力と前記第１の疎行列との積が前記タイプと同値であるとする第１の制約式、前記復号化器出力の符号語長と前記タイプとの積である前記ハミング重みが前記復号化器出力の要素が１である桁の個数と等値であるとする第２の制約式、前記情報源出力の要素と前記復号化器出力の要素とが双方とも１である桁の個数が所定の自然数と等値であるとする第３の制約式、および、前記復号化器出力に関して線形な目的関数を用い、前記第１の制約式、前記第２の制約式および前記第３の制約式を緩和法によって実数体上の線形制約条件へ変換したうえで、該線形制約条件をすべて満たす前記復号化器出力のうち、前記目的関数を最小とする前記復号化器出力を線形計画法で求解し、当該復号化器出力と前記第２の疎行列との積を前記有歪み情報源符号とする最適化実行工程とを含んだことを特徴とする。
【００２３】
また、本発明は、有歪み情報源符号から復号化器出力を生成する復号化方法であって、符号化に用いられた第１の疎行列、第２の疎行列、所定のハミング重みを有する１行の横行列および所定のタイプを記憶部へ記憶させる記憶工程と、前記復号化器出力と前記第１の疎行列との積が前記タイプと等値であるとする第１の制約式、前記復号化器出力と前記第２の疎行列との積が前記有歪み情報源符号と等値であるとする第２の制約式、および、前記復号化器出力の符号語長と前記タイプとの積である前記ハミング重みが前記復号化器出力の要素が１である桁の個数と等値であるとする第３の制約式を用い、前記第１の制約式、前記第２の制約式および前記第３の制約式を緩和法によって実数体上の線形制約条件へ変換したうえで、該線形制約条件をすべて満たす前記復号化器出力を線形計画法で求解する最適化実行工程とを含んだことを特徴とする。
【発明の効果】
【００２４】
本発明によれば、第１の疎行列、第２の疎行列、所定のハミング重みを有する１行の横行列および所定のタイプを記憶し、符号語と第１の疎行列との積がタイプと等値であるとする第１の制約式、符号語と第２の疎行列との積が２値メッセージと等値であるとする第２の制約式、および、符号語の符号語長とタイプとの積であるハミング重みが符号語の要素が１である桁の個数と等値であるとする第３の制約式を用い、第１の制約式、第２の制約式および第３の制約式を緩和法によって実数体上の線形制約条件へ変換したうえで、これらの線形制約条件をすべて満たす符号語を線形計画法で求解することとしたので、各制約式を実数体上の線形制約条件とみなすことによって、符号語長の長短に関わらず効率的にタイプ一定符号を生成する符号化を実現することができるという効果を奏する。また、典型系列を用いた符号よりもシャノン限界に近い伝送容量を実現することができるという効果を奏する。
【００２５】
また、本発明によれば、符号化に用いられた第１の疎行列、第２の疎行列、所定のハミング重みを有する１行の横行列および所定のタイプを記憶し、符号化された２値メッセージをあらわす符号語と第１の疎行列との積がタイプと等値であるとする第１の制約式、符号語の符号語長とタイプとの積であるハミング重みが符号語の要素が１である桁の個数と等値であるとする第２の制約式、符号語の要素と通信路出力の要素とが双方とも１である桁の個数が所定の自然数と等値であるとする第３の制約式、および、符号語に関して線形な目的関数を用い、第１の制約式、第２の制約式および第３の制約式を緩和法によって実数体上の線形制約条件へ変換したうえで、これらの線形制約条件をすべて満たす符号語のうち、目的関数を最小とする符号語を線形計画法で求解し、求解した符号語と第２の疎行列との積を２値メッセージとすることとしたので、各制約式を実数体上の線形制約条件とみなし、また、線形の目的関数を用いることで、タイプ一定符号を効率よく復号化することができるという効果を奏する。
【００２６】
また、本発明によれば、目的関数は、符号語をｘｎ、通信路出力をｙｎ、符号語長をｎ、タイプをＰ、Ｈｂ（δ）をＨｂ（δ）＝−δｌｏｇδ−（１−δ）ｌｏｇ（１−δ）、系列ｒｎにおけるａの出現回数をＮ（ａ｜ｒｎ）、所定の自然数ｍを０≦ｍ≦ｍｉｎ｛ｎＰ，Ｎ（１｜ｙｎ）｝とした場合に、（Ｎ（０｜ｙｎ）／ｎ）Ｈｂ（（ｎＰ−ｍ）／Ｎ（０｜ｙｎ））＋（Ｎ（１｜ｙｎ）／ｎ）Ｈｂ（ｍ／Ｎ（１｜ｙｎ））とあらわされることとしたので、タイプ一定符号を効率よく復号化することができるという効果を奏する。
【００２７】
また、本発明によれば、所定の自然数は、０以上、かつ、ハミング重みまたは通信路出力の要素が１である桁の個数のうち小さいほうの値以下であって、それぞれの所定の自然数について、第１の制約式、第２の制約式および第３の制約式をすべて満たす符号語についての実行可能解が存在するか否かについて判定し、実行可能解が存在すると判定した場合に、目的関数の値を算出することとしたので、復号化に関する処理負荷を低減することができるという効果を奏する。
【００２８】
また、本発明によれば、第１の疎行列、第２の疎行列、所定のハミング重みを有する１行の横行列および所定のタイプを記憶し、復号化器出力と第１の疎行列との積がタイプと同値であるとする第１の制約式、復号化器出力の符号語長とタイプとの積であるハミング重みが復号化器出力の要素が１である桁の個数と等値であるとする第２の制約式、情報源出力の要素と復号化器出力の要素とが双方とも１である桁の個数が所定の自然数と等値であるとする第３の制約式、および、復号化器出力に関して線形な目的関数を用い、第１の制約式、第２の制約式および第３の制約式を緩和法によって実数体上の線形制約条件へ変換したうえで、これらの線形制約条件をすべて満たす復号化器出力のうち、目的関数を最小とする復号化器出力を線形計画法で求解し、求解した復号化器出力と第２の疎行列との積を有歪み情報源符号とすることとしたので、各制約式を実数体上の線形制約条件とみなし、また、線形の目的関数を用いることによって、符号語長の長短に関わらず効率的にタイプ一定符号を生成する符号化を実現することができるという効果を奏する。
【００２９】
また、本発明によれば、目的関数は、情報源出力をｘｎ、復号化器出力をｙｎ、符号語長をｎ、タイプをＰ、ｐを０＜ｐ＜１、ｑを０＜ｑ＜１、Ｄ（ｐ‖ｑ）をＤ（ｐ‖ｑ）＝ｐｌｏｇ（ｐ／ｑ）＋（１−ｐ）ｌｏｇ（（１−ｐ）／（１−ｑ））、系列ｒｎにおけるａの出現回数をＮ（ａ｜ｒｎ）、所定の条件付確率をＷＹ｜Ｘとした場合に、（Ｎ（０｜ｙｎ）／ｎ）Ｄ（（ｎＰ−ｍ）／Ｎ（０｜ｘｎ）‖ＷＹ｜Ｘ（１｜０））＋（Ｎ（１｜ｙｎ）／ｎ）Ｄ（ｍ／Ｎ（１｜ｙｎ）‖ＷＹ｜Ｘ（１｜１））とあらわされることとしたので、タイプ一定符号を生成する符号化を効率よく行うことができるという効果を奏する。
【００３０】
また、本発明によれば、所定の自然数は、０以上、かつ、ハミング重みまたは情報源出力の要素が１である桁の個数のうち小さいほうの値以下であって、それぞれの所定の自然数について、第１の制約式、第２の制約式および第３の制約式をすべて満たす復号化器出力についての実行可能解が存在するか否かについて判定し、実行可能解が存在すると判定した場合に、目的関数の値を算出することとしたので、符号化に関する処理負荷を低減することができるという効果を奏する。
【００３１】
また、本発明によれば、符号化に用いられた第１の疎行列、第２の疎行列、所定のハミング重みを有する１行の横行列および所定のタイプを記憶し、復号化器出力と第１の疎行列との積がタイプと等値であるとする第１の制約式、復号化器出力と第２の疎行列との積が有歪み情報源符号と等値であるとする第２の制約式、および、復号化器出力の符号語長とタイプとの積であるハミング重みが復号化器出力の要素が１である桁の個数と等値であるとする第３の制約式を用い、第１の制約式、第２の制約式および第３の制約式を緩和法によって実数体上の線形制約条件へ変換したうえで、これらの線形制約条件をすべて満たす復号化器出力を線形計画法で求解することとしたので、各制約式を実数体上の線形制約条件とみなすことで、タイプ一定符号を効率よく復号化することができるという効果を奏する。
【図面の簡単な説明】
【００３２】
【図１】図１は、通信路符号化問題および有歪み情報源符号化問題を示す図である。
【図２】図２は、本発明に係る符号化手法および復号化手法の概要を示す図である。
【図３】図３は、通信路符号に関する符号化装置の構成を示すブロック図である。
【図４】図４は、通信路符号に関する符号化装置が実行する処理手順を示すフローチャートである。
【図５】図５は、通信路符号に関する復号化装置の構成を示すブロック図である。
【図６】図６は、通信路符号に関する復号化装置が実行する処理手順を示すフローチャートである。
【図７】図７は、有歪み情報源符号に関する符号化装置の構成を示すブロック図である。
【図８】図８は、有歪み情報源符号に関する符号化装置が実行する処理手順を示すフローチャートである。
【図９】図９は、有歪み情報源符号に関する復号化装置の構成を示すブロック図である。
【図１０】図１０は、有歪み情報源符号に関する復号化装置が実行する処理手順を示すフローチャートである。
【発明を実施するための形態】
【００３３】
以下に添付図面を参照して、本発明に係る符号化装置、復号化装置、符号化方法、復号化方法、符号化プログラムおよび復号化プログラムの実施例を詳細に説明する。なお、以下では、本発明の適用対象となる通信路符号問題および有歪み情報源符号問題について図１を、本発明の概要について図２を、それぞれ用いて説明した後に、本発明を適用した実施例について図３〜図１０を用いて説明することとする。
【００３４】
まず、本発明の適用対象となる通信路符号問題および有歪み情報源符号問題について図１を用いて説明する。図１は、通信路符号問題および有歪み情報源符号問題を示す図である。なお、同図の（Ａ）には、通信路符号問題を、同図の（Ｂ）には、有歪み情報源符号問題を、それぞれ示している。また、通信路符号は誤り訂正符号と、有歪み情報源符号はベクトル量子化と、それぞれ呼ばれる場合もある。
【００３５】
最初に、図１の（Ａ）に示した通信路符号問題の課題について説明する。なお、有歪み情報源符号に関しても同様な課題が存在する。
【００３６】
図１の（Ａ）に示したように、送り手である符号化器（Φｎ）は、メッセージｕｋ∈｛０，１｝ｋを符号化し、符号語ｘｎを、通信路へ送り出す。通信路は、入力として受け付けた符号語ｘｎを、通信路出力ｙｎとして出力する。ここで、通信路は、同図に示す条件付き確率ＷＹ｜Ｘ（なお、ここでは、ＹおよびＸの添字ｎの記載を省略している）としてあらわされる。また、受け手である復号化器（Ψｎ）は、通信路出力ｙｎを受け取り、メッセージｕｋに対応する復元メッセージ（（＾：ハット記号）付きのｕｋ）を復号化する。
【００３７】
ここで、図１の（Ａ）に示した系に対してタイプ一定符号を導入した場合について説明する。タイプ一定符号は、あらかじめ与えられたタイプをＰ（０＜Ｐ＜１）、各符号語の符号語長をｎとした場合に、ハミング重みｎＰをもつ符号語のことを指す。
【００３８】
一方、クロスオーバー確率がδの２値対称通信路ＢＳＣ（δ）の通信路容量Ｃは、
Ｃ＝１−Ｈｂ（δ）
ただし、Ｈｂ（δ）＝−δｌｏｇδ−（１−δ）ｌｏｇ（１−δ）
によって与えられることが知られている。
【００３９】
したがって、タイプ一定符号は、ｎＣｎＰ個の符号語の候補の中から２ｎＣ個の符号語を選ぶことによって生成されることになる。しかし、かかる符号語の選択操作に要する計算量は、符号語長ｎに関して指数的に増加することが明らかである。このため、従来は、任意の符号語長ｎのタイプ一定符号を効率的に算出することはできなかった。
【００４０】
そこで、本発明では、任意の符号語長ｎのタイプ一定符号を効率的に生成する符号化手法と、かかる符号化手法によって符号化された符号を効率的に復号する復号化手法を提供することとした。
【００４１】
ここで、本発明に係る符号化手法および復号化手法の概要について図２を用いて説明しておく。なお、同図の（Ａ−１）には、通信路符号に関する符号化手法の概要について、同図の（Ａ−２）には、通信路符号に関する復号化手法の概要について、それぞれ示している。
【００４２】
図２の（Ａ−１）に示したように、本発明に係る符号化手法では、
制約式：Σｘｉ＝ｎＰ
ただし、Σｘｉは、ｉ＝１からｎまでのｘｉの総和
を拘束条件の１つとして含む符号化器Φｎを構成することとした。ここで、かかる制約式は、符号語ｘｎの各要素ｘｉが１である桁の個数が、ハミング重みｎＰと等しいことを意味するものである。
【００４３】
このように、図２の（Ａ−１）に示した制約式は、符号語のハミング重みが一定であること、すなわち、符号語がタイプ一定符号であることをあらわしているが、かかる制約式を拘束条件の１つとして含んだ符号化器は、従来提供されていなかった。
【００４４】
これは、符号語のハミング重みが一定である旨の制約式を拘束条件の１つとしたとしても、そもそも、各拘束条件における行列演算が２値の体（たい）である体Ｆ２上の演算であるため、全ての拘束条件を満たす符号語ｘｎを線形的な計算で求めることは不可能であると認識されていたからであると考えられる。
【００４５】
しかしながら、本発明に係る符号化手法では、かかる拘束条件を、実数体上の線形制約条件へ変換する手法である緩和法（上記した非特許文献４参照）を用いて線形制約条件へ変換し、符号語ｘｎを線形計画法で求解することとした。
【００４６】
したがって、本発明に係る符号化手法によれば、従来においては符号語長ｎに関して指数的に増加すると考えられていたタイプ一定符号の計算量を、多項式オーダーの計算量に抑えることができる。すなわち、符号語長ｎを増加させていった場合であっても、タイプ一定符号の生成に要する処理負荷が符号語長ｎに関して指数的に増加することはない。このため、符号語長ｎの長短に関わらずタイプ一定符号を効率的に生成することができる。
【００４７】
また、図２の（Ａ−２）に示したように、本発明に係る復号化手法においても、
制約式：Σｘｉ＝ｎＰ
ただし、Σｘｉは、ｉ＝１からｎまでのｘｉの総和
を拘束条件の１つとして含む復号化器Ψｎを構成することとした。
【００４８】
そして、全ての拘束条件を、上記した緩和法を用いて線形制約条件へ変換し、線形制約条件のもと、あらたに導出した線形の目的関数を最小とする符号語ｘｎを線形計画法で求解することとした。また、求解した符号語ｘｎに対して所定の疎行列Ｂを乗じた推定メッセージ（符号化前のメッセージに対応）を算出することとした。なお、かかる目的関数の詳細については後述することとする。
【００４９】
したがって、本発明に係る復号化手法によれば、符号語長ｎが大きい場合であっても、タイプ一定符号を効率的に復号化することができる。なお、本発明の通信路符号に関する詳細な説明については、後述する実施例１にて行うこととする。
【００５０】
図１の説明に戻り、図１の（Ｂ）に示した有歪み情報源符号問題の課題について説明する。図１の（Ｂ）に示したように、情報源は確率ＰＸ（なお、ここでは、Ｘの添字ｎの記載を省略している）で与えられる。そして、情報源から情報源出力ｘｎを受け取った符号化器Φｎでは、情報源出力ｘｎをｕｋへ符号化することによって圧縮操作を実行する。また、受け手である復号化器Ψｎは、受け取った符号語ｕｋを、復元メッセージｙｎとして復号化する。なお、復元メッセージｙｎを、復号化器出力と呼ぶこともできる。
【００５１】
そして、歪み測度を「ｄ：｛０，１｝×｛０，１｝→［０，∞］」とすると、情報源出力ｘｎおよび復号化器出力ｙｎは、あらかじめ与えられた歪み基準Ｄ（Ｄ＞０）に対し、
（１／ｎ）Σｄ（ｘｉ，ｙｉ）＜Ｄ
ただし、Σｄ（ｘｉ，ｙｉ）は、ｉ＝１からｎまでのｄ（ｘｉ，ｙｉ）の総和
を満足することが要請される。
【００５２】
ここで、図１の（Ｂ）に示した系に対してタイプ一定符号を導入した場合についても、図１の（Ａ）に示した系と同様の問題が発生する。すなわち、符号語長ｎを増加させていくとタイプ一定符号の生成に要する処理負荷が符号語長ｎに関して指数的に増加してしまっていた。
【００５３】
そこで、本発明では、有歪み情報源符号についても、任意の符号語長ｎのタイプ一定符号を効率的に生成する符号化手法と、かかる符号化手法によって符号化された符号を効率的に復号する復号化手法を提供することとした。なお、本発明の有歪み情報源符号に関する詳細な説明については、後述する実施例２にて行うこととする。
【実施例１】
【００５４】
本実施例１では、本発明を通信路符号に対して適用した場合について説明する。まず、符号化装置の構成について図３を用いて説明する。図３は、通信路符号に関する符号化装置１０の構成を示すブロック図である。
【００５５】
図３に示すように、符号化装置１０は、入力部１１と、記憶部１２と、制御部１３と、出力部１４とを備えている。また、記憶部１２は、疎行列１２ａと、ベクトル１２ｂと、タイプ１２ｃとを記憶し、制御部１３は、最適化実行部１３ａをさらに備えている。
【００５６】
入力部１１は、符号化の対象となるメッセージｕｋ（ｕｋ∈｛０，１｝ｋ）を受け付け、受け付けたメッセージｕｋを制御部１３へ渡す処理を行うデバイスである。また、出力部１４は、制御部１３から符号語ｘｎを受け取り、受け取った符号語ｘｎを図示しない通信路に対して出力する処理を行うデバイスである。
【００５７】
記憶部１２は、ハードディスクドライブや不揮発性メモリといった記憶デバイスで構成される記憶部であり、疎行列１２ａと、ベクトル１２ｂと、タイプ１２ｃとを記憶する。疎行列１２ａは、ｎ行×ｌ列の疎行列Ａと、ｎ行×ｋ列の疎行列Ｂとを含んでいる。ここで、ｎは、符号語長である。
【００５８】
また、ベクトル１２ｂは、ハミング重み（ｎＰ：ただし、ｎＰは自然数）が２の１行×ｌ列のｌ次元横ベクトルｃ２である。なお、本実施例１では、ハミング重みが２であるｌ次元横ベクトルを用いる場合について説明するが、ハミング重みが０以外の他の偶重み（たとえば、４や６など）となるｌ次元横ベクトルを用いることとしてもよい。
【００５９】
タイプ１２ｃは、所定の値をとるタイプＰ（ただし、符号語長ｎ×タイプＰは自然数）を含んでいる。なお、疎行列１２ａ、ベクトル１２ｂおよびタイプ１２ｃは、あらかじめ定められており、静的な値をとる。なお、以下の説明では、疎行列１２ａ、ベクトル１２ｂおよびタイプ１２ｃをパラメータと呼ぶ場合もある。
【００６０】
制御部１３は、符号化装置１０に含まれる各種デバイスの全体制御を行う処理部である。また、最適化実行部１３ａは、記憶部１２から各パラメータを読み出すとともに、入力部１１から受け取ったメッセージｕｋからタイプ一定符号である符号語ｘｎを生成して出力部１４へ渡す処理を行う処理部である。
【００６１】
以下では、この最適化実行部１３ａが行う処理内容についてさらに詳細に説明する。なお、以下の説明で用いるａあるいはｂは、任意の２値数であるものとする。
【００６２】
図１の（Ａ）で既に説明したように、通信路は、入力ｘが与えられた場合の出力ｙに関する条件付確率ＷＹ｜Ｘ（なお、ここでは、ＹおよびＸの添字ｎの記載を省略している）であらわされる。また、符号語長をｎ、疎行列Ａの列数をｌ、疎行列Ｂの列数をｋ、Ｘに関するエントロピーをＨ（Ｘ）、Ｘに関する条件付エントロピーをＨ（Ｘ｜Ｙ）とした場合、
【数１】
2011041081.tif 000003
式（ａ１）および式（ａ２）が満足されるものとする。
【００６３】
そして、ＰをＸ上の確率分布、ＷＹ｜Ｘを条件付確率とすると、Ｘに関するエントロピーＨ（Ｘ）は、
【数２】
2011041081.tif 000004
式（ａ３）で与えられる。
【００６４】
また、Ｘに関する条件付エントロピーＨ（Ｘ｜Ｙ）は、
【数３】
2011041081.tif 000005
式（ａ４）で与えられる。ただし、式（ａ４）は、式（ａ５）を満足するものとする。
【００６５】
この場合、最適化実行部１３ａが有する符号化器「Φｎ：｛０，１｝ｋ→｛０，１｝ｎ」は、入力されるメッセージをｕｋ∈｛０，１｝ｋとすると、
【数４】
2011041081.tif 000006
式（１）としてあらわされる。なお、ｃ２は、ハミング重みが２のｌ次元横ベクトル（ベクトル１２ｂ）であり、ｘｉは、ｘｎの第ｉ成分（ｉ桁目）である。
【００６６】
ここで、式（１）を線形計画問題とみなすことができれば、既存の効率のよい算出アルゴリズムを適用することが可能となる。しかし、式（１）の各拘束条件における行列演算は、２値の体（たい）である体Ｆ２上の演算であるため、このままでは、線形計画問題とはならない。
【００６７】
そこで、最適化実行部１３ａでは、式（１）の各拘束条件を、緩和法（上記した非特許文献４参照）を用いて線形制約条件へ変換し、これらの線形制約条件を満たす符号語ｘｎを、線形計画法を用いて求めることとした。
【００６８】
これにより、従来においては符号語長ｎに関して指数的に増加すると考えられていたタイプ一定符号の計算量を、多項式オーダーの計算量に抑えることができる。したがって、図３に示した符号化装置１０によれば、符号語長の長短に関わらず効率的にタイプ一定符号を生成する符号化を実現することができる。
【００６９】
次に、通信路符号に関する符号化装置１０が実行する処理手順について図４を用いて説明する。図４は、通信路符号に関する符号化装置１０が実行する処理手順を示すフローチャートである。
【００７０】
図４に示すように、入力部１１へメッセージｕｋ∈｛０，１｝ｋが入力されると（ステップＳ１０１）、最適化実行部１３ａは、記憶部１２から各パラメータを読み出す（ステップＳ１０２）。
【００７１】
そして、式（１）の各拘束条件、すなわち、ｘｎＡ＝ｃ２、ｘｎＢ＝ｕｋおよびΣｘｉ＝ｎＰをすべて満たす符号語ｘｎを、緩和法を併用した線形計画法で算出する（ステップＳ１０３）。そして、ステップＳ１０３で算出されたｘｎを符号語として出力部１４へ渡し（ステップＳ１０４）、処理を終了する。
【００７２】
次に、図３に示した符号化装置１０によって符号化された符号語を復号化する復号化装置について説明する。図５は、通信路符号に関する復号化装置２０の構成を示すブロック図である。
【００７３】
図５に示すように、復号化装置２０は、入力部２１と、記憶部２２と、制御部２３と、出力部２４とを備えている。また、記憶部２２は、疎行列２２ａと、ベクトル２２ｂと、タイプ２２ｃとを記憶し、制御部２３は、最適化実行部２３ａをさらに備えている。
【００７４】
入力部２１は、通信路出力ｙｎ（ｙｎ∈｛０，１｝ｎ）を受け付け、受け付けた通信路出力ｙｎを制御部２３へ渡す処理を行うデバイスである。また、出力部２４は、制御部２３から推定メッセージｘｎＢを受け取り、受け取った推定メッセージｘｎＢを出力する処理を行うデバイスである。
【００７５】
記憶部２２は、ハードディスクドライブや不揮発性メモリといった記憶デバイスで構成される記憶部であり、疎行列２２ａと、ベクトル２２ｂと、タイプ２２ｃとを記憶する。疎行列２２ａは、ｎ行×ｌ列の疎行列Ａと、ｎ行×ｋ列の疎行列Ｂとを含んでいる。ここで、ｎは、符号語長である。なお、疎行列Ａおよび疎行列Ｂは、図３に示した符号化装置１０の記憶部１２に記憶される疎行列１２ａと同一である。
【００７６】
また、ベクトル２２ｂは、ハミング重み（ｎＰ：ただし、ｎＰは自然数）が２の１行×ｌ列のｌ次元横ベクトルｃ２であり、図３に示した符号化装置１０の記憶部１２に記憶されるベクトル１２ｂと同一である。そして、タイプ２２ｃについても、図３に示した符号化装置１０の記憶部１２に記憶されるタイプ１２ｃと同一である。なお、以下の説明では、疎行列２２ａ、ベクトル２２ｂおよびタイプ２２ｃをパラメータと呼ぶ場合もある。
【００７７】
制御部２３は、復号化装置２０に含まれる各種デバイスの全体制御を行う処理部である。また、最適化実行部２３ａは、記憶部２２から各パラメータを読み出すとともに、入力部２１から受け取った通信路出力ｙｎから推定メッセージｘｎＢを生成して出力部２４へ渡す処理を行う処理部である。
【００７８】
以下では、この最適化実行部２３ａが行う処理内容についてさらに詳細に説明する。なお、以下の説明で用いるａあるいはｂは、任意の２値数であるものとする。
【００７９】
最適化実行部２３ａが有する復号化器「Ψｎ：｛０，１｝ｎ→｛０，１｝ｋ」は、通信路出力をｙｎ∈｛０，１｝ｎとすると、
【数５】
2011041081.tif 000007
式（２）としてあらわされる。なお、Ｈ（ｘｎ｜ｙｎ）は、系列ｘｎおよび系列ｙｎの同時経験確率分布から導かれる条件付エントロピーである。
【００８０】
また、
【数６】
2011041081.tif 000008
式（ａ６）は、式（ａ７）を達成するｘをあらわす。
【００８１】
ここで、式（２）を線形計画問題とみなすことができれば、既存の効率のよい算出アルゴリズムを適用することが可能となる。しかし、式（２）の各拘束条件における行列演算は、２値の体（たい）である体Ｆ２上の演算であるため、このままでは、線形計画問題とはならない。さらに、式（２）の目的関数は、変数ｘｉに関して線形ではない。
【００８２】
そこで、最適化実行部２３ａでは、式（２）の各拘束条件を、緩和法（上記した非特許文献４参照）を用いて線形制約条件へ変換することとした。さらに、式（２）の目的関数については、実行可能解を求める以下の方式を用いることとした。
【００８３】
具体的には、通信路出力をｙｎ、Ｎ（ａ｜ｙｎ）＝｛系列ｙｎにおけるａの出現回数｝、自然数ｍを
【数７】
2011041081.tif 000009
式（３）とした場合、式（２）に示した復号化器Ψｎを、
【数８】
2011041081.tif 000010
式（４）へ置き換えることとした。
【００８４】
ただし、Ｈｂ（δ）＝−δｌｏｇδ−（１−δ）ｌｏｇ（１−δ）である。また、ｘｉは、ｘｎの第ｉ成分（ｉ桁目）であり、ｙｉは、ｙｎの第ｉ成分（ｉ桁目）である。
【００８５】
すなわち、式（４）は、線形の拘束条件の下で、目的関数である
【数９】
2011041081.tif 000011
式（４’）を最小にするｘｎを求めるものである。
【００８６】
そして、最適化実行部２３ａは、各ｍに対して式（４）の実行可能解の有無を判別し、実行可能解が存在する場合には、式（４’）を計算する手順を繰り返すことによって、最終的に、式（４’）の最小値を与えるｘｎを求める。
【００８７】
ここで、注目すべきは、上記した手順は、線形計画法を適用することですべて実行できる点である。すなわち、従来においては符号語長ｎに関して指数的に増加すると考えられていたタイプ一定符号の計算量を、多項式オーダーの計算量に抑えることができる。このように、本発明は、条件付エントロピーが目的関数である場合における最適化の実現アルゴリズムをあらたに提案するものでもある。
【００８８】
次に、通信路符号に関する復号化装置２０が実行する処理手順について図６を用いて説明する。図６は、通信路符号に関する復号化装置２０が実行する処理手順を示すフローチャートである。
【００８９】
図６に示すように、入力部２１へ通信路出力ｙｎ∈｛０，１｝ｎが入力されると（ステップＳ２０１）、最適化実行部２３ａは、記憶部２２から各パラメータを読み出す（ステップＳ２０２）。
【００９０】
そして、式（４）の各拘束条件、すなわち、ｘｎＡ＝ｃ２、Σｘｉ＝ｎＰおよびΣｙｉｘｉ＝ｍをすべて満たし、かつ、目的関数（式（４’）参照）を最小とするｘｎを、緩和法を併用した線形計画法で算出する（ステップＳ２０３）。そして、ステップＳ２０３で算出されたｘｎと疎行列Ｂとの積であるｘｎＢを推定メッセージとして出力部２４へ渡し（ステップＳ２０４）、処理を終了する。
【００９１】
上述してきたように、実施例１では、記憶部が、第１の疎行列、第２の疎行列、所定のハミング重みを有する１行の横行列および所定のタイプを記憶し、最適化実行部が、符号語と第１の疎行列との積がタイプと等値であるとする第１の制約式、符号語と第２の疎行列との積が２値メッセージと等値であるとする第２の制約式、および、符号語の符号語長とタイプとの積であるハミング重みが符号語の要素が１である桁の個数と等値であるとする第３の制約式を用い、第１の制約式、第２の制約式および第３の制約式を緩和法によって実数体上の線形制約条件へ変換したうえで、これらの線形制約条件をすべて満たす符号語を線形計画法で求解するように符号化装置を構成した。したがって、符号語長の長短に関わらず効率的にタイプ一定符号を生成する符号化を実現することができる。また、典型系列を用いた符号よりもシャノン限界に近い伝送容量を実現することができる。
【００９２】
また、実施例１では、記憶部が、符号化に用いられた第１の疎行列、第２の疎行列、所定のハミング重みを有する１行の横行列および所定のタイプを記憶し、最適化実行部が、符号化された２値メッセージをあらわす符号語と第１の疎行列との積がタイプと等値であるとする第１の制約式、符号語の符号語長とタイプとの積であるハミング重みが符号語の要素が１である桁の個数と等値であるとする第２の制約式、符号語の要素と通信路出力の要素とが双方とも１である桁の個数が所定の自然数と等値であるとする第３の制約式、および、符号語に関して線形な目的関数を用い、第１の制約式、第２の制約式および第３の制約式を緩和法によって実数体上の線形制約条件へ変換したうえで、これらの線形制約条件をすべて満たす符号語のうち、目的関数を最小とする符号語を線形計画法で求解し、求解した符号語と第２の疎行列との積を２値メッセージとするように復号化装置を構成した。したがって、タイプ一定符号を効率よく復号化することができる。
【００９３】
以下に示す実施例２では、本発明を有歪み情報源符号に対して適用した場合について説明する。
【実施例２】
【００９４】
本実施例２では、本発明を有歪み情報源符号に対して適用した場合について説明する。まず、符号化装置の構成について図７を用いて説明する。図７は、有歪み情報源符号に関する符号化装置３０の構成を示すブロック図である。
【００９５】
図３に示すように、符号化装置３０は、入力部３１と、記憶部３２と、制御部３３と、出力部３４とを備えている。また、記憶部３２は、疎行列３２ａと、ベクトル３２ｂと、タイプ３２ｃとを記憶し、制御部３３は、最適化実行部３３ａをさらに備えている。
【００９６】
入力部３１は、符号化の対象となる情報源出力ｘｎ（ｘｎ∈｛０，１｝ｎ）を受け付け、受け付けた情報源出力ｘｎを制御部３３へ渡す処理を行うデバイスである。また、出力部３４は、制御部３３から符号語ｙｎＢを受け取り、受け取った符号語ｙｎＢを出力する処理を行うデバイスである。
【００９７】
記憶部３２は、ハードディスクドライブや不揮発性メモリといった記憶デバイスで構成される記憶部であり、疎行列３２ａと、ベクトル３２ｂと、タイプ３２ｃとを記憶する。疎行列３２ａは、ｎ行×ｌ列の疎行列Ａと、ｎ行×ｋ列の疎行列Ｂとを含んでいる。ここで、ｎは、符号語長である。
【００９８】
また、ベクトル３２ｂは、ハミング重み（ｎＰ：ただし、ｎＰは自然数）が２の１行×ｌ列のｌ次元横ベクトルｃ２である。なお、本実施例２では、ハミング重みが２であるｌ次元横ベクトルを用いる場合について説明するが、ハミング重みが０以外の他の偶重み（たとえば、４や６など）となるｌ次元横ベクトルを用いることとしてもよい。
【００９９】
タイプ３２ｃは、所定の値をとるタイプＰ（ただし、符号語長ｎ×タイプＰは自然数）を含んでいる。なお、疎行列３２ａ、ベクトル３２ｂおよびタイプ３２ｃは、あらかじめ定められており、静的な値をとる。なお、以下の説明では、疎行列３２ａ、ベクトル３２ｂおよびタイプ３２ｃをパラメータと呼ぶ場合もある。
【０１００】
制御部３３は、符号化装置３０に含まれる各種デバイスの全体制御を行う処理部である。また、最適化実行部３３ａは、記憶部３２から各パラメータを読み出すとともに、入力部３１から受け取った情報源出力ｘｎからタイプ一定符号である復号化器出力ｙｎを生成し、生成したｙｎと疎行列Ｂとの積である符号語ｙｎＢを出力部３４へ渡す処理を行う処理部である。
【０１０１】
以下では、この最適化実行部３３ａが行う処理内容についてさらに詳細に説明する。なお、以下の説明で用いるａあるいはｂは、任意の２値数であるものとする。
【０１０２】
図１の（Ｂ）で既に説明したように、情報源は、確率Ｐｘであらわされる。また、情報源から情報源出力ｘｎを受け取った符号化器Φｎでは、情報源出力ｘｎをｕｋへ符号化することによって圧縮操作を実行する。
【０１０３】
そして、歪み測度を「ｄ：｛０，１｝×｛０，１｝→［０，∞］」とすると、情報源出力ｘｎおよび復号化器出力ｙｎは、あらかじめ与えられた歪み基準Ｄ（Ｄ＞０）に対し、
【数１０】
2011041081.tif 000012
式（ｂ１）を満足することが要請される。
【０１０４】
そして、疎行列Ａの列数をｌ、疎行列Ｂの列数をｋ、Ｙに関するエントロピーをＨ（Ｙ）、Ｙに関する条件付エントロピーをＨ（Ｙ｜Ｘ）とした場合、
【数１１】
2011041081.tif 000013
式（ｂ２）および式（ｂ３）が満足されるものとする。
【０１０５】
ここで、Ｙに関するエントロピーＨ（Ｙ）およびＹに関する条件付エントロピーＨ（Ｙ｜Ｘ）は、それぞれ、ＰｘをＸ上の確率分布、所定の条件付確率（たとえば、レート・歪み限界を達成する条件付隔離値）をＷＹ｜Ｘとした場合の、Ｙに関するエントロピーおよび条件付エントロピーである。そして、レート・歪み限界を達成する条件付確率ＷＹ｜Ｘは、たとえば、Arimoto-Blahutアルゴリズムを用いて求めることができる（非特許文献１参照）。
【０１０６】
この場合、最適化実行部３３ａが有する符号化器「Φｎ：｛０，１｝ｎ→｛０，１｝ｋ」は、情報源出力ｘｎ∈｛０，１｝ｎについて、
【数１２】
2011041081.tif 000014
式（５）としてあらわされる。なお、ｃ２は、ハミング重みが２のｌ次元横ベクトル（ベクトル３２ｂ）である。
【０１０７】
ここで、
【数１３】
2011041081.tif 000015
式（ｂ４）、式（ｂ５）および式（ｂ６）が満たされるものとする。なお、Ｎ（ａ，ｂ｜ｘｎｙｎ）＝｛系列ｘｎｙｎにおけるａおよびｂの同時出現回数｝であり、式（ｂ６）は、条件付ダイバージェンスである。
【０１０８】
ここで、式（５）を線形計画問題とみなすことができれば、既存の効率のよい算出アルゴリズムを適用することが可能となる。しかし、式（５）の各拘束条件における行列演算は、２値の体（たい）である体Ｆ２上の演算であるため、このままでは、線形計画問題とはならない。さらに、式（５）の目的関数は、変数ｙｉに関して線形ではない。
【０１０９】
そこで、最適化実行部３３ａでは、式（５）の各拘束条件を、緩和法（上記した非特許文献４参照）を用いて線形制約条件へ変換することとした。さらに、式（５）の目的関数については、実行可能解を求める以下の方式を用いることとした。
【０１１０】
具体的には、情報源出力をｘｎ、自然数ｍを
【数１４】
2011041081.tif 000016
式（７）とした場合、式（５）に示した符号化器Φｎを、
【数１５】
2011041081.tif 000017
式（８）へ置き換えることとした。
【０１１１】
ただし、ｐ（０＜ｐ＜１）およびｑ（０＜ｑ＜１）に対し、
【数１６】
2011041081.tif 000018
式（ｂ７）を満足するものとする。
【０１１２】
すなわち、式（８）は、線形の拘束条件の下で、目的関数である
【数１７】
2011041081.tif 000019
式（８’）を最小にするｙｎを求めるものである。
【０１１３】
そして、最適化実行部３３ａは、各ｍに対して式（８）の実行可能解の有無を判別し、実行可能解が存在する場合には、式（８’）を計算する手順を繰り返すことによって、最終的に、式（８’）の最小値を与えるｙｎを求める。
【０１１４】
ここで、注目すべきは、上記した手順は、線形計画法を適用することですべて実行できる点である。すなわち、従来においては符号語長ｎに関して指数的に増加すると考えられていたタイプ一定符号の計算量を、多項式オーダーの計算量に抑えることができる。このように、本発明は、条件付ダイバージェンスが目的関数である場合における最適化の実現アルゴリズムをあらたに提案するものでもある。
【０１１５】
次に、有歪み情報源符号に関する符号化装置３０が実行する処理手順について図８を用いて説明する。図８は、有歪み情報源符号に関する符号化装置３０が実行する処理手順を示すフローチャートである。
【０１１６】
図８に示すように、入力部３１へ情報源出力ｘｎ∈｛０，１｝ｎが入力されると（ステップＳ３０１）、最適化実行部３３ａは、記憶部３２から各パラメータを読み出す（ステップＳ３０２）。
【０１１７】
そして、式（８）の各拘束条件、すなわち、ｙｎＡ＝ｃ２、Σｙｉ＝ｎＰおよびΣｘｉｙｉ＝ｍをすべて満たし、かつ、目的関数（式（８’）参照）を最小とするｙｎを、緩和法を併用した線形計画法で算出する（ステップＳ３０３）。そして、ステップＳ３０３で算出されたｙｎと疎行列Ｂとの積であるｙｎＢを符号語として出力部３４へ渡し（ステップＳ３０４）、処理を終了する。
【０１１８】
次に、図７に示した符号化装置３０によって符号化された符号語を復号化する復号化装置について説明する。図９は、有歪み情報源符号に関する復号化装置４０の構成を示すブロック図である。
【０１１９】
図９に示すように、復号化装４０は、入力部４１と、記憶部４２と、制御部４３と、出力部４４とを備えている。また、記憶部４２は、疎行列４２ａと、ベクトル４２ｂと、タイプ４２ｃとを記憶し、制御部４３は、最適化実行部４３ａをさらに備えている。
【０１２０】
入力部４１は、符号語ｕｋ（ｕｋ∈｛０，１｝ｋ）を受け付け、受け付けた符号語ｕｋを制御部４３へ渡す処理を行うデバイスである。また、出力部４４は、制御部４３から復元メッセージｙｎを受け取り、受け取った復元メッセージｙｎを出力する処理を行うデバイスである。
【０１２１】
記憶部４２は、ハードディスクドライブや不揮発性メモリといった記憶デバイスで構成される記憶部であり、疎行列４２ａと、ベクトル４２ｂと、タイプ４２ｃとを記憶する。疎行列４２ａは、ｎ行×ｌ列の疎行列Ａと、ｎ行×ｋ列の疎行列Ｂとを含んでいる。ここで、ｎは、符号語長である。なお、疎行列Ａおよび疎行列Ｂは、図７に示した符号化装置３０の記憶部３２に記憶される疎行列３２ａと同一である。
【０１２２】
また、ベクトル４２ｂは、ハミング重み（ｎＰ：ただし、ｎＰは自然数）が２の１行×ｌ列のｌ次元横ベクトルｃ２であり、図７に示した符号化装置３０の記憶部３２に記憶されるベクトル３２ｂと同一である。そして、タイプ４２ｃについても、図７に示した符号化装置３０の記憶部３２に記憶されるタイプ３２ｃと同一である。なお、以下の説明では、疎行列４２ａ、ベクトル４２ｂおよびタイプ４２ｃをパラメータと呼ぶ場合もある。
【０１２３】
制御部４３は、復号化装置４０に含まれる各種デバイスの全体制御を行う処理部である。また、最適化実行部４３ａは、記憶部４２から各パラメータを読み出すとともに、入力部４１から受け取った符号語ｕｋから復元メッセージｙｎを生成して出力部４４へ渡す処理を行う処理部である。
【０１２４】
以下では、この最適化実行部４３ａが行う処理内容についてさらに詳細に説明する。なお、以下の説明で用いるａあるいはｂは、任意の２値数であるものとする。
【０１２５】
最適化実行部４３ａが有する復号化器「Ψｎ：｛０，１｝ｋ→｛０，１｝ｎ」は、符号化装置３０によって符号化された符号語をｕｋ∈｛０，１｝ｋとすると、
【数１８】
2011041081.tif 000020
式（６）としてあらわされる。なお、ｃ２は、ハミング重みが２のｌ次元横ベクトル（ベクトル４２ｂ）であり、ｙｉは、ｙｎの第ｉ成分（ｉ桁目）である。
【０１２６】
ここで、式（６）を線形計画問題とみなすことができれば、既存の効率のよい算出アルゴリズムを適用することが可能となる。しかし、式（６）の各拘束条件における行列演算は、２値の体（たい）である体Ｆ２上の演算であるため、このままでは、線形計画問題とはならない。
【０１２７】
そこで、最適化実行部４３ａでは、式（６）の各拘束条件を、緩和法（上記した非特許文献４参照）を用いて線形制約条件へ変換し、これらの線形制約条件を満たす符号語ｙｎを、線形計画法を用いて求めることとした。
【０１２８】
これにより、従来においては符号語長ｎに関して指数的に増加すると考えられていたタイプ一定符号の計算量を、多項式オーダーの計算量に抑えることができる。したがって、図９に示した符号化装置４０によれば、符号語長の長短に関わらず効率的にタイプ一定符号を復号化することができる。
【０１２９】
次に、有歪み情報源符号に関する復号化装置４０が実行する処理手順について図１０を用いて説明する。図１０は、有歪み情報源符号に関する復号化装置４０が実行する処理手順を示すフローチャートである。
【０１３０】
図１０に示すように、入力部４１へ符号語ｕｋ∈｛０，１｝ｋが入力されると（ステップＳ４０１）、最適化実行部４３ａは、記憶部４２から各パラメータを読み出す（ステップＳ４０２）。
【０１３１】
そして、式（６）の各拘束条件、すなわち、ｙｎＡ＝ｃ２、ｙｎＢ＝ｕｋおよびΣｙｉ＝ｎＰをすべて満たす復元メッセージｙｎを、緩和法を併用した線形計画法で算出する（ステップＳ４０３）。そして、ステップＳ４０３で算出されたｙｎを復元メッセージとして出力部４４へ渡し（ステップＳ４０４）、処理を終了する。
【０１３２】
上述してきたように、実施例２では、記憶部が、第１の疎行列、第２の疎行列、所定のハミング重みを有する１行の横行列および所定のタイプを記憶し、最適化実行部が、復号化器出力と第１の疎行列との積がタイプと同値であるとする第１の制約式、復号化器出力の符号語長とタイプとの積であるハミング重みが復号化器出力の要素が１である桁の個数と等値であるとする第２の制約式、情報源出力の要素と復号化器出力の要素とが双方とも１である桁の個数が所定の自然数と等値であるとする第３の制約式、および、復号化器出力に関して線形な目的関数を用い、第１の制約式、第２の制約式および第３の制約式を緩和法によって実数体上の線形制約条件へ変換したうえで、これらの線形制約条件をすべて満たす復号化器出力のうち、目的関数を最小とする復号化器出力を線形計画法で求解し、求解した復号化器出力と第２の疎行列との積を有歪み情報源符号とするように符号化装置を構成した。したがって、符号語長の長短に関わらず効率的にタイプ一定符号を生成する符号化を実現することができる。
【０１３３】
また、実施例２では、記憶部が、符号化に用いられた第１の疎行列、第２の疎行列、所定のハミング重みを有する１行の横行列および所定のタイプを記憶し、最適化実行部が、復号化器出力と第１の疎行列との積がタイプと等値であるとする第１の制約式、復号化器出力と第２の疎行列との積が有歪み情報源符号と等値であるとする第２の制約式、および、復号化器出力の符号語長とタイプとの積であるハミング重みが復号化器出力の要素が１である桁の個数と等値であるとする第３の制約式を用い、第１の制約式、第２の制約式および第３の制約式を緩和法によって実数体上の線形制約条件へ変換したうえで、これらの線形制約条件をすべて満たす復号化器出力を線形計画法で求解するように復号化装置を構成した。したがって、タイプ一定符号を効率よく復号化することができる。
【０１３４】
ところで、上記した各実施例において説明した各処理のうち、自動的に行われるとして説明した処理の全部または一部を手動的に行うこともでき、あるいは、手動的に行われるとして説明した処理の全部または一部を公知の手法で自動的に行うこともできる。
【０１３５】
また、図示した各装置の各構成要素は機能概念的なものであり、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、各装置の分散・統合の具体的形態は図示のものに限られず、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。
【０１３６】
さらに、各装置にて行なわれる各処理機能は、その全部または任意の一部が、コンピュータ（たとえば、パーソナルコンピュータやワークステーション）およびコンピュータで解析実行されるプログラムにて、あるいは、ワイヤードロジックによるハードウェアとして実現され得る。
【０１３７】
なお、かかるプログラムは、インターネットなどのネットワークを介して配布することができる。また、かかるプログラムは、ハードディスク、フレキシブルディスク（ＦＤ）、ＣＤ−ＲＯＭ、ＭＯ、ＤＶＤなどのコンピュータで読み取り可能な記録媒体に記録され、コンピュータによって記録媒体から読み出されることによって実行することもできる。
【産業上の利用可能性】
【０１３８】
以上のように、本発明に係る符号化装置、復号化装置、符号化方法、復号化方法、符号化プログラムおよび復号化プログラムは、符号語長の長短に関わらず効率的にタイプ一定符号を生成する符号化およびその復号化を行いたい場合に有用であり、特に、タイプ一定符号を用いる各種技術、たとえば、無線システム技術や検索技術への実装に適している。
【符号の説明】
【０１３９】
１０    符号化装置
１１    入力部
１２    記憶部
１２ａ  疎行列
１２ｂ  ベクトル
１２ｃ  タイプ
１３    制御部
１３ａ  最適化実行部
１４    出力部
２０    復号化装置
２１    入力部
２２    記憶部
２２ａ  疎行列
２２ｂ  ベクトル
２２ｃ  タイプ
２３    制御部
２３ａ  最適化実行部
２４    出力部
３０    符号化装置
３１    入力部
３２    記憶部
３２ａ  疎行列
３２ｂ  ベクトル
３２ｃ  タイプ
３３    制御部
３３ａ  最適化実行部
３４    出力部
４０    復号化装置
４１    入力部
４２    記憶部
４２ａ  疎行列
４２ｂ  ベクトル
４２ｃ  タイプ
４３    制御部
４３ａ  最適化実行部
４４    出力部
【図１】
2011041081.tif 000021
【図２】
2011041081.tif 000022
【図３】
2011041081.tif 000023
【図４】
2011041081.tif 000024
【図５】
2011041081.tif 000025
【図６】
2011041081.tif 000026
【図７】
2011041081.tif 000027
【図８】
2011041081.tif 000028
【図９】
2011041081.tif 000029
【図１０】
2011041081.tif 000030