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  */
  41 public final class ReedSolomonDecoder {
  42
  43   private ReedSolomonDecoder() {
  44   }
  45
  46   public static void decode(int[] received, int twoS) throws ReedSolomonException {
  47     GF256Poly poly = new GF256Poly(received);
  48     int[] syndromeCoefficients = new int[twoS];
  49     for (int i = 0; i < twoS; i++) {
  50       syndromeCoefficients[syndromeCoefficients.length - 1 - i] = poly.evaluateAt(GF256.exp(i));
  51     }
  52     GF256Poly syndrome = new GF256Poly(syndromeCoefficients);
  53     if (!syndrome.isZero()) { // Error
  54       GF256Poly[] sigmaOmega =
  55           runEuclideanAlgorithm(GF256Poly.buildMonomial(twoS, 1), syndrome, twoS);
  56       int[] errorLocations = findErrorLocations(sigmaOmega[0]);
  57       int[] errorMagnitudes = findErrorMagnitudes(sigmaOmega[1], errorLocations);
  58       for (int i = 0; i < errorLocations.length; i++) {
  59         int position = received.length - 1 - GF256.log(errorLocations[i]);
  60         received[position] = GF256.addOrSubtract(received[position], errorMagnitudes[i]);
  61       }
  62     }
  63   }
  64
  65   private static GF256Poly[] runEuclideanAlgorithm(GF256Poly a, GF256Poly b, int R)
  66       throws ReedSolomonException {
  67     // Assume a's degree is >= b's
  68     if (a.getDegree() < b.getDegree()) {
  69       GF256Poly temp = a;
  70       a = b;
  71       b = temp;
  72     }
  73
  74     GF256Poly rLast = a;
  75     GF256Poly r = b;
  76     GF256Poly sLast = GF256Poly.ONE;
  77     GF256Poly s = GF256Poly.ZERO;
  78     GF256Poly tLast = GF256Poly.ZERO;
  79     GF256Poly t = GF256Poly.ONE;
  80
  81     // Run Euclidean algorithm until r's degree is less than R/2
  82     while (r.getDegree() >= R / 2) {
  83       GF256Poly rLastLast = rLast;
  84       GF256Poly sLastLast = sLast;
  85       GF256Poly tLastLast = tLast;
  86       rLast = r;
  87       sLast = s;
  88       tLast = t;
  89
  90       // Divide rLastLast by rLast, with quotient in q and remainder in r
  91       if (rLast.isZero()) {
  92         // Oops, Euclidean algorithm already terminated?
  93         throw new ReedSolomonException("r_{i-1} was zero");
  94       }
  95       r = rLastLast;
  96       GF256Poly q = GF256Poly.ZERO;
  97       int denominatorLeadingTerm = rLast.getCoefficient(rLast.getDegree());
  98       int dltInverse = GF256.inverse(denominatorLeadingTerm);
  99       while (r.getDegree() >= rLast.getDegree() && !r.isZero()) {
 100         int degreeDiff = r.getDegree() - rLast.getDegree();
 101         int scale = GF256.multiply(r.getCoefficient(r.getDegree()), dltInverse);
 102         q = q.addOrSubtract(GF256Poly.buildMonomial(degreeDiff, scale));
 103         r = r.addOrSubtract(rLast.multiplyByMonomial(degreeDiff, scale));
 104       }
 105
 106       s = q.multiply(sLast).addOrSubtract(sLastLast);
 107       t = q.multiply(tLast).addOrSubtract(tLastLast);
 108     }
 109
 110     int sigmaTildeAtZero = t.getCoefficient(0);
 111     if (sigmaTildeAtZero == 0) {
 112       throw new ReedSolomonException("sigmaTilde(0) was zero");
 113     }
 114
 115     int inverse = GF256.inverse(sigmaTildeAtZero);
 116     GF256Poly sigma = t.multiply(inverse);
 117     GF256Poly omega = r.multiply(inverse);
 118     return new GF256Poly[] { sigma, omega };
 119   }
 120
 121   private static int[] findErrorLocations(GF256Poly errorLocator)
 122       throws ReedSolomonException {
 123     // This is a direct application of Chien's search
 124     Vector errorLocations = new Vector(3);
 125     for (int i = 1; i < 256; i++) {
 126       if (errorLocator.evaluateAt(i) == 0) {
 127         errorLocations.addElement(new Integer(GF256.inverse(i)));
 128       }
 129     }
 130     if (errorLocations.size() != errorLocator.getDegree()) {
 131       throw new ReedSolomonException("Error locator degree does not match number of roots");
 132     }
 133     int[] result = new int[errorLocations.size()]; // Can't use toArray() here
 134     for (int i = 0; i < result.length; i++) {
 135       result[i] = ((Integer) errorLocations.elementAt(i)).intValue();
 136     }
 137     return result;
 138   }
 139
 140   private static int[] findErrorMagnitudes(GF256Poly errorEvaluator,
 141                                            int[] errorLocations) {
 142     // This is directly applying Forney's Formula
 143     int s = errorLocations.length;
 144     int[] result = new int[s];
 145     for (int i = 0; i < errorLocations.length; i++) {
 146       int xiInverse = GF256.inverse(errorLocations[i]);
 147       int denominator = 1;
 148       for (int j = 0; j < s; j++) {
 149         if (i != j) {
 150           denominator = GF256.multiply(denominator,
 151               GF256.addOrSubtract(1, GF256.multiply(errorLocations[j], xiInverse)));
 152         }
 153       }
 154       result[i] = GF256.multiply(errorEvaluator.evaluateAt(xiInverse),
 155                                  GF256.inverse(denominator));
 156     }
 157     return result;
 158   }
 159
 160 }