第01章 數(shù)據(jù)存儲

1、第1章 數(shù)據(jù)存儲,1.1 位和位存儲1.2 主存儲器1.3 海量存儲器1.4 用位模式表示信息1.5 二進制系統(tǒng)1.6 整數(shù)存儲1.7 小數(shù)的存儲1.8 數(shù)據(jù)壓縮1.9 通信差錯,1.1 位和位存儲,計算機中，信息是以0和1的模式編碼的。數(shù)字0和1稱為位（bit, binary digits）。,1.1.1 布爾運算,處理真假值的運算稱為布爾運算（Boolean operation）。位0代表假值位1代表真值布爾

2、運算類型：AND（與）OR（或）XOR（異或）NOT（非）,布爾運算,與AND：0*0=00*1=01*0=01*1=1,或OR：0+0=00+1=11+0=11+1=1,異或XOR：0⊕0=00⊕1=11⊕0=11⊕1=0,1.1.2 門和觸發(fā)器,門（gate）是一種設(shè)備，給出一種布爾運算輸入值時，可以得出該布爾運算的輸出值。觸發(fā)器（flip-flop）是可以產(chǎn)生0或1輸出值的電路，它的值會一直保持不

3、變，除非其它電路過來的臨時脈沖使其改變成另一個值，即輸出值是在外界的刺激下在兩個值之間相互轉(zhuǎn)換的。,門,觸發(fā)器1,觸發(fā)器2,1.1.3 十六進制記數(shù)法,十六進制記數(shù)法（hexadecimal notation）計算機位模式101101010011用簡寫符號來表示位，一個符號表示4位,十六進制編碼系統(tǒng),例：10110101 B51010010011001000 A4C8,練習(xí)題,1、什么樣的位模式輸入可以使得下面的電路輸出值

4、為1？,上面的兩個輸入中有且只有一個必須為1，且最下面的輸入必須為1。,練習(xí)題續(xù),2、二進制位模式0110101011110010用16進制計數(shù)法表示為 。3、十六進制5FD97用二進制位模式表示為 。,6AF2,,,01011111110110010111,1.2 主存儲器,存儲單元（cell）：主存儲器

5、的可管理單位。一個典型的存儲單元是一個字節(jié)（byte），即一個8位的串。最高有效位（most significant bit）：存儲單元行的左端稱為高位端（high-order end），高位端的最左一位稱為最高有效位或高位。最低有效位（least significant bit）：存儲單元行的右端稱為低位端（low-order end），低位端的最右一位稱為最低有效位或低位。,字節(jié)型存儲單元的結(jié)構(gòu),地址（address）,為了區(qū)分

6、主存儲器中的各存儲單元，每一個存儲單元都被賦予了一個唯一的名字，稱為地址。地址用數(shù)字表示；所有存儲單元看做是排成一行的；從0開始編號。,按地址排列的存儲單元,存儲器類型,隨機存儲器（RAM）：反映用任意順序存取存儲單元的能力；動態(tài)隨機存儲器（DRAM）：包含刷新電路，具有不穩(wěn)定性的存儲器。,存儲器容量的度量,Kilobyte: 210 bytes = 1024 bytes例: 3 KB = 3 × 1024 BMe

7、gabyte: 220 bytes = 1,048,576 bytes例: 3 MB = 3 × 1,048,576 BGigabyte: 230 bytes = 1,073,741,824 bytes例: 3 GB = 3 × 1,073,741,824 B,練習(xí)題,1、如果地址為5的存儲單元存有值8，那么將值5寫入6號存儲單元和將5號存儲單元的內(nèi)容移到6號存儲單元之間有什么差別？ 2

8、、擁有4KB的計算機存儲器里有多少個二進制位？ 4×1024×8＝32768,1.3 海量存儲器,海量存儲系統(tǒng)（mass storage）優(yōu)點：更穩(wěn)定、容量大、價格低、可拆卸缺點：需要機械運動，數(shù)據(jù)存取花費的時間長聯(lián)機（on-line）：設(shè)備或信息已經(jīng)與計算機相連接，不需要人的干預(yù)就可以使用；脫機（0ff-line）：必須有人的干預(yù)，設(shè)備和信息才可以被計算機使用。,1.3.1 磁學(xué)系統(tǒng),磁盤,磁帶,1

