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) are a class of codes designed to protect the evaluation of a specific function of a message against channel errors at a higher level than the level of protection for the message, while requiring significantly less redundancy than conventional error-correcting codes. In this paper, we study function-correcting codes under the sum-rank metric, which is a natural generalization of both the Hamming metric and the rank-metric and also we derive general upper and lower bounds on the optimal redundancy of FCCs in the sum-rank metric. In particular, we establish a Plotkin-like bound for irregular-distance codes in sum-rank metric. Furthermore, we present explicit construction of function-correcting sum-rank metric codes (FCSRCs) for locally binary functions with optimal redundancy.

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.

In this paper, we consider the recently introduced concept of \emph{function-correcting codes (FCCs) with data protection}, which provide a certain level of error protection for the data and a higher level of protection for a desired function on the data. These codes are denoted by $(f\!:\!d_d,d_f)$-FCC, where $d_d$ is the minimum distance of the code and $d_f$ denotes the minimum distance between those codewords that correspond to different function values of a function $f:\mathbb{F}_q^k \to \mathrm{Im}(f)$, with $d_f \geq d_d$. We use a distance graph on a code based on the pairwise distances of its codewords, and show conditions under which a code cannot work as a \emph{strict} $(f\!:\!d_d,d_f)$-FCC, that is, code for which $d_f > d_d$. We then consider some well-known classes of codes, such as perfect codes and maximum distance separable (MDS) codes, and show that they cannot be used as \emph{strict} $(f\!:\!d_d,d_f)$-FCCs.

Function-correcting codes (FCCs) are designed to provide error protection for the value of a function computed on the data. Existing work typically focuses solely on protecting the function value and not the underlying data. In this work, we propose a general framework that offers protection for both the data and the function values. Since protecting the data inherently contributes to protecting the function value, we focus on scenarios where the function value requires stronger protection than the data itself. We first introduce a more general approach and a framework for function-correcting codes that incorporates data protection along with protection of function values. A two-step construction procedure for such codes is proposed, and bounds on the optimal redundancy of general FCCs with data protection are reported. Using these results, we exhibit examples that show that data protection can be added to existing FCCs without increasing redundancy. Using our two-step construction procedure, we present explicit constructions of FCCs with data protection for specific families of functions, such as locally bounded functions and the Hamming weight function. We associate a graph called minimum-distance graph to a code and use it to show that perfect codes and maximum distance separable (MDS) codes cannot provide additional protection to function values over and above the amount of protection for data for any function. Then we focus on linear FCCs and provide some results for linear functions, leveraging their inherent structural properties. To the best of our knowledge, this is the first instance of FCCs with a linear structure. Finally, we generalize the Plotkin and Hamming bounds well known in classical error-correcting coding theory to FCCs with data protection.

We introduce function-correcting partition codes (FCPCs), which are a natural generalization of function-correcting codes (FCCs). An FCPC is defined directly on a partition of the message space, rather than on a specific target function. We show that any FCC for a function $f$ is exactly an FCPC with respect to the domain partition induced by $f$, which makes these codes a natural generalization of FCCs. We use the join of domain partitions to construct a single code that protects multiple functions simultaneously. We define the notions of partition gains to measure the bandwidth saved by using a single FCPC for multiple functions instead of constructing separate FCCs for each function. We derive general lower and upper bounds on the redundancy of such FCPCs and illustrate the achievable gains through examples. We specialize this concept of using single code for protecting multiple functions to linear functions via coset partition of the intersection of their kernels. We also present explicit FCPC constructions for locally bounded partitions and grouped weight partitions. Then, we associate a partition graph with any given partition of $\mathbb{F}_q^k$, and show that the existence of a suitable clique in this graph yields a set of representative information vectors that achieves the optimal redundancy. Using the existence of a full-size clique in the weight partition and support partition, we obtain lower and upper bounds on the optimal redundancy of FCPCs for these partitions. We introduce the notion of a block-preserving contraction for a partition, which helps reduce the problem size of finding optimal redundancy for an FCPC. We further show that such a contraction exists for all weight-based partitions. Finally, we observe that FCPCs naturally provide a form of partial privacy in the sense that only the domain partition of the function needs to be revealed to the transmitter.

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.

The model considered in this work consists ofHservers where the file library is Maximum Distance Separable (MDS) coded and stored. Each server is connected toKusers through a dedicated shared link, and each user has access to a unique set ofrout ofCcaches. For every set ofrcaches, there is a user. Each user aims to retrieve an arbitrary linear combination of files. All the users should be able to retrieve their demands using the signals from anyLout ofHservers. In addition, the following conditions must be satisfied: (a) content-security from an eavesdropper, b) demand-privacy against non-colluding users and any colluding set of servers. We propose two schemes, one of which satisfies both the above conditions and the other satisfies only the security condition. Over a certain range in the low memory region, our schemes are within a constant multiplicative factor from the optimal. As special cases, our schemes recover some of the previous works in the literature. One of our schemes is extended to a more general setup where different users are connected to different numbers of caches, and multiple users are connected to the same subset of caches.

Device-to-device (D2D) communication is one of the most promising techniques for next-generation wireless Internet of Things networks. This paper considers coded caching in a wireless multiaccess D2D network, where users communicate with each other and can access multiple cache nodes. Access topologies derived from two combinatorial designs known as thet-design andt-group divisible design (t-GDD), referred to as thet-design andt-GDD topologies, respectively, have been studied recently for the multiaccess coded caching (MACC) network. These access topologies, which subsume the other known topologies except the cyclic wrap-around topology, are extended to a multiaccess D2D coded caching (MADCC) network. Novel MADCC schemes are proposed, and schemes are also derived from existing MACC schemes witht-design andt-GDD topologies. To compare different MADCC schemes, the metrics of load per user and subpacketization level are used while keeping the number of caches, cache size, and access degree the same. A comparison of the proposed schemes with those derived from existing MACC schemes, as well as with the existing MADCC scheme under a cyclic wrap-around topology, shows that the proposed schemes have an advantage in either load per user or subpacketization level or both. Additionally, several low subpacketization level coded caching schemes are obtained for the original D2D network with dedicated caches.

Function-Correcting Codes (FCCs) are a novel class of codes designed to protect function evaluations of messages against errors while minimizing redundancy. A theoretical framework for systematic FCCs to channels matched to the Lee metric has been studied recently, which introduced function-correcting Lee distance codes (FCLCs) and also derived upper and lower bounds on their optimal redundancy. In this paper, we first propose a Plotkin-like bound for irregular Lee-distance codes. We then construct explicit FCLCs for specific classes of functions, including the Lee weight, Lee weight distribution, modular sum and locally bounded function. For these functions, lower bounds on redundancy are obtained, and our constructions are shown to be optimal in certain cases. Finally, a comparative analysis with classical Lee error-correcting codes and codes correcting errors in function values demonstrates that FCLCs can significantly reduce redundancy while preserving function correctness.

Function-correcting codes (FCCs) are designed to provide error protection for the value of a function computed on the data. Existing work typically focuses solely on protecting the function value and not the underlying data. In this work, we propose a general framework that offers protection for both the data and the function values. Since protecting the data inherently contributes to protecting the function value, we focus on scenarios where the function value requires stronger protection than the data itself. A two-step construction procedure for such codes is proposed, and bounds on the optimal redundancy of general FCCs with data protection are reported. Using these results, we exhibit examples that show that data protection can be added to existing FCCs without increasing redundancy. Using our two-step construction procedure, we present explicit constructions of FCCs with data protection for specific families of functions, such as locally bounded functions and the Hamming weight function. We associate a graph calledminimum-distance graphto a code and use it to show that perfect codes and maximum distance separable (MDS) codes cannot provide additional protection to function values over and above the amount of protection for data for any function. Then we focus on linear FCCs and provide some results for linear functions, leveraging their inherent structural properties. While FCCs for linear functions have been considered earlier in the literature, to the best of our knowledge, the linearity of the FCC itself has not been studied before. Finally, we generalize the Plotkin and Hamming bounds well known in classical error-correcting coding theory to FCCs with data protection.

Federated Learning is a promising option for data privacy and security in ITS, because it allows edge devices, Road Side Units (RSUs), and Central Server (CS) to jointly train the machine learning model. Since RSU collects data from the vehicles passing through its range, the local data of each RSU will have a non-IID distribution, which adversely affects the convergence speed and accuracy of FL training. Generating synthetic data locally at individual nodes, followed by data shuffling among the nodes, is a promising approach to address the Non-IID data problem. In this work, we propose pliable index coding (PIC) solutions for efficient data shuffling among the nodes in an FL system. In PIC($S$) problems, a client is satisfied if it can retrieve any $S$ new messages not originally present in its side-information. We particularly consider decentralized pliable index coding problems (DPIC) where the clients communicate among themselves without a central server to model the data shuffling in FL. A class of DPIC, known as Consecutive Decentralized Pliable Index Coding (CDPIC($S$,$K$)), where each client has $K$ consecutive messages as side-information, is considered. For CDPIC($S$,$K$) problems, pliable index code designs are provided for any value of $K$ and $S$, and optimality proofs for some of the cases are established. Further, these CDPIC solutions are applied for data shuffling in FL, to transform the local data distribution towards IID progressively with each transmission, thereby enhancing the performance of FL. The improvement in the accuracy and convergence of the most popular FL technique, FedAvg, and a promising federated submodel technique, CELL (Communication Efficient Lottery Learning), are analysed by providing different degrees of data shuffling using the proposed CDPIC schemes.

In this paper, we propose a multi-access coded caching system under decentralized setting tailored for Content Delivery Networks (CDNs). In this system, a central server hosts N files, each of size F bits, and serves K≤N users through a shared link. The network is equipped with c caches, each with a capacity of MF bits, distributed across the network, where each of the K users is connected to a random set of r≤c caches. Initially, we consider a model where each cache subset is accessed by an equal number of users. We introduce a novel content delivery algorithm for the central server, which allows us to derive a closed-form expression for the per user transmission rate. Using techniques from index coding, we prove the optimality of the proposed delivery scheme. Additionally, we extend the model to propose a more general and novel framework by allowing each subset of caches to serve an arbitrary number of users, thereby greatly enhancing the system’s flexibility and applicability. We also propose a new delivery algorithm tailored to this generalized setting and demonstrate its optimality under specific user-to-cache association scenarios. Numerical results demonstrate that, in a specific scenario where the user-to-cache associations do not satisfy the optimality conditions, the proposed generalized scheme shows improvement over the order-optimal state-of-the-art decentralized multi-access coded caching scheme for small cache sizes. Specifically, when approximately 25% of the content is stored at every cache, the proposed scheme achieves up to a 20% reduction in the per user transmission rate. Considering that both schemes serve an equal number of users, the observed improvements indicate a potential reduction in server bandwidth requirements, lower latency, and enhanced energy efficiency during content delivery.

We consider a two-layer hierarchical coded caching network where a server with a library of$N$files is connected to$K_{1}$mirrors, each having a cache memory of size$M_{1}$files. Each mirror is further connected to$K_{2}$users, each equipped with a dedicated cache of size$M_{2}$files. In this paper, we propose two distinct coded caching schemes based on coded placement, corresponding to two distinct memory pairs, ($M_{1}, M_{2}$), which operate effectively in the high memory regime, i.e., when both$M_{1}$and$M_{2}$are large. We show that the proposed schemes outperform existing schemes at these memory points for smaller values of$K_{2}$. In setups where mirrors are positioned near each other, avoiding signal interference is crucial. This can be ensured by having all mirrors transmit using orthogonal carrier frequencies. To compare our schemes with existing ones, we used the composite rate metric, which accurately represents the total bandwidth utilized in such setups. The composite rate is given by$\bar{R}=R_{1}+K_{1} R_{2}$, where$R_{1}$is the rate from the server to the mirrors, and$R_{2}$is the rate from the mirrors to the users, with respect to$M_{1}$and$M_{2}$.

This paper studies wireless device-to-device (D2D) coded caching in a multiaccess network, where users communicate with each other and access multiple cache nodes. Access topologies derived from two combinatorial designs, the$t$-design and$t$-group divisible design ($t$-GDD), previously studied for multiaccess coded caching (MACC) network by Cheng et al. in [14], are extended to multiaccess D2D coded caching (MADCC) network. Novel MADCC schemes are proposed and also derived schemes from existing MACC schemes in [14]. To compare different MADCC schemes, the metrics of load per user and subpacketization level are used while keeping the number of caches and cache memory size fixed. Comparison of the proposed schemes with the schemes derived from existing MACC schemes in [14] and the existing MADCC scheme with cyclic wrap-around topology shows that the proposed schemes have an advantage in either load per user or subpacketization level or both.

In this work, we consider the multi-access combinatorial topology with C caches where each user accesses a unique set of r caches. For this setup, we consider secrecy, where each user should not know anything about the files it did not request, and demand privacy, where each user’s demand must be kept private from other non-colluding users. We propose a scheme satisfying both conditions and derive a lower bound based on cut-set arguments. Also, we prove that our scheme is optimal when r ≥ C − 1, and it is order-optimal when the cache memory size M is greater than or equal to a certain threshold for r < C − 1. When r = 1, in most of the memory region, our scheme achieves the same rate as the one given by the secretive scheme for the dedicated cache setup by Ravindrakumar et al. (’Private Coded Caching,’ in IEEE Transactions on Information Forensics and Security, 2018), while satisfying both secrecy and demand privacy conditions.

In this paper, we introduce a class of functions that assume only a limited number λ of values within a given Hamming ρ-ball and call them locally (ρ,λ)-bounded functions. We develop function-correcting codes (FCCs) for a subclass of these functions and propose an upper bound on the redundancy of FCCs. The bound is based on the minimum length of an error-correcting code with a given number of codewords and a minimum distance. Furthermore, we provide a sufficient optimality condition for FCCs when λ = 4. We also demonstrate that any function can be represented as a locally (ρ,λ)-bounded function, illustrating this with a representation of Hamming weight distribution functions. Furthermore, we present another construction of function-correcting codes for Hamming weight distribution functions.

Function-Correcting Codes (FCCs) is a novel paradigm in Error Control Coding introduced by Lenz et al. 2023 for the binary substitution channel [1]. FCCs aim to protect the function evaluation of data against errors instead of the data itself, thereby relaxing the redundancy requirements of the code. Later R. Premlal et al. [4] gave new bounds on the optimal redundancy of FCCs and also extensively studied FCCs for linear functions. The notion of FCCs has also been extended to different channels such as symbol-pair read channel over the binary field by Xia et al. [2] and b-symbol read channel over finite fields by A.Singh et al. [3]. In this work, we study FCCs for linear functions for the b-symbol read channel. We provide the Plotkin-like bound on FCCs for b-symbol read channel which reduces to a Plotkin-like bound for FCCs for the symbol-pair read channel when b=2. FCCs reduce to classical Error Correcting Codes (ECCs) when the function is bijective. Analogous to this our bound reduces to the Plotkin-bound for classical ECCs for both the b-symbol and symbol-pair read channels [5], [6] when we consider linear bijective functions.

This paper studies a two-layer hierarchical network in which some users are offline during the content delivery phase. A two-layer hierarchical network consists of a single server connected to multiple cache-aided mirror sites, and each mirror site is connected to a distinct set of cache-aided users. A scheme for such a hierarchical system with offline users has been proposed recently, but considered a special case where all mirror caches have zero memory, which is a significant limitation. We propose an array known as a hierarchical hotplug placement delivery array (HHPDA), which describes the placement and delivery phases of a coded caching scheme for a general two-layer hierarchical network with offline users. Further, we construct a class of HHPDAs using combinatorial t-designs.

In Pliable Private Information Retrieval (PPIR) with a single server, messages are partitioned into T non-overlapping classes. The user wants to retrieve a message from its desired class without revealing the identity of the desired class to the server. In [S. A. Obead, H. Y. Lin and E. Rosnes, “Single-Server Pliable Private Information Retrieval With Side Information,” arXiv:2305.06857 [cs.IT]], authors consider the problem of PPIR with Side Information (PPIR-SI), where the user now has side information. The user wants to retrieve any new message (not included in the side information) from its desired class without revealing the identity of the desired class. Identity of each message can be represented as a class-subclass index pair, where subclass index represents the membership of a message within a class. If the user does not know the subclass indices of its side information from a class, that class is termed as unidentifiable. Conversely, if the user knows the subclass indices of its side information from a class, that class is termed as identifiable. A scheme for the PPIR-SI is given by Obead et al. for the case when all classes are unidentifiable, i.e., the user is unaware of the subclass indices of all its side information, and this case is referred to as PPIR with Unidentifiable SI (PPIR-USI). In this paper, we study the problem of PPIR for the single server case when the side information is partially identifiable, and we term this case as PPIR with Identifiable Side Information (PPIR-ISI). There are η number of identifiable classes, where 1 ≤η≤r. We give a scheme for PPIR-ISI, and we prove that having some identifiable side information is advantageous by comparing the rate of the proposed scheme to the rate of the PPIR-USI scheme given by Obead et al. for some cases.

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.

Coded caching in a wireless device-to-device (D2D) network was first studied by Ji et al. in [4] (referred to as the JCM scheme). Wang et al. in [7] proposed the D2D placement delivery array (DPDA) that characterizes coded caching in a D2D network and derived a lower bound on the transmission load of a DPDA. Only the JCM scheme achieves this bound but requires a subpacketization level that grows exponentially with the number of users. This paper proposes two new classes of DPDA constructions that give low subpacketization level D2D schemes using cross resolvable designs. The first class of constructed DPDA achieves the known lower bound on the transmission load of DPDA while requiring a subpacketization level lesser than that of the JCM scheme. A new lower bound on the transmission load of a DPDA is proposed and shows that the second class of constructed DPDA achieves this lower bound.

A novel distributed computing model calledMulti-access Distributed Computing (MADC)was recently introduced in the literature. The MADC models with Combinatorial Topology (CT) were studied, where there are A mapper nodes andK= (Λ α) reducer nodes with each reducer node connected to distinct α mapper nodes. In this paper, we represent MADC models via 2-layered bipartite graphs called Map-Reduce Graphs (MRGs) and a set of arrays called Map-Reduce Arrays (MRAs). The connection between MRAs and MRGs is established, thereby exploring new topologies and providing coded shuffling schemes for the MADC models with MRGs using the structure of MRAs. A novelNearest Neighbor Connect-MRG (NNC-MRG)is explored and a coding scheme is provided for MADC models with NNC-MRG. Moreover, CT is generalized to Generalized Combinatorial-MRG (GC-MRG). A set ofg–regular MRAs is provided which corresponds to the existing scheme for MADC models with CT and extended those to generate another set of MRAs to represent MADC models with GC-MRG. One of the major limitations of the existing scheme for CT is that it requires an exponentially large number of reducer nodes and input files for large Λ. This can be overcome by representing CT by MRAs, where coding schemes can be derived even if some of the reducer nodes are not present. Another way of tackling this is by using a different MRG, specifically NNC-MRG, where the number of reducer nodes and files required are significantly smaller compared to CT.

Multi-layer cache structures are commonly used in various IoT environments due to their distributed architecture. This paper considers coded caching for a two-layer hierarchical network consisting of a single server connected to multiple cache-aided mirror sites, and each mirror site connected to a distinct set of cache-aided users. The placement delivery array (PDA) and the hierarchical placement delivery array (HPDA) were proposed as tools for designing coded caching schemes with reduced subpacketization levels for single-layer and two-layer networks, respectively. This paper proposes construction of a novel class of HPDAs by first constructing a class of PDAs using combinatorial t-designs. The proposed class of HPDAs yields hierarchical coded caching schemes at several memory points for a given number of mirrors and users. Additionally, we introduce the concept of hierarchical memory sharing to achieve the lower envelope of the convex hull of these points. It is shown that the proposed hierarchical schemes have significantly lower subpacketization levels compared to many known schemes. In cases where the system parameters and subpacketization levels of the proposed and existing schemes match, the proposed scheme achieves a better coding delay. Furthermore, the class of PDAs constructed either subsumes several known PDA constructions or achieves a better transmission load for the same system parameters.

This work explores a multiple transmit antenna setting in a multi-access coded caching (MACC) network where each user accesses more than one cache. A MACC network has K users and K caches, and each user has access to$r \lt K$consecutive caches in a cyclic wrap-around manner. There are L antennas at the server, and each cache has a normalized size$M/N \leq 1$. The cyclic wrap-around MACC network with a single antenna at the server has been well-investigated, and several coded caching schemes and improved lower bounds on the performance are derived for the same. However, this MACC network has not yet been studied under multi-antenna settings in the coded caching literature. We study the multi-antenna MACC problem and propose a solution for the same by constructing a pair of arrays called caching and delivery arrays. We present four constructions of caching and delivery arrays for different scenarios and obtain corresponding multi-antenna MACC schemes. Three of the above schemes achieve optimal performance under uncoded placement and one-shot delivery. The optimality is shown by matching the performance of the multi-antenna MACC scheme to the optimal performance in a dedicated cache network having K users and normalized cache size$rM/N$. Further, as a special case, one of the proposed schemes subsumes an existing optimal MACC scheme for the single-antenna setting.

Function-correcting codes were introduced in the work "Function-Correcting Codes" (FCC) by Lenz et al. 2023, which provides a graphical representation for the problem of constructing function-correcting codes. We use this function dependent graph to get a lower bound on the redundancy required for function correction codes. Considering the function to be a bijection, leads to a lower bound on the redundancy required for classical systematic error correcting codes (ECCs). We propose a range of parameters for which this bound is tight. For single error correcting codes, we show that this bound is at least as good as a bound proposed by Zinoviev, Litsyn, and Laihonen in 1998. Thus, this framework helps to study classical systematic error correcting codes. Further, we study the structure of this function dependent graph for linear functions, which leads to bounds on the redundancy of linear-function correcting codes. We show that the Plotkin-like bound for function-correcting codes proposed by Lenz et.al 2023 is simplified for linear functions. We identify a class of linear functions for which an upper bound proposed by Lenz et al., is tight and also identify a class of functions for which coset-wise coding is equivalent to a lower dimensional classical error correction problem.

This work introduces a multi-antenna coded caching problem in a two-dimensional multi-access network, where a server with$L$transmit antennas and$N$files communicates to$K_{1}K_{2}$users, each with a single receive antenna, through a wireless broadcast link. The network consists of$K_{1}K_{2}$cache nodes and$K_{1}K_{2}$users. The cache nodes, each with capacity$M$, are placed on a rectangular grid with$K_{1}$rows and$K_{2}$columns, and the users are placed regularly on the square grid such that a user can access$r^{2}$neighbouring caches in a cyclic wrap-around fashion. For a given cache memory$M$, the goal of the coded caching problem is to serve the user demands with a minimum delivery time. We propose a solution for the aforementioned coded caching problem by designing two arrays: a caching array and a delivery array. Further, we present two classes of caching and delivery arrays and obtain corresponding multi-access coded caching schemes. The first scheme achieves a normalized delivery time (NDT)$\frac{K_{1}K_{3}(1-r^{2}\frac{M}{N})}{L+K_{1}K_{2}\frac{M}{N}}$. The second scheme achieves an NDT$\frac{K_{1}K_{3}(1-r^{2}\frac{M}{N})}{L+K_{1}K_{2}r^{2}\frac{M}{N}}$when$M/N=1/K_{1}K_{2}$and$L=K_{1}K_{2}-r^{2}$, which is optimal under uncoded placement and one-shot delivery.

We consider a coded caching network consisting of a server with a library of$N$files connected to$K$users, where each user is equipped with a dedicated cache of size$M_{p}$units. In addition to that, the network consists of$\Lambda\leq K$helper caches, each with a size$M_{h}$units. Each helper cache can serve an arbitrary number of users; however, each user can access only a single helper cache. Also, we assume that the server knows the user-to-helper cache association, defined as the sets of users connected to each helper cache, during the cache placement phase. We propose a solution for the aforementioned coded caching problem by introducing a combinatorial structure called a Shared and Private Placement Delivery Array (SP-PDA). These SP-PDAs describe the helper cache placement, private cache placement, and the server transmissions in a single array. Further, we propose a novel construction of SP-PDAs using two Placement Delivery Arrays (PDAs). Interestingly, we observe that the permutations of the columns of the two chosen PDAs result in SP-PDAs with different performances. Moreover, we characterize the conditions for selecting the best column permutations of the chosen PDAs. Furthermore, the coded caching schemes resulting from SP-PDAs subsume two existing coded caching schemes as special cases. Additionally, SP-PDAs enable the construction of coded caching schemes with much smaller subpacketization numbers-subpacketization number is defined as the number of subfiles to which a file is divided-compared to the existing schemes, without paying much in terms of rate (the size of the transmission in the delivery phase).

We consider the two-layered hierarchical coded caching problem introduced in [N. Karamchandani,$\mathbf{U}$. Niesen, M. A. Maddah-Ali, and S. N. Diggavi, “Hierarchical coded caching,” IEEE Trans. Inf. Theory, 2016], in which a server is connected to$K_{1}$mirrors, and each mirror is connected to$K_{2}$users. The mirrors and the users are equipped with the cache of size$M_{1}$and$M_{2}$, respectively. We propose a hierarchical coded caching scheme with coded placements that perform better than the existing schemes. In order to ensure a fair comparison with existing schemes, we introduce the notion of composite rate, defined as$\overline{R}=R_{1}+K_{1}R_{2}$, which consists of the rate from server to mirrors$R_{1}$and the rate from mirror to users$R_{2}$. The composite rate has not been discussed before in literature, and it represents the total consumed bandwidth in the system. Therefore, it is more appropriate to consider the composite rate along with$R_{1}$and$R_{2}$. For the proposed scheme, we show a trade-off between the global memory$\overline{M}=K_{1}M_{1}+K_{1}K_{2}M_{2}$of the system and the composite rate. We compare the proposed scheme with the existing hierarchical coded caching schemes using the proposed parameter “composite rate.”

We consider a hotplug coded caching systems in which some users are offline at the time of delivery. A placement delivery array (PDA) is a well-known tool for constructing a coded caching scheme for dedicated caches. In this paper, we introduce the concept of PDAs for hotplug coded caching schemes and refer to it as hotplug placement delivery array (HpPDA). We give an algorithm to describe the placement and the delivery phase of a hotplug coded caching scheme using HpPDA. We show that an existing hotplug coded caching scheme given in [Y. Ma and D. Tuninetti, “On coded caching systems with offline users,” in 2022 IEEE International Symposium on Information Theory (ISIT), 2022, pp. 1133–1138] corresponds to a class of HpPDAs, and then propose a method to further improve the rate of that scheme.

A novel distributed computing model called Multi-access Distributed Computing (MADC) was recently introduced in [B. Federico and P. Elia, “Multi-Access Distributed Computing,” June 2022, [online] Available: http://www.arXiv:2206.12851]. The MADC models with Combinatorial Topology (CT) were studied, where there are$\Lambda$mapper nodes and$\dot{K}=\binom{\lambda}{\alpha}$reducer nodes with each reducer node connected to distinct$\alpha$mapper nodes. In this paper, we represent MADC models via 2-layered bipartite graphs called Map-Reduce Graphs (MRGs), and a set of arrays called Map-Reduce Arrays (MRAs) inspired from the Placement Delivery Arrays (PDAs) used in the coded caching literature. The connection between MRAs and MRGs is established, thereby providing coded shuffling schemes for the MADC models using the structure of MRAs. Moreover, a set of$g$-regular MRAs is provided which corresponds to the existing scheme for MADC models with CT. One of the major limitations of the existing scheme for CT is that it requires an exponentially large number of reducer nodes for large$\Lambda$. This can be overcome by representing CT by MRAs, where coding schemes can be derived even if some of the reducer nodes are not present.

Coded caching scheme originally proposed by Maddah-Ali and Niesen (MN) achieves optimal transmission rate$R$under uncoded placement but requires a subpacketization level$F$which increases exponentially with the number of users$K$where the number of files$N\geq K$. Placement delivery array (PDA) was proposed as a tool to design coded caching schemes with reduced subpacketization level by Yan et al. in [4]. This paper proposes two novel classes of PDA constructions from combinatorial t-designs which achieve improved transmission rate for a given low subpacketization level, cache size and number of users compared to existing coded caching schemes from t- designs. A$(K,F, Z,S)$PDA composed of a specific symbol$\star$and$S$nonnegative integers corresponds to a coded caching scheme with subpacketization level F, K users each caching$Z$packets and the demands of all the users are met with a rate$R=\frac{S}{F}$. For a given K, F and Z, a lower bound on$S$such that a (K, F, Z, S) PDA exists is given by Cheng et al. in [16]. The first class of proposed PDA achieves this lower bound on S. The second class of PDA also achieves this lower bound in some cases.

In this work, the problem setup consists of a server with$N$files connected to$K$users through an error-free shared link. Also, it consists of$C$caches of size$M_{M}\mathbf{files}$called multi-access caches and$K$caches of size$M_{P}$files called private caches. Each user is connected to a private cache and to a unique set of$r$multi-access caches. For every set of$r$multi-access caches, there is a user. For this setup a scheme is proposed that satisfies the following simultaneously: a) Linear Function Retrieval (LFR), b) content-security from an eavesdropper, and c) demand-privacy against a colluding set of users. It is shown that the private caches included in this work, enables the proposed scheme to provide privacy against colliding users. Also it is shown that to achieve the same rate both in [17] and in the proposed scheme, the total memory accessed by each user is less in the proposed scheme. Moreover, it turns out that the total cache memory requirement is also less for the system considered in this work compared to that in [17]. When$r=1$, the proposed scheme recovers one of the schemes given by Yan and Tuninetti (“Key Superposition Simultaneously Achieves Security and Privacy in Cache-Aided Linear Function Retrieval,” in Trans. Inf. Forensics and Security, 2021).

In the original coded caching model introduced by Maddah-Ali and Niesen in 2014, the server starts broadcasting only after it receives demands from all the users. So, all the users must be active during the delivery phase. In this work, we consider a coded caching model called hotplug coded caching in which some of the users are offline during the delivery phase. This model was first introduced by Ma and Tuninetti (“On Coded Caching Systems with Offline Users,” 2022 IEEE International Symposium on Information Theory). The concept of Hotplug Placement Delivery Arrays (HpPDAs) for the hotplug coded caching systems was introduced in (“Improved Hotplug Caching Schemes Using PDAs and t-Designs,” arXiv:2311.02856, 2024), in which the authors have constructed HpPDAs from t-designs. This work provides a new hotplug coded caching scheme from the existing HpPDAs. The performance comparison of the proposed scheme with the existing schemes is presented. When applied for HpPDAs from t-designs, our scheme outperforms the baseline scheme by Ma and Tuninetti, and the Improved t-scheme by Rajput and Rajan in some memory segments.

Caching is a method to ease the strain on the network during peak hours. Many caching approaches consider a single-layer system in which the server is connected to the users via an error-free shared link. However, in these systems, all the users involved in the placement phase must be present during the delivery phase. To address this, a hotplug model was presented, in which only some users may actually reveal their demand and be present during the delivery phase. On the other hand, a single-layered caching system was extended to the two-layered coded caching system. In this work, we consider a two-layered hierarchical system in which a server with$N$files is connected to$K_{1}$mirrors and each mirror is connected to$K_{2}$users. Out of all$K_{1}K_{2}$users, only$K^{\prime}$users are online during the delivery phase. All the mirrors and users are equipped with caches. We refer to this system as a hotplug hierarchical caching system. Here, we consider this system with the case when the cache memory of each mirror is zero, and propose a scheme using the concept of hotplug placement delivery arrays (HpPDAs).

We consider the two-layer hierarchical coded caching networks, where users connected to each mirror are connected to multiple caches instead of having a dedicated cache. The problem setting involves a server with$N$files connected to$K_{1}$mirrors, each with a cache size of$M_{1}$files, through an error-free bottleneck link, which are further connected to users each one of them can access$r$out of$C$caches each of size$M_{2}$files, available in the system. Each mirror is connected to$\binom{C}{r}$, users, and no two of these users connect to the same set of$r$caches. The total cache size in the system is$\overline{M}=K_{1}M_{1}+K_{1}CM_{2}$called the global memory. The case$r=1$corresponds to hierarchical two-layer systems with users having dedicated caches. Let$R_{1}$be the rate (in the unit of files) of the transmission from the server to the mirrors and$R_{2}$be the rate of transmission from any mirror to the users connected to it that satisfy the demands of all the users. The total delivery time from the server to a user is indicated by the metric$R_{1}+R_{2}$, which is also known as the coding delay. In this work, we present an achievable scheme with low coding delay for a given global memory size. We compare$R_{1}+R_{2}$vs. global memory$\overline{M}=K_{1}M_{1}+K_{1}CM_{2}$of our scheme with other existing schemes for hierarchical two-layer coded caching networks. As we increase$r$, our scheme has a reduction in$R_{1}+R_{2}$, which provides a dual advantage of serving a larger number of users while having a lower coding delay.

We study the wireless MapReduce distributed computing system in [5], which operates in three phases: Map, Shuffle, and Reduce. The system consists of a set of distributed nodes assigned to compute arbitrary output functions depending on a file library. The computation of the output functions is decomposed into Map and Reduce functions, and the Shuffle phase, which involves the data exchange, links the two. In our model, the Shuffle phase communication happens over a full-duplex wireless interference channel. For this setting, a coded wireless MapReduce distributed computing scheme exists in the literature, achieving optimal performance under one-shot linear schemes. However, the scheme requires the number of input files to be very large, growing exponentially with the number of nodes. We present schemes that require the number of files to be in the order of the number of nodes and achieve the same performance as the existing scheme. The schemes are obtained by designing a structure called wireless MapReduce array that succinctly represents all three phases in a single array. The wireless MapReduce arrays can also be obtained from the extended placement delivery arrays known for multi-antenna coded caching schemes.

A class of codes designed to protect function evaluations of a message from errors was introduced in “Function-Correcting Codes” by Lenz et al. 2023. They provide a graphical representation for the problem of constructing functioncorrecting codes. We use this graph to get a lower bound on the redundancy required for function correction and classical error correction. For linear functions, we show that the adjacency matrix of this graph is diagonalised by tensor powers of Discrete Fourier Transform (DFT) matrices, which leads to a lower bound on redundancy. Also, we propose a version of the sphere packing bound for linear-function correcting codes. Further more, we identify a class of linear functions for which an upper bound proposed by Lenz et al., is tight.

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.

This work explores a multiple transmit antenna setting in a multi-access coded caching (MACC) network where each user accesses more than one cache. A MACC network has$K$users and$K$caches, and each user has access to$r < K$consecutive caches in a cyclic wrap-around manner. There are$L$antennas at the server, and each cache has a normalized size of$M/N\leq 1$. The cyclic wrap-around MACC network with a single antenna at the server has been a well-investigated topic, and several coded caching schemes and improved lower bounds on the performance are known for the same. However, this MACC network has not yet been studied under multi-antenna settings in the coded caching literature. We study the multi-antenna MACC problem and propose a solution for the same by constructing a pair of arrays called caching and delivery arrays. We present three constructions of caching and delivery arrays for different scenarios and obtain corresponding multi-antenna MACC schemes for the same. Two schemes resulting from the above constructions achieve optimal performance under uncoded placement and one-shot delivery. The optimality is shown by matching the performance of the multi-antenna MACC scheme to that of an optimal multi-antenna scheme for a dedicated cache network having an identical number of users, and each user having a normalized cache size of$rM/N$. Further, as a special case, one of the proposed schemes subsumes an existing optimal MACC scheme for the single-antenna setting.

This work studies the coded caching problem in a setting where users can access a private cache of their own along with a shared cache. The setting consists of a server connected to a set of users, assisted by a smaller number of helper nodes that are equipped with their own storage. In addition to the helper caches, each user possesses a dedicated cache which is also used to prefetch file contents. Each helper cache can serve an arbitrary number of users, but each user gets served by only one helper cache. We consider two scenarios: (a) the server has no prior information about the user-to-helper cache association, and (b) the server knows the user-to-helper cache association at the placement phase itself. We design centralized coded caching schemes under uncoded placement for the above two settings. For case (b), we propose four schemes, and establish the optimality of certain schemes in specific memory regimes by deriving matching lower bounds. The fourth scheme, called as the composite scheme, appropriately partitions the file library and the cache memories between two other schemes in case (b) to minimize the rate by leveraging the advantages of both.

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.

We consider the problem of cache-aided multi-user private information retrieval (MuPIR). This problem consists of$N$independent files that are replicated across$S \geq 2$non-colluding servers. There are$K$cache-equipped users having caches of size equivalent to$M$files. Every user aims to retrieve a file from the servers, but servers should not obtain any information about users’ demands. The user caches are filled with some arbitrary function of the files before the users decide their demands, known as the placement phase. After deciding their demands, users cooperatively send queries to the servers to retrieve their desired files privately. Upon receiving the queries, servers broadcast coded transmissions based on these queries and the files, known as the delivery phase. Conveying queries to the servers incurs an upload cost for the users, and downloading the answers broadcasted by the servers incurs a download cost. Each file has to be split into$F$packets to implement cache-aided MuPIR schemes. In this paper, we propose MuPIR schemes that utilize placement delivery arrays (PDAs) to characterize placement and delivery. Proposed MuPIR schemes significantly reduce subpacketization levels while slightly increasing the download cost. The proposed scheme also substantially reduces the upload cost for the users. We show that our scheme is order optimal in terms of download cost for PDAs based on Ali-Niesen scheme for centralised coded caching. We recover the optimal single-user PIR scheme presented by Tian et al. in [“Capacity-Achieving Private Information Retrieval Codes With Optimal Message Size and Upload Cost,” IEEE Trans. Inform. Theory, 2019] as a special case. Our scheme also achieves optimal rate for single-user cache-aided PIR setup reported in [R. Tandon, “The capacity of cache aided private information retrieval,” Annual Allerton Conference on Communication, Control and Computing, 2017.]

In a Multi-user Private Information Retrieval (MuPIR) problem, there areNfiles replicated acrossSnon-colluding servers andKusers, each wanting to retrieve a file from the servers without letting the servers getting any information about the demanded files. In a dedicated-cache-aided MuPIR problem each user is equipped with a cache that can storeMfiles. In this paper, we consider a generalized version, called multi-access cache-aided MuPIR problem, where there areKusers andC≤Kcaches each capable of storingMfiles and each user can access several cache nodes and every cache node can be accessed by several users. The cache nodes are filled with the content of the files before users decide their demands. Then each user chooses a file index, and users cooperatively send queries to the servers to retrieve their desired files privately. The aim is to reduce the size of broadcast done by the servers as a response to these queries. We propose a scheme that utilizes multi-access caches in generalised combinatorial topology, introduced by Brunero and Elia in [13] and show that our scheme is order-optimal within a multiplicative factor of 2, assuming uncoded cache placement. Also, we compare the per-user rate of our setup with dedicated cache setup of [10] in various settings.

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.

This work considers the combinatorial multi-access coded caching problem introduced in the recent work by Muralidhar et al. (2021). The problem setting consists of a central server having a library of$N$files and$C$caches each with capacity$M$. Each user in the system can access a unique set of$r < C$caches, and there exist users corresponding to every distinct set of$r$caches. Therefore, the number of users in the system is$\binom {C}{r}$. For the aforementioned combinatorial multi-access setting, we propose a coded caching scheme with an MDS code-based coded placement. This novel placement technique helps to achieve a better rate in the delivery phase compared to the optimal scheme under uncoded placement when$M> N/C$. For a lower memory regime, we present another scheme with coded placement, which outperforms the optimal scheme under uncoded placement if the number of files is no more than the number of users. Further, we derive an information-theoretic lower bound on the optimal rate-memory trade-off of the combinatorial multi-access coded caching scheme. In addition, using the derived lower bound, we show that the first scheme is optimal in the higher memory regime, and the second scheme is optimal if$N\leq \binom {C}{r}$. Finally, we show that the performance of the first scheme is within a constant factor of the optimal performance, when$r=2$.

We study the combinatorial multi-access coded caching problem, introduced by Muralidhar et al. with a single antenna at the server [P. N. Muralidhar, D. Katyal, and B. S. Rajan, "Maddah-Ali-Niesen scheme for multi-access coded caching," in IEEE ITW, 2021], under the setting of multiple transmit antennas. The problem setting consists of a server with L transmit antennas connected to a set of K users that are assisted with C ≤ K helper caches. Each user accesses a unique set of r caches, and there exists a user corresponding to every distinct set of r caches. Thus,$K = \binom {C} { r} $. For this network, the fundamental limits under uncoded placement are known for the single-antenna case [F. Brunero and P. Elia, "Fundamental limits of combinatorial multi-access caching," IEEE Trans. Inf. Theory, 2023]. Notable performance gains were achieved using multiple antennas at the server in other network models [1], [2]. The multi-antenna scenario has not been explored in any multi-access networks in the context of coded caching. In this work, we propose a multi-antenna coded caching scheme for the combinatorial multi-access setting where the number of transmit antennas is one more than the number of caches accessible to each user. When the normalized cache size equals 1/C and r = C−2, our scheme achieves the same performance obtained in a dedicated cache network having $K = \binom {C} { r} $ users, each having a normalized cache size r/C, and L = C−1 antennas. When r = 1, the proposed scheme recovers the multi-antenna coded caching scheme for the dedicated cache networks in [S. P. Shariatpanahi, G. Caire, and B. H. Khalaj, "Physical-layer schemes for wireless coded caching," IEEE Trans. Inf. Theory, 2019].

In this paper, we study shared cache coded caching (SC-CC): a set of caches serves a larger set of users; each user access one cache, and a cache may serve many users. For this problem, under uncoded placement, Parrinello, Ünsal, and Elia showed an optimal SC-CC scheme, in which the subpacketization level depends upon the number of caches. We show an SC-CC scheme where the subpacketization level does not directly depend upon the number of users or caches; any number of caches and users can be accommodated for a fixed subpacketization level. We show that given an upper limit on the allowable subpacketization level, our SC-CC scheme may achieve a lesser rate than other relevant SC-CC schemes. Our scheme is constructed using matrices and designs.

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.

This work considers the combinatorial multi-access coded caching problem introduced in the recent work by Muralidhar et al. [P. N. Muralidhar, D. Katyal, and B. S. Rajan, "MaddahAli-Niesen scheme for multi-access coded caching," in IEEE Inf. Theory Workshop (ITW), 2021] The problem setting consists of a central server having a library of N files and C caches each of capacity M. Each user in the system can access a unique set of rN/C. For a lower memory regime, we present another scheme with coded placement, which outperforms the optimal scheme under uncoded placement if the number of files is no more than the number of users. Further, we derive an information-theoretic lower bound on the optimal rate-memory trade-off of the combinatorial multi-access coded caching scheme. Finally, using the derived lower bound, we show that the first scheme is optimal in the higher memory regime, and the second scheme is optimal if $N \leq \binom C r $.

We consider the coded caching problem where users are simultaneously endowed with a private and shared cache. The problem setting consists of a server having a library of files connected to a set of users via a smaller number of helper nodes having its own storage facility. Each user possesses a dedicated cache which is also used to prefetch file contents. Each helper cache serves an arbitrary number of users. We assume that the server knows the set of users served by each helper cache at the content placement itself. For this setting, we design two centralized coded caching schemes based on uncoded placement. The proposed schemes are shown to be optimal in specific memory regimes.

In this paper, we propose a scheme for the problem of cache-aided multi-user private information retrieval with small caches. All users want to retrieve a file without revealing their demands to the databases. During off-peak hours, all the users will fill their caches, and when required, users will demand their desired files by cooperatively generating query sets for each database. After receiving the transmissions from databases, all the users should get their desired files using transmitted data and their cache contents. This problem has been studied in [X. Zhang, K. Wan, H. Sun, M. Ji and G. Caire, "Fundamental limits of cache-aided multiuser private information retrieval", IEEE Trans. Commun., 2021], in which authors proposed a product design scheme. In this paper, we propose a scheme that gives a better rate for a small value of cache size than the product design scheme. We consider a slightly different approach for the placement phase. Instead of a database filling the caches of all users directly, a database will broadcast cache content for all users on a shared link, and then the users will decide together which part of the broadcasted content will be stored in the cache of each user. This variation facilitates maintaining the privacy constraint at a reduced rate.

We consider the problem of cache-aided multi-user private information retrieval (MuPIR). In this problem, each of K cache-equipped users wants to privately retrieve a file out of N files replicated across B non-colluding servers. The user caches are filled with some arbitrary function of the files before the users decide their demands, known as the placement phase. Then in the delivery phase, users decide their demands and send queries to the servers to retrieve their desired files. This paper proposes MuPIR schemes that utilize placement delivery arrays (PDAs) to characterize placement and delivery. Proposed MuPIR schemes significantly reduce subpacketization levels while slightly increasing the download cost for the users. The proposed scheme also substantially reduces the upload cost for the users. For PDAs based on Ali-Niesen scheme for centralized coded caching, we show that our scheme is order optimal in terms of download cost. We recover the optimal single-user PIR scheme presented by Tian et al. in "Capacity-Achieving Private Information Retrieval Codes With Optimal Message Size and Upload Cost" as a special case. Our scheme also achieves optimal rate for single-user cache-aided PIR setup as described by R. Tondon in "The capacity of cache aided private information retrieval".

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.

Noisy index coding problem over single-input single-output (SISO) additive white Gaussian noise (AWGN) broadcast channel has been studied in [6]. Further the performance of high priority receivers has been improved by using rotated PSK constellation in [7] for AWGN broadcast channel. In this work, we consider noisy index coding problem in which the source transmits symbols over a SISO Rayleigh fading broadcast channel. We show that even for transmission over Rayleigh fading channel minimum inter-set distance, as seen by the receiver plays a crucial role in its ML decoding performance unlike classical fading cases. For improving the performance of high priority receivers for a chosen index code of length N we are transmitting N bits over Rayleigh fading channel using a rotated M-PSK (M = 2N) constellation where half of the signal points have been rotated in such a way to maximize the minimum inter-set distance. Additionally, we account for the multiplicity of signal pairs along with inter-set distance as a factor to achieve better ML decoding performance for some index coding problems with rotated constellation for prioritized receivers over fading channel.

Multiple input multiple output (MIMO) scheme which employs Alamouti code with index coded PSK modulation over Rayleigh fading channel has been studied. In this work, for the noisy index coding problem we generalize the MIMO scheme for any space time block codes (STBCs) obtained from orthogonal designs in which the central server transmits symbols over Nt×NrMIMO Rician fading channel. We show that, for a chosen index code and 2N-PSK signal set at very high SNR, error performance of a receiver is decided by minimum inter-set distance seen by the receiver and for achieving its best ML decoding performance, we must choose the mappings that maximizes minimum inter-set distance. Further for improving the performance of high priority receivers for a chosen index code of length N we are transmitting N bits using a rotated M-PSK (M =2N) constellation.

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 work addresses the multi-antenna coded caching problem where a server with$L$transmit antennas communicates to$K$users through a wireless broadcast link. In the problem setting, the server has a library of$N$files, and each user is equipped with a dedicated cache of capacity$M$. A novel solution for the multi-antenna coded caching problem is obtained by designing a combinatorial structure called an extended placement delivery array (EPDA). It is shown that the placement delivery arrays known for the centralized coded caching scheme are a special class of EPDAs with$L=1$. Furthermore, three constructions of EPDAs are proposed for the settings: a)$K = t+L$, b)$K = nt+ (n-1)L;L\geq t, n\geq 2$, and c)$K,L,t$such that$t + L\leq K$, where$t = KM/N$is an integer. The multi-antenna schemes resulting from the first two constructions achieve the optimal degrees of freedom (DoF)$t+L$with a subpacketization number -the number of subfiles into which a file is divided-$K/\text {gcd}(K,t,L)$, which is lower than the subpacketization number of the existing schemes. The scheme obtained from the third construction also achieves the optimal DoF with a subpacketization number$\binom {K/{\gamma }}{(t+L)/{\gamma }}\left ({{t+L}}\right)/{\gamma }$, where$\gamma =\text {gcd}(K,t,L)$.

We study the problem of multi-access coded caching (MACC): a central server has N files, K (K ≤ N) caches each of which stores M out of the N files, K users each of which demands one out of the N files, and each user accesses z caches. The objective is to jointly design the placement, delivery, and user-to-cache association, to optimize the achievable rate. This problem has been extensively studied in the literature under the assumption that a user accesses only one cache. However, when a user accesses one or more caches, this problem has been studied only under the assumption that a user accesses z consecutive caches with a cyclic wrap-around over the boundaries. A natural question is how other user-to-cache associations fare against the cyclic wrap-around user-to-cache association. A bipartite graph can describe a general user-to-cache association. We identify a class of bipartite graphs that, when used as a user-to-cache association, achieves either a lesser rate or a lesser subpacketization than all other existing MACC schemes using a cyclic wrap-around user-to-cache association. The placement and delivery strategy of our MACC scheme is constructed using a combinatorial structure called maximal cross resolvable design.

The multi-antenna coded caching problem, where the server having L transmit antennas communicating to K users through a wireless broadcast link, is addressed. In the problem setting, the server has a library of N files, and each user is equipped with a dedicated cache of capacity M. The idea of extended placement delivery array (EPDA), an array which consists of a special symbol ⋆ and integers in a set {1, 2, …, S}, is proposed to obtain a novel solution for the aforementioned multiantenna coded caching problem. From a (K, L, F, Z, S) EPDA, a multi-antenna coded caching scheme with K users, and the server with L transmit antennas, can be obtained in which the normalized memory $\frac{M}{N} = \frac{Z}{F}$, and the delivery time $T = \frac{S}{F}$. The placement delivery array (for single-antenna coded caching scheme) is a special class of EPDAs with L = 1. For the multiantenna coded caching schemes constructed from EPDAs, it is shown that the maximum possible Degree of Freedom (DoF) that can be achieved is t + L, where $t = \frac{{KM}}{N}$ is an integer. Furthermore, two constructions of EPDAs are proposed: a) K = t + L, and b) K = nt + (n − 1)L, L ≥ t, where n ≥ 2 is an integer. In the resulting multi-antenna schemes from those EPDAs achieve the full DoF, while requiring a subpacketization number $\frac{K}{{\gcd (K,t,L)}}$. This subpacketization number is less than that required by previously known schemes in the literature.

The multi-access variant of the coded caching problem with N files, K users and K caches, where each user has access to L neighbouring caches in a cyclic wrap-around manner, is considered. A cut-set based lower bound on the optimal rate-memory trade-off of the multi-access coded caching (MACC) scheme is derived. Furthermore, an improved lower bound on the optimal rate-memory trade-off of the MACC scheme is derived using non-cut-set arguments. The improved lower bound is tighter than the previously known lower bounds for the same setting.

This paper considers the secretive coded caching problem with shared caches in which no user must have access to the files that it did not demand. In a shared cache network, the users are served by a smaller number of helper caches, and each user is connected to exactly one helper cache. To ensure the secrecy constraint in shared cache networks, each user is required to have an individual cache of at least unit file size. The existing secretive coded caching scheme for shared caches requires a subpacketization level, which is exponential in the number of helper caches. In this work, we propose a procedure to obtain new secretive coded caching schemes for shared caches with reduced subpacketization levels by utilizing the placement delivery array constructions. We also show that the existing secretive coded caching scheme for shared caches can be recovered using our procedure. In addition, a lower bound based on cut-set based arguments is derived for the shared cache networks under secrecy constraint and characterized the performance of the obtained scheme.

In private information delivery (PID) problem, there are K messages stored across N servers, each capable of storing M messages and a user. Servers want to convey one of the K messages to the user without revealing the identity (index) of the message conveyed. The capacity of PID problem is defined as the maximum number of bits of the desired message that can be conveyed privately, per bit of total communication, to the user. For the restricted case of replicated systems, where coded messages or splitting one message into several servers is not allowed, the capacity of PID has been characterized by Hua Sun in "Private Information Delivery, IEEE Transactions on Information Theory, December 2020" in terms of K, N and M. In this paper, we study the problem of PID with coded storage at the servers. For a class of problems called bi-regular PID we characterize the capacity for N = K/M and for N > K/M we provide achievable scheme. In both the cases, the rates achieved are more than the rates achievable with the replicated systems.

A multi-access network consisting of C caches, K users with each user having access to unique set of r caches has been introduced recently. It considers Single File Retrieval (SFR) i.e, each user demands an arbitrary file from the server. It proposes a coded caching scheme which was shown to be optimal under the assumption of uncoded placement by Brunero and Elia ("Fundamental Limits of Combinatorial Multi-Access Caching" in arXiv:2110.07426 ). The above multi-access network is referred to as combinatorial topology which was considered in our work by imposing three additional constraints : a) Linear Function Retrieval (LFR) i.e., each user is interested in retrieving an arbitrary linear combination of the files in the server’s library; b) Security i.e., the content of the library must be kept secure from an eavesdropper who obtains the signal sent by the server; c) Privacy i.e., each user can only get its required file and can not get any information about the demands of other users. An achievable Secure, Private LFR (SP-LFR) scheme from which Private LFR (P-LFR), LFR schemes can be derived was proposed and also an achievable Secure LFR (S-LFR) scheme was proposed. In the higher memory region, rate achieved by SP-LFR scheme and P-LFR scheme will be same. When the access ratio (number of caches each user having access to) is 1, our SP-LFR scheme and P-LFR scheme reduces to MAN-PDA based SP-LFR scheme and MAN-PDA based P-LFR scheme respectively by Yan and Tuninetti ("Key Superposition Simultaneously Achieves Security and Privacy in Cache-Aided Linear Function Retrieval", in Trans. Inf. Forensics and Security, 2021) and our SP-LFR scheme, S-LFR and security key scheme for SFR by Sengupta et al. ("Fundamental limits of caching with secure delivery", in Trans. Inf. Forensics and Security, 2015 ) will have same performance.

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.

This work considers the coded caching problem with shared caches, where users share the caches, and each user gets access only to one cache. The number of users connected to each cache is assumed to be known at the server during the placement phase. We focus on the schemes derived using placement delivery arrays (PDAs). The PDAs were originally designed to address the sub-packetization bottleneck of coded caching in a dedicated cache setup. We observe that in the setup of this paper, permuting the columns of the PDA results in schemes with different performances for the same problem, but the sub-packetization level remains the same. This is contrary to what was observed for dedicated cache networks. We propose a procedure to identify the ordering of columns that gives the best performance possible from the PDA employed in the given problem. Further, the performance gain achieved by reordering the columns of the PDA is illustrated using certain classes of PDAs.

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.

We consider a particular category of the index coding problems in the network to vehicle (N2V) communication scenario where each vehicle possesses some messages as side information and demands all messages which it does not possess. Under this setup, a lower bound on the number of transmissions is determined. This work proposes the design of an optimal index code for a particular case of N2V communication where the side information is consecutive and present a practical VANET scenario, where the proposed index code (IC) could be applied. The proposed IC solution is independent of the field size and can operate in any field. We have applied index-coded modulation (ICM) over the proposed IC for noisy broadcasting on the AWGN broadcast channel for improved bandwidth efficiency. An algorithm is proposed to map the index coded vectors to constellation points in such a way that the benefit in the error performance can be achieved by a maximum number of vehicles. The simulation results show that ICM offers improved error performance compared to Gray coded modulation for many vehicles while not degrading the performance for others.

Vehicular ad hoc network (VANET), is a developing platform with massive data demands for infotainment services in recent years. Index Coded NOMA (IC-NOMA) is a spectral efficient transmission method that can be used in VANETs. IC-NOMA applies the concepts of non-orthogonal multiple access (NOMA) over the index coded data to increase spectrum and power efficiency. In NOMA, far user does not get access to the near user data, while near user can successfully decode far user data. Therefore, the IC-NOMA demands a novel design of index code for improved bandwidth efficiency. This work considers the design of index code for NOMA when the user demands in VANET follows the data distribution of one-sided symmetric neighboring consecutive side information single unicast index coding problem (SNC-SUICP). For this setup, we develop an optimal closed form index coding (IC) solution which can bring in additional bandwidth savings through NOMA. The improved performance of the proposed IC-NOMA transmission scheme when compared with one-sided SNC-SUICP in terms of bandwidth efficiency is demonstrated.

Noisy index coding problem over a single-input single-output additive white Gaussian noise (AWGN) broadcast channel has been studied in [4]–[6]. For a given index coding problem with an order of priority among the receivers and a chosen index code of length N results have been reported only for symmetric PSK modulation. In this work we improve the performance of high priority receivers by transmitting the N bits using a rotated M-PSK $(M=2^{N}$) constellation where half the number of points are rotated by an angle $\theta$, where $0\leq\theta\lt 2\pi/M$. The results in [4]–[6] correspond to the case $\theta=0$. We show that the probability of error performance for the high priority receivers improve as $\theta$ increases and simultaneously that of the low priority receivers deteriorate. As a result the performance of some of the receivers in the middle of the priority order may remain unchanged.

The multi-access variant of the coded caching problem with K users, K caches and N files, where each user has access to L neighbouring caches in a cyclic wrap-around manner, is studied. Coded placement technique is introduced in the multi-access coded caching set-up for the first time. Furthermore, it is shown that the rate of transmission can be significantly lowered using coded placement, especially when the number of files is no more than the number of users. For cache memory $M \leq \frac{{N - (K - L)}}{K}$, a multi-access coded caching scheme with coded placement is introduced. The scheme presented is optimal when N ≤ K. Also, for some specific values of K,L,N and M, achievable schemes and matching converses are presented.

The demand private coded caching problem in a multi-access network with K users and K caches, where each user has access to L neighbouring caches in a cyclic wraparound manner, is studied. The additional constraint imposed is that one user should not get any information regarding the demands of the remaining users. A lifting construction of demand private multi-access coded caching scheme from conventional, non-private multi-access scheme is introduced. The demand-privacy for a user is ensured by placing some additional keys in a set of caches called the private set of that user. For a given K and L, a technique is also devised to find the private sets of the users.

In this paper, we consider the multi-access cache-aided multi-user Private Information Retrieval (MuPIR) problem. In this problem, N files are replicated across S servers. There are K users and C cache nodes, each capable of storing M files. Each user can access L cache nodes, and every cache node can be accessed by several users. Each user wants to retrieve one file from the servers, but users don’t want the servers to know their demands. This problem is an extension of the dedicated cache-aided MuPIR problem, which itself generalizes the single-user PIR setup. In this paper, we propose an order optimal MuPIR scheme that utilizes a multi-access setup of the coded caching problem where every set of L caches is accessed by one user resulting in K=$\begin{pmatrix} c\\ L \end{pmatrix}$. We also propose

The multi-access variant of the coded caching problem with$N$files,$K$users and$K$caches, where each user has access to$L$neighbouring caches in a cyclic wrap-around manner, is considered. A cut-set based lower bound on the optimal rate-memory trade-off of the multi-access coded caching (MACC) scheme is derived. Furthermore, an improved lower bound on the optimal rate-memory trade-off of the MACC scheme is derived using non-cut-set arguments. The improved lower bound is tighter than the previously known lower bounds for the same setting. Further, for cache memory$M\leq {(N-K+L)}/{K}$, an achievable scheme makes use of coded placement is presented. By matching with the improved lower bound, the scheme is shown to be optimal when$N\leq K$. Also, lower bounds on the optimal rate-memory trade-off of the MACC scheme incorporating secure delivery and secrecy conditions are derived.

The coded caching problem with shared caches where the server is equipped with multiple transmit antennas is considered. In a shared cache network, several users share a cache, but each user can access only a single cache. The fundamental limits of coded caching are known for the above setting under centralized uncoded placement. In the centralized case, to achieve the gains offered by coded caching, one requires a sub-packetization level which increases exponentially with the number of caches. The dedicated cache networks too had a similar issue, and placement delivery arrays (PDAs) were introduced as a solution to address the sub-packetization bottleneck of coded caching in the dedicated cache network. Our objective is to design coded caching schemes for shared caches with lower sub-packetization requirements than the existing schemes. By leveraging the PDA constructions, we propose a procedure to obtain new coded caching schemes for shared caches with reduced sub-packetization levels than the known schemes in both single and multi-antenna settings. The advantage of the proposed procedure is that all the existing PDA constructions can be transformed into coded caching schemes for shared caches, thereby reducing the sub-packetization level requirement. In addition, the proposed procedure also recovers the optimal caching schemes given by Parinelloet al.by using a PDA corresponding to the Maddah-Ali Niesen scheme.

Multi-access coded caching schemes from cross resolvable designs (CRD) have been reported recently [7]. To be able to compare coded caching schemes with different number of users and possibly with different number of caches a new metric called rate-per-user was introduced and it was shown that under this new metric the schemes from CRDs perform better than the Maddah-Ali-Niesen scheme in the large memory regime. In this paper a new class of CRDs is presented and it is shown that the multi-access coded caching schemes derived from these CRDs perform better than the Maddah-Ali-Niesen scheme in the entire memory regime.

Coded Caching is an efficient technique to reduce peak-hour network traffic. One limitation of known coded caching schemes is that the demands of all users are revealed to their peers in the delivery phase. Schemes that assure privacy for user demands are studied in the recent past. Assuming that the users are equipped with caches of small memory sizes, the achievable rate under demand privacy constraints is investigated in this work. We present an MDS code based demand private coded caching scheme with$K$users and$N$files that achieves a memory rate pair$\left(\frac{1}{K(N-1)+1}, N\, \left(1- \frac{1}{K(N-1)+1}\right)\right)$. The presented memory-rate pair meets the lower bound under demand-privacy requirements, proposed by Yan and Tuninetti in the recent work “Fundamental Limits of Caching for Demand Privacy against Colluding Users”. By memory sharing, the achievable memory-rate pair characterizes the exact rate-memory trade-off for the demand private coded caching scheme for cache memory$M\in\left[0,\frac{1}{K(N-1)+1}\right]$.

In this paper we consider multi-access coded caching problem introduced by Hachem et.al., where each user has access to$L$neighboring caches in a cyclic wrap-around fashion. We focus on the deterministic schemes for a specific class of multi-access coded caching problem based on the concept of PDA. We construct new PDAs which specify the delivery scheme for the specific class of multi-access coded caching problem discussed in this paper. For the proposed scheme, the coding gain is larger than that of the state-of-the-art while the sub-packetization level varies only linearly with the number of users. Hence, the advantage of the proposed scheme is two-fold, in terms of the coding gain as well as the sub-packetization level.

The well known Maddah-Ali-Niesen (MAN) coded caching scheme for users with dedicated cache is extended for use in multi-access coded cache scheme where the number of users need not be same as the number of caches in the system. The well known MAN scheme is recoverable as a special case of the multi-access system considered. The performance of this scheme is compared with the existing works on multi-access coded caching. To be able to compare the performance of different multi-access schemes with different number of users for the same number of caches, the terminology of per user rate (rate divided by the number of users) introduced in [11] is used.

Recently multi-access coded caching schemes with number of users different from the number of caches obtained from a special class of resolvable designs called Cross Resolvable Designs (CRDs) have been reported and a new performance metric called rate-per-user has been introduced by Digvijay et al (“Multi-Access Coded Caching Schemes From Cross Resolvable Designs” in IEEE Transactions on Communications, May 2021). In this paper, we present a generalization of this work resulting in multi-access coded caching schemes with improved rate-per-user.

The multi-access variant of the coded caching problem in the presence of external wiretappers is investigated. A multiaccess coded caching scheme with K users, K caches and N files, where each user has access to L neighbouring caches in a cyclic wrap-around manner, is proposed, which is secure against the wiretappers. Each transmission in the conventional insecure scheme will be now encrypted by a random key. The proposed scheme uses a novel technique for the key placement in the caches. It is also shown that the proposed secure multi-access coded caching scheme is within a constant multiplicative factor from the information-theoretic optimal rate for $L\displaystyle \geq\frac{K}{2}$ and $N\geq 2K$.

Data traffic in a client-server framework exhibits a temporal variability leading to congestion of resources at peak hours. One prevalent technique to overcome this problem is to load popular content/data into cache memories distributed across the end users. In this paper, the multi-access coded caching problem is considered in which each client is connected to multiple consecutive caches in a cyclic wrap around fashion and the cache memories are arbitrarily loaded in a decentralized manner. A new delivery scheme is proposed for the decentralized multi-access coded caching problem. A lower bound on the delivery rate is also obtained for the decentralized multi-access coded caching problem using techniques from index coding. The delivery scheme is shown to be optimal among all linear schemes when the number of caches associated with each user satisfies certain constraints.

The coded caching problem with secrecy constraint i.e., the users should not be able to gain any information about the content of the files that they did not demand, is known as the secretive coded caching problem. This was proposed by Ravindrakumar et al. in the paper titled "Private Coded Caching" that appeared in IEEE Transactions on Information Forensics and Security, 2018 and is characterised by subpacketization levels growing exponentially with the number of users. In the context of coded caching without secrecy, coded caching schemes at subexponential subpacketization levels are feasible by representing the caching system in the form of a Placement Delivery Array (PDA) and designing placement and delivery policies from it. Motivated by this, we propose a secretive coded caching scheme with low subpacketization using PDA, for users with dedicated caches in the centralized setting. When our scheme is applied to a special class of PDA known as MN PDA, the scheme proposed by Ravindrakumar et al. is recovered.

We consider the coded caching problem with shared caches where several users share a cache, but each user has access to only a single cache. For this network, the fundamental limits of coded caching are known for centralized and decentralized settings under uncoded placement. In the centralized case, to achieve the gains offered by coded caching, one requires a subpacketization which increases exponentially with the number of caches. The dedicated cache networks had a similar issue, and placement delivery arrays (PDAs) were introduced as a solution to it. Using the PDA framework, we propose a procedure to obtain new coded caching schemes for shared caches with lower sub-packetization requirements. The advantage of this procedure is that we can transform all the existing PDA structures into coded caching schemes for shared caches, thus resulting in low sub-packetization schemes. We also show that the optimal scheme given by Parrinello, Ünsal and Elia (Fundamental Limits of Coded Caching with Multiple Antennas, Shared Caches and Uncoded Prefetching) can be recovered using a Maddah-Ali Niesen PDA.

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.

In a distributed computation system, there is a master node who wants to compute a function of its own data by distributing the computation amongst several worker nodes. In distributed computation system considered here, the master wants to multiply two matrices, one owned by the master and other matrix is in the library of matrices shared by the worker nodes. The master divides the computation task among these nodes. After recovering the desired computation, any set of up to T colluding workers should not know which matrix in the library was desired by the master, referred to as demand privacy and also do not have any information about master's matrix, referred to as data privacy. In this paper, a distributed computing scheme is proposed that simultaneously ensures (1) data and demand privacy of the master against colluding workers (2) straggler mitigation and (3) security against malicious workers. Similar matrix multiplication scenario was considered against non-colluding worker nodes by M. Kim and J. Lee in Private Secure Coded Computation.

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.

The decentralized coded caching was Introduced In [M. A. Maddah-Ali and U. Niesen, "Decentralized coded caching attains order-optimal memory-rate tradeoff," IEEE/ACM Trans. Networking, Aug. 2015] in which no coordination is required for the content placement. This scheme is extended to all the demand cases and the optimality is shown in the literature under the uncoded prefetching regime using information theoretic lower bound. In this paper, an alternate proof for optimality is given using index coding techniques. Moreover, for the case when the shared broadcast link is error prone, an optimal error correcting delivery scheme is proposed for coded caching problems with the decentralized placement. Next, the Least Recently Sent (LRS) online coded caching scheme is considered. The optimality of this scheme is also proved using index coding techniques. An optimal error correcting delivery scheme is proposed for coded caching problems with the LRS online prefetching.

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.

We present a novel caching and coded delivery scheme for a multi-access network where multiple users can have access to the same cache (shared cache) and multiple caches can be accessed by the same user. This scheme is obtained from resolvable designs satisfying certain conditions which we call cross resolvable designs. To be able to compare different multi-access coded schemes with different number of users we normalize the rate of the schemes by the number of users served. Based on this per-user-rate we show that our scheme performs better than the well known Maddah-Ali - Niesen (MaN) scheme and the recently proposed (“Multi-access coded caching: gains beyond cache-redundancy” by Serbetci, Parrinello and Elia) SPE scheme. It is shown that the resolvable designs from affine planes are cross resolvable designs and our scheme based on these performs better than the MaN scheme for large memory size cases. The exact size beyond which our performance is better is also presented. The SPE scheme considers only the cases where the product of the number of users and the normalized cache size is 2, whereas the proposed scheme allows different choices depending on the choice of the cross resolvable design.

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.

A variant of the index coding problem (ICP), the embedded index coding problem (EICP) was introduced in [A. Porter and M. Wootters, "Embedded Index Coding," ITW, Sweden, 2019] which was motivated by its application in distributed computing where every user can act as sender for other users and an algorithm for code construction was reported. The construction depends on the computation of minrank of a matrix, which is computationally intensive. In [A.A. Mahesh, N. S. Karat and B. S. Rajan, "Min-rank of Embedded Index Coding Problems," ISIT, 2020], the authors have provided an explicit code construction for a class of EICP - Consecutive and Symmetric Embedded Index Coding Problem (CS-EICP). We introduce the idea of sub-packetization of the messages in index coding problems to provide a novel code construction for CSEICP in contrast to the scalar linear solutions provided in the prior works. For CS-EICP, the normalized rate, which is defined as the number of bits transmitted by all the users together normalized by the total number of bits of all the messages, for our construction is lesser than the normalized rate achieved by Mahesh et al., for scalar linear codes.

Coding theoretic techniques have been proposed for synchronous Gradient Descent (GD) on multiple servers to mitigate stragglers. These techniques provide the flexibility that the job is complete when any k out of n servers finish their assigned tasks. The task size on each server is found based on the values of k and n. However, it is assumed that all the n jobs are started when the job is requested. In contrast, we assume a tiered system, where we start with n1≥ k tasks, and on completion of c tasks, we start n2- n1more tasks. The aim is that as long as k servers can execute their tasks, the job gets completed. This paper exploits the flexibility that not all servers are started at the request time to obtain the achievable task sizes on each server. The task sizes are in general lower than starting all n2tasks at the request times thus helping achieve lower task sizes which helps to reduce both the job completion time and the total server utilization.

The problem of broadcasting with noisy side information (BNSI) consists of a set of receivers, each demanding a subset of messages available at a sender. The receivers already have a noisy version of their demands (due to decoding errors in previous transmissions) that can be considered as noisy side information for the retransmission phase. The maximum possible number of errors in the noisy side-information at a receiver is referred to as its error threshold. The objective is to reduce the number of transmissions in the retransmission phase by taking advantage of the knowledge of noisy side-information at the receivers, when each receiver has a different error threshold. We consider linear encoding schemes and provide a set of necessary and sufficient conditions for any linear code to be valid. We present a field-size independent coding scheme with low-complexity (only additions allowed in the coding scheme). This generalizes a coding scheme given in a prior work for the BNSI problem with equal error thresholds. We then provide a greedy algorithm to obtain a field-size independent encoding scheme with low-complexity for any BNSI problem with equal error thresholds.

One of the key problems affecting the performance of algorithms running on a distributed storage system is straggler nodes. There have been works on reducing the recovery threshold (i.e., the minimum number of workers the master needs to wait for, in order to compute the final output) in the case of massive matrix multiplication problems. These works generally consider matrices over arbitrary field i.e., matrices over fields of characteristic both zero and prime. In this paper, we focus on multiplication of matrices over finite fields in a distributed storage system and exploit some properties of finite fields to achieve a fractional improvement in the recovery threshold, with a tradeoff in computational complexity. The proposed coding idea is applicable without restriction on the number of workers and the field size.

Groupcast index coding problem is the most general version of the classical index coding problem, where any receiver can demand any number of messages and have any subset of messages as side-information as described by its fitting matrix. A single-sender index coding problem is said to be a joint extension of a set of single unicast sub-problems, if the fitting matrices of all the sub-problems are disjoint submatrices of its fitting matrix. In our prior work (C. Arunachala and B. S. Rajan, "Optimal scalar linear index codes for three classes of two-sender unicast index coding problem", International Symposium on Information Theory and its Applications (ISITA 2018)), a special class of joint extensions were used to obtain scalar linear codes for some classes of two-sender unicast index coding problems. We extend the definition of single-sender joint extensions of single-unicast sub-problems to the case, where the sub-problems can also be groupcast problems. We study a special class of such joint extensions where the extended problem is also dependent on another groupcast problem called the base problem. The fitting matrix of the base problem decides the positions of fitting matrices of the sub-problems in that of the extended problem. We then provide an algorithm to construct a scalar linear code (not optimal in general), for this class of joint extensions using scalar linear codes of all the sub-problems and the base problem. We also identify a subclass where the constructed codes are scalar linear optimal.

Classical coded caching setting avails each user to have one dedicated cache. This is generalized to a more general shared cache scheme and the exact expression for the worst case rate was derived in [E. Parrinello, A. Unsal, P. Elia, " Fundamental Limits of Caching in Heterogeneous Networks with Uncoded Prefetching," available on arXiv:1811.06247 [cs.IT], Nov. 2018]. For this case, an optimal linear error correcting delivery scheme is proposed and an expression for the peak rate is established for the same. Furthermore, a new delivery scheme is proposed, which gives an improved rate for the case when the demands are not distinct.

A new variant of index coding problem termed as Pliable Index Coding Problem (PICOD) is formulated in [S. Brahma, C. Fragouli, "Pliable index coding", IEEE Transactions on Information Theory, vol. 61, no. 11, pp. 6192-6203, 2015]. In PICOD, we consider a server holding a set of messages and there is a set of clients having a subset of messages with them. Each client is satisfied if it receives any of the message which it doesn't have. We discuss the class of PICOD where the side information is consecutive. We provide index codes for two cases - for the class where each client gets exactly one desired message and for a class where total number of messages decoded by the effective clients is maximized. Another variant of index coding problem is - c-Constrained Pliable Index Coding Problem [Linqi Song, Christina Fragouli and Tianchu Zhao, "A Pliable Index Coding Approach to Data Shuffling," arXiv:1701.05540v3 [cs.IT] 3 May 2018]. It is basically PICOD with a c-constraint, i.e, each message is decoded by at most c clients demanding that message. We provide index codes for some classes of this variant with consecutive side information.

For index coding problems with special structure on the side-information graphs called Interlinked Cycle (IC) structures index codes have been proposed in the literature (C. Thapa, L. Ong, and S. Johnson, "Interlinked Cycles for Index Coding: Generalizing Cycles and Cliques", in IEEE Trans. Inf. Theory, vol. 63, no. 6, Jun. 2017 with a correction in "Interlinked Cycles for Index Coding: Generalizing Cycles and Cliques", in arxiv (arxiv:1603.00092v2 [cs.IT] 25 Feb 2018)). In this paper we consider a generalization of IC structures called IC structures with interlocked outer cycles. For IC structures with interlocked outer cycles we show that the optimal length (also known as the minrank of the index coding problem) depends on the maximum number of disjoint outer cycles. We give two sufficient conditions such that if any of these is satisfied then we provide explicit optimal index code construction. The conditions mentioned above are shown to be not necessary by an explicit example.

In most of the network coding problems with k messages, the existence of binary network coding solution over F2depends on the existence of adequate sets of k-dimensional binary vectors such that each set comprises of linearly independent vectors. In a given k × n (n ≥ k) binary matrix, there exist (n) binary sub-matrices of size k × k. Every possible k × k submatrix may be of full rank or singular depending on the columns present in the matrix. In this work, for full rank binary matrix G of size k × n satisfying certain condition on minimum Hamming weight, we establish a relation between the number of full rank sub-matrices of size k × k and the weight enumerating function of the error correcting code with G as the generator matrix. We give an algorithm to compute the number of full rank k × k submatrices.

