Current-steering (CS) digital-to-analog converters (DACs) generate analog signals by combining weighted current sources. Ideally, the current sources are combined at each switching instant simultaneously. However, this is not true in practice due to timing mismatch, resulting in nonlinear distortion. This work uses the equivalent timing error model, introduced by previous work, to analyze the signal-to-distortion ratio (SDR) resulting from these timing errors. Using a behavioral simulation model we demonstrate that our analysis is significantly more accurate than the previous methods. We also use our simulation model to investigate the effect of timing mismatch in partially-segmented CS-DACs, i.e., those comprised of both equally-weighted and binary-weighted current sources.

This work presents analysis and calibration of interleaving and data timing errors that are encountered in modern times-2 interleaved digital-to-analog converters (DACs) with a current-steering (CS) architecture. Such errors corrupt the DAC output spectrum with spectral images that require calibration. We develop an analytical model for the interleaving and data timing errors that we understand are most significant and propose a calibration algorithm that treats all of them. Extensive simulations of the algorithm are made possible by leveraging the speed and accuracy of the analytical model. The algorithm is demonstrated on a commercially-developed 10-bit times-2 interleaved CS-DAC, operating at 40GS/s in 14nm CMOS.

We present Deep-n-Cheap – an open-source AutoML framework to search for deep learning models. This search includes both architecture and training hyperparameters, and supports convolutional neural networks and multilayer perceptrons. Our framework is targeted for deployment on both benchmark and custom datasets, and as a result, offers a greater degree of search space customizability as compared to a more limited search over only pre-existing models from literature. We also introduce the technique of ’search transfer’, which demonstrates the generalization capabilities of our models to multiple datasets. Deep-n-Cheap includes a user-customizable complexity penalty which trades off performance with training time or number of parameters. Specifically, our framework results in models offering performance comparable to state-of-the-art while taking 1-2 orders of magnitude less time to train than models from other AutoML and model search frameworks. Additionally, this work investigates and develops various insights regarding the search process. In particular, we show the superiority of a greedy strategy and justify our choice of Bayesian optimization as the primary search methodology over random / grid search.

The high computational complexity associated with training deep neural networks limits online and real-time training on edge devices. This paper proposed an end-to-end training and inference scheme that eliminates multiplications by approximate operations in the log-domain which has the potential to significantly reduce implementation complexity. We implement the entire training procedure in the log-domain, with fixed-point data representations. This training procedure is inspired by hardware-friendly approximations of log-domain addition which are based on look-up tables and bit-shifts. We show that our 16-bit log-based training can achieve classification accuracy within approximately 1% of the equivalent floating-point baselines for a number of commonly used datasets.

The high energy cost of processing deep convolutional neural networks impedes their ubiquitous deployment in energy-constrained platforms such as embedded systems and IoT devices. This article introduces convolutional layers with pre-defined sparse 2D kernels that have support sets that repeat periodically within and across filters. Due to the efficient storage of our periodic sparse kernels, the parameter savings can translate into considerable improvements in energy efficiency due to reduced DRAM accesses, thus promising significant improvements in the trade-off between energy consumption and accuracy for both training and inference. To evaluate this approach, we performed experiments with two widely accepted datasets, CIFAR-10 and Tiny ImageNet in sparse variants of the ResNet18 and VGG16 architectures. Compared to baseline models, our proposed sparse variants require up to ~82% fewer model parameters with 5.6× fewer FLOPs with negligible loss in accuracy for ResNet18 on CIFAR-10. For VGG16 trained on Tiny ImageNet, our approach requires 5.8× fewer FLOPs and up to ~83.3% fewer model parameters with a drop in top-5 (top-1) accuracy of only 1.2% (~2.1%). We also compared the performance of our proposed architectures with that of ShuffleNet and MobileNetV2. Using similar hyperparameters and FLOPs, our ResNet18 variants yield an average accuracy improvement of ~2.8%.

The enormous success of advanced wireless devices is pushing the demand for higher wireless data rates. The industry is satisfying this increasing demand by densely deploying large numbers of access points (APs). Unfortunately, unicast rates, especially in crowded scenarios, remain very low due to severe interference and time-sharing. However, one may take advantage of the broadcasting nature of wireless transmissions to offer high multicast rates. Motivated by this, we present coordinated broadcasting (Co-BCast), a system which coordinates multiple APs to provide participants of big events with high multicast rates that can support multiple high definition video streams.

