Open Access Open Access  Restricted Access Subscription or Fee Access

New Efficient Scheme Based on Reduction of the Dimension in the Multiple Impulse Method to Find the Minimum Distance of Linear Codes


(*) Corresponding author


Authors' affiliations


DOI: https://doi.org/10.15866/irecos.v11i9.9702

Abstract


In order to find a minimum weight codeword in a linear code, the Multiple Impulse Method uses the Ordered Statistics Decoder of order 3 having a complexity which increases with the code dimension. This paper presents an important improvement of this method by finding a sub code of C of small dimension containing a lowest weight codeword. In the case of Binary Extended Quadratic Residue codes, the proposed technique consists on finding a self invertible permutation σ from the projective special linear group and searching a codeword having the minimum weight in the sub code fixed by σ. The proposed technique gives the exact value of the minimum distance for all binary quadratic residue codes of length less than 223 by using the Multiple Impulse Method on the sub codes in less than one second. For lengths more than 223, the obtained results prove the height capacity of the proposed technique to find the lowest weight in less time. The proposed idea is generalized for BCH codes and it has permits to find the true value of the minimum distance for some codes of lengths 1023 and 2047. The proposed methods performed very well in comparison to previously known results.
Copyright © 2016 Praise Worthy Prize - All rights reserved.

Keywords


Automorphism Group; Projective Special Linear Group; Quadratic Residue Codes; Minimum Distance; BCH Codes; Designed Distance; Minimum Weight; Multiple Impulse Method

Full Text:

PDF


References


A. Vardy, The intractability of Computing the Minimum distance of a Code, IEEE Transaction on Information Theory, vol. 43, No. 6 (1997), 1757–1766.
http://dx.doi.org/10.1109/18.641542

V. Pless et al., Handbook of Coding Theory (North Holland, 1998).
http://dx.doi.org/10.1002/9781118032749

F.J.MacWilliams and N.J.A.Sloane. The theory of Error-Correcting Codes ( North-Holland, 1977).
http://dx.doi.org/10.1016/s0924-6509(08)70549-x

Krasikov, I. and Litsyn, S. (2000) 'An improved upper bound on the minimum distance of doubly-even self-dual codes', IEEE-IT, Vol. 46, No. 1, pp.274–278
http://dx.doi.org/10.1109/18.817527

S. Nouh and M. Belkasmi, “Genetic algorithms for finding the weight enumerator of binary linear block codes”, International Journal of Applied Research on Information Technology and Computing IJARITAC, N°3, Vol 2, 2011.
http://dx.doi.org/10.5958/j.0975-8070.2.3.022

Saïd Nouh, Idriss Chana and Mostafa Belkasmi, " Decoding of Block Codes by using Genetic Algorithms and Permutations Set", International Journal of Communication Networks and Information Security, Vol. 5, No. 3, 2013.
http://dx.doi.org/10.4236/ijcns.2012.57052

R.C Bose and D. K. Ray-Chaudhuri. On a class of error correcting binary group codes. Information and Control, 3 :68–79, mars 1960
http://dx.doi.org/10.1016/s0019-9958(60)90287-4

A. Hocquenghem. Codes correcteurs d’erreurs. Chiffres, 2 :147–156, sept 1959.
http://dx.doi.org/10.1016/0012-365x(77)90159-5

Priya Mathew, Lismi Augustine, Sabarinath G., Tomson Devis, "Hardware Implementation of (63,51) BCH Encoder and Decoder For WBAN Using LFSR and BMA", International Journal on Information Theory (IJIT), Volume 3, No.3, July 2014.
http://dx.doi.org/10.5121/ijit.2014.3301

J. Wallis and K. Houghten, “A Comparative Study of Search Techniques Applied tothe Minumum Distance of BCH Codes,” Conference on Artificial Intelligence and Soft Computing, Banff, 17-19 July 2002.
http://dx.doi.org/10.1109/aici.2010.197

A. Canteaut, and F. Chabaud. A new algorithm for finding minimum-weight words in a linear code: Application to primitive narrow-sense BCH codes of length 511, IEEE Trans. Inform. Theory, IT-44(1), pp 367-378, Jan. 1998.
http://dx.doi.org/10.1109/18.651067

Askali M., Azouaoui A., Nouh S., Belkasmi M. (2012) On the Computing of the Minimum Distance of Linear Block Codes by Heuristic Methods, International Journal of Communications, Network and System Sciences, 5(11), 774-784
http://dx.doi.org/10.4236/ijcns.2012.511081