9、.3.2 光學(xué)系統(tǒng),光盤（compact disk, CD）DVD(digital versatile disk),1.3.3 閃存驅(qū)動器,基于磁學(xué)和光學(xué)的海量存儲系統(tǒng)，通過物理運動來存儲和讀取信息，數(shù)據(jù)存儲和讀取的速度比較慢。閃存（flash memory）：用電子信號將二進制位直接送到存儲介質(zhì)中，使得二氧化硅的微小晶格截獲電子，從而轉(zhuǎn)換微電子電路的性質(zhì)。,1.3.4 文件存儲及檢索,文件（file）：海量存儲系統(tǒng)中的信息單元。

10、邏輯記錄（logical record）字段（field）鍵字段（key field）－鍵（key）物理記錄（physical record）緩沖區(qū)（buffer）：一個設(shè)備向另一個設(shè)備傳輸?shù)倪^程中臨時存儲數(shù)據(jù)的區(qū)域。,1.4 用位模式表示信息,1.4.1 文本的表示文本形式的信息通常用一種代碼表示，文本中的每一個不同的符號均賦予其相應(yīng)的唯一的位模式。ASCII：7位（擴展8位）Unicode：16位ISO標(biāo)準(zhǔn)碼：32位

11、,報文“Hello”的ASCII碼,1.4.2 數(shù)值的表示,二進制計數(shù)法（binary notation）整數(shù)：二進制補碼小數(shù)：浮點數(shù),1.4.3 圖像的表示,位圖（bit map）技術(shù)像素（pixel）RGB亮度、色度圖像不能輕易調(diào)節(jié)到任意大小矢量（vector）技術(shù)將圖像表示為一組直線和曲線圖像可縮放,1.4.4 聲音的表示,采樣按有規(guī)律的時間間隔采樣聲波的振幅，并記錄所得到的數(shù)值序列，對音樂本身編碼。采樣頻率

12、（CD，44100次/秒）用于音樂錄制的高保真，需要大容量存儲MIDI（樂器數(shù)字化接口）編碼演奏者樂譜用于音樂合成或輔助音效,編碼的聲波,,數(shù)制：按進位原則進行計數(shù)，逢R進一。,基數(shù)：數(shù)制中所需的數(shù)字字符個數(shù)。R進制的基數(shù)=R,位權(quán)：是一個與數(shù)字位置有關(guān)的常數(shù)，位權(quán)=Rn其中n取值：以小數(shù)點為界，向左 0，1，2，3……，向右-1，-2，-3……例：(275.8)10=2×102＋7×101＋5

13、5;100＋8×10-1,1.5 二進制系統(tǒng),,位權(quán)相加法：各位數(shù)碼乘以位權(quán)，再相加。,例：(1011.1)2 = 1×23 + 0×22 + 1×21 + 1×20 + 1×2-1 = 8 + 0 + 2 + 1 + 0.5 = (11.5)10,二進制轉(zhuǎn)換為十進制,,,除2取余數(shù)直到商為0；由下而上排列。,結(jié)果為：1001011,乘2取整直到小數(shù)

14、部分為0或達到精度；由上而下排列。,0.6875 × 21 ………1.3750 × 2 0 ………0.7500 × 2 1 ………1.5000 × 2 1 ………1.0000,結(jié)果為：0.1011,(75.6875)10=(1001011.1011)2,十進制轉(zhuǎn)化為二進制,,加：0+0=00+1=11+0

15、=11+1=0,減：0-0=00-1=11-0=11-1=0,乘：0×0=00×1=01×0=01×1=1,除：0÷0=00÷1=01÷0(無意義)1÷1=1,例：11010＋1001＝100011；11010－1001＝10001 101×110＝11110；1111÷11＝101,二進制的算術(shù)運算,1

