We present methods for semi-supervised learning (SSL) from few pilots over nonlinear channels using variational autoencoders. These channels, which are unknown at the receiver, may have finite memory (intersymbol interference). The loss function we use for SSL incorporates both the labeled (pilot) symbols and unlabeled (payload) symbols. We demonstrate a very significant reduction in the number of pilot symbols required for reliable inference over the channel when applying SSL to train a variational autoencoder, compared to standard supervised learning of a neural network decoder using only pilot data information.

CRC-aided belief propagation list (CBPL) is a low latency, high throughput decoder for polar codes. In this work, it is shown that CBPL decoding of polar codes over the additive white Gaussian noise channel can be substantially improved using ordered statistics post-processing that only requires a very low reprocessing order (e.g., order one). We present efficient implementations of the ordered statistics post-processing with a trade-off between computational complexity and error rate.

A new algorithm for efficient exact maximum likelihood decoding of polar codes (which may be CRC augmented), transmitted over the binary erasure channel, is presented. The algorithm applies a matrix triangulation process on a sparse polar code parity check matrix, followed by solving a small size linear system over GF(2). To implement the matrix triangulation, we apply belief propagation decoding type operations. We also indicate how this decoder can be implemented in parallel for low latency decoding. Numerical simulations are used to evaluate the performance and computational complexity of the new algorithm.

We propose a successive cancellation list (SCL) encoding and decoding scheme for the Gelfand Pinsker (GP) problem based on the known nested polar coding scheme. It applies SCL encoding for the source coding part, and SCL decoding with a properly defined CRC for the channel coding part. The scheme shows improved performance compared to the existing method. A known issue with nested polar codes for binary dirty paper is the existence of frozen channel code bits that are not frozen in the source code. These bits need to be retransmitted in a second phase of the scheme, thus reducing the rate and increasing the required blocklength. We provide an improved bound on the size of this set, and on its scaling with respect to the blocklength, when the Bhattacharyya parameter of the test channel used for source coding is sufficiently large, or the Bhattacharyya parameter of the channel seen at the decoder is sufficiently small. The result is formulated for an arbitrary binary-input memoryless GP problem, since unlike the previous results, it does not require degradedness of the two channels mentioned above. Finally, we present simulation results for binary dirty paper and noisy write once memory codes.

The problem of communicating over an additive white Gaussian noise channel with feedback, using low precision arithmetic, is considered. The Schalkwijk-Kailath (SK) scheme is known to achieve an error probability that decays double exponentially in the number of interaction rounds, for any rate below channel capacity. However, SK is also known to suffer from numerical issues. In this work we propose a new, modified scheme termed Zoom-in SK (ZSK), which breaks the SK protocol into several stages. Each stage comprises several SK iterations followed by a synchronized zoom step. The zoom-in allows the receiver and transmitter to keep the scheme's parameters relatively large such that low precision arithmetic can be used. We prove that the new scheme achieves approximately the same error probability as SK while not suffering from numerical issues. We further verify our results in simulation and compare ZSK to the original SK scheme.

The problem of communication over binary dirty paper (DP) using nested polar codes is considered. An improved scheme, focusing on low delay, short to moderate blocklength communication is proposed. Successive cancellation list (SCL) decoding with properly defined CRC is used for channel coding, and SCL encoding without CRC is used for source coding. The performance is compared to the best achievable rate of any coding scheme for binary DP using nested codes. A well known problem with nested polar codes for binary DP is the existence of frozen channel code bits that are not frozen in the source code. These bits need to be retransmitted in a second phase of the scheme, thus reducing transmission rate. We observe that the number of these bits is typically either zero or a small number, and provide an improved analysis, compared to that presented in the literature, on the size of this set and on its scaling with respect to the blocklength when the power constraint parameter is sufficiently large or the channel crossover probability sufficiently small.

The polarization process of polar codes over a prime q-ary alphabet is studied. Recently, it has been shown that the blocklength of polar codes with prime alphabet size scales polynomially with respect to the inverse of the gap between code rate and channel capacity. However, except for the binary case, the degree of the polynomial in the bound is extremely large. In this paper, a different approach to computing the degree of this polynomial for any prime alphabet size is shown. This approach yields a lower degree polynomial for various values of the alphabet size that were examined. It is also shown that even lower degree polynomial can be computed with an additional numerical effort.

A concatenated coding scheme over binary memoryless symmetric (BMS) channels using a polarization transformation followed by outer sub-codes is analyzed. Achievable error exponents and upper bounds on the error rate are derived. The first bound is obtained using outer codes which are typical random linear codes. As a byproduct of this bound, it determines the rates of the outer codes. A lower bound on the error exponent that holds for all BMS channels with a given capacity is then derived. Improved bounds and approximations for finite blocklength codes using channel dispersions (normal approximation), as well as converse and approximate converse results, are also obtained. The bounds are compared with actual simulation results from the literature. For the cases considered, when transmitting over the binary input additive white Gaussian noise channel, there was only a small gap between the channel dispersion-based approximation and the actual error rate of concatenated BCH-polar codes.

We consider low-density parity-check (LDPC) code ensembles over non-binary Galois fields when used for transmission over arbitrary discrete memoryless channels. Belief propagation decoding for these codes has been shown to achieve excellent results. However, computing the decoding threshold using density evolution is usually impractical, since one needs to propagate multi-dimensional probability distributions, and Monte Carlo simulations are required instead. By considering the evolution of the message Bhattacharyya parameter and the message expected value parameter, we derive a simple lower bound on the performance of the algorithm. This bound applies for both regular and irregular non-binary LDPC ensembles.

