新世代計算機概論 第2章　數字系統與資料表示法.

Presentation on theme: "新世代計算機概論 第2章　數字系統與資料表示法."— Presentation transcript:

1 新世代計算機概論 第2章　數字系統與資料表示法

2 2-1 電腦的基本單位 0與1是電腦的基本單位。 我們將0或1稱為一個位元 (bit)，而這種只有「關」或「開」兩種狀態的系統稱為二進位系統 (binary system) 。

3 單位 位元數目 簡寫 位元(bit) 1位元 b 位元組 (byte) 8位元 B 字組 (word) 16位元 W 雙字組 (double word ) 32位元 DW 四字組 (quad word) 64位元 QW

4 單位 簡寫 準確值 近似值 KB 210Bytes 103Bytes MB 220Bytes 106Bytes GB 230Bytes
千位元組 (kilobyte) KB 210Bytes 103Bytes 百萬位元組 (megabyte) MB 220Bytes 106Bytes 十億位元組 (gigabyte) GB 230Bytes 109Bytes 兆位元組 (terabyte) TB 240Bytes 1012Bytes 千兆位元組 (petabyte) PB 250Bytes 1015Bytes 百京位元組 (exabyte) EB 260Bytes 1018Bytes

5 電腦的資料傳輸速率是以bps為單位，意指每秒鐘能夠傳輸多少位元。
我們通常採用Kbps 、Mbps 、Gbps 等單位，意指每秒鐘傳輸1,024 (210)、1,048,576 (220)、1,073,741,824 (230) 位元。

6 2-2 數字系統 電腦使用的二進位系統人類不易閱讀使用 任何一個屬於K進位系統的正數N(整數或實數)都可以表示成如下多項式：16進位最普遍
2-2　數字系統 電腦使用的二進位系統人類不易閱讀使用 任何一個屬於K進位系統的正數N(整數或實數)都可以表示成如下多項式：16進位最普遍 N通常寫成NK = (dp-1dp-2…d1d0.d-1d-2…d-q)K 如 ，最左邊數字dp-1稱最大有效數字(MSD)，最右邊數字d-q稱最小有效數字(LSD)

7 舉例來說，12345.67810是一個十進位數字，我們 可以將它表示成如下多項式：
= 1 x x x 102 + 4 x x x 7 x x 10-3 是一個二進位數字，我們可以將它表 示成如下多項式： = 1 x x x 24 + 1 x x x 21 + 0 x x x 2-2

8 1234.5678是一個八進位數字，我們可以將它表示 成如下多項式：
= 1 x x x x 80 + 5 x x x 8-3 56789A.BC16是一個十六進位數字，我們可以將它 表示成如下多項式： 56789A.BC16 = 5 x x x 163 + 8 x x x 160 + 11 x x 16-2

9 2-2-1 二進位系統 二進位系統 (binary system) 是以0、1等兩個數字做為計數的基底。
2-2-1　二進位系統 二進位系統 (binary system) 是以0、1等兩個數字做為計數的基底。 為了簡化起見，我們通常將二進位數字1000和十進位數字8寫成10002和810 (或寫成10002 = 810)。

10 2-2-2 八進位系統 八進位系統 (octal system) 是以0、1、2 ~ 7等八個數字做為計數的基底。
2-2-2　八進位系統 八進位系統 (octal system) 是以0、1、2 ~ 7等八個數字做為計數的基底。 由於78已經是八進位系統裡面一位數的最後一個數字，所以下一個數字 (810) 必須進位變成108，然後我們可以再往下數118 (910)、128 (1010)、 (1510)、208 (1610)、 218 (1710)、 (2310)、308 (2410)、 318 (2510)、 (3110)、408 (3210)、... 778 (6310)，因為778是八進位系統裡面二位數的最後一個數字，所以下一個數字 (6410) 必須進位變成1008，其它請依此類推。

11 2-2-3 十六進位系統 十六進位系統 (hexadecimal system) 是以0、1~9、
2-2-3　十六進位系統 十六進位系統 (hexadecimal system) 是以0、1~9、 A、B、C、D、E、F等十六個數字做為計數的基底。 由於F16 (1510) 已經是十六進位系統裡面一位數的最後一個數字，所以下一個數字 (1610) 必須進位變成1016，然後我們可以再往下數1116 (1710)、1216 (1810) 、 (2510)、1A16 (2610)、1B16 (2710)、...1F16 (3110)、2016 (3210)、2116 (3310)、...2F16 (4710)、3016 (4810)、3116 (4910)、...3F16 (6310)、...FF16 (25510)，因為FF16是十六進位系統裡面二位數的最後一個數字，所以下一個數字 (25610) 必須進位變成10016，其它請依此類推。

12 十進位 二進位 八進位 十六進位 0000 16 10000 20 10 1 0001 17 10001 21 11 2 0010 18 10010 22 12 3 0011 19 10011 23 13 4 0100 10100 24 14 5 0101 10101 25 15 6 0110 10110 26 7 0111 10111 27 8 1000 11000 30 9 1001 11001 31 1010 A 11010 32 1A 1011 B 11011 33 1B 1100 C 28 11100 34 1C 1101 D 29 11101 35 1D 1110 E 11110 36 1E 1111 F 11111 37 1F 表2.3二、八、十、十六進位對照表

13 2-2-4 將二、八、十六進位數字轉換成十進位數字
2-2-4　將二、八、十六進位數字轉換成十進位數字 = (5 x 1000) + (6 x 100) + (2 x 10) + (1 x 1) + (7 x 0.1) + (8 x 0.01) = (5 x 103) + (6 x 102) + (2 x 101) + (1 x 100) + (7 x 10-1) + (8 x 10-2)

14 = (5 x 84) + (1 x 83) + (7 x 82) + (6 x 81) + (3 x 80) + (2 x 8-1) = (5 x 4096) + (1 x 512) + (7 x 64) + (6 x 8) + (3 x 1) + (2 x 0.125) = =

15 F2A9.C16 = (F x 163) + (2 x 162) + (A x 161) + (9 x 160) + (C x 16-1) = (15 x 4096) + (2 x 256) + (10 x 16) + (9 x 1) + (12 x ) = =

16 = (1 x 24) + (0 x 23) + (1 x 22) + (1 x 21) + (0 x 20) + (0 x 2-1) + (0 x 2-2) + ( ) +( ) = (1 x 16) + (0 x 8) + (1 x 4) + (1 x 2) + (0 x 1) + (0 x 0.5) + (0 x 0.25) + (1 x 0.125) + (1x ) = =

17 2-2-5 將十進位數字轉換成二、八、十六進位數字
2-2-5　將十進位數字轉換成二、八、十六進位數字 將十進位數字 轉換成二進位數字： (1) = (2) 找出整數部分的二進位表示法 (59除以2的餘數) (29除以2的餘數) (14除以2的餘數) (7除以2的餘數) (3除以2的餘數) (最大有效字元) 商數小於除數時停止，依反方向寫下餘數得到5910 =

18 0.75 取得小數部分乘以2 x 2 （3）找出小數部分的二進位表示法 小數點右邊第一位 1.50 0.50 取得小數部分乘以2 x 2
小數點右邊第二位 小數部分等於0時停止 依序寫下乘以2之積數的整數部分得到 = 0.112 （4）將整數部分及小數部分的二進位表示法合併得到 =

19 將十進位數字 轉換成八進位數字： （1） = （2）找出整數部分的八進位表示法 (5176除以8的餘數) (647除以8的餘數) (80除以8的餘數) (10除以8的餘數) (最大有效數字) 商數小於除數時停止，依反方向寫下餘數得到 =

