core/src/com/google/zxing/common/reedsolomon/ReedSolomonDecoder.java

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