原理の説明
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/12/08 05:20 UTC 版)
N = PQ とする。N 次離散フーリエ変換を、以下のようにP 次離散フーリエ変換とQ 次離散フーリエ変換に分解する。 N 次離散フーリエ変換： F ( n ) = ∑ k = 0 N − 1 f ( k ) exp ( − 2 π i n k N ) {\displaystyle F(n)=\sum _{k=0}^{N-1}f(k)\exp \left(-2\pi i{\frac {nk}{N}}\right)} を、n = 0, 1, ..., N − 1 について計算することを考える。n, k を次のように書き換える。ただし 0 ≤ n ≤ N − 1 また 0 ≤ k ≤ N − 1 である。 n = s Q + r 0 ≤ s ≤ P − 1 , 0 ≤ r ≤ Q − 1 k = q P + p 0 ≤ p ≤ P − 1 , 0 ≤ q ≤ Q − 1 {\displaystyle {\begin{aligned}n&=sQ+r\qquad 0\leq s\leq P-1,\,0\leq r\leq Q-1\\k&=qP+p\qquad 0\leq p\leq P-1,\;0\leq q\leq Q-1\end{aligned}}} すると F ( n ) = F ( s Q + r ) = ∑ p = 0 P − 1 ∑ q = 0 Q − 1 f ( q P + p ) exp ( − 2 π i ( q P + p ) ( s Q + r ) P Q ) = ∑ p = 0 P − 1 ∑ q = 0 Q − 1 f ( q P + p ) exp ( − 2 π i ( r q Q + s p P + p r P Q ) ) = ∑ p = 0 P − 1 [ exp ( − 2 π i ( s p P + p r P Q ) ) ∑ q = 0 Q − 1 f ( q P + p ) exp ( − 2 π i r q Q ) ] {\displaystyle {\begin{aligned}F(n)&=F(sQ+r)=\sum _{p=0}^{P-1}\sum _{q=0}^{Q-1}f(qP+p)\exp \left(-2\pi i{\frac {(qP+p)(sQ+r)}{PQ}}\right)\\&=\sum _{p=0}^{P-1}\sum _{q=0}^{Q-1}f(qP+p)\exp \left(-2\pi i\left({\frac {rq}{Q}}+{\frac {sp}{P}}+{\frac {pr}{PQ}}\right)\right)\\&=\sum _{p=0}^{P-1}\left[\exp \left(-2\pi i\left({\frac {sp}{P}}+{\frac {pr}{PQ}}\right)\right)\sum _{q=0}^{Q-1}f(qP+p)\exp \left(-2\pi i{\frac {rq}{Q}}\right)\right]\end{aligned}}} ここで、 f 1 ( p , r ) = exp ( − 2 π i p r P Q ) ∑ q = 0 Q − 1 f ( q P + p ) exp ( − 2 π i r q Q ) {\displaystyle f_{1}(p,r)=\exp \left(-2\pi i{\frac {pr}{PQ}}\right)\sum _{q=0}^{Q-1}f(qP+p)\exp \left(-2\pi i{\frac {rq}{Q}}\right)} と置くと、 F ( n ) = F ( s Q + r ) = ∑ p = 0 P − 1 exp ( − 2 π i s p P ) f 1 ( p , r ) {\displaystyle F(n)=F(sQ+r)=\sum _{p=0}^{P-1}\exp \left(-2\pi i{\frac {sp}{P}}\right)f_{1}(p,r)} となる。即ち、F(n) = F(sQ + r) の計算は、次の2ステップになる。 ステップ1 p = 0, 1, ..., P − 1 と r = 0, 1, ..., Q − 1 について f 1 ( p , r ) = exp ( − 2 π i p r P Q ) ∑ q = 0 Q − 1 f ( q P + p ) exp ( − 2 π i r q Q ) {\displaystyle f_{1}(p,r)=\exp \left(-2\pi i{\frac {pr}{PQ}}\right)\sum _{q=0}^{Q-1}f(qP+p)\exp \left(-2\pi i{\frac {rq}{Q}}\right)} を計算する。これは、Q次の離散フーリエ変換 ∑ q = 0 Q − 1 f ( q P + p ) exp ( − 2 π i r q Q ) {\displaystyle \sum _{q=0}^{Q-1}f(qP+p)\exp \left(-2\pi i{\frac {rq}{Q}}\right)} の実行と、回転因子 exp(−2πipr/PQ) の掛け算を、全ての p, r の組（PQ = N 通り）に対して行うことと見ることができる。 ステップ2 s = 0, 1, ..., P − 1 と r = 0, 1, ..., Q − 1 について F ( s Q + r ) = ∑ p = 0 P − 1 exp ( − 2 π i s p P ) f 1 ( p , r ) {\displaystyle F(sQ+r)=\sum _{p=0}^{P-1}\exp \left(-2\pi i{\frac {sp}{P}}\right)f_{1}(p,r)} を計算する。ここで、右辺は r を固定すれば、P 次の離散フーリエ変換である。 ステップ1、2は、N = PQ 次の離散フーリエ変換を、Q 次の離散フーリエ変換と回転因子の掛け算の実行により、Q 組 (r = 0, 1, ..., Q − 1) の P 次離散フーリエ変換に分解したと見ることができる。 N = Qk (P = Qk − 1) の場合には、上を繰り返せば、Q 次の離散フーリエ変換と回転因子の掛け算を繰り返すことだけで次数を下げることができ、最終的に1次離散フーリエ変換（何もしないことと同じ）にまで下げると、F(t)を求めることができる。特に、Q が2または4の場合は、Q次の離散フーリエ変換は非常に簡単な計算になる。 Q = 2 の場合は、exp(−2πirq/Q) は 1 か −1 なので、Q 次の離散フーリエ変換は符号の逆転と足し算だけで計算できる。 Q = 4 の場合は、exp(−2πirq/Q) は 1, −1, i, −i のいずれかなので、Q 次の離散フーリエ変換の計算は、符号の逆転、実部虚部の交換と足し算だけで計算できる。 このため、2の累乗あるいは4の累乗次の離散フーリエ変換は簡単に計算できる。実務的に用いられるのは、Q = 2 か Q = 4 の場合のみである。なお、Q = 2 かQ = 4 の場合のこの部分のQ次の離散フーリエ変換のことを、バタフライ演算と言う。 また、Q = 2かQ = 4の場合において、計算を終了するまでに何回の「掛け算」が必要かを考える。符号の逆転、実部虚部の交換は「掛け算」として数えなければ、回転因子の掛け算のみが「掛け算」である。N = Qkの次数を1落とすためにN回の「掛け算」が必要であり、次数をkから0に落とすにはそれをk回繰り返す必要があるため、「掛け算」の数は Nk = N logQ N となる。高速フーリエ変換の計算において時間がかかるのは「掛け算」の部分であるため、これが「高速フーリエ変換では計算速度は O(N' log N) になる」ことの根拠になっている。
※この「原理の説明」の解説は、「高速フーリエ変換」の解説の一部です。
「原理の説明」を含む「高速フーリエ変換」の記事については、「高速フーリエ変換」の概要を参照ください。
原理の説明
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/01/16 20:36 UTC 版)
元々古くから備わるinitプロセスは、電源オンの後にコンピュータを通常の起動状態にすることや、シャットダウン前にきちんとサービスを終了することにしか責任を持たなかった。このため、前記の設計により現在のタスクが完了するまで将来のタスクは厳格に同期化され、さらにブロックされてしまう。さらに準備やクリーンアップ機能による制限を受けるため、これらのタスクはあらかじめ定義されねばならない。これでは現代のデスクトップコンピュータにおけるスタートアップ以外の、以下に挙げるような様々なタスクを簡潔に処理できなくなる: マシン起動中におけるUSBフラッシュドライブなどのポータブルストレージやネットワークデバイスの脱着。 システムロックなしの、特にディスクがスキャンされるまで電源すらオンになっていない場合における新規ストレージデバイスの発見とスキャン。 デバイス用ファームウェアのロード。ロードはデバイスが発見された後かつデバイスが使えない前に行わなければならないはずである。 Upstartのイベント駆動型モデルにより、イベント生成とは非同期にイベント応答ができる。
※この「原理の説明」の解説は、「Upstart」の解説の一部です。
「原理の説明」を含む「Upstart」の記事については、「Upstart」の概要を参照ください。
- 原理の説明のページへのリンク
