ch1-編碼與程序設計語言原理_201721913555131

1、 Ch1 編碼與程序設計語言原理王 超Embedded System Lab Spring 2017本章提綱 編碼 程序設計語言的原理與基本概念編碼 編碼是最原始的程序設計語言 編碼出現(xiàn)要遠遠早于計算機和程序 常見的編碼形式 摩爾斯碼 字符編碼ASCII, Unicode, UTF-8, GB2312 拼音、五筆 二進制編碼 條形碼與二維碼 量子編碼 DNA編碼摩爾斯編碼摩爾斯發(fā)明的的有線電報摩爾斯電碼的演變摩爾斯電碼的演變馬可尼的無線電報機1901年，馬可尼首次成功地實現(xiàn)了橫跨大年，馬可尼首次成功地實現(xiàn)了橫跨大西洋的無線電通信西洋的無線電通信 可以由任何能夠產(chǎn)生可控長短脈沖的裝置發(fā)送，解碼不

2、需要使用專門設備，適合小功率通信摩爾斯電碼的優(yōu)勢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要我降低發(fā)信機功率嗎？QTH你的地理位置在？QRS要我發(fā)得慢一些嗎？QSB我的信號有衰落嗎？QRT 要我停止拍發(fā)嗎？Q

3、SL你能確認聯(lián)絡嗎？QRU你有什么發(fā)給我嗎？QRZ誰在叫我？QRM你受到他臺干擾嗎？QSA我的信號強度怎樣？QRN你受到天電干擾嗎？QSY要我改用別的頻率拍發(fā)嗎？Q簡語與宏定義 稱呼：U(你) / UR(你的) / OM(老朋友) / YL(女士) 問候：GM(早上好) / GA(下午好) / GE(晚上好) 狀況：RST(信號報告) / RIG(設備) / ANT(天線) / PWR(功率) / WX(天氣) / OP(操作員) 其它：DE(這里是) / R(收到) / K(發(fā)送結束 ) / TNX(Thanks) / TU(Thank you) / CLG(呼叫) / VY(非常) / P

4、SE(請) / NW(現(xiàn)在) / SOS(緊急呼救) / 73(Best regards) / 88(Love and kisses)發(fā)送摩爾斯電碼的工具電鍵 手鍵手鍵 美式（平頭）鍵簧較軟 蘇式（圓頭）鍵簧較硬 半自動鍵半自動鍵 自動鍵自動鍵 單槳自動鍵（掃撥鍵） 雙槳自動鍵特別的手鍵布萊葉盲文編碼布萊葉編碼的歷史 路易斯布萊葉1809年出生于法國，1852去世 Valentin Hay(17451822 )，巴黎學校的創(chuàng)始人，發(fā)明了一種將字母凸印以供觸摸閱讀的方法。 法國陸軍上尉Charles Barbier在1819年發(fā)明了一種夜間文字的書寫體系，使用厚紙板上有規(guī)律凸起的點劃來供士兵們在

5、夜間無聲地傳遞口信。 布萊葉在上述原理基礎上進行改進，1823年創(chuàng)建了布萊葉編碼系統(tǒng)布萊葉編碼的編碼格式 共64種編碼格式 數(shù)字、字母和標點符號都被編碼成局限在23小格中一個或多個凸起的點。字母和數(shù)字的表示方法 字母： 例子： 數(shù)字： 例子：布萊葉編碼擴展（宏定義） 二級布萊葉編碼條形碼與二維碼條形碼和二維碼 條形碼(barcode)是將寬度不等的多個黑條和空白，按照一定的編碼規(guī)則排列，用以表達一組信息的圖形標識符。PDF417碼碼QR碼碼Universal Product Code條形碼的解碼條形碼的解碼 第一個數(shù)字（在這里是 0）被稱為數(shù)字系統(tǒng)字符， 0的意思是說這是一個規(guī)范的條形碼。如果

6、是具有不同重量的貨物（像肉類或其他商品），這個數(shù)字是 2；訂單、票券的 U P C 編碼的第一個數(shù)字通常是 5。 緊接著的 5個數(shù)字是制造商代碼。再后面的 5個數(shù)字（ 0 1 2 5 1）是該公司的某種產(chǎn)品的編號。 最后的數(shù)字（這里是 7）稱作模校驗字符，這個字符可用來進行另外一種錯誤檢驗。條形碼校驗 為了解釋校驗字符是怎樣工作的，將前 11個數(shù)字（是 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 +

