[CRC] Bài 1 - Lý Thuyết Về CRC Và Mạch Tính CRC Nối Tiếp

Trang chủ » Bảng Mã Hóa Crc » [CRC] Bài 1 - Lý Thuyết Về CRC Và Mạch Tính CRC Nối Tiếp

Có thể bạn quan tâm

VLSI TECHNOLOGY
  • Home
  • Background
    • Basic Knowledge
    • Verilog & SV
    • SystemC
    • Perl
    • CAN
  • VLSI
    • Sync Design
    • Multi-Clock Design
    • Async Design
    • STA
    • DFT
  • IP cores
  • Tool
    • Open Source
    • Simulation
  • Q&A
  • Jobs
  • Project
  • Training
  • About

Thứ Hai, 9 tháng 10, 2017

[CRC] Bài 1 - Lý thuyết về CRC và mạch tính CRC nối tiếp

Tác giả Nguyễn Quân at 08:27 background, CRC, IP core, Kiến Thức Cơ Bản, Synchronous Design, System Verilog, Verilog 2 bình luận Nội dung bài viết này trình bày về lý thuyết tạo và và kiểm tra CRC. Phương pháp thực hiện mạch tính CRC nối tiếp. Đồng thời, bài viết đưa ra một RTL code tính CRC có thể lựa chọn độ dài đa thức sinh (generator polynomial) trước khi tổng hợp và gán giá trị đa thức sinh mong muốn khi sử dụng. 1. Tổng quan Việc truyền một dữ liệu trong một môi trường từ điểm này đến điểm khác, ví dụ như truyền dữ liệu giữa hay máy tính trong một mạng, luôn tiềm ẩn nhiều yếu tố làm dữ liệu truyền bị sai. Cơ chế phát hiện lỗi dữ liệu là không thể thiếu đối với các giao thức có độ tin cậy cao. Phương pháp chung để kiểm tra lỗi dữ liệu là thêm các bit kiểm tra kèm theo dữ liệu được truyền theo một quy tắc đã được quy định trước. Bộ truyền dữ liệu sẽ tạo ra các bit kiểm tra từ giá trị dữ liệu cần truyền và gắn nó với dữ liệu truyền. Bộ nhận sẽ nhận dữ liệu và tính toán lại các bit kiểm tra để so sánh với các bit kiểm tra mà nó nhận được. Nếu hai kết quả khác nhau thì đây là một lỗi. Một phương pháp kiểm tra đơn giản đó chính là sử dụng parity bit. Parity bit là phương pháp sử dụng 1 bit để kiểm tra số bit "1" hoặc "0" của chuỗi dữ liệu là "chẵn" hoặc "lẻ". Ví dụ sau đây minh họa việc kiểm tra parity chẵn, tổng số bit 1 trong chuỗi được truyền đi bao gồm cả dữ liệu và bit kiểm tra luôn là một số chẵn.
  • Tạo bit parity: XOR tất cả các bit dữ liệu
  • Kiểm tra parity: XOR tất cả các bit dữ liệu và bit parity. Nếu giá trị là 1 thì chuỗi dữ liệu nhận bị sai.
Một số điểm cần lưu ý:
  • Bit sai có thể là bit dữ liệu hoặc bit parity
  • Chỉ phát hiện được nếu số bit sai là số lẻ (sai 1, 3, 5, 7, ... bit)
Hình 1. Tạo và kiểm tra Parity chẵn cho chuỗi dữ liệu 8 bit
Phương pháp kiểm tra parity đơn giản nhưng độ tin cậy kém nên được ứng dụng cho các giao thức có tốc độ truyền dữ liệu chậm hoặc số lượng bit dữ liệu cần kiểm tra ít ví dụ như giao thức UART. CRC (Cyclic Redundancy Code) là một phương pháp phổ biến có độ tin cậy cao hơn nhiều so với sử dụng bi parity. CRC được ứng dụng trong nhiều giao thức có khối lượng dữ liệu truyền lớn hoặc tốc độ truyền dữ liệu cao như CAN, Ethernet, giao tiếp RF 15693, ... 2. Lý thuyết về tính toán CRC Giá trị chuỗi bit kiểm tra hay chuỗi CRC là số dư của phép chia của chuỗi bit dữ liệu cho một chuỗi bit đa thức sinh (Generator Polynomial). Đa thức sinh là số chia sẽ khác nhau tùy vào mỗi giao thức quy định. Phép chia trong tính toán CRC sử dụng cách tính modulo-2. Modulo-2 thực chất là XOR hai số hạng. Giả sử đa thức chuỗi dữ liệu cần truyền là M(x): Đa thức sinh là G(x): Trong đó:
  • am và an bằng 1 hoặc 0
  • Độ dài chuỗi CRC bằng độ dài đa thức sinh trừ 1 và bằng số mũ lớn nhất của đa thức sinh và bằng n.
