|
|
快速哈达玛变换基本理论
2.1 沃尔什--哈达玛变换
沃尔什--哈达玛变换因实现简单且性能比较好而得到广泛的应用；在数字水印中就有很好的应用，在数字水印技术中水印的生成基于m序列和快速沃尔什-哈达玛变换矩阵嵌入与检测时使用了一个私钥来产生伪随机序列作为原始水印，使得攻击者在没有密钥的情况下无法取得水印的信息，增强了保密性 [6] 。
2.1.1 哈达玛变换
哈达玛变换（FHT）是数字信号处理中的基本变换之一，在移动通信、多媒体编解码中得到了广泛的应用。
设x(n),n=0,1, ...,N-1，为一实序列，其离散哈达玛变换（DHT）定义为
(2-1)
将XH(k)分解为奇对称分量XHo(k)与偶对称分量XHe(k)之和，其次，可以把奇偶对称分量表示出来：
(2-2)
由DHT定义把XH（k）代入（2-2）式,可得到奇偶对称分量表示如下：
(2-3)
仿照快速DFT的分解方法，可通过时域抽取或频域抽取的方式实现快速DHT。
x(n)的N=2M点DHT如下式：
(2-4)
2.1.2 沃尔什--哈达玛变换
沃尔什函数是二值正交函数,它仅有可能的取值是+1和-1(或0和1),适合于数字信号的处理,可作为码分多址通信系统的地址码使用。沃尔什函数记作Ｗａｌ(ｎ,ｔ),其中ｎ称一般序数,ｔ是时间变数。按由小到大排列的前八个沃尔什函数分别是:Ｗａｌ(0,ｔ)、Ｗａｌ(1,ｔ)、Ｗａｌ(2,ｔ)、Ｗａｌ(3,ｔ)、Ｗａｌ(4,ｔ)、Ｗａｌ(5,ｔ)、Ｗａｌ(6,ｔ)、Ｗａｌ(7,ｔ)。可用一个8×8阶矩阵表示如下:
(2-6)
一般沃尔什函数矩阵记为Ｗ,它是一个Ｎ×Ｎ阶实数方阵。
沃尔什函数也可用哈达玛矩阵Ｈ表示,Ｈ是一个正交方阵,它的每一行代表着一个沃尔什函数。二阶哈达玛矩阵为:
或 (2-7)
四阶、八阶哈达玛矩阵分别为:
与 (2-8)
从而可得
(2-9)
可见哈达玛矩阵Ｈ容易利用递推关系来构造,Ｈ中行的序数称为哈达玛序数,记作 。它不同于一般序数ｎ,而与所取矩阵的行数有关系。
1．哈达玛到沃尔什的变换
ｎ与 之间的关系哈达玛矩阵的行数Ｎ确定后,一般序数ｎ与哈达玛序数 的特定关系,可用格雷码推演出来。若Ｈ的行数为Ｎ,格雷码的位数ｍ随之确定(因Ｎ=2ｍ),则ｎ的格雷码为ｇ(ｎ)=(ｇｍ-1ｇｍ-2…ｇ1ｇ0 ),将ｇ(ｎ)中的二进制位上的数自右向左(或自左向右)翻转过来,得到格雷码的反序,其值就等于 的值,即:
(ｇ0ｇ1…ｇｍ-2ｇｍ-1)2= ,Ｗａｌ(ｎ,ｔ)= (ｔ)
例如:Ｎ = 8 、ｍ = 3 、ｎ= 1时,ｇ(ｎ) = ( 001 ),则有 =( 100 )2 = 4 ,即Ｗａｌ(1,ｔ) = ｈ4(ｔ)，Ｈ8的第5行对应着沃尔什函数Ｗａｌ(1,ｔ)。而当Ｎ= 64 ｍ = 6 ｎ= 1时,ｇ(ｎ) = ( 000001 ) ,则 = ( 100000 )2 = 32 。即Ｗａｌ(1,ｔ) = ｈ32(ｔ),Ｈ64的第33行对应着沃尔什函数Ｗａｌ(1,ｔ)。当Ｈ的行数Ｎ = 4,8,16,32,64时,用此方法推算出的ｎ与 的对应关系如表2-1。从表中数据可知当0≤ｎ<Ｎ/2时,ｎ的值对应 的偶数;当Ｎ/2≤ｎ<Ｎ时,ｎ的值对应 的奇数。
表2-1 Ｎ=4,8,16时ｎ与 的对应关系
序数 对应数值
n 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 2 3 1
0 4 6 2 3 7 5 1
0 8 12 4 6 14 10 2 3 11 15 7 5 13 9 1
若将表2-1中的 先以从小到大的顺序排出,再得出ｎ的对应值如表2-2。
表2-2 =4,8,16时 与n的对应关系
序数 对应数值
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 3 1 2
0 7 3 4 1 6 2 5
0 15 7 8 3 12 4 11 1 14 6 9 2 13 5 10
2．沃尔什到哈达玛的变换
Ｗ与Ｈ的相互转化方法沃尔什函数矩阵Ｗ与哈达玛矩阵Ｈ可以利用置换阵相互转化。根据表2-1中的数据可以构造出第一种置换阵,记为Ｃ,Ｃ为方阵,它的任一行,任一列仅有一个元素是1,其余元素都是0。Ｃ的构造方法是:在表2-1中ｎ的值为Ｃ中等于1的元素的行序(所在行数Ｎ=ｎ+1),而对应的 值为该元素的列序(所在列数Ｎ= +1)。用Ｃ左乘一个矩阵的结果是仅改变该矩阵各行的位置。当哈达玛矩阵Ｈ为已知时,可以用Ｃ左乘Ｈ得到沃尔什函数矩阵Ｗ,即:Ｗ=ＣＨ。
例如:已知
(2-10)
由表2-1中数据构造出
(2-11)
则 (2-12)
根据表2-2中的数据可以构造出第二种置换阵记为Ｄ,Ｄ为方阵。Ｄ的构造方法是:表2-2中 的值为Ｄ中等于1的元素所在的行序(行数Ｎ= +1),而对应的ｎ值为该元素所在的列序(列数Ｎ=ｎ+10)。用Ｄ左乘一个矩阵的结果是仅改变该矩阵各行的位置。当Ｗ为已知时,用Ｄ左乘Ｗ,可得到Ｈ。即:Ｈ=ＤＷ。
例如:
(2-13)
由表2-2构造出Ｄ8
(2-14)
则 (2-15)
另外,置换阵Ｃ、Ｄ之间存在如下关系:ＣＤ=ＤＣ=Ｅ,Ｅ为单位矩阵。
以上讨论了沃尔什函数一般序数ｎ与哈达玛序数 的对应关系;置换矩阵Ｃ和Ｄ的构造方法;Ｗ与Ｈ的相互转化方法。所述方法便于理解和使用。
2.2 快速哈达玛变换
2.2.1 速哈达玛变换算法的基本特点
CDMA2000中在数据的正交调制、解调，正交扩频，信道分离等多处使用离散沃尔什变换，快速哈达玛变换是第二类离散沃尔什变换的快速算法，它能将运算量由 数量级减少为 数量级（ 为变换的点数或数据的个数）。如果使用普通的结构实现快速哈达玛变换，则运算单元数目（加法器数目）需要 。
由于在CDMA2000中哈达玛变换单元的时钟频率并不高（例如在接入信道和反向交通信道中64阶正交调制Walsh码片的速率仅为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 。
