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

第三章計(jì)算機(jī)中的邏輯運(yùn)算與邏輯部件,本章基本要求：1.掌握邏輯運(yùn)算的基本概念、規(guī)則；2.掌握用真值表、邏輯表達(dá)式、卡諾圖這三種邏輯函數(shù)表示方法；3.了解計(jì)算機(jī)內(nèi)常用邏輯器件：基本門電路、三態(tài)門、觸發(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)立的，所以通常人們又稱邏輯代數(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，因此又稱為二值邏輯。,它們通常反映在邏輯電路上則是電路的“通”與“斷”、反映在電信號(hào)上則是信號(hào)電平的“髙”與“低”，所以把這種工作在二值（0、1）狀態(tài)下的電路稱為數(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基本邏輯門電路,邏輯門是描述數(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電路有與門電路或門電路和非門電路。常用的邏輯門電路還有與非門電路與或門電路與或非門電路異或門電路同或門電路三態(tài)門電路等。,在邏輯門電路中，任何信號(hào)只存在兩種狀態(tài)，即高電平和低電平；通常以高電平來(lái)表示邏輯1（正邏輯）、以低電平來(lái)表示邏輯0（負(fù)邏輯）。,(1)邏輯“與”運(yùn)算和“與門”電路,邏輯“與”又稱為邏輯“乘”運(yùn)算。運(yùn)算符號(hào)：“”,“”,“AND”等。邏輯表達(dá)式：L=AB=AB=與門電路符號(hào)：與門電路：能實(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)算和“或門”電路,邏輯“或”又稱為邏輯加運(yùn)算。運(yùn)算符號(hào)：“+”、“”、“OR”等。邏輯表達(dá)式：L=A+B=AB=或門電路符號(hào)：邏輯真值表：ABL=A+B000011101111,L,AB,1(A、B中任一為1)0(A、B均為0),(3)邏輯“非”運(yùn)算和“非門”電路,邏輯“非”又稱為邏輯反運(yùn)算.運(yùn)算符號(hào)：“”（上橫線）邏輯表達(dá)式為：L=非門電路符號(hào)：邏輯真值表：AL0110,A,A,1（A=0）0（A=1）,L,（4）常用的組合邏輯門,在數(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)算通常被稱為復(fù)合運(yùn)算，常見(jiàn)的復(fù)合運(yù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)潔明了，便于書寫和推演變換，根據(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)。該表稱為邏輯函數(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è)平面方格矩陣圖就稱為卡諾圖。,卡諾圖是一種直觀的平面方塊圖。它根據(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ù)，但要保持最小跳躍。小方格中所填寫的是：根據(jù)行列坐標(biāo)點(diǎn)上自變量的取值關(guān)系，找出在邏輯表達(dá)式中對(duì)應(yīng)的最小項(xiàng)的位置，在相應(yīng)的小方格中填寫1；即小方格中填寫那些使得邏輯函數(shù)在所對(duì)應(yīng)的行列坐標(biāo)點(diǎn)上取值為1的項(xiàng)。,卡諾圖的書寫規(guī)則：,二維卡諾圖,輸入為X1、X2，輸出為F。左下圖為真值表，右下圖為卡諾圖?？ㄖZ圖左邊和上邊書寫自變量的可能取值，中間則表明Mi最小項(xiàng)。最小項(xiàng)即一行真值表中各自變量或其“非”的邏輯乘積項(xiàng)。,NOX1X2FM000F0M101F1M210F2M311F3,X1,01,X2,01,M0,M1,M2,M3,三維卡諾圖輸入為X1、X2、X3，輸出為F。左下圖為真值表，右下圖為卡諾圖?？ㄖZ圖的左邊上邊書寫自變量的可能取值，規(guī)則是最小跳躍。中間則表明最小項(xiàng)。,NOX1X2X3FM0000F0M1001F1M2010F2M3011F3M4100F4M5101F5M6110F6M7111F7,M0M1M2M3M6M7M4M5,X1X2,X3,01,00011110,四維卡諾圖輸入為A、B、C、D，輸出為F。卡諾圖的左邊上邊書寫自變量的可能取值，規(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í)覆蓋面盡可能大的圈，然后寫出其最簡(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ì)上（如磁盤、磁帶等）；另一種是采用電子元器件存儲(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)書上詳細(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)門,D輸入端L輸出端E使能端當(dāng)E=1時(shí)，其輸出等于輸入，是同相門；當(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è)輸出故稱為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ò)充的部分被稱為校驗(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)，寫作: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),