Record with encoded data5471533Abstract A record contains a graphic image and an information area which are interrelated to discourage misuse of the record. The information area can overlay the graphic image and include information encoded in a error-correctable, machine-readable format which allows recovery of the information despite distortion due to the underlying graphic image. The record may also represent the image by words similar in form to words in the information area. Both the information and graphic words can then be altered when an action regarding the record takes place. Claims What is claimed is: Description BACKGROUND OF THE INVENTION
______________________________________
Row 0:
L.sub.0 (row #, # of rows)
R.sub.0 (row #, # of columns)
Row 1:
L.sub.1 (row #, security level)
R.sub.1 (row #, # of rows)
Row 2:
L.sub.2 (row #, # of columns)
R.sub.2 (row #, security level)
Row 3:
L.sub.3 (row #, # of rows)
R.sub. 3 (row #, # of columns)
etc.
______________________________________
In other words, the left row indicator codeword L.sub.0 for the first row 0 contains the row number (0) and the total number of rows in the symbol. The right row indicator codeword R.sub.0 for row 0 contains the row number (0) and the number of data columns in the symbol, and so on. Encoding data into a PDF417 symbol is typically a two-step process. First, data is converted into codeword values of 0 to 928, which represent the data. This is known as "high-level encoding." The values are then physically represented by particular bar-space patterns, which is known as "low-level encoding." Encoding/Decoding System Encoders and decoders are discussed more completely in U.S. Ser. No. 07/851,493, which is herein incorporated by reference. Referring now to FIGS. 5-7 in the drawings, FIG. 5 is a block diagram of the system 10 for representing and recognizing data or a record in machine readable graphic image form. System 10 includes an encoding means, generally indicated by the reference numeral 12, and a recognition means, generally indicated by the reference numeral 14. Encoding means 12 produces a record 16 (see FIG. 1A), such as a driver's license, visa, or passport, with a photograph. Overlaying the photograph would be data encoded in a two-dimensional pattern 18. Record 16 may also contain human readable data 20, such as text. The two-dimensional pattern 18 on record 16 is recognized by recognition means 14 to produce output signals representative of the data encoded into the pattern 18. Data to be encoded into the two-dimensional pattern 18 on record 16 is entered into the encoding means 12 by entering means 22. The data entered by entering means 22 may include both data to be encoded into the two-dimensional pattern 18 and the data to appear on record 16 in human readable form. That data can even include the photograph or image. Processing means 24 encodes the set of data into a two-dimensional pattern 18 and generates transfer drive signals for controlling the transfer of the indicia onto the record 16. Transferring means 26 transfers an image of the two-dimensional pattern 18 onto record 16 in response to the transfer drive signals. Preferably, transferring means 26 includes a printer which transfers either light-colored ink or ultraviolet-light sensitive ink as explained above. If human readable data is also to be transferred onto record 16, the processing means 24 generates a second set of transfer drive signals for controlling the transfer of the human readable data onto record 16. A portion or all of the data to be encoded and the human readable data may be transferred from a storage memory in processing means 24 or other computer files rather than being entered by means 22. Recognition means 14 includes converting means 28 that converts the image on record 16 into electrical signals representative of the graphic indicia. Decoding means 30 decodes the electrical signals into decoder output signals, indicated at 32, that are representative of the data encoded into the pattern 18. FIG. 6 is a perspective view of one embodiment of encoding means 12. The embodiment of FIG. 6 is for illustrative purposes, and not meant to limit the scope of the invention. In this embodiment, the entering means 22 of FIG. 5 is shown in form of a keyboard 32 for entering alphanumeric and graphic data into the encoding means 12. Entering means 22 may take forms other than a keyboard, such as an optical scanning means for scanning data directly from documents for entry into the encoding means 12. Referring again to FIG. 6, the processing means 24 of FIG. 5 is shown in the form of a processor and display unit 34. The data entered by keyboard 32 is transmitted to the processor and display unit 34 for storage and processing. In addition to entering data, the keyboard 32 is also used for entering control commands to effect operation of the processor unit 34. The data entered by keyboard 32 is preferably displayed on display screen 36, and upon entry of a proper control command, is also stored in memory. The data to be encoded into the pattern 18 is stored in a first memory in processor 34, and the data, if any, to be transferred in human readable form is stored in a second memory. Alternatively, both data may be stored in a separate portion of a single memory. Upon the appropriate control command from keyboard 32, the processor unit 34 encodes the data in the first memory into a two-dimensional pattern 18 and generates first transfer drive signals representative of the data stored in the first memory. The processor unit 34 also generates second transfer drive signals representative of the data stored in the second memory. The processor unit 34 is shown in FIG. 6 as being coupled to a printer 38. Printer 38 is one form of the transferring means 26 of FIG. 5. Printer 38 transfers an image of the two-dimensional pattern 18 on record 16 in response to the first transfer drive signals and prints the second set of data in human readable form onto record 16 in response to the second transfer drive signals. Turning now to FIG. 7, the recognition means 14 includes a card reader 40 which contains the converting means 28 and the decoding means 30 of FIG. 5. The use of appropriate converting means that corresponds to the particular data encoding technology employed is contemplated by the present invention. The converting means 28 may be a bar code reader such as those disclosed in U.S. patent application Ser. Nos. 317,433 and 317,533, and incorporated herein by reference, which can read the ink used by printer 38. The readers disclosed in the above patent applications are open system devices designed to read an optically encoded two-dimensional bar code and to convert the light reflected from the pattern into electrical signals representative of the graphic indicia. The decoding means 30 decodes the electrical signals into output signals representative of the data encoded onto record 16. The decoder output signals are outputted from the recognition unit 40 to various output means 42. FIG. 7 depicts two examples of output devices, one being a display unit 44 and the other a printer 46. Display unit 44 may be any suitable display such as liquid crystal display or a CRT. The printer 46 may be any print device such as a dot matrix printer, laser printer, etc. The system maximizes the use of available space for encrypting data. The density of the encoded data is such that for a two-dimensional bar code symbol, a minimum of about 1600 characters can be encoded into a space of approximately 5".times.1/2". In addition to being compact, the system provides for high security in the transmission of information. Although the encoding means 12 and the recognition means 14 are shown in FIGS. 5-7 as separate devices, they can be in the same device. This is particularly useful when a record 316 (FIG. 1B) is read and modified. In such cases it would be useful to have a single unit for both purposes. FIG. 5A shows a block diagram of a system 10' for use with record 316 in FIG. 1B. System 10' includes elements that PG,21 correspond to those of system 10 shown in FIGS. 5-7. Specifically, system 10' includes a converting means 28' which converts the encoded data from record 316 into electrical signals, and a decoding means 30' which decodes those signals. Processing means 24' then reads the decoded signals and, based upon certain criteria, cause transferring means 26' to print appropriate output signals to modify record 316 (FIG. 1B) into record 316' (FIG. 1C). The slight variations could be determined in a variety of ways. For example, if record 316 is a bearer bond on a stock certificate, processing means 24' could be a large computer or a computer network which keeps track of redemptions. Processing means 24' could also receive data on either the interpretation of the information or the printing of the information using entering means 22'. Processing means 24' also preferably includes alignment means 25' for locating selected areas of record 316 for reading a printing. Alignment means 24' interprets fields that identify rows and particular words in those rows. Although alignment means 25' is shown as part of processing means 24', it could also be a microprocessor in either converting means 28' or transferring means 26'. Data may also be encoded using a keyed encryption algorithm that may be accessed only by an encryption key. As shown in FIG. 8, the data entry means 47 contains the keyed algorithm and upon entry of the key 49, the data will be encoded into a two-dimensional graphic pattern in a unique configuration. The unique configuration can only be read by a reader 48 having the proper algorithm, and only upon entry of the key 49 into the reader. Thus, a high degree of security may be provided with the keyed encryption embodiment. Another feature of the present invention is to have the image on record 316' be a "digital signature" which is embedded as the PDF 417 bar code in encrypted form. The printer which created the two dimensional digital signal would then use a keyed encryption algorithm that could be accessed only by an encryption key. By use of a keyboard or other data entry means which had the keyed algorithm, and upon entry of the key, the data entered as plain text on a keyboard would be encoded into the two dimensional graphic pattern in a unique decoded configuration. The unique pattern or code configuration could only be decoded and read by a reader having the algorithm and only upon entry of the identical key into the reader. This provides a high degree of security for applications needing such security. A low-level decoder may be embodied in a computer program operating on a microcomputer separate from the host computer. The low-level decoder would be preferably connected to the host computer by a standard interface, such as an RS-232 interface, for transmitting the codeword values after they are decoded. Alternatively, the low-level decoder could be embodied entirely in hardware, or a combination of a hardware and software, which is physically located in either the scanner itself or the host computer. The matrix of codeword values from low-level decoder is decoded into usable data by a high-level decoder, which may be embodied as a separate computer program operating on the host computer. For example, PDF417 has three predefined modes and nine reserved modes. The predefined modes are Binary, EXC, and Numeric. In the Binary mode, each codeword can encode 1.2 bytes. In the EXC mode, the alphanumeric data can be encoded in double density (i.e., two characters per code word), and in Numeric mode, the numeric data can be packed in almost triple density. Therefore, the high-level decoder in host computer 112 will further decode the codeword values (0-928) from low-level decoder 114, depending on the mode, to obtain the actual data embodied in the symbol. The decoded data from the high-level decoder may then be used by a user application program also operating on the host computer 112. FIG. 9 is a flow chart showing the sequence of operation of a low-level decoder for decoding a two-dimensional bar code symbol such as PDF417 into a matrix of codeword values. The various steps in the sequence are embodied in a software computer program which is stored and executed by processor 34. In the first step 150 in FIG. 9, the low-level decoder initializes the scanner interface and initiates scanning of the symbol. The actual functions performed in this step will depend on the type of scanner and will involve various scanner-dependent routines to initialize the scanner interface and to start scanning. In step 152, the low-level decoder attempts to determine the dimensions and the security level of the symbol being scanned. Specifically, this step determines the number of rows, the number of data columns, and the security level of the symbol from the left and right row indicator codewords. These dimensions are then used to initialize a two-dimensional codeword matrix and other related parameters for decoding the symbol. Each location in the matrix contains both a codeword value and an associated confidence weight, which are initially set to a null or empty value. If the dimensions and security level of the symbol cannot be determined, then the scan is aborted. This step will be discussed in further detail below in connection with FIG. 10. Continuing in FIG. 9, step 154 is the first step in a control loop in which the rows of the two-dimensional bar code symbol are repeatedly scanned and the codeword values are filled into the codeword matrix. The steps of the control loop are each repeated until the number of codewords remaining in the matrix which have not been successfully decoded is small enough that the rest of the matrix can be determined using the built-in error correction capability of the symbol. Thus, in step 154, if the number of codewords which have not been successfully decoded is less than the error correction capability of the symbol based on the security level (see FIG. 4), an attempt is made to correct the matrix using the error-correction codewords. If the attempted error correction is successful, then in step 156, the control loop is exited and scanning is terminated in step 158. Otherwise, if the attempted error correction is not successful, then the following steps 160-164 are performed to try to decode additional codewords to fill in the matrix. First, step 160 searches a scan line of data obtained from the buffer area of the memory for a start or a stop pattern. If either a start or a stop pattern is found, then in step 162, the low-level decoder attempts to decode as many codewords as possible from the scan line. Specifically, the scan line of data is parsed into individual codewords whose values and cluster numbers are placed in a codeword vector ready for incorporation into the codeword matrix. Both steps 160 and 162 are discussed in further detail below in connection with FIGS. 11 and 13, respectively. The codeword vector produced in step 162 is analyzed and then used to update the codeword matrix in step 164. In particular, step 164 assigns a confidence weight to each codeword value depending on whether its nearest neighbors were also decoded. Row numbers are also assigned to each codeword value based on the left or right row indicator codewords and the corresponding cluster number for the codeword. If the scan line crosses a row boundary, the cluster numbers of the codewords can be used to determine the correct row number for each individual codeword. For example, if a decoded scan line has a left row indicator with row number 2, and the cluster numbers of the following codewords are 6, 0, 0, 3, the codewords are accordingly placed in the following locations: (row 2, column 1); (row 3, column 2); (row 3, column 3); and (row 4, column 4). In this way, a single scan line of data can contain codewords from more than one row, which can then be stitched into the appropriate location in the codeword matrix. This step is discussed in further detail in connection with FIGS. 16A and 16B below. FIG. 10 is a flow chart showing in greater detail the sequence of steps for determining the dimensions and security level of a symbol as referred to in step 152 of FIG. 9 above. In the first step 170 of FIG. 10, the low-level decoder searches a scan line of data obtained from the buffer area of the memory for a start or a stop pattern. This step is the same as step 160 in FIG. 9 and is discussed in further detail in connection with FIG. 11 below. Step 172 then decodes the first codeword immediately adjacent to either the start or stop pattern found in the previous step. As shown in FIG. 3, this codeword will be either a left or right row indicator codeword containing the row number and either the number of rows, the number of data columns, or the security level of the symbol. If both a start and a stop pattern are found, then both the left and the right row indicators are decoded. The sequence of steps for decoding an individual codeword are discussed further below in connection with FIG. 15. Continuing in FIG. 10, in step 174 the particular dimension or security level encoded in the row indicator is extracted from the codeword value and the cluster number determined in the previous step 172. For example, for a left row indicator codeword with a cluster number of 0, the number of rows is extracted from the codeword value. A confidence weight assigned to each of the dimensions and the security level is initially set to 0. Steps 176-184 update both the current value and the confidence weight of the dimension or security level extracted in the previous step in the following way. First, the particular parameter, say the number of rows, is compared to the current value of the number of rows obtained from previous decodes. If the current value of the number of rows and the newly decoded value are the same, as determined in step 176, then the confidence weight assigned to the number of rows is increased in step 178. If the current value and the newly-decoded value are different, however, then the confidence weight is decreased in step 180. If the confidence weight assigned to the particular parameter is decreased below zero as determined in step 182, then the newly decoded value is substituted for the current value and a new minimum weight is assigned to the parameter in step 184. Step 186 determines whether the confidence weight for all three parameters, i.e., number of rows, number of data columns, and security level, exceeds a predetermined threshold. If so, then the two-dimensional codeword matrix is initialized in step 188 based on the current values of the number of rows and the number of columns. The number of correctable errors may also be determined from the current value of the security level according to the table in FIG. 4. If all three confidence weights do not exceed the threshold in step 186, however, then program control returns to step 170 to begin searching for the start and stop patterns in a new scan line. Steps 170-184 are repeated until all three parameters have been successfully decoded with a high degree of confidence. FIG. 11 is a flow chart showing in greater detail the sequence of steps for searching a scan line of data for a start or stop pattern as referred to above in step 160 of FIG. 9 and step 170 of FIG. 10. Briefly, the search begins at the first location of an individual scan line of data obtained from the buffer area of the memory and is repeated at sequential locations until either a match is found or the length of the scan line is exceeded. When a match is found, an index is set to a location immediately following or preceding the pattern for decoding the adjacent code word. As shown in FIG. 11, the first step 200 sets an index to the location of the data elements in the scan line to "1," indicating the first data element or integer value of the scan line. This index is used to identify the first element of each sequence of eight elements in the scan line for comparison to the start and stop patterns. Step 202 is the first step of an iterative loop for searching the scan line from left to right for either a start or a stop pattern. In this step, if the current index is less than the length of the scan line, then the remaining steps are executed and the search continues. Once the index exceeds the length of the scan line, however, then the loop is exited and an indication is returned signifying that the search failed and a start or stop pattern was not found. Rather than using the X-sequence of codeword, the low-level decoder decodes a symbol by using "edge to similar edge" measurements to compensate for ink spreading which occurs when printing the symbols. Thus, in step 204, a raw "t-sequence" is obtained from the scan line by adding pairs of consecutive integer values beginning at the location specified by the index. Specifically, the raw t-sequence, which corresponds to the seven width measurements t.sub.1,t.sub.2, . . . t.sub.7 shown in FIG. 12, is calculated by adding pairs of the consecutive integer values x.sub.0,x.sub.1, . . . x.sub.7, representing the widths of the bars and spaces, as follows: t.sub.1 =x.sub.0 +x.sub.1 t.sub.2 =x.sub.1 +x.sub.2 t.sub.3 =x.sub.2 +x.sub.3 etc. A width W for the entire codeword is also calculated in step 204 by summing the eight integer values x.sub.0 +x.sub.1 + . . . +x.sub.7. For the codeword in FIG. 12, for example, the sequence of integer values from the scan line, representing the widths of the bars and spaces might be something like: 43, 19, 21, 19, 22, 18, 103, 96. The raw t-sequence t.sub.1,t.sub.2, . . . t.sub.7 would then be 62, 40, 40, 41, 40, 121, 199, and the width W would be 341. In step 206 in FIG. 11, the raw t-sequence obtained in step 204 is normalized and rounded to integer values. Specifically, a value for the codeword's "module" or "unit" is first established by dividing the width W of the codeword by the total number of units for each codeword. In a PDF417 symbol, each codeword is seventeen units, so that the width W is divided by seventeen to obtain the unit of the codeword. Thus, for the example in FIG. 12, the unit would be (341/17)=20.0. Each value of the raw t-sequence is then divided by the unit and rounded to an integer to normalize the t-sequence. The normalized t-sequence for the codeword in FIG. 12 is 3, 2, 2, 2, 2, 6, 10. The normalized t-sequence is then compared to the t-sequences of the start and stop patterns of the code in step 208. If the scanner scans from both left to right and right to left, then the t-sequence must be compared to the start and stop patterns in both their normal and reverse orientations. If there is a match in step 210, then the index is set in step 214 to a location in the scan line immediately following the pattern if it is a start pattern or immediately preceding it if it is a stop pattern. If the current t-sequence does not match either the start or the stop pattern, however, then in step 212, the index is incremented by one and steps 202 through 210 are repeated until either a match is found or the length of the scan line is exceeded. FIG. 13 is a flow chart showing in greater detail the sequence of steps for decoding a scan line of data into a vector of codewords and their clusters as referred to in step 162 of FIG. 9 above. In decoding the individual codeword values and cluster numbers from the scan line, the low-level decoder begins decoding at the start or stop pattern and decodes as many codewords possible. For those codewords that are not successfully decoded, the codeword values in the codeword vector are set to "BAD." At the completion of the sequence of steps shown in FIG. 13, the codeword vector will contain certain codeword values and cluster numbers in locations corresponding to the appropriate columns of the codewords that were successfully decoded. FIG. 14A shows an example of a codeword vector in which the codewords in eight of the ten columns were successfully decoded. The codeword values in columns 1 and 10 correspond to the left row indicator codeword in row 2 (L.sub.2) and the right row indicator codeword in row 1 (R.sub.1), respectively. The codewords in columns 5 and 7 were not successfully decoded as indicated by the notation "BAD" in those locations of the codeword vector. Returning to the first step 220 of FIG. 13, an upper limit on the number of codewords that may be decoded ("cwlimit") is set equal to the number of columns in the codeword matrix. If this number of codewords is successfully decoded, then the decoding process for the current scan line is obviously complete. Step 222 determines the direction of the scan if the scanner scans from both left to right and right to left. If the particular scan was from left to right as determined in step 222, then the column number of the first codeword is set to "1" in step 224 and the amount that it will incremented by ("incr") each time a subsequent codeword is decoded is set to "+1." If the scan was from right to left, however, then in step 226, the column number of the first codeword in the scan line will be the last column of the codeword matrix, and the incremental value is set to "-1." Step 228 is the first step of a control loop in which individual codeword values and their cluster numbers are decoded from the scan line of data. In step 228, the codeword limit is tested to see if it is still greater than zero. If not, then all of the codewords in the scan line have been decoded and the loop is exited. Otherwise, step 230 obtains the next codeword value and its cluster number from the scan line. This step will be discussed in further detail below in connection with FIG. 15. If the codeword decoded in the previous step is a valid codeword as determined in step 232, then in step 234 the codeword value and its cluster number are saved in the codeword vector at a location corresponding to the column of the codeword. The codeword values thus placed in the codeword vector are ready for incorporation into the codeword matrix. If the codeword decoded in step 230 is not a valid codeword, however, then the codeword value in the codeword vector corresponding to the current column is set to "BAD" in step 236 to indicate that this codeword was not successfully decoded. A "BAD" codeword is most likely to occur when the scan line crosses the boundary between two rows in the middle of the codeword. Finally, in step 238, the current column number is either incremented or decremented depending on the direction of the scan, and the codeword limit is decremented by one. Steps 228-236 are then repeated until there has been an attempt to decode all of the codewords in the scan line. FIG. 15 is a flow chart diagram showing the sequence of steps corresponding to step 230 in FIG. 13 and step 172 in FIG. 10 in which an attempt is made to decode an individual codeword value and cluster number from the scan line. In the first step 240, a raw t-sequence and the width W are obtained from the scan line. This same step was discussed previously in connection with step 204 in FIG. 11. In step 242, the width W of the eight elements presumed to be the next codeword are compared to the width of the previously decoded codeword. If the current width W is not within a range of plus or minus a predetermined difference (delta), then there is probably a split (undercount by a multiple of two elements) or a merge (overcount by a multiple of two elements) error in the current codeword. This codeword is not decoded further, but rather in step 244 its value and cluster number are both set to BAD to indicate that it could not be decoded. Then in step 246, an attempt is made to resynchronize to the boundary of the next codeword by finding a t-sequence with a corresponding width W that falls within a given tolerance of the expected width of a codeword, based on the width of the previous codeword. If the current width W is significantly greater than the expected width, indicating a possible merge error, then the last two integer values are dropped from the t-sequence until it falls within the proper limits. Likewise, if the current width W is significantly less than the expected width, indicating a possible split error, the next two integer values in the scan line are added to the t-sequence until it falls within the proper limits. If the current width W is within a certain tolerance of the expected width, as determined in step 242, then an attempt is made to decode the codeword. In step 248, the raw t-sequence is normalized as described above in connection with step 206 in FIG. 11. Then in step 250, the cluster number is determined from the normalized t-sequence. The cluster number may be determined from the t-sequence (as opposed to the X-sequence described above) as follows: cluster number=(T.sub.1 -T.sub.2 +T.sub.5 -T.sub.6) mod 9 For codewords in PDF417, valid cluster numbers are 0, 3, and 6. If in step 252 it is determined that the cluster number is not 0, 3, or 6, then the codeword is not valid. Accordingly, in step 254 the cluster number and value are set to "BAD" to indicate that the codeword was not successfully decoded. Otherwise, in step 256, the normalized t-sequence and its cluster number are used to find the corresponding codeword value in a look-up table. If no corresponding codeword value is found for the t-sequence, then the codeword value is set to "BAD" to indicate that it was not successfully decoded. Finally, in step 258 the "last width" value is updated to the current width W of the codeword for use in decoding the next codeword value from the scan line. FIGS. 16A and 16B together comprise a flow chart of the sequence of steps executed by the low-level decoder in order to update the codeword matrix using the codeword vector. These figures explain in greater detail step 164 in FIG. 9 discussed above. The first step 260 of FIG. 16A checks the first and last values in the codeword vector to see if either is a valid row indicator. If neither the first nor the last values in the codeword vector is a valid row indicator, then in step 262 the program exits the routine and no attempt is made to update the codeword matrix using the codeword vector. If a valid row indicator is present, however, then in step 264 confidence weights are assigned to each codeword value in the codeword vector. Specifically, a confidence weight is assigned to each codeword depending on whether its nearest neighbors and their cluster were also decoded. For example, as shown in FIG. 14B, the codeword values in columns 1, 2, 3, 9, and 10 are assigned high confidence weights ("H") because their immediate neighbors were also successfully decoded and have the same cluster number. The codeword values for columns 4 and 8 are assigned medium confidence weights ("M") because one of their neighbors was successfully decoded and has the same cluster number but the other neighboring codeword value is "BAD." The codeword value in column 3 is assigned a very low confidence weight ("L") because neither of its neighbors was successfully decoded. Thus, the confidence weight for a codeword value at column i in the codeword vector is essentially a function of the cluster numbers of the codewords at columns i-1, i, and i+1. This function may be implemented by a look-up table whose index is calculated from the cluster numbers of the three codewords. In step 266, a row number is assigned to each codeword value in the codeword vector based on the row indicator codewords and the cluster numbers. As shown in the example in FIG. 14C, the left row indicator codeword L.sub.2 indicates that the row number is 2 and the cluster number is 6. The cluster numbers for the codeword values in columns 2-4 are also 6. Therefore, row number 2 is assigned to the codeword values in the first four columns of the codeword vector. Also in the example in FIG. 14C, columns six and 8-10 all have a cluster number of 3 and the right row indicator codeword R.sub.1 indicates that the row number is 1. Therefore, it can be assumed that the scan line crossed the row boundary between row 2 and row 1 and the codeword values in columns 6 and 8-10 should be assigned to row 1. Once the confidence weights and row numbers have been assigned to each of the codeword values in the codeword vector, the codeword matrix is updated one codeword at a time. In step 268, the column number C of both the codeword vector and the codeword matrix is set is initially set to "1." Step 270 is the first step of an iterative loop which steps through the codewords in the codeword vector and uses them to update the corresponding codewords and their associated confidence weights in the codeword matrix. When the column number C exceeds the number of columns in step 270, then all of the codewords in the codeword vector have been processed and the routine ends. For each codeword in the codeword vector, step 272 sets the row number R of the codeword matrix to the row number assigned in step 266 to the codeword in the codeword vector at the location C. Thus, for each codeword value in the codeword vector, there is a corresponding value in the codeword matrix at location [R,C]. Continuing in FIG. 16B, step 274 determines whether the current codeword value in location [R,C] in the codeword matrix is the same as the corresponding codeword value in the codeword vector at column C. If the values are the same, then in step 276, the confidence weight assigned to the codeword value in matrix location [R,C] is increased by the confidence weight of the corresponding codeword value in the codeword vector. If not, the confidence weight of the codeword value in the matrix is decreased by the confidence weight of the codeword value in the vector in step 278. If the confidence weight was decreased in step 278, then in step 280 that confidence weight is tested to see if it was decreased below zero. If the confidence weight is less than zero, then in step 282 the new codeword value in the codeword vector is substituted for the current codeword value in the corresponding location in the codeword matrix. The confidence weight assigned to the codeword value in the matrix is also changed to a positive value in step 284. Finally, in step 286 the column number C is incremented by 1 for processing the next codeword value in the codeword vector and program control is returned to step 270 for repeating steps 272 through 286 for all of the columns in the vector. Returning briefly to step 154 in FIG. 9, each time after the codeword matrix has been filled in with the new vector of codeword values and the confidence weights have been updated, an attempt is made to fill in the rest of the matrix using the built-in error correction capability of the symbol. The number and location of codewords which have not yet been successfully decoded may be determined by comparing the confidence weights assigned to each of the codeword values in the matrix with a predetermined threshold. Those values having confidence weights below the threshold are considered to not yet be decoded. If the number of codewords not yet decoded is less than the error correction capability of the symbol as determined by the security level, then an attempt is made to correct the matrix. It will be apparent to those skilled in the art that various modifications and variations can be made in the decoding method and apparatus without departing from the scope or spirit of the invention. Other embodiments of the invention will be apparent to those skilled in the art from consideration of the specification and practice of the invention disclosed herein. It is intended that the specification and examples be considered as exemplary only, with a true scope and spirit of the invention being indicated by the following claims.
|
Same subclass Same class Consider this |
||||||||||