0
$\begingroup$

Suppose you want an encoding of the integers $ \{0,1,2,\ldots,N-1\} $ into bitstrings. Two ways to do this are standard binary place value and unary encoding. The binary place value method is efficient in that it uses only $\log_2 N$ bits. However, given an $x \in \{0,1,2,\ldots,N-1\}$, to check whether a bitstring encodes $x$ you have to read all $\log_2 N$ bits.The unary coding is the other extreme: the encoding is very space-inefficient in that it uses $N$ bits, but to check whether the string represents $x$ you only have to read two of the bits, namely bit $x$ and bit $x+1$ which must be 1 and 0 respectively if the bitstring encodes $x$. My question is: what is known about encodings in between these two extremes? Can we encode the the integers $\{0,\ldots,N-1\}$ into bitstrings of length scaling less than linearly with $N$ such that we can check whether the bitstring encodes $x$ by looking at only a constant number of bits? I assume that somehow by squinting at this question the right way it can be mapped onto a well-studied question about error correcting codes, combinatorial designs, or something of that sort.

$\endgroup$
1
  • $\begingroup$ A related concept in computer science is probabilistically checkable proofs (PCPs) where, after reading just a few bits of a proof (randomly chosen), one can tell with good probability if it is valid or not. $\endgroup$
    – usul
    Oct 2 '16 at 19:50
1
$\begingroup$

Fix $k$ which will be your constant. Assume that the string length is $d$. Set $N={d\choose k}$, and to every $x\in \{0,\dots,N-1\}$ put into bijective correspondence a $k$-tuple of positions $F_x$. Now you may encode $x$ by pussing ones eactly at the positions from $F_x$, and then check `$x$-ness' by the same positions.

$\endgroup$
4
  • $\begingroup$ Ah, perhaps my question was more elementary than I realized. Thank you for this simple and very satisfactory answer. $\endgroup$
    – StephenJ
    Oct 2 '16 at 19:49
  • $\begingroup$ How about a lower bound? $\endgroup$
    – usul
    Oct 2 '16 at 19:53
  • $\begingroup$ For some error detection, I recommend checking K other bits to assure that they are zero. Which bits will depend on where the errors are likely to occur. Gerhard "Safety Is A Constant Concern" Paseman, 2016.10.02. $\endgroup$ Oct 2 '16 at 21:14
  • $\begingroup$ @GerhardPaseman, at that point I think this begins to resemble the Bloom filter data structure. $\endgroup$
    – usul
    Oct 2 '16 at 22:13

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.