Skip to main content
SpringerLink
Log in

Random Matrices and Codes for the Erasure Channel

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

The design of erasure correcting codes and their decoding algorithms is now at the point where capacity achieving codes are available with decoding algorithms that have complexity that is linear in the number of information symbols. One aspect of these codes is that the overhead (number of coded symbols beyond the number of information symbols required to achieve decoding completion with high probability) is linear in k. This work considers a new class of random codes which have the following advantages: (i) the overhead is constant (in the range of 5 to 10), independent of the number of data symbols being encoded (ii) the probability of completing decoding for such an overhead is essentially one (iii) the codes are effective for a number of information symbols as low as a few tens (iv) the only probability distribution required is the uniform distribution. The price for these properties is that the decoding complexity is greater, on the order of k 3/2. However, for the lower values of k where these codes are of particular interest, this increase in complexity might be outweighed by their advantages. The parity check matrices of these codes are chosen at random as windowed matrices, i.e. for each column an initial starting position of a window of length w is chosen and the succeeding w positions are chosen at random as zero or one. It can be shown that it is necessary that w=O(k 1/2) for the probabilistic matrix rank properties to behave as a non-windowed random matrix. The sufficiency of the condition has so far been established by extensive simulation, although other arguments strongly support this conclusion. The properties of the codes described depend heavily on the rank properties of random matrices over finite fields. Known results on such matrices are briefly reviewed and several conjectures needed in the discussion of the code properties, are stated. The likelihood of the validity of the conjectures is supported through extensive experimentation. Mathematical proof of the conjectures would be of great value for their own interest as well of the particular coding application described here.

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

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Berlekamp, E.R.: The technology of error correcting codes. Proc. IEEE 68, 564–593 (1980)

    Article  Google Scholar 

  2. Blömer, J., Karp, R., Welzl, E.: The rank of sparse random matrices over finite fields. Random Struct. Algorithms 10, 407–419 (1997)

    Article  MATH  Google Scholar 

  3. Bollobas, B.: Random Graphs, 2nd edn. Cambridge Univ. Press, Cambridge (2001)

    MATH  Google Scholar 

  4. Cooper, C.: On the rank of random matrices. Random Struct. Algorithms 16(2), 209–232 (2000)

    Article  MATH  Google Scholar 

  5. Cooper, C.: On the distribution of rank of a random matrix over a finite field. Random Struct. Algorithms 17, 197–212 (2000)

    Article  MATH  Google Scholar 

  6. Esmaeli, O., Shokrollahi, A.: Raptor codes for the binary memoryless symmetric channels. IEEE Trans. Inf. Theory 52, 2033–2051 (2006)

    Article  Google Scholar 

  7. Gallager, R.G.: Low Density Parity Check Codes. MIT Press, Cambridge (1963)

    Google Scholar 

  8. Kolchin, V.F.: Random Graphs. Cambridge University Press, Cambridge (1999)

    MATH  Google Scholar 

  9. Landsburg, G.: Über eine Anzahlbestimmung und eine damit zusammenhängende Reihe. J. Reine Angew. Math. 111, 87–88 (1893)

    Google Scholar 

  10. Luby, M., Mitzenmacher, M., Amin Shokrollahi, M., Speilman, D., Stemann, V.: Practical loss-resilient codes. In: Symposium on Theory of Computing, pp. 150–159 (1997)

  11. Luby, M.: LT codes. In: Symposium on Theory of Computing, 2002

  12. Luby, M., et al.: On demand encoding with a window, Patent No. 6,486,803,United States Patent and Trademark Office, 26 November 2002

  13. Maymounkov, P.: Online codes. Technical report TR2002-833, New York University, October 2002

  14. Shokrollahi, A.: Raptor codes. IEEE Trans. Inf. Theory 52, 2552–2567 (2006)

    Article  Google Scholar 

  15. Studhome, C., Blake, I.F.: Properties of random matrices and applications. Unpublished report available at http://stoa.dhs.org/~cvs/coding/

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, University of Toronto, 10 King’s College Road, Room 3302, Sandford Fleming Building, Toronto, Ontario, M5S 3G4, Canada

    Chris Studholme

  2. Department of Electrical and Computer Engineering, University of Toronto, Toronto, Ontario, M5S 3G4, Canada

    Ian F. Blake

Authors
  1. Chris Studholme
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ian F. Blake
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Chris Studholme.

Additional information

The first author was supported in part by NSERC Grant A632.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Studholme, C., Blake, I.F. Random Matrices and Codes for the Erasure Channel. Algorithmica 56, 605–620 (2010). https://doi.org/10.1007/s00453-008-9192-0

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-008-9192-0

Keywords

Search

Navigation