16、.6 整數(shù)存儲,二進制補碼記數(shù)法二進制余碼記數(shù)法（略）,符號位：二進制數(shù)的最高位表示“正”、“負(fù)”。0為正，1為負(fù)。機器數(shù)：正負(fù)符號被數(shù)值化了的數(shù)。真值：該機器數(shù)所表達的數(shù)值。,有符號數(shù),原碼：正號為0，負(fù)號為1，數(shù)值部分為二進制絕對值。補碼：正數(shù)的補碼和原碼相同；負(fù)數(shù)的補碼是將其原碼除符號位外各位取反，末位加1。,+5的原碼和補碼都是00000101,為了運算方便，計算機中機器數(shù)采用補碼表示。,原碼和補碼,“?！笔侵敢粋€系統(tǒng)

17、所能表示的數(shù)據(jù)個數(shù)。按模運算(mod)是指運算結(jié)果超過模時，模（或模的整數(shù)倍）將溢出而只剩下余數(shù)。,例：8位二進制的模為28=256。若某字節(jié)中已有數(shù)據(jù) 1111 1111，即255?，F(xiàn)在加上2，得到257，即二進制 10000 0001，此時已超過模(8位二進制)，則運算結(jié)果最高位的 1 將溢出，被自然丟失，該字節(jié)中只保留0000 0001（257 mod 256＝1）。,計算機的運算最終都轉(zhuǎn)換為加法，為了使符號位和數(shù)值位同時參與

18、運算，故采用補碼表示有符號整數(shù)。,溢出（overflow）,練習(xí)題,1、二進制101.111對應(yīng)的十進制數(shù)為 。2、十進制6.375對應(yīng)的二進制數(shù)為 。3、二進制111.11＋00.01＝ 。4、十進制數(shù)-17的二進制補碼為 。,,11101111,,110.011,,1000.00,,5.87

19、5,定點數(shù)與浮點數(shù),小數(shù)點位置固定的數(shù)稱為定點數(shù)。 定點整數(shù)：小數(shù)點固定在數(shù)值部分最右端。 定點小數(shù)：小數(shù)點固定在數(shù)值部分最左端。 小數(shù)點位置不固定的數(shù)稱為浮點數(shù)，分為階碼（指數(shù)）和尾數(shù)兩部分。,1.7 小數(shù)存儲,定點小數(shù)：（+0.5）,定點整數(shù)：（-3）,符號位,符號位,定點數(shù),例：將十進制數(shù) +55 以浮點數(shù)格式存放。 (55)10 = (110111)2 = 0.110111 * 26,浮點數(shù)：字長4字節(jié)，則階碼部分為

20、8位補碼定點整數(shù)，尾數(shù)部分為24位補碼定點小數(shù)。,浮點數(shù),截斷誤差（trancation error）,用浮點數(shù)表示存儲數(shù)值時，若尾數(shù)部分不夠用，則會丟失一些位。無窮展開式多個數(shù)值相加,1.8 數(shù)據(jù)壓縮,數(shù)據(jù)壓縮（data compression）：為了存儲和傳輸數(shù)據(jù)，在保留原有內(nèi)容的條件下，縮小所設(shè)計數(shù)據(jù)的大小。無損（lossless）壓縮：在壓縮過程中不丟失信息。有損（lossy）壓縮：在壓縮過程中會發(fā)生信息丟失。,18.1

21、 通用的數(shù)據(jù)壓縮技術(shù),行程長度編碼赫夫曼編碼相對編碼字典編碼,1、 行程長度編碼,行程長度編碼（run-length encoding）將一組相同的數(shù)據(jù)成分替換成一個代碼，指出重復(fù)的成分以及其在序列中出現(xiàn)的次數(shù)。無損,例：aaaabbbbbccccccthezz需要20B存放，壓縮后為 *a4*b5*c6thezz，只需14B,赫夫曼編碼（Huffman code）頻率相關(guān)編碼（frequency-dependent enc

