第二章運算方法與運算器

22.1數制與編碼2.1.1進位計數制及其相互轉換回顧與復習1、數制任意一個數（N）R＝an－1an－2…a1a0.a－1a－2…a－m的按權展開式為：（N）R＝an－1Rn-1＋an－2Rn-2＋…＋a0R0＋a-1R-1＋…＋a－mR-m①R為基數，表示數列中各位數字ai的取值范圍是0～R－1，并且計數規則是“逢R進一”②ai為系數，代表第i位的一個數碼，可以是0～R-1中任意一個；③Ri

為第i位的權值。基數和權值是任意進位計數制中兩個重要的基本因素。3常見的進位計數制有：二、八、十、十六進制等。

基數基本取值規則后綴表示形式二進制20，1逢二進一B（1010.0010）2或1010.0010B八進制80，1…，7逢八進一O或Q（317.061）8或317.061Q或317.061O

十進制100，1…，9逢十進一D或省略（2549.57）10或2569.57D或2569.57

十六進制160，1…，F

逢十六進一

H

（24AE.F）16或24AE.FH

42、各種進制數之間的轉換1）任意進制十進制方法：按權展開然后相加例：將（101101.0011）2轉換成十進制數。解：（101101.0011）2＝1×25＋0×24＋1×23＋1×22＋0×21＋1×20＋0×2－1＋0×2－2＋1×2－3＋1×2－4＝45.18755２）十進制

任意進制整數部分：除基取余小數部分：乘基取整例：將十進制數98.375轉換成二進制數。解：整數部分

298余數

2490最低位

2241212026023021101最高位整數部分（98）10＝（1100010）260.375×2整數

0.750最高位

×21.510.5×21.01最低位故小數部分（0.375）10＝（0.011）2所以（98.375）10＝（1100010.011）273）二、八、十六進制間的轉換例：（1101011.1101）2=（153.64）8=（6B.D）16例：將十六進制數（2B.6）16轉換成八進制數。解：（2B.6）16=（00101011.0110）2=（053.30）8

任意進制數之間的轉換可以用十進制或二進制進行中轉。82.1.2機器數的表示機器數無符號數有符號數原碼補碼反碼移碼9真值、原碼、反碼、補碼的轉換10例如：當X＝＋0.1100[X]原＝0.1100[X]反＝0.1100[X]補＝0.1100

當X＝－1100[X]原＝11100[X]反＝10011[X]補＝1010011當X＝0時，[＋0.0000]原＝0.0000[－0.0000]原＝1.0000當X＝0時，[＋0.0000]反＝0.0000[－0.0000]反＝1.1111當X＝0時，[＋0.0000]補＝0.0000[－0.0000]補＝0.0000原碼、反碼“0”的表示形式不唯一。補碼“0”只有一種表示形式。12移碼表示法小數移碼：[X]移＝1＋X1＞X≥－1整數移碼：[X]移＝2n＋X2n＞X≥－2nX為真值，n為整數的位數。移碼表示是將真值X在數軸上正向平移1（小數）或2n（整數）后得到的。13例：（1）當X＝＋10101，求[X]移。解：[X]移＝2n＋X＝25＋X＝100000＋10101＝110101[X]補＝010101

（2）當X＝－0.10101，求[X]移。解：[X]移＝1＋X＝1－0.10101＝0.01011[X]補＝1.01011移碼和補碼的符號位相異。當X＝0時，[＋0.00…0]移＝1＋X＝1＋0.00…0＝1.00…0[－0.00…0]移＝1＋X＝1－0.00…0＝1.00…0“0”的移碼的表示形式也是唯一的。14例：設機器字長為8位，其中包含一位符號位，對于整數，當其分別代表無符號數、原碼、補碼、反碼和移碼時，對應的真值范圍各位多少？解：下表列出了8位機器字長所對應的所有的二進制代碼，當其分別代表無符號數、原碼、補碼、反碼和移碼時，所對應的真值（用十進制數表示）。15二進制代碼無符號數對應的真值原碼對應的真值補碼對應的真值反碼對應的真值移碼對應的真值000000000+00+0－128000000011＋1＋1＋1－127000000102＋2＋2＋2－126………………01111111127＋127＋127＋127－110000000128－0－128－127010000001129－1－127－126＋1………………11111110254－126－2－1＋12611111111255－127－1－0＋12716結論：1、補碼和移碼只有一個“0”，原碼和反碼有“＋0”和“－0”之分。2、8位無符號數對應的真值的表示范圍是0～255；原碼、反碼對應的真值的表示范圍是－127～＋127；補碼、移碼對應的真值的表示范圍是－128～＋127。3、補碼和移碼表示范圍比原碼和反碼多一個負數。172.1.3十進制數的二進制編碼

