Tutte Polynomials and Performances of Individual Rows of Reed–Muller Codes of Length 64 and 128 on Erasure Channels

Iwan Duursma, University of Illinois at Urbana-Champaign

Usage Details

The Tutte Polynomial is an essential ingredient in understanding the performance/efficiency/reliability of a code, a technique to communicate over noisy channels. Reed–Muller codes, invented 64 years ago, play an important role in the long history of codes. They are used both in theory results and as building blocks for many other codes. They are receiving increased attention with the invention in 2008 by Arikan of polar codes, a direct descendent of Reed–Muller codes.

Polar codes combine a low complexity with excellent performance. They are now being adapted as part of the 5G standard. As of this time there is no complete comparison available between Reed–Muller codes and polar codes. Experiments suggest that while polar codes are proven to have excellent performance, Reed–Muller codes perform much better than expected and may even outperform polar codes.

We aim to make a full comparison between the performance of polar codes and Reed–Muller codes for codes of length 64. We will do this by computing the Tutte polynomial of a Reed–Muller code of length 64. We come up with an algorithm that reduces the cost by a factor of 50000 yet gives detailed performances of individual rows which will permanently change how people view and utilize Reed–Muller codes and polar codes.

The computation is possible only if one has access  to tens of thousands of CPU-hours and a more detailed analysis of performances can be obtained  only if the intermediate data can be exported and stored at the same speed that they are generated.  For Reed–Muller codes of length 128 a similar computation including all details is not feasible.  But a reduced version will provide important statistics that will validate the performance results for codes of length 64 to codes of higher length.