# Improved PEG-Based Construction of Analog Fountain Codes
## 3 Improved PEG-Based Construction
### Analysis of Improved PEG-Based Construction  
Suppose that after applying Algorithm 1, a new initialized CN \(c_{n}\) introduces length-\(r\) cycles following the selection of \(E_{c_{n}}^{d-e}\), where \(e\) denotes the minimum number of length-\(r\) cycles introduced by \(c_{n}\). During the selection of \(E_{c_{n}}^{a}\), where \(d-e\leq a<d\), \(a\) selected edges \(E_{c_{n}}^{0},E_{c_{n}}^{1},\cdots,E_{c_{n}}^{a-1}\) during the selection of \(c_{n}\), and \(nd\) edges established before the initialization of \(c_{n}\) are candidates that can be randomly connected to form a length-\(r\) cycle. Denote the \(r-2\) edges of the length-\(r\) cycle established before the initialization of \(c_{n}\) as \(\left(c_{j_{0}},b_{i_{0}}\right)\), \(\left(c_{j_{1}},b_{i_{1}}\right)\), \(\cdots,\left(c_{j_{r-3}},b_{i_{r-3}}\right)\), where \(0\leq j<n\) and \(0\leq i<k\). Without loss of generality, denote \(E_{c_{n}}^{a}\leftarrow\left(c_{n},b_{i_{0}}\right)\) as the edge closes the cycle, and denote \(E_{c_{n}}^{a^{\prime}}\leftarrow\left(c_{n},b_{i_{1}}\right)\) as the edge forming the cycle due to the presence of \(\left(c_{n},b_{i_{0}}\right)\), where \(0\leq a^{\prime}<a\). Moreover, divide \(\text{W}\) into two subsets according to \(E_{c_{n}}^{d-e}\) as \(\text{W}=\text{W}_{\text{large}}\cup\text{W}_{\text{small}}\), where \(\text{W}_{\text{large}}=\{w_{0},w_{1},\cdots,w_{d-e-1}\}\) and \(\text{W}_{\text{small}}=\{w_{d-e},w_{d-e+2},\cdots,w_{d-1}\}\) represent the sets consisting of relatively large and small weight coefficients, respectively. Based on the aforementioned discussion, the probabilities that a weight coefficient involved in the above edges are analyzed case by case. _Case 1:_  
\[P(g_{j,i}=w)=1/d,\ w\in\text{W}, \tag{6}\]  
where \(\left(c_{j},b_{i}\right)\) is one of the \(r-2\) edges. The weight coefficient in \(\left(c_{j},b_{i}\right)\) is allocated before the PEG selects edges for \(c_{n}\). Thus, it is considered as randomly selected from \(\text{W}\). _Case 2:_  
\[P(g_{n,j_{0}}=w)=0,\ w\in\text{W}_{\text{large}}. \tag{7}\]Considering that length-\(r\) cycles arise after selecting \(E_{c_{n}}^{d-e}\), and the weight coefficients are allocated in descending order, the last selected \(e\) edges for \(c_{n}\) are allocated with \(w\in\text{W}_{\text{small}}\). On the contrary, any \(w\in\text{W}_{\text{large}}\) cannot be allocated to \(g_{n,i_{0}}\). _Case 3:_  
\[P(g_{n,i_{1}}=w)=\frac{1}{a}\leq\frac{1}{d-e},\ w\in\text{W}_{\text{large}}. \tag{8}\]  
The corresponding \(\left(c_{n},b_{i_{1}}\right)\) is randomly connected from the \(a\) selected edges. Thus, \(w\) can be considered as randomly selected from \(\left\{w_{0},w_{1},\cdots,w_{a-1}\right\}\). Based on the above analysis, \(r-2\) edges \(\left(c_{j},b_{i}\right)\), \(1\) edge \(\left(c_{n},b_{i_{0}}\right)\), and \(1\) edge \(\left(c_{n},b_{i_{1}}\right)\) have the probabilities in cases 1, 2, and 3, respectively. The probability that \(w\) is involved in an edge of the new introduced length-\(r\) cycles when \(w\in\text{W}_{\text{large}}\) is  
\[P(g_{j,i}=w)\leq(\frac{1}{d-e}+\frac{r-2}{d})/r,\ w\in\text{W}_{\text{large}}, \tag{9}\]  
where \(0\leq j\leq n\). **Example 1**. : _Let us consider a \(256\times 64\) matrix \(\mathbf{G}\) with degree \(d=4\), which is generated using Algorithm 1. According to the parameter settings and the bound analysis in [10], a few length-\(4\) cycles arise. Thus, we consider \(r=4\) and \(e=1\). \(\text{W}\) is divided into \(\text{W}_{\text{large}}=\left\{w_{0},w_{1},w_{2}\right\}\) and \(\text{W}_{\text{small}}=\left\{w_{3}\right\}\). Substitute \(d\), \(e\), and \(r\) into (9), \(P(g_{j,i}=w)\leq 0.208\), when \(w\in\text{W}_{\text{large}}\). Through statistical analysis of a generated \(\mathbf{G}\), there are 25 length-\(4\) cycles. The probabilities of weight coefficients involved in the length-\(4\) cycles are shown in Table 1. These results verify our analysis for length-\(4\) cycles._  
**Example 2**.