The Berlekamp-Massey algorithm revisited

被引：21

作者：

Atti, NB ^{[1
]}

Diaz-Toca, GM

Lombardi, H

机构：

[1] Univ Murcia, Dept Matemat Aplicada, E-30001 Murcia, Spain

[2] Univ Franche Comte, CNRS, Equipe Math,UMR 6623, UFR Sci & Tech, F-25030 Besancon, France

来源：

APPLICABLE ALGEBRA IN ENGINEERING COMMUNICATION AND COMPUTING | 2006年 / 17卷 / 01期

关键词：

Berlekamp-Massey algorithm; linearly recurrent sequences;

D O I：

10.1007/s00200-005-0190-z

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

We propose a slight modification of the Berlekamp-Massey Algorithm for obtaining the minimal polynomial of a given linearly recurrent sequence. Such a modification enables to explain it in a simpler way and to adapt it to lazy evaluation.

引用

页码：75 / 82

页数：8

共 10 条

[1]

Berlekamp E. R., 1968, ALGEBRAIC CODING THE

[2]

CHENG U, 1984, IEEE T INFORM THEORY, V30, P541, DOI 10.1109/TIT.1984.1056906

[3] ON THE EQUIVALENCE BETWEEN BERLEKAMP AND EUCLIDS ALGORITHMS [J].

DORNSTETTER, JL .

IEEE TRANSACTIONS ON INFORMATION THEORY, 1987, 33 (03) :428-431

[4] A SIMPLE HANKEL INTERPRETATION OF THE BERLEKAMP-MASSEY ALGORITHM [J].

JONCKHEERE, E ;

MA, CW .

LINEAR ALGEBRA AND ITS APPLICATIONS, 1989, 125 :65-76

[5]

MASSEY JL, 1969, IEEE T INFORM THEORY, V15, P122, DOI 10.1109/TIT.1969.1054260

[6]

MILLS WH, 1975, MATH COMPUT, V29, P173, DOI 10.1090/S0025-5718-1975-0369276-7

[7] New techniques for the computation of linear recurrence coefficients [J].

Pan, VY .

FINITE FIELDS AND THEIR APPLICATIONS, 2000, 6 (01) :93-118

[8]

Shoup V., 2005, COMPUTATIONAL INTRO

[9] METHOD FOR SOLVING KEY EQUATION FOR DECODING GOPPA CODES [J].

SUGIYAMA, Y ;

KASAHARA, M ;

HIRASAWA, S ;

NAMEKAWA, T .

INFORMATION AND CONTROL, 1975, 27 (01) :87-99

[10]

WELCH LR, 1979, IEEE T INFORM THEORY, V25, P18

← 1 →