7、0 + 0 + 1 + 5）= 34 + 11 = 2 3從緊挨它并大于等于它的一個1 0的整倍數(shù)中減去它，其結果稱為模校驗字符。緊挨2 3并大于等于 2 3的一個1 0的整倍數(shù)是 3 0 ,故：3 02 3 = 7 這就是印在外包裝上并以 UPC（Universal Product Code）形式編碼的模校驗字符，這是一種冗余措施。如果掃描儀計算出來的模校驗結果和 U P C中編碼中的校驗字不一致，計算機就不能將這個 U P C作為一個有效值接收。二進制與邏輯門需要復習的背景知識計算機組成原理 二進制、八進制、十進制、十六進制的轉換 與、或、非、同或、異或、或非、與非 全加器、半加器、反向器

8、 原碼、反碼、補碼 鎖存器、觸發(fā)器擴充的 2的各次冪的表 不同進制之間的轉換常見的邏輯門 與、或、非、與非、或非、與或非、異或、同或量子編碼量子編碼 量子計算是利用量子力學來大幅度加速計算，微軟，谷歌，英特爾和IBM投入了數(shù)千萬美元，通過不同的量子位技術來實現(xiàn)一臺實用的量子計算機。量子計算機處理的信息是以量子位的形式存儲的，每個量子位可以使1或0或這兩個狀態(tài)的疊加，因此可以表示比傳統(tǒng)的二進制更多的數(shù)據(jù)。它有望解決人類一些最復雜的問題。它得到了亞馬遜創(chuàng)始人兼 CEO Jeff Bezos、NASA 和 CIA 的支持。每一臺造價 10,000,000 美元并且在零下 459 度下運行。而且沒人知

9、道它究竟是怎樣工作的。量子計算機http:/ 使用格型架構（lattice architecture）的 5 量子位處理器，其可以擴展成更大更強的量子計算機和 1950 年代早期的計算機一樣，今天的量子計算機要占據(jù)一整個實驗室量子計算的研究硬件加拿大的D-Wave公司首先實現(xiàn)了16個超導量子比特的量子計算機，可以提高優(yōu)化問題的效率。谷歌和IBM都是用超導量子技術來實現(xiàn)計算設備。英特爾投資荷蘭代爾夫特理工大學的量子技術研究項目QuTech，使用“硅原子點”技術，通過向純硅中加入電子造出的人造原子，微波控制電子的量子態(tài)。微軟選擇基于非阿貝爾任意子的拓撲量子比特，電子通過半導體結構時會出現(xiàn)準離子，他

10、們交叉路徑可以用來編寫量子信息，可以減少錯誤修正比特數(shù)量，還需要進一步驗證其是否存在。ionQ的Chris Monroe堅持囚禁離子技術，并在馬里蘭大學的實驗室客服對離子控制的挑戰(zhàn)。超導量子位（superconducting qubits）囚禁離子（trapped ions）量子計算的研究軟件 微軟聯(lián)合加州大學圣芭芭拉分校Station Q實驗室，Redmod的QuArC團隊 Intel-荷蘭戴爾福特理工大學的QuTech實驗室 普渡大學的Station Q Purdue實驗室 馬里蘭大學，悉尼大學，哥本哈根大學的QDev實驗室 谷歌與加州大學圣芭芭拉分校John M. Martinis團隊合

11、作利用超導體建立量子計算機 IBM的沃森實驗室 耶魯大學Schoelkopf實驗室 NASA量子人工智能實驗室 中科院量子信息重點實驗室等團隊均在關注量子計算領域。目標應用 加解密 將兩個大素數(shù)（萬位以上）相乘十分容易，但是想要對其乘積進行因式分解卻極其困難，因此可以將乘積公開作為加密密鑰，計算機需要處理幾千年。 2001 年，IBM 使用一臺 7 量子位的量子計算機求解了 15 的因子 3 和 5 2012 年，一個研究團隊求解了 21 的因子。然后到了 2014 年，一種被稱為極小化算法（minimization algorithm）的前沿方法成功求解了 56,153 的因子。 仿真IBM

12、開放量子計算仿真平臺https:/ 通過檢測DNA，并通過測序技術，與目標DNA進行對比。 為什么測序？ 疾病檢測 預防與治療 人工培育工作流程測序（Sanger法）測序與匹配 與目標串進行比對（串匹配算法） 基因變異，允許誤差（靈敏度）技術發(fā)展-成本降低/sequencingcostsdata/目前主要挑戰(zhàn)性問題 計算和存儲的增長速度與數(shù)據(jù)規(guī)模難以匹配The cancer genome，Michael R. Stratton, Peter J. Campbell & P. Andrew Futreal，Nature 458, 719-724(

13、9 April 2009)數(shù)據(jù)規(guī)模增長速度：數(shù)據(jù)規(guī)模增長速度：2 2年年1010倍倍存儲增長速度：存儲增長速度：2 2年年4 4倍倍處理器增長速度：處理器增長速度：1818個月個月2 2倍倍作業(yè)1、復習二進制、八進制、十進制、十六進制之間的互相轉換2、復習邏輯門和移位等操作的物理結構與操作原理3、調研QR二維碼的識別過程4、閱讀量子計算機和DNA測序的相關文獻或者論文程序設計語言原理本章內容 程序設計語言的發(fā)展 計算模型和語言范型 語言：標準和實現(xiàn) 語言的開發(fā)和標準化 新趨勢程序設計語言的發(fā)展 程序是計算機科學技術領域最基本最核心的概念，有計算機就必須有程序，有描述程序的手段和方式，即，必須有

14、描述程序的程序設計語言 硬件計算機，就是機器語言程序的執(zhí)行器機器語言程序的執(zhí)行器（解釋器） 計算機硬件只能處理二進制二進制形式的程序（機器語言程序）。如MIPS機器語言：用歐幾里得算法求GCD的程序 機器語言，人很難閱讀、理解、使用 使用機器開發(fā)程序的成本高昂，耗時巨大，容易出錯，難以檢查，依賴于具體計算機，移植困難程序設計語言的發(fā)展 為解決程序的易寫和可讀性，人們發(fā)展了符號形式的匯編語言。例 每條指令都很容易理解，容易書寫和閱讀 仍用與機器語言直接對應的簡單線性形式。沒有高級結構，不支持程序的高級組織，大型程序難以理解和開發(fā)，移植性差MIPS匯編語言：匯編語言：GCD程序程序Top 10 編

15、程語言 TIOBE 指數(shù)走勢(2002-2016)2016-12 月編程語言排行榜 TOP20為什么有這么多語言 計算機的應用領域豐富多彩 不同領域、不同具體應用對于合適的語言有不同要求 一種語言無法最好地滿足所有應用的需要 語言設計的許多方面有很多選擇 不同的設計選擇通常是各有各的優(yōu)點和缺點 常常是“魚和熊掌不可兼得” 新應用領域和應用需求不斷出現(xiàn) 不同領域（任務）有特殊的功能或描述方式的要求 為滿足新需要，人們常常設計出新的語言 如網(wǎng)絡、實時應用、圖形用戶界面，業(yè)務處理等為什么有這么多語言 硬件發(fā)展，例如速度、容量、并行機、RISC等 有些過去認為“奢侈”的特征，由于有助于軟件系統(tǒng)的開發(fā)者

16、，慢慢變成必備的特征（如GC） 例：近來多核多處理器系統(tǒng)正在快速發(fā)展，要求新的編程方式和技術，將推動語言里支持并行程序設計的特征的大發(fā)展 安迪-比爾定律 程序技術發(fā)展，如 結構化程序設計（結構化程序設計語言） 面向對象的程序設計（面向對象的語言） 腳本技術，等 應用的驅動和牽引 程序設計語言的發(fā)展 計算模型和語言范型 語言：標準和實現(xiàn) 語言的開發(fā)和標準化 新趨勢計算模型和語言范型 形成許多程序設計語言的另一重要原因：對計算過程可以有多種不同看法，由此產(chǎn)生了不同的計算模型（范型，Paradigms） 基于不同計算范型產(chǎn)生了不同的語言類（語言范型）。主要范型有： 過程式范型（Procedural，

17、或稱命令式，Imperative）： 把計算看成一系列操作的執(zhí)行，基本計算元素是一組基本操作。計算在一個環(huán)境里進行，操作的效果就是改變環(huán)境的狀態(tài)： 語言提供一組基本操作和一組描述組合操作的手段，提供的抽象手段是定義新操作（定義過程）。過程實現(xiàn)大步的狀態(tài)變換 寫程序就是描述操作執(zhí)行的順序過程，描述狀態(tài)和狀態(tài)的變化 常規(guī)語言，如C，Pascal，F(xiàn)ortran 等，都是命令式語言計算模型和語言范型 函數(shù)式范型（Functional）： 把計算看成對數(shù)據(jù)的函數(shù)變換，一個計算就是一系列函數(shù)變換 基本計算元素是一組基本函數(shù)，語言提供各種函數(shù)組合機制（復合、函 數(shù)選擇），抽象手段是定義新函數(shù)（允許遞歸定義

18、） 最早的函數(shù)式語言是John McCarthy 開發(fā)的Lisp。目前最重要的函數(shù)式語言包括Common Lisp，Scheme，ML 和Haskell 等。Scheme例子 Scheme 語言是LISP語言的一個方言(或說成變種)，它誕生于1975年的MIT。 可以采用可以采用Guile(GNUsextensionlanguage)。Guile是GNU工程的一個項目，它是GNU擴展語言庫，它也是Scheme語言的一個具體實現(xiàn)。 變量定義變量定義(define a 100) (set! a “xyz) Lambda關鍵字關鍵字來定義過程(define add5 (lambda (x) (+ x

19、 5) (add5 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結構結構 遞

20、歸遞歸(begin (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

21、) composite)參考參考LispLisp和和SchemeScheme相關語言教程，結論：語法簡潔、效率高相關語言教程，結論：語法簡潔、效率高(define (define factoralfactoral (lambda (x) (lambda (x) (if (= x 1) 1 (if (匯編語言-高級語言 計算模型和語言范型 過程式： C 函數(shù)式:Scheme (語法例子) 面向對象:Java 邏輯式:Prolog （例子）程序設計語言 語言：標準和實現(xiàn) 翻譯和解釋 純編譯 C 純解釋 腳本語言 編譯+解釋 Java-Lisp 即時編譯和動態(tài)編譯優(yōu)化 微程序優(yōu)化語言設計：實例不同設

22、計目標導致了不同的語言設計： Fortran：高效的大規(guī)模數(shù)值計算 Lisp：靈活的符號表達式處理，數(shù)據(jù)與程序的統(tǒng)一 Pascal：結構化程序設計，教學，清晰的基本程序設計概念 C：系統(tǒng)程序設計，低級操作與高級語言結構的結合 Smalltalk：概念的統(tǒng)一性和最小化，面向對象 C+：復雜的系統(tǒng)程序設計，低級機制與高級抽象機制（數(shù)據(jù)抽象的面向對象）的有機融合，支持多種范型的程序設計技術 Ada：復雜軟件，復雜的嵌入式系統(tǒng)、實時系統(tǒng) Java：支持面向對象的程序設計，平臺無關性，一次編程到處使用，網(wǎng)絡環(huán)境下的應用，安全性 Python, Perl等重要性：圖靈獎 1966-2010，45屆圖靈獎，

23、屆圖靈獎，15屆由于與程序設計語言有關的工作獲獎屆由于與程序設計語言有關的工作獲獎1966, Alan J. Perlis, 早期語言和早期語言和Algol 60的貢獻，圖靈獎第一位獲獎者的貢獻，圖靈獎第一位獲獎者1971, John McCarthy, LISP語言語言, 程序語程序語義義, 程序理論程序理論1972, E. W. Dijkstra, Algol編譯編譯, 結構化結構化程序設計程序設計, 并發(fā)概念和原語并發(fā)概念和原語, 形式化推導形式化推導, 衛(wèi)式命令等衛(wèi)式命令等1977, John Backus, Fortran語言語言, FP語言語言, BNF等等1978, Robert

24、 Floyd, Algol編譯編譯, 編譯技術編譯技術, 程序優(yōu)化程序優(yōu)化, 歸納斷言法和前后斷言歸納斷言法和前后斷言, 程序程序正確性正確性, 編譯生成編譯生成1979, K. E. Iverson, APL語言語言1980, C.A.R. Hoare, 結構化程序設計結構化程序設計, case語句語句, 公理語義學公理語義學, 并發(fā)程序理論并發(fā)程序理論, CSP 等等1983, Dennis Ritchie 和和Thompson, C語語言和言和UNIX1984, Niklaus Wirth, Algol W, PL 360, Pascal, Modula-1/2, Oberon, 逐步求精逐步求精, 結構化程序設計結構化程序設計, 語法圖語法圖1991, Robin Milner, ML語言語言, 并發(fā)理論并發(fā)理論, CCS2001, Ole-Johan Dahl 和和Kristen Nygaard, Simula語言語言, OO概念概念2003, Alan