Thứ Tư, Tháng Mười 27, 2021
Trang chủ TIN TỨC Tìm hiểu CRC

Tìm hiểu CRC

🤔 Có bạn nào thắc mắc là các thiết bị điện tử ngoài việc chúng có thể giao tiếp trao đổi thông tin với nhau. Làm sao chúng có thể biết được thông tin nhận được là đúng hay sai?

Khi mà chúng lại hoạt động trong môi trường thực tế. Nơi luôn có nhiều yếu tố xung quanh tác động đến. Trường hợp khả năng xảy ra Lỗi trong quá trình truyền data luôn có thể xảy ra.

⇒ Nhìn lại nếu ta có thể tận dụng chính khả năng truyền/nhận data. Và làm cách nào đó, để trong chính gói data nhận được có chứa thông tin cho chúng biết data đó là đúng hay sai.

⇒ Có một thuật ngữ để gọi chung cho vấn đề này là các phương pháp “Phát hiện Lỗi” (Error Detection).

Hiện tại có khá nhiều phương pháp khác nhau. Trong bài này mình sẽ tập trung nói về phương pháp CRC.

Vậy CRC là gì?

_ CRC viết tắt của (Cyclic Redundancy Check).
_ Là một thuật toán CheckSum, để phát hiện sự không nhất quán của data.
_ Ví dụ như “lỗi bit” trong quá trình truyền data.

_ Một CheckSum, được tính toán bởi CRC, sau đó được bên TRUYỀN đính kèm vào gói data, để giúp bên NHẬN phát hiện những lỗi như vậy.

🤔 Vậy CRC được tính như thế nào? Và làm sao sử dụng CRC để xác minh?
⇒ Tất cả những câu hỏi đó bạn có thể tìm thấy trong bài phân tích này: Understanding and implementing CRC (Cyclic Redundancy Check) calculation.
⇒ Còn phần dưới mình đề cập đến những điểm mấu chốt về CRC.

1. Phép tính CRC?

_ Nó dựa trên “Phép chia Đa thức” (Division of Polynomial).

⚠️ Lưu ý: “Phép chia Đa thức” khác hoàn toàn với “Phép chia Số nguyên” thông thường.
Các Chuỗi nhị phân không được coi là các giá trị Số nguyên.
Mà là “Binary Polyonimal” trong đó các bit được sử dụng làm Hệ số. Vd:

Binary Integer (Hệ số 2) Binary Polyonimal
0b1010 0b1010
1*23 + 0*22 + 1*21 + 0*20
1*8 + 0*4 + 1*2 + 0*1
⇒ Số Nguyên 10
1*x3 + 0*x2 + 1*x1 + 0*x0

2. Phép chia Đa thức của CRC?

The CRC Checksum = Divident % Divisor

    • Số chia (Divident):InputData.
    • Số bị chia (Divisor):Generator Polynomial.
      _ Được xác định bởi thuật toán CRC đã sử dụng.
      _ Với thuật toán CRC-n sẽ cần dùng 1 Polynom cố định có kích thước (n+1) bit.
      _ Trong đó bit MSBbit LSB phải luôn là bit 1.
    • Phần dư phép chia (Remainder):CRC CheckSum (n) bit.

! Mấu chốt cơ bản của Thuật toán CRC là dựa trên phép toán XOR.

3. Cách tính CRC và Cách xác minh CRC thủ công

CRC Manual Calculation
CRC Verification

_ Trong cả 2 quá trình tính trên, thuật toán CRC chỉ dừng lại khi Polynom làm cho tất cả các bit trên InputData đều là 0.

_ Theo cách tính trên, ta thấy InputData đứng yên, còn Polynom sẽ từ từ dịch chuyển SANG PHẢI sau mỗi phép tính XOR.

🤔 Nhưng làm sao chúng ta triển khai cách tính trên cho máy tính. Trong khi luồng InputData thường khá là dài và ko có kích thước cố định.
⇒ Lúc này ta cần sử dụng đến khái niệm “Thanh ghi dịch” (A Shift Register).

4. Thanh ghi dịch?

_ Một Thanh ghi có độ rộng cố định (phù hợp dùng cho Polynom cũng có giá trị xác định).
_ Nó có thể dịch chuyển nội dung của nó 1 bit qua bên trái hoặc bên phải.
_ Khi đó nó sẽ loại bỏ bit ở đường viền bên phải hoặc bên trái và thêm 1 bit mới vào vị trí được giải phóng.

! Thuật toán CRC sử dụng chức năng Thanh ghi dịch trái.

_ Với Thanh ghi dịch trái, khi dịch chuyển, bit MSB sẽ “bật ra” khỏi Thanh ghi.
_ Bit ở vị trí MSB-1 bị di chuyển sang trái để lắp vào vị trí MSB, bit ở vị trí MSB-2 đến MSB-1 và cứ tương tự như thế …
_ Lúc này bit ở vị trí LSB bị bỏ trống. Nên bit tiếp theo của InputData được chuyển vào.

Left Shift Register

5. Cách tính toán CRC bằng máy tính

_ Đây là cách CRC được triển khai vào máy tính.

_ Theo cách tính trên, ta thấy Polynom đứng yên, còn InputData sẽ từ từ dịch chuyển SANG TRÁI sau mỗi phép tính XOR.

