1st Edition

VLSI Architectures for Modern Error-Correcting Codes

ISBN 9781482229646
Published July 24, 2015 by CRC Press
410 Pages 124 B/W Illustrations

USD $175.00

Prices & shipping based on shipping country


Book Description

Error-correcting codes are ubiquitous. They are adopted in almost every modern digital communication and storage system, such as wireless communications, optical communications, Flash memories, computer hard drives, sensor networks, and deep-space probing. New-generation and emerging applications demand codes with better error-correcting capability. On the other hand, the design and implementation of those high-gain error-correcting codes pose many challenges. They usually involve complex mathematical computations, and mapping them directly to hardware often leads to very high complexity.

VLSI Architectures for Modern Error-Correcting Codes serves as a bridge connecting advancements in coding theory to practical hardware implementations. Instead of focusing on circuit-level design techniques, the book highlights integrated algorithmic and architectural transformations that lead to great improvements on throughput, silicon area requirement, and/or power consumption in the hardware implementation.

The goal of this book is to provide a comprehensive and systematic review of available techniques and architectures, so that they can be easily followed by system and hardware designers to develop en/decoder implementations that meet error-correcting performance and cost requirements. This book can be also used as a reference for graduate-level courses on VLSI design and error-correcting coding. Particular emphases are placed on hard- and soft-decision Reed-Solomon (RS) and Bose-Chaudhuri-Hocquenghem (BCH) codes, and binary and non-binary low-density parity-check (LDPC) codes. These codes are among the best candidates for modern and emerging applications due to their good error-correcting performance and lower implementation complexity compared to other codes. To help explain the computations and en/decoder architectures, many examples and case studies are included.

More importantly, discussions are provided on the advantages and drawbacks of different implementation approaches and architectures.

Table of Contents


List of Figures

List of Tables

Finite Field Arithmetic

Definitions, Properties and Element Representations

Finite Field Arithmetic

Multiplications Using Basis Representations

Inversions Using Basis Representations

Mapping Between Finite Field Element Representations

Mapping Between Standard Basis and Composite Field Representations

Mapping Between Power and Standard Basis Representations

Mapping Between Standard and Normal Basis Representations

VLSI Architecture Design Fundamentals

Definitions and Graph Representation

Pipelining and Retiming

Parallel Processing and Unfolding


Root Computations for Polynomials Over Finite Fields

Root Computation for General Polynomials

Root Computation for Linearized and Affine Polynomials

Root Computation for Polynomials of Degree Two or Three

Reed-Solomon Encoder and Hard-Decision and Erasure Decoder Architectures

Reed-Solomon Codes

Reed-Solomon Encoder Architectures

Hard-Decision Reed-Solomon Decoding Algorithms and Architectures

Peterson-Gorenstein-Zierler Algorithm

Berlekamp-Massey Algorithm

Reformulated Inversionless Berlekamp-Massey Algorithm and Architectures

Syndrome, Error Location, and Magnitude Computation Architectures

Pipelined Decoder Architecture

Error-and-Erasure Reed-Solomon Decoders

Algebraic Soft-Decision Reed-Solomon Decoder Architectures

Algebraic Soft-Decision Decoding Algorithms

Re-Encoded Algebraic Soft-Decision Decoder

Re-Encoding Algorithms and Architectures

Interpolation Algorithms and Architectures

Kotter's Interpolation Algorithm and Architectures

Lee-O'Sullivan Interpolation Algorithm and Architectures

Kotter's and Lee-O'Sullivan Interpolation Comparisons

Factorization Algorithm and Architectures

Prediction-Based Factorization Architecture

Partial-Parallel Factorization Architecture

Interpolation-Based Chase and Generalized Minimum Distance Decoders

Interpolation-Based Chase Decoder

Backward-Forward Interpolation Algorithms and Architectures

Eliminated Factorization

Polynomial Selection Schemes

Chien-Search-Based Codeword Recovery

Systematic Re-Encoding

Generalized Minimum Distance Decoder

Kotter's One-Pass GMD Decoder

Interpolation-Based One-Pass GMD Decoder

BCH Encoder and Decoder Architectures

BCH Codes

BCH Encoder Architectures

Hard-Decision BCH Decoding Algorithms and Architectures

Peterson's Algorithm

The Berlekamp's Algorithm and Implementation Architectures

3-Error-Correcting BCH Decoder Architectures

Chase BCH Decoder Based on Berlekamp's Algorithm

Interpolation-Based Chase BCH Decoder Architectures

Binary LDPC Codes and Decoder Architectures

LDPC Codes

LDPC Decoding Algorithms

Belief Propagation Algorithm

Min-Sum Algorithm

Majority-Logic and Bit-Flipping Algorithms

Finite Alphabet Iterative Decoding Algorithm

LDPC Decoder Architectures

Scheduling Schemes

VLSI Architectures for CNUs and VNUs

Low-Power LDPC Decoder Design

Non-Binary LDPC Decoder Architectures

Non-Binary LDPC Codes and Decoding Algorithms

Belief Propagation Decoding Algorithms

Extended Min-Sum and Min-Max Algorithms

Iterative Reliability-Based Majority-Logic Decoding

Min-Max Decoder Architectures

Forward-Backward Min-Max Check Node Processing

Trellis-Based Path-Construction Min-Max Check Node Processing

Simplified Min-Max Check Node Processing

Syndrome-Based Min-Max Check Node Processing

Basis-Construction Min-Max Check Node Processing

Variable Node Unit Architectures

Overall NB-LDPC Decoder Architectures

Extended Min-Sum Decoder Architectures

Extended Min-Sum Elementary Step Architecture

Trellis-Based Path-Construction Extended Min-Sum Check Node Processing

Iterative Majority-Logic Decoder Architectures

IHRB Decoders for QCNB-LDPC Codes

IHRB Decoders for Cyclic NB-LDPC Codes

Enhanced IHRB Decoding Scheme and Architectures



View More



Xinmiao Zhang received her Ph.D in electrical engineering from the University of Minnesota, Twin Cities, USA. She is currently an Associate Professor in the Department of Electrical and Computer Engineering at The Ohio State University. Previously, she was a Timothy E. and Allison L. Schroeder Associate Professor at Case Western Reserve University, Cleveland, Ohio. Between her academic positions, she continued her research on error-correcting codes at SanDisk/Western Digital Corporation. She has also been a visiting professor at Qualcomm and spent her sabbatical leave at the University of Washington, Seattle, USA. Her research focuses on VLSI architecture design for communications, digital signal processing, and cryptography. She is a recipient of the National Science Foundation Faculty Early Career Development (CAREER) Award.

Featured Author Profiles


"Error-correction coding has become an ineluctable feature for the development of modern telecommunication and storage systems. The VLSI implementation of powerful error-correcting codes and decoders with a minimum hardware resource is especially of great importance for the integration of the codes in high-speed, low consumption circuits. Such implementation requires a deep understanding of both mathematical theory of the codes and VLSI architecture design of their decoders, a dual expertise that Dr. Xinmiao Zhang was able to transcribe with high rigor and clarity in this book. From cyclic codes to the more recent binary and non-binary LDPC codes, this book equips any engineer or researcher with the necessary knowledge to implement state-of-the-art solutions."
—Prof. David Declercq, Director General of Research at the ENSEA, Cergy-Pontoise, France

"This book is unique in its synthesis of the advanced concepts in abstract algebra, decoding algorithms and architecture used masterfully to introduce VLSI implementations of highly sophisticated decoders of modern error correction codes."
—Bane Vasic, University of Arizona