تحويل هادامارد

يُعد تحويل هادامارد ( المعروف أيضًا باسم تحويل والش-هادامارد ، أو تحويل هادامارد-رادماخر-والش ، أو تحويل والش ، أو تحويل والش-فورييه ) مثالًا على فئة معممة من تحويلات فورييه . وهو يُجري عملية خطية متعامدة ومتناظرة وانعكاسية على مجموعة من 2 ^ ^m عدد .

يمكن اعتبار تحويل هادامارد مبنيًا من تحويلات فورييه منفصلة (DFTs) بحجم 2، وهو في الواقع مكافئ لتحويل فورييه منفصل متعدد الأبعاد بحجم 2 × 2 × ⋯ × 2 × 2. [ ^{2 ] يقوم} بتحليل متجه إدخال عشوائي إلى تراكب لدوال والش .

وقد سميت هذه التحويلة نسبة إلى عالم الرياضيات الفرنسي جاك هادامارد ( بالفرنسية: [ adamaʁ ] )، وعالم الرياضيات الألماني الأمريكي هانز رادماخر ، وعالم الرياضيات الأمريكي جوزيف ل. والش .

تحويل هادامارد H_{_m} هو مصفوفة من الرتبة 2^{^m}  ×  2^{^m} ، وهي مصفوفة هادامارد (مُقاسة بمعامل توحيد)، تُحوّل 2^{^m} عددًا حقيقيًا x _{_n} إلى 2^{^m} عددًا حقيقيًا x_{_k} . يُمكن تعريف تحويل هادامارد بطريقتين: إما بشكل تكراري ، أو باستخدام التمثيل الثنائي ( الأساس -2) للمؤشرين n و k .

بشكل متكرر، نُعرّف تحويل هادامارد 1  ×  1 H ₀ من خلال المتطابقة H ₀ = 1، ثم نُعرّف H _m لـ m  >  0 من خلال: $${\displaystyle H_{m}={\frac {1}{2^{m/2}}}{\begin{pmatrix}H_{m-1}&H_{m-1}\\H_{m-1}&-H_{m-1}\end{pmatrix}}}$$ حيث أن القسمة على 2 ^م/2 هي عملية توحيد يتم حذفها أحيانًا.

بالنسبة لـ m  >  1، يمكننا أيضًا تعريف H _m على النحو التالي: $${\displaystyle H_{m}=H_{1}\otimes H_{m-1}}$$ أين${\displaystyle \otimes }$يمثل هذا حاصل ضرب كرونكر . وبالتالي، باستثناء عامل التطبيع هذا، تتكون مصفوفات هادامارد بالكامل من 1 و -1.

بصورة مكافئة، يمكننا تعريف مصفوفة هادامارد من خلال العنصر ( k , n ) الخاص بها عن طريق كتابة $${\displaystyle {\begin{aligned}k&=\sum _{i=0}^{m-1}{k_{i}2^{i}}=k_{m-1}2^{m-1}+k_{m-2}2^{m-2}+\dots +k_{1}2+k_{0}\\n&=\sum _{i=0}^{m-1}{n_{i}2^{i}}=n_{m-1}2^{m-1}+n_{m-2}2^{m-2}+\dots +n_{1}2+n_{0}\end{aligned}}}$$

حيث يمثل k _j و n _j عنصري البت (0 أو 1) للمتغيرين k و n على التوالي. لاحظ أنه بالنسبة للعنصر الموجود في الزاوية العلوية اليسرى، فإننا نُعرّف ما يلي:${\displaystyle k=n=0}$في هذه الحالة، لدينا: $${\displaystyle (H_{m})_{k,n}={\frac {1}{2^{m/2}}}(-1)^{\sum _{j}k_{j}n_{j}}}$$

هذا هو بالضبط متعدد الأبعاد${\textstyle 2\times 2\times \cdots \times 2\times 2}$DFT، مُعَيَّر ليكون أحاديًا ، إذا تم اعتبار المدخلات والمخرجات كمصفوفات متعددة الأبعاد مفهرسة بواسطة n _j و k _j على التوالي.