A single unicast index coding problem (SUICP) with symmetric neighboring interference (SNI) has K messages and K receivers, the kth receiver Rk wanting the kth message xk and having the interference with D messages after and U (D ≥ U) messages before its desired message. Maleki et. al. derived the lowerbound on the broadcast rate of this setting to be D + 1. In our earlier work, for SUICP(SNI) with arbitrary K, D and U, we defined set S of 2-tuples and for every (a, b) ∈ S, we constructed b-dimensional vector linear index code with rate D + 1 + a/b by using an encoding matrix of dimension Kb × (b(D + 1) + a). In this paper, we use the symmetric structure of the SUICP(SNI) to reduce the size of encoding matrix by partitioning the message symbols. The rate achieved in this paper is same as that of the existing constructions of vector linear index codes. More specifically, we construct b-dimensional vector linear index codes for SUICP(SNI) by partitioning the Kb messages into b(U + 1) + c sets for some non-negative integer c. We use an encoding matrix of size Kb/b(U+1)+c × b(D+1)+a/b(U+1)+c to encode each partition separately. The advantage of this method is that the receivers need to store at most b(D+1)+a/b(U+1)+c number of broadcast symbols (index code symbols) to decode a given wanted message symbol. We also give a construction of scalar linear index codes for SUICP(SNI) with arbitrary K, D and U. We give an improved upperbound on the broadcast rate of SUICP(SNI).

Cycles and Cliques in a side-information graph reduce the number of transmissions required in an index coding problem. Thapa, Ong and Johnson defined a more general form of overlapping cycles, called the interlinked-cycle (IC) structure, that generalizes cycles and cliques. They proposed a scheme, that leverages IC structures in digraphs to construct scalar linear index codes. In this paper, we extend the notion of interlinked cycle structure to define more generalised graph structures called overlapping interlinked cycle (OIC) structures. We prove the index coding capacity of OIC structures by giving an index code with length equal to the order of maximum acyclic induced subgraph (MAIS) of OIC structures.

The two-sender unicast index coding problem consists of two senders collectively having all the demanded messages of a set of receivers, where each receiver demands a unique message. The senders avail the knowledge of the side-information present at all the receivers to reduce the total number of broadcast transmissions. This problem is relevant in many practical communication problems like multi-source satellite communication, multi-user coded cooperative data exchange, and other related problems. In this paper, the two-sender unicast index coding problem is analyzed using three independent single-sender subproblems. Optimal broadcast rate (total number of transmitted bits per message bit as the message length tends to infinity) for all the unsolved instances of a special class of the two-sender unicast index coding problem is provided in terms of those of the three associated subproblems. The optimal broadcast rate established in this work serves as a lower bound for the optimal broadcast rate of any general associated two-sender unicast index coding problem. An achievable broadcast rate (total number of transmitted bits per message bit) with finite length messages for any finite length, is given for a subclass of the two-sender unicast index coding problem by providing a code-construction. This serves as a tighter upper bound when compared to the prior state of art.

The length of an optimal scalar linear index code of a single unicast index coding problem (SUICP) is equal to the minrank of its side-information graph. A single unicast index coding problem is called symmetric neighboring and consecutive (SNC) side-information problem if it has K messages and K receivers, the kth receiver Rkwanting the kth message xkand having the side-information D messages immediately after xkand U (D ≥ U) messages immediately before xk. Maleki, Cadambe and Jafar obtained the capacity of this SUICP(SNC) and proposed (U + 1)-dimensional optimal length vector linear index codes by using Vandermonde matrices. However, for a b-dimensional vector linear index code, the transmitter needs to wait for b realizations of each message and hence the latency introduced at the transmitter is proportional to b. For any given single unicast index coding problem with the side-information graph G, MAIS(G) is used to give a lower-bound on the broadcast rate of the ICP. In this paper, we analyse the properties of minrank of SUICP(SNC) side-information graph. We derive the MAIS(G) of side-information graph G of SUICP(SNC). For arbitrary K, D and U, we construct scalar linear index codes lfor SUICP(SNC) with length ⌈K/U+1⌉ - ⌊D-U/U+1⌋. We obtain the minrank of SUICP(SNC) side-information graph and show that the length of the constructed scalar linear index codes is equal to minrank of SUICP(SNC) side-information graph for some combinations of K, D and U.

The length of an optimal scalar linear index code of a groupcast index coding problem is equal to the minrank of its side-information hypergraph. The side-information hyper-graph becomes a side-information graph for a special class of groupcast index coding problems known as unicast index coding problems. The number of computations required to find the minrank of a side-information graph depends on the number of edges present in the side-information graph. In this paper, we define the notion of minrank-critical edges in a side-information graph and derive some properties of minrank, which identifies minrank-non-critical edges. Using these properties we present a method to reduce the number of computations required to compute minrank. Apart from this, we give a heuristic method to compute minrank. Also, we give an heuristic algorithm to find a clique cover of the side-information graph by using some binary operations on the adjacency matrix of the side-information graph. We also give a method to convert a groupcast index coding problem into a single unicast index coding problem. Combining all these results, we give a method to construct index codes (with not necessarily optimal length) for groupcast index coding problems. The construction technique is independent of field size and hence can be used to construct index codes over the binary field. In some cases the constructed index codes are better than the best known in the literature both in terms of the length of the code and the minimum field size required.

The two-sender unicast index coding problem consists of two senders, each having a different set of messages. Some messages may be common to both the senders. Each receiver demands a unique message and has a subset of messages known as its side-information. The senders transmit coded messages by availing the knowledge of the side-information of all the receivers, such that all the receivers are able to decode their demands. The aim is to find the optimal aggregate number of coded transmissions per message length (also called the optimal broadcast rate with finite length messages), and its limiting value as the message length tends to infinity (also called the optimal broadcast rate). In this paper, only linear coding schemes are considered. Optimal linear broadcast rate for any finite message length and optimal linear broadcast rate for a basic class of the two-sender unicast index coding problem are established. Optimal code-constructions are also provided. These results are given in terms of the corresponding results of three independent single-sender sub-problems of the two-sender unicast index coding problem. Proof techniques used to obtain the results for the two-sender problem are shown to be useful in obtaining the results for some classes of the multi-sender unicast index coding problem.

The problem of two-sender unicast index coding consists of two senders and a set of receivers. Each receiver demands a unique message not demanded by any other receiver and has a subset of messages as its side information. Every demanded message is available with at least one of the senders. The senders avail the knowledge of the side information at all the receivers to reduce the total number of transmissions required to satisfy the demands of all the receivers. The objective is to find the minimum total of number of transmissions per message length (known as the optimal broadcast rate with finite length messages) and its limiting value as the message length tends to infinity (called the optimal broadcast rate). Achievable broadcast rates are provided for a class of the two-sender unicast index coding problem based on a special graph coloring technique called two-sender graph coloring. This result illustrates the utility of graph products in the two-sender unicast index coding problem for the first time in the literature. For another class, achievable broadcast rates are provided based on the optimal broadcast rates of three single-sender sub-problems with finite message length. This employs a code construction for the two-sender unicast index coding problem using optimal codes (including non-linear codes) of the sub-problems. Optimal broadcast rates are provided for a special class of the TUICP for which only an upper bound was known prior to this work. The optimal broadcast rates presented in this work also consider non-linear coding schemes at the two senders.

The index coding with side-information problem introduced by Birk and Kol has been generalized to the case, where the transmissions are subjected to errors by Dau et al.. Lower and upper bounds on the optimal number of transmissions required to correct a specified number δ of errors were established. In another generalization of index coding problem, namely, generalized index coding (GIC) problem introduced by Dai et al., linear combination of the messages can be demanded and held as side information by the receivers. Error correction for GIC problems was studied and the bounds for optimal number of transmissions required for δ-error correcting generalized index codes were established by Byrne and Calderini. In this paper, for a particular class of GIC problems construction of optimal scalar linear index codes are discussed. For this class of GIC problems, the optimal linear δ-error correcting index codes are also constructed. As special cases, optimal linear error correcting codes are obtained for two classes of original index coding problems, namely, single-prior index coding problems and single unicast index coding problems with symmetric neighboring consecutive side information.

In coded caching, a single server is connected to a set of users through a shared bottleneck link, which is assumed to be error free. During non-peak hours, all the users fill their local cache with portions of the files available. During the delivery phase, each user requests a file and the server delivers coded transmissions to meet the demands. In this paper, the links between the server and the users are assumed to be error prone. Prefetching errors are also considered. A new delivery scheme is required to meet the demands of each user even after receiving a finite number of transmissions in error in the presence of erroneous portions of files in the cache. The minimum average rate and minimum peak rate for this problem are characterized. Closed form expressions for average and peak rates for a particular caching scheme, namely, symmetric batch prefetching are established when there are no prefetching errors. An optimal linear error correcting delivery scheme is proposed for coded caching problems with symmetric batch prefetching in the absence of prefetching errors. In addition to this, lower bounds are established for the optimal rate required when there are prefetching errors in symmetric batch prefetching.

In the conventional index coding problem, the messages transmitted by the source to satisfy the demands of the receivers are error-free. However, in practice, the messages may be error prone which led to the introduction of error-correcting index codes. An error-correcting index code is an encoding scheme which enables every receiver to decode its demanded message even in the presence of certain number of transmission errors. Formally, an index code capable of correcting at most δ errors at all its receivers is defined as a δ-error-correcting index code. In this paper, we explore the connections between vector linear error-correcting index codes and discrete polymatroids. This is motivated from the connections between linear network error-correcting codes and matroids. It is shown that a vector linear error-correcting index code exists if and only if there exists a representable discrete polymatroid satisfying certain conditions. Differential error-correcting index codes which allow different receivers to have different error-correcting capabilities are also studied. Note that the δ-error-correcting code is a special case of a differential error-correcting index code. Error correction at a subset of receivers is another special case which is discussed.

Index code construction and decoding algorithm for side-information graphs called interlinked cycle (IC) structures, which generalize cycles and cliques, are given by Thapa, Ong and Johnson (“Interlinked Cycles for Index Coding: Generalizing Cycles and Cliques”, IEEE Trans. Inf. Theory, vol. 63, no. 6, Jun. 2017 and “Interlinked Cycles for Index Coding: Generalizing Cycles and Cliques”, in arxiv (arxiv:1603.00092v2 [cs.IT] 25 Feb 2018)). These IC structures do not have cycles containing only non-inner vertices (called outer cycles). In this paper, index code construction and decoding algorithm are given for IC structures with outer cycles.

Optimal delivery scheme for coded caching problems with small buffer sizes and the number of users no less than the amount of files in the server was proposed by Chen, Fan and Letaief [“Fundamental limits of caching: improved bounds for users with small buffers,” IET Communications, 2016]. This scheme is referred to as the CFL scheme. In this paper, an extension to the coded caching scheme where the link between the server and the users is error prone, is considered. The delivery phase is error prone and the placement phase is considered to be error free. The closed form expressions for average rate and peak rate of error correcting delivery scheme are found for CFL prefetching scheme using techniques from index coding. For a given demand, the delivery phase of a coded caching problem becomes an index coding problem. Using results from error correcting index coding, an optimal linear error correcting delivery scheme for caching problems employing CFL prefetching is proposed.

Coded caching is used to reduce network congestion during peak hours. A single server is connected to a set of users through a shared bottleneck link, which generally is assumed to be error-free. During non-peak hours, all the users have full access to the files and they fill their local cache with portions of the files available. During delivery phase, each user requests a file and the server delivers coded transmissions to meet the demands taking into consideration their cache contents. In this paper we assume that the link between the server and the users is error prone. A new delivery scheme is required to meet the demands of each user even after receiving finite number of transmissions in error. We characterize the average rate and peak rate for this problem. We find closed form expressions of these rates for a particular caching scheme namelysymmetric batch prefetching. We also propose an optimal linear error correcting delivery scheme for coded caching problems with symmetric batch prefetching.

A single unicast index coding problem (SUICP) with symmetric neighboring interference (SNI) has equal number of K messages and K receivers, the kth receiver Rkwanting the kth message xkand having the side-information Kk= (Ik∪xk)c, where Ik= {xk-U, ..., xk-2, xk-1} ∪{xk+1, xk+2, ..., xk+D} is the interference with D messages after and U messages before its desired message. The single unicast index coding problem with symmetric neighboring interference (SUICP-SNI) is motivated by topological interference management problems in wireless communication networks. Maleki, Cadambe and Jafar obtained the capacity of this SUICP-SNI with K tending to infinity and Blasiak, Kleinberg and Lubetzky for the special case of (D=U= 1) with K being finite. Finding the capacity of the SUICP-SNI for arbitrary K,D and U is a challenging open problem. In this paper, for an SUICP-SNI with arbitrary K,D and U, we define a set S of 2-tuples such that for every (a, b) in that set S, the rate D+1+[a/b] is achieved by using vector linear index codes over every finite field. We give an algorithm to find the values of a and b such that (a, b) ∈ S and [a/b] is minimum. We present a new upperbound on the broadcast rate of SUICP-SNI and prove that this upperbound coincides with the existing results on the exact value of the capacity of SUICP-SNI in the respective settings.

The interlinked cycle (IC) structure, that generalizes cycles and cliques was defined by Thapa, Ong and Johnson. Interlinked-cycle-cover (ICC) scheme that leverages IC structures in digraphs to construct scalar linear index codes was proposed. Thapa et, al. conjectured that for any IC structure, the ICC scheme is optimal. It was also conjectured that for any digraph, the ICC scheme performs at least as well as the partial-clique-cover scheme. In this paper, we disprove both the conjectures. We also show that for a specific class of symmetric index coding problems, the performance of ICC scheme is equal to that of the partial-clique-cover scheme.

In this paper, two-sender unicast index coding problem (TUICP) is studied, where the senders possibly have some messages in common, and each receiver requests a unique message. It is analyzed using three independent subproblems (which are single-sender unicast index coding problems (SUICPs)) and the interactions among them. These sub-problems are described by three disjoint vertex-induced subgraphs of the side-information graph of the TUICP respectively, based on the availability of messages at the senders. The TUICP is classified based on the type of interactions among the sub-problems. Optimal scalar linear index codes for a class of TUICP are obtained using those of the sub-problems. For two classes, we identify a sub-class for which scalar linear codes are obtained using the notion of joint extensions of SUICPs. An SUICP IEis said to be a joint extension of l SUICPs if the fitting matrices of all the l SUICPs are disjoint submatrices of that of IE. Joint extensions generalize the notion of rank-invariant extensions. Scalar linear codes and a condition for optimality of the codes are given for a class of joint extensions. Using this result, scalar linear codes and the conditions for their optimality are obtained for two classes of the TUICP.

For side-information graphs called Interlinked Cycle (IC) structures, which generalize cycles and cliques, Thapa, Ong and Johnson ("Interlinked Cycles for Index Coding: Generalizing Cycles and Cliques", IEEE Trans. Inf. Theory, vol. 63, no. 6, Jun. 2017 and "Interlinked Cycles for Index Coding: Generalizing Cycles and Cliques", in arxiv (arxiv:1603.00092v2 [cs.IT] 25 Feb 2018)) have given an index code construction and a decoding algorithm, for the case where the IC structure does not have any cycles consisting only of non-inner vertices (called outer cycles). In this paper, for IC structures with outer cycles, we give a set of necessary and sufficient conditions for the code construction and the decoding algorithm of Thapa, Ong and Johnson to be valid.

A single unicast index coding problem (SUICP) with symmetric neighboring and consecutive side-information (SNCS) has K messages and K receivers, the kth receiver Rkwanting the kth message xkand having the side-information Kk= {xk-U,..., xk-2, xk-1}U{xk+1, xk+2,..., xk+D}. Maleki, Cadambe and Jafar obtained the symmetric capacity of this single unicast index coding problem with symmetric neighboring and consecutive side-information (SUICP(SNCS)) and proposed optimal length codes by using Vandermonde matrices. SUICP(SNCS) with arbitrary K, D and U is the only known setting in index coding for which symmetric capacity is known and vector linear index codes are required to achieve capacity. In our earlier work, we gave optimal length (U + 1)-dimensional vector linear index codes for SUICP(SNCS) satisfying some conditions on K, D and U. In this paper, for SUICP(SNCS) with arbitrary K, D and U, we construct optimal length gcd(U+1/K,D-U,U+1)-dimensional vector linear index codes. We prove that the constructed vector linear index code is of minimal dimension if gcd(K - D + U, U + 1) is equal to gcd(K, D - U, U + 1). The proposed construction gives optimal length scalar linear index codes for the SUICP(SNCS) if (U + 1) divides both K and D - U. The proposed construction is independent of field size and works over every field. We give encoding matrices and a low-complexity decoding for the proposed construction.

A single unicast index coding problem (SUICP) with symmetric and consecutive interference (SCI) has K messages and K receivers, the kth receiver Rkwanting the kth message xkand having interference Ik= {xk-U-m, . . . , xk-m-2, xk-m-1}∪ {xk+m+1, xk+m+2, . . . , xk+m+D} and side-information Kk= (Ik∪xk)c. In this paper, we derive a lowerbound on the broadcast rate of single unicast index coding problem with symmetric and consecutive interference (SUICP(SCI)). In the SUICP(SCI), if m = 0, we refer this as single unicast index coding problem with symmetric and neighboring interference (SUICP(SNI)). In our previous work, we gave the construction of near-optimal vector linear index codes for SUICP(SNI) with arbitrary K, D, U. In this paper, we convert the SUICP(SCI) into SUICP(SNI) and give the construction of near-optimal vector linear index codes for SUICP(SCI) with arbitrary K, U, D and m. The constructed codes are independent of field size. The near-optimal vector linear index codes of SUICP(SNI) is a special case of near-optimal vector linear index codes constructed in this paper for SUICP(SCI) with m = 0. We give an upperbound on the broadcast rate of SUICP(SCI). We derive the capacity of SUICP(SCI) for some special cases.

A single unicast index coding problem (SUICP) with symmetric side-information has K messages and K receivers, the kth receiver Rk wants xk, Rk has some subset of messages as side-information and the side-information is symmetric to its wanted message xk. Maleki, Cadambe and Jafar studied various symmetric index coding problems because of their importance in topological interference management problems. In our previous work, we constructed binary matrices of size mxn for any given arbitrary positive integers m and n such that any n adjacent rows of this matrix are linearly independent. We refer these matrices as Adjacent Independent Row (AIR) matrices. We designed optimal and near-optimal vector linear index codes for various symmetric SUICPs by using AIR matrices. To design the optimal and nearoptimal vector linear index codes, we convert the respective symmetric SUICP into an SUICP with symmetric neighboring and consecutive (SNC) side-information. Then, we use AIR matrix to encode the SUICP with SNC side-information. Hence, low-complexity decoding of SUICP with SNC side-information is important for efficient decoding of optimal and near-optimal index codes for various symmetric SUICPs. We analyse some of the combinatorial properties of AIR matrices in this work. By using these properties, we provide a low-complexity decoding for SUICP with SNC side-information. The low-complexity decoding explicitly identifies the set of broadcast symbols required at every receiver to decode its wanted message. By using lowcomplexity decoding, we find the capacity of SUICP with symmetric side-information Kk= {xk+g, xk+2g, . . . , xk+tg}, where g = gcd(K, D) and t = D/g for any positive integer D <; K.

The broadcast rate β of an index coding problem is the minimum number of index code symbols required to transmit to satisfy the demands of all the receivers. The linear broadcast rate β(l) of an index coding problem is the minimum number of index code symbols obtained by linear encoding by using a encoding matrix. Blasiak et al. defined the fractional clique cover number of an undirected graph and used it to bound the broadcast rate of an index coding problem. Lubetzky et al. proved that nonlinear codes can outperform linear codes. In this paper, we find the fractional clique cover number of two classes of symmetric index coding problems. For single unicast index coding problems with symmetric consecutive and neighboring side-information, we prove that broadcast rate is equal to the fractional clique cover number. We define m-dimensional vector index code of an index coding problem by using disjunctive product of side-information graph. We prove that if linear broadcast rate is equal to fractional clique cover number, then, linear broadcast rate is equal to broadcast rate.

A source coding problem in which a central source has to satisfy the demands of several receivers, with each receiver having some subset of the messages (side-information) held by the source is considered. The source has knowledge of only the cardinality of the side-information at each receiver. The encoding scheme used by the source to transmit at a higher throughput is referred to as an informed source code. A technique to obtain informed source codes by using ℓ-th Near Maximum Distance Separable (Near-MDS) Codes is presented. The advantage of using ℓ-th Near-MDS codes is the reduction in field size required. For certain informed source coding problems, the code obtained from ℓ-th Near-MDS codes is shown to be of the minimum length under certain field size restrictions. The same technique can be used for a given index coding problem to obtain index codes. The index codes obtained through this technique are optimal for, but not limited to, special cases of index coding problems discussed in the paper. Finding an optimal solution to a general index coding problem is NP hard and this technique helps in finding binary suboptimal solutions. Using the Gilbert-Varshamov bound, an upper bound on the lengths of optimal binary informed source codes is obtained.

Noisy index coding problem over a Rayleigh fading channel is studied. The receivers are assumed to be priority ordered with each of them equipped with single antenna and the server with two antennas. To obtain diversity gain along with coding gain, a multiple-input multiple-output (MIMO) scheme which employs space time coding along with index coded PSK modulation, is proposed. For a chosen index code, an arbitrary mapping (of broadcast vectors to PSK signal points) and a 2x1 MIMO system employing Alamouti code, a decision rule for the maximum likelihood (ML) decoding is derived. It is shown that, at very high SNR, the message error performance of the receiver employing ML decoder, depends on the metric called minimum inter-set distance, and for the best coding gain at high SNR, the mapping must maximize the minimum inter-set distance.

In this work an extension of the index coding problem referred to as index coding with restricted information (ICRI) problem is considered. The source has to develop encoding schemes which not only deliver the demanded messages but also prevent receivers from decoding certain specified messages. The problem finds applications in content delivery where a content provider has to restrict the user to obtain only subscribed data. A necessary condition for the ICRI problem to have a linear index coding solution is obtained. Using this condition it is shown that for a certain class of index coding problems, the source is unable to restrict the receiver from decoding unwanted messages. We also show that an ICRI problem has a linear solution if a contraction of the index coding problem can be constructed by contraction of a finite sequence of certain alignment edges. A solution to the ICRI problem is obtained by extending the solution of the contracted index coding problem.

An index coding problem is symmetric if relative to its position, each receiver has identical sets of wanted messages and side information. We provide an algorithm to construct an optimal length scalar linear code for single unicast symmetric index coding problems with neighboring interference. First we compute the minimum number of independent dimensions required to avoid interference and show this number to be equal to the minimum possible length of a scalar linear index code. A code construction is provided that gives the optimal scalar linear index code. Further, we have identified the one-sided neighboring antidotes single unicast symmetric index coding problem as a special case of the neighboring interference problem and have constructed an optimal scalar linear index code for the former.

A procedure to obtain index codes for a given index coding problem by using l-th Near Maximum Distance Separable Codes (NMDS) codes is presented. The advantage of using l-th NMDS codes is the reduction in field size required. A trade off between field size and length of index codes is observed. Using appropriate l-th NMDS codes binary index codes for the index coding problem can be constructed. The index codes obtained through this technique make use of only the minimum value of cardinality of the side-information available at the receivers and do not use messages in their side-information. The index codes obtained through this technique are optimal for, but not limited to, special cases of index coding problems discussed in the paper. Finding an optimal solution of a general index coding problem is NP Hard and this technique helps in finding binary suboptimal solutions. Using the Gilbert-Varshamov bound, an upper bound on the length of optimal binary index codes is obtained. Specifically we obtain a length for which a binary index code is guaranteed to exist.

The connections between index coding and matroid theory have been well studied in the recent past. Index coding solutions were first connected to multi linear representation of matroids. For vector linear index codes, discrete polymatroids, which can be viewed as a generalization of the matroids, were used. The index coding problem has been generalized recently to accommodate receivers that demand functions of messages and possess functions of messages. In this work we explore the connections between generalized index coding and discrete polymatroids. The conditions that need to be satisfied by a representable discrete polymatroid for a generalized index coding problem to have a vector linear solution is established. From a discrete polymatroid, an index coding problem with coded side information is constructed and it is shown that if the index coding problem has a certain optimal length solution then the discrete polymatroid is representable. If the generalized index coding problem is constructed from a matroid, it is shown that the index coding problem has a binary scalar linear solution of optimal length if and only if the matroid is binary representable.

A single unicast index coding problem (SUICP) with symmetric neighboring interference (SNI) has equal number of K messages and K receivers, the kth receiver Rkwanting the kth message xkand having the side-information Kk= (IkUxk)c, where Ik= {xk-U,..., Xk-2, xk-1} U {xk+1, xk+2,..., xk+D} is the interference with D messages after and U messages before its desired message. Maleki, Cadambe and Jafar obtained the capacity of this symmetric neighboring interference single unicast index coding problem (SNI-SUICP) with (K) tending to infinity and Blasiak, Kleinberg and Lubetzky for the special case of (D = U = 1) with K being finite. In this work, for any finite K and arbitrary D we obtain the capacity for the case U = gcd(K, D + 1) - 1. Our achievability proof is constructive, i.e., we give an explicit construction of a linear index code achieving the capacity.

In bidirectional relaying using Physical Layer Network Coding (PLNC), it is generally assumed that users employ same modulation schemes in the Multiple Access phase. However, as observed by Zhang et al., it may not be desirable for the nodes to always use the same modulation schemes, particularly when node-relay channels are not equally strong. Such a scheme is called Heterogeneous PLNC. However, the above approach uses the computationally intensive Closest Neighbour Clustering algorithm to find the network coding maps to be applied at the relay. Also, the treatment is specific to certain cases of heterogeneous modulations. In this paper, we show that, when users employ heterogeneous symmetric-PSK modulations, the network coding maps and the mapping regions in the fade state plane can be obtained analytically. Performance results are provided in terms of relay error rate and bit error rate.

The index coding problem with side information (ICSI) was introduced by Birk and Kol, 1998. In this problem, a sender seeks to meet the demands, in minimum number of transmissions, of several receivers, each of which has some prior information on the messages (called side information). In a generalization of this problem called Generalized Index Coding problem (GICP) (Dai et al 2014), linear combination of the messages can be demanded and held as side information by the receivers. The paper by Byrne and Calderini 2017, characterizes the optimal length of linear index codes for GICP based on generalized minrank. Computation of min-rank is known to be NP-hard in general. Another generalization to ICSI problem, where transmissions are subject to noise, was addressed in Dau et al 2013 and lower and upper bounds on optimal linear ¿-error correcting index codes were established. The paper by Byrne and Calderini 2017, studied error correction for GICP and obtains lower and upper bounds on optimal linear ¿-error correcting index codes. In this paper, we find the optimal length of scalar linear index codes (min-rank) for a specific class of GICP and discuss the construction of optimal scalar linear index codes. We also find optimal error correcting index codes for some special cases of the above mentioned class and discuss the construction of optimal linear ¿-error correcting index codes.

Two-way relaying is one of the major applications of broadband communication satellites, for which Physical Layer Network Coding (PLNC) is an efficient technique. Earlier studies have considered satellites employing PLNC with onboard processing. This paper investigates the performance of PLNC over non-regenerative satellites, as a majority of the operational and planned satellites do not have onboard processing. Assuming that the channel magnitudes of the two users are equal, two operating conditions are considered with uncoded-QPSK relaying. In the first operating condition, both users are completely synchronized in phase and transmit power, and in the second operating condition, phase is not synchronized. The peak power constraint imposed by the satellite amplifier is considered and the error performance bounds are derived for both the conditions. The simulation results for end-to-end Bit Error Rate (BER) and throughput are provided. These results shall enable communication system designers to decide system parameters like power and linearity, and perform trade-off analysis between different relaying schemes.

Index coded PSK modulation over an AWGN broadcast channel, for a given index coding problem (ICP) is studied. For a chosen index code and an arbitrary mapping (of broadcast vectors to PSK signal points), a decision rule for the maximum likelihood (ML) decoder is derived. The message error performance of a receiver at high SNR is characterized by a parameter called PSK-index coding gain (PSK-ICG). The PSK-ICG of a receiver is determined by a metric called minimum inter-set distance. For a given ICP with an order of priority among the receivers, and a chosen $2^N$-PSK constellation an algorithm to find (index code, mapping) pairs, each of which gives the best performance in terms of PSK-ICG of the receivers, is proposed. No other pair of index code (of length 𝒩 with $2^N$ broadcast vectors) and mapping can give a better PSK-ICG for the highest priority receiver. Also, given that the highest priority receiver achieves its best performance, the next highest priority receiver achieves its maximum gain possible and so on in the specified order of priority.

Instantly Decodable Network Codes are of great interest in broadcast applications because of their properties like low decoding delay, low encoding and decoding complexities, and simple receiver requirements. This work explores two different multicast broadcast scenarios and gives instantly decodable index codes that perform better than codes in existing literature. First, we describe our novel Unequal Error Protection scheme that achieves theoretical optimality and illustrate it through examples. In order sensitive or delay sensitive applications, based on an earlier decodability at the receivers' end, a packet can be classified as high priority (HP) packets or low priority (LP) packets. We introduce a practical algorithm that improves the packet retransmission technique of Muhammed et al. (Proceedings of the 2013 IEEE International Conference on Communications (ICC), Budapest, pp. 5120-5125) for reliable multicast in the instantly decodable network coding framework. Our scheme improves the delay and total completion time by optimizing the number of instantly decodable network code packet transmissions from the source. Further, simulation results with a comparative study show considerable improvement in Quality of Experience (QoE) for the end-users.

The symmetric capacity for index coding problems with K messages and K receivers, each demanding a unique message (Single Unicast Index Coding Problem) and having symmetric (with respect to receiver index), neighboring and consecutive side information (SUICP-SNC) have been reported by Maleki, Cadambe and Jafar. For these index coding problems, assuming that the transmissions are error prone, we present optimal length error-correcting index codes for all one-sided SUICP-SNC problems and for some cases of two-sided SUICP-SNC problems. We also discuss construction for these optimal Error Correcting Index Codes.

In an index coding with side-information (ICSI) problem there is a sender with a set of n independent messages ℳ = {x1, x2, ..., xn} and there are m receivers ℛ = {R1, R2,..., Rm}, each identified with (Wi, Ki), where Wi⊆ ℳ is the set of messages wanted by receiver Riand Ki⊂ ℳ is the set of messages known a priori to receiver Ri. We call a ICSI problem to be single-prior if |Ki| = 1, ∀i. In addition, if Ki∩ Ki= φ, it is called a single-uniprior problem and has been studied in detail by Ong, Ho and Lim [1]. Error Correcting index codes (ECIC) have been studied by Dau, Skachek and Chee [2] and lower and upper bounds on the optimal length of ECICs have been reported. In this paper we show that for single-prior ICSI problems the lower and upper bounds on the optimal ECICs coincide. This leads to construction of optimal length linear ECICs.

While feasibility and obtaining a solution of a given network coding problem are well studied, the decoding procedure and complexity have not garnered much attention. We consider the decoding problem in a network wherein the sources generate multiple messages and the sink nodes demand some or all of the source messages. We consider both linear and non-linear network codes over a finite field and propose to use the sum-product (SP) algorithm over the Boolean semiring for decoding at the sink nodes in order to reduce the computational complexity. We use traceback to further lower the computational cost incurred by SP decoding. For sinks demanding all the messages, we define fast decodability of a network code and identify a sufficient condition for the same.

We consider the functional index coding problem over an error-free broadcast network in which a source generates a set of messages and there are multiple receivers, each holding a set of functions of source messages in its cache, called the Has-set, and demands to know another set of functions of messages, called the Want-set. Cognizant of the receivers' Hassets, the source aims to satisfy the demands of each receiver by making coded transmissions, called a functional index code. The objective is to minimize the number of such transmissions required. The restriction a receiver's demands pose on the code is represented via a constraint called the generalized exclusive law and obtain a code using the confusion graph constructed using these constraints. Bounds on the size of an optimal code based on the parameters of the confusion graph are presented. Next, we consider the case of erroneous transmissions and provide a necessary and sufficient condition that an FIC must satisfy for correct decoding of desired functions at each receiver and obtain a lower bound on the length of an error-correcting FIC.

This paper deals with vector linear index codes for multiple unicast index coding problems where there is a source with K messages and there are K receivers each wanting a unique message and having symmetric (with respect to the receiver index) two-sided antidotes (side information). Starting from a given multiple unicast index coding problem with K messages and symmetric one-sided antidotes for which a scalar linear index code ℭ is known, we give a construction procedure which constructs a sequence (indexed by m) of multiple unicast index coding problems with symmetric two-sided antidotes (for the same source) for all of which a vector linear code ℭ(m)is obtained from ℭ. Also, it is shown that if ℭ is optimal then ℭ(m)is also optimal for all m. To our knowledge, this is the first paper which gives a method to construct a sequence of optimal vector linear index codes.

In contrast to the network coding problem wherein the sinks in a network demand subsets of the source messages, in a network computation problem the sinks demand functions of the source messages. Similarly, in the functional index coding problem, the side information and demands of the clients include disjoint sets of functions of the information messages held by the transmitter instead of disjoint subsets of the messages, as is the case in the conventional index coding problem. It is known that any network coding problem can be transformed into an index coding problem and vice versa. In this work, we establish a similar relationship between network computation problems and a class of functional index coding problems, viz., those in which only the demands of the clients include functions of messages. We show that any network computation problem can be converted into a functional index coding problem wherein some clients demand functions of messages and vice versa. We prove that a solution for a network computation problem exists if and only if a functional index code (of a specific length determined by the network computation problem) for a suitably constructed functional index coding problem exists. Next we show that a functional index coding problem admits a solution of a specified length if and only if a suitably constructed network computation problem admits a solution.

An index coding problem arises when there is a single source with a number of messages and multiple receivers each wanting a subset of messages and knowing a different set of messages a priori. The noiseless Index Coding Problem is to identify the minimum number of transmissions (optimal length) to be made by the source through noiseless channels so that all the receivers can decode their wanted messages using the transmitted symbols and their respective prior information. Recently [4], it is shown that different optimal length codes perform differently in a noisy channel. Towards identifying the best optimal length index code one needs to know the number of optimal length index codes. Preliminary results on this have been presented in [7]. In this paper we present more results on the number of optimal linear index codes for unicast index coding problems. Specifically we obtain the exact number of optimal linear index codes for two classes of unicast index coding problems: (i) Single-unicast uniprior problems, and (ii) Single-uniprior unicast problems. For the case of single-unicast single-uniprior problems a more general proof is provided for the number of optimal linear index codes. A method to identify the optimal length codes which lead to minimum-maximum probability of error is also presented.

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.

While the capacity, feasibility, and methods to obtain codes for network coding problems are well studied, the decoding procedure and complexity have not garnered much attention. In this paper, we pose the decoding problem at a sink node in a network as a marginalize product function (MPF) problem over the Boolean semiring and use the sum product (SP) algorithm on a suitably constructed factor graph to perform iterative decoding. The number of operations required to perform SP decoding is reduced using traceback. The number of operations required to perform SP decoding with and without traceback is obtained. For nonlinear network codes, we define fast decodability of a network code at sinks demanding all the messages and identify a sufficient condition for the same. Next, we consider the network function computation problem wherein the sink nodes demand a function of the messages. We present an MPF formulation for function computation at the sink nodes and use the SP algorithm to obtain the value of the demanded function. Though the proposed method can be used for decoding both linear and nonlinear network codes, it is advantageous only for the case of nonlinear network codes.

Discrete polymatroids are the multi-set analogue of matroids. In this paper, we explore the connections among linear network coding, linear index coding, and representable discrete polymatroids. We consider the vector linear solutions of networks over a field Fq, with possibly different message and edge vector dimensions, which are referred to as linear fractional solutions. It is well known that a scalar linear solution over Fqexists for a network if and only if the network is matroidal with respect to a matroid representable over Fq. We define a discrete polymatroidal network and show that a linear fractional solution over a field Fqexists for a network if and only if the network is discrete polymatroidal with respect to a discrete polymatroid representable over Fq. An algorithm to construct the networks starting from certain class of discrete polymatroids is provided. Every representation over Fqfor the discrete polymatroid, results in a linear fractional solution over Fqfor the constructed network. Next, we consider the index coding problem, which involves a sender, which generates a set of messages X = {x1, x2, . . . xk}, and a set of receivers R, which demand messages. A receiver R ∈ R is specified by the tuple (x, H), where x ∈ X is the message demanded by R and H ⊆ X \ {x} is the side information possessed by R. We first show that a linear solution to an index coding problem exists if and only if there exists a representable discrete polymatroid, satisfying certain conditions, which are determined by the index coding problem considered. Rouayheb et al. showed that the problem of finding a multi-linear representation for a matroid can be reduced to finding a perfect linear index coding solution for an index coding problem obtained from that matroid. The multi-linear representation of a matroid can be viewed as a special case of representation of an appropriate discrete polymatroid. We generalize the result of Rouayheb et al., by showing that the problem of finding a representation for a discrete polymatroid can be reduced to finding a perfect linear index coding solution for an index coding problem obtained from that discrete polymatroid.

The functional source coding problem in which the receiver side information (Has-set) and demands (Want-set) include functions of source messages is studied using row-Latin rectangle. The source transmits encoded messages, called the functional source code, in order to satisfy the receiver's demands. We obtain a minimum length using the row-Latin rectangle. Next, we consider the case of transmission errors and provide a necessary and sufficient condition that a functional source code must satisfy so that the receiver can correctly decode the values of the functions in its Want-set.

In Index coding there is a single sender with multiple messages and multiple receivers each wanting a different set of messages and knowing a different set of messages a priori. The Index Coding problem is to identify the minimum number of transmissions (optimal length) to be made so that all receivers can decode their wanted messages using the transmitted symbols and their respective prior information and also the codes with optimal length. Recently in [6], it is shown that different optimal length codes perform differently in a wireless channel. Towards identifying the best optimal length index code one needs to know the number of optimal length index codes. In this paper we present results on the number of optimal length index codes making use of the representation of an index coding problem by an equivalent network code. We give the minimum number of codes possible with the optimal length. This is done using a simpler algebraic formulation of the problem compared to the approach of Koetter and Medard [4].

The set of all subspaces of Fnqis denoted by ℙq(n). The subspace distance dS(X, Y) = dim(X)+dim(Y)−2 dim(X∩Y) defined on ℙq(n) turns it into a natural coding space for error correction in random network coding. A subset of ℙq(n) is called a code and the subspaces that belong to the code are called codewords. Motivated by classical coding theory, a linear coding structure can be imposed on a subset of ℙq(n). Braun, Etzion and Vardy conjectured that the largest cardinality of a linear code, that contains Fnq, is 2n. In this paper, we prove this conjecture and characterize the maximal linear codes that contain Fnq.

