PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (198)
Orphanage
Unclass'd
Unproven (498)
Corrections (24)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: Very high Entry average rating: No information on entry rating
Berlekamp-Massey algorithm (Definition)

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

Definition 1   Suppose the infinite sequence $ a$ with elements from a field $ K$ has the property that there exist constants $ c_1, \ldots, c_k$ in $ K$ such that, for all $ t > k$,
$\displaystyle a_t = a_{t-1}c_1 + a_{t-2}c_2 + ... + a_{t-k}c_k.$
Then $ a$ is called a linearly recurrent sequence.
Definition 2   Given a linearly recurrent sequence $ a$, suppose $ c_0 \ldots c_k \in K$ with $ c_0 \neq 0$ satisfy, for all $ t>k, $
$\displaystyle c_0a_t = a_{t-1}c_1 + a_{t-2}c_2 + ... + a_{t-k}c_k.$
Then the polynomial
$\displaystyle c_0x^k - c_1x^{k-1} - c_2x^{k-2} - ... - c_k$
is called an annihilator for $ a$.
Proposition 1   The annihilators of $ a$ form an ideal of $ K[x]$.
Definition 3   Since $ K[x]$ is a principal ideal domain, the ideal of $ a$'s annihilators have a unique monic generator of minimal 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 $ c_1, \ldots c_m$).

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

$\displaystyle C(x)(a_1 + a_2x + a_3x^2 + ...)$
has finitely many nonzero terms. (In fact, the nonzero terms will have coefficients up to $ x^{k-1}$ where $ k$ is the degree of $ C$).

We can rewrite this as

$\displaystyle C(x)\cdot(a_1 + a_2x + ... + a_{2m}x^{2m-1}) - Q(x)\cdot x^{2m} = 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 $ \Sigma_{i=1}^{2m}a_ix^{i-1}$.

This is where the Euclidean Algorithm comes in; if we take the GCD of $ A(x)$ and $ x^{2m}$, keeping track of remainders, we get two sequences $ P_i(x), Q_i(x)$ such that

$\displaystyle P_i(x)\cdot A(x) - Q_i(x)\cdot x^{2m}$
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=P_i, Q=Q_i$.

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.



"Berlekamp-Massey algorithm" is owned by mathcam. [ full author list (2) | owner history (1) ]
(view preamble)

View style:

See Also: recurrence relation, maple implementation of Berlekamp-Massey algorithm

Also defines:  linear recurrent sequence, minimal polynomial of a sequence, annihilator

Attachments:
maple implementation of Berlekamp-Massey algorithm (Algorithm) by daveagp
Log in to rate this entry.
(view current ratings)

Cross-references: application, theory, algebraic, decreasing, series, gcd, sum, quotient, remainder, coefficients, terms, product, monic polynomial, characteristic polynomial, Euclidean algorithm, equations, upper bound, degree, minimal, generator, monic, principal ideal domain, ideal, polynomial, property, field, infinite, algorithm, sequence, minimal polynomial
There are 6 references to this entry.

This is version 4 of Berlekamp-Massey algorithm, born on 2004-07-22, modified 2005-04-14.
Object id is 6015, canonical name is BerlekampMasseyAlgorithm.
Accessed 21765 times total.

Classification:
AMS MSC: 15A03 (Linear and multilinear algebra; matrix theory :: Vector spaces, linear dependence, rank)
 11B37 (Number theory :: Sequences and sets :: Recurrences)
Pending Errata and Addenda
None.
[ View all 1 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add derivation | add example | add (any)