# 什麼是 CRC（Cyclic Redundancy Check）檢測？

[TOC]

歡迎你點入本篇文章，會促成我想做這篇的原因，主要是因為在上計概時，突然浮現很多靈感，跟一大堆的問題（~~教授，為什麼要講的這麼淺白呢？我想知道更多啊啊！~~），為了一次解決我所有的困惑，於是製作本篇文章。

若文章有任何疑點及錯誤的地方歡迎提出。

## CRC 是啥？能吃嗎？

CRC 的中文全名叫做循環冗餘校驗（Cyclic Redundancy Check, CRC），是一種廣泛應用於數位網路和儲存裝置中的錯誤偵測碼，用於檢測數據傳輸或儲存後可能出現的意外變化。

這種 CRC 校驗的方法是由 W. Wesley Peterson 這個人在 1961 年所發表的。

CRC 的核心概念是在發送端（Sender）根據要傳送的數據，按照特定規則產生一個固定位數的校驗碼（也稱為檢查和），將其附加在原始數據（Original Data）後面一起傳送。接收端（Receiver）收到數據後，使用相同的算法重新計算校驗碼，並與接收到的校驗碼進行比對。如果兩者一致，則該數據傳輸正確；若不一致，則表示這個數據在傳輸過程中發生了錯誤。

總之呢，CRC 就是拿來檢驗資料在傳輸過程中是否錯誤的一種工具。

## 來算 CRC！

首先要知道在 CRC 中二進位數字（不是原始數據，而是發送端與接收端約定好要檢驗的數據）可對應每一位多項式的係數，如：

- $(1101)_2 = x^3 + x^2 + 0 \times x^1 + 1 \times x^0 = x^3 + x^2 + 1$
- $(10111)_2 = x^4 + 0 \times x^3 + x^2 + x^1 + 1 \times x^0 = x^4 + x^2 + x + 1$

這邊生成出來的多項式，看到它的領導係數（最高次方），就以這個數字在原始數據補 k 個 0，假設 k 是最高次方。

接下來 CRC 是使用 Modulo-2 運算（模 2 運算），他的加法減法都是一樣的，都是做兩組位元去做 XOR 運算。

XOR 運算規則如下：

- $0 \oplus 0 = 0$
- $0 \oplus 1 = 1$
- $1 \oplus 0 = 1$
- $1 \oplus 1 = 0$

如果兩位元相等就輸出 0，否則為 1。

這個運算會用在多項式長除法，將數據多項式除以一個固定的生成多項式（就是最上面雙方約定好的數據生成出來的多項式），最後所得的餘數就是 CRC 校驗碼。

這個 CRC 檢測最後可以用一個數學式表示： $M(x) \cdot x^n = Q(x) \cdot K(x) - R(x)$

以下是上面這些多項式所代表的意思：

- M(x) : 原始資訊多項式
- K(x) : 最高 n 次的生成多項式（除數）
- $M(x) \cdot x^n$ : 原始資訊後面補 n 個 0。
- Q(x) : 商（實際計算不會用到這個商的值）
- R(x) : 餘數多項式，即為 CRC 檢驗碼。

### 範例

假設有個 8 位元的原始數據 `10101010`，除數為 `10111`，求得 CRC 校驗碼。

首先將 `10111` 生成出多項式： $x^4 + x^2 + x + 1$ ，取出最高次方 4 次，在原始數據後方補上 4 個 0，變成 `101010100000`。

然後將 `101010100000` 除以 `10111` 以長除法形式進行（每次上下兩位元都是做 XOR 運算），如下圖：


做完之後會得到餘數，那個就是題目要求的 CRC 校驗碼了。

而題目如果是要求完整的訊息，也就是所謂的 codeword 的時候，那就要將原始數據加上 CRC 校驗碼，如 `10101010` + `1100` = `101010101100`。

如果對方收到後，將 `101010101100` 用一樣的除數 `10111` 去除，得到的餘數是 0 的話，那就表示這組數據是沒有問題的，否則有誤。

## CRC 演算流程（整理）

1. 選定多項式（如果在考試的話應該會給你除數，你要自己生成）
2. 原始數據補 0（挑生成多項式的最高次方）
3. 做 Modulo-2 長除法（每次都做 XOR 運算）
4. 取得 CRC 校驗碼（就是長除法的餘數）
5. 附加並傳送（若題目有要求 codeword，則將 CRC 校驗碼加到原始數據最後面）

## CRC 常見的標準多項式

CRC-16： $x^{16} + x^{15} + x^2 + 1$ （`0x8005`）

CRC-32： $x^{32} + x^{26} + x^{22} + x^{16} + x^{12} + x^{11} + x^{10} + x^8 + x^7 + x^5 + x^4 + x^2 + x + 1$ （`0x04C11DB7`）

CRC-CCITT：`0x1021` 用於電信業。

## 參考資料

[循環冗餘校驗 - 維基百科，自由的百科全書](https://zh.wikipedia.org/zh-tw/%E5%BE%AA%E7%92%B0%E5%86%97%E9%A4%98%E6%A0%A1%E9%A9%97)

[什麼是 CRC（Cyclic Redundancy Check）？ | Pure Storage](https://www.purestorage.com/tw/knowledge/cyclic-redundancy-check.html)

[什么是循环冗余校验 (CRC) 及其工作原理？ | 台灣 聯想](https://www.lenovo.com/tw/zh/glossary/cyclic-redundancy-check/?orgRef=https%253A%252F%252Fwww.perplexity.ai%252F)

[C 嵌入式系统设计模式 26：循环冗余校验模式_循环冗余校验32位-CSDN博客](https://blog.csdn.net/zhzht19861011/article/details/136642956)

[什么是CRC（Cyclic Redundancy Check）？如何解决CRC错误？ - 华为](https://info.support.huawei.com/info-finder/encyclopedia/zh/CRC.html)