温鸿航,葛建华,许唐雯

(西安电子科技大学综合业务网理论及关键技术国家重点实验室,陕西西安 710071)

一种低复杂度OFDM峰均比降低方法

温鸿航,葛建华,许唐雯

(西安电子科技大学综合业务网理论及关键技术国家重点实验室,陕西西安 710071)

针对部分传输序列方法搜索复杂度会随着分组呈指数增长的问题,给出了基于免疫进化搜索的算法来降低部分传输序列方法的复杂度.采用量子比特表示各分组状态,用免疫算法在搜索过程中抑制退化,增加群体适应度,并采用六边形星座消除边带信息.计算机仿真结果表明,该方法计算复杂度较部分传输序列方法明显减小,较同类方法有更好的正交频分复用峰均比性能表现,且无需额外传输边带信息.

多载波调制;正交频分复用;峰均功率比;量子计算;进化算法

正交频分复用(Orthogonal Frequency Division Multiplexing,OFDM)作为多载波调制的一种,具有高频谱效率、抗频率选择性干扰和易实现等优点.OFDM已被广泛应用在多个通信标准中,如IEEE 802.11 a/ g、IEEE 802.16(Wi MAX)和3GPP LTE等.但OFDM信号峰均功率比(Peak-to-Average Power Ratio, PAPR)较大,易导致信号失真与功放失效[1].

部分传输序列(Partial Transmit Sequences,PTS)作为一种畸变最优PAPR降低方法[2-3],只会增加很小的冗余.但PTS要对所有相位因子组合进行穷举搜索,文献[4-7]给出次优搜索算法,分别是基于模拟退火[4]、人工蜂群[5]、禁忌搜索[6]和量子进化[7].文献[9]是一种基本免疫进化算法,但未能完全消除退化,可进一步改善.笔者联合进化算法和免疫算法,给出了一种新的免疫进化算法(Immune Evolutionary Mechanism,IEM),既保留了进化算法的优点,又可抑制退化,显著提高了效率.另外,采用六边形星座消除边带信息,避免了边带信息误传引起的突发错误.

1 基于PTS的OFDM系统及问题描述

1.1 PAPR的定义

N个子载波的OFDM信号,经过LN点逆傅里叶变换可表示为

当过采样因子L≥4时,其峰均功率比近似连续OFDM信号.那么,OFDM信号的峰均功率比可表示为

1.2 PTS-OFDM系统

如图1所示,系统输入X被划分为V个子块,{X(v),v=1,2,…, V},可表示为

图1 PTS-OFDM系统

其中,X(v)=[X0(v),X1(v),…,XN(v-)1],且Xk(v)=Xk或0(1≤v≤V).每个X(v)都有独立的相位旋转因子,b={bv=ex p(jφv),v=1,2,…,V},从而得到峰均功率比降低后的OFDM信号,即

再对其逆傅里叶变换,可得时域序列为

调整相位旋转因子b,可以使峰均功率比最小.因此,基于PTS的最优问题可表示为

其中,b∈{exp(jφv)}V,且φv∈{(2πωW)|ω=0,1,…,W-1}.理论上,bv可为[0, 2π)的任意相位,PTS算法就是搜索使峰均功率比最小的解.因此,算法复杂度会随子块的增加呈指数增加,降低复杂度是算法的关键问题.

1.3 PTS边带信息

基于PTS的OFDM系统接收端译码需要利用边带信息,边带信息错误会引起突发错误.文献[10]给出一种利用六边形星座(Hexagonal Constellation,HC)减小峰均比的方法.

图2给出23点(23-HC)的例子.23-HC与16QAM有相同的吞吐量和最小距离,HC的判决面积为31/2d2/2,其中,d为星座点间的最小距离.因此,16QAM与23-HC判决面积比为2/31/2,23-HC的误比特率较16QAM稍微差一点.若增加重复表示的星座点,六边形星座的峰均比性能可进一步改善.

图2 六边形星座图(23-HC)

1.4 立方量度

立方量度(Cubic Metric,CM)表示功放功率效率的降低,被证明在宽带码分多址移动通信系统(Wideband Code Division Multiple Access,WCDMA)和长期演进(Long Term Evolution,LTE)中是比峰均功率比更为准确的度量方法[11].文中也将比较不同方法的立方量度性能.OFDM信号的立方量度定义为

其中,RRCM称为原立方量度,RRCM_ref和K用于完善给定信道邻道泄露比情况下的功率退化.信号x(t)的原立方量度(Row Cubic Metric,RCM)可表示为

其中,[x(t)]RMS表示x(t)的均方根(Root Mean Square,RMS).

2 量子计算与免疫算法

2.1 量子计算

量子比特(qubit)除0或1外,还可处于两种状态的叠加态,可表示为

2.2 免疫算法

免疫算法是一种进化算法,可利用本地特征信息去寻找最优解.与自然界的免疫现象类似,算法需避免发生退化,因此要确保群体的适应度会稳定增加.

