ErrorCorrection.cpp Example File
appdemos/qtws/QZXing/zxing/zxing/pdf417/decoder/ec/ErrorCorrection.cpp
#include <zxing/pdf417/decoder/ec/ErrorCorrection.h>
#include <zxing/pdf417/decoder/ec/ModulusPoly.h>
#include <zxing/pdf417/decoder/ec/ModulusGF.h>
using std::vector;
using zxing::Ref;
using zxing::ArrayRef;
using zxing::pdf417::decoder::ec::ErrorCorrection;
using zxing::pdf417::decoder::ec::ModulusPoly;
using zxing::pdf417::decoder::ec::ModulusGF;
ErrorCorrection::ErrorCorrection()
: field_(ModulusGF::PDF417_GF)
{
}
void ErrorCorrection::decode(ArrayRef<int> received,
int numECCodewords,
ArrayRef<int> erasures)
{
Ref<ModulusPoly> poly (new ModulusPoly(field_, received));
ArrayRef<int> S( new Array<int>(numECCodewords));
bool error = false;
for (int i = numECCodewords; i > 0; i--) {
int eval = poly->evaluateAt(field_.exp(i));
S[numECCodewords - i] = eval;
if (eval != 0) {
error = true;
}
}
if (error) {
Ref<ModulusPoly> knownErrors = field_.getOne();
for (int i=0;i<erasures->size();i++) {
int b = field_.exp(received->size() - 1 - erasures[i]);
ArrayRef<int> one_minus_b_x(new Array<int>(2));
one_minus_b_x[1]=field_.subtract(0,b);
one_minus_b_x[0]=1;
Ref<ModulusPoly> term (new ModulusPoly(field_,one_minus_b_x));
knownErrors = knownErrors->multiply(term);
}
Ref<ModulusPoly> syndrome (new ModulusPoly(field_, S));
vector<Ref<ModulusPoly> > sigmaOmega (
runEuclideanAlgorithm(field_.buildMonomial(numECCodewords, 1), syndrome, numECCodewords));
Ref<ModulusPoly> sigma = sigmaOmega[0];
Ref<ModulusPoly> omega = sigmaOmega[1];
ArrayRef<int> errorLocations = findErrorLocations(sigma);
ArrayRef<int> errorMagnitudes = findErrorMagnitudes(omega, sigma, errorLocations);
for (int i = 0; i < errorLocations->size(); i++) {
int position = received->size() - 1 - field_.log(errorLocations[i]);
if (position < 0) {
throw ReedSolomonException("Bad error location!");
}
received[position] = field_.subtract(received[position], errorMagnitudes[i]);
#if (defined (DEBUG) && defined _WIN32)
{
WCHAR szmsg[256];
swprintf(szmsg,L"ErrorCorrection::decode: fix @ %d, new value = %d\n",
position, received[position]);
OutputDebugString(szmsg);
}
#endif
}
}
}
vector<Ref<ModulusPoly> > ErrorCorrection::runEuclideanAlgorithm(Ref<ModulusPoly> a, Ref<ModulusPoly> b, int R)
{
if (a->getDegree() < b->getDegree()) {
Ref<ModulusPoly> temp = a;
a = b;
b = temp;
}
Ref<ModulusPoly> rLast ( a);
Ref<ModulusPoly> r ( b);
Ref<ModulusPoly> tLast ( field_.getZero());
Ref<ModulusPoly> t ( field_.getOne());
while (r->getDegree() >= R / 2) {
Ref<ModulusPoly> rLastLast (rLast);
Ref<ModulusPoly> tLastLast (tLast);
rLast = r;
tLast = t;
if (rLast->isZero()) {
throw ReedSolomonException("Euclidean algorithm already terminated?");
}
r = rLastLast;
Ref<ModulusPoly> q (field_.getZero());
int denominatorLeadingTerm = rLast->getCoefficient(rLast->getDegree());
int dltInverse = field_.inverse(denominatorLeadingTerm);
while (r->getDegree() >= rLast->getDegree() && !r->isZero()) {
int degreeDiff = r->getDegree() - rLast->getDegree();
int scale = field_.multiply(r->getCoefficient(r->getDegree()), dltInverse);
q = q->add(field_.buildMonomial(degreeDiff, scale));
r = r->subtract(rLast->multiplyByMonomial(degreeDiff, scale));
}
t = q->multiply(tLast)->subtract(tLastLast)->negative();
}
int sigmaTildeAtZero = t->getCoefficient(0);
if (sigmaTildeAtZero == 0) {
throw ReedSolomonException("sigmaTilde = 0!");
}
int inverse = field_.inverse(sigmaTildeAtZero);
Ref<ModulusPoly> sigma (t->multiply(inverse));
Ref<ModulusPoly> omega (r->multiply(inverse));
vector<Ref<ModulusPoly> > v(2);
v[0] = sigma;
v[1] = omega;
return v;
}
ArrayRef<int> ErrorCorrection::findErrorLocations(Ref<ModulusPoly> errorLocator) {
int numErrors = errorLocator->getDegree();
ArrayRef<int> result( new Array<int>(numErrors));
int e = 0;
for (int i = 1; i < field_.getSize() && e < numErrors; i++) {
if (errorLocator->evaluateAt(i) == 0) {
result[e] = field_.inverse(i);
e++;
}
}
if (e != numErrors) {
#if (defined (DEBUG) && defined _WIN32)
char sz[128];
sprintf(sz,"Error number inconsistency, %d/%d!",e,numErrors);
throw ReedSolomonException(sz);
#else
throw ReedSolomonException("Error number inconsistency!");
#endif
}
#if (defined (DEBUG) && defined _WIN32)
{
WCHAR szmsg[256];
swprintf(szmsg,L"ErrorCorrection::findErrorLocations: found %d errors.\n",
e);
OutputDebugString(szmsg);
}
#endif
return result;
}
ArrayRef<int> ErrorCorrection::findErrorMagnitudes(Ref<ModulusPoly> errorEvaluator,
Ref<ModulusPoly> errorLocator,
ArrayRef<int> errorLocations) {
int i;
int errorLocatorDegree = errorLocator->getDegree();
ArrayRef<int> formalDerivativeCoefficients (new Array<int>(errorLocatorDegree));
for (i = 1; i <= errorLocatorDegree; i++) {
formalDerivativeCoefficients[errorLocatorDegree - i] =
field_.multiply(i, errorLocator->getCoefficient(i));
}
Ref<ModulusPoly> formalDerivative (new ModulusPoly(field_, formalDerivativeCoefficients));
int s = errorLocations->size();
ArrayRef<int> result ( new Array<int>(s));
for (i = 0; i < s; i++) {
int xiInverse = field_.inverse(errorLocations[i]);
int numerator = field_.subtract(0, errorEvaluator->evaluateAt(xiInverse));
int denominator = field_.inverse(formalDerivative->evaluateAt(xiInverse));
result[i] = field_.multiply(numerator, denominator);
}
return result;
}