The minimal set of Shannon-type inequalities (or elemental inequalities) plays a central role in efficiently determining whether a given inequality is in fact Shannon-type or not and in computing the linear programming bound for network coding capacity. In many cases, random variables under consideration are subject to additional constraints, such as functional dependence and conditional independence constraints. For example, functional dependence constraints are common in many communication problems due to deterministic encoding and decoding constraints. In other situations, the variables involved may form a Markov chain or in general a Markov random field, leading to conditional independence constraint. Subject to additional constraints, the challenge is how to identify the non-redundant inequalities. While one can always numerically determine the non-redundant inequalities (subject to additional linear equality constraints), it will be instrumental and also important if the non-redundant inequalities can be listed explicitly. In this paper, we show that this is achievable under the functional dependence and full conditional independence constraints.

We consider the problem of tracking, in realtime, an unstable autoregressive (AR) source over a discrete memoryless channel (DMC). We present computable achievable bounds on the optimal tracking error for general DMCs, and we particularize these bounds to the binary erasure, packet erasure, and binary symmetric channels. The achievable bounds in this paper are proved using a partially separatesource quantizationandchannel codingarchitecture. We do not use complete or strict separation in usual Shannon sense: 1) the quantiser’s resolution is optimized against the error-correction capabilities of the channel code and the channel code is optimized against anAR Hamming distortion functionmatched to the source (a weighted Hamming distortion function that provides unequal error protection to different parts of the AR source). The achievability results for general DMCs are proved by combining the AR Hamming distortion function with new realtime (streaming) versions of therandom coding unionanddependence testing bounds. When applied to erasure channels, these general bounds combine with simple converses to demonstrate that the channel’s cutoff rate plays an important role in realtime tracking.

The minimal set of Shannon-type inequalities, called elemental inequalities, plays a central role in efficiently determining whether a given inequality is in fact Shannon-type or not and in computing the linear programming bound for network coding capacity. In previous work we characterised a minimal set when functional dependence constraints are present. In this work we further generalize the characterisation to include Markov random field (MRF) structures which are defined by full conditional mutual independence constraints.

The minimal set of Shannon-type inequalities (referred to as elemental inequalities), plays a central role in determining whether a given inequality is Shannon-type. Often, there arises a situation where one needs to check whether a given inequality is a constrained Shannon-type inequality. Another important application of elemental inequalities is to formulate and compute the Shannon outer bound for multi-source multi-sink network coding capacity. Under this formulation, it is the region of feasible source rates subject to the elemental inequalities and network coding constraints that is of interest. Hence it is of fundamental interest to identify the redundancies induced amongst elemental inequalities when given a set of functional dependence constraints. In this paper, we characterize a minimal set of Shannon-type inequalities when functional dependence constraints are present.

Characterising the capacity region for a network can be extremely difficult. Even with independent sources, determining the capacity region can be as hard as the open problem of characterising all information inequalities. The majority of computable outer bounds in the literature are relaxations of the linear programming bound, which involves entropy functions of random variables related to the sources and link messages. When sources are not independent, the problem is even more complicated. Extension of linear programming bounds to networks with correlated sources is largely open. Source dependence is usually specified through a joint probability distribution, and one of the main challenges in extending linear program bounds is the difficulty (or impossibility) of characterising arbitrary dependences via entropy functions. This paper tackles the problem by answering the question of how well entropy functions can characterise correlation among sources. We show that by using carefully chosen auxiliary random variables, the characterisation can be fairly “accurate”. Using such auxiliary random variables, we also give implicit and explicit outer bounds on the capacity of networks with correlated sources. The characterisation of correlation or joint distribution via Shannon entropy functions is also applicable to other information measures, such as Rényi entropy and Tsallis entropy.

Explicit characterization of the capacity region of communication networks is a long-standing problem. While it is known that network coding can outperform routing and replication, the set of feasible rates is not known in general. Characterizing the network coding capacity region requires the determination of the set of all entropic vectors. Furthermore, computing the explicitly known linear programming bound is infeasible in practice due to an exponential growth in complexity as a function of network size. This paper focuses on the fundamental problems of characterization and computation of outer bounds for multi-source multi-sink networks. Starting from the known local functional dependence induced by the communication network, we introduce the notion of irreducible sets, which characterize implied functional dependence. We provide recursions for the computation of all maximal irreducible sets. These sets act as information-theoretic bottlenecks, and provide an easily computable outer bound for networks with correlated sources. We extend the notion of irreducible sets (and resulting outer bound) for networks with independent sources. We compare our bounds with existing bounds in the literature. We find that our new bounds are the best among the known graph theoretic bounds for networks with correlated sources and for networks with independent sources.

This paper considers an entropy maximisation problem subject to functional dependency constraints. We compare Delsarte's linear programming (LP) bound, an information theoretic LP bound, and functional dependency bounds and prove that both Delsarte's LP bound and the information theoretic LP bound are at least better than the functional dependency bound.

A streaming communications model with an autoregressive distortion function is proposed. We show that the model is useful for delay-sensitive systems, and we present asymptotic and non-asymptotic achievability results that exhibit some fundamental tradeoffs between rate, reliability and delay.

Following the recent proposed nonlinear frequency division multiplexing (NFDM) scheme [1] for integrable communication channels, we have designed a class of signals called spatially periodic signals that maintain their shape periodically during transmission. This class of signals is of interest because the encoding and decoding processes are much simpler. This paper establishes properties of spatially periodic signals, leading to a better understanding of how spatially periodic signals should be designed and the tradeoff between various system parameters including signal energy and minimum period.

We show that for those lattices of Voronoi's first kind with known obtuse superbasis, a closest lattice point can be computed in $O(n^4)$ operations, where $n$ is the dimension of the lattice. To achieve this a series of relevant lattice vectors that converges to a closest lattice point is found. We show that the series converges after at most $n$ terms. Each vector in the series can be efficiently computed in $O(n^3)$ operations using an algorithm to compute a minimum cut in an undirected flow network.

The problem of synchronizing weak user signals in multiuser code-division multiple access systems is addressed. We integrate timing synchronization into an iterative multiuser detection (MUD) framework for the improved synchronization performance of weak users. First, the effect of correctly detected users on the remaining undetected users is suppressed via soft parallel interference cancellation. Then, the time offset (TO) of each undetected user is estimated. To speed up the MUD, interference cancellation is performed after only a few decoder iterations of the detected users, and the TO estimator is designed taking into account the residual multiple access interference. A low-complexity non-data-aided TO estimator that estimates the TO of each undetected user separately is proposed. The proposed technique significantly improves the synchronization performance of weak users under high near-far conditions compared to the full interference case. Assuming Gaussian distributed log-likelihood ratios at the decoder outputs, we directly relate the missed detection probability of a desired user to the root-mean-squared error of the detected user's data sequences. The extrinsic information transfer chart of the decoder is used to analyze the acquisition performance of the desired user with the number of decoder iterations of the detected users. An upper bound for the missed detection probability of the proposed estimator is derived.

This paper deals with the design of non-systematic irregular repeat-accumulate codes that are optimised for a finite number of decoding iterations. In many cases of practical interest, the usual approach for sparse-graph codes, which aims to approach capacity (with arbitrarily many decoder iterations), may not be suitable. This is of particular importance for systems with complexity or delay constraints. In this paper, we provide a design methodology which constrains the number of decoder iterations, as well as other measures of implementation complexity. Our approach uses extrinsic information transfer analysis, and our main contribution is the formulation of code optimisation problems which directly incorporate the number of iterations into the constraints. We focus on the single user binary erasure channel and the two-user binary adder channel, where this transfer analysis is exact. Generalisation to other sparse graph codes and other channels (under usual approximations) is straightforward.

In this paper, we use entropy functions to characterize the set of rate-capacity tuples achievable with either zero decoding error, or vanishing decoding error, for general network coding problems for acyclic networks. We show that when sources are colocated, the outer bound is tight and the sets of zero-error achievable and vanishing-error achievable rate-capacity tuples are the same. Then, we extend this paper to networks subject to linear encoding constraints, routing constraints (where some or all nodes can only perform routing), and secrecy constraints. Finally, we show that even for apparently simple networks, design of optimal codes may be difficult. In particular, we prove that for the incremental multicast problem and for the single-source secure network coding problem, characterization of the achievable set can be very hard and linear network codes may not be optimal.

This paper considers source coding problems with the requirements of perfect secrecy and zero error at receivers. In the problems considered in this paper, there is always one transmitter but there can be one or two receivers. Two different scenarios depending on whether the receivers' side information are present at the transmitter or not are considered. By deriving bounds on the probability masses of the cipher-text and the key, the minimum transmission rate and key rate are characterized. Although zero-error capacities are typically difficult to characterize, the perfect secrecy constraint turns out to be the key that simplifies the problems considered in this paper and makes them analytically tractable.

Characterising the capacity region for a network can be extremely difficult. Even with independent sources, determining the capacity region can be as hard as the open problem of characterising all information inequalities. The majority of computable outer bounds in the literature are relaxations of the Linear Programming bound which involves entropy functions of random variables related to the sources and link messages. When sources are not independent, the problem is even more complicated. Extension of Linear Programming bounds to networks with correlated sources is largely open. Source dependence is usually specified via a joint probability distribution, and one of the main challenges in extending linear program bounds is the difficulty (or impossibility) of characterising arbitrary dependencies via entropy functions. This paper tackles the problem by answering the question of how well entropy functions can characterise correlation among sources. We show that by using carefully chosen auxiliary random variables, the characterisation can be fairly “accurate”.

Single carrier systems with frequency domain equalization (SC-FDE) have been recently proposed for optical wireless systems as alternatives to optical orthogonal frequency division multiplexing (OFDM) to reduce the peak-to-average power ratio (PAPR) of the transmitted signal and improve the system performance. However, these SC-FDE systems have either higher complexity or lower spectrum efficiency. In this paper a low complexity SC-FDE system based on on-off-keying (OOK) modulation is proposed. Theoretical bit-error-rate (BER) analysis is provided based on minimum mean square error (MMSE) equalization for the proposed system and typical optical SC-FDE and OFDM systems. Both analytical and numerical results show that the proposed system significantly outperforms existing SC-FDE and OFDM systems in terms of PAPR, BER and implementation complexity.

Quasi-uniform random vectors have probability distributions that are uniform over their projections. They are of fundamental interest because a linear information inequality is valid if and only if it is satisfied by all quasi-uniform random vectors. In this paper, we investigate properties of codes induced by quasi-uniform random vectors. We prove that quasi-uniform codes (which include linear and almost affine codes as special cases) are distance-invariant and that Greene's Theorem and the Critical Theorem of Crapo and Rota hold in the setting of quasi-uniform codes. We show that both theorems are essentially combinatorial but not algebraical in nature. Linear programming bounds proposed by Delsarte are extended for quasi-uniform codes.

A pair of strings (X,Y) put out by a memoryless source needs to be reliably communicated over a memoryless broadcast channel. Receiver 1 hasYas side information and must reconstructXto within some distortion. Receiver 2 hasXand must reconstructYto within some distortion. The problem is motivated by the broadcast phase (downlink) of the two-way relay channel. We characterize reliable communication for Gaussian sources with quadratic distortion functions; conditionally independent sources; deterministic distortion functions; and small distortions with Hamming distortion functions. The last result is obtained by solving a new version of the broadcast problem with Steinberg's common-reconstruction decoding constraint.

This paper focuses on the problem of code acquisition in multiuser CDMA systems in a near-far scenario. A new time offset estimator which iteratively cancels interference from correctly acquired users is proposed. Interference cancellation is accomplished by projecting the received signal into the null space of already acquired users. The proposed technique performs well under low SNR conditions in the presence of high multiple access interference. Analytical expressions for the missed detection probability of the proposed estimator are derived and these agree with the results of Monte-Carlo simulations.

This paper investigates a new method in proving converses in secure communication problems. The method gives a converse result in terms of the logarithm of support size instead of entropy. The results are connected to constrained information inequalities involving three random variables. A new constrained non-Shannon type inequality is shown.

We show that for those lattices of Voronoi's first kind with known obtuse superbasis, a vector of shortest nonzero Euclidean length can computed in polynomial time by computing a minimum cut in a graph.

The polymatroid axioms are dominantly used to study the capacity limits of various communication systems. In fact for most of the communication systems, for which the capacity is known, these axioms are solely required to obtain the characterization of capacity. Moreover, the polymatroid axioms are stronger tools to tackle the implication problem for conditional independencies compared to the axioms used in Bayesian networks. However, their use is prohibitively complex as the number of random variables increases since the number of inequalities to consider increases exponentially. In this paper we give a compact characterization of the minimal set of polymatroid axioms when arbitrary conditional independence and functional dependence constraints are given. In particular, we identify those elemental equalities which are implied by given constraints. We also identify those elemental inequalities which are redundant given the constraints.

