全套電子課件：數(shù)字邏輯

1、歡迎使用數(shù)字邏輯與數(shù)字系統(tǒng)設(shè)計(jì)1目錄第一章 數(shù)制與編碼1前言第一節(jié) 進(jìn)位計(jì)數(shù)制1第二節(jié) 數(shù)制轉(zhuǎn)換2第三節(jié) 帶符號(hào)二進(jìn)制數(shù)的表示方法4第四節(jié) 數(shù)的定點(diǎn)與浮點(diǎn)表示法7第五節(jié) 字符編碼8第六節(jié) 可靠行編碼 10習(xí)題 16 第二章 布爾代數(shù)及其邏輯實(shí)現(xiàn) 第一節(jié) 布爾代數(shù)的基本概念19 第二節(jié) 布爾代數(shù)的公式、定理和 規(guī)則22 第三節(jié) 布爾函數(shù)的基本形式25 第四節(jié) 布爾函數(shù)的代數(shù)化簡(jiǎn)法28 第五節(jié) 布爾函數(shù)的卡諾圖化簡(jiǎn)法30 第六節(jié) 布爾函數(shù)的實(shí)現(xiàn)37 第七節(jié) 多輸出布爾函數(shù)的化簡(jiǎn) 與實(shí)現(xiàn)44 習(xí)題47第四章 組合邏輯電路102第一節(jié) 組合邏輯電路的分析102第二節(jié) 組合邏輯電路設(shè)計(jì)105第三節(jié) 常用

2、組合邏輯電路分析 與應(yīng)用120習(xí)題154第三章 集成邏輯門(mén)電路51 第一節(jié) 晶體管開(kāi)關(guān)的特性51 第二節(jié) 基本邏輯門(mén)電路54第三節(jié) TTL集成電路 58*第四節(jié) 集成MOS門(mén)電路 80習(xí)題96 第五章 觸發(fā)器159第一節(jié) 基本觸發(fā)器159 第二節(jié) 其它觸發(fā)器162第三節(jié) 空翻現(xiàn)象及其解決方法167第四節(jié) 不同類(lèi)型觸發(fā)器邏輯 功能的轉(zhuǎn)換.171第五節(jié) 觸發(fā)器的主要參數(shù)和 脈沖工作特性172習(xí)題174 目錄第七章 異步時(shí)序邏輯電路227第一節(jié) 脈沖異步時(shí)序邏輯電路227第二節(jié) 電平異步時(shí)序邏輯電路236*第三節(jié) 電平異步時(shí)序邏輯電路 的設(shè)計(jì)241第四節(jié) 邏輯電路的險(xiǎn)象250*第五節(jié) 電平異步時(shí)序邏

3、輯電路 設(shè)計(jì)舉例257習(xí)題260第六章 同步時(shí)序邏輯電路177第一節(jié) 時(shí)序邏輯電路的基本概念177第二節(jié) 同步時(shí)序邏輯電路的分析183第三節(jié) 同步時(shí)序邏輯電路的設(shè)計(jì)187第四節(jié) 同步時(shí)序邏輯電路設(shè)計(jì) 舉例205第五節(jié) 常用同步時(shí)序邏輯電路212習(xí)題223第八章 脈沖產(chǎn)生與整形電路第一節(jié) 555時(shí)基電路 264第二節(jié) 施密特觸發(fā)器266第三節(jié) 單穩(wěn)態(tài)觸發(fā)器271第四節(jié) 多諧振蕩器278習(xí)題.280第九章 可編程邏輯器件285 第一節(jié) 只讀存儲(chǔ)器(ROM)286第二節(jié) 可編程邏輯陣列(PLA)294第三節(jié) 可編程陣列邏輯(PAL)301*第四節(jié) 通用陣列邏輯(GAL)308習(xí)題.337第十章 在系

4、統(tǒng)編程技術(shù)340第一節(jié) ISP技術(shù)的特點(diǎn) 340第二節(jié) ISP邏輯器件 344第三節(jié) ispLSI器件的結(jié)構(gòu)347*第四節(jié) 在系統(tǒng)編程和方法356*第五節(jié) ISP技術(shù)的實(shí)現(xiàn) EDA技術(shù)365*第六節(jié) EDA系統(tǒng)中的可編程集成 電路（ASIC）設(shè)計(jì)379習(xí)題381參考文獻(xiàn)382說(shuō)明：加“*”的章節(jié)，可根據(jù)學(xué)時(shí)的安排，作為選學(xué)內(nèi)容第一章 數(shù)制與編碼本章內(nèi)容提要第一節(jié) 進(jìn)位計(jì)數(shù)制第二節(jié) 數(shù)制轉(zhuǎn)換第三節(jié) 帶符號(hào)二進(jìn)制數(shù)的表示方法第四節(jié) 數(shù)的定點(diǎn)與浮點(diǎn)表示法第五節(jié) 字符編碼第六節(jié) 字符編碼概述 數(shù)字計(jì)算機(jī)現(xiàn)已廣泛地應(yīng)用于科學(xué)計(jì)算、數(shù)據(jù)處理和過(guò)程控制等領(lǐng)域。數(shù)字計(jì)算機(jī)是數(shù)字系統(tǒng)中最常見(jiàn)、最有代表性的一種設(shè)

5、備。數(shù)字系統(tǒng)的特點(diǎn)是它所處理的 信息都是離散元素。 這些離散元素可以是十進(jìn)制數(shù)字、某種字母、各種算符及標(biāo)點(diǎn)符號(hào)等。離散元素通常是以二進(jìn)制的形式出現(xiàn)的。為此,必須討論數(shù)的代碼特征及運(yùn)算。 本章討論數(shù)制和編碼的概念。通過(guò)本章學(xué)習(xí),讀者將熟悉數(shù)字系統(tǒng)數(shù)制和編碼的表示方法、性質(zhì)及相互間的轉(zhuǎn)換,帶符號(hào)數(shù)和帶小數(shù)點(diǎn)數(shù)的表示方法及字符編碼,為離散元素的處理打下基礎(chǔ)。第一節(jié) 進(jìn)位計(jì)數(shù)制 十進(jìn)制計(jì)數(shù)制早已為人們所熟悉。在十進(jìn)制計(jì)數(shù)制中,采用了10 個(gè)有序數(shù)字符號(hào)0、1、2、3、4、5、6、7、8、9 和一個(gè)小數(shù)點(diǎn)符號(hào)“. ”,并且是“逢十進(jìn)一”。任何一個(gè)十進(jìn)制數(shù), (S)10可以表示為(S)10 = kn-1

6、10n-1 + kn-2 10n-2 + + k0 100 + k-1 10-1 + + k-m 10-m 其中,ki可以是09這10個(gè)數(shù)碼中的任一個(gè),m 和n是正整數(shù),ki、m 、n 均由(S)10決定,(S)的下標(biāo)與式中的10是十進(jìn)制的基數(shù)。一、十進(jìn)制計(jì)數(shù)制 由于基數(shù)為10，每個(gè)數(shù)位計(jì)滿10就向高位進(jìn)位,即逢十進(jìn)一,所以稱(chēng)它為十進(jìn)制計(jì)數(shù)制。 例如,一個(gè)十進(jìn)制數(shù)2003.3，可以表示為:(2003.3)10 = 2103 + 0102 + 0101 +3100 +310-1 在數(shù)字系統(tǒng)中,為了便于工程實(shí)現(xiàn),廣泛采用二進(jìn)制計(jì)數(shù)制。這是因?yàn)?二進(jìn)制的每一位只用兩個(gè)數(shù)碼0和1,因而可以用具有兩個(gè)不

7、同穩(wěn)定狀態(tài)的電子元件來(lái)表示,并且二進(jìn)制數(shù)運(yùn)算簡(jiǎn)單,數(shù)的存儲(chǔ)和傳送也可用簡(jiǎn)單而可靠的方式進(jìn)行。二進(jìn)制基數(shù)是2,其計(jì)數(shù)規(guī)律是逢二進(jìn)一。二、二進(jìn)制計(jì)數(shù)制 任意一個(gè)二進(jìn)制數(shù)可以表示為:(S)2 = kn- 12n- 1 + kn -22n -2 + + k020 + k-12- 1 + + k- m2- m = 其中, ki 只能取0或1,m、n 為正整數(shù),由(S)2決定。例如,一個(gè)二進(jìn)制數(shù)1011.101可以表示為: (1011.101)2 = 123 + 022 + 121 + 120 + 12- 1 + 02- 2 + 12-3 采用二進(jìn)制計(jì)數(shù)制,對(duì)計(jì)算機(jī)等數(shù)字系統(tǒng)來(lái)說(shuō),數(shù)據(jù)的運(yùn)算、存儲(chǔ)和傳送都

