# A New Coding Paradigm for the Primitive Relay Channel +
## 2 Existing Upper and Lower Bounds
### Improvements on a Cut-Set Upper Bound  
For the case of the _primitive relay channel_, an upper bound demonstrating an explicit gap to the cut-set bound was presented in [13]. Furthermore, two new upper bounds that are generally tighter than cut-set are proposed in [14] for the symmetric primitive relay channel, in which \(Y_{\text{\tiny SR}}\) and \(Y_{\text{\tiny SD}}\) are conditionally identically distributed given \(X_{\text{\tiny S}}\). The results of [14] are extended to the non-symmetric case and to the Gaussian case in [15; 16], respectively.  
Let us now state the result in ([15] Theorem 3.1), which provides an extension of the first bound of [14]. If a rate \(R\) is achievable, then there exists some \(p_{X_{\text{\tiny S}}}(x_{\text{\tiny S}})\) and \(a\geq 0\) such that  
\[\left\{\begin{array}{l}R\leq I(X_{\text{\tiny S}};Y_{\text{\tiny SR}},Y_{ \text{\tiny SD}}),\\ \\ R\leq I(X_{\text{\tiny S}};Y_{\text{\tiny SD}})+C_{\text{\tiny RD}}-a,\\ \\ R\leq I(X_{\text{\tiny S}};Y_{\text{\tiny SD}},\tilde{Y}_{\text{\tiny SR}})+h_{2 }\left(\sqrt{\frac{a\ln 2}{2}}\right)+\sqrt{\frac{a\ln 2}{2}}\log_{2}(|Y_{ \text{\tiny SR}}|-1)-a,\end{array}\right. \tag{4}\]  
for any random variable \(\tilde{Y}_{\text{\tiny SR}}\) with the same conditional distribution as \(Y_{\text{\tiny SR}}\) given \(X_{\text{\tiny S}}\). The evaluation of the term \(I(X_{\text{\tiny S}};Y_{\text{\tiny SD}},\tilde{Y}_{\text{\tiny SR}})\) that gives the tightest bound is simple in the following special cases:  
1. _Symmetric_ (\(Y_{\text{\tiny SR}}\) and \(Y_{\text{\tiny SD}}\) are conditionally identically distributed given \(X_{\text{\tiny S}}\)): \(I(X_{\text{\tiny S}};Y_{\text{\tiny SD}},\tilde{Y}_{\text{\tiny SR}})=I(X_{ \text{\tiny S}};Y_{\text{\tiny SD}})\).
2. _Degraded_ (\(Y_{\text{\tiny SD}}\) is a stochastically degraded version of \(Y_{\text{\tiny SR}}\)): \(I(X_{\text{\tiny S}};Y_{\text{\tiny SD}},\tilde{Y}_{\text{\tiny SR}})=I(X_{ \text{\tiny S}};Y_{\text{\tiny SR}})\).
3. _Reversely degraded_ (\(Y_{\text{\tiny SR}}\) is a stochastically degraded version of \(Y_{\text{\tiny SD}}\)): \(I(X_{\text{\tiny S}};Y_{\text{\tiny SD}},\tilde{Y}_{\text{\tiny SR}})=I(X_{ \text{\tiny S}};Y_{\text{\tiny SD}})\).  
For the special case of the erasure relay channel, the bound can be re-written as  
\[R\leq\max_{a\geq 0}\min\Biggl{\{}1-\varepsilon_{\text{\tiny SR}}\varepsilon_  
and \(H(p(\omega|x)|p(x))\) is the conditional entropy similarly defined with respect to \(p(x)p(\omega|x)\). At this point, we can state the result in ([14] Theorem 4.2). If a rate \(R\) is achievable, then there exists some \(p_{X_{\rm S}}(x_{\rm s})\) and \(a\in[0,\min\{C_{\rm RD},H(Y_{\rm SR}\mid X_{\rm s})\}]\) such that  
\[\left\{\begin{array}{l}R\leq I(X_{\rm S};Y_{\rm SR},Y_{\rm SD}),\\ R\leq I(X_{\rm S};Y_{\rm SD})+C_{\rm RD}-a,\\ R\leq I(X_{\rm S};Y_{\rm SD})+\Delta\left(p_{X_{\rm S}}(x_{\rm s}),\sqrt{\frac{ a\ln 2}{2}}\right).\end{array}\right. \tag{10}\]  
As pointed out at the end of Section IV.C of [14], for the special case of the symmetric erasure relay channel, we have that \(\Delta(p_{X_{\rm S}}(x_{\rm s}),d)=\infty\) for all \(p_{X_{\rm S}}(x_{\rm s})\) and \(d>0\). Thus, formula (10) reduces to the cut-set bound (3).