The Error Correcting Code Design Problem
|
||||||||||||||||||||||||||||||||||
|
||||||||||||||||||||||||||||||||||
A code can be formally represented by a three-tuple (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 n-dimensional space [DJ90] by considering the minimal energy configuration of M particles (where is the Hamming distance between words i and j): 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, specifically-designed 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 805-811, 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 805-811, 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, Springer-Verlag, Berlin, Heidelberg, pp. 689-700, 2001 [AK02] E. Alba, S. Khuri, Sequential and Distributed
Evolutionary Algorithms for Combinatorial Optimization Problems, to appear
in Studies in Fuziness and Soft Computing, Springer-Verlag, 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. 3004-3006, 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. 985-989, 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. 51-60, Springer-Verlag Berlin, 2004. Click here to get the bibliography in bibtex fotmat. |
||||||||||||||||||||||||||||||||||
Last Updated: 4/2/03 For any question or suggestion, click here to contact with us. |
||||||||||||||||||||||||||||||||||