Nonrecursive decoding algorithm for PR4 channel

The Viterbi algorithm (VA) is a recursive optimal solution to the state sequence estimation problem. The recursive nature of this algorithm puts limitations on high-speed implementations of Viterbi decoders. The authors propose a nonrecursive suboptimal decoding algorithm for the PR4 channel. The new decoder has negligible performance loss     

Correcting dependent errors in sequences generated by finite-stateprocesses

A new channel model and channel inversion algorithm are presented for correcting symbol sequences that have been corrupted by an unknown combination of known fault mechanisms. The algorithm is similar to the Viterbi algorithm in that it is suitable for situations in which the uncorrupted data string is generated by a known finite-state process, but it is more versatile in that it can correct a much broader class of errors. Of particular importance is the fact that the algorithm corrects common context-sensitive errors, such as symbol changes, transpositions, mergers, splits, insertions, and deletions, which may be assigned different probabilities depending on the context of preceeding and subsequent symbols. As many communication channels can be modeled in this way, this algorithm is a significant extension over the Viterbi algorithm and previous decoding techniques. The notion of channel rules is introduced to provide a framework for the user to specify the channel operation. The algorithm is given in both an off-line form and a recursive form suitable for sequentially presented data streams. In most applications, the recursive form has computational complexity only a constant times that of the Viterbi algorithm     

A reduced-complexity online state sequence and parameter estimatorfor superimposed convolutional coded signals

This paper develops a reduced-complexity online state sequence and parameter estimator for superimposed convolutional coded signals. Joint state sequence and parameter estimation is achieved by iteratively estimating the state sequence via a variable reduced-complexity Viterbi algorithm (VRCVA) and the model parameters via a recursive expectation maximization (EM) approach. The VRCVA is developed from a fixed reduced-complexity Viterbi algorithm (FRCVA). The FRCVA is a special case of the delayed decision-feedback sequence estimation (DDFSE) algorithm. The performance of online versions of the FRCVA, VRCVA, and the standard Viterbi algorithm (VA) are compared when they are used to estimate the state sequence as part of the reduced-complexity online state sequence and parameter estimator     

高速Viterbi处理器—流水式块处理并行结构

本文提出一种流水式块处理并行Ｖｉｔｅｒｂｉ处理器，可以得到ＬＭ倍增速（Ｍ为流水级数，Ｌ为块长度），为达到更高速的Ｖｉｔｅｒｂｉ处理器提供了新型的并行结构。它可用Ｓｙｓｔｏｌｉｅ阵列构成，因而适于ＶＬＳＩ实现。     

Real-Time Minimal-Bit-Error Probability Decoding of Convolutional Codes

A recursive procedure is derived for decoding of rateR = 1/nbinary convolutional codes which minimizes the probability of the individual decoding decisions for each information bit, subject to the constraint that the decoding delay be limited to Δ branches. This new decoding algorithm is similar to, but somewhat more complex than, the Viterbi decoding algorithm. A "real-time," i.e., fixed decoding delay, version of the Viterbi algorithm is also developed and used for comparison to the new algorithm on simulated channels. It is shown that the new algorithm offers advantages over Viterbi decoding in soft-decision applications, such as in the inner coding system for concatenated coding.     

The viterbi algorithm

The Viterbi algorithm (VA) is a recursive optimal solution to the problem of estimating the state sequence of a discrete-time finite-state Markov process observed in memoryless noise. Many problems in areas such as digital communications can be cast in this form. This paper gives a tutorial exposition of the algorithm and of how it is implemented and analyzed. Applications to date are reviewed. Increasing use of the algorithm in a widening variety of areas is foreseen.     

Stack algorithm for recursive deconvolution of Bernoulli-Gaussianprocesses [seismic exploration]

The deconvolution of pulse trains modeled as Bernoulli-Gaussian processes is addressed. The detector presented implements a stack Viterbi algorithm with a parametric level of suboptimality. Simulation results are satisfactory, even in the difficult case of a poor spectral content of the wavelet. The recursive and parallel structure of the method allows fast data processing on modern architectures     

MIMO系统中STTC译码的一种改进型算法

本文对MIMO系统中用于STTC编码器的VA译码算法进行了改进,建立了节点度量的递推方程,并给出了分枝转移的度量方法。改进后的VA算法适用于已经估计出MIMO系统中信道转移阵的条件下。相比于标准的STTC译码算法,改进后的算法可以在一根接收天线上独立进行,并且节点度量可以通过递推方程进行累积。当多根天线独立译码后,可以进一步进行后续比较以再次降低误码率。仿真结果显示：改进VA在比特误码性能上与标准VA算法接近,但是在分段度量计算时收敛速度要远快于标准VA。     

