In this paper, we investigate the capacity and capacity-achieving input probability distributions (IPDs) of finite-input–finite-output discrete memoryless channels (DMCs). In the general respect, we establish a novel and simple characterization for the capacity-achieving IPDs of a DMC, which is equivalent to the conventional Kuhn–Tucker conditions. We then prove a conjecture of Majani and Rumsey, which claims that every probability component of each capacity-achieving IPD of a DMC with positive capacity is less than$1-e^{-1}$, where$e=2.71828182\ldots $is the base of natural logarithms. It remains an open problem whether there exists an explicit closed-form solution for the capacity and capacity-achieving IPDs of a general finite-input–finite-output DMC, except for the two-input–two-output DMC. In the algebraic respect, we demonstrate that there does not, in general, exist an algebraic solution for the capacity-achieving IPDs of an$m$-input–$n$-output DMC for any$m\geq 2$and any$n\geq 3$. In the analytic respect, however, we can obtain an explicit closed-form analytic solution, represented as an infinite series, for the capacity-achieving IPD of a two-input–three-output DMC. We also provide a formula for the average capacity of weakly symmetric DMCs and show that the average capacity in nats per channel use of the$n$-input–$n$-output weakly symmetric DMCs increases for$n\geq 2$but has a finite limit of$1-\gamma$as$n\to \infty$, where$\gamma =0.57721566\ldots $is Euler's constant. In the algorithmic respect, the convergence of the Arimoto–Blahut algorithm is proved in a direct and elementary way. A new and simple iterative algorithm for calculating a capacity-achieving IPD is then proposed, which is provably convergent for all DMCs with positive transition probabilities. Finally, the characterization and determination of the set of all capacity-achieving IPDs of a DMC are addressed.

In the above titled paper (ibid., vol. 54, no. 3, pp. 1003-1023, Mar 08), several misprints were introduced. The corrections are presented here.

In this paper, we present a new iterative algorithm for calculating the capacity of discrete memoryless channels. The proposed algorithm is comparable in simplicity and effectiveness to the well-known Arimoto-Blahut algorithm. In addition, we provide a short and elementary proof for the convergence of the Arimoto-Blahut algorithm.

Ahlswede, Cai, Li, and Yeung have proposed a new paradigm of network coding in multicast networks. They demonstrated that network coding can achieve the maximum information flow in the single-source multicast networks beyond the conventional network switching. A basic problem arising here is that, for a given single-source multicast network, what is the switching gap of the network defined as the ratio of the maximum information flow in the multicast network with network coding to that only with network switching. In this brief, we investigate the maximum possible switching gap of Ahlswede-Cai-Li-Yeung's single-source multicast network and find some condition, in terms of the capacity of links, under which Ahlswede-Cai-Li-Yeung's network has the minimum possible switching gap of one

Network coding for achieving the maximum information flow in the multicast networks has been proposed by Ahlswede, Cai, Li, and Yeung. They have demonstrated that the conventional network switching, without resort to network coding, is in general not able to achieve the optimum information flow that has been promised by network coding. A basic problem arising here is that, for a given multicast network, what is the switching gap of the network defined as the ratio of the maximum information flow in the multicast network with network coding to that only with network switching. In the paper, by considering network switching as a special form of network coding, we make a complete theoretical and computational determination of the achievable information rate region for multisource multicast network switching. The multicast networks are allowed to be cyclic or acyclic with links having arbitrary positive integer or real-valued capacity. Network switching is essentially a problem of multicast-route packing in the multicast networks. Based on this, we use the theory of games to formulate the network switching as a matrix game between the first "player" of links and the second "player" of multicast routes in the multicast networks. We prove that the maximum achievable information rate at each probabilistic direction in the information rate region is the reciprocal of the value of the corresponding game. Consequently, the maximum achievable information rate can be computed in a simple way by applying the existing theory and algorithms for the computation of the value of a matrix game, especially for such multicast networks with links all having unit capacity as the Ahlswede-Cai-Li-Yeung multicast networks. For multicast networks with links having arbitrary positive real-valued capacity, by using convex optimization, we develop a simple and efficient iterative algorithm to find the maximum achievable information rates for multisource multicast network switching. For single-source multicast networks whose links have arbitrary positive real-valued capacity, we present two max-flow min-cut theorems. The maximum information flow for single-source network switching is the minimum capacity among all soft link-cuts of the multicast network, while the maximum information flow for single-source network coding is the minimum capacity among all hard link-cuts. Consequently, by applying the theory of approximation algorithms for the set-covering problem, we demonstrate that the switching gap of a single-source multicast network is upper-bounded by the nth harmonic number Hn=1+1/2+...+1/n where n is the largest number of multicast routes containing a given link in the network. This harmonic-number bound is asymptotically tight as Oscr(ln n) for the combination multicast network. For the special class of multisource multicast networks with the same set of sink nodes, we make a comparison between the achievable information rate regions for network switching and network coding

