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

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