Low-Complexity Transformed Encoder Architectures for Quasi-Cyclic Non-binary LDPC Codes Over Subfields

by | Oct 24, 2017 | ieee project

Low-Complexity Transformed Encoder Architectures for Quasi-Cyclic Non-binary LDPC Codes Over Subfields

Abstract:

Quasi-cyclic low-density parity-check (QC-LDPC) codes are adopted in many digital communication and storage systems. The encoding of these codes is traditionally done by multiplying the message vector with a generator matrix consisting of dense circulant submatrices. To reduce the encoder complexity, this paper introduces two schemes making use of finite Fourier transform. We focus on QC-LDPC codes whose circulant submatrices are of dimension (2r−1) × (2r−1) and the entries are elements of GF(2p), where p divides r, and hence, GF(2p) is a subfield of GF(2r). These cover a broad range of codes, and binary LDPC codes are a special case. Making use of conjugacy constraints, low-complexity architectures are developed for finite Fourier and inverse transforms over subfields in this paper. In addition, composite field arithmetic is exploited to eliminate the computations associated with message mapping and reduce the complexity of Fourier transform. For a (2016, 1074) nonbinary QC-LDPC code whose generator matrix consists of circulants of dimension 63×63 with GF(22)entries, the proposed encoders achieve 22% area reduction compared with the conventional encoders without sacrificing the throughput. The proposed architecture of this paper analysis the logic size, area and power consumption using Xilinx 14.2.

Existing System:

Quasi-cyclic LDPC (QC-LDPC) codes enable efficient partial-parallel processing because of the regularity in their parity-check matrices H. The H matrix of a binary QC-LDPC code consists of cyclic permutation matrices (CPMs), and that of a QCNB-LDPC code can be designed by replacing each “1” in the CPMs with elements of GF(2p)(p>1). The dimension of the CPMs is usually moderate or large in order to reach a reasonably long codeword length. On the other hand, p needs to be small to keep the decoder complexity low.

This paper focuses on the cases that the dimension of the CPMs is(2r −1)×(2r −1) and pdividesr. Accordingly,GF(2p)is a subfield of GF(2r). These cases are quite versatile and binary codes are a special case with p=1.

LDPC code design usually starts with the H matrix. If H has a lower triangular structure, then the encoding can be done by using H directly. However, such an H matrix often has at least a few columns with low weight. This makes the corresponding bits more likely stay at wrong values, especially in bit-flipping type of decoders, and hence leads to earlier error floor. A more general encoding method that applies to code with any H is to derive a systematic generator matrix G from H first, and then multiply the message vector with G[5]. The computed G consists of blocks of circulant matrices, and the circulants corresponding to the parity symbols are usually dense. This means that a large number of multipliers are required for encoding.

A transformed approach was proposed to reduce the encoder complexity of binary QC-LDPC codes. Applying finite Fourier transform, each dense circulant becomes a diagonal matrix, and hence, the number of multipliers needed for the transformed generator matrix multiplication is greatly reduced at the cost of Fourier transform and some message mapping. Later, two improved encoding methods making use of finite Fourier transform were described. They are the binary cases of the encoders over subfields developed independently. No hardware implementation architecture was provided. If implemented directly according to the formulas, the overheads brought by the Fourier transform, message mapping, and their inverse may offset the savings achieved by the simplified generator matrix multiplication.

Disadvantages:

  • Area coverage is high

Proposed System:

To simplify the notations, this section uses a QCNB-LDPC code over GF(22)(p=2) whose generator matrix consists of circulants of dimension 63×63 (r=6) to explain the proposed encoder architectures. Our architectures can be easily extended to codes with different p and r values, such that p|r. Binary codes belong to these cases with p=1. Each component is detailed before the overall encoder architectures are summarized. The same composite field arithmetic, Fourier and inverse transform architectures, and generator matrix multiplication architecture are used in both encoders.

Composite Field Construction; To construct GF ((2p)t) from GF(2p), a degree-t irreducible polynomial over GF(2p), f(x), is needed. As aforementioned, an element a ∈ GF((2p)t) can be represented as a polynomial in x with degreet −1,at−1x t−1+ ···+a1x+a0, whose coefficients are elements of GF(2p). Finite field multiplication is defined as polynomial multiplication modulo f(x), and field addition is done as polynomial addition. GF(22) is constructed using f0(x)=x2+x+1. It is the only degree-2 irreducible polynomial over GF(2). However, for constructing GF((22)3)from GF(22), there are quite a few options for the irreducible polynomial. To reduce the complexity of finite field multiplications, an irreducible polynomial with fewer nonzero terms is preferred. For example, f1(x) =x3 +φ, where φ=’10’∈GF (22), is a degree-3 irreducible polynomial over GF(22)with the fewest nonzero terms.

Figure 1: Format of transformed generator matrix for a QC-LDPC code

Transformed Generator Matrix Multiplication Architecture:

The transformed generator matrix, GF, is in the format shown in Fig.1.Eache×esubmatrix in the parity columns is a diagonal matrix, and the entries in the diagonal satisfy the conjugacy constraints. Therefore, only the leading symbols in those diagonals need to be stored, and the memory requirement is reduced. In addition, each block of e symbols in the products m GF and mFGF also satisfies the conjugacy constraints. Hence, unlike it was suggested, only the leading symbols in the products are computed in our designs, and the others are recovered if needed by 2p th power, whose complexity is lower than that of a general multiplier. As a result, substantially fewer multipliers are needed in the transformed generator matrix multiplication. A similar idea was used in the encoder variation of that computes mGF to reduce the number of multiplications needed in mapping the products. Fig. 2 shows partial-parallel architecture for the transformed generator matrix multiplication.

Figure 2: Partial-parallel transformed generator matrix multiplication architecture

Advantages:

  • Area coverage is reduced

Software implementation:

  • Modelsim
  • Xilinx ISE