Advances in lattice-based cryptography are enabling the use of public key algorithms (PKAs) in power-constrained ad hoc and sensor network devices. Unfortunately, while many wireless networks are dominated by group communications, PKAs are inherently unicast—i.e., public/private key pairs are generated by data destinations. To fully realize public key cryptography in these networks, lightweight PKAs should be augmented with energy-efficient mechanisms for group key agreement. We consider a setting where master keys are loaded on clients according to an arbitrary distribution. We present a protocol that uses session keys derived from those master keys to establish a group key that is information-theoretically secure. When master keys are distributed randomly, our protocol requires$O(\log_b t)$multicasts, where$1-1/b$is the probability that a given client possesses a given master key. The minimum number of public multicast transmissions required for a set of clients to agree on a secret key in our setting was recently characterized. The proposed protocol achieves the best possible approximation to that optimum that is computable in polynomial time. Moreover, the computational requirements of our protocol compare favorably to multi-party extensions of Diffie-Hellman key exchange.

Conditionally cycle-free graphical models (i.e., cyclic graphical models which become cycle-free after conditioning on a subset of the hidden variables) are constructed for coset codes. Following the description of a general construction procedure, examples of a number of families of codes-including first-order Reed-Muller (RM) and the Delsarte-Goethals codes - are provided for which the proposed procedure yields optimal soft-in soft-out (SISO) decoding algorithms that are less complex than the best known trellis-based algorithms. In the case of the first-order RM codes, which have a recursive coset construction, the optimal SISO decoding algorithm that results when the proposed construction is applied repeatedly is denoted recursive coset representation (RCR) decoding. Connections are made between RCR decoding and existing algorithms that exploit fast Hadamard transforms. Finally, the utility of the proposed decoding algorithms are supported by a practically motivated application: the construction of serially concatenated codes that have high rates and low error floors. Extended Hamming codes are proposed as outer codes in such constructions with efficient decoding employing the SISO algorithms developed herein.

Barrage relay networks (BRNs) are mobile ad hoc networks designed from the ground up to meet the demands of tactical edge communications. The fundamental building block of BRNs is not a point-to-point wireless link, but rather a rapid and robust broadcast mechanism that employs an autonomous cooperative communications scheme. Following a summary of basic BRN concepts, this paper demonstrates how the efficient barrage broadcast mechanism can be contained for unicast traffic via controlled barrage regions (CBRs). In particular, a protocol for CBR establishment is defined and formally verified.

This letter presents an iterative soft-in soft-out (SISO) decoding algorithm based on redundant Tanner graphs that is applicable to arbitrary linear block codes. The proposed algorithm utilizes the permutation group of a code in order to efficiently and randomly generate redundant parity-checks.

Two broad classes of graphical modeling problems for codes can be identified in the literature: constructive and extractive problems. The former class of problems concern the construction of a graphical model in order to define a new code. The latter class of problems concern the extraction of a graphical model for a (fixed) given code. The design of a new low-density parity-check code for some given criteria (e.g., target block length and code rate) is an example of a constructive problem. The determination of a graphical model for a classical linear block code that implies a decoding algorithm with desired performance and complexity characteristics is an example of an extractive problem. This work focuses on extractive graphical model problems and aims to lay out some of the foundations of the theory of such problems for linear codes. The primary focus of this work is a study of the space of all graphical models for a (fixed) given code. The tradeoff between cyclic topology and complexity in this space is characterized via the introduction of a new bound: the forest-inducing cut-set bound (FI-CSB). The proposed bound provides a more precise characterization of this tradeoff than that which can be obtained using existing tools (e.g., the CSB) and can be viewed as a generalization of the square-root bound for tail-biting trellises to graphical models with arbitrary cyclic topologies. Searching the space of graphical models for a given code is then enabled by introducing a set of basic graphical model transformation operations that are shown to span this space. Finally, heuristics for extracting novel graphical models for linear block codes using these transformations are investigated.

Generalized Tanner graphs have been implicitly studied by a number of authors under the rubric of generalized parity-check matrices. This work considers the conditioning of binary hidden variables in such models in order to break all cycles and thus derive optimal soft-in soft-out (SISO) decoding algorithms. Conditionally cycle-free generalized Tanner graphs are shown to imply optimal SISO decoding algorithms for the first order Reed-Muller codes and their duals - the extended Hamming codes - which are substantially less complex than conventional bit-level trellis decoding. The study of low-complexity optimal SISO decoding algorithms for the family of extended Hamming codes is practically motivated. Specifically, it is shown that exended Hamming codes offer an attractive alternative to high- rate convolutional codes in terms of both performance and complexity for use in very high-rate, very low-floor, serially concatenated coding schemes.

In this paper, we present an overview on the design of algorithms for iterative detection over channels with memory. The starting point for all the algorithms is the implementation of soft-input soft-ouput maximum a posteriori (MAP) symbol detection strategies for transmissions over channels encompassing unknown parameters, either stochastic or deterministic. The proposed solutions represent effective ways to reach this goal. The described algorithms are grouped into three categories: i) we first introduce algorithms for adaptive iterative detection, where the unknown channel parameters are explicitly estimated; ii) then, we consider finite-memory iterative detection algorithms, based on ad hoc truncation of the channel memory and often interpretable as based on an implicit estimation of the channel parameters; and iii) finally, we present a general detection-theoretic approach to derive optimal detection algorithms with polynomial complexity. A few illustrative numerical results are also presented.

This work focuses on the expansion properties of a Tanner Graph because they are known to be related to the performance of associated iterative message-passing algorithms over various channels. By analyzing the eigenvalues and corresponding eigenvectors of the normalized incidence matrix representing a Tanner Graph, lower bounds on these expansion properties are derived. Specifically, for the binary erasure channel, these results lead to two lower bounds on stopping distance for any given binary linear code and an upper bound on stopping redundancy for the family of difference-set codes (type-I 2-D projective geometry low-density parity-check (LDPC) codes).

The optimal detector for coded multiple antenna systems is too complex to be implemented. Even approximations to the optimal decoder, such as iterating between detection and decoding, are too complex for many practical systems. Thus, we consider a number of spatial stream decouplers with the assumption of separate decoding and decoupling. The linear zero-forcing decoupler, the linear minimum mean-squared error (LMMSE) decoupler, the successive soft/hard interference canceller, and the parallel soft/hard interference canceller are investigated. The capacity of the channel including these constrained receiver structures is analyzed. It is shown that no other decoupler can achieve larger capacity than the LMMSE decoupler in a sense that it achieves the maximum sub-channel capacities. This contrasts the general belief that interference cancellation schemes are better than linear filters. This is because this general belief is based on the assumption of perfect interference cancellation, which, in practice, requires joint decoding/decoupling. We discuss the likelihood value derivation from the decouplers, which can be used for decoding error correction codes. The performance of parallel transmission of turbo-coded symbols is given to support the constrained capacity analysis.

We derive iterative message passing update rules for solving the bipartite maximum weighted matching problem. It is shown that if the optimal matching solution is unique, the algorithm converges to this optimal solution at a rate comparable to the algorithm of Bayati et. al. It is shown that the two algorithms are both standard messages passing, but on dual graphs of each other. Also, the algorithm presented here requires less storage. We also provide a method to use the proposed algorithm to solve the integer maximal weighted matching problem - i.e., where the optimal solution is generally not unique

A number of authors have recently considered iterative soft-in soft-out (SISO) decoding algorithms for classical linear block codes that utilize redundant Tanner graphs. Jiang and Narayanan presented a practically realizable algorithm that applies only to cyclic codes while Kothiyal et al. presented an algorithm that, while applicable to arbitrary linear block codes, does not imply a low-complexity implementation. This work first presents the aforementioned algorithms in a common framework and then presents a related algorithm - random redundant iterative decoding - that is both practically realizable and applicable to arbitrary linear block codes. Simulation results illustrate the successful application of the random redundant iterative decoding algorithm to the extended binary Golay code. Additionally, the proposed algorithm is shown to outperform Jiang and Narayanan's algorithm for a number of Bose-Chaudhuri-Hocquenghem (BCH) 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/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 G=(U/spl cup/W, E) be a bipartite graph with disjoint vertex sets U and W, edge set E, and girth g. This correspondence presents an algorithm for counting the number of cycles of length g, g+2, and g+4 incident upon every vertex in U/spl cup/W. The proposed cycle counting algorithm consists of integer matrix operations and its complexity grows as O(gn/sup 3/) where n=max(|U|,|W|).

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

In this paper, we derive an equivalent channel model for constant envelope, continuous phase (CECP) signals transmitted over the bandlimited additive white Gaussian noise (AWGN) channel. Using this equivalent channel model, it is proved that at high carrier-to-noise ratio (CNR), the capacity of coherent and non-coherent CECP-AWGN channel are the same. We then derive the main result of this paper, i.e., the capacity of the CECP-AWGN channel under Carson's rule bandwidth constraint. For comparison, the symmetric information rate (SIR) of several commonly used bandwidth efficient continuous phase modulation (CPM) signals are estimated using the method described in Kuo and Chugg (2004). We conclude that under Carson's rule bandwidth measure, the bandwidth efficiency of these CPM signals is still far below the CECP-AWGN capacity.

Iterative message passing algorithms on graphs, which are generalized from the well-known turbo decoding algorithm, have been studied intensively in recent years because they can provide near-optimal performance and significant complexity reduction. In this paper, we demonstrate that this technique can be applied to pseudorandom code acquisition problems as well. To do this, we represent good pseudonoise (PN) patterns using sparse graphical models, then apply the standard iterative message passing algorithms over these graphs to approximate maximum-likelihood synchronization. Simulation results show that the proposed algorithm achieves better performance than both serial and hybrid search strategies in that it works at low signal-to-noise ratios and is much faster. Compared with full parallel search, this approach typically provides significant complexity reduction.

The traditional method of sending a training signal to identify a channel, followed by data, may be viewed as a simple code for the unknown channel. Results in blind sequence detection suggest that performance similar to this traditional approach can be obtained without training. However, for short packets and/or time-recursive algorithms, significant error floors exist due to the presence of sequences that are indistinguishable without knowledge of the channel. In this paper, we reconsider training-signal design in light of recent results in blind sequence detection. Specifically, we consider the tradeoff between the complexity of receiver processing and the amount of training overhead required. More generally, we design training codes which combine modulation and training. In order to design these codes, we find an expression for the pairwise error probability of the joint maximum-likelihood (JML) channel and sequence estimator. This expression motivates a pairwise distance for the JML receiver based on principal angles between the range spaces of data matrices. The general code-design problem (generalized sphere packing) is formulated as the clique problem associated with an unweighted, undirected graph. We provide optimal and heuristic algorithms for this clique problem. For both long and short packets, we demonstrate that significant improvements are possible by jointly considering the design of the training, modulation, and receiver processing.

