計(jì)算機(jī)中的邏輯運(yùn)算與邏輯部件.ppt

第三章計(jì)算機(jī)中的邏輯運(yùn)算與邏輯部件,本章基本要求：1.掌握邏輯運(yùn)算的基本概念、規(guī)則；2.掌握用真值表、邏輯表達(dá)式、卡諾圖這三種邏輯函數(shù)表示方法；3.了解計(jì)算機(jī)內(nèi)常用邏輯器件：基本門(mén)電路、三態(tài)門(mén)、觸發(fā)器、寄存器、計(jì)數(shù)器、譯碼器的基本功能及作用；4.了解計(jì)算機(jī)在傳輸數(shù)據(jù)時(shí)常用的校驗(yàn)方法：奇、偶校驗(yàn)方法與CRC校驗(yàn)方法,3.1邏輯代數(shù)與基本邏輯運(yùn)算,邏輯代數(shù)是1847年由英國(guó)數(shù)學(xué)家喬治布爾（GeorgeBoole)首先創(chuàng)立的，所以通常人們又稱(chēng)邏輯代數(shù)為布爾代數(shù)。邏輯代數(shù)與普通代數(shù)有著不同的概念，其所表示的不是數(shù)值之間的大小關(guān)系，而是邏輯函數(shù)與邏輯變量之間所存在的邏輯關(guān)系與邏輯規(guī)律。邏輯規(guī)律表示了一種因果關(guān)系，如“真”與“假”、“有”和“無(wú)”、“是”與“非”、“開(kāi)”與“關(guān)”等，這些邏輯關(guān)系的一個(gè)共同點(diǎn)是它們僅有兩種狀態(tài)，即：0和1，因此又稱(chēng)為二值邏輯。,它們通常反映在邏輯電路上則是電路的“通”與“斷”、反映在電信號(hào)上則是信號(hào)電平的“髙”與“低”，所以把這種工作在二值（0、1）狀態(tài)下的電路稱(chēng)為數(shù)字邏輯電路。邏輯代數(shù)是分析和設(shè)計(jì)數(shù)字邏輯系統(tǒng)的數(shù)學(xué)基礎(chǔ)，而數(shù)字邏輯電路則是構(gòu)成計(jì)算機(jī)硬件核心電路的主要部分。邏輯代數(shù)是指：用0和1兩個(gè)基本的數(shù)字符號(hào)表示邏輯常量，用取值只能為0或1的任何字母符號(hào)表示邏輯變量，用“與”、“或”、“非”等基本邏輯符號(hào)表示運(yùn)算關(guān)系所構(gòu)成的代數(shù)系統(tǒng)。邏輯代數(shù)的自變量取值只有0和1（非0即1）兩個(gè)數(shù)，同樣邏輯函數(shù)的取值也只有0和1（非0即1）兩個(gè)數(shù)，自變量就是邏輯變量，這種函數(shù)就是邏輯函數(shù)。,3.1.1基本邏輯門(mén)電路,邏輯門(mén)是描述數(shù)字邏輯電路的最基本單元部件，是計(jì)算機(jī)硬件電路的基礎(chǔ)；由于它的結(jié)構(gòu)與邏輯函數(shù)中描述的自變量乘積項(xiàng)及函數(shù)邏輯關(guān)系相對(duì)應(yīng)，所以能夠?qū)崿F(xiàn)計(jì)算機(jī)中的運(yùn)算、控制、數(shù)據(jù)存儲(chǔ)等功能部件的邏輯電路描述?；具壿嬮T(mén)電路有與門(mén)電路或門(mén)電路和非門(mén)電路。常用的邏輯門(mén)電路還有與非門(mén)電路與或門(mén)電路與或非門(mén)電路異或門(mén)電路同或門(mén)電路三態(tài)門(mén)電路等。,在邏輯門(mén)電路中，任何信號(hào)只存在兩種狀態(tài)，即高電平和低電平；通常以高電平來(lái)表示邏輯1（正邏輯）、以低電平來(lái)表示邏輯0（負(fù)邏輯）。,(1)邏輯“與”運(yùn)算和“與門(mén)”電路,邏輯“與”又稱(chēng)為邏輯“乘”運(yùn)算。運(yùn)算符號(hào)：“”,“”,“AND”等。邏輯表達(dá)式：L=AB=AB=與門(mén)電路符號(hào)：與門(mén)電路：能實(shí)現(xiàn)邏輯與功能的數(shù)字電路單元真值表：兩個(gè)輸入變量的四種組合與其對(duì)應(yīng)的輸出變量之間的關(guān)系。ABL=AB000010100111,1(A、B均為1)0(A、B中任一為0),AB,L,(2)邏輯“或”運(yùn)算和“或門(mén)”電路,邏輯“或”又稱(chēng)為邏輯加運(yùn)算。運(yùn)算符號(hào)：“+”、“”、“OR”等。邏輯表達(dá)式：L=A+B=AB=或門(mén)電路符號(hào)：邏輯真值表：ABL=A+B000011101111,L,AB,1(A、B中任一為1)0(A、B均為0),(3)邏輯“非”運(yùn)算和“非門(mén)”電路,邏輯“非”又稱(chēng)為邏輯反運(yùn)算.運(yùn)算符號(hào)：“”（上橫線）邏輯表達(dá)式為：L=非門(mén)電路符號(hào)：邏輯真值表：AL0110,A,A,1（A=0）0（A=1）,L,（4）常用的組合邏輯門(mén),在數(shù)字系統(tǒng)中，除了基本的“與”運(yùn)算、“或”運(yùn)算、“非”運(yùn)算之外，為了方便邏輯關(guān)系的描述常常使用一些通過(guò)這三種基本邏輯運(yùn)算關(guān)系派生出來(lái)的邏輯運(yùn)算關(guān)系，這種派生出來(lái)的邏輯運(yùn)算通常被稱(chēng)為復(fù)合運(yùn)算，常見(jiàn)的復(fù)合運(yùn)算有：與非、或非、同或及異或等。,還有很多的組合邏輯門(mén)電路，如：全加器、譯碼器、編碼器、多路選擇器等等,3.1.2基本運(yùn)算規(guī)律和公式,基本運(yùn)算：加：A+0=A，A+1=1，A+A=A，A+A=1乘：A0=0，A1=A，AA=A，AA=0非：A+A=1，AA=0，A=A基本公式：吸收律，分配律，交換律，結(jié)合律，反演律,#吸收律：A+AB=A證明：A+AB=A（1+B）=A1=AA（A+B）=A證明：AA+AB=A+AB=AA+AB=A+B證明：A+AB=A+AB+AB=A+（A+A）B=A+1B=A+B,#分配律：,A(B+C)=AB+AC(A+B)(A+C)=A+BC證明：(A+B)(A+C)=AA+AC+BA+BC=A(1+C+B)+BC=A+BC,#交換律：,A+B=B+AAB=BA#結(jié)合率：（A+B）+C=A+（B+C）（AB）C=A（BC）#反演律：ABC=A+B+CA+B+C=ABC,3.2邏輯函數(shù)的三種表示法,1邏輯真值表：將邏輯函數(shù)輸入（邏輯變量）與輸出（函數(shù)取值）之間的所有組態(tài)關(guān)系用數(shù)字符號(hào)以并列的形式表示出來(lái)的表格。這是一種將具體問(wèn)題的描述轉(zhuǎn)變?yōu)檫壿嬯P(guān)系的描述的有效工具，也是獲得嚴(yán)謹(jǐn)?shù)倪壿嫼瘮?shù)表達(dá)式的最有效方法。2邏輯函數(shù)表達(dá)式：用與、或、非等基本的邏輯運(yùn)算關(guān)系符和邏輯常量、邏輯變量所組成的表示邏輯函數(shù)的數(shù)學(xué)表達(dá)式。形式簡(jiǎn)潔明了，便于書(shū)寫(xiě)和推演變換，根據(jù)真值表可以列出其邏輯表達(dá)式。3卡諾圖：n個(gè)變量的函數(shù)可以由2n個(gè)方格構(gòu)成的平面方格圖來(lái)表示，每個(gè)方格代表邏輯函數(shù)中的一個(gè)最小項(xiàng)，而任何一個(gè)邏輯函數(shù)都可以表示成“最小項(xiàng)之和”的形式，因此通過(guò)方格陣列可清楚的反映出函數(shù)所有最小項(xiàng)之間的關(guān)系，這個(gè)平面方格圖就是卡諾圖。利用卡諾圖中表示最小項(xiàng)的方格之間的相鄰、相對(duì)、相重的位置關(guān)系進(jìn)行最小項(xiàng)合并是進(jìn)行邏輯函數(shù)化簡(jiǎn)的最直接、最有效的方法。,321邏輯真值表,1、真值表：由邏輯變量的所有可能取值的組合及其對(duì)應(yīng)的邏輯函數(shù)值所構(gòu)成的表格。例：有一個(gè)3位二進(jìn)制數(shù)ABC，列出ABC中出現(xiàn)奇數(shù)個(gè)1的邏輯關(guān)系。解：3位二進(jìn)制數(shù)ABC共有8種組合狀態(tài)，分別定義為m0m7；它們的奇偶性定義為函數(shù)F，其中F0表示呈偶性，F(xiàn)1表示呈奇性，將ABC全部的組態(tài)關(guān)系以及對(duì)應(yīng)的F取值以表格的形式表示出來(lái)。該表稱(chēng)為邏輯函數(shù)F的真值表。,注意：真值表必須列出邏輯變量所有可能的取值及其所對(duì)應(yīng)的函數(shù)取值，不能有遺漏。（二個(gè)變量有22=4、三個(gè)邏輯變量有23=8、四個(gè)變量有2416、n個(gè)變量有2n種可能的取值）。,3.2.2邏輯表達(dá)式：由邏輯變量、邏輯常量和運(yùn)算符組成的表達(dá)式。它是邏輯變量的函數(shù)，也是設(shè)計(jì)邏輯電路的根據(jù)。根據(jù)真值表可以列出邏輯表達(dá)式。方法是：把真值表中所有使函數(shù)值為1的自變量組合項(xiàng)“或”起來(lái)。每一項(xiàng)（最小項(xiàng)）是邏輯變量的本身或其非的與運(yùn)算。如果變量是1取其本身；是0則取變量的非值例如，上頁(yè)例題中的邏輯表達(dá)式為：F=1:F(A,B,C)=m(1,2,4,7)=ABC+ABC+ABC+ABCF=0:F(A,B,C)=m(0,3,5,6)=ABC+ABC+ABC+ABC,由于邏輯表達(dá)式進(jìn)行化簡(jiǎn)需要較強(qiáng)的技巧，不熟練者很難判斷，,323卡諾圖（KarnaughMap）卡諾圖是邏輯函數(shù)的另一種表示形式，它是一種以圖形形式來(lái)表達(dá)邏輯關(guān)系的方法，也是將邏輯函數(shù)進(jìn)行邏輯化簡(jiǎn)的一種最有效的手段。用卡諾圖化簡(jiǎn)邏輯函數(shù)，不但具有簡(jiǎn)單、直觀、方便的特點(diǎn)，而且還較容易的判斷出得到結(jié)果是否為最簡(jiǎn)的形式。用卡諾圖表示邏輯函數(shù)，是將該邏輯函數(shù)的每一個(gè)最小項(xiàng)取值，按照一定規(guī)則填入到所對(duì)應(yīng)的平面方格矩陣內(nèi)，這個(gè)平面方格矩陣圖就稱(chēng)為卡諾圖。,卡諾圖是一種直觀的平面方塊圖。它根據(jù)輸入變量的數(shù)量n將平面劃分為2n個(gè)方格，用來(lái)表示全部輸入變量組合項(xiàng)或者表示全部輸出項(xiàng)。與真值表有些相似，但是和真值表的自變量取值變化的最大不同在于：自變量的取值是按照它們?nèi)≈抵g的最小跳越關(guān)系進(jìn)行排列，即在左邊和上邊的自變量取值中只能有一個(gè)變量的取值是變化（相反）的，其余的保持不變?？ㄖZ圖坐標(biāo)點(diǎn)上的自變量取值可以不連續(xù)，但要保持最小跳躍。小方格中所填寫(xiě)的是：根據(jù)行列坐標(biāo)點(diǎn)上自變量的取值關(guān)系，找出在邏輯表達(dá)式中對(duì)應(yīng)的最小項(xiàng)的位置，在相應(yīng)的小方格中填寫(xiě)1；即小方格中填寫(xiě)那些使得邏輯函數(shù)在所對(duì)應(yīng)的行列坐標(biāo)點(diǎn)上取值為1的項(xiàng)。,卡諾圖的書(shū)寫(xiě)規(guī)則：,二維卡諾圖,輸入為X1、X2，輸出為F。左下圖為真值表，右下圖為卡諾圖?？ㄖZ圖左邊和上邊書(shū)寫(xiě)自變量的可能取值，中間則表明Mi最小項(xiàng)。最小項(xiàng)即一行真值表中各自變量或其“非”的邏輯乘積項(xiàng)。,NOX1X2FM000F0M101F1M210F2M311F3,X1,01,X2,01,M0,M1,M2,M3,三維卡諾圖輸入為X1、X2、X3，輸出為F。左下圖為真值表，右下圖為卡諾圖?？ㄖZ圖的左邊上邊書(shū)寫(xiě)自變量的可能取值，規(guī)則是最小跳躍。中間則表明最小項(xiàng)。,NOX1X2X3FM0000F0M1001F1M2010F2M3011F3M4100F4M5101F5M6110F6M7111F7,M0M1M2M3M6M7M4M5,X1X2,X3,01,00011110,四維卡諾圖輸入為A、B、C、D，輸出為F?？ㄖZ圖的左邊上邊書(shū)寫(xiě)自變量的可能取值，規(guī)則是最小跳躍。中間則表明最小項(xiàng)。,請(qǐng)用卡諾圖表示下列函數(shù),1、F(A,B,C)=ABC+ABC+ABC+ABC,卡諾圖的化簡(jiǎn)規(guī)則,若任何兩個(gè)標(biāo)“1”的相鄰單元可以形成一個(gè)圈，就可以消去一個(gè)變量；若任何四個(gè)標(biāo)“1”的相鄰單元可以形成一個(gè)圈，就可以消去兩個(gè)變量；若任何八個(gè)標(biāo)“1”的相鄰單元可以形成一個(gè)圈，就可以消去三個(gè)變量；卡諾圖化簡(jiǎn)的過(guò)程就是在卡諾圖上找出能夠覆蓋給定函數(shù)全部為1的單元的個(gè)數(shù)最少同時(shí)覆蓋面盡可能大的圈，然后寫(xiě)出其最簡(jiǎn)邏輯表達(dá)式。需要注意的是，由于卡諾圖的最上行、最下行和最左列、最右列以及4個(gè)頂點(diǎn)上所對(duì)應(yīng)的小方格在邏輯關(guān)系上也是彼此相鄰的，圈最小項(xiàng)時(shí)也屬于相鄰關(guān)系。,AB,CD,00011110,00011110,1,1,1,1,1,1,1,1,例：試用卡諾圖化簡(jiǎn)下面的邏輯表達(dá)式。解：根據(jù)邏輯表達(dá)式做出卡諾圖如下：根據(jù)卡諾圖化簡(jiǎn)規(guī)則，最后得到化簡(jiǎn)后的結(jié)果：,AB,CD,00011110,1,1,1,1,1,1,1,1,例：試用卡諾圖化簡(jiǎn)下面的邏輯表達(dá)式。解：根據(jù)邏輯表達(dá)式做出卡諾圖如下：根據(jù)卡諾圖化簡(jiǎn)規(guī)則，最后得到化簡(jiǎn)后的結(jié)果：,00011110,3.3邏輯代數(shù)的應(yīng)用舉例3.3.1數(shù)據(jù)處理方面的應(yīng)用,例3-3將寄存器R中的d5位清零，其他位不變。解：利用與運(yùn)算的特點(diǎn)，對(duì)寄存器中的內(nèi)容按位相“與”，即,例3-4將寄存器R中的數(shù)據(jù)都置為“1”。解：利用或運(yùn)算的特點(diǎn)，對(duì)寄存器中的內(nèi)容按位相“或”，即例3-5設(shè)有寄存器R1R2，要求把R1的高4位和R2的低四位拼成一個(gè)字節(jié)送給寄存器R3。解：可以綜合利用與運(yùn)算和或運(yùn)算的特點(diǎn)，先分別對(duì)R1和R2進(jìn)行與運(yùn)算，然后再按位相或。,3.3.2半加器和全加器,計(jì)算機(jī)的一個(gè)主要功能就是進(jìn)行數(shù)字信息處理，處理中一項(xiàng)很重要的工作就是進(jìn)行數(shù)值的算數(shù)運(yùn)算，通過(guò)上一章的介紹我們已經(jīng)有了一個(gè)概念，計(jì)算機(jī)首先是將各種要處理的數(shù)值信息轉(zhuǎn)變成機(jī)內(nèi)的二進(jìn)制形式進(jìn)行表示，其中基本的算術(shù)運(yùn)算（加、減、乘、除），都可以以補(bǔ)碼的形式通過(guò)加法來(lái)完成。所以加法器是計(jì)算機(jī)系統(tǒng)中最基本的也是最重要的部件。由于二進(jìn)制運(yùn)算可以用邏輯運(yùn)算來(lái)表示，因此可以用邏輯設(shè)計(jì)的方法來(lái)設(shè)計(jì)加法運(yùn)算電路。加法器分為半加器和全加器。,（1）一位半加器設(shè)計(jì),由于半加器不需要考慮低位向本位產(chǎn)生的進(jìn)位，因此它只有兩個(gè)輸入端和兩個(gè)輸出端。設(shè)加數(shù)與被加數(shù)（輸入端）為A、B；和為S（輸出端）、本位產(chǎn)生的向高位進(jìn)位為Ci（輸出端）；它們的取值關(guān)系用下列真值表來(lái)表示。,A,B,S,C,S=AB+AB=AB，Ci=AB,（2）一位全加器的設(shè)計(jì),由于全加器考慮了低位向本位產(chǎn)生的進(jìn)位關(guān)系，所以它有三個(gè)輸入端和兩個(gè)輸出端。設(shè)輸入變量為：A（被加數(shù)）、B（加數(shù)）、Ci-1（低位進(jìn)位），輸出變量為：和S、本位向高位的進(jìn)位Ci+1，它們的取值關(guān)系用下列真值表表示。,S=ABCi-1+ABCi-1+ABCi-1+ABCi-1=ABCi-1Ci+1=ABCi-1+ABCi-1+ABCi-1+ABCi-1=(AB)Ci-1+AB,3.4計(jì)算機(jī)中常用的邏輯部件,3.4.1基本存儲(chǔ)邏輯電路,計(jì)算機(jī)信息的存儲(chǔ)一般是采用兩種方式實(shí)現(xiàn)的一種是將信息記錄在磁性介質(zhì)上（如磁盤(pán)、磁帶等）；另一種是采用電子元器件存儲(chǔ)信息計(jì)算機(jī)內(nèi)部有許多寄存器，其保存一位信息的基本單元器件是觸發(fā)器，它有兩種穩(wěn)定狀態(tài)，分別代表數(shù)字信號(hào)“0”和“1”其狀態(tài)取決于當(dāng)前輸入和以前的存儲(chǔ)狀態(tài)(時(shí)序邏輯電路)。,(1)D觸發(fā)器,DSQCLKCLRQ,輸入輸出SCLRCLKDQ0011000010XX101XX0,電路符號(hào)：D為數(shù)據(jù)輸入端；CLK為時(shí)鐘信號(hào)；S為置位信號(hào)端；CLR復(fù)位信號(hào)端；Q為輸出信號(hào)端。D觸發(fā)器功能表：正跳變觸發(fā)有效。,(2)J-K觸發(fā)器,輸入輸出SCLRCLKJKQ0000不變00101000100011翻轉(zhuǎn)01XXX010XXX1,電路符號(hào)：J、K為控制輸入端；CLK為時(shí)鐘信號(hào)；S為置位信號(hào)端；CLR復(fù)位信號(hào)端；Q為輸出信號(hào)端。,J-K觸發(fā)器功能表：（負(fù)跳變觸發(fā)有效）,3.4.2寄存器,計(jì)算機(jī)中常用部件，用于暫存二進(jìn)制信息。寄存器可由多個(gè)觸發(fā)器組成。每個(gè)觸發(fā)器存1Bit，N個(gè)觸發(fā)器儲(chǔ)存N位二進(jìn)制數(shù)據(jù)。下圖為由4個(gè)D觸發(fā)器組成的四位緩沖寄存器。,寄存器通?？梢杂脕?lái)作為數(shù)據(jù)緩存的緩沖寄存器和進(jìn)行移位操作的移位寄存器。見(jiàn)書(shū)上詳細(xì)介紹。,3.4.3計(jì)數(shù)器,計(jì)數(shù)器也是一種由若干個(gè)觸發(fā)器組成的寄存器，它的功能是能夠在外部計(jì)數(shù)脈沖的作用下，將存儲(chǔ)在觸發(fā)器中的數(shù)字加1。在計(jì)算機(jī)中，計(jì)數(shù)器可被用來(lái)對(duì)取出的指令進(jìn)行計(jì)數(shù)，以保證能準(zhǔn)確地取出后續(xù)指令。計(jì)數(shù)器也分很多種，有脈沖計(jì)數(shù)器、同步計(jì)數(shù)器、程序計(jì)數(shù)器等。在此僅介紹一種最基本的四位二進(jìn)制脈沖計(jì)數(shù)器，電路原理如下頁(yè)圖。,四級(jí)二進(jìn)制并行計(jì)數(shù)器,3.4.4三態(tài)門(mén),D輸入端L輸出端E使能端當(dāng)E=1時(shí)，其輸出等于輸入，是同相門(mén)；當(dāng)E=0時(shí)，輸出與輸入呈現(xiàn)高電阻隔離。計(jì)算機(jī)中用做數(shù)據(jù)輸出器件，當(dāng)不輸出數(shù)據(jù)時(shí)，可令E=0，使對(duì)總線無(wú)影響，因而多個(gè)器件可同時(shí)連到總線上。,3.4.5譯碼器,譯碼：把某組編碼翻譯為唯一的輸出。譯碼器：有38譯碼器，即8選1譯碼器和416譯碼器，即16選1譯碼器等多種。,例如：38譯碼器，即8選1譯碼器的輸入信號(hào)有三個(gè)：C、B、A（A為低位），三位二進(jìn)制數(shù)可組成8個(gè)不同數(shù)字，因此可分別選中輸出Y0到Y(jié)7的某一個(gè)輸出故稱(chēng)為8選1譯碼器。,下圖分別為譯碼器引腳圖和輸入輸出真值表其中：G1、G2A、G2B為芯片選擇端，G1高電平有效，而G2A、G2B為低電平有效。,74LS138,3.5計(jì)算機(jī)中的數(shù)據(jù)校驗(yàn)方法,計(jì)算機(jī)中各部件與各部件之間經(jīng)常需要進(jìn)行大量的數(shù)據(jù)存取、傳送操作，并且要求傳輸準(zhǔn)確、可靠。為此一方面需要通過(guò)硬件電路的可靠性來(lái)保障，另一方面還要在傳輸過(guò)程中，需對(duì)接收到的數(shù)據(jù)進(jìn)行檢錯(cuò)、糾錯(cuò)，以便發(fā)現(xiàn)和糾正數(shù)據(jù)在傳輸過(guò)程中產(chǎn)生的錯(cuò)誤。常用的數(shù)據(jù)較驗(yàn)方法有：奇偶檢驗(yàn)、循環(huán)冗余較驗(yàn)、海明碼等。本節(jié)將介紹前兩種交驗(yàn)方法。,在被傳輸?shù)挠行?shù)據(jù)代碼之外，擴(kuò)充部分校驗(yàn)代碼，擴(kuò)充的部分被稱(chēng)為校驗(yàn)位；將有效數(shù)據(jù)代碼和擴(kuò)充校驗(yàn)位一起按照某種規(guī)則或算法進(jìn)行統(tǒng)一編碼，形成帶校驗(yàn)信息的數(shù)據(jù)，在數(shù)據(jù)傳輸時(shí)一并進(jìn)行傳送；當(dāng)接收端收到帶有校驗(yàn)信息的編碼數(shù)據(jù)時(shí)，再利用約定的規(guī)則或算法進(jìn)行譯碼（解碼），如果所約定的規(guī)則或算法沒(méi)被破壞則表示數(shù)據(jù)傳輸正確，否則表明收到的數(shù)據(jù)信息在傳輸過(guò)程中發(fā)生錯(cuò)誤，然后根據(jù)被破壞后編碼信息的某些特征和規(guī)則來(lái)判斷，看是哪一位出錯(cuò)，再進(jìn)行修正它。,冗余校驗(yàn)法的基本原理是：,幾個(gè)名詞概念：碼字：由若干代碼組成的一個(gè)字。如8421碼中6（0110），7（0111）碼距：一種碼制中任意兩個(gè)碼字間的最小距離。距離：兩個(gè)碼字之間不同的代碼個(gè)數(shù)。8421碼中，最小的碼距為1，如0000和0001、0010和0011等；最大碼距為4，如0111和1000。8421碼的碼距為1。碼距為1，即不能查錯(cuò)也不能糾錯(cuò)。碼距越大，查錯(cuò)、糾錯(cuò)能力越強(qiáng)。,3.5.1奇偶校驗(yàn)碼,奇偶校驗(yàn)法是計(jì)算機(jī)中廣泛采用的檢查傳輸數(shù)據(jù)準(zhǔn)確性的方法。奇偶校驗(yàn)法的原理是：在每組數(shù)據(jù)信息上附加一個(gè)校驗(yàn)位，校驗(yàn)位的取值（0或1）取決于這組信息中1的個(gè)數(shù)和校驗(yàn)方式（奇或偶校驗(yàn)）。如果采用奇校驗(yàn)，則這組數(shù)據(jù)加上校驗(yàn)碼位后數(shù)據(jù)中1的個(gè)數(shù)應(yīng)為奇數(shù)個(gè)。如果采用偶校驗(yàn)，則這組數(shù)據(jù)加上校驗(yàn)碼位后數(shù)據(jù)中1的個(gè)數(shù)應(yīng)為偶數(shù)個(gè)。,例如：八位信息10101011中共有5個(gè)1，附加校驗(yàn)位后變?yōu)榫盼?。若采用奇校?yàn)，則附加的校驗(yàn)位應(yīng)取0值，保證1的個(gè)數(shù)為奇數(shù)個(gè)即010101011；若采用偶校驗(yàn)則附加的校驗(yàn)位應(yīng)取1值,即110101011。奇偶校驗(yàn)的特點(diǎn)：1、奇偶校驗(yàn)法使數(shù)據(jù)的碼距為2，因而可檢出數(shù)據(jù)傳送過(guò)程中奇數(shù)個(gè)數(shù)位出錯(cuò)的情況；2、實(shí)際中兩位同時(shí)出錯(cuò)的概率極低，奇偶校驗(yàn)法簡(jiǎn)便可靠易行，但它只能發(fā)現(xiàn)錯(cuò)誤，卻不知錯(cuò)在何處，因而不能自動(dòng)糾正。,例如一個(gè)實(shí)用的8-Bits數(shù)據(jù)奇偶校驗(yàn)與奇偶校驗(yàn)碼形成電路，其中數(shù)據(jù)用D7D0表示，校驗(yàn)位用P表示。,PD7D6D5D4D3D2D1D0,P奇形成,P偶形成,P奇校錯(cuò),P偶校錯(cuò),3.5.2循環(huán)冗余碼（CRC碼）,循環(huán)冗余校驗(yàn)方式：通過(guò)某種數(shù)學(xué)公式建立信息位和校驗(yàn)位之間的約定關(guān)系能夠校驗(yàn)傳送信息的對(duì)錯(cuò)，并且能自動(dòng)修正錯(cuò)誤。廣泛用于通信和磁介存儲(chǔ)器中。CRC編碼格式是在k位信息后加r位檢驗(yàn)碼。NN-121信息位（k位）校驗(yàn)位（r位）,C1C2.CKr1r2ri,1、CRC碼的編碼方法,CRC整個(gè)編碼長(zhǎng)度為n=k+r位，故CRC碼又叫（n，k）碼。其編碼方法如下：假設(shè)被傳送的k位二進(jìn)制信息位用C(x)表示,系統(tǒng)選定的生成多項(xiàng)式用G(X)表示，將C(x)左移G(X)的最高次冪(即等于需要添加的校驗(yàn)位的位數(shù)r)，寫(xiě)作:C(x)2r然后將其C(x)2r除以生成多項(xiàng)式G(x)，所得商用Q(x)表示，余數(shù)用R(x)表示。則：兩邊同時(shí)乘以G(x)并左移R(x)得到：,故有：上式中，等式左邊即為所求的n位CRC碼，其中余數(shù)表達(dá)式R(x)就是校驗(yàn)位(r位)。且等式兩邊都是G(x)的倍數(shù)。發(fā)送信息時(shí)將等式左邊生成的n位CRC碼送給對(duì)方。當(dāng)接收方接到n位編碼后，同樣除以G(x).如果傳輸正確則余數(shù)為0，否則則可以根據(jù)余數(shù)的數(shù)值確定是哪位數(shù)據(jù)出錯(cuò)。,由于CRC編碼采用的加、減法是按位加減法，即不考慮進(jìn)位與借位，運(yùn)算規(guī)則為：,例：有一個(gè)（7,4）碼（即CRC碼為7位，信息碼為4位），已確定生成多項(xiàng)式為：G（X）=X3+X+1=1011被傳輸?shù)男畔(x)=1001，求C(x)的CRC碼。,解：C（x）左移r=nk=3位即：將上式模2(無(wú)進(jìn)/借位),除以給定的G(x)=1011：1001000/1011=1010+110/1011得到余數(shù)表達(dá)式：R(x)=110所求CRC碼為：,2、CRC碼的查錯(cuò)與糾錯(cuò),收到的CRC碼除以約定的生成多項(xiàng)式G(x)，如果余數(shù)為0則傳輸無(wú)誤，否則傳輸錯(cuò)誤，根據(jù)所得余數(shù)值就可找出錯(cuò)誤并取反糾正。上表詳細(xì)說(shuō)明了CRC碼1001110在傳送時(shí)某一位出錯(cuò)后的判斷與糾正方法C(X)=1001、G(x)=1011。,3、生成多項(xiàng)式G（x）的確定,G(x)是一個(gè)約定的除數(shù)，用來(lái)產(chǎn)生校驗(yàn)碼。從檢錯(cuò)和糾錯(cuò)的要求出發(fā)，它并不是隨意選擇的，它應(yīng)滿足下列要求：任何一位發(fā)生錯(cuò)誤都應(yīng)使余數(shù)不為0不同位發(fā)生錯(cuò)誤應(yīng)使余數(shù)不同余數(shù)繼續(xù)做模2除，應(yīng)使余數(shù)循環(huán),