循環冗餘檢查（cyclic redundancy check）

假設你想要一段訊息的指紋，好到幾乎對訊息做任何改動都會產生不同的指紋。CRC 就是訊框的這種指紋。發送方對整個訊框算出一個短短的檢查值並附在後面；接收方重新計算，若和收到的不一樣，就判定這個訊框已損壞。CRC 是連結層的主力錯誤偵測器——乙太網路、Wi-Fi 與大多數現代連結，都在訊框結尾帶著一個。

它的機制是長除法，但有個轉折：除法是在二進位的模 2 算術裡做的，其中加法與減法就只是 XOR、沒有進位。發送方與接收方約定好一個固定的除數，叫做產生多項式（generator），是一串由標準選定的 r+1 個位元。發送方在資料後面補上 r 個 0，用以 XOR 為基礎的長除法去除以這個產生多項式，得到的 r 位元餘數就是 CRC。它送出資料加上這個餘數。接收方把整串收到的東西——資料加 CRC——用同一個產生多項式去除；餘數為零代表沒有可偵測到的錯誤，餘數非零則代表訊框損壞、予以丟棄。巧妙之處在於，慎選的產生多項式能保證偵測出一整類一整類的錯誤。

這正是 CRC 賺到名聲的地方。一個好的 r 位元 CRC 能抓到每一個單一位元錯誤、每一個雙位元錯誤、任何奇數個錯誤，以及每一個短於 r+1 位元的叢發錯誤（burst error）——而叢發錯誤恰恰是雜訊連結最常製造的東西。用 32 位元的 CRC，一次隨機損壞溜過去的機率小到微不足道。不過，誠實的提醒和任何檢查碼一樣：CRC 只偵測意外的損壞。它「不是」密碼學雜湊，對蓄意竄改毫無防護，因為一個編輯了訊框的攻擊者，可以重算出相符的 CRC。