![](media/image1.wmf){width="0.925in" height="0.7493055555555556in"}

**Goddard Technical Standard**

**Low Density Parity Check Code for Rate 7/8**

**GSFC -- STD -- 9100**

**Release Pending**

**May 1, 2006**

THIS STANDARD HAS NOT BEEN REVIEWED FOR EXPORT CONTROL RESTICTIONS;
CONSULT YOU CENTER/HEADQUARTERS EXPORT CONTROL PROCEDURES/AUTHORITY
PRIOR TO DISTRIBUTION OF THIS DOCUMENT

CONTENTS

**[Section]{.underline}** **[Page]{.underline}**

[**1.** **Purpose 1**](#purpose)

[2. Scope 1](#scope)

[3. Numbering Convention 1](#numbering-convention)

[4. Conformance 2](#conformance)

[5. Technical Introduction 2](#technical-introduction)

[6. Baselined (8176,7156) LDPC Code 4](#baselined-81767156-ldpc-code)

[7. Encoding 6](#encoding)

[8. Proposed Shortened (8160, 7136) Code Standard
9](#shortened-8160-7136-code-standard)

[9. Randomization and Synchronization
10](#randomization-and-synchronization)

[10. References 10](#references)

[11. Appendix A -- Generator Matrix Circulant Table (Normative)
11](#appendix-a-generator-matrix-circulant-table-normative)

[12. Appendix B -- Complexity (Informative)
13](#appendix-b-complexity-informative)

[13. Appendix C -- FPGA Test Results (Informative)
14](#appendix-c-fpga-test-results-informative)

LIST OF FIGURES

**[Figures]{.underline}** **[Page]{.underline}**

[Figure 1: Bit Numbering Convention 2](#__RefHeading___Toc132094880)

[Figure 2. Example of a 15 x 15 circulant matrix
3](#__RefHeading___Toc132094881)

[Figure 3. Example of a quasi-cyclic matrix
3](#__RefHeading___Toc132094882)

[Figure 4. Base Parity Check Matrix of the (8176, 7156) LDPC code
4](#__RefHeading___Toc132094883)

[Figure 5. Scatter Chart of Parity Check Matrix
5](#__RefHeading___Toc132094884)

[Figure 6. Systematic Circulant Generator Matrix of 14 x 16 Cirulants
7](#__RefHeading___Toc132094885)

[Figure 7. Encoder Diagram 8](#__RefHeading___Toc132094886)

[Figure 8. Proposed Shortened Codeword Standard
9](#__RefHeading___Toc132094887)

[Figure 9. Bit Error Rate Test Results 14](#__RefHeading___Toc132094888)

[Figure 10. Block Error Rate Test Results
15](#__RefHeading___Toc132094889)

LIST OF TABLES

**[Table]{.underline}** **[Page]{.underline}**

[Table 1. Specification of Circulants 5](#__RefHeading___Toc128467594)

[Table 2. Table of Circulants for the Generator Matrix
11](#__RefHeading___Toc128467595)

# Purpose

The purpose of this document is to establish a common GSFC channel
coding standard for bandwidth efficient spacecraft communications.
Currently many Goddard missions use the concatenated Reed-Solomon and
convolutional coding technique for space to ground links. While this
standard has served NASA well in the past it is bandwidth inefficient.
The need for bandwidth efficiency has prompted the Microwave and
Communication Systems Branch (Code 567) to search for a new channel code
that require less bandwidth without paying a heavy penalty in power
requirement and complexity. This document details the result of that
search. It gives a technical description of this new channel coding
called low density parity check (LDPC) coding (Section 5). A description
of the baselined LDPC code is presented in Section 6 and it's encoding
in Section 7. However, the baselined code needs to be modified to ease
implementations for current space and ground systems. This modification
is the proposed standard and is described in Section 8. Section 9
outlines synchronization issues and the Sections 12 and 13 of the
Appendices discusses complexity issues and performance testing
respectively. The reader is assumed to have a basic understanding of
channel coding theory (linear algebra also) and digital communications.
(The reader is encouraged to review \[7\] for an overview of linear
block codes).

# Scope

The concepts and protocols for this document are designed for any space
communications link although it was initially targeted for
communications links between spacecraft to ground elements. Current
advances in space qualified field programmable gate array (FPGA)
technology has potentially given rise to implementations for space to
space communication links as well. As a result, this document can apply
to any space link that requires bandwidth efficient communications.

# Numbering Convention

This document adheres to the following convention with few exceptions:
the first bit in a data field (e.g. codeword or column of matrix as it
relates to the codeword) to be transmitted is defined to be "Bit 1"; the
following bit is defined to be "Bit 2" and so on up to "Bit N", as shown
in Figure 1. In the instances where the data field begins with Bit 0, it
will end with Bit N-1 but follow the same ascending order. When the
field is used to express a binary value, the most significant bit (MSB)
is the first transmitted bit of the field.

![](media/image2.wmf)

[]{#__RefHeading___Toc132094880 .anchor}Figure 1: Bit Numbering
Convention

# Conformance

An implementation conforms to this standard by conforming to Sections
6-8, the normative references of Section 10, and Section 11. Sections 6,
7 and 11 specifies the encoding, while 8 section define the format of
the codeword. Section 9 is a recommendation for pseudo-randomization of
the codeword and codeword synchronization. While not essential to this
standard, methods to guarantee sufficient bit transitions and to provide
codeword synchronization to the receiver are required. Therefore,
Section 9 is strongly recommended.

# Technical Introduction

A linear block code is designated in this specification by (n, k) where
n is the length of the codeword (or block) and k is the length of the
information sequence. LDPC codes are linear block codes in which the
ratio of the total number of 1's to the total number of elements in the
parity check matrix is \<\< 0.5. The distribution of the 1's determine
the structure and performance of the decoder. An LDPC code is defined by
its parity check matrix. The k x n generator matrix which is used to
encode a linear block code can be derived from the parity check matrix
through linear operations. In general, a codeword **v** is obtained by
matrix multiplication of the information sequence or vector **u** and
the generator matrix **G**.

The LDPC code considered in this specification is a member of a class of
codes called Quasi-Cyclic codes. The construction of these codes
involves juxtaposing smaller circulants (or cyclic submatrices) to form
a larger parity check or base matrix.

An example of a circulant is shown in Figure 2. Notice that every row is
one bit right cyclic shift (where the end bit is wrapped around to the
beginning bit) of the previous row. The entire circulant is uniquely
determined and specified by its first row. For this example the first
row has 4 1's or a row weight of 4.

$\begin{bmatrix}
0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 \\
1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 \\
0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 \\
0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 \\
1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 \\
0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\
1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\
1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0
\end{bmatrix}$

[]{#__RefHeading___Toc132094881 .anchor}Figure 2. Example of a 15 x 15
circulant matrix

An example of a quasi-cyclic parity check matrix is shown in Figure 3.
In this case, a quasi-cyclic 10 x 25 matrix is formed by an array of 2 x
5 circulant submatrices of size 5 x 5. To unambiguously describe this
matrix, only the position of the 1's in the first row of every circulant
submatrix and the location of each submatrix within the base matrix is
needed.

![](media/image3.wmf){width="5.9992125984251965in"
height="2.516535433070866in"}

[]{#__RefHeading___Toc132094882 .anchor}Figure 3. Example of a
quasi-cyclic matrix

Constructing parity check matrices in this manner produces two positive
features:

1\. the encoding complexity can be made linear with the code length or
parity bits using shift registers, and

2\. encoder and decoder routing complexity in the interconnections of
integrated circuits is reduced.

#  Baselined (8176,7156) LDPC Code

#   {#section .unnumbered}

The baselined LDPC code described in this section is the foundation for
the proposed standard shortened code defined in Section 8.

The parity check matrix for the baselined (8176, 7156) LDPC code is
formed by using a 2 x 16 array of 511 x 511 square circulants. This
creates a parity check matrix of dimension 1022 x 8176. The structure of
the parity check base matrix is shown in Figure 4.

$$\begin{bmatrix}
A_{1,1} & A_{1,2} & A_{1,3} & A_{1,4} & A_{1,5} & A_{1,6} & A_{1,7} & A_{1,8} & A_{1,9} & A_{1,\text{10}} & A_{1,\text{11}} & A_{1,\text{12}} & A_{1,\text{13}} & A_{1,\text{14}} & A_{1,\text{15}} & A_{1,\text{16}} \\
A_{2,1} & A_{2,2} & A_{2,3} & A_{2,4} & A_{2,5} & A_{2,6} & A_{2,7} & A_{2,8} & A_{2,9} & A_{2,\text{10}} & A_{2,\text{11}} & A_{2,\text{12}} & A_{2,\text{13}} & A_{2,\text{14}} & A_{2,\text{15}} & A_{2,\text{16}}
\end{bmatrix}$$

[]{#__RefHeading___Toc132094883 .anchor}Figure 4. Base Parity Check
Matrix of the (8176, 7156) LDPC code

Each A~i,j~ is a 511 x 511 circulant. The row weight of the each of the
32 circulants is 2, i.e. there are two 1's in each row. The total row
weight of each row in the parity check matrix is 2 x 16 or 32. The
column weight of each circulant is also 2, i.e. there are two 1's in
each column. The total weight of each column in the parity check matrix
is 2 x 2 or 4. The position of the 1's in each circulant is defined in
table 1. A scatter chart of the parity check matrix is shown in Figure 5
where every 1 bit in the matrix is represented by a point.

![](media/image4.jpeg){width="6.497222222222222in"
height="5.134722222222222in"}

[]{#__RefHeading___Toc132094884 .anchor}Figure 5. Scatter Chart of
Parity Check Matrix

[]{#__RefHeading___Toc128467594 .anchor}Table 1. Specification of
Circulants

  ----------- ------------------------ -----------------------------------
  Circulant   1's position in 1^st^    Absolute 1's position in 1^st^ row
              row of circulant         of Parity Check Matrix

  A~1,1~      0, 176                   0, 176

  A~1,2~      12, 239                  523, 750

  A~1,3~      0, 352                   1022, 1374

  A~1,4~      24, 431                  1557, 1964

  A~1,5~      0, 392                   2044, 2436

  A~1,6~      151, 409                 2706, 2964

  A~1,7~      0, 351                   3066, 3417

  A~1,8~      9, 359                   3586, 3936

  A~1,9~      0, 307                   4088, 4395

  A~1,10~     53, 329                  4652, 4928

  A~1,11~     0, 207                   5110, 5317

  A~1,12~     18, 281                  5639, 5902

  A~1,13~     0, 399                   6132, 6531

  A~1,14~     202, 457                 6845, 7100

  A~1,15~     0, 247                   7154, 7401

  A~1,16~     36, 261                  7701, 7926

  A~2,1~      99, 471                  99, 471

  A~2,2~      130, 473                 641, 984

  A~2,3~      198, 435                 1220, 1457

  A~2,4~      260, 478                 1793, 2011

  A~2,5~      215, 420                 2259, 2464

  A~2,6~      282, 481                 2837, 3036

  A~2,7~      48, 396                  3114, 3462

  A~2,8~      193, 445                 3770, 4022

  A~2,9~      273, 430                 4361, 4518

  A~2,10~     302, 451                 4901, 5050

  A~2,11~     96, 379                  5206, 5489

  A~2,12~     191, 386                 5812, 6007

  A~2,13~     244, 467                 6376, 6599

  A~2,14~     364, 470                 7007, 7113

  A~2,15~     51, 382                  7205, 7536

  A~2,16~     192, 414                 7857, 8079
  ----------- ------------------------ -----------------------------------

Note that the numbers in the second column represent the relative column
position of the 1's in the first row of each circulant. Since there are
only 511 possible positions, these numbers can only range from 0 to 510.
The third column represents the absolute position of the 1's in the
parity-check matrix. There are exactly 8176 possible; therefore these
numbers can only range from 0 to 8175.

# Encoding 

The generator matrix for the baselined (8176, 7156) code (Figure 4)
consists of two components:

-   The first component is a 7154 x 8176 submatix in
    systematic-circulant form as shown in Figure 6. It consists of a
    7154 x 7154 identity matrix and two columns of 511 x 511 circulants
    B*~i,j~*'s, each column consisting of 14 circulants. The I's are the
    511 x 511 identity submatrices and the 0's are the all zero 511 x
    511 submatrices.

-   The second component consists of two independent rows (not shown).

The first component generates a (8176, 7154) LDPC subcode of the (8176,
7156) code. The subcode is a subset of codewords from the baseline code.
Each codeword in the subcode consists of 7154 information bits and 1022
parity-check bits. For reasons given in Section 8, there are advantages
in using only the subcode implementation. The diagram in Figure 7 is an
example of how an encoder can be designed using the circulants
B*~i,j~*'s. (Please refer to \[8\] for additional information on
encoding.) Appendix A gives the values of the first row of these
circulants. These values are initialized or loaded in the shifted
registers at the start of each information sequence. The top circuit is
responsible for parity bits P1 to P511 and the bottom circuit for bits
P512 to P1022. After initialization, two parity bits are created, P1 and
P512, then after 510 shifts, all of the parity bits are generated.
Afterwards, a codeword shortening procedure is performed in accordance
to Section 8.

There are many other ways to design the encoder based on the generator
matrix in Figure 6. These schemes have complexities that are
proportional to the length of the codeword or parity check bits \[8\].

$$\begin{bmatrix}
I & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & B_{\text{1,1}} & B_{\text{1,2}} \\
0 & I & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & B_{\text{2,1}} & B_{\text{2,2}} \\
0 & 0 & I & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & B_{\text{3,1}} & B_{\text{3,2}} \\
0 & 0 & 0 & I & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & B_{\text{4,1}} & B_{\text{4,2}} \\
0 & 0 & 0 & 0 & I & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & B_{\text{5,1}} & B_{\text{5,2}} \\
0 & 0 & 0 & 0 & 0 & I & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & B_{\text{6,1}} & B_{\text{6,2}} \\
0 & 0 & 0 & 0 & 0 & 0 & I & 0 & 0 & 0 & 0 & 0 & 0 & 0 & B_{\text{7,1}} & B_{\text{7,2}} \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & I & 0 & 0 & 0 & 0 & 0 & 0 & B_{\text{8,1}} & B_{\text{8,2}} \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & I & 0 & 0 & 0 & 0 & 0 & B_{\text{9,1}} & B_{\text{9,2}} \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & I & 0 & 0 & 0 & 0 & B_{\text{10,1}} & B_{\text{10,2}} \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & I & 0 & 0 & 0 & B_{\text{11,1}} & B_{\text{11,2}} \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & I & 0 & 0 & B_{\text{12,1}} & B_{\text{12,2}} \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & I & 0 & B_{\text{13,1}} & B_{\text{13,2}} \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & I & B_{\text{14,1}} & B_{\text{14,2}}
\end{bmatrix}$$

[]{#__RefHeading___Toc132094885 .anchor}Figure 6. Systematic Circulant
Generator Matrix of 14 x 16 Cirulants

![](media/image5.wmf)

[]{#__RefHeading___Toc132094886 .anchor}Figure 7. Encoder Diagram

# Shortened (8160, 7136) Code Standard

The code described in section 6 is shortened to the dimensions of (8160,
7136) by the method outlined in this section.

Using the generator matrix given by Figure 6, an encoder can be
implemented using circuits described in section 7 and in \[8\]. This
encoder generates a (8176, 7154) LDPC subcode of the (8176, 7156) code.
Current spacecraft and ground systems manipulate and process data at
32-bit computer word size. Neither (8176, 7154) or (8176, 7156) is a
multiple of 32. It is beneficial to shorten the codeword to the
dimensions of (8160, 7136). In other words, by shortening the
information sequence to 7136 through the use of 18 bits of virtual fill,
the (8176, 7154) subcode encoder can be used. This is accomplished by
encoding the virtual fill bits with zeros but not transmitting them;
thus the total codeword length becomes 8158. Note that it is not
necessary to add two independent rows to the generator matrix to encode
the full (8176, 7156) code because these bits would be shortened anyway
and so the subcode is sufficient and less complicated for this
application. Since the codelength of 8158 is two bits shy of 8160, an
exact multiple of 32, two bits of actual transmitted zero fill are
appended to end of the codeword to achieve a shortened code dimension of
(8160, 7136) bits or (1020, 892) octets or (255, 223) 32-bit words. The
shortened codeword is shown in Figure 8.

The received shortened codeword would require the removal of the 2 zero
fill bits prior to decoding. The decoder would then reproduce the 18
virtual fill zeros after processing but would, in general, not pass
these 18 zeros on to the ground equipment.

![](media/image6.wmf)

[]{#__RefHeading___Toc132094887 .anchor}Figure 8. Proposed Shortened
Codeword Standard

# Randomization and Synchronization

The use of the shortened (8160, 7136) LDPC standard code does not
guarantee sufficient bit (symbol) transitions to acquire or maintain bit
(symbol) synchronization. It is highly recommended that a
pseudo-randomizer be used after encoding in accordance to CCSDS
recommendation 131.0-B-1, TM Synchronization and Channel Coding. Blue
Book. Issue 1. September 2003 Section 7.

In addition, codeword synchronization is required so that the receiver
can identify the beginning of the codeword for proper decoding. The use
of an attached sync marker (ASM) as specified in CCSDS recommendation
131.0-B-1, TM Synchronization and Channel Coding. Blue Book. Issue 1.
September 2003 Section 6.6 is required. Note that the ASM is not
pseudo-randomized.

# References

Informative References:

\[1\] D. J. C. MacKay and R. M. Neal, "Near Shannon limit performance of
low density parity check codes," *Electro. Lett.*, vol. 32, pp.
1645-1646, Aug. 1996.

\[2\] R. G. Gallager, "Low density parity check codes," *IRE Trans.
Inform. Theory*, IT-8, pp. 21-28, Jan. 1962.

\[3\] T. Richardson and R. Urbanke, "Design of capacity-approaching low
density parity check codes," *IEEE Trans. Inform. Theory*, vol. 47, pp.
619-637, Feb. 2001.

\[4\] Y. Kou, S. Lin, and M. P. C. Fossorier, "Low-density parity-check
codes based on finite geometries: a rediscovery and new results," *IEEE
Trans. Information Theory*, vol. 47, pp. 2711-2736, Nov. 2001.

\[5\] W. Fong, "White Paper for Low Density Parity Check (LDPC) Codes
for CCSDS Channel Coding Blue Book," CCSDS P1B Channel Coding Meeting:
Houston, TX, Oct. 2002.

\[6\] J. Heo, "Analysis of scaling soft information on low density
parity check code," *Electro. Lett.*, vol. 39, pp. 219-221, Jan. 2003.

\[7\] S. Lin and D. Costello, Jr. *Error Control Coding, 2^nd^ Ed.* New
Jersey: Pearson Prentice Hall, 2004.

Normative References:

\[8\] Z. Li, L. Chen, L. Zeng, S. Lin, and W. Fong, "Efficient Encoding
of Quasi-Cyclic Low Density Parity Check Codes," *IEEE Transactions on
Communication*, vol. 53, pp. 71-81, Jan. 2006.

#  Appendix A -- Generator Matrix Circulant Table (Normative)

[]{#__RefHeading___Toc128467595 .anchor}Table 2. Table of Circulants for
the Generator Matrix

  ------------ ----------------------------------------------------------------------------------------------------------------------------------
  Circulant    1^st^ row of circulant

  B~1,1~       55BF56CC55283DFEEFEA8C8CFF04E1EBD9067710988E25048D67525426939E2068D2DC6FCD2F822BEB6BD96C8A76F4932AAE9BC53AD20A2A9C86BB461E43759C

  B~1,2~       6855AE08698A50AA3051768793DC238544AF3FE987391021AAF6383A6503409C3CE971A80B3ECE12363EE809A01D91204F1811123EAB867D3E40E8C652585D28

  B~2,1~       62B21CF0AEE0649FA67B7D0EA6551C1CD194CA77501E0FCF8C85867B9CF679C18BCF7939E10F8550661848A4E0A9E9EDB7DAB9EDABA18C168C8E28AACDDEAB1E

  B~2,2~       64B71F486AD57125660C4512247B229F0017BA649C6C11148FB00B70808286F1A9790748D296A593FA4FD2C6D7AAF7750F0C71B31AEE5B400C7F5D73AAF00710

  B~3,1~       681A8E51420BD8294ECE13E491D618083FFBBA830DB5FAF330209877D801F92B5E07117C57E75F6F0D873B3E520F21EAFD78C1612C6228111A369D5790F5929A

  B~3,2~       04DF1DD77F1C20C1FB570D7DD7A1219EAECEA4B2877282651B0FFE713DF338A63263BC0E324A87E2DC1AD64C9F10AAA585ED6905946EE167A73CF04AD2AF9218

  B~4,1~       35951FEE6F20C902296C9488003345E6C5526C5519230454C556B8A04FC0DC642D682D94B4594B5197037DF15B5817B26F16D0A3302C09383412822F6D2B234E

  B~4,2~       7681CF7F278380E28F1262B22F40BF3405BFB92311A8A34D084C086464777431DBFDDD2E82A2E6742BAD6533B51B2BDEE0377E9F6E63DCA0B0F1DF97E73D5CD8

  B~5,1~       188157AE41830744BAE0ADA6295E08B79A44081E111F69BBE7831D07BEEBF76232E065F752D4F218D39B6C5BF20AE5B8FF172A7F1F680E6BF5AAC3C4343736C2

  B~5,2~       5D80A6007C175B5C0DD88A442440E2C29C6A136BBCE0D95A58A83B48CA0E7474E9476C92E33D164BFF943A61CE1031DFF441B0B175209B498394F4794644392E

  B~6,1~       60CD1F1C282A1612657E8C7C1420332CA245C0756F78744C807966C3E1326438878BD2CCC83388415A612705AB192B3512EEF0D95248F7B73E5B0F412BF76DB4

  B~6,2~       434B697B98C9F3E48502C8DBD891D0A0386996146DEBEF11D4B833033E05EDC28F808F25E8F314135E6675B7608B66F7FF3392308242930025DDC4BB65CD7B6E

  B~7,1~       766855125CFDC804DAF8DBE3660E8686420230ED4E049DF11D82E357C54FE256EA01F5681D95544C7A1E32B7C30A8E6CF5D0869E754FFDE6AEFA6D7BE8F1B148

  B~7,2~       222975D325A487FE560A6D146311578D9C5501D28BC0A1FB48C9BDA173E869133A3AA9506C42AE9F466E85611FC5F8F74E439638D66D2F00C682987A96D8887C

  B~8,1~       14B5F98E8D55FC8E9B4EE453C6963E052147A857AC1E08675D99A308E7269FAC5600D7B155DE8CB1BAC786F45B46B523073692DE745FDF10724DDA38FD093B1C

  B~8,2~       1B71AFFB8117BCF8B5D002A99FEEA49503C0359B056963FE5271140E626F6F8FCE9F29B37047F9CA89EBCE760405C6277F329065DF21AB3B779AB3E8C8955400

  B~9,1~       0008B4E899E5F7E692BDCE69CE3FAD997183CFAEB2785D0C3D9CAE510316D4BD65A2A06CBA7F4E4C4A80839ACA81012343648EEA8DBBA2464A68E115AB3F4034

  B~9,2~       5B7FE6808A10EA42FEF0ED9B41920F82023085C106FBBC1F56B567A14257021BC5FDA60CBA05B08FAD6DC3B0410295884C7CCDE0E56347D649DE6DDCEEB0C95E

  B~10,1~      5E9B2B33EF82D0E64AA2226D6A0ADCD179D5932EE1CF401B336449D0FF775754CA56650716E61A43F963D59865C7F017F53830514306649822CAA72C152F6EB2

  B~10,2~      2CD8140C8A37DE0D0261259F63AA2A420A8F81FECB661DBA5C62DF6C817B4A61D2BC1F068A50DFD0EA8FE1BD387601062E2276A4987A19A70B460C54F215E184

  B~11,1~      06F1FF249192F2EAF063488E267EEE994E7760995C4FA6FFA0E4241825A7F5B65C74FB16AC4C891BC008D33AD4FF97523EE5BD14126916E0502FF2F8E4A07FC2

  B~11,2~      65287840D00243278F41CE1156D1868F24E02F91D3A1886ACE906CE741662B40B4EFDFB90F76C1ADD884D920AFA8B3427EEB84A759FA02E00635743F50B942F0

  B~12,1~      4109DA2A24E41B1F375645229981D4B7E88C36A12DAB64E91C764CC43CCEC188EC8C5855C8FF488BB91003602BEF43DBEC4A621048906A2CDC5DBD4103431DB8

  B~12,2~      2185E3BC7076BA51AAD6B199C8C60BCD70E8245B874927136E6D8DD527DF0693DC10A1C8E51B5BE93FF7538FA138B335738F4315361ABF8C73BF40593AE22BE4

  B~13,1~      228845775A262505B47288E065B23B4A6D78AFBDDB2356B392C692EF56A35AB4AA27767DE72F058C6484457C95A8CCDD0EF225ABA56B7657B7F0E947DC17F972

  B~13,2~      2630C6F79878E50CF5ABD353A6ED80BEACC7169179EA57435E44411BC7D566136DFA983019F3443DE8E4C60940BC4E31DCEAD514D755AF95A622585D69572692

  B~14,1~      7273E8342918E097B1C1F5FEF32A150AEF5E11184782B5BD5A1D8071E94578B0AC722D7BF49E8C78D391294371FFBA7B88FABF8CC03A62B940CE60D669DFB7B6

  B~14,2~      087EA12042793307045B283D7305E93D8F74725034E77D25D3FF043ADC5F8B5B186DB70A968A816835EFB575952EAE7EA4E76DF0D5F097590E1A2A978025573E
  ------------ ----------------------------------------------------------------------------------------------------------------------------------

Note that the numbers in the second column represent the hexadecimal
representation of the first row of each circulant. Since there are only
511 possible positions, the leftmost bit is padded with a zero to allow
a 128 digit hexadecimal number. Table 2 cannot be as efficiently
described as table 1 due to the fact that the generator circulants do
not have a low density of 1's.

#  Appendix B -- Complexity (informative)

The complexity of LDPC codes has been an area of research and
discussion. For an FPGA or application specific integrated circuit
(ASIC) implementation, the encoder's complexity are dominated by two
factors: 1. the total number of required logic gates and 2. the routing
complexity. For the code presented in this document, the quasi-cylic
property allows for the use of shift registers whose required number of
logic gates is proportional to n-k \[8\] or 8176-7156= 1020
(unshortened). In regards to the routing complexity, there is currently
no way to predict this figure and would depend on a number of factors
such as the choice of the FPGA or ASIC, routing algorithm and the layout
of the device.

The decoder's complexity is larger than the encoder's and even more
difficult predict. The primary complexity factors (the total number of
required logic gates and the routing complexity) are a function of the
choice of Belief Propagation (BP) decoding algorithm (there are many)
\[4, 6, 7\] as well as the architectural decisions (i.e. parallel or
serial processing, number of bits of finite precision, fixed number of
iterations or stopping rule, use of look up tables, etc.)  These choices
also determine the decoder's bit error rate (BER) performance.

For the development of the baselined (8176, 7156) code, an FPGA
implementation was used to confirm the software simulations. A Xilinx
8000 Virtex-2 FPGA was used for the test. The device contained both the
encoder and decoder. The decoder algorithm was a Scaled Min-Sum parallel
BP decoder (SMSPD) described in \[6\]. The encoder algorithm was a shift
register based encoder described in \[8\]. An architectural evaluation
was performed prior to implementation to produce a quasi-optimal
implementation based on routing, logic requirements and BER performance.
 

The FPGA had the following statistics: 1. encoder used 2,535 logic
slices out of 46,592 available or 5.4% and 4 memory blocks out of 168
available or 2.4%; 2. decoder used 21,803 logic slices out of 46,592 or
46.8% and 137 memory blocks out of 168 or 81.5%. The number of logic
slices is an aggregate measure of the number of logic gates required and
the routing complexity while the memory blocks figure is the number of
dedicated FPGA memory blocks used. It is clear from these statistics
that the encoder is of much lower complexity than the decoder using only
5.4% of the logic slices resources while the decoder requires 46%.

Appendix C summarizes the test results.

# Appendix C -- FPGA Test Results (informative)

![](media/image7.png){width="6.495833333333334in"
height="4.211805555555555in"}

[]{#__RefHeading___Toc132094888 .anchor}Figure 9. Bit Error Rate Test
Results

Figure 9 shows the BER and Figure 10 shows the Block Error Rate (BLER)
test results for 50 and 10 maximum iterations from an FPGA
implementation of the baselined (8176, 7156) code. Note that for both
cases the difference between simulations and hardware tests was 0.1 dB
or less.

The encoder data rate was limited to 2 x system clock while the decoder
operated at 14 x system clock / number of iterations. For testing, the
system clock was set to 100 MHz, so for 10 iterations, the decoder
operated at 140 Mbps. Although, the shortened (8160, 7136) was not
tested, it is reasonable to say that the baselined (8176, 7156) code and
the shortened (8160, 7136) standard code will have similar results.

![](media/image8.png){width="6.495833333333334in"
height="4.211805555555555in"}

[]{#__RefHeading___Toc132094889 .anchor}Figure 10. Block Error Rate Test
Results