تحويل فورييه المنفصل على حلقة

📅 آخر تحديث: ٢٩ يوليو ٢٠٢٦
✍️ نُشر في: ٢٩ يوليو ٢٠٢٦
📷 يحتوي على 146 صور
الموسوعة الحرة

في الرياضيات ، يُعمم تحويل فورييه المنفصل على حلقة تحويل فورييه المنفصل (DFT) لدالة تكون قيمها عادةً أعدادًا مركبة ، على حلقة عشوائية .

تعريف

ليكن R أي حلقة ، وليكنن≥1{\displaystyle n\geq 1}ليكن عددًا صحيحًا، وليكنα∈R{\displaystyle \alpha \in R}ليكن جذرًا رئيسيًا من الرتبة n للوحدة، معرفًا على النحو التالي: [ 1 ]

تحويل فورييه المنفصل يرسم خريطة لمجموعة من n عنصر(v0،...،vن-1){\displaystyle (v_{0},\ldots ,v_{n-1})}من عناصر R إلى مجموعة n أخرى(و0،...،ون-1){\displaystyle (f_{0},\ldots ,f_{n-1})}عناصر R وفقًا للصيغة التالية:

بحسب الاصطلاح، فإن المجموعة(v0،...،vن-1){\displaystyle (v_{0},\ldots ,v_{n-1})}يُقال إنها في المجال الزمني ويُطلق على الفهرس j اسم الزمن .(و0،...،ون-1){\displaystyle (f_{0},\ldots ,f_{n-1})}يُقال إنها تقع في مجال التردد، ويُطلق على الفهرس k اسم التردد .(و0،...،ون-1){\displaystyle (f_{0},\ldots ,f_{n-1})}ويُطلق عليه أيضًا اسم طيف(v0،...،vن-1){\displaystyle (v_{0},\ldots ,v_{n-1})}. هذا المصطلح مشتق من تطبيقات تحويلات فورييه في معالجة الإشارات .

إذا كانت R مجالًا تكامليًا (يشمل الحقول )، يكفي اختيارα{\displaystyle \alpha }كجذر أولي من الرتبة n للوحدة ، والذي يحل محل الشرط ( 1 ) بواسطة: [ 1 ]

αك≠1{\displaystyle \alpha ^{k}\neq 1}ل1≤ك<ن{\displaystyle 1\leq k<n}
دليل

يأخذβ=αك{\displaystyle \beta =\alpha ^{k}}مع1≤ك<ن{\displaystyle 1\leq k<n}. منذαن=1{\displaystyle \alpha ^{n}=1}،βن=(αن)ك=1{\displaystyle \beta ^{n}=(\alpha ^{n})^{k}=1}، مما يعطي:

βن-1=(β-1)(∑ج=0ن-1βج)=0{\displaystyle \beta ^{n}-1=(\beta -1)\left(\sum _{j=0}^{n-1}\beta ^{j}\right)=0}

حيث يتطابق المجموع مع ( 1 ). بما أنα{\displaystyle \alpha }هو جذر بدائي للوحدة،β-1≠0{\displaystyle \beta -1\neq 0}بما أن R مجال تكاملي، فإن المجموع يجب أن يكون صفرًا. ∎

ينطبق شرط بسيط آخر في حالة كون n قوة للعدد اثنين: يمكن استبدال ( 1 ) بـαن/2=-1{\displaystyle \alpha ^{n/2}=-1}[ 1 ]​

معكوس

يُعطى معكوس تحويل فورييه المنفصل على النحو التالي:

أين1/ن{\displaystyle 1/n}هو المعكوس الضربي لـ n في R (إذا لم يكن هذا المعكوس موجودًا، فلا يمكن عكس DFT).

دليل

بإدخال ( 2 ) في الطرف الأيمن من ( 3 )، نحصل على

