Journals Proceedings

Abstract

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