Let k[D] be the ring of differential operators with coefficients in a differential field k. We say that an element L of k[D] is reducible if L = L(1)oL(2) for L(1), L(2) is an element of K[D], L(1), L(2) is not an ele...
详细信息
Let k[D] be the ring of differential operators with coefficients in a differential field k. We say that an element L of k[D] is reducible if L = L(1)oL(2) for L(1), L(2) is an element of K[D], L(1), L(2) is not an element of k. We show that for a certain class of differential operators (completely reducible operators) there exists a berlekamp-style algorithm for factorization. Furthermore, we show that operators outside this class can never be irreducible and give an algorithm to test if an operator belongs to the above class. This yields a new reducibility test for linear differential operators. We also give applications of our algorithm to the question of determining Galois groups of linear differential equations.
In this paper, we devise a rational curve fitting algorithm and apply it to the list decoding of Reed-Solomon and Bose-Chaudhuri-Hocquenghen (BCH) codes. The resulting list decoding algorithms exhibit the following si...
详细信息
In this paper, we devise a rational curve fitting algorithm and apply it to the list decoding of Reed-Solomon and Bose-Chaudhuri-Hocquenghen (BCH) codes. The resulting list decoding algorithms exhibit the following significant properties. The algorithm achieves the limit of list error correction capability (LECC)n(1-root 1-D) for a (generalized) (n, k, d = n-k+1) Reed-Solomon code, which matches the Johnson bound, where D =Delta d/n denotes the normalized minimum distance. The algorithmic complexity is O (n(6)(1-root 1-D)(8)). In comparison with the Guruswami-Sudan algorithm, which exhibits the same LECC, the proposed requires a multiplicity (which dictates the algorithmic complexity) significantly smaller than that of the Guruswami-Sudan algorithm in achieving a given LECC, except for codes with code-rate below 0.15. In particular, for medium-to-high rate codes, the proposed algorithm reduces the multiplicity by orders of magnitude. Moreover, for any epsilon > 0, the intermediate LECC t = left perpendicular 1/epsilon right perpendicular. Its list size is shown to be upper bounded by a constant with respect to a fixed normalized minimum distance D, rendering the algorithmic complexity quadratic in nature, O(n(2)). By utilizing the unique properties of the berlekamp algorithm, the algorithm achieves the LECC limit n/2 (1-root 1 - 2D) for a narrow-sense (n, k, d) binary BCH code, which matches the Johnson bound for binary codes. The algorithmic complexity is O (n(6)(1-root 1-2D)(8)). Moreover, for any epsilon > 0, the intermediate LECC t = left perpendicular epsilon . d/2 + (1 - epsilon) . n-root n(n-2d)/2 right perpendicular can be achieved by the proposed algorithm with multiplicity m = left perpendicular 1/2 epsilon right perpendicular. Its list size is shown to be upper bounded by a constant, rendering the algorithmic complexity quadratic in nature, O(n(2)).
Generalized integrated interleaved (GII) error-correcting codes nest sub-codewords to form codewords of more powerful codes. They can achieve hyper-speed decoding with good error correction capability. For GII codes b...
详细信息
Generalized integrated interleaved (GII) error-correcting codes nest sub-codewords to form codewords of more powerful codes. They can achieve hyper-speed decoding with good error correction capability. For GII codes built on BCH codes, the first decoding stage is to decode individual BCH sub-words. This stage largely determines the throughput and dominates the area of the overall decoder. Unlike that in traditional BCH decoding, longer polynomials need to be kept in the key-equation solver (KES) step of the first stage in order to continue the KES step in the second-stage nested decoding of GII codes. To take advantage of the very fast storage class memories (SCMs), GII codes with 3-error-correcting BCH sub-codewords can be utilized. This brief proposes a low-complexity and high-speed design for the KES of 3-error-correcting BCH sub-word decoding. Formulas are developed to compute the KES results directly instead of utilizing the traditional iterative process. More importantly, through analyzing the properties of the involved variables, the coefficients are scaled and reformulated to substantially reduce the complexity. Detailed hardware implementation architectures are also developed in this brief. Our design achieves three times throughput with 20.2% smaller area than the best prior design for a code over GF(2(10)).
In this paper, we devise a rational curve fitting algorithm and apply it to the list decoding of Reed-Solomon and Bose-Chaudhuri-Hocquenghen (BCH) codes. The resulting list decoding algorithms exhibit the following si...
详细信息
ISBN:
(纸本)1424414296
In this paper, we devise a rational curve fitting algorithm and apply it to the list decoding of Reed-Solomon and Bose-Chaudhuri-Hocquenghen (BCH) codes. The resulting list decoding algorithms exhibit the following significant properties. The algorithm achieves the limit of list error correction capability (LECC)n(1-root 1-D) for a (generalized) (n, k, d = n-k+1) Reed-Solomon code, which matches the Johnson bound, where D =Delta d/n denotes the normalized minimum distance. The algorithmic complexity is O (n(6)(1-root 1-D)(8)). In comparison with the Guruswami-Sudan algorithm, which exhibits the same LECC, the proposed requires a multiplicity (which dictates the algorithmic complexity) significantly smaller than that of the Guruswami-Sudan algorithm in achieving a given LECC, except for codes with code-rate below 0.15. In particular, for medium-to-high rate codes, the proposed algorithm reduces the multiplicity by orders of magnitude. Moreover, for any epsilon > 0, the intermediate LECC t = left perpendicular 1/epsilon right perpendicular. Its list size is shown to be upper bounded by a constant with respect to a fixed normalized minimum distance D, rendering the algorithmic complexity quadratic in nature, O(n(2)). By utilizing the unique properties of the berlekamp algorithm, the algorithm achieves the LECC limit n/2 (1-root 1 - 2D) for a narrow-sense (n, k, d) binary BCH code, which matches the Johnson bound for binary codes. The algorithmic complexity is O (n(6)(1-root 1-2D)(8)). Moreover, for any epsilon > 0, the intermediate LECC t = left perpendicular epsilon . d/2 + (1 - epsilon) . n-root n(n-2d)/2 right perpendicular can be achieved by the proposed algorithm with multiplicity m = left perpendicular 1/2 epsilon right perpendicular. Its list size is shown to be upper bounded by a constant, rendering the algorithmic complexity quadratic in nature, O(n(2)).
BCH codes are adopted in many applications, such as flash memory and optical communications. Compared to harddecision decoders, the soft-decision Chase BCH decoder can achieve significant coding gain by trying multipl...
详细信息
ISBN:
(纸本)9781479935901
BCH codes are adopted in many applications, such as flash memory and optical communications. Compared to harddecision decoders, the soft-decision Chase BCH decoder can achieve significant coding gain by trying multiple test vectors. Previously, one-pass Chase BCH decoding schemes based on the berlekamp's algorithm are used to share intermediate results among the decoding trials. In this paper, it will be shown that the interpolation-based one-pass Chase BCH decoder has much lower hardware complexity. Techniques for simplifying the implementation architecture for each step of the interpolationbased decoder are summarized. For a (4200, 4096) BCH code, the interpolation-based Chase decoder with 16 test vectors has 2.2 times higher hardware efficiency than that based on the berlekamp's algorithm in terms of throughput-over-area ratio.
This paper presents a software implementation of a very fast parallel Reed-Solomon decoder on the second generation of MorphoSys reconfigurable computation platform, which is targeting on streamed applications such as...
详细信息
ISBN:
(纸本)1581137427
This paper presents a software implementation of a very fast parallel Reed-Solomon decoder on the second generation of MorphoSys reconfigurable computation platform, which is targeting on streamed applications such as multimedia and DSP. Numerous modifications of the first-generation of the architecture have made a scalable computation and communication intensive architecture capable of extracting parallelisms of fine grain in instruction level. Many algorithms and the whole Digital Video Broadcasting base-band receiver as well, have been mapped onto the second architecture with impressing performance. The mapping of a Reed-Solomon decoder proposed in this paper highly parallelizes all of its sub-algorithms, including Syndrome Computation. berlekamp algorithm, Chem Search, and Error Value Computation, in a SIMD fashion. The mapping is tested on a cycle-accurate simulator, "Mulate", and the performance is encouragingly better than other architectures. The decoding speed of the RS (255,239,16) decoder using two different methods of GF multiplication can be 1.319Gbps and 2.534Gbps, respectively. Furthermore, since there is no functionality specifically tailored to Reed-Solomon decoder, the result has demonstrated the capability of MorphoSys architecture to extracting Instruction Level Parallelism from streamed applications.
A new modification on Reed-Solomon (RS) codes is proposed. The modification is based on a connection ofroots of a generator polynomial of an RS code and a rational function. In such a way, the roots of such an RS-like...
详细信息
A new modification on Reed-Solomon (RS) codes is proposed. The modification is based on a connection ofroots of a generator polynomial of an RS code and a rational function. In such a way, the roots of such an RS-like code are no more consecutive, which is contradicted to the conventional RS encoding. By properselection of a rational function, the error correction capacityof such RS-like codes still possesses the same capability as that of original RS codes. Error decoding is proposed for such RS-like codes based on modified berlekampiterative algorithm (BIA) with less decoding complexity than extended Euclidean algorithm (EEA).From the theoretical proof and computer simulations of 105to decode RS(255,239,t=8) code, decoding complexity of BIA does be less than that of EEA by decreasing about one-third of complexity as EEA employed. Preciselyspeaking, this proposed decoding algorithm contains all processes in BIA but with an extra step to find exact error locator numbers. The main contribution of this work is to propose a way to determine rational functions such that theserational functioned RS codes, which are RS-like codes and called in this work, still have the same error correction capability and employ BIA for decoding as RS codes do.
暂无评论