This paper gives expressions for the capacity of ergodic multiple-input multiple-output channels with finite dimensions, in which the channel gains have a correlated complex normal distribution and receivers experience independent Gaussian noise. The particular correlated normal distribution considered corresponds to flat Rayleigh fading with arbitrary transmit and receive correlation. Knowledge of the correlation matrices is assumed at both the transmitter and receiver, while the receiver, but not the transmitter, has complete knowledge of the channel realization. The optimal input density is characterized via a necessary and sufficient condition for optimality, along with an iterative algorithm for its numerical computation. The resulting capacity is expressed in terms of hypergeometric functions of matrix argument, which depend on the channel correlation matrices only through their eigenvalues. Some closed-form expressions are also given in the case of single-sided correlation. Some consideration is given to high- and low-power asymptotics. Easily computable asymptotic expressions are also given for receive-side only correlation in the case that the number of transmitters is large. In that case, the capacity can be divided into two components: one arising from the dominant eigenvalues of the receiver-end correlation matrix, and the other from the remaining spherically distributed eigenvalues. Some numerical results are also presented.

Energy minimization in wireless sensor networks is a key issue, particularly in order to maximize the lifetime of nonserviceable battery powered devices in the field. In this paper, we propose a new energy consumption model that allows allocation of variable transmit power and data compression/transmission rate to each sensor node. In contrast to previous work, our model captures both the cost of wireless transmission as well as the cost for a node to be in an active mode during transmission. This is an important and non-trivial consideration, as higher data rates require greater transmit power for reliable wireless transmission, however this reduces the duration for which the node must be in active mode. Based on this new model, we consider minimization of the total energy cost of lossless data gathering by using joint power and rate allocation under rate and capacity constraints. We show how the rate and power allocation problems are coupled in general, and we provide a convex optimization formulation for the resulting joint optimization problem. We present a special case for which power allocation separates from the rate allocation problem, namely when the cost of being active dominates. For this special case we obtain a simple characterization of the optimum power and rate allocation strategy. Simulation results are given in line with the theoretical analysis.

The rate-distortion (RD) function for source coding with complementary side-information is characterised for several special cases of the general problem. These include Steinberg's common-reconstruction setting, small distortions for both sources, zero distortion for one source, conditionally independent sources, and deterministic distortion measures.

We study a secure distributed source coding problem. Two terminals with correlated observations would like to send their observations securely to a receiver using minimal transmission rates and key rates. By providing a converse, we show the optimality of a natural structure, in which Slepian-Wolf distributed compression is followed by an application of a onetime pad for encryption. Hence, in contrast to many multiuser setting, the separation of compression and encryption is optimal for this particular case. The optimality of the separation can simplify practical algorithm design. In addition, we constructively demonstrate that switching the order of compression and encryption does not incur any performance loss. Finally, we show that if one requires perfect secrecy and zero error probability, the required rates increase significantly and data compression becomes unnecessary.

The mobile outdoor radio environment is challenging for vehicular communications. Although multipath propagation offers diversity and benefits in non-line-of-sight (NLOS) conditions, simultaneous multipath and mobility results in a doubly-selective fading channel. In practice, this means that the channel parameters vary significantly in both time and frequency within the bandwidth and typical packet durations used in 802.11p/WAVE standards for short-range vehicular communications. This paper presents the results of extensive field trial campaigns conducted in several countries, totaling over 1100 km. These field trials are scenario based, focusing on challenging low-latency, high-reliability vehicle-to-vehicle (V2V) safety applications including intersection collision warning, turn across path, emergency electronic brake light, do not pass warning, and precrash sensing. Vehicle-to-infrastructure (V2I) applications are also considered. The field trials compared the performance of off-the-shelf WiFi-based radio equipment with a more advanced 802.11p compliant radio employing more sophisticated channel estimation and tracking. Field trial results demonstrate significantly improved performance using the advanced radio, translating into greatly increased driver warning times and stopping distances. In fact the results show that off-the-shelf WiFi equipment fails to provide sufficient stopping distance to avert accidents in some cases. During the field trials, channel sounding data were also captured. Analysis of these channel measurements reveals the critical importance of accurate channel estimation, tracking the channel in both time and frequency within each packet. Delay spread and Doppler spread statistics computed from the channel measurements validate previously reported results in the literature. The results in this paper, however, provide the first instance of channel measurements performed simultaneously to application performance evaluation. The objective is to firmly establish the link between radio channel characteristics and the performance of critical V2V safety applications.

Linear polymatroids have a strong connection to network coding. The problem of finding the linear network coding capacity region is equivalent to the characterization of all linear polymatroids. It is well known that linear polymatroids must satisfy the inequalities of Ingleton (Combin. Math. Appln., 1971). However, it has been an open question for years as to whether these inequalities are sufficient. It was until recently that new subspace rank inequalities have been discovered (independently by Kinser and Dougherty, ). In this paper, we propose a new approach to investigate properties of linear polymatroids. Specifically, we demonstrate how to construct a new polymatroid that satisfies not only the Ingleton and DFZ inequalities, but also lies outside the minimal closed and convex cone containing all linear polymatroids. Using this polymatroid, we prove that all truncation-preserving inequalities (including Ingleton inequalities and DFZ inequalities) are insufficient to characterize linear polymatroids.

The Ingleton inequalities are the inequality constraints known to be required of representable matroids. For a matroid ofnelements, there are 16nIngleton inequalities. In this paper, we show that many of these inequalities are redundant. We explicitly determine the unique minimal set of Ingleton inequalities, which number on the order of 6n/4-O(5n). In information theory, these inequalities are required of the entropy functions of certain random variables constructed from linear subspaces. As a result, these inequalities appear as constraints in linear programming outer bounds for the capacity region of multisource network coding where the codes are required to be linear. Ingleton inequalities have also played an instrumental role in demonstrating the insufficiency of linear codes for multisource network coding. The reduction that we obtain for Ingleton inequalities is sufficiently large to meaningfully reduce the complexity of these linear programming bounds.

We present an achievable rate region for the multistage successive-refinement problem with side-information. We also present an upper bound for the rate-distortion function for lossy source coding with side-information at many decoders. Characterising this rate-distortion function is a long-standing open problem, and it is widely believed that the tightest upper bound is provided by Theorem 2 of Heegard and Berger's paper “Rate distortion when side information may be absent” (IEEE Trans. Inf. Theory, 1985). We give a counterexample to Heegard and Berger's result.

We consider the problem of transmitting a Gaussian source over a Rayleigh fading channel where some side-information may be available to the receiver. Our objective is to minimize the average distortion at the receiver. We consider two source models with side-information: 1) the Heegard-Berger model where "side-information may be absent", and 2) successive refinement with degraded side-information. We show that the average distortion problem can be numerically solved by convex optimization techniques. Furthermore, in high SNR, we obtain an analytical solution that shows that the side-information does not affect the distortion exponent, but causes an offset with respect to the case without side information. Numerical results show that our analytical high SNR approximation gives accurate results even at medium SNR.