The connection between index coding and matroid theory have been well studied in the recent past. El Rouayheb et al. established a connection between multi linear representation of matroids and wireless index coding. Muralidharan and Rajan showed that a vector linear solution to an index coding problem exists if and only if there exists a representable discrete polymatroid satisfying certain conditions. Recently index coding with erroneous transmission was considered by Dau et al.. Error correcting index codes in which all receivers are able to correct a fixed number of errors was studied. In this paper we consider a more general scenario in which each receiver is able to correct a desired number of errors, calling such index codes differential error correcting index codes. A link between differential error correcting index codes and certain matroids is established. We define matroidal differential error correcting index codes and we show that a scalar linear differential error correcting index code exists if and only if it is matroidal differential error correcting index code associated with a representable matroid.

The connection between index coding and matroid theory have been well studied in the recent past. El Rouayheb et al. established a connection between multi linear representation of matroids and wireless index coding. Muralidharan and Rajan showed that a vector linear solution to an index coding problem exists if and only if there exists a representable discrete polymatroid satisfying certain conditions. Recently index coding with erroneous transmission was considered by Dau et al.. Error correcting index codes in which all receivers are able to correct a fixed number of errors was studied. In this paper we show that vector linear δ-error correcting index code exists if and only if there exists a representable discrete polymatroid satisfying certain conditions.

An index coding scheme in which the source (transmitter) transmits symbols over a wireless fading channel is considered. Index codes with the transmitter using minimum number of transmissions are known as optimal index codes. Different optimal index codes give different performances in terms of probability of error in a fading environment and this also varies from receiver to receiver. In this paper we deal with optimal index codes which minimizes the maximum probability of error among all the receivers. We identify a criterion for optimal index codes that minimizes the maximum probability of error among all the receivers. For a special class of index coding problems, we give an algorithm to identify optimal index codes which minimize the maximum error probability. We illustrate our techniques and claims with simulation results leading to conclude that a careful choice among the optimal index codes will give a considerable gain in fading channels.

The set of all subspaces of Fqnis denoted by Pq(n). The subspace distance dS(X, Y) = dim(X) + dim(Y) - 2 dim(X ∩ Y) defined on Pq(n) turns it into a natural coding space for error correction in random network coding. A subset of Pq(n) is called a code and the subspaces that belong to the code are called codewords. Motivated by classical coding theory, a linear coding structure can be imposed on a subset of Pq(n). Braun et al. conjectured that the largest cardinality of a linear code, that contains Fqn, is 2n. In this paper, we prove this conjecture and characterize the maximal linear codes that contain Fqn.

Matroidal networks were introduced by Dougherty et al. and have been well studied in the recent past. It was shown that a network has a scalar linear network coding solution if and only if it is matroidal associated with a representable matroid. A particularly interesting feature of this development is the ability to construct (scalar and vector) linearly solvable networks using certain classes of matroids. Furthermore, it was shown through the connection between network coding and matroid theory that linear network coding is not always sufficient for general network coding scenarios. The current work attempts to establish a connection between matroid theory and network-error correcting and detecting codes. In a similar vein to the theory connecting matroids and network coding, we abstract the essential aspects of linear network-error detecting codes to arrive at the definition of a matroidal error detecting network (and similarly, a matroidal error correcting network abstracting from network-error correcting codes). An acyclic network (with arbitrary sink demands) is then shown to possess a scalar linear error detecting (correcting) network code if and only if it is a matroidal error detecting (correcting) network associated with a representable matroid. Therefore, constructing such network-error correcting and detecting codes implies the construction of certain representable matroids that satisfy some special conditions, and vice versa. We then present algorithms that enable the construction of matroidal error detecting and correcting networks with a specified capability of network-error correction. Using these construction algorithms, a large class of hitherto unknown scalar linearly solvable networks with multisource, multicast, and multiple-unicast network-error correcting codes is made available for theoretical use and practical implementation, with parameters, such as number of information symbols, number of sinks, number of coding nodes, error correcting capability, and so on, being arbitrary but for computing power (for the execution of the algorithms). The complexity of the construction of these networks is shown to be comparable with the complexity of existing algorithms that design multicast scalar linear network-error correcting codes. Finally, we also show that linear network coding is not sufficient for the general network-error correction (detection) problem with arbitrary demands. In particular, for the same number of network errors, we show a network for which there is a nonlinear network-error detecting code satisfying the demands at the sinks, whereas there are no linear network-error detecting codes that do the same.

Using the spatial modulation approach, where only one transmit antenna is active at a time, we propose two transmission schemes for two-way relay channel using physical layer network coding with space time coding using coordinate interleaved orthogonal designs (CIODs). It is shown that using two uncorrelated transmit antennas at the nodes, but using only one RF transmit chain and space–time coding across these antennas can give a better performance without using any extra resources and without increasing the hardware implementation cost and complexity. In the first transmission scheme, two antennas are used only at the relay, adaptive network coding (ANC) is employed at the relay and the relay transmits a CIOD space time block code (STBC). This gives a better performance compared to an existing ANC scheme for two-way relay channel which uses one antenna each at all the three nodes. It is shown that for this scheme at high SNR the average end-to-end symbol error probability (SEP) is upper bounded by twice the SEP of a point-to-point fading channel. In the second transmission scheme, two transmit antennas are used at all the three nodes, CIOD STBCs are transmitted in multiple access and broadcast phases. This scheme provides a diversity order of two for the average end-to-end SEP with an increased decoding complexity of${\cal O}(M^{3})$for an arbitrary signal set and${\cal O}(M^{2}\sqrt{M})$for square QAM signal set. Simulation results show that the proposed schemes performs better than the existing ANC schemes under perfect and imperfect channel state information.

Interference alignment is known to achieve the maximum sum DoF of 4M/3 in the 2 × 2 X-Network (i.e., two-transmitter (Tx) two-receiver (Rx) X-Network) with M antennas at each node, as demonstrated by Jafar and Shamai. Recently, an Alamouti code based transmission scheme, which we call the Li-Jafarkhani-Jafar (LJJ) scheme, was proposed for the 2×2 X-Network with two antennas at each node. This scheme achieves a sum degrees of freedom (DoF) of 8/3 and also a diversity gain of two with fixed finite constellation inputs. This work first proposes a new STBC for a three transmit antenna single user MIMO system. Building on this STBC, we extend the LJJ scheme to the 2×2 X-Network with three antennas at each node. As in the LJJ scheme and unlike the Jafar-Shamai scheme, only local channel knowledge is assumed at each Tx. It is shown that the proposed scheme achieves the maximum possible sum DoF of 4. A diversity gain of 3 is also guaranteed when fixed finite constellation inputs are used.

Discrete polymatroids are the multi-set analogue of matroids. In this paper, we explore the connections between linear index coding and representable discrete polymatroids. The index coding problem involves a sender which generates a set of messages X = {x1, x2, ... xk} and a set of receivers R which demand messages. A receiver R ∈ R is specified by the tuple (x,H) where x ∈ X is the message demanded by R and H ⊆ X \ {x} is the side information possessed by R. It is first shown that a linear solution to an index coding problem exists if and only if there exists a representable discrete polymatroid satisfying certain conditions which are determined by the index coding problem considered. El Rouayheb et. al. showed that the problem of finding a multi-linear representation for a matroid can be reduced to finding a perfect linear index coding solution for an index coding problem obtained from that matroid. Multi-linear representation of a matroid can be viewed as a special case of representation of an appropriate discrete polymatroid. We generalize the result of El Rouayheb et. al. by showing that the problem of finding a representation for a discrete polymatroid can be reduced to finding a perfect linear index coding solution for an index coding problem obtained from that discrete polymatroid.

Existing construction algorithms of block network-error correcting codes require a rather large field size, which grows with the size of the network and the number of sinks, and thereby can be prohibitive in large networks. In this work, we give an algorithm which, starting from a given network-error correcting code, can obtain another network code using a small field, with the same error correcting capability as the original code. An algorithm for designing network codes using small field sizes proposed recently by Ebrahimi and Fragouli can be seen as a special case of our algorithm. The major step in our algorithm is to find a least degree irreducible polynomial which is coprime to another large degree polynomial. We utilize the algebraic properties of finite fields to implement this step so that it becomes much faster than the brute-force method. As a result the algorithm given by Ebrahimi and Fragouli is also quickened.

The algebraic formulation for linear network coding in acyclic networks with the links having integer delay is well known. Based on this formulation, for a given set of connections over an arbitrary acyclic network with integer delay assumed for the links, the output symbols at the sink nodes, at any given time instant, is a Fpm-linear combination of the input symbols across different generations, where Fpm denotes the field over which the network operates (p is prime and m is a positive integer). We use finite-field discrete Fourier transform to convert the output symbols at the sink nodes, at any given time instant, into a Fpm-linear combination of the input symbols generated during the same generation without making use of memory at the intermediate nodes. We call this as transforming the acyclic network with delay into n-instantaneous networks (n is sufficiently large). We show that under certain conditions, there exists a network code satisfying sink demands in the usual (nontransform) approach if and only if there exists a network code satisfying sink demands in the transform approach. When the zero-interference conditions are not satisfied, we propose three precoding-based network alignment (PBNA) schemes for three-source three-destination multiple unicast network with delays (3-S 3-D MUN-D) termed as PBNA using transform approach and time-invariant local encoding coefficients (LECs), PBNA using time-varying LECs, and PBNA using transform approach and block time-varying LECs. We derive sets of necessary and sufficient conditions under which throughputs close to n' + 1/2n' + 1, n'/2n'+ 1, and n'/2n'+ 1 are achieved for the three source-destination pairs in a 3-S 3-D MUN-D employing PBNA using transform approach and time-invariant LECs, and PBNA using transform approach and block time-varying LECs, where n' is a positive integer. For PBNA using time-varying LECs, we obtain a sufficient condition under which a throughput demand of n1/n, n2/n, and n3/n can be met for the three source-destination pairs in a 3-S 3-D MUN-D, where n1, n2, and n3are positive integers less than orequal to the positive integer n. This condition is also necessary when n1+ n3= n1+ n2= n where n1≥ n2≥ n3.

A transmission scheme based on the Alamouti code, which we call the Li-Jafarkhani-Jafar (LJJ) scheme, was recently proposed for the 2 × 2 X-network [i.e., two-transmitter (Tx) two-receiver X-network] with two antennas at each node. This scheme was claimed to achieve a sum degrees of freedom (DoF) of 8/3 and also a diversity gain of two when fixed finite constellations are employed at each Tx. Furthermore, each Tx required the knowledge of only its own channel unlike the Jafar-Shamai scheme which required global CSIT to achieve the maximum possible sum DoF of 8/3. In this paper, we extend the LJJ scheme to the 2 × 2 X-network with four antennas at each node. The proposed scheme also assumes only local channel knowledge at each Tx. We prove that the proposed scheme achieves the maximum possible sum DoF of 16/3. In addition, we also prove that, using any fixed finite constellation with appropriate rotation at each Tx, the proposed scheme achieves a diversity gain of at least four.

In this paper, a new method is proposed to obtain full-diversity, rate-2 (rate of two complex symbols per channel use) space-time block codes (STBCs) that are full-rate for multiple input double output (MIDO) systems. Using this method, rate-2 STBCs for 4 × 2, 6 × 2, 8 × 2, and 12 × 2 systems are constructed and these STBCs are fast ML-decodable, have large coding gains, and STBC-schemes consisting of these STBCs have a non-vanishing determinant (NVD) so that they are DMT-optimal for their respective MIDO systems. It is also shown that the Srinath-Rajan code for the 4 × 2 system, which has the lowest ML-decoding complexity among known rate-2 STBCs for the 4 × 2 MIDO system with a large coding gain for 4-/16-QAM, has the same algebraic structure as the STBC constructed in this paper for the 4 × 2 system. This also settles in positive a previous conjecture that the STBC-scheme that is based on the Srinath-Rajan code has the NVD property and hence is DMT-optimal for the 4 × 2 system.

This paper considers linear precoding for the constant channel-coefficient K-user MIMO Gaussian interference channel (MIMO GIC) where each transmitter-i (Tx-i) requires the sending of diindependent complex symbols per channel use that take values from fixed finite constellations with uniform distribution to receiver-i (Rx-i) for i=1,2,..., K. We define the maximum rate achieved by Tx-i using any linear precoder as the signal-to-noise ratio (SNR) tends to infinity when the interference channel coefficients are zero to be the constellation constrained saturation capacity (CCSC) for Tx-i. We derive a high-SNR approximation for the rate achieved by Tx-i when interference is treated as noise and this rate is given by the mutual information between Tx-i and Rx-i, denoted as I[Xi;Yi]. A set of necessary and sufficient conditions on the precoders under which [IXi; Yi] tends to CCSC for Tx-i is derived. Interestingly, the precoders designed for interference alignment (IA) satisfy these necessary and sufficient conditions. Furthermore, we propose gradient-ascent-based algorithms to optimize the sum rate achieved by precoding with finite constellation inputs and treating interference as noise. A simulation study using the proposed algorithms for a three-user MIMO GIC with two antennas at each node with di=1 for all i and with BPSK and QPSK inputs shows more than 0.1-b/s/Hz gain in the ergodic sum rate over that yielded by precoders obtained from some known IA algorithms at moderate SNRs.

A new class of Space Time Block Codes (STBCs) known as block orthogonal STBCs (BOSTBCs) was recently presented by Ren et al., which could be exploited by a QR decomposition decoder with M paths (QRDM decoder) to achieve significant decoding complexity reduction without performance loss. The block orthogonal property of the codes constructed, was however only shown via simulations. In this paper, we give analytical proofs for the block orthogonal structure of various existing codes in literature including codes formed as the sum of Clifford Unitary Weight Designs (CUWDs). We also show that, construction methods from Coordinate Interleaved Orthogonal Designs (CIODs), Cyclic Division Algebras (CDAs) and Crossed-Product Algebras (CPAs) can lead to BOSTBCs. In addition, we show that the block orthogonal STBCs offer a reduced decoding complexity when used in tandem with a fast sphere decoder using a depth first search approach. Simulation results involving decoding complexity show a 30% reduction in the number of floating point operations (FLOPS) of BOSTBCs as compared to STBCs without the block orthogonal structure.

A transmission scheme based on the Alamouti code, which we call the Li-Jafarkhani-Jafar (LJJ) scheme, was recently proposed for the 2×2 X Network (i.e., two-transmitter (Tx) two-receiver (Rx) X Network) with two antennas at each node. This scheme was claimed to achieve a sum degrees of freedom (DoF) of 8 over 3 and also a diversity gain of two when fixed finite constellations are employed at each Tx. Furthermore, each Tx required the knowledge of only its own channel unlike the Jafar-Shamai scheme which required global CSIT to achieve the maximum possible sum DoF of 8 over 3. In this paper, we extend the LJJ scheme to the 2 × 2 X Network with four antennas at each node. The proposed scheme also assumes only local channel knowledge at each Tx. We prove that the proposed scheme achieves the maximum possible sum DoF of 16 over 3. In addition, we also prove that, using any fixed finite constellation with appropriate rotation at each Tx, the proposed scheme achieves a diversity gain of at least four.

A linear Fractional Network Coding (FNC) solution over Fqis a linear network coding solution over Fqin which the message dimensions need not necessarily be the same and need not be the same as the edge vector dimension. Scalar linear network coding, vector linear network coding are special cases of linear FNC. In this paper, we establish the connection between the existence of a linear FNC solution for a network over Fqand the representability over Fqof discrete polymatroids, which are the multi-set analogue of matroids. All previously known results on the connection between the scalar and vector linear solvability of networks and representations of matroids and discrete polymatroids follow as special cases. An algorithm is provided to construct networks which admit FNC solution over Fq, from discrete polymatroids representable over Fq. Example networks constructed from discrete polymatroids using the algorithm are provided, which do not admit any scalar and vector solution, and for which FNC solutions with the message dimensions being different provide a larger throughput than FNC solutions with the message dimensions being equal.

This paper considers linear precoding for constant channel-coefficient K-User MIMO Gaussian Interference Channel (K-MIMO GIC) where each transmitter-i (Tx-i) requires to send diindependent complex symbols per channel use that take values from fixed finite constellations with uniform distribution to receiver-i (Rx-i), for i = 1, 2, ..., K. The maximum rate achieved by Tx-i as the signal to noise ratio (SNR) tends to infinity, using any linear precoder, when the interference channel-coefficients are zero is termed as Constellation Constrained Saturation Capacity (CCSC) for Tx-i. In this paper, we derive a high SNR approximation for the rate achieved by Tx-i when interference is treated as noise, which is given by the mutual information between Tx-i and Rx-i, denoted by I[Xi;Yi] where, Xidenotes the symbols generated at Tx-i before precoding and Yidenotes the symbols received at the antennas of Rx-i. Based on this high SNR approximation, we derive a set of necessary and sufficient conditions on the precoders under which I[Xi;Yi] tends to CCSC for Tx-i. Interestingly, the precoders that achieve interference alignment (IA) satisfy these necessary and sufficient conditions. However, finding precoders that achieve IA is known to be NP-hard in general whereas, the precoders that satisfy the derived necessary and sufficient conditions are easy to find for any given channel-coefficients. Further, we propose a gradient-ascent based algorithm to optimize the sum-rate achieved by precoding with finite constellation inputs and treating interference as noise. Simulation study for a 3-MIMO GIC with di= 1, for all i, equipped with two antennas at each node and QPSK inputs shows an improvement of 1.07 bits/sec/Hz in the ergodic sum-rate using the precoders obtained from the proposed algorithm over the precoders that achieve IA, at SNR = -2 dB.

We consider the two-user wireless Multiple Access Relay Channel (MARC), in which nodes A and B want to transmit messages to a destination node D with the help of a relay node R. For the MARC, Wang and Giannakis proposed a Complex Field Network Coding (CFNC) scheme. As an alternative, we propose a scheme based on Physical layer Network Coding (PNC), which has so far been studied widely only in the context of two-way relaying. For the proposed PNC scheme, transmission takes place in two phases: (i) Phase 1 during which A and B simultaneously transmit and, R and D receive, (ii) Phase 2 during which A, B and R simultaneously transmit to D. At the end of Phase 1, R decodes the messages xAof A and xBof B, and during Phase 2 transmits f(xA, xB), where f is many-to-one. Communication protocols in which the relay node decodes are prone to loss of diversity order, due to error propagation from the relay node. To counter this, we propose a novel decoder which takes into account the possibility of an error event at R, without having any knowledge about the links from A to R and B to R. It is shown that if certain parameters are chosen properly and if the map f satisfies a condition called exclusive law, the proposed decoder offers the maximum diversity order of two. Also, it is shown that for a proper choice of the parameters, the proposed decoder admits fast decoding, with the same decoding complexity order as that of the CFNC scheme. Simulation results indicate that the proposed PNC scheme performs better than the CFNC scheme.

Perfect space-time block codes (STBCs) are based on four design criteria - full-rateness, non-vanishing determinant, cubic shaping and uniform average transmitted energy per antenna per time slot. Cubic shaping and transmission at uniform average energy per antenna per time slot are important from the perspective of energy efficiency of STBCs. The shaping criterion demands that the generator matrix of the lattice from which each layer of the perfect STBC is carved be unitary. In this paper, it is shown that unitariness is not a necessary requirement for energy efficiency in the context of space-time coding with finite input constellations, and an alternative criterion is provided that enables one to obtain full-rate (rate of ntcomplex symbols per channel use for an nttransmit antenna system) STBCs with larger normalized minimum determinants than the perfect STBCs. Further, two such STBCs, one each for 4 and 6 transmit antennas, are presented and they are shown to have larger normalized minimum determinants than the comparable perfect STBCs which hitherto had the best known normalized minimum determinants.

In this paper a MIMO quasi static block fading channel with finite N-ary delay-free, noise-free feedback is considered. The transmitter uses a set of N Space-Time Block Codes (STBCs), one corresponding to each of the N possible feedback values, to encode and transmit information. The feedback function used at the receiver and the N component STBCs used at the transmitter together constitute a Finite Feedback Scheme (FFS). If each of the component codes encodes K independent complex symbols and is of transmission duration T, the rate of the FFS is K/T complex symbols per channel use. Although a number of FFSs are available in the literature that provably achieve full-diversity, there is no known universal criterion to determine whether a given arbitrary FFS achieves full-diversity or not. Further, all known full-diversity FFSs for Ttwhere Ntis the number of transmit antennas, have rate at the most 1. In this paper a universal necessary condition for any FFS to achieve full-diversity is given, using which the notion of Feedback-Transmission duration optimal (FT-optimal) FFSs-schemes that use minimum amount of feedback N given the transmission duration T, and minimum transmission duration given the amount of feedback to achieve full-diversity-is introduced. When there is no feedback (N = 1) an FT-optimal scheme consists of a single STBC with T = Nt, and the proposed necessary condition reduces to the well known necessary and sufficient condition for an STBC to achieve full-diversity, viz. every non-zero codeword difference matrix of the STBC must be of rank Nt. Also, a sufficient condition for full-diversity is given for those FFSs in which the component STBC yielding the largest minimum Euclidean distance is chosen. Using this sufficient condition, full-rate (rate Nt) full-diversity FT-optimal schemes are constructed for all (Nt, T, N) with NT = Nt. These are the first full-rate full-diversity FFSs reported in the literature for Tt. Simulation results show that the new schemes have the best error performance among all known FFSs.

The binary coding theory and subspace codes for random network coding exhibit similar structures. The method used to obtain a Singleton bound for subspace codes mimic the technique used in obtaining the Singleton bound for binary codes. This motivates the question of whether there is an abstract framework that captures these similarities. As a first step towards answering this question, we use the lattice framework proposed in [1]. A lattice is a partially ordered set in which any two elements have a least upper bound and a greatest lower bound. A `lattice scheme' is defined as a subset of a lattice. In this paper, we derive a Singleton bound for lattice schemes and obtain Singleton bounds known for binary codes and subspace codes as special cases. The lattice framework gives additional insights into the behaviour of Singleton bound for subspace codes. We also obtain a new upper bound on the code size for non-constant dimension codes. The plots of this bound along with plots of the code sizes of known non-constant dimension codes in the literature reveal that our bound is tight for certain parameters of the code.

In this paper, a new method is proposed to obtain full-diversity, rate-2 (rate of 2 complex symbols per channel use) space-time block codes (STBCs) that are full-rate for multiple input, double output (MIDO) systems. Using this method, rate-2 STBCs for 4×2, 6×2, 8×2 and 12×2 systems are constructed and these STBCs are fast ML-decodable, have large coding gains, and STBC-schemes consisting of these STBCs have a non-vanishing determinant (NVD) so that they are DMT-optimal for their respective MIDO systems.

Construction of high rate Space Time Block Codes (STBCs) with low decoding complexity has been studied widely using techniques such as sphere decoding and non Maximum-Likelihood (ML) decoders such as the QR decomposition decoder with M paths (QRDM decoder). Recently Ren et al., presented a new class of STBCs known as the block orthogonal STBCs (BOSTBCs), which could be exploited by the QRDM decoders to achieve significant decoding complexity reduction without performance loss. The block orthogonal property of the codes constructed was however only shown via simulations. In this paper, we give analytical proofs for the block orthogonal structure of various existing codes in literature including the codes constructed in the paper by Ren et al. We show that codes formed as the sum of Clifford Unitary Weight Designs (CUWDs) or Coordinate Interleaved Orthogonal Designs (CIODs) exhibit block orthogonal structure. We also provide new construction of block orthogonal codes from Cyclic Division Algebras (CDAs) and Crossed-Product Algebras (CPAs). In addition, we show how the block orthogonal property of the STBCs can be exploited to reduce the decoding complexity of a sphere decoder using a depth first search approach. Simulation results of the decoding complexity show a 30% reduction in the number of floating point operations (FLOPS) of BOSTBCs as compared to STBCs without the block orthogonal structure.

A Physical layer Network Coding (PNC) scheme is proposed for the K-user wireless Multiple Access Relay Channel (MARC), in which K source nodes transmit their messages to the destination node D with the help of a relay node R. The proposed PNC scheme involves two transmission phases: (i) Phase 1 during which the source nodes transmit, the relay node and the destination node receive and (ii) Phase 2 during which the source nodes and the relay node transmit, and the destination node receives. At the end of Phase 1, the relay node decodes the messages of the source nodes and during Phase 2 transmits a many-to-one function of the decoded messages. Wireless networks in which the relay node decodes, suffer from loss of diversity order if the decoder at the destination is not chosen properly. A novel decoder is proposed for the PNC scheme, which offers the maximum possible diversity order of 2, for a proper choice of certain parameters and the network coding map. Specifically, the network coding map used at the relay is chosen to be a K-dimensional Latin Hypercube, in order to ensure the maximum diversity order of 2. Also, it is shown that the proposed decoder can be implemented by a fast decoding algorithm. Simulation results presented for the 3-user MARC show that the proposed scheme offers a large gain over the existing scheme for the K-user MARC.

This paper deals with physical layer network-coding for the four-way wireless relaying scenario where four nodes A, B, C and D wish to communicate their messages to all the other nodes with the help of the relay node R. The scheme given in the paper is based on the denoise-and-forward scheme proposed first by Popovski et al. in [1]. Intending to minimize the number of channel uses, the protocol employs two phases: Multiple Access (MA) phase and Broadcast (BC) phase with each phase utilizing one channel use. This paper does the equivalent for the four-way relaying scenario as was done for the two-way relaying scenario by Koike-Akino et al. [2], and for three-way relaying scenario in [3]. It is observed that adaptively changing the network coding map used at the relay according to the channel conditions greatly reduces the impact of multiple access interference which occurs at the relay during the MA phase. These network coding maps are so chosen so that they satisfy a requirement called exclusive law. We show that when the four users transmit points from the same M-PSK constellation, every such network coding map that satisfies the exclusive law can be represented by a 4-fold Latin Hyper-Cube of side M. The network code map used by the relay for the BC phase is explicitly obtained and is aimed at reducing the effect of interference at the MA stage.

The design of modulation schemes for the physical layer network-coded two-way relaying scenario is considered with a protocol which employs two phases: multiple access (MA) phase and broadcast (BC) phase. It was observed by Koike-Akino et al. that adaptively changing the network coding map used at the relay according to the channel conditions greatly reduces the impact of MA interference which occurs at the relay during the MA phase and all these network coding maps should satisfy a requirement called the exclusive law. We show that every network coding map that satisfies the exclusive law is representable by a Latin Square and conversely, that this relationship can be used to get the network coding maps satisfying the exclusive law. The channel fade states for which the minimum distance of the effective constellation at the relay become zero are referred to as the singular fade states. For M- PSK modulation ( M any power of 2), it is shown that there are (M2/4- M/2+1 )M singular fade states. Also, it is shown that the constraints which the network coding maps should satisfy so that the harmful effects of the singular fade states are removed, can be viewed equivalently as partially filled Latin Squares (PFLS). The problem of finding all the required maps is reduced to finding a small set of maps for M- PSK constellations ( M any power of 2), obtained by the completion of PFLS. Even though the completability of M ×M PFLS using M symbols is an open problem, specific cases where such a completion is always possible are identified and explicit construction procedures are provided. Having obtained the network coding maps, the set of all possible channel realizations (the complex plane) is quantized into a finite number of regions, with a specific network coding map chosen in a particular region. It is shown that the complex plane can be partitioned into two regions: a region in which any network coding map which satisfies the exclusive law gives the same best performance and a region in which the choice of the network coding map affects the performance. The quantization thus obtained analytically, leads to the same as the one obtained using computer search for 4-PSK signal set by Koike-Akino et al. when specialized for Simulation results show that the proposed scheme performs better than the conventional exclusive-OR (XOR) network coding and in some cases outperforms the scheme proposed by Koike-Akino et al.

The problem of designing good space-time block codes (STBCs) with low maximum-likelihood (ML) decoding complexity has gathered much attention in the literature. All the known low ML decoding complexity techniques utilize the same approach of exploiting either the multigroup decodable or the fast-decodable (conditionally multigroup decodable) structure of a code. We refer to this well-known technique of decoding STBCs as conditional ML (CML) decoding . In this paper, we introduce a new framework to construct ML decoders for STBCs based on the generalized distributive law (GDL) and the factor-graph-based sum-product algorithm. We say that an STBC is fast GDL decodable if the order of GDL decoding complexity of the code, with respect to the constellation sizeM, is strictly less thanMλ, where λ is the number of independent symbols in the STBC. We give sufficient conditions for an STBC to admit fast GDL decoding, and show that both multigroup and conditionally multigroup decodable codes are fast GDL decodable. For any STBC, whether fast GDL decodable or not, we show that the GDL decoding complexity is strictly less than the CML decoding complexity. For instance, for any STBC obtained from cyclic division algebras which is not multigroup or conditionally multigroup decodable, the GDL decoder provides about 12 times reduction in complexity compared to the CML decoder. Similarly, for the Golden code, which is conditionally multigroup decodable, the GDL decoder is only half as complex as the CML decoder.

A space-time block code (STBC) is said to be multigroup decodable if the information symbols encoded by it can be partitioned into two or more groups such that each group of symbols can be maximum-likelihood (ML) decoded independently of the other symbol groups. In this paper, we show that the upper triangular matrix R encountered during the sphere decoding of a linear dispersion STBC can be rank-deficient even when the rate of the code is less than the minimum of the number of transmit and receive antennas. We then show that all known families of high-rate (rate greater than 1) multigroup decodable codes have rank-deficient R matrix even when the rate is less than the number of transmit and receive antennas, and this rank-deficiency problem arises only in asymmetric MIMO systems when the number of receive antennas is strictly less than the number of transmit antennas. Unlike the codes with full-rank R matrix, the complexity of the sphere decoding-based ML decoder for STBCs with rank-deficient R matrix is polynomial in the constellation size, and hence is high. We derive the ML sphere decoding complexity of most of the known high-rate multigroup decodable codes, and show that for each code, the complexity is a decreasing function of the number of receive antennas.

For any nt transmit, nr receive antenna ( nt×nr) multiple-input multiple-output (MIMO) system in a quasi-static Rayleigh fading environment, it was shown by Elia that linear space-time block code schemes (LSTBC schemes) that have the nonvanishing determinant (NVD) property are diversity-multiplexing gain tradeoff (DMT)-optimal for arbitrary values of nr if they have a code rate of nt complex dimensions per channel use. However, for asymmetric MIMO systems (where ), with the exception of a few LSTBC schemes, it is unknown whether general LSTBC schemes with NVD and a code rate of nr complex dimensions per channel use are DMT optimal. In this paper, an enhanced sufficient criterion for any STBC scheme to be DMT optimal is obtained, and using this criterion, it is established that any LSTBC scheme with NVD and a code rate of min{nt,nr} complex dimensions per channel use is DMT optimal. This result settles the DMT optimality of several well-known, low-ML-decoding-complexity LSTBC schemes for certain asymmetric MIMO systems.

Perfect space-time block codes (STBCs) are based on four design criteria-full-rateness, nonvanishing determinant, cubic shaping, and uniform average transmitted energy per antenna per time slot. Cubic shaping and transmission at uniform average energy per antenna per time slot are important from the perspective of energy efficiency of STBCs. The shaping criterion demands that the generator matrix of the lattice from which each layer of the perfect STBC is carved be unitary. In this paper, it is shown that unitariness is not a necessary requirement for energy efficiency in the context of space-time coding with finite input constellations, and an alternative criterion is provided that enables one to obtain full-rate (rate of nt complex symbols per channel use for an nt transmit antenna system) STBCs with larger normalized minimum determinants than the perfect STBCs. Further, two such STBCs, one each for 4 and 6 transmit antennas, are presented and they are shown to have larger normalized minimum determinants than the comparable perfect STBCs which hitherto had the best-known normalized minimum determinants.

Constellation Constrained (CC) capacity regions of two-user Gaussian Multiple Access Channels (GMAC) have been recently reported, wherein an appropriate angle of rotation between the constellations of the two users is shown to enlarge the CC capacity region. We refer to such a scheme as the Constellation Rotation (CR) scheme. In this paper, we propose a novel scheme called the Constellation Power Allocation (CPA) scheme, wherein the instantaneous transmit power of the two users are varied by maintaining their average power constraints. We show that the CPA scheme offers CC sum capacities equal (at low SNR values) or close (at high SNR values) to those offered by the CR scheme with reduced decoding complexity for QAM constellations. We study the robustness of the CPA scheme for random phase offsets in the channel and unequal average power constraints for the two users. With random phase offsets in the channel, we show that the CC sum capacity offered by the CPA scheme is more than the CR scheme at high SNR values. With unequal average power constraints, we show that the CPA scheme provides maximum gain when the power levels are close, and the advantage diminishes with the increase in the power difference.

Decoding of linear space-time block codes (STBCs) with sphere-decoding (SD) is well known. A fast-version of the SD known as fast sphere decoding (FSD) was introduced by Biglieri, Hong and Viterbo. Viewing a linear STBC as a vector space spanned by its defining weight matrices over the real number field, we define a quadratic form (QF), called the Hurwitz-Radon QF (HRQF), on this vector space and give a QF interpretation of the FSD complexity of a linear STBC. It is shown that the FSD complexity is only a function of the weight matrices defining the code and their ordering, and not of the channel realization (even though the equivalent channel when SD is used depends on the channel realization) or the number of receive antennas. It is also shown that the FSD complexity is completely captured into a single matrix obtained from the HRQF. Moreover, for a given set of weight matrices, an algorithm to obtain an optimal ordering of them leading to the least FSD complexity is presented. The well known classes of low FSD complexity codes (multi-group decodable codes, fast decodable codes and fast group decodable codes) are presented in the framework of HRQF.

With no Channel State Information (CSI) at the users, transmission over the two-user Gaussian Multiple Access Channel with fading and finite constellation at the input, will have high error rates due to multiple access interference (MAI). However, perfect CSI at the users is an unrealistic assumption in the wireless scenario, as it would involve extremely large feedback overheads. In this paper we propose a scheme which removes the adverse effect of MAI using only quantized knowledge of fade state at the transmitters such that the associated overhead is nominal. One of the users rotates its constellation relative to the other without varying the transmit power to adapt to the existing channel conditions, in order to meet certain pre-determined minimum Euclidean distance requirement in the equivalent constellation at the destination. The optimal rotation scheme is described for the case when both the users use symmetric M-PSK constellations at the input, where M=2λ, λ being a positive integer. The strategy is illustrated by considering the example where both the users use QPSK signal sets at the input. The case when the users use PSK constellations of different sizes is also considered. It is shown that the proposed scheme has considerable better error performance compared to the conventional non-adaptive scheme, at the cost of a feedback overhead of just ⌈ log2(M2/8 - M/4 + 2)⌉ + 1 bits, for the M-PSK case.

The performance analysis of adaptive physical layer network-coded two-way relaying scenario is presented which employs two phases: Multiple access (MA) phase and Broadcast (BC) phase. The deep channel fade conditions which occur at the relay referred as the singular fade states fall in the following two classes: (i) removable and (ii) non-removable singular fade states. With every singular fade state, we associate an error probability that the relay transmits a wrong network-coded symbol during the BC phase. It is shown that adaptive network coding provides a coding gain over fixed network coding, by making the error probabilities associated with the removable singular fade states contributing to the average Symbol Error Rate (SER) fall as SNR-2instead of SNR-1. A high SNR upper-bound on the average end-to-end SER for the adaptive network coding scheme is derived, for a Rician fading scenario, which is found to be tight through simulations. Specifically, it is shown that for the adaptive network coding scheme, the probability that the relay node transmits a wrong network-coded symbol is upper-bounded by twice the average SER of a point-to-point fading channel, at high SNR. Also, it is shown that in a Rician fading scenario, it suffices to remove the effect of only those singular fade states which contribute dominantly to the average SER.

We propose a Physical layer Network Coding (PNC) scheme for the K-user wireless Multiple Access Relay Channel, in which K source nodes want to transmit messages to a destination node D with the help of a relay node R. The proposed scheme involves (i) Phase 1 during which the source nodes alone transmit and (ii) Phase 2 during which the source nodes and the relay node transmit. At the end of Phase 1, the relay node decodes the messages of the source nodes and during Phase 2 transmits a many-to-one function of the decoded messages. To counter the error propagation from the relay node, we propose a novel decoder which takes into account the possibility of error events at R. It is shown that if certain parameters are chosen properly and if the network coding map used at R forms a Latin Hypercube, the proposed decoder offers the maximum diversity order of two. Also, it is shown that for a proper choice of the parameters, the proposed decoder admits fast decoding, with the same decoding complexity order as that of the reference scheme based on Complex Field Network Coding (CFNC). Simulation results indicate that the proposed PNC scheme offers a large gain over the CFNC scheme.

The design of modulation schemes for the physical layer network-coded two-way MIMO relaying scenario is considered, with the denoise-and-forward protocol which employs two phases: Multiple Access phase and Broadcast phase. It is shown that for MIMO two-way relaying, the minimum distance of the effective constellation at the relay becomes zero when all the rows of the channel fade coefficient matrix belong to a finite number of vector subspaces referred to as the singular fade subspaces. The singular fade subspaces can be classified into two kinds based on whether their harmful effects can be removed or not: (i) the removable and (ii) the non-removable singular fade subspaces. It is shown that network coding maps obtained by the completion of appropriate partially filled Latin Rectangles can remove the harmful effects of all the removable singular fade subspaces. For 2λ-PSK signal set, the removable and non-removable singular fade subspaces are characterized and, it is shown that the number of non-removable singular fade subspaces is a small fraction of the total number of singular fade subspaces and this fraction tends to zero as the constellation size tends to infinity. The Latin Rectangles for the case when the end nodes use different number of antennas are shown to be obtainable from the Latin Squares for the case when they use the same number of antennas. Also, the network coding maps which remove all the removable singular singular fade subspaces are shown to be obtainable from a small set of Latin Squares. The removal of all the singular fade subspaces by properly choosing the network coding map, provides a gain of 5.5 dB over the conventional Exclusive-OR network coding, in a Rayleigh fading scenario with 2 antennas at the end nodes and one antenna at the relay node, for 4-PSK signal set.

The design of modulation schemes for the physical layer network-coded two-way relay network has been studied in literature and it is known that every network coding map that satisfies the exclusive law is representable by a Latin Square. This relationship has been used to get network coding maps satisfying the exclusive law. But, only the scenario in which the end nodes use M-PSK signal sets has been addressed previously. In this paper, we address the case in which the end nodes use M-QAM signal sets. In a fading scenario, for certain channel conditions γejθ, termed singular fade states, the end-to-end performance is greatly reduced. By formulating a procedure for finding the exact number of singular fade states for QAM, we show that square QAM signal sets give lesser number of singular fade states compared to PSK signal sets. This reduces the computational complexity at the relay node. It is shown that the criterion for partitioning the complex plane, for the purpose of using a particular network code for a particular fade state, is different from that used for M-PSK. Using a modified criterion, we describe a procedure to analytically partition the complex plane representing the channel condition. We show that when M-QAM (M >4) signal set is used, the conventional XOR network mapping fails to remove the ill effects of γejθ=1, which is a singular fade state for all signal sets of arbitrary size. We show that a doubly block circulant Latin Square removes this singular fade state for M-QAM. Finally it is shown that M-QAM gives superior performance over M-PSK.

A Finite Feedback Scheme (FFS) for a quasi-static MIMO block fading channel with finite N-ary delay-free noise-free feedback consists of N Space-Time Block Codes (STBCs) at the transmitter, one corresponding to each possible value of feedback, and a function at the receiver that generates N-ary feedback. A number of FFSs are available in the literature that provably attain full-diversity. However, there is no known full-diversity criterion that universally applies to all FFSs. In this paper a universal necessary condition for any FFS to achieve full-diversity is given, and based on this criterion the notion of Feedback-Transmission duration optimal (FT-optimal) FFSs is introduced, which are schemes that use minimum amount of feedback N for the given transmission duration T, and minimum T for the given N to achieve full-diversity. When there is no feedback (N = 1) an FT-optimal scheme consists of a single STBC, and the proposed condition reduces to the well known necessary and sufficient condition for an STBC to achieve fulldiversity. Also, a sufficient criterion for full-diversity is given for FFSs in which the component STBC yielding the largest minimum Euclidean distance is chosen, using which full-rate (Ntcomplex symbols per channel use) full-diversity FT-optimal schemes are constructed for all Nt> 1. These are the first full-rate full-diversity FFSs reported in the literature for Tt. Simulation results show that the new schemes have the best error performance among all known FFSs.

For a family of Space-Time Block Codes (STBCs) C1, C2, ... , with increasing number of transmit antennas Ni, with rates Ri complex symbols per channel use, i = 1, 2, ... , we introduce the notion of asymptotic normalized rate which we define as limi→∞Ri/Ni, and we say that a family of STBCs is Ri asymptotically-good if its asymptotic normalized rate is non-zero, i.e., when the rate scales as a non-zero fraction of the number of transmit antennas. An STBC C is said to be g-group decodable, g ≥ 2, if the information symbols encoded by it can be partitioned into g groups, such that each group of symbols can be ML decoded independently of the others. In this paper we construct full-diversity g-group decodable codes with rates greater than one complex symbol per channel use for all g ≥ 2. Specifically, we construct delay-optimal, g-group decodable codes for number of transmit antennas Ntthat are a multiple of g2[g-1/2]with rate Nt/g2g-1+ g2-g/2Nt. Using these new codes as building blocks, we then construct non-delay-optimal g-group decodable codes with rate roughly g times that of the delay-optimal codes, for number of antennas Ntthat are a multiple of 2[g-1/2], with delay gNtand rate Nt/2g-1+g-1/2NtFor each g ≥ 2, the new delay-optimal and nondelay-optimal families of STBCs are both asymptotically-good, with the latter family having the largest asymptotic normalized rates among all known families of multigroup decodable codes with delay T ≤ gNt. Also, for g ≥ 3, these are the first instances of g-group decodable codes with rates greater than 1 reported in the literature.

A transform approach to network coding was introduced by Bavirisetti et al. (arXiv:1103.3882v4 [cs.IT]) as a tool to view wireline networks with delays as k-instantaneous networks, for some large k. When the local encoding kernels (LEKs) of the network are varied with every time block of length k > 1, the network is said to use block time varying LEKs. In this work, we propose a Precoding Based Network Alignment (PBNA) scheme based on transform approach and block time varying LEKs for three-source three-destination multiple unicast network with delays (3-S 3-D MUN-D). In a recent work, Meng et al. (arXiv:1202.3405v1 [cs.IT]) reduced the infinite set of sufficient conditions for feasibility of PBNA in a three-source three-destination instantaneous multiple unicast network as given by Das et al. (arXiv:1008.0235v1 [cs.IT]) to a finite set and also showed that the conditions are necessary. We show that the conditions of Meng et al. are also necessary and sufficient conditions for feasibility of PBNA based on transform approach and block time varying LEKs for 3-S 3-D MUN-D.

We consider the wireless two-way relay channel, in which two-way data transfer takes place between the end nodes with the help of a relay. For the Denoise-And-Forward (DNF) protocol, it was shown by Koike-Akino et. al. that adaptively changing the network coding map used at the relay greatly reduces the impact of Multiple Access interference at the relay. The harmful effect of the deep channel fade conditions can be effectively mitigated by a proper choice of these network coding maps at the relay. Alternatively, in this paper we propose a Distributed Space Time Coding (DSTC) scheme, which effectively removes most of the deep fade channel conditions at the transmitting nodes itself without any CSIT and without any need to adaptively change the network coding map used at the relay. It is shown that the deep fades occur when the channel fade coefficient vector falls in a finite number of vector subspaces of ℂ2, which are referred to as the singular fade subspaces. DSTC design criterion referred to as the singularity minimization criterion under which the number of such vector subspaces are minimized is obtained. Also, a criterion to maximize the coding gain of the DSTC is obtained. Explicit low decoding complexity DSTC designs which satisfy the singularity minimization criterion and maximize the coding gain for QAM and PSK signal sets are provided. Simulation results show that at high Signal to Noise Ratio, the DSTC scheme provides large gains when compared to the conventional Exclusive-OR network code and performs slightly better than the adaptive network coding scheme proposed by Koike-Akino et. al.

In the design of modulation schemes for the physical layer network-coded two way relaying scenario with two phases (Multiple access (MA) Phase and Broadcast (BC) Phase), it was observed by Koike-Akino et al. that adaptively changing the network coding map used at the relay according to the channel conditions greatly reduces the impact of multiple access interference and all these network coding maps should satisfy a requirement called the exclusive law. In [11] the case in which the end nodes use M-PSK signal sets is extensively studied using Latin Squares. This paper deals with the case in which the end nodes use square M-QAM signal sets. In a fading scenario, for certain channel conditions, termed singular fade states, the MA phase performance is greatly reduced. We show that the square QAM signal sets lead to lesser number of singular fade states compared to PSK signal sets. Because of this, the complexity at the relay is enormously reduced. Moreover lesser number of overhead bits are required in the BC phase. We find the number of singular fade states for PAM and QAM signal sets used at the end nodes. The fade state γℯjθ= 1 is a singular fade state for M-QAM for all values of M and it is shown that certain block circulant Latin Squares remove this singular fade state. Simulation results are presented to show that QAM signal set perform better than PSK.

In this work, interference alignment for a class of Gaussian interference networks with general message demands, having line of sight (LOS) channels, at finite powers is considered. We assume that each transmitter has one independent message to be transmitted and the propagation delays are uniformly distributed between 0 and (L - 1) (L >; 0). If receiver-j, j ∈{1,2,..., J}, requires the message of transmitter-i, i ∈ {1, 2, ..., K}, we say (i, j) belongs to a connection. A class of interference networks called the symmetrically connected interference network is defined as a network where, the number of connections required at each transmitter-i is equal to ctfor all i and the number of connections required at each receiver-j is equal to crfor all j, for some fixed positive integers ctand cr. For such networks with a LOS channel between every transmitter and every receiver, we show that an expected sum-spectral efficiency (in bits/sec/Hz) of at least K/(e+c1-1)(ct+1) (ct/ct+1)ctlog2 (1+min(i, j)∈c|hi, j|2P/WN0) can be achieved as the number of transmitters and receivers tend to infinity, i.e., K, J →∞ where, C denotes the set of all connections, hijis the channel gain between transmitter-i and receiver-j, P is the average power constraint at each transmitter, W is the bandwidth and N0W is the variance of Gaussian noise at each receiver. This means that, for an LOS symmetrically connected interference network, at any finite power, the total spectral efficiency can grow linearly with K as K, J →∞. This is achieved by extending the time domain interference alignment scheme proposed by Grokop et al. for the k-user Gaussian interference channel to interference networks.

The algebraic formulation for linear network coding in acyclic networks with each link having an integer delay is well known. Based on this formulation, for a given set of connections over an arbitrary acyclic network with integer delay assumed for the links, the output symbols at the sink nodes at any given time instant is a Fq-linear combination of the input symbols across different generations, where Fqdenotes the field over which the network operates. We use finite-field discrete Fourier transform (DFT) to convert the output symbols at the sink nodes at any given time instant into a Fq-linear combination of the input symbols generated during the same generation. We call this as transforming the acyclic network with delay into n-instantaneous networks (n is sufficiently large). We show that under certain conditions, there exists a network code satisfying sink demands in the usual (non-transform) approach if and only if there exists a network code satisfying sink demands in the transform approach. Furthermore, assuming time invariant local encoding kernels, we show that the transform method can be employed to achieve half the rate corresponding to the individual source-destination mincut (which are assumed to be equal to 1) for some classes of three-source three-destination multiple unicast network with delays using alignment strategies when the zero-interference condition is not satisfied.

The design of modulation schemes for the physical layer network-coded two-way MIMO relaying scenario is considered, with the denoise-and-forward (DNF) protocol which employs two phases: Multiple access (MA) phase and Broadcast (BC) phase. It is shown that for MIMO two-way relaying, deep fade occurs at the relay when the row space of the channel fade coefficient matrix is a subspace of a finite number of vector subspaces which are referred to as the singular fade subspaces. It is shown that proper choice of network coding map obtained by the completion of appropriate partially filled Latin Rectangle can remove most of the singular fade subspaces, referred to as the removable singular fade subspaces. For 2λ-PSK signal set, the number of removable and non-removable singular fade subspaces are obtained analytically and it is shown that the number of non-removable singular fade subspaces is a small fraction of the total number of singular fade subspaces. The Latin Rectangles for the case when the end nodes use different number of antennas are shown to be obtainable from the Latin Squares for the case when they use the same number of antennas, irrespective of the number of antennas at the relay. For 2λ-PSK signal set, the singular fade subspaces which are removed by the conventional XOR network code are identified. Also, using the notions of isotopic and transposed Latin Squares, the network coding maps which remove all the removable singular singular fade subspaces are shown to be obtainable from a small set of Latin Squares.

The problem of designing good Space-Time Block Codes (STBCs) with low maximum-likelihood (ML) decoding complexity has gathered much attention in the literature. All the known low ML decoding complexity techniques utilize the same approach of exploiting either the multigroup decodable or the fast-decodable (conditionally multigroup decodable) structure of a code. We refer to this well known technique of decoding STBCs as Conditional ML (CML) decoding. In [1], we introduced a framework to construct ML decoders for STBCs based on the Generalized Distributive Law (GDL) and the Factor-graph based Sum-Product Algorithm, and showed that for two specific families of STBCs, the Toepltiz codes and the Overlapped Alamouti Codes (OACs), the GDL based ML decoders have strictly less complexity than the CML decoders. In this paper, we introduce a `traceback' step to the GDL decoding algorithm of STBCs, which enables roughly 4 times reduction in the complexity of the GDL decoders proposed in [1]. Utilizing this complexity reduction from `traceback', we then show that for any STBC (not just the Toeplitz and Overlapped Alamouti Codes), the GDL decoding complexity is strictly less than the CML decoding complexity. For instance, for any STBC obtained from Cyclic Division Algebras that is not multigroup or conditionally multigroup decodable, the GDL decoder provides approximately 12 times reduction in complexity compared to the CML decoder. Similarly, for the Golden code, which is conditionally multigroup decodable, the GDL decoder is only about half as complex as the CML decoder.

A Space-Time Block Code (STBC) is said to be multigroup ML decodable if the information symbols encoded by it can be partitioned into two or more groups, such that each group of symbols can be ML decoded independently of the other symbol groups. In this paper, we show that the upper triangular matrix R encountered during the sphere decoding of a linear dispersion STBC can be rank-deficient even when the rate of the code is less than the minimum of the number of transmit and receive antennas. We then show that all known families of high rate (rate greater than 1) multigroup ML decodable codes have rank-deficient R matrix, even when the rate is less than the number of transmit and receive antennas, and this rank-deficiency problem arises only when the number of receive antennas is strictly less than the number of transmit antennas. Unlike the codes with full-rank R matrix, the average sphere decoding complexity of the STBCs whose R matrix is rank-deficient is polynomial in the constellation size, and hence is high. We derive the sphere decoding complexity of most of the known high rate multigroup ML decodable codes, and show that for each code, the complexity is a decreasing function of the number of receive antennas.

Matroidal networks were introduced by Dougherty et al. and have been well studied in the recent past. It was shown that a network has a scalar linear network coding solution if and only if it is matroidal associated with a representable matroid. The current work attempts to establish a connection between matroid theory and network-error correcting codes. In a similar vein to the theory connecting matroids and network coding, we abstract the essential aspects of network-error correcting codes to arrive at the definition of a matroidal error correcting network. An acyclic network (with arbitrary sink demands) is then shown to possess a scalar linear error correcting network code if and only if it is a matroidal error correcting network associated with a representable matroid. Therefore, constructing such network-error correcting codes implies the construction of certain representable matroids that satisfy some special conditions, and vice versa.

For an nttransmit, nrreceive antenna (nt× nr) MIMO system with quasi-static Rayleigh fading, it was shown by Elia et al. that space-time block code-schemes (STBC-schemes) which have the non-vanishing determinant (NVD) property and are based on minimal-delay STBCs (STBC block length equals nt) with a symbol rate of ntcomplex symbols per channel use (rate-ntSTBC) are diversity-multiplexing gain tradeoff (DMT)-optimal for arbitrary values of nr. Further, explicit linear STBC-schemes (LSTBC-schemes) with the NVD property were also constructed. However, for asymmetric MIMO systems (where nrt), with the exception of the Alamouti code-scheme for the 2×1 system and rate-1, diagonal STBC-schemes with NVD for an nt×1 system, no known minimal-delay, rate-nrLSTBC-scheme has been shown to be DMT-optimal. In this paper, we first obtain an enhanced sufficient criterion for an STBC-scheme to be DMT optimal and using this result, we show that for certain asymmetric MIMO systems, many well-known LSTBC-schemes which have low ML-decoding complexity are DMT-optimal, a fact that was unknown hitherto.

For transmission over the two-user Gaussian Multiple Access Channel with fading and finite constellation at the inputs, we propose a scheme which uses only quantized knowledge of fade state at users with the feedback overhead being nominal. One of the users rotates its constellation without varying the transmit power to adapt to the existing channel conditions, in order to meet certain pre-determined minimum Euclidean distance requirement in the equivalent constellation at the destination. The optimal modulation scheme has been described for the case when both the users use symmetric M-PSK constellations at the input, where M = 2λ, λ being a positive integer. The strategy has been illustrated by considering examples where both the users use QPSK signal set at the input. It is shown that the proposed scheme has considerable better error performance compared to the conventional non-adaptive scheme, at the cost of a feedback overhead of just [log2(M2/8 - M/4 + 2)] + 1 bits, for the M-PSK case.

The analysis of modulation schemes for the physical layer network-coded two way relaying scenario is presented which employs two phases: Multiple access (MA) phase and Broadcast (BC) phase. Depending on the signal set used at the end nodes, the minimum distance of the effective constellation seen at the relay becomes zero for a finite number of channel fade states referred as the singular fade states. The singular fade states fall into the following two classes: (i) the ones which are caused due to channel outage and whose harmful effect cannot be mitigated by adaptive network coding called the non-removable singular fade states and (ii) the ones which occur due to the choice of the signal set and whose harmful effects can be removed called the removable singular fade states. In this paper, we derive an upper bound on the average end-to-end Symbol Error Rate (SER), with and without adaptive network coding at the relay, for a Rician fading scenario. It is shown that without adaptive network coding, at high Signal to Noise Ratio (SNR), the contribution to the end-to-end SER comes from the following error events which fall as SNR-1: the error events associated with the removable and nonremovable singular fade states and the error event during the BC phase. In contrast, for the adaptive network coding scheme, the error events associated with the removable singular fade states fall as SNR-2, thereby providing a coding gain over the case when adaptive network coding is not used. Also, it is shown that for a Rician fading channel, the error during the MA phase dominates over the error during the BC phase. Hence, adaptive network coding, which improves the performance during the MA phase provides more gain in a Rician fading scenario than in a Rayleigh fading scenario. Furthermore, it is shown that for large Rician factors, among those removable singular fade states which have the same magnitude, those which have the least absolute value of the phase angle alone contribute dominantly to the end-to-end SER and it is sufficient to remove the effect of only such singular fade states.

The design of modulation schemes for the physical layer network-coded three-way wireless relaying scenario is considered. The protocol employs two phases: Multiple Access (MA) phase and Broadcast (BC) phase with each phase utilizing one channel use. For the two-way relaying scenario, it was observed by Koike-Akino et al. [4], that adaptively changing the network coding map used at the relay according to the channel conditions greatly reduces the impact of multiple access interference which occurs at the relay during the MA phase and all these network coding maps should satisfy a requirement called exclusive law. This paper does the equivalent for the three-way relaying scenario. We show that when the three users transmit points from the same 4-PSK constellation, every such network coding map that satisfies the exclusive law can be represented by a Latin Cube of Second Order. The network code map used by the relay for the BC phase is explicitly obtained and is aimed at reducing the effect of interference at the MA stage.

A decode and forward protocol based Trellis Coded Modulation (TCM) scheme for the half-duplex relay channel, in a Rayleigh fading environment, is presented. The proposed scheme can achieve any spectral efficiency greater than or equal to one bit per channel use (bpcu). A near-ML decoder for the suggested TCM scheme is proposed. It is shown that the high Signal to Noise Ratio (SNR) performance of this near-ML decoder approaches the performance of the optimal ML decoder. Based on the derived Pair-wise Error Probability (PEP) bounds, design criteria to maximize the diversity and coding gains are obtained. Simulation results show a large gain in SNR for the proposed TCM scheme over uncoded communication as well as the direct transmission without the relay.

In this paper, we employ message passing algorithms over graphical models to jointly detect and decode symbols transmitted over large multiple-input multiple-output (MIMO) channels with low density parity check (LDPC) coded bits. We adopt a factor graph based technique to integrate the detection and decoding operations. A Gaussian approximation of spatial interference is used for detection. This serves as a low complexity joint detection/decoding approach for large dimensional MIMO systems coded with LDPC codes of large block lengths. This joint processing achieves significantly better performance than the individual detection and decoding scheme.

For the design of modulation schemes for the physical layer network-coded two way wireless relaying, it was observed by Koike-Akino et al. that adaptively changing the network coding map used at the relay according to the channel conditions greatly reduces the impact of multiple access interference which occurs at the relay during the MA Phase and all these network coding maps should satisfy a requirement called exclusive law. We extend this approach to an Accumulate-Compute and Forward protocol which employs two phases: Multiple Access (MA) phase consisting of two channel uses with independent messages in each channel use, and Broadcast (BC) phase having one channel use. Assuming that the two users transmit points from the same 4-PSK constellation, every such network coding map that satisfies the exclusive law can be represented by a Latin Square with side 16, and conversely, this relationship can be used to get the network coding maps satisfying the exclusive law. Two methods of obtaining this network coding map to be used at the relay are discussed. Using the structural properties of the Latin Squares for a given set of parameters, the problem of finding all the required maps is reduced to finding a small set of maps. Having obtained all the Latin Squares, the set of all possible channel realizations is quantized, depending on which one of the Latin Squares obtained optimizes the performance. The quantization thus obtained, is shown to be the same as the one obtained in [7] for the 2-stage bidirectional relaying.

The design of modulation schemes for the physical layer network-coded two way relaying scenario is considered with the protocol which employs two phases: Multiple access (MA) Phase and Broadcast (BC) phase. It was observed by Koike-Akino et al. that adaptively changing the network coding map used at the relay according to the channel conditions greatly reduces the impact of multiple access interference which occurs at the relay during the MA phase. In other words, the set of all possible channel realizations (the complex plane) is quantized into a finite number of regions, with a specific network coding map giving the best performance in a particular region. We obtain such a quantization analytically for the case when M-PSK (for M any power of 2) is the signal set used during the MA phase. We show that the complex plane can be classified into two regions: a region in which any network coding map which satisfies the so called exclusive law gives the same best performance and a region in which the choice of the network coding map affects the performance, which is further quantized based on the choice of the network coding map which optimizes the performance. The quantization thus obtained analytically, leads to the same as the one obtained using computer search for 4-PSK signal set by Koike-Akino et al., for the specific value of M = 4.

The design of modulation schemes for the physical layer network-coded two way relaying scenario is considered with the protocol which employs two phases: Multiple access (MA) Phase and Broadcast (BC) Phase. It was observed by Koike-Akino et al. that adaptively changing the network coding map used at the relay according to the channel conditions greatly reduces the impact of multiple access interference which occurs at the relay during the MA Phase and all these network coding maps should satisfy a requirement called the exclusive law. We show that every network coding map that satisfies the exclusive law is representable by a Latin Square and conversely, and this relationship can be used to get the network coding maps satisfying the exclusive law. Using the structural properties of the Latin Squares for a given set of parameters, the problem of finding all the required maps is reduced to finding a small set of maps for M-PSK constellations. This is achieved using the notions of isotopic and transposed Latin Squares. Furthermore, the channel conditions for which the bit-wise XOR will perform well is analytically obtained which holds for all values of M (for M any power of 2). We illustrate these results for the case where both the end users use QPSK constellation.

The maximal rate of a nonsquare complex orthogonal design forntransmit antennas is [1/2]+[1/(n)] ifnis even and [1/2]+[1/(n+1)] ifnis odd and the codes have been constructed for allnby Liang (2003) and Lu (2005) to achieve this rate. A lower bound on the decoding delay of maximal-rate complex orthogonal designs has been obtained by Adams (2007) and it is observed that Liang's construction achieves the bound on delay fornequal to 1 and 3 modulo 4 while Lu et al.'s construction achieves the bound forn=0 , 1, 3 mod 4. Forn=2 mod 4, Adams (2010) have shown that the minimal decoding delay is twice the lower bound, in which case, both Liang's and Lu et al.'s construction achieve the minimum decoding delay. For large value ofn, it is observed that the rate is close to half and the decoding delay is very large. A class of rate-[1/2] codes with low decoding delay for allnhas been constructed by Tarokh (1999). In this paper, another class of rate-[1/2] codes is constructed for allnin which case the decoding delay is half the decoding delay of the rate-[1/2] codes given by Tarokh This is achieved by giving first a general construction of square real orthogonal designs which includes as special cases the well-known constructions of Adams, Lax, and Phillips and the construction of Geramita and Pullman, and then making use of it to obtain the desired rate-[1/2] codes. For the case of nine transmit antennas, the proposed rate-[1/2] code is shown to be of minimal delay. The proposed construction results in designs with zero entries which may have high peak-to-average power ratio and it is shown that by appropriate postmultiplication, a design with no zero entry can be obtained with no change in the code parameters.

In the two-user Gaussian Strong Interference Channel (GSIC) with finite constellation inputs, it is known that relative rotation between the constellations of the two users enlarges the Constellation Constrained (CC) capacity region. In this paper, a metric for finding the approximate angle of rotation to maximally enlarge the CC capacity is presented. It is shown that for some portion of the Strong Interference (SI) regime, with Gaussian input alphabets, the FDMA rate curve touches the capacity curve of the GSIC. Even as the Gaussian alphabet FDMA rate curve touches the capacity curve of the GSIC, at high powers, with both the users using the same finite constellation, we show that the CC FDMA rate curve lies strictly inside the CC capacity curve for the constellations BPSK, QPSK, 8-PSK, 16-QAM and 64-QAM. It is known that, with Gaussian input alphabets, the FDMA inner-bound at the optimum sum-rate point is always better than the simultaneous-decoding inner-bound throughout the Weak Interference (WI) regime. For a portion of the WI regime, it is shown that, with identical finite constellation inputs for both the users, the simultaneous-decoding inner-bound enlarged by relative rotation between the constellations can be strictly better than the FDMA inner-bound.

Low-complexity near-optimal detection of signals in MIMO systems with large number (tens) of antennas is getting increased attention. In this paper, first, we propose a variant of Markov chain Monte Carlo (MCMC) algorithm which i) alleviates the stalling problem encountered in conventional MCMC algorithm at high SNRs, and ii) achieves near-optimal performance for large number of antennas (e.g., 16×16, 32×32, 64×64 MIMO) with 4-QAM. We call this proposed algorithm as randomized MCMC (R-MCMC) algorithm. Second, we propose an other algorithm based on a random selection approach to choose candidate vectors to be tested in a local neighborhood search. This algorithm, which we call as randomized search (RS) algorithm, also achieves near-optimal performance for large number of antennas with 4-QAM. The complexities of the proposed R-MCMC and RS algorithms are quadratic/sub-quadratic in number of transmit antennas, which are attractive for detection in large-MIMO systems. We also propose message passing aided R-MCMC and RS algorithms, which are shown to perform well for higher-order QAM.

For a family/sequence of Space-Time Block Codes (STBCs) C1, C2,⋯, with increasing number of transmit antennas Ni, with rates Ricomplex symbols per channel use (cspcu), i = 1,2,⋯, the asymptotic normalized rate is defined as limi→∞Ri/Ni. A family of STBCs is said to be asymptotically-good if the asymptotic normalized rate is non-zero, i.e., when the rate scales as a non-zero fraction of the number of transmit antennas, and the family of STBCs is said to be asymptotically-optimal if the asymptotic normalized rate is 1, which is the maximum possible value. In this paper, we construct a new class of full-diversity STBCs that have the least maximum-likelihood (ML) decoding complexity among all known codes for any number of transmit antennas N>;1 and rates R>;1 cspcu. For a large set of (R,N) pairs, the new codes have lower ML decoding complexity than the codes already available in the literature. Among the new codes, the class of full-rate codes (R=N) are asymptotically-optimal and fast-decodable, and for N>;5 have lower ML decoding complexity than all other families of asymptotically-optimal, fast-decodable, full-diversity STBCs available in the literature. The construction of the new STBCs is facilitated by the following further contributions of this paper: (i) Construction of a new class of asymptotically-good, full-diversity multigroup ML decodable codes, that not only includes STBCs for a larger set of antennas, but also either matches in rate or contains as a proper subset all other high-rate or asymptotically-good, delay-optimal, multigroup ML decodable codes available in the literature. (ii) Construction of a new class of fast-group-decodable codes (codes that combine the low ML decoding complexity properties of multigroup ML decodable codes and fast-decodable codes) for all even number of transmit antennas and rates 1 <; R ≤ 5/4. (iii) Given a design with full-rank linear dispersion matrices, we show that a full-diversity STBC can be constructed from this design by encoding the real symbols independently using only regular PAM constellations.

Recently in, a framework was given to construct low ML decoding complexity Space-Time Block Codes (STBCs) via codes over the finite field F4. In this paper, we construct new full-diversity STBCs with cubic shaping property and low ML decoding complexity via codes over F4for number of transmit antennas N = 2m, m >; 1, and rates R >; 1 complex symbols per channel use. The new codes have the least ML decoding complexity among all known codes for a large set of (N, R) pairs. The new full-rate codes of this paper (R = N) are not only information-lossless and fully diverse but also have the least known ML decoding complexity in the literature. For N ≥ 4, the new full-rate codes are the first instances of full-diversity, information-lossless STBCs with low ML decoding complexity. We also give a sufficient condition for STBCs obtainable from codes over F4to have cubic shaping property, and a sufficient condition for any design to give rise to a full-diversity STBC when the symbols are encoded using rotated square QAM constellations.

It has been shown recently that the maximum rate of a 2-real-symbol (single-complex-symbol) maximum likelihood (ML) decodable, square space-time block codes (STBCs) with unitary weight matrices is 2a/2acomplex symbols per channel use (cspcu) for 2anumber of transmit antennas [1]. These STBCs are obtained from Unitary Weight Designs (UWDs). In this paper, we show that the maximum rates for 3- and 4-real-symbol (2-complex-symbol) ML decodable square STBCs from UWDs, for 2atransmit antennas, are 3(a-1)/2aand 4(a-1)/2acspcu, respectively. STBCs achieving this maximum rate are constructed. A set of sufficient conditions on the signal set, required for these codes to achieve full-diversity are derived along with expressions for their coding gain.

Decoding of linear space-time block codes (STBCs) with sphere-decoding (SD) is well known. A fast-version of the SD known as fast sphere decoding (FSD) has been recently studied by Biglieri, Hong and Viterbo. Viewing a linear STBC as a vector space spanned by its defining weight matrices over the real number field, we define a quadratic form (QF), called the Hurwitz-Radon QF (HRQF), on this vector space and give a QF interpretation of the FSD complexity of a linear STBC. It is shown that the FSD complexity is only a function of the weight matrices defining the code and their ordering, and not of the channel realization (even though the equivalent channel when SD is used depends on the channel realization) or the number of receive antennas. It is also shown that the FSD complexity is completely captured into a single matrix obtained from the HRQF. Moreover, for a given set of weight matrices, an algorithm to obtain a best ordering of them leading to the least FSD complexity is presented. The well known classes of low FSD complexity codes (multi-group decodable codes, fast decodable codes and fast group decodable codes) are presented in the framework of HRQF.

Recently, Guo and Xia introduced low complexity decoders called Partial Interference Cancellation (PIC) and PIC with Successive Interference Cancellation (PIC-SIC), which include the Zero Forcing (ZF) and ZF-SIC receivers as special cases, for point-to-point MIMO channels. In this paper, we show that PIC and PIC-SIC decoders are capable of achieving the full cooperative diversity available in wireless relay networks. We give sufficient conditions for a Distributed Space-Time Block Code (DSTBC) to achieve full diversity with PIC and PIC-SIC decoders and construct a new class of DSTBCs with low complexity full-diversity PIC-SIC decoding using complex orthogonal designs. The new class of codes includes a number of known full-diversity PIC/PIC-SIC decodable Space-Time Block Codes (STBCs) constructed for point-to-point channels as special cases. The proposed DSTBCs achieve higher rates (in complex symbols per channel use) than the multigroup ML decodable DSTBCs available in the literature. Simulation results show that the proposed codes have better bit error rate performance than the best known low complexity, full-diversity DSTBCs.

Recently, Ebrahimi and Fragouli proposed an algorithm to construct scalar network codes using small fields (and vector network codes of small lengths) satisfying multicast constraints in a given single-source, acyclic network. The contribution of this paper is two fold. Primarily, we extend the scalar network coding algorithm of Ebrahimi and Fragouli (henceforth referred to as the EF algorithm) to block network-error correction. Existing construction algorithms of block network-error correcting codes require a rather large field size, which grows with the size of the network and the number of sinks, and thereby can be prohibitive in large networks. We give an algorithm which, starting from a given network-error correcting code, can obtain another network code using a small field, with the same error correcting capability as the original code. Our secondary contribution is to improve the EF Algorithm itself. The major step in the EF algorithm is to find a least degree irreducible polynomial which is coprime to another large degree polynomial. We suggest an alternate method to compute this coprime polynomial, which is faster than the brute force method in the work of Ebrahimi and Fragouli.

Precoding for multiple-input, multiple-output (MIMO) antenna systems is considered with perfect channel knowledge available at both the transmitter and the receiver. For 2 transmit antennas and QAM constellations, a precoder that is approximately optimal (with respect to the minimum Euclidean distance between points in the received signal space) among real-valued precoders based on the singular value decomposition (SVD) of the channel is proposed. The proposed precoder is obtainable easily for arbitrary QAM constellations, unlike the known complex-valued optimal precoder by Collin et al. for 2 transmit antennas which is in existence for 4-QAM alone and is extremely hard to obtain for larger QAM constellations. The proposed precoding scheme is extended to higher number of transmit antennas on the lines of the E-dminprecoder for 4-QAM by Vrigneau et al.. The proposed precoder has an ML-decoding complexity of O(√M) as against the E-dminprecoder's complexity of O(M√M) (M = 4). Compared with the recently proposed X- and Y - precoders, the error performance of the proposed precoder is significantly better. The proposed precoder provides full-diversity for QAM constellations and this is supported by simulation plots of the word error probability for 2 × 2, 4 × 4 and 8 × 8 systems.

The concept of interference alignment when extended to three-source three-destination instantaneous multiple unicast network for the case where, each source-destination pair has a min-cut of 1 and zero-interference conditions are not satisfied, is known to achieve a rate of half for every source-destination pair under certain conditions. This was called network alignment. We generalize this concept of network alignment to three-source three-destination multiple unicast (3S-3D-MU) networks with delays, without making use of memory at the intermediate nodes (i.e., nodes other than the sources and destinations) and using time varying Local Encoding Kernels (LEKs). This achieves half the rate corresponding to the individual source-destination min-cut for some classes of 3S-3D-MU network with delays which do not satisfy the zero-interference conditions.

The Generalized Distributive Law (GDL) is a message passing algorithm which can efficiently solve a certain class of computational problems, and includes as special cases the Viterbi's algorithm, the BCJR algorithm, the Fast-Fourier Transform, Turbo and LDPC decoding algorithms. In this paper GDL based maximum-likelihood (ML) decoding of Space-Time Block Codes (STBCs) is introduced and a sufficient condition for an STBC to admit low GDL decoding complexity is given. Fast-decoding and multigroup decoding are the two algorithms used in the literature to ML decode STBCs with low complexity. An algorithm which exploits the advantages of both these two is called Conditional ML (CML) decoding. It is shown in this paper that the GDL decoding complexity of any STBC is upper bounded by its CML decoding complexity, and that there exist codes for which the GDL complexity is strictly less than the CML complexity. Explicit examples of two such families of STBCs is given in this paper. Thus the CML is in general suboptimal in reducing the ML decoding complexity of a code, and one should design codes with low GDL complexity rather than low CML complexity.

Problems related to network coding for acyclic, instantaneous networks (where the edges of the acyclic graph representing the network are assumed to have zero-delay) have been extensively dealt with in the recent past. The most prominent of these problems include (a) the existence of network codes that achieve maximum rate of transmission, (b) efficient network code constructions, and (c) field size issues. In practice, however, networks have transmission delays. In network coding theory, such networks with transmission delays are generally abstracted by assuming that their edges have integer delays. Using enough memory at the nodes of an acyclic network with integer delays can effectively simulate instantaneous behavior, which is probably why only acyclic instantaneous networks have been primarily focused on thus far. However, nulling the effect of the network delays are not always uniformly advantageous, as we will show in this work. Essentially, we elaborate on issues ((a), (b) and (c) above) related to network coding for acyclic networks with integer delays, and show that using the delay network as is (without adding memory) turns out to be advantageous, disadvantageous or immaterial, depending on the topology of the network and the problem considered i.e., (a), (b) or (c).

The capacity region of the 3-user Gaussian Interference Channel (GIC) with mixed strong-very strong interference was established in [1]. The mixed strong-very strong interference conditions considered in [1] correspond to the case where, at each receiver, one of the interfering signals is strong and the other is very strong. In this paper, we derive the capacity region of K-user (K ≥ 3) Discrete Memoryless Interference Channels (DMICs) with a mixed strong-very strong interference. This corresponds to the case where, at each receiver one of the interfering signals is strong and the other (K - 2) interfering signals are very strong. This includes, as a special case, the 3-user DMIC with mixed strong-very strong interference. The proof is specialized to the 3-user GIC case and hence an alternative derivation for the capacity region of the 3-user GIC with mixed strong-very strong interference is provided.

Constellation Constrained (CC) capacity regions of two-user Gaussian Multiple Access Channels (GMAC) have been recently reported, wherein introducing appropriate rotation between the constellations of the two users is shown to maximally enlarge the CC capacity region. Such a Non-Orthogonal Multiple Access (NO-MA) method of enlarging the CC capacity region is referred to as Constellation Rotation (CR) scheme. In this paper, we propose a novel NO-MA technique called Constellation Power Allocation (CPA) scheme to enlarge the CC capacity region of two-user GMAC. We show that the CPA scheme offers CC sum capacities equal (at low SNR values) or close (at high SNR values) to those offered by the CR scheme with reduced ML decoding complexity for some QAM constellations. For the CR scheme, code pairs approaching the CC sum capacity are known only for the class of PSK and PAM constellations but not for QAM constellations. In this paper, we design code pairs with the CPA scheme to approach the CC sum capacity for 16-QAM constellations. Further, the CPA scheme used for two-user GMAC with random phase offsets is shown to provide larger CC sum capacities at high SNR values compared to the CR scheme.

In the two-user Gaussian Strong Interference Channel (GSIC) with finite constellation inputs, it is known that relative rotation between the constellations of the two users enlarges the Constellation Constrained (CC) capacity region. In this paper, a metric for finding the approximate angle of rotation (with negligibly small error) to maximally enlarge the CC capacity for the two-user GSIC is presented. In the case of Gaussian input alphabets with equal powers for both the users and the modulus of both the cross-channel gains being equal to unity, it is known that the FDMA rate curve touches the capacity curve of the GSIC. It is shown that, with unequal powers for both the users also, when the modulus of one of the cross-channel gains being equal to one and the modulus of the other cross-channel gain being greater than or equal to one, the FDMA rate curve touches the capacity curve of the GSIC. On the contrary, it is shown that, under finite constellation inputs, with both the users using the same constellation, the FDMA rate curve strictly lies within (never touches) the enlarged CC capacity region throughout the strong-interference regime. This means that using FDMA it is impossible to go close to the CC capacity. It is well known that for the Gaussian input alphabets, the FDMA inner-bound, at the optimum sum-rate point, is always better than the simultaneous-decoding inner-bound throughout the weak-interference regime. For a portion of the weak interference regime, it is shown that with identical finite constellation inputs for both the users, the simultaneous-decoding inner-bound, enlarged by relative rotation between the constellations, is strictly better than the FDMA inner-bound.

