5
$\begingroup$

I want to reversibly transcode arbitrary information (a digital signature), initially $n$ bits, into symbols in an alphabet with $s$ symbols, with little space loss. In my application‡ $s=45$. Thus I can e.g. transcode $n=192$ bits into $m=\lceil n/\log_2s\rceil=\lceil34.961\ldots\rceil=35$ symbols with less than $0.12\%$ density loss.

I have working C code for this using textbook base conversion, including the necessary arbitrary-precision arithmetic on an integer up to $s^m\approx2^n$. It require $\mathcal o(n)$ bits of temporary space for that integer, and $\mathcal O(n^2)$ time. For the beauty of it, I'm in search for (not exclusive)

  • a method achieving the same density (or at least $m=35$ for $n=192$, $s=45$) with a simpler symbols-to-bits conversion algorithm, even if somewhat more temporary space is needed to run the algorithm, and the bits-to-symbols conversion was complex.
  • a proof (or disproof) that for odd $s$, any method with density as good as base conversion requires $n$ bits of temporary space in the decoder, on top of the $m$-symbols read-only input.

Update: I do not need compatibility with a pre-existing encoding. I could live without detection at decoding that a combination of $m$ symbols among $s$ can't be generated by proper encoding of $n$ bits.


Encoding on "QR codes" using the "Aphanumeric mode", which is more compatible with various deployed readers than the "Byte mode". $s=45$ is such that $2\log_2(s)\approx10.9837\lesssim11$, allowing the QR code standard to store $2$ symbols into $11$ bits with less than $0.15\%$ space loss.
Update: Problem with the binary mode is that existing readers (physical devices, apps on a mobile phone) are harder to interconnect to other devices/wares when their output is arbitrary bytes, e.g. a digital signature. Issues include 7-bit serial mode; XOFF (0x13) halting serial communications; binary mode being intentionally disabled to block denial of service by the previous method; NUL (0x00) terminating a C string; filters limiting strings to valid UTF8.

$\endgroup$
5
  • $\begingroup$ A good communication protocol must be able to transparently transmit the non printing characters. $\endgroup$
    – user16034
    Mar 17, 2023 at 12:35
  • $\begingroup$ By "storage", do you mean additional storage, beyond read-only access to the $n$-bit input? $\endgroup$
    – D.W.
    Mar 17, 2023 at 18:37
  • $\begingroup$ A plausible approach is to split the input into 11-bit blocks and split on two cases: (a) no 11-bit block has a value larger than 2024, (b) one or more 11-bit blocks have a value larger than 2024. Case (a) is easy to handle, by transcoding the 17 11-bit blocks into two symbols, and transcoding the remaining 5 bits into one more symbol, reserving the other 13 values for that symbol to indicate we are in case (b). Case (b) can probably be handled through a separate mechanism, by using those other 13 values to indicate we are in case (b). $\endgroup$
    – D.W.
    Mar 17, 2023 at 19:08
  • $\begingroup$ @D.W. (on your first comment) No, it's not storage as in data storage. The QR code content is static (e.g. printed). It only carries a message and it's signature, totaling perhaps 400 to 900 bits. For the application, think access to a train platform. I want to keep the QR code as easy to use as possible, and that means with as little data encoded as possible. (on the second comment) I'm looking for something on that tune. But everything I tried so far beyond straight base conversion turned out significantly less compact on average, and with an annoying variance on top of that. $\endgroup$
    – fgrieu
    Mar 17, 2023 at 19:27
  • $\begingroup$ @D.W. I finally understood your first comment. I meant temporary RAM space, in addition of the $m$ symbols input of the decoder. You disproved my initial conjecture! I now fixed the question to use more standard vocabulary. $\endgroup$
    – fgrieu
    Mar 17, 2023 at 22:22

1 Answer 1

4
$\begingroup$