The problem of reliable capacity achieving transmission over asymmetric side-information channels is considered. A new simple and general method is proposed that can be used to convert this problem to the problem of transmission over symmetric side-information channels which is simpler to implement. In particular, the method can be used to achieve the capacity of side-information channels using polar codes. For the degenerated case where there is no side information at the transmitter (i.e., a plain communication channel) the method yields a new simple scheme for transmission over plain asymmetric channels.

The polarization process of polar codes over a ternary alphabet is studied. Recently it has been shown that the scaling of the blocklength of polar codes with prime alphabet size scales polynomially with respect to the inverse of the gap between code rate and channel capacity. However, except for the binary case, the degree of the polynomial in the bound is extremely large. In this work, it is shown that a much lower degree polynomial can be computed numerically for the ternary case. Similar results are conjectured for the general case of prime alphabet size.

Polar code-based source coding is considered for some given code rate and some desired distortion level. The distortion level of a typical quantized source vector is required to be below the desired distortion level. A sufficient polynomial scaling law of the blocklength with respect to the gap between the desired distortion and the distortion-rate function is derived. The results are then used to obtain a polynomial scaling of the blocklength with respect to the gap to capacity for the polar code-based solution of the binary dirty paper problem and for polar write-once memory codes.

A concatenated coding scheme, recently proposed by Mahdavifar et al., is considered. The scheme uses polar codes as inner codes and maximum distance separable codes, such as Reed-Solomon codes, as outer codes. It was shown by Mahdavifar et al. that the concatenated coding scheme has a significantly better asymptotic error decay rate compared to Arikan's polar codes. However, the scaling of the required blocklength with respect to the gap between the code rate and the channel symmetric capacity was not considered. Following the analysis of the scaling problem for Arikan's polar codes by Guruswami and Xia, it is shown that the scaling of blocklength in the concatenated scheme is still inverse polynomial with the gap to the symmetric capacity. It is also shown that improved bounds can be derived for the concatenated scheme, compared to plain polar codes, both for the asymptotic error decay and for the scaling of the blocklength with respect to the gap to the symmetric capacity. An improved result for the error burst length that can be corrected is also derived for the concatenated coding scheme.

Improved upper bounds on the blocklength required to communicate over binary-input channels using polar codes, below some given error probability, are derived. For that purpose, an improved bound on the number of non-polarizing channels is obtained. The main result is that the blocklength required to communicate reliably scales at most as O((I(W ) - R)-5.702), where R is the code rate and I(W ) is the symmetric capacity of the channel W. The results are then extended to polar lossy source coding at rate R of a source with symmetric distortion-rate function D(·). The blocklength required scales at most as O((D0)-5.702), where D0is the maximal allowed gap between the actual average (or typical) distortion and D(R).

A coding scheme for write once memory (WOM) using polar codes is presented. It is shown that the scheme achieves the capacity region of noiseless WOMs when an arbitrary number of multiple writes is permitted. The encoding and decoding complexities scale as O(N log N), where N is the blocklength. For N sufficiently large, the error probability decreases subexponentially in N. The results can be generalized from binary to generalized WOMs, described by an arbitrary directed acyclic graph, using nonbinary polar codes. In the derivation, we also obtain results on the typical distortion of polar codes for lossy source coding. Some simulation results with finite length codes are presented.

The confidence in the reliability of a codeword output by some (not necessarily optimal) decoding algorithm is discussed. A new property which relies on the linear programming (LP) decoder, the approximate maximum-likelihood certificate (AMLC), is introduced to address this issue as follows. First, the channel output vector is decoded by some symmetric decoder D, e.g., belief propagation or min-sum algorithm decoding. Second, the channel output vector is decoded by LP decoding. Third, if the decoding result of D is a codeword, its LP value is compared to the LP value of the LP decoding result (the latter need not be a codeword). If these two values are close, the AMLC holds. Using upper bounding techniques, we show that the conditional frame error probability given that the AMLC holds, is with some degree of confidence below a threshold. In channels with low noise, this threshold is orders of magnitude lower than the simulated frame error rate, and our bound holds with a very high degree of confidence. This is in stark contrast with standard Monte Carlo simulation, which would require excessively long runs to demonstrate like performance. When the AMLC holds, our approach thus provides the decoder with extra error detection capability, which is especially important in applications requiring high data integrity.

The problem of low-complexity linear programming (LP) decoding of nonbinary low-density parity-check (LDPC) codes is considered, and an iterative LP decoding algorithm is presented. Results that were previously derived for binary LDPC codes are extended to the nonbinary case. Both simple and generalized nonbinary LDPC codes are considered. It is shown how the algorithm can be implemented efficiently using a finite-field fast Fourier transform. Then, the convergence rate of the algorithm is analyzed. The complexity of the algorithm scales linearly in the block length, and it can approximate, up to an arbitrarily small relative error, the objective function of the exact LP solution. When applied to a typical code from an appropriate nonbinary LDPC code ensemble, the algorithm can correct a constant fraction of errors in linear (in the block length) computational complexity. Computer experiments with the new iterative LP decoding algorithm show that, in the error floor region, it can have better performance compared to belief propagation decoding, with similar computational requirements.

