Login| Sign Up| Help| Contact|

Patent Searching and Data


Title:
DETERMINATION OF A QUASI-CYCLIC LOW-DENSITY PARITY-CHECK, QC-LDPC, CODE FOR CHANNEL CODING IN DIGITAL COMMUNICATION SYSTEMS
Document Type and Number:
WIPO Patent Application WO/2017/105270
Kind Code:
A1
Abstract:
Provided is an apparatus configured to choose shift values of a multitude of circulants for determining a quasi-cyclic low-density parity-check matrix, H, for channel coding in network systems, wherein each circulant links variable nodes and check nodes of corresponding node groups consisting of a plurality of variable nodes or check nodes and wherein each shift value corresponds to an entry of a shift matrix. The apparatus is configured to choose the shift values in a row-by-row order of the shift matrix and values corresponding to entries in a row of the shift matrix are chosen in an order that is at least in part based on a measure of a number of cycles in which check nodes and variable nodes of node groups corresponding to the entries, participate. Accordingly, the selection of shift values in a row may start with the shift value whose corresponding variable nodes are involved in the most cycles. Moreover, the shift value may be selected from the set of possible shift values based on enumerating the Trapping Sets, TSs, involved using the Approximate Cycle Extrinsic, ACE, Message Degree spectrum.

Inventors:
USATYUK VASILY STANISLAVOVICH (CN)
GAEV VLADIMIR ANATOLYEVICH (CN)
SHATILOV SERGEY VALERYEVICH (CN)
KHODUNIN ALEXANDER VIKTOROVICH (CN)
Application Number:
PCT/RU2015/000886
Publication Date:
June 22, 2017
Filing Date:
December 15, 2015
Export Citation:
Click for automatic bibliography generation   Help
Assignee:
HUAWEI TECH CO LTD (CN)
International Classes:
H03M13/03; H03M13/11
Foreign References:
US20100257425A12010-10-07
Other References:
TAO TIAN ET AL: "Construction of irregular LDPC codes with low error floors", PROC., IEEE INTERNATIONAL CONFERENCE ON COMMUNICATIONS, ICC 2003, ANCHORAGE, ALASKA, USA, vol. 5, 11 May 2003 (2003-05-11) - 15 May 2003 (2003-05-15), pages 3125 - 3129, XP010643022, ISBN: 978-0-7803-7802-5, DOI: 10.1109/ICC.2003.1203996
VUKOBRATOVIC D ET AL: "Generalized ACE Constrained Progressive Edge-Growth LDPC Code Design", IEEE COMMUNICATIONS LETTERS, IEEE SERVICE CENTER, PISCATAWAY, NJ, US, vol. 10, no. 1, 1 January 2008 (2008-01-01), pages 32 - 34, XP011224659, ISSN: 1089-7798
USATYUK; VASILY: "Some problems of Graph Based Codes for Belief Propagation decoding Quasi-cyclic Low Density Parity-check code (QC-LDPC)", 24 November 2015 (2015-11-24), XP055302971, Retrieved from the Internet [retrieved on 20160915]
FOSSORIER: "Quasi-cyclic low-density parity-check codes from circulant permutation matrices", IEEE TRANS. INF. THEORY, vol. 50, no. 8, 2004, pages 1788 - 1793, XP011115246, DOI: doi:10.1109/TIT.2004.831841
TANNER ET AL.: "A class of group structured LDPC codes", PROC. ICSTA 2001, AMBLESIDE, ENGLAND, 2001
WANG ET AL.: "Hierarchical and High-Girth QC LDPC Codes", IEEE TRANSACTIONS ON INFORMATION THEORY, vol. 59, no. 7, July 2013 (2013-07-01), pages 4553,4583, XP011514460, DOI: doi:10.1109/TIT.2013.2253512
Attorney, Agent or Firm:
LAW FIRM "GORODISSKY & PARTNERS" LTD et al. (RU)
Download PDF:
Claims:
CLAIMS

1. An apparatus configured to choose shift values of a multitude of circulants for determining a quasi-cyclic low-density parity-check matrix for channel coding in digital communication systems, wherein each circulant links variable nodes and check nodes of corresponding node groups consisting of a plurality of variable nodes and check nodes, respectively, and wherein each shift value corresponds to an entry of a shift matrix,

wherein the apparatus is further configured to choose the shift values in a row- by-row order of the shift matrix; and

wherein values corresponding to entries in a row of the shift matrix are chosen in an order that is at least in part based on a measure of a number of cycles in which check nodes and variable nodes of node groups corresponding to the entries, participate.

2. The apparatus of claim 1 , wherein a mask matrix defines entries of the shift matrix for which no corresponding shift values are to be chosen.

3. The apparatus of claim 1 or 2, wherein the apparatus is further configured to choose shift values that correspond to entries in a first row of the shift matrix for which values are chosen, randomly.

4. The apparatus of any one of claims 1 to 3, wherein the apparatus is further configured to choose a shift value corresponding to a first entry in a row of the shift matrix, randomly.

5. The apparatus of any one of claims 1 to 4, wherein the measure defines a cycle density and wherein the apparatus is configured to choose values corresponding to entries in a row of the shift matrix in order of decreasing cycle density of the corresponding node groups, given the already chosen values.

6. The apparatus of any one of claims 1 to 5, wherein the apparatus is further configured to select a shift value from a plurality of possible shift values based on a measure of connectivity of cycles in a Tanner graph representation of a quasi- cyclic low-density parity-check matrix determined from the chosen shift values of the multitude of circulants. 15

7. The apparatus of claim 6, wherein the plurality of possible shift values are based on a predetermined requirement regarding a girth of the quasi-cyclic low- density parity-check matrix.

8. The apparatus of claim 6 or 7, wherein the measure of connectivity is an Approximate Cycle Extrinsic Message Degree, ACE, spectrum.

9. The apparatus of any one of claims 1 to 8, wherein the apparatus is further configured to:

perform multiple attempts to choose a set of shift values for the quasi-cyclic low-density parity-check matrix;

store the set of shift values for successful attempts; and

choose one of the sets based on a predetermined criterion.

10. The apparatus of claim 9, wherein the apparatus is further configured to abort an attempt to choose a set of shift values for a quasi-cyclic low-density parity- check matrix, if all shift values which can be chosen for an entry of the shift matrix lead to quasi-cyclic low-density parity-check matrices which violate a predetermined requirement.

1 1. The apparatus of claim 10, wherein the predetermined requirement is a girth of the quasi-cyclic low-density parity-check matrix.

12. The apparatus of any one of claims 9 to 1 1, wherein the apparatus is further configured to:

determine a quasi-cyclic low-density parity-check matrix from each set of a multitude of stored sets of shift values.

13. The apparatus of claim 12, wherein the apparatus is further configured to:

simulate a performance of each determined quasi-cyclic low-density parity- check matrix,

wherein the multitude of stored sets is selected from all stored sets based on Approximate Cycle Extrinsic Message Degree, ACE, spectrum as Trapping Set, TS, enumerator.

14. A decoder comprising the apparatus of claim 13, wherein the decoder is configured to: select a quasi-cyclic low-density parity-check matrix from the determined quasi-cyclic low-density parity-check matrices based on the simulated performance of the determined quasi-cyclic low-density parity-check matrices;

signal information regarding the selected quasi-cyclic low-density parity-check matrix to an encoder; and

decode binary data using the selected quasi-cyclic low-density parity-check matrix.

15. An encoder comprising the apparatus of claim 13, wherein the encoder is configured to:

select a quasi-cyclic low-density parity-check matrix from the determined quasi-cyclic low-density parity-check matrices based on the simulated performance of the determined quasi-cyclic low-density parity-check matrices;

signal information regarding the selected quasi-cyclic low-density parity-check matrix to a decoder;

calculate a generator matrix from the selected quasi-cyclic low-density parity- check matrix; and

encode binary data using the calculated generator matrix.

Description:
DETERMINATION OF A QUASI-CYCLIC LOW-DENSITY PARITY-CHECK, QC-LDPC, CODE FOR CHANNEL CODING IN

DIGITAL COMMUNICATION SYSTEMS

FIELD

The present disclosure relates to digital communications. In particular, the present invention relates to Quasi-Cyclic Low-Density Parity-Check (QC-LDPC) codes for channel coding in digital communication systems.

BACKGROUND

Fig. 1 shows a block diagram illustrating a digital communications system 10 including an encoder apparatus 12 and a decoder apparatus 14.

The input of the encoder apparatus 12 is an information sequence B 1 of k bits to which a redundancy sequence of r bits is added in an encoding operation, thereby producing an encoded sequence B2 of n bits. A modulator 16 transforms the encoded sequence B2 into a modulated signal vector CH_IN which is in turn transmitted through a channel 18. Since the channel 18 is usually subject to noisy disturbance, the channel output CH OUT may differ from the channel input CH IN.

At the receiving end, the channel output vector CH_OUT is processed by the demodulator 20 which produces some likelihood ratio. The decoder apparatus 14 uses the redundancy in the received sequence B3 in a decoding operation to correct the error in the information sequence of the received sequence B3 and produces a decoded signal B4 which is an information signal estimate.

The encoding operation and the decoding operation are governed by the use of LDPC codes. In the general formulation of channel coding, LDPC codes employ a generator matrix G for the encoding operation in the encoder apparatus 12 and a binary parity-check matrix H for the decoding operation in the decoder apparatus 14.

For a LDPC code with information sequence of k bits, a code word of n bits and redundancy (parity) sequence of r=(n-k) bits, the generator matrix G has focrc dimensions, and the binary parity-check matrix H has rxn=(n-k)xn dimensions. The binary parity-check matrix H rxn and the generator matrix Gkxn enjoy the orthogonal property, which states that for any matrix kxn with k linearly independent rows there exists a matrix with r=(n-k) linearly independent rows such that any row of is orthogonal to the rows of H rxn such that the following equation is satisfied: (1)

The encoding operation is performed by means of the multiplication between the information sequence B\ Xxk and the code generator matrix G fan . The result, of such multiplication, is the encoded output sequence B2 Xxn as follows:

At the receiving side, due to the orthogonal property between matrixes G t and H rxn , the following equation should be satisfied:

(3)

where Β η Ί χΧ is the decoded received sequence which comprises the information signal estimate B4 xk . If the above equation is verified, the information signal estimate B4 Xxk is correct.

Once the binary parity-check matrix H rxn is built, it is possible to obtain the code generator matrix <_? fan and vice versa. Accordingly, any process of determining a binary parity-check matrix H rxn may be mapped to an equivalent process of obtaining a code generator matrix so that any process disclosed throughout the description and claims in relation to determining a binary parity-check matrix H rxn shall be understood as encompassing the equivalent process of obtaining a code generator matrix G fan and vice versa.

A particular form of the binary parity-check matrix H rxn is a regular QC-LDPC matrix reg H; xn build from submatrices l{p jj ) which are circulant permutation matrices, shortly "circulants", which may, for example, be obtained from cyclically right-shiftin an p x p identity matrix l(0) by p , positions:

rxn

(4)

I(PJ-LO ) l(pj-u ) ··· Pj-n-i ) with p = n l L. Thus, the regular QC-LDPC matrix Kg H" xn may be defined by a shift matrix B which satisfies:

(5)

Moreover, an irregular QC-LDPC matrix ' mg H^ n may be obtained by H n = reg H^ Θ M where <8> is the ronecker product and

m 0,0 m 0,1 m 0,1-1

m 1 ,0 m U m 1,1-1

M =

(6)

m ,/ - l ,0

denotes a mask matrix. Thus, for using a QC-LDPC code in the encoder apparatus 12 and the decoder apparatus 14, the encoder apparatus 12 and the decoder apparatus 14 may be provided with shift values, i.e. values corresponding to the entries of the shift matrix B. For instance, an apparatus configured to choose shift values for determining a QC-LDPC matrix H;^ may be integrated in (or connected to) the encoder apparatus 12 and/or the decoder apparatus 14. Moreover, the encoder apparatus 12 and the decoder apparatus 14 may also be provided with a corresponding mask matrix M to generate an irregular QC-LDPC matrix ' rres H n .

A QC-LDPC matrix can be described by its equivalent bipartite graph ("Tanner graph"), wherein each edge of the Tanner graph connects one variable node of a plurality of variable nodes (which from the first set of the bipartite graph) to one check node of a plurality of check nodes (which form the second set of the bipartite graph). For example, a QC-LDPC matrix H;^ n of n columns and r rows can be represented by its equivalent bipartite graph with r check nodes and n variable nodes which has edges between the check nodes and the variable nodes if there are corresponding Is in the QC-LDPC matrix H^ . Thus, the variable nodes represent code-word bits and the check nodes represent parity-check equations.

A cycle in the Tanner graph refers to a finite set of connected edges, wherein the set starts and ends at the same node and satisfies the condition that no node (except the initial and final node) appears more than once. The length of the cycle is then the number of edges of the set. The girth of the Tanner graph is the length of the shortest cycle(s) in the graph. In this regard, it is to note that short cycles in the Tanner graphs of QC-LDPC codes may prevent decoding algorithms from converging. Furthermore, short cycles may degrade the performance of QC-LDPC decoders, because they affect the independence of the extrinsic information exchanged in the iterative decoding. Accordingly, shift values are to be chosen that achieve high girth of the Tanner graph representation of the respective QC-LDPC matrix.

Moreover, a QC-LDPC code may contain Trapping Sets (TSs). More particularly, a (a,b) TS contains b check nodes which have an odd number of connections to a variable nodes. Accordingly, when the a variable nodes are wrong, only the b check nodes will be unsatisfied which may lead to a high error floor, as a belief propagation algorithm employed in the decoder apparatus 14 may be "trapped" in a false minimum.

SUMMARY

It is thus the object of the present invention to provide for an efficient technique of choosing shift values to generate QC-LDPC codes with favorable properties, such as, for example, high girth, fast convergence properties, and low error floor.

According to a first aspect of the present invention, there is provided an apparatus configured to choose shift values of a multitude of circulants for determining a QC-LDPC matrix for channel coding in digital communication systems, wherein each circulant links variable nodes and check nodes of corresponding node groups consisting of a plurality of variable nodes and check nodes, respectively, and wherein each shift value corresponds to an entry of a shift matrix, wherein the apparatus is further configured to choose the shift values in a row-by-row order of the shift matrix and wherein values corresponding to entries in a row of the shift matrix are chosen in an order that is at least in part based on a measure of a number of cycles in which check nodes and variable nodes of node groups corresponding to the entries, participate.

In this regard, the term "circulant" as used throughout the description and claims refers to a matrix, e.g. the identity matrix, which is cyclically modified by cyclically shifting the rows of the matrix by a predetermined number of places. In particular, the shift value of each circulant may define the number of times by which rows of the identity matrix are cyclically (right-)shifted by the predetermined number of places, wherein the predetermined number of places may be one. By choosing the shift-values in a row-by-row order, it is possible to create a stronger connected row- code which is advantageous for layered belief-propagation decoding.

In a first possible implementation form of the apparatus according to the first aspect, a mask matrix defines entries of the shift matrix for which no corresponding shift values are to be chosen.

Thus, instead of modifying a regular QC-LDPC matrix reg H^„ by multiplication with a mask matrix M, an irregular QC-LDPC matrix can be directly established by labelling the mask matrix M, e.g., by choosing shift values only for non-zero entries of the mask matrix M. This allows for increasing the girth and facilitates encoding while reducing complexity in establishing an irregular QC-LDPC matrix im *H .

In a second possible implementation form of the apparatus according to the first aspect as such or according to the first implementation form of the first aspect, the apparatus is further configured to choose shift values that correspond to entries in a first row of the shift matrix for which values are chosen, randomly.

As entries in the first row for which values are chosen, i.e., the first row to be labelled, cannot produce cycles in the corresponding Tanner graph, they can be chosen randomly which reduces the overall computational effort. In this regard, it is to note that the term "first row" as used throughout the description and claims does not necessarily refer to the upmost row "in a matrix sense" but to the row for which shift values are chosen while all other rows of the shift matrix are still empty.

In a third possible implementation form of the apparatus according to the first aspect as such or according to the first or second implementation form of the first aspect, the apparatus is further configured to choose a shift value corresponding to a first entry in a row of the shift matrix, randomly.

As the first entry in a row cannot produce cycles in the corresponding Tanner graph representation, it can be chosen randomly which reduces the overall computational effort. In this regard, it is to note that the term "first entry" as used throughout the description and claims does not necessarily refer to the leftmost entry in a row "in a matrix sense" but to the entry for which a shift value is chosen while all other entries in the row are still empty.

In a fourth possible implementation form of the apparatus according to the first aspect as such or according to any of the preceding implementation forms of the first aspect, the measure defines a cycle density and the apparatus is configured to choose values corresponding to entries in a row of the shift matrix in order of decreasing cycle density of the corresponding node groups, given the already chosen values.

Filling the entries of the shift matrix in an order of decreasing cycle density of the corresponding Tanner graph representation gives greater freedom for those node groups which do already participate in many cycles and for which the generation of further cycles is more probable. Thus, density of all parts of the Tanner graph becomes substantially equal.

In a fifth possible implementation form of the apparatus according to the first aspect as such or according to any of the preceding implementation forms of the first aspect, the apparatus is further configured to select a shift value from a plurality of possible shift values based on a measure of connectivity of cycles in a Tanner graph representation of a QC-LDPC matrix determined from the chosen shift values of the multitude of circulants.

Selecting a shift value from a plurality of possible shift values based on a measure of connectivity of cycles allows reducing the generation of trapping sets. In this regard, it is noted that the Tanner graph representation of a QC-LDPC matrix determined from the chosen shift values of the multitude of circulants may be determined on the assumption that all circulants for which no shift vales have been yet chosen are zero matrices.

In a sixth possible implementation form of the apparatus according to the fifth implementation form of the first aspect, the plurality of possible shift values are based on a predetermined requirement regarding a girth of the QC-LDPC matrix.

Thus, shift values that can be chosen for entries of the shift matrix may be limited to those shift values which allow for a predetermined girth of the corresponding tanner graph representation. This assures that the girth of the QC-LDPC code meets predefined requirements. In a seventh possible implementation form of the apparatus according to the fifth or sixth implementation forms of the first aspect, the measure of connectivity is an Approximate Cycle Extrinsic Message Degree, ACE, spectrum.

This allows improving the connectivity of cycles and reducing the influence of trapping sets by using the ACE spectrum as trapping set enumerator, resulting in an improved error-floor.

In an eighth possible implementation form of the apparatus according to the first aspect as such or according to any of the preceding implementation forms of the first aspect, the apparatus is further configured to perform multiple attempts to choose a set of shift values for a QC-LDPC matrix, store the set of shift values for successful attempts, and choose one of the sets based on a predetermined criterion.

This allows to select a QC-LDPC matrix with particular beneficial properties from the set of generated QC-LDPC matrices.

In a ninth possible implementation form of the apparatus according to the eighth implementation form of the first aspect, the apparatus is further configured to abort an attempt to choose a set of shift values for a QC-LDPC matrix, if all shift values which can be chosen for an entry of the shift matrix lead to QC-LDPC matrices which violate a predetermined requirement.

Thus, computational complexity can be reduced as QC-LDPC matrices which violate a predetermined requirement are dropped at an early stage.

In a tenth possible implementation form of the apparatus according to the ninth implementation form of the first aspect, the predetermined requirement is a girth of the QC-LDPC matrix.

Thus, it can be ensured that the girth of the produced QC-LDPC matrix meets a predetermined requirement, for example that the girth is larger than a threshold value.

In an eleventh possible implementation form of the apparatus according to one of the eighth to tenth implementation forms of the first aspect, the apparatus is further configured to determine a QC-LDPC matrix from each set of a multitude of stored sets of shift values.

Thus, the apparatus is configured to generate a plurality of QC-LDPC matrices with different properties from which to choose. Accordingly, a QC-LDPC matrix with particular beneficial properties can be selected. In a twelfth possible implementation form of the apparatus according to the eleventh implementation form of the first aspect, the apparatus is further configured to simulate a performance of each determined QC-LDPC matrix, wherein the multitude of stored sets is selected from all stored sets based on Approximate Cycle Extrinsic Message Degree, ACE, spectrum as Trapping Set, TS, enumerator.

This allows for taking into account the connectivity of cycles and TSs which results in a low error-floor.

According to a second aspect of the present invention, there is provided a decoder comprising the apparatus according to the twelfth implementation form. Furthermore, the decoder 14 is configured to select a QC-LDPC matrix from the determined QC-LDPC matrices based on the simulated performance of the determined QC-LDPC matrices, signal information regarding the selected QC-LDPC matrix to an encoder, and decode binary data using the selected QC-LDPC matrix.

Accordingly, a QC-LDPC matrix showing a desired performance as determined by simulation can be selected and used for encoding the information sequence Bl at the encoder and decoding the received sequence B3 at the decoder. Moreover, the decoder apparatus may be connected to the decoder and the decoder may receive an indication of the QC-LDPC matrix.

According to a second aspect of the present invention, there is provided an encoder comprising the apparatus according to the twelfth implementation form. Furthermore, the encoder is configured to select a QC-LDPC matrix from the determined QC-LDPC matrices based on the simulated performance of the determined QC-LDPC matrices, signal information regarding the selected QC-LDPC matrix to a decoder, calculate a generator matrix from the selected QC-LDPC matrix, and encode binary data using the calculated generator matrix.

BRIEF DESCRIPTION OF THE DRAWINGS

Fig. 1 is a schematic illustration of a digital communication system 10 in which the determined QC-LDPC code may be employed;

Fig. 2 is a flow chart of a process of choosing shift values of a multitude of circulants for determining the QC-LDPC code for channel coding in the digital communication system 10; Fig. 3 illustrates ACE spectra corresponding to different shift values in a second row of a shift matrix; and

Fig. 4 illustrates ACE spectra corresponding to different shift values in a third row of a shift matrix.

DETAILED DESCRIPTION

As shown in Fig. 2, the process 22 for determining the QC-LDPC code may start at 24 with choosing shift values in a row-by-row order of the shift matrix. For example, the shift matrix may have a size 4x10 and the circulant may be a 100x100 identity matrix.

The shift values of the first row of the shift matrix may be generated randomly, because a one-layer (row) QC-LDPC with circulant permutation matrix of weight one represents a tree graph without any cycle. After random labeling, the shift matrix may look like:

Because one layer QC-LDPC matrix doesn't have any cycle the second layer may be labelled starting from any circulant. For example, the 9 th circulant may be labelled with 13 (as shift value) so that the shift matrix looks like:

As indicated at 26, the process may continue by choosing entries in the second row of the shift matrix in an order that is at least in part based on a measure of a number of cycles in which check nodes and variable nodes of node groups corresponding to the entries, participate. The shift values may be selected from a plurality of possible shift values based on a measure of connectivity of cycles in the corresponding Tanner graph representation. For example, the possible shift values, i.e. the shift values from which may be chosen, may all satisfy a pre-defined girth condition regarding the girth of the corresponding Tanner graph, wherein the girth of the corresponding QC-LDPC code may be calculated using the equation from Fossorier: "Quasi-cyclic low-density parity- check codes from circulant permutation matrices ' ", IEEE Trans. Inf. Theory, vol. 50, no. 8, pp.1788-1793, 2004.

In addition, values corresponding to entries in the second row of the shift matrix may be chosen in order of decreasing cycle density of the corresponding node groups, given the already chosen values. Accordingly, the selection of shift values may start with the shift value whose corresponding variable nodes are involved in the most cycles. Moreover, the shift value may be selected from the possible shift values based on enumerating the TSs involved.

For instance, the ACE spectrum may, if particular conditions are satisfied, be equal to the extrinsic message degree (EMD) as described in Deka et al.: "On the equivalence of the ACE and the EMD of a cycle for the ACE spectrum constrained LDPC codes ' ", 8 th International Symposium on Turbo Codes and Iterative Information Processing (ISTC), pp. 55,59, 18-22 Aug. 2014, which may be exploited for any cycle for which the ACE is equal to the EMD. More particularly, check nodes connected to the variable nodes in the cycle but not involved in the cycle will be singly connected to the cycle. The reliability of the messages coming from these check nodes can be increased relative to messages coming from the check nodes involved in the cycle in order to enhance the benefit of the messages coming from the rest of the Tanner graph.

In this way, better connectivity can be ensured for the isolated small cycles and the performance of the iterative decoders may be improved which may result in a gain in the waterfall region. Moreover, TS enumerators can be obtained by the ACE spectrum, because the cycle of length / contains 111 variable nodes. For the ACE value η, the subgraph induced by the 111 virtual nodes constrains exactly η number of odd- degree check nodess. Hence, the cycle can be treated as TS (ΙΙ ,η) .

However, in the present example, the next shift values may be chosen without considering the ACE spectrum as the cycle length can only be a multiple of four (4, 8, 12). Cycle 8 1.5 0.75 0.75 1.5 1.75 2 1 1 0.5 1.25

6 4 31 34 59 4 25 6 12 7 24

6 -1 -1 -1 -1 -1 -1 1 78 13 26

0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1

0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1

After that, a shift for the densest variable node in the second row value may be chosen. In this regard, Fig. 3 shows ACE spectra of QC-LDPC codes for shift matrix entry 64 on the left side and shift matrix entry 9 on the right side, both enumerating the ACE spectrum with a maximum cycle of 12. From this comparison, the shift matrix entry 64 is chosen:

Moreover, al other shift values in the second row may be chosen analogously by comparing the respective ACE spectra:

In the following, shift values for the third row are chosen. As with choosing shift values for the second row, the first shift value is chosen randomly and may be, for example, be set to 93. For the next shift value, the ACE spectra are shown for shift matrix entry 93 on the left side and shift matrix entry 33 on the right side from which 33 is chosen as shown in the following: Cycle 8 1.5 1 1 1.5 2 2.25 1 1 0.5 1.25

6.25 4 31 34 59 4 25 6 12 7 24

6.5 33 12 91 68 80 64 1 78 13 26

0.25 -1 -1 -1 -1 33 93 -1 -1 -1 -1

0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1

This process is continued until all shift values are chosen or, if only shift values exist for an entry which violate a required condition, such as a minimal girth of the QC-LDPC code, the process 22 may be aborted.

The process 22 may be repeated a defined number of times to generate candidate matrices and additional heuristics may be used to filter the candidate matrices for candidate matrices with favorable properties. For example, parameters which measure how fast messages disperse to all nodes may be used.

More particularly, there exist [_(g - l)/4j independent iterations, with g denoting the girth of the graph. Thus, after diameter! 2 iterations, information from any variable nodes shall have reached any other variable node. In this case if diameter≥ \_g - lj / 2 all vertex shall have statistically independent information. These considerations motivate another heuristics of code on the graphs design with large girth and smallest diameter for the degrees of the vertexes as described in Tanner et al. class of group structured LDPC codes", Proc. ICSTA 2001, Ambleside, England, 2001. In particular, the goal of this sieving stage is to obtain codes with maximal girth and small graph diameter. The upper bound on the girth is determined by the length of the shortest balanced cycle of the graph, for example a Petersen graph. The graph diameter depends on the graph structure.

Another parameter is described in Wang et al., "Hierarchical and High-Girth QC LDPC Codes", IEEE Transactions on Information Theory, vol.59, no.7, pp.4553,4583, July 2013. Heretofore, the bipartite graph defined by the QC-LDPC is taken and the spectral graph (connective) property of the corresponding graph is considered by the real-value adjacency matrix:

This representation is equvalent to

because change of columns (VN) positions do not change code and Eigen value monotonically. A similar order for spectral graph sieve of parity-check matrix candidates with simplification of GPU calculation is obtained.

After diagonalizing and taking real eigenvalues: / , > μ 2 > ... > μ χ ; a QC-LDPC matrix may be chosen which achieves a QC-LDPC code having a minimum ratio of the second eigenvalue to the first eigenvalue mm— or a ration which is below a

/

predetermined threshold.

After (optionally) filtering the candidate matrices, the remaining candidate matrices may be simulated and the candidate matrix that performs best may be chosen for producing the QC-LDPC code employed in the encoder apparatus 12 and the decoder apparatus 14. In this regard, the candidate matrices may be filtered by a property which points at the quality of the code such as, for example, the weight spectrum enumerator and the TS spectrum enumerator. Moreover the candidate matrices may be filtered using Tanner spectral graph properties. After filtering some (or all) candidate matrices whose properties is above a pre-determine threshold matrix or a pre-determined number of candidate matrices may be further evaluated by measuring the code distance. Then, codes with favorable ACE Spectrum, Tanner spectral graph properties and large code distance may be simulated at a working point. For example, a EB/No of 2 dB may be used and the code exhibiting the lowest probability of error (BER, FER) may be selected from the candidates.