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

苞年◎稱

TONGJIUNIVERSITY

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

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

2.3寄存器

2.4多路選擇器

2.5移位器

2.6譯碼器

2.7計數(shù)器

同濟大學(xué)電信學(xué)院

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

苞年◎稱

TONGJIUNIVERSITY

2.8節(jié)拍分配器

2.9總線

2.10加法器

2.11進位鏈

同濟大學(xué)電信學(xué)院

主要知識點

高年◎稱

TONGJIUNIVERSITY

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

和移碼的表示

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

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

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

同濟大學(xué)電信學(xué)院

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

荀年日降、

TONGJIUNIVERSITY

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

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

和小數(shù)點。

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

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

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

同濟大學(xué)電信學(xué)院

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

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

苞年◎稱

TONGJIUNIVERSITY

1.定點表示法

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

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

(1)定點小數(shù)

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

Xn-1XO

Xs：符號位

小數(shù)點

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

同濟大學(xué)電信學(xué)院

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

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

高年◎稱

TONGJIUNIVERSITY

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

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

的數(shù)值范圍為：

一（1—2-（NT））WXW1-2一'I）

即：—0.??1?0.

\n-17\n-17

同濟大學(xué)電信學(xué)院

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

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

苞年◎稱

TONGJIUNIVERSITY

(2)定點整數(shù)

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

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

XsXn-IXO

Xs：符號位

小數(shù)點

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

同濟大學(xué)電信學(xué)院

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

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

苞年◎稱

TONGJIUNIVERSITY

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

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

的數(shù)值范圍為：

—2*1—1<X<2丘1—1

即：??1???1

\n-l/\n-l/

同濟大學(xué)電信學(xué)院

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

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

苞年◎稱

TONGJIUNIVERSITY

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

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

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

小數(shù)點的位置。

例：

435=0.435X103

110101.11010=0.11010111010X2110

同濟大學(xué)電信學(xué)院

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

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

苞年◎稱

TONGJIUNIVERSITY

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

X=±SXb±N

b-進位基數(shù)

±N—階

+S-尾數(shù)

同濟大學(xué)電信學(xué)院

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

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

百年◎稱

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

110

0.11010111010X2DO

—OOO

t

階

階

尾

尾

值

數(shù)

符

符

D15)0

HO

—

階

階

尾

尾

值

數(shù)

符

符

同濟大學(xué)電信學(xué)院

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

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

高年◎稱

TONGJIUNIVERSITY

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

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

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

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

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

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

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

圍就越大。

同濟大學(xué)電信學(xué)院

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

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

高年◎稱

TONGJIUNIVERSITY

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

點數(shù)有兩種格式:

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

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

位）O

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

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

位）O

同濟大學(xué)電信學(xué)院

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

2.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）Do

1/2<|S|<1

同濟大學(xué)電信學(xué)院

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

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

百年⑼滁

TONGJIUNIVERSITY

例：正尾數(shù)0.0XXXXXXXX非規(guī)格化數(shù)

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

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

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

注：以上的尾數(shù)是以補碼表示。

同濟大學(xué)電信學(xué)院

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

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

苞年◎稱

TONGJIUNIVERSITY

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

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

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

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

溢”,當(dāng)階碼的值超出機器中能表示的最小值

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

理，稱為機器零。當(dāng)階碼的值超出機器中能表

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

同濟大學(xué)電信學(xué)院

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

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

苞年◎稱

TONGJIUNIVERSITY

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

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

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

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

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

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

同濟大學(xué)電信學(xué)院

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

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

苞年◎稱

TONGJIUNIVERSITY

(1)原碼

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

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

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

原碼的定義：

一「XOWXb"-I

[x]原=(

12叫兇?(2n-i/)WXW0

即［X］原=符號位+IX|o

同濟大學(xué)電信學(xué)院

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

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

苞年◎稱

TONGJIUNIVERSITY

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

原

X=+10110005[X]=01011000;

原。

X=-1011000?[X]=11011000

同濟大學(xué)電信學(xué)院

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

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

苞年◎稱

TONGJIUNIVERSITY

根據(jù)定義，當(dāng)X=-1011000時,

[X]原=2nT+|x|=10000000+1-1011000

=1.1011000。

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

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

[+0]’原=00000000

[-0]原=10000000。

同濟大學(xué)電信學(xué)院

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

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

高年◎稱

TONGJIUNIVERSITY

(2)反碼

反碼的定義:

0WXW2、

?(2n-i-l)WXW0

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

反

X=+10110005[X]=01011000;

同濟大學(xué)電信學(xué)院

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

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

苞年◎稱

TONGJIUNIVERSITY

X=-10110005

n8

［乂］反=(2-l)-|X|=(2-1)-|-1011000|

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

=10100111

反碼零有兩種表示形式：

[+0]反=00000000

[-0]反=11111111

同濟大學(xué)電信學(xué)院

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

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

高年◎稱

TONGJIUNIVERSITY

(3)補碼

補碼的定義：

fXowxd

[x]補=]

[2n-|X|-2n-1^X<0

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

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

同濟大學(xué)電信學(xué)院

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

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

高年◎稱

TONGJIUNIVERSITY

X=-10110009

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

=100000000-1011000=10101000

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

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

同濟大學(xué)電信學(xué)院

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

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

苞年◎稱

TONGJIUNIVERSITY

(4)移碼

移碼的定義:

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

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

[X]移=2nT+X=10000000+10n000

=11011000

同濟大學(xué)電信學(xué)院

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

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

苞年◎稱

TONGJIUNIVERSITY

X=-10110009

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

=10000000-1011000=00101000

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

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

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

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

同濟大學(xué)電信學(xué)院

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

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

高年◎稱

TONGJIUNIVERSITY

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

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

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

2.BCD碼

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

0000050101

1000160110

2001070111

3001181000

4010091001

同濟大學(xué)電信學(xué)院

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

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

苞年◎稱

TONGJIUNIVERSITY

3.字符編碼

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

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

同濟大學(xué)電信學(xué)院

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

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

高年◎稱

TONGJIUNIVERSITY

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

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

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

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

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

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

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

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

同濟大學(xué)電信學(xué)院

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

LWif2.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)錯誤的能力，或

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

概念。

同濟大學(xué)電信學(xué)院

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

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

苞年◎稱

TONGJIUNIVERSITY

1.碼距

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

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

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

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

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

一位不相同，其碼距為1。

00000001001000110100010101100111

10001001101010111100110111101111

同濟大學(xué)電信學(xué)院

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

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

苞年◎稱

TONGJIUNIVERSITY

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

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

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

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

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

0001001001000111

1000101111011110

同濟大學(xué)電信學(xué)院

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

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

苞年◎稱

TONGJIUNIVERSITY

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

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

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

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

或校正錯誤。

同濟大學(xué)電信學(xué)院

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

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

苞年◎稱

TONGJIUNIVERSITY

2.奇偶校驗

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

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

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

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

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

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

非法編碼。

同濟大學(xué)電信學(xué)院

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

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

高年◎簾

TONGIIUNIVERSITY

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

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

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

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

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

之,則稱為偶校驗。

同濟大學(xué)電信學(xué)院

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

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

苞年◎稱

TONGJIUNIVERSITY

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

00000001001000110100010101100111

10001001」01010111100110111101111

奇校驗

0000100010001000011101000010110110101110

1000010011101011011011001110101110011111

偶校驗

0000000011001010011001001010100110001111

1000110010101001011111000110111110111110

同濟大學(xué)電信學(xué)院

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

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

高年◎稱

TONGJIUNIVERSITY

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

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

形成形成出錯出錯

同濟大學(xué)電信學(xué)院

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

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

高年◎稱

TONGJIUNIVERSITY

3.交叉校驗

當(dāng)'一次傳送一個數(shù)據(jù)塊時）如果不但

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

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

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

向和縱向代碼同時校驗。

同濟大學(xué)電信學(xué)院

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

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

苞年◎稱

TONGJIUNIVERSITY

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

采用奇校驗。

橫向校

D7D6D5D4D3D2DIDO嚶胃

驗位

數(shù)據(jù)1100110011

數(shù)據(jù)2001011000

數(shù)據(jù)31110011111

數(shù)據(jù)4011111101

縱向校

驗位1101(.)011()

同濟大學(xué)電信學(xué)院

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

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

苞年◎稱

TONGJIUNIVERSITY

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

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

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

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

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

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

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

同濟大學(xué)電信學(xué)院

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

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

苞年◎稱

TONGJIUNIVERSITY

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

校驗碼。

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

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

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

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

紹。

同濟大學(xué)電信學(xué)院

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

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

苞年◎稱

TONGJIUNIVERSITY

(1)CRC碼的編碼方法

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

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

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

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

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