A coding scheme for write once memory (WOM) using polar codes is presented. It is shown that the scheme achieves the capacity region of noiseless WOMs when an arbitrary number of multiple writes is permitted. The encoding and decoding complexities scale as O(N log N) where N is the blocklength. For N sufficiently large, the error probability decreases sub-exponentially in N. Some simulation results with finite length codes are presented.

We consider LDPC code ensembles over non-binary Galois fields, when used for transmission over arbitrary memoryless channels. Belief propagation decoding for these codes has been shown to achieve excellent results. However, computing the decoding threshold using density evolution is usually impractical, since one needs to propagate multi-dimensional probability distributions, and Monte Carlo simulations are required instead. By considering the evolution of the message Bhattacharyya parameter and the message expected value parameter we derive a simple lower bound on the performance of the algorithm. This bound applies for both regular and irregular non-binary LDPC ensembles.

A method which obtains a tight lower bound on the fractional distance of LDPC codes is proposed. This algorithm exhibits complexity which scales quadratically with the block length, and thus less than currently-known methods. We also show how the fundamental LP polytope for generalized LDPC codes and nonbinary LDPC codes can be obtained.

A new property which relies on the linear programming (LP) decoder, the approximate maximum-likelihood certificate (AMLC), is introduced. When the belief propagation decoder outputs a codeword, this property is satisfied if this codeword is close to the LP solution. Using upper bounding techniques, it is demonstrated that the conditional frame error probability given that the AMLC holds is, with some degree of confidence, below a threshold. In channels with low noise, this threshold is several orders of magnitude lower than the simulated frame error rate, and our bound holds with very high degree of confidence. In contrast, showing this error performance by simulation would require very long Monte Carlo runs. When the AMLC holds, our approach thus provides the decoder with extra error detection capability, which is especially important in applications requiring high data integrity.

We examine LDPC codes decoded using linear programming (LP). Four contributions to the LP framework are presented. First, a new method of tightening the LP relaxation, and thus improving the LP decoder, is proposed. Second, we present an algorithm which calculates a lower bound on the minimum distance of a specific code. This algorithm exhibits complexity which scales quadratically with the block length. Third, we propose a method to obtain a tight lower bound on the fractional distance, also with quadratic complexity, and thus less than previously-existing methods. Finally, we show how the fundamental LP polytope for generalized LDPC codes and nonbinary LDPC codes can be obtained.

We propose a technique for improving LP decoding, based on the merging of check nodes. This technique can be applied to standard as well as generalized LDPC codes. Furthermore, we show how a recently-discovered linear-complexity LP decoder can be used to derive non-trivial lower bounds on the minimum distance of specific LDPC codes, with complexity that exhibits quadratic growth with respect to the block length. This bound can be refined using the check node merging technique. The lower bound on the minimum distance is shown to be an upper bound on the fractional distance of the code.

A binary erasure channel with erasure probability which can take one of two values is considered. Transmission is done by using a low density parity-check code under the requirement that completely successful decoding is possible when the channel is in its better state, while tolerating some predetermined residual erasure fraction when the channel is in its worse state. Upper bounds on the achievable design rate under iterative decoding are derived for this setting. These bounds are compared to rates obtained by practical code profiles. It is also observed that when exceeding the capacity of the erasure channel, the performance of such codes exhibits graceful degradation as measured by the residual erasure fraction.

The problem of low complexity linear programming (LP) decoding of low-density parity-check (LDPC) codes is considered. An iterative algorithm, similar to min-sum and belief propagation, for efficient approximate solution of this problem was proposed by Vontobel and Koetter. In this paper, the convergence rate and computational complexity of this algorithm are studied using a scheduling scheme that we propose. In particular, we are interested in obtaining a feasible vector in the LP decoding problem that is close to optimal in the following sense. The distance, normalized by the block length, between the minimum and the objective function value of this approximate solution can be made arbitrarily small. It is shown that such a feasible vector can be obtained with a computational complexity which scales linearly with the block length. Combined with previous results that have shown that the LP decoder can correct some fixed fraction of errors we conclude that this error correction can be achieved with linear computational complexity. This is achieved by first applying the iterative LP decoder that decodes the correct transmitted codeword up to an arbitrarily small fraction of erroneous bits, and then correcting the remaining errors using some standard method. These conclusions are also extended to generalized LDPC codes.

The error performance of the ensemble of typical low-definition parity-check (LDPC ) codes transmitted over the binary erasure channel (BEC) is analyzed. In the past, lower bounds on the error exponents were derived. In this paper, a probabilistic upper bound on this error exponent is derived. This bound holds with some confidence level.

A binary erasure channel with erasure probability which can take one of two values is considered. Transmission is done by using a low density parity-check code under the requirement that completely successful decoding is possible when the channel is in its better state, while tolerating some predetermined residual erasure fraction when the channel is in its worse state. Upper bounds on the achievable design rate under iterative decoding are derived for this setting. These bounds are compared to rates obtained by practical code profiles. It is also observed that when exceeding the capacity of the erasure channel, the performance of such codes exhibits graceful degradation as measured by the residual erasure fraction.

The problem of low complexity linear programming (LP) decoding of low-density parity-check (LDPC) codes is considered. An iterative algorithm for efficient approximate solution of this problem was proposed by Vontobel and Koetter. In this paper the convergence rate and computational complexity of this algorithm are studied. In particular we are interested in obtaining a feasible vector in the LP decoding problem, with objective function value whose distance to the minimum, normalized by the block length, can be made arbitrarily small. It is shown that such a feasible vector can be obtained in linear, in the block length, computational complexity. Combined with previous results, that have shown that the LP decoder can correct some fixed fraction of errors, we conclude that this error correction can be achieved with linear computational complexity.

We consider transmission over the ergodic fading multiple-antenna broadcast (MIMO-BC) channel with partial channel state information at the transmitter and full information at the receiver. Over the equivalent non-fading channel, capacity has recently been shown to be achievable using transmission schemes that were designed for the "dirty paper" channel. We focus on a similar "fading paper" model. The evaluation of the fading paper capacity is difficult to obtain. We confine ourselves to the linear-assignment capacity, which we define, and use convex analysis methods to prove that its maximizing distribution is Gaussian. We compare our fading-paper transmission to an application of dirty paper coding that ignores the partial state information and assumes the channel is fixed at the average fade. We show that a gain is easily achieved by appropriately exploiting the information. We also consider a cooperative upper bound on the sum-rate capacity as suggested by Sato. We present a numeric example that indicates that our scheme is capable of realizing much of this upper bound.

The iterative bit flipping algorithm is applied to the standard regular low-density parity-check (LDPC) code ensemble. In the past, it was shown, for a typical code in the ensemble with left degree at least five and block length sufficiently large, that this algorithm can correct a linear (in the block length) number of worst case errors. In this paper, this result is extended to the case where the left degree is at least four. For the case where the left degree is larger than four, an improvement, compared to existing results, of several orders of magnitude is obtained on the fraction of worst case errors that can be corrected. It is also shown how the results can be further improved when random errors produced by the channel (as opposed to worst case errors) are considered.

We apply the iterative bit flipping algorithm to the standard regular low-density parity-check (LDPC) code ensemble. In the past it was shown, for a typical code in the ensemble with left degree at least five and block length sufficiently large, that this algorithm can correct all error patterns with some linear (in the block length) number of errors. We extend this result to the case where the left degree is at least four. For the case where the left degree is larger than four, we obtain an improvement of several orders of magnitude compared to the existing results on the fraction of worst case errors that can be corrected. We also show how our results can be improved when we consider random errors (as opposed to worst case errors) produced by the channel.

Techniques for efficient speaker recognition are presented. These techniques are based on approximating Gaussian mixture modeling (GMM) likelihood scoring using approximated cross entropy (ACE). Gaussian mixture modeling is used for representing both training and test sessions and is shown to perform speaker recognition and retrieval extremely efficiently without any notable degradation in accuracy compared to classic GMM-based recognition. In addition, a GMM compression algorithm is presented. This algorithm decreases considerably the storage needed for speaker retrieval.

The ensemble of regular low-definition parity-check (LDPC) codes is considered. Using concentration results on the weight distribution, lower bounds on the error rate of a random code in the ensemble are derived. These bounds hold with some confidence level. Combining these results with known lower bounds on the error exponent, confidence intervals on the error exponent, under maximum-likelihood (ML) decoding, are obtained. Over a large range of channel parameter and transmission rate values, when the graph connectivity is sufficiently large, the upper bound of the interval approaches the lower bound, and the probability that the error exponent is within the interval can be arbitrarily close to one. In fact, in this case the true error exponent approaches the maximum between the random coding and the expurgated random coding exponents, with probability that approaches one.

The complexity of brute-force encoding of low-density parity-check (LDPC) codes is proportional to the square value of the block length. Richardson and Urbanke have proposed efficient encoding algorithms for LDPC codes. These algorithms permute the parity-check matrix of the code iteratively, such that it becomes approximately lower triangular. We propose a new approach for efficient encoding of LDPC codes in which we modify the code ensemble to force an approximate lower triangular structure, thus eliminating the need to apply the algorithms of Richardson and Urbanke in this ensemble. We prove that the new ensemble has the same asymptotic threshold as the corresponding standard ensemble. The new ensemble can be used for linear time encoding of an arbitrary code profile. Computer simulations confirm that the performances of the standard and new ensembles are also very similar when using finite length codes

We consider the ensemble of regular LDPC codes and use recent concentration results on the distance spectrum to derive upper bounds on the error exponent of a randomly chosen code from the ensemble. These bounds hold with some confidence level that approaches one as the connectivity of the graph increases. We show that the bounds can be used to obtain the true error exponent over some range of channel parameter values, with the above confidence level

The complexity of brute force encoding of LDPC codes is proportional to the square value of the block length. Richardson and Urbanke have proposed efficient encoding algorithms for LDPC codes. These algorithms permute the parity check matrix of the code iteratively, such that it becomes approximately lower triangular. We propose a new approach for efficient encoding of LDPC codes in which we modify the code ensemble to force an approximate lower triangular structure, thus eliminating the need to apply the algorithms of Richardson and Urbanke. We prove that the new ensemble has the same asymptotic threshold as the corresponding standard ensemble. The new ensemble can be used for linear time encoding of an arbitrary code profile. Computer simulations confirm that the performances of the standard and new ensembles are also very similar when using finite length codes

