Chachlakis Dimitrios, Χαχλακης Δημητριος · Technical University of Crete · 2016
In this diploma thesis, we study the problem of optimal noncoherent trellis decoding, that is, the maximization of |s(x)^H y| over x, where y is a complex vector, x is a discrete symbol sequence, and s(x) is a vector that is produced by x through a trellis structure. Two example cases of noncoherent trellis decoding are noncoherent detection of a minimum-shift keying (MSK) modulated sequence and noncoherent decoding of convolutionally encoded data. Specifically, MSK is a modulation scheme that limits problems associated with nonlinear distortion and is used in a variety of applications, like signal transmission from satellites and broadcasting. Although the optimal coherent MSK receiver simplifies to constant-complexity symbol-bysymbol detection, optimal noncoherent reception of MSK takes the form of sequence detection (due to channel-induced memory) which has exponential (in the sequence length) complexity when implemented through an exhaustive search among all possible sequences. Convolutional codes are used extensively to achieve reliable data transfer in numerous applications, such as digital video, radio, and satellite communications. They are modeled by a trellis structure and optimal noncoherent reception of convolutionally encoded data also takes the form of sequence detection. In this work, we present an algorithm that performs generalized-likelihood-ratio-test (GLRT) optimal noncoherent sequence detection of MSK signals in flat fading with log-linear (in the sequence length) complexity. Moreover, for Rayleigh fading channels, the proposed algorithm is equivalent to the maximum-likelihood (ML) noncoherent sequence detector. We then discuss how the proposed algorithm can be generalized for use on noncoherent convolutional decoding. To simplify the presentation, we consider a particular convolutional code and modify the proposed algorithm to perform optimal noncoherent trellis decoding with empirically low complexity. Simulation studies indicate that the optimal noncoherent MSK detector attains coherent-detection performance when the sequence length is on the order of 100, offering a 5–6 dB gain over the typical single-symbol detector. Similar results are obtained for the generalized algorithm on convolutional decoding.
Cited by 0Open access
Honary, Bahram, Markarian, Garik, Darnell, Mike · Lancaster EPrints (Lancaster University) · 1993
Cited by 0
Torbjörn Larsson · 2002
A novel reduced-complexity trellis decoding algorithm is described. The new algorithm, called wavefront decoding (WD), avoids the throughput bottleneck caused by metric and state-information feedback, which characterizes previously known breadth-first decoding algorithms. The error performance of WD for trellis-coded 8PSK on AWGN and Rayleigh fading channels is investigated by simulation. The results indicate that for a given number of survivor paths, the performance of WD is comparable, although necessarily inferior, to that of the M-algorithm, However, in contrast to the M-algorithm, WD exhibits a high degree of temporal parallelism, rendering it suitable for high speed applications.
Cited by 0
Kasra Vakilinia, T. Chen, D. Divsalar et al. · 2012
Cited by 0
Kaya, L · OpenGrey (Institut de l'Information Scientifique et Technique) · 1993
Cited by 0Open access
Gökmen Altay, Ş. Yalçın, Osman N. Uçan · 2003
This paper presents a maximum likelihood (ML) soft decision decoding scheme to implement Viterbi Algorithm for some constructed decomposable codes of Hamming distance four and show that the decoding complexity is simple, hence, it may be employed in trellis - based decoders. Bit error rate performances of some decomposable codes that were obtained employing the technique in AWGN channel are also presented.
Cited by 1
Garik Markarian, Bahram Honary · Lancaster EPrints (Lancaster University) · 1995
Cited by 0
Bahram Honary, Garik Markarian · 1997
Cited by 0
Garik Markarian, Honary, Bahram, K. S. Soyjaudah · Lancaster EPrints (Lancaster University) · 1993
Cited by 1
L. Palacios, R.M. Edwards, Bahram Honary · Lancaster EPrints (Lancaster University) · 2001
Cited by 0
J.J. Kosmach, Stephen B. Wicker · 2003
An improved two-stage trellis decoder for Reed-Solomon (RS) codes is presented. This decoder uses reliability information as a basis for reordering the symbols in the received word. The coset trellis for the resulting code has the same structure and complexity as the standard two-stage trellis decoder, but an efficient means can now be implemented for the selection of the sub-trellis that contains the best path prior to decoding. Simulation results for the RS(7, 3) code are presented for AWGN and Rayleigh fading channels.
Cited by 1
Banihashemi, Amir H. · UWSpace (University of Waterloo) · 1997
Decoding operation i s the major obstacle associated with using a lat tice in communication applications.There are two general methods for lattice decoding: i) The integer programming method based on geometry of numbers, and ii) The trellis method.This thesis has contributions to both methods, and provides results which make the cornparison between the two methods possible-Regarding method (i), Kannan's algorithrn, which is currently known as the fastest methad for the decoding of a general lattice, is analyzed.Based on a geometrical interpretation of this algorithm, it is shown that it i s a specid case of a wider category of algorithms?called recursive cube search (RCS) algorithms.In this category, we improve Kaman's algorithm, and establish tight upper and lower bounds on the decoding complexity of lattices.The lower bounds prove that the 1 would like to appreciate the valuable efforts of Dr.
Cited by 3Open access
Garik Markarian, Bahram Honary · Lancaster EPrints (Lancaster University) · 1998
Cited by 0
Jens Berkmann, C. Weiss · IEEE Transactions on Communications · 2002
The trellis of a finite Abelian group code is locally (i.e., trellis section by trellis section) related to the trellis of the corresponding dual group code which allows one to express the basic operations of the a posteriori probability (APP) decoding algorithm (defined on a single trellis section of the primal trellis) in terms of the corresponding dual trellis section. Using this local approach, any algorithm employing the same type of operations as the APP algorithm can, thus, be dualized, even if the global dual code does not exist (e.g., nongroup codes represented by a group trellis). Given this, the complexity advantage of the dual approach for high-rate codes can be generalized to a broader class of APP decoding algorithms, including suboptimum algorithms approximating the true APP, which may be more attractive in practical applications due to their reduced complexity. Moreover, the local approach opens the way for mixed approaches where the operations of the APP algorithm are not exclusively performed on the primal or dual trellis. This is inevitable if the code does not possess a trellis consisting solely of group trellis sections as, e.g., for certain terminated group or ring codes. The complexity reduction offered by applying dualization is evaluated. As examples, we give a dual implementation of a suboptimum APP decoding algorithm for tailbiting convolutional codes, as well as dual implementations of APP algorithms of the sliding-window type. Moreover, we evaluate their performance for decoding usual tailbiting codes or convolutional codes, respectively, as well as their performance as component decoders in iteratively decoded parallel concatenated schemes.
Cited by 26
G. Hellstern · 2002
It has previously been shown that with trellis-coded modulation it is possible to achieve a significant coding gain of 3 to 6 dB over uncoded modulation without bandwidth expansion. However, the decoding effort grows rapidly with the coding gain. A different approach is given by the author. Based on a feedback decoding scheme, trellis codes of large constraint length are proposed which can be easily decoded. At similar decoder complexity, but at a larger decoding delay, they attain additional coding gain over conventional trellis codes.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>
Cited by 11
Ian F. Blake, Amirhossein Banihashemi · 1997
Decoding operation is the major obstacle associated with using a lattice in communication applications. There are two general methods for lattice decoding: (i) The integer programming method based on geometry of numbers, and (ii) The trellis method. This thesis has contributions to both methods, and provides results which make the comparison between the two methods possible.
Regarding method (i), Kannan's algorithm, which is currently known as the fastest method for the decoding of a general lattice, is analyzed. Based on a geometrical interpretation of this algorithm, it is shown that it is a special case of a wider category of algorithms, called recursive cube search (RCS) algorithms. In this category, we improve Kannan's algorithm, and establish tight upper and lower bounds on the decoding complexity of lattices. The lower bounds prove that the RCS decoding complexity of any sequence of lattices with possible application in communications increases at least exponentially with dimension and coding gain.
Regarding method (ii), we discuss and develop a universal approach to the construction and analysis of the trellis diagrams of lattices using their bases. Based on this approach, we derive tight upper bounds on the trellis complexity of lattices, and study the problem of finding minimal trellis diagrams for lattices. The upper bounds both improve and generalize the previously known similar results. Minimal trellis diagrams for many important lattices are also constructed. These trellises, which are novel in many cases, can be employed to efficiently decode the lattices via the Viterbi algorithm. Moreover, we establish tight lower bounds on the trellis complexity of lattices. For many of the obtained trellises, these lower bounds provide a proof for minimality.
Finally, we derive some results in lattice theory with possible application in communications. These include an upper bound on covering radius of a lattice in terms of its successive minima, and an inequality on the coding gain of densest lattice packings in successive dimensions.
Cited by 7
Fu-Quan Wang, Daniel J. Costello · IEEE Transactions on Information Theory · 1994
An erasure-free sequential decoding algorithm for trellis codes, called the buffer looking algorithm (BLA), is introduced. Several versions of the algorithm can be obtained by choosing certain parameters and selecting a resynchronization scheme. These can be categorized as block decoding or continuous decoding, depending on the resynchronization scheme. Block decoding is guaranteed to resynchronize at the beginning of each block, but suffers some rate loss when the block length is relatively short. The performance of a typical block decoding scheme is analyzed, and we show that significant coding gains over Viterbi decoding can be achieved with much less computational effort. A resynchronization scheme is proposed for continuous sequential decoding. It is shown by analysis and simulation that continuous sequential decoding using this scheme has a high probability of resynchronizing successfully. This new resynchronization scheme solves the rate loss problem resulting from block decoding. The channel cutoff rate, demodulator quantization, and the tail's influence on performance are also discussed. Although this paper considers only the decoding of trellis codes, the algorithm can also be applied to the decoding of convolutional codes.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>
Cited by 13
Peter Trifonov · 2020
Recursive trellis decoding of polar codes is considered. Polar codes are shown to have much lower recursive trellis decoding complexity compared to similar Reed-Muller codes. Furthermore, a low-latency decoding algorithm, which combines recursive trellis and successive cancellation decoding methods, is presented.
Cited by 5
S.J. Simmons · IEEE Transactions on Communications · 1990
A breadth-first trellis decoding algorithm is introduced for application to sequence estimation in digital data transmission. The high degree of inherent parallelism makes a parallel-processing implementation attractive. The algorithm is shown to exhibit an error-rate versus average-computational-complexity behavior that is much superior to the Viterbi algorithm and also improves on the M-algorithm. The decoding algorithm maintains a variable number of paths as its computation adapts to the channel noise actually encountered. Buffering of received samples is required to support this. Bounds that are evaluated by trellis search are produced for the error event rate and average number of survivors. Performance is evaluated with conventional binary convolutional codes over both binary-synchronous-communication (BSC) and additive-white-Gaussian-noise (AWGN) channels. Performance is also found for multilevel AM and phase-shift-keying (PSK) codes and simple intersymbol interference responses over an AWGN channel. At lower signal-to-noise ratio Monte Carlo simulations are used to improve on the bounds and to investigate decoder dynamics.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>
Cited by 259
Matthias Kamuf · Lund University Publications (Lund University) · 2007
Trellis decoding is a popular method to recover encoded information corrupted during transmission over a noisy channel. Prominent members of this class of decoding algorithms are the Viterbi algorithm, which provides maximum likelihood estimates, and the BCJR algorithm, which is a maximum a posteriori estimator commonly used in iterative decoding. In this thesis, the Viterbi algorithm is chosen since it provides a good trade-off between achievable coding gain and implementation complexity. This is the basis for considerations on simplified, hybrid, and, most importantly, flexible VLSI architectures. Algorithm simplifications are necessary to reduce the computational burden laid on an implementation platform. In our work on trellis decoding blocks, a simplification that lowers the number of arithmetic operations is derived and evaluated. By using a complementary code property, the arithmetic complexity of the main part on the Viterbi algorithm is reduced by 17%. Synthesized blocks show varying savings for cell area and estimated power consumption. A comparison to a competing simplification shows the advantage in a hardware implementation of our work for the important class of rate 1/2 convolutional codes. Hybrid architectures try to combine benefits of several approaches to lower the drawbacks of the individual contributors. For survivor path processing in Viterbi decoders, a new hybrid approach is proposed. A low-latency algorithm, whose implementation complexity quickly increases with the number of trellis states, is combined with a scalable RAM-based method. As a result, the developed hybrid architecture exhibits a better latency-complexity behavior compared to other hybrid approaches. Flexible VLSI architectures to cover several communication standards become increasingly important as fabrication costs for microchips rise rapidly with every new process generation. In the context of flexible trellis decoding, earlier work mostly concentrated on varying encoder memory and thus the number of trellis states. This work studies the effects on hardware size and throughput introduced by flexibility if the code rate is varied. The investigation of a decoder for bandwidth-efficient codes, which was fabricated in a 0.13 um digital CMOS process and verified for functionality, distinguishes between task- and rate-flexibility. A comparison is carried out between flexible designs, which decode both convolutional and TCM codes and provide two or three transmission rates. It is concluded that the larger number of rates is more beneficial from a cost--flexibility viewpoint.
Cited by 4