![]() In the second step we prove the minimality. ProofĪs a first step we will prove by induction on i that f i is a feedback polynomial of an LFSR that produces x 0,…, x i−1. In the notation of Algorithm 2.1, L i is the linear complexity of the sequence x 0,…, x i−1 and f i is the feedback polynomial of the minimal LFSR that generates x 0,…, x i−1. To simplify the notation we specialize Algorithm 2.1 to the binary case. In cryptography we are interested only in binary sequences, in contrast to coding theory where the algorithm is normally used over larger finite fields. We present the algorithm, which is now known as Berlekamp-Massey algorithm, in the form which computes the linear complexity of a binary sequence. One year later, Massey noticed that the decoding problem is in its essential parts equivalent to the determination of the shortest LFSR that generates a given sequence. ![]() ![]() In 1968 E.R. Berlekamp presented an efficient algorithm for decoding BCH-codes (an important class of cyclic error-correcting codes). ![]() In the next section we will prove that we even have equality in ( 2.20). Where the last equality is due to Lemma 2.1. □ ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |