第2章計算機中數(shù)的表示及基本邏輯部件

1907-2007第二章計算機中數(shù)的表示及基本邏輯部件

高年同滁-----------------------

TONGJIUNIVERSITY

2.1數(shù)據(jù)信息在機器中的表示

2.2數(shù)據(jù)的校驗方法

2.3寄存器

2.4多路選擇器

2.5移位器

2.6譯碼器

2.7計數(shù)器

同濟大學電信學院

第二章計算機中數(shù)的表示及基本邏輯部件

苞年◎稱

TONGJIUNIVERSITY

2.8節(jié)拍分配器

2.9總線

2.10加法器

2.11進位鏈

同濟大學電信學院

主要知識點

苞年◎稱

TONGJIUNIVERSITY

■掌握定點數(shù)、浮點數(shù)、原碼、反碼、補碼

和移碼的表示

■掌握數(shù)據(jù)的校驗方法及原理

■掌握常用的邏輯部件的工作原理

■掌握加法器進位鏈的工作原理

同濟大學電信學院

2.1數(shù)據(jù)信息在機器中的表示

苞年向解、

TONGJIUNIVERSITY

計算機中的數(shù)據(jù)簡稱為機器數(shù)，一個完

整的機器數(shù)一般應(yīng)含有三個方面：符號、數(shù)值

和小數(shù)點。

2.1.1數(shù)的定點和浮點表示

在計算機中按機器數(shù)的小數(shù)點位置是否

固定，把數(shù)分成定點表示和浮點表示兩種。

同濟大學電信學院

2.1數(shù)據(jù)信息在機器中的表示

2.2.1數(shù)的定點和浮點表示

苞年◎稱

TONGJIUNIVERSITY

1.定點表示法

定點表示法約定機器中所有數(shù)據(jù)的小數(shù)

點位置固定不變，一般采用兩種簡單的約定。

(1)定點小數(shù)

小數(shù)點放在最高數(shù)位之前，符號位之后。

Xn-lX0

Xs：符號位

小數(shù)點

Xn-1-XO：數(shù)值部分

同濟大學電信學院

1907-20072.1數(shù)據(jù)信息在機器中的表示

2.1.1數(shù)的定點和浮點表示

苞年◎稱

TONGJIUNIVERSITY

假定機器字長為n位，其中一位符號位,

其n-l位是有效數(shù)值位，則定點小數(shù)能表示

的數(shù)值范圍為：

-（1-2-（N-D）WXW1-2-（NT）

即：-o.iiimi?-??1?o.limn---?1

\n-l/\n-l/

同濟大學電信學院

1907-20072.1數(shù)據(jù)信息在機器中的表示

頤92.1.1數(shù)的定點和浮點表示

苞年◎稱

TONGJIUNIVERSITY

(2)定點整數(shù)

小數(shù)點的位置在數(shù)的最低位之后，即參

與運算的數(shù)是純整數(shù)。

XsXn-1XO

Xs：符號位

Xn-1—X0：數(shù)值部分小數(shù)點

同濟大學電信學院

1907-20072.1數(shù)據(jù)信息在機器中的表示

2.1.1數(shù)的定點和浮點表示

苞年◎稱

TONGJIUNIVERSITY

假定機器字長為n位，其中一位符號位,

其n-l位是有效數(shù)值位，則定點整數(shù)能表示

的數(shù)值范圍為：

-2n-1-lWXW2n-i-l

即：-1111111--??1?1111111--??1

\n-l/\nT/

同濟大學電信學院

1907-20072.1數(shù)據(jù)信息在機器中的表示

頤92.1.1數(shù)的定點和浮點表示

苞年◎稱

TONGJIUNIVERSITY

2.數(shù)的浮點表示

在浮點藪的表示中，由于小數(shù)點的位

置是變動的，所以，要用一種方法來表示

小數(shù)點的位置。

例：

435=0.435X103

110101.11010=0.11010111010X2110

同濟大學電信學院

1907-20072.1數(shù)據(jù)信息在機器中的表示

2.1.1數(shù)的定點和浮點表示

苞年◎稱

TONGJIUNIVERSITY

一般地，任何一個數(shù)都可以寫成:

X=±Sxb±N

b-進位基數(shù)

±N—階

±S—尾數(shù)

同濟大學電信學院

1907-20072.1數(shù)據(jù)信息在機器中的表示

頤92.1.1數(shù)的定點和浮點表示

苞年◎稱

TONGJIUNIVERSITY在計算機中浮點數(shù)表示為：

110

D150.11O1O111O1OX2DO

0110011010111010

t\_________________________________________________________________________/

\_<

