热门问题
时间线
聊天
视角
快速沃尔什转换
来自维基百科,自由的百科全书
Remove ads
在计算数学中,一个与阿达马变换有高度相关的快速沃尔什转换(英语:fast Walsh–Hadamard transform,FWHTh)是一个十分有效率的演算法,目的是计算阿达马变换。一个直观且基本的沃尔什转换,他的计算复杂度 大约是 O()。而快速沃尔什转换只需要 个加法或是减法即可。

而快速沃尔什转换是一个分而治之的演算法,是一个常见的递回方法,将大小为 的沃尔什转换拆成两个大小为 的沃尔什转换。这样的写法是根据阿达马矩阵 的递回定义:
其中 的正规化项可以提出或省略掉。
沃尔什矩阵,又叫沃尔什序列,快速沃尔什转换FWHTw,就是用上面的作法计算以后,把输出结果排成序列。
Remove ads
相关条目
参考资料
- Fino, B. J.; Algazi, V. R. Unified Matrix Treatment of the Fast Walsh–Hadamard Transform. IEEE Transactions on Computers. 1976, 25 (11): 1142–1146. doi:10.1109/TC.1976.1674569.
![]() | 这是一篇电脑科学小作品。您可以通过编辑或修订扩充其内容。 |
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads