Skew-feedback shift-register synthesis and decoding interleaved gabidulin codes

Vladimir Sidorenko; Lan Jiang; Martin Bossert

doi:10.1109/TIT.2010.2096032

Skew-feedback shift-register synthesis and decoding interleaved gabidulin codes

Vladimir Sidorenko, Lan Jiang, Martin Bossert

Research output: Contribution to journal › Article › peer-review

43 Scopus citations

Abstract

An efficient algorithm which synthesizes all shortest skew-feedback shift-registers (defined in the paper) generating L sequences of varying length over a field is derived and its correctness is proved. It generalizes the BerlekampMassey algorithm and some other algorithms, and has time complexity O(LN²), where N is the length of a longest sequence. The proposed algorithm can be applied for efficiently solving the key equation when decoding interleaved (or direct sum of) Gabidulin codes beyond half minimum distance. Those codes have many applications and, as shown by Ktter and Kschischang, can be used for random network coding.

Original language	English
Article number	5695126
Pages (from-to)	621-632
Number of pages	12
Journal	IEEE Transactions on Information Theory
Volume	57
Issue number	2
DOIs	https://doi.org/10.1109/TIT.2010.2096032
State	Published - Feb 2011
Externally published	Yes

Keywords

Decoding
Gabidulin codes
direct sum of codes
interleaved codes
linearized-feedback
multiple sequences
rank-distance
shift-register synthesis
skew-feedback

Access to Document

10.1109/TIT.2010.2096032

Cite this

@article{956dc13355914d72a2447706def6293b,

title = "Skew-feedback shift-register synthesis and decoding interleaved gabidulin codes",

abstract = "An efficient algorithm which synthesizes all shortest skew-feedback shift-registers (defined in the paper) generating L sequences of varying length over a field is derived and its correctness is proved. It generalizes the BerlekampMassey algorithm and some other algorithms, and has time complexity O(LN2), where N is the length of a longest sequence. The proposed algorithm can be applied for efficiently solving the key equation when decoding interleaved (or direct sum of) Gabidulin codes beyond half minimum distance. Those codes have many applications and, as shown by Ktter and Kschischang, can be used for random network coding.",

keywords = "Decoding, Gabidulin codes, direct sum of codes, interleaved codes, linearized-feedback, multiple sequences, rank-distance, shift-register synthesis, skew-feedback",

author = "Vladimir Sidorenko and Lan Jiang and Martin Bossert",

note = "Funding Information: Manuscript received April 15, 2010; revised October 31, 2010; accepted November 09, 2010. Date of current version January 19, 2011. This work was supported by DFG (German Research Council) under Grant BO 867/21-1. The material in this paper was presented in part at the IEEE International Symposium on Information Theory, Austin, TX, June 2010.",

year = "2011",

month = feb,

doi = "10.1109/TIT.2010.2096032",

language = "English",

volume = "57",

pages = "621--632",

journal = "IEEE Transactions on Information Theory",

issn = "0018-9448",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "2",

}

TY - JOUR

T1 - Skew-feedback shift-register synthesis and decoding interleaved gabidulin codes

AU - Sidorenko, Vladimir

AU - Jiang, Lan

AU - Bossert, Martin

N1 - Funding Information: Manuscript received April 15, 2010; revised October 31, 2010; accepted November 09, 2010. Date of current version January 19, 2011. This work was supported by DFG (German Research Council) under Grant BO 867/21-1. The material in this paper was presented in part at the IEEE International Symposium on Information Theory, Austin, TX, June 2010.

PY - 2011/2

Y1 - 2011/2

N2 - An efficient algorithm which synthesizes all shortest skew-feedback shift-registers (defined in the paper) generating L sequences of varying length over a field is derived and its correctness is proved. It generalizes the BerlekampMassey algorithm and some other algorithms, and has time complexity O(LN2), where N is the length of a longest sequence. The proposed algorithm can be applied for efficiently solving the key equation when decoding interleaved (or direct sum of) Gabidulin codes beyond half minimum distance. Those codes have many applications and, as shown by Ktter and Kschischang, can be used for random network coding.

AB - An efficient algorithm which synthesizes all shortest skew-feedback shift-registers (defined in the paper) generating L sequences of varying length over a field is derived and its correctness is proved. It generalizes the BerlekampMassey algorithm and some other algorithms, and has time complexity O(LN2), where N is the length of a longest sequence. The proposed algorithm can be applied for efficiently solving the key equation when decoding interleaved (or direct sum of) Gabidulin codes beyond half minimum distance. Those codes have many applications and, as shown by Ktter and Kschischang, can be used for random network coding.

KW - Decoding

KW - Gabidulin codes

KW - direct sum of codes

KW - interleaved codes

KW - linearized-feedback

KW - multiple sequences

KW - rank-distance

KW - shift-register synthesis

KW - skew-feedback

UR - http://www.scopus.com/inward/record.url?scp=79251470095&partnerID=8YFLogxK

U2 - 10.1109/TIT.2010.2096032

DO - 10.1109/TIT.2010.2096032

M3 - Article

AN - SCOPUS:79251470095

SN - 0018-9448

VL - 57

SP - 621

EP - 632

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

IS - 2

M1 - 5695126

ER -

Skew-feedback shift-register synthesis and decoding interleaved gabidulin codes

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this