Decoding Hermitian Codes with Sudan's Algorithm

Tom Høholdt; Rasmus Refslund Nielsen

doi:10.1007/3-540-46796-3_26

Decoding Hermitian Codes with Sudan's Algorithm

Tom Høholdt
, Rasmus Refslund Nielsen

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Abstract

We present an efficient implementation of Sudan's algorithm for list decoding Hermitian codes beyond half the minimum distance. The main ingredients are an explicit method to calculate so-called increasing zero bases, an efficient interpolation algorithm for finding the Q-polynomial, and a reduction of the problem of factoring the Q-polynomial to the problem of factoring a univariate polynomial over a large finite field.

Original language	English
Title of host publication	Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, Proceedings
Place of Publication	Berlin
Publisher	Springer
Publication date	1999
Pages	260-270
ISBN (Print)	3-540-66723-7
DOIs	https://doi.org/10.1007/3-540-46796-3_26
Publication status	Published - 1999
Event	13th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes - Honolulu, United States Duration: 15 Nov 1999 → 19 Nov 1999 Conference number: 13

Conference

Conference	13th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes
Number	13
Country/Territory	United States
City	Honolulu
Period	15/11/1999 → 19/11/1999

Series	Lecture Notes in Computer Science
Volume	1719
ISSN	0302-9743

Access to Document

10.1007/3-540-46796-3_26

OpenUrl availability

Check availability in DTU Findit

Cite this

@inproceedings{0b3f8f5aaa724f568439a26673e6d849,

title = "Decoding Hermitian Codes with Sudan's Algorithm",

abstract = "We present an efficient implementation of Sudan's algorithm for list decoding Hermitian codes beyond half the minimum distance. The main ingredients are an explicit method to calculate so-called increasing zero bases, an efficient interpolation algorithm for finding the Q-polynomial, and a reduction of the problem of factoring the Q-polynomial to the problem of factoring a univariate polynomial over a large finite field.",

author = "Tom H{\o}holdt and Nielsen, \{Rasmus Refslund\}",

year = "1999",

doi = "10.1007/3-540-46796-3\_26",

language = "English",

isbn = "3-540-66723-7",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "260--270",

booktitle = "Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, Proceedings",

note = "13th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes ; Conference date: 15-11-1999 Through 19-11-1999",

}

Høholdt, T & Nielsen, RR 1999, Decoding Hermitian Codes with Sudan's Algorithm. in Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, Proceedings. Springer, Berlin, Lecture Notes in Computer Science, vol. 1719, pp. 260-270, 13th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, Honolulu, Hawaii, United States, 15/11/1999. https://doi.org/10.1007/3-540-46796-3_26

Decoding Hermitian Codes with Sudan's Algorithm. / Høholdt, Tom; Nielsen, Rasmus Refslund.
Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, Proceedings. Berlin: Springer, 1999. p. 260-270 (Lecture Notes in Computer Science, Vol. 1719).

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

TY - GEN

T1 - Decoding Hermitian Codes with Sudan's Algorithm

AU - Høholdt, Tom

AU - Nielsen, Rasmus Refslund

N1 - Conference code: 13

PY - 1999

Y1 - 1999

N2 - We present an efficient implementation of Sudan's algorithm for list decoding Hermitian codes beyond half the minimum distance. The main ingredients are an explicit method to calculate so-called increasing zero bases, an efficient interpolation algorithm for finding the Q-polynomial, and a reduction of the problem of factoring the Q-polynomial to the problem of factoring a univariate polynomial over a large finite field.

AB - We present an efficient implementation of Sudan's algorithm for list decoding Hermitian codes beyond half the minimum distance. The main ingredients are an explicit method to calculate so-called increasing zero bases, an efficient interpolation algorithm for finding the Q-polynomial, and a reduction of the problem of factoring the Q-polynomial to the problem of factoring a univariate polynomial over a large finite field.

U2 - 10.1007/3-540-46796-3_26

DO - 10.1007/3-540-46796-3_26

M3 - Article in proceedings

SN - 3-540-66723-7

T3 - Lecture Notes in Computer Science

SP - 260

EP - 270

BT - Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, Proceedings

PB - Springer

CY - Berlin

T2 - 13th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes

Y2 - 15 November 1999 through 19 November 1999

ER -

Decoding Hermitian Codes with Sudan's Algorithm

Abstract

Conference

Access to Document

OpenUrl availability

Fingerprint

Cite this