8、極為方便,但二進(jìn)制書(shū)寫(xiě)很不方便,且記憶困難,為此人們經(jīng)常采用八進(jìn)制計(jì)數(shù)制和十六進(jìn)制計(jì)數(shù)制來(lái)進(jìn)行書(shū)寫(xiě)或打印。 任意一個(gè)八進(jìn)制數(shù)可以表示為 (S)8 其中, ki可取0、1、2、7 這8 個(gè)數(shù)碼之一,m和n為正整數(shù),由(S)8決定。八進(jìn)制的基數(shù)是8,其計(jì)數(shù)規(guī)律是逢八進(jìn)一。三、八進(jìn)制計(jì)數(shù)制和十六進(jìn)制計(jì)數(shù)制 例如,八進(jìn)制數(shù)(537. 25)8 可以表示為(537.25)8 = 582 + 381 + 780 + 28- 1 + 58-2 任意一個(gè)十六進(jìn)制數(shù)可以表示為 (S)16 其中, ki 可取0、1、2、8、9、A、B、C、D、E、F 等10 個(gè)數(shù)碼及6 個(gè)字母之一,m 和n 為正整數(shù),由(S)1

9、6決定,十六進(jìn)制數(shù)的基數(shù)是16,其計(jì)數(shù)規(guī)律是逢十六進(jìn)一。 例如,一個(gè)十六進(jìn)制數(shù)(7FAE3. 8C)16 可以表示為(7FAE3.8C)16 = 7164 + F163 + A162 + E161 + 3160 + 816-1 + C16-2 人們習(xí)慣的是十進(jìn)制數(shù),計(jì)算機(jī)及數(shù)字系統(tǒng)采用的是二進(jìn)制數(shù),人們書(shū)寫(xiě)時(shí)又多采用八進(jìn)制數(shù)或十六進(jìn)制數(shù),因此,必然產(chǎn)生各種進(jìn)位計(jì)數(shù)制間的相互轉(zhuǎn)換問(wèn)題,以便計(jì)算機(jī)和人之間相互理解。 對(duì)于基值大的整數(shù)轉(zhuǎn)換成基值小的整數(shù)時(shí),一般采用除基取余法進(jìn)行,例如(935)10 = (?)2 可以用如下方法: 第二節(jié) 數(shù)制轉(zhuǎn)換一、整數(shù)轉(zhuǎn)換方法 1 3 7 14 29 58 116

10、 233 467 935 2 1 1 1 0 1 0 0 1 1 1 余數(shù) 轉(zhuǎn)換結(jié)果為(935)10 = (1110100111)2 對(duì)于基值小的整數(shù)轉(zhuǎn)換成基值大的整數(shù)時(shí),一般采用按冪展開(kāi)法進(jìn)行,例如:(1101001)2 =126 +125 +024 +123 +022 + 021+120 = (105)10二、小數(shù)轉(zhuǎn)換方法 0.875 0.75 0.5 0.0 2 1 1 1 0 整數(shù) 對(duì)于基值大的小數(shù)轉(zhuǎn)換成基值小的小數(shù)時(shí),一般采用乘基取整法進(jìn)行,例如(0.875)10 =(?)2 可以用如下方法:轉(zhuǎn)換結(jié)果為(0. 875)10 = (0. 1110)2 同樣對(duì)于基值小的小數(shù)轉(zhuǎn)換成基值大的

11、小數(shù)時(shí),一般采用按冪展開(kāi)法進(jìn)行,例如:(0.1101)2=12-1 + 12-2 + 02 -3 + 12-4 =(0.8125)10三、二進(jìn)制數(shù)與八進(jìn)制數(shù)和十六進(jìn)制數(shù)之間的轉(zhuǎn)換 二進(jìn)制數(shù)與八進(jìn)制數(shù)和十六進(jìn)制數(shù)之間有著確定的對(duì)應(yīng)關(guān)系,對(duì)于二進(jìn)制數(shù)與八進(jìn)制數(shù)之間為每3 位二進(jìn)制數(shù)對(duì)應(yīng)1 位八進(jìn)制數(shù),當(dāng)二進(jìn)制數(shù)轉(zhuǎn)換為八進(jìn)制數(shù)時(shí),從小數(shù)點(diǎn)開(kāi)始分別向左或向右每3 位一組劃分,不足3 位時(shí)用0填補(bǔ),即可得到等值的八進(jìn)制數(shù),例如: (1101011.1001)2 = (153.44)8 而八進(jìn)制數(shù)轉(zhuǎn)換為二進(jìn)制數(shù)時(shí),則直接展開(kāi)成3 位一組二進(jìn)制數(shù)即可,然后去掉整數(shù)最高位的0和小數(shù)最低位的0,例如:(1635

12、.724)8 =(001110011101.111010100)2 = (1110011101.1110101)2 對(duì)于二進(jìn)制數(shù)與十六進(jìn)制數(shù)之間為每4位二進(jìn)制數(shù)對(duì)應(yīng)1位十六進(jìn)制數(shù),當(dāng)二進(jìn)制數(shù)轉(zhuǎn)換為十六進(jìn)制數(shù)時(shí),從小數(shù)點(diǎn)開(kāi)始分別向左或向右按每4位一組劃分,不足4位時(shí)用0填補(bǔ),即可得到等值的十六進(jìn)制數(shù),例如:(110100111.101101)2 = (1A7.B4)16 而十六進(jìn)制數(shù)轉(zhuǎn)換為二進(jìn)制數(shù)時(shí),則直接展開(kāi)成4位一組二進(jìn)制數(shù)即可,然后去掉整數(shù)最高位的0和小數(shù)最低位的0,例如:(3FC7.A4)16=(0011111111000111.10100100)2 = (11111111000111.

13、101001)2四、數(shù)制轉(zhuǎn)換中應(yīng)注意的問(wèn)題 (1)實(shí)數(shù)轉(zhuǎn)換時(shí)應(yīng)將整數(shù)和小數(shù)分別轉(zhuǎn)換,然后再拼接起來(lái)。 (2)基值大的小數(shù)不一定有確定對(duì)應(yīng)的基值小的小數(shù),可能出現(xiàn)無(wú)限循環(huán)或無(wú)限不循環(huán)的小數(shù),例如十進(jìn)制小數(shù)0.6,其等效的二進(jìn)制小數(shù)0.100110011001,為一無(wú)限循環(huán)小數(shù),應(yīng)按精度要求取相應(yīng)位數(shù)。 (3)不同進(jìn)位計(jì)數(shù)制可分別用后綴來(lái)標(biāo)注,B表示二進(jìn)制數(shù),Q表示八進(jìn)制數(shù),H表示十六進(jìn)制數(shù),D或缺省則表示十進(jìn)制數(shù)。 例如: 139D = 10001011B= 213Q = 8BH第三節(jié) 帶符號(hào)二進(jìn)制數(shù)的表示方法一、機(jī)器數(shù)與真值 帶符號(hào)二進(jìn)制數(shù)在計(jì)算機(jī)內(nèi)部如何表示呢,通常將數(shù)的符號(hào)數(shù)碼化,即用0表

14、示“+ ”,用1表示“- ”, 例如: 數(shù)(-1101)2 是機(jī)器數(shù)(11101)2 的真值; 而數(shù)(+1011)2 則是(01011)2 的真值。二、原碼表示法 X 1 X0 原碼定義 X原= 1 X - 1 X0 由原碼定義可以看出,任何大于0 的數(shù)的原碼就是符號(hào)位為0,尾數(shù)為真值本身;小于0 的數(shù)的原碼符號(hào)位為1,尾數(shù)仍為真值本身,從真值求原碼就是正數(shù)前加符號(hào)0,負(fù)數(shù)前加符號(hào)1即可。例如: X = + 0. 1011, X原= 0. 1011 X = - 0. 1011, X原= 1. 1011 三、補(bǔ)碼表示法 原碼表示通俗易懂,而且與真值間轉(zhuǎn)換很簡(jiǎn)單。但是用原碼表示時(shí)加/減運(yùn)算很不方便

