We study a variant of the coded caching problem where a server, with a library of files, serves users through a broadcast link. Each user is equipped with a private cache and additionally connects to L neighboring access caches in a cyclic wrap-around manner. This setting generalizes the cyclic wraparound networks studied in coded caching by incorporating private caches. For this model, we propose a coded caching scheme under uncoded placement, characterize its achievable rate, and derive a cut-set-based lower bound on the optimal worst-case rate. The optimality of the scheme is proven in the large-memory regime and verified through numerical comparisons.

This paper investigates single-error-correcting function-correcting codes (SEFCCs) for the Hamming code membership function (HCMF), which indicates whether a vector in $\mathbb{F}_2^7$ belongs to the [7,4,3]-Hamming code. Necessary and sufficient conditions for valid parity assignments are established in terms of distance constraints between codewords and their nearest non-codewords. It is shown that the Hamming-distance-3 relations among Hamming codewords induce a bipartite graph, a fundamental geometric property that is exploited to develop a systematic SEFCC construction. By deriving a tight upper bound on the sum of pairwise distances, we prove that the proposed bipartite construction uniquely achieves the maximum sum-distance, the largest possible minimum distance of 2, and the minimum number of distance-2 codeword pairs. Consequently, for the HCMF SEFCC problem, sum-distance maximisation is not merely heuristic-it exactly enforces the optimal distance-spectrum properties relevant to error probability. Simulation results over AWGN channels with soft-decision decoding confirm that the resulting max-sum SEFCCs provide significantly improved data protection and Bit Error Rate (BER) performance compared to arbitrary valid assignments.

Function-Correcting Codes (FCCs) enable reliable computation of a function of a $k$-bit message over noisy channels without requiring full message recovery. In this work, we study optimal single-error correcting FCCs (SEFCCs) for maximally-unbalanced Boolean functions, where $k$ denotes the message length and $t$ denotes the error-correction capability. We analyze the structure of optimal SEFCC constructions through their associated codeword distance matrices and identify distinct FCC classes based on this structure. We then examine the impact of these structural differences on error performance by evaluating representative FCCs over the additive white Gaussian noise (AWGN) channel using both soft-decision and hard-decision decoding. The results show that FCCs with different distance-matrix structures can exhibit markedly different Data BER and function error behavior, and that the influence of code structure depends strongly on the decoding strategy.

We study hotplug coded caching in combinatorial multi-access networks, which generalizes existing hotplug coded caching models by allowing users to access multiple caches, while only a subset of caches is online during the delivery phase. We first generalize the Hotplug Placement Delivery Array (HpPDA) framework to the combinatorial multi-access setting. Based on this generalized framework, we propose a t-design-based coded caching scheme for combinatorial multi-access networks. We characterize a class of design parameters under which every active user has access to a sufficient number of coded subfiles to decode its requested file, and show that appropriate parameter choices allow for the elimination of redundant multicast transmissions. As a result, the proposed scheme achieves a family of rate memory trade offs with flexible subpacketization. We present numerical comparisons illustrating that the proposed t-scheme outperforms existing hotplug coded caching schemes in certain memory regimes.

We consider a variant of the coded caching problem where users connect to two types of caches, called private and access caches. The problem setting consists of a server with a library of files and a set of access caches. Each user, equipped with a private cache, connects to a distinct$r$-subset of the access caches. For this setting, we provide a coded caching scheme and derive a lower bound on the number of transmissions for this scheme. We also present lower and upper bounds for the optimal worst-case rate under uncoded placement for this setting using the rates of the Maddah-Ali-Niesen scheme for dedicated and combinatorial multi-access coded caching settings, respectively. Further, we derive a lower bound on the optimal worst-case rate for any general placement policy using cut-set arguments. Numerical plots comparing the rate of the proposed achievability scheme with the above bounds are also provided, from which it can be observed that the proposed scheme approaches the lower bound in the large-memory regime.

Consider single unicast index coding problems with prioritized receivers with transmissions over additive white Gaussian (AWGN) channels. In this setting, if a length-N index-coded vector is transmitted as a 2N-PSK symbol, there will exist some receivers, especially the lower priority ones, that would not see much improvement over the average bit error probability obtained for a 2N-PSK modulated transmission. On the other hand, if we use binary-modulated transmission, which gives the best probability of performance at the receivers, it will result in an N/2 -fold increase in the bandwidth consumed. Hence, in a setting where each receiver has to satisfy some quality of service requirements, we propose multi-symbol PSK-modulated transmission for a bandwidth-performance trade-off where the$N$index-coded bits are mapped to complex symbols of multiple smaller-sized constellations. Depending on the available bandwidth, we can choose the number of symbols to which the N-bit index-coded vector should be mapped. In addition to proposing the multi-symbol modulated transmission, we present an algorithm that takes the$N$bits of the index-coded vector and maps it to the multiple complex symbols in a way that guarantees that the highest priority receiver sees the best possible performance followed by the second-highest priority receiver and so on. For the special case of single unicast single uniprior index coding problems, we also describe optimal index code selection to ensure that the highest priority receiver sees the best performance.

Abstract-This paper studies noisy index coding problems over broadcast channels. The codewords from a chosen binary index code of lengthNare mapped to a 2N-PSK constellation before being transmitted over an AWGN channel. The receivers follow the two-step decoding process of first estimating the PSK symbol using a maximum-likelihood decoder and then performing index code decoding. After estimating the PSK symbol, there is, in general, more than one decoding strategy at a receiver, i.e., more than one linear combination of index-coded bits along with a subset of side information bits, that can be used to estimate the requested message. Thomas et al. in [“Single Uniprior Index Coding With Min–Max Probability of Error Over Fading Channels,” IEEE Transactions on Vehicular Technology, pp. 6050-6059, July 2017] showed that for binary-modulated index code transmissions, minimizing the number of transmissions used to decode a requested message is equivalent to reducing the probability of error. This paper shows that this is no longer true while employing multi-level modulations. Further, we consider the side information available to each receiver also to be noisy and derive an expression for the probability that a requested message bit is estimated erroneously at a receiver. We also show that the criterion for choosing a decoding strategy that gives the best probability of error performance at a receiver changes with the signal-to-noise ratio at which the side information is broadcast. Hence, for a given index coding problem and a chosen index code, we give an algorithm to select the best decoding strategy for the receivers. The above results are shown to be valid over fading channels also.

Ong and Ho developed optimal linear index codes for single uniprior index coding problems (ICPs) by finding a spanning tree for each strongly connected component of their information-flow graphs, following which Thomas et al. considered the same class of ICPs over Rayleigh fading channels. They developed the min-max probability of error criterion for choosing an index code from the set of bandwidth-optimal linear index codes. Motivated by the above works, this paper deals with single uniprior ICPs over binary-input continuous-output channels. Minimizing the average probability of error is introduced as a criterion for further selection of index codes which is shown to be equivalent to minimizing the total number of transmissions used for decoding the message requests at all the receivers. An algorithm that generates a spanning tree with a lower value of this metric than the optimal star graph is also presented. A couple of lower bounds for the total number of transmissions, used by any optimal index code, are derived, and two classes of ICPs for which these bounds are tight are identified. An improvement of the proposed algorithm for information-flow graphs with bridges and a generalization of the improved algorithm for information-flow graphs obtainable as the union of strongly connected sub-graphs are presented, and some optimality results are derived.

Ong and Ho developed optimal linear index codes for single uniprior index coding problems (ICPs) by finding a spanning tree for each of the strongly connected components of the corresponding information-flow graphs, following which Thomas et al. considered the same class of ICPs over Rayleigh fading channel. They developed the min-max probability of error criterion for choosing an index code which minimized the probability of error at the receivers and showed that there always exist optimal linear index codes for which any receiver takes at most two transmissions to decode a requested message. Motivated by the above works, this paper considers single uniprior ICPs over Rayleigh fading channels for which minimizing average probability of error is shown to be a criterion for further selection of index codes. The optimal index code w.r.t this criterion is shown to be one that minimizes the total number of transmissions used for decoding the message requests at all the receivers. An algorithm that generates a spanning tree which has a lower value of this metric as compared to the optimal star graph is also presented. For a given set of parameters of single uniprior ICPs, a lower bound for the total number of transmissions used by any optimal index code is derived, and a class of ICPs for which this bound is tight is identified.

