تحويل والش-هادامارد السريع

الموسوعة الحرة
تطبيق تحويل والش-هادامارد السريع على متجه طوله 8
مثال لمتجه الإدخال (1، 0، 1، 0، 0، 1، 1، 0)

في الرياضيات الحسابية، يُعد تحويل والش-هادامارد السريع المرتب حسب هادامارد ( FWHT h ) خوارزمية فعالة لحساب تحويل والش-هادامارد (WHT). ويُمكن تطبيق WHT من الرتبة 1 بشكل مبسط.ن=2م{\displaystyle n=2^{m}}سيكون لها تعقيد حسابي من O(ن2{\displaystyle n^{2}}) . يتطلب FWHT h فقطنسجل⁡ن{\displaystyle n\log n}عمليات الجمع أو الطرح.

خوارزمية FWHT h هي خوارزمية فرق تسد تقوم بتقسيم WHT بشكل متكرر إلى حجمن{\displaystyle n}إلى اثنين من أجهزة WHT الأصغر حجمًان/2{\displaystyle n/2}[ 1 ] يتبع هذا التنفيذ التعريف التكراري لـ2م×2م{\displaystyle 2^{m}\times 2^{m}}مصفوفة هاداماردحم{\displaystyle H_{m}}:

حم=12(حم-1حم-1حم-1-حم-1).{\displaystyle H_{m}={\frac {1}{\sqrt {2}}}{\begin{pmatrix}H_{m-1}&H_{m-1}\\H_{m-1}&-H_{m-1}\end{pmatrix}}.}

ال1/2{\displaystyle 1/{\sqrt {2}}}يمكن تجميع عوامل التطبيع لكل مرحلة معًا أو حتى حذفها.

يتم الحصول على التحويل المرتب بالتسلسل ، والمعروف أيضًا باسم تحويل والش-هادامارد السريع المرتب بـ Walsh، FWHT w ، عن طريق حساب FWHT h كما هو مذكور أعلاه، ثم إعادة ترتيب المخرجات.

يُمكن الحصول على تطبيق بسيط وسريع وغير تكراري لتحويل والش-هادامارد من خلال تحليل مصفوفة تحويل هادامارد كما يلي:حم=أم{\displaystyle H_{m}=A^{m}}، حيث A هو الجذر m لـحم{\displaystyle H_{m}}[ 2 ]​

مثال على كود بايثون

import math def fwht ( a ) -> None : " ""تحويل والش-هادامارد السريع في مكانه للمصفوفة a.""" assert math.log2 ( len ( a ) ) . is_integer (), "طول a هو قوة للعدد 2" h = 1 while h < len ( a ): # تنفيذ تحويل والش-هادامارد السريع for i in range ( 0 , len ( a ), h * 2 ): for j in range ( i , i + h ): x = a [ j ] y = a [ j + h ] a [ j ] = x + y a [ j + h ] = x - y # تطبيع وزيادة a /= math.sqrt ( 2 ) h * = 2

انظر أيضاً

مراجع

  1. ↑ فينو، بي جيه؛ ألغازي، في آر (1976). "معالجة مصفوفية موحدة لتحويل والش-هادامارد السريع". معاملات IEEE في الحوسبة . 25 (11): 1142-1146 . doi : 10.1109/TC.1976.1674569 . S2CID 13252360 . 
  2. ↑ يارلاجادا وهيرشي، "تحليل وتوليف مصفوفة هادامارد"، 1997 (سبرينغر)
  • تشارلز قسطنطين غوماس، تحويل هادامارد السريع الذي يعود تاريخه إلى قرن من الزمان، يثبت فائدته في الاتصالات الرقمية