# Upper Bound on the Bit Error Probability of Systematic Binary Linear Codes via Their Weight Spectra

Authors: Jia Liu; Mingyu Zhang; Chaoyong Wang; Rongjun Chen; Xiaofeng An; Yufei Wang
Journal: Discrete Dynamics in Nature and Society
 (2020)

---

## Abstract

In this paper, upper bound on the probability of maximuma posteriori (MAP) decoding error for systematic binary linear codes over additive white Gaussian noise (AWGN) channels is proposed. The proposed bound on the bit error probability is derived with the framework of Gallager’s first bounding technique (GFBT), where the Gallager region is defined to be an irregular high-dimensional geometry by using a list decoding algorithm. The proposed bound on the bit error probability requires only the knowledge of weight spectra, which is helpful when the input-output weight enumerating function (IOWEF) is not available. Numerical results show that the proposed bound on the bit error probability matches well with the maximum-likelihood (ML) decoding simulation approach especially in the high signal-to-noise ratio (SNR) region, which is better than the recently proposed Ma bound.


---

## Body

## 1. Introduction

Upper bounds on the maximuma posteriori (MAP) decoding error probability, as a key technique for evaluating the performance of the binary linear codes over additive white Gaussian noise (AWGN) channels, bring a profound impact on the reliable transmission of the next-generation mobile communication systems since they can be used to not only predict the performance without resorting to computer simulations but also guide the design of coding [1]. In order to improve the looseness of the union bound in the low signal-to-noise ratio (SNR) region, many improved upper bounds, on the bit error probability [2–5] and on the frame error probability [2–4, 6–15], are proposed. As surveyed in [1], the improved upper bounds on the bit error probability [2–4] are based on Gallager’s first bounding technique (GFBT):(1)PrEb=PrEb,y¯∈ℛ+PrEb,y¯∉ℛ,(2)≤PrEb,y¯∈ℛ+Pry¯∉ℛ,in which Eb denotes the event that represents an error in one of the information bits of the decoded codeword, y¯ denotes the received signal vector, and ℛ denotes an arbitrary region around the transmitted signal vector (called the Gallager region). Divsalar [2] chose the region ℛ to be an Euclidean sphere centered at the point along the line connecting the origin to the transmitted signal vector. Sason and Shamai [3] chose the region ℛ to be a circular cone whose central line passes through the origin and the transmitted signal vector. The upper bounds [2, 3] on the bit error probability based on equation (2) can be considered to be simply replaced by the weight spectra Ad,1≤d≤n in the upper bound on the frame error probability by(3)Ad∗≜∑i=0kikAi,d,1≤d≤n,where Ai,d denotes the number of code words of Hamming weight d encoded by information bits of Hamming weight i and k denotes the dimension of the linear code. However, as noted by Zangl and Herzog [4], computing the expression Pry¯∉ℛ by the factor 1.0 in (2) means that the worst case of k bit errors is assumed if y¯ falls outside the good region ℛ, and then Zangl and Herzog [4] improved the tangential-sphere bound (TSB) on the bit error probability [3] by computing this probability in a more accurate way. The upper bounds on the bit error probability [2–4] require the whole input-output weight enumerating function (IOWEF), which can be applied to both systematic codes and nonsystematic codes. The upper bound on the bit error probability by Ma et al. [16] can be evaluated by calculating partial IOWEF with truncated information weight (Ai,d,0≤i≤T,0≤d≤n−k+T, where T≥0 is a positive integer), which holds only for systematic codes. However, for most codes, the IOWEF is usually not computable. In contrast, it is reasonable to assume that the weight spectra Ad,0≤d≤n of codes are available, such as the BCH code [17]. In this paper, different from most of the existing bounds, we derive a tighter upper bound on the bit error probability of systematic binary linear codes via their weight spectra.The main results as well as the structure of this paper are summarized as follows:(1)
In Section2, we present the preliminaries and necessary notation. The conventional union bound and four reported upper bounds based on GFBT are also reviewed in Section 2.(2)
In Section3, in a detailed way, we rederive the recently proposed bound on the bit error probability by Liu [5], in which the union bound is firstly truncated and then amended for the systematic linear codes over AWGN channels. In this paper, the proposed upper bound on the bit error probability is derived in a much more detailed way by considering more information of the Gallager region ℛ and the truncated IOWEF of the code. Finally, with the framework of GFBT, we derive the upper bound on the bit error probability which requires only the knowledge of weight spectra of the code.(3)
In Section4, numerical examples are given to show that the proposed bound is helpful to evaluate the performance of the systematic binary linear codes which can predict the performance of the code in the high-SNR region, avoiding the time-consuming computer simulations.(4)
Section5 concludes this paper.


## 2. Preliminaries

LetF2=0,1 be the binary field. Let Cn,k be a systematic binary linear block code of dimension k and length n with a generator matrix G = [Ik, P], where Ik is the k×k identity matrix. Let u¯∈F2k be the information vector and c¯∈F2n be the associated codeword. We have the encoding function as follows:(4)u¯⟶c¯=u¯G.Considering the binary phase shift keying (BPSK) mapping, we havec¯⟶s¯ by st=1−2ct for 0≤t≤n−1. Suppose that s¯ is transmitted over an AWGN channel. Let y¯=s¯+z¯ be the received vector, where z¯ is a vector of independent Gaussian random variables with zero mean and variance σ2. We have the decoding function as follows:(5)y¯⟶u¯^.Without loss of generality, assume that the all-zero codewordc¯0 is transmitted. The conventional union bound and four reported upper bounds based on GFBT are also reviewed in the following sections.


### 2.1. Union Bound

The simplest upper bound on the bit error probability is the union bound:(6)PrEb≤∑i=1kik∑d=1nPrEbi,d≤∑i=1kik∑d=1nAi,dQdσ,where Ebi,d is the event that there exists at least one codeword of Hamming weight d encoded by information bits of Hamming weight i that is nearer than c¯0 to y¯, and Qd/σ is the pairwise error probability with(7)Qx≜∫x+∞12πe−z2/2dz.However, the above conventional union bound is loose and even diverges≥1 in the low-SNR region. Then, the improved upper bounds on the bit error probability based on GFBT were proposed, such as the Divsalar bound [2], the tangential-sphere bound (TSB) [3], the improved tangential-sphere bound (ITSB) [4], and the Ma bound [16].


### 2.2. The Divsalar Bound

In 1999, Divsalar derived a simple upper bound [2] on the bit error probability based on GFBT, where the region ℛ is chosen to be an n-dimensional sphere centered at a scaled transmitted signal vector. Both the radius and the center of the sphere can be optimized. Let dmin denote the minimum Hamming weight. Taking into account the definition of Ad∗ in (3), we have the Divsalar bound on the bit error probability:(8)Pb≤∑d=dminn−k+1mine−nEbδ,β,γ,Ad∗Q2dγ,where(9)Ebδ,β,γ=−rbδ+12lnβ+1−βe2rbδ+βγδ1−1−βδ,γ=12σ2,δ=dn,rbδ=lnAd∗n,β=γ1−δδ21−e−2rbδ+1−δδ21+γ2−1−1−δδ1+γ.


### 2.3. The Tangential-Sphere Bound

In 2000, Sason and Shamai [3] derived the tangential-sphere bound on the bit error probability based on GFBT, where the region ℛ is chosen to be an n-dimensional circular cone whose central line passes through the origin O and the transmitted signal. Let(10)γ¯a,x=1Γa∫0xta−1e−tdt,a>0,x≥0,denote the normalized incomplete gamma function. Taking into account the definition of Ad∗ in (3), we have the TSB with a parameter r on the bit error probability:(11)Pb=∫−∞+∞Pbz112πσe−z12/2σ2dz1,where(12)Pbz1≤∑d:δd/2<αdAd∗∫βdz1rz1e−z22/2σ22πσγ¯n−22,rz12−z222σ2dz2+1−γ¯n−12,rz122σ2,δd=2d,αd=r1−δd24n,rz1=r1−z1n,βdz1=rz1dr1−d/n.The parameterr in the TSB can be optimized by a numerical solution of the following equation:(13)∑d:δd/2<αdAd∗∫0θdsinn−3ϕdϕ=πΓn−2/2Γn−1/2,where(14)θd=arccosδd2r1−δd2/4n.


### 2.4. The Improved Tangential-Sphere Bound

In 2001, Zangl and Herzog [4] derived the improved tangential-sphere bound on the bit error probability based on GFBT by computing the expression Pry¯∉ℛ in a more accurate way. We have the ITSB with a parameter rΨ on the bit error probability:(15)Pb≤∫−∞+∞∑d:δd/2<αdAdg¯dkγ¯n−22,rz12−βd2z12σ2⋅Qβdz1σ−Qrz1σ+maxg¯0,…,g¯optk⋅γ¯n−12,βdopt+12z12σ2∑d=dopt+1nmaxg¯0,…,g¯d−1−maxg¯0,…,g¯dk⋅γ¯n−12,rz122σ2+maxg¯0,…,g¯nk⋅12πσe−z12/2σ2dz1.The parameterrΨ in the ITSB can be optimized by a numerical solution of the following equation:(16)∑d:δd/2<αdAdg¯dk∫0θdsinn−3ϕdϕ=maxg¯0,…,g¯optk⋅πΓn−2/2Γn−1/2,where(17)θd=arccosδd2rΨ1−δd2/4n.


### 2.5. The Ma Bound

In 2018, Ma et al. [16] derived the upper bound on the bit error probability under maximum a posteriori (MAP) decoding. The Ma bound can be evaluated by calculating partial IOWEF with truncated information weight. We have the Ma bound with a parameter r∗ on the bit error probability(18)BERMAP≤min0≤r∗≤T/2∑i≤2r∗ik∑dAi,dQdσ+∑i=r∗+1kmini+r∗,kkkipbi1−pbk−i,where(19)pb=Q1σ.


## 2.1. Union Bound

The simplest upper bound on the bit error probability is the union bound:(6)PrEb≤∑i=1kik∑d=1nPrEbi,d≤∑i=1kik∑d=1nAi,dQdσ,where Ebi,d is the event that there exists at least one codeword of Hamming weight d encoded by information bits of Hamming weight i that is nearer than c¯0 to y¯, and Qd/σ is the pairwise error probability with(7)Qx≜∫x+∞12πe−z2/2dz.However, the above conventional union bound is loose and even diverges≥1 in the low-SNR region. Then, the improved upper bounds on the bit error probability based on GFBT were proposed, such as the Divsalar bound [2], the tangential-sphere bound (TSB) [3], the improved tangential-sphere bound (ITSB) [4], and the Ma bound [16].


## 2.2. The Divsalar Bound

In 1999, Divsalar derived a simple upper bound [2] on the bit error probability based on GFBT, where the region ℛ is chosen to be an n-dimensional sphere centered at a scaled transmitted signal vector. Both the radius and the center of the sphere can be optimized. Let dmin denote the minimum Hamming weight. Taking into account the definition of Ad∗ in (3), we have the Divsalar bound on the bit error probability:(8)Pb≤∑d=dminn−k+1mine−nEbδ,β,γ,Ad∗Q2dγ,where(9)Ebδ,β,γ=−rbδ+12lnβ+1−βe2rbδ+βγδ1−1−βδ,γ=12σ2,δ=dn,rbδ=lnAd∗n,β=γ1−δδ21−e−2rbδ+1−δδ21+γ2−1−1−δδ1+γ.


## 2.3. The Tangential-Sphere Bound

In 2000, Sason and Shamai [3] derived the tangential-sphere bound on the bit error probability based on GFBT, where the region ℛ is chosen to be an n-dimensional circular cone whose central line passes through the origin O and the transmitted signal. Let(10)γ¯a,x=1Γa∫0xta−1e−tdt,a>0,x≥0,denote the normalized incomplete gamma function. Taking into account the definition of Ad∗ in (3), we have the TSB with a parameter r on the bit error probability:(11)Pb=∫−∞+∞Pbz112πσe−z12/2σ2dz1,where(12)Pbz1≤∑d:δd/2<αdAd∗∫βdz1rz1e−z22/2σ22πσγ¯n−22,rz12−z222σ2dz2+1−γ¯n−12,rz122σ2,δd=2d,αd=r1−δd24n,rz1=r1−z1n,βdz1=rz1dr1−d/n.The parameterr in the TSB can be optimized by a numerical solution of the following equation:(13)∑d:δd/2<αdAd∗∫0θdsinn−3ϕdϕ=πΓn−2/2Γn−1/2,where(14)θd=arccosδd2r1−δd2/4n.