15、。例如,當(dāng)A 、B 兩數(shù)相加時(shí),還要視其同號(hào),還是異號(hào)。若同號(hào),則數(shù)值相加,結(jié)果符號(hào)不變;如果兩數(shù)異號(hào),則實(shí)際做減法,并判斷兩數(shù)的絕對(duì)值,讓絕對(duì)值大的數(shù)減去絕對(duì)值小的數(shù),其結(jié)果符號(hào)與絕對(duì)值大的數(shù)相同。在整個(gè)操作中費(fèi)時(shí)、費(fèi)設(shè)備。為了解決這些矛盾,人們尋求一種補(bǔ)碼表示法。 1.補(bǔ)碼的概念和定義 補(bǔ)碼是根據(jù)同余的概念提出來(lái)的，例如： 8 4 = 8 6 (mod 10) 11 2 = 11 10 (mod 12) 其中10和12稱(chēng)為模數(shù),在相應(yīng)模數(shù)下等號(hào)兩邊余數(shù)是相同的,當(dāng)以10為模時(shí)84可以用86來(lái)計(jì)算,6就是以10為模4的補(bǔ)碼。同樣10就是以12為模2的補(bǔ)碼。 對(duì)于小于1 的二進(jìn)制數(shù)的補(bǔ)碼定義如

16、下: X 0 X 1 原碼定義 X補(bǔ)= (mod 2) 2 X - 1 X 0或?qū)懗赏嗍? X補(bǔ)= X(mod 2) 2. 補(bǔ)碼的轉(zhuǎn)換 (1)由真值求補(bǔ)碼。根據(jù)補(bǔ)碼的定義,任何正數(shù)的補(bǔ)碼就是真值本身;負(fù)數(shù)的補(bǔ)碼按其定義為： X補(bǔ) = 2 + X X = - 0. X1 X2 Xn X補(bǔ) = 10.00000 + (- 0. X1 X2 Xn) = 1.11111 + 0.00001 0.X1 X2 Xn = 1. X1 X2 Xn + 0.00001 其中 1 = +2-n 從而得到由負(fù)數(shù)值求補(bǔ)碼的方法:符號(hào)位為1,尾數(shù)各位取反(0變1,1變0), 在末位加1(簡(jiǎn)稱(chēng)除符號(hào)位外求反加1)就是X

17、補(bǔ)。 (2)由原碼求補(bǔ)碼。由原碼和補(bǔ)碼的定義可知,正數(shù)的原碼和補(bǔ)碼相同,就是真值的表示。 對(duì)于負(fù)數(shù)X,當(dāng)X = - 0. X1 X2 Xn X原= 1. X1 X2 Xn X補(bǔ)= 2 + X = 2 - 0. X1 X2 Xn = 1 + (1 - 0. X1 X2 Xn) = 1 + (0. X1 X2 Xn + 0.00001) 這個(gè)結(jié)果表明任何負(fù)數(shù)的補(bǔ)碼X補(bǔ)等于它的原碼除符號(hào)位以外各位“求反加1” (3)由一個(gè)數(shù)的補(bǔ)碼表示求其負(fù)數(shù)的表示 這是實(shí)現(xiàn)補(bǔ)碼減法運(yùn)算的基礎(chǔ)。若X補(bǔ)= 0. X1 X2 Xn 則X原= 0. X1 X2 Xn -X= - 0. X1 X2 Xn -X補(bǔ)= 1. X1

18、 X2 Xn + 2-n若X補(bǔ)= 1. X1 X2 Xn 則X原= 1. X1 X2 Xn + 2-n -X = -(0. X1 X2 Xn + 2-n) -X補(bǔ)= 0. X1 X2 Xn + 2-n 結(jié)論:對(duì)絕對(duì)值小于1 的任何正、負(fù)數(shù)X,通過(guò)對(duì)X補(bǔ)連同符號(hào)位一起“求反加1”便可得到-X補(bǔ),稱(chēng)-X補(bǔ)為X補(bǔ)的機(jī)器負(fù)數(shù),由X補(bǔ)求-X補(bǔ)的過(guò)程稱(chēng)為對(duì)X補(bǔ)求-X的補(bǔ)碼。 3.補(bǔ)碼的性質(zhì) (1)若用X0 表示符號(hào)位,則有 1 X 0 (2)真值0在補(bǔ)碼表示中是唯一的。 +0補(bǔ) = 0.0000 -0補(bǔ) = 10.0000 - 0.0000 = 10.0000 = 0.0000(mod2) 即+0補(bǔ)= -

19、0補(bǔ)= 0.0000 4. 補(bǔ)碼的運(yùn)算規(guī)則 X補(bǔ)Y補(bǔ)= XY補(bǔ) 即補(bǔ)碼運(yùn)算結(jié)果仍然是補(bǔ)碼,當(dāng)結(jié)果的最高位有向上進(jìn)位時(shí),丟掉不要,即為正確結(jié)果。 5. 補(bǔ)碼的溢出判斷與變形補(bǔ)碼 當(dāng)兩正數(shù)相加結(jié)果超過(guò)1 或兩負(fù)數(shù)相加結(jié)果超過(guò)-1時(shí),其結(jié)果超出了機(jī)器所能表示數(shù)的范圍,則產(chǎn)生溢出錯(cuò)誤,為能正確判斷其溢出錯(cuò)誤常采用變形補(bǔ)碼,即采用兩位符號(hào)位。 X 1 X0 X補(bǔ) = (mod4) 4 + X 0 X-1 例如: X = 0.101101 X補(bǔ)= 00. 101101 X = - 0.101101 X補(bǔ)= 11. 010011 當(dāng)兩數(shù)運(yùn)算結(jié)果符號(hào)位相異時(shí),則產(chǎn)生溢出,結(jié)果符號(hào)= 01為正溢出,結(jié)果符號(hào)=

20、10為負(fù)溢出。 例如: X = 0.1101，Y = 0.1010,求X + Y補(bǔ)。 X補(bǔ)= 00.1101, Y補(bǔ)= 00.1010 X補(bǔ)Y補(bǔ)= 01.0111, 產(chǎn)生正溢出。四、反碼表示法 在補(bǔ)碼表示中,如果只求反末位不加1,就得到了另一種機(jī)器數(shù)表示法反碼表示法?？蓮难a(bǔ)碼的定義推出反碼的定義為： X 1 X0 X反= (mod2 - 2-n) (22-n)X 0 X -1 其中,n為尾數(shù)的位數(shù)。 在反碼表示中0的表示不是唯一的,+0反= 0.0000,而-0反= 1.1111。 反碼的運(yùn)算規(guī)則為： X反 Y反= XY 結(jié)果為反碼,如果結(jié)果的最高位有向上的進(jìn)位,則應(yīng)加到結(jié)果的末位,即循環(huán)進(jìn)位

21、,才能得到正確結(jié)果。第四節(jié) 數(shù)的定點(diǎn)與浮點(diǎn)表示法一、數(shù)的定點(diǎn)表示法 定點(diǎn)數(shù)是各種數(shù)據(jù)表示中最簡(jiǎn)單,最基本的一種數(shù)據(jù)表示形式,它用于表示二進(jìn)制形式具有固定比例換算的量。在定點(diǎn)表示中約定機(jī)器中所有數(shù)據(jù)的小數(shù)點(diǎn)位置是固定不變的,因而小數(shù)點(diǎn)就不必要再使用記號(hào)表示。 1. 定點(diǎn)小數(shù)格式 小數(shù)點(diǎn)位置固定在最高有效數(shù)位的左邊。任一定點(diǎn)小數(shù)表示為： N = Ns. N -1 N -2 N -3 N -m (m 為數(shù)據(jù)位數(shù))在計(jì)算機(jī)中的表示形式為： Ns . N-1 N-2 N-3 N-m 符號(hào)位 小數(shù)點(diǎn) 數(shù)值部分（尾數(shù)） 2. 定點(diǎn)整數(shù)格式 小數(shù)點(diǎn)固定在最低數(shù)據(jù)位的右邊,任一定點(diǎn)整數(shù)表示為：N = Ns Nm

22、-1 Nm-2 Nm-3 N2 N1 N0 (其中m 為數(shù)據(jù)位數(shù))在計(jì)算機(jī)中整數(shù)表示形式為： . 符號(hào)位 數(shù)值部分（尾數(shù)） 小數(shù)點(diǎn) 定點(diǎn)數(shù)可以表示為帶符號(hào)數(shù)或不帶符號(hào)數(shù)。表示算術(shù)操作數(shù)時(shí),應(yīng)用帶符號(hào)的數(shù),一般以左邊最高位表示符號(hào)位。不帶符號(hào)的數(shù)一般表示邏輯量或某些特征值。N0N1N2Nm-2Nm-1Ns二、浮點(diǎn)表示法 一個(gè)數(shù)N 的浮點(diǎn)形式可表示為： N = MREm 其中,M(Mantissa)表示尾數(shù),E(Exponent)表示階碼,Rm (Radix)表示基數(shù)。Rm 一般為2、8、16等,由于Rm 是常數(shù),不需在數(shù)碼中表示出來(lái),故浮點(diǎn)數(shù)只需用一對(duì)定點(diǎn)數(shù)表示。 一個(gè)尾數(shù)是M,在浮點(diǎn)表示中尾數(shù)

