Mã Hamming: Phát hiện và sửa lỗi bằng các ví dụ
Lỗi là gì?
Dữ liệu truyền có thể bị hỏng trong quá trình giao tiếp. Nó có thể bị ảnh hưởng bởi tiếng ồn bên ngoài hoặc các lỗi vật lý khác. Trong tình huống như vậy, dữ liệu đầu vào không thể giống với dữ liệu đầu ra. Sự không khớp này được gọi là "Lỗi".
Các lỗi dữ liệu có thể dẫn đến mất dữ liệu quan trọng hoặc an toàn. Hầu hết việc truyền dữ liệu trong hệ thống kỹ thuật số sẽ ở dạng 'Truyền bit'. Ngay cả một thay đổi nhỏ cũng có thể ảnh hưởng đến hiệu suất của toàn bộ hệ thống. Trong chuỗi dữ liệu, nếu 1 được thay đổi thành 0 hoặc 0 được thay đổi thành 1 thì đó được gọi là “Lỗi bit”.
Các loại lỗi
Có ba loại lỗi bit chủ yếu xảy ra trong quá trình truyền dữ liệu từ người gửi đến người nhận.
- Lỗi bit đơn
- Lỗi nhiều bit
- Lỗi bùng nổ
Lỗi bit đơn
Sự thay đổi được thực hiện ở một bit trong toàn bộ chuỗi dữ liệu được gọi là “Lỗi bit đơn”. Tuy nhiên, lỗi bit đơn không phổ biến đến vậy. Hơn nữa, lỗi này chỉ xảy ra trong hệ thống truyền thông song song vì dữ liệu được truyền từng bit trên một dòng duy nhất. Do đó, có nhiều khả năng một dòng duy nhất có thể bị nhiễu.
Lỗi nhiều bit
Trong chuỗi dữ liệu, nếu có sự thay đổi hai hoặc nhiều bit trong chuỗi dữ liệu của máy phát đến máy thu thì đó được gọi là “Lỗi nhiều bit”.
Loại lỗi này chủ yếu xảy ra ở cả mạng truyền dữ liệu kiểu nối tiếp và song song.
Lỗi bùng nổ
Sự thay đổi tập hợp các bit trong chuỗi dữ liệu được gọi là “Lỗi bùng nổ”. Loại lỗi dữ liệu này được tính từ thay đổi bit đầu tiên đến thay đổi bit cuối cùng.
Phát hiện lỗi và sửa lỗi là gì?
Trong hệ thống truyền thông kỹ thuật số, lỗi sẽ được chuyển từ hệ thống truyền thông này sang hệ thống truyền thông khác. Nếu những lỗi này không được phát hiện và sửa chữa thì dữ liệu sẽ bị mất. Để giao tiếp hiệu quả, dữ liệu hệ thống cần được truyền với độ chính xác cao. Điều này sẽ được thực hiện bằng cách trước tiên xác định các lỗi và sửa chúng.
Phát hiện lỗi là phương pháp phát hiện các lỗi có trong dữ liệu được truyền từ máy phát đến máy thu trong hệ thống truyền dữ liệu.
Tại đây, bạn có thể sử dụng mã dự phòng để tìm các lỗi này bằng cách thêm vào dữ liệu khi nó được truyền từ nguồn. Các mã này được gọi là “Mã phát hiện lỗi”.
Ba loại mã phát hiện lỗi là:
- kiểm tra chẵn lẻ
- Kiểm tra dự phòng chu kỳ (CRC)
- Kiểm tra dự phòng theo chiều dọc (LRC)
kiểm tra chẵn lẻ
- Nó còn được gọi là kiểm tra tính chẵn lẻ.
- Nó có một cơ chế tiết kiệm chi phí để phát hiện lỗi.
- Trong kỹ thuật này, bit dư thừa được gọi là bit chẵn lẻ. Nó được nối thêm cho mọi đơn vị dữ liệu. Tổng số 1 trong đơn vị sẽ trở thành số chẵn, được gọi là bit chẵn lẻ.
Kiểm tra dự phòng theo chiều dọc
Trong kỹ thuật phát hiện lỗi này, một khối bit được sắp xếp theo dạng bảng. Phương pháp LRC giúp bạn tính toán bit chẵn lẻ cho mỗi cột. Tập hợp chẵn lẻ này cũng được gửi cùng với dữ liệu gốc. Khối chẵn lẻ giúp bạn kiểm tra sự dư thừa.
Kiểm tra dự phòng theo chu kỳ
Kiểm tra dự phòng theo chu kỳ là một chuỗi dự phòng phải được thêm vào cuối thiết bị. Đó là lý do tại sao đơn vị dữ liệu thu được sẽ chia hết cho số nhị phân thứ hai được xác định trước.
Tại đích, dữ liệu đến cần được chia cho cùng một số. Trong trường hợp không có phần dư, thì đơn vị dữ liệu được coi là đúng và được chấp nhận. Nếu không, điều đó chỉ ra rằng đơn vị dữ liệu bị hỏng trong quá trình truyền và do đó phải bị từ chối.
Mã Hamming là gì?
Mã Hamming là mã lót hữu ích cho việc phát hiện lỗi lên đến hai lỗi bit ngay lập tức. Nó có khả năng xảy ra lỗi bit đơn.
Trong mã Hamming, nguồn mã hóa thông điệp bằng cách thêm các bit dư thừa vào thông điệp. Các bit dư thừa này hầu hết được chèn và tạo tại các vị trí nhất định trong thông báo để thực hiện quá trình phát hiện và sửa lỗi.
Lịch sử mã Hamming
- Mã Hamming là một kỹ thuật do RWHamming xây dựng để phát hiện lỗi.
- Mã Hamming nên được áp dụng cho các đơn vị dữ liệu có độ dài bất kỳ và sử dụng mối quan hệ giữa dữ liệu và các bit dự phòng.
- Ông đã nghiên cứu vấn đề về phương pháp sửa lỗi và phát triển một loạt thuật toán ngày càng mạnh mẽ được gọi là mã Hamming.
- Năm 1950, ông xuất bản Mã Hamming, được sử dụng rộng rãi ngày nay trong các ứng dụng như bộ nhớ ECC.
Ứng dụng mã Hamming
Dưới đây là một số ứng dụng phổ biến của việc sử dụng mã Hamming:
- Vệ tinh
- Bộ nhớ máy tính
- modem
- PlasmaCAM
- Mở đầu nối
- Dây che chắn
- Bộ xử lý nhúng
Ưu điểm của mã Hamming
- Phương pháp mã Hamming có hiệu quả trên các mạng nơi các luồng dữ liệu được cung cấp cho các lỗi bit đơn.
- Mã Hamming không chỉ cung cấp khả năng phát hiện lỗi bit mà còn giúp bạn thụt lề bit chứa lỗi để có thể sửa lỗi.
- Sự dễ dàng sử dụng của mã hamming khiến chúng trở nên phù hợp nhất để sử dụng trong bộ nhớ máy tính và sửa lỗi đơn lẻ.
Nhược điểm của mã Hamming
- Mã phát hiện và sửa lỗi bit đơn. Tuy nhiên, nếu nhiều bit bị lỗi thì kết quả có thể dẫn đến một bit khác đúng cần được thay đổi. Điều này có thể khiến dữ liệu bị lỗi thêm.
- Thuật toán mã Hamming chỉ có thể giải quyết các vấn đề về bit đơn.
Cách mã hóa tin nhắn bằng mã Hamming
Quá trình người gửi sử dụng để mã hóa tin nhắn bao gồm ba bước sau:
- Tính tổng số bit dư thừa.
- Kiểm tra vị trí của các bit dư thừa.
- Cuối cùng, tính toán giá trị của các bit dư thừa này.
Khi các bit dư thừa trên được nhúng vào trong tin nhắn, nó sẽ được gửi tới người dùng.
Bước 1) Tính tổng số bit dư thừa.
Giả sử rằng tin nhắn chứa:
- n– số bit dữ liệu
- p – số bit dư thừa được thêm vào để np có thể biểu thị ít nhất (n + p + 1) trạng thái khác nhau.
Ở đây, (n + p) mô tả vị trí của lỗi trong mỗi vị trí bit (n + p) và một trạng thái bổ sung cho biết không có lỗi. Vì các bit p có thể chỉ ra 2p tiểu bang, 2p ít nhất phải bằng (n + p + 1).
Bước 2) Đặt các bit dư thừa vào đúng vị trí của chúng.
Các bit dự phòng p phải được đặt ở các vị trí bit có lũy thừa bằng 2. Ví dụ: 1, 2, 4, 8, 16, v.v. Chúng được gọi là p1 (tại vị trí 1), p2 (tại vị trí 2), p3 (ở vị trí 4), v.v.
Bước 3) Tính toán các giá trị của bit dư thừa.
Các bit dư thừa phải là các bit chẵn lẻ làm cho số 1 là chẵn hoặc lẻ.
Hai loại tương đương là?
- Tổng số bit trong thông báo được tạo thành số chẵn được gọi là chẵn lẻ.
- Tổng số bit trong thông báo được chuyển thành số lẻ được gọi là chẵn lẻ lẻ.
Ở đây, tất cả bit dư thừa p1 phải được tính là bit chẵn lẻ. Nó phải bao gồm tất cả các vị trí bit mà biểu diễn nhị phân của nó phải bao gồm số 1 ở vị trí thứ nhất ngoại trừ vị trí của p1.
P1 là bit chẵn lẻ cho mọi bit dữ liệu ở các vị trí có biểu diễn nhị phân bao gồm 1 ở vị trí ít quan trọng hơn, không bao gồm 1 Like (3, 5, 7, 9, …. )
P2 là bit chẵn lẻ cho mọi bit dữ liệu ở các vị trí có biểu diễn nhị phân bao gồm 1 ở vị trí thứ 2 từ phải sang, không bao gồm 2 Like (3, 6, 7, 10, 11,…)
P3 là bit chẵn lẻ cho mỗi bit ở các vị trí có biểu diễn nhị phân bao gồm số 1 ở vị trí thứ 3 từ phải sang không bao gồm 4 Like (5-7, 12-15,… )
Giải mã tin nhắn bằng mã Hamming
Người nhận nhận được các tin nhắn đến yêu cầu thực hiện tính toán lại để tìm và sửa lỗi.
Quá trình tính toán lại được thực hiện theo các bước sau:
- Đếm số bit dư thừa
- Định vị chính xác tất cả các bit dư thừa.
- Kiểm tra chẵn lẻ
Bước 1) Đếm số bit dư thừa
Bạn có thể sử dụng công thức tương tự để mã hóa, số bit dư thừa
2p ? n + p + 1
Ở đây số bit dữ liệu và p là số bit dư thừa.
Bước 2) Đặt chính xác tất cả các bit dư thừa
Ở đây, p là một bit dư thừa nằm ở vị trí bit có lũy thừa bằng 2, ví dụ: 1, 2, 4, 8, v.v.
Bước 3) Kiểm tra chẵn lẻ
Các bit chẵn lẻ cần được tính toán dựa trên các bit dữ liệu và các bit dư thừa.
p1 = chẵn lẻ(1, 3, 5, 7, 9, 11…)
p2 = số chẵn lẻ(2, 3, 6, 7, 10, 11…)
p3 = số chẵn lẻ(4-7, 12-15, 20-23…)
Tổng kết
- Dữ liệu truyền có thể bị hỏng trong quá trình giao tiếp
- Ba loại lỗi Bit là 1) Lỗi bit đơn 2) Lỗi nhiều bit 3) Lỗi bit bùng nổ
- Sự thay đổi được thực hiện ở một bit trong toàn bộ chuỗi dữ liệu được gọi là “Lỗi bit đơn”.
- Trong chuỗi dữ liệu, nếu có sự thay đổi hai hoặc nhiều bit trong chuỗi dữ liệu của máy phát đến máy thu thì đó được gọi là “Lỗi nhiều bit”.
- Sự thay đổi tập hợp các bit trong chuỗi dữ liệu được gọi là “Lỗi bùng nổ”.
- Phát hiện lỗi là phương pháp phát hiện các lỗi có trong dữ liệu được truyền từ máy phát đến máy thu trong hệ thống truyền dữ liệu
- Ba loại mã phát hiện lỗi là 1) Kiểm tra tính chẵn lẻ 2) Kiểm tra dự phòng theo chu kỳ (CRC) 3) Kiểm tra dự phòng theo chiều dọc (LRC)
- Mã Hamming là mã lót hữu ích cho việc phát hiện lỗi lên đến hai lỗi bit ngay lập tức. Nó có khả năng xảy ra lỗi bit đơn.
- Mã Hamming là một kỹ thuật do RWHamming xây dựng để phát hiện lỗi.
- Các ứng dụng phổ biến của việc sử dụng mã Hamming là Bộ nhớ máy tính vệ tinh, Modem, Bộ xử lý nhúng, v.v.
- Lợi ích lớn nhất của phương pháp mã Hamming là hiệu quả trên các mạng nơi các luồng dữ liệu được cung cấp cho các lỗi bit đơn.
- Hạn chế lớn nhất của phương pháp mã Hamming là nó chỉ có thể giải quyết các vấn đề về bit đơn.
- Chúng ta có thể thực hiện quá trình mã hóa và giải mã tin nhắn với sự trợ giúp của mã hamming.