デジタル信号処理の礎となる数学の概念に、サンプリング定理と直交関数系がある。サンプリング定理とは、再現性の限界を定めたもので、ナイキスト周波数とも呼ばれ慣れ親しんできた。そして、その周波数から生じる位相を数学的にどう扱うかが問題となる。
一方、複雑な演算処理では乗算回数や加算回数が問題視され、アルゴリズムの効率性が問われる。そこで重宝されるのが直交関数系である。直交とは、幾何学で言うところの直角を代数的に抽象化した概念である。これを、加法や乗法で定義された多項式で考察する時、正則性や転置性といった行列式の性質を利用できるように仕組むと、演算量を大幅に減らすことができる。その際、2乗可積分関数の列として捉え、ノルムの収束性が、すなわち平均収束ってやつが正規直交系へ、さらには完備(完全)な正規直交系へと、より甘美な世界へいざなってくれる。ただし、確率論的ではあるのだが...
本書に紹介される数々の方法論もまた、直交の概念に支えられている。解析学にも、任意の物理現象を直交関係にある関数成分に分解することが、基本的な思考としてある。こいつは、線形代数における真理であろうか。やはり、バーへ向かうベクトルとクラブへ向かうベクトルも、ある次元空間上において直交関係にあるに違いない。その証拠に、今宵もまた完備(甘美)な夜の社交場へ直行するのであった...
本書はまず、離散フーリエ変換(DFT)、離散コサイン変換(DCT)、離散ハートレー変換(DHT)、ウォルシュ・アダマール変換(WFT)、カルーネン・レーベ変換(KLT)が紹介され、線形性、対称性、周期性、推移則、合成積則(巡回畳み込み計算)、相関則などの性質から離散型アルゴリズムの有用性を語ってくれる。
また、高速フーリエ変換(FFT)や高速コサイン変換(FCT)などの高速バージョンに加え、高速数論変換や高速多項式変換も興味深い。
そして、並列アルゴリズムでは、多次元FFT、遺伝的アルゴリズム、シストリックアルゴリズムが紹介され、さらに、アレイ信号処理における配置の仕方では、空間スペクトルの非線形性や分解能の考察、そしてパワースペクトルの推定にまで議論が及ぶ。
特に、高速演算を実装するプロセッサの設計において、パイプライン処理の時間的単位と並列処理の空間的配置の組合せは、幾度となくお世話になってきた概念である。シストリックアレイでは、畳込み演算、行列積和演算、IIRフィルタ、多項式除算、逐次最小2乗法に適した構造が紹介され、これらを眺めるだけでも、幸せな気分にさせてくれる...
1. 収束条件
関数列の直交展開において、基底関数に三角関数が選ばれる理由は、区間 (-π, π) において完備な正規直交系であることで、フーリエ級数は平均収束することが知られている。尚、フーリエ級数 f(x) は、よくこの形で表される。
f(x) = a0/2 + ∑(an cos nx + bn sin nx)
これの部分和、fk(x), (1 ≦ n ≦ k) において...
| fk(x) = a0/2 + | k ∑ n = 1 | (an cos nx + bn sin nx) |
任意のε＞0 と x に無関係な m を適当に選ぶ。この時、k ＞ m を満足するすべての k と任意の x に対して、|f(x) - fk(x)| ＜ ε が成り立てば、fk(x) は、f(x) に一様収束するという。
ここで、有名な二つの判定条件をメモっておこう。
[Jordan の判定条件]
点 x0 ∈ (-π, π) のある近傍で f(x) が有界変動ならば、f(x) のフーリエ級数は、x = x0 で、{f(x0 + 0) + f(x0 - 0)}/2 に収束する。さらに f(x) が連続ならば、任意のε＞0 に対して、区間 (a + ε, b - ε) で一様収束する。
[Dini の判定条件]
Φx(t) = f(x + t) + f(x - t) -2f(x) の時、点 x0 ∈ (-π, π) において、
| ∫ | π 0 |
|Φx(t)| t |
dt ＜ ∞ |
が成立すれば、フーリエ級数は x = x0 で f(x) に収束する。
2. 高速フーリエ変換(FFT)と間引き型アルゴリズム
FFTのアルゴリズムでは、データを間引いて DFT を施し、演算数を大幅に減らすという考え方がある。代表的な Cooley - Tukey アルゴリズムもその一つ。
本書は、時間間引き型と周波数間引き型のアルゴリズムを紹介している。それは、時間方向で間引きするか、空間方向で間引きするかの違いで、基本的な演算方法は同じ。
DFTは次式で定義される。
| X(k) = | N - 1 ∑ n = 0 | x(n)exp | ( | -j | 2πnk N |
) | , k = 0, 1, ..., N - 1 |
W = exp(-j2πk/N) とおくと、
そして、時間間引き型と周波数間引き型のバタフライ計算は、こんな感じ...
3. 高速数論変換(FNTT: fast number theoretic transform)
FFTを利用して巡回畳込み計算をする時、次のような問題があるという。
まず、FFTの変換核 WN は、複素数の三角関数で、事前計算や WNn の保存などが必要。また、FFTの計算にはある程度の誤差が生じるという。ただし、複素数体上で巡回畳込み特性を持つ変換は、DFT だけだとか。
そこで、複素数体以外の代数体を調べた結果、整数の mod M での剰余類環 ZM 上に、DFTの構造に似たような性質があることが発見されたという。これが、「数論変換」と呼ばれる。
数論の基本では、整数と素数の関係や、最大公約数と最小公倍数の考察があり、モジュロ演算が重要な役割を果たす。大雑把に言えば、整数を、mod M で同値とみなす思考法だ。オイラーの定理やフェルマーの定理(小定理)が重要な基本定理として君臨する世界とも言えよう。
数論変換は、正の整数 M に対し、mod M での整数環 ZM 上に、次のように定義される...
長さ N の信号系列 {x(n)} (n = 0, 1, ..., N - 1) に対して、{x(n)} ∈ ZM, a ∈ ZM と仮定する。
{x(n)} を変換行列 T
で変換すると、次式が得られる。
| X(k) ≡ | N - 1 ∑ n = 0 | x(n)αnk (mod M), (k = 0, 1, ..., N - 1) |
逆変換は、次式。
| x(n) ≡ 1/N | N - 1 ∑ k = 0 | X(k)α-nk (mod M), (n = 0, 1, ..., N - 1) |
なるほど、FFTと同型であるが、それだけでなく、巡回畳込み特性を持っていることが特徴だという。尚、物理的な意味の薄いアルゴリズムで、応用例は少ないのだそうな。古書なので今はどうか知らんが、興味深い形をしている。
4. 高速多項式変換(FPT: fast polynomical transform)
M(z) を有理数体上の多項式とし、{Pm(z)} (m = 0, 1, ..., N - 1) を有理数体上の多項式の列とすると、次式で定義される。
| ＿ Pl(z) |
≡ | N - 1 ∑ m = 0 | Pm(z)(αzd)ml | mod M(z), (l = 0, 1, ..., N - 1) |
ただし、α は定数、d は正の整数。
また、次の逆変換が存在する場合、可逆多項式変換と呼ばれる。
| Pm(z) ≡ 1/N | N - 1 ∑ l = 0 | ＿ Pl(z) |
(αzd)-ml | mod M(z), (m = 0, 1, ..., N - 1) |
可逆多項式変換は、巡回畳込み特性を持つという。尚、本書では有理数体で記述されるが、複素数体に拡張できるようだ。
また、可逆多項式変換であるための必要十分条件は、
| St = 1/N | N - 1 ∑ m = 0 | (αzd)mt |
とすると、次のようになるという。
St ≡ 1 mod M(z), t ≡ 0 (mod N)
St ≡ 0 mod M(z), t ≠ 0 (mod N)
5. シストリックアレイ
systolic とは、心臓の収縮を意味する。ホストコンピュータが心臓の鼓動のように規則正しくデータを演算器に供給し、データは演算器の間を血流のように脈動することから、その名が付けられたという。この言葉だけで、高度なパイプライン構造を匂わせ、演算器の配置がアルゴリズムの効率性に関わることを想像させる。ノイマン型コンピュータは、記憶部から読み出した命令コードやデータを演算器で処理し、その出力結果をメモリに戻す、といった工程を踏む。
したがって、演算器の計算能力だけが高くても、メモリとの入出力バンド幅の制限によって、システム全体の性能を引き出すことができない。いわゆる、「フォン・ノイマン・ボトルネック」ってやつだ。
そこで、複数の演算器を直列に配置し、それぞれの出力結果を記憶部に戻すのではなく、次の演算器に伝搬させながら、末端の演算器からすべての結果をまとめてメモリへ戻したり、あるいは、並列に配置して見かけ上の入出力バンド幅を大きくしたり、さらには、演算器と補助メモリを一組で配置するなど、様々な工夫が施される。こうした演算器の配置では、それぞれの処理時間を固定し、順序正しく同期的に処理することで効率を高めるなど、プロセッサの設計では、だいたい時分割処理と並列処理がセットで計画される。近年、マルチプロセッサが搭載されるケースも多く、CPU の数に比例した処理速度を引き出すために、時間的な配置と空間的な配置が重視される。
本書は、一次元シストリックアレイと二次元シストリックアレイの事例を紹介してくれる。
一次元シストリックアレイは、演算器を直列接続した構成で、畳込み演算、FIR/IIR フィルタ、行列ベクトル乗算などに向いているという。そして、演算器にローカルメモリを配置する構造も示している。
二次元シストリックアレイは、直交接続、三角接続、六角接続などが紹介され、行列積和演算には直交接続、逐次最小2乗法には三角接続、LU 分解には六角接続が、ぞれぞれ向いているという。二次元アレイ構造では、高速な処理能力を持つ反面、大規模になるほどクロックスキューや接続数の増加が深刻になり、コストも高くなる。
尚、畳込み演算用、行列積和演算用、IIRフィルタ、多項式除算、逐次最小2乗法の構成イメージは、こんな感じ... これらを眺めているだけでも、構造上のヒントを与えてくれる。
0 コメント:
コメントを投稿