Data Matrix Generator – What is this about?

Data Matrix codes are two-dimensional barcodes that can display arbitrary binary information. They come in various sizes (depending on the amount of data to be stored) and use a Reed-Solomon error correction code. Even if a part of the barcode is damaged, they can still be read correctly (e.g., by a suitable smartphone app). Approximately half of the space in the barcode is used for error correction.

If the message to be stored is shorter than the capacity of the barcode type, then the stored information needs to be padded by some bytes that can be chosen arbitrarily. The padding is also subject to error correction and hence changing the padding information changes more than half of the pixels of the barcode. This allows us to optimize a barcode for some properties that we may be interested in without changing the content of the barcode. For example, if a barcode is to be printed, choosing the padding such that the amount of black ink needed to represent the barcode should be minimized. This is exactly the idea of the barcode generator on this site: We want to make Data Matrix codes more environment friendly by reducing the amount of ink needed to print them. At the same time, the generated barcodes are 100% valid and allow the same level of error correction than traditionally generated Data Matrix codes (with random padding information).

To obtain environment-friendly barcodes, we could iterate over all possible padding values and compare the generated barcodes. The approach implemented in this generator is however different. Rather than brute-forcing the problem, our tool builds a constraint system that encodes the relationship between the encoded text and the barcode. Due to complexity of Reed-Solomon error correction, this constraint system uses not only simple Boolean constraints, but also makes extensive use of the exclusive or operator. The resulting (difficult) computational problems are solved using the solver CryptoMiniSat with the aim of minimizing the number of black pixels in the resulting barcode.

This idea was developed and implemented as part of the work in the Bachelor student project group “TAPPS” that took place at the University of Bremen from 2016-2017. The students Philipp Dargel and Gerrit Marquardt designed a complete implementation (in Haskell) of all components of the Reed-Solomon error correction and wrote a constraint set generator that optimizes away the fixed parts of the search problem (namely, the text to be encoded). The resulting approach can efficiently deal with large search spaces. Since the tool runs on a web server, the search space size is restricted to (and can be smaller when using a message that fits quite well into barcodes of the selected size) for computational reasons. The web service was written by the lecturer of the student project group, Rüdiger Ehlers.

When using the tool (by typing a message into the box on the landing page of this site and clicking the button), you will be taken immediately to a results page that initially only states how long you will have to wait for the computation to finish. You can bookmark this page and return later, as the results will be stored after the computation finishes. The page will also auto-refresh until the computation is finished. The numbers below every barcode represent the number of black pixels, not counting the fixed borders of the barcode, which cannot be optimized.