Error-Correcting Codes for the Sum Channel

We introduce the sum channel, a new channel model motivated by applications in distributed storage and DNA data storage. In the error-free case, it takes as input an $\mathrm{\ell }$-row binary matrix and outputs an $(\mathrm{\ell }+1)$-row matrix whose first $\mathrm{\ell }$ rows equal the input and whose last row is their parity (sum) row. We construct a two-deletion-correcting code with redundancy $2\lceil {\log }_2{\log }_{2}n\rceil +O({\mathrm{\ell }}^2)$ for $\mathrm{\ell }$-row inputs. When $\mathrm{\ell }=2$, we establish an upper bound of $\lceil {\log }_2{\log }_{2}n\rceil +O(1)$, implying that our redundancy is optimal up to a factor of 2. We also present a code correcting a single substitution with $\lceil {\log }_2(\mathrm{\ell }+1)\rceil$ redundant bits and prove that it is within one bit of optimality.