—

階

階

尾

尾

值

數(shù)

符

符

D15Do

0011011010111010

階階

符值

同濟大學電信學院

1907-20072.1數(shù)據(jù)信息在機器中的表示

頤92.1.1數(shù)的定點和浮點表示

苞年◎稱

TONGJIUNIVERSITY

■尾數(shù)是一個純小數(shù)，尾數(shù)的位數(shù)越多，精

度越高。整個浮點數(shù)的正負號由尾符決定。

■階值是一個純整數(shù)，階符表示數(shù)的實際小

數(shù)點位置的方向，若階符為正，則實際小數(shù)

點在假象小數(shù)點的右邊，若階符為負，則實

際小數(shù)點在假象小數(shù)點的左邊，其具體位置

由階值確定。麻值的位數(shù)越多，數(shù)的表示范

圍就越大。

同濟大學電信學院

1907-20072.1數(shù)據(jù)信息在機器中的表示

2.1.1數(shù)的定點和浮點表示

高年同滁-----------------------------------

根據(jù)IEEE754國際標準，常用的浮

點數(shù)看兩種格式：

（1）單精度浮點數(shù)（32位），階碼8位（內(nèi)

含1位符號位）,尾數(shù)24位（內(nèi)含1位符號

位）。

（2）雙精度浮點數(shù)（64位），階碼11位（內(nèi)

含1位符號位），尾數(shù)53位（內(nèi)含1位符號

位）。

同濟大學電信學院

1907-20072.1數(shù)據(jù)信息在機器中的表示

頤92.1.1數(shù)的定點和浮點表示

苞年◎稱

TONGJIUNIVERSITY

3.浮點數(shù)規(guī)格化和溢出

浮點數(shù)分為規(guī)格化浮點數(shù)和非規(guī)格化浮點

數(shù)，在計算機中常用的是規(guī)格化浮點數(shù)。

規(guī)格化的目的:提高數(shù)的表示精度。

所謂的規(guī)格化尾數(shù)：就是尾數(shù)的最高有效

位和符號位相反（補碼表示的尾數(shù)），即尾數(shù)

值不為0時，其絕對值應(yīng)大于或等于（0.5）口。

1/2W|S|VI

同濟大學電信學院

1907-20072.1數(shù)據(jù)信息在機器中的表示

頤92.1.1數(shù)的定點和浮點表示

苞年◎稱

TONGJIUNIVERSITY

例:正尾數(shù)0.OXXXXXXXX非規(guī)格化數(shù)

0.1XXXXXXXX規(guī)格化數(shù)

負尾數(shù)1.1XXXXXXXX非規(guī)格化數(shù)

1.OXXXXXXXX規(guī)格化數(shù)

注:以上的尾數(shù)是以補碼表示O

同濟大學電信學院

1907-20072.1數(shù)據(jù)信息在機器中的表示

2.1.1數(shù)的定點和浮點表示

高年同滁------------------------------------

TONGJIUNIVERSITY

浮點數(shù)的溢出有尾數(shù)溢出和階值溢出。

尾數(shù)發(fā)生溢出時，可以用尾數(shù)右移一位，

而階值加一，就消除尾數(shù)溢出。

階值發(fā)生溢出時，又分為“下溢”和“上

溢”，當階碼的值超出機器中能表示的最小值

時，稱為“下溢”，一般把該浮點數(shù)作為0處

理，稱為機器零。當階碼的值超出機器中能表

示的最大值時，稱為“上溢”。

同濟大學電信學院

1907-20072.1數(shù)據(jù)信息在機器中的表示

頤92.1.2機器數(shù)的編碼表示

苞年◎稱

TONGJIUNIVERSITY

2.1.2機器數(shù)的編碼表示

1.帶符號數(shù)的表示

一般情況下，通常用二進制數(shù)的最高位表

示數(shù)的符號，把一個數(shù)及符號在機器中的表示

加以數(shù)值化，這樣的數(shù)稱為機器數(shù)，而機器數(shù)

所表示的數(shù)稱為該機器數(shù)的真值。

同濟大學電信學院

1907-20072.1數(shù)據(jù)信息在機器中的表示

頤J2.1.2機器數(shù)的編碼表示

高年同滁------------------------------------

TONGJIUNIVERSITY

(1)原碼

機器數(shù)的最高位為符號位，。表示正數(shù)，1

表示負數(shù)，數(shù)值跟隨其后，并以絕對值形式給

出。這是與真值最接近的一種表示形式。

原碼的定義：

X0WXW211"-I

［x］原=

2n“+|X|-(2f)WXW0

即［X］原=符號位+IXIo