Syndrome Decoding of Convolutional Codes

The classical Viterbi decoder recursively finds the trellis path (code word) closest to the received data. Given the received data, the syndrome decoder first forms a syndrome, instead. A recursive algorithm like Viterbi's is used to determine the noise sequence of minimum Hamming weight that can be a possible cause of this syndrome. Given the estimate of the noise sequence, one derives an estimate of the original data sequence. While the bit error probability of the syndrome decoder is no different from that of the classical Viterbi decoder, the syndrome decoder can be implemented using a read only memory (ROM), thus obtaining a considerable saving in hardware.     

多径信道下的软序列检测

本文提出一种基于软信息的序列检测算法,建立了状态转移条件下软信息的递推方程,并给出了计算不同时刻符号软信息的关系表达式.这种软序列检测算法与多径信道估计器配合,可以有效地解调发送符号序列.与传统的MLSE解调算法相比,软信息检测需要两个级连解调器,通过前后迭代来为每个发送符号计算边信息,因此误码率会得到很大的改善.此外,前端的信道估计可以由RLS算法及Kalman滤波器联合实时估计.仿真结果显示:软序列检测算法尽管在复杂度上增加了,但是误码性能远优于ML最佳准则下的解调算法.     

Implementation of scalable power and area efficient high-throughputViterbi decoders

Today's data reconstruction in digital communication systems requires designs of highest throughput rate at low power. The Viterbi algorithm is a key element in such digital signal processing applications. The nonlinear and recursive nature of the Viterbi decoder makes its high-speed implementation challenging. Several promising approaches to achieve either high throughput or low power have been proposed in the past. A combination of these is developed in this paper. Additional new concepts allow building a signal-flow graph suitable for the design of high-speed Viterbi decoders with low power. Using a flexible datapath generator facilitates the essential quantitative optimization from architectural down to physical level to fully exploit the low-power and high-speed potential of a given technology. With parameterizable design entry, this datapath generator establishes the basis of a scalable platform-based design library. Altogether, this allows coverage of the range of today's industrial interest in high throughput rates, from 150 Msymbols/s up to 1.2 Gsymbols/s using conventional CMOS logic. The features of two exemplary Viterbi decoder implementations prove the benefit of this physically oriented design methodology in terms of speed and low power, when compared to other leading edge implementations     

MIMO Receiver Using Reduced Complexity Sequence Estimation With Channel Estimation and Tracking

A sequence-based multiple-input–multiple-output receiver incorporating channel estimation and tracking for a frequency selective fading environment is developed. It employs near-maximum likelihood sequence estimation using the partitioned Viterbi algorithm and offers linearly increasing complexity with the number of transmit antennas. The receiver implements channel estimation and tracking using a vector-polynomial-based generalized recursive least squares algorithm. The resulting integrated receiver can operate in a continuously time-varying Rayleigh or Rician fading environment. Simulation results show that it offers a good tradeoff between complexity and performance. Further complexity reduction can be achieved using tentative decisions as reference signals to the estimator and a reduced complexity form of the estimator.      

一种基于小波变换和隐Markov模型的声调识别方法

本文给出了一种基于小波变换和隐Markov模型(HMM)的声调识别方法。根据小波变换检测信号突变的性质,充分利用多分辨率分析,准确可靠地实现了基音检测;采用分划Gauss混合(PGM)概率密度函数的HMM进行汉语声调识别,推导出用PGM函数的Viterbi算法的简化递推式。在匹配计算量大大减小的情况下,特定人的四声识别率为97.22％,非特定人达到94.47％。     

A novel product coding and recurrent alternate decoding scheme for image transmission over noisy channels

In this letter, we present a novel product channel coding and decoding scheme for image transmission over noisy channels. Two convolutional codes with at least one recursive systematic convolutional code are employed to construct the product code. Received data are decoded alternately in two directions. A constrained Viterbi algorithm is proposed to exploit the detection results of cyclic redundancy check codes so that both reduction in error patterns and fast decoding speed are achieved. Experiments with image data coded by the algorithm of set partitioning in hierarchical trees exhibit results better than those currently reported in the literature.     

Application of Sequential Estimation Algorithm Based on Branch Metric to Frequency-Selective Channel Equalization

