# Trellis Tone Modulation Multiple-Access for Peer Discovery in D2D Networks
## 3 Trellis Tone Modulation Multiple-Access
### Trellis Tone Modulation Procedure  
In this subsection, we show the process of individual TTM. Assume that \(n\) transmitting UEs share the same DRU. Let \(U^{(i)}\) be a UE among the \(n\) ones. Also, let \(\mathbf{w}^{(i)}=\left[w_{1}^{(i)},w_{2}^{(i)},\,\cdots,\,w_{L}^{(i)}\right]\) be the discovery message of \(U^{(i)}\). \(\mathbf{w}^{(i)}\) are fragmented into \(N\) parts as mentioned in previous subsection. The trellis matrix is designed for the given discovery resource unit, a single trellis matrix \(\mathbf{T}\) is used for all \(n\) UEs. The tone index of the first symbol, \(t_{1}^{(i)}\) is determined by \(b_{0}\) bits of \(\mathbf{w}_{1}^{(i)}\). Since the number of tones is \(M\) in each symbol, a choice of single-tone can represent the maximum \(\left\lfloor\log_{2}M\right\rfloor\) bits. Thus, \(b_{0}\)-bits, \(b_{0}\leq\left\lfloor\log_{2}M\right\rfloor\) can be represented by the tone selection in the first symbol. For simplicity, we assume \(2^{b_{0}}\left\lvert M\right\rfloor\). The tone index set is partitioned into \(2^{b_{0}}\) groups and the choice of a group can represent \(b_{0}\) bits. Single tone selection is conducted uniform-randomly within the group determined by the message bits. Figure 3a shows an example of the tone selection where \(b_{0}\) is 2 and \(M\) is 12. If the \(\mathbf{w}_{1}^{(i)}\) is (0,1),  
Figure 2: (a) Example of trellis matrix \(\mathbf{T}\); (b) Corresponding trellis diagram. one of the 4-th, 5-th and 6-th tones can be randomly selected. In the example of Figure 3a, the selected tone is the 5-th tone, so \(t_{1}^{(i)}=5\). The tone indices of following symbols are determined by the previous tone index and the tone transition function. The tone index \(t_{k+1}^{(i)}\) of the \((k+1)\)-th symbol is determined by \(t_{k}^{(i)}\), \(\mathbf{w}_{k+1}^{(i)}\) and the tone transition function \(f_{T}(. )\), for \(k=1,\ \ldots,\ N-1\). For example, if \(t_{1}^{(i)}=5\) and \(\mathbf{w}_{2}^{(i)}=(0,1)\), \(t_{2}^{(i)}\)= \(f_{T}(5,\mathbf{w}_{2}^{(i)})=7\) as shown in Figure 3a. Figure 3a gives a more comprehensive illustration of the entire TTM process. If the discovery message intended to be transmitted by the UE is (0,1,0,1,1,1,0,0,...), the single-tone of the first symbol is determined as the fifth tone, which is one of the tones belong to the region corresponding to the first 2 bits (0,1), as described above. The single-tone of the second and subsequent symbols is determined according to the single-tone of the previous symbol and two bits message, respectively. Algorithm 1 summarizes the procedure of TTM for a UE. ```
Require: Message vector \(\mathbf{w}=(\mathbf{w}_{1}:\mathbf{w}_{2}:\ldots:\mathbf{w}_{N})\), trellis matrix \(\mathbf{T}\)  Determine \(t_{1}^{(i)}\) with \(\mathbf{w}_{1}^{(i)}\) and \(\mathbf{x}_{1}^{(i)}\gets t_{1}^{(i)}\)
```  
Note \(\mathbf{x}_{1}^{(i)}\) is the column vector the \(t_{1}^{(i)}\)-th element having only the value of \(\sqrt{P}\) and the other elements having a value of zero. for\(k=1\) to \(N-1\)do \(t_{k+1}^{(i)}=f_{T}(t_{k}^{(i)},\mathbf{w}_{k+1}^{(i)})\), \(\mathbf{x}_{k+1}^{(i)}\gets t_{k+1}^{(i)}\) endfor \(\mathbf{x}^{(i)}\leftarrow[\mathbf{x}_{1}^{(i)},\ldots,\mathbf{x}_{N}^{(i)}]\) ```
**Algorithm 1** Trellis Tone Modulation Procedure  
For use in the next section, we derive a relation over the OFDM signal domain, which is equivalent to (1). The tone-transition matrix \(\mathbf{H}_{k}^{(i)}\), which represents the form in which the tone transits from the previous \(k\)-th symbol to the \((k+1)\)-th symbol of the \(U^{(i)}\), is defined as a matrix that has an element in the \((t_{k}^{(i)},\ t_{k+1}^{(i)})\) position in the trellis matrix \(\mathbf{T}\) and all other elements are zero. Therefore, \(\mathbf{H}_{k}^{(i)}\) has only  
Figure 3: (**a**) Example of trellis tone modulation generated by referring to the trellis diagram in Figure 2; (**b**) Corresponding trellis tone modulation signal in orthogonal frequency division multiplexing (OFDM) resource grid. one nonzero element.