On encoding symbol degrees of array BP-XOR codes

Article English OPEN
Paterson, Maura B. ; Stinson, D.R. ; Wang, Y. (2016)

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.
  • References (37)
    37 references, page 1 of 4

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

  • Metrics
    0
    views in OpenAIRE
    0
    views in local repository
    10
    downloads in local repository

    The information is available from the following content providers:

    From Number Of Views Number Of Downloads
    Birkbeck Institutional Research Online - IRUS-UK 0 10
Share - Bookmark