軟件設(shè)計師讀書筆記(精華版)

1、1校驗碼（1）碼距碼距就是兩個碼字 C1 與 C2 之間不同的比特數(shù)。如： 1100 與 1010 的碼距為 2; 1111 與 0000 的碼距為 4 。一個編碼系統(tǒng)的碼距就是整個編碼系統(tǒng)中任意（ 所有 ）兩個碼字的最小距離。若一個編碼系統(tǒng)有四種編碼分別為： 0000 ， 0011 ， 1100 ， 1111 ，此編碼系統(tǒng)中 0000 與 1111 的碼距為 4;0000 與 0011 的碼距為 2，是此編碼系統(tǒng)的最小碼距。因此該編碼 系統(tǒng)的碼距為 2 。（2） 8421 碼BCD 碼也叫 8421 碼就是將十進(jìn)制的數(shù)以 8421 的形式展開成二進(jìn)制，大家知道十進(jìn)制是 09十個數(shù)組成，著十個

2、數(shù)每個數(shù)都有自己的8421碼：0 = 00001 = 00012 = 00103 = 00114 = 01005 = 01016 = 01107 = 01118 = 10009 = 1001舉個例子：321 的 8421 碼就是3 2 10011 0010 0001之所以叫8421 碼，是因為四位 8421 碼時 ,從左到右每個"1"代表的十進(jìn)制數(shù)分別是"8"II"2" 、 "1"如下："1000"為十進(jìn)制"8""0100"為十進(jìn)制"4"

3、;"0010"為十進(jìn)制"2""0001"為十進(jìn)制"1"5421 碼與此相同，每位一代表的是十進(jìn)制的"5"、"4"、"2"、"1"即:"1000"為十進(jìn)制"5""0100"為十進(jìn)制"4""0010"為十進(jìn)制"2""0001"為十進(jìn)制"1"3）什么是檢錯與糾錯有很多網(wǎng)友和學(xué)員不明白，

4、為什么有些編碼能檢查出錯誤，而不能糾正錯誤? 下面來舉一個生活當(dāng)中簡單的例子來說明這一點。若希賽公司發(fā)出一個通知： “明天 14: 0016:00 開會 ”，但在通知過程中由于行政部工作人員疏忽，變成了 “明天 10:0016: 00 開會 ”。員工收到這個錯誤通知后由于無法判斷其正確與否，就會按這個錯誤時間 去安排與組織。為了使接收者能判斷正誤，可以在通知內(nèi)容中增加 “下午 ”兩個字，即改為： “明天 下午 14:0016:00 開會 ”。這時，如果仍錯為： “明天下午 10:0016:00 開會，則收到 此通知后，根據(jù) “下午 ”與 “10:00 ”信息即可判斷出通知發(fā)生了錯誤。但仍不能糾

5、正其錯 誤，因為無法判斷是“下午 ”與 “10:00 ”哪一信息出錯，即無法判斷公司原來制定開會的具體時間。這時，接收者可以告訴發(fā)送方再發(fā)一次通知（ 員工向行政部人員詢問，行政部再次確認(rèn)會議時間），這就是檢錯重發(fā) （ 這也就是我們所說的能檢錯， 但無法糾錯 ）。為了實現(xiàn)不但能判斷通知準(zhǔn)確性（檢錯 ），同時還能正確判斷會議開始的具體時間（糾錯 ） ，行政部可以把通知內(nèi)容再增加“兩個小時 ”四個字，即改為： “明天下午 14:0016:00 開會兩個小時 ”。這樣，如果其中 “14:00錯”為 “ 10:00 ，”不但能判斷出錯誤，同 時還能糾正錯誤，因為其中增加的 “兩個小時 ”這個標(biāo)識可以判斷

6、出正確的時間為“14:0016:00 ”。當(dāng)然，這顯然也增加了信息的冗余，降低了數(shù)據(jù)處理的效率。但隨著帶 寬的不斷提高， 數(shù)據(jù)執(zhí)行與處理的能力日益增強(qiáng)， 可靠性與效率的均衡， 這是值得的。 （ 4 ）碼距和檢錯糾錯有何關(guān)聯(lián) 首先大家要了解以下兩個概念：1. 在一個碼組內(nèi)為了檢測e 個誤碼，要求最小碼距應(yīng)該滿足： d>=e+12. 在一個碼組內(nèi)為了糾正t 個誤碼，要求最小碼距應(yīng)該滿足：d>=2t+1現(xiàn)在舉個例子來說明這個問題：假如我們現(xiàn)在要對 A， B 兩個字母進(jìn)行編碼。我們可以選用不同長度的編碼，以 產(chǎn)生不同碼距的編碼，分析它們的檢錯糾錯能力。l 若用 1 位長度的二進(jìn)制編碼。若

7、A=1 ，B=0 。這樣 A， B 之間的最小碼距為1。合法碼：0,1 ;非法碼：0,1 ；根據(jù)上面的規(guī)則可知此編碼的檢錯糾錯能力均為0，即無檢錯糾錯能力。其實道理很簡單，這種編碼無論由 1 錯為 0，或由 0 錯為 1 ，接收端都無法判斷是否有錯， 因為 1 ， 0 都是合法的編碼。l 若用 2 位長度的二進(jìn)制編碼，可選用 11 ， 00 作為合法編碼，也可以選用 01 ，10 作為合法編碼。若以 A=11 ， B=00 為例， A、 B 之間的最小碼距為2。合法碼：11,00 ;非法碼：01,10 ；根據(jù)上面的規(guī)則可知此編碼的檢錯位數(shù)為1 位，無法糾錯。 因為無論 A（11） 或 B（00

8、），如果發(fā)生一位錯碼，必將變成 01 或 1 0 ，這都禁用碼組 （非法碼 ），故接收端可以 判斷為誤碼，卻不能糾正其錯誤。因為無法判斷誤碼（01 或10）是 A（00） 錯誤還是 B（11）錯誤造成，即無法判斷原信息是A或B,或說A與B形成誤碼（01或10）的可能性（概率）是相同的。如果產(chǎn)生二位錯碼，即00 錯為 11 ，或 11 錯為 00 ，結(jié)果將從一個合法編變成另一個合法編碼，接收端就無法判斷其是否有錯。所以此種編碼的檢錯能力為1位，糾錯能力為0位。I若用3位長度的二進(jìn)制編碼，可選用111，000作為合法編碼。A，B之間的最小碼距為 3。合法碼：111,000 ;非法碼：001,010

9、,011,100,101,110;根據(jù)上面的規(guī)則可知此編碼的檢錯位數(shù)為2位，糾錯位數(shù)為1位。例如：當(dāng)信息A(000)產(chǎn)生1位錯誤時，將有3種誤碼形式，即001或010或100，這些都是禁用碼組，可確定是誤碼。而有這3個誤碼與合法編碼000的距離最近，與合編碼111的距離較遠(yuǎn)，根據(jù)誤碼少的概率大于誤碼多的概率的規(guī)律，可以判定原來的正確碼組為000 ,只要把誤碼中的1改為0即可得到糾正。同理，如果信息B(111)產(chǎn)生1位錯誤時，則有另三種誤碼可能產(chǎn)生，即110 , 101 , 011，根據(jù)同樣道理可以判定原來的正確碼組是111，并能糾正錯誤。但是，如果信息A(000)或信息B(111)產(chǎn)生兩位錯誤

10、時，雖然能根據(jù)禁用碼組識別其錯誤，但糾錯時去會做出錯誤的糾正而造成誤糾錯”。如果信息 A(000)或信息B(111)產(chǎn)生三位錯誤時，將從一個合法編碼A(或B)變成了另一個合法編碼B(或A)，這時既檢不出錯，更不會糾錯了，因為誤碼已成為合法編碼，譯碼后必然產(chǎn)生錯誤。所以檢錯位數(shù)為2位，糾錯位數(shù)為1位。四、小結(jié)編碼信息糾錯和檢錯能力的進(jìn)一步提高需要進(jìn)一步增加碼字間的最小距離。概括了最小距離為 1至7的碼的糾錯和檢錯能力。碼距4碼的能力檢措存D疳0心%1P4豐» 1且中2夕亙J-1且可j0 11且Q!3心增大編碼信息的碼距的一個基本缺點是，在任何給定的系統(tǒng)中，都會因而降低數(shù)據(jù)傳輸效率。顯然

