Low-density parity-check (LDPC) codes are used in the current 5G standard based on their powerful error-correction performance [1]. The theoretically achievable performance under message passing decoding requires high-precision message representations and computationally complex node operations. Such implementations introduce impractical latency and high power consumption. The desired throughput and latency promised by 5G [1] require practical hardware implementations that use finite-precision message passing algorithms and node computations that are simplified by smart approximations. Still, the error-rate performance of such finite-precision decoders deteriorates significantly with decreasing precision [2].
To address the challenge of good performance with low precision and simple computation, the information bottleneck (IB) decoder [2]- [6] combines ideas from information theory and machine learning. IB decoders differ from conventional finiteprecision decoders significantly. First, instead of executing any conventional arithmetic exactly or approximated, the node operations are replaced by relevant-information-maximizing functions which map discrete input messages onto discrete output messages.
While similar in operation to the lookup tables developed for finite-alphabet iterative decoding (FAID) approach [7], [8], the tables used in IB decoders are learned in an unsupervised manner, using the IB method [2]- [6].
As with the FAID approach, in the entire decoder no loglikelihood ratios (LLRs) are processed at any time. Instead, integer-valued messages, sometimes called cluster indices, are exchanged. However, whereas the FAID approach is mainly restricted to regular LDPC codes with variable node degree three, in our previous work [4], [9], [10], IB decoders with only 4 bits of precision perform within 0.1 dB of double precision belief-propagation for arbitrary regular and arbitrary irregular LDPC codes without puncturing. For irregular codes, message alignment provides a common representation across nodes with different degrees [5]. In [11] it was shown that, with a similar decoder, a throughput up to 500 Gb/s is possible with high energy and area efficiency.
To the best of our knowledge, all information bottleneck decoders in literature are tailored for a specific rate. However, in practical systems a rate-compatible decoding scheme is favorable. Recently, so-called protograph-based raptor-like (PBRL) LDPC codes were shown to pair very powerful errorcorrecting capabilities and an efficient structure which enables an inherent rate-compatibility [12].
This paper presents a generalized design of IB decoders to enable decoding of 5G-related PBRL codes with a bit-width down to 4 bits while incorporating puncturing and hence ratecompatibility into the IB decoder itself. In detail, the paper contains the following main contributions:
• This paper extends the design of IB LDPC decoders from [4], [5] to include puncturing in both the high-rate mother code and the degree-one variable nodes of PBRL codes.
This section briefly reviews the information bottleneck method. Furthermore protograph-based raptor-like (PBRL) LDPC codes are introduced.
The information bottleneck method [13] is a mutualinformation-maximizing clustering framework from machine learning. The overall information bottleneck setup is depicted in Figure 1. It considers a Markov chain X → Y → T of three random variables. X is termed the relevant variable, Y is termed the observation and T is a compressed representation of Y . The compression is described by the conditional distribution p(t|y). This compression mapping is designed such that the mutual information I(X; T ) is maximized while at the same time the mutual information I(Y ; T ) is minimized. If the mapping p(t|y) uniquely assigns a t to each y with probability 1, this mapping can be implemented in a lookup table such that t = f (y). Algorithms to find suitable compression mappings are described in [14]. These algorithms require the joint distribution p(x, y) and the desired cardinality |T | of the compression variable T as inputs.
Thorpe [15], [16] introduced LDPC codes constructed from a protograph, which is a small Tanner graph that describes the connectivity of the overall LDPC Tanner graph. A copy and permute operation referred to as lifting obtains the full LDPC parity check matrix from the protograph. Figure 2 shows the protograph structure of a PBRL code as described in [12], [17]. The protograph of an PBRL LDPC code consists of two parts: (1) a highest-rate code (HRC) protograph and (2) an incremental redundancy code (IRC) protograph. Thereby, the IRC provides lower rates as more of its variable nodes are transmitted, starting from the top. A more detailed introduction to PBRL LDPC codes is given in [12], [17].
This paper addresses the issue of designing IB decoders that accommodate the puncturing that is inherent to PBRL code families. As pointed out in [17], one or two variable nodes in the HRC are typically punctured, as indicated by the shaded HRC variable node in Figure 2. Thus, the IB decoder for the HRC must be designed to handle this puncturing. Additionally, all of the IRC variable nodes are punctured for the HRC, but degree-one variable nodes are added to the protograph as the rate is lowered. Thus, a degree-one variable node might be punctured depending on the code rate, as indicated by the partial shade of the degree-one variable nodes. The IB decoder must be able to adapt to the induced changes in the degree distributions and the associated changes in the probability distributions of message reliabilities that occur as the rate is lowered.
In the following section, this paper introduces all the required steps to construct an information bottleneck decoder as described in [4] and [5].
We consider binary LDPC codewords transmitted over a symmetric additive white Gaussian noise (AWGN) channel with binary phase shift keying modulation (BPSK) and quantized channel outputs. We use x to denote the equally likely transmitted symbols, which serve as channel inputs. The binary channel input x and continuous channel output y are related by the transition probability p(y|x). Feeding p(y, x) into the information bottleneck algorithm yields the quantizer mapping p(t ch |y), where t ch ∈ T ch denotes the discrete channel output. Such a mapping is illustrated in Figure 3. In general, a representative log-likelihood ratio can be assigned to each quantization region. These representatives correspond to the quantized channel knowledge which serves as input
Fig. 3. Quantization boundaries for the BI-AWGN channel computed using the information bottleneck algorithm from [4].
for belief-propagation decoding. In contrast, an information bottleneck decoder does not use any quantized LLRs, but processes a single cluster index t ch ∈ {1, . . . , |T ch |} instead.
In recent work [2]- [6], information bottleneck (IB) decoders were shown to handle the trade-off between low implementation complexity and near-optimal performance very well. When constructing an IB decoder, node operations are optimized specifically for the available discrete input and output alphabets rather than as approximations of the original belief propagation operations that assume the uncountable alphabet of all reals for inputs and outputs. The IB operations are essentially lookup tables mapping each possible set of incoming, discrete messages onto a discrete outgoing message. As a result, only highly informative integer-valued messages are passed along the edges of a Tanner graph.
To construct the discrete node operations, the joint probability distribution of the observed random variable and relevant random variable are required (cf. Figure 1). In the context of LDPC decoder design, the observed random variables are the M incoming discrete messages t in = [t in 1 , . . . , t in M ] T and the relevant random variable X depends on the node type. For a variable node, X represents the underlying code bit of a particular node, whereas, if the mapping is designed for a check node, X represents the (mod 2)-sum of the connected, possibly different code bits b 1 , . . . , b M . Given the joint distribution p(x, t in ) at each node type in every iteration, the information bottleneck method allows to squeeze p(x, t in ) through a compact bottleneck. Meaning that the highdimensional discrete observation vector t in , is mapped onto a scalar integer-valued cluster index t out ∈ T = {1, . . . , |T |} defined by the mapping p(t out |t in ). However, the information bottleneck method aims to preserve all relevant information such that I(X; T out ) ≈ I(X; T in ). Hence, at any time, X can be inferred very precisely using p(x|t out ) (cf. Figure 1). However, once the mappings are found, the actual decoding simplifies to lookups in offline generated tables, which map the sequence of incoming integers t in onto an outgoing integer-valued message t out . Therefore, instead of passing the meaning p(x|t out ), e.g. as LLR, only cluster indices are passed which are never converted to an explicit LLR representation.
In contrast to regular LDPC codes, irregular LDPC codes are characterized by nodes with varying degrees, i.e., the number of incoming messages differs. This paper leverages the edge-degree distribution [18]:
where λ d denotes the fraction of edges connected to variable nodes with degree d and ρ d denotes the fraction of edges connected to check nodes with degree d. Information bottleneck decoders pass integer-valued cluster indices t instead of log-likelihood ratios. As the eventspace of T is independent of the node degree d but in contrast the particular meaning p(x|t out , d) depends on the node degree, a receiving node cannot resolve if the message originates from a conveying node with high or low degree from the cluster indices alone. As the variety of node degrees increases also the range of the different meanings increases likewise. In turn, the decoder cannot exploit the full error-correction capabilities of the LDPC code because it cannot uniquely recover the actual meaning of the received message. In [5], it was revealed that with a processing at the origin nodes called message alignment, information bottleneck decoders can achieve competitive performance for LDPC codes with non-optimized irregular degree distributions.
As an extension to the original mutual-information based lookup table design, message alignment considers the three random variables T out , X and D jointly, i.e, the clusters, the channel input (which is the relevant random variable), and the node degree. Given the node dependent meanings p(x, t out |d) and the edge degree distributions, the task is to find a mapping p(z|t out , d) such that I(X; T out , D) ≈ I(X; Z) [5]. Using this modified objective, message alignment ensures that identical outgoing cluster indices of nodes with different degrees correspond to similar beliefs on the code bits. In fact, Figure 4 reveals that the objective of message alignment is closely related to the information bottleneck setup from Figure 1. Leveraging the information bottleneck notation, one would refer to X as the relevant quantity and T out and D represent the observation which squeeze through a compact bottleneck resulting in Z which is a compressed version of T out and D but preserves the maximum relevant information I(X; Z).
To decode PBRL LDPC codes the respective decoders must support puncturing. Although puncturing itself is a fairly easy problem for conventional decoders, the existing design of information bottleneck decoders prohibits the use of puncturing.
Message Alignment This section contains our main contributions. First, this paper shows how to incorporate punctured nodes using message alignment. Second, this paper devises a generalized scheme well suited for the structure of PBRL codes enabling ratecompatibility.
To increase the code rate, "punctured" codeword bits are not transmitted and are thus unknown to the receiver. In conventional approaches this corresponds to an LLR=0 for the respective punctured bits.
Going back to Figure 3 reveals that the informationoptimum channel quantizer is fully symmetric [19]. Typically, the resolution of the analog-to-digital converter (ADC) is a power of two and thus even. In this case, the LLR=0 can not be represented properly. Usually the quantization boundaries are then shifted to be able to represent LLR = 0.
In information bottleneck decoders, LLR representations are ignored. Furthermore, the decoder is designed using density evolution and thus requires the complete knowledge of the statistics of the decoder input. Hence, constructing an information bottleneck decoder for puncturing is far less straightforward than in conventional decoders. In the following we propose a generic extension to include puncturing which leverages the message alignment technique.
Without loss of generality, we consider a variable node with degree d v = 4 which processes one channel message and three messages received from connected check nodes to generate extrinsic information about the underlying code bit. Figure 5 shows this processing as a concatenation of two-input-lookup tables. In Figure 5 each lookup table is depicted as trapezoid with the input vector
T and output t out i . The respective mappings are found using the information bottleneck method. The joint distribution in the first stage, which is processing the input vector
T is computed as follows (See [4] for details.):
Clearly, p(x, [t in ch , t in 1 ] T ) and thus also p(x|t out 1 ), which is used in the next step, depend on the statistics of the quantized observed random variable (T out , P ) relevant random variable X compressed random variable Z I(X; T out , P ) I(T out , P ; Z) p(z|t out , )
Fig. 6. Considering puncturing as message alignment problem, where I(X; Z) is the relevant information and I(Z; T, P ) is the compressed information.
channel output (cf. Section III-A). When incorporating puncturing, p(x, t in ch ) differs depending on whether the variable node is punctured or not. First, we introduce the random variable P with event space ∈{true, false} indicating if a node is punctured or not. In this paper, the puncturing rate indicates the fraction of variable nodes with degree d > 1 that are punctured. In the next section, it will become clear why punctured variable nodes with degree d = 1 are ignored when computing the puncturing rate. As a result, we rewrite (2) as
Due to the concatenation of lookup tables as shown in Figure 5 all subsequent tables depend on P . Consequently, in a straightforward implementation the number of required lookup tables will increase drastically to account for all possible combinations of punctured and non-punctured nodes and their respective degrees. This paper proposes a novel design objective which includes puncturing in the table design. In turn, P and T are considered jointly, i.e., the objective is to find a mapping p(z|t out , ) such that I(X; T out , P ) ≈ I(X; Z). As depicted in Figure 6 the resulting problem is basically a message alignment setup. As a result, one creates the mapping p(z|t out , ) and the meaning p(x|z) such that all subsequently constructed tables do not depend any longer on the node being punctured or not. This approach significantly reduces the number of distinct lookup tables.
PBRL codes can operate close to the theoretical limit for a wide range of code rates [17]. The rate can be easily adapted by puncturing or transmitting the degree-one variables (cf. Figure 2). As a punctured degree-one variable node always conveys an LLR equal to zero to the connected check nodes, these check nodes and thus entire parts of the respective Tanner graph are deactivated [17], meaning that no relevant information propagates from the punctured degreeone nodes towards the inner variable nodes with very high degree (cf. Figure 2). Hence, puncturing degree-one nodes, i.e., deactivating parts of the Tanner graph changes the effective degree distribution λ ef f (z) = λ(z) and ρ ef f (z) = ρ(z). To allow information bottleneck decoders to cope with punctured degree-one nodes and rate-adaptability the effective degree distribution is of crucial importance. To determine the effective degree distribution, the following strategy is proposed:
Variable Node: If an edge carries no information, this would correspond to LLR = 0 in a conventional decoder, the effective node degree seen by the outgoing message is reduced by one.
Check Node: If already one edge which is used to generate extrinsic information contributes no information, i.e., the corresponding LLR = 0, the outgoing message will automatically carry no extrinsic information. Thus, only the fraction of edges over which extrinsic information is passed is considered for each effective degree.
The computations are performed offline given a parity check matrix for every iteration. In Figure 5, we have depicted an unfold variable node. It can be seen that in the general scheme only one tree of lookup tables for the highest node degree in the code has to be constructed. All nodes with smaller degrees can easily reuse the tables. As mentioned above, puncturing degree-one variable nodes reduce the effective degree distribution. However, in the context of the concatenated structure presented in Figure 5, this paper argues that puncturing basically only effects the depth of the lookup tree, because if a message is punctured it would not contribute any relevant information and thus can be skipped. Hence, designing a decoder for the lowest code rate, yields the maximum depth of the lookup tree. Higher code rates will reuse this architecture but require individually optimized tables. It is possible to reuse the same tables for a range of code rates, but this analysis is left to the journal version of this paper due to space limitations.
In this section, we present and discuss results obtained performing frame error rate simulations for an exemplary PBRL LDPC code. The code was taken from [17]. The code has K = 1032 information bits, and is evaluated for various code rates R c range from R c = 1/3 up to R c = 2/3.
We propose to construct all involved lookup tables just once for a fixed design-E b /N 0 . The constructed lookup tables are then stored and applied for all E b /N 0 . Hence, the lookup table construction needs to be done only once and offline.
We consider three reference schemes to compare the performance of our decoder. Decoding of a codeword is stopped after a maximum number of 100 decoding iterations or earlier if the syndrome check is successful. First, we consider a doubleprecision belief propagation decoder with flooding schedule. The received samples are not quantized and the internal operations are additions at the variable node and box-plus at the check node. Second, we use the layered normalized minsum algorithm (NMSA) [20], [21] with 6 bit resolution at the check node and 6 bits at the variable node. Again the inputs to the decoder are not quantized. The operations here are again additions at the variable nodes but the normalized min-sum approximation is used at the check nodes. Third, we use the offset-min-sum decoder with only 4 bit resolution at the check node and 6 bits at the variable node to prevent an overflow when adding the 4 bit messages received from the channel quantizer. Finally, we designed our proposed information bottleneck decoder for a fully 4 bit integer architecture. This means, starting form the channel quantizer which outputs 4 bit integers, the internal messages require only 4 bits and only lookup operations performed. These lookups do not mimic any arithmetic function but realize the relevant-information preserving mappings found using the information bottleneck method.
The most important parameters of the applied decoders are summarized in Table I for a quick overview. First we consider a decoder designed for a fixed rate of R = 0.5. The results are shown in Figure 7. As expected the beliefpropagation (BP) decoder ( -marker) achieves the best frame error rate performance, but at the same time, has the highest computational complexity (cf. Table I). Although all applied operations in the information bottleneck decoder ( -marker) are simple lookups, the decoder performs only less than 0.2 dB worse than the benchmark. The results are even more remarkable when considering the tremendous gap to the offset-
Authorized licensed use limited to: UCLA Library. Downloaded on October 01,2020 at 00:01:23 UTC from IEEE Xplore. Restrictions apply.