快速哈达玛变换.docx

《快速哈达玛变换.docx》由会员分享，可在线阅读，更多相关《快速哈达玛变换.docx（3页珍藏版）》请在第一文库网上搜索。

1、快速哈达玛变换基本理论2.1 沃尔什-哈达玛变换沃尔什-哈达玛变换因实现简单且性能比较好而得到广泛的应用；在数字水印中就有很好的应用，在数字水印技术中水印的生成基于m序列和快速沃尔什-哈达玛变换矩阵嵌入与检测时使用了一个私钥来产生伪随机序列作为原始水印，使得攻击者在没有密钥的情况卜.无法取得水印的信息，增强了保密性6o2.1.1哈达玛变换哈达玛变换(FHT)是数字信号处理中的基本变换之一，在移动通信、多媒体编解码中得到了广泛的应用。设x(n),n=O,1,N-1为一实序列，其离散哈达玛变换(DHT)定义为(2-1)将XH(k)分解为奇对称分量XHO(k)与偶对称分量XHe(k)之和，其次，可以

2、把奇偶对称分量表示出来：(2-2)由DHT定义把XH(k)代入(2-2)式,可得到奇偶对称分量表示如下：(2-3)仿照快速DFT的分解方法，可通过时域抽取或频域抽取的方式实现快速DHTox(n)的N=2M点DHT如卜.式：(2-4)2.1.2沃尔什哈达玛变换沃尔什函数是二值正交函数,它仅有可能的取值是+1和-1(或O和1),适合于数字信号的处理,可作为码分多址通信系统的地址码使用。沃尔什函数记作Wa1(11),其中门称一般序数，1是时间变数。按由小到大排列的前八个沃尔什函数分别是:Wa1(O,t)、Wa1(I,t)、Wa1(2,t)、Wa1(3,t)、Wa1(4,t)、Wa1(5,t)、Wa1

3、(6,t)、Wa1(7zt)。可用一个88阶矩阵表示如下：(2-6)一般沃尔什函数矩阵记为W,它是一个NXN阶实数方阵。沃尔什函数也口J用哈达玛矩阵H表示,H是一个正交方阵,它的每一行代表着一个沃尔什函数。二阶哈达玛矩阵为：或(2-7)四阶、八阶哈达玛矩阵分别为：与(2-8)从而可得(2-9)可见哈达玛矩阵H容易利用递推关系来构造,H中行的序数称为哈达玛序数,记作。它不同于一般序数n,而与所取矩阵的行数有关系。1 .哈达玛到沃尔什的变换n与之间的关系哈达玛矩阵的行数N确定后,一般序数n与哈达玛序数的特定关系,可用格雷码推演出来。若H的行数为N,格雷码的位数m随之确定(因N=2m),则n的格雷码

4、为g(n)=(gm-1gm-2.g1g0),将g(n)中的二进制位上的数自右向左(或自左向右)翻转过来,得到格雷码的反序,其值就等于的值,即：(gg1.gm-2gm-1)2=,Wa1(nzt)=(t)例如：N=8、m=3、n=1时，g(n)=(001),则有=(IOO)2=4,即Wa1(1zt)=h4(t),H8的第5行对应着沃尔什函数Wa1(1zt)0而当N=64171=6门=1时*(11)=(000001),则=(IOOOOo)2=32。即Wa1(1,t)=h32(t),H64的第33行对应着沃尔什函数Wa1(1,t)0当H的行数N=4,8,16,32,64时,用此方法推算出的n与的对应关

5、系如表2-1。从表中数据可知当0nVN/2时，n的值对应的偶数;当N2nVN时，n的值对应的奇数。表2-1N=4,8,16时n与的对应关系序数对应数值nO1234567891011121314150231046237510812461410231115751391若将表2-1中的先以从小到大的顺序排出,再得出n的对应值如表2-2e表22=4,8,16时与n的对应关系序数对应数值012345678910111213141503120734162501578312411114692135102 .沃尔什到哈达玛的变换W与H的相互转化方法沃尔什函数矩阵W与哈达玛矩阵H可以利用置换阵相互转化。根据表2

6、-1中的数据可以构造出第种置换阵,记为C,C为方阵,它的任行,任列仅有个元素是1,其余元素都是0。C的构造方法是:在表2-1中n的值为C中等于1的元素的行序(所在行数N=n+1),而对应的值为该元素的列序(所在列数N=+1)。用C左乘个矩阵的结果是仅改变该矩阵各行的位置。当哈达玛矩阵H为已知时，可以用C左乘H得到沃尔什函数矩阵W,即:W=CH。例如:已知(2-10)由表2-1中数据构造出(2-H)则(2-12)根据表22中的数据可以构造出第二种置换阵记为D,D为方阵。D的构造方法是:表22中的值为D中等于1的元素所在的行序(行数N=+1),而对应的n值为该元素所在的列序(列数N=n+10)。用

7、D左乘一个矩阵的结果是仅改变该矩阵各行的位置。当W为已知时,用D左乘W,可得到H。即：H=DW。例如：(2-13)由表2-2构造出D8(2-14)则(2-15)另外,置换阵C、D之间存在如下关系：CD=DC=EzE为单位矩阵。以上讨论了沃尔什函数一般序数n与哈达玛序数的对应关系;置换矩阵C和D的构造方法;W与H的相互转化方法。所述方法便于理解和使用。2.2快速哈达玛变换2.2.1 速哈达玛变换算法的基本特点CDMA2000中在数据的正交调制、解调，正交扩频，信道分离等多处使用离散沃尔什变换，快速哈达玛变换是第二类离散沃尔什变换的快速算法，它能将运算量由数量级减少为数量级(为变换的点数或数据的个

8、数)。如果使用普通的结构实现快速哈达玛变换，则运算单元数目(加法器数目)需要。由于在CDMA2000中哈达玛变换单元的时钟频率并不高(例如在接入信道和反向交通信道中64阶正交调制WaISh码片的速率仅为307.2KCPS),因此在基带芯片的设计中可以考虑采用折钱结构来减少变换单元的使用，从而节约芯片的资源，减少芯片的面积。本设计基于上述考虑，设计了快速哈达玛变换的几种折叠结构。2.2.2 快速哈达玛变换算法分析如式(2-16)、(2-17)所示，第二类离散沃尔什变换及其反变换可以采用哈达玛矩阵表示：(2-16)(2-17)直接计算离散沃尔什变换需要次加法运算，快速哈达玛算法通过将哈达玛矩阵分解为稀疏矩阵的()耗次方，从而大大减少了变换所需的运算量，如公式(2-18)式所示：(2-18)其中稀疏矩阵为：(2-19)对于稀疏矩阵TN可以这样来理解，下面以举例的方式对它进行解释例如：(2-20)则有(2-21)通过计算可以很容易的得到H4=(T4)2。