IBM Journal of Research and Development
IBM Skip to main content
  Home     Products & services     Support & downloads     My account  

  Select a country  
Journals Home  
  Systems Journal  
Journal of Research
and Development
    Current Issue  
    Recent Issues  
    Papers in Progress  
    Search/Index  
    Orders  
    Description  
    Patents  
    Recent publications  
    Author's Guide  
  Staff  
  Contact Us  
  Related links:  
     IBM Research  

IBM Journal of Research and Development  
Volume 20, Number 3, Page 204 (1976)
Nontopical Issue
  Full article: arrowPDF   arrowCopyright info





   

Analysis of the Berlekamp–Massey Linear Feedback Shift-Register Synthesis Algorithm

by F. G. Gustavson
An analysis of the Berlekamp–Massey Linear Feedback Shift-Register (LFSR) Synthesis Algorithm is provided which shows that an input string of length n requires O(n2) multiplication/addition operations in the underlying field of definition. We also derive the length distribution for digit strings of length n. Results show that, on the average, the encoded length is no greater than n + 1 Furthermore, we exhibit a connection between step 1 of the Ling–Palermo algorithm and the LFSR Algorithm, and the LFSR Algorithm turns out to be computationally superior.
Related Subjects: Algorithms; Codes and coding