Efficient Hardware Implementation of Iterative FEC Decoders

Abstract

Modern forward error correcting (FEC) codes with high-performance iterative decoders are of tremendous interest in the wireless communications research community. On the practical side, these codes have already been adopted in many wireless communication standards and are under consideration in numerous future standards. The widespread use of these codes places tremendous importance on decoder design and implementation. The goal of this research is to develop hardware FEC decoders that are efficient in their use of hardware resources and implementation effort. While our approach is quite general and is widely applicable, we focus on low density parity check (LDPC) codes and serially concatenated convolutional codes (SCCC) as design examples.

Use of Functional Programming

On this project, we used Kansas Lava to generate efficient forward error correcting codes. From a research point of view, we were attempting to to answer the following questions:

• Can we use use functional programming to complement and support the current development module of using MATLAB for a reference, and VHDL for an implementation.
• Can we build a functional program that mitigates against the need to perform frequent refactorings when working in VHDL, as a suitable architecture is discovered.
• Can we gain a stronger assurance of the relationship between the specification and implementation?
• What are the weaknesses of using a system like Lava to implement a FEC, and what are the remaining research problems with using EDSLs as an architecture bridge.

Relevent Publications

• A. Gill, T. Bull, A. Farmer, G. Kimmell, and E. Komp, “Types and associated type families for hardware simulation and synthesis: The internals and externals of Kansas Lava,” Journal of Higher-Order and Symbolic Computation, pp. 1–20, 2013.

• A. Gill and B. Neuenschwander, “Handshaking in Kansas Lava using patch logic,” in Practical Aspects of Declarative Languages, vol. 7149 of LNCS, Springer-Verlag, January 2012.

• A. Gill, “Declarative FPGA circuit synthesis using Kansas Lava,” in The International Conference on Engineering of Reconfigurable Systems and Algorithms, July 2011.

• A. Gill and A. Farmer, “Deriving an efficient FPGA implementation of a low density parity check forward error corrector,” in Proceedings of the 16th ACM SIGPLAN international conference on Functional programming, ICFP ’11, pp. 209–220, ACM, Sep 2011.

• A. Gill, T. Bull, D. DePardo, A. Farmer, E. Komp, and E. Perrins, “Using functional programming to generate an LDPC forward error corrector,” in Proceedings of the IEEE 19th Annual International Symposium on Field-Programmable Custom Computing Machines, FCCM ’11, pp. 133–140, IEEE Computer Society, May 2011.

• T. Bull, “Forward error correction and functional programming,” Master’s thesis, The University of Kansas, 2011.

• A. Gill, T. Bull, A. Farmer, G. Kimmell, and E. Komp, “Types and type families for hardware simulation and synthesis: The internals and externals of Kansas Lava,” in Post-Proceedings of Trends in Functional Programming, vol. 6546 of LNCS, Springer-Verlag, May 2010.

• A. Farmer, G. Kimmell, and A. Gill, “What’s the matter with Kansas Lava?,” in Post-Proceedings of Trends in Functional Programming, Springer-Verlag, LNCS 6546, May 2010.

• A. Gill, T. Bull, G. Kimmell, E. Perrins, E. Komp, and B. Werling, “Introducing Kansas Lava,” in Proceedings of the Symposium on Implementation and Application of Functional Languages, vol. 6041 of LNCS, Springer-Verlag, Sep 2009.

• B. Werling, E. Perrins, and A. Gill, “Implementation of an LDPC decoder using functional programming languages,” in Proceedings of the International Telemetering Conference, Oct 2009. (Student Paper).

• T. Bull, E. Perrins, and A. Gill, “Implementation of the viterbi algorithm using functional programming languages,” in Proceedings of the International Telemetering Conference, Oct 2009. (Student Paper).