Method and Apparatus for Reading and Decoding a High Density Linear Bar Code

This invention relates to a method and apparatus for reading and decoding a high density, linear bar code of the type of the Universal Product Code standard symbol and variations thereof.

The grocery industry has adopted a linear bar code that is known as the Universal Product Bar Code (UPC) for identifying the items sold in the grocery trade. This Universal Product Code symbol is widely used in the grocery industry by marking it on packages, containers, cans or the like in which the items are packaged and sold. The standard symbol comprises a series of parallel light and dark bars of different widths with an optical character recognition (OCR-B) numeric font equivalent of the symbol printed along with the bar code symbol. The standard UPC symbol is also employed on shelf labels for identifying the items stored on the shelves for use in inventory control purposes and the like. Various prior art publications disclose the standard UPC symbol and its characteristics as utilized in the grocery industry and the various versions for use in other industries, i.e., for use on drug and health related items and general merchandise or department store items. In addition, special versions that have been developed such as the zero-suppression version to facilitate marking the symbol on packages that are too small to include the UPC symbol and the distribution symbol (DCI) and which DCI symbol is designed for printing on shipping containers. The primary advantage in utilizing the UPC symbol is automatic item identification at the check stand in conjunction with automatic, electronic check-out systems. In present day check-out systems, the UPC bar code symbol is interpreted by a high speed laser beam scanner.

There is also a need for a portable data acquisition device to scan the UPC symbol and its descendant, the DCI symbol. This is most easily satisfied with a hand-held wand scanner. A wand scanner need not have the depth of field that the check stand scanner requires since it is scanned in contact with the label. It does not require the speed of the laser beam since it is hand propelled. Also, the laser scanner must reject the majority of its input as extraneous graphics but a wand scanner would "see" little extraneous input. However, a portable scanner would be battery powered and therefore low power consumption is important. Also, while the velocity of the laser beam is known, hand movement velocities vary over a wide range and exhibit significant accelerations.

Prior art methods of reading the UPC symbol consist of decoding the symbol through the use of delta distances to eliminate printing tolerances due to ink spread resulting from printing the symbol on a surface. Ink spread is the major printing error to be considered in decoding bar coded data. Delta distance measurements are the distances between the leading edges and the trailing edges of a combination of successive bars and spaces in the bar coded symbol. The delta distance measurements are utilized to obtain ratios of the selected delta distances for decoding the symbol. If the ink spread is uniform in the recorded symbol, these decoding ratios do not change as a result of the ink spread. There are sixteen combinations of ratios, but when the forward and reverse sequences are considered, twenty ratios are required. Accordingly, some further measurement must be made to resolve the ambiguities that result when a distinct delta distance ratio cannot be solely used for decoding purposes. These other measurements do not have the advantage with respect to printing tolerances that the delta distance measurements have. Some early prior art decoding techniques required that the decoding circuitry distinguish between a large number of ratios and very close ratios thereby requiring very good resolution for decoding purposes. Such resolution is not readily obtainable, particularly in a hand-held wand scanner or a portable decoding unit. More recently, decoding techniques have been developed so as to reduce the number of ratios to be discriminated between to four ratios having relatively good separation between them so that they may be readily distinguished. In this type of decoding arrangement, the ratios are selected so that the numerator and denominator have one bar and one space so that the ink spread is not a factor in the resulting ratio. Since in the UPC symbol each coded digit has a forward and a reverse sequence, there are still combinations that produce ambiguities when these prior art techniques are resorted to. These digits cannot be unambiguously decoded solely on the basis of the aforementioned delta distance ratios and some other means or ratios must be utilized to eliminate the printing tolerance problem and yet unambiguously decode all of the coded digits. The prior art methods of implementing the aforementioned decoding techniques in terms of delta distance measurements are generally by means of utilizing the high speed laser beam scanner and associated circuits for computing the decoding ratios. In a manual wand scanning technique for reading the UPC symbol and similar symbols, wide ranges of velocities may result from passing the wand over the recorded symbol whereby these prior art circuits for computing the delta distance ratios are not practical. Some prior art techniques utilized with hand-held wand scanners for reading bar coded data utilize logarithm time based circuits, however, these circuits are not practical for computing the delta distance ratios for decoding the UPC symbol.

The present invention provides an improved, very reliable low cost, lower power consuming method and apparatus for reading and decoding a high density linear bar code of the type of the UPC symbol that may be advantageously employed in a manual wand scanner but may also be used in other decoding apparatus. The invention provides reliable reading and decoding that is highly tolerant to wand acceleration and poorly printed symbols and symbols having a wide range of printing tolerances, yet permitting a simplified technique for resolving ambiguities. The implementation of the present invention recognizes and takes advantage of the minimum amount of graphics rejection required in a hand-held wand, vis-a-vis, a high-speed laser beam scanner. The implementation of the present invention is advantageous over prior art methods and apparatus in that it measures the widths of the successive bars and spaces in a bar coded symbol in real time and stores them in a storage device of the type of a random access memory which permits sophisiticated post processing techniques to be utilized once the measurements are made. In addition, certain computations may be readily made by use of logarithmic techniques which permit wide dynamic ranges without the need for multiplying and dividing large numbers. By utilizing the coded information from the central portion or a standard portion of coded symbol of the UPC type, ink spread corrections can be readily made and by selecting proper secondary decoding ratios for ambiguity resolution purposes that are dependent upon the primary decoding ratios whereby the ambiguities may be resolved with confidence.

These and other features of the present invention may be more fully appreciated when considered in the light of the following specification and drawings, in which:

FIG. 1 is a schematic block diagram of the reader for manually reading a UPC symbol or a derivative thereof and embodying the present invention;

FIG. 1A is a representation of the UPC standard symbol;

FIG. 1B is a representation of the character structure of the symbol illustrated in FIG. 1A;

FIG. 1C is a representation of the character structure of the symbol of FIG. 1A and identifying the primary and secondary decoding ratios;

FIG. 2 is a schematic block diagram of the linear time to digital converter utilized in the system of FIG. 1;

FIG. 3 is a schematic block diagram of the center bar locator utilized in the system of FIG. 1;

FIG. 3A is a diagrammatic illustration of the address positions in a memory of the center bar pattern for a symbol of the type illustrated in FIG. 1A;

FIG. 3B is a representation of the information stored in the read only memory E utilized in the center bar locator of FIG. 3;

FIG. 4 is a schematic block diagram of the ratio computer utilized in the system of FIG. 1; and

FIG. 5 is a schematic block diagram of the character decoder utilized in the system of FIG. 1.

Now referring to the drawings, the invention will be examined in detail as the concept may be implemented for reading and decoding a high density, linear bar code of the type of the grocery industry Universal Product Code (UPC).

For the purpose of facilitating the understanding of the concept of the present invention, the basic characteristics of the standard UPC symbol as illustrated in FIGS. 1A and 1B will be first examined. The basic characteristics of the standard Universal Product Code symbol as illustrated in FIG. 1 includes a series of light and dark parallel bars with a light margin on each side. As illustrated in FIG. 1A, there are 30 dark bars and 29 light bars for any 10 character code. The overall shape of the symbol is rectangular. As can be best appreciated from examining FIG. 1B, each character or digit of the code is represented by two dark bars and two light spaces. Each coded character is made up of seven modules. A module may consist of either a dark bar or a light bar (or a sequential combination of 1, 2, 3 or 4 dark bars or light bars). To this end, in FIG. 1B the left-hand portion of the character structure illustrated represents the digit 6 wherein the seven modules are characterized as two bars and two spaces. From this, it will be noted that the right-hand bar consists of a series of four dark modules. The right-hand portion of the character structure is similarly encoded in terms of two bars and two spaces for representing the decimal digit 0. It will also be appreciated from examining FIG. 1A in particular, that each of the two characters coded in terms of the UPC symbol is independent of the other. The symbol is designed to be recordable or printed by conventional methods. The UPC symbol is "wandable" which means a simple hand-held device can be used to scan or read the symbol.

Fixed position scanners have been constructed to scan this symbol in an omnidirectional manner. Specifically, the symbol can be automatically read by a scanner, such as a laser beam scanner, when the symbol is drawn past the scanner in any orientation. Whether the symbol is read by means of a hand-held device or by a device having omnidirectional characteristics, there must be some relative motion produced between the recorded symbol and the scanning device.

The UPC symbol as represented in FIG. 1A also includes a standard pattern comprising a group of coding modules having known width ratios between successive coding modules. As utilized in the standard UPC symbol, the standard patterns illustrated in FIG. 1A include three such patterns having a 1:1 width ratio and which patterns are identified as the left-hand guard bar pattern, the right-hand guard bar pattern and the tall center bar pattern. The right-hand and left-hand guard patterns are defined to represent a dark-light-dark pattern or 1 0 1. The tall center bar pattern represents the pattern of information 0 1 0 1 0 or a light bar-dark bar-light bar pattern. The central bar pattern separates the forward and reverse digits that are encoded by means of the symbol. To the left of the center bar pattern there are five characters of the code which represent the "forward" encoded characters, while to the right of the tall center bar pattern there are five characters that are encoded in the "reverse" direction. The forward, or left characters, and the reverse, or right characters, refer to the fact that the right-hand characters represent the binary complement of the left-hand characters. For the decimal digit zero, for example, the left-hand encoding is 0001101, while the right-hand encoding for zero is 1110010. The left-hand characters are considered to have an odd parity and the right-hand characters an even parity. The left-hand character will comprise 3 or 5 dark modules and always begin with a light space. The right-hand characters will comprise 2 or 4 dark modules and always begin with a dark module.