計算機能處理十進制數，而十進制數在計算機內是采用二進制數碼編碼的。 用二進制數碼表示十進制數稱為二進制編碼的十進制數（Binary-CodedDecimal），簡稱BCD碼。 一位十進制數需要4位二進制數進行編碼。181、8421碼特點：①有權編碼，十進制數D＝8b3＋4b2＋2b1＋1b0。②8421碼與所對應的十進制數之間符合二進制和十進制數相互轉換的規則，簡單直觀。③編碼中不許出現1010～1111。例：（258.27）10=(001001011000.00100111)8421(10010101.01110010)8421=(95.72)10192、2421碼特點：①有權編碼，十進制數D＝2b3＋4b2＋2b1＋1b0。②是對9的自補碼。即某數的2421碼，只要按自身取反，就能得到該數對9的補碼的2421碼。例如：4的2421碼是0100，4對9的補碼是5，而5的2421碼是1011，即4的2421碼自身按位取反可得到5的2421碼。③編碼中不許出現0101～1010。203、余三碼 從二進制編碼序列中選取0011～1100對應表示十進制數的0～9。 若將二進制代碼按二進制數轉換成十進制數，其值比相應的十進制數多3，所以稱為余三碼。特點：①無權編碼。②也是對9的自補碼。③不許出現0000～0010、1101～1111。21十進制數的二進制編碼表十進制數8421碼2421碼余三碼0000000000011100010001010020010001001013001100110110401000100011150101101110006011011001001701111101101081000111010119100111111100未選用的編碼1010～11110101～10100000～00101101～1111222.1.4非數值數據的表示

機器內除了數值信息之外，還有數字、字母、通用符號、控制符號等字符信息、邏輯信息、圖形、圖像、語音等信息，稱為非數值數據。這些信息進入計算機后都轉變成“0”、“1”表示的二進制編碼。1、邏輯數據特點：（1）邏輯數中的“0”和“1”不代表值的大小，僅代表一個命題的真與假、是與非等邏輯關系；（2）沒有符號問題。各位之間相互獨立，沒有位權和進位問題；（3）只能參加邏輯運算，并且按位進行。232、字符與字符串 字符是非數值數據的基礎，字符與字符串數據是計算機中用的最多的非數值型數據。在使用計算機的過程中，人們需要利用字符與字符串編寫程序、表示文字及各類信息，以便與計算機進行交流。（1）字符編碼 對字符按一定規則進行二進制進行編碼。廣泛采用的是美國國家信息交換標準代碼(AmericanStandardCodeforInformationInterchange)，簡稱ASCII碼。（2）字符串的表示 字符串數據是指連續的一串字符。通常一個字符串需要占用主存中多個連續的字節進行存放。24字符串的存儲形式（單字節存儲器）：25多字節存儲器存儲形式：字符串中的字符從低位字節向高位字節順序存放；字符串中的字符從高位字節向低位字節順序存放。例：設主存字長為32位，將字符串“HOWAREYOU?”按從高位字節向低位字節的順序和從低位字節向高位字節的順序存放到主存中。解：這一字符串包括空格在內共有12個字符。48H4FH57H20H41H52H45H20H59H4FH55H3FH3210A+0A+4A+820H57H4FH48H20H45H52H41H3FH55H4FH59H3210A+0A+4A+8從高到低從低到高263、漢字編碼計算機處理漢字要比處理英文字符更加復雜。 在計算機中使用漢字時，需要涉及漢字的輸入、存儲、處理、輸出等各方面的問題。（1）漢字輸入碼①拼音碼②字形碼③數字編碼④整字編碼（2）國標碼漢字信息交換的一個通用的標準。國標碼規定每個漢字或圖像符號都用兩個連續的字節表示，每個字節只使用最低七位，兩個字節的最高位均為0。27（3）漢字內碼漢字內碼是漢字在計算機內用于存儲、檢索、交換的信息代碼。將國標碼兩個字節最高位改為1。如“啊”的國標碼為0011000000100001，漢字內碼為1011000010100001。（4）漢字字形碼用0、1表示漢字的字形，將漢字放入n行×ｎ列的正方形內，該正方形共有n2個小方格，每個小方格用一位二進制表示，凡是筆畫經過的方格值為1，未經過的值為0。284、UnicodeUnicode是一種在計算機上使用的字符編碼。 它為每種語言中的每個字符設定了統一并且唯一的二進制編碼，以滿足跨語言、跨平臺進行文本轉換、處理的要求。

Unicode于1990年開始研發，1994年正式公布。 在Unicode體系中，每個字符和符號被賦予一個永久、唯一的16位值，即碼點。Unicode體系中共有65536個碼點，可以表示65536個字符。292.1.5數據信息的校驗1、奇偶校驗奇校驗：校驗碼（包括信息位和校驗位）中1的個數為奇數。偶校驗：校驗碼中1的個數為偶數。例：信息位奇校驗碼偶校驗碼

00000000

100000000

000000000

01010100

001010100

101010100

01111111

001111111

101111111

11111111

111111111

011111111其中，最高一位為校驗位，低八位為信息位。30優點：實現簡單方便。缺點：只能發現出錯，不能找出錯誤的具體位置；檢測不了偶數位同時出錯的情況。312、海明校驗由RichardHamming（理查德·海明）于1950年提出。不僅能檢測錯誤，還能指出錯誤所在位置。（1）校驗位的位數 設海明碼為N位，信息位為k位，校驗位為r位。應滿足如下關系：2r≥k+r+1信息位k值校驗位r值122~435~11412~26527~57658~120732（2）海明碼的編碼方法①將k位信息位和r位校驗位，構成k＋r位的海明校驗碼。設校驗碼各位編碼的位號按從左向右（或從右向左）的順序從1到k＋r排列，規定校驗位所在的位號分別為2i，i＝0，1，2，…，r－1，信息位按照原來的編碼順序依次安排在其他的位號中。設ASCII碼的有效信息位為b1b2b3b4b5b6b7。若k＝7，則r＝4，海明校驗碼為7＋4＝11位。4個校驗位分別位于位號為2i的位置上，即位號為20、21、22、23的位置上。設校驗位為p1、p2、p3、p4，有效校驗位b1b2b3b4b5b6b7依次排列在其余位上。位號：1234567891011編碼：p1p2b1p3b2b3b4p4b5b6b733②將r個校驗位分成r組進行奇偶校驗，每個有效信息位都被2個或2個以上的校驗位校驗。 有效信息位被哪些校驗位校驗的規則：被校驗的信息位位號等于校驗它的校驗位的位號之和。例：b3的位號是6，6＝2＋4，所以b3應被p2和p3所校驗；b7位號是11，11＝1＋2＋8，所以b7應被p1、p2和p4所校驗。依此類推。。。34

