Composite code symbology

[0001] This application derives priority from U.S. Provisional Application Ser. No. 60/183,509, filed on Feb. 18, 2000, which is incorporated herein by reference.

[0002] The present invention relates to an composite code having two parts encoded using different coding schemes and located adjacent to each other. The two parts are associated by a link-flag adjacent at least one of the two parts.

[0003] Optically encoded indicia, such as bar codes are well known in the art. Today, bar codes are used in just about every type of business application: point-of-sale, retail, warehousing, etc. Bar codes are printed on substrates, individual items and on containers enclosing a number of items. Bar codes carry information encoded into bars and spaces of various width, arranged in a predetermined patterns. The bars and spaces are made up of unit elements called modules. A module has a specified height and width. Width is usually called the horizontal dimension of the module. When a bar code is scanned by a laser scanner, bar code modules are usually crossed by the scanning beam along its horizontal dimension. The relative size of a bar coded label is determined by the type of coding used, as are the actual sizes of the label's individual bars and spaces. The size of the bar code is also directly proportional to the amount of information that is stored in that bar code. Conversely, the amount of information is constrained by the size limitations on the bar code. Bar codes usually get scanned via a bar code scanning system, and the encoded information gets extracted and decoded by the system's processing means. Bar code reading can be accomplished by scanning across the bar code with a laser scanner, a wand, a charged coupled device (CCD), or some other solid-state imaging device (SSI). Bar code reading systems are known in the art and have been disclosed, for example, in U.S. Pat. Nos. 4,251,798; 4,360,798; 4,369,361; 4,387,297; 4,409,470 and 4,460,120 and are incorporated by reference herein.

[0004] A number of different one-dimensional (1-D) bar code symbologies (encodation schemes) exist. These symbologies include UPC/EAN, Code 39, Code 128, Codabar and Interleaved 2 of 5. Due to their low information density storage capacity these types of bar codes can carry only a limited amount of information, on the order often to twenty letters or digits. This information is usually an index to a file or a database where more comprehensive information is stored.

[0005] Some bar codes are referred to as belonging to the (n,k) family. A code of (n,k) type uniquely represents characters by a string of n modules containing k bars and k spaces. The UPC symbology is an example of a (7,2) code, i.e., n7 and k2.

[0006] Two-dimensional (2-D) bar codes carry more information per substrate area than linear bar codes. Some two-dimensional bar code symbologies are just an extension of one-dimensional bar codes, in that they are formed by stacking rows of one-dimensional bar codes and typically placing a horizontal line between each row. In order to keep the same vertical dimension of the overall bar code, the height of each row is smaller then the normal height of a one-dimensional bar code. U.S. Pat. No. 4,794,239.

[0007] There exists a number of different two-dimensional code symbologies. Some of the symbologies are: Code49, 16K Code, Codabar, Supercode, Matrix code, etc. The PDF417 symbology is one type of two dimensional bar code symbology that is used when we need to encode a greater amount of information within a limited amount of space, thus giving us a higher information density encodation scheme. U.S. Pat. No. 5,304,786 which is incorporated by reference herein. A stacked two-dimensional bar code, such as PDF417, uses a row/column spatial arrangement of codewords. The information is usually broken up and encoded into individual codewords which, when decoded, are used to recompose the encoded information. PDF417 symbology has a number of variants. MicroPDF417 symbology is one of the variants of PDF417 symbology and is described in detail in AIM International Symbology Specification-MicroPDF417.

[0008] When two different symbologies are used to encode different parts of a given data, the resultant symbol is called a Composite code symbol. Thus, composite symbol is a hybrid consisting of symbols encoded using more then one encoding scheme. For example, product identification number may be encoded in a 1D bar code and supplementary product information may be encoded in a linked 2D bar code located adjacent the 1D bar code. Many companies would like to adopt Composite (1D/2D hybrid) symbologies, so that they can stay compatible with their installed base of 1D scanners (readers), and upgrade the scanning equipment over time (at their own pace) to also capture supplementary information (such as a serial number) in a linked 2D portion. For this to really work without disrupting the current application, the 1D barcode must remain compatible with old generation scanners, while adding an encoded link flag so that a new generation scanner knows that additional information is printed adjacent (above or below) the 1D bar code symbol. Without a link flag, a scanner (unless it captures a full two-dimensional 2D image) would decode the linear symbol and transmit the data from it, but fail to recognize that additional data was printed in an associated 2D symbol. A standard link flag has been defined for the 2D portion of a composite bar code symbol (for symbologies such as PDF417 and MicroPDF417), so the data encoded in the two-dimensional (2D) portion of a composite bar code won't accidentally be transmitted without the data in the accompanying one-dimensional (linear) bar code. But, linkage in both directions is needed, for a truly robust system.

