Re: [考題] 經濟部102年計概-漢明碼

看板Examination作者lo33 (lo33)時間10年前 (2013/12/15 00:49)推噓3(3推 0噓 17→)

留言20則, 3人參與討論串2/2 (看更多)

※ 引述《edward790501 (Dark)》之銘言： : 經濟部所屬機構102年度資訊類別的記概有一題關於漢明碼的題目 : 一個二進位值為10101111的8bit位元組，以偶數同位的漢明碼予以編碼， : 以下何者為正確的編碼後二進位值? : A)101011111000 : B)101001001111 : C)001101011111 : D)011101001111 : 我手上拿到的答案是(B) : 可是我算出來的檢查碼是0001 : 答案為101001110101 : 這樣就沒有答案了，是我有算錯檢查碼嗎? : 麻煩各位了我知道的算法是這樣 ============================================================================= (1) 首先要知道需要幾個檢查碼假設原訊息為 N bits，則需要 K bits 檢查碼，共變成(N+K)bits。需滿足 2的K次方>=(n+K+1) 原:8bits， 2的K次>=8+1+K ， K=4 本題原訊息8bits，所以需要4bits檢查碼共12bits ============================================================================= (2)擺放位置本題長這樣: 擺放位置: __ __ N1 __ N2 N3 N4 __ N5 N6 N7 N8 K1 K2 K3 K4 第幾位: S1 S2 S3 S4 S5 S6 S7 S8 S9 S10 S11 S12 4個檢查碼的位置就在第1(2的0次)位:K1 第2(2的1次)位:K2 第4(2的2次)位:K3 第8(2的3次)位:K4 而 N1 N2 N3 N4 N5 N6 N7 N8 就是原訊息由左至右排變這樣:K1 K2 1 K3 0 1 0 K4 1 1 1 1 第幾位:S1 S2 S3 S4 S5 S6 S7 S8 S9 S10 S11 S12 =========================================================================== (3)求出 K1 K2 K3 K4 方法一: 先照原資訊畫出表格如下: 8 4 2 1 (K4) (K3) (K2) (K1) ======================== 1: 0 0 0 1 2: 0 0 1 0 3: 0 0 1 1 4: 0 1 0 0 5: 0 1 0 1 6: 0 1 1 0 7: 0 1 1 1 8: 1 0 0 0 9: 1 0 0 1 10: 1 0 1 0 11: 1 0 1 1 12: 1 1 0 0 (位置) ###然後看直排 K1那排、K2那排 K3那排 K4那排和其他((位置是1))的做((XOR運算))，用偶同位檢查!!!!! 結果要偶數個1 ! 配合第(2)步的結果: :K1 K2 1 K3 0 1 0 K4 1 1 1 1 第幾位:S1 S2 S3 S4 S5 S6 S7 S8 S9 S10 S11 S12 如下: K1 xor S3 xor S5 xor S7 xor S9 xor S11=0 (S3、S9、S11 共3個1，所以K1要是1) (S1) K2 xor S3 xor S6 xor S7 xor S10 xor S11=0 (S3、S6、S10、S11 4個1，所以K2要是0) (S2) K3 xor S5 xor S6 xor S7 xor S12=0 (S6、S12 共2個1，所以K3要是0) (S4) K4 xor S9 xor S10 xor S11 xor S12=0 (S9~S12都是1 共4個1，所以K4要是0) 解出來啦 K1=1 K2=0 K3=0 K4=0 排進去如下: 1 0 1 0 0 1 0 0 1 1 1 1 (K1)(K2) (K3) (K4) 第幾位:S1 S2 S3 S4 S5 S6 S7 S8 S9 S10 S11 S12 所以答案是 (B)101001001111 ===================================================================== 方法二:快速解法接續步驟(2) K1 K2 1 K3 0 1 0 K4 1 1 1 1 第幾位:S1 S2 S3 S4 S5 S6 S7 S8 S9 S10 S11 S12 把所有位置為1的做XOR運算 S3、S6、S9、S10、S11、S12 為1 將他們做以下運算 3 xor 6 xor 9 xor 10 xor 11 xor 12 3= 0011 6= 0110 9= 1001 10=1010 11=1011 12=1100 ========= XOR的結果: 0001 這裡的0001 由左至右的方向填入也就是 S8=0 S4=0 S2=0 S1=1 一樣答案是(B)101001001111 ==================================================== 看似很多很複雜因為要在PTT解釋很麻煩看不懂在問吧哈(有速解拉..但原理就是這樣且實際用手算就很快) 照解法寫一寫在紙上，不難的多寫就很快就算出來有錯請高手指證! -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 114.27.251.58

推

edward790501

12/15 01:02, , 1^F

12/15 01:02, 1^F

→

edward790501

12/15 01:03, , 2^F

12/15 01:03, 2^F

推

raywen

12/15 01:04, , 3^F

12/15 01:04, 3^F