# Wireless Covert Communication with Polarization Dirty Constellation
## 4 Wireless Covert Channels with Polarized Dirty Constellation
### Maximum Likelihood Decoding  
#### 4.4.1 A Successive Cancellation (SC) Decoding  
Polar code is a Gn-coset code with parameter \((N,K,A,u_{A})\) where \(K\) is the code dimension and specifies the size of the information set \(A\). Cover message \(u_{1}^{N}\) would be encoded into \(x_{1}^{N}\), \(x_{1}^{N}\) would be transmitted through the channel \(W^{N}\) and [PERSON] would receive \(y_{1}^{N}\). Thus, [PERSON] needs a corresponding decoder that could generate an accurate estimate \(\hat{u}_{1}^{N}\) of \(u_{1}^{N}\) with given knowledge of \(A\), \(u_{a}\) and \(y_{1}^{N}\). Because parts of the codewords are frozen bits, the decoder can directly set \(\hat{u}_{Ac}=u_{Ac}\). The task is just to estimate \(\hat{u}_{A}\) of \(u_{A}\). Arikan has given a specific successive cancellation (SC) decoder. The SC decoder can generate its estimate of \(u_{A}\) with given parameter \((N,K,A,u_{A})\) by computing  
\[\hat{u}_{i}\triangleq\begin{cases}u_{Ac}&ifi\in Ac\\ h_{i}(y_{1}^{N},\hat{u}_{1}^{i-1})&ifi\in A,\end{cases} \tag{26}\]  
where \(i\in[1,N]\) and the decision functions are defined as  
\[h_{i}(y_{1}^{N},\hat{u}_{1}^{i-1})\triangleq\begin{cases}0,&ifL_{N}^{(i)}(y_{ 1}^{N},\hat{u}_{1}^{i-1})\geq 0\\ 1,&ifL_{N}^{(i)}(y_{1}^{N},\hat{u}_{1}^{i-1})<0,\end{cases} \tag{27}\]  
Figure 5: Symbol construction of subcarrier signal.  
Figure 6: Block extraction of covert information.  
and the Log-Likelihood Ratio (LLR) can be expressed as  
\[L_{N}^{(i)}(y_{1}^{N},\hat{u}_{1}^{i-1})\triangleq\ln\left(\frac{W_{N}^{(i)}(y_{1 }^{N},\hat{u}_{1}^{i-1}|0)}{W_{N}^{(i)}(y_{1}^{N},\hat{u}_{1}^{i-1}|1)}\right). \tag{28}\]  
To calculate the LLR, we can use function \(f\) and function \(g\)  
\[\left\{\begin{aligned} f(a,b)&\triangleq\ln(\frac{1 +e^{a+b}}{e^{a}+e^{b}})\\ g(a,b,u_{s})&\triangleq(-1)^{u_{s}}a+b.\end{aligned}\right. \tag{29}\]  
We can equivalently express the LLR as  
\[\left\{\begin{aligned} L_{N}^{(2i-1)}\left(y_{1}^{N},\hat{u}_{1}^{2 i-2}\right)&=f\left(L_{N/2}^{(i)}\left(y_{1}^{N/2}\,,\hat{u}_{1,\omega}^{2 i-2}\oplus\hat{u}_{1,\epsilon}^{2i-2}\right),L_{N/2}^{(i)}\left(y_{N/2\, +1}^{N},\hat{u}_{1,\epsilon}^{2i-2}\right)\right)\\ L_{N}^{(2i)}\left(y_{1}^{N},\hat{u}_{1}^{2i-1}\right)& =g\left(L_{N/2}^{(i)}\left(y_{1}^{N/2}\,,\hat{u}_{1,\omega}^{2i-2 }\oplus\hat{u}_{1,\epsilon}^{2i-2}\right),L_{N/2}^{(i)}\left(y_{N/2\,+1}^{N}, \hat{u}_{1,\epsilon}^{2i-2}\right),\hat{u}_{2i-1}\right).\end{aligned}\right. \tag{30}\]  
Thus, the task of calculating an LLR at length \(N\) is converted to calculating two LLRs at length \(N/2\). This recursion can be continued down until the block length is 1, at which point the LLRs can be computed directly. To estimate the complexity of LLR calculations, we denote the Kolmogorov complexity of decoding over \(k\in[N,N/2,N/4,\cdots,1]\) as \(K_{L}(k)\). We have the complexity bound  
\[K_{L}(k)\leq 2K_{L}(k/2)+c_{A}, \tag{31}\]  
where \(c_{A}\) is the worst-case complexity of combining two LLRs at length \(k/2\) into an LLR at length \(k\). We can obtain the bound  
\[K_{L}(N)\leq NK_{L}(1)+c_{A}=\mathcal{O}(N). \tag{32}\]  
We can obtain the overall decoder complexity  
\[K_{D}(N)\leq KK_{L}(N)\leq NK_{L}(N)=\mathcal{O}(N^{2}). \tag{33}\]  
This overall complexity corresponds to a decoder whose DEs work privately. By sharing any partial results between DEs, the decoder could have a more efficient implementation with overall complexity \(\mathcal{O}(N\log N)\).