リング上の離散フーリエ変換

数学において、環上の離散フーリエ変換は、値が一般的に複素数である関数の任意の環上の離散フーリエ変換（DFT）を一般化したものである。

意味

$R$ を任意の環とし、 $n\geq 1$ を整数とし、 $\alpha \in R$ 1のn乗根の主値であり、次のように定義される： ^[¹^]

離散フーリエ変換はnタプルをマッピングする $(v_{0},\ldots ,v_{n-1})$ $R$ の要素を別のnタプルに $(f_{0},\ldots ,f_{n-1})$ 以下の式に従って、 $R$ の要素の数を決定します。

慣例として、タプル $(v_{0},\ldots ,v_{n-1})$ は時間領域にあると言われ、インデックス $jは$ 時間と呼ばれます。タプル $(f_{0},\ldots ,f_{n-1})$ は周波数領域にあると言われ、インデックス $kは$ 周波数と呼ばれます。タプル $(f_{0},\ldots ,f_{n-1})$ スペクトルとも呼ばれる $(v_{0},\ldots ,v_{n-1})$ この用語は、信号処理におけるフーリエ変換の応用から派生したものです。

$Rが$ 整域(体を含む)である場合、選択すれば十分である。 $\alpha$ 原始的なn乗根として、条件 ( 1 ) を次のように置き換えます: ^{[ 1 ]}

\alpha^k ≠ 1

のために

1\leq k<n

証拠

取る $\beta =\alpha ^{k}$ と $1\leq k<n$ 。以来 $\displaystyle \alpha ^{n}=1}$ 、 $\beta ^{n}=(\alpha ^{n})^{k}=1$ 与えるもの：

\beta ^{n}-1=(\beta -1)\left(\sum _{j=0}^{n-1}\beta ^{j}\right)=0

ここで合計は（1）と一致する。 $\alpha$ 統一の原始的な根源であり、 $\beta -1\neq 0$ $R$ は整域であるため、和はゼロでなければならない。∎

nが2のべき乗である場合には、別の簡単な条件が適用されます。( 1 )は次のように置き換えることができます。 $\displaystyle \alpha ^{n/2}=-1}$ [ ¹^]

逆

離散フーリエ変換の逆変換は次のように表されます。

どこ $1/n$ $はR$ における $n$ の乗法逆元です(この逆元が存在しない場合、DFT を逆変換することはできません)。

証拠

（２）を（ ３）の右辺に代入すると、

{\begin{aligned}&{\frac {1}{n}}\sum _{k=0}^{n-1}f_{k}\alpha ^{-jk}\\={}&{\frac {1}{n}}\sum _{k=0}^{n-1}\sum _{j'=0}^{n-1}v_{j'}\alpha ^{j'k}\alpha ^{-jk}\\={}&{\frac {1}{n}}\sum _{j'=0}^{n-1}v_{j'}\sum _{k=0}^{n-1}\alpha ^{(j'-j)k}.\end{aligned}}

これはまさに $v_{j}$ 、なぜなら $\sum _{k=0}^{n-1}\alpha ^{(j'-j)k}=0$ いつ $j'\neq j$ （１）により $k=j'-j$ ）、そして $\sum _{k=0}^{n-1}\alpha ^{(j'-j)k}=n$ いつ $j'=j$ ∎

マトリックス組成

離散フーリエ変換は線形演算子であるため、行列乗算によって記述できます。行列表記では、離散フーリエ変換は次のように表されます。

{\begin{bmatrix}f_{0}\\f_{1}\\\vdots \\f_{n-1}\end{bmatrix}}={\begin{bmatrix}1&1&1&\cdots &1\\1&\alpha &\alpha ^{2}&\cdots &\alpha ^{n-1}\\1&\alpha ^{2}&\alpha ^{4}&\cdots &\alpha ^{2(n-1)}\\\vdots &\vdots &\vdots &\ddots &\vdots \\1&\alpha ^{n-1}&\alpha ^{2(n-1)}&\cdots &\alpha ^{(n-1)(n-1)}\\\end{bmatrix}}{\begin{bmatrix}v_{0}\\v_{1}\\\vdots \\v_{n-1}\end{bmatrix}}.

