第1章圖靈機模型及數(shù)據(jù)編碼ppt課件

1、第1章 圖靈機模型及數(shù)據(jù)編碼n圖靈機模型理論是計算學(xué)科最核心的理論之一n圖靈機模型為計算機設(shè)計指明了方向n圖靈機模型是算法分析和程序語言設(shè)計的基礎(chǔ)理論。本章主要內(nèi)容n1.1 圖靈機n1.2 位的存儲n1.3 存儲器n1.4 數(shù)據(jù)在計算機中的表示n1.5 數(shù)據(jù)壓縮n1.6 數(shù)據(jù)傳輸誤碼及對策圖靈機的直觀描述n3個部件：有窮控制器、無窮帶和讀寫頭n3個動作：改寫當(dāng)前格、左移或右移一格讀寫頭讀寫頭有窮控制器有窮控制器存儲帶存儲帶 圖靈機模型圖靈機模型圖靈機的形式化描述n圖靈機是一個五元組K，s，H），其中：nK 是有窮個狀態(tài)的集合；n 是字母表，即符號的集合；ns K是初始狀態(tài)；nHK 是停機狀態(tài)的

2、集合，當(dāng)控制器內(nèi)部狀態(tài)為停機狀態(tài)時圖靈機結(jié)束計算；n是轉(zhuǎn)移函數(shù)，即控制器的規(guī)則集合。計算“x+1的圖靈機n目的：利用二進制來設(shè)計一個專門計算“x+1的圖靈機，要求計算完成時，讀寫頭要回歸原位 n狀態(tài)集合K：start，add，carry，noncarry，overflow，return，halt；n字母表：0，1，*；n初始狀態(tài)s：start；n停機狀態(tài)集合H：halt；計算“x+1的圖靈機n規(guī)則集合：“51的計算過程1）“51的計算過程2）“51的計算過程3）“51的計算過程4）通用圖靈機1）編碼方案：通用圖靈機2）通用圖靈機蘊含的計算思想n“x+1圖靈機功能是固定的，相當(dāng)于一個程序 n通用

3、的圖靈機功能根據(jù)輸入編碼的不同而變化n程序也是數(shù)據(jù)n存儲程序和程序控制n通用圖靈機模型是計算機的計算能力的極限 n計算機系統(tǒng)應(yīng)該有存儲器相當(dāng)于存儲帶）、中央處理器控制器及其狀態(tài)），并且其字母表可以僅有0和1兩個符號；為了能將數(shù)據(jù)保存到存儲器并將計算結(jié)果從存儲器送出來展示給用戶，計算機系統(tǒng)還應(yīng)該有輸入設(shè)備和輸出設(shè)備如鍵盤、鼠標(biāo)、顯示器和打印機等。 1.2 位的存儲n如果用0-1作為編碼的基本元素的話，那么存儲的最小單位為1位bit），要么是0要么是1。可見只要存儲裝置有兩種不同的穩(wěn)定狀態(tài)就能可以表示和存儲這兩個元素，其中一個狀態(tài)表示1，則另一種狀態(tài)就表示0邏輯運算門n可以設(shè)計出進行邏輯運算的裝置

4、，比如用繼電器或者齒輪等，把這種能完成邏輯運算的裝置稱為門Gate）?，F(xiàn)代電子計算機中的門是用電子線路實現(xiàn)的，其中1和0分別用電平的高和低來表示。觸發(fā)器其他存儲技術(shù)n磁芯n電容 n磁介質(zhì)n有機玻璃或聚酯樹酯等材料制作的介質(zhì) 1.3 存儲器n1 Byte 8 Bitn1 KBkilobyte） 1024 Byten1 MBmegabyte） 1024 KBn1 GBgigabyte） 1024 MBn1 TBterabyte） 1024 GB存儲器n主存儲器n地址n輔助存儲器n軟盤、硬盤和光盤等1.4 數(shù)據(jù)在計算機中的表示n二進制n數(shù)值的表示 n字符的表示 n 圖形和圖象的表示 n音頻數(shù)據(jù)的表示