فيما يلي بعض الأمثلة على مصفوفات هادامارد. $${\displaystyle {\begin{aligned}H_{0}&=+{\begin{pmatrix}1\end{pmatrix}}\\[5pt]H_{1}&={\frac {1}{\sqrt {2}}}\left({\begin{array}{rr}1&1\\1&-1\end{array}}\right)\\[5pt]H_{2}&={\frac {1}{2}}\left({\begin{array}{rrrr}1&1&1&1\\1&-1&1&-1\\1&1&-1&-1\\1&-1&-1&1\end{array}}\right)\\[5pt]H_{3}&={\frac {1}{2^{3/2}}}\left({\begin{array}{rrrrrrrr}1&1&1&1&1&1&1&1\\1&-1&1&-1&1&-1&1&-1\\1&1&-1&-1&1&1&-1&-1\\1&-1&-1&1&1&-1&-1&1\\1&1&1&1&-1&-1&-1&-1\\1&-1&1&-1&-1&1&-1&1\\1&1&-1&-1&-1&-1&1&1\\1&-1&-1&1&-1&1&1&-1\end{array}}\right)\\[5pt](H_{n})_{i,j}&={\frac {1}{2^{n/2}}}(-1)^{i\cdot j}\end{aligned}}}$$ أين${\displaystyle i\cdot j}$هو حاصل الضرب النقطي الثنائي للتمثيلات الثنائية للعددين i و j. على سبيل المثال، إذا${\textstyle n\;\geq \;2}$، ثم$${\displaystyle (H_{n})_{3,2}\;=\;(-1)^{3\cdot 2}\;=\;(-1)^{(1,1)\cdot (1,0)}\;=\;(-1)^{1+0}\;=\;(-1)^{1}\;=\;-1}$$، بالتوافق مع ما سبق (مع تجاهل الثابت الإجمالي). لاحظ أن العنصر الأول في الصف الأول والعمود الأول من المصفوفة يُرمز إليه بـ${\textstyle (H_{n})_{0,0}}$.

H ₁ هو بالضبط تحويل فورييه من الحجم 2. ويمكن اعتباره أيضًا تحويل فورييه على المجموعة الجمعية ثنائية العناصر لـ Z /(2).

صفوف مصفوفات هادامارد هي دوال والش .

تحويل هادامارد مكافئ لتحويل فورييه المنفصل متعدد الأبعاد بحجم 2 × 2 × ⋯ × 2 × 2. ^{[ 2 ]}

بصورة رسمية، يُعد تحويل هادامارد تحويل فورييه على المجموعة البوليانية${\displaystyle (\mathbb {Z} /2\mathbb {Z} )^{n}}$[ ^{3 ] [ 4 ]} باستخدام تحويل فورييه على الزمر المنتهية (الأبيلية) ، ^يكون تحويل فورييه لدالة${\displaystyle f\colon (\mathbb {Z} /2\mathbb {Z} )^{n}\to \mathbb {C} }$هي الوظيفة${\displaystyle {\widehat {f}}}$محدد بواسطة $${\displaystyle {\widehat {f}}(\chi )=\sum _{a\in (\mathbb {Z} /2\mathbb {Z} )^{n}}f(a){\bar {\chi }}(a)}$$ أين${\displaystyle \chi }$هو شخصية من${\displaystyle (\mathbb {Z} /2\mathbb {Z} )^{n}}$لكل حرف شكل${\displaystyle \chi _{r}(a)=(-1)^{a\cdot r}}$بالنسبة للبعض${\displaystyle r\in (\mathbb {Z} /2\mathbb {Z} )^{n}}$حيث يكون الضرب هو حاصل الضرب النقطي المنطقي على سلاسل البتات، لذلك يمكننا تحديد المدخلات لـ${\displaystyle {\widehat {f}}}$مع${\displaystyle r\in (\mathbb {Z} /2\mathbb {Z} )^{n}}$( ازدواجية بونترياجين ) وتعريفها${\displaystyle {\widehat {f}}\colon (\mathbb {Z} /2\mathbb {Z} )^{n}\to \mathbb {C} }$بواسطة $${\displaystyle {\widehat {f}}(r)=\sum _{a\in (\mathbb {Z} /2\mathbb {Z} )^{n}}f(a)(-1)^{r\cdot a}}$$

هذا هو تحويل هادامارد لـ${\displaystyle f}$، مع الأخذ في الاعتبار المدخلات إلى${\displaystyle f}$و${\displaystyle {\widehat {f}}}$كسلاسل منطقية.

فيما يتعلق بالصيغة المذكورة أعلاه حيث يقوم تحويل هادامارد بضرب متجه من${\displaystyle 2^{n}}$الأعداد المركبة${\displaystyle v}$على اليسار بجوار مصفوفة هادامارد${\displaystyle H_{n}}$يمكن ملاحظة التكافؤ من خلال أخذ${\displaystyle f}$لأخذ سلسلة البتات المقابلة لفهرس عنصر من المدخلات${\displaystyle v}$وامتلاك${\displaystyle f}$أخرج العنصر المقابل من${\displaystyle v}$.

