rose.blog

Sending, storing and processing operations generate errors. One example of this is if I attempt to send you 64 bits of information over the internet, maybe only 63 of them arrive. Neither you nor I know which was deleted. A code to fix such a problem is called a single-deletion-correcting code. There are many other types of errors that occur, and modern encoding schemes need to correct all of them.

One family of encoding schemes can be found by solving for the Maximum Independent Set of a graph. I am not entirely sure how these graphs are constructed, but several challenge graphs whose Maximum Independent Sets provide error correction schemes, are posted here.

An application to generate error correction codes could comprise building these graphs based on desired error correction properties, and then solving for the Maximum Independent Set of these graphs using the Orion web services API.