אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

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 $\ell$-row binary matrix and outputs an $(\ell+1)$-row matrix whose first $\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+ \log_2 \ell + O(1)$ for $\ell$-row inputs. When $\ell=2$, we establish a lower bound of $\lceil\log_2\log_2 n\rceil + O(1)$ bits, 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(\ell+1)\rceil$ redundant bits and prove that it is within one bit of optimality.