Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userNetwork error correction with limited feedback capacity
124
0
0.0
(
0
)
Added by
Yanbo Yang
Publication date
2013
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We consider the problem of characterizing network capacity in the presence of adversarial errors on network links,focusing in particular on the effect of low-capacity feedback links cross network cuts.
rate research
Read More
The zero-error feedback capacity of the Gelfand-Pinsker channel is established. It can be positive even if the channels zero-error capacity is zero in the absence of feedback. Moreover, the error-free transmission of a single bit may require more than one channel use. These phenomena do not occur when the state is revealed to the transmitter causally, a case that is solved here using Shannon strategies. Cost constraints on the channel inputs or channel states are also discussed, as is the scenario where---in addition to the message---also the state sequence must be recovered.
We consider linear network error correction (LNEC) coding when errors may occur on edges of a communication network of which the topology is known. In this paper, we first revisit and explore the framework of LNEC coding, and then unify two well-known LNEC coding approaches. Furthermore, by developing a graph-theoretic approach to the framework of LNEC coding, we obtain a significantly enhanced characterization of the error correction capability of LNEC codes in terms of the minimum distances at the sink nodes. In LNEC coding, the minimum required field size for the existence of LNEC codes, in particular LNEC maximum distance separable (MDS) codes which are a type of most important optimal codes, is an open problem not only of theoretical interest but also of practical importance, because it is closely related to the implementation of the coding scheme in terms of computational complexity and storage requirement. By applying the graph-theoretic approach, we obtain an improved upper bound on the minimum required field size. The improvement over the existing results is in general significant. The improved upper bound, which is graph-theoretic, depends only on the network topology and requirement of the error correction capability but not on a specific code construction. However, this bound is not given in an explicit form. We thus develop an efficient algorithm that can compute the bound in linear time. In developing the upper bound and the efficient algorithm for computing this bound, various graph-theoretic concepts are introduced. These concepts appear to be of fundamental interest in graph theory and they may have further applications in graph theory and beyond.
A Viterbi-like decoding algorithm is proposed in this paper for generalized convolutional network error correction coding. Different from classical Viterbi algorithm, our decoding algorithm is based on minimum error weight rather than the shortest Hamming distance between received and sent sequences. Network errors may disperse or neutralize due to network transmission and convolutional network coding. Therefore, classical decoding algorithm cannot be employed any more. Source decoding was proposed by multiplying the inverse of network transmission matrix, where the inverse is hard to compute. Starting from the Maximum A Posteriori (MAP) decoding criterion, we find that it is equivalent to the minimum error weight under our model. Inspired by Viterbi algorithm, we propose a Viterbi-like decoding algorithm based on minimum error weight of combined error vectors, which can be carried out directly at sink nodes and can correct any network errors within the capability of convolutional network error correction codes (CNECC). Under certain situations, the proposed algorithm can realize the distributed decoding of CNECC.
In this work, we analyze the performance of a signature quantization scheme for reverse-link Direct Sequence (DS)- Code Division Multiple Access (CDMA). Assuming perfect estimates of the channel and interference covariance, the receiver selects the signature that minimizes interference power or maximizes signal-to-interference plus noise ratio (SINR) for a desired user from a signature codebook. The codebook index corresponding to the optimal signature is then relayed to the user with a finite number of bits via a feedback channel. Here we are interested in the performance of a Random Vector Quantization (RVQ) codebook, which contains independent isotropically distributed vectors. Assuming arbitrary transmit power allocation, we consider additive white Gaussian noise (AWGN) channel first with no fading and subsequently, with multipath fading. We derive the corresponding SINR in a large system limit at the output of matched filter and linear minimum mean squared error (MMSE) receiver. Numerical examples show that the derived large system results give a good approximation to the performance of finite-size system and that the MMSE receiver achieves close to a single-user performance with only one feedback bit per signature element.
Index coding is a source coding problem in which a broadcaster seeks to meet the different demands of several users, each of whom is assumed to have some prior information on the data held by the sender. If the sender knows its clients requests and their side-information sets, then the number of packet transmissions required to satisfy all users demands can be greatly reduced if the data is encoded before sending. The collection of side-information indices as well as the indices of the requested data is described as an instance of the index coding with side-information (ICSI) problem. The encoding function is called the index code of the instance, and the number of transmissions employed by the code is referred to as its length. The main ICSI problem is to determine the optimal length of an index code for and instance. As this number is hard to compute, bounds approximating it are sought, as are algorithms to compute efficient index codes. Two interesting generalizations of the problem that have appeared in the literature are the subject of this work. The first of these is the case of index coding with coded side information, in which linear combinations of the source data are both requested by and held as users side-information. The second is the introduction of error-correction in the problem, in which the broadcast channel is subject to noise. In this paper we characterize the optimal length of a scalar or vector linear index code with coded side information (ICCSI) over a finite field in terms of a generalized min-rank and give bounds on this number based on constructions of random codes for an arbitrary instance. We furthermore consider the length of an optimal error correcting code for an instance of the ICCSI problem and obtain bounds on this number, both for the Hamming metric and for rank-metric errors. We describe decoding algorithms for both categories of errors.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
