Underwater acoustic environment estimation is a challenging but important task for remote sensing scenarios. Current estimation methods require high signal strength and a solution to the fragile echo labeling problem to be effective. In previous publications, we proposed a general deep learning-based method for two-dimensional environment estimation which outperformed the state-of-the-art, both in simulation and in real-life experimental settings. A limitation of this method was that some prior information had to be provided by the user on the number and locations of the reflective boundaries, and that its neural networks had to be re-trained accordingly for different environments. Utilizing more advanced neural network and time delay estimation techniques, the proposed improved method no longer requires prior knowledge the number of boundaries or their locations, and is able to estimate two-dimensional environments with one or two boundaries. Future work will extend the proposed method to more boundaries and larger-scale environments.

Learning the physical environment is an important yet challenging task in reverberant settings such as the underwater and indoor acoustic domains. The locations of reflective boundaries, for example, can be estimated using echoes and leveraged for subsequent, more accurate localization. Current boundary estimation methods are constrained to a regime of high signal strength, or mitigate noise with heuristic (suboptimal) filters. These limitations can lead to fragile estimators that fail under non-ideal conditions. Furthermore, many algorithms in the literature also require a correct assignment of echoes to boundaries, which is combinatorially hard. To evade these limitations, we develop a convolutional neural network method for robust 2D boundary estimation, given known emitter and receiver locations. Our method uses as its input data format transform images, which are the potential boundary locations mapped into curves. We demonstrated in simulations that the proposed neural network method outperforms alternative state-of-the-art algorithms.

Wireless assistive listening devices (ALDs), such as induction loops, radio-frequency transmitters, and digital streaming systems, improve accessibility for people with hearing loss by transmitting from a venue’s sound system directly to the listener. Today, ALDs are used primarily for lectures and performances. When paired with advanced hearing devices, however, they could form part of an augmented listening system that lets users "remix" sounds in their environment, including from loudspeakers in public spaces. For example, users could amplify public announcements or suppress background music while having a conversation. In the proposed system, a binaural adaptive filter uses the ALD signal to estimate the loudspeaker sound at the ears. The hearing device can then either enhance or remove the loudspeaker sound in the hearing device output while preserving other nearby sounds. We demonstrate the proposed system using several commercial ALDs and assess the effects of delay, bandwidth, distortion, and noise on real-world system performance.

Key challenges in developing underwater acoustic localization methods are related to the combined effects of high reverberation in intricate environments. To address such challenges, recent studies have shown that with a properly designed architecture, neural networks can lead to unprecedented localization capabilities and enhanced accuracy. However, the robustness of such methods to environmental mismatch is typically hard to characterize, and is usually assessed only empirically. In this work, we consider the recently proposed data-driven method [18] based on a deep convolutional neural network, and demonstrate that it can learn to localize in complex and mismatched environments. To explain this robustness, we provide an upper bound on the localization mean squared error (MSE) in the "true" environment, in terms of the MSE in a "presumed" environment and an additional penalty term related to the environmental discrepancy. Our theoretical results are corroborated via simulation results in a rich, highly reverberant, and mismatch channel.

High frequency (HF) radio communications offer latency advantages over fiber-optics in certain long-distance communication applications. As a result, there is interest in using HF for high-frequency trading (HFT), to make trans-continental market decisions that leverage the lower latency path of HF channels. The HF skywave channel is a dynamic medium and is one of the most challenging communication channels. Latencies in existing HF modems from coding and interleaving over several packets are prohibitive for HFT, which motivates the development of receivers that provide good performance given a delay constraint. In this paper, we present receiver designs that can be employed for low-latency reliable communication. We introduce a multitrellis adaptive Viterbi algorithm (MAVA) for sparse and time-varying intersymbol interference (ISI) channels, where the conventional Viterbi algorithm would lead to a large trellis. While multitrellis receiver designs have previously been considered, MAVA also incorporates real-time channel tracking, which is necessary for a practical HF receiver. We combine the MAVA algorithm with maximum a posteriori (MAP) detection to obtain a hybrid receiver with high-fidelity, low-delay performance. Finally, we conduct an asymptotic efficiency analysis of the hybrid receiver to gain insight into how deferring decisions improves performance in the high signal-to-noise ratio (SNR) regime.

Augmented listening devices, such as hearing aids and augmented reality headsets, enhance human perception by changing the sounds that we hear. Microphone arrays can improve the performance of listening systems in noisy environments, but most array-based listening systems are designed to isolate a single sound source from a mixture. This work considers a source-remixing filter that alters the relative level of each source independently. Remixing rather than separating sounds can help to improve perceptual transparency: it causes less distortion to the signal spectrum and especially to the interaural cues that humans use to localize sounds in space.

We present an open-access dataset of over 8000 acoustic impulse from 160 microphones spread across the body and affixed to wearable accessories. The data can be used to evaluate audio capture and array processing systems using wearable devices such as hearing aids, headphones, eyeglasses, jewelry, and clothing. We analyze the acoustic transfer functions of different parts of the body, measure the effects of clothing worn over microphones, compare measurements from a live human subject to those from a mannequin, and simulate the noise-reduction performance of several beamformers. The results suggest that arrays of microphones spread across the body are more effective than those confined to a single device.

Computational units implemented on nanoscale physical substrates are susceptible to errors that can be catastrophic if not mitigated. Statistical error compensation techniques have become prevalent to safeguard computational units against such hardware-failures. Algorithmic Noise Tolerance (ANT) is one such technique that utilizes a low-fidelity replica unit to detect and bypass such failures occurring within the primary (main) computational unit. Connections between ANT and the binary hypothesis testing as well as the information theoretic CEO problem have been explored for sub-exponential error profiles, quadratic and logarithmic distortion functions. However, there exist fundamental performance limits of ANT approach even without such model-dependent restrictions. The purpose of this paper is to explore fidelity-dependent conditions that are universal over the statistical properties of the computational units under which, the overall performance of ANT is arbitrarily close to the fundamental limits.