理想的免疫算法分为两个步骤:接种疫苗和免疫选择.前者可提升群体适应度,后者可防止退化.在接种疫苗时,假设个体x是整数优化问题的潜在解(比特序列),那么,x的疫苗就是根据先验知识修正x的某些比特,以增加适应度.免疫选择有免疫测试选择和退火测试选择两种方法.

3 文中算法及复杂度

3.1 免疫进化算法

其中,V为量子比特数目,即量子比特字符串长度.IEM可分如下步骤迭代运行:

Step 1 观察Q(t)状态,在P(t)中随机生成二进制解,其中…}.在峰均功率比问题中,二进制值ptik定义为

Step 2 在P(t)进行免疫以增加群体适应度.

(1)疫苗接种:首先,根据接种修改个体相位因子.其次,对于,若或则去掉重复个体.这意味着个体选择要兼顾当前和过去的群体,生成新个体直到没有重复.最后,计算相应的适应度值,并自适应修改相位因子.适应度的计算公式为

由式(12)可得r个不同的个体.

(2)免疫选择:方法1,根据适应性和群体多样性对群体进行分类,使得适应度优于平均值且与最优差异大的个体能够存活.方法2,根据退火算法选择当前个体.

Step 3 用Q-gate修正概率α和β的值,更新量子比特个体.Q-gate可表示为

其中,Δθ是旋转角度参数,量子比特会偏向0还是1取决于其符号.可用Δθ大小控制收敛速度,但如果其值太大,有可能会导致发散或者局部收敛的情况.

3.2 文中算法流程

文中算法流程如下:

t←0

初始化Q(t),所有的量子比特设为1/21/2

观察Q(t)的状态,确定P(t)

计算评估P(t),把P(t)中的最优解存到B(t)

while(not termination-condition)do

t←t+1

观察Q(t-1)的状态,确定P(t)

对P(t)执行免疫算法Step 2

计算评估P(t)

把B(t-1)和P(t)中的最优解存到B(t)

存储B(t)中的最佳解b

if(migration-condition)then

end if

end while.

其中,B(t-1)和P(t)中的最优解存储到B(t),如果B(t)中存储的最优解优于b中的最优解,则b中最优解被新的替代.P(t)的二元解在循环最后会被抛弃,因为Step 3中观察更新后的Q(t)会得到P(t+1).在终止条件满足之前,算法一直在while循环内执行.

learn_model两种算法流程如下.

算法1learn_model

for all i do

else Qi←rotatetowardsusing-Δθ

end if

end for.

算法2learn_model

for j=1 to V do

else

end if

end if

end for.

每个解必须评估出一个其适应度函数级别.显然,式(5)中的相位因子并不改变原始OFDM信号的平均功率.因此,文中算法的适应度函数可表示为此外,算法中非终止条件是x′(bi)的峰均比大于预先确定的极限,转移条件是x′(bi)峰均比符合需求或者达到最大迭代数.

3.3 复杂度分析

基于PTS的群体搜索,其复杂度由采样数决定[4,6].假设最大迭代数和群体规模分别为Gen和pop,那么采样数为Gen·pop.采样经快速傅里叶变换算法(Fast Fourier Transform Algorithm,FFT)后,次最优解的算法复杂度为每个采样O(N log N)次乘法.该复杂度分析可适用所有群体PTS搜索方法.根据式(12),由forginal得到fmodified需要进行N次加法.因此,相对其他PTS算法,IEM算法的加法增加,乘法复杂度不变.表1列出各种PTS算法的采样数以及PAPR性能,分别为模拟退火PTS(SA)[4]、量子进化PTS(QEA)[7]、人工蜂群PTS(ABC)[5]、并行禁忌搜索PTS(Parallel TS)[6],以及最优PTS(OPTS).其中“I1”和“I2”分别表示免疫选择方法1和方法2,“A1”和“A2”分别表示learn_model的算法1和算法2。从表1可看出,文中算法与其他PTS算法的复杂度相同,仅为全搜索的0.46%,但仿真结果表明,文中算法的PAPR性能比起其他PTS算法更接近全搜索.

表1 不同PTS算法复杂度与PAPR性能

4 性能评估

性能评估参数:105个正交幅度调制(Quadrature Amplitude Modulation,QAM)的随机OFDM符号,过采样因子L=4,子载波N=256,相位因子和子块数分别为W=2和V=16,子块分割采用交织分割,每个量子比特的旋转角度为Δθ=0.01π.选择表1中的PTS算法与文中算法比较.图中“Original”和“OPTS”分别表示直接使用IFFT输出和搜索全部WV-1个相位因子的最优PTS.

图3比较了5个方案的互补累计概率分布函数(Complementary Cumulative probability Distribution Function,CCDF),其中,Gen为3,pop为50.如图3所示,文中算法性能较其他算法好,r越大,性能越好.图4对比了峰均功率比性能,在同样采样数下,IEM性能明显优于其他算法.尽管随采样点的增加,PAPR会持续改善,但从400点到1 200点时,I2A2的峰均比仅降低了0.3dB.因此,采用400点可以兼顾性能和复杂度.

