Movatterモバイル変換


[0]ホーム

URL:


Skip to main content

Advertisement

Springer Nature Link
Log in

A Unifying System-Theoretic Framework for Errors-and-Erasures Reed-Solomon Decoding

  • Conference paper
  • First Online:

Part of the book series:Lecture Notes in Computer Science ((LNCS,volume 2227))

  • 841Accesses

  • 3Citations

Abstract

In the literature there exist several methods for errors-anderasures decoding of RS codes. In this paper we present a unified approach that makes use of behavioral systems theory. We show how different classes of existing algorithms (e.g., syndrome based or interpolation based, non-iterative, erasure adding or erasure deleting) fit into this framework. In doing this, we introduce a slightly more general WB key equation and show how this allows for the handling of erasure locations in a natural way.

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

Access this chapter

Subscribe and save

Springer+ Basic
¥17,985 /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
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide -see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Araki, K. and I. Fujita (1992). Generalized syndrome polynomials for decoding Reed-Solomon codes.IEICE Trans. FundamentalsE75–A, 1026–1029.

    Google Scholar 

  2. Araki, K., Takada, M. and M. Morii (1992). On the efficient decoding of Reed-Solomon codes based on GMD criterion.Proc. 22nd Int. Symp. on Multiple Valued Logic, 138–142.

    Google Scholar 

  3. Araki, K., Takada, M. and M. Morii (1993). The efficient GMD decoders for BCH codes.IEICE Trans. Inform. and SystemsE76–D, 594–604.

    Google Scholar 

  4. Berlekamp, E.R. (1996). Bounded distance+1 soft-decision Reed-Solomon decoding.IEEE Trans. Inform. Theory42, 704–721.

    Article MATH  Google Scholar 

  5. Blackburn, S.R. (1997). A generalized rational interpolation problem and the solution of the WB algorithm.Designs,Co des and Cryptography11, 223–234.

    Article MATH MathSciNet  Google Scholar 

  6. Blahut, R.E. (1983).Theory and Practice of Error Control Codes, Addison-Wesley.

    Google Scholar 

  7. Elias, P. (1954). Error-free coding.IRE Trans. Inform. TheoryPGIT–4, 29–37.

    Article MathSciNet  Google Scholar 

  8. Fitzpatrick, P. (1995). On the key equation.IEEE Trans. Inform. Theory41, 1290–1302.

    Article MATH MathSciNet  Google Scholar 

  9. Forney, G.D., Jr. (1966). Generalized minimum distance decoding.IEEE Trans. Inform. Theory12, 125–131.

    Article MATH MathSciNet  Google Scholar 

  10. Fujisawa, M. and S. Sakata (1999). On fast generalized minimum distance decoding for algebraic codes.Preproc. AAECC-13, 82–83.

    Google Scholar 

  11. Kamiya, N. (1995). On multisequence shift register synthesis and generalizedminimum-distance decoding of Reed-Solomon codes.Finite Fields Appl.1, 440–457.

    Article MATH MathSciNet  Google Scholar 

  12. Kamiya, N. (1999). A unified algorithm for solving key equations for decoding alternant codes.IEICE Trans. Fundamentals,E82–A, 1998–2006.

    Google Scholar 

  13. Kobayashi, Y., Fujisawa, M. and S. Sakata (2000). Constrained shiftregister synthesis: fast GMD decoding of 1D algebraic codes.IEICE Trans. Fundamentals83, 71–80.

    Google Scholar 

  14. Kötter, R. (1996). Fast generalized minimum distance decoding of algebraic geometric and Reed-Solomon codes.IEEE Trans. Inform. Theory42, 721–738.

    Article MATH MathSciNet  Google Scholar 

  15. Kuijper, M. and J.C. Willems (1997). On constructing a shortest linear recurrence relation.IEEE Trans. Aut. Control42, 1554–1558.

    Article MATH MathSciNet  Google Scholar 

  16. Kuijper, M. (1999). The BM algorithm, error-correction, keystreams and modeling. InDynamical Systems,Control, Coding,Computer Vision, G. Picci, D. S. Gilliam (eds.), Birkhäuser

    Google Scholar 

  17. Kuijper, M. (1999). Further results on the use of a generalized BM algorithm for BCH decoding beyond the designed error-correcting capability,Proc. 13th AAECC, Hawaii, USA (1999), 98–99.

    Google Scholar 

  18. Kuijper, M. (2000). Algorithms for Decoding and Interpolation. InCodes,Systems, and Graphical Models, IMA Series Vol. 123, B. Marcus and J. Rosenthal (eds.), pp. 265–282, Springer-Verlag.

    Google Scholar 

  19. Kuijper, M. (2000). A system-theoretic derivation of the WB algorithm, inProc. IEEE International Symposium on Information Theory (ISIT’00) p. 418.

    Google Scholar 

  20. Sorger, U. (1993). A new Reed-Solomon decoding algorithm based on Newton’s interpolation.IEEE Trans. Inform. Theory39, 358–365.

    Article MATH MathSciNet  Google Scholar 

  21. Taipale, D.J. and M.J. Seo (1994). An efficient soft-decision Reed-Solomon decoding algorithm.IEEE Trans. Info. Theory40, 1130–1139.

    Article MATH MathSciNet  Google Scholar 

  22. Wicker, S.B. (1995).Error control systems, Prentice Hall.

    Google Scholar 

  23. Willems, J.C. (1991). Paradigms and puzzles in the theory of dynamical systems.IEEE Trans. Aut. Control36, 259–294.

    Article MATH MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Dept. of EE Engineering, University of Melbourne, 3010, VIC, Australia

    Margreta Kuijper

  2. Philips Research, 5656, AA Eindhoven, The Netherlands

    Marten van Dijk, Henk Hollmann & Job Oostveen

Authors
  1. Margreta Kuijper
  2. Marten van Dijk
  3. Henk Hollmann
  4. Job Oostveen

Editor information

Editors and Affiliations

  1. Department of Mathematics, RMIT University, GPO Box 2476V, 3001, Melbourne, Australia

    Serdar Boztaş

  2. Department of Computing, Macquarie University, 2109, NSW, Australia

    Igor E. Shparlinski

Rights and permissions

Copyright information

© 2001 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Kuijper, M., van Dijk, M., Hollmann, H., Oostveen, J. (2001). A Unifying System-Theoretic Framework for Errors-and-Erasures Reed-Solomon Decoding. In: Boztaş, S., Shparlinski, I.E. (eds) Applied Algebra, Algebraic Algorithms and Error-Correcting Codes. AAECC 2001. Lecture Notes in Computer Science, vol 2227. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45624-4_36

Download citation

Publish with us

Access this chapter

Subscribe and save

Springer+ Basic
¥17,985 /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
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide -see info

Tax calculation will be finalised at checkout

Purchases are for personal use only


[8]ページ先頭

©2009-2025 Movatter.jp