Lý thuyết về CRC thì trong bài viết này, ta không bàn tới nữa. Nếu bạn cần tìm tài liệu định nghĩa và giải thích chi tiết về nó, thì có thể tham khảo cuốn Data and Computer Communications (phiên bản thứ 8 trở lên). 

Ở phạm vi trong đây, ta chỉ minh họa thực tiễn một cách triển khai cơ chế CRC trong thực tế là như thế nào.

Trước tiên, ta cần ôn lại kiến thức về phép XOR, phép chia bit. Hiểu đơn giản, phép XOR giữa hai bit sẽ cho ra kết quả là 0 nếu cả hai bit giống nhau, trả về 1 nếu hai bit khác nhau. Còn phép chia bit thì ứng dụng trong đây sẽ có hơi khác một ít.

Lấy một đề bài cụ thể, ta có chuỗi bit D = 101011 và G=x^3 +1.

Tiến hành giải, ta bắt đầu phân tích đề bài. Cho G với hệ số mũ cao nhất là bậc 3, thì phải thêm 3 số 0 vào cuối chuỗi bit D. Tương tự, nếu G có bậc 2 thì thêm 2 số 0, bậc 4 thì thêm 4 số 0 vào cuối D. Cần phải tập quan sát và làm bước này đầu tiên, vì có thể sẽ quên hẳn nó sau khi tính ra chuỗi bit G rồi cắm đầu thực hiện chia.

Tiếp theo, ta tìm chuỗi bit của G. Quan sát ta thấy G có dạng x^3 +1. Phân tích ra sẽ có chuỗi bit tương đương là 1001. Tại sao lại như vậy? Vì phương trình đầy đủ của bậc 3 sẽ là x^3 + x^2 + x + d. Đề chỉ cho x^3 và 1 tức là cho x^3 và d trong phương trình chung. Cái nào được cho thì ta sử dụng bit 1, cái nào không thì ghi bit 0.

Do đó mà G = x^3 +1 sẽ có chuỗi bit tương đương là 1001. Giả sử G = x^4 + x + 1 thì sao? Sẽ có chuỗi bit tương đương là 10011.

Tiếp theo, ta sử dụng phép chia bit để chia D (đã thêm bit 0 tương ứng với bậc của G) cho chuỗi G.

Trong phép chia này, ta cắt D ra có chiều dài tương đương chiều dài chuỗi G (G có 4 bit thì cắt D 4 bit ra để chia) và sử dụng XOR để tính dư. Thay vì phép chia thông thường là ta sử dụng phép trừ, thì sau khi đặt G xuống dưới chuỗi D vừa cắt ra để chia, ta sử dụng phép XOR. Nếu bit dư tìm được ngắn hơn G thì hạ xuống 1 bit của D để thực hiện tiếp.

Nếu hạ xuống mà vẫn chưa đủ chiều dài bằng G, thì ghi kết quả là bit 0 rồi tiếp tục hạ thêm 1 bit của D xuống để đủ chiều dài cần thiết cho việc chia.

Lưu ý: kết quả cuối cùng thu được phải là một chuỗi bit dư có chiều dài BẰNG VỚI bậc của phương trình G ban đầu.

Ví dụ, nếu G bậc 3 thì chuỗi bit dư phải dài bằng 3 và G ban đầu là 4 thì chuỗi là dư phải tương đương là 4.

VÕ TÌNH THƯƠNG

votinhthuong9@gmail.com

Advertisements