We study communication with noiseless feedback over Gaussian channels with stationary autoregressive noise of arbitrary finite order. We introduce a class of Gaussian feedback coding schemes, called SK(2), in which the message process follows a second-order deterministic recursion, and derive a closed-form characterization of its maximal achievable rate under an average-power constraint. As a first-order benchmark, we formulate the SK(1) scheme and show that it provides the branch-complete and sign-consistent reformulation of Butman's equal-energy linear-feedback construction. The SK(2) coding scheme achieves feedback capacity for the additive white Gaussian noise channel and stationary AR(1) Gaussian channels. For certain stationary AR(2) Gaussian channels, genuinely second-order SK(2) scheme strictly outperforms SK(1); for the subclass obtained by interleaving two independent AR(1) noise processes, SK(2) also achieves feedback capacity. These results show that first-order SK/Butman coding scheme is not universally optimal beyond first-order autoregressive noise and disprove the corrected form of Butman's conjecture.

In this paper, we propose and studyr-minimal codes, a natural extension of minimal codes which have been extensively studied with respect to Hamming metric, rank metric and sum-rank metric. We first proposer-minimal codes in a general setting where the ambient space is a finite dimensional left module over a division ring and is supported on a lattice. We characterize minimal subcodes andr-minimal codes, derive a general singleton bound, and give existence results forr-minimal codes by using combinatorial arguments. We then considerr-minimal rank metric codes over a field extension E/F of degreem, where E can be infinite unless otherwise specified. We characterize these codes in terms of cuttingr-blocking sets, generalized rank weights of the codes and those of the dual codes, and classify codes whoser-dimensional subcodes have constant rank support weight. Next, with the help of the evasiveness property of cuttingr-blocking sets and some upper bounds for the dimensions of evasive subspaces, we derive several lower and upper bounds for the minimal length ofr-minimal codes. Furthermore, when E is finite, we establish a general upper bound which generalizes and improves the counterpart for minimal codes in the literature. As a corollary, we show that ifm= 3, then for anyk⩾ 2, the minimal length ofk-dimensional minimal codes is equal to 2k. To the best of our knowledge, whenm⩾ 3, there is no known explicit formula for the minimal length ofk-dimensional minimal codes for arbitrarykin the literature.

In this paper, we consider a strongly reachable multiple unicast network with$k$pairs of sender and receivers, and we show that the Langberg-Médard multiple unicast conjecture holds for such a network under the assumption that it is supported on a collapsed backbone that takes the form of rooted binary tree.

We consider the continuous-time ARMA(1,1) Gaussian channel and derive its feedback capacity in closed form. More specifically, the channel is given by$\boldsymbol {y}(t) =\boldsymbol {x}(t) +\boldsymbol {z}(t)$, where the channel input$\{\boldsymbol {x}(t) \}$satisfies average power constraint P and the noise$\{\boldsymbol {z}(t)\}$is a first-order autoregressive moving average (ARMA(1,1)) Gaussian process satisfying$\boldsymbol {z}^{\prime } (t)+\kappa \boldsymbol {z}(t)=(\kappa +\lambda)\boldsymbol {w}(t)+\boldsymbol {w}^{\prime } (t)$, where$\kappa \gt 0,~\lambda \in \mathbb {R}$and$\{\boldsymbol {w}(t) \}$is a white Gaussian process with unit double-sided spectral density. We show that the feedback capacity of this channel is equal to the unique positive root of the equation$P(x+\kappa)^{2} = 2x(x+\vert \kappa +\lambda \vert)^{2}$when$-2\kappa \lt \lambda \lt 0$and is equal to$P/2$otherwise. Among many others, this result shows that, as opposed to a discrete-time additive Gaussian channel, feedback may not increase the capacity of a continuous-time additive Gaussian channel even if the noise process is colored. The formula enables us to conduct a thorough analysis of the effect of feedback on the capacity for such a channel. We characterize when the feedback capacity equals or doubles the non-feedback capacity; moreover, we disprove continuous-time analogues of the half-bit bound and Cover’s$2P$conjecture for discrete-time additive Gaussian channels.

In this paper, we examine the Rényi entropy rate of stationary ergodic processes. For a special class of stationary ergodic processes, we prove that the Rényi entropy rate always exists and can be approximated by its defining sequence at most polynomially; moreover, using the Markov approximation method, we show that the Rényi entropy rate can be exponentially approximated by that of the Markov approximating sequence, as the Markov order goes to infinity. For the general case, by constructing a counterexample, we disprove the conjecture that the Rényi entropy rate of a general stationary ergodic process always converges to its Shannon entropy rate as$\alpha $goes to 1.