## 2.4. The Improved Tangential-Sphere Bound

In 2001, Zangl and Herzog [4] derived the improved tangential-sphere bound on the bit error probability based on GFBT by computing the expression Pry¯∉ℛ in a more accurate way. We have the ITSB with a parameter rΨ on the bit error probability:(15)Pb≤∫−∞+∞∑d:δd/2<αdAdg¯dkγ¯n−22,rz12−βd2z12σ2⋅Qβdz1σ−Qrz1σ+maxg¯0,…,g¯optk⋅γ¯n−12,βdopt+12z12σ2∑d=dopt+1nmaxg¯0,…,g¯d−1−maxg¯0,…,g¯dk⋅γ¯n−12,rz122σ2+maxg¯0,…,g¯nk⋅12πσe−z12/2σ2dz1.The parameterrΨ in the ITSB can be optimized by a numerical solution of the following equation:(16)∑d:δd/2<αdAdg¯dk∫0θdsinn−3ϕdϕ=maxg¯0,…,g¯optk⋅πΓn−2/2Γn−1/2,where(17)θd=arccosδd2rΨ1−δd2/4n.


## 2.5. The Ma Bound

In 2018, Ma et al. [16] derived the upper bound on the bit error probability under maximum a posteriori (MAP) decoding. The Ma bound can be evaluated by calculating partial IOWEF with truncated information weight. We have the Ma bound with a parameter r∗ on the bit error probability(18)BERMAP≤min0≤r∗≤T/2∑i≤2r∗ik∑dAi,dQdσ+∑i=r∗+1kmini+r∗,kkkipbi1−pbk−i,where(19)pb=Q1σ.


## 3. Upper Bound on the Bit Error Probability Based on GFBT

### 3.1. The Gallager Regionℛ

We define the regionℛ by the Hamming distance based on a list decoding algorithm which is shown in Figure 1, resulting in an irregular high-dimensional geometry (Algorithm 1).Figure 1
Graphical illustrations of the decoding error events. (a) The error event that the all-zero sequenceu¯0 is not in the list. (b) The error event that the all-zero sequence u¯0 is in the list but not the closest one.
(a)
(b)Algorithm 1:A list decoding algorithm.
(1)
We denote
y¯≜y¯0k−1y¯kn−1
in which
y¯0k−1=y0⋯yk−1︸k
and
y¯kn−1=yk⋯yn−1︸n−k
Make hard decisions on the information party¯0k−1=y0⋯yk−1︸k of the received vector y¯, resulting in a vector y¯^0k−1=y^0⋯y^k−1︸k of length k. Then, the channel becomes a memoryless binary symmetric channel (BSC) with cross probability
pb≜Q1/σ
(2)
List all sequences of lengthk within the Hamming sphere with center at y¯^0k−1 of radius r∗, where r∗ is a positive integer. The resulting list is denoted as ℒy¯.
(3)
Encode each sequence inℒy¯ by the encoding algorithm of the systematic code, resulting in a list of code words, denoted as ℒc¯.
(4)
Find the codewordc¯∗∈ℒc¯ that is closest to y¯. Output the information part u¯^ of c¯∗ as the decoding result.The list decoding algorithm is similar to but different from the algorithm presented in [14]. The list region in [14] is an n-dimensional Hamming sphere with center at the hard decision of the whole received sequence, while the list region here is a k-dimensional Hamming sphere with center at the hard decision of the information part of the received sequence.The Gallager regionℛ can be defined by(20)ℛ≜y¯u¯0∈ℒy¯=y¯WHy¯^0k−1≤r∗.


### 3.2. Upper Bound on the Bit Error Probability via IOWEF

We assume thatAi,d≥1 and denote all the code words of Hamming weight d encoded by information bits of Hamming weight i by c¯ℓ, 1≤ℓ≤Ai,d. Let E0⟶ℓ be the event that c¯ℓ is nearer than c¯0 to y¯.With the framework of GFBT, we have(21)PrEb=PrEb,y¯∈ℛ+PrEb,y¯∉ℛ.As shown in Figure1(b), we have(22)PrEb,y¯∈ℛ≤∑i=12r∗ik∑d=1nPrEbi,d,y¯∈ℛ,(23)≤∑i=12r∗ik∑d=1nAi,dPrE0⟶1,y¯∈ℛ.As shown in Figure1(a), we have(24)PrEb,y¯∉ℛ≤∑i=r∗+1kmini+r∗,kkkipbi1−pbk−i,which means that the decoder outputs at most i+r∗ erroneous bits.Assuming a binary vector of total lengthNt passes through a BSC with cross error probability p, we denote Bp,Nt,Nℓ,Nu to be the probability that the number of bit errors occurring ranges from Nℓ to Nu, that is,(25)Bp,Nt,Nℓ,Nu≜∑m=NℓNuNtmpm1−pNt−m.Then, we define(26)Cr,p,Nt,Nℓ,Nu≜∑m=NℓNuminm+r,NtNtNtmpm1−pNt−m.Theorem 1.
We have the upper bound on the bit error probability of systematic binary linear codes under MAP decoding(27)PrEb≤min0≤r∗≤k∑i=12r∗ik∑d=1nAi,dQdσBpb,k−i,0,r−i2+Cr∗,pb,k,r∗+1,k.Proof.
Without loss of generality, we denote(28)c¯1≜1⋯1︸i0⋯0︸k−i1⋯1︸d−i0⋯0︸n−k−d+i,y^0k−1≜1⋯1︸i10⋯0︸i−i11⋯1︸i20⋯0︸k−i−i2.
Notice that a necessary condition for the eventE0⟶1 is that the corresponding input information sequence of the codeword c¯1 is in the list ℒy¯. Hence,(29)WHc¯01k−1−y^¯0k−1≤r∗.
We have(30)i−i1+i2≤r∗.
Also notice that, fory¯∈ℛ,(31)WHy^¯0k−1≤r∗.
We have(32)i1+i2≤r∗.
By combining (30) and (32), we can verify that(33)i2≤r∗−i2.
By the union bounds, we have(34)PrE0⟶1,y¯∈ℛ=PrE0⟶1,WHy^¯0k−1≤r∗≤∑i2=1r∗PrE0⟶1,WHy^¯0i−1≤r∗−i2,WHy^¯ik−1=i2≤∑i2=1r∗PrE0⟶1,WHy^¯ik−1=i2=∑i2=1r∗−i/2PrE0⟶1,WHy^¯ik−1=i2,for i2≤r∗−i/2 from (33).
Since the eventPrE0⟶1 is independent of y^¯ik−1 and PrE0⟶1=Qd/σ, we have(35)∑i2=1r∗−i/2PrE0⟶1,WHy^ik−1=i2,(36)=∑i2=1r∗−i/2PrE0⟶1PrWHy^ik−1=i2,(37)=PrE0⟶1∑i2=1r∗−i/2PrWHy^ik−1=i2,(38)=QdσBpb,k−i,0,r∗−i2.
Then, by substituting (38) in (23), we have(39)PrEb,y¯∈ℛ≤∑i=12r∗ik∑d=1nAi,dQdσBpb,k−i,0,r∗−i2.
Therefore, it can be verified by substituting (24) and (39) in (1) to complete the proof.Corollary 1.
The proposed upper bound on the bit error probability (Theorem1) can improve the conventional union bound on the bit error probability.Proof.
As to the proposed bound (Theorem1), note that(40)Cr∗,pb,k,r∗+1,k=0,by setting(41)r∗=k.
we have(42)PrEb≤∑i=1kik∑d=1nAi,dQdσBpb,k−i,0,r∗−i2≤∑i=1kik∑d=1nAi,dQdσ.
SinceBpb,k−i,0,r∗−i/2≤1, the proof is completed.Corollary 2.
The proposed upper bound on the bit error probability (Theorem1) can improve the Ma bound on the bit error probability (18).Proof.
Assuming that we know only partial IOWEF with truncated information weightAi,d,0≤i≤T,0≤d≤n−k+T, the parameter r∗ in the proposed bound (Theorem 1) is optimized in the interval 0,T/2. Theorem 1 can be written as(43)PrEb≤min0≤r∗≤T/2∑i=12r∗ik∑d=1nAi,dQdσBpb,k−i,0,r−i2+Cr∗,pb,k,r∗+1,k.
SinceBpb,k−i,0,r−i/2 is the probability that the number of bit errors occurring in a binary vector of total length k−i, when passing through a BSC with cross error probability pb, it ranges from 0 to r−i/2. Then, it can be verified by(44)Bpb,k−i,0,r∗−i2≤1,to complete the proof.The objective of this paper is to derive the upper bound on bit error probability with only knowing of the weight spectrum.


### 3.3. Upper Bound on the Bit Error Probability via Weight Spectra