The arbitrarily varying channel can be modeled as communication in the presence of a jammer. In this paper we propose a new model: a jammer who knows the channel input, and where the transmitter and receiver share a secret random key. Shared randomness differentiates this scenario from the case where the jammer knows the message. For sufficiently large key rate, we determine the capacity of this channel (which may be strictly smaller than the case where the jammer knows only the message). We also provide an upper bound on the minimum key rate required to achieve capacity. We prove that additionally revealing the message to the jammer does not change the capacity, provided the key rate is sufficiently large. This new capacity result differs from existing results for the AVC, and in fact coincides with a well-known upper bound on the deterministic coding capacity of the AVC with maximum error. Without secret keys, our problem degenerates to deterministic coding for the AVC with maximum probability of error, a well-known hard problem. Our results demonstrate that knowledge of the channel input is better than knowledge of the message for the jammer.

We study the network coding capacity of multi-source, multi-sink networks with colocated sources, but where each sink may demand a different subset of the sources. We show that in this scenario, the set of admissible (zero probability of decoding errors) and achievable (vanishing probability of decoding errors) rate capacity tuples are the same. We also simplify the capacity region by showing that the outer bound obtained in “A First Course in Information Theory” (Yeung, 2002) is in fact tight. We conjecture that this bound remains tight, even when the sources are not colocated.

Quasi-uniform random variables have probability distributions that are uniform over their supports. They are of fundamental interest because a linear information inequality is valid if and only if it is satisfied by all quasi-uniform random variables. In this paper, we investigate properties of codes induced by quasi-uniform random variables.We prove that quasi-uniform codes (which include linear and almost affine codes as special cases) are distance-invariant and that Greene's Theorem and the Critical Theorem of Crapo and Rota hold in the setting of quasi-uniform codes. We also outline how these results provide a coding theoretic approach to construct information inequalities.

An Ingletonian polymatroid satisfies, in addition to the polymatroid axioms, the inequalities of Ingleton. These inequalities are required for a polymatroid to be representable. It has been an open question as to whether these inequalities are also sufficient. Representable polymatroids are of interest in their own right. They also have a strong connection to network coding. In particular, the problem of finding the linear network coding capacity region is equivalent to the characterization of all representable, entropic polymatroids. In this paper, we describe a new approach to adhere two polymatroids together to produce a new polymatroid. Using this approach, we can construct a polymatroid that is not inside the minimal closed and convex cone containing all representable polymatroids. This polymatroid is proved to satisfy not only the Ingleton inequalities, but also the recently reported inequalities of Dougherty, Freiling and Zeger. A direct consequence is that these inequalities are not sufficient to characterize representable polymatroids.

We present a new inner bound for the admissible rate region of the t-stage successive-refinement problem with side-information. We also present a new upper bound for the rate-distortion function for lossy-source coding with multiple receivers and side-information. A single-letter characterisation of this rate-distortion function is a long-standing open problem, and it is widely believed that the tightest upper bound is provided by Theorem 2 of Heegard and Berger's paper “Rate Distortion when Side Information may be Absent,” IEEE Trans. Inform. Theory, 1985. We give a counterexample to Heegard and Berger's result.

Suppose a stationary memoryless source is observed through a discrete memoryless channel. Determining analytical confidence intervals on the source entropy is known to be a difficult problem, even when the observation channel is noiseless. In this paper, we determine confidence intervals for estimation of source entropy over discrete memoryless channels with invertible transition matrices. A lower bound is given for the minimum number of samples required to guarantee a desired confidence interval. All these results do not require any prior knowledge of the source distribution, other than the alphabet size. When the alphabet size is countably infinite or unknown, we illustrate an inherent difficulty in estimating the source entropy.

Cochlear implants, also known as bionic ears, are surgically implanted biomedical devices that can provide hearing to some deaf people by direct electrical stimulation of the auditory nerve. A crucial question for the design of future cochlear implants is that of how many electrodes might achieve optimal hearing performance in patients. It is efficient to avoid using more electrodes if this does not provide a performance improvement. Whether an improvement can be gained by inclusion of more electrodes depends crucially on physical properties such as distance of the electrode array from the auditory nerve and current spread. The response of individual fibers in the auditory nerve to electrical stimulation is stochastic, and it is proposed that the interface between an array of electrodes and the auditory nerve can be thought of as a communication channel in which only uncoded transmission can be used. A discrete memoryless channel model for this interface is defined and used as the basis for obtaining numerical estimates of the optimal number of electrodes in the array as a function of array-to-nerve distance. While the only true indicator of improved hearing through cochlear implants is via empirical audiological measurements, the discrete memoryless channel model allows maximization of mutual information as a proxy measure, under the hypothesis that there exists a monotonic relationship between mutual information and perceptibility.

This paper considers a key agreement problem in which two parties aim to agree on a key by exchanging messages in the presence of adversarial tampering. The aim of the adversary is to disrupt the key agreement process, but there are no secrecy constraints (i.e. we do not insist that the key is kept secret from the adversary). The main results of the paper are coding schemes and bounds on maximum key generation rates for this problem.

In this paper, we show how to construct a factor graph from a network code. This provides a systematic framework for decoding using message passing algorithms. The proposed message passing decoder exploits knowledge of the underlying communications network topology to simplify decoding. For uniquely decodeable linear network codes on networks with error-free links, only the message supports (rather than the message values themselves) are required to be passed. This proposed simplified support message algorithm is an instance of the sum-product algorithm. Our message-passing framework provides a basis for the design of network codes and control of network topology with a view toward quantifiable complexity reduction in the sink terminals.

Explicit characterization and computation of the multi-source network coding capacity region (or even bounds) is long standing open problem. In fact, finding the capacity region requires determination of the set of all entropic vectors Gamma*, which is known to be an extremely hard problem. On the other hand, calculating the explicitly known linear programming bound is very hard in practice due to an exponential growth in complexity as a function of network size. We give a new, easily computable outer bound, based on characterization of all functional dependencies in networks. We also show that the proposed bound is tighter than some known bounds.

We propose a novel access technique for cellular downlink resource sharing. In particular, a distributed self-selection procedure is combined with the technique of compressed sensing to identify a set of users who are getting simultaneous access to the downlink broadcast channel. The performance of the proposed method is analyzed, and its suitability as an alternate access mechanism is argued.

In this paper we propose a method for on-line estimation of bit error rate during turbo decoding. We model the log-likelihood ratios as a mixture of two Gaussian random variables and derive estimators for the mean and variance of these distributions based on a maximum-likelihood approach. The parameter estimates are then employed to calculate the cross-over area of the Gaussian tails to estimate BER at each decoder iteration. The performance of the BER estimator is analysed and compared.

