请输入您要查询的字词:

 

单词 BerlekampMasseyAlgorithm
释义

Berlekamp-Massey algorithm


The Berlekamp-Massey algorithmMathworldPlanetmath is used for finding the minimal polynomialPlanetmathPlanetmath of a linearly recurrent sequenceMathworldPlanetmath. The algorithm itself is presented at the end of this article.

Definition 1.

Suppose the infiniteMathworldPlanetmathPlanetmath sequence a with elements from a field K has the property that there exist constants c1,,ck in K such that, for all t>k,

at=at-1c1+at-2c2++at-kck.

Then a is called a linearly recurrent sequence.

Definition 2.

Given a linearly recurrent sequence a, suppose c0ckK with c00 satisfy, for all t>k,

c0at=at-1c1+at-2c2++at-kck.

Then the polynomialPlanetmathPlanetmath

c0xk-c1xk-1-c2xk-2--ck

is called an annihilatorMathworldPlanetmathPlanetmath for a.

Proposition 1.

The annihilators of a form an ideal of K[x].

Definition 3.

Since K[x] is a principal ideal domainMathworldPlanetmath, the ideal of a’s annihilators have a unique monic generator of minimalPlanetmathPlanetmath degree. This annihilator is called the minimal polynomial of a.

To find the minimal polynomial, we need to be given an upper bound m on its degree; having done so, the minimal polynomial is uniquely determined by the first 2m elements of a (since we need to get m equations to solve for the unknowns c1,cm).

There is another way to determine the minimal polynomial, originally presented by Dornstetter, which uses the Euclidean AlgorithmMathworldPlanetmath. It can be shown that the characteristic polynomialMathworldPlanetmathPlanetmath of a sequence is the unique monic polynomial C(x) of least degree for which the infinite product

C(x)(a1+a2x+a3x2+)

has finitely many nonzero terms. (In fact, the nonzero terms will have coefficients up to xk-1 where k is the degree of C).

We can rewrite this as

C(x)(a1+a2x++a2mx2m-1)-Q(x)x2m=R(x)

where R(x) is a remainder polynomial of degree ¡ m, and Q(x) is a quotient polynomial. Denote by A(x) the sum Σi=12maixi-1.

This is where the Euclidean Algorithm comes in; if we take the GCD of A(x) and x2m, keeping track of remainders, we get two sequences Pi(x),Qi(x) such that

Pi(x)A(x)-Qi(x)x2m

forms a series of polynomials whose degree is decreasing; as soon as this degree is less than m, we have the needed polynomials with C=Pi,Q=Qi.

There is more info about the Extended Euclidean Algorithm in “Modern Computer Algebra” by von zur Gathen and Gerhard.

(Berlekamp’s algorithm proper to come)

The original algorithm is from Algebraic Coding Theory by Elwyn R. Berlekamp, McGraw-Hill, 1968. Its application to linearly recurrent sequences was noted by J.L.Massey, in “Shift-register synthesis and BCH decoding”, 1969.

TitleBerlekamp-Massey algorithm
Canonical nameBerlekampMasseyAlgorithm
Date of creation2013-03-22 14:28:55
Last modified on2013-03-22 14:28:55
Ownermathcam (2727)
Last modified bymathcam (2727)
Numerical id7
Authormathcam (2727)
Entry typeDefinition
Classificationmsc 15A03
Classificationmsc 11B37
Related topicRecurrenceRelation
Related topicMapleImplementationOfBerlekampMasseyAlgorithm
Defineslinear recurrent sequence
Definesminimal polynomial of a sequence
Definesannihilator
随便看

 

数学辞典收录了18232条数学词条,基本涵盖了常用数学知识及数学英语单词词组的翻译及用法,是数学学习的有利工具。

 

Copyright © 2000-2023 Newdu.com.com All Rights Reserved
更新时间:2025/5/5 4:54:09