I want to have 14 different qr codes, where the white boxes are transparent. Then I print it on a transparent paper, and if I put a white paper behind it, I can scan it normally. I want to be able to take any 2 of these 14 qr codes printed on a transparent paper, put one on top of the other and then behind them a white paper, and get a new valid qr code with a unique value for each combination of 2 codes from the original 14 codes. The encoded value should be something readable by a person (the user should copy the value manually, so preferably it's a short text).
How do I find these 14 values that should be encoded in the original qr codes? I have an idea, but I still need to solve the error correction code issue.
If we violate the QR encoding standard slightly by fixing a mask (which in practice the decoders won't validate), we can do this without intentional error correction failures, on the lowest error correction setting. There's a bit of slack (but not too much, I think, unless the error correcting code has more structure than I could imagine), so maybe someone else could do one or more of the following:
I'll describe at a high level what I did below, but the code is too long for me to want to post on Stack Overflow, so I uploaded it to https://github.com/eisenstatdavid/pairwise-qr-codes.
Mostly, we can think of a QR code as a fixed frame surrounding a payload. We can think of the payload as a linear-algebraic vector over the finite field GF(2), consisting of some data bits and some error correction bits. We want to find 14 vectors such that
The error correcting code specified by the QR code standard is a Reed--Solomon code, a linear code, which means that the XOR of two valid payloads is always a valid payload. So, the most straightforward way to proceed is to look for 14 vectors with pairwise disjoint support, since every pair of pairwise disjoint vectors has OR = XOR.
One way to do that is to apply linear algebra over GF(2) and observe that, if there are k error correcting bits, for every subset of k + 1 positions in the vector, there is a nonzero vector supported on a subset of those positions that is a valid payload. If the vector has n ≥ 14 (k + 1) bits total, then, we're golden. In practice, ≈ 7 k should suffice since the nonzero vector typically only sets half of the positions on which it could be supported, and we can reuse the unset positions.
Even on the lowest error correction setting, however, we don't seem to be able to get that kind of efficiency with a reasonably sized QR code. 1. In the construction above, for each vector, we can expect about half of the k + 1 positions to be set, so naively I would imagine that we could get a 2x improvement by carefully overlapping the subsets by using a constraint solver or maybe just local search.
The squeeze that puts us into a feasible rate is to use non-adaptive group testing. 9 tests suffice to distinguish pairs of 14 items, and 10 is attainable by a greedy algorithm that always chooses the test minimizing entropy.
Pretty pictures below: