2020 IEEE International Symposium
on Information Theory
21-26 June 2020 • Los Angeles, California, USA
| Paper ID | A.3.5 | ||
| Paper Title | Error Detection and Correction in Communication Networks | ||
| Authors | Chong Shangguan, Itzhak Tamo, Tel Aviv University, Israel | ||
| Session | A.3: Combinatorics and Information Theory | ||
| Presentation | Lecture | ||
| Track | Algebraic and Combinatorial Coding Theory | ||
| Manuscript | Click here to download the manuscript | ||
| Virtual Presentation | Click here to watch in the Virtual Symposium | ||
| Abstract | Let $G$ be a connected graph on $n$ vertices and $C$ be an $(n,k,d)$ code with $d\ge 2$, defined on the alphabet set $\{0,1\}^m$. Suppose that for $1\le i\le n$, the $i$-th vertex of $G$ holds an input symbol $x_i\in\{0,1\}^m$ and let $\vec{x}=(x_1,\ldots,x_n)\in\{0,1\}^{mn}$ be the input vector formed by those symbols. Assume that each vertex of $G$ can communicate with its neighbors by transmitting messages along the edges, and these vertices must decide deterministically, according to a predetermined communication protocol, that whether $\vec{x}\in C$. Then what is the minimum communication cost to solve this problem? Moreover, if $\vec{x}\not\in C$, say, there is less than $\lfloor(d1)/2\rfloor$ input errors among the $x_i$'s, then what is the minimum communication cost for error correction? In this paper we initiate the study of the two problems mentioned above.For the error detection problem, we obtain two lower bounds on the communication cost as functions of $n,k,d,m$, and our bounds are tight for several graphs and codes. For the error correction problem, we design a protocol which can efficiently correct a single input error when $G$ is a cycle and $C$ is a repetition code. We also present several interesting problems for further research. Full version available at https://www.dropbox.com/s/ov159ziw00qp39x/full.pdf?dl=0 | ||
Plan Ahead
2021 IEEE International Symposium on Information Theory
11-16 July 2021 | Melbourne, Victoria, Australia
