※ 引述《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解釋很麻煩
看不懂在問吧哈(有速解拉..但原理就是這樣且實際用手算就很快)
照解法寫一寫在紙上，不難的 多寫就很快就算出來
有錯請高手指證!
--
: 經濟部所屬機構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解釋很麻煩
看不懂在問吧哈(有速解拉..但原理就是這樣且實際用手算就很快)
照解法寫一寫在紙上，不難的 多寫就很快就算出來
有錯請高手指證!
--
All Comments