A diversity combining DS/CDMA system with convolutional encodingand Viterbi decoding

Averaged diversity combining is applied to an asynchronous DS/CDMA system using convolutional encoding and Viterbi decoding. A cyclic redundancy check (CRC) code is included in the scheme to trigger retransmission requests. Multiple received packets are combined on a bit by bit basis to form a single, more reliable packet. The error correcting decoder operates on the combined packet, as opposed to the most recently received individual packet (e.g., as in a type-I hybrid ARQ protocol), substantially increasing the probability of acceptance with each additional transmission. We show that the proposed technique allows a significant increase in the CDMA system capacity, throughput, and reliability     

Survivor memory reduction in the Viterbi algorithm

This paper presents a novel approach for implementation of the Viterbi algorithm, wherein survivor paths are generally kept in as low as one half of the storage required for traditional trace-back methods. Survivor memory reduction is obtained by storing only the useful part of the survivor paths. In other words, the redundancy in the survivor paths is removed. A decoder using this approach not only requires significantly less memory, but also runs faster than conventional decoders. Some instances of this approach are explicitly presented.     

Low-Power Limited-Search Parallel State Viterbi Decoder Implementation Based on Scarce State Transition

In this paper, a low-power Viterbi decoder design based on scarce state transition (SST) is presented. A low complexity algorithm based on a limited search algorithm, which reduces the average number of the add-compare-select computation of the Viterbi algorithm, is proposed and seamlessly integrated with the SST-based decoder. The new decoding scheme has low overhead and facilitates low-power implementation for high throughput applications. We also propose an uneven-partitioned memory architecture for the trace-back survivor memory unit to reduce the overall memory access power. The new Viterbi decoder is designed and implemented in TSMC 0.18-mum CMOS process. Simulation results show that power consumption is reduced by up to 80% for high throughput wireless systems such as Multiband-OFDM Ultra-wideband applications.     

Limited search trellis decoding of convolutional codes

The least storage and node computation required by a breadth-first tree or trellis decoder that corrects t errors over the binary symmetric channels is calculated. Breadth-first decoders work with code paths of the same length, without backtracking. The Viterbi algorithm is an exhaustive trellis decoder of this type; other schemes look at a subset of the tree or trellis paths. For random tree codes, theorems about the asymptotic number of paths required and their depth are proved. For concrete convolutional codes, the worst case storage for t error sequences is measured. In both cases the optimal decoder storage has the same simple dependence on t. The M algorithm and algorithms proposed by G.J. Foschini (ibid., vol.IT-23, p.605-9, Sept. 1977) and by S.J. Simmons (PhD. diss., Queens Univ., Kingston, Ont., Canada) are optimal, or nearly so; they are all far more efficient than the Viterbi algorithm     

Modified Viterbi decoders for joint data detection and timingrecovery of convolutionally encoded PPM and OPPM optical signals

Two novel Viterbi decoders, known as joint Viterbi decoder (JVD) and enhanced Viterbi decoder (EVD), for synchronization and data detection are introduced and analyzed for convolutionally-encoded (CE) optical pulse-position modulation (PPM) and overlapping PPM (OPPM) channels. For the JVD algorithm, a count metric is employed to perform the Viterbi decoding in the absence of synchronization. For the EVD algorithm, a memory array is utilized to reduce the computation time of the JVD algorithm. With the aid of a previously proposed upper-bound and taking advantage of the minimal asymptotic normalized timing error (MANTE) concept, approximate performance measures for the EVD and JVD receivers are obtained     

Split soft-decision equalization for wireless channels with large delay spread

A novel split soft-decision equalizer (SSE) with near-optimum performance is proposed for wireless multipath channels with large delay spread. The concept of SSE is significantly different from the traditional notions of the Viterbi algorithm and decision-feedback equalizer. Instead of dealing with received sequence as a combined sequence, it splits the received sequence into its constituent paths. Using an iterative soft-decision algorithm, reliability of the soft decisions on each decomposed element is improved iteratively. The major advantage of SSE is the independence of computation complexity on channel time dispersion. Joint design of SSE with a soft-decision decoder is also considered in this paper. Performance analysis and simulation results show that performance of the proposed algorithm comes very close to that of the logarithmic maximum a posteriori decoder.     