In this section, we focus on how to derive the upper bound on the bit error probability via weight spectra. The IOWEF is usually not computable, but the weight spectraAd,0≤d≤n of the code are usually available, such as the BCH code [17]. Let T≥0 be a positive integer that is relatively small. Assuming that we know only the truncated IOWEF {Ai,d, 0≤i≤T, 0≤d≤n−k+T} which can be obtained by using a brute-force method and the weight spectrum Ad,0≤d≤n.Define(45)Ad′=Ad−∑i=1TAi,d,for 0≤d≤n.Then, we focus on how to obtain the upper bound on the bit error probability by using the IOWEF {Ai,d, 0≤i≤T, 0≤d≤n−k+T} and the weight spectrum Ad,0≤d≤n. We derive the upper bound in the two following cases.Case 1: if the radius of the Hamming spherer∗∈0,T/2 in Figure 1, we can get the IOWEF {Ai,d, 0≤i≤T, 0≤d≤n−k+T} by using a brute-force method, and we have(46)PrEb≤min0≤r∗≤T/2∑i=12r∗ik∑d=1nAi,dQdσBpb,k−i,0,r−i2+Cr∗,pb,k,r∗+1,k,which can be verified by Theorem1.Case 2: if the radius of the Hamming spherer∗∈T/2+1,k in Figure 1, we can derive the upper bound on the bit error probability by employing both the IOWEF {Ai,d, 0≤i≤T, 0≤d≤n−k+T} and the weight spectrum Ad,0≤d≤n.From Theorem1, we have(47)PrEb≤minT/2+1≤r∗≤k∑i=12r∗ik∑d=1nAi,dQdσBpb,k−i,0,r−i2+Cr∗,pb,k,r∗+1,k,in which(48)∑i=12r∗ik∑d=1nAi,dQdσBpb,k−i,0,r∗−i2=∑i=1T∑d=1nikAi,dQdσBpb,k−i,0,r∗−i2+∑i=T+12r∗∑d=1nikAi,dQdσBpb,k−i,0,r∗−i2.Note that(49)∑i=T+12r∗∑d=1nAi,d=∑i=T+12r∗∑d=i2r∗Ai,d+∑i=T+12r∗∑d=2r∗+12r∗+n−kAi,d.Firstly, it is easy to verify that the first term in the right-hand side (RHS) of (49)(50)∑i=T+12r∗∑d=i2r∗Ai,d=∑d=T+12r∗∑i=T+1dAi,d.Since(51)∑i=T+1dAi,d=Ad′,for d∈T+1,2r∗ and i is obviously not greater than mind,k, we have(52)∑i=T+1dikAi,d≤mind,kkAd′.Therefore,(53)∑i=T+12r∗∑d=i2r∗ikAi,dQdσBpb,k−i,0,r∗−i2≤∑d=T+12r∗mind,kkAd′Qdσ,for(54)Bpb,k−i,0,r∗−i2≤1.Secondly, it is easy to verify that the second term in the RHS of (49)(55)∑i=T+12r∗∑d=2r∗+12r∗+N−KAi,d≤∑d=2r∗+12r∗+N−KAd′.Since(56)∑i=T+12r∗Ai,d≤Ad′,for d∈T+1,2r∗+n−k and i is obviously not greater than min2r∗,k, we have(57)∑i=T+12r∗ikAi,d≤min2r∗,kkAd′.Therefore,(58)∑i=T+12r∗∑d=2r∗+12r∗+n−kikAi,dQdσBpb,k−i,0,r∗−i2≤∑d=2r∗+12r∗+n−kmin2r∗,kkAd′Qdσ,for Bpb,k−i,0,r∗−i/2≤1.Then, we have(59)∑i=T+12r∗∑d=1nikAi,dQdσBpb,k−i,0,r∗−i2≤∑d=T+12r∗mind,kkAd′Qdσ+∑d=2r∗+12r∗+n−kmin2r∗,kkAd′Qdσ,by combining (53) and (58) with (59).Finally, we have(60)PrEb≤minT/2+1≤r∗≤k∑i=1Tik∑d=1nhi,d,r∗+∑d=T+12r∗mind,kkAd′Qdσ+∑d=2r∗+12r∗+n−kmin2r∗,kkAd′Qdσ+Cr∗,pb,k,r∗+1,k,by combining (48) and (59) with (47).Then, we have the following theorem.Theorem 2.
We have the upper bound on the bit error probability of systematic binary linear codes via their weight spectra(61)PrEb≤minPrEb1,PrEb2,where(62)PrEb1=min0≤r∗≤T/2∑i=12r∗ik∑d=1nAi,dQdσBpb,k−i,0,r−i2+Cr∗,pb,k,r∗+1,k,PrEb2=minT/2+1≤r∗≤k∑i=1Tik∑d=1nhi,d,r∗+∑d=T+12r∗mind,kkAd′Qdσ+∑d=2r∗+12r∗+n−kmin2r∗,kkAd′Qdσ+Cr∗,pb,k,r∗+1,k.Proof.
We can complete the theorem by combining (46) and (60).Corollary 3.
The proposed upper bound on the bit error probability (Theorem2) can improve the proposed upper bound on the bit error probability (Theorem 1).Assuming that we know only the truncated IOWEF {Ai,d, 0≤i≤T, 0≤d≤n−k+T} and the proof weight spectrum Ad,0≤d≤n, Theorem 1 can be written as(63)PrEb≤min0≤r∗≤T/2∑i=12r∗ik∑d=1nAi,dQdσBpb,k−i,0,r−i2+Cr∗,pb,k,r∗+1,k,implying that PrEb≤PrEb1. Theorem 2 needs a minimization over 0≤r∗≤k if the optimal parameter r∗ is in the interval 0,T/2, and Theorem 2 is exactly Theorem 1; if r∗ is in the interval T/2+1,k, Theorem 2 is tighter than Theorem 1. Therefore, we claim that Theorem 2 can improve Theorem 1 to complete the proof.Corollary 4.
The proposed upper bound on the bit error probability (Theorem2) can improve the Ma bound on the bit error probability (18).Proof.
It can be verified by combining Corollaries 2 and 3.Remark.
The proposed bound (Theorem2) has a little higher computational loads than the conventional union bound. Firstly, the overhead is caused by recursively computing B⋅,⋅,⋅,⋅ and C⋅,⋅,⋅,⋅,⋅. The probability B⋅,⋅,⋅,⋅ and C⋅,⋅,⋅,⋅,⋅ is the summation with at most k summands, which are independent of the IOWEF and hence can be calculated and stored for use. Secondly, the overhead is caused by minimizing over r∗0≤r∗≤k. A brute-force method can be implemented by computing the bound for each r∗, which can be done recursively.


## 3.1. The Gallager Regionℛ

We define the regionℛ by the Hamming distance based on a list decoding algorithm which is shown in Figure 1, resulting in an irregular high-dimensional geometry (Algorithm 1).Figure 1
Graphical illustrations of the decoding error events. (a) The error event that the all-zero sequenceu¯0 is not in the list. (b) The error event that the all-zero sequence u¯0 is in the list but not the closest one.
(a)
(b)Algorithm 1:A list decoding algorithm.
(1)
We denote
y¯≜y¯0k−1y¯kn−1
in which
y¯0k−1=y0⋯yk−1︸k
and
y¯kn−1=yk⋯yn−1︸n−k
Make hard decisions on the information party¯0k−1=y0⋯yk−1︸k of the received vector y¯, resulting in a vector y¯^0k−1=y^0⋯y^k−1︸k of length k. Then, the channel becomes a memoryless binary symmetric channel (BSC) with cross probability
pb≜Q1/σ
(2)
List all sequences of lengthk within the Hamming sphere with center at y¯^0k−1 of radius r∗, where r∗ is a positive integer. The resulting list is denoted as ℒy¯.
(3)
Encode each sequence inℒy¯ by the encoding algorithm of the systematic code, resulting in a list of code words, denoted as ℒc¯.
(4)
Find the codewordc¯∗∈ℒc¯ that is closest to y¯. Output the information part u¯^ of c¯∗ as the decoding result.The list decoding algorithm is similar to but different from the algorithm presented in [14]. The list region in [14] is an n-dimensional Hamming sphere with center at the hard decision of the whole received sequence, while the list region here is a k-dimensional Hamming sphere with center at the hard decision of the information part of the received sequence.The Gallager regionℛ can be defined by(20)ℛ≜y¯u¯0∈ℒy¯=y¯WHy¯^0k−1≤r∗.


## 3.2. Upper Bound on the Bit Error Probability via IOWEF

