资 源 简 介
《嵌入式系统软件设计中的常用算法》根据嵌入式系统软件设计需要的常用算法知识编写而成。基本内容有：线性方程组求解、代数插值和曲线拟合、数值积分、能谱处理、数字滤波、数理统计、自动控制、数据排序、数据压缩和检错纠错等常用算法。从嵌入式系统的实际应用出发，用通俗易懂的语言代替枯燥难懂的数学推导，使读者能在比较轻松的条件下学到最基本的常用算法，并为继续学习其他算法打下基础。">《嵌入式系统软件设计中的常用算法》根据嵌入式系统软件设计需要的常用算法知识编写而成。基本内容有：线性方程组求解、代数插值和曲线拟合、数值积分、能谱处理、数字滤波、数理统计、自动控制、数据排序、数据压缩 [更多]内容简介本书根据嵌入式系统软件设计需要的常用算法知识编写而成。基本内容有:线性方程组求解、代薮插值和曲线拟合、数值积分、能谱处理、数字滤波、数理统计、自动控制、数据排序、数据压缩和检错纠错等常用算法。从嵌入式系统的实际应用岀发,用通俗易懂的语言代替枯燥难懂的数学推导,使读者能在比较轻松的条件下学到最基本的常用算法,并为继续学习其他算法打下基础。本书可作为电子技术人员自学常用算法的教材,也可作为高等院校电子技术类专业本科生研究生的教学参考书。图书在版编目(CIP)数据嵌入式系统软件设计中的常用算法/周航慈著.一北京北京航空航天大学出版社,2010.1ISBN978-7-81124-943-9Ⅰ.嵌…Ⅱ.周…Ⅲ.微型计算机一软件设计一算法Ⅳ.TP311.5中国版本图书馆(IP数据核字(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册ISBN9787811249439定价: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有回代过程的主元消去法1.2行列式法·鲁1.2.1行刎式法概述······.··:·····121.2.2三元线性方程组的行列式法应用实例DD鲁。鲁D·D。鲁·········.·.:·.·····..·.·······数学模型分析161.3.2算法设计………3.3程序设计20第2章常用代数插值和曲线拟合算法。·DDDD暑·鲁鲁。鲁·,·香带看看。香着。212.1线性插值∴261.1算法原理2.1.2应用实例272.2抛物线插值92.2.1算法原理…………·非鲁.DDBD曹鲁。鲁。。。。。·非。··。非。香D看曹看鲁音b。·非。2.2.2应用实例…322.3曲线拟合...··.····.···..·····.:·.·······.·······线性拟合算法及其应用实例抛物线拟合算法及其应用实例D。DD·D第3章常用数值积分算法523.1算法原理··曾曹曹曹·3.2应用实例……第4章常用能谱处理算法…4.1谱曲线平滑着看看D着着D着·D4.1.1算法原理4.1.2算法程序……………………………………………………………………604.2谱峰定位…………………614.2.1算法原理624.2.2算法程序…………………………………………………………………624.3能量刻度·····634.3.1算法原理……………………644.3.2算法程序66A.4峰面积计算4.4.1算法原理…。鲁更.....····674.4.2算法程序684.5含量计算第5章常用数字滤波算法…;;·····.·······;····705.1程序判断滤波5.2中值滤波…·.····..·············∴…………………745.3算术平均滤波775.4去极值平均滤波……··.·.··。。着。看着D着·D着·鲁·。。·5.5滑动平均滤波806滑动加权滤波…5.7一阶滯后滤波5.8数字滤波算法小结…84第6章常用数理统计算法…6.1数据样品的正态分布…6.2均值和均方差的估算6.3川数理统计方法消除粗人误差酯画…………………………………886.4用数理统计方法计算线性相关系数第7章常用自动控制算法b鲁·b。鲁937.1简单阈值控制算法原理··.···..·.·.·.·······.······7.1.2应用实例···············;········.········…………………………∴…967.2经典PI控制…∷10l算法原理1027.2.2PID控制算法在应用中需要解决的问题……106第8章常用数据排序算法1088.1归并排序108算法原理……………………1088.1.2算法程序1098.1.3改进的算法······會,8.2快速排序…·。·鲁D曹看D看………………………………1268.2.1算法原理…1268.2.2算法程序…………………………………………………………………1288.2.3非递归算法程序……130第9章常用数据压缩算法…..··..:··..··....·..·:..·.··…………∷…1349.1信源编码概述1349.2霍大曼编码。。。。。。。。。。,,,,。,,。,,,,。.,。1369.2.1变长码1369.2.2霍夫曼编码原理………1399.2.3霍夫曼编码算法程序1419.3批量采样数据的压缩编码……………………………………………………147紧凑压缩编码9.3.2增量压缩编码………………………………150预测压缩编码153第10章常用检错与纠错算法……….···15810.1检错码…·10.1.1检错原理……………∴……15810.1.2奇偶校验10.1.3和校验16410.1.4循环冗余校验(CRC校验16710.2纠错码…10.2.1纠错原理17110.2.2汉明码17110.2.3检二纠一码10.2.4抗突发干扰的措施…186参考文献………189第1章常用线性方程组求解算法在一个嵌人式系统中,往往繙要从外部环境中获取若干个信息(多输入),然后通过数据处理,从中求解出若干个结果(多输出)。如果多输出与多输入之间为线性关系,则将其称为“多变量线性系统”。在多变量线性系统中,经常要碰到求解多元线性方程组的问题,线性方程组的一般形式为AuX1+A12+.+ AlnX,= B1A21X1+AX+…+Anx=B2AnX1+A2X2+…+AXn=Bn写成矩阵形式便是:A1A12A137「xAiXBB:BA. AA-」LX线性方程组的求解算法有直接法和迭代法等它们各自又有分支。从嵌人式系统的特点出发,在这里只讨论最基本的主元消去法和行列式法,它们是直接法的代表。在本章的应用实例中,将介绍一个直接法和迭代法相结合的算法1.1主元消去法主元消去法又分总体选主元消去法和按列选主元消去法,由于前者每次选主元的范围大,速度相对慢,所以采用按列选主元消去法。主元消去法又分为无回代过程的主元消去法和有回代过程的主元消去法11.1无回代过程的主元消去法这里,通过求解一个具体的线性方程组来说明这一方法的计算步骤。第1章常用线性方程组求解箅法2x1+3x2+x3=1-1)2(1-2)嵌入式系统软件设计中的常用算法4x1+2写成矩阵形式便是31解第1步:为了提高计算的精度在第1列找出绝对值最大的系数作为第1列的主元这里是第3行的4。为了使主元位于主对角线上,把方程组中的式(1-1)和式(1-3)交换位置,得到等效的方程组4x1+2(1-4x1+2x2-x3=-3(1-5)2x1+3x8+(1-62写成矩阵形式便是:42-173第2步:用主元除式(1-4)中各个元素,则方程组变为:0.5x2-0.25+(1-8)2x1+3x2+写成矩阵形式便是0.50.2512第3步:用高斯消去法将式(1-8)和式(1-9)中x1的系数变为0。高斯消去法的算法原理如下:对于一个n阶线性方程组,设当前主元位于第i行第列(主元一定在主对角线上),通过前面若干步骤的处理已经将主元调整为1,主元左边各个系数均已为零,则主元所在的第i行成为:X,+A,+11+…+A4nXm1+A,Xn=B(1-10)
