csharp/common/reedsolomon/ReedSolomonDecoder.cs

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