In this paper, a new list decoding algorithm for tail-biting convolutional codes (TBCCs) with a cyclic redundancy check (CRC) is proposed, where the CRC is considered as a concatenated outer code. The main idea of the...
详细信息
In this paper, a new list decoding algorithm for tail-biting convolutional codes (TBCCs) with a cyclic redundancy check (CRC) is proposed, where the CRC is considered as a concatenated outer code. The main idea of the proposed algorithm is to modify the listdecoding procedure of the TBCC by using the CRC. Two algorithms are proposed for the listdecoding of the TBCC with the CRC. The first proposed algorithm is a new initial state estimating algorithm using re-encoded CRC bits and having the low computational complexity. The other proposed algorithm is a modified list Viterbi algorithm, where trellis paths are fixed by re-encoded CRC bits and some CRC bits are used for the error correction. For the TBCC concatenated with the CRC code defined in the long-term evolution standard, the proposed decoding scheme by partially using CRC bits outperforms the conventional list decoding algorithms for the list size L = 4 even though the proposed algorithm has the lower decoding complexity.
Polar codes are of great interests because they provably achieve the symmetric capacity of discrete memoryless channels with arbitrary input alphabet sizes while having an explicit construction. Most existing decoding...
详细信息
Polar codes are of great interests because they provably achieve the symmetric capacity of discrete memoryless channels with arbitrary input alphabet sizes while having an explicit construction. Most existing decodingalgorithms of polar codes are based on bit-wise hard or soft decisions. In this paper, we propose symbol-decision successive cancellation (SC) and successive cancellation list (SCL) decoders for polar codes, which use symbol-wise hard or soft decisions for higher throughput or better error performance. First, we propose to use a recursive channel combination to calculate symbol-wise channel transition probabilities, which lead to symbol decisions. Our proposed recursive channel combination has lower complexity than simply combining bit-wise channel transition probabilities. The similarity between our proposed method and Arikan's channel transformations also helps to share hardware resources between calculating bit-and symbol-wise channel transition probabilities. Second, a two-stage list pruning network is proposed to provide a trade-off between the error performance and the complexity of the symbol-decision SCL decoder. Third, since memory is a significant part of SCL decoders, we propose a pre-computation memory-saving technique to reduce memory requirement of an SCL decoder. Finally, to evaluate the throughput advantage of our symbol-decision decoders, we design an architecture based on a semi-parallel successive cancellation list decoder. In this architecture, different symbol sizes, sorting implementations, and message scheduling schemes are considered. Our synthesis results show that in terms of area efficiency, our symbol-decision SCL decoders outperform existing bit-decision and multi-bit SCL decoders.
A list decoding algorithm for iterative soft-decision decoding of Reed-Solomon (RS) codes is proposed in this study. The algorithm erases a combination of least reliable symbols and iteratively flips a new combination...
详细信息
A list decoding algorithm for iterative soft-decision decoding of Reed-Solomon (RS) codes is proposed in this study. The algorithm erases a combination of least reliable symbols and iteratively flips a new combination of least reliable bits in the received sequence. The symbol error correction capability of the algebraic hard decision RS decoder is extended up to the minimum Hamming distance of the code. A gain in performance is exhibited either at a lower or similar iteration complexity as compared to other iterative soft decision decoders of similar type. A complexity comparison with some of the comparable soft decision decoders is given. Simulation results for different modulation schemes and channel types are presented in this study for a comparison with other soft decision decoders of a similar kind.
We tighten a key estimate, which dictates the computational complexity of Guruswami-Sudan algorithm, on the lower bound of the degrees of freedom, and then propose a modified decodingalgorithm for Reed-Solomon codes ...
详细信息
We tighten a key estimate, which dictates the computational complexity of Guruswami-Sudan algorithm, on the lower bound of the degrees of freedom, and then propose a modified decodingalgorithm for Reed-Solomon codes beyond half the minimum distance. The computational complexity of the modified algorithm is lower than the Guruswami-Sudan algorithm for the medium to high rate Reed-Solomon codes, and has the same asymptotic complexity as the algorithm proposed by Wu. Besides we also claim that our modified algorithm outperforms Wu's algorithm to some extent. (C) 2010 Elsevier By. All rights reserved.
For an error-correcting code and a distance bound, the listdecoding problem is to compute all the codewords within a given distance to a received message. The bounded distance decoding problem is to find one codeword...
详细信息
For an error-correcting code and a distance bound, the listdecoding problem is to compute all the codewords within a given distance to a received message. The bounded distance decoding problem is to find one codeword if there is at least one codeword within the given distance, or to output the empty set if there is not. Obviously the bounded distance decoding problem is not as hard as the listdecoding problem. For a Reed-Solomon code [n, k](q), a simple counting argument shows that for any integer 0 < g < n, there exists at least one Hamming ball of radius n-g, which contains at least ((n)(g))/q(g-k) many codewords. Let (g) over cap (n, k, q) be the smallest positive integer g such that (g(n))/q(g-k) <= 1. One knows that k - 1 <= (g) over bar (n, k, q) <= root n(k-1) <= n. For the distance bound up to n - root n(k - 1), it is known that both the list and bounded distance decoding can be solved e. ciently. For the distance bound between n- root n(k - 1) and n-(g) over bar (n, k, q), we do not know whether the Reed - Solomon code is list or bounded distance decodable;nor do we know whether there are polynomially many codewords in all balls of the radius. It is generally believed that the answer to both questions is no. In this paper, we prove the following: ( 1) listdecoding cannot be done for radius n-(g) over cap (n, k, q) or larger, unless the discrete logarithm over F-q (g) double under bar (n,F- k,F- q)- k is easy. (2) Let h and g be positive integers satisfying q >= max(g(2), (h - 1)(2+is an element of)) and g = (4/is an element of + 2)(h+1) for a constant is an element of > 0. We show that the discrete logarithm problem over F-q(h) can be e. ciently reduced by a randomized algorithm to the bounded distance decoding problem of the Reed-Solomon code [q, g-h](q) with radius q - g. These results show that the decoding problems for the Reed-Solomon code are at least as hard as the discrete logarithm problem over certain finite fields. For the listdecoding proble
For an error-correcting code and a distance bound, the listdecoding problem is to compute all the codewords within a given distance to a received message. The bounded distance decoding problem is to find one codeword...
详细信息
For an error-correcting code and a distance bound, the listdecoding problem is to compute all the codewords within a given distance to a received message. The bounded distance decoding problem is to find one codeword if there is at least one codeword within the given distance, or to output the empty set if there is not. Obviously the bounded distance decoding problem is not as hard as the listdecoding problem. For a Reed-Solomon code [n, k](q), a simple counting argument shows that for any integer 0 < g < n, there exists at least one Hamming ball of radius n-g, which contains at least ((n)(g))/q(g-k) many codewords. Let (g) over cap (n, k, q) be the smallest positive integer g such that (g(n))/q(g-k) <= 1. One knows that k - 1 <= (g) over bar (n, k, q) <= root n(k-1) <= n. For the distance bound up to n - root n(k - 1), it is known that both the list and bounded distance decoding can be solved e. ciently. For the distance bound between n- root n(k - 1) and n-(g) over bar (n, k, q), we do not know whether the Reed - Solomon code is list or bounded distance decodable;nor do we know whether there are polynomially many codewords in all balls of the radius. It is generally believed that the answer to both questions is no. In this paper, we prove the following: ( 1) listdecoding cannot be done for radius n-(g) over cap (n, k, q) or larger, unless the discrete logarithm over F-q (g) double under bar (n,F- k,F- q)- k is easy. (2) Let h and g be positive integers satisfying q >= max(g(2), (h - 1)(2+is an element of)) and g = (4/is an element of + 2)(h+1) for a constant is an element of > 0. We show that the discrete logarithm problem over F-q(h) can be e. ciently reduced by a randomized algorithm to the bounded distance decoding problem of the Reed-Solomon code [q, g-h](q) with radius q - g. These results show that the decoding problems for the Reed-Solomon code are at least as hard as the discrete logarithm problem over certain finite fields. For the listdecoding proble
Traitor tracing is one kind of piracy deterrent schemes that helps trace the source of leaks when sensitive or proprietary data is made available to a large set of *** their natural properties,error correcting codes c...
详细信息
ISBN:
(纸本)0780397371
Traitor tracing is one kind of piracy deterrent schemes that helps trace the source of leaks when sensitive or proprietary data is made available to a large set of *** their natural properties,error correcting codes can be applied as traceability codes in such *** this paper,we present ReedSolomon codes as a kind of traceability codes and use list decoding algorithm to efficiently trace the traitors. We emphasize the conditions under which list decoding algorithm can be applied successfully for Reed-Solomon codes and the maximum numbers of users and traceable traitors for particular codes.
暂无评论