The BMS Algorithm

Shojiro Sakata ()
Additional contact information
Shojiro Sakata: The University of Electro-Communications

A chapter in Gröbner Bases, Coding, and Cryptography, 2009, pp 143-163 from Springer

Abstract: Abstract We present a sketch of the n-dimensional (n-D) Berlekamp–Massey algorithm (alias Berlekamp–Massey–Sakata or BMS algorithm) w.r.t. n-D arrays. That is: (1) How is it related to Gröbner basis? (2) What problem can it solve? (3) How does it work? (4) Its variations. First we discuss another problem closely related to our main problem, and introduce some concepts about n-D linear recurrences and modules of n-D arrays as their general solutions. These two problems are just the inverse (or rather dual) to each other, which can be solved by the Buchberger algorithm (Buchberger in Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal, Ph.D. thesis, Innsbruck, 1965; J. Symb. Comput. 41(3–4):475–511, 2006; Multidimensional systems theory, Reidel, Dordrecht, pp. 184–232, 1985; Mora in Gröbner technology, this volume, pp. 11–25, 2009b), and the BMS algorithm, respectively. Furthermore, we discuss some properties of BMS algorithm and its outputs, including its computational complexity, as well as several variations of the BMS algorithm.

Keywords: Cyclic Code; Fibonacci Sequence; Linear Recurrence; Complete Class; Fast Decode (search for similar items in EconPapers)
Date: 2009
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-540-93806-4_9

Ordering information: This item can be ordered from
http://www.springer.com/9783540938064

DOI: 10.1007/978-3-540-93806-4_9

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().