“計算機組成原理”中信息校驗碼的探討

劉 昆

（曲靖師范學(xué)院計算機科學(xué)與工程學(xué)院 云南 曲靖 655011）

0 引言

“計算機組成原理”是計算機相關(guān)專業(yè)的一門核心專業(yè)基礎(chǔ)課，主要討論計算機基本的部件構(gòu)成和組成方式,也包括基本的運算操作原理和單元設(shè)計思想、操作方式及其實現(xiàn)，“模擬電子技術(shù)”、“數(shù)字邏輯”是它的先導(dǎo)課程，它的后繼課程如“操作系統(tǒng)”、“編譯原理”、“匯編語言程序設(shè)計”等，它學(xué)好與否直接影響著后繼課程的學(xué)習(xí)，“計算機組成原理”在這些課程之間起著承上啟下的作用[1-4]。學(xué)習(xí)過程中學(xué)生普遍感到“計算機組成原理”課程涉及的內(nèi)容多、抽象、難度大、難學(xué)、難懂，“教師難教,學(xué)生怕學(xué)”的現(xiàn)象在各高校普遍存在，如何把握課程的主線和重點培養(yǎng)學(xué)生的學(xué)習(xí)興趣、提高教學(xué)效果,是從事本課程教學(xué)的教師在不斷探討的問題[1]；結(jié)合多年“計算機組成原理”的教學(xué)經(jīng)驗，對學(xué)生難理解的信息校驗問題提出實例教學(xué)法。

1 信息校驗問題

信息校驗問題95%的學(xué)生對奇偶校驗是能正確理解，但是對海明碼校驗只有50%的學(xué)生能正確理解，如何讓更多學(xué)生順利理解海明校驗碼以及其他校驗方法，是一直上課教師思考的問題。結(jié)合遇到的一個問題，通過這個問題的解決，可以讓同學(xué)們更好的理解海明校驗碼。

1.1 問題的提出

問題如下，有1000瓶一模一樣的藥，其中至多有一瓶是毒藥或者沒有毒藥，任何喝下毒藥的生物都會在一星期之后死亡。現(xiàn)在，有10只小白鼠和一星期的時間，如何檢驗出哪瓶瓶子里有毒藥或者證明沒有毒藥？

1.2 解決問題算法

小白鼠喝了藥后，有中毒和不中毒2種情況，一個星期后，有死亡和未死亡2種情況，符合二進制的特征。在二進制中，10位二進制數(shù)可以表示的范圍為0000000000至1111111111，轉(zhuǎn)換為十進制為0～1023。用10只小白鼠，能表示1000瓶藥，通過10只小白鼠喝這1000瓶藥，根據(jù)小白鼠的死亡情況，能找出哪瓶藥是毒藥或者能證明沒有毒藥。具體檢測算法如下。

算法：

S1：對1000瓶藥，按二進制進行編號，編號為D9D8D7D6D5D4D3D2D1D0，如第1瓶，編號為0000000001，第300瓶，標(biāo)號為0100101100，第1000瓶，編號為1111101000。

S2：對10只小白鼠進行排序，按排位M9M8M7M6M5M4M3M2M1M0，稱為小白鼠序列，Mi表示在排位中的從右向左數(shù)過來的第i+1只小白鼠。

S3：小白鼠喝藥的方法，用每瓶藥編號與小白鼠序列對應(yīng)，找出藥編號中為1的位與該位對應(yīng)的小白鼠序列中的白鼠，找出來的小白鼠喝該瓶藥，如：第1瓶，編號為0000000001，則編號為M0的小白鼠喝第 1 瓶藥；第 300 瓶，標(biāo)號為 0100101100，則編號為 M2，M3，M5，M8的小白鼠喝第300瓶藥，同理，第1000瓶，編號為1111101000；為編號M3，M5，M6，M7，M8，M9的小白鼠喝第 1000 瓶藥。

S4：一個星期后，看10只編了號的小白鼠的死亡情況。如果一只小白鼠都沒有死亡，證明沒有毒藥，否則，毒藥的編號就為小白鼠死亡情況的編號，喝了毒藥的小白鼠全都死亡，未喝的就未死亡，即M9M8M7M6M5M4M3M2M1M0中死亡的小白鼠M為1，未死亡小白鼠M的為0，得到的二進制編碼即為毒藥編號。

1.3 算法分析

算法的每一步是正確的，每一步是可行的，算法是完全正確的。下面思考這樣一個問題，如果N瓶藥中至多有1瓶毒藥或者沒有毒藥，要找出該瓶毒藥或者證明沒有毒藥，需要多少只小白鼠？根據(jù)上面的算法可知，設(shè)需要的R只小白鼠，R與N之間必須存在下面的關(guān)系式：2R＞＝N（關(guān)系式2.1）。只有當(dāng)R只白鼠所能表示的數(shù)大于或等于藥的瓶數(shù)，才能用小白鼠序列與藥的編號對應(yīng)，否則，小白鼠序列不夠?qū)?yīng)藥的編號。

小白鼠R多大最為合適，如上面算法，如果選取20只小白鼠也一定能找出毒藥來，但造成了不必須的浪費，很顯然按上面的算法進行，小白鼠編號＞9的小白鼠都不用喝藥。所以R與N之間滿足下面的關(guān)系式也一定能讓問題解決：(log2N)+1＞＝R （關(guān)系式 2.2）。

R的大小由關(guān)系式2.1和關(guān)系式2.2決定。

藥的編號與十進制的關(guān)系是：D9D8D7D6D5D4D3D2D1D0對應(yīng)的十進制數(shù)＝D9×29+D8×28+D7×27+D6×26+D5×25+D4×24+D3×23+D2×22+D1×21+D0×20。 （關(guān)系式 2.3）

小白鼠Mi喝的藥是藥編號中所有的Di位有關(guān)，當(dāng)Di為1時，Mi喝該瓶藥，當(dāng)Di為0時，不喝該瓶藥，一只小白鼠大約要喝N/2瓶藥，1瓶藥最多被R只小白鼠喝，最少被1只小白鼠喝。

1.4 算法轉(zhuǎn)換為信息校驗

把1000瓶藥轉(zhuǎn)換為計算機中的1000位信息位，在傳輸過程中至多有1位或者沒有信息出錯，需要多少位校驗位來校驗出出錯的信息位或者證明信息沒有出錯，可以使用算法1.1的思想。但是，算法1.1中的S3如何在信息校驗中實現(xiàn)，信息位和校驗位又如何對應(yīng)起來呢？Mi和Di通過什么建立起關(guān)系呢？解決這個問題的關(guān)鍵是正確理解校驗的過程，校驗的過程是首先，通過正確的信息位構(gòu)建校驗位，從而得到校驗碼，其次，傳輸?shù)倪^程中，可能某位信息位受到干擾發(fā)生錯誤，通過校驗位糾出出錯的信息位或者證明在傳輸過程中沒有出錯。

根據(jù)小白鼠檢測毒藥的問題，可以知道一只小白鼠Mi是用來檢測藥品中編號中的Di位，在信息校驗中，有奇偶校驗?zāi)軐崿F(xiàn)生產(chǎn)校驗位。奇偶校驗是一種校驗代碼傳輸正確性的方法。根據(jù)被傳輸?shù)囊唤M二進制代碼的數(shù)位中“1”的個數(shù)是奇數(shù)或偶數(shù)來進行校驗。采用奇數(shù)的稱為奇校驗，反之，稱為偶校驗。采用何種校驗是事先規(guī)定好的。通常專門設(shè)置一個奇偶校驗位，用它使這組代碼中“1”的個數(shù)為奇數(shù)或偶數(shù)。若用奇校驗，則當(dāng)接收端收到這組代碼時，校驗“1”的個數(shù)是否為奇數(shù)，從而確定傳輸代碼的正確性[1-3]。奇偶校驗可以通過異或運算（⊕）實現(xiàn)。

2 結(jié)束語

通過這個例子的理解，對海明碼校驗?zāi)苓M一步理解，能深入的理解，校驗是怎么回事，糾錯是怎么回事。希望能對信息校驗理解有困難的人有一定的幫助。

［1］唐朔飛.計算機組成原理[M].高等教育出版社,2008,1.

［2］徐昆良.《計算機組成原理》課程教學(xué)方法探討[J].中國科技信息,2009.5.1

［3］蔣本珊.計算機組成原理[M].清華大學(xué)出版社,2004,3.

［4］王愛英.計算機組成與結(jié)構(gòu)[M].清華大學(xué)出版社,2007,7.