Evolutionary Approaches to the Generation of Optimal Error Correcting Codes

Daniel McCarney^†, Brian Ross^‡, Sheridan Houghten^‡

Presented at GECCO 2012

Daniel McCarney
http://danielmccarney.ca
dmccarney@ccsl.carleton.ca

^† Carleton University, Ottawa, ON, Canada
^‡ Brock University, St. Catharines, ON, Canada

Arrow keys advance slides. Press 'm' for slide overview.

Error Correcting Codes (ECC)

What is an ECC?

• A collection of code words, expressed in an alphabet
• Each code word in code has a known relationship with all others
• Relationship can be exploited to detect & correct errors

Goals of an ECC:

• Express maximum (optimal) amount of information given constraints
• Detect corruption/error
• Repair error without requiring retransmission

Q-ary ECC's

Defined by three parameters: q, n, d

1. q - Alphabet size. Radix of symbols
2. n - Number of symbols in every code word. Code word length
3. d - Minimum edit distance constraint

Written: A_q(n,d)

Example

A₂(4,2)

• 000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111
• 0011 and 1011 are not compatible (Hamming distance 1)
• 0011 and 1110 are compatible (Hamming distance 3)
• Possible code: 0000, 0011, 1010, 1111

Properties

• Amount of information that can be expressed, the overhead involved, and the max tolerance for error are theoretically proven.
• Larger n or q allows for more information to be encoded. Larger d allows for more correction.
• ⌊(d−1)/2⌋ symbols can be corrected for by choosing the closest code word
• Optimal code has proven maximum # of code words for the n, q, d

Complexity

• Search for larger & more robust codes is computationally difficult
• Massive number of potential code words for large n, q
• Exponential number of comparisons to maintain min. dist. requirement
• NP-Hard, equivalent to maximum clique problem
• So let's use evolutionary search techniques!

Experiments

• Focused on just binary error correcting codes (q = 2)
• Edit distance taken as Hamming distance (number of bits differing between code words)
• Wanted to establish GP as a viable approach, not improve optimal bound on hard codes

Codes examined:

• A₂(12,6) - 2,510 code words to consider. Optimal code size of 24
• A₂(13,6) - 5,812 code words to consider. Optimal code size of 32
• A₂(17,6) - 121,670 code words to consider. Optimal code lower bound of 256

GA Approaches

• Fixed length chromosome, size equal to optimal # of code words in code
• Indirect indexing (I)
  • Gene values between 0 and # of possible code words
  • Treated as index into remaining compatible code words
• Direct Modulo indexing (DM)
  • Gene values between 0 and INT_MAX
  • Treated as index into all possible code words. Forward linear search when incompatible
• Fitness equal to # of compatible code words found

GP Approaches

• Motivation: fixed length linear chromosome representation not ideal.
• Strongly typed: code, code word
• Terminal nodes: code word index
• Function nodes: union, Conway union
  • Built in-progress code by collecting code words up
  • Only compatible code words added to code
• Baldwinian state object. Local search, not updating tree
• Played with function arity & tree processing order

Conway's Lexicode Algorithm

Greedy Algorithm for the creation of codes. Used as a local search in experiments.

• Generates all possible code words
• Sorts by ascending lexicographic order
• Normally starts with empty code, we "seed" code with GA/GP's work
• List of codes scanned linearly, adding valid code words as possible

Conway's Cont'd

GA Integration:

• Based on prior work, used Conway 'finish'
• Evolved code was used as starting point for Conway search
• Conway added code words greedily until options exhausted

GP Integration:

• Conway Union node
• Collects up code words from nodes beneath it like standard union
• Extends the code with a limited Conway search

Results Highlights

GA Results:

• A₂(13,6) hard for GA. Best found: 27 (of optimal 32)
• Conway finish provided the most benefit
• Statistically significant difference in quality of results between I and DM indexing.

GP Results:

• A₂(13,6), GP came much closer to optimal: 31 (of optimal 32)
• Baldwinian tree state made large difference.
• Use of Baldwinian tree state reached code size of 256 for A₂(17,6)

Conclusions

Comparisons:

• For A₂(13,6) GP and GA comparable.
• For A₂(17,6) GP converged much faster (less generations).
• In all cases, GP converged more reliably across the runs performed.
• Improved performance of GA with tweaked representation.
• Established GP as a viable approach to the problem.

Fin