この変換のための行列はDFT行列と呼ばれます。

同様に、逆フーリエ変換の行列表記は次のようになります。

{\begin{bmatrix}v_{0}\\v_{1}\\\vdots \\v_{n-1}\end{bmatrix}}={\frac {1}{n}}{\begin{bmatrix}1&1&1&\cdots &1\\1&\alpha ^{-1}&\alpha ^{-2}&\cdots &\alpha ^{-(n-1)}\\1&\alpha ^{-2}&\alpha ^{-4}&\cdots &\alpha ^{-2(n-1)}\\\vdots &\vdots &\vdots &\ddots &\vdots \\1&\alpha ^{-(n-1)}&\alpha ^{-2(n-1)}&\cdots &\alpha ^{-(n-1)(n-1)}\end{bmatrix}}{\begin{bmatrix}f_{0}\\f_{1}\\\vdots \\f_{n-1}\end{bmatrix}}.

多項式表現

$n$ タプルを識別することが便利な場合もあります $(v_{0},\ldots ,v_{n-1})$ 形式的な多項式を用いて

p_{v}(x)=v_{0}+v_{1}x+v_{2}x^{2}+\cdots +v_{n-1}x^{n-1}.\,

離散フーリエ変換の定義（ 2 ）における総和を書き出すと、次の式が得られる。

f_{k}=v_{0}+v_{1}\alpha ^{k}+v_{2}\alpha ^{2k}+\cdots +v_{n-1}\alpha ^{(n-1)k}.\,

これはつまり $f_{k}$ これは多項式の値です $p_{v}(x)$ のために $x=\alpha ^{k}$ つまり、

したがって、フーリエ変換は多項式の係数と値を関連付けるものと見なすことができます。係数は時間領域にあり、値は周波数領域にあります。ここで重要なのは、多項式が1の $n$ 乗根で評価されることであり、これはまさに次のべき乗です。 $\alpha$ 。

同様に、逆フーリエ変換の定義（3）は次のように記述できる。

と

p_{f}(x)=f_{0}+f_{1}x+f_{2}x^{2}+\cdots +f_{n-1}x^{n-1},

これはつまり

v_{j}={\frac {1}{n}}p_{f}(\alpha ^{-j}).

これを次のようにまとめることができます。 $p_{v}(x)$ は係数です $p_{f}(x)$ すると、 $p_{f}(x)$ は係数です $p_{v}(x)$ スカラー係数と並べ替えを除いて。^{[ 2 ]}

特別なケース

複素数

もし $F={\mathbb {C} }$ は複素数の体である、 $n$ 1のn乗根は、複素平面の単位円上の点として視覚化できます。この場合、通常はを取ります。

\alpha =e^{\frac {-2\pi i}{n}},

これにより、複素離散フーリエ変換の通常の公式が得られます。

f_{k}=\sum _{j=0}^{n-1}v_{j}e^{{\frac {-2\pi i}{n}}jk}.

複素数においては、DFTおよび逆DFTの式をスカラー因子を用いて正規化するのが一般的である。 ${\frac {1}{\sqrt {n}}}$ どちらの式でも、 $1$ DFTの式と ${\frac {1}{n}}$ 逆DFTの式において。この正規化により、DFT行列はユニタリ行列となる。 ${\sqrt {n}}$ 任意の分野では意味をなさない。

有限体

もし $F=\mathrm {GF} (q)$ は有限体であり、 $qは$ 素数のべき乗である。このとき、原始 $n$ 乗根の存在は自動的に $n が$ を割り切ることを意味する。 $q-1$ なぜなら、各要素の乗法位数は $F$ の乗法群のサイズを割り切る必要があるからである。 $q-1$ これは特に以下のことを保証します。 $n=\underbrace {1+1+\cdots +1} _{n\ {\rm {times}}}$ は可逆であるため、表記法は ${\frac {1}{n}}$ （３）は理にかなっている。

離散フーリエ変換の適用 $\mathrm {GF} (q)$ 符号理論において、リード・ソロモン符号を BCH符号に変換することは、このような変換である。このような変換は、例えば円分高速フーリエ変換などの適切な高速アルゴリズムを用いることで効率的に実行できる。

