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

2024 Information Theory Workshop

作者： Chen, Chao Tang, Nianqi Han, Yunghsiang S. Bai, Baoming Zhang, Jiefei Zhou, Wenhao Xidian Univ State Key Lab ISN Xian Peoples R China UESTC Shenzhen Inst Adv Study Shenzhen Peoples R China CETC Res Inst 54 Shijiazhuang Hebei Peoples R China

ISBN: (纸本)9798350348941;9798350348934

The berlekamp-massey algorithm is a primary algorithm for decoding Reed-Solomon codes. As an inherent property of the algorithm, the early termination can effectively reduce the latency and power of decoding. It has been known that the algorithm can be terminated at the completion of the (t + )-th iteration (where e is the number of errors and t is the error-correction capability of the code). In this paper, we explore a new mechanism for the early termination. Specifically, assuming e <= t, we present a detection method that can identify the 2e-th iteration. Since the error locator polynomial will have been found at the completion of the 2e-th iteration, we can terminate the algorithm at this point based on the proposed method. As an application, a hardware-friendly algorithm variant, dubbed Reformulated Early-Terminating Parallel Inversionless berlekamp-massey (RETPIBM) algorithm, is presented, which yields a systolic architecture. The derivative architecture consists of 3t + 1 processing elements (PEs) and has the critical path of one multiplier and one adder. To the best of the authors' knowledge, this is literally the first architecture that achieves the early termination for berlekamp-massey algorithm.

关键词： Reed-Solomon code berlekamp-massey algorithm early termination systolic architecture

来源：评论

学校读者我要写书评

暂无评论

algorithm 970: Optimizing the NIST Statistical Test Suite and the berlekamp-massey algorithm

引用

ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE 2017年第3期43卷 27-27页

作者： Sys, Marek Riha, Zdenek Matyas, Vashek Masaryk Univ Fac Informat Ctr Res Cryptog & Secur Bot 68a Brno 60200 Czech Republic

The NIST Statistical Test Suite (NIST STS) is one of the most popular tools for the analysis of randomness. This test battery is widely used, but its implementation is quite inefficient. A complete randomness analysis using the NIST STS can take hours on a standard computer when the tested data volume is on the order of GB. We improved the most time-consuming test (Linear Complexity) from the previous most efficient implementation of the NIST STS. We also optimized other tests and achieved an overall speedup of 50.6x compared with the reference implementation. This means that 20MB of data can be tested within a minute using our new optimized version of the NIST STS. To speed up the Linear Complexity test, we proposed a new version of the berlekamp-massey algorithm that computes only the linear complexity of a sequence. This new variant does not construct a linear feedback shift register and is approximately 187x faster than the original NIST implementation of the berlekamp-massey algorithm.

关键词： berlekamp-massey algorithm NIST STS statistical randomness testing

来源：评论

学校读者我要写书评

暂无评论

New codes for the berlekamp-massey-Sakata algorithm

引用

FINITE FIELDS AND THEIR APPLICATIONS 2001年第2期7卷 293-317页

作者： O'Sullivan, ME Natl Univ Ireland Univ Coll Cork Dept Math Cork Ireland

The key concept for generalizing the berlekamp-massey algorithm is the existence of an order function, a map from a ring to the nonnegative integers which determines a filtration of the ring with one-dimensional quotients. In this article I show that an order function determines a unique valuation on the function field, which has a residue field equal to the base field. The geometry of these valuations for several monomial orderings on a polynomial ring is discussed, and an ordering is constructed which does not correspond to any monomial ordering. The geometric description allows us to define order functions on general surfaces and higher dimensional varieties. (C) 2001 Academic Press.

关键词： algebraic geometry codes berlekamp-massey algorithm order function valution ring

来源：评论

学校读者我要写书评

暂无评论

On the matrix feedback shift register synthesis for matrix sequences

引用

Science China(Information Sciences) 2016年第3期59卷 87-96页

作者： Liping WANG Guang ZENG Institute of Information Engineering Chinese Academy of Sciences Zhengzhou Information Science and Technology Institute

In this paper, a generalization of the linear feedback shift register synthesis problem is presented for synthesizing minimum-length matrix feedback shift registers(MFSRs for short) to generate prescribed matrix sequences and so a new complexity measure, that is, matrix complexity, is introduced. This problem is closely related to the minimal partial realization in linear systems and so can be solved through any minimal partial realization algorithm. All minimum-length MFSRs capable of generating a given matrix sequence with finite length are characterized and a necessary and sufficient condition for the uniqueness issue is obtained. Furthermore, the asymptotic behavior of the matrix complexity profile of random vector sequences is determined.

