Remember Me
Or use your Academic/Social account:


Or use your Academic/Social account:


You have just completed your registration at OpenAire.

Before you can login to the site, you will need to activate your account. An e-mail will be sent to you with the proper instructions.


Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version of the site upon release.

Thank you for your patience,
OpenAire Dev Team.

Close This Message


Verify Password:
Verify E-mail:
*All Fields Are Required.
Please Verify You Are Human:
fbtwitterlinkedinvimeoflicker grey 14rssslideshare1
Paterson, Maura B.; Stinson, D.R.; Wang, Y. (2016)
Publisher: Springer
Languages: English
Types: Article
Subjects: ems

Classified by OpenAIRE into

Low density parity check (LDPC) codes, LT codes and digital fountain techniques have received significant attention from both academics and industry in the past few years. By employing the underlying ideas of efficient Belief Propagation (BP) decoding process (also called iterative message passing decoding process) on binary erasure channels (BEC) in LDPC codes, Wang has recently introduced the concept of array BP-XOR codes and showed the necessary and sufficient conditions for MDS [k + 2,k] and [n,2] array BP-XOR codes. In this paper, we analyze the encoding symbol degree requirements for array BP-XOR codes and present new necessary conditions for array BP-XOR codes. These new necessary conditions are used as a guideline for constructing several array BP-XOR codes and for presenting a complete characterization (necessary and sufficient conditions) of degree two array BP-XOR codes and for designing new edge-colored graphs. Meanwhile, these new necessary conditions are used to show that the codes by Feng, Deng, Bao, and Shen in IEEE Transactions on Computers are incorrect.
  • The results below are discovered through our pilot algorithms. Let us know how we are doing!

    • [1] N. Alon, J. Edmonds, and M. Luby. Linear time erasure codes with nearly optimal recovery. In Proc. 36th FOCS, pages 512-. IEEE Computer Society, 1995.
    • [2] C. Berrou and A. Glavieux. Near optimum error correcting coding and decoding: Turbo-codes. Communications, IEEE Transactions on, 44(10):1261-1271, 1996.
    • [3] M. Blaum, J. Brady, J. Bruck, and J. Menon. EVENODD: An efficient scheme for tolerating double disk failures in raid architectures. IEEE Trans. Computers, 44(2):192-202, 1995.
    • [4] M. Blaum, J. Bruck, and E. Vardy. MDS array codes with independent parity symbols. IEEE Trans. on Information Theory, 42:529-542, 1996.
    • [5] M. Blaum and R. M. Roth. New array codes for multiple phased burst correction. IEEE Trans. on Information Theory, 39(1):66-77, 1993.
    • [6] M. Blaum and R. M. Roth. On lowest-density MDS codes. IEEE Trans. on Information Theory, 45:46-59, 1999.
    • [7] K.A. Bush. Orthogonal arrays of index unity. The Annals of Mathematical Statistics, 23(3):426-434, 1952.
    • [8] Yuval Cassuto and Jehoshua Bruck. Cyclic lowest density mds array codes. IEEE Trans. Inf. Theor., 55(4):1721-1729, April 2009.
    • [9] G.L. Feng, R.H. Deng, F. Bao, and J.C. Shen. New efficient MDS array codes for RAID. Part I. Reed-Solomon-like codes for tolerating three disk failures. IEEE Trans. Computers, 54(9):1071-1080, 2005.
    • [10] G.L. Feng, R.H. Deng, F. Bao, and J.C. Shen. New efficient MDS array codes for RAID. Part II. Rabin-like codes for tolerating multiple ( 4) disk failures. IEEE Trans. Computers, 54(12):1473-1483, 2005.
    • [11] R. G. Gallager. Low density Parity Check Codes. MIT Press, 1963.
    • [12] J.W.P. Hirschfeld, L. Storme, et al. The packing problem in statistics, coding theory and finite projective spaces: update 2001. Developments in Mathematics, 3:201-246, 2000.
    • [13] S. Kounias and CI Petros. Orthogonal arrays of strength three and four with index unity. Sankhya┬»: The Indian Journal of Statistics, Series B, pages 228-240, 1975.
    • [14] E. Louidor and R. M. Roth. Lowest density MDS codes over extension alphabets. IEEE Trans. Inf. Theor., 52(7):3186-3197, 2006.
    • [15] A. Lubotzky, R. Phillips, and P. Sarnak. Ramanujan graphs. Combinatorica, 8(3):261-277, 1988.
    • [16] M. Luby. LT codes. In Proc. FOCS, pages 271-280, 2002.
    • [17] M. Luby, M. Mitzenmacher, M. Shokrollahi, and D. Spielman. Efficient erasure correcting codes. IEEE Trans. Information Theory, 47:569-584, 2001.
    • [18] M. Luby, M. Mitzenmacher, M. Shokrollahi, D. Spielman, and V. Stemann. Practical loss-resilient codes. In Proc. 29th ACM STOC, pages 150-159. ACM, 1997.
    • [19] M. G. Luby, M. Mitzenmacher, and M. Amin Shokrollahi. Analysis of random processes via and-or tree evaluation. In In Proc. 9th Annual ACM-SIAM SODA, pages 364-373, 1998.
    • [20] D. MacKay and R. Neal. Good codes based on very sparse matrices. Cryptography and Coding, pages 100-111, 1995.
    • [21] D.J.C. MacKay. Good error-correcting codes based on very sparse matrices. IEEE Trans. Infor. Theory, 45(2):399-431, 1999.
    • [22] D.J.C. MacKay. Information theory, inference and learning algorithms. Cambridge university press, 2003.
    • [23] F. J. MacWilliams and N. J. A. Sloane. The theory of error-correcting codes. NH Pub. Company, 1978.
    • [24] G. Margulis. Explicit construction of concentrators. Probl. Inform. transm., 9:325-332, 1975.
    • [25] G.A. Margulis. Explicit constructions of graphs without short cycles and low density codes. Combinatorica, 2(1):71-78, 1982.
    • [26] MinT. Bound for oas with index unity. http:// mint.sbg.ac.at/ desc CBoundT0.html, 2012.
    • [27] J. Pearl. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann, 1988.
    • [28] R. Roth. Introduction to coding theory. Cambridge University Press, 2006.
    • [29] A. Shokrollahi. Raptor codes. IEEE Trans. on Inform. Theory, 52(6):2551-2567, 2006.
    • [30] M. Sipser and D. Spielman. Expander codes. IEEE Trans. Infor. Theo., 42(6):1710-1722, 1996.
    • [31] D.A. Spielman. Linear-time encodable and decodable error-correcting codes. IEEE Trans. Information Theory, 42(6):1723-1731, 1996.
    • [32] Yongge Wang. Efficient LDPC code based secret sharing schemes and private data storage in cloud without encryption. Technical report, UNC Charlotte, 2012.
    • [33] Yongge Wang. LT codes for efficient and reliable distributed storage systems revisited. Technical report, UNC Charlotte, submitted for publication, 2012.
    • [34] Yongge Wang and Yvo Desmedt. Edge-colored graphs with applications to homogeneous faults. Inf. Process. Lett., 111(13):634-641, 2011.
    • [35] Yongge Wang and Yvo Desmedt. Efficient secret sharing schemes achieving optimal information rate. Technical report, UNC Charlotte, 2012.
    • [36] L. Xu, V. Bohossian, J. Bruck, and D. Wagner. Low density mds codes and factors of complete graphs. IEEE Trans. Inf. Theor., 45:1817-1826, 1998.
    • [37] L. Xu and J. Bruck. X-code: Mds array codes with optimal encoding. IEEE Trans. on Information Theory, 45:272-276, 1999.
  • No related research data.
  • No similar publications.

Share - Bookmark

Cite this article