We assume thatAi,d≥1 and denote all the code words of Hamming weight d encoded by information bits of Hamming weight i by c¯ℓ, 1≤ℓ≤Ai,d. Let E0⟶ℓ be the event that c¯ℓ is nearer than c¯0 to y¯.With the framework of GFBT, we have(21)PrEb=PrEb,y¯∈ℛ+PrEb,y¯∉ℛ.As shown in Figure1(b), we have(22)PrEb,y¯∈ℛ≤∑i=12r∗ik∑d=1nPrEbi,d,y¯∈ℛ,(23)≤∑i=12r∗ik∑d=1nAi,dPrE0⟶1,y¯∈ℛ.As shown in Figure1(a), we have(24)PrEb,y¯∉ℛ≤∑i=r∗+1kmini+r∗,kkkipbi1−pbk−i,which means that the decoder outputs at most i+r∗ erroneous bits.Assuming a binary vector of total lengthNt passes through a BSC with cross error probability p, we denote Bp,Nt,Nℓ,Nu to be the probability that the number of bit errors occurring ranges from Nℓ to Nu, that is,(25)Bp,Nt,Nℓ,Nu≜∑m=NℓNuNtmpm1−pNt−m.Then, we define(26)Cr,p,Nt,Nℓ,Nu≜∑m=NℓNuminm+r,NtNtNtmpm1−pNt−m.Theorem 1.
We have the upper bound on the bit error probability of systematic binary linear codes under MAP decoding(27)PrEb≤min0≤r∗≤k∑i=12r∗ik∑d=1nAi,dQdσBpb,k−i,0,r−i2+Cr∗,pb,k,r∗+1,k.Proof.
Without loss of generality, we denote(28)c¯1≜1⋯1︸i0⋯0︸k−i1⋯1︸d−i0⋯0︸n−k−d+i,y^0k−1≜1⋯1︸i10⋯0︸i−i11⋯1︸i20⋯0︸k−i−i2.
Notice that a necessary condition for the eventE0⟶1 is that the corresponding input information sequence of the codeword c¯1 is in the list ℒy¯. Hence,(29)WHc¯01k−1−y^¯0k−1≤r∗.
We have(30)i−i1+i2≤r∗.
Also notice that, fory¯∈ℛ,(31)WHy^¯0k−1≤r∗.
We have(32)i1+i2≤r∗.
By combining (30) and (32), we can verify that(33)i2≤r∗−i2.
By the union bounds, we have(34)PrE0⟶1,y¯∈ℛ=PrE0⟶1,WHy^¯0k−1≤r∗≤∑i2=1r∗PrE0⟶1,WHy^¯0i−1≤r∗−i2,WHy^¯ik−1=i2≤∑i2=1r∗PrE0⟶1,WHy^¯ik−1=i2=∑i2=1r∗−i/2PrE0⟶1,WHy^¯ik−1=i2,for i2≤r∗−i/2 from (33).
Since the eventPrE0⟶1 is independent of y^¯ik−1 and PrE0⟶1=Qd/σ, we have(35)∑i2=1r∗−i/2PrE0⟶1,WHy^ik−1=i2,(36)=∑i2=1r∗−i/2PrE0⟶1PrWHy^ik−1=i2,(37)=PrE0⟶1∑i2=1r∗−i/2PrWHy^ik−1=i2,(38)=QdσBpb,k−i,0,r∗−i2.
Then, by substituting (38) in (23), we have(39)PrEb,y¯∈ℛ≤∑i=12r∗ik∑d=1nAi,dQdσBpb,k−i,0,r∗−i2.
Therefore, it can be verified by substituting (24) and (39) in (1) to complete the proof.Corollary 1.
The proposed upper bound on the bit error probability (Theorem1) can improve the conventional union bound on the bit error probability.Proof.
As to the proposed bound (Theorem1), note that(40)Cr∗,pb,k,r∗+1,k=0,by setting(41)r∗=k.
we have(42)PrEb≤∑i=1kik∑d=1nAi,dQdσBpb,k−i,0,r∗−i2≤∑i=1kik∑d=1nAi,dQdσ.
SinceBpb,k−i,0,r∗−i/2≤1, the proof is completed.Corollary 2.
The proposed upper bound on the bit error probability (Theorem1) can improve the Ma bound on the bit error probability (18).Proof.
Assuming that we know only partial IOWEF with truncated information weightAi,d,0≤i≤T,0≤d≤n−k+T, the parameter r∗ in the proposed bound (Theorem 1) is optimized in the interval 0,T/2. Theorem 1 can be written as(43)PrEb≤min0≤r∗≤T/2∑i=12r∗ik∑d=1nAi,dQdσBpb,k−i,0,r−i2+Cr∗,pb,k,r∗+1,k.
SinceBpb,k−i,0,r−i/2 is the probability that the number of bit errors occurring in a binary vector of total length k−i, when passing through a BSC with cross error probability pb, it ranges from 0 to r−i/2. Then, it can be verified by(44)Bpb,k−i,0,r∗−i2≤1,to complete the proof.The objective of this paper is to derive the upper bound on bit error probability with only knowing of the weight spectrum.


## 3.3. Upper Bound on the Bit Error Probability via Weight Spectra