Để tạo CRC, chuỗi dữ liệu cần truyền sẽ được mở rộng thêm n bit về phía bên phải: Điều này, tương ứng với việc dịch trái n bit chuỗi dữ liệu M(x). Cuối cùng, chia T(x) cho G(x) và lấy số dư. Số dư chính là chuỗi CRC n bit. Kiểm tra CRC được thực hiện bằng 1 trong 2 cách sau:
  • Lấy chuỗi dữ liệu có cả các bit kiểm tra CRC chia cho đa thức sinh. Nếu số dư khác "0" thì dữ liệu nhận bị lỗi.
  • Tách chuỗi dữ liệu và chuỗi CRC riêng. Chỉ lấy chuỗi dữ liệu chia cho đa thức sinh rồi lấy số dư phép chia so sánh với chuỗi CRC. Nếu hai chuỗi khác nhau thì dữ liệu nhận bị lỗi.
Ví dụ về tính toán CRC-4, tương ứng với số bit kiểm tra là 4 bit, với đa thức sinh như sau: x^4 + x + 1 (b10011) Chuỗi dữ liệu cần truyền có 8 bit như sau: x^7 + x^5 + x (b1010_0010) Chuỗi dữ liệu trước khi chia sẽ được mở rộng thêm 4 bit "0": x^11 + x^9 + x^5 (b1010_0010_0000)
Hình 2. Tính chuỗi CRC
Việc kiểm tra CRC được thực hiện trên chuỗi dữ liệu có đính kèm CRC như sau:
Hình 3. Kiểm tra CRC - trường hợp nhận đúng, số dư bằng 0
Hình 4. Kiểm tra CRC bằng cách chia chuỗi dữ liệu có CRC với đa thức sinh - trường hợp sai 1 bit và trường hợp sai 2 bit, số dư khác 0
Bộ nhận sẽ không phát hiện được lỗi dữ liệu khi chuỗi dữ liệu bị sai và chuỗi CRC cũng sai trùng với giá trị CRC của chuỗi dữ liệu bị sai. Tuy nhiên, xác suất để xảy ra đúng trường hợp này là thấp. Xác suất này càng thấp khi chuỗi CRC càng dài.
Hình 6. Kiểm tra CRC không phát hiện được lỗi khi cả dữ liệu và CRC cùng sai đồng thời
Xét đa thức sinh g(x) = x + 1, đây là đa thức CRC-1, tính CRC cho chuỗi 8 bit b10100010 và chuỗi b10011111.
Hình 7. Tính CRC-1
So sánh kết quả với phương pháp tính parity chẵn đã trình bày phía trên chúng ta có thể nhận thấy sự tương đồng. CRC-1 chính là phương pháp kiểm tra parity. 3. Mạch nguyên lý tính CRC Xem lại các ví dụ đã trình bày trên đây, CRC được tính theo nguyên tắc:
  • Nếu bit MSB của lần tính hiện tại bằng 1 thì nó sẽ được XOR (modulo-2) với đa thức sinh
  • Nếu bit MSB của lần tính hiện tại bằng 0 thì nó sẽ không đổi