5、 數(shù)制n進位計數(shù)的方法即數(shù)制n在采用進位計數(shù)的數(shù)字系統(tǒng)中，如果只用r個數(shù)碼，則稱其為基r數(shù)制Radix-r Number System或 r 進制，r 便稱為該數(shù)制的“基數(shù)”（Radix） n二進制：BBinary），如 (11101)B；n八進制：OOctal），如 (35)O；n十進制：DDecimal），如 (29)D；n十六進制：HHexadecimal），如 (1D)H；二進制與其他數(shù)制的轉(zhuǎn)換1）n二進制與十進制的轉(zhuǎn)換n十進制轉(zhuǎn)換成二進制：將整數(shù)部分和小數(shù)部分分別轉(zhuǎn)換，然后再拼接起來n整數(shù)部分，采用除2取余法；n小數(shù)部分，采用乘2取整法。n二進制轉(zhuǎn)換為十進制：直接按權(quán)展開即可n小數(shù)點

6、后的權(quán)分別為2的-1、-2、-3、次冪 二進制與其他數(shù)制的轉(zhuǎn)換2）n十進制轉(zhuǎn)換成二進制：二進制與其他數(shù)制的轉(zhuǎn)換3）n二進制轉(zhuǎn)換為十進制：二進制與其他數(shù)制的轉(zhuǎn)換4）n二進制與十六進制的轉(zhuǎn)換n16124，4位二進制數(shù)剛好可以表示0F這16個數(shù)碼，也就是說二進制的4位數(shù)正好可以用1位十六進制數(shù)表示 n將二進制數(shù) 10110101111011.011101 轉(zhuǎn)換為十六進制：n(0010 1101 0111 1011.0111 0100)B(2 D 7 B.7 4)Hn將十六進制數(shù) 2C1D.A1 轉(zhuǎn)換為二進制：n(2 C 1 D. A 1)H(0010 1100 0001 1101.1010 0001

7、)B n二進制與八進制的轉(zhuǎn)換類似數(shù)值的表示1）n機器數(shù)n把在機器內(nèi)存放的正負(fù)號數(shù)碼化的數(shù)稱為機器數(shù)，把機器外部由正負(fù)表示的數(shù)稱為真值數(shù)n若一個數(shù)占8位，真值數(shù)（0101100B的機器數(shù)為10101100 數(shù)值的表示2）n整數(shù)和實數(shù)n整數(shù)數(shù)值的表示3）n整數(shù)和實數(shù)n實數(shù)pdN2數(shù)值的表示4）n若要考慮符號位的處理，則運算變得復(fù)雜:n為了解決此類問題，在機器數(shù)中，負(fù)數(shù)有三種表示法：原碼、反碼和補碼。數(shù)值的表示5）n原碼：n數(shù)符位以0表示正1表示負(fù)，數(shù)值部分就是絕對值的二進制表示，不便于加減運算n反碼：n對于正數(shù)與原碼相同；對于負(fù)數(shù)，數(shù)符位為1，其數(shù)值部分為絕對值取反n補碼：n對于正數(shù)與原碼相同；對

8、于負(fù)數(shù)，數(shù)符位為1，其數(shù)值部分為絕對值取反最右加1，即為反碼加1n可方便地實現(xiàn)正負(fù)數(shù)的加法運算，符號位如同數(shù)值一樣參加運算，也允許產(chǎn)生最高位的進位字符的表示1）n西文字符n最常用的是ASCII字符編碼，即American Standard Code for Information Interchange (美國信息交換標(biāo)準(zhǔn)代碼)，用7位二進制編碼，它可以表示27 即128個字符nEBCDIC碼，即Extended Binary Coded Decimal Interchange Code擴展的二-十進制交換碼），主要用在大型機器中，采用8位二進制編碼，有256個編碼狀態(tài)，但只選用其中一部分n存

9、放和使用數(shù)據(jù)的軟件會以其他方式保存有關(guān)類型的信息，指明這個數(shù)據(jù)是何類型，不致引起混淆字符的表示2）n漢字編碼n用戶用輸入碼輸入漢字，輸入碼比較容易學(xué)習(xí)和記憶；系統(tǒng)由輸入碼找到相應(yīng)的內(nèi)碼，內(nèi)碼是計算機內(nèi)部對漢字的表示；要在顯示器上顯示或在打印機上打印出用戶所輸入的漢字，需要漢字的字形碼，系統(tǒng)由內(nèi)碼找到相應(yīng)的字形碼字符的表示3）n漢字編碼n漢字國標(biāo)碼n全稱是GB231280信息交換用漢字編碼字符集基本集，1980年發(fā)布，是中文信息處理的國家標(biāo)準(zhǔn)，也稱漢字交換碼，簡稱GB碼。根據(jù)統(tǒng)計，把最常用的6763個漢字分成兩級：一級漢字有3755個，按漢語拼音排列；二級漢字有3008個，按偏旁部首排列。為了編

10、碼，將漢字分成若干個區(qū)，每個區(qū)中94個漢字。由區(qū)號和位號區(qū)中的位置構(gòu)成了區(qū)位碼。例如，“中位于第54區(qū)48位，區(qū)位碼為5448。區(qū)號和位號各加32就構(gòu)成了國標(biāo)碼，這是為了與ASCII碼兼容，每個字節(jié)值大于32032為非圖形字符碼值）。所以，“中的國標(biāo)碼為8650。字符的表示4）n漢字編碼n漢字機內(nèi)碼n一個國標(biāo)碼占兩個字節(jié)，每個字節(jié)最高位仍為“0”；英文字符的機內(nèi)碼是7位ASCII碼，最高位也是“0”。因為西文字符和漢字都是字符，為了在計算機內(nèi)部能夠區(qū)分是漢字編碼還是ASCII碼，將國標(biāo)碼的每個字節(jié)的最高位由“0變?yōu)椤?”，變換后的國標(biāo)碼稱為漢字機內(nèi)碼。由此可知漢字機內(nèi)碼的每個字節(jié)都大于128，

11、而每個西文字符的ASCII碼值均小于128。字符的表示5）n漢字編碼n漢字的輸入編碼n目的：進行漢字的輸入n要求：編碼要盡可能的短，重碼要盡量少，容易學(xué)容易上手n最常用的輸入碼：五筆字型、智能拼音等。字符的表示6）n漢字編碼n漢字字形碼n點陣方式n矢量方式 圖形和圖象的表示1）n基本概念n圖形n一般是指通過繪圖軟件繪制的由直線、圓、圓弧、任意曲線等組成的畫面，即圖形是由計算機產(chǎn)生的，且以矢量形式存儲；n圖像n是由掃描儀、數(shù)字照相機、攝像機等輸入的畫面，即圖像是由真實的場景或現(xiàn)實存在的圖片輸入計算機產(chǎn)生的，圖像以位圖形式存儲。圖形和圖象的表示2）n基本概念n動畫n每一副畫面通過一些工具軟件對圖像

12、素材進行編輯制作而成；動畫是用人工合成的方法對真實世界的一種模擬n視頻n對視頻信號源如電視機、攝像機等經(jīng)過采樣和數(shù)字化后保存；而視頻影像則是對真實世界的記錄圖形和圖象的表示3）n一副圖像可認(rèn)為是由若干行和若干列的像素Pixels點組成的陣列，每個像素點用若干個二進制進行編碼，表示圖像的顏色，這就是圖像的數(shù)字化。n圖像分辨率n顏色深度n即每一個像素點表示顏色的二進制位數(shù)音頻數(shù)據(jù)的表示n采樣頻率n采樣頻率即每秒鐘的采樣次數(shù)。n采樣點精度n即存放每一個采樣點振幅值的二進制位數(shù)n聲道數(shù)1.5 數(shù)據(jù)壓縮n在保留原數(shù)據(jù)表達的信息不變或者在稍有變動但不致于影響使用的同時盡量減少表達這些信息的數(shù)據(jù)量就是數(shù)據(jù)壓