Iterative Channel Decoding for PC-Based Software Radio DVB-T Receiver

The previous scheme only modifies the Viterbi decoder input positions where the Reed-Solomon decoder makes sure they are correct. Although it is simple and can get perfect image quality in static channels, it still suffer image quality degradation in mobile channels. Besides that, we propose to change the parameter Q of the metrics of the Viterbi decoder input positions where the Reed-Solomon decoder makes sure they are incorrect. The Q is defined as the norm of channel state information (CSI), Q = |CSI|². We propose to change Q to maximum for the Viterbi decoder input positions where the Reed-Solomon decoder makes sure they are incorrect, so the incorrect paths are unlikely to be selected in the Viterbi algorithm. The field test results in 100 km/h moving speed show that the proposed scheme with Q modification outperforms the previous scheme without Q modification by 0.36 % (7.45–>7.09 %) in symbol error rate and noticeable image quality difference.     

Viterbi译码器的优化设计

Viterbi译码算法用FPGA实现时，其硬件资源消耗与译码速度始终是相互制约的两个方面，通过合理安排ACS单元和路径度量存储单元可有效缓解这两方面的矛盾。本文以(2，1，6)卷积码为例，基于基4算法提出的动态路径度量存储管理方法能在不影响译码速度的前提下有效降低译码器的硬件复杂度。     

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     

An artificial neural net Viterbi decoder

The Viterbi algorithm is a maximum likelihood means for decoding convolutional codes and has thus played an important role in applications ranging from satellite communications to cellular telephony. In the past, Viterbi decoders have usually been implemented using digital circuits. The speed of these digital decoders is directly related to the amount of parallelism in the design. As the constraint length of the code increases, parallelism becomes problematic due to the complexity of the decoder. In this paper an artificial neural network (ANN) Viterbi decoder is presented. The ANN decoder is significantly faster than comparable digital-only designs due to its fully parallel architecture. The fully parallel structure is obtained by implementing most of the Viterbi algorithm using analog neurons as opposed to digital circuits. Several modifications to the ANN decoder are considered, including an analog/digital hybrid design that results in an extremely fast and efficient decoder. The ANN decoder requires one-sixth the number of transistors required by the digital decoder. The connection weights of the ANN decoder are either +1 or -1, so weight considerations in the implementation are eliminated. This, together with the design's modularity and local connectivity, makes the ANN Viterbi decoder a natural fit for VLSI implementation. Simulation results are provided to show that the performance of the ANN decoder matches that of an ideal Viterbi decoder     

Performance of truncated type-II hybrid ARQ schemes with noisyfeedback over block fading channels

This paper considers truncated type-II hybrid automatic repeat-request (ARQ) schemes with noisy feedback over block fading channels. With these ARQ techniques, the number of retransmissions is limited, and, similar to forward error correction (FEC), error-free delivery of data packets cannot be guaranteed. Bounds on the average number of transmissions, the average coding rate as well as the reliability of the schemes are derived using random coding techniques, and the performance is compared with FEC. The random coding bounds reveal the achievable performance with block codes and maximum-likelihood soft-decision decoding. Union upper bounds and simulation results show that over block fading channels, these bounds can be closely approached with simple terminated convolutional codes and soft-decision Viterbi decoding. Truncated type-II hybrid ARQ and the corresponding FEC schemes have the same probability of packet erasure; however, the truncated ARQ schemes offer a trade-off between the average coding rate and the probability of undetected error. Truncated ARQ schemes have significantly higher average coding rates than FEC at high and medium signal-to-noise ratio even with noisy feedback. Truncated ARQ can be viewed as adaptive FEC that adapts to the instantaneous channel conditions     

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.     

数字流水Viterbi译码器的VLSI设计

本文介绍了高速数字流水Ｖｉｔｅｒｂｉ译码器的ＶＬＳＩ设计。在符号４值系统的基础上，给出Ｖｉｔｅｒｂｉ算法的新的功能分解公式，并介绍了用于译码器实现的两个重要的快速运算部件ＡＤＤ和ＭＡＸ的原理及其现场可编程（序）门阵列（ＦＰＧＡ）实现。文中详细讨论了译码器的ＶＬＳＩ结构、设计和性能分析。本文给出的Ｖｉｔｅｒｂｉ译码器可塑性强，并具有高度的并行性和很高的数据吞吐率。     

Power control and capacity analysis for a packetized indoormultimedia DS-CDMA network

This paper proposes a packetized indoor wireless system using direct-sequence code-division multiple-access (DS-CDMA) protocol. The indoor radio environment is characterized by slow Rayleigh fading with or without lognormal shadowing. The system supports multimedia services with various transmission rates and quality of service (QoS) requirements and allows for seamless interfacing to asynchronous transfer mode (ATM) broadband networks. All packets are transmitted with forward error correction (FEC) using convolutional code for voice packets and Bose-Chaudhuri-Hocquenghem (BCH) code for data packets with an automatic retransmission request (ARQ) protocol and for video packets without ARQ. A queueing model is used for servicing data transmission requests. A power control algorithm is proposed for the system, which combines closed-loop power control with channel estimation to give the best performance. The cell capacity of each traffic type and various multimedia traffic configurations in both single-cell and multiple-cell networks are evaluated theoretically under the assumption of perfect power control. The effect of power control imperfection on the capacity using the proposed power control algorithm is investigated by computer simulation     

Implementing the Viterbi algorithm

The Viterbi algorithm, an application of dynamic programming, is widely used for estimation and detection problems in digital communications and signal processing. It is used to detect signals in communication channels with memory, and to decode sequential error-control codes that are used to enhance the performance of digital communication systems. The Viterbi algorithm is also used in speech and character recognition tasks where the speech signals or characters are modeled by hidden Markov models. The article explains the basics of the Viterbi algorithm as applied to systems in digital communication systems, and speech and character recognition. It also focuses on the operations and the practical memory requirements to implement the Viterbi algorithm in real-time     

一种高速Viterbi译码器的优化设计及Verilog实现

文章设计了一种高速Viterbi译码器，该设计基于卷积码编码及其Viterbi译码原理，完成了Viterhi译码的核心单元算法的优化，并采用Verilog语言编程实现了卷积码编码器和译码器。仿真和综合的结果表明本文设计的译码器速率达50Mbit／s，同时译码器的电路规模也通过算法得到了优化。     

Performance of the Viterbi algorithm for interleaved convolutionalcodes

This paper presents a maximum-likelihood decoder for error-burst channels with a very efficient implementation. In particular, the encoder is formed of an interleaved convolutional code with generator polynomials of the type [g⁽¹⁾(D^I), g⁽²⁾(D^I)] (for a rate 1/2 coder), where I may assume a very high integer value. The decoder consists of the Viterbi algorithm (VA) optimized for these sparse polynomials. For a given decoded bit-error probability, the required delay time and memory requirements of this approach are more inferior by far than those of the traditional method of interleaving. Moreover, for bursts of an average length less than 1/2, this method provides better performance than the dual-mode burst-error-correcting algorithm     

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     

Systolic array processing of the Viterbi algorithm

Results on efficient forms of decoding convolutional codes based on the Viterbi algorithm by using systolic arrays are presented. Various properties of convolutional codes are discussed. A technique called strongly connected trellis decoding is introduced to increase the efficient utilization of all the systolic array processors. Issues dealing with the composite branch metric generation, survivor updating, overall system architecture, throughput rate, and computational overhead ratio are also investigated. The scheme is applicable to both hard and soft decoding of any rate b/n convolutional code. It is shown that as the length of the code becomes large, the systolic Viterbi decoder maintains a regular and general interconnection structure as well as moderate throughput rate gain over the sequential Viterbi decoder     

一种高速Viterbi译码器的设计与实现

Viterbi算法是卷积码的最优译码算法.设计并实现了一种高速(3,1,7)Viterbi译码器,该译码器由分支度量单元(BMU)、加比选单元(ACSU)、幸存路径存储单元(SMU)、控制单元(CU)组成.在StratixⅡ FPGA上实现、验证了该Viterbi译码器.验证结果表明,该译码器数据吞吐率达到231Mbit/s,在加性高斯白噪声(AWGN)信道下的误码率十分接近理论仿真值.与同类型Viterbi译码器比较,该译码器具有高速、硬件实现代价低的特点.