如果我想發送一個d位數據包並添加另一個r位用於糾錯碼(d> r)
最多可以找到和糾正多少個錯誤?錯誤校正碼上限
錯誤校正碼上限
回答
你或許應該閱讀維基百科頁面上這樣的:
http://en.wikipedia.org/wiki/Error_detection_and_correction
這聽起來像你特別想要一個漢明碼:
http://en.wikipedia.org/wiki/Hamming_code#General_algorithm
使用方案,你可以看一下來自鏈接表的一些示例值。
你有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,但這很簡單。
- 1. 校正代碼
- 2. 錯誤校驗
- 3. 奇偶校驗錯誤上缺少「126」
- 4. 限制錯誤代碼
- 5. OpenCV上抖動校正的圖像校正
- 6. Range.deserializeSelection校驗和錯誤?
- 7. 錯誤執行校驗
- 8. java的郎校驗錯誤
- 9. 錯誤預校驗類oauth.signpost.commonshttp.CommonsHttpOAuthConsumer
- 10. FTP上傳權限錯誤
- 11. OCR號碼格式校正和轉換
- 12. jQuery的:鏈接事件 - 代碼校正
- 13. 柵格步行算法代碼校正
- 14. R:轉換試驗和錯誤校正自動化
- 15. 梯形校正錯誤 - 你不能更新人口的關係
- 16. SignalR/malloc錯誤 - 釋放對象的校驗和不正確?
- 17. 字段必須用型功能錯誤指定 - 梯形校正
- 18. Malloc錯誤不正確的校驗和爲釋放的對象
- 19. Malloc錯誤:釋放對象的校驗和不正確
- 20. Installshield的錯誤:「vstor40_x86.exe的校驗和不正確」
- 21. 紅眼校正
- 22. 響應的極限錯誤代碼
- 23. 限制校驗器的角
- 24. 錯誤的TCP校驗和計算Scapy
- 25. IO錯誤:CRC校驗失敗0xffca51ff = 0x3679ba0L
- 26. JAVA NullPointerException異常錯誤(學校項目)
- 27. C#串行rs232奇偶校驗錯誤
- 28. 的ARToolKit校準結果保存錯誤
- 29. C#Indexoutofrange Arrays學校項目錯誤
- 30. 軍刀EnhancedAirBookRS校驗段0003錯誤
爲什麼downvote?這是正確的答案。 – 2009-11-09 23:40:46