# Bit-Error-Rate Analysis of Raptor Codes over Rician Fading Channels

Authors: Jingke Dai
Journal: Journal of Electrical and Computer Engineering
 (2020)

---

## Abstract

The bit-error-rate expressions of nonsystematic Raptor (NR) codes and systematic Raptor (SR) codes over Rician fading channels are first derived using a Gaussian approximation (GA) approach. These BER expressions provide a significant reduction in computational complexity for analyzing system performance when compared with simulation and discretized density evolution (DDE). As shown by the asymptotic analysis, the NR codes originally designed for binary erasure channels still have good performance on Rician fading channels but SR codes do not. Therefore, the degree distributions of SR codes are specifically optimized on Rician channels which are superior to the existing SR codes and comparable to NR codes.


---

## Body

## 1. Introduction

Rateless codes are able to adapt the bit rate without channel state information at the transmitter and then are suitable for variant channels. Luby Transform (LT) codes [1] are the first class of practical rateless codes which are proposed for binary erasure channels (BEC). As an extension of LT codes, the Raptor codes with lower decoding complexity are constructed by serially concatenating inner LT codes with an outer high-rate code [2]. If the original symbols are first transmitted followed by LT-coded symbols, the corresponding rateless codes could be called systematic LT (SLT) codes [3] or systematic Raptor (SR) codes [4].LT codes and Raptor codes have been generalized to noisy channels, such as binary symmetric channels (BSC) [5], additive white Gaussian noise (AWGN) channels [5–8], multiple-access channels [9], and fading channels [10], which have been shown to achieve good decoding performance. The asymptotic analyses of them are normally obtained by discretized density evolution (DDE) [4, 8] and some simplified one-dimensional (1D) analysis methods, e.g., Gaussian approximation with message mean (GA-mean) [3, 6] and extrinsic information transfer (EXIT) chart [7]. By combining those asymptotic analyses with differential evolution algorithm or linear programming (LP) method, the performance of LT codes and Raptor codes can be further improved [6–8]. As is well known, the DDE provides an accurate result but has high complexity, while those 1D methods sacrifice reasonable accuracy for much faster calculation. In addition, the lower bounds of bit-error-rate (BER) for LT codes and low-density generator-matrix (LDGM) codes are analyzed based on GA-mean [3], EXIT [7], and DDE [11], respectively, which match the corresponding asymptotic performance very well at high signal-to-noise ratio (SNR) but significant discrepancy occurs at low SNR.Meanwhile, most of the above literature studies with asymptotic analysis concentrate on BEC or AWGN channels, and the performance of LT/Raptor codes on fading channels is usually obtained by computer simulations [10, 12–15]. Among them, the study in [10] reveals that the rateless coding scheme has advantages in efficiency and reliability over fixed-rate codes when channels information is not available and provides the simulated performance of Raptor codes on Rayleigh fading channels. The simulation results in [12] show that the Raptor codes can closely approach the capacity limits of both Rayleigh fading channels and Rician fading channels.Recently, based on a modified GA method, the bit-error-rate of systematic Raptor codes on Rayleigh/Nakagami fading channels has been derived in [16], providing a way of asymptotic analysis for Raptor codes on fading channels. We extend the work of [16] to nonsystematic Raptor codes and Rician channels. First, the BER expressions of both NR codes and SR codes are derived on Rician channels. Comparisons among simulation, DDE analysis, and the proposed analytical BER demonstrate that they are in good agreement and our analytical expression has a significant reduction in computation complexity compared to DDE analysis. In addition, the asymptotic results show that the decoding thresholds of NR codes are very close to the Shannon-limits though the employed degree distribution is originally designed for BEC. Second, the SR codes with the distribution designed for NR codes are prone to poor performance; hence, the proposed BER expression is combined with LP method to search good degree distributions for SR codes. The simulation results indicate that the optimized SR codes have BER performance as good as NR codes and outperform existing SR codes which are specifically designed on AWGN channels.


## 2. Encoding and Decoding

