Cyclic Redundancy Check and Modulo-2 Division – GeeksforGeeks

crc hoặc Kiểm tra dự phòng theo chu kỳ là một phương pháp phát hiện các thay đổi/lỗi ngẫu nhiên trong các kênh liên lạc. Crc sử dụng đa thức trình tạo có sẵn cho cả người gửi và người nhận. Ví dụ đa thức sinh có dạng x3 + x + 1. Đa thức sinh này đại diện cho khóa 1011. Một ví dụ khác là x2 + 1, đại diện cho khóa 101.

Người gửi (tạo dữ liệu được mã hóa từ dữ liệu và đa thức trình tạo (hoặc khóa):

1. Đầu tiên, tăng cường dữ liệu nhị phân bằng cách thêm k-1 số 0 vào cuối dữ liệu
2. Sử dụng phép chia nhị phân theo mô-đun 2 để chia dữ liệu nhị phân cho khóa và lưu trữ phần còn lại của phép chia.
3. Nối phần còn lại vào cuối dữ liệu để tạo thành truyền dữ liệu được mã hóa

Đầu nhận (kiểm tra lỗi trong quá trình truyền) Thực hiện lại phép chia modulo 2, nếu phần dư bằng 0 thì không có lỗi.

Trong bài viết này, chúng ta chỉ tập trung tìm phần còn lại là từ kiểm tra và từ mã.

Phép chia modulo 2: Quy trình chia nhị phân modulo 2 giống như quy trình chia các số thập phân quen thuộc. Chỉ là chúng ta đang sử dụng xor ở đây thay vì phép trừ.

• Tại mỗi bước, một bản sao của số chia (hoặc dữ liệu) được XOR với k bit của số bị chia (hoặc khóa).
• Kết quả (phần còn lại) của thao tác XOR là (n-1) bit và sau khi kéo 1 bit, nó được sử dụng trong bước tiếp theo để tạo ra n bit dài.
• Chúng tôi có kết quả khi không còn dữ liệu để thả xuống. (n-1) bit của phần còn lại được thêm vào bên gửi.

Minh họa:Ví dụ 1 (đường truyền không có lỗi):





Ví dụ 2: (lỗi đường truyền)





Đã phát hiện lỗi ở bên nhận do phần còn lại không phải toàn là số không.

Triển khai Dưới đây là một triển khai để tạo từ mã từ khóa và dữ liệu nhị phân đã cho.

Đầu ra:

Độ phức tạp về thời gian: o(n)

Không gian phụ trợ: o(n)

Lưu ý rằng crc chủ yếu nhằm mục đích ngăn chặn các lỗi phổ biến trên kênh liên lạc, chứ không phải là biện pháp bảo vệ thích hợp chống lại sự thay đổi dữ liệu có chủ ý (xem lý do tại đây)

Triển khai sử dụng thao tác bit: Việc tạo từ mã crc cũng có thể được thực hiện bằng các phương pháp thao tác bit, như minh họa bên dưới:

Độ phức tạp về thời gian:o(n)

Không gian phụ trợ:o(n)

Tham khảo:https://en.wikipedia.org/wiki/cyclic_redundancy_check

Bài viết này được đóng góp bởi jay patel. Nếu bạn thích geeksforgeeks và muốn đóng góp, bạn cũng có thể viết một bài báo và gửi bài viết của mình tới review-team@geeksforgeeks.org. Xem các bài viết của bạn nổi bật trên trang chủ của geeksforgeeks và giúp đỡ các chuyên viên máy tính khác.

Vui lòng để lại nhận xét nếu bạn thấy điều gì không đúng hoặc nếu bạn muốn chia sẻ thêm thông tin về các chủ đề trên