是否可以用CRC做基本的糾錯？

Question

我知道使用CRC的全部目的是做錯誤檢測，但是我聽到有人說它除了錯誤檢測之外還可以用來做基本的錯誤糾正。我很好奇，如果是這樣，如果是這樣，它有多強大？我的意思是，我們通常將CRC稱爲能夠執行x位檢測，但我很好奇它是否能夠執行x位校正。如果是這樣，這是如何工作的？謝謝。

Answer 1

有可能用CRC進行單比特糾錯。假設一個具有CRC「登記」，並具有以下功能：以運行CRC算法向前和向後一點的時間，忽略傳入的數據

 
int crc_forward(int old_value, int data_bit) 
{ 
    if (old_value & 0x8000) 
    return ((old_value^0x8000) SHL 1)^0x1021^data_bit; 
    else 
    return (old_value SHL 1)^data_bit; 
} 

int crc_reverse(int old_value) 
{ 
    if (old_value & 1) 
    return (old_value SHR 1)^0x8810; 
    else 
    return old_value SHR 1; 
} 

假設一個具有被計算，使得初始化CRC一些分組值併爲每個位（MSB優先）運行crc_forward應爲零。如果得到的CRC值不是零，則可以反向運行算法（忽略數據位），直到計算出的CRC值爲1.這就是不正確位的位置。

請注意，這種方法可能適用於NAND閃存等軟件糾錯。爲了有用地將其用於硬件糾錯，必須能夠延遲讀取操作直到ECC可以被處理，否則將需要「綜合症」值和位位置的表。

Answer 2

我最近致力於CRC16錯誤檢測和單比特糾錯。

這裏的基本思想是：

1. 假設你有一個單比特錯誤。
2. 如果data + crc不包含錯誤，則CRC將爲0，否則不會。
3. 我們定義CRC作爲CRCr發送的CRC和CRC。
4. 然後錯誤位由CRCox = CRCs^CRCr給出。
5. 結果包含CRC錯誤和數據錯誤。
6. 看看CRCox和誤碼之間有什麼關係。

這是否清楚？我有一篇關於這個的文章。如果你想知道更多，請讓我知道。

Answer 3

您可以使用CRC執行多位錯誤更正。看看維基百科，參考koopmans的工作，CRC可以檢測到它的hamming_distance-1錯誤。漢明距離取決於有效載荷長度和正在使用的CRC多項式。因此，例如Koopmans多項式0xBA0DC66B可以檢測長達16360比特長度的消息中的高達5比特的錯誤。前兩個消息中描述的算法可以根據需要擴展到儘可能多的位，但時間隨着要修復的位數呈指數增長。

1. 計算錯誤CRC = CRC_gotten^CRC_expected。
2. 查看所有可能的1位消息（即全0，1和全0）（有message_length個案來評估。注意這是BITS而不是BYTES），錯誤位是生成錯誤CRC的消息。
3. 反轉檢測到的位以糾正錯誤。

如果找不到與CRC錯誤相匹配的1位，請查看所有2位，3位到hamming_distance-1。請注意，這變得很慢，message_length平方爲2位，立方體爲3位，五位爲5位。