嵌入式系统软件设计中的常用算法(完整版)

嵌入式系统软件设计中的常用算法(完整版)，嵌入式入门基础教材。内容简介本书根据嵌入式系统软件设计需要的常用算法知识编写而成。基本内容有:线性方程组求解、代数插值和曲线拟合、数值积分、能谱处理、数字滤波、数理统计、自动控制、数据排序、数据压缩和检错纠错等常用算法。从嵌入式系统的实际应用岀发,用通俗易懂的语言代替枯燥难懂的数学推导,使读者能在比较轻松的条件下学到最基本的常用算法,并为继续学习其他算法打下基础。本书可作为电子技术人员自学常用算法的教材,也可作为高等院校电子技术类专业本科生、研究生的教学参考书。图书在版编目(CIP)数据嵌入式系统软件设计中的常用算法/周航慈著.一北京:北京航空航天大学出版社,2010.1ISBN978-7-81124-943-9Ⅰ.嵌…Ⅱ.周…Ⅲ.微型计算机一软件设计一算法Ⅳ.TP311.5中国版本图书馆CIP数据核字(2009)第189989号嵌入式系统软件设计中的常用算法周航慈著责任编辑董云凤张金伟北京航空航天大学出版社出版发行北京市海淀区学院路37号(100191)发行部电话:010-82317024传真:010-82328026http://www.buaapress.comcnE-mail:bhpress@263.net印刷有限公司印装各地书店经销开本:787mm×960mm1/16印张:12.5字数:280千字2010年1月第1版2010年1月第1次印刷印数:5000册ISBN978-7-81124-943-9定价:24.00元嵌入式系统在各行各业的应用越来越广,我国从事嵌入式系统开发的人员也越来越多,从国内主要的几种电子杂志上可以看出,有关嵌入式系统应用的文章也越来越多。在开发一种嵌入式系统产品时,主要是做两方面的设计:硬件设计和软件设计。在硬件设计方面,各个半导体公司竞相推出各种高性能、低功耗、低成本的CPU和外围芯片,这使我们在进行硬件设计时可以很快地得到最先进的芯片。在这种情况下,硬件设计的外部条件越来越好,集成度越来越髙,在实现相同功能的情况下线路越来越简化。在软件设计方面,虽然开发工具和程序设计语言也在不断提高,但技术人员本身的软件素质无疑起决定作用。因此,软件设计水平在嵌入式系统产品开发的过程中占有重要的地位,直接影响到产品的功能和竞争能力我国目前绝大多数从事嵌入式系统开发的技术人员基本上不是计算机专业毕业的,有的可能还没有上过大学,他们未接受过系统的软件基础理论教育,软件设计水平仍不太高。在软件开发过程中,他们只是不自觉地采用了一些规律性的设计方法,或者模仿别人的程序设计方法,而有更多成熟的基本方法没有掌握,开发出来的软件水平不高,致使产品的功能和可靠性受到一定的制约。软件设计是一门科学,有其自身的规律,也有很多成熟的理论和算法。要学习就要选教材,而目前所能选到的都是专为计算机专业编写的教材。这些教材起点较高,偏重理论叙述,不考虑嵌入式系统的硬件特点,对于广大嵌入式系统开发人员来说不是十分适合学起来会感到比较抽象和吃力出于提高我国广大嵌入式系统开发人员软件素质的愿望,我们决定编写一本适合自学的关于常用算法的书。该书起点要求不高,只要掌握了C语言、学习了“数据结构”有关知识并从事过嵌入式系统开发工作的人员就可以看懂。学完本书后,对软件设计中常用的算法就能初步掌握。在进行软件设计时,可以减少很多盲目性,并为更系统、更深入地学习其他计算机软件设计理论打下良好基础。本书主要内容如下第1章介绍常用线性方程组求解算法;第2章介绍常用代数插值和曲线拟合算法;第3章介绍常用数值积分算法;第4章介绍常用能谱处理算法;第5章介绍常用数字滤波算法;第6章介绍常用数理统计算法;第7章介绍常用自动控制算法;第8章介绍常用数据排序算法;第9章介绍常用数据压缩算法;第10章介绍常用检错与纠错算法。本书编写的原则是:尽量结合嵌入式系统的应用实例,采用通俗易懂的叙述方式,介绍最基本的核心内容,以便读者能够顺利入门,为进一步学习更多的算法打下基础。在本书的编写过程中,得到北京航空航天大学出版社的大力支持,何立民教授给予了无私帮助,在此表示衷心感谢!周立功先生在本书的策划过程中起了很大促进作用,在此也表示衷心感谢!王冬霞参与了部分算法程序的调试工作,在此一并感谢!由于作者水平有限,书中一定会有错误及不足之处,敬请广大读者予以指正,不胜感谢作者于东华理工大学2009年8月目录第1章常用线性方程组求解算法1.1主元消去法1.1.1无回代过程的主元消去法1.1.2有回代过程的主元消去法行列式法121.2.1行列式法概述………………121.2.2三元线性方程组的行列式法131.3应用实例··········1.3.1数学模型分析……1.3.2算法设计……1.3.3程序设计20第2章常用代数插值和曲线拟合算法…………···242.1线性插值262.1.1算法原理…262.1.2应用实例27抛物线插值202.2.1算法原理292.2.2应用实例322.3曲线拟合2.3.1线性拟合算法及其应用实例382.3.2抛物线拟合算法及其应用实例第3章常用数值积分算法523.1算法原理…523.2应用实例第4章常用能谱处理算法584.1谱曲线平滑…584.1.1算法原理584.1.2算法程序604.2谱峰定位614.2.1算法原理624.2.2算法程序624.3能量刻度…∴634.3.1算法原理644.3.2算法程序……∴……………………………664.4峰面积计算4.4.1算法原理674.4.2算法程序684.5含量计算69第5章常用数字滤波算法∴705.1程序判断滤波705.2中值滤波…745.3算术平均滤波775.4去极值平均滤波785.5滑动平均滤波5.6滑动加权滤波825.7一阶滞后滤波5.8数字滤波算法小结84第6章常用数理统计算法6.1数据样品的正态分布86均值和均方差的估算甲鲁·鲁鲁·鲁鲁··里鲁鲁·鲁春………………886.3用数理统计方法消除粗大误差…886.4用数理统计方法计算线性相关系数……………∴…∴91第7章常用自动控制算法937.1简单阈值控制………937.1.1算法原理937.1.2应用实例967.2经典PID控制1017.2.1算法原理1027.2.2PID控制算法在应用中需要解决的问题…106第8章常用数据排序算法…1088.1归并排序1088.1.1算法原理1088.1.2算法程序…1098.1.3改进的算法1168.2快速排序………1268.2.1算法原理………1268.2.2算法程序1288.2.3非递归算法程序……130第9章常用数据压缩算法1349.1信源编码概述1349.2霍夫曼编码…1369.2.1变长码9.2.2霍夫曼编码原理………………………………………………………1399.2.3霍夫曼编码算法程序9.3批量采样数据的压缩编码·…………1473.1紧凑压缩编码1479.3.2增量压缩编码…1509.3.3预测压缩编码153第10章常用检错与纠错算法15810.1检错码15810.1.1检错原理15810.1.2奇偶校验16010.1.3和校验16410.1.4循环冗余校验(CRC校验)…………………16710.2纠错码17110.2.1纠错原理17110.2.2汉明码…17110.2.3检二纠一码…………17710.2.4抗突发干扰的措施186参考文献189页码,1/5第章常用线性方程组求解算法在一个嵌人式系统中,往往需要从外部环境中获取若干个信息(多输人〕然后通过数据处理,从屮求解出若干个结果(多输出)。如果多输出与多输入之间为线性关系,则将共称为“多变量线性系统”。在多变量线性系统中经常要碰到求解多元线性方程组的问题,线性方程组的般形式为:AnX1+A1x2+…+AnX,=B1A21 X1+A2 X2+.+AznX,= B2A,l XI+An2 X2+a++AnX,= B写成矩阵形式便是:AAA1n「XBA21A2AsXBA」xB线性方程组的求解算法有直接法和迭代法等,它们各自又有分支。从嵌人式系统的特点出发,在这里只讨论最基本的主元消去法和行列式法,它们是直接法的代表。在本章的应用实例中将介绍一个直接法和迭代法相结合的算法。1.1主元消去法主元消去法又分总体选主元消去法和按列选主元消去法,由于前者每次选主元的范围大,速度相对慢所以采用按列选主元消去法。主元消去法又分为无回代过程的主元消去法和有回代过程的主元消去法,I.11无回代过程的主元消去法这里,通过求解一个具体的线性方程组来说明这一方法的计算步骤http://www.wenxuclcia.cn/n/printing.htm2012/129页码第1章常用线性方程组欢解算法嵌入+式尔4x1+2x2-x3=0(1-3)统写成短阵形式便是软1件42解的第1步:为了提高计算的精度,在第1列找出绝对值最大的系数作为第1列的主元,这里是第3行的4。为了使主元位于主对角线上,把方程组中的式(1-1)和式(1-3交换算位置得到等效的方程组:法4x1+201-4)x1+2x2-x3=-3(1-5)2x1+3x21写成矩阵形式便是:第2步:用主元除式(1-4)中各个元素,则方程组变为x1+0.5x2-0.250(l-7)t 2.3(1-8冫2x1+3x2+(1-9写成矩阵形式便是0.5120第3步:用高斯消去法将式(1-8)和式(1-9)中x1的系数变为0高斯消去法的算法原理如下:对于一个n阶线性方程组,设当前主元位于第行第i列(主元一定在主对角线上)通过前面若干步骤的处理,已经将主元调整为1,主元左边各个系数均已为零,则主元所在的第i行成为:x;+A;H+1Ai+L十A1m1X.1+A.,X,=B1-10)即http://www.wenxuclcia.cn/n/printing.htm2012/129