+++ /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