(57)【要約】【課題】データベースのサイズを極めて小さくし、最も近いベクトルの探索時間を極めて短くする。【解決手段】符号器４では、典型ベクトル探索装置４−１により、シンドロームデータベース４−２にあるインデックスｉを持つｋ次元のベクトルｓ（ｉ）を１つとり、与えられた線形行列４−３（Ａ）に対して、Ａｙ＝ｓを満たすｎ次元の典型ベクトル４−７（ｙ）とインデックス４−８（ｉ）とを出力する。乗算器４−５は、線形行列４−４（Ｂ）に対して、典型ベクトル４−７（ｙ）を乗じてベクトルＢｙを求める。そして、符号器４は、典型ベクトル探索装置４−１が求めたインデックス４−８（ｉ）を［ｌｏｇ２ｍ］ビットで符号化したものと、［ｌ・ｌｏｇ２｜Ｗ｜］ビットで符号化したベクトルＢｙとの組を、符号語４−９として出力する。【選択図】図１
2008177892.tif 000002
【特許請求の範囲】
【請求項１】
インデックスが付与された第１のベクトルを発生する系列発生手段と、
第１の関数と第２の関数とを記憶する記憶手段と、
入力される入力ベクトルに基づいて前記系列発生手段から前記インデックスと前記第１のベクトルとを少なくとも１回取得し、該第１のベクトルと前記第１の関数とにより定められる方程式の解ベクトルの中から予め定められる第１の確率分布に基づいて解ベクトルを選択し、選択した解ベクトルに対応する第１のベクトルを典型ベクトルとする典型ベクトル探索手段と、
前記典型ベクトルに対して前記第２の関数を作用させて第２のベクトルを出力する関数作用手段とを具備し、
前記典型ベクトルに対応するインデックスと前記関数作用手段から出力される第２のベクトルとを符号語として出力することを特徴とする符号装置。
【請求項２】
前記系列発生手段は、ｍ（ｍ≧１）個のｋ（ｋ＜ｎ）次元のベクトルを記憶するシンドロームデータベースであることを特徴とする請求項１記載の符号装置。
【請求項３】
前記系列発生手段は、ｍ（ｍ≧１）個のｋ（ｋ＜ｎ）次元のベクトルをランダムに生成する擬似乱数生成器であることを特徴とする請求項１記載の符号装置。
【請求項４】
前記第１の関数は、ｋ＜ｎの関係を有する（ｋ，ｎ）型の線形行列であり、前記第２の関数は、ｌ＜ｎの関係を有する（ｌ，ｎ）型の線形行列であり、前記関数作用手段は、前記（ｌ，ｎ）型の線形行列に対して前記典型ベクトルを乗ずる乗算器であることを特徴とする請求項１乃至３のいずれかに記載の符号装置。
【請求項５】
インデックスが付与され、入力される符号語が生成される際に用いられた第１のベクトルを発生する系列発生手段と、
前記符号語が生成される際に用いられた第１の関数と第２の関数とを記憶する記憶手段と、
前記符号語に含まれるインデックスに基づいて、当該インデックスに対応する第１のベクトルを前記系列発生手段から取得し、取得した第１のベクトルと前記第１の関数と、前記第２の関数と、前記符号語に含まれる第２のベクトルとに基づいて定められる方程式の解ベクトルの中から予め定められる第２の確率分布に基づいて解ベクトルを選択し、選択した解ベクトルを再生ベクトルとする典型ベクトル探索手段と
を具備することを特徴とする復号装置。
【請求項６】
前記系列発生手段は、ｍ（ｍ≧１）個のｋ（ｋ＜ｎ）次元のベクトルを記憶するシンドロームデータベースであることを特徴とする請求項５記載の復号装置。
【請求項７】
前記系列発生手段は、ｍ（ｍ≧１）個のｋ（ｋ＜ｎ）次元のベクトルをランダムに生成する擬似乱数生成器であることを特徴とする請求項５記載の復号装置。
【請求項８】
前記第１の関数は、ｋ＜ｎの関係を有する（ｋ，ｎ）型の線形行列であり、前記第２の関数は、ｌ＜ｎの関係を有する（ｌ，ｎ）型の線形行列であることを特徴とする請求項５乃至７のいずれかに記載の復号装置。
【請求項９】
符号装置と復号装置とからなる符号化復号化システムであって、
前記符号装置は、
インデックスが付与された第１のベクトルを発生する第１の系列発生手段と、
第１の関数と第２の関数を記憶する第１の記憶手段と、
入力される入力ベクトルに基づいて前記第１の系列発生手段から前記インデックスと前記第１のベクトルとを少なくとも１回取得し、該第１のベクトルと前記第１の記憶手段に記憶される前記第１の関数とにより定められる方程式の解ベクトルの中から予め定められる第１の確率分布に基づいて解ベクトルを選択し、選択した解ベクトルに対応する第１のベクトルを典型ベクトルとする第１の典型ベクトル探索手段と、
前記典型ベクトルに対して前記第１の記憶手段に記憶される前記第２の関数を作用させて第２のベクトルを出力する関数作用手段とを具備し、
前記典型ベクトルに対応するインデックスと前記関数作用手段から出力される第２のベクトルとを符号語として出力し、
前記復号装置は、
前記第１の系列発生手段と同一の対応付けを有する前記インデックスと前記第１のベクトルとを発生する第２の系列発生手段と、
前記第１の関数と前記第２の関数を記憶する第２の記憶手段と、
前記符号語に含まれるインデックスに基づいて、当該インデックスに対応する第１のベクトルを前記第２の系列発生手段から取得し、取得した第１のベクトルと、前記第２の記憶手段に記憶される前記第１の関数及び前記第２の関数と、前記符号語に含まれる第２のベクトルとに基づいて定められる方程式の解ベクトルの中から予め定められる第２の確率分布に基づいて解ベクトルを選択し、選択した解ベクトルを再生ベクトルとする第２の典型ベクトル探索手段と
を具備することを特徴とする符号化復号化システム。
【請求項１０】
符号装置と復号装置とからなる符号化復号化システムであって、
前記符号装置は、
１つの第１のベクトルを発生する第１の系列発生手段と、
第１の関数と第２の関数を記憶する第１の記憶手段と、
入力される入力ベクトルに基づいて前記第１の系列発生手段から第１のベクトルを取得し、該第１のベクトルと前記第１の記憶手段に記憶される第１の関数とにより定められる方程式の解ベクトルの中から予め定められる第１の確率分布に基づいて解ベクトルを選択し、選択した解ベクトルに対応する第１のベクトルを典型ベクトルとする第１の典型ベクトル探索手段と、
前記典型ベクトルに対して前記第１の記憶手段に記憶される前記第２の関数を作用させて第２のベクトルを出力する関数作用手段とを具備し、
前記典型ベクトルに対応するインデックスと前記関数作用手段から出力される第２のベクトルとを符号語として出力し、
前記復号装置は、
前記第１のベクトルを発生する第２の系列発生手段と、
前記第１の関数と前記第２の関数を記憶する第２の記憶手段と、
前記第１のベクトルを前記第２の系列発生手段から取得し、取得した第１のベクトルと前記第２の記憶手段に記憶される第１の関数及び前記第２の関数と、前記符号語に含まれる第２のベクトルとに基づいて定められる方程式の解ベクトルの中から予め定められる第２の確率分布に基づいて解ベクトルを選択し、選択した解ベクトルを再生ベクトルとする第２の典型ベクトル探索手段と
を具備することを特徴とする符号化復号化システム。
【請求項１１】
インデックスが付与された第１のベクトルを発生する第１の系列発生手段と、第１の関数と第２の関数とを記憶する第１の記憶手段を有する符号装置と、前記第１の系列発生手段と同一の対応付けを有する前記インデックスと前記第１のベクトルとを発生する第２の系列発生手段と、前記第１の関数と前記第２の関数とを記憶する第２の記憶手段を有する復号装置とを備えた符号化復号化システムにおける符号化復号化方法であって、
前記符号装置が、入力される入力ベクトルに基づいて、前記第１の系列発生手段から前記インデックスと前記第１のベクトルとを少なくとも１回取得するステップと、
前記符号装置が、該第１のベクトルと前記第１の記憶手段に記憶される第１の関数とにより定められる方程式の解ベクトルの中から予め定められる第１の確率分布に基づいて解ベクトルを選択し、選択した解ベクトルに対応する第１のベクトルを典型ベクトルとするステップと、
前記符号装置が、前記典型ベクトルに対して前記第１の記憶手段に記憶される第２の関数を作用させて第２のベクトルを出力するステップと、
前記符号装置が、前記典型ベクトルに対応するインデックスと前記関数作用手段から出力される第２のベクトルとを符号語として出力するステップと、
前記復号装置が、前記符号語に含まれるインデックスに基づいて、当該インデックスに対応する第１のベクトルを、前記第２の系列発生手段から取得するステップと、
前記復号装置が、前記取得した第１のベクトルと、前記第１の記憶手段に記憶される第１の関数及び前記第２の関数と、前記符号語に含まれる第２のベクトルとに基づいて定められる方程式の解ベクトルの中から予め定められる第２の確率分布に基づいて解ベクトルを選択し、選択した解ベクトルを再生ベクトルとするステップと
を含むことを特徴とする符号化復号化方法。
【請求項１２】
１つの第１のベクトルを発生する第１の系列発生手段と、第１の関数と第２の関数とを記憶する第１の記憶手段を有する符号装置と、前記第１のベクトルとを発生する第２の系列発生手段と、前記第１の関数と前記第２の関数とを記憶する第２の記憶手段を有する復号装置とを備えた符号化復号化システムにおける符号化復号化方法であって、
前記符号装置が、入力される入力ベクトルに基づいて、前記第１の系列発生手段から第１のベクトルを取得するステップと、
前記符号装置が、前記取得した第１のベクトルと前記第１の記憶手段に記憶される第１の関数とにより定められる方程式の解ベクトルの中から予め定められる第１の確率分布に基づいて解ベクトルを選択し、選択した解ベクトルに対応する第１のベクトルを典型ベクトルとするステップと、
前記符号装置が、前記典型ベクトルに対して前記第１の記憶手段に記憶される第２の関数を作用させて第２のベクトルを出力するステップと、
前記符号装置が、前記典型ベクトルに対応するインデックスと前記第２のベクトルとを符号語として出力するステップと、
前記復号装置が、前記第２の系列発生手段から前記第１のベクトルを取得するステップと、
前記復号装置が、該取得した第１のベクトルと、前記第２の記憶手段に記憶される前記第１の関数及び前記第２の関数と、前記符号語に含まれる第２のベクトルとに基づいて定められる方程式の解ベクトルの中から予め定められる第２の確率分布に基づいて解ベクトルを選択し、選択した解ベクトルを再生ベクトルとするステップと
を含むことを特徴とする符号化復号化方法。
【請求項１３】
インデックスが付与された第１のベクトルを発生する系列発生手段と、第１の関数と第２の関数とを記憶する記憶手段とを備えた符号装置のコンピュータに、
入力される入力ベクトルに基づいて、前記第１の系列発生手段から前記インデックスと前記第１のベクトルとを少なくとも１回取得するステップと、
該第１のベクトルと第１の関数とにより定められる方程式の解ベクトルの中から予め定められる第１の確率分布に基づいて解ベクトルを選択し、選択した解ベクトルに対応する第１のベクトルを典型ベクトルとするステップと、
前記典型ベクトルに対して第２の関数を作用させて第２のベクトルを出力するステップと、
前記典型ベクトルに対応するインデックスと前記関数作用手段から出力される第２のベクトルとを符号語として出力するステップと
を実行させるための符号化プログラム。
【請求項１４】
インデックスが付与され、入力される符号語が生成される際に用いられた第１のベクトルを発生する系列発生手段と、前記符号語が生成される際に用いられた第１の関数と第２の関数とを記憶する記憶手段とを備えた復号装置のコンピュータに、
入力される符号語に含まれるインデックスに基づいて、当該インデックスに対応する第１のベクトルを、前記第２の系列発生手段から取得するステップと、
前記取得した第１のベクトルと、第１の関数と、第２の関数と、前記符号語に含まれる第２のベクトルとに基づいて定められる方程式の解ベクトルの中から予め定められる第２の確率分布に基づいて解ベクトルを選択し、選択した解ベクトルを再生ベクトルとするステップと
を実行させるための復号化プログラム。
【請求項１５】
インデックスが付与された第１のベクトルを発生する第１の系列発生手段と、第１の関数と第２の関数とを記憶する第１の記憶手段を有する符号装置と、前記第１の系列発生手段と同一の対応付けを有する前記インデックスと前記第１のベクトルとを発生する第２の系列発生手段と、前記第１の関数と前記第２の関数とを記憶する第２の記憶手段を有する復号装置とを備えた符号化復号化システムに具備されるコンピュータに、
前記符号装置として、入力される入力ベクトルに基づいて、前記第１の系列発生手段から前記インデックスと前記第１のベクトルとを少なくとも１回取得するステップと、
前記符号装置として、該第１のベクトルと前記第１の記憶手段に記憶される第１の関数とにより定められる方程式の解ベクトルの中から予め定められる第１の確率分布に基づいて解ベクトルを選択し、選択した解ベクトルに対応する第１のベクトルを典型ベクトルとするステップと、
前記符号装置として、前記典型ベクトルに対して前記第１の記憶手段に記憶される第２の関数を作用させて第２のベクトルを出力するステップと、
前記符号装置として、前記典型ベクトルに対応するインデックスと前記関数作用手段から出力される第２のベクトルとを符号語として出力するステップと、
前記復号装置として、前記符号語に含まれるインデックスに基づいて、当該インデックスに対応する第１のベクトルを、前記第２の系列発生手段から取得するステップと、
前記復号装置として、前記取得した第１のベクトルと、前記第１の記憶手段に記憶される第１の関数及び前記第２の関数と、前記符号語に含まれる第２のベクトルとに基づいて定められる方程式の解ベクトルの中から予め定められる第２の確率分布に基づいて解ベクトルを選択し、選択した解ベクトルを再生ベクトルとするステップと
を実行させるための符号化復号化プログラム。
【請求項１６】
１つの第１のベクトルを発生する第１の系列発生手段と、第１の関数と第２の関数とを記憶する第１の記憶手段を有する符号装置と、前記第１のベクトルとを発生する第２の系列発生手段と、前記第１の関数と前記第２の関数とを記憶する第２の記憶手段を有する復号装置とを備えた符号化復号化システムに具備されるコンピュータに、
前記符号装置として、入力される入力ベクトルに基づいて、前記第１の系列発生手段から第１のベクトルを取得するステップと、
前記符号装置として、前記取得した第１のベクトルと前記第１の記憶手段に記憶される第１の関数とにより定められる方程式の解ベクトルの中から予め定められる第１の確率分布に基づいて解ベクトルを選択し、選択した解ベクトルに対応する第１のベクトルを典型ベクトルとするステップと、
前記符号装置として、前記典型ベクトルに対して前記第１の記憶手段に記憶される第２の関数を作用させて第２のベクトルを出力するステップと、
前記符号装置が、前記典型ベクトルに対応するインデックスと前記第２のベクトルとを符号語として出力するステップと、
前記復号装置として、前記第２の系列発生手段から前記第１のベクトルを取得するステップと、
前記復号装置として、該取得した第１のベクトルと、前記第２の記憶手段に記憶される前記第１の関数及び前記第２の関数と、前記符号語に含まれる第２のベクトルとに基づいて定められる方程式の解ベクトルの中から予め定められる第２の確率分布に基づいて解ベクトルを選択し、選択した解ベクトルを再生ベクトルとするステップと
を実行させるための符号化復号化プログラム。
【請求項１７】
インデックスが付与された第１のベクトルを発生する系列発生手段と、第１の関数と第２の関数とを記憶する記憶手段とを備えた符号装置のコンピュータに、
入力される入力ベクトルに基づいて、前記第１の系列発生手段から前記インデックスと前記第１のベクトルとを少なくとも１回取得するステップと、
該第１のベクトルと第１の関数とにより定められる方程式の解ベクトルの中から予め定められる第１の確率分布に基づいて解ベクトルを選択し、選択した解ベクトルに対応する第１のベクトルを典型ベクトルとするステップと、
前記典型ベクトルに対して第２の関数を作用させて第２のベクトルを出力するステップと、
前記典型ベクトルに対応するインデックスと前記関数作用手段から出力される第２のベクトルとを符号語として出力するステップと
を実行させるための符号化プログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項１８】
インデックスが付与され、入力される符号語が生成される際に用いられた第１のベクトルを発生する系列発生手段と、前記符号語が生成される際に用いられた第１の関数と第２の関数とを記憶する記憶手段とを備えた復号装置のコンピュータに、
入力される符号語に含まれるインデックスに基づいて、当該インデックスに対応する第１のベクトルを、前記第２の系列発生手段から取得するステップと、
前記取得した第１のベクトルと、第１の関数と、第２の関数と、前記符号語に含まれる第２のベクトルとに基づいて定められる方程式の解ベクトルの中から予め定められる第２の確率分布に基づいて解ベクトルを選択し、選択した解ベクトルを再生ベクトルとするステップと
を実行させるための復号化プログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項１９】
インデックスが付与された第１のベクトルを発生する第１の系列発生手段と、第１の関数と第２の関数とを記憶する第１の記憶手段を有する符号装置と、前記第１の系列発生手段と同一の対応付けを有する前記インデックスと前記第１のベクトルとを発生する第２の系列発生手段と、前記第１の関数と前記第２の関数とを記憶する第２の記憶手段を有する復号装置とを備えた符号化復号化システムに具備されるコンピュータに、
前記符号装置として、入力される入力ベクトルに基づいて、前記第１の系列発生手段から前記インデックスと前記第１のベクトルとを少なくとも１回取得するステップと、
前記符号装置として、該第１のベクトルと前記第１の記憶手段に記憶される第１の関数とにより定められる方程式の解ベクトルの中から予め定められる第１の確率分布に基づいて解ベクトルを選択し、選択した解ベクトルに対応する第１のベクトルを典型ベクトルとするステップと、
前記符号装置として、前記典型ベクトルに対して前記第１の記憶手段に記憶される第２の関数を作用させて第２のベクトルを出力するステップと、
前記符号装置として、前記典型ベクトルに対応するインデックスと前記関数作用手段から出力される第２のベクトルとを符号語として出力するステップと、
前記復号装置として、前記符号語に含まれるインデックスに基づいて、当該インデックスに対応する第１のベクトルを、前記第２の系列発生手段から取得するステップと、
前記復号装置として、前記取得した第１のベクトルと、前記第１の記憶手段に記憶される第１の関数及び前記第２の関数と、前記符号語に含まれる第２のベクトルとに基づいて定められる方程式の解ベクトルの中から予め定められる第２の確率分布に基づいて解ベクトルを選択し、選択した解ベクトルを再生ベクトルとするステップと
を実行させるための符号化復号化プログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項２０】
１つの第１のベクトルを発生する第１の系列発生手段と、第１の関数と第２の関数とを記憶する第１の記憶手段を有する符号装置と、前記第１のベクトルとを発生する第２の系列発生手段と、前記第１の関数と前記第２の関数とを記憶する第２の記憶手段を有する復号装置とを備えた符号化復号化システムに具備されるコンピュータに、
前記符号装置として、入力される入力ベクトルに基づいて、前記第１の系列発生手段から第１のベクトルを取得するステップと、
前記符号装置として、前記取得した第１のベクトルと前記第１の記憶手段に記憶される第１の関数とにより定められる方程式の解ベクトルの中から予め定められる第１の確率分布に基づいて解ベクトルを選択し、選択した解ベクトルに対応する第１のベクトルを典型ベクトルとするステップと、
前記符号装置として、前記典型ベクトルに対して前記第１の記憶手段に記憶される第２の関数を作用させて第２のベクトルを出力するステップと、
前記符号装置が、前記典型ベクトルに対応するインデックスと前記第２のベクトルとを符号語として出力するステップと、
前記復号装置として、前記第２の系列発生手段から前記第１のベクトルを取得するステップと、
前記復号装置として、該取得した第１のベクトルと、前記第２の記憶手段に記憶される前記第１の関数及び前記第２の関数と、前記符号語に含まれる第２のベクトルとに基づいて定められる方程式の解ベクトルの中から予め定められる第２の確率分布に基づいて解ベクトルを選択し、選択した解ベクトルを再生ベクトルとするステップと
を実行させるための符号化復号化プログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、与えられた品質基準を保証し、可能な限り少ない代表点数もしくは可能な限り短い符号長を達成する符号装置、復号装置、符号化復号化システム、符号化復号化方法、符号化プログラム、復号化プログラム、符号化復号化プログラム及び記録媒体に関する。
【背景技術】
【０００２】
従来、「有歪み符号化」もしくは「ベクトル量子化」と呼ばれる符号化システムがある。なお、２つのベクトル間の歪みを測る尺度は、予め定められているものとする。
【０００３】
図５は、従来技術のベクトル量子化による符号器の構成を示すブロック図である。図において、符号器１は、再生ベクトル選択装置１−１と再生ベクトルデータベース１−２とからなる。ここで、再生ベクトルデータベース１−２には、予め、複数の入力データと同じ次元のベクトルが初期値として格納されている。また、再生ベクトルデータベース１−２内の各ベクトルには、それぞれ異なるインデックスが割り当てられている。
【０００４】
符号化において、再生ベクトル選択装置１−１は、入力ベクトルｖである入力データ１−３に対して、再生ベクトルデータベース１−２内にあるベクトルとの歪みを測り、最も歪みの小さいベクトルのインデックスｃを符号語１−４として出力する。
【０００５】
図６は、従来技術のベクトル量子化による復号器の構成を示すブロック図である。図において、復号器２は、データベース参照装置２−１と再生ベクトルデータベース２−２とからなる。ここで、再生ベクトルデータベース２−２は、図５に示す再生ベクトルデータベース１−２と同一のものである。
【０００６】
復号化において、デーベース参照装置２−１は、符号器１が出力した符号語２−３（インデックスｃ）をインデックスとして解釈し、再生ベクトルデータベース２−２からインデックスｃに対応するベクトルｖを参照して再生ベクトル２−４として出力する。
【０００７】
図７は、従来技術による、符号器１と復号器２とを含む全体の構成を示すブロック図である。ｆは符号器、ｇは復号器である。Ｘは入力データを表す確率変数、Ｙは再生データを表す確率変数、Ｉ（Ｘ；Ｙ）は相互情報量、すなわち、アルゴリズムが達成する符号化レート、ｄは歪み尺度、ＥＸＹｄ（Ｘ，Ｙ）はアルゴリズムが達成する平均歪みである。
【０００８】
なお、上述した説明では、再生ベクトルデータベース１−２、２−２の構築を、符号化・復号化前に済ませているものとしたが、複数の入力データを一括して与えた後で、データベースを構築、もしくは、入力データを与えるたびにデータベースを更新するようなアルゴリズムもある。
【０００９】
また、図５、図６に示すような従来の符号器及び復号器については、非特許文献１に記されている。理論的には、ｎ次元のベクトルに対して、再生ベクトルデータベース１−２、２−２に、２ｎＩ（Ｘ；Ｙ）個の異なるベクトルを適切に選択すれば、アルゴリズムは、平均歪みＥＸＹｄ（Ｘ；Ｙ）を達成することが知られている。有歪み符号化もしくはベクトル量子化と呼ばれる装置は、音声・画像などのデータ圧縮にとどまらず、データベースの構築や、情報の要約などにも応用できる汎用性の高い装置である。
【非特許文献１】T. M. Cover and J. A. Thomas, “Elements of Information Theory 2nd Ed.”, John Wiley & Sons. Inc., 2006, Chapter10, p301-325.
【発明の開示】
【発明が解決しようとする課題】
【００１０】
しかしながら、従来技術による符号化復号化システムでは、一般に再生ベクトルデータベース１−２、２−２の大きさがベクトルの次元に対して指数的に大きくなるため、再生ベクトル選択装置１−１による最も近いベクトルの探索が困難であった。また、再生ベクトルデータベース１−２、２−２の構成を改良することで、再生ベクトル選択装置１−１による最も近いベクトルの探索を容易にしようとしたとしても、そのような最適な再生ベクトルデータベース１−２、２−２の構築を行うことは困難であった。
【００１１】
本発明は、このような事情を考慮してなされたものであり、その目的は、データベースのサイズを極めて小さくすることができ、最も近いベクトルの探索時間を極めて短くすることができる符号装置、復号装置、符号化復号化システム、符号化復号化方法、符号化プログラム、復号化プログラム、符号化復号化プログラム及び記録媒体を提供することにある。
【課題を解決するための手段】
【００１２】
上述した課題を解決するために、本発明は、インデックスが付与された第１のベクトルを発生する系列発生手段と、第１の関数と第２の関数とを記憶する記憶手段と、入力される入力ベクトルに基づいて前記系列発生手段から前記インデックスと前記第１のベクトルとを少なくとも１回取得し、該第１のベクトルと前記第１の関数とにより定められる方程式の解ベクトルの中から予め定められる第１の確率分布に基づいて解ベクトルを選択し、選択した解ベクトルに対応する第１のベクトルを典型ベクトルとする典型ベクトル探索手段と、前記典型ベクトルに対して前記第２の関数を作用させて第２のベクトルを出力する関数作用手段とを具備し、前記典型ベクトルに対応するインデックスと前記関数作用手段から出力される第２のベクトルとを符号語として出力することを特徴とする符号装置である。
【００１３】
また、本発明は、上記に記載の発明において、前記系列発生手段は、ｍ（ｍ≧１）個のｋ（ｋ＜ｎ）次元のベクトルを記憶するシンドロームデータベースであることを特徴とする。
【００１４】
また、本発明は、上記に記載の発明において、前記系列発生手段は、ｍ（ｍ≧１）個のｋ（ｋ＜ｎ）次元のベクトルをランダムに生成する擬似乱数生成器であることを特徴とする。
【００１５】
また、本発明は、上記に記載の発明において、前記第１の関数は、ｋ＜ｎの関係を有する（ｋ，ｎ）型の線形行列であり、前記第２の関数は、ｌ＜ｎの関係を有する（ｌ，ｎ）型の線形行列であり、前記関数作用手段は、前記（ｌ，ｎ）型の線形行列に対して前記典型ベクトルを乗ずる乗算器であることを特徴とする。
【００１６】
また、本発明は、インデックスが付与され、入力される符号語が生成される際に用いられた第１のベクトルを発生する系列発生手段と、前記符号語が生成される際に用いられた第１の関数と第２の関数とを記憶する記憶手段と、前記符号語に含まれるインデックスに基づいて、当該インデックスに対応する第１のベクトルを前記系列発生手段から取得し、取得した第１のベクトルと前記第１の関数と、前記第２の関数と、前記符号語に含まれる第２のベクトルとに基づいて定められる方程式の解ベクトルの中から予め定められる第２の確率分布に基づいて解ベクトルを選択し、選択した解ベクトルを再生ベクトルとする典型ベクトル探索手段とを具備することを特徴とする復号装置である。
【００１７】
また、本発明は、上記に記載の発明において、前記系列発生手段は、ｍ（ｍ≧１）個のｋ（ｋ＜ｎ）次元のベクトルを記憶するシンドロームデータベースであることを特徴とする。
【００１８】
また、本発明は、上記に記載の発明において、前記系列発生手段は、ｍ（ｍ≧１）個のｋ（ｋ＜ｎ）次元のベクトルをランダムに生成する擬似乱数生成器であることを特徴とする。
【００１９】
また、本発明は、上記に記載の発明において、前記第１の関数は、ｋ＜ｎの関係を有する（ｋ，ｎ）型の線形行列であり、前記第２の関数は、ｌ＜ｎの関係を有する（ｌ，ｎ）型の線形行列であることを特徴とする。
【００２０】
また、本発明は、符号装置と復号装置とからなる符号化復号化システムであって、前記符号装置は、インデックスが付与された第１のベクトルを発生する第１の系列発生手段と、第１の関数と第２の関数を記憶する第１の記憶手段と、入力される入力ベクトルに基づいて前記第１の系列発生手段から前記インデックスと前記第１のベクトルとを少なくとも１回取得し、該第１のベクトルと前記第１の記憶手段に記憶される前記第１の関数とにより定められる方程式の解ベクトルの中から予め定められる第１の確率分布に基づいて解ベクトルを選択し、選択した解ベクトルに対応する第１のベクトルを典型ベクトルとする第１の典型ベクトル探索手段と、前記典型ベクトルに対して前記第１の記憶手段に記憶される前記第２の関数を作用させて第２のベクトルを出力する関数作用手段とを具備し、前記典型ベクトルに対応するインデックスと前記関数作用手段から出力される第２のベクトルとを符号語として出力し、前記復号装置は、前記第１の系列発生手段と同一の対応付けを有する前記インデックスと前記第１のベクトルとを発生する第２の系列発生手段と、前記第１の関数と前記第２の関数を記憶する第２の記憶手段と、前記符号語に含まれるインデックスに基づいて、当該インデックスに対応する第１のベクトルを前記第２の系列発生手段から取得し、取得した第１のベクトルと、前記第２の記憶手段に記憶される前記第１の関数及び前記第２の関数と、前記符号語に含まれる第２のベクトルとに基づいて定められる方程式の解ベクトルの中から予め定められる第２の確率分布に基づいて解ベクトルを選択し、選択した解ベクトルを再生ベクトルとする第２の典型ベクトル探索手段とを具備することを特徴とする符号化復号化システムである。
【００２１】
また、本発明は、符号装置と復号装置とからなる符号化復号化システムであって、前記符号装置は、１つの第１のベクトルを発生する第１の系列発生手段と、第１の関数と第２の関数を記憶する第１の記憶手段と、入力される入力ベクトルに基づいて前記第１の系列発生手段から第１のベクトルを取得し、該第１のベクトルと前記第１の記憶手段に記憶される第１の関数とにより定められる方程式の解ベクトルの中から予め定められる第１の確率分布に基づいて解ベクトルを選択し、選択した解ベクトルに対応する第１のベクトルを典型ベクトルとする第１の典型ベクトル探索手段と、前記典型ベクトルに対して前記第１の記憶手段に記憶される前記第２の関数を作用させて第２のベクトルを出力する関数作用手段とを具備し、前記典型ベクトルに対応するインデックスと前記関数作用手段から出力される第２のベクトルとを符号語として出力し、前記復号装置は、前記第１のベクトルを発生する第２の系列発生手段と、前記第１の関数と前記第２の関数を記憶する第２の記憶手段と、前記第１のベクトルを前記第２の系列発生手段から取得し、取得した第１のベクトルと前記第２の記憶手段に記憶される第１の関数及び前記第２の関数と、前記符号語に含まれる第２のベクトルとに基づいて定められる方程式の解ベクトルの中から予め定められる第２の確率分布に基づいて解ベクトルを選択し、選択した解ベクトルを再生ベクトルとする第２の典型ベクトル探索手段とを具備することを特徴とする符号化復号化システムである。
【００２２】
また、本発明は、インデックスが付与された第１のベクトルを発生する第１の系列発生手段と、第１の関数と第２の関数とを記憶する第１の記憶手段を有する符号装置と、前記第１の系列発生手段と同一の対応付けを有する前記インデックスと前記第１のベクトルとを発生する第２の系列発生手段と、前記第１の関数と前記第２の関数とを記憶する第２の記憶手段を有する復号装置とを備えた符号化復号化システムにおける符号化復号化方法であって、前記符号装置が、入力される入力ベクトルに基づいて、前記第１の系列発生手段から前記インデックスと前記第１のベクトルとを少なくとも１回取得するステップと、前記符号装置が、該第１のベクトルと前記第１の記憶手段に記憶される第１の関数とにより定められる方程式の解ベクトルの中から予め定められる第１の確率分布に基づいて解ベクトルを選択し、選択した解ベクトルに対応する第１のベクトルを典型ベクトルとするステップと、前記符号装置が、前記典型ベクトルに対して前記第１の記憶手段に記憶される第２の関数を作用させて第２のベクトルを出力するステップと、前記符号装置が、前記典型ベクトルに対応するインデックスと前記関数作用手段から出力される第２のベクトルとを符号語として出力するステップと、前記復号装置が、前記符号語に含まれるインデックスに基づいて、当該インデックスに対応する第１のベクトルを、前記第２の系列発生手段から取得するステップと、前記復号装置が、前記取得した第１のベクトルと、前記第１の記憶手段に記憶される第１の関数及び前記第２の関数と、前記符号語に含まれる第２のベクトルとに基づいて定められる方程式の解ベクトルの中から予め定められる第２の確率分布に基づいて解ベクトルを選択し、選択した解ベクトルを再生ベクトルとするステップとを含むことを特徴とする符号化復号化方法である。
【００２３】
また、本発明は、１つの第１のベクトルを発生する第１の系列発生手段と、第１の関数と第２の関数とを記憶する第１の記憶手段を有する符号装置と、前記第１のベクトルとを発生する第２の系列発生手段と、前記第１の関数と前記第２の関数とを記憶する第２の記憶手段を有する復号装置とを備えた符号化復号化システムにおける符号化復号化方法であって、前記符号装置が、入力される入力ベクトルに基づいて、前記第１の系列発生手段から第１のベクトルを取得するステップと、前記符号装置が、前記取得した第１のベクトルと前記第１の記憶手段に記憶される第１の関数とにより定められる方程式の解ベクトルの中から予め定められる第１の確率分布に基づいて解ベクトルを選択し、選択した解ベクトルに対応する第１のベクトルを典型ベクトルとするステップと、前記符号装置が、前記典型ベクトルに対して前記第１の記憶手段に記憶される第２の関数を作用させて第２のベクトルを出力するステップと、前記符号装置が、前記典型ベクトルに対応するインデックスと前記第２のベクトルとを符号語として出力するステップと、前記復号装置が、前記第２の系列発生手段から前記第１のベクトルを取得するステップと、前記復号装置が、該取得した第１のベクトルと、前記第２の記憶手段に記憶される前記第１の関数及び前記第２の関数と、前記符号語に含まれる第２のベクトルとに基づいて定められる方程式の解ベクトルの中から予め定められる第２の確率分布に基づいて解ベクトルを選択し、選択した解ベクトルを再生ベクトルとするステップとを含むことを特徴とする符号化復号化方法である。
【００２４】
また、本発明は、インデックスが付与された第１のベクトルを発生する系列発生手段と、第１の関数と第２の関数とを記憶する記憶手段とを備えた符号装置のコンピュータに、入力される入力ベクトルに基づいて、前記第１の系列発生手段から前記インデックスと前記第１のベクトルとを少なくとも１回取得するステップと、該第１のベクトルと第１の関数とにより定められる方程式の解ベクトルの中から予め定められる第１の確率分布に基づいて解ベクトルを選択し、選択した解ベクトルに対応する第１のベクトルを典型ベクトルとするステップと、前記典型ベクトルに対して第２の関数を作用させて第２のベクトルを出力するステップと、前記典型ベクトルに対応するインデックスと前記関数作用手段から出力される第２のベクトルとを符号語として出力するステップとを実行させるための符号化プログラムである。
【００２５】
また、本発明は、インデックスが付与され、入力される符号語が生成される際に用いられた第１のベクトルを発生する系列発生手段と、前記符号語が生成される際に用いられた第１の関数と第２の関数とを記憶する記憶手段とを備えた復号装置のコンピュータに、入力される符号語に含まれるインデックスに基づいて、当該インデックスに対応する第１のベクトルを、前記第２の系列発生手段から取得するステップと、前記取得した第１のベクトルと、第１の関数と、第２の関数と、前記符号語に含まれる第２のベクトルとに基づいて定められる方程式の解ベクトルの中から予め定められる第２の確率分布に基づいて解ベクトルを選択し、選択した解ベクトルを再生ベクトルとするステップとを実行させるための復号化プログラムである。
【００２６】
また、本発明は、インデックスが付与された第１のベクトルを発生する第１の系列発生手段と、第１の関数と第２の関数とを記憶する第１の記憶手段を有する符号装置と、前記第１の系列発生手段と同一の対応付けを有する前記インデックスと前記第１のベクトルとを発生する第２の系列発生手段と、前記第１の関数と前記第２の関数とを記憶する第２の記憶手段を有する復号装置とを備えた符号化復号化システムに具備されるコンピュータに、前記符号装置として、入力される入力ベクトルに基づいて、前記第１の系列発生手段から前記インデックスと前記第１のベクトルとを少なくとも１回取得するステップと、前記符号装置として、該第１のベクトルと前記第１の記憶手段に記憶される第１の関数とにより定められる方程式の解ベクトルの中から予め定められる第１の確率分布に基づいて解ベクトルを選択し、選択した解ベクトルに対応する第１のベクトルを典型ベクトルとするステップと、前記符号装置として、前記典型ベクトルに対して前記第１の記憶手段に記憶される第２の関数を作用させて第２のベクトルを出力するステップと、前記符号装置として、前記典型ベクトルに対応するインデックスと前記関数作用手段から出力される第２のベクトルとを符号語として出力するステップと、前記復号装置として、前記符号語に含まれるインデックスに基づいて、当該インデックスに対応する第１のベクトルを、前記第２の系列発生手段から取得するステップと、前記復号装置として、前記取得した第１のベクトルと、前記第１の記憶手段に記憶される第１の関数及び前記第２の関数と、前記符号語に含まれる第２のベクトルとに基づいて定められる方程式の解ベクトルの中から予め定められる第２の確率分布に基づいて解ベクトルを選択し、選択した解ベクトルを再生ベクトルとするステップとを実行させるための符号化復号化プログラムである。
【００２７】
また、本発明は、１つの第１のベクトルを発生する第１の系列発生手段と、第１の関数と第２の関数とを記憶する第１の記憶手段を有する符号装置と、前記第１のベクトルとを発生する第２の系列発生手段と、前記第１の関数と前記第２の関数とを記憶する第２の記憶手段を有する復号装置とを備えた符号化復号化システムに具備されるコンピュータに、前記符号装置として、入力される入力ベクトルに基づいて、前記第１の系列発生手段から第１のベクトルを取得するステップと、前記符号装置として、前記取得した第１のベクトルと前記第１の記憶手段に記憶される第１の関数とにより定められる方程式の解ベクトルの中から予め定められる第１の確率分布に基づいて解ベクトルを選択し、選択した解ベクトルに対応する第１のベクトルを典型ベクトルとするステップと、前記符号装置として、前記典型ベクトルに対して前記第１の記憶手段に記憶される第２の関数を作用させて第２のベクトルを出力するステップと、前記符号装置が、前記典型ベクトルに対応するインデックスと前記第２のベクトルとを符号語として出力するステップと、前記復号装置として、前記第２の系列発生手段から前記第１のベクトルを取得するステップと、前記復号装置として、該取得した第１のベクトルと、前記第２の記憶手段に記憶される前記第１の関数及び前記第２の関数と、前記符号語に含まれる第２のベクトルとに基づいて定められる方程式の解ベクトルの中から予め定められる第２の確率分布に基づいて解ベクトルを選択し、選択した解ベクトルを再生ベクトルとするステップとを実行させるための符号化復号化プログラムである。
【００２８】
また、本発明は、インデックスが付与された第１のベクトルを発生する系列発生手段と、第１の関数と第２の関数とを記憶する記憶手段とを備えた符号装置のコンピュータに、入力される入力ベクトルに基づいて、前記第１の系列発生手段から前記インデックスと前記第１のベクトルとを少なくとも１回取得するステップと、該第１のベクトルと第１の関数とにより定められる方程式の解ベクトルの中から予め定められる第１の確率分布に基づいて解ベクトルを選択し、選択した解ベクトルに対応する第１のベクトルを典型ベクトルとするステップと、前記典型ベクトルに対して第２の関数を作用させて第２のベクトルを出力するステップと、前記典型ベクトルに対応するインデックスと前記関数作用手段から出力される第２のベクトルとを符号語として出力するステップとを実行させるための符号化プログラムを記録したコンピュータ読み取り可能な記録媒体である。
【００２９】
また、本発明は、インデックスが付与され、入力される符号語が生成される際に用いられた第１のベクトルを発生する系列発生手段と、前記符号語が生成される際に用いられた第１の関数と第２の関数とを記憶する記憶手段とを備えた復号装置のコンピュータに、入力される符号語に含まれるインデックスに基づいて、当該インデックスに対応する第１のベクトルを、前記第２の系列発生手段から取得するステップと、前記取得した第１のベクトルと、第１の関数と、第２の関数と、前記符号語に含まれる第２のベクトルとに基づいて定められる方程式の解ベクトルの中から予め定められる第２の確率分布に基づいて解ベクトルを選択し、選択した解ベクトルを再生ベクトルとするステップとを実行させるための復号化プログラムを記録したコンピュータ読み取り可能な記録媒体である。
【００３０】
また、本発明は、インデックスが付与された第１のベクトルを発生する第１の系列発生手段と、第１の関数と第２の関数とを記憶する第１の記憶手段を有する符号装置と、前記第１の系列発生手段と同一の対応付けを有する前記インデックスと前記第１のベクトルとを発生する第２の系列発生手段と、前記第１の関数と前記第２の関数とを記憶する第２の記憶手段を有する復号装置とを備えた符号化復号化システムに具備されるコンピュータに、前記符号装置として、入力される入力ベクトルに基づいて、前記第１の系列発生手段から前記インデックスと前記第１のベクトルとを少なくとも１回取得するステップと、前記符号装置として、該第１のベクトルと前記第１の記憶手段に記憶される第１の関数とにより定められる方程式の解ベクトルの中から予め定められる第１の確率分布に基づいて解ベクトルを選択し、選択した解ベクトルに対応する第１のベクトルを典型ベクトルとするステップと、前記符号装置として、前記典型ベクトルに対して前記第１の記憶手段に記憶される第２の関数を作用させて第２のベクトルを出力するステップと、前記符号装置として、前記典型ベクトルに対応するインデックスと前記関数作用手段から出力される第２のベクトルとを符号語として出力するステップと、前記復号装置として、前記符号語に含まれるインデックスに基づいて、当該インデックスに対応する第１のベクトルを、前記第２の系列発生手段から取得するステップと、前記復号装置として、前記取得した第１のベクトルと、前記第１の記憶手段に記憶される第１の関数及び前記第２の関数と、前記符号語に含まれる第２のベクトルとに基づいて定められる方程式の解ベクトルの中から予め定められる第２の確率分布に基づいて解ベクトルを選択し、選択した解ベクトルを再生ベクトルとするステップとを実行させるための符号化復号化プログラムを記録したコンピュータ読み取り可能な記録媒体である。
【００３１】
また、本発明は、１つの第１のベクトルを発生する第１の系列発生手段と、第１の関数と第２の関数とを記憶する第１の記憶手段を有する符号装置と、前記第１のベクトルとを発生する第２の系列発生手段と、前記第１の関数と前記第２の関数とを記憶する第２の記憶手段を有する復号装置とを備えた符号化復号化システムに具備されるコンピュータに、前記符号装置として、入力される入力ベクトルに基づいて、前記第１の系列発生手段から第１のベクトルを取得するステップと、前記符号装置として、前記取得した第１のベクトルと前記第１の記憶手段に記憶される第１の関数とにより定められる方程式の解ベクトルの中から予め定められる第１の確率分布に基づいて解ベクトルを選択し、選択した解ベクトルに対応する第１のベクトルを典型ベクトルとするステップと、前記符号装置として、前記典型ベクトルに対して前記第１の記憶手段に記憶される第２の関数を作用させて第２のベクトルを出力するステップと、前記符号装置が、前記典型ベクトルに対応するインデックスと前記第２のベクトルとを符号語として出力するステップと、前記復号装置として、前記第２の系列発生手段から前記第１のベクトルを取得するステップと、前記復号装置として、該取得した第１のベクトルと、前記第２の記憶手段に記憶される前記第１の関数及び前記第２の関数と、前記符号語に含まれる第２のベクトルとに基づいて定められる方程式の解ベクトルの中から予め定められる第２の確率分布に基づいて解ベクトルを選択し、選択した解ベクトルを再生ベクトルとするステップとを実行させるための符号化復号化プログラムを記録したコンピュータ読み取り可能な記録媒体である。
【発明の効果】
【００３２】
この発明によれば、符号装置は、入力される入力ベクトルに基づいて、インデックスが付与された第１のベクトルを発生する系列発生手段からインデックスと第１のベクトルとを少なくとも１回取得し、該第１のベクトルと第１の関数とにより定められる方程式の解ベクトルの中から予め定められる第１の確率分布に基づいて解ベクトルを選択し、選択した解ベクトルに対応する第１のベクトルを典型ベクトルとし、該典型ベクトルに対して第２の関数を作用させて第２のベクトルを出力し、典型ベクトルに対応するインデックスと第２のベクトルとを符号語として出力する。したがって、第１の系列発生手段から発生させる第１のベクトルの数を極めて小さくすることができ、最も近いベクトルの探索時間を極めて短くすることができるという利点が得られる。
【００３３】
また、本発明によれば、復号装置は、入力される符号語に含まれるインデックスに基づいて、当該インデックスに対応する第１のベクトルを、入力される符号語が生成される際に用いられた第１のベクトルを発生する系列発生手段から取得し、該取得した第１のベクトルと、第１の関数と、第２の関数と、符号語に含まれる第２のベクトルとに基づいて定められる方程式の解ベクトルの中から予め定められる第２の確率分布に基づいて解ベクトルを選択し、該選択した解ベクトルを再生ベクトルとする。したがって、第２の系列発生手段から発生させる第１のベクトルの数を極めて小さくすることができ、最も近いベクトルの探索時間を極めて短くすることができるという利点が得られる。
【００３４】
また、本発明によれば、入力される入力ベクトルに基づいて、インデックスが付与された第１のベクトルを発生する第１の系列発生手段からインデックスと第１のベクトルとを少なくとも１回取得し、該第１のベクトルと第１の関数とにより定められる方程式の解ベクトルの中から予め定められる第１の確率分布に基づいて解ベクトルを選択し、選択した解ベクトルに対応する第１のベクトルを典型ベクトルとし、典型ベクトルに対して第２の関数を作用させて第２のベクトルを出力し、典型ベクトルに対応するインデックスと第２のベクトルとを符号語として出力する一方、符号語に含まれるインデックスに基づいて、当該インデックスに対応する第１のベクトルを、インデックスが付与された第１のベクトルを発生する第２の系列発生手段から取得し、該取得した第１のベクトルと、第１の関数と、第２の関数と、符号語に含まれる第２のベクトルとに基づいて定められる方程式の解ベクトルの中から予め定められる第２の確率分布に基づいて解ベクトルを選択し、選択した解ベクトルを再生ベクトルとする。したがって、第１の系列発生手段及び第２の系列発生手段から発生させる第１のベクトルの数を極めて小さくすることができ、最も近いベクトルの探索時間を極めて短くすることができるという利点が得られる。
【００３５】
また、本発明によれば、入力される入力ベクトルに基づいて、１つの第１のベクトルを発生する第１の系列発生手段から第１のベクトルを取得し、該取得した第１のベクトルと第１の関数とにより定められる方程式の解ベクトルの中から予め定められる第１の確率分布に基づいて解ベクトルを選択し、選択した解ベクトルに対応する第１のベクトルを典型ベクトルとし、典型ベクトルに対して第２の関数を作用させて第２のベクトルを出力し、典型ベクトルに対応するインデックスと第２のベクトルとを符号語として出力する一方、第１のベクトルを発生する第２の系列発生手段から第１のベクトルを取得し、該取得した第１のベクトルと、第１の関数と、第２の関数と、符号語に含まれる第２のベクトルとに基づいて定められる方程式の解ベクトルの中から予め定められる第２の確率分布に基づいて解ベクトルを選択し、選択した解ベクトルを再生ベクトルとする。したがって、最も近いベクトルの探索時間を極めて短くすることができるという利点が得られる。
【発明を実施するための最良の形態】
【００３６】
以下、本発明の一実施形態を、図面を参照して説明する。
【００３７】
Ａ．原理
まず、本発明の原理について説明する。なお、以下のアルゴリズムにおいて、入力ベクトルｘのスカラー空間Ｖは、有限である必要はなく、有限体の構造も必要としないが、出力ベクトルｙ及び非線形行列のスカラー空間については有限体とし、Ｗと記す。入力ベクトルの次元をｎとし、確率変数Ｘ，Ｙの同時分布をμＸＹとして、Ｙの周辺分布を次式（１）とする。
【００３８】
【数１】
2008177892.tif 000003
【００３９】
また、以下の説明において、確率変数Ｘ，Ｙの同時エントロピーをＨ（Ｘ，Ｙ）とし、ｎ次元のベクトルの歪みを測る尺度をｄｎとする。ここで、同時エントロピーは、上記した同時分布μＸＹを用いて、次式（２）のように定義される。
【００４０】
【数２】
2008177892.tif 000004
【００４１】
図１は、本発明の実施形態による符号器の構成を示すブロック図である。符号器４は、典型ベクトル探索装置４−１、シンドロームデータベース４−２、内部のメモリ等の記憶手段に記憶される線形行列４−３（Ａ）、線形行列４−４（Ｂ）及び乗算器４−５からなる。シンドロームデータベース４−２には、ｋ（ｋ＜ｎ）次元のベクトルがｍ個（ｍ≧１）、格納されている。これは、ｍ個のｋ次元ベクトルをランダムに生成する乱数生成器と置き換えることができる。ベクトルには、異なるインデックスが割り当てられている。
【００４２】
線形行列４−３（Ａ）は、サイズが（ｋ，ｎ）型の行列であり、線形行列４−３（Ａ）にｎ次元の縦ベクトルを右から乗ずることによってｋ次元の縦ベクトルが出力される。線形行列４−４（Ｂ）は、（ｌ，ｎ）型の行列であり、線形行列４−４（Ｂ）にｎ次元のベクトルを乗算器４−５を用いて右から乗ずることによって、ｌ（ｌ＜ｎ）次元の縦ベクトルが出力される。
【００４３】
最初に典型ベクトル探索装置４−１は、シンドロームデータベース４−２にあるインデックスｉを持つｋ次元のベクトルｓ（ｉ）を１つとり、与えられた線形行列４−３（Ａ）に対して、次式（３）を満たすｎ次元の典型ベクトル４−７（ｙ）とインデックス４−８（ｉ）とを出力する。
【００４４】
【数３】
2008177892.tif 000005
【００４５】
典型ベクトル探索装置４−１が求める典型ベクトル４−７（ｙ）とインデックス４−８（ｉ）との組は次式（４）で表される。
【００４６】
【数４】
2008177892.tif 000006
【００４７】
上記数式（４）で示される典型ベクトル４−７（ｙ）とインデックス４−８（ｉ）との組については次式（５）で表される性質のいずれかを持つものが望ましい。
【００４８】
【数５】
2008177892.tif 000007
【００４９】
続いて、乗算器４−５は、線形行列４−４（Ｂ）に対して、典型ベクトル４−７（ｙ）を乗じてベクトルＢｙを求める。そして、符号器４は、典型ベクトル探索装置４−１が求めたインデックス４−８（ｉ）を［ｌｏｇ２ｍ］ビットで符号化したものと、［ｌ・ｌｏｇ２｜Ｗ｜］ビットで符号化したベクトルＢｙとの組を、符号語４−９として出力する。該インデックス４−８（ｉ）とベクトルＢｙとの組は、次式（６）で表される。
【００５０】
【数６】
2008177892.tif 000008
【００５１】
但し、シンドロームデータベース４−２の大きさが１（すなわち、ｍ＝１）である場合には、符号語４−９は、インデックス４−８（ｉ）を含まないものとする。
【００５２】
図２は、本発明の実施形態による復号器の構成を示すブロック図である。復号器５は、典型ベクトル探索装置５−１、シンドロームデータベース５−２、内部のメモリ等の記憶手段に記憶される線形行列５−３（Ａ）及び線形行列５−４（Ｂ）からなる。シンドロームデータベース５−２と、前述した符号化の際に用いたシンドロームデータベース４−２とは同一のものとする。また、上述したように、シンドロームデータベース４−２を乱数発生器とした場合には、シンドロームデータベース５−２は、シンドロームデータベース４−２と同期したｋ次元のベクトルを出力するものとする。
【００５３】
線形行列５−３（Ａ）、線形行列５−４（Ｂ）は、線形行列４−３（Ａ）、線形行列４−４（Ｂ）とそれぞれ同一のものとする。但し、後述の典型ベクトル探索装置５−１は、典型ベクトル探索装置４−１とは異なるものである。
【００５４】
典型ベクトル探索装置５−１は、符号語５−６からベクトルｃについての（ｃ，ｉ）を求める。ここで、ベクトルｃは、符号器４が求めた典型ベクトル４−７（ｙ）に対して、次式（７）を満たすものであるが、復号器５は、ベクトルｙを知ることができないので、符号語５−６をベクトルｃについての（ｃ，ｉ）と示すこととする。
【００５５】
【数７】
2008177892.tif 000009
【００５６】
続いて、シンドロームデータベース５−２からインデックスｉを持つｋ次元のシンドロームｓ（ｉ）を参照する。但し、シンドロームデータベース５−２の大きさが１（すなわち、ｍ＝１）である場合には、符号語５−６は、インデックスｉを含ませなくともよく、シンドロームデータベース５−２にある唯一のシンドロームｓ（ｉ）を参照するようにしてもよい。そして、線形行列５−３（Ａ）、線形行列５−４（Ｂ）を用いて、次式（８）を満たすｎ次元の再生ベクトル５−５（ｚ）を求める。
【００５７】
【数８】
2008177892.tif 000010
【００５８】
典型ベクトル探索装置５−１が求める再生ベクトル５−５（ｚ）は、次式（９）で表される性質を持つことが望ましい。
【００５９】
【数９】
2008177892.tif 000011
【００６０】
Ｂ．実施形態の記号
ここで、実施形態の説明中に現れる記号について説明する。
入力ベクトルのスカラー空間をＶ、出力ベクトルのスカラー空間をＷとする。また、ベクトルｙ∈Ｗｎ、Ｙｎ∈Ｗｎを列ベクトルとする。このとき、一般のスカラーの歪み尺度をｄとして、次式（１０）が得られる。
【００６１】
【数１０】
2008177892.tif 000012
【００６２】
そして、ｙ、ｙ’∈ＷのＨａｍｍｉｎｇ（ハミング）歪みハットｄを、次式（１１）で表されるように定義する。
【００６３】
【数１１】
2008177892.tif 000013
【００６４】
また、ｎ次元ベクトルｘ＝（ｘ１，…，ｘｎ）、ｙ＝（ｙ１，…，ｙｎ）間の歪みを、次式（１２）とする。また、ｎ次元ベクトルｙ＝（ｙ１，…，ｙｎ）、ｙ’＝（ｙ１’，…，ｙｎ’）間の歪みを、次式（１３）とする。
【００６５】
【数１２】
2008177892.tif 000014
【００６６】
【数１３】
2008177892.tif 000015
【００６７】
集合の大きさを｜・｜で表し、対数の底を｜Ｗ｜とする。入力の確率変数をＸ、分布μＸを与える。そして、Ｘを与えたときの出力Ｙの条件付き確率分布をμＹ｜Ｘとする。これによって、Ｘ、Ｙの同時分布μＸＹは、次式（１４）で与えられる。
【００６８】
【数１４】
2008177892.tif 000016
【００６９】
また、Ｙの周辺分布μＹを次式（１５）とする。
【００７０】
【数１５】
2008177892.tif 000017
【００７１】
条件付きエントロピーＨ（Ｙ｜Ｘ）、及び相互情報量Ｉ（Ｘ；Ｙ）を次式（１６）、（１７）で定義される。なお、入力ベクトルのスカラー空間Ｖが無限集合の場合には、Σｘ∈Ｖは、積分で表される。
【００７２】
【数１６】
2008177892.tif 000018
【００７３】
【数１７】
2008177892.tif 000019
【００７４】
次に、任意のε＞０と分布μＸを持つ情報源Ｘに対して、次式（１８）を満たす同時分布μＸＹを計算する。
【００７５】
【数１８】
2008177892.tif 000020
【００７６】
ここで、Ｒｘ（Ｄ）は、レート歪み関数と呼ばれ、次式（１９）で定義される。
【００７７】
【数１９】
2008177892.tif 000021
【００７８】
ここで、ＥＸＹは、確率変数（Ｘ，Ｙ）に関する平均を表す。最小値を達成する条件付き確率μＹ｜Ｘは、Ｂｌａｈｕｔ−Ａｒｉｍｏｔｏのアルゴリズム（文献１：R. E. Blahut, “Computation of Channel Capacity and Rate-Distortion Function”, IEEE Trans, Inform. Theory, Vol.IT-18, No.4, p460-p473, July 1972.）を用いて計算することができる。
【００７９】
次に、典型系列集合ＴＸＹを、次式（２０）と定義する。
【００８０】
【数２０】
2008177892.tif 000022
【００８１】
ここで、ベクトルｘ∈Ｖｎ、ベクトルｙ∈Ｗｎに対して、経験分布ｐｘｙは、次式（２１）で定義される確率分布である。
【００８２】
【数２１】
2008177892.tif 000023
【００８３】
また、探索空間の大きさと性能に影響するパラメータγ＞０は小さい値とする。
【００８４】
以下では、Ａ，Ｂ，ψＡ，ψＡＢを、次式（２２）で表されるような写像とする。
【００８５】
【数２２】
2008177892.tif 000024
【００８６】
Ｂ−１．第１動作例
線形行列４−３、５−３（Ａ）を（ｋ，ｎ）疎行列として、ψＡに次式（２３）で表す性質を仮定する。ここで、Ｐｒｏｂ（Probability）は、確率変数ＸとＹに対してランダムな値が与えられた場合に、括弧内の条件を満たす確率を算出する演算を行うことを意味する。
【００８７】
【数２３】
2008177892.tif 000025
【００８８】
Ａｙで情報源Ｙを符号化し、ψＡをＸを補助情報としたときの符号語Ａｙ（なお、ｙは、ベクトルである）に対するＹの復号器とすると、十分大きなｎを取れば任意のεＡ，δＢに対して、上記式（２３）を満たす。
【００８９】
Ｂを（ｌ，ｎ）疎行列として、Ｂｙで情報源Ｙを符号化する。ψＡＢを符号語（Ａｙ，Ｂｙ）（なお、ｘとｙは、ベクトルである）に対するＹの符号器とする。そして、次式（２４）で示す性質を仮定する。
【００９０】
【数２４】
2008177892.tif 000026
【００９１】
なお、数式（２４）における二番目の式は、次式（２５）としてもよい。
【００９２】
【数２５】
2008177892.tif 000027
【００９３】
このときは、次式（２６）を満たすことになる。
【００９４】
【数２６】
2008177892.tif 000028
【００９５】
なお、Ａ，Ｂは、疎行列であると仮定したが、上記の仮定を満たす関数Ａ：Ｗｎ→Ｗｋ，Ｂ：Ｗｎ→Ｗｌならば、どのようなものでもよい。例えば、文献５（A. Aaron and B. Girod, “Compression with Side Information Using Turbo Codes”, Proc. of the IEEE DATA COMPRESSION CONFERENCE, Snowbird, UT, p252-p261, Apr. 2002.）で示されるＴｕｒｂｏ符号がその例である。
【００９６】
ここで、例えば、ψＡ、ψＡＢは、次式（２７）のように定義する。
【００９７】
【数２７】
2008177892.tif 000029
【００９８】
このψＡ、ψＡＢを近似的に実現する方法としては、文献２、３、４（文献２：F. R. Kschischang, B. J. Frey and H. A. Loeliger, “Factor Graphs and the Sum-Product Algorithm”, IEEE Transaction on Information Theory, Vol.47, No.2, p498-p519, February 2001.、文献３：S. M. Aji and R. J. McEliece, “The Generalized Distributive Law”, IEEE Trans. Inform. Theory, Vol.46, No.2, p325-p343, Mar. 2000、文献４：J. Feldman, M. J. Wainwright and D. R. Karger, “Using Linear Programming to Decode Binary Linear Codes”, IEEE Trans. Inform. Theory, Vol.IT-51, No.3, p954-p972, March 2005.）のアルゴリズムがあり、これらは、ベクトルの次元ｎに比例する時間で実行できる。そして、十分大きなｎに対して、上記仮定を満たすＡ、Ｂの存在が知られている。
【００９９】
ＳをＷｋ上の一様分布を持つ確率変数とする。符号器４と復号器５とは、長さｍの定常無記憶情報源Ｓｍから発生させた、次式（２８）で表される乱数系列を共有していると仮定する。シンドロームデータベース４−２、５−２は、該乱数系列を格納している。
【０１００】
【数２８】
2008177892.tif 000030
【０１０１】
符号器４は、以下のφ、φ’、φ’’のいずれかを適用することができる。
【０１０２】
（Ａ）φを適用する場合
Ｓｔｅｐ１）符号器４において、典型ベクトル探索装置４−１は、後述のφ−１を用いて、例えば、インデックスｉを更新しながら、次式（２９）で示す値を最小にするｉ∈｛１，…，ｍ｝を求め、これをｉ（ｘ）（なお、ｘはベクトルである）とする。
【０１０３】
【数２９】
2008177892.tif 000031
【０１０４】
Ｓｔｅｐ２）符号器４は、次式（３０）で示す値を符号語４−９とする。ここで、ｉ（ｘ）は、符号化されているものとする。
【０１０５】
【数３０】
2008177892.tif 000032
【０１０６】
（Ｂ）φ’を適用する場合
Ｓｔｅｐ１）符号器４において、典型ベクトル探索装置４−１は、入力ベクトルｘ∈Ｖｎに対して、例えば、インデックスｉを更新しながら、次式（３１）、（３２）を同時に満たすｉ∈｛１，…，ｍ｝を求め、これをｉ（ｘ）（なお、ｘはベクトルである）とする。存在しない場合には、ｉ（ｘ）＝１とするか、次式（３３）の値を最小にするｉをｉ（ｘ）とする。
【０１０７】
【数３１】
2008177892.tif 000033
【０１０８】
【数３２】
2008177892.tif 000034
【０１０９】
【数３３】
2008177892.tif 000035
【０１１０】
Ｓｔｅｐ２）符号器４は、前述したφと同様に、数式（３０）で示す値を符号語４−９とする。ここで、ｉ（ｘ）（なお、ｘはベクトルである）は、符号化されているものとする。
【０１１１】
（Ｃ）φ’’を適用する場合
Ｓｔｅｐ１）符号器４において、典型ベクトル探索装置４−１は、入力ベクトルｘ∈Ｖｎに対して、例えば、インデックスｉを更新しながら、上述した数式（３１）を満たし、上述した数式（３３）を最小にするｉ∈｛１，…，ｍ｝を求め、これをｉ（ｘ）（なお、ｘはベクトルである）とする。
Ｓｔｅｐ２）前述したφで説明した数式（３０）で求めた値を符号語４−９とする。ここで、ｉ（ｘ）は、符号化されているものとする。
【０１１２】
次に、復号器５に、以下のφ−１を適用する場合について説明する。
Ｓｔｅｐ１）復号器５において、典型ベクトル探索装置５−１は、符号語５−６（ｃ，ｉ）に対して、ψＢ（ｓ（ｉ），ｃ）∈Ｗｎを再生ベクトル５−５（ｚ）とする。すなわち、再生ベクトル５−５（ｚ）は、次式（３４）で示される。ここで、左辺のｉは、符号化されたもので、右辺のｉは、それを復号したものである。
【０１１３】
【数３４】
2008177892.tif 000036
【０１１４】
符号器４・復号器５対（φ，φ−１）は、以下の効果を有する。なお、φは、φ’もしくはφ’’と置き換えることが可能である。
【０１１５】
（効果）
Ａ，Ｂ，ψＡ，ψＡＢは、上記数式（２３）、（２４）で示した仮定を満たしているとする。そして、次式（３５）を満たすデータベースの大きさｍに関して次式（３６）が成立するものとする。
【０１１６】
【数３５】
2008177892.tif 000037
【０１１７】
【数３６】
2008177892.tif 000038
【０１１８】
このとき、符号器４・復号器５対（φ，φ−１）の符号化レートは、次式（３７）を満たし、平均歪みは、次式（３８）を満たす。ここで、ＥＸＶは、Ｘｎと、Ｘｎと独立に発生させたＳｍとに関する平均を表す。
【０１１９】
【数３７】
2008177892.tif 000039
【０１２０】
【数３８】
2008177892.tif 000040
【０１２１】
したがって、γが小さくなるように、ｍを取り、εＡ，εＡＢ，δＡ，δＡＢ，ρを小さく取ることにより、アルゴリズムの性能を、そのレート歪み限界までいくらでも近づけることができる。
【０１２２】
続いて、符合器４・復号器５対（φ’，φ−１）は、以下の効果を有する。
Ａ，Ｂ，ψＡ，ψＡＢは、上記数式（２３）、（２４）で示した仮定を満たしているとする。そして、ＴＸＹを定めるパラメータγ＞０に対して、データベースの大きさ及び探索時間ｍを、次式（３９）とする。
【０１２３】
【数３９】
2008177892.tif 000041
【０１２４】
さらに、次式（４０）とする。
【０１２５】
【数４０】
2008177892.tif 000042
【０１２６】
このとき、符号器４・復号器５対（φ’，φ−１）の符号化レートは、次式（４１）であり、上述した数式（３８）を満たす。ここで、ＥＸＶは、Ｘｎと、Ｘｎと独立に発生させたＳｍとに関する平均を表す。
【０１２７】
【数４１】
2008177892.tif 000043
【０１２８】
したがって、γ，εＡ，εＡＢ，δＡ，δＡＢ，ρを小さく取ることにより、アルゴリズムの性能を、そのレート歪み限界までいくらでも近づけることができる。
【０１２９】
従来技術による、ベクトル量子化による符号化法で最適な品質と符号化レートを達成させるには、データベースの大きさ・探索時間は、簡易な方法で、｜Ｗ｜ｎＲＸ（Ｄ）が必要である。一方、本第１動作例による、符号器４・復号器５対（φ，φ−１）の組み合わせでは、ｍは、上述した数式（３５）を満たせば十分であり、εＡは、理論的にはいくらでも小さく取ることができるため、データベースの大きさ・探索時間ｍは、従来技術に比べて非常に小さい値にできる。また、本第１動作例では、符号器４・復号器５対（φ’，φ−１）の組み合わせでは、γ，εＡは、理論的にはいくらでも小さく取ることができるため、データベースの大きさ・探索時間ｍは、従来技術に比べて非常に小さな値にできる。
【０１３０】
Ｂ−２．第２動作例
線形行列４−３、５−３（Ａ）を（ｋ，ｎ）疎行列（成分のほとんどが０の行列）、線形行列４−４、５−４（Ｂ）を（ｌ，ｎ）疎行列とする。以下、シンドロームデータベース４−２、５−２の大きさｍについてｍ＝１とし、１つのシンドロームｓ∈Ｗｋを共有していると仮定する。すなわち、シンドロームデータベース４−２、５−２に記憶されるデータの数は「１」である。なお、符号器４、復号器５の構成は、上述した実施形態（図１、図２）と同様である。また、εＡＢ＞εＡ＞０、δＡ，δＡＢ＞０として、ｋ，ｌを次式（４２）に示すように定める。
【０１３１】
【数４２】
2008177892.tif 000044
【０１３２】
そして、ψＡ，ψＡＢに次式（４３）で表される性質を仮定する。
【０１３３】
【数４３】
2008177892.tif 000045
【０１３４】
疎行列をランダムに生成することにより、十分大きなｎに対して、上記数式（４３）で表される性質を有する。例えば、ψＡ，ψＡＢを、上述した数式（２７）のように定義する。このψＡ，ψＡＢを近似的に実現する方法としては、前述した文献２、３、４のアルゴリズムがあり、これらは、ベクトルの次元ｎに比例する時間で実行することができる。
【０１３５】
なお、Ａ，Ｂは、疎行列であると仮定したが、上記仮定を満たす関数Ａ：Ｗｎ→Ｗｋ，Ｂ：Ｗｎ→Ｗｌならば、どのようなものでもよい。
【０１３６】
符号器４は、φを用いる。
Ｓｔｅｐ１）符号器４において、典型ベクトル探索装置４−１は、次式（４４）で定めたφ（ｘ｜ｓ）を復号語とする。
【０１３７】
【数４４】
2008177892.tif 000046
【０１３８】
また、復号器５は、φ−１を用いる。
Ｓｔｅｐ１）復号器５において、典型ベクトル探索装置５−１は、符号語５−６（ｃ）に対して、ψＢ（ｓ，ｃ）∈Ｗｎを再生ベクトルとする。すなわち、次式（４５）で表される値を再生ベクトルとする。
【０１３９】
【数４５】
2008177892.tif 000047
【０１４０】
第２動作例によるアルゴリズムの符号化レートは、次式（４６）に示すようになる。
【０１４１】
【数４６】
2008177892.tif 000048
【０１４２】
そして、データベースの大きさ及び探索時間は、ｍ＝１であり、アルゴリズム全体の計算量は、ψＡ及びψＡＢの計算量のみに依存する。つまり、次式（４７）に示すようになる。ここで、ＥＸは、Ｘｎに関する平均を表す。
【０１４３】
【数４７】
2008177892.tif 000049
【０１４４】
したがって、γ，εＡ，εＡＢ，δＡ，δＡＢ，ρを小さく取ることにより、アルゴリズムの性能を、そのレート歪み限界までいくらでも近づけることができる。
【０１４５】
Ｃ．変形例
図３及び図４は、それぞれ本発明の変形例による符号器と復号器との構成を示すブロック図である。本変形例による符号器６は、図３に示すように、典型ベクトル探索装置６−１、系列発生装置６−２、関数６−３（Ａ）、関数６−４（Ｂ）及び関数作用器６−５からなる。典型ベクトル探索装置６−１は、図１の典型ベクトル探索装置４−１に対応し、系列発生装置６−２はシンドロームデータベース４−２、関数６−３（Ａ）は線形行列４−３（Ａ）、関数６−４（Ｂ）は線形行列４−４（Ｂ）、関数作用器６−５は乗算器４−５にそれぞれ対応する。なお、関数６−３（Ａ）及び関数６−４（Ｂ）は、線形行列４−３（Ａ）及び線形行列４−４（Ｂ）と同様に、内部のメモリ等の記憶手段に記憶される。特に、系列発生装置６−２は、シンドロームデータベース４−２に対応するとともに、乱数生成器に対応している。
【０１４６】
また、本変形例による復号器７は、図４に示すように、典型ベクトル探索装置７−１、系列発生装置７−２、関数７−３（Ａ）及び関数７−４（Ｂ）からなる。典型ベクトル探索装置７−１は、図２の典型ベクトル探索装置５−１に対応し、系列発生装置７−２はシンドロームデータベース５−２、関数７−３（Ａ）は線形行列５−３（Ａ）、関数７−４（Ｂ）は線形行列４−４（Ｂ）にそれぞれ対応する。特に、系列発生装置７−２は、シンドロームデータベース７−２に対応するとともに、乱数生成器に対応している。
【０１４７】
上述した実施形態及び変形例によれば、最適な符号化レートを与えたとき、従来技術との違いは以下の通りである。
（１）従来技術における再生ベクトルデータベース１−２、２−２に比べ、本実施形態によるシンドロームデータベース４−２、５−２の大きさを格段に小さくすることができる。これによって、探索時間を大幅に削減することができる。
【０１４８】
（２）探索時間を大幅に削減できる再生ベクトルデータベース１−２、２−２を用意する場合、再生ベクトルデータベース１−２、２−２は、最適な符号化レートを出力ために最適化する必要があったが、本実施形態によるシンドロームデータベース４−２、５−２内のシンドロームは、前述したように、等確率でランダムに出力すればよく、符号器と復号器とで同期した乱数生成器に置き換えることも可能である。すなわち、データベースの構築のコストを大幅に削減することができる。
【０１４９】
なお、本発明に記載の符号装置における方程式の解ベクトルの中から予め定められる第１の確率分布に基づいて解ベクトルを選択する構成について、第１の確率分布とは、例えば、式（１４）で示される同時確率分布から導出されるｎ次元ベクトルの同時確率分布であり、解ベクトルは上記の式（５）で示される条件を満たすように選択され、また、当該構成については文献２、３、４で与えられている近似アルゴリズムによって実現することも可能であります。
また、本発明に記載の復号装置における方程式の解ベクトルの中から予め定められる第２の確率分布に基づいて解ベクトルを選択する構成において、第２の確率分布とは、例えば、式（１５）で示される同時確率分布から導出されるｎ次元ベクトルの同時確率分布であり、解ベクトルは上記の式（９）で示される条件を満たすように選択され、また、当該構成はあるいは文献２、３、４で与えられている近似アルゴリズムによって実現することも可能であります。
【０１５０】
また、上述した符号器４、６、復号器５、７などによる各ステップを実現するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、また、符号器４、６、復号器５、７などにおける処理部の機能を実現するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することにより、符号化処理、及び復号化処理を行ってもよい。なお、ここでいう「コンピュータシステム」とは、ＯＳや周辺機器等のハードウェアを含むものであってもよい。また、「コンピュータシステム」は、ＷＷＷシステムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、フラッシュメモリ等の書き込み可能な不揮発性メモリ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。
【０１５１】
さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムが送信された場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリ（例えばＤＲＡＭ（Dynamic Random Access Memory））のように、一定時間プログラムを保持しているものも含むものとする。また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されてもよい。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。また、上記プログラムは、前述した機能の一部を実現するためのものであっても良い。さらに、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるもの、いわゆる差分ファイル（差分プログラム）であっても良い。
【図面の簡単な説明】
【０１５２】
【図１】本発明の実施形態による符号器の構成を示すブロック図である。
【図２】本実施形態による復号器の構成を示すブロック図である。
【図３】本発明の変形例による符号器の構成を示すブロック図である。
【図４】本変形例による復号器の構成を示すブロック図である。
【図５】従来技術のベクトル量子化による符号器の構成を示すブロック図である。
【図６】従来技術のベクトル量子化による復号器の構成を示すブロック図である。
【図７】従来技術による、符号器１と復号器２とを含む全体の構成を示すブロック図である。
【符号の説明】
【０１５３】
４  符号器（符号装置）
４−１  典型ベクトル探索装置（典型ベクトル探索手段、第１の典型ベクトル探索手段）
４−２  シンドロームデータベース（系列発生手段、擬似乱数生成器、第１の系列発生手段）
４−３  線形行列（Ａ）
４−４  線形行列（Ｂ）
４−５  乗算器（関数作用手段）
４−６  入力ベクトル
４−７  典型ベクトル
４−８  インデックス
４−９  符号語
５  復号器（復号装置）
５−１  典型ベクトル探索装置（典型ベクトル探索手段、第２の典型ベクトル探索手段）
５−２  シンドロームデータベース（系列発生手段、擬似乱数生成器、第２の系列発生手段）
５−３  線形行列（Ａ）
５−４  線形行列（Ｂ）
６−６  入力ベクトル
６−７  典型ベクトル
６−８  インデックス
５−６  符号語
５−５  再生ベクトル
６  符号器（符号装置）
６−１  典型ベクトル探索装置（典型ベクトル探索手段、第１の典型ベクトル探索手段）
６−２  系列発生装置（系列発生手段、擬似乱数生成器、第１の系列発生手段）
６−３  関数（Ａ）
６−４  関数（Ｂ）
６−５  関数作用器（関数作用手段）
６−９  符号語
７−１  典型ベクトル探索装置（典型ベクトル探索手段、第２の典型ベクトル探索手段）
７−２  系列発生装置（系列発生手段、擬似乱数生成器、第２の系列発生手段）
７−３  関数（Ａ）
７−４  関数（Ｂ）
７−５  再生ベクトル
７−６  符号語
【図１】
2008177892.tif 000050
【図２】
2008177892.tif 000051
【図３】
2008177892.tif 000052
【図４】
2008177892.tif 000053
【図５】
2008177892.tif 000054
【図６】
2008177892.tif 000055
【図７】
2008177892.tif 000056