nach oben

Designs, Codes and Cryptography

Erschienen in:

01.11.2014

On transform-domain error and erasure correction by Gabidulin codes

verfasst von: Wenhui Li, Vladimir Sidorenko, Danilo Silva

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

KI-gestützte Suche

Aus

Abstract

Gabidulin codes are the rank metric analogues of Reed–Solomon codes and have found many applications including network coding. In this paper, we propose a transform-domain algorithm correcting both errors and erasures with Gabidulin codes. Interleaving or the direct sum of Gabidulin codes allows both decreasing the redundancy and increasing the error correcting capability for network coding. We generalize the proposed decoding algorithm for interleaved Gabidulin codes. The transform-domain approach allows to simplify derivations and proofs and also simplifies finding the error vector after solving the key equation.

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

Nächster Artikel A matrix approach for constructing quadratic APN functions

Nur mit Berechtigung zugänglich

Gabidulin E.M.: Theory of codes with maximal rank distance. Probl. Inf. Transm. 21(1), 1–12 (1985).

Delsarte P.: Bilinear forms over a finite field, with application to coding theory. J. Comb. Theory Ser. A 25, 226–241 (1978).

Roth R.M.: Maximum-rank array codes and their application to criss-cross error correction. IEEE Trans. Inf. Theory 37(2), 328–1336 (1991).

Kötter R., Kschischang F.R.: Coding for errors and erasures in random network coding. IEEE Trans. Inf. Theory 54(8), 3579–3591 (2008).

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).

Sidorenko V., Jiang L., Bossert M.: Skew-feedback shift-register synthesis and decoding interleaved gabidulin codes. IEEE Trans. Inf. Theory IT-57, 621–632 (2011).

Paramonov A.V., Tretjakov O.V.: An analogue of Berlekamp–Massey algorithm for decoding codes in rank metric. In: Proceedings of Moscow Institute for Physics and Technology (MIPT), Moscow, Russia (1991) (In Russian).

Richter G., Plass S.: Fast decoding of rank codes with rank errors and column erasures. In: Proceedings of IEEE International Symposium on Information Theory, Chicago, IL, 27 June– 2 July, p. 398 (2004).

Loidreau, P.: A Welch–Berlekamp like algorithm for decoding Gabidulin codes. In: 4th International Workshop on Coding and Cryptography. LNCS, vol. 3969, pp. 36–45 (2006).

10.

Wachter A., Afanassiev V., Sidorenko V.: Fast decoding of Gabidulin codes. Des. Codes Cryptogr. 66, 57–73 (2013).

11.

Silva D., Kschischang F.R.: Fast encoding and decoding of Gabidulin codes. In: Proceedings of IEEE International Symposium on Information Theory, Seoul, Korea, Jul. 2009, pp. 2858–2862 (2009).

12.

Gabidulin E.M., Pilipchuk N.I.: Error and erasure correcting algorithms for rank codes. Des. Codes Cryptogr. 49, 105–122 (2008).

13.

Gabidulin E.M., Paramonov A.V., Tretjakov O.V.: Rank errors and rank erasures correction. In: Proceedings of 4th International Collocvium on Coding Theory, Dilijan, Armenia, Sept. 30–Oct. 7, pp. 11–19 (1991).

14.

Loidreau P., Overbeck R.: Decoding rank errors beyond the error-correction capability. In: Proceedings of 10th International Workshop on Algebraic and Combinatorial Coding Theory, ACCT-10, Zvenigorod, Russia, Sept. 2006 (2006).

15.

Overbeck R.: Public key cryptography based on coding theory. PhD dissertation, Darmstadt, Germany (2007).

16.

Wachter-Zeh A., Zeh A.: List and unique error-erasure decoding of interleaved Gabidulin codes with interpolation techniques. Des. Codes Cryptogr. (2014). doi:10.1007/s10623-014-9953-5.

17.

Hua L.-K.: A theorem on matrices over a fields and its applications. Chin. Math. Soc. 1(2), 109–163 (1951).

18.

Lidl R., Niederreiter H.: In: Finite Fields. Addison-Wesley, Reading (1983).

19.

Ore O.: Theory of non-commutative polynomials. Ann. Math. 34, 480–508 (1933).

20.

Sidorenko V., Bossert M.: Fast skew-feedback shift-register synthesis. Des. Codes Cryptogr. April, 1–13 (2012).

21.

Sidorenko V., Richter G., Bossert M.: Linearized shift-register synthesis. IEEE Trans. Inf. Theory 57(9), 6025–6032 (2011).

22.

Gadouleau M., Yan Z.: Complexity of decoding Gabidulin codes. In: Proceedings of Annual Conference on Information Sciences and Systems, Princeton, NJ, 19–21 Mar., pp. 1081–1085 (2008).

23.

Li W., Sidorenko V., Chen D.: On transform-domain decoding of Gabidulin codes. In: Proceedings of International Workshop on Coding and Cryptography, Apr. 2013, Bergen, Norway (2013).

Titel: On transform-domain error and erasure correction by Gabidulin codes
verfasst von: Wenhui Li
Vladimir Sidorenko
Danilo Silva
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-9954-4

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Weitere Artikel der Ausgabe 2/2014

A new large class of functions not APN infinitely often

On the geometry of balls in the Grassmannian and list decoding of lifted Gabidulin codes

Distinguisher-based attacks on public-key cryptosystems using Reed–Solomon codes

Towards the optimality of Feistel ciphers with substitution-permutation functions

PotLLL: a polynomial time version of LLL with deep insertions

On discrete Fourier transform, ambiguity, and Hamming-autocorrelation of pseudorandom sequences