图 1  快速哈达马变换的直接实现结构
其中每一级内部的运算结构见图 2：
从图 2(a) 可以看出，在快速哈达马的直接实现结构中，每一级需要 N/2 个如图 2(b) 所示的蝶形运算单元，即：需要 N 个加法器（加法器的位宽由输入数据的位宽决定），又因为整个快速哈达马运算共有 log2N级，因此直接实现结构总共需要 Nlog2N 个加法器，例如：当 N=64 时，加法器数目为 384 个，在 CDMA2000 前向信道中，哈达马变换的阶数最大可为 256，如果采用直接结构，那么将需要 2048 个加法器！这是一个非常消耗资源的部分，在芯片资源等因素的限制下，必须考虑采用折叠（unfolding）技术复用功能单元从而减少资源的消耗，根据折叠的功能单元不一样，可以设计不同层次的折叠结构。
3 快速哈达马变换的折叠结构设计
折叠是一种变换技术[3]，通过使用该技术设计一种控制单元，在该控制单元的控制下可以分时复用电路结构中的功能单元，从而达到减少所使用的功能单元数目的目的。折叠虽然减少了对功能单元数目的使用，但同时也引入了新的控制单元和一些选择器件（如：数据选择器）及存储器件（如：寄存器），这些新的单元对于原功能实现来说是附加的（overhead），它们只是为了实现分时复用功能单元，因此只有当附加的控制单元的资源消耗小于因功能单元数目减少而节约的芯片资源时，折叠结构才能达到减少芯片资源的作用，否则不仅没有减少反而会增加芯片资源，这是设计所不希望的；另外，不同的折叠结构对芯片资源减少所起到的效果也不一样，一种折叠结构在既能保证功能正确实现的前提下又最大化的减少对资源的消耗应是设计者的最佳选择。实际应用中，设计者可以在满足芯片面积需求的情况下选择最适合的折叠结构。除此之外，折叠结构由于需要分时复用功能单元，因此其内部时钟频率要大于输入数据的速率，假设折叠因子为 K（即在一次数据处理中将内部功能单元复用 K 次），输入数据的速率为 R，那么折叠结构内部的时钟频率应为 KR，这在实际应用中也是限制折叠结构选择的重要因素，如果某种折叠结构内部实际时钟频率无法达到所需要的频率，那么就不能选择这种结构。
根据快速哈达马变换中功能单元的折叠使用的不一样，我们设计了两种不同的快速哈达马变换的折叠结构，并分别验证了它们的功能，对比了它们所需要的资源以及对时钟频率的要求。
3.1 级间复用 N 点蝶形运算单元的折叠结构设计
从图 1 可以清楚的看到，哈达马变换的各级所使用的功能模块是完全相同的，这里为方便论述，将每一级的功能模块称为 N 点蝶形运算单元，因此可以在级与级之间分时复用 N 点蝶形运算单元，从而达到减少所消耗资源的目的。图 3 是这种折叠结构的结构框图。
图 3 中，控制单元主要负责产生寄存器输入端数据选择器的选择信号以及在整个哈达马变换结束后使能输出有效指示信号，整个控制器只需要一个计数器（计数器的模为 log2N 以及简单的译码逻辑即可实现，因此控制器的设计是相对简单的。注意：图 3 中哈达马变换单元的输入数据和输出数据都是表示并行输入或输出的。
假设哈达马变换的数据位宽为 W，前级输入信号的码片速率为 R，输出数据位宽与输入相同，则可以该折叠结构的一些理论指标：
(1) 折叠因子 K=log2N。
(2) 节约的功能单元（即：N 点蝶形运算单元）的数目为：log2N-1。
(3) 内部时钟的频率。（之所以分母有 N 因子，是因为前级需要将串行码流转化为 N 路并行数据输入需要 N 个码片时钟周期）。
(4) 哈达马变换的结果延迟为 N 个码片时钟周期。
(5) 因控制和数据选择消耗的资源主要有：N 个位宽为 W 的 2 选 1MUX，一个模 log2N 计数器以及若干简单的译码逻辑。（N 点蝶形运算单元数据输入寄存器一般在未折叠结构中也是需要的，因此不算入附加资源消耗中）从以上理论指标可以看出，这种级间通过分时复用 N 点蝶形远算单元能有效的减少芯片的资源消耗，而且控制器的设计相对比较简单，引入的附加资源消耗较少，特别是当 N 和 W 比较大时，资源的节约非常明显。
3.2 整个哈达马变换单元分时复用 2 点蝶形运算单元
由图 2 哈达马变换各级内部的运算结构图可以清楚的看到：N 点蝶形运算单元就是由 2 点蝶形运算单元组成，因此很自然的考虑可以级间复用 N 点蝶形运算单元的基础上，各级内部分时复用 2 点蝶形运算单元。图 4 为该折叠结构的结构框图。
图 4 所示的折叠结构是在图 3 所示的级间复用结构的基础上在每级内部分时复用 2 点蝶形运算单元，由于各级内部共需要 N/2 个 2 点蝶形运算，由于这些蝶形运算相互没有数据依赖，因此可以按自然顺序将 2 点蝶形运算单元分配给输入数据使用，这样完成一级运算需要 N/2 时钟周期，另外中间每级运算完毕后需要一个时钟周期将结果从输出寄存器打入输入寄存器中，完成整个哈达马变换共需要 (N/2+1)log2N 个时钟周期，  控制单元可由一个模为 (N/2+1)log2N 的计数器以及译码逻辑组成，2 点蝶形运算单元的输入需要两个数据选择器选择输入寄存器中的数据，其输出也要用数据分配器分配给运算结果寄存器（可以等效为在运算结果寄存器前的数据选择器）。
同样，假设哈达马变换的数据位宽为 W，前级输入信号的码片速率为 R，输出数据位宽与输入相同，则可以该折叠结构的一些理论指标：
(1) 折叠因子 。
(2) 节约的功能单元（即：2 点蝶形运算单元）数目为：。
(3) 内部时钟频率 。
(4) 哈达马变换的结果延迟为 N 个码片时钟周期。
(5) 因控制和数据选择消耗的资源主要有：N 个位宽为 W 的 2 选 1MUX（输入数据寄存器前的数据选择器），2 个位宽为 W 的（N/2）选 1MUx（2 点的蝶形运算单元输入数据前的数据选择器），N 个 3 选 1 的MUX（结果寄存器前的数据选择器），模 (N/2+1)log2N 的计数器以及相应的译码逻辑等。（输入数据寄存器和结果寄存器在非折叠结构中一般也是需要的，因此不算入附加资源消耗的计算中）。
从以上分析可以看出，在级与级间复用的基础上再复用每级内部的 2 点蝶形运算单元，可以减少加法器的使用数量（如果输出位宽与输入相同的话，一个两点蝶形运算单元需要两个位宽为 (W+1) 的加法器），当然所需要付出的代价是增加了很多数据选泽器，这些额外增加的数据选择器在某些情兄下甚至会超过因复用而减少的资源，从而导致资源的增加，因此必须通过实际设计来检验该折叠结构是节省资源还是增加资源消耗。
另外，在图 4 所示的结构中，蝶型运算结果寄存器可以和输入寄存器合并（因为一次蝶型运算消耗两个输入数据同时也产生两个结果），当然这样中间运算的输出结果顺序可能会“打乱”，但最终结果的顺序是不变的。虽然这样可以节约 N 个位宽为 W 的寄存器以及寄存器前的数据选择器，但输入寄存器前的数据选择器更复杂了，在实际的设计中不一定可以节约资源。
4 设计实现与验证
为验证以上设计的结构，使用硬件描述语言分别设计了 8 点快速哈达马变换 FHT 一般结构模块，8 点 FHT 级间折叠结构模块和 8 点 FHT 级间/级内部折叠结构模块，并分别在 Altera FPGA EP1C12 期间上实现，对比三种结构的资源消耗情况如表 1 所示。
    表 1  8 点 FHT 不同结构的资源消耗情况
