We construct error correcting codes for jointly transmitting a finite set of independent messages to an informed receiver which has prior knowledge of the values of some subset of the messages as side information. The...
详细信息
ISBN:
(纸本)9781509018062
We construct error correcting codes for jointly transmitting a finite set of independent messages to an informed receiver which has prior knowledge of the values of some subset of the messages as side information. The transmitter is oblivious to the message subset already known to the receiver and performs encoding in such a way that any possible side information can be used efficiently at the decoder. We construct and identify several families of algebraic error correcting codes for this problem using cyclic and maximum distance separable (MDS) codes. The proposed codes are of short block length, many of them provide optimum or near-optimum error correction capabilities and guarantee larger minimum distances than known codes of similar parameters for informed receivers. The constructed codes are also useful as error correcting codes for index coding when the transmitter does not know the side information available at the receivers.
For the caching problem, when the number of files is no larger than that of users, the best known rate-memory region is achieved by memory sharing between the rate-memory pairs obtained by three schemes: the scheme pr...
详细信息
ISBN:
(纸本)9781538647813
For the caching problem, when the number of files is no larger than that of users, the best known rate-memory region is achieved by memory sharing between the rate-memory pairs obtained by three schemes: the scheme proposed by Yu et al., the scheme proposed by Gomez-Vilardebo and the scheme proposed by Tian-Chen. While the first two schemes operate on the binary field, the Tian-Chen scheme makes use of a finite field of order 2(m) with m >= K log(2) (N) in some situations, for a caching systems with K users and N files. The practical implications of this increase in the size of the field are equivalent to an increase, by a factor of m, in the number of sub file partitions required. We propose a novel caching scheme that approaches the rate-memory region achieved by the Tian-Chen scheme as the number of users in the system increases, which only requires a field of order 2(2).
We consider a cache network in which a single server is connected to multiple users via a shared error free link. The server has access to a database with N files of equal length F, and serves K users each with a cach...
详细信息
ISBN:
(纸本)9781538631805
We consider a cache network in which a single server is connected to multiple users via a shared error free link. The server has access to a database with N files of equal length F, and serves K users each with a cache memory of MF bits. A novel centralized coded caching scheme is proposed for scenarios with more users than files N <= K and cache capacities satisfying 1/K <= M <= N/K. The proposed scheme outperforms the best rate-memory region known in the literature if N <= K <= N (2)+1/2.
Broadcasting K independent messages to multiple users where each user has a subset of the K messages as side information is studied. This problem can be regarded as a natural generalization of the well-known index cod...
详细信息
ISBN:
(纸本)9781467377041
Broadcasting K independent messages to multiple users where each user has a subset of the K messages as side information is studied. This problem can be regarded as a natural generalization of the well-known index coding problem to the physical-layer additive white Gaussian noise channel due to the analogy between these two problems. Recently, Natarajan, Hong, and Viterbo proposed a novel broadcasting strategy called lattice index coding which uses lattices constructed over principal ideal domains (PIDs) as a transmission scheme and showed that such a scheme provides uniform side information gains. In this paper, we generalize this strategy to rings of algebraic integers of number fields which may not be PIDs and show upper and lower bounds on the achievable side information gains. This generalization substantially enlarges the design space and includes some interesting examples in which all the messages are from the same field.
Vehicular ad hoc networks are characterized by the dynamic movements of vehicles and intermittent and lowbandwidth connectivity and topology among vehicular nodes and roadside infrastructure. One way of understanding ...
详细信息
ISBN:
(纸本)9781665419710
Vehicular ad hoc networks are characterized by the dynamic movements of vehicles and intermittent and lowbandwidth connectivity and topology among vehicular nodes and roadside infrastructure. One way of understanding the general flow of traffic in an urban city is analyzing the movements of the vehicles that ply the roads and how road data can be disseminated to ensure travel convenience, road safety, and immediate response to urban emergency situations. In this work, data dissemination in a vehicular network employing empirical mobility traces is analyzed. Particularly, the method of index coding is incorporated to minimize the number of transmissions and transmitted size. Junctions of busy cities and their taxi mobility traces will be used to evaluate how much dynamic and static data are available and requested in a given period.
This paper presents a unified framework for Automatic Repeat reQuest (ARQ)-based retransmission schemes in multi-user broadcast environments. Two perspectives, namely, coded packet design and the enhancement of the AR...
详细信息
This paper presents a unified framework for Automatic Repeat reQuest (ARQ)-based retransmission schemes in multi-user broadcast environments. Two perspectives, namely, coded packet design and the enhancement of the ARQ protocol, are used to establish the unified framework. Consequently, the combined use of index coding and ARQ incorporated with memory is demonstrated to be beneficial toward performance enhancement in terms of transmission efficiency and memory overhead. Specifically, the asymptotic and finite transmission efficiencies of the index-coded ARQ incorporated with memory are analyzed to be close to the optimum over a wide range of packet error probabilities and the number of users, which is validated numerical evaluations. Furthermore, the use of index coding is analyzed to be also favourable in terms of memory overhead in comparison with the memory ARQ. Thus, index-coded ARQ with appropriate use of memory is shown to be a reasonable option in a practical sense, which sheds light on the possibility that multi-user coded ARQ can play a crucial role for a reliable broadcast beyond unicast.
A characteristic-dependent linear rank inequality is a linear inequality that holds by ranks of subspaces of a vector space over a finite field of determined characteristic, and does not in general hold over other cha...
详细信息
A characteristic-dependent linear rank inequality is a linear inequality that holds by ranks of subspaces of a vector space over a finite field of determined characteristic, and does not in general hold over other characteristics. In this paper, we produce new characteristic-dependent linear rank inequalities by an alternative technique to the usual Dougherty's inverse function method [9]. We take up some ideas of Blasiak [4], applied to certain complementary vector spaces, in order to produce them. Also, we present some applications to network coding. In particular, for each finite or co-finite set of primes P, we show that there exists a sequence of networks N(k) in which each member is linearly solvable over a field if and only if the characteristic of the field is in P, and the linear capacity, over fields whose characteristic is not in P, -> 0 as k -> infinity.
In this work, we formulate and study a data dissemination problem, which can be viewed as a generalization of the index coding problem and of the data exchange problem to networks with an arbitrary topology. We define...
详细信息
ISBN:
(纸本)9781509018253
In this work, we formulate and study a data dissemination problem, which can be viewed as a generalization of the index coding problem and of the data exchange problem to networks with an arbitrary topology. We define r-solvable networks, in which data dissemination can be achieved in r> 0 communications rounds. We show that the optimum number of transmissions for any one-round communications scheme is given by the minimum rank of a certain constrained family of matrices. For a special case of this problem, called bipartite data dissemination problem, we present lower and upper graph-theoretic bounds on the optimum number of transmissions. For general r-solvable networks, we derive an upper bound on the minimum number of transmissions in any scheme with> r rounds. We experimentally compare the obtained upper bound to a simple lower bound.
暂无评论