圖靈機模型及數據編碼.ppt

第1章 圖靈機模型及數據編碼,圖靈機模型理論是計算學科最核心的理論之一 圖靈機模型為計算機設計指明了方向 圖靈機模型是算法分析和程序語言設計的基礎理論。,本章主要內容,1.1 圖靈機 1.2 位的存儲 1.3 存儲器 1.4 數據在計算機中的表示 1.5 數據壓縮 1.6 數據傳輸誤碼及對策,圖靈機的直觀描述,3個部件：有窮控制器、無窮帶和讀寫頭 3個動作：改寫當前格、左移或右移一格,圖靈機的形式化描述,圖靈機是一個五元組（K，s，H），其中： K 是有窮個狀態(tài)的集合； 是字母表，即符號的集合； s K是初始狀態(tài)； HK 是停機狀態(tài)的集合，當控制器內部狀態(tài)為停機狀態(tài)時圖靈機結束計算； 是轉移函數，即控制器的規(guī)則集合。,計算“x+1”的圖靈機,目標：利用二進制來設計一個專門計算“x+1”的圖靈機，要求計算完成時，讀寫頭要回歸原位 狀態(tài)集合K：start，add，carry，noncarry，overflow，return，halt； 字母表：0，1，*； 初始狀態(tài)s：start； 停機狀態(tài)集合H：halt；,計算“x+1”的圖靈機,規(guī)則集合：,“51”的計算過程（1）,“51”的計算過程（2）,“51”的計算過程（3）,“51”的計算過程（4）,通用圖靈機（1）,編碼方案：,通用圖靈機（2）,通用圖靈機蘊含的計算思想,“x+1”圖靈機功能是固定的，相當于一個程序 通用的圖靈機功能根據輸入編碼的不同而變化 程序也是數據 存儲程序和程序控制 通用圖靈機模型是計算機的計算能力的極限 計算機系統(tǒng)應該有存儲器（相當于存儲帶）、中央處理器（控制器及其狀態(tài)），并且其字母表可以僅有0和1兩個符號；為了能將數據保存到存儲器并將計算結果從存儲器送出來展示給用戶，計算機系統(tǒng)還應該有輸入設備和輸出設備如鍵盤、鼠標、顯示器和打印機等。,1.2 位的存儲,如果用0-1作為編碼的基本元素的話，那么存儲的最小單位為1位（bit），要么是0要么是1?？梢娭灰鎯ρb置有兩種不同的穩(wěn)定狀態(tài)就能可以表示和存儲這兩個元素，其中一個狀態(tài)表示1，則另一種狀態(tài)就表示0,邏輯運算,門,可以設計出進行邏輯運算的裝置，比如用繼電器或者齒輪等，把這種能完成邏輯運算的裝置稱為門（Gate）?，F代電子計算機中的門是用電子線路實現的，其中1和0分別用電平的高和低來表示。,觸發(fā)器,其他存儲技術,磁芯 電容 磁介質 有機玻璃或聚酯樹酯等材料制作的介質,1.3 存儲器,1 Byte 8 Bit 1 KB（kilobyte） 1024 Byte 1 MB（megabyte） 1024 KB 1 GB（gigabyte） 1024 MB 1 TB（terabyte） 1024 GB,存儲器,主存儲器 地址 輔助存儲器 軟盤、硬盤和光盤等,1.4 數據在計算機中的表示,二進制 數值的表示 字符的表示 圖形和圖象的表示 音頻數據的表示,數制,進位計數的方法即數制 在采用進位計數的數字系統(tǒng)中，如果只用r個數碼，則稱其為基r數制（Radix-r Number System）或 r 進制，r 便稱為該數制的“基數”（Radix） 二進制：B（Binary），如 (11101)B； 八進制：O（Octal），如 (35)O； 十進制：D（Decimal），如 (29)D； 十六進制：H（Hexadecimal），如 (1D)H；,二進制與其他數制的轉換（1）,二進制與十進制的轉換 十進制轉換成二進制：將整數部分和小數部分分別轉換，然后再拼接起來 整數部分，采用除2取余法； 小數部分，采用乘2取整法。 二進制轉換為十進制：直接按權展開即可 小數點后的權分別為2的-1、-2、-3、次冪,二進制與其他數制的轉換（2）,十進制轉換成二進制：,二進制與其他數制的轉換（3）,二進制轉換為十進制：,二進制與其他數制的轉換（4）,二進制與十六進制的轉換 16124，4位二進制數剛好可以表示0F這16個數碼，也就是說二進制的4位數正好可以用1位十六進制數表示 將二進制數 10110101111011.011101 轉換為十六進制： (0010 1101 0111 1011.0111 0100)B(2 D 7 B.7 4)H 將十六進制數 2C1D.A1 轉換為二進制： (2 C 1 D. A 1)H(0010 1100 0001 1101.1010 0001)B 二進制與八進制的轉換類似,數值的表示（1）,機器數 把在機器內存放的正負號數碼化的數稱為機器數，把機器外部由正負表示的數稱為真值數 若一個數占8位，真值數（0101100）B的機器數為10101100,數值的表示（2）,整數和實數 整數,數值的表示（3）,整數和實數 實數,數值的表示（4）,若要考慮符號位的處理，則運算變得復雜:,為了解決此類問題，在機器數中，負數有三種表示法：原碼、反碼和補碼。,數值的表示（5）,原碼： 數符位以0表示正1表示負，數值部分就是絕對值的二進制表示，不便于加減運算 反碼： 對于正數與原碼相同；對于負數，數符位為1，其數值部分為絕對值取反 補碼： 對于正數與原碼相同；對于負數，數符位為1，其數值部分為絕對值取反最右加1，即為反碼加1 可方便地實現正負數的加法運算，符號位如同數值一樣參加運算，也允許產生最高位的進位,字符的表示（1）,西文字符 最常用的是ASCII字符編碼，即American Standard Code for Information Interchange (美國信息交換標準代碼)，用7位二進制編碼，它可以表示27 即128個字符 EBCDIC碼，即Extended Binary Coded Decimal Interchange Code（擴展的二-十進制交換碼），主要用在大型機器中，采用8位二進制編碼，有256個編碼狀態(tài)，但只選用其中一部分 存放和使用數據的軟件會以其他方式保存有關類型的信息，指明這個數據是何類型，不致引起混淆,字符的表示（2）,漢字編碼 用戶用輸入碼輸入漢字，輸入碼比較容易學習和記憶；系統(tǒng)由輸入碼找到相應的內碼，內碼是計算機內部對漢字的表示；要在顯示器上顯示或在打印機上打印出用戶所輸入的漢字，需要漢字的字形碼，系統(tǒng)由內碼找到相應的字形碼,字符的表示（3）,漢字編碼 漢字國標碼 全稱是GB231280信息交換用漢字編碼字符集基本集，1980年發(fā)布，是中文信息處理的國家標準，也稱漢字交換碼，簡稱GB碼。根據統(tǒng)計，把最常用的6763個漢字分成兩級：一級漢字有3755個，按漢語拼音排列；二級漢字有3008個，按偏旁部首排列。為了編碼，將漢字分成若干個區(qū)，每個區(qū)中94個漢字。由區(qū)號和位號（區(qū)中的位置）構成了區(qū)位碼。例如，“中”位于第54區(qū)48位，區(qū)位碼為5448。區(qū)號和位號各加32就構成了國標碼，這是為了與ASCII碼兼容，每個字節(jié)值大于32（032為非圖形字符碼值）。所以，“中”的國標碼為8650。,字符的表示（4）,漢字編碼 漢字機內碼 一個國標碼占兩個字節(jié)，每個字節(jié)最高位仍為“0”；英文字符的機內碼是7位ASCII碼，最高位也是“0”。因為西文字符和漢字都是字符，為了在計算機內部能夠區(qū)分是漢字編碼還是ASCII碼，將國標碼的每個字節(jié)的最高位由“0”變?yōu)椤?”，變換后的國標碼稱為漢字機內碼。由此可知漢字機內碼的每個字節(jié)都大于128，而每個西文字符的ASCII碼值均小于128。,字符的表示（5）,漢字編碼 漢字的輸入編碼 目的：進行漢字的輸入 要求：編碼要盡可能的短，重碼要盡量少，容易學容易上手 最常用的輸入碼：五筆字型、智能拼音等。,字符的表示（6）,漢字編碼 漢字字形碼 點陣方式 矢量方式,圖形和圖象的表示（1）,基本概念 圖形 一般是指通過繪圖軟件繪制的由直線、圓、圓弧、任意曲線等組成的畫面，即圖形是由計算機產生的，且以矢量形式存儲； 圖像 是由掃描儀、數字照相機、攝像機等輸入的畫面，即圖像是由真實的場景或現實存在的圖片輸入計算機產生的，圖像以位圖形式存儲。,圖形和圖象的表示（2）,基本概念 動畫 每一副畫面通過一些工具軟件對圖像素材進行編輯制作而成；動畫是用人工合成的方法對真實世界的一種模擬 視頻 對視頻信號源（如電視機、攝像機等）經過采樣和數字化后保存；而視頻影像則是對真實世界的記錄,圖形和圖象的表示（3）,一副圖像可認為是由若干行和若干列的像素（Pixels）點組成的陣列，每個像素點用若干個二進制進行編碼，表示圖像的顏色，這就是圖像的數字化。 圖像分辨率 顏色深度 即每一個像素點表示顏色的二進制位數,音頻數據的表示,采樣頻率 采樣頻率即每秒鐘的采樣次數。 采樣點精度 即存放每一個采樣點振幅值的二進制位數 聲道數,1.5 數據壓縮,在保留原數據表達的信息不變或者在稍有變動但不致于影響使用的同時盡量減少表達這些信息的數據量就是數據壓縮 數據壓縮有利于節(jié)省存儲空間，而且可有效提高數據傳輸效率 無損壓縮（熵編碼） 有損壓縮,無損壓縮（1）,行程編碼法(Run-length Encoding,RLE),0 0 0 0 0 0 0 0 1 1 1 1 1 1 7 7 77 7 1 1 11 1 1 （8個0） （6個1） （30個7） （50個1） 0 0 00 0 8 8 8 8 （30個0） （4個8） 可以編碼為： 8A0A6A1A30A7A50A1A30A0A4A8,無損壓縮（2）,霍夫曼編碼 （1）根據符號出現的概率大小按由小到大的次序排序； （2）把概率最小的兩個符號組成一個節(jié)點P1； （3）重復步驟（2），依次得到節(jié)點P2，P3，P4，構成了如圖1.17所示的一棵倒立的“樹”；其中，P4為樹根，稱為根節(jié)點；P1、P2、P3為樹枝，稱為枝節(jié)點；A、B、C、D和E為樹葉； （4）從根節(jié)點P4開始到對應于每個符號的樹葉，左分支標上“0”，右分支標上“1”； （5）從根節(jié)點P4開始順著樹枝到每個葉子分別寫出每個符號的代碼,無損壓縮（3）,霍夫曼編碼,無損壓縮（4）,LZW算法 LZW算法是一種詞典編碼法，其根據是待編碼的數據中總包含有重復代碼即詞 LZW算法先編制一個基本詞典，該詞典由待壓縮數據當中出現過的每個字符構成，然后，在不斷編碼的待壓縮數據的過程中不斷擴充，詞典中的每個詞都有一個編號即碼 數據經過LZW算法壓縮的結果是一系列的碼,無損壓縮（4）,LZW算法 假設待壓縮數據為：ABBABABAC,有損壓縮（1）,對聲音、圖像等多媒體信息來說，忽略一些微小的細節(jié)信息不會嚴重影響視聽質量。因此，可以通過有意丟棄一些對視聽效果相對不太重要的細節(jié)數據來壓縮數據，這類壓縮方法就稱為有損壓縮。 經有損壓縮的數據，進行數據重構，重構后的數據與原始數據有所不同，但不影響人對原始數據表達的信息的理解 JPEG：Joint Photographic Experts Group MPEG：Moving Picture Experts Group,有損壓縮（2）,JPEG：由國際標準化組織（ISO）和國際電工技術委員會（International Electrotechnical Commission）聯合組成的一個專家組，負責制訂靜態(tài)的數字圖像數據壓縮標準 以離散余弦變換（Discrete Cosine Transform，DCT）為基礎的有損壓縮算法， 采用以預測技術為基礎的無損壓縮算法 以離散小波變換（Discrete Wavelet Transform，DWT）為基礎的有損壓縮算法（JPEG2000）,有損壓縮（3）,MPEG：1988年由ISO和IEC成立的聯合專家組，負責開發(fā)電視圖像數據和聲音數據的編碼、解碼和它們的同步等標準 標準包括：MPEG視頻、MPEG音頻和MPEG系統(tǒng)三個部分的多個標準 方法：先利用動態(tài)預測及差分編碼方式去除相鄰兩張圖像的相關性，然后用一般量化或向量量化的方式舍去一些畫質而提高壓縮比，最后再經過一個可變長度的不失真型壓縮算法如霍夫曼編碼而得到最少位數的結果 可以得到50:1到100:1的壓縮比,1.6 數據傳輸誤碼及對策,兩種策略： 檢測傳輸錯誤，發(fā)現誤碼則重新傳輸或者發(fā)出錯誤警告，如奇偶校驗 檢測并糾正誤碼，如海明（糾錯）碼,奇偶校驗,以單字節(jié)編碼為例，可以在8位編碼的最左端增加1位，校驗位（Parity Bit） 奇校驗（Ood Parity） 校驗位總保持使整個9位序列里有奇數個1 偶校驗（Even Parity） 校驗位總使得編碼序列含有偶數個1,糾錯碼(Error-c