11、， 這是由于增加的碼位(為增大最小距離所需的)減小了有用的信息時間。這就給每個信息增加了所謂多余度。所以，選擇最小距離要取決于特定系統(tǒng)的參數(shù)。數(shù)字系統(tǒng)的設(shè)計者必須考慮信息發(fā)生差錯的概率和該系統(tǒng)能容許的最小差錯率等因素，這里不再介紹，大家也可以在輔導(dǎo)平臺中與我進(jìn)一步來討論這些問題。(5)奇偶校驗奇偶校驗碼是一種通過增加冗余位使得碼字中"1"的個數(shù)恒為奇數(shù)或偶數(shù)的編碼方法，它是一種檢錯碼。在實際使用時又可分為垂直奇偶校驗、水平奇偶校驗和水平垂直奇偶校驗等幾種。1.垂直奇偶校驗垂直奇偶校驗又稱為縱向奇偶校驗，它是將要發(fā)送的整個信息塊分為定長p位的若干段（比如說q段），每段后面按&

12、quot;1"的個數(shù)為奇數(shù)或偶數(shù)的規(guī)律加上一位奇偶位，如圖2.19所示。問位信息（111,121,lpl,l12,，中q每p位構(gòu)成一段（即圖中的一列），共有q段（即共有q列。 每段加上一位奇偶校驗冗余位，即圖中的rio編碼規(guī)則為奇樓馳:嚴(yán)切+咕+“+ +1注意:此間的"+"指的是模二加，也即異或運算。圖中箭頭給出了串行發(fā)送的順序 ，即逐位先后次序為111,121,Ip1,r1,I12,Ipa,r2,兒,1間,rq。在編碼和校驗過程中，用硬件方法或軟件方法很容易實現(xiàn)上述連續(xù)半加運算，而且可以邊發(fā)送邊產(chǎn)生冗余位；同樣,在接收端也可邊接收邊進(jìn)行校驗后去掉校驗位。垂直奇偶

13、校驗方法的編碼效率為 R=p/（p+1）。通常,取一個字符的代碼為一個信息段，這種 垂直奇偶校驗有時也稱為字符奇偶校驗。例如，在8位字符代碼（即用8位二進(jìn)制數(shù)位表示一一個字符）中,p=8，編碼效率便為8/9。垂直奇偶校驗方法能檢測出每列中的所有奇數(shù)位錯，但檢測不出偶數(shù)位的錯。對于突發(fā)錯誤來說，奇數(shù)位錯與偶數(shù)位錯的發(fā)生概率接近于相等，因而對差錯的漏檢率接近于1/20。2.水平奇偶校驗為了降低對突發(fā)錯誤的漏檢率，可以采用水平奇偶校驗方法。水平奇偶校驗又稱為橫向奇 偶校驗，它是對各個信息段的相應(yīng)位橫向進(jìn)行編碼，產(chǎn)生一個奇偶校驗冗余位，如圖2.20所示,編碼規(guī)則為Wt臉冷址+計“+垢(ii跆©

14、;*ttt:r=Itt+I;+-+I +1 (匸 IQ'"”若每個信息段就是一個字符的話，這里的q就是發(fā)送的信息塊中的字符數(shù)。水平奇偶校驗的編碼效率為R=q/(q+1)。水平奇偶校驗不但可以檢測出各段同一位上的奇數(shù)位錯，而且還能檢測出突發(fā)長度 <p的所有突發(fā)錯誤。因為按發(fā)送順序從圖2.20可見，突發(fā)長度p的突發(fā)錯誤必然分布在不同的行中，且每行一位，所以可以檢出差錯，它的漏檢率要比垂直奇偶校驗方法低。但是實現(xiàn)水平奇偶校驗時，不論采用硬件方法還是軟件方法，都不能在發(fā)送過程中邊產(chǎn)生奇偶校驗冗余位邊插入發(fā)送，而必須等待要發(fā)送的全部信息塊到齊后，才能計算冗余位，也就是一定要使用數(shù)據(jù)緩沖器，因此它的編碼和檢測實現(xiàn)起來都要復(fù)雜一些。冗余位3. 水平垂直奇偶校驗，也稱為縱橫奇偶校實驗同時進(jìn)行水平奇偶校驗和垂直奇偶校驗就構(gòu)成水平垂直奇偶校驗 如圖2.21所示。若水平垂直都采用偶校驗，則乍+L,嚴(yán) Iy+l+'-'+I*射葉人討決卻對"+!>+*rLl+rZi+