In this work, a sequential estimation algorithm based on branch metric is used as channel equalizer to combat intersymbol interference in frequency-selective wireless communication channels. The bit error rate (BER) and computational complexity of the algorithm are compared with those of the maximum likelihood sequence estimation (MLSE), the recursive least squares (RLS) algorithm, the Fano sequential algorithm, the stack sequential algorithm, list-type MAP equalizer, soft-output sequential algorithm (SOSA) and maximum-likelihood soft-decision sequential decoding algorithm (MLSDA). The BER results have shown that whilst the sequential estimation algorithm has a close performance to the MLSE using the Viterbi algorithm, its performance is better than the other algorithms. Beside, the sequential estimation algorithm is the best in terms of computational complexity among the algorithms mentioned above, so it performs the channel equalization faster. Especially in M-ary modulated systems, the equalization speed of the algorithm increases exponentially when compared to those of the other algorithms.     

Incremental frequency, amplitude and phase tracker (IFAPT) forcoherent demodulation over fast flat fading channels

The incremental frequency amplitude and phase tracker (IFAPT) is a recursive algorithm that estimates the parameters of piecewise-linear approximation to assumed continuous narrow-band signals. The parameters are amplitude, phase, and their respective slopes. The simple, recursive nature of IFAPT enables its direct interaction with recursive algorithms, such as the Viterbi and the BCJR in the APP SISO module, used for iteratively decoding concatenated codes. An augmented APP (A ²P²)-module, containing IFAPT and BCJR algorithms, is here applied to iterative decoding serial concatenated convolutional codes under Rayleigh fading conditions with diversity reception. The bit-error rate under Rayleigh fading with dual diversity reception at E _bT/N₀=6 dB and f_dT_s=10^-2 is 10^-4, where E _bT is the total mean energy per bit in both diversity branches, f_d is the Doppler frequency, and T_s the symbol time     

Threshold reduction for demodulating a BPSK suppressed-carrier signal (Corresp.)

If a Costas loop is forced to have a relatively wide bandwidth, for example, to track phase variation due to platform motion, binary phase-shift keying (BPSK) demodulator performance is significantly degraded. However, if the data bits were known, the Costas loop would become equivalent to a phase-locked loop, which has approximately a 6-dB lower tracking threshold for the same loop bandwidth. A delayed-bit estimation algorithm with a recursive structure similar to the Viterbi algorithm is described. The memory in the tracking loop is exploited to correct preliminary bit decisions, as a means of realizing most of this theoretical threshold reduction. Experimental results for a practical digital implementation of the new algorithm for a 50-bit/s data rate and a 20-Hz loop noise bandwidth show a 4-dB improvement in demodulator threshold.     

An effective simplifying scheme for Viterbi decoder

A Viterbi decoding algorithm with a scarce-state transition-type circuit configuration, namely the probability selecting states (PSS) mode decoder, is presented. The algorithm has reduced complexity compared to a conventional Viterbi decoder. It is shown that this method has three advantages over the general Viterbi algorithm: it is suitable to the quick look-in code, it applies the optimum decoding in a PSS-type decoder, and it makes full use of the likelihood concentration property. The bit-error-rate (BER) performance of a r=1/2, k=7 (147,135) code and PSS-type Viterbi decoder approximates the optimum performance of the standard Viterbi decoder and reduces the hardware of the conventional Viterbi decoder to about half     

Low-Power State-Parallel Relaxed Adaptive Viterbi Decoder

Although it possesses reduced computational complexity and great power saving potential, conventional adaptive Viterbi algorithm implementations contain a global best survivor path metric search operation that prevents it from being directly implemented in a high-throughput state-parallel decoder. This limitation also incurs power and silicon area overhead. This paper presents a modified adaptive Viterbi algorithm, referred to as the relaxed adaptive Viterbi algorithm, that completely eliminates the global best survivor path metric search operation. A state-parallel decoder VLSI architecture has been developed to implement the relaxed adaptive Viterbi algorithm. Using convolutional code decoding as a test vehicle, we demonstrate that state-parallel relaxed adaptive Viterbi decoders, versus Viterbi counterparts, can achieve significant power savings and modest silicon area reduction, while maintaining almost the same decoding performance and very high throughput     

Linear Minimum Mean-Square Error Estimators Applied to Channel Equalization

This concise paper investigates various aspects of the application of unbiased linear minimum mean-square error (ULMMSE) estimators to the equalization of channels used for digital data transmission. One application is to the equalization of the channel to a response free from intersymbol interference. Previous results regarding this application are clarified and extended. The other application is to the equalization of the channel to a finite short memory response. This stems from an interest in reducing the complexity of the Viterbi algorithm. Various new results on the optimum ULMMSE equalizer and its performance are presented. In both applications, the optimum ULMMSE equalizer is a stable, realizable, finite dimensional recursive filter.