This paper presents a natural concatenation between the real or complex square orthogonal designs and the differential unitary space-time modulation scheme for multiple transmit antennas. This concatenation renders the differential unitary space-time demodulator to detect in a decoupled way the information symbols and hence to have a very low decoding complexity. This fast differential demodulation method for multiple transmit antennas can be regarded as a generalization of the existing differential detection method proposed by Tarokh and Jafarkhani for two and four transmit antennas based on orthogonal designs. By using a systematic matrix-vector representation, a unified and simplified form of differential unitary demodulation via square orthogonal designs for any number of transmit antennas and any transmission rate in bits per channel use is provided.

We present a proof for a conjecture of Majani and Rumsey (1991), which claims that every probability component of each capacity-achieving input probability distribution (IPD) of a finite-input finite-output discrete memoryless channel (DMC) with positive capacity is less than 1 - 1/e, where e = 1+1/1! +1/2! +1/3! +.... = 2.71828182... is the base of natural logarithms.

Orthogonal designs have been used as space-time block codes for wireless communications with multiple transmit antennas, which can achieve full transmit diversity and have a very simple decoupled maximum-likelihood decoding algorithm. The rate of an orthogonal design is defined as the ratio of the number of transmitted information symbols in a block of channel uses to the length of the given block, which reflects the bandwidth efficiency of the employed space-time block code constructed from the orthogonal design. This paper focuses on the analysis and synthesis of orthogonal designs with the maximum possible rates, which may be real or complex and square or rectangular matrices. We first provide several representations of orthogonal designs and their characterizations in terms of Hurwitz-Radon matrix equations. Next, we observe that the real orthogonal designs, square or rectangular, and the complex square orthogonal designs with maximal rates have been well understood from the existing results in the mathematics literature which can be dated back to 1890s. However, unfortunately, it is not the case for the complex rectangular orthogonal designs with rates as high as possible. We then construct a class of complex orthogonal designs for any number of transmit antennas. The proposed complex orthogonal designs for the number of transmit antennas n=2m-1 and 2m have the same rate m+1 and 2m, where m is any natural number. Finally, we demonstrate that, for n=2m-1 and 2m with any given natural number m, the value m+1 and 2m is the maximum possible rate that the complex orthogonal designs, square or rectangular, with n transmit antennas can achieve.

Orthogonal space-time block coding proposed recently by Alamouti (1998) and Tarokh et al. (1999) is a promising scheme for information transmission over Rayleigh-fading channels using multiple transmit antennas due to its favorable characteristics of having full transmit diversity and a decoupled maximum-likelihood (ML) decoding algorithm. Tarokh et al. extended the theory of classical orthogonal designs to the theory of generalized, real, or complex, linear processing orthogonal designs and then applied the theory of generalized orthogonal designs to construct space-time block codes (STBC) with the maximum possible diversity order while having a simple decoding algorithm for any given number of transmit and receive antennas. It has been known that the STBC constructed in this way can achieve the maximum possible rate of one for every number of transmit antennas using any arbitrary real constellation and for two transmit antennas using any arbitrary complex constellation. Contrary to this, in this correspondence we prove that there does not exist rate-one STBC from generalized complex linear processing orthogonal designs for more than two transmit antennas using any arbitrary complex constellation.

