Samenvatting
The decoding of arbitrary linear block codes is accomplished by solving a system of quadratic equations by means of Buchberger’s algorithm for finding a Gröbner
basis. This generalizes the algorithm of Berlekamp-Massey for decoding Reed
Solomon, Goppa and cyclic codes up to half the true minimum distance by intro
ducing the unknown syndromes as variables. The complexity of this algorithm
is exponential and the complexity coefficient is measured under the assumption
that the over-determined system of quadratic equations is semi-regular using the
results of Bardet et al. [5]. The complexity is compared to existing bounded
distance decoding algorithms. Our method can be extended to complete and
generic decoding, and to finding the minimum distance and the complete weight
distribution.
| Originele taal-2 | Engels |
|---|---|
| Titel | Proceedings of the 28th Symposium on Information Theory in the Benelux, 24-25 May 2007, Enschede, The Netherlands |
| Redacteuren | R. Veldhuis, H. Cronie, H. Hoeksema |
| Plaats van productie | Enschede |
| Uitgeverij | Universiteit Twente |
| Pagina's | 3-10 |
| ISBN van geprinte versie | 978-90-365-2509-1 |
| Status | Gepubliceerd - 2007 |