(57)【要約】【課題】主アルゴリズムを用いて最適化問題を解いて得られる解の中で、エラーとして処理されて捨て去られていた解を活かしてデータを符号化することを課題とする。【解決手段】掃出し部は、主アルゴリズムからの出力（解）を入力すると、主アルゴリズムからの出力（解）の中で、パリティ検査条件を満足しない不定解部分に対応するパリティ検査行列内の行インデックス（ＩｎｄＸ）を掃出し法を用いて特定し、所定の記憶部に格納する。量子化部は、不定解部分に対応する各不定解について、所定の基準で行われる量子化演算により量子化値をそれぞれ算出する。求解部は、不定解部分に対応するパリティ検査行列内のインデックスについて、量子化部により算出された量子化値をパリティ検査条件を表すｎ変数のｋ連立一次方程式にそれぞれ代入してｋ変数のｋ連立一次方程式に帰着させ、ｋ変数のｋ連立一次方程式を解いて、パリティ検査条件を満足する解ｘｎを算出する。【選択図】        図１
2010016684.tif 000002
【特許請求の範囲】
【請求項１】
データを符号化する符号化装置であって、
符号化の対象となる符号化対象データを記憶する記憶部から当該符号化対象データを読込んで、当該符号化対象データを所定のアルゴリズムを用いて符号化する符号化手段と、
前記符号化手段により前記符号化対象データが符号化された符号化結果が所定の拘束条件を満足するか否かを判定する拘束条件判定手段と、
前記拘束条件判定手段により前記符号化結果が前記所定の拘束条件を満足しないものと判定された場合には、当該所定の拘束条件を満足しない当該符号化結果内の不定部分を当該所定の拘束条件から導出する不定部分導出手段と、
前記不定部分導出手段により導出された前記不定部分を構成する要素値の各々について、所定の基準で量子化した量子化値をそれぞれ算出する量子化値算出手段と、
前記量子化値算出手段により算出された各量子化値と前記不定部分を構成する各要素値とを入れ替えて、前記所定の拘束条件を満足するような適合値を算出する適合値算出手段と、
を備えたことを特徴とする符号化装置。
【請求項２】
前記符号化手段は、最尤推定を近似するアルゴリズムを用いて前記符号化対象データを符号化した符号化結果である解を前記拘束条件判定手段に出力し、
前記拘束条件判定手段は、前記符号化手段から入力した前記解が前記所定の拘束条件を表す方程式を満足しているか否かを判定し、
前記不定部分導出手段は、前記符号化手段から入力した前記解が前記所定の拘束条件を表す方程式を満足しないものと前記拘束条件判定手段により判定された場合には、当該方程式を構成する検査行列を変形して、当該方程式を満足しない前記解の不定解部分に対応するパリティ検査行列内の行インデックスを導出し、
前記量子化値算出手段は、前記不定部分導出手段により導出された前記行インデックスに対応する解を所定の基準で量子化した量子化値をそれぞれ算出し、
前記算出手段は、前記量子化値算出手段により算出された各量子化値と前記行インデックスに対応する解とを入れ替えて、前記所定の拘束条件を表す方程式を満足するような解を算出することを特徴とする請求項１に記載の符号化装置。
【請求項３】
データを符号化する符号化方法であって、
符号化の対象となる符号化対象データを記憶する記憶部から当該符号化対象データを読込んで、当該符号化対象データを所定のアルゴリズムを用いて符号化する符号化ステップと、
前記符号化ステップにより前記符号化対象データが符号化された符号化結果が所定の拘束条件を満足するか否かを判定する拘束条件判定ステップと、
前記拘束条件判定ステップにより前記符号化結果が前記所定の拘束条件を満足しないものと判定された場合には、当該所定の拘束条件を満足しない当該符号化結果内の不定部分を当該所定の拘束条件から導出する不定部分導出ステップと、
前記不定部分導出ステップにより導出された前記不定部分を構成する要素値の各々について、所定の基準で量子化した量子化値をそれぞれ算出する量子化値算出ステップと、
前記量子化値算出ステップにより算出された各量子化値と前記不定部分を構成する各出力値と入れ替えて、前記所定の拘束条件を満足するような適合値を算出する適合値算出ステップと、
を含んだことを特徴とする符号化方法。
【請求項４】
データを符号化する処理をコンピュータに実行させる符号化プログラムであって、
符号化の対象となる符号化対象データを記憶する記憶部から当該符号化対象データを読込んで、当該符号化対象データを所定のアルゴリズムを用いて符号化する符号化手順と、
前記符号化手順により前記符号化対象データが符号化された符号化結果が所定の拘束条件を満足するか否かを判定する拘束条件判定手順と、
前記拘束条件判定手順により前記符号化結果が前記所定の拘束条件を満足しないものと判定された場合には、当該所定の拘束条件を満足しない当該符号化結果内の不定部分を当該所定の拘束条件から導出する不定部分導出手順と、
前記不定部分導出手順により導出された前記不定部分を構成する要素値の各々について、所定の基準で量子化した量子化値をそれぞれ算出する量子化値算出手順と、
前記量子化値算出手順により算出された各量子化値と前記不定部分を構成する各要素値と入れ替えて、前記所定の拘束条件を満足するような適合値を算出する適合値算出手順と、
をコンピュータに実行させることを特徴とする符号化プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、符号化装置、符号化方法および符号化プログラムに関する。
【背景技術】
【０００２】
従来より、通信技術分野などにおいて、文字や画像、音声などのデータを少ないビット数で効率的に圧縮し、大容量のデータを格納したり、転送したりすることを目的として、文字や画像、音声などのデータを符号化する符号化技術が存在する（例えば、非特許文献１参照）。
【０００３】
上述した符号化技術では、例えば、有限体Ｆ２＝｛０，１｝上で、以下の（１）式に示す最適化問題（以下、適宜、「最適化問題」と記載する）を解いて得られる解の中から、所定の拘束条件を満足するものを最適値として選択し、データを圧縮するための符号として利用するのが一般的である。
【０００４】
しかし、最適化問題を厳密に解くためには指数オーダーの計算量が必要となって効率的ではないので、ｓｕｍ−ｐｒｏｄｕｃｔ法やＬＰ緩和法などのアルゴリズム（以下、適宜、「既存アルゴリズム」と記載する）を用いて、最適化問題を近似的に解く方法が提案されている。
【０００５】
【数１】
2010016684.tif 000003
【０００６】
なお、上記（１）内の「Ｘn（＝Ｘ１,・・・,Ｘn）」は、確率分布ＰXに従い、独立同分布で出現する確率変数であり、「Ａ」は、ｎ行ｋ列の行列であり、「ｃ」は、１行ｋ列の横ベクトルである。
【０００７】
【非特許文献１】和田山  正，「低密度パリティ検査符号とその復号法」，トリケップス，２００２”
【発明の開示】
【発明が解決しようとする課題】
【０００８】
しかしながら、既存アルゴリズムを用いて最適化問題を解いて得られる解の中で、所定の拘束条件（パリティ検査条件）を満足しない解については、エラーとして処理されて捨てられていたという問題点があった。
【０００９】
すなわち、エラーとして処理されて利用されない解の中には、所定の拘束条件（パリティ検査条件）を満足する最適値にほど遠くなく、利用価値のあるものが存在する。
【００１０】
したがって、エラーとして処理されて利用されない解を利用して、所定の拘束条件を満足するような解を導き出す方法が求められている。
【００１１】
そこで、この発明は、上述した従来技術の課題を解決するためになされたものであり、既存アルゴリズムを用いて最適化問題を解いて得られる解の中で、エラーとして処理されて捨て去られていた解を活かしてデータを符号化することが可能な符号化装置、符号化方法および符号化プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１２】
上述した課題を解決し、目的を達成するため、本発明は、データを符号化する符号化装置であって、符号化の対象となる符号化対象データを記憶する記憶部から当該符号化対象データを読込んで、当該符号化対象データを所定のアルゴリズムを用いて符号化する符号化手段と、前記符号化手段により前記符号化対象データが符号化された符号化結果が所定の拘束条件を満足するか否かを判定する拘束条件判定手段と、前記拘束条件判定手段により前記符号化結果が前記所定の拘束条件を満足しないものと判定された場合には、当該所定の拘束条件を満足しない当該符号化結果内の不定部分を当該所定の拘束条件から導出する不定部分導出手段と、前記不定部分導出手段により導出された前記不定部分を構成する要素値の各々について、所定の基準で量子化した量子化値をそれぞれ算出する量子化値算出手段と、前記量子化値算出手段により算出された各量子化値と前記不定部分を構成する各要素値とを入れ替えて、前記所定の拘束条件を満足するような適合値を算出する適合値算出手段と、を備えたことを特徴とする。
【００１３】
また、本発明は、データを符号化する符号化方法であって、符号化の対象となる符号化対象データを記憶する記憶部から当該符号化対象データを読込んで、当該符号化対象データを所定のアルゴリズムを用いて符号化する符号化ステップと、前記符号化ステップにより前記符号化対象データが符号化された符号化結果が所定の拘束条件を満足するか否かを判定する拘束条件判定ステップと、前記拘束条件判定ステップにより前記符号化結果が前記所定の拘束条件を満足しないものと判定された場合には、当該所定の拘束条件を満足しない当該符号化結果内の不定部分を当該所定の拘束条件から導出する不定部分導出ステップと、前記不定部分導出ステップにより導出された前記不定部分を構成する要素値の各々について、所定の基準で量子化した量子化値をそれぞれ算出する量子化値算出ステップと、前記量子化値算出ステップにより算出された各量子化値と前記不定部分を構成する各出力値と入れ替えて、前記所定の拘束条件を満足するような適合値を算出する適合算出ステップと、を含んだことを特徴とする。
【００１４】
また、本発明は、データを符号化する処理をコンピュータに実行させる符号化プログラムであって、符号化の対象となる符号化対象データを記憶する記憶部から当該符号化対象データを読込んで、当該符号化対象データを所定のアルゴリズムを用いて符号化する符号化手順と、前記符号化手順により前記符号化対象データが符号化された符号化結果が所定の拘束条件を満足するか否かを判定する拘束条件判定手順と、前記拘束条件判定手順により前記符号化結果が前記所定の拘束条件を満足しないものと判定された場合には、当該所定の拘束条件を満足しない当該符号化結果内の不定部分を当該所定の拘束条件から導出する不定部分導出手順と、前記不定部分導出手順により導出された前記不定部分を構成する要素値の各々について、所定の基準で量子化した量子化値をそれぞれ算出する量子化値算出手順と、前記量子化値算出手順により算出された各量子化値と前記不定部分を構成する各要素値と入れ替えて、前記所定の拘束条件を満足するような適合値を算出する適合値算出手順と、をコンピュータに実行させることを特徴とする。
【発明の効果】
【００１５】
本発明によれば、既存アルゴリズムを用いて最適化問題を解いて得られる解の中で、エラーとして処理されて捨て去られていた解を活かしてデータを符号化することができるという効果を奏する。
【発明を実施するための最良の形態】
【００１６】
以下に添付図面を参照して、この発明に係る符号化装置、符号化方法および符号化プログラムの実施例を詳細に説明する。なお、以下では、本発明に係る符号化装置の骨子、本発明に係る符号化装置の構成および処理を順に説明し、最後に実施例１による効果を説明する。
【００１７】
［用語の説明］
以下の実施例１で用いる主要な用語について説明する。以下の実施例１に登場する共通パラメータ内の「ｎ×ｋ行列：Ａ」は、行列要素が“０”または“１”からなるパリティ検査行列であり、パリティ検査条件を構成する。
【００１８】
また、以下の実施例１に登場する共通パラメータ内の「１×ｋベクトル：ｃ」は、要素が“０”または“１”からなる定ベクトルであり、予め任意に与えられる。
【００１９】
また、以下の実施例１にパラメータとして登場する「確率分布：ＰＸ」は、有限体Ｆ２＝｛０，１｝上の確率分布を表し、例えば、「ＰＸｎ」は、ｎ個の独立同分布系列に対する確立分布を表す。
【００２０】
また、以下の実施例１で説明する主アルゴリズムからの出力「ｚｎ」は、情報源に格納されている各種データ（文字や画像、音声など）について最適化問題（上記（１）式参照）を近似的に解いて得られた解（符号）であり、出力「ｚｎ」を構成する各要素ｚｉ（
１≦ｉ≦ｎ）が０≦ｚｉ≦１を満足するものとする。
【００２１】
また、以下の実施例１で登場する「ｑ（ｚｎ）Ａ＝ｃ」（あるいは、「ｘｎＡ＝ｃ」：ｎ変数のｋ連立一次方程式）は、主アルゴリズムからの出力「ｚｎ」が満足すべきパリティ検査条件（上記（１）に示す最適化問題の拘束条件）であり、「ｑ（ｚｎ）」は、主アルゴリズムからの出力「ｚｎ」を構成する各要素ｚｉ（１≦ｉ≦ｎ）を所定の基準（主アルゴリズムに依存する）で“０”または“１”に量子化したものを表す。
【００２２】
また、以下の実施例１で登場する「ｘｎ」は、実施例１に係る符号化装置の最終出力を表し、“０”または“１”の要素からなる。
【実施例１】
【００２３】
［符号化装置の骨子（実施例１）］
まず、図１および図２を用いて、実施例１に係る符号化装置の骨子を説明する。図１は、実施例１に係る符号化装置のアルゴリズムの全体像を示す図である。図２は、実施例１に係る補助アルゴリズムの構成を示す図である。
【００２４】
実施例１に係る符号化装置は、情報源に格納されている各種データ（文字や画像、音声など）を効率的に圧縮することを目的として、主アルゴリズム（既存アルゴリズム）を用いて最適化問題を解いて得られる解により、各種データを符号化することを概要とする。
【００２５】
そして、実施例１に係る符号化装置の骨子は、主アルゴリズムを用いて最適化問題を解いて得られる解の中で、エラーとして処理されて捨て去られていた解を活かしてデータを符号化することができる点にある。
【００２６】
具体的には、実施例１に係る符号化装置は、図１に示すように、各パラメータを用いて、最適化問題（上記（１）式参照）を近似的に解く主アルゴリズムにより得られた解がパリティ検査条件を満足しなかった場合に、主アルゴリズムにより得られた解について処理を行う補助アルゴリズムにより、実施例１に係る符号化装置の骨子を実現する。
【００２７】
具体的に説明すると、実施例１に係る符号化装置の補助アルゴリズムは、図２に示すように、掃出し部と、量子化部と、求解部とから構成される。
【００２８】
そして、実施例１に係る符号化装置において、主アルゴリズムからの出力（解）が、パリティ検査条件を表すｎ変数のｋ連立一次方程式（「ｘｎＡ＝ｃ」）を満足するか否かを判定する。
【００２９】
実施例１に係る符号化装置において、判定の結果、例えば、ｎ＞ｋであることを原因として、主アルゴリズムからの出力（解）が、パリティ検査条件を満足しないものと判定された場合には、主アルゴリズムからの出力（解）が補助アルゴリズムへ出力される。
【００３０】
そこで、上記補助アルゴリズムの掃出し部は、主アルゴリズムからの出力（解）を入力すると、主アルゴリズムからの出力（解）の中で、パリティ検査条件を満足しない不定解部分に対応するパリティ検査行列内の行インデックス（ＩｎｄＸ）を掃出し法を用いて特定し、所定の記憶部に格納する（図２の（１）参照）。
【００３１】
次に、上記補助アルゴリズムの量子化部は、主アルゴリズムからの出力（解）の中で、パリティ検査条件を満足しない不定解部分に対応する各不定解について、所定の基準で行われる量子化演算により量子化値をそれぞれ算出する（図２の（２）参照）。
【００３２】
続いて、上記補助アルゴリズムの求解部は、主アルゴリズムからの出力（解）の中で、パリティ検査条件を満足しない不定解部分に対応するインデックスについて、上記の量子化部により算出された量子化値をパリティ検査条件を表すｎ変数のｋ連立一次方程式にそれぞれ代入してｋ変数のｋ連立一次方程式に帰着させ、ｋ変数のｋ連立一次連立方程式を解いて、パリティ検査条件を満足する解ｘｎを算出する（図２の（３）参照）。
【００３３】
実施例１に係る符号化装置は、上記の求解部により算出された解ｘｎによりデータを符号化する。
【００３４】
このようなことから、実施例１に係る符号化装置は、主アルゴリズムを用いて最適化問題を解いて得られる解の中で、エラーとして処理されて捨て去られていた解を活かしてデータを符号化することができる。
【００３５】
［符号化装置の構成（実施例１）］
次に、図３および図４を用いて、実施例１に係る符号化装置の構成を説明する。図３は、実施例１に係る符号化装置の適用例を示す図である。図４は、実施例１に係る符号化装置の構成を示す図である。
【００３６】
図３に示すように、実施例１に係る符号化装置は、例えば、情報源に格納されているデータ（文字や画像など）を符号化部により符号化した符号化データを、通信路を介して復号化装置に送信する。
【００３７】
符号化装置から符号化データを受信した復号化装置では、復号化部によって符号化データを復号することによりデータを取得する。
【００３８】
上述した符号化装置は、例えば、図４に示すように、情報記憶部１００と、最適化実行部２００と、補助符号化部３００とを有する。
【００３９】
情報記憶部１００は、文字や画像、音声などの各種データを記憶する記憶部である。
【００４０】
最適化実行部２００は、情報記憶部１００に記憶されている各種データを符号化するために、例えば、ｓｕｍ−ｐｒｏｄｕｃｔ法やＬＰ緩和法などの既存の主アルゴリズムを用いて最適化問題（上記（１）式参照）を近似的に解く処理部である。
【００４１】
最適化実行部２００は、計算結果である出力ｚｎを後述する補助符号化部３００に出力する。
【００４２】
補助符号化部３００は、最適化実行部２００から入力した出力ｚｎが、パリティ検査条件を満足しなかった場合に、最適化実行部２００から入力した出力ｚｎについて処理を行う処理部である。
【００４３】
そして、補助符号化部３００は、例えば、図４に示すように、行列係数記憶部３１０と、出力判定部３２０と、掃出し演算処理部３３０と、行インデックス記憶部３４０と、量子化演算部３５０と、求解演算部３６０とを有する。
【００４４】
なお、出力判定部３２０は、特許請求の範囲に記載の「拘束条件判定手段」に対応し、掃出し演算処理部３３０は、同じく特許請求の範囲に記載の「不定部分導出手段」に対応し、量子化演算部３５０は、同じく特許請求の範囲に記載の「量子化値算出手段」に対応し、求解演算部３６０は、同じく特許請求の範囲に記載の「適合値算出手段」に対応する。
【００４５】
行列係数記憶部３１０は、パリティ検査行列Ａの行列係数を記憶する記憶部である。
【００４６】
出力判定部３２０は、最適化実行部２００から入力した出力ｚｎを所定の基準で“０”もしくは“１”に量子化した後、量子化された値が、パリティ検査条件（「ｘｎＡ＝ｃ」）を満足するか否かを判定する処理部である。
【００４７】
具体的には、出力判定部３２０は、最適化実行部２００から出力ｚｎを入力すると、行列係数記憶部３１０からパリティ検査行列Ａの行列係数を読込んで、パリティ検査条件（ｎ変数のｋ連立一次方程式：「ｘｎＡ＝ｃ」）を算出する。
【００４８】
そして、出力判定部３２０は、最適化実行部２００から入力した出力ｚｎが、パリティ検査条件（ｎ変数のｋ連立一次方程式：「ｘｎＡ＝ｃ」）を満足しないものと判定した場合には、出力ｚｎを後述する量子化演算部３５０に出力する。
【００４９】
一方、出力判定部３２０は、最適化実行部２００から入力した出力ｚｎが、パリティ検査条件（「ｘｎＡ＝ｃ」）を満足するものと判定した場合には、出力ｚｎを最終出力ｘｎとして出力する。
【００５０】
なお、以下では、便宜上、パリティ検査条件であるｎ変数のｋ連立一次方程式、「ｘｎＡ＝ｃ」について、以下に示す条件（２）を採用した場合を説明する。
【００５１】
【数２】
2010016684.tif 000004
【００５２】
掃出し演算処理部３３０は、上記の出力判定部３２０によって、最適化実行部２００から入力した出力ｚｎの中に、パリティ検査条件（「ｘｎＡ＝ｃ」）を満足しないものと判定された場合に、パリティ検査条件（「ｘｎＡ＝ｃ」）を満足しない不定解部分に対応するパリティ検査条件（「ｘｎＡ＝ｃ」）内の行インデックスを特定するための掃出し演算処理を行う処理部である。
【００５３】
具体的には、掃出し演算処理部３３０は、行列係数記憶部３１０から行列係数を読込んで、例えば、上記の条件（２）に示すパリティ検査行列Ａを生成し、生成したパリティ検査行列Ａの列基本変形を実行する。列基本変形後のパリティ検査行列は、以下に示す行列（３）となる。
【００５４】
【数３】
2010016684.tif 000005
【００５５】
そして、掃出し演算処理部３３０は、列基本変形後のパリティ検査行列（上記の行列（３）参照）から、ｋ（＝３）次元の単位ベクトルを与える行を除いた残りの行のインデックスを、パリティ検査条件（「ｘｎＡ＝ｃ」）を満足しない不定解部分に対応するパリティ検査条件内の行インデックス（ＩｎｄＸ）として特定し、行インデックス記憶部３４０に格納する。
【００５６】
例えば、掃出し演算処理部３３０は、上記の条件（２）の時、パリティ検査条件（「ｘｎＡ＝ｃ」）を満足しない不定解部分に対応するインデックス（ＩｎｄＸ）として、ＩｎｄＸ＝｛２，３｝（２行目、３行目）を行インデックス記憶部３４０に格納する。
【００５７】
行インデックス記憶部３４０は、不定解部分のインデックス（ＩｎｄＸ）を記憶する記憶部であり、例えば、掃出し演算処理部３３０から格納されたＩｎｄＸ＝｛２，３｝を不定解部分に対応するパリティ検査条件内のインデックス（ＩｎｄＸ）として記憶する。
【００５８】
量子化演算部３５０は、最適化実行部２００から入力した出力ｚｎの中で、パリティ検査条件（「ｘｎＡ＝ｃ」）を満足しない不定解部分について、所定の基準で量子化演算を行って、量子化値を算出する処理部である。
【００５９】
具体的には、量子化演算部３５０は、最適化実行部２００から出力ｚｎを入力すると、パリティ検査条件（「ｘｎＡ＝ｃ」）を満足しない出力ｚｎの不定解部分（ｚｉ）について、以下に示す基準（４）で量子化演算を行い、量子化値Ｑ（ｚｉ）を算出して、求解演算部３６０に出力する。
【００６０】
【数４】
2010016684.tif 000006
【００６１】
求解演算部３６０は、パリティ検査条件（「ｘｎＡ＝ｃ」）を満足しない出力ｚｎの不定解部分（ｚｉ）について量子化演算を実行して求められた量子化値を量子化演算部３５０から入力して、パリティ検査条件（「ｘｎＡ＝ｃ」）を満足する解ｘｎを算出する処理部である。
【００６２】
具体的には、求解演算部３６０は、量子化演算部３５０から量子化値を入力すると、行インデックス記憶部３４０から読込んだ行インデックス（ＩｎｄＸ＝｛２，３｝）に基づいて、不定解部分に対応するパリティ検査条件を表す方程式「ｘｎＡ＝ｃ」内の値、ｘｉ（ｉ∈ＩｎｄＸ＝｛２，３｝）に量子化値Ｑ（ｚｉ）を代入する。
【００６３】
そして、求解演算部３６０は、ｘｉ（ｉ∈ＩｎｄＸ＝｛２，３｝）に量子化値Ｑ（ｚｉ）を代入後、パリティ検査条件を表す方程式「ｘｎＡ＝ｃ」を展開して、ｋ（＝３）変数のｋ（＝３）連立一次方程式を解くことにより、パリティ検査条件（「ｘｎＡ＝ｃ」）を満足する解ｘｎを算出する。
【００６４】
上記条件（２）の時に、求解演算部３６０が解くべき方程式は、以下の（５）式のようになる。
【００６５】
【数５】
2010016684.tif 000007
【００６６】
［符号化装置の処理（実施例１）］
続いて、図５を用いて、実施例１に係る符号化装置の処理を説明する。図５は、実施例１に係る符号化装置の処理の流れを示す図である。
【００６７】
同図に示すように、出力判定部３２０は、最適化実行部２００から入力した出力ｚｎが、パリティ検査条件（「ｘｎＡ＝ｃ」）を満足するか否かを判定する（ステップＳ５０１）。
【００６８】
判定の結果、出力判定部３２０は、最適化実行部２００から入力した出力ｚｎが、パリティ検査条件（ｎ変数のｋ連立一次方程式：「ｘｎＡ＝ｃ」）を満足しないものと判定した場合には（ステップＳ５０１否定）、出力ｚｎを量子化演算部３５０に出力する。
【００６９】
掃出し演算処理部３３０は、上記の出力判定部３２０によって、最適化実行部２００から入力した出力ｚｎの中に、パリティ検査条件（「ｘｎＡ＝ｃ」）を満足しない不定解部分が存在するものと判定された場合に、不定解部分に対応するパリティ検査条件（「ｘｎＡ＝ｃ」）内のインデックスを特定するための掃出し演算処理を行う（ステップＳ５０２）。
【００７０】
具体的には、掃出し演算処理部３３０は、行列係数記憶部３１０から行列係数を読込んで、パリティ検査行列Ａ（上記の条件（２）参照）を生成し、生成したパリティ検査行列Ａの列基本変形を実行する。
【００７１】
そして、掃出し演算処理部３３０は、列基本変形後のパリティ検査行列（上記の行列（３）参照）から、ｋ（＝３）次元の単位ベクトルを与える行を除いた残りの行のインデックスを、不定解部分に対応するパリティ検査条件内のインデックス（ＩｎｄＸ）として特定し、行インデックス記憶部３４０に格納する。
【００７２】
例えば、掃出し演算処理部３３０は、上記の条件（２）の時、パリティ検査条件（「ｘｎＡ＝ｃ」）を満足しない不定解部分に対応するインデックス（ＩｎｄＸ）として、ＩｎｄＸ＝｛２，３｝（２行目、３行目）を行インデックス記憶部３４０に格納する。
【００７３】
量子化演算部３５０は、最適化実行部２００から入力した出力ｚｎの中で、パリティ検査条件（「ｘｎＡ＝ｃ」）を満足しない不定解部分について、所定の基準で量子化演算を行って、量子化値を算出する（ステップＳ５０３）。
【００７４】
具体的には、量子化演算部３５０は、最適化実行部２００から出力ｚｎを入力すると、パリティ検査条件（「ｘｎＡ＝ｃ」）を満足しない出力ｚｎの不定解部分（ｚｉ）について、所定の基準（上記の基準（４）参照）で量子化演算を行い、量子化値Ｑ（ｚｉ）を算出して、求解演算部３６０に出力する。
【００７５】
求解演算部３６０は、パリティ検査条件（「ｘｎＡ＝ｃ」）を満足しない出力ｚｎの不定解部分（ｚｉ）について量子化演算を実行して求められた量子化値を量子化演算部３５０から入力して、パリティ検査条件（「ｘｎＡ＝ｃ」）を満足する解ｘｎを算出する（ステップＳ５０４）。
【００７６】
具体的には、求解演算部３６０は、量子化演算部３５０から量子化値を入力すると、行インデックス記憶部３４０から読込んだ行インデックス（ＩｎｄＸ＝｛２，３｝）に基づいて、不定解部分に対応するパリティ検査条件を表す方程式「ｘｎＡ＝ｃ」内の値、ｘｉ（ｉ∈ＩｎｄＸ＝｛２，３｝）に量子化値Ｑ（ｚｉ）を代入する。
【００７７】
そして、求解演算部３６０は、ｘｉ（ｉ∈ＩｎｄＸ＝｛２，３｝）に量子化値Ｑ（ｚｉ）を代入後、パリティ検査条件を表す方程式「ｘｎＡ＝ｃ」を展開して、ｋ（＝３）変数のｋ（＝３）連立一次方程式を解くことにより、パリティ検査条件（「ｘｎＡ＝ｃ」）を満足する解ｘｎを算出する。
【００７８】
求解演算部３６０は、算出した解ｘｎを最終出力として出力し（ステップＳ５０５）、符号化装置は処理を終了する。
【００７９】
ここで、ステップＳ５０１の説明に戻ると、出力判定部３２０は、判定の結果、最適化実行部２００から入力した出力ｚｎが、パリティ検査条件（ｎ変数のｋ連立一次方程式：「ｘｎＡ＝ｃ」）を満足するものと判定した場合には（ステップＳ５０１肯定）、出力ｚｎを最終出力ｘｎとして出力し（ステップＳ５０６）、符号化装置は処理を終了する。
【００８０】
［実施例１による効果］
上述してきたように、実施例１によれば、最適化実行部２００からの出力（解）がパリティ検査条件を満足しなかった場合に、最適化実行部２００からの出力（解）の中で、パリティ検査条件を満足しない不定解部分を量子化した値を用いて、補助符号化部３００によりパリティ検査条件を満足する解を算出するので、エラーとして処理されて捨て去られていた解を活かしてデータを符号化することができるという効果を奏する。
【００８１】
また、上記の実施例１で説明した補助符号化部３００の処理（例えば、図５参照）を、既存技術である有歪み情報源符号化方式（S.Miyake, J.Marumatsu,“Construction of lossy code using LDPC matrices,”Proc. 2007 IEEE Int. Symp. Inform Theory, pp.1106-1110,2007  参照）に同様に適用することもできる。
【００８２】
例えば、有歪み情報源符号化方式において、ＬＰ緩和法（J. Feldman, Decoding Error-Correcting Codes via Linear Programming, PhD dissertation, Massachusetts Institute of Technology,2003  参照）を用いて情報減を符号化して得られる出力に対して、上記の実施例１で説明した補助符号化部３００の処理を同様に適用することにより、パリティ検査条件に適合した最終出力を得ることができる。
【実施例２】
【００８３】
さて、これまで本発明の符号化装置の実施例について説明したが、本発明は上述した実施例以外にも、種々の異なる形態にて実施されてよいものである。そこで、以下では、本発明に含まれる他の実施例を説明する。
【００８４】
（１）装置構成等
図４に示した符号化装置の各構成要素は機能概念的なものであり、必ずしも物理的に図示の如く構成されていることを要しない。
【００８５】
すなわち、図４に示す符号化装置の分散・統合の具体的形態は図示のものに限られず、例えば、補助符号化部３００の出力判定部３２０と、量子化演算部３５０と、求解演算部３６０とを統合した一つの処理機能部とするなど、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。
【００８６】
さらに、図４に示す符号化装置にて行なわれる各処理機能（例えば、図５参照）は、その全部または任意の一部が、ＣＰＵおよび当該ＣＰＵにて解析実行されるプログラムにて実現され、あるいは、ワイヤードロジックによるハードウェアとして実現され得る。
【００８７】
（２）符号化プログラム
また、上記の実施例１で説明した符号化装置の各種の処理（例えば、図５等参照）は、あらかじめ用意されたプログラムをパーソナルコンピュータやワークステーションなどのコンピュータシステムで実行することによって実現することができる。
【００８８】
そこで、以下では、図６を用いて、上記の実施例１で説明した符号化装置（補助符号化部３００）と同様の機能を有する符号化プログラムを実行するコンピュータの一例を説明する。図６は、符号化プログラムを実行するコンピュータを示す図である。
【００８９】
同図に示すように、符号化装置（補助符号化部３００）としてコンピュータ４００は、入力部４１０、出力部４２０、ＨＤＤ４３０、ＲＡＭ４４０およびＣＰＵ４５０をバス５００で接続して構成される。
【００９０】
ここで、入力部４１０は、ユーザから各種データの入力を受け付ける。出力部４２０は、各種情報を表示する。ＨＤＤ４３０は、ＣＰＵ４５０による各種処理の実行に必要な情報を記憶する。ＲＡＭ４４０は、各種情報を一時的に記憶する。ＣＰＵ４５０は、各種演算処理を実行する。
【００９１】
そして、ＨＤＤ４３０には、図６に示すように、上記の実施例１に示した符号化装置（補助符号化部３００）の各処理部と同様の機能を発揮する符号化プログラム４３１と、符号化処理用データ４３２とがあらかじめ記憶されている。
【００９２】
なお、この符号化プログラム４３１を適宜分散させて、ネットワークを介して通信可能に接続された他のコンピュータの記憶部に記憶させておくこともできる。
【００９３】
そして、ＣＰＵ４５０が、この符号化プログラム４３１をＨＤＤ４３０から読み出してＲＡＭ４４０に展開することにより、図６に示すように、符号化プログラム４３１は符号化プロセス４４１として機能するようになる。
【００９４】
そして、符号化プロセス４４１は、符号化処理用データ４３２等をＨＤＤ４３０から読み出して、ＲＡＭ４４０において自身に割り当てられた領域に展開し、この展開したデータ等に基づいて各種処理を実行する。
【００９５】
なお、符号化プロセス４４１は、図４に示した符号化装置が有する補助符号化部３００の出力判定部３２０、掃出し演算処理部３３０、量子化演算部３５０および求解演算部３６０等において実行される処理にそれぞれ対応する。
【００９６】
なお、上記した符号化プログラム４３１については、必ずしも最初からＨＤＤ４３０に記憶させておく必要はなく、例えば、コンピュータ４００に挿入されるフレキシブルディスク（ＦＤ）、ＣＤ−ＲＯＭ、ＤＶＤディスク、光磁気ディスク、ＩＣカードなどの「可搬用の物理媒体」、さらには、公衆回線、インターネット、ＬＡＮ、ＷＡＮなどを介してコンピュータ４００に接続される「他のコンピュータ（またはサーバ）」などに各プログラムを記憶させておき、コンピュータ４００がこれらから各プログラムを読み出して実行するようにしてもよい。
【００９７】
（３）符号化方法
上記の実施例１で説明した符号化装置（補助符号化部３００）により、以下のような符号化方法が実現される。
【００９８】
すなわち、符号化の対象となる符号化対象データを記憶する記憶部から当該符号化対象データを読込んで、当該符号化対象データを所定のアルゴリズムを用いて符号化する符号化ステップと、符号化ステップにより符号化対象データが符号化された符号化結果が所定の拘束条件を満足するか否かを判定する拘束条件判定ステップと（例えば、図５のステップＳ５０１参照）、所定の拘束条件を満足しない不定部分が符号化結果の中に存在するものと拘束条件判定ステップにより判定された場合には、所定の拘束条件から前記不定部分を導出する不定部分導出ステップと（例えば、図５のステップＳ５０２参照）、不定部分導出ステップにより決定された不定部分を構成する各出力値について、所定の基準で量子化した量子化値をそれぞれ算出する量子化値算出ステップと（例えば、図５のステップＳ５０３参照）、量子化値算出ステップにより算出された各量子化値と不定部分を構成する各出力値と入れ替えて、所定の拘束条件を満足するような出力値を算出する出力値算出ステップと（例えば、図５のステップＳ５０４参照）、を含んだ符号化方法が実現される。
【産業上の利用可能性】
【００９９】
以上のように、本発明に係る符号化装置、符号化方法および符号化プログラムは、情報源に格納されている各種データ（文字や画像、音声など）を効率的に圧縮することを目的として、主アルゴリズム（既存アルゴリズム）を用いて最適化問題を解いて得られる解により、各種データを符号化することに有用であり、特に、主アルゴリズムを用いて最適化問題を解いて得られる解の中で、エラーとして処理されて捨て去られていた解を活かしてデータを符号化することに適する。
【図面の簡単な説明】
【０１００】
【図１】実施例１に係る符号化装置のアルゴリズムの全体像を示す図である。
【図２】実施例１に係る補助アルゴリズムの構成を示す図である。
【図３】実施例１に係る符号化装置の適用例を示す図である。
【図４】実施例１に係る符号化装置の構成を示す図である。
【図５】実施例１に係る符号化装置の処理の流れを示す図である。
【図６】符号化プログラムを実行するコンピュータを示す図である。
【符号の説明】
【０１０１】
１００  情報記憶部
２００  最適化実行部
３００  補助符号化部
３１０  行列係数記憶部
３２０  出力判定部
３３０  掃出し演算処理部
３４０  行インデックス記憶部
３５０  量子化演算部
３６０  求解演算部
４００  コンピュータ（符号化装置（補助符号化部））
４１０  入力部
４２０  出力部
４３０  ＨＤＤ（Hard Disk Drive）
４３１  符号化プログラム
４３２  符号化処理用データ
４４０  ＲＡＭ（Random Access Memory）
４４１  符号化プロセス
４５０  ＣＰＵ（Central Processing Unit）
５００  バス
【図１】
2010016684.tif 000008
【図２】
2010016684.tif 000009
【図３】
2010016684.tif 000010
【図４】
2010016684.tif 000011
【図５】
2010016684.tif 000012
【図６】
2010016684.tif 000013