Trong các hệ thống kỹ thuật số, dữ liệu được truyền cho giao tiếp có thể bị hỏng do nhiễu bên ngoài và bất kỳ lỗi vật lý nào khác. Nếu dữ liệu được truyền không khớp với dữ liệu đầu vào đã cho, thì nó được gọi là 'lỗi'. Các lỗi dữ liệu có thể xóa dữ liệu quan trọng trong hệ thống kỹ thuật số. Việc truyền dữ liệu sẽ ở dạng bit (0 và 1) trong hệ thống kỹ thuật số. Nếu bất kỳ ai trong số bit bị thay đổi, thì hiệu suất của toàn bộ hệ thống có thể bị ảnh hưởng. Nếu bit ‘1’ được thay đổi thành bit ‘0’ hoặc ngược lại, thì nó được gọi là lỗi bit. Có khác nhau các loại lỗi như lỗi bit đơn, nhiều lỗi và lỗi cụm. Trong bài viết này, chúng tôi thảo luận về việc sửa và phát hiện lỗi cũng như mã hamming.
Phát hiện và sửa lỗi là gì?
Trong truyền thông kỹ thuật số, dữ liệu sẽ bị mất nếu có lỗi trong quá trình truyền thông tin từ hệ thống / mạng này sang hệ thống / mạng khác. Vì vậy, điều quan trọng là phải tìm ra và sửa lỗi. Một số lỗi dò tìm và các phương pháp sửa chữa được sử dụng để phát hiện và sửa chữa các lỗi để giao tiếp hiệu quả. Nếu các phương pháp này được sử dụng, thì dữ liệu có thể được truyền với độ chính xác cao hơn.
Phát hiện lỗi được định nghĩa là, phương pháp được sử dụng để phát hiện các lỗi được truyền từ máy phát / máy gửi đến máy thu trong các hệ thống kỹ thuật số. Mã dự phòng được thêm vào dữ liệu trong quá trình truyền để tìm lỗi. Chúng được gọi là mã phát hiện lỗi.
Sửa lỗi là việc sửa dữ liệu được truyền từ máy phát đến máy thu. Sửa lỗi có thể được thực hiện theo hai loại.
Sửa lỗi lùi
Trong kiểu sửa lỗi này, người nhận sẽ yêu cầu người gửi truyền lại dữ liệu nếu người nhận phát hiện ra lỗi.
Sửa lỗi chuyển tiếp
nếu dữ liệu nhận được bởi người nhận tìm thấy lỗi, sau đó nó thực hiện các mã sửa lỗi, để sửa và phục hồi dữ liệu tự động.
Nếu có ‘m’ no.of bit dữ liệu và ‘r’ no.of bit dư thừa, thì các kết hợp thông tin sẽ là 2r.
2r> = m + r + 1
Các loại mã phát hiện lỗi
Các lỗi trong dữ liệu nhận được có thể được phát hiện bằng cách sử dụng 3 loại mã phát hiện lỗi. Đó là, kiểm tra chẵn lẻ, kiểm tra dự phòng theo chu kỳ (CRC) và kiểm tra dự phòng theo chiều dọc.
Kiểm tra chẵn lẻ
Bit dư thừa được gọi là bit chẵn lẻ được thêm vào để làm cho các bit số chẵn hoặc lẻ trong trường hợp chẵn lẻ hoặc chẵn lẻ. Máy thu đếm các bit no.of (1’s) trong một khung để thêm bit chẵn lẻ. Đây được gọi là kiểm tra chẵn lẻ. Nếu số 1 trong khung là chẵn, thì chẵn lẻ được sử dụng bằng cách thêm bit ‘1’với giá trị 0. Tương tự, của số 1 là số lẻ, sau đó tính chẵn lẻ lẻ được sử dụng bằng cách thêm bit có giá trị ‘1’.
phát hiện lỗi
Do đó, nó được sử dụng để đảm bảo rằng khung / ngày mà người nhận nhận được từ nguồn không bị hỏng. Trong kiểu phát hiện lỗi này, số của 1 phải nằm ngay trong khung đã nhận. Nó rất ít tốn kém hơn trong số tất cả các loại phát hiện lỗi.
Kiểm tra dự phòng theo chiều dọc (LRC)
khi tập hợp / khối bit được sắp xếp, thì phương pháp LRC có thể được sử dụng để kiểm tra bit chẵn lẻ trong mọi khung. Nó giúp gửi tập hợp các bit chẵn lẻ cùng với dữ liệu gốc và kiểm tra độ dư thừa.
Kiểm tra dự phòng theo chu kỳ
kiểu của anh ấy được sử dụng để phát hiện dữ liệu / khung nhận được từ nguồn có hợp lệ hay không. Nó liên quan đến việc phân chia nhị phân của dữ liệu cần được gửi và sử dụng đa thức (để tạo ra số chia). Trước sự truyền tải , một phép toán chia được thực hiện bởi người gửi trên data / bits / frame để tính phần còn lại.
kiểm tra dự phòng theo chu kỳ
Trong quá trình truyền dữ liệu thực tế từ người gửi, nó sẽ thêm phần còn lại vào cuối dữ liệu thực tế. Sự kết hợp của dữ liệu thực tế và phần còn lại được gọi là từ mã. Dữ liệu được truyền dưới dạng từ mã. Trong quá trình này, nếu dữ liệu bị hỏng, thì dữ liệu sẽ bị người nhận từ chối nếu không sẽ được chấp nhận.
Mã Hamming là gì?
Mã Hamming được định nghĩa là, một mã tuyến tính được sử dụng trong quá trình phát hiện lỗi lên đến lỗi 2 trung gian. Nó cũng có khả năng phát hiện các lỗi bit đơn. Trong phương pháp này, các bit dư thừa được người gửi thêm vào dữ liệu / thông điệp để mã hóa dữ liệu. Để phát hiện và sửa lỗi, các bit dư thừa này được thêm vào các vị trí nhất định cho quá trình sửa lỗi.
mã hamming
Lịch sử của mã Hamming
Năm 1950, Richard W. hamming phát minh ra mã Hamming để phát hiện và sửa các lỗi trong dữ liệu. Sau sự phát triển của máy tính với độ tin cậy cao hơn, ông đã giới thiệu mã hamming cho các mã sửa lỗi 1 và sau đó, ông đã mở rộng lên đến mã phát hiện 2 lỗi. Mã Hamming được tạo ra vì việc kiểm tra chẵn lẻ không thể phát hiện và sửa lỗi trong dữ liệu. Các mã Hamming được chèn vào bất kỳ cường độ khối dữ liệu nào giữa dữ liệu thực tế và các bit dự phòng. Ông đã phát triển một loạt các thuật toán để giải quyết các vấn đề của phương pháp sửa lỗi và những mã này được sử dụng rộng rãi trong bộ nhớ ECC.
Quy trình mã hóa tin nhắn bằng mã Hamming
Quá trình mã hóa một tin nhắn bằng cách sử dụng mã hamming bởi người gửi bao gồm 3 bước.
Bước 1: Bước đầu tiên là tính toán số bit dư thừa trong một tin nhắn
- Ví dụ: nếu một thông báo chứa các bit ‘n’ no.of và ‘p’ no.of bit dư thừa được thêm vào thông báo, thì ‘np’ chỉ ra (n + p + 1) các trạng thái khác nhau.
- Trong đó (n + p) thể hiện vị trí của lỗi ở mọi vị trí bit
- 1 (trạng thái bổ sung) đại diện cho không có lỗi.
- Vì ‘p’ chỉ ra 2 ^ p (2p) trạng thái, tương đương với (n + p + 1) trạng thái.
Bước 2: Đặt các bit dư thừa vào vị trí chính xác / đúng
Các bit 'p' được chèn vào các vị trí bit là lũy thừa của 2 như 1, 2, 4, 8, 16, v.v. Các vị trí bit này được biểu thị là p1 (vị trí 1), p2 (vị trí 2), p3 (vị trí 4), v.v.
Bước 3: Tính giá trị của các bit dư thừa
- Ở đây các bit chẵn lẻ được sử dụng để tính giá trị của các bit dư thừa.
- Các bit chẵn lẻ có thể làm cho số 1 trong một tin nhắn là chẵn hoặc lẻ.
- Nếu tổng số của 1 trong một tin nhắn là chẵn, thì chẵn lẻ được sử dụng
- Nếu tổng số của 1 trong một tin nhắn là số lẻ, thì tính chẵn lẻ được sử dụng.
Quy trình giải mã thông báo bằng mã Hamming
Quá trình giải mã một tin nhắn mà người nhận nhận được từ người gửi bằng cách sử dụng mã hamming bao gồm các bước sau. Quá trình này không có gì khác ngoài tính toán lại để phát hiện và sửa các lỗi trong thư.
Bước 1: Đếm số bit dư thừa không.
Công thức để mã hóa thông báo bằng cách sử dụng các bit dư thừa là,
2p≥ n + p + 1
Bước 2: sửa vị trí của tất cả các bit dư thừa
‘P’ no. Của các bit dự phòng được đặt ở các vị trí bit của lũy thừa 2 như 1,2,4,8,16,32, v.v.
Bước 3: kiểm tra chẵn lẻ (chẵn lẻ và chẵn lẻ)
Các bit chẵn lẻ được tính toán dựa trên số 1 trong các bit dữ liệu và các bit dư thừa.
Ví dụ
Tính chẵn lẻ của p1 sẽ là 1, 3, 5, 7, 9, 11,…
Tính chẵn lẻ của p2 sẽ là 2, 3, 6, 7, 10, 11,…
Độ chẵn lẻ của p3 sẽ là 4-7, 12-15, 20-23,…
Ưu điểm của mã Hamming
Ưu điểm chính của việc sử dụng mã hamming là hiệu quả về chi phí nếu luồng dữ liệu chứa lỗi bit đơn.
- Nó có thể cung cấp khả năng phát hiện lỗi và cũng chỉ ra bit có lỗi để sửa.
- Mã Hamming rất dễ sử dụng và tốt nhất trong bộ nhớ máy tính cũng như sửa và phát hiện lỗi một bit.
Nhược điểm của mã Hamming
- Nó chỉ tốt nhất để sửa và phát hiện lỗi một bit. Nếu nhiều bit lỗi, thì toàn bộ có thể bị hỏng.
- Thuật toán mã Hamming chỉ có thể giải quyết các lỗi bit đơn.
Các ứng dụng của mã Hamming
Mã Hamming được sử dụng trong,
- Tin học
- Viễn thông
- Nén dữ liệu
- Giải câu đố và mã turbo
- Vệ tinh
- CAM Plasma
- Dây được bảo vệ
- Modem
- Bộ nhớ máy tính
- Mở kết nối
- Những hệ thống nhúng và bộ xử lý
Câu hỏi thường gặp
1). Mã Hamming có thể phát hiện lỗi 2 bit không?
Mã Hamming có thể phát hiện và sửa lỗi tối đa 2 bit trong luồng dữ liệu
2). Làm cách nào để bạn sửa mã Hamming?
Mã Hamming được đặt trong bất kỳ độ dài dữ liệu nào giữa dữ liệu thực và các bit dư thừa. Những mã này là những nơi có khoảng cách tối thiểu là 3 bit
3). Mã chẵn lẻ là gì?
Mã chẵn lẻ hoặc bit chẵn lẻ đang thêm một bit vào khung đã nhận (dữ liệu chứa 1’s và 0’s) để tạo ra tổng số bit no.of (1’s) là chẵn hoặc lẻ.
4). Khoảng cách Hamming giữa các dữ liệu là gì?
Khoảng cách giới hạn giữa hai luồng dữ liệu khác nhau có độ dài bằng nhau là không bằng 1.
Khoảng cách giữa hai chuỗi dữ liệu có độ dài bằng nhau có thể được tính toán bằng cách sử dụng phép toán XOR.
Ví dụ: a = 11011001
b = 10011101
Khoảng cách Hamming có thể được tính bằng,
11011001 ⊕ 10011101 = 01000100 (số bit 1 là 2)
Khoảng cách hamming cho biết số 1 trong luồng dữ liệu kết quả
Vì vậy, d (11011001, 10011101) = 2
Tương tự, 010 ⊕ 011 = 001, d (010, 011) = 1.
5). Mã Hamming có tuần hoàn không?
Có, mã hamming tương đương với mã tuần hoàn có thể được sử dụng làm mã phát hiện lỗi.
Vì vậy, đây là tất cả về sửa lỗi và phát hiện, các loại phát hiện lỗi, mã hàng rào , quá trình mã hóa và giải mã tin nhắn bằng mã hamming, ứng dụng của mã hamming, ưu nhược điểm của mã Hamming. Đây là một câu hỏi dành cho bạn, 'Các ứng dụng phát hiện và sửa lỗi là gì?'
