About This Repository

This repository contains C++ and Python implementations of Guess & Check (GC) codes. The GC codes were first implemented using Python, which is easy to code, but slow. The codes were later implemented using C++, in an attempt to optimize the decoding performance. However, this is not a fully completed work. All we did was to translate what we had in Python to C++. We believe there is still a lot of room for optimization because of C++'s control over lower levels of computers' resources. Below are some of areas can be optimized:

1. The use of variables (try to reuse or maintain often used variable, don't make uneccessary copies when passing them to other fucnitons.)
2. NTL's Multithreading: NTL has its own multithreading library to speed up some matrix calculations.
3. Levenshtein Distance check (to minimize failure probability): this is available only in the Python implementation.

Guess & Check Codes for Deletions, Insertions, and Synchronization

This project is based on the Guess & Check (GC) codes, introduced by Serge Kas Hanna and Salim El Rouayheb. GC codes are binary codes that can correct multiple deletions (or insertions) with high probability. These codes have a redundancy that is logarithmic in the length of the information message. The encoding and decoding schemes of GC codes are deterministic and polynomial time. The decoding may fail in some cases, but the probability of failure is proven to be low in theory (asymptotically vanishing) and in practice. For instance, one of the simulations shows that a GC code with rate 0.8 can correct up to 4 deletions in a message of 1024 bits with no decoding failure detected within 10000 runs of simulations. GC codes can also be applied to file synchronization resulting in savings in total communication cost and number of communication rounds (https://arxiv.org/abs/1705.09569).

Below is an installation guide to help you run the C++ code. Note: running the Python code does not require performing the steps below.

Installation Guide for C++

Requirements

1. Number Theory Library (NTL) by Victor Shoup: You must install this library to your machine and correctly add the include path to its header files.
2. Recomended OS: Unix (Mac or Linux).
3. Compiler: g++ (because of NTL)

Additional Library

This implimentation is so much easier thanks to the help of Number Theory Library (NTL). This is a wonderful library that effectively deals with calculations in finite fields. Some of the helpful features include performing basic mathematical calculations in finite field, simulating abitrary sized numbers, and performing matrix manipulations in finite fields. A detailed installation guide can be found in Shoup's website. However, below are some tips and IDE settings that might be helpful to you.

Tips

Here is one quick way to compile this project in terminal is (assuming you have install NTL in /usr/local).

In Terminal:

cd /to/your/project/folder

g++ -g -O2 main.cpp -o main -lntl -lgmp -lm

Setup IDE

All of these settings are for your IDE to be able to compile NTL library.

1. Suggested IDE: CLion because this was done in CLion, but anything uses g++ compiler should work (with the right settings, see below).
2. Add additional linking flags to your linker setting: -lntl -lgmp -lm.
3. Add additional compiling flags to your compiler setting: -g -O2.
4. Change your default C++ compiler to g++ (if it is not already in used). Check this folder /usr/bin/g++ (although it could be at somewhere else depending on the Unix package manager you use.)

Warning to Windows Users

We did not verify if the C++ code (as is) compiles using Visual Studio's complier (MSVC). If you are testing these codes in a Windows machine, make sure you use g++ to compile this project. MinGW and Cygwin are the two tools that could help you to get the g++ compiler and Unix like Terminal.