doi: 10.3934/amc.2020061

On perfect poset codes

1. 

Center of Exact Sciences and Engineering, State University of West Paraná, Foz do Iguaçu, Paraná, Brazil

2. 

ILACVN - Federal University for Latin American Integration, Foz do Iguaçu, Paraná, Brazil

3. 

Polytechnic Center - Department of Mathematics, Federal University of Paraná, Curitiba, Paraná, Brazil

4. 

IMECC - Department of Mathematics, University of Campinas, Campinas, São Paulo, Brazil

* Corresponding author: Luciano Panek, luciano.panek@unioeste.br

Received  December 2018 Revised  September 2019 Published  January 2020

Fund Project: The second author was partially supported by São Paulo Research Foundation (FAPESP), grant 2017/10018-5. The third author was partially supported by CNPq, grant 306583/2016-0. The fourth author was partially supported by São Paulo Research Foundation (FAPESP), grant 2013/25977 and by CNPq, grant 304046/2017-5.

We consider on $ \mathbb{F}_{q}^{n} $ metrics determined by posets and classify the parameters of $ 1 $-perfect poset codes in such metrics. We show that a code with same parameters of a $ 1 $-perfect poset code is not necessarily perfect, however, we give necessary and sufficient conditions for this to be true. Furthermore, we characterize the unique way up to a labeling on the poset, considering some conditions, to extend an $ r $-perfect poset code over $ \mathbb{F}_q^n $ to an $ r $-perfect poset code over $ \mathbb{F}_q^{n+m} $.

Citation: Luciano Panek, Jerry Anderson Pinheiro, Marcelo Muniz Alves, Marcelo Firer. On perfect poset codes. Advances in Mathematics of Communications, doi: 10.3934/amc.2020061
References:
[1]

J. AhnH. K. KimJ. S. Kim and M. Kim, Classification of perfect linear codes with crown poset structure, Discrete Mathematics, 268 (2003), 21-30.  doi: 10.1016/S0012-365X(02)00679-9.  Google Scholar

[2]

M. M. S. AlvesL. Panek and M. Firer, Error-block codes and poset metrics, Advances in Mathematics of Communications, 2 (2008), 95-111.  doi: 10.3934/amc.2008.2.95.  Google Scholar

[3]

A. BargL. V. FelixM. Firer and M. V. P. Spreafico, Linear codes on posets with extension property, Discrete Mathematics, 317 (2014), 1-13.  doi: 10.1016/j.disc.2013.11.001.  Google Scholar

[4]

A. Barg and W. Park, On linear ordered codes, Moscow Mathematical J., 15 (2015), 679-702.  doi: 10.17323/1609-4514-2015-15-4-679-702.  Google Scholar

[5]

R. BrualdiJ. S. Graves and M. Lawrence, Codes with a poset metric, Discrete Mathematics, 147 (1995), 57-72.  doi: 10.1016/0012-365X(94)00228-B.  Google Scholar

[6]

B. K. DassN. Sharma and R. Verma, Perfect codes in poset spaces and poset block spaces, Finite Fields and Their Applications, 46 (2017), 90-106.  doi: 10.1016/j.ffa.2017.02.003.  Google Scholar

[7]

L. V. Felix and M. Firer, Canonical-systematic form for codes in hierarchical poset metrics, Advances in Mathematics of Communications, 6 (2012), 315-328.  doi: 10.3934/amc.2012.6.315.  Google Scholar

[8]

M. Firer, M. M. S. Alves, J. A. Pinheiro and L. Panek, Poset Codes: Partial Orders, Metrics and Coding Theory, SpringerBriefs in Mathematics. Springer, Cham, 2018. doi: 10.1007/978-3-319-93821-9.  Google Scholar

[9]

M. Firer and J. A. Pinheiro, Bounds for complexity of syndrome decoding for poset metrics, 2015 IEEE Information Theory Workshop, (2015), 1–5. doi: 10.1109/ITW.2015.7133130.  Google Scholar

[10] W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes, Cambridge University Press, Cambridge, 2003.  doi: 10.1017/CBO9780511807077.  Google Scholar
[11]

J. Y. Hyun and H. K. Kim, The poset structures admitting the extended binary Hamming code to be a perfect code, Discrete Mathematics, 288 (2004), 37-47.  doi: 10.1016/j.disc.2004.07.010.  Google Scholar

[12]

C. JangH. K. KimD. Y. Oh and Y. Rho, The poset structures admitting the extended binary Golay code to be a perfect code, Discrete Mathematics, 308 (2008), 4057-4068.  doi: 10.1016/j.disc.2007.07.111.  Google Scholar

[13]

Y. Jang and J. Park, On a MacWilliams type identity and a perfectness for a binary linear $(n, n-1, j)$-poset code, Discrete Mathematics, 265 (2003), 85-104.  doi: 10.1016/S0012-365X(02)00624-6.  Google Scholar

[14]

H. K. Kim and D. Y. Oh, On the nonexistence of triple-error-correcting perfect binary linear codes with a crown poset structure, Discrete Mathematics, 297 (2005), 174-181.  doi: 10.1016/j.disc.2005.03.018.  Google Scholar

[15]

H. K. Kim and D. S. Krotov, The poset metrics that allow binary codes of codimension $m$ to be $m$-, $m-1$-, or $m-2$-perfect, IEEE Transactions on Information Theory, 54 (2008), 5241-5246.  doi: 10.1109/TIT.2008.929972.  Google Scholar

[16]

J. G. Lee, Perfect codes on some ordered sets, Bulletin of the Korean Mathematical Society, 43 (2006), 293-297.  doi: 10.4134/BKMS.2006.43.2.293.  Google Scholar

[17]

Y. Lee, Projective systems and perfect codes with a poset metric, Finite Fields and Their Applications, 10 (2004), 105-112.  doi: 10.1016/S1071-5797(03)00046-7.  Google Scholar

[18]

R. A. MachadoJ. A. Pinheiro and M. Firer, Characterization of metrics induced by hierarquical posets, IEEE Transactions on Information Theory, 63 (2017), 3630-3640.  doi: 10.1109/TIT.2017.2691763.  Google Scholar

[19]

R. G. L. D'Oliveira and M. Firer, The packing radius of a code and partitioning problems: The case for poset metrics on finite vector spaces, Discrete Mathematics, 338 (2015), 2143-2167.  doi: 10.1016/j.disc.2015.05.011.  Google Scholar

[20]

L. PanekM. FirerH. K. Kim and J. Y. Hyun, Groups of linear isometries on poset structures, Discrete Mathematics, 308 (2008), 4116-4123.  doi: 10.1016/j.disc.2007.08.001.  Google Scholar

show all references

References:
[1]

J. AhnH. K. KimJ. S. Kim and M. Kim, Classification of perfect linear codes with crown poset structure, Discrete Mathematics, 268 (2003), 21-30.  doi: 10.1016/S0012-365X(02)00679-9.  Google Scholar

[2]

M. M. S. AlvesL. Panek and M. Firer, Error-block codes and poset metrics, Advances in Mathematics of Communications, 2 (2008), 95-111.  doi: 10.3934/amc.2008.2.95.  Google Scholar

[3]

A. BargL. V. FelixM. Firer and M. V. P. Spreafico, Linear codes on posets with extension property, Discrete Mathematics, 317 (2014), 1-13.  doi: 10.1016/j.disc.2013.11.001.  Google Scholar

[4]

A. Barg and W. Park, On linear ordered codes, Moscow Mathematical J., 15 (2015), 679-702.  doi: 10.17323/1609-4514-2015-15-4-679-702.  Google Scholar

[5]

R. BrualdiJ. S. Graves and M. Lawrence, Codes with a poset metric, Discrete Mathematics, 147 (1995), 57-72.  doi: 10.1016/0012-365X(94)00228-B.  Google Scholar

[6]

B. K. DassN. Sharma and R. Verma, Perfect codes in poset spaces and poset block spaces, Finite Fields and Their Applications, 46 (2017), 90-106.  doi: 10.1016/j.ffa.2017.02.003.  Google Scholar

[7]

L. V. Felix and M. Firer, Canonical-systematic form for codes in hierarchical poset metrics, Advances in Mathematics of Communications, 6 (2012), 315-328.  doi: 10.3934/amc.2012.6.315.  Google Scholar

[8]

M. Firer, M. M. S. Alves, J. A. Pinheiro and L. Panek, Poset Codes: Partial Orders, Metrics and Coding Theory, SpringerBriefs in Mathematics. Springer, Cham, 2018. doi: 10.1007/978-3-319-93821-9.  Google Scholar

[9]

M. Firer and J. A. Pinheiro, Bounds for complexity of syndrome decoding for poset metrics, 2015 IEEE Information Theory Workshop, (2015), 1–5. doi: 10.1109/ITW.2015.7133130.  Google Scholar

[10] W. C. Huffman and V. Pless, Fundamentals of Error-Correcting Codes, Cambridge University Press, Cambridge, 2003.  doi: 10.1017/CBO9780511807077.  Google Scholar
[11]

J. Y. Hyun and H. K. Kim, The poset structures admitting the extended binary Hamming code to be a perfect code, Discrete Mathematics, 288 (2004), 37-47.  doi: 10.1016/j.disc.2004.07.010.  Google Scholar

[12]

C. JangH. K. KimD. Y. Oh and Y. Rho, The poset structures admitting the extended binary Golay code to be a perfect code, Discrete Mathematics, 308 (2008), 4057-4068.  doi: 10.1016/j.disc.2007.07.111.  Google Scholar

[13]

Y. Jang and J. Park, On a MacWilliams type identity and a perfectness for a binary linear $(n, n-1, j)$-poset code, Discrete Mathematics, 265 (2003), 85-104.  doi: 10.1016/S0012-365X(02)00624-6.  Google Scholar

[14]

H. K. Kim and D. Y. Oh, On the nonexistence of triple-error-correcting perfect binary linear codes with a crown poset structure, Discrete Mathematics, 297 (2005), 174-181.  doi: 10.1016/j.disc.2005.03.018.  Google Scholar

[15]

H. K. Kim and D. S. Krotov, The poset metrics that allow binary codes of codimension $m$ to be $m$-, $m-1$-, or $m-2$-perfect, IEEE Transactions on Information Theory, 54 (2008), 5241-5246.  doi: 10.1109/TIT.2008.929972.  Google Scholar

[16]

J. G. Lee, Perfect codes on some ordered sets, Bulletin of the Korean Mathematical Society, 43 (2006), 293-297.  doi: 10.4134/BKMS.2006.43.2.293.  Google Scholar

[17]

Y. Lee, Projective systems and perfect codes with a poset metric, Finite Fields and Their Applications, 10 (2004), 105-112.  doi: 10.1016/S1071-5797(03)00046-7.  Google Scholar

[18]

R. A. MachadoJ. A. Pinheiro and M. Firer, Characterization of metrics induced by hierarquical posets, IEEE Transactions on Information Theory, 63 (2017), 3630-3640.  doi: 10.1109/TIT.2017.2691763.  Google Scholar

[19]

R. G. L. D'Oliveira and M. Firer, The packing radius of a code and partitioning problems: The case for poset metrics on finite vector spaces, Discrete Mathematics, 338 (2015), 2143-2167.  doi: 10.1016/j.disc.2015.05.011.  Google Scholar

[20]

L. PanekM. FirerH. K. Kim and J. Y. Hyun, Groups of linear isometries on poset structures, Discrete Mathematics, 308 (2008), 4116-4123.  doi: 10.1016/j.disc.2007.08.001.  Google Scholar

Figure 1.  Posets $ P $, $ Q $ and $ R $
Figure 2.  Posets $ P^+ $, $ Q^+ $ and $ R^+ $
[1]

B. K. Dass, Namita Sharma, Rashmi Verma. Characterization of extended Hamming and Golay codes as perfect codes in poset block spaces. Advances in Mathematics of Communications, 2018, 12 (4) : 629-639. doi: 10.3934/amc.2018037

[2]

Marcelo Muniz S. Alves, Luciano Panek, Marcelo Firer. Error-block codes and poset metrics. Advances in Mathematics of Communications, 2008, 2 (1) : 95-111. doi: 10.3934/amc.2008.2.95

[3]

Luciano Viana Felix, Marcelo Firer. Canonical- systematic form for codes in hierarchical poset metrics. Advances in Mathematics of Communications, 2012, 6 (3) : 315-328. doi: 10.3934/amc.2012.6.315

[4]

