Coding Techniques for Future Wi-Fi

Future wireless applications such as high definition video streaming, wireless cloud radio access networks, and cellular data offload are bandwidth-hungry, which highlights the need for Wi-Fi links exceeding 1 Gb/s. This article discusses coding schemes and, in particular, the use of Low-Density Parity-Check (LDPC) codes as Forward Error Correction (FEC) in future Wi-Fi standards. Moreover, we consider advanced design strategies such as root-check LDPC structures, computer-aided design for short blocks and high-performance decoding algorithms with low latency. We then conclude the article with a discussion of FEC challenges for future Wi-FI applications.


I. INTRODUCTION
Driven by the ever-increasing user connectivity demands, emerging and future generations of Wi-Fi, such as IEEE 802.11ac and WiGig IEEE 802.11ad, will be capable of achieving multiple gigabits per second speeds. Furthermore, the future Wi-Fi will be used to do everything from simple web browsing and peer-to-peer sharing, to multimedia streaming, real-time teleconferencing, cable replacement, and wireless docking, to name a few. Therefore, one key element will be the reliable delivery of information at the final destination. One strategy to improve the reliability of the received information is the use of Forward Error Correction (FEC). FEC relies on a mathematical mapping of messages to include a special kind of redundancy that enables the receiver to correct the errors caused by the channel [1].
There are two main types of FEC used by Wi-Fi: LDPC codes and convolutional codes.
LDPC codes belong to the class of block codes, can perform close to channel capacity and achieve excellent performance. Block codes work on fixed-size blocks (packets) of bits or January  whereas LDPC codes are preferred for higher latencies or medium to large blocks [2].
In Fig. 1 an example of a system model for a Wireless Local Area Network (WLAN) is presented. In Fig 1 a), we have a Wi-Fi communications system where a tablet, a laptop and a mobile phone exchange information with an Access Point (AP). In Fig. 1 b) a simplified structure of a Wi-Fi communication system between a transmitter (TX) and a receiver (RX), for example, a laptop and an AP is shown. In Fig. 1  Extensions to OFDM systems [3], [4] and multiple-antenna systems [5] can also be considered.
The focus of this article is on LDPC design and decoding strategies for future Wi-Fi.
Following the system model of Fig. 1  consists of m × n circulant sub-matrices of dimensions s × s with M = ms and N = ns, the resulting linear block code will be a QC code with a period of n. In such code, the n-bit shift of any codeword is another codeword. The generator matrices G of QC-LDPC codes are in systematic-circulant form with the requirement that the PCM are full rank. The memory cost for encoding QC-LDPC codes is greatly reduced and the encoder can be implemented by using simple shift registers [1].
The accumulator-based codes that were invented first are the so-called repeat-accumulate (RA) codes [1]. Despite their simple structure, they were shown to provide good performance and, more importantly, they pioneered the design of efficiently encodable LDPC codes. The key points in using IRA-LDPC codes are the simplicity in designing such codes and faster encoding than conventional LDPC methods. The Wi-Fi standard uses a type of QC-LDPC codes, whereas other standards work with a combination of QC and IRA LDPC codes known as QC-IRA LDPC codes.
There are two main advantages in QC-IRA-LDPC codes: the memory requirements to store the matrices by QC codes and the simple encoding process provided by IRA codes. For instance,   Fig. 2 is an LDPC code with code rate R = 1 2 . The rate 1 2 means that half of the codeword is the message (information) and the other half is the redundancy. The Wi-Fi standard operates with the following code rates, R = 1 2 , 3 4 , 5 8 and 13 16 with a fixed block length of L = 672 bits. For example, with a code rate 1 2 we have 336 information bits plus 336 bits of redundancy, for code rate 13 16 we have 546 information bits plus 126 bits of redundancy. Fig. 3 presents the PCM H of the Wi-Fi standard with code rate R = 1 2 and dimensions 336 × 672. The other PCMs for the rest of code rates follow a similar structure as for code rate Once a standard is defined, a design is adopted and the PCM H must be stored in all devices for compatibility issues. Whenever the standard is updated there is an opportunity to incorporate more sophisticated PCM designs which could lead to improved performance.