0土0=0)0±1=191土0=1)1±l=0o兩

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

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

同濟大學(xué)電信學(xué)院

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

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

高年◎稱

TONGJIUNIVERSITY

例:1010乘以101。

1010

x101

1010

0000

1010

100010

同濟大學(xué)電信學(xué)院

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

LWif2.1.3數(shù)據(jù)校驗方法

高年◎歌-----------------------------------------------

TONGJIUNIVERSITY

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

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

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

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

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

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

同濟大學(xué)電信學(xué)院

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

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

高年◎稱

TONGJIUNIVERSITY

例:1110除以101。

11

101J1110

101

100

101

01

同濟大學(xué)電信學(xué)院

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

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

苞年◎稱

TONGJIUNIVERSITY

CRC碼的編碼方法：

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

M(x)=C_xn_1+C_2Xn-2+...+0^^...

式中C*n01或1。n

將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ù)碼除盡。

同濟大學(xué)電信學(xué)院

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

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

苞年◎稱

TONGJIUNIVERSITY

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

編碼,選擇生成多項式G(x)=101L

M(x)=x3+x2=ll00

(n=4)

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

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

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

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

同濟大學(xué)電信學(xué)院

1907-2007、2.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

同濟大學(xué)電信學(xué)院

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

LWif2.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ù)。

同濟大學(xué)電信學(xué)院

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

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

苞年◎稱

TONGJIUNIVERSITY

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

余數(shù)出錯位

D6D5D4D3D2DiDo

正確1100010000無

1100011001Do

1100000010Di

1100110100

B2

錯誤1101010011

D3

1110010110

D4

1000010111

D5

0100010101

D6

同濟大學(xué)電信學(xué)院

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

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

苞年◎稱

TONGJIUNIVERSITY

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

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

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

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

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

同濟大學(xué)電信學(xué)院

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

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

苞年◎稱

TONGJIUNIVERSITY

(3)生成多項式

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

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

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

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

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

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

同濟大學(xué)電信學(xué)院

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

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

高年◎稱----------

TONGJIUNIVERSITY

常用多項式

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

CRC-5-USBx5+X2+1(用途：USB信令包)100101

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

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

x12+x11+x3+x2+x+1

CRC-121100000001111

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

x16+x12+X5+1（X25,V.41,

CRC-16-CCITT10001000000100001

Bluetooth,PPP,IrDA）

CRC-16-IBMx16+x15+x2+111000000000000101

CRC-32-IEEEX32+x26+x23+x22+X16+X12+X11+100000100110000010

802.3X10+x8+x7+x5+X4+x2+X+1001110110110111

同濟大學(xué)電信學(xué)院

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

LWif2.1.3數(shù)據(jù)校驗方法

高年◎歌-----------------------------------------------

TONGJIUNIVERSITY

5.海明校驗碼

這是由RichardHamming于1950年提出的、

目前還被廣泛采用。

實現(xiàn)原理：

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

每一個二進制位分配在幾個奇偶校驗組中。當(dāng)

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

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

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

同濟大學(xué)電信學(xué)院

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

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

苞年◎稱

TONGJIUNIVERSITY

同濟大學(xué)電信學(xué)院

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

LWif2.1.3數(shù)據(jù)校驗方法

高年◎歌-----------------------------------------------

TONGJIUNIVERSITY

假設(shè)校驗位的個數(shù)為t,貝I它能表示2i個

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

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

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

在校驗位，因此只有k=21-l-t個信息能用于糾

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

2r>k+r+1o

例:假如校驗位有4位,貝也=24-1-4=11,即

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

同濟大學(xué)電信學(xué)院

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

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

苞年◎稱

TONGJIUNIVERSITY

如要能檢測與自動校正一位錯）并發(fā)

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

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

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

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

1?44

5?115

12?266

27?577

58?1208

同濟大學(xué)電信學(xué)院

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

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

高年◎稱

TONGJIUNIVERSITY

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

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

即H1ALi…電明，則此海明碼的編碼規(guī)律通常是:

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

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

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

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

同濟大學(xué)電信學(xué)院

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

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

苞年◎稱

TONGJIUNIVERSITY

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

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

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

位的位號之和。

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

4P4P3P2PP

位是n位,D10D9D8D7D6D5D4D3D2D1D0,生成海明碼。

生成的海明碼：

1115111411131112HII1110119118117116115114113112III

DIOD908D7D6D5D4P4D3D2DIP3DOP2Pl

同濟大學(xué)電信學(xué)院

被校驗位的海明碼

參與校驗的校驗位

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

位號

號之和

珥%11=1

P222=2

H2

3=1+2

H3Do1,2

P344=4

H4

珥□1,45=1+4

2,46=2+4

H6D2

D31,2,47=1+2+4

H7

P488=8

H8

珥D41,89=1+8

2,810=2+8

珥0D5

1,2,811=1+2+8

HuD6

H4,812=4+8

12D7

珥31,4,813=1+4+8

D8

D92,4,814=2+4+8

H14

珥5Dio1,2,4,815=1+2+4+8

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

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

苞年◎稱

TONGJIUNIVERSITY

③校驗位P4P3P2Pl值得確定。

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

位的異或。

Pi=D0十Di十D3十D4十口6十D8十D10

P2=D0十D2十D3十D5十十D9十D10

P3=D1十D2十D3十D7十Dg十D9十D10

P4=D4十D5十口6十D7十Dg十D9十D10

這時P4P3P2Pl的取值是采用偶校驗，當(dāng)采用

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

同濟大學(xué)電信學(xué)院

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

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

苞年◎稱

TONGJIUNIVERSITY

(2)海明碼校驗和糾錯

S1】=DUn十D1i十/j十以4十DRo十Do2十D1Uin十P1i

十十十十十十十

Sz9=DAUDL.D3RDj,DoADyqD1IUnpz?

「十十十十十。十十

SJDi1DZ,DJ]D/7Do&D71nUPJQ

S4=D4十D5十十D7十Dg十D9十D10十P4

采用偶校驗時，S]S2s3s4的值為0000,則

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

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

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

同濟大學(xué)電信學(xué)院

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

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

苞年◎稱

TONGJIUNIVERSITY

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

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

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

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

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

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

同濟大學(xué)電信學(xué)院

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

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

苞年◎稱

TONGJIUNIVERSITY

已知：D10D9D8D7D6D5D4D3D2D1D0=10110100110

P1=O十1十0十o十0十1十1=1

P9=0十1十0十1十0十0十1=1

Po=l十1十0十1十1十0十1=1

P4=0十1十0十1十1十0十1=0

生成海明碼：

H1511141113H1211111110119118H7116115114113112II!

101101000111011

DIOD9D8D7D6D5D4P4D3D2DIP3DOP2Pl

同濟大學(xué)電信學(xué)院

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

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

苞年◎稱

TONGJIUNIVERSITY

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

S1=O十1十0十0十0十1十1十1出）=0

S2=0十1十0十1十0十0十1十1出）=0

$3=1十1十0十1十1十0十1十1（P3）=0

S4=0十1十0十1十1十0十1十。（P4）=0

如產(chǎn)生錯誤,D。出錯

111511141113Hl2III1110119IIB117116115114113H2III

101101000111111

DIOD9D8D7D6D5D4P4D3D2DIP3DOP2Pl

同濟大學(xué)電信學(xué)院

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

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

高年◎歌--------------------------------------------------

TONGJIUNIVERSITY

Pi=D0十Di十D3十D4十口6十％十D10

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

P3=D1十D2十D3十D7十％十D9十Di。

P4=D4十D5十十D7十％十D9十Di。

Pi=O十1十0十0十0十1十1=1

「2=0十1十0十1十0十0十1=1

十十0十1十1十十

P3=l101=1

P4=0十1十0十1十1十0十1=0

同濟大學(xué)電信學(xué)院

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

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

苞年◎稱

TONGJIUNIVERSITY

S1=1十1十0十0十0十1十1十1(P1)=1

$2=^1十0十1十0十0十1十1(P2)=1

$3=^1十0十1十1十0十1十1(P3)=0

$4=(^1十0十1十1十0十1十0(P4)=0

111511141113H12IIII1110H9118117116H5114113112III

D1OD9D8D7D6D5D4P4D3D2D1P3DOP2Pl

同濟大學(xué)電信學(xué)院

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

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

苞年◎稱

TONGJIUNIVERSITY

如產(chǎn)生錯誤,Di。出錯

111511141113111211111110119118117116115114113112III

101101000111011

D10D9D807D6D5D4P4D3D2D1P3DOP2Pl

HI511141113111211111110119118H7116115114113112HI

001101000111011

D10D9D8D7D6D5D4P4D3D2D1P3DOP2Pl