22、oding），無損,香農(nóng)信息論：只要信源(即要壓縮的對象)不是等概率分布，就存在著數(shù)據(jù)壓縮的可能性。,Huffman 編碼就是利用變字長最佳編碼，實現(xiàn)信源符號按概率大小順序排列。Huffman 編碼是從樹葉到樹根生成二叉樹，樹葉是要編碼的字符，所以“一個字符的編碼不會是另一個字符編碼的前綴”。,2、赫夫曼編碼,例如：對于單詞 passages (8個字符長),0.25,0.625,0.375,1,s - 1 a - 01 p

23、- 001 g - 0000 e - 0001,1.計算信源符號出現(xiàn)的概率。p-0.125, a-0.25, s-0.375, g-0.125, e-0.1252.概率最小的兩個符號概率相加合成一個概率。3.將合成概率看成一個新組合符號概率，重復(fù)上述做法，直到最后只剩下兩個符號概率為止。4.反過來逐步向前編碼，每一步有兩個分支各賦予一個二進制碼，可以對概率大的編碼為1.,passages的原始ASCII碼有64位,001

24、011101000000011 壓縮后的代碼只有18位,相對編碼（relative encoding）記錄連續(xù)數(shù)據(jù)單元之間的區(qū)別，即每一個單元根據(jù)與前一個單元的關(guān)系編碼。適合于壓縮的數(shù)據(jù)流有很多單元組成，每一個單元與其前面的單元差別很小。有損，無損,3、 相對編碼,字典編碼（dictionary encoding）字典是指一組構(gòu)造塊，壓縮的信息通過它們建造起來，信息本身編碼成一系列字典的參照符。一般無損，有時有損。自

25、適應(yīng)字典編碼（adaptive dictionary encoding）編碼過程中字典是可以改變的LZW,4、 字典編碼,LZW例：xyx xyx xyx xyx,xyx xyx xyx xyx,,,,,,,,,,,,,2,1,3,1,4,3,4,3,4,最終編碼序列：121343434,1.8.2 圖像壓縮,GIF基于字典；有損壓縮；不適合需要高精確度的應(yīng)用。JPEG壓縮圖像的一種有效標(biāo)準(zhǔn)；有損，可提供無損；包含幾種圖像壓縮

26、方法。TIFF包含數(shù)據(jù)壓縮技術(shù)，但更常用為存儲照片的一個標(biāo)準(zhǔn)格式。,1.8.3 音頻和視頻壓縮,MPEG音頻及視頻編碼壓縮最常用的標(biāo)準(zhǔn)；MPEG包含許多不同應(yīng)用的許多標(biāo)準(zhǔn)；MP3壓縮音頻最著名的系統(tǒng)，是在MPEG標(biāo)準(zhǔn)中開發(fā)出來的；MP3利用人耳的特性，刪除人耳察覺不到的細節(jié)：暫時模糊頻率模糊,1.9 通信差錯,數(shù)據(jù)在傳輸和存取時可能發(fā)生差錯，因此需要人們開發(fā)了許多編碼技術(shù)來檢測甚至校正錯誤。奇偶校驗位糾錯編碼,能發(fā)

27、現(xiàn)編碼中一位出錯的情況，常用于內(nèi)存讀寫檢查、ASCII字符傳送檢查。原理：為一個字節(jié)補充1bit（校驗位），設(shè)置校驗位的值為0或1，使字節(jié)中的8bit和該校驗位含有1值的個數(shù)為奇數(shù)（奇校驗）或偶數(shù)（偶校驗）。如要向內(nèi)存寫1B時，先用專門電路形成校驗位的值，再將9bit數(shù)據(jù)寫入內(nèi)存；讀出時，用相應(yīng)電路檢測9bit代碼的合法性。只能發(fā)現(xiàn)1bit或多bit錯，但不能確定哪一bit錯，也不能發(fā)現(xiàn)偶數(shù)個bit錯。,1.9.1 奇偶校驗位,1