As illustrated in FIG. 1A, the standard symbol also includes a modulo check character encoded between the right-hand guard bar pattern and the last module of the reverse character field. In addition to the left-hand guard pattern and to the right of the left-hand guard bar pattern, information is recorded which may be utilized to identify the number system of the characters encoded by means of the symbol and having a preselected width. In reading any bar coded symbol, the symbol is not only read as recorded but the peripheral recorded information adjacent the desired information bar coded pattern is generally detected whether it is related to the symbol or not. In the laser scanner techniques, for example, the majority of the extraneous graphics must be rejected while in a hand-held wand scanner very little extraneous graphics are sensed by the scanner.

As indicated hereinabove and illustrated in FIG. 1B, the UPC symbol comprises two bars and two spaces for representing a single character. The order of the bars and spaces may be space-bar-space-bar, or the reverse sequence in accordance with the direction of the scan and the field of the recorded character. For the purposes of examining the present invention the sequencing assumed is A, B, C, D wherein the spaces and the bars are identified in accordance with FIG. 1C for both the forward and the reverse directions. Stated differently, each character, whether recorded in the forward direction or the reverse direction will be represented by the sequence A, B, C and D. With this sequence, the two primary decoding ratios utilized herein are defined as: ##EQU1##

In examining FIG. 1C, it will be noted that each of these primary decoding ratios contain in both the numerator and denominator one bar and one space so that any ink spread that may be present does not affect the ratio. These primary decoding ratios produce the numerical ratios 2/5, 3/4, 4/3 and 5/2. A pair of these primary ratios are utilized to decode a single character. However, it should be recognized that in any delta distance method utilizing the aforementioned decoding ratios, an ambiguity occurs and certain characters cannot be unambiguously decoded solely on the basis of the primary decoding ratios. The present invention utilizes selected and simplified secondary decoding ratios for resolving the ambiguity and also corrects any print tolerances rendering the decoding of a character symbol on the basis of a primary and secondary ratio very reliable. The secondary ratios, which are utilized in accordance with the present invention, are dependent upon values resulting from developing the two primary ratios. As indicated in FIG. 1C, if the two primary ratios produce the ratios 3/4, 4/3 or 4/3, 3/4, then the secondary ratios must be assigned in accordance with the values of the primary ratios. If the selected primary ratio upon which thesecondary decoding ratios are dependent is 3/4 then the ratio of the widths of the modules A and B (A/B) is examined while if the primary ratio is 4/3, then the secondary ratio of the width of the modules C and D (C/D) is examined. The secondary ratios are examined to determine if they are 2/1 or 1/2. In any event, for those digits that do produce an ambiguity, such as 1 and 7 and 2 and 8, they are decoded on the basis of the two primary decoding ratios and the selected secondary decoding ratio. All of the other digits may be unambigously decoded on the basis of primary decoding ratios alone.

The improved scanner and decoder of the present invention is implemented by means of a microprocessor. The widths of each bar and each space of a scanned symbol are measured and stored in a counter that is driven by a linear time base. These measured distances or widths are then transferred to a memory, once a measurement is completed and the successive measurements are stored in successive storage locations in the memory until all of the measurements are completed. As indicated hereinabove, in the scanning of a recorded symbol there is extraneous graphics on the label with the UPC symbol that may be sensed and this extraneous data is also stored in the memory along with the desired information. Accordingly, the information scanned before scanning the symbol itself as well as the information detected after the symbol is stored in the memory. There is no decoding while the label is being scanned. This procedure requires that the "label" having the desired encoded information be located or "framed" in the memory before it can be decoded. As indicated hereinabove, the standard UPC symbol has a standard central bar pattern wherein characters are encoded to the left and to the right of the center bar pattern. The data in the memory is examined so that the encoded data may be located therein by examining and locating the stored data representing the standard center bar pattern. Once this center bar pattern is located, it is utilized in accordance with the present invention for identifying the locations in storage of the encoded characters to the left and to the right thereof. Stated differently, once the center bar pattern position in memory is located, the locations of the modules A, B, C and D will be known for each character of the symbol. Once these modules are located in the memory, then the sums of the modules may be computed to determine the values of the two primary decoding ratios. Once the primary decoding ratios are computed, the secondary decoding ratios may be computed and the symbol decoded. If the two primary ratios produce any combination of 3/4 and 4/3, an ambiguity exists which is resolved by means of the aforementioned secondary decoding ratios; see Table I.

The secondary ratios A/B and C/D do not contain delta distance properties and so exhibit a wide range of values. While they do not overlap according to the symbol specification, other errors or out-of-tolerance symbols can cause reading errors.

Included in the standard UPC symbol are guard bars and center bars with a 1:1 ratio. If the logarithm of the ratio of a center bar to a center space is other than zero, the ratio is not 1:1 and the degree of deviation therefrom is indicated by the magnitude of the log. This provides information on the direction and magnitude of print tolerance which can be used to correct the secondary ratio measurements. For example, if the ratio of a center bar to a center space is measured as 2:1, it can be inferred that the symbol is overprinted. In that case, a nominal 2:1, A/B ratio would be measured as close to 4:1. If the measured A/B ratio is divided by the measured center bar to center space ratio, the nominal value of 2:1 would result.

The computations are simplified by utilizing logarithms. The division results by subtracting the logs. If the A/B (or C/D) ratio is a space-to-bar ratio, then the logarithm of the center bar to center space ratio is added to the A/B ratio to effect multiplication. In reading from left to right, the correction factor is logarithmically added to the measured widths of the first half of the symbol while it is subtracted from the righthand characters. In a reverse read, the first half is the right half.

A 1:1 ratio does not change proportionately to a 2:1 under conditions of ink spread. But a correction can be made if the only nominal ratios are 1:2 and 2:1. If all other ratios were to be encountered, in a middle bar to middle bar space ratio, for example, the accuracy of the correction would be less accurate.

With the above structure and the general philosophy for decoding the symbol discussed above in mind, the general organization of the decoding system will now be examined as it is represented in the block diagram of FIG. 1. The UPC symbol is illustrated in FIG. 1 as it may be recorded or printed on a label 10. The label 10 is read by passing the optical wand 11 over the symbol for detecting and signalling the bars and spaces representing the data in terms of the UPC symbol. The optical wand 11 provides signals indicating the transition between a white bar and a white space and vice versa. Such optical wands are well known in the art and such a wand reading system is exemplified by the disclosure in U.S. Pat. No. 3,925,639 owned by the same assignee as the present invention. These wand signals or raw data are applied to a linear time to digital converter 12. The converter 12 measures the amount of time spent by the wand 11 in traversing each bar and each space and these width measurements are stored in a read/write memory 13. The width measurements are stored in sequence in storage locations in the memory 13. The read/write memory 13 may conveniently be a random access memory (RAM). When the transitions sensed by the wand 11 terminate, control of the system is passed from the linear time to digital converter 12 to a center bar locator 14. The center bar locator 14 searches the memory 13 for ratios that satisfy the pattern for the center bar of the UPC symbol or the center bar pattern 0 1 0 1 0. The center bar pattern locator 14 utilizes a ratio computer 15 for this purpose. The ratio computer 15 is utilized also by a character decoder 16.

When the ratio computer 15 is under the control of the center bar locator, it receives the linear values of the width measurements for the modules A, B, C and D from the memory 13 and adds a selected pair of these values and computes preselected ratios to determine if a valid center bar pattern is present. The center bar locator 14 determines the position of the center bar pattern in the memory by determining that a preselected pair of ratios are both one. The center bar pattern represents the pattern 0 1 0 1 0 and in reading from left to right these can be considered as the A, B, C. D and E modules. To determine that a valid center bar is located in the memory 13, the center bar ratios ##EQU2## are developed and examined. If both of these ratios are one, then the center bar pattern has been correctly located in the memory 13. By examining both of the aforementioned ratios and when the correct result is produced, the system will be assured that the center bar pattern was begun with a space and is correctly located. If either of the above ratios do not compute to one, the process must be repeated until two successive ratios of unity are detected. It should be noted in the calculations for locating the center bar pattern that the delta distances are utilized and therefore if the ink spread is uniform it will not effect the determination of the correct location of the center bar pattern. If after the preselected number of trys, the desired ratios are not detected, then the read is aborted.