23、通常為規(guī)格化的純小數(shù),即： | M | 1/Rm 另一個(gè)是階碼,通常是整數(shù)。 浮點(diǎn)數(shù)在計(jì)算機(jī)中的表示形式為： 階符 階碼 數(shù)符 小數(shù)點(diǎn) 尾數(shù) . 小數(shù)點(diǎn)EnE2E1EsN-mN-2N-1.Ns尾數(shù)階碼數(shù)符第五節(jié) 字符編碼 1. ASCII碼 ASCII碼是美國(guó)信息交換標(biāo)準(zhǔn)代碼。 ASCII碼是用7位二進(jìn)制碼編碼的,故可表示字符 27 = 128 其中包括:10 個(gè)十進(jìn)制數(shù)(09), 52個(gè)大、小寫(xiě)英文字母(AZ，az), 32個(gè)通用控制字符,34個(gè)專(zhuān)用字符。 我國(guó)標(biāo)準(zhǔn)“信息交換用的七位編碼字符集80GB1988”規(guī)定了信息處理交換用的圖形字符和控制字符共128個(gè),每個(gè)字符用7位二進(jìn)制數(shù)碼進(jìn)行編

24、碼,與ASCII 碼兼容。 2. 十進(jìn)制數(shù)編碼 在數(shù)字系統(tǒng)中十進(jìn)制數(shù)也是應(yīng)用二進(jìn)制數(shù)編碼的，即二進(jìn)制編碼的十進(jìn)制數(shù)，其中應(yīng)用最廣泛的是ASCII碼和BCD碼，ASCII碼的十進(jìn)制數(shù)主要用于非數(shù)值計(jì)算，它們所表示的數(shù)串可以作為字符串來(lái)運(yùn)算或操作。作為十進(jìn)制數(shù)進(jìn)行算術(shù)運(yùn)算則采用BCD碼。 ASCII碼十進(jìn)制數(shù)是用一個(gè)字節(jié)來(lái)表示的，09等10個(gè)數(shù)字用ASCII碼字符集中3039(十六進(jìn)制數(shù))10個(gè)編碼表示。BCD 碼是用二進(jìn)制編碼的十進(jìn)制數(shù)碼(通常用8421 有權(quán)碼),每?jī)蓚€(gè)十進(jìn)制數(shù)占一個(gè)字節(jié)，稱(chēng)為壓縮十進(jìn)制數(shù)串，其符號(hào)則用BCD碼中的冗余碼來(lái)表示，如用10、12、14 或15表示“”；用11或13

25、表示“”。 對(duì)于BCD 碼表示的十進(jìn)制數(shù)在進(jìn)行加/ 減運(yùn)算時(shí)要考慮修正問(wèn)題,對(duì)8421 編碼的十進(jìn)制數(shù),其修正方法是:當(dāng)兩十進(jìn)制數(shù)相加結(jié)果小于等于9 時(shí),不修正;當(dāng)結(jié)果大于9 或產(chǎn)生向高位進(jìn)位時(shí),均加6 修正,以得到正確結(jié)果。例如: X = 358 Y = 9298421 碼表示為： X = 0011 0101 1000 Y = 1001 0010 1001先按二進(jìn)制數(shù)運(yùn)算規(guī)則計(jì)算: 0011 0101 1000 ）1001 0010 1001 1100 1000 1 0001修正結(jié)果 ）0110 0000 0110 1 0010 1000 0111 其中個(gè)位和有向十位進(jìn)位，個(gè)位和需修正，百位

26、和大于9，亦需進(jìn)行修正得到正確結(jié)果。 X + Y = 1287 3. 漢字編碼 為了能在各個(gè)處理環(huán)節(jié)中方便和確切地表示漢字,在漢字系統(tǒng)中要涉及到各種漢字代碼，包括：漢字輸入碼、漢字交換碼、漢字機(jī)內(nèi)碼以及漢字輸出碼等。 (1)漢字輸入碼：漢字輸入碼是將漢字的不同編碼規(guī)則通過(guò)鍵盤(pán)或其他設(shè)備，以編碼形式輸入計(jì)算機(jī)。漢字輸入計(jì)算機(jī)可以通過(guò)圖像識(shí)別、漢字語(yǔ)音識(shí)別、漢字編碼輸入和非編碼輸入等方法。如電報(bào)明碼、國(guó)標(biāo)區(qū)位碼、整字輸入、字元編碼、筆形編碼、拼音編碼等，可通過(guò)標(biāo)準(zhǔn)鍵盤(pán)擊鍵輸入。 (2)漢字機(jī)內(nèi)碼：漢字編碼輸入到計(jì)算機(jī)系統(tǒng)后，要將其轉(zhuǎn)換成計(jì)算機(jī)內(nèi)部表示漢字的機(jī)內(nèi)碼，按照程序的要求，控制計(jì)算機(jī)對(duì)機(jī)內(nèi)碼

27、進(jìn)行加工處理。 (3)漢字交換碼：漢字交換碼是用于不同的漢字系統(tǒng)之間交換漢字信息的。中華人民共和國(guó)國(guó)家標(biāo)準(zhǔn)信息交換用漢字字符集GB 2312-80，共收錄一級(jí)漢字3755個(gè)，二級(jí)漢字3008個(gè)，各種圖形符號(hào)682個(gè)，共計(jì)7445個(gè)。GB 2312-80規(guī)定每個(gè)漢字、圖形符號(hào)都用兩個(gè)字節(jié)表示，每個(gè)字節(jié)7位二進(jìn)制代碼，與94個(gè)可打印字符(除空格外)的ASCII字符取值范圍相同，GB 13000大字符集則收錄了10902 個(gè)漢字與字符，符合國(guó)際肆八位編碼字符集。 漢字交換碼還用區(qū)位碼。區(qū)位碼由4位數(shù)字組成，前兩位是區(qū)號(hào)0194，后兩位是位號(hào)0194。區(qū)位碼是把圖形符號(hào)分為94個(gè)區(qū)(行)，每個(gè)區(qū)又分為

28、94 位(列)，并分別標(biāo)出區(qū)號(hào)、位號(hào)來(lái)表示漢字的編碼。當(dāng)一個(gè)漢字在表中的位置確定之后，就能從縱、橫坐標(biāo)上找到它的相應(yīng)區(qū)號(hào)與位號(hào)，區(qū)號(hào)、位號(hào)連接起來(lái)就構(gòu)成區(qū)位碼。 (4)漢字輸出碼：漢字信息加工處理后的結(jié)果如以漢字形式輸出，則又應(yīng)將漢字機(jī)內(nèi)碼再轉(zhuǎn)換成漢字交換碼或直接變換成漢字地址碼，按這些地址從漢字庫(kù)中取出漢字字形存儲(chǔ)碼，根據(jù)輸出設(shè)備的要求再轉(zhuǎn)換成字形輸出碼，供顯示或打印。漢字字形存儲(chǔ)碼是每一個(gè)漢字信息的字形點(diǎn)陣碼。如用1616點(diǎn)陣，則每一個(gè)漢字字形碼為32B;如用2424點(diǎn)陣，則每一個(gè)漢字字形碼為72B。第六節(jié) 可靠性編碼 為了減少代碼在形成或傳輸過(guò)程中可能產(chǎn)生的錯(cuò)誤,人們常采用一些可靠的編碼

29、方法,它使代碼本身具有一種特征或能力,使代碼在形成過(guò)程中不易出錯(cuò),即使出錯(cuò)也容易發(fā)現(xiàn),或能確定出錯(cuò)的位置并予以糾正。 目前,常用的可靠性編碼有格雷(Gray)碼、奇偶校驗(yàn)碼、漢明校驗(yàn)碼和循環(huán)冗余校驗(yàn)碼等。一、格雷(Gray)碼 Gray碼有多種形式,但它們都有一個(gè)共同特點(diǎn),即從一個(gè)代碼變換為相鄰的另一代碼時(shí),只有一位發(fā)生變化。表1-1 給出了一種典型的Gray碼。表1-1 典型Gray碼 從表可以看出,任何相鄰的十進(jìn)制數(shù),它們的Gray碼都僅有1 位不同。 例如,7到8,二進(jìn)制碼是0111到1000，4位均發(fā)生變化,而Gray碼是0100到1100,只有1位發(fā)生變化。 如在二進(jìn)制碼做加1計(jì)數(shù)時(shí)

