CHƯƠNG 5
Mã hóa kênh truyền
1
Nội dung
Khái niệm về mã phát hiện sai và sửa sai. – Cơ chế phát hiện sai của mã hiệu. – Khả năng phát hiện và sửa sai. – Hệ số sai không phát hiện được. Mã khối tuyến tính – Định nghĩa – Ma trận kiểm tra – Mạch mã hóa – Giải mã – Syndrome và sự phát hiện lỗi – Sửa lỗi
2
Vấn đề
Lỗi khi truyền dữ liệu trên một hệ thống truyền tin:
• Lỗi khi truyền tin là một điều khó tránh.
• Nguyên nhân: Do nhiễu bên ngoài xâm nhập, tác động
lên kênh truyền, làm thông tin truyền đi bị sai.
1 → 0
0 → 1
• Việc khắc phục và kiểm soát lỗi là một vấn đề hết sức
quan trọng.
3
Nguyên lý mã hóa kiểm soát lỗi
• Nguyên lý chung là thêm vào tập mã cần truyền một tập bit
kiểm tra nào đó để bên nhận có thể kiểm soát lỗi.
• Bên phát: Bổ sung thêm thông tin (thêm bit) vào bit cần gửi.
• Bên thu: Nhận thông tin bổ sung ở phía phát, kiểm tra, phát
k bit
k+n-k = n bit
Phát
Thu
Bộ mã KSL + (n-k) bit
Thông tin
hiện và sửa lỗi.
4
Với n-k: bit kiểm tra
Khái niệm về mã phát hiện sai và sửa sai.
Dạng sai lầm của mã hiệu được truyền tuỳ thuộc tính
chất thống kê của kênh: sai độc lập dẫn đến sai ngẫu nhiên: 1 hoặc 2 sai. Sai tương quan dẫn đến sai chùm (sai cụm)
Người ta thống kê: sai ngẫu nhiên xẩy ra 80%, sai chùm
xảy ra 20%.
Xác suất xuất hiện một từ mã n ký hiệu có t sai bất kỳ: tps
p(n,t) = Cn
t(1-ps)n-t
5
Cơ chế phát hiện sai của mã hiệu.
n
k
2
2 E
1
Số từ mã có thể có: N0 = 2n Số từ mã mang tin: N = 2k. Số từ mã không dùng đến: 2n –2k (số tổ hợp cấm) Để mạch có thể phát hiện hết i lỗi thì phải thỏa mãn điều kiện:
n
k
2
6
2 n
1
Trong đó EΣ = E1 + E2+ . . . + Ei E1, E2, . . Ei là tập hợp các vector sai 1,2 . . .i lỗi. Để phát hiện và sửa hết sai 1 lỗi ta có:
Khả năng phát hiện và sửa sai
Trọng số Hamming của vector t: ký hiệu: w(t) được xác định theo số các thành phần
khác không của vector.
Ví dụ: t1 = 1 0 0 1 0 1 1 w(t1) = 4
Khoảng cách giữa 2 vector t1, t2: ký hiệu, d(t1, t2) được định nghĩa là số các thành
phần khác nhau giữa chúng.
Ví dụ: t2 = 0 1 0 0 0 1 1 d(t1, t2) = 3 chúng khác nhau ở vị trí 0, 1 và 3
Khoảng cách Hamming giữa 2 vector mã t1, t2 = trọng số của vector tổng t1 t2:
d(t1, t2)=w(t1 t2) .
t1 = 1 0 0 1 0 1 1 t2 = 0 1 0 0 0 1 1
t1 t2 = 1 1 0 1 0 0 0 w(t1 t2) = 3 = d(t1, t2)
Điều kiện phát hiện sai
Điều kiện để một mã tuyến tính có thể phát hiện được t
sai:
d t+1
ví dụ: t = 1 d 2; t = 2 d 3 t = 5 d 6
Điều kiện để một mã tuyến tính có thể phát hiện và sửa
được t sai: d 2t + 1
t = 1 d 3; t = 2 d 5; t = 5 d 11
8
Hệ số sai không phát hiện được
Ví dụ: đối với bộ mã (5,2) có trọng số Hamming w =2 ta xác
định được hệ số sai không phát hiện được:
2p2q
p’ = C2
1pqC3
1 pq2 + C2
2p2C3
nếu p = 10-3 p’ 6p2 = 6.10-6 nghĩa là có 106 bit truyền đi,
103 bit bị sai thì có 6 bit sai không phát hiện được.
9
Phương trình đường truyền
• Gọi từ mã phát đi là T. • Gọi từ mã nhận được là R • Gọi từ mã sai do đường truyền gây ra là E. phương trình đường truyền:
R = T E T = R E E = T R
Đối với mã nhị phân 3 phương trình trên tương đương
nhau.
10
Vector sai – cô cheá söûa loãi
• Cơ chế ARQ(Automatic Repeat Request-cơ chế tự động phát lại): cơ chế yêu cầu phát lại số liệu một cách tự động (khi phát hiện sai) . cơ chế này có 3 dạng cơ bản: Cơ chế ARQ dừng & chờ (stop and wait ARQ) Cơ chế ARQ quay ngược N vector (N go back ARQ). Cơ chế ARQ chọn lựa việc lặp lại.
• Cơ chế FEC (Forward Error Control): phát hiện và tự sửa sai sử dụng các
loại mã sửa lỗi. Khi có sai đơn (1 sai) người ta thường dùng các loại mã như: mã khối tuyến
tính, mã Hamming, mã vòng…
Khi có sai chùm (> 2 sai) người ta thường dùng các loại mã như: mã BCH, mã
tích chập, mã Trellis, mã Tubor, mã Tubor Block, mã tổng hợp GC… 11
Vector sai: E = (e0, e1, …, en) Ví dụ: E = (1 0 0 1 0 1 0) sai ở vị trí 0, 3, 5 Trong các hệ thống truyền số liệu có 2 cơ chế sửa lỗi:
Mã khối tuyến tính
• Mã khối tuyến tính được xây dựng dựa trên các kết quả của đại số tuyến
tính là một lớp mã được dùng rất phổ biến trong việc chống nhiễu.
• Định nghĩa:
• Một mã khối có chiều dài n, k bit gồm 2k từ mã tuyến tính C(n,k) nếu và chỉ nếu 2k từ mã hình thành một không gian vectơ k chiều 2n, gồm
tất cả các vectơ n thành phần trên trường Galois sơ cấp GF(2) ( bao
gồm 2 phần tử {0,1} với 2 phép tính + và *).
• Mã tuyến tính C(n,k) có mục đích mã hóa những khối tin (hay thông
báo) k bit thành những từ mã n bit. Hay nói cách khác trong n bit của
từ mã có chứa k bit thông tin.
• Ví dụ: C (7,4): Từ mã dài 7 bit. Thông tin cần truyền: 4 bit.
12
Cách biểu diễn mã – Ma trận sinh
• Mã tuyến tính C(n,k) là một không gian k chiều của không gian vectơ n
thành phần, cho nên tồn tại k từ mã độc lập tuyến tính (g0,g1,…,gk-1) sao cho mỗi từ mã trong C là một tổ hợp tuyến tính của k từ mã này :
gaw
ga
...
ga
0
0
1
1
1
k
k
1
(
a
}1,0{
i
,...,1,0
k
)1
i
• k từ mã này tạo thành một ma trận sinh cấp k x n như sau:
g
g
...
g
g
00
01
(0
n
)1
0
...
g
g
)1
1
G
nk
g 10
g 11
(1 n
...
...
g
g
g
g
(
k
0)1
(
k
1)1
(
k
)(1
n
)1
k
1
13
Với: gi = (gi0, gi1… gi(n-1)) với i = 0, 1, …, k-1
Cách mã hóa
• Nếu u = (a0,a1,…,ak-1) , với ai =0/1 và 0i k-1, là thông tin
cần được mã hóa.
• Goïi t laø töø maõ phaùt ñi: t = t0 t1 ….tn-1 , Vôùi tj = 0
hoaëc 1 vaø 0 j k-1 thì từ mã w tương ứng với t được hình thành bằng cách lấy t x G
w = t x G = a0g0 + a1g1 +…+ ak-1gk-1
• Vì các từ mã tương ứng với các thông báo được sinh ra bởi G
theo cách trên nên G được gọi là ma trận sinh của bộ mã.
• Maõ khoái tuyeán tính heä thoáng coù caáu truùc:
n-k bits kiểm tra
K bits mang tin
Độ dài từ mã : n
14
Ví dụ
• Cho ma trận sinh của một mã tuyến tính C(7,4) sau:
1
1
0
1
0
0
0
0
1
G
74
2
1 0
0 1
1 0
1 0
1 0
0 1
0 1
g g g g
3
1
0
1
0
0
0
1
• Nếu u = (u0 u1 u2 u3) = (1101) là thông tin cần mã hóa thì từ mã tương ứng là:
(u0, u1, u2, u3)
.Gut ~ ~
1 1 0 1 0 0 0 0 1 1 0 1 0 0 1 1 1 0 0 1 0 1 0 1 0 0 0 1
t0 = u0.1 + u1.0 + u2.1 + u3.1 = u0+ u2 + u3 = 1 + 0 +1 = 0 t1 = u0.1 + u1.1 + u2.1 + u3.0 = u0 + u1 + u2 = 1+ 1 +0 = 0 t2 = u0.0 + u1.1 + u2.1 + u3.1 = u1 + u2 + u3 = 1+0+ 1 = 0 t3 = u0.1 + u1.0 + u2.0 + u3.0 = u0 = 1 t4 = u0.0 + u1.1 + u2.0 + u3.0 = u1 = 1 t5 = u0.0 + u1.0 + u2.1 + u3.0 = u2= 0 t6 = u0.0 + u1.0 + u2.0 + u3.1 = u3= 1 • => w = (0001101)
15
Ma trận sinh
• Bất kỳ k từ mã độc lập tuyến tính nào cũng có thể được dùng
để làm ma trận sinh cho bộ mã.
• Một bộ mã tuyến tính (không gian mã) có thể có nhiều ma trận
sinh khác nhau cùng biểu diễn.
16
• Mỗi ma trận sinh tương ứng với một cách mã hóa khác nhau.
Cách giải mã
• Từ ma trận sinh ở ví dụ trước, gọi: u = (a0, a1, a2, a3) là thông
tin, w = (b0, b1, b2, b3 , b4 , b5 , b6) là từ mã tương ứng.
• Ta có hệ phương trình liên hệ giữa u và w
1
1
0
1
0
0
0
0
1
0
1
1
1
0
0
1
G
74
3
0 1
1 0
0 1
0 0
0 0
1 0
1 1
4
w = u x G ↔ b0 = a0 + a1 + a3 (1)
17
b1 = a0 + a2 (2) g b2 = a1 + a3 (3) g b3 = a0 + a1 (4) g (5) b4 = a1 g b5 = a2 (6) b6 = a2 + a3 (7)
Cách giải mã (tt)
0
0
1
0
1
0
1
0
1
1
1
0
0
1
0
1
74
g
3
0 1
1 0
1 1
0 0
0 1
0 0
1 0
4
• Chọn bốn phương trình đơn giản nhất để giải các ai theo các b1 • Chọn các phương trình (4), (5), (6), (7) ta giải được:
a0 = b3 + b4 g g a1 = b4 G a2 = b5 g a3 = b5 + b6 • Hệ phương trình trên gọi là hệ phương trình giải mã.
• Có thể có nhiều hệ phương trình giải mã khác nhau, nhưng kết
18
quả sẽ giống nhau.
Mã tuyến tính hệ thống
• Một mã tuyến tính C(n,k) được gọi là mã tuyến tính hệ thống nếu mỗi từ mã
có một trong hai dạng sau:
• Dạng 1: Từ mã bao gồm phần thông tin k bit đi trước và phần còn lại (gồm
n-k bit) đi sau (phần này còn được gọi là phần dư thừa hay phần kiểm tra)
k bit thông tin
n - k bit kiểm tra
• Dạng 2: Ngược lại của dạng 1, từ mã bao gồm phần kiểm tra đi trước và
phần thông tin đi sau.
.
n - k bit kiểm tra
k bit thông tin
19
Ma trận sinh hệ thống
kn
)1
P (0 P
1 0
0 1
0 0
(1
kn
)1
G
|
P
I
nk
kk
knk
(
)
P 00 P 10
P 01 P 11
k
k
P k (
0 0 1 kk
P 0)1 ( 1)1 k kn (
P kn )(1 )1 ( )
• Ví dụ:
Mã hóa
u = 1101 → w = u x Ght = 1101000
1 0
0 1
0 0
0 0
1 0
1 1
0 1
)74(htG
Giãi mã
0
0
1
0
1
1
1
w = 0110100 → u = 0110
0
0
0
1
1
0
1
20
Ví dụ
xét mã khối tuyến tính C(7,4)có thông báo cần mã hóa u = (u0, u1, u2, u3) & từ mã phát đi tương ứng t = (t0, t1, t2, t3, t4, t5, t6)
)7,4(
G(4,7)=
=
G ~
1 1 0 1 0 0 0 0 1 1 0 1 0 0 0 0 1 1 0 1 0 0 0 0 1 1 0 1
(1) (2) (3) (4)
1 1 0 1 0 0 0 0 1 1 0 1 0 0 1 1 1 0 0 1 0 1 0 1 0 0 0 1
1’=1 2’=2 3’=1+3 4’=1+2+4
21
Cho G(4,7) dạng không chính tắc ta đi tìm G(4,7) dạng chính tắc:
Ví dụ
Cho tin cần phát đi: u = (u0, u1, u2, u3) = (1 0 1 1) ta tìm từ mã phát đi theo 2 công thức 5 & 8 từ đó rút ra nhận xét
t ~
.Gu ~
(u0, u1, u2, u3)
22
t0 = u0.1 + u1.0 + u2.0 + u3.0 = u0 = 1 t1 = u0.1 + u1.1 + u2.0 + u3.0 = u0 + u1= 1+0 = 1 t2 = u0.0 + u1.1 + u2.1 + u3.0 = u1 + u2= 0+1 = 1 t3 = u0.1 + u1.0 + u2.1 + u3.1 = u0 + u2 + u3= 1+1 + 1 = 1 t4 = u0.0 + u1.1 + u2.0 + u3.1 = u1 + u3= 0+1 = 1 t5 = u0.0 + u1.0 + u2.1 + u3.0 = u2= 1 t6 = u0.0 + u1.0 + u2.0 + u3.1 = u3= 1 Vậy ta có từ mã phát đi t = (1 1 1 1 1 1 1) không có dạng mã khối tuyến tính
1 1 0 1 0 0 0 0 1 1 0 1 0 0 1 1 1 0 0 1 0 1 0 1 0 0 0 1
t ~
.Gu ~
(u0, u1, u2, u3)
1 1 0 1 0 0 0 0 1 1 0 1 0 0 1 1 1 0 0 1 0 1 0 1 0 0 0 1
23
t0 = u0.1 + u1.0 + u2.1 + u3.1 = u0+ u2 + u3 = 1 + 1 +1 = 1 t1 = u0.1 + u1.1 + u2.1 + u3.0 = u0 + u1 + u2 = 1+ 0 + 1 = 0 t2 = u0.0 + u1.1 + u2.1 + u3.1 = u1 + u2 + u3 = 0+1+ 1 = 0 t3 = u0.1 + u1.0 + u2.0 + u3.0 = u0 = 1 t4 = u0.0 + u1.1 + u2.0 + u3.0 = u1 = 0 t5 = u0.0 + u1.0 + u2.1 + u3.0 = u2= 1 t6 = u0.0 + u1.0 + u2.0 + u3.1 = u3= 1 Vậy ta có từ mã phát đi: ( 1 0 0 1 0 1 1) có dạng mã khối tuyến tính
Ví dụ
• Dùng các phép biến đổi sơ cấp biển đổi các ma trận sinh
sau thành ma trận sinh hệ thống.
1
1
0
1
0
0
1
1
1
0
1
0
0
1
1
0
1
0
1
0
1
0
1
1
0
1
0
1
74G
74G
0 1
0 0
1 0
1 1
0 0
0 1
1 1
1 1
0 0
0 0
1 1
1 0
0 1
0 1
• Không phải mọi ma trận sinh đều có thể biến đổi thành ma
trận sinh hệ thống.
24
Phát hiện sai và sửa sai
• Nguyên lý phát hiện sai: Kiểm tra xem tổ hợp nhận có phải là từ mã hay
không, nếu không thì tổ hợp nhận là sai.
• Nguyên lý sửa sai: Kiểm tra xem tổ hợp nhận có khoảng cách Hamming
gần với từ mã nào nhất, thì đó chính là từ mã đúng đã phát đi.
• → Nguyên lý khoảng cách Hamming tối thiểu.
Không gian bù trực giao:
• Cho S là một không gian k chiều của không gian V n chiều. Gọi Sd là tập
tất cả các vectơ v trong V sao cho:
u
uS ,
v
0
• Sd được chứng minh là một không gian con của V và có số chiều là n-k. • Sd được gọi là không gian bù trừ trực giao của S và ngược lại.
25
Cách phát hiện sai
• Hệ quả:
• Mỗi ma trận G bất kỳ kích thước (k x n) với k hàng độc lập tuyến tính luôn tồn tại ma trận H kích thước (n-k)n với (n-k) hàng độc lập tuyến tính sao cho G x HT = 0, trong đó HT là ma trận chuyển vị của ma trận H.
• Hay: các vectơ hàng của H đều trực giao với các vectơ hàng của
G.
• Cách phát hiện sai:
• Nếu v là một từ mã được sinh ra từ ma trận G có ma trận trực
giao tương ứng là H thì: V x HT = 0
26
• Ngược lại nếu V x HT = 0 thì v là một từ mã.
Ma trận kiểm tra
• Ma trận kiểm tra H của một bộ mã có ma trận sinh Gkxn là
ma trận có kích thước (n-k)n sao cho :
G x HT = 0
• Ma trận sinh hệ thống có dạng Gkxn = [Ikk|Pk(n-k)]
T | I(n-k)(n-k)]
thì ma trận H(n-k)n = [Pk(n-k) Trong đó: I(n-k)(n-k) là ma trận đơn vị kích thước (n-k)(n-k), còn
Pk(n-k)
T là ma trận chuyển vị của ma trận Pk(n-k).
27
Cho G không hệ thống, tính H?
• VD: trên Z3, cho ma trận sinh của một mã như sau
đương
• Ta chuyển thành ma trận sinh của mã hệ thống
tương bằng một phép hoán vị p=(1,4,6,2,5,3) các cột về dạng [I | B].
• Ta tính được H* tươngứng với G* là
p-1.
Tính H bằng hoán vị ngược Thử lại: GHT = 0.
• •
17
28
Ma trận kiểm tra
• Ví dụ: Tìm ma trận kiểm tra của ma trận sinh hệ
thống sau:
1 0
0 1
0 0
0 0
1 0
1 1
0 1
)74(htG
0
0
1
0
1
1
1
0
0
0
1
1
0
1
1
0
1
1
1
0
0
1
1
1
0
0
1
0
)73(htH
0
1
1
1
0
0
1
29
Cách sửa sai
Syndrome – vectơ sửa sai (corrector)
S= v x HT được gọi là Syndrome hay vectơ sửa sai của
v và được kí hiệu là s(v). v là từ mã khi và chỉ khi
s(v)=0.
Từ ma trận H(n-k)n thành phần của Syndrome như sau:
S0 = v0p00 + v1p10 + . . . + vk-1pk-1,0 + vk
S1 = v0p01 + v1p11 + . . . + vk-1pk-1,1 + vk+1
…………….
30
Sn-k-1 = v0p0,n-k-1 + v1p1,n-k-1 + ...+ vk-1pk-1,n-k-1 + vn-1
Phương pháp giải mã mã khối tuyến tính:
(1) (2) (3) : e = (e0 e1 . . . en-1)
(4)
– Gọi từ mã phát đi : t = (t0 t1 . . . . tn-1) – Gọi từ mã thu được: r = (r0 r1 . . . . rn-1) – Vector sai – Trong đó ei = 1 nếu ti ri và ei = 0 nếu ti = ri Để phát hiện sai ta dùng thuật toán thử Syndrome: – S = r.HT = (s0 s1 . . . . sn-k-1) gồm n-k thành phần – S=0 nếu và chỉ nếu r là từ mã phát (r t) hoặc là tổ hợp
tuyến tính của các từ mã (gọi là vector sai không phát hiện được).
– S 0 thì r không phải là từ mã phát đi (r t) và do đó có sai
31
(e 0)
Phương pháp giải mã mã khối tuyến tính
(5)
32
Từ ma trận kiểm tra thành phần của Syndrome như sau: S0 = r0 + rn-kp00 + rn-k-1p10 + . . . + rn-ipk-1,0 S1 = r1 + rn-kp01 + rn-k-1p11 + . . . + rn-ipk-1,1 ……………. Sn-k-1 = rn-k-1 + rn-kp0,n-k-1 + rn-k+ip11 + .+ rn-ipk-1,n-k-1 Từ (5) tương tự như mạch mã hóa, ta có mạch tính Syndrome như sau:
Mạch tính Syndrome
r0
r1
rn-k
rn-1
....
...
P0,n-k-1
p00
p01
Pk-1,1
pk-1,0
Pk-1,n-k-1
+
+
+
sn-k-1
s1
so
33
Ví dụ:
Tính Syndrome của mã khối tuyến tính C(7,4) với ma trận
= (S0 S1 S2)
S=r.HT= (r0 r1 r2 r3 r4 r5 r6)
1 0 0 0 1 0 0 0 1 1 1 0 0 1 1 1 1 1 1 0 1
34
H đã cho với vector thu: r = (r0 r1 r2 r3 r4 r5 r6)
35
S0 = r0.1 + r1.0 + r2.0 + r3.1 + r4.0 + r5.1 + r6.1 = r0+ r3 + r5 + r6 S1 = r0.0 + r1.1 + r2.0 + r3.1 + r4.1 + r5.1 + r6.0 = r1+ r3 + r4 + r5 S2 = r0.0 + r1.0 + r2.1 + r3.0 + r4.1 + r5.1 + r6.1 = r2+ r4 + r5 + r6 Mạch tính Syndrome của mã hệ thống tuyến tính C(7,4)
Cách sửa sai Khi xác định được một giá trị Syndrome S = (S0, S1. . . . Sn-k-1) ta có đến 2k vector sai tương ứng, nhưng ta chỉ chọn các vector sai nào có trọng số nhỏ nhất là vector sai có nhiều khả năng nhất. Trong thực tế khi tìm được Syndrome ta thấy S trùng với cột nào của ma trận kiểm tra H thì có sai ở vị trí tương ứng. Ví dụ: “ 1 1 1” trùng với cột thứ sáu tính từ trái sang của ma trận H, ta kết luận vector nhận được r sai ở vị trí r5. Ta chỉ việc đổi trị số của r5 từ 0 sang 1 hoặc ngược lại là được vector nhận được đúng (r=t)
36
r = 1 0 0 1 0 0 1 e = 0 0 0 0 0 1 0 t = 1 0 0 1 0 1 1 -> đảo bit tại r5
Ví dụ tính Syndrome
• Tính Syndrome của mã khối tuyến tính C(7,4) với ma
trận sinh hệ thống sau: giả sử gửi tin: u=1001. Nhận
được v = 1011011. Nhận xét gì về mẫu tin nhận được.
1 0 0 0 1 1 0
0 1 0 0 0 1 1
)74(htG
0 0 1 0 1 1 1
37
0 0 0 1 1 0 1
Ví dụ tính Syndrome
)74(htG
1 0 0
0 1 0
0 0 1
0 0 0
1 0 1
1 1 1
0 1 1
1
1
0
0
0
0
1
1
0
1
0
1
1
1
1
1
T
1
0
1
1
1
0
0
1
0
1
htH
)73(
1
1
1
0
0
1
0
)73(htH
1
0
0
0
1
1
1
0
0
1
0
1
0
0
0
1
S(v) = v.HT = (111)
38
Cách sửa sai
• Qua ví dụ trên, ta thấy:
• S(v) = (111) trùng với cột thứ 3 của H, nên ta
sửa giá trị ở vị trí thứ 3.
v r = t
10110110010000 = 1001011
Vậy tin gửi đi là: 1001.
39
Mã Hamming
•Với mọi số nguyên dương m 3, 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
•Cấu trúc ma trận kiểm tra H với các cột là một vector m chiều khác không.
• H = [Imxm | P(n-k)k]
40
•Mỗi cột của ma trận P là vector m chiều, có trọng số là 2 hoặc lớn hơn.
Ví dụ: với m = 3, ma trận kiểm tra của mã (7,4) được viết dưới dạng
H(3,7) = (1)
1 0 0 1 0 1 1 0 1 0 1 1 1 0 0 0 1 0 1 1 1
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 kiểm tra xen kẽ với các bit mang tin chứ không còn tính chất khối, từ (1) ta có:
(2) H =
41
0 0 0 1 1 1 1 0 1 1 0 0 1 1 1 0 1 0 1 0 1
(3)
Để việc tạo mã đơn giản ta chọn các bit kiểm tra x, y, z ở 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 & thứ tư của các ký hiệu từ mã: t = (x, y, u0, z, u1, u2, u3) Tạo mã:
42
= 0 t.HT= (x, y, u0, z, u1, u2, u3) x
0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1
t = (x, y, u0, z, u1, u2, u3)
(2)
x.0 +y.0 +u0.0 +z.1 + u1.1 + u2.1 + u3.1 =0 z = u1 + u2 + u3 x.0 +y.1 +u0.1 +z.1 + u1.0 + u2.1 + u3.1 =0 y = u0 + u2 + u3 x.1 +y.0 +u0.1 +z.1 + u1.1 + u2.0 + u3.1 =0 x = u0 + u1 + u3
43
Ví dụ:
Tin cần phát đi: U = (u0, u1, u2, u3) = (1 0 1 1) x = u0 + u1 + u3 = 1+ 0+1= 0 y = u0 + u2 + u3 = 1+1+1 = 1 z = u1 + u2 + u3 = 0+1+1 = 0 Vậy từ mã phát đi sẽ là: t = ( 0 1 1 0 0 1 1) không có dạng mã khối. Giải mã Haming cũng giống như giải mã khối tuyến tính nhưng đơn giản hơn nhờ sử dụng ma trận kiểm tra H có dạng 2. Khi đó việc xác định vị trí ký hiệu sai tương đối thuận tiện.
44
Mã Hamming (tt)
•Ví dụ:
Với m = 3, ta có ma trận kiểm tra của bộ mã C(7,4) như sau:
1 0
0 1
0 0
1 1
0 1
1 1
1 0
3H
7
0
0
1
0
1
1
1
45
Mã Hamming (tt)
• 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 kiểm tra
xen kẽ với các bit mang tin chứ không còn tính chất khối. Và giá
trị của cột hi khi này bằng i (i = 1,2,…)
• Vị trí các bit kiểm tra ở các vị trí tương ứng 2i, với i = 0,1,2,…
1 0
1 0
1 1
1 1
0 0
Ứng với các vị trí tương ứng của từ mã. 0 0 c = (x,y,u0,z,u1,u2,u3) 3H 1 1
7
1
0
1
0
1
0
1
46
Tạo mã
• Theo tính chất mã khối tuyến tính ta có:
c.HT = 0
0 0
0 1
1 0
= 0.
(x,y,u0,z,u1,u2,u3) x
0 1
1 0
1 0
1
0
1
1 1
1 1
0 1
x = u0 + u1 + u3
y = u0 + u2 + u3
z = u1 + u2 + u3
47
Tạo mã
• Với tin cần phát: u = 1011
• x = u0 + u1 + u3 = 1 + 0 + 1 = 0
• y = u0 + u2 + u3= 1 + 1 + 1 = 1
• z = u1 + u2 + u3= 0 + 1 + 1 = 0
• Vậy từ mã phát đi: c = 0110011
48
Giải mã
• Cách giải mã giống với giải mã, phát hiện lỗi sai và sửa
lỗi của mã khối tuyến tính.
• Tính Syndrome – vectơ sửa sai
• S(v) = v.HT
• Nếu S(v) khác 0, ta xem giá trị s(v) trùng với cột thứ
mấy của ma trận H, thì có sai ở vị trí đó, và sửa lỗi.
49
Giải mã
• Với từ mã thu được v = 0 0 1 1 0 1 1
• S(v) = v x HT = 110. Trùng với cột thứ 6 của ma trận
H. Có nghĩa ký hiệu sai là ký hiệu thứ 6.
v = 0 0 1 1 0 0 1
u = 1001.
50
