# Trellis Tone Modulation Multiple-Access for Peer Discovery in D2D Networks
## 4 Multi-User Detection of TTMMA via Message-Passing
### Message-Passing Algorithm
If they are sufficiently close as \(\left\|\left\{\mathbf{y}_{k+1}\right\}_{q}-C_{\mathbf{p}}\right\|^{2}\leq \left(\mathrm{w}_{\mathrm{H}}(\mathbf{p})+1\right)\delta\), where \(\delta\) is the noise power and \(\mathrm{w}_{\mathrm{H}}(\cdot)\) denotes the Hamming weight, we confirm the edge connection pattern \(\mathbf{p}\) is valid. The edges are validated or pruned according to the confirmed pattern \(\mathbf{p}\). Since one noise component is added to the value of node and the message, \(\mathrm{w}_{\mathrm{H}}(\mathbf{p})+1\) noise components is included in \(\left\{\mathbf{y}_{k+1}\right\}_{q}-C_{\mathbf{p}}\). If \(\left\{\mathbf{y}_{k+1}\right\}_{q}\) satisfies the pattern \(\mathbf{p}\), then only \(\mathrm{w}_{\mathrm{H}}(\mathbf{p})+1\) noise components remain in \(\left\{\mathbf{y}_{k+1}\right\}_{q}-C_{\mathbf{p}}\), so this value follows the complex Gaussian distribution \(CN\left(0,(\mathrm{w}_{\mathrm{H}}(\mathbf{p})+1)\sigma^{2}\right)\). Therefore, when \(\alpha\) is a constant larger than \(1\), it is set to \(\delta=\alpha\sigma^{2}\) and the process of checking \(\left\|\left\{\mathbf{y}_{k+1}\right\}_{q}-C_{\mathbf{p}}\right\|^{2}\leq( \mathrm{w}_{\mathrm{H}}(\mathbf{p})+1)\delta\) is used to determine whether the remaining signal component of \(\left\{\mathbf{y}_{k+1}\right\}_{q}-C_{\mathbf{p}}\) is noise only. The details of the message-passing procedure is given in the following. 1. The forward message \(u_{p\to q}^{l}\) is passed from the \(p\)-th PreN to the \(q\)-th PostN in the \(l\)-th iterative message-passing. Similarly, \(v_{q\to p}^{l}\) is the backward message passed from the \(q\)-th PostN to the \(p\)-th PreN. The initial forward messages are set as \(u_{p\to q}^{1}=\left\{\mathbf{y}_{k}\right\}_{p}\). 2. In the \(l\)-th iterative message-passing, the \(q\)-th PostN compares its value \(\left\{\mathbf{y}_{k+1}\right\}_{q}\) with all candidate patterns \(C_{\mathbf{p}}=\mathbf{u}_{q}\mathbf{p}^{\mathrm{T}}\). The condition \(\left\|\left\{\mathbf{y}_{k+1}\right\}_{q}-C_{\mathbf{p}}\right\|^{2}\leq( \mathrm{w}_{\mathrm{H}}(\mathbf{p})+1)\delta\) is checked for all \(\mathbf{p}\). For example, in Figure 5b, the second PostN compares the combined messages \(C_{(00)}=0\), \(C_{(10)}=u_{1\to 2}^{l}\), \(C_{(01)}=u_{3\to 2}^{l}\) and \(C_{(11)}=u_{1\to 2}^{l}+u_{3\to 2}^{l}\) with \(\left\{\mathbf{y}_{k+1}\right\}_{2}\). 3. When at least one case satisfies the above matching condition, the \(q\)-th PostN determines the pattern that minimizes \(\left\{\mathbf{y}_{k+1}\right\}_{q}-C_{\mathbf{p}}\). The \(q\)-th PostN then passes the value corresponding to determined pattern \(\mathbf{p}\) to the neighbor PreNs. For validated edges, the outgoing message is set to the incoming edge. For pruned edges whose corresponding entry in \(\mathbf{p}\) is zero, no message is passed. If no pattern is confirmed, the differential message \(\sum_{v\in V_{q}\backslash\left\{p\right\}}u_{v\to q}^{l}\), where \(\mathrm{V}_{q}\) is the set of neighbors of \(q\), is generated and sent to each individual neighbor PreN \(p\). For example, in Figure 5b, the second PostN does not find a satisfying candidate, passes the \(\left\{\mathbf{y}_{k+1}\right\}_{2}-u_{3\to 2}^{l}\) value to the first PreN and the \(\left\{\mathbf{y}_{k+1}\right\}_{2}-u_{1\to 2}^{l}\) value to the third PreN. 4. In the \((l+1)\)-th iterative message-passing process (\(l\geq 1\)), the PreNs and the PostNs are performed in the same manner. A threshold-based check is performed on all candidates and if a satisfactory candidate is found, it is determined and passed. If a satisfactory candidate is not found, a differential message is generated and passed. 5. If all PreNs and PostNs are satisfied, or the number of iteration for message-passing reaches a predetermined maximum number, the demodulation is terminated. If the message-passing between the \(k\)-th symbol and the \((k+1)\)-th symbol is performed, a reduced trellis graph is obtained.