用於QR碼生成器的Reed-Solomon算法

Question

在我的數據結構類中，我想爲我的最終項目創建一個QR碼生成器。不過，我在理解「格式化錯誤修正」部分時遇到了一些麻煩。我想使用11（L）的錯誤校正和100（每隔一行）的掩蔽模式。由於我是一名本科生，因此我想嘗試使用版本1 QR代碼並使用字節編碼來保持它非常簡單。

然後我不明白如何在數據輸出後提出錯誤更正框。

Answer 1

查看一些規範，糾錯等級L（低，可以糾正7％）被識別爲兩位模式01，而不是11.連接到QR碼格式字符串，其中包括掩碼和糾錯等級。

http://www.thonky.com/qr-code-tutorial/format-version-information

由於你選擇了一個特定的糾錯水平和掩模圖案，這是與在thonky.com網頁所使用的，格式字符串將是固定的比特15位模式： 「糾錯級別爲L並且掩碼圖案4的代碼的最終格式字符串爲110011000101111」，因此您不必費心計算它。

對於QR碼，8比特域GF（2^8）是基於一個9位多項式

x^8 + x^4 + x^3 + x^2 + 1 = hex 11d 
    the primitive α = x + 0 = hex 2 

注意，這兩個加法和減法爲二進制字段是相同的異或。

QR碼版本1是由21位= 441位表示的矩陣，表示爲黑色或白色方塊，其中208位== 26字節用於數據和ecc。

具有糾錯等級L的QR碼具有152位== 19個字節的數據和56位== 7個字節的ecc，4個用於校正，3個用於檢測。用於校正的4個字節可以校正26個字節中的2個，約26個數據字節的7％。除了用於檢測的3個字節外，如果在解碼期間，計算出的任何一個位置都在26個字節的數據範圍之外，也會檢測到不可糾正的錯誤。

生成多項式g（x）是導致7項餘數的8項多項式。 g（x）= 0的7個根是α的連續冪，在這種情況下，α^ 0，α^ 1，...α^ 6 ==十六進制01,02,04,08,10,20,40。

g(x) = (x-1)(x-α)(x-α^2)(x-α^3)(x-α^4)(x-α^5)(x-α^6) 

由於除了==減法== XOR，所述弊可以用加號代替：

g(x) = (x+1)(x+α)(x+α^2)(x+α^3)(x+α^4)(x+α^5)(x+α^6) 
g(x) = (x+01)(x+02)(x+04)(x+08)(x+10)(x+20)(x+40) 
g(x) = 01 x^7 + 7f x^6 + 7a x^5 + 9a x^4 + a4 x^3 + 0b x^2 + 44 x + 75 

考慮19個字節的數據爲多項式M（X）（m表示消息） 。 19個字節的數據用7個字節的零填充x^7。然後，26字節多項式被生成多項式除並且餘數被「減」（異或因爲填充產生零，餘數僅替換填充的字節）到填充數據的低7字節。調用餘數r（x）和編碼結果C（X）：

r(x) = (m(x) x^7) % g(x) 
c(x) = (m(x) x^7) - r(x) 

再次注意減法是異或，相同的加法。

Wiki有關於裏德 - 所羅門像樣的文章：

http://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction

和美國航天局有一個教程：

http://ntrs.nasa.gov/archive/nasa/casi.ntrs.nasa.gov/19900019023.pdf