Xem mẫu
Chương 4: Mã sửa sai 4.2 Ứng dụng lý thuyết nhóm cho
mã kiểm tra chẵn lẻ
2
Huỳnh Văn Kha 9/30/2010
Mã chẵn lẻ
• Mã chẵn lẻ ban đầu được xây dựng rất đơn giản • Cho trước bộ mã gồm các từ mã n bit nhị phân.
Một bit chẵn lẻ được thêm vào mỗi từ mã sao tổng số bit một mỗi từ mã là chẵn (hoặc lẻ)
• Ví dụ bộ mã ban đầu là {00, 01, 10, 11}, thì bộ mã chẵn lẻ thu được là {000, 011, 101, 110}
• Dễ dàng thấy rằng mọi sự truyền sai e bit, với e lẻ, đều phát hiện được
• Gọi r , r , …, r là các bit của một từ mã, số bit 1 là chẵn được viết là r1 + r2 + … + rn = 0 modulo 2
3
Huỳnh Văn Kha 9/30/2010
ðịnh nghĩa (mã chẵn lẻ) Cho hệ phương trình tuyến tính
Tập nghiệm của hệ trên gọi là một bộ mã kiểm tra chẵn lẻ (hay bộ mã nhóm)
Chú ý:
Các a , r là các số 0, 1. Phép cộng, nhân theo modulo 2 được định nghĩa như sau:
0 + 0 = 1 + 1 = 0; 0 + 1 = 1 + 0 = 1; 1.1 = 1; 1.0 = 0.1 = 0.0 = 0
4
Huỳnh Văn Kha 9/30/2010
Ma trận chẵn lẻ
• Ma trận A = [aij] gọi là ma trận kiểm tra chẵn lẻ • Nếu A có hạng t và các cột j1, …, jt là độc lập tuyến
tính thì có n – t = k các rj (j ≠ j1, …, jt) có thể được chọn tùy ý, và ta gọi là các bit thông tin
• Các bit thứ j1, …, jt gọi là các bit kiểm tra
• Mỗi khi cho giá trị của các bit thông tin ta được một từ mã duy nhất
• Bộ mã kiểm tra chẵn lẻ có 2k từ mã
5
Huỳnh Văn Kha 9/30/2010
Ví dụ 1
• Cho hệ sau
• Có thể chọn r , r , r làm bit kiểm tra và r , r , r làm bit thông tin
• Cho r = 0, r = 1, r = 0. Ta được r = 1, r = 1, r = 1. Và từ mã thu được là 111010
• Cho các giá trị khác cho r , r , r ta được 23 = 8 từ mã. Toàn bộ từ mã được cho trong bảng sau
...
- tailieumienphi.vn
nguon tai.lieu . vn