Let$\mathbf {H}$be the Cartesian product of a family of left modules over a ring$S$, indexed by a finite set$\Omega $. We study the MacWilliams extension property (MEP) with respect to$(\mathbf {P},\omega)$-weight on$\mathbf {H}$, where$\mathbf {P}=(\Omega,\preccurlyeq _{\mathbf {P}})$is a poset and$\omega:\Omega \longrightarrow \mathbb {R}^{+}$is a weight function. We first give a characterization of the group of$(\mathbf {P},\omega)$-weight isometries of$\mathbf {H}$, which is then used to show that MEP implies the unique decomposition property (UDP) of$(\mathbf {P},\omega)$, which, for the case that$\omega $is identically 1, further implies that$\mathbf {P}$is hierarchical. When$\mathbf {P}$is hierarchical or$\omega $is identically 1, with some weak additional assumptions, we give necessary and sufficient conditions for$\mathbf {H}$to satisfy MEP with respect to$(\mathbf {P},\omega)$-weight in terms of MEP with respect to Hamming weight. With the help of these results, when$S$is a finite field, we compare MEP with various well studied coding-theoretic properties including the property of admitting MacWilliams identity (PAMI), reflexivity of partitions, UDP, transitivity of the group of isometries and whether$(\mathbf {P},\omega)$induces an association scheme; in particular, we show that MEP is always stronger than all the other properties.

We derive an explicit formula of the feedback capacity for a continuous-time OU-colored AWGN channel. Among many others, this result shows that at least in some cases, the continuous-time Schalkwijk-Kailath coding scheme achieves the feedback capacity for such a channel, and feedback may not increase the capacity of a continuous-time ACGN channel even if the noise process is colored.

Let$\mathbf {H}$be the Cartesian product of a family of finite abelian groups. Via a polynomial approach, we give sufficient conditions for a partition of$\mathbf {H}$induced by weighted poset metric to be reflexive, which also become necessary for some special scenarios. Moreover, by examining the roots of the Krawtchouk polynomials, we give sufficient conditions for a partition of$\mathbf {H}$induced by combinatorial metric to be non-reflexive, and then give several examples of non-reflexive partitions. When$\mathbf {H}$is a vector space over a finite field$\mathbb {F}$, we consider the property of admitting MacWilliams identity (PAMI) and the MacWilliams extension property (MEP) for partitions of$\mathbf {H}$. More specifically, under some invariance assumptions, we show that two partitions of$\mathbf {H}$admit MacWilliams identity if and only if they are mutually dual and reflexive, and any partition of$\mathbf {H}$satisfying MEP is in fact an orbit partition induced by some subgroup of$\mathrm {Aut}\,_{\mathbb {F}}(\mathbf {H})$, which is necessarily reflexive. Furthermore, we show that the aforementioned non-reflexive partitions induced by combinatorial metric do not satisfy MEP, which further enables us to disprove a conjecture proposed by Pinheiro et al., (2019).

For $R \triangleq Ma{t_m}({\mathbb{F}})$, the ring of all m × m matrices over the finite field ${\mathbb{F}}$ with $|{\mathbb{F}}| = q$, and the left R-module $A \triangleq Ma{t_{m,k}}({\mathbb{F}})$ with m + 1 ⩽ k, by deriving the minimal length of solutions of the related isometry equation, Dyshko has proved in [3], [4] that the minimal code length n for Annot satisfying the MacWilliams extension property (MEP) with respect to Hamming weight is equal to $\prod\nolimits_{i = 1}^m {\left( {{q^i} + 1} \right)}$. In this paper, using the Möbius functions, we derive the minimal length of nontrivial solutions of the isometry equation for a finite lattice. For the finite vector space ${\mathbf{H}} \triangleq \prod\nolimits_{i \in \Omega } {{{\mathbb{F}}^{{k_i}}}}$, a poset P = (Ω, ≼P) and a map ω: Ω → ℝ+give rise to the (P, ω)-weight on H, which has been proposed by Hyun, Kim and Park in [18]. For such a weight, we study the relations between the MEP and other properties including admitting MacWilliams identity, Fourier-reflexivity of involved partitions and the Unique Decomposition Property (UDP) defined for (P, ω). We give necessary and sufficient conditions for H to satisfy the MEP with the additional assumption that either P is hierarchical or ω is identically 1, i.e., (P, ω)-weight coincides with P-weight, which further allow us to partly answer a conjecture proposed by Machado and Firer in [22].

