[Title of Invention]

METHOD FOR AMC AND AMC CONTROLLER

[Technical Field]

[0001]

This invention is related to error control coding for digital data

communications, particularly for optical and radio communications systems.

[Background Art]

[0002]

Low-density parity-check (LDPC) codes have been often used for error control codes in digital data communications including radio and optical communications networks because these codes achieve close to theoretical

Shannon limit in practice. For those communications networks, LDPC-coded data are sent from a transmitter to a receiver over noisy channels. Using LDPC codes with an appropriate code rate, potential errors caused by channel noise can be efficiently corrected by an LDPC decoder at the receiver. To achieve better performance depending on the channel quality, an adaptive modulation and coding (AMC) has been used. The AMC uses different pairs of modulation order and code rate depending on the channel quality. For example, depending on a signal-to-noise ratio (SNR) at the receiver, the transmitter changes the modulation format, e.g., from 4-ary quadrature-amplitude modulation (QAM) to 16-ary QAM, and the code rate of the LDPC codes, e.g., from 0.5 to 0.9. By adaptively choosing the modulation order and the code rate, the AMC can achieve the maximum possible data rate close to Shannon limit over all the SNR regimes.

[0003]

Typically, a degree distribution of LDPC codes determines a bit-error rate (BER) performance of the LDPC decoder. However, one optimized degree distribution of irregular LDPC code at a certain condition is not always best for other conditions even when the channel quality is constant. For example, the best code for 4QAM may be no longer the best for 16QAM. Therefore, the

conventional AMC with the rate adaptation does not resolve this problem because the AMC does not provide multiple LDPC codes having the same code rate.

[0004]

Recently, high-dimensional modulation (HDM) formats, such as

polarization-switched quadrature phase-shift keying (PS-QPSK) and set- partitioned 128QAM, have been used for reliable data transmissions, especially for coherent optical communications. Those modulation formats can provide a larger squared Euclidean distance, and the BER performance can be improved especially in uncoded networks. However, there is no obvious way to optimize LDPC codes for high-order and high-dimensional modulations. For example, one LDPC code optimized for 4-dimensional modulation format cannot be optimal for 8- dimensional modulation formats.

[0005]

Some networks use bit-interleaved coded-modulations (BICM) and its iterative demodulation (ID) variant (called BICM-ID) for high-order modulation formats. Another way includes multi-layer coding (MLC), which uses multiple LDPC codes for different significant bits in high-order modulation formats. BICM is the simplest and optimizing LDPC codes for BICM does not depend on modulation formats, while the performance depends on labeling. BICM-ID outperforms BICM, and approaches the MLC performance bound. However, BICM-ID requires a higher latency because soft-decision information needs to be fed back to a demodulator from the decoder. Although MLC performs the best in theory, it has a drawback of codeword length shortening for each layered codes. In addition, there is no good way to design LDPC codes for HDM formats. [0006]

The performance of LDPC codes can be analyzed by an extrinsic

information transfer (EXIT) chart or density evolution (DE). Those methods are also used for designing a degree distribution of irregular LDPC codes, for example, by linear programing for curve fitting. Although a good degree distribution can be designed with EXIT or DE, those methods assume infinite codeword length, infinite precision, and infinite number of iterations for decoding. Therefore, sometimes the expected performance cannot be obtained in practical use, where there exist some limitations in size of memory, bit width for precision, and maximum number of iterations.

[0007]

Accordingly, there is a need in the art for an approach in designing practical LDPC codes to support various high-order and high-dimensional modulation formats in high-speed communications networks accounting for the trade-off between performance and complexity.

[Summary of Invention]

[0008]

The problem to adapt data rates by changing modulation order and code rate in conventional adaptive modulation and coding (AMC) networks is dealt with by this invention with parity-check matrix (PCM) adaptation for finite-iteration decoders and any modulation formats. The conventional AMC uses multiple LDPC codes having different code rates, and multiple modulation formats having different modulation orders to control a total data rate depending on channel quality such as signal-to-noise ratio (SNR).

[0009]

Some important features of the invention include that the PCM design method considers any order and any dimension for modulation formats, and any iteration number for decoding and demodulation. The advantage over the conventional AMC solutions is the fact that high-performance decoding is possible for any modulation formats and any practical decoders by adapting not only the code rate but also the PCM. At the same time, the decoder can use the best code and modulation while computational complexity and power consumption can be minimized.

[0010]

The network of the invention uses multiple LDPC codes, which have different PCMs even for the same code rate, and the best LDPC code is adaptively selected to use at the transmitter depending on the modulation format and the receiver behavior as well as the channel quality. For example, when the receiver reduces the maximum number of iterations for lower-power decoding, a different LDPC code is selected even though the channel quality such as the SNR does not change.

[0011]

For another example, depending on whether or not the receiver uses iterative demodulation (ID) to improve performance of high-dimensional modulation (FfDM), a different LDPC code is selected. In addition to the conventional code rate adaptation, the network adapts PCM, whose degree distribution is predesigned for different modulations and different number of iterations by an extrinsic information transfer (EXIT) chart analysis.

[0012]

The method of the invention provides a way to adjust a degree distribution of PCM depending on different conditions. The decoder performance is improved by changing the degree distribution while the mutual information updates are tracked over iteration. The design method can consider different HDM formats, different number of iterations, different number of demodulations, different decoding algorithms, different bit widths, and different codeword lengths.

[0013]

In one embodiment, the receiver adaptively changes the PCM, which is linearly dependent on the original PCM of one LDPC code. The adaptive PCM simplifies the transmitter as this embodiment can keep using the same LDPC code (or fewer number of codes) regardless of modulation formats, decoding methods, and channel quality. This embodiment provides a way to adjust the degree distribution of original PCM by semi-random linear transformation by a modular perturbation matrix to achieve best possible decoder performance.

[0014]

In yet another embodiment, the PCM is changed over different iteration count at the decoder to accelerate convergence of decoding speed. The different PCMs, which are linearly dependent, are pre-designed by EXIT chart trajectory analysis to improve convergence speed for low-power and high-throughput decoding.

[0015]

In one embodiment, the network uses spatially coupled LDPC codes and nonbinary LDPC codes. To decode without high latency, the method of the invention provides a way to use dynamic window decoding by generating spatially coupled PCM. To solve the problem of latency of BICM-ID and codeword length shortening of MLC, the methods of the invention optimize labeling for nonbinary LDPC codes to provide a coded modulation scheme referred to as nonbinary input coded modulation (NBICM).

[Brief Description of the Drawings]

[0016]

[Fig. 1]

Fig. 1 is a block diagram of a network for transmitting digital data with adaptive modulation and coding (AMC) using principles employed by some embodiments of the invention.

[Fig. 2]

Fig. 2 is a block diagram of a prior art AMC controller.

[Fig. 3]

Fig. 3 is a block diagram of a network for transmitting digital data with enhanced AMC using high-dimensional modulation (HDM) and parity-check matrix (PCM) adaptation depending on iteration counts as well as channel quality according to some embodiments of the invention.

[Fig. 4]

Fig. 4 is a block diagram of an AMC controller using iteration-dependent PCM adaptation according to some embodiments of the invention.

[Fig- 5]

Fig. 5 is a table example of degree distributions designed for iteration- dependent PCM adaptation according to some embodiments of the invention. [Fig. 6]

Fig. 6 is a block diagram of an AMC controller using modulation-dependent PCM adaptation according to some embodiments of the invention.

[Fig. 7]

Fig. 7 is a table example of degree distributions designed for modulation- dependent PCM adaptation according to some embodiments of the invention. [Fig. 8]

Fig. 8 is a schematic of PCM design using EXIT trajectory analysis for modulation-dependent and iteration-dependent AMC networks according to some embodiments of the invention.

[Fig. 9]

Fig. 9 is a schematic of PCM design using protograph-based EXIT trajectory analysis for quasi-cyclic LDPC convolutional codes according to some embodiments of the invention.

[Fig. 10]

Fig. 10 is a schematic of PCM design for a common generator matrix to support a large number of parameter combinations according to some

embodiments of the invention.

[Description of Embodiments]

[0017]

Fig. 1 shows a network to transmit digital data from a transmitter 1 10 to a receiver 130 over communications channel 120 with an adaptive modulation and coding (AMC) controller 150 using principles employed by some embodiments of the invention. The communications channel 120 includes, e.g., fiber for optical communications, free space for visible light communications, air for radio communications, water for acoustic communications, coaxial cable for power line communications, and so on.

[0018]

At the transmitter 1 10, the digital data coming from a source 1 1 1 are encoded by an encoder 1 12 into coded words by a forward error correction (FEC) code, e.g., such as a low-density parity-check (LDPC) code. For such linear codes, the digital data s of a length N— M are multiplied arithmetically by a generator matrix G 164 of a size N-by-(N— ), which appends parity-check data p of a size M for the receiver 130 to correct potential errors. The code rate is defined by

R = 1— M/N. The coded words c are expressed as c = Gs over the Galois field or the Lie ring. The coded words are then modulated by a modulator 1 13 in a format, such as binary phase-shift keying (BPSK), 16-ary quadrature-amplitude modulation (16QAM), and so on. The modulated data are expressed as x = M [c], where M[. ] denotes a modulation format 161 to generate complex- valued signal constellations from the coded words. The modulated data x are transmitted into the channel 120 through an analog front-end 114, e.g., such as an electro-optic circuit with a laser source and a radio-frequency circuit with a transmitting antenna. The front-end 114 can include other digital/analog pre-processing, e.g., such as pre- equalization, pre-coding, filtering, etc. For example, a root-raised-cosine filter is used as a low-pass filter. The transmitter 110 uses some memory storages and at least one processer for transmitting the modulated data.

[0019]

The receiver 130 obtains noisy modulated data through the channel 120 and an analog front-end 131, e.g., such as an opto-electric circuit. The front-end 131 can include other digital/analog pre-processing, such as equalization, filtering, timing recovery, carrier phase recovery, etc. The noisy modulated data received after pre-processing at the front-end 131 are expressed as y = x + z, where z is a sequence of additive noise of variance σ ² . The noisy modulated data y are demodulated by a demodulator 132, and decoded by a decoder 133 to recover the original digital data. The demodulator 132 uses the modulation format M[. ] 162, which is identical to the one 161 used in the modulator 113 at the transmitter 110. The demodulator 132 calculates likelihoods based on the squared Euclidean distance for all the possible constellations, and provides log-likelihood ratios (LLR) based on the maximum a posteriori probability (MAP) estimation for the decoder 133. As an example, the decoder 133 employs an iterative belief propagation algorithm for message passing over a sparse graph represented by a parity-check matrix (PCM) H 163 of a size -by-N, which is an arithmetically orthogonal compliment of the generator matrix such that HG = 0 holds over the Galois field or the Lie ring. The belief propagation algorithm can correct potential errors occurred through the data communications. The decoder provides decoded data as an estimate of the original digital data sent from the data source 1 1 1. The decoded data are sent to a data sink 134. The receiver 130 uses some memory storages and at least one processer for recovering the digital data.

[0020]

The generator matrix G, the modulation format M[. ], and the PCM H are adaptively selected by the AMC controller 150. The AMC controller 150 uses some memory storages to store a set of modulation formats and FEC codes, and at least one processer. In one embodiment, the AMC controller 150 can work remotely at an external base station. In another embodiment, the AMC controller 150 is embedded at either the transmitter 110 or the receiver 130. It does not matter where it is, as long as the transmitter can use the selected modulation format and the selected generator matrix, and the receiver can use the selected modulation format and the selected parity-check matrices.

[0021]

The AMC controller 150 selects one best modulation format from a finite set of variable-order modulation formats 151, together with one best FEC code from a finite set of variable-rate FEC codes 152, depending on the channel quality, e.g., such as signal-to-noise ratio (SNR) measured by an SNR monitor 141 or bit-error counts measured by an error checker 142.

[0022]

Fig. 2 shows a non-limiting example of a block diagram of the conventional AMC controller 150. The AMC controller 150 uses a finite set of FEC codes 152, having different code rates. For example, the set 152 comprises three codes, whose code rates R are 1/2, 2/3, and 3/4. Each code has corresponding PCM ( 1/2 , H ₂ / ₃ , and / ₃ / ₄ ) and generator matrix (G _{1 /2} , G ₂ / ₃ , and G ₃ / ₄ ). The AMC controller 150 uses another finite set of modulation formats 151, having different modulation orders. For example, the set 151 comprises three modulation formats of 4QAM, 16QAM, and 64QAM, wherein all modulation formats are 2-dimensional (2D) constellations using in-phase and quadrature components.

[0023]

The AMC controller 150 uses the measured SNR value from the SNR monitor 141 to select the best pair of modulation and coding by an AMC selector 310. The AMC selector 310 uses a pre-defined selection rule table 21 1. For example, the selection rule 211 determines the modulation format and the code rate to be selected; 4QAM with 1/2-rate code is chosen when the SNR is between OdB and 6dB, 4QAM with 3/4-rate code is chosen when the SNR is between 6dB and 8.5dB, 16QAM with 1/2-rate code is chosen when the SNR is between 8.5dB and 1 1.5dB, 16QAM with 3/4-rate code is chosen when the SNR is between 1 1.5dB and 15dB, 64QAM with 2/3-rate code is chosen when the SNR is between 15dB and 18.5dB, and 64QAM with 3/4-rate code is chosen when the SNR is between 18.5dB and 21dB. By adaptively selecting the pair of modulation formats and code rates, the maximum possible data rate can be achieved under a certain bit-error rate (BER) target for a wide range of SNR regimes. The AMC selector 310 indicates the selected best PCM H 163, generator matrix G 164, and modulation format M[. ] 161 and 162 for the transmitter 1 10 and the receiver 130.

[0024]

Such a rate adaptation of the conventional AMC controller 150 works well for bit-interleaved coded modulation (BICM), in which any modulation order is treated as a unified binary-output data. However, such an adaptation of code rates has a limitation for some receivers, which employ adaptive iteration decoding and BICM iterative demodulation (BICM-ID). For example, a 1/2-rate LDPC code optimized for BPSK is no longer optimal for 16QAM with BICM-ID.

[0025]

Enhanced AMC with PCM and HDM Adaptation A schematic of the network and method according to some embodiments of the invention is shown in Fig. 3. These embodiments use an enhanced AMC controller 350 with a set of variable-PCM codes 352 in order to make full use of high-dimensional modulations (HDM) 351, a variable-iteration demodulator 332, and a variable-iteration decoder 333. The decoder 333 uses an adaptive number of iterations for belief propagation decoding. For example, the decoder uses at most 32 iterations when the BER performance needs to be improved at low SNR regimes, while the maximum number of iterations can be reduced when the receiver needs to save power consumption at high SNR regimes. In order to improve the BER performance, the decoded data can be fed back 335 to the demodulator for BICM-ID. The number of iterative demodulations is also adaptive so that the best tradeoff between the BER performance and the power consumption is maintained for various different requirements. The AMC selection rule can be based on the minimum required SNR, the maximum possible data rate, the maximum processer throughput, the minimum possible power consumption, and any combination of those metrics.

[0026]

In these embodiments of the invention, the AMC controller 350 uses not only the channel quality based on the SNR monitor 141 but also the number of iteration counts for the decoder 333 and the demodulator 332 based on an iteration monitor 343, in order to select the best pair of modulation formats and FEC codes. The AMC controller uses an enhanced finite set of modulation formats 351, wherein the modulation formats have not only various modulation orders but also various dimensions to support HDM. For example, a BPSK alternative HDM includes 4D simplex modulation, 8D modulation based on the extended Hamming code, 16D modulation based on the Nordstrom-Robinson nonlinear code, and 24D modulation based on the extended Golay code, those of which achieve a larger minimum squared Euclidean distance than BPSK, respectively, by 1.25dB, 3.01dB, 4.77dB, and 6.02dB. For other modulation orders, set-partitioned UDM, block- coded HDM, sphere-cut lattice-packed HDM, unitary space-time modulation and so on can be used. The AMC controller 350 selects HDM depending on SNR, iteration counts, required BER performance, allowable complexity, and maximum power consumption, according to network demands.

[0027]

In these embodiments of the invention, the AMC controller 350 also uses an enhanced finite set of FEC codes 352, wherein the FEC codes have not only various code rates but also various PCMs for each code rate. For example, one PCM of 1/2-rate LDPC code for BPSK is different from another PCM of 1/2-rate LDPC code for 16QAM, depending on the number of decoding iterations and demodulation iterations at the receiver. In particular, this embodiment is effective for supporting various HDM formats using BICM-ID because one LDPC code designed for one modulation format does not offer the best performance for the other modulation formats.

[0028]

While the conventional AMC network uses only the rate adaptation

according to the channel quality, this embodiment of the invention uses PCM adaptation according to the receiver behavior as well as the channel quality. For example, when the receiver reduces the number of iterations for decoding and changes to use no iteration for demodulator to reduce power consumption, a different LDPC code, whose PCM is pre-designed for this receiver parameter setup, is used at the transmitter. For another example, when the transmitter uses higher dimensional modulation and the receiver uses iterative demodulation in order to achieve lower BER, a different LDPC code, whose PCM is pre-designed for this HDM and this receiver parameter setup, is selected. This PCM adaptation can provide better performance by 2dB than the conventional AMC using the constant PCM because one of best LDPC codes for one receiver condition does not always perform well for different receiver parameter setups.

[0029]

Adaptive LDPC Codes for Finite-Iteration Decoder

One embodiment uses different PCMs depending on the number of iterations for decoding and demodulation. The receiver may use a variable-iteration decoder, in which the maximum number of iterations is adaptive to adjust the decoder throughput and power consumption depending on the condition and demand. This invention is based on a realization that the best LDPC code depends on the number of iterations for decoding and demodulation. For example, one LDPC code designed for 32-iteration decoder does not perform well for 4-iteration decoder. In conventional networks, the LDPC code is typically designed for a sufficiently large or even infinite number of iterations by linear programming for curve fitting of an extrinsic information transfer (EXIT) chart in order to provide best possible performance for idealistic decoders. This embodiment of the invention takes the finite-iteration decoding into account for practical receivers. The LDPC code is designed by a method using a trajectory of mutual information update over decoder iterations in EXIT chart analysis, instead of using the curve fitting.

[0030]

Fig. 4 shows a non-limiting example of the AMC controller using variable- rate and variable-PCM codes 352 according to one embodiment of the invention. This embodiment provides the best possible pair of the modulation format and FEC code for practical finite-iteration decoder, which may change the maximum number of iterations to adjust the power consumption and the BER performance. In this embodiment, the AMC controller 350 adaptively selects 310 the code rate and PCM from a finite set of FEC codes 352, depending on the maximum number of decoding iterations 343 as well as the measured SNR value 141. In this example, there are three different code rates of R =1/2, 2/3, and 3/4, each of which has two different PCMs H _{R 4} and H _{R 32} for 4-iteration decoding and 32-iteration decoding, respectively. In addition to the modulation formats, the different PCMs, i.e.,

#1/2,32 » 2/3,32 * and #3/ ,32 * ^are adaptively selected as a function of SNR for 32- iteration decoding, according to a selection rule table 41 1. And, another selection rule table 412 is used for 4-itertion decoding to adaptively select PCMs, i.e., #1/2,4, #2/3,4 ₅ and #3/4,4, as well as the modulation format. The 32-iteration decoding offers better BER performance than 4-itertion decoding, while longer decoding latency and higher power consumption are required.

[0031]

Since the BER performance of LDPC codes depends on the degree

distribution of the PCM and the maximum number of iterations, the PCM H _{R 4} has a different degree distribution compared to the PCM H _{R 32} to provide the best BER performance for any iteration counts. The PCMs for LDPC codes are usually very sparse, i.e., the number of non-zero elements in the PCM is much smaller than the total number of elements. Any PCM has an equivalent representation by a bipartite graph, wherein each column, row, and non-zero element of the PCM are

represented, respectively, by a variable node, a check node, and an edge

connecting between one variable node and one check node. The number of edges connecting to one variable node is referred to as a variable node degree. The number of edges connecting to one check node is referred to as a check node degree. The BER performance of the belief propagation decoding for LDPC codes highly depends on the degree distribution. For example, a rate- 1/2 regular LDPC code having a variable node degree of 5 and a check node degree of 10 for all nodes performs poorly in general. In order to achieve the best possible performance, the degree distribution for irregular LDPC codes is designed by the EXIT trajectory analysis, wherein the finite number of decoding iterations is taken into account by a trajectory of mutual information updates over iterations.

[0032]

Fig. 5 is a table of a non-limiting example of the degree distribution

designed for the iteration-dependent AMC, as a function of iterations and code rates R, according to some embodiments of the invention. In Fig. 5, the optimized degree distributions of variable nodes for various code rates (R = 1/2, 2/3, 3/4, 4/5, and 9/10) and maximum number of iterations (2, 4, 8, 16, 32, and infinity) are present. This example considers check-concentrated LDPC codes, whose check node degrees are two consecutive integers. Therefore, the degree distribution of check nodes is automatically given by the variable degree distribution and the code rate. The degree distribution is represented by a polynomial function 501, e.g., as 0.21x ² + 0.33x ³ + 0A6x ¹² , which indicates that 21%, 33%, and 46% of edges are connected to variable nodes having degrees of 2, 3, and 12, respectively. The required SNR (RSNR) 502 can be improved when higher power consumption for more number of iterations is allowed. Note that the designed degree distribution depends on the code rates and the number of iterations. This embodiment of the invention using iteration-dependent PCM adaptation provides up to 2dB gain compared to the conventional AMC, in which PCM does not depend on the number of iterations. In one embodiment, the AMC controller also depends on the number of demodulation iterations in addition to the number of decoding iterations for BICM-ID networks.

[0033]

Adaptive LDPC Codes for High-Dimensional Modulations

In yet another embodiment of the invention, the PCM depends on the modulation format as well as the SNR value, the number of iterations for decoding, and the number of iterations for demodulation. This embodiment is based on a realization that one LDPC code designed for one modulation format does not perform well for another modulation format when BICM-ID is employed.

[0034]

Fig. 6 shows the AMC controller using modulation-dependent PCM

adaptation according to this embodiment of the invention. The AMC controller 350 uses a finite set of variable-order and variable-dimensional modulation formats 351, and a finite set of variable-rate and variable-PCM codes 352, wherein there are a large number of different PCMs for each code rate. For example, a PCM denoted by H R,mxn,qQAMdO is ^use d for the case when the code rate is R, the number of decoding iterations is n, the number of demodulation iterations is m, the

modulation order is q, and the modulation dimension is d. The AMC controller 350 selects the best combination of modulation order q, modulation dimension d, and code rate R according to a selection rule table 611, which depends on the SNR value, the number of decoding iterations n, and the number of demodulation iterations m. Given the selected combination, the corresponding PCM and

generator matrix are provided to the receiver and the transmitter. By using different PCMs for different modulation formats, the best possible BER performance can be achieved especially for high-order and high-dimensional modulations.

[0035]

Fig. 7 is a table of a non-limiting example of the degree distribution of check-concentrated LDPC codes designed for BPSK-alternative high-dimensional modulations (2D, 4D, 8D, 16D, and 24D), according to this embodiment of the invention. In this example, the degree distributions 702 of the PCMs for 16D modulation based on the Nordstrom-Robinson nonlinear code and for 24D

modulation based on the extended Golay code are different from that for BPSK 2D modulation. By increasing the modulation dimension 701, the required SNR 703 can be significantly improved from 4.35dB to 0.69dB. This modulation-dependent AMC offers some gain (e.g., 0.3dB gain for 24D modulation at a code rate of 9/10) from the conventional AMC, in which PCM is independent of the modulation format.

[0036]

Parity-Check Matrix (PCM) Design

The embodiments of the invention use different PCMs for modulation- and iteration-dependent AMC networks. Multiple PCMs are designed for each parameter setup of q-QAM, d-dimension, n-iteration decoding, m-iteration demodulation, code rate R, and codeword length N.

[0037]

Fig. 8 shows a schematic of PCM design according to some embodiments of the invention. This PCM design procedure is carried out either beforehand off-line or real-time on-line at the AMC controller 350, using some memory storages and computing processers. The PCM design method comprises a degree optimization 810, an EXIT trajectory analysis 820, and a girth optimization 830, given coding parameters (code rate R and length N) 801, modulation parameters (order q and dimension d) 802, and receiver parameters (decoding iteration n and demodulation iteration m) 803, to provide optimized PCM 832 and its corresponding generator matrix 836.

[0038]

The degree optimization 810 uses a heuristic optimizer 81 1 to jointly optimize variable node degree distribution and check node degree distribution 812, in order to achieve the minimum possible required SNR, which is calculated by RSNR search 815. The degree distribution 812 is designed with the coding parameter 801, such that the average variable node degree d _v and average check node degree d _c are constrained as R = 1 — d _v /d _c . In practice, there is another constraint in the maximum degree (e.g., 16), which can determine the decoder throughput. The BER performance is usually improved by increasing the maximum degree, while the larger maximum degree can reduce the maximum decoder throughput. The heuristic optimizer 81 1 can use any optimization algorithms such as differential evolution, evolutionary strategy, genetic algorithm, simulated annealing, particle swarm optimization, Nelder-Mead, and quasi-Newton method, to minimize the required SNR. The RSNR search 815 can use any line search algorithms such as golden section search, bisection search, and Newton- Raphson method, to find the required SNR for the given degree distribution. The RSNR search 815 uses a tentative SNR value 816 to check if a finite-iteration decoder can decode the LDPC codes having the given degree distribution at the SNR value, by using the EXIT trajectory analysis 820. The SNR value 816 is chosen from a larger value than the theoretically minimum possible value determined by the Shannon limit of q ^R — 1.

[0039]

In order to take the finite-iteration decoder and high-dimensional modulation into account, the methods of the invention modify some principles of the EXIT chart analysis, derived by S. ten Brink, G. Kramer, and A. Ashikhmin in "Design of low-density parity-check codes for modulation and detection," IEEE

Transactions on Communications, vol. 52, no. 4, April 2004. Rather than using EXIT curve fitting or linear programing, the embodiment uses the EXIT trajectory analysis 820 for practical decoders.

[0040]

In this embodiment of the invention, the EXIT trajectory analysis 820 uses the SNR value 816 and the degree distribution 812 in addition to the modulation parameters 802 (which determine the modulation format) and the receiver parameters 803 (which determine the maximum number of iterations for decoding and demodulation), to calculate the mutual information after the fmite-iteration decoding/demodulation for the given modulation format. The EXIT trajectory analysis 820 comprises a modulator 821, an emulated channel 822, a demodulator 823, a variable node decoder (VND) 824, and a check node decoder (CND) 825, with an iteration loop 826 from the CND to the VND and another iteration loop 827 from the CND to the demodulator. The demodulator loop 827 is iterated m times, and the decoder loop 826 is iterated n times every demodulator loop. The EXIT trajectory analysis uses Monte-Carlo simulations to generate many

realizations of demodulator output by emulating the communications networks from the modulator 821 to the demodulator 823 through the virtual channel 822. The demodulator output is then statistically analyzed to calculate the mutual information. The modulator 821 and the demodulator 823 use the modulation parameters 802 to use the q-ary d-dimensional modulation format. The channel 822 uses the SNR value 816 to add random noise by a pseudo-random number generator from the white Gaussian distribution. Given the noisy channel output, the demodulator 823 generates log-likelihood ratio (LLR) output, with and without the decoder feedback 827. For high-order and high-dimensional modulations, each bit LLR can have different reliability, and the mutual information for each bit is calculated separately. For example, the most significant bit for 16QAM has higher mutual information than the least significant bit. The mutual information is calculated by taking sample mean of the LLR values as / _DEM = 1— E[l + exp(— L)], where 7 _DEM is the mutual information of the demodulator output, E[. ] denotes the statistical sample mean, and L is the LLR value. The original random data transmitted from the modulator is used as a precoded coset leader, which adds zero codeword of the LDPC coding so that the encoding is not necessary for the mutual information analysis. For example, the LLR is algebraically inverted by the known transmitted data to emulate zero-word transmissions.

[0041]

The calculated mutual information of the demodulator output are fed into the VND 824, where the mutual information is updated by another mutual information representing the belief propagation from the CND 825 from the previous iteration 826. The mutual information update is calculated as follows VND = ; (vw _* - OtrK ] ² + [TK/DEM)] ² ) .

where d _v is the variable node degree, and 7 _CND is the mutual information of the CND output. Here, the J-function is defined as

a s ³ + b[s ² + c[s, 0 < 5 < s ₀ ,

/O) = 1 - e pCc^s ³ ) + b ₂ 's ² + c ₂ 's + d ₂ ',s ₀ <s < 10,

l,s> 10,

where a[ = -0.0421061, b[ = 0.209252, c[ = -0.00640081, a ₂ ' =

0.00181491, b ₂ ' = -0.142675, c ₂ ' = -0.0822054, d ₂ ' = 0.0549608, and

s ₀ = 1.6363. And, the inverse- J function is defined as

-1 ₌ ( l ² + b I + Ci J, 0 < / < I ₀ ,

{-a ₂ \nb ₂ (l-D-c ₂ I,I ₀ <I < 1,

where = 1.09542, b _x = 0.214217, c _x = 2.33727, a ₂ = 0.706692, b ₂ =

0.386013, c ₂ = -1.75017, and /„ = 0.3646. According to the variable node degree distribution 812, the updated mutual information are averaged and submitted to the CND 825.

[0042]

At the CND 825, the averaged mutual information are updated for each degree-d _c check nodes as follows

/CND = 1 -/( (d _C - l)[/- ^;l (l - vND)] ² ).

[0043] According to the check node degree distribution 812, the updated mutual information are averaged, and submitted back to the VND 824.

[0044]

After n iterations of the decoding loop 826, the extrinsic mutual information from the decoder are fed back to the demodulator 823 through the demodulator loop 827. The extrinsic mutual information are expressed as EXT = ; ( ^I/- ¹ ( CN D)] ² )- -

[0045]

With the extrinsic mutual information, the demodulator 823 updates the LLR by feeding the corresponding a priori belief messages, generated by a pseudorandom number generator from the Gaussian distribution with a standard deviation of / ^_1 ( ΕΧΤ)· The demodulator output is analyzed to calculate the mutual information of the updated LLR subtracted by the extrinsic mutual information. The updated mutual information from the demodulator 823 are then submitted to the VND 824. The demodulator iteration loop 827 is iterated m times, and the above mutual information updates are iterated mn times in total over the n- iteration decoding and the m-iteration demodulation.

[0046]

After all mutual information updates are done, the mutual information of the a posteriori probabilit is calculated as

and the EXIT trajectory analysis 820 provides the mutual information of the a posteriori probability to the RSNR search 815. The RSNR search 815 uses the line search algorithm to find the minimum possible SNR, at which the EXIT trajectory analysis gives the mutual information achieving 1 (within a certain numerical precision). [0047]

The degree optimization 810 submits the optimized degree distribution 812 to the girth optimization 830 to generate the PCM 832 according to the degree distribution. One embodiment of the invention uses a progressive edge growth (PEG), proposed by X.-Y. Hu, E. Eleftheriou, and D.M. Arnold in "Regular and irregular progressive edge-growth tanner graphs," IEEE Transactions on

Information Theory, vol. 51, no. 1, pp. 386-396, Jan. 2005. The PEG uses a greedy design method to increase the girth of the sparse bipartite graph, according to the target degree distribution and the desired codeword length N of the coding parameters 801. The PEG generates one PCM H 832 of a size M x N, optimized for the given coding parameters 801, the modulation parameters 802, and the receiver parameters 803.

[0048]

The corresponding generator matrix G 836 is computed, e.g., by the

Gaussian elimination 835, to generate a systematic codeword. Because there is no unique reorientation to fulfill the orthogonal compliment pair of HG = 0, any other different methods such as a block-diagonalization method may apply to calculate the generator matrix. The procedure in the PCM design method 800 is carried out for all possible combinations of the coding parameters 801, the modulation parameters 802, and the receiver parameters 803.

[0049]

In one embodiment, the mutual information updates are done by considering the statistical deviation due to the finite codeword length and finite-precision computations. In this embodiment, the mutual information is updated by the J- function and the inverse J-function with a standard deviation loss. For example, the mutual information updates are modified as follows /VN D = / (<xj(d _v - Dt .-K cNo)] ² + [TK DEM )] ² ), where ≤ 1 is a loss parameter, empirically modeled as a function of the codeword length N, the variable node degree d _v , the target SNR, the precision digits, and the input mutual information. This robust degree distribution design can provide better performance, especially for short LDPC codes.

[0050]

In another embodiment, the PCM design method is modified to use nonbinary LDPC codes, whose PCM comprises 0,1, ... , Q — 1 for the Galois field or the Lie ring of alphabet size Q. This embodiment uses an expected ensemble average of the mutual information for the nonbinary belief messages, by using the nonbinary variant of EXIT chart analysis. The nonbinary EXIT chart analysis also uses the J-function assuming that the nonbinary LLR vector is modeled by a correlated Gaussian distribution. The covariance is written as +

1Q_ ₁ 1Q_ ₁ )S ² /2, where s is the standard deviation, is the identity matrix of size Q — 1, Ιρ-i is the all-one vector of size Q— 1, and the superscript of [. ] ^T denotes the transpose. The nonbinary LDPC codes are particularly important because the BER performance is usually improved and the demodulation iteration can be avoided if the alphabet size holds Q = q ^d ^ ² , whereas the computational complexity increases linearly with Q for nonbinary belief propagation decoding based on fast Fourier transform Q -ary sum-product algorithm (FFT-QSPA).

[0051]

In yet another embodiment, the heuristic optimizer jointly optimizes multi- objective functions, comprising not only the required SNR but also the decoder complexity and the encoder complexity. This embodiment is based on a realization that the computational complexity of the belief propagation decoding is a function of the degree distribution. For example, the computational complexity of the VND increases with the variable node degree, in particular for fixed-point precision implementation. Using multi-objective variants of differential evolution, evolutionary strategy, and genetic algorithm, the heuristic optimizer searches for the best degree distribution 812 to provide a set of Pareto optimal solutions, which achieve, for example, the minimum possible required SNR and the minimum possible decoding complexity at the same time. For example, because the mutual information depends on a labeling for high-order and high-dimensional modulation if Q≠ q ^d / ² , the modulator 821 also uses a labeling table provided by the heuristic optimizer 811 to optimize the labeling together with the degree distribution.

[0052]

Parity-Check Matrix (PCM) Design for Dynamic Window Decoding of QC- LDPC Convolutional Codes

In one embodiment, the mutual information updates are tracked over all variable nodes and check nodes having different connectivity, characterized by a protograph. This embodiment uses a protograph-based EXIT chart analysis, which can provide more accurate performance prediction by using edge connection knowledge. For example, the check node degree is averaged not only by the degree distribution but also by all possible pairs derived by multi-nomial distribution. This embodiment is useful for high-order and high-dimensional modulation to take different LLR reliabilities into account.

[0053]

For protograph-based LDPC codes, the PCM design can avoid using the PEG by considering quasi-cyclic (QC) LDPC codes, which are preferred for low- complexity encoding in some applications. In addition to the low-complexity encoding of QC-LDPC codes, the decoding can be simplified by using a dynamic window decoding for the case when the protograph is structured as a spatially- coupled convolutional coding. In some embodiments of the invention, the PCM design considers the protograph-based QC-LDPC convolutional codes for the dynamic window decoding. The dynamic window decoding performs well, while the decoding latency can be adjusted by a window size. This is particularly important for some modern communications applications, which are latency critical, e.g., machine-to-machine communications and optical interconnects.

[0054]

Fig. 9 shows the schematic of the PCM design for QC-LDPC convolutional codes according to these embodiments of the invention. The design method uses the coding parameters 901, the modulation parameters 802, and the receiver parameters 903. The coding parameters 901 comprises a QC matrix size C (e.g., C = 256) as well as the code rate R and the length N. In this embodiment, the degree optimization 810 is not directly performed, while the protograph

optimization 910 is carried out. The protograph optimization 910 uses the heuristic optimization 81 1 to design a protograph base matrix B 912. The protograph base matrix B is a size of M/C-by-N/C, which determines the block- wise connectivity of QC-LDPC codes. For QC-LDPC convolutional codes, the protograph base matrix is structured as a band matrix, in which non-zero entries are confined to a diagonal band 913. This band matrix structure enables low-complexity encoding and low-latency decoding. Rather than using regular QC-LDPC convolutional codes, whose variable node degree is constant over all variable nodes, the heuristic optimizer 811 searches for the best irregular band matrix, e.g., by using simulated annealing, genetic algorithm, and differential evolution, in terms of the minimum possible required SNR. The RSNR search 815 finds the required SNR by using a protograph-based EXIT (P-EXIT) trajectory analysis 920, which tracks the mutual information updates for all the variable nodes and check nodes in the protograph base matrix. Here, the P-EXIT trajectory analysis uses Monte-Carlo mutual information analysis according to the protograph base matrix, given the receiver parameters 903, which comprise the window size W as well as the decoding iteration n and the demodulation iteration m. The window size W 914 determines how many consecutive variable nodes propagate belief messages at once in the dynamic window decoding. The band matrix allows a relatively small window size without large performance degradation while the decoding latency can be significantly decreased.

[0055]

Once the protograph optimization is done, the optimized protograph base matrix is submitted to a girth optimization 930. For QC-LDPC codes, the girth optimization is done by using a greedy permutation 931 instead of using the PEG 831. This embodiment uses some principles of the girth optimization described in US 20130086456 Al . The greedy permutation 931 sequentially searches for the minimum cycle in the protograph base matrix by an algebraic computation check, and modifies the exponent of the cyclic matrix. As a non-limiting example, the cyclic matrix of size C X C is defined as

In the end, the optimized PCM 932 is obtained for QC-LDPC convolutional codes. The corresponding generator matrix G is provided by a convolutional coding structure 935, which creates multiple generator matrices for sub matrices in the PCM for convolutional encoding.

[0056]

Adaptive Receivers using Few Number of Generator Matrices

To support all possible combinations of the coding parameters (the code rate R, the length N, and the QC size C), the modulation parameters (order q and dimension d) and the receiver parameters (the decoding iteration n, the demodulator iteration m, and the window size W), the AMC scheme according to the embodiments in Fig. 6 requires to provide a large number of pairs for generator matrices and PCMs. For example, when the receiver parameters comprise all combinations of m 6 {1,2,4,8,16,32}, n 6 {1,2,4,8,16,32}, and

W G {10,20,40,80,160,320}, the total number of combinations becomes 6 ³ =. 216 for every code rate and every modulation format. Some embodiments of the invention solve this problem by reducing the required number of generator matrices. This embodiment is based on a realization that the orthogonal pair of the generator matrix G and the PCM H is not uniquely defined. This suggests that a lot of linearly dependent PCMs can be generated for one generator matrix. This embodiment is also based on a realization that the decoding performance is dependent on the degree distribution of PCMs, whereas the generator matrix does not directly determine the BER performance but encoder complexity.

[0057]

Fig. 10 shows the schematic of the PCM design method according to this embodiment of the invention. In this embodiment, an initial generator matrix G ₀ and an initial PCM H ₀ are first optimized by the PCM design method 800 in Fig. 8 or the PCM design method 900 in Fig. 9. The initial matrices 1032 are designed for one combination 1002 of the modulation parameters 802 and the receiver parameters 903, for a coding parameter 901. For example, the PCM design begins one typical set of parameters, e.g., q = 4, d = 2, n = 16, and m = 1. The designed PCM H ₀ works only for this set of parameters. This embodiment uses the common generator matrix G ₀ regardless of the modulation parameters and the receiver parameters, so that the number of required generator matrices are reduced for the transmitter in the AMC networks. For example, when the receiver changes the number of iterations for decoding, the AMC network keeps using the same generator matrix, while the different PCM is adaptively selected to be optimal for the receiver.

[0058]

The PCM adaptation 1050 then modifies the initial PCM H ₀ to be optimal for the different combinations 1003 of the modulation parameters and the receiver parameters. For example, the modified PCM 1051 is optimized for fewer- iteration decoder, e.g., q = 4, d = 2, n = 4, and m = 1. The optimized PCM H _T 1051 has a different degree distribution from the initial PCM H ₀ , while it is still orthogonal to the initial generator matrix G ₀ such that H ₁ G ₀ — 0 over the Galois field or the Lie ring. At the PCM adaptation 1050, the PCM refinement 1040 searches for the best PCM, which is linearly transformed at a greedy transform 1041, to achieve the minimum possible required SNR 1042 via the protograph- based EXIT trajectory analysis 1020. The greedy transform 1041 adds one randomly selected row to another randomly selected row of the PCM. The random selection is prioritized for a pair of rows, which has a higher correlation so that the PCM does not rapidly increase the number of non-zero elements. For each linear- transformed PCM, the required SNR is determined by the EXIT trajectory analysis 1020, which uses the considered combinations 1003 of the modulation parameters and the receiver parameters. After several iterations of the random linear transforms, the best PCM H ₁ to provide the minimum required SNR is obtained.

[0059]

The PCM adaptation 1050 is performed for all different combinations of the modulation parameters 802 and the receiver parameters 903. In the end, multiple PCMs (H ₀ , , ...) having different degree distributions are designed for various different parameters, while the transmitter can keep using only one generator matrix G ₀ for each code rate.

[0060] One embodiment can use a regular LDPC code for encoder, while the redesigned irregular PCM, which is orthogonal to the regular LDPC generator matrix, can be used for better decoding performance. In another embodiment, a fast- encodable LDPC codes such as bi-diagonal LDPC codes or QC-LDPC codes are used at the transmitter, while the receiver uses the re-optimized PCM, which is linearly dependent on the original PCM, to achieve better BER performance.

[0061]

Parity-Check Matrix (PCM) Adaptation over Iteration

Based on the realization that multiple PCMs having different degree distribution can be designed for one common generator matrix, another

embodiment of the invention uses more dynamic PCM adaptation across decoding iterations. This embodiment can improve the convergence speed for mutual information updates over the belief propagation decoding, and can mitigate a BER error floor problem by removing the cycle over the bipartite graph. In the previous embodiments, the best PCM designed for a finite-iteration decoder does not change over the iteration count. For example, one PCM Z/1/2,32 ^1S used for the code rate 1/2 and for 32-iteration decoding over all iteration counts from the 1 ^st iteration to the 32 ^nd iteration. In this embodiment of the invention, multiple different PCMs #i/2,32 [i] > #i/2,32 [2] > · · > #i/2,32 [32]∞ ^Q designed for the 32-iteration decoding, wherein the i-th PCM #1 2,32 _[ i _] achieves the best performance at the i-th iteration to maximize the mutual information.

[0062]

This embodiment is related to adaptive belief propagation (ABP), while the PCM adaptation across the iteration count is pre-defined unlike the ABP. The method of this embodiment can remove a fundamental problem of minimal cycles over a bipartite graph, which can cause a BER error floor, by changing directly the bipartite graph over iteration. In addition to the error floor mitigation, this embodiment can improve the convergence speed of belief propagation decoding because the best PCM can be designed to have specific degree distribution in order to maximize the mutual information for every iteration count.