Once the conditions for a valid center bar are satisfied, a recording or print tolerance correction character is computed. The print tolerance correction is computed on the basis of the sensed widths of the modules comprising the center bar pattern. The magnitude of the correction is obtained by measuring the ratio of the standard bars to the guard spaces. Accordingly, to determine the value of the print tolerance correction, the ratio ##EQU3## is computed. In this ratio, (A+C) represents the widths of the bars while (B+D) represents the widths of the spaces and if the center bar pattern is correctly located, the ratio should be one as that was the basic logic of the symbol prior to recording or printing it. Once this print tolerance correction value is computed, the memory address of the memory 13 is set to the location of the start of the first character to be decoded. At this point in the decoding process, the control is passed to the character decoder 16.

The character decoder 16 utilizes the ratio computer 15 for executing its function in decoding the pattern of modules to the left and the right of the center bar pattern. As in the case of the valid center bar pattern recognition, the characters are decoded by a sequence of ratios produced by the ratio computer 15 under the control of the character decoder 16. The character decoder 16 then steps through the sequence of 12 characters plus the center bar pattern as stored in the memory 13 starting from the location noted by the center bar locator. Once each of the primary ratios are computed, the secondary ratios are computed to resolve any possible ambiguity. Before the secondary decoding ratios are computed, the printing tolerance correction character is combined with the data representing the width of the modules as stored in the memory 13 and then these corrected values are utilized in computing the secondary decoding ratios. If any of the 12 characters fail to properly decode, control is returned to the center bar locator 14. Once all of the characters are properly decoded by the character decoder 16 then the control is passed from the decoder 16 to the validity check circuit 17.

The validity check circuit 17 will not be described in detail since it does not constitute a portion of the novel aspect of the method and apparatus for decoding the UPC symbol. It is merely included for the sake of the completeness of the read cycle iterative loop. To this end there is included with each character a read direction indicator. In order that the information decoded be valid, the read direction indicators must all be consistent. If the direction of the reading by the wand 11 is in the reverse direction, the character order is reversed and the check digit verified. If either of these tests fail, control of the system is returned to the center bar locator 14 to determine the correct location of the center bar pattern in the memory 13. This process is repeated until a valid read is accomplished or the potential locations of a valid symbol as stored in the memory 13 are exhausted. In this latter case, the read cycle is aborted.

With the above general organization of the decoding system in mind, the details of the linear time to digital converter 12 as illustrated in FIG. 2 will now be examined in detail. The linear time to digital converter 12 comprises the circuit elements for receiving the wand raw data information from the wand 11 and processing the data for storage in the read/write memory 13. For this purpose, an AND circuit 20 has one input terminal coupled to receive the wand raw data information at its input. The other input of the AND circuit 20 is coupled to a start/stop toggle 21. The output circuit from the AND circuit 20 is coupled to a differentiator circuit 22, which in turn is coupled to a rectifier 23. A toggle TM has its set input, S, coupled directly to the output of the rectifier 23. The reset output for the toggle TM is identified as M1. The set output of the toggle TM is coupled to an AND circuit 24. The output of the AND circuit 24 is coupled to a sequencer 25 which provides the sequential output signals M2, M3 and M4. The real time measurements result through the provision of a count rate oscillator 26 which provides clock pulses at a preselected rate to an AND circuit 27. The other input to the AND circuit 27 is the M1 reset output from the toggle TM. The clock pulses from the oscillator 26 are also applied as a second input to the AND circuit 24 for controlling the operation of the sequencer 25. The AND circuit 27 has its output connected to the incrementing input of an 8-bit counter 28. The 8-bit counter may be preset through a signal coupled to its preset input and which signal is identified in FIG. 2 as the M3 signal from the sequencer 25. The 8-bit counter 28 also has an overflow output which is identified as a carry output and this output signal is coupled to an OR circuit 29 as one input thereto. The count outputs for the 8-bit counter 28 are coupled as one input to an AND circuit 30. The other input to the AND circuit 30 is the M2 signal from the sequencer 25. The output of the AND circuit 30 enables the data input terminal for the read/write memory 13 and transfers data into the memory at the successive storage locations. The read/write memory 13 is under the control of an address counter and register 31. The address counter and register 31 has an incrementing input further identified as having the M3 signal from the sequencer 25 coupled thereto for incrementing the successive addresses of the memory 13. The address counter and register 31 also have an overflow output terminal identified as a "carry out" and this output signal is applied as a second input signal to the OR circuit 29. The starting signal for initiating the read cycle is coupled to the reset terminal for the address counter 31. The OR circuit 29 will produce an overflow output signal identified as an M5 signal if either of its inputs receive an overflow signal from the counter 28 or the register 31. The M4 signal from the sequencer 25 is applied to the reset terminal R for the toggle TM for resetting the toggle at the completion of reading a module of the UPC symbol. The "start" signal is also coupled to the reset terminal of the toggle 21 for enabling the AND gate 20.

The operation of the linear time to digital converter 12 may now be appreciated with the above structure in mind. This element 12 may be provided with a switch to function to start the reading operation and apply a "start" signal to the reset terminal for the toggle 21 or the "T" toggle, as well as to the reset terminal for the address counter and the register 31. The unit 12 on the other hand may be armed to be automatically responsive to certain conditions that indicate that an attempt is to be made to read the label 10, such as when the wand 11 is placed against the white surface or the end of the label 10 as disclosed in U.S. Pat. No. 3,925,639, for example. As the wand 11 is moved over the label 10, it detects the transitions between the dark bars and the white spaces. When these transitions occur, they are passed through the AND gate 20 and are differentiated in the element 22 and rectified at the element 23 for application of the resulting signals to the "set" terminal of the toggle TM. The toggle TM is "set" at each transition between the detected modules. The clock pulses provided by the oscillator 26 are accumulated in the 8-bit counter 28 between the time intervals, the toggle TM is reset resulting from the application of the M1 signal to AND gate 27. The setting of the toggle TM will cause the sequencer 25 to be enabled and disable the application of the clock pulses to the 8-bit counter 28. This disabling of the clock pulses to the counter 28 results through the change in state of the M1 signal upon the toggle TM being "set". At this point in time, the information that has been accumulated in the counter 28 is transferred into the memory 13, the address of the memory for storing the next piece of information is incremented between transitions and then resetting the toggle TM. The sequencer 25 is provided to perform these functions by generating the sequential signals M2, M3 and M4 in that sequence. The sequencing opertions that result after the setting of the toggle TM are as follows:

The memory 13 is preferably defined to have the capacity to accumulate the results of 64 measurements to permit the wand 11 to traverse any extraneous graphics that may be associated with the UPC symbol on the label 10. The count interval for the counter 28 is about 40 microseconds and the count capacity is 8 bits, or counts. It will be recognized that some finite amount of time is required to execute the functions identified above after a transition point is detected by the wand 11. For this purpose the counter 28 is preset to a value that represents the count that would have been accumulated during this processing time. In one arrangement, the minimum count is preset to 7 to allow sufficient time to store the accumulated measurements in the memory 13 after the transition. The counter 28 is preset to count 7 at the beginning of each measurement by the M3 signal to preserve the accuracy of the decoding system.

If the counter 28 or the memory address counter 31 overflows and provides an output signal, the overflow is indicated by the M5 output signal from the OR gate 29. If the M5 signal occurs, it is assumed that the end of the label 10 has been reached and the M5 signal is effective to transfer control of the system from the converter 12 to the center bar locator 14.

Now referring to FIGS. 3, 3A and 3B, the block diagram of the circuits for recognizing and identifying the location of the center bar pattern of the UPC symbol in the memory 13 will be explained. Basically, the center bar locator includes a center bar ratio detector 14D, a retry counter 14C, a center bar locator sequencer 14S and a memory address control unit 14M. The center bar locator unit 14 operates in conjunction with the ratio computer 15 for computing the desired ratios that are processed by the center bar locator 14. During the time interval that the center bar pattern is being located in memory, the ratio computer 15 is under the control of the center bar locator unit 14. The operation of the ratio computer will be described more fully hereinafter.

The center bar locator sequencer 14S as illustrated in block form in FIG. 3 includes a sequence for providing the signals identified, as P1, P2, P3, etc. and S1, S2, S3, etc. The sequencer functions such that when it is preset to a specific state all of the other positions of the sequencer are reset. The preset positions are identified in FIG. 3 at the bottom of the sequencer as P1, S1, P9, etc. The input circuit for the sequencer advances the sequencer as it sequentially receives a signal at its step input. The sequencer is controlled and sequentially advanced in response to the clock pulses generated by the clock pulse oscillator 26. The clock pulses from the oscillator 26 are applied as one input to an AND circuit 35. The other input to the AND circuit is derived from the "set" output from the toggle 35T. When a clock pulse is applied to the input of the AND circuit 35 at the time that the toggle 35T is in its "set" state, an output signal will be applied to the step input of the sequencer to advance it to the next successive position. Accordingly, when the toggle 35T is in the set state, the sequencer will be sequentially advanced in response to the reception of each clock pulse at the AND gate 35. The set input of the toggle 35T is controlled by an OR gating circuit 36. The OR circuit receives the overflow signal M5 from the linear time to digital converter 12 in addition to a "retry" signal. It will be recalled that the control of the system is transferred from the linear time to digital converter 12 to the center bar locator 14 in response to the M5 signal. The output of the OR circuit 36 is coupled to the set input of the toggle 35T as well as to the P1 preset position for the sequencer.