Let H be the cartesian product of a family of abelian groups indexed by a nonempty finite set Ω. A given poset P = (Ω, ≼P) and a map ω : Ω → ℝ+give rise to the (P, ω)-weight on H, which further leads to a partition $\mathcal{Q}\left( {{\text{H}},{\text{P}},\omega } \right)$ of H. For the case that H is finite, we give sufficient conditions for two codewords to belong to the same block of Λ, the dual partition of $\mathcal{Q}\left( {{\text{H}},{\text{P}},\omega } \right)$, and sufficient conditions for $\mathcal{Q}\left( {{\text{H}},{\text{P}},\omega } \right)$ to be Fourier-reflexive. By relating the involved partitions with certain polynomials, we show that such sufficient conditions are also necessary if P is hierarchical and ω is integer valued. With H further set to be a finite vector space over a finite field $\mathbb{F}$, from a partition perspective, we extend the property of "admitting MacWilliams identity" to arbitrary pairs of partitions of H, and prove that a pair of $\mathbb{F}$-invariant partitions (Λ, Γ) with |Λ| = |Γ| admits MacWilliams identity if and only if (Λ, Γ) is a pair of mutually dual Fourier-reflexive partitions. Such a result is applied to the partition $\mathcal{Q}\left( {{\text{H}},{\text{P}},\omega } \right)$. Finally, with H set to be a (possibly infinite) left module over a ring S, we show that each (P, ω)- weight isometry of H uniquely induces an order automorphism of P, which further leads to a group homomorphism from the group of (P, ω)-weight isometries to Aut (P), whose kernel consists of isometries preserving the P-support.

In 1991, Wei proved a duality theorem that established an interesting connection between the generalized Hamming weights of a linear code and those of its dual code. Wei’s duality theorem has since been extensively studied from different perspectives and extended to other settings. In this paper, we re-examine Wei’s duality theorem and its various extensions, henceforth referred to as Wei-type duality theorems, from a new Galois connection perspective. Our approach is based on the observation that the generalized Hamming weights and the dimension/length profiles of a linear code form a Galois connection. The central result of this paper is a general Wei-type duality theorem for two Galois connections between finite subsets of$\mathbb {Z}$, from which all the known Wei-type duality theorems can be recovered. As corollaries of our central result, we prove new Wei-type duality theorems for$w$-demi-matroids defined over finite sets and$w$-demi-polymatroids defined over modules with a composition series, which further allows us to unify and generalize all the known Wei-type duality theorems established for codes endowed with various metrics.

The Langberg-Médard multiple unicast conjecture claims that for a strongly reachable$k$-pair network, there exists a feasible multi-flow with rate$(1,1, {\dots },1)$. In this paper, we confirm the conjecture for$k=3$.

For a continuous-time additive white Gaussian noise (AWGN) channel with possible feedback, it has been shown that as sampling gets infinitesimally fine, the mutual information of the associative discrete-time channels converges to that of the original continuous-time channel. We give in this paper more quantitative strengthenings of this result, which, among other implications, characterize how over-sampling approaches the true mutual information of a continuous-time Gaussian channel with bandwidth limit. The assumptions in our results are relatively mild. In particular, for the non-feedback case, compared to the Shannon-Nyquist sampling theorem, a widely used tool to connect continuous-time Gaussian channels to their discrete-time counterparts that requires the band-limitedness of the channel input, our results only require some integrability conditions on the power spectral density function of the input.

We propose two modified versions of the classical gradient ascent method to compute the capacity of finite-state channels with Markovian inputs. For the case that the channel mutual information rate is strongly concave in a parameter taking values in a compact convex subset of some Euclidean space, our first algorithm proves to achieve polynomial accuracy in polynomial time and, moreover, for some special families of finite-state channels our algorithm can achieve exponential accuracy in polynomial time under some technical conditions. For the case that the channel mutual information rate may not be strongly concave, our second algorithm proves to be at least locally convergent.

Let$\mathbf {H}$be the cartesian product of a family of finite abelian groups indexed by a finite set$\Omega $. A given poset (i.e., partially ordered set)$\mathbf {P}=(\Omega,\preccurlyeq _{\mathbf {P}})$gives rise to a poset metric on$\mathbf {H}$, which further leads to a partition$\mathcal {Q}(\mathbf {H},\mathbf {P})$of$\mathbf {H}$. We prove that if$\mathcal {Q}(\mathbf {H},\mathbf {P})$is Fourier-reflexive, then its dual partition$\Lambda $coincides with the partition of$\hat {\mathbf {H}}$induced by$\mathbf {\overline {P}}$, the dual poset of$\mathbf {P}$, and moreover,$\mathbf {P}$is necessarily hierarchical. This result establishes a conjecture proposed by Gluesing-Luerssen in Gluesing-Luerssen, 2015. We also show that with some other assumptions,$\Lambda $is finer than the partition of$\hat {\mathbf {H}}$induced by$\mathbf {\overline {P}}$. In addition, we give some necessary and sufficient conditions for$\mathbf {P}$to be hierarchical, and for the case that$\mathbf {P}$is hierarchical, we give an explicit criterion for determining whether two codewords in$\hat {\mathbf {H}}$belong to the same block of$\Lambda $. We prove these results by relating the involved partitions with certain family of polynomials, a generalized version of which is also proposed and studied to generalize the aforementioned results.

Let$\mathrm{H}=\prod\nolimits_{i\in\Omega}H_{i}$be the cartesian product of finite abelian groups$H_{i}$indexed by a finite set$\Omega$. Any partition of H gives rise to a dual partition of its character group$\hat{\mathrm{H}}$. A given poset (i.e., partially ordered set) P on$\Omega$gives rise to the corresponding poset metric on H, which further leads to a partition$\Gamma$of H. We prove that if$\Gamma$is Fourier-reflexive, then its dual partition$\hat{\Gamma}$coincides with the partition of$\hat{\mathrm{H}}$induced by$\overline{\mathrm{P}}$, the dual poset of P, and moreover, P is necessarily hierarchical. This result establishes a conjecture proposed by Heide Gluesing-Luerssen in [4]. We also show that with some other assumptions,$\hat{\Gamma}$is finer than the partition of$\hat{\mathrm{H}}$induced by$\overline{\mathrm{P}}$. We prove these results by relating the partitions with certain family of polynomials, whose basic properties are studied in a slightly more general setting.

The Langberg-Médard multiple unicast conjecture claims that for a strongly reachable k-pair network, there exists a multi-flow with rate (1,1,...,1). In this paper, we show that the conjecture holds true for stable 3-pair networks.

In this paper, we consider a discrete channel with inter-cell interference (ICI) as a model for NAND flash memory. We derive an explicit formula for the mutual information rate when the input is Markovian. Using this formula, we obtain the asymptotics of the channel capacity in the high signal-to-noise (SNR) regime.

A renowned information-theoretic formula by Shannon expresses the mutual information rate of a white Gaussian channel with a stationary Gaussian input as an integral of a simple function of the power spectral density of the channel input. We give in this paper a rigorous yet elementary proof of this classical formula. As opposed to all the conventional approaches, which either rely on heavy mathematical machineries or have to resort to some "external" results, our proof, which hinges on a recently proven sampling theorem, is elementary and self- contained, only using some well-known facts from basic calculus and matrix theory.

We propose a modified version of the classical gradient descent method to compute the capacity of finite-state channels with Markovian input. Under some concavity assumptions, our algorithm proves to achieve polynomial accuracy in polynomial time for general finite-state channels. Moreover, for some special families of finite-state channels, our algorithm can achieve exponential accuracy in polynomial time.

Consider an acyclic directed graph $G$ with sources $s_1, s_2, \ldots,s_n$ and sinks $r_1, r_2, \ldots, r_n$. For $i=1, 2, \ldots,n$, let $c_i$ denote the size of the minimum edge cut between $s_i$ and $r_i$, which, by Menger's theorem, implies that there exists a group of $c_i$ edge-disjoint paths from $s_i$ to $r_i$. Although they are edge disjoint within the same group, the above-mentioned edge-disjoint paths from different groups may merge with each other (or, roughly speaking, share a common subpath). In this paper we show that by choosing these paths appropriately, the number of mergings among all these edge-disjoint paths is always bounded by a finite function $\mathcal{M}(c_1, c_2, \ldots, c_n)$, which is independent of the size of $G$. Moreover, we prove some elementary properties of $\mathcal{M}(c_1, c_2, \dots, c_n)$, derive exact values of $\mathcal{M}(1, c)$ and $\mathcal{M}(2, c)$, and establish a scaling law of $\mathcal{M}(c_1, c_2)$ when one of the parameters is fixed.

