2012年9月18日 星期二

100正式Problem:3-2


子題 2：
漢明碼(Hamming Code)
1. 具有自動偵錯與更正錯誤一個位元的功能，兩個位元有誤只能偵測。
2. m 個位元資料，須 r 個同位元查出錯誤。而 m 和 r 的限制式為 m+r+1≦2^r
3. 同位元(Parity)放置位置為2^(r-1)
m：資料位元長度 r：檢查位元長度 (2^r) n：總傳送位元數 ( n= m+ r )
舉例來說，如果需要傳送7 個位元 110 0001 資料，則 m = 7，7+4+1 < =2^4，r 由限制式算出至少為4，因此r= 4，n = 7 + 4，檢查位元需要4 個位元。如果需要傳送16 個位元資料，則檢查位元需要5 個位元。
同位元檢查，分為兩種，一種為奇同位檢查另一種為偶同位檢查，以偶同位例子來說，0110110，已經有4 個1，其值為偶數，所以偶同位元就填入0，保持為1 的個數為偶數，資
料加偶同位為01101100。接下來的計算都用偶同位。
假設，要傳的16 位元資料為0001 0010 0011 0101，則其漢明碼的檢查碼至少需五碼，分別為P1P2P3P4P5，要傳送的位元資料的 1、 2、 4 、8 、16 這幾個位置插入這五位元的漢明碼檢查碼，如下圖：
位置 1 2 3 4 5 6 7 8 9 10 11
P1 P2 0 P3 0 0 1 P4 0 0 1
位置 12 13 14 15 16 17 18 19 20 21
0 0 0 1 P5 1 0 1 0 1
目前檢查位元P1 P2 P3 P4P5 是未知，對應的位置分別為1、 2、 4 、8 、16，需要透過同位元檢查來取得，位置分別以十進制和二進制表示，如下圖：
位置 二進位數字
1(00001) 0 0 0 0 P1
2(00010) 0 0 0 P2 0
3(00011) 0 0 0 0 0
4(00100) 0 0 P3 0 0
5(00101) 0 0 0 0 0
6(00110) 0 0 0 0 0
7(00111) 0 0 1 1 1
8(01000) 0 P4 0 0 0
9(01001) 0 0 0 0 0
10(01010) 0 0 0 0 0
11(01011) 0 1 0 1 1
12(01100) 0 0 0 0 0
13(01101) 0 0 0 0 0
14(01110) 0 0 0 0 0
15(01111) 0 1 1 1 1
16(10000) P5 0 0 0 0
17(10001) 1 0 0 0 1
18(10010) 0 0 0 0 0
19(10011) 1 0 0 1 1
20(10100) 0 0 0 0 0
21(10101) 1 0 1 0 1
同位元檢查1 0 1 0 0
要注意的是位置7、11、15、17、19、21 為1，所以在二進位數字那邊分別要填入00111、01011、01111、10001、10011、10101，其他數字因為都為0，所以位置填00000。
同位元檢查那邊以 P1 那一欄來說，一共有6 個1，所以P1 需要填入0，P5 那一欄來說，一共有3 個1，所以P5 需要填入1，P2P3P4 以此類推，16 位元資料0001 0010 0011 0101，漢明碼檢查碼P1P2P3P4P5 為00101。
十六進制在數學中是一種逢 16 進1 的進位制，一般用數字0 到9 和字母A 到F 表示（其中:A~F 即10~15），由1,2,3,---,9,A,B,C,D,E,F 等十六個基本數字所組成，數量計數從0 到F，滿十六即進位，其中A,B,C,D,E,F 分別代表十進制的10,11,12,13,14,15。例如十進制數78，在二進制寫成01001110，在16 進制寫成4E（4 = 0100, E = 1110）。下表列出0~15 的二進制、十進制與十六進制的對照：
二進制 十進制 十六進制
0000 0 0
0001 1 1
0010 2 2
0011 3 3
0100 4 4
0101 5 5
0110 6 6
0111 7 7
1000 8 8
1001 9 9
1010 10 A
1011 11 B
1100 12 C
1101 13 D
1110 14 E
1111 15 F
假設每筆輸入資料都有16 位元(二進制)資料要傳送，輸入資料以十六進制來表示，以4位元(二進制)為一字元(十六進制)，則每筆輸入資料四個字元，每個字元為0~9 和A~F。
輸入說明：
第 1 行的數字n 代表有幾筆資料要傳送，n 的值介於1(含)和5(含)之間，每筆輸入資料為四個字元的十六進制，字元A~F 為大寫。程式不用檢查輸入格式。
輸出說明：
輸出為四個字元資料所對應的漢明碼 P1P2P3P4P5 檢查碼。
輸入範例：【檔名：in1.txt】
5
1235
1234
6F00
8000
1000
輸入範例：【檔名：in2.txt】
2
C80B
8828
輸出範例：【檔名：out.txt】
00101
10000
11100
11000
11100

00111
11101
張貼者： 於