In this letter, we are concerned with low-complexity detection in large multiple-input multiple-output (MIMO) systems with tens of transmit/receive antennas. Our new contributions in this letter are two-fold. First, we propose a low-complexity algorithm for large-MIMO detection based on a layered low-complexity local neighborhood search. Second, we obtain a lower bound on the maximum-likelihood (ML) bit error performance using the local neighborhood search. The advantages of the proposed ML lower bound are i) it is easily obtained for MIMO systems with large number of antennas because of the inherent low complexity of the search algorithm, ii) it is tight at moderate-to-high SNRs, and iii) it can be tightened at low SNRs by increasing the number of symbols in the neighborhood definition. The proposed detection algorithm based on the layered local neighborhood search achieves bit error performances which are quite close to this lower bound for large number of antennas and higher-order QAM.

Constellation Constrained (CC) capacity regions of two-user Single-Input Single-Output (SISO) Gaussian Multiple Access Channels (GMAC) are computed for several Non-Orthogonal Multiple Access schemes (NO-MA) and Orthogonal Multiple Access schemes (O-MA). For NO-MA schemes, a metric is proposed to compute the angle(s) of rotation between the input constellations such that the CC capacity regions are maximally enlarged. Further, code pairs based on Trellis Coded Modulation (TCM) are designed with PSK constellation pairs and PAM constellation pairs such that any rate pair within the CC capacity region can be approached. Such a NO-MA scheme which employs CC capacity approaching trellis codes is referred to as Trellis Coded Multiple Access (TCMA). Then, CC capacity regions of O-MA schemes such as Frequency Division Multiple Access (FDMA) and Time Division Multiple Access (TDMA) are also computed and it is shown that, unlike the Gaussian distributed continuous constellations case, the CC capacity regions with FDMA are strictly contained inside the CC capacity regions with TCMA. Hence, for finite constellations, a NO-MA scheme such as TCMA is better than FDMA and TDMA which makes NO-MA schemes worth pursuing in practice for two-user GMAC. Then, the idea of introducing rotations between the input constellations is used to construct Space-Time Block Code (STBC) pairs for two-user Multiple-Input Single-Output (MISO) fading MAC. The proposed STBCs are shown to have reduced Maximum Likelihood (ML) decoding complexity and information-losslessness property. Finally, STBC pairs with reduced sphere decoding complexity are proposed for two-user Multiple-Input Multiple-Output (MIMO) fading MAC.

Distributed space-time block codes (DSTBCs) from complex orthogonal designs (CODs) (both square and nonsquare), coordinate interleaved orthogonal designs (CIODs), and Clifford unitary weight designs (CUWDs) are known to lose their single-symbol ML decodable (SSD) property when used in two-hop wireless relay networks using amplify and forward protocol. For such networks, in this paper, three new classes of high rate, training-symbol embedded (TSE) SSD DSTBCs are constructed: TSE-CODs, TSE-CIODs, and TSE-CUWDs. The proposed codes include the training symbols inside the structure of the code which is shown to be the key point to obtain the SSD property along with the channel estimation capability. TSE-CODs are shown to offer full-diversity for arbitrary complex constellations and the constellations for which TSE-CIODs and TSE-CUWDs offer full-diversity are characterized. It is shown that DSTBCs from nonsquare TSE-CODs provide better rates (in symbols per channel use) when compared to the known SSD DSTBCs for relay networks. Important from the practical point of view, the proposed DSTBCs do not contain any zeros in their codewords and as a result, antennas of the relay nodes do not undergo a sequence of switch on/off transitions within every codeword, and, thus, avoid the antenna switching problem.

It is well known that the space-time block codes (STBCs) from complex orthogonal designs (CODs) are single-symbol decodable/symbol-by-symbol decodable (SSD). The weight matrices of the square CODs are all unitary and obtainable from the unitary matrix representations of Clifford Algebras when the number of transmit antennasnis a power of 2. The rate of the square CODs forn= 2ahas been shown to be [(a+1)/(2a)] complex symbols per channel use. However, SSD codes having unitary-weight matrices need not be CODs, an example being the minimum-decoding-complexity STBCs from quasi-orthogonal designs. In this paper, an achievable upper bound on the rate of any unitary-weight SSD code is derived to be [(a)/(2a-1)] complex symbols per channel use for 2aantennas, and this upper bound is larger than that of the CODs. By way of code construction, the interrelationship between the weight matrices of unitary-weight SSD codes is studied. Also, the coding gain of all unitary-weight SSD codes is proved to be the same for QAM constellations and conditions that are necessary for unitary-weight SSD codes to achieve full transmit diversity and optimum coding gain are presented.

In this paper, we give a new framework for constructing low ML decoding complexity space-time block codes (STBCs) using codes over the Klein groupK. Almost all known low ML decoding complexity STBCs can be obtained via this approach. New full-diversity STBCs with low ML decoding complexity and cubic shaping property are constructed, via codes overK, for number of transmit antennasN=2m,m≥ 1, and ratesR>; 1 complex symbols per channel use. WhenR=N, the new STBCs are information-lossless as well. The new class of STBCs have the least known ML decoding complexity among all the codes available in the literature for a large set of (N,R) pairs.

For annttransmit,nrreceive antenna system (nt×nrsystem), a full-rate space time block code (STBC) transmits at leastnmin=min(nt,nr) complex symbols per channel use. The well-known Golden code is an example of a full-rate, full-diversity STBC for two transmit antennas. Its ML-decoding complexity is of the order ofM2.5for squareM-QAM. The Silver code for two transmit antennas has all the desirable properties of the Golden code except its coding gain, but offers lower ML-decoding complexity of the order ofM2. Importantly, the slight loss in coding gain is negligible compared to the advantage it offers in terms of lowering the ML-decoding complexity. For higher number of transmit antennas, the best known codes are the Perfect codes, which are full-rate, full-diversity, information lossless codes (fornr≥nt) but have a high ML-decoding complexity of the order ofMntnmin(for nrrwith reduced ML-decoding complexity of the order of Mnt(nmin-3/4)-0.5 is presented. The codes constructed are also information lossless fornr≥nt, like the Perfect codes, and allow higher mutual information than the comparable punctured Perfect codes fornrnt. These codes are referred to as the generalized Silver codes, since they enjoy the same desirable properties as the comparable Perfect codes (except possibly the coding gain) with lower ML-decoding complexity, analogous to the Silver code and the Golden code for two transmit antennas. Simulation results of the symbol error rates for four and eight transmit antennas show that the generalized Silver codes match the punctured Perfect codes in error performance while offering lower ML- decoding complexity.

Low complexity decoders called Partial Interference Cancellation (PIC) and PIC with Successive Interference Cancellation (PIC-SIC), which include the Zero Forcing (ZF) and ZF-SIC receivers as special cases, were given by Guo and Xia along with sufficient conditions for a Space-Time Block Code (STBC) to achieve full diversity with PIC/PIC-SIC decoding for point-to-point MIMO channels. In Part-I of this two part series of papers, we give new conditions for an STBC to achieve full diversity with PIC and PIC-SIC decoders, which are equivalent to Guo and Xia's conditions, but are much easier to check. We then show that PIC and PIC-SIC decoders are capable of achieving the full cooperative diversity available in wireless relay networks and give sufficient conditions for a Distributed Space-Time Block Code (DSTBC) to achieve full diversity with PIC and PIC-SIC decoders. In Part-II, we construct new low complexity full-diversity PIC/PIC-SIC decodable STBCs and DSTBCs that achieve higher rates than the known full-diversity low complexity ML decodable STBCs and DSTBCs.

In this second part of a two part series of papers, we construct a new class of Space-Time Block Codes (STBCs) for point-to-point MIMO channel and Distributed STBCs (DSTBCs) for the amplify-and-forward relay channel that give full-diversity with Partial Interference Cancellation (PIC) and PIC with Successive Interference Cancellation (PIC-SIC) decoders. The proposed class of STBCs include most of the known full-diversity low complexity PIC/PIC-SIC decodable STBCs as special cases. We also show that a number of known full-diversity PIC/PIC-SIC decodable STBCs that were constructed for the point-to-point MIMO channel can be used as full-diversity PIC/PIC-SIC decodable DSTBCs in relay networks. For the same decoding complexity, the proposed STBCs and DSTBCs achieve higher rates than the known low decoding complexity codes. Simulation results show that the new codes have a better bit error rate performance than the low ML decoding complexity codes available in the literature.

For a family/sequence of Space-Time Block Codes (STBCs) C1, C2, ..., with increasing number of transmit antennas Ni, with rates Ricomplex symbols per channel use, i = 1, 2,..., the asymptotic normalized rate is defined as limi→∞Ri/Ni. A family of STBCs is said to be asymptotically-good if the asymptotic normalized rate is non-zero, i.e., when the rate scales as a nonzero fraction of the number of transmit antennas. An STBC C is said to be g-group ML-decodable if its information symbols can be partitioned into g groups, such that each group of symbols can be ML decoded independently of others. In this paper, for g ≥ 2, we construct g-group ML-decodable codes with rates greater than one complex symbol per channel use. These codes are asymptotically good too. For g >; 2, these are the first instances of g-group ML-decodable codes, with rates greater than 1, presented in the literature. We also construct multigroup ML-decodable codes with the best known asymptotic normalized rates. Specifically, we propose delay-optimal 2-group ML-decodable codes for number of antennas N >; 1 with rate N/4 + 1/N for even N and rate N/4 + 5/4N - ½ for odd N. We construct delay optimal, g-group ML-decodable codes, g >; 2, for number of antennas N that are a multiple of g2⌊g-1/2⌋with rate N/g2g-1+ g2-g/2N. We also construct non-delay-optimal g-group ML-decodable codes, g ≥ 2, for number of antennas N that are a multiple of 2⌊g-1/2⌋, with delay gN and rate N/2g-1 + g-1/2N.

For an nttransmit, nrreceive antenna system (nt× nrsystem), a fall-rate space time block code (STBC) transmits nmin= min(nt, nr) complex symbols per channel use and in general, has an ML-decoding complexity of the order of Mntnmin(considering square designs), where M is the constellation size. In this paper, a scheme to obtain a fullrate STBC for 2atransmit antennas and any nτ, with reduced ML-decoding complexity of the order of Mnt(nmin-3/4)-0.5, is presented. The well known Silver code for 2 transmit antennas is a special case of the proposed scheme. Further, it is shown that the codes constructed using the scheme have higher ergodic capacity than the well known punctured Perfect codes for nrt. Simulation results of the symbol error rates are shown for 8 × 2 systems, where the comparison of the proposed code is with the punctured Perfect code for 8 transmit antennas. The proposed code matches the punctured Perfect code in error performance, while having reduced ML-decoding complexity and higher ergodic capacity.

In this paper, we are concerned with low-complexity detection in large multiple-input multiple-output (MIMO) systems with tens of transmit/receive antennas. Our new contributions in this paper are two-fold. First, we propose a low-complexity algorithm for large-MIMO detection based on a layered low-complexity local neighborhood search. Second, we obtain a lower bound on the maximum-likelihood (ML) bit error performance using the local neighborhood search. The advantages of the proposed ML lower bound are i) it is easily obtained for MIMO systems with large number of antennas because of the inherent low complexity of the search algorithm, ii) it is tight at moderate-to-high SNRs, and iii) it can be tightened at low SNRs by increasing the number of symbols in the neighborhood definition. Interestingly, the proposed detection algorithm based on the layered local search achieves bit error performances which are quite close to this lower bound/or large number of antennas and higher-order QAM. For e.g., in a 32 × 32 V-BLAST MIMO system, the proposed detection algorithm performs close to within 1.7 dB of the proposed ML lower bound at 10-3BER for 16-QAM (128 bps/Hz), and close to within 4.5 dB of the bound for 64-QAM (192 bps/Hz).

Recently, a special class of complex designs called Training-Embedded Complex Orthogonal Designs (TE-CODs) has been introduced to construct single-symbol Maximum Likelihood decodable (SSD) distributed space-time block codes (DSTBCs) for two-hop wireless relay networks using the amplify and forward protocol. However, to implement DSTBCs from square TE-CODs, the overhead due to the transmission of training symbols becomes prohibitively large as the number of relays increase. In this paper, we propose TE-Coordinate Interleaved Orthogonal Designs (TE-CIODs) to construct SSD DSTBCs. Exploiting the block diagonal structure of TE-CIODs, we show that the overhead due to the transmission of training symbols to implement DSTBCs from TE-CIODs is smaller than that for TE-CODs. We also show that DSTBCs from TE-CIODs offer higher rate than those from TE-CODs for identical number of relays while maintaining the SSD and full-diversity properties.

A single source network is said to be memory-free if all of the internal nodes (those except the source and the sinks) do not employ memory but merely send linear combinations of the symbols received at their incoming edges on their outgoing edges. In this work, we introduce network-error correction for single source, acyclic, unit-delay, memory-free networks with coherent network coding for multicast. A convolutional code is designed at the source based on the network code in order to correct network- errors that correspond to any of a given set of error patterns, as long as consecutive errors are separated by a certain interval which depends on the convolutional code selected. Bounds on this interval and the field size required for constructing the convolutional code with the required free distance are also obtained. We illustrate the performance of convolutional network error correcting codes (CNECCs) designed for the unit-delay networks using simulations of CNECCs on an example network under a probabilistic error model.

A single-source network is said to be memory-free if all of the internal nodes (those except the source and the sinks) do not employ memory but merely send linear combinations of the incoming symbols (received at their incoming edges) on their outgoing edges. Memory-free networks with delay using network coding are forced to do inter-generation network coding, as a result of which the problem of some or all sinks requiring a large amount of memory for decoding is faced. In this work, we address this problem by utilizing memory elements at the internal nodes of the network also, which results in the reduction of the number of memory elements used at the sinks. We give an algorithm which employs memory at all the nodes of the network to achieve single- generation network coding. For fixed latency, our algorithm reduces the total number of memory elements used in the network to achieve single- generation network coding. We also discuss the advantages of employing single-generation network coding together with convolutional network-error correction codes (CNECCs) for networks with unit- delay and illustrate the performance gain of CNECCs by using memory at the intermediate nodes using simulations on an example network under a probabilistic network error model.

Distributed Space-Time Block Codes (DSTBCs) from Complex Orthogonal Designs (CODs) (both square and non-square CODs other than the Alamouti design) are known to lose their single-symbol ML decodable (SSD) property when used in two-hop wireless relay networks using the amplify and forward protocol. For such a network, a new class of high rate, training-symbol embedded (TSE) SSD DSTBCs are proposed from TSECODs. The constructed codes include the training symbols within the structure of the code which is shown to be the key point to obtain high rate along with the SSD property. TSE-CODs are shown to offer full-diversity for arbitrary complex constellations. Non-square TSE-CODs are shown to provide better rates (in symbols per channel use) compared to the known SSD DSTBCs for relay networks when the number of relays is less than 10. Importantly, the proposed DSTBCs do not contain zeros in their codewords and as a result, antennas of the relay nodes do not undergo a sequence of switch on and off transitions within every codeword use. Hence, the proposed DSTBCs eliminate the antenna switching problem.

In this paper we construct low ML decoding complexity STBCs by using the Pauli matrices as linear dispersion matrices. In this case the Hurwitz-Radon orthogonality condition is shown to be easily checked by transferring the problem to F4domain. The problem of constructing low ML decoding complexity STBCs is shown to be equivalent to finding certain codes over F4. It is shown that almost all known low ML decoding complexity STBCs can be obtained by this approach. New classes of codes are given that have the least known ML decoding complexity in some ranges of rate.

Convolutional network-error correcting codes (CNECCs) are known to provide error correcting capability in acyclic instantaneous networks within the network coding paradigm under small field size conditions. In this work, we investigate the performance of CNECCs under the error model of the network where the edges are assumed to be statistically independent binary symmetric channels, each with the same probability of error pe(0 ≤ peeshould be so that only single edge network-errors need to be accounted for, thus reducing the complexity of evaluating the probability of error of any CNECC. Simulations indicate that convolutional codes are required to possess different properties to achieve good performance in low peand high peregimes. For the low peregime, convolutional codes with good distance properties show good performance. For the high peregime, convolutional codes that have a good slope (the minimum normalized cycle weight) are seen to be good. We derive a lower bound on the slope of any rate b/c convolutional code with a certain degree.

For an nttransmit, nrreceive antenna system (nt× nrsystem), a full-rate space time block code (STBC) transmits min(nt, nr) complex symbols per channel use. In this paper, a scheme to obtain a full-rate STBC for 4 transmit antennas and any nr, with reduced ML-decoding complexity is presented. The weight matrices of the proposed STBC are obtained from the unitary matrix representations of a Clifford Algebra. By puncturing the symbols of the STBC, full rate designs can be obtained for nrr, the proposed design offers the least ML-decoding complexity among known codes. The proposed design is comparable in error performance to the well known Perfect code for 4 transmit antennas while offering lower ML-decoding complexity. Further, when nr< 4, the proposed design has higher ergodic capacity than the punctured Perfect code. Simulation results which corroborate these claims are presented.

Recently, Guo and Xia gave sufficient conditions for an STBC to achieve full diversity when a PIC (Partial Interference Cancellation) or a PIC-SIC (PIC with Successive Interference Cancellation) decoder is used at the receiver. In this paper, we give alternative conditions for an STBC to achieve full diversity with PIC and PIC-SIC decoders, which are equivalent to Guo and Xia's conditions, but are much easier to check. Using these conditions, we construct a new class of full diversity PIC-SIC decodable codes, which contain the Toeplitz codes and a family of codes recently proposed by Zhang, Xu et. al. as proper subclasses. With the help of the new criteria, we also show that a class of PIC-SIC decodable codes recently proposed by Zhang, Shi et. al. can be decoded with much lower complexity than what is reported, without compromising on full diversity.

This paper is on the design and performance analysis of practical distributed space-time codes for wireless relay networks with multiple antennas terminals. The amplify-and-forward scheme is used in a way that each relay transmits a scaled version of the linear combination of the received symbols. We propose distributed generalized quasi-orthogonal space-time codes which are distributed among the source antennas and relays, and valid for any number of relays. Assuming M-PSK and M-QAM signals, we derive a formula for the symbol error probability of the investigated scheme over Rayleigh fading channels. For sufficiently large SNR, this paper derives closed-form average SER expression. The simplicity of the asymptotic results provides valuable insights into the performance of cooperative networks and suggests means of optimizing them. Our analytical results have been confirmed by simulation results, using full-rate full-diversity distributed codes.

In this paper, collocated and distributed space-time block codes (DSTBCs) which admit multigroup maximum-likelihood (ML) decoding are studied. First, the collocated case is considered and the problem of constructing space-time block codes (STBCs) which optimally tradeoff rate and ML decoding complexity is posed. Recently, sufficient conditions for multigroup ML decodability have been provided in the literature and codes meeting these sufficient conditions were called Clifford unitary weight (CUW) STBCs. An algebraic framework based on extended Clifford algebras (ECAs) is proposed to study CUW STBCs and using this framework, the optimal tradeoff between rate and ML decoding complexity of CUW STBCs is obtained for few specific cases. Code constructions meeting this tradeoff optimally are also provided. The paper then focuses on multigroup ML decodable DSTBCs for application in synchronous wireless relay networks and three constructions of four-group ML decodable DSTBCs are provided. Finally, the orthogonal frequency-division multiplexing (OFDM)-based Alamouti space-time coded scheme proposed by Li–Xia for a 2-relay asynchronous relay network is extended to a more general transmission scheme that can achieve full asynchronous cooperative diversity for arbitrary number of relays. It is then shown how differential encoding at the source can be combined with the proposed transmission scheme to arrive at a new transmission scheme that can achieve full cooperative diversity in asynchronous wireless relay networks with no channel information and also no timing error knowledge at the destination node. Four-group decodable DSTBCs applicable in the proposed OFDM-based transmission scheme are also given.

Capacity region for two-user Gaussian Broadcast Channels (GBC) is well known with the optimal input being Gaussian. In this paper we explore the capacity region for GBC when the users' symbols are taken from finite complex alphabets (like M-QAM, M-PSK). When the alphabets for both the users are the same we show that rotation of one of the alphabets enlarges the capacity region. We arrive at an optimal angle of rotation by simulation. The effect of rotation on the capacity region at different SNRs is also studied using simulation results. Using the setup of Fading Broadcast Channel (FBC) given by [Li and Goldsmith, 2001], we study the ergodic capacity region with inputs from finite complex alphabets. It is seen that, using the procedure for optimum power allocation obtained in [Li and Goldsmith, 2001] for Gaussian inputs, to allocate power to symbols from finite complex alphabets, relative rotation between the alphabets does not improve the capacity region. Simulation results for a modified heuristic power allocation procedure for finite-constellation case, show that Constellation Constrained capacity region enlarges with rotation.

In this paper, Space-Time Block Codes (STBCs) with reduced Sphere Decoding Complexity (SDC) are constructed for two-user Multiple-Input Multiple-Output (MIMO) fading multiple access channels. In this set-up, both the users employ identical STBCs and the destination performs sphere decoding for the symbols of the two users. First, we identify the positions of the zeros in the R matrix arising out of the Q-R decomposition of the lattice generator such that (i) the worst case SDC (WSDC) and (ii) the average SDC (ASDC) are reduced. Then, a set of necessary and sufficient conditions on the lattice generator is provided such that the R matrix has zeros at the identified positions. Subsequently, explicit constructions of STBCs which results in the reduced ASDC are presented. The rate (in complex symbols per channel use) of the proposed designs is at most 2/Ntwhere Ntdenotes the number of transmit antennas for each user. We also show that the class of STBCs from complex orthogonal designs (other than the Alamouti design) reduce the WSDC but not the ASDC.

In this work, we introduce convolutional codes for network-error correction in the context of coherent network coding. We give a construction of convolutional codes that correct a given set of error patterns, as long as consecutive errors are separated by a certain interval. We also give some bounds on the field size and the number of errors that can get corrected in a certain interval. Compared to previous network error correction schemes, using convolutional codes is seen to have advantages in field size and decoding technique. Some examples are discussed which illustrate the several possible situations that arise in this context.

This paper proposes a full-rate, full-diversity space-time block code (STBC) with low maximum likelihood (ML) decoding complexity and high coding gain for the 4 transmit antenna, 2 receive antenna (4 times 2) multiple-input multiple-output (MIMO) system that employs 4/16-QAM. For such a system, the best code known is the DjABBA code and recently, Biglieri, Hong and Viterbo have proposed another STBC (BHV code) for 4-QAM which has lower ML-decoding complexity than the DjABBA code but does not have full-diversity like the DjABBA code. The code proposed in this paper has the same ML-decoding complexity as the BHV code for any squareM-QAM but has full- diversity for 4- and 16-QAM. Compared with the DjABBA code, the proposed code has lower ML-decoding complexity for squareM-QAM constellation, higher coding gain for 4- and 16-QAM, and hence a better codeword error rate (CER) performance. Simulation results confirming this are presented.

In this paper, we propose a training-based channel estimation scheme for large non-orthogonal space-time block coded (STBC) MIMO systems. The proposed scheme employs a block transmission strategy where an Nttimes Ntpilot matrix is sent (for training purposes) followed by several Nttimes Ntsquare data STBC matrices, where Ntis the number of transmit antennas. At the receiver, we iterate between channel estimation (using an MMSE estimator) and detection (using a low-complexity likelihood ascent search (LAS) detector) till convergence or for a fixed number of iterations. Our simulation results show that excellent bit error rate and nearness-to-capacity performance are achieved by the proposed scheme at low complexities. The fact that we could show such good results for large STBCs (e.g., 16times16 STBC from cyclic division algebras) operating at spectral efficiencies in excess of 20 bps/Hz (even after accounting for the overheads meant for pilot-based channel estimation and turbo coding) establishes the effectiveness of the proposed scheme.

It is well known that n-length stabilizer quantum error correcting codes (QECCs) can be obtained via n-length classical error correction codes (CECCs) over GF(4), that are additive and self-orthogonal with respect to the trace Hermitian inner product. But, most of the CECCs have been studied with respect to the Euclidean inner product. In this paper, it is shown that n-length stabilizer QECCs can be constructed via 3n-length linear CECCs over GF(2) that are self-orthogonal with respect to the Euclidean inner product. This facilitates usage of the widely studied self-orthogonal CECCs to construct stabilizer QECCs. Moreover, classical, binary, self-orthogonal cyclic codes have been used to obtain stabilizer QECCs with guaranteed quantum error correcting capability. This is facilitated by the fact that (i) self-orthogonal, binary cyclic codes are easily identified using transform approach and (ii) for such codes lower bounds on the minimum Hamming distance are known. Several explicit codes are constructed including two pure MDS QECCs.

Space-time block codes based on orthogonal designs are used for wireless communications with multiple transmit antennas which can achieve full transmit diversity and have low decoding complexity. However, the rate of the square real/complex orthogonal designs tends to zero with increase in number of antennas, while it is possible to have a rate-1 real orthogonal design (ROD) for any number of antennas. In case of complex orthogonal designs (CODs), rate-1 codes exist only for 1 and 2 antennas. In general, For n transmit antennas, the maximal rate of a COD is 1/2 + 1/n or 1/2 + 1/n+1 for n even or odd respectively. In this paper, we present a simple construction for maximal-rate CODs for any number of antennas from square CODs which resembles the construction of rate-1 RODs from square RODs. These designs are shown to be amenable for construction of a class of generalized CODs (called Coordinate-Interleaved Scaled CODs) with low peak-to-average power ratio (PAPR) having the same parameters as the maximal-rate codes. Simulation results indicate that these codes perform better than the existing maximal rate codes under peak power constraint while performing the same under average power constraint.

Constellation constrained (CC) capacity regions of a two-user Gaussian multiple access channel (GMAC) have been recently reported. For such a channel, code pairs based on trellis coded modulation are proposed in this paper with M-PSK and M-PAM alphabet pairs, for arbitrary values of M; to achieve sum rates close to the CC sum capacity of the GMAC. In particular, the structure of the sum alphabets of M-PSK and M-PAM alphabet pairs are exploited to prove that, for certain angles of rotation between the alphabets, Ungerboeck labelling on the trellis of each user maximizes the guaranteed squared Euclidean distance of the sum trellis. Hence, such a labelling scheme can be used systematically to construct trellis code pairs to achieve sum rates close to the CC sum capacity. More importantly, it is shown for the first time that ML decoding complexity at the destination is significantly reduced when M-PAM alphabet pairs are employed with almost no loss in the sum capacity.

Non-orthogonal space-time block codes (STBC) from cyclic division algebras (CDA) are attractive because they can simultaneously achieve both high spectral efficiencies (same spectral efficiency as in V-BLAST for a given number of transmit antennas) as well as full transmit diversity. Decoding of non-orthogonal STBCs with hundreds of dimensions has been a challenge. In this paper, we present a probabilistic data association (PDA) based algorithm for decoding non-orthogonal STBCs with large dimensions. Our simulation results show that the proposed PDA-based algorithm achieves near SISO AWGN uncoded BER as well as near-capacity coded BER (within 5 dB of the theoretical capacity) for large non-orthogonal STBCs from CDA.We study the effect of spatial correlation on the BER, and show that the performance loss due to spatial correlation can be alleviated by providing more receive spatial dimensions. We report good BER performance when a training-based iterative decoding/channel estimation is used (instead of assuming perfect channel knowledge) in channels with large coherence times. A comparison of the performances of the PDA algorithm and the likelihood ascent search (LAS) algorithm (reported in our recent work) is also presented.

Non-orthogonal space-time block codes (STBC) with large dimensions are attractive because they can simultaneously achieve both high spectral efficiencies (same spectral efficiency as in V-BLAST for a given number of transmit antennas) as well as full transmit diversity. Decoding of non-orthogonal STBCs with large dimensions has been a challenge. In this paper, we present a reactive tabu search (RTS) based algorithm for decoding non-orthogonal STBCs from cyclic division algebras (CDA) having large dimensions. Under i.i.d fading and perfect channel state information at the receiver (CSIR), our simulation results show that RTS based decoding of 12 × 12 STBC from CDA and 4-QAM with 288 real dimensions achieves i) 10−3uncoded BER at an SNR of just 0.5 dB away from SISO AWGN performance, and ii) a coded BER performance close to within about 5 dB of the theoretical MIMO capacity, using rate-3/4 turbo code at a spectral efficiency of 18 bps/Hz. RTS is shown to achieve near SISO AWGN performance with less number of dimensions than with LAS algorithm (which we reported recently) at some extra complexity than LAS.We also report good BER performance of RTS when i.i.d fading and perfect CSIR assumptions are relaxed by considering a spatially correlatedMIMO channelmodel, and by using a training based iterative RTS decoding/channel estimation scheme.

Jing and Hassibi introduced a distributed space time block coding scheme for symbol synchronous, coherent, amplify and forward relay networks with half duplex constrained relay nodes. In this two phase transmission scheme, the source transmits a vector of complex symbols to the relays during the first phase and each relay applies a pre-assigned unitary transformation to the received vector or its conjugate before transmitting it to the destination during the second phase. The destination then perceives a certain structured distributed space time block code (DSTBC) whose maximum likelihood (ML) decoding complexity in general, is very high. In this paper, explicit constructions of minimum delay, full diversity, four group ML decodable DSTBCs with unitary relay matrices are provided for even number of relay nodes. Prior constructions of DSTBCs with the same features were either limited to power of two number of relay nodes or had non-unitary relay matrices which leads to large peak to average power ratio of the relay's transmitted signals. For the case of odd number of relays, constructions of minimum delay, full diversity, two group ML decodable DSTBCs are given.

A Space-Time Block Code (STBC) in K-variables is said to be g-Group ML-Decodable (GMLD) if its Maximum-Likelihood (ML) decoding metric can be written as a sum of g independent terms, with each term being a function of a subset of the K variables. In this paper, a construction method to obtain high-rate, 2-GMLD STBCs for 2mtransmit antennas, m ≫ 1, is presented. The rate of the STBC obtained for 2mtransmit antennas is 2m−2+ 1/2mcomplex symbols per channel use. The design method is illustrated for the case of 4 and 8 transmit antennas. The code obtained for 4 transmit antennas is equivalent to the rate-5/4 Quasi-Orthogonal design (QOD) proposed by Yuen, Guan and Tjung.

In this paper, we present a belief propagation (BP) based algorithm for decoding non-orthogonal space-time block codes (STBC) from cyclic division algebras (CDA) having large dimensions. The proposed approach involves message passing on Markov random field (MRF) representation of the STBC MIMO system. Adoption of BP approach to decode non-orthogonal STBCs of large dimensions has not been reported so far. Our simulation results show that the proposed BP-based decoding achieves increasingly closer to SISO AWGN performance for increased number of dimensions. In addition, it also achieves near-capacity turbo coded BER performance; for e.g., with BP decoding of 24 × 24 STBC from CDA using BPSK (i.e., 576 real dimensions) and rate-1/2 turbo code (i.e., 12 bps/Hz spectral efficiency), coded BER performance close to within just about 2.5 dB from the theoretical MIMO capacity is achieved.

In this paper, we present novel precoder designs for V-BLAST systems which achieve full-rate. We first present a precoding scheme based on algebraic lattices over real number fields. We prove that this full-rate scheme achieves full-diversity, assuming availability of full channel state information at the transmitter. We then propose a precoding scheme which achieves full-rate and high orders of diversity with limited feedback. The proposed scheme involves a precoder codebook design consisting of unitary matrices parametrized by a single angular parameter, thereby requiring less feedback overhead. Our simulation results show that the proposed limited feedback precoding scheme provides a performance improvement of 1.5 dB and 2.5 dB at a bit error rate of 10-3over existing schemes for 2×2 and 4×4 V-BLAST systems, respectively, using 4-QAM.

Distributed orthogonal space-time block codes (DOSTBCs) achieving full-diversity order and single-symbol maximum-likelihood (ML) decodability have been introduced recently by Yi and Kim for cooperative networks, and an upper bound on the maximal rate of such codes along with code constructions has been presented. In this paper, a new class of single-symbol ML decodable precoded distributed space-time block codes (SSD-PDSTBCs) called semiorthogonal SSD-PDSTBCs (semi-SSD-PDSTBCs) is introduced wherein, the source performs linear precoding of information symbols appropriately before transmitting it to all the relays. It is shown that DOSTBCs are a special case of semi-SSD-PDSTBCs. A special class of semi-SSD-PDSTBCs having diagonal covariance matrix at the destination is studied and an upper bound on the maximal rate of such codes is derived. The bounds obtained are approximately twice larger than that of the DOSTBCs. A systematic construction of semi-SSD-PDSTBCs is presented when the number of relaysKges 4. The constructed codes are shown to achieve the upper bound on the rate whenKis of the form0or3modulo4. For the rest of the values ofK, the constructed codes are shown to have rates higher than that of DOSTBCs. It is shown that semi-SSD-PDSTBCs cannot be constructed with any form of linear processing at the relays when the source does not perform linear precoding of the information symbols.

A space-time block code (STBC) inKsymbols (variables) is called ag-group decodable STBC if its maximum-likelihood (ML) decoding metric can be written as a sum ofgterms, for some positive integerggreater than one, such that each term is a function of a subset of theKvariables and each variable appears in only one term. In this paper, we provide a general structure of the weight matrices of multigroup decodable codes using Clifford algebras. Without assuming that the number of variables in each group is the same, a method of explicitly constructing the weight matrices of full-diversity, delay-optimal multigroup decodable codes is presented for arbitrary number of antennas. For the special case of2anumber of transmit antennas, we construct two subclass of codes: 1) a class of2a-group decodable codes with rate[(a)/(2(a-1))], which is, equivalently, a class of single-symbol decodable codes, and 2) a class of(2a-2)-group decodable codes with rate[((a-1))/(2(a-2))], i.e., a class of double-symbol decodable codes.

It is well known that space-time block codes (STBCs) obtained from orthogonal designs (ODs) are single-symbol decodable (SSD) and from quasi-orthogonal designs (QODs) are double-symbol decodable (DSD). However, there are SSD codes that are not obtainable from ODs and DSD codes that are not obtainable from QODs. In this paper, a method of constructingg-symbol decodable (g-SD) STBCs using representations of Clifford algebras are presented which when specialized tog=1,2 gives SSD and DSD codes, respectively. For the number of transmit antennas2athe rate (in complex symbols per channel use) of theg-SD codes presented in this paper is[(a+1-g)/(2a-g)]. The maximum rate of the DSD STBCs from QODs reported in the literature is[(a)/(2a-1)] which is smaller than the rate[(a-1)/(2a-2)] of the DSD codes of this paper, for2atransmit antennas. In particular, the reported DSD codes for 8 and 16 transmit antennas offer rates1and3/4, respectively, whereas the known STBCs from QODs offer only3/4and1/2, respectively. The construction of this paper is applicable for any number of transmit antennas. The diversity sum and diversity product of the new DSD codes are studied. It is shown that the diversity sum is larger than that of all known QODs and hence the new codes perform better than the comparable QODs at low signal-to-noise ratios (SNRs) for identical spectral efficiency. Simulation results for DSD codes at various spectral efficiencies are provided.

It is known that neither the Alamouti nor the V-BLAST scheme achieves the Zheng–Tse diversity–multiplexing tradeoff (DMT) of the multiple-input multiple-output (MIMO) channel. With respect to the DMT curve, the Alamouti scheme achieves the point corresponding to maximum diversity gain only, whereas V-BLAST meets only the point corresponding to maximum multiplexing gain. It is also known that D-BLAST achieves the optimal DMT for$n$transmit and$n$receive antennas, but only under the assumption that the leading and trailing zeros are ignored. When these zeros are taken into account, D-BLAST achieves the point corresponding to zero multiplexing gain, but not the point corresponding to zero diversity gain. The first scheme to achieve the DMT is the coding scheme of Yao and Wornell for the case of two transmit and two receive antennas. In this paper, we introduce the notion of an asymptotic-information-lossless (AILL) design and obtain a necessary and sufficient condition under which a design is AILL. Analogous to the result that full-rank designs achieve the point corresponding to the zero multiplexing gain of the optimal DMT curve, we show AILL to be a necessary and sufficient condition for a design to achieve the point on the DMT curve corresponding to zero diversity gain. We also derive a lower bound on the tradeoff achieved by designs from field extensions and show that the tradeoff is very close to the optimal tradeoff in the case of a single receive antenna. A lower bound to the tradeoff achieved by designs from division algebras is presented which indicates that these designs achieve both extreme points (corresponding to zero diversity and zero multiplexing gain) of the optimal DMT curve. Finally, we present simulations results for$n$transmit and$n$receive antennas, for$n=2,3,4$, which suggest that designs from division algebras are likely to have the property of being DMT achieving.

Space-Time Block Codes from square complex orthogonal designs (SCOD) have been extensively studied and most of the existing SCODs contain large number of zero. The zeros in the designs result in high peak-to-average power ratio (PAPR) and also impose a severe constraint on hardware implementation of the code when turning off some of the transmitting antennas whenever a zero is transmitted. Recently, rate 1/2 SCODs with no zero entry have been reported for 8 transmit antennas. In this paper, SCODs with no zero entry for 2atransmit antennas whenever a + 1 is a power of 2, are constructed which includes the 8 transmit antennas case as a special case. More generally, for arbitrary values of a, explicit construction of 2atimes 2arate a+1/2aSCODs with the ratio of number of zero entries to the total number of entries equal to 1 - aplusmn1/2a2[logs2(2a/a+1)]is reported, whereas for standard known constructions, the ratio is 1- a+1/2a. The codes presented do not result in increased signaling complexity. Simulation results show that the codes constructed in this paper outperform the codes using the standard construction under peak power constraint while performing the same under average power constraint.

Distributed space time coding for wireless relay networks when the source, the destination and the relays have multiple antennas have been studied by Jing and Hassibi. In this set-up, the transmit and the receive signals at different antennas of the same relay are processed and designed independently, even though the antennas are colocated. In this paper, a wireless relay network with single antenna at the source and the destination and two antennas at each of the R relays is considered. A new class of distributed space time block codes called Co-ordinate Interleaved Distributed Space-Time Codes (CIDSTC) are introduced where, in the first phase, the source transmits a T-length complex vector to all the relays and in the second phase, at each relay, the in-phase and quadrature component vectors of the received complex vectors at the two antennas are interleaved and processed before forwarding them to the destination. Compared to the scheme proposed by Jing-Hassibi, for T ≥ 4R, while providing the same asymptotic diversity order of 2R, CIDSTC scheme is shown to provide asymptotic coding gain with the cost of negligible increase in the processing complexity at the relays. However, for moderate and large values of P, CIDSTC scheme is shown to provide more diversity than that of the scheme proposed by Jing-Hassibi. CIDSTCs are shown to be fully diverse provided the information symbols take value from an appropriate multi-dimensional signal set.