This paper presents a 10-b statistical ADC (S-ADC), achieving higher resolution (INL) than any previously reported S-ADC. This resolution requires a large number of statistical observations via comparators (12 k) with offset variation, making code estimation a key challenge. The efficiency of estimation is enhanced by a coarse frontend estimator, employing pipelining and sub-ranging to arrive at a reduced range, which is then provided to a fine backend estimator. The total computations are reduced by 19×, compared to single-stage estimation over the entire analog range. Implemented in a 32 nm process, the S-ADC achieves INLRMS. Designed to run at 20 MHz, excess supply impedance limits comparator speed to 2 MHz. The energy per 10-b conversion for the comparator array (at 2 MHz) is 744 pJ and the energy per 10-b conversion of the digital estimator (at 20 MHz) is 627 pJ.

A performance bound on low-pass reconstruction of a finite energy, band-limited signal from its corresponding pulse width modulated (PWM) signal is given. A finite dimensional input signal structure is proposed and its characteristics such as ℒ∞norm and convergence rate in the tail regions are investigated. The criteria on sampling rate and reference signal structure for lossless PWM generation are specified. With uniform oversampling, different PWM structures are constructed using a generator consisting of an ideal sampler and a comparator. An equivalent model for PWM generation and low-pass reconstruction is proposed in order to separate infinite energy components in the modulated signal from the finite energy information bearing components. Using the equivalent model, bounds on distortion energies due to low-pass reconstruction and the corresponding signal to distortion ratios are given. Characteristics of low-pass reconstruction from different PWM signals such as output shifts, blurring effects and distortion attenuations are discussed.

Analog to digital conversion is often a critical component of a digital communication link. However, the designs of typical architectures for analog to digital converters (ADCs) are focused primarily on signal reconstruction rather than gathering information for the reliable detection of symbols sent through a channel. Therefore, we consider new architectures for statistics gathering converters (SGCs), and demonstrate that these architectures achieve good communication performance while removing the artificial constraints imposed by the typical ADC design metrics. In this paper, we extend previous work on system level metrics for statistics gathering converters (SGCs). For the particular case of the delay-line based SGC, we demonstrate two important facts. First, we consider the comparison between the performance indicated by system level metrics (BER and LMMSE) with the results of a simulated communication scenario utilizing a low complexity least mean squares equalizer. Simulations demonstrate that the system level metrics are an accurate representation of the realizable communication performance of a system using the converter in question, and that such performance can be nearly achieved by the delay-line SGC using a specially designed low complexity (LMS) equalizer that takes into account the particular structure of the SGC. Second, we demonstrate that the communication performance of the delay-line SGC is robust to significant levels of process variation, which manifest in random realizations of the values of the various SGC circuit elements. Notably, this is contrary to the strict requirements on process variation imposed by traditional metrics (SNDR, SFDR, THD) on conventional analog to digital converter designs.

In this paper, we review some recent advances in the design of ADCs that exploit system-driven metrics, such as the bit-error rate in a communication link, or mutual information in a scheme employing forward error correction. We show, for example, that ADCs can be designed that maximize the information rate between the quantized output of the channel and the input to the channel for communication links with intersymbol-interference and additive noise. These ADCs dramatically outper-form (in terms of achievable information rates) traditional ADC design methods that are based on fixed uniform quantization. Architectures are also developed for ADCs such that system-metrics can be used to dynamically adapt the structure of the ADC to optimize application meaningful criteria, such as bit-error rate for communication over intersymbol interference links.

Analog-to-digital converters that maximize the information rate between the quantized channel output sequence and the channel input sequence are designed for discrete-time channels with intersymbol-interference, additive noise, and for independent and identically distributed signaling. Optimized scalar quantizers with Λ regions achieve the full information rate of log2(Λ) bits per channel use with a transmit alphabet of size Λ at infinite signal-to-noise ratio; these quantizers, however, are not necessarily uniform quantizers. Low-precision scalar and two-dimensional analog-to-digital converters are designed at finite signal-to-noise ratio, and an upper bound on the information rate is derived. Simulation results demonstrate the effectiveness of the designed quantizers over conventional quantizers. The advantage of the new quantizers is further emphasized by an example of a channel for which a slicer (with a single threshold at zero) and a carefully optimized channel input with memory fail to achieve a rate of one bit per channel use at high signal-to-noise ratio, in contrast to memoryless binary signaling and an optimized quantizer.

Tree detection techniques are often used to reduce the complexity of a posteriori probability (APP) detection in multiantenna wireless communication systems. In this paper, we introduce an efficient soft-input soft-output tree detection algorithm that employs a new type of look-ahead path metric in the process of branch pruning (or sorting). While conventional path metrics depend only on symbols on a visited path, the new path metric accounts for unvisited parts of the tree in advance through an unconstrained linear estimator and adds a bias term that reflects the contribution of as-yet undecided symbols. By applying the linear estimate-based look-ahead path metric to an -algorithm that selects the best paths for each level of the tree, we develop a new soft-input soft-output tree detector, called an improved soft-input soft-output -algorithm (ISS-MA). Based on an analysis of the probability of correct path loss, we show that the improved path metric offers substantial performance gain over the conventional path metric. We also demonstrate through simulations that the proposed ISS-MA can be a promising candidate for soft-input soft-output detection in high-dimensional systems.

In this paper, we propose a system-assisted analog mixed-signal (SAMS) design paradigm whereby the mixed-signal components of a system are designed in an application-aware manner in order to minimize power and enhance robustness in nanoscale process technologies. In a SAMS-based communication link, the digital and analog blocks from the output of the information source at the transmitter to the input of the decision device in the receiver are treated as part of the composite channel. This comprehensive systems-level view enables us to compensate for impairments of not just the physical communication channel but also the intervening circuit blocks, most notably the analog/mixed-signal blocks. This is in stark contrast to what is done today, which is to treat the analog components in the transmitter and the analog front-end at the receiver as transparent waveform preservers. The benefits of the proposed system-aware mixed-signal design approach are illustrated in the context of analog-to-digital converters (ADCs) for high-speed links. CAD challenges that arise in designing system-assisted mixed-signal circuits are also described.

We consider the sequential portfolio investment problem. Building on results in signal processing, machine learning, and other areas, we use factor graphs to develop new universal portfolio algorithms for switching strategies under transaction costs. These algorithms make use of a transition diagram in order to compactly rep resent and compute message passing on an exponentially increasing number of factor graphs. We compare this with a previous universal switching portfolios, demonstrating typically superior performance.

Current techniques used in pipelining recursive filters require significant hardware complexity. These techniques attempt to preserve the exact frequency response of the original circuit while seeking to construct a pipelined architecture. We present a technique that relaxes the need to preserve the ex act frequency response and instead considers a least-squares formulation in conjunction with the pipelined architecture. The benefit of this design is that it reduces the complexity of the pipelined circuit immensely, while enabling a simple pipelined architecture based on a polyphase decomposition of the original filter.

Analog to digital conversion is often a critical component of a digital communication link. However, the figures of merit that are used in the design of the components that comprise this step are more appropriate for signal reconstruction applications than for digital communication. This paper considers the design of time-interleaved analog-to-digital converters using deflection, or output signal-to-noise ratio, as a tractable design criterion (versus mutual information) for optimizing the phase timing parameters. This criterion is then compared with input to output mutual information, demonstrating their shared qualitative properties. It is shown that for oversampling converters under the deflection criterion, as with mutual information, the optimal sampling phases are not in general equispaced, as is conventionally assumed in converter design.

We consider the discrete-time channel with intersymbol-interference and additive noise under output analog-to-digital conversion (quantization) at the receiver. The analog-to-digital converter is optimized so as to maximize the information rate between the quantized channel output sequence and the channel input sequence, where the input sequence has independent and identically distributed symbols. An upper bound on the information rate is derived. Simulation results demonstrate the effectiveness of the designed quantizers over conventional quantizers at 1-bit/sample precision. The advantage of those quantizers is further emphasized by an example of a channel for which a simple slicer and a carefully optimized channel input with memory fail to achieve a rate of one bit per channel use at high signal-to-noise ratio, in contrast to memoryless binary signaling and an optimized quantizer.

The exponential server timing channel is known to be the simplest, and in some sense canonical, queuing timing channel. The capacity of this infinite-memory channel is known. Here, we discuss practical finite-length restrictions on the codewords and attempt to understand the maximal rate that can be achieved for a target error probability. By using Markov chain analysis, we prove a lower bound on the maximal channel coding rate achievable at blocklength n and error probability ϵ. The bound is approximated by C - n-1/2σQ (ϵ) where Q denotes the Q-function and σ2is the asymptotic variance of the underlying Markov chain. A closed form expression for σ2is given.

Turbo codes and the iterative algorithm for decoding them sparked a new era in the theory and practice of error control codes. Turbo equalization followed as a natural extension to this development, as an iterative technique for detection and decoding of data that has been both protected with forward error correction and transmitted over a channel with intersymbol interference (ISI). In this paper, we review the turbo equalization approach to coded data transmission over ISI channels, with an emphasis on the basic ideas, some of the practical details, and many of the research directions that have arisen from this offshoot, introduced by Douillard, of the original turbo decoding algorithm. The subsequent relaxation of the maximum a posteriori (MAP) equalization algorithm to include linear and other simpler receivers sparked a decade and a half of research into iterative algorithms, spanning research problems ranging from trellis coded modulation to underwater acoustic communications.

In this paper, we develop a novel statistical detection algorithm following similar principles to that of expectation maximization (EM) algorithm. Our goal is to develop an iterative algorithm for joint channel estimation and data detection in channels that have a long memory and are fast varying in time. At each iteration, starting with an estimate of the channel, we combine a Markov Chain Monte Carlo (MCMC) algorithm for data detection, and an adaptive algorithm for channel tracking, to develop a statistical search procedure that finds joint important samples of possible transmitted data and channel impulse responses. The result of this step, which may be thought as E-step of the proposed algorithm, is used in an M-step that refines the channel estimate, for the next iteration. Excellent behavior of the proposed algorithm is presented by examining it on real data from underwater acoustic communication channels.

We consider the sequential portfolio investment problem. We demonstrate that the insights of Blum and Kalai's transaction costs algorithm may be used to construct more sophisticated algorithms. In particular, we show that transaction costs can be taken into account in Cover and Ordentlich's side information portfolio and Kozat and Singer's switching portfolio. For these, we present the corresponding universal (low regret) performance bounds for each of these portfolios. We then present factor graph representations of the algorithms and demonstrate that computationally efficient algorithms may be derived from the graphs. Finally, we present results of simulations of one of the derived algorithms and compare it to other portfolios.

Linear turbo equalizers with/without channel estimation have been exploited due to their good performance with low complexity compared to a maximuma posteriori (MAP) turbo equalizer. Much work has focused on channel estimate-based minimum mean square error (MMSE) turbo equalizers. However, an MMSE turbo equalizer still requires higher complexity than an adaptive turbo equalizer such as with a normalized least mean square (NLMS) turbo equalizer. Even if adaptive turbo equalizers converge, there is often a performance loss compared to an MMSE turbo equalizer because the adaptive turbo equalizers treat soft decision data as stationary. In order to reduce this loss, we propose a new adaptive turbo equalizer that uses the soft decision data to switch among a set of K different equalizers to approximate the time varying MMSE behavior. Simulations show that the proposed switching-based NLMS turbo equalizer has better bit error rate (BER) performance than a conventional NLMS turbo equalizer by as much as 0.6dB.

This paper addresses the problem of state estimation in the case where the prior distribution of the states is not perfectly known but instead is parameterized by some unknown parameter. Thus in order to support the state estimator with prior information on the states and improve the quality of the state estimates, it is necessary to learn this unknown parameter first. Here we assume a parameterized Gaussian Markov random field to model the prior distribution of the states and propose an algorithm that is able to learn its parameters from given observations on these states. The effectiveness of this approach is proven experimentally by simulations.

