知识卡片

普通读书笔记卡 · 3693.c.1.b.1.a

位逆序使递归叶子顺序连续

理解等级:中级

FFT按下标奇偶递归分组时,逐层剥离的是原下标的低位。把每个下标的lg n位二进制顺序反转,输入就排成递归叶子的次序,可从两点变换自底向上逐级合并。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第30章 多项式与快速傅里叶变换 · 查看原书依据

      The order in which the leaves appear in Figure 30.5 is a bit-reversal permutation. That is, letting rev(k) be the lg n-bit integer formed by reversing the bits of the binary representation of k, then vector element ak moves to position rev(k). In Figure 30.5, for example, the leaves appear in the order 0, 4, 2, 6, 1, 5, 3, 7. This sequence in

    参考来源

    - 位置:《算法导论(第4版)》第30章《多项式与快速傅里叶变换》(OEBPS/chapter030.xhtml,文本字符[30000,35000))。 - 结论依据:原文说明位逆序、FFT电路、精确变换或数值稳定性;相应图和公式已核对。 - 原始内容:The order in which the leaves appear in Figure 30.5 is a bit-reversal permutation . That is, letting rev( k ) be the lg n -bit integer formed by reversing the bits of the binary representation of k , then vector element a k moves to position rev( k ). In Figure 30.5 , for example, the leaves appear in the order 0, 4, 2, 6, 1, 5, 3, 7. This sequence in