The memory address control unit 14M of the center bar locator 14 utilizes and time shares the address counter and register 31 for the memory 13 utilized in the linear time to digital converter 12. It is illustrated in FIG. 3 as a separate circuit element to simplify the explanation of the invention. The memory address register 31 has a "preset" input for setting a desired address into the address register 31 as well as an "incrementing" input for sequentially incrementing the addresses stored in the register. For the purposes of the present invention an address may be preset into the register 31 such as the "start" address entered into the unit 37 and this "start" address is stored in the register to commence a read-out of the memory at that address. For this purpose, the numerical value of a desired address stored in th unit 37 is coupled to an AND circuit 38 in conjunction with the M5 signal (from unit 12) for initiating the sequential search in the memory for the center bar pattern location. The output circuit of the AND circuit 38 is coupled as one input to the OR circuit 39. The other input to the OR circuit 39 is the output of the AND circuit 40 which receives the P13 signal from the sequencer in conjunction with the output signal from the memory address register 31. The output signal from the OR circuit 39 is coupled to a control network identified as a preset and next start address control unit 41. The output of the control unit 41 is applied as one input signal to the AND circuit 42 in conjunction with the P1 signal from the sequencer. The output signal from the AND circuit 42 is in turn applied as one input to the OR circuit 43. The output signal from the OR circuit 43 is applied to the preset input for the address register 31 and thereby may store the address entered at unit 37 in the register.

To the right of the memory address register 31 there is illustrated a control network for subtracting preselected numerical values from the address at which the address register 31 is set. This control network includes a unit 44 for storing a number to be subtracted from the address stored in the address register 31. As illustrated in FIG. 3, the subtrahend is identified as the number 26 stored in the unit 44. The output of the storage unit 44 is applied as one input signal to the AND circuit 45 in conjunction with the P13 signal from the sequencer. The output signal from the AND circuit 45 is applied as one input to the OR circuit 46. The other input to the OR circuit 46 is derived through the control network having a storage element 47 for storing other numerical values (such as the digit 2 illustrated in FIG. 3) to be subtracted from the address stored in the register 31. The element 47 has an output signal coupled to an input circuit for the AND circuit 48. An OR circuit 49 has its output signal coupled to the other input of the AND circuit 48. The input signals to the OR circuit 49 are derived from the sequencer and are identified as the two signals P6 and P11. The output of the AND circuit 48 is coupled as the remaining input to the OR circuit 46. The output of the OR circuit 46 is coupled to the preset input for the subtrahend register 50. The subtrahend register 50 will then store either the number stored in the unit 44 or the unit 47 for further processing. The output signal from the subtrahend register 40 is applied as one input signal to the subtractor 51. The other input to the subtractor 51 is derived from the output of the address register 31. The numerical value of the address provided from the address register 31 has the value stored in the subtrahend register 50 subtracted therefrom and applied and stored in a difference register 52. The signal derived from the difference register 52 is applied as one input signal to the AND circuit 53. The other input signal to the AND circuit 53 is derived from the output signal of the OR circuit 54. The two signals applied to the OR circuit 54 are derived from the center bar locator sequencer 14S and are identified as the two signals P8 and P15. The output signal from the AND circuit 53 is applied as the remaining input signal to the OR circuit 43 for presetting an address into the memory address register 31, i.e., 29-26=3.

The incrementing input of the memory address register 31 is controlled by the output signal from the OR circuit 55. The OR circuit receives the S1, S2 and S3 signals from the center bar locator sequencer for sequentially incrementing the address stored in the address register 31.

The center bar ratio detector 14D is illustrated on the left-hand side of FIG. 3. The ratio detector 14D receives a signal representative of the logarithm of the desired ratio from the ratio computer 15. The logarithmic signal is applied and stored in a log ratio register 56. The numerical value of the log ratio is utilized to address a conversion table stored in a read only memory identified as the unit 57, further identified as the ROM E. The read only memory stores the data from a table for converting the computed logarithmic ratio to numerical value in the decimal number system or any other convenient number system. It will be assumed that the conversion will be to the decimal number system for the purposes of understanding the present invention. Accordingly, the logarithmic ratio signals applied to the ROM E, unit 57, representative of the logarithm of the ratio is converted to a numerical signal representative of the computed ratio. The numeric value signal representative of the ratio that is read out of the read only memory ROM E is applied to a pair of AND circuits 58 and 59. The output signal from the unit 57 is applied to the AND circuit 59 as one input by means of an inverter 60 while it is applied directly, in an unmodified state, to the AND circuit 58. The remaining input signal for each of the two input AND circuits 58 and 59 is the same P2 signal derived from the center bar locator sequencer. Both output signals from the AND circuits 58 and 59 are applied to control a cycle counter 61. The output signal from the AND circuit 58 is applied directly to the incrementing input of the cycle counter 61. The output signal from the AND circuit 59 is applied as one input to the OR circuit 62. The output of the OR circuit 62 is applied directly to a reset input for the cycle counter 61. The remaining input signal applied to the OR circuit 62 is derived from the AND circuit 63. The AND circuit 63 is controlled through an OR circuit 64 that is responsive to the P1 and P8 signals from the sequencer 14S. In addition, an even/odd bit signal derived from a retry counter unit 14C is applied as the remaining input to the AND circuit 63.

The cycle counter 61 has its output applied to a cycle counter decoding network 65 for signalling the decimal value of the count of the counter 61. The output signal of the network 65 is applied as one input to the AND circuit 66 in conjunction with the P4 signal from the sequencer 14S. The output signal from the AND circuit 66 is applied directly to the P9 preset position of the center bar locator sequencer 14S, as illustrated.

The retry counter 14C comprises a retry binary counter 67 for counting the number of attempts the system makes to locate the center bar pattern in the memory and stores the results. The retry counter 67 is reset at its R input by means of the M5 signal from the linear time to digital converter 12. The incrementing input to the counter 67 is responsive to the P3 signal from the center bar sequencer 14S. The even/odd signal from counter 67 is applied to the AND gate 63 for controlling the cycle counter 61 as discussed hereinabove. The count stored in the retry counter 67 is applied directly to a retry decoding network 68 for decoding the output signals from the counter 67 as the counter is counted up. The unit 68 is also responsive to the P5 signal from the center bar locator sequencer 14S. The unit 68 is constructed and defined so that after 10 attempts to locate the center bar pattern in the memory 13 that after the tenth attempt the read is aborted and, accordingly, the output signal from the unit 68 is so identified. This value is selected since a valid symbol would exceed the memory's capacity.

In considering the search for the position of the standard center bar pattern in the memory 13, it is initially assumed that in reading the label 10 that no transitions occurred before the guard bars provided on the UPC symbol on the label 10 so that the center bar pattern would be stored in the memory 13 at addresses 27-31. The first memory location (.phi.) always contains the measurement for a module that is a bar and therefore all even addresses in the memory store bar measurements. This storage arrangement is illustrated in FIG. 3A wherein the coding module of the center bar pattern are identified as A, B, C. and D along with the decoding ratios for determining a valid center bar pattern. Accordingly, the search for the position of the center bar pattern in the memory 13 is always started with address 27. It will be understood that if extraneous data is stored in the memory 13 during a scan, the memory positions will be displaced and the initial attempts to locate the pattern will result in failure. This starting address is stored in the unit 37 for examining the data stored at address positions 27-31 for determining if the known center bar width ratios are satisfied by the stored data for positively locating the position of the center bar pattern in the memory 13. A valid center bar pattern will be located if both of the ratios ##EQU4## compute to one.

Table II delineates the step-by-step sequence to be followed for locating the center bar pattern in the memory.

The basic sequence of events that occur in searching the memory 13 for the correct addresses of the stored center bar data is that at step P1, starting with memory address 27, the values for the modules A, B, C and D are read out of the memory 13. The first ratio ##EQU5## is computed in the ratio computer 15 and further processed through the center bar ratio detector 14D. If it is determined that this ratio is one, the cycle counter 61 will be incremented at P2 time. At the P3 time, the retry counter 67 is incremented to record that a decode attempt is completed. The next sequence is that the information stored in the memory 13, beginning with address 28 through address 31, the new set of data representing the modules A, B, C and D are read out of the memory 13. This results by modifying the start address through sequential steps P6 to P8 and then retrieving the data and computing the ratio through steps P9 through P13.

Table III relates the memory addresses of the register 31 to Table II and indicates the counts of the cycle counter 61 and the retry counter 67 during the sequence of operations detailed in Table II when the center bar pattern is located in the memory on the first attempt.

With this new data, the ratio ##EQU6## is computed and if it is determined that this ratio is one, the cycle counter 61 is incremented. In addition, the retry counter 67 is again incremented. The cycle counter 61 now should signal the count 2 and the decode network will be signalling the decimal digit two. This state of conditions will be recognized at P4 time so that the signal from the AND gate 66 will preset the position of the sequencer to P9. At P9 time, the recording or printing correction character is computed as will be explained hereinafter.