🤔 Có điều những vd trên, InputData chỉ có 1 Byte, vậy điều gì sẽ xảy ra nếu ta mở rộng thành một mảng InputData nhiều Byte tùy ý?
⇒ Với cách tính thủ công thì việc thực hiện đơn giản. Tuy nhiên áp dụng vào cho máy tính khá là khó khi phải xử lý các bit dịch chuyển giữa ranh giới các Byte data.

⇒ Nhưng nhờ đặc tính “Giao hoán” (Commutativity)“Kết hợp” (Associativity) của XOR.

Nguồn (en.wikipedia.org)

⇒ Ta có thể cho máy tính xử lý từng Byte một mà không cần xét Byte tiếp theo cho đến khi xử lý hoàn toàn xong Byte hiện tại.

6. Cải thiện thuật toán CRC (dựa trên Lookup Table)

_ Tuy ta có thể xử lý từng Byte một riêng lẻ trong InputData. Nhưng về cơ bản thuật toán vẫn phải xử lý từng bit trong một Byte, cho nên hiệu suất khá là kém. Nhất là khi InputData có một lượng lớn data. Điều này có thể làm chậm chương trình đi rất nhiều.

🤔 Vậy làm sao chúng ta có thể tăng tốc thuật toán CRC?
⇒ Như đã biết, ta có thể xét từng Byte của InputData (Số chia). Và 1 Byte thì chỉ có thể chứa 256 giá trị khác nhau.
⇒ Trong khi đó, Polynom (Số bị chia) có giá trị cố định, đã được xác định trước.

⇒ Tại sao không tính toán trước phép chia cho mỗi giá trị có thể có của 1 Byte với giá trị Polynom cố định. Và lưu trữ các kết quả này trong một “Bảng tra cứu” (Lookup Table)?
⇒ Điều này có thể thực hiện được vì kết quả Remainder luôn giống nhau cho cùng một số Divident và số Divisor.

! Như vậy, InputData có thể được xử lý từng Byte thay vì từng bit.

Lookup Table of Polynom (0x1D)

_ Nhờ vậy, tốc độ xử lý thuật toán CRC tăng lên đáng kể.
_ Tuy nhiên việc cải thiện tốc độ đi kèm với chi phí là cần Thời gian xử lý để tính toán trước Lookup Table và có Mức tiêu thụ bộ nhớ cao hơn cho 256 phần tử, với mỗi phần tử là (n-bit).

7. Các bản mở rộng CRC-n?

_ Hiện có kha khá nhiều biến thể khác nhau. Nhưng nhìn chung, các bản CRC có thể được phân loại theo “chiều rộng” của chúng.

CRC-8 CRC-16 CRC-32 CRC-64


!
CRC càng nhiều bit, xác suất xảy ra Lỗi càng ít hơn.

8. Các thông số để tính CRC?

_ Đương nhiên thông số quan trọng nhất của thuật toán CRC phải kể đến là giá trị Polynom.

_ Còn đây là 2 thông số ảnh hướng đến giá trị đầu vào của InputData:

    • Input Reflected: YES/NO.
      _ Nó cho phép ta. Có chọn đảo ngược chuỗi InputData, trước khi tính CRC ko?
      _ Nếu chọn YES, tức bit MSB ↔ LSB.
    • Initial Value: Giá trị được sử dụng để khởi tạo giá trị ban đầu cho Thanh ghi CRC. Nó có thể là bất kỳ giá trị nào.
      _ Sau đó được XOR với InputData trước khi bắt đầu tính CRC.
      _ Trong tất cả vd trên, nó luôn là Zero.

_ Cuối cùng là 2 thông số ảnh hưởng đến giá trị đầu ra của kết quả CRC:

    • Result Reflected: YES/NO.
      _ Nó cho phép ta. Có chọn đảo ngược chuỗi kết quả, sau khi tính CRC ko?
      _ Nếu chọn YES, tức bit MSB ↔ LSB.
    • Final Xor Value: sau khi tính ra CRC xong (thực hiện thêm “Result Reflected” nếu có). Nó sẽ XOR với giá trị này, rồi mới trả về kết quả cuối cùng.

Hết rồi ^^

Mình hy vọng bài viết này giúp các bạn dễ hiểu hơn về thuật toán CRC.

Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments

Most Popular

Tìm hiểu CRC

🤔 Có bạn nào thắc mắc là các thiết bị điện tử ngoài việc chúng có thể giao tiếp trao đổi thông tin với...

Tìm hiểu Giao thức I2C

Có bạn nào thắc mắc làm sao giữa các thiết bị điện tử chúng có thể giao tiếp trao đổi data qua lại lẫn...

Tìm hiểu cách sử dụng các cảm biến Nhiệt độ & Độ ẩm DHT

Chắc nhiều bạn sinh viên cũng quá quen mấy con này rồi nhỉ. Nói không sai, DHT có thể xem như cảm biến quốc...

Tìm hiểu về Nhiệt độ biểu kiến cũng như Cách ta cảm nhận nhiệt độ

Có bạn nào từng thắc mắc rằng, tại sao đôi khi nhiệt độ ngoài trời không cao lắm, nhưng ta lại thấy nóng nực...

Recent Comments

0
Would love your thoughts, please comment.x
()
x