We present an analysis under the iterative decoding of coset low-density parity-check (LDPC) codes over GF(q), designed for use over arbitrary discrete-memoryless channels (particularly nonbinary and asymmetric channels). We use a random- coset analysis to produce an effect that is similar to output symmetry with binary channels. We show that the random selection of the nonzero elements of the GF(q) parity-check matrix induces a permutation-invariance property on the densities of the decoder messages, which simplifies their analysis and approximation. We generalize several properties, including symmetry and stability from the analysis of binary LDPC codes. We show that under a Gaussian approximation, the entire q-1-dimensional distribution of the vector messages is described by a single scalar parameter (like the distributions of binary LDPC messages). We apply this property to develop extrinsic information transfer (EXIT) charts for our codes. We use appropriately designed signal constellations to obtain substantial shaping gains. Simulation results indicate that our codes outperform multilevel codes at short block lengths. We also present simulation results for the additive white Gaussian noise (AWGN) channel, including results within 0.56 dB of the unrestricted Shannon limit (i.e., not restricted to any signal constellation) at a spectral efficiency of 6 bits/s/Hz.

We present simple, practical codes designed for the binary and Gaussian dirty-paper channels. We show that the dirty-paper decoding problem can be transformed into an equivalent multiple-access decoding problem, for which we apply superposition coding. Our concept is a generalization of the nested lattices approach of Zamir, Shamai, and Erez. In a theoretical setting, our constructions are capable of achieving capacity using random component codes and maximum-likelihood decoding. We also present practical implementations of the constructions, and simulation results for both dirty-paper channels. Our results for the Gaussian dirty-paper channel are on par with the best known results for nested lattices. We discuss the binary dirty- tape channel, for which we present a simple, effective coding technique. Finally, we propose a framework for extending our approach to general Gel'fand-Pinsker channels.

Test utterance parameterization (TUP) using Gaussian mixture models (GMMs) has recently been shown to be beneficial for speaker indexing due to its computational efficiency and identical accuracy compared to classic GMM-based recognizers. We show that TUP can also lead to more accurate speaker recognition. On the NIST-2004 evaluation corpus, recognition error rate was reduced by 8% compared to the classic GMM-based algorithm. Furthermore, we introduce a novel generative statistical model for generation of test utterances by speakers. This model is incorporated naturally into the TUP framework and improves speaker recognition accuracy. On the NIST-2004 evaluation corpus, recognition error rate was reduced by 15% compared to the classic GMM-based algorithm.

In this paper we present techniques for efficient speaker recognition of a large population of speakers and for efficient speaker retrieval in large audio archives. We deal with aspects of both time and storage. We use Gaussian mixture modeling (GMM) for representing both train and test sessions and show how to perform speaker recognition and retrieval efficiently with only a small degradation in accuracy compared to classic GMM based recognition. We present techniques for achieving a dramatic acceleration of both tasks. Finally, we present a GMM compression algorithm that decreases considerably the storage needed for speaker retrieval. 1.

In this paper we present a speaker recognition algorithm that models explicitly intra-speaker inter-session variability. Such variability may be caused by changing speaker characteristics (mood, fatigue, etc.), channel variability or noise variability. We define a session-space in which each session (either train or test session) is a vector. We then calculate a rotation of the session-space for which the estimated intra-speaker subspace is isolated and can be modeled explicitly. We evaluated our technique on the NIST-2004 speaker recognition evaluation corpus, and compared it to a GMM baseline system. Results indicate significant reduction in error rate. 1.

We consider the ensemble of regular LDPC codes and obtain an expression for the second moment of the distance spectrum. We show how this expression can be used to derive a lower bound on the probability that the growth rate of a randomly chosen code from the ensemble is equal to the growth rate of the average distance spectrum, when the block length is sufficiently large. In particular, when the connectivity of the code is sufficiently large, the distance spectrum of a code in the ensemble is concentrated. We then derive a lower bound on the probability (confidence level) that the minimum distance and error rate, respectively, of a randomly chosen code from the ensemble are upper and lower bounded by some values (which depend on the confidence level)

We consider coset LDPC codes over GF(q), designed for use over arbitrary channels (particularly nonbinary and asymmetric channels). We show that the random selection of the nonzero elements of the GF(q) parity-check matrix induces a permutation-invariance property on the densities of the messages produced by the decoder. We use this property to show that under a Gaussian approximation, the entire q - 1 dimensional distribution of the vector messages is described by a single scalar parameter. We apply this result to develop EXIT charts for our codes. We use appropriately designed signal constellations to obtain substantial shaping gains. Simulation results indicate that our codes outperform multilevel codes at short block lengths. We also present results for the AWGN channel at 0.56 dB of the unconstrained Shannon limit (i.e. not restricted to any signal constellation) at a spectral efficiency of 6 bits/s/Hz

Speaker Indexing has recently emerged as an important task due to the rapidly growing volume of audio archives. Current filtration techniques still suffer from problems both in accuracy and efficiency. The major reason for the drawbacks of existing solutions is the use of inaccurate anchor models. The contribution of this paper is two-fold. On the theoretical side, a new method is developed for simulating GMM scoring. This enables to fit a GMM not only to every target speaker but also to every test utterance, and then compute the likelihood of the test call using these GMMs instead of using the original data. The second contribution of this paper is in harnessing this GMM simulation to achieve very efficient speaker indexing in terms of both search time and index size. Results on the SPIDRE corpus show that our approach maintains the accuracy of the conventional GMM algorithm. 1.

This paper is motivated by the fact that text dependent speaker recognition is inherently more accurate than text independent speaker recognition. In this work we assign models to frequent words spoken by a speaker and spot them in a test call. In this way, text-dependent speaker recognition technology can be used for text independent tasks. The approach we take is to use DTW (Dynamic Time Warp) word spotting to find words in the test that resemble words in the train set. Results on the SPIDRE corpus show that using a combined DTW spotter based system and a GMM system improves performance significantly. For very low false acceptance rate (0.1%) misdetection was reduced from 32.2% to 23.3 % (28 % reduction). For low false acceptance rate (1%) misdetection was reduced from 28.9 % to 21.1 % (27% reduction). 1.

We introduce a discriminative training algorithm for the estimation of hidden Markov model (HMM) parameters. This algorithm is based on an approximation of the maximum mutual information (MMI) objective function and its maximization in a technique similar to the expectation-maximization (EM) algorithm. The algorithm is implemented by a simple modification of the standard Baum-Welch algorithm, and can be applied to speech recognition as well as to word-spotting systems. Three tasks were tested: isolated digit recognition in a noisy environment, connected digit recognition in a noisy environment and word-spotting. In all tasks a significant improvement over maximum likelihood (ML) estimation was observed. We also compared the new algorithm to the commonly used extended Baum-Welch MMI algorithm. In our tests the algorithm showed advantages in terms of both performance and computational complexity.

We derive upper bounds on the maximum achievable rate of low-density parity-check (LDPC) codes used over the binary erasure channel (BEC) under Gallager's decoding algorithm, given their right-degree distribution. We demonstrate the bounds on the ensemble of right-regular LDPC codes and compare them with an explicit left-degree distribution constructed from the given right degree.

We discuss three structures of modified low-density parity-check (LDPC) code ensembles designed for transmission over arbitrary discrete memoryless channels. The first structure is based on the well-known binary LDPC codes following constructions proposed by Gallager and McEliece, the second is based on LDPC codes of arbitrary (q-ary) alphabets employing modulo-q addition, as presented by Gallager, and the third is based on LDPC codes defined over the field GF(q). All structures are obtained by applying a quantization mapping on a coset LDPC ensemble. We present tools for the analysis of nonbinary codes and show that all configurations, under maximum-likelihood (ML) decoding, are capable of reliable communication at rates arbitrarily close to the capacity of any discrete memoryless channel. We discuss practical iterative decoding of our structures and present simulation results for the additive white Gaussian noise (AWGN) channel confirming the effectiveness of the codes.

We show how asymptotic estimates of powers of polynomials with nonnegative coefficients can be used in the analysis of low-density parity-check (LDPC) codes. In particular, we show how these estimates can be used to derive the asymptotic distance spectrum of both regular and irregular LDPC code ensembles. We then consider the binary erasure channel (BEC). Using these estimates we derive lower bounds on the error exponent, under iterative decoding, of LDPC codes used over the BEC. Both regular and irregular code structures are considered. These bounds are compared to the corresponding bounds when optimal (maximum-likelihood (ML)) decoding is applied.

We propose an efficient maximum-likelihood (ML) decoding algorithm for decoding low-density parity-check (LDPC) codes over the binary-erasure channel (BEC). We also analyze the computational complexity of the proposed algorithm.

We introduce an enhanced dynamic time warping model (EDTW) which, unlike conventional dynamic time warping (DTW), considers all possible alignment paths for recognition as well as for parameter estimation. The model, for which DTW and the hidden Markov model (HMM) are special cases, is based on a well-defined quality measure. We extend the derivation of the Forward and Viterbi algorithms for HMMs, in order to obtain efficient solutions for the problems of recognition and optimal path alignment in the new proposed model. We then extend the Baum-Welch (1972) estimation algorithm for HMMs and obtain an iterative method for estimating the model parameters of the new model based on the Baum inequality. This estimation method efficiently considers all possible alignment paths between the training data and the current model. A standard segmental K-means estimation algorithm is also derived for EDTW. We compare the performance of the two training algorithms, with various path movement constraints, in two isolated letter recognition tasks. The new estimation algorithm was found to improve performance over segmental K-means in most experiments.

We present a spectral domain, speech enhancement algorithm. The new algorithm is based on a mixture model for the short time spectrum of the clean speech signal, and on a maximum assumption in the production of the noisy speech spectrum. In the past this model was used in the context of noise robust speech recognition. In this paper we show that this model is also effective for improving the quality of speech signals corrupted by additive noise. The computational requirements of the algorithm can be significantly reduced, essentially without paying performance penalties, by incorporating a dual codebook scheme with tied variances. Experiments, using recorded speech signals and actual noise sources, show that in spite of its low computational requirements, the algorithm shows improved performance compared to alternative speech enhancement algorithms.

We derive upper bounds on the rate of low-density parity-check (LDPC) codes for which reliable communication is achievable. We first generalize Gallager's (1963) bound to a general binary-input symmetric-output channel. We then proceed to derive tighter bounds. We also derive upper bounds on the rate as a function of the minimum distance of the code. We consider both individual codes and ensembles of codes.

We consider Gallager's (1963) soft-decoding (belief propagation) algorithm for decoding low-density parity-check (LDPC) codes, when applied to an arbitrary binary-input symmetric-output channel. By considering the expected values of the messages, we derive both lower and upper bounds on the performance of the algorithm. We also derive various properties of the decoding algorithm, such as a certain robustness to the details of the channel noise. Our results apply both to regular and irregular LDPC codes.

The synchronization phase of a code division multiple access communication system might pose a limitation on the performance of the system, since unlike other communication systems it is required to obtain the state (i.e., sequence phase) of a linear feedback shift register (LFSR). Usually the state is obtained by using a brute force exhaustive search over all possibilities, which might be a computationally demanding task. In this paper, we suggest a new method for LFSR sequence phase acquisition. Our method is suitable for practical systems in which an unknown frequency drift may be present. Simulation results for the IS-95/CDMA-2000 standard show a dramatic reduction in the time required to acquire synchronization when using the new algorithm compared to the standard synchronization method.

The computational complexity of classical time domain gradient-based echo cancellation algorithms might be prohibitively high, due to the very long response of the acoustic transfer functions involved. A reduction in computational complexity can be achieved by using frequency domain or subband algorithms. However, these algorithms introduce an inherent delay in the signal path. The delayed echo has an annoying psychoacoustic effect. Additionally, the delay prevents natural, full-duplex conversation. Moreover, when operated in practical scenarios, using speech signals in actual room acoustic environments, the convergence and tracking properties of the frequency domain algorithms do not compare favorably with those of the NLMS algorithm. This is because the range of values of the convergence constant that support a stable filter is more restrictive for the frequency domain algorithms. In this study we introduce a new algorithm termed delayless frequency domain (DLFD). The DLFD exhibits performance comparable to that of the NLMS algorithm with a computational complexity comparable to that of standard frequency domain algorithms and without the processing delay.

We show how expander-based arguments may be used to prove that message-passing algorithms can correct a linear number of erroneous messages. The implication of this result is that when the block length is sufficiently large, once a message-passing algorithm has corrected a sufficiently large fraction of the errors, it will eventually correct all errors. This result is then combined with known results on the ability of message-passing algorithms to reduce the number of errors to an arbitrarily small fraction for relatively high transmission rates. The results hold for various message-passing algorithms, including Gallager's hard-decision and soft-decision (with clipping) decoding algorithms. Our results assume low-density parity-check (LDPC) codes based on an irregular bipartite graph.

We derive both upper and lower bounds on the decoding error probability of maximum-likelihood (ML) decoded low-density parity-check (LDPC) codes. The results hold for any binary-input symmetric-output channel. Our results indicate that for various appropriately chosen ensembles of LDPC codes, reliable communication is possible up to channel capacity. However, the ensemble averaged decoding error probability decreases polynomially, and not exponentially. The lower and upper bounds coincide asymptotically, thus showing the tightness of the bounds. However, for ensembles with suitably chosen parameters, the error probability of almost all codes is exponentially decreasing, with an error exponent that can be set arbitrarily close to the standard random coding exponent.

A major limitation of hidden Markov model (HMM) based automatic speech recognition is the inherent assumption that successive observations within a state are independent and identically distributed (i.i.d.). The i.i.d. assumption is reasonable for some of the states (e.g., a state that corresponds to a steady state vowel). However, most states clearly violate this assumption (e.g., states corresponding to vowel-consonant transition, diphthongs, etc.) and are in fact characterized by a highly correlated and nonstationary speech signal. Previous alternative models have been proposed, that attempt to describe the dynamics of the signal within a phonetic unit. The new approach is generally known by the name segmental modeling, since the speech signal is modeled on a segment level base and not on a frame base (such as HMM). We propose a family of new segmental models that are composed of two elements. The first element is a nonparametric representation of the mean and variance trajectories, and the second is some parameterized transformation (e.g., random shift) of the trajectory that is global to the entire segment. The new model is in fact a continuous mixture of segment trajectories. We present recognition results on a large vocabulary task, and compare the model to alternative segment models on a triphone recognition task.

We present the concept of a scaled random segmental model, which aims to overcome the modeling problem created by the fact that segment realizations of the same phonetic unit differ in length. In the scaled model the variance of the random mean trajectory is inversely proportional to the segment length. The scaled model enables a Baum-Welch type parameter reestimation, unlike the previously suggested, non-scaled models, that require more complicated iterative estimation procedures. In experiments we have conducted with phoneme classification, it was found that the scaled model shows improved performance compared to the non-scaled model.

Speech quality and intelligibility might significantly deteriorate in the presence of background noise, especially when the speech signal is subject to subsequent processing. In particular, speech coders and automatic speech recognition (ASR) systems that were designed or trained to act on clean speech signals might be rendered useless in the presence of background noise. Speech enhancement algorithms have therefore attracted a great deal of interest. In this paper, we present a class of Kalman filter-based algorithms with some extensions, modifications, and improvements of previous work. The first algorithm employs the estimate-maximize (EM) method to iteratively estimate the spectral parameters of the speech and noise parameters. The enhanced speech signal is obtained as a byproduct of the parameter estimation algorithm. The second algorithm is a sequential, computationally efficient, gradient descent algorithm. We discuss various topics concerning the practical implementation of these algorithms. Extensive experimental study using real speech and noise signals is provided to compare these algorithms with alternative speech enhancement algorithms, and to compare the performance of the iterative and sequential algorithms.

We lower-bound the error-correcting capabilities of the Hopfield (1982) network under error-tolerant conditions, given some distorted version of a fundamental memory with a random (typical) error pattern. Our main result is that for any sufficiently small /spl alpha/, and for any /spl rho/<1/2, a Hopfield memory with n neurons can store /spl alpha/n fundamental memories, such that the following is satisfied in probability: a distorted fundamental memory with /spl rho/n errors, located at random positions may be corrected up to a residual error rate of exp{-1/2/spl alpha/}.

