(57)【特許請求の範囲】
【請求項１】
フィルタに印加された信号サンプルのシーケンス（ｘ（１）からｘ（ｔ））の補間残差（εＮ−ｉ，ｉ−１（ｔ−ｉ＋１））から導出（１４）されるゲインベクトル（ｋＮ（ｔ））によって、フィルタの係数または重み（ｗ１（ｔ）からｗＮ（ｔ））を更新する（１６）ように構成されることを特徴とする適応フィルタ。
【請求項２】
ａ）予測残差（εｎＦ（ｔ），εｎＢ（ｔ））を導出するために信号サンプルの入力シーケンスを処理し（１２）、
ｂ）予測残差（εｎＦ（ｔ），εｎＢ（ｔ））を補間残差（εＮ−ｉ，ｉ−１（ｔ−ｉ＋１））に変換し（１４）、
ｃ）補間残差（εＮ−ｉ，ｉ−１（ｔ−ｉ＋１））からゲインベクトル（ｋＮ（ｔ））の成分（ｋｉＮ（ｔ））を導出し（１６）、および、
ｄ）ゲインベクトル（ｋＮ（ｔ））を入力および参照信号（ｘ（ｔ），ｙ（ｔ））と組み合わせ（１８）、適応フィルタリングを提供するために要求されるように、フィルタ係数または重み（ｗ１（ｔ）からｗＮ（ｔ））を更新するように構成されることを特徴とする適応フィルタ。
【請求項３】
予測残差は最小二乗予測残差（εｎＦ（ｔ），εｎＢ（ｔ））であることを特徴とする請求項２に記載の適応フィルタ。
【請求項４】
再帰性最小二乗格子（ＲＬＳＬ）アルゴリズムを使用して信号サンプルのシーケンス（ｘ（１）からｘ（ｔ））を処理する（１２）ことによって予測残差（εｎＦ（ｔ），εｎＢ（ｔ））を得るように構成されることを特徴とする請求項２または３に記載の適応フィルタ。
【請求項５】
各反復が残差（εｐ，ｆ（ｔ−ｆ））またはそれから導出される中間結果（εｐ＋１，ｆ（ｔ−ｆ），εｐ，ｆ＋１（ｔ−ｆ−１））の指数（例えばｆまたはｐ）を変更する反復手法によって、予測残差（εｎＦ（ｔ），εｎＢ（ｔ））を、ゲインベクトル成分（ｋｉＮ（ｔ））に対応する補間残差（εＮ−ｉ，ｉ−１（ｔ−ｉ＋１））に変換する（１４）ように構成されることを特徴とする請求項２、３、または、４に記載の適応フィルタ。
【請求項６】
反復手法は予測残差（εｎＦ（ｔ），εｎＢ（ｔ））を補間残差（εｐ，０（ｔ），ε０，ｆ（ｔ−ｆ））として扱うことによって実施される分割征服手法（７０，７２）であり、反復は、補間残差（εｐ，０（ｔ），ε０，ｆ（ｔ−ｆ））を、非正規化形のゲインベクトル（ｋＮ（ｔ））の成分を提供する補間残差（εＮ−ｉ，ｉ−１（ｔ−ｉ＋１））に変換するよう、指数（ｆ，ｐ）が適切に変更されるまで進行するように構成されることを特徴とする請求項５に記載の適応フィルタ。
【請求項７】
予測残差は最小二乗予測残差（εｎＦ（ｔ），εｎＢ（ｔ））であり、反復手法は、前方または後方予測残差（εｎＦ（ｔ），εｎＢ（ｔ））を、後続または先行する時系列信号サンプルの不在に対応する２つの指数（ｆ，ｐ）の１つについてゼロの値を持つ補間残差（εｐ，０（ｔ），ε０，ｆ（ｔ−ｆ））として扱うことによって実施され、反復は、ゼロ指数の補間残差（εｐ，０（ｔ），ε０，ｆ（ｔ−ｆ））を、同じく非正規化形ゲインベクトルの成分である他の補間残差（εＮ−ｉ，ｉ−１（ｔ−ｉ＋１））に変換するよう、ゼロ指数（０＝ｆまたはｐ）が十分に変更されるまで進行するように構成されることを特徴とする請求項６に記載の適応フィルタ。
【請求項８】
反復手法は、ゲインベクトル（ｋＮ（ｔ））の成分（ｋｉＮ（ｔ））に導く複数回の反復のシーケンスにおける反復（εｐ＋１，ｆ（ｔ−ｆ），εｐ，ｆ＋１（ｔ−ｆ−１））を、中間結果として扱うことも含み、反復は、中間結果をゲインベクトル（ｋＮ（ｔ））の成分（ｋｉＮ（ｔ））に対応する補間残差（εＮ−ｉ，ｉ−１（ｔ−ｉ＋１））に変換するよう、中間結果（εｐ＋１，ｆ（ｔ−ｆ），εｐ，ｆ＋１（ｔ−ｆ−１））の指数（ｆ，ｆ＋１，ｐ，ｐ＋１）が十分に変更されるまで進行するように構成されることを特徴とする請求項５、６、または、７に記載の適応フィルタ。
【請求項９】
Ｎが２ｘに等しく、ｘが正の整数である次数Ｎの適応フィルタであって、ゲインベクトル（ｋＮ（ｔ））の非正規化成分を生成するためのシーケンスにおける反復は、中間点のすぐ隣および逆側の２つの残差（εＭＦ（ｔ）＝εＭ，０（ｔ），εＭＢ（ｔ）＝ε０，Ｍ（ｔ））の１つの使用で開始し、使用する残差（εＭ，０（ｔ），ε０，Ｍ（ｔ））は、反復シーケンスにおいて変化されない指数（Ｍ）が相対的に大きな値を有するものであり、関連する中間点は２つの量の間の中間であり：
ａ）２つの量の１つは補間残差（ε６３，０（ｔ））であり、他の１つはゲインベクトルが生成される関連する時系列のメンバ（ｘ（ｔ）＝ε０，０（ｔ））であるか、または、
ｂ）２つの量の１つは補間残差（ε６３，０（ｔ））であり、他の１つは以前の反復のための開始点（ε３２，０（ｔ））であるか、または、
ｃ）２つの量は以前の反復のためのそれぞれ開始および終了点（ε３２，０（ｔ），ε３２，３１（ｔ））であることを特徴とする請求項８に記載の適応フィルタ。
【請求項１０】
Ｎは各々が２の累乗である整数の和に等しい次数Ｎの適応フィルタであって、反復手法は、次数の各々がそれぞれ２の累乗であるフィルタの組合せとしてフィルタを扱うことを含むことを特徴とする請求項８に記載の適応フィルタ。
【請求項１１】
ゲインベクトルの非正規化成分を生成するためのシーケンスにおける反復は、中間点のすぐ隣および逆側の２つの残差の１つの使用で開始し、使用する残差は、反復シーケンスにおいて変化されない指数が相対的大きな値を有するものであり、関連する中間点は２つの量の間の中間であり：
ａ）２つの量の１つは補間残差であり、他の１つはゲインベクトルが生成される関連する時系列のメンバであるか、または、
ｂ）２つの量の１つは補間残差であり、他の１つは以前の反復のための開始点であるか、または、
ｃ）２つの量は以前の反復のためのそれぞれ開始および終了点であることを特徴とする請求項１０に記載の適応フィルタ。
【請求項１２】
ＱＲ分解手法によって、予測残差を、ゲインベクトルの成分に対応する補間残差に変換するよう構成され、ＱＲ分解手法において：
ａ）ζ（ｉ）＝Ψ（ｉ）＋ｋ（ｉ）ξ（ｉ）という形の方程式は、与えられた予測および補間残差Ψ（ｉ）およびξ（ｉ）に対して補間残差ζ（ｉ）および係数ｋ（ｉ）について解かれ、そうする際に、異なったサンプル指数ｊについて得られたΨ（ｊ）＋ｋ（ｊ）ξ（ｊ）の二乗和の最小化を行うという制約が条件となり；および
ｂ）Ψ（ｉ）＝ζ（ｉ）−ｋ（ｉ）ξ（ｉ）という形の方程式は、与えられた予測および補間残差ζ（ｉ）およびξ（ｉ）に対してΨ（ｉ）およびｋ（ｉ）について解かれ、そうする際に、得られたｋ（ｉ）の値が、実質的に、ζ（ｉ）およびｋ（ｉ）についてζ（ｉ）＝Ψ（ｉ）＋ｋ（ｉ）ξ（ｉ）を解く際に得られるものであるという制約が条件となることを特徴とする請求項２に記載の適応フィルタ。
【請求項１３】
ＱＲ分解は、正弦および余弦回転パラメータの平方根の計算を必要としない等価物である平方根自由回転パラメータを採用することを特徴とする請求項１２に記載の適応フィルタ。
【請求項１４】
ゲインベクトルはカルマンゲインベクトル（ｋＮ（ｔ））であることを特徴とする請求項１または２に記載の適応フィルタ。
【請求項１５】
フィルタリングのためのデータとして提供される信号サンプルのシーケンス（ｘ（１）からｘ（ｔ））の補間残差（εＮ−ｉ，ｉ−１（ｔ−ｉ＋１））から導出されるゲインベクトル（ｋＮ（ｔ））によってフィルタの係数または重み（ｗ１（ｔ）からｗＮ（ｔ））を更新（１６）することを含むことを特徴とする適応フィルタリングのための方法。
【請求項１６】
適応フィルタリングのための方法であって、
ａ）予測残差（εｎＦ（ｔ），εｎＢ（ｔ））を導出するために、信号サンプルの入力シーケンスを処理するステップ（１２）と、
ｂ）予測残差（εｎＦ（ｔ），εｎＢ（ｔ））を補間残差（εＮ−ｉ，ｉ−１（ｔ−ｉ＋１））に変換するステップ（１４）と、
ｃ）補間残差（εＮ−ｉ，ｉ−１（ｔ−ｉ＋１））からゲインベクトル（ｋＮ（ｔ））の成分（ｋｉＮ（ｔ））を導出するステップ（１６）と、および、
ｄ）ゲインベクトル（ｋＮ（ｔ））と入力および参照信号（ｘ（ｔ），ｙ（ｔ））とを組み合わせ（１８）、適応フィルタリングを提供するために要求されるように、フィルタ係数または重み（ｗ１（ｔ）からｗＮ（ｔ））を更新するステップを含むことを特徴とする方法。
【請求項１７】
予測残差は最小二乗予測残差（εｎＦ（ｔ），εｎＢ（ｔ））であることを特徴とする請求項１６に記載の方法。
【請求項１８】
再帰性最小二乗格子（ＲＬＳＬ）アルゴリズムを使用して信号サンプルのシーケンス（ｘ（１）からｘ（ｔ））を処理する（１２）ことによって予測残差（εｎＦ（ｔ），εｎＢ（ｔ））を得るように構成されることを特徴とする請求項１６または１７に記載の方法。
【請求項１９】
各反復は残差（εｐ，ｆ（ｔ−ｆ））またはそれから導出される中間結果（εｐ＋１，ｆ（ｔ−ｆ），εｐ，ｆ＋１（ｔ−ｆ−１））の指数（例えばｆまたはｐ）を変更する反復手法によって、予測残差（εｎＦ（ｔ），εｎＢ（ｔ））を、ゲインベクトル成分（ｋｉＮ（ｔ））に対応する補間残差（εＮ−ｉ，ｉ−１（ｔ−ｉ＋１））に変換することを含むことを特徴とする請求項１６、１７、または、１８に記載の方法。
【請求項２０】
反復手法は、予測残差（εｎＦ（ｔ），εｎＢ（ｔ））を補間残差（εｐ，０（ｔ），ε０，ｆ（ｔ−ｆ））として扱い、補間残差（εｐ，０（ｔ），ε０，ｆ（ｔ−ｆ））を非正規化形ゲインベクトルの成分を提供する補間残差に変換するよう、指数（ｆまたはｐ）を適切に変更する分割征服手法であることを特徴とする請求項１９に記載の方法。
【請求項２１】
予測残差は最小二乗予測残差（εｎＦ（ｔ），εｎＢ（ｔ））であり、反復手法は、前方または後方残差（εｎＦ（ｔ），εｎＢ（ｔ））を、後続または先行する時系列信号サンプルの不在に対応する２つの指数（ｆ，ｐ）の１つについてゼロの値を持つ補間残差（εｐ，０（ｔ），ε０，ｆ（ｔ−ｆ））として扱い、反復は、ゼロ指数の補間残差（εｐ，０（ｔ），ε０，ｆ（ｔ−ｆ））を、同じく非正規化形ゲインベクトルの成分である他の補間残差（εＮ−ｉ，ｉ−１（ｔ−ｉ＋１））に変換するよう、ゼロ指数（０＝ｆまたはｐ）が十分に変更されるまで進行することを特徴とする請求項２０に記載の方法。
【請求項２２】
反復手法はまた、ゲインベクトル（ｋＮ（ｔ））の成分（ｋｉＮ（ｔ））に導く複数回の反復のシーケンスにおける反復（εｐ＋１，ｆ（ｔ−ｆ），εｐ，ｆ＋１（ｔ−ｆ−１））を、中間結果として扱い、反復は、中間結果をゲインベクトルの成分に対応する補間残差（εＮ−ｉ，ｉ−１（ｔ−ｉ＋１））に変換するよう、中間結果（εｐ＋１，ｆ（ｔ−ｆ），εｐ，ｆ＋１（ｔ−ｆ−１））の指数（ｆ，ｆ＋１，ｐ，ｐ＋１）が十分に変更されまで進行することを特徴とする請求項１９、２０、または２１に記載の方法。
【請求項２３】
Ｎは２ｘに等しく、ｘは整数である次数Ｎのデジタルフィルタを実施する方法であって、ゲインベクトル（ｋＮ（ｔ））の非正規化成分を生成するためのシーケンスにおける反復を含み、反復は中間点のすぐ隣および逆側の２つの残差（εＭＦ（ｔ）＝εＭ，０（ｔ），εＭＢ（ｔ）＝ε０，Ｍ（ｔ））の１つの使用で開始し、使用する残差（εＭ，０（ｔ），ε０，Ｍ（ｔ））は、反復シーケンスにおいて変化されない指数（Ｍ）が相対的に大きな値を有するものであり、関連する中間点は２つの量の中間であり、
ａ）２つの量の１つは補間残差（ε６３，０（ｔ））であり、他の１つはゲインベクトルが生成される関連する時系列のメンバ（ｘ（ｔ）＝ε０，０（ｔ））であるか、または、
ｂ）２つの量の１つは補間残差（ε６３，０（ｔ））であり、他の１つは以前の反復のための開始点（ε３２，０（ｔ））であるか、または、
ｃ）２つの量は以前の反復のためのそれぞれ開始および終了点（ε３２，０（ｔ），ε３２，３１（ｔ））であることを特徴とする請求項２２に記載の方法。
【請求項２４】
反復手法は、次数の各々がそれぞれ２の累乗であるフィルタの組合せとしてフィルタを扱うことを含むことを特徴とするＮは各々が２の累乗である整数の和に等しい次数Ｎのデジタルフィルタを実施する請求項２２に記載の方法。
【請求項２５】
ゲインベクトルの非正規化成分を生成するためのシーケンスにおける反復を含み、反復は中間点のすぐ隣および逆側の２つの残差の１つの使用で開始し、使用する残差は、反復シーケンスにおいて変化されない指数が相対的に大きな値を有するものであり、関連する中間点は２つの量の中間であり、
ａ）２つの量の１つは補間残差であり、他の１つはゲインベクトルが生成される関連する時系列のメンバであるか、または、
ｂ）２つの量の１つは補間残差であり、他の１つは以前の反復のための開始点であるか、または、
ｃ）２つの量は以前の反復のためのそれぞれ開始および終了点であることを特徴とする請求項２４に記載の方法。
【請求項２６】
ＱＲ分解手法によって、予測残差を、ゲインベクトルの成分に対応する補間残差に変換するすることを含み、ＱＲ分解手法において：
ａ）ζ（ｉ）＝Ψ（ｉ）＋ｋ（ｉ）ξ（ｉ）という形の方程式は、与えられた予測および補間残差Ψ（ｉ）および補間残差ξ（ｉ）に対して係数ζ（ｉ）およびｋ（ｉ）について解かれ、そうする際に、異なったサンプル指数ｊについて得られたΨ（ｊ）＋ｋ（ｊ）ξ（ｊ）の二乗和の最小化を行うという制約が条件となり；および
ｂ）Ψ（ｉ）＝ζ（ｉ）−ｋ（ｉ）ξ（ｉ）という形の方程式は、与えられた予測および補間残差ζ（ｉ）およびξ（ｉ）に対してΨ（ｉ）およびｋ（ｉ）について解かれ、そうする際に、得られたｋ（ｉ）の値が、実質的に、ζ（ｉ）およびｋ（ｉ）についてζ（ｉ）＝Ψ（ｉ）＋ｋ（ｉ）ξ（ｉ）を解く際に得られるものであるという制約が条件となることを特徴とする請求項１６に記載の方法。
【請求項２７】
ＱＲ分解は正弦および余弦回転パラメータの平方根の計算を必要としない等価物である平方根自由回転パラメータを採用することを特徴とする請求項２６に記載の方法。
【請求項２８】
ゲインベクトルはカルマンゲインベクトル（ｋＮ（ｔ））であることを特徴とする請求項１５または１６に記載の方法。
【請求項２９】
コンピュータ装置を制御して、フィルタリングのために提供される信号サンプルのシーケンス（ｘ（１）からｘ（ｔ））の補間残差（εＮ−ｉ，ｉ−１（ｔ−ｉ＋１））から導出されるゲインベクトル（ｋＮ（ｔ））によって、更新されたフィルタの係数または重み（ｗ１（ｔ）からｗＮ（ｔ））を生成する（１６）ように構成されることを特徴とする適応フィルタを実施するためのコンピュータプログラム。
【請求項３０】
適応フィルタを実施するためのコンピュータプログラムであって、コンピュータ装置を制御して、
ａ）予測残差（εｎＦ（ｔ），εｎＢ（ｔ））を導出するために信号サンプルの入力シーケンスを処理し（１２）、
ｂ）予測残差（εｎＦ（ｔ），εｎＢ（ｔ））を、補間残差（εＮ−ｉ，ｉ−１（ｔ−ｉ＋１））に変換し（１４）、
ｃ）補間残差（εＮ−ｉ，ｉ−１（ｔ−ｉ＋１））からゲインベクトル（ｋＮ（ｔ））の成分（ｋｉＮ（ｔ））を導出し（１６）、および、
ｄ）ゲインベクトル（ｋＮ（ｔ））と入力および参照信号（ｘ（ｔ），ｙ（ｔ））とを組み合わせ、適応フィルタリングを提供するために要求されるように、フィルタ係数または重み（ｗ１（ｔ）からｗＮ（ｔ））を更新するように構成されることを特徴とする方法。
【請求項３１】
予測残差は最小二乗予測残差（εｎＦ（ｔ），εｎＢ（ｔ））であることを特徴とする請求項３０に記載のコンピュータプログラム。
【請求項３２】
コンピュータ装置を制御して、再帰性最小二乗格子（ＲＬＳＬ）アルゴリズムを使用して信号サンプルのシーケンス（ｘ（１）からｘ（ｔ））を処理する（１２）ことによって予測残差（εｎＦ（ｔ），εｎＢ（ｔ））を得るように構成されることを特徴とする請求項３０または３１に記載のコンピュータプログラム。
【請求項３３】
コンピュータ装置を制御して、各反復が残差（εｐ，ｆ（ｔ−ｆ））またはそれから導出される中間結果（εｐ＋１，ｆ（ｔ−ｆ），εｐ，ｆ＋１（ｔ−ｆ−１））の指数（例えばｆまたはｐ）を変更する反復手法によって、予測残差（εｎＦ（ｔ），εｎＢ（ｔ））を、ゲインベクトル成分（ｋｉＮ（ｔ））に対応する補間残差（εＮ−ｉ，ｉ−１（ｔ−ｉ＋１））に変換する（１４）ように構成されることを特徴とする請求項３０、３１、または、３２に記載のコンピュータプログラム。
【請求項３４】
反復手法は予測残差（εｎＦ（ｔ），εｎＢ（ｔ））を補間残差（εｐ，０（ｔ），ε０，ｆ（ｔ−ｆ））として扱うことによって実施される分割征服手法（７０，７２）であり、コンピュータプログラムは、補間残差（εｐ，０（ｔ），ε０，ｆ（ｔ−ｆ））を非正規化形のゲインベクトル（ｋＮ（ｔ））の成分を提供する補間残差（εＮ−ｉ，ｉ−１（ｔ−ｉ＋１））に変換するよう、指数（ｆまたはｐ）が適切に変更されるまで進行する反復を提供することを特徴とする請求項３３に記載のコンピュータプログラム。
【請求項３５】
予測残差は最小二乗予測残差（εｎＦ（ｔ），εｎＢ（ｔ））であり、コンピュータプログラムは、前方または後方予測残差（εｎＦ（ｔ），εｎＢ（ｔ））を、後続または先行する時系列信号サンプルの不在に対応する２つの指数（ｆ，ｐ）の１つについてゼロの値を持つ補間残差（εｐ，０（ｔ），ε０，ｆ（ｔ−ｆ））として扱うことによって実行される反復手法を提供し、コンピュータプログラムは、ゼロ指数の補間残差（εｐ，０（ｔ），ε０，ｆ（ｔ−ｆ））を、同じく非正規化形ゲインベクトルの成分である他の補間残差に変換するよう、ゼロ指数（０＝ｆまたはｐ）が十分に変更されるまで進行する反復を提供することを特徴とする請求項３４に記載のコンピュータプログラム。
【請求項３６】
反復手法は、ゲインベクトル（ｋＮ（ｔ））の成分（ｋｉＮ（ｔ））に導く複数回の反復のシーケンスにおける反復（εｐ＋１，ｆ（ｔ−ｆ），εｐ，ｆ＋１（ｔ−ｆ−１））を、中間結果として扱うことも含み、コンピュータプログラムは、中間結果をゲインベクトル（ｋＮ（ｔ））の成分（ｋｉＮ（ｔ））に対応する補間残差（εＮ−ｉ，ｉ−１（ｔ−ｉ＋１））に変換するよう、中間結果（εｐ＋１，ｆ（ｔ−ｆ），εｐ，ｆ＋１（ｔ−ｆ−１））の指数（ｆ，ｆ＋１，ｐ，ｐ＋１）が十分に変更されるまで進行する反復を提供することを特徴とする請求項３３、３４、または、３５に記載のコンピュータプログラム。
【請求項３７】
Ｎが２ｘに等しく、ｘが整数である次数Ｎのデジタルフィルタを実施するコンピュータプログラムであって、コンピュータプログラムが、ゲインベクトル（ｋＮ（ｔ））の非正規化成分を生成するためのシーケンスにおける反復を提供し、反復は、中間点のすぐ隣および逆側の２つの残差（εＭＦ（ｔ）＝εＭ，０（ｔ），εＭＢ（ｔ）＝ε０，Ｍ（ｔ））の１つの使用で開始し、使用する残差（εＭＦ（ｔ）＝εＭ，０（ｔ），εＭＢ（ｔ）＝ε０，Ｍ（ｔ））は、反復シーケンスにおいて変化されない指数（Ｍ）が相対的に大きな値を有するものであり、関連する中間点は２つの量の間の中間であり：
ａ）２つの量の１つは補間残差（ε６３，０（ｔ））であり、他の１つはゲインベクトルが生成される関連する時系列のメンバ（ｘ（ｔ）＝ε０，０（ｔ））であるか、または、
ｂ）２つの量の１つは補間残差（ε６３，０（ｔ））であり、他の１つは以前の反復のための開始点（ε３２，０（ｔ））であるか、または、
ｃ）２つの量は以前の反復のためのそれぞれ開始および終了点（ε３２，０（ｔ），ε３２，３１（ｔ））であることを特徴とする請求項３６に記載のコンピュータプログラム。
【請求項３８】
反復手法は、次数の各々がそれぞれ２の累乗であるフィルタの組合せとしてフィルタを扱うことを含むことを特徴とするＮは各々が２の累乗である整数の和に等しい次数Ｎのデジタルフィルタを実施する請求項３６に記載のコンピュータプログラム。
【請求項３９】
コンピュータプログラムが、ゲインベクトルの非正規化成分を生成するためのシーケンスにおける反復を提供し、反復は、中間点のすぐ隣および逆側の２つの残差の１つの使用で開始し、使用する残差は、反復シーケンスにおいて変化されない指数が相対的に大きな値を有するものであり、関連する中間点は２つの量の間の中間であり：
ａ）２つの量の１つは補間残差であり、他の１つはゲインベクトルが生成される関連する時系列のメンバであるか、または、
ｂ）２つの量の１つは補間残差であり、他の１つは以前の反復のための開始点であるか、または、
ｃ）２つの量は以前の反復のためのそれぞれ開始および終了点であることを特徴とする請求項３８に記載のコンピュータプログラム。
【請求項４０】
コンピュータプログラムは、ＱＲ分解手法によって、予測残差を、ゲインベクトルの成分に対応する補間残差に変換し、ＱＲ分解手法において：
ａ）ζ（ｉ）＝Ψ（ｉ）＋ｋ（ｉ）ξ（ｉ）という形の方程式は、与えられた予測および補間残差Ψ（ｉ）およびξ（ｉ）に対して補間残差ζ（ｉ）および係数ｋ（ｉ）について解かれ、そうする際に、異なったサンプル指数ｊについて得られたΨ（ｊ）＋ｋ（ｊ）ξ（ｊ）の二乗和の最小化を行うという制約が条件となり；および
ｂ）Ψ（ｉ）＝ζ（ｉ）−ｋ（ｉ）ξ（ｉ）という形の方程式は、与えられた予測および補間残差ζ（ｉ）およびξ（ｉ）に対してΨ（ｉ）およびｋ（ｉ）について解かれ、そうする際に、得られたｋ（ｉ）の値が、実質的に、ζ（ｉ）およびｋ（ｉ）についてζ（ｉ）＝Ψ（ｉ）＋ｋ（ｉ）ξ（ｉ）を解く際に得られるものであるという制約が条件となることを特徴とする請求項３０に記載のコンピュータプログラム。
【請求項４１】
ＱＲ分解は、正弦および余弦回転パラメータの平方根の計算を必要としない等価物である平方根自由回転パラメータを採用することを特徴とする請求項４０に記載のコンピュータプログラム。
【請求項４２】
ゲインベクトルはカルマンゲインベクトル（ｋＮ（ｔ））であることを特徴とする請求項２９または３０に記載のコンピュータプログラム。
【発明の詳細な説明】
【０００１】
本発明は適応フィルタ、および、これを実施するための方法とコンピュータプログラムに関する。
【０００２】
フィルタリングは、信号処理における最も一般的な手順の１つである。フィルタは、所望の特定の諸特性を有する出力信号を作成するために、その入力において信号を処理する。これらの特性が取る正確な形は、特定のフィルタパラメータが取る値によって決定される。線形フィルタにおいて、出力は、入力信号と、タップ付遅延ラインによって生成される遅延入力信号との重み付けされた線形的組合せである。フィルタは、この線形的組合せに重み付けをするために使用される重みである制御可能なパラメータを有する。
【０００３】
フィルタの１つの知られている形は、１つの入力信号のみを備えた時系列フィルタ（または、適応可能であることもある横断フィルタ）である。このフィルタは、遅延信号の線形的組合せを形成する。フィルタの重みは、入力信号の異なった周波数成分を選択または拒絶するために選ぶことができる。フィルタの他の形は、位相アレーレーダビームフォーマである。受信モードにおいて、このようなビームフォーマは空間的に離れたセンサのアレーから信号を受信し、信号は場面から反射されたレーダ波の受信に応じて生成される。フィルタの重みは、センサにおけるレーダ波の到着の方向によってセンサアレー信号の成分を、例えば、選択または拒絶するために選ぶことができ、そのようなビームフォーマは、その空間的選択特性のために、空間フィルタであると言われる。ソナーアレービームフォーマは空間フィルタの関連例であり、ここで、受信モードにおいて、ソナートランスデューサのアレーからの信号およびこれらの遅延信号は、フィルタへの入力を構成する。ソナービームフォーマは、フィルタの重みを変化させることによって、到着の方向と周波数の双方に基づいて信号を選択または拒絶することができる。レーダおよびソナービームフォーマは、送信されたビームを構成するためにフィルタ技術が使用できる送信モードにおいても動作可能である。
【０００４】
有限インパルス応答（ＦＩＲ）フィルタまたは横断フィルタは、それぞれが、個々の乗算器および乗算係数に関連するクロック活性化レジスタが直列接続された一群を含むタップ付遅延ラインとして、ハードウエア内に実施することができるフィルタの知られている形態である。しかし、コンピュータシステムで実行し、アナログからデジタルへの電子的形態の変換の後にセンサからデータを受け入れるソフトウエアにおいて、ＦＩＲフィルタは、等価的に、益々実施されている。遅延ライン型のものにおいて、ｉがクロックサイクル指数を示す、データ成分ｘ（ｉ）のシーケンスはラインに沿ってクロック制御され、各レジスタは一時に１つの成分を保持する。データ成分の総数ｍはレジスタの数Ｎより非常に大きい。そのため、Ｎ個の連続した成分のみがいつでもラインを占有する。ラインは、Ｎ番目のクロックサイクル上において、データ成分ｘ（１）〜ｘ（Ｎ）によって占有される。ラインをクロック制御することは、シーケンスを１つのレジスタだけ前進させる。そのため、先頭の成分はラインの一端を離れ、新しい成分が別の一端に導入される。ｐ番目のクロックサイクル上において、ラインはデータ成分ｘ（ｐ−Ｎ＋１）〜ｘ（ｐ）によって占有される。各クロックサイクル上において、各レジスタ内のデータ成分は、各場合における関連乗算器内の個々のフィルタ係数（ｉ番目のレジスタについてはｗｉ、但し、ｉ＝１〜Ｎ）によって乗算され、結果として得られる積は、ｐ番目のサイクルについてｚＮ（ｐ）である結果を形成するために加算される。すなわち：
【数１】
0004398146.tif 000002
代わりに、数式（１）は、成分ｗ１〜ｗＮ（横断フィルタ係数または重み）を有する重みベクトルｗと、成分ｘ（ｐ）〜ｘ（ｐ−Ｎ＋１）を有するデータベクトルｘＮ（ｐ）とのスカラ（ドット）積としても表すことができる。すなわち：
【数２】
0004398146.tif 000003
ここで、肩文字の指数Ｔはベクトル転置行列を示す。
【０００５】
有用な信号に加えて、不要な雑音または他の不正な成分を含むデータの集合から意味のある情報を得ることは一般的な要求であり、信号雑音比を改善するために、これに線形フィルタリングを使用することは知られている。しかし、雑音および信号の特性が未知であれば、フィルタの選定は不可能でなくとも困難であり、したがって、システムへのデータの入力に応じて修正可能な特性を備えた適応フィルタを使用することが望ましくなり、この点に関して、フィルタの適応性は重要であり、そのため、フィルタ特性は、データ特性に関する評価または仮定を行うことによる演繹の代わりにフィルタリングされるべき入力データから決定される。フィルタの適応性は、係数、および、したがって、変更できる特性も備えた適応フィルタによって実現される。
【０００６】
適応フィルタは、上述したようにレーダおよびソナーなどの分野における、および、同様に、画像および音声の通信および処理におけるアプリケーションを有する。それらは、中でも、チャンネル等化、信号検出（すなわち、マッチングさせたフィルタリング）、音響エコー消去、および、適応雑音消去を行うために使用することができる。
【０００７】
適応フィルタの典型的な例は、「手を使わない」電話システムのエコー消去器のものである。ここで、電話のマイクロフォンは呼を発している人からの音声だけでなく、電話のスピーカによって音声が出力される呼の受け手の音声も拾う。もし是正措置が取られなければ、受け手の音声も受け手に送られ、エコーとして現われる。もし受け手が手を使わない電話を使用しているなら、返答は発呼者に戻されることがあり、正帰還または「ハウリング」をもたらすことがある。
【０００８】
エコーは適応フィルタによって除去することができる。電話のスピーカはフィルタへの入力信号となる音声信号ｘ（ｔ）によって駆動され、参照信号ｙ（ｔ）が電話のマイクロフォンによって拾われる。フィルタ係数は、ｙ（ｔ）におけるエコー信号を消去するために適応的に調整される。エコーが除去されたなら、発呼者の音声のみを含む残差信号が電話の呼の受け手に送信される。この残差信号は、エラー信号ｅＮ（ｔ）と呼ぶこともでき、後述するようにフィルタ係数を調整する際に使用される。
【０００９】
適応フィルタリングのためのデジタル信号処理アルゴリズムの開発に関しては、かなりの研究がある。２つの広範な種類のアルゴリズムがある。すなわち、ブロックベースアルゴリズムと再帰性アルゴリズムである。前者は有限な長さのブロックのデータを処理するために使用され、後者は連続したデータストリームを処理するために使用される。アルゴリズムの選定は意図された使用の分野によるが、多くの問題のために、再帰性アルゴリズムはより魅力的である。
【００１０】
長年にわたって、２つのタイプの再帰性適応フィルタリングアルゴリズムのみが知られていた。確率傾斜下降（Ｓｔｏｃｈａｓｔｉｃ  Ｇｒａｄｉｅｎｔ  Ｄｅｓｃｅｎｔ）（ＳＧＤ）アルゴリズムと再帰性最小二乗（Ｒｅｃｕｒｓｉｖｅ  Ｌｅａｓｔ  Ｓｑｕａｒｅｓ）（ＲＬＳ）アルゴリズムである。より最近には、新しいタイプの再帰性適応フィルタリングアルゴリズムが導入され、これはＳＧＤおよびＲＬＳアルゴリズムの混成型として見ることができる。
【００１１】
（よく知られている最小平均二乗（ＬＭＳ）アルゴリズムが典型である）ＳＧＤアルゴリズムは、瞬間ごとには数学的演算をほとんど要求せず、有限の精度数値効果、すなわち、小さなデジタル量における大きな部分的エラーに対しては堅牢である。残念ながら、ＬＭＳアルゴリズムは、ほとんどの場合、最適な解に収斂するのが非常に緩慢である。
【００１２】
他方、ＲＬＳアルゴリズムは収斂が非常に迅速である。しかし、これは単位時間当りにより多くの数学的演算を要求し、このことはこのアルゴリズムを完全に非現実的なものにすることもある。例えば、手を使わない電話のためのフィルタは、４×１０１０フロップ／秒に相当する１００μ秒の１クロックサイクルにおいて、４百万の浮動小数点算術演算（フロップ）を要求し、これは、現在、単一のコンピュータプロセッサを使用しては達成不可能である。
【００１３】
さらに、ＲＬＳアルゴリズムは数学的な不安定性を示すことがある。すなわち、それは、有限精度数値効果のために、小さな不正確な量による除算などを適切に演算することに失敗することがある。例えば、８ビットの数は、最も重要でないビットの値に関して不正確であることがある。もしこの数の最も重要でないビット以外の全てのビットがゼロ、すなわち、この数が０００００００１であれば、不正確さは、これが００００００００になることを導くことがある。計算は、この場合ゼロによる除算を含むことがある。
【００１４】
さらなる問題は、いくつかのＲＬＳアルゴリズムが要求されるフィルタ係数を明示的には計算しないが、代わりに、いくつかのアプリケーションに対してより有用ではない関連する量を計算することである。
【００１５】
新しい種類の混成型アルゴリズムは、収斂速度とコンピュータ処理の重荷という相反する問題に対処するために導入された。例は、アフィン射影（Ａｆｆｉｎｅ  Ｐｒｏｊｅｃｔｉｏｎ）アルゴリズムおよび高速ニュートン（Ｆａｓｔ  Ｎｅｗｔｏｎ）アルゴリズムである。ここで、ＬＭＳ型のアルゴリズムとＲＬＳアルゴリズムは、適応フィルタリングの問題を解決するために協働する。ＲＬＳアルゴリズムは、適応フィルタの本来の問題よりはかなり小さな問題を解決するために使用され、そのため、多過ぎる追加的コンピュータ処理の負荷を課すことはない。ＬＭＳとＲＬＳは協働して、適応フィルタが、ＬＭＳのみの場合よりは迅速だが通常は適切なＲＬＳに基づく適応フィルタと同じ程には迅速でなく収斂することを可能にする。これらのアルゴリズムは、アルゴリズムに対するＲＬＳ成分が数値的に不安定になることがあるという事実から損害を被っている。
【００１６】
現時点では、ＲＬＳアルゴリズムには３つの種類がある。すなわち、二次ＲＬＳアルゴリズム、高速横断フィルタアルゴリズム、および、ＲＬＳ格子アルゴリズムである。二次ＲＬＳアルゴリズムは数値的には安定であるが、決定されるべきＮ個の未知の係数を有する問題のために、Ｎ２に比例する、クロックサイクル当りの数学的演算数を要求するという欠点を有する。大きなＮ（例えば、典型的にＮ＝２０００である音響エコー消去の問題）を備えたアプリケーションについては、このことが高価なハードウエアとなるか、または、現在の技術を考えれば非現実的でさえある。
【００１７】
他方、高速横断フィルタアルゴリズムおよびＲＬＳ格子アルゴリズムは、Ｎに比例するクロックサイクル当りの数学的演算数を要求するのみである（「高速」アルゴリズムと呼ぶ）。残念ながら、高速横断フィルタアルゴリズムは、その数値的不安定性、すなわち、計算における不正確さと四捨五入エラーから生じる有限精度数値効果に対する敏感さのために大きな問題に対しては実質的に使用不可能である。さらに、ＲＬＳ格子アルゴリズムが数値的に安定であることは可能であるが、それは最も望ましいパラメータ（フィルタ係数）を直接には作成しない。
【００１８】
要約すれば、ＲＬＳアルゴリズムは、それがいつでもフィルタ係数（または、関連する量）の最適な集合を計算する限りにおいて、最適な性能を有する。次数Ｎのシングルチャンネルの問題、すなわち、決定するべきＮ個の量を有する問題については、ＲＬＳアルゴリズムは３つの範疇に分けられる。
【００１９】
Ｏ（Ｎ２）アルゴリズム：コンピュータ処理が高価、Ｎの大きな値については禁止的に高価。
【００２０】
Ｏ（Ｎ）ＬＳ格子アルゴリズム：コンピュータ処理は高価でない（高速）が、横断フィルタの重みは抽出が困難。
【００２１】
Ｏ（Ｎ）高速横断フィルタアルゴリズム：コンピュータ処理は高価でない（高速）が、数値的に不安定。
【００２２】
ここで、「Ｏ」は、各々の場合に関連する括弧内にあるように、クロックサイクル当りに行われる計算数の大きさ（ＮまたはＮ２）の次数を示す。
【００２３】
アプリケーションの分野にかかわらず、ほとんどの適応フィルタリングアプリケーションは、性能は可能な限り高いが複雑さの低いアルゴリズムの使用を要求する。しかし、アルゴリズムが全ての現実的な意図に対して少なくとも数値的に安定であることは必要条件である。さらに、多くの適応フィルタリングアプリケーションは実際のフィルタの重み自体を要求し、他のいくつかの関連するパラメータは要求しない。従来の技術では、フィルタへの入力が、部分的にせよ全体的にせよ、１つまたは複数の遅延信号で構成されている時に、これらの特性を備えた適応フィルタのためのＲＬＳアルゴリズムが存在しない。本発明の目的は、適応フィルタの代案となる形態を提供することである。
【００２４】
本発明は、フィルタに印加された信号サンプルのシーケンスの補間残差から導出されるゲインベクトルの手段によって、フィルタの重みを更新するように構成されることを特徴とする適応フィルタを提供する。
【００２５】
これに関連して、適応フィルタの重みまたは係数を更新する目的のための従来技術において、補間残差からの導出ではないものの、「カルマン」ゲインベクトルが知られている。補間残差は予測残差の一種である。予測残差は、直接得られたデータ成分と、この成分に関連する他のデータから補間されるこの成分の予測との間の差である。補間残差は、このデータ成分に先行および後続する双方のデータを使用して得られる。直接得られた成分からそれぞれ前方および後方補間を使用して得られた前方および後方予測残差もある。
【００２６】
本発明は多くの長所を提供する。本発明は適応フィルタの代案となる形態である。ＲＬＳ格子アルゴリズムに基づく従来技術のフィルタとは異なり、要求されるフィルタの重みは、他のいくつかの関連するパラメータとは異なり直接導出され、本発明はＲＬＳアルゴリズム、または、信号サンプルの特性に関する簡略化のための仮定に基づいてコンピュータ処理の負荷の削減されたアルゴリズムにより実施することができる。本発明が、代案となる手法より数値的に堅牢である結果を提供することを期待されていることを示す優れた理論的理由もある。
【００２７】
好ましい実施形態において、本発明は、
ａ）予測残差を導出するために、信号サンプルの入力シーケンスを処理し、
ｂ）予測残差を補間残差に変換し、
ｃ）補間残差からゲインベクトルの成分を導出し、および、
ｄ）ゲインベクトルを入力および参照信号と組み合わせ、適応フィルタリングを提供するために要求されるように、フィルタ係数または重みを更新するように構成されることを特徴とする適応フィルタも提供する。
【００２８】
ゲインベクトルはカルマンゲインベクトルであってもよい。予測残差は最小二乗予測残差であってもよく、これは、再帰性最小二乗格子アルゴリズムを使用して信号サンプルのシーケンスを処理することによって得られてもよい。
【００２９】
各反復が残差またはそれから導出された中間量の指数（後に定義する）を変更する反復手法によって、予測残差は、ゲインベクトルの成分に対応する補間残差に変換することもできる。反復手法は、予測残差を補間残差として扱うことによって実施される分割征服手法であってもよく、反復は、予測残差を補間残差に変換して非正規化形ゲインベクトルの成分を提供するために、指数が適切に変更されるまで進行するように構成されている。
【００３０】
反復手法は、予測残差を、２つの指数の１つに対するゼロの値を持つ補間残差として扱うことによって実施してもよい。これは、後続または先行する時系列信号サンプルの不在に対応する。反復は、各場合のゼロ指数が前方または後方残差を非正規化形ゲインベクトルの成分でもある補間残差に変換するために十分に変更されるまで進行するように構成される。これは、中間結果として、非正規化ゲインベクトルの成分に導く中間結果のシーケンスにおける反復を扱うことも含んでよく、反復は、中間結果の指数がそのような結果をゲインベクトルの成分に対応する補間残差に変換するために、十分に変更されるまで進行するように構成される。
【００３１】
Ｎが２ｘに等しく、ｘが正の整数である次数Ｎの適応フィルタについて、ゲインベクトルの非正規化成分を生成するためのシーケンスにおける反復は、中間点のすぐ隣および逆側の２つの残差の１つの使用で開始してもよく、使用する残差は、反復シーケンスにおいて変化されない比較的大きな値の指数を有する残差であり、関連する中間点は、２つの量の間の中間であり：
ａ）２つの量の１つは補間残差であり、他の１つはいくつかのゲインベクトルが生成される関連する時系列のメンバであるか、または、
ｂ）２つの量の１つは補間残差であり、他の１つは以前の反復のための開始点であるか、または、
ｃ）２つの量は以前の反復のためのそれぞれ開始および終了点である。
【００３２】
Ｎが２の累乗ではない次数Ｎの適応フィルタについて、反復手法はまだ使用することができるが、等しくない次数の重みベクトルの組合せとしてフィルタの重みベクトルを扱うことを含む。例えば、もしＮが、各々が２の累乗である整数の和に等しければ、フィルタは、次数の各々がそれぞれ２の累乗であるフィルタの組合せとして扱うことができる。
【００３３】
ゲインベクトルの非正規化成分を生成するためのシーケンスにおける反復は、中間点のすぐ隣および逆側の２つの残差の１つの使用で開始してもよく、使用する残差は、反復シーケンスにおいて変化されない指数の比較的大きな値を有するものであり、関連する中間点は、２つの量の中間であり：
ａ）２つの量の１つは補間残差であり、他の１つはいくつかのゲインベクトルが生成される関連する時系列のメンバであるか、または、
ｂ）２つの量の１つは補間残差であり、他の１つは以前の反復のための開始点であるか、または、
ｃ）２つの量は以前の反復のためのそれぞれ開始および終了点である。
【００３４】
本発明のフィルタは、ＱＲ分解手法によって、予測残差をゲインベクトルの成分に対応する補間残差に変換するよう構成してもよく、この手法において：
ａ）ζ（ｉ）＝Ψ（ｉ）＋ｋ（ｉ）ξ（ｉ）という形の方程式は、与えられたΨ（ｉ）およびξ（ｉ）に対してζ（ｉ）およびｋ（ｉ）について解かれ、そうする際に、異なったサンプル指数ｊについて得られたΨ（ｊ）＋ｋ（ｉ）ξ（ｊ）の二乗和の最小化を行うという制約が条件となり；および
ｂ）Ψ（ｉ）＝ζ（ｉ）−ｋ（ｉ）ξ（ｉ）という形の方程式は、与えられたζ（ｉ）およびξ（ｉ）に対してΨ（ｉ）およびｋ（ｉ）について解かれ、そうする際に、得られたｋ（ｉ）の値が、実質的に、ζ（ｉ）およびｋ（ｉ）についてζ（ｉ）＝Ψ（ｉ）＋ｋ（ｉ）ξ（ｉ）を解く際に得られるものであるという制約が条件となる。
【００３５】
ＱＲ分解は、正弦および余弦の回転パラメータの平方根自由等価物を採用するように構成されてもよい。
【００３６】
代案となる態様において、本発明は、フィルタリングのためのデータとして提供される信号サンプルのシーケンスの補間残差から導出されるゲインベクトルを備えたフィルタの重みを更新することを含むことを特徴とする適応フィルタのための方法を提供する。
【００３７】
好ましい実施形態において、本発明の方法は：
ａ）予測残差を導出するために、信号サンプルの入力シーケンスを処理するステップと、
ｂ）予測残差を補間残差に変換するステップと、
ｃ）補間残差からゲインベクトルの成分を導出するステップと、および、
ｄ）ゲインベクトルと入力および参照信号とを組み合わせ、適応フィルタリングを提供するために要求されるように、フィルタ係数または重みを更新するステップを含む。
【００３８】
予測残差は、再帰性最小二乗格子アルゴリズムを使用して信号サンプルのシーケンスを処理することによって得られる最小二乗予測残差であってもよい。
【００３９】
各反復が残差またはそれから導出される中間量の指数（後述する）を変更する反復手法によって、予測残差は、ゲインベクトル成分に対応する補間残差に変換してもよい。反復手法は、予測残差を補間残差として扱い、予測残差を補間残差に変換して非正規化形ゲインベクトルの成分を提供するために指数を適切に変更する分割征服手法であってもよい。この手法は、予測残差を、２つの指数の１つについてゼロの値を持つ補間残差として扱うことができる。これは、後続または先行する時系列信号サンプルの不在に対応し、前方または後方残差を、同じく非正規化形ゲインベクトルの成分である補間残差に変換するために、各場合においてゼロ指数を十分に変更する。
【００４０】
反復手法はまた、中間結果として、ゲインベクトルの成分に導く中間結果のシーケンスにおける反復を扱うことができ、中間結果の指数を、そのような結果をゲインベクトルの成分に対応する補間残差に変換するために、十分に変更する。
【００４１】
本フィルタリング方法は、Ｎが２ｘに等しく、ｘが正の整数である次数Ｎのフィルタリングを実施することができ、ゲインベクトルの非正規化成分を生成するためのシーケンスにおける反復を含み、反復は、中間点のすぐ隣および逆側の２つの残差の１つの使用で開始し、使用する残差は、反復シーケンスにおいて変化されない指数の比較的大きな値を有するものであり、関連する中間点は２つの量の中間であり：
ａ）２つの量の１つは補間残差であり、他の１つはいくつかのゲインベクトルが生成される関連する時系列のメンバであるか、または、
ｂ）２つの量の１つは補間残差であり、他の１つは以前の反復のための開始点であるか、または、
ｃ）２つの量は以前の反復のためのそれぞれ開始および終了点であることを特徴とする。
【００４２】
本フィルタリング方法は、Ｎが２の累乗ではない次数Ｎのフィルタリングを実施することができ、反復方法は、次数の各々がそれぞれ２の累乗である重みベクトルの組合せとしてフィルタを扱うことを含むことを特徴とする。この方法は、ゲインベクトルの非正規化成分を生成するためのシーケンスにおける反復を含んでもよく、反復は中間点のすぐ隣および逆側の２つの残差の１つの使用で開始し、使用する残差は反復シーケンスにおいて変化されない指数の比較的大きな値を有するものであり、関連する中間点は２つの量の中間であり：
ａ）２つの量の１つは補間残差であり、他の１つはいくつかのゲインベクトルが生成される関連する時系列のメンバであるか、または、
ｂ）２つの量の１つは補間残差であり、他の１つは以前の反復のための開始点であるか、または、
ｃ）２つの量は以前の反復のためのそれぞれ開始および終了点である。
【００４３】
ＱＲ分解手法によって、予測残差は、ゲインベクトルの成分に対応する補間残差に変換することができ、この手法において：
ａ）ζ（ｉ）＝Ψ（ｉ）＋ｋ（ｉ）ξ（ｉ）という形の方程式は、与えられたΨ（ｉ）およびξ（ｉ）に対してζ（ｉ）およびｋ（ｉ）について解かれ、そうする際に、異なったサンプル指数ｊについて得られたΨ（ｊ）＋ｋ（ｊ）ξ（ｊ）の二乗和の最小化を行うという制約が条件となり；および
ｂ）Ψ（ｉ）＝ζ（ｉ）−ｋ（ｉ）ξ（ｉ）という形の方程式は、与えられたζ（ｉ）およびξ（ｉ）に対してΨ（ｉ）およびｋ（ｉ）について解かれ、そうする際に、得られたｋ（ｉ）の値が、実質的に、ζ（ｉ）およびｋ（ｉ）についてζ（ｉ）＝Ψ（ｉ）＋ｋ（ｉ）ξ（ｉ）を解く際に得られるものであるという制約が条件となる。
【００４４】
ＱＲ分解は、正弦および余弦の回転パラメータの平方根自由等価物を採用することができる。
【００４５】
さらなる態様において、本発明は、フィルタリングのためのデータとして提供される信号サンプルのシーケンスの補間残差から導出されるゲインベクトルの手段によって、更新されたフィルタの重みを生成するように構成されることを特徴とする適応フィルタを実施するためのコンピュータプログラムを提供する。
【００４６】
好ましい実施形態において、本発明の方法は：
ａ）予測残差を導出するために、信号サンプルの入力シーケンスを処理し、
ｂ）予測残差を補間残差に変換し、
ｃ）補間残差からゲインベクトルの成分を導出し、および、
ｄ）ゲインベクトルと入力および参照信号と組み合わせ、適応フィルタリングを提供するために要求されるように、フィルタ係数または重みを更新するように構成されることを特徴とする適応フィルタを実施するためのコンピュータプログラムを提供する。
【００４７】
このコンピュータプログラムは、予測残差を、各反復が残差またはそれから導出される中間量の後述する指数を変更する反復手法によって、ゲインベクトル成分に対応する補間残差に変換するように構成することができる。反復手法は、予測残差を補間残差として扱うことによって実施される分割征服手法であってもよく、ここで、反復は、予測残差を補間残差に変換して非正規化形ゲインベクトルの成分を提供するために、指数が適切に変更されるまで進行するように構成されている。このプログラムは、予測残差を、２つの指数の１つに対するゼロの値を持つ補間残差として扱うことによって実施することができる。これは、後続または先行する時系列信号サンプルの不在に対応し、ここで、反復は、各場合のゼロ指数が、前方または後方残差を、同じく非正規化形ゲインベクトルの成分である補間残差に変換するために十分に変更されるまで、進行するように構成される。
【００４８】
反復手法は、中間結果として、ゲインベクトルの成分に導く中間結果のシーケンスにおける反復を扱うことも含んでよく、ここで、反復も、中間結果の指数が、そのような結果を、ゲインベクトルの成分に対応する補間残差に変換するために十分に変更されるまで進行するように構成される。
【００４９】
本コンピュータプログラムは、Ｎが２ｘに等しく、ｘが正の整数である次数Ｎの適応フィルタを実施することができ、ゲインベクトルの非正規化成分を生成するためのシーケンスにおける反復が、中間点のすぐ隣および逆側の２つの残差の１つの使用で開始し、使用する残差は、反復シーケンスにおいて変化されない指数の比較的大きな値を有するものであり、関連する中間点は２つの量の中間であり：
ａ）２つの量の１つは補間残差であり、他の１つはいくつかのゲインベクトルが生成される関連する時系列のメンバであるか、または、
ｂ）２つの量の１つは補間残差であり、他の１つは以前の反復のための開始点であるか、または、
ｃ）２つの量は以前の反復のためのそれぞれ開始および終了点であることを特徴とする。
【００５０】
本コンピュータプログラムは、Ｎが２の累乗ではない次数Ｎの適応フィルタを実施することができ、反復手法が、重みベクトルを次数の各々がそれぞれ２の累乗である重みベクトルの組合せとして扱うことを含むことを特徴とする。
【００５１】
ゲインベクトルの非正規化成分を生成するためのシーケンスにおける反復は、中間点のすぐ隣および逆側の２つの残差の１つの使用で開始することができ、使用する残差は、反復シーケンスにおいて変化されない指数の比較的大きな値を有する残差であり、関連する中間点は、２つの量の間の中間であり：
ａ）２つの量の１つは補間残差であり、他の１つはゲインベクトルが生成される関連する時系列のメンバであるか、または、
ｂ）２つの量の１つは補間残差であり、他の１つは以前の反復のための開始点であるか、または、
ｃ）２つの量は以前の反復のためのそれぞれ開始および終了点である。
【００５２】
コンピュータプログラムは、ＱＲ分解手法によって、予測残差を、ゲインベクトルの成分に対応する補間残差に変換するように構成することができ、この手法において：
ａ）ζ（ｉ）＝Ψ（ｉ）＋ｋ（ｉ）ξ（ｉ）という形の方程式は、与えられたΨ（ｉ）およびξ（ｉ）に対してζ（ｉ）およびｋ（ｉ）について解かれ、そうする際に、異なったサンプル指数ｊについて得られたΨ（ｊ）＋ｋ（ｉ）ξ（ｊ）の二乗和の最小化を行うという制約が条件となり；および
ｂ）Ψ（ｉ）＝ζ（ｉ）−ｋ（ｉ）ξ（ｉ）という形の方程式は、与えられたζ（ｉ）およびξ（ｉ）に対してΨ（ｉ）およびｋ（ｉ）について解かれ、そうする際に、得られたｋ（ｉ）の値が、実質的に、ζ（ｉ）およびｋ（ｉ）についてζ（ｉ）＝Ψ（ｉ）＋ｋ（ｉ）ξ（ｉ）を解く際に得られるものであるという制約が条件となる。
【００５３】
ＱＲ分解は、正弦および余弦の回転パラメータの平方根自由等価物を採用するように構成することができる。
【００５４】
本発明がより完全に理解されるために、添付の図面を参照して、その実施形態を例としてのみの方法によって以下に説明する。
【００５５】
格子アルゴリズムではないこれらの従来技術のＲＬＳアルゴリズムにおいて、「カルマンゲイン」ベクトルｋＮ（ｔ）と呼ばれるものは、時系列、すなわち、時間ｔの関数として入力信号ｘ（ｔ）の変分を表すデータ値の系列、を構成する連続的な入力信号の各々の受領に際しＮ個の適応フィルタ係数を更新するために使用される。ここで、ｔは連続的なデジタル信号サンプル（クロックサイクル）間の間隔を単位とし、整数値１、２、などを有する。
【００５６】
Ｎがフィルタ係数の数（フィルタの次数）として、時間ｔおよびｔ−１における適応フィルタ係数のベクトルをｗＮ（ｔ）およびｗＮ（ｔ−１）とすると、新しい信号サンプルの入力に応じてフィルタ係数を適応的に更新するための演算は、以下の式によって定義される。
【数３】
0004398146.tif 000004
ここで、
【数４】
0004398146.tif 000005
であり、これは演繹エラーとして知られており、ｘＮ（ｔ）は上記に検討したようにｘ（ｔ）からｘ（ｔ−Ｎ＋１）の入力信号値で構成される成分を備えたベクトルであり、肩文字指数Ｔは転置行列を示し、ｙ（ｔ）は手を使わない電話システムの例において既に述べた適応フィルタリングにおける使用のために検出された参照信号の直近の値である。したがって、ｘＮ（ｔ）およびｙ（ｔ）は知られている量である。カル
マンゲインベクトルｋＮ（ｔ）は従来から以下のように定義されている。
【数５】
0004398146.tif 000006
ここで、ＭＸＸ（ｔ）は、
【数６】
0004398146.tif 000007
によって与えられる入力信号の共分散行列であり、ｘＮ（ｔ−１）は、上記に検討したようにｘ（ｔ−ｉ）からｘ（ｔ−ｉ−Ｎ＋１）の入力信号値で構成される成分を備えたＮ次元（列）ベクトルであり、
【数７】
0004398146.tif 000008
はそれの転置（行ベクトル）である。パラメータＬ１は総和に含まれるサンプルの数を決定する。時々、Ｌ１は固定された数に選定され、時々、これは、時間とともに変化するように構成される。例えば、Ｌ１＝ｔ＋１は一般的である。式（６）の総和は、もし直近のデータ値を廃棄することが決定されたなら、ｉの非ゼロ値からでも開始できる。項β１は「忘却係数」と呼ばれるものである。これは０＜β１≦１の範囲の値を有し、通常は０．９９＜β１＜１．０であり、データ成分を漸減し、そのため、直近のデータ成分ｘ（ｔ）は漸減されず、その直前のものが一度漸減され、次のものは２回、それのｎ番目の前のものはｎ回漸減される。これの効果は、直近のデータに有利に式（６）の総和にバイアスをかけることである。すなわち、これは、データ成分が使用される度にデータ成分の値を減じる。そのため、古いデータは、より最近のデータに比較して、解に対して次第に影響が少なくなる。信号処理における忘却係数の使用は知られている。例えば、ＭｃＷｈｉｒｔｅｒの米国特許第４，７２７，５０３号を参照。
【００５７】
カルマンゲインベクトルを使用するほとんどのＲＬＳアルゴリズムは、上記の公式またはそれに関連するものを使用して、計算する。
【００５８】
しかし、本発明によれば、時間ｔにおける信号について、Ｎ次カルマンゲインベクトルｋＮ（ｔ）のｉ番目の成分
【数８】
0004398146.tif 000009
も
【数９】
0004398146.tif 000010
によって与えられることが発見されている。ここで、εＮ−ｉ，ｉ−１（ｔ−ｉ＋１）は、定義および導出を後述する帰納的最小二乗補間残差と呼ばれるものである。ＥＮ−ｉ，ｉ−１（ｔ−ｉ＋１）は、補間残差εＮ−ｉ，ｉ−１（ｔ−ｉ＋１）の累乗に対応する（同じく後述する）正規化係数である。式（７）は、その右手側の項の時間パラメータ（すなわち、ｔ−ｉ＋１）がｉ番目の成分
【数１０】
0004398146.tif 000011
の指数ｉに左右されることを示し、したがって、時間パラメータはカルマンゲインベクトルｋＮ（ｔ）の成分によって変化する。
【００５９】
便宜上のために指数を変更すると、時系列ｘ（１）〜ｘ（ｔ）を含むシーケンスにおける信号成分ｘ（ｔ−ｆ）について、最小二乗補間残差はεｐ，ｆ（ｔ−ｆ）となる。指数ｐおよびｆは、時系列におけるｘ（ｔ−ｆ）の前のｐ信号成分およびその後のｆ信号成分が補間において使用されることを示す。この補間残差は、成分ｘ（ｔ−ｆ）自体から、時系列においてそれの前（合計ｐ）および後（合計ｆ）の双方の信号成分から導出される成分の評価補間または予測を引き算することによって導出される。信号成分ｘ（ｔ−ｆ）に対する補間は、その前のｐ個の成分、すなわちｘ（ｔ−ｆ−ｐ）からｘ（ｔ−ｆ−１）までの重み付けされた線形的組合せまたは総和、その後のｆ個の成分、すなわちｘ（ｔ−ｆ＋１）からｘ（ｔ）までの第２のそのような組合せによって与えられる。次に、信号成分ｘ（ｔ−ｆ）に対する最小二乗補間残差は、成分と補間との間の差、すなわち
【数１１】
0004398146.tif 000012
であり、ここで、ベクトル
【数１２】
0004398146.tif 000013
は（ｐ＋ｆ）個の次元を有し、調整可能な係数
【数１３】
0004398146.tif 000014
を含み、総和の項は重み付けされた線形的組合せである。「最小二乗」に対する参照は、これらの係数が、いかなる最小二乗最適化手順によって作成されるものであることを示す。本発明の好ましい実施形態において、これらの係数は決して計算されず、補間残差は、後述する代案となる方法を介して計算される。にもかかわらず、最小二乗最小化手順は、直近の残差によって決定され、これを含む残差の二乗の所定の数Ｌ２の和を最小化する方法で、
【数１４】
0004398146.tif 000015
の係数を決定することを含む。すなわち、
【数１５】
0004398146.tif 000016
は、
【数１６】
0004398146.tif 000017
を最小化するベクトルωの値である。
【００６０】
上記のＬ１およびＬ２は不変のものに選定できるか、または、時間とともに変化することができるため、β２は、上記に検討したβ１のような「忘却係数」である。
【００６１】
式（７）を再び参照すると、既に述べたように、ＥＮ−ｉ，ｉ−１（ｔ−ｉ＋１）は、補間残差信号εＮ−ｉ，ｉ−１（ｔ−ｉ＋１）の累乗に対応する正規化係数である。これは、補間残差自体から計算することができる。帰納的残差と、以下に定義し、直近の時点を含めることによって決定される演繹的残差と呼ばれるものの積の所定の数Ｌ３の和を形成することによるなど、これが行える多くの方法がある。すなわち、
【数１７】
0004398146.tif 000018
である。
【００６２】
項ｅＮ−ｉ，ｉ−１（ｔ−ｉ＋１）は、演繹的最小二乗補間と呼ばれるものであり、使用される重みベクトルがその前の瞬間に計算されたもの、すなわち、
【数１８】
0004398146.tif 000019
であることを除き、帰納的残差（式（８））と同様の方法で計算される。
【００６３】
演繹的残差は、以下のようないわゆる変換係数δｐ，ｆ（ｔ−ｆ）（これの計算は後述する）によって、帰納的等価物に関連付けられる。
【数１９】
0004398146.tif 000020
【００６４】
式（７）〜（１１）は、フィルタ係数を更新するために要求されるゲインベクトル（本例ではカルマンゲインベクトル）が補間残差から生成することができるという本発明による発見を実証する。この点に関して、式（７）は、カルマンゲインベクトルの各成分が、式（１０）によって与えられる正規化係数に対する個々の補間残差の比であることを示し、式（８）および（９）は、正規化係数およびカルマンゲインベクトルの導出のための残差自体をもたらす。
【００６５】
本例において、β１などの全ての忘却係数は等しくされている。この点において、選定された値は、フィルタリングされる信号の性質によって決まる。総和の項の連結された数は、Ｌ１＝Ｌ２＝Ｌ３＝Ｌ４＝Ｌ５＝ｔ＋１などである。すなわち、全ての利用可能な項が含まれ、Ｌ４Ｌ５は以下の式で定義することに注意が必要である。
【００６６】
したがって、本発明による適応フィルタにおいて、ゲインベクトルは、例えば、
【数２０】
0004398146.tif 000021
などによって与えられる補間残差から決定され、ここで、ｘ（ｔ−ｆ）は時系列の（ｔ−ｆ）番目のデータ成分であり、
【数２１】
0004398146.tif 000022
は時系列の前および後の成分の双方から（利用可能性を条件として）補間によって得られるｘ（ｔ−ｆ）の評価を表し、
【数２２】
0004398146.tif 000023
は補間係数ベクトルであり、最小二乗最小化手順で得ることができる。既に述べたように、補間残差は、後述するように
【数２３】
0004398146.tif 000024
を計算することなく得ることができる。量
【数２４】
0004398146.tif 000025
は、ｘ（ｔ−ｆ）の省略を除いて時系列ｘ（ｔ−ｆ−ｐ）〜ｘ（ｔ）のｐ＋ｆ個の成分から構成されるベクトルである。
【００６７】
図１を参照すると、新しい入力信号に応じて適応フィルタのための更新された重みベクトルを計算するための段を概略して示す。これらの段は、初めに簡単に説明し、詳細は後に述べる。箱１０で示すコンピュータは、４つの一般化された処理段１２〜１８を実行することをプログラムされている。段１２から１８のうち、段１２は、ＲＬＳ格子アルゴリズムを使用して入力信号を処理すること、および、前方および後方の最小二乗予測残差を得ることを含む。既に示したように、予測残差は、直接得られたデータ成分と、その成分に関連する他のデータから外挿されたその成分の予測との間の差である。前方予測残差は、直接得られた成分に先行するデータ成分の前方外挿を使用して得られ、後方等価物は、その値に続くデータの後方外挿を使用することによって得られる。前方および後方の予測残差は、当然、高速で数値的に安定な方法でＲＬＳ格子アルゴリズムによって生成される。
【００６８】
段１４において、前方および後方の予測残差は、式（７）の右手側の分子に示される成分を持つ非正規化カルマンゲインベクトルの成分を提供するために適切な補間残差を生成するために使用される。本例において、演繹的補間残差は、式（１２）を使用してそれらを帰納的補間残差に変換するための変換係数とともに計算される。この手法は、記憶されている様々なパラメータの初期化を、帰納的残差が使用される場合より容易にすると理解される。
【００６９】
段１６において、正規化されたカルマンゲインベクトルを作成するために、各帰納的補間残差は、正規化係数ＥＮ−ｉ，ｉ−１（ｔ−ｉ＋１）による除算によって正規化される。この係数は積の重み付けされた総和として計算され、各積は個々の時点に対する演繹的と帰納的補間残差との間のものであり、総和は、式（１０）におけるように信号サンプルが直近の時点を含め、それまでに得られた全ての時点に対するそのような積に対するものである。
【００７０】
段１８において、式（３）および（４）に示すように、ｘ（ｔ）を含めてそれまでの入力信号成分から導出されるカルマンゲインベクトルは、ｘ（ｔ）自身および参照信号ｙ（ｔ）と組み合わされる。これは、したがって、入力および参照信号の成分ｘ（ｔ）およびｙ（ｔ）の双方に応じて修正された、更新されたフィルタ係数または重みを作成する。段１２〜１６においてカルマンゲインベクトルの導出における処理遅延を許容し、段１８への入力で同時に達成するために、信号成分ｘ（ｔ）およびｙ（ｔ）が記憶され、または、リアルタイムシステムにおいて必要であれば、遅延される。
【００７１】
ＲＬＳ格子アルゴリズムは以下のように段１２において実施される。最小二乗（ＬＳ）格子アルゴリズムは、時系列などの信号のシーケンスの最小二乗前方および後方予測残差を計算するための効率的なアルゴリズムである。時系列は、時間の関数としての信号ｘ（ｔ）の変化を表す一連のデータ値である。
【００７２】
Ｎ次目の適応フィルタは、Ｎ個の係数、すなわち、フィルタ係数を有する重みベクトルｗＮに対応する。線形予測残差は、これらの係数を得る際の第１のステップとして作成され、次数１〜Ｎ−１を有する。残差は帰納的でも演繹的でもよく、すなわち、それらは、直近に決定された重みベクトルまたはその直前に決定されたベクトルのいずれかを使用して作成することができる。時間ｔにおける値ｘ（ｔ）を備えた信号の時系列に対するｎ次目の帰納的ＬＳ前方予測残差
【数２５】
0004398146.tif 000026
は、
【数２６】
0004398146.tif 000027
として定義され、ここで、ｘｎ（ｔ−１）は成分ｘ（ｔ−１）〜ｘ（ｔ−ｎ）を有するデータベクトルであり、ａｎ（ｔ）は後述する最小二乗最適化手順で再び決定される前方予測係数ベクトルであり、このベクトルは、直近の残差を含めてそれまでで決定された残差の二乗の所定の数（Ｌ４）の重み付けされた和
【数２７】
0004398146.tif 000028
を最小化する方法で決定される。すなわち、ａｎ（ｔ）は、
【数２８】
0004398146.tif 000029
を最小化するベクトルωの値であり、ここで、β４は既に説明した忘却係数である。
【００７３】
同様に、時間ｔにおける値ｘ（ｔ）を備えた信号の時系列に対するｎ次目の帰納的ＬＳ後方予測残差
【数２９】
0004398146.tif 000030
は、
【数３０】
0004398146.tif 000031
として定義され、ここで、ｃｎ（ｔ）は直近の残差を含めてそれまでで決定された残差の二乗の数Ｌ５の重み付けされた和を最小化する最小二乗最適化手順によって前述のように決定される後方予測に対する係数ベクトルである。すなわち、ｃｎ（ｔ）は、
【数３１】
0004398146.tif 000032
を最小化するベクトルωの値であり、ここで、β５は忘却係数である。
【００７４】
対応する演繹的前方および後方ＬＳ予測残差
【数３２】
0004398146.tif 000033
および
【数３３】
0004398146.tif 000034
は、それぞれ同じように以下のように定義される。
【数３４】
0004398146.tif 000035
【００７５】
前方および後方演繹的残差をそれぞれの帰納的等価物に関連付ける変換係数
【数３５】
0004398146.tif 000036
および
【数３６】
0004398146.tif 000037
は、
【数３７】
0004398146.tif 000038
として定義される。
【００７６】
Ｎ次目の最小二乗格子（ＬＳＬ）アルゴリズムは、前方および後方帰納的予測残差の集合を生成し、各々のＮは、すなわち、
【数３８】
0004398146.tif 000039
である。ここで、Ｎは一般的な意味で使用され、本明細書で他に使用されるＮと必ずしも同じ値ではない。本例において使用される特定のＬＳＬアルゴリズムは、平方根自由ＱＲ分解を基本とした再帰性最小二乗格子（ＲＬＳＬ）アルゴリズムである。これは、内部的には、帰納的予測残差を直接計算しないが、代わりに、演繹的予測残差および対応する変換係数を計算する。アルゴリズムは、ＭｃＷｈｉｒｔｅｒの米国特許第４，７２７，５０３号明細書に述べられる再帰性平方根自由ＱＲ分解に関連付けられる。同特許は、中でもＧｉｖｅｎｓ回転の平方根自由等価物を使用してこの関数を実行する収縮性アレーについての境界および内部セル関数について説明している。ＩＫ  Ｐｒｏｕｄｌｅｒ、ＪＧ  ＭｃＷｈｉｒｔｅｒおよびＴＪ  Ｓｈｅｐｈｅｒｄによる「Ｃｏｍｐｕｔａｔｉｏｎａｌｌｙ  Ｅｆｆｉｃｉｅｎｔ，ＱＲ  Ｄｅｃｏｍｐｏｓｉｔｉｏｎ  Ａｐｐｒｏａｃｈ  ｔｏ  Ｌｅａｓｔ  Ｓｑｕａｒｅｓ  Ａｄａｐｔｉｖｅ  Ｆｉｌｔｅｒｉｎｇ：最小二乗適応フィルタリングに対する計算上効率的なＱＲ分解手法」ＩＥＥ  Ｐｒｏｃｅｅｄｉｎｇｓ、第１３８巻、Ｐｔ．Ｆ、ｎｏ．４、１９９１年８月の３４１〜３５３頁も同じく参照のこと。
【００７７】
ＱＲ分解は、データ行列Ｘを、座標系の回転によって右上三角行列Ｒ（すなわち、対角線より下の全ての成分がゼロ）に変換する回転パラメータの行列Ｑを決定することによって、線形方程式の集合を解く際に使用されるよく知られている手順である。このようなＲ行列は、単一の未知数を備えた１つの方程式に対応し、各方程式が逆代入によって解かれることを可能にする最後の行を有する。回転パラメータは、正弦および余弦、または、それらの平方根自由等価物である。
【００７８】
図２は、ＲＬＳＬアルゴリズムの最初の４つの連続したステップを説明する図であり、それらは連結された段である。ｉ番目の段（ｉ＝１、２、３または４）は、２つの内部セル（二乗）ＩａｉおよびＩｂｉ、２つの境界セルＢａｉおよびＢｂｉ、および、２つの遅延セルＤａｉおよびＤｂｉを含む。「内部セル」および「境界セル」という表現はＱＲ処理において従来からのものであり、本来、三角アレーにおいて対角線上のセルから対角線より上方のセルを区別していたものである。これらは、現在、回転パラメータを評価するセルから回転パラメータを適用するセルを区別するために使用されている。
【００７９】
米国特許第４，７２７，５０３号明細書に説明されているように、境界セルは、入力データからの回転パラメータを評価し、余弦状回転パラメータを累積的に増倍する。内部セルは、入力データに回転パラメータを適用する。これらのセルの各々も、各入力に応じて再計算し、量を記憶し、それらの処理関数は、後で詳細に説明する。各遅延セルＤａｉおよびＤｂｉは単一の時間間隔にわたって入力信号を記憶し、直前の入力信号を出力する。例えば、Ｄａ１がデータ成分ｘ（ｔ）などの新しい入力信号を受け取った時、それは先行する入力信号ｘ（ｔ−１）を出力し、次の入力信号ｘ（ｔ＋１）が受け取られるまで新しい信号を記憶する。ｉ番目の段は、ｉ＝１の時は入力信号ｘ（ｔ）を使用して、および、ｉが２以上の時は段ｉ−１からの出力に対応する残差を使用して、次数ｉの前方および後方の双方の予測残差を提供する。
【００８０】
時点ｔにおいて、データ成分ｘ（ｔ）はＲＬＳＬアルゴリズムの第１段に入力される。これは、第１の内部セルＩａ１、第１の遅延セルＤａ１および第２の境界セルＢｂ１に渡す。第１の遅延セルＤａ１はｘ（ｔ−１）を第２の内部セルＩｂ１および第１の境界セルＢａ１に出力する。第１の境界セルＢａｉおよび第２の境界セルＢｂｉも１の入力を受け取り、第２の境界セルＢｂｉは第２の遅延セルＤｂ１からである（必要ではないが、各段間の整合性のために含まれる）。したがって、演算のシーケンスは左から右に向かう。
【００８１】
第１のＲＬＳＬアルゴリズム段のセルは、量を生成し、それらを以下のように渡す。
【００８２】
第１の境界セルＢａ１：内部に記憶された量を更新するためにｘ（ｔ−１）を使用し、記憶された量から平方根自由回転パラメータを計算し、それらを第１の内部セルＩａ１に送る。また、（演繹的および帰納的前方予測残差に関するｎ＝１で式（２０）で定義した）変換係数
【数３９】
0004398146.tif 000040
を計算し、それを、入力として第２段の第１の境界セルＢａ２へ渡す。
【００８３】
第２の境界セルＢｂ１：記憶された量を更新するためにｘ（ｔ）を使用し、記憶された量から平方根自由回転パラメータを計算し、それらを第２の内部セルＩｂ１に渡す。また、演繹的および帰納的後方予測残差に関する変換係数
【数４０】
0004398146.tif 000041
を計算し、それを入力として第２段の第２の遅延セルＤｂ２へ渡し、この第２の遅延セルは、第２段の第２の境界セルＢｂ２へ（既に受け取っている）
【数４１】
0004398146.tif 000042
を出力することで応答する。
【００８４】
第１の内部セルＩａ１：記憶された量を更新するためにｘ（ｔ）を使用する。続いて、演繹的前方予測残差
【数４２】
0004398146.tif 000043
を計算し（すなわち、式（１８）においてｎ＝１）、それを、第２段の第１の内部および第２の境界セルＩａ２およびＢｂ２へ渡す。
【００８５】
第２の内部セルＩｂ１：記憶された量を更新するためにｘ（ｔ−１）を使用する。続いて、演繹的後方予測残差
【数４３】
0004398146.tif 000044
を計算し（すなわち、式（１９）においてｎ＝１）、それを、第２段の第１の遅延セルＤａ２へ通過させ、このセルは、第２段の第２の内部セルＩｂ２および第１の境界セルＢａ２へ（既に受け取っている）
【数４４】
0004398146.tif 000045
を出力することで応答する。
【００８６】
値
【数４５】
0004398146.tif 000046
および
【数４６】
0004398146.tif 000047
は評価され、第１段によってこのように伝達され、第１次（ｎ＝１）前方および後方線形予測の問題を解決する。第２段は第２次（ｎ＝２）のこれの等価物を解決する。すなわち、第２段の内部および境界セルＩａ２、Ｂａ２、Ｉｂ２、および、Ｂｂ２は第１段の結果に等価な結果を計算するが、肩文字指数が２である。すなわち、
【数４７】
0004398146.tif 000048
である。同様に、第３および第４段は、指数ｎ＝３およびｎ＝４の第３次および第４次の等価物を続いて計算する。Ｎ次目の予測残差はＮ個の段を要求し、そのうちの４つを図２に示す。
【００８７】
既に述べたように、上述のように生成された項
【数４８】
0004398146.tif 000049
および
【数４９】
0004398146.tif 000050
は、演繹的予測残差である。これらは、同じくＲＬＳＬアルゴリズムによって生成された項
【数５０】
0004398146.tif 000051
および
【数５１】
0004398146.tif 000052
を使用し、上記の式（２０）および（２１）に以下のように代入して、
【数５２】
0004398146.tif 000053
帰納的残差
【数５３】
0004398146.tif 000054
および
【数５４】
0004398146.tif 000055
に変換することができる。
【００８８】
式（２２）および（２３）を使用して帰納的予測残差が計算されたなら、それらは、以下に説明するように、非正規化カルマンゲインベクトルを構成する補間残差を計算するために使用することができ、このベクトルは、式（７）の右手側の分子である。しかし、演繹的な形で補間残差を、対応する変換係数とともに計算することは、上述したように初期化の目的のために有利である。そのため、本例において、式（２２）および（２３）は実施されない。
【００８９】
図３および４は、ｅｐ，ｆ（ｔ−ｆ）（および、対応する変換係数）などの演繹的補間残差が、他の２つの補間残差を生成するために、特定の予測残差とともに、どのように使用できるかを示す。本来の補間残差の指数および時点を基準として、それから作成された２つの残差の１つは、１だけ増加したｐ指数を有し、他の１つは同様に増加したｆ指数および１サンプル間隔前の時点、すなわち、ｅｐ＋１，ｆ（ｔ−ｆ）およびｅｐ，ｆ＋１（ｔ−ｆ−１）を有する。
【００９０】
図３において、演繹的補間残差ｅｐ，ｆ（ｔ−ｆ）およびその関連する変換係数δｐ，ｆ（ｔ−ｆ）は、演繹的補間残差ｅｐ＋１，ｆ（ｔ−ｆ）およびその関連する変換係数δｐ＋１，ｆ（ｔ−ｆ）に変換される。この処理は、２つの内部セル（二乗）Ｉ１およびＩ２、および、２つの境界セルＢ１およびＢ２に関わる。境界セルは回転パラメータを評価し、Ｂ２の場合、余弦状の回転パラメータを累積的に増倍する。内部セルは回転パラメータをデータに適用する。これらのセルの各々も、各入力に応じて量を再計算し、記憶する。それらのセルの処理関数は、次に詳細に説明する。
【００９１】
境界セルＢ１：演繹的補間残差ｅｐ，ｆ（ｔ−ｆ）および変換係数δｐ，ｆ（ｔ−ｆ）を、内部に記憶された量を更新するために使用し、記憶された量から平方根自由回転パラメータを計算し、それらを第１の内部セルＩ１に渡す。演繹的と帰納的残差に関連する変換係数δｐ，ｆ（ｔ−ｆ）を入力において境界セルＢ２へ渡す。
【００９２】
内部セルＩ１：演繹的後方予測残差
【数５５】
0004398146.tif 000056
および境界セルＢ１からの回転パラメータを、記憶された量を更新するために使用する。続いて、量
【数５６】
0004398146.tif 000057
を計算し、それを境界セルＢ２に渡す。
境界セルＢ２：
【数５７】
0004398146.tif 000058
および変換係数δｐ，ｆ（ｔ−ｆ）を、記憶された量を更新するために使用し、記憶された量から平方根自由回転パラメータを計算し、それらを内部セルＩ２に渡す。演繹的と帰納的残差に関連する変換係数δｐ＋１，ｆ（ｔ−ｆ）を計算する。
【００９３】
内部セルＩ２：
【数５８】
0004398146.tif 000059
および境界セルＢ２からの回転パラメータを、記憶された量を更新するために使用する。続いて、演繹的補間残差ｅｐ＋１，ｆ（ｔ−ｆ）を計算する。
【００９４】
図４において、演繹的補間残差ｅｐ，ｆ（ｔ−ｆ）およびその関連する変換係数δｐ，ｆ（ｔ−ｆ）は、演繹的補間残差ｅｐ，ｆ＋１（ｔ−ｆ−１）およびその関連する変換係数δｐ，ｆ＋１（ｔ−ｆ−１）に変換される。２つの遅延セル（Ｄ１およびＤ２）を除いて、基礎となる演算は図３に関して説明したものと全く同じである。図３および４を参照して説明した手法を区別するものは、異なった入力信号の使用である。
【００９５】
図４において、処理は、２つの遅延セルＤ１およびＤ２、２つの内部セル（二乗）Ｉ３およびＩ４、および、２つの境界セルＢ３およびＢ４に関わる。遅延セルＤ１およびＤ２の各々は単一の時間間隔にわたって１つの入力信号を記憶する。新しい入力信号ｈ（ｔ）を受け取った時、それは、先行する入力信号ｈ（ｔ−１）を出力し、次の入力信号ｈ（ｔ＋１）を受け取るまで新しいものを記憶する。境界セルＢ３およびＢ４は回転パラメータを評価し、Ｂ４の場合、余弦状回転パラメータを累積的に増倍する。内部セルはデータに回転パラメータを適用する。これらのセルの各々も、各入力に応じて量を再計算し、記憶する。それらの処理関数は次に詳細に説明する。
【００９６】
境界セルＢ３：演繹的補間残差ｅｐ，ｆ（ｔ−ｆ−１）、遅延セルＤ２からの出力、および、変換係数δｐ，ｆ（ｔ−ｆ−１）を、内部に記憶された量を更新するために使用し、記憶された量から平方根自由回転パラメータを計算し、それらを第１の内部セルＩ１に渡す。演繹的と帰納的残差に関連する遅延セルＤ１からの出力である変換係数δｐ，ｆ（ｔ−ｆ−１）を入力において境界セルＢ４へ渡す。
【００９７】
内部セルＩ３：演繹的前方予測残差
【数５９】
0004398146.tif 000060
および境界セルＢ３からの回転パラメータを、記憶された量を更新するために使用する。続いて、量
【数６０】
0004398146.tif 000061
を計算し、それを境界セルＢ４に渡す。
【００９８】
境界セルＢ４：
【数６１】
0004398146.tif 000062
および変換係数δｐ，ｆ（ｔ−ｆ−１）を、記憶された量を更新するために使用し、記憶された量から平方根自由回転パラメータを計算し、それらを内部セルＩ２に渡す。演繹的と帰納的残差に関連する変換係数δｐ，ｆ＋１（ｔ−ｆ−１）を計算する。
【００９９】
内部セルＩ４：ｅｐ，ｆ（ｔ−ｆ−１）および境界セルＢ４からの回転パラメータを、記憶された量を更新するために使用する。続いて、演繹的補間残差ｅｐ，ｆ＋１（ｔ−ｆ−１）を計算する。
【０１００】
図３および４のセルの関数の詳細を以下に説明する。ＩＥＥＥ  Ｔｒａｎｓ  ＳＰ、２０００年１月、第４８（１）巻、７０〜７９頁の「ＱＲ  ｄｅｃｏｍｐｏｓｉｔｉｏｎ  ｂａｓｅｄ  ｌｅａｓｔ  ｓｑｕａｒｅｓ  ｌａｔｔｉｃｅ  ｉｎｔｅｒｐｏｌａｔｏｒｓ：ＱＲ分解に基づく最小二乗格子補間器」でＪＴ  Ｙｕａｎは、以下の式（２４）および（２５）に詳述されるように帰納的補間残差εｐ＋１，ｆ（ｔ−ｆ）およびεｐ，ｆ＋１（ｔ−ｆ−１）を生成するために、帰納的補間残差εｐ，ｆ（ｔ−ｆ）、または、１ステップ遅延された等価物εｐ，ｆ（ｔ−ｆ−１）を使用することが可能であることを示す。
【数６２】
0004398146.tif 000063
【０１０１】
ここで、ｋｐ＋１，ｆ（ｔ）およびμｐ，ｆ＋１（ｔ）は最小二乗最小化手順によって決定される係数である。すなわち、ｋｐ＋１，ｆ（ｔ）およびμｐ，ｆ＋１（ｔ）は、（それぞれ）異なった時間ｔにおける評価の連続にわたって項
【数６３】
0004398146.tif 000064
および
【数６４】
0004398146.tif 000065
の値の二乗の重み付けされた和を最小化する係数ω１およびω２の値に（それぞれ）等しく設定される。量
【数６５】
0004398146.tif 000066
および
【数６６】
0004398146.tif 000067
は、後述するように、他の知られている量から計算される。ここで、各場合のεの上の折り曲った記号は、量
【数６７】
0004398146.tif 000068
および
【数６８】
0004398146.tif 000069
が、それぞれ、式（１６）および（１４）によって与えられる後方および前方線形予測残差とは同じでないことを示す。
【０１０２】
【数６９】
0004398146.tif 000070
は、データ成分ｘ（ｔ−ｆ）を省略して導出された時間（ｔ）における次数（ｐ＋ｆ）の後方予測残差であり、
【数７０】
0004398146.tif 000071
は、データ成分ｘ（ｔ−ｆ−１）を省略して導出された時間（ｔ）における次数（ｐ＋ｆ）の前方予測残差である。
【０１０３】
厳密に言えば、パラメータが余分であることは数学的に示すことができるが、上記の解析において、時間指数（ｔ−ｆ）は便宜上のために使用されている。
【０１０４】
最小二乗最小化の問題を解決するために、いくつかのよく知られている方法がある。この例においては、ＱＲ分解（ＱＲＤ）に基づくそのような方法が採用されている。以下に、一般化された式における係数ｋ（ｔ）を決定することに関して説明する。
【０１０５】
式（２４）および（２５）の各々は、
【数７１】
0004398146.tif 000072
の形のものである。
【０１０６】
式（２６）において、入力データξ（ｔ）およびΨ（ｔ）（それぞれ、帰納的に修正された予測および補間残差）が与えられた場合、係数ｋ（ｔ）を、計算において、特定の異なった時間ｉの間に対して計算され、忘却係数βによって重み付けされた量Ψ（ｉ）＋ωξ（ｉ）の二乗の和の最小化があるという制限を条件として、時点ｔにおいて計算することが要求される。すなわち、ｋ（ｔ）は、以下の表記に対する最小値を与えるパラメータωの値に等しい。
【数７２】
0004398146.tif 000073
【０１０７】
パラメータＬは、総和に含まれる過去のサンプルの数を決定する。既に述べたように、Ｌは固定しても、または、時間とともに変化してもよく、βは忘却係数である。この方法でｋ（ｔ）を計算する効果は、同じくΨ（ｔ）に現われるξ（ｔ）のいかなる成分も減衰させることである。項ξ（ｔ）は、この問題に対する帰納的最小二乗残差である。
【０１０８】
本例において、式（２６）および（２７）に与えられた最小二乗の問題を解決するための好ましい方法は、帰納的残差ξ（ｔ）およびΨ（ｔ）ではなく、変換係数δｉｎ（ｔ）が適用される対応するそれぞれの演繹的残差ｕ（ｔ）およびｖ（ｔ）を含む。各残差について異なった変換係数があることが推測されるが、事実、本例において、それらは同じであることが見出されている。加えて、好ましい方法は、式（２６）および（２７）に与えられた最小二乗の問題を直接解決しないが、代わりに、現時点のみにおける演繹的残差ｕ（ｔ）およびｖ（ｔ）および変換係数δｉｎ（ｔ）、および、前の時点に計算され、後の使用のために記憶される様々なパラメータの値の知識に基づいてｋ（ｔ）を計算する再帰性手順を使用する。１つのそのような記憶されたパラメータは、前の時点における最小二乗係数の値、すなわち、ｋ（ｔ−１）である。
【０１０９】
「Ａ  Ｎｏｔｅ  ｏｎ  Ｍｏｄｉｆｉｃａｔｉｏｎｓ  ｔｏ  ｔｈｅ  Ｇｉｖｅｎｓ  Ｐｌａｎｅ  Ｒｏｔａｔｉｏｎ：ギブンスの平面回転に対する修正に関するメモ」、Ｊ．Ｉｎｓｔ．Ｍａｔｈｓ．Ａｐｐｌｉｃｓ．、第１３巻２１５〜２１８頁、１９７４年のＳ  Ｈａｍｍａｒｌｉｎｇの解析に関して、およびＭｃＷｈｉｒｔｅｒの米国特許第４，７２７，５０３号明細書に説明されている解析によって、ｋ（ｔ）が以下の帰納法から計算できることを示すことができる。この帰納法は、ζ（ｔ）（すなわち、ｚ（ｔ））に関連する演繹的残差および対応する変換係数（δｏｕｔ（ｔ））ももたらす。
【数７３】
0004398146.tif 000074
【０１１０】
項ｄ（ｔ）は式（２８）によって定義され、時系列ｕ（０）〜ｕ（ｔ）のエネルギの評価を表すが、より最近のサンプルにはより多くの重みが与えられている。式（２８）の右手側の全ての項は、時間ｔにおいて知られている。項ｄ（ｔ−１）は、もしｔ＝２以上であれば計算によって直前に先行する時点において得られた。ｔ＝１については、対応する初期項ｄ（０）にゼロなどの所定の値が与えられる。項δｉｎ（ｔ）およびｕ（ｔ）は入力データである。項ｓはＱＲ分解において使用される種類の一般化された回転パラメータである。これは、式（２８）を使用して関連する時点について計算される量ｄ（ｔ）とともに、入力データδｉｎ（ｔ）およびｕ（ｔ）に関して式（２９）によって定義される。式（３０）は知られている量に関する残差ｚ（ｔ）に対する変換係数δｏｕｔ（ｔ）を定義する。すなわち、ｄ（ｔ−１）は前の時点から知られ、δｉｎ（ｔ）およびｄ（ｔ）は式（２８）を使用してこの時点について計算されている。式（２８）〜（３０）はともに、図２に示す境界セルＢａ１などおよび図３および４に示す境界セルＢ２およびＢ４において各時点について行われる計算を表す。
【０１１１】
式（３１）および（３２）は、図２における内部セルＩａ１などおよび図３および４に示す内部セルＩ２およびＩ４において各時点について行われる計算を表す。式（３１）は、２つの知られている量（入力データ）ｕ（ｔ）およびｖ（ｔ）、および、ｔ＝２以上の場合の時点（ｔ−１）のデータについて既に評価された値ｋ（ｔ−１）に関するｚ（ｔ）を表す。ｔ＝１は、ゼロなどの所定の値に等しく設定される項ｋ（０）に対応する。式（３２）は、量ｓおよび前の時点からのｋ（ｔ−１）とともに、式（２９）および（３１）から計算されるｚ（ｔ）に関するｋ（ｔ）を表す。したがって、いかなる開始値、例えば、ｋ（０）の知識により、式（２８）および（３２）を使用してｚ（ｔ）およびｋ（ｔ）の次に続く一連の値を生成することが可能である。
【０１１２】
式（２４）および（２５）を再び参照すると、量
【数７４】
0004398146.tif 000075
および
【数７５】
0004398146.tif 000076
は前述の計算において要求され、事実、それらは以下により他の知られている量から得られる。
【数７６】
0004398146.tif 000077
【０１１３】
ここで、ηｐ＋１，ｆ（ｔ）およびｖｐ，ｆ＋１（ｔ）は以下に説明する修正された最小二乗最小化手順によって決定される係数である。この手順は再帰性最小二乗最小化を含み、式（３３）および（３４）における２つの最小二乗の問題は同じ形である。すなわち、
【数７７】
0004398146.tif 000078
【０１１４】
ここで、ζ（ｔ）およびξ（ｔ）は知られている入力データ（それぞれ帰納的予測および補間残差）であり、ｋ（ｔ）およびΨ（ｔ）は計算される。これは、式（２６）および（２７）に関連する手順に比較すれば修正された手順であるが、この再帰性最小二乗手順が、式（２６）および（２７）によって説明され、帰納法の式（２８）〜（３２）によって実施される従来の最小二乗の問題を解決することによって得られる係数ｋ（ｔ）に対するのと、同じ値を計算することを示すことができる。式（２８）〜（３２）は入力データとしてΨ（ｔ）およびξ（ｔ）を有し、ｋ（ｔ）およびζ（ｔ）をもたらしたが、今度の場合では、Ψ（ｔ）が利用可能ではない。しかし、ｋ（ｔ−１）およびζ（ｔ）が知られていれば、Ψ（ｔ）の知識なしにｋ（ｔ）を導出できることを示すことができる。これは、対応する演繹的残差および関連する変換係数に関して以下に説明する。演繹的残差（ローマ字記号）ｚ（ｔ）、ｕ（ｔ）、および、ｖ（ｔ）は、帰納的残差（ギリシャ文字記号）ζ（ｔ）、ξ（ｔ）、および、Ψ）（ｔ）にそれぞれ対応する。
【０１１５】
式（２８）〜（３２）は、ｋ（ｔ）がｖ（ｔ）の知識を使用してｋ（ｔ−１）から導出できることを示す。さらに、帰納法は副産物としてｚ（ｔ）を生み出す。前述した修正再帰性最小二乗手順を実施する目的のために、これらの式が、もしこの場合に該当する、ｚ（ｔ）が知られている場合に、ｖ（ｔ）の知識なしにｋ（ｔ−１）からｋ（ｔ）についての値を導出することが可能であるような方法で再配置できることを示すことができる。さらに、そのように再配置されたこれらの式は、副産物としてｖ（ｔ）を生み出し、以下の式（３６）〜（４０）において詳述される。
【数７８】
0004398146.tif 000079
【０１１６】
式（３６）〜（４０）が、帰納的残差（ギリシャ文字記号）ζ（ｔ）、ξ（ｔ）、および、Ψ）（ｔ）にそれぞれ対応する演繹的残差（ローマ字記号）ｚ（ｔ）、ｕ（ｔ）、および、ｖ（ｔ）に関することを繰り返して述べる。
【０１１７】
項ｄ（ｔ）は式（３６）によって定義され、時系列ｕ（０）〜ｕ（ｔ）のエネルギの評価を表すが、より最近のサンプルにより重みが与えられている。式（３６）の右手側の全ての項は、時間ｔにおいて知られている。ｔ＝２以上について、項ｄ（ｔ−１）は、その前の時点から知られる。ｔ＝１およびｄ（０）の場合、ｄ（０）はゼロなどの所定の値に設定される。項δｉｎ（ｔ）およびｕ（ｔ）は入力データである。項ｓは一般化された回転パラメータである。これは、入力データδｉｎ（ｔ）およびｕ（ｔ）、および、式（３６）を使用して計算されるｄ（ｔ）に関して式（３７）によって定義される。式（３８）は、知られている入力変換係数δｉｎ（ｔ）に等しいとして残差ｖ（ｔ）に対して変換係数δｏｕｔ（ｔ）を定義する。式（３６）〜（３８）はともに、境界セルＢ１およびＢ２において実行され、図３および４を参照して説明される計算を表す。
【０１１８】
式（３９）および（４０）は、図３および４に示す内部セルＩ１およびＩ３において実行される計算を表す。式（３９）は、知られている量、すなわち、時間（ｔ−１）のデータについて既に評価された値ｋ（ｔ−１）、または、ｋ（０）の場合、ゼロなどの所定の値に設定された値とともに入力データｕ（ｔ）およびｚ（ｔ）、に関するｖ（ｔ）を表す。式（４０）は、式（３７）を使用して計算される量ｓ、および、その前の時点からのｋ（ｔ−１）とともに入力データｚ（ｔ）に関するｋ（ｔ）を表す。したがって、任意の開始値、例えば、ｋ（０）の知識により、式（３６）〜（４０）を使用して、その後の時点についてｖ（ｔ）およびｋ（ｔ）のその後の一連の値を生成することは可能である。
【０１１９】
式（２４）以降は、εｐ，ｆ（ｔ−ｆ）（または、等価的に、演繹的補間残差ｅｐ，ｆ（ｔ−ｆ）および対応する変換係数δｐ，ｆ（ｔ−ｆ））または１サンプル時間間隔遅延した等価残差ｅｐ，ｆ（ｔ−ｆ−１）などの帰納的補間残差が、特定の予測残差とともに、他の２つの補間残差を生成するために使用できることを示す。本来の補間残差の指数を基準として、それから生成された２つの残差の１つは、１だけ増加したｐ指数を有し、他の１つは同様に増加したｆ指数を有する。すなわち、εｐ＋１，ｆ（ｔ−ｆ）およびεｐ，ｆ＋１（ｔ−ｆ−１）である。これは、演繹的補間残差および対応する変換係数に関して図３および４に示す。
【０１２０】
便宜上のため、ベクトル
【数７９】
0004398146.tif 000080
は次数Ｎの非正規化カルマンゲインベクトルであると定義される。すなわち、
【数８０】
0004398146.tif 000081
のｉ番目の成分は、
【数８１】
0004398146.tif 000082
である。式（７）を参照。Ｎ次目の適応フィルタに対する非正規化カルマンゲインベクトル
【数８２】
0004398146.tif 000083
の成分
【数８３】
0004398146.tif 000084
である補間残差を生成するために、図３および４を参照して説明される方法を使用する多くの可能な方法がある。
【０１２１】
説明の簡略化のため、以下の検討は、帰納的残差の面からのものであるのに対して、本例においては、等価的に、演繹的残差および変換係数が実際に使用されている。補間残差εｐ，０（ｔ）およびε０，ｆ（ｔ−ｆ）は特別な特性を有する。補間残差εＮ−ｉ，０（ｔ）は、ｐ＝Ｎ−ｉおよびｆ＝０を有する。ｆ＝０は、時系列に後続の項がないことに対応する。したがって、この残差は先行する項のみから、すなわち、時系列の同じ項から、および、前方予測残差
【数８４】
0004398146.tif 000085
と同じ方法で計算される。式（１４）を参照。したがって、これらの２つの残差は等しい。さらに、前方予測残差が最小二乗格子プロセッサを使用して得られるため、補間残差εＮ−ｉ，０（ｔ）も同様に得られる。
【０１２２】
既に述べたように、図３および４を参照して説明された方法が、非正規化カルマンゲインベクトル
【数８５】
0004398146.tif 000086
の成分を生成するために利用することができる多くの方法がある。例えば、上述の原理に従えば、補間残差εＮ−ｉ，０（ｔ）は、１だけ増加したｆ指数を備え、直前または（ｔ−１）番目の時間サンプル、すなわち、εＮ−ｉ，１（ｔ−１）に対応する他の補間残差を生成するために使用できる。この手順は、εＮ−ｉ，１（ｔ−１）からεＮ−ｉ，２（ｔ−２）を作成するために繰り返される。反復はεＮ−ｉ，ｉ−１（ｔ−ｉ＋１）が生成されるまで合計（ｉ−１）回繰り返される。すなわち、反復段は、
【数８６】
0004398146.tif 000087
である。
【０１２３】
εＮ−ｉ，ｉ−１（ｔ−ｉ＋１）を生成するための代案となる方法は、以下のとおりである。補間残差ε０，ｉ−１（ｔ−ｉ＋１）（すなわち、ｐ＝０、ｆ＝ｉ−１）は、時間ｔに対する（ｉ−１）番目の後方予測残差と同じである。すなわち、
【数８７】
0004398146.tif 000088
である。式（１６）を参照。上述の原理に従えば、補間残差ε０，ｉ−１（ｔ−ｉ＋１）は、１だけ増加したｐ指数を備えたε１，ｉ−１（ｔ−ｉ＋１）を生成するために使用される。この手順は、ε１，ｉ−１（ｔ−ｉ＋１）からε２，ｉ−１（ｔ−ｉ＋１）を作成するまで反復される。反復は、εＮ−ｉ，ｉ−１（ｔ−ｉ＋１）が生成されるまで合計（Ｎ−ｉ）回繰り返される。すなわち、
【数８８】
0004398146.tif 000089
である。
【０１２４】
項εＮ−ｉ，ｉ−１（ｔ−ｉ＋１）は非正規化カルマンゲインベクトル
【数８９】
0004398146.tif 000090
のｉ番目の成分である。
【０１２５】
上記の反復（４１）および（４２）が示す２つの方法は、非正規化カルマンゲインベクトルを構成する要求される補間残差の全てを生成するために、Ｎ２（Ｏ（Ｎ２））の次数のコンピュータ処理を要求する。ここで、Ｎは適応フィルタの次数である。計算の数をＯ（Ｎｌｏｇ２Ｎ）に削減するための代案となる手順を説明する。
【０１２６】
説明の便宜のため、Ｎ＝２ｘであることを仮定し、ここで、Ｎはフィルタの次数であり、ｘは正の整数である。反復（４１）および（４２）に関して説明したように、εＭ，Ｍ−１（ｔ−Ｍ＋１）（Ｍ＝Ｎ／２）などの種類εｐ，ｆ（ｔ−ｆ）の補間残差は、補間残差εＭ，０（ｔ）から開始される反復によって計算することができる。すなわち、εＭ，０（ｔ）がｐ＝Ｍおよびｆ＝０を有するので、これは０（後続しない）の後続する時系列データ成分を除くＭ先行成分から導出される。したがって、これは、同じ計算によって同じデータ成分から得られる帰納的前方予測残差
【数９０】
0004398146.tif 000091
と同一である。その結果、εＭ，Ｍ−１（ｔ−Ｍ＋１）は、既に説明したように最小二乗格子プロセッサから得られる
【数９１】
0004398146.tif 000092
自体から、式（４１）に示すタイプの反復によって得られる。さらに、本反復の処理において、０〜Ｍ−１のｆの値を持つ残差ｅＭ，ｆ（ｔ−ｆ）が計算される。すなわち、ｆ＝１〜Ｍ−２であり、すなわち、
【数９２】
0004398146.tif 000093
である。
【０１２７】
（４３）における補間残差も、（２≦ｉ≦Ｍ−１）とした残差εＮ−ｉ，ｉ−１（ｔ−ｉ＋１）を計算するために式（４２）に示す反復を使用して計算される中間量である。このため、もし式（４３）における中間量が後の再使用のために記憶されれば、非正規化カルマンゲインベクトルを構成する他の残差を計算する際に含まれるコンピュータ処理のいくらかは回避することが可能である。
【０１２８】
同様に、補間残差εＭ−１，Ｍ（ｔ−Ｍ）は、それ自体が帰納的後方予測残差
【数９３】
0004398146.tif 000094
と同一であるε０，Ｍ（ｔ−Ｍ）から式（４２）に示す反復によって得られる。この反復は、１〜Ｍ−２のｐの値を持つ中間量εｐ，Ｍ（ｔ−Ｍ）も生成する。
【０１２９】
同様の節約は、他の項、すなわち、反復（４１）を介して（Ｍ＋２≦ｉ≦Ｎ−１）によって与えられるｉの値を持つεＮ−ｉ，ｉ−１（ｔ−ｉ＋１）の計算についても可能である。
【０１３０】
中間量を記憶する一方で、εＮ−３Ｐ，Ｍ（ｔ−Ｍ）（ここでＰ＝Ｎ／４）からεＮ−３Ｐ，３Ｐ−１（ｔ−３Ｐ＋１）を計算することは、式（４２）を介して計算される（Ｍ＋２≦ｉ≦３Ｐ−１）によって与えられるｉの値を持つ残差εＮ−ｉ，ｉ−１（ｔ−ｉ＋１）のコンピュータ処理の削減をもたらす。合計で４つのそのようなコンピュータ処理のセットがある。すなわち、（Ｍ＋２≦ｉ≦３Ｐ−１）、（３Ｐ＋２≦ｉ≦Ｎ−１）、（２≦ｉ≦Ｐ−１）、および、（Ｐ＋２≦ｉ≦Ｍ−１）によって与えられるｉの値を持つεＮ−ｉ，ｉ−１（ｔ−ｉ＋１）である。さらに、これら４つのコンピュータ処理のセットは、次に、カルマンゲインベクトルのために必要なＮ個の残差が生成されるまで、繰り返し重複する同様の方法などで８つに分割することができる。
【０１３１】
手順は、式（４１）および（４２）の反復手法を使用して中心近くの非正規化カルマンゲインベクトルの２つの成分を計算することによって開始される。Ｍ番目の成分εＭ，Ｍ−１（ｔ−Ｍ＋１）は、前方残差ｅＭ，０（ｔ）から開始する式（４１）の反復使用を介して計算される。（Ｍ＋１）番目の成分εＭ−１，Ｍ（ｔ−Ｍ）は、後方残差ε０，Ｍ（ｔ−Ｍ）から開始する式（４２）の反復使用を介して計算される。これらの開始残差を使用することは、事実、本質的ではないが、それらは、要求されるコンピュータ処理の数の面からは、使用するうえで最も経済的であると信じられている。
【０１３２】
図５は、ｆおよびｐ指数の値に従い、水平および垂直の軸５０および５２に対してプロットされた、補間残差εｐ，ｆ（ｔ−ｆ）を視覚的に表す。三角形空間５４における各点は、補間残差を表す。図の点の水平位置および関連するｆ指数の値は、補間残差を生成するために使用されるその後のデータサンプルの数を表す。垂直位置および関連するｐ指数の値は、補間残差を作成するために使用される過去のデータサンプルの数を表す。水平軸５０上の値は、ｆ＝０〜Ｎ−１およびｐ＝０を持つ補間残差であり、したがって、それらも、既に説明したように、かつ、その時に与えられた理由のために得られた後方予測残差
【数９４】
0004398146.tif 000095
である。同様に、垂直軸５２上の値は、ｆ＝０およびｐ＝０〜Ｎ−１を持つ補間残差であり、したがって、それらも、上記のように得られた前方予測残差
【数９５】
0004398146.tif 000096
である。
【０１３３】
計算することが要求される補間残差は、直線の半分５６ａおよび５６ｂとして示す対角の点線５６上に位置し、それらは、既に述べたように、非正規化カルマンゲインベクトル
【数９６】
0004398146.tif 000097
の成分
【数９７】
0004398146.tif 000098
である。対角線５６に対して全体的に中央にある５８および６０における２つの残差εＭ，Ｍ−１（ｔ−Ｍ＋１）およびεＭ−ｉ，Ｍ（ｔ−Ｍ）を計算するために反復において生成される残差のシーケンスは、それぞれ鎖線６２および６４として示す。
【０１３４】
次に、次数Ｍ＝Ｎ／２を除いて、本来の問題と原理的には同一である２つの副次的問題がある。それらは、それぞれ半分の直線５６ａおよび５６ｂで示す。手順の次のステップは、２つの成分の対を計算することであり、各対は、それぞれ半分の直線５６ａまたは５６ｂに対して全体的に中央にある。Ｎ／４＝Ｍ／２＝Ｐとする。
【０１３５】
【数９８】
0004398146.tif 000099
のＰ番目の成分、すなわち、ε３Ｐ，Ｐ−１（ｔ−Ｐ＋１）は、前方残差ε３Ｐ，０（ｔ）から開始する式（４１）の反復によって計算される。
【０１３６】
【数９９】
0004398146.tif 000100
の（Ｐ＋１）番目の成分、すなわち、ε３Ｐ−１，Ｐ（ｔ−Ｐ）は、それ自体が
【数１００】
0004398146.tif 000101
の計算中に計算された補間残差εＭ，Ｐ（ｔ−Ｐ）から開始する式（４２）の反復によって計算される。
【０１３７】
【数１０１】
0004398146.tif 000102
の３Ｐ番目の成分、すなわち、εＰ，３Ｐ−１（ｔ−３Ｐ＋１）は、残差εＰ，Ｍ（ｔ−Ｍ）から開始する式（４１）の反復によって計算される。
【０１３８】
【数１０２】
0004398146.tif 000103
の（３Ｐ＋１）番目の成分、すなわち、εＰ−１，３Ｐ（ｔ−３Ｐ）は、残差ε０，３Ｐ（ｔ−３Ｐ）から開始する式（４２）の反復によって計算される。
【０１３９】
この点までのコンピュータ処理の展開は図６に説明され、図中で、既に説明したものと同等の部分は同じ参照番号を与える。４つの水平および垂直鎖線６６は、図５に比較して本図に加えられ、非正規化カルマンゲインベクトルの４つの追加的な補間残差または成分の計算を示す。
【０１４０】
図６は、次に、５６ｃなどの４つの対角の四半線によって示すように、次数Ｐの４つの副次的問題があることを説明する。各副次的問題を２つの半分のサイズの副次的問題に分割し、直線部分の中央領域における２つの隣接する残差を評価するこの手順は、非正規化カルマンゲインベクトルの全ての成分が計算されるまで続けられる。これは、「分割征服」手法と呼ばれる。これは、Ｏ（Ｎ２）からＯ（Ｎｌｏｇ２Ｎ）までに要求されるコンピュータ処理の数を削減する。なぜなら、図中の直線間の空間によって示される残差を評価することが必要でないからである。
【０１４１】
Ｎ＝６４の場合、実際に計算された補間残差の集合を図７に示す。既に示したように、７０などの垂直線は、式（４２）を使用して下方に反復される残差を示し、７２などの水平線は式（４１）を使用して右に反復される残差を示す。
【０１４２】
図７を調べると、一般的な手法は、残差の２つの直交する線を生成すること、各線に沿って約中間までの残差を選定すること、および、線の方向に直交して反復して、非正規化カルマンゲインベクトルの要求された値に到達するまで反復のそれぞれ新しい線を生成することが分かる。この手順は、既に選定された残差の約中間までの残差を使用して、および、同様に、反復の新しい各線の約中間までの残差を使用して繰り返される。
【０１４３】
厳密に言えば、「各線に沿って中間まで」は不正確である。なぜなら、中間点には残差がないからである。代わりに、中間点は、２つの値の中間であり、本来の予測残差の場合では（図５の最上および最左軸５０および５２上）、中間点の各側に、Ｎ／２個の残差がある（Ｎ＝６４に対しては３２個）。中間点のすぐ隣および逆側の２つの残差の１つで、反復が開始される。開始された残差は、次の反復で漸増されない指数の大きな値を有するものである。これは、実際には本質的でないが、最も小さな反復ステップ数の数値的に堅牢な手順をもたらすと思われる。これに関連して、再び図６を参照すると、非正規化カルマンゲインベクトルを作成するために、開始点は、前方予測残差εＭ，０（ｔ）であり、反復は、第２またはｆ指数（最初はゼロ）がＭ−１になるまでＭ−１ステップにわたって実行された。後方予測残差ε０，Ｍ−１（ｔ）で開始し、最初またはｐ指数がＭになるまで反復することもできるが、これは、反復を１つ多く要求し、「分割征服」処理に役立たない。後の方の反復は、中間点のすぐ隣の、かつ、増加されない指数の大きな値を有する残差で同様に開始され、関連する中間点は、既に得られている
【数１０３】
0004398146.tif 000104
の値を提供する補間残差と前の方の反復のための開始残差との間の中間である。
【０１４４】
２の累乗の整数に等しくない次数Ｎを持つフィルタの場合、上述の分割征服手法はまだ使用できるが、問題は異なった方法で分割される。各問題を２つの等しい副次的問題に分割することは、完全な解決を得るために、最早、完全には適切ではない。問題または副次的問題は、２つ以上の必ずしも等しくない副次的問題には分割できる。例えば、Ｎ＝４８は、次数３２および１６の副次的問題に分割でき、その１つは、３２個の重みベクトル成分、および、他の１つは１６個をもたらす。Ｎのいかなる整数値も、各々が２の累乗であり、要求される重みベクトル成分の部分集合をもたらす数の和として扱うことができる。そのため、問題は、このように解決できる。他の多くの「分割征服」方式は、２の累乗の整数に等しくない次数Ｎを持つフィルタの重みベクトルを、等しくない次数を持つ副次的重みベクトルに分割する多くの異なった方法に基づいて可能である。
【０１４５】
図１の段１６を参照すると、カルマンゲインベクトルのｊ番目の成分は式（７）を使用して計算される。この式において、分子は、非正規化カルマンゲインベクトルのｊ番目の成分である帰納的補間残差εＮ−ｊ，ｊ−１（ｔ−ｊ＋１）である。帰納的残差は、演繹的残差ｅＮ−ｊ，ｊ−１（ｔ−ｊ＋１）および変換係数δＮ−ｊ，ｊ−１（ｔ−ｊ＋１）として、図３および４におけるように計算される。
【０１４６】
帰納的残差自体は、
【数１０４】
0004398146.tif 000105
のように計算される。
【０１４７】
式７の分母は、
【数１０５】
0004398146.tif 000106
によって各反復において更新されるＥＮ−ｊ，ｊ−１（ｔ−ｊ＋１）の形のものである。
【０１４８】
ここで図８を参照すると、Ｎ次目の適応フィルタが電子的に実施されることが示される。適応フィルタは、接続ノード１０４１〜１０４Ｎの個々の対の間に直列に接続される遅延セル１０２１〜１０２Ｎ−１の鎖で構成される。これらのノードは、それぞれ増幅率ｗ１（１）〜ｗＮ（ｔ）を備えて更新バス１０８に接続されるそれぞれの増幅器１０６１〜１０６Ｎに接続される。増幅器１０６は合算器１１０に出力を供給する。
【０１４９】
各遅延セル１０２は、第１のノード１０４１、第１の遅延セル１０２１、および、第１の増幅器１０６１に入力される入力信号サンプルｘ（ｔ）の連続する値の間の時間に等しい遅延を供給する。クロックが動作すると、遅延セルは、直前の先行するクロックサイクルで受け取られた信号サンプル入力ｘ（ｔ−１）を出力し、新しい信号サンプルｘ（ｔ）を入力する。その結果、ｘ（ｔ）が第１のセル１０２１および第１の増幅器１０６１に入力されると、ｉ番目（ｉ＝２〜Ｎ−１）のセル１０２ｉおよびｉ番目の増幅器１０６ｉ（ｉ＝２〜Ｎ）は、ｘ（ｔ−ｉ＋１）の入力を受け取る。増幅器は、重みベクトルを信号ｘ（ｔ）〜ｘ（ｔ−Ｎ＋１）にまとめて適用する個々のゲイン率を有する。すなわち、ｉ番目の増幅器１０６ｉは、時間ｔにおいてｗｉ（ｔ）のゲインを有し、ｗｉ（ｔ）ｘ（ｔ−ｉ＋１）の出力を作成する。合算器１１０は、増幅器の出力を合計する。すなわち、その出力Ｓｏは、
【数１０６】
0004398146.tif 000107
である。これは、式（１）にある要求された適応フィルタ出力である。重みｗｉ（ｔ）は、既に与えた式（３）および（４）に従って更新バス１０８を介して更新される。
【０１５０】
カルマンゲインベクトルが知られているとすると、これまでの説明で与えられた式は、適切なキャリヤ媒体に記録され、従来のコンピュータシステム上で実行するプログラム命令を含む適切なコンピュータプログラムによって明確に評価することができる。キャリヤ媒体は、メモリ、フロッピー（登録商標）もしくはコンパクトもしくは光ディスク、或いは、他のハードウエア記録媒体、または、電気信号でもよい。このようなプログラムは、熟練したプログラマが、発明を要求せずに、これまでの説明から実施することが明白である。なぜなら、それは、よく知られているコンピュータ処理手順を含むからである。ｘが正の整数であるＮ＝２ｘを仮定して、カルマンゲインベクトルを計算するためのプログラムの概略を以下に説明する。コードはＭＡＴＬＡＢ（登録商標）のコンピュータプログラムの規則を使用して書かれている。セミコロン（；）は命令の終了を示す。エプシス（ｅｐｓｉｓ）（．．．）は命令が次の行に続くことを示す。記号「＊」は、２つのベクトルの成分の乗算を示す。それぞれ成分ａｉ、ｂｉを有する２つのベクトルａおよびｂの成分の乗算は、成分ａｉ、ｂｉ（ｉ＝１、２、３など）の同じ指数を持つ対の積ａｉｂｉと等しいｉ番目の成分ｃｉを持つベクトルｃを形成すると定義される。
【０１５１】
所与の時点におけるＮ次目の非正規化カルマンゲインベクトル（以下、記号「ｋ」）は、４行のプログラムによって与えられる。式（１０）に従った真の（すなわち、正規化）カルマンゲインベクトルへの非正規化カルマンゲインベクトルの変換は、熟練したプログラマが発明を要求せずに実施することが明白である。なぜなら、上記変換は、よく知られているコンピュータ処理手順を含むからである。
【０１５２】
［ｋｍ，ｄｅｌｔａｋｍ，ｓｔｏｒｅ，ｓｔａｔｅ］＝ｉｎｔｅｒｐｏｌａｔｅ（Ｎ，ｆｒ，ｂｒ，ｄｅｌｔａｆ，ｄｅｌｔａｂ，ｆｒ，ｂｒ，ｂｅｔａ，ｓｔｏｒｅ，ｓｔａｔｅ）；
ｋｐ＝［ｆｒ（Ｎ），ｋｍ，ｂｒ（Ｎ）］；
ｄｅｌｔａｋ＝［ｄｅｌｔａｆ（Ｎ），ｄｅｌｔａｋｍ，ｄｅｌｔａｂ（Ｎ）］；
ｋ＝ｋｐ．＊ｄｅｌｔａｋ；
【０１５３】
ここで、Ｎ次元のベクトル「ｆｒ」および「ｂｒ」は、その時点に対する次数０〜Ｎ−１の演繹的前方および後方予測残差を含み、ｄｅｌｔａｆ、ｄｅｌｔａｂは、演繹的残差を帰納的残差に関連させる対応する変換係数を含むＮ次元ベクトルであり（帰納的残差は、演繹的残差と変換係数の積に等しい）、変数「ｓｔｏｒｅ」および「ｓｔａｔｅ」は、中間量を記憶するために使用され、それぞれ次元Ｎ×Ｎ×２およびＮ×Ｎ×４のアレーである。前方および後方予測残差および変換係数は、例えば、ＱＲＤに基づいたＬＳＬプログラムを使用して前述のとおりに作成することができる。中間量「ｓｔｏｒｅ」および「ｓｔａｔｅ」は、最初にプログラムを実行する前に初期化する必要がある。これについては後述する。
【０１５４】
ｎ＝２ｍと定義し、ｍは２以上の整数とすれば、関数「ｉｎｔｅｒｐｏｌａｔｅ」は、水平線５０および垂直線５２によって定義される、図４に描かれる空間の三角形領域の対角線を構成する補間残差の（ｎ−２）次元のベクトルを計算する。対角線の中央の近くの２つの残差は、関数「ａｃｒｏｓｓ」および「ｄｏｗｎ」に対するコールを介して帰納法（４１）および（４２）を使用して計算される。もしｎが４より大きければ、残りの対角成分は、次元ｎ／２のデータから構成される関数「ｉｎｔｅｒｐｏｌａｔｅ」に対する２つのさらなる（再帰性）コールによって計算される（「分割征服」技術）。関数「ｉｎｔｅｒｐｏｌａｔｅ」は：
ｆｕｎｃｔｉｏｎ［ｋ，ｄｅｌｔａｋ，ｓｔｏｒｅ，ｓｔａｔｅ］＝ｉｎｔｅｒｐｏｌａｔｅ（ｎ，ｖ，ｈ，ｄｅｌｔａｖ，ｄｅｌｔａｈ，ｆｒ，ｂｒ，ｂｅｔａ，ｓｔｏｒｅ０，ｓｔａｔｅ０）
ｓｔｏｒｅ＝ｓｔｏｒｅ０；ｓｔａｔｅ＝ｓｔａｔｅ０；
ｉｆ（ｎ＞４）
［ｖ１，ｄｅｌｔａｖ１，ｓｔａｔｅ（１：ｎ／２，ｎ／２＋１，：）］＝．．．
ｄｏｗｎ（ｎ／２，ｈ（ｎ／２＋１），ｄｅｌｔａｈ（ｎ／２＋１），ｂｒ（ｎ／２＋１：ｎ），ｂｅｔａ，ｓｔａｔｅ（１：ｎ／２，ｎ／２＋１，：））；
［ｈ１，ｄｅｌｔａｈ１，ｓｔｏｒｅ（（ｎ／２＋１），１：（ｎ／２），：），ｓｔａｔｅ（（ｎ／２＋１），１：（ｎ／２），：）］＝．．．
ａｃｒｏｓｓ（ｎ／２，ｖ（ｎ／２＋１），ｄｅｌｔａｖ（ｎ／２＋１），ｆｒ（（ｎ／２＋１）：ｎ），ｂｅｔａ，ｓｔｏｒｅ（（ｎ／２＋１），１：（ｎ／２），：）．．．
ｓｔａｔｅ（（ｎ／２＋１），１：（ｎ／２），：））；
［ｋｕ，ｄｅｌｔａｋｕ，ｓｔｏｒｅ（１：ｎ／２，ｎ／２＋１：ｎ，：），ｓｔａｔｅ（１：ｎ／２，ｎ／２＋１：ｎ，：）］＝．．．
ｉｎｔｅｒｐｏｌａｔｅ（ｎ／２，ｖ１，ｈ（ｎ／２＋１：ｎ），ｄｅｌｔａｖ１，ｄｅｌｔａｈ（ｎ／２＋１：ｎ），  ｆｒ（ｎ／２＋１：ｎ），ｂｒ（ｎ／２＋１：ｎ），．．．
ｂｅｔａ，ｓｔｏｒｅ（１：ｎ／２，（（ｎ／２）＋１）：ｎ，：），ｓｔａｔｅ（１：ｎ／２，ｎ／２＋１：ｎ，：））；
［ｋ１，ｄｅｌｔａｋ１，ｓｔｏｒｅ（ｎ／２＋１：ｎ，１：ｎ／２，：），ｓｔａｔｅ（ｎ／２＋１：ｎ，１：ｎ／２，：）］＝．．．
ｉｎｔｅｒｐｏｌａｔｅ（ｎ／２，ｖ（ｎ／２＋１：ｎ），ｈ１，ｄｅｌｔａｖ（ｎ／２＋１：ｎ），ｄｅｌｔａｈ１，  ｆｒ（ｎ／２＋１：ｎ），ｂｒ（ｎ／２＋１：ｎ），．．．
ｂｅｔａ，ｓｔｏｒｅ（（（ｎ／２）＋１）：ｎ，１：ｎ／２，：），ｓｔａｔｅ（ｎ／２＋１：ｎ，１：ｎ／２，：））；
ｋ＝［ｋ１，ｈ１（ｎ／２），ｖ１（ｎ／２），ｋｕ］；
ｄｅｌｔａｋ＝［ｄｅｌｔａｋ１，ｄｅｌｔａｈ１（ｎ／２），ｄｅｌｔａｖ１（ｎ／２），ｄｅｌｔａｋｕ］；
ｅｌｓｅ
［ｖ１，ｄｅｌｔａｖ１，ｓｔａｔｅ（１：ｎ／２，ｎ／２＋１，：）］＝．．．
ｄｏｗｎ（ｎ／２，ｈ（ｎ／２＋１），ｄｅｌｔａｈ（ｎ／２＋１），ｂｒ（ｎ／２＋１：ｎ），ｂｅｔａ，ｓｔａｔｅ（１：ｎ／２，ｎ／２＋１，：））；
［ｈ１，ｄｅｌｔａｈ１，ｓｔｏｒｅ（ｎ／２＋１，１：ｎ／２，：），ｓｔａｔｅ（ｎ／２＋１，１：ｎ／２，：）］＝．．．
ａｃｒｏｓｓ（ｎ／２，ｖ（ｎ／２＋１），ｄｅｌｔａｖ（ｎ／２＋１），ｆｒ（ｎ／２＋１：ｎ），ｂｅｔａ，ｓｔｏｒｅ（ｎ／２＋１，１：ｎ／２，：），ｓｔａｔｅ（ｎ／２＋１，１：ｎ／２，：））；
ｋ＝［ｈ１（ｎ／２），ｖ１（ｎ／２）］；
ｄｅｌｔａｋ＝［ｄｅｌｔａｈ１（ｎ／２），ｄｅｌｔａｖ１（ｎ／２）］；
ｅｎｄ
【０１５５】
関数「ｄｏｗｎ」は反復（４２）を実施する。すなわち、（演繹的残差ｈ＝ｅｐ，ｆ（ｔ−ｆ）および変換係数ｄｅｌｔａ０＝δｐ，ｆ（ｔ−ｆ）によって実際に表される）εｐ，ｆ（ｔ−ｆ）の形の残差から開始し、（再び、ｖおよびｄｅｌｔａ１にそれぞれ記憶される演繹的残差および変換係数によって表される）ｉ＝１〜ｎ−１についての残差εｐ＋ｉ，ｆ（ｔ−ｆ）のシーケンスを作成する。
【０１５６】
関数「ｕｐｄａｔｅ」は、関数「ａｃｒｏｓｓ」にも共通で、それら双方を以下に説明する。関数「ｄｏｗｎ」は、
ｆｕｎｃｔｉｏｎ［ｖ，ｄｅｌｔａ１，ｓｔａｔｅ］＝ｄｏｗｎ（ｎ，ｈ，ｄｅｌｔａ０，ｂｒ，ｂｅｔａ，ｓｔａｔｅ０）
ｓｔａｔｅ＝ｓｔａｔｅ０；
ｖ（１）＝ｈ；ｄｅｌｔａ１（１）＝ｄｅｌｔａ０；
ｆｏｒ  ｉ＝２：ｎ，
［ｖ（ｉ），ｄｅｌｔａ１（ｉ），ｓｔａｔｅ（ｉ，１，：）］＝ｕｐｄａｔｅ（ｖ（ｉ−１），ｄｅｌｔａ１（ｉ−１），ｂｒ（ｉ），ｂｅｔａ，ｓｔａｔｅ（ｉ，１，：））；
ｅｎｄ
【０１５７】
関数「ａｃｒｏｓｓ」は反復（４１）を実施する。すなわち、（演繹的残差ｖ＝ｅｐ，ｆ（ｔ−ｆ）および変換係数ｄｅｌｔａ０＝δｐ，ｆ（ｔ−ｆ）によって実際に表される）εｐ，ｆ（ｔ−ｆ）の形の残差から開始し、（再び、ｈおよびｄｅｌｔａ１にそれぞれ記憶される演繹的残差および変換係数によって表される）ｉ＝１〜ｎ−１についての残差εｐ，ｆ＋１（ｔ−ｆ−ｉ）のシーケンスを作成する。時間指数の変更を実施するために、関数「ｄｏｗｎ」に比較して、余分の記憶が必要である。関数「ｕｐｄａｔｅ」は関数「ｄｏｗｎ」にも共通であり、以下に説明する。関数「ａｃｒｏｓｓ」は、
ｆｕｎｃｔｉｏｎ［ｈ，ｄｅｌｔａ１，ｓｔｏｒｅ，ｓｔａｔｅ］＝ａｃｒｏｓｓ（ｎ，ｖ，ｄｅｌｔａ０，ｆｒ，ｂｅｔａ，ｓｔｏｒｅ０，ｓｔａｔｅ０）
ｓｔａｔｅ＝ｓｔａｔｅ０；ｓｔｏｒｅ＝ｓｔｏｒｅ０；
ｈ（１）＝ｖ；ｄｅｌｔａ１（１）＝ｄｅｌｔａ０；
ｆｏｒ  ｉ＝２：ｎ，
［ｈ（ｉ），ｄｅｌｔａ１（ｉ），ｓｔａｔｅ（１，ｉ，：）］＝ｕｐｄａｔｅ（ｓｔｏｒｅ（１，ｉ，１），ｓｔｏｒｅ（１，ｉ，２），ｆｒ（ｉ），ｂｅｔａ，ｓｔａｔｅ（１，ｉ，：））；
ｓｔｏｒｅ（１，ｉ，：）＝［ｈ（ｉ−１），ｄｅｌｔａ１（ｉ−１）］；
ｅｎｄ
【０１５８】
関数「ｕｐｄａｔｅ」は、（実際に、演繹的残差ｘ＝ｅｐ，ｆ（ｔ−ｆ）および変換係数ｄｅｌｔａ＝δｐ，ｆ（ｔ−ｆ）によって表される）残差εｐ，ｆ（ｔ−ｆ）を取り、入力「ｒ」の値によって指数「ｆ」または指数「ｐ」のいずれかを１だけ増加させる。「ｓｗｉｔｃｈｉｎｇ」は要求されない。もし「ｒ」が適切な後方予測残差であれば、指数「ｐ」は増加される（式（２４）および（３３）を参照）。逆に、もし「ｒ」が適切な前方予測残差であれば、指数「ｆ」が増加される（式（２５）および（３４）を参照）。既に述べたように、これは、ＲＬＳおよび修正されたＲＬＳ問題が解決されることが要求される。これは、それぞれ関数「ｒｌｓ」および「ｍｒｌｓ」で行われる。関数「ｕｐｄａｔｅ」は、
ｆｕｎｃｔｉｏｎ［ｙ，ｄｅｌｔａ１，ｓｔａｔｅ１］＝ｕｐｄａｔｅ（ｘ，ｄｅｌｔａ，ｒ，ｂｅｔａ，ｓｔａｔｅ）
ｄ＝ｓｔａｔｅ（１）；ｋ＝ｓｔａｔｅ（２）；
ｄｍ＝ｓｔａｔｅ（３）；ｋｍ＝ｓｔａｔｅ（４）；
［ｚ，ｄｍ１，ｋｍ１］＝ｍｒｌｓ（ｘ，ｒ，ｄｅｌｔａ，ｄｍ，ｂｅｔａ，ｋｍ）；
［ｙ，ｄｅｌｔａ１，ｄ１，ｋ１］＝ｒｌｓ（ｚ，ｘ，ｄｅｌｔａ，ｄ，ｂｅｔａ，ｋ）；
ｓｔａｔｅ１（１）＝ｄ１；ｓｔａｔｅ１（２）＝ｋ１；
ｓｔａｔｅ１（３）＝ｄｍ１；ｓｔａｔｅ１（４）＝ｋｍ１；
【０１５９】
関数「ｒｌｓ」は、式（２８）〜（３２）で説明したようにＲＬＳ問題を解決する。
【０１６０】
関数「ｒｌｓ」は、
ｆｕｎｃｔｉｏｎ［ｚ，ｄｅｌｔａ１，ｄ１，ｋ１］＝ｒｌｓ（ｘ，ｙ，ｄｅｌｔａ，ｄ，ｂｅｔａ，ｋ）
ｉｆ（（ｘ＝＝０）｜（ｄｅｌｔａ＝＝０））
ｄ１＝ｂｅｔａ＾２＊ｄ；
ｓ＝０；
ｄｅｌｔａ１＝ｄｅｌｔａ；
ｅｌｓｅ
ｄ１＝ｂｅｔａ＾２＊ｄ＋ｄｅｌｔａ＊ａｂｓ（ｚ）＾２；
ｓ＝ｄｅｌｔａ＊ｘ／ｄ１；
ｄｅｌｔａ１＝ｂｅｔａ＾２＊ｄ／ｄ１；
ｅｎｄ
ｚ＝ｙ＋ｋ＊ｘ；
ｋ１＝ｋ−ｓ＊ｚ；
【０１６１】
関数「ｍｒｌｓ」は、式（３６）〜（４０）で説明した修正ＲＬＳ問題を解決する。関数「ｍｒｌｓ」は、
ｆｕｎｃｔｉｏｎ［ｙ，ｄ１，ｋ１］＝ｍｒｌｓ（ｘ，ｚ，ｄｅｌｔａ，ｄ，ｂｅｔａ，ｋ）
ｉｆ（（ｘ＝＝０）｜（ｄｅｌｔａ＝＝０））
ｄ１＝ｂｅｔａ＾２＊ｄ；
ｓ＝０；
ｅｌｓｅ
ｄ１＝ｂｅｔａ＾２＊ｄ＋ｄｅｌｔａ＊ａｂｓ（ｘ）＾２；
ｓ＝ｄｅｌｔａ＊ｘ／ｄ１；
ｅｎｄ
ｙ＝ｚ−ｋ＊ｘ；
ｋ１＝ｋ−ｓ＊ｚ；
【０１６２】
上記のプログラムリストおよび関連する数学の説明において、時点ごとに更新される特定の量がある。例えば、ｋ（ｔ−１）−＞ｋ（ｔ）である。そのため、初期値が特定されなければならない。この初期化を行うための方法の例は、以下のとおりである。第１に、コンピュータ処理に含まれる全ての記憶されている変数は、１に設定される記憶されている変換係数を除いてゼロに設定される。次に、正規化段までだが、正規化段を含まないプログラムまたはハードウエアの例示は、Ｎ個のゼロが後続する１から構成される入力時系列の初期化を処理するように構成されるが、以前と同様にＮはデジタルフィルタの次数である。この手順は、要求される適切な初期値を与え、その後、真の時系列が処理される。
【０１６３】
近年、（「高速ニュートン」アルゴリズムと呼ばれる）新しいタイプのアルゴリズムが、学術文献に現われている。例えば、以下を参照。
【０１６４】
Ｍ．ＭｏｏｎｅｎおよびＩ．Ｋ．Ｐｒｏｕｄｌｅｒ、「Ｕｓｉｎｇ  ａ  Ｌａｔｔｉｃｅ  Ａｌｇｏｒｉｔｈｍ  ｔｏ  Ｅｓｔｉｍａｔｅ  ｔｈｅ  Ｋａｌｍａｎ  Ｇａｉｎ  Ｖｅｃｔｏｒ  ｉｎ  Ｆａｓｔ  Ｎｅｗｔｏｎ−ｔｙｐｅ  Ａｄａｐｔｉｖｅ  Ｆｉｌｔｅｒｉｎｇ：高速ニュートンタイプの適応フィルタリングにおけるカルマンゲインベクトルを評価するための格子アルゴリズムの使用」、Ｐｒｏｃ．ＩＣＡＳＳＰ’９７、ミュンヘン、１９９７年４月。
【０１６５】
Ｇ．Ｖ．ＭｏｕｓｔａｋｉｄｅｓおよびＳ．Ｔｈｅｏｄｏｒｉｄｉｓ、「Ｆａｓｔ  Ｎｅｗｔｏｎ  Ｔｒａｎｓｖｅｒｓａｌ  Ｆｉｌｔｅｒｓ−Ａ  Ｎｅｗ  Ｃｌａｓｓ  ｏｆ  Ａｄａｐｔｉｖｅ  Ｅｓｔｉｍａｔｉｏｎ  Ａｌｇｏｒｉｔｈｍｓ：高速ニュートン横断フィルタ−適応評価アルゴリズムの新しいクラス」、ＩＥＥＥ  ｔｒａｎｓ．ＳＰ−３９（６）、２１８４〜２１９３頁、１９９１年。
【０１６６】
Ｄ．Ｋ．ＰｈｉｌｌｉｐｓおよびＣ．Ｆ．Ｎ．Ｃｏｗａｎ、「Ｚｅｒｏ−Ｐｈａｓｅ  Ｓｉｇｎａｌ  Ｃｏｎｄｉｔｉｏｎｉｎｇ  ｆｏｒ  Ｉｍｐｒｏｖｅｄ  ＮＬＭＳ  Ｐｅｒｆｏｒｍａｎｃｅ：改良されたＮＬＭＳの性能に対するゼロ−位相信号の条件」、１３ｔｈ  Ｉｎｔ．Ｃｏｎｆ．ｏｎ  ＤＳＰ、１９９７年７月２〜４日、Ｓａｎｔｏｒｉｎｉ、ギリシャ、３７〜３９頁。
【０１６７】
Ｋ．ＭａｏｕｃｈｅおよびＤ．Ｔ．Ｍ．Ｓｌｏｃｋ、「Ａ  Ｆａｓｔ  Ｉｎｓｔｒｕｍｅｎｔａｌ  Ｖａｒｉａｂｌｅ  Ａｆｆｉｎｅ  Ｐｒｏｊｅｃｔｉｏｎ  Ａｌｇｏｒｉｔｈｍ：高速インスツルメンタル可変アフィン投射アルゴリズム」、Ｐｒｏｃ．ＩＣＡＳＳＰ’９８、米国ワシントン州シアトル、１４８１〜４頁。
【０１６８】
高速ニュートンアルゴリズムはＲＬＳアルゴリズム、および、フィルタリングされる入力信号が、低次数自己回帰（ＡＲ）処理としてモデル化できるという仮定に基づいている。この仮定は、ＲＬＳアルゴリズムにおけるコンピュータ処理のいくつかを、コンピュータ処理の大きな節約は別として、おそらく収斂性能を殆ど失うことなく、無視することを可能にする。本発明によれば、この手法が実行可能となるために、使用するＲＬＳアルゴリズムがフィルタ係数を明示的に作成するタイプのものであることが必要であることが見出されている。これは、本発明の前に知られているＲＬＳ格子アルゴリズムを使用しない。
【０１６９】
入力信号におけるいかなる自己回帰の性質も利用できるために、アルゴリズムが、高速ニュートン（ＦＮ）アルゴリズムに変換可能えあることも、特に音響アプリケーションにおいて有利である。本発明がＦＮ手法を使用した実施に適していることを示すことができる。
【０１７０】
本発明は、様々なアプリケーションにおける使用に適している。適応フィルタのためのそのようなアプリケーションは、Ｓ  Ｈａｙｋｉｎの「Ａｄａｐｔｉｖｅ  Ｆｉｌｔｅｒ  Ｔｈｅｏｒｙ：適応フィルタ理論」第２版、Ｐｒｅｎｔｉｃｅ−Ｈａｌｌ、Ｅｎｇｌｅｗｏｏｄ  Ｃｌｉｆｆｓ、米国ニュージャージー州、１９９１年により与えられる。その１つは、システム識別である。ここで、要件は、現実のシステムを観察すること、および、その動作のコンピュータモデルを生成することである。モデルは、健康モニタリング、制御システムの開発、（例えば、部屋の音響特性を操作するための）歪み補償プロセッサを設計することなどの多くのことに使用することができる。システム識別は、システムの入力および出力をモニタすること、および、これらの信号をデジタルの電子的形態の入力データとして、コンピュータシステムで実施される適応フィルタに送ることによって達成される。厳密には必要でないが、システムのいくつかの他のパラメータ化より、むしろフィルタの重みを有することは、それらは解釈および操作するのがより容易であるため、通常望ましいと考えられる。
【０１７１】
適応フィルタは、通信チャンネル等化にも適用可能である。近代的なデジタル通信システムにおいて、速いデータ速度は、しばしば、要件となる。ここで「速い」とは、使用している通信チャンネルの最大データ速度との関係で「速い」ことを意味する。システム内の個々のデータビットは、通信チャンネルの特性のために、それらの信号波形が重なるほどともに近接して送られることがある。これは、情報を正確に回復させるためのシステム内の受信器の能力に悪影響を及ぼす。標準的手法は、チャンネルを「等化」することである。これは、チャンネル等化フィルタ（適応フィルタ）または（Ｖｉｔｅｒｂｉアルゴリズムを使用して通常実施される）最大尤度シーケンス評価のいずれかを介して行うことができる。このような等化は、例えば、ＧＳＭ移動電話システム、ケーブルネットワークを介したデジタルＴＶ送信、および、電話回線用データモデムにおいて必要である。
【０１７２】
最も効果的な等化フィルタ構造の１つは、「決定フィードバックイコライザ」である。これは、通信チャンネルの影響を打ち消すために、（正しいと仮定される）以前の復号化決定を使用する。これは、フィルタの重みのためのいかなる更新メカニズムからも独立に受け取った信号をフィルタリングするための能力を要求する。フィルタの他のいくつかのパラメータ化より、むしろフィルタの重みを得ることは、この課題の実施をさらに容易にする。
【０１７３】
最大尤度シーケンス評価は通信チャンネルを等化する非常に強力な手段であり、ＧＳＭ移動電話システムに使用されている。チャンネル等化フィルタリングとは異なり、これは、通信チャンネル内の送信された情報信号を直接評価することによって動作する。これを達成するために、チャンネルによって導入された歪みの評価が要求され、適応フィルタによって提供することができる（上記のシステム識別と比較）。再び、あまり直接的でない手法とは逆に、フィルタの重みに関して直接に通信チャンネルをモデル化することが望ましい。
【０１７４】
例えば、電話回線用データモデムなどのいくつかのアプリケーションにおいて、適切な等化フィルタはあらかじめ知られていず、そのため、適応フィルタによって決定されなければならないが、それが知られたなら、それは、時間とともにほとんど変化しない。ここで、フィルタの重みを継続的に更新することにほとんど問題はない。最も単純な代案は、フィルタの重みの計算が要求される時にのみ行われるように、（時々「オフライン処理」と呼ばれる）フィルタの重みの計算からフィルタリングを分離することである。フィルタリングと異なり、フィルタの重みの計算がデータ速度に対処する必要がない時、これは高速データにさらに利点を与える。再び、他のいくつかのフィルタのパラメータ化より、むしろフィルタの重み自体を得ることが、この手法の実施をより容易にする。
【０１７５】
前述の知られていないが変化しない場合とは逆に、例えば、高周波無線通信などのいくつかの状況では、通信チャンネル特性は時間とともに変化することがあり、等化フィルタの重みの継続的更新を要求する。これは、２つの基本的な方法、再帰性またはブロック適応フィルタのいずれかの使用によって達成できる。再帰性適応フィルタは、新しいデータが到着するごとにフィルタの重みを継続的に更新する。ブロック適応フィルタは、データをブロックに区切り、各ブロックを他のブロックから独立して処理する。再帰性適応フィルタは、何百万ものデータサンプルを処理するために要求されることがあり、したがって、適応フィルタは、コンピュータ計算回路で実施された時でさえ、正しく振る舞うことは重要である。各データブロックが一時に処理される限られた量のデータのみを表すため、ブロック適応フィルタはこの問題にあまり影響されない。しかし、ブロック適応フィルタは、データのブロックに対する余分の記憶要件、および、結果として得られる処理されたデータのブロックの滑らかな「結合」に対する必要性などのいくつかの短所を有する。
【０１７６】
制約のある適応フィルタは知られている。それらは、最小分散スペクトル解析、および、アンテナアレーからのデータを処理するためなどの様々なアプリケーションを有する。ここで、適応フィルタは、特定の周波数におけるゼロ応答などのフィルタの重みに関する制約に従う信号を最小化することが要求される。このような適応フィルタは、カルマンゲインベクトルを使用して効果的に更新することができる。したがって、本明細書に説明する本発明の関連部分は、制約のある適応フィルタに使用することができる。
【０１７７】
図１以降を参照して説明した本発明の実施例において、適応フィルタは、ＲＬＳ格子アルゴリズム１２、補間残差計算１４、正規化１６、および、重み更新１８の４つのブロックから構成されると示されている．ブロック１２〜１８の非常に詳細な例は、これまでに述べた本発明の実施形態において述べた。しかし、述べた実施形態の利点を有する、ブロック１２〜１８が実施できる多くの異なった方法があることは、フィルタリングの当業者に明らかである。
【０１７８】
本明細書に述べた実施形態は、カルマンゲインベクトル自体を導出し、計算上の不正確さ、すなわち、四捨五入エラーを無視している。もしカルマンゲインベクトルが、代替となる様々なゲインベクトルの１つによって提供される、カルマンゲインベクトルに対する近似によって置き換えられるなら、適応フィルタが（恐らく、性能が低減して）実現可能であることは知られている。例えば、上記に述べた高速ニュートンアルゴリズムに関する文献を参照。これらの代替ゲインベクトルの長所は、それらが、カルマンゲインベクトルより少ない演算で計算できることである。
【０１７９】
本発明の実施例において、補間残差を生成する第１のステップは、再帰性ＬＳ格子（ＲＬＳＬ）アルゴリズムを介して最小二乗（ＬＳ）予測残差を生成することである。ＲＬＳＬアルゴリズムは、予測残差を生成するいかなる他の方法によっても置き換えられる。ＬＳ予測残差を生成するために使用できる他のアルゴリズムは、従来のＲＬＳアルゴリズム、高速横断フィルタ（ＦＴＦ）アルゴリズム、または、ＱＲ  ＲＬＳアルゴリズムなどのＲＬＳアルゴリズムである。
【０１８０】
最小平均二乗（ＬＭＳ）アルゴリズム、傾斜適応格子（ＧＡＬ）アルゴリズム、クランプＬＳＬアルゴリズム、または、高速ニュートン横断フィルタ（ＦＮＴＦ）アルゴリズムなどの非ＲＬＳアルゴリズムも使用できる。この場合、残差（の少なくともいくつか）は、近似的ＲＬＳ予測残差である。非ＲＬＳアルゴリズムの使用は、カルマンゲインベクトルと同一でないゲインベクトルに導く。
【０１８１】
予測残差は、図１の１４における補間残差計算への唯一の入力である必要はない。補間残差計算１４の基礎は、反復が補間残差の次数、すなわち、それらのｐおよびｆの下付き文字を増加することである。予測残差は、ｐ＝０またはｆ＝０に対応し、そのため、可能な開始変数である。明らかに、変数のいかなる適切な集合からでも開始することができる。例えば、ｐ＝１の補間残差の集合、および、ｆ＝１の残差の集合は、任意の手段により計算（または、近似）することができ、したがって、これらは非正規化カルマンゲインベクトルを構成する所望の補間残差を生成するために使用できる。例えば、Ｊ  Ｔ  Ｙｕａｎの「ＱＲ  ｄｅｃｏｍｐｏｓｉｔｉｏｎ  ｂａｓｅｄ  ｌｅａｓｔ  ｓｑｕａｒｅｓ  ｌａｔｔｉｃｅ  ｉｎｔｅｒｐｏｌａｔｏｒｓ：ＱＲ分解に基づく最小二乗格子補間」、ＩＥＥＥ  Ｔｒａｎｓ  ＳＰ、２０００年１月、第４８巻（１）、７０〜７９頁によって与えられる再帰性補間アルゴリズムを使用することができる。
【０１８２】
式（２４）および（２５）の適切な数学的操作によって、補間残差の次数、すなわち、それらのｐおよびｆの下付き文字を減少させる反復による補間残差の計算を予想することも可能である。このため、非正規化カルマンゲインベクトルを構成する残差は、開始変数として、他の多くの残差から得ることができる。特に、図１の段１４の分割征服構造を、非正規化カルマンゲインベクトルの最初の成分から最後の成分に「蛇行」（図５を参照）する処理段の連鎖で置き換えることが可能である。これらの両極端の間で生成された残差の集合は、非正規化カルマンゲインベクトルの他の全ての成分に対応する残差を含むことができる。この方法は、好ましい実施形態に使用される分割征服処理より少ない演算で済むが、同実施形態には使用されていない。なぜなら、これは、有限精度計算を使用して行われた時、劣った数値特性を有するからである。
【０１８３】
上述した分割征服手法以外にも、非正規化カルマンゲインベクトルを生成するために、いくつかの選択肢がある。例えば、同じベクトルが後方予測残差から開始する式（４２）から計算できる。これは、分割征服法のＯ（Ｎｌｏｇ２Ｎ）個の演算に対してＯ（Ｎ２）個の演算を要求する。補間残差は、様々な経路を介して、低い指数を持つ補間残差から基本的反復（その際、補間残差の次数（ｐおよびｆ下付き文字）が１だけ増加される）を使用して計算することができる。もしＲＬＳ反復が使用されるなら、取られた経路に関係なく、結果は実質的に同じである。
【０１８４】
したがって、非正規化カルマンゲインベクトルを生成するために行うことができる反復の多くの潜在的な集合がある。さらに、非正規化カルマンゲインベクトルの代わりに生成することができる他の全範囲のベクトルがある。カルマンゲインベクトルは、ＲＬＳアルゴリズムにおけるフィルタの重みを更新するために使用されるベクトルである。カルマンゲインベクトル以外にも、フィルタの重みを更新するために使用できる多くの他のゲインベクトルがある。カルマンゲインベクトルに近いゲインベクトルを備えたアルゴリズムは、ＲＬＳアルゴリズムと同様に機能することを期待されている。
【０１８５】
カルマンゲインベクトルに対する近似は、例えば、コンピュータ処理に関してより安価な反復によって、補間次数を増加させるいくつか（または、全て）の反復を置き換えることによって生成できる。例えば、反復は、そのＬＭＳ等価物、または、いかなる他の近似によって置き換えることができる。いくつかの場合、コンピュータ処理は、単なる時間遅延または全く何もないところまで削減できる（これは、上述の「高速ニュートン」アルゴリズムの背景にある同じ基本思想に基づくことに注意が必要である。）。これは、高い次数の補間残差が低い次数の補間残差と等しいという近似を行うことと同等である。
【０１８６】
再び図５を参照すると、第２の可能性は、対角線５６ａ／５６ｂ上の補間残差を計算しようと試みるより、むしろ、代わりに、カルマンゲインベクトルの左下の成分から開始する水平線８０を形成する残差を使用することができるということである。これは、ｆ＝０，．．．，Ｎ−１である成分εＮ−１，ｆ（ｔ−ｆ）から構成されるベクトルに対応する。
【０１８７】
例において、非正規化カルマンゲインベクトルは、ベクトルの各成分をその累乗によって除算することによって正規化される。非正規化カルマンゲインベクトルの成分である各残差の累乗は、式（１０）を介して計算される。この量は、例えば、単に演繹的残差あるいは帰納的残差から、または、多くの他の手段を介して近似することができる。代案となる正規化係数は、アルゴリズムの収斂特性を変化させるために使用できる。例えば、より大きな正規化係数を選定することは、収斂を緩慢にするが、これは、フィルタの重みが、一度収斂すれば、その理想的な値に近づくことを可能にする。
【０１８８】
前述の例は、式（５）によって定義されるカルマンゲインベクトルに基づいている。従来技術において、いわゆる「複式カルマンゲインベクトル」を使用するＲＬＳアルゴリズムは知られている。これは、帰納的残差より、むしろ正規化された演繹的補間残差に基づく、カルマンゲインベクトルの縮小版である。これは、わずかに修正された重み更新公式を要求するが、これはＲＬＳアルゴリズムでもある。複式カルマンゲインベクトルに対する（上述したような）近似も、使用することができる。
【０１８９】
上記に詳細に説明したように、本発明によれば、カルマンゲインベクトルが、Ｏ（Ｎｌｏｇ２Ｎ）適応フィルタに使用することができる正規化された補間残差の集合として導出できることが見出されている。しかし、カルマンゲインは、ユビキタス再帰性最小二乗（ＲＬＳ）手順の１つの形態の不可欠な部分である。適応フィルタリングを使用する雑音消去および通信チャンネル等化などのアプリケーションは別として、フィルタリング手順（および、近似的な代案）は、適応ビームフォーミングに使用することができる。これは、広帯域ビームフォーマとして知られているソナーのアプリケーションに使用されることがある多チャンネル適応フィルタを構築するためにも使用できる。カルマンゲインベクトルを構成する残差は、処理されているデータが時系列の形である場合のみ、最近の従来技術において「補間残差」と従来呼ばれている。もしデータが、例えば、空間的に分布したセンサの集合から取られるなら、対応する残差は、例え、基本的な信号処理手法が未だに有効であっても、許容される一般的な描写的名称を持たない。本発明の目的のために、表現「補間残差」は、制限なくいかなる次元、すなわち、時間または空間またはいかなる他の次元にもわたって分布したデータ成分のシーケンスからの補間によって得られた残差を指すものと理解されるべきである。
【０１９０】
全ての実際的状況について未だに検証されてはいないが、理論的考察から、フィルタパラメータが式（３）を使用して更新される場合では、補間残差を介してカルマンゲインベクトルを計算することは、同様のコンピュータ処理上の要件を持つ従来の手法より数値的に堅牢であると信じられている。
【０１９１】
前述の例は実数値のデータを使用した。本発明は、デジタル通信またはレーダシステムに使用されるデータの同相直角位相（Ｉｎ−ｐｈａｓｅ  ａｎｄ  Ｑｕａｄｒａｔｕｒｅ）チャンネルなどの複素数値のデータにも適用することができる。
【０１９２】
Ｏ（Ｎｌｏｇ２Ｎ）演算の分割征服手法を使用してカルマンゲインベクトルを得ることが好ましいが、得られる演算の数の増加が許容できるなら、上記に説明したＯ（Ｎ２）法の１つなどの補間残差を得るためのいくつかの他の方法を使用することは全く可能である。後者は、それでも長所を有する。なぜなら、上記に示したように、優れた理論的理由のために、これが、代案となる手法より数値的に堅牢である可能性が高いからである。
【図面の簡単な説明】
【図１】  本発明の適応フィルタのブロック図である。
【図２】  図１に示す再帰性最小二乗格子アルゴリズムの４つの連続する段を示す図である。
【図３】  指数の単位の相対的変化による第１の補間残差の第２の補間残差への変換を示す図である。
【図４】  指数の単位の相対的変化による第１の補間残差の第２の補間残差への変換を示す図である。
【図５】  本発明のフィルタにおけるコンピュータ処理の負荷を低減するための「分割征服」手法を示す図である。
【図６】  本発明のフィルタにおけるコンピュータ処理の負荷を低減するための「分割征服」手法を示す図である。
【図７】  本発明のフィルタにおけるコンピュータ処理の負荷を低減するための「分割征服」手法を示す図である。
【図８】  ハードウエアに関する本発明の重み更新を示す図である。
【図１】
0004398146.tif 000108
【図２】
0004398146.tif 000109
【図３】
0004398146.tif 000110
【図４】
0004398146.tif 000111
【図５】
0004398146.tif 000112
【図６】
0004398146.tif 000113
【図７】
0004398146.tif 000114
【図８】
0004398146.tif 000115