Optimal binary switch codes with small query size
Zhiying Wang, Han Mao Kiah, Yuval Cassuto · 2015
In this paper, we study a construction of binary switch codes. A switch code is a code such that a multi-set request of information symbols can be simultaneously recovered from disjoint sets of codeword symbols. Our construction is optimal in the sense that it has the smallest codeword length given its average encoding degree, which is logarithmic in the code dimension. Moreover, the number of queries needed to recover any information symbol in the request is at most 2. As a result, our construction is the first family of switch codes with low encoding and decoding complexity.