Đề tài : Mã Hamming
Richard W. Hamming (1915-1998)
Hamming Code
Nhóm 1
Ký hiệu Định nghĩa
u Bản tin gốc
v Mã hóa
S(x) Tín hiệu truyền
N(x) Tín hiệu nhiễu
R(x) Tín hiệu nhận
R Chuỗi bit giải điều chế
u Chuỗi bit đã giải mã
Hamming Code
Mục đích của lý thuyết Mã hóa trên kênh truyền (channel encoding theory) là tìm những mã có
thể truyền thông nhanh chóng, chứa đựng nhiều mã ký (code word) hợp lệ và có thể sửa lỗi (error
correction) hoặc ít nhất phát hiện các lỗi xảy ra (error detection). Các mục đích trên không phụ
thuộc vào nhau, và mỗi loại mã có công dụng tối ưu cho một ứng dụng riêng biệt. Những đặc tính
mà mỗi loại mã này cần còn tuỳ thuộc nhiều vào xác suất lỗi xảy ra trong quá trình truyền thông
Ở đây ta tìm hiểu mã khối tuyến tính (), bao gồm :
•
Mã tuần hoàn (Cyclic codes, mã Hamming là một bộ phận nhỏ)
•
Mã tái diễn (Repetition codes)
•
Mã chẵn lẻ (Parity codes)
•
Mã Reed-Solomon (Reed Solomon codes)
•
Mã BCH (BCH code)
•
Mã Reed-Muller

•
Mã hoàn hảo (Perfect codes)
Hamming Code
Trong viễn thông (telecommunication), mã Hamming là một mã sửa lỗi tuyến tính (linear error-
correcting code), được đặt tên theo tên của người phát minh ra nó, Richard Hamming. Mã
Hamming có thể phát hiện một bit hoặc hai bit bị lỗi (single and double-bit errors). Mã Hamming
còn có thể sửa các lỗi do một bit bị sai gây ra.
Ngược lại với mã của ông, mã chẵn lẻ (parity code) đơn giản vừa không có khả năng phát hiện các
lỗi khi 2 bit cùng một lúc bị hoán vị (0 thành 1 và ngược lại), vừa không thể giúp để sửa được các
lỗi mà nó phát hiện thấy.
Hamming Code
Khoảng cách Hamming
Khoảng cách Hamming được sử dụng trong kỹ thuật viễn thông để tính số lượng các bit trong
một từ nhị phân (binary word) bị đổi ngược, như một hình thức để ước tính số lỗi xảy ra trong
quá trình truyền thông, và vì thế, đôi khi nó còn được gọi là khoảng cách tín hiệu (signal
distance). Việc phân tích trọng số Hamming của các bit còn được sử dụng trong một số ngành,
bao gồm lý thuyết tin học, lý thuyết mã hóa, và mật mã học.
Trước tiên ta tìm hiểu về trọng số Hamming: trọng số Hamming của một từ mã là số số 1 có trong
từ mã đó. Ví dụ với từ mã 00111010 có trọng số Hamming là 4. Khoảng cách Hamming được
định nghĩa là các bít khác nhau giữa hai từ mã. Khoảng cách Hamming giữa hai từ mã được lấy
bằng cách dùng toán tử XOR từng bít của hai từ mã với nhau và khoảng cách Hamming là trọng
số của kết quả tìm được trong phép XOR trên. Ví dụ ta có hai từ mã 0110101 và 1110001 ta có:
0 1 1 0 1 0 1
XOR
1 1 1 0 0 0 1

1 0 0 0 1 0 0
Vậy khoảng cách Hamming của 2 từ mã trên là 2.
Hamming Code
Trọng lượng Hamming

Trọng lượng Hamming () của một dãy ký tự là khoảng cách Hamming từ một
dãy ký tự toàn số không có cùng chiều dài. Có nghĩa là số phần tử trong dãy ký tự không có giá
trị không (0): đối với một dãy ký tự nhị phân (), nó chỉ là số các ký tự có giá trị một
(1), lấy ví dụ trọng lượng Hamming của dãy ký tự 11101 là 4.

