Loading...
Please wait, while we are loading the content...
Similar Documents
On the matrix Berlekamp-Massey algorithm (2006)
| Content Provider | CiteSeerX |
|---|---|
| Author | Kaltofen, Erich Yuhasz, George Carolina, North |
| Abstract | We analyze the Matrix Berlekamp/Massey algorithm, which generalizes the Berlekamp/Massey algorithm [Massey 1969] for computing linear generators of scalar sequences. The Matrix Berlekamp/Massey algorithm computes a minimal matrix generator of a linearly generated matrix sequence and has been first introduced by [Rissanen 1972a], [Dickinson et al. 1974] and [Coppersmith 1994]. Our version of the algorithm makes no restrictions on the rank and dimensions of the matrix sequence. We also give new proofs of correctness and complexity for the algorithm, which is based on self-contained loop invariants and includes an explicit termination criterion for a given determinantal degree bound of the minimal matrix generator. ACM Reference Format: |
| File Format | |
| Journal | Manuscript |
| Language | English |
| Publisher Date | 2006-01-01 |
| Access Restriction | Open |
| Subject Keyword | Matrix Berlekamp-massey Algorithm Matrix Sequence Matrix Berlekamp Massey Algorithm Minimal Matrix Generator Linear Generator Self-contained Loop Invariant Determinantal Degree Bound New Proof Berlekamp Massey Algorithm Massey Acm Reference Format Scalar Sequence Explicit Termination Criterion |
| Content Type | Text |
| Resource Type | Article |
