Dissertation Defense, Ning Cheng

Dissertation Defense, Ning Chen

Title:         Efficient Implementations of Error Correcting Codes
                and Cryptography Systems

Date:        November 19, 2009
Time:         2:15pm

Location:  Packard Lab 360


As coding theory and cryptography play important roles in data transmission, their implementations are of great interests. This dissertation focuses on the design of architectures for the low-density parity-check (LDPC) decoders, Reed--Solomon (RS) decoders, the Advanced Encryption Standard (AES), and rank metric decoders for Gabidulin and K\"otter-Kschischang (KK) codes.

We propose partly parallel architectures based on optimal overlapped sum-product (OSP) decoding and parallel turbo-sum-product (PTSP) decoding. To ensure high throughput and hardware utilization efficiency, partly parallel parity check and pipelined access to memory are utilized.

FPGA implementations of our proposed architectures for a (1536, 768) (3,6)-regular quasi-cyclic (QC) LDPC code achieve higher throughput than other architectures.

We investigate the complexity of syndromeless decoding, and compare it to that of syndrome-based decoding. For high rate RS codes, when compared to syndrome-based decoding algorithms, not only syndromeless decoding algorithms require more field operations, but also decoder architectures based on them have higher hardware costs and lower throughput.

We propose a novel common subexpression elimination (CSE) algorithm for matrix-vector multiplications over characteristic-2 fields, taking advantage of the cancellation property. Using our CSE algorithm, we reduce the additive complexity of cyclotomic FFT (CFFT). Our CFFTs achieve smaller total complexities than previously proposed CFFTs and other FFTs. Utilizing our CFFTs in both transform-domain and time-domain RS decoders, we achieve significant complexity reductions.

We further extend our CSE algorithm so that it reduces the gate count while satisfying any feasible logic CPD (LCPD) requirement. Using the new CSE algorithm, we propose high-performance designs for two

major transformations of the AES, MixColumns (MC) and SubBytes (SB), as well as their inverses. Compared with prior works, our designs not only offer a wider range of area-CPD tradeoffs, but also achieve smaller gate counts with the same LCPDs.

Rank metric codes attract attentions for their applications in network coding. Although rank metric decoders have been proposed for both Gabidulin and KK codes, it is not clear whether such decoders are

feasible and suitable for hardware implementations. In this dissertation, we propose novel decoder architectures for both codes. The synthesis results of our decoder architectures for Gabidulin and KK codes show that our architectures not only are affordable, but also achieve high throughput.

Ph.D. Committee:

Prof. Zhiyuan Yan (Chair), ECE, Lehigh University

Prof. Meghanad Wagh, ECE, Lehigh University

Prof. Tiffany Jing Li, ECE, Lehigh University

Dr. Xingdong Dai, LSI