# Study of Coded ALOHA with Multi-User Detection under Heavy-Tailed and Correlated Arrivals
## 2 System Model
### Bipartite Graph Representation and Degree Distributions  
It is well known in the literature [28; 37] that a CSA system can be modeled as a bipartite graph between the set \(\mathcal{V}\) of variable nodes and the set \(\mathcal{C}\) of constraint (or check) nodes. In the graph, an edge between \(i\in\mathcal{V}\) and \(j\in\mathcal{C}\) represents the transmission of a packet (one of its copies) from node \(i\) in slot \(j\). Hence, the number of outgoing links from node \(i\) is equal to the number of replicas generated for that packet, and the number of incoming edges into \(j\) is \(r\) if \(j\) is a degree-\(r\) slot. The main advantage of the bipartite graph representation can be summarized by noting that this graphical model allows us to understand the iterative decoding procedure described in Section 2.1 as an instance in the framework of message passing algorithms over graphs (see [37]).  
Figure 1 shows in detail in its top panel an example of FS-CSA for a system with frames of \(n=6\) slots and \(\lambda_{a}=0.5\). The nodes select degrees 2 or 3 for their packets. These are depicted as slots filled with blue (degree-2) and red (degree-3), respectively. The shaded areas depict the frames, the same for all users, and the striped blocks show the slots in which packets cannot be decoded, since this example assumes standard ALOHA (\(k=1\), no MUD).  
In Figure 2, the graphical representation for the two scenarios of Figure 1 is depicted, while in Figure 3 we plot an example of FA-CSA-F, with with \(n=6\), \(\lambda_{a}=1\) and where users select degree 2 or 3. In this case only if \(k>1\) all the packets can be decoded.  
Figure 1: An example of FS-CSA and FA-CSA-F with \(k=1\).  
Figure 3: An example of FA-CSA-F with \(k=2\).  
Figure 2: Equivalent graph representation of the system depicted in Figure 1.  
As is customary for the analysis of codes defined on graphs, the different degrees of the nodes is represented in polynomial compact form as  
\[\Lambda(x)\triangleq\sum_{i}\Lambda_{i}x^{i},\quad P(x)\triangleq\sum_{j}P_{j}x^{j} \tag{1}\]  
for variable and check nodes, respectively. Here \(\Lambda_{i}\) is the probability that a variable node (VN) has degree \(i\), and \(P_{j}\) is the probability that a check node (CN) has degree equal to \(j\). The VN degree polynomial \(\Lambda(x)\) is a system design parameter and can be optimized for maximizing the system performance.  
Similarly, the degree polynomials defined as  
\[\lambda(x)\triangleq\sum_{i}\lambda_{i}x^{i-1},\quad\rho(x)\triangleq\sum_{j} \rho_{j}x^{j-1}, \tag{2}\]  
summarize the distribution of degrees for a random edge in the bipartite graph. More precisely, in the definition \(\lambda_{i}\) denotes the probability that an edge is connected to a degree-\(i\) VN, and the probability that the edge is connected to a degree-\(j\) CN is given by \(\rho_{j}\). The relationship between the coefficients that appear in (1) and (2) is  
\[\lambda_{i}=\frac{i\Lambda_{i}}{\sum_{m}m\Lambda_{m}},\quad\rho_{j}=\frac{jP_{ j}}{\sum_{m}mP_{m}}. \tag{3}\]  
Thus, \(\lambda(x)=\Lambda^{\prime}(x)/\Lambda^{\prime}(1)\) and \(\rho(x)=P^{\prime}(x)/P^{\prime}(1)\), where \(f^{\prime}\) is the derivative of function \(f\).