# Trellis Tone Modulation Multiple-Access for Peer Discovery in D2D Networks
## 4 Multi-User Detection of TTMMA via Message-Passing
### Message-Passing Algorithm  
The first goal of the message-passing algorithm is to determine \(\mathbf{H}_{k}\). The linear equation (8) with a sparse matrix \(\mathbf{H}_{k}\) can be represented by a bipartite graph as given in Figure 5a. The bipartite graph, which we call the multiple-access tone transition graph, is composed of pre-state nodes (PreN) and post-state nodes (PostN) onto which \(\widetilde{\mathbf{x}}_{k}\) and \(\widetilde{\mathbf{x}}_{k+1}\) are loaded respectively. Let \(\{\mathbf{A}\}_{j}\) be the \(j\)-th row vector of matrix \(\mathbf{A}\) and \(\{\mathbf{A}\}_{i,j}\) be the entry at the \(i\)-th row and the \(j\)-th column. The edge connecting PreN \(i\) and PostN \(j\) is weighted by \(\{\mathbf{H}_{k}\}_{i,j}\). If forward messages from left to right are generated such that the node value is multiplied to edge weight, then in the \(i\)-th right node the sum of incoming messages are equal to the node value, equivalently,  
\[\left\{\widetilde{\mathbf{x}}_{k+1}\right\}_{i}=\{\mathbf{H}_{k}\}_{j} \widetilde{\mathbf{x}}_{k} \tag{10}\]  
Finding \(\mathbf{H}_{k}\) is equivalent to determination of the graph structure. We achieve the goal by validating and pruning edges from a base graph via message-passing decoding with the received signals \(\mathbf{y}_{k}\) and \(\mathbf{y}_{k+1}\). First, the base graph is defined as a graph with the same state node sets where every possible state transition due to \(\mathbf{T}\) is represented as an edge. Naturally, the multiple-access tone transition graph is a subgraph of this base graph. The base graph corresponding to an example  
\[\mathbf{T}=\left[ \begin{array}{cccc}1&1&0&0\\ 1&0&1&0\\ 0&1&0&1\\ 0&0&1&1\end{array} \right]\]  
is given in Figure 5b. When decoding is conducted, first the nodes are initialized with \(\mathbf{y}_{k}\) and \(\mathbf{y}_{k+1}\) and then messages are exchanged between PreNs and PostNs through the edges. Edges in the base graph can be validated or pruned during the demodulation; the graph is then reduced by the node processing. The node processing is basically the validation (or pruning) of edge candidates. This is equivalent to find the non-zero elements in \(\{\mathbf{H}_{k}\}_{i}\) for the node. The PostN check if there is a possible edge connection pattern that satisfies the matching condition; the incoming messages are well matched to the node value \(\{\mathbf{y}_{k+1}\}_{i}\) with respect to the edge combination. If an edge connection pattern is confirmed then some edges are validated and some edges are pruned and outgoing messages are generated based on the decision. The messages for pruned edges will be ignored or nulled whereas the messages for validated edges are set as the incoming message. For non-confirmed nodes, the outgoing  
Figure 5: (a) Example of multiple-access tone transition graph; (b) Example of base graph corresponding to an example T.  
message is determined by the subtraction of the sum of incoming messages from other nodes from the node value \(\left\{\mathbf{y}_{k+1}\right\}_{i}\). The backward message-passing is exactly the same as the forward processing other than the fact that the relation is inverted as  
\[\left\{\widetilde{\mathbf{x}}_{k}\right\}_{i}=\left\{\mathbf{H}_{k}^{-1} \right\}_{i}\widetilde{\mathbf{x}}_{k+1} \tag{11}\]  
Iterative processing of the forward and backward message-passing gives a reliable detection of multiple UE messages. When the node processing is conducted at PostN \(q\), there are \(2^{d}\) edge combinations where \(d\) is the degree of PostN \(q\). Let \(\mathbf{p}\) be a binary vector of length \(d\) and indicate the edge connection pattern where zero indicates the edge pruned and \(\mathbf{u}_{q}\) be the vector of incoming messages to PostN \(q\). Let \(C_{\mathbf{p}}=\mathbf{u}_{q}\mathbf{p}^{\mathrm{T}}\) be the combined message with respect to \(\mathbf{p}\). Then \(C_{\mathbf{p}}\) is compared with the node value \(\left\{\mathbf{y}_{k+1}\right\}_{q}\).