The group capacity of a discrete memoryless channel$(\mathcal {X},\mathcal {Y},W_{Y|X})$is characterized with maximal probability of error in of[1, Sec. II]. There is a mistake in the proof of achievability as given in Section VII.A. It is correctly shown on page 2408–2409 that\begin{equation*} \lim _{n \rightarrow \infty } \max _{a} \mathbb {E} \left [{ P(E(a)) }\right ] =0 \end{equation*}if for all$\hat {\theta } \neq \boldsymbol {s}$,\begin{align*}&\hspace {-0.5pc}R \frac {\sum _{(p,s)\in \mathcal {S}(G)} (s- \hat {\theta }_{p,s}) w_{p,s} \log p}{\sum _{(p,s) \in \mathcal {S} (G)} s w_{p,s} \log q} \\&\qquad \qquad \quad \qquad <\log |H_{\eta ^{*}+\hat {\theta }}|-H(X_{\eta ^{*},b}|Y,[X_{\eta ^{*},b}]_{\hat {\theta }}) - O(\epsilon ). \end{align*}However it is incorrectly claimed that the achievability conditions are: for all$\hat {\theta } \neq \pmb {s}$,\begin{equation*} R\le \frac {1}{1-\omega _{\hat {\theta }}} I(X_{\eta ^{*},b};Y|[X_{\eta ^{*},b}]_{\hat {\theta }}). \end{equation*}Our original objective was to characterize the average error group capacity of a discrete memoryless channel. The average error is more widely used than the maximal error. Although we had the proof of achievability for the average error case, we could not prove the converse. So we settled for characterizing the maximal error group capacity. In light of the above error, we have the following resolution.

We consider the problem of communication over a three-user discrete memoryless interference channel (3-IC). The current known coding techniques for communicating over an arbitrary 3-IC are based on message splitting, superposition coding, and binning using independent and identically distributed (i.i.d.) random codebooks. In this paper, we propose a new ensemble of codes-partitioned coset codes (PCCs)-that possess an appropriate mix of empirical and algebraic closure properties. We develop coding techniques that exploit the algebraic closure property of PCC to enable interference alignment over general 3-IC. We analyze the performance of the proposed coding technique to derive an achievable rate region for the general discrete 3-IC. Additive and non-additive examples are identified for which the derived achievable rate region is the capacity, moreover, strictly larger than the current known largest achievable rate regions based on the i.i.d. random codebooks.

In this paper, we study the asymptotic performance of Abelian group codes for the channel coding problem for arbitrary discrete (finite alphabet) memoryless channels as well as the lossy source coding problem for arbitrary discrete (finite alphabet) memoryless sources. For the channel coding problem, we find the capacity characterized in a single-letter information-theoretic form. This simplifies to the symmetric capacity of the channel when the underlying group is a field. For the source coding problem, we derive the achievable rate-distortion function that is characterized in a single-letter information-theoretic form. When the underlying group is a field, it simplifies to the symmetric rate-distortion function. We give several illustrative examples. Due to the nonsymmetric nature of the sources and channels considered, our analysis uses a synergy of information-theoretic and group-theoretic tools.

It is shown that polar coding schemes achieve the known achievable rate regions for several multi-terminal communications problems including lossy distributed source coding, multiple access channels and multiple descriptions coding. The results are valid for arbitrary alphabet sizes (binary or non-binary) and arbitrary distributions (symmetric or asymmetric).

We introduce a scheme for the binary one-help-one distributed source coding problem using two layers of codes. The primary code is of constant finite block-length and the secondary code has a block-length approaching infinity. The achievable rate-distortion region for this scheme is derived for the binary one-help-one problem. It is shown that the scheme achieves the common component rate-distortion region in the case when the sources have a common component, while if a common component is not present (i.e. replaced with highly correlated functions of the two inputs) it improves upon existing achievable bounds. We show that as the block-length of the primary code is increased, the transmission rate required in the scheme decreases, reaches its minimum at some finite value and then increases. This phenomenon is not typically seen in traditional schemes used in multi-terminal source coding.

It is shown that polar codes, with their original (u,u+v) kernel, achieve the symmetric capacity of discrete memoryless channels with arbitrary input alphabet sizes. It is shown that in general, channel polarization happens in several, rather than only two levels so that the synthesized channels are either useless, perfect or “partially perfect.” Any subset of the channel input alphabet which is closed under addition induces a coset partition of the alphabet through its shifts. For any such partition of the input alphabet, there exists a corresponding partially perfect channel whose outputs uniquely determine the coset to which the channel input belongs. By a slight modification of the encoding and decoding rules, it is shown that perfect transmission of certain information symbols over partially perfect channels is possible. Our result is general regarding both the cardinality and the algebraic structure of the channel input alphabet; i.e., we show that for any channel input alphabet size and any Abelian group structure on the alphabet, polar codes are optimal. Due to the modifications, we make to the encoding rule of polar codes, the constructed codes fall into a larger class of structured codes called nested group codes.

The 3-user discrete memoryless interference channel is considered in this paper. We provide a new inner bound (achievable rate region) to the capacity region for this channel. This inner bound is based on a new class of code ensembles based on asymptotically good nested linear codes. This achievable region is strictly superior to the straightforward extension of Han-Kobayashi rate region from the case of two-users to three-users. This rate region is characterized using single-letter information quantities. We consider examples to illustrate the rate region.

In this paper, we show that nested lattice codes achieve the capacity of arbitrary continuous channels with or without non-causal state information at the transmitter. We also show that nested lattice codes are optimal for source coding with or without non-causal side information at the receiver for arbitrary continuous sources. We show the optimality of lattice codes for the Gelfand-Pinsker and Wyner-Ziv problems in their most general settings.

In this paper, we show that good structured codes over non-Abelian groups do exist. Specifically, we construct codes over the smallest non-Abelian group D6and show that the performance of these codes is superior to the performance of Abelian group codes of the same alphabet size. This promises the possibility of using non-Abelian codes for multi-terminal settings where the structure of the code can be exploited to gain performance. We also show that for the problem of computation over MAC, these codes are superior to random codes in certain cases.

For most discrete memoryless channels, there does not exist a linear code which uses all of the channel's input symbols. Therefore, linearity of the code for such channels is a very restrictive condition and there should be a loosening of the algebraic structure of the code to a degree that the code can admit any channel input alphabet. For any channel input alphabet size, there always exists an Abelian group structure defined on the alphabet. We investigate the capacity of Abelian group codes over discrete memoryless channels and provide lower and upper bounds on the capacity.

In this paper an extension of the sparse decomposition problem is considered and an algorithm for solving it is presented. In this extension, it is known that one of the shifted versions of a signal s (not necessarily the original signal itself) has a sparse representation on an overcomplete dictionary, and we are looking for the sparsest representation among the representations of all the shifted versions of s. Then, the proposed algorithm finds simultaneously the amount of the required shift, and the sparse representation. Experimental results emphasize on the performance of our algorithm.