电路结构 逻辑单元数
一股结构（未折叠）         217
级问折叠 77
级间+级内部折叠 l         197
级间+级内部折叠 2   230

为验证所设计的折叠结构的正确性，设计输入测试向量为：
x0=2，x1=0，x2=0，x3=-2，x4=2，x5=0，x6=0， x7=-2
经计算输出经哈达马变换（除以 8）输出结果为：
y0=0，y1=1，y2=1，y3=0，y4=0，y5=0，y6=0，y7=0
级间折叠结构的 FPGA 后仿真波形见图 5，级问及级内部折叠结构的 FPGA 后仿真波形见图 6。
5 结论
由表 l 可以看出：对于 8 点 FHT 的 FPGA 实现而言，级间折叠结构所消耗的资源近似为未折叠的一般结构的 1/3，但级间/级内部折叠结构却并没有节省多少资源，这是因为由于复用引入了大量的数据选择器，而这些数据选择器的输入端的个数超过了 4（EP1C12 查找表输入的最大个数），从而导致为实现这样的数据选择器而消耗了多个逻辑单元（LE），这些 LE 的利用是不经济的（有很多用于 3 输入函数及 2 输入函数），从而使得节约的资源并不明显，甚至在合并输入和结果寄存器后，资源消耗比一般的未折叠结构还要略多。当然在 ASIC 实现时，这种“资源浪费”的情况相对小些，因为 ASIC 实现某些逻辑时要比 FPGA 灵活。
当然，可以预见当 N 较大以及 W 较大时，采用级间与级内部折叠结构对减少资源消耗的改进要明显，这点可以通过将相同结构用于 64 点、甚至 256 点 FHT 中得到验证。

参考文献
[1] 张祟高。快速哈达马德变换。石油地球物理勘探，1980年第4期。
[2] 何永富，刘争平，陈天与。修正哈达马变换的快速算法。成都理工学院学报，第21卷，第2期，1994年。
[3] Keshab K．Parhi．Digital Signal Processing Systems．China Machine Press 2003．P119-P140．