糾錯碼

Question

我需要在短消息（100到200位之間）上使用糾錯技術。可用於添加冗餘位的空間受限於20-50％。我將不得不在C/C++中實現編碼和解碼。所以它需要開源或者編程足夠簡單。 （我在過去有一些解碼算法的經驗 - 他們是可怕的！）

任何人都可以建議一個合適的錯誤代碼使用（與相關參數）？

Answer 1

看看裏德所羅門糾錯。

C++中的示例實現可用here。

對於不同的選項看起來here - 見第11項

編輯：如果你想有一個商業庫 - http://www.schifra.com/faq.html

Answer 2

的Reed-Solomon編碼器的形式RS（能力，有效載荷）進行說明。容量始終爲2^SYMBOL-1，其中SYMBOL是每個Reed-Solomon符號中的位數。通常，這個SYMBOL大小是8位（一個正常字節）。它通常可以是3到16位的任何值。對於8位符號，Reed-Solomon編碼器將被命名爲RS（255，PAYLOAD）。

PAYLOAD是非奇偶校驗符號的數量。如果你想要4個奇偶校驗符號，你可以指定RS（255,251）。

爲了有效地糾正數據塊中的錯誤，必須首先將數據打包爲符號（比特組，通常只有8比特字節）。你的目標是嘗試安排（如果可能的話）任何錯誤聚集成儘可能少的符號。例如，如果平均每8位發生一次錯誤，則8位符號將不合適;例如，如果平均每8位發生一次錯誤，那麼8位符號將不合適。幾乎每個符號都會有錯誤！您可能會使用4位符號並使用RS（15,11）編解碼器 - 一次最多可使用11個4位符號，每個塊產生4個奇偶校驗符號。符號大小越小，容量越低（例如SYMBOL大小爲4位，2^4-1 == 15符號CAPACITY）。

但通常情況下，您會使用8位符號。如果你有一個比較現實的錯誤率，例如你的8位符號的10％是錯誤的，那麼你可以使用一個RS（255,205） - 每255個符號Reed-Solomon「碼字」的50個奇偶校驗符號， 205字節的PAYLOAD。這給了我們〜25％的平價，使我們能夠糾正包含高達〜12.5％錯誤的碼字。

使用https://github.com/pjkundert/ezpwd-reed-solomon的C++/ezpwd/RS裏德 - 所羅門API，你會爲指定此：

#include <ezpwd/rs> 
... 
ezpwd::RS<255,205> rscodec; 

放入一個std :: string的數據（它可以處理原始8位二進制數據就好）或一個std ::向量並調用API，將奇偶校驗的50個符號：

std::string data; 
// ... fill data with a fixed size block, up to 205 bytes 
rscodec.encode(data); 

發送的數據，後來，你接收到的數據加上奇偶校驗位後，恢復原始數據（和丟棄50個奇偶符號）：

int corrected = rscodec.decode(data); 

如果可以恢復數據，則會返回糾正的符號數，如果Reed-Solomon碼字包含太多錯誤，則返回-1。

享受！