30、,從7到8，4位都要發(fā)生變化,當(dāng)4 位變化不是同時(shí)發(fā)生時(shí),在計(jì)數(shù)過(guò)程中就可能出現(xiàn)計(jì)數(shù)錯(cuò)誤,Gray 碼是從編碼的形式上杜絕了出現(xiàn)這種錯(cuò)誤的可能。 Gray碼與二進(jìn)制碼之間有簡(jiǎn)單的轉(zhuǎn)換關(guān)系,設(shè)二進(jìn)制碼為: B = Bn Bn-1 B1 B0其對(duì)應(yīng)的Gray 碼為 G = Gn Gn-1 G1 G0則有 Gn = Bn Gi = Bi+1 Bi (i n)式中i = 0,1,2,n-1;“ ”符號(hào)表示異或運(yùn)算或模2加運(yùn)算。 反過(guò)來(lái),如果已知Gray 碼,也可以用類(lèi)似的方法求出對(duì)應(yīng)的二進(jìn)制碼,其方法如下: Bn = Gn Bi = Bi+1Gi (i n) 例如,把二進(jìn)制碼0111和1100轉(zhuǎn)換成G

31、ray碼;把Gray碼0100和1010轉(zhuǎn)換成二進(jìn)制碼：二、奇偶校驗(yàn)碼 二進(jìn)制代碼在傳輸、存儲(chǔ)過(guò)程中,可能會(huì)發(fā)生錯(cuò)誤,即有的1錯(cuò)成了0或有的0錯(cuò)成了1,奇偶校驗(yàn)碼具有發(fā)現(xiàn)這種錯(cuò)誤的能力。 奇偶校驗(yàn)碼由兩部分組成,即由信息位和校驗(yàn)位組成。信息位就是要傳輸?shù)男畔⒈旧?可以是位數(shù)不限的二進(jìn)制代碼,例如并行傳輸?shù)?421BCD 碼,信息位就是4 位,校驗(yàn)位是附加的冗余位,奇偶位僅1 位。 1.奇偶校驗(yàn)碼的編碼方法 在信息的發(fā)送端根據(jù)信息位1的個(gè)數(shù)配成奇數(shù)個(gè)1,構(gòu)成奇校驗(yàn);若信息位1的個(gè)數(shù)配成偶數(shù)個(gè)1,則構(gòu)成偶校驗(yàn)。 一般來(lái)說(shuō),對(duì)于任何n位二進(jìn)制信息碼,只要增加1位校驗(yàn)位,便可構(gòu)成(n+1)位的奇或偶校

32、驗(yàn)碼。設(shè)奇偶校驗(yàn)碼為 C1 C2 C3 Cn P則校驗(yàn)位P可以表示為 P = C1 C2 C3 Cn (對(duì)偶校驗(yàn)碼) 或 P = C1 C2C3Cn1 (對(duì)奇校驗(yàn)碼) 2.奇偶校驗(yàn)碼的校驗(yàn)方法 在發(fā)送端對(duì)信息碼進(jìn)行編碼后,將信息位和校驗(yàn)位構(gòu)成的奇(或偶)校驗(yàn)碼一起發(fā)送出去,在接收端對(duì)接收到的編碼按發(fā)送端對(duì)信息碼的編碼方法進(jìn)行校驗(yàn)碼生成,得到新的校驗(yàn)碼P,與接收到的P相比較,相同為傳送正確,相異則說(shuō)明傳送有錯(cuò)。則校驗(yàn)位P可以表示為： P= C1 C2 C3 Cn (對(duì)偶校驗(yàn)碼)或 P= C1 C2 C3 Cn1 (對(duì)奇校驗(yàn)碼)校正子 S = P + P 當(dāng) S = 0時(shí),說(shuō)明傳送正確; 當(dāng) S

33、= 1時(shí),說(shuō)明傳送錯(cuò)誤。 奇偶校驗(yàn)碼能發(fā)現(xiàn)代碼1位(或奇1個(gè)數(shù)位)出錯(cuò),但它不能發(fā)現(xiàn)2位(或偶數(shù)個(gè)數(shù)位)出錯(cuò)。由于2位出錯(cuò)的概率遠(yuǎn)低于1位出錯(cuò)的概率,所以奇偶校驗(yàn)碼用來(lái)檢測(cè)代碼在傳送過(guò)程中的錯(cuò)誤是很有效的。 實(shí)現(xiàn)奇偶校驗(yàn)只需要在發(fā)送端增加一個(gè)奇偶形成電路和在接收端增加一個(gè)奇偶校驗(yàn)電路就可以了。其原理框圖如圖1 - 1 所示。圖1-1 BCD碼奇偶校驗(yàn)原理框圖 三、漢明校驗(yàn)碼 奇偶校驗(yàn)碼只能發(fā)現(xiàn)代碼1位(或奇數(shù)個(gè)數(shù)位)出錯(cuò),但不能定位出錯(cuò)位置,因而就不能糾正錯(cuò)誤,漢明校驗(yàn)碼是由Richard Hamming 提出的,它實(shí)際上是一種多重奇偶校驗(yàn),即將代碼按照一定規(guī)則組織為若干小組,分組進(jìn)行奇偶校驗(yàn)

34、,各組的校驗(yàn)信息組成一個(gè)指誤字,通過(guò)指誤字不僅可以檢測(cè)是否出錯(cuò),而且在1 位出錯(cuò)的情況下能進(jìn)行錯(cuò)誤定位并能糾正錯(cuò)誤。 1. 漢明碼的編碼方法 漢明碼也是由信息位和校驗(yàn)位構(gòu)成的,但校驗(yàn)位有多位。且要滿足如下漢明不等式: 2r k + r + 1 其中,k是信息位數(shù),r是校驗(yàn)位數(shù)。漢明校驗(yàn)是奇偶校驗(yàn)的擴(kuò)充,各校驗(yàn)位都是由奇偶校驗(yàn)方程產(chǎn)生的,可以由奇校驗(yàn)方程產(chǎn)生,也可以由偶校驗(yàn)方程產(chǎn)生。 設(shè)需傳送的信息碼為4位二進(jìn)制碼,即 M = a1 a2 a3 a4 為了實(shí)現(xiàn)漢明校驗(yàn),按漢明不等式則需要增加3位校驗(yàn)位b1、b2、b3 ,稱(chēng)它們?yōu)闈h明奇偶校驗(yàn)位。分別設(shè)置在2i碼位上(i = 0,1,2),即b1置

35、于20 =1碼位上,b2置于21 =2碼位上,b3置于22 =4碼位上。校驗(yàn)位的取值由下列表達(dá)式求得(對(duì)偶校驗(yàn))： b1 = a1 a2 a4 b2 = a1 a3 a4 b3 = a2 a3 a4 將校驗(yàn)位b1、b2、b3 分別置于相應(yīng)碼位上,就完成了漢明碼的編碼,即： n = b1 b2 a1 b3 a2 a3 a4 生成校驗(yàn)位的方程為r個(gè),每一信息位至少參加到兩個(gè)校驗(yàn)方程中,某一信息位出錯(cuò),則引起多位校驗(yàn)位出錯(cuò),產(chǎn)生的指誤字就可以確定出錯(cuò)位置。 例如: k = 1011 b1 = 1 0 1 = 0 b2 = 1 1 1 = 1 b3 = 0 1 1 = 0 n = 0110011 2.

36、漢明碼的校驗(yàn)方法 在發(fā)送端將編碼好的漢明碼發(fā)送出去后,在接收端根據(jù)接收到的信息碼和校驗(yàn)碼進(jìn)行檢錯(cuò)和糾錯(cuò)。在接收端根據(jù)下列校驗(yàn)方程生成指誤字或錯(cuò)誤模式(對(duì)偶校驗(yàn))。 S1 = b1 a1 a2 a4 S2 = b2 a1 a3 a4 S3 = b3 a2 a3 a4 根據(jù)求得的S1 S2 S3 的值就能夠檢測(cè)錯(cuò)誤和錯(cuò)誤定位。 如果接收到的代碼是正確的,則 S3 S2 S1 = 000 如果接收到的代碼有錯(cuò)誤(假設(shè)只有1位錯(cuò)),則S3 S2 S1 的值就是出錯(cuò)碼位,只要將該位取反即可。例如:發(fā)送的代碼為： n = 0110011但接收的代碼為： n = 0110010指誤字為： S3 S2 S1