图3 互补累计分布函数与峰均功率比

图4 峰均功率比与采样数

图5比较了各种算法的立方量度性能.同样可以看到,文中算法在给定CCDF时,有明显的立方度量性能优势.最后,如图6所示,在有固态功率放大器时,比较六边形星座采用不同搜索算法的误比特率.仿真参数设置C=6.5dB和p=3,采样数设为200.当误比特达到10-3时,算法I2A2明显优于其他算法,仅需要11.3dB,说明文中算法在消除边界信息的同时,亦有明显的性能优势.

图5 互补累计分布函数与原立方量度

图6 误比特率与信噪比

5 结束语

部分传输序列算法是一种有效的OFDM系统降低峰均功率比技术,但其计算复杂度会随划分子块数呈指数增加.文中给出结合免疫遗传的量子算法,可利用接种和选择的进化算法,避免了部分传输序列搜索过程中无用反复的工作,以明显低于传统PTS算法的复杂度得到与其同样的峰均功率比.

[1]Van Nee R,Prasad R.OFDM for Wireless Multimedia Communications[M].Boston:Artech House,2000.

[2]Muller S H,Huber J B.OFDM with Reduced Peak-to-average Power Ratio by Optimum Combination of Partial Transmit Sequences[J].Electronics Letters,1997,33(5):368-369.

[3]王进祥,吴新春,毛志刚,等.降低OFDM信号PAPR的低复杂度PTS方法[J].西安电子科技大学学报,2010,37 (2):326-333. Wang Jinxiang,Wu Xinchun,Ma Zhigang,et al.Low Complexity PTS Scheme for PAPR Reduction of OFDM Signals [J].Journal of Xidian University,2010,37(2):326-333.

[4]Jiang T,Xiang W,Richardson P C,et al.PAPR Reduction of OFDM Signals Using Partial Transmit Sequences with Low Computational Complexity[J].IEEE Transactions on Broadcasting,2007,53(3):719-724.

[5]Yu X,Li S,Zhu Z,et al.An Improved Artificial Bee Colony-partial Transmit Sequence Algorithm for PAPR Reduction in OFDM Systems[J].International Journal of Wireless and Mobile Computing,2013,6:473-480.

[6]Ding S Y,Shu R,Li S B,et al.An Optimization Algorithm for PAPR Reduction in OFDM System Based on Tabu Search[C]//Proceedings of the 8th International Conference on Networking,Architecture and Storage.Washington: IEEE Computer Society,2013:317-320.

[7]Chen J C.Application of Quantum-inspired Evolutionary Algorithm to Reduce PAPR of an OFDM Signal Using Partial Transmit Sequences Technique[J].IEEE Transactions on Broadcasting,2010,56(1):110-113.

[8]Tsai C W,Liao Y H,Chiang M C.A Quantum-inspired Evolutionary Clustering Algorithm[C]//Proceedings of the International Conference on Fuzzy Theory and Its Applications.Washington:IEEE Computer Society,2013:305-310.

[9]Hou J,Ge J,Huang S.Immune Evolutionary Algorithm to Reduce PAPR of OFDM Signals Using PTS Technique[C]// IEEE Global Telecommunications Conference.New York:IEEE,2011:1-5.

[10]Wang L,Tellambura C.Cross-entropy-based Sign-selection Algorithms for Peak-to-average Power Ratio Reduction of OFDM Systems[J].IEEE Transactions on Signal Processing,2008,56(10):4990-4994.

[11]Motorola.3GPP Tdoc R1-060023:Cubic Metric in 3GPP-LTE[R/OL].[2014-08-10].http://www.3gpp.org/ftp/tsg_ran/WG1_RL1/TSGR1_AH/LTE_AH_0601/Docs/R1-060023.zip

(编辑:齐淑娟)

Low complexity method for PAPR reduction of OFDM signals

WEN Honghang,GE Jianhua,XU Tangwen
(State Key Lab.of Integrated Service Networks,Xidian Univ.,Xi’an 710071,China)

Partial transmit sequences(PTS)search complexity increases exponentially with the number of subblocks.To solve this problem,a novel immune quantum evolutionary PTS scheme is proposed to reduce computational complexity and improve PAPR performance.In this scheme,a Q-gate is introduced to drive the individuals toward better solutions,the evolutionary mechanism restrains degeneracy and increases the fitness of population,and a specially hexagonal constellation is used to eliminate side information. Simulation results indicate that the conventional PTS is more complicated than the proposed strategy,and that the proposal shows better performance without additional transmit sideband information than similar other solutions.

multicarrier modulation;orthogonal frequency division multiplexing;peak-to-average power ratio;quantum computing;evolutionary algorithms

TN919.3

A

1001-2400(2015)05-0188-06

2014-10-14

国家重点基础研究发展计划(973计划)资助项目(2012CB316100)

温鸿航(1979-),男,西安电子科技大学博士研究生,E-mail:wenhonghang@126.com.

10.3969/j.issn.1001-2400.2015.05.031