The Error Correcting Code Design Problem




A code can be formally represented by a threetuple (n, M, d), where n is the length (number of bits) of each codeword, M is the number of codewords and d is the minimum Hamming distance between any pair of codewords. An optimal code consists in M binary codewords, each of length n, such that d, the minimum Hamming distance between each codeword and all other codewords, is maximized. In other words, a good (n, M, d) code has a small value of n (reflecting smaller redundancy and faster transmission), a large value for M (denoting a larger vocabulary) and a large value for d (reflecting greater tolerance to noise and error). The optimized criteria could be as simple as the minimum Hamming distance d taken over all pairs of distinct codewords. However, this value will only depend upon a few words and provides very little information as to the progress towards the optimal. A better approach is to measure how well the M words are placed in the corners of a ndimensional space [DJ90] by considering the minimal energy configuration of M particles (where is the Hamming distance between words i and j): However, the energy formula may lead to an incorrect results, as sometimes distributions with suboptimal minimum Hamming distance may have energy values equal to distributions with the required distance. In [AC04] the following corrected formula is used: Click here to get this description in tex format and here to get the figure in eps format. 

Instances and best known solutions for those instances:In order to define an instance of this problem we need to provide the value of n (the length of each codeword) and the value of M (number of codeword). The following table (reproduced from [AVZ01]) lists the value for M given a value of n and a minimum distance d.


Results:In order to resolve the ECC problem, several techniques can be chosen, with different approaches.
As is expected, specificallydesigned algorithms achieve greater success rates and better performance. The following table summarizes the results reported in [AC04] and [CTT04], and the results of RPSO, over the instance (n>=12, M=24, d=6).


Table 1. Results by several algorithms on the ECC instance (12,24,6) 

Related Papers:[GHSW87] A.A. El Gamal, L.A. Hemachandra, I. Shperling, and V.K. Wei. “Using Simulated Annealing to Design Good Codes”. IEEE Trans. Information Theory, vol. 33, no. 1, Jan. 1987. [DJ90] K. Dontas and K. De Jong.“Discovery of Maximal Distance Codes Using Genetic Algorithms”. Proceedings of the 2nd International IEEE Conference on Tools for Artificial Intelligence, pages 805811, Herndon, VA, 1990. [CFW98] H. Chen, N. S. Flann and D. W. Watson. "Parallel genetic simulated annealing: a massively parallel SIMD algorithm". IEEE transactions on parallel and distributed systems, pages 805811, vol. 9, number 2, February 1998. [AK01] E. Alba and S. Khuri. "Applying Evolutionary Algorithms to Combinatorial Optimization Problems". Proceedings of the International Conference on Computational Science (ICCS'01), LNCS vol. 2074, Part II, SpringerVerlag, Berlin, Heidelberg, pp. 689700, 2001 [AK02] E. Alba, S. Khuri, Sequential and Distributed
Evolutionary Algorithms for Combinatorial Optimization Problems, to appear
in Studies in Fuziness and Soft Computing, SpringerVerlag, Berlin, Heidelberg,
2002. [AVZ01] Agrell, E., Vardy, A., Zeger,K A table of
upper bounds for binary codes. IEEE Transactions on Information Theory,
vol. 47, pp. 30043006, 2001. [ACCN02] Alba, E., Cotta, C., Chicano, J.F., Nebro, A. Parallel evolutionary algorithms in telecommunications: Two case studies. Proceedings of CACIC'02, Buenos Aires, Argentina, 2002. [AC04] Alba, E., Chicano, J.F., Solving the Error Correcting
Code Problem with Parallel Hybrid Heuristics, Proceedings of ACM SAC'04,
ACM (ed.), Vol. 2, pp. 985989, 2004. [CTT04] Cotta, C., Scatter Search and Memetic Approaches to the Error Correcting Code Problem, Evolutionary Computation in Combinatorial Optimization, J. Gottlieb, G.Raidl (eds.), Lecture Notes in Computer Science, Vol. 3004, pp. 5160, SpringerVerlag Berlin, 2004. Click here to get the bibliography in bibtex fotmat. 

Last Updated: 6/28/05 For any question or suggestion, click here to contact with us. 
