Description of Minimum Weight Codewords of Cyclic Codes by Algebraic Systems

✍ Scribed by Daniel Augot

• Publisher: Elsevier Science
• Year: 1996
• Tongue: English
• Weight: 272 KB
• Volume: 2
• Category: Article
• ISSN: 1071-5797
• DOI: 10.1006/ffta.1996.0009

✦ Synopsis

We consider cyclic codes of length n over ‫ކ‬ q , n being prime to q. For such a cyclic code C, we describe a system of algebraic equations, denoted by S C (w), where w is a positive integer. The system is constructed from Newton's identities, which are satisfied by the elementary symmetric functions and the (generalized) power sum symmetric functions of the locators of codewords of weight w. The main result is that, in a certain sense, the algebraic solutions of S C (w) are in one-to-one correspondence with all the codewords of C having weight lower than w. In the particular case where w is the minimum distance of C, all minimum weight codewords are described by S C (w). Because the system S C (w) is very large, with many indeterminates, no great insight can be directly obtained, and specific tools are required in order to manipulate the algebraic systems. For this purpose, the theory of Gro ¨bner bases can be used. A Gro ¨bner basis of S C (w) gives information about the minimum weight codewords.