In this paper, we propose a new soft-input soft-output (SISO) multi-input multi-output (MIMO) detection technique, called an improved SISO M-algorithm (ISS-MA). We modify the conventional M-algorithm to improve the performance-complexity trade-off of the SISO symbol detector. Towards this end, an improved path metric is proposed, which accounts for the information on undecided symbols at a particular path visited. The inclusion of this information is enabled through a bias term which is added to the conventional path metric in order to reflect the contributions of the undecided symbols. We derive the bias term using soft unconstrained linear estimates of undecided symbols. As a result, the ISS-MA that picks up the best M candidates based on this modified path metric exhibits improved performance/complexity trade-off compared to the existing SISO detectors. According to extensive simulations performed over i.i.d. Rayleigh fading channels, the proposed SISO detector yields significantly lower complexity than other symbol detectors while maintaining strong performance especially in high dimensional systems.

In this paper, we propose BER-optimal analog-to-digital converters (ADC) where quantization levels and thresholds are set non-uniformly to minimize the bit-error rate (BER). This is in contrast to present-day ADCs which act as transparent waveform preservers. Simulations for various communication channels show that the BER-optimal ADC achieves shaping gains that range from 2.5dB for channels with low intersymbol interference (ISI) to more than 30dB for channels with high ISI. Moreover, a 3-bit BER-optimal ADC achieves the same or even lower BER than a 4-bit uniform ADC. For flash converters, this corresponds a power reduction by 2×. Look-up table based equalizers compatible with BER-optimal ADCs are shown to reduce the power up to 47% and the area up to 66% in a 45nm CMOS process. The shaping gain due to BER-optimal ADCs can be exploited to lower peak transmit swings at the transmitter or decrease power consumption of the ADC.

We propose an improved minimum mean square error (MMSE) vertical Bell Labs layered space-time (V-BLAST) detection technique, called a soft input, soft output, and soft feedback (SIOF) V-BLAST detector, for turbo multi-input multioutput (turbo-MIMO) systems. We derive a symbol estimator by minimizing the power of the interference plus noise, given a priori probabilities of undetected layer symbols and a posteriori probabilities for past detected layer symbols. For a low-complexity implementation, an approximate SIOF algorithm is presented, which allows for a time-invariant realization of the symbol ordering and an MMSE filtering process. Another implementation, referred to as the iterative SIOF algorithm is introduced, which decides on symbol detection order based on a posteriori symbol probabilities to improve the detection performance. Simulations performed on a space-time bit-interleaved coded modulation (STBICM) architecture over quasi-static MIMO fading channels demonstrate that the SIOF V-BLAST detector provides performance gains over previous turbo-BLAST detectors, most notably when more transmit antennas are used.

In this paper, we propose a near-maximum likelihood (ML) detection method referred to as reduced dimension ML search (RD-MLS). The RD-MLS detector is based on a partitioned search method that divides the symbol space into two groups and searches over the vector space of one group instead of that comprising all of the symbols. First, a minimum mean square error (MMSE) dimension reduction operator suppressing the interference from the second group is applied, and then a list tree search (LTS) is performed over the symbols in the first group. For each lattice point of symbols for the first group found from the LTS, the rest of symbols are estimated by MMSE-decision feedback (MMSE-DF) estimation. Among these lattice point candidates, a final solution is chosen as a minimizer of the L2-norm criterion. From an asymptotic error probability analysis, we show that the dimension reduction loss is potentially compensated by the LTS gain proportional to the size of the list. Furthermore, we demonstrate through simulation on multi-input multi-output (MIMO) transmissions that the RD-MLS detector achieves substantial complexity reduction with relatively little performance loss over ML detection.

In the area of combination of adaptive filters, two main approaches, namely convex and affine combinations have been introduced. In this article, the relation between these two approaches is investigated. First, the problem of obtaining optimal convex combination coefficients is formulated as the projection of the optimal affine combination weights to the unit simplex in a weighted inner product space. Based on this formulation the closed form expressions for optimal combination weights and target MSE levels are obtained for two and three branch cases.

In this paper, we explore the use of a particular multistage adaptation algorithm for a variety of adaptive filtering applications where the structure of the underlying process to be estimated is unknown. The proposed algorithm uses a performance-weighted mixture of LMS filters of various orders to construct its final output. The algorithm is analyzed in a stochastic context with respect to its convergence and mean-square error (MSE) behaviors and is shown to achieve the best MSE performance of the constituent algorithms in the mixture. Through simulations, it has been observed that the mixture structure can offer considerable performance improvement for both stationary and time varying observation sequences.

In this paper, an improved minimum mean square error (MMSE) soft feedback detector, called the soft input, soft output, and soft feedback (SIOF) symbol detector, is proposed for turbo multi-input multi-output (TURBO-MIMO) systems. The SIOF symbol detector is derived by minimizing the power of interference plus noise, given a priori probabilities of yet undetected layers and a posteriori probabilities of detected layers. As a result, soft feedback interference cancellation based on a posteriori information is derived, yielding symbol detection robust to error propagation effects. Furthermore, a low complexity implementation using approximate detection ordering and linear filtering is introduced. Simulations performed for block fading channels show that the SIOF symbol detector exhibits performance gains over the existing TURBO-BLAST algorithm [3].

In this paper, we consider online (sequential) portfolio selection in a competitive algorithm framework under transaction costs. We construct a sequential algorithm for portfolio selection that asymptotically achieves the wealth of the best piecewise constant rebalanced portfolio tuned to the underlying individual sequence of price relative vectors where we pay a fixed percent commission for each transaction. Without knowledge of the investment duration, the algorithm can perform as well as the best investment algorithm that can choose both the partitioning of the sequence of the price relative vectors as well as the best constant rebalanced portfolio within each segment based on knowledge of the sequence of price relative vectors in advance. We use a transition diagram similar to that in [1] to compete with an exponential number of switching investment strategies, using only linear complexity in the data length for combination.