Space-time codes from complex orthogonal designs (CODs) with no zero entries offer low Peak to Average Power Ratio (PAPR) and avoid the problem of switching off antennas. But square CODs for 2aantennas with a+1 complex variables, with no zero entries were discovered only for a ⩽ 3 and if a+1 = 2k, for k ⩾ 4. In this paper, a method of obtaining no zero entry (NZE) square designs, called Complex Partial-Orthogonal Designs (CPODs), for 2a+1antennas whenever a certain type of NZE code exists for 2aantennas is presented. Then, starting from a so constructed NZE CPOD for n = 2a+1antennas, a construction procedure is given to obtain NZE CPODs for 2n antennas, successively. Compared to the CODs, CPODs have slightly more ML decoding complexity for rectangular QAM constellations and the same ML decoding complexity for other complex constellations. Using the recently constructed NZE CODs for 8 antennas our method leads to NZE CPODs for 16 antennas. The class of CPODs do not offer full-diversity for all complex constellations. For the NZE CPODs presented in the paper, conditions on the signal sets which will guarantee fulldiversity are identified. Simulation results show that bit error performance of our codes is same as that of the CODs under average power constraint and superior to CODs under peak power constraint.

For point to point multiple input multiple output systems, Dayal-Brehler-Varanasi have proved that training codes achieve the same diversity order as that of the underlying coherent space time block code (STBC) if a simple minimum mean squared error estimate of the channel formed using the training part is employed for coherent detection of the underlying STBC. In this letter, a similar strategy involving a combination of training, channel estimation and detection in conjunction with existing coherent distributed STBCs is proposed for noncoherent communication in amplify-and-forward (AF) relay networks. Simulation results show that the proposed simple strategy outperforms distributed differential space-time coding for AF relay networks. Finally, the proposed strategy is extended to asynchronous relay networks using orthogonal frequency division multiplexing.

A relay network with N relays and a single source destination pair is called a partially-coherent relay channel (PCRC) if the destination has perfect channel state information (CSI) of all the channels and the relays have only the phase information of the source-to-relay channels. In this paper, first, a new set of necessary and sufficient conditions for a space-time block code (STBC) to be single-symbol decodable (SSD) for colocated multiple antenna communication is obtained. Then, this is extended to a set of necessary and sufficient conditions for a distributed STBC (DSTBC) to be SSD for a PCRC. Using this, several SSD DSTBCs for PCRC are identified. It is proved that even if a SSD STBC for a co-located MIMO channel does not satisfy the additional conditions for the code to be SSD for a PCRC, single-symbol decoding of it in a PCRC gives full-diversity and only coding gain is lost. It is shown that when a DSTBC is SSD for a PCRC, then arbitrary coordinate interleaving of the in-phase and quadrature-phase components of the variables does not disturb its SSD property for PCRC. Finally, it is shown that the possibility of channel phase compensation operation at the relay nodes using partial CSI at the relays increases the possible rate of SSD DSTBCs from 2/N when the relays do not have CSI to 1/2, which is independent of N.

Large MIMO systems with tens of antennas in each communication terminal using full-rate non-orthogonal space- time block codes (STBC) from cyclic division algebras (CDA) can achieve the benefits of both transmit diversity as well as high spectral efficiencies. Maximum-likelihood (ML) or near-ML decoding of these large-sized STBCs at low complexities, however, has been a challenge. In this paper, we establish that near-ML decoding of these large STBCs is possible at practically affordable low complexities. We show that the likelihood ascent search (LAS) detector, reported earlier by us for V-BLAST, is able to achieve near-ML uncoded BER performance in decoding a 32 times 32 STBC from CDA, which employs 32 transmit antennas and sends 322= 1024 complex data symbols in 32 time slots in one STBC matrix (i.e., 32 data symbols sent per channel use). In terms of coded BER, with a 16 times 16 STBC, rate-3/4 turbo code and 4-QAM (i.e., 24 bps/Hz), the LAS detector performs close to within just about 4 dB from the theoretical MIMO capacity. Our results further show that, with LAS detection, information lossless (ILL) STBCs perform almost as good as full-diversity ILL (FD-ILL) STBCs. Such low-complexity detectors can potentially enable implementation of high spectral efficiency large MIMO systems that could be considered in wireless standards.

This paper presents a low-ML-decoding-complexity, full-rate, full-diversity space-time block code (STBC) for a 2 transmit antenna, 2 receive antenna multiple-input multiple- output (MIMO) system, with coding gain equal to that of the best and well known Golden code for any QAM constellation. Recently, two codes have been proposed (by Paredes, Gershman and Alkhansari and by Sezginer and Sari), which enjoy a lower decoding complexity relative to the Golden code, but have lesser coding gain. The 2 times 2 STBC presented in this paper has lesser decoding complexity for non-square QAM constellations, compared with that of the Golden code, while having the same decoding complexity for square QAM constellations. Compared with the Paredes-Gershman-Alkhansari and Sezginer-Sari codes, the proposed code has the same decoding complexity for non-rectangular QAM constellations. Simulation results, which compare the codeword error rate (CER) performance, are presented.

Single-symbol maximum likelihood (ML) decodable distributed orthogonal space-time block codes (DOST- BCs) have been introduced recently for cooperative networks and an upper-bound on the maximal rate of such codes along with code constructions has been presented. In this paper, we introduce a new class of distributed space-time block codes (DSTBCs) called semi-orthogonal precoded distributed single-symbol decodable space-time block codes (Semi-SSD-PDSTBCs) wherein, the source performs preceding on the information symbols before transmitting it to all the relays. A set of necessary and sufficient conditions on the relay matrices for the existence of semi-SSD- PDSTBCs is proved. It is shown that the DOSTBCs are a special case of semi-SSD-PDSTBCs. A subset of semi-SSD-PDSTBCs having diagonal covariance matrix at the destination is studied and an upper bound on the maximal rate of such codes is derived. The bounds obtained are approximately twice larger than that of the DOSTBCs. A systematic construction of Semi- SSD-PDSTBCs is presented when the number of relays K ges 4 and the constructed codes are shown to have higher rates than that of DOSTBCs.

In a distributed space-time coding scheme, based on the relay channel model, the relay nodes co-operate to linearly process the transmitted signal from the source and forward them to the destination such that the signal at the destination appears as a space time block code. Recently, a code design criteria for achieving full diversity in a partially-coherent environment, wherein the destination has the knowledge of channels from the relays to itself, but not the channels from the source to the relays, have been proposed along with codes based on differential encoding and decoding techniques. For such a set up, in this paper, a non-differential encoding technique and construction of distributed space time block codes from unitary matrix groups (a set of diagonal unitary matrices forming a group) at the source and a set of diagonal unitary matrices for the relays are proposed. It is shown that, the performance of our scheme is independent of the choice of unitary matrices at the relays. When the group is cyclic, a necessary and sufficient condition on the generator of the cyclic group to achieve full diversity and to minimize the pairwise error probability is proved. It is also shown that, at the source, if non-cyclic abelian unitary matrix groups are used, then full-diversity can not be obtained.

We consider large MIMO systems, where by 'large' we mean number of transmit and receive antennas of the order of tens to hundreds. Such large MIMO systems will be of immense interest because of the very high spectral efficiencies possible in such systems. We present a low-complexity detector which achieves uncoded near-exponential diversity performance for hundreds of antennas in V-BLAST (i.e., achieves near SISO AWGN performance in a large MIMO fading environment) with an average per-bit complexity of just 0(NtNr), where Ntand Nrdenote the number of transmit and receive antennas, respectively. With an outer turbo code, the proposed detector achieves good coded bit error performance as well. For example, in a 600 transmit and 600 receive antennas V-BLAST system with a high spectral efficiency of 200 bps/Hz (using BPSK and rate-1/3 turbo code), our simulation results show that the proposed detector performs close to within about 4.6 dB of the theoretical capacity. We also adopt the proposed detector for the low-complexity decoding of high-rate non-orthogonal space- time block codes (STBC) from division algebras (DA). We have decoded the 16x16 full-rate STBC from DA using the proposed detector and show that it performs close to within about 5.5 dB of the capacity using 4-QAM and rate-3/4 turbo code at a spectral efficiency of 24 bps/Hz. The practical feasibility of the proposed high-performance low-complexity detector could trigger wide interest in the implementation of large MIMO systems.

Recently Li and Xia have proposed a transmission scheme for wireless relay networks based on the Alamouti space time code and orthogonal frequency division multiplexing to combat the effect of timing errors at the relay nodes. This transmission scheme is amazingly simple and achieves a diversity order of two for any number of relays. Motivated by its simplicity, this scheme is extended to a more general transmission scheme that can achieve full cooperative diversity for any number of relays. The conditions on the distributed space time block code (DSTBC) structure that admit its application in the proposed transmission scheme are identified and it is pointed out that the recently proposed full diversity four group decodable DST-BCs from precoded co-ordinate interleaved orthogonal designs and extended Clifford algebras satisfy these conditions. It is then shown how differential encoding at the source can be combined with the proposed transmission scheme to arrive at a new transmission scheme that can achieve full cooperative diversity in asynchronous wireless relay networks with no channel information and also no timing error knowledge at the destination node. Finally, four group decodable distributed differential space time block codes applicable in this new transmission scheme for power of two number of relays are also provided.

Space-time block codes (STBCs) that are single-symbol decodable (SSD) in a co-located multiple antenna setting need not be SSD in a distributed cooperative communication setting. A relay network with N relays and a single source-destination pair is called a partially-coherent relay channel (PCRC) if the destination has perfect channel state information (CSI) of all the channels and the relays have only the phase information of the source- to-relay channels. In this paper, first, a new set of necessary and sufficient conditions for a STBC to be SSD for co-located multiple antenna communication is obtained. Then, this is extended to a set of necessary and sufficient conditions for a distributed STBC (DSTBC) to be SSD for a PCRC, by identifying the additional conditions. Using this, several SSD DSTBCs for PCRC are identified among the known classes of STBCs. It is proved that even if a SSD STBC for a co-located MIMO channel does not satisfy the additional conditions for the code to be SSD for a PCRC, single-symbol decoding of it in a PCRC gives full-diversity and only coding gain is lost.

Space-time block codes (STBCs) obtained from non-square complex orthogonal designs are bandwidth efficient compared to those from square real/complex orthogonal designs for colocated coherent MIMO systems and has other applications in (i) non-coherent MIMO systems with non-differential detection, (ii) Space-Time-Frequency codes for MIMO-OFDM systems and (iii) distributed space-time coding for relay channels. Liang (IEEE Trans. Inform. Theory, 2003) has constructed maximal rate non-square designs for any number of antennas, with rates given by [(a+1)/(2a)] when number of transmit antennas is 2a-1 or 2a. However, these designs have large delays. When large number of antennas are considered this rate is close to 1/2. Tarokh et al (IEEE Trans. Inform. Theory, 1999) have constructed rate 1/2 non-square CODs using the rate-1 real orthogonal designs for any number of antennas, where the decoding delay of these codes is less compared to the codes constructed by Liang for number of transmit antennas more than 5. In this paper, we construct a class of rate-1/2 codes for arbitrary number of antennas where the decoding delay is reduced by 50% when compared with the rate-1/2 codes given by Tarokh et al. It is also shown that even though scaling the variables helps to lower the delay it can not be used to increase the rate.

The capacity region of a two-user Gaussian multiple access channel (GMAC) with complex finite input alphabets and continuous output alphabet is studied. When both the users are equipped with the same code alphabet, it is shown that, rotation of one of the userpsilas alphabets by an appropriate angle can make the new pair of alphabets not only uniquely decodable, but will result in enlargement of the capacity region. For this set-up, we identify the primary problem to be finding appropriate angle(s) of rotation between the alphabets such that the capacity region is maximally enlarged. It is shown that the angle of rotation which provides maximum enlargement of the capacity region also minimizes the union bound on the probability of error of the sum-alphabet and vice-verse. The optimum angle(s) of rotation varies with the SNR. Through simulations, optimal angle(s) of rotation that gives maximum enlargement of the capacity region of GMAC with some well known alphabets such as M-QAM and M-PSK for some M are presented for several values of SNR. It is shown that for large number of points in the alphabets, capacity gains due to rotations progressively reduce. As the number of points N tends to infinity, our results match the results in the literature wherein the capacity region of the Gaussian code alphabet doesnpsilat change with rotation for any SNR.

In this paper, we present a low-complexity, near maximum-likelihood (ML) performance achieving detector for large MIMO systems having tens of transmit and receive antennas. Such large MIMO systems are of interest because of the high spectral efficiencies possible in such systems. The proposed detection algorithm, termed as multistage likelihood-ascent search (M-LAS) algorithm, is rooted in Hopfield neural networks, and is shown to possess excellent performance as well as complexity attributes. In terms of performance, in a 64 × 64 V-BLAST system with 4-QAM, the proposed algorithm achieves an uncoded BER of 10−3at an SNR of just about 1 dB away from AWGN-only SISO performance given by Q(√SNR). In terms of coded BER, with a rate-3/4 turbo code at a spectral efficiency of 96 bps/Hz the algorithm performs close to within about 4.5 dB from theoretical capacity, which is remarkable in terms of both high spectral efficiency as well as nearness to theoretical capacity. Our simulation results show that the above performance is achieved with a complexity of just O(NtNr) per symbol, where Ntand Nrdenote the number of transmit and receive antennas.

Space-time block codes (STBCs) that are single-symbol decodable (SSD) in a co-located multiple antenna setting need not be SSD in a distributed cooperative communication setting. A relay network with N relays and a single source-destination pair is called a partially-coherent relay channel (PCRC) if the destination has perfect channel state information (CSI) of all the channels and the relays have only the phase information of the source-to-relay channels. In our earlier work, we had derived a set of necessary and sufficient conditions for a distributed STBC (DSTBC) to be SSD for a PCRC. Using these conditions, in this paper we show that the possibility of channel phase compensation operation at the relay nodes using partial CSI at the relays increases the possible rate of SSD DSTBCs from 2/N when the relays do not have CSI to 1/2 , which is independent of N. We also show that when a DSTBC is SSD for a PCRC, then arbitrary coordinate interleaving of the in-phase and quadrature-phase components of the variables does not disturb its SSD property. Using this property we are able to construct codes that are SSD and have higher rate than 2/N but giving full diversity only for signal constellations satisfying certain conditions.

Recently, we reported a low-complexity likelihood ascent search (LAS) detection algorithm for large MIMO systems with several tens of antennas that can achieve high spectral efficiencies of the order of tens to hundreds of bps/Hz. Through simulations, we showed that this algorithm achieves increasingly near SISO AWGN performance for increasing number of antennas in i.i.d. Rayleigh fading. However, no bit error performance analysis of the algorithm was reported. In this paper, we extend our work on this low-complexity large MIMO detector in two directions: i)We report an asymptotic bit error probability analysis of the LAS algorithm in the large system limit, where Nt, Nr→ ∞ keeping Nt= Nr, where Ntand Nrare the number of transmit and receive antennas, respectively. Specifically, we prove that the error performance of the LAS detector for V-BLAST with 4-QAM in i.i.d. Rayleigh fading converges to that of the maximum-likelihood (ML) detector as Nt,Nr→ ∞ keeping Nt= Nr. ii)We present simulated BER and nearness to capacity results for V-BLAST as well as high-rate non-orthogonal STBC from Division Algebras (DA), in a more realistic spatially correlated MIMO channel model. Our simulation results show that a) at an uncoded BER of 10−3, the performance of the LAS detector in decoding 16×16 STBC from DA with Nt=Nr=16 and 16-QAM degrades in spatially correlated fading by about 7 dB compared to that in i.i.d. fading, and b) with a rate-3/4 outer turbo code and 48 bps/Hz spectral efficiency, the performance degrades by about 6 dB at a coded BER of 10−4. Our results further show that providing asymmetry in number of antennas such thatNr≫Ntkeeping the total receiver array length same as that for Nr=Nt, the detector is able to pick up the extra receive diversity thereby significantly improving the BER performance.

In this paper, we consider the problem of preceding in large multiuser MISO systems, where by 'large' we mean (i) large number of transmit antennas (Nt) at the base station of the order of tens to hundreds of transmit antennas, and (ii) large number of downlink users (Nu) of the order of tens to hundreds of users where each user has one receive antenna. Such large MISO systems will be of immense interest because of the high capacities (sum-rates) of the order of hundreds of bits/channel use possible in such systems. We propose a vector perturbation based low-complexity precoder, termed as norm descent search (NDS) precoder, which has a complexity of just O(NuNt) per information symbol. This low complexity attribute of the precoder is achieved by searching for the perturbation vector over a reduced search space. Interestingly, in terms of BER performance, the proposed precoder achieves increasingly better BER for increasing Nt, Nu, such that for large Nt, Nuit achieves near-exponential diversity with some SNR loss, thus making it suited for large MISO systems both in terms of complexity as well as performance. The results of uncoded/turbo-coded simulations without and with channel estimation errors are presented.

We consider large MIMO systems, where by 'large' we mean number of transmit and receive antennas of the order of tens to hundreds. Such large MIMO systems will be of immense interest because of the very high spectral efficiencies possible in such systems. We present a low-complexity detector which achieves uncoded near-exponential diversity performance for hundreds of antennas (i.e., achieves near SISO AWGN performance in a large MIMO fading environment) with an average per-bit complexity of just O(NtNr), where Ntand Nrdenote the number of transmit and receive antennas, respectively. With an outer turbo code, the proposed detector achieves good coded bit error performance as well. For example, in a 600 transmit and 600 receive antennas V-BLAST system with a high spectral efficiency of 450 bps/Hz (using BPSK and rate-3/4 turbo code), our simulation results show that the proposed detector performs to within about 7 dB from capacity. This practical feasibility of the proposed high-performance, low-complexity detector could potentially trigger wide interest in the theory and implementation of large MIMO systems. We also illustrate the applicability of the proposed detector in the low-complexity detection of high-rate, non-orthogonal space-time block codes and large multicarrier CDMA (MC-CDMA) systems. In large MC-CDMA systems with hundreds of users, the proposed detector is shown to achieve near single-user performance at an average per-bit complexity linear in number of users, which is quite appealing for its use in practical CDMA systems.

In a distributed space-time coding scheme, based on the relay channel model, the relay nodes co-operate to linearly process the transmitted signal from the source and forward them to the destination such that the signal at the destination appears as a space time block code. Recently, a code design criteria for achieving full diversity in a partially-coherent environment have been proposed along with codes based on differential encoding and decoding techniques. For such a set up, in this paper, a nondifferential encoding technique and construction of distributed space time block codes from unitary matrix groups at the source and a set of diagonal unitary matrices for the relays are proposed. It is shown that, the performance of our scheme is independent of the choice of unitary matrices at the relays. When the group is cyclic, a necessary and sufficient condition on the generator of the cyclic group to achieve full diversity and to minimize the pairwise error probability is proved. Various choices on the generator of cyclic group to reduce the ML decoding complexity at the destination is presented. It is also shown that, at the source, if non-cyclic abelian unitary matrix groups are used, then fulldiversity can not be obtained. The presented scheme is also robust to failure of any subset of relay nodes.

Design of space-time block codes (STBCs) for maximum likelihood (ML) reception has been predominantly the main focus of researchers. However, the ML decoding complexity of STBCs becomes prohibitive large as the number of transmit and receive antennas increase. Hence it is natural to resort to a suboptimal reception technique like linear minimum mean squared error (MMSE) receiver. Barbarossa et al and Liu et al have independently derived necessary and sufficient conditions for a full rate linear STBC to be MMSE optimal, i.e achieve least symbol error rate (SER). Motivated by this problem, certain existing high rate STBC constructions from crossed product algebras are identified to be MMSE optimal. Also, it is shown that a certain class of codes from cyclic division algebras which are special cases of crossed product algebras are MMSE optimal. Hence, these STBCs achieve least SER when MMSE reception is employed and are fully diverse when ML reception is employed.

The differential encoding/decoding setup introduced by Kiran et al, Oggier-Hassibi and Jing-Jafarkhani for wireless relay networks that use codebooks consisting of unitary matrices is extended to allow codebooks consisting of scaled unitary matrices. For such codebooks to be usable in the Jing-Hassibi protocol for cooperative diversity, the conditions involving the relay matrices and the codebook that need to be satisfied are identified. Using the algebraic framework of extended Clifford algebras, a new class of Distributed Differential Space-Time Codes satisfying these conditions for power of two number of relays and also achieving full cooperative diversity with a low complexity sub-optimal receiver is proposed. Simulation results indicate that the proposed codes outperform both the cyclic codes as well as the circulant codes. Furthermore, these codes can also be applied as Differential Space-Time codes for noncoherent communication in classical point to point multiple antenna systems.

Distributed space time coding for wireless relay networks where the source, the destination and the relays have multiple antennas have been studied by Jing and Hassibi. In this set up, the transmit and the receive signals at different antennas of the same relay are processed and designed independently, even though the antennas are colocated. In this paper, a wireless relay network with single antenna at the source and the destination and two antennas at each of the R relays is considered. In the first phase of the two-phase transmission model, a T -length complex vector is transmitted from the source to all the relays. At each relay, the inphase and quadrature component vectors of the received complex vectors at the two antennas are interleaved before processing them. After processing, in the second phase, a T x 2R matrix codeword is transmitted to the destination. The collection of all such codewords is called Co-ordinate interleaved distributed space-time code (CIDSTC). Compared to the scheme proposed by Jing-Hassibi, for T ges AR, it is shown that while both the schemes give the same asymptotic diversity gain, the CIDSTC scheme gives additional asymptotic coding gain as well and that too at the cost of negligible increase in the processing complexity at the relays.

Space-time codes from complex orthogonal designs (CODs) with no zero entries offer low peak to average power ratio (PAPR) and avoid the problem of turning off antennas. But CODs for 2alphaantennas with alpha + 1 complex variables, with no zero entries are not known in the literature for alpha ges 4. In this paper, a method of obtaining no zero entry (NZE) codes, called complex partial-orthogonal designs (CPODs), for 2alpha+1antennas whenever a certain type of NZE code exists for 2alphaantennas is presented. This is achieved with slight increase in the ML decoding complexity for regular QAM constellations and no increase for other complex constellations. Since NZE CODs have been constructed for 8 antennas our method leads to NZE CPODs for 16 antennas. Moreover, starting from certain NZE CPODs for n antennas, a construction procedure is given to obtain NZE CPODs for 2n antennas. The class of CPODs do not offer full-diversity for all complex constellations. For the NZE CPODs presented in the paper, conditions on the signal sets which will guarantee full-diversity are identified. Simulations results show that bit error performance of our codes under average power constraint is same as that of the CODs and superior to CODs under peak power constraint.

A linear processing complex orthogonal design (LPCOD) is a ptimesn matrix epsiv, (pgesn) in k complex indeterminates x1,x2,...,xksuch that (i) the entries of epsiv are complex linear combinations of 0, plusmnxi, i=1,...,k and their conjugates, (ii) epsivHepsiv=D, where epsivHis the Hermitian (conjugate transpose) of epsiv and D is a diagonal matrix with the (i,i)-th diagonal element of the form l1(i)|x1|2+l2(i)|x2|2+...+lk(i)|xk|2where lj(i),i=1,2,...,n, j=1,2,...,k are strictly positive real numbers and the condition l1(i)=l2(i)=...=lk(i), called the equal- weights condition, holds for all values of i. For square designs it is known that whenever a LPCOD exists without the equal-weights condition satisfied then there exists another LPCOD with identical parameters with l1(i)=l2(i)=...=lk(i)=1. This implies that the maximum possible rate for square LPCODs without the equal-weights condition is the same as that of square LPCODs with equal-weights condition. In this paper, this result is extended to a subclass of non-square LPCODs. It is shown that, a set of sufficient conditions is identified such that whenever a non- square (p>n) LPCOD satisfies these sufficient conditions and do not satisfy the equal-weights condition, then there exists another LPCOD with the same parameters n, k and p in the same complex indeterminates with l1(i)=l2(i)=...=lk(i)=1.

Differential Unitary Space-Time Block codes (STBCs) offer a means to communicate on the Multiple Input Multiple Output (MIMO) channel without the need for channel knowledge at both the transmitter and the receiver. Recently Yuen-Guan-Tjhung have proposed Single-Symbol-Decodable Differential Space-Time Modulation based on Quasi-Orthogonal Designs (QODs) by replacing the original unitary criterion by a scaled unitary criterion. These codes were also shown to perform better than differential unitary STBCs from Orthogonal Designs (ODs). However the rate (as measured in complex symbols per channel use) of the codes of Yuen-Guan-Tjhung decay as the number of transmit antennas increase. In this paper, a new class of differential scaled unitary STBCs for all even number of transmit antennas is proposed. These codes have a rate of 1 complex symbols per channel use, achieve full diversity and moreover they are four-group decodable, i.e., the set of real symbols can be partitioned into four groups and decoding can be done for the symbols in each group separately. Explicit construction of multidimensional signal sets that yield full diversity for this new class of codes is also given.

Space-Time Block Codes from square complex orthogonal designs (SCOD) have been extensively studied and most of the existing SCODs contain large number of zero resulting in high peak to average of power ratio (PAPR) and also impose a severe constraint on hardware implementation of the code when turning off some of the transmitting antennas whenever a zero is transmitted. Recently, maximal-rate SCODs with no zero entry have been reported for 8 transmit antennas, constructed using Amicable Orthogonal Designs. In this paper, maximal-rate SCODs with no zero entry for 2atransmit antennas whenever a+1 is a power of 2 are constructed which includes the 8 transmit antennas case as a special case. More generally, for arbitrary values of a, explicit construction of 2atimes 2amaximal-rate SCODs with the fraction of number of zero entries to the total number of entries equal to [1-(a-1)/(2a)] 2[log2(2a/a+1)]is reported. Moreover, it is shown that these codes are obtainable by premultiplying the well known SCODs with appropriate scaled unitary matrices consisting of nonzero entries that are plusmn1 only. A procedure to compute these scaled unitary matrices is also presented.

Zero entries in complex orthogonal designs (CODs) impede their practical implementation. In this paper, a method of obtaining a no zero entry (NZE) code for 2k+1antennas whenever a NZE code exists for 2kantennas is presented. This is achieved with slight increase in the ML decoding complexity for regular QAM constellations and no increase for other complex constellations. Since NZE CODs have been constructed recently for 8 antennas our method leads to NZE codes for 16 antennas. Simulation results show good performance of our new codes compared to the well known constructions for 16 and 32 antennas under peak power constraints.

A set of sufficient conditions to construct lambda-real symbol Maximum Likelihood (ML) decodable STBCs have recently been provided by Karmakar et al. STBCs satisfying these sufficient conditions were named as Clifford Unitary Weight (CUW) codes. In this paper, the maximal rate (as measured in complex symbols per channel use) of CUW codes for lambda = 2alpha, alpha epsiv N is obtained using tools from representation theory. Two algebraic constructions of codes achieving this maximal rate are also provided. One of the constructions is obtained using linear representation of finite groups whereas the other construction is based on the concept of right module algebra over non-commutative rings. To the knowledge of the authors, this is the first paper in which matrices over non-commutative rings is used to construct STBCs. An algebraic explanation is provided for the 'ABBA' construction first proposed by Tirkkonen et al and the tensor product construction proposed by Karmakar et al. Furthermore, it is established that the 4 transmit antenna STBC originally proposed by Tirkkonen et al based on the ABBA construction is actually a single complex symbol ML decodable code if the design variables are permuted and signal sets of appropriate dimensions are chosen.

"Extended Clifford algebras" are introduced as a means to obtain low ML decoding complexity space-time block codes. Using left regular matrix representations of two specific classes of extended Clifford algebras, two systematic algebraic constructions of full diversity distributed space-time codes (DSTCs) are provided for any power of two number of relays. The left regular matrix representation has been shown to naturally result in space-time codes meeting the additional constraints required for DSTCs. The DSTCs so constructed have the salient feature of reduced maximum likelihood (ML) decoding complexity. In particular, the ML decoding of these codes can be performed by applying the lattice decoder algorithm on a lattice of four times lesser dimension than what is required in general. Moreover these codes have a uniform distribution of power among the relays and in time, thus leading to a low Peak to Average Power Ratio at the relays.

The differential encoding/decoding setup introduced by Kiran et al, Oggier et al and Jing et al for wireless relay networks that use codebooks consisting of unitary matrices is extended to allow codebooks consisting of scaled unitary matrices. For such codebooks to be used in the Jing-Hassibi protocol for cooperative diversity, the conditions that need to be satisfied by the relay matrices and the codebook are identified. A class of previously known rate one, full diversity, four-group encodable and four-group decodable differential space-time codes (DSTCs) is proposed for use as distributed DSTCs (DDSTCs) in the proposed set up. To the best of our knowledge, this is the first known low decoding complexity DDSTC scheme for cooperative wireless networks.

The problem of designing high rate, full diversity noncoherent space-time block codes (STBCs) with low encoding and decoding complexity is addressed. First, the notion of p-group encodable and p-group decodable linear STBCs is introduced. Then for a known class of rate-1 linear designs, an explicit construction of fully-diverse signal sets that lead to four-group encodable and four-group decodable differential scaled unitary STBCs for any power of two number of antennas is provided. Previous works on differential STBCs either sacrifice decoding complexity for higher rate or sacrifice rate for lower decoding complexity.

Statistical information about the wireless channel can be used at the transmitter side to enhance the performance of MIMO systems. This paper addresses how the concept of channel precoding can be used to enhance the performance of STBCs from Generalized Pseudo Orthogonal Designs which were first introduced by Zhu and Jafarkhani. Such designs include some important classes of STBCs that are directly derivable from Quasi-Orthogonal Designs and Co-ordinate Interleaved Orthogonal Designs.

A half-duplex constrained non-orthogonal cooperative multiple access (NCMA) protocol suitable for transmission of information from N users to a single destination in a wireless fading channel is proposed. Transmission in this protocol comprises of a broadcast phase and a cooperation phase. In the broadcast phase, each user takes turn broadcasting its data to all other users and the destination in an orthogonal fashion in time. In the cooperation phase, each user transmits a linear function of what it received from all other users as well as its own data. In contrast to the orthogonal extension of cooperative relay protocols to the cooperative multiple access channels wherein at any point of time, only one user is considered as a source and all the other users behave as relays and do not transmit their own data, the NCMA protocol relaxes the orthogonality built into the protocols and hence allows for a more spectrally efficient usage of resources. Code design criteria for achieving full diversity of N in the NCMA protocol is derived using pair wise error probability (PEP) analysis and it is shown that this can be achieved with a minimum total time duration of 2N - 1 channel uses. Explicit construction of full diversity codes is then provided for arbitrary number of users. Since the maximum likelihood decoding complexity grows exponentially with the number of users, the notion of g-group decodable codes is introduced for the setup and a set of necessary and sufficient conditions is also obtained.

Design criteria and full-diversity distributed space time codes (DSTCs) for the two phase transmission based cooperative diversity protocol of Jing-Hassibi and the generalized nonorthogonal amplify and forward (GNAF) protocol are reported, when the relay nodes are assumed to have knowledge of the phase component of the source to relay channel gains. It is shown that this under this partial channel state information (CSI), several well known space time codes for the colocated MIMO (multiple input multiple output) channel become amenable for use as DSTCs. In particular, the well known complex orthogonal designs, generalized coordinate interleaved orthogonal designs (GCIODs) and unitary weight single symbol decodable (UW-SSD) codes are shown to satisfy the required design constraints for DSTCs. Exploiting the relaxed code design constraints, DSTCs was proposed obtained from Clifford algebras which have low ML decoding complexity.

A construction of a new family of distributed space time codes (DSTCs) having full diversity and low maximum likelihood (ML) decoding complexity is provided for the two phase based cooperative diversity protocols of Jing-Hassibi and the recently proposed generalized non-orthogonal amplify and forward (GNAF) protocol of Rajan et al. The salient feature of the proposed DSTCs is that they satisfy the extra constraints imposed by the protocols and are also four-group ML decodable which leads to significant reduction in ML decoding complexity compared to all existing DSTC constructions. Moreover these codes have uniform distribution of power among the relays as well as in time. Also, simulations results indicate that these codes perform better in comparison with the only known DSTC with the same rate and decoding complexity, namely the coordinate interleaved orthogonal design (CIOD). Furthermore, they perform very close to DSTCs from field extensions which have same rate but higher decoding complexity.

Distributed space-time coding is a mean of achieving diversity through cooperative communication in a wireless relay network. In this paper, we consider a transmission protocol that follows a two-stage model: transmission from source to relays in the first stage, followed by a simple relaying technique from relays to destination. The relays transmit a vector which is a transformation of the received vector by a relay-specific unitary transformation. We assume that the relays do not have any channel information, while the destination has only a partial-channel knowledge, by which we mean that destination knows only the relay-to-destination channel. For such a setup, we derive a Chernoff bound on the pairwise error probability and propose code design criteria. A second contribution is the differential encoding and decoding scheme for this setup, which is different from the existing ones. Furthermore, differential codes from cyclic division algebra are proposed that achieve full diversity. For our setup with two relays, a Generalized PSK code is shown to achieve full diversity, for which the decoding complexity is independent of code size

For the number of transmit antennas N = 2athe maximum rate (in complex symbols per channel use) of all the Quasi-Orthogonal Designs (QODs) reported in the literature is a/2a-1. In this paper, we report double-symbol-decodable Space- Time Block Codes with rate a-1/2a-2for N = 2atransmit antennas. In particular, our code for 8 and 16 transmit antennas offer rates 1 and 3/4 respectively, the known QODs offer only 3/4 and 1/2 respectively. Our construction is based on the representations of Clifford algebras and applicable for any number of transmit antennas. We study the diversity sum and diversity product of our codes. We show that our diversity sum is larger than that of all known QODs and hence our codes perform better than the comparable QODs at low SNRs for identical spectral efficiency. We provide simulation results for various spectral efficiencies.

Multiple antennas can be used for increasing the amount of diversity (diversity gain) or increasing the data rate (the number of degrees of freedom or spatial multiplexing gain) in wireless communication. As quantified by Zheng and Tse [1], given a Multiple Input Multiple Output (MIMO) channel, both gains can, in fact, be simultaneously obtained, but there is a fundamental tradeoff (called the Diversity-Multiplexing Gain (DM-G) tradeoff) between how much of each type of gain, any coding scheme can extract. Space-time codes (STC's) can be employed to make use of these advantages offered by multiple antennas. STC's can be broadly classified in two categories; namely space-time block codes (STBC) and space-time trellis codes (STTC). STTCs are known to have better bit error rate performance than STBCs, but with a penalty in decoding complexity. Also, for STTCs, the frame length is assumed to be finite and hence zeros are forced towards the end of the frame (called the trailing zeros), inducing rate loss. In this paper, we derive an upper bound on the DM-G tradeoff of full-rate STTCs with non-vanishing determinant (NVD). Also, we show that the full-rate STTCs with NVD are optimal under the DM-G tradeoff for any number of transmit and receive antennas, neglecting the rate loss due to trailing zeros. Next we give a explicit generalized full-rate STTC construction for any number of states of the trellis, which achieves the optimal DM-G tradeoff for any number of transmit and receive antennas, neglecting the rate loss due to trailing zeros.

For ptimesn complex orthogonal designs in k variables, where p is the number of channels uses and n is the number of transmit antennas, the maximal rate k/p of the design is asymptotically half as n increases. But, for such maximal rate codes, the decoding delay p increases exponentially. To control the delay, if we put the restriction that p = n, i.e., consider only the square designs, then, the rate decreases exponentially as n increases. This necessitates the study of the maximal rate of the designs with restrictions of the form p = n+1, p = n+2, p = n+3 etc. In this paper, we study the maximal rate of complex orthogonal designs with the restrictions p = n+1 and p = n+2. We derive upper and lower bounds for the maximal rate for p = n+1 and p = n+2. Also for the case of p = n+1, we show that if the orthogonal design admit only the variables, their negatives and multiples of these by radic-1 and zeros as the entries of the matrix (other complex linear combinations are not allowed), then the maximal rate always equals the lower bound

It is well known that Alamouti code and, in general, space-time block codes (STBCs) from complex orthogonal designs (CODs) are single-symbol decodable/symbol-by-symbol decodable (SSD) and are obtainable from unitary matrix representations of Clifford algebras. However, SSD codes are obtainable from designs that are not CODs. Recently, two such classes of SSD codes have been studied: (i) coordinate interleaved orthogonal designs (CIODs) and (ii) minimum-decoding-complexity (MDC) STBCs from quasi-ODs (QODs). In this paper, we obtain SSD codes with unitary weight matrices (but not CODs) from matrix representations of Clifford algebras. Moreover, we derive an upper bound on the rate of SSD codes with unitary weight matrices and show that our codes meet this bound. Also, we present conditions on the signal sets which ensure full-diversity and give expressions for the coding gain

Space-time block codes (STBCs) from complex orthogonal designs (CODs) are single-symbol decodable/symbol-by-symbol decodable (SSD); however, SSD codes are obtainable from designs that are not CODs. Recently, two such classes of SSD codes have been studied: (i) coordinate interleaved orthogonal designs (CIODs) and (ii) minimum-decoding-complexity (MDC) STBCs from quasi-ODs (QODs). The class of CIODs have non-unitary weight matrices when written as a linear dispersion code (LDC) proposed by Hassibi and Hochwald, whereas the other class of SSD codes including CODs have unitary weight matrices. In this paper, we construct a large class of SSD codes with non-unitary weight matrices. Also, we show that the class of CIODs is a special class of our construction

We address the problem of distributed space-time coding with reduced decoding complexity for wireless relay network. The transmission protocol follows a two-hop model wherein the source transmits a vector in the first hop and in the second hop the relays transmit a vector, which is a transformation of the received vector by a relay-specific unitary transformation. Design criteria is derived for this system model and codes are proposed that achieve full diversity. For a fixed number of relay nodes, the general system model considered in this paper admits code constructions with lower decoding complexity compared to codes based on some earlier system models

Distributed space-time coding is a means of achieving diversity through cooperative communication in a wireless relay network. In this paper, we consider a transmission protocol that follows a two-stage model: transmission from source to relays in the first stage, followed by a simple relaying technique from relays to destination. The relays transmit a vector, which is a transformation of the received vector by a relay-specific unitary transformation. We assume that the relays do not have any channel information, while the destination has only a partial-channel knowledge, by which we mean that destination knows only the relay-to-destination channel. We derive a Chernoff bound on the pairwise error probability and propose code design criteria. A second contribution is the differential encoding and decoding scheme for this setup, which is different from the existing ones. Furthermore, differential codes from cyclic division algebra are proposed that achieve full diversity. For our setup with two relays, a Generalized PSK code is shown to achieve full diversity, for which the decoding complexity is independent of code size

Space-time block codes (STBCs) from orthogonal designs (ODs) and coordinate interleaved orthogonal designs (CIOD) have been attracting wider attention due to their amenability for fast (single-symbol) maximum-likelihood (ML) decoding, and full-rate with full-rank over quasi-static fading channels. However, these codes are instances of single-symbol decodable codes and it is natural to ask, if there exist codes other than STBCs form ODs and CIODs that allow single-symbol decoding? In this paper, the above question is answered in the affirmative by characterizing all linear STBCs, that allow single-symbol ML decoding (not necessarily full-diversity) over quasi-static fading channels-calling them single-symbol decodable designs (SDD). The class SDD includes ODs and CIODs as proper subclasses. Further, among the SDD, a class of those that offer full-diversity, called Full-rank SDD (FSDD) are characterized and classified. We then concentrate on square designs and derive the maximal rate for square FSDDs using a constructional proof. It follows that 1) except for N=2, square complex ODs are not maximal rate and 2) a rate one square FSDD exist only for two and four transmit antennas. For nonsquare designs, generalized coordinate-interleaved orthogonal designs (a superset of CIODs) are presented and analyzed. Finally, for rapid-fading channels an equivalent matrix channel representation is developed, which allows the results of quasi-static fading channels to be applied to rapid-fading channels. Using this representation we show that for rapid-fading channels the rate of single-symbol decodable STBCs are independent of the number of transmit antennas and inversely proportional to the block-length of the code. Significantly, the CIOD for two transmit antennas is the only STBC that is single-symbol decodable over both quasi-static and rapid-fading channels.