The above description of the operation of the center bar locator 14 assumes that only two successive trys were required to locate the center bar pattern in the initially indentified address positions 27-31. If either of the above attempts at locating the center bar position did not produce a ratio of one, the search must be repeated until two successive ratios of unity are detected. During each of these attempts the retry counter 67 is incremented and if the number of attempts reaches 10, as illustrated in FIG. 3, it is assumed that the valid label would exceed the capacity of the memory 13 and accordingly the read is aborted. In addition, it should be noted that if the cycle counter 61 has not been counted up to 2, and the retry counter 67 produces an "even" output signal at AND gate 63, the cycle counter 61 will be reset at P8 time by the signal from the OR circuit 62. This assures that two successive ratios of unity always begin with a space, a requirement for satisfying the conditions for detecting a valid center bar pattern.

At this point, in the detailed step-by-step operation of the center bar locator 14 for locating the position in memory of the center bar information as represented in Table II, it should be recognized that the steps identified as steps S1-S9 and P9-P13 are performed in the ratio computer 15. These steps derive the information in the address positions of the memory 13 having the modules A, B, C, D and E stored therein and compute the logarithmic ratio signal to be applied to the log register 56 of the center bar ratio detector 14D. These sequencing operations will be described in conjunction with the operation of the ratio computer 15.

Table III records the counts in the cycle counter 61 and the retry counter 67 during the center bar locating procedures when the center bar pattern is identified on the first attempt. This table corresponds to the detailed operation of the sequencer as represented in Table II. In following through the step-by-step sequence represented in Table II, it will be noted that there is a correspondence between the operations delineated in Table II and the values represented in Table III. It should be noted that in sequence P6 of Table II that the subtrahend register 50 is loaded with the decimal digit 2 from the unit 47. This value is subtracted from the address of the memory position from which the last piece of information is derived. It will be recalled that in following the steps for deriving the value for A, B, C, and D from the memory 13 that at the S4 sequence time the last memory position interrogated was number 30. Accordingly, when the numeral 2 is subtracted from the memory position 30 at sequence P8 time, the memory address identified is 28 which corresponds to that indicated in Table III. Address 28 then identifies the starting address for the second cycle in the first attempt for identifying the center bar pattern and the information is derived from addresses 28-31. This information is derived through the sequence of steps P9 through P12, as identified in Table II, corresponding to sequences P8, S1-S3 in Table III. After this interval at sequence P13, the numeral 26 stored in unit 44 is entered into the subtrahend register 50. At the P14 sequence, the numeral 26 is subtracted from the memory address at which the memory is pointing, namely 29, so that the new memory address stored in the register 31 is directed to memory position 3 at sequence P14; see Table III. This number 3, of course, is the memory position in which the A module for the first character to be decoded resides. After this memory position is identified at sequence P15, see Table II, the control of the system is transferred to the character decoder 16. The character decoder 16 will start to decode the stored data beginning with memory position 3 and sequentially forward.

It should be noted that the contents of the center bar ratio read only memory 57 is as represented in FIG. 3B. The logarithm of the ratio stored in this ROM E are permitted to be the value minus 1, 0 or plus 1 to allow for any quantization error. This ROM E is utilized to convert the logarithm ratio signal applied thereto to the decimal number of the ratio. As defined and recorded in FIG. 3A, the resulting ratio output signals represent a ratio of one or a ratio other than one.

To complete the understanding of the center bar pattern search in the memory, Tables IV, V, and VI are included for relating the memory addresses of the register 31 and counts of the cycle counter 61 and retry counter 67 when the center bar pattern is not located in the memory 13 on the first attempt.

Table IV relates the register 31 values of a first retry after a decoding failure. This new attempt commences with address position 29 in memory and follows the same sequence as noted in Table II. The counts of the counters 61 and 67 at the commencement of the "retry" procedure are both at count 2. At P1 time the cycle counter is reset to zero as a result of the signals applied to the AND gate 63. The P1 signal provides an output signal from the OR gate 64 to the AND gate 63 along with the even bit (2) signal from the retry counter 67. The sequence of operations then commence with the data retrieved from address positions 29 through 32 in accordance with the sequential operations of Table II. The cycle counter 61 is counted up at P2 time to one during the first search cycle and again at P2 time during the second cycle. At P3 time during the first cycle, the retry counter 67 is counted up to three and again at P3 time during the second cycle to four. As noted hereinabove, at P12 time two is subtracted from the address register 31 position and after P13 time, twenty-six has been subtracted. Accordingly, the address register 31 is pointing to address 5 for commencing the next decoding attempt at P14 time.

Table V represents the address values of register 31 if during the first attempt, the first cycle results in a center bar pattern that is not one, but is one in the second cycle. This table then corresponds to Table III with the aforementioned exception. The cycle counter 61 will only be counted up to one at P2 time during the second cycle of the new attempt. By referring to Table II, it will be noted that at P8 time the cycle counter 61 will be reset if the retry counter 67 provides an even bit signal to AND gate 63. Since this is true under these conditions, the counter 61 is reset at P8 time to zero. Since a valid center bar pattern has not been located in memory, the sequence commences with sequence S1; see Table II. The search for a valid center bar pattern will now commence at memory address 29 and retry counter at 2.

Table VI represents the values of the address register similar to Table V except the inverse relationship of the cycles. Table VI represents the address locations when an attempt for locating a valid center bar pattern results in a one during the first cycle, but not during the second cycle. During these assumed conditions, the cycle counter 61 will be counted up at P2 time during the first cycle only. As noted in Table II, during the second cycle at P2, the cycle counter is reset to zero. After completing this attempt, the search is repeated starting at memory locations 29 and the retry counter registering two.

Now referring to Table II, once again, it will be noted that if a valid center bar pattern has been located in memory at P4 time, that the sequence skips to P9 time. At P9 time, the recording or printing tolerance correction character computations commence. The sequencer 14S is preset to P9 since at P4 time an output signal is applied to the sequencer from AND gate 66. This signal results due to the decoding network 65 applying a "two" signal to the AND gate 66 which is read out at P4 time.

At P9 time, then, the correction computation commences on the basis of the width measurement stored at the address position denoted for step S1 in accordance with the location resulting in the valid search. If this occurs on the first attempt, the address location is 27, for example. The computations continue during steps P10 through P12 for the modules B, C and D. These computations are performed in the ratio computer 15 and will be described in conjunction therewith. The resulting character correction value is stored in the correction value register 100 of the character decoder 16 to be utilized during the decoding procedures to be described.

Now referring to FIG. 4, the general organization of the ratio computer 15 will be examined. The ratio computer 15 is utilized in conjunction with both the center bar locator 14 and the character decoder 16. The ratio computer 15 is operative on the data read out of the memory 13 for providing the necessary ratio computations and providing an output signal that is the logarithmn of the desired ratio to be used in either the center bar locator 14 or the character decoder 16. The data that is read out of the memory 13 and processed in the ratio computer 15 are width measurements representing the measured values for the modules A, B, C and D of a character. This A, B, C and D data is read out of the memory 13 and stored in individual storage registers A, B, C and D in the ratio computer 15. The data module that a register stores is identified in terms of the data read out from the register. Accordingly, the A module measurement is stored in the A register, and the B module measurement in the B register. The C module measurement is stored in the C register and the D module measurement in the D register. Each of the registers A, B, C and D have their inputs controlled by an individual AND circuit identified as AND circuits 70, 71, 72 and 73 respectively and are arranged left to right in FIG. 4. The data from the memory 13 is coupled in parallel circuit relationship to each of the AND circuits 70-73 as one input to each of these AND circuits. The AND circuit 70 is activated to store the A module measurement by means of the signal S1 from the center bar sequencer 14S. Similarly, the signals S2, S3 and S4 individually activate the respective AND gates 71, 72 and 73.

The output circuits for the registers A-D are controlled by means of one or two AND gates. The A register output circuit is controlled by means of the single two input AND gate 74, while the output circuit from the B register is controlled by means of two, two input AND gates 75 and 76. The output from the C register is controlled by a single AND gate 77, while the D register is controlled by means of a pair of AND gates 78 and 79. The second input to the AND gate 74 coupled to the A register is the output signal provided from the OR gate 80. The OR gate 80 is responsive to the input signals S5, S11, S17A and P9 which provide an output signal from the OR circuit 80 for reading out the data stored in the A register for further processing in the computer 15. Similarly, an OR gate 81 controls one of the input signals to the AND gate 75 for the B register. The OR gate 81 is responsive to the sequencing signals S13, S19B and P11. The output signals from the B register are applied in parallel circuit relationship as one input to both AND gates 75 and 76. The second input to the AND gate 76 is the S5 signal from the sequencer 14S. An OR gate 82 provides one of the input signals for the AND gate 77 for reading out the information out of the C register. The OR gate 82 is responsive to the sequencer signals S7, S13, S17C and P9. The sequencer signal S7 controls the transfer of the D register data through the AND gate 78. The D register data is coupled in parallel to both of the AND gates 78 and 79. An OR circuit 83 controls the input signal to the second input to the AND gate 79. The OR gate 83 is responsive to the sequencer signals S11, S19D and P11. The data stored in the registers A, B, C and D (and the memory 13) is not destroyed since a number of attempts may be required to decode the recorded symbol. The raw measurement data stored in the registers are merely read out for processing in the ratio computer 15. The data stored in the registers A, B, C and D is applied to a two input binary adder 84. One of the inputs to the adder 84 is controlled by an OR gate 85 and the other by an OR gate 86. The OR gate 85 is responsive to the output signals from the AND circuits 74, 75 and 78. The OR gate 86 is responsive to the output signals from the AND circuits 76, 77 and 79. The output signals from the adder 84 represent the linear sum of the width measurements of the two modules applied thereto or the sum of the signals presented to it by means of the OR gates 85 and 86.