[0009] In particular, UPC/EAN, Code 39, Codabar, and Interleaved 2 of 5 do not provide a means of adding a link flag character without changing the data that an old scanner would transmit.

[0010] An optical symbology is needed that provides the means for a code reader to recognize that a 1D code is a part of a composite symbol and that another part of the composite symbol must be adjacent to the 1D code, and that both 1D and 2D bar codes must be decoded in order to obtain full information contained within the composite symbol.

[0011] The present invention solves this problem by printing a link flag character outside of the linear barcode (preferably, immediately adjacent to its trailing white Quiet Zone). An old generation scanner would not decode this character (because it is outside the standard symbol), but a new generation scanner can be reprogrammed to look past the Quiet Zone for an additional character pattern. Different patterns could be assigned (and a list maintained by a standards organization such as AM) to represent different application data sets and rules, and/or to denote which 2D symbology (e.g., PDF417 vs. MicroPDF417) is linked to the accompanying linear symbol.

[0012] FIG. 1 illustrates a composite code symbol of the preferred embodiment of the present invention including a link-flag;

[0013] FIG. 2 illustrates a composite code symbol of the preferred embodiment of the present invention including an extended link-flag.

[0014] The preferred embodiment discloses a new composite code symbology in a form of Code 39/MicroPDF417 Composites (1D/2D composite), and the encoding and decoding algorithms for Code 39/McroPDF417 Composites using the Telecommunications Industry Forum (TCIF) application as an example. The TCIF standard specifies how TCIF members can add a Serial Number (and additional supplementary information) to a CLEI-coded product, when that product is currently marked with a Code 39 representation of the common language equipment identification (CLEI) code as a six-digit equipment catalog item (ECI) number. The supplementary information is encoded in a MicroPDF417 symbol that is logically linked to the Code 39 symbol, and printed above it. Note that, for a longer linear symbol, a PDF417 could be used above the linear symbol, instead of a MicroPDF417, to most efficiently utilize the area above the linear symbol.

[0015] Existing scanning equipment will still be able to scan the CLEI code and transmit the six-digit ECI as before. New scanners can be modified to recover both the CLEI code and the supplementary information, and to transmit the entire data according to predetermined format, for example Format 06 of the ISO/IEC 15434 2D syntax specification, using Federation of Automated Coding Technologies (FACT) Data Identifiers (DI's).

[0016] 1. Data Format of the Preferred Embodiment

[0017] The TCIF's Code 39 Composite application specifies the use of two required data elements, which may optionally be followed by additional data elements.

[0018] a six-digit ECI number (representing a CLEI Code). When encoded in a stand-alone Code 39 symbol, it is transmitted verbatim. When encoded in a Code 39 Composite, the transmission of the six-digit number is part of a Format 06 envelope, and the ECI number is prefixed by a pre-assigned Data Identifier. An example of a pre-assigned Data Identifier if 6P.

[0019] A Serial Number, prefixed by another Data Identifier of S (predetermined choice, to be decided by TCIF). Note that the use of AI's such as 21 would not be appropriate, because no EAN.UCC primary product identifier is being encoded. This serial number may be alphanumeric, and may be up to 18 characters long (and up to 22 characters long, if starting with a four-character manufacturer code).

[0020] Additional data items, such as a Country of Origin, may optionally follow the Serial Number. Any such additional items must each be preceded by an ASCII^G_S character and a Data Identifier.

[0021] 2. Encoding a Code 39 Composite for the TCIF Application

[0022] Special encoding software is required to implement the application-specific rules for use of Code 39 Composites. Encoding software designed for this TCIF application needs to perform the following steps:

[0023] Encode the six-digit ECI number as a standard Code 39 symbol (per the AIM USS for Code 39).

[0024] If no serial number or other supplemental data is required, then encoding is completedo not perform the remaining steps of this section.

[0025] If supplemental data needs to be encoded, first validate the input data, to ensure that it fully complies with the rules of Section 2 above. If the data matches the TCIF format, proceed with the remaining steps.

[0026] Encode a linkage flag immediately to the right of the Code 39 symbol's right Quiet Zone. For the TCIF application, this linkage flag is the single Code 39 symbol character (5 bars and 4 spaces) representing the letter T. An additional Quiet Zone (minimum 1X) is required to the right of this linkage flag. While the preferred embodiment specifies locating the link-flag immediately to the right of the 1D bar code, in another embodiment the link-flag can be positioned anywhere adjacent to the 1D symbol as long as there is no print in between the 1D symbol and the link-flag.

[0027] Encode the supplemental data in a four-column MicroPDF417 symbol above the Code 39 symbol. Alignment and spacing between the two components are not critical. To print the smallest possible Composite, the MicroPDF417 symbol can be printed directly adjacent to the top edge of the Code 39 symbol, and the first (leftmost) bar of the MicroPDF417 symbol can be aligned with the first interior space of the Code 39 symbol. The data is encoded into the MicroPDF417 symbol as follows:

[0028] Skip the leading Data Identifier S, and encode the remaining data into a series of codewords, using the encodation rules specified in MicroPDF417specification, which is incorporated herein by reference.

[0029] Encode this series of codewords into a four-column MicroPDF417 symbol whose first codeword is 918 (the linkage flag specified in the AIM Code 93i specification), and whose second codeword is a mode latch to Alpha, Numeric or Byte mode, depending on data content. The MicroPDF417 symbol is encoded according to the AIM specification for MicroPDF417. (Individual parts of the composite code can be printed or etched on a substrate right after being encoded or at the same time with the other parts of the composite code.)

[0030] 3. Decoding a Code 39 Composite for the TCIF Application

[0031] Special decoding software is required to decode a TCIF Code 39 Composite. Decoding software designed for this TCIF application needs to perform the following steps. Note that the first two major steps (decoding the Code 39 symbol, and decoding the MicroPDF417 symbol) may be performed in either order (depending upon where the operator initially aims the scanner).

[0032] Decode the Code 39 symbol, and its link flag. This operation consists of the following sub-steps, in the following order:

[0033] Find and decode the body of the Code 39 symbol, in accordance with the AIM Code 39 specification.

[0034] If the complete decoded message does not consist of a six-digit number, then it is not part of a TCIF Code 39 Composite; transmit it as a standard Code 39 symbol, and do not perform the remaining steps.

[0035] If the complete decoded message consists of a six-digit number, then:

[0036] look past the symbol's right Quiet Zone. If at least 5 more bars and 5 more spaces are present, attempt to decode these as a single Code 39 character, using the same scan direction that was determined from the body of the symbol. If these bars and spaces represent the letter T, then a TCIF Code 39 Composite has been detected. Save the six-digit data, but do not transmit the data until the MicroPDF417 portion of the Composite has also been decoded.

[0037] If a T link flag was not decoded next to this six-digit Code 39 symbol, then transmit it as a standard Code 39 symbol, and do not perform the remaining steps. Note: scanners can be programmed to virtually eliminate the possibility of missing a printed link flag, by applying this voting algorithm:

[0038] If the linear symbol is not a 6-digit Code 39, it is not TCIF-Linked; no voting is necessary;

[0039] If the decoded symbol is a 6-digit Code 39, increment an unlinked-39-count, and store the data (but do not transmit it). Acquire another scan line, and repeat this entire set of steps, until either:

[0040] a link flag is found (in which case TCIF Code 39 Composite has been detected), or

[0041] unlinked-39-count reaches a predefined limit, such as 3 (in which case the symbol is deemed to be a standard, unlinked, Code 39 symbol).

[0042] Decode the MicroPDF417 symbol, and its link flag. This operation consists of the following sub-steps, in the following order:

[0043] Find and decode (to the codeword level) the body of the MicroPDF417 symbol, in accordance with the AIM MicroPDF417 specification.

[0044] If the first codeword is not 918, then complete the decode process (from codewords to ASCII), and transmit this as a standard MicroPDF417 symbol (or as an EAN.UCC Composite, if the first codeword is 920).

[0045] If the first codeword is 918, then a non-EAN.UCC Composite has been detected. Decode the codewords into bytes, per the standard MicroPDF417 procedures, but do not transmit these bytes until the associated linear portion of this Composite has also been decoded.

[0046] Combine the data from the linear and MicroPDF417 portions of the Composite. This step is performed after all of the steps above have been completed. Then, perform the following sub-steps:

[0047] If the linear symbol was not a six-digit Code 39 with a trailing T link flag, this is not a TCIF Code 39 Composite. Transmit the data according to the relevant symbology and/or application specification(s), and do not perform the remaining sub-steps below.

[0048] Transmit the TCIF Code 39 Composite data as a single message, consisting of

[0049] The leading characters of an ISO/IEC 15434 Format 06 message, transmitted as )>^R_S06^G_S

[0050] The ECI code, transmitted as 6P followed by the six digits encoded in the Code 39 symbol

[0051] A^G_S character (to separate this data item from the next), followed by the Data Identifier S

[0052] The ASCII data that was decoded from the MicroPDF417 symbol.

[0053] A trailing ^R_S^EO_T, to complete the ISO/IEC 15434 Format 06 message.

[0054] A sample Code 39/MicroPDF417 Composite symbol, conforming to the TCIF application, is shown in FIG. 1 as reference numeral 10. Reference numeral 2 represents a linear portion of the composite bar code 10. The linear portion is encoded using Code39 Symbology. Reference numeral 6 represents an adjacent two-dimensional portion of the composite bar code 10, encode using MicroPDF417 symbology. Reference numeral 4 represents an adjacent link flag.