2 則留言:

  1. 匿名2012年9月18日 晚上8:05

    Dim h(5) As Integer
    Dim t(21), b(4), r
    Dim a(21), p(21) As String
    Private Sub Form_Load()
    Me.Hide
    Open App.Path & "\in1.txt" For Input As #1
    Open App.Path & "\in2.txt" For Input As #2
    Open App.Path & "\out.txt" For Output As #3
    r = Split("0 1 2 3 4 5 6 7 8 9 A B C D E F", " ")
    For i = 0 To 21
    o = i
    d = ""
    Do
    c = o Mod 2
    o = o \ 2
    d = c & d
    Loop Until o = 0
    a(i) = d
    If Len(a(i)) = 1 Then a(i) = "000" & a(i)
    If Len(a(i)) = 2 Then a(i) = "00" & a(i)
    If Len(a(i)) = 3 Then a(i) = "0" & a(i)
    If i <= 15 Then p(i) = "0" & a(i) Else: p(i) = a(i)
    Next
    Input #1, n
    Input #2, n1
    For i = 1 To n
    Line Input #1, x
    Call abc(x)
    Next
    Print #3,
    For i = 1 To n1
    Input #2, x
    Call abc(x)
    Next
    Close
    Close
    Close
    End
    End Sub
    Sub abc(x)
    b(1) = Mid(x, 1, 1)
    b(2) = Mid(x, 2, 1)
    b(3) = Mid(x, 3, 1)
    b(4) = Mid(x, 4, 1)
    For i = 0 To 15
    For j = 1 To 4
    If b(j) = r(i) Then b(j) = i
    Next
    Next
    c = ""
    c = a(Val(b(1))) & a(Val(b(2))) & a(Val(b(3))) & a(Val(b(4)))
    f = 0
    v = 0
    Do
    f = f + 1
    If f <> 1 And f <> 2 And f <> 4 And f <> 8 And f <> 16 Then
    v = v + 1
    t(f) = Mid(c, v, 1)
    End If
    Loop Until f = 21
    For j = 1 To 5
    h(j) = 0
    Next
    For l = 1 To 21
    If t(l) = 1 Then List1.AddItem p(l)
    Next
    For l = 0 To List1.ListCount
    For j = 1 To 5
    h(j) = h(j) + Val(Mid(List1.List(l), j, 1))
    Next
    Next
    For j = 1 To 5
    If h(j) Mod 2 = 0 Then ans = 0 & ans Else: ans = 1 & ans
    Next
    Print #3, ans
    ans = ""
    List1.Clear
    End Sub

    回覆刪除
  2. 匿名2012年9月22日 晚上9:27

    Private Sub Form_Load()
    Me.Hide
    Open App.Path & "\in1.txt" For Input As #1
    Open App.Path & "\in2.txt" For Input As #2
    Open App.Path & "\out.txt" For Output As #3
    Input #1, n
    For i = 1 To n
    Line Input #1, x
    Call ans(x)
    Next i
    Input #2, m
    For j = 1 To m
    Line Input #2, y
    Call ans(y)
    Next j
    Close #3
    Close #2
    Close #1
    End
    End Sub
    Sub ans(x)
    Dim a(4)
    Dim xx(21)
    Dim y(6)
    Dim z(5)
    '-------------------------------------------------------------
    ' a16 to a10
    b = Array("A", "B", "C", "D", "E", "F")
    c = Array("10", "11", "12", "13", "14", "15")
    For i = 1 To Len(x)
    a(i) = Mid(x, i, 1)
    Next i
    For i0 = 1 To UBound(a)
    For i1 = 1 To UBound(b)
    If a(i0) = b(i1) Then a(i0) = c(i1)
    Next i1
    Next i0
    '-------------------------------------------------------------
    '10 to 2
    For i = 1 To UBound(a)
    a(i) = qq(Val(a(i)), 4)
    'Print #3, a(i)
    Next i
    '-------------------------------------------------------------
    '查出1的位置
    For i = 1 To UBound(a)
    For j = 1 To Len(a(i))
    List1.AddItem (Mid(a(i), j, 1))
    Next j
    Next i
    i = 0
    q = 1
    For k = 1 To 21
    If k <> 1 And k <> 2 And k <> 4 And k <> 8 And k <> 16 Then
    xx(k) = List1.List(i)
    i = i + 1
    Else
    xx(k) = "P" & k
    End If
    If xx(k) = "1" Then
    y(q) = qq(k, 5)
    q = q + 1
    End If
    Next k
    List1.Clear
    '-------------------------------------------------------------
    For i = 1 To UBound(y)
    For j = 1 To Len(y(i))
    If Mid(y(i), j, 1) = "1" Then z(j) = z(j) + 1
    Next j
    Next i
    For j = 1 To 5
    If z(j) Mod 2 = 0 Then g = "0" & g Else g = "1" & g
    Next j
    Print #3, g
    '-------------------------------------------------------------
    End Sub
    Function qq(ByVal r, ByVal s) '----10進位 to 2進位
    qq = ""
    If r = 0 And s = 4 Then qq = "0000"
    If r = 0 And s = 5 Then qq = "00000"
    Do While (r > 0)
    qq = r Mod 2 & qq
    r = r \ 2
    Loop
    Do Until Len(qq) = s
    qq = "0" & qq
    Loop
    End Function

    回覆刪除

訂閱： 張貼留言 (Atom)