20 (3）找出小數部分的八進位表示法 　 取得小數部分乘以8 x 小數點右邊第一位 取得小數部分乘以8 小數點右邊第二位 依序寫下乘以8之積數的整數部分得到 = 0.248 (4) 將整數部分及小數部分的八進位表示法合併，得到 = 。

21 16 4877 13 (4877除以16的餘數) 將十進位數字4877.610轉換成十六進位數字 ：
（1） = （2）找出整數部分的十六進位表示法 (4877除以16的餘數) (304除以16的餘數) (19除以16的餘數) (最大有效數字) 商數小於除數時停止，依反方向寫下餘數得到 = 130D16

22 （3）找出小數部分的十六進位表示法 取得小數部分乘以16 x 16 小數點右邊第一位 9.6 出現循環時停止 (從小 數點右邊第一位開始) 依序寫下乘以16之積數的整數部分，得到0.610 = 0.916 （4）將整數部分及小數部分的十六進位表示法合併，得到 = 130D.916

23 2-2-6 將八或十六進位數字轉換成二進位數字 5 7 6 2. 1 38 = 101 111 110 010. 001 0112
2-2-6　將八或十六進位數字轉換成二進位數字 = E 8 C 4. B16 =

24 2-2-7 將二進位數字轉換成八或十六進位數字 011 010 111.101 1002 = 3 2 7. 5 48
2-2-7　將二進位數字轉換成八或十六進位數字 = 整數部分每三個數字一組，不足三個的 　就在左邊補上0 　小數部分每三個數字一組，不足三個的 　就在右邊補上0

25 整數部分每四個數字一組，不足四個的就 0010 1101 0111 1010. 1111 00102 = 2 D 7 A. F 216
在左邊補上0 小數部分每四個數字一組，不足四個的就 在右邊補上0

26 2-3　數值表示法 2-3-1　帶符號大小 假設使用n位元來表示正負整數，那麼最左邊的位元 (MSD) 是整數的正負符號，0表示正數，1表示負數，剩下的n - 1位元才是整數的數值大小，正整數的範圍為0 ~ 2n-1-1，負整數的範圍為 -(2n-1-1) ~ 0。 如以8位元來表示+127為 、-127表示為 ，但電腦不採用此種表示。

27 2-3-2　1’s補數 假設使用n位元來表示正負整數，那麼最左邊的位元 (MSD) 是整數的正負符號，0表示正數，1表示負數，剩下的n - 1位元才是整數的數值大小，正整數的範圍為0 ~ 2n-1-1，負整數的範圍為 -(2n-1-1) ~ 0。 1’s補數的正數表示法和帶符號大小一樣，但負數表示法就不一樣了，它是將某個正整數的表示法中所有0改為1，所有1改為0，之後得到的二進位字串才是這個正整數對應的負整數。 如以8位元來表示+127為 、-127表示為 。但電腦亦不採用此種表示。

28 補數 補數的意義，簡單而言就是有一數字(A)和某數(B)加起來等於該數之進制最高大值(C)者,某數(B)即為該數字(A)的補數。補數通常有兩種： 一種為該數之進制最高大值(C)； 另一種為該數之進制最高大值＋１(C+1) 為了簡化數位邏輯電路的結構設計，希望加、減、乘、除四則運算都可以只用一種運算(加法)來完成 ; 例如減法運算可利用補數的方法來完成，乘法運算則是累加和位移的方法，而除法運算則採用累減及位移的方法即可完成。 補數簡單來說，如果將某正數取其補數，就相當於等值的負數 ; 如此可以輕易的將減法運算，經由取補數的動作，變成單純加法的運算。

29 2-3-3　2’s補數(電腦採用的數值表示法) 假設使用n位元來表示正負整數，那麼最左邊的位元 (MSD) 是整數的正負符號，0表示正數，1表示負數，剩下的n - 1位元才是整數的數值大小，正整數的範圍為0 ~ 2n-1-1，負整數的範圍為 -2n-1 ~ 0。 2’s補數的正數表示法和帶符號大小、1’s補數一樣，但負數表示法就不一樣了，它是將某個正整數的表示法中所有0改為1，所有1改為0，之後得到的二進位字串再加上1，才是這個正整數對應的負整數。如以8位元來表示正負整數，則最大數為 (+127)、最小數為 (-128)。

30 十進位 帶符號大小 1’s 補數 2’s 帶符號 大小 +8 無 -8 1000 +7 0111 -7 1111 1001 +6 0110 -6 1110 1010 +5 0101 -5 1101 1011 +4 0100 -4 1100 +3 0011 -3 +2 0010 -2 +1 0001 -1 +0 0000 -0 表2.4不同數值表示法對照表

31 補數的推廣 r補數：若有一數字N不等於0且基底(base)是r，位數為n，則它的r補數(complement)為rn - N 。
若N=0，則N的r補數為0。如 (012398)10的10‘s complement = =987602 ( )2的2‘s complement = = (r-1)補數：若有一數字N不等於0且基底(base)是r，位數為n，則r-1補數(complement)為(rn -1) - N。 若N=0，則N的r-1補數也為0。如 (012398)10的9‘s complement=(106-1) =987601 ( )2的9‘s complement=(27-1) =

32 考題 以2的補數來表示整數，則兩個8位元整數相減 結果為: (A) (B) (C) (D) (89二技管理類) 下列何者可以表示八位元電腦中的-10(以2的補數法表示)? (A) (B) (C) (D) (93中央資管所)

33 使用2的補數來完成減法運算， 則A-B = A+(-B) = A+(B的2的補數) = = 答案(B) -10 = 使用2的補數結果為 1的補數加1， 答案(D)

34 2-4　數值算術運算 2-4-1　加法 範例： （1） （2）

35 （3） （4）

36 （5） （6）

37 2-4-2　減法 （1） （2）

38 （3） （4）

39 （5）

40 2-4-3　乘法 範例：11012 x 10112 x

41 2-4-4　除法 範例： ÷ 10012

42 考題1 (1.75)8 +(2.63)8 以10進位表示為: (A)4.60 (B)4.38 (C)4.75 (D)4.625
(88二技管理類) 考題2 (30)4 * (20)4 以4進位表示為: (A)(1200)4 (B)(600)4 (C)(700)4 (D)(1300) (89二技管理類)

43 考題1答案 C 考題2答案 A 2-5 數碼系統 8421碼 具加權數碼 二五碼(binquary碼)
數 (Weighted) 環形計數碼(ring counter碼) 碼 五取二碼(2-out-of-5碼) 系 超三碼(XS-3碼) 統 葛雷碼(Gray code) 無加權數碼 BCD碼 (Unweighted) ASCII碼 EBCDIC碼 其他

44 2-5　數碼系統 2-5-1　BCD(Binary Coded Decimal)碼，又稱8421碼

45

46 2-5-3　84-2-1碼(互補特性45,36…)

47 2-5-4　超三碼

48 2-5-5　二五碼(又稱5043210碼)；前兩個位元及後五個位元中一定要各有一個位元為1，其餘為0

49 2-5-6　五取二碼(二個位元為1、三個位元為0)

50 任何連續兩個數字的二進位表示法只有一個位元不相同，其餘位元均相同稱為Gray Code。可用於資料傳輸，但不適用於算術運算。 1 3 2 4
2-5-7　葛雷碼 任何連續兩個數字的二進位表示法只有一個位元不相同，其餘位元均相同稱為Gray Code。可用於資料傳輸，但不適用於算術運算。 反射葛雷碼 (reflected gray codes) 公式： 1 3 2 4 5 7 6 12 13 15 14 8 9 11 10 Gn+1 = {0Gn, 1Gnref }，G1 = {0, 1}，n >= 1

51 映 射

52 若要將二進位數字BnBn-1…B1轉換成葛雷碼GnGn-1
二進位數字 ⊕ ⊕ ⊕ ⊕ 葛 雷 碼

53 若要將葛雷碼GnGn-1…G1轉換成二進位數字BnBn-1…B1，可以套用如下公式：
葛 雷 碼 ⊕ ⊕ ⊕ 二進位數字

54 單精確度表示法 (4Bytes)-IEEE754 1bit 8bits 23bits
Sign bit(0表正數1表負數) -(1)S × 2E-127 × 1.F 尾數(mantissa)或稱分數(fraction)必須先做正規化成0.ddd…X2n格式，然後再將最高位的 1調整到個位數上。 偏移指數(biased exponent)ㄧ般使用offset (偏移)方式區別正負，假設exponent部分使用8bits，則共有28=256種狀態(127~ -128)(稱為excess-128)。實數真正的指數=偏移指數-127

55 正規數字(normalized number)表示法如下a0
正規數字(normalized number)表示法如下a0.a1a2a3…×10K，其中a0，需介於1~9之間的ㄧ個整數(前面可以有負號)，不得為0(科學計數法無此限制)。 如3.0 × 10-9是正規數字

56 若某電腦採excess-64格式，請將(194.25)10化成單精確度的浮點格式(採16進位表示)
解 (194.25)10 = ( )2 正規化 = ( )2 × 28 調整成 × 27 i.e.真正指數為7 由題目知道excess-64格式(亦即指數部分有7bits)。所以，指數值應為 = (71)10 亦即為( )2；故浮點格式為 ( )16

57 倍精確度表示法 (8Bytes) 1bit 11bits 52bits
b b62b61b60 … b52 b51b50 … b1b0 就excess-32系統而言，當指數小於-32稱為underflow(超下限)；指數大於31則發生overflow(溢位)。此種情形常會造成例外處理(exception)而引起中斷(interrupt)。

58 中斷(interrupt)有分硬體中斷與軟體中斷，屬於同步事件，是由特定事件所引發的，例如Timer、 Keyboard就會產生硬體中斷；而像BIOS、DOS Function Call就屬於軟體中斷，是由程式自行呼叫所產生的中斷 例外中斷(exception)是為了非正常狀態的執行，例如Divide by 0 or File I/O error就會產生例外中斷，此時可針對異常而進行補救處理 陷阱中斷(trap)屬於例外中斷的一種，一般是在程式中欲執行未經定義的指令或為了Trace程式執行所設定的中斷點，CPU執行到此即會中斷，以便檢視狀態

59 Exception is a general term for an exceptional event that breaks the normal instruction flow.
There are several types of exceptions. Traps are exceptions that are triggered by an action of the program. An trap example is an attempt of a program to execute an undefined instruction. Interrupts are asynchronous events triggered by sources which are external to the core, like a timer.

60 2-7　文字表示法 ASCII(讀作as-key，美國資訊交換標準碼，American Standard Code for Information Interchange) 是目前使用最廣泛的編碼系統，使用7位元來表示字元符號，可表達27=128種文數字字元。 繁體中文編碼系統，例如BIG5 (資策會設計，又稱為大五碼)、王安碼、CCCII碼(全漢字標準交換碼)，以BIG5碼最普遍，使用16位元來表示一個中文字，理論上可表達216=65536種文數字字元，但為兼容ASCII碼故實際僅能表達萬餘字，至於簡體中文則是以GB碼為主。國際上其他各國則採Unicode編碼。

61 EBCDIC(IBM使用，Extended Binary Coded Decimal Interchange Code)和ASCII-8均使用8位元來表示字元符號，共256個字元。
近來又有另一套編碼系統叫做Unicode，這是使用16位元來表示字元符號，為了涵蓋電腦使用的文字及各個語系，可以表示216 (65,536) 個字元，前128個字元符號和ACSII相同。目前編碼已有四萬多個字元。

62

63 2-8 圖形表示法 2-8-1 點陣圖(bitmap graphic)
2-8　圖形表示法 2-8-1　點陣圖(bitmap graphic) 點陣圖是將圖形當成許多點的集合，每個點稱為一個像素 (pixel)，像素愈多，解析度就愈高，畫質也愈細緻。 一張黑白點陣圖可以表示成一連串的像素，每個像素佔用1位元，以0或1表示白色或黑色。28=256色

64 許多電腦設備是藉由不同強度的紅(R)、綠(G)、藍(B)三原色來表示各種顏色，一個像素佔用3位元組
255)。適合用來儲存複雜圖案與色彩的影像(例如：照片) 紅(R) 綠(G) 藍(B) 顏色 紅 綠 藍 白 黑 黃