1ن∑ك=0ن-1وكα-جك=1ن∑ك=0ن-1∑ج′=0ن-1vج′αج′كα-جك=1ن∑ج′=0ن-1vج′∑ك=0ن-1α(ج′-ج)ك.// ^ {j'k}\alpha ^{-jk}\\={}&{\frac {1}{n}}\sum _{j'=0}^{n-1}v_{j'}\sum _{k=0}^{n-1}\alpha ^{(j'-j)k}.\end{محاذاة}}}

هذا يساوي تمامًاvج{\displaystyle v_{j}}، لأن ∑ك=0ن-1α(ج′-ج)ك=0{\displaystyle \sum _{k=0}^{n-1}\alpha ^{(j'-j)k}=0}متىج′≠ج{\displaystyle j'\neq j}(بواسطة ( 1 ) معك=ج′-ج{\displaystyle k=j'-j})، و ∑ك=0ن-1α(ج′-ج)ك=ن{\displaystyle \sum _{k=0}^{n-1}\alpha ^{(j'-j)k}=n}متىج′=ج{\displaystyle j'=j}. ∎

تركيبة المصفوفة

بما أن تحويل فورييه المتقطع هو مؤثر خطي ، فإنه يمكن وصفه بضرب المصفوفات . وباستخدام ترميز المصفوفات، يُعبّر عن تحويل فورييه المتقطع كما يلي:

[و0و1⋮ون-1]=[111⋯11αα2⋯αن-11α2α4⋯α2(ن-1)⋮⋮⋮⋱⋮1αن-1α2(ن-1)⋯α(ن-1)(ن-1)][v0v1⋮vن-1].{\displaystyle {\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 .

Similarly, the matrix notation for the inverse Fourier transform is

[v0v1⋮vn−1]=1n[111⋯11α−1α−2⋯α−(n−1)1α−2α−4⋯α−2(n−1)⋮⋮⋮⋱⋮1α−(n−1)α−2(n−1)⋯α−(n−1)(n−1)][f0f1⋮fn−1].{\displaystyle {\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 \begin{bmatrix}f_{0}\\f_{1}\\\vdots \\f_{n-1}\end{bmatrix}}}

Polynomial formulation

Sometimes it is convenient to identify an n-tuple (v0,…,vn−1){\displaystyle (v_{0},\ldots ,v_{n-1})} with a formal polynomial

pv(x)=v0+v1x+v2x2+⋯+vn−1xn−1.{\displaystyle p_{v}(x)=v_{0}+v_{1}x+v_{2}x^{2}+\cdots +v_{n-1}x^{n-1}.\,}

By writing out the summation in the definition of the discrete Fourier transform (2), we obtain:

fk=v0+v1αk+v2α2k+⋯+vn−1α(n−1)k.{\displaystyle f_{k}=v_{0}+v_{1}\alpha ^{k}+v_{2}\alpha ^{2k}+\cdots +v_{n-1}\alpha ^{(n-1)k}.\,}

This means that fk{\displaystyle f_{k}} is just the value of the polynomial pv(x){\displaystyle p_{v}(x)} for x=αk{\displaystyle x=\alpha ^{k}}, i.e.,

The Fourier transform can therefore be seen to relate the coefficients and the values of a polynomial: the coefficients are in the time-domain, and the values are in the frequency domain. Here, of course, it is important that the polynomial is evaluated at the nth roots of unity, which are exactly the powers of α{\displaystyle \alpha }.

Similarly, the definition of the inverse Fourier transform (3) can be written:

With

pf(x)=f0+f1x+f2x2+⋯+fn−1xn−1,{\displaystyle p_{f}(x)=f_{0}+f_{1}x+f_{2}x^{2}+\cdots +f_{n-1}x^{n-1},}

this means that

vj=1npf(α−j).{\displaystyle v_{j}={\frac {1}{n}}p_{f}(\alpha ^{-j}).}

We can summarize this as follows: if the values of pv(x){\displaystyle p_{v}(x)} are the coefficients of pf(x){\displaystyle p_{f}(x)}, then the values of pf(x){\displaystyle p_{f}(x)} are the coefficients of pv(x){\displaystyle p_{v}(x)}, up to a scalar factor and reordering.[2]

Special cases

Complex numbers

If F=C{\displaystyle F={\mathbb {C} }} is the field of complex numbers, then the n{\displaystyle n}th roots of unity can be visualized as points on the unit circle of the complex plane. In this case, one usually takes

α=e−2πin,{\displaystyle \alpha =e^{\frac {-2\pi i}{n}},}

which yields the usual formula for the complex discrete Fourier transform:

fk=∑j=0n−1vje−2πinjk.{\displaystyle f_{k}=\sum _{j=0}^{n-1}v_{j}e^{{\frac {-2\pi i}{n}}jk}.}

Over the complex numbers, it is often customary to normalize the formulas for the DFT and inverse DFT by using the scalar factor 1n{\displaystyle {\frac {1}{\sqrt {n}}}} in both formulas, rather than 1{\displaystyle 1} in the formula for the DFT and 1n{\displaystyle {\frac {1}{n}}} in the formula for the inverse DFT. With this normalization, the DFT matrix is then unitary. Note that n{\displaystyle {\sqrt {n}}} does not make sense in an arbitrary field.

Finite fields

If F=GF(q){\displaystyle F=\mathrm {GF} (q)} is a finite field, where q is a prime power, then the existence of a primitive nth root automatically implies that ndividesq−1{\displaystyle q-1}, because the multiplicative order of each element must divide the size of the multiplicative group of F, which is q−1{\displaystyle q-1}. This in particular ensures that n=1+1+⋯+1⏟n times{\displaystyle n=\underbrace {1+1+\cdots +1} _{n\ {\rm {times}}}} is invertible, so that the notation 1n{\displaystyle {\frac {1}{n}}} in (3) makes sense.

An application of the discrete Fourier transform over GF(q){\displaystyle \mathrm {GF} (q)} is the reduction of Reed–Solomon codes to BCH codes in coding theory. Such transform can be carried out efficiently with proper fast algorithms, for example, cyclotomic fast Fourier transform.

Polynomial formulation without nth root

Suppose F=GF(p){\displaystyle F=\mathrm {GF} (p)}. If p∤n{\displaystyle p\nmid n}, it may be the case that n∤p−1{\displaystyle n\nmid p-1}هذا يعني أننا لا نستطيع العثور علىنتح{\displaystyle n^{th}}أصل الوحدة فيF{\displaystyle F}يمكننا اعتبار تحويل فورييه بمثابة تماثلF[جن]=F[x]/(xن-1)≅⨁أناF[x]/(Pأنا(x)){\displaystyle \mathrm {F} [C_{n}]=\mathrm {F} [x]/(x^{n}-1)\cong \bigoplus _{i}\mathrm {F} [x]/(P_{i}(x))}بالنسبة لبعض كثيرات الحدودPأنا(x){\displaystyle P_{i}(x)}، وفقًا لنظرية ماشكه . تُعطى الدالة بواسطة نظرية الباقي الصينية ، ويُعطى معكوسها بتطبيق متطابقة بيزو لكثيرات الحدود. [ 3 ]

xن-1=∏د|نΦد(x){\displaystyle x^{n}-1=\prod _{d|n}\Phi _{d}(x)}، ناتج ضرب كثيرات الحدود الدائرية. التحليل إلى عواملΦد(x){\displaystyle \Phi _{d}(x)}فيF[x]{\displaystyle F[x]}يكافئ تحليل المثالي الأولي(ص){\displaystyle (p)}فيZ[ζ]=Z[x]/(Φد(x)){\displaystyle \mathrm {Z} [\zeta ]=\mathrm {Z} [x]/(\Phi _{d}(x))}نحصل علىز{\displaystyle g}كثيرات الحدودP1...Pز{\displaystyle P_{1}\ldots P_{g}}درجة علميةو{\displaystyle f}أينوز=φ(د){\displaystyle fg=\varphi (d)}وو{\displaystyle f}هو ترتيبص مود د{\displaystyle p{\text{ mod }}d}.

كما ذكرنا سابقاً، يمكننا توسيع الحقل الأساسي إلىجيF(q){\displaystyle \mathrm {GF} (q)}من أجل إيجاد جذر أولي، أي حقل تقسيم لـxن-1{\displaystyle x^{n}-1}. الآنxن-1=∏ك(x-αك){\displaystyle x^{n}-1=\prod _{k}(x-\alpha ^{k})}، لذلك عنصر∑ج=0ن-1vجxج∈F[x]/(xن-1){\displaystyle \sum _{j=0}^{n-1}v_{j}x^{j}\in F[x]/(x^{n}-1)}خرائط إلى∑ج=0ن-1vجxجمود(x-αك)≡∑ج=0ن-1vج(αك)ج{\displaystyle \sum _{j=0}^{n-1}v_{j}x^{j}\mod (x-\alpha ^{k})\equiv \sum _{j=0}^{n-1}v_{j}(\alpha ^{k})^{j}}لكلك{\displaystyle k}.

عندما يقسم p عدد n

متىص|ن{\displaystyle p|n}، لا يزال بإمكاننا تعريفFص{\displaystyle F_{p}}التشاكل الخطي كما سبق. لاحظ أن(xن-1)=(xم-1)صs{\displaystyle (x^{n}-1)=(x^{m}-1)^{p^{s}}}أينن=مصs{\displaystyle n=mp^{s}}وص∤م{\displaystyle p\nmid m}نطبق التحليل المذكور أعلاه علىxم-1{\displaystyle x^{m}-1}والآن احصل على التفكيكF[x]/(xن-1)≅⨁أناF[x]/(Pأنا(x)صs){\displaystyle F[x]/(x^{n}-1)\cong \bigoplus _{i}F[x]/(P_{i}(x)^{p^{s}})}أصبحت الوحدات النمطية التي تحدث الآن غير قابلة للتحليل بدلاً من كونها غير قابلة للاختزال.

رتبة مصفوفة DFT

يفترضص∤ن{\displaystyle p\nmid n}لذا لدينانتح{\displaystyle n^{th}}أصل الوحدةα{\displaystyle \alpha }. يتركأ{\displaystyle A}لتكن مصفوفة DFT المذكورة أعلاه، مصفوفة فاندرموند ذات عناصرأأناج=αأناج{\displaystyle A_{ij}=\alpha ^{ij}}ل0≤أنا،ج<ن{\displaystyle 0\leq i,j<n}تذكر أن∑ج=0ن-1α(ك-ل)ج=ندلتاك،ل{\displaystyle \sum _{j=0}^{n-1}\alpha ^{(k-l)j}=n\delta _{k,l}}منذ ذلك الحينك=ل{\displaystyle k=l}إذا كان ، فإن كل مدخل يساوي 1.ك≠ل{\displaystyle k\neq l}إذن لدينا متسلسلة هندسية بنسبة مشتركةαك-ل{\displaystyle \alpha ^{k-l}}وهكذا نحصل1-αن(ك-ل)1-αك-ل{\displaystyle {\frac {1-\alpha ^{n(k-l)}}{1-\alpha ^{k-l}}}}. منذαن=1{\displaystyle \alpha ^{n}=1}البسط يساوي صفرًا، ولكنك-ل≠0{\displaystyle k-l\neq 0}إذن المقام غير صفري.

أولاً، حساب المربع،(أ2)أناك=∑ج=0ن-1αج(أنا+ك)=ندلتاأنا،-ك{\displaystyle (A^{2})_{ik}=\sum _{j=0}^{n-1}\alpha ^{j(i+k)}=n\delta _{i,-k}}الحوسبةأ4=(أ2)2{\displaystyle A^{4}=(A^{2})^{2}}وبالمثل، وبتبسيط دلتا، نحصل على(أ4)أناك=ن2دلتاأنا،ك{\displaystyle (A^{4})_{ik}=n^{2}\delta _{i,k}}. هكذا،أ4=ن2أنان{\displaystyle A^{4}=n^{2}I_{n}}والترتيب هو4⋅طلب(ن2){\displaystyle 4\cdot {\text{ord}}(n^{2})}.

تطبيع مصفوفة DFT

من أجل التوافق مع الحالة المعقدة وضمان أن تكون المصفوفة من الرتبة الرابعة بالضبط، يمكننا تطبيع مصفوفة DFT المذكورة أعلاهأ{\displaystyle A}مع1ن{\displaystyle {\frac {1}{\sqrt {n}}}}لاحظ أنه على الرغم من ذلكن{\displaystyle {\sqrt {n}}}قد لا يكون موجودًا في حقل التقسيمFq{\displaystyle F_{q}}لxن-1{\displaystyle x^{n}-1}، يمكننا تشكيل امتداد تربيعيFq2≅Fq[x]/(x2-ن){\displaystyle F_{q^{2}}\cong F_{q}[x]/(x^{2}-n)}حيث يوجد الجذر التربيعي. يمكننا حينها أن نضعيو=1نأ{\displaystyle U={\frac {1}{\sqrt {n}}}A}، ويو4=أنان{\displaystyle U^{4}=I_{n}}.

الوحدة

يفترضص∤ن{\displaystyle p\nmid n}يمكن للمرء أن يسأل عما إذا كانت مصفوفة تحويل فورييه المنفصل (DFT) وحدوية على حقل منتهٍ . إذا كانت عناصر المصفوفة علىFq{\displaystyle F_{q}}ثم يجب التأكدq{\displaystyle q}مربع كامل أو يمتد إلىFq2{\displaystyle F_{q^{2}}}من أجل تعريف التشاكل الذاتي من الرتبة الثانيةx↦xq{\displaystyle x\mapsto x^{q}}انظر إلى مصفوفة DFT المذكورة أعلاهأأناج=αأناج{\displaystyle A_{ij}=\alpha ^{ij}}. لاحظ أنأ{\displaystyle A}متناظرة. وبإجراء المرافقة والنقل، نحصل علىأأناج*=αqجأنا{\displaystyle A_{ij}^{*}=\alpha ^{qji}}.

(أأ*)أناك=∑ج=0ن-1αج(أنا+qك)=ندلتاأنا،-qك{\displaystyle (AA^{*})_{ik}=\sum _{j=0}^{n-1}\alpha ^{j(i+qk)}=n\delta _{i,-qk}}

باستخدام حجة مماثلة للمتسلسلة الهندسية كما في الأعلى. يمكننا حذفن{\displaystyle n}عن طريق التطبيع بحيثيو=1نأ{\displaystyle U={\frac {1}{\sqrt {n}}}A}و(يويو*)أناك=دلتاأنا،-qك{\displaystyle (UU^{*})_{ik}=\delta _{i,-qk}}. هكذايو{\displaystyle U}تكون موحدة إذا وفقط إذاq≡-1(مودن){\displaystyle q\equiv -1\,({\text{mod}}\,n)}تذكر أنه بما أن لدينانتح{\displaystyle n^{th}}أصل الوحدة،ن|q2-1{\displaystyle n|q^{2}-1}وهذا يعني أنq2-1≡(q+1)(q-1)≡0(مودن){\displaystyle q^{2}-1\equiv (q+1)(q-1)\equiv 0\,({\text{mod}}\,n)}ملاحظة إذاq{\displaystyle q}لم يكن مربعًا مثاليًا في البداية، إذنن|q-1{\displaystyle n|q-1}وهكذاq≡1(مودن){\displaystyle q\equiv 1\,({\text{mod}}\,n)}.

على سبيل المثال، عندماص=3،ن=5{\displaystyle p=3,n=5}نحتاج إلى التوسع إلىq2=34{\displaystyle q^{2}=3^{4}}للحصول على الجذر الخامس للوحدة.q=9≡-1(مود5){\displaystyle q=9\equiv -1\,({\text{mod}}\,5)}.

على سبيل المثال لا الحصر، عندماص=3،ن=8{\displaystyle p=3,n=8}نمتد إلىF32{\displaystyle F_{3^{2}}}للحصول على الجذر الثامن للوحدة.q2=9{\displaystyle q^{2}=9}، لذاq≡3(مود8){\displaystyle q\equiv 3\,({\text{mod}}\,8)}وفي هذه الحالةq+1≢0{\displaystyle q+1\not \equiv 0}وq-1≢0{\displaystyle q-1\not \equiv 0}.يويو*{\displaystyle UU^{*}}هو الجذر التربيعي للوحدة، لذايو{\displaystyle U}ليس نظامًا وحدويًا.

القيم الذاتية لمصفوفة DFT

متىص∤ن{\displaystyle p\nmid n}لدينانتح{\displaystyle n^{th}}أصل الوحدةα{\displaystyle \alpha }في مجال التقسيمFq≅Fص[x]/(xن-1){\displaystyle F_{q}\cong F_{p}[x]/(x^{n}-1)}لاحظ أن متعددة الحدود المميزة لمصفوفة DFT المذكورة أعلاه قد لا تنقسم علىFq{\displaystyle F_{q}}مصفوفة DFT من الرتبة الرابعة. قد نحتاج إلى توسيع إضافي.Fq′{\displaystyle F_{q'}}، وهو امتداد التقسيم لكثير الحدود المميز لمصفوفة DFT، والذي يحتوي على الأقل على أربعة جذور للوحدة. إذاأ{\displaystyle a}هو مولد المجموعة الضربية لـFq′{\displaystyle F_{q'}}إذن، القيم الذاتية هي{±1،±أ(q′-1)/4}{\displaystyle \{\pm 1,\pm a^{(q'-1)/4}\}}، على غرار الحالة المركبة تمامًا. تحدث هذه الحالات بتعدد غير سالب.

التحويل النظري العددي

يتم الحصول على التحويل النظري العددي (NTT) [ 4 ] عن طريق تخصيص تحويل فورييه المنفصل إلىF=Z/ص{\displaystyle F={\mathbb {Z} }/p}، الأعداد الصحيحة بتردد عدد أولي p . هذا حقل منتهٍ ، وتوجد جذور الوحدة الأولية من الرتبة n كلما قسم n علىص-1{\displaystyle p-1}لذلك لديناص=ξن+1{\displaystyle p=\xi n+1}لعدد صحيح موجب ξ . تحديدًا، ليكنω{\displaystyle \omega }كن بدائيًا(ص-1){\displaystyle (p-1)}الجذر النوني للوحدة، ثم الجذر النوني للوحدةα{\displaystyle \alpha }يمكن العثور عليها عن طريق السماحα=ωξ{\displaystyle \alpha =\omega ^{\xi }}.

مثال علىص=5{\displaystyle p=5}،α=2{\displaystyle \alpha =2}

21=2(مود5)22=4(مود5)23=3(مود5)24=1(مود5){\displaystyle {\begin{aligned}2^{1}&=2{\pmod {5}}\\2^{2}&=4{\pmod {5}}\\2^{3}&=3{\pmod {5}}\\2^{4}&=1{\pmod {5}}\end{aligned}}}

متىشمال=4{\displaystyle N=4}

[F(0)F(1)F(2)F(3)]=[1111124314141342][و(0)و(1)و(2)و(3)]{\displaystyle {\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}}}

قد يكون للتحويل النظري العددي معنى في الحلقةZ/م{\displaystyle \mathbb {Z} /m}حتى عندما لا يكون المعامل m أوليًا، بشرط وجود جذر رئيسي من الرتبة n . تستخدم حالات خاصة من التحويلات النظرية للأعداد، مثل تحويل فيرما العددي ( m = 2k + 1 )، المستخدم في خوارزمية شونهاج-ستراسن ، أو تحويل ميرسين العددي [ 5 ] ( m = 2k - 1   )، معاملًا مركبًا.

بشكل عام، إذام=∏أناصأناهـأنا{\textstyle m=\prod _{i}p_{i}^{e_{i}}}عندها قد يجد المرءنتح{\textstyle n^{th}}جذر الوحدة modulo m عن طريق إيجاد العناصر الأوليةنتح{\textstyle n^{th}}جذور الوحدةزأنا{\displaystyle g_{i}}مودصأناهـأنا{\textstyle p_{i}^{e_{i}}}، مما ينتج عنه مجموعةز=(زأنا)أنا∈∏أنا(Z/صأناهـأناZ)*{\textstyle g=\left(g_{i}\right)_{i}\in \prod _{i}\left(\mathbb {Z} /p_{i}^{e_{i}}\mathbb {Z} \right)^{\ast }}الصورة الأصلية لـز{\displaystyle g}بموجب نظرية الباقي الصينية، فإن التشاكل هونتح{\textstyle n^{th}}أصل الوحدةα{\textstyle \alpha }بحيثαن/2=-1مودم{\textstyle \alpha ^{n/2}=-1\mod m}وهذا يضمن استيفاء شروط الجمع المذكورة أعلاه. يجب أن يكون لدينا ذلكن|φ(صأناهـأنا){\textstyle n|\varphi (p_{i}^{e_{i}})}لكلأنا{\displaystyle i}، أينφ{\displaystyle \varphi }هي دالة أويلر . [ 6 ]

يمكن تكييف تحويل فورييه السريع مع NTT وتنفيذه باستخدام عمليات الأعداد الصحيحة فقط. [ 7 ] بعض الخيارات لـ m مثل عدد سولينس الأولي264-232+1{\displaystyle 2^{64}-2^{32}+1}يسهل حسابها على أجهزة الكمبيوتر لأنها لا تتطلب عملية قسمة للاختزال. [ 8 ]

التحويل الموزون المنفصل

التحويل الموزون المنفصل (DWT) هو شكل من أشكال تحويل فورييه المنفصل على حلقات عشوائية، ويتضمن ترجيح المدخلات قبل تحويلها بضرب كل عنصر في متجه وزن، ثم ترجيح النتيجة بمتجه آخر. [ 9 ] يُعد التحويل الموزون المنفصل ذو الأساس غير النسبي حالة خاصة من هذا التحويل.

ملكيات

تعتمد معظم الخصائص المهمة لتحويل فورييه المنفصل المعقد ، بما في ذلك التحويل العكسي، ونظرية الالتفاف ، ومعظم خوارزميات تحويل فورييه السريع (FFT)، فقط على خاصية أن نواة التحويل هي جذر رئيسي للوحدة. وتتحقق هذه الخصائص أيضًا، مع براهين متطابقة، على أي حلقات. في حالة الحقول، يمكن صياغة هذا التشابه رسميًا بواسطة الحقل ذي العنصر الواحد ، مع اعتبار أي حقل ذي جذر أولي من الرتبة n للوحدة بمثابة جبر على حقل التمديد.F1ن.{\displaystyle \mathbf {F} _{1^{n}}.}

وعلى وجه الخصوص، مدى قابلية تطبيقيا(نسجل⁡ن){\displaystyle O(n\log n)}تُتيح خوارزميات تحويل فورييه السريع لحساب تحويل نظرية الأعداد (NTT)، بالإضافة إلى نظرية الالتفاف، طريقةً فعّالةً لحساب الالتفافات الدقيقة لمتتاليات الأعداد الصحيحة. في حين أن تحويل فورييه المنفصل المركب (DFT) قادر على أداء المهمة نفسها، إلا أنه عُرضة لخطأ التقريب في حسابات الفاصلة العائمة ذات الدقة المحدودة ؛ أما تحويل نظرية الأعداد (NTT) فلا يُعاني من خطأ التقريب لأنه يتعامل فقط مع أعداد صحيحة ذات حجم ثابت يُمكن تمثيلها بدقة.

خوارزميات سريعة

لتنفيذ خوارزمية "سريعة" (على غرار كيفية حساب تحويل فورييه السريع لتحويل فورييه المنفصل )، يُفضّل غالبًا أن يكون طول التحويل مُركّبًا بدرجة كبيرة، مثل أن يكون قوة للعدد اثنين . مع ذلك، توجد خوارزميات متخصصة لتحويل فورييه السريع للحقول المنتهية، مثل خوارزمية وانغ وتشو [ 10 ]، والتي تتسم بالكفاءة بغض النظر عن عوامل طول التحويل.

انظر أيضاً

مراجع

  1. 1 2 3 مارتن فورر، " ضرب الأعداد الصحيحة بشكل أسرع "، وقائع STOC 2007، ص 57-66 . القسم 2: تحويل فورييه المنفصل.
  2. ↑ ليدل، ر.؛ بيلز، ج. (1999). الجبر المجرد التطبيقي (  الطبعة الثانية). وايلي. ص 217-219 . ISBN  0-387-98290-6.
  3. ↑ "تحويل فورييه المنفصل المعياري للمجموعة المتناظرة" . GitHub .
  4. ↑ أغاروال، ر.؛ بوروس، س. (أبريل 1974). "الالتفاف السريع باستخدام تحويلات عدد فيرما مع تطبيقات في الترشيح الرقمي". معاملات IEEE في الصوتيات والكلام ومعالجة الإشارات . 22 (2): 87-97 . doi : 10.1109/TASSP.1974.1162555 . ISSN 0096-3518 . 
  5. ↑ رادر، سي إم (ديسمبر 1972). "الالتفافات المنفصلة باستخدام تحويلات ميرسين". معاملات IEEE في الحوسبة . C-21 (12): 1269-1273 . doi : 10.1109/TC.1972.223497 . ISSN 0018-9340 . S2CID 1939809 .  
  6. ↑ والترز، جاكسون؛ سيلفرمان، توماس. "ntt" . crates.io . تم ​​الاسترجاع في 14 فبراير 2025 .
  7. ↑ ساترياوان، أرديانتو؛ سيافالني، إنفال؛ ماريتا، ريلا؛ أنشوري، عيسى؛ شالاناندا، ويرفيان؛ بارا، أليامز (2023). "مراجعة مفاهيمية حول التحويل النظري للأعداد ومراجعة شاملة لتطبيقاته" . IEEE Access . 11 : 70288–70316 . doi : 10.1109/ACCESS.2023.3294446 .
  8. ↑ كريج وود، نيك. "تحويلات المويجات المنفصلة للأعداد الصحيحة modulo 2 64 -2 32 +1" . www.craig-wood.com .
  9. ↑ كراندال، ريتشارد؛ فاجين، باري (1994)، "التحويلات الموزونة المنفصلة والحسابات ذات الأعداد الصحيحة الكبيرة" (ملف PDF) ، رياضيات الحساب ، 62 (205): 305-324 ، doi : 10.2307/2153411 ، JSTOR 2153411 
  10. ↑ ياو وانغ ؛ شولونغ تشو (1988). "خوارزمية سريعة لتحويل فورييه على الحقول المنتهية وتنفيذها بتقنية VLSI". مجلة IEEE للمجالات المختارة في الاتصالات . 6 (3): 572-577 . doi : 10.1109/49.1926 .