ch1-编码与程序设计语言原理_201721913555131

1、 Ch1 编码与程序设计语言原理王 超Embedded System Lab Spring 2017本章提纲 编码 程序设计语言的原理与基本概念编码 编码是最原始的程序设计语言 编码出现要远远早于计算机和程序 常见的编码形式 摩尔斯码 字符编码ASCII, Unicode, UTF-8, GB2312 拼音、五笔 二进制编码 条形码与二维码 量子编码 DNA编码摩尔斯编码摩尔斯发明的的有线电报摩尔斯电码的演变摩尔斯电码的演变马可尼的无线电报机1901年，马可尼首次成功地实现了横跨大年，马可尼首次成功地实现了横跨大西洋的无线电通信西洋的无线电通信 可以由任何能够产生可控长短脉冲的装置发送，解码不

2、需要使用专门设备，适合小功率通信摩尔斯电码的优势A J S 1 . : B K T 2 , ; C L U 3 ? = D MV 4 + E N W5 ! - F O X 6 / _ G P Y 7 ( H Q Z 8 ) $ I R 0 9 & 摩尔斯电码摩尔斯电码-二叉树 点“嘀”长度为1个单位，划“哒”长度为3个单位 同一字母中点划间隔为1个单位 同一词中字母间隔为3个单位 词与词间隔为7个单位摩尔斯电码的时间控制QRA你台的名称是什么？QRV你准备好了吗？QRP要我降低发信机功率吗？QTH你的地理位置在？QRS要我发得慢一些吗？QSB我的信号有衰落吗？QRT 要我停止拍发吗？QSL你能

3、确认联络吗？QRU你有什么发给我吗？QRZ谁在叫我？QRM你受到他台干扰吗？QSA我的信号强度怎样？QRN你受到天电干扰吗？QSY要我改用别的频率拍发吗？Q简语与宏定义 称呼：U(你) / UR(你的) / OM(老朋友) / YL(女士) 问候：GM(早上好) / GA(下午好) / GE(晚上好) 状况：RST(信号报告) / RIG(设备) / ANT(天线) / PWR(功率) / WX(天气) / OP(操作员) 其它：DE(这里是) / R(收到) / K(发送结束 ) / TNX(Thanks) / TU(Thank you) / CLG(呼叫) / VY(非常) / PSE(请

4、) / NW(现在) / SOS(紧急呼救) / 73(Best regards) / 88(Love and kisses)发送摩尔斯电码的工具电键 手键手键 美式（平头）键簧较软 苏式（圆头）键簧较硬 半自动键半自动键 自动键自动键 单桨自动键（扫拨键） 双桨自动键特别的手键布莱叶盲文编码布莱叶编码的历史 路易斯布莱叶1809年出生于法国，1852去世 Valentin Hay(17451822 )，巴黎学校的创始人，发明了一种将字母凸印以供触摸阅读的方法。 法国陆军上尉Charles Barbier在1819年发明了一种夜间文字的书写体系，使用厚纸板上有规律凸起的点划来供士兵们在夜间无声

5、地传递口信。 布莱叶在上述原理基础上进行改进，1823年创建了布莱叶编码系统布莱叶编码的编码格式 共64种编码格式 数字、字母和标点符号都被编码成局限在23小格中一个或多个凸起的点。字母和数字的表示方法 字母： 例子： 数字： 例子：布莱叶编码扩展（宏定义） 二级布莱叶编码条形码与二维码条形码和二维码 条形码(barcode)是将宽度不等的多个黑条和空白，按照一定的编码规则排列，用以表达一组信息的图形标识符。PDF417码码QR码码Universal Product Code条形码的解码条形码的解码 第一个数字（在这里是 0）被称为数字系统字符， 0的意思是说这是一个规范的条形码。如果是具有不

6、同重量的货物（像肉类或其他商品），这个数字是 2；订单、票券的 U P C 编码的第一个数字通常是 5。 紧接着的 5个数字是制造商代码。再后面的 5个数字（ 0 1 2 5 1）是该公司的某种产品的编号。 最后的数字（这里是 7）称作模校验字符，这个字符可用来进行另外一种错误检验。条形码校验 为了解释校验字符是怎样工作的，将前 11个数字（是 0 51000 01251）各用一个字母来代替：A BCDEF GHIJK 然后，计算下式的值：3（A + C + E + G + I + K）+（B + D + F + H + J）3（0 + 1 + 0 + 0 + 2 + 1）+（5 + 0 +