The signal derived from the adder 84 is utilized to address a table stored in a read only memory identified as ROM A in FIG. 4. The data stored in ROM A is a conversion table that converts the linear sum signals to a binary coded decimal number that is the logarithmic value of the sum signal. A method for selecting the base for the logarithms is disclosed in the copending patent application bearing Ser. No. 638,056 and assigned to the same assignee as the present application, now U.S. Pat. No. 4,058,708. The disclosure of this copending application is incorporated herein by reference and resort to the teaching of said application Ser. No. 638,056 may be had if necessary to the understanding of the present invention. The sum signal is utilized as the address signal for reading out ROM A in accordance therewith. The signals read out of the ROM A are stored in a log register 87 coupled to receive the binary coded output signals from ROM A. The register 87 has an 8-bit capacity and is illustrated in FIG. 4 as having a left and right half, each storing four bits. The right half of the register stores the binary bits 2.sup.0 through 2.sup.3, while the left half stores the binary bits 2.sup.4 through 2.sup.7.

It will be recalled that the minimum linear value selected for the counter 28 was seven and therefore values below seven need not be considered in Table VII. The logarithmic values represented in Table VII are arbitrarily initiated at zero and restart with zero after the value of 15 is reached. When the correction character is calculated, the ratios A/B or C/D are computed as ##EQU7##

The output signals from the two portions of the logarithm register 87 are controlled for further processing through the pair of AND gates 88 and 89. The left-hand portion of the register 87 has its output signals applied as an input to the AND gate 88, while the right-hand portion of the register 87 has its output signals applied as an input signal to the AND gate 89. The four bits comprising the input signals to the AND gates 88 and 89 represent the decimal values recorded in Table VII. An OR gate 90 controls the second input to the AND gate 88. The OR gate 90 is responsive to the signals from the sequencer 145 identified as S6, S8, S12, S14, S18 and S20. Similarly, an OR gate 91 controls the other input to the AND gate 89. The OR gate 91 is responsive to the sequencer signals P10 and P12. An OR gate 92 controls the application of the output signals from the AND gates 88 and 89 and is coupled thereto. The output signal from the OR gate 92 is coupled to a pair of AND gates 93 and 94 in parallel circuit relationship. The other input to the AND gate 93 is controlled by means of an OR circuit 95. The OR circuit 95 is responsive to the sequencer signals S6, S12, S18, and P10. An OR gate 96 controls the other input to the AND circuit 94. The OR gate 96 is responsive to the signals S8, S14, S20 and P12. The AND circuits 93 and 94 control the data that is entered into the individual log registers E and F, respectively. Each of the registers E and F are 4-bit registers for storing values of the logarithms of the sums of the measured widths, such as the logarithm of the sum A+B, for example. The registers E and F each have their output circuits coupled for transferring their contents to a subtractor 97. The subtractor 97 subtracts the logarithm of the two sums stored in the registers E and F, the register F value is subtracted from the register E value, and provides an output signal that is the log of the desired ratio signal. The subtractor 97 is enabled under the control of an OR gate 98. The OR gate 98 is responsive to the sequencer signals S9, S15, S21 and P13. The signal from the subtractor 97 is coupled to the center bar locator 14 or to the character decoder 16 in accordance with the use made of the ratio computer 15.

With the above structure of the ratio computer 15 in mind, the operation of the ratio computer will now be further examined. The information from the memory 13 representing the modules A, B, C and D are entered into the corresponding module registers in response to the generation of the sequencing signals S1, S2, S3 and S4 are delineated in Table II hereinabove. Once all of the A, B, C and D data is entered into the registers, the sequencing continues as indicated in Table II so that the A data and the B data are applied to the adder 84 to obtain the linear sum of these measured widths. This results due to the generation of the sequence signal S5 appearing as an input to the OR gate 80 for reading out the A register through the AND gate 74 and the OR gate 85. The same sequencing signal S5 transfers the B register data through the AND gate 76 and the OR gate 86 to the adder 84. The linear sum derived from the adder 84 addresses the ROM A to read out the logarithmic value of the sum and which sum is stored in the register 87. As noted in Table II, this data is transferred into the E register upon the generation of the S6 sequencing signal. The S6 sequencing signal provides an input signal to the AND gate 88 for transferring the data from the left half of the register 87 through the OR gate 92 and the AND gate 93 to the E register. It will be noted that the AND gate 93 is responsive to the output signal from the OR gate 92 in combination with the output signal from the OR gate 95 which latter gate produces the output signal in response to the reception of the S6 signal at its input.

The next sequence as noted in Table II is the generation of the S-7 signal and that signal is effective through OR gate 82, AND gate 77 and OR gate 86 to apply the "C" data to the adder 84. At the same time, The S7 signal transfers the D data from the D register to the AND circuit 78 and the OR circuit 86 to the other input to the adder 84. In the same fashion this data is transferred from the adder 84 by means of the ROM A and the logarithmic register 87 to the F register. The S8 sequence signal, as noted in Table II, will transfer the logarithmic value of the sum of the C and D data by means of the AND gate 88, the OR gate 92 and the AND gate 94. This results from the coupling of the S8 signal to the OR gate 90 and the OR gate 96 for activating the AND gates 88 and 94. Accordingly, at S9 time in the sequencing operation, the subtractor 97 is activated to subtract the data in the F register from that in the E register to provide the desired log of ratio signal from the subtractor 97.

Now referring to FIG. 5, the general organization of the character decoder 16 will be examined. The character decoder 16 as mentioned hereinabove operates in conjunction with the ratio computer 15 and receives the input signal from the ratio computer which is the logarithmn of the ratio computed and is stored in the log ratio register 101 for the character decoder 16. It will be recalled that during the operation of the ratio computer 15 in locating the center bar pattern that the printing error correction value was also calculated and transferred to the character decoder. It will be assumed that this value is stored in the correction value register 100 for the decoder 16. The correction value register 100 has the correction value entered therein under the control of the AND gate 102. The AND gate controls the input to the register 100 and has its input connected to the output of the log ratio register 101 and the signal P14 from the center bar locator sequencer 14S illustrated in FIG. 3.

The table stored in ROM A comprehends the character correction resulting from printing the UPC symbol on a label or the like. Accordingly, the correction value is calculated in the ratio computer 15 after a valid center bar pattern is located and prior to decoding the characters of the symbol. The correction value is stored in the register 100 of the character decoder 16.

The correction value is computed in accordance with the present invention by examining the standard pattern having the known 1:1 ratio as to bars and spaces. For the purposes of decoding the UPC standard symbol the standard pattern that is examined is the center bar pattern widths. The correction value is obtained by measuring the actual or printed ratio of the center pattern bars and spaces. The ratio has been selected to include two bars and two spaces for minimizing the effects of local printing irregularities. In the standard UPC symbol, the ratio is defined by the two center bars over the two center spaces, or the ratio ##EQU8## For a nominal symbol these ratios will be one. For an over-printed symbol or label they will be greater than one and for an under-printed label they will be less than one. Stated differently, the ratio is defined by the widths of two dark bars over the widths of two light bars. Since the known ratio, or the width of a bar and space should be the same, any resulting ratio other than one will require a correction value to be combined with the stored, measured values of the modules A, B, C and D.

The correction computation in the sequence of events commences at P9 time by the reading out of the data for the two center bars from registers A and C. These width measurements are read out at P9 time by the P9 signal appearing at OR gate 80 and OR gate 82. They are applied to adder 84 through AND gate 74 and OR gate 85 and AND gate 77 and OR gate 86 respectively. The logarithmn of the resulting sum is read out of ROM A and stored in register 87. At P10 time, the register 87 has its contents transferred to the E register. This results from the signal P10 applied to the OR gates 91 and 95 which correspondingly activate AND gates 89, OR gate 92 and AND gate 93. Similarly, the B and D registers are read out at P11 time in the sequence. These width measurements are coupled to the input of adder 84 as a result of the P11 signal being coupled to the OR gate 81 and the OR gate 83. At P12 time, the log of the sum signal is transferred from register 87 to the F register. This results from the coupling of the P12 signal to OR gate 91 and OR gate 96. At P13 time, the subtractor 97 is enabled as a result of the P13 signal being coupled to the OR gate 98. The resulting logarithm of the correction signal is loaded into the correction value register 100 for the decoder 16 to be utilized for decoding by means of the aforementioned secondary ratios.