التحويل المتقطع المعتاد لفورييه ، المطبق على متجه${\displaystyle v}$ل${\displaystyle 2^{n}}$تستخدم الأعداد المركبة بدلاً من ذلك خصائص المجموعة الدورية${\displaystyle \mathbb {Z} /2^{n}\mathbb {Z} }$وبالتالي، تتطلب تحويلة فورييه المنفصلة (DFT) عمليات حسابية أكثر تعقيدًا بكثير من تحويلة هادامارد. على عكس تحويلة فورييه المنفصلة، ​​فإن تحويلة هادامارد حقيقية تمامًا، ولا تتطلب في الواقع أي عملية ضرب، بل مجرد عكس الإشارات .

في المجال الكلاسيكي، يمكن حساب تحويل هادامارد في${\displaystyle n\log n}$العمليات (${\displaystyle n=2^{m}}$)، باستخدام خوارزمية تحويل هادامارد السريعة .

في المجال الكمومي، يمكن حساب تحويل هادامارد في${\displaystyle O(1)}$الوقت، لأنه بوابة منطقية كمومية يمكن موازاتها .

يُستخدم تحويل هادامارد على نطاق واسع في الحوسبة الكمومية . تحويل هادامارد 2  ×  2${\displaystyle H_{1}}$بوابة المنطق الكمومي المعروفة باسم بوابة هادامارد، وتطبيق بوابة هادامارد على كل كيوبت من${\displaystyle n}$تسجيل الكيوبتات بالتوازي يكافئ تحويل هادامارد${\displaystyle H_{n}}$.

يمكن استخدام تحويل هادامارد لتقدير الأشجار التطورية من البيانات الجزيئية. ^{[ 8 ] [ 9 ] [ 10 ]} من حيث المبدأ، يمكن تطبيق تحويل هادامارد على العديد من نماذج تطور التسلسل المختلفة ، ولكن الحالة الأكثر أهمية هي تلك التي تستخدم بيانات الأحماض النووية . ^{[ 8 ] [ 11 ]}

بصورة رسمية، يمكن اعتبار القواعد النيتروجينية الأربعة المحتملة في السلسلة عناصر من مجموعة كلاين الرباعية V التي تؤثر على نفسها. يتوافق أحد محوري C2 مع التحولات، _والآخر مع التبديلات . تُعدّ متواليات الحمض النووي ذات الطول k عناصر من Vk ^، ويُطلق على أي فهرس في هذه المتواليات ذات الطول k اسم موقع. الشجرة التطورية T هي شجرة، جذرها عند نقطة r ، حيث تم تحديد كل نقطة فيها بمتواليات الحمض النووي. ^{[ 12 ]}

في التطبيقات البيولوجية، يُراد تحديد معدلات الطفرات لكل حافة من حواف الشجرة T ، ثم حساب احتمالية رصد T. من الناحية المثالية، ينبغي أن تكون هذه العملية قابلة للعكس بسهولة، بحيث يمكن لخوارزمية التحسين إيجاد زوج (شجرة، معدل طفرة) يُنتج تسلسلات الحمض النووي المرصودة بأقصى احتمالية . في الواقع، يمكن القيام بذلك باستخدام تحويل هادامارد، كما يلي. ^{[ 12 ] [ 13 ]}

ليكن I مجموعة القوى لـ T \{ r } ، ولنعتبر المتجه x المفهرس ^{بـ I²} كما يلي. يحدد كل موقع j مجموعة σ₁ ∈ I ، وهي مجموعة النقاط التي يحدث عندها انتقال بالنسبة إلى _r في الموقع j . وبالمثل _{، تحدد الانتقالات العكسية مجموعة} σ₂ ∈ I أخرى لكل موقع. عندئذٍ، _يمثل x _{( σ₁ , σ₂ )} نسبة المواقع التي تحدد ( σ₁ , σ₂ ) من بين {1, _{... ,} k } . ^{[ 12 ]}

المؤثر الخطي H :ℝ ^{I 2} → ℝ ^{I 2} ذو المعامل ( σ , τ ) من الرتبة ( −1 ) ^{| σ ₁ ∩ τ ₁ | + | σ ₂ ∩ τ ₂ |} هو مصفوفة هادامارد ؛ في الواقع، يُعرّف تحويل هادامارد عندما يتم تعداد I بترتيب معين. ^{[ 9 ]} ليكن

γ = H ^{− 1} سجل ^{⊗ I 2} ( Hx )

حيث يشير الرمز ⊗ I ² إلى أن اللوغاريتم يؤثر على كل عنصر من عناصر المتجه. عندئذٍ، تكون γ تقريبًا معدلات الطفرة m اللازمة لإنتاج توزيع الاحتمالية المرصود x ، كما يلي. ^{[ 12 ] [ 14 ]}

بالنسبة لنموذج كيمورا الكامل ، مع تمييز الأحماض النووية الأربعة جميعها، توجد ثلاثة معلمات حرة لكل حافة. ​​يتطلب تحويل هذه القيم إلى المدخل المقابل في γ إجراء اقتران لوغاريتمي آخر مع مصفوفة 3 × 3. ^{[ 12 ]}

إذا كانت المتتاليات مُرمَّزة بنظام RY ، فإن العلاقة تصبح أبسط بكثير. في هذه الحالة، يُفهرس x و γ بواسطة I (بدلاً من I² ⁾ ، وكذلك m : بالنسبة لـ σ ∈ I ذات الحجم الزوجي ، ليكن E ( σ ) = σ ؛ وبالنسبة لـ σ ∈ I ذات الحجم الفردي ، ليكن E ( σ ) = σ ⊔ {r} ؛ وليكن mσ معدل الطفرة على الحافة التي تفصل σ عن بقية T. ( m ليس كمية مُقاسة بدقة، لأنه يشمل احتمال الطفرات العكسية. وهو مرتبط باحتمال تغير الحرف الملحوظ _عبر

م _σ = − ⁠ 1 / 2 ⁠ سجل(1-2 ص _σ )

حيث p هي الاحتمالية المرصودة.) ثم γ = m . ^{[ 9 ]}

ويمكن تعميم هذه التقنية أيضاً لتشمل الحالة التي تتحور فيها المواقع المختلفة بمعدلات مختلفة. ^{[ 15 ]}

في جميع الحالات، يهيمن تحويل هادامارد على التعقيد الزمني لتحديد الشجرة، والذي يتطلب O(| T |² ^{| T |} ) من الخطوات. ^{[ 16 ]} ومع ذلك، يمكن للخوارزميات إعادة بناء الشجرة عن طريق تجميع أشجار أصغر مُنشأة من مجموعة فرعية ^من T. ^{[ 17} ]

يُستخدم تحويل هادامارد أيضًا في تشفير البيانات ، بالإضافة إلى العديد من خوارزميات معالجة الإشارات وضغط البيانات ، مثل JPEG XR و MPEG-4 AVC . في تطبيقات ضغط الفيديو ، يُستخدم عادةً في صورة مجموع الفروق المطلقة المُحوَّلة . كما يُعدّ جزءًا أساسيًا من عدد كبير من خوارزميات الحوسبة الكمومية. يُطبَّق تحويل هادامارد أيضًا في تقنيات تجريبية مثل الرنين المغناطيسي النووي ، وقياس الطيف الكتلي ، وعلم البلورات . بالإضافة إلى ذلك، يُستخدم في بعض إصدارات التجزئة الحساسة للموقع ، للحصول على دورانات مصفوفة شبه عشوائية.

• تحويل والش-هادامارد السريع
• تحويل شبه هادامارد
• تحويل الشعر
• قانون التوزيع المعمم

• ريتر، تيري (أغسطس 1996). "تحولات والش-هادامارد: مسح أدبي" .
• أكانسو، علي ن .؛ بولوري، ر. (يوليو 2007). "رموز والش غير الخطية المتعامدة الطورية لاتصالات CDMA ذات التسلسل المباشر" (ملف PDF) . معاملات IEEE في معالجة الإشارات . 55 (7): 3800-3806 . رمز Bibcode : 2007ITSP...55.3800A . doi : 10.1109/TSP.2007.894229 . S2CID 6830633 . 
• بان، جينغ شيانغ طريقة تشفير البيانات باستخدام تحويل هادامارد الجزئي المنفصل (28 مايو 2009)
• لاكوفيتش، د. باول. تحويل والش-هادامارد واختبارات عشوائية سلسلة العائدات المالية (7 أبريل 2015)
• بيدارد، جودفري؛ يورك، بريوني أ. (يناير 2011). "مطيافية الضخ والاستشعار باستخدام تحويلات هادامارد" (ملف PDF) . مؤرشف من النسخة الأصلية (ملف PDF) بتاريخ 18 أكتوبر 2014. تم الاطلاع عليه بتاريخ 28 أبريل 2012 .
• يورك، بريوني أ.؛ بيدارد، غودفري؛ أوين، روبن ل.؛ بيرسون، أروين ر. (سبتمبر 2014). "علم البلورات المعتمد على الزمن باستخدام تحويل هادامارد" . مجلة نيتشر ميثودز . 11 (11): 1131-1134 . doi : 10.1038/nmeth.3139 . PMC 4216935. PMID 25282611 .