November  2012, 6(4): 505-516. doi: 10.3934/amc.2012.6.505

Partial permutation decoding for simplex codes

1. 

Department of Mathematics and Applied Mathematics, University of the Western Cape, 7535 Bellville, South Africa

Received  January 2012 Revised  May 2012 Published  November 2012

We show how to find $s$-PD-sets of size $s+1$ that satisfy the Gordon-Schönheim bound for partial permutation decoding for the binary simplex codes $\mathcal S_n(\mathbb F_2)$ for all $n \geq 4$, and for all values of $s$ up to $\left\lfloor\frac{2^n-1}{n}\right\rfloor -1$. The construction also applies to the $q$-ary simplex codes $\mathcal S_n(\mathbb F_q)$ for $q>2$, and to $s$-antiblocking information systems of size $s+1$, for $s$ up to $\left\lfloor\frac{(q^n-1)/(q-1)}{n}\right\rfloor -1$ for all $q$.
Citation: Washiela Fish, Jennifer D. Key, Eric Mwambene. Partial permutation decoding for simplex codes. Advances in Mathematics of Communications, 2012, 6 (4) : 505-516. doi: 10.3934/amc.2012.6.505
References:
[1]

E. F. Assmus, Jr. and J. D. Key, "Designs and their Codes,'', Cambridge University Press, (1992). Google Scholar

[2]

W. Bosma, J. Cannon and C. Playoust, The Magma algebra system I: The user language,, J. Symbolic Comput., 24 (1997), 235. doi: 10.1006/jsco.1996.0125. Google Scholar

[3]

J. Cannon, A. Steel and G. White, Linear codes over finite fields,, in, (2006), 3951. Google Scholar

[4]

D. M. Gordon, Minimal permutation sets for decoding the binary Golay codes,, IEEE Trans. Inform. Theory, 28 (1982), 541. doi: 10.1109/TIT.1982.1056504. Google Scholar

[5]

E. V. Gorkunov, The group of permutation automorphisms of a $q$-ary Hamming code,, Probl. Inf. Transm., 45 (2009), 309. doi: 10.1134/S0032946009040024. Google Scholar

[6]

W. C. Huffman, Codes and groups,, in, (1998), 1345. Google Scholar

[7]

J. D. Key, T. P. McDonough and V. C. Mavron, Partial permutation decoding for codes from finite planes,, European J. Combin., 26 (2005), 665. doi: 10.1016/j.ejc.2004.04.007. Google Scholar

[8]

H.-J. Kroll and R. Vincenti, PD-sets related to the codes of some classical varieties,, Discrete Math., 301 (2005), 89. doi: 10.1016/j.disc.2004.11.020. Google Scholar

[9]

H.-J. Kroll and R. Vincenti, PD-sets for binary RM-codes and the codes related to the Klein quadric and to the Schubert variety of $PG(5,2)$,, Discrete Math., 308 (2008), 408. doi: 10.1016/j.disc.2006.11.057. Google Scholar

[10]

H.-J. Kroll and R. Vincenti, Antiblocking decoding,, Discrete Appl. Math., 158 (2010), 1461. doi: 10.1016/j.dam.2010.04.007. Google Scholar

[11]

H.-J. Kroll and R. Vincenti, How to find small AI-systems for antiblocking decoding,, Discrete Math., 312 (2012), 657. doi: 10.1016/j.disc.2011.06.014. Google Scholar

[12]

F. J. MacWilliams, Permutation decoding of systematic codes,, Bell System Tech. J., 43 (1964), 485. Google Scholar

[13]

F. J. MacWilliams and N. J. A. Sloane, "The Theory of Error-Correcting Codes,'', North-Holland, (1983). Google Scholar

[14]

T. P. McDonough, Private communication,, 2012., (). Google Scholar

[15]

J. Schönheim, On coverings,, Pacific J. Math., 14 (1964), 1405. Google Scholar

[16]

J. Wolfmann, A permutation decoding of the $(24,12,8)$ Golay code,, IEEE Trans. Inform. Theory, 29 (1983), 748. doi: 10.1109/TIT.1983.1056726. Google Scholar

show all references

References:
[1]

E. F. Assmus, Jr. and J. D. Key, "Designs and their Codes,'', Cambridge University Press, (1992). Google Scholar

[2]

W. Bosma, J. Cannon and C. Playoust, The Magma algebra system I: The user language,, J. Symbolic Comput., 24 (1997), 235. doi: 10.1006/jsco.1996.0125. Google Scholar

[3]

J. Cannon, A. Steel and G. White, Linear codes over finite fields,, in, (2006), 3951. Google Scholar

[4]

D. M. Gordon, Minimal permutation sets for decoding the binary Golay codes,, IEEE Trans. Inform. Theory, 28 (1982), 541. doi: 10.1109/TIT.1982.1056504. Google Scholar

[5]

E. V. Gorkunov, The group of permutation automorphisms of a $q$-ary Hamming code,, Probl. Inf. Transm., 45 (2009), 309. doi: 10.1134/S0032946009040024. Google Scholar

[6]

W. C. Huffman, Codes and groups,, in, (1998), 1345. Google Scholar

[7]

J. D. Key, T. P. McDonough and V. C. Mavron, Partial permutation decoding for codes from finite planes,, European J. Combin., 26 (2005), 665. doi: 10.1016/j.ejc.2004.04.007. Google Scholar

[8]