^n乗根を含まない多項式表現

仮定する $F=\mathrm {GF} (p)$ 。もし $p\nmid n$ 次のような場合もあるかもしれません。 $n\nmid p-1$ これは、 $n^{th}$ 統一の根源 $F$ フーリエ変換を同型写像と見なすことができる。 $\mathrm {F} [C_{n}]=\mathrm {F} [x]/(x^{n}-1)\cong \bigoplus _{i}\mathrm {F} [x]/(P_{i}(x))$ いくつかの多項式について $P_{i}(x)$ マシュケの定理に従って、写像は中国剰余定理によって与えられ、逆写像は多項式に対するベズーの恒等式を適用することによって与えられる。^{[ 3 ]}

$x^{n}-1=\prod _{d|n}\Phi _{d}(x)$ 円分多項式の積。因数分解 $\Phi _{d}(x)$ で $F[x]$ これは素イデアルの因数分解に相当する。 $(p)$ で $\mathrm {Z} [\zeta ]=\mathrm {Z} [x]/(\Phi _{d}(x))$ 我々は得る $g$ 多項式 $P_{1}\ldots P_{g}$ 学位 $f$ どこ $fg=\varphi (d)$ そして $f$ の順序は $p{\text{ mod }}d$ 。

上記のように、基底フィールドを拡張すると、 $\mathrm {GF} (q)$ 原始根、つまり分割体を見つけるために $x^{n}-1$ 。今 $x^{n}-1=\prod _{k}(x-\alpha ^{k})$ 要素 $\sum _{j=0}^{n-1}v_{j}x^{j}\in F[x]/(x^{n}-1)$ 地図 $\sum _{j=0}^{n-1}v_{j}x^{j}\mod (x-\alpha ^{k})\equiv \sum _{j=0}^{n-1}v_{j}(\alpha ^{k})^{j}$ 各 $k$ 。

pがnを割り切るとき

いつ $p|n$ 我々はまだ定義することができる $F_{p}$ -線形同型性は上記のとおりです。 $(x^{n}-1)=(x^{m}-1)^{p^{s}}$ どこ $n=mp^{s}$ そして $p\nmid m$ 。上記の因数分解を以下に適用します。 $x^{m}-1$ そして、分解を取得する $F[x]/(x^{n}-1)\cong \bigoplus _{i}F[x]/(P_{i}(x)^{p^{s}})$ 出現するモジュールは、既約ではなく、分解不可能である。

DFT行列の次数

仮定する $p\nmid n$ だから私たちは $n^{th}$ 統一の根源 $\alpha$ 。させて $A$ 上記のDFT行列は、要素がヴァンデルモンド行列である。 $A_{ij}=\alpha ^{ij}$ のために $0\leq i,j<n$ 思い出してください。 $\sum _{j=0}^{n-1}\alpha ^{(k-l)j}=n\delta _{k,l}$ もし $k=l$ の場合、すべてのエントリは 1 になります。 $k\neq l$ すると、公比が等しい等比数列が得られます。 $\alpha ^{k-l}$ すると、 ${\frac {1-\alpha ^{n(k-l)}}{1-\alpha ^{k-l}}}$ 。以来 $\alpha ^{n}=1$ 分子はゼロですが、 $k-l\neq 0$ つまり、分母はゼロではない。

まず二乗を計算し、 $(A^{2})_{ik}=\sum _{j=0}^{n-1}\alpha ^{j(i+k)}=n\delta _{i,-k}$ コンピューティング $A^{4}=(A^{2})^{2}$ 同様にデルタを単純化すると、次の式が得られます。 $(A^{4})_{ik}=n^{2}\delta _{i,k}$ 。したがって、 $A^{4}=n^{2}I_{n}$ そしてその順序は $4\cdot {\text{ord}}(n^{2})$ 。

DFT行列の正規化

