Recovering erasures by using MDS codes over extension alphabets

Springer Science and Business Media LLC - Tập 73 - Trang 85-95 - 2015
Sara D. Cardell1, Joan-Josep Climent2
1Instituto de Matemática, Estatística e Computação Científica, Universidade Estadual de Campinas (UNICAMP), Campinas, Brazil
2Departament de Matemàtiques, Universitat d’Alacant, Alacant, Spain

Tóm tắt

A new family of $${\mathbb {F}}_{q}$$ -linear codes over $${\mathbb {F}}_{q}^{b}$$ can be obtained replacing the elements in the large field $${\mathbb {F}}_{q^{b}}$$ by elements in $${\mathbb {F}}_{q}[C]$$ , where C is the companion matrix of a primitive polynomial of degree b and coefficients in $${\mathbb {F}}_{q}$$ . In this work, we propose a decoding algorithm for this family of $${\mathbb {F}}_{q}$$ -linear codes over the erasure channel, based on solving linear systems over the field  $${\mathbb {F}}_{q}$$ .

Tài liệu tham khảo

Blaum, M., Brady, J., Bruck, J., Menon, J.: EVENODD: an efficient scheme for tolerating double disk failures in RAID architectures. IEEE Trans. Comput. 42(2), 192–202 (1995) Blaum, M., Bruck, J., Vardy, A.: MDS array codes with independent parity symbols. IEEE Trans. Inf. Theory 42(2), 529–542 (1996) Blaum, M., Fan, J.L., Xu, L.: Soft decoding of several classes of array codes. In: Proceedings of the 2002 IEEE International Symposium on Information Theory (ISIT 2002), p 368, Lausanne, Switzerland. IEEE (2002) Blaum, M., Farrell, P.G., van Tilborg, H.C.A.: Array codes. In: Pless, V.S., Huffman, W.C. (eds.) Handbook of Coding Theory, pp. 1855–1909. Elsevier, North-Holland (1998) Blaum, M., Roth, R.M.: New array codes for multiple phased burst correction. IEEE Trans. Inf. Theory 39(1), 66–77 (1993) Blaum, M., Roth, R.M.: On lowest density MDS codes. IEEE Trans. Inf. Theory 45(1), 46–59 (1999) Blömer, J., Kalfane, M., Karp, R., Karpinski, M., Luby, M., Suckerman, D.: An XOR-based erasure-resilient coding scheme. Technical Report TR-95-048, International Computer Science Institute, Berkeley, CA (1995) Cardell, S.D.: Constructions of MDS codes over extension alphabets. Ph.D. thesis, Departamento de Ciencia de la Computación e Inteligencia Artificial, Universidad de Alicante, Alicante, España (2012) Cardell, S.D., Climent, J.-J., Requena, V.: A construction of MDS array codes. WIT Trans. Inf. Commun. Technol. 45, 47–58 (2013) Chee, Y.M., Colbourn, C.J., Ling, A.C.H.: Asymptotically optimal erasure-resilient codes for large disk arrays. Discret. Appl. Math. 102, 3–36 (2000) Chen, C.L.: Byte-oriented error-correcting codes for semiconductor memory systems. IEEE Trans. Comput. 35(7), 646–648 (1986) Chen, C.L., Curran, B.W.: Switching codes for delta-I noise reduction. IEEE Trans. Comput. 45(9), 1017–1021 (1996) Elias, P.: Coding for noisy channels. In: IRE International Convention Record, part 4, pp. 37–46 (1955) Hill, R.: A First Course in Coding Theory. Oxford University Press, New York (1986) Hutchinson, R., Smarandache, R., Trumpf, J.: On superregular matrices and MDP convolutional codes. Linear Algebra Appl. 428, 2585–2596 (2008) Kousa, M.A., Mugaibel, A.H.: Cell loss recovery using two-dimensional erasure correction for ATM networks. In: Proceedings of the Seventh International Conference on Telecommunication Systems, Nashville, TN, pp. 85–89 (1999) Lacan, J., Fimes, J.: A construction of matrices with no singular square submatrices. In: Mullen, G.L., Poli, A., Stichtenoth, H. (eds.) Finite Fields and Applications. Lecture Notes in Computer Science, vol. 2948, pp. 145–147. Springer, Berlin (2003) Lacan, J., Fimes, J.: Systematic MDS erasure codes based on Vandermonde matrices. IEEE Commun. Lett. 8(9), 570–572 (2004) Lidl, R., Niederreiter, H.: Introduction to Finite Fields and Their Applications, 2nd edn. Cambridge University Press, New York (1994) MacWilliams, F.J., Sloane, N.J.A.: The Theory of Error-Correcting Codes, 6th edn. North-Holland, Amsterdam (1988) Reed, I.S., Solomon, G.: Polynomial codes over certain finite fields. J. Soc. Ind. Appl. Math. 8(2), 300–304 (1960) Roman, S.: Coding and Information Theory. Springer, New York (1992) Roth, R.M., Lempel, A.: On MDS codes via Cauchy matrices. IEEE Trans. Inf. Theory 35(6), 1314–1319 (1989) Roth, R.M., Seroussi, G.: On generator matrices of MDS codes. IEEE Trans. Inf. Theory 31(6), 826–830 (1985) Sweeney, P.: Error Correcting Coding. Wiley, West Sussex (2002) Tomás, V., Rosenthal, J., Smarandache, R.: Decoding of convolutional codes over the erasure channel. IEEE Trans. Inf. Theory 58(1), 90–108 (2012) Wang, Z., Dimakis, A.G., Bruck, J.: Rebuilding for array codes in distributed storage systems. In: Proceedings of the IEEE Globecom 2010 Workshop on Application of Communication Theory to Emerging Memory Technologies, Miami, FL, pp. 1909–1909. IEEE (2010)