Performance of Viterbi detection algorithm for DFH codes based on recursive shift register
-
摘要: 设计了一种基于回归移位寄存器的差分跳频(Differential Frequency Hopping, DFH)码, 定义了DFH码的路径重量分布和距离谱, 给出了快速计算方法; 采用两种不同方法推导了维特比检测算法的误比特率上界, 通过计算机仿真对理论推导结果进行了验证, 在频率集频点个数为8, 误比特率为10-3时, 理论分析给出的性能估计已经非常精确.对DFH码距离谱特性的分析表明, 自由距尽可能大, 距离谱尽可能小的是好码.Abstract: A class of differential frequency hopping (DFH) codes based on the recursive shift register is designed. The path weight distribution and the distance spectrum of the DFH codes are defined. The fast algorithm for the two parameters is given. The upper bound of the Viterbi detection algorithm performance for DFH system is derived by using two different methods. Simulation results indicate that the performance evaluation of the bit error rate (BER) given by the upper bound is accurate, when the hopping set includes 8 frequencies and the BER is less than 10-3. Finally the rules to select the good codes of the DFH codes are given.
-
Keywords:
- DFH /
- free distance /
- distance spectrum /
- path weight distribution
-
引言
差分跳频(Differential Frequency Hopping, DFH)技术首先由Herrick和Lee提出, 并应用于短波跳频通信[1-2].Mills等人的研究表明DFH技术的应用不局限于短波频段, 可推广到其他频段, 进一步扩展了DFH技术的应用范围[3].采用DFH技术的CHESS电台在短波信道实现了5000跳/秒的高跳速和19.2 kbps的高数据传输率, 并具有良好的抗跟踪干扰和抗衰落能力.DFH技术的主要特点是不对载波进行调制, 直接通过载波频率的变化来传递信息.差分跳频系统相邻两跳之间通过传输的信息序列建立了一定的相关性, 在解调时利用这种相关性可以进行误跳纠正.因此, 可将频率转移函数看作一种编码器, 误跳纠正的过程就是译码的过程.
DFH编码和译码算法设计是DFH系统中的关键技术, 直接影响到DFH系统的误码率性能.文献[4]给出了一个具有最大化自由距的DFH码的实例, 针对该实例分析了维特比检测算法的译码性能.文献[5]用非二进制卷积编码等效模型对此类DFH码做了进一步描述.文献[6-7]对维特比检测算法的性能进行了分析, 但没有考虑DFH编码器的距离谱特性.本文设计了一种基于回归移位寄存器的DFH码, 定义了用于DFH码维特比检测性能分析的两个重要参数:路径重量分布和距离谱, 并给出了计算上述参数的快速算法.基于DFH码路径重量分布和距离谱特性, 采用两种不同方法推导了维特比检测算法的误比特率上界, 通过计算机仿真对理论推导结果进行了验证.最后, 对DFH码的距离谱特性进行了分析.
1 基于回归移位寄存器的DFH编码器
回归移位寄存器的状态变化过程是马尔科夫链, 将回归移位寄存器的状态映射为差分跳频系统的频率序号, 就构成了一种DFH编码器, 见图 1.
DFH编码器要求频率集的频点数M是2的正整数次幂.回归移位寄存器的级数N由频率集的频点个数M决定, 即N=log2M-1.每跳携带的比特数NBPH要小于N+1, 实际应用中NBPH的取值一般不大于4.F是映射函数, 它将移位寄存器的N+1个抽头的状态一一映射到离散集合{0, 1, …, 2N+1-1}中, 即移位寄存器每个时刻N+1个抽头的状态对应一个跳频频点fk.移位寄存器的输入ak可用下式计算
ak=uk+N∑i=1qiak−imod (1) 式中; uk为当前时刻输入的数据.
当回归系数qi∈{q1, q2, …, qN}取不同值时, 频率转移网格图的状态转移规律不会发生改变, 只是导致状态转移的触发信息发生了变化, 因此基于回归移位寄存器的DFH码的自由距完全由回归移位寄存器长度N和每跳携带的比特数HBP决定.对于处于全0状态的回归移位寄存器, 一旦有输入信息使其离开全0状态, 那么寄存器至少经过[(N+1)/NBPH]([]表示向下取整运算)次移位才能再次回到全0状态, 根据频率转移函数的自由距的定义[4]可知基于回归移位寄存器的DFH码具有最大化的自由距.
2 维特比检测算法的性能分析
维特比检测算法是一种最大似然序列译码算法, 基本思想是充分利用连续多跳的接收信号的快速傅里叶变换(Fast Fourier Transform, FFT)分析结果, 针对频率转移网格图的每个频点(状态), 比较所有转入这个频点的路径的度量, 并选择度量最大的一条路径作为幸存路径, 再将当前跳的FFT样值累加到幸存路径的度量值上.最终从频率转移网格图中选出累积度量最大的一条路径作为频率序列检测结果并最终解调出原始数据.
2.1 路径重量分布和距离谱的定义
在分析维特比检测算法性能前, 首先定义两个重要参数:路径重量分布和距离谱.
定义1 在频率转移网格图中, 从某个节点与全0路径分离, 在后续的某个节点又首次同全0路径重合的路径叫做全0路径的竞争路径.
定义2 在频率转移网格图中, 某条频率转移路径与全0路径的距离叫做该路径的重量.
定义3 假设频率转移网格图中重量为i的全0路径的竞争路径的数量为Ai, 那么集合{Adf, Adf+1, …, Ai, …}定义为DFH码的路径重量分布, 其中df为自由距.
定义4 假设频率转移网格图中所有重量为i的全0路径的竞争路径对应的输入信息序列的汉明重量为Wi, 那么集合{(df, Wdf), (df+1, Wdf+1), …, (i, Wi), …}定义为DFH码的距离谱.
假设B是有关输入信息序列汉明重量的变量, D是有关路径重量的变量[8-9], Ab, d表示汉明重量为b的信息序列产生的路径重量为d的路径的个数.定义DFH码关于输入信息汉明重量和路径重量的转移函数为
T\left( {B, D} \right) = \sum\limits_{b, d} {{A_{b, d}}{B^b}{D^d}.} (2) 通过上式可进一步得出:
\frac{{\partial T\left( {B, D} \right)}}{{\partial B}}\left| {_{B = 1}} \right. = \sum\limits_{d = {d_{\rm{f}}}}^\infty {{W_d}{D^d};} (3) T\left( {B, \mathit{D}} \right)\left| {_{B = 1}} \right. = \sum\limits_{d = {d_{\rm{f}}}}^\infty {{A_d}{D^d}.} (4) 式中: {A_d} = \sum\limits_b {{A_{b, d}}} 是DFH码的路径重量分布; Wd是DFH码的距离谱.可采用计算机搜索的方法计算Ad和Wd.
2.2 路径重量分布和距离谱的快速算法
如果计算基于回归移位寄存器的DFH码第1到i个谱分量, 首先根据回归移位寄存器的结构产生频率转移网格图, 并计算网格图中各状态返回到0状时经过的最短路径长度[l0, l1, …, ls, …, l2N-1].选择0状态为起始节点, 并将其对应的路径长度设为df+i.在网格图中搜索状态为0, 对应路径长度为0的节点.每向前搜索一步, 节点对应的路径长度相应减1.对于搜索的每个节点, 如果其对应的路径长度大于ls, 继续延伸此节点, 如果小于ls, 将得到状态非0且对应路径长度为0或负数的节点, 则停止延伸此节点.
快速算法的具体实现步骤如下:
1) 初始化.初始节点状态设为0, 其对应的路径长度设为lp←df+i, 堆栈指针设为0.
2) 查找下个节点的状态, 设置节点对应的路径长度lp←lp-1, 计算错误比特数(导致状态跃迁的输入信息的汉明重量), 将这些参数压入堆栈.
3) 如果堆栈指针大于0, 从堆栈中弹出存储的参数, 否则跳到6).
4) 查找下个节点的状态, 设置节点对应的路径长度lp←lp-1, 计算错误比特数.
5) 如果节点对应的路径长度不小于ls, 且节点状态不为0, 则将节点参数压栈, 如果节点状态为0, 则记录错误事件, 跳到3).如果节点对应的路径长度小于ls, 跳到3).
6) 结束.
2.3 AWGN信道维特比检测算法误比特率上界
假设DFH系统可用频点数为M, 每跳持续周期为T.将第i跳发送信号的等效低通表示为
{S_{i, j}}\left( t \right) = \sqrt P {{\rm{e}}^{{\rm{j2 \mathit{ π} }}{\mathit{f}_\mathit{j}}\mathit{t}}}, j = 0, 1, \cdots , M - 1. (5) 式中; P为信号功率.在加性高斯白噪声(Additive White Gaussian Noise, AWGN)信道下, 第i跳接收信号可表示为
{r_i}\left( t \right) = {s_i}\left( t \right) + n\left( t \right). (6) 式中, n(t)为AWGN, 其功率谱密度为N0/2.
对第i跳接收信号进行L(L≥M)点FFT分析可得各频点的输出幅值为
\begin{array}{l} {\mathit{Y}_\mathit{i}}\left( k \right) = \left| {{R_\mathit{i}}\left( k \right)} \right| = \left| {\sum\limits_{n = 0}^{L - 1} {{r_i}\left( n \right)} {{\rm{e}}^{ - {\rm{j}}\frac{{{\rm{2 \mathit{ π} }}\mathit{kn}}}{L}}}} \right|, \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\mathit{k} = 0, 1, \cdots , \mathit{L} - {\rm{1}}{\rm{.}} \end{array} (7) 式中, ri(n)(0≤n≤L-1)是ri(t)的L点采样信号.在第j个频点上的幅值Yi(kj)记为Yi, j.
假设网格图中的发送路径为全0路径, 全0路径的判决变量可以表示为
{\mathit{Y}_{\rm{0}}} = \sum\limits_{k = 1}^d {Y_{k, 0}^2} . (8) 它服从2d(d=df, df+1, df+2, …)个自由度的非中心χ2分布
\begin{array}{l} \mathit{p}\left( {{y_0}} \right) = \frac{1}{{{E_{\rm{s}}}{N_0}}}{\left( {\frac{{{y_0}}}{{E_{\rm{s}}^2d}}} \right)^{\frac{{d - 1}}{2}}}{{\rm{e}}^{ - \frac{{E_{\rm{s}}^2d + {y_0}}}{{{E_{\rm{s}}}{N_0}}}}}.\\ \;\;\;\;\;\;\;\;\;\;\;\;{{\rm{I}}_{\mathit{d}{\rm{ - 1}}}}\left( {\frac{{2\sqrt {{y_0}d} }}{{{N_0}}}} \right), \end{array} (9) 式中: Es为符号能量; Id(x)是d阶修正贝塞尔函数.
全0路径的竞争路径的判决变量可以表示为
\begin{array}{l} {\mathit{Y}_x} = \sum\limits_{k = 1}^d {Y_{k, {\mathit{x}_\mathit{k}}}^2} , \\ \;\;\;\;\;\;\;\;\;1 \le x \le {A_d}, 0 < {\mathit{x}_\mathit{k}} \le M - 1. \end{array} (10) 它服从2d个自由度的中心χ2分布:
\mathit{p}\left( {{y_x}} \right) = \frac{{y_x^{d - 1}}}{{{{\left( {{E_{\rm{s}}}{N_0}} \right)}^d}\left( {d - 1} \right)!}}{{\rm{e}}^{ - \frac{{{y_x}}}{{{E_{\rm{s}}}{N_0}}}}}. (11) 只有当全0路径的判决变量大于所有竞争路径的判决变量时, 才能做出正确的判决.因此, 可以直接推导出正确判决的概率为
\begin{array}{l} {\mathit{P}_\mathit{c}}\left( d \right) = \int_0^\infty {P{{\left( {{y_x} < {y_0}} \right)}^{{A_d}}}p\left( {{y_0}} \right)} {\rm{d}}{y_0}\\ \;\;\;\;\;\;\;\;\; = {\int_0^\infty {\left[ {\int_0^{{y_0}} {p\left( {{y_x}} \right)} {\rm{d}}{y_x}} \right]} ^{{A_d}}}p\left( {{y_0}} \right){\rm{d}}{y_0}\\ \;\;\;\;\;\;\;\;\; = {\int_0^\infty {\left[ {1 - {{\rm{e}}^{ - \frac{{{y_0}}}{{{E_{\rm{s}}}{N_0}}}}}{{\sum\limits_{k = 0}^{d - 1} {\frac{1}{{k!}}\left( {\frac{{{y_0}}}{{{E_{\rm{s}}}{N_0}}}} \right)} }^k}} \right]} ^{{A_d}}}\\ \;\;\;\;\;\;\;\;\;\;\;\;p\left( {{y_0}} \right){\rm{d}}{y_0}, \end{array} (12) 那么错误判决概率为
{\mathit{P}_{\rm{e}}}\left( d \right) = 1 - {\mathit{P}_{\rm{c}}}\left( d \right). (13) 将对应于不同路径重量的所有错误判决的概率求和, 得到错误判决的上界为
{\mathit{P}_{\rm{e}}} \le \sum\limits_{d = {d_{\rm{f}}}}^\infty {{\mathit{P}_{\rm{e}}}\left( d \right).} (14) 每次错误判决导致的平均错误比特数为Wd/Ad, 因此, 误比特率上界为
{\mathit{P}_{\rm{b}}} \le \sum\limits_{d = {d_{\rm{f}}}}^\infty {{\mathit{W}_\mathit{d}}{\mathit{P}_{\rm{e}}}\left( d \right) / {A_d}.} (15) 由于式(15)没有闭式表达, 误比特率上界需要通过数值积分来计算.
另外, 可以直接采用文献[10]给出的首错事件概率计算方法.假设网格图中的发送路径为全0路径, 接收机错误选择全0路经的竞争路径的概率就是首错事件的概率.重量为d的全0路径的竞争路径的首错事件概率可以表示为
\begin{array}{l} {\mathit{P}_2}\left( d \right) = \frac{1}{{{2^{2d - 1}}}}{{\rm{e}}^{ - \frac{{dy}}{2}}}\sum\limits_{n = 0}^{d - 1} {\frac{1}{{n!}}} \\ \;\;\;\;\;\;\;\;\;\;\;\;\left( {\sum\limits_{k = 0}^{d - 1 - n} {\left( \begin{array}{l} 2d - 1\\ \;\;\;\;k \end{array} \right)} } \right){\left( {\frac{{d\gamma }}{2}} \right)^n}. \end{array} (16) 式中, γ=Es/N0.
重量为d的全0路径的竞争路径会有多条, 而定义的路径重量分布Ad描述了重量为d的全0路径的竞争路径的数量, 因此可以将d为不同值的所有首错事件概率求和, 得到首错事件概率联合界(上界)
{\mathit{P}_{\rm{e}}} \le \sum\limits_{d = {d_{\rm{f}}}}^\infty {{A_\mathit{d}}{\mathit{P}_2}\left( d \right).} (17) 同样, 描述了重量为d的Ad个竞争路径对应的错误比特数, 因此, 误比特率上界为
{P_{\rm{b}}} \le \sum\limits_{d = {d_{\rm{f}}}}^\infty {{W_d}{P_2}\left( d \right).} (18) 2.4 仿真验证
为验证理论推导的正确性, 在AWGN信道下对DFH码维特比检测算法的性能进行了计算机仿真, 设置的仿真条件如表 1所示.
表 1 维特比检测算法性能仿真条件频率点数 回归移位寄存器级数 回归系数 帧长 BPH 8 2 (0, 0) 1 600 1 图 2给出了仿真得到的DFH码维特比检测算法性能曲线和采用数值计算法的误比特率上界.
从图 2可以看出, 在系统频率集频点数为8个, 误比特率低于10-3时, 理论推导的误比特率上界所给出的性能估计同仿真结果非常接近.
图 3给出了采用数值计算法和首错事件法计算的误比特率上界.
从图 3可以看出, 采用数值计算法得到的维特比检测算法误比特率上界较首错事件法计算得到的误比特率上界更紧.
3 距离谱性能分析
根据上文给出的DFH码距离谱的快速算法, 计算了回归移位寄存器级数为2, 回归系数[q1, q2]分别取[0, 0]、[0, 1]、[1,0]、[1,1]时的DFH码路径分布Ad和距离谱Wd, 见表 2和3.
表 2 DFH码的路径分布回归系数 A4 A5 A6 A7 A8 A9 A10 A11 A12 x, x 1 1 2 4 7 13 24 44 81 注:表中x在(0, 1)中取值. 表 3 DFH码的距离谱回归系数 W4 W5 W6 W7 W8 W9 W10 W11 W12 0, 0 1 2 5 12 26 56 118 244 499 0, 1 2 4 10 16 36 72 140 280 550 1, 0 2 4 6 16 32 64 132 264 526 1, 1 3 4 7 18 34 68 138 272 537 从表 2和3可以看出, 当回归系数取不同值时, DFH码的路径分布Ad完全相同, 回归系数只会影响DFH码的距离谱Wd, 而对路径分布Ad没有影响.回归系数为[0, 0](无反馈环节)的DFH码的谱分量总是小于回归系数为其他值时DFH码的谱分量.这说明在使用维特比检测算法时, 无反馈环节的DFH码性能要好于有反馈环节的DFH码.在选择DFH码时, 应主要考察参数df和Wd.自由距df尽可能大, 距离谱Wd尽可能小的是好码.实际上, 有反馈环节的DFH码具有无限冲激响应特性, 可用于Turbo-DFH系统中[11-12], 采用并行级联编码和迭代译码算法时, 可以获得较维特比检测算法更好的性能.
4 结论
设计了一种基于回归移位寄存器的DFH码.定义了DFH码的路径重量分布和距离谱, 并给出了它们的快速算法.采用两种不同方法推导了维特比检测算法的误比特率上界, 并通过计算机仿真对理论推导结果进行了验证, 数值计算法给出的误比特率上界较首错事件算法给出的更紧.对DFH码距离谱特性的分析表明, 自由距尽可能大, 距离谱尽可能小的DFH码是好码.
-
表 1 维特比检测算法性能仿真条件
频率点数 回归移位寄存器级数 回归系数 帧长 BPH 8 2 (0, 0) 1 600 1 表 2 DFH码的路径分布
回归系数 A4 A5 A6 A7 A8 A9 A10 A11 A12 x, x 1 1 2 4 7 13 24 44 81 注:表中x在(0, 1)中取值. 表 3 DFH码的距离谱
回归系数 W4 W5 W6 W7 W8 W9 W10 W11 W12 0, 0 1 2 5 12 26 56 118 244 499 0, 1 2 4 10 16 36 72 140 280 550 1, 0 2 4 6 16 32 64 132 264 526 1, 1 3 4 7 18 34 68 138 272 537 -
[1] HERRICK D L, LEE P K. CHESS: A new reliable high speed HF radio[C]//MILCOM'96. McLean Virginia, 1996: 684-690.
[2] HERRICK D L, LEE P K. Correlated frequency hopping: an improved approach to HF spread spectrum communications[C]//The Tactical Communications Conference. Washington D C, 1996: 319-324.
[3] MILLS D G, EDELSON G S, EGNOR D E. A multiple access differential frequency hopping system[C]//MILCOM'03, 2003: 1184-1189.
[4] 潘武, 周世东, 姚彦.差分跳频通信系统性能分析[J].电子学报, 1999, 27(11A): 102-104. http://d.old.wanfangdata.com.cn/Periodical/dianzixb1999Z1025 PAN Wu, ZHOU Shidong, YAO Yan. Performance analysis of differential frequency hopping communication system[J]. Acta Electronica Sinica, 1999, 27(11A): 102-104.(in Chinese) http://d.old.wanfangdata.com.cn/Periodical/dianzixb1999Z1025
[5] 董彬虹, 李少谦.差分跳频信号最佳接收机设计[J].电子科技大学学报, 2003, 32(5): 530-534. doi: 10.3969/j.issn.1001-0548.2003.05.014 DONG Binhong, LI Shaoqian. Design of Optium Receiver for DFH Signal[J]. Journal of UEST of China, 2003, 32(5): 530-534.(in Chinese) doi: 10.3969/j.issn.1001-0548.2003.05.014
[6] 陈智, 李少谦, 董彬虹. AWGN下差分跳频通信系统的性能分析[J].信号处理, 2006, 22(6): 891-894. doi: 10.3969/j.issn.1003-0530.2006.06.026 CHEN Zhi, LI Shaoqian, DONG Binhong. Performance analysis of differential frequency hopping system in AWGN[J]. Signal Processing, 2006, 22(6): 891-894. doi: 10.3969/j.issn.1003-0530.2006.06.026
[7] 熊俊俏, 甘良才, 朱毅超.短波差分跳频系统序列译码的性能分析[J].系统工程与电子技术, 2011, 33(2): 399-403. doi: 10.3969/j.issn.1001-506X.2011.02.34 XIONG Junqiao, GAN Liangcai, ZHU Yichao. Performance analysis of sequence decoded short wave dif-ferential frequency hopping systems[J]. Systems Engineering and Electronics, 2011, 33(2): 399-403. (in Chinese) doi: 10.3969/j.issn.1001-506X.2011.02.34
[8] BERROU C, GLAVIEUX A. Near optimum error correcting coding and decoding: Turbo-codes[J]. IEEE Trans Commun, 1996: 44(10): 1261-1271. doi: 10.1109/26.539767
[9] 曹志刚, 钱亚生.现代通信原理[M].北京:清华大学出版社, 1992. CAO Zhigang, QIAN Yasheng. Modern Communication Principles[M]. Beijing: Tsinghua University press, 1992.(in Chinese)
[10] PROAKIS J G. Digital Communications[M]. 4th ed. Beijing: Publishing House of Electronics Industry, 2001.
[11] 裴小东, 何遵文, 匡镜明. Turbo-DFH编码调制与迭代译码[J].北京理工大学学报, 2005, 25(11): 981-984. doi: 10.3969/j.issn.1001-0645.2005.11.010 PEI Xiaodong, HE Zunwen, KUANG Jingming. Turbo-DFH-coded modulation and iterative decoding[J]. Transactions of Beijing Institute of Technology, 2005, 25(11): 981-984.(in Chinese) doi: 10.3969/j.issn.1001-0645.2005.11.010
[12] 裴小东, 何遵文, 匡镜明. Turbo-DFH迭代译码算法[J].电子科技大学学报, 2007, 36(1): 57-59. doi: 10.3969/j.issn.1001-0548.2007.01.018 PEI Xiaodong, HE Zunwen, KUANG Jingming. Iterative decoding algorithm for Turbo-DFH system[J]. Journal of UEST of China, 2007, 36(1): 57-59.(in Chinese) doi: 10.3969/j.issn.1001-0548.2007.01.018
[13] CEDERVALL M, JOHANNESSON R. A fast algorithm for computing distance spectrum of convolutional codes[J]. IEEE Trans Inform Theory, 1989, 35 (6): 1146-1159. doi: 10.1109/18.45271
[14] 陈智, 李少谦, 董彬虹.瑞利衰落信道下差分跳频通信系统的性能分析[J].电波科学学报, 2007, 22(1): 126-129. doi: 10.3969/j.issn.1005-0388.2007.01.026 CHEN Zhi, LI Shaoqian, DONG Binhong. Performance analysis of differential frequency hopping system over Rayleigh fading channels[J]. Chinese Journal of Radio Science, 2007, 22(1): 126-129.(in Chinese) doi: 10.3969/j.issn.1005-0388.2007.01.026
[15] 朱毅超, 甘良才, 熊俊俏, 等. BICM在差分跳频系统中的应用[J].电波科学学报, 2009, 24(1): 15-21. doi: 10.3969/j.issn.1005-0388.2009.01.003 ZHU Yichao, GAN Liangcai, XIONG Junqiao. Performance of BICM in the differential frequency hopping system[J]. Chinese Journal of Radio Science, 2009, 24(1): 15-21.(in Chinese) doi: 10.3969/j.issn.1005-0388.2009.01.003