The LDPC encode is performed using a parity check matrix. The encoder supports matrices with lower triangular parity portion where the diagonal has a circulant weight of 1. It also supports a set of constrained matrices which have a double diagonal as employed by WiFi codes ( IEEE Standard for Information technology - Local and Metropolitan area Network Standards (IEEE Std 802.11)), and matrices that are a mix of double diagonal parity followed by a single diagonal as adopted by 5G wireless ( 3rd Generation Partnership Project; Technical Specification Group Radio Access Network; NR; Multiplexing and channel coding (Release 15) (3GPP Std TS 38.212 V15.0.0)).
Examples of supported matrices are shown in the following figures. The base matrix elements in dark gray contain single circulants and have zero rotation. The patterned region of the matrix can contain multiple circulants in each sub-matrix and arbitrary rotation values.
A lower triangular matrix, as shown in the first figure, has a first layer containing a single circulant in the first parity column, with each new layer adding only one new circulant to the parity part of the matrix in the adjacent column. Additional circulants can be included in both the information and parity parts of the layer, but must be to the left of the new parity circulant. For such a matrix, it is possible to calculate parity by processing the layers from first layer to last, solving the parity check equation for the single unknown parity column.
When the matrix is double diagonal, as shown in the second figure, the first layer contains two parity circulants in the first two parity columns, and the following layers contain another two parity circulants offset to the right by 1. For such a matrix, there are two unknown parity columns in the first layer, and a direct solution is not possible. However, in many cases it is possible to transform the double diagonal matrix into a single diagonal matrix by adding rows to eliminate additional parity columns. For example, adding the last row of the second figure to the second last row results in the cancellation of the unwanted right-most circulant in the second-last row. Then, this resulting second-last row can be added to the third-last row, to cancel the unwanted right-most circulant, and likewise this process repeated up the rows, to finally obtain the matrix of the first figure. This matrix is then suitable for encode. The main drawback of this method is that it can lead to additional operations in the information portion and under the triangular part of the parity portion, when row combinations have different rotations and so do not cancel.
While the above method is more generally applicable, for a range of double diagonal matrices it is possible to implement a matrix with fewer operations. This exploits the property of the matrix that the sum of all the layers in the parity check matrix gives a check equation containing only the first parity column. That is when all the circulants in each column of the parity part of the check matrix are summed, then that sum is 0 for all but the first row where it is a single circulant. This new check equation can be used to solve for the first parity bit, and the existing check equations (layers of the parity check matrix) providing solutions for the remaining parity bits.
For example, the third figure shows a portion of the 5G wireless graph 1 parity check matrix. Only the parity portion is shown in detail. In particular, the circulant rotation is shown as a number in the sub-matrix. The first four layers can be summed to provide an equation for the first parity bit. That is, the sum of the parity column consists of the modulo 2 addition of three circulants with rotation 1,0 and 1. The two circulants with rotation 1 cancel leaving a circulant with rotation 0. The other columns contain two circulants with rotation 0 and, likewise, they cancel, leaving only the circulant in first parity column.
The third figure also shows a mix of double diagonal and diagonal matrices. When the first parity column has been derived, the remaining parity can be calculated as each new layer is only adding one new column of parity.
Double diagonal matrices, with the property described, are supported directly by the Vivado® IDE. A further optimization is applied in the solution implemented that reuses layer products, and as a consequence the additional operations over-and-above that of the parity check matrix are relatively small.