7、0 + 1 + 5）= 34 + 11 = 2 3从紧挨它并大于等于它的一个1 0的整倍数中减去它，其结果称为模校验字符。紧挨2 3并大于等于 2 3的一个1 0的整倍数是 3 0 ,故：3 02 3 = 7 这就是印在外包装上并以 UPC（Universal Product Code）形式编码的模校验字符，这是一种冗余措施。如果扫描仪计算出来的模校验结果和 U P C中编码中的校验字不一致，计算机就不能将这个 U P C作为一个有效值接收。二进制与逻辑门需要复习的背景知识计算机组成原理 二进制、八进制、十进制、十六进制的转换 与、或、非、同或、异或、或非、与非 全加器、半加器、反向器 原码、

8、反码、补码 锁存器、触发器扩充的 2的各次幂的表 不同进制之间的转换常见的逻辑门 与、或、非、与非、或非、与或非、异或、同或量子编码量子编码 量子计算是利用量子力学来大幅度加速计算，微软，谷歌，英特尔和IBM投入了数千万美元，通过不同的量子位技术来实现一台实用的量子计算机。量子计算机处理的信息是以量子位的形式存储的，每个量子位可以使1或0或这两个状态的叠加，因此可以表示比传统的二进制更多的数据。它有望解决人类一些最复杂的问题。它得到了亚马逊创始人兼 CEO Jeff Bezos、NASA 和 CIA 的支持。每一台造价 10,000,000 美元并且在零下 459 度下运行。而且没人知道它究竟

9、是怎样工作的。量子计算机http:/ 使用格型架构（lattice architecture）的 5 量子位处理器，其可以扩展成更大更强的量子计算机和 1950 年代早期的计算机一样，今天的量子计算机要占据一整个实验室量子计算的研究硬件加拿大的D-Wave公司首先实现了16个超导量子比特的量子计算机，可以提高优化问题的效率。谷歌和IBM都是用超导量子技术来实现计算设备。英特尔投资荷兰代尔夫特理工大学的量子技术研究项目QuTech，使用“硅原子点”技术，通过向纯硅中加入电子造出的人造原子，微波控制电子的量子态。微软选择基于非阿贝尔任意子的拓扑量子比特，电子通过半导体结构时会出现准离子，他们交叉路

10、径可以用来编写量子信息，可以减少错误修正比特数量，还需要进一步验证其是否存在。ionQ的Chris Monroe坚持囚禁离子技术，并在马里兰大学的实验室客服对离子控制的挑战。超导量子位（superconducting qubits）囚禁离子（trapped ions）量子计算的研究软件 微软联合加州大学圣芭芭拉分校Station Q实验室，Redmod的QuArC团队 Intel-荷兰戴尔福特理工大学的QuTech实验室 普渡大学的Station Q Purdue实验室 马里兰大学，悉尼大学，哥本哈根大学的QDev实验室 谷歌与加州大学圣芭芭拉分校John M. Martinis团队合作利用超

11、导体建立量子计算机 IBM的沃森实验室 耶鲁大学Schoelkopf实验室 NASA量子人工智能实验室 中科院量子信息重点实验室等团队均在关注量子计算领域。目标应用 加解密 将两个大素数（万位以上）相乘十分容易，但是想要对其乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥，计算机需要处理几千年。 2001 年，IBM 使用一台 7 量子位的量子计算机求解了 15 的因子 3 和 5 2012 年，一个研究团队求解了 21 的因子。然后到了 2014 年，一种被称为极小化算法（minimization algorithm）的前沿方法成功求解了 56,153 的因子。 仿真IBM开放量子

