On encoding symbol degrees of array BP-XOR codes

详细信息    查看全文

• 作者：Maura B. Paterson ; Douglas R. Stinson ; Yongge Wang
• 关键词：Array codes ; Encoding symble degrees ; MDS array codes ; Bounds on codes ; Error corecting codes
• 刊名：Cryptography and Communications
• 出版年：2016
• 出版时间：January 2016
• 年：2016
• 卷：8
• 期：1
• 页码：19-32
• 全文大小：383 KB
• 参考文献：1.Alon, N., Edmonds, J., Luby, M.: Linear time erasure codes with nearly optimal recovery. In: Proc. 36th FOCS, pages 512–519. IEEE Computer Society (1995)
  2.Berrou, C., Glavieux, A.: Near optimum error correcting coding and decoding: Turbo-codes. Communications, IEEE Transactions on 44(10), 1261–1271 (1996)CrossRef
  3.Blaum, M.: A family of mds array codes with minimal number of encoding operations. In: Proc. IEEE ISIT 2006, pages 2784–2788. IEEE (2006)
  4.Blaum, M., Brady, J., Bruck, J., Menon, J.: EVENODD: An efficient scheme for tolerating double disk failures in raid architectures. IEEE Trans. Comput. 44(2), 192–202 (1995)CrossRef MATH
  5.Blaum, M., Bruck, J., Vardy, E.: MDS array codes with independent parity symbols. IEEE Trans. Inf. Theory 42, 529–542 (1996)CrossRef MATH
  6.Blaum, M., Roth, R.M.: New array codes for multiple phased burst correction. IEEE Trans. Inf. Theory 39(1), 66–77 (1993)MathSciNet CrossRef MATH
  7.Blaum, M., Roth, R.M.: On lowest-density MDS codes. IEEE Trans. Inf. Theory 45, 46–59 (1999)MathSciNet CrossRef MATH
  8.Bush, K.A.: Orthogonal arrays of index unity. Ann. Math. Stat. 23(3), 426–434 (1952)MathSciNet CrossRef MATH
  9.Cassuto, Y., Shokrollahi, A.: Ldpc codes for 2d arrays. Information Theory, IEEE Transactions on 60(6), 3279–3291 (2014)MathSciNet CrossRef
  10.Cassuto, Yuval, Bruck, Jehoshua: Cyclic lowest density mds array codes. IEEE Trans. Inf. Theor. 55(4), 1721–1729 (2009)MathSciNet CrossRef
  11.Feng, G.L., Deng, R.H., Bao, F., Shen, J.C.: New efficient MDS array codes for RAID. Part I. Reed-Solomon-like codes for tolerating three disk failures. IEEE Trans. Comput. 54(9), 1071–1080 (2005)CrossRef
  12.Feng, G.L., Deng, R.H., Bao, F., Shen, J.C.: New efficient MDS array codes for RAID. Part II. Rabin-like codes for tolerating multiple (≥4) disk failures. IEEE Trans. Comput. 54(12), 1473–1483 (2005)CrossRef
  13.Semakov, N.V., Zaitsev, G.V., Zinov’ev, V.A.: Minimum-check-density codes for correcting bytes of errors, erasures, or defects. Probl. Inf. Transm. 19(3), 197–204 (1983)MathSciNet MATH
  14.Gallager, R.G.: Low density Parity Check Codes. MIT Press (1963)
  15.Hirschfeld, J.W.P., Storme, L., et al.: The packing problem in statistics, coding theory and finite projective spaces: update 2001. Developments in Mathematics 3, 201–246 (2000)MathSciNet CrossRef MATH
  16.Huang, C., Xu, L.: STAR: an efficient coding scheme for correcting triple storage node failures. In: FAST, pages 197–210 (2005)
  17.Kounias, S., Petros, CI: Orthogonal arrays of strength three and four with index unity. Sankhyā: The Indian Journal of Statistics Series B, 228–240 (1975)
  18.Louidor, E., Roth, R.M.: Lowest density MDS codes over extension alphabets. IEEE Trans. Inf. Theor. 52(7), 3186–3197 (2006)MathSciNet CrossRef MATH
  19.Lubotzky, A., Phillips, R., Sarnak, P.: Ramanujan graphs. Combinatorica 8(3), 261–277 (1988)MathSciNet CrossRef MATH
  20.Luby, M.: LT codes. In: Proc. FOCS, pages 271–280 (2002)
  21.Luby, M., Mitzenmacher, M., Shokrollahi, M., Spielman, D., Stemann, V.: Practical loss-resilient codes. In: Proc. 29th ACM STOC, pages 150–159. ACM (1997)
  22.Luby, M.G., Mitzenmacher, M., Amin Shokrollahi, M.: Analysis of random processes via and-or tree evaluation. In: In Proc 9th Annual ACM-SIAM SODA, 364–373 (1998)
  23.MacKay, D., Neal, R.: Good codes based on very sparse matrices. Cryptography and Coding, 100–111 (1995)
  24.MacKay, D.J.C.: Good error-correcting codes based on very sparse matrices. IEEE Trans. Infor. Theory 45(2), 399–431 (1999)MathSciNet CrossRef MATH
  25.MacKay, D.J.C.: Information theory, inference and learning algorithms. Cambridge university press (2003)
  26.MacWilliams, F.J., Sloane, N.J.A.: The theory of error-correcting codes. NH Pub. Company (1978)
  27.Margulis, G.: Explicit construction of concentrators. Probl. Inform. transm. 9, 325–332 (1975)MathSciNet
  28.Margulis, G.A.: Explicit constructions of graphs without short cycles and low density codes. Combinatorica 2(1), 71–78 (1982)MathSciNet CrossRef MATH
  29.MinT: Bound for oas with index unity, URL http://​mint.​sbg.​ac.​at/​desc_​CBoundT0.​html (2012)
  30.Pearl, J.: Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference, Morgan Kaufmann (1988)
  31.Roth, R.: Introduction to coding theory. Cambridge University Press (2006)
  32.Shokrollahi, A.: Raptor codes. IEEE Trans. on Inform. Theory 52(6), 2551–2567 (2006)MathSciNet CrossRef MATH
  33.Sipser, M., Spielman, D.: Expander codes. IEEE Trans. Infor. Theo. 42(6), 1710–1722 (1996)MathSciNet CrossRef MATH
  34.Spielman, D.A., Linear-time encodable and decodable error-correcting codes. IEEE Trans. Inf. Theory 42(6), 1723–1731 (1996)CrossRef
  35.Wang, Yongge: Resource bounded randomness and computational complexity. Theoret. Comput. Sci. 237, 33–55 (2000)MathSciNet CrossRef MATH
  36.Wang, Yongge: Insecure “provably” secure network coding and homomorphic authentication sechemes for network coding, Available at http://​coitweb.​uncc.​edu/​yonwang/​papers/​ncattack.​pdf (2010)
  37.Wang, Yongge: Array BP-XOR codes for reliable cloud storage systems. In: Proc IEEE ISIT 2013, pages 326–330. IEEE Press (2013)
  38.Wang, Yongge : Privacy-preserving data storage in cloud using array BP-XOR codes, IEEE Trandactions on Cloud Computing (2015)
  39.Wang, Yongge, Desmedt, Yvo: Edge-colored graphs with applications to homogeneous faults. Inf. Process. Lett. 111(13), 634–641 (2011)MathSciNet CrossRef MATH
  40.Wang, Yongge, Desmedt, Yvo: Homogeneous faults, colored edge graphs, and cover free families. In: ICITS, pages 58–72 (2011)
  41.Wang, Z.: Private communication (2014)
  42.Xu, L., Bohossian, V., Bruck, J., Wagner, D.: Low density mds codes and factors of complete graphs. IEEE Trans. Inf. Theor. 45, 1817–1826 (1998)MathSciNet MATH
  43.Xu, L., Bruck, J.: X-code: Mds array codes with optimal encoding. IEEE Trans. on Information Theory 45, 272–276 (1999)MathSciNet CrossRef MATH
  
• 作者单位：Maura B. Paterson (1)
  Douglas R. Stinson (2)
  Yongge Wang (3)
  
  1. Department Economics, Mathematics and Statistics, Birkbeck University of London, Malet Street, London, WC1E 7HX, UK
  2. David R. Cheriton School of Computer Science, University of Waterloo, 200 University Ave W, Waterloo, ON, N2L 3G1, Canada
  3. Department of Software and Information Systems, UNC Charlotte, Charlotte, NC, 28223, USA
  
• 刊物类别：Computer Science
• 刊物主题：Coding and Information Theory
  Mathematics of Computing
  
• 出版者：Springer New York
• ISSN：1936-2455

文摘

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.