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

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

2、運(yùn)算類型：AND（與）OR（或）XOR（異或）NOT（非）,布爾運(yùn)算,與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è)備，給出一種布爾運(yùn)算輸入值時(shí)，可以得出該布爾運(yùn)算的輸出值。觸發(fā)器（flip-flop）是可以產(chǎn)生0或1輸出值的電路，它的值會(huì)一直保持不

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

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

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

6、主存儲(chǔ)器中的各存儲(chǔ)單元，每一個(gè)存儲(chǔ)單元都被賦予了一個(gè)唯一的名字，稱為地址。地址用數(shù)字表示；所有存儲(chǔ)單元看做是排成一行的；從0開始編號(hào)。,按地址排列的存儲(chǔ)單元,存儲(chǔ)器類型,隨機(jī)存儲(chǔ)器（RAM）：反映用任意順序存取存儲(chǔ)單元的能力；動(dòng)態(tài)隨機(jī)存儲(chǔ)器（DRAM）：包含刷新電路，具有不穩(wěn)定性的存儲(chǔ)器。,存儲(chǔ)器容量的度量,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的存儲(chǔ)單元存有值8，那么將值5寫入6號(hào)存儲(chǔ)單元和將5號(hào)存儲(chǔ)單元的內(nèi)容移到6號(hào)存儲(chǔ)單元之間有什么差別？ 2

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

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

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

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

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

13、5;100＋8×10-1,1.5 二進(jìn)制系統(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,二進(jìn)制轉(zhuǎn)換為十進(jìn)制,,,除2取余數(shù)直到商為0；由下而上排列。,結(jié)果為：1001011,乘2取整直到小數(shù)

14、部分為0或達(dá)到精度；由上而下排列。,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,十進(jìn)制轉(zhuǎn)化為二進(jì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,二進(jìn)制的算術(shù)運(yùn)算,1

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

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

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

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

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

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

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

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

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

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ù)，但更常用為存儲(chǔ)照片的一個(gè)標(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利用人耳的特性，刪除人耳察覺不到的細(xì)節(jié)：暫時(shí)模糊頻率模糊,1.9 通信差錯(cuò),數(shù)據(jù)在傳輸和存取時(shí)可能發(fā)生差錯(cuò)，因此需要人們開發(fā)了許多編碼技術(shù)來檢測(cè)甚至校正錯(cuò)誤。奇偶校驗(yàn)位糾錯(cuò)編碼,能發(fā)

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