检索结果-内蒙古大学图书馆

Testing reducibility of linear differential operators: A group theoretic perspective

APPLICABLE ALGEBRA IN ENGINEERING COMMUNICATION AND COMPUTING 1996年第2期7卷 77-104页

作者： Singer, MF N CAROLINA STATE UNIV DEPT MATHRALEIGHNC 27695

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.

关键词： linear differential operator factorization berlekamp algorithm differential Galois theory

来源：评论

学校读者我要写书评

暂无评论

New list decoding algorithms for Reed-Solomon and BCH codes

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2008年第8期54卷 3611-3630页

作者： Wu, Yingquan Link A Media Devices Corp Santa Clara CA USA

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)).

关键词： berlekamp algorithm berlekamp-Massey algorithm binary Bose-Chaudhuri-Hocquenghen (BCH) codes Johnson bound list decoding rational curve-fitting algorithm Reed-Solomon codes

来源：评论

学校读者我要写书评

暂无评论

Efficient Sub-Codeword Key Equation Solver for Generalized Integrated Interleaved BCH Decoder

引用

IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS II-EXPRESS BRIEFS 2022年第1期69卷 85-89页

作者： Xie, Zhenshan Zhang, Xinmiao Ohio State Univ Dept Elect & Comp Engn Columbus OH 43210 USA

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)).

关键词： BCH codes berlekamp algorithm generalized integrated interleaved codes key equation solver storage class memories

来源：评论

学校读者我要写书评

暂无评论

New list decoding algorithms for Reed-Solomon and BCH codes

New list decoding algorithms for Reed-Solomon and BCH codes

引用

IEEE International Symposium on Information Theory

作者： Wu, Yingquan Link A Media Devices Corp Santa Clara CA USA

ISBN: (纸本)1424414296

关键词： berlekamp algorithm berlekamp-Massey algorithm binary Bose-Chaudhuri-Hocquenghen (BCH) codes Johnson bound list decoding rational curve-fitting algorithm Reed-Solomon codes

来源：评论

学校读者我要写书评

暂无评论

Interpolation-based Chase BCH Decoder

Interpolation-based Chase BCH Decoder

引用

Information Theory and Applications Workshop (ITA)

作者： Zhang, Xinmiao Case Western Reserve Univ Cleveland OH 44106 USA

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.

关键词： BCH codes codecs interpolation BCH codes berlekamp algorithm Chase BCH decoder Chase BCH decoding schemes flash memory hard-decision decoders hardware complexity interpolation-based decoder multiple test vectors optical communications soft-decision decodes Complexity theory Computer architecture Decoding Interpolation Polynomials Systematics Vectors

来源：评论

学校读者我要写书评

暂无评论

A fast parallel Reed-Solomon decoder on a reconfigurable architecture

A fast parallel Reed-Solomon decoder on a reconfigurable arc...

引用

1st IEEE/ACM/IFIP International Conference on Hardward/Software Codesign and System Synthesis

作者： Koohi, A Bagherzadeh, N Pan, CZ Univ Calif Irvine Dept EECS Irvine CA 92717 USA

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.

关键词： reconfigurable architecture SIMD processor Reed_Solomon codes berlekamp algorithm chein search

来源：评论

学校读者我要写书评

暂无评论

Decoding of Rational Functioned Reed-Solomon Codes

中正岭学报

引用

中正岭学报 2014年第2期43卷 79-88页

作者： Yuan-Wu Ching Ta-Hsiang Hu Feng-Chia Chuang

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.

关键词： RS codes rational function BCH bound berlekamp algorithm Euclidean algorithm RS-like codes

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：