Olof Heden. A survey of perfect codes. Advances in Mathematics of Communications, 2008, 2 (2) : 223-247. doi: 10.3934/amc.2008.2.223

[5]

Joaquim Borges, Josep Rifà, Victor Zinoviev. Completely regular codes by concatenating Hamming codes. Advances in Mathematics of Communications, 2018, 12 (2) : 337-349. doi: 10.3934/amc.2018021

[6]

Olof Heden. The partial order of perfect codes associated to a perfect code. Advances in Mathematics of Communications, 2007, 1 (4) : 399-412. doi: 10.3934/amc.2007.1.399

[7]

Anuradha Sharma, Saroj Rani. Trace description and Hamming weights of irreducible constacyclic codes. Advances in Mathematics of Communications, 2018, 12 (1) : 123-141. doi: 10.3934/amc.2018008

[8]

Markku Lehtinen, Baylie Damtie, Petteri Piiroinen, Mikko Orispää. Perfect and almost perfect pulse compression codes for range spread radar targets. Inverse Problems & Imaging, 2009, 3 (3) : 465-486. doi: 10.3934/ipi.2009.3.465

[9]

Sergio R. López-Permouth, Steve Szabo. On the Hamming weight of repeated root cyclic and negacyclic codes over Galois rings. Advances in Mathematics of Communications, 2009, 3 (4) : 409-420. doi: 10.3934/amc.2009.3.409

[10]

Olof Heden, Faina I. Solov’eva. Partitions of $\mathbb F$n into non-parallel Hamming codes. Advances in Mathematics of Communications, 2009, 3 (4) : 385-397. doi: 10.3934/amc.2009.3.385

[11]

Alonso sepúlveda Castellanos. Generalized Hamming weights of codes over the $\mathcal{GH}$ curve. Advances in Mathematics of Communications, 2017, 11 (1) : 115-122. doi: 10.3934/amc.2017006

[12]

Olof Heden, Fabio Pasticci, Thomas Westerbäck. On the existence of extended perfect binary codes with trivial symmetry group. Advances in Mathematics of Communications, 2009, 3 (3) : 295-309. doi: 10.3934/amc.2009.3.295

[13]

Olof Heden, Denis S. Krotov. On the structure of non-full-rank perfect $q$-ary codes. Advances in Mathematics of Communications, 2011, 5 (2) : 149-156. doi: 10.3934/amc.2011.5.149

[14]

Helena Rifà-Pous, Josep Rifà, Lorena Ronquillo. $\mathbb{Z}_2\mathbb{Z}_4$-additive perfect codes in Steganography. Advances in Mathematics of Communications, 2011, 5 (3) : 425-433. doi: 10.3934/amc.2011.5.425

[15]

Ettore Fornasini, Telma Pinho, Raquel Pinto, Paula Rocha. Composition codes. Advances in Mathematics of Communications, 2016, 10 (1) : 163-177. doi: 10.3934/amc.2016.10.163

[16]

Michael Braun. On lattices, binary codes, and network codes. Advances in Mathematics of Communications, 2011, 5 (2) : 225-232. doi: 10.3934/amc.2011.5.225

[17]

Alexis Eduardo Almendras Valdebenito, Andrea Luigi Tironi. On the dual codes of skew constacyclic codes. Advances in Mathematics of Communications, 2018, 12 (4) : 659-679. doi: 10.3934/amc.2018039

[18]

David Keyes. $\mathbb F_p$-codes, theta functions and the Hamming weight MacWilliams identity. Advances in Mathematics of Communications, 2012, 6 (4) : 401-418. doi: 10.3934/amc.2012.6.401

[19]

Olav Geil, Stefano Martin. Relative generalized Hamming weights of q-ary Reed-Muller codes. Advances in Mathematics of Communications, 2017, 11 (3) : 503-531. doi: 10.3934/amc.2017041

[20]

Jennifer D. Key, Washiela Fish, Eric Mwambene. Codes from the incidence matrices and line graphs of Hamming graphs $H^k(n,2)$ for $k \geq 2$. Advances in Mathematics of Communications, 2011, 5 (2) : 373-394. doi: 10.3934/amc.2011.5.373

2019 Impact Factor: 0.734

Article outline

Figures and Tables

[Back to Top]