On Minimum Distances for Error Correction and Detection of Generalized Network Code
Yulin CHEN Raymond W. Yeung · 2026
Read On Minimum Distances for Error Correction and Detection of Generalized Network Code by Yulin CHEN Raymond W. Yeung (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-00647.txt.
Introduction
Chen and Yeung study minimum distances for error correction and detection in generalised network codes. Minimum distance for linear network codes matches its role for classic error control codes. But Yang and Yeung showed error-correction and error-detection distances can differ for nonlinear network codes. Since the channel affects distances between codewords, the authors build a generalised network channel and code. They define correction and detection distances under this scheme, consider joint correction and detection, and characterise them fully via a distance and its refined version.
Catalog record
| CREATOR | Yulin CHEN Raymond W. Yeung |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 87385 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.00647
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On Minimum Distances for Error Correction and Detection of Generalized Network Code Yulin CHEN Raymond W. Yeung Abstract It is well known that the minimum distance for linear network codes plays the same role as the minimum distance for classical error control codes. However, Yang et al. (2008) discovered that for nonlinear network codes, the minimum distance for error correction is not always the same as the minimum distance for error detection. In this paper, we define two distances for joint error correction and detection, one being a refinement of the other, and obtain their basic properties. Then we study the relations among these two distances and the two previously defined distances for error correction and error detection. In particular, it is proved that in the case of a linear network code, only one minimum distance is needed to completely characterize the various capabilities of the code for error correction and detection. At the end of the paper, we introduce the generalized network channel as an abstraction of a network from the input-output point of view. This enables our results to be applied in a very general setting, which induces the rank metric code as a special case. I Introduction Network error correction was first studied by Yeung and Cai in [ 1 , 14 ] . Subsequently, Zhang [ 16 ] introduced an algebraic definition of minimum distance for network error correction, and Yang et al. [ 13 ] introduced a geometrical definition of minimum distance that was recently shown by Guang and Yeung [ 3 ] to be equivalent to the one introduced in [ 16 ] . This minimum distance fully characterizes the error correction capability of a linear network code. In addition to network error correction, network error detection was also considered in [ 13 ] . In particular, it was shown that for a nonlinear network code, two different distances are needed for characterizing its capabilities for error correction and error detection. This leads to the surprising discovery that for a nonlinear network code, unlike a classical block channel code, the number of correctable errors can be more than half of the number of detectable errors. Moreover, a framework that captures joint error correction and detection was introduced. In the above line of research, it is assumed that the network can be used once, and both the transmitter and the receiver have full knowledge of the network. In another line of research started by Koetter and Kschischang [ 6 ] , which was inspired by random linear network coding [ 4 ] , it is assumed that the network can be used multiple times, but the transmitter and the receiver do not need to have any knowledge on the network and its transfer characteristics except that the underlying network code is linear. This line of research is referred to as noncoherent (linear) network coding, in order to distinguish it from the original line of research on network coding. In this paper, a network code is assumed to be coherent unless otherwise specified. The current paper is a continuation of the studies in [ 13 ] . Our contributions are two-fold: 1. We formulate the transmission system studied in [ 13 ] as the generalized network channel and the generalized network code . We study the interplay between different error control functions (error correction, error detection, and joint error correction and detection) of a generalized network code by establishing fundamental bounds on the distances associated with these error control functions. 2. We formulate the notions of error-linearity for a generalized network channel and linearity for a generalized network code. In particular, all the following can be regarded as special cases of a linear generalized network code over an error-linear generalized network channel: (a) a block code in classical channel coding (b) a coherent linear network code (c) a rank metric code (d) a sum-rank metric code. We prove that for an error-linear generalized network channel, the distances for error correction, error detection, and joint error correction and detection coincide with each other, generalizing the corresponding result in [ 13 ] . The rest of the paper is organized as follows. In Section II we define the generalized network channel and the generalized network code. In Section III , four codes from the classical channel coding and network coding are casted into the framework introduced in Section II . In Section IV , we obtain a lower bound on the minimum error correction distance in terms of the minimum error detection distance. Section V is a discussion on joint network error correction and detection that contains the main results of this paper. In this section, we introduce a distance and its refined version for joint error correction and detection and prove some of their basic properties. We also obtain various bounds between the distances for error correction, error detection, and joint error correction and detection. Section VI uses the toy example in [ 13 ] to illustrate the results in the previous sections. The paper is concluded in Section VII . II Generalized Network Channel and Code In [ 13 ] , error correction and error detection were studied for a general transmission system which includes network coding as a special case. It was shown that for a nonlinear network code, two different distances are needed for characterizing its capabilities for error correction and error detection. An example of a nonlinear network code was given to illustrate that these two distances can in fact be different. Specifically, this nonlinear network code can correct one error and detect one error. This example is very intriguing because in classical channel coding, the number of errors that can be corrected is at most half of the number of errors that can be detected. On the other hand, it was proved in [ 13 ] that for a coherent linear network code, the distances for error correction and error detection coincide with each other, so that we only need one distance to characterize the capabilities of such a code for error correction and error detection. In Section V (Theorem V.5 ), we will establish the same result but in a much more general context. To start with, we formulate in this section the transmission system studied in [ 13 ] as the generalized network channel and the generalized network code. In the next section, we will show that our formulation includes a block code in classical channel coding, a coherent linear network code, a rank metric code, and a sum-rank metric code as special cases. Since the network topology and coding coefficients can be represented only by the transfer function \tilde{F} , we are motivated to introduce the generalized network channel as an abstraction of a network from the input-output point of view, with the aim to establish a more general coding scheme that focuses on whether the channel is “linear”. To formulate the generalized network channel, we let {\cal C} and {\cal E} be the set of codewords and the set of errors, respectively. The set {\cal C} and the error set {\cal E} can be arbitrary. The error set {\cal E} is equipped with a weight measure w:{\cal E}\rightarrow\mathbb{N}\cup\{0\}