Divide the first 187 bits into 17 blocks of 11-bit values. This leaves 5 bits left over. Call each 11-bit block good if it it corresponds to a number in the range $0 \ldots 2024$, or bad if it is in the range $2025 \ldots 2047$. (Note that $2025 = 45^2$, so a good block can be encoded into two symbols.) We'll store the left-over 5 bits (in a symbol or less), a list of bad blocks, then a list of good blocks. To handle the specifics of exactly how to do that, we'll case-split into two cases:

  • Case A: All of those 17 11-bit blocks are good.

  • Case B: One or more of those 17 11-bit blocks is bad.

We will encode those two cases differently.

  • Case A: Encode the left-over 5 bits into the first symbol, using values $0 \ldots 31$. Then, encode each of the 17 11-bit blocks into two symbols. Since they are all in the range $0 \ldots 2024$, each can be encoded into two symbols. This uses a total of $1+2\times 17 = 35$ symbols.

  • Case B: The general concept is that we'll store the left-over 5 bits, then a list of all bad blocks, then a list of all good blocks. The rough idea is that each bad block can be represented in two symbols, and each good block can be represented in two symbols, but we'll have to make some tweaks to squeeze the left-over 5 bits in somewhere.

    Specifically, we will store the 5 left-over bits and the first bad block in the first three symbols. They will be followed by a list of the rest of the bad blocks. Each bad block will correspond to a tuple $\langle i,\ell,v \rangle$, where $i$ represents the index of the bad block, $\ell$ is a boolean indicating whether it is the last bad block, and $v$ is the value of the bad block. There are $17$ possible values for $i$, $2$ possible values for $\ell$, and $23$ possible values for $v$, so in total we have $17 \times 2 \times 23 = 782$ possible tuples.

    The first bad block will be encoded in a special way. In particular, we encode the 5 left-over bits and the tuple of the first bad block into the first three symbols. Here we have $2^5 \times 782=25024$ possible values to represent, and there are $13 \times 45^2$ possible values for the first three symbols (we have to avoid the 32 possible values for the first symbol that is taken up by case A), so the tuple of the first bad block and 5 left-over bits can be encoded into the first three symbols.

    Then, we'll store a list of the rest of the bad blocks,

    $$\langle i_2,\text{False},v_2 \rangle, \dots \langle i_{k-1},\text{False},v_{k-1} \rangle, \langle i_k,\text{True},v_k \rangle,$$

    where each tuple $\langle i_j,\ell_j,v_j \rangle$ represents a single bad block. Here $i_j$ represents the index of the $j$th bad block, $\ell_j$ is a boolean that indicates whether it is the last bad block in the list or not, and $v_j$ represents value of the bad block itself. There are $17$ possible values for $i$, $2$ possible values for $\ell$, and $2048-2025=23$ possible values for $v$, so there are $17 \times 2 \times 23 = 782$ possible values for the tuple. Therefore each tuple can be encoded easily into two symbols.

    The list of good blocks will be represented by simply encoding each good block into two symbols.

    So, assuming there are $k$ bad blocks, the first 3 symbols will contain the 5 left-over bits and the first bad block, the next $2k-2$ symbols will encode the list of the rest of bad blocks (2 symbols per bad block), and the remaining $34-2k$ symbols will contain the list of $17-k$ good values, in order (2 symbols per good block). Thus, case B uses a total of $35$ symbols.


This provides a valid encoding that can be uniquely decoded. Also, the total amount of additional storage required is about 12 bits for Case A, or about 24 bits for Case B. Regardless of which case we are in, this is less storage and probably faster running time than textbook base conversion.

$\endgroup$
1
  • $\begingroup$ I verified it carefully, and found no gap. It fits the stated problem perfectly. Congratulations, I was quite uncertain that this was possible! Now I have to decide about using it, and in the affirmative what I do about the last block of bits that does not fit a 192-bit chunk (which is pretty easy with textbook base conversion). $\endgroup$
    – fgrieu
    Mar 17, 2023 at 22:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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