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

劉 昆

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

0 引言

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

1 信息校驗問題

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

1.1 問題的提出

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

1.2 解決問題算法

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

算法：

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

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

S3：小白鼠喝藥的方法，用每瓶藥編號與小白鼠序列對應，找出藥編號中為1的位與該位對應的小白鼠序列中的白鼠，找出來的小白鼠喝該瓶藥，如：第1瓶，編號為0000000001，則編號為M0的小白鼠喝第 1 瓶藥；第 300 瓶，標號為 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瓶毒藥或者沒有毒藥，要找出該瓶毒藥或者證明沒有毒藥，需要多少只小白鼠？根據上面的算法可知，設需要的R只小白鼠，R與N之間必須存在下面的關系式：2R＞＝N（關系式2.1）。只有當R只白鼠所能表示的數大于或等于藥的瓶數，才能用小白鼠序列與藥的編號對應，否則，小白鼠序列不夠對應藥的編號。

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

R的大小由關系式2.1和關系式2.2決定。

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

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

1.4 算法轉換為信息校驗

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

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

2 結束語

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

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

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

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

［4］王愛英.計算機組成與結構[M].清華大學出版社,2007,7.