Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Designs, Codes and Cryptography
Erschienen in: Designs, Codes and Cryptography 2/2014

01.11.2014

List and unique error-erasure decoding of interleaved Gabidulin codes with interpolation techniques

verfasst von: Antonia Wachter-Zeh, Alexander Zeh

Erschienen in: Designs, Codes and Cryptography | Ausgabe 2/2014

Einloggen, um Zugang zu erhalten

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

A new interpolation-based decoding principle for interleaved Gabidulin codes is presented. The approach consists of two steps: First, a multi-variate linearized polynomial is constructed which interpolates the coefficients of the received word and second, the roots of this polynomial have to be found. Due to the specific structure of the interpolation polynomial, both steps (interpolation and root-finding) can be accomplished by solving a linear system of equations. This decoding principle can be applied as a list decoding algorithm (where the list size is not necessarily bounded polynomially) as well as an efficient probabilistic unique decoding algorithm. For the unique decoder, we show a connection to known unique decoding approaches and give an upper bound on the failure probability. Finally, we generalize our approach to incorporate not only errors, but also row and column erasures.
Vorheriger Artikel Paillier-based publicly verifiable (non-interactive) secret sharing
Nächster Artikel On transform-domain error and erasure correction by Gabidulin codes
Anhänge
Nur mit Berechtigung zugänglich
Fußnoten
1
Throughout this paper, \([a,b]\) is a short-hand notation for the set of integers \( \{i:a \le i \le b\}\).
 
Literatur
1.
Ahlswede R., Cai N., Li S., Yeung R.: Network information flow. IEEE Trans. Inf. Theory 46(4), 1204–1216 (2000).
2.
Bachoc C., Vallentin F., Passuello A.: Bounds for projective codes from semidefinite programming. Adv. Math. Commun. 7(2), 127–145 (2013).
3.
Delsarte P.: Bilinear forms over a finite field with applications to coding theory. J. Comb. Theory Ser. A 25(3), 226–241 (1978).
4.
Etzion T., Silberstein N.: Error-correcting codes in projective spaces via rank-metric codes and Ferrers diagrams. IEEE Trans. Inf. Theory 55(7), 2909–2919 (2009).
5.
Etzion T., Vardy A.: Error-correcting codes in projective space. IEEE Trans. Inf. Theory 57(2), 1165–1173 (2011).
6.
Gabidulin E.M.: Theory of codes with maximum rank distance. Probl. Inf. Transm. 21(1), 3–16 (1985).
7.
Gabidulin E.M., Pilipchuk N.I.: Error and erasure correcting algorithms for rank codes. Des. Codes Cryptogr. 49(1–3), 105–122 (2008).
8.
Gadouleau M., Yan Z.: Complexity of decoding Gabidulin codes. In: 42nd Annual Conference on Information Sciences Sciences and Systems (CISS), pp. 1081–1085 (2008).
9.
Guruswami V.: Linear-algebraic list decoding of folded Reed–Solomon codes. In: IEEE Conference on Computational Complexity, pp. 77–85 (2011).
10.
Guruswami V., Sudan M.: Improved decoding of Reed–Solomon and algebraic-geometry codes. IEEE Trans. Inf. Theory 45(6), 1757–1767 (1999).
11.
Guruswami V., Wang C.: Linear-algebraic list decoding for variants of Reed–Solomon codes. IEEE Trans. Inf. Theory 59(6), 3257–3268 (2013).
12.
Ho T., Kötter R., Médard M., Karger D.R., Effros M.: The benefits of coding over routing in a randomized setting. In IEEE International Symposium on Information Theory (ISIT), p. 442 (2003).
13.
Ho T., Médard M., Kötter R., Karger D.R., Effros M., Shi J., Leong B.: A random linear network coding approach to multicast. IEEE Trans. Inf. Theory 52(10), 4413–4430 (2006).
14.
Kötter R., Kschischang F.R.: Coding for errors and erasures in random network coding. IEEE Trans. Inf. Theory 54(8), 3579–3591 (2008).
15.
Li W., Sidorenko V.R., Chen D.: On transform-domain decoding of Gabidulin codes. In: International Workshop on Coding and Cryptography (WCC) (2013).
16.
Lidl R., Niederreiter H.: Finite Fields, Series. Encyclopedia of Mathematics and Its Applications. Cambridge University Press, Cambridge (1996).
17.
Loidreau P., Overbeck R.: Decoding rank errors beyond the error correcting capability. In: International Workshop on Algebraic and Combinatorial Coding Theory (ACCT), pp. 186–190 (2006).
18.
Loidreau P.: A Welch–Berlekamp like algorithm for decoding Gabidulin codes. In: Coding and Cryptography-Revised Selected Papers of WCC 2005, vol. 3969, pp. 36–45 (2006).
19.
Mahdavifar H., Vardy A.: List-decoding of subspace codes and rank-metric codes up to singleton bound. In: IEEE International Symposium on Information Theory (ISIT), pp. 1488–1492 (2012).
20.
McEliece R.J.: On the average list size for the Guruswami–Sudan decoder. In: International Symposium on Communications Theory and Applications (ISCTA) (2003).
21.
Menezes A.J., Blake I.F., Gao X., Mullin R.C., Vanstone S.A., Yaghoobian T.: Applications of Finite Fields, 1st edn. Springer, New York (1993).
22.
Ore Ø.: On a special class of polynomials. Trans. Am. Math. Soc. 35, 559–584 (1933).
23.
Ore Ø.: Theory of non-commutative polynomials. Ann. Math. 34(3), 480–508 (1933).
24.
Overbeck R.: Public key cryptography based on coding theory. Ph.D. dissertation, TU Darmstadt, Darmstadt, Germany (2007).
25.
Overbeck R.: Structural attacks for public key cryptosystems based on Gabidulin codes. J. Cryptol. 21(2), 280–301 (2008).
26.
Roth R.M.: Maximum-rank array codes and their application to crisscross error correction. IEEE Trans. Inf. Theory 37(2), 328–336 (1991).
27.
Sidorenko V.R., Bossert M.: Decoding interleaved Gabidulin codes and multisequence linearized shift-register synthesis. In: IEEE International Symposium on Information Theory (ISIT), pp. 1148–1152 (2010).
28.
Sidorenko V.R., Jiang L., Bossert M.: Skew-feedback shift-register synthesis and decoding interleaved Gabidulin codes. IEEE Trans. Inf. Theory 57(2), 621–632 (2011).
29.
Silva D.: Error control for network coding. Ph.D. dissertation, University of Toronto, Toronto, Canada (2009).
30.
Silva D., Kschischang F.R.: Rank-metric codes for priority encoding transmission with network coding. In: Canadian Workshop on Information Theory (CWIT), pp. 81–84 (2007).
31.
Silva D., Kschischang F.R.: Fast encoding and decoding of Gabidulin codes. In: IEEE International Symposium on Information Theory (ISIT), pp. 2858–2862 (2009).
32.
Silva D., Kschischang F.R., Kötter R.: A rank-metric approach to error control in random network coding. IEEE Trans. Inf. Theory 54(9), 3951–3967 (2008).
33.
Skachek V.: Recursive code construction for random networks. IEEE Trans. Inf. Theory 56(3), 1378–1382 (2010).
34.
Sudan M.: Decoding of Reed–Solomon codes beyond the error-correction bound. J. Complex. 13(1), 180–193 (1997).
35.
Wachter-Zeh A.: Bounds on list decoding of rank-metric codes. IEEE Trans. Inf. Theory 59(11), 7268–7277 (2013).
36.
Wachter-Zeh A.: Decoding of block and convolutional codes in rank metric. Ph.D. dissertation, Ulm University, Ulm, Germany and Université de Rennes 1, Rennes, France (2013).
37.
Wachter-Zeh A., Zeh A.: Interpolation-based decoding of interleaved Gabidulin codes. In: International Workshop on Coding and Cryptography (WCC) (2013).
38.
Wang H., Xing C., Safavi-Naini R.: Linear authentication codes: bounds and constructions. IEEE Trans. Inf. Theory 49(4), 866–872 (2003).
39.
Xia S., Fu F.: Johnson type bounds on constant dimension codes. Des. Codes Cryptogr. 50(2), 163–172 (2009).
40.
Xie H., Yan Z., Suter B.W.: General linearized polynomial interpolation and its applications. In: IEEE International Symposium on Network Coding (Netcod), pp. 1–4 (2011).
Metadaten
Titel
List and unique error-erasure decoding of interleaved Gabidulin codes with interpolation techniques
verfasst von
Antonia Wachter-Zeh
Alexander Zeh
Publikationsdatum
01.11.2014
Verlag
Springer US
Erschienen in
Designs, Codes and Cryptography / Ausgabe 2/2014
Print ISSN: 0925-1022
Elektronische ISSN: 1573-7586
DOI
https://doi.org/10.1007/s10623-014-9953-5

Weitere Artikel der Ausgabe 2/2014

Designs, Codes and Cryptography 2/2014 Zur Ausgabe

OriginalPaper

Paillier-based publicly verifiable (non-interactive) secret sharing

OriginalPaper

Wiretap lattice codes from number fields with no small norm elements

OriginalPaper

On the arithmetic Walsh coefficients of Boolean functions

OriginalPaper

Connections between Construction D and related constructions of lattices

OriginalPaper

Multi-trial Guruswami–Sudan decoding for generalised Reed–Solomon codes

OriginalPaper

Editorial: special issue on coding and cryptography

Premium Partner

    Bildnachweise