複雑なケースに対応し、行列が正確に4次であることを保証するため、上記のDFT行列を正規化することができます。 $A$ と ${\frac {1}{\sqrt {n}}}$ ただし、 ${\sqrt {n}}$ 分割フィールドには存在しない可能性があります $F_{q}$ の $x^{n}-1$ 二次拡張を形成することができます $F_{q^{2}}\cong F_{q}[x]/(x^{2}-n)$ 平方根が存在する。次に、 $U={\frac {1}{\sqrt {n}}}A$ 、そして $U^{4}=I_{n}$ 。

単一性

仮定する $p\nmid n$ 有限体上でDFT行列がユニタリであるかどうかを問うことができる。行列の要素が $F_{q}$ そうすれば、必ず $q$ 完全な正方形であるか、または拡張します $F_{q^{2}}$ 2次の自己同型を定義するために $x\mapsto x^{q}$ 上記のDFT行列を考慮してください。 $A_{ij}=\alpha ^{ij}$ 。ご了承ください $A$ 対称である。共役変換と転置を行うと、次の式が得られる。 $A_{ij}^{*}=\alpha ^{qji}$ 。

$(AA^{*})_{ik}=\sum _{j=0}^{n-1}\alpha ^{j(i+qk)}=n\delta _{i,-qk}$

上記と同様の等比級数の議論により、 $n$ 正規化することで $U={\frac {1}{\sqrt {n}}}A$ そして $(UU^{*})_{ik}=\delta _{i,-qk}$ 。したがって $U$ ユニタリであるのは、 $q\equiv -1\,({\text{mod}}\,n)$ 。我々は $n^{th}$ 統一の根源、 $n|q^{2}-1$ これはつまり $q^{2}-1\equiv (q+1)(q-1)\equiv 0\,({\text{mod}}\,n)$ . 注記 $q$ 最初は完全な正方形ではなかったが、 $n|q-1$ など $q\equiv 1\,({\text{mod}}\,n)$ 。

例えば、 $p=3,n=5$ 拡張する必要がある $q^{2}=3^{4}$ 1の5乗根を求める。 $q=9\equiv -1\,({\text{mod}}\,5)$ 。

非例として、 $p=3,n=8$ 拡張する $F_{3^{2}}$ 1の8乗根を求める。 $q^{2}=9$ 、それで $q\equiv 3\,({\text{mod}}\,8)$ 、そしてこの場合 $q+1\not \equiv 0$ そして $q-1\not \equiv 0$ 。 $UU^{*}$ は恒等式の平方根なので、 $U$ 単一ではない。

DFT行列の固有値