The coded BPSK symbols from transmitter are mapped asx∈1,−1 and then the received symbols are given by(1)y=a⋅x+n,where n is a Gaussian variable with zero-mean and variance σ2 and the fading factor a is Rician distributed with the probability density function (PDF) as [12](2)pa=2a1+γexp−a21+γ−γI02aγ1+γ,where γ is called a Rician factor and I0x is the zeroth-order modified Bessel function of the first kind. The channel side information is assumed as known and then the log-likelihood ratio (LLR) provided for decoder is calculated as(3)z=logPx=1y,aPx=−1y,a=2σ2y⋅a.Raptor encoding is a two-stage process. The original information sequence of lengthK is precoded using a high-rate (LDPC) code to produce the intermediate sequence of length K′. This intermediate sequence is further LT-encoded to produce the output of Raptor code. Here LT code is the inner code, which can be described by its output degree distribution Ωx=∑j=1drΩjxj. The integer dr is the maximum degree and Ωj denotes the probability that degree j is chosen in the random XOR-encoding process [3]. If the NR codes are taken, the generation matrix of inner nonsystematic LT (NLT) codes is G=GLT, where GLT is a matrix of size K′×N constructed according to Ωx and N is the actual number of LT-coded symbols. If the SR codes are taken, the generation matrix is constructed by G=IK′GLT, where IK′ is an identity matrix of size K′×K′ and GLT is of size K′×N−K′. The actual rates of inner codes, outer codes, and whole codes are denoted as Rin=K′/N, Rout=K/K′, and R=K/N, respectively.Raptor decoding is also divided into two steps for inner and outer decoding, respectively. Firstly, the classic sum-product algorithm (SPA) is employed to decode inner code, which is based on matrixGLTT, the transpose of GLT, for both NLT codes and SLT codes. Each column and each row of GLTT correspond to the variable node (VN) and check node (CN) of the decoding bipartite graph. The messages are updated between VNs and CNs as follows [3, 12]:(4)NLT code:un−>ml=2tanh−1tanhzn2∏k∈Sn\mtanhvk−>nl−12,(5)vm−>nl=∑k∈Sm\nuk−>ml,(6)SLT code:un−>ml=2tanh−1tanhzn+K′2∏k∈Sn\mtanhvk−>nl−12,(7)vm−>nl=zm+∑k∈Sm\nuk−>ml,where un−>ml is the message passed from the n-th check node to the m-th variable node at the l-th decoding iteration and vm−>nl+1 is the message passed in the opposite direction, The set of all neighbors of n-th node except for the m-th node is denoted by Sn\m.When the iteration achieves the maximum numberlmax, the inner decoder outputs the soft information vmlmax=∑k∈Smuk−>mlmax (NLT) or vmlmax=zm+∑k∈Smuk−>mlmax (SLT) as the initial message provided to outer decoder. The outer (LDPC) code is also decoded by SPA, the detail of which is found in [12] and is not presented here.


## 3. BER Analysis of NR Codes

To analyze the BER of NR codes, some notations are predefined as follows. The edge degree distribution of CNs is calculated by their node degree distributionΩx as given by ωx=∑j=1drωjxj−1=Ω′x/Ω′1 and the average degree of CNs is β=Ω′1. The average degree of VNs is denoted by α and the variable node and edge degrees are both assumed to be Poisson distributed as Λx=eαx−1 and λx=eαx−1, respectively. They can also be truncated to obtain polynomials as Λx=∑i=1dlΛiαxi and λx=∑i=1dlλiαxi−1, where dl is large enough to ensure Λ1≈1 and Λiα=λiα=αie−α/i!.If all-zero codewords are transmitted [3], the initial LLR has the following conditional PDF as [16](8)pza=σ2a2πexp−z−2a2/σ228a2/σ2.Combining with (2), we have the unconditional PDF(9)pzz=1+γσ2πexpz2−γ∫0∞exp−σ2z28x2−12σ2+1+γx2I02xγ1+γdx,and the corresponding initial BER before decoding is calculated as(10)P0=Pz<0=∫−∞0pzzdz.First, the inner NLT decoding is considered. We denote the error probabilityPe,inl−1 at iteration l−1 as the average probability that the VNs messages are negative and uj as the check nodes with degree j. According to (4), the probability of uj<0 at iteration l is derived as(11)Pluj<0=P∏k=1j−1vk>0Pz<0+P∏k=1j−1vk<0Pz>0=121+1−2Pe,inl−1j−1Pz<0+121−1−2Pe,inl−1j−11−Pz<0=121−1−2Pe,inl−1j−1+21−2Pe,inl−1j−1Pz<0,where the VNs messages vk are assumed to be i.i.d. Note that uj is assumed to be symmetric Gaussian distributed. Denoting mu,jl as the mean of uj, we get the following equation:(12)Qmu,jl2=Pluj<0,where function Qx=1/2π∫x+∞e−t2/2dt. By averaging over all the possible check node degrees, the mean of message by check nodes is(13)mul=∑j=1drωjmu,jl=∑j=1dr2ωjQ−1Pluj<02.The VN of degreei outputs a Gaussian message with mean(14)mv,il=i−1mul,as well as variance 2mv,il; thus, the conditional BER is(15)Plvi<0=Qi−1mul2.By averaging over all the possible variable node degrees, we have the BER as given by(16)Pe,inl=∑i=1dlλiPlvi<0=∑i=1dlλiQi−1∑j=1dc2ωjQ−11/21−1−2Pe,inl−1j−1+21−2Pe,inl−1j−1P022.Note thatPe,inl is the function of Pe,inl−1.At the iterationlmax, the message provided from inner decoder to outer decoder can be assumed to be Gaussian distributed [8] with the mean and variance as(17)mouter=2Q−1Pe,inlmax2,σouter2=4Q−1Pe,inlmax2.Since the initial message for outer decoder is Gaussian distributed, the EXIT chart technique can be employed to track the message in decoding iterations. The mutual information from check nodes at thel-th iteration is updated by [16](18)IECl=∑j=1dcρj1−Jj−1J−11−∑i=1dvγiJσouter2+i−1J−1IECl−122,where γx=∑i=1dvγixi−1 and ρx=∑j=1dcρjxj−1 are the edge degree distributions of variable nodes and check nodes of outer LDPC codes, dv and dc are the corresponding maximum degrees, and the function Jσ is defined in [17].At the maximum iteration, the BER of Raptor code is calculated by(19)Pelmax=∑i=1dvΓiQσouter2+iJ−1Io,E,Clmax24,where Γx=∑i=1dvΓixi−1 denotes the variable node degree distribution of outer LDPC codes.