12、计算仿真平台https:/ 通过检测DNA，并通过测序技术，与目标DNA进行对比。 为什么测序？ 疾病检测 预防与治疗 人工培育工作流程测序（Sanger法）测序与匹配 与目标串进行比对（串匹配算法） 基因变异，允许误差（灵敏度）技术发展-成本降低/sequencingcostsdata/目前主要挑战性问题 计算和存储的增长速度与数据规模难以匹配The cancer genome，Michael R. Stratton, Peter J. Campbell & P. Andrew Futreal，Nature 458, 719-724(9 April

13、2009)数据规模增长速度：数据规模增长速度：2 2年年1010倍倍存储增长速度：存储增长速度：2 2年年4 4倍倍处理器增长速度：处理器增长速度：1818个月个月2 2倍倍作业1、复习二进制、八进制、十进制、十六进制之间的互相转换2、复习逻辑门和移位等操作的物理结构与操作原理3、调研QR二维码的识别过程4、阅读量子计算机和DNA测序的相关文献或者论文程序设计语言原理本章内容 程序设计语言的发展 计算模型和语言范型 语言：标准和实现 语言的开发和标准化 新趋势程序设计语言的发展 程序是计算机科学技术领域最基本最核心的概念，有计算机就必须有程序，有描述程序的手段和方式，即，必须有描述程序的程序设

14、计语言 硬件计算机，就是机器语言程序的执行器机器语言程序的执行器（解释器） 计算机硬件只能处理二进制二进制形式的程序（机器语言程序）。如MIPS机器语言：用欧几里得算法求GCD的程序 机器语言，人很难阅读、理解、使用 使用机器开发程序的成本高昂，耗时巨大，容易出错，难以检查，依赖于具体计算机，移植困难程序设计语言的发展 为解决程序的易写和可读性，人们发展了符号形式的汇编语言。例 每条指令都很容易理解，容易书写和阅读 仍用与机器语言直接对应的简单线性形式。没有高级结构，不支持程序的高级组织，大型程序难以理解和开发，移植性差MIPS汇编语言：汇编语言：GCD程序程序Top 10 编程语言 TIOB

15、E 指数走势(2002-2016)2016-12 月编程语言排行榜 TOP20为什么有这么多语言 计算机的应用领域丰富多彩 不同领域、不同具体应用对于合适的语言有不同要求 一种语言无法最好地满足所有应用的需要 语言设计的许多方面有很多选择 不同的设计选择通常是各有各的优点和缺点 常常是“鱼和熊掌不可兼得” 新应用领域和应用需求不断出现 不同领域（任务）有特殊的功能或描述方式的要求 为满足新需要，人们常常设计出新的语言 如网络、实时应用、图形用户界面，业务处理等为什么有这么多语言 硬件发展，例如速度、容量、并行机、RISC等 有些过去认为“奢侈”的特征，由于有助于软件系统的开发者，慢慢变成必备的

16、特征（如GC） 例：近来多核多处理器系统正在快速发展，要求新的编程方式和技术，将推动语言里支持并行程序设计的特征的大发展 安迪-比尔定律 程序技术发展，如 结构化程序设计（结构化程序设计语言） 面向对象的程序设计（面向对象的语言） 脚本技术，等 应用的驱动和牵引 程序设计语言的发展 计算模型和语言范型 语言：标准和实现 语言的开发和标准化 新趋势计算模型和语言范型 形成许多程序设计语言的另一重要原因：对计算过程可以有多种不同看法，由此产生了不同的计算模型（范型，Paradigms） 基于不同计算范型产生了不同的语言类（语言范型）。主要范型有： 过程式范型（Procedural，或称命令式，Im

17、perative）： 把计算看成一系列操作的执行，基本计算元素是一组基本操作。计算在一个环境里进行，操作的效果就是改变环境的状态： 语言提供一组基本操作和一组描述组合操作的手段，提供的抽象手段是定义新操作（定义过程）。过程实现大步的状态变换 写程序就是描述操作执行的顺序过程，描述状态和状态的变化 常规语言，如C，Pascal，Fortran 等，都是命令式语言计算模型和语言范型 函数式范型（Functional）： 把计算看成对数据的函数变换，一个计算就是一系列函数变换 基本计算元素是一组基本函数，语言提供各种函数组合机制（复合、函 数选择），抽象手段是定义新函数（允许递归定义） 最早的函数式

