Note: Descriptions are shown in the official language in which they were submitted.
- 2~3~ ~3
BACKGROUND OF THE INVENTION
The present invention generally relates to the representation
of data in machine xeadable form, and more particularly to a
method and apparatus for encoding and decoding data into a two-
dimensîonal grapnic image, such as the two-dimensional bar code
PDF417, that can be au~omatically machine read to obtain the
encoded data in both open and closed systems.
In today's high-technology world, more and more operations
are being automatically performed by machines and systems. This
ever-increa~ing drive for automation ha~ resulted in a demand for
new techniques for encoding data into machine readable form for
automatic entry into the various systems and machinery. The data
ent7~ may be for such uses as data transmission, operating various
machine functions or the identification of persons or items. The
various media that carry the data for automatic ent~y include
punch cards, magnetic tapes and discs and magnetic stripes on
cards such as credit cards and badges. The systems utilizing the
above carriers are in "clossd" systems, i.e., the read function is
performed within an apparatus or housing and the reading element
-- 2 --
' ' ~ ' .
. , .. . . , . -
: -
'
2~31~3
is in contact or in near-contact with the carrier means during ~he
reading operation.
One method for representing data in a machine readable form
is ~o encode the data into a pattern of indicia having parts of
different light reflectivity, for example, bar code symbols. A
bar code symbol is a pattern comprised of a series of bars of --
various widths and spaced apart from one another by spaces of
various widths, the bars and spaces ha~ing different light
reflective properties. The bars represent strings of binary ones
and the spaces represent strings of binary zeros. Generally, the
bars and spaces can be no smaller than a specified minimum width
which is called a ~'module" or "unit." The bars and spaces are
multiples of this module size or minimum width.
~ ar code symbol5 are typically printed directly on the object
or on labels that a~e a~tached to the ob~ect. The bar code
symbols are read by optical techniques, such as scanning laser
beams or CCD cameras, and the resulting electrical signals are
decoded into data representative of the symbol for further
processing. Bar code reading systams are known as open~' systems
in that the carrier while being read is not sealed, but is read
from a distance and without being in physical contact with the
scanner.
~ he conventional bar code described above is "one-
dimensional" in that the info~mation encoded therein is
represented by the width of the bars and spaces, which extend in a
single dimension. Thus, a bar code of a supermarket item, for
example, consists of a string o~ ele~en digits ~hich represent an
, . ., . ~ ~ , . . ~ .. . . .... . . . . . .
2~3~03
identifying number, but not a description of the item. The
remainder of the relevant information, such as the price, name of
the product, manufacturer, weight, inventory data, and expiration
date, must be obtained from a database using the identification
number. Similarly, data encoded onto o~her mledia such as credit
card magnetic stripes is composed of one or more "one dimensional~
tracks of encoded data.
The use of bar code symbols and magnetically encoded data has
found wide acceptance in almost ev~ry type of industry. ~owever,
the one-dimensional nature of the encoded data limits the amount
of information that can be encoded and hence use has been
generally restricted to simple digital representations.
There is an increasing need, however, or a system to encode
data in machine readable form that allow~ for an increase in the
amount of data encoded into a given space that can be quickly and
easily decoded for further processing. In particulax, there is a
desire to create ~'portable data files" which provide more than an
identification number which is then used as an index to referenc2
a database. The ~portable data fila~l approach is well-suited to
applica~ions where it is impractical to store item information in
a database or where the database is not readily accessible when
and where the bar code is read. For example, information such as
the contents of a shipping mani~est or an equipment maintenance
history could be carried dixectly on the ob~ect without requiring
access to a remote database. Similarly, a hospital could use
portable data files to put more~medical information on patient
identification bracelets. In a manufacturing environment,
-- 4 --
. , .. , ~. ~-. ~ ,.. . . - - . . . . . .
2~631~3
portable data files could be used to keep production records or
even to provide instructions to con~rol machine operations.
Ideally, such portable data files could contain up to several
hundred or more characters in a relatively small area~ but still
be read from a distance by a hand-held laser scanner.
One approach or increasing the information in machine-
readable symbols i5 ~0 reduce the height of the bar codes and
stack the bar codes one on top of each other to create a ~stacked~'
or "two-dimensional~ bar code. A major problem in reading two-
dimensional symbols, however, is the loss of vertical
synchronization. As shown in Figure lA, if the data rows are too
short or the scan line intersects the row at a large angle/ the
scan lines will not coincide with the horizontal lines of the
pattern. The height of the rows can be increased as shown in
Figure lB, but this causes an obvious reduction of in~ormation
density.
A proposed solution to the vextical synchronization problem
is to include both row identifiers and local row discriminators in
the two dimensional bar code symbol in order to distinguish
between the rows. One such two-dimensional bar code with row
identifiers and local row discriminators is PDF417, which was
developed by S~mbol Technologies, Inc. A more complete
description of PDF417 is contained in U.5. Patent Application
Sèrial No. 0~ ~ 1,881r~iled January 5~ 1990, and assigned to the
same assignea as the present inven~ion, which is hereby
incorporated by reference.
6 ~ ~ / '
~ /oo
G~ 3~ -
. . .
'
.
.. : .
2~3~33
Even if ~he symbol is constructed so tha~ the rows can be
distinguished from one another, however, there xemains the problem
of how to decode such a symbol sficiently. In particular, it is
no-t enough for a decoding me~hod or apparatus to simply recognize
that a scan line crossed a row boundary.
SI~MARY OF_THE INVENTION
Accordingly, the present invention is direGted to a system
for representing and recognizing data in machine readable graphic
image form having an incrPased capacity for encoded information
that can be used in both open and closed systems. The system
comprises an encoding means having a means for entering data such
as a keyboard or optical character ~canner. In addition, the data
may be obtained directly from computer files. Tha data entered
into the system may be both textual data and control data. The
data is entered into a processing means or encoding the data into
a two-dimensional pattern of graphic indicia.
The graphic indicia may, for example, be in the form of a
two-dimensional bar code which is comprised of a pattern of
vertical bars of pxedetermined lengths that are spaced at various
vertical and horizontal intervals. The two-dimensional bar code
sym~ol, which may be a PDF417 3~mb01, pxeerably includes a
plurality o ordered, ad-jacent rows of codeword~ o bar-coded
information from a set of codeword~, the set of codewords being
partitioned into at least three mutually exclusive clu~tersj each
row in the symbol having at lea~t one row indicator codeword and
containing only codewords from a cluster different from the
-- 6 --
. . . .~, ., ... ~ -- . ; . - . - , ";
, - ,;
.
., .: , . - : . . .
2~3:~3
codewords in an adjacent row. It shoul~ be understood, however,
that the graphic indicia representative of the data is not limited
to two-dimensional bar codes such as PDF417, but may be in the
form of any two-dimensional graphic pattern of indicia suitable
for encoding data.
The processing means generates electrical drive signals for
transferring the two-dimensional graphic pattern onto a d~ta
carrier means, that may be a card or document or the surface of a
machine part. The encoding means also includes means for
transferring an image of the ~wo-dimensional pattPrn of graphic
indicia onto the data carrier means in response to the transfer
drive signals. ~he image may for example be printed in the form
of a two-dimensional pattern of graphic indicia having different
areas of light reflectivity in which the indicia have one level of
reflectivity and the spaces have another level of reflectivity.
In this embodiment, the converting means may be a type of optical
scanner typically used for scanning one-dimensional bar codes that
converts the areas of different light reflectivity into electrical
signals representative of the indicia. Scanners employed in the
present invention, however, have the added feature of scanning the
indicia in two dimansions. For example, in one me~hod a laser
light beam is scanned across the indicia in a raster pattern for
reading and decoding two-dimensional graphic codes. Optical
scanners suitable for reading two-dimensional patterns are
disclosed in U.S. Patent Application Serial Nos. 317,433 and
317,533, filed March 1, 1989, assigned to the same assignee as the
present invention and incorporated herein by r~ference.
,, , , ' , " , ' , .
' ,' ', .' . ' ' ", ' '. , , ' ' ' ~, , . ' . . ~ , '
. ' . .' . .. .
.. . : .
. . - . . . . .
2~3~
The system of the present invention further includes
recognition means comprising means for converting the image on the
carrier means into electrical signals representative of the
graphic indicia and means for decoding the electrical signals into
output signals representative of the data.
Where the converting means is a hand-held laser scanner, in
order to decode the electrical signals representing the graphic
indicia efficiently, the decoding means should be able to decode
the signal~ even though the scan lines cross a row boundary. In
particular, whare ~he graphic indicia is a two-dimensional bar
code symbol, such as PDF417, which has both row indicators and
local row discriminators, the electrical signals obtained from
scanning the symbol may be decoded in such a way that partial
scans from different rows can be stitched together. This allows
greater scanning angles and lower aspect ratios of the rows, which
in turn makss possible hand-held la3er Rcanning of two-dimensional
bar code symbols.
Accordingly, the decoding means for decoding the two-
dimen ional bar code symbol, in accordance with the invention,
compxises: means for scanning the two-dimensional bar code symbol
to produce scan lines of data representing the bar-coded
information in the codewords of the symbol; means for decoding a
scan line of data into a vec~or of codeword values corresponding
to the codewords that were scanned, at least one of the values
being for a row indicator codeword; means for assigning a row
number to each of the codeword values in the vector bassd on the
value of th~ row indicator codeword and th2 clus~er of the
.' ~
.. ' . ' " .
:
- 2~3~ ~
codeword; and means for filling in a codeword matrix with the
codeword values in the vector according to their assigned row
numbers.
In a two-dimensional bar code symbol such as PDF417, the row
indicator codewords may also contain information regarding the
number of rows in the symbol and the number of codewords in each
row. Where this is the case, one embodiment of the decoding means
includes both means for decoding a scan line of data to obtain a
codeword value for a row indicator codeword, and means for
determining either ~he number of rows or ~he number of columns
from the codeword value corre~ponding to a row indicator codeword.
The two-dimensional bar code symbol may also contain one or
more error correction codewords. Another aspect o~ the decoding
means o~ the invention therefore includes means or locating in
the matrix the codeword values for any codewords that have not
been successfully decoded, and means for correcting any erroneous
codeword values in the codeword matrix using the error correction
codeword.
The decoded output signals are available for further
processing and the 3ystem may therefore include means for
outputting the decoder output signals. TypicaL output devices may
include a liquid cryskal display, a CRT display and a printer.
The outputted signals may also be transmitted to a computer or
other system for further processing and use via telephone lines
using a modem or via a data bus. The present invention
contemplates the outputting of the decoder output signals to a
microprocessor for controlling the operation o~ various machines
_ g
., ..,,. ~.,, , ~, , .. - -
, , :
. . ' ' ' '
,
2~631~
such as facsimile, VCR; microwave oven, robotic systems and
weight/price label scale devices.
In another embodiment of the invention, the processing means
encodes a first set of data into the two-dimensional pa~tern of
graphic indicia and generates first transfer dri~e signals for
transferring the two-dimensional pattern onto a carrier means.
The processing means also generates a second set of transfer drive
signals in response to a second set of data entered into the
system intended to be transferred to the carrier means in human
readable iorm. Thereafter, the transfer means trans~ers onto ~he
carrier means both the image of the two-dimensional graphic
pattern of indicia in response to the first ~ransfer drive signals
and the second set of data in human readable form in response to
the second transfer drive signals. Thus, the system provides
means for automatically representing data in both a machine
readable foxm and human readabla foxm onto a single carrier means.
In yet another embodiment of the invention, the data is
encoded and decoded using a keyed data encryption technique in
order to increase the secuxity of the da~a transmission. In this
embodiment, only the person haviny the encryption key will ~e able
to decode the graphic pattern.
The ~ystem of the present invention maximizes the use of
available space or encrypting da~a. In addition to being compact
in size, the system provides fox high secuxity in tha transmission
of information. Thus, ~he invention pro~ides a highly reliable
system for representing da~a in machine readable graphic form
having incxeased encoding capaci~y thereby substantially expanding
_ 10 --
.
,
''
2~3~3
applications for automatic data entry. In adclition, the invention
creates a new media for man-machine interfacing.
It is to be understood that both th~ foregoing general
description and the following detailed description are exemplary
and explanatory only and are not restrictive of the invention as
claimed.
The accompanying drawings, which are incorporated in and
constitute a part of the specification, illustrate an embodiment
of the invention and together with the gen~ral description, serve
to explain the principles of the invention.
BRIEF DESCRIPTION OF TH~ DRAWINGS
Figures lA and lB are diagrams illustrating the intersection
of scan lines with the rows of a two-dimensional bar code 9ymbol;
Figure 2 is a diagram illustrating one example of a codeword
in PDF417;
Figure 3 is a diagram illustrating the overall structure of a
PDF417 symbol;
Figure 4 i5 a table listing the number of error correction
codewords for a given security level in PDF417;
Figure 5 i5 a block diagram of the ~ystem of the present
invention;
Figure 6 is a psrspective view of an encoding means of the
system of the present invention;
Figure 7 is a perspective view of a recognition means of the
system of the present invention;
',
2~3~3
Figure 8 is a perspective view of a data entry device and
reader in which a key may be entered for encrypting and decrypting
data;
Figure 9 is a perspective view of a facsimile machine
incorporating the recognition means of the present invention;
Figure 10 is a schematic diagram of another em~odimen~ of
recognition means for scanning and decoding a two-dimensional bar
code symbol;
Figure 11 is a schematic block diagram of an embodiment of
the hardware apparatus of a low-level decoder for decoding a two-
dimensional bar code symbol;
Figure 12 is a flow diagram of the steps performed by the
low-level decoder for decoding a two-dimensional bar code symbol;
Figure 13 i~ a flow diagram of the steps performed by the
low-level decoder for de~ermining the dimen~ions and security
level of the symbol being scanned;
Figure 14 is a flow diagram of the steps performed by the
low-level decoder for searching a scan line of data for a start or
a stop pattern;
Figure 15 is a diagram illustrating the various width
measurements that are used for the "t-sequence" of a codeword;
Figure 16 is a flow diagram of the steps performed by the
low level decoder for decoding a scan line of data into a vector
of codeword values and their cluster numbers;
Figures 17A, 17Br and 17C are diagrams showing an example of
a codeword vector;
- 12 -
-
.~ ,
.: , ' .,, ' "' :
~3 ~ ~3
Figure 18 is a flow diagram of the steps performed by the
low-level decoder for decoding an individual codeword value and
its cluster number from the scan line data; and
Figures l9A and l9B together are a flow diagram of the steps
performed by the low level decoder in order to update the codeword
matrix using the codeword vector.
DESCRIP~ION OF_THE PREFERRED EMBODIMENTS
Reference will now be made in detail to the presently
preferred embodiments of the invention, examples of which are
illustratéd in the accompanying drawings.
Code PDF417
Before di~cussing the method and apparatus of the invention
or encoding and decoding data in machine readable graphic form,
such a~ the two-dimen~ional bar code PDF417, it i~ important to
understand the structure of the two-dimensional bar code symbol
itself.
Each PDF417 s~mbol is composed o~ a stack of rows of bar-
coded information. ~ach row in the symbol consists of a start
pattern, several s~mbol characters called "codewords,l' and a stop
pattern. A codeword is the basic unit for encoding a value
repre~enting, or associated with, certain numbers, letter~, or
other symbols. Collectively, the codewords in each row ~orm data
columns.
Both the numbex of rows and the number of data columns of the
PDF417 symbol are vaxiable. The s~mbol must have at least three
'
'
rows and may have up to ninety rows. Likewise, within each row,
the number of codewords or data columns can vary from three to
thirty.
Each PDF417 codeword consists of seventeen modules or units.
There are four bars and four spaces in each codeword. Individual
bars or spaces can vary in width from one to six modules, but the
combined total per cod~word is always seventeen modules. Thus,
each codeword can be defined by an eight-digit sequence, which
represents the four sets of alternating bar and space widths
within the codeword. This is called the "X-sequence" of the
codeword and may be represented by the sequence Xo,Xl,...X7. For
example, for an X-se~uence of "51111125", the first element is
five modules wide, followecl by five elements one module wide, one
element two modules wide, and the last element five modules wide.
This example is illustrated in Figure 2.
The set o possible codewords is further partitioned into
three mutually exclusive subsets called "clusters." In the PDF417
symbol, each row uses only one of the three clusters to encode
data, and each cluster repeats sequentially every third row.
Because any two adjacent rows use different clusters, the decoder
is able to discrimina~e between codewords from diferent rows
within the same scan line.
The cluster number of a codeword may be detexmined from its
X-sequence using the following formula:
cluster number = (XO - X2 ~ X4 - X~) mod 9
- 14 -
- ~ ' ' '
~3~
where ~mod 9" is the remainder after division by nine. Referring
to the codeword in Figure 2, the cluster number is calculated as
~ollows:
cluster number = (5 - 1 + 1 - 2~ mod 9 = 3
To minimize error probabilities, PDF417 uses only three
clusters, even though nine are mathematically possible. Thus,
each row uses only one of the three clusters 0, 3, or 6, to encode
data, with the same cluster repeating sequentially every third
row. Row O codewords, for example, use cluster 0, row 1 uses
cluster 3, and row 2 uses cluster 6, etc. In general, the cluster
number may be determined ~rom the row number as follows:
clu~ter number - ((row number) mod 3) * 3
There are 929 codeword value~ defined in PDF417. These
values are O through 928. Each cluster presen~s the 929 available
values with distinct bar-space patterns so that one cluster cannot
be confused with another.
Figure 3 is a block diagram showing the overall structure of
a PDF417 symbol. Each row of the symbol consi~ts of a start
pattern, a left row indicator codeword Li, data codewords di or
error detection/correction codewords Ci, a right row indicator
codeword Ri~ and a stop pattern. The minimum number of codewords
in a row is three, including ~ha left row indicator codeword, at
lea~t one da~a codeword, and ~he righ~ row indicator codeword.
- 15
:
2~31~3
The right and left row indicator codewords, which are discussed
further below, help synchronize the structure of the symbol.
The start and stop pa~terns identify where each row of the
symbol begins and ends. PDF417 uses unique start and stop
patterns. The start pattern, or left side of each row, has the
unique pattern, or X-sequence, of ~81111113~. The stop pattern,
or right side of each row, has the unique X-sequence of
"711311121".
Every symbol contains one codeword (the first data codeword
in row O) indicating the total number of codewords within the
symbol, and at lea~t two error-detection codewords CO and Cl.
These two error-detection codewords together form a checksum which
is two codewords long.
A PDF417 s~mbol can also encode data with error correction
capability. The level of error correction capability, called the
"security level," is selected by the user and ranges from O to 8.
This means, for example, that at level 6, a total of 126 codewords
can be eithex missing or destroyed and the entire symbol can be
read and decoded. Figure S is a table showing the relationship
between the Recurity level of the PDF417 symbol and the number of
error correction codewords Ci.
In addition to correcting or missing or destroyed data
(known as ~erasures~)t PDF417 can also recover from misdecodes of
codewords. Since it requires two codewords to re~over from a
misdecods/ one to detect the error and one to correct it, a given
security level can support half the number of misdecodas that it
can of undecoded codewords.
_ 16 -
.. . . ,,,, ~ . - . . .
.
:
- 2~3~3
The row indicator codewords in a PDF417 symbol contain
several key componen~s: row number, number of rows, number of
data column~, and security level. Not every row indicator
contains every component, however. The information is spread over
several rows, and the pattern repeats itself every three rows.
The pattern for encoding the infoxmation in ~he row indicator
codewords can be illustrated as follows:
Row 0: Lo (row #, # of rows) Ro (row #, # of col~unns3
Row 1: Ll (row ~, security level) Rl (row ~, # of rows)
Row 2: L2 (row #, # of columns) R2 (row ~, security level)
Row 3: L3 (row #, ~ of rows) R3 (row #, # of COl~LmI15 )
etc.
In other words, the left row indicator codeword Lo for the first
row O contains the row number (O) and the total number of rows in
the symbol. The right row indicator codeword Ro for row O
contains the row number (O) and the number of data columns in the
symbol, and so on.
Encoding data into a PDF417 symbol is ~ypically a two-step
proce~s. Fixst, data is converted into codeword values of O to
928, which xepresent the data. This is known as "high-level
encoding.ll The values are then physically represented by
particular bar-space patterns, which is known as "low-level
encoding."
. - 17 -
., , :~ . . . .
2~3~3
En_odinq~Decodinq Sy~stem
Referring now to Figures 5-7 in the drawings, Figure 5 is a
block diagram of the system 10 of the present invention for
representing and recognizing data in machine readable graphic
image form. System lO includes an encoding means generally
indicated by the reference numeral 12 and a recognition means
generally indicated by the re~erence numeral 14. Encoding means
12 produces a carrier means 16 containing at least a two~
dimensional pattern of graphic indicia 18. Carrier means 16 may
also contain human readable data 20. The two-dimensional pattern
of graphic indicia on carrier means 16 is recoqnized by
recognition means 14 to produce output signals representative of
the data encoded into the pattern 18.
Data to be txansferred onto carrier means 16 is ontered by
entering means 22 into the encoding means 12. The dat'~ en~ered by
entering means 22 may be both the data to be encoded into the two-
dimensional pattern of graphic indicia and the data to appear on
carrier means 16 in human readable form. Processing means 24
encodes the set of data to appear in pa~tern 18 into a ~wo-
dimensional pattern of graphic indicia and generates transfer
drive signals for controlling the transfer of the indicia onko the
carrier means 16. Transferring mean~ 26 transfers an image of the
two-dimensional pattern of graphic indicia onto carrier means 16
in response to the transfer drive signals. If human readable data
is also to be transferred onto carrier 16, the processing means 24
generates a second set of ~ransfer drive signals for controlling
the transfer of the human readable data onto carrier 16. A
- 18 -
.. . . , . . ~ . .
. -
. . ~ ... . . .
. . .
' ' ', ~ '
2~3~3
portion or all of the data to be encoded and the human readable
data may be transferred from a storage memory in processing means
24 or other computer files rather than being entered by means 22.
The carrier means 18 shown in Figures 5, 6, and 7 is
represented as being in the form of a card approximately the si~e
of a credit card. This type of card is illustrative only as the
carrier means 18 may be made of any material on which graphic
indicia may be transferred to, such as paper, etc.
Recognition means 14 includes converting means 28 that
converts the image on carrier means 16 into ~lectrical signals
representative of ths graphic indicia. Decoding means 30 decodes
the electrical signals into decoder output signals indicated at 32
that are representative of the data encoded into the pattern 18.
Figure 6 is a perspective view o one embodiment of encoding
means 12. In ~his embodiment, the entering means 22 of Figure 5
i~ shown in form of a keyboard 32 for entering alphanumeric and
graphic data into the encoding means 12. The embodiment of Figur0
6 is illustrative only as entering means 22 may take forms other
than a keyboard such as an optical scanning means for scanning
data directly from documen~s for entry into the encoding means 12.
Entering means 22 may also be in the form of various card readers
in which magnetically encoded inormation i5 scanned and converted
into electrical signals representative of the data.
Referring again to Figure 6, the processing means 24 of
Figure 5 is shown in the form of a processor and display u~it 34.
The data entered by keyboard 32 is transmitted to the processor
and display unit 34 for storage and processing. In addi~ion to
2~31~3
entering data, the keyboard 32 is also used for entering control
commands to effect operation of the processor unit 34.
The data entered by keyboard 32 is displayed on display
screen 36 and upon entry of a proper control command, is also
stored in memory. The data to be encoded into the pattern of
graphic indicia is stored in a first memory, in processor 34 and
the data, if any, to be transferred in human readable form is
stored in a second memory. Alternatively, ~he data may be stored
in a separate portion of a single memory. Upon the appropriate
control command from keyboard 32, the processor unit 34 encodes
the data in the first memory into a two-dimensional pattern of
graphLc indicia and generates first transfer drive signals
representative o the data stored in the first memory. The
processor unit 34 also generates second transfer drive signals
representative of the data stored in the second memory.
The processor unit 34 is shown in Figure 6 as being coupled
to a printer 38. The printer 38 is one form of the transferring
means 26 of Figure 5. Printer 38 transfers an image of the two-
dimensional pattern of graphic indicia on carrier means 18 in
response to the first transfer drive signals and prints the second
set of data in human readable form onto carrier means 18 in
response to the second transfer drive signals. In one embodiment,
the printer 38 prints the two-dimensional pattern in the form of
graphic indicia ha~ing different areas o light raflectivity, such
as the two-dimensional bar code described above. Printer 38 may
take other forms such as a means for printing the two-dimensional
pattern of graphic indicia with magnetic-ink. In such a device,
- 20 -
. .
.
. , " '
' '
.
3 ~l ~ 3
magnetic indicia are deposited on the carrier material in a two-
dimensional pattern that may be recognized by magnetic-ink
recognition sensors.
Turning now to Figure 7, the recognition means 14 includes a
card reader 40 which contains the converting means 28 and the
decoding means 30 of Figure 5. The converting means 28 may be a
bar code reader such as those disclosed in U.~. Patent Application
Serial Nos. 317,433 and 317,533, assigned to the same assignee as
the present invention and incorporated herein by reference. The
readers disclosed in the above patent applications are open system
devices designed to read an optically encoded two-dimensional bar
code and to convert the light reflected from the pattern into
electrical signals representative of the graphic indicia.
The card reader 40 ~ay also comprise a magnetic-ink
recognition device for reading and decoding magnetically encoded
data. These closed ~y~tem de~ices include a magnetic read head
that senses ~he change in reluctance associated wi~h the presence
of the magnetic-ink. The use of appropriate converting means that
corresponds to ~he particular data encoding ~echnology employed is
contemplated by the present invention.
The decoding means 30 decodes the electrical signals into
output signals representative of the data encoded onto carrier
means 18. The decoder output signals are outputted from the
recognition unit 40 to various output means 42. Figure 7 depicts
two examples of output devices, one being a display unit 44 and
the other a printer 46. Display unit 44 may be any suitable
display such as liquid crystal display or a C~T. The printer 46
- 21
- , . . . ., ~ .. . .. .
2~3~03
may be any print device such as a dot matrix printer, laser
printer, etc.
The system of the present invention maximizes the use o~
available space for encrypting data. ~he density of the encoded
data is such that for a two-dimensional bar code symbol, a minimum
of about 1600 characters can be encoded into a space o~
approximately 5" x lJ2". In addition to being compact in size,
the system provides for high security in the transmission of
information. For example, a sensitive message may be encoded onto
a document also containing non-sensitive material. This document,
the same as any document, can be copied, transmitted by facsimile,
etc., but only those with a recognition means of the present
invention will be able to "read" the sensitive portion. The
carrior means, being a single sheek o paper or a plastic credit
card type o card, is an inexpensive read-only-memory Ytructure
that facilitates data communication.
In another embodiment, the data may be encoded using a keyed --
encryption algorithm that may be accessed only by an encryption
key. As shown in Figure 8, the data entry means 47 contains the
keyed algorithm and upon entry of the key 4g, the data will be
encoded into a two-diniensional graphic pattern in a unique
coniguration. The unique configuration can only be read by a
reader 48 having the algorithm and only upon entry of the key 49
into the reader. Thus, a high degree of security may be provided
with the keyed encryption embodiment.
In addition, the recognition unit 40 may al~o transmit the
output ~ignals to a central processing unit locally or remotely,
- 22 -
- . . . ., ~ . , . . ~ , . ... . .
- .
'' : ' , . . ' '
,' ~
2~63 1 03
by ~or example a mcdem, for further use or processing by the CPU.
In this embodiment, the data encoded onto the carrier means 18 may
be control data in the form of machine operating instructions for
controlling a robotic system or to a security identification
system for performing such functions as unlocX:ing doors. In
connection with the use of the present invention in a robotic
system, it is contemplated that the two-dimensional graphic
pattern containing the control data be placed or printed directly
onto a machine part or part holder. A scanner coupled to the
machine tool reeds the pattern and -transmits the decoded
instruction to the control computer which in turn controls the
machining of the part in accordance with the control program.
Another example of the use of the present invention includes a
microwave food container where the two-dimensional graphic pattern
con~ains instructions automatically entering the recommended
cooking sequence. A further use may be in connection with placing
on roadway signs two-dimensional patterns containing geographic
location information tha~ may be read by a scanner in passing
vehicles for use with onboard computers.
The present inven~ion further contemplates the use of the
system of the present invention to encode control data containing
machine operating instructions on~o the carrier means in the form
of tnachine readable graphic indicia that may be inserted into the
machine to effect operation of the machine. Figure 9 is an
example of a facsimile machine 50 in which a document 52
containing human readable data 54 and a ~wo-dimensional pattern of
graphic machine readable indicia 56. The document 52 is inserted
- 23 -
,, , ' ' : ~
2~3~3
into the facsimile machine 50 the same as documents are normally
inserted for transmission. The machine 50 contains a converting
means for converting the two-dimensional image into electrical
signals and a decoding means for decoding the signals into output
signals operative to actuate the facsimile machine 50. The
pattern 56 may contain such information as the phone number of the
intended recipient of the memo 54 and the appropriat~ instructions
for automatically entering the phone number and actuating the
transmission process. Thus, where numerous messages are faxed to
a particular recipient, a supply of paper containing the phone
number of the recipient encoded in the two-dimensional graphic
indicia machine readable format may be maintained by the sender.
The tra~smission of messages to that recipient will be facilitated
by placing the message onto the pre-encoded paper and simply
inserting the paper into the facsimile machine. In addition to
simplifying and speeding the transmission process, the possibility
of sending highly sensitive information to an incorrect party will
also be eliminated.
- 24
,
,
2~31~3
Scanninq/Decodin~ AP~aratus
Referring now to Figure 10, there is illus~rated a further
embodiment of the recognition means 14 for scanning and decoding
graphic indicia in machine readable form, where that graphic
indicia is in the form of a two-dimensional bar code symbol such
as PDF417. As shown in Figure 10, the recogni.tion means 14
includes a host computer 112, which may ~e a personal computer, a
low-level decoder 114, and a hand-held laser scanner 116. Scanner
116 uses a laser light beam 118 to scan a two--dimensional bar code
symbol 120 in a raster pattern while a trigger 122 is pulled. A
laser scanner suitable for scanning a two-dimensional bar c:ode
symbol is disclosed in U.SO Patent Application No. 07/317,433,
filed March 1, 1989, and assigned to the same assignee as the
present invention, which is hereby incorporated by reference.
Electrical signals from laser scanner 114 are transmitted to
low-level decoder 114 where they are decoded into a matrix of
codeword values corresponding to the rows and coLumns of the two-
dimensional bar code s~ymbol. As explained in further detail
below, low-level decoder 114 may be embodied in a computer program
operating on a micro-computer separate from the host computer.
The low-level decoder is connected to the host computer by a
standard interface, such as an ~S-232 interface, ~or transmitting
the codeword values after they are decoded. Alternatively, the
low-level decoder 114 may be embodied entirely in hardware, or a
combination of a hardware and software, which is physically
located in either the ~canner itself or ~he host compu~er.
- 25 -
. . .
2 ~ Q 3
The matrix of codeword values from low-level decoder 114 is
decoded into usable data by a high-level decoder, which may be
embodied as a separate computer program operating on the host
computer 112. For example, PDF417 has three predefined modes and
nine reserved modes. The predefined modes are ~inary, EXC, and
Numeric. In the Binary mode, each codeword c~ln encode 1.2 bytes.
In the EXC mode, the alphanumeric data can be encoded in double
density ~i.e., two characters per code word), and in Numer.ic mode,
the numeric data can be packed in almost triple density.
Therefore, the high-level decoder in host computer 112 will
further decode the codeword values (0-928) from low-level decoder
114, depending on the mode, to obtain the actual data embodied in
the symbol. The decoded data from the high~level decoder may then
be used by a user application program also operating o~ the host
computer 112.
Low-~evel Decoder
Figure 11 is a schematic block diagram of one e~bodiment of
the hardware apparatus of low-level decoder 114 shown in Figure
10. In this embodiment, the low-level decoder i8 primarily
embodied in a computer program which is executed by a micro-
computer separate from the host computer.
As shown in Figure 11, the low-level decoder includes a
scanner interface 130 which receives the electrical signals from
the scanner. The electrical signals from the scanner may be in
the form of a digital signal which corresponds to the light and
dark elements of the symbol as it is being scanned. Scanner
- 26 -
2~31~3
interface 130 converts the electrical signals into a sequence of
integer v~lues representing the varying widths of the bars and
spaces and stores them in a buffer area of a memory 134. In order
to accomplish this, scanner interace 130 is connected to a
central bus 132 to which the other hardware elements of the low-
level decoder are also connected. Scanner interface 130 has
direct memory access (DMA) capability which allows it to store the
converted scanner data directly in the memory for decoding.
Low-level decoder also includes a central processing unit
(CPU) 136 and a second interface 138 for communicating with the
host compuker. The inter~ace to the host computer may be one or
more standard interfaces such as an RS-232 interface.
Figure 12 is a flow chart showing the sequence of operation
o~ the low-level decoder for decoding a two-dimensional bar code
s~mbol such as PDE'417 into a matrix o~ codeword values. The
various steps in the ~e~uence are embodied in a software computer
program which is stored in memoxy 134 and executed by CPU 136
shown in Figure 11.
In the first step 150 in Figure 12, the low-level decoder
initializes the scanner in~erface and initiates scanning o the
symbol. The actual functions performed in this step will depend
on the type of scanner and will involve various scanner dependent
routines to initialLze the scanner interface and to sta.rt
scanning.
In step 152, the low-level decoder a~tempts to determina ~he
dimensions and the security level of ~he symbol being scanned~
SpecificalIy, this step determines the number of rows, the number
_ 27 -
. ~ ~ . , ,.. . . ~ ..
~31~3
of data columns, and the security level of the symbol from theleft and right row indicator codewords. These dimensions are ~hen
used to initialize a two-dimensional codeword matrix and other
related parameters for decoding the symbol. Each location in the
matrix contains both a codeword value and an associated confidence
weight, which are initially se~ to a null or empty value. If the
dimens.ions and security level of the s~mbol cannot be det0rmined~
then the scan is abortedO This step will be di~cussed in further
detail below in connection w.ith Figure 13.
Continuing in Figure 12, step 154 i~ the first ~tep in a
control loop in which the rows of the two-dimensional bar code
symbol are repeatedly scanned and the codeword values are filled
into the codeword matrix. The steps of the control loop are each
repeated until the number o codewords remaining in the matrix
which have not been successfully decoded is small enough that rest
of the matrix can be determined using the built-in error
correction capability of the symbol. Thus, in step 154, if the
number of codewords which ha~e not been successfully decoded is
less than the error correction capability of the symbol based on
the security level (see Figure 4), an attempt is made to correct
the matrix using the error-correction codewords. If the attempted
error correction is successful, then in step 156, the control loop
i8 exited and scanning is terminated in step 158. Otherwi5e, if
the attempted error corxection is not successful, then the
following steps 160-164 are performed to try to decodQ additional
codewords to fill in the matrix.
- 28
.
~3~0~
First, step 160 searches a scan line of data obtained from
the buffer area of the memory for a start or a stop pattern. If
either a start or a stop pattern is found, then in step 162, ~he
low-level decoder attempts to decode as many codewords as possible
from the scan line. Specifically, the scan line of data is parsed
into individual codewords whose values and cluster numbers are
placed in a codeword vector ready for incoxporation into the
codeword matrix. Both steps 160 and 162 are discussed in further
detail below in connection with Figures 14 and 16, respectively.
The codeword vector produced in step 162 is analyzed and then
used to update the codeword matrix in step 164. In particular,
step 164 assigns a confidence weight to each codeword ~alue
depending on whether its nearest neighbors were also decoded. Row
numbers are also assigned to each codeword value based on the left
or right row indicator codewords and the corresponding cluster
number ~or the codeword. If the scan line crosses a row boundary,
the cluster numbers of the codewords can be used to determine the
correck row number for each individual codeword. For example, if
a decoded scan line has a left row indicator with row number 2,
and the cluster numbers of the following codewords are 5, 0, O, 3,
the codewords are accordingly placed in the following locations:
(row 2, column 1); (row 3, column 2); (row 3, column 3); and (row
4, column 4). In this way, a single scan line o~ data can contain
codewords ~rom more than one row, which can then be stitched into
the appropriate location in the codeword matrix. This step is
discussed in further detail in connection with Figures 19A and 19B
below.
- 29 -
..
2~31~3
Figure 13 is a flow chart showing in greater detail the
sequence of steps for determining the dimensions and securi~y
level of a symbol as referred to in step 152 of Figure 12 above.
In the first step 170 of Figure 13, the low-level decoder searches
a scan li.ne of data obtained from the buffer area of the memory
for a start or a stop pattern. This step is t:he same as step 160
in Figure 12 and is discussed in further detai.l in connection with
Figure 14 below.
Step 172 then decodes the first codeword immediately adjacent
to either the start or stop pattern found in the previous step.
As shown in Figure 3, this codeword wilL be either a left or right
row indicator codeword containing the row number and either the
number of row~, the nllmber o~ data columns, or the securlty level
o~ the symbol. If both a start and a stop pattern are ound, then
both the left and the right row indicators are decoded. The
sequence of steps for decoding an individual codeword are
discussed further below in connection with Figure 18.
Continuing in Figuxe 13, in step 174 the particular dimension
or security level encoded in the row indicator is extractecl from
the codeword value and the cluster number determined in the
previous step 172. For example, for a left row indicator codeword
with a cluster number of 0, the number of rows is extractecl from
the codeword value.
A confidence weight assigned to each of the dimensions and
the security level is initially set ~o 0. Ste~s 176-184 update
both the current value and the confidence weight of the dimension
or security level extracted in ~hP previous step in the following
- 30 -
..
' , ,
,
. . . , ... ... .. . . ' : '' .: . ' . ' ,
2~31 03
way. First, th0 particular parameter, say the number of rows, is
compared to the current value of the number of rows obtained from
previous decodes. If the current value of the number of rows and
the newly decoded value are the same, as determined in step 176,
then the confidence weight assigned to the n~ber of rows is
increased in step 178. If the current value 2~nd the newly decoded
value are different, however, then the confidence weight is
decreased in step 180. If the confidence weight assigned to the
particular parameter is decreased below zero as determined ln step
182, then the newly decoded value is substituted for the current
value and a new minimum weight is assigned to the parameter in
step 184.
Step 186 determines whether the confidence weight for all
three parameter3, i.e., number of rows, number of data columns,
and security level, exceeds a predetermined threshold. If so,
then the two-dimensional codeword matrix is initialized in step
188 based on the current values of the number of xows and the
number of columns. The number of correctable errors may al90 be
determined from the current value of the security level according
to the table in Figure 4. If all three confidence weights do not
exceed the threshold in step 186, however, then program control
raturns to step 170 to begin searching for the start and stop
patterns in a new scan line. Steps lrl0-184 are repeated until all
three parameters have been successfully decoded with a high degree
of confidence.
Figure 14 is a flow chart showing in greater detail the
sequence of s~eps for searching a scan line of data for a start or
- 31 -
-
.
.
.. . . .
: '
. '' ' : .
,
2~3~3
stop pattern as referred to above in step 160 of Figure 12 and
skep 170 of Figure 13~ Bxiefly, the search begins a~ the first
location of an individual scan line of data obtained from the
buffer area of the memory and is repeated at sequential locations
until either a match is found or the length of the scan line is
exceeded. When a ma~ch is found, an index is set to a location
immediately following or preceding the pattern for decoding the
adjacent code word.
As shown in Figure 14, the first step 200 sets an index to
the location of the data elements in the scan line to "1",
indica~ing the first da~a element or integer value of the scan
line. This index i5 used to identiy the first element of each
sequence o~ eight elements in the scan line for comparison to the
start and stop patterns.
Step 202 is the first step of an iterative loop for searching
the scan line from left to right for either a star~ or a stop
pattern. In this step, if the current index is less than ~he
length of the scan line, then the remaining steps are executed and
the search continues. Once the index exceeds the length of the
scan line, however, then the loop is exited and an indication is
returned signifying that the search ~ailed and a start or stop
pattern was not found.
Rather than using the X-sequence of codeword, the low-level
decoder decodes a symbol by using l~edge to similar edge"
measurements to compensate for ink spreading which occurs when
printing the symbols. Thus, in step 2G4, a raw "t-sequence" is
obtained from the ~can line by adding pair~ of consecutive integer
- 32 -
' ' :' ' .. ,: '.
.
.
,
,
'', ' '
2 ~ 0 3
values beginning at the location specified by the index.
Specifically, the r~w t-sequence, which corresponds to the seven
width measurements kl,t~,...t7 shown in Figure 15, is calculated
by adding pairs of ~he consecutive integer values Xo,Xl,...X7,
representing the widths of the bars and spaces, as follows:
tl = xo + Xl
t2 = Xl ~ X2
t3 = x2 + x3
etc.
A width W for the entire codeword is also calculated in step 204
by summing the eight integer values xO + xl + . . . + X7.
For the codeword in Figure 15, for exampl.e, the sequence of
integer values ~rom the ~can line, representing the widths of the
bars and spaces might be something like: 43, 19, 21, 19, 22, 18,
1~3, 96. The raw t-sequence tl,t2,...t7 would then be 62, 40, 40,
41, 40, 121, l9q, and the width W would be 341.
In step 206 in Figure 14, the raw t-sequence obtained in step
204 is normalized and rounded to integer values. Specifically, a
value for the codeword~s ~module~ or l'unit'~ is first established
by dividing the width W of the codeword by the total number of
units for each codeword. In a PDF417 symbol, each codeword is
seventeen units, so that the width W is divided by ~eventeen to
obtain the unit of the codeword. Thus t for the example in Figure
15, the unit would be (341/17) = 20Ø Each ~alue of the raw t-
sequence is then divided by the unit and rounded to an integer to
no~malize the t-sequence. The normalized t-sequence for the
codeword in Figure lS is 3~ 2, 2, 2, 2, 6, 10.
\
- 33 - ~
. . . -: . .
.
:
-. .
, . . . : . . :
~0~31~3
The normalized t-sequence i5 then compared to the t-saquences
of the start and stop patterns of the code in step 208. If the
scanner scans from both left to right and right to left, then the
t-sequence must be compared to the start and stop patterns in bo~h
their normal and reverse orientations.
If there is a match in step 210, then the index is set in
step 214 to a location in the scan line immediately following the
pattern if it is a start pattern or i~mediately preceding it if it
is a stop pattern. If the curren~ t-sequence does not match
either the start or the stop pattern, however, then in step 212,
the index is incremented by one and steps 202 through 210 are
repeated until either a match is found or the length of the scan
line is exceeded.
Figure 16 is a flow chart ~howing in greater detail the
se~uence o~ steps for decoding a scan line of data into a vector
o~ codewords and their clusters as referxed to in step 162 of
Figure 12 above. In decodlng ~he individual codeword values and
cluster numbers from the scan line, the low-level decoder begins
decoding at the start or stop pattérn and decodes as many
codewords possible~ For those codewords that are not successfully
decoded, the codeword values in the codeword vector are set to
'^ ~AD " .
At the completion of the sequence of steps shown in Figure
16, the codeword vector will contain certain codeword values and
cluster numbers in locations corresponding to the appropriate
columns of the codewords that were successfully decoded. Figure
17A shows an example of a codeword vector in which the codewords
- 3~ -
"' ' ' ' ' '
' " ~ '' ' '
.
2~3~ ~3
in eight of the ten ~olumns were successfully decoded. The
codeword values in columns 1 and 10 correspond to the left row
indicator codeword in row 2 (L2) and the right row indicator
codeword in row 1 (Rl), respectively. The codewords in columns 5
and 7 were not successfully decoded as indicated by the notation
"BAD" in ~hose locations of the codeword vector.
Returning to the first step 220 of Figure 16, an upper limit
on the number of codewords that may be decoded ("cwlimit") is set
equal to the number of column5 in the codeword matrix. If this
number of codewords is successfully decoded, then the decoding
process for the current scan line ls obviously complete.
Step 2~2 determines the direction of the scan if the scanner
scans from both left to right and right to left. If khe
particular scan was from left to right as detenmined in step 222,
then the column number of the first codeword is set to "1" in step
224 and the amount that it will incremented by ~"incr") each time
a subsequent codeword is decoded is set to "+1". If the scan was
from right to left, however, then in step ~26, the column number
of the first codeword in the scan line will be the last column of
the codeword matrix, and the incremental vaLue i9 set to "-l".
Step 228 is the first step of a control loop in which
individual codeword values and their cluster numbers are decoded
from the scan line of data. In step 228, the codeword limit is
tested to see if it is still gre ter than zero. If not, then all
of the codewords in the scan line have been decoded and the loop
is exited.
- 35 -
, ' ~ ~ ' . . '.:
2~3~3~
Otherwise, step 230 obtain6 the next codeword value and its
cluster number from the scan line. This step will be discussed in
further detail below in connection with Figure 18.
If the codeword decoded in the previous step is a valid
codeword as determined in step 232, then in ~t:ep 234 the codeword
value and its cluster number are saved in the codeword vector at a
location corresponding to the column of the codeword. The
codeword values thus placed in the codeword vector are reacly for
incorporation into the codeword matrix.
If the codeword decoded in step 230 is not a valid codeword,
however, then the codeword value in the codeword vector
corresponding to the current column is se~ to "BAD" in step 236 to
indicate tha~ this codeword was not successfully decoded. A ~BAD~
codeword is most likely to occur when the ~can line crosses the
boundary between two rows in the middle of the codeword.
Finally, in step 238, the current column number is either
incremented or decremented depending on the direction of the scan,
and the codeword limit is decremented by one. Steps 228-236 are
then repeated until there has been an attempt to decode all of the
codewords in the scan line.
Figure 18 is a flow chart diagram showing the sequence of
step~ corresponding to step 230 in Figu.re 16 and step 172 in
Figure 13 in which an attempt is made to decode an individual
codeword value and cluster number from the scan line. In the
fixst step 240, a raw t-sequence and the width W are obtained from
the scan line. This same step was discussed previously in
connection with step 204 in Figure 14.
- 36 -
2~1~3~3
In step 242, the width W of the eight elements presumed to be
the next codeword are compared to the width of the pre~iously
decoded codeword. If the current width W is not within a range o F
plus or minus a predetermined difference (delta), th~n there is
probably a split ~undercount by a multiple of two elements) or a
merge (overcount by a multiple of two element:s) error in the
current codeword. This codeword is not decoded further, but
rather in step 244 its value and cluster numher are both set ~o
BAD to indicate that it could not be decoded.
Then in step 246, an attempt is made to resynchronize to the
boundary o the next codeword by finding a t-sequence with a
corresponding width ~ that falls with.in a given tolerance of the
expected width of a codeword, basèd on the wid~h o~ the previous
codeword. I~ the current width W i9 significantly greater than
the expected width, indicating a po~sible merge error, then the
last two integer values are dropped from the t-sequ~nce until it
falls within the proper limits. Likewise, if the curxent wldth W
is significantly less than the expected width, indicating a
possible split error, the next two integer values in the scan line
are added to the t-sequence until it falls within the proper
limi~s.
If the current width W is within a certain tolerance of the
expected width, as determined in ~tep 242, then an attempt is made
to decode the codeword. In step 248, ~he raw t-sequence is
normalized as described above in connection with step 206 in
Figure 14. Then in step 250, ~he cluster number is determined
from the normalized t-~equence. The cluster number may bs
.. - ~ .
.
2~31 ~3
determined from the t-sequence (as opposed to th~ X-sequence
described above) as follows-
cluster number = (Tl - T2 + T5 - T6) mod 9
For codewords in PDF417, valid cluster mImbers are 0, 3, and
6. I~ in step 252 it is determined that the cluster number is not
0, 3, or 6, then the codeword is not valid. Accordingly, in step
254 the cluster number and value are set to ~BAD~ to indicate that
the codeword was not successfully decoded.
Otherwise, in step 256, the normalized t-sequence and its
cluster number are used to find the corresponding codeword value
in a look-up table. If no corresponding codeword val~e is found
for th~ t-sequence, then the codeword ~alue i9 ~et to ~'BAD~ to
indicate that it was not succe~sfully decoded.
Finally, in step 258 the "last width" value is updated to the
current width W of the codeword for use in decoding the next
codeword value from the scan line.
Figures 19A and l9B together comprise a flow chart of the
sequence of steps executed by the low-level decoder in order to
update the codeword matrix using the codeword vector. These
figure~ explain in greater detail step 164 in Figure 12 discussed
previou~ly.
The first step 260 of Figure l9A checks the first and la~t
values in the codeword vector to see i~ either is a valid row
indicator. If neither the first nor the last values in the
codeword vector are valid row indicatoxs, then in step 262, the
- 38 -
'
~ ., ', ,
2~$3~3
program exits the routine and no attempt is made to update the
codeword matrix using the codeword vector.
If a valid row indicator is present, howe~er, then in step
264 confidence weights are as~igned to each codeword value in the
codeword vector~ Specifically, a confidence weight is assigned to
each cod~word depending on whether its nearest neighbors and their
cluster were also decoded. For example, as shown in ~igure 17B,
the codeword ~alues in columns l, 2, 3, 9, ancl lO are assigned
high confidence weights ("H") because their in~ediate neighbors
were also successfully decoded and have the same cluster number.
The codeword values for columns 4 and 8 are assigned medium
confidence weights ("M") because one of their neighbors was
successfully decoded and has the same cluster number but the other
neighboring codeword value is ~BAD". The codeword value in column
3 is assigned a very low confidence weight ("L") because neither
o~ its neighbors was succe3s~ully decoded. Thus, the confidence
weight for a codeword value at column i in the codeword vector is
essentially a function of ~he cluster numbers of the codewords at
columns i - 1, i, and i + l. This function may be implemented by
a look-up table whos0 index is calculated from the cluster numbers
of the three codewords.
In step 266, a row number is assigned to each codeword value
in the codeword vector based on the row indicator codewords and
the cluster numbers. As shown in the example in Figure 17C, the
left row indicator codeword L2 indicates that the row number is 2
and the cluster number is 6. The cluster numbers for the codeword
values in columns 2-4 are also 6. Therefore, row number 2 is
39 -
- ~ . , , , " ~. . ..
~.
'
2 ~ 3
assigned to the codeword values in the first four columns of the
codeword vector.
Also in the example in Figure 17C, columns six and 8-10 all
have a cluster number of 3 and the right row indicator codeword R
indicates that the row number is 1. Therefore, it can be assumed
that the scan line crossed the row boundaxy between row 2 and row
1 and the codeword values in columns 6 and 8-10 should be assi~ned
to row 1.
Once the confidence weights and row numbers have been
hssigned to each of the codeword values in the codewoxd vector,
the codeword matrix is updated one codeword at a time. In step
26~, the column number C of both the codeword vector and the
codeword mat,rix is set is initially set ~o "1". Step 270 is the
first step of an Lterative loop which steps through the codewords
in the codeword vector and uses them to update the corresponding
codewords and their associated confidence weights in the codeword
matrix. When the column number C exceeds the number of columns in
step 270, then all of the codewords in the codeword vector have
been processed and the routine ands.
For each codeword in the codeword vector, 5t2p 272 sets the
row number R o the codeword matrix to ~he row number as~igned in
step 266 to the codeword in the codeword vector at the location C.
Thus, for each codeword value in the codeword vec~or, there is a
corresponding value in the codeword matrix at location [R,C].
Continuing in Figure l9B, step 274 determines whethex the
cuxrent codeword value in location ~R,CI in the codeword matrix is
the same a~ the corresponding codeword value in the codeword
- 40
,
.
2~3~3
vector at column C. If the values are the same, then in step 276,
the confidence weigh~ assigned to the codeword value in matrix
location [R,C] is increased by the confidence weigh~ of the
corresponding codeword value in the codeword vector. If not, the
confidence weight of the codeword value in the matrix is decreased
by the confidence weight of the codeword valule in the vector in
step 278.
If the confidence weight was decreased in step 278, then in
step 280 that confidence weight is tested to see if it was
decreased below zero. If the confidence weight is less than zero,
then in step 282 the new codeword value in the codeword vector is
substituted for the current codeword value in the corresponding
location in the codeword matrix. The confidence weight assigned
to the codeword value in ~he matrix is also changed to a positive
value in step 284.
Finally, in step 286 the colu~n number C is incremented by 1
for processing the next codeword value in the codeword vector and
program control is returned to step 270 for repeating steps 272
through 286 for all of the columns in the vector.
Returnin~ briefly to step 154 in Figure 12, each time after
the codeword matrix has been ~illed in with the new vector of
codewo.rd values and the confidence weights have been updated, an
attempt is made to fill in the rest of the matrix using the built-
in error correction capability of the symbol. The number and
location of codewords which have not yet been successfully decoded
may be determined by comparing the confidence weights assigned to
each of the codeword values in the matrix with a predetermined
- 41 - -
. . , ~' ~ , '
.
2B63~3
threshold. Those values having confidence weights below the
threshold are considered to not yet be decoded. If the numbe~ of
codewords not yet decoded is less than the error correction
capability of the symbol as determined by the security level, then
an attempt is made to correct the matrixO
It will be apparen~ to those skilled in the art that various
modifications and varia~ions can be made in the decoding me~hod
and apparatus without departing from the scope or spirit of the
invention. Other embodiments of the invention will be apparent to
those skilled in the art from consideration of the specifi.cation
and practice of the invention disclosed herein. It is in~ended
that the specification and examples bo considered as exemplary
only, with a true scope and spiri.t of the invention being
indicated by the following claims.
- 42 -
, . .
' ~
.:
