论文标题
通信网络中的错误检测和校正
Error Detection and Correction in Communication Networks
论文作者
论文摘要
令$ g $为$ n $顶点上的连接图，$ c $为$（n，k，d）$ d \ ge 2 $，在字母集$ \ {0,1 \}^m $上定义。假设以$ 1 \ le i \ le n $，$ i $ th $ g $的顶点保留一个输入符号$ x_i \ in \ in \ {0,1 \}^m $，让$ \ \ \ vec {x} =（x_1，x_1，\ ldots，\ ldots，x_n）\ in \ in \ in \ in \ in \ {0,1 \ {0,1 \} =假设$ g $的每个顶点可以通过沿边缘传输消息与邻居进行通信，并且这些顶点必须根据预定的通信协议确定性决定，是否$ \ vec {x} \ in C $。那么解决此问题的最低通信成本是多少？此外，如果$ \ vec {x} \ in c $中的\ not \，例如，$ x_i $之间的$ \ lfloor（d-1）/2 \ rfloor $输入错误，那么错误纠正错误的最低通信成本是多少？ 在本文中，我们启动了上述两个问题的研究。对于错误检测问题，我们以$ n，k，d，m $的功能获得了两个下限，并且对于几个图形和代码而言，我们的界限很紧。对于错误纠正问题，我们设计了一个协议，该协议可以在$ g $为周期时有效纠正单个输入错误，而$ c $是重复代码。我们还为进一步研究提供了一些有趣的问题。
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(d-1)/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.