We propose a systematic design framework for optimal, low-complexity punctured multiple parallel concatenated codes (MPCCs), based on minimizing the convergence threshold using extrinsic information transfer (EXIT) charts. As the convergence threshold is related to the area between the two EXIT curves, the corresponding optimization problem is equivalent to a curve-fitting problem. The EXIT curves are determined by the respective EXIT functions of the constituents, which can be conveniently shaped through the use of random puncturing and unequal energy allocations across parallel coding streams. The design task is therefore to find the optimal combination of constituents, puncturing ratios, and energy allocation for matching the EXIT curves. A search over all rate-one convolutional codes of memory length four or less is performed, identifying 98 classes of codes with unique EXIT functions out of a total of 310 codes. Low-complexity MPCCs with up to four constituents are found, where the convergence thresholds are observed to be within 0.1 dB or less of the fundamental minimum signal-to-noise ratio (SNR) corresponding to the binary phase-shift keying (BPSK) capacity for code rates1/3lesRles 7/8. Further allowing for unequal energy allocation, the convergence thresholds for lower code rates are similarly improved.

Low-density parity-check (LDPC) codes may be decoded using a circuit implementation of the sum-product algorithm which maps the factor graph of the code. By reusing the decoder for encoding, both tasks can be performed using the same circuit, thus reducing area and verification requirements. Motivated by this, iterative encoding techniques based upon the graphical representation of the code are proposed. Code design constraints which ensure encoder convergence are presented, and then used to design iteratively encodable codes, while also preventing 4-cycle creation. We show how the Jacobi method for iterative matrix inversion can be applied to finite field matrices, viewed as message passing, and employed as the core of an iterative encoder. We present an algebraic construction of4-cycle free iteratively encodable codes using circulant matrices. Analysis of these codes identifies a weakness in their structure, due to a repetitive pattern in the factor graph. The graph supports pseudo-codewords of low pseudo-weight. In order to remove the repetitive pattern in the graph, we propose a recursive technique for generating iteratively encodable codes. The new codes offer flexibility in the choice of code length and rate, and performance that compares well to randomly generated, quasi-cyclic and extended Euclidean-geometry codes.

One of the main theoretical motivations for the emerging area of network coding is the achievability of the max-flow/min-cut rate for single source multicast. This can exceed the rate achievable with routing alone, and is achievable with linear network codes. The multi-source problem is more complicated. Computation of its capacity region is equivalent to determination of the set of all entropy functions Gamma*, which is non-polyhedral. The aim of this paper is to demonstrate that this difficulty can arise even in single source problems. In particular, for single source networks with hierarchical sink requirements, and for single source networks with secrecy constraints. In both cases, we exhibit networks whose capacity regions involve Gamma*. As in the multi-source case, linear codes are insufficient.

The Ingleton-LP bound is an outer bound for the multicast capacity region, assuming the use of linear network codes. Computation of the bound is performed on a polyhedral cone obtained by taking the intersection of half-spaces induced by the basic (Shannon-type) inequalities and Ingleton inequalities. This paper simplifies the characterization of this cone, by obtaining the unique minimal set of Ingleton inequalities. As a result, the effort required for computation of the Ingleton-LP bound can be greatly reduced.

We consider the problem of source coding with receiver side information for the simple network proposed by R. Gray and A. Wyner in 1974. In this network, a transmitter must reliably transport the output of two correlated information sources to two receivers using three noiseless channels: a public channel which connects the transmitter to both receivers, and two private channels which connect the transmitter directly to each receiver. We extend Gray and Wyner's original problem by permitting side information to be present at each receiver. We derive inner and outer bounds for the achievable rate region and, for three special cases, we show that the outer bound is tight.

In communications networks, the capacity region of multisource network coding is given in terms of the set of entropy functions Gamma*. More broadly, determination of Gamma*would have an impact on converse theorems for multi-terminal problems in information theory. This paper provides several new dualities between entropy functions and network codes. Given a functiongges 0 defined on all subsets ofNrandom variables, we provide a construction for a network multicast problem which is ldquosolvablerdquo if and only ifgis the entropy function of a set of quasi-uniform random variables. The underlying network topology is fixed and the multicast problem depends ongonly through link capacities and source rates. A corresponding duality is developed for linear network codes, where the constructed multicast problem is linearly solvable if and only ifgis linear group characterizable. Relaxing the requirement that the domain ofgbe subsets of random variables, we obtain a similar duality between polymatroids and the linear programming bound. These duality results provide an alternative proof of the insufficiency of linear (and abelian) network codes, and demonstrate the utility of non-Shannon inequalities to tighten outer bounds on network coding capacity regions.

In this correspondence, the uplink of a multibeam satellite system with Rician fading is analyzed under the framework of Wyner's Gaussian cellular multiple access channel. In this framework the received signal at a given multibeam antenna is the sum of signals transmitted by users within that beam's cell area plus a factor 0 les alpha les 1 times the sum of the signals transmitted by users from adjacent cells plus ambient Gaussian noise. Both one-dimensional (1-D) linear, and 2-D hexagonal cellular arrangements are considered. In addition, we consider a modified version of the 1-D linear arrangement whereby users from cells further than adjacent cells contribute to intercell interference. It is assumed that the distance between the antenna elements is small compared to the distance between a user and the satellite. Thus when fading is present, a particular user's fading coefficient is the same at each multibeam antenna. This is the fundamental difference between the multibeam satellite fading channel and the terrestrial cellular fading channel, in which each user experiences independent fading at each base station. Using a Haar measure approximation we derive closed form approximations for the capacity of the satellite fading channel for the scenarios when optimal joint decoding and linear minimum mean square error filtering is employed at the ground station. These approximations are shown to be in close agreement to Monte Carlo simulation results for large dimensional systems. It is shown that fading causes a loss in capacity compared to the nonfading channel. Furthermore, at high signal-to-noise ratio (SNR) this loss is independent of the intercell interference and topology of the system, but is dependent on the distribution of the fading coefficients and the number of users per beam.

One promising approach to peak to average power ratio (PAPR) reduction for orthogonal frequency division multiple access (OFDMA) is the use of reserved tones, which are modulated so as to reduce the PAPR. One problem with this approach is the computationally efficient determination of reserved tone signals that best reduce the PAPR. In this paper we describe a new algorithm for selection of the reserved tone signals. The algorithm results from a differentiable approximation of the PAPR optimisation criterion. We derive a new joint minimisation method capable of reducing multiple peaks simultaneously. It is shown how this can be utilized in a low complexity gradient update algorithm. Simulations show superior performance (lower resultant PAPR) compared to other methods, where system parameters have been motivated by the proposed long term evolution of the 3GPP cellular standard.