18、语言是John McCarthy 开发的Lisp。目前最重要的函数式语言包括Common Lisp，Scheme，ML 和Haskell 等。Scheme例子 Scheme 语言是LISP语言的一个方言(或说成变种)，它诞生于1975年的MIT。 可以采用可以采用Guile(GNUsextensionlanguage)。Guile是GNU工程的一个项目，它是GNU扩展语言库，它也是Scheme语言的一个具体实现。 变量定义变量定义(define a 100) (set! a “xyz) Lambda关键字关键字来定义过程(define add5 (lambda (x) (+ x 5) (add

19、5 1) = 5(define square (lambda (x) (* x x) 过程的嵌套定义过程的嵌套定义(define fix (define fix (lambda (x y z) (lambda (x y z) (define add (define add (lambda (a b) (+ a b) (lambda (a b) (+ a b) (- x (add y z) (- x (add y z)(display (fix 100 20 30)(display (fix 100 20 30)Scheme代码的结构 顺序结构 if结构结构 Case结构结构 递归递归(begi

20、n (begin (display Hello world!) ; (display Hello world!) ; 输出输出Hello world! (newline) (newline) ; ; 换行换行(if (= x 0) (if (= x 0) (display is zero)(display is zero)(display not zero)(display not zero)(case (case (* * 2 3) 2 3) (2 3 5 7) prime) (2 3 5 7) prime) (1 4 6 8 9) composite) (1 4 6 8 9) compos

21、ite)参考参考LispLisp和和SchemeScheme相关语言教程，结论：语法简洁、效率高相关语言教程，结论：语法简洁、效率高(define factoral (lambda (x)(define factoral (lambda (x) (if (= x 1) 1 (if (汇编语言-高级语言 计算模型和语言范型 过程式： C 函数式:Scheme (语法例子) 面向对象:Java 逻辑式:Prolog （例子）程序设计语言 语言：标准和实现 翻译和解释 纯编译 C 纯解释 脚本语言 编译+解释 Java-Lisp 即时编译和动态编译优化 微程序优化语言设计：实例不同设计目标导致了不同

22、的语言设计： Fortran：高效的大规模数值计算 Lisp：灵活的符号表达式处理，数据与程序的统一 Pascal：结构化程序设计，教学，清晰的基本程序设计概念 C：系统程序设计，低级操作与高级语言结构的结合 Smalltalk：概念的统一性和最小化，面向对象 C+：复杂的系统程序设计，低级机制与高级抽象机制（数据抽象的面向对象）的有机融合，支持多种范型的程序设计技术 Ada：复杂软件，复杂的嵌入式系统、实时系统 Java：支持面向对象的程序设计，平台无关性，一次编程到处使用，网络环境下的应用，安全性 Python, Perl等重要性：图灵奖 1966-2010，45届图灵奖，届图灵奖，15届

23、由于与程序设计语言有关的工作获奖届由于与程序设计语言有关的工作获奖1966, Alan J. Perlis, 早期语言和早期语言和Algol 60的贡献，图灵奖第一位获奖者的贡献，图灵奖第一位获奖者1971, John McCarthy, LISP语言语言, 程序语程序语义义, 程序理论程序理论1972, E. W. Dijkstra, Algol编译编译, 结构化结构化程序设计程序设计, 并发概念和原语并发概念和原语, 形式化推导形式化推导, 卫式命令等卫式命令等1977, John Backus, Fortran语言语言, FP语言语言, BNF等等1978, Robert Floyd,

24、Algol编译编译, 编译技术编译技术, 程序优化程序优化, 归纳断言法和前后断言归纳断言法和前后断言, 程序程序正确性正确性, 编译生成编译生成1979, K. E. Iverson, APL语言语言1980, C.A.R. Hoare, 结构化程序设计结构化程序设计, case语句语句, 公理语义学公理语义学, 并发程序理论并发程序理论, CSP 等等1983, Dennis Ritchie 和和Thompson, C语语言和言和UNIX1984, Niklaus Wirth, Algol W, PL 360, Pascal, Modula-1/2, Oberon, 逐步求精逐步求精, 结构化程序设计结构化程序设计, 语法图语法图1991, Robin Milner, ML语言语言, 并发理论并发理论, CCS2001, Ole-Johan Dahl 和和Kristen Nygaard, Simula语言语言, OO概念概念2003, Alan