網絡糾錯

Question

我需要模擬器模擬發送4位數據字，然後將其轉換爲代碼字，然後在整個過程中發生噪音和錯誤的可能性。 模擬器需要糾正至少3個錯誤。

問題是我一直在閱讀幾個小時左右的錯誤檢測和糾正，它只會談論最多糾正1位錯誤！

對於多於1位的糾錯，線性漢明距離表不能很好地工作（在性能方面）。

有沒有辦法做到這一點？我只需要一個指南 謝謝！

Answer 1

我認爲你正在尋找前向糾錯;預先計算一些「奇偶校驗」數據，將其附加到原始數據中，然後在接收時重新生成原始數據（檢測/糾正錯誤）並丟棄奇偶校驗。

如果您使用的是C/C++，Javascript或Python，則可以使用https://github.com/pjkundert/ezpwd-reed-solomon。該庫（可在GPLv3，LGPL和Commercial許可下使用）提供了Reed-Solomon FEC編碼和解碼的簡單，非常快速的實現。

它支持2到16位的「符號」（數據元素）大小。最大的「碼字」（數據+奇偶校驗）大小取決於該字中的位數。例如，對於4位符號，最大碼字大小爲15個符號。因此，每個數據塊可以是1到14個符號，其中由Reed-Solomon編碼器產生的其餘奇偶校驗符號（總數爲15）產生R-S「碼字」。之後，當接收符號時，裏德 - 所羅門解碼器驗證和/或校正「碼字」，並丟棄奇偶符號。在C++中，您需要將二進制數據解壓縮爲4位符號（可能只是一個數組或unsigned char的std :: vector，其中每個char都保存從0到15的值）。

然後，決定要糾正多少錯誤。每個錯誤符號需要2個Reed-Solomon奇偶校驗符號，所以要糾正3個錯誤，您需要6個奇偶校驗符號。您會使用您的預期錯誤率來確定您可以組合在一起的符號的最大數量，然後再期望看到3個錯誤的符號。

假設您的最大預期誤差率爲15％。所以，你可以在預期3個壞符號之前收集20個符號。由於6個奇偶校驗符號也可能是錯誤的，因此它們包含在20中。因此，理想情況下，您希望採用14個數據符號，然後在碼字中爲總共20個符號添加6個奇偶校驗符號。

問題是，對於4位符號，您的最大R-S碼字大小爲15。對於N位符號，R-S編解碼器總是具有2^N-1的最大碼字尺寸。因此，對於4位符號，2^4-1是15 - 因此，RS（15，...）編解碼器就是您將要使用的編解碼器。第二個數字是有效載荷大小 - 非奇偶校驗符號的數量。因此，對於6個奇偶校驗 - RS（15,9）。因此，使用RS（15,9）編解碼器，您將獲得比您需要的更多的錯誤分辨能力，能夠在每15個符號中解決3個錯誤。

因此，將您的數據剪切成9個符號的塊。創建一個ezpwd :: rs :: RS < 15,9>實例，並使用其編碼方法添加6個奇偶校驗符號。在你的模擬中發送出去。

後您的模擬器增加了一些錯誤，接收15個符號的塊，並通過您的RS < 15,9>編解碼器的解碼方法運行的每個塊。它會返回糾正的錯誤符號的數量 - 或者拋出異常，如果錯誤負載超過Reed-Solomon編碼的容量。

玩得開心！