I'm working on an application and wondering if there's a name for the code I'm describing and any further reading.
Given $n$ items, assign a binary string for each such that the bitwise-or of any subset of up to $k$ items will be unique.
Examples:
When $k=1$, you can just assign each to a different non-zero integer, and you need $\lceil log_2 (n+1) \rceil$ bits.
When $k=n$, you can use a unary encoding with a single bit set for each integer, and you need $n$ bits.
When $n=8$, $k=2$, there are 37 subsets that need to be identified. With a computer search I found that the optimal encoding uses 7 bits:
k0 0000101
k1 0001010
k2 0001100
k3 0010010
k4 0100001
k5 0100010
k6 1000001
k7 1010000
k0 | k1 0001111
k0 | k2 0001101
k0 | k3 0010111
k0 | k4 0100101
k0 | k5 0100111
k0 | k6 1000101
k0 | k7 1010101
k1 | k2 0001110
k1 | k3 0011010
k1 | k4 0101011
k1 | k5 0101010
k1 | k6 1001011
k1 | k7 1011010
k2 | k3 0011110
k2 | k4 0101101
k2 | k5 0101110
k2 | k6 1001101
k2 | k7 1011100
k3 | k4 0110011
k3 | k5 0110010
k3 | k6 1010011
k3 | k7 1010010
k4 | k5 0100011
k4 | k6 1100001
k4 | k7 1110001
k5 | k6 1100011
k5 | k7 1110010
k6 | k7 1010001
Is there a known method for generating reasonably efficient codes of this type? If I have $k \ll n$, is the shortest code closer to $\lceil log_2 \sum_{i=0}^{k} {n \choose i} \rceil$ bits, or is it proportional to the trivial solution in $n$ bits?
This is related to combinatorial group testing. Specifically $k-$disjunct codes or $k-$cover free families are designed to ensure no union (OR combination) of $k$ sets covers (masks) another set (codeword).
Kautz-Singleton had an early construction for such codes. It was recently shown to be as good as randomised constructions see here.
OOCs are related but there you have to include all cyclic shifts of any sequence in the family.
Edit: Erdos, Frankl and Furedi proved that the maximum size of such a code (given $n$ and $k$) is upper bounded by $$ k+\binom{n}{\lceil (n-k)/\binom{k+1}{2} \rceil}, $$ see here, though Dyachov and Rykov have a better upper bound mentioned in that paper. For explicit construction details the paper by Porat and Rothschild is good to read.