Hình 8. Vị trí có MSB = 1 được XOR với đa thức sinh
Để thực hiện mạch CRC-1, ngoài cách XOR tất cả các bit dữ liệu đầu vào như đã trình bày ở phần trên, chúng ta có thể thực hiện dựa trên nguyên lý của việc chia đa thức như hình trên. Mạch cần 2 FF để lưu giá trị sau mỗi lần XOR và mạch sẽ dịch 1 bit sau mỗi lần XOR để lấy 1 bit dữ liệu mới như hình sau:
Hình 9. Mạch nguyên lý của CRC-1
Ở hình trên, bit MSB sẽ điều khiển MUX chọn có XOR với đa thức sinh x+1 hay không? Tuy nhiên, sau mỗi chu kỳ tính, bit MSB luôn bị loại bỏ nên mạch MUX và XOR của bit MSB là không cần thiết. Mạch được rút gọn như hình sau:
Hình 10. Mạch nguyên lý CRC-1 (bỏ mạch tính ở bit MSB)
Xét mạch MUX, nếu bit MSB bằng 1 thì bit 0 XOR với 1, nếu bit MSB bằng 0 thì tương ứng với việc bit 0 XOR với 0 nên mạch MUX được loại bỏ để thay bằng bit 1 XOR bit 0.
Hình 11. Mạch nguyên lý CRC-1 (bỏ mạch MUX)
Bit 0 chỉ dùng để lưu giá trị bit dịch vào nên cũng có thể loại bỏ.
Hình 12. Mạch nguyên lý CRC-1 (bỏ FF đầu vào)
Ở đây, bit CRC chỉ có 1 bit nên việc thêm 1 bit 0 ở chuỗi dữ liệu đầu vào để tính CRC cũng không cần thiết vì giá trị nào XOR với 0 cũng bằng chính nó.
Hình 12. Mạch nguyên lý CRC-1
Biểu diễn thường thấy cho mạch tính CRC như sau:
Hình 13. Mạch nguyên lý CRC-1 với biểu diễn thông thường
Tương tự, xét lại mạch CRC-4 có đa thức sinh x^4 + x + 1, mạch nguyên lý tính CRC-4 như sau (lưu ý, vị trí XOR với "0" thì loại bỏ cả MUX và cổng XOR):
Hình 14. Mạch nguyên lý tính CRC-4
5. RTL code tính CRC nối tiếp 5.1 Nhận xét Qua hai ví dụ trên đây, nhận xét chung như sau:
  • Tại vị trí mà bit đa thức sinh bằng "0" thì chỉ là phép dịch bit
  • Tại vị trí mà bit đa thức sinh bằng "1" thì được chèn cổng XOR
  • Dữ liệu nối tiếp để tính CRC dịch từ MSB đến LSB với số lần dịch bằng độ dài dữ liệu cộng độ dài giá trị CRC. Ví dụ, dữ liệu 8 bit dùng CRC-4 thì số lần dịch là 12 lần với 4 bit cuối là 4 bit 0 được thêm vào chuỗi dữ liệu.
5.2 Phân tích module tạo và kiểm tra CRC Căn cứ vào những nhận xét trên, một thiết kế thực hiện tính CRC tổng quát được thực hiện như sau:
  1. Sử dụng một define CRC_CTRL_POLY để cho phép tạo tín hiệu input điều khiển giá trị của đa thức sinh nếu muốn. Chú ý, độ rộng tín hiệu điều khiển bằng số bit CRC vằ bằng số mũ lớn nhất của đa thức sinh. Ví dụ, nếu đa thức sinh là x^4 + x + 1 thì độ rộng tín hiệu là 4 bit và giá trị gán cho tín hiệu điều khiển là 4'b0011 (bỏ bit 1 của x^4)
  2. Sử dụng một define CRC_CHECKER để cho phép tạo chức năng kiểm tra CRC
  3. Sử dụng một parameter CRC_GPW_MAX cho phép cấu hình độ rộng đa thức sinh. Độ rộng đa thức sinh bằng số mũ lớn nhất của đa thức sinh. Ví dụ, nếu đa thức sinh là x^4 + x + 1 thì CRC_GPW_MAX = 4
  4. Sử dụng một parameter CRC_POLY_VALUE cho phép gán giá trị đa thức sinh sẽ sử dụng nếu không sử dụng tín hiệu điều khiển được tạo ra bởi định nghĩa CRC_CTRL_POLY. Ví dụ, nếu không định nghĩa CRC_CTRL_POLY, đa thức sinh là x^4 + x + 1 thì CRC_GPW_MAX = 4 và giá trị CRC_POLY_VALUE = 4'b0011
Sơ đồ tín hiệu giao tiếp của module CRC như sau:
Hình 15. Sơ đồ tín hiệu của module tính CRC
Hai tín hiệu ctrl_en và chk_en sẽ điều khiển chức năng tạo và kiểm tra CRC như sau, khi tín hiệu ctrl_en tích cực, dữ liệu dùng để tạo CRC hoặc được kiểm tra CRC sẽ bắt đầu dịch vào data_in. ctrl_en sẽ tích cực bằng số bit cần dịch trên data_in.
  • Nếu chk_en = 0 thì khi ctrl_en = 0, crc_seq sẽ giữ giá trị chuỗi CRC trong 1 chu kỳ xung clock
  • Nếu chk_en = 1 thì khi ctrl_en = 0, crc_error sẽ báo lỗi CRC
    • crc_error = 1 thì chuỗi kiểm tra bị lỗi CRC
    • crc_error = 0 thì chuỗi kiểm tra không bị lỗi