## 4. BER Analysis of SR Codes

From equations (4)–(7), we know the SLT decoding is very similar to NLT decoding and then the BER analysis of SR codes is also like that of NR codes. However, in (5), the message from VNs is the sum of LLR from CNs, whereas, in (7), the message from VNs is the sum of LLR from CNs and initial LLR from channel. Hence, the process of VNs for SLT codes is a little different from NLT codes.Since the message from check nodes is assumed to be Gaussian distributed, the sum of them at the variable nodes with degreei is also Gaussian distributed (see (14)) with the PDF as(20)pu−>vlv=14πmv,ilexp−v−mv,il24mv,il.Therefore, the PDF of message from VNs with degreei is the convolution of (9) and (20) as given by(21)pv,il=pzv∗pu−>vlv,and the corresponding average BER is calculated as(22)Pe,inl=∑i=1dlλi∫−∞0pzv∗pu−>vlvdv.As the outer decoding is the same as that in NR codes, the BER of SR codes is also calculated by (19), only needing to substitute (22) for (16) in advance. Note that the convolution in (22) is easily obtained by Fast Fourier Transform (FFT).We define the decoding overhead asε=N/K′=1/Rin. The outer codes are set as the 0.98-rate (4,200)-regular LDPC code and the 0.80-rate (4,20)-regular LDPC code, respectively. The degree distributions of inner codes for both NR codes and SR codes take the optimized result in [2], which is rewritten as(23)Ω0x=0.007969x+0.493570x2+0.166220x3+0.072646x4+0.082558x5+0.056058x8+0.037229x9+0.055590x19+0.025023x65+0.003135x66.In Figures1 and 2, the BER of NR codes and SR codes obtained by (19) are compared with the simulation results with information length K=10000, which are indicated as “Analytical” and “Simulation,” respectively. Furthermore, decoding threshold achieved by DDE and Shannon-limit are also depicted in those figures. Note that the Shannon-limit here is calculated by Rout/Cγ,σ2, where Cγ,σ2 is the capacity of Rician channel with fading factor γ and noise variance σ2. It can be seen that the analytical curves closely match the simulated results at high overhead region. Generally, at the BER of 10−5, the difference between the simulated overhead and the analytical threshold of error-free decoding is around 0.03–0.15 for all the BER curves. For example, we observe from Figure 1(a) that the simulated overhead to BER of 10−5 is around 2.41, whereas the analytical threshold is 2.31, which has a difference of 0.10. The performance of NR codes is much better than the SR codes, since the employed degree distribution of inner codes is originally designed for NR codes, though on binary erasure channel. In fact, the decoding threshold of NR codes is very close to the corresponding channel capacity. For example, in Figure 2(a), the DDE-threshold of NR codes is 1.73, the gap of which to Shannon-limit is only 0.07. The above results show that the NR codes have good robustness on different classes of channels and then the performance improvement space is limited (also see [8]), whereas the SR codes require careful design for specific channels.Figure 1
Analytical and simulated BER of Raptor codes on Rician channel withγ=10 and σ2=1. (a) Rout=0.98; (b) Rout=0.80.
(a)(b)Figure 2
Analytical and simulated BER of Raptor codes on Rician channel withγ=1 and σ2=0.5. (a) Rout=0.98; (b) Rout=0.80.
(a)(b)From Figures1(b) and 2(b), the simulation results of Raptor codes with outer rate of 0.80 are similar to the ones with outer rate of 0.98; only the overheads of former codes are smaller than the corresponding later codes. But it does not mean the codes with outer rate of 0.80 are better than the codes with outer rate of 0.98 because their performance should be evaluated by the whole rates at this time. For example, the overhead thresholds of NR codes in Figures 1(a) and 1(b) are 2.22 and 2.17, respectively, but the whole rates of them are around 0.441 and 0.369, respectively. In fact, we observe that the codes with outer rate of 0.80 have gaps between Shannon-limit and decoding threshold which are much larger than the gaps of codes with outer rate of 0.98, indicating that the outer rate should be set higher (e.g., ≥0.95).