It is well known that the problem of computing the feedback capacity of a stationary Gaussian channel can be recast as an infinite-dimensional optimization problem; moreover, necessary and sufficient conditions for the optimality of a solution to this optimization problem have been characterized, and based on this characterization, an explicit formula for the feedback capacity has been given for the case that the noise is a first-order autoregressive moving-average Gaussian process. In this paper, via a simple “change of variables” trick, we further examine the above-mentioned infinite-dimensional optimization problem. We prove that unless the Gaussian noise is white, its optimal solution is unique, and we propose an algorithm to recursively compute the unique optimal solution, which is guaranteed to converge in theory and features an efficient implementation for a suboptimal solution in practice. Furthermore, for the case, that the noise is a $k$ -th order autoregressive moving-average Gaussian process, we give a relatively more explicit formula for the feedback capacity; more specifically, the feedback capacity is expressed as a simple function evaluated at a solution to a system of polynomial equations.

The Langberg-Médard k-Unicast Conjecture states that for any strongly reachable k-pair network, there exists a multi-flow with rate (1, 1, ..., 1). In this paper, for k=3,4, we construct multi-flows with rate ([11/12], [11/12],..., [11/12]), which improves the previous result ([8/9], [8/9], ..., [8/9]), and we further prove that our constructions are optimal within the proposed framework.

We give a counterexample to the vector generalization of Costa's entropy power inequality due to Liu et al. In particular, the claimed inequality can fail if the matrix-valued parameter in the convex combination does not commute with the covariance of the additive Gaussian noise. Conversely, the inequality holds if these two matrices commute.

In this paper, we examine an input-constrained erasure channel and we characterize the asymptotics of its capacity when the erasure rate is low. More specifically, for a general memoryless erasure channel with its input supported on an irreducible finite-type constraint, we derive partial asymptotics of its capacity, using some series expansion type formula of its mutual information rate; and for a binary erasure channel with its first-order Markovian input supported on the$(1, \infty )$-RLL constraint based on the concavity of its mutual information rate with respect to some parameterization of the input, we numerically evaluate its first-order Markov capacity and further derive its full asymptotics. The asymptotics obtained in this paper, when compared with the recently derived feedback capacity for a binary erasure channel with the same input constraint, enable us to draw the conclusion that feedback may increase the capacity of an input-constrained channel, even if the channel is memoryless.

We consider the locally repairable codes (LRCs), aiming at sequentially recovering multiple erasures; in particular, we propose and study the so-called (n, k, r, t)-sequential LRCs (SLRC) as an [n, k] linear code, where any t' (≤ t) erasures can be sequentially recovered, each by r (2 ≤ r <; k) other code symbols. Here, sequential recovering means that the erased symbols are recovered one by one, and an already recovered symbol can be used to recover the remaining erased symbols. This important recovering method, in contrast with the extensively studied parallel recovering, is currently far from being thoroughly understood; more specifically, there are to date no codes constructed for arbitrary t ≥ 3 erasures and bounds to evaluate the performance of such codes. We first derive a tight upper bound on the code rate of the (n, k, r, t)-SLRC for t = 3 and r ≥ 2. We then propose two constructions of binary (n, k, r, t)-SLRCs for general r, t ≥ 2 (existing constructions only deal with t ≤7 erasures). The first construction generalizes the method of direct product construction. The second construction is based on the resolvable configurations and yields SLRCs for any r ≥ 2 odd t ≥ 3. For both constructions, the rates are optimal for t ∈ {2, 3} and are higher than most of the existing LRC families for arbitrary t ≥ 4.

Using Kim's variational formulation [1] (with a slight yet important modification), we derive the ARMA(fc) Gaussian feedback capacity, i.e., the feedback capacity of an additive channel where the noise is a k-th order autoregressive moving average Gaussian process. More specifically, the ARMA(fc) Gaussian feedback capacity is expressed as a simple function evaluated at a solution to a system of polynomial equations, which proves to have only finitely many solutions for the cases k = 1,2 and possibly beyond.

In this paper, we focus our attention on the Rényi entropy rate of hidden Markov processes under certain positivity assumptions. The existence of the Rényi entropy rate for such processes is established. Furthermore, we show that, with some extra “fast-forgetting” assumptions, the Rényi entropy rate of the approximating Markov processes exponentially converges to that of the original hidden Markov process, as the Markov order goes to infinity.

