SpringerLink
Log in

Coding Techniques for Transmitting Packets Through Complex Communication Networks

  • Chapter
  • First Online:
Communications in Interference Limited Networks

Part of the book series: Signals and Communication Technology ((SCT))

  • 750 Accesses

Abstract

Random Linear Network Coding (RLNC) is a technique to disseminate information in a network. Various error scenarios require algebraic code constructions with high error-correcting capability in order to transmit packets reliably through such a network. It was shown that subspace codes, in particular lifted rank-metric codes, are suitable for this purpose, in contrast to Hamming metric in the case of a classical transmission. The mainly used codes are Gabidulin codes. In this contribution, we will introduce Gabidulin codes and describe several error-erasure decoding algorithms. Further, an extension of Gabidulin codes is introduced which allows to decode beyond half the minimum rank distance, the interleaved Gabidulin codes. Further, we will introduce (partial) unit memory codes based on Gabidulin codes. Such convolutional codes are of particular interest in so-called multi-shot transmissions since memory between different transmission is introduced. Finally, we will show a significant difference of Gabidulin and Reed-Solomon codes in case of list decoding. Namely, that the list size can grow exponentially for a decoding radius below the Johnson bound for rank metric codes.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 129.00
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 169.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free ship** worldwide - see info
Hardcover Book
USD 169.99
Price excludes VAT (USA)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free ship** worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    \(\mathbb {F}_q\) denotes a finite field with q elements, where q is a prime power.

References

  1. Bachoc C, Passuello A, Vallentin F (2013) Bounds for projective codes from semidefinite programming. Adv Math Commun 7(2):127–145

    Article  MathSciNet  MATH  Google Scholar 

  2. Bassalygo LA (1965) New upper bounds for error correcting codes. Prob Inf Transm 1(4):41–44

    MathSciNet  MATH  Google Scholar 

  3. Bossert M (1999) Channel coding for telecommunications. Wiley, Chichester

    Google Scholar 

  4. Bossert M (2012) Einführung in die Nachrichtentechnik. Oldenburg Verlag

    Google Scholar 

  5. Cai N, Yeung RW (2002) Network coding and error correction. In: Proceedings of IEEE Information Theory Workshop, pp 119–122

    Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  7. Dettmar U, Shavgulidze S (1992) New optimal partial unit memory codes. Electron Lett 28:1748–1749

    Article  Google Scholar 

  8. Dettmar U, Sorger U (1993) New optimal partial unit memory codes based on extended BCH codes. Electron Lett 29(23):2024–2025

    Article  Google Scholar 

  9. Etzion T, Silberstein N (2009) Error-correcting codes in projective spaces via rank-metric codes and ferrers diagrams. IEEE Trans Inf Theory 55(7):2909–2919

    Article  MathSciNet  Google Scholar 

  10. Forney G (1970) Convolutional codes I: algebraic structure. IEEE Trans Inf Theory 16(6):720–738

    Article  MathSciNet  MATH  Google Scholar 

  11. Gabidulin EM (1985) Theory of codes with maximum rank distance. Prob Peredachi Inf 21(1):3–16

    MathSciNet  Google Scholar 

  12. Gadouleau M, Yan Z (2010) Constant-rank codes and their connection to constant-dimension codes. IEEE Trans Inf Theory 56(7):3207–3216

    Article  MathSciNet  Google Scholar 

  13. Goldreich O, Rubinfeld R, Sudan M (2000) Learning polynomials with queries: the highly noisy case. SIAM J Discrete Math 13(4). doi:10.1137/S0895480198344540

    Google Scholar 

  14. Guruswami V (1999) List decoding of error-correcting codes: winning thesis of the 2002 ACM doctoral dissertation competition. Lecture notes in computer science. Springer, Berlin

    Google Scholar 

  15. Guruswami V, Sudan M (1999) Improved decoding of reed-solomon and algebraic-geometry codes. IEEE Trans Inf Theory 45(6):1757–1767

    Article  MathSciNet  MATH  Google Scholar 

  16. Ho T, Koetter R, Medard M, Karger DR, Effros M (2003) The benefits of coding over routing in a randomized setting

    Google Scholar 

  17. Hua LK (1951) A theorem on matrices over a field and its applications. Acta Math Sinica 1(2):109–163

    Google Scholar 

  18. Johnson S (1962) A new upper bound for error-correcting codes. IRE Trans Inf Theory 8(3):203–207. doi:10.1109/TIT.1962.1057714

    Article  MATH  Google Scholar 

  19. Justesen J (1993) Bounded distance decoding of unit memory codes. IEEE Trans Inf Theory 39(5):1616–1627

    Article  MathSciNet  MATH  Google Scholar 

  20. Koetter R, Kschischang FR (2008) Coding for errors and erasures in random network coding. IEEE Trans Inf Theory 54(8):3579–3591. doi:10.1109/TIT.2008.926449

    Article  MathSciNet  Google Scholar 

  21. Lauer GS (1979) Some optimal partial-unit memory codes. IEEE Trans Inf Theory 23(2):240–243

    Article  Google Scholar 

  22. Lee LN (1976) Short unit-memory byte-oriented binary convolutional codes having maximal free distance. IEEE Trans Inf Theory :349–352

    Google Scholar 

  23. Lidl R, Niederreiter H (1996) Finite fields. Encyclopedia of mathematics and its applications. Cambridge University Press, Cambridge

    Google Scholar 

  24. Loidreau P, Overbeck R (2006) Decoding rank errors beyond the error correcting capability, pp 186–190

    Google Scholar 

  25. Overbeck R (2006) Decoding interleaved gabidulin codes and ciphertext-security for GPT variants. Preprint

    Google Scholar 

  26. Paramonov A, Tretjakov O (1991) An analogue of Berlekamp-Massey algorithm for decoding codes in rank metric. In: Proceedings of MIPT

    Google Scholar 

  27. Pollara F, McEliece RJ, Abdel-Ghaffar KAS (1988) Finite-state codes. IEEE Trans Inf Theory 34(5):1083–1089

    Article  MathSciNet  Google Scholar 

  28. Richter G, Plass S (2004) Error and erasure decoding of rank-codes with a modified Berlekamp-Massey algorithm. In: ITG Fachbericht, pp 203–210

    Google Scholar 

  29. Roth RM (1991) Maximum-rank array codes and their application to crisscross error correction. IEEE Trans Inf Theory 37(2):328–336

    Article  MATH  Google Scholar 

  30. Sidorenko V, Bossert M (2010) Decoding interleaved gabidulin codes and multisequence linearized shift-register synthesis. In: IEEE international symposium on information theory, pp 1148–1152. doi:10.1109/ISIT.2010.5513676

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

    Article  MathSciNet  Google Scholar 

  32. Sidorenko V, Wachter-Zeh A, Chen D (2012) On fast decoding of interleaved gabidulin codes. In: The XIII international symposium—problems of redundancy in information and control systems

    Google Scholar 

  33. Sidorenko V, Li W, Chen D (2013) On transform domain decoding of gabidulin codes. In: Accepted for the eigth international workshop on coding and cryptography (WCC 2013)

    Google Scholar 

  34. Silberstein N, Etzion T (2011) Enumerative coding for grassmannian space. IEEE Trans Inf Theory 57(1):365–374

    Article  MathSciNet  Google Scholar 

  35. Silva D, Kschischang FR (2007) Using rank-metric codes for error correction in random network coding. In: IEEE international symposium on information theory, pp 796–800. doi:10.1109/ISIT.2007.4557322

  36. Silva D, Kschischang FR, Koetter R (2008) A Rank-Metric Approach to Error Control in Random Network Coding. IEEE Trans Inf Theory 54(9):3951–3967

    Article  MathSciNet  MATH  Google Scholar 

  37. Skachek V (2008) Recursive code construction for random networks. Ar**v preprint ar**v:08063650

  38. Sudan M (1997) Decoding of Reed Solomon codes beyond the error-correction bound. J Complex 13(1):180–193. doi:10.1006/jcom.1997.0439

    Article  MathSciNet  MATH  Google Scholar 

  39. Thommesen C, Justesen J (1983) Bounds on distances and error exponents of unit memory codes. IEEE Trans Inf Theory 29(5):637–649

    Article  MathSciNet  MATH  Google Scholar 

  40. Wachter A, Sidorenko V, Bossert M, Zyablov V (2011) On (partial) unit memory codes based on Gabidulin codes. Prob Inf Transm 47(2):38–51

    Google Scholar 

  41. Wachter A, Sidorenko V, Bossert M, Zyablov V (2011) Partial unit memory codes based on Gabidulin codes. In: IEEE international symposium on information theory (ISIT 2011)

    Google Scholar 

  42. Wachter-Zeh A (2012) Bounds on list decoding Gabidulin codes. In: Thirteenth international workshop on algebraic and combinatorial coding theory (ACCT 2012), pp 329–334

    Google Scholar 

  43. Wachter-Zeh A (2013) Bounds on list decoding of rank metric codes. IEEE Trans Inf Theory 59(11):7268–7277

    Article  MathSciNet  Google Scholar 

  44. Wachter-Zeh A (2013) Bounds on polynomial time list decoding of rank metric codes. In: IEEE international symposium on information theory (ISIT), vol 59(11), pp 7268–7277

    Google Scholar 

  45. Wachter-Zeh A, Sidorenko V (2012) Rank metric convolutional codes for random linear network coding. In: IEEE International symposium on network coding (Netcod 2012)

    Google Scholar 

  46. Wachter-Zeh A, Zeh A (2014) List and unique error-erasure decoding of interleaved gabidulin codes with interpolation techniques. Des Codes Crypt 73(2):547–570

    Article  MathSciNet  MATH  Google Scholar 

  47. Wachter-Zeh A, Afanassiev V, Sidorenko V (2013) Fast decoding of Gabidulin codes. Des Codes Crypt 66(1):57–73

    Article  MathSciNet  MATH  Google Scholar 

  48. Wang H, **ng C, Safavi-Naini R (2003) Linear authentication codes: bounds and constructions. IEEE Trans Inf Theory 49(4):866–872

    Article  MathSciNet  MATH  Google Scholar 

  49. **a ST, Fu FW (2009) Johnson type bounds on constant dimension codes. Des Codes Crypt 50(2):163–172

    Article  MathSciNet  Google Scholar 

  50. Zyablov V, Sidorenko V (1994) On periodic (partial) unit memory codes with maximum free distance. Lect Notes Comput Sci 829:74–79

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgments

This work was supported from 2009 to 2013 by the Deutsche Forschungsgemeinschaft (DFG) under grant No. Bo-867/21.

Author information

Authors and Affiliations

  1. Ulm University, Albert-Einstein-Allee 43, 89081, Ulm, Germany

    Martin Bossert & Antonia Wachter-Zeh

  2. Institute for Information Transmission Problems, Russian Academy of Sciences, Moscow, Russia

    Vladimir Sidorenko

  3. Technion—Israel Institute of Technology, Haifa, Israel

    Antonia Wachter-Zeh

Authors
  1. Martin Bossert
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Vladimir Sidorenko
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Antonia Wachter-Zeh
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Martin Bossert .

Editor information

Editors and Affiliations

  1. Technische Universität München, Muenchen, Germany

    Wolfgang Utschick

Rights and permissions

Reprints and permissions

Copyright information

© 2016 Springer International Publishing Switzerland

About this chapter

Cite this chapter

Bossert, M., Sidorenko, V., Wachter-Zeh, A. (2016). Coding Techniques for Transmitting Packets Through Complex Communication Networks. In: Utschick, W. (eds) Communications in Interference Limited Networks. Signals and Communication Technology. Springer, Cham. https://doi.org/10.1007/978-3-319-22440-4_1

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-22440-4_1

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-22439-8

  • Online ISBN: 978-3-319-22440-4

  • eBook Packages: EngineeringEngineering (R0)

Publish with us

Policies and ethics

Search

Navigation