Optimal communication scheduling for iterative decoding of irregular codes

Many important and newer classes of error-correction codes, such as LDPC, expander, repeat-accumulate or polar codes have a bipartite graph representation of their computation. Decoders for such codes are practically implemented using iterative decoding over such bipartite graphs. The iterative decoding progresses as per various communication schedules between the nodes on both sides of the graph. The schedules are designed to be optimal typically in the latency or the throughput of decoding process. Designing optimal schedules for irregular or partial regular codes, which have found way in communication standards such as DVB-S2 and WiMAX, is a challenging problem. In our work, we have tried to design VLSI decoding schemes having optimal communication schedule for such codes. We employed edge-coloring based greedy approach for communication scheduling during the decoding process for such codes. The communication throughput of such decoder systems is provably optimal. As such, it is well-known that the irregular-graph based codes can asymptotically achieve the Shannon limit on erasure channels. Hence we are hopeful that irregular graphs will be used in many other practical error correction systems in future, for which usage of such optimal communication scheduling will lead to efficient design of decoders.