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

《計(jì)算機(jī)中的邏輯運(yùn)算與邏輯部件.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《計(jì)算機(jī)中的邏輯運(yùn)算與邏輯部件.ppt（50頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

第三章計(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年由英國數(shù)學(xué)家喬治布爾（GeorgeBoole)首先創(chuàng)立的，所以通常人們又稱邏輯代數(shù)為布爾代數(shù)。邏輯代數(shù)與普通代數(shù)有著不同的概念，其所表示的不是數(shù)值之間的大小關(guān)系，而是邏輯函數(shù)與邏輯變量之間所存在的邏輯關(guān)系與邏輯規(guī)律。邏輯規(guī)律表示了一種因果關(guān)系，如“真”與“假”、“有”和“無”、“是”與“非”、“開”與“關(guān)”等，這些邏輯關(guān)系的一個(gè)共同點(diǎn)是它們僅有兩種狀態(tài)，即：0和1，因此又稱為二值邏輯。,它們通常反映在邏輯電路上則是電路的“通”與“斷”、反映在電信號上則是信號電平的“髙”與“低”，所以把這種工作在二值（0、1）狀態(tài)下的電路稱為數(shù)字邏輯電路。邏輯代數(shù)是分析和設(shè)計(jì)數(shù)字邏輯系統(tǒng)的數(shù)學(xué)基礎(chǔ)，而數(shù)字邏輯電路則是構(gòu)成計(jì)算機(jī)硬件核心電路的主要部分。邏輯代數(shù)是指：用0和1兩個(gè)基本的數(shù)字符號表示邏輯常量，用取值只能為0或1的任何字母符號表示邏輯變量，用“與”、“或”、“非”等基本邏輯符號表示運(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)系相對應(yīng)，所以能夠?qū)崿F(xiàn)計(jì)算機(jī)中的運(yùn)算、控制、數(shù)據(jù)存儲(chǔ)等功能部件的邏輯電路描述?；具壿嬮T電路有‘與門’電路﹑‘或門’電路和‘非門’電路。常用的邏輯門電路還有‘與非門’電路﹑‘與或門’電路﹑‘與或非門’電路﹑‘異或門’電路﹑‘同或門’電路﹑‘三態(tài)門’電路等。,在邏輯門電路中，任何信號只存在兩種狀態(tài)，即高電平和低電平；通常以高電平來表示邏輯‘1’（正邏輯）、以低電平來表示邏輯‘0’（負(fù)邏輯）。,,(1)邏輯“與”運(yùn)算和“與門”電路,,,邏輯“與”又稱為邏輯“乘”運(yùn)算。運(yùn)算符號：“”,“∩”,“AND”等。邏輯表達(dá)式：L=AB=A∧B=與門電路符號：與門電路：能實(shí)現(xiàn)邏輯與功能的數(shù)字電路單元真值表：兩個(gè)輸入變量的四種組合與其對應(yīng)的輸出變量之間的關(guān)系。ABL=AB000010100111,,,1(A、B均為1)0(A、B中任一為0),,,,,,,AB,L,(2)邏輯“或”運(yùn)算和“或門”電路,邏輯“或”又稱為邏輯加運(yùn)算。運(yùn)算符號：“+”、“∪”、“OR”等。邏輯表達(dá)式：L=A+B=A∨B=或門電路符號：邏輯真值表：ABL=A+B000011101111,,,,L,AB,1(A、B中任一為1)0(A、B均為0),,,,(3)邏輯“非”運(yùn)算和“非門”電路,邏輯“非”又稱為邏輯反運(yùn)算.運(yùn)算符號：“—”（上橫線）邏輯表達(dá)式為：L==非門電路符號：邏輯真值表：AL0110,,,,A,—A,1（A=0）0（A=1）,L,,,,,,（4）常用的組合邏輯門,在數(shù)字系統(tǒng)中，除了基本的“與”運(yùn)算、“或”運(yùn)算、“非”運(yùn)算之外，為了方便邏輯關(guān)系的描述常常使用一些通過這三種基本邏輯運(yùn)算關(guān)系派生出來的邏輯運(yùn)算關(guān)系，這種派生出來的邏輯運(yùn)算通常被稱為復(fù)合運(yùn)算，常見的復(fù)合運(yùn)算有：與非、或非、同或及異或等。,還有很多的組合邏輯門電路，如：全加器、譯碼器、編碼器、多路選擇器等等,3.1.2基本運(yùn)算規(guī)律和公式,基本運(yùn)算：加：A+0=A，A+1=1，A+A=A，A+A=1乘：A?0=0，A?1=A，A?A=A，A?A=0非：A+A=1，A?A=0，A=A基本公式：吸收律，分配律，交換律，結(jié)合律，反演律,—,—,,,,,#吸收律：A+A?B=A證明：A+A?B=A（1+B）=A?1=AA?（A+B）=A證明：A?A+A?B=A+A?B=AA+A?B=A+B證明：A+A?B=A+A?B+A?B=A+（A+A）?B=A+1?B=A+B,,,,,#分配律：,A?(B+C)=A?B+A?C(A+B)?(A+C)=A+B?C證明：(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ù)字符號以并列的形式表示出來的表格。這是一種將具體問題的描述轉(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á)式。形式簡潔明了，便于書寫和推演變換，根據(jù)真值表可以列出其邏輯表達(dá)式。3．卡諾圖：n個(gè)變量的函數(shù)可以由2n個(gè)方格構(gòu)成的平面方格圖來表示，每個(gè)方格代表邏輯函數(shù)中的一個(gè)最小項(xiàng)，而任何一個(gè)邏輯函數(shù)都可以表示成“最小項(xiàng)之和”的形式，因此通過方格陣列可清楚的反映出函數(shù)所有最小項(xiàng)之間的關(guān)系，這個(gè)平面方格圖就是卡諾圖。利用卡諾圖中表示最小項(xiàng)的方格之間的相鄰、相對、相重的位置關(guān)系進(jìn)行最小項(xiàng)合并是進(jìn)行邏輯函數(shù)化簡的最直接、最有效的方法。,3．2．1邏輯真值表,1、真值表：由邏輯變量的所有可能取值的組合及其對應(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)，分別定義為m0～m7；它們的奇偶性定義為函數(shù)F，其中F＝0表示呈偶性，F(xiàn)＝1表示呈奇性，將ABC全部的組態(tài)關(guān)系以及對應(yīng)的F取值以表格的形式表示出來。該表稱為邏輯函數(shù)F的真值表。,注意：真值表必須列出邏輯變量所有可能的取值及其所對應(yīng)的函數(shù)取值，不能有遺漏。（二個(gè)變量有22=4、三個(gè)邏輯變量有23=8、四個(gè)變量有24＝16、n個(gè)變量有2n種可能的取值……）。,3.2.2邏輯表達(dá)式：——由邏輯變量、邏輯常量和運(yùn)算符組成的表達(dá)式。它是邏輯變量的函數(shù)，也是設(shè)計(jì)邏輯電路的根據(jù)。根據(jù)真值表可以列出邏輯表達(dá)式。方法是：把真值表中所有使函數(shù)值為1的自變量組合項(xiàng)“或”起來。每一項(xiàng)（最小項(xiàng)）是邏輯變量的本身或其非的與運(yùn)算。如果變量是1取其本身；是0則取變量的非值例如，上頁例題中的邏輯表達(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)行化簡需要較強(qiáng)的技巧，不熟練者很難判斷，,3．2．3卡諾圖（KarnaughMap）卡諾圖是邏輯函數(shù)的另一種表示形式，它是一種以圖形形式來表達(dá)邏輯關(guān)系的方法，也是將邏輯函數(shù)進(jìn)行邏輯化簡的一種最有效的手段。用卡諾圖化簡邏輯函數(shù)，不但具有簡單、直觀、方便的特點(diǎn)，而且還較容易的判斷出得到結(jié)果是否為最簡的形式。用卡諾圖表示邏輯函數(shù)，是將該邏輯函數(shù)的每一個(gè)最小項(xiàng)取值，按照一定規(guī)則填入到所對應(yīng)的平面方格矩陣內(nèi)，這個(gè)平面方格矩陣圖就稱為卡諾圖。,卡諾圖是一種直觀的平面方塊圖。它根據(jù)輸入變量的數(shù)量n將平面劃分為2n個(gè)方格，用來表示全部輸入變量組合項(xiàng)或者表示全部輸出項(xiàng)。與真值表有些相似，但是和真值表的自變量取值變化的最大不同在于：自變量的取值是按照它們?nèi)≈抵g的最小跳越關(guān)系進(jìn)行排列，即在左邊和上邊的自變量取值中只能有一個(gè)變量的取值是變化（相反）的，其余的保持不變。卡諾圖坐標(biāo)點(diǎn)上的自變量取值可以不連續(xù)，但要保持最小跳躍。小方格中所填寫的是：根據(jù)行列坐標(biāo)點(diǎn)上自變量的取值關(guān)系，找出在邏輯表達(dá)式中對應(yīng)的最小項(xiàng)的位置，在相應(yīng)的小方格中填寫1；即小方格中填寫那些使得邏輯函數(shù)在所對應(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?？ㄖZ圖的左邊上邊書寫自變量的可能取值，規(guī)則是最小跳躍。中間則表明最小項(xiàng)。,請用卡諾圖表示下列函數(shù),1、F(A,B,C)=ABC+ABC+ABC+ABC,,,,,,卡諾圖的化簡規(guī)則,若任何兩個(gè)標(biāo)“1”的相鄰單元可以形成一個(gè)圈，就可以消去一個(gè)變量；若任何四個(gè)標(biāo)“1”的相鄰單元可以形成一個(gè)圈，就可以消去兩個(gè)變量；若任何八個(gè)標(biāo)“1”的相鄰單元可以形成一個(gè)圈，就可以消去三個(gè)變量；卡諾圖化簡的過程就是在卡諾圖上找出能夠覆蓋給定函數(shù)全部為1的單元的個(gè)數(shù)最少同時(shí)覆蓋面盡可能大的圈，然后寫出其最簡邏輯表達(dá)式。需要注意的是，由于卡諾圖的最上行、最下行和最左列、最右列以及4個(gè)頂點(diǎn)上所對應(yīng)的小方格在邏輯關(guān)系上也是彼此相鄰的，圈最小項(xiàng)時(shí)也屬于相鄰關(guān)系。,,,AB,CD,00011110,00011110,1,1,1,1,,,,,1,1,1,1,,,,,,,,例：試用卡諾圖化簡下面的邏輯表達(dá)式。解：根據(jù)邏輯表達(dá)式做出卡諾圖如下：根據(jù)卡諾圖化簡規(guī)則，最后得到化簡后的結(jié)果：,,,,,,,,,AB,CD,00011110,1,1,1,1,1,1,1,1,,例：試用卡諾圖化簡下面的邏輯表達(dá)式。解：根據(jù)邏輯表達(dá)式做出卡諾圖如下：根據(jù)卡諾圖化簡規(guī)則，最后得到化簡后的結(jié)果：,,00011110,3.3邏輯代數(shù)的應(yīng)用舉例3.3.1數(shù)據(jù)處理方面的應(yīng)用,例3-3將寄存器R中的d5位清零，其他位不變。解：利用與運(yùn)算的特點(diǎn)，對寄存器中的內(nèi)容按位相“與”，即,,例3-4將寄存器R中的數(shù)據(jù)都置為“1”。解：利用或運(yùn)算的特點(diǎn)，對寄存器中的內(nèi)容按位相“或”，即例3-5設(shè)有寄存器R1R2，要求把R1的高4位和R2的低四位拼成一個(gè)字節(jié)送給寄存器R3。解：可以綜合利用與運(yùn)算和或運(yùn)算的特點(diǎn)，先分別對R1和R2進(jìn)行與運(yùn)算，然后再按位相或。,3.3.2半加器和全加器,計(jì)算機(jī)的一個(gè)主要功能就是進(jìn)行數(shù)字信息處理，處理中一項(xiàng)很重要的工作就是進(jìn)行數(shù)值的算數(shù)運(yùn)算，通過上一章的介紹我們已經(jīng)有了一個(gè)概念，計(jì)算機(jī)首先是將各種要處理的數(shù)值信息轉(zhuǎn)變成機(jī)內(nèi)的二進(jìn)制形式進(jìn)行表示，其中基本的算術(shù)運(yùn)算（加、減、乘、除），都可以以補(bǔ)碼的形式通過加法來完成。所以加法器是計(jì)算機(jī)系統(tǒng)中最基本的也是最重要的部件。由于二進(jìn)制運(yùn)算可以用邏輯運(yùn)算來表示，因此可以用邏輯設(shè)計(jì)的方法來設(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)系用下列真值表來表示。,A,B,S,C,S=AB+AB=A⊕B，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=A⊕B⊕Ci-1Ci+1=ABCi-1+ABCi-1+ABCi-1+ABCi-1=(A⊕B)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ù)字信號“0”和“1”其狀態(tài)取決于當(dāng)前輸入和以前的存儲(chǔ)狀態(tài)(時(shí)序邏輯電路)。,(1)D觸發(fā)器,DSQCLKCLRQ,,,,,,輸入輸出SCLRCLKDQ0011000010XX101XX0,,,,,,,,,,,,,,,電路符號：D為數(shù)據(jù)輸入端；CLK為時(shí)鐘信號；S為置位信號端；CLR復(fù)位信號端；Q為輸出信號端。D觸發(fā)器功能表：正跳變觸發(fā)有效。,,,(2)J-K觸發(fā)器,輸入輸出SCLRCLKJKQ0000不變00101000100011翻轉(zhuǎn)01XXX010XXX1,,,,,,,,,,,,,,,,,,,,,,電路符號：J、K為控制輸入端；CLK為時(shí)鐘信號；S為置位信號端；CLR復(fù)位信號端；Q為輸出信號端。,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ā)器組成的四位緩沖寄存器。,寄存器通?？梢杂脕碜鳛閿?shù)據(jù)緩存的緩沖寄存器和進(jìn)行移位操作的移位寄存器。見書上詳細(xì)介紹。,3.4.3計(jì)數(shù)器,計(jì)數(shù)器也是一種由若干個(gè)觸發(fā)器組成的寄存器，它的功能是能夠在外部計(jì)數(shù)脈沖的作用下，將存儲(chǔ)在觸發(fā)器中的數(shù)字加1。在計(jì)算機(jī)中，計(jì)數(shù)器可被用來對取出的指令進(jìn)行計(jì)數(shù)，以保證能準(zhǔn)確地取出后續(xù)指令。計(jì)數(shù)器也分很多種，有脈沖計(jì)數(shù)器、同步計(jì)數(shù)器、程序計(jì)數(shù)器等。在此僅介紹一種最基本的四位二進(jìn)制脈沖計(jì)數(shù)器，電路原理如下頁圖。,四級二進(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，使對總線無影響，因而多個(gè)器件可同時(shí)連到總線上。,3.4.5譯碼器,譯碼：把某組編碼翻譯為唯一的輸出。譯碼器：有3—8譯碼器，即8選1譯碼器和4～16譯碼器，即16選1譯碼器等多種。,例如：3—8譯碼器，即8選1譯碼器的輸入信號有三個(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)確、可靠。為此一方面需要通過硬件電路的可靠性來保障，另一方面還要在傳輸過程中，需對接收到的數(shù)據(jù)進(jìn)行檢錯(cuò)、糾錯(cuò)，以便發(fā)現(xiàn)和糾正數(shù)據(jù)在傳輸過程中產(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ī)則或算法沒被破壞則表示數(shù)據(jù)傳輸正確，否則表明收到的數(shù)據(jù)信息在傳輸過程中發(fā)生錯(cuò)誤，然后根據(jù)被破壞后編碼信息的某些特征和規(guī)則來判斷，看是哪一位出錯(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ù)傳送過程中奇數(shù)個(gè)數(shù)位出錯(cuò)的情況；2、實(shí)際中兩位同時(shí)出錯(cuò)的概率極低，奇偶校驗(yàn)法簡便可靠易行，但它只能發(fā)現(xiàn)錯(cuò)誤，卻不知錯(cuò)在何處，因而不能自動(dòng)糾正。,例如一個(gè)實(shí)用的8-Bits數(shù)據(jù)奇偶校驗(yàn)與奇偶校驗(yàn)碼形成電路，其中數(shù)據(jù)用D7┄D0表示，校驗(yàn)位用P表示。,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,PD7D6D5D4D3D2D1D0,,,P奇形成,P偶形成,P奇校錯(cuò),P偶校錯(cuò),3.5.2循環(huán)冗余碼（CRC碼）,循環(huán)冗余校驗(yàn)方式：通過某種數(shù)學(xué)公式建立信息位和校驗(yàn)位之間的約定關(guān)系——能夠校驗(yàn)傳送信息的對錯(cuò)，并且能自動(dòng)修正錯(cuò)誤。廣泛用于通信和磁介存儲(chǔ)器中。CRC編碼格式是在k位信息后加r位檢驗(yàn)碼。NN-121信息位（k位）校驗(yàn)位（r位）,C1C2…...CKr1r2……ri,,,,,,,,,,,,,,,1、CRC碼的編碼方法,CRC整個(gè)編碼長度為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碼送給對方。當(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=n–k=3位即：將上式模2(無進(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則傳輸無誤，否則傳輸錯(cuò)誤，根據(jù)所得余數(shù)值就可找出錯(cuò)誤并取反糾正。上表詳細(xì)說明了CRC碼1001110在傳送時(shí)某一位出錯(cuò)后的判斷與糾正方法[C(X)=1001、G(x)=1011]。,3、生成多項(xiàng)式G（x）的確定,G(x)是一個(gè)約定的除數(shù)，用來產(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),