Download presentation
Presentation is loading. Please wait.
1
Foundations of Computer Science Chapter 3 資料的儲存
計算機概論 第二版 Foundations of Computer Science Chapter 3 資料的儲存
2
3.1 資料型態 現今的資料有不同的形式,包含數值、文字、音訊、圖像和視訊(圖 3.1)。 人類需要能夠處理各種不同型態的資料:
3.1 資料型態 現今的資料有不同的形式,包含數值、文字、音訊、圖像和視訊(圖 3.1)。 人類需要能夠處理各種不同型態的資料: 工程應用程式利用電腦處理數值:包括作算術運算、解決代數或三角方程式、微分方程式的解等。 文書處理程式利用電腦處理文字:排版、移動、刪除等。 處理語音資料,播放音樂以及將聲音記錄成資料。 利用電腦處理圖像:包括建立、縮小、擴展、旋轉等。 播放電影,產生電影中所看到的特效。 電腦產業使用「多媒體」來定義包含數值、文字、圖像、音訊和視訊的資訊。 p.40
3
圖 3.1 不同型態的資料 p.40
4
當所有的資料型態儲存到電腦時,都被轉換成一致的表達方式,稱為位元樣式。
電腦內部的資料 當所有的資料型態儲存到電腦時,都被轉換成一致的表達方式,稱為位元樣式。 位元〔bit,二進位數字(binary digit)〕是電腦裡可被儲存的最小資料單元,而且其值為 0 或 1。 為了表示不同型態的資料,我們使用位元樣式(bit pattern),這是一連串位元,又稱為位元字串(a string of bits)。 一個具有 8 位元的位元樣式稱為一個位元組(byte)。字組(word)表示較長的位元樣式。 屬於不同資料型態的一筆資料可能在記憶體內儲存成相同的樣式。 p.40
5
圖 3.2 位元樣式 p.41
6
圖 3.3 不同資料型態的儲存 p.41
7
3.2 儲存數值 一個數值在儲存到電腦記憶體內部之前,會先被轉換成二進位系統。有兩個問題需要處理: 1. 如何儲存數值的符號。
3.2 儲存數值 一個數值在儲存到電腦記憶體內部之前,會先被轉換成二進位系統。有兩個問題需要處理: 1. 如何儲存數值的符號。 2. 如何表示小數點。 電腦使用兩種不同的表示法:定點法(fixed-point)和浮點法 (floating-point)。第一種表示法是將一個數值儲存成一個整 數,第二種則是將一個數值儲存成一個實數。 p.42
8
一個整數儲存在記憶體中通常是使用定點數表示法。
儲存整數 一個整數可以視為是一個小數點位置固定的數值:小數點在最低有效(最右邊)位元的右邊。 在定點數表示法(fixed-point representation)中假設有小數點但並不儲存。 一個整數儲存在記憶體中通常是使用定點數表示法。 p.42
9
圖 3.4 整數的定點數表示法 p.42
10
2. 如果位元數小於 n,則將 0 加到此二進位整數的左方,使得全部共有 n 位元。如果位元數大於 n,則此整數不能儲存,將會發生溢位情況。
無號整數(unsigned integer)的範圍介於 0 和正無窮大之間。其值為 (2n – 1),其中 n 表示一個無號數所配置的位元數目。 儲存一個無號整數: 1. 整數轉換成二進位。 2. 如果位元數小於 n,則將 0 加到此二進位整數的左方,使得全部共有 n 位元。如果位元數大於 n,則此整數不能儲存,將會發生溢位情況。 p.43
11
範例 3.1 儲存 7 到 8 位元的記憶體位置,使用無號數表示法。 解答
首先轉換整數成二進位 (111)2,加上五個 0 使全部為 8 個位元, ( )2。此整數儲存到記憶體位置中,注意下標 2 是用來強 調此整數是二進位,但是該下標並不儲存在電腦中。 轉換 7 成為二進位 在左邊加五個位元 p.43
12
範例 3.2 儲存 258 至 16 位元的記憶體位置。 解答 首先轉換整數成二進位,(100000010)2,加上七個 0 使全部為 16
個位元,( )2。此整數儲存到記憶體位置中。 轉換 258 成為二進位 在左邊加七個位元 p.43
13
範例 3.3 當一個輸出裝置取回儲存在記憶體中的位元字串 00101011 來當作 一個無號整數時,會傳回什麼? 解答
使用示於第 2 章中的程序,此二進位整數被轉換成無號整數 43。 p.44
14
溢位 在一個 n 位元的記憶體位置中,只能儲存一個介於 0 與 2n – 1 之間的無號整數。如果我們嘗試要儲存一個整數的值大於 24 – 1 = 15 到只有四個位元的記憶體位置中,這種情況稱為溢位(overflow)。 p.44
15
圖 3.5 無號整數中的溢位 p.44
16
無號整數表示法可以增進儲存的效率,因為我們不需要儲存整數的符號。無號整數表示法可以使用於當我們不需要負整數的時候:
無號整數的應用 無號整數表示法可以增進儲存的效率,因為我們不需要儲存整數的符號。無號整數表示法可以使用於當我們不需要負整數的時候: 計數(counting) 定址(addressing) 儲存其他資料型態 p.45
17
圖 3.6 符號大小表示法 p.45
18
符號大小表示法 以符號大小格式儲存整數需要 1 個位元來表示符號(0 表示正,1 表示負)。n 位元配置所能儲存數值範圍為 – (2n–1 – 1)到 +(2n–1 – 1)。在 n 位元的配置中,最左邊的位元專用於儲存符號(0 為正,1 為負)。 在符號大小表示法中,有兩個 0:+ 0 與 – 0。 p.45
19
範例 3.4 儲存 +28 至 8 位元的記憶體位置,使用符號大小表示法。 解答
將此整數轉換成 7 位元之二進位值,最左邊位元設為 0。儲存此 8 位元數值。 轉換 28 至 7 位元二進位值 加上符號並儲存 p.46
20
範例 3.5 儲存 –28 至 8 位元的記憶體位置,使用符號大小表示法。 解答
將此整數轉換成 7 位元之二進位值,最左邊位元設為 1。儲存此 8 位元數值。 轉換 28 至 7 位元二進位值 加上符號並儲存 p.46
21
範例 3.6 取回以符號大小表示法儲存成 01001101 的整數。 解答
因為最左邊位元為 0,符號為正。其餘位元 ( ) 轉換成十進 位為 77。加上符號之後,此整數為 +77。 p.46
22
範例 3.7 取回以符號大小表示法儲存成 10100001 的整數。 解答
因為最左邊位元為 1,符號為負。其餘位元 ( ) 轉換成十進 位為 17。加上符號之後,此整數為 –17。 p.46
23
圖 3.7 符號大小表示法之溢位 p.47
24
幾乎所有的電腦都使用 2 補數(two’s complement)表示法來儲存一個 n 位元記憶體位置中的有號整數。
2 補數表示法 幾乎所有的電腦都使用 2 補數(two’s complement)表示法來儲存一個 n 位元記憶體位置中的有號整數。 在 2 補數表示法中,最左邊位元定義了整數的符號。如果該位元為 0,則此整數為正;如果該位元為 1,則此整數為負。 圖 補數表示法 p.47
25
另一個取整數的 2 補數之方法是先取 1 補數,然後再將結果 加 1。
兩種運算 第一種稱為 1 補數(one’s completing)或取整數的 1 補數。此運算僅簡單地反相(反轉)每一個位元,0 位元改變成 1 位元,1 位元改變成 0 位元。 第二個運算稱為 2 補數或取二進位整數的 2 補數,此運算分 兩步驟完成。首先,從右邊開始複製位元直到第一個 1 為止, 然後反轉其餘的位元。 另一個取整數的 2 補數之方法是先取 1 補數,然後再將結果 加 1。 p.48
26
範例 3.8 底下顯示我們如何取整數 的 1 補數。 p.48
27
範例 3.9 底下顯示我們得到原始整數,如果我們應用 1 補數運算兩次。 p.48
28
範例 3.10 底下顯示我們如何取整數 的 2 補數。 p.49
29
範例 3.11 底下顯示我們永遠會得到原始整數,如果我們應用 2 補數運算兩 次。 p.49
30
以 2 補數表示法儲存整數,電腦遵循下列步驟: 整數轉換成 n 位元之二進位。
以 2 補數格式儲存整數 以 2 補數表示法儲存整數,電腦遵循下列步驟: 整數轉換成 n 位元之二進位。 如果此整數是正或零,則依照原樣式儲存;如果此整數是負,電腦取此整數的 2 補數然後再儲存。 取回 2 補數格式之整數 取回 2 補數格式之整數,電腦遵循下列步驟: 如果最左邊位元是 1,電腦對此整數執行 2 補數運算。如果是0,不執行任何運算。 電腦將此整數轉換成十進位。 p.49
31
範例 3.12 儲存整數 28 至 8 位元的記憶體位置,使用 2 補數表示法。 解答 此整數為正(無符號表示為正),所以在
十進位轉換成二進位之後無須另外的動作。注意五個額外的 0 被 加到此整數的左邊,使其成為八個位元。 p.50
32
範例 3.13 儲存整數 –28 至 8 位元的記憶體位置,使用 2 補數表示法。 解答
此整數為負,所以轉換成二進位之後,電腦對此整數執行 2 補數 運算。 p.50
33
範例 3.14 取回以 2 補數格式儲存成 00001101 的整數。 解答 因為最左邊位元為 0,所以此整數為正。此整數轉換成十進位並且
加上符號。 p.50
34
範例 3.15 取回以 2 補數格式儲存成 11100110 的整數。 解答 因為最左邊位元為 1,所以此整數為負。此整數轉換成十進位之前
需要取 2 補數。 p.50
35
圖 補數表示法之溢位 p.51
36
表 3.1 整數表示法之總結 p.52
37
實數(real)是一個具有整數部分和分數部分的數值。例如23.7 是一個實數──整數部分是 23,而分數部分是 7/10。
儲存實數 實數(real)是一個具有整數部分和分數部分的數值。例如23.7 是一個實數──整數部分是 23,而分數部分是 7/10。 具有很大的整數部分或很小的分數部分之實數不應該儲存成定點數表示法。 p.53
38
範例 3.16 在十進位系統中,假設我們使用定點數表示法,兩個數字在小數 點右邊和十四個數字在小數點左邊,總共有十六個數字。在這系
統中實數的精確度會不準,如果我們要表示一個十進位數字例如 ;這系統會將此數值存成 1.00。 p.53
39
範例 3.17 在十進位系統中,假設我們使用定點數表示法,六個數字在小數 點右邊和十個數字在小數點左邊,總共有十六個數字。在這系統
中實數的精確度會不準,如果我們要表示一個十進位數字例如 ,這系統會將此數值存成 ,整數部 分遠小於其應有的大小。 p.53
40
保持正確性或精確度的解決方法是使用浮點數表示法(floating-point representation)。
在浮點數表示法中,一個數值是由三個欄位所組成。第一個欄位是符號,不是正就是負。第二個欄位顯示小數點應該從實際數值往右或往左位移多少位置。第三個欄位是定點數表示法,其小數點位置是固定的。 定點數欄位只有一個數字在小數點左邊,而位移量是 10 的次方,稱為科學記號(scientific notation)。 一個數值的浮點數表示法是由三個部分所組成:符號、位移量和定點數。 p.53
41
圖 浮點數表示法之數值的三個部分 p.53
42
範例 3.18 底下顯示十進位數值 7,425,000,000,000,000,000,000.00 之科學記號 (浮點數表示法)。 解答
p.54
43
範例 3.19 以科學記號顯示數值 – 。 解答 我們使用上一範例中相同方法──移動小數點到數字 2 之後,如 下方所示: p.54
44
範例 3.20 以浮點數格式儲存數值 ( )2。 解答 我們使用相同的想法,保持只有一個數值在此小數點的左邊。 p.55
45
範例 3.21 以浮點數格式儲存數值 –( )2。 解答 我們使用相同的想法,保持只有一個非零數字在此小數點的左 邊。 p.55
46
正規化 為了使表示法的定點數部分一致,科學方法(十進位系統)和浮點數方法(二進位系統)使用在小數點左邊只有一個非零數字,這稱為正規化(normalization)。 p.55
47
一個二進位數值正規化之後,僅有此數值三個部分的資訊被儲存:符號、指數和尾數(小數點右邊的位元)。例如,+1000111.0101 變成:
注意小數點和定點數欄位左邊的位元 1 並沒有加以儲存,它們是隱含的。 p.55
48
指數(2 的次方)定義小數點的位移。超碼(Excess)表示法是用來儲存指數的方法。
符號 數值的符號可以使用 1 位元儲存(0 或 1)。 指數 指數(2 的次方)定義小數點的位移。超碼(Excess)表示法是用來儲存指數的方法。 尾數 尾數(mantissa)是指小數點右邊的二進位整數,它定義了數值的精確度。尾數是以定點數記法儲存。記住這並不是一個整數──而是儲存成類似整數的分數部分。 p.56
49
超碼系統 在超碼系統(Excess system)中,正整數和負整數都儲存成無號整數。要表示一個正或負整數,有一個正整數〔稱為偏移值(bias)〕要加到每一個數值以便將它們一律移動到非負數值的那一邊。這個偏移值為 2m – 1 – 1,其中 m 是儲存指數之記憶體的大小。 p.56
50
範例 3.22 我們可以用 4 位元配置的數值系統來表達 16 個整數。使用一個位
置表示 0 並且平分其餘 15 個(並非完全相等均分)可表達範圍 為 –7 到 8 的數值,如圖 3.11 所示。藉由加上 7 個單位到此範圍的 每一個整數,我們可以將所有的整數一律往右移動並且讓它們成 為正數,而不必改變這些整數彼此間相關的位置,如此圖所示。 這新系統稱為超 7(Excess-7)系統,或偏移值為 7 之偏移表示 法。 p.56
51
圖 超碼表示法之位移 p.57
52
電機電子工程師協會標準 電機電子工程師協會(Institute of Electrical and Electronics Engineers;IEEE)為浮點數定義了幾種標準。此處我們討論兩種最常用的標準,單精度和倍精度。 單精度格式使用 32 位元來儲存浮點表示法之實數。符號佔 1 個位元(0 為正 1 為負),指數佔 8 個位元(使用偏移值 127),尾數使用 23 個位元(無號數)。有時就是指超 127 (Excess_127),因為偏移值為127。 p.57
53
圖 IEEE 標準之浮點數表示法 p.57
54
倍精度格式使用總共 64 位元來儲存浮點表示法之實數。符號佔 1 個位元,指數佔 11 個位元(使用偏移值 1023),尾數使用 52 個位元。有時就是指超 1023(Excess_1023),因為偏移值為 1023。 表 3.2 兩種 IEEE 浮點數標準的規格 p.58
55
一個實數可以用 IEEE 標準浮點數格式之一來加以儲存,使用下列程序:
1. 儲存符號於 S(0 或 1)。 2. 改變數值成為二進位。 3. 正規化。 4. 找出 E 和 M 之值。 5. 連結 S、E 和 M。 p.58
56
範例 3.23 顯示十進位數值 5.75 之超 127(單精度)表示法。 解答 a. 符號為正,所以 S = 0。
b. 十進位至二進位之轉換:5.75 = (101.11)2。 c. 正規化:(101.11)2 = (1.011)2 × 22。 d. E = = 129 = ( )2,M = 0111。我們需要加 19 個零 在 M 的右邊使其成為 23 個位元。 e. 這表示顯示如下: 此數值儲存在電腦中為 。 p.58
57
範例 3.24 顯示十進位數值 –161.875 的超 127(單精度)表示法。 解答 a. 符號為負,所以 S = 1。
b. 十進位至二進位之轉換: = ( )2。 c. 正規化:( )2 = ( )2 × 27。 d. E = = 134 = ( )2,M = ( )2。 e. 表示: 此數值儲存在電腦中為 。 p.59
58
範例 3.25 顯示十進位數值 –0.0234375 的超 127(單精度)表示法。 解答 a. S = 1(此數值為負)。
b. 十進位至二進位之轉換: = ( )2。 c. 正規化:( )2 = (1.1)2 × 2–6。 d. E = – = 121 = ( )2,M = (1)2。 e. 表示: 此數值儲存在電腦中為 。 p.59
59
以 IEEE 標準浮點數格式之一所儲存之數值,可以使用下列方法取回:
1. 找出 S、E 和 M 之值。 2. 如果 S = 0,符號設為正,否則,符號設為負。 3. 找出為位移值(E–127)。 4. 反正規化尾數。 5. 改變反正規化後之數值成為二進位以便找出絕對值。 6. 加上符號。 p.59
60
範例 3.26 位元樣式 ( )2 以超 127 格式存 在記憶體中。顯示此數值之十進位記法。 解答 a. 第一個位元表示 S,之後 8 個位元為 E,其餘 23 個位元為 M。 b. 符號為負。 c. 位移量 = E – 127 = 148 – 127 = 21。 d. 反正規化得到( )2 × 221。 e. 二進位數值為( )2。 f. 絕對值為 2,104,378.75。 g. 此數值為 –2,104,378.75。 p.60
61
一個實數之整數部分和分數部分設為零,亦即 0.0,不能使用上面所討論的步驟來加以儲存。在此情況下將符號、指數和尾數都設為 0。
在浮點數的情況中,會有溢位和下限溢位(underflow)。圖3.13 顯示了使用 32 位元記憶體位置(超 127)浮點表示法的範圍。此表示法不能儲存具有非常小或非常大的絕對值之數值。 一個實數之整數部分和分數部分設為零,亦即 0.0,不能使用上面所討論的步驟來加以儲存。在此情況下將符號、指數和尾數都設為 0。 在原來的數值與取回的數值之間的差稱為捨棄誤差(truncation error)。這種誤差的類型在使用到非常大或非常小的數值之領域中是很重要的,例如太空工業中的計算。 p.60
62
圖 實數的浮點數表示法之溢位與下限溢位 p.60
63
3.3 儲存文字 文字(text)用一個位元樣式來表達每一個符號。
3.3 儲存文字 文字(text)用一個位元樣式來表達每一個符號。 在一個位元樣式裡需要用多少個位元來表示一種語言中的一 個符號?這取決於此語言所使用的符號集合裡的數量。 符號的位元樣式長度取決於符號的數量;但兩者之間不是線 性關係:而是對數關係。如果需要四個符號,長度為兩個位 元(log24 = 2)。 p.61
64
圖 使用位元樣式表示符號 p.61
65
表 3.3 符號數量與位元樣式長度 p.62
66
不同的位元樣式組合,可用來表達文字符號。每一個集合稱為一種編碼法(code),而表達符號的過程稱為編碼。 ASCII
美國國家標準局(American National Standards Institute;ANSI)發展了一套編碼法稱為美國資訊交換標準碼(American Standard Code for Information Interchange;ASCII),每個符號使用了 7 個位元,表示在這個編碼法中可以定義出 27 = 128 個不同的符號。 萬國碼 一個硬體和軟體廠商所組成的聯盟已經設計了一套編碼法稱為萬國碼(Unicode),它使用 32 位元,因此可表示多達 232 = 4,294,967,296 個符號。編碼中不同的區段分別配置給世界上不同語言中的符號來使用,某些部分的萬國碼則用來表示繪圖和特殊符號。 p.62
67
3.4 儲存音訊 音訊(audio)是一種聲音和音樂的表達方式。音訊是不可計數的。音訊是隨時間改變的實體──只能測量每個時刻的聲音強度。要儲存音訊到電腦記憶體時,意指儲存一段時間:一秒或一小時音訊訊號的強度。 音訊是一種類比(analog)資料,無法儲存所有的值到電腦記 憶體。 取樣(sampling)是指只選擇類比訊號上的有限數量的點,測 量這些點的值,並記錄這些值。 p.63
68
圖 音訊訊號 p.63
69
圖 音訊訊號的取樣 p.63
70
在每一秒鐘之內需要多少樣本才能取得原始訊號的複本?樣本的數量取決於類比訊號中變換的最大數量。現已證實每秒40,000 個樣本的取樣頻率(sampling rate)足以複製音訊訊號。
量化(quantization)是指將樣本值取四捨五入至最接近的整數值之過程。例如,如果實數值是 17.2,四捨五入後降為17;如果實數值是 17.7,四捨五入後增為 18。 p.64
71
量化的樣本值需要被編碼(encoding)為位元樣式。 每個樣本之位元數有時稱為位元深度(bit depth)。
如果位元深度或每一樣本之位元數為 B,每秒鐘之樣本數為S,則每一秒的音訊需要儲存 S × B 個位元數。這項乘積有時稱為位元率(bit rate)R。例如,如果我們使用每秒 40,000 個樣本和每一樣本 16 個位元,則位元率 R = 40,000 × 16 = 640,000 位元/秒 = 640 K 位元/秒。 p.64
72
在今日,儲存聲音的主要標準為 MP3(MPEG 第 3 層之簡稱)。它使用每秒 44,100 個樣本和每一樣本 16 個位元。結果是訊號的位元率為每秒 705,600 個位元,它是使用捨棄無法被人類耳朵所察覺的資訊之壓縮方法來加以壓縮,稱為失真的壓縮。 p.64
73
3.5 儲存圖像 圖像儲存在電腦中使用了兩種不同的技術:點掃繪圖法和向量繪圖法。 點掃繪圖法
3.5 儲存圖像 圖像儲存在電腦中使用了兩種不同的技術:點掃繪圖法和向量繪圖法。 點掃繪圖法 點掃繪圖法(raster graphics)〔或位元映像繪圖法(bitmap graphics)〕使用於需要儲存類比圖像時,例如相片。相片是由類似音訊資料的類比資料所組成:這表示資料必須加以取樣,然而,取樣在這情況中通常稱為掃瞄(scanning)。所掃瞄的樣本稱為像素(pixel)。 在圖像處理中的掃瞄率稱為解析度(resolution)。 p.65
74
一個像素所使用的位元數量,也就是其色彩深度(color depth),取決於像素色彩是如何用不同編碼技術加以處理的。
用來編碼像素的技術其中一種稱為全彩(True-Color),它使用 24 個位元來編碼一個像素。在此技術中,三原色(RGB)中的每一種顏色是用 8 個位元來表示。每一個色彩可以用三個介於 0 到 255 之間的十進位數值來表達。 注意全彩結構可以編碼 224 或 16,776,216 種色彩,換言之,每個像素的色彩強度是這些數值其中之一。 p.65
75
表 3.4 全彩中的一些色彩 p.65
76
索引的使用減少了儲存一個像素所需要的位元數,索引顏色結構通常使用 256 個索引值,只需要 8 個位元來儲存同一個像素。
索引顏色(indexed color)〔或調色盤顏色(palette color)〕結構只使用這些顏色的一部分,在這結構中每一個應用程式從顏色的最大集合中挑選一些(通常為 256)顏色並建立索引,設定一個介於 0 到 255 之間的值給每一個所挑選的顏色。 索引的使用減少了儲存一個像素所需要的位元數,索引顏色結構通常使用 256 個索引值,只需要 8 個位元來儲存同一個像素。 有幾種實際的圖像編碼標準在使用中。JPEG〔靜態影像壓縮標準(joint photographic experts group)〕使用全彩結構,但利用壓縮圖像來減少位元數。GIF〔圖形交換格式(graphic interchange format)〕使用索引顏色結構。 p.66
77
圖 索引顏色結構對全彩結構的關係 p.66
78
向量圖形法又稱為幾何模型(geometric modeling)或物件導向繪圖法(object-oriented graphics)。
向量繪圖法 點掃繪圖法有兩個缺點:檔案太大與調整大小困難。當圖像放大時看起來有鋸齒狀。向量繪圖(vector graphic)之圖像編碼方法並不是儲存每個像素的位元樣式。一張圖像被分解成幾何形狀的組合,例如直線、正方形或圓,每一個幾何形狀用一個數學方程式來代表。一張向量繪圖法之圖像是由一連串定義這些形狀應該如何繪製的指令所構成。 向量圖形法又稱為幾何模型(geometric modeling)或物件導向繪圖法(object-oriented graphics)。 向量繪圖法不適合用來儲存攝影圖像的微妙之處,JPEG 或GIF 點掃圖形可以提供更好且更生動的圖片。向量繪圖法適用於主要是使用幾何元素來產生圖像的應用 p.66
79
3.6 儲存視訊 視訊(video)是一種即時圖像(稱為畫面)的表達方式。視訊是空間變化(單一圖像)與時間變化(一連串圖像)的資訊之表達。
3.6 儲存視訊 視訊(video)是一種即時圖像(稱為畫面)的表達方式。視訊是空間變化(單一圖像)與時間變化(一連串圖像)的資訊之表達。 每一張圖像或畫面被轉換成一個位元樣式的集合並且加以儲存,這些圖像的組合可用來表達視訊。現今的視訊通常是經過壓縮的,動態影像壓縮標準(MPEG),這是一種常見的視訊壓縮技術。 p.67
Similar presentations