Density evolution has recently been used to analyze iterative decoding and explain many characteristics of iterative decoding including convergence of performance and preferred structures for the constituent codes. The scaling of extrinsic information (messages) has been heuristically used to enhance the performance in the iterative decoding literature, particularly based on the min-sum message passing algorithm. In this paper, it is demonstrated that density evolution can be used to obtain the optimal scaling factor and also estimate the maximum achievable scaling gain. For low density parity check (LDPC (codes and serially) concatenated convolutional codes (SCCC) with two-state constituent codes, the analytic density evolution technique is used, while the signal-to-noise ratio (SNR) evolution technique and the EXIT chart technique is used for SCCC with more than 2 state constituent codes. Simulation results show that the scaling gain predicted by density evolution or SNR evolution matches well with the scaling gain observed by simulation.

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.

In this paper, we show that the direct transmission scheme of low-density parity-check (LDPC) codes can achieve the upper bound of rate-diversity tradeoff with probability one for multiple-input multiple-output (MIMO) systems with BPSK modulation. We then present an algorithm to construct the LDPC space-time codes through a 2-dimensional array whose doubly-periodic correlation is bounded by 1.

In this paper, we propose a novel method to construct low rate recursive convolutional codes. The 'overall' convolutional code has a block code and a simple recursive convolutional code as building blocks. The novelty of this type of convolutional code is that it uses coset leaders in order to distinguish the signals that originate from different states. Several of these codes are then used to construct low rate turbo-like codes. Apart from being bandwidth efficient, simulation results show that these codes outperform the best known low rate turbo-like codes, the turbo-Hadamard codes (THC), in additive white Gaussian noise (AWGN) channel for interleaver sizes of practical interest.

We describe an approach for the identification of good distance spectra for possibly existing binary linear block codes based on linear programming and the MacWilliams-Delsarte (1977, 1972) identities. Specifically, the linear program is defined by an expression characterizing the performance of a potential code in terms of its distance spectrum and constraints imposed by the MacWilliams-Delsarte identities. Using the union bound to characterize performance, our results suggest that the best distance spectrum is not a function of signal-to-noise ratio (SNR) above the cutoff rate SNR and also suggest the existence of several unknown, good codes. Characterizing the performance using the maximum spectral error component of the union bound suggests spectral thinning with decreasing SNR.

This article presents a new asymptotically exact lower bound on pairwise error probability of a space-time code as well as an example code that outperforms the comparable orthogonal-design-based space-time (ODST) code. Also contained in the article are an exact expression for pairwise error probability (PEP), signal design guidelines, and some observations relating to the reception of ODST codes.

We introduce a simple method to construct very low rate systematic recursive convolutional codes from a standard rate 1/2 code. These codes in turn are used in parallel concatenation to obtain very low rate turbo codes. This construction always leads to a class or convolutional codes for which the signals on trellis transition are a subset or complete bi-orthogonal signal set for any given code rate. The resulting codes are rate compatible and require low complexity decoders. By applying this construction methodology to the rate 1/2 turbo code used in 3G standard, we show that an additional coding gain of approximately 1.2 dB is achievable at a bit error rate of 10/sup -5/.

A general structure of trellis-based reduced-state soft-input/soft-output (RS-SISO) algorithms for communication systems based on concatenated finite state machines (FSMs) with large memory is presented. Based on forward and backward reduced-state (RS) recursions, a particular structure for the RS-SISO algorithm can be obtained by setting suitable parameters in the general formulation. Two novel RS-SISO algorithms are proposed based on a bi-directional state reduction paradigm. To assess the performance of the proposed RS-SISO algorithms, numerical simulations are conducted for isolated long intersymbol interference with additive white Gaussian noise (ISI/AWGN) channels and a serially concatenated system given by interleaved trellis coded modulation (TCM) over an ISI/AWGN channel. Simulation results show that low-complexity RS-SISO algorithms can approach the performance of a full-state SISO algorithm. Moreover, one of the novel RS-SISO algorithms is found to be robust in all the considered cases.

This paper provides an overview of the results in a recent journal submission by the same authors. The first part of that paper studies the pairwise error probability of codewords (PEP) of a space-time code over a quasistatic channel, using an approach that allows both known and unknown channel cases to be considered simultaneously. A closed-form expression for the PEP is provided, and given a constraint on the sum of the squares of the singular values of the difference signal matrix, it is shown that the PEP is minimized by choosing signals with equal singular values. A useful sequence of simple upper and lower bounds that converge to the PEP is also provided. An example space-time code is introduced and shown using this sequence of bounds to outperform the corresponding orthogonal-design-based space-time (ODST) code at all values of SNR. Exact expressions, based on the PEP, are given for the asymptotic coding and diversity gain. It is shown that the diversity gain remains unchanged if the PEP is replaced by either the codeword error probability (CEP) or else the message symbol error probability (SEP). Signal-design implications of the above results are also discussed. The second part deals with ODST codes. It is shown that ODST codes represent an instance of orthogonal signaling. This observation is used to derive a closed-form expression for the pairwise error probability of message symbols (PEP-ms) of these codes, as well as an expression for coding gain based on PEP-ms, that is exact in the case of BPSK signaling.

Iterative detection (ID) has proven to be a near-optimal solution for concatenated finite state machines (FSMs) with interleavers over an additive white Gaussian noise (AWGN) channel. When perfect channel state information (CSI) is not available at the receiver, an adaptive ID (AID) scheme is required to deal with the unknown, and possibly time-varying, parameters. The basic building block for ID or AID is the soft-input soft-output (SISO) or adaptive SISO (A-SISO) module. The complexity of SISOs and A-SISOs increases exponentially with constraint length. Reduced state SISO (RS-SISO) algorithms have been applied to reduce the complexity of the A-SISO module. We show that serially concatenated CPM (SCCPM) with AID has turbo-like performance over fading ISI channels and also RS-A-SISO systems have large iteration gains. Various design options for RS-A-SISO algorithms are evaluated and performance and complexity are compared.

In this paper we examine the possibility of applying fixed-lag smoothing techniques to trellis coded quantization (TCQ). For this application, we exploit the tree structure of the predictive TCQ (P-TCQ). We apply the (M,L) algorithm for searching the tree and Kalman smoother to find the smoothed estimates of the data. The performance of the resulting smoothed TCQ (S-TCQ) is compared to that of some other predictive quantization techniques such as predictive TCQ (P-TCQ), smoothed differential pulse code modulation (S-DPCM) and scalar DPCM codes. We find that the proposed S-TCQ outperform all the other schemes mentioned above by more than 1 dB when applied to several synthetic sources.

A reduced complexity algorithm is presented for iterative multiuser detection (MUD) and decoding of asynchronous users. For complexity reduction, multiple soft-input soft-output (SISO) modules are operated in parallel each executing the Verdu (see Multiuser Detection, Cambridge University Press, Cambridge, UK, 1998) optimum detection algorithm on a subset of active users. The novel approach introduced is the application of soft-output broadcasters (SOBC) to combine the soft values generated by parallel MUD-SISOs which model the same user. SOBC modules then exchange soft information with SISO decoders and after the first receiver iteration provide probability values necessary for soft cancellation of the interfering users not modeled in each MUD-SISO. Simulation results show that, after multiple iterations, performance of the reduced-complexity algorithm converges to the single user bound at a slightly degraded SNR threshold relative to the full-complexity algorithm, and acceptable performance is achieved with significant reduction in computational complexity.

Space-time convolutional codes have been shown to provide improved performance for high data rate transmission over fading channels through combined space diversity and coding gain. However, there are still some questions on how to design the codes in binary or discrete domain to achieve these gains in the complex domain of baseband-modulated signals. In this paper, we first consider the effect of minimum distance in the space-time codes, then propose a new efficient design method which is based on the upper and lower bounds of the coding gain. The simulation result shows that the new approach allows a fast search for optimal space-time convolutional codes for many practical problems.

Based on message-passing techniques, a novel iterative grid algorithm for the general two-dimensional (2D) digital least metric (DLM) problem is proposed and applied to image halftoning. The algorithm attempts to achieve a globally optimal solution via a local-metric computation and message passing as opposed to other 2D iterative global-metric optimizations such as simulated annealing and toggle/swap scheme. A reduced-complexity version of the proposed digital image halftoning technique is demonstrated. Results show that the quality of the halftone images is comparable to that of the state-of-the-art toggle/swap algorithm. Since the algorithm is not constrained by the specific metric used, the proposed method is directly applicable to other digital image processing tasks (eg, optimal near-lossless coding or entropy-constrained halftoning).

The standard algorithm for computing the soft-inverse of a finite-state machine [i.e., the soft-in/soft-out (SISO) module] is the forward-backward algorithm. These forward and backward recursions can be computed in parallel, yielding an architecture with latency /spl Oscr/(N), where N is the block size. We demonstrate that the standard SISO computation may be formulated using a combination of prefix and suffix operations. Based on well-known tree-structures for fast parallel prefix computations in the very large scale integration (VLSI) literature (e.g., tree adders), we propose a tree-structured SISO that has latency /spl Oscr/(log/sub 2/N). The decrease in latency comes primarily at a cost of area with, in some cases, only a marginal increase in computation. We discuss how this structure could be used to design a very high throughput turbo decoder or, more generally, an iterative detector. Various subwindowing and tiling schemes are also considered to further improve latency.

The problem of performing iterative detection (ID)-a technique originally introduced for the decoding of turbo codes-for systems having parametric uncertainty has received relatively little attention in the open literature. In this paper, the problem of adaptive ID (AID) for serial and parallel concatenated convolutional codes (SCCCs and PCCCs or turbo codes) in the presence of carrier-phase uncertainty is examined. Based on the theoretical framework of Anastasopoulos and Chugg, (see Proc. Int. Conf. Communications, p.177-181, 1999). and Colavolpe, Ferrari and Raheli (see IEEE Trans. Commun., vol.48, p.1488-98, 2000), adaptive soft inverse (ASI) algorithms are developed for two commonly used blocks in turbo codes, leading to the adaptive soft-input soft-output (A-SISO) and the adaptive soft demodulator (A-SODEM) algorithms. Based on these algorithms, practical AID receivers are presented. Several design options are proposed and compared and the impact of parametric uncertainty on previously established results for iterative detection with perfect channel state information (CSI) is assessed.

Some issues with Forney's upper and lower bounds (1972) for the symbol error probability in systems with memory (e.g., intersymbol interference channels) have been pointed out in the literature. We expound on these issues. For the upper bound, we show that, although the most commonly cited proofs are not logically consistent, the bound is true for more general conditions. The reasoning leading to the lower bound is shown to be flawed and, in general,to lead to invalid lower bounds. We suggest a lower bound based on Mazo's bound (1975) as an alternative.

Soft-input/soft-output (SISO) algorithms have been widely used for iterative detection in various applications since this technique was introduced for decoding turbo codes. However, the complexity of the SISO algorithms is a major concern in the detector implementation. A novel way to simplify the SISO algorithms is proposed based on the concept of state reduction via decision feedback. The resulting complexity reduction is exponential in the number of feedback taps. The proposed low-complexity SISO algorithm can be applied directly in place of the standard SISO (e.g., a full-state forward-backward algorithm). Additionally, thresholding the soft-outputs of the reduced-state (RS) SISO can provide a robust and effective alternative to RS sequence detectors. Simulation results are also provided to illustrate the advantages of the RS-SISO.

Several structures for fixed-lag (FL) soft-in/soft-out (SISO) algorithms in the case of a perfectly known channel are well-known. These forward-only and bi-directional fixed-lag SISOs have been described with the bi-directional version shown to be preferred. Adaptive iterative detection using adaptive SISOs (A-SISOs) have also been demonstrated to provide significant performance gains for time-varying channels. However, these impressive results have been obtained with fixed-interval, bi-directional A-SISOs and training signals at both ends of the data packet. We combine these results to develop and compare various adaptive, fixed-lag SISOs. Among several reasonable options considered, the preferred A-SISO algorithm is found to be bi-directional with forward-only channel estimation.

Several structures for adaptive iterative detection (AID) for fading channels have been described in the literature. One approach to AID, iterative detection with a decoupled estimator, has been proposed with hard decision feedback. Recently, it was noted that a soft decoder (e.g., turbo decoder) makes it possible to feed back soft information on data to the decoupled channel estimator. In this paper we present adaptive iterative detection with a decoupled channel estimator (decoupled-AID) based on hard or soft decision feedback from a turbo decoder. The performance of the decoupled-AID on two modulation methods (e.g., punctured-QPSK, 8PSK) is compared. As a decoupled channel estimator, the Wiener filter and Kalman filter are considered based on probabilistic channel models. A new feedback method, which uses partial soft information with or without amplitude normalization, is proposed.

The soft-input soft-output (SISO) module is the basic building block for established iterative detection (ID) algorithms for a system consisting of a network of finite state machines. The problem of performing ID for systems having parametric uncertainty has received relatively little attention in the open literature. Previously proposed adaptive SISO (A-SISO) algorithms are either based on an oversimplified channel model, or have a complexity that grows exponentially with the observation length N (or the smoothing lag D). In this paper, the exact expressions for the soft metrics in the presence of parametric uncertainty modeled as a Gauss-Markov process are derived in a novel way that enables the decoupling of complexity and observation length. Starting from these expressions, a family of suboptimal (practical) algorithms is motivated, based on forward/backward adaptive processing with linear complexity in N. Previously proposed A-SISO algorithms, as well as existing adaptive hard decision algorithms are interpreted as special cases within this framework. Using a representative application-joint iterative equalization-decoding for trellis-based codes over frequency-selective channels-several design options are compared and the impact of parametric uncertainty on previously established results for ID with perfect channel state information is assessed.

The performance of per-survivor processing (PSP) algorithms with stochastic gradient estimators is investigated for frequency-selective channels and array measurements. The focus is on the degree to which the underlying channel structure can be reliably exploited by such algorithms in tracking the time-varying channel and detecting the data.

The severity of frequency-selective fading channels necessitates the combining of multiple diversity sources to achieve acceptable performance. Traditional techniques often perform the combining of different sources of diversity separately, resulting in significant performance degradation. Algorithms for the joint optimal combining were reformulated in a form suitable for practical implementation. We investigate the applicability of these algorithms for the specific problem of interleaved TCM systems in frequency-selective fading channels with or without external diversity. It is demonstrated that soft decision equalization techniques are necessary and sufficient for the application of TCM techniques over such channels. In addition, it is shown that the design trade-offs associated with the resulting TCM techniques are significantly different than those associated with memoryless channels.

The general problem of performing digital data detection for a two-dimensional (2D) systems is considered with the specific application of page-access optical memory systems in mind. A simple 2D intersymbol interference (ISI) channel with additive white Gaussian noise (AWGN) is assumed. An equivalent signal model consisting of two one-dimensional systems separated by a block interleaver is developed and used to motivate the application of previously developed algorithms for data detection in concatenated systems. The resulting iterative detection algorithms, which are based on soft-output algorithms, are demonstrated to achieve near-optimal performance even for very severe 2D ISI channels.

Algorithms which compute either the a posteriori probability (APP) or the minimum sequence metric (MSM) of an input symbol to a finite state machine based on some portion of the observation sequence are developed. Full-record (i.e., type-I) and fixed-delay algorithms are both considered and related to existing algorithms. In particular, the fixed-delay APP and MSM algorithms developed are shown to be significantly less complex than the equivalent algorithms of Li, Vucetic, and Sato (1995) i.e. the optimal soft-output algorithm (OSA) and the simplified version (SSA), respectively.

The problem of performing adaptive maximum likelihood sequence detection (MLSD) for a slowly time-varying, frequency-selective, multipath channel based on array measurements is considered. Two adaptive MLSD algorithms with LMS estimation of the overall channel (i.e., all filtering and physical channel effects) are compared through simulations: conventional adaptive MLSD (CA-MLSD) and per survivor processing (PSP) based adaptive MLSD. The results suggest that PSP based adaptive MLSD is particularly effective and robust to variations in the channel structure, level of dynamics, delay spread profile, and timing offsets. Analytical characterization of the PSP based algorithm is developed. This algorithm has the additional advantage that it may be fully initialized with the same training overhead used in current single-antenna systems for channel identification.

A correspondence between the problem of two-dimensional digital least metric (DLM) fitting and data detection in serially concatenated systems in digital communication theory is described. Nearly optimal detection algorithms based on previous advances in iterative detection/decoding are applied to the DLM problem for two applications in digital image compression. The first application is least squares halftoning of digital images. The second is near-lossless (i.e., error constrained) minimum-entropy image compression. In both applications the use of the iterative algorithm yields significant improvements, measured in terms of residual metric, relative to previously suggested approaches to the DLM problem.

The blind acquisition characteristics of binary sequence detection algorithms based on per-survivor processing (PSP) are demonstrated via computer simulations. These capabilities are impressive as compared to those of traditional blind equalizers. It is demonstrated that the short-term acquisition performance of PSP-based algorithms is dominated by the poor performance obtained when certain sequences are transmitted. These sequences are those that cannot be distinguished by the joint maximum likelihood (ML) channel and sequence estimator or do not allow for a complete identification of the channel impulse response. Such sequences are defined and analytically characterized, resulting in asymptotic results on performance for joint ML channel and sequence estimators. Typical misacquisition conditions, the effects of initialization, and the impact of increased tree search complexity are also all characterized by simulations and motivated by the analytical results.

The general condition for the optimality of the Viterbi algorithm (VA) as a method for implementing maximum-likelihood sequence detection (MLSD) is described. It is shown that this folding condition is not met for the fading linear Gaussian channel. This clarifies previously published results and allows approaches for approximate MLSD to be viewed as an attempt to force the VA as a suboptimal solution.

The problem of performing joint maximum-likelihood (ML) estimation of a digital sequence and unknown dispersive channel impulse response is considered starting from a continuous-time (CT) model. Previous investigations of this problem have not considered the front-end (FE) processing in detail; rather, a discrete-time signal model has been assumed. We show that a fractionally-spaced whitened matched filter, matched to the known data pulse, provides a set of sufficient statistics when a tapped delay line channel model is assumed, and that the problem is ill-posed when the channel impulse response is generalized to a CT, finite-length model. Practical approximations are considered that circumvent this ill-posed condition. Recursive computation of the joint-ML metric is developed. Together, the FE processing and metric recursion provide a receiver structure which may be interpreted as the theoretical foundation for the previously introduced technique of per-survivor processing, and they lead directly to generalizations. Several FE processors representative of those suggested in the literature are developed and related to the practically optimal FE.

For pt. I see ibid., vol.44, no.7, p.836, 1996. The channel-tracking mode performance of the front-end (FE) processors is determined through approximate analysis and computer simulation. A general model for the FE processing, which encompasses these representative FEs, is assumed. Previous analysis techniques are extended to include the effects of FE processing. The specific system analyzed consists of a Rayleigh-fading, diffuse multipath channel, with several data pulse shapes considered. An adaptive maximum likelihood sequence estimation (MLSE) algorithm based on the per-survivor processing (PSP) technique is analyzed and compared to an algorithm based on correct symbol feedback. The results show that significant performance degradation is suffered when suboptimal FE processing is used. Some of the issues which may complicate matters in practice are examined with an emphasis on application in packet mobile radio systems. The limitations of the results and the models used are discussed.