いつ $p\nmid n$ 私たちには $n^{th}$ 統一の根源 $\alpha$ 分裂フィールドにおいて $F_{q}\cong F_{p}[x]/(x^{n}-1)$ 上記のDFT行列の特性多項式は、以下の範囲で分割されない可能性があることに注意してください。 $F_{q}$ DFT行列は4次です。さらに拡張する必要があるかもしれません。 $F_{q'}$ 、DFT行列の特性多項式の分割拡張であり、少なくとも1の4乗根を含む。 $a$ 乗法群の生成元は $F_{q'}$ すると、固有値は $\{\pm 1,\pm a^{(q'-1)/4}\}$ 複素数の場合と全く同様に、それらは非負の多重度で出現する。

数論的変換

数論的変換 (NTT) ^{[ 4 ]}は、離散フーリエ変換を特殊化することによって得られます。 $F={\mathbb {Z} }/p$ 、素数 $p$ を法とする整数。これは有限体であり、 $n が$ を割り切るときはいつでも原始 $n$ 乗根が存在する。 $p-1$ ということで、 $p=\xi n+1$ 正の整数 $ξ$ に対して、具体的には、 $\omega$ 原始的である $(p-1)$ 1のn乗根、次に1の $n$ 乗根 $\alpha$ 見つけることができる $\alpha =\omega ^{\xi }$ 。

例えば $p=5$ 、 $\alpha =2$

{\begin{aligned}2^{1}&=2{\pmod {5}}\\2^{2}&=4{\pmod {5}}\\2^{3}&=3{\pmod {5}}\\2^{4}&=1{\pmod {5}}\end{aligned}}

いつ $N=4$

{\begin{bmatrix}F(0)\\F(1)\\F(2)\\F(3)\end{bmatrix}}={\begin{bmatrix}1&1&1&1\\1&2&4&3\\1&4&1&4\\1&3&4&2\end{bmatrix}}{\begin{bmatrix}f(0)\\f(1)\\f(2)\\f(3)\end{bmatrix}}

数論的変換は環において意味を持つかもしれない $\mathbb {Z} /m$ $法m$ が素数でない場合でも、 $n$ 位の主根が存在する限り、この変換は有効です。Schönhage –Strassen アルゴリズムで使用される Fermat 数変換 ( $m = 2 k +1$ )や Mersenne 数変換^[⁵^] ( $m$ $= 2$ $k$ $-$ $1$ ) などの数論的変換の特殊なケースでは、合成法が使用されます。

一般的に、もし ${\textstyle m=\prod _{i}p_{i}^{e_{i}}}$ そうすれば、 ${\textstyle n^{th}}$ 原始関数を見つけることによる、 $m$ を法とする 1 の根 ${\textstyle n^{th}}$ 団結の根源 $g_{i}$ モジュール ${\textstyle p_{i}^{e_{i}}}$ タプルを生成する ${\textstyle g=\left(g_{i}\right)_{i}\in \prod _{i}\left(\mathbb {Z} /p_{i}^{e_{i}}\mathbb {Z} \right)^{\ast }}$ . の原像 $g$ 中国剰余定理の下では同型は ${\textstyle n^{th}}$ 統一の根源 ${\textstyle \alpha }$ そのため ${\textstyle \alpha ^{n/2}=-1\mod m}$ これにより、上記の合計条件が満たされることが保証されます。 ${\textstyle n|\varphi (p_{i}^{e_{i}})}$ 各 $i$ 、どこ $\varphi$ はオイラーのトーシェント関数である。^{[ 6 ]}

高速フーリエ変換はNTTに適合させることができ、整数演算のみで実装できます。^{[ 7 ]}ソリナス素数などのmの選択肢 $2^{64}-2^{32}+1$ これらは、除算演算を必要としないため、コンピュータ上で計算するのがさらに簡単です。^{[ 8 ]}

離散重み変換

離散重み付き変換（DWT）は、任意のリング上の離散フーリエ変換の変形であり、入力を要素ごとに重みベクトルで乗算して変換する前に重み付けし、次に結果を別のベクトルで重み付けします。^{[ 9 ]}無理数基底離散重み付き変換は、この特殊なケースです。

不動産

複素離散フーリエ変換（DFT）の重要な属性のほとんど、例えば逆変換、畳み込み定理、そしてほとんどの高速フーリエ変換（FFT）アルゴリズムなどは、変換の核が1の主根であるという性質のみに依存します。これらの性質は、任意の環上でも同様の証明で成り立ちます。体の場合、この類推は、1つの要素を持つ体によって形式化できます。これは、原始n乗根を持つ任意の体を、拡大体上の代数とみなすことで実現できます。 $\mathbf {F} _{1^{n}}.$

特に、 $O(n\log n)$ NTTを計算するための高速フーリエ変換アルゴリズムと畳み込み定理を組み合わせることで、数論的変換は整数列の正確な畳み込みを効率的に計算する方法を提供する。複素DFTも同じタスクを実行できるが、有限精度浮動小数点演算における丸め誤差の影響を受けやすい。一方、NTTは正確に表現できる固定サイズの整数のみを扱うため、丸め誤差は発生しない。

高速アルゴリズム

「高速」アルゴリズム（FFTが DFTを計算する方法と同様）を実装する場合、変換長も合成数、例えば2のべき乗であることが望ましい場合が多い。しかし、WangとZhuのアルゴリズム^{[ 10 ]}のように、変換長係数に関係なく効率的な有限体用の特殊な高速フーリエ変換アルゴリズムも存在する。

参考文献

1 2 3 Martin Fürer、「より高速な整数乗算」、STOC 2007 Proceedings、pp. 57 – 66。セクション 2: 離散フーリエ変換。
↑ Lidl, R.; Pilz, G. (1999).応用抽象代数学（第2 版）. Wiley. pp. 217–219 . ISBN 0-387-98290-6。
↑「対称群のモジュラーDFT」。GitHub 。
↑ Agarwal, R.; Burrus, C. (1974年4月)「フェルマー数変換を用いた高速畳み込みとデジタルフィルタリングへの応用」IEEE Transactions on Acoustics, Speech, and Signal Processing . 22 (2): 87–97 . doi : 10.1109/TASSP.1974.1162555 . ISSN 0096-3518 .
↑ Rader, CM (1972 年 12 月). "メルセンヌ変換による離散畳み込み". IEEE Transactions on Computers . C-21 (12): 1269–1273 . doi : 10.1109/TC.1972.223497 . ISSN 0018-9340 . S2CID 1939809 .
↑ウォルターズ、ジャクソン; シルバーマン、トーマス。「ntt」。crates.io。2025年2月14日取得。
↑ Satriawan, Ardianto; Syafalni, Infall; Mareta, Rella; Anshori, Isa; Shalannanda, Wervyan; Barra, Aleams (2023). "数論変換の概念的レビューと実装に関する包括的なレビュー" . IEEE Access . 11 : 70288– 70316. doi : 10.1109/ACCESS.2023.3294446 .
↑ Craig-Wood, Nick. "Integer DWTs mod 2 ⁶⁴ -2 ³² +1" . www.craig-wood.com .
↑クランドール、リチャード；フェイギン、バリー (1994)、「離散重み付き変換と大整数演算」(PDF)、Mathematics of Computation、62 (205): 305–324、doi : 10.2307/2153411、JSTOR 2153411
↑ Yao Wang ; Xuelong Zhu (1988). "有限体上のフーリエ変換の高速アルゴリズムとそのVLSI実装". IEEE Journal on Selected Areas in Communications . 6 (3): 572– 577. doi : 10.1109/49.1926 .

外部リンク

https://www.apfloat.org/ntt.html

[furer-1] 1 2 3 Martin Fürer、「より高速な整数乗算」、STOC 2007 Proceedings、pp. 57 – 66。セクション 2: 離散フーリエ変換。

[2] Lidl, R.; Pilz, G. (1999).応用抽象代数学（第2 版）. Wiley. pp. 217–219 . ISBN 0-387-98290-6。

[3] 「対称群のモジュラーDFT」。GitHub 。

[4] Agarwal, R.; Burrus, C. (1974年4月)「フェルマー数変換を用いた高速畳み込みとデジタルフィルタリングへの応用」IEEE Transactions on Acoustics, Speech, and Signal Processing . 22 (2): 87–97 . doi : 10.1109/TASSP.1974.1162555 . ISSN 0096-3518 .

[5] Rader, CM (1972 年 12 月). "メルセンヌ変換による離散畳み込み". IEEE Transactions on Computers . C-21 (12): 1269–1273 . doi : 10.1109/TC.1972.223497 . ISSN 0018-9340 . S2CID 1939809 .

[6] ウォルターズ、ジャクソン; シルバーマン、トーマス。「ntt」。crates.io。2025年2月14日取得。

[7] Satriawan, Ardianto; Syafalni, Infall; Mareta, Rella; Anshori, Isa; Shalannanda, Wervyan; Barra, Aleams (2023). "数論変換の概念的レビューと実装に関する包括的なレビュー" . IEEE Access . 11 : 70288– 70316. doi : 10.1109/ACCESS.2023.3294446 .

[8] Craig-Wood, Nick. "Integer DWTs mod 2 ⁶⁴ -2 ³² +1" . www.craig-wood.com .

[9] クランドール、リチャード；フェイギン、バリー (1994)、「離散重み付き変換と大整数演算」(PDF)、Mathematics of Computation、62 (205): 305–324、doi : 10.2307/2153411、JSTOR 2153411

[10] Yao Wang ; Xuelong Zhu (1988). "有限体上のフーリエ変換の高速アルゴリズムとそのVLSI実装". IEEE Journal on Selected Areas in Communications . 6 (3): 572– 577. doi : 10.1109/49.1926 .

[

[ 2 ]

[ 3 ]

[ 4 ]

[

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

意味

逆