由上圖可知，每個校驗位校驗著哪些信息位，也可以看出校驗組的分組情況，每一組包含了一個校驗位。p1：b1、b2、b4、b5、b7（校驗位p1可以校驗信息位b1、b2、b4、b5、b7）（第一組）p2：b1、b3、b4、b6、b7（校驗位p2可以校驗信息位b1、b3、b4、b6、b7）（第二組）p3：b2、b3、b4（校驗位p3可以校驗信息位b2、b3、b4）（第三組）p4：b5、b6、b7（校驗位p4可以校驗信息位b5、b6、b7）（第四組）35③根據分組情況，按奇偶校驗原理，求出各個校驗位，形成海明校驗碼。偶校驗方法：p1＝b1⊕b2⊕b4⊕b5⊕b7p2＝b1⊕b3⊕b4⊕b6⊕b7p3＝b2⊕b3⊕b4p4＝b5⊕b6⊕b7奇校驗方法：p1＝b1⊕b2⊕b4⊕b5⊕b7⊕1p2＝b1⊕b3⊕b4⊕b6⊕b7⊕1p3＝b2⊕b3⊕b4⊕1p4＝b5⊕b6⊕b7⊕136例：編制ASCII字符X的偶校驗的海明碼。解：X的ASCII碼為1011000，其偶校驗海明碼的校驗位分別為：p1＝b1⊕b2⊕b4⊕b5⊕b7＝10100＝0p2＝b1⊕b3⊕b4⊕b6⊕b7＝11100＝1p3＝b2⊕b3⊕b4＝011＝0p4＝b5⊕b6⊕b7＝000＝0則字符X的偶校驗的海明碼：。同理求得其奇校驗的海明碼為：10110111000。37（3）海明碼的校驗以上述7位ASCII碼為例，校驗時，分四組進行校驗。按偶校驗的海明碼求指誤字E4E3E2E1：E1＝p1⊕b1⊕b2⊕b4⊕b5⊕b7E2＝p2⊕b1⊕b3⊕b4⊕b6⊕b7E3＝p3⊕b2⊕b3⊕b4E4＝p4⊕b5⊕b6⊕b7按奇校驗的海明碼求指誤字E4E3E2E1：E1＝p1⊕b1⊕b2⊕b4⊕b5⊕b7⊕1E2＝p2⊕b1⊕b3⊕b4⊕b6⊕b7⊕1E3＝p3⊕b2⊕b3⊕b4⊕1E4＝p4⊕b5⊕b6⊕b7⊕1若E4E3E2E1＝0000，則無錯誤；若E4E3E2E1≠0000，則其所對應的十進制值可以指明所接收到的11位海明校驗碼中出錯的位號。38例：已知ASCII字符X的偶校驗的海明碼為。設接收到的代碼是和，分別寫出校驗后得到的指誤字并判別出錯位置。解：①若接收到的代碼是，則指誤字E4E3E2E1分別為：E1＝p1⊕b1⊕b2⊕b4⊕b5⊕b7＝0⊕1⊕0⊕1⊕1⊕1＝0E2＝p2⊕b1⊕b3⊕b4⊕b6⊕b7＝1⊕1⊕1⊕1⊕0⊕0＝0E3＝p3⊕b2⊕b3⊕b4＝0⊕0⊕1⊕1＝0E4＝p4⊕b5⊕b6⊕b7＝0⊕0⊕0⊕1＝0即E4E3E2E1＝0000，說明接收到的海明校驗碼沒有錯誤。②若接收到的代碼是，則指誤字E4E3E2E1分別為：E1＝p1⊕b1⊕b2⊕b4⊕b5⊕b7＝0⊕1⊕0⊕0⊕1⊕1＝1E2＝p2⊕b1⊕b3⊕b4⊕b6⊕b7＝1⊕1⊕1⊕0⊕0⊕0＝1E3＝p3⊕b2⊕b3⊕b4＝0⊕0⊕1⊕0＝1E4＝p4⊕b5⊕b6⊕b7＝0⊕0⊕0⊕1＝0即E4E3E2E1＝0111，說明接收到的海明校驗碼的第7位出錯，將其取反即可。393、循環冗余校驗碼（CyclicRedundancyCheck，CRC）適用于串行傳送方式的領域中。如：磁介質存儲器與主機之間的信息傳輸；計算機之間的通信；網絡通信等。CRC碼是基于模2運算的校驗碼。40特點：不考慮進位和借位的運算。①模2加減：即按位加，可用異或邏輯實現。0±0=00±1=11±0=11±1=0。②模2乘：按模2加的規則求部分積之和，計算時不進位。