## 5. Optimization of SR Codes

The degree distribution of inner codes of SR codes is normally optimized by linear programming, which is presented as(24)Min∑j=1drωjj,(25)s.t.Pe,inl+1<Pe,inl,l=0,…,L−1,(26)∑j=1drωj=1,(27)ωj≥0,j=1,…,dc.In this design model, the objective is minimizing inner code’s overhead, which is calculated byε=N/K′=α/β+1=α∑j=1drωj/j+1 in (24), and equations (26) and (27) ensure the validity of the distributions. Note that α is predefined. Pe,inl+1 in (25) is obtained by (22) and Pe,inl is chosen from L points in the interval Pe,target,P0, where L is an integer indicating the number of sampling points, P0 is the initial error probability given by (10), and Pe,target is the target error probability, usually set as the desired BER for successful decoding of outer LDPC codes [16].Setting differentγ and σ2, the optimized degree distributions of inner SLT codes are shown in Table 1. The BER performance of SR codes with those optimized degree distributions is compared with that of the NR codes and SR codes with existing degree distributions. Besides the distribution Ω0x, the optimized distribution on AWGN channel for rate-1/2 SR codes in [4] is also considered and denoted as Ω1x. The 0.98-rate (4,200)-regular LDPC code is fixed as the outer code and the iteration number in SPA is set to 100 for both inner codes and outer codes. All the codes have the same information length as K=10000.Table 1
Optimized distributions of inner SLT codes on Rician channels.
γ=10,σ2=1γ=10,σ2=0.5γ=1,σ2=1γ=1,σ2=0.5Ωopt1xΩopt2xΩopt3xΩopt4xα=12.5α=8.5α=15α=11Ω40.39338Ω70.12848Ω40.75880Ω50.17517Ω50.45979Ω80.77037Ω50.08967Ω60.69037Ω250.10970Ω480.01474Ω230.12561Ω320.02886Ω260.00593Ω1000.08641Ω700.00918Ω330.05380Ω830.01884Ω710.01674Ω1000.05180Ω840.01236The simulation results of those Raptor codes on Rician channels are shown in Figures3 and 4. It is seen that the optimized SR codes indeed outperform the SR codes with existing distributions and the performance is very close to that of NR codes on all the considered channels, which indicates the effectiveness of our analysis and optimization method. For example, on the channel with γ=10 and σ2=1, the required overheads for NR codes and optimized SR codes achieving BER below 10−5 are both 2.45. The maximum difference between NR codes and optimized SR codes occurs on the channel with γ=10 and σ2=0.5, and the overhead gap is only 0.03. Although the performance of optimized SR codes does not exceed that of NR codes, the good features of systematic codes should be considered, such as visible information bit, convenience of error checking, and smaller decoding matrix. The SR codes with Ω1x have moderate performance on Rician channel when γ=10 but have poor performance when γ=1 because of being originally designed for AWGN channel, where the distribution of initial LLR is more like the one in former case. In addition, it should be noted that all the optimized SR codes are designed under specific channel conditions (γ and σ2), and their performance would be degraded if the channel changes; that is, the SR codes are prone to be affected by the channel when compared with NR codes.Figure 3
Simulated BER of Raptor codes on Rician channel withγ=10. (a) σ2=1; (b) σ2=0.5.
(a)(b)Figure 4
Simulated BER of Raptor codes on Rician channel withγ=1. (a) σ2=1; (b) σ2=0.5.
(a)(b)


## 6. Conclusions

The BER expressions of nonsystematic Raptor codes and systematic Raptor codes on Rician fading channels have been derived using GA approach. The simulation results are in good agreement with the analytical results; thus the BER expressions provide a computationally efficient way of analyzing BER performance and predicting the overhead threshold with reasonable accuracy. With the existing degree distributions, NR codes still have Shannon-limit approaching performance on Rician channels but SR codes have poor performance. The proposed analytical expression is combined with linear programming to search good degree distributions for SR codes and the simulation results indicate that the optimized SR codes have BER performance as good as NR codes.



---

*Source: 2685075-2020-06-08.xml*