Đối với một chiều dài cố định "n", khoảng cách Hamming là độ đo trên không gian vectơ của các
từ có chiều dài đó, vì nó thỏa mãn yêu cầu về tính chất số không âm (non-negativity) (số tuyệt
đối), hiện thân của tính bất khả phân định (indiscernibles) và tính đối xứng (symmetry), và nó có
thể được chứng minh một cách dễ dàng bằng phép quy nạp toàn phần (complete induction) rằng
nó còn thỏa mãn bất đẳng thức tam giác (triangle inequality) nữa.
Hamming Code
Khoảng cách Hamming giữa hai từ a và b còn được gọi là trọng lượng Hamming (Hamming
weight) của phép toán a−b, dùng một toán tử thích hợp thay thế cho toán tử "−".
Đối với hai dãy ký tự nhị phân a và b, phép toán này tương đương với phép toán a XOR b.
Khoảng cách Hamming của các dãy ký tự nhị phân còn tương đương với khoảng cách Manhattan
giữa hai giao điểm của một hình giả phương cấp n (n-dimensional hypercube), trong đó n là
chiều dài của các từ.
Hamming Code
Ví dụ đối với mã ASCII 7 bit
Mã ASCII 7 bit cần 4 bit dư thừa để thêm vào dữ liệu gốc. Sở dĩ ta chọn là 4 bít vì 24 = 16 sẽ
xác định được 16 trường hợp bị lỗi đơn bít (trong dãy ta xét có 11 bit: 7 bit dữ liệu và 3 bit
mã). Các bít dư thừa được đặt vào vị trí 1, 2, 4 và 8 (Chữ d () được dùng để biểu thị các
bit dữ liệu và chữ p () để biểu thị các bit chẵn lẻ ().)
d
7
d
6
d
5
p

4
d
4
d
3
d
2
p
3
d
1
p
2
p
1
11 10 9 8 7 6 5 4 3 2 1
Hamming Code
Thuật toán :
Mã Hamming là một mã sửa lỗi tuyến , mã này có thể phát hiện một bit hoặc hai bit bị lỗi. Mã
Hamming còn có thể sửa các lỗi do một bit bị sai gây ra.
Có thể tóm tắt các bước cho việc sử dụng mã Hamming như sau:
1) Các vị trí trong một khối được bắt đầu đánh số từ 1: Bit 1, 2, 3…
2) Tất cả các bít ở vị trí số mũ của 2 được dùng làm bít chẵn lẻ. Vd: 20, 21, 22, 23, 24…
3) Tất cả các vị trí khác vị trí còn lại sẽ được dùng cho các bit dữ liệu. VD: vị trí thứ 2, 3, 5, 6, 7…

4) Mỗi bit chẵn lẻ tính giá trị chẵn lẻ cho một số bit trong từ mã theo quy tắc như sau:
Hamming Code
Bít chẵn lẻ ở vị trí số 1 (20) sẽ kiểm tra tính chẵn lẻ của các vị trí mà số thứ tự của vị trí đó
trong hệ nhị phân có bít ngoài cùng là 1. Vd: 1 (1), 3 (11), 5 (101), 7 (111), 9 (1001)
Bít chẵn lẻ ở vị trí số 2 (10) sẽ kiểm tra tính chẵn lẻ của các vị trí mà số thứ tự của vị trí đó

trong hệ nhị phân có bít thứ 2 là 1. Vd: 2 (10), 3 (111), 6 (110), 7 (111), 10 (1010)…
Bít chẵn lẻ ở vị trí số 4 (100) sẽ kiểm tra tính chẵn lẻ của các vị trí mà số thứ tự của vị trí đó
trong hệ nhị phân có bít thứ 3 là 1. Vd: 4, 5, 6, 7, 12, 13, 14, 15…
Tương tự với các bít chẵn lẻ ở vị trí cao hơn: 8, 16, 32…
 !"#$"%&'"
()*'+!'" #,-!./
Hamming Code
012344
Trong đó, bit R được dùng để tính chẵn lẻ các tổ hợp bít sau:
Bit p1 tính các bit thứ 3, 5, 7, 9, 11
Bit p2 tính các bit thứ 3, 6, 7, 10, 11
Bit p3 tính các bit thứ 5, 6, 7
Bit p4 tính các bit thứ 9, 10, 11
Hamming Code
Ví dụ, ta có chuỗi bit "1010110" và mã Hamming sử dụng bít chẵn lẻ chẵn thì
p1 = 1, p2 = 0, p3 = 0, p4 = 0
Khi đó, chuỗi dữ liệu truyền đi sẽ là 10100100110
052344
Hamming Code
Do mã hamming sử dụng bit chẵn-lẻ-chẵn nên tổng số bít 1 trong 1 vòng tròn là số chẵn. Giả
sử trong quá trình truyền xảy ra lỗi tại bit 11, tại phía thu, thuật toán sẽ phát hiện ra tổng số
bit 1 trong 3 vòng tròn (vòng bên trái và hai vòng trên dưới) là một số lẻ, trái với quy tắc nên
nó sẽ thay đổi giá trị của bít nằm ở vùng giao của 3 vòng tròn này.
05/627811"9:-1&6'44;<
#,-
Hamming Code
Ký Hiệu : G (k,n)
k: số vecto cơ hệ (số hàng)
n: độ dài từ mã (số cột)
Cho [a] =[u1 u2 …ui] là ma trận mang tin và ma trận sinh G thì ta có [V]=[u].[G] .Viết gọn :

V=u.G
Ma Trận Sinh Chuẩn
Hamming Code
Bộ mã V có thể thay đổi bằng bộ mã V’ có cùng xác suất sai
Các bộ mã tương đương được tạo ra bằng cách biến đổi tương đương trên ma trận sinh : hoán bị
cột , tổ hợp tuyến tính các hàng củ thành hàng mới
G  Gch = [Ik,k , p k,(n-k)]
Ma Trận Sinh
Dưới dạng cấu trúc hệ thống H = [Ir.Q] Trong đó :
Ir là ma trận đơn vị
Ma trận Q gồm 2r – 1 – r cột
Mỗi cột là vector r chiều có trọng số là 2 hoặc lớn hơn
Định nghĩa : với v € V , u € U thì ma trận sinh [H] = [h1 h2 …hn-k] với v.HT =0
Định lý : nếu V có Gch = [Ik,k , p k,(n-k)] thì Hch = [- , Ik,(n-k)]
Trong thực tế để việc tạo và giải mã hamming một cách đơn giản, người ta đổi vị trí các cột
trong ma trận H . Khi đó các bit cần kiểm tra xen kẽ với các bit mang tin chứ không còn tính
chất khối
Ma Trận Thử
Hamming Code
-


=
>
Mô tả bằng thuật toán
Ví dụ, với m=3, ma trận của mã [7,4] được viết dưới dạng H(3,7) =
Như ta đã biết, mã Hamming là một mã khối. Và với mọi m > 2, luôn tồn tại mã Hamming với
các thông số sau:
•
Chiều dài từ mã: n = 2m-1

•
Chiều dài phần tin: k=2m-m-1
•
Chiều dài phần kiểm tra: m=n-k
•
Khả năng sửa sai: t=1
•
Ma trận kiểm tra H có dạng: H = [Im.Q]
Trong đó Im là mà trận đơn vị m*m và Q là ma trận [2m-m-1] cột, mỗi cột là vectơ m chiều có
trọng số là 2 hoặc lớn hơn.
Hamming Code
1 0 0 1 0 1 1
0 1 0 1 1 1 0
0 0 1 0 1 1 1
Xây Dựng Mã Hamming
Hamming Code
Mã hamming có đặc điểm : Ma trận thử H có r hàng , 2r – 1 cột
?@3*A2BCDEFG%HIJ
Để việc tạo mã đơn giản ta chọn các bit kiểm tra c-1- , c-2 , c-3- ở các vị trí tương ứng 2i với i = 0,1,2,
(nghĩa là các vị trí thứ nhất , thứ hai và thứ tư của các ký hiệu từ mã)
32'KL1LL5ML1LL6LML5LML6LMLEL'NGMKML1LLML5LML6LMLE
?G$HL1LL5LL6O
PQ2'LKR
3GMHMK1R1R'K1516R1R'/KR
c3 +1 = 0 => c3= 1
c2 + 1 + 1 = 0 => c2 = 0
c1 + 1 = 0 => c1 = 1
v = 1011010
Hamming Code
Sơ đồ tạo mã : u = u1 u2 u3 u4

v = c-1- c-2 u-1- c-3- u-2- u-3- u-4 v H-T = [c-1- c-2 u-1- c-3- u-2- u-3- u-4 ] HT = 0
c3 = u2 + u3 + u4
c2 = u1 + u3 + u4
c1 = u1 + u2 + u4
Hamming Code
0E/S
Ưu điểm :
Từ ma trận H ta dễ dàng suy ra từ mã v , nghĩa là không cần biết ma trận
sinh G ta cũng dễ dàng tìm được v
Hamming Code
Sơ Đồ Sửa Lỗi Mã Hamming
PQT9'#U;MVWX
S = r.HT
Nếu : S = 0 thì r = v ( Không có lỗi )
S ≠ 0 thì r ≠ v ( có lỗi )
Ta có : S = r.HT mà r = v + e  S = ( v + e ) . HT = v HT + e HT = e HT
Xác định được e ta suy ra v = r + e
Hamming Code
VD : xét mã Hamming ( 7 ,4 )
Với r = r1r2r3r4r5r6r7
Syndrome :

S = r HT
S = [ r4 + r5 + r6 + r7, r2 + r3 + r6 + r7, r1 + r3 + r5 + r7 ]
Hamming Code
Cho :
e= 1000000 => s1= eHT = [ 1000000 ] HT = 001
e= 0100000 => s2 = 010
e= 0010000 => s3 = 011
e= 0001000 => s4 = 100

e= 0000100 => s5 = 101
e= 0000010 => s6 = 110
e= 0000001 => s7 = 111
Hamming Code
Bản sự thật :
Hamming Code
Mạch Sửa Lỗi :
Hamming Code