1010

×

101

1010

0000

1010

10001041③模2除：按模2減（加）求部分余數，計算時不借位。上商的原則是：當部分余數（首次是被除數）的最高位為1時，則上商為1；當部分余數最高位為0時，則上商為0。每求一位商應使部分余數減少一位。當部分余數的位數小于除數的位數時，該余數即為最后余數。42

110110110011101110011010010000001010000101100143（1）CRC編碼方法將待編碼的k位有效信息位表示為多項式：M(x)＝Ck-1xk-1+Ck-2xk-2+…+Cixi+…+C1x1+C0x0將信息位左移r位，即M(x)·xr

，就可以空出初值為０的r個校驗位。CRC碼是用k個數據位拼接上r個校驗位得到的。設G(x)為生成多項式（特定的一個多項式），余數為R(x)（校驗位），商為Q(x)，則：M(x)·xr/G(x)=Q(x)+R(x)/G(x)并推導出：M(x)·xr+R(x)=[Q(x)·G(x)+R(x)]+R(x)

=[Q(x)·G(x)]+[R(x)+R(x)]

=Q(x)·G(x)

即CRC碼是一個可被G(x)數碼除盡的數碼。44例：設生成多項式為G(x)=x3+x+1，將4位有效信息位1100編成7位CRC碼。解：生成多項式G(x)=x3+x+1=1011，有效信息M(x)=1100=x3+x2

(k=4)M(x)·x3=x6+x5=1100000；

M(x)·x3/G(x)=1100000/1011=1110+010/1011

即余數R(x)（校驗位）為010。

M(x)·x3+R(x)=1100000+010=1100010∴有效信息位1100的7位CRC碼為1100010。45在CRC碼中，由k位信息位和r位校驗位構成k＋r位編碼，稱為（k＋r，k）碼。在若k＝4，k＋r＝7，則稱（7，4）碼。（7，4）碼為碼制，還可以有（7，3）碼制和（7，6）碼制等。46（2）CRC的譯碼與糾錯將收到的CRC碼用G(x)去除，如果無錯余數應為0；如有某一位出錯，則余數不為0；不同數位出錯余數會不同。如果循環碼有一位出錯，用G(x)作模2除將得到一個不為0的余數。如果對余數補0繼續除下去,則各次余數將按下表中的內容順序循環。47A1A2A3A4A5A6A7余數出錯位正確1

1

0

0

0

1

0000無錯誤11

0

00

1

1

1

1

0

00

0

0

1

1

0

0

1

1

0

1

1

0

1

0

1

0

1

1

1

0

0

1

0

1

0

0

0

0

1

0

0

1

0

0

0

1

0001

010

100

011

110

111

1017

6

5

4

3

2

148并不是任何一個r次的多項式都可以作為生成多項式。要求：任何一位發生錯誤應當使余數不為0；不同位發生錯誤應當使余數不同；對余數繼續作模2除，應使余數循環。2.2機器數的定點表示和浮點表示502.2.1定點數的表示定點數的格式定點整數（小數點約定在最低位的右邊，最高位為符號位）

2.定點小數（最高位為符號位，小數點約定在符號位的右邊）說明：小數點的位置僅是一種約定，計算機內并無專門的器件來表示它。XnXn-1……X0XnXn-1……X051定點數的表示范圍：編碼方式定點小數定點整數最小數最大數最小數最大數原碼－（1－2-n）1－2-n－（2n－1）2n－1反碼－（1－2-n）1－2-n－（2n－1）2n－1補碼－11－2-n－2n2n－1移碼－11－2-n－2n2n－1522.2.2浮點數的表示定點數和浮點數的比較定點數表示數的范圍比較小，運算容易發生溢出；浮點數表示數的范圍比較大，運算不容易發生溢出且精度高