# Trellis Tone Modulation Multiple-Access for Peer Discovery in D2D Networks
## 4 Multi-User Detection of TTMMA via Message-Passing  
In this section, we describe the process of multi-user detection via a message-passing algorithm. This multi-user detection algorithm is effective in both single user and multiple user scenarios. Figure 4: Conceptual description of multiple-access of trellis tone modulation (TTM) signals. In addition, we propose some supplementary techniques such as tone-space expansion, pre-prediction, etc., for efficient realization of the message-passing-based multi-user detection. At the transmitter, \(\mathbf{w}_{1}^{(i)}\) is represented only by \(\mathbf{x}_{1}^{(i)}\) and then, \(\mathbf{x}_{k+1}^{(i)}\) is generated only depending on \(\mathbf{w}_{k+1}^{(i)}\) and \(\mathbf{x}_{k}^{(i)}\) for \(k\geq 2\). Since the modulation of TTMMA discovery signal is Markovian, \(\mathbf{w}_{k+1}^{(i)}\) can separately be determined by the tone transition from \(\mathbf{x}_{k}^{(i)}\) to \(\mathbf{x}_{k+1}^{(i)}\). Therefore, the receiver carries out multi-user detection by using only \(\mathbf{y}_{k}\) and \(\mathbf{y}_{k+1}\) to find \(\mathbf{w}_{k}^{(i)}\) for each \(k\), where \(\mathbf{y}_{k}\) is the \(k\)-th column vector of \(\mathbf{Y}\). Now let us focus on the multi-user detection procedure between \(\mathbf{y}_{k}\) and \(\mathbf{y}_{k+1}\) to find \(\mathbf{w}_{k}^{(i)}\) for all \(i\). From (3), \(\mathbf{y}_{k}\) is broken down as  
\[\mathbf{y}_{k}=\sum_{i=1}^{n}c^{(i)}\mathbf{x}_{k}^{(i)}+\mathbf{z}_{k}= \widetilde{\mathbf{x}}_{k}+\mathbf{z}_{k} \tag{4}\]  
where \(\widetilde{\mathbf{x}}_{k}=\sum_{i=1}^{n}c^{(i)}\mathbf{x}_{k}^{(i)}\) and \(\mathbf{z}_{k}\in\mathbb{C}^{M}\) is the corresponding noise vector and \(\mathbf{y}_{k+1}\) is given by  
\[\mathbf{y}_{k+1}=\sum_{i=1}^{n}c^{(i)}\mathbf{x}_{k+1}^{(i)}+\mathbf{z}_{k+1 }=\sum_{i=1}^{n}c^{(i)}(\mathbf{H}_{k}^{(i)}\mathbf{x}_{k}^{(i)})+\mathbf{z}_ {k+1}=\sum_{i=1}^{n}\mathbf{H}_{k}^{(i)}(c^{(i)}\mathbf{x}_{k}^{(i)})+\mathbf{ z}_{k+1} \tag{5}\]  
Then we derive the optimal joint detection problem given by  
\[\{\mathbf{\hat{H}}_{k}^{(i)}\}_{i=1}^{n}=\operatorname*{argmin}_{\mathbf{A}_ {i}}\|\mathbf{y}_{k+1}-\sum_{i=1}^{n}\mathbf{A}_{i}(c^{(i)}\mathbf{x}_{k}^{(i )})+\mathbf{z}_{k+1}\| \tag{6}\]  
where \(\mathbf{A}_{i}\) is a possible form of \(\mathbf{H}_{k}^{(i)}\). There is only one non-zero element \(1\) in \(\mathbf{H}_{k}^{(i)}\) and the number of possible locations of the non-zero element is \(dM\). Thus, the joint ML of (5) requires \((dM)^{n}\) comparisons and even \(n\) is unknown to the receiver. Thus, it is impractical to be exploited. Therefore, using the sparsity of \(\mathbf{H}_{k}^{(i)}\) and \(\mathbf{x}_{k}^{(i)}\), we modify (5) into an easy-to-solve form, that is given by  
\[\mathbf{y}_{k+1}=\mathbf{H}_{k}\left(\sum_{i=1}^{n}c^{(i)}\mathbf{x}_{k}^{(i )}\right)+\mathbf{z}_{k+1}=\mathbf{H}_{k}\widetilde{\mathbf{x}}_{k}+\mathbf{ z}_{k+1} \tag{7}\]  
where \(\mathbf{H}_{k}\in\mathbb{R}^{M\times M}\) is a newly defined multiple-access tone-transition matrix. Since trellis tone modulated signals of multiple UEs are superposed and separated across the symbols, \(\mathbf{H}_{k}\) is no longer a binary matrix, but a real matrix. The number of non-zero elements is less than or equal to \(n\) and the possible locations of non-zero elements in \(\mathbf{H}_{k}\) is still restricted by \(\mathbf{T}\). Now the multi-user detection problem is to find \(\mathbf{H}_{k}\) instead of finding \(\mathbf{H}_{k}^{(i)}\) for all \(i\). After obtaining \(\mathbf{H}_{k}\), we decompose \(\mathbf{H}_{k}\) into \(\mathbf{H}_{k}^{(i)}\) by applying a combinatorial method to \(\mathbf{H}_{k}\) for all \(k\). From (4) and (7),  
\[\mathbf{y}_{k+1}=\mathbf{H}_{k}(\mathbf{y}_{k}-\mathbf{z}_{k})+\mathbf{z}_{k+1} \tag{8}\]  
The problem in (8) is different from the conventional one of linear equations.