13、縮n數(shù)據(jù)壓縮有利于節(jié)省存儲空間，而且可有效提高數(shù)據(jù)傳輸效率n無損壓縮熵編碼）n有損壓縮無損壓縮1）n行程編碼法(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）n霍夫曼編碼n（1根據(jù)符號出現(xiàn)的概率大小按由小到大的次序排序；n（2把概率最小的兩個符號組成一個節(jié)點P1；n（3重復(fù)步驟2），依次得

14、到節(jié)點P2，P3，P4，構(gòu)成了如圖1.17所示的一棵倒立的“樹”；其中，P4為樹根，稱為根節(jié)點；P1、P2、P3為樹枝，稱為枝節(jié)點；A、B、C、D和E為樹葉；n（4從根節(jié)點P4開始到對應(yīng)于每個符號的樹葉，左分支標(biāo)上“0”，右分支標(biāo)上“1”；n（5從根節(jié)點P4開始順著樹枝到每個葉子分別寫出每個符號的代碼無損壓縮3）n霍夫曼編碼無損壓縮4）nLZW算法nLZW算法是一種詞典編碼法，其根據(jù)是待編碼的數(shù)據(jù)中總包含有重復(fù)代碼即詞nLZW算法先編制一個基本詞典，該詞典由待壓縮數(shù)據(jù)當(dāng)中出現(xiàn)過的每個字符構(gòu)成，然后，在不斷編碼的待壓縮數(shù)據(jù)的過程中不斷擴充，詞典中的每個詞都有一個編號即碼n數(shù)據(jù)經(jīng)過LZW算法壓縮的

15、結(jié)果是一系列的碼無損壓縮4）nLZW算法n假設(shè)待壓縮數(shù)據(jù)為：ABBABABAC有損壓縮1）n對聲音、圖像等多媒體信息來說，忽略一些微小的細(xì)節(jié)信息不會嚴(yán)重影響視聽質(zhì)量。因而，可以通過有意丟棄一些對視聽效果相對不太重要的細(xì)節(jié)數(shù)據(jù)來壓縮數(shù)據(jù)，這類壓縮方法就稱為有損壓縮。n經(jīng)有損壓縮的數(shù)據(jù)，進行數(shù)據(jù)重構(gòu)，重構(gòu)后的數(shù)據(jù)與原始數(shù)據(jù)有所不同，但不影響人對原始數(shù)據(jù)表達的信息的理解nJPEG：Joint Photographic Experts GroupnMPEG：Moving Picture Experts Group有損壓縮2）nJPEG：由國際標(biāo)準(zhǔn)化組織ISO和國際電工技術(shù)委員會Internationa

16、l Electrotechnical Commission聯(lián)合組成的一個專家組，負(fù)責(zé)制訂靜態(tài)的數(shù)字圖像數(shù)據(jù)壓縮標(biāo)準(zhǔn)n以離散余弦變換Discrete Cosine Transform，DCT為基礎(chǔ)的有損壓縮算法，n采用以預(yù)測技術(shù)為基礎(chǔ)的無損壓縮算法n以離散小波變換Discrete Wavelet Transform，DWT為基礎(chǔ)的有損壓縮算法JPEG2000）有損壓縮3）nMPEG：1988年由ISO和IEC成立的聯(lián)合專家組，負(fù)責(zé)開發(fā)電視圖像數(shù)據(jù)和聲音數(shù)據(jù)的編碼、解碼和它們的同步等標(biāo)準(zhǔn)n標(biāo)準(zhǔn)包括：MPEG視頻、MPEG音頻和MPEG系統(tǒng)三個部分的多個標(biāo)準(zhǔn)n方法：先利用動態(tài)預(yù)測及差分編碼方式去除相鄰兩張圖像的相關(guān)性，然后用一般量化或向量量化的方式舍去一些畫質(zhì)而提高壓縮比，最后再經(jīng)過一個可變長度的不失真型壓縮算法如霍夫曼編碼而得到最少位數(shù)的結(jié)果n可以得到50:1到100:1的壓縮比1.6 數(shù)據(jù)傳輸誤碼及對策n兩種策略：n檢測傳輸錯誤，發(fā)現(xiàn)誤碼則重新傳輸或者發(fā)出錯誤警告，如奇偶校驗n檢測并糾正誤碼，如海明糾錯碼奇偶校驗n以單字節(jié)編碼為例，可以在8位編碼的最左端增加1位，校驗位Parity Bit）n奇校驗Ood Parity）n校驗位總保持使整個9位序列里有奇數(shù)個1n偶校驗Even Parity）n校驗位總使得編碼序列含有偶數(shù)個1糾錯碼(Error