Coded caching techniques help to reduce the traffic overload on the server during peak-traffic hours. Most of the existing schemes consider all transmissions to be over noiseless channels, whereas noise is inherent in wireless communication. In this paper, the multi-access coded caching scheme proposed in the paper [“Maddah-Ali-Niesen Scheme for Multi-access Coded Caching,” ITW 2021], is studied when the server-user shared link and all the cache-user links are noisy. This coded caching has been shown to be information-theoretically optimal in [“Fundamental Limits of Combinatorial Multi-Access Caching,” IEEE Transactions on Information Theory, Feb. 2023]. For binary modulated transmissions, the probability that a bit of a requested file is decoded in error at a user is derived when the transmissions are over binary-symmetric, AWGN, and Rayleigh fading channels. Further, the effect of varying the cache access degree (which is the number of caches accessed by each user), and the cache memory size on the probability of bit error performance at a user are also analyzed. Simulation results validating the findings in this paper are also presented.

This paper considers the problem of broadcasting with side information (BWSI), where a central server broadcasts encoded transmissions using$M$-ary modulation to a set of caching receivers over an additive white Gaussian noise channel. For this problem of noisy index coding with$M$-ary modulated transmission, the ML decoder at any receiver does not involve demodulation to the complex signal point and then index code decoding to the requested message bit. Instead, it decodes directly to the requested message bit, raising the question of whether the central server’s encoding scheme is required to correspond to an index code or if any set of transmissions encoding across the entire library of messages is sufficient. This paper proves that index codes are necessary for solving noisy BWSI problems even with$M$-ary modulated transmission. Further, we look at index-coded QAM for prioritized receivers. An algorithm for mapping index-coded vectors to signal points on a square QAM constellation is presented, which gives mappings that achieve the best ML decoding performance for the prioritized receivers. Expressions for the ML metric seen by the highest priority receiver while using$M$-PSK and$M$-QAM for transmission are derived. For the highest priority receiver,$M$-PSK is shown to outperform$M$-QAM.

This paper deals with embedded index coding problem (EICP), introduced by A. Porter and M. Wootters, which is a decentralized communication problem among users with side information. An alternate definition of the parameter minrank of an EICP, which has reduced computational complexity compared to the existing definition, is presented. A graphical representation for an EICP is given using directed bipartite graphs, called bipartite problem graph, and the side information alone is represented using an undirected bipartite graph called the side information bipartite graph. Inspired by the well-studied single unicast index coding problem, graphical structures, similar to cycles and cliques, are identified in the side information bipartite graph of a single unicast embedded index coding problem (SUEICP). Transmission schemes based on these graphical structures, called tree cover scheme and bi-clique cover scheme are also presented. For a class of SUEICPs, scalar linear optimal solution is given using bi-clique cover. A relation between connectedness of the side information bipartite graph and the number of transmissions required in a scalar linear solution of an EICP is established.

The demand for multimedia services is growing day by day in vehicular ad-hoc networks (VANETs), resulting in high spectral usage and network congestion. Non-orthogonal multiple access (NOMA) is a promising wireless communication technique to solve the problems related to spectral efficiency effectively. The index coding (IC) is a powerful method to improve spectral utilization, where a sender aims to satisfy the needs of multiple receivers with a minimum number of transmissions. By combining these two approaches, in this work, we propose a novel technique called index coded NOMA (IC-NOMA), where we apply NOMA techniques on index coded data to reduce the number of transmissions further. This work shows that the IC-NOMA system demands a specific design for index codes to reap the advantages of NOMA. We have done the feasibility analysis of the proposed method in a general scenario and proposed an index code design to integrate IC over NOMA for the best efficiency. The performance gains of proposed system compared to conventional IC system is ilustrated in terms of power efficiency and spectral efficiency.

