Жылдам Уолш-Хадамарды түрлендіру - Fast Walsh–Hadamard transform - Wikipedia

Ұзындығы 8 векторға қолданылатын жылдам Уолш-Хадамарды түрлендіру

Кіріс векторына мысал (1, 0, 1, 0, 0, 1, 1, 0)

Есептеу математикасында Хадамард бұйырды Уолш - Хадамардтың жылдам өзгеруі (FWHT_сағ) тиімді болып табылады алгоритм есептеу үшін Уолш-Хадамард трансформациясы (WHT). WHT тапсырысының аңғалдықпен орындалуы ${ displaystyle n = 2 ^ {m}}$ болар еді есептеу күрделілігі туралы O ( ${ displaystyle n ^ {2}}$ ). FWHT_сағ талап етеді ${ displaystyle n log n}$ қосу немесе азайту.

FWHT_сағ Бұл алгоритмді бөлу және бағындыру бұл рекурсивті WHT өлшемін бұзады ${ displaystyle n}$ екі кіші WHT өлшеміне ${ displaystyle n / 2}$ . ^[1] Бұл іске асырудың рекурсивті анықтамасынан кейін ${ displaystyle 2 ^ {m} times 2 ^ {m}}$ Хадамард матрицасы ${ displaystyle H_ {m}}$ :

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

The ${ displaystyle 1 / { sqrt {2}}}$ әр кезең үшін қалыпқа келтіру факторлары топтастырылуы немесе тіпті алынып тасталуы мүмкін.

The реттілігі тапсырыс берілді, сонымен қатар Walsh деп аталады, жылдам Walsh-Hadamard трансформациясы, FWHT_w, FWHT есептеу арқылы алынады_сағ жоғарыдағыдай, содан кейін шығуларды қайта реттеңіз.

Уальш-Хадамард түрлендіруінің қарапайым жылдам және рекурсивті емес орындалуы Хадамард түрлендіру матрицасының ыдырауынан туындайды. ${ displaystyle H_ {m} = A ^ {m}}$ , мұндағы A - m-тің түбірі ${ displaystyle H_ {m}}$ . ^[2]

Python мысал коды

деф басқа(а) -> Жоқ:    «» «А. Массивінің орнында жылдам Уолш - Хадамарды түрлендіру.» «»    сағ = 1    уақыт сағ < лен(а):        үшін мен жылы ауқымы(0, лен(а), сағ * 2):            үшін j жылы ауқымы(мен, мен + сағ):                х = а[j]                ж = а[j + сағ]                а[j] = х + ж                а[j + сағ] = х - ж        сағ *= 2

Сондай-ақ қараңыз

Жылдам Фурье түрлендіруі

Әдебиеттер тізімі

^ Фино, Б.Дж .; Algazi, V. R. (1976). «Жылдам Уальш - Хадамдар трансформациясының бірыңғай матрицалық емі». Компьютерлердегі IEEE транзакциялары. 25 (11): 1142–1146. дои:10.1109 / TC.1976.1674569.
^ Ярлагадда мен Херши, «Хадамарды матрицалық талдау және синтездеу», 1997 (Springer)

Сыртқы сілтемелер

Чарльз Константин Гумас, Бір ғасырлық Хадамдамның жылдам өзгеруі цифрлық байланыста пайдалы екенін дәлелдеді

Бұл сигналдарды өңдеу - қатысты мақала а бұта. Сіз Уикипедияға көмектесе аласыз оны кеңейту.

Бұл алгоритмдер немесе мәліметтер құрылымы - қатысты мақала а бұта. Сіз Уикипедияға көмектесе аласыз оны кеңейту.

[1] Фино, Б.Дж .; Algazi, V. R. (1976). «Жылдам Уальш - Хадамдар трансформациясының бірыңғай матрицалық емі». Компьютерлердегі IEEE транзакциялары. 25 (11): 1142–1146. дои:10.1109 / TC.1976.1674569.

[2] Ярлагадда мен Херши, «Хадамарды матрицалық талдау және синтездеу», 1997 (Springer)

[1]

[2]