I'm a doctor studying tiny specimen under a microscope. I had this strange idea to "barcode" each specimen with a physical barcode. This barcode is assembled from two pigments which can be analogized as {1, 0}.

My goal is to find an error-correcting barcode that can be physically assembled from these two pigments, and decodable even despite noisy images (hence, the importance of error-correcting bits).

Because the microscope resolution is finite, there's a certain "agglomeration" size of pigments that can be visualized. For instance, a codeword with many alternating bits (ie. 10101010) blurs together and cannot be distinguished. But, a codeword with agglomeration >= $a$ (ie. 11110001110000 has $a$ = 3) can be distinguished.

My question is, for some linear binary code of length $n$ and rank $k$, what is the subspace of $ \mathbb {F} _{2}^{n}$ where the shortest stretch of any digit is >= $a$ called? Are there robust ways of discovering all such codewords? (Is this related by any chance to covering sets?). I realize this is a bit more applied than most questions here, please also forgive my ignorance!

  • 3
    $\begingroup$ Maybe use "111","000" as the actual coding symbols, then you are back to a binary code, that is guaranteed to be distinguished. $\endgroup$
    – user619894
    Feb 7, 2021 at 8:56
  • 1
    $\begingroup$ This is not a bad suggestion, but for subtleties that I don't describe above, this barcoding technique would be more powerful for a variable length "stretch" (ie. "1111", "11111", "111111" ... "0000", "00000", "000000" for a = 4). $\endgroup$
    – batlike
    Feb 7, 2021 at 9:12
  • 2
    $\begingroup$ Linearity may easily ruin your wishes. Say, if you want to allow both 1111000 as well as 1110000, then the Hamming distance will drop down to two. My first idea was the same user619894 also suggested. A somewhat more refined idea might be to treat variation on the run length $a$ as some kind of a reliability measure. Say, if you try to consistently use agglomerates of length $a=6$, but due to whatever reason (specimen motion while the barcode is "printed"?) the run of 1s or 0s may have length $5$ or $7$ instead. Then you could have some heuristics at play when "reading" the barcode. $\endgroup$ Feb 7, 2021 at 16:17
  • 1
    $\begingroup$ @JyrkiLahtonen - "runlength constrained code" - for magnetic media, longer runs in bit patterns are used for sync in schemes like MFM. For drives that use rotating heads, the encoded data needs to be nearly DC free, since it passes through a (rotating) transformer. Typically 8 bits of data are expanded into 10 bit sequences, with dual sequences for specific 8 bit values, which are alternated as needed to keep the encoded data nearly DC free. $\endgroup$
    – rcgldr
    Feb 8, 2021 at 21:20
  • 2
    $\begingroup$ The "channel errors" in this case correspond to bit fliping, or rather to sync errors? That is, "111000", can be misread as "111010" or perhaps as "1111000" ? $\endgroup$
    – leonbloy
    Feb 9, 2021 at 2:23


You must log in to answer this question.