The Error Correcting Code Design Problem

Description:

      The Error Correcting Code Design Problem [GHSW87] (ECC) consists in assigning codewords to an alphabet that minimizes the length of transmitted messages and that provides maximal correction of single uncorrelated bit errors, when the messages are transmitted over noisy channels. Note that the two restrictions are conflicting in nature. On the one hand, we would like to assign codewords that are as short as possible, and on the other hand, high error correction is achieved by adding redundant bits so as to maximize the Hamming distance between every pair of codewords.  

      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):

      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.

1. A well-known instance is related to construct a code with n=12 and M=12 [CFW98,AK01,AK02]. For this code, the best known solution has been found in [AK02] and is illustrated in [CFW98].

2. In [AC04], a more complex instance is used; to construct a code with n=12 and M=24, with minimum distance 6. For this code, the following results are available.

3. In [CTT04], harder problems are solved: n=16 and M=32 (d=8) and, n=20 and M=40 (d=10).

Results:

In order to resolve the ECC problem, several techniques can be chosen, with different approaches.

• General-purpose techniques, with no problem knowledge, such as Genetic Algorithms, sequential or parallel, panmictic or celular [AK01][ACCN02]

• Repulsion based population algorithms, such as RA, devised in [AC04], or the Repulsive Particle Swarm (RPSO) described here.

• Hybridization of a repulsion algorithm and GAs [AC04]

• Special purpose algorithms, that are instantiated with problem knowledge, such as Memetic algorithms (MA) and Scatter Search (SS) [CTT04].

• There is work in progress that uses some of the topological properties, such as the simmetry of the solutions, to obtain better algorithms for some specific instances of this problem (like the ones mentioned earlier).

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.