US 4,056,710 AGrant
System for Decoding Bar Code
Issue Date:1977-11-01
•3 Claims
•12 Drawing Sheets
Abstract
A system for decoding encoded character information characterized by a plurality of bars of alternating light reflective characteristics of one or more widths in applications such as reader/scanner systems utilizing a decision tree technique that enables decoding to take place on line in real time.
Metadata
Assignee
- Coherent Radiation
Inventors
- Robert C. Shepardson
- Michael E. Watts
Application Information
Application Number:US 6777155
Filing Date:1976-04-16
Priority Date:1976-04-16
Art Unit:235
Classifications
IPC:
G06K 708G06F 1534
Field of Search:
23534061.11 E;61.12 N;61.7 R146.3 K;146.3 F;146.3 Z
Patent Drawings (12 sheets)
Description
BACKGROUND OF THE INVENTION
The present invention relates to optical reader-scanner systems and, in particular, for improved means for processing data detected by a reader-scanner system.
Optical reader-scanner systems have achieved applications at automated supermarket check-out counters. A reader-scanner system operates as a data input system for electronic cash register systems and is used to read UPC (universal product code) symbols on the items.
The UPC symbol system was developed by the Universal Grocery Product Code Council, Inc., and is a bar code system which provides for binary coding of ten product identification decimal digits. The first five of these digits identify the producer of the item, and the last five identify the particular item of his product line. The actual symbol is comprised of about sixty parallel light and dark bars. Each of the ten digits used to identify the item is represented by a specific group of these bars and the actual encoding of the digit is obtained by variation in widths of bars making up this group.
In some cases, lesser numbers of digits are used and provisions have been made for utilizing greater numbers of digits for future codification. A complete description of the UPC symbol system may be found in a publication entitled "UPC Symbol Specification" dated May 1973 and published by Distribution Number Bank, 1725 K Street, N.W., Washington, D.C.
The reader-scan system contributes to the efficiency and convenience of the operation of automated check-out counters by allowing the UPC symbols to be read automatically as a package is manually transferred from the counter, across a scan pattern area or window.
In automatic electronic cash register systems, the data covering such things as pricing, quantity or coupon discounting and taxable or non-taxable nature of the item are stored in a memory bank of a controller console. The controller is programmed so that the address of this memory bank location corresponds to digital information encoded in the UPC symbol printed on the package of the item.
Typically, the scan pattern system uses a very low-powered laser, such as a helium-neon laser, to provide a coherent beam of monochromatic light. This type of light source provides the high level signal-to-noise ratio necessary for processing that is unavailable from other sources. The laser beam is then directed to a scanner mechanism which generates an optical scan pattern at a window in the check-out counter. An example of such an optical scan system is disclosed in copending patent application Ser. No. 568,633, filed Apr. 16, 1975, entitled "Optical Scan Pattern Generator" of James L. Hobart and Wayne S. Mefferd, and assigned to the assignee of the present application.
The actual identification of the symbol is made by electronically analyzing the signals generated by the laser light beam that is reflected back from the package surface to an optical detector. The output of the detector then goes to electronic circuitry and is continuously analyzed for the UPC symbol coded content.
When the high speed movement of the light beam crosses the light and dark bars of a UPC symbol, a specific pulse train waveform is generated. The characteristics of this waveform are established by the width of the individual light and dark bars and by the speed of the sweep. If the electronic circuitry determines that the symbol is valid and positive identification of the symbol is made, the signal is passed onto the controller of the cash register system. This output signal provides the address for the memory bank location where the instructions, for billing and cash register-receipt recording of that symbol, are stored.
If the symbol is not valid, i.e. has been tampered with, altered or damaged, the positive identification cannot be made, a no-reading visual or audio alarm is sounded. This notifies the clerk that a visual identification and a manual cash register entry must be made.
In scanner-reader systems presently available, the validation and identification of the stream of light and dark bars does not take place in real time. By this it is meant that the electronic processing circuitry does not analyze the data on a one-for-one basis as it is received. Rather, data which is believed to be valid data is routed to off-line registers or other storage devices, where the data is analyzed by the processor. Simultaneously, on-coming data which may be valid is routed to other registers. Data remains in a register until the processor determines that it is either valid or invalid.
Depending upon the optical scanner system used and the position of a label as it passes the scanner window, it is possible that only one or a few scans will intercept the label. When this happens, it is important that the data stream be correctly processed to determine the label information or else the label will not be read.
In the prior art system previously described, the storage registers frequently fill up with information which, although originally thought to be good information, turns out to be invalid. For example, the register may be filled with signals reflected from print on the container surface. If the processor takes a longer time to determine the contents of each register than it takes to fill up the registers, and if all the registers fill up with invalid data, then a for a given scan, good data which is subsequently provided as the beam sweeps the label is lost. In the case described above, where only one or a few scans intersect the label, this results in the label not being read at all.
The foregoing data processing system has other disadvantages. Processing time is relatively slow since the processing time does not take place in real time. Also, data is frequently stored long after sufficient information is available to determine that it is invalid. Also, this approach involves relatively expensive and complex electronic circuitry for its implementation.
SUMMARY OF THE INVENTION
In accordance with the present invention a system is provided for decoding coded character information where each encoded character comprises a plurality of bars of alternating light reflective characteristics of one or more widths which includes means responsive to bar width and character information to determine in real time valid sequences of the information.
More specifically, means are provided for establishing a multiple level decision-making sequence which includes means for comparing incoming bar width and characteristic information with bar width and characteristic values allowable at that level of the decision-making sequence for the bar and characteristic information sequence developed to that point, means for failing any information sequence which is not allowable, and means for moving to the next and subsequent levels of the decision-making sequence so long as the information sequence is an allowable one, until the completion of the multi-level sequence at which time an individual character is uniquely defined.
BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 is a block diagram of the improved decoder of the subject invention utilizing a decision tree technique.
FIG. 2A is the UPC standard symbol; and FIG. 2B is the UPC character structure for the characters shown in FIG. 2A.
FIGS. 3A and 3B are a detailed graphical illustration of the digit tree starting with white shown in FIG. 1.
FIGS. 4A and 4B are graphical illustrations of the digit tree starting with black shown in FIG. 1.
FIG. 5 is a detailed graphical illustration of the edge guard bar tree and center pattern bar tree shown in FIG. 1.
FIG. 6 is a detailed graphical illustration of the funny tree shown in FIG. 1.
FIG. 7 is a block schematic diagram of one implementation of a decoder utilizing the decision tree technique of the subject invention for UPC applications; and
FIGS. 8A, 8B, 8C and 8D are detailed schematics of the block schematic diagram of FIG. 7.
DESCRIPTION OF THE PREFERRED EMBODIMENTS
FIG. 1 is a block diagram of a decoder 10 for identifying information encoded in the form of a plurality of bars of alternating light reflective characteristics of one or more widths. For purposes of illustrating and describing the invention, the UPC code is hereafter used and described. However, the invention is equally applicable to other coding schemes and the invention is not limited to decoding UPC information.
Before explaining the operation of the decoder 10, a further description of the UPC is necessary. As explained above, for a complete description of this code, reference is made to the "UPC Symbol Specification."
FIG. 2A shows the UPC standard symbol. Among its characteristics are:
1. Overall rectangular shape, consisting of light and dark parallel bars (30 dark and 29 light for any 10-character code) with a light margin on each side. There are ten numeric characters.
2. Each character or digit of a code is represented by two dark bars and two light bars.
3. Each character is made up of seven data elements; a data element hereinafter is called a "module". A module may be dark or light.
4. A bar may be made up of 1, 2, 3 or 4 dark modules, as shown in FIG. 2B.
5. The symbol also includes two characters beyond the ten needed to encode the UPC;
i. One character, a modulo check character, is embedded in the right-most position of the symbol to ensure a high level of reading reliability.
ii. Another character, embedded in the left-most position of the symbol, shows which number system a particular symbol encodes.
6. Starting at the left side of the regular symbol following the light margin are edge or guard bars, followed by the number system character, followed by five UPC characters on the left side of the "center bar pattern", and then with the remaining five UPC characters on the right side of the center bar pattern, followed by the modulo-10 check character. Finally, the same guard bars are provided at the right side.
7. Dark modules represent 1's while light modules represent 0's. The number of dark modules per character on the left side is always 3 or 5 (i.e. odd) and the number is always 2 or 4 (i.e. even) for right-hand characters. This provides an "odd" and "even" parity encodation for each character.
8. Encoding is identical for all characters on a given side of the symbol, whether the character is part of the UPC number or is the number system character in the modulo check character.
9. The left and right guard bars are each encoded 101.
10. The center bar pattern is encoded 01010.
11. Encodation for the regular UPC characters (Version A) is given in the following table:
For purposes of describing the invention, only the Regular Version, or Version A, and the Zero Suppression, or Version E, of the UPC are considered. Once again, however, the subject invention is applicable to all versions of the UPC.
The zero suppression version of the symbol is included to facilitate source symbol marking on packages that would otherwise be too small to include a symbol. This is achieved by encoding the symbol in a special way that leaves out some zeros that can occur in the UPC code. For example, code 56700-00089 can be encoded as 56789, effectively eliminating half of the area that would otherwise be required for the symbol. There is no explicit number system character for this version of the symbol.
The zero suppression label is similar to the portion of the regular UPC symbol, Version A, to the left of the center except for several items, including the following:
1. It has a right guard pattern which is coded 010101.
2. Three of the characters are coded in odd parity and three are in even. Character encodation for this version (E) only is given in the following table:
Note that the even parity encodation is different for Version E than that shown in Table I for the regular version.
3. As was pointed out above, the coding of the zero suppression version is compressed into six characters of varying parity. The determination of whether a character's parity is odd or even is per the following table:
There is, therefore, no explicit character encodation of the category or modulo check characters, their values are derived from the parity permutation of the six encoded characters. For further explanation, reference is made to page 17 of "UPC Symbol Specification" referred to above.
As set forth above, co-pending patent application entitled "Optical Scan Generator" by James L. Hobart et al, Ser. No. 568,633, as assigned to the same assignee as the subject invention, describes a system for optically scanning an item containing a UPC label with a laser beam as it passes over the scanning window. The subject matter of that patent application is incorporated herein by reference.
Referring to patent application Ser. No. 568,633, for any given laser beam scan of an item containing a UPC code, the reflected light beam and resulting electrical equivalent signal from the detector 58 may not provide useful information to decoder 10. This happens when the beam scans print on the product label, only a portion of the UPC symbol, etc. It is thus the job of decoder 10 to separate the valid UPC information from the useless information and to properly decode the valid data.
For operation of the decoder 10 of FIG. 1, it is first necessary to provide it with bar width (1, 2, 3 or 4 modules) or light and color characteristics (black or white) information which could be valid data. Whether it is or not is determined by the decoder 10 and subsequent processing circuitry.
A bar width measurer (BWM) 11 provides this information. It is the function of the BWM to examine the stream of video data from detector 58 representing the relative widths of the bars printed on the bar code label as it is scanned by the optical system. The length of time the digital video input signal remains in one logic state represents the width of one bar of one reflectivity. The absolute length of time the video signal remains in a given logic state is unimportant as long as it is within some rather crude limits. The information of interest is contained in the relative width of a bar with respect to the other bars in the label and, in particular, with respect to the basic unit of width, the module, upon which the bars are based.
There are a number of ways of accomplishing this function and presently in use in scanning equipment, all within the state of the art of those skilled in the art. See, for example, U.S. Pat. No. 3,723,710. Since the BWM 11 does not form a part of the subject invention, it will not be described in great detail, although the following brief description is given of one approach to the design of a BWM.
The BWM accepts the digital video from the optical scanning system and compares each bar to the basic unit of width upon which all the bars are based and determines how many of these basic units are contained in the bar being examined. It does so by pursuing a certain set of assumptions about which bars are contained by the boundary pattern and proceeding until it sees a bar that is either too big or too small to exist in the label if the basic assumption was correct. When it sees a bar such as this, i.e. out of range, it begins again with new assumptions. These assumptions are:
1. Too Large: If a bar that is too large is encountered, assume (a) it was a margin, and (b) the next bar is the beginning of a boundary pattern.
2. Too Small: If a bar that is too small is encountered, assume (a) it must be the first bar of a boundary pattern.
Thus, decoder 10 is fed a stream of signals from the BWM indicating bar sizes and color, which in relationship to each other may be valid. The decoder 10 must determine if the sequence of those bars constitutes a valid one or not. This includes distinguishing when only a part of a label has been scanned, but not enough to get a complete reading. The validation of one-half of a regular UPC symbol is considered a complete identification since the other half of the label can be read and validated by earlier or subsequent scans.
In order to determine the start of a valid half label, decoder 10 must identify either a left guard bar pattern, a right guard bar pattern, or a center bar pattern. The edge guard bar pattern tree 12 and the center pattern bar tree 14 accomplish this in a manner which will be described subsequently.
Assuming that a guard bar or center bar pattern has been identified, then the BWM information goes to either decision (or digit) tree 16 or 18. The former is applicable if the next bar is one which is white and the latter if it is dark.
FIGS. 3A and 3B are graphical representations of decision tree 16 and FIGS. 4A and 4B of decision tree 18. Each tree 16 and 18 provides a four level decision making sequence. It has four levels because each character comprises four bars of from one to four modules in size. At each level a determination is made whether for the bar width sequence information provided, the sequence is a valid one, i.e. does it represent a valid sequence of 1's and 0's as set forth in Tables 1 and 2?. If it turns out to be valid, then the next BWM signal is looked at at the subsequent level of the decision tree. As long as the sequence is valid, the process continues through all the decision tree levels, i.e. four levels, and a valid character is decoded.
If at any time an invalid sequence is determined, decoder 10 is initialized and the search for a center bar pattern or an edge pattern begins again. If a valid character is decoded, the next BWM information is sent to the beginning of the same decision tree 16 or 18 and the decision tree procedure is followed again until it either culminates into the identification of another valid character or else it fails and the decoder 10 is initialized, and the search begins for another guard edge bar or center bar pattern.
There is one exception where the identification of an invalid sequence does not result in initialization of decoder 10. This occurs where the scan beam is sweeping past only a part of one side of the label and, without having scanned the entire side, passes over the center bar pattern. In that case, since the subsequent scan could result in a valid scan of the other half of the label, once decoder 10 realizes the number is invalid, but that this situation has occurred, it drops out of the decision tree 16 or 18 and into the appropriate level of the center pattern bar tree 14. Further explanation of this procedure will be given subsequently.
Each validated digit is loaded into a buffer 120, which is shown in FIG. 7 and which will be described in greater detail subsequently. Once six digits representing one-half of a label are read and stored in the buffer, then the decoder 10 looks for either an edge pattern and white margin or a center bar pattern, depending upon the direction of the scan. If it finds either, it signals a valid one-half label complete. In the case of an edge pattern, since the scan can no longer be on the UPC symbol, the decoder is initialized, and it looks for the next edge guard pattern or center bar pattern. In the case of a center pattern, since there is the possibility of a scan of the remaining half label, the decoder goes back to decision tree 18, since the center bar pattern always ends with a white bar.
The operation of the digit trees 16 and 18 are best understood by providing several examples of their operation. Suppose that the first signal from the BWM 11 indicates a bar which is white and is one module wide. This is indicated by "1W" in FIG. 3A, at the first level of the decision tree, at reference #71. Since, of course, this is a valid first bar for quite a few digits, see Tables 1 and 2, the decoder progresses up to the second level of the tree. At this level of the tree, every size black bar, i.e. from 1B to 4B, is still a possible valid bar for the digits shown in Tables 1 and 2.
Let us suppose that the next bar is a black bar three modules wide, i.e. 3B. This corresponds to position #713 in FIG. 3A. At this next level, level 3, only a 1W or 2W bar constitutes a valid sequence. Thus, if the next input is either 3W or 4W, there is an invalid sequence and the decoder is initialized.
Assuming the next bar is 1W, then for there to be a valid digit, the next bar at the 4th level must be 2B, which gives the sequence 1W, 3B, 1W, 2B or 0111011. This corresponds to the digit 7, on the left side of the label, having odd parity, with the scanning beam going east. This can be confirmed by reference to Tables 1 and 2.
Should the last bar have been 1B, and hence invalid, the decoder 10 would not have initialized. This is because the scan could have been passing through a part of one side of the label and then, without scanning a complete half, have started into a center bar pattern or edge pattern. In the case of the former, it is thus possible that the remainder of the scan, across the other half of the label, will result in a valid half label scan. Accordingly, in the case of a 1B in this case, the decoder 10 automatically switches to the center bar tree at the first level.
Under the circumstances set forth in the previous paragraph, the decoder 10 switches to the center bar pattern tree. More specifically these circumstances are: whenever decoder 10 fails to progress further in tree 14 or 16 because the current BWM is invalid, and it is either a 1W or 1B, it shifts to the center bar pattern and, using the information previously acquired, it shifts into the appropriate place in the center bar pattern tree. The latter will be explained in greater detail in connection with the following explanation of the guard bar and center bar pattern trees 12 and 14 which are shown in greater detail in FIG. 5.
At the first, second or third levels of the edge tree 12, if a 1B-1W-1B sequence doesn't occur, then the tree is initialized, i.e. it starts back at the beginning of trees 12 and 14 looking for the start of an edge or center pattern. At the fourth level of edge tree 12, if the BWM is 2W, 3W or 4W, then the decoder switches to the first level of digit tree 16, indicated by the numbers 71-74 in FIGS. 3A and 3B, since the previous combination of bars indicates an edge guard pattern.
Should the bar at the fourth level be 1W, then the tree progresses to the fifth level since the scan may be either the start of a digit having 1W as its first bar or else the second bar of an edge pattern.
At level 5 of tree 12, if the BWM provides either a 2B, 3B or 4B, the decoder 10 switches again to the digit tree 16, but this time at its second level since it already has a 1W as the first level. This level is indicated as numbers 711-714. If the bar is 1B, it still could be the beginning of a character (having 1W, 1B as the first two bars) or it could be the fifth bar of a zero suppress label.
If the next bar is 1W, at the sixth level, then it knows, in fact, that it is a right edge of a zero suppress label since it has picked up a 1B-1W-1B-1W-1B-1W. A 2W, 3W or 4W puts it into digit tree 16 at the third level.
At the first and third levels of center pattern tree 14, if a 1W isn't present, it cannot be a center tree pattern and hence the tree initializes back to the edge tree 12 in anticipation of an edge bar. At the second and fourth levels of center tree 14, if no 1B is provided, then there cannot be a center tree and hence the decoder initializes, but back to the same tree in anticipation of a center pattern.
At the fifth level of center tree 14, if a 1W appears, a possible center pattern is determined and decoder 10 shifts over to funny tree 20, starting with black. Funny tree 20, shown in greater detail in FIG. 6, will be explained subsequently. If a 2W, 3W or 4W appears, then the decoder switches to digit tree 16, at the first level, since the three preceding bars, e.g. 1B, 1W, 1B, define an edge pattern.
Funny Tree 20
Whenever decoder 10 picks up what appears to be a center pattern, there is a potential ambiguity that the first two bars of the alleged center pattern actually are the last two bars of the character adjacent the center pattern. This can only happen in the case of the left hand digits 0 and 4 and right hand digits 4 and 6 since these are the only digits which end in bar 1W, 1B going toward the center pattern. See Table 1.
Recognizing this potential ambiguity, decoder 10, if it gets a single black or single white bar after a center pattern, goes to the funny decision tree 20. Funny tree 20 is the same as the regular digit trees 16 and 18 except that decoder 10 only stays in it so long as the first two bars of the characters are single black and single white, i.e. right 3's and 6's and left 0's and 4's. With this general rule stated, the following specific action is taken by the funny tree 20, referring additionally to FIG. 6.
1. If following 1B, 1W, either 2B, 3B or 4B follows, then decoder 10 knows that right 3's and 6's and left 0's and 4's are not being scanned and decoder 10 switches to the second level of digit tree 18 (FIG. 4A), numbers 812-814.
2. If decoder 10 keeps decoding any sequences of right 3's and 6's or left 0's and 4's, then decoder 10 stays in the funny tree throughout the six digit sequence and afterwards looks for the standard terminating edge pattern and large white space. In this situation, decoder 10 has seen a "real" center pattern.
3. If at any time, a 1B is not followed by 1W, and it is the beginning of a legitimate character sequence, a transfer is made to digit tree 18 at an appropriate level, i.e. the second level numbers 812-813. This is an indication that the center pattern was "real" and decoder 10 switches back into the regular tree.
4. If, following 1B, 1W, any of the following sequences occur, the decoder 10 goes to the third level of digit tree 18 as indicated in FIG. 6 and a funny convert takes place:
1B -- 1W
1b -- 2w
1b -- 3w
2b -- 1w
2b -- 2w
2b -- 3w
3b -- 1w
3b -- 3w
3b -- 4w
4b -- 2w
4b -- 3w
4b -- 4w
a funny convert indicates that the center pattern was not "real" and a conversion must take place to "shift" over two places. This is what takes place by shifting to the third level of digit tree 18. Further details of funny convert will be explained subsequently in connection with FIGS. 7 and 8A-8B.
5. If, following 1B, 1W, any of the following sequences occur, then the decoder 10 remains in the decision tree:
1B -- 4W
2b -- 3w
3b -- 2w
4b -- 1w
one example of the implementation of the decision tree technique of decoder 10 which has been described above is now given. Reference is made to FIG. 7 which is a block schematic diagram of decoder 10 and to FIGS. 8A-8D which are detailed schematics of the block diagram of FIG. 7.
The heart of the decoder 10 is the program ROM 100 which contains 256, 16-bit instructions that direct the functioning of decoder 10. Included in these instructions are Front End and Back End instructions. The Back End instructions process the information acquired by the Front End operation to perform the "checksum check" (see "UPC Symbol Specification" referred to above) and outputting of decoded data. The Back End instructions are not pertinent to an understanding of the subject invention and will not be described in detail.
The Front End instructions constitute the various decision trees which have been described above. Henceforth these trees will be referred to collectively as "tree". These instructions derive their information from current data relating to bar size and color and past history consisting of 5 bits from the previous 16 bit instruction. Thus, program action consists of examining each piece of information as it comes in and making decisions for action immediately, rather than storing a large volume of data and then looking at all of the individual pieces of information to decide if any group of data is valid. This function of processing data from UPC labels in real time, i.e. examining data as it appears, is a major and unique feature of decoder 10.
Each new piece of data is used by the Front End instructions to update the program position in the tree. The program position in the tree determines whether the instruction output causes the program to continue looking at incoming data or causes the program to jump back to the beginning of the tree. The jump back to the beginning of the tree will be caused by a new piece of data trying to force the program to an illegal branch of the tree or by having acquired enough valid data to constitute a complete set of data, i.e. a valid half label.
Since the program ROM, block 100, contains both Front End and Back End instruction as explained and they will never both be used simultaneously, ROM output requirements can be cut in half by making duplicate use of the output bits. In the Front End, the bits have one meaning and in the Back End, another. The logic distinguishes between these two states by referencing all interpretation of the output bits to QBACK, block 136. If flag (flip-flop) QBACK is reset, Front End operation is indicated. IF QBACK is set, Back End operation is indicated. The meaning of the bits in Back End operation is not discussed, as it is not necessary for an understanding of the subject invention.
The breakdown of the 16-bit instruction word is given below for `Front End` operation only:
The `A` bits help to determine the next program address for the program ROM, block 100. Three bits of UPC label video, XBLK, XBS0, and XBS1 combine with the five `A` bits to specify the next 8-bit address as will be explained in greater detail subsequently.
The `V` bits specify Front End instructions as shown in the table below:
The `E` bits are used by the program to specify the next allowable bar size. The program knows, from where it is currently in the tree, what the allowable bar sizes are for the next data coming in, as will be explained by way of example subsequently. This data is fed into the illegal bar size detector 128, with the current bar size, to indicate good or bad bar size data from bar width measure. See the table below for `E` data coding:
the parity bit, XP, specifies the parity of the black modules in the UPC label digit being loaded into the digit buffer 120. The parity for each digit in the digit buffer 120 is stored in the parity buffer 124. The parity is stored only for one label half at a time. See "UPC Symbol Specification" referred to above for more information concerning parity of the black modules.
The funny convert enable bit, XM, enables the funny convert flags 132, QRHFC and QLHFC, so they are set if conditions indicate they should. The inhibit update bit, XNS, inhibits the updating function of the Bar Width Measurer if XNS is true.
Each branch in the tree actually consists of a particular 8-bit address at the input of the program ROM 100. The program counter 102 applies this 8-bit address. The program counter operates in two modes: the "load" and the "count" modes. In the load mode, the data at the input to the counter 102 appears at the counter outputs following the rising edge of the counter clock signal.
In the count mode, the counter output increments by 1 following the rising edge of the counter clock signal. The counter is in the load mode during the Front End and is in the count mode during the Back End. This is because during the Front End, the program ROM 100 must be free to instruct a jump in address, corresponding to a branch in the tree. This means that not all addresses are consecutive and therefore the program counter 102 does not have a sequential output. Thus, it must be in the load mode, where its output follows the input and not a sequential counting scheme.
The program counter 102 is in the load mode when QBACK or XA4 is true. The term QBACK is a flag (flip-flop output) designating Back End operation when set, Front End operation when reset. XA4 has no effect on the load input to the program counter 102 during the Front End because QBACK is reset. XA4 affects the load function of the program counter 102 only during Back End operation.
The count enable input of the program counter 102 is true if the load term is false and QCE 104 is set. The flag QCE is set when a valid set of data has been acquired (XVLD is true) and is set only for Back End operation, so its function is not pertinent.
The clear input of the program counter 102 is activated only if QIDLE, block 106, is set. The flag QIDLE is controlled by Back End and Entry/Exit logic, so its function does not relate to the subject invention except that it starts the program counter, block 102, always at 00 (hexadecimal). This assures that the program ROM 100 always has a fixed starting address (tree location) for the program.
The program counter 102 clock input comes from the clock select logic 108. During Front End operation, the clock output is XCCC, the color change clock that is part of the UPC label video information from the Bar Width Measurer 11. Thus, the program counter 102 does nothing and the program ROM 100 instruction output bits do not change, until a new piece of video data is sent from the Bar Width Measurer. In Back End operation, data acquisition has halted and the data that is currently stored needs to be processed for a "checksum check". Therefore, an internal Back End clock, CPB, is selected to clock the program counter 102 so the appropriate processing can take place by sequencing the program ROM 100 address inputs.
The program counter 102 load inputs come from the 8-bit address multiplexor, Mux 110. Normally, the `B` inputs of the Mux are selected, meaning that the 8-bit program counter 102 inputs consist of the `A` bit outputs from the program ROM 100, and three bits of video data from the Bar Width Measurer, XBS0, XBS1, XBLK.
If the disable input on the address Mux 110 is high, all outputs of the Mux become a logic 0. This causes the program counter, block 102, to load a 00H (00hexadecimal), forcing the program back to address 00H. The disable is high if XHFFL is true, XSMALL is false, and QBACK is false. In the Front End operation QBACK is always false. The XSMALL term is an error signal from the Bar Width Measurer, indicating that it has discovered some bad data and this term is normally false. Later explanation covers the case where it is true. The term XHFFL is the output of fail detect logic, block 130. Any of four types of failure or a masterclear signal causes XHFFL to become true.
If XSIXTH, XSMALL or QBACK is true, address Mux 110 `A` inputs are selected. The flat QBACK true indicates Back End operation. The signal XSMALL is an error signal sent to the decoder 10 by the Bar Width Measurer and indicates bad video data. The signal XSIXTH is an output of the digit buffer address counter 122 and indicates that six valid digits from a UPC label have been stored. This indicates either a partial or complete UPC label has been acquired, depending upon the status of the program flag 132 outputs.
Any of the three signals described in the preceding paragraph require special action on the part of the program. Therefore, the `A` inputs of the address Mux 110 are selected for the program counter 102 load inputs. This connects the output of the Front End special address logic 114 to the program counter 102 load inputs.
This means that the load inputs for the program counter 102 and consequently the next address for the program ROM 100 are determined by the front end special address logic 114. The inputs to the front end special address logic are XBLK, XSMALL, and QBACK. For Front End operation, QBACK is false all the time, so the variable inputs to the front end special address logic 114 are only XBLK and XSMALL, both signals from the Bar Width Measurer.
Summarizing operation of the address logic for the program in the Front End (QBACK is always false), the following simple operation becomes apparent:
The front end instruction decode logic 118 looks at the `V` data and if appropriate, generates a `store digit` (XSTD) signal or a `half complete` (XHC) signal. As was shown in Table No. 4, XSTD occurs for `V` data of 0H-9H (0-9 hexadecimal).
The `V` data is also the data input for the digit buffer 120. The write enable for the digit buffer is XSTD, XCCC, and XBFL. The signal XBFL indicates that the digit buffer is full. If the buffer is full, no more data can be written into it. When a store digit command (XSTD) is given, the color change clock (XCCC) will write the `V` data into the buffer if the buffer is not full (XBFL). Note that since `V` data 0H-BH (0-B hex) causes the front end instruction decode 118 to generate a store digit command (XSTD), and that the same `V` data 0H-BH is present at the digit buffer 120 data inputs, `V` data 0H-BH is equivalent to `Load digit 0H-BH specified by `V` data into the digit buffer`. That is, `V` data of 3H means "Load 3H into the digit buffer".
If `V` data were AH, a AH digit would be loaded in to the digit buffer 120. Thus, when the program is at a point in the tree where it knows that the last piece of UPC video data it saw was the last bar of a valid character, the program puts the hexadecimal value of that character of the `V` data outputs of the program ROM 100, causing the value of that character to be loaded into the digit buffer 120. The data output from the digit buffer goes to the Back End logic.
For Front End operation, the digit buffer address consists of the digit buffer address counter 122, and a signal XRH. This specifies where in the buffer the digits are stored. It is necessary to store data in fixed locations in the digit buffer so during Back End operation, the Back End logic always calls out data from the digit buffer in the correct order that it appears on the UPC label code. The signal XRH specifies which half of the digit buffer the data is stored in and the 3-bit digit buffer address counter 122 specifies the particular location within the half.
The digit buffer address counter 122 is incremented with each store digit command, XSTD. The next location in the half of the digit buffer being loaded is selected each time a digit is loaded into the digit buffer. The clock for the buffer address counter is the same as for the program counter 102, CPC.
During Front End operation, CPC is the color change clock XCCC. The digit buffer address counter is cleared by XHFFL 130, or XSPA, block 110. The signal XSPA is XSIXTH, or XSMALL, or QBACK. During the operation of the tree, the digit buffer address counter is cleared by the error signal XSMALL from the Bar Width Measurer Unit, or XSIXTH, one of the digit buffer address counter, block 122, outputs indicating a complete label half (6 digits) has been loaded in the digit buffer, or by XHFFL, indicating some error in label data being acquired.
In each of these cases, the data in the digit buffer 120 is not cleared, but the buffer address is moved back to its starting location so that new data is written over the data that was written in error. In the case where a complete label half of data was completed, the digit buffer address counter being cleared does not cause new data to be written over the old because the XRH signal that is one of the digit buffer address inputs changes state so that new data is written into the beginning location of the other half of the digit buffer.
The digit buffer address counter 122 also provides the address input for the parity buffer 124. This buffer provides the same function as the digit buffer, except it stores the black module parity of the digit being stored in the digit buffer.
The data input for this buffer is the program ROM 100, output of XP. The condition for writing into the parity buffer is that if no valid zero suppress label has been read (XZSVLD) and a store digit command has been given, write the parity, XP, on the color change clock, XCCC.
The parity check ROM 126 performs this check of the parity pattern. For a regular (Version A) UPC label (12 digits) the black module parity of all six digits in a half is the same, but the parity of left half digits is opposite the parity of right half digits. In the UPC zero suppress label, there are only six digits in the label and it is not possible to read only half the label successfully. Therefore, there are no left and right label halves as with the expanded UPC label. In the zero suppress label, the parity of all six digits is not the same. See Table 3.
This parity pattern of odd-even-even-odd, etc. can be only one of twenty different combinations. If all combinations were allowed, there would be sixty-four combinations. The parity check ROM 126 has as inputs XPZS, which indicates a zero suppress label, and QLP, which indicates, for a Regular Version, which half of the label is currently being tested for parity. The parity check ROM is normally disabled, so its output has no effect. When the program generates the XHC (half complete) command 118, the parity check ROM 126 is enabled during the command, so its output is active. If any parity discrepancy exists, the output XPE, for a parity error, comes up.
Another error detecting circuit is the illegal bar size detector 128. As was mentioned above, the `E` data out of the ROM 100 gives the allowable bar sizes for the next bar seen by the video and measured by the bar size measurer. The expected bar size (`E` data) is matched against the bar size (XBS0,XBS1) and if a discrepancy exists, the XBADBAR signal goes up.
The fail detect logic 130 indicates a failure to acquire a label half (XHFFL) if XPE or XBADBAR occur, or if the Bar Size Measurer detects a bar size discrepancy with a bar suddenly far too large or small compared to the bars it had been measuring (XLARGE, XSMALL), or if a master clear occurs (usually only on powering up).
The program flags, block 132, are flip-flops that indicate the status of the decoder 10 as it is attempting to read a UPC label. The flags are used by the rest of the decoder 10 logic to indicate action that has been taken and the action that still needs to be taken in order to acquire a complete valid UPC label.
All the flags are clocked by CPC, the same clock that clocks the program counter 102, so that during Front End operation, they are clocked by XCCC, the color change clock. They are set and reset by the signal inputs depending on the state of these, but they are all cleared by XOVER, a signal generated by the Back End and Entry/Exit Logic 138. This signal occurs as the operator, who is moving a UPC label through the scan target or window area, causes the label to leave the scan target area. As the decoder 10 senses that the label has left the scanning area, it resets all the program flags to be ready to start from scratch on the next label that enters the scan target area.
The flags QRP and QLP are the "right partial" and "left partial" flags, respectively. These are set as soon as the first valid UPC label digit is read and stored by a store digit (XSTD) command. One or the other is set, depending upon the parity (XP) of the first digit. As was mentioned earlier, in the explanation of the parity ROM 126, for an expanded label, the parity of all the digits are the same and the parity of the right half digits is opposite the left half.
The program starts off assuming a Regular Version UPC label is being read and sets either QRP or QLP, as XP indicates. At the same time, the flag QEVEN is set or not and then its inputs are locked out until a complete label half has been acquired or the flags have been reset by a fail condition.
The flag QEVEN stores the parity of the first digit in the half label currently being acquired for use as reference later on, as will soon be explained. For a Regular Version label, the flags stay in the state they are in during the remainder of the acquisition of the half if no fail condition occurs, as designated by XHFFL, block 130, or by XOVER which indicates the Back End functions are complete and the label is out of the acquisition area. During the half acquisition, XRH tells the digit buffer 120 which half of the label is currently being acquired and thus, which half of the digit buffer to store the digits in. When the sixth digit is stored, XSIXTH occurs and is detected by the program.
The program generates the half complete command, XHC, block 118, and the parity check ROM 126 is enabled. The parity ROM 126 checks the status of QLP to check parity. If QLP is not set, QRP is assumed to be set. The half complete command, XHC, also enables either QRHC or QLHC (right or left half complete) flags to be set, and the one set will depend on whether QRP or QLP respectively are set when XHC occurs. If at this time a parity error (XPE is true) occurs, then the flags are all reset and the program starts looking for another half label from scratch. If no parity error occurs, QRHC or QLHC are set and the program accepts only label halves of the missing variety (i.e. left halves if QRHC is set, or right halves, if QLHC is set). This is true until XOVER happens, at which point all flags are reset.
For zero suppress labels, the flag operation is similar, but additional flags are required. The flags QRP, QLP and QEVEN are set as described above, depending on the parity of the first digit stored. As was stated above, the program makes the assumption that one half of the UPC Regular Version label is being acquired at this point. If, however, the parity of one of the six digits being acquired changes from what the parity of the first digit was (QEVEN), it is realized that a zero suppress label is being acquired. Therefore, QRZS or QLZS (right or left zero suppress) is set, depending on whether QRP or QLP, respectively, are set. The terminology "right" or "left" zero suppress does not imply that there are two zero suppress label halves. It just indicates what the parity of the first digit was and, therefore, which half of the digit buffer 120 the zero suppress label is being stored in.
As soon as QRZS or QLZS is set, the indicator XPZS comes up, indicating a "partial zero suppress" label has been acquired and the rest of it is still to be acquired. This flag output, XPZS, is one of the inputs to the parity ROM 126, and indicates that when the command "half complete", XHC, is given, the parity ROM must check the parity pattern of the six digits to see that it agrees with one of the accepted patterns. The half complete command, XHC, also sets QRHC or QLHC as was described above. At this point, the flag output XZSVLD (zero suppress valid) comes up if QRHC and QRZS or QLHC and QLZS are true.
The two remaining flags, QRHFC and QLHFC (right or left half funny convert) are set from the input XBADBAR and XM. Under conditions described above, the program gets out of step with the incoming data so that it is looking at part of one UPC character and part of another, yet it thinks it is looking at all of one character. As explained previously, there are some digits that are encoded in such a manner that by taking part of one digit's code and placing it with part of another digit's code, a valid digit code, being neither of the two digits involved, is seen by the program. As was explained earlier (see UPC label and funny convert explanation), there are only four digits that can be involved in a funny convert situation. These digits are `0`, `4`, `3`, and `6`. At times a `0` can look like a `4` and vice versa. Similarly, a `3` can look like a `6` and vice versa. When this condition exists, the program realizes it, but at this point does not have enough information to tell what it is actually seeing, so it writes either an `A` or `B` hexadecimal into the digit buffer. The `A` will be converted (funny convert) to a `0` or `4` by the Back End logic and the `B` will be converted to a `3` or `6`. This conversion will be explained shortly.
As soon as the program comes to two digits that do not yield a valid code, the signal XBADBAR occurs, because the program was expecting a certain bar size and did not see it. At this point, the logic normally generates a fail condition indication, XHFFL, block 130. The program can recognize that it was in this type of situation usually, so when the XBADBAR signal occurs, it gives the XM command that inhibits XHFFL and sets one of the funny convert flags, QRHFC or QLHFC, if conditions warrant it.
The funny convert flags are used by the Back End logic 138 to convert the `A` or `B` stored in the digit buffer 120 to the proper number.
Funny Convert Explanation
This is done by a ROM in the Back End logic which will convert an `A` hexadecimal number stored in the digit buffer 120 to a `0` or `4`, as the digits are being moved out of the digit buffer in the Back End operation. A `B` hexadecimal number will be converted to a `3` or `6`. Digits `0` through `9`, including `0`, `4`, `3`, and `6` are uneffected by the funny convert operation of the ROM. They are moved out of the digit buffer 120 in the same form as they are stored. The conversion that takes place depends upon the state of the funny convert flags, QRHFC and QLHFC, and the half of the UPC label that the digit `A` or `B` was from. A digit is said to be stored in the "left half" of the digit buffer if the digit was part of the left half of a UPC label or in the "right half" of the buffer if the digit was from the right half portion of a UPC label. Digits are always stored in fixed locations depending on which half of the label they are in (see digit buffer 120 explanation) so the Back End logic always knows which half of a UPC label a digit was from by its location in the digit buffer. The following table will define these relationships as they apply to the funny convert operation:
The valid label detect logic 134 generates the signal XVLD (valid label acquired) that sets QBACK and puts the processor unit in the Back End mode. The flags QRHC and QLHC or XZSVLD cause the XVLD signal to go high.
The flag QBACK, block 136, determines whether the decoder 10 is in the Front End or Back End mode. That is, whether the decoder 10 is acquiring (reading) a UPC label (Front End operation) or it is processing stored UPC label digits (Back End operation). If QBACK is true, it indicates Back End operation. The flag QBACK is set by XVLD and reset by one of several Back End logic 138 signals.
The Back End function is to check the checksum according to the modulo 10 algorithm defined by the UPC specifications. The Back End is entered after the Front End has fully decoded a label known to be valid in every way except for the checksum. The Back End then performs the modulo 10 calculations and checks for the correct check character. If the checksum is incorrect, the decoder 10 is completely reinitialized and returns to Front End operation. If the checksum is valid, the decoder 10 becomes idle until the entry/exit logic 130 signals that the operator has removed the label from the scanning target area. At this time, the data in the digit buffer 120 is taken by an interface unit external to the decoder and the decoder is placed in an idle state as indicated by a logic true condition of the flag QIDLE.
The Back End and entry/exit logic 138 is not shown in FIG. 8 since it is not pertinent to the description of the subject invention.
Detailed Functional Examples
To further aid in explaining the operation of decoder 10, the step by step operation of the action of the decision "tree" is given by way of two different examples. The first illustrates the fail condition response and the second illustrates the successful acquisition of a complete label half of a UPC label.
A review of how the program makes the decision on allowable bar sizes would be helpful. The widths of all the bars in the UPC label that encode the numeric information are required to be an even multiple of the unit module width (i.e. 1, 2, 3 or 4 module widths). By definition, there are a total of seven unit module widths required per encoded digit. This total is the sum of the black modules and white modules.
Also, there are four bars required for each encoded digit, two white bars and two black bars, alternating within the character. Each character must have seven modules and four bars. It follows that the largest allowable bar is four modules. This is because if one bar is four modules, there are only three modules left and there are still three bars required. Since each bar has to be at least one module wide, there are just enough modules left for three-one module bars.
This is the scheme used by the program to deduce which bar sizes are allowable for the next bar. Some examples follow:
Example I:
This example assumes the following bars seen by the Bar Width Measurer Unit: Color Bar Size
Each of the following examples represents the change due to a single color change clock, XCCC. The program ROM 100 outputs are derived directly from the ROM program listing, Table No. 8, which follows:
For example, at ROM address 2BH (hexadecimal), the ROM 100 output is 5F98H. The output breaks down as follows:
This output implies that the `A` data is 0BH (hexadecimal), the `V` data is FH (NOP instruction), the `E` data is 3H (the next bar must be a 1 or 2 to be valid), the parity, XP, is 0 (odd partiy), XM is 0 (no funny convert), and XNS, which is not pertinent to the subject invention.
Example II: will follow the program through acquisition of a complete label half as shown below:
Claims
We claim:
1. A reader-scanner system for detecting and decoding coded character information where each encoded character comprises a plurality of bars of alternating light reflective characteristics of one or more widths comprising: a. a light source for projecting a beam of light; b. a scan target area through which pass encoded objects to be scanned; c. a light-sensitive detector for detecting changes in the level of light reflected from objects at said scan target area which are scanned by said beam of light; d. means responsive to said detector for determining possible bar width and bar characteristic information of the object being scanned; f. means responsive to said bar width information to determine in real time valid sequences of said information comprising; multiple level decision making means which includes means for comparing incoming bar width and characteristic information with allowable bar width and characteristic values for the bar and characteristic information sequence developed to that point, means for failing any information sequence which is not allowable, and means for moving to the next and subsequent levels of the decision-making sequence so long as the information sequence is an allowable one, until the completion of the multi-level sequence at which time an individual character is uniquely defined.
2. A reader-scanner system for detecting and decoding coded character information where each encoded character comprises a plurality of bars of alternating light reflective characteristics of one or more widths comprising: a. a laser for projecting a narrow beam of light; b. a scan target area through which pass encoded objects to be scanned; c. a light-sensitive detector for detecting changes in the level of laser light reflected from objects at said scan target area; d. optical means for directing the light beam from said laser to said scan target area to scan said encoded objects; e. means responsive to said detector for determining possible bar width and bar characteristic information of the object being scanned; f. decoding means comprising means responsive to said bar width information determining means for comparing first bar width and characteristic information of the beginning of a possible valid encoded character sequence with allowable character bar widths and characteristics and means for failing said first bar width and characteristic information if it is not allowable; g. means for comparing the next sequential bar width and characteristic information with allowable character bar width and characteristic values for the sequence which contains said first bar width and characteristic information if the first bar width and characteristic information is allowable, and means for failing the first and second bar width and characteristic information if it is not allowable; and h. means for comparing subsequent bar width and characteristic information with allowable character bar width and characteristic sequences until a character is decoded or else the sequence is invalidated.
3. A reader-scanner system for detecting and decoding UPC coded character information where information is encoded as a plurality of bars of alternating light reflective characteristics of one or more widths, said UPC characterized by a symbol having edge and center bar patterns and character bar patterns comprising: a. a laser for projecting a narrow beam of light; b. a scan target area through which pass encoded objects to be scanned; c. a light-sensitive detector for detecting changes in the level of laser light reflected from objects at said scan target area; d. optical means for directing the light beam from said laser to said scan target area to scan said encoded objects; e. means responsive to said detector for determining possible bar width and bar characteristic information of the object being scanned; f. first decision tree means responsive to said bar width information determining means for detecting edge and center bar patterns; g. second decision tree means responsive to the bar width information determining means for determining valid sequences of UPC characters once a valid edge or center bar pattern is determined; and h. wherein said first and second decision tree means comprise multiple-level decision making means which includes means for comparing incoming bar width and characteristic information with allowable bar width and characteristic values for the bar and characteristic information sequence developed to that point, means for failing any information sequence which is not allowable, and means for moving to the next and subsequent levels of the decision-making sequence so long as the information sequence is an allowable one, until the completion of the multi-level sequence at which time an individual identification is uniquely defined.