圖靈機(jī)模型及數(shù)據(jù)編碼.pptVIP

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