Maximum size of abandonable codes

43 Views Asked by At

Consider a keypad which accepts fixed-length numeric sequences from $b$ symbols and maps them uniquely to a set of actions. What is the largest set of actions which can be mapped for a given length of key $n$, subject to them being abandonable. Abandoning a code means that after entering a number of characters $k<n$, the enterer may completely forget that they were entering a code and start another. The partially entered code has no effect, the one which is completed acting as if not prefixed.

This is clearly related to the issue of synchronisaiton and is, I suppose, a very tight bound on a self-synchronising prefix code. No special "abandon" sequence is permitted, as the enterer has no knowledge of any earlier entry. They must also be prefix codes, ie completion be implicit in the sequence. Within these constraints, what is the maximum number of valid codes?

From what I can see, for $b=2$, there is a trivial code with $n=1$ mapping to two actions which cannot be extended to larger $n$.

For larger numbers of symbols, the obvious approach, which is easily analysed, is to reserve one symbol as valid only for the initial character of a code. For example, with $b=10$, $n=3$, we can insist the first character is $1$ and so have $(b-1)^2 = 81$ codes. For example the sequence $1213121156$ would map to $156$ and $141912317178$ would map to actions $123, 178$. By simple extension, $m<b$ such codes can be reserved for the initial character, giving $m(b-m)^2$ codes, but this is clearly optimal when $m=1$.

I'm sure there is a clever procedure which can exceed $(b-1)^{(n-1)}$?