递归网络

递归网络（精选9篇）

递归网络 篇1

模糊模型与神经网络的结合在系统辨识中得到广泛应用,这样既克服了模糊建模方法缺乏学习能力、辨识过程复杂、模型参数优化难以设定的缺点,又充分发挥了神经网络较强的自学习和优化能力的优点。前向网络(FNN)和递归网络(RFNN)是模糊神经网络的两大分支[1]。其中,T-S模糊模型的神经网络(TSFNN)成为众多学者研究的热点。但是TSFNN模糊神经网络是静态映射,在线训练中,权值的调节不能充分利用动态数据信息,因而函数逼近对训练数据敏感[2]。这类常规TSFNN被限制在静态系统中。针对上述缺陷,笔者提出一种新的递归T-S模型的模糊神经网络(TSRFNN),其特点是通过在输入-输出层之间加上动态元件,使得网络具有记忆暂态信息的能力。

1 递归

T-S模型的神经网络结构T-S模型的前件和后件与网络的节点函数有明显的对应关系。在结构辨识中,采用无监督聚类算法[3,4],根据已知的输入输出数据自动地划分输入-输出空间,确定模糊规则数目及其每条规则的前提参数。在参数辨识中采用动态反响传播算法(DBP),辨识部分参数。该神经网络结构如图1所示。

如图1所示模糊神经网络包括前件和后件两部分。TSRFNN的模糊规则具体形式为:

Rj:如果x1是A${}_1^j$and x2是A${}_2^j$and…and xn是A${}_n^j$,则

yj=pj0+pj1x1+…+pjnxn,j=1,2,…,m (1)

式中 A${}_i^j$——模糊子集;

m ——规则的数目;

Rj ——第j条模糊规则;

yj ——第j条输出规则。

递归T-S模糊模型的神经网络结构内部机理如下:

a. 第一层作为输入层,输入向量的各分量通过该节点,把输入向量的值传到下一层。

b. 第二层作用是计算上层节点传递值的隶属度函数。

c. 第三层是规则层,每个节点表示一条相应的模糊规则,对规则的前件进行匹配,得到对应规则的适应度值,即:

aj=min{μ${}_1^{i{}_1}$,μ${}_2^{i{}_2}$,…,μ${}_n^{i{}_n}$} (2)

其中$i{}_1\in \{1,2,\cdots ,m{}_1\},i{}_2\in \{1,2,\cdots ,m{}_2\},\cdots ,i{}_n\in \{1,2,\cdots ,m{}_n\},j=1,2,\cdots ,m,m={\displaystyle \prod _{i=1}^{n}m}{}_i$。

d. 第四层作为运算层,对前面的变量进行归一化计算处理,即:

$\overline{a{}_j}=a{}_j/{\displaystyle \sum _{j=1}^{{\rm N}{}^m}a}{}_j,j=1,2,\cdots ‚m$ (3)

e. 第五、六层作为递归T-S模糊模型的后件,其表达式为yj=pj0+pj1x1+…+pjnxn。

f. 第七、八层的功能是把模糊规则映射到输出空间,形式是$y={\displaystyle \sum \overline{a{}_j}}\times y{}_j$。

g. 第八、九层加入具有记忆性功能的元件W(z-1)=z-1。在此递归网络中,作为递归环节将该元件的输出反馈到网络前件第m个输入中,此反馈环节使整个网络具有了递归的特性。因此,TSRFNN网络的输出既与当前时刻的输入数据有关,又与上一时刻的输出数据相关联。

2 递归T-S模型的模糊神经网络逼近性证明

模糊规则的一般形式如式(1)所示。输入变量模糊集合的隶属度函数采用高斯函数,输出变量的隶属度函数为模糊单点,采用乘积求和加权平均的解模糊方法[5],系统的输出为:

$Y=f(x)={\displaystyle \sum _{j=1}^{{\rm N}}\overline{y{}^j}}[{\displaystyle \prod _{i=1}^n\mu }A{}_i^j(x{}_i)]/{\displaystyle \sum _{j=1}^{{\rm N}}[}{\displaystyle \prod _{i=1}^n\mu }A{}_i^j(x{}_i)]$ (4)

其中

$p{}_j(x)={\displaystyle \prod _{i=1}^n\mu }A{}_i^j(x{}_i)/{\displaystyle \sum _{j=1}^{{\rm N}}[}{\displaystyle \prod _{i=1}^n\mu }A{}_i^j(x{}_i)$ (5)

称为模糊基函数[6](FBF),是模糊系统的模糊基函数展开式。

基函数逼近定理 设所有FBF展开式包含于集合Y中,在集合U⊂Rn上的所有的连续实函数s和任何ε>0,都可以找到f<Y,并且下式成立:

$\underset{x\in U}{{\displaystyle \max }}|s(x)-f(x)|＜\epsilon$ (6)

图1所示的递归T-S模型的模糊神经网络的输出为:

$\begin{array}{l}y={\displaystyle \sum _{k=1}^{{\rm N}}(}p{}_{k0}+p{}_{k1}x{}_1+\cdots +p{}_{km}x{}_m)a{}_k/{\displaystyle \sum _{k=1}^{{\rm N}}a}{}_k\\ ={\displaystyle \sum _{k=1}^{{\rm N}}(}p{}_{k0}+p{}_{k1}x{}_1+\cdots +p{}_{km}x{}_m)a{}_k/\overline{a{}_k}(7)\end{array}$

其中$a{}_k=A{}_{k1}(x{}_1)\cdot A{}_{k2}(x{}_2)‚\overline{a{}_k}=a{}_k/{\displaystyle \sum _{m=1}^{{\rm N}}a}{}_m$。

可以看出式(7)具有FBF的形式,故基于T-S模型的模糊神经模型的输出符合基函数FBF展开式的逼近性,即该模型能够很好地逼近非线性动态系统。

3 递归T-S模糊神经网络在系统辨识中的应用

递归T-S模糊网络在系统动态辨识应用中包括两个过程:系统的结构辨识和参数辨识[7]。笔者在系统结构辨识中采用无监督模糊聚类方法,在参数辨识中采用动态BP算法。

3.1 结构辨识

在提取模糊规则中,不仅要搜集输入-输出数据,并且详细分析系统的内部信息。可是,一般情形下,直接获取系统内部信息是十分困难的。因此,聚类方法就成为获取模糊规则的一种行之有效的方法,笔者采用无监督聚类算法[8]。设X={x1,x2,…,xp}是p个输入-输出样本数据的集合,其中xk=(x1k,x2k,…,x${}_m^k$,yk)是第k个输入-输出样本数据,(x1k,x2k,…,xmk)是第k个样本的m个输入,yk是第k个输入相应的输出。无监督聚类算法就是把每个样本都作为聚类中心,即:

vk=xk,k=1,2,…,p (8)

具体步骤如下:

a. 计算聚类中心与样本空间其他矢量的相关性。

rk1=exp[-‖vk-vi‖2/(2b2)],k=1,2,…,p;l=1,2,…,p (9)

式中 b——隶属函数的宽度;

‖vk-vi‖ ——vk与vi的欧式距离值。

b. 调整vk与vi的相关性。

c. 算出跟聚类矢量vk相关性大的全部矢量均值。

$\begin{array}{l}z{}^k=\{z{}_1{}^k,z{}_2{}^k,\cdots ,z{}_{m+1}{}^k\}\\ z{}_m{}^k={\displaystyle \sum _{i=1}^{p}r}{}_{kl}v{}^l/{\displaystyle \sum _{i=1}^{p}r}{}_{kl}‚k=1,2,\cdots ,p(10)\end{array}$

d. 若所有的zk与vk(k=1,2,…,p)均相同,则转到步骤e;否则,令vk=zk,返回到步骤b再次计算。

e. 最后得到的zk集合,相关性大的矢量具有同样的收敛矢量,且被划为同一类,收敛矢量的值即聚类中心,也作为隶属函数的中心。收敛矢量的个数既是聚类的个数,也是设计时需要考虑的隶属函数个数。

3.2 参数辨识

经过上面步骤得到递归T-S模糊网络的前件,下面的工作是对后件中的参数进行辨识。目标设定为下式:

$J=\frac{1}{2}[y{}_{\text{d}}(t)-y(t)]{}^2=\frac{1}{2}e(t){}^2$ (11)

式中 y(t)——系统当前时刻的输出;

yd(t) ——系统的期望输出。

目标采用DBP算法最小化目标函数[9]。

经过上面的步骤,笔者构造出了基于T-S模糊模型的递归神经网络和推导出其学习算法,考虑到学习算法的整体最优[10],选择学习率取为0.01。

4 仿真

本节先后采用常规TSFNN神经网络和带递归环节的TSRFNN神经网络来辨识同一个非线性系统。仿真对象是非线性函数:

y=0.5sin(πx)+0.3sin(3πx)+0.1sin(5πx) (12)

用函数随机产生200组数据作为样本进行训练,按照同样方法随机产生测试样本进行测试。首先采用模糊聚类方法将样本进行聚类处理,经过此步骤获得输入和输出数据的隶属度(高斯函数)中心,将高斯函数(隶属函数)宽度设定为0.2。通过对训练样本数据分析聚类后,对含递归的TSRFNN网络进行训练,学习效率取0.01,训练次数为150,结果如图2～5所示。

从仿真图2可以看出在非线性函数变化率大的地方TSFNN网络不能很好地跟随系统的变化,而图4采用TSRFNN网络就能够起到动态预测的功能,取得较好的泛化效果。比较图3、5的检验误差可以看出在辨识非线性系统中能够获得较高精度的逼近性的原因,在于TSRFNN含有递归环节并且有记忆特性,从而能够抑制运算过程中向量维数的级数增长带来的维数扩张,表现出优良的动态特性。

5 结束语

笔者提出的递归T-S模糊模型对非线性函数辨识实验,由仿真结果和前节证明可知该网络可以逼近复杂的非线性函数;减少模糊规则的数量,同时系统的网络结构得到简化。对于不了解内部机理的系统,可根据输入-输出数据对象进行准确的辨识。神经网络和递归T-S模糊模型的有机结合不仅增强了其学习能力和数据泛化能力,而且自适应能力和收敛速度也得到提高。

摘要：在常规T-S模糊神经网络的基础上加入动态递归元件,提出了递归T-S模糊模型的神经网络。在系统辨识中采用无监督聚类算法和动态反向传播算法训练该递归神经网络的参数,给出了该递归网络的逼近性证明。辨识效果与常规T-S模糊模型作比较,说明递归T-S模糊模型的神经网络在非线性系统辨识中表现出更好的性能。

关键词：递归神经网络,T-S模糊模型,非线性系统辨识建摸,模糊基函数,无监督聚类算法,动态BP算法

参考文献

[1]卢志刚,吴士昌,于灵慧.非线性自适应逆控制及其应用[M].北京:国防工业出版社,2004.

[2]Jang J-S R,Sun C-T T.Neuro-Fuzzy Model and Control[J].Proceedings of the IEEE,1955,83(3):378～406.

[3]Fahd A A,Abdennour A B.Neuro-Fuzzy Control of aSteam Boiler-Turbine Unit[C].Processing of the IEEEInternational Conference on Control Application.USA:IEEE,1999:1050～1055.

[4]师黎,陈铁军.智能控制[M].北京:清华大学出版社,2008:125～133.

[5]李国勇.智能预测控制及其MATLAB实现[M].第2版.北京:电子工业出版社,2010:250～254.

[6]Takagi T,Sugeno M.Fuzzy Identification of Systems andIts Application to Modeling and Control[J].IEEETransactions on Systems,Man and Cybernetics,1985,15(1):116～132.

[7]Wang C C,Lin N S.Rule Extraction for Fuzzy LogicControl and Decision System[J].IEEE Transactions onComputers,1991,40(12):1320～1336.

[8]张凯,钱锋,刘漫丹.模糊神经网络技术综述[J].信息与控制,2005,32(5):431～435.

[9]李香娜.基于T-S模糊模型的酸碱中和过程的系统辨识[J].华北科技学院学报,2010,7(3):56～60.

[10]Sugeno M,Kang G T.Structure Identification of FuzzyModel[J].Fuzzy Sets and Systems,1988,28(1):15～33.

递归网络 篇2

如：abcdedbca就是回文，判断一个面试者对递归理解的简单程序

int find(char *str, int n) {

if(n<=1) return 1;

else if(str[0]==str[n-1]) return find(str+1, n-2);

else return 0;

}

int main(int argc, char* argv[]) {

char *str = “abcdedcba”;

printf(“%s: %s ”, str, find(str, strlen(str)) ? “Yes” : “No”);

递归网络 篇3

关键词：冗余机械臂,重复运动规划,二次规划,对偶神经网络

1 概述

机械臂是一个末端能动机械装置, 其末端运动任务包括焊接、油漆、分捡等, 广泛应用于装备制造、产品加工、零件分类等实际工程中, 特别地, 机械臂末端执行器做封闭轨迹的重复作业很常见。冗余度机械臂运动的非重复性可能产生不期望的关节位形, 使冗余度机器人末端封闭轨迹的重复作业出现预料之外的情况, 甚至会导致意外及危险情况的发生。以往学者们对于冗余度机器手臂的重复运动问题主要是基于伪逆的方法[1]或基于复杂的控制理论方法, 但是这种基于伪逆方法的求解方式涉及矩阵求逆和相乘, 计算量大, 并且在处理不等式约束上有困难。近年来, 有研究表明这样一个冗余度解析问题可通过在线优化技术[2]更好地求解, 例如采用二次规划[3]和递归神经网络的方法[4]。

文章考虑冗余度机器手臂的重复运动规划问题, 将这一规划问题转化为一个二次型优化方案, 可以克服传统方法中求伪逆的困难, 并且易于实时控制。

2 问题描述

机械臂的运动学问题中末端执行器的位置向量r (t) 与关节向量θ (t) 的关系可用如下关系式表述:

式中:θ (t) 表示维数为n的关节向量, r (t) ∈Rm表示末端执行器的位置向量, f (·) 表示给定机械手臂的关于结构和参数的连续非线性函数。

一般地, 对 (1) 式进行求微分, 可得到速度层的关系式, 即笛卡尔速度和关节速度的关系。

式中:为f的雅克比矩阵[5], 因为冗余机械臂m<n, 所以式 (1) 和式 (2) 就可能存在多个解或无穷多解。通常用伪逆方法求解式 (2) , 得不到闭合末端执行器轨迹的闭合关节轨迹, 也就是说伪逆方法通常不能解决机械臂的重复运动问题[5]。

为了解决这一关节角偏差问题使得机械臂做重复运动, 采用求解最小化关节的当前位置和初始位置间的位移量的最优解, 从而能减小甚至消除关节角偏差现象。因此, 考虑优化性能指标:

式中:c=λ (θ-θ (0) ) , λ>0是用来控制关节位移幅值的正设计参数。

实际上, 机械臂存在一定的物理约束, 所以在考虑机械臂的关节角度极限约束[θ-, θ+]和关节速度极限约束的情况下, 可将冗余机械臂重复运动规划问题表述如下:

式中:θ-, θ+表示关节向量的上下物理极限, 表示关节速度向量的上下物理极限。将其合并为双端约束不等式:, 其中ξ-和ξ+的第i个元素定义如下:

其中, μ>0是用来调节关节速度的可行域。

经进一步转化, 该问题便可表述为如下二次型规划形式:

式中,

令, 则上述优化问题可转化为如下具有不等式约束的标准二次规划问题形式:

3 神经动态优化求解

神经动态优化方法的基本思想是根据优化问题设计出合适的神经网络结构, 然后利用能量函数法计算网络参数, 利用神经网络的并行运算特性快速找到优化问题的解。文章将利用一种单层递归神经网络模型[6]求解二次规划问题, 神经网络模型如下:

其中, z∈Rm+n是神经元状态变量, ε是神经网络收敛率参数, g (v) 是一个神经元的投影分段函数, 满足:

4 数值仿真

本节以平面六连杆冗余机械臂末端执行器作来回直线运动为例进行计算机仿真验证。直线长度为1m, 观察其关节轨迹能否重合。末端执行器的运动周期为8s, 关节变量的初始状态为:θ (0) = (0, -π/4, 0, π/2, 0, -π/4) T弧度。仿真结果如图1所示, 从图1也可以看出, 在经过8s周期运动之后, 平面六连杆机器手臂的各自关节状态都回到初始状态;仿真结果达到预期的目的, 且其最大位置误差不大于1.79×10-6。可见, 利用所提出的规划解析方案对带关节物理约束的机械臂进行重复运动规划是可行、有效的。

5 结束语

针对平面冗余机械臂重复运动规划问题, 文章首先将机械臂重复运动问题转化为一个二次型规划问题, 该二次规划方案可避开传统的伪逆解析方案难以求逆的问题, 然后利用一种简单对偶神经网络来求解该含不等式约束的二次规划问题, 该实现算法具有并行性、快速实时处理能力和电路实现性。

参考文献

[1]Malysz P, Sirouspour S.A kinematic control framework for singleslave asymmetric teleoperation systems.IEEE Transactions on Robotics, 2011, 27 (5) :901-917.

[2]张智军, 张雨浓.重复运动速度层和加速度层方案的等效性[J].自动化学报, 2013, 39 (1) :88-91.

[3]Zhang Y N, Xie L, Zhang Z J, Li K N, Xiao L.Real-time joystick control and experiments of redundant manipulators using cosine-based velocity mapping.Proceedings of the 2011 IEEE International Conference on Automation and Logistics.Chongqing, China:IEEE, 2011:345-350.

[4]Zhang Y N, Tan Z G, Chen K, Yang Z, Lv X J.Repetitive motion of redundant robots planned by three kinds of recurrent neural networks and illustrated with a four-link planar manipulator's straight-line example.Robotics and Autonomous Systems, 2009, 57 (6-7) :645-651.

[5]张雨浓, 郭东生, 蔡炳煌, 等.基于新型性能指标的冗余度机械臂重复运动规划之方案分析与验证[J].武汉理工大学学报 (交通科学与工程版) , 2011, 35 (1) :67-70.

后序遍历非递归算法 篇4

typedef enum{L,R} tagtype;

typedef struct

{

Bitree ptr;

tagtype tag;

}stacknode;

typedef struct

{

stacknode Elem[maxsize];

int top;

}SqStack;

//后序遍历

void PostOrderUnrec(Bitree t)

{

SqStack s;

stacknode x;

StackInit(s);

p=t;

do

{

while (p!=null) //遍历左子树

{

x.ptr = p;

x.tag = L; //标记为左子树

push(s,x);

p=p->lchild;

}

while (!StackEmpty(s) &&s.Elem[s.top].tag==R)

{

x = pop(s);

p = x.ptr;

visite(p->data); //tag为R，表示右子树访问完毕，故访问根结点

}

if (!StackEmpty(s))

{

s.Elem[s.top].tag =R; //遍历右子树

p=s.Elem[s.top].ptr->rchild;

}

}while (!StackEmpty(s));

递归网络 篇5

神经网络由于具有理论上能逼近任意非线性函数的能力,在非线性系统的辨识中有着广泛的应用。传统的前向神经网络属于静态网络,在处理非线性动态系统的应用中存在很多不足。递归神经网络能通过内部反馈环节自动存储动态信息并实现动态映射,用于系统辨识时无需知道详细的对象知识,特别不需要假定模型的阶次,这是其突出的优点。正因如此,近年来递归神经网络的研究引起了人们的极大兴趣[1]。但目前沿用的仍是Pineda提出的递归神经网络的BP学习算法,它是依据梯度法来进行的,因此会产生局部收敛和收敛速度慢等缺陷。本文将LM算法应用于目前应用较多的对角递归神经网络,并在非线性动态系统建模中与BP学习算法的递归神经网络进行比较,发现前者明显优于后者。

1LM算法

LM算法是牛顿法的变形,用以最小化那些作为其它非线性函数平方和的函数。构造优化性能指数F(W)的算法,其目的是求出使F(W)最小化的W值。假设F(W)是平方函数之和,即:

undefined。 (1)

那么第j个梯度分量[∇F(W)]j为:

undefined。 (2)

由此梯度∇F(W)可以写成矩阵形式:

∇F(W)=2JT(W)e(W) 。 (3)

其中:J(W)为雅可比矩阵,即:

undefined

。 (4)

下一步计算赫森矩阵∇2F(W),其中赫森矩阵的第k,j元素为:

undefined。 (5)

则 ∇2F(W)=2JT(W)J(W)+2S(W) 。 (6)

其中:undefined。如果假设S(W)很小,则:

∇2F(W)≌2JT(W)J(W) 。 (7)

根据牛顿法的迭代关系有:

Wk+1=Wk-(∇2F(W))-1∇F(W) 。 (8)

把式(3)、式(7)代入式(8),可得:

Wk+1=Wk-[JT(Wk)J(Wk)]-1JT(Wk)e(Wk) 。 (9)

由于矩阵H=JTJ可能不可逆,这可以用下述近似赫森矩阵改进:

G=H+μI 。 (10)

其中:I为单位矩阵;μ为系数。该矩阵是可逆的,则:

Wk+1=Wk-[JT(Wk)J(Wk)+μkI]-1JT(Wk)·e(Wk) 。 (11)

或 ΔWk=-[JT(Wk)J(Wk)+μkI]-1JT(Wk)·e(Wk) 。 (12)

这种算法的特点是:不需要计算二阶导数。当μk增加时,它接近于有效学习速度的最速下降算法:

undefined。 (13)

当μk下降到0的时候,算法变成了:

Wk+1=Wk-[JT(Wk)J(Wk)]-1JT(Wk)e(Wk) 。 (14)

式(14)即为牛顿法的变形。

算法开始时,μk取小值。如果某一步不能减小F(W)值,则将μk乘以一个θ>1后再重复这一步,最后F(W)会下降。如果某一步产生了更小的F(W),则μk在下一步被除以θ,可以提高收敛速度。这样该算法提供了快速性和收敛性之间的一个折衷[2]。

2对角递归神经网络的LM学习算法

对角递归神经网络(Diagonal Recurrent Neural Network,DRNN)是一个三层网络[1,3]。设在每个离散时刻k网络输入为ui(k),i=1,2,…,m;网络输出为y(k);隐层输入、输出分别为xj(k)、rj(k),j=1,2…,q;输入层至隐层的连接权为whji;隐层至输出层的连接权为wundefined;递归神经元连接权为wundefined;记ND={Um,Hq,Yn}。为了计算和训练方便,取一个输出(对于多输出情况与此相似),即n=1,ND={Um,Hq,Y1}。则DRNN输入、输出关系为:

undefined。 (15)

rj(k)=f(xj(k)) 。 (16)

undefined。 (17)

设网络的期望输出为z(k),取性能指标函数为:

undefined。 (18)

undefined。 (19)

设undefined,则:

undefined。 (20)

undefined。 (21)

设undefined,则:

undefined。 (22)

undefined。 (23)

所以

undefined

。 (24)

其中:i=1,2,…,m,是待求权的数目。由此得出DRNN的LM学习算法具体步骤如下:

(1) 初始化权值和所有其它参数,使W(0)=random(·),P(0)、Q(0)为适当的值。

(2) k←1。

(3) 取当前最新的样本数据(Uk,Zk),按式(16)和式(17)计算DRNN的隐含层输出rj(k)和网络输出y(k),计算目标函数F(k)。

(4) 计算e(k)=z(k)-y(k)。

(5) 按式(24)构成J(Wk)阵。

(6) 计算ΔWk=-[JT(Wk)J(Wk)+μkI]-1·JT(Wk)e(k)。

(7) 用Wk+ΔWk重复计算目标函数。若新的计算结果小于原来的计算结果,则把μk除以θ,并设Wk+1=Wk+ΔWk,转第(3)步;若新的计算结果没有减少,则μk乘以θ,转第(6)步。当误差平方和减小到某个目标误差时,算法被认为收敛。

3非线性动态系统的仿真研究

严格地讲,实际过程都是非线性的,是非线性动态系统,所以非线性动态系统的建模难以避免。本文应用所提出的算法对非线性动态系统建模进行了仿真研究,取得了很好的效果。

假设系统结构未知,非线性系统模型为:

y(u)=8+2e1-u2cos(2πu) 。

其中:输入样本集u==0∶0.04∶4 。

选择DRNN为模型训练网络,输入为u(k),输出为y(k);选择DRNN的结构为(2,7,1)。为进行比较,分别对BP算法和LM算法进行训练,均训练100步。采用BP算法训练该网络,学习速率η=0.45,仿真结果见图1(a)。采用LM算法,设参数P(0)=0、Q(0)=0,仿真结果见图1(b)。比较二者可知,在同样的训练次数下,用对角递归神经网络LM的学习算法建立的非线性系统模型比用BP算法建立的模型精度要高,说明LM算法较BP算法收敛速度快。

4结论

本文将LM算法引入对角递归神经网络的权值学习中,克服了传统的递归BP算法收敛速度慢的缺陷。仿真结果表明所提出的对角递归神经网络LM算法比传统递归BP算法有更快的收敛性和更高的辨识精度,用于非线性动态系统建模是有效的。

摘要：针对递归神经网络传统BP学习算法收敛慢的缺陷,将Levenberg-Marquardt(LM)算法引入到对角递归神经网络权值的训练,这种算法提供了快速性与收敛性之间的一个折衷。仿真结果表明,该算法比传统BP算法具有更快的收敛速度,用于非线性动态系统的建模是有效的。

关键词：对角递归神经网络,LM算法,非线性动态系统,系统建模

参考文献

[1]徐丽娜.神经网络控制[M].北京:电子工业出版社,2003.

[2]哈根.神经网络设计[M].戴葵,译.北京:机械工业出版社,2002.

递归网络 篇6

在轧钢系统中,精轧机液压压下机架的两侧采用的是独立的压下缸及伺服系统,如图1所示,由于两侧液压压下系统具有不同的动态响应特性,如果不能保证两侧压下速度、位置同步,将出现两侧辊缝不同的调节速度,从而造成带钢横向厚度不均匀,直接影响带材的板形质量,在高速轧制时,由于两侧压下系统特性的不一致,带材可能会产生单边浪,甚至产生带材跑偏、断带等[1,2]。在本文中,将基于对角递归网络(diagonal recurrent neural network,DRNN)自适应PID控制器用于反馈回路中的补偿控制方案,较好地解决了常规控制方法难以解决的保持轧机两侧液压压下系统动态特性一致的控制问题。

2 液压压下系统的数学模型

两侧液压压下系统的结构相同,以一侧为例建立系统的模型,一侧液压压下系统的结构图如图2所示[3]。

伺服放大器的传递函数为

$G{}_1(s)=\frac{u{}_{\text{r}}(s)}{{\rm I}(s)}=k{}_{\text{a}}(1)$

式中:ur(s)为伺服放大器的输入;I(s)为伺服放大器的输出电流;ka为伺服放大器的放大倍数。

电液伺服阀的传递方程为

QL(s)=kaI(s)-kcPL(s) (2)

式中:QL(s)为伺服阀的流量;ka为伺服阀的静态流量放大倍数;kc为伺服阀的零位流量;PL(s)为伺服阀的负载压力。

液压缸的运动方程为

APL(s)=(Ms2+Bs)X(s) (3)

油液连续性方程为

$Q{}_{\text{L}}(s)=AsX(s)+C{}_{\text{t}}{\rm P}{}_{\text{L}}(s)+\frac{V{}_{\text{t}}}{4\phi {}_{\text{e}}}s{\rm P}{}_{\text{L}}(s)(4)$

式中:A为油缸的有效工作面积;Ct为油缸的漏油系数;X(s)为滚缝的位移输出;M为可动部分的等效质量;B为油缸运动的粘滞系数;Vt为油缸的压缩容积;φe为系统有效体积弹性模量。

由以上各环节的运动方程可得到单侧压下系统的方框图如图3所示。

图3中,kct=kc+Ct。由图3化简得

$\begin{array}{l}G(s)=\frac{k{}_{\text{a}}k{}_{\text{s}}}{s(\frac{{\rm M}V{}_{\text{t}}}{4\phi {}_{\text{e}}A}s{}^2+\frac{BV{}_{\text{t}}}{4\phi {}_{\text{e}}A}s+\frac{k{}_{\text{c}\text{t}}}{A}{\rm M}s+\frac{k{}_{\text{c}\text{t}}}{A}B+A)}\\ =G^{\prime }(s)\frac{1}{s}(5)\end{array}$

令

$G^{\prime }(s)=\frac{k{}_{\text{a}}k{}_{\text{s}}}{\frac{{\rm M}V{}_{\text{t}}}{4\phi {}_{\text{e}}A}s{}^2+\frac{BV{}_{\text{t}}}{4\phi {}_{\text{e}}A}s+\frac{k{}_{\text{c}\text{t}}}{A}{\rm M}s+\frac{k{}_{\text{c}\text{t}}}{A}B+A}$

式中,B,Ct,φe等参数受环境等因素的影响而相对缓慢地在较大的范围内波动,因而两侧的液压压下系统的传递函数不可能一致,这样显然很难保证两侧压下系统动态品质的一致性。本文采用主从结构,仅对主动侧液压压下系统使用位置控制,主动侧液压压下系统的位置输出作为两侧液压压下的速度给定信号以实现某一自由度的位置控制。另外,为了提高液压压下系统的动态同步性,采用了基于对角递归网络的自适应反馈PID补偿控制器。

3 基于对角递归网络的自适应PID控制器设计

3.1 对角递归网络

动态神经网络利用网络的内部状态反馈来描述系统的非线性动力学特性,能更直接地反映系统的动态特性,更适合于工业过程建模、仿真和控制。但动态递归网络由于结构复杂,存在训练算法收敛速度慢的问题,而适于实时应用的动态网络必须具有简单的结构[4]。对角递归神经网络[5]作为一种动态神经网络具有结构简单的特点,正好满足了这一要求。DRNN由输入层、隐层和输出层组成,如图4所示。

对角递归神经网络非线性状态空间表达式为

$S{}_j(k)={\displaystyle \sum _{i=1}^{{\rm M}}W}{}_{ji}^h\times X{}_i(k)+W{}_j^d{\rm O}{}_j(k-1)+b{}_{1j}(k)$

Oj(k)=f(Sj(k))

$y(k)={\displaystyle \sum _{j=1}^{{\rm H}}V}{}_j\times {\rm O}{}_j(k)+b{}_2(k)(6)$

式中:Xi(k)为网络输入,i=1,2,…,m;y(k)为网络输出;Sj(k),Oj(k)分别为隐层输入和输出,j=1,2,…,n;W${}_{ji}^h$为输入层至隐层的连接权;Vj为隐层至输出层连接权;W${}_j^d$为递归神经元连接权;b1j和b2分别为隐层和输出层的阈值。

3.2基于对角递归网络的自适应PID控制

由于对角递归网络所具有的任意非线性表示能力,因而可以通过对系统性能学习来实现具有最佳组合的PID控制。基于对角递归网络的自适应PID控制系统结构图如图5所示。

设控制系统的输入-输出采样序列为r(k),y(k),则PID控制的增量算式为

u(k)=u(k-1)+KP[e(k)-e(k-1)]+KIe(k)+KD[e(k)-2e(k)+e(k-2)]e(k)=r(k)-y(k) (7)

将KP,KI,KD视为依赖于系统运行状态的可调系数时,可以将式(7)描述为

u(k)=f[u(k-1),KP,KI,KD,e(k),

e(k-1),e(k-2)]

e(k)=r(k)-y(k) (8)

式中,f(·)是与u(k-1),KP,KI,KD,y(k),r(k)等有关的非线性函数,可以用对角递归神经网络训练和学习来找到这样的规律。因此在此控制器中,选取DRNN的结构为4-4-3,即输入层神经元个数为4,隐层神经元个数为4,输出层神经元个数为3。

在控制器中的神经网络的学习算法采用递推预报误差[5](recursive prediction error)。递推预报误差算法为一种通过极小化预报误差来获取参数估计的方法。定义性能指标为

$E(\mathit{\theta })=\frac{1}{2{\rm N}}\cdot {\displaystyle \sum _{k=1}^{{\rm N}}\mathit{e}}{}^{\mathbf{{\rm T}}}(\mathit{k},\mathit{\theta })\cdot \mathit{e}(\mathit{k},\mathit{\theta })(9)$

式中:e (k,θ)为预报误差矢量;θ为参数矢量;N为数据长度。

RPE算法的基本原理是沿着E(θ)的Gauss-Newton搜索方向修正未知参数矢量,从而使E(θ)趋于最小,参数矢量的修正算式为

$\begin{array}{l}\mathit{\theta }(k)=\mathit{\theta }(k-1)+\alpha (k)\cdot \mu [\mathit{\theta }(k-1)]\\ \mu (\mathit{\theta })=-[{\rm H}(\mathit{\theta })]{}^{-1}\nabla E(\mathit{\theta })\\ \nabla E(\mathit{\theta })=-\frac{1}{{\rm N}}\cdot {\displaystyle \sum _{k=1}^{{\rm N}}\Psi }(k,\mathit{\theta })\cdot \mathit{e}(\mathit{k},\mathit{\theta })\\ {\rm H}(\mathit{\theta })={\displaystyle \sum _{k=1}^{{\rm N}}\Psi }(k,\mathit{\theta })\cdot \Psi {}^{\text{Τ}}(k,\mathit{\theta })\end{array}(10)$

式中,α(k)为学习速率。

本文引用BP算法中对于学习率的调整规则,即:若总误差减小(即新误差比老误差小),则学习速率增加;若总误差增加(即新误差比老误差大),则学习速率减小。μ(θ)为Gauss-Newton搜索方向,$\Psi (\mathit{\theta })=[\text{d}\widehat{y}(k,\mathit{\theta })/\text{d}\mathit{\theta }]{}^{\text{Τ}}$是网络的一步预报值对θ的一阶微分。基于上述原理的RPE算法是:

$\begin{array}{l}e(k)=y(k)-\widehat{y}(k)\\ {\rm M}(k)=\frac{{\rm P}(k-1)\cdot \Psi (k)}{\lambda (k)+\Psi {}^{\text{Τ}}(k){\rm P}(k-1)\Psi (k)}\\ {\rm P}(k)=\frac{1}{\lambda (k)}\cdot [{\rm I}+{\rm M}(k)\Psi {}^{\text{Τ}}(k)]\cdot {\rm P}(k-1)\\ \mathit{\theta }(k)=\mathit{\theta }(k-1)+\alpha (k){\rm P}(k)\Psi (k)e(k)\\ \lambda (k)=\lambda {}_0\cdot \lambda (k-1)+(1-\lambda {}_0)\end{array}(11)$

式中:λ(k)为遗忘因子;λ0为常数。

由式(10)可知,RPE算法是一种利用了高阶导数信息的学习算法,在计算H(θ)的逆矩阵上利用了递推最小二乘的方法,与仅利用了一次导数信息的基本BP算法相比,显然RPE算法的收敛速度更快。

4 系统的控制框图和仿真实验

图6为采用基于对角递归网络的自适应PID反馈补偿控制系统的框图。只在一侧安放位置检测器件,X1,X2为左右侧轧辊的位置,采用双环控制。图7为未加入神经网络PID补偿控制器在t=0.5 s突然加入扰动的响应曲线。图8为加入神经网络PID补偿控制器在t=0.5 s突然加入扰动的响应曲线。

5 结论

从仿真曲线可以看出,采用在反馈回路中加入对角递归神经网络自适应PID补偿控制器之后,系统的性能得到明显改善。不仅很好地消除了两侧动态调节过程的不一致,而且有效地提高了系统的抗扰动能力,使两侧液压压下系统输出的一致性得到保证。

参考文献

[1]孙一康.带钢热连轧的模型与控制[M].北京:冶金工业出版社,2002.

[2]唐谋凤.现代带钢冷轧连轧机的自动化[M].北京:冶金工业出版社,1999.

[3]陈巍,吴捷.具有辅助调节功能的递归神经网络自适应PID控制[J].信息与控制,2000,29(5):461-470.

[4]Gao Furong,Wang Fuli.A Si mple Nonlinear Controller with Diagonal Recurrent Neural Network[J].Chemical Engineering Science,2000,55(7):1283-1288.

[5]段慧达,郑德玲,刘聪.基于对角递归神经网络的建模及应用[J].北京科技大学学报,2004,26(1):103-105.

递归网络 篇7

对于用顺序法表示的二叉树,各结点在数组中的编号很有规律,其周游较容易进行,但对于用链式存储结构表示的二叉树,进行周游就复杂一些,仅讨论二叉链表存储的二叉树的周游算法。首先讨论深度优先周游二叉树的递归算法,然后研究深度优先周游二叉树的非递归算法。

1 深度优先周游二叉树的递归算法

前序法(DLR)的递归定义是:若二叉树为空,则空操作;否则:访问根结点;前序周游左子树;前序周游右子树。

中序法(LDR)的递归定义是:若二叉树为空,则空操作;否则:中序周游左子树;访问根结点;中序周游右子树。

后序法(LRD)的递归定义是:若二叉树为空,则空操作;否则:后序周游左子树;后序周游右子树;访问根结点。

深度优先周游二叉树的次序是递归定义的,因此其递归算法是很容易实现的。若二叉树的二叉链表存储结构定义为:

则3种深度优先周游二叉树的递归算法分别为:

从上述深度优先周游二叉树的定义可知,3种周游算法的不同处仅在于访问根结点和周游左、右子树的先后关系。深度优先周游二叉树的递归算法的实现,在系统运行时是借助栈来完成的。以图1所示的二叉树为例,分析栈的变化过程。前序周游二叉树与中序周游二叉树时,栈的变化相同,而后序周游二叉树则稍微复杂一些。如表1、表2和表3所示。

2 二叉树的非递归周游算法

根据上述二叉树周游时的栈的变化情况,可以看出:二叉树的前序周游和中序周游时栈的变化情况完全相同,不同的是前序周游时,进栈时访问元素;而中序周游时,出栈时访问元素。由此设计二叉树的DLR和LDR的非递归周游算法如下:

使用栈进行前序周游时,遇到一个结点,就访问该结点,并把该结点推入栈中,然后下降去周游它的左子树。周游完它的左子树后,从栈顶托出这个结点,然后按照它的右孩子指针指示的地址再去周游该结点的右子树。

使用栈进行中序周游时,遇到一个结点,就把它推入栈中,并去周游它的左子树。周游完它的左子树后,从栈顶托出这个结点并访问之,然后按照它的右孩子指针指示的地址再去周游该结点的右子树。

使用栈进行后序周游二叉树时,遇到一个结点,把它推入栈中,去周游它的左子树。周游遍它的左子树后,还不能马上访问处于栈顶的结点,而是要再按照它的右孩子指针指示的地址去周游该结点的右子树。周游遍右子树后才能从栈顶托出该结点并访问之。为此,需要设一个标志,以标识右子树已被周游。算法中设置了一个指针标志pre,表示刚刚访问的结点。如果当前结点的右孩子为pre,就说明右子树已被访问,接下来是访问当前结点了。

3 深度优先周游二叉树的算法性能分析

上述深度优先周游二叉树的递归算法与非递归算法的时间复杂度均为O(n),空间复杂度在理想情况下为O(log 2n),如二叉树退化为单支树时,则空间复杂度为O(n)。

由于递归算法结构清晰,程序易读,而且它的正确性容易得到证明,因此,利用允许递归调用的语言进行程序设计时,给用户编制程序和调试程序带来很大的方便。因为对这样的一类递归问题编程时,不需要程序员而由系统来管理递归工作栈。而非递归算法更方便读者理解工作栈的变化情况,但需要程序员决定栈所占据的存储空间大小,为保证二叉树周游不至于因为栈溢出而进行不下去,就需要给栈分配足够的存储空间。

摘要：给出了深度优先周游二叉树的前序、中序、后序的3种递归算法,在分析了周游二叉树的递归算法中的工作栈的执行过程的基础上,设计了先序、中序、后序周游二叉树的非递归算法,对深度优先周游二叉树算法的性能进行了分析。

关键词：二叉树,周游,递归,非递归,栈

参考文献

[1]严蔚敏,吴伟民.数据结构(C语言版).清华大学出版社,2010.

浅析C语言递归 篇8

所谓递归,简而言之就是在调用一个函数的过程中又直接或间接地调用该函数本身,以实现层次数据结构的查询和访问。在函数中直接调用函数本身,称为直接递归调用。在函数中调用其它函数,其它函数又调用原函数,这就构成了函数自身的间接调用,称为间接递归调用。

而采用递归方法来解决问题,必须符合以下三个条件:

1、可以把要解决的问题转化为一个新问题,而这个新的问题的解决方法仍与原来的解决方法相同,只是所处理的对象有规律地递增或递减。

说明:解决问题的方法相同,调用函数的参数每次不同(有规律的递增或递减),如果没有规律也就不能适用递归调用。

2、可以应用这个转化过程使问题得到解决。

说明:使用其他的办法比较麻烦或很难解决,而使用递归的方法可以很好地解决问题。

3、必定要有一个明确的结束递归的条件。

说明:一定要能够在适当的地方结束递归调用。不然可能导致系统崩溃。

好知道是这样以后;我们来写一个众多教材上的程序:使用递归的方法求n!。当n>1时,求n!的问题可以转化为n*(n-1)!的新问题。比如n=4:

第一部分:4*3*2*1n*(n-1)!

第二部分:3*2*1(n-1)(n-2)!

第三部分:2*1 (n-2)(n-3)!

第四部分:1(n-4)!4-4=0,得到值1,结束递归。我给的源程序如下:

可以看到,加上两条printf()和getchar()语句后,可以察看各级调用及其中间答案,很清楚的看到程序的执行过程。运行结果如图1所示,当主函数第一次调用fac0函数的时候,由于n=4不等于0和1,并不立即返回结果1,而是执行c=n*fac(n-1),用实参n-1 (值为3)调用fac()函数自己,即递归调用fac(3)。于是进入第二层调用fac(),这时也没有得出结果,继续用实参n-1(值为2)调用fac()函数自己。同样经过第三层调用后进入第四层调用,这时候n=1,算出1!=1,满足结束递归的条件,然后把得出的结果1返回给第三次调用的fac函数,得出2*1!=2,然后把结果2返回给第二次调用的fac函数,得出3*2!=6,最后第一次调用的fac函数根据第二次调用的返回值算出4!=4*3!=4*6=24,结束整个递归调用,得出最终结果并输出。

我们做事情,一般都是从头开始的,而递归却是从末尾开始的。比如上面的函数,当n>1的时候,就只能求助于n-1,而(n-1)1时,就求助于n-2,然后……直到(n-k)=1时,函数fac终于有了返回值1了,它再从头开始计算,然后一直算到n为止。所以说,递归简直就是一个数学模型,它的工作过程就是自己调用自己。以下是几点对递归的说明:

1、当函数自己调用自己时,系统将自动把函数中当前的变量和形参暂时保留起来,在新一轮的调用过程中,系统为新调用的函数所用到的变量和形参开辟另外的存储单元(内存空间)。每次调用函数所使用的变量在不同的内存空间。

2、递归调用的层次越多,同名变量的占用的存储单元也就越多。一定要记住,每次函数的调用,系统都会为该函数的变量开辟新的内存空间。

3、当本次调用的函数运行结束时,系统将释放本次调用时所占用的内存空间。程序的流程返回到上一层的调用点,同时取得当初进入该层时,函数中的变量和形参所占用的内存空间的数据。

4、在开发过程中使用printf()和getchar()可以看到执行过程,并且可以在发现错误后停止运行。

很多人说所有递归问题都可以用非递归的方法来解决,能不用递归就不用递归。但是对于一些比较复杂的递归问题用非递归的方法往往使程序变得十分复杂难以读懂,而函数的递归调用在解决这类问题时能使程序简洁明了有较好的可读性,因此很多问题用递归可很容易解决。同时由于递归调用过程中,系统要为每一层调用中的变量开辟内存空间、要记住每一层调用后的返回点、要增加许多额外的开销,因此函数的递归调用通常会降低程序的运行效率(在许多情况下,速度的差别不太明显)。

我曾经碰到过这样一个动物繁殖问题:若一头小母牛,从出生起第四个年头开始每年生一头母牛,按此规律,第n年时有多少头母牛?

如果不用递归函数来做,每当母牛到第4岁的时候才会生下一头小母牛,所以,每年增加的新的1岁小母牛都是上一年3岁的母牛加上4岁的母牛生下数量之和,分析过程如图2所示,给出程序如下:

程序虽然简短,但是可读性太差,不易理解。那么如果用递归函数求此问题呢?

我们先写出函数表达式:f(n)=f(n-1)+f(n-3)

为什么f(n)=f(n-1)+f(n-3)呢,请看:

f(n)-f(n-1)=f(n-3)

因为第n年要比n-1年多的牛,都是大于三岁的牛生的小牛,而f(n-3正是那些在n年大于三岁的牛,然后它们在第n年生下相同数量的小牛。源代码如下:

运行结果如图3所示:

可见,递归函数的主要优点是可以把算法写的比使用非递归函数时更清晰更简洁,而且某些问题,特别是与人工智能有关的问题,更适宜用递归方法。递归的另一个优点是,递归函数不会受到怀疑,较非递归函数而言,某些人更相信递归函数。编写递归函数时,必须在函数的某些地方使用if语句,强迫函数在未执行递归调用前返回。如果不这样做,在调用函数后,它永远不会返回,造成无穷递归。在递归函数中不使用if语句,是一个很常见的错误。此外,象汉诺塔问题就只能靠递归才能解决,但是现实中很多问题都是比较简单的,没有象汉诺塔那么复杂,我们只要会用递归编程来为我们解决一些问题就行了,所以就不必深究了。

参考文献

状态积累递归软序列估计 篇9

1965年Ward等人提出序列估计机制的捕获算法后[1],这一类算法有了很大的发展。在文献[2]提出的捕获算法中,将序列提前积累多次后作为初始捕获状态,这样大幅降低了信道噪声的干扰,然后以此为基础再进行捕获。Salih等提出的算法在接收端利用PN序列的相关性构造了一种辅助序列[3],在得到辅助序列后,根据辅助序列不断判断当前捕获序列结果与正确序列的距离和迭代方向,最终实现正确捕获。这两种方法都需要超过一个周期的捕获时间。Chiu等改进了序列的积累方式[4],信息的积累效率提高,因此算法性能获得了提高。文献[5]通过重新设计收发端的序列给出了一种分布式接收机,并采用不断积累修正获得较好的算法性能。文献[6]对现有的同步捕获方法进行了总结,并支持估计机制的优势所在。Yang等提出的递归软序列估计(Recursive Soft Sequence Estimation,RSSE)是SE机制的典型代表[7]。

RSSE是目前针对低信噪比、长序列周期条件下伪随机捕获算法中比较有效的一种。但当SNR值下降时,对数似然比(LLR)值会受到噪声的影响,使得RSSE机制与原有的序列捕获机制的硬判决相比没有什么优势。尤其是对于长周期序列,或是序列的生成多项式中非零项较多时,算法的捕获性能急剧下降。

为了提高RSSE类的序列捕获算法在低信噪比下(尤其对于捕获长PN序列)的性能,文中提出一种基于状态积累递归软序列估计(SARSSE)的序列捕获算法。通过在RSSE前端加入状态积累移位寄存器的设计,可以提高算法捕获效率。对于多个PN周期而言,由于每个PN序列周期内伴随发送信号的噪声都是相互独立的。所以将每个PN序列发送的前n个接收比特叠加在一起可以改善初始状态的估计,从而改善文献[7]信道输出信噪比(SNR)和LLR的值,最终能够在低SNR下得到较好的PN序列捕获性能。改善了RSSE机制的捕获性能。

1 SARSSE捕获机制

如图1所示,SARSSE捕获机制包括5个功能块:SISO译码器、状态累积寄存器、软码片寄存器、PN序列生成器以及积分判决电路。SISO译码器在接收到与PN序列的给定码片相关联的软信道输出采样之后估计相应的LLR软输出。除了这个码片的内信息(即直接从信道接收到的信息)之外,还可以利用外信息,外信息是由软码片寄存器中的延迟单元(称为软码片延迟单元,SCDU)中 所存储的由以前接收到的码片值所计算得到的LLR值构成。因此若可用过去时刻的软信息对当前时刻的软信息加强,必须将SCDU构造成线性反馈移位寄存器(LFSR)的结构形式,该过程需利用序列生成多项式g(x),这样才能使得当前时刻软信息的计算可以利用过去时刻的软信息积累。SCDU的数目与PN序列生成器中的延迟单元的数目相同,将SISO译码器的软输出送到软码片寄存器的最左边的SCDU,并丢弃最右边的SCDU中的软LLR值。SCDU用来存储连续的码片瞬时LLR值,并且采用该LLR的计算连续的码片值。与此同时,与PN序列的给定码片相关联的软信道输出采样还将送入状态累积寄存器中。当接收信噪比较高时,SARSSE机制可以在一个周期之内捕获到PN码,那么状态累积寄存器将不起作用。但是当SNR低时,SARSSE机制无法在一个PN码周期之内完成捕获,此时将上一周期在状态累积寄存器中存储的码片值与当前输入的软信道输出采样值相加,然后再将相加的值送入SISO译码器进行处理。

图1中SISO译码器需要软信道输出信息以及SISO译码器以前估计的LLR值所提供的外信息来计算软输出,从而更新软码片寄存器中的值。在单用户情况下,标准的捕获模型是

Zk = αk(-1)ck+nk (1)

式中:Zk是捕获模块接收到的对应于ck的噪声抽样信号,并且αk是信道衰落幅度。nk是单边功率谱密度为N0的零均值加性高斯白噪声(AWGN)。用Ec代表发送的码片能量,且undefined代表每码片的SNR。

ck是扩频序列,并且假设ck是由一个r-级LFSR产生的,这个寄存器的生成多项式可以表示为

g(D)=1+Ds1+Ds2+…+Dsl+…+DsM=r (2)

式中,D代表单位延时算子。每个生成器系数g1, g2, …,gr(共r个系数)表示是否存在反馈连接线(1表示存在,0表示不存在),其中有M个系数{s1,s2,…,sM=r,1≤si≤r}为1,而其他的系数均为0。由于扩频通信系统通常用+1来表示0,并且利用码片值取为{+1,-1}的二进制扩频序列进行通信,所以PN序列生成器输出的是符号{+1,-1}。因此,现在用域{+1,-1}上定义的模2乘运算替换域{1,0}上的常规模2加运算,如图1中所示。并且,PN序列生成器的输出符号服从以下的递归公式

undefined

软信道输出信息是信道输出为Zk条件下的ck的LLR值,即

undefined, i=0,1,2,… (4)

式中,undefined代表信道的可靠值。在式(4)中,L(ci)是随机变量ci的LLR值,其计算式为

undefined

如果没有有关ci的先验信息,那么有L(ci)=0。

由图1中可知,在计算当前时刻软信息的时候利用了过去时刻的软信息积累。根据生成多项式(2)的递归关系以及图1中软码片寄存器中SCDU的反馈连接,用于增强ci的正确译码概率的外信息可以近似表示为

undefined·undefined·

undefined (6)

假设Le(c-∞)=…=Le(c-2)=Le(c-1)=0,其中L(yi-1),L(yi-2),…,L(yi-r)是SISO译码器以前的r个软输出。

最后,利用式(4)中的信道输出信息和式(6)中的外信息,可以得到与ci相关联的SISO译码器软输出为

undefined

undefined·

undefined (7)

利用式(7)可以估计出完整PN序列的前r个连续码片值。

可见,ci的软信息积累依赖于信道的可靠值,当SNR低时,软信息并不会随着递归深度的增加而增加。因此,SARSSE机制在SISO译码器之前增加了状态累积移位寄存器,状态累积移位寄存器的初始值为0。当没有在一个PN码周期之内捕获到PN序列时,状态累积移位寄存器中的值会与下一个PN码周期的信道输入值相加。由于两次PN码周期期间的噪声是相互独立的,所以有

undefined

显然,信道的可靠性增加了,也即改善了SISO译码器输入内信息的可靠性,从而改善了整个机制的捕获性能。

用仿真来验证提出的SARSSE捕获机制。仿真结果主要基于生成多项式为g(D)=1+D+D3+D4+D13和g(D)=1+D2+D5的PN序列。首先比较了与正确判决PN序列的某个指定码片值的极性相关的可靠性。横坐标是接收到的归一化码片数(l/r);纵坐标是判决可靠性,定义为SISO译码器输出(公式(7)的计算结果)的绝对值。图2显示了由生成多项式g(D)=1+D+D3+D4+D13产生的PN序列的捕获性能,用两种机制进行捕获(RSSE和SARSSE)。

2 SARSSE算法仿真

通过在AWGN(加性高斯白噪声)环境下的仿真,来验证上文提出的SARSSE捕获机制。仿真结果主要基于生成多项式为f(D)=1+D+D3+D4+D13的PN序列。首先比较了两种捕获机制在改进前后的可靠性,该可靠性是指正确判决PN序列的某个指定码片值,具体定义为SISO译码器的输出绝对值,判断可靠性是通过式(7)计算的。图2是信噪比为-2 dB时,在第二个周期其判断可靠性的积累情况。随着序列积累过程的进行,软信息不断地增加,从而两种算法的判断可靠性在理论上应该持续积累,但从仿真结果可以看出,信道环境的信噪比为-2 dB时,RSSE机制的判断可靠性已经不会像SARSSE机制那样随着接收序列数的增加而变大,因此SARSSE机制在低信噪比时可靠性优于RSSE序列捕获算法。

图3中通过计算利用不同的序列状态数对序列进行捕获后,对序列进行纠错的效果来考量算法的捕获能力,从而对比了两种算法(RSSE和SARSSE)的捕获性能。仿真序列的生成多项式为f(D)=1+D+D3+D4+D13。图中的结果再次验证了SARSSE捕获机制在低信噪比环境下的捕获可靠性能好于RSSE捕获算法。从图3中的曲线对比可以看出,当SNR较高时,使用相同的递归积累数(例如积累数L都为1 Sa或者10 Sa,1 Sa表示一个序列状态),SARSSE机制相对于RSSE机制的每码片的SNR增益大约为1 dB;并且当SNR继续降低时,增加递归积累数并不能再继续改善RSSE机制的系统性能,因此此时的SARSSE机制的SNR增益更加明显,L=40 Sa时的SNR增益达到了2 dB。

3 结束语

笔者提出了改善的RSSE捕获方法——SARSSE算法,并且研究了SARSSE机制对PN序列的捕获性能。仿真结果显示SARSSE捕获算法在低SNR环境下对PN序列的捕获可靠性好于RSSE算法,可以在硬件复杂度增加不大的情况下,在低SNR环境下进一步改善系统的捕获性能。

摘要：目前对于数字电视应用的长周期伪随机序列,捕获性能有限。提出状态积累递归软序列估计算法,在递归软信息积累过程前端建立状态积累移位寄存器,通过积累多个周期的信息来提供较为可靠的初始积累值,最终加速后续软信息积累,从而取得较好的捕获性能。

关键词：伪随机序列,捕获,状态积累,递归软序列估计

参考文献

[1]WARD R B.Acquisition of pseudonoise signals by sequential estimation[J].IEEE Trans.Communications,1965,13(4):475-483.

[2]JUNG C Y,YOON S.A novel DS/SS code acquision technique based onseed accumulation of sequence generator[C]//Proc.2001 IEEE MilitaryCommunications Conference.[S.l.]:IEEE Press,2001:1380-1383.

[3]SALIH M,TANTARATANA S.A closed-loop coherent acquisitionscheme for PN sequences using an auxiliary sequence[J].IEEE Journalon Selected Areas in Communications,1996,14(8):1653-1659.

[4]CHIU J,LEE L.An improved sequential estimation scheme for PN acqui-sition[J].IEEE Trans.Communications,1988,36(10):1182-1184.

[5]刘震昆,黄顺吉.低信噪比下超长PN码的快速捕获技术[J].信号处理,2006,22(3):299-302.

[6]康荣宗,汪涛,刘洛琨,等.超宽带通信系统的同步捕获算法研究[J].电视技术,2008,32(S1):78-81.