Random linear network coding is a particularly decentralized approach to the multicast problem. Use of random network codes introduces a non-zero probability however that some sinks will not be able to successfully decode the required sources. One of the main theoretical motivations for random network codes stems from the lower bound on the probability of successful decoding reported by Ho et. al. (2003). This result demonstrates that all sinks in a linearly solvable network can successfully decode all sources provided that the random code field size is large enough. This paper develops a new bound on the probability of successful decoding.

We consider a network multicast example that relates the solvability of the multicast problem with the existence of an entropy function. As a result, we provide an alternative approach to the proving of the insufficiency of linear (and abelian) network codes and demonstrate the utility of non- Shannon inequalities to tighten outer bounds on network coding capacity regions.

We derive a closed form expression for the Shannon transform of the product of two arbitrary positive semidefinite random matrices, where at least one of the matrices is unitary invariant. In principle, S-transforms could be directly applied in this scenario, however in many cases of interest this approach leads to an intractable expression. Our alternative approach, based on hypergeometric functions, leads to a tractable asymptotic expression. This result is validated for finite size matrices using Monte Carlo simulations.

We consider multiple-input multiple-output (MIMO) transmit beamforming systems with maximum ratio combining (MRC) receivers. The operating environment is Rayleigh fading with both transmit and receive spatial correlation. We present exact expressions for the probability density function (pdf) of the output signal-to-noise ratio, as well as the system outage probability. The results are based on explicit closed-form expressions which we derive for the pdf and cumulative distribution function of the maximum eigenvalue of double-correlated complex Wishart matrices. For systems with two antennas at either the transmitter or the receiver, we also derive exact closed-form expressions for the symbol-error rate. The new expressions are used to prove that MIMO-MRC achieves the maximum available spatial diversity order, and to demonstrate the effect of spatial correlation. The analysis is validated through comparison with Monte Carlo simulations

The paper describes a curve-fitting approach for the design of capacity approaching coded modulation for orthogonal signal sets with non-coherent detection. In particular, bit-interleaved coded modulation with iterative decoding is considered. Decoder metrics are developed that do not require knowledge of the signal-to-noise ratio, yet still offer very good performance.

One method for approximating a-posteriori symbol probabilities is to marginalise over a reduced list of possible vectors. Several methods exist for obtaining suitable lists (e.g. the list sphere detector), but in many cases the list size required for an accurate approximation may still be large. This paper describes an implementation technique which removes the requirement for list storage, with minimal increase in complexity. The method updates the posterior probabilities in place, and works with any depth-first tree-search based detector. We then introduce a novel depth-first branch and bound algorithm, which is shown to be more computationally efficient than standard Fincke-Pohst enumeration. It is particularly effective in difficult channels, characterized by having channel matrices with small determinants.

This paper considers multiple-input multiple-output (MIMO) antenna systems employing transmit beamforming (BF) with maximum ratio combining (MRC) receivers. Rayleigh fading environments are considered, with both transmit and receive spatial correlation. Exact expressions are presented for the probability density function (p.d.f.) of the output signal-to-noise ratio (SNR), as well as the system outage probability. The results are based on efficient closed-form expressions which we derive for the p.d.f. and c.d.f. of the maximum eigenvalue of double-correlated complex Wishart matrices. The results are validated through comparison with Monte-Carlo simulations, and used to examine the effect of spatial correlation on the SNR p.d.f. and the outage probability

We consider t-input r-output Rayleigh fading channels with transmit-sided correlation, where the receiver knows the channel realizations, and the transmitter only knows the channel statistics. Using Lagrange duality, we develop an easily computable, tight upper bound on the loss in information rate due to the use of any given input covariance for this channel. This bound is applied to two simple transmission strategies. The first strategy is a reduced-rank uniform allocation, in which independent, equal power Gaussian symbols are transmitted on the at strongest eigenvectors of the transmit covariance matrix, where 0 les alpha les 1 is chosen to optimize the resulting information rate. The second strategy is water-filling on the eigenvalues of the transmit covariance matrix. The upper bound on loss shows these strategies are nearly optimal for a wide range of signal to noise ratios and correlation scenarios

Let C be an [n, k, d] binary linear code with rate R = k/n and dual Cperp. In this correspondence, it is shown that C can be represented by a 4-cycle-free Tanner graph only if: pdperples lfloorradicnp(p-1)+n2/4+n/2rfloor where p = n - k and dperpis the minimum distance of Cperp. By applying this result, it is shown that 4-cycle-free Tanner graphs do not exist for many classical binary linear block codes

Let C be an [n,k,d] binary linear code with rate R=k/n and dual Cperp. In this correspondence, it is shown that C can be represented by a 4-cycle-free Tanner graph only if: pdperples lfloorradicnp(p-1)+n2/4+n/2 rfloorwhere p=n-k and dperpis the minimum distance of Cperp. By applying this result, it is shown that 4-cycle- free Tanner graphs do not exist for many classical binary linear block codes

We provide a thorough analysis for a class of iteratively encodable low-density parity-check codes. The iterative encoding technique is based upon the graphical representation of the code and allows the decoder circuit to also be used for encoding, thus saving circuit area. The analysis identifies a weakness in the structure of the code, which arises due to a repetitive pattern in its factor graph. We show that the graph supports pseudo-codewords of low pseudo-weight, and relate this to the empirical observation of some near-codewords. We then propose a new recursive technique for constructing iteratively encodable codes which have improved expansion. The new codes offer a large amount of flexibility in the choice of code length and rate, and performance that compares well to both randomly generated and extended Euclidean-geometry codes

We give an optimality condition for the input covariance for arbitrary ergodic Gaussian vector channels under the condition that the channel gains are independent of the transmit signal, the transmitter has knowledge of the channel gain probability law and the receiver has knowledge of each channel realization. Using this optimality condition, we find an iterative algorithm for numerical computation of optimal input covariance matrices

Application of the turbo principle to multiuser decoding results in an exchange of probability distributions between two sets of constraints. Firstly, constraints imposed by the multiple-access channel, and secondly, individual constraints imposed by each users' error control code. A-posteriori probability computation for the first set of constraints is prohibitively complex for all but a small number of users. Several lower complexity approaches have been proposed in the literature. One class of methods is based on linear filtering (e.g. LMMSE). A more recent approach is to compute approximations to the posterior probabilities by marginalising over a subset of sequences (list detection). Most of the list detection methods are restricted to non-singular systems. In this paper, we introduce a transformation that permits application of standard tree-search methods to underdetermined systems. We find that the resulting tree-search based receiver outperforms existing methods

Using the theory of random matrices, a performance analysis is given for uncoded binary transmission over multiple-input multiple-output channels, under the assumption that transmitter beamforming is used. In particular, exact finite antenna expressions are found for the average bit error rate (in the case of ergodic channels) for both noncoherent and coherent detection. Expressions for the the outage probability (in the case of quasi-static channels) are also given.

An interesting practical consideration for decoding of serial or parallel concatenated codes with more than two components is the determination of the lowest complexity component decoder schedule which results in convergence. This correspondence presents an algorithm that finds such an optimal decoder schedule. A technique is also given for combining and projecting a series of three-dimensional extrinsic information transfer (EXIT) functions onto a single two-dimensional EXIT chart. This is a useful technique for visualizing the convergence threshold for multiple concatenated codes and provides a design tool for concatenated codes with more than two components.

This correspondence presents an optimal soft-in soft-out (SISO) decoding algorithm for the binary image of Reed-Solomon (RS) codes that is based on Vardy and Be'ery's optimal soft-in hard-out algorithm. A novel suboptimal list-based SISO decoder that exploits Vardy and Be'ery's decomposition is also presented. For those codes with very high rate, which allows practical decoding with the proposed algorithms, the proposed suboptimal SISO significantly outperforms standard list-based decoding techniques in iteratively decoded systems.

A K-symmetric channel is a K-user linear multiple-access channel in which the cross correlations between each pair of users are identical. The main contribution of this correspondence is an algorithm which finds the P sequences with highest a posteriori probability (APP) in the case of binary transmission over a K-symmetric channel with additive white Gaussian noise. This list detector is applied to the problem of iterative multiple-user decoding, approximating the APP computation by marginalization over these P sequences, rather than all possible 2/sup K/ sequences. Simulation results indicate that using only small values of P, very good performance may be obtained. It is also demonstrated how to incorporate prior probabilities (a requirement for iterative decoding). The overall per-bit computational complexity of the approach is O(K/sup 2/+PlogP). It is also shown that for any multiuser system possessing a polynomial complexity optimal detection algorithm it is possible to obtain the P most probable sequences with polynomial complexity.

We consider a simple conceptual model of random accessing to a receiver deploying multiuser detection techniques. The model is a simple extension of Massey and Mathys' collision channel without feedback in which a certain probability of recovery from collision is introduced. As the main result, we derive the slot-synchronized capacity region of this recovery channel and show that for sufficiently powerful multiuser detectors, maximal performance is achieved without any sophisticated transmission protocols. We also explore the effect of a simple fading model.

We derive the Linear Minimum Mean Square Error (LMMSE) receiver for Wyner's model of a linear cellular array. By exploiting the special structure of the channel model, we obtain explicit Mean Square Error (MSE) expressions and information capacity formulae for both finite-sized as well as infinite-sized linear cellular arrays. We show that the performance of an individual user becomes insensitive to the array size for large array sizes and that the proportion of users achieving almost the same performance converges to one, as the array size tends to infinity. The effects of intercell interference and noise on the performance of each user are also investigated.

Optimal puncturing ratios for parallel concatenated codes with two or more constituent codes are found using extrinsic information transfer functions. These ratios minimize the signal-to-noise ratio convergence threshold and provide additional degrees of freedom for constructing codes with low thresholds over a wide range of code rates.

A strategy is described for closely approximating the symbol a-posteriori probabilities in systems with large dimensionality, by marginalising over a small high-probability subset of possible sequences. The variation in the required size of this subset with system parameters is investigated.

The nonGaussian behaviour of extrinsic log-values (L-values) during iterative turbo-decoding process is investigated in this paper. We assess the use of the Pearson system to model the extrinsic L-values nonGaussian behaviour

The Arimoto-Blahut algorithm is generalized for computation of the total capacity of discrete memoryless multiple access channels. This extension is based on the specialization of the Kuhn-Tucker condition for the total capacity of the multiple access channel, and depends on the result announced by Y. Watanabe et al. (2002) concerning the sufficiency of the Kuhn-Tucker condition.

Most space-time coding schemes can be classified either as noncoherent or coherent. In this paper we prove that optimal noncoherent decoding can always be decomposed into a channel estimation step followed by coherent decoding step. Surprisingly the required estimators do not in general minimise the mean squared error between the estimated and actual channel.

We present information theoretic capacity results for information transfer in space, under the general assumption that the receiver applies a spatial filter to receive signals. Our work presents novel applications of linear, bounded, invariant operators to communication channels. We outline the procedure for calculating the information theoretic capacity for this restricted class of operator channels and apply this result to wireless information transfer.

One powerful approach for multiuser decoding is to iterate between a linear multiuser filter (which ignores coding constraints) and individual decoders (which ignore multiple-access interference). Subject to clearly formulated statistical assumptions and the history of input signals provided by the outer decoders over all previous iterations, an extrinsic Kalman filter is suggested. This approach is motivated by the recent observation that decoder outputs are loosely correlated during initial iterations. Numerical results show that iterative decoding using this filter provides better performance in terms of the supportable load and convergence speed as compared to previously suggested linear-filter-based iterative decoders.

The Arimoto-Blahut (1972) algorithm is generalized for computation of the total capacity of discrete memoryless multiple-access channels (MAC). In addition, a class of MAC is defined with the property that the uniform distribution achieves the total capacity. These results are based on the specialization of the Kuhn-Tucker condition for the total capacity of the MAC, and an extension of a known symmetry property for single-user channels.

A space-time coding method with low decoding complexity suitable for large numbers of antennas and high data rates is presented. High dimensionality is accommodated through use of a sub-optimal receiver that efficiently locates short vectors in a high-dimensional lattice. These vectors are used to approximate the transmitted symbol a-posteriori probabilities, which are refined by an outer serially concatenated code. We show that the codes can achieve hundreds of bits per channel use at low signal-to-noise ratios.

Serial concatenation of simple error control codes and differential space-time modulation is considered. Decoding is performed iteratively by passing symbol-wise a posteriori probability values between the decoders of the inner space-time code and the outer code. An extrinsic information transfer analysis is used to predict thresholds for outer convolutional codes of various memory orders and a simple outer parity-check code. This parity-check code is well matched to the inner differential space-time code and achieves a bit-error rate (BER) of 10/sup -6/ less than 2 dB from the Shannon capacity of the fast fading multiple antenna channel. The differential space-time code can also be used to generate a priori information in the absence of channel knowledge. This information can be exploited by a channel estimator inserted into the decoding iteration. It is demonstrated that the inner space-time code provides soft training symbols from periodically inserted training symbols. The reliability of these soft training symbols does not depend on the speed of the channel variations, but on the structure of the inner code and the signal-to-noise ratio (SNR). Simulation studies confirm these findings and show that the proposed system with no initial channel knowledge achieves a performance very close to that of the system with perfect channel knowledge.