Vehicle to vehicle (V2V) communication has gained its importance in recent years. In this work we consider the index coding problem (ICP) over noisy channel in V2V communication phase of message dissemination. The ICP in V2V communication is considered as device to device ICP with transmitting nodes as receiving nodes also. The index code is used in noisy scenario over AWGN channel and the broadcast vectors are mapped to suitable M-PSK signal constellations to save bandwidth, thus increasing the bandwidth efficiency. An algorithm is proposed to derive suitable mapping of the broadcast vectors to M-PSK signal constellation for improving the error performance. Performance improvement in terms of PSK index coding gain is discussed. While one vehicle transmits, the proposed algorithm provides performance improvement for at least one of the remaining vehicles, in most of the scenarios, while not penalizing the other vehicles.

Stragglers, adversaries and colluding workers are some of the key problems affecting the performance of a distributed computing system. There have been many works in reducing the recovery threshold (i.e. minimum number of workers the master needs to wait, to compute the final output), while tackling adversaries and colluding workers for providing security and data privacy. These works generally consider datasets over arbitrary fields i.e. fields of characteristic both zero and prime. In this paper, we show that, for distributed computing problems over finite fields, performing the computations over an appropriately-sized extension field can improve the recovery threshold with a trade off only in computational complexity while preserving the privacy and security parameters. We show this for two schemes: (i) Lagrange coded computing scheme for evaluating an arbitrary multivariate polynomial over a dataset over finite fields, proposed in [Q. Yu, N. Raviv, J. So, and A. S. Avestimehr, “Lagrange coded computing: Optimal design for resiliency, security and privacy,” arXiv:1806.00939v3] and (ii) private secure matrix multiplication discussed in [M. Kim, and J. Lee, “Private Secure Coded Computation,” arXiv:1902.00167]. When a proper degree of field extension is chosen, the proposed coding schemes is applicable even in cases where the original schemes are not applicable because of insufficient number of workers or insufficient field size.

For the problem of embedded index coding, a matrix representation, called a side-information matrix and a metric called min-rank are defined to characterize the length of an optimal embedded index code. An optimal embedded index code for a given embedded index coding problem is shown to be obtainable from the columns of its side information matrix. Further, for a class of embedded index coding problems, called one-sided neighboring side information problems, the min-rank is derived and a transmission scheme which has length equal to this min-rank is presented.

This paper addresses the problem of exponentially increasing sub-packetization with the number of users in a centralized coded caching system by introducing a new coded caching scheme inspired by the symmetric neighboring consecutive side information index coding problem. The scheme has a placement policy where the number of sub-packets required grows only linearly with the number of users, with no restriction on the number of users or file size, and a delivery policy which is instantaneously decodable. Further, an application of the new delivery scheme in a multi-access coded caching set-up is studied and a few results in that direction are presented. In particular, in the multi-access set-up, for cases where optimality rate-memory trade-off characterizations are available, it is shown that the new delivery scheme achieves optimal or near-optimal rates.

In this paper, noisy index coding problems over AWGN channel are considered. For a given index coding problem and a chosen scalar linear index code of length N, we propose to transmit the N index coded bits as a single signal from a 2-PSK constellation. By transmitting the index coded bits in this way, there is an N/2-fold reduction in the required bandwidth. Also, by transmitting the index coded bits as a PSK signal, receivers with side information satisfying certain conditions get coding gain relative to a receiver with no side information. This coding gain obtained by the receivers is due to proper utilization of their side information and hence is called “PSK side information coding gain (PSK-SICG)”. We state and prove a necessary and sufficient condition for a receiver to get PSK-SICG. An algorithm to map the index coded bits to PSK signal set such that the PSK-SICG obtained is maximized for the receiver with maximum side information is given. Further, we show that if index coded bits are transmitted as a PSK signal, it is not always necessary to minimize the length of index code used as there are index coding problems where use of a longer index code will give a better performance in terms of probability of error.