In this paper, we consider the sequential portfolio investment problem considered by Cover [3] and extend the results of [3] to the class of piecewise constant rebalanced portfolios that are tuned to the underlying sequence of price relatives. Here, the piecewise constant models are used to partition the space of past price relative vectors where we assign a different constant rebalanced portfolio to each region independently. We then extend these results where we compete against a doubly exponential number of piecewise constant portfolios that are represented by a context tree. We use the context tree to achieve the wealth of a portfolio selection algorithm that can choose both its partitioning of the space of the past price relatives and its constant rebalanced portfolio within each region of the partition, based on observing the entire sequence of price relatives in advance, uniformly, for every bounded deterministic sequence of price relative vectors. This performance is achieved with a portfolio algorithm whose complexity is only linear in the depth of the context tree per investment period. We demonstrate that the resulting portfolio algorithm achieves significant gains on historical stock pairs over the algorithm of [3] and the best constant rebalanced portfolio.

In this paper, we study moments of soft bits of binary-input symmetric-output channels and solve some extremal problems of the moments. We use these results to solve the extremal information combining problem. Further, we extend the information combining problem by adding a constraint on the second moment of soft bits, and find the extremal distributions for this new problem. The results for this extension problem are used to improve the prediction of convergence of the belief propagation decoding of low-density parity-check (LDPC) codes, provided that another extremal problem related to the variable nodes is solved.

Level-crossing A/D converters (LCA/D) have been considered in the literature and have been shown to efficiently sample certain classes of signals. In this paper we provide a stable algorithm to perfectly reconstruct signals of finite rate of innovation using level-crossing samples. Furthermore, we also apply level-crossing sampling to detection of event-arrival signals.

In this paper, we consider online (sequential) portfolio selection in a competitive algorithm framework. We construct a sequential algorithm for portfolio investment that asymptotically achieves the wealth of the best piecewise constant rebalanced portfolio tuned to the underlying individual sequence of price relative vectors. Without knowledge of the investment duration, the algorithm can perform as well as the best investment algorithm that can choose both the partitioning of the sequence of the price relative vectors as well as the best constant rebalanced portfolio within each segment based on knowledge of the sequence of price relative vectors in advance. We use a transition diagram similar to that in F.M.J. Willems, (1996) to compete with an exponential number of switching investment strategies, using only linear complexity in the data length for combination. The regret with respect to the best piecewise constant strategy is at most O(ln(n)) in the exponent, where n is the investment duration. This method is also extended in S.S. Kozat and A.C. Singer, (2006) to switching among a finite collection of candidate algorithms, including the case where such transitions are represented by an arbitrary side-information sequence.

We consider universal piecewise linear regression of real valued bounded sequences under the squared loss function. In this setting, we present a lower bound on the regret of a universal sequential piecewise linear regressor compared to the best piecewise linear regressor that has access to the entire sequence in advance. This lower bound is tight in that it achieves the corresponding upper bound, suggesting a minmax optimality of the sequential regressor, for every individual bounded sequence.

In this letter, pilot design and channel estimation are discussed for orthogonal frequency-division multiplexing (OFDM) systems with guard subcarriers. First, we investigate the effects of guard band on channel estimation errors. From this, we propose pilot placement having a maximum distance between adjacent pilots except for the guard band, and show that it achieves minimum channel estimation errors among partially equispaced pilots using equivalence of the Toeplitz and circulant matrices. Also, an efficient channel estimator is developed by introducing an extended channel and its finite impulse response (FIR) approximation to overcome high numerical complexity caused by the presence of guard subcarriers and the use of a large number of subcarriers. Simulation results are presented for OFDM and orthogonal frequency division multiple access (OFDMA) systems consistent with IEEE 802.16a standards.

In this correspondence, blind channel estimators exploiting finite alphabet constraints are discussed for orthogonal frequency-division multiplexing (OFDM) systems. Considering the channel and data jointly, a joint maximum-likelihood (JML) algorithm is described, along with identifiability conditions in the noise-free case. This approach enables development of general identifiability conditions for the minimum-distance (MD) finite alphabet blind algorithm of Zhou and Giannakis. Both the JML and MD algorithms suffer from high numerical complexity, as they rely on exhaustive search methods to resolve a large number of ambiguities. We present a substantially more efficient blind algorithm, the reduced complexity minimum distance (RMD) algorithm, by exploiting properties of the assumed finite-length impulse response (FIR) channel. The RMD algorithm exploits constraints on the unwrapped phase of FIR systems and results in significant reductions in numerical complexity over existing methods. In many cases, the RMD approach is able to completely eliminate the exhaustive search of the JML and MD approaches, while providing channel estimates of the same quality.

In this paper, we present an adaptive FIR equalizer which reduces power dissipation by employing a new algorithmic error correction technique. Building on the voltage over-scaling (VOS) technique, we formulate the statistical estimation of timing errors that may be caused by VOS, called soft errors to detect and cancel them at a system level. We derive a minimum variance unbiased estimator, and develop an adaptive and power-optimized algorithm for an adaptive equalizer. Up to 30% power savings are demonstrated with negligible performance loss for an example, 16-tap minimum mean square error (MMSE) FIR equalizer.

We propose a level-crossing A/D (LCA/D) converter which can be modelled with an oversampling A/D followed by a low resolution quantizer. In this paper we will study the reconstruction of non-bandlimited inputs processed by such a system and compare its performance to uniform sampling

Conditional asymptotic multi-user efficiency is introduced as a quantitative measure for comparing the performance of multi-user detectors that employ successive interference cancellation (SIC). For a given ordering of user signals, we derive the detector that achieves the maximum asymptotic conditional efficiency for each user among all possible SIC detectors. The optimal ordering that maximizes the asymptotic conditional efficiency at each stage of successive detection is also derived. We extend the concept of maximal asymptotic conditional efficiency detection to the case of joint successive interference cancellation (JSIC), where at each stage of successive detection, the corresponding bit is detected taking into account the interference of the "closest", or nearest, interferer in an ordered set of users. Both detection algorithms proposed are robust against strong correlation of user signals, e.g., in a multi-user system where the user signals are linearly dependent. Simulation results demonstrate that the maximum conditional efficiency approach significantly improves detector performance, particularly at high SNR

An order recursive algorithm for minimum mean square error (MMSE) estimation of signals under a Bayesian model defined on the steering vector is introduced. The MMSE estimate can be viewed as a mixture of conditional MMSE estimates weighted by the posterior probability density function (PDF) of the random steering vector given the observed data. This paper derives an adaptive closed form Kalman-filter implementation that updates the weight vector by successive incorporations of data collected from additional array elements in the steering vector. The performance of the Bayesian beamformer is compared against several robust beamformers in terms of mean square error (MSE) and output signal-to-interference-plus-noise ratio (SINR).

We propose a novel scheme for detecting coded data transmitted over a communication channel that is either partially or entirely unknown. Viewing the unknown channel parameters as stochastic quantities drawn from a known probability distribution, the likelihood of a sequence of data is derived using Bayesian techniques. A stack-like tree search algorithm is proposed for implementation of maximum likelihood (ML) sequence detection under the Bayesian metric. We apply the Bayesian scheme to the binary symmetric channel (BSC) with unknown crossover probability. The structure of the resulting metric is compared to both the conventional Fano metric and a universal metric presented in (Lapidoth and Ziv, IEEE Trans. IT 1999). Based on its relationship to the metric developed by Lapidoth and Ziv, the newly-derived metric is shown to be pairwise universal over the ensemble of random uniform codes

We investigate the problem of sequential prediction of individual sequences using a competitive algorithm approach. We have previously developed prediction algorithms that are universal with respect to the class of all linear predictors, such that the prediction algorithm competes against a continuous class of prediction algorithms, under the square error loss. In this paper, we introduce the use of a "context tree," to compete against a doubly exponential number of piecewise linear models. We use the context tree to achieve the performance of the best piecewise linear model that can choose its partition of the real line and real-valued prediction parameters, based on observing the entire sequence in advance, for the square error loss, uniformly, for any individual sequence. This performance is achieved with a prediction algorithm whose complexity is only linear in the depth of the context tree

We present a maximum likelihood-based error correction (ML-EC) technique which achieves significant power savings in digital filtering. Although voltage over-scaling (VOS) can achieve high energy efficiency, it can introduce "soft errors" which severely degrade the performance of the filter. The proposed scheme detects, estimates and corrects these soft errors via an ML-based algorithm that achieves up to 47% power savings without any SNR loss and up to 60% power savings with a 1.5 dB SNR loss for an example case study of a frequency-selective low-pass filter.

In this paper we study moments of soft-bits of binary-input symmetric-output channels and solve some extremal problems of the moments. We use these results to solve the extremal information combining problem. Further, we extend the information combining problem by adding a constraint on the second moment of soft-bits, and find the extreme distributions for this new problem

The bidirectional arbitrated decision-feedback equalizer (BAD), which has bit-error rate performance between a decision-feedback equalizer (DFE) and maximum a posteriori (MAP) detection, is presented. The computational complexity of the BAD algorithm is linear in the channel length, which is the same as that of the DFE, and significantly lower than the exponential complexity of the MAP detector. While the relative performance of BAD to those of the DFE and the MAP detector depends on the specific channel model, for an error probability of 10/sup -2/, the performance of BAD is typically 1-2 dB better than that of the DFE, and within 1 dB of the performance of MAP detection.

Iterative decoders such as turbo decoders have become integral components of modern broadband communication systems because of their ability to provide substantial coding gains. A key computational kernel in iterative decoders is the maximum a posteriori probability (MAP) decoder. The MAP decoder is recursive and complex, which makes high-speed implementations extremely difficult to realize. In this paper, we present block-interleaved pipelining (BIP) as a new high-throughput technique for MAP decoders. An area-efficient symbol-based BIP MAP decoder architecture is proposed by combining BIP with the well-known look-ahead computation. These architectures are compared with conventional parallel architectures in terms of speed-up, memory and logic complexity, and area. Compared to the parallel architecture, the BIP architecture provides the same speed-up with a reduction in logic complexity by a factor of M, where M is the level of parallelism. The symbol-based architecture provides a speed-up in the range from 1 to 2 with a logic complexity that grows exponentially with M and a state metric storage requirement that is reduced by a factor of M as compared to a parallel architecture. The symbol-based BIP architecture provides speed-up in the range M to 2M with an exponentially higher logic complexity and a reduced memory complexity compared to a parallel architecture. These high-throughput architectures are synthesized in a 2.5-V 0.25-/spl mu/m CMOS standard cell library and post-layout simulations are conducted. For turbo decoder applications, we find that the BIP architecture provides a throughput gain of 1.96 at the cost of 63% area overhead. For turbo equalizer applications, the symbol-based BIP architecture enables us to achieve a throughput gain of 1.79 with an area savings of 25%.

A multi-user detector with scalable complexity that achieves the maximum likelihood (ML) solution for two users and gives good sub-optimal performance for a higher number of users is proposed. The key idea is to construct a lookup table based on the geometric structure of the signal constellation, and then perform fast decoding based on the lookup table. The proposed detector is near-far resistant and its performance is consistently better than existing sub-optimal detectors when the number of users is greater than the number of dimensions. The robustness of the detector against noise can be controlled at the expense of higher complexity.

We consider the problem of sequential prediction of arbitrary real-valued sequences with side information. We first construct a universal algorithm that asymptotically achieves the performance of the best side-information dependent constant predictor uniformly for all data and side-information sequences. We then extend these results to linear predictors of some fixed order. We derive matching upper and lower bounds, and show that the algorithms are not only universal but they are also optimal such that no sequential algorithm can give better performance for all sequences.

