Đối với mã sửa sai Hamming, cho xâu gốc là 10100111000011, xâu truyền đi là:
Trả lời:
Đáp án đúng: C
Để giải bài toán này, ta cần áp dụng mã sửa sai Hamming. Mã Hamming thêm các bit parity vào xâu gốc để có thể phát hiện và sửa lỗi. Các bước thực hiện như sau:
1. **Xác định số lượng bit parity cần thiết:** Gọi *m* là số bit dữ liệu và *r* là số bit parity. Ta cần tìm *r* sao cho 2^r >= m + r + 1. Trong trường hợp này, m = 14 (số bit trong xâu gốc 10100111000011). Ta thấy rằng 2^4 = 16 > 14 + 4 + 1 = 19 là sai. 2^5 = 32 > 14 + 5 + 1 = 20 là đúng. Vậy r = 5.
2. **Xác định vị trí các bit parity:** Các bit parity được đặt ở các vị trí là lũy thừa của 2 (1, 2, 4, 8, 16).
3. **Tính giá trị của các bit parity:** Mỗi bit parity kiểm tra một tập các bit dữ liệu. Bit parity ở vị trí 2^i kiểm tra các bit có vị trí mà biểu diễn nhị phân của nó có bit thứ i là 1 (tính từ phải sang trái, bắt đầu từ 0).
4. **Xây dựng xâu Hamming:** Sau khi tính toán các bit parity, ta chèn chúng vào xâu gốc ở các vị trí tương ứng.
Xâu gốc: 10100111000011 (14 bits)
Số bit parity: 5
Vị trí các bit parity: 1, 2, 4, 8, 16
Xâu Hamming (với các vị trí parity đánh dấu là 'p'): p p 1 p 0 1 0 p 0 1 1 1 0 0 0 p 1 1
Bây giờ, ta cần tính các bit parity:
- p1 kiểm tra các bit ở vị trí 1, 3, 5, 7, 9, 11, 13, 15, 17, 19. Tức là, p1 kiểm tra các bit: p1, 1, 0, 0, 0, 1, 0, 0, 1. Để parity là chẵn (even parity), tổng số bit 1 phải là số chẵn. Vì hiện tại có 4 bit 1, nên p1 = 0.
- p2 kiểm tra các bit ở vị trí 2, 3, 6, 7, 10, 11, 14, 15, 18, 19. Tức là, p2 kiểm tra các bit: p2, 1, 1, 1, 1, 0, 0, 1. Để parity là chẵn, p2 = 1.
- p4 kiểm tra các bit ở vị trí 4, 5, 6, 7, 12, 13, 14, 15, 20. Tức là, p4 kiểm tra các bit: p4, 0, 1, 1, 0, 0, 0, 1. Để parity là chẵn, p4 = 1.
- p8 kiểm tra các bit ở vị trí 8, 9, 10, 11, 12, 13, 14, 15. Tức là, p8 kiểm tra các bit: p8, 0, 0, 1, 0, 0, 0, 1. Để parity là chẵn, p8 = 0.
- p16 kiểm tra các bit ở vị trí 16, 17, 18, 19, 20. Tức là, p16 kiểm tra các bit: p16, 1, 0, 1, 1. Để parity là chẵn, p16 = 1.
Vậy xâu Hamming hoàn chỉnh là: 0 1 1 1 0 1 0 0 0 1 0 0 0 1 1 1. Đảo ngược lại ta có: 1110001001011110 (19 bits).
So sánh với các đáp án, không có đáp án nào hoàn toàn trùng khớp. Có thể có sự khác biệt trong cách tính parity (chẵn/lẻ) hoặc cách đánh số bit. Tuy nhiên đáp án gần nhất là đáp án B.