H.-J. Kroll and R. Vincenti, PD-sets related to the codes of some classical varieties,, Discrete Math., 301 (2005), 89. doi: 10.1016/j.disc.2004.11.020. Google Scholar

[9]

H.-J. Kroll and R. Vincenti, PD-sets for binary RM-codes and the codes related to the Klein quadric and to the Schubert variety of $PG(5,2)$,, Discrete Math., 308 (2008), 408. doi: 10.1016/j.disc.2006.11.057. Google Scholar

[10]

H.-J. Kroll and R. Vincenti, Antiblocking decoding,, Discrete Appl. Math., 158 (2010), 1461. doi: 10.1016/j.dam.2010.04.007. Google Scholar

[11]

H.-J. Kroll and R. Vincenti, How to find small AI-systems for antiblocking decoding,, Discrete Math., 312 (2012), 657. doi: 10.1016/j.disc.2011.06.014. Google Scholar

[12]

F. J. MacWilliams, Permutation decoding of systematic codes,, Bell System Tech. J., 43 (1964), 485. Google Scholar

[13]

F. J. MacWilliams and N. J. A. Sloane, "The Theory of Error-Correcting Codes,'', North-Holland, (1983). Google Scholar

[14]

T. P. McDonough, Private communication,, 2012., (). Google Scholar

[15]

J. Schönheim, On coverings,, Pacific J. Math., 14 (1964), 1405. Google Scholar

[16]

J. Wolfmann, A permutation decoding of the $(24,12,8)$ Golay code,, IEEE Trans. Inform. Theory, 29 (1983), 748. doi: 10.1109/TIT.1983.1056726. Google Scholar

[1]

Kwankyu Lee. Decoding of differential AG codes. Advances in Mathematics of Communications, 2016, 10 (2) : 307-319. doi: 10.3934/amc.2016007

[2]

Elisa Gorla, Felice Manganiello, Joachim Rosenthal. An algebraic approach for decoding spread codes. Advances in Mathematics of Communications, 2012, 6 (4) : 443-466. doi: 10.3934/amc.2012.6.443

[3]

Alexander Barg, Arya Mazumdar, Gilles Zémor. Weight distribution and decoding of codes on hypergraphs. Advances in Mathematics of Communications, 2008, 2 (4) : 433-450. doi: 10.3934/amc.2008.2.433

[4]

Terasan Niyomsataya, Ali Miri, Monica Nevins. Decoding affine reflection group codes with trellises. Advances in Mathematics of Communications, 2012, 6 (4) : 385-400. doi: 10.3934/amc.2012.6.385

[5]

Heide Gluesing-Luerssen, Uwe Helmke, José Ignacio Iglesias Curto. Algebraic decoding for doubly cyclic convolutional codes. Advances in Mathematics of Communications, 2010, 4 (1) : 83-99. doi: 10.3934/amc.2010.4.83

[6]

Hannes Bartz, Antonia Wachter-Zeh. Efficient decoding of interleaved subspace and Gabidulin codes beyond their unique decoding radius using Gröbner bases. Advances in Mathematics of Communications, 2018, 12 (4) : 773-804. doi: 10.3934/amc.2018046

[7]

Joan-Josep Climent, Diego Napp, Raquel Pinto, Rita Simões. Decoding of $2$D convolutional codes over an erasure channel. Advances in Mathematics of Communications, 2016, 10 (1) : 179-193. doi: 10.3934/amc.2016.10.179

[8]

Johan Rosenkilde. Power decoding Reed-Solomon codes up to the Johnson radius. Advances in Mathematics of Communications, 2018, 12 (1) : 81-106. doi: 10.3934/amc.2018005

[9]

Irene I. Bouw, Sabine Kampf. Syndrome decoding for Hermite codes with a Sugiyama-type algorithm. Advances in Mathematics of Communications, 2012, 6 (4) : 419-442. doi: 10.3934/amc.2012.6.419

[10]

Anas Chaaban, Vladimir Sidorenko, Christian Senger. On multi-trial Forney-Kovalev decoding of concatenated codes. Advances in Mathematics of Communications, 2014, 8 (1) : 1-20. doi: 10.3934/amc.2014.8.1

[11]

Vladimir Sidorenko, Christian Senger, Martin Bossert, Victor Zyablov. Single-trial decoding of concatenated codes using fixed or adaptive erasing. Advances in Mathematics of Communications, 2010, 4 (1) : 49-60. doi: 10.3934/amc.2010.4.49

[12]

Peter Beelen, Kristian Brander. Efficient list decoding of a class of algebraic-geometry codes. Advances in Mathematics of Communications, 2010, 4 (4) : 485-518. doi: 10.3934/amc.2010.4.485

[13]

Alexey Frolov, Victor Zyablov. On the multiple threshold decoding of LDPC codes over GF(q). Advances in Mathematics of Communications, 2017, 11 (1) : 123-137. doi: 10.3934/amc.2017007

[14]

Fernando Hernando, Tom Høholdt, Diego Ruano. List decoding of matrix-product codes from nested codes: An application to quasi-cyclic codes. Advances in Mathematics of Communications, 2012, 6 (3) : 259-272. doi: 10.3934/amc.2012.6.259

[15]

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

[16]

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

[17]

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

[18]

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

[19]

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

[20]

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

2018 Impact Factor: 0.879

Metrics

  • PDF downloads (4)
  • HTML views (0)
  • Cited by (8)

Other articles
by authors

[Back to Top]