Abstract
Two dimensional (2D) convolutional codes is a class of codes that generalizes standard one-dimensional (1D) convolutional codes in order to treat two dimensional data. In this paper we present a novel and concrete construction of 2D convolutional codes with the particular property that their projection onto the horizontal lines yield optimal [in the sense of Almeida et al. (Linear Algebra Appl 499:1–25, 2016)] 1D convolutional codes with a certain rate and certain Forney indices. Moreover, using this property we show that the proposed constructions are indeed maximum distance separable, i.e., are 2D convolutional codes having the maximum possible distance among all 2D convolutional codes with the same parameters. The key idea is to use a particular type of superregular matrices to build the generator matrix.
Similar content being viewed by others
References
Almeida P., Napp D., Pinto R.: A new class of superregular matrices and MDP convolutional codes. Linear Algebra Appl. 439(7), 2145–2157 (2013).
Almeida P., Napp D., Pinto R.: Superregular matrices and applications to convolutional codes. Linear Algebra Appl. 499, 1–25 (2016).
Charoenlarpnopparut C., Bose N.K.: Grobner bases for problem solving in multidimensional systems. Multidimens. Syst. Signal Process. 12(3), 365–376 (2001).
Climent J.J., Napp D., Perea C., Pinto R.: A construction of MDS \(2\)D convolutional codes of rate \(1/n\) based on superregular matrices. Linear Algebra Appl. 437, 766–780 (2012).
Climent J.J., Napp D., Perea C., Pinto R.: Maximum distance separable 2D convolutional codes. IEEE Trans. Inf. Theory 62(2), 669–680 (2016).
Climent J.J., Napp D., Pinto R., Simões R.: Decoding of 2D convolutional codes over the erasure channel. Adv. Math. Commun. 10(1), 179–193 (2016).
El Oued M., Sole P.: MDS convolutional codes over a finite ring. IEEE Trans. Inf. Theory 59(11), 7305–7313 (2013).
Fornasini E., Valcher M.E.: Algebraic aspects of two-dimensional convolutional codes. IEEE Trans. Inf. Theory 40(4), 1068–1082 (1994).
Gluesing-Luerssen H., Rosenthal J., Smarandache R.: Strongly MDS convolutional codes. IEEE Trans. Inf. Theory 52(2), 584–598 (2006).
Hansen J., Østergaard J., Kudahl J., Madsen J.: On the construction of jointly superregular lower triangular Toeplitz matrices. International Symposium on Information Theory (ISIT) (2016).
Hutchinson R.: The existence of strongly MDS convolutional codes. SIAM J. Control Optim. 47(6), 2812–2826 (2008).
Hutchinson R., Smarandache R., Trumpf J.: On superregular matrices and MDP convolutional codes. Linear Algebra Appl. 428, 2585–2596 (2008).
Justesen J., Forchhammer S.: Two Dimensional Information Theory and Coding. With Applications to Graphics Data and High-Density Storage Media. Cambridge University Press, Cambridge (2010).
La Guardia G.: On classical and quantum MDS-convolutional BCH codes. IEEE Trans. Inf. Theory 60(1), 304–312 (2013).
Lobo R.G., Bitzer D.L., Vouk M.A.: On locally invertible encoders and muldimensional convolutional codes. IEEE Trans. Inf. Theory 58(3), 1774–1782 (2012).
Mahmood R., Badr A., Khisti A.: Convolutional codes with maximum column sum rank for network streaming. IEEE Trans. Inf. Theory 62(6), 3039–3052 (2016).
McEliece R.J.: The algebraic theory of convolutional codes. In: Pless V., Huffman W.C. (eds.) Handbook of Coding Theory, vol. 1, pp. 1065–1138. Elsevier Science Publishers, Amsterdam (1998).
Napp D., Perea C., Pinto R.: Input-state-output representations and constructions of finite support 2D convolutional codes. Adv. Math. Commun. 4(4), 533–545 (2010).
Napp D., Pinto R., Toste T.: On MDS convolutional codes over \({\mathbb{Z}}_{p^r}\). Des. Codes Cryptogr. 83, 101–114 (2017).
Norton G.: On minimal realization over a finite chain ring. Des. Codes Cryptogr. 16(2), 161–178 (1999).
Ozbudak F., Ozkaya B.: A minimum distance bound for quasi-nd-cyclic codes. Finite Fields Appl. 41, 193–222 (2016).
Pinho T., Pinto R., Rocha P.: Realization of 2D convolutional codes of rate \(\frac{1}{n}\) by separable Roesser models. Des. Codes Cryptogr. 70(1), 241–250 (2014).
Rosenthal J., York E.V.: BCH convolutional codes. IEEE Trans. Inf. Theory 45(6), 1833–1844 (1999).
Roth R.M., Lempel A.: On MDS codes via Cauchy matrices. IEEE Trans. Inf. Theory 35(6), 1314–1319 (1989).
Smarandache R., Gluesing-Luerssen H., Rosenthal J.: Constructions of MDS-convolutional codes. IEEE Trans. Automat. Control 47(5), 2045–2049 (2001).
Tomás V.: Complete-MDP Convolutional Codes over the Erasure Channel. PhD thesis, Departamento de Ciencia de la Computación e Inteligencia Artificial, Universidad de Alicante, Alicante, España (2010).
Tomás V., Rosenthal J., Smarandache R.: Decoding of MDP convolutional codes over the erasure channel. In: Proceedings of the 2009 IEEE International Symposium on Information Theory (ISIT 2009), pp. 556–560, Seoul, Korea (2009). IEEE.
Tomas V., Rosenthal J., Smarandache R.: Decoding of convolutional codes over the erasure channel. IEEE Trans. Inf. Theory 58(1), 90–108 (2012).
Valcher M.E., Fornasini E.: On 2D finite support convolutional codes: an algebraic approach. Multidimens. Syst. Signal Process. 5, 231–243 (1994).
Weiner P.: Muldimensional Convolutional Codes. PhD dissertation, University of Notre Dame, USA (1998).
Acknowledgements
The authors are grateful to the anonymous referees for the many insightful comments. This work was supported by Portuguese funds through the CIDMA - Center for Research and Development in Mathematics and Applications, and the Portuguese Foundation for Science and Technology (FCT-Fundação para a Ciência e a Tecnologia), within Project UID/MAT/04106/2013.
Author information
Authors and Affiliations
Corresponding author
Additional information
This is one of several papers published in Designs, Codes and Cryptography comprising the Special Issue on Network Coding and Designs.
Rights and permissions
About this article
Cite this article
Almeida, P., Napp, D. & Pinto, R. MDS 2D convolutional codes with optimal 1D horizontal projections. Des. Codes Cryptogr. 86, 285–302 (2018). https://doi.org/10.1007/s10623-017-0357-1
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10623-017-0357-1