การแปลงแบบเร็วของวอลช์-ฮาดามาร์ด

Q: ตัวอย่างโค้ด Python

None:\n \"\"\"In-place Fast Walsh–Hadamard Transform of array a.\"\"\"\n assert math.log2(len(a)).is_integer(), \"length of a is a power of 2\"\n h = 1\n while h import math def fwht ( a ) -> None : """การแปลง Walsh–Hadamard แบบเร็วในตัวของอาร์เรย์ a.

Q: ดูเพิ่มเติม

การแปลงฟูริเยร์แบบเร็ว การแปลงเวฟเล็ตแบบเร็ว

ในคณิตศาสตร์เชิงคำนวณการแปลงวอลช์-ฮาดามาร์ดแบบเร็วที่ เรียงลำดับตามฮาดามาร์ด ( FWHT ) เป็นอัลกอริทึม ที่มีประสิทธิภาพ ในการคำนวณการแปลงวอลช์-ฮาดามาร์ด (WHT) การใช้งาน WHT แบบง่ายๆ ที่มีลำดับ $n=2^{m}$ จะมี ความซับซ้อน ในการคำนวณ O( $n^{2}$ ) . FWHT ต้องการเพียง $n\log n$ การบวกหรือการลบ

FWHT เป็นอัลกอริทึมแบบแบ่งและพิชิต (divide-and-conquer)ที่แบ่ง WHT ขนาด ออกเป็นส่วนย่อยๆ แบบเรียกซ้ำ $n$ แบ่งเป็น WHT ขนาดเล็ก 2 อัน $n/2$ [ ¹^{] การใช้งานนี้เป็นไปตามคำ}^{จำกัดความ} แบบเรียกซ้ำของ $2^{m}\times 2^{m}$ เมทริกซ์ฮาดามาร์ด $H_{m}$ :

H_{m}={\frac {1}{\sqrt {2}}}{\begin{pmatrix}H_{m-1}&H_{m-1}\\H_{m-1}&-H_{m-1}\end{pmatrix}}.

เดอะ $1/{\sqrt {2}}$ ปัจจัยการปรับค่ามาตรฐานสำหรับแต่ละขั้นตอนอาจถูกจัดกลุ่มเข้าด้วยกัน หรืออาจถูกละเว้นไปเลยก็ได้

การ แปลงวอลช์-ฮาดามาร์ดแบบเร็ว (FWHT ) ที่เรียงลำดับตามลำดับ หรือที่รู้จักกันในชื่อการแปลงวอลช์-ลำดับแบบเร็ว ได้มาจากการคำนวณ FWHT ดังที่กล่าวมาข้างต้น แล้วจัดเรียงผลลัพธ์ใหม่

การนำการแปลง Walsh–Hadamard ไปใช้แบบง่ายๆ รวดเร็ว และไม่ใช้การเรียกซ้ำนั้น ได้มาจากการแยกส่วนเมทริกซ์การแปลง Hadamard ดังนี้ $H_{m}=A^{m}$ โดยที่Aคือรากที่m ของ $H_{m}$ [ ²^]

ตัวอย่างโค้ด Python

import math def fwht ( a ) -> None : """การแปลง Walsh–Hadamard แบบเร็วในตัวของอาร์เรย์ a.""" assert math . log2 ( len ( a )) . is_integer (), "ความยาวของ a เป็นกำลังของ 2" h = 1 while h < len ( a ): # ทำการแปลง FWHT 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

ดูเพิ่มเติม

ลิงก์ภายนอก

Charles Constantine Gumas กล่าวว่าการแปลง Hadamard ที่รวดเร็วซึ่งมีอายุเกือบศตวรรษพิสูจน์แล้วว่ามีประโยชน์ในการสื่อสารดิจิทัล

1

2

ไม่มีชื่อบทความ

การแปลงแบบเร็วของวอลช์-ฮาดามาร์ด

ตัวอย่างโค้ด Python

ดูเพิ่มเติม

ลิงก์ภายนอก

ข้อมูลสำคัญจากบทความ