One of PDF417's primary features is error detection
and error correction. Each label has 2 codewords of error
detection. The error correction capacity may be selected by the
user, based on application needs, when the label is to be
generated.
Error detection requires two error-detection
codewords per symbol. The error correction scheme involves
flexibility and user selection; it compensates for label defects
and misdecodes.
At the time of printing a PDF417 bar code, the user
specifies a security level in the range 0 - 8. This means, for
example, that at level 6, a total of 126 codewords can be either
missing or destroyed and the entire label can be read and decoded;
up to that limit, for security level 6, the contents of the
entire label can be recovered.
In addition to correcting for missing or destroyed
data, PDF417 also can recover from misdecodes of codewords. Since
it requires two codewords to recover from a misdecode, one to
detect the error and one to correct for it, a given security
level can support half the number of misdecodes that it can of
undecoded codewords. Erasures + 2(Misdecodes) < Maximum
Limit.
The minimum level of error correction level should
be as defined in Table E.1.
Number of Data Codewords |
Minimum Error Correction Level |
1 to 40 |
2 |
41 to 160 |
3 |
161 to 320 |
4 |
321 to 863 |
5 |
As a guide to using Table E.1, it should be
noted that for normal data encodation in Text Compaction mode, a
data codeword typically encodes 1,8 text characters, and in
Numeric Compaction mode, a data codeword typically encodes 2,93
digits.
Higher levels of error correction should be used
where significant symbol damage or degradation is anticipated. Lower
than recommended error correction levels may be used in closed
system applications.
The objective in an application standard should be
to make use of the features of error correction without
sacrificing the data content capacity.
The following factors should be taken into account
by the user in selecting an error correction level:
The recommended error correction level (see Table
E.1) should be followed.
Since the maximum number of data codewords per
symbol is fixed at 925, large numbers of data codewords limit the
maximum level of error correction that can be implemented. More
than 415 data codewords precludes Error Correction Level 8. More
than 671 data codewords precludes Levels 7 and 8. More than 799
data codewords precludes Levels 6, 7 and 8.
Where ‘PDF417' symbols are likely to have missing
or totally obliterated codewords, the Error Correction Level may
be increased up to Error Correction level 8, or up to a level
where the number of error correction codewords fills the maximum
sized matrix appropriate for the application.
Instead of adopting a high error correction level it
may be simpler, in the application specification, to specify particular
substrates and materials which can protect the ‘PDF417' symbol.
Error Correction should not be used as a substitute
for achieving adequate quality bar code symbols designed for the
application or to compensate for a poor printing process.
The relation of security level to error correction
capability is as follows:
Security Level Maximum Limit
of E + 2(M)*
0 0
1 2
2 6
3 14
4 30
5 62
Security Level Maximum Limit
of E + 2(M)*
6 126
7 254
8 510
* E = Erasures (Undecodable);
M = Misdecodes
Calculating error correction/detection codewords is
based on all data codewords except for the row indicators.
To calculate these codewords, we must first define
the following:
n = number
of codewords
s = user
selectable security level
k = number
of error detection/correction codewords or 2s+1
gk(x) = generator
polynomial (x - 3)(x-32) ... (x-3k), where x is the unknown
variable
ak =
coefficient of powers of x taken from the generator polynomial gk(x)
ck = error
detection/correction codeword* c0 .. ck-1
dn = data codeword
d0 .. dn-1
t1, t2, t3 = temporary
variables
* Notations c0 and c1 are
used for error detection, while c2 to ck-1 are used for error
correction, where k varies according to security level (s).
The generator polynomial coefficients are calculated
as follows:
First, expand the equation into powers of x:
gk(x) = (x - 3)(x-32)
... (x-3k)
= ak0
+ ak1x + ... + ak-1x k-1 + xk
Next, calculate the complement of the coefficients
from above:
For ai = a0 ... ak-1
BEGIN
ai
= ai mod 929
END
Example:
Calculate
generator polynomial coefficients for security level 1.
s = 1
security level 1
k = 2s+1
= 4 number of error detection/correction codewords
g4(x)
= (x-3) (x-32) (x-33) (x-34)
= 59049 - 29160x + 3510x2 - 120x3 + x4
a0
= 59049 mod 929 = 522
a1
= -29160 mod 929 = 568
a2
= 3510 mod 929 = 723
a3
= -120 mod 929 = 809
Note:
Error
Detection/Correction Coefficients
contains all of the coefficient tables necessary to encode a PDF417
label with any security level.
The error detection/correction codewords are
calculated as follows:
Initialize error detection/correction
codewords c0, ..., ck-1 to 0.
Initialize temporary
variables t1,t2, and t3 to 0.
For each codeword di = dn-1
... d0,
BEGIN
t1 =
(di + ck-1) mod 929
For
each error detection/correction codeword cj = ck-1 ... c1,
BEGIN
t2 = (t1 * aj) mod 929
t3 = 929 - t2
cj = (cj-1 + t3) mod 929
END
t2 =
(t1 * a0) mod 929
t3 =
929 - t2
c0 =
t3 mod 929
END
Calculate the complement for
each error detection/correction
codeword cj = c0 ... ck-1
BEGIN
if cj
not 0
cj = 929 - cj
END
Example:
The string PDF417 represented
as codewords is: 453,178,121,239
Next, precede the codewords by the symbol length
descriptor, which is 5.
5,453,178,121,239
Then,
n
= 5 number of codewords (including symbol length
descriptor)
d4
= 5
d3
= 453
d2
= 178
d1
= 121
d0
= 239
Let's use a security level of
1. So,
s
= 1
k
= 2s+1 = 4
a0,
... ,a3 = 522,568,723,809
The calculations are:
Initialize
c0, ... ,c3 to 0
t1 =
(d4 + c3) mod 929 = (5 + 0) mod 929 = 5
t2 = (t1 * a3) mod 929 = (5 * 809) mod 929 = 329
t3 = 929 - t2 = 929 - 329 = 600
c3 = (c2 + t3) mod 929 = (0 + 600) mod 929 = 600
t2 = (t1 * a2) mod 929 = (5 * 723) mod 929 = 828
t3 = 929 - t2 = 929 - 828 = 101
c2 = (c1 + t3) mod 929 = (0 + 101) mod 929 = 101
t2 = (t1 * a1) mod 929 = (5 * 568) mod 929 = 53
t3 = 929 - t2 = 929 - 53 = 876
c1 = (c0 + t3) mod 929 = (0 + 876) mod 929 = 876
t2 = (t1 * a0) mod 929 = (5 * 522) mod 929 = 752
t3 = 929 - t2 = 929 - 752 = 177
c0 = t3 mod 929 = 177 mod 929 = 177
t1 =
(d3 + c3) mod 929 = (453 + 600) mod 929 = 124
t2 = (t1 * a3) mod 929 = (124 * 809) mod 929 = 913
t3 = 929 - t2 = 929 - 913 = 16
c3 = (c2 + t3) mod 929 = (101 + 16) mod 929 = 117
t2 = (t1 * a2) mod 929 = (124 * 723) mod 929 = 468
t3 = 929 - t2 = 929 - 468 = 461
c2 = (c1 + t3) mod 929 = (876 + 461) mod 929 = 408
t2 = (t1 * a1) mod 929 = (124 * 568) mod 929 = 757
t3 = 929 - t2 = 929 - 757 = 172
c1 = (c0 + t3) mod 929 = (177 + 172) mod 929 = 349
t2 = (t1 * a0) mod 929 = (124 * 522) mod 929 = 627
t3 = 929 - t2 = 929 - 627 = 302
c0 = t3 mod 929 = 302 mod 929 = 302
t1 =
(d2 + c3) mod 929 = (178 + 117) mod 929 = 295
t2 = (t1 * a3) mod 929 = (295 * 809) mod 929 = 831
t3 = 929 - t2 = 929 - 831 = 98
c3 = (c2 + t3) mod 929 = (408 + 98) mod 929 = 506
t2 = (t1 * a2) mod 929 = (295 * 723) mod 929 = 544
t3 = 929 - t2 = 929 - 544 = 385
c2 = (c1 + t3) mod 929 = (349 + 385) mod 929 = 734
t2 = (t1 * a1) mod 929 = (295 * 568) mod 929 = 340
t3 = 929 - t2 = 929 - 340 = 589
c1 = (c0 + t3) mod 929 = (302 + 589) mod 929 = 891
t2 = (t1 * a0) mod 929 = (295 * 522) mod 929 = 705
t3 = 929 - t2 = 929 - 705 = 224
c0 = t3 mod 929 = 224 mod 929 = 224
t1 =
(d1 + c3) mod 929 = (121 + 506) mod 929 = 627
t2 = (t1 * a3) mod 929 = (627 * 809) mod 929 = 9
t3 = 929 - t2 = 929 - 9 = 920
c3 = (c2 + t3) mod 929 = (734 + 920) mod 929 = 725
t2 = (t1 * a2) mod 929 = (627 * 723) mod 929 = 898
t3 = 929 - t2 = 929 - 898 = 31
c2 = (c1 + t3) mod 929 = (891 + 31) mod 929 = 922
t2 = (t1 * a1) mod 929 = (627 * 568) mod 929 = 329
t3 = 929 - t2 = 929 - 329 = 600
c1 = (c0 + t3) mod 929 = (224 + 600) mod 929 = 824
t2 = (t1 * a0) mod 929 = (627 * 522) mod 929 = 286
t3 = 929 - t2 = 929 - 286 = 643
c0 = t3 mod 929 = 643 mod 929 = 643
t1 =
(d0 + c3) mod 929 = (239 + 725) mod 929 = 35
t2 = (t1 * a3) mod 929 = (35 * 809) mod 929 = 445
t3 = 929 - t2 = 929 - 445 = 484
c3 = (c2 + t3) mod 929 = (922 + 484) mod 929 = 477
t2 = (t1 * a2) mod 929 = (35 * 723) mod 929 = 222
t3 = 929 - t2 = 929 - 222 = 707
c2 = (c1 + t3) mod 929 = (824 + 707) mod 929 = 602
t2 = (t1 * a1) mod 929 = (35 * 568) mod 929 = 371
t3 = 929 - t2 = 929 - 371 = 558
c1 = (c0 + t3) mod 929 = (643 + 558) mod 929 = 272
t2 = (t1 * a0) mod 929 = (35 * 522) mod 929 = 619
t3 = 929 - t2 = 929 - 619 = 310
c0 = t3 mod 929 = 310 mod 929 = 310
Finally calculate the complement of the results from
above, to get the 4 error detection/correction codewords for the
symbol PDF417 as follows:
c3 =
929 - c3 = 929 - 477 = 452
c2 =
929 - c2 = 929 - 602 = 327
c1 =
929 - c1 = 929 - 272 = 657
c0 =
929 - c0 = 929 - 310 = 619