We focus on the design of unitary signal constellations for differential space-time modulation with double transmit antennas. By using the parametric form of a two-by-two unitary matrix, we present a class of unitary space-time codes called parametric codes and show that this class of unitary space-time codes leads to a five-signal constellation with the largest possible diversity product and a 16-signal constellation with the largest known diversity product. Although the parametric code of size 16 is not a group by itself, we show that it is a subset of a group of order 32. Furthermore, the unitary signal constellations of sizes 32, 64, 128, and 256 obtained by taking the subsets of the parametric codes of sizes 37, 75, 135, and 273, respectively, have the largest known diversity products. We also use large diversity sum of unitary space-time signal constellations as another significant property for the signal constellations to have good performance in low-SNR scenarios. The newly introduced unitary space-time codes can lead to signal constellations with sizes of 5 and 9 through 16 that have the largest possible diversity sums. Subsequently, we construct a few sporadic unitary signal constellations with the largest possible diversity product or diversity sum. A four-signal constellation which has both the largest possible diversity product and the largest possible diversity sum and three unitary signal constellations with the largest possible diversity sums for sizes of 6, 7, and 8 are constructed, respectively. Furthermore, by making use of the existing results in sphere packing and spherical codes, we provide several upper and lower bounds on the largest possible diversity product and the largest possible diversity sum that unitary signal constellations of any size can achieve.

We investigate the qualitative properties of a general class of contractive dynamical systems with time delay by using a unified analysis approach for any p-contraction with p in [1,infinity]. It is proved that the delayed contractive dynamical system is always globally exponentially stable no matter how large the time delay is, while the rate of convergence of the delayed system is reduced as the time delay increases. A lower bound on the rate of convergence of the delayed contractive dynamical system is obtained, which is the unique positive solution of a nonlinear equation with three parameters, namely, the time delay, the time constant and the p-contraction constant in the system. We show that the previously established results in the literature about the global asymptotic or exponential stability independent of delay for Hopfield-type neural networks can actually be deduced by recasting the network model into the general framework of contractive dynamical systems with some p-contraction (p in [1,infinity]) under the given delay-independent stability conditions. Numerical simulation examples are also presented to illustrate the obtained theoretical results.

We investigate the qualitative properties of a recurrent neural network (RNN) for solving the general monotone variational inequality problems (VIPs), defined over a nonempty closed convex subset, which are assumed to have a nonempty solution set but need not be symmetric. The equilibrium equation of the RNN system simply coincides with the nonlinear projection equation of the VIP to be solved. We prove that the RNN system has a global and bounded solution trajectory starting at any given initial point in the above closed convex subset which is positive invariant for the RNN system. For general monotone VIPs, we show by an example that the trajectory of the RNN system can converge to a limit cycle rather than an equilibrium in the case that the monotone VIPs are not symmetric. Contrary to this, for the strictly monotone VIPs, it is shown that every solution trajectory of the RNN system starting from the above closed convex subset converges to the unique equilibrium which is also locally asymptotically stable in the sense of Lyapunov, no matter whether the VIPs are symmetric or nonsymmetric. For the uniformly monotone VIPs, the aforementioned solution trajectory of the RNN system converges to the unique equilibrium exponentially.

Sudharsanan and Sundareshan developed (1991) a neural-network model for bound constrained quadratic minimization and proved the global exponential convergence of their proposed neural network. The global exponential convergence is a critical property of the synthesized neural network for solving the optimization problem successfully. However, Davis and Pattison (1992) presented a counterexample to show that the proof given by Sudharsanan and Sundareshan for the global exponential convergence of the neural network is not correct. Bouzerdoum and Pattison (ibid., vol.4, no.2, p.293-303, 1993) then generalized the neural-network model given by Sudharsanan and Sundareshan and derived the global exponential convergence of the neural network under an appropriate condition. In this letter, we demonstrate through an example that the global exponential convergence condition given by Bouzerdoum and Pattison is not always satisfied by the quadratic minimization problem and show that the neural-network model under the global exponential convergence condition given by Bouzerdoum and Pattison is essentially restricted to contractive networks. Subsequently, a complete proof of the global exponential convergence of the neural-network models proposed by Sudharsanan and Sundareshan and Bouzerdoum and Pattison is given for the general case, without resorting to the global exponential convergence condition given by Bouzerdoum and Pattison. An illustrative simulation example is also presented.

We propose a general recurrent neural-network (RNN) model for nonlinear optimization over a nonempty compact convex subset which includes the bound subset and spheroid subset as special cases. It is shown that the compact convex subset is a positive invariant and attractive set of the RNN system and that all the network trajectories starting from the compact convex subset converge to the equilibrium set of the RNN system. The above equilibrium set of the RNN system coincides with the optimum set of the minimization problem over the compact convex subset when the objective function is convex. The analysis of these qualitative properties for the RNN model is conducted by employing the properties of the projection operator of Euclidean space onto the general nonempty closed convex subset. A numerical simulation example is also given to illustrate the qualitative properties of the proposed general RNN model for solving an optimization problem over various compact convex subsets.

