csharp/common/reedsolomon/ReedSolomonDecoder.cs

   1 /*\r
   2 * Licensed under the Apache License, Version 2.0 (the "License");\r
   3 * you may not use this file except in compliance with the License.\r
   4 * You may obtain a copy of the License at\r
   5 *\r
   6 *      http://www.apache.org/licenses/LICENSE-2.0\r
   7 *\r
   8 * Unless required by applicable law or agreed to in writing, software\r
   9 * distributed under the License is distributed on an "AS IS" BASIS,\r
  10 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\r
  11 * See the License for the specific language governing permissions and\r
  12 * limitations under the License.\r
  13 */\r
  14 \r
  15 using System;\r
  16 namespace com.google.zxing.common.reedsolomon\r
  17 {\r
  18 \r
  19     /// <summary> <p>Implements Reed-Solomon decoding, as the name implies.</p>\r
  20     /// \r
  21     /// <p>The algorithm will not be explained here, but the following references were helpful\r
  22     /// in creating this implementation:</p>\r
  23     /// \r
  24     /// <ul>\r
  25     /// <li>Bruce Maggs.\r
  26     /// <a href="http://www.cs.cmu.edu/afs/cs.cmu.edu/project/pscico-guyb/realworld/www/rs_decode.ps">\r
  27     /// "Decoding Reed-Solomon Codes"</a> (see discussion of Forney's Formula)</li>\r
  28     /// <li>J.I. Hall. <a href="www.mth.msu.edu/~jhall/classes/codenotes/GRS.pdf">\r
  29     /// "Chapter 5. Generalized Reed-Solomon Codes"</a>\r
  30     /// (see discussion of Euclidean algorithm)</li>\r
  31     /// </ul>\r
  32     /// \r
  33     /// <p>Much credit is due to William Rucklidge since portions of this code are an indirect\r
  34     /// port of his C++ Reed-Solomon implementation.</p>\r
  35     /// \r
  36     /// </summary>\r
  37     /// <author>  srowen@google.com (Sean Owen)\r
  38     /// </author>\r
  39     /// <author>  William Rucklidge\r
  40     /// </author>\r
  41     public sealed class ReedSolomonDecoder\r
  42     {\r
  43           private GF256 field;\r
  44 \r
  45           public ReedSolomonDecoder(GF256 field) {\r
  46             this.field = field;\r
  47           }\r
  48 \r
  49           /**\r
  50            * <p>Decodes given set of received codewords, which include both data and error-correction\r
  51            * codewords. Really, this means it uses Reed-Solomon to detect and correct errors, in-place,\r
  52            * in the input.</p>\r
  53            *\r
  54            * @param received data and error-correction codewords\r
  55            * @param twoS number of error-correction codewords available\r
  56            * @throws ReedSolomonException if decoding fails for any reason\r
  57            */\r
  58           public void decode(int[] received, int twoS) {\r
  59               try{\r
  60               \r
  61               \r
  62                 GF256Poly poly = new GF256Poly(field, received);\r
  63                 int[] syndromeCoefficients = new int[twoS];\r
  64                 bool dataMatrix = field.Equals(GF256.DATA_MATRIX_FIELD);\r
  65                 bool noError = true;\r
  66                 for (int i = 0; i < twoS; i++) {\r
  67                   // Thanks to sanfordsquires for this fix:\r
  68                   int eval = poly.evaluateAt(field.exp(dataMatrix ? i + 1 : i));\r
  69                   syndromeCoefficients[syndromeCoefficients.Length - 1 - i] = eval;\r
  70                   if (eval != 0) {\r
  71                     noError = false;\r
  72                   }\r
  73                 }\r
  74                 if (noError) {\r
  75                   return;\r
  76                 }\r
  77                 GF256Poly syndrome = new GF256Poly(field, syndromeCoefficients);\r
  78                 GF256Poly[] sigmaOmega =\r
  79                     runEuclideanAlgorithm(field.buildMonomial(twoS, 1), syndrome, twoS);\r
  80                 GF256Poly sigma = sigmaOmega[0];\r
  81                 GF256Poly omega = sigmaOmega[1];\r
  82                 int[] errorLocations = findErrorLocations(sigma);\r
  83                 int[] errorMagnitudes = findErrorMagnitudes(omega, errorLocations, dataMatrix);\r
  84                 for (int i = 0; i < errorLocations.Length; i++) {\r
  85                   int position = received.Length - 1 - field.log(errorLocations[i]);\r
  86                   if (position < 0) {\r
  87                     throw new ReedSolomonException("Bad error location");\r
  88                   }\r
  89                   received[position] = GF256.addOrSubtract(received[position], errorMagnitudes[i]);\r
  90                 }\r
  91               }catch(ReedSolomonException e){\r
  92                 throw new ReedSolomonException(e.Message);\r
  93               }\r
  94           }\r
  95 \r
  96           private GF256Poly[] runEuclideanAlgorithm(GF256Poly a, GF256Poly b, int R){\r
  97             // Assume a's degree is >= b's\r
  98             if (a.getDegree() < b.getDegree()) {\r
  99               GF256Poly temp = a;\r
 100               a = b;\r
 101               b = temp;\r
 102             }\r
 103 \r
 104             GF256Poly rLast = a;\r
 105             GF256Poly r = b;\r
 106             GF256Poly sLast = field.getOne();\r
 107             GF256Poly s = field.getZero();\r
 108             GF256Poly tLast = field.getZero();\r
 109             GF256Poly t = field.getOne();\r
 110 \r
 111             // Run Euclidean algorithm until r's degree is less than R/2\r
 112             while (r.getDegree() >= R / 2) {\r
 113               GF256Poly rLastLast = rLast;\r
 114               GF256Poly sLastLast = sLast;\r
 115               GF256Poly tLastLast = tLast;\r
 116               rLast = r;\r
 117               sLast = s;\r
 118               tLast = t;\r
 119 \r
 120               // Divide rLastLast by rLast, with quotient in q and remainder in r\r
 121               if (rLast.isZero()) {\r
 122                 // Oops, Euclidean algorithm already terminated?\r
 123                 throw new ReedSolomonException("r_{i-1} was zero");\r
 124               }\r
 125               r = rLastLast;\r
 126               GF256Poly q = field.getZero();\r
 127               int denominatorLeadingTerm = rLast.getCoefficient(rLast.getDegree());\r
 128               int dltInverse = field.inverse(denominatorLeadingTerm);\r
 129               while (r.getDegree() >= rLast.getDegree() && !r.isZero()) {\r
 130                 int degreeDiff = r.getDegree() - rLast.getDegree();\r
 131                 int scale = field.multiply(r.getCoefficient(r.getDegree()), dltInverse);\r
 132                 q = q.addOrSubtract(field.buildMonomial(degreeDiff, scale));\r
 133                 r = r.addOrSubtract(rLast.multiplyByMonomial(degreeDiff, scale));\r
 134               }\r
 135 \r
 136               s = q.multiply(sLast).addOrSubtract(sLastLast);\r
 137               t = q.multiply(tLast).addOrSubtract(tLastLast);\r
 138             }\r
 139 \r
 140             int sigmaTildeAtZero = t.getCoefficient(0);\r
 141             if (sigmaTildeAtZero == 0) {\r
 142               throw new ReedSolomonException("sigmaTilde(0) was zero");\r
 143             }\r
 144 \r
 145             int inverse = field.inverse(sigmaTildeAtZero);\r
 146             GF256Poly sigma = t.multiply(inverse);\r
 147             GF256Poly omega = r.multiply(inverse);\r
 148             return new GF256Poly[]{sigma, omega};\r
 149           }\r
 150 \r
 151           private int[] findErrorLocations(GF256Poly errorLocator){\r
 152             // This is a direct application of Chien's search\r
 153             int numErrors = errorLocator.getDegree();\r
 154             if (numErrors == 1) { // shortcut\r
 155               return new int[] { errorLocator.getCoefficient(1) };\r
 156             }\r
 157             int[] result = new int[numErrors];\r
 158             int e = 0;\r
 159             for (int i = 1; i < 256 && e < numErrors; i++) {\r
 160               if (errorLocator.evaluateAt(i) == 0) {\r
 161                 result[e] = field.inverse(i);\r
 162                 e++;\r
 163               }\r
 164             }\r
 165             if (e != numErrors) {\r
 166               throw new ReedSolomonException("Error locator degree does not match number of roots");\r
 167             }\r
 168             return result;\r
 169           }\r
 170 \r
 171           private int[] findErrorMagnitudes(GF256Poly errorEvaluator, int[] errorLocations, bool dataMatrix) {\r
 172             // This is directly applying Forney's Formula\r
 173             int s = errorLocations.Length;\r
 174             int[] result = new int[s];\r
 175             for (int i = 0; i < s; i++) {\r
 176               int xiInverse = field.inverse(errorLocations[i]);\r
 177               int denominator = 1;\r
 178               for (int j = 0; j < s; j++) {\r
 179                 if (i != j) {\r
 180                   denominator = field.multiply(denominator,\r
 181                       GF256.addOrSubtract(1, field.multiply(errorLocations[j], xiInverse)));\r
 182                 }\r
 183               }\r
 184               result[i] = field.multiply(errorEvaluator.evaluateAt(xiInverse),\r
 185                   field.inverse(denominator));\r
 186               // Thanks to sanfordsquires for this fix:\r
 187               if (dataMatrix) {\r
 188                 result[i] = field.multiply(result[i], xiInverse);\r
 189               }\r
 190             }\r
 191             return result;\r
 192           }\r
 193     \r
 194     }\r
 195 }