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

社 版 出 学 大 天 航 空 航 京 北 嵌入式系统软件设计基础丛书 嵌入式系统软件设计中的 常用算法 社 版 周航慈 著 出 学 大 天 航 空 航 京 北 内容简介 本书根据嵌入式系统 软 件 设 计 需 要 的 常 用 算 法 知 识 编 写 而 成。 基 本 内 容 有:线 性 方 程 组 求 解、代数插值和曲线拟合、数值积 分、能 谱 处 理、数 字 滤 波、数 理 统 计、自 动 控 制、数 据 排 序、数 据 压 缩和检错纠错等常用算法。从嵌入式系统的实际应用出发,用 通 俗 易 懂 的 语 言 代 替 枯 燥 难 懂 的 数 学 推 导 ,使 读 者 能 在 比 较 轻 松 的 条 件 下 学 到 最 基 本 的 常 用 算 法 ,并 为 继 续 学 习 其 他 算 法 打 下 基 础 。 本书可作为电子技术人员自学 常 用 算 法 的 教 材,也 可 作 为 高 等 院 校 电 子 技 术 类 专 业 本 科 生、 研究生的教学参考书。 图 书 在 版 编 目 (CIP)数 据 嵌 入 式 系 统 软 件 设 计 中 的 常 用 算 法/周 航 慈 著 .— 北 京 : 社 北 京 航 空 航 天 大 学 出 版 社 ,2010.1 版 ISBN978 7 81124 943 9 出 学 Ⅰ.嵌… Ⅱ.周… Ⅲ.微型计算机—软件设计—算法 Ⅳ .TP311.5 大 天 中国版本图书馆 CIP 数据核字(2009)第189989号 航 空 航 京 北 嵌入式系统软件设计中的常用算法 周航慈 著 责任编辑 董云凤 张金伟 * 北京航空航天大学出版社出版发行 北京市海淀区学院路37号(100191) 发行部电话:010 82317024 传真:010 82328026 http://www.buaapress.com.cn E-mail:bhpress@263.net 印刷有限公司印装 各地书店经销 * 开本:787mm×960mm 1/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 无回代过程的主元消去法 ………………………………………………… 1 版 1.1.2 有回代过程的主元消去法 ………………………………………………… 8 出 1.2 行列式法……………………………………………………………………………… 12 学 1.2.1 行列式法概述 ……………………………………………………………… 12 大 1.2.2 三元线性方程组的行列式法 ……………………………………………… 13 天 1.3 应用实例……………………………………………………………………………… 16 航 1.3.1 数学模型分析 ……………………………………………………………… 16 空 1.3.2 算法设计 …………………………………………………………………… 18 1.3.3 程序设计 …………………………………………………………………… 20 航 第2章 常用代数插值和曲线拟合算法 ……………………………………………………… 24 京 2.1 线性插值……………………………………………………………………………… 26 北 2.1.1 算法原理 …………………………………………………………………… 26 2.1.2 应用实例 …………………………………………………………………… 27 2.2 抛物线插值…………………………………………………………………………… 29 2.2.1 算法原理 …………………………………………………………………… 29 2.2.2 应用实例 …………………………………………………………………… 32 2.3 曲线拟合……………………………………………………………………………… 36 2.3.1 线性拟合算法及其应用实例 ……………………………………………… 38 2.3.2 抛物线拟合算法及其应用实例 …………………………………………… 47 第3章 常用数值积分算法 …………………………………………………………………… 52 3.1 算法原理……………………………………………………………………………… 52 3.2 应用实例……………………………………………………………………………… 55 第4章 常用能谱处理算法 …………………………………………………………………… 58 4.1 谱曲线平滑…………………………………………………………………………… 58 4.1.1 算法原理 …………………………………………………………………… 58 4.1.2 算法程序 …………………………………………………………………… 60 4.2 谱峰定位……………………………………………………………………………… 61 4.2.1 算法原理 …………………………………………………………………… 62 4.2.2 算法程序 …………………………………………………………………… 62 4.3 能量刻度……………………………………………………………………………… 63 4.3.1 算法原理 …………………………………………………………………… 64 4.3.2 算法程序 …………………………………………………………………… 66 4.4 峰面积计算…………………………………………………………………………… 67 社 4.4.1 算法原理 …………………………………………………………………… 67 版 4.4.2 算法程序 …………………………………………………………………… 68 4.5 含量计算……………………………………………………………………………… 69 出 第5章 常用数字滤波算法 …………………………………………………………………… 70 学 5.1 程序判断滤波………………………………………………………………………… 70 大 5.2 中值滤波……………………………………………………………………………… 74 天 5.3 算术平均滤波………………………………………………………………………… 77 航 5.4 去极值平均滤波……………………………………………………………………… 78 空 5.5 滑动平均滤波………………………………………………………………………… 80 5.6 滑动加权滤波………………………………………………………………………… 82 航 5.7 一阶滞后滤波………………………………………………………………………… 83 京 5.8 数字滤波算法小结…………………………………………………………………… 84 北 第6章 常用数理统计算法 …………………………………………………………………… 86 6.1 数据样品的正态分布………………………………………………………………… 86 6.2 均值和均方差的估算………………………………………………………………… 88 6.3 用数理统计方法消除粗大误差……………………………………………………… 88 6.4 用数理统计方法计算线性相关系数………………………………………………… 91 第7章 常用自动控制算法 …………………………………………………………………… 93 7.1 简单阈值控制………………………………………………………………………… 93 7.1.1 算法原理 …………………………………………………………………… 93 7.1.2 应用实例 …………………………………………………………………… 96 7.2 经典 PID 控制 ……………………………………………………………………… 101 7.2.1 算法原理 ………………………………………………………………… 102 7.2.2 PID 控制算法在应用中需要解决的问题 ……………………………… 106 第8章 常用数据排序算法…………………………………………………………………… 108 8.1 归并排序 …………………………………………………………………………… 108 8.1.1 算法原理 ………………………………………………………………… 108 8.1.2 算法程序 ………………………………………………………………… 109 8.1.3 改进的算法 ……………………………………………………………… 116 8.2 快速排序 …………………………………………………………………………… 126 8.2.1 算法原理 ………………………………………………………………… 126 8.2.2 算法程序 ………………………………………………………………… 128 8.2.3 非递归算法程序 ………………………………………………………… 130 第9章 常用数据压缩算法…………………………………………………………………… 134 社 9.1 信源编码概述 ……………………………………………………………………… 134 版 9.2 霍夫曼编码 ………………………………………………………………………… 136 9.2.1 9.2.2 9.2.3 变长码 …………………………………………………………………… 136 出 霍夫曼编码原理 ………………………………………………………… 139 学 霍夫曼编码算法程序 …………………………………………………… 141 大 9.3 批量采样数据的压缩编码 ………………………………………………………… 147 天 9.3.1 紧凑压缩编码 …………………………………………………………… 147 航 9.3.2 增量压缩编码 …………………………………………………………… 150 空 9.3.3 预测压缩编码 …………………………………………………………… 153 第10章 常用检错与纠错算法 ……………………………………………………………… 158 航 10.1 检错码……………………………………………………………………………… 158 京 10.1.1 检错原理 ………………………………………………………………… 158 北 10.1.2 奇偶校验 ………………………………………………………………… 160 10.1.3 和校验 …………………………………………………………………… 164 10.1.4 循环冗余校验(CRC 校验) …………………………………………… 167 10.2 纠错码……………………………………………………………………………… 171 10.2.1 纠错原理 ………………………………………………………………… 171 10.2.2 汉明码 …………………………………………………………………… 171 10.2.3 检二纠一码 ……………………………………………………………… 177 10.2.4 抗突发干扰的措施 ……………………………………………………… 186 参考文献………………………………………………………………………………………… 189