首页
会员中心
到顶部
到尾部
其他电子电气

快速哈达玛变换

时间:2020/10/27 9:23:30  作者:  来源:  查看:0  评论:0
内容摘要:快速哈达玛变换基本理论2.1 沃尔什--哈达玛变换沃尔什--哈达玛变换因实现简单且性能比较好而得到广泛的应用;在数字水印中就有很好的应用,在数字水印技术中水印的生成基于m序列和快速沃尔什-哈达玛变换矩阵嵌入与检测时使用了一个私钥来产生伪随机序列作为原始水印,使得攻击者在没有密钥的...

快速哈达玛变换基本理论
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),适合于数字信号的处理,可作为码分多址通信系统的地址码使用。沃尔什函数记作Wal(n,t),其中n称一般序数,t是时间变数。按由小到大排列的前八个沃尔什函数分别是:Wal(0,t)、Wal(1,t)、Wal(2,t)、Wal(3,t)、Wal(4,t)、Wal(5,t)、Wal(6,t)、Wal(7,t)。可用一个8×8阶矩阵表示如下:
                   (2-6)
一般沃尔什函数矩阵记为W,它是一个N×N阶实数方阵。
沃尔什函数也可用哈达玛矩阵H表示,H是一个正交方阵,它的每一行代表着一个沃尔什函数。二阶哈达玛矩阵为:
 或                             (2-7)
四阶、八阶哈达玛矩阵分别为:
  与           (2-8)
 从而可得
                             (2-9)
可见哈达玛矩阵H容易利用递推关系来构造,H中行的序数称为哈达玛序数,记作 。它不同于一般序数n,而与所取矩阵的行数有关系。
1.哈达玛到沃尔什的变换
n与 之间的关系哈达玛矩阵的行数N确定后,一般序数n与哈达玛序数 的特定关系,可用格雷码推演出来。若H的行数为N,格雷码的位数m随之确定(因N=2m),则n的格雷码为g(n)=(gm-1gm-2…g1g0 ),将g(n)中的二进制位上的数自右向左(或自左向右)翻转过来,得到格雷码的反序,其值就等于 的值,即:
(g0g1…gm-2gm-1)2= ,Wal(n,t)=  (t)
例如:N = 8 、m = 3 、n= 1时,g(n) = ( 001 ),则有  =( 100 )2 = 4 ,即Wal(1,t) = h4(t),H8的第5行对应着沃尔什函数Wal(1,t)。而当N= 64 m = 6 n= 1时,g(n) = ( 000001 ) ,则  = ( 100000 )2 = 32 。即Wal(1,t) = h32(t),H64的第33行对应着沃尔什函数Wal(1,t)。当H的行数N = 4,8,16,32,64时,用此方法推算出的n与 的对应关系如表2-1。从表中数据可知当0≤n<N/2时,n的值对应 的偶数;当N/2≤n<N时,n的值对应 的奇数。
表2-1 N=4,8,16时n与 的对应关系
序数 对应数值
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中的 先以从小到大的顺序排出,再得出n的对应值如表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.沃尔什到哈达玛的变换
W与H的相互转化方法沃尔什函数矩阵W与哈达玛矩阵H可以利用置换阵相互转化。根据表2-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-11)


则                                          (2-12)
根据表2-2中的数据可以构造出第二种置换阵记为D,D为方阵。D的构造方法是:表2-2中 的值为D中等于1的元素所在的行序(行数N= +1),而对应的n值为该元素所在的列序(列数N=n+10)。用D左乘一个矩阵的结果是仅改变该矩阵各行的位置。当W为已知时,用D左乘W,可得到H。即:H=DW。
例如:
                   (2-13)
由表2-2构造出D8
                   (2-14)
则                                 (2-15)
另外,置换阵C、D之间存在如下关系:CD=DC=E,E为单位矩阵。
以上讨论了沃尔什函数一般序数n与哈达玛序数 的对应关系;置换矩阵C和D的构造方法;W与H的相互转化方法。所述方法便于理解和使用。
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 。
 
 

Tags:



相关评论
广告联系QQ:45157718 点击这里给我发消息 电话:13516821613 杭州余杭东港路118号雷恩国际科技创新园  网站技术支持:黄菊华互联网工作室 浙ICP备06056032号