We present an analysis of the performance of Bayesian beamformers that are able to estimate signals from unknown source directions by balancing multiple optimal estimates according to the a posteriori probability mass function (PMF). We show that the conditional mean square error (MSE) of the Bayesian beamformer asymptotically achieves the conditional MSE of an estimator that has prior knowledge of the true direction of arrival. The convergence rate depends on both the signal-to-noise ratio (SNR) and the Kullback Leibler distance between certain probability distributions on which the Bayesian model is defined.

Turbo equalization using linear filters for data detection has been shown to perform nearly as well as those based on the original maximum a posteriori probability (MAP) detection approach. Such linear equalization methods have taken on many forms in the literature, from simple least-mean-square (LMS)-based adaptive filtering approaches, to minimum mean square error (MMSE)-based methods that are recursively computed for each output symbol for each iteration. In this paper, we consider a class of turbo equalization algorithms in which complexity requirements dictate that a fixed set of filter coefficients must be used for all symbols and for all iterations. By computing one such set of coefficients via the LMS algorithm assuming unreliable soft information, and another set assuming highly reliable soft information, we show that a switching strategy can be employed, nearly achieving the performance of recomputing the coefficients at each iteration.

We propose an equalization algorithm that employs multiple decision-feedback equalizers (DFE)s operating in different directions and arbitration among the outputs of these equalizers to mitigate the effects of two-dimensional intersymbol interference (ISI). The multi-directional arbitrated DFE (MAD) exploits directional diversity to reduce the effects of error-propagation while maintaining complexity on the same order as a DFE. Simulation results show that, when four DFEs are used, the MAD algorithm can achieve substantial gains over a single DFE, including gains of over 10 dB at 10/sup -2/ BER for simulations in this paper.

This paper apply the factor graph framework to the techniques of linear equalization and decision feedback equalization to obtain a new class of low complexity equalization algorithms. The estimation of Gaussian processes has been studied in previous work, and the application of factor graphs to this problem is a recent extension. Here it uses a factor graph model for the specific estimation problem of equalization and use the sum-product algorithm to obtain the desired estimate. The reduced complexity message passing update equations are derived and detail the complexity of the resulting algorithms.

The problem of sequential prediction of real-valued sequences using piece-wise linear models under the square-error loss function is presented in this paper. In this context, we demonstrate a sequential algorithm for prediction whose accumulated squared error for every bounded sequence is asymptotically as small as that of the best fixed predictor for that sequence taken from the class of piecewise linear predictors. We also show that this predictor is optimal in certain settings in a particular min-max sense. This approach can also be applied to the class of piecewise constant predictors, for which a similar universal sequential algorithm can be derived with corresponding min-max optimality.

We propose a method for the analysis of linear turbo equalization based on extrinsic information transfer (EXIT) charts. Given channel knowledge, and therefore the optimum linear equalizer coefficients, the evolution of soft information of the soft-input soft-output (SISO) equalizer can be estimated by computing bit error rates (BER) analytically. Compared to conventional analysis methods, the proposed method predicts the linear turbo equalizer performance without running extensive simulations to obtain the SISO equalizer EXIT charts. Using an empirically generated SISO decoder EXIT chart, convergence analysis can be undertaken. Further, the method provides a bound on the achievable BER for given channels and an estimate of equalizer complexity. These approximate analyses are validated via computer simulations.

Presented in this paper is a low-power architecture for turbo decodings of parallel concatenated convolutional codes. The proposed architecture is derived via the concept of block-interleaved computation followed by folding, retiming and voltage scaling. Block-interleaved computation can be applied to any data processing unit that operates on data blocks and satisfies the following three properties: 1.) computation between blocks are independent, 2.) a block can be segmented into computationally independent sub-blocks, and 3.) computation within a sub-block is recursive. The application of block-interleaved computation, folding and retiming reduces the critical path delay in the add-compare-select (ACS) kernel of MAP decoders by 50% - 84% with an area overhead of 14% - 70%. Subsequent application of voltage scaling results in up to 65% savings in power for block-interleaving depth of 6. Experimental results obtained by transistor-level timing and power analysis tools demonstrate power savings of 20% - 44% for a block-interleaving depth of 2 in 0.25μm CMOS process.

We propose a method for exploiting transmit diversity using parallel independent intersymbol interference channels together with an iterative equalizing receiver. Linear iterative turbo equalization (LITE) employs an interleaver in the transmitter and passes a priori information on the transmitted symbols between multiple soft-input/soft-output minimum mean-square error linear equalizers in the receiver. We describe the LITE algorithm, present simulations for both stationary and fading channels, and develop a framework for analyzing the evolution of the a priori information as the algorithm iterates.

We study the separability of demodulation and decoding for communications over multiple-antenna block-fading channels when bit-linear linear dispersion (BL-LD) codes are used. We assume the channel is known to the receiver only, and find necessary and sufficient conditions on the dispersion matrices for the separation of demodulation and decoding at the receiver without loss of optimality.

In this paper, we investigate some of the stochastic properties of two recently introduced multistage adaptive filtering algorithms, namely the LMS-Bayesian and the RLS-Bayesian algorithms. We study probability-1 convergence of these algorithms and derive their final mean squared error for stationary Gaussian time series. We will show that under some general independence assumptions, both algorithms are convergent in a probability-1 sense and achieve the performance of the best algorithm used in the mixture.

We consider the problem of joint equalization and decoding, using the method of turbo equalization originally developed by Douillard, et al. [3]. In its original form, turbo-equalization requires accurate knowledge of the channel at the receiver. We propose a receiver structure, based on a soft-input Kalman channel estimator, that can operate effectively without accurate channel knowledge and without training data. The resulting joint channel and data estimator is shown to outperform standard turbo equalization based on moderate-length training data.

We study the turbo equalization approach to coded data transmission over channels with intersymbol interference. In the original system invented by Douillard et al. (1995), the data are protected by a convolutional code and the receiver consists of two trellis-based detectors, one for the channel (the equalizer) and one for the code (the decoder). It has been shown that iterating equalization and decoding tasks can yield tremendous improvements in bit error rate. We introduce new approaches to combining equalization based on linear filtering, with decoding.. Through simulation and analytical results, we show that the performance of the new approaches is similar to the trellis-based receiver, while providing large savings in computational complexity. Moreover, this paper provides an overview of the design alternatives for turbo equalization with given system parameters, such as the channel response or the signal-to-noise ratio.