Mạch tổng quát của từng bit trong thanh ghi chứa giá trị CRC như sau:
Hình 16. Mạch tổng quát tính giá trị bit CRC thứ i
Riêng bit 0 có đầu vào là data_in có mạch như sau:
Hình 17. Mạch tổng quát tính giá trị bit CRC 0
Khi có định nghĩa CRC_CHECKER, mạch kiểm tra lỗi CRC sẽ được tạo ra như sau:
Hình 18. Mạch kiểm tra lỗi CRC
5.3 RTL code Link download RTL code và testbench: CRC RTL code pass (nếu có): nguyenquanicd 5.4 Kết quả mô phỏng
Hình 19. Mô phỏng tạo và kiểm tra CRC
Đa thức sinh: x^4 + x + 1 tương ứng với việc gán ctrl_poly_en = 4'b0011 Dữ liệu dùng để tạo CRC: 1010_0110 sau khi thêm 4 bit "0" là 1010_0110_0000 => Kết quả tính CRC là 1110 Dữ liệu dùng để kiểm tra CRC: 1010_0110_1110. Trong đó, 4 bit LSB 1110 là chuỗi CRC => Kết quả kiểm tra CRC là crc_error = 0 Lưu ý, đa thức sinh có nhiều cách biểu diễn khác nhau. Trong bài viết này chỉ dùng cách biểu diễn thông thường (normal representation) từ MSB đến LSB. Lịch sử cập nhật: 1) 2019.08.26 - Thêm lưu ý về cách biểu diễn đa thức sinh ← Bài đăng Mới hơn Bài đăng Cũ hơn → Trang chủ

2 bình luận:

  1. Phat Nguyenlúc 06:42:00 PST Thứ Năm, 3 tháng 1, 2019

    Thanks :D

    Trả lờiXóaTrả lời
      Trả lời
  2. Hai Volúc 01:41:00 PDT Thứ Năm, 23 tháng 5, 2019

    Cảm ơn tác giả

    Trả lờiXóaTrả lời
      Trả lời
Thêm nhận xétTải thêm...

Bài mới

[Low Power] Các kỹ thuật thiết kế giúp giảm công suất tiêu thụ

Bài viết này trình bày khái niệm cơ bản về công suất thấp và các kỹ thuật giúp giảm công suất tiêu thụ trong thiết kế số. Trong đó, nội dun...

Bài xem nhiều

  • [DES] Thuật toán mã hóa và giải mã DES Bài viết này giới thiệu về thuật toán mã hóa và giải mã dữ liệu DES (Data Encryption Standard). Đây là thuật toán mã hóa dữ liệu được công ...
  • [CRC] Bài 1 - Lý thuyết về CRC và mạch tính CRC nối tiếp Nội dung bài viết này trình bày về lý thuyết tạo và và kiểm tra CRC. Phương pháp thực hiện mạch tính CRC nối tiếp. Đồng thời, bài viết đưa ...
  • [Q&A] Muốn làm về lĩnh vực thiết kế vi mạch số cần học những gì? Các job của ngành này ở Việt Nam? Bài viết này dành cho các bạn sinh viên chuyên ngành điện tử, khoa học máy tính, hệ thống nhúng hoặc viễn thông mong muốn hiểu cơ bản về ng...
  • [Verilog][System Verilog] Máy trạng thái hữu hạn FSM Bài viết này phân tích cấu trúc của máy trạng thái hữu hạn FSM (Finite State Machine), cách mô tả RTL code của FSM và các vấn đề liên quan ...
  • [AES] Bài 1 - Lý thuyết về mã hóa AES-128 Trước đây, tác giả có tham gia một diễn đàn và đăng về thiết kế mã hóa và giải mã AES. Chuỗi bài này đăng lại ở blog với mục tiêu tập hợp l...
facebook tweeter linked in you tube Github EDAPlayground

YouTube

Dịch-Translate

Theo dõi

Liên hệ

Tên Email * Thông báo *

Các chủ đề

AES (7) Arbiter (5) Asynchronous Design (6) AXI (4) BUS (4) CAN (17) CAN2.0 (12) CANFD (6) CDC (4) Clock gating (1) Controller Area Network (18) counter (1) Coverage (1) cpu (5) CRC (5) cryptography (2) DES (2) Design Techniques (1) DFT (2) FIFO (2) High Level Design (11) ieee1149 (6) Interview Question (1) IP core (13) job (3) JTAG (6) layouttool (1) LIFO (1) Low Power (1) Multi-clock Design (4) opentool (1) perl (8) Power gating (1) Project1 (11) Project2 (8) Project3 (2) Protocol (17) Q&A (5) Questa Sim (4) race condition (1) Round Robin (3) script (7) simtool (5) simulation (17) STA (6) SVforSynthesis (2) Synchronous Design (27) System Verilog (41) SystemC (13) systool (2) tap (1) TLM (4) tool (4) Transaction Level Modeling (4) UVM (9) verification (15) Verilog (43)  

  • Thống Kê

  • Giới Thiệu

  • Python For RTL Designer

  • VLSI003 - Logic Design

Copyright © VLSI TECHNOLOGY | Powered by Blogger Wordpress Theme by ThemePix.com | Blogger Theme by Lasantha - PremiumBloggerTemplates.comNewBloggerThemes.com

Từ khóa » Bảng Mã Hóa Crc