經濟部102年 計概-漢明碼 - 考試

※ 引述《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解釋很麻煩

看不懂在問吧哈(有速解拉..但原理就是這樣且實際用手算就很快)

照解法寫一寫在紙上，不難的 多寫就很快就算出來


有錯請高手指證!

--