As an outsider looking into the field of coding-theory, I am wondering if there are examples of an error-correcting code where the bits are expressed in 3-D space?

Though I am not sure this exists, I am imagining a "lattice" extension of a 2-D barcode generated with the Reed-Solomon polyonmial. In 3-D, the row (x), column (y) and height (z) are used as information to encode the barcode. Would someone be able to point me to some examples of these codes? I am particularly interested in how this added dimension will change error-correction and message capacity.

enter image description here

  • 2
    $\begingroup$ The sensor required to detect height would be much more complicated. QR codes can be just black and white images. Very easy to process, scale. $\endgroup$ – IanJ Jan 6 at 22:49

Not really an answer, but I started thinking, then typing, and then thinking again. Posting whatever popped into my mind :-(

The Reed-Solomon codes used in 2D barcode really correct byte errors. Or perhaps more precisely, symbol errors. IIRC the QuickResponse code has 8-bit symbols (=bytes)., but Reed-Solomon codes exist for each possible symbol size, 9-bit, 10-bit, whatever. Their math is simple enough. Should symbol errors be relevant to your application, it is trivial to construct a Reed-Solomon code to deal with them.

The way I see it the challenges in your idea are technical. The standard of Quick Response codes specifies a handful of formats, and those squary parts are designed in a way that makes it possible for example to identify the orientation of the barcode in relation to the scanner as well as to deduce the choice of format.

Any 3D-barcode would likely need something similar.

But the details depend on the type of printing/scanning available to both whoever produces such 3D-barcode labels and whoever tries to interpret them.

If asked to design an error/orientation coding scheme for such a system, I would need to know at least:

  • What kind of range of information content are we supposed to handle with this system? Would a larger 2D-barcode do just as well?
  • What can go wrong with the interpreter? Orientation? Distance? Identifying a 3D-orientation probably needs something other than those squares. But is that a problem we want to solve?
  • What kind of errors are possible? Are some types of error more likely than others (probably want to concentrate on those)?
  • How is the data encoded into the 3D-barcode (at the level of bits)?

Those are largely engineering problems. But we need at least a rough idea of these before we can begin the design of the error correction scheme. A few general remarks.

  1. If it turns out that errors in interpreting "nearby" bits correlate with each other (often happens in 2D-barcodes because a small part of the barcode may be damaged), then (possibly only then) we should probably think in terms of symbol errors. Basically treating a small lump of adjacent illegible bits as a single error event. This. Is a tell-tale sign to go with Reed-Solomon.
  2. On the other hand, it may turn out that a more typical error event involves isolated bits only. Say, the least significant bit of the height of an individual part of the 3D-barcode is often misinterpreted, but in a haphazarz way, all across the 3D-barcode. If this is a prevalent error, then we need either a different kind of an error-correcting code altogether. Or, possibly we need to restructure the encoding of data to the barcode in a different way.

With all that off my chest, I try to say something about your $xyz$. If your Reed-Solomon code uses $m$-bit symbols, we need a way to encode them in the barcode. A part of it would be just a numbers game.

If we decide to use $12$-bit symbols, and the scanner is able to reliably distinguish $8$ different heights, we could lump together a 2x2 square of adjacent locations and build a symbol of $12$ bits out of those. If there are only $4$ levels of heights, that 2x2 square would produce only $8$-bit symbols. Because RS-codes deal with symbol errors, this kind of encoding could deal with the type of error events, where damage to the barcode is typically limited to small areas.

But if a typical damage to the 3D-barcode amounts to the top layer being scrubbed away, the simple scheme of the previous paragraph is mostly useless. After all, with it the data was in the height information. Hence scrubbing would disturb several symbols. This is a much more complicated error event. For starters the errors are asymmetrical. The height may get reduced by scrubbing, but it much less likely that the height of a barcode would become higher. A totally different kind of scheme is required. We could try and use erasure recovery properties of RS-codes, building symbols differently, but I don't see that working either. I have next to no knowledge about coping with asymmetrical errors, so cannot even suggest a scheme.

  • $\begingroup$ Thank you for your insight! I had suggested RS code, merely as an example. After thinking about this problem, I recognize now that in the system where I'd like to implement such channel encoding, bit shift errors are more prone than bit insertions. At a glance, I have these beads that are embedded into a translucent gel. The inspiration came from the thought that I can manipulate the positioning of such beads to encode a 3-D barcode. Because it is translucent, I can selectively illuminate "slices" of the gel, accurately capturing each bead's (x, y, z). $\endgroup$ – batlike Jan 9 at 8:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.