串行优化算法范文（精选3篇）
串行优化算法 第1篇
随着信息化的发展, 人们对低密度奇偶校验(Low Density Parity Check , LDPC ) 码有了重新的认识。 LDPC码作为高效的信道纠错编码,具有较低的译码复杂度,系统吞吐量较大, 已在电力线载波(Power Line Carrier ,PLC) 通信、第三代和第四代无线移动通信等方面得到了广泛应用[1]。 相对于turbo译码算法[2],采用LDPC编码和置信传播(Belief Propagation ,BP)译码算法更受人们的青睐[3]。 但是BP算法存在对硬件存储量的需求较大以及对信道情况较为敏感等问题。 人们更趋向于鲁棒性更好和复杂度更低的译码算法, 最典型的就是并行最小和(Parallel Min - Sum , PMS ) 算法[4]。 这类算法在实现中只需要加法和比较运算, 且不需要知道信道情况, 可以获得性能和复杂度的良好折衷。 考虑到PMS算法前后两次迭代译码过程中,参与信息交换的置信度被过高估计, 文献[5] 通过引入归一化权重因子来减少这种负面影响,使其性能逼近最优BP算法的性能, 可称之为归一化并行最小和( Normalized Parallel Min - Sum , N - PMS ) 算法。 随着研究的深入,人们提出了不同的译码机制来提高置信传播的效率,其中较为重要的一类是采用权重因子的串行最小和( Normalized Serial Min - Sum , N - SMS ) 算法[6]。 在电力线载波通信中,收发模块通常采用具有低存储量和低复杂度的编、 译码算法。 N-SMS算法虽然在存储上较N-PMS算法有一定减少, 但N-SMS算法由于每次迭代都采用min操作来更新最小值, 复杂度相对较高。
为实现可靠通信, 并综合考虑实现成本、 器件功耗以及处理复杂度的问题, 针对N-SMS算法提出了一种基于竞争机制的归一化的串行最小和(Normalized Com- petitive Min - Sum , N - CMS ) 算法。 该算法在按照自然顺序更新变量节点对校验节点消息的同时,还利用竞争关系更新变量节点对校验节点消息集合中的最小值。 与文献[ 6 ] 类似的是, N - CMS在更新某一变量节点时, 同时利用了与该节点之前已更新的软信息和该节点之后还未更新的软信息,所以N-SMS算法与N-CMS算法的性能相同。 不同的是,N-CMS通过采用竞争机制来更新属于同一校验式的变量节点集合中的最小值, 避免了文献[6] 中采用min操作的复杂运算,并进一步减少了存储量。
1 N -PMS算法简介
为了简化叙述, 该文沿用文献[7] 中的部分符号定义。 设m和n分别表示校验节点和变量节点,H为LDPC码对应的校验矩阵, 当变量节点和校验节点有边相连接时,则hmn= 1 , 它是H中的第m行和n列的元素。 N(m)={n|hmn=1} 表示参与校验方程m的变量节点的集合, N ( m ) n为N ( m ) 中除去元素n后构成的集合; 相应地, M ( n ) = {m|hmn=1} 表示与变量节点n相连的校验节点的集合,M (n)m为集合M (n) 中除去元素m后构成的集合。设Qxnm是从变量 节点n传递给校 验节点m的软信息 ,表示在给 定接收序 列y , 并且除了 第m个校验方 程外 ,其他与n相关的校 验方程都 满足的条 件下 ,xn= x的概率 ; Rxmn是由校验 节点m传递给变 量节点n的软信息 , 表示在xn= x , 且参加第m个校验方 程的除n外的其他 变量节点的概率已知的条 件下 , 该校验方 程成立的 概率 ,其中
设s为长为N的编码序列x =[x1, x2, … , xN]T经过BPSK调制后的信号, g是均值为0 、 方差为 σ2的高斯噪声。设s经过AWGN信道后的接收序列为y=[y1,y2,… ,yN]T, BP译码后的 序列为其中 :
定义变量信息、校验信息和后验信息分别为:
传统的N-PMS算法可归纳如下:
初始化:令先验信息L(Pn) = yn, L( Qnm) = L( Pn)
步骤1: 判断是否达到设定的最大迭代次数MT, 若是则程序结束;否则执行步骤(2)。
步骤2:对m=1,2,… ,M和所有的n∈N(m) 计算:
在上式中,αnm= sign ( L( Qnm) ) 和 βnm= abs ( L( Qnm) ) , 分别表示L(Qnm) 的符号和绝对值, λ 为归一化权重因子, 满足0 ≤ λ ≤ 1 。
步骤3:对n=1,2,… ,N和所有的m∈M(n) 计算:
步骤4 : 对译码软信息进行硬判决, 若L (Qn) < 0 , 则, 否, n= 1 , 2 , … , N。 若, 则译码成 功 ,程序结束 ,否则转到 步骤(1)。
2 N -CMS算法的原理与实现步骤
在N-PMS中, 校验节点和变量节点是分别并行更新的。 文献[4]指出,对于H矩阵中的第m个校验式,N-PMS在计算所 有n ∈N (m) 集合中的 最小值时 , 可以通过找出该集合中最小的两个量 γ1和 γ2来简化运算。
初始化 : 令先验信 息L(Pn) = yn, L ( Qnm) = L ( Pn) , 对m =1 , 2 , … , M, 采用操作计算 对应于各 个m的最小的两 个值 γ1和 γ2, 且 γ1≤γ2。
步骤1: 判断是否 达到设定 的最大迭 代次数MT, 若是则程 序结束 ; 否则按照n=1,2, … ,N的顺序更 新变量节 点对校验 节点的消 息 ,执行步骤(2)。
步骤2: 对特定的n和每一个m ∈M (n) 按照式 (5) 计算L(Rmn) , 此处的min操作由 γ1和 γ2取代 。
步骤3: 对特定的n和每一个m ∈M (n) 依据式 (6)、 式(7)算出L(Qn) 和L( Qnm) , 由更新后 的L( Qnm) 得出 β ′nm后 , 再根据竞 争模式更 新 γ1和 γ2。
步骤4 : 若n ≤ N , 对译码软 信息进行 硬判决 , 若L( Qn) < 0 , 则, 反之转到步骤 ( 2 ) 。 否则执行步骤(5)。
3复杂度及存储量分析
对于操作 ,N-PMS算法在每 次迭代中 借助二进制 树图需要N/2 (2J +「log22J骎 - 2 ) 次加法运 算 [6] ; N - SMS算法则需 要更大的 计算量 , 为NJ ( 2J + 「 log22J - 2 ) 次加法运 算 ;N -CMS算法只在 初始化时 计算一次而在之后 的迭代过 程中 , 按照竞争 机制对 γ1和 γ2更新即可 ,其运算量 相对于N-SMS可大为简 化 。在竞争机 制中 , 更新 γ1和 γ2时 ,β ′nm与 γ1和 γ2的比较关 系需要2次操作 , 所以对每 个校验式 来说 ,2J个变量节 点总共要4J次操作 , 从而N/2个校验式 共需2NJ次操作 。 设N-PMS、N-SMS和N-CMS所需的平 均迭代译 码次数分别为, 注意到N - CMS只是N - SMS算法复杂度的简 化 , 所以有表1归纳了其 在计算时的平均 译码复杂 度 , 可以看出 , 当相差不大 时 ,N-PMS的平均译 码复杂度 最低 ,N-CMS次之 ,而N-SMS较高 。
另一方面 ,N-PMS需要较大 的存储 , 根据式 (5), 对于每个校 验式m,需要2个单元来 存储2个最小值 ,所以对于N/2个校验式 ,L(Rmn) 总共需N个存储单 元 ;根据式(6)、式(7),L(Qn) 、 L( Qnm) 分别需N和NJ个存储单 元 。 再来看N-SMS算法 , 由于变量 节点串行 更新 , L(Rmn) 只需2J个存储 , 但N - SMS算法每次 迭代都要 进行min操作 , 对于每个 校验式m ,L (Qnm) 仍需2J个 βnm来计算从而L ( Qn) 、 L ( Qnm) 分别仍需N和NJ个存储单元。 在N-CMS算法中,L(Rmn) 也只需2J个存储 , 由于N-CMS算法采用 了竞争机 制 , 每计算出 一个 β ′nm, 便用于 γ1和 γ2的更新 。 所以对于 每个校验 式m,只需分配1个临时单 元用于存 储 β ′nm, 从而L ( Qnm) 共需N / 2个单元 ,L(Qn) 需N个存储单 元 。 综上所述 , N - PMS 、 N - SMS和N -CMS所需存储 总量分别 为2N +NJ 、N +(N +2)J和3N / 2 + 2J 。 显而易见 , 相对于N - PMS算法和N - SMS算法 ,N-CMS算法具有 极低的存 储需求 , 这对于设 计成本低 廉的译码 模块具有 重要意义 。
4算法仿真与测试
仿真中选取码率1/2的(512,3,6)规则LDPC码通过AWGN信道, 译码分别采用N - PMS算法和N - CMS算法。 为了使得信息得到充分的传播,在仿真中令最大迭代译码次数MT= 30 。 下面从归一化权重因子的选取、 误比特率(Bit Error Rate ,BER)、 误帧率(Frame Error Rate , FER ) 、 收敛速率和译码平均译码复杂度几个方面来进行对比分析。
为简化讨论,此处利用蒙特卡罗方法来获得N-PMS和N-CMS的归一化权重因子。 如图1和图2所示,两者都在 λ=0.8时表现出最佳的性能,因此将 λ=0.8作为最佳归一化权重因子用于之后的仿真。
图3和图4分别对比了PMS、N-PMS、CMS和N-CMS系统的BER和FER性能, 按照是否引入归一化权重因子分为两组,即PMS和N-PMS,CMS和N-CMS。可以看出,不论哪一组归一化算法均比非归一化的算法性能要好得多, 约有0.5~0.7 d B的性能差距。 此外,即使都是归一化算法,N-CMS较N-PMS也有0.1~0.2 dB的性能提升。
由图5可知知,CMS所所需需的的平平均均迭迭代代译译码码次数要少于PMS , 类似的, N - CMS所需的平均迭代译码次数也少于N - PMS 。 从图6可以得出, N - CMS在中低信噪比时译码复杂度较N-SMS有明显的优势, 但比N-PMS略高; 在高信噪比时N-CMS与N-PMS复杂度接近,而且两者都比N-SMS的复杂度低。
5结论
本文提出了一种按照变量节点更新的归一化串行最小和算法 ———N-CMS。 N-CMS算法采用竞争机制实时更新变量节点对校验节点消息集合中最小的两个值, 它在保持与N-SMS算法相同性能的前提下大幅降低了运算量。 相对N-PMS算法而言,N-CMS算法不论是在收敛速度, 还是在译码性能上都更有优势, 其复杂度只有略微增加。 最为重要的是N-CMS算法具有极低的存储需求,尤其是在电力线载波通信所需的译码模块的设计中,表现出巨大的实用价值。
摘要：针对译码模块设计成本和功耗的问题,提出了一种LDPC码串行最小和算法。该算法是一种采用权重因子的基于变量节点更新的串行算法,它基于竞争机制来更新变量节点对校验节点消息集合中的最小值。与传统串行算法相比,在不损失性能的前提下,它大幅降低了译码所需的复杂度。另一方面,与并行最小和算法相比,新算法不仅大幅降低了所需存储量,而且性能也有一定的提升,复杂度只有略微增加。
关键词：电力线载波通信,串行最小和算法,低密度奇偶校验码,迭代译码,归一化权重因子
参考文献
[1]DEVELI I,KABALCI Y.Analysis of the use of different decoding schemes in LDPC coded OFDM systems over indoor PLC channel[J].Electronics&Electrical Engineering,2014,20(1):76-80.
[2]BERROU C,GLAVIEUX A,THITIMAJSHIMA P.Near Shannon limit error-correcting coding:turbo codes[C].In ICC93,1993(5):1064-1070.
[3]MACKAY D J C.Good error-correcting codes based on very sparse matrices[J].IEEE Trans.Inform.Theory,1999(45):399-431.
[4]FOSSORIER M P C,MIHALJEVIC M,IMAI H.Reduced complexity iterative decoding of low density parity check codes based on belief propagation[J].IEEE Trans.Commun,1999(47):673-680.
[5]CHEN J,FOSSORIER M P C.Decoding low-density parity check codes with normalized APP-based algorithm[C].Proc.IEEE Global Communications Conference,2001,9(1):1026-1030.
[6]刘原华,王新梅,胡树楷,等.一种改进的卷积LDPC码置信传播译码算法[J].西安电子科技大学学报,2009,36(3):424-428.
一类优化问题的快速收敛算法 第2篇
一类优化问题的快速收敛算法
给出了一个用于解决LC1线性约束优化问题的BFGS-SQP算法,这个算法是用Armijo线性原则来求步长的.为推广BFGS-SGP算法,本文采用Wolfe线性搜索原则来替代该BFGS-SQP算法的.Armijo原则,经过分析,同样得到了BFGS-SGP算法的全局收敛性及超线性收敛性.
作 者：王道林 宁伟 作者单位：山东泰山学院计算机科学与技术系,山东,泰安,271000刊 名：数学的实践与认识 ISTIC PKU英文刊名：MATHEMATICS IN PRACTICE AND THEORY年，卷(期)：34(5)分类号：O1关键词：LC1问题 BFGS-SQP算法 全局收敛 超线性收敛
基于遗传算法的飞机气动优化设计 第3篇
基于遗传算法的飞机气动优化设计
建立了一种以实数编码技术为基础的遗传算法模型,并把它与通过工程估算的气动分析方法相结合,进行飞机气动外形的单点和多点优化设计.优化设计中,设计变量取为机翼、机身和尾翼的外形及三者之间的相对位置,优化目标是使飞机在跨音速和超音速飞行状态下获得配平状态下最大的升阻比.设计结果表明该优化设计方法是十分有效的.,可以用来对具有正常布局形式的飞机进行气动外形的优化设计.
作 者：王晓鹏 作者单位：西北工业大学,飞机系,西安,710072;上海航天技术研究院,上海,33刊 名：计算力学学报 ISTIC EI PKU英文刊名：CHINESE JOURNAL OF COMPUTATIONAL MECHANICS年，卷(期)：200219(2)分类号：V211.3关键词：遗传算法 气动外形 优化设计