Edge-to-Edge vs. Module-Width Decoding: The Two Paths to Barcode Interpretation |
Executive Summary |
This article provides a comprehensive exploration of the two fundamental approaches to decoding barcode signals: edge-to-edge decoding and module-width decoding. We examine how these methods interpret the timing and width measurements extracted from a barcode scan, each offering distinct advantages for different symbologies and conditions. Rather than focusing on abstract theory, we ground every concept in concrete design examples and real patent disclosures from industry leaders including Symbol Technologies, Intermec, and others. We explore the historical development of these approaches, the practical implementation of edge-to-edge measurements using similar-edge timing, the use of start/stop patterns for module-width estimation, and the advanced techniques like moving averages and ratio analysis that enhance decoding robustness. The article covers both traditional fixed-pitch symbologies and the variable-pitch challenges of binary codes. The closing summary synthesizes the key lessons and offers practical guidance for anyone implementing barcode decoding algorithms. |
|
Chapter 1: The Two Paths to Decoding |
Once the barcode signal has been digitized and the widths of the bars and spaces have been measured, the decoder must interpret those measurements to extract the encoded data. There are two fundamental approaches to this interpretation: edge-to-edge decoding and module-width decoding. |
Edge-to-edge decoding measures the distances between similar edges---for example, the distance from the leading edge of one bar to the leading edge of the next bar. These distances correspond to the combined widths of a bar and the following space. In symbologies where each character has a fixed number of elements, the pattern of these edge-to-edge distances uniquely identifies the character. |
Module-width decoding, on the other hand, measures the widths of individual bars and spaces relative to a reference 'module' width. The module is the smallest unit of width in the symbology. By dividing each measured width by the module width and rounding to the nearest integer, the decoder determines the number of modules in each element. The pattern of module counts identifies the character. |
A patent from Intermec describes the fundamental challenge: 'Bar code decoding is the process of taking a one dimensional signal, either directly collected from a laser scanner, a one dimensional image sensor, or sampled from a 2-D image from an imaging device and interpreting the signal to extract the information in the bar code symbol' . The choice between edge-to-edge and module-width decoding depends on the symbology, the signal quality, and the required robustness. |
|
Chapter 2: The Concept of Module Width |
The module is the fundamental unit of measurement in barcode symbologies. It is the smallest width that can be used to encode data. All bar and space widths are integer multiples of the module width. |
For two-width symbologies like Code 39, there are two element widths: narrow (one module) and wide (typically two or three modules). The module width is the narrow element width. For multiple-width symbologies like Code 128, there are four different element widths: one, two, three, or four modules. |
The module width is not a fixed physical measurement. It depends on the print resolution, the scanning speed, and the distance from the reader. The decoder must estimate the module width from the measured signal and use it to interpret the element widths. |
A patent from Symbol Technologies explains the measurement in terms of module units: 'A module is unit of measurement that is based on the smallest bar or unit of encoded information in the bar code' . The decoder must 'correlate the size of the physical bar code in modules... to the size of the imaged original bar code in memory' . |
|
Chapter 3: Edge-to-Edge Decoding --- The Similar-Edge Approach |
Edge-to-edge decoding measures the distance between similar edges in the barcode signal. The most common implementation measures the distance from the leading edge of one bar to the leading edge of the next bar. This distance corresponds to the combined width of a bar and the following space. |
The advantage of this approach is that it is relatively insensitive to variations in the absolute element widths. If the scanning speed varies, both the bar and the space widths change proportionally, but the sum of a bar and a space is less affected. Edge-to-edge measurements are also less sensitive to threshold shifts, as the leading edges of bars are well-defined. |
The patent for the BCB (Binary Coded Binary) symbology describes the edge-to-edge approach: 'Edge-to-edge refers [to] a particular strength that makes them less sensitive to uniform ink spread or shrink... BCB uses only two widths of elements, but at a uniform and perfect harmonic ratio of 2:1 exactly; and BCB is continuously decodable purely edge-to-edge, every edge-to-edge measurement is utilized in turn in a continuous fashion' . |
This continuous edge-to-edge approach is particularly powerful because it uses every measurement, rather than relying on isolated comparisons. |
|
Chapter 4: Module-Width Decoding |
Module-width decoding measures the width of each individual element (bar or space) and compares it to the estimated module width. The measured width is divided by the module width and rounded to the nearest integer to determine the number of modules in that element. |
The challenge is estimating the module width accurately. This is typically done by using the start/stop character, where the number of modules is known, or by using an average of multiple elements. A patent from Intermec describes the process: 'calculating a first average unit bar module width by dividing the sum of the bar widths of the start or stop character by a known number of bar unit modules in the start or stop character' . |
Module-width decoding is essential for symbologies with more than two element widths, where the element counts directly determine the character value. In Code 128, for example, each character has 11 modules total, and the pattern of element widths (1, 2, 3, or 4 modules each) uniquely identifies the character. |
Chapter 5: The Role of Start/Stop Patterns in Module Estimation |
The start and stop patterns are essential for module-width decoding. Because the number of modules in the start pattern is known, the decoder can use it to estimate the module width. |
A patent from Intermec describes this method: 'decoding a start or stop character of the bar code; calculating a first average unit bar module width by dividing the sum of the bar widths of the start or stop character by a known number of bar unit modules in the start or stop character; calculating a first average unit space module width by dividing the sum of the space widths of the start or stop character by a known number of space unit modules in the start or stop character' . |
This is particularly valuable because it provides separate estimates for bar modules and space modules. In some symbologies, the module width for bars and spaces is not exactly the same, due to printing variations. |
|
Chapter 6: Moving Averages for Module Estimation |
A more sophisticated approach to module estimation uses a moving average. The module width is recalculated after each element using a sliding window of recent measurements. This allows the decoder to adapt to changes in scanning speed. |
The BCB patent describes this method: 'a selected minimum number of modules is divided into one or more associated pairs of elements... in order to calculate Z, in a directional moving average process... a fresh calculation for Z is made for each line' . The Z value is 'the average number of timing counts per module' . |
The use of a moving average is particularly powerful for hand-scanned barcodes, where the scanning speed can vary significantly during the scan. By continuously updating the module estimate, the decoder can track these speed variations and maintain accurate decoding. |
The patent also notes that the median of a selected number of prior calculated Z's may be selected for use as the operational Z, providing a more accurate reference . |
Chapter 7: Edge-to-Edge in BCB Decoding |
The BCB symbology provides a clear example of edge-to-edge decoding in practice. BCB uses only two element widths (1X and 2X), but it is decoded continuously edge-to-edge. |
The BCB patent describes the process: 'BCB is continuously decodable purely edge-to-edge, every edge-to-edge measurement is utilized in turn in a continuous fashion; ink spread considerations simply do not get involved in the decoding process' . |
The decoding process uses a moving average to estimate the module width: 'As the number of modules is decoded continuously element by element, the total number of modules comprising the last two pairs of decoded elements is divided into the timing count total for these last two pairs of elements in order to calculate Z' . |
This continuous edge-to-edge approach is made possible by the fact that BCB has a 'perfect black and white balance' and 'each BCB symbol forms one big (n, k) codeword' . The decoder can decode from either direction, using the start and stop patterns as anchors. |
|
Chapter 8: Character-by-Character Decoding |
Many barcode decoders operate on a character-by-character basis. The decoder identifies the start and stop patterns, then decodes each character in sequence, using the preceding character to estimate the module width for the next. |
A patent from Symbol Technologies describes a character-by-character method: 'At step 1306, the reader locates and decodes the first delimiter character... At step 1308, the reader advances to the next character position... At step 1310, the reader estimates the character unit grid' . The character unit grid includes 'the starting position, minimum feature size (X), wide/narrow ratio (if applicable), and inter-character gap' . |
This character-by-character approach is particularly well-suited to symbologies where each character has a fixed number of modules, such as Code 128. The decoder can use the known module count of the character to estimate the module width, and then use that estimate to decode the next character. |
Chapter 9: Advantages of Edge-to-Edge Decoding |
Edge-to-edge decoding offers several advantages over module-width decoding. It is less sensitive to variations in the absolute element widths, making it more robust to printing variations and scanning speed changes. |
As the BCB patent explains, edge-to-edge measurements 'make them less sensitive to uniform ink spread or shrink' . This is because the edge-to-edge measurement spans both a bar and a space, so variations that affect both elements tend to cancel out. |
Edge-to-edge decoding is also less sensitive to threshold shifts. The leading edges of bars are well-defined in the signal, regardless of the threshold setting. This makes the measurement more reliable. |
Furthermore, edge-to-edge decoding is efficient. It uses every measurement, rather than relying on isolated comparisons. This makes it more robust to noise and damage. |
|
Chapter 10: Advantages of Module-Width Decoding |
Module-width decoding offers its own set of advantages. It is essential for symbologies with more than two element widths, where the element counts directly determine the character value. |
Module-width decoding is also more straightforward for multiple-width symbologies. The decoder simply divides each measured width by the module width and rounds to the nearest integer to determine the number of modules. This is a simple and efficient process. |
Furthermore, module-width decoding allows the decoder to work with character lengths. As the Intermec patent notes, 'Because some symbologies... specify the exact mapping of the number of codeword characters and the number of modules for a bar code, the number of modules can be found in the decoding process' . |
Module-width decoding also allows for more sophisticated error detection. The decoder can check that the sum of the modules in each character matches the expected total, providing a validation of the decode. |
Chapter 11: Ratio Analysis for Decoding |
Ratio analysis is a powerful technique that combines aspects of both edge-to-edge and module-width decoding. Instead of measuring absolute widths, the decoder compares the ratios of element widths to determine the character. |
The Intermec patent describes ratio analysis for Code 39: 'The first measurement is the lateral distance from the quiet zone to the center of the wide space. The second measurement is from the center of the wide space to the center of the first wide bar. The third measurement is the center-to-center spacing of the wide bars' . The difference between these measurements provides the unit module size. |
Ratio analysis is particularly useful for low-quality signals where absolute measurements are unreliable. The ratios of element widths are more robust to noise and distortion than the absolute values. |
The patent also describes using the stop character measurements to judge acceleration of the scanning beam, allowing the decoder to remove distortion caused by varying scan speed . |
|
Chapter 12: Decoding Two-Width Symbologies |
Two-width symbologies like Code 39 are decoded by distinguishing between narrow and wide elements. The decoder measures each element width and classifies it as narrow or wide based on a threshold. |
The Code 39 decoder in a practical implementation starts by finding the start pattern (the asterisk) and extracting the narrow width from it. This narrow width becomes the reference. Each element is then compared to this reference; if it is close to the narrow width, it is classified as narrow; if it is about twice the narrow width (or more), it is classified as wide. |
This approach works well for clean signals, but it can be challenging when the signal is noisy or the scanning speed varies. The moving average technique described in the BCB patent can be applied to two-width symbologies to improve robustness. |
Chapter 13: The Lost Element Matrix |
The Intermec patent describes a technique called the 'lost element matrix' for decoding barcodes where narrow elements are not resolved. This is particularly useful for out-of-focus scans where the narrow elements are lost. |
The lost element matrix is constructed from the wide element measurements. The adjacent wide element measurement (which contains a single narrow element) and the opposite wide element measurement (which contains two narrow elements) are used to establish the unit module size. The rest of the matrix is assembled by adding or subtracting the unit value. |
To determine the number of lost elements, the measured count is compared to the matrix table. The closest value with the appropriate element parity (odd/even) is the correct number of lost elements. This allows decoding of barcodes where the narrow elements are not resolved, dramatically improving depth of field performance . |
The patent notes that 'the realization that element count parity must be preserved adds considerable tolerance to this procedure' . |
|
Chapter 14: Decoding Multiple-Width Symbologies |
Multiple-width symbologies like Code 128 require a different approach to decoding. Each character has a fixed number of modules (11 in Code 128), and the pattern of element widths (1, 2, 3, or 4 modules each) determines the character. |
The decoder first estimates the module width, typically from the start character. It then measures each element width and divides by the module width to determine the number of modules. The resulting pattern is looked up in a table to determine the character value. |
A patent from Symbol Technologies describes the process: 'The reader can be configured to use a constant scan sampling pitch over the relatively small positional range of a character. A single minimum feature size and wide bar width (if applicable)... can be used to describe the unit grid for a character' . The decoder can 'solve for each character unit encodation pattern by examining all possible combinations of unit encodation patterns... and choosing the unit encodation pattern that results in an expected (e.g., predicted) normalized scan samples' . |
Chapter 15: The Unit Sampling Coefficients Matrix |
A recent patent from Symbol Technologies describes a sophisticated approach to module-width decoding using a unit sampling coefficients matrix. This matrix maps the scan samples to the barcode units, enabling accurate decoding even when the sampling pitch is not aligned with the modules. |
The patent explains: 'The unit sampling coefficients matrix includes zeros at all locations besides those shown including non-zero values... row s0 includes a 0.84 in the first column because 84% of scan sample bin s0 is covered by unit b0, and includes a 0.16 in the second column because 16% of scan sample bin s0 is covered by unit b1' . |
This matrix approach is particularly useful for image-based barcode readers, where the sampling grid may not align with the barcode modules. By using the matrix, the decoder can accurately recover the module values from the scan samples. |
The patent notes that 'Decoding such a section of the barcode can be performed, for example, by solving a linear system of equations for the actual unit encodation pattern (e.g., module values), and then converting that to the element width pattern' . |
|
Chapter 16: Handling Speed Variations |
Speed variation is one of the greatest challenges in barcode decoding. Hand-scanned barcodes are rarely scanned at a constant speed, and this variation can distort the measured element widths. |
The moving average technique, described in the BCB patent, is one method for handling speed variations. By continuously updating the module width estimate, the decoder can track speed variations and maintain accurate decoding . |
The Intermec patent describes another method: using the stop character measurements to judge acceleration of the scanning beam . The difference between the measurements in the start and stop characters provides a measure of the speed variation, allowing the decoder to remove the distortion. |
The character-by-character approach also helps with speed variations. By using the previous character to estimate the module width for the next character, the decoder can track gradual changes in speed . |
Chapter 17: Decoding from Either Direction |
A key feature of many barcode decoders is the ability to decode from either direction. The start and stop patterns are used to determine the orientation of the barcode, and the decoder can then decode the data in the appropriate direction. |
A patent from Symbol Technologies describes the process: 'the reader can locate and decode the delimiter character in the reverse direction along the scan (e.g., by reversing the scan signal)' . This allows the decoder to handle barcodes that are scanned from right to left. |
The start and stop patterns provide the necessary anchors for bi-directional decoding. The decoder can start from either end of the symbol and work toward the other. |
This is particularly important for handheld scanners, where the user may scan the barcode in either direction. |
|
Chapter 18: The Inter-Character Gap |
In discrete symbologies like Code 39, there is a small gap between characters called the inter-character gap. The decoder must account for this gap when measuring the element widths. |
The Symbol Technologies patent describes the process: 'the reader can add the measured character length of the current character... plus any measured inter-character gap, to determine the starting position of the current character' . The decoder can 'measure the inter-character gap using the first edge distance' . |
The inter-character gap is typically a narrow space. The decoder validates the gap to ensure that it is within the expected range. If the gap is too wide or too narrow, the decode may be rejected. |
This validation step is important for ensuring that the decoder is correctly parsing the character boundaries. |
Chapter 19: Error Detection and Correction |
Decoding algorithms must be robust to errors in the measured widths. Both edge-to-edge and module-width decoding incorporate error detection mechanisms. |
The Intermec patent describes a method for detecting mis-decoded characters by comparing average module widths based on the start or stop character to average module widths of a decoded character . If the averages do not match, a mis-decode is suspected. |
The patent also describes adaptive techniques for re-decoding characters: 'The invention identifies misdecoded characters and uses adaptive techniques to decode characters previously non-decodable or misdecoded by standard methods, thereby improving the decode rate as compared to prior techniques' . |
The use of checksums and character parity also provides error detection. The decoder can check that the sum of the modules in each character matches the expected total, providing a validation of the decode. |
|
Chapter 20: The Power of Continuous Decoding |
The BCB patent emphasizes the power of continuous decoding---the ability to decode a barcode element by element, from one end to the other. This approach is both efficient and robust. |
The patent explains: 'The average number of timing counts per module, Z, is first calculated in BCB using a known n from a given (fixed) BCB start pattern or stop pattern convention... and thereafter the number of modules per individual element is decoded one element at a time, continuously, from one end of the symbol to the other, element by element' . |
This continuous approach allows the decoder to track changes in the module width in real time, adapting to speed variations and other distortions. It also makes the decoder self-correcting: 'Self-correcting and other enhanced decode features are described below for use with BCB and other bar codes' . |
The BCB patent claims that this continuous edge-to-edge approach provides 'a many fold improvement beyond the mere self-checking many other bar codes presently offer' . |
Chapter 21: The Role of Fixed Pitch in Decoding |
Many symbologies, including Code 128 and UPC, have a fixed pitch: each character has a fixed number of modules. This makes module-width decoding more straightforward. |
The BCB patent describes the concept: 'This describes the (fixed) 'pitch' of a bar code. Because (n, k) codewords have a (fixed) pitch, applicants characterize such codes as directly character by character self-clocking' . |
The fixed pitch provides a valuable constraint for the decoder. If the measured widths of a character do not sum to the expected total, the decoder can infer that an error has occurred and take corrective action. |
The patent contrasts this with 'Binary Coded Binary,' which 'is short on such fixed pitch' and requires the moving average technique for decoding . |
|
Chapter 22: The PPM and Module Estimation |
PPM (pixels per module) is a measure of image resolution in image-based barcode readers. A higher PPM provides better resolution for measuring module widths. |
The Symbol Technologies patent explains: 'The image sampling pitch essentially determines the image resolution, typically measured as the number of pixels per module ('PPM')' . Higher PPM values allow more accurate estimation of the module width. |
The patent also notes that perspective effects can change the effective PPM across the barcode: 'it is possible that the effective image sampling pitch actually changes substantially but continuously from one end of the barcode to the other due to perspective effects' . |
This makes module estimation more challenging for image-based readers, as the module width may not be constant across the image. |
Chapter 23: The Lined 'Counting' Barcode |
A historic patent from International Standard Electric Corporation describes a novel barcode design that addresses a fundamental scanning challenge: speed variation. The patent introduces counting marks within the spaces of the barcode, which enable the reader to generate a counting clock independent of scanning speed . |
The patent explains: 'the spaces between neighboring code bars which have a width greater than one modular width, with the modular width always being larger than the diameter of the scanning spot of a reading device, contains counting-line marks or counting bars' . These counting marks have 'a reflectance lying between that of the spaces and that of the code bars' . |
The reading device detects three signal levels---code bars, spaces with counting marks, and blank spaces---and processes them to provide a pulse train synchronized to the scanning speed. This effectively makes the decoder independent of speed variations . |
This historical example demonstrates that the challenge of decoding under speed variation has been recognized for decades, and that various solutions have been developed. The modern moving average and edge-to-edge techniques are refinements of this same principle. |
|
Chapter 24: Summary --- The Two Paths in Perspective |
Edge-to-edge and module-width decoding are the two fundamental approaches to interpreting barcode signals. Each has its strengths and weaknesses, and each is suited to different symbologies and conditions. |
We have examined how different companies and technologies have approached these decoding methods: |
The BCB patent describes a continuous edge-to-edge decoding approach using moving averages to estimate the module width. This approach is self-correcting and robust to ink spread and threshold shifts . |
The Intermec patent describes using the start/stop characters to estimate module widths, and using ratio analysis to detect mis-decoded characters. The lost element matrix technique allows decoding of barcodes where narrow elements are unresolved . |
Symbol Technologies describes character-by-character decoding with unit sampling coefficients matrices for image-based readers. The decoder can use multiple thresholds and validate results against expected character lengths . |
|
The key lessons from our exploration are: |
Edge-to-edge decoding measures similar-edge distances. This approach is robust to threshold shifts and ink spread. It is particularly well-suited to two-width symbologies. |
Module-width decoding measures individual elements relative to a reference module. This approach is essential for multiple-width symbologies where the element counts determine the character value. |
Start/stop patterns provide the reference for module estimation. The known module count of the start pattern allows the decoder to estimate the module width and use it for the rest of the symbol. |
Moving averages track speed variations. By continuously updating the module estimate, the decoder can adapt to changing scanning speeds and maintain accurate decoding. |
Ratio analysis provides additional robustness. By comparing ratios of element widths rather than absolute values, the decoder can handle degraded signals. |
Error detection is essential. The decoder must validate each character against expected module counts, symbology rules, and checksums. |
In the end, the choice between edge-to-edge and module-width decoding depends on the symbology, the signal quality, and the application requirements. Both approaches have their place, and modern decoders often combine them to achieve the best possible performance. The art of barcode decoding lies in knowing which method to use when, and how to adapt it to the real-world conditions of each scan. |
cs@easiersoft.com