--- /dev/null
+/*\r
+* Licensed under the Apache License, Version 2.0 (the "License");\r
+* you may not use this file except in compliance with the License.\r
+* You may obtain a copy of the License at\r
+*\r
+* http://www.apache.org/licenses/LICENSE-2.0\r
+*\r
+* Unless required by applicable law or agreed to in writing, software\r
+* distributed under the License is distributed on an "AS IS" BASIS,\r
+* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\r
+* See the License for the specific language governing permissions and\r
+* limitations under the License.\r
+*/\r
+\r
+using System;\r
+namespace com.google.zxing.common.reedsolomon\r
+{\r
+\r
+ /// <summary> <p>Implements Reed-Solomon decoding, as the name implies.</p>\r
+ /// \r
+ /// <p>The algorithm will not be explained here, but the following references were helpful\r
+ /// in creating this implementation:</p>\r
+ /// \r
+ /// <ul>\r
+ /// <li>Bruce Maggs.\r
+ /// <a href="http://www.cs.cmu.edu/afs/cs.cmu.edu/project/pscico-guyb/realworld/www/rs_decode.ps">\r
+ /// "Decoding Reed-Solomon Codes"</a> (see discussion of Forney's Formula)</li>\r
+ /// <li>J.I. Hall. <a href="www.mth.msu.edu/~jhall/classes/codenotes/GRS.pdf">\r
+ /// "Chapter 5. Generalized Reed-Solomon Codes"</a>\r
+ /// (see discussion of Euclidean algorithm)</li>\r
+ /// </ul>\r
+ /// \r
+ /// <p>Much credit is due to William Rucklidge since portions of this code are an indirect\r
+ /// port of his C++ Reed-Solomon implementation.</p>\r
+ /// \r
+ /// </summary>\r
+ /// <author> srowen@google.com (Sean Owen)\r
+ /// </author>\r
+ /// <author> William Rucklidge\r
+ /// </author>\r
+ public sealed class ReedSolomonDecoder\r
+ {\r
+ private GF256 field;\r
+\r
+ public ReedSolomonDecoder(GF256 field) {\r
+ this.field = field;\r
+ }\r
+\r
+ /**\r
+ * <p>Decodes given set of received codewords, which include both data and error-correction\r
+ * codewords. Really, this means it uses Reed-Solomon to detect and correct errors, in-place,\r
+ * in the input.</p>\r
+ *\r
+ * @param received data and error-correction codewords\r
+ * @param twoS number of error-correction codewords available\r
+ * @throws ReedSolomonException if decoding fails for any reason\r
+ */\r
+ public void decode(int[] received, int twoS) {\r
+ try{\r
+ \r
+ \r
+ GF256Poly poly = new GF256Poly(field, received);\r
+ int[] syndromeCoefficients = new int[twoS];\r
+ bool dataMatrix = field.Equals(GF256.DATA_MATRIX_FIELD);\r
+ bool noError = true;\r
+ for (int i = 0; i < twoS; i++) {\r
+ // Thanks to sanfordsquires for this fix:\r
+ int eval = poly.evaluateAt(field.exp(dataMatrix ? i + 1 : i));\r
+ syndromeCoefficients[syndromeCoefficients.Length - 1 - i] = eval;\r
+ if (eval != 0) {\r
+ noError = false;\r
+ }\r
+ }\r
+ if (noError) {\r
+ return;\r
+ }\r
+ GF256Poly syndrome = new GF256Poly(field, syndromeCoefficients);\r
+ GF256Poly[] sigmaOmega =\r
+ runEuclideanAlgorithm(field.buildMonomial(twoS, 1), syndrome, twoS);\r
+ GF256Poly sigma = sigmaOmega[0];\r
+ GF256Poly omega = sigmaOmega[1];\r
+ int[] errorLocations = findErrorLocations(sigma);\r
+ int[] errorMagnitudes = findErrorMagnitudes(omega, errorLocations, dataMatrix);\r
+ for (int i = 0; i < errorLocations.Length; i++) {\r
+ int position = received.Length - 1 - field.log(errorLocations[i]);\r
+ if (position < 0) {\r
+ throw new ReedSolomonException("Bad error location");\r
+ }\r
+ received[position] = GF256.addOrSubtract(received[position], errorMagnitudes[i]);\r
+ }\r
+ }catch(ReedSolomonException e){\r
+ throw new ReedSolomonException(e.Message);\r
+ }\r
+ }\r
+\r
+ private GF256Poly[] runEuclideanAlgorithm(GF256Poly a, GF256Poly b, int R){\r
+ // Assume a's degree is >= b's\r
+ if (a.getDegree() < b.getDegree()) {\r
+ GF256Poly temp = a;\r
+ a = b;\r
+ b = temp;\r
+ }\r
+\r
+ GF256Poly rLast = a;\r
+ GF256Poly r = b;\r
+ GF256Poly sLast = field.getOne();\r
+ GF256Poly s = field.getZero();\r
+ GF256Poly tLast = field.getZero();\r
+ GF256Poly t = field.getOne();\r
+\r
+ // Run Euclidean algorithm until r's degree is less than R/2\r
+ while (r.getDegree() >= R / 2) {\r
+ GF256Poly rLastLast = rLast;\r
+ GF256Poly sLastLast = sLast;\r
+ GF256Poly tLastLast = tLast;\r
+ rLast = r;\r
+ sLast = s;\r
+ tLast = t;\r
+\r
+ // Divide rLastLast by rLast, with quotient in q and remainder in r\r
+ if (rLast.isZero()) {\r
+ // Oops, Euclidean algorithm already terminated?\r
+ throw new ReedSolomonException("r_{i-1} was zero");\r
+ }\r
+ r = rLastLast;\r
+ GF256Poly q = field.getZero();\r
+ int denominatorLeadingTerm = rLast.getCoefficient(rLast.getDegree());\r
+ int dltInverse = field.inverse(denominatorLeadingTerm);\r
+ while (r.getDegree() >= rLast.getDegree() && !r.isZero()) {\r
+ int degreeDiff = r.getDegree() - rLast.getDegree();\r
+ int scale = field.multiply(r.getCoefficient(r.getDegree()), dltInverse);\r
+ q = q.addOrSubtract(field.buildMonomial(degreeDiff, scale));\r
+ r = r.addOrSubtract(rLast.multiplyByMonomial(degreeDiff, scale));\r
+ }\r
+\r
+ s = q.multiply(sLast).addOrSubtract(sLastLast);\r
+ t = q.multiply(tLast).addOrSubtract(tLastLast);\r
+ }\r
+\r
+ int sigmaTildeAtZero = t.getCoefficient(0);\r
+ if (sigmaTildeAtZero == 0) {\r
+ throw new ReedSolomonException("sigmaTilde(0) was zero");\r
+ }\r
+\r
+ int inverse = field.inverse(sigmaTildeAtZero);\r
+ GF256Poly sigma = t.multiply(inverse);\r
+ GF256Poly omega = r.multiply(inverse);\r
+ return new GF256Poly[]{sigma, omega};\r
+ }\r
+\r
+ private int[] findErrorLocations(GF256Poly errorLocator){\r
+ // This is a direct application of Chien's search\r
+ int numErrors = errorLocator.getDegree();\r
+ if (numErrors == 1) { // shortcut\r
+ return new int[] { errorLocator.getCoefficient(1) };\r
+ }\r
+ int[] result = new int[numErrors];\r
+ int e = 0;\r
+ for (int i = 1; i < 256 && e < numErrors; i++) {\r
+ if (errorLocator.evaluateAt(i) == 0) {\r
+ result[e] = field.inverse(i);\r
+ e++;\r
+ }\r
+ }\r
+ if (e != numErrors) {\r
+ throw new ReedSolomonException("Error locator degree does not match number of roots");\r
+ }\r
+ return result;\r
+ }\r
+\r
+ private int[] findErrorMagnitudes(GF256Poly errorEvaluator, int[] errorLocations, bool dataMatrix) {\r
+ // This is directly applying Forney's Formula\r
+ int s = errorLocations.Length;\r
+ int[] result = new int[s];\r
+ for (int i = 0; i < s; i++) {\r
+ int xiInverse = field.inverse(errorLocations[i]);\r
+ int denominator = 1;\r
+ for (int j = 0; j < s; j++) {\r
+ if (i != j) {\r
+ denominator = field.multiply(denominator,\r
+ GF256.addOrSubtract(1, field.multiply(errorLocations[j], xiInverse)));\r
+ }\r
+ }\r
+ result[i] = field.multiply(errorEvaluator.evaluateAt(xiInverse),\r
+ field.inverse(denominator));\r
+ // Thanks to sanfordsquires for this fix:\r
+ if (dataMatrix) {\r
+ result[i] = field.multiply(result[i], xiInverse);\r
+ }\r
+ }\r
+ return result;\r
+ }\r
+ \r
+ }\r
+}
\ No newline at end of file
projects / zxing.git / blobdiff