Computing Groebner Bases for Finding Codewords of Small Weight

Daniel Augot

Date: July 19th (Friday)
Time: 17:00-17:30
Abstract
We describe a relationship between codewords of small weight in codes and algebraic systems of equations. These systems are constructed from the (generalized) Newton's identities, and solving these systems is equivalent to find codewords of weight less than a given weight. We propose to compute a Groebner basis of the system, by using the Buchberger algorithm, or variants. These is a complexity barrier, which make the method inefficient for long codes. However, for small length, valuable information is obtained on codewords, because their Fourier transform is then known. Examples are given.

______________
__________________________________________

Previous page RISC SWP Linz Austria