Skip to main content
Erschienen in: Designs, Codes and Cryptography 1/2017

15.04.2016

On MDS convolutional codes over \({\mathbb {Z}}_{p^{r}}\)

verfasst von: Diego Napp, Raquel Pinto, Marisa Toste

Erschienen in: Designs, Codes and Cryptography | Ausgabe 1/2017

Einloggen, um Zugang zu erhalten

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Maximum distance separable (MDS) convolutional codes are characterized through the property that the free distance meets the generalized Singleton bound. The existence of free MDS convolutional codes over \({\mathbb {Z}}_{p^{r}}\) was recently discovered in Oued and Sole (IEEE Trans Inf Theory 59(11):7305–7313, 2013) via the Hensel lift of a cyclic code. In this paper we further investigate this important class of convolutional codes over \({\mathbb {Z}}_{p^{r}}\) from a new perspective. We introduce the notions of p-standard form and r-optimal parameters to derive a novel upper bound of Singleton type on the free distance. Moreover, we present a constructive method for building general (non necessarily free) MDS convolutional codes over \({\mathbb {Z}}_{p^{r}}\) for any given set of parameters.
Literatur
1.
Zurück zum Zitat Almeida P., Napp D., Pinto R.: A new class of superregular matrices and MDP convolutional codes. Linear Algebr. Appl. 439(7), 2145–2157 (2013). Almeida P., Napp D., Pinto R.: A new class of superregular matrices and MDP convolutional codes. Linear Algebr. Appl. 439(7), 2145–2157 (2013).
2.
Zurück zum Zitat Ashikhmin A., Zyablov V.: Samples of unit-memory codes over \({\mathbb{Z}}_{4}\). In: Proceedings of IEEE International Workshop on Information Theory, Moscow, Russia, pp. 119–121 (1994). Ashikhmin A., Zyablov V.: Samples of unit-memory codes over \({\mathbb{Z}}_{4}\). In: Proceedings of IEEE International Workshop on Information Theory, Moscow, Russia, pp. 119–121 (1994).
3.
Zurück zum Zitat Calderbank A.R., Sloane N.J.A.: Modular and p-adic cyclic codes. Des. Codes Cryptogr. 6(1), 21–35 (1995). Calderbank A.R., Sloane N.J.A.: Modular and p-adic cyclic codes. Des. Codes Cryptogr. 6(1), 21–35 (1995).
4.
Zurück zum Zitat Chang S.K., Gill A.: Algorithmic solution of the change-making problem. Assoc. Comput. Mach. 17(1), 113–122 (1970). Chang S.K., Gill A.: Algorithmic solution of the change-making problem. Assoc. Comput. Mach. 17(1), 113–122 (1970).
5.
Zurück zum Zitat Chen C.J., Chen T.Y., Loeliger H.A.: Construction of linear ring codes for 6 PSK. IEEE Trans. Inf. Theory 40(2), 563–566 (1994). Chen C.J., Chen T.Y., Loeliger H.A.: Construction of linear ring codes for 6 PSK. IEEE Trans. Inf. Theory 40(2), 563–566 (1994).
6.
Zurück zum Zitat Fagnani F., Zampieri S.: Canonical kernel representations for behaviors over finite abelian groups. Syst. Control Lett. 32(5), 271–282 (1997). Fagnani F., Zampieri S.: Canonical kernel representations for behaviors over finite abelian groups. Syst. Control Lett. 32(5), 271–282 (1997).
7.
Zurück zum Zitat Fagnani F., Zampieri S.: System-theoretic properties of convolutional codes over rings. IEEE Trans. Inf. Theory 47(6), 2256–2274 (2001). Fagnani F., Zampieri S.: System-theoretic properties of convolutional codes over rings. IEEE Trans. Inf. Theory 47(6), 2256–2274 (2001).
8.
Zurück zum Zitat Greferath M., Schmidt S.E.: Finite-ring combinatorics and macwilliams’ equivalence theorem. J. Comb. Theory Ser. A 92(1), 17–28 (2000). Greferath M., Schmidt S.E.: Finite-ring combinatorics and macwilliams’ equivalence theorem. J. Comb. Theory Ser. A 92(1), 17–28 (2000).
9.
Zurück zum Zitat Guardia G.G.L.: On classical and quantum mds-convolutional bch codes. IEEE Trans. Inf. Theory 60(1), 304–312 (2014). Guardia G.G.L.: On classical and quantum mds-convolutional bch codes. IEEE Trans. Inf. Theory 60(1), 304–312 (2014).
10.
Zurück zum Zitat Guendaa K., Gulliver T.A.: MDS and self-dual codes over rings. Finite Fields Appl.18(6), 1061–1075 (2012). Guendaa K., Gulliver T.A.: MDS and self-dual codes over rings. Finite Fields Appl.18(6), 1061–1075 (2012).
11.
Zurück zum Zitat Johannesson R., Wittenmark E.: Two 16-state, rate r=2/4 trellis codes whose free distances meet the heller bound. IEEE Trans. Inf. Theory 44(4), 1602–1604 (1998). Johannesson R., Wittenmark E.: Two 16-state, rate r=2/4 trellis codes whose free distances meet the heller bound. IEEE Trans. Inf. Theory 44(4), 1602–1604 (1998).
12.
Zurück zum Zitat Johannesson R., Zigangirov K.S.: Fundamentals of Convolutional Coding. IEEE Press, New York (1999). Johannesson R., Zigangirov K.S.: Fundamentals of Convolutional Coding. IEEE Press, New York (1999).
13.
Zurück zum Zitat Johannesson R., Wan Z., Wittenmark E.: Some structural properties of convolutional codes over rings. IEEE Trans. Inf. Theory 44(2), 839–845 (1998). Johannesson R., Wan Z., Wittenmark E.: Some structural properties of convolutional codes over rings. IEEE Trans. Inf. Theory 44(2), 839–845 (1998).
14.
Zurück zum Zitat Kötter R., Dettmar U., Sorger U.K.: On the construction of trellis codes based on (P)UM codes over \({\mathbb{Z}}_4\). Probl. Inf. Transm. 31(2), 154–161 (1995). Kötter R., Dettmar U., Sorger U.K.: On the construction of trellis codes based on (P)UM codes over \({\mathbb{Z}}_4\). Probl. Inf. Transm. 31(2), 154–161 (1995).
15.
Zurück zum Zitat Kuijper M., Pinto R.: Minimal trellis construction for finite support convolutional ring codes. Lecture Notes in Computer Science. Coding Theory Appl. 5228, 95–106 (2008). Kuijper M., Pinto R.: Minimal trellis construction for finite support convolutional ring codes. Lecture Notes in Computer Science. Coding Theory Appl. 5228, 95–106 (2008).
16.
Zurück zum Zitat Kuijper M., Pinto R.: On minimality of convolutional ring encoders. IEEE Trans. Autom. Control 55(11), 4890–4897 (2009). Kuijper M., Pinto R.: On minimality of convolutional ring encoders. IEEE Trans. Autom. Control 55(11), 4890–4897 (2009).
17.
Zurück zum Zitat Kuijper M., Pinto R., Polderman J.W.: The predictable degree property and row reducedness for systems over a finite ring. Linear Algebr. Appl. 425(2–3), 776–796 (2007). Kuijper M., Pinto R., Polderman J.W.: The predictable degree property and row reducedness for systems over a finite ring. Linear Algebr. Appl. 425(2–3), 776–796 (2007).
18.
Zurück zum Zitat Massey J.L., Mittelholzer T.: Convolutional codes over rings. In: Proceedings of 4th Joint Swedish-Soviet International Workshop Information Theory, pp. 14–18 (1989). Massey J.L., Mittelholzer T.: Convolutional codes over rings. In: Proceedings of 4th Joint Swedish-Soviet International Workshop Information Theory, pp. 14–18 (1989).
19.
Zurück zum Zitat McDonald B.: Finite Rings with Identity. Marcel Dekker, New York (1974). McDonald B.: Finite Rings with Identity. Marcel Dekker, New York (1974).
20.
Zurück zum Zitat McEliece R.J.: The algebraic theory of convolutional codes. In: Pless V., Huffman W. (eds.) Handbook of Coding Theory, vol. 1, pp. 1065–1138. Elsevier Science Publishers, Amsterdam (1998). McEliece R.J.: The algebraic theory of convolutional codes. In: Pless V., Huffman W. (eds.) Handbook of Coding Theory, vol. 1, pp. 1065–1138. Elsevier Science Publishers, Amsterdam (1998).
21.
Zurück zum Zitat Napp D., Smarandache R.: Constructing strongly mds convolutional codes with maximum distance profile. Adv. Math. Commun. 10(2), (2016). doi:10.3934/amc.2016005. Napp D., Smarandache R.: Constructing strongly mds convolutional codes with maximum distance profile. Adv. Math. Commun. 10(2), (2016). doi:10.​3934/​amc.​2016005.
22.
Zurück zum Zitat 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., Perea C., Pinto R.: Input-state-output representations and constructions of finite support 2D convolutional codes. Adv. Math. Commun. 4(4), 533–545 (2010).
23.
Zurück zum Zitat Norton G.: On minimal realization over a finite chain ring. Des Codes Cryptogr. 16(2), 161–178 (1999). Norton G.: On minimal realization over a finite chain ring. Des Codes Cryptogr. 16(2), 161–178 (1999).
24.
Zurück zum Zitat Norton G., Salagean A.: On the key equation over a commutative ring. Des Codes Cryptogr. 20(2), 125–141 (2000). Norton G., Salagean A.: On the key equation over a commutative ring. Des Codes Cryptogr. 20(2), 125–141 (2000).
25.
Zurück zum Zitat Norton G.H., Salagean A.: On the hamming distance of linear codes over a finite chain ring. IEEE Trans. Inf. Theory 46(3), 1060–1067 (2001). Norton G.H., Salagean A.: On the hamming distance of linear codes over a finite chain ring. IEEE Trans. Inf. Theory 46(3), 1060–1067 (2001).
26.
Zurück zum Zitat Oued M.E., Sole P.: MDS convolutional codes over a finite ring. IEEE Trans. Inf. Theory 59(11), 7305–7313 (2013). Oued M.E., Sole P.: MDS convolutional codes over a finite ring. IEEE Trans. Inf. Theory 59(11), 7305–7313 (2013).
27.
Zurück zum Zitat Rosenthal J., Smarandache R.: Maximum distance separable convolutional codes. Appl. Algebr. Eng. Commun. Comput. 10(1), 15–32 (1999). Rosenthal J., Smarandache R.: Maximum distance separable convolutional codes. Appl. Algebr. Eng. Commun. Comput. 10(1), 15–32 (1999).
28.
Zurück zum Zitat Rosenthal J., Schumacher J.M., York E.V.: On behaviors and convolutional codes. IEEE Trans. Autom. Control 42(6, part 1), 1881–1891 (1996). Rosenthal J., Schumacher J.M., York E.V.: On behaviors and convolutional codes. IEEE Trans. Autom. Control 42(6, part 1), 1881–1891 (1996).
29.
Zurück zum Zitat Smarandache R., Gluesing-Luerssen H., Rosenthal J.: Constructions for MDS-convolutional codes. IEEE Trans. Autom. Control 47(5), 2045–2049 (2001). Smarandache R., Gluesing-Luerssen H., Rosenthal J.: Constructions for MDS-convolutional codes. IEEE Trans. Autom. Control 47(5), 2045–2049 (2001).
30.
Zurück zum Zitat Sole P., Sison V.: Quaternary convolutional codes from linear block codes over galois rings. IEEE Trans. Inf. Theory 53, 2267–2270 (2007). Sole P., Sison V.: Quaternary convolutional codes from linear block codes over galois rings. IEEE Trans. Inf. Theory 53, 2267–2270 (2007).
31.
Zurück zum Zitat Vazirani V., Saran H., Rajan B.: An efficient algorithm for constructing minimal trellises for codes over finite abelian groups. IEEE Trans. Inf. Theory 42, 1839–1854 (1996). Vazirani V., Saran H., Rajan B.: An efficient algorithm for constructing minimal trellises for codes over finite abelian groups. IEEE Trans. Inf. Theory 42, 1839–1854 (1996).
Metadaten
Titel
On MDS convolutional codes over
verfasst von
Diego Napp
Raquel Pinto
Marisa Toste
Publikationsdatum
15.04.2016
Verlag
Springer US
Erschienen in
Designs, Codes and Cryptography / Ausgabe 1/2017
Print ISSN: 0925-1022
Elektronische ISSN: 1573-7586
DOI
https://doi.org/10.1007/s10623-016-0204-9

Weitere Artikel der Ausgabe 1/2017

Designs, Codes and Cryptography 1/2017 Zur Ausgabe