Trong mã đối xứng DEA ta có nhắc đến khái niệm bit dư ngang bậc (extra parity bits) để sửa sai. Bạn đọc đã quen biết với việc mã hóa thông tin trong truyền thông điện tử, với các giao thức trong họ TCP/IP chắc chắn đều đã biết về những phương pháp mã hóa phát hiện sai (Error detection) và mã hóa tự sửa sai (Error correction) chẳng hạn như mã Hamming.
Dưới đây chỉ nhắc lại tóm tắt phương pháp tính toán thực hành cụ thể.
Nguyên tắc mấu chốt của mã Hamming là việc sử dụng một số
“bit dư ngang bậc” (extra parity bit) để nhận diện ra một bit sai trong thông tin được truyền đi.
Xuất phát từ một từ “mang thông tin”, một từ mã tương ứng được tạo như sau:
1. Đánh dấu mọi bit tại các vị trí là lũy thừa của 2 để làm bit dư ngang bậc (Các vị trí thứ 1, 2, 4, 8, 16, 32, 64…)
2. Tất cả các bit ở những vị trí khác còn lại dùng để ghi thông tin gốc cần truyền (Vị trí thứ 3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17,…)
3. Mỗi bit dư ngang bậc được tính toán theo giá trị của một số bit thông tin trong thông điệp. Vị trí của bit dư ngang bậc xác định dãy các bit lần lượt được xét hay bỏ qua:
- Vị trí 1: Xét 1 bit, bỏ qua 1 bit, xét 1 bit, bỏ qua 1 bit,v.v.
(1, 3, 5, 7, 9, 11, 13, 15…)
- Vị trí 2: Xét 2 bit, bỏ qua 2 bit, xét 2 bit, bỏ qua 2 bit,v.v.
(2, 3, 6, 7, 10, 11, 14, 15…)
- Vị trí 4: Xét 4 bit, bỏ qua 4 bit,v.v. (4, 5, 6, 7, 12, 13, 14, 15, 20, 21, 22, 23, …)
- Vị trí 8: Xét 8 bit, bỏ qua 8 bit, …(8 - 15, 24 - 31, 40 - 63, 80 - 95, …)
- Vị trí 16: Xét 16 bit, bỏ qua 16 bit, …(16 - 31, 48 - 63, 80 - 95, …)
4. Chọn lấy giá trị của bit dư parity là 1 nếu số các ký tự số 1 tại các vị trí được xét của nó là lẻ. Chọn lấy giá trị của bit dư parity là 0 nếu số các ký tự số 1 tại các vị trí được xét của nó là chẵn.
Ví dụ: Một thông điệp cần truyền là: 10011010
Tạo một thông điệp dữ liệu để truyền thông điệp đó, giành các vị trí thích hợp cho các bit dư:
_ _ 1 _ 0 0 1 _ 1 0 1 0
Tính giá trị cho từng bit dư parity (Dấu ? ký hiệu cho giá trị của bit parity cần tính)
• Vị trí 1 các bit được xét là 1, 3, 5, 7, 9, 11:
? _ 1 _ 0 0 1 _ 1 0 1 0. Có 4 số 1: chẵn, vậy giá trị bit parity ở vị trí 1 là 0: 0 _ 1 _ 0 0 1 _ 1 0 1 0
• Vị trí 2, các bit được xét là: 2, 3, 6, 7, 10, 11:
0 ? 1 _ 0 0 1 _ 1 0 1 0. Có 3 số 1: lẻ, vậy giá trị bit parity ở vị trí 2 là 1: 0 1 1 _ 0 0 1 _ 1 0 1 0
• Vị trí 4 các bit được xét là: 4, 5, 6, 7, 12:
0 1 1 ? 0 0 1 _ 1 0 1 0. Số lẻ: giá trị parity là 1:
0 1 1 1 0 0 1 _ 1 0 1 0
• Vị trí 8, các bit được xét là: 8, 9, 10, 11, 12:
0 1 1 1 0 0 1 ? 1 0 1 0. Số chẵn: giá trị parity là 0:
0 1 1 1 0 0 1 0 1 0 1 0
• Thông điệp mã hóa: 011100101010.
Phát hiện bit sai
Việc sử dụng bit parity đơn cho phép bạn phát hiện là tồn tại một bit sai trong thông điệp nhận được. Muốn sửa sai ta cần biết thêm vị trí cụ thể của bit sai đó trong thông điệp vì nếu chỉ biết là trong thông điệp có một bit sai mà không biết vị trí của nó thì không thể sửa được.
Nếu có nhiều bit dư parity gắn vào một thông điệp và các bit dư đó được tổ chức sao cho sự hiện diện của các bit sai tại các vị trí khác nhau sẽ cho ra những kết quả tính toán sai khác nhau thì các bit sai có thể nhận diện được. Trong một thông điệp 7 bit chẳng hạn, vị trí của bit sai có thể có 7 khả năng, vì vậy với 3 bit kiểm tra là ta đã có thể phát hiện không những là có 1 bit sai mà còn có thể định vị bit sai đó.
Tương tự như vậy, nếu một họ từ mã hóa được chọn sao cho khoảng cách bé nhất giữa các từ đó ít nhất bằng 3 thì mã sửa sai với 1 bit là có thể. Việc tiếp cận theo khoảng cách đó có tính chất “hình học”, trong khi lập luận tính toán bit sai trên kia có tính chất “đại số”. Những lập luận trên đây dùng để dẫn dắt ta đến khái niệm về Mã tự sửa sai Hamming, một phương pháp kiểm tra cho phép bạn tự sửa 1 sai.
Chẳng hạn, trong ví dụ trên cho ta thông điệp mã hóa là:
011100101010. Bên A gửi thông điệp đó đi. Giả sử do một lý do nào đó trong quá trình truyền tin, thông điệp bên B nhận được lại là:
011100101110. Người nhận (B) sẽ căn cứ vào việc kiểm tra các bit dư parity để phát hiện xem trong thông điệp có bit nào sai và do đó có thể tự sửa sai. B sẽ tính lại từng bit kiểm tra trong thông điệp nhận được bằng phương pháp như trước. Làm như vậy ta thấy ngay các bit parity thứ 2 và thứ 8 là sai! Vậy thì: 2 + 8 = 10. 10 là vị trí của bit thông tin bị sai (số 1 trong thông điệp nhận được ở vị trí thứ 10 là sai, cần sửa thành số 0). Trong trường hợp tổng quát, kiểm tra lại tất cả các bit parity sai, tổng của các vị trí của chúng cho ta vị trí của bit thông tin bị sai.
Bạn hãy tự kiểm tra bằng phương pháp mã Hamming xem trong các thông điệp nhận được sau đây, thông điệp nào có sai ở vị trí nào và cần được sửa lại như thế nào?
• 010101100011
• 111110001100
• 000010001010
Phụ lục 2