It should now be noted that the decode sequencer 14S illustrated in FIG. 5 is the same sequencer that is illustrated in FIG. 3 solely for the purpose of the center bar locator 14 and is merely duplicated in FIG. 5 to simplify the consideration of the operation of the decoder 16. It will be recognized by those skilled in the art that the sequencer could be time shared in a decoding system.

The log ratio register 101 output signals are applied to a primary ratio read only memory identified as the ROM B in FIG. 5. This ROM B stores a table for converting the logarithmic value of the ratios for the primary ratios generated during the decoding process or to a numerical valve representative of one of the primary ratios 4/3, 5/2, 2/5 or 3/4.

Table IX relates the addresses of the ROM B to the output data for representing the primary ratios as indicated. It should be noted that when the output data of the ROM B is "2" the primary ratio is 4/3 and when the output data is "1" the primary ratio is 3/4.

The output data derived from ROM B is applied in a parallel circuit relationship to a pair of AND circuits 103 and 104. The AND circuit 103 is effective for transferring the ROM B output data therethrough in response to the S10 signal from the sequencer 14S. For this purpose, the output from the AND circuit 103 couples this data into the R1 register for storing the first primary ratio. Similarly, the AND circuit 104 is controlled by means of the signal S16 to transfer the ROM B output data to the R2 register. The R2 register will store the second primary decoding ratio. The output circuits from the AND circuits 103 and 104 are also applied to an OR circuit 105 for controlling a decoding circuit 106. The decoding circuit 106 indicates an error when a primary ratio data signal from ROM B is 4, as noted in Table IX.

The output signals of the registers R1 and R2 are coupled to a ratio to binary coded decimal ROM C. The data output signal of register R1 is applied to the b.sub.2 and b.sub.3 bits of ROM C, while the output signal of the R2 register is applied as the b.sub.0 and b.sub.1 bits of the ROM C.

The stored contents of ROM C is in accordance with Table X. This table relates the two primary ratios and the secondary ratios to produce the desired character decoding in terms of the decoded decimal value as indicated in the data column and whether the data is a forward or a reverse read bit. The zero, .phi., bit identifies a forward number while a one, 1, bit identifies a reverse number. Forward is utilized in the sense illustrated in FIG. 1A of a left to right scan and reverse is a right to left scan. Both right and left characters decode as "forward" in a left to right scan and "reverse" in a right to left scan. The binary coded decimal output of the ROM C is applied to an AND circuit 107 which is controlled by means of signal S23 from the sequencer. The output of the AND circuit 107 is a binary coded decimal character having a direction bit which is coupled to the validity check circuit.

As will be recalled prior to generating the secondary ratio for decoding a character, the correction value character must be added or substracted to the measured widths for the modules A, B, C and D. In the left-hand portion of the label 10 the correction value is added to the measurement data and in the right half of the label, it is subtracted from this data. For this purpose, a binary adder 108 is provided for adding the information to the left-hand characters. The operation of the adder 108 is controlled by an AND gate 109. The AND gate 109 activates the adder 108 in response to a "left" signal and the S22 signal from the sequencer. The adder 108 combines the signals from the log ratio register 101 with the signal from the correction value register 100 and provides the corrected module data signal on the lead wire 110 to an OR circuit 111. Similarly, for the right half of the UPC symbol a subtracter 112 is provided. The subtracter 112 is enabled by means of an AND circuit 113 which is responsive to a "rite" signal and the S22 signal from the sequencer 14S. The subtractor 112 combines the data from the log ratio register 101 with the data from the correction value register 100 by subtracting the correction signal from the ratio signal. The corrected module value signal appears on a lead wire 114 that is applied as a second input to the OR circuit 111. The output signal of the OR circuit 111 is applied for addressing the secondary ratio ROM D.

The contents of the secondary ratio ROM is represented in Table XI. The output signals of the ROM D define whether the ratio A/B or C/D is 2/1 or 1/2 for the purposes of resolving the ambiguity. The outputs of the secondary ratios ROM D are identified as b.sub.0 and b.sub.1 outputs. If the b.sub.0 output from the ROM D is 1, the ratio is 2/1 and if the b.sub.0 output is zero, the ratio is 1/2. Other output signals are the b.sub.1 signals and all have the value two to denote a decoding error; see Table XI. The b.sub.1 output signal from the ROM D is coupled as an input signal to an AND circuit 115. A second input to the AND circuit 115 is provided by the output signal from the element 116A further identified as the R.sub.2 equals 1 or 2 element. The input signal for the element 116A is coupled from the output of the R2 register. The b.sub.0 ROM output signal is coupled to the b.sub.4 bit of the ROM C.

For the purpose of resolving any ambiguity, it is necessary to select one of the two desired secondary ratios in accordance with whether the first primary ratio, or the ratio stored in the R1 register is 3/4 or 4/3. To this end, the output of the R1 register is coupled to a pair of decoding elements 116 and 117 for storing the R1 value for decoding purposes. When the decoding element 116 signals that the R1 register equals 1, the primary ratio is 3/4 and the selected secondary ratio is A/B. When the decode register 117 signals that the R1 register equals 2, the primary ratio is 4/3 and the selected ratio is C/D; see FIG. 1C. Each of the output circuits for the decode registers 116 and 117 are applied as input signals to an OR gate 118. The output of the OR gate 118 is coupled as the third input to the AND circuit 115. Accordingly, when R1 equals 2 or 1 and R2 equals 2 or 1, and the b.sub.1 signal of two appears at the AND circuit 115, an error will be signalled from the AND circuit 115. The output signals from each of the decode registers 116 and 117 are coupled in a parallel circuit relationship to an individual pair of AND circuits 119 and 120 and 121 and 122 respectively. The AND circuit 119 is responsive to the S17 signal and the R1 decode so that it produces a signal identified as the S17A signal at its output which is coupled to the ratio computer 15. Similarly, the other input to the AND circuit 120 is responsive to the S19 input signal for producing the output signal S19B to the ratio computer 15. The AND circuit 121 and the AND circuit 122 are each responsive to the output of the decode register 117 in parallel circuit relationship. The AND circuit 121 is also responsive to the S17 sequencer signal to produce the output signal S17C. Similarly, the AND circuit 122 is responsive to the S19 signal to produce the S19D signal which is coupled to the ratio computer 15.

Since the character decoding unit 16 decodes both the left-hand and right-hand UPC symbol in sequences through the 6 left-hand (0-5) characters normally, at character 6 time the center bar pattern commences and would be decoded. To prevent decoding the central pattern, the memory address is advanced 5 positions. The decoding may then commence at the first right-hand character. For this purpose a character counter 123 is provided which counts the characters as they are sequentially decoded in response to each of the S24 signals from the sequencer. The counter 123 provides an output to decode register 124 for indicating that 6 characters have been decoded. This unit 124 is further identified as the character count=6 decode. Similarly, a second register 125 is responsive to the 12th count of the counter 123 to indicate that the symbol has been completely decoded. The decode register 124 provides a CH6 signal for resetting the toggle element 126 to produce the "rite" signal. The decode register 125 has its output applied to the reset terminal of the toggle 21. The toggle 21 has its set terminal coupled to be responsive to the P15 signal from the center bar sequencer 14S illustrated in FIG. 3. The setting of the toggle 21 provides a signal to the AND circuit 35. The P15 signal is also applied to reset the character counter 123 and to set the toggle 126. The setting of the toggle 126 provides the "left" signal to the AND circuit 109. The P15 signal is also coupled to the OR circuit 127 for resetting the decode sequencer 14S (FIG. 5). The sequencer 14S is controlled as in the previous sequencer by means of the AND circuit 35 coupling the clock pulses to the stepping input of the sequencer in response to the "set" state of the toggle 21. The OR circuit 127 is also provided with an input signal from the AND circuit 128 for resetting the sequencer. The AND circuit 128 is responsive to the CH6 signal from the decoding register 124 and the S5 sequencing circuit. The output of the AND circuit 128 is also coupled to the OR circuit 129 for providing a signal M3 for incrementing the memory address. The OR circuit 129 for this purpose is also responsive to the S1, S2, S3 and S4 sequencing signals for incrementing the memory address of the other four positions.

With the above structure of the character decoder 16 in mind, the step-by-step operation can now be examined. The sequential operation will be examined in conjunction with Table VIII. Initially, it will be recalled that during the center bar locating sequence that the correction value for correcting the measured widths of the modules was generated. Accordingly, at the P14 time in the center bar locating sequence, the AND gate 102 for the character decoder 16 was activated and the logarithm of the tolerance correction character from the register 101 was transferred into a correction value register 100 prior to the actual character decoding operation commencing. At the P15 time in the center bar locating sequence the control of the system was transferred from the center bar locater 14 to the character decoder 16 so that the decoding of the character of the UPC symbol will commence; see Table II.

At this point, the logic for making the correction to the measured widths of the modules should be understood. For both a forward and reverse scan of the UPC symbol, the tolerance correction character or value is added to the measured modules widths for those modules in the left-hand field of the symbol and is subtracted from the measured widths in the right-hand field. In a reverse scanning operation, the correction is made before inverting the reverse scanned characters. This logic applies when the correction value has been computed from a bar/space ratio.

Since the character decoder 16 is dependent upon the ratio computer 15, certain operations for the purposes of decoding are identical to those required for locating the center bar pattern; see Table VIII. Accordingly, the initial sequencing steps S1-S9 are identical to those disclosed in conjunction with the operation of the center bar locator 14 for producing the desired logarithm of the decoding ratios that are stored in the register 101. Accordingly, after the S9 sequencing step occurred, the primary ratio computation, log ##EQU9## is transferred from the ratio computer 15 to the decoder 16. This logarithmic signal addresses the ROM B and provides a numerical output signal representative of the primary ratio in accordance with Table IX. At S10 time in the sequence, the data read out of the ROM B is stored in the R1 register. Similarly, during the sequence steps S11-S16, the second primary ratio is generated in the ratio computer 15 and transferred to the register 101 of the decoder 16. This second primary ratio log signal represents the ratio ##EQU10## At the end of S16 time, the data read out of ROM B is stored in register R2.

With both primary decoding ratios generated and residing in registers R1 and R2, the decision as to which secondary ratio is to be utilized for the purposes of resolving the ambiguity must take place; see FIG. 1C. The ratio A/B or C/D is computed during each decoding operation whether or not it is required. For this purpose, the contents of decode registers 116 and 117 are examined to determine if the first primary ratio is 3/4 or 4/3. The data stored in the registers 116 and 117 is in accordance with Table IX. It should now be noted that if the data signal stored in either register 116 or 117 is four (R1 or R2 is four) an ERROR signal is generated and the control of the system is returned to the center bar locator 14. An ERROR signal is generated by the OR gate 118 sensing the "four" stored in the register 116 or 117 and providing an input signal to the AND gate 115. The b.sub.1 signal from ROM D will be true when it signals a "two" as indicated in Table XI.

If there is no error at this point, the selection of the correct secondary decoding ratio will continue in accordance with sequence step S17. If the register 116 signals that R1 is equal to 1, the ratio is 3/4 (Table IX) and then the A module is selected or the A register in the ratio computer 15 is interrogated. For this purpose, the decoder 16 generates a signal S17A in response to the S17 sequencing step for reading out the contents of the A register in the ratio computer 15 by means of the OR circuit 80 and the AND circuit 74; and the OR circuit 85 to the adder 84 of the ratio computer. If the register 117 signals that R1 is equal to 2 then the ratio is 4/3 (Table IX), the ratio computer 15 receives an S17C signal during the S17 sequence and which S17C signal is applied to the OR circuit 82 and enables the AND circuit 121. This will read the data out of the C register in the ratio computer 15 through the OR circuit 82, the AND circuit 77 and the OR circuit 86 to the adder 84. At step S18, the logarithm signal of the measured module width A or C, in accordance with the previous selection is loaded into the E register of the ratio computer 15. The same procedure occurs at sequencing time S19 to read out either the B register or the D register to the adder 84 in accordance with whether R1 is 1 or 2. At step S20 the resulting logarithm signal for the modules B or D is loaded into the F register of the ratio computer 15. At S21 time, the contents of register F is subtracted from the contents of register E to provide the log of the ratio signal in the register 101. At S22 time, the tolerance correction value previously stored in register 100 is added or subtracted in accordance with whether the left-hand or the right-hand field characters are being decoded.

If the correction value is to be added to the measured width, the logical conditions for this addition must be satisfied. At P15 time of the center bar locating sequence, the toggle 126 was "set" for providing a "LEFT" output signal that is in the true state. This "LEFT" signal is coupled to the AND gate 109 and upon the occurrence of the S22 time the adder 108 is enabled. The contents of the log ratio register 101 is added to the contents of the correction value register 100 and the corrected module width signal appears on the lead wire 110 and is coupled to the OR gate 111.

If the correction value is to be subtracted to the measured module width, the logical conditions for a subtraction must be satisfied. Assuming an initial forward scan, after the left-hand field has been decoded, the character counter 123 has been counted up to six. This six count is decoded by the character six decoding network 124 to provide an output signal indicative of the six counts. This output signal is coupled to the reset input of the toggle 126 to produce a "RITE" output signal that is in the TRUE state. This RITE signal is coupled to the AND gate 113 and upon the occurrence of the signal S22, the subtractor 112 is enabled. The contents of the correction value register 100 is subtracted from the contents of the log ratio register 101 and the corrected module width signal appears on the lead wire 114 and is coupled to the OR gate 111.

When a corrected module width signal for either a left-hand or a right-hand field appears at the input of OR gate 111, the output signal thereof addresses the secondary decoding ratio ROM D. The signals read out of ROM D are in accordance with Table XI. With the secondary ratio data read out of ROM D, the data signals representative of a valid 2/1 or 1/2 secondary ratio is applied to the bit 4 (b.sub.4) position of the ROM C along with the data from the R1 and R2 registers. The R1 data is applied to the b.sub.2 and b.sub.3 positions of ROM C and the R2 data to the b.sub.0 and b.sub.1 positions thereof. The contents of the ROM C corresponds to the data represented in Table X. In relating this Table data to the circuit operation of the character decoder 16, it will be noted that since the secondary ratio value is applied to the highest order address bit or position of ROM C, the characters that do not require a secondary ratio to be unambiguously decoded appear twice in ROM C. For these characters the secondary ratio is a "don't care" bit and can be ignored.

The values recorded in Tables I and X can be readily translated to reveal the decoding of the recorded characters in terms of the primary and secondary ratios. If the primary ratios decode to 2/5 and 3/4, the decoded character is defined solely by these two primary ratios and the character is unambiguously a forward 4, Table I and address 1 in Table X. If the two primary ratios are 3/4, 3/4, a secondary ratio must be examined as a reverse 7 or a reverse 1 may result; Table I. If the secondary ratio of A/B results in the ratio 2/1, a reverse 7 is decoded. Similarly, if the secondary ratio is 1/2, reverse 1 is unambiguously decoded.

The Table X contents relate the b.sub.0 -b.sub.4 address positions of ROM C for both a forward and reverse scan and the secondary ratios of 1/2 and 2/1. The "Address" column of Table X represents the decimal equivalent of the binary coded bits b.sub.0 -b.sub.4. The bits b.sub.0 -b.sub.3 will have the values 0,1,2, or 3 for a valid primary ratio as noted in Table IX. The b.sub.4 bit will be either 1 or 0 for a valid secondary ratio as noted in Table XI. The F/R column of Table X identifies whether the decoded data character is a forward or reverse bit. The .phi. symbol signifies a forward bit and the 1 a reverse bit.

At the S23 sequence, the addressed memory location in ROM C is coupled through AND gate 107 to produce the binary coded decimal decoded character having the direction bit as discussed hereinabove. At this time, the output signal from the AND gate 107 is transmitted to the validity check circuit 17. The remaining step in the decoding procedure is S24. The S24 signal increments the character counter 123 to the count of twelve. This 12th character is decoded in the unit 125, which signals a "12" output signal. With the register 125 signalling that the 12th character has been decoded, the toggle 21 is reset to disable the AND gate circuit 35 and thereby the decoder sequencer 14S. The character decode sequence may now be restarted.

The characters that are decoded in accordance with Table X must be consistent either for a forward or reverse scan. This effectively satisfies the parity check requirements referred to in the UPC standard symbol specifications. To provide a valid, decoded output there must be twelve valid characters and the check digit must verify. If the read direction indicators are not consistent and the check digit test fails, control is returned to the center bar locator 14 to attempt to find another position.

In following through the operation of the system various conditions have been mentioned herein, wherein an invalid decoding operation may return the control to the center bar locator 14 to reexamine the memory for a valid center bar pattern. In addition, it has been noted that a read will be aborted when the retry counter 67 has been counted up to ten (5 attempts and 2 cycles per attempt). Other conditions that will abort the read are:

(1) If any of the data from the wand 11 provides module width measurements that when added together or summed (A+B, C+D,---) overflow 8 bits cause an aborted read.

(2) If any of the character ratios or A/B or C/D ratios fall into the regions marked "Error" in Tables IX and XI the read is aborted in addition to the conditions noted in Table II.

It should be appreciated by those skilled in the art that the circuit elements described herein are well known in the art and commercially available thereby permitting the system to be constructed on the basis of the above disclosure. The element functions that have been repeated herein for purposes of explanation can be performed by a single element that may be time shared in an operational system.

The improvement disclosed herein has advanced the state of the art with respect to reading and decoding a high density, linear bar code of the type of the standard Universal Product Code symbol and derivatives thereof that permit decoding ambiguities to be simply resolved and is highly tolerant to manual accelerations and of recording or printing tolerances. The improvement is directly applicable to high speed laser scanners as well as portable, battery operated hand-held scanners.