关键词： berlekamp-massey algorithm minimal partial realization multisequences σ-LFSR

来源：评论

学校读者我要写书评

暂无评论

Comparison of two algorithms for decoding alternant codes

引用

APPLICABLE ALGEBRA IN ENGINEERING COMMUNICATION AND COMPUTING 1998年第3期9卷 211-220页

作者： Fitzpatrick, P Jennings, SM Univ Coll Dept Math Cork Ireland S Bank Univ SCISM London SE1 0AA England

We compare the key equation solving algorithm introduced by Fitzpatrick to the berlekamp-massey algorithm. Our main result is that the two algorithms have the same computational complexity. It follows that in practice Fitzpatrick's algorithm improves on berlekamp-massey since it uses less storage and has a simpler control structure. We also give an improved version of Fitzpatrick's algorithm and a new simplified proof of the central inductive step in the argument.

关键词： decoding alternant codes berlekamp-massey algorithm key equation

来源：评论

学校读者我要写书评

暂无评论

On the annihilator ideal of an inverse form

引用

APPLICABLE ALGEBRA IN ENGINEERING COMMUNICATION AND COMPUTING 2017年第1期28卷 31-78页

作者： Norton, Graham H. Univ Queensland Sch Math & Phys Brisbane Qld 4072 Australia

Let be a field. We simplify and extend work of Althaler and Dur on finite sequences over by regarding as a module and studying forms in from first principles. Then we apply our results to finite sequences. First we define the annihilator ideal of a form of total degree . This is a homogeneous ideal. We inductively construct an ordered pair (, ) of forms in which generate;our generators are special in that z does not divide the leading grlex monomial of but z divides , and the sum of their total degrees is always . The corresponding algorithm is . We prove that the row vector obtained by accumulating intermediate forms of the construction gives a minimal grlex Grobner basis for for no extra computational cost other than storage (this is based on a closed-form description of a 'form vector' for F, an associated vector of total degrees and a syzygy triple derived from the construction. These imply that the remainder of the S polynomial of is zero. Then we inductively apply Buchberger's Criterion to show that the form vector yields a minimal Gb for ). We apply this to determining . We show that either the form vector is reduced or a monomial of can be reduced by . This enables us to efficiently construct the unique reduced Grobner basis for from the vector extension of our algorithm. Then we specialise to the inverse form of a finite sequence, obtaining generator forms for its annihilator ideal and a corresponding algorithm. We compute the intersection of two annihilator ideals using syzygies in . This improves a result of Althaler and Dur. Finally we show that dehomogenisation induces a one-to-one correspondence (,) (minimal polynomial, auxiliary polynomial), the output of the author's variant of the berlekamp-massey algorithm. So we can also solve the LFSR synthesis problem via the corresponding algorithm for sequences.

关键词： Annihilator ideal berlekamp-massey algorithm Grlex monomial order Grobner basis Linear complexity Minimal polynomial Inverse form S polynomial Syzygy

来源：评论

学校读者我要写书评

暂无评论

High-speed architectures for Reed-Solomon decoders

引用

IEEE TRANSACTIONS ON VERY LARGE SCALE INTEGRATION (VLSI) SYSTEMS 2001年第5期9卷 641-655页

作者： Sarwate, DV Shanbhag, NR Univ Illinois Coordinated Sci Lab Urbana IL 61801 USA Univ Illinois Dept Elect & Comp Engn Urbana IL 61801 USA

New high-speed VLSI architectures for decoding Reed-Solomon codes with the berlekamp-massey algorithm are presented in this paper. The speed bottleneck in the berlekamp-massey algorithm is in the iterative computation of discrepancies followed by the updating of the error-locator polynomial. This bottleneck is eliminated via a series of algorithmic. transformations that result in a fully systolic architecture in which a single array of processors computes both the error-locator and the error-evaluator polynomials. In contrast to conventional berlekamp-massey architectures in which the critical path passes through two multipliers and 1 +[log(2) (t + 1)] adders, the critical path in the proposed architecture passes through only one multiplier and one adder, which is comparable to the critical path in architectures based on the extended Euclidean algorithm. More interestingly, the proposed architecture requires approximately 25% fewer multipliers and a simpler control structure than the architectures based on the popular extended Euclidean algorithm. For block-interleaved Reed-Solomon codes, embedding the interleaver memory into the decoder results in a further reduction of the critical path delay to just One XOR gate and one multiplexer, leading to speed ups of as much as an order of magnitude over conventional architectures.

关键词： interleaved codes berlekamp-massey algorithm pipelined decoders Reed-Solomon codes systolic architectures

来源：评论

学校读者我要写书评

暂无评论

Studies on the distribution of the shortest linear recurring sequences

引用

INFORMATION SCIENCES 2009年第14期179卷 2379-2389页

作者： Yin, Qian Yuan, Zhi-Yong Guo, Ping Beijing Normal Univ Image Proc & Pattern Recognit Lab Beijing 100875 Peoples R China Wuhan Univ Sch Comp Sci Wuhan 430079 Peoples R China

The distribution of the shortest linear recurrence (SLR) sequences in the Z/(p) field and over the Z/(p(e)) ring is studied. It is found that the length of the shortest linear recurrent (SLRL) is always equal to n/2, if n is even and n/2 + 1 if n is odd in the Z/(p) field, respectively. On the other hand, over the Z/(p(e)) ring, the number of sequences with length n can also be calculated. The recurring distribution regulation of the shortest linear recurring sequences is also found. To solve the problem of calculating the SLRL, a new simple representation of the berlekamp-massey algorithm is developed as well. (C) 2009 Elsevier Inc. All rights reserved.

关键词： Stream cipher Matrix-representation method berlekamp-massey algorithm Distribution regulation Shortest linear recurring sequences

来源：评论

学校读者我要写书评

暂无评论

ON THE PERFORMANCE AND COMPLEXITY OF A GENERALIZED MINIMUM DISTANCE REED-SOLOMON DECODING algorithm

引用

INTERNATIONAL JOURNAL OF SATELLITE COMMUNICATIONS 1994年第4期12卷 333-359页

作者： PEILE, RE Racal Research Ltd Worton Grange Reading Berkshire RG2 OSB U.K.

The article reports on the characteristics of an algorithm that implements generalized minimum distance (GMD) decoding of Reed-Solomon codes. The algorithm uses the novel Welch-berlekamp (WB) algorithm, as modified by Tze-Hua, in order to minimize the complexity of the decoder. Both the WB algorithm and the GMD extension of the WB algorithm are described in outline. The performance of the GMD algorithm was simulated on AWGN channels and fading channels. Results are presented both for RS and concatenated RS codes. The gains over conventional decoding are larger for fading channels than for AWGN conditions but seem useful in all cases. The complexities of the GMD algorithm and the WB algorithm are analysed and compared to that of conventional RS decoding algorithms.

关键词： ERROR CORRECTION REED-SOLOMON CODES CONCATENATED CODES REED-MULLER CODES DECODING algorithmS GENERALIZED MINIMUM DISTANCE DECODING WELCH-berlekamp algorithm berlekamp-massey algorithm

来源：评论

学校读者我要写书评

暂无评论

GPU-based acceleration of the Linear Complexity Test for random number generator testing

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2019年 128卷 115-125页

作者： Kim, HyungGyoon Cho, Hyungmin Pyo, Changwoo Hongik Univ Dept Comp Engn Wausan Ro 94 Seoul South Korea

The Linear Complexity Test is a statistical test for verifying the randomness of a binary sequence produced by a random number generator (RNG). It is the most time-consuming test in the widely used randomness testing suite that was published by the National Institute of Standards and Technology (NIST). The slow performance of the original Linear Complexity Test implementation is one of the major hurdles in the RNG testing process. In this work, we present a parallelized implementation of the Linear Complexity Test for GPU computation. We incorporate two levels of parallelism and various design optimization approaches to accelerate the test execution on modern GPU architectures. To further enhance the performance, we also create a hybrid computation approach that uses both CPU and GPU simultaneously. We achieve a speedup of more than 4000 times over the original Linear Complexity Test implementation from NIST (27 times over the previous best implementation of the test). (C) 2019 Elsevier Inc. All rights reserved.

关键词： berlekamp-massey algorithm Linear complexity Random number generator Randomness Parallelization GPU

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：