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

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

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

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

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

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

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

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

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

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

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

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

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

13、縮n數(shù)據(jù)壓縮有利于節(jié)省存儲(chǔ)空間，而且可有效提高數(shù)據(jù)傳輸效率n無(wú)損壓縮熵編碼）n有損壓縮無(wú)損壓縮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個(gè)個(gè)0） （6個(gè)個(gè)1） （30個(gè)個(gè)7） （50個(gè)個(gè)1） 0 0 00 0 8 8 8 8 （30個(gè)個(gè)0） （4個(gè)個(gè)8）可以編碼為：可以編碼為：8A0A6A1A30A7A50A1A30A0A4A8 無(wú)損壓縮2）n霍夫曼編碼n（1根據(jù)符號(hào)出現(xiàn)的概率大小按由小到大的次序排序；n（2把概率最小的兩個(gè)符號(hào)組成一個(gè)節(jié)點(diǎn)P1；n（3重復(fù)步驟2），依次得

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

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

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