37、= 111說(shuō)明第7 位出錯(cuò),將其取反就得到正確代碼0110011。四、循環(huán)冗余校驗(yàn)碼 循環(huán)冗余校驗(yàn)(Cyclic Redundancy Check,CRC)是目前在磁表面存儲(chǔ)器中應(yīng)用最廣泛的一種校驗(yàn)方法,也是網(wǎng)絡(luò)和多機(jī)通信中常用的校驗(yàn)方法。它所約定的校驗(yàn)規(guī)則是:讓校驗(yàn)碼能為某一約定代碼除盡;如果除得盡,表明代碼正確,如果除不盡,余數(shù)將指明出錯(cuò)位所在位置。 任意一串?dāng)?shù)碼,很可能除不盡,將產(chǎn)生一個(gè)余數(shù)。如果讓被除數(shù)減去余數(shù),勢(shì)必能為約定除數(shù)所除盡。但減法操作可能需要借位運(yùn)算,難于用簡(jiǎn)單的拼裝方法實(shí)現(xiàn)編碼。因此采用一種模2運(yùn)算,即通過(guò)模2減實(shí)現(xiàn)模2除,以模2加將所得余數(shù)拼接在被除數(shù)后面,形成一個(gè)能除

38、盡的校驗(yàn)碼。當(dāng)然,對(duì)除數(shù)的選擇是有條件的。模2運(yùn)算是一種以按位加/ 減為基礎(chǔ)的四則運(yùn)算,不考慮進(jìn)位和借位。它是一種按位加/ 減或異或運(yùn)算,可用異或門(mén)實(shí)現(xiàn)。 待編碼的信息是一串代碼,可能是表示數(shù)值大小的數(shù)字,也可能是字符編碼,或其他性質(zhì)的代碼。在模2除中,暫將它視為數(shù)字,可用多項(xiàng)式來(lái)描述?，F(xiàn)定義待編信息(被除數(shù))為M(x);約定的除數(shù)為G(x),因?yàn)樗怯脕?lái)產(chǎn)生余數(shù)的,所以G(x)又稱(chēng)為生成多項(xiàng)式;所以產(chǎn)生的余數(shù)R(x),它相當(dāng)于所配的冗余校驗(yàn)位。 M(x)= Q(x)G(x)+ R(x) M(x)- R(x)= Q(x)G(x) 顯然,將M(x)減去余數(shù)R(x),就必定能為G(x)所除盡。因而

39、可以設(shè)想讓M(x)- R(x)作為編好的校驗(yàn)碼送往輔助存儲(chǔ)器。當(dāng)從輔助存儲(chǔ)器取得校驗(yàn)碼時(shí),仍用約定的多項(xiàng)式G(x)去除,若余數(shù)為0,表明該校驗(yàn)碼正確;若余數(shù)不為0,表明有錯(cuò)。再進(jìn)一步由余數(shù)確定是哪一位出錯(cuò),以便糾正。 1. 編碼方法 (1)將待編碼的k 位有效信息碼組表達(dá)為多項(xiàng)式M(x)。 M(x)= Ck-1xk-1 +Ck-2xk-2 + + Cixi + + C1x + C0 式中Ci = 0或1。 (2)將M (x)左移r 位,得M(x)xr。這樣做的目的是空出r 位,以便拼裝r 位余數(shù)(即校驗(yàn)位)。 (3)用r +1 位的生成多項(xiàng)式G(x),對(duì)M(x)xr 做模2除。 要產(chǎn)生r 位余

40、數(shù),所以除數(shù)應(yīng)為r +1 位。 M(x)xr/G(x) = Q(x)+ R(x)/G(x) (模2 除) (4)將左移r 位的待編有效信息與余數(shù)R(x)做模2 加(減),即拼接為循環(huán)校驗(yàn)碼。M(x)xr + R(x)= Q(x)G(x)+ R(x)+ R(x)= Q(x)G(x) (模2加) 兩個(gè)相同數(shù)的模2和為0,所以M(x)xr + R(x)是一個(gè)能被G(x)除盡的數(shù)碼,可作為循環(huán)校驗(yàn)碼,共n = k + r 位。由于M(x)xr 已經(jīng)空出r 位,所以與R(x)的模2加可由簡(jiǎn)單的拼接來(lái)實(shí)現(xiàn)。 在按位運(yùn)算中,模2加與模2減的結(jié)果是一致的,所以 M(x)xr -R (x)= M(x)xr +R

41、(x) 在本節(jié)中,將M(x)+ R(x)稱(chēng)為循環(huán)校驗(yàn)碼。在許多應(yīng)用中,常只將R(x)部分稱(chēng)為校驗(yàn)碼,簡(jiǎn)寫(xiě)為CRC。 例如,將4 位有效信息1100編成循環(huán)校驗(yàn)碼,選擇生成多項(xiàng)式1011。 M(x)= x3 + x2 , 即1100 (k = 4) M(x)xr = x6 + x5 ,即1100000 (左移r = 3 位) G(x)= x3 + x + 1, 即1011 (r + 1 = 4 位) M(x)x3/G(x) =1100000/1011 =1110 + 010/1011 (模2 除) M(x)x3 + R(x)= 1100000 + 010 = 1100010 (模2 加) 把編好

42、的循環(huán)校驗(yàn)碼稱(chēng)為(7,4)碼,即n = 7,k = 4,出錯(cuò)位之間有著唯一的對(duì)應(yīng)關(guān)系。 2. 譯碼與糾錯(cuò) 將接收到的循環(huán)校驗(yàn)碼,用約定的生成多項(xiàng)式G (x)去除。如果接收代碼無(wú)誤,則余數(shù)R(x)= 0;如果接收代碼某1 位出錯(cuò),則余數(shù)R(x)不為0,不同位出錯(cuò)則余數(shù)不同,余數(shù)代碼與出錯(cuò)位之間有著唯一的對(duì)應(yīng)關(guān)系。 通過(guò)上例可求出其出錯(cuò)模式如表1-2所示,即余數(shù)與出錯(cuò)位序號(hào)之間的對(duì)應(yīng)模式。變更待測(cè)碼字不影響錯(cuò)誤模式,出錯(cuò)模式只與碼制和多項(xiàng)式有關(guān),與碼字代碼無(wú)關(guān)。對(duì)于(7,4)CRC碼,表1-2具有通用性,可作為(7,4)碼的判別依據(jù)。當(dāng)然,對(duì)于其他碼制或選用其他生成多項(xiàng)式,出錯(cuò)模式可能不同。表1-

43、2中列舉了八種情況。一種是正確碼字,除后余數(shù)為0。其余七種是依次有1位出錯(cuò),余數(shù)不為0,與出錯(cuò)位序號(hào)有唯一的對(duì)應(yīng)模式。如果有1位碼字出錯(cuò),用G(x)除后得到一個(gè)不為0的余數(shù),如果對(duì)該余數(shù)補(bǔ)0后繼續(xù)除,各次余數(shù)將按表1-2順序循環(huán)。例如第7位A7出錯(cuò),余數(shù)為001,補(bǔ)0后繼續(xù)除,得余數(shù)010,以后將依次為100、011、110、111、101,然后是001,呈循環(huán)性,故又稱(chēng)循環(huán)碼。表1-2 (7,4)循環(huán)碼的出錯(cuò)模式生成多項(xiàng)式G(x)= 1011 循環(huán)碼可以采用硬件糾錯(cuò)方法,只設(shè)置余數(shù)101的譯碼輸出,對(duì)應(yīng)于第1位出錯(cuò)位置;如果校驗(yàn)后發(fā)現(xiàn)余數(shù)不為0,一邊對(duì)余數(shù)補(bǔ)0繼續(xù)做模2除,同時(shí)將被檢測(cè)碼字循

44、環(huán)左移1位;當(dāng)出現(xiàn)余數(shù)101時(shí),出錯(cuò)位也移至第1位位置,可用異或門(mén)將其變反糾正,或在由第1位移往第7位的途中予以糾正;繼續(xù)移滿一個(gè)循環(huán),即共移7次,將得到一個(gè)糾正后的正確碼字。 3. 生成多項(xiàng)式的選取 從檢錯(cuò)與糾錯(cuò)的要求出發(fā),生成多項(xiàng)式應(yīng)能滿足下列要求:任何一位發(fā)生錯(cuò)誤都應(yīng)使余數(shù)不為0,不同位發(fā)生錯(cuò)誤應(yīng)當(dāng)使余數(shù)不同,應(yīng)滿足余數(shù)循環(huán)規(guī)律。在計(jì)算機(jī)與通信系統(tǒng)中廣泛使用的是下列兩種標(biāo)準(zhǔn): CCITT(國(guó)際電報(bào)電話咨詢(xún)委員會(huì))推薦: G(x)= x16 + x15 + x2 + 1 IEEE(美國(guó)電器和電子工程師協(xié)會(huì))推薦: G(x)= x16 + x12 + x5 + 1第二章 布爾代數(shù)及其邏輯實(shí)現(xiàn)

45、本章內(nèi)容提要第一節(jié) 布爾代數(shù)及其邏輯實(shí)現(xiàn)第二節(jié) 布爾代數(shù)的公式、定理和規(guī)則第三節(jié) 布爾函數(shù)的基本形式第四節(jié) 布爾函數(shù)的代數(shù)化簡(jiǎn)法第五節(jié) 布爾函數(shù)的卡諾圖化簡(jiǎn)法第六節(jié) 布爾函數(shù)的實(shí)現(xiàn)第七節(jié) 多輸出布爾函數(shù)的化簡(jiǎn)與實(shí)現(xiàn)概述 1847 年,英國(guó)數(shù)學(xué)家喬治布爾(George Boole)提出了一個(gè)系統(tǒng)的邏輯處理方法并由此而發(fā)展成一個(gè)代數(shù)體系布爾代數(shù)。布爾代數(shù)是研究開(kāi)關(guān)理論和邏輯設(shè)計(jì)的數(shù)學(xué)基礎(chǔ),已被廣泛應(yīng)用于數(shù)字系統(tǒng)設(shè)計(jì)中。 數(shù)字計(jì)算機(jī)和其他數(shù)字系統(tǒng)大量使用各種各樣的數(shù)字邏輯電路。數(shù)字邏輯電路種類(lèi)很多,為了弄清它們的原理和性能,必須掌握布爾代數(shù)這一數(shù)學(xué)工具。 本章主要介紹布爾代數(shù)的基本概念、基本定理、性

46、質(zhì)、布爾函數(shù)表達(dá)式及其邏輯實(shí)現(xiàn)。第一節(jié) 布爾代數(shù)的基本概念一、布爾變量及其基本運(yùn)算 布爾代數(shù)和普通代數(shù)變量一樣,用字母表示變量,布爾代數(shù)的變量稱(chēng)為布爾變量。由于目前使用的器件通常只有兩個(gè)穩(wěn)定狀態(tài),它的取值只有兩種可能,即取值1或0,故又稱(chēng)二值代數(shù)。計(jì)算機(jī)或其他數(shù)字系統(tǒng)無(wú)論多么復(fù)雜,它們都是由若干種最簡(jiǎn)單的、最基本的電路(如門(mén)電路、觸發(fā)器等)所組成。第一節(jié) 布爾代數(shù)的基本概念 這些電路的工作具有下列基本特點(diǎn):從電路內(nèi)部看,或是開(kāi)關(guān)器件的導(dǎo)通,或是開(kāi)關(guān)器件的截止;從電路的輸入、輸出看,或是電平的高低,或是脈沖的有無(wú)。由于這些電路工作在開(kāi)關(guān)狀態(tài),故稱(chēng)開(kāi)關(guān)電路。開(kāi)關(guān)電路的工作狀態(tài)可以用二值布爾代數(shù)來(lái)描

47、述,且布爾代數(shù)是研究開(kāi)關(guān)理論的,所以又稱(chēng)開(kāi)關(guān)代數(shù)。 研究數(shù)字邏輯電路時(shí),關(guān)心的是電路所完成的邏輯功能,而不是電的或機(jī)械的性能,因此一般只考慮輸入變量和輸出變量之間的邏輯關(guān)系,并用代數(shù)的形式來(lái)描述。輸入信號(hào)A 和B 如果是布爾變量,則輸出信號(hào)便是布爾函數(shù),且可表示為 F = f (A,B) 這種代數(shù)表達(dá)式以理想的形式來(lái)表示實(shí)際的數(shù)字邏輯電路。反映了邏輯電路的特征和功能。因此,它使我們有可能將一個(gè)具體的數(shù)字邏輯電路轉(zhuǎn)換成抽象的代數(shù)表達(dá)式而加以分析研究。 實(shí)際的邏輯關(guān)系是千變?nèi)f化的,但它們都是由或、與、非運(yùn)算組成的,都是通過(guò)這三種基本運(yùn)算來(lái)實(shí)現(xiàn)的。第一節(jié) 布爾代數(shù)的基本概念 1.或運(yùn)算 或運(yùn)算又叫邏

48、輯加。兩個(gè)變量或運(yùn)算的邏輯關(guān)系可表示為F = A + B,式中“+ ”號(hào)是或運(yùn)算符,有時(shí)也用“”來(lái)表示。上式讀作“F 等于A或B”,或者“F等于A加B”。變量A和B中只要有一個(gè)取值為1,則F就為1;若A和B全為0,則F為0。其邏輯關(guān)系可以用真值表來(lái)描述, 如表2 - 1 所示。第一節(jié) 布爾代數(shù)的基本概念表2 - 1 或運(yùn)算第一節(jié) 布爾代數(shù)的基本概念 2.與運(yùn)算 與運(yùn)算又叫邏輯乘。兩個(gè)變量與運(yùn)算的邏輯關(guān)系可表示為F = AB 式中“”號(hào)表示與運(yùn)算符,有時(shí)也用“”來(lái)表示,通常,與運(yùn)算符可以省略。上式讀作“F等于A與B”,或者“F等于A乘B”。只有當(dāng)變量A 與B 都為1時(shí),F才為1;否則,F 就為0

49、,其邏輯關(guān)系可以用真值表表2-2來(lái)描述。第一節(jié) 布爾代數(shù)的基本概念表2 - 2 與運(yùn)算第一節(jié) 布爾代數(shù)的基本概念 3.非運(yùn)算 非運(yùn)算又稱(chēng)邏輯取反。對(duì)一個(gè)變量的非運(yùn)算的邏輯關(guān)系可表示為F = A ,式中符號(hào)“ - ”表示非運(yùn)算符。上式讀作“F 等于A的非”,其意思是若A為1,則F為0;反之,若A為0,則F 為1。非運(yùn)算的邏輯關(guān)系可以用表2-3 所示的真值表來(lái)描述。第一節(jié) 布爾代數(shù)的基本概念表2-3 非運(yùn)算第一節(jié) 布爾代數(shù)的基本概念 通過(guò)以上對(duì)布爾變量及3個(gè)基本運(yùn)算的定義,可以對(duì)布爾代數(shù)下個(gè)定義: 布爾代數(shù)是一個(gè)由布爾變量集K、常量0、1以及或、與、非三種運(yùn)算符所構(gòu)成的代數(shù)系統(tǒng), 記為B = (K

50、,+ ,- ,0,1) 其中,布爾變量集K是指布爾代數(shù)中的所有可能變量的集合,它可用任何字母表示,但每一個(gè)變量的取值只可能為常量0或1。而且,布爾代數(shù)中只有或、與、非三種運(yùn)算。第一節(jié) 布爾代數(shù)的基本概念二、布爾函數(shù)及其表示方法 布爾代數(shù)中的函數(shù)定義與普通代數(shù)中函數(shù)定義十分相似,把布爾函數(shù)與邏輯網(wǎng)絡(luò)聯(lián)系起來(lái),布爾函數(shù)可以這樣敘述:設(shè)某一邏輯網(wǎng)絡(luò)的輸入變量為x1 ,x2 ,xn ,輸出變量為F,如圖2-1 所示。對(duì)應(yīng)于變量x1 ,x2 ,xn的每一組確定值,F就有唯一確定的值,則稱(chēng)F 是變量x1 ,x2 ,xn 的布爾函數(shù)。 記為 F = f(x1 ,x2 ,xn )圖2 - 1 布爾函數(shù)第一節(jié)

51、布爾代數(shù)的基本概念 注意:布爾代數(shù)中函數(shù)的取值也只可能是0或1。這是與普通代數(shù)不同的。 布爾函數(shù)的表示方法有三種形式:布爾表達(dá)式、真值表和卡諾圖。這與普通代數(shù)中用公式、表格和圖解這三種方法來(lái)表示函數(shù)十分類(lèi)似。下面分別說(shuō)明這三種表示方法。第一節(jié) 布爾代數(shù)的基本概念1. 布爾表達(dá)式 布爾表達(dá)式是由布爾變量和或、與、非三種運(yùn)算符所構(gòu)成的式子,這是一種用公式來(lái)表示布爾函數(shù)的方法。 例如,要表示這樣一個(gè)函數(shù)關(guān)系:當(dāng)兩個(gè)變量A 和B 取值相同時(shí),函數(shù)取值為0;否則,函數(shù)取值為1。此函數(shù)稱(chēng)為異或函數(shù),可以用下列布爾表達(dá)式來(lái)表示: F = f(A,B)= B + A 顯然,只要將A和B 的四種可能取值代入這表