[0055] Only the data encoded in a linear portion of the composite bar code is decoded and transmitted by an old generation scanner. The content of such decoded data is: 239316

[0056] The new generation scanner, capable of decoding Code 39 Composite bar codes, will decode both, the data encoded in the 1D potion and the 2D portion of the composite symbol. The content of decoded and transmitted data is:

[0057] 4. Additional Techniques Within the Scope of the Invention

[0058] Although the implementation described above was specifically tailored to the needs of the TCIF application, many other variations and improvements are possible, especially to broaden the applicability of this idea to other industries and applications. As examples:

[0059] This technique, of having a link flag external to the main body of the linear barcode symbol, can be applied to any linear symbology that lacks the inherent ability to encode a link flag. For example:

[0060] A single symbol character (i.e., a set of bars and spaces defined by the Symbology Specification to represent one or more data characters) could be used as a link flag, in the same manner described above, using Codabar instead of Code 39.

[0061] Using Interleaved Two of Five as the linear symbology, a set of 5 bars and 5 spaces, representing any pair of digits from 00 to 99, could be placed after the right quiet zone. In this case, as in the case of many other symbologies such as Code 93, the symbology's symbol characters end in a space not a bar, and an extra narrow bar would need to be added to the right of the link flag.

[0062] In the Case of UPC-A, UPC-E, EAN-8, or EAN-13 symbologies, a single symbol character consists of only two bars and two spaces, thus it is not unlikely that random graphics patterns or text next to these symbols could accidentally look like a link flag. For symbologies such as these, the link flag could instead be defined as two adjacent symbol characters (four bars and four spaces, plus an extra trailing bar as was needed for Code 93 above). This would create a much stronger pattern for the link flag, making it highly improbable that graphics could accidentally mimic a valid link flag.

[0063] This technique, of having a choice of link flags indicate different applications and/or different associated 2D symbols, can be extended as needed. For example, up to 44 different Code 39 Composite applications could be defined by a single Code 39 symbol character used as a link flag. Potentially, each of these applications could define its own rules for allowed data content and transmitted data formatting. Similarly up to 100 different applications could be defined for Interleaved Two of Five Composites. Preferably, these different application assignments would be standardized by an industry standards body (such as AIM, Inc), and a list of the applications and their descriptions made available to all interested parties.

[0064] The link flag does not have to be placed to the right of the linear symbol (placing it instead to the left would work equally well).

[0065] The 2D component of the Composite does not need to be placed above the linear symbol; it could be printed beneath it, or to the left or right of it. Also, the 1D and the 2D portions of the composite code need not touch each other.

[0066] Additional techniques can be applied to improve the robustness of the scheme, to maximize the probability that a scanner will neither a) fail to recognize a link flag that was printed, nor b) accidentally interpret random graphics as a link flag.

[0067] FIG. 2 illustrates an example of improved composite bar code 20 over the composite bar code 10 of FIG. 1. The composite bar code 20 of FIG. 2 has the same two-dimensional and one dimensional portions 22 and 24 as the respective two-dimensional and linear portions 6 and 2 of the composite symbol 10 of FIG. 1. However, the linkage flag character 26 is of a somewhat greater height than the base linear portion 24, preferably extending both above and below the vertical extents of the base linear portion 24. This ensures that a tilted scan line, either 28 or 30, that would otherwise cross the linear data portion 24 of the symbol 10 and miss the link flag 4, will not miss the extended height link flag 26. A small vertical extension of the link flag 26 ensures that any tilted but usable scan line will capture the link flag.

[0068] In the above-described embodiments the 2D bar code included an internal link-flag, separate from the link flag 4 of FIG. 1 or the link flag 26 of FIG. 2. However, if other symbologies that do not have internal linking schemes are used, Composite code of the present invention will work equally well if either the external link-flag 26 of FIG. 2 is extended up to the top edge of the 2D bar code portion, or a separate external link flag is used for the 2D portion. In other embodiments, element 6 of FIG. 1 and element 22 of FIG. 2 could be a 1D bar code.

[0069] The decoder can be programmed to verify that a detected linkage flag is approximately the correct distance from the body of the linear symbol (the nominal distance being the defined size of that symbol's Quiet Zone), to minimize false recognition of graphics patterns.

[0070] Again to minimize false recognition of graphics patterns, a voting algorithm, similar to that described above for the no-flag-detected case, could also be applied to the flag-detected case.

[0071] The preferred embodiment of the invention has been described above. It should be obvious to one skilled in the art that other embodiments including modifications of the present invention are possible without departing from the spirit of the invention.