In this paper, we initiate a first information-theoretic study on multilevel NAND flash memory channels with intercell interference. More specifically, for a multilevel NAND flash memory channel under mild assumptions, we first prove that such a channel is indecomposable and it features asymptotic equipartition property; we then further prove that stationary processes achieve its information capacity, and consequently, as the order tends to infinity, its Markov capacity converges to its information capacity; eventually, we establish that its operational capacity is equal to its information capacity. Our results suggest that it is highly plausible to apply the ideas and techniques in the computation of the capacity of finite-state channels, which are relatively better explored, to that of the capacity of multilevel NAND flash memory channels.

We consider the problem of network coding advantage in a communication scenario where information exchange is bi-directional and peers communicate via multiple unicast sessions. In such a setting, we study the overall performance of all multiple unicast sessions and propose a version of the multiple unicast conjecture. One of our main results is a weaker version of the proposed conjecture: Consider all the multiple unicast sessions associated with a number of terminals in an undirected network. Then, the common transmission rate of all these multiple unicast sessions achieved by network coding in the sense of Langberg and Médard [13] can also be achieved by fractional routing.

In this paper, we initiate a first information-theoretic study on multilevel NAND flash memory channels [2] with intercell interference. More specifically, for a multilevel NAND flash memory channel under mild assumptions, we first prove that such a channel is indecomposable and it features asymptotic equipartition property; we then further prove that stationary processes achieve its information capacity, and consequently, as its order tends to infinity, its Markov capacity converges to its information capacity; eventually, we establish that its operational capacity is equal to its information capacity. Our results suggest that it is highly plausible to apply the ideas and techniques in the computation of the capacity of finite-state channels, which are relatively better explored, to that of the capacity of multilevel NAND flash memory channels.

Unveiling a fundamental link between information theory and estimation theory, the I-MMSE relationship by Guo et al., together with its numerous extensions, has great theoretical significance and various practical applications. On the other hand, its influences to date have been restricted to channels without feedback or memory, due to the absence of its extensions to such channels. In this paper, we propose the extensions of the I-MMSE relationship to discrete-time and continuous-time Gaussian channels with feedback and/or memory. Our approach is based on a very simple observation, which can be applied to other scenarios, such as a simple and direct proof of the classical de Bruijn's identity.

In this paper, by studying the feasible fractional routing solution under the so-called full reachability condition, we give bounds on the network coding advantage for undirected multiple unicast networks. More precisely, we prove that, for certain class of fully reachable networks, the network coding advantage is upper bounded by 9/8, improving the previous bound 3 by M. Langberg and M. Médard.

Inspired by ideas from the field of stochastic approximation, we propose a randomized algorithm to compute the capacity of a finite-state channel with a Markovian input. When the mutual information rate of the channel is concave with respect to the chosen parameterization, the proposed algorithm proves to be convergent to the capacity of the channel almost surely with the derived convergence rate. We also discuss the convergence behavior of the algorithm without the concavity assumption.

We first prove that under certain mild assumptions, the entropy rate of a hidden Markov chain, observed when passing a finite-state stationary Markov chain through a discrete-time continuous-output channel, is analytic with respect to the input Markov chain parameters. We then further prove, under strengthened assumptions on the channel, that the entropy rate is jointly analytic as a function of both the input Markov chain parameters and the channel parameters. In particular, the main theorems establish the analyticity of the entropy rate for two representative channels: 1) Cauchy and 2) Gaussian. The analyticity results obtained are expected to be helpful in computation/estimation of entropy rate of hidden Markov chains and capacity of finite-state channels with continuous output alphabet.

Unveiling a fundamental link between information theory and estimation theory, the I-MMSE relation by Guo, Shamai and Verdú [4] has great theoretical significance and numerous practical applications. On the other hand, its influences to date have been restricted to channels without feedback or memory, due to the lack of extensions of the I-MMSE relation to such channels. In this paper, we propose extensions of the I-MMSE relation for discrete and continuous-time Gaussian channels with feedback or memory. Our approach is based on a very simple observation, which can be applied to other scenarios, such as a simple and direct proof of the classical de Bruijn's identity.

In this paper, we derive an explicit formula for the entropy rate of a hidden Markov chain, observed when the Markov chain passes through a memoryless erasure channel. This result naturally leads to an explicit formula for the mutual information rate of memoryless erasure channels with Markovian inputs. Moreover, if the input Markov chain is of first-order and supported on the (1,∞)-run length limited (RLL) constraint, we show that the mutual information rate is strictly concave with respect to a chosen parameter. Then we apply a recent algorithm [1] to approximately compute the first-order noisy constrained channel capacity and the corresponding capacity-achieving distribution.