It is known that the Alamouti code is the only complex orthogonal design (COD) which achieves capacity and that too for the case of two transmit and one receive antenna only. Damen proposed a design for two transmit antennas, which achieves capacity for any number of receive antennas, calling the resulting space–time block code (STBC) when used with a signal set an information-lossless STBC. In this paper, using crossed-product central simple algebras, we construct STBCs for arbitrary number of transmit antennas over an a priori specified signal set. Alamouti code and quasi-orthogonal designs are the simplest special cases of our constructions. We obtain a condition under which these STBCs from crossed-product algebras are information-lossless. We give some classes of crossed-product algebras, from which the STBCs obtained are information-lossless and also of full rank. We present some simulation results for two, three, and four transmit antennas to show that our STBCs perform better than some of the best known STBCs and also that these STBCs are approximately 1 dB away from the capacity of the channel with quadrature amplitude modulation (QAM) symbols as input.

Multiple antennas can be used for increasing the amount of diversity (diversity gain) or increasing the data rate (the number of degrees of freedom or spatial multiplexing gain) in wireless communication. As quantified by Zheng and Tse, given a multiple-input-multiple-output (MIMO) channel, both gains can, in fact, be simultaneously obtained, but there is a fundamental tradeoff (called the Diversity-Multiplexing Gain (DM-G) tradeoff) between how much of each type of gain, any coding scheme can extract. Space-time codes (STCs) can be employed to make use of these advantages offered by multiple antennas. Space-Time Trellis Codes (STTCs) are known to have better bit error rate performance than Space-Time Block Codes (STBCs), but with a penalty in decoding complexity. Also, for STTCs, the frame length is assumed to be finite and hence zeros are forced towards the end of the frame (called the trailing zeros), inducing rate loss. In this correspondence, we derive an upper bound on the DM-G tradeoff of full-rate STTCs with nonvanishing determinant (NVD). Also, we show that the full-rate STTCs with NVD are optimal under the DM-G tradeoff for any number of transmit and receive antennas, neglecting the rate loss due to trailing zeros. Next, we give an explicit generalized full-rate STTC construction for any number of states of the trellis, which achieves the optimal DM-G tradeoff for any number of transmit and receive antennas, neglecting the rate loss due to trailing zeros

Use of preceding transforms such as Hadamard transforms and phase alteration for peak to average power ratio (PAPR) reduction in OFDM systems are well known. In this paper we propose use of inverse discrete Fourier transform (IDFT) and Hadamard transform as preceding transforms in MIMO-OFDM systems to achieve low peak to average power ratio (PAPR). We show that while our approach using IDFT does not disturb the diversity gains of the MIMO-OFDM systems (spatial, temporal and frequency diversity gains), it offers a better trade-off between PAPR reduction and ML decoding complexity compared to that of the Hadamard transform precoding. We study in detail the amount of PAPR reduction achieved for the following two recently proposed full-diversity space-frequency coded MIMO-OFDM systems using both the IDFT and the Hadamard transform: (i) W. Su, Z. Safar, M. Olfat, K. J. R. Liu (IEEE Trans. on Signal Processing, Nov. 2003), and (ii) W. Su, Z. Safar, K. J. R. Liu (IEEE Trans. on Information Theory, Jan. 2005).

A linear rank-distance code is a set of matrices over a finite field F/sub q/, with the rank over Fq as a distance metric. A space-time block code (STBC) is a finite set of complex matrices with the rank over the complex field as a metric. Rank-distance codes over prime fields F/sub p/ have found applications as space-time codes. In this paper, we extend this result to arbitrary finite fields by providing an isomorphism from F/sub q/ (q = p/sup m/) to a subset of the ring of integers of an appropriate number field. Using this map and a maximal rank-distance code over F/sub q/, we construct STBC that achieve optimal rate-diversity tradeoff for any given diversity order. Simulation results confirm the diversity gain obtained using these codes.

Multiple antennas can be used for increasing the amount of diversity (diversity gain) or increasing the data rate (the number of degrees of freedom or spatial multiplexing gain) in wireless communication. As quantified by Zheng and Tse, given a multiple input multiple output (MIMO) channel, both gains can, in fact, be simultaneously obtained, but there is a fundamental tradeoff (called the diversity-multiplexing tradeoff) between how much of each type of gain any coding scheme can extract. It is well known that space-time trellis codes (STTC) can be used to achieve full-diversity and better coding gain than space-time block codes (STBC). There have many STBC constructions, which achieve the diversity-multiplexing tradeoff, but to the best of our knowledge no such construction is proposed for the case of STTC. A delay diversity scheme used to construct STTC introduced in Tarokh et al. (2002) is known to achieve full-diversity, for any number of transmit antennas. In this paper, we show that the delay diversity scheme can achieve the optimal diversity-multiplexing tradeoff, only for one receive antenna. Then we propose a generalized construction of a high-rate generalized coded delay diversity scheme (HRGCDD). We show that the HRGCDD scheme meets both the extreme points (corresponding to zero diversity gain and zero multiplexing gain) of the optimal diversity-multiplexing tradeoff curve for any number of transmit and receive antennas. Also by using the HRGCDD scheme we construct STTC for 2 transmit antennas. Furthermore we also show that the new proposed STTC achieves the optimal diversity-multiplexing tradeoff for 2 transmit and 2 receive antennas by simulation.

It is known that in an OFDM system using Hadamard transform or phase alteration before the IDFT operation can reduce the peak-to-average power ratio (PAPR). Both these techniques can be viewed as constellation preceding for PAPR reduction. In general, using non-diagonal transforms, like Hadamard transform, increases the ML decoding complexity. In this paper we propose the use of block-IDFT matrices and show that appropriate block-IDFT matrices give lower PAPR as well as lower decoding complexity compared to using Hadamard transform. Moreover, we present a detailed study of the tradeoff between PAPR reduction and the ML decoding complexity when using block-IDFT matrices with various sizes of the blocks

This paper presents a systematic technique for constructing STBC-schemes (space-time block code schemes) with non-vanishing determinant, based on cyclic division algebras. Prior constructions of STBC-schemes with non-vanishing determinant are available only for 2,3,4 and 6 transmit antennas. In this paper, by using an appropriate representation of a cyclic division algebra over a maximal subfield, we construct STBC-schemes with non-vanishing determinant for the number of transmit antennas of the form 2kor 3middot2kor 2middot3kor qk(q - 1)/2, where q is a prime of the form 4s + 3 and s is any arbitrary integer. In a recent work, Elia et. al. have proved that non-vanishing determinant is a sufficient condition for STBC-schemes from cyclic division algebra to achieve the optimal diversity-multiplexing gain (D-MG) tradeoff; thus proving that the STBC-schemes constructed in this paper achieve the optimal D-MG tradeoff

This paper presents a systematic construction of high-rate and full-diversity space-frequency block codes for MIMO-OFDM systems. While all prior constructions offer only a maximum rate of one complex symbol per channel use, our construction yields rate equal to the number of transmit antennas and simultaneously achieves full-diversity. The proposed construction works for arbitrary number of transmit antennas and arbitrary channel power delay profile. A key step in this construction is the generalization of the stacked matrix code design criteria given by Bolcskei et al., (IEEE WCNC 2000). Explicit equivalence of our generalized code design criteria with the Hadamard-product based criteria of W. Su et al., (IEEE Trans. Sig. Proc. Nov 2003) is established and new high-rate codes are constructed using our criteria

It is known that by employing space-time-frequency codes (STFCs) to frequency selective MIMO-OFDM systems, all the three diversity viz spatial, temporal and multipath can be exploited. There exists space-time-frequency block codes (STFBCs) designed using orthogonal designs with constellation precoder to get full diversity (Z. Liu, Y. Xin and G. Giannakis IEEE Trans. Signal Processing, Oct. 2002). Since orthogonal designs of rate one exists only for two transmit antennas, for more than two transmit antennas STFBCs of rate-one and full-diversity cannot be constructed using orthogonal designs. This paper presents a STFBC scheme of rate one for four transmit antennas designed using quasi-orthogonal designs along with coordinate interleaved orthogonal designs (Zafar Ali Khan and B. Sundar Rajan Proc: ISIT 2002). Conditions on the signal sets that give full-diversity are identified. Simulation results are presented to show the superiority of our codes over the existing ones

It is known that multi-antenna transmissions over frequency-selective channels can provide a diversity gain that is product of the number of transmit antennas, the receive antennas and the length of the channel impulse response. Liu, Xin and Giannakis have studied multi-antenna orthogonal frequency division multiplexing (OFDM) through frequency-selective Rayleigh-fading channels and have introduced the concept of space-time frequency (STF) coding to enable maximum diversity and high coding gains. It is known that under some conditions, an n-length cyclic code C over Fqm(n|qm- 1, and m les n) can have fullrank i.e Rankq(C) = m. Designs for space-time codes suitable for both quasi-static fading channels and block-fading channels have been derived from n length cyclic codes over Fqm. In this paper, we present a simplified design of STF codes using designs derived from cyclic codes to obtain group space-time-frequency (GSTF) codes for frequency selective Rayleigh fading channels. These codes achieve maximum diversity gain

A space-time block-code scheme (STBC-scheme) is a family of STBCs {C(SNR)}, indexed by the signal-to-noise ratio (SNR) such that the rate of each STBC scales with SNR. An STBC-scheme is said to have a nonvanishing determinant if the coding gain of every STBC in the scheme is lower-bounded by a fixed nonzero value. The nonvanishing determinant property is important from the perspective of the diversity multiplexing-gain (DM-G) tradeoff: a concept that characterizes the maximum diversity gain achievable by any STBC-scheme transmitting at a particular rate. This correspondence presents a systematic technique for constructing STBC-schemes with nonvanishing determinant, based on cyclic division algebras. Prior constructions of STBC-schemes from cyclic division algebra have either used transcendental elements, in which case the scheme may have vanishing determinant, or is available with nonvanishing determinant only for two, three, four, and six transmit antennas. In this correspondence, we construct STBC-schemes with nonvanishing determinant for the number of transmit antennas of the form 2/sup k/, 3/spl middot/2/sup k/, 2/spl middot/3/sup k/, and q/sup k/(q-1)/2, where q is any prime of the form 4s+3. For cyclic division algebra based STBC-schemes, in a recent work by Elia et al., the nonvanishing determinant property has been shown to be sufficient for achieving DM-G tradeoff. In particular, it has been shown that the class of STBC-schemes constructed in this correspondence achieve the optimal DM-G tradeoff. Moreover, the results presented in this correspondence have been used for constructing optimal STBC-schemes for arbitrary number of transmit antennas, by Elia et al.

For multiple-input multiple-output (MIMO) channels, at high spectral efficiencies, space-time block codes (STBC) must be designed to maximize the mutual information between the transmit and receive signals. In an uncoiled scheme (spatial multiplexing or V-BLAST), it is well-known that the Gaussian input distribution maximizes the mutual information. Hassibi and Hochwald (2002) introduced a linear dispersion (LD) framework for designing space-time codes, wherein any transmit codeword is a linear combination of a fixed set of matrices called the weight matrices. A LD space-time block code is said to be information-lossless if it does not disturb the maximum mutual information between the transmit and receive signals. In other words, a MIMO scheme using information-lossless LD space-time block codes has the same capacity as the uncoded scheme. Through computer search, information-lossless LD codes with better diversity compared to the uncoded system were found by Hassibi et al., and also by Heath et al. (2002). We give a general algebraic construction of high-rate information-lossless STBC, both square and rectangular, by restricting the weight matrices to those which form a finite group under matrix multiplication.

We present a new class of space-time-frequency block codes (STFBC) for multiantenna orthogonal frequency division multiplexing (MIMO-OFDM) transmissions over frequency selective Rayleigh fading channels. We show that these codes admit symbol-by-symbol decoding (decoupled decoding) when the number of nonzero taps of the channel impulse response is equal to two and they admit reduced complexity (1/2 of that of known schemes) for more than two channel taps. We also present simulation results to show that our codes perform better than the known codes.

Viewing an n-length vector over F(q/sup m/) (the finite field of q/sup m/ elements) as an m/spl times/n matrix over F/sub q/, by expanding each entry of the vector with respect to a basis of F(q/sup m/) over F/sub q/, the rank weight of the n-length vector over F(q/sup m/) is the rank of the corresponding m/spl times/n matrix over F/sub q/. Using the appropriate discrete Fourier transform (DFT), it is known that, under some conditions, n-length cyclic codes over F(q/sup m/), (n|q/sup m/-1 and m/spl les/n), have full-rank (=m). Using this result, we obtain designs for full-diversity space time block codes (STBCs) suitable for block-fading channels from n length cyclic codes over F(q/sup m/). These STBCs are suitable for m transmit antennas over signal sets matched to F/sub q/, where q=2 or q is a prime of the form 4k+1, (k=1, 2, ...). We also present simulation results which illustrate the performance of a few of these STBCs and show that our codes perform better than the well known codes for block-fading channels.

For the case of a quasi-static fading channel, high rate space-time trellis codes have already been constructed by concatenating multiple trellis coded modulation (MTCM) and space-time block codes (STBC), called the STBC-MTCM scheme. The focus in all these constructions was to increase the rate of transmission by using more than one orthogonal design while retaining the diversity advantage, and little attention was paid to increasing the coding gain advantage. We present a systematic approach by which STTCs can be constructed by the STBC-MTCM scheme, which achieve high rate, full diversity and increased coding gain advantage over the existing codes under certain conditions. Also we a present a systematic approach, to construct STTCs by STBC-MTCM codes which can achieve any given diversity for the case of block-fading channel. The codes constructed for block-fading channels trade-off the rate of transmission and the number of states of the trellis.

It is well known that in the Zheng-Tse optimal diversity-multiplexing tradeoff curve, the Alamouti scheme meets the point corresponding to the maximum diversity gain only, whereas V-BLAST meets only the point corresponding to the maximum multiplexing gain. We define asymptotic-information-lossless (AILL) designs and obtain a necessary and sufficient condition under which a design is AILL. Analogous to the condition that full-rank designs achieve the point corresponding to the zero multiplexing gain of the optimal tradeoff, we show that it is a necessary and sufficient condition for a design to be AILL to achieve the point corresponding to the zero diversity gain of the optimal tradeoff curve. Also, we obtain a lower bound on the tradeoff achieved by the designs from field extensions and division algebras. The lower bound for the designs from division algebras indicates that they achieve both the extreme points (corresponding to the zero diversity gain and zero multiplexing gain) of the optimal tradeoff curve.

We construct full-rank, rate-n space-time block codes (STBC), over any a priori specified signal set for n-transmit antennas using crossed-product division algebras and give a sufficient condition for these STBCs to be information lossless. A class of division algebras for which this sufficient condition is satisfied is identified. Simulation results are presented to show that STBCs constructed in this paper perform better than the best known codes, including those constructed from cyclic division algebras and also to show that they are very close to the capacity of the channel with QAM input.

A new transform is denned for the class of cocyclic group ring codes over a Galois ring, where the underlying group is Abelian and the cocycle is the Vandermonde-cocycle on the Abelian group. The class of Vandermonde-cocyclic (VC) group ring codes are characterized using this new transform by means of a structure theorem for VC group rings.

In this paper we show that the maximal rates of square quasiorthogonal designs (QOD) is upper bounded by 2a/2afor N=2atransmit antennas. We also show that known constructions of QODs achieve this bound with equality and are therefore maximal-rate QODs

We present a lower bound on the peak to average power ratio (PAPR) for the second order cosets of binary Reed-Muller code by classifying the codewords using their Walsh Hadamard transform (WHT) vectors. This result categorizes the second order cosets of binary Reed-Muller code as per their PAPR by observing their WHT spectrum.

We identify a cocycle on the dihedral group D/sub n/ of 2n elements which results in a new class of codes called consta-dihedral codes. We define a new transform for these codes and then characterize all the consta-dihedral codes using this new transform.

This paper shows that the codes from division algebras (Sethuraman et al., 2003) achieve the optimal diversity-multiplexing tradeoff for n transmit and n receive antennas for n=2,3,4 by simulation. It also present a lower bound for the tradeoff curve which shows that codes from division algebras for arbitrary number of transmit and receive antennas achieve points corresponding to zero diversity gain and zero multiplexing gain.

This work presents the construction of STBCs, using crossed-product algebras, for arbitrary number of transmit antennas over an a priori specified signal set. It obtains a condition under which these STBCs from arbitrary crossed-product algebras are information-lossless.

Viewing an n length vector over Fqmas an mtimesn matrix over Fq, by expanding each entry of the vector with respect to a basis of Fqmover Fq, the rank weight of the n length vector over Fqmis the rank of the corresponding mtimesn matrix over Fq. It is known that under some conditions, n-length cyclic codes over Fqm, (n|qm-1 and mlesn) have full rank. In this paper, using this result we obtain a design using which we construct full-rank space-time block codes (STBCs) for m transmit antennas over signal sets matched to Fqwhere q=2 or q is a prime of the form 4k+1. We also propose a construction of STBCs using n-length cyclic codes over Fqm, for r transmit antennas, where rlesn and r|m

In this paper we present a matrix characterization of AMDS codes and NMDS codes over Z/sub m/ and Abelian groups. A linear code with the ring of integers modulo is a subset closed under all linear combinations. An AMDS code is said to be near-MDS if its dual code is also AMDS.

Algebraic structure of codes over F q , closed under arbitrary abelian group G of permutations with exponent relatively prime to q, called G-invariant codes, is investigated using a transform domain approach. In particular, this general approach unveils algebraic structure of quasi-cyclic codes, abelian codes, cyclic codes, and quasi-abelian codes with restriction on G to appropriate special cases. Dual codes of G-invariant codes and self-dual G-invariant codes are characterized. The number of G-invariant self-dual codes for any abelian group G is found. In particular, this gives the number of self-dual l-quasi-cyclic codes of length ml over F q when (m,q)=1. We extend Tanner's approach for getting a bound on the minimum distance from a set of parity check equations over an extension field and outline how it can be used to get a minimum distance bound for a G-invariant code. Karlin's decoding algorithm for a systematic quasi-cyclic code with a single row of circulants in the generator matrix is extended to the case of systematic quasi-abelian codes. In particular, this can be used to decode systematic quasi-cyclic codes with columns of parity circulants in the generator matrix.

Recently, Blackford and Ray-Chaudhuri used transform domain techniques to permutation groups of cyclic codes over Galois rings. They used the same technique to find a set of necessary and sufficient conditions for extended cyclic codes of length 2/sup m/ over any subring of GR(4,m) to be affine invariant. Here, we use the same technique to find a set of necessary and sufficient conditions for extended cyclic codes of length p/sup m/ over any subring of GR(p/sup e/,m) to be affine invariant, for e=2 with arbitrary p and for p=2 with arbitrary e. These are used to find two new classes of affine invariant Bose-Chaudhuri-Hocquenghem (BCH) and generalized Reed-Muller (GRM) codes over Z/sub 2//sup e/ for arbitrary e and a class of affine invariant BCH codes over Z/sub p//sup 2/ for arbitrary prime p.

It is shown that two theorems regarding the existence of generalized linear processing orthogonal designs (GLPOD) are valid under more general conditions than those for which they have been stated and proved (for original paper see V. Tarokh et al., "Space-time block codes from orthogonal designs", ibid., vol. 45, p. 1456-1467 (1999)).

We study n-length consta-Abelian codes (a generalization of the well-known Abelian codes and constacyclic codes) over Galois rings of characteristic p/sup a/, where n and p are coprime. A twisted discrete Fourier transform (DFT) is used to generalize transform domain results of Abelian and constacyclic codes, to consta-Abelian codes. Further, we characterize consta-Abelian codes invariant under two kinds of monomials, whose underlying permutations are effected by: i) multiplying the coordinates with a unit in the appropriate mixed-radix representation of the coordinate positions and ii) shifting the coordinates by t positions. All the codes studied here belong to the class of quasi-twisted codes which are known to contain some good codes. We show that the dual of a consta-Abelian code invariant under the two monomials is also a consta-Abelian code closed under both monomials.

Space-time block codes (STBC) from orthogonal designs (OD), quasi-orthogonal designs (QOD) and co-ordinate interleaved orthogonal designs (CIOD) have been attracting wider attention due to their amenability for fast (single-symbol decoding for OD, CIOD and double-symbol decoding for QOD) ML decoding, and rate-one with full-rank over quasi-static fading channels. The importance of CIOD is due to the fact that, rate-one, full-rank, square ODs for arbitrary complex constellations exist only for 2 transmit antennas while such a CIOD exists for 2,3 and 4 transmit antennas with a slight restriction on the complex constellations (Zafar Ali Khan and B. Sundar Rajan, Proc. IEEE ISIT 2002, p.275, 2002; DRDO-IISc Tech. Report No. TR-PME-2002-17, 2002). These limitations motivate study of rectangular (non-square) designs. One way of obtaining rectangular designs is by deleting columns from square or non-square ODs or CIODs. We present a new construction of rectangular single-symbol decodable designs that have higher maximum mutual information than those obtained by deleting columns of CIODs and has lower peak-to-average-power ratio (PAPR). Simulation results are presented for three and five transmit antennas and compared with that of OD, QOD, CIOD to demonstrate the superiority of the proposed rectangular designs.

The diversity order and coding gain are crucial for the performance of a multiple antenna communication system. It is known that space-time trellis codes (STTC) can be used to achieve these objectives. In particular, we can use STTCs to obtain large coding gains. Many attempts have been made to construct STTCs which achieve full-diversity and good coding gains, though a general method of construction does not exist. Delay diversity code (rate-1) is known to achieve full-diversity, for any number of transmit antennas and any signal set, but does not give a good coding gain. A product distance code based delay diversity scheme (Tarokh, V. et al., IEEE Trans. Inform. Theory, vol.44, p.744-65, 1998) enables one to improve the coding gain and construct STTCs for any given number of states using coding in conjunction with delay diversity; it was stated as an open problem. We achieve such a construction. We assume a shift register based model to construct an STTC for any state complexity. We derive a sufficient condition for this STTC to achieve full-diversity, based on the delay diversity scheme. This condition provides a framework to do coding in conjunction with delay diversity for any signal constellation. Using this condition, we provide a formal rate-1 STTC construction scheme for PSK signal sets, for any number of transmit antennas and any given number of states, which achieves full-diversity and gives a good coding gain.

It is known that the Alamouti code is the only complex orthogonal design (COD) which achieves capacity and that only for the case of two transmit and one receive antennas. M.O. Damen et al. (see IEEE Trans. Inform. Theory, vol.48, no.3, p.753-60, 2002) gave a design for 2 transmit antennas, which achieves capacity for any number of receive antennas, calling it an information lossless STBC. We construct capacity achieving designs using cyclic division algebras for an arbitrary number of transmit and receive antennas. For the STBCs obtained using these designs, we present simulation results for those numbers of transmit and receive antennas for which Damen et al. also gave results, and show that our STBCs perform better than their's.

We study n-length Abelian codes over Galois rings with characteristic p/sup a/, where n and p are relatively prime, having the additional structure of being closed under the following two permutations: (i) permutation effected by multiplying the coordinates with a unit in the appropriate mixed-radix representation of the coordinate positions and (ii) shifting the coordinates by t positions. A code is t-quasi-cyclic (t-QC) if t is an integer such that cyclic shift of a codeword by t positions gives another codeword. We call the Abelian codes closed under the first permutation as unit-invariant Abelian codes and those closed under the second as quasi-cyclic Abelian (QCA) codes. Using a generalized discrete Fourier transform (GDFT) defined over an appropriate extension of the Galois ring, we show that unit-invariant Abelian and QCA codes can be easily characterized in the transform domain. For t=1, QCA codes coincide with those that are cyclic as well as Abelian. The number of such codes for a specified size and length is obtained and we also show that the dual of an unit-invariant t-QCA code is also an unit-invariant t-QCA code. Unit-invariant Abelian (hence unit-invariant cyclic) and t-QCA codes over Galois field F/sub p//sup l/ and over the integer residue rings are obtainable as special cases.

We present some general techniques for constructing full-rank, minimal-delay, rate at least one space-time block codes (STBCs) over a variety of signal sets for arbitrary number of transmit antennas using commutative division algebras (field extensions) as well as using noncommutative division algebras of the rational field /spl Qopf/ embedded in matrix rings. The first half of the paper deals with constructions using field extensions of /spl Qopf/. Working with cyclotomic field extensions, we construct several families of STBCs over a wide range of signal sets that are of full rank, minimal delay, and rate at least one appropriate for any number of transmit antennas. We study the coding gain and capacity of these codes. Using transcendental extensions we construct arbitrary rate codes that are full rank for arbitrary number of antennas. We also present a method of constructing STBCs using noncyclotomic field extensions. In the later half of the paper, we discuss two ways of embedding noncommutative division algebras into matrices: left regular representation, and representation over maximal cyclic subfields. The 4/spl times/4 real orthogonal design is obtained by the left regular representation of quaternions. Alamouti's (1998) code is just a special case of the construction using representation over maximal cyclic subfields and we observe certain algebraic uniqueness characteristics of it. Also, we discuss a general principle for constructing cyclic division algebras using the nth root of a transcendental element and study the capacity of the STBCs obtained from this construction. Another family of cyclic division algebras discovered by Brauer (1933) is discussed and several examples of STBCs derived from each of these constructions are presented.

An n /spl times/ l (l /spl ges/ n) space time block code (STBC) C consists of a finite number |C| of n /spl times/ l matrices with entries from the complex field. If the entries of the codeword matrices are from a complex signal set S or complex linear combinations of elements of S then the code is said to be over S. For quasi-static, flat fading channels a primary performance index of C is the minimum of the rank of the difference of any two codeword matrices, called the rank of the code. C is of full-rank if its rank is n and is of minimal-delay if l = n. The rate of the code R in symbols per channel use is given by 1/l log/sub |S|/(|C|). It is well known that orthogonal designs provide rate 1, mimial-delay, full-rank STBCs with linear decodability, but exist only for n = 2 (Alamouti code) for complex constellations and for n = 2, 4 and 8 only for real constellations. In this paper, we present some general techniques for constructing rate 1, full-rank, minimal-delay STBCs over S using non-commutative division algebras of the rational field /spl Qopf/ embedded in matrix rings. Using two ways of embedding non-commutative division algebras into matrices, namely, the left regular representation and representation over maximal cyclic subfields, we observe that (i) the Alamouti's (1998) code and real orthogonal designs for n = 2 and 4 are just special cases of our construction and (ii) algebraically, the uniqueness of the Alamouti code is due to the fact: Hamilton's quaternions H is the only non-commutative division algebra which has /spl Copf/ as a maximal subfield.

An n/spl times/l (l/spl ges/n) space time block code (STBC) C over a complex signal set S consists of a finite number of n/spl times/l matrices with elements from S. For quasi-static, flat fading channels, a primary performance index of C is the minimum of the rank of the difference of any two matrices, called the rank of the code. C is of full rank if its rank is n and is of minimum delay if l=n. The rate R, in bits per second per Hertz, of a full rank minimum delay code over S is upper bounded by log/sub 2/|S| and those meeting this bound are referred to as full rate codes. A full rank, full rate, minimum delay, space time block code over S is said to be rate-optimal. We present some general techniques for constructing rate-optimal codes from field extensions embedded in matrix rings. Working mostly with cyclotomic fields, we construct rate-optimal n/spl times/n STBCs over m-PSK signal sets for arbitrary values of m and a large set of values of n.

Construction of rate-optimal full-diversity space-time block codes (STBC) over symmetric PSK signal sets using cyclotomic field extensions of the field of rational /spl Qopf/ was reported previously, and for a variety of other signal sets using non-cyclotomic field extensions. Fields are commutative division algebras. Construction of full-rate STBCs with full-diversity using a class of non-commutative division algebras (cyclic division algebras) was also reported previously and the Alamouti code was shown to be a special case with an algebraic uniqueness property. In this paper, we present the basic principle behind these constructions and also obtain full-diversity, full-rate STBCs using a different class of non-commutaive division algebra constructed by Brauer. The interrelationship between codes constructed from division algebras, linear dispersion codes and codes from orthogonal designs is discussed.

A code is s-quasi-cyclic (s-QC) if there is an integer s such that cyclic shift of a codeword by s-positions is also a codeword. For s = 1, cyclic codes are obtained. A dyadic code is a code which is closed under all dyadic shifts. An s-QC dyadic (s-QCD) code is one which is both s-QC and dyadic. QCD codes with s = 1 give codes that are cyclic and dyadic (CD). We obtain a simple characterization of all QCD codes (hence of CD codes) over any field of odd characteristic using Walsh-Hadamard transform defined over that finite field. Also, it is shown that dual a code of an s-QCD code is also an s-QCD code and s-QCD codes for a given dimension are enumerated for all possible values of s.

In this correspondence, in an extension of Piret's bound for codes over phase-shift keying (PSK) signal sets, we investigate the application of the Gilbert-Varshamov (GV) bound to a variety of distance-uniform (DU) signal sets in Euclidean space. It is shown that four-dimensional signal sets matched to binary tetrahedral, binary octahedral, and binary icosahedral groups lead to better bounds compared to the bounds for signal sets matched to dicyclic groups with the same number of signal points and comparable symmetric PSK signal sets.

The diversity order is crucial for the performance of communication systems over fading channels. It has been shown by Zehavi (1992) that the diversity and hence performance of coded modulation over fading channels can be improved by bit-wise interleaving at the encoder output, and by using an appropriate soft decision metric as an input to the Viterbi decoder. A related approach is coordinate interleaving whereby the signal space coordinates are interleaved before transmission. In this paper we combine both bit interleaving and coordinate interleaving to increase the diversity order. The resulting system is referred to here as bit and coordinate interleaved coded modulation (BCICM). The pairwise probability of error is also derived, which shows that by proper design the diversity order can be doubled over bit interleaved coded modulation (BICM), for two dimensional signal sets. Simulation results for rate 2/3, 4-state 8-PSK coded modulation schemes show that BCICM significantly outperforms all known coded modulation (symbol or bit interleaved) schemes.

A length n group code over a group G is a subgroup of G/sup n/ under component-wise group operation. Two-level group codes over the class of generalized quaternion groups, Q(2/sup m/), m/spl ges/3, are constructed using a binary code and a code over Z(2/sup m-1/), the ring of integers modulo 2/sup m-1/ as component codes and a mapping f from Z/sub 2//spl times/Z(2/sup m-1/)to Q(2/sup m/). A set of necessary and sufficient conditions on the component codes is derived which will give group codes over Q(2/sup m/). Given the generator matrices of the component codes, the computational effort involved in checking the necessary and sufficient conditions is discussed. Starting from a four-dimensional signal set matched to Q(2/sup m/), it is shown that the Euclidean space codes obtained from the group codes over Q(2/sup m/) have Euclidean distance profiles which are independent of the coset representative selection involved in f. A closed-form expression for the minimum Euclidean distance of the resulting group codes over Q(2/sup m/) is obtained in terms of the Euclidean distances of the component codes. Finally, it is shown that all four-dimensional signal sets matched to Q(2/sup m/) have the same Euclidean distance profile and hence the Euclidean space codes corresponding to each signal set for a given group code over Q(2/sup m/) are automorphic Euclidean-distance equivalent.

A length n group code over a group G is a subgroup of G/sup n/ under component-wise group operation. Group codes over dihedral groups D/sub M/, with 2M elements, that are two-level constructible using a binary code and a code over Z/sub M/ residue class integer ring modulo M, as component codes are studied for arbitrary M. A set of necessary and sufficient conditions on the component codes for the two-level construction to result in a group code over D/sub M/ are obtained. The conditions differ for M odd and even. Using two-level group codes over D/sub M/ as label codes, the performance of a block-coded modulation scheme is discussed under all possible matched labelings of 2M-APSK and 2M-SPSK (asymmetric and symmetric PSK) signal sets in terms of the minimum squared Euclidean distance. Matched labelings that lead to automorphic Euclidean distance equivalent codes are identified. It is shown that depending upon the ratio of Hamming distances of the component codes some labelings perform better than others. The best labeling is identified under a set of restrictive conditions. Finally, conditions on the component codes for phase rotational invariance properties of the signal space codes are discussed.

We present an efficient algorithm for computing the minimal trellis for a group code over a finite Abelian group, given a generator matrix for the code. We also show how to compute a succinct representation of the minimal trellis for such a code, and present algorithms that use this information to efficiently compute local descriptions of the minimal trellis. This extends the work of Kschischang and Sorokine (1995), who handled the case of linear codes over fields. An important application of our algorithms is to the construction of minimal trellises for lattices. A key step in our work is handling codes over cyclic groups C/sub p//spl alpha/, where p is a prime. Such a code can be viewed as a submodule over the ring Z/sub p//spl alpha/. Because of the presence of zero-divisors in the ring, submodules do not share the useful properties of vector spaces. We get around this difficulty by restricting the notion of linear combination to p-linear combination, and introducing the notion of a p-generator sequence, which enjoys properties similar to that of a generator matrix for a vector space.

We present an efficient algorithm for computing the minimal trellis for a group code over a finite abelian group, given a generator matrix for the code. We also show how to compute a succinct representation of the minimal trellis for such a code, and present algorithms that use this information to compute efficiently local descriptions of the minimal trellis. This extends the work of Kschischang and Sorokine (see ibid., vol.41, no.6, p.1926-37, 1995), who treated the case of linear codes over fields. An important application of our algorithms is to the construction of minimal trellises for lattices. A key step in our work is handling codes over cyclic groups C/sub p//spl alpha/, where p is a prime. Such a code can be viewed as a module over the ring Z/sub p//spl alpha/. Because of the presence of zero divisors in the ring, modules do not share the useful properties of vector spaces. We get around this difficulty by restricting the notion of linear combination to a p-linear combination, and by introducing the notion of a p-generator sequence, which enjoys properties similar to those of a generator matrix for a vector space.

An (n,k) group code over a group G is a subset of G/sup n/ which forms a group under componentwise group operation and can be defined in terms of n-k homomorphisms from G/sup k/ to G. The set of homomorphisms which define maximum distance separable (MDS) group codes defined over cyclic groups are characterized. Each defining homomorphism can be specified by a set of k endomorphisms of G. A matrix is associated with the k(n-k) defining endomorphisms of the code and necessary and sufficient conditions for this matrix to define an MDS code over cyclic groups is proved. Using this matrix characterization it is proved that over a cyclic group with M elements, where M=p/sub 1//sup d(1)/p/sub 2//sup d(2)//spl middot//spl middot//spl middot/p/sub m//sup d(m)/,(k+s,k) MDS group codes, for all s,k/spl ges/2, do not exist if max {s,k}/spl ges/min {p/sub 1/,p/sub 2/,/spl middot//spl middot/,p/sub m/}. Finally, it is shown that the dual code of an MDS group code over C/sub M/, a cyclic group with M elements, is also an MDS group code.

A generalized discrete Fourier transform defined over an appropriate extension ring is given that is suitable to characterize Abelian codes over residue class integer rings Z/sub m/. The characterization is in terms of generalized discrete Fourier transform components taking values from certain ideals of the extension ring. It is shown that the results known for cyclic codes over Z/sub m/, like the simple characterization of dual and self-dual codes and the nonexistence of self-dual codes for certain values of code parameters, extend to Abelian codes over Z/sub m/ as well.>

Abelian codes constitute a class of codes that includes cyclic codes as a special case. It is shown that the general class of abelian codes can be characterized in the transform domain using the discrete Fourier transform (DFT) over finite fields with the appropriate mixed radix number system as the indexing scheme for DFT coefficients. A simple transform domain description for dual codes of abelian codes is also obtained. Using this description the idempotent generator of the dual of a given abelian code can be easily obtained. Finally, it is shown that in the case of cyclic codes which can be considered as abelian codes also, one can work in smaller extension fields compared to the extension fields if they were considered as cyclic codes only.>