65 2-8-2 向量圖(vector graphic)
向量圖是利用數學貝茲(Bezier) 曲線來描述圖形的輪廓，然後透過解譯演算法來解譯並轉換成點和線，故向量圖可以依照任意比例放大、縮小、旋轉及傾斜。在工程繪圖上,或製作幾合圖型或較簡易圖型時，向量圖都是較好的選擇,常見的工具軟體是Corel draw、Illustrator flash、Visio、AutoCAD等。通常將向量圖轉成點陣圖很容易，不過將點陣圖轉向量圖效果比較差。 點陣圖放大會產生鋸齒

66 我們平常慣用的繪圖軟體如：Windows內建的小畫家(
我們平常慣用的繪圖軟體如：Windows內建的小畫家(.BMP影像格式)、友立公司的PhotoImpact、Adboe公司的PhotoShop...等所用的影像檔案格式皆為點陣圖 既然點陣圖的體積這麼的龐大，那麼如何可以拿來做網站的主要圖型檔呢？為了要降低點陣圖的尺寸，業界提出了幾種降低圖檔尺寸的方法來，而在網站建置上應用最廣也最普遍的，主要有兩種檔案格式：一個是降低圖檔的色階的256色的.GIF檔案格式，另一個是透過取樣演算的方式來降低圖檔尺寸的全彩的.JPG檔案格式

67 所謂的256色的.GIF影像格式，顧名思義，這種格式的影像其顏色的變化最多只可以有256種而已(其使用1個位元組(byte)(=8個位元bit)來紀錄每一種不同的顏色，而這1個位元組透過排列組合可以擁有256種的變化，也就是256色的由來)，這種影像格式(.GIF)最適合用來儲存我們自己動手畫的圖檔。GIF允許使用者指定透明色系(去背景處理)及支援動畫。 試問：有誰在作畫時，會使用超過256種的顏料呢？因此，256種的顏色變化已經是綽綽有餘的了，所以，透過繪圖軟體所繪製的圖檔，若將之儲存為.GIF的影像格式的話，可以在不降低畫質情況下，有效的降低圖檔的尺寸。

68 全彩的.JPG影像格式，也是使用3bytes來紀錄每一種不同的顏色，而這3bytes透過排列組合當然也可以擁有 種的變化，也就是所謂的16百萬色。既然也是使用3bytes來紀錄每一種不同的顏色，那麼，它與全彩的.BMP的點陣圖又有什麼不同呢？ 差就差在：人類的視覺辨認能力有其上限，基本上很細微的顏色變化透過人眼很難(甚至無法)察覺出來，於是數學家們便透過某種的演算法來取樣並記載點陣圖的色彩變化，因此，不再是每一個單位每一個單位的紀錄圖檔的色彩變化，自然也就有效的降低了圖檔的尺寸，這種.JPG的影像格式，因為仍有 種的顏色變化，特別適合用來儲存透過掃瞄器取得或數位相像所拍攝的圖檔。

69 2-9 聲音表示法 由於聲音屬於連續的類比(analog)訊號，而電腦只能接 受0與1的數位(digital)訊號，因此，聲音必須經過如
2-9　聲音表示法 由於聲音屬於連續的類比(analog)訊號，而電腦只能接 受0與1的數位(digital)訊號，因此，聲音必須經過如 下圖的轉換過程，才能儲存於電腦。單位時間內，取樣 頻率愈高就愈接近原音，但所佔儲存空間越大。一般的 數位音效是每秒取樣8000次，每次取樣存成8bits，所 以一個數位語音通道頻寬為8000*8 =64Kbps 常見得取樣頻率 11KHz(11000次/每秒)=一般聲音 22KHz(22000次/每秒)=錄音機 一般的電台FM廣播為32KHz 44.1KHz(44100次/每秒)=CD 電腦上的DVD音效則為48KHz(經音效卡轉換)

70 2-10 資料壓縮 非失真壓縮：所壓縮過的資料在經過解壓縮後，會和原始資料一樣，不會遺失任何位元。
2-10　資料壓縮 非失真壓縮：所壓縮過的資料在經過解壓縮後，會和原始資料一樣，不會遺失任何位元。 常見的非失真壓縮方法有變動長度編碼 (run length encoding)、霍夫曼碼 (Huffman code)、Lempel-Ziv編碼…等。

71 失真壓縮 (lossy compression)：由於人類的眼睛、耳朵無法察覺非常細微的差異
，所以對於圖形、照片、影像、聲音等資料，可以使用效率高且空間小的失真壓縮 ，例如JPEG、GIF可以用來壓縮圖形、照片，MPEG可以用來壓縮影片，MP3可以用來壓縮聲音(壓縮比約為12：1)…。 　MPEG-1主要應用在VCD 影音光碟 　MPEG-2主要應用在DVD 光碟 　MPEG-4主要應用在視訊傳遞及視訊編輯

72 2-10-1變動長度編碼(run length encoding)
此編碼技術在資料純粹由兩個符號(如0與1)所組成的情況下最有效率，原理是記錄符號出現的次數，例如： 14個1 3個1 0個1 7個1

73 2-10-2 霍夫曼碼 不固定長度的編碼方式，符號的編碼長度與出現頻率成反比。 編碼步驟如下： 1.找出所有符號的出現頻率。
2-10-2　霍夫曼碼 不固定長度的編碼方式，符號的編碼長度與出現頻率成反比。 編碼步驟如下： 1.找出所有符號的出現頻率。 2.將頻率最低的兩者相加得出另一個頻率；其中，頻率低者置放左邊。 3.重覆步驟2不斷將頻率最低的兩者相加，直到只剩下一個頻率為止。 4.根據合併的關係分別配置0(左邊)和1(右邊)，而形成一個編碼樹。

74 (1)假設編碼系統中有A、B、C、D、E、F等符號，其 出現頻率依序為0.2、0.15、0.3、0.18、0.05、0.12
，請據此畫出編碼樹並設計一套霍夫曼碼。 (2) 將 進行解碼 A：01 B：110 C：10 D：00 E：1110 F：1111 (1) (2) F C A D D B

75 2-10-3　LZ編碼 LZ編碼(Lempel-Ziv encoding)屬於字典式編碼(dictionary based encoding)，也就是在進行壓縮時，從原始資料擷取字典中所沒有的子字串，然後建立成字典中的索引，再根據索引加以編碼。

76

77

78 2-11 誤差與錯誤檢查 固有誤差 (inherent error)：由先天上的限制所導致的誤差。如無窮小數1/3
2-11　誤差與錯誤檢查 固有誤差 (inherent error)：由先天上的限制所導致的誤差。如無窮小數1/3 捨棄誤差(truncation error)：因數值方法(如刪除尾數項)所造成的誤差。 捨位誤差(round-off error)：以有限小數來替代真正數所造成的誤差。如小數點無法完全存入浮點格式的mantissa時，就會產生這種誤差。

79 同位元檢查 奇(odd)同位元檢查 (parity check) 偶(even)同位元檢查 數 碼 定數檢查(fixed-count check) 檢 查 循環冗餘碼檢查(Cyclic Redundancy Check) 漢明碼(Hamming Code)

80 2-11-1　同位位元檢查 在資料位元傳送出去之前，先加上一個同位位元 (通常加在最前面)，然後傳送出去，待接收到這些位元圖樣後，就檢查看看是否有奇數個1或偶數個1。 又分成奇同位檢查和偶同位檢查。

81 2-11-2　循環冗餘碼 (CRC) 讓發訊端與收訊端事先協調一個生成多項式，然後發訊端在將資料位元傳送出去之前，先將資料位元除以生成多項式，再將得到的餘數 (即CRC碼) 放在資料位元的後面一起傳送出去。CRC法保證在1012之中只會出現一個錯誤。

82 假設資料位元為110010101110，生成多項式為X3 + 1 (1001)，試求取CRC碼及加上CRC碼後的完整訊息：

83 以長除法求取110010101110000除以生成多項式X3 + 1 (1001) 的餘數：
CRC碼為餘數11，故完整訊息為 。只要收訊端有正確的接收到訊息，就ㄧ定能被生成多項式所整除。

84 2-11-3　錯誤更正碼 (ECC) 漢明碼為一兼具自動錯誤偵測與更正一個bit的雙種功能，若用7個bit，4個代表data，3個代表檢查碼。 Bit position Data M4 M3 M M1 Check bit C C2 C1 其中，C1 = M4 ⊕ M2 ⊕ M1 C2 = M4 ⊕ M3 ⊕ M1 C3 = M4 ⊕ M3 ⊕ M2

85 當錯誤更正碼的漢明距離大於等於D時，只要發生錯誤的位元不超過D - 1個，系統都能夠偵測出來，而只要發生錯誤的位元不超過 (D - 1) / 2個，系統都能夠加以更正。
考題：漢明碼距離為5的一組編碼，至多能校正幾個位元的錯誤? (A)1 (B)2 (C)3 (D)4 PS.漢明碼距離指的是兩個碼中所具有不同位元值的數目，如00110和11110之間，漢明碼距離為2

86 補充 16進位 28*B5何值？ 先轉成2進位再計算 2816= B516= * (1 C )16

87 小考1 (123.4)8等於16進位何值？(A) (B)53.8 (C) (D)83.8 小考2 當10進位數(-9)用8位元以2的補數表示，其等值為？ (A) (B) (C) (D)

88 小考1 先化成2進位，再化成16進位 (123.4)8=( )2 =( )=(53.8)16 答案B 小考2 (-9)10=( )2 =>1的補數 ( )2 =>2的補數 ( )2 答案B

89 Ref. 課本P2-46~47 資訊科技的專業技術認證