Convergence analysis of iterative detectors for narrow-band multiple access is performed using extrinsic information transfer charts. The system has no bandwidth expansion, so K users use the same bandwidth as a single user. The load (the number of bits used per channel) of the system is therefore higher than the load in, for example, conventional CDMA systems. The analysis provides useful guidelines on how to combine outer codes with the chosen mapper for different loads of the system. Both memoryless mappers and differential mappers are evaluated. We present the limitations of the system measured with the maximum number of users and the required SNR for different scenarios.

Motivated by the potential to reuse the decoder architecture, and thus reduce circuit space, we explore the use of iterative encoding techniques which are based upon the graphical representation of the code. We design codes by identifying associated encoder convergence constraints and also eliminating some well known undesirable properties for sum-product decoding such as 4-cycles. In particular we show how the Jacobi method for iterative matrix inversion can be viewed as message passing and employed as the core of an iterative encoder. Example constructions of both regular and irregular LDPC codes that are encodable using this method are investigated.

We propose a low complexity iterative multiuser decoder. We perform the multiuser a-posteriori probability calculation based on the marginalization of probabilities over a subset of the P highest probable sequences. Given a K user symmetric channel this list may be approximated closely with per-bit computational complexity O(K + P + 2K log K). We further show that for any multiuser system possessing a polynomial complexity optimal detection algorithm it is possible to obtain the P highest probable sequences with polynomial complexity. We further show that for any multiuser channel it is possible to obtain P highly probable sequences in polynomial time and hence utilize the list detection procedure for iterative decoding.

The serial concatenation of standard convolutional codes with differential space-time modulation is considered for fast flat fading multiple antenna channels. Decoding is performed iteratively by passing symbol-wise a-posteriori probability information between the decoders of the inner space-time code and the outer convolutional code. An input-output extrinsic information transfer analysis is used to predict thresholds for outer codes or various memory orders. Simulation results show that this system can achieve bit error rates below 10/sup -4/ at less than 2.5 dB from the Shannon capacity or the multiple antenna channel.

Mutual information transfer characteristics have been proposed by ten Brink (see IEE Electron. Lett., vol.35, no.10, p.806-9, 1999) as a quasi-analytical tool for the performance analysis of iterative decoding of concatenated codes. Given the individual transfer characteristics of the component codes in a concatenated coding system (obtained by simulation), the convergence region and average decoding trajectory of the concatenated system may be accurately predicted. In this paper, we extend the techniques of ten Brink to non-binary codes. In addition to providing a useful tool for the analysis of non-binary codes, our extension reveals several subtle points concerning the motivation and interpretation of the technique for binary codes. We propose a method for practical implementation of our extension, and apply the technique to the evaluation or non-binary turbo codes and space-time turbo codes.

We investigate a sub-optimal iterative receiver for joint equalization and decoding called a turbo-equalizer. We view the evolution of the error variance of the transmitted symbols through iterative processing, obtaining the convergence analysis. This allows us to predict the asymptotic performance (when the turbo-equalizer has converged) but also the trigger point observed in its performance.

Serial concatenation of standard convolutional or block codes with differential space-time modulation is considered for flat fading multiple antenna channels. Extrinsic information transfer is used to predict thresholds for various outer codes. Using the differential structure of the inner code near coherent performance is obtained without the use of training symbols.

We consider the convergence in norm of several iterative implementations of linear multiuser receivers, under the assumption of long random spreading sequences. We find that asymptotically, linear parallel interference cancellation diverges for systems loads of greater than about 17%. Using known results from the theory of iterative solutions for linear systems we derive optimal or near-optimal relaxation parameters for parallel (first- and second-order stationary, Chebyshev) and serial cancellation (successive relaxation) methods. An analytic comparison of the asymptotic convergence factor for the various methods is given. Simulations are used to verify results for finite size systems.

It is shown that the encoding/decoding problem for any asynchronous M-user discrete memoryless multiple-access channel can be reduced to corresponding problems for at most 2M-1 single-user discrete memoryless channels. This result, which extends a similar result for Gaussian channels, reduces the seemingly hard task of finding good multiple-access codes to the much better understood task of finding good codes for single-user channels. As a by-product, some interesting properties of the capacity region of M-user asynchronous discrete memoryless channels are derived.

We investigate a sub-optimal reduced-complexity iterative technique for joint detection and estimation for sets of constrained sequences and derive analytical results concerning convergence regions and fixed points. We apply this theory to the problem of multiple-user decoding.

We consider the problem of joint decoding and channel estimation for linear multiple-input multiple-output channels. We assume that the receiver has no a priori knowledge of the channel parameters. The amount of training data required is reduced by using a decision feedback approach to iteratively improve channel estimates. We present experimental results for joint channel estimation and decoding of space-time channels.

It is demonstrated that optimal multiple-user detection in a linear multiple-access system with identical crosscorrelations requires only /spl Oscr/(KlogK) operations instead of the worst case O(2/sup K/). A simple optimal detection algorithm is given, which when generalized has a complexity that is exponential not in the number of users but in the number of unique crosscorrelation values.

The effect of using randomly selected sequence multisets for the uplink of a synchronous code-division multiple-access channel is considered. A tight lower bound on the expected value of the sum capacity over the ensemble of randomly selected sequence multisets is given. For large systems, the sum rate penalty for using randomly selected multisets is shown to be at most 1 nat and to vanish as the number of users becomes large, compared to the sequence length.

A collision-type multiple access system is investigated in which every user transmits symbols from a common N-ary frequency-shift-keyed signal alphabet. We present a series of information-theoretic properties of the associated mathematical channel model. In the absence of noise, we calculate a large system approximation to the sum capacity, which is used to show that, in the limit, the combining of the multiple-accessing and coding results in no loss in capacity, compared to a fixed-allocation scheme. The presence of thermal noise or undetected users influences the capacity. Bounds on the capacity of the channel in the presence of thermal noise are calculated, as well as the capacity of the system in the presence of interfering users. Finally, a new iterative multiuser detector, the consensus decoder, is described and simulation performance results are shown. It is demonstrated that this decoder can operate to within approximately 70% of the channel capacity.

We examine the behaviour of the information theoretic capacity of jointly detected (multiuser) symbol synchronous DS-SSMA systems, when randomly selected spreading sequences are used. We find upper and lower bounds on capacity for a certain cross-correlation measure, and show that if the number of users is larger than the sequence length, that the lower bound tends to the maximum capacity with increasing sequence length. This implies that for large systems, random spreading sequences are optimal in terms of capacity. We also examine more realistic cases for the number of users and sequence length, and find that in certain cases that the use of random spreading sequences results only in a very small decrease in capacity. I. Introduction In a recent paper by Rupf and Massey [1], it was shown that any sequence multiset that achieves Welch's lower bound on total squared correlation [2] (denoted a WBE set) maximises capacity for the Gaussian direct sequence spread spectrum multiple access ...