同濟大學電信學院

1907-20072.1數(shù)據(jù)信息在機器中的表示

頤92.1.2機器數(shù)的編碼表示

苞年◎稱

TONGJIUNIVERSITY

例：設(shè)字長n=8

X=+1011000,[X]原=01011000;

X=-1011000,[X]原=11011000。

同濟大學電信學院

1907-20072.1數(shù)據(jù)信息在機器中的表示

頤92.1.2機器數(shù)的編碼表示

苞年◎稱

TONGJIUNIVERSITY

根據(jù)定義，當X=-1011000時，

[X]原=2^+1XI=10000000+1-10110001

=1.1011000o

數(shù)值零的真值有+0和-0兩種表示形式,

[X]原也有兩種表示形式：

[+0]原=00000000

[-0]原=10000000。

同濟大學電信學院

1907-20072.1數(shù)據(jù)信息在機器中的表示

2.1.2機器數(shù)的編碼表示

高年同滁----------------------------------

TONGJIUNIVERSITY

(2)反碼

反碼的定義：

」

fX0WXW2"

[X]反=?

[(2%1)-|X|?(2n.i?l)WXW0

例：設(shè)字長n=8

X=+1011000,[X]反=01011000;

同濟大學電信學院

1907-20072.1數(shù)據(jù)信息在機器中的表示

2.1.2機器數(shù)的編碼表示

苞年◎稱

TONGJIUNIVERSITY

X=-1011000,

[X](2n-l)-|X|=(2M)-1-10110001

=(100000000-1)-1011000=11111111-1011000

=10100111

反碼零有兩種表示形式：

[+0]反=00000000

[-0]反=11111111

同濟大學電信學院

2.1數(shù)據(jù)信息在機器中的表示

2.1.2機器數(shù)的編碼表示

苞年◎稱

TONGJIUNIVERSITY

(3)補碼

補碼的定義:

owxd

-2n4^X<0

例：設(shè)字長n=8

X=+1O11OOO,[X]補=01011000;

同濟大學電信學院

1907-20072.1數(shù)據(jù)信息在機器中的表示

2.1.2機器數(shù)的編碼表示

苞年◎稱

TONGJIUNIVERSITY

X=-1011000,

[X]補=2n-|X|=28-|-1011000|

=100000000-1011000=10101000

補碼零有唯一的表示形式：

[+0]補=[-0]補=00000000

同濟大學電信學院

1907-20072.1數(shù)據(jù)信息在機器中的表示

2.1.2機器數(shù)的編碼表示

高年同滁--------

TONGJIUNIVERSITY

(4)移碼

移碼的定義:

[X]移=l^+X-2n-1^X<2nd

例：設(shè)字長n=8,X=+1011000

[X]^=2n-1+X=10000000+1011000

=11011000

同濟大學電信學院

1907-20072.1數(shù)據(jù)信息在機器中的表示

2.1.2機器數(shù)的編碼表示

高年同滁--------------------------------

TONGJIUNIVERSITY

X=-1011000,

[X]移=2n-i+X=10000000+(-1011000)

=10000000-1011000=00101000

移碼零有唯一的表示形式：

[+0]移=[-0]移=10000000

移碼的正數(shù)時，符號用“1”表示

移碼的負數(shù)時，符號用“0”表示

同濟大學電信學院

2.1數(shù)據(jù)信息在機器中的表示

2.1.2機器數(shù)的編碼表示

苞年◎稱

TONGJIUNIVERSITY

⑸浮點數(shù)常用編碼

尾數(shù)可用原碼、補碼，常用補碼。

階值可用原碼、補碼、移碼，常用移碼。

2.BCD碼

用四位二進制表示十進制。

0000050101

1000160110

2001070111

3001181000

4010091001

同濟大學電信學院

1907-20072.1數(shù)據(jù)信息在機器中的表示

2.1.2機器數(shù)的編碼表示

高年同滁----------------------------------

TONGJIUNIVERSITY

3.字符編碼

美國信息交換標準代碼ASCH使用的最

普遍，一般用8位二進制表示一個字符。

同濟大學電信學院

1907-20072.1數(shù)據(jù)信息在機器中的表示

頤92.1.3數(shù)據(jù)校驗方法

苞年◎稱

TONGJIUNIVERSITY

2.1.3數(shù)據(jù)校驗方法

計算機系統(tǒng)中的數(shù)據(jù)，在讀寫、存取和

傳送的過程中可能產(chǎn)生錯誤。為減少和避免

這類錯誤，一方面是精心設(shè)計各種電路，提

高計算機硬件的可靠性；另一方面是在數(shù)據(jù)

編碼上找出路，即采用某種編碼法，通過少

量的附加電路，使之能發(fā)現(xiàn)某些錯誤，甚至

能確定出錯位置，進而實現(xiàn)自動改錯的能力。

同濟大學電信學院

1907-20072.1數(shù)據(jù)信息在機器中的表示

頤92.1.3數(shù)據(jù)校驗方法

苞年◎稱

TONGJIUNIVERSITY

數(shù)據(jù)校驗碼是一種常用的帶有發(fā)現(xiàn)某些

錯誤或自動改錯能力的數(shù)據(jù)編碼方法。它的

實現(xiàn)原理，是加進一些冗余碼，使合法數(shù)據(jù)

編碼出現(xiàn)某些錯誤時，就成為非法編碼。這

樣，就可以通過檢測編碼的合法性來達到發(fā)

現(xiàn)錯誤的目的。合理地安排非法編碼數(shù)量和

編碼規(guī)則，就可以提高發(fā)現(xiàn)錯誤的能力，或

自動改正錯誤的目的。這里用到一個碼距的

概念。

同濟大學電信學院

1907-20072.1數(shù)據(jù)信息在機器中的表示

頤92.1.3數(shù)據(jù)校驗方法

苞年◎稱

TONGJIUNIVERSITY

1.碼距

碼距一是根據(jù)任意兩個合法碼之間至

少有幾個二進制位不相同而確定的，不相

同的位數(shù)稱為此編碼的碼距。

例:于位二進制數(shù)有16種不同的編碼，在

這16種編碼中的任意兩個編碼之間，僅有

一位不相同，其碼距為L

00000001001000110100010101100111

10001001101010111100110111101111

同濟大學電信學院

1907-20072.1數(shù)據(jù)信息在機器中的表示

頤92.1.3數(shù)據(jù)校驗方法

苞年◎稱

TONGJIUNIVERSITY

碼距為1的編碼是不能發(fā)現(xiàn)錯誤的。

一般來說，合理地增大碼距，就能提

高發(fā)現(xiàn)錯誤的能力，但編碼所使用的二進

制位數(shù)變多，增加了數(shù)據(jù)存儲的容量或數(shù)

據(jù)傳送的數(shù)量。

0001001001000111

1000101111011110

同濟大學電信學院

1907-20072.1數(shù)據(jù)信息在機器中的表示

頤92.1.3數(shù)據(jù)校驗方法

苞年◎稱

TONGJIUNIVERSITY

在確定與使用數(shù)據(jù)校驗碼的時候，通

常要考慮在不過多增加硬件開銷的情況下,

盡可能發(fā)現(xiàn)或改正更多的錯誤。

所以碼距大于1的編碼才能發(fā)現(xiàn)錯誤

或校正錯誤。

同濟大學電信學院

1907-20072.1數(shù)據(jù)信息在機器中的表示

頤92.1.3數(shù)據(jù)校驗方法

苞年◎稱

TONGJIUNIVERSITY

2.奇偶校驗

奇偶校驗碼是一種開銷最小，能發(fā)現(xiàn)

數(shù)據(jù)代碼中一位出錯情況的編碼，常用于

存儲器讀寫檢查，或ASCH字符傳送過程中

的檢查。它的實現(xiàn)原理，是使碼距由1增加

到2。若編碼中有一個二進制位的值出錯了,

由1變成0,或由0變成1,這個碼都將成為

非法編碼。

同濟大學電信學院

1907-20072.1數(shù)據(jù)信息在機器中的表示

頤92.1.3數(shù)據(jù)校驗方法

苞年◎稱

TONGJIUNIVERSITY

實現(xiàn)的具體方法，通常是為一個字節(jié)

補充一個二進制位，稱為校驗位，用設(shè)置

校驗位的值為0或1,使字節(jié)的8位和該校驗

位含有1值的個數(shù)為奇數(shù)或偶數(shù)。在使用奇

數(shù)個1的方案進行校驗時，稱為奇校驗，反

之，則稱為偶極驗。

同濟大學電信學院

1907-20072.1數(shù)據(jù)信息在機器中的表示

2.1.3數(shù)據(jù)校驗方法

苞年◎稱

TONGJIUNIVERSITY

例：以四位二進制編碼為例。

00000001001000110100010101100111

10001001101010111100110111101111

奇校驗

0000100010001000011101000010110110101110

1000010011101011011011001110101110011111

偶校驗

0000000011001010011001001010100110001111

1000110010101001011111000110111110111110

同濟大學電信學院

1907-20072.1數(shù)據(jù)信息在機器中的表示

頤92.1.3數(shù)據(jù)校驗方法

苞年◎稱

TONGJIUNIVERSITY

奇偶校驗位的實現(xiàn)邏輯電路如下:

奇校驗位偶校驗位偶校驗奇校驗

形成形成出錯出偌

同濟大學電信學院

1907-20072.1數(shù)據(jù)信息在機器中的表示

頤92.1.3數(shù)據(jù)校驗方法

苞年◎稱

TONGJIUNIVERSITY

3.交叉校驗

當一次傳送一^個數(shù)據(jù)塊時，如果不但

對每一個字節(jié)設(shè)有奇偶校驗位（橫向校

驗），而且全部字節(jié)的同一位也設(shè)置一個

奇偶校驗位（縱向校驗），對數(shù)據(jù)塊的橫

面和縱向代碼同時校驗。

同濟大學電信學院

2.1數(shù)據(jù)信息在機器中的表示

2.1.3數(shù)據(jù)校驗方法

TONGJIUNIVERSITY

例：有四個字節(jié)組成的數(shù)據(jù)塊，縱橫向均

采用奇校驗。

D7D6D5D4D3D2D1D。櫻

數(shù)據(jù)1100110011

數(shù)據(jù)2001011000

數(shù)據(jù)3111001111

數(shù)據(jù)4011111101

縱向校

驗位1000110

同濟大學電信學院

1907-20072.1數(shù)據(jù)信息在機器中的表示

頤92.1.3數(shù)據(jù)校驗方法

苞年◎稱

TONGJIUNIVERSITY

4.循環(huán)冗余校驗(CRC)碼

二進制信息位流沿一條線逐位在部件

之間或計算機之間傳送稱為串行傳送。

CRC(cyclicredundancycheck)碼可以發(fā)

現(xiàn)并糾正信息存儲或傳送過程中連續(xù)出現(xiàn)

的多位錯誤，因此在磁介質(zhì)存儲和計算機

之間通信方面得到廣泛應(yīng)用。

同濟大學電信學院

1907-20072.1數(shù)據(jù)信息在機器中的表示

2.1.3數(shù)據(jù)校驗方法

高年同滁----------------------------------

TONGJIUNIVERSITY

CRC碼一般是指k位信息碼之后拼接r位

校驗碼。

應(yīng)用CRC碼的關(guān)鍵是如何從k位信息位

簡便地得到r位校驗位（編碼）,以及如何從

k+r位信息碼判斷是否出錯。

下面僅就CRC碼應(yīng)用中的問題做簡單介

紹。

同濟大學電信學院

1907-20072.1數(shù)據(jù)信息在機器中的表示

頤92.1.3數(shù)據(jù)校驗方法

苞年◎稱

TONGJIUNIVERSITY

(1)CRC碼的編碼方法

在CRC碼的編碼中，要用到的模2運算。

模2運算是指以按位模2相加為基礎(chǔ)的四則

運算，運算時不考慮進位和借位。

①模2加減：即按位加，可用異或邏輯實

現(xiàn)。模2加與模2減的結(jié)果相同，即

0±0=0,0±1=1,1±0=1,l±l=0o兩

個相同的數(shù)據(jù)的模2和為0。

②模2乘一一按模2加求部分積之和。

同濟大學電信學院

2.1數(shù)據(jù)信息在機器中的表示

2.1.3數(shù)據(jù)校驗方法

苞年◎稱

TONGJIUNIVERSITY

例:1010乘以101。

1010

x101

1010

0000

1010

100010

同濟大學電信學院

1907-20072.1數(shù)據(jù)信息在機器中的表示

2.1.3數(shù)據(jù)校驗方法

高年同滁-----------------------------------

TONGJIUNIVERSITY

③模2除---按模2減求部分余數(shù)。每求一

位商應(yīng)使部分余數(shù)減少一位。上商的原

則是：當部分余數(shù)的首位為1時，商取1；

當部分余數(shù)的首位為。時，商取0。當部

分的余數(shù)的位數(shù)小于除數(shù)的位數(shù)時，該

余數(shù)即為最后余數(shù)。

同濟大學電信學院

2.1數(shù)據(jù)信息在機器中的表示

2.1.3數(shù)據(jù)校驗方法

苞年◎稱

TONGJIUNIVERSITY

例：1110除以101。

11

101J1110

101

100

101

01

同濟大學電信學院

1907-20072.1數(shù)據(jù)信息在機器中的表示

頤92.1.3數(shù)據(jù)校驗方法

苞年◎稱

TONGJIUNIVERSITY

CRC碼的編碼方法：

設(shè)被校驗數(shù)據(jù)M(x)是由n位二進制組成,

M(x)=C_xn-1+C_xn-2+...+Cxi+...+Cx+C

1n11JL1n1&2JLi.Lv10

式中Ci為0或L

將M(x)信息位左移k位后，被一個約定的生成多

項式G(x)相除，G(x)必須是k+1位二進制組成，

相除后得到k位余數(shù)就是校驗位。將k位余數(shù)拼

接到n位的M(x)后面，即形成n+k位長的循環(huán)冗余

校驗碼，稱為(n+k,n)碼，因此所得CRC碼可被

G(x)表示的數(shù)碼除盡。

同濟大學電信學院

1907-20072.1數(shù)據(jù)信息在機器中的表示

頤92.1.3數(shù)據(jù)校驗方法

苞年◎稱

TONGJIUNIVERSITY

例：對4位有效信息M(x)=1100,求循環(huán)校驗

編碼，選擇生成多項式G(x)=1011。

M(x)=x3+x2=1100

(n=4)

M(x)-x3=x6+x5=1100000(左移k=3位)

G(x)=x3+x+l=1011(k+l=4位)

M(x)?x3/G(x)=1100000/1011(模2除)

結(jié)果：余數(shù)=010,商=1110

同濟大學電信學院

1907-20072.1數(shù)據(jù)信息在機器中的表示

2.1.3數(shù)據(jù)校驗方法

高年同滁---------------------------------

TONGJIUNIVERSITY

將余數(shù)拼接到M(x)上，即得到CRC校驗碼。

M(x)的CRC校驗碼：

CRC校驗碼=1100000+010=1100010

(模2加)

將編好的循環(huán)校驗碼稱為(7,4)碼，即

n=7,k=4o

同濟大學電信學院

1907-20072.1數(shù)據(jù)信息在機器中的表示

頤92.1.3數(shù)據(jù)校驗方法

苞年◎稱

TONGJIUNIVERSITY

(2)CRC的糾錯原理

將收到的循環(huán)校驗碼用約定的生成多

項式G(x)去除，如果循環(huán)校驗碼無誤則余

數(shù)應(yīng)為0,如有某一位出錯，則余數(shù)不為0,

不同位數(shù)出錯余數(shù)不同。如下表給出的關(guān)

系可作為(7,4)碼的判別依據(jù)。

同濟大學電信學院

1907-20072.1數(shù)據(jù)信息在機器中的表示

頤

92.1.3數(shù)據(jù)校驗方法

苞年◎稱

TONGJIUNIVERSITY

(7,4)循環(huán)碼的出錯模式(生成多項式G(x)=1011)

余數(shù)出錯位

D6D5D4D3D2DIDo

正確1100010000無

1100011001Do

1100000010Di

1100110100

D2

錯誤1101010OilD3

1110010110D4

1000010111D5

0100010101

D6

同濟大學電信學院

1907-20072.1數(shù)據(jù)信息在機器中的表示

頤92.1.3數(shù)據(jù)校驗方法

苞年◎稱

TONGJIUNIVERSITY

更換不同的待測碼字可以證明：余數(shù)

與出錯位的對應(yīng)關(guān)系是不變的，只與碼制

和生成多項式有關(guān)。

對于其他碼制或選用其他生成多項式,

出錯模式將發(fā)生變化。

同濟大學電信學院

1907-20072.1數(shù)據(jù)信息在機器中的表示

2.1.3數(shù)據(jù)校驗方法

高年同滁----------------------------------

TONGJIUNIVERSITY

(3)生成多項式

并不是任何一個(k+1)位多項式都可

以作為生成多項式的。從檢錯及糾錯的要

求出發(fā)，生成多項式應(yīng)能滿足下列要求：

①任何一位發(fā)生錯誤都應(yīng)使余數(shù)不為0。

②不同位發(fā)生錯誤應(yīng)當使余數(shù)不同。

③對余數(shù)繼續(xù)作模2除，應(yīng)使余數(shù)循環(huán)。

同濟大學電信學院

1907-20072.1數(shù)據(jù)信息在機器中的表示

2.1.3數(shù)據(jù)校驗方法

高年同滁----------

TONGJIUNIVERSITY

常用多項式

名稱G(x)多項式G(x)二進制碼

CRC-5-USBH+x2+1(用途：USB信令包)100101

CRC-7X7+X3+1(用途：通信系統(tǒng))10001001

CRC-8-ATM川+x2+x+1（用途：ATMHEC）100000111

X12+X11+X3+X2+X+1

CRC-121100000001111

（用途：通信系統(tǒng)）

x16+x12+x5+1（X25,V41,

CRC-16-CCITT10001000000100001

Bluetooth,PPP,IrDA）

CRC-16-IBMX16+X15+X2+111000000000000101

CRC-32-IEEEA32+X26+X23+X22+X16+X12+X11+100000100110000010

802.3X10+X8+X7+A6+A4+X2+X+1001110110110111

同濟大學電信學院

1907-20072.1數(shù)據(jù)信息在機器中的表示

頤92.1.3數(shù)據(jù)校驗方法

苞年◎稱

TONGJIUNIVERSITY

5.海明校驗碼

這是由RichardHamming于1950年提出的、

目前還被廣泛采用。

實現(xiàn)原理：

是在數(shù)據(jù)中加入幾個校驗位，并把數(shù)據(jù)的

每一個二進制位分配在幾個奇偶校驗組中。當

某一位出錯后，就會引起有關(guān)的幾個校驗組的

值發(fā)生變化，這不但可以發(fā)現(xiàn)出錯，還能指出

是哪一位出錯，為自動糾錯提供了依據(jù)。

同濟大學電信學院

1907-20072.1數(shù)據(jù)信息在機器中的表示

2.1.3數(shù)據(jù)校驗方法

苞年◎稱

TONGJIUNIVERSITY

同濟大學電信學院

1907-20072.1數(shù)據(jù)信息在機器中的表示

頤92.1.3數(shù)據(jù)校驗方法

苞年◎稱

TONGJIUNIVERSITY

假設(shè)校驗位的個數(shù)為r,則它能表示2r個

信息（21編碼），用其中的一個信息（編碼）

指出“沒有錯誤”，其余的2-1個信息（編碼）

指出錯誤發(fā)生在哪一位。然而錯誤也可能發(fā)生

在校驗位，因此只有k=2J「r個信息能用于糾

正被傳送數(shù)據(jù)的位數(shù)，也就是說要滿足關(guān)系：

2r>k+r+1o

例：假如校驗位有4位，貝世=24-1-4=11,即

被校驗的數(shù)據(jù)位最長為11位。

同濟大學電信學院

1907-20072.1數(shù)據(jù)信息在機器中的表示

2.1.3數(shù)據(jù)校驗方法

高年同滁-----------------------------------

.■一

TONGJIUNIVERSITY如.要能檢測與自?動校正一位錯，并發(fā)B

現(xiàn)兩位錯，此時校驗位的位數(shù)r和數(shù)據(jù)位

的位數(shù)k應(yīng)滿足下述關(guān)系：21》k+r

數(shù)據(jù)位k與校驗位r的對應(yīng)關(guān)系如表：

k值（數(shù)據(jù)位）最小的r值（校驗位）

1?44

5?115

12?266

27?577

58?1208

同濟大學電信學院

1907-20072.1數(shù)據(jù)信息在機器中的表示

頤92.1.3數(shù)據(jù)校驗方法

TONGJIUNIVERSITY

(1)海明碼編碼規(guī)則

若海明碼的最高位號為m,最低位號為1,

即H1nHmT.?.H2HI，則此海明碼的編碼規(guī)律通常是:

①校驗位與數(shù)據(jù)位之和為m,每個校驗位Pi在

海明碼中被分在位號21的位置，其余各位

為數(shù)據(jù)位，并按從低向高逐位依次排列的

關(guān)系分配各數(shù)據(jù)位。

同濟大學電信學院

1907-20072.1數(shù)據(jù)信息在機器中的表示

2.1.3數(shù)據(jù)校驗方法

高年同滁-------------------------------------

TONGJIUNIVERSITY

②海明碼的每一位碼Hj（包括數(shù)據(jù)位和校驗

位本身）由多個校驗位校驗，其關(guān)系是被

校驗的每一位位號要等于校驗它的各校驗

位的位號之和。

例：設(shè)校驗位為4位，P4P3P2PP被校驗的數(shù)據(jù)

位是11位，D10D9D8D7D6D5D4D3D2D1D0,生成海明碼。

生成的海明碼：

HI5H1411131112HII1110119H8H7H6H5114H3H2III

D10D9D8D7D6D5D4P4D3D2D1P3DOP2Pl

同濟大學電信學院

被校驗位的海明碼

參與校驗的校驗位

海明碼位號數(shù)據(jù)位/校驗位位號二參與校驗位位

位號

號之和

珥Pi11=1

22=2

H2P2

3=1+2

H3D°1,2

44=4

H4P3

1,45=1+4

H5□

2,46=2+4

H6D2

1,2,47=1+2+4

H7D3

88=8

H8P4

9-1+8

H9D41,8

HIO2,810=2+8

D5

1,2,811=1+2+8

HuD6

4,812=4+8

H12D7

1,4,813=1+4+8

H13D8

H14D92,4,814=2+4+8

1,2,4,815=1+2+4+8

H15Dio

1907-20072.1數(shù)據(jù)信息在機器中的表示

2.1.3數(shù)據(jù)校驗方法

高年同滁--------------------------------------

TONGJIUNIVERSITY

③校驗位P4P3P2Pl值得確定。

校驗位Pi的取值就是該校驗位所校驗的數(shù)據(jù)

位的異或。

Pi=D0?D?D?D?D?D?

13468D1O

?D?D?D?D?D?D

P2=DO23569lo

P3=D1?D2?D3?D7?D8?D9?D10

P4=D4?D5?D6?D7?D8?D9?D10

這時P4P3P2Pl的取值是采用偶校驗，當采用

奇校驗時,P4P3P2Pl取偶校驗值得反。

同濟大學電信學院

1907-20072.1數(shù)據(jù)信息在機器中的表示

頤92.1.3數(shù)據(jù)校驗方法

苞年◎稱

TONGJIUNIVERSITY

(2)海明碼校驗和糾錯

Si=D()十Di十D3十D4十口6十Dg十D10?Pi

S2=D0十D2十D3十D5十口6十D9十D10?P2

$3=D1?D2?D3?D7?D8?D9?D10十P3

S4=D4十D5十口6十D7十口8十D9十D10?P4

采用偶校驗時，S1S2s3s4的值為0000,則

傳送正確。否則傳送錯誤。

采用奇校驗時，S1S2s3s4的值為1111,則

傳送正確。否則傳送錯誤。

同濟大學電信學院

1907-20072.1數(shù)據(jù)信息在機器中的表示

2.1.3數(shù)據(jù)校驗方法

高年同滁-------------------------------------

TONGJIUNIVERSITY

當傳送發(fā)生錯誤時（以偶校驗為例），假

設(shè)S1S2s3s4=0011,說明是P3P4同時校驗的那位

數(shù)據(jù)位出錯。P3P4同時校驗的數(shù)據(jù)位是D7出錯,

所以，只要將該位取反就可糾錯。

例：請寫出被校驗數(shù)據(jù)10110100110的海明碼,

采用4位校驗位和偶校驗。

同濟大學電信學院

1907-20072.1數(shù)據(jù)信息在機器中的表示

2.1.3數(shù)據(jù)校驗方法

高年同滁---------------------------------------

TONGJIUNIVERSITY

已知：口10口9口8。7口6口5口4口3口2口衛(wèi)0=10110100110

Pi=0?1?0?0?0?1?1=1

十十十十十十

P2=0101001=1

PR=1?1?0?1?1?0?1=1

十十十

P4=o101=0

生成海明碼：

H15H141113H12IIH1110H9H8H7H6H5114H3112HI

101101000111011

DIOD9D8D7D6D5D4P4D3D2DIP3DOP2Pl

同濟大學電信學院

2.1數(shù)據(jù)信息在機器中的表示

2.1.3數(shù)據(jù)校驗方法

苞年◎稱

TONGJIUNIVERSITY

如在傳送中未產(chǎn)生錯誤，則：

Si=O?1?O?O?O@1?1?1(PJ=0

S9=0十1十0十1十0十0十1十1(P2)=0

Sq=l?1?0?1?1?0?1?1(P3)=0

十十十十十。十十

S4=0101110(P4)=0

如產(chǎn)生錯誤，Do出錯

H15H14H13H12Hll1110119118117116H5H4H3H2Hl

101101000111111

DIOD9D8D7D6D5D4P4D3D2DIP3DOP2Pl

同濟大學電信學院

1907-20072.1數(shù)據(jù)信息在機器中的表示

2.1.3數(shù)據(jù)校驗方法

百年◎歌-------

TONGJIUNIVERSITY

Pl=D0?Dl

P2=D0?D2

P產(chǎn)DI十D?

P4=D4?D5

Pi=0?1?0?0?0?1?1=1

P9=0?1?0?1?0?0?1=1

P3=l?1?0?1?1?0?1=1

P4=0?l?0?l?l?0?1=0

同濟大學電信學院

1907-20072.1數(shù)據(jù)信息在機器中的表示

2.1.3數(shù)據(jù)校驗方法

苞年◎稱

TONGJIUNIVERSITY

Sx=l十1十0十0十0十1十1十1出)=1

S9=l?1?0?1?0?0?1?1(P7)=1

S3=l十1十0十1十1十0十1十1(P3)=0

S4=0?1?0?1?1?0?1?0(P