Open Topics in the Area of Guesswork

Guessing Noise to Decode Messages

(Supervisor: Juan Cabrera)

An ideal channel decoder would implement a maximum likelihood decoding technique to guess what message was transmitted. This is guessing which codeword was sent by maximizing the probability of receiving the obtained message. Because this is computationally complex, channel codes are designed backward. I.e., the design of a low-complexity decoder comes first followed by the encoder. This limits the type of codes that can be used because not all codes can be decoded in practical time. However, researchers from MIT and Maynooth University have proven that by guessing the noise in the transmission channel instead of the message you can obtain similar results to a maximum likelihood decoder. The mathematical proof is complicated, yet the principle of operation is quite simple: If you receive a stream of bits that is not a valid codeword, you can flip one bit and ask if the new codeword is a valid one. If it is not, flip a different bit and repeat the process. If the probability of an error bit is low, then with a few flips and questions it is possible to decode. This opens the door to new codes since the decoding process is universal and potentially independent of the code used. We want to implement these novel techniques into our wireless system. To do that, we want to use Software Defined Radio to build the wireless channel and benchmark the novel decoder with state of the art codecs.