We consider the problem of sequential linear prediction of real-valued sequences under the square-error loss function. For this problem, a prediction algorithm has been demonstrated whose accumulated squared prediction error, for every bounded sequence, is asymptotically as small as the best fixed linear predictor for that sequence, taken from the class of all linear predictors of a given order p. The redundancy, or excess prediction error above that of the best predictor for that sequence, is upper-bounded by A/sup 2/P ln(n)/n, where n is the data length and the sequence is assumed to be bounded by some A. We provide an alternative proof of this result by connecting it with universal probability assignment. We then show that this predictor is optimal in a min-max sense, by deriving a corresponding lower bound, such that no sequential predictor can ever do better than a redundancy of A/sup 2/p ln(n)/n.

Detection and localization of underwater mines remains a challenging and important problem for safe operation of naval platforms. A number of new technologies exploit airborne LIDARs, which can penetrate the air-water interface and optically detect and localize underwater mines. Such systems process the received optical field generated by scattering within the water column, and have proven to be an effective technology for mine detection and localization. We consider the use of multiple looks at a single target to form a three-dimensional representation of the scatterers within the water column. To form such images, we account for the integration within the receive sensors, and formulate the problem in a tomographic framework. We present preliminary image formation results generated from data collected at sea with a state-of-the-art navy mine imaging system.

We develop an automated algorithm for determining the number and sparsely supported locations of coefficients in a multi-element array decision-feedback equalizer based on an estimated channel response. We aim for robustness to a wide variety of possible channel conditions, especially through taking advantage of the interplay between the MMSE-optimal feedforward and feedback filters.

We investigate the redundancy that arises from adding a worst case length constraint to uniquely decodable fixed-to-variable codes over achievable Huffman (1952) codes. This is in contrast to the traditional metric of the redundancy over the entropy. We show that the cost for adding constraints on the worst case coding length is small, and that the resulting bound is related to the Fibonacci numbers.

In this paper, we derive some of the stochastic properties of a universal linear predictor, through analyses similar to those generally made in the adaptive signal processing literature. A. C. Singer et al. (see IEEE Trans. Signal Proc., vol.47, no.10, p.2685-2700, Oct. 1999) introduced a predictor whose sequentially accumulated mean squared error for any bounded individual sequence was shown to be as small as that for any linear predictor of order less than some maximum order m. For stationary Gaussian time series, we generalize these results, and remove the boundedness restriction. In this paper we show that the learning curve of this universal linear predictor is dominated by the learning curve of the best order predictor used in the algorithm.

The relationship between prediction and data compression can be extended to universal prediction schemes and universal data compression. Previous work shows that minimizing the sequential squared prediction error for individual sequences can be achieved using the same strategies which minimize the sequential code length for data compression of individual sequences. Defining a "probability" as an exponential function of sequential loss, results from universal data compression can be used to develop universal linear prediction algorithms. Specifically, we present an algorithm for linear prediction of individual sequences which is twice-universal, over parameters and model orders.

A low complexity approach to coding-enhanced multi-user detection is developed to mitigate the problems associated with the near-far effect and to permit a more efficient assignment of channel resources relative to current multiple access (MA) communications systems. Through prudent integration of error correction decoding, multi-user and inter-symbol interference equalization and stripping, a low complexity near-far resistant multi-user joint detector/decoder has been developed which exhibits significant performance gains relative to the best known low complexity joint detection/decoding procedures reported in literature. Empirical analysis of the coding-enhanced multi-user detector (CMD) for a case of heavy intersymbol interference and multi-user interference shows a 3 dB improvement over these best known methods.

Soliton solutions to nonlinear wave equations have been recently proposed as signaling waveforms in a variety of communication contexts. One such system modulates the relative positions or amplitudes of multiple solitons generated by a nonlinear ladder circuit. At the receiver, there are inherent difficulties in the problems of parameter estimation and detection of soliton signals due to the nonlinear coupling imposed by the soliton dynamics. We demonstrate that the ladder circuit can act as a tuned receiver for the component solitons, naturally decoupling them so that the detection and estimation problems can be solved with standard techniques. We develop robust and asymptotically efficient algorithms for maximum likelihood parameter estimation and present a technique for generalized likelihood ratio test detection.

Solitons and the nonlinear evolution equations that support them arise in the description of a wide range of nonlinear physical phenomena including shallow water waves, piezoelectrics, and optical transmission in nonlinear fibers. Although such systems are nonlinear, they are exactly solvable and possess a class of remarkably robust solutions, known as solitons, which satisfy a nonlinear form of superposition. By exploiting the properties of solitons, such nonlinear systems may be attractive for a variety of signal processing problems including multiple access communications, private or low power transmission, and multiresolution transmission. We outline a number of modulation techniques using solitons, and explore some of the properties of such systems in the presence of additive channel corruption. We also discuss the use of a nonlinear LC network (transmission line model) and its soliton solutions for signal synthesis in a variety of modulation techniques.

The problem of modeling chaotic nonlinear dynamical systems using hidden Markov models is considered. A hidden Markov model for a class of chaotic systems is developed from noise-free observations of the output of that system. A combination of vector quantization and the Baum-Welch algorithm is used for training. The importance of this combined iterative approach is demonstrated. The model is then used for signal separation and signal detection problems. The difference between maximum likelihood signal estimation and maximum a posteriori signal estimation using a hidden Markov model is illustrated for a nonlinear dynamical system.>

A nonlinear generalization of the family of autoregressive signal models is introduced. This generalization can be viewed as an autoregressive model with state-varying parameters. For such signals, minimum mean-square error prediction can be reformulated as an interpolation problem. A novel interpretation of the signal as a codebook for its own prediction leads to an interpolation strategy resembling a predictive counterpart to vector quantization. The applicability of this model is then demonstrated empirically for a variety of signals.>