In this section, we focus on how to derive the upper bound on the bit error probability via weight spectra. The IOWEF is usually not computable, but the weight spectraAd,0≤d≤n of the code are usually available, such as the BCH code [17]. Let T≥0 be a positive integer that is relatively small. Assuming that we know only the truncated IOWEF {Ai,d, 0≤i≤T, 0≤d≤n−k+T} which can be obtained by using a brute-force method and the weight spectrum Ad,0≤d≤n.Define(45)Ad′=Ad−∑i=1TAi,d,for 0≤d≤n.Then, we focus on how to obtain the upper bound on the bit error probability by using the IOWEF {Ai,d, 0≤i≤T, 0≤d≤n−k+T} and the weight spectrum Ad,0≤d≤n. We derive the upper bound in the two following cases.Case 1: if the radius of the Hamming spherer∗∈0,T/2 in Figure 1, we can get the IOWEF {Ai,d, 0≤i≤T, 0≤d≤n−k+T} by using a brute-force method, and we have(46)PrEb≤min0≤r∗≤T/2∑i=12r∗ik∑d=1nAi,dQdσBpb,k−i,0,r−i2+Cr∗,pb,k,r∗+1,k,which can be verified by Theorem1.Case 2: if the radius of the Hamming spherer∗∈T/2+1,k in Figure 1, we can derive the upper bound on the bit error probability by employing both the IOWEF {Ai,d, 0≤i≤T, 0≤d≤n−k+T} and the weight spectrum Ad,0≤d≤n.From Theorem1, we have(47)PrEb≤minT/2+1≤r∗≤k∑i=12r∗ik∑d=1nAi,dQdσBpb,k−i,0,r−i2+Cr∗,pb,k,r∗+1,k,in which(48)∑i=12r∗ik∑d=1nAi,dQdσBpb,k−i,0,r∗−i2=∑i=1T∑d=1nikAi,dQdσBpb,k−i,0,r∗−i2+∑i=T+12r∗∑d=1nikAi,dQdσBpb,k−i,0,r∗−i2.Note that(49)∑i=T+12r∗∑d=1nAi,d=∑i=T+12r∗∑d=i2r∗Ai,d+∑i=T+12r∗∑d=2r∗+12r∗+n−kAi,d.Firstly, it is easy to verify that the first term in the right-hand side (RHS) of (49)(50)∑i=T+12r∗∑d=i2r∗Ai,d=∑d=T+12r∗∑i=T+1dAi,d.Since(51)∑i=T+1dAi,d=Ad′,for d∈T+1,2r∗ and i is obviously not greater than mind,k, we have(52)∑i=T+1dikAi,d≤mind,kkAd′.Therefore,(53)∑i=T+12r∗∑d=i2r∗ikAi,dQdσBpb,k−i,0,r∗−i2≤∑d=T+12r∗mind,kkAd′Qdσ,for(54)Bpb,k−i,0,r∗−i2≤1.Secondly, it is easy to verify that the second term in the RHS of (49)(55)∑i=T+12r∗∑d=2r∗+12r∗+N−KAi,d≤∑d=2r∗+12r∗+N−KAd′.Since(56)∑i=T+12r∗Ai,d≤Ad′,for d∈T+1,2r∗+n−k and i is obviously not greater than min2r∗,k, we have(57)∑i=T+12r∗ikAi,d≤min2r∗,kkAd′.Therefore,(58)∑i=T+12r∗∑d=2r∗+12r∗+n−kikAi,dQdσBpb,k−i,0,r∗−i2≤∑d=2r∗+12r∗+n−kmin2r∗,kkAd′Qdσ,for Bpb,k−i,0,r∗−i/2≤1.Then, we have(59)∑i=T+12r∗∑d=1nikAi,dQdσBpb,k−i,0,r∗−i2≤∑d=T+12r∗mind,kkAd′Qdσ+∑d=2r∗+12r∗+n−kmin2r∗,kkAd′Qdσ,by combining (53) and (58) with (59).Finally, we have(60)PrEb≤minT/2+1≤r∗≤k∑i=1Tik∑d=1nhi,d,r∗+∑d=T+12r∗mind,kkAd′Qdσ+∑d=2r∗+12r∗+n−kmin2r∗,kkAd′Qdσ+Cr∗,pb,k,r∗+1,k,by combining (48) and (59) with (47).Then, we have the following theorem.Theorem 2.
We have the upper bound on the bit error probability of systematic binary linear codes via their weight spectra(61)PrEb≤minPrEb1,PrEb2,where(62)PrEb1=min0≤r∗≤T/2∑i=12r∗ik∑d=1nAi,dQdσBpb,k−i,0,r−i2+Cr∗,pb,k,r∗+1,k,PrEb2=minT/2+1≤r∗≤k∑i=1Tik∑d=1nhi,d,r∗+∑d=T+12r∗mind,kkAd′Qdσ+∑d=2r∗+12r∗+n−kmin2r∗,kkAd′Qdσ+Cr∗,pb,k,r∗+1,k.Proof.
We can complete the theorem by combining (46) and (60).Corollary 3.
The proposed upper bound on the bit error probability (Theorem2) can improve the proposed upper bound on the bit error probability (Theorem 1).Assuming that we know only the truncated IOWEF {Ai,d, 0≤i≤T, 0≤d≤n−k+T} and the proof weight spectrum Ad,0≤d≤n, Theorem 1 can be written as(63)PrEb≤min0≤r∗≤T/2∑i=12r∗ik∑d=1nAi,dQdσBpb,k−i,0,r−i2+Cr∗,pb,k,r∗+1,k,implying that PrEb≤PrEb1. Theorem 2 needs a minimization over 0≤r∗≤k if the optimal parameter r∗ is in the interval 0,T/2, and Theorem 2 is exactly Theorem 1; if r∗ is in the interval T/2+1,k, Theorem 2 is tighter than Theorem 1. Therefore, we claim that Theorem 2 can improve Theorem 1 to complete the proof.Corollary 4.
The proposed upper bound on the bit error probability (Theorem2) can improve the Ma bound on the bit error probability (18).Proof.
It can be verified by combining Corollaries 2 and 3.Remark.
The proposed bound (Theorem2) has a little higher computational loads than the conventional union bound. Firstly, the overhead is caused by recursively computing B⋅,⋅,⋅,⋅ and C⋅,⋅,⋅,⋅,⋅. The probability B⋅,⋅,⋅,⋅ and C⋅,⋅,⋅,⋅,⋅ is the summation with at most k summands, which are independent of the IOWEF and hence can be calculated and stored for use. Secondly, the overhead is caused by minimizing over r∗0≤r∗≤k. A brute-force method can be implemented by computing the bound for each r∗, which can be done recursively.


## 4. Numerical Examples

