錯誤校正碼上限

Question

如果我想發送一個d位數據包並添加另一個r位用於糾錯碼（d> r）
最多可以找到和糾正多少個錯誤？

Answer 1

你或許應該閱讀維基百科頁面上這樣的：

http://en.wikipedia.org/wiki/Error_detection_and_correction

這聽起來像你特別想要一個漢明碼：

http://en.wikipedia.org/wiki/Hamming_code#General_algorithm

使用方案，你可以看一下來自鏈接表的一些示例值。

Answer 2

你有2^d個不同種類的你想發送的長度爲d位的數據包。把你的r位加到它們中，使它們成爲長度爲d + r的碼字，所以現在你有2^d個可能的碼字可以發送。接收器可以得到2 ^（d + r）個不同的接收字（可能有錯誤的碼字）。那麼問題就變成了，你如何將2 ^（d + r）個接收到的字映射到2^d個碼字？

這歸結於代碼的minimum distance。也就是說，對於每對碼字，找出它們不同的位數，然後取這些值中的最小值。

假設您的最小距離爲3.您收到一個單詞，並且您注意到它不是代碼字之一。也就是說，有一個錯誤。所以，對於缺乏更好的解碼算法，你翻轉第一位，看看它是否是一個碼字。如果不是，則將其翻轉並翻轉下一個。最終，你會得到一個代碼字。由於所有碼字在3個位置上都不相同，因此您知道該碼字與接收到的字「最接近」，因爲您必須翻轉接收字中的2個位才能到達另一個碼字。如果你一次沒有得到一個代碼字翻轉一個位，你不能找出錯誤的位置，因爲你可以通過翻轉兩位來獲得多個代碼字，但是你知道至少有兩個代碼字錯誤。

這導致了一般原則，即對於最小距離md，您可以檢測md-1錯誤並糾正floor（（md-1）/ 2）錯誤。計算最小距離取決於您如何生成代碼字的細節，也稱爲代碼。根據d和（d + r），可以使用各種界限來確定md的上限。

保羅提到了漢明碼，這是一個很好的例子。它達到Hamming bound。對於（7,4）漢明碼，你有4位信息和7位碼字，並且你的最小距離爲3。顯然*，你永遠不會得到大於你正在添加的位數的最小距離所以這是你能做的最好的事情。不要太習慣於這個。漢明碼是非重要的少數例子之一perfect code，其中大多數的最小距離小於您添加的位數。

*這不是很明顯，但我非常確定這是非常重要的糾錯碼。添加一個奇偶校驗位可使您獲得至少兩個距離，從而可以檢測到錯誤。由{000111}組成的代碼通過添加2位來獲得最小距離爲3，但這很簡單。