IV. DESIGNING HIGH-PERFORMANCE LDPC CODES
In this section we review advanced LDPC code design strategies such as Progressive Edge Growth (PEG) algorithms, Root-Check LDPC structures, QC and IRA structures.

A. PEG-Based Algorithms
Among the algorithms capable of producing LDPC codes of highest performance and efficiency for short to moderate lengths are the PEG-based algorithms [6] and QC and IRA structures.
The codes produced by the PEG algorithm exhibit improved performance compared to random construction methods [6] as PEG optimizes the underlying graph structure of the PCM. In particular, PEG strategies attempt to increase the girth of the graph and improve its general connectivity. Improvements and modifications in the original PEG algorithm have provided a better performance than the original PEG algorithm. For instance, Healy and de Lamare in [7] have proposed an algorithm to design LDPC codes which involves the use of decoder-based optimisation with the sum-product algorithm (SPA) and also considered multiple candidates to optimize the graph connections [8]. Therefore, LDPC codes for future Wi-Fi standards can take advantage if they are designed by PEG-based algorithms and several detection and decoding strategies [9], [10], [11], [12], [13], [14].

B. Structured Code Designs
A drawback of standard unstructured LDPC codes designed with conventional and PEG-based algorithms is their high encoding complexity, which impacts the cost and power consumption of devices. Fortunately, the memory and computational cost for encoding LDPC codes can be greatly reduced by adopting QC-LDPC codes because the encoder can be implemented by simple shift registers. Furthermore, IRA LDPC codes are also useful due to their simplicity in designing and faster encoding than conventional LDPC codes. In addition, designers can resort to QC-IRA LDPC codes which brings further cost reduction by combining the features of QC and IRA LDPC codes [15], using PEG-based optimization of the graphs and statistically-driven approaches [16]. These highly structured LDPC codes could play an important role in the design of future Wi-Fi standards.

C. Root-Check Codes
Another family of LDPC codes called Root-Check for block-fading channels were proposed in [17]. Root-Check codes are able to achieve the maximum diversity of a block-fading channel and have a performance near the limit of outage. Several types of Root-Check LDPC codes were developed, e.g, [18], [19], [8]. Among the Root-Check based LDPC codes the ones designed with the PEG algorithm have shown the best performance [19]. In particular, we have designed For example, consider a simple scenario where the channel is a block-fading with F = 2 fadings, BPSK modulation is used and a maximum of 20 decoding iterations are allowed.
In Fig. 4 we depict the Frame Error Rate (FER) performance of a Root-Check LDPC code versus the LDPC code from Wi-Fi standard both are with the same code rate and with the same block length. The outage curve is also plotted as reference which represents the channel capacity.
From Fig. 4, we can see that the QC-IRA Root-Check LDPC code outperforms the Wi-Fi LDPC code by 6.5dB in terms of SNR.

V. ADVANCED DECODING TECHNIQUES
In this section, we discuss advanced LDPC decoding techniques which include reweighting and scheduling approaches, and low-complexity decoding algorithms. These algorithms offer considerable advantages over standard belief propagation (BP) algorithms and can address some of its limitations with regards to performance, delay issues and computational cost.

A. Reweighting Methods
The BP algorithm, sometimes also called sum-product algorithm (SPA), is a powerful algorithm to approximately solve several inference problems which can be used for error control coding.
where L(x j ) is the a priori Log Likelihood Ratio (LLR) from the channel, ρ is the constant

B. Scheduling Methods
The studies in [22], [23] have suggested that the use of appropriate scheduling mechanisms for LDPC decoding can significantly improve the convergence speed in terms of number of iterations. In general, BP or SPA consist of the exchange of messages between the nodes of a graph. Each node generates and propagates messages to its neighbours based on its current incoming messages.
The LDPC code graph is a bi-partite graph composed by N V N variable nodes v j for j ∈ {1, · · · , N V N } that represent the codeword bits and M CH check nodes c i for i ∈ {1, · · · , M CH } that represent the parity-check equations [22]. RBP was first introduced in [24] and consists of an informed dynamic scheduling strategy that updates messages according to an ordering metric called the residual. The message with the largest residual is updated first. A residual is the norm (defined over the message space) of the difference between the values of a message before and after an update. The intuitive justification of this approach is that as iterative BP converges, the differences between the messages before and after an update diminish. Then, if a message has a large residual, it means that it is located in a part of the graph that has not converged yet. Accordingly, propagating that message first should speed up convergence.
In order to obtain a better performance, a less greedy scheduling strategy can be used. Node Wise Scheduling BP (NWBP). Fig. 6, depicts an example decoding techniques, which illustrates how they can reduce significantly the number of iterations as compared to BP. With the advent of parallel computing in the latest powerful processors, the use of scheduling methods can reduce significantly the overall number of iterations required in the decoding procedure. With the advent of parallel computing in the latest powerful processors, the use of scheduling methods can reduce significantly the overall number of iterations required in the decoding procedure.

C. Reduced Complexity Decoding Methods
Work on LDPC decoding has mainly focused on floating point arithmetic or infinite precision (BP algorithm). However, hardware implementations of decoding algorithms for LDPC codes must address quantization effects in a fixed-point realization [25]. The first approach was to adopt a logarithmic version of the BP algorithm called Log-BP. Nevertheless, Log-BP sacrifices hardware implementation due to the fact it requires many hyperbolic tangent operations.
The Log-BP algorithm can be simplified using the so-called BP-based approximation (also known as the "min-sum" approximation), which greatly reduces the implementation complexity, but incurs a degradation in decoding performance. This has led to the development of many reduced complexity variants of the BP algorithm that deliver near-optimum decoding performance. There are three main reduced complexity methods of decoding LDPC codes: BP-based, Normalized BP-based and Offset BP-based [25].
In the min-sum algorithm the key modification is on the horizontal step or the check to variable node update equation. The check to variable node update is given by where, Λ j ′ ,i are the messages sent from variable node v j to check node c i and j ′ ∈ N (i) \ j is the neighbouring set of variable nodes of c i except v j . As it can be seen in (2) there is no hyperbolic tangent operation which decreases significantly the overall computational complexity, although it causes a degradation in decoding performance.
The min-sum algorithm can be improved by employing a check node update that uses a normalization constant greater than α. The change made in (2) is on the right hand side and inside the min operation that is divided by α. This method is called Normalized BP-based.
The α parameter should be adjusted for different SNRs and iterations to achieve its optimum performance. An effective approach to determine the optimum value of α is by Density Evolution [25].
A computationally more efficient approach that captures the net effect of the additive correction term applied in each check node update operation is obtained from the BP-based decoding by subtracting a positive constant β. This is called Offset BP-based. Eq. (2) is modified such The PEG-based QC-IRA Root-Check LDPC code designed was compared to the Wi-Fi LDPC code to analyse the overall performance in terms of FER. As seen in Fig. 4 the PEG-based designed code has outperformed the Wi-Fi LDPC code by about 6.5dB. Therefore, future Wi-Fi standards would have benefits if they considered the use of Root-Check based LDPC codes for rate R = 1 2 scenarios. The use of scheduling methods to decode LDPC codes can reduce significantly the number of iterations required in the decoding procedure. Accordingly, the resulting number of iterations can increase the advantages LDPC codes over convolutional codes, which are widely used in portable devices due to their simplicity. An open problem in LDPC decoding is: Which is the most costeffective method for the Wi-Fi standard? This is an investigation that will keep designers of Wi-Fi systems busy in the next few years.
In terms of adoption of LDPC codes as FEC in Wi-Fi standards, key issues are the encoding and decoding operations. The cost of encoding can be decreased significantly by using RA based LDPC codes which are able to provide simple and low complexity encoding methods. The decoding cost is another key issue that must be addressed. One way to addressing such problem is by introducing reduced complexity decoding (RCD) algorithms, e.g., min-sum, normalized BP-based and Offset BP-based. The choice of decoding algorithm is another important design challenge, which must take into account aspects such low complexity operations, stability and performance.

VII. CONCLUSION
This article has discussed coding techniques for Wi-Fi systems. In particular, we have discussed approaches to reducing the complexity of encoding and decoding and improving the design and the decoding of LDPC codes. The main challenge is in decoding which is how to obtain an attractive trade-off between performance and computational complexity. To conclude, we advocate that future Wi-Fi standards should use LDPC codes as the main FEC to fulfil the needs of bandwidth-hungry and high-performance applications.

ACKNOWLEDGMENT
This work was partially supported by PNPD/CAPES (Brazil).