52、達(dá)式,驗(yàn)證是正確的。第一節(jié) 布爾代數(shù)的基本概念 真值表是由輸入變量的所有可能取值組合及其對(duì)的輸出函數(shù)值所構(gòu)成的表格,這是一種用表格表示布爾函數(shù)的方法。例如,對(duì)于前面的異或函數(shù)可以用表2-4 所示的真值表來(lái)表示。 2.真值表第一節(jié) 布爾代數(shù)的基本概念 真值表中的變量為兩個(gè),共有22種取值組合,所以該表由4 行組成。當(dāng)變量為n 個(gè)時(shí),真值表就由2n 行組成。顯然,隨著變量數(shù)目的增加,真值表的行數(shù)將急劇增加。因此,一般當(dāng)變量數(shù)目不超過(guò)4 個(gè)時(shí),用真值表表示函數(shù)比較方便。表2 - 4 異或運(yùn)算第一節(jié) 布爾代數(shù)的基本概念 例如,已知下列兩個(gè)函數(shù) F = xy ， G = x + y 列出F 和G 的真值

53、表,如表2-5所示。由表可知,它們的真值表完全相同,故F 和G 是相等的,即有： xy = x + y表2 - 5 F = xy和G = x + y 的真值表第一節(jié) 布爾代數(shù)的基本概念第二節(jié) 布爾代數(shù)的公式、定理和規(guī)則 根據(jù)布爾變量的取值只有0和1以及布爾變量?jī)H有的三種運(yùn)算的定義,不難推出下列基本公式:交換律 A + B = B + A (2.1.1) AB = BA (2.1.2)結(jié)合律 (A + B)+ C = A + (B + C) (2.2.1) (AB)C = A(BC) (2.2.2)一、布爾代數(shù)的基本公式分配律 A(B + C)= AB + AC (2.3.1) A + BC =

54、 (A + B)(A + C) (2.3.2)0-1 律 A + 1 = 1 (2.4.1) A + 0 = A (2.5.1) A 1 = A (2.4.2) A 0 = 0 (2.5.2) 互補(bǔ)律 A + A = 1 (2.6.1) A A = 0 (2.6.2) 等冪律 A + A = A (2.7.1) A A = A (2.7.2) 吸收律 A + A B = A (2.8.1) A(A + B)= A (2.8.2) A + A B = A + B (2.9.1) A( A + B)= A B (2.9.2) 對(duì)合律(雙重否定律) A = A (2.10) 以上是布爾代數(shù)的基本公式

55、。其中式(2.1.1)(2.6.1)、式(2.1.2)(2.6.2)和式(2.10)可以作為布爾代數(shù)的公理。公理是代數(shù)系統(tǒng)的基本出發(fā)點(diǎn),是客觀存在的抽象,它無(wú)需證明,但它可以用客觀存在來(lái)驗(yàn)證。以此為基礎(chǔ),可以推得布爾代數(shù)的其他公式(2.7)(2.9)。 例如,式(2.7.1)的證明如下: A + A = (A + A)1 (0-1律) = (A + A)(A + A) (互補(bǔ)律) = A + A A (分配律) = A + 0 (互補(bǔ)律) = A (0-1律) 又如,式(2.9.1)的證明如下: A + AB =(A + A)(A + B) (分配律) = 1(A + B) (互補(bǔ)律) = A

56、 + B (0-1律) 必須指出,上述基本公式中,有些公式與普通代數(shù)中的相 同,但有些公式卻是布爾代數(shù)中所特有的。這一點(diǎn)請(qǐng)讀者在以后使用中注意。二、布爾代數(shù)的主要定理 定理1 德摩根(De Morgan)定理 (1) x1 + x2 + + xn = x1x2xn (2) x1x2xn = x1 + x2 + + xn 這就是說(shuō),n 個(gè)變量的或的非等于各變量的非的與;n 個(gè)變量的與的非等于各變量的非的或。 當(dāng)變量的數(shù)目較少時(shí),該定理可很容易用真值表證明。當(dāng)變量為n 個(gè)時(shí),則可以用數(shù)學(xué)歸納法證明。 德摩根定理是布爾代數(shù)中一個(gè)很重要且經(jīng)常使用的定理,它提供了一種變換布爾表達(dá)式的簡(jiǎn)便方法。由于它具有

57、反演特性,即把變量的與運(yùn)算改成或運(yùn)算,或運(yùn)算改成與運(yùn)算,所以又稱(chēng)反演律。 定理2 香農(nóng)(Shannon)定理 f(x1,x2,xn ,0,1,+,)=f(x1,x2 ,xn,1,0,+ ) 這就是說(shuō),任何函數(shù)的反函數(shù)(或稱(chēng)補(bǔ)函數(shù)),可以通過(guò)對(duì)該函數(shù)的所有變量取反,并將常量1換為0,0換為1,運(yùn)算符“+ ”換為“”,“”換為“+ ”而得到。 證明:根據(jù)德摩根定理,任何函數(shù)的反函數(shù)可寫(xiě)成 f( x1,x2 ,xn ,0,1,+ ,) =f1(x1,x2,xn,0,1,+ ,)+f2 (x1,x2,xn ,0,1,+ ,) =f1(x1,x2,xn ,0,1,+ ,)f2 (x1,x2,xn ,0,

58、1,+ ,)或?qū)懗?f(x1,x2,xn ,0,1,+ ,) =f1(x1,x2,xn ,0,1,+ ,)f2 (x1,x2,xn ,0,1,+ ,) =f1(x1,x2,xn ,0,1,+ ,)+ f2(x1,x2,xn ,0,1,+ ,) 其中,f1 和f2 是f 的兩個(gè)部分函數(shù)。對(duì)f1 和f2 重復(fù)上述過(guò)程,直到使f 中的每個(gè)變量都用德摩根定理。由于每對(duì)f(或f的部分函數(shù))應(yīng)用一次德摩根定理,就將部分函數(shù)(或子部分函數(shù))取反,并將與、或運(yùn)算變換一次,以求得函數(shù)f (或部分函數(shù))的反函數(shù)。因此,當(dāng)對(duì)每個(gè)變量進(jìn)行德摩根變換后,其結(jié)果必然是f(x1,x2 ,xn,1,0,+ ),證畢。 香農(nóng)定

59、理實(shí)際上是德摩根定理的推廣,它可以用在任何復(fù)雜函數(shù)。 例2-1 已知函數(shù)F =AB + AB(C + D),求其反函數(shù)F。 解: F = AB + AB(C + D)= AB AB(C + D) = (A + B)(AB + C + D)= (A + B)(A + B)+ CD 利用香農(nóng)定理,可以直接寫(xiě)出 F = (A + B)(A + B + CD)三、布爾代數(shù)的重要規(guī)則 布爾代數(shù)有3 個(gè)重要規(guī)則,即代入規(guī)則、反演規(guī)則和對(duì)偶規(guī)則,現(xiàn)分別敘述如下。 1. 代入規(guī)則 任何一個(gè)含有變量X 的等式,如果將所有出現(xiàn)X 的位置,都代之以一個(gè)布爾函數(shù)F,則等式仍然成立。這個(gè)規(guī)則稱(chēng)為代入規(guī)則。 由于任何一個(gè)

60、布爾函數(shù)和任何一個(gè)變量一樣,只有0或1兩種取值,顯然,以上規(guī)則是成立的。 例2-2 已知等式A + B = AB,函數(shù)F = B + C,若用F 代入此等式中的B,則有: A + (B + C)= AB + C A + (B + C)= ABC 據(jù)此可以證明n 變量的德摩根定理的成立。 2. 對(duì)偶規(guī)則 任何一個(gè)布爾函數(shù)表達(dá)式F,如果將表達(dá)式中的所有的“+ ”改成“”,“”改成“+ ”,1改成0,0改成1,而變量保持不變,則可得到一個(gè)新的函數(shù)表達(dá)式Fd ,稱(chēng)Fd 為F 的對(duì)偶函數(shù)。這一規(guī)則稱(chēng)為對(duì)偶規(guī)則。例如,下列為幾個(gè)原函數(shù)及其對(duì)偶函數(shù): F = A B + ABC Fd = (A + B)(A