Note : Les descriptions sont présentées dans la langue officielle dans laquelle elles ont été soumises.
CA 02202139 1997-04-08
WO 96/13803 PCT/CA95/00606
1
BAR CODE FOR MAIL PROCESSING
Hackaround of the Invention
This invention relates to bar codes used in the
processing of mail pieces.
In many countries a postal code is used to
facilitate automation in sorting. In Canada, the postal
code contains three alphabetic characters (letters)
interleaved with three numeric characters (numbers) while
in the U.S.A. the zip code consists of five numbers. If a
customer has applied the postal code to an envelope this is
converted by an optical character reader (O.C.R.) and
computer in the Post Office to a bar code which is then
printed on the envelope. If the customer has not applied
the postal code, this will be generated in the Post Office
and the bar code will be printed on the envelope as before.
It is also becoming more usual for the large
corporate customer to apply the postal code in bar code
format. A bar code is used because it is easier to read
automatically than alphanumeric characters.
The British Post Office (BPO) has developed a 4
state bar code. The four possible states are one which
comprises only a tracker element, one which comprises a
tracker element and an ascender element, one which
comprises a tracker element and a descender element and one
which comprises a tracker element, an ascender element and
a descender element. These elements will be described in
detail hereinbelow.
The HPO code uses four bars to represent each
alphanumeric character but for error protection each
character must have two ascenders and two descenders which
limits the number of possible combinations to 36. Error
detection is dealt with by including a check sum. The HPO
code is intended to be printed by customers (mailers) to
encode sort at ion information.
The BPO code uses a single bar to indicate the
start of the code and a different single bar to indicate
CA 02202139 1997-04-08
2
the end of the code. The start/stop bars in the HPO code
can easily be confused and can result in decoding of an
upside down bar code.
A paper entitled "A Damage Resistant Bar Code for
the Royal Mail" by Blahut et al, 1992 discusses an
improvement of the BPO bar code which essentially makes the
BPO code more robust by adding Reed-Solomon error
correction to handle missing bars (erasures) and bar print
errors. The encoding is based on codewords of two bars
each - a left and right codeword - and the interleaving ef
the codewords to form a bar code. Blahut has also
identified some decoding logic to recover from missing or
incorrect bars and overcome the weakness of the start/stop
pattern with decoding logic. The Blahut Code is intended
to be printed by the Post Office as an internal code and
only postal sortation data is encoded.
U.S. °atent 5,288,970, which does not relate
specifically to mail handling, discloses a bar code having
a start field followed by an instruction field, a reference
field, a check sum field and a~ stcp field. The instruction
field contains data relating to an action to be taken and
the reference field contains data related to the data in
the instruction. field. As an example, the data in the
instruction field may specify an action to be taken and the
data in the reference field may identify what the specified
action is to be taken on. There is no suggestion of the
data in the instruction field specifying the structure of
the reference field or vice versa.
It is an object of the present invention to
improve on the BPO and Hlahut codes by offering a robust
code which is sufficiently flexible that it may be applied
by the Post Office or the customer and which can be used
not only for the postal code but for route sequencing,
track and tracing, revenue accounting and other customer
information as well as customer service information such as
return mail management, automated data entry of customer
AIAEiVDED SHEEP
CA 02202139 1997-04-08
3
information and the like.
Summary of the Invention
The present invention provides a method of
reading a bar codeword on a mail piece by a code reader,
the bar codeword containing information for the processing
of the mail piece, the bar codeword having a plurality of
parallel bars each of which has a state selected from a
plurality of possible states, the bar codeword comprising a
start field followed by a data content identifier (DCI)
field specifying the number, type, order and length of the
various fields making up the codeword and the format of the
data characters within the fields of the codeword followed
by at least one data field, followed by a Reed-Solomon
parity field, followed by a stop field, the DCI instructing
the code reader how to decode the remaining data
characters.
According to another aspect, the present
invention provides a mail piece bearing a bar codeword
containing information for the processing of the mail
piece, the bar codeword having a plurality of parallel bars
each of which has a state selected from a plurality of
possible states, the bar codeword comprising a start field
followed by a data content identifier (DCI) field
specifying the structure of the codeword followed by at
least one data field, followed by a Reed-Solomon parity
field, followed by a stop field.
The term "structure" in relation to the codeword
implies the number, type, order and length of the various
fields making up the codeword and the format of the data
characters within the fields.
The use of the DCI permits codewords of different
structure to be read correctly because as soon as the DCI
is read and identified the structure of the codeword is
correspondingly identified. Without a DCI the code reader
would only be capable of reading a single structure for
which it was specifically programmed. This introduces
CA 02202139 1997-04-08
3a
great flexibility because it permits codewords of many
different structures to be used depending on the
application such as domestic codes, global codes, service
codes and internal codes.
In one embodiment of the invention, as in Blahut,
bars which have four possible states are used but the
invention is not limited to the use of a four state code.
The data field may contain different types of information
depending on the application. For example, it may contain
a postal code in the ANANAN format where A is an
alphabetical character and N is a numerical character. The
A's are each represented by three bars and the N's are each
represented by two bars.
The use of the start and stop bars provides an
indication of correct orientation and direction of reading
in a single efficient manner.
Not only postal (sortation and sequencing) data
can be encoded but also customer data to support the
creation of value added products and services selectable by
the customer at the time of printing the mail pieces.
The new coding is space efficient because in a
preferred embodiment it encodes characters in 3 bars with
the numerics in the CPC postal code using only 2 bars each.
The code is highly damage resistant and provides
varying levels of error correction appropriate to the
application. For example, more error correction is
provided in the internal applied codes than the customer
applied codes.
The invention also enables in a specific
embodiment the concatenation of multiple bar codes.
Brief Description of the Drawings
Figure la illustrates the basic elements of the
four state code used in a preferred embodiment of the
invention;
CA 02202139 1997-04-08
WO 96/13803 PCT/CA95/00606
4
Figure lb illustrates the minimum and maximum
dimensions of the bars used in the four state code;
Figures 2a to 2d illustrate how the code pattern
or the individual bars within the code may be skewed;
Figure 3 illust rates a typical bar code employing
the invention;
Figure 4a illust rates another example of a bar
code employing the invention;
Figure 4b illustrates a bar code similar to that
of Figure 4a in which the customer field has been broken
down into sub-fields; and
Figures 5 through 11 illustrate further examples
of bar codes employing the invention.
Description of the Preferred Embodiments
Referring to Figure 1, the basic elements of the
printed four state code are four vertical bars which differ
in length and/ or starting point with respect to the
horizontal.
More particularly, there is a full height bar H
which is the longest of the four bars and extends between
lower and upper horizontal references R1 and R2,
respectively. The bar immediately to the right of bar H is
a bar D which is greater than half of the height of bar H
and extends from above the mid-point of bar H down to the
level of reference Rl. Immediately to the right of bar D
is a bar A which has the same height as bar D but extends
from below the mid-point of bar H up to the level of
reference R2. The final element is a bar T which is
centred about the mid-point of bar H and which has a height
represented by the overlap of bars A and D.
Another way of defining bars H, D, A and T is in
terms of the three basic elements, Tracker, Ascender and
Descender shown in Figure la. The Tracker element is a
short element centred exactly between the lower and upper
references R1 and R2. The Ascender and Descender elements
are identical in length, the Ascender extending upwardly
CA 02202139 1997-04-08
WO 96113803 PCT/CA95/00606
from the upper limit of the Tracker to reference R2 and the
Descender extending downwardly from the lower limit of the
Tracker to reference R1.
The Tracker is present in all of the four bars.
5 In the T bar the Tracker is the only element, the D bar
consists of Tracker and Descender, the A bar consists of
Tracker and Ascender and the H bar consists of the Tracker,
Ascender and Descender. The four possible bars and their
assigned numerical values can be summarized as follows:
BAR ELEMENTS VALUE
T Tracker 3
D Tracker and Descender 2
A Tracker and Ascender 1
H Tracker, Ascender and Descender 0
The maximum and minimum permissible dimensions of
elements A, D, H, T and bar width X are indicated in Figure
lb where the maximum bar outlines are the shaded portions,
and are summarized below:
Element Minimum Maximum
mm in. mm in.
T 1.0 0.04 1.6 0.06
A 2.6 0.10 3.7 0.145
D 2.6 0.10 3.7 0.145
H 4.2 0.165 5.8 0.23
X (bar width) 0.4 0.015 0.6 0.025
bar gap 0.4 0.015
Note: The minimum gap between bars takes
priority over all other dimensions.
The bar density should be around 20-24 bars per
25.4 mm. Figure 2 illustrates two types of skew that can
occur when printing bar codes. Figures 2a and 2b
illustrate code skew a in which the entire code pattern is
skewed with respect to the bottom edge of the mail piece
s and Figures 2c and 2d illustrate bar skew p in which
individual bars are skewed with respect to the centreline
of the code pattern.
For code skew the acceptable limit is less than
CA 02202139 1999-10-13
WO 9G/13803 PCT/CA95/00606
6
+/- 5° from the horizontal and for bar skew the limit is
less than +/- 5o from the vertical. It is possible for
both types of skew to occur on a single item and in that
case the total skew Ia I+ (p I should be less than 5°.
Canada Post Corporation (CPC) proposes using the
basic four state bar code in different applications. The
term PostBar has been coined by CPC to refer to the basic
four state bar code and the letters xyz appear after the
designation PostBar where
"x" is "D" for domestic (Canada) applications
"G" for global (international)
applications
"C" for CPC internal applications and
"S" for service applications.
"yz" specifies the number of characters in the
bar code.
The PostBar applications are as follows:
Domestic Global Service Internal
PostBar.D07 PostHar.Gl2 PostBar.S06 PostBar.ClO
PostHar.Dl2 PostBar.G22 PostHar.Sll
PostBar.D22 PostBar.S21
Let us consider in detail PostBar.ClO
to
illustrate how the four state code 1s applied.
The format
of this code is illustrated i n Fi4ure This may be
3.
summarized as follows=
DATA FIELD BARS DATA
CHARACTERS
Start/synchronization 2
Data Content Identifier (DCI) 3 Z
Postal code (FSA LDU) 15 ANANAN
RS Parity Check 30
Machine ID 4 BBHB
Stop/synchronizat ion _2
Total 56
The data characters are denoted A, N, Z and B. A
is an alphabetic character and is denoted by 3 bars, N is a
numeric character and is denoted by 2 bars, Z is an
alphanumeric (i.e., either alphabetic or numeric) character
CA 02202139 1997-04-08
WO 96/13803 PCTICA95/00606
7
and is denoted by 3 bars and B is 1 bar.
Table 1 shows the encoding for the "A" and "N"
characters and Table 2 shows the encoding for the "Z"
characters.
TABLE 1
'A' CHARACTERS 'N' CHARACTERS
1o
LetterBars Number Bars
A -~ f HI~ p -.
~~p~
g ..tl.~..H~ 1 ...tl...Hle,
C -~ f HAA 2 ...
!v~-
D ..f !-p~HAD 3 ...~~...AH
E .. t HDH 4 ... y...~e,~e~
l ~..
F wf pl-- HDA 5 ...Ii...
G -yy- HDD 6 ... t DH
(...
H ~~~~I-~ HHA ~ ...y... DA
I v~ iw ABA g ...tl...DD
2o J ~~I~y~ AHD 9 ...,~...TH
K ..II.I..pAH
L ..Il.l..AAA
M ..ELI.. HHH
N wlpw ADH
-.~l_!..~A
..
P wlly~ ADD
DHH
R wtw~ DHA
S ~-t~ DHD
l~-
T ..tly. DAB
U wtiv~ DAA
V yiy. DAD
W wti-- DDB
X wtiw DDA
Y wtpw DDD
Z
CA 02202139 1997-04-08
WO 96/13803 PCTlCA95/00606
8
TABLE 2
'Z' CHARACTERS
SymbolBars SymbolBars
Space --f HHT 0 --tp.. DDD
(-~--
A '. t HHH 1 , I-I.. THH
Iy..
Ii --f HHA 2 --.LL. THA
I-~--
C f (1-. ~D 3 .., Li.-THD
D ..tl.L.~ 4 ..,IL. TAH
E .. f ~.I,e,AS ..,1.1..TA~e,
1.1..
P --II-1..HAD 6 ..,l.i..TAD
G --f HDH 7 ..,i.L. TDH
p..
H ..t1.1..~A g ..,1.1..TDA
I --Ell. HDD 9 ..,1.1..TDD
J ..ALL. AHH
K ..1 AHA
L L.
L ..1L1..AHD
M ..li AAH
L.
N ..11.1..AAA
O ..Ii.l..AAD
P ..11.L.~H
Q --1~ ADA
1~~
-Ip~~ ADD
S --fII~.DHH
T tll~- DHA
wtllw DHD
V ..tl.L.'DAH
--t DAA
~ ~--
X --t DAD
l 1..
--ri-I..DDH
Z --ti~l.-DDA
Note that the encoding shown in Table 1 is used
only for the postal code mapping. As seen in Table 1 only
the 9 digit contains the tracking element T which because
of its size is the most likely of the four elements to be
obscured or missing. This minimization of the occurrence
of the T bars provides extra security for the Postal Code.
CA 02202139 1997-04-08
WO 96/13803 PCT/CA95/00606
9
With regard to the "B" bars, these are used only
for the Machine ID and can be decoded using a quadral
representation with 'n' as the number of bars in the data
block and 'Vn' as the value of each bar in the following
equation:
BnBn-1...B1 = Vnx4n 1+Vn-lx4n 2+...t V1x40
The bar values (Vn) are assigned as follows: H=0;
A=1; D=2; T=3
e.g. ADHA = 1 x 43 + 2 x 42 + 0 x 4 + 1 x 40
- 64 + 32 + 0 + 1 - 097
For 4 bars, the maximum value is:
TTTT = 3 x 64 + 3 x 16 + 3 x 4 + 3 x 1 =
225
Referring to the various data fields shown in
Figure 3, the first field is START which comprises an A bar
followed by a T bar. The last field is STOP which also
comprises an A bar followed by a T bar. This sequence
provides an orientation or direction of flow of the code so
that an upside down label or letter inserted backwards can
be identified immediately. The sequence also provides an
additional marker for synchronization and a unique
identifier so that the code can be recognized immediately.
The next field is the DCI (Data Content
Identifier) which specifies the structure and the number of
data elements within the bar code. When a bar code reader
decodes a DCI it will know how to decode the remaining data
elements. The DCI can be either an alphabetic or numeric
character ("Z" character) encoded using three bars
according to Table 2. Within CPC the DCI's are assigned in
the following way:
1-9 Reserved for global (international)
applications
A-L Reserved for domestic (Canada) applications
M-U Reserved for service applications
V-Z Reserved for internal applications.
CA 02202139 1997-04-08
WO 96/13803 PCTICA95/00606
The DCI illustrated in Figure 3 comprises two D
bars followed by one A bar and from Table 2 this
corresponds to the letter Z. When the DCI is a Z this
specifies that there are 6 decodable characters in the form
5 ANANAN for sortation and a binary machine ID in the form
HHHH.
This does in fact correspond with Figure 3 where
the next field is the postal code which in Canada is
constructed as alternate alphabetic/numerical characters
10 ANANAN with each letter being formed by 3 bars and each
number formed of 2 bars as shown in Table 1. The postal
code thus consists of 15 bars. Hy consulting Table 1, it
can be seen the postal code in the example illustrated in
Figure 3 is K1A OH1.
The next field is the Reed-Solomon Parity Check
consisting of 30 bars comprising 10 alphanumeric characters
Z. The RS code chosen is a (16,6) Reed-Solomon code over
GF(64) which can correct 5 symbol errors and up to 10
symbol erasures (30 bars). That is, more than half the bar
code could be missing and the remaining bar code would
still be successfully decoded. The error correcting
capability of this RS code will be discussed in greater
detail below.
The next field is the Machine ID field which
identifies the particular machine which applied the bar
code. The four bars shown in this example are:
ADHA = 1 x 43 + 2 x 42 + 0 x 41 + 1 x 40
- 64 + 32 + 0 + 1 - 097
Turning now to Figure 4a, this illustrates the
format of PostHar.D22 which uses a (25,21) Reed-Solomon
code over GF(64). PostHar.D22 is a customer applied bar
code for domestic Canadian applications. The data
structure may be summarized as follows:
CA 02202139 1997-04-08
WO 96/13803 PCT/CA95/00606
11
DATA FIELD BARS DATA CHARACTERS
Start/synchronization 2
Data Content Identifier (DCI) 3 Z
Postal code (FSA LDU) 15 ANANAN
Address Locator (AL) 12 ZZZZ
Customer Information 33 ZZZZZZZZZZZ
RS Parity Check 12
Stop/synchronization 2
Total
As for the PostBar.ClO code discussed above, data
character A is an alphabetic character denoted by 3 bars, N
is a numeric character denoted by 2 bars and Z is an
alphanumeric character denoted by 3 bars. Table 1 shows
the encoding for the "A" and "N" characters and Table 2
shows the encoding for the "Z" characters.
Referring to the various data fields shown in
Figure 4a, the start and stop fields, the DCI field and the
Postal code fields are identical to the corresponding
fields in the PostBar.ClO code. In the particular example
shown, by consulting Table 2 it will be seen the DCI
corresponds to the letter C and by consulting Table 1 it
will be seen the Postal code corresponds to L3B 4T9.
When the DCI is a C this specifies that there are
21 decodable characters which follow in the form of the
postal code (ANANAN), address locator (ZZZZ) and 11
customer data characters (ZZZZZZZZZZZ).
Unlike PostBar.ClO, PostBar.D22 does not have a
Machine ID field as the printer applying the code is not a
CPC (Canada Post Corporation) machine and is, therefore, of
no real interest.
PostBar.D22 has two fields, namely AL and
Customer Information, not present in PostBar.ClO. The
field AL is an address locator field which consists of 12
bars and appears immediately to the right of the Postal
Code. The Customer Information field follows and this has
33 bars. These fields are encoded according to
alphanumeric Table 2 and so there are 4 characters for the
AL field and 11 for the Customer Information field.
CA 02202139 1999-10-13
12
Reference should be made to U.S. Patent No. 5,420,403
issued on May 30, 1995 to Canada Post Corporation for a further
explanation of the AL and Customer Information fields. More
particularly and in brief, the AL field, referred to in the
earlier application as PODI (Point of Delivery Indicator) is a
suffix to the postal code which is determined from the address
on the mail piece as well as the postal code. The postal code
together with the AL allows a mail piece to be sorted for
delivery to the specific address. The term POCI (Point of Call
Identifier) has been coined for the combination (Postal Code +
the Address Locator).
It is noted that the RS Parity field in PostBar.D22
consists of only 12 bars in contrast to the 30 bars of
PostBar.ClO. This is because more protection is needed for
PostBar.ClO than for PostBar.D22. This results from the fact
that the PostBar.ClO is a code printed by CPC on mail pieces
which have a great variety of surfaces and background and so
there is a likelihood of background noise from extraneous
printing or marking. On the other hand PostBar.D22 is applied
by the customer who has greater control over the printing
surface and so there is less potential for background noise.
From a consideration of Table 2 it can be seen that,
for the specific example shown for PostBar.D22, the AL is 1420,
and the Customer Information is CFFMIPLXF6V. From a
consideration of Table 1 the postal code converts to L3B 4T9.
Figure 4b shows how the Customer Information field of
Figure 4a may be broken down into sub-fields. In Figure 4b the
bars are not shown. The customer data can be broken into sub-
fields such as those shown. The Product Code identifies the
specific customer, the Sequence Number identifies the batch
mailed on a particular day and the Month and Day of Month are
self-explanatory. This
CA 02202139 1997-04-08
WO 96/13803 PCT/CA95/00606
13
information uniquely identifies a mail piece and allows
track~and trace of the mail piece as well as revenue
accounting fvr example.
The numbers in the brackets represent the number
of combinations possible for each sub-field.
Figure 5 illustrates an example of an
International or Global code, PostBar.Gl2 which would be
used when the mail piece is addressed to another country..
This is a (15,11) Reed-Solomon code over GF(64). The
format may be summarized as follows:
DATA FIELD BARS DATA CHARACTERS
Start /synchronizat ton 2
Data Content Identifier (DCI) 3 Z
Country Code (CC) 6
Postal code* 24 ZZZZZZZZ
RS Parity Check 12
Stop/synchronization 2
Total 4g
* Unused characters in the postal code field will
be filled with space characters.
The DCI is determined from Table 2 to be 1 and
this specifies that there are 11 decodable characters that
follow in the form of a three numeric character country
code (NNN) and an 8 character postal code (ZZZZZZZZ).
It is noted that in this code no A or N
characters of Table 1 are used for the Postal Code. Also,
a new field, namely Country Code, is present and as can be
seen by consulting Table 1, for the specific example shown
this translates to 180 which may, for example, identify the
USA. The postal code or zip code is determined from Table
2 to be 91266 followed by three spaces. For the U.S.A.
only 15 bars are needed for the ZIP code but the field is
provided with 24 bars because other countries require more
than 5 characters for the postal code.
Figure 6 illustrates an example of a customer
applied service code, PostBar.S21 which is a (25, 21) Reed-
Solomon code over GF(64) having a data structure summarized
as follows:
CA 02202139 1997-04-08
WO 96/13803 PCT/CA95/00606
14
DATA FIELD BARS DATA CHARACTERS
Start /synchronizat ion 2
Data Content Identifier (DCI) 3 Z
Bar Code Sequences (HCS) 3 Z
Service Information (SI) 57 ZZZZZZZZZZZZZZZZZZZ
RS Parity Check 12
Stop/synchronization 2
Total 79
As for PostBar.Gl2 discussed above all the data
characters are Z characters obtained from Table 2. The DCI
is determined from Table 2 to be S and this specifies that
there follows as data a 19 character (57 bars) Service
Information field which in this case translates to
ABCDEFGHIJ123456789 from Table 2. There is no routing data
field because this code is used for special services
required by a customer. For example the Service
Information field could be used for return mail management
or to provide other information useful to the customer.
Between the DCI field and the Service Information
field is a Bar Code Sequences (BCS) field which is a single
character consisting of 3 bars that allows the
concatenation of two bar codes to encode data longer than
19 characters. When a single 19 character code is used the
BCS is DDD which from Table 2 is 0. To indicate the first
of two concatenated bar codes the BCS would be chosen to be
1 and to indicate the second of two concatenated bar codes
the BCS would be chosen to equal 2.
The operation of the error correcting code (ECC>
for PostBar.ClO (Figure 3) and for PostBar.D22 (Figure 4a)
will now be discussed in greater detail.
The error correcting code (ECC) for PostBar.ClO
protects the postal code and DCI but not the machine ID.
The ECC is a (16, 6) Reed-Solomon code defined over the
field GF(64) with 64 elements. Precisely, the defining
roots of the code are ai for i = 1, 2, ..., 10 where a is a
root of X6+X+1. Each codeword consists of 6 message (or
information) symbols and 10 check symbols. Each symbol is
an element of GF(64) and is represented by 3 bars. The ECC
CA 02202139 1997-04-08
WO 96/13803 PCT/CA95/00606
can correct up to t symbols with errors and a erased
symbols as long as 2t+e~10. For example, since each symbol
corresponds to 3 bars, an erasure of 30 consecutive bars is
correctable. One should be aware that if there are e=10
5 erased symbols then there is no way for the code to detect
any additional errors. Any other error in addition to
these 10 will force a decoding error. (The constant erase
max in the software can be set less than 10 to stay away
from this possibility.)
10 The error correcting code for PostBar.D22 covers
all of the fields except the start and stop bars. The code
is a (25, 21) Reed-Solomon code defined over GF(64). It
can correct t errors and a erasures in the symbols of the
code as long as 2t+e<_4. As before, each code symbol
15 corresponds to 3 bars. The code uses 4 check symbols which
contribute 12 bars to the code.
The error correcting code specified for each of
the bar codes is a Reed-Solomon code over the field GF(64)
with 64 elements. We use a primitive element a of the
field GF(64) which is a root of X6+X+1 (over GF(2)). This
means that the 63 powers ai, for i=0, 1, ..., 62 are the 63
distinct non-zero elements of the field. Also the 6
elements a0, al, a2, a3, a4, a5 form a linear basis for the
field GF(64). Thus each element w of Gf(64) has a unique
expression as a sum,
(*) w = w5a5 + w4a4 + w3a3 + w2a2 + wlal + w0a0
where each wi = 0 or 1. By using the identity a6 - a + 1
any power of a can be expressed in the form (*).
The translation from bar to field elements is
accomplished by grouping the bars in sets of three. Each
bar corresponds to a pattern of 2 bits:
H = 00, A = O1, D = 10, T = 11
A set of three bars corresponds to 6 bits which
we take as the values of wi in the expression (*). So for
example,
TDT--r 11 10 11-1 lay + la4 + la3 + Oa2 + lal + la0 = a21
CA 02202139 1997-04-08
WO 96/13803 PCT/CA95/00606
16
Table 3 displays the correspondence between bar
patterns and field elements. In the encoding and decoding
software the field elements are represented as integers in
the range 0 to 63, (thus as 6 bits). For example, the
element a21, above, which has bit pattern 111011
corresponds to the integer 59 which is 111011 in binary
(59=32+16+8+2+1). In Table 3, the column int gives the
integer corresponding to each field element in this way.
TABLE 3
bars i ai int bars i ~ int
HHH ** 000000 0 DAA 31 100101 37
HHA 0 000001 1 HDA 32 001001 9
HHD 1 000010 2 AHD 33 010010 18
BAH 2 000100 4 DAB 34 100100 36
HDH 3 001000 8 HDT 35 001011 11
AHH 4 010000 16 .AAD 36 010110 22
DHH 5 100000 32 DTH 37 101100 44
HHT 6 000011 3 ADT 38 011011 27
HAD 7 000110 6 TAD 39 110110 54
HTH 8 001100 12 DTT 40 101111 47
ADH 9 011000 24 ATA 41 011101 29
THH 10 110000 48 TDD 42 111010 58
DHT 11 100011 35 TAT 43 110111 55
HAA 12 000101 5 DTA 44 101101 45
HDD 13 001010 10 ADA 45 011001 25
AAH 14 010100 20 THD 46 110010 50
DDB 15 101000 40 DAT 47 100111 39
AHT 16 010011 19 HTA 48 001101 13
DAD 17 100110 38 ADD 49 011010 26
HTT 18 001111 15 TAB 50 110100 52
ATD 19 011110 30 DDT 51 101011 43
TTH 20 111100 60 AAA 52 010101 21
TDT 21 111011 59 DDD 53 101010 42
TAA 22 110101 53 AAT 54 010111 23
DDA 23 101001 41 DTD 55 101110 46
ABA 24 010001 17 ATT 56 011111 31
DHD 25 100010 34 TTD 57 111110 62
HAT 26 000111 7 TTT 58 111111 63
HTD 27 001110 14 TTA 59 111101 61
ATH 28 O1I100 28 TDA 60 111001 57
TDB 29 111000 56 THA 61 110001 49
THT 30 110011 51 DHA 62 100001 33
CA 02202139 1997-04-08
WO 96/13803 PCT/CA95l00606
17
For the CPC internal bar code, PostBar.ClO, the
56 bars are arranged as follows:
b~ b?b~ b5pb51b52b53 b54b55
start coded portion machine ID stop
The coded portion is divided into blocks of three
bars. Each block represents one element of the field. The
ECC runs from right to left across the bars. We set
ci b47-31b48-31b49-31'
Thus we have:
b b b b b b b b . ...b b b b b b b b b b b b
~2 3 4 ~ ' 44 45 46 47 48 49 50 51 52 53 54 55
s~r't c15 c14 c1 c0 machine ID stop
Using these 16 elements c0, ..., c15 of GF(64)
the ECC is defined by specifying that a codeword must
satisfy:
(**) ~ ciaij = 0 for j = 1, 2, ..., 10
1=0
The equation represents 10 equations with 10
unknown coefficients which is solved by the computer bar
code generating software.
Using the symbology defined above, we record the
postal code (PC) in bars b5 ...b19 hence in elements c14'
..., c10. The DCI goes in bars b2b3b4 hence in c15. The
check symbols c0, ..., c9 are now uniquely determined by
the parity checks (**).
For example, DCI=Z, postal code K1S 5B6, mach ID
- DHAH encodes to the following codeword:
18 29 12 5 14 27 52 54 4 6 8 33 9 6 20 41
c0 ... ... C15
Table 2 then produces the bar code
AT DDA AAH HAD HDA DHA HDH HAD HAH TAD
TAH ADT HTD HAA HTH ATA AHD DHAH AT
Reorganized into A- and N- fields this is
CA 02202139 1997-04-08
WO 96/13803 PCT/CA95/00606
18
AT DDA AAH HA DHD AD HAH DH
Start DCI Postal Code -ANANAN
HAD HAH TAD TAH ADT HTD HAA HTH ATA AHD DHAH AT
~~,-~ ~-,r'
checks mach ID stop
The Domestic Har Code, PostHar.D22 is similar in
definition to the CPC Internal code. All of the 79 bars of
the Customer Code, except for the 4 start/stop bars are
covered by the ECC. Again the bars correspond to field
elements in sets of 3. Thus field element ci=b74-31b75-
31b76-31' We have:
b b b b b b b b ....b b b b b b b b
0 1 2 3 4 5 6 7 ' 71 72 73 74 75 76 77 78
start c24 c23 ..... cl c0 stop
Using these 25 elements c0, ..., c24 of GF(64)
the ECC for the Customer Code is defined by specifying that
a codeword must satisfy:
24
(***) ~ ciai~ - 0 for j = 1,2,3,4
1=0
This equation represents 4 equations with 4
unknown coefficients which is solved by the computer bar
code generating software.
Using the symbology defined above, we record the
DCI in bars b2b3b4 hence in the element c24. The postal
code is placed in bars b5 to blg hence in the elements c23'
... c19. The Address Locator (AL) goes in bars b20, ..'
b31 hence in c18' ~~~, c15' The customer field goes in
bars b32, ..., b64 hence in c14, .~., c4. The check
symbols c0, ... c3 are now uniquely determined by the
parity checks (***),
For example, DCI=C, Postal Code=M4J 3W8, AL-1420,
Cust field=ABCDEFGHIJK encodes the following codeword:
30 23 4 17 16 10 9 8 6 5 4 2 1 0 42 49 52 48 10 10 9 21 02
c0 ... ...c24
Using Table 3 to change from integer representation to bars
CA 02202139 1997-04-08
WO 96/13803 PGT/CA95/00606
19
produces the bar code=
AT HHD HHH AAA HDA HDD HDD THH TAH THA DDD HHA HHH
HHD HAH HAA HAD HDH HDA HDD AHH AHA HAH AAT ATD DDH AT
This breaks down into A-, N-, and Z-fields as:
AT HHD HHH AA AHD AH DDH DD THH TAH THA DDD
Start DCI Postal Code-ANANAN Address Locator
HHA HHH HHD HAH HAA HAD HDH HDA HDD AHH AHA HAH AAT ATD DDH AT
Customer Field checks stop
The checks do not follow any of the Table 1 or 2
symbologies but are simply field elements coded as in Table
3.
It is noted that in a (16,6) Reed-Solomon code
the probability of a random pattern being a valid codeword
is p~3.78x10 6. Moreover, for PostBar.ClO the letters
D,F,I,O,Q, or U currently do not appear in the bar codes
and W or Z do not appear as the first letters of the code.
There are 64 possible 3 bar system patterns, and only 20
are used for postal code letters. The digits for the
postal code are encoded as 2 bar patterns, and only 10 of
16 are used. This gives a probability of:
18 x 10 x 20 x 10 x 20 x 10 _ , 0067
64 16 64 16 64 16
or about ~ of 1$ that a random sequence of bars is a valid
postal code. Combining this with p above gives a
probability of 2.5x10 8 or 1 chance in 40,000,000 that a
random string of bars will be interpreted as a valid postal
code. Other internal checks, such as the use of the code
type, will reduce this probability even further. This
information should be incorporated into the OCR software.
Figures 7 through 11 respectively illustrate the
format of PostBar.D07, D12, S06, S11 and G22. These
structures will not be described herein as they will be
readily understood from the foregoing description.
It should be understood that the inherent
flexibility of the new code permits of many more
CA 02202139 1997-04-08
WO 96/13803 PCT/CA95/00606
applications than described and illustrated herein and the
particular applications described are to be considered
representative only.
Furthermore, it is envisaged that data
5 compression techniques may be used to accommodate longer
messages than currently provided for with PostHar.D07, D12
and D22. Data compression could also be used with the G
and S codes.
Where data compression is used, it is likely the
10 DCI will not be compressed so as to allow speedy
determination of the make-up of the bar code. An example
is the case of a service bar code present on a mail item
that is being processed for sortation. As there is no
sortation data in S codes, once the DCI is derived, the
15 machine logic knows that no further decoding is required to
process and decompress the data.
Suitable software listing for encoding of
PostHar.ClO is provided on Appendix A attached hereto and
the software listing for encoding of PostBar.D07, D12 and
20 D22 is provided on Appendix B attached hereto. Appendix C
attached hereto is suitable software listing for decoding
PostHar.ClO and Appendix D attached hereto is the software
listing for decoding PostBar.D07, D12 and D22.