Recent results on the memory storage capacity of higher order neural networks indicate a significant improvement compared to the limited capacity of the Hopfield model. However, such results have so far been obtained under the restriction that only a single iteration is allowed to converge. This paper presents a indirect convergence (long-term attraction) analysis of higher order neural networks. Our main result is that for any kappa(d)<d!2(d-1)/(2d)!, and 0< or =rho<1/2, a Hebbian higher order neural network of order d with n neurons can store a random set of kappa(d)n(d)/log n fundamental memories such that almost all memories have an attraction radius of size rhon. If kappa(d)

Speech quality and intelligibility might significantly deteriorate in the presence of background noise, especially when the speech signal is subject to subsequent processing. In this paper we represent a class of Kalman-filter based speech enhancement algorithms with some extensions, modifications, and improvements. The first algorithm employs the estimate-maximize (EM) method to iteratively estimate the spectral parameters of the speech and noise parameters. The enhanced speech signal is obtained as a by-product of the parameter estimation algorithm. The second algorithm is a sequential, computationally efficient, gradient descent algorithm. We discuss various topics concerning the practical implementation of these algorithms. Experimental study, using real speech and noise signals is provided to compare these algorithms with alternative speech enhancement algorithms, and to compare the performance of the iterative and sequential algorithms.

We compare two different approaches to the problem of additive noise in a hidden Markov model (HMM) filterbank-based speech recognition system: (i) preprocessing by estimation and (ii) adaptation of the HMM output probability distributions. The adaptation method, previously formulated only for the static spectral features, is generalized in this paper to the time-derivative of the spectrum. Estimation and adaptation are formulated with a common statistical model (MIXMAX) and are compared using the same recognition system. We find that under low and medium signal-to-noise ratio (SNR) conditions, parameter adaptation is superior to preprocessing by estimation.

A major weakness of conventional hidden Markov models is that they implicitly model state durations by a geometric distribution, which is usually inappropriate. This paper presents a modified Viterbi algorithm that, by incorporating proper state and word duration modeling, significantly reduces the string error rate of the conventional Viterbi algorithm for a speaker-independent, connected-digit string task. The algorithm has essentially the same computational requirements of the conventional Viterbi algorithm.

We address the problem of explicit state and word duration modeling in hidden Markov models (HMMs). A major weakness of conventional HMMs is that they implicitly model state durations by a geometric distribution, which is usually inappropriate. Using explicit modeling of state and word durations, it is possible to significantly enhance the performance of speech recognition systems. The main outcome of this work is a modified Viterbi algorithm that by incorporating both state and word duration modeling, reduces the string error rate of the conventional Viterbi algorithm by 29% and 43% for known and unknown string lengths respectively, for a speaker independent, connected digit string task. The uniqueness of the algorithm is that unlike alternative approaches, it adds the duration metric at each frame transition (and not at the end of a state, word or sentence), thus enhancing the performance.

Considers a Hopfield associative memory consisting of n neurons, designed to store an m-set of n-dimensional /spl plusmn/1 statistically independent uniformly distributed random vectors (fundamental memories), using a connection matrix, constructed by the usual Hebbian rule. Previous results have indicated that the maximal value of m, such that almost all m vectors are stable points of the memory, in probability (i.e., with probability approaching one as n approaches infinity), is n/(2 log n)(n/(4 log n) if all m vectors must be stable simultaneously, in probability). Previous work further analyzed the direct convergence (i.e., convergence in one iteration) error-correcting power of the Hopfield memory. The present authors rigorously analyze the general case of nondirect convergence, and prove that in the m=n/(2 log n) case, independently of the operation mode used (synchronous or asynchronous), almost all memories have an attraction radius of size n/2 around them (in the n/(4 log n) case, all memories have such an attraction radius, in probability). This result, which was conjectured in the past but was never proved rigorously, combined with an old converse result that the network cannot store more than n/(2 log n)(n/(4 log n)) fundamental memories, gives a full picture of the error-correcting power of the Hebbian Hopfield network. The authors also upper bound the number of iterations required to achieve convergence.>

The speech production model where the speech signal is modeled as the output of an all pole filter driven either by some white noise sequence (unvoiced speech) or by the sum of an impulse sequence and a noise sequence (voiced speech) is considered. Approximate maximum-likelihood (ML) estimation algorithms for the unvoiced case are well known. In this work, the expectation-maximization (EM) algorithm is used in order to obtain the ML estimator of the parameters for the voiced speech model. These parameters consist of the parameters of the impulse sequence (pitch parameters) and the parameters of the filter (autoregressive parameters).>

A description is presented of the authors' current research on automatic speech recognition of continuously read sentences from a naturally-occurring corpus: office correspondence. The recognition system combines features from their current isolated-word recognition system and from their previously developed continuous-speech recognition system. It consists of an acoustic processor, an acoustic channel model, a language model, and a linguistic decoder. Some new features in the recognizer relative to the isolated-word speech recognition system include the use of a fast match to prune rapidly to a manageable number the candidates considered by the detailed match, multiple pronunciations of all function words, and modeling of interphone coarticulatory behavior. The authors recorded training and test data from a set of ten male talkers. The perplexity of the test sentences was found to be 93; none of sentences was part of the data used to generate the language model. Preliminary (speaker-dependent) recognition results on these talkers yielded an average word error rate of 11.0%.>