We investigate the qualitative properties of a recurrent neural network (RNN) for minimizing a nonlinear continuously differentiable and convex objective function over any given nonempty, closed, and convex subset which may be bounded or unbounded, by exploiting some key inequalities in mathematical programming. The global existence and boundedness of the solution of the RNN are proved when the objective function is convex and has a nonempty constrained minimum set. Under the same assumption, the RNN is shown to be globally convergent in the sense that every trajectory of the RNN converges to some equilibrium point of the RNN. If the objective function itself is uniformly convex and its gradient vector is a locally Lipschitz continuous mapping, then the RNN is globally exponentially convergent in the sense that every trajectory of the RNN converges to the unique equilibrium point of the RNN exponentially. These qualitative properties of the RNN render the network model well suitable for solving the convex minimization over any given nonempty, closed, and convex subset, no matter whether the given constrained subset is bounded or not.

This paper investigates the existence, uniqueness, and global exponential stability (GES) of the equilibrium point for a large class of neural networks with globally Lipschitz continuous activations including the widely used sigmoidal activations and the piecewise linear activations. The provided sufficient condition for GES is mild and some conditions easily examined in practice are also presented. The GES of neural networks in the case of locally Lipschitz continuous activations is also obtained under an appropriate condition. The analysis results given in the paper extend substantially the existing relevant stability results in the literature, and therefore expand significantly the application range of neural networks in solving optimization problems. As a demonstration, we apply the obtained analysis results to the design of a recurrent neural network (RNN) for solving the linear variational inequality problem (VIP) defined on any nonempty and closed box set, which includes the box constrained quadratic programming and the linear complementarity problem as the special cases. It can be inferred that the linear VIP has a unique solution for the class of Lyapunov diagonally stable matrices, and that the synthesized RNN is globally exponentially convergent to the unique solution. Some illustrative simulation examples are also given.

In a recent paper, Fang and Kincaid proposed an open problem about the relationship between the local stability of the unique equilibrium point and the global stability for a Hopfield-type neural network with continuously differentiable and monotonically increasing activation functions. As a partial answer to the question, in the two-neuron case it is proved that for each given specific interconnection weight matrix, a Hopfield-type neural network has a unique equilibrium point which is also locally exponentially stable for any activation functions and for any other network parameters if and only if the network is globally asymptotically stable for any activation functions and for any other network parameters. If the derivatives of the activation functions of the network are bounded, then the network is globally exponentially stable for any activation functions and for any other network parameters.

It is pointed out that the main analysis results about the existence, uniqueness, and global asymptotic stability of the equilibrium of a continuous-time Hopfield type neural network given in the paper by Zhi-Hong Guan et al. (2000) are special cases of relevant ones previously obtained in the literature. In reply the original authors consider the reasoning of Xue-Bin Liang's comments and state that their analysis method is in fact different to existing ones.

This paper presents a continuous-time recurrent neural-network model for nonlinear optimization with any continuously differentiable objective function and bound constraints. Quadratic optimization with bound constraints is a special problem which can be solved by the recurrent neural network. The proposed recurrent neural network has the following characteristics. 1) It is regular in the sense that any optimum of the objective function with bound constraints is also an equilibrium point of the neural network. If the objective function to be minimized is convex, then the recurrent neural network is complete in the sense that the set of optima of the function with bound constraints coincides with the set of equilibria of the neural network. 2) The recurrent neural network is primal and quasiconvergent in the sense that its trajectory cannot escape from the feasible region and will converge to the set of equilibria of the neural network for any initial point in the feasible bound region. 3) The recurrent neural network has an attractivity property in the sense that its trajectory will eventually converge to the feasible region for any initial states even at outside of the bounded feasible region. 4) For minimizing any strictly convex quadratic objective function subject to bound constraints, the recurrent neural network is globally exponentially stable for almost any positive network parameters. Simulation results are given to demonstrate the convergence and performance of the proposed recurrent neural network for nonlinear optimization with bound constraints.