New efficient techniques to catch lowest weights in large Quadratic Residue codes

ABDELWAHED, NAMIR and ISSAM, ABDERRAHMAN JOUNDAN and SAID, NOUH (2017) New efficient techniques to catch lowest weights in large Quadratic Residue codes. In: Fifth International Conference on Advances in Computing, Electronics and Communication - ACEC 2017, 27-28 May, 2017, Rome, Italy.

20170612_064602.pdf - Published Version

Download (942kB) | Preview
Official URL:


For a large Quadratic Residue (QR) code C, the problem of finding the minimum weight d is NP-hard and many research techniques have been developed to attack its hardness such as simulated annealing, Multiple Impulse Method, Ant Colony Optimization, Zimmermann algorithms and MIM-FSI method. The true value of the minimum weight in QR codes is known for only lengths less than or equal to 223. In this work, we propose new efficient schemes to catch lowest weights codewords in QR codes. The first proposed scheme Zimmermann-FSI uses the Zimmermann algorithm for searching lowest weights in the sub code SubEQR fixed by a self invertible element of the projective special linear group. The code SubEQR has a small dimension comparing to C itself. This reduction of the dimension permits to reduce considerably the research space size and it is behind the success of the Zimmermann-FSI scheme. This good result has encourages us to continue on reducing again the dimension of SubEQR and to propose the second scheme Zimmermann-FSI-RSC which uses the Zimmermann algorithm to catch lowest weights in a list of sub codes of small dimensions randomly extracted from the sub code SubEQR. The two proposed schemes are validated on all QR codes of known minimum weight. The comparison between MIM-FSI, Zimmermann-FSI and Zimmermann-FSI-RSC on many large QR codes proves the efficiency of the two latest ones in terms of run time reduction and the results quality. The proposed methods performed very well in comparison to previously known results and they yield to some new ones for lengths up to 601.

Item Type: Conference or Workshop Item (Paper)
Uncontrolled Keywords: Automorphism group, projective special linear group, Quadratic Residue codes, minimum distance, minimum weight, Multiple Impulse Method, Zimmermann’s algorithm, MIM-FSI method.
Depositing User: Mr. John Steve
Date Deposited: 15 Mar 2019 11:08
Last Modified: 15 Mar 2019 11:08

Actions (login required)

View Item View Item