Mã phát hiện & sửa lỗi
Chúng ta biết rằng các bit 0 và 1 tương ứng với hai dải điện áp tương tự khác nhau. Vì vậy, trong quá trình truyền dữ liệu nhị phân từ hệ thống này sang hệ thống khác, nhiễu cũng có thể được thêm vào. Do đó, dữ liệu nhận được ở hệ thống khác có thể bị lỗi.
Điều đó có nghĩa là một bit 0 có thể thay đổi thành 1 hoặc một bit 1 có thể thay đổi thành 0. Chúng ta không thể tránh được sự can thiệp của nhiễu. Tuy nhiên, chúng tôi có thể lấy lại dữ liệu ban đầu trước tiên bằng cách phát hiện xem có bất kỳ lỗi nào hay không và sau đó sửa các lỗi đó. Với mục đích này, chúng tôi có thể sử dụng các mã sau.
- Mã phát hiện lỗi
- Mã sửa lỗi
Error detection codes- được sử dụng để phát hiện (các) lỗi có trong dữ liệu nhận được (luồng bit). Những mã này chứa (các) bit, được bao gồm (nối thêm) vào dòng bit gốc. Các mã này phát hiện lỗi, nếu nó xảy ra trong quá trình truyền dữ liệu gốc (luồng bit).Example - Mã chẵn lẻ, mã Hamming.
Error correction codes- được sử dụng để sửa (các) lỗi có trong dữ liệu đã nhận (dòng bit) để chúng ta lấy dữ liệu gốc. Mã sửa lỗi cũng sử dụng chiến lược tương tự của mã phát hiện lỗi.Example - Mã Hamming.
Do đó, để phát hiện và sửa lỗi, (các) bit bổ sung được nối vào các bit dữ liệu tại thời điểm truyền.
Mã chẵn lẻ
Có thể dễ dàng bao gồm (nối thêm) một bit chẵn lẻ ở bên trái MSB hoặc bên phải LSB của dòng bit gốc. Có hai loại mã chẵn lẻ, đó là mã chẵn lẻ và mã chẵn lẻ dựa trên loại chẵn lẻ được chọn.
Mã chẵn lẻ
Giá trị của bit chẵn lẻ phải bằng 0, nếu số bit chẵn có trong mã nhị phân. Nếu không, nó phải là một. Vì vậy, số lượng chẵn có trongeven parity code. Mã chẵn lẻ chứa các bit dữ liệu và bit chẵn lẻ.
Bảng sau đây cho thấy even parity codestương ứng với mỗi mã nhị phân 3 bit. Ở đây, bit chẵn lẻ được đưa vào bên phải LSB của mã nhị phân.
| Mã nhị phân | Bit chẵn lẻ | Mã chẵn lẻ |
|---|---|---|
| 000 | 0 | 0000 |
| 001 | 1 | 0011 |
| 010 | 1 | 0101 |
| 011 | 0 | 0110 |
| 100 | 1 | 1001 |
| 101 | 0 | 1010 |
| 110 | 0 | 1100 |
| 111 | 1 | 1111 |
Ở đây, số bit có trong mã chẵn lẻ là 4. Vì vậy, số bit chẵn có thể có trong các mã chẵn lẻ này là 0, 2 & 4.
Nếu hệ thống khác nhận được một trong các mã chẵn lẻ này, thì dữ liệu nhận được sẽ không có lỗi. Các bit khác với bit chẵn lẻ giống như bit của mã nhị phân.
Nếu hệ thống khác nhận được không phải là mã chẵn lẻ, thì sẽ có (các) lỗi trong dữ liệu đã nhận. Trong trường hợp này, chúng tôi không thể dự đoán mã nhị phân ban đầu vì chúng tôi không biết (các) vị trí bit bị lỗi.
Do đó, bit chẵn lẻ chỉ hữu ích để phát hiện lỗi trong mã chẵn lẻ nhận được. Nhưng, nó không đủ để sửa lỗi.
Mã chẵn lẻ lẻ
Giá trị của bit chẵn lẻ lẻ phải bằng 0, nếu có số lẻ trong mã nhị phân. Nếu không, nó phải là một. Vì vậy, số lẻ của những người có trongodd parity code. Mã chẵn lẻ lẻ chứa các bit dữ liệu và bit chẵn lẻ lẻ.
Bảng sau đây cho thấy odd parity codestương ứng với mỗi mã nhị phân 3 bit. Ở đây, bit chẵn lẻ lẻ được đưa vào bên phải LSB của mã nhị phân.
| Mã nhị phân | Bit chẵn lẻ lẻ | Mã chẵn lẻ lẻ |
|---|---|---|
| 000 | 1 | 0001 |
| 001 | 0 | 0010 |
| 010 | 0 | 0100 |
| 011 | 1 | 0111 |
| 100 | 0 | 1000 |
| 101 | 1 | 1011 |
| 110 | 1 | 1101 |
| 111 | 0 | 1110 |
Ở đây, số bit có trong các mã chẵn lẻ lẻ là 4. Vì vậy, số bit lẻ có thể có trong các mã chẵn lẻ lẻ này là 1 & 3.
Nếu hệ thống khác nhận được một trong các mã chẵn lẻ lẻ này, thì dữ liệu nhận được sẽ không có lỗi. Các bit khác với bit chẵn lẻ lẻ giống như bit của mã nhị phân.
Nếu hệ thống khác nhận được không phải là mã chẵn lẻ lẻ, thì có một lỗi trong dữ liệu nhận được. Trong trường hợp này, chúng tôi không thể dự đoán mã nhị phân ban đầu vì chúng tôi không biết (các) vị trí bit bị lỗi.
Do đó, bit chẵn lẻ lẻ chỉ hữu ích để phát hiện lỗi trong mã chẵn lẻ nhận được. Nhưng, nó không đủ để sửa lỗi.
Mã Hamming
Mã Hamming hữu ích cho cả việc phát hiện và sửa lỗi có trong dữ liệu nhận được. Mã này sử dụng nhiều bit chẵn lẻ và chúng ta phải đặt các bit chẵn lẻ này vào vị trí lũy thừa của 2.
Các minimum value of 'k' mà quan hệ sau là đúng (hợp lệ) không là gì ngoài số bit chẵn lẻ cần thiết.
$$ 2 ^ k \ geq n + k + 1 $$
Ở đâu,
'n' là số bit trong mã nhị phân (thông tin)
'k' là số bit chẵn lẻ
Do đó, số bit trong mã Hamming bằng n + k.
Hãy để Hamming codelà $ b_ {n + k} b_ {n + k-1} ..... b_ {3} b_ {2} b_ {1} $ & bit chẵn lẻ $ p_ {k}, p_ {k-1}, .... p_ {1} $. Chúng ta chỉ có thể đặt các bit chẵn lẻ 'k' theo lũy thừa của 2 vị trí. Ở các vị trí bit còn lại, chúng ta có thể đặt các bit 'n' của mã nhị phân.
Dựa trên yêu cầu, chúng ta có thể sử dụng chẵn lẻ hoặc chẵn lẻ trong khi tạo mã Hamming. Tuy nhiên, kỹ thuật chẵn lẻ tương tự nên được sử dụng để tìm xem có lỗi nào xuất hiện trong dữ liệu đã nhận hay không.
Làm theo quy trình này để tìm parity bits.
Tìm giá trị của p1, dựa trên số lượng đơn vị có mặt ở các vị trí bit b 3 , b 5 , b 7 , v.v. Tất cả các vị trí bit này (hậu tố) trong hệ nhị phân tương đương của chúng có giá trị '1' ở vị trí là 2 0 .
Tìm giá trị của p2, dựa trên số lượng đơn vị có ở các vị trí bit b 3 , b 6 , b 7 , v.v. Tất cả các vị trí bit này (hậu tố) trong hệ nhị phân tương đương của chúng có giá trị '1' ở vị trí là 2 1 .
Tìm giá trị của p3, dựa trên số lượng đơn vị có ở các vị trí bit b 5 , b 6 , b 7 , v.v. Tất cả các vị trí bit này (hậu tố) trong hệ nhị phân tương đương của chúng có giá trị '1' ở vị trí là 2 2 .
Tương tự, tìm các giá trị khác của bit chẵn lẻ.
Làm theo quy trình này để tìm check bits.
Tìm giá trị của c 1 , dựa trên số đơn vị có ở các vị trí bit b 1 , b 3 , b 5 , b 7 , v.v. Tất cả các vị trí bit này (hậu tố) trong hệ nhị phân tương đương của chúng có giá trị '1' ở vị trí là 2 0 .
Tìm giá trị của c 2 , dựa trên số lượng đơn vị có mặt ở các vị trí bit b 2 , b 3 , b 6 , b 7 , v.v. Tất cả các vị trí bit này (hậu tố) trong hệ nhị phân tương đương của chúng có giá trị '1' ở vị trí là 2 1 .
Tìm giá trị của c 3 , dựa trên số lượng đơn vị có ở các vị trí bit b 4 , b 5 , b 6 , b 7 , v.v. Tất cả các vị trí bit này (hậu tố) trong hệ nhị phân tương đương của chúng có giá trị '1' ở vị trí là 2 2 .
Tương tự, tìm các giá trị khác của các bit kiểm tra.
Tương đương thập phân của các bit kiểm tra trong dữ liệu nhận được cung cấp giá trị của vị trí bit, nơi có lỗi. Chỉ cần bổ sung giá trị hiện tại ở vị trí bit đó. Do đó, chúng ta sẽ nhận được mã nhị phân ban đầu sau khi loại bỏ các bit chẵn lẻ.
ví dụ 1
Hãy để chúng tôi tìm mã Hamming cho mã nhị phân, d 4 d 3 d 2 d 1 = 1000. Xét các bit chẵn lẻ.
Số bit trong mã nhị phân đã cho là n = 4.
Chúng ta có thể tìm số lượng bit chẵn lẻ cần thiết bằng cách sử dụng quan hệ toán học sau.
$$ 2 ^ k \ geq n + k + 1 $$
Thay thế, n = 4 trong quan hệ toán học trên.
$$ \ Rightarrow 2 ^ k \ geq 4 + k + 1 $$
$$ \ Rightarrow 2 ^ k \ geq 5 + k $$
Giá trị nhỏ nhất của k thỏa mãn quan hệ trên là 3. Do đó, chúng ta yêu cầu 3 bit chẵn lẻ p 1 , p 2 và p 3 . Do đó, số bit trong mã Hamming sẽ là 7, vì có 4 bit trong mã nhị phân và 3 bit chẵn lẻ. Chúng ta phải đặt các bit chẵn lẻ và các bit của mã nhị phân trong mã Hamming như hình dưới đây.
Các 7-bit Hamming code là $ b_ {7} b_ {6} b_ {5} b_ {4} b_ {3} b_ {2} b_ {1} = d_ {4} d_ {3} d_ {2} p_ {3} d_ {1 } p_ {2} bp_ {1} $
Bằng cách thay thế các bit của mã nhị phân, mã Hamming sẽ là $ b_ {7} b_ {6} b_ {5} b_ {4} b_ {3} b_ {2} b_ {1} = 100p_ {3} Op_ {2 } p_ {1} $. Bây giờ, chúng ta hãy tìm các bit chẵn lẻ.
$$ p_ {1} = b_ {7} \ oplus b_ {5} \ oplus b_ {3} = 1 \ oplus 0 \ oplus 0 = 1 $$
$$ p_ {2} = b_ {7} \ oplus b_ {6} \ oplus b_ {3} = 1 \ oplus 0 \ oplus 0 = 1 $$
$$ p_ {3} = b_ {7} \ oplus b_ {6} \ oplus b_ {5} = 1 \ oplus 0 \ oplus 0 = 1 $$
Bằng cách thay thế các bit chẵn lẻ này, Hamming code sẽ là $ b_ {7} b_ {6} b_ {5} b_ {4} b_ {3} b_ {2} b_ {1} = 1001011 $.
Ví dụ 2
Trong ví dụ trên, chúng tôi có mã Hamming là $ b_ {7} b_ {6} b_ {5} b_ {4} b_ {3} b_ {2} b_ {1} = 1001011 $. Bây giờ, hãy để chúng tôi tìm vị trí lỗi khi mã nhận được là $ b_ {7} b_ {6} b_ {5} b_ {4} b_ {3} b_ {2} b_ {1} = 1001111 $.
Bây giờ, chúng ta hãy tìm các bit kiểm tra.
$$ c_ {1} = b_ {7} \ oplus b_ {5} \ oplus b_ {3} \ oplus b_ {1} = 1 \ oplus 0 \ oplus 1 \ oplus1 = 1 $$
$$ c_ {2} = b_ {7} \ oplus b_ {6} \ oplus b_ {3} \ oplus b_ {2} = 1 \ oplus 0 \ oplus 1 \ oplus1 = 1 $$
$$ c_ {3} = b_ {7} \ oplus b_ {6} \ oplus b_ {5} \ oplus b_ {4} = 1 \ oplus 0 \ oplus 0 \ oplus1 = 0 $$
Giá trị thập phân của các bit kiểm tra cho biết vị trí của lỗi trong mã Hamming nhận được.
$$ c_ {3} c_ {2} c_ {1} = \ left (011 \ right) _ {2} = \ left (3 \ right) _ {10} $$
Do đó, lỗi xuất hiện ở bit thứ ba (b 3 ) của mã Hamming. Chỉ cần bổ sung giá trị có trong bit đó và loại bỏ các bit chẵn lẻ để có được mã nhị phân ban đầu.