ISSN : 0975-3273
EISSN : 0975-9085
ASKALI M.1*, NOUH S.2, AZOUAOUI A.3, BELKASMI M.4
1National School of Computer Science and Systems Analysis (ENSIAS), Mohammed V - Souisi University, Rabat, Morocco.
2National School of Computer Science and Systems Analysis (ENSIAS), Mohammed V - Souisi University, Rabat, Morocco.
3National School of Computer Science and Systems Analysis (ENSIAS), Mohammed V - Souisi University, Rabat, Morocco.
4National School of Computer Science and Systems Analysis (ENSIAS), Mohammed V - Souisi University, Rabat, Morocco.
* Corresponding Author : askali11@gmail.com
Received : 25-07-2013 Accepted : 09-08-2013 Published : 20-12-2013
Volume : 5 Issue : 1 Pages : 141 - 148
Adv Comput Res 5.1 (2013):141-148
Conflict of Interest : None declared
The construction of optimal linear block error-correcting codes is not an easy problem, for this, many studies describe methods for generating good error correcting codes in terms of minimum distance. In a previous work, we have presented the multiple impulse method (MIM) to evaluate the minimum distance of linear codes. In this paper we will present an optimization of the MIM method by genetic algorithms, and we found many new optimal Double and Triple Circulant Codes (DCC & TCC) with the highest known parameters using the MIM method as an evaluator of the minimum distance. Two approaches are used in the exploration of the space of generators; the first is based on genetic algorithms, however the second is on the random search algorithm.
Minimum distance, Error impulse Method, heuristic methods, Genetic algorithms, NP-hardness, Linear error correcting codes, Double and Triple Circulant Codes.
The design of good codes is of fundamental importance in a communication system. Furthermore, finding good linear or nonlinear codes may affect the sphere packing problems in Euclidean spaces [1] . When the code rate is 1/2 or 1/3; Double or Triple Circulant Codes (DCC & TCC) have been an interesting family of codes with high minimum distances. It is still hard to determine the minimum distances of long binary codes as well as their asymptotic relative minimum distances [2,4] . Besides, Karlin [5] and Pless [3] found many good codes by systematic double circulant codes over GF(2) and GF(3) using quadratic residues respectively. In [6] , Gaborit proposes a double circulant code scheme which generalizes the constructions of Karlin and Pless over any field and for any length n=pm, where p is an odd prime. Furthermore, Karlin considered binary circulant [ 3p+1, p+1 ] and [ 3p, p ] codes using quadratic residues and nonresidues [5] . Recently artificial intelligence techniques were introduced to solve this problem. Among related works, one idea used Genetic Algorithms (GA) to design constant weight codes [7] , another one used GA for searching the minimum distance of BCH code [8] . Lacan et al. [9] introduced Genetic algorithms in the search of optimal error correcting codes, and in [10] , authors give new good DCC constructed by GA. Here, we propose two heuristic search methods such as Genetic Algorithm, and random search of DCC and TCC when we use the MIM method published in [11] in order to determine the minimum distance, and we give an improvement by introducing the multiple impulse error using genetic algorithm, which we call MIM-GA.
A table of the best known codes is regularly updated on site of code tables maintained by Markus Grassl [17] . For each pair of parameters n and k, this table contains the distance d of the best known code and its theoretical upper bound. In this paper, we are going to search for optimal error-Correcting double circulant codes, by the exploration of the space by Genetic Algorithms and random search. Besides, we will present a new optimization which reduces the complexity. Hence, we propose a technique based on heuristic methods to search of good DCC and TCC codes which have not been previously developed, at our knowledge, for this family of codes.
The paper is organized as follows: In the beginning, we give backgrounds about error correcting codes, and the manner of construction of DCC and TCC codes. Then we introduce genetic algorithms. After we give the implementing methods to evaluate minimum distance, and we improve the MIM method to search good DCC and TCC codes. In the last some experimental results and discussion are presented.
The In this section, we give the basics of error correcting codes, in particular we introduce the construction of Double and Triple Circulant error correcting codes (DCC & TCC).
In all communication systems, the information transmitted is represented via a source code as the ASCII code, Huffman code, etc. This source-encoded information is then sent over a Channel, such as a telephone line, optical fiber, microwave link, etc. To have a reliable transmission the data are encoded again by using an error correcting code that enables the detection and the correction of possible errors introduced during the transmission of message [Fig-1] . Several modes of efficient coding are known: Hamming codes, Reed-Solomon codes, etc.
There exist principally two classes of error correcting Codes: convolutional codes and block codes. In this paper, we will focus on a special case of block codes: double and triple circulant codes (DCC & TCC). Let us explain more precisely the background of block code. Firstly, Let us suppose now that the information to transmit is a sequence of elements which take q possible values, where q is a power of the finite field of cardinal p, which is denoted by Fq. In general, transmitted symbols are binary; then q=2. Principle of block code is the following: the initial message is cut out into blocks of length k. The length of the redundancy is n-k and thus, the length of the transmitted blocks is n. Main blocks are linear codes. In this case, redundancy is computed in such a way as concatenation of information and of redundancy is an element of vector space (a code) of dimension k of (Fq)n.
The operation of coding can be computed by multiplying the message (considered as a vector of length k) by a k*n systematic generator matrix of this vector space. Note that a generator matrix is called systematic if their k first columns form the identity matrix. For a giving code, there exists at most one systematic generator matrix. Some codes did not admit a systematic generator matrix. On the other hand, all these codes are equivalent (modulo a permutation of the positions) to a code which admits one. For a linear code, k and n are respectively called the dimension and the length of the code. The last parameter of a code is its minimum distance d. It is the smallest Hamming distance (the number of distinct components) between two codewords. As the considered codes are linear vector spaces, their minimum distance is also the Hamming weight (the number of nonzero components) of the codeword of smaller hamming weight. The correction capability (the maximum number of error that can be corrected per word of length n) of the code is then equal to t= (d-1)/2.
Example 1: Let C be a code of length 8 and dimension 4 over F2 characterized by its systematic generator G:
The transmitted codeword corresponding to the message (1101) is: (1101) x G = (1101 0100).
The set all possible messages (information vectors), the corresponding set of codewords and their weight are shown in [Table-1] .
An r x r matrix A= [Aij] 0≤i, j≤r-1 over an alphabet F is called circulant if Aij=A0, j-i for all 0≤ i, j≤ r-1, where indices are computed modulo r. Let the notation [ n, k, d ] stand for a k-dimensional linear code of length n and minimum distance d over F, and let r=n-k denotes the redundancy of the code. An [ n = 2r, k = r, d ] linear code over F is called a double circulant if its generated matrix G=[ I A ], where A is an r x r circulant matrix over F[ 2, p. 497 ]. Double circulant codes have been discussed extensively in the literature [2] and a subclass of DCC approaches the Gilbert-Varshamov bound [14] . We are interested by this family of codes because it contains good codes with a maximum minimum distance.
Consider a double circuant code C generated by a matrix [I | A] where A= [aij] 0≤i, j≤r-1. The vector (a0 ,…, ar-1) is called the header of generator matrix of DCC and I is the identity matrix. With every (a0,…, ar-1) є Fr, we associate a matrix A= [Aij] 0≤i, j≤r-1 as the [Eq-1] :
(1)
Where (a0, a1,……………., ar-1) is the header of the A circulant matrix. Each header corresponds to exactly one DCC.
Example 2: Let C (18, 9, 6) a double circulant where her header generator matrix is (011101001) we have the generator matrix G is as the following:
There exists other subfamily of Double Circulant codes like the bordered double Circulant Codes witch is represented by the form described in [Fig-2] .
The Let the notation [ n, k, d ] stand for a k-dimensional linear code of length n and minimum distance d over F, and let r=n-k denotes the redundancy of the code. An [ n=3r, k=r, d ] linear code over F is called a triple circulant if its generated matrix G= [I A B], where A and B are two r x r circulant matrices. We are interested by this family of codes because by experimentation we found good codes with a maximum minimum distance.
Consider a Triple circuant code C generated by a matrix [I | A | B] where A= [aij] 0≤i, j≤r-1 and B= [bij] 0≤i, j≤r-1.
The vectors (a0, a1,…, ar-1) and (b0, b1,…, br-1) are called the headers of generator matrix of TCC and I is the identity matrix. With every header (a0, a1,…, ar-1) є Fr, we associate a matrix A= [Aij] 0≤i, j≤r-1 and every header (b0, b1,…, br-1) є Fr, we associate a matrix B= [bij] 0≤i, j≤r-1 as the [Eq-2] and [Eq-3] :
(2)
(3)
Where
(a0, a1,…………….,ar-1) is the header of the circulant matrix A, and (b0, b1,…………….,br-1) is the header of the circulant matrix B.
Example 3: Let C (27, 9, 6) a Triple circulant code, where its headers of the generator matrix G are a=(011101001) and b=(110110110), G is as the following:
Before, Genetic Algorithms (GA) was first proposed by John Holland’s, as a means to find good solutions to problems that were otherwise computationally intractable. Holland’s schema theorem [12] , and the related building block hypothesis, provided a theoretical and conceptual basis for the design of efficient GA. It also proved straight forward to implement GA due to their highly modular nature. As a consequence, the field grew quickly and the technique was successfully applied to a wide range of practical problems in science, engineering and industry. GA theory is an active and growing area, with a range of approaches being used to describe and explain phenomena not anticipated by earlier theory. In tandem with this, more sophisticated approaches for directing the evolution of a GA population are aimed at improving performance on classes of problem known to be difficult for GA, [12] . The development and success of GA contributed greatly to a wider interest in computational approaches based on natural phenomena. It is now a major stand of the wider field of computational intelligence, which encompasses techniques such as neural networks, and artificial immunology. Genetic algorithms are search methods that can be used for both solving problems and modelling evolutionary systems. Since it is heuristic (it estimates a solution), GA differs from other heuristic methods in several ways. The most important difference is that it works on a population of possible solutions; while other heuristic methods use another important difference is that GA is not a deterministic but a probabilistic one.
A genetic algorithm is defined by [Fig-3] :
Individual or chromosome: a potential solution of the problem, it’s a sequence of genes.
• Population: a set of points of the research space.
• Environment: the space of research.
• Fitness function: the function to maximize / minimize.
Encoding of Chromosomes: it depends on the treated problem, the famous known schemes of coding are:
Binary encoding, permutation encoding, value encoding and tree encoding.
The Stochastic Operators are:
• Selection: replicates the most successful solutions found in a population at a rate proportional to their relative quality.
• Crossover: Decomposes two distinct solutions and then randomly mixes their parts to form novel solutions.
• Mutation: Randomly perturbs a candidate solution. In the selection process, some individuals are selected to be copied into a tentative next population. Individual with higher fitness value is more likely to be selected. The selected individuals are altered by the mutation and crossover and form a new population of solutions. The GA is simple yet provides an adaptive and robust optimization methodology [13] .
In this section, we give some methods previously used to estimate the minimum distance of error correcting codes; Multiple Impulse Method (MIM) and Genetic algorithm evaluators used by authors for some linear block codes [11] , and Chen’s Method for Cyclic codes [15] .
This method produces a tight minimum distance based on true (low-weight) codewords found by a fine-tuned local search. the principal is injecting a noise iteratively in a multiple random positions, on the contrary of error impulse method used by Berrou in [18] where the minimum distance is the magnitude of the noise that we inject to the ‘all zero” codeword’ in one position. In the MIM method the decoded word in the output of the Soft-In OSD decoder will be mostly near than the “all-zero” codeword, and the minimum distance of the code will be the minimum weight of the decoded words. The MIM algorithm described in [11] is as follow:
Inputs: G, the generator matrix
We assume that dt is in the range [ d0, d1 ] where d0 and d1 are two
integers. Then dt can be determined as follows:
Step 1: set Amin = d1 + 0.5 and dt = n - k 1;nb_test.
Step 2: For i=1 to nb_test
Step 2.1: A = d0 – 0.5;
Step 2.2: Set[()= TRUE];
Step 2.3: While[() = TRUE] && [A ≤ Amin-1.0]
Step 2.3.1: A = A + 1.0
Step 2.3.2: For nb_error = error_max to 1
Step 2.3.3: Subdivide A randomly on nb_error positions
Step 2.3.3.1: Y ← x (after modulation) + A
Step 2.3.3.2: OSD decoding of Y →
Step 2.3.3.3: If (weight() ≤ dt) then dt = weight(
)
Step 2.3.3.4: If() then [ (
)= TRUE ]
End for
End while
Step 2.4: Amin=A;
End for
Output: dt is the minimum distance
A general result for cyclic codes, due to Chen [15] is the following:
Theorem 1: Let c be a codeword of a cyclic [ n, k ] code. Suppose that the Hamming weight of c is equal to w. Then there exists a cyclic shift of c with exactly . Nonzero coordinates among its first k coordinates.
Some improvements of this theorem were obtained by Voloch [16] . With Chen's theorem, it is then possible to look for code words of weight w in a cyclic [ n, k ] code, given the systematic encoding matrix of the code.
Let G = [Ik M] be such a matrix where Ik is the identity matrix of size k. Then, if a codeword of Hamming weight w exists, it can be obtained by the linear combination of r rows of G. Chen's theorem gives then an explicit way to enumerate low weight codewords, provided that the number of combinations is not too large.
More precisely, if we denote aij for 0 ≤ i, j ≤ k the binary element at row i and column j of M, then for a given r value, Chen's algorithm amounts to enumerating vectors of the form:
[ mi1,1, mi2,2, ....... mir,r ]
Where denotes column wise modulo 2 operation. For each of these vectors, the Hamming weight is computed. If µ is the minimum value of the obtained Hamming weights, then the minimum Hamming weight of codewords obtained by linear combination of r rows of G is then r + µ. Doing this, for each possible w (and r) value, it is then possible to determine the minimum distance of the cyclic code generated by matrix G. In this work we use Chen’s Theorem to minimize the computing of the minimum distance used in the genetic algorithm presented in [10] . And we will focus on a special case of block codes: double and triple circulant codes.
The steps of the algorithm are organized as follow:
Step 1: randomly generate an initial population
Seed uniformly, randomly the initial population with a Ni, and where each individual is a word of length k with a random weight. We initiate the number of generation Ng to 1.
Step 2: while (Ng < Ngmax) do
Step 2.1: Compute the fitness of each individual in the population
An individual i represents an information vector of k bits which is encoded by the generator code to an n-bit code vector. The fitness is the weight of the encoded individual if this last is different to zero otherwise, the fitness is equal to n as a maximum value.
f ← weight (coding individual)
Step 2.2: Sort population in increasing order of fitness
Step 2.3: select the best Ne individuals in the intermediate population
Step 2.4: For i=Ne to Ni
Step 2.4.1: tournament select of two parents p1 and p2 for reproduction
Step 2.4.2: If (rand_value < pc) {Cross p1 and p2 to generate ch1 and ch2; Mutate ch1 and ch2 and introduce them in the next population} Else introduce p1 or p2 into the next population with equal probability.
End For
Step 2.5: Let currbest=fittest of the intermediate population. If (fitness(best) < fitness(currbest)) best=currbest
End while
Step 3: output best
In Step 2.4.1, we use the tournament selection, in that only one of two possible parents is preserved to reproduce two children whose will be inserted in the next generation.
Step 2.4.2, in this variant, the crossover operation depends on pc, and it is done before the mutation step which is done bit-wise on offspring with probability pm. In case of no-cross we insert the two initials parents in the next generation. We have used three strategies of crossover: a single crossover point, two point crossover, and uniform crossover. The two-point Crossover that randomly selects two crossover points within a chromosome then interchanges the two parent chromosomes between these points to produce two new offspring [Fig-4] . The Uniform Crossover uses a fixed mixing ratio between two parents. Unlike one- and two-point crossover, the Uniform Crossover enables the parent chromosomes to contribute the gene level rather than the segment level. An example of this operation is depicted in [Fig-5] .
From the MIM method presented above, we can pose the key question bellow: Which values of the parameters A and nb_error are good in terms of the minimization which they make on the weight of the decoded word by the OSD decoder ? In other words, which is the good impulse?
In this work, we will use a genetic algorithm to find these appropriate values. Consequently, the MIM-GA method will be works as follows:
Inputs:
- The population size Nind
- The maximum number of generations Ngm
- The crossover probability pcr
- The mutation probability pmu
- The mutation amplitude r
- The assumed interval [d0,d1] The number of positions nb_error
Outputs: dt
Begin
Step 1: Seed uniformly, randomly the initial population of Nind individuals, and where each individual is a word of n genes. Each gene is a reel value. These words are obtained by subdividing some random values (A between d0 and d1) on nb_error positions. At each individual, the modulated zero word is added. We initiate the number of generation Ng to 1 and dt to n.
Step 2: While(Ng < Ngm) do
Step 2.1: Compute the fitness of each individual in the population
Step 2.1.1: OSD decoding of the individual →
Step 2.1.2: f ← weight()
Step 2.1.2: if(f=0) then f ← n
Step 2.1.3: If(f ≤ dt) then dt ← f
Step 2.2: Sort population in increasing order of fitness
Step 2.3: insert the best individuals in the current population
Step 2.4: For i=2 to Nind
Step 2.4.1: Randomly select two parents p1 and p2 for reproduction
Step 2.4.2: If (rand_value < pcr)
{Cross p1 and p2 to generate ch;
Mutate ch according to pmu and r;
introduce ch in the current population}
Else insert p1 or p2 into the next population with equal probability.
End For
End while
Step 3: output dt
In order to compare the run times of MIM-GA and MIM algorithms, we fixe all the parameters of MIM-GA at the values outlined in the [Table-2] below:
The [Table-3] and [Table-4] below give the run time in seconds of the MIM and MIM-GA algorithms executed for some QR and BCH codes in the same computer, This run time is equal to the beginning of the algorithm and the moment of finding the lowest weight codeword.
The [Table-3] and [Table-4] clearly show that the MIM and MIM-GA algorithms give the same value of the estimated minimum distance. However, the run time of MIM-GA is much reduced comparing to the MIM version.
In order to find good DCC and TCC, we propose two approaches, in the first we use genetic algorithms (GA variant) and in the second we search randomly good headers (RS variant).
All simulations of the GA variant used to discover good codes were made with default GA parameters outlined in the [Table-5] .
The Algorithm of the GA Variant is described as follow
1. Generate an initial population, of Ni individuals, each individual is a word of weight w³ upper bound-1 where its length is equal to k for DCC, and it is equal to 2k for TCC.
Ng ← 0; fix the value of Ngmax
2. Make evolve the population:
• while (Ng
• fitness (individual) = d_MIM(individual)
• Sort the population by decreasing order of the fitness.
• m ← fitness (best individual)
• Copy the best Ne individuals (of big fitness) in the intermediate population.
• For i= Ne to Ni :
☆ Select a couple of parents (p1,p2) of individuals among the better.
☆ Generate a random number x: 0 ≤x≤1
☆ if x < pc then:
a) Cross p1 and p2 for generate ch1 and ch2
b) Mute ch1 and ch2
☆ Among ch1, ch2 select the word c' of the biggest fitness and insert it in the intermediate population.
• Ng ← Ng + 1.
The [Table-6] summarizes the good DCC codes that we found by the genetic variant, using the multiple impulse method. Where, we denote by LB the lower bound, and by UP, the Upper bound of the minimum distance of a given parameters of a linear code.
The algorithm of the random search (RS) variant using multiple impulse method, we try to discover good codes with best parameters. The algorithm is described as follow:
Inputs: k, n, Max
For i= 1 to Max
generate randomly the header of length k
Generate the Generator matrix G related to h1.
Evaluate the minimum distance d of the Code generated by G using MIM
If(d ≥ Lower Bound) save the code
End For
Outputs: list of good codes
The [Table-7] summarizes the good DCC codes that we found by random search variant, using the multiple impulse method and validated by the chen’s method.
The [Table-8] summarizes the good TCC codes that we found by random search variant, using the multiple impulse method and validated by the chen’s method.
In this paper, we have improved the MIM method in terms of its run time and we have proposed two approaches to search good DCC and TCC. These techniques have given a high performance based on the presented integration of MIM method. Our results show that the MIM method explained in this work lead to good DCC and TCC, and we have found some codes in this family with a higher minimum distance than the lower bound of a given length and dimension. Most importantly, the technique proposed is useful also to be applied to deal with other type of codes especially non-binary ones.
[1] Conway J.H. and Sloane N.J.A. (1999) Sphere Packings, Lattices and Groups, 3rd ed., Springer, New York.
» CrossRef » Google Scholar » PubMed » DOAJ » CAS » Scopus
[2] McWilliams F.J. and Sloane N.J.A. (1977) The Theory of Error-Correcting Codes, Amsterdam, The Netherlands: North-Holland Mathematical Library.
» CrossRef » Google Scholar » PubMed » DOAJ » CAS » Scopus
[3] Pless V. (1972) J. Combinatorial Theory, 12, 119-142.
» CrossRef » Google Scholar » PubMed » DOAJ » CAS » Scopus
[4] Pless V.S. and Huffman W.C. (1998) Handbook of Coding Theory, Elsevier, Amsterdam.
» CrossRef » Google Scholar » PubMed » DOAJ » CAS » Scopus
[5] Karlin M. (1969) IEEE Trans. Inform. Theory, 15, 81-92.
» CrossRef » Google Scholar » PubMed » DOAJ » CAS » Scopus
[6] Gaborit P. (2002) J. Combin. Theory, A97, 85-107.
» CrossRef » Google Scholar » PubMed » DOAJ » CAS » Scopus
[7] Comellas F., Roca R. (1993) International Workshop on Applications of Neural Networks to Telecommunications, 119-124.
» CrossRef » Google Scholar » PubMed » DOAJ » CAS » Scopus
[8] Wallis J. and Houghten K. (2002) Conference on Artificial Intelligence and Soft Computing, Banff.
» CrossRef » Google Scholar » PubMed » DOAJ » CAS » Scopus
[9] Lacan J., Chatonnay P. (1999) Computational Intelligence, Springer Berlin Heidelberg, 93-98.
» CrossRef » Google Scholar » PubMed » DOAJ » CAS » Scopus
[10] Azouaoui A., Askali M., Belkasmi M. (2011) International Conference on Multimedia Computing and Systems, Ouarzazate, Morocco, 829 - 833.
» CrossRef » Google Scholar » PubMed » DOAJ » CAS » Scopus
[11] Askali M., Azouaoui A., Nouh S., Belkasmi M. (2012) International Journal of Communications, Network and System Sciences, 5(11), 774-784.
» CrossRef » Google Scholar » PubMed » DOAJ » CAS » Scopus
[12] Dontas K., De Jong K. (1990) 2nd International IEEE Conference on Tools for Artificial Intelligence, 805-811.
» CrossRef » Google Scholar » PubMed » DOAJ » CAS » Scopus
[13] Coley D. (1999) An Introduction to Genetic Algorithms for Scientists and Engineers, World Scientific.
» CrossRef » Google Scholar » PubMed » DOAJ » CAS » Scopus
[14] Kasami T. (1974) IEEE Trans. Inform. Theory, 20(5), 679-679.
» CrossRef » Google Scholar » PubMed » DOAJ » CAS » Scopus
[15] Chen C.L. (1970) IEEE Trans. Inform. Theory, 16(3), 359-360.
» CrossRef » Google Scholar » PubMed » DOAJ » CAS » Scopus
[16] Voloch J. (2005) Computational and Applied Mathematics, 24, 393-398.
» CrossRef » Google Scholar » PubMed » DOAJ » CAS » Scopus
[17] Grassl M. (2006) Discovering Mathematics with Magma, Springer, 287-313.
» CrossRef » Google Scholar » PubMed » DOAJ » CAS » Scopus
[18] Berrou C., Vaton S., Jezequel M., Douillard C. (2002) IEEE Global Telecommunications Conference, 2, 1017-1020.
» CrossRef » Google Scholar » PubMed » DOAJ » CAS » Scopus
 | Fig. 1- A simplified model of communication system. |
 | Fig. 2- Bordered form of Double Circulant Code B = Circulant matrix presented by one header Ip = Identity matrix p*p. |
 | Fig. 3- The Basic Structure of Genetic Algorithm |
 | Fig. 4- Two-point Crossover structure. |
 | Fig. 5- Uniform Crossover structure. |
 | Table 1- Codewords of a code C (8, 4, 4) |
 | Table 2- Parameters of implementation of Genetic Algorithms |
 | Table 3- Comparaison of the Run time of MIM and MIM-GA for some QR codes |
 | Table 4- Comparaison of the Run time of MIM and MIM-GA for some BCH codes |
 | Table 5- Parameters of implementation of GA variant. |
 | Table 6- Good DCC codes obtained by GA variant |
 | Table 7- Good DCC found using random search variant and validated by the Chen’s method |
 | Table 8- Good TCC found using random search Algorithm and validated by the Chen’s method |