D. Coppersmith and G. Seroussi, “On the Minimum Distance of some Quadratic Residue Codes,” IEEE Trans. Inform. Theory, vol. 30, no. 2,pp. 407-411, Mar. 1984.
http://dx.doi.org/10.1109/tit.1984.1056861

N. Boston, “The Minimum Distance of the [137, 69] Quadratic Residue Code,” IEEE Trans. Inform. Theory, vol. 45, no. 1, pp. 282, Jan. 1999.
http://dx.doi.org/10.1109/18.746813

D. Kuhlmann, “The Minimum Distance of the [83, 42] Quadratic Residue Code,” IEEE Trans. Inform. Theory, vol. 45, no. 1, pp. 282, Jan. 1999.
http://dx.doi.org/10.1109/18.746813

Markus Grassl, “On the Minimum Distance of some Quadratic Residue Codes,” Proc. IEEE Int’l Symp. on Inform. Theory(ISIT), Sorrento, Italy, June, 2000.
http://dx.doi.org/10.1109/isit.2000.866551

Wen-Ku Su ,Pei-Yu Shih ,Tsung-Ching Lin ,Trieu-Kien Truong “On the minimum weights of binary extended quadratic residue codes”, ICACT'09 Proceedings of the 11th international conference on Advanced Communication Technology - Volume 3 IEEE Press Piscataway, NJ, ISBN: 978-8-9551-9138-7
http://dx.doi.org/10.1109/icct.2008.4716290

Saouter, Y., Mestre, G. LE. A FPGA implementation of Chen’s algorithm 35th International Symposium on Symbolic and Algebraic Computation, July 2010, Munich, Germany, 2010. length 223
http://dx.doi.org/10.1145/1940475.1940503

C. Berrou, S. Vaton, M. Jezequel and C. Douillard, “Computing the Minimum Distance of Linear Codes by the Error Impulse Method,” Proceedings of IEEE Globecom, Taipei, 17-21 November 2002, pp. 10-14.
http://dx.doi.org/10.1109/glocom.2002.1188348

C. Chen. Computer results on the minimum distance of some binary cyclic codes. IEEE Trans. Inf. Theory, IT-16:359–360, 1970.
http://dx.doi.org/10.1109/tit.1970.1054452

M. Zhang, F. Ma, Simulated annealing approach to the minimum distance of error-correcting codes, Int. J. Electron. 76 (1994) 377–384.
http://dx.doi.org/10.1080/00207219408925934

J.A. Bland, D.J. Baylis, A tabu search approach to the minimum distance of error-correcting codes, Int. J. Electron. 79 (1995) 829–837.
http://dx.doi.org/10.1080/00207219508926317

J.A. Bland. Local search optimisation applied to the minimum distance problem. Advanced Engineering Informatics, 21, 2007
http://dx.doi.org/10.1016/j.aei.2007.01.002

Bouchaib AYLAJ and Mostafa BELKASMI, New Simulated Annealing Algorithm for Computing the Minimum Distance of Linear Block Codes. Advances in Computational Research, indexed Google Scholar ISSN : 0975-3273, E-ISSN : 0975-9085, Volume 6, Issue 1, pp.-153-158, 2014.
http://dx.doi.org/10.1007/978-3-319-30301-7_19

J. Leon, “A probabilistic algorithm for computing minimum weights of large error-correcting codes,”IEEE Trans. Inform. Theory, vol. 34, pp.1354–1359, 1988.
http://dx.doi.org/10.1109/18.21270

J. Stern, “A method for finding codewords of small weight,” in Coding Theory and Applications, G. Cohen and J. Wolfmann, Eds. New York:Springer-Verlag, 1989, pp. 106–113.
http://dx.doi.org/10.1007/bfb0019850

Ajitha Shenoy K. B, Somenath Biswas, Piyush P. Kurur, "Performance of metropolis algorithm for the minimum weight code word problem", Genetic and Evolutionary Computation Conference, 2014.
http://dx.doi.org/10.1145/2576768.2598274

M. Askali, S. Nouh, A. Azouaoui, M. Belkasmi "Discovery of Good Double and Triple Circulant Codes using Multiple Impulse Method", Advances in Computational Research, Volume 5, Issue 1, pp.141-148, 2013.
http://dx.doi.org/10.1109/icmcs.2011.5945582

P. Remlein, D. Szłapka, “Genetic Algorithm used in Search of good Tailbiting Codes”, International Journal of Communication Networks and Information Security, IJCNIS, Vol. 1, No. 3, December 2009.
http://dx.doi.org/10.1109/iswcs.2009.5285310


Refbacks

  • There are currently no refbacks.


Please send any question about this web site to info@praiseworthyprize.com
Copyright © 2005-2024 Praise Worthy Prize