In this section, we need to point out that the weight spectra of the compared BCH codes can be found in [17]. For all the upper bounds on the bit error probability except the Ma bound, we need the whole IOWEF. Then, in this paper, the compared bounds are the Ma bound (18) and the proposed bound (61) in Theorem 2 on the bit error probability, which are also compared with the simulation results under the maximum-likelihood (ML) decoding.Figures2 and 3 show the comparisons between the upper bounds of BCH codes [127, 106] and [127, 113], respectively, which are also compared with the simulation results under ML decoding. A partial IOWEF {Ai,d, 0≤i≤T, 0≤d≤n−k+T} with T=8 of the BCH codes [127, 106] and [127, 113] can be obtained by using a brute-force method, respectively. The computed IOWEF {Ai,d, 0≤i≤8, 0≤d≤29} of the BCH code [127, 106] is given in Table 1. The Ma bound is obtained by this truncated IOWEF according to (18). The proposed upper bound is obtained by this truncated IOWEF and the weight spectrum according to (61) in Theorem 2 (note that (61) is different from [5], (23)) since Theorem 2 here is derived in a much more detailed way when the Hamming weight d∈T,2r∗. As pointed out in [18], multidimensional signal processing plays a very important role in effective data analytics and interpretation. In this paper, we tighten the upper bound by analysing the k-dimensional vector. We can see that the proposed bound is tighter than the Ma bound. We can also see that, for the same code length n, the higher the code rate is, the tighter the Ma bound is. The proposed bound is always tighter whatever the code rate is.Figure 2
comparison between the proposed bound (Theorem 2) and the Ma bound on the bit error probability of the BCH code [127, 106], which is also compared with the simulation results under ML decoding.Figure 3
comparison between the proposed bound (Theorem 2) and the Ma bound on the bit error probability of the BCH code [127, 113], which is also compared with the simulation results under ML decoding.Table 1
The partial IOWEF {Ai,d, 0≤i≤8, 0≤d≤29} with T=8 of the BCH code [127, 106].
1
7
17
3
19
1847
5
20
2627123
7
15
2.364896e + 009
1
8
8
3
20
584
5
21
984117
7
16
3.415877e + 009
1
9
2
3
21
127
5
22
288687
7
17
4.098554e + 009
1
10
4
3
22
21
5
23
64158
7
18
4.098554e + 009
1
11
23
4
7
3470
5
24
10105
7
19
3.415535e + 009
1
12
27
4
8
15952
5
25
1049
7
20
2.364660e + 009
1
13
13
4
9
46995
5
26
59
7
21
1351255504
1
14
3
4
10
125279
6
7
19462
7
22
630548101
1
15
8
4
11
275791
6
8
194386
7
23
236462455
1
16
1
4
12
484126
6
9
1059704
7
24
69546072
2
7
71
4
13
697948
6
10
4752113
7
25
15457425
2
8
188
4
14
834510
6
11
16623036
7
26
2439979
2
9
305
4
15
834260
6
12
44331232
7
27
243848
2
10
472
4
16
696623
6
13
94527372
7
28
11614
2
11
711
4
17
482965
6
14
165420289
8
8
163532
2
12
1007
4
18
275130
6
15
239125721
8
9
2946230
2
13
964
4
19
128772
6
16
286915986
8
10
29469636
2
14
794
4
20
47734
6
17
286915986
8
11
192045523
2
15
511
4
21
14385
6
18
239077900
8
12
864339336
2
16
340
4
22
3172
6
19
165519571
8
13
2.924072e + 009
2
17
135
4
23
513
6
20
94593564
8
14
7.797383e + 009
2
18
48
4
24
37
6
21
44141017
8
15
1.672354e + 010
2
19
12
4
25
2
6
22
16553366
8
16
2.926719e + 010
2
20
7
5
7
11611
6
23
4864138
8
17
4.226740e + 010
3
7
614
5
8
73116
6
24
1082409
8
18
5.072263e + 010
3
8
2097
5
9
281110
6
25
170775
8
19
5.072258e + 010
3
9
4816
5
10
960971
6
26
17090
8
20
4.226969e + 010
3
10
10482
5
11
2633699
6
27
823
8
21
2.926271e + 010
3
11
18637
5
12
5642851
7
7
13142
8
22
1.672131e + 010
3
12
27236
5
13
9825582
7
8
276537
8
23
7.803514e + 009
3
13
32706
5
14
14197834
7
9
2380926
8
24
2.926377e + 009
3
14
32212
5
15
17043850
7
10
15092372
8
25
860707256
3
15
27027
5
16
17047259
7
11
69866721
8
26
191259366
3
16
18689
5
17
14202094
7
12
237457686
8
27
30195788
3
17
10826
5
18
9829514
7
13
630106871
8
28
3021987
3
18
5000
5
19
5614707
7
14
1350174932
8
29
143670Figure4 shows the comparisons between the upper bounds on the bit error probability of the BCH code [255, 239], which are also compared with the simulation results under ML decoding. A partial IOWEF {Ai,d, 0≤i≤T, 0≤d≤n−k+T} with T=5 of the BCH code [255, 239] can be obtained by using a brute-force method. The Ma bound is obtained by this truncated IOWEF according to (18). The proposed upper bound is obtained by this truncated IOWEF and the weight spectrum according to (61). We can see that the proposed bound is tighter than the Ma bound. We can also see that, the proposed bound coincides nicely with the ML decoding results in the high-SNR region when we only know less IOWEF {Ai,d, 0≤i≤5, 0≤d≤21} of the BCH code [255, 239].Figure 4
comparison between the proposed bound (Theorem 2) and the Ma bound on the bit error probability of the BCH code [255, 239], which is also compared with the simulation results under ML decoding.Figure5 shows the comparisons between the upper bounds on the bit error probability of the BCH code [31, 21], which are also compared with the simulation results under ML decoding. The whole IOWEF Ai,d, 0≤i≤21, 0≤d≤31} of the BCH code [31, 21] can be obtained by using a brute-force method. The Ma bound is obtained by the whole IOWEF according to (18), where T=21. The proposed upper bound is obtained by the whole IOWEF and the weight spectrum according to (61). We can see that the proposed bound is tighter than the Ma bound in the low-SNR region when we know the whole IOWEF. We can also see that, the proposed bound and the Ma bound coincide nicely with the ML decoding results in the high-SNR region.Figure 5
comparison between the proposed bound (Theorem 2) and the Ma bound on the bit error probability of the BCH code [31, 21], which is also compared with the simulation results under ML decoding.


## 5. Conclusions

In this paper, upper bound on the bit error probability of systematic binary linear codes under MAP decoding is derived. The proposed bound just requires the weight spectra of the code, which is helpful when the whole IOWEF of the code is not available. The proposed bound (Theorem2) is proved to be tighter than the recently proposed Ma bound. The numerical results show that the proposed bound on the bit error probability via weight spectra coincides nicely with the ML decoding results in the high-SNR region, which can predict the BER performance without resorting to computer simulations since the simulation is time-consuming in high-SNR region.



---

*Source: 1469090-2020-01-29.xml*