1969/01/01 by J. Massey · 11 citations
Computer Science · Mathematics · #Algorithms and Data Compression #Coding theory and cryptography #Cellular Automata and Applications #BCH code #Shift register #Berlekamp–Welch algorithm #Decoding methods #Computer science #Algorithm #Equivalence (formal languages) #Sequence (biology) #Sequential decoding #Arithmetic #Mathematics #Discrete mathematics #Block code #Telecommunications
paper · doi:10.1109/tit.1969.1054260
openalex publication_date 1969/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
It is shown in this paper that the iterative algorithm introduced by Berlekamp for decoding BCH codes actually provides a general solution to the problem of synthesizing the shortest linear feedback shift register capable of generating a prescribed finite sequence of digits. The shift-register approach leads to a simple proof of the validity of the algorithm as well as providing additional insight into its properties. The equivalence of the decoding problem for BCH codes to a shift-register synthesis problem is demonstrated, and other applications for the algorithm are suggested.