Synthesizing All Linearized Shift-Registers of the Minimal or Required Length

Conference: SCC'10 - 8th International ITG Conference on Source and Channel Coding
01/18/2010 - 01/21/2010 at Siegen, Germany

Proceedings: SCC'10

Pages: 6Language: englishTyp: PDF

Personal VDE Members are entitled to a 10% discount on this title

Sidorenko, Vladimir R.; Bossert, Martin (Inst. of Telecommunications and Applied Information Theory, Ulm University, Ulm, Germany)

An efficient algorithm synthesizing all q-linearized shift-registers of the minimal or required length generating a sequence of length N over a finite field Fqm is considered. This algorithm, which is a generalization of the Berlekamp-Massey algorithm, has time complexity O(N(exp2)) operations in Fqm, and can be applied for efficient solving the key equation when decoding Gabidulin codes up to and beyond half the minimum rank distance.