In this paper, we propose to use Brownian motions to formulate continuous-time multiuser Gaussian networks and derive the capacity regions of a continuous-time white Gaussian multiple access channel with/without feedback, a continuous-time white Gaussian interference channel without feedback and a continuous-time white Gaussian broadcast channel without feedback. These “complete” results stand in stark contrast to the status quo of network information theory in discrete-time, where the capacity regions of the all the above-mentioned channels are known only for a handful of special scenarios. For certain cases, our results echo, from a different perspective, the folklore that “a continuous-time channel is the limit of bandwidth limited discrete-time ones as the bandwidth tends to infinity”.

We consider the solvability problem under network coding and derive a sufficient and necessary condition for 3-pair networks with common “bottleneck links” being solvable. We show that, for such networks: (1) the solvability can be determined in polynomial time; (2) being solvable is equivalent to being linear solvable; (3) finite fields of size 2 or 3 are sufficient to construct linear solutions.

Inspired by the ideas from the field of stochastic approximation, we propose a randomized algorithm to compute the capacity of a finite-state channel with a Markovian input. When the mutual information rate of the channel is concave with respect to the chosen parameterization, we show that, at least for some practical channels, the proposed algorithm will converge to the capacity almost surely.

The computation of the capacity of a finite-state channel (FSC) is a fundamental and long-standing open problem in information theory. The capacity of a memoryless channel can be effectively computed via the classical Blahut-Arimoto algorithm (BAA), which, however, does not apply to a general FSC. Recently Vontobel et al. [1] generalized the BAA to compute the capacity of a finite-state machine channel with a Markovian input. Their proof of the convergence of this algorithm, however, depends on the concavity conjecture posed in their paper. In this paper, we confirm the concavity conjecture for some special FSCs. On the other hand, we give examples to show that the conjecture is not true in general.

In this paper, under mild assumptions, we derive a law of large numbers, a central limit theorem with an error estimate, an almost sure invariance principle, and a variant of the Chernoff bound in finite-state hidden Markov models. These limit theorems are of interest in certain areas of information theory and statistics. Particularly, we apply the limit theorems to derive the rate of convergence of the maximum likelihood estimator in finite-state hidden Markov models.

We consider a memoryless channel with an input Markov process supported on a mixing finite-type constraint. We continue the development of asymptotics for the entropy rate of the output hidden Markov chain and deduce that, at high signal-to-noise ratio, the mutual information rate of such a channel is concave with respect to “almost” all input Markov chains of a given order.

The Shannon-McMillan-Breiman theorem asserts that the sample entropy of a stationary and ergodic stochastic process converges to the entropy rate of the same process (as the sample size tends to infinity) almost surely. In this paper, we restrict our attention to the convergence behavior of the sample entropy of hidden Markov chains. Under certain positivity assumptions, we prove that a central limit theorem (CLT) with some Berry-Esseen bound for the sample entropy of a hidden Markov chain, and we use this CLT to establish a law of iterated logarithm (LIL) for the sample entropy.

We prove that under mild positivity assumptions, the entropy rate of a continuous-state hidden Markov chain, observed when passing a finite-state Markov chain through a discrete-time continuous-output channel, is analytic as a function of the transition probabilities of the underlying Markov chain. We further prove that the entropy rate of a continuous-state hidden Markov chain, observed when passing a mixing finite-type constrained Markov chain through a discrete-time Gaussian channel, is smooth as a function of the transition probabilities of the underlying Markov chain.

We derive an asymptotic formula for entropy rate of a hidden Markov chain under certain parameterizations. We also discuss applications of the asymptotic formula to the asymptotic behaviors of entropy rate of hidden Markov chains as outputs of certain channels, such as binary symmetric channel, binary erasure channel, and some special Gilbert-Elliot channel.

We consider a finite-state memoryless channel with i.i.d. channel state and the input Markov process supported on a mixing finite-type constraint. We discuss the asymptotic behavior of entropy rate of the output hidden Markov chain and deduce that the mutual information rate of such a channel is concave with respect to the parameters of the input Markov processes at high signal-to-noise ratio. In principle, the concavity result enables good numerical approximation of the maximum mutual information rate and capacity of such a channel.

For an acyclic directed graph with multiple sources and multiple sinks, we prove that one can choose the Menger's paths between the sources and the sinks such that the number of mergings between these paths is upper bounded by a constant depending only on the min-cuts between the sources and the sinks, regardless of the size and topology of the graph. We also give bounds on the minimum number of mergings between these paths, and discuss how it depends on the min-cuts.

