It is well-known that the computational complexity of the Viterbi decoding algorithm for an (n, k, V) convolutional code grows exponentially with k and the code memory v, and thus it becomes quickly impractical as the...
详细信息
It is well-known that the computational complexity of the Viterbi decoding algorithm for an (n, k, V) convolutional code grows exponentially with k and the code memory v, and thus it becomes quickly impractical as the code rate increases. A solution, so far, has been to use punctured convolutional codes, which strongly reduces the decoding complexity but leads to a slightly worse performance. Recently, it has been pointed out that every non-punctured high-rate convolutional code (with 2(k) > 2(v)) can be viewed as the concatenation of a block code and a simpler convolutional code. In this paper, we exploit this property of high-rate codes to facilitate the implementation of the Viterbi algorithm. We propose a modification of the Viterbi decoding algorithm for non-punctured high-rate convolutional codes which results in very significant computational savings. Copyright (c) 2005 AEIT.
A major challenge in the area of the space time codes is to find codes suitable for efficient decoding, thus overcoming the problem of many existing space time code designs which require maximum-likelihood (NIL) decod...
详细信息
ISBN:
(纸本)0780389662
A major challenge in the area of the space time codes is to find codes suitable for efficient decoding, thus overcoming the problem of many existing space time code designs which require maximum-likelihood (NIL) decoding. A solution could be to apply Single-Input Single-Output (SISO) channel codes and theory over temporal channel fading to the Multi-Input Single-Output (MISO) code construction and classical suboptimum decoding methods. For these purposes, a space time code construction which allows the use of efficient decoding algorithms is described. We propose a concatenated code, where the inner code is the diagonal space time Hadamard (D-STH) code [11 [21 with Paley constructions and the outer code is an algebraic block code, such as a Reed-Solomon (RS) code. Our perspective is different than most existing concatenation type schemes, which destroy the inter-dependence of the outer channel code and the inner space time code by using an interleaver. As decoding method, we investigate bounded minimum distance (BMD) with erasure decoding algorithm. A simple method to achieve the optimum threshold for deciding on an erased symbol will be derived. Using that, the proposed concatenated scheme is able to exploit almost all of the spatial diversity of the system.
Channel coding always plays an important role In communication systems. decoding complexity is one factor which needs to be considered in its implementation. In this paper the decoding algorithm for MTCM is studied. V...
详细信息
ISBN:
(纸本)9781424421077
Channel coding always plays an important role In communication systems. decoding complexity is one factor which needs to be considered in its implementation. In this paper the decoding algorithm for MTCM is studied. Viterbi decoding algorithm for MTCM contains much more computations per trellis state transition. A most applicable decoding scheme for MTCM Is proposed, which can achieve reduced computational complexity. The BER performance can approach that of the maximum likelihood decoding algorithm quickly by increasing the value of one parameter of MTCM.
The complexity of Viterbi decoding algorithm will increase exponentially to the constraint length of convolutional codes by index and the decoding delay is too large. So it only adapts to the decoding of shorter const...
详细信息
ISBN:
(纸本)9780769533049
The complexity of Viterbi decoding algorithm will increase exponentially to the constraint length of convolutional codes by index and the decoding delay is too large. So it only adapts to the decoding of shorter constraint length convolutional codes. Aiming at these shortcomings, this paper presents fast decoding of convolutional codes, which are based on particle swarm optimization (PSO) algorithm. The algorithm decides the number of decoding paths by setting up the population size M. So it could reduce the searching area in the trellis of decoding and shorten the decoding delay, thereby more adapts to longer constraint length convolutional codes. The simulation results show that the proposed algorithm reduce the bit error rate (BER) and the decoding time.
We present a two stage automatic speech recognition architecture suited for applications, such as spoken document retrieval, where large scale language models can be used and very low out-of-vocabulary rates need to b...
详细信息
ISBN:
(纸本)9781615673780
We present a two stage automatic speech recognition architecture suited for applications, such as spoken document retrieval, where large scale language models can be used and very low out-of-vocabulary rates need to be reached. The proposed system couples a weakly constrained phone-recognizer with a phone-to-word decoder that was originally developed for phrase-based statistical machine translation. The decoder permits to efficiently decode confusion networks in input, and to exploit large scale unpruned language models. Preliminary experiments are reported on the transcription of speeches of the Italian parliament. The use of phone confusion networks as interface between the two decoding steps permits to reduce the WER by 28%, thus making the system perform relatively close to a state-of-the-art baseline using a comparable language model.
In this paper we propose algorithms which combine Belief-propagation (BP) decoding algorithm with Genetic algorithm (GA). The main idea is to improve the performance of traditional BP decoding algorithm by efficiently...
详细信息
ISBN:
(纸本)9781424441969
In this paper we propose algorithms which combine Belief-propagation (BP) decoding algorithm with Genetic algorithm (GA). The main idea is to improve the performance of traditional BP decoding algorithm by efficiently using the belief of variable nodes passing to check nodes. By considering the belief as genes, the proposed algorithms mainly employ the mutation operation in GA, and change the genes' amplitudes (either increase or decrease) when updating the check nodes' information. First, we explore that the marriage of the GA and BP decoding algorithm is reasonable. Three algorithms are proposed accordingly. Proposed algorithm I mutates chosen genes by amplitude enhancement, while proposed algorithm II by amplitude reduction. Finally, proposed algorithm III is a mixture of the former two. From computer simulation results, we show that for short and middle length LDPC codes, our proposed algorithms can improve both BER (Bit Error Rate) and FER (Frame Error Rate) performance over traditional BP decoding algorithm, with slight modification of traditional BP decoding algorithm and little increase of computation complexity.
In this article, the main point is to describe the fast decoding algorithm of [256,252] RS extended code. In order to correct the error in the received data quickly, the algorithm gets the error type and error pattern...
详细信息
In this article, the main point is to describe the fast decoding algorithm of [256,252] RS extended code. In order to correct the error in the received data quickly, the algorithm gets the error type and error pattern through simple parameter-comparison, then adds the error pattern to the receive data. Compared to the algorithms in existence, this algorithm has the advantages of using less hardware resources and decoding time. When this algorithm implements in hardware, its throughput is more than 400Mbit/s.
The t-error-correcting Reed-Solomon (RS) code can detect more than t errors with high probability [1]. Welch-Berlekamp (WB) algorithm is known as a decoding algorithm for RS codes [2] [3], and it can solved the remain...
详细信息
ISBN:
(纸本)9781424420681
The t-error-correcting Reed-Solomon (RS) code can detect more than t errors with high probability [1]. Welch-Berlekamp (WB) algorithm is known as a decoding algorithm for RS codes [2] [3], and it can solved the remainder key-equation. We have shown the condition for detecting the (t+μ)-error of RS code by WB algorithm [4]. In this paper, we show a error locator polynomial for correctable (t+1)-error of RS codes.
Channel coding always plays an important role in communication systems. decoding complexity is one factor which needs to be considered in its implementation. In this paper the decoding algorithm for MTCM is studied. V...
详细信息
Channel coding always plays an important role in communication systems. decoding complexity is one factor which needs to be considered in its implementation. In this paper the decoding algorithm for MTCM is studied. Viterbi decoding algorithm for MTCM contains much more computations per trellis state transition. A most applicable decoding scheme for MTCM is proposed, which can achieve reduced computational complexity. The BER performance can approach that of the maximum likelihood decoding algorithm quickly by increasing the value of one parameter of MTCM.
The classical Direct-Product Theorem for circuits says that if a Boolean function f : {0, l}~n→ {0,1} is somewhat hard to compute on average by small circuits, then the corresponding kwise direct product function f~k...
详细信息
ISBN:
(纸本)9781605604657
The classical Direct-Product Theorem for circuits says that if a Boolean function f : {0, l}~n→ {0,1} is somewhat hard to compute on average by small circuits, then the corresponding kwise direct product function f~k (x_1;...,x_k) = (f(s_1),...,f(x_k)) (where each x_i ∈ {0, l}~n) is significantly harder to compute on average by slightly smaller circuits. We prove a fully uniform version of the Direct-Product Theorem with information-theoretically optimal parameters, up to constant factors. Namely, we show that for given k and ε, there is an efficient randomized algorithm A with the following property. Given a circuit C that computes f~k on at least ε fraction of inputs, the algorithm A outputs with probability at least 3/4 a list of 0(1/ε) circuits such that at least one of the circuits on the list computes f on more than 1 - δ fraction of inputs, for δ = O((log1/ε)/k). Moreover, each output circuit is an AC~0 circuit (of size poly(n, k, log 1/δ,1/ε)), with oracle access to the circuit C. Using the Goldreich-Levin decoding algorithm [5], we also get a fully uniform version of Yao's XOR Lemma [18] with optimal parameters, up to constant factors. Our results simplify and improve those in [10]. Our main result may be viewed as an efficient approximate, local, list-decoding algorithm for direct-product codes (encoding a function by its values on all k-tuples) with optimal parameters. We generalize it to a family of "derandomized" direct-product codes, which we call intersection codes, where the encoding provides values of the function only on a subfamily of k-tuples. The quality of the decoding algorithm is then determined by sampling properties of the sets in this family and their intersections. As a direct consequence of this generalization we obtain the first derandomized direct product result in the uniform setting, allowing hardness amplification with only constant (as opposed to a factor of k) increase in the input length. Finally, this general setting naturally a
暂无评论