We generalize a result in [8] and derive an asymptotic formula for entropy rate of a hidden Markov chain around a "weak Black Hole". We also discuss applications of the asymptotic formula to certain channels.

In this paper, we generalize a result by E. Ordentlich and T. Weissman. (2004) and derive an asymptotic formula for the entropy rate of a hidden Markov chain, observed when a Markov chain passes through a binary symmetric channel. And we prove an asymptotic formula for the capacity of a binary symmetric channel with input process supported on an irreducible finite type constraint.

Consider a hidden Markov chain obtained as the observation process of an ordinary Markov chain corrupted by noise. Recently Zuk et al showed how, in principle, one can explicitly compute the derivatives of the entropy rate of at extreme values of the noise. Namely, they showed that the derivatives of standard upper approximations to the entropy rate actually stabilize at an explicit finite time. We generalize this result to a natural class of hidden Markov chains called "black holes." We also discuss in depth special cases of binary Markov chains observed in binary-symmetric noise, and give an abstract formula for the first derivative in terms of a measure on the simplex due to Blackwell.

We give relaxed sufficient conditions (compared to D. Blackwell (1957)) for analyticity of the entropy rate of a hidden Markov chain. Several special cases of the relaxed conditions are discussed. A general principle to calculate the domain of analyticity is stated. An example is given to estimate the radius of convergence for the entropy rate. Finally, we prove a "stabilizing" property of "black hole" case, which suggests that one can explicitly compute the derivatives and obtain an explicit Taylor series in certain cases, generalizing the results in O. Zuk et al. (2004)

We prove that under mild positivity assumptions the entropy rate of a hidden Markov chain varies analytically as a function of the underlying Markov chain parameters. A general principle to determine the domain of analyticity is stated. An example is given to estimate the radius of convergence for the entropy rate. We then show that the positivity assumptions can be relaxed, and examples are given for the relaxed conditions. We study a special class of hidden Markov chains in more detail: binary hidden Markov chains with an unambiguous symbol, and we give necessary and sufficient conditions for analyticity of the entropy rate for this case. Finally, we show that under the positivity assumptions, the hidden Markov chain itself varies analytically, in a strong sense, as a function of the underlying Markov chain parameters

There exist two important design criteria for unitary space time codes. In the situation where the signal-to-noise ratio (SNR) is large the diversity product (DP) of a constellation should be as large as possible. It is less known that the diversity sum (DS) is a very important design criterion for codes working in a low SNR environment. So far, no general method to design good-performing constellations with large diversity for any number of transmit antennas and any transmission rate exists. In this correspondence, we propose constellations with suitable structures, which allow one to construct codes with excellent diversity using geometrical symmetry and numerical methods. The presented design methods work for any dimensional constellation and for any transmission rate

The diversity product and the diversity sum are two very important parameters for a good-performing unitary space-time constellation. A basic question is what the maximal diversity product (or sum) is. In this correspondence, we are going to derive general upper bounds on the diversity sum and the diversity product for unitary constellations of any dimension n and any size m using packing techniques on the compact Lie group U(n)

We prove that under mild assumptions a hidden Markov chain varies analytically, in a strong sense, as a function of the underlying Markov chain parameters. In particular, we show that, under these assumptions, the entropy rate of a hidden Markov chain is an analytic function of the parameters. We give examples to show how this can fail in some cases. And we study two natural special classes of hidden Markov chains in more detail: binary hidden Markov chains with an unambiguous symbol and binary Markov chains corrupted by binary symmetric noise

A wireless communication system using multiple antennas promises reliable transmission under Rayleigh flat fading assumptions. Design criteria and practical schemes have been presented for both coherent and noncoherent communication channels. In this paper, we generalize one-dimensional (1-D) phase-shift keying (PSK) signals and introduce space-time constellations from generalized PSK (GPSK) signals based on the complex and real orthogonal designs. The resulting space-time constellations reallocate the energy for each transmitting antenna and feature good diversity products; consequently, their performances are better than some of the existing comparable codes. Moreover, since the maximum-likelihood (ML) decoding of our proposed codes can be decomposed to 1-D PSK signal demodulation, the ML decoding of our codes can be implemented in a very efficient way.

Diversity product and diversity sum are two important parameters for unitary space time constellation design. An interesting observation in this paper is that full diversity can be easily achieved by Haar distributed random constellations. Using the packing techniques on the compact Lie group U(n), we derive an upper bound for the diversity product and the diversity sum.