# A New Coding Paradigm for the Primitive Relay Channel +
## 3 Main Result
: _Consider the transmission over the erasure relay channel, where \(Y_{\text{SD}}\) is obtained from \(X_{\hat{s}}\) via a BEC\((\varepsilon_{\text{SD}})\), \(Y_{\text{SR}}\) is obtained from \(X_{\hat{s}}\) via a BEC\((\varepsilon_{\text{SR}})\), \(\hat{Y}_{\text{SR}}\) is obtained from \(Y_{\text{SR}}\) via an BEC\((\varepsilon_{\text{SR}})\), and the relay is connected to the destination via a noiseless link with capacity \(C_{\text{RD}}\). Then, the rate_  
\[ \begin{split} R_{\text{new}}&=\frac{(C_{\text{RD}}- \max\{0,\varepsilon_{\text{SD}}-\varepsilon_{\text{SR}}\})(1-(\hat{\varepsilon }_{\text{SR}}\circ\varepsilon_{\text{SR}})\cdot\varepsilon_{\text{SD}})}{h_{2} (\varepsilon_{\text{SR}}\circ\hat{\varepsilon}_{\text{SR}})+\varepsilon_{ \text{SD}}(1-\varepsilon_{\text{SR}}\circ\hat{\varepsilon}_{\text{SR}})-(1- \varepsilon_{\text{SR}})h_{2}(\hat{\varepsilon}_{\text{SR}})-\max\{0, \varepsilon_{\text{SD}}-\varepsilon_{\text{SR}}\}}\\ &+\frac{\max\{1-\varepsilon_{\text{SR}},1-\varepsilon_{\text{SD}} \}(h_{2}(\varepsilon_{\text{SR}}\circ\hat{\varepsilon}_{\text{SR}})+ \varepsilon_{\text{SD}}(1-\varepsilon_{\text{SR}}\circ\hat{\varepsilon}_{\text{ SR}})-(1-\varepsilon_{\text{SR}})h_{2}(\hat{\varepsilon}_{\text{SR}})-C_{ \text{RD}})}{h_{2}(\varepsilon_{\text{SR}}\circ\hat{\varepsilon}_{\text{SR}})+ \varepsilon_{\text{SD}}(1-\varepsilon_{\text{SR}}\circ\hat{\varepsilon}_{\text{ SR}})-(1-\varepsilon_{\text{SR}})h_{2}(\hat{\varepsilon}_{\text{SR}})-\max\{0, \varepsilon_{\text{SD}}-\varepsilon_{\text{SR}}\}}\end{split}  \tag{36}\]  
_is achievable for any \(\varepsilon_{\text{SR}}\in[0,1]\) such that_  
\[1-\varepsilon_{\text{SR}}<1-\varepsilon_{\text{SD}}+C_{\text{RD}}, \tag{37}\] \[h_{2}(\varepsilon_{\text{SR}}\circ\hat{\varepsilon}_{\text{SR}})+ \varepsilon_{\text{SD}}(1-\varepsilon_{\text{SR}}\circ\hat{\varepsilon}_{\text{ SR}})-(1-\varepsilon_{\text{SR}})h_{2}(\hat{\varepsilon}_{\text{SR}})\geq C_{ \text{RD}}. \tag{38}\]_Furthermore, the rate (36) can be achieved by a polar coding scheme with encoding/decoding complexity \(\Theta(n\log n)\) and error probability \(O(2^{-n^{\beta}})\) for any \(\beta\in(0,1/2)\), where \(n\) is the block length._  
The proof of Corollary 1 easily follows from the application of Theorem 1 and of Formulas (25) and (26). We will now proceed with the proof of our main result. Proof of Theorem 1.: We start by presenting the main idea of our scheme. We split the transmission into two blocks. In the first block, we perform a variant of compress-and-forward: the relay does not decode the received sequence, but it sends a compressed description of it to the destination. However, differently from standard compress-and-forward, we require that (35) holds. Hence, we cannot transmit all the compressed description \(\hat{Y}_{\text{ss}}\) during the first block. In the second block, we perform decode-and-forward: the relay completely decodes the received sequence. Furthermore, we choose the length of the second block so that the relay can transmit the part of \(\hat{Y}_{\text{ss}}\) that was not sent in the previous block plus the new information needed to decode the second block. Let us now describe this scheme more in detail and provide the achievability proof of the rate (33). First, we deal with the case \(I(X_{\text{s}};Y_{\text{ss}})\geq I(X_{\text{s}};Y_{\text{sD}})\). Consider the transmission of the first block. Denote by \(n_{1}\) and \(R_{1}\) the block length and the rate of the message transmitted by the source, and let \(R_{1}\) approach from below \(I(X_{\text{s}};\hat{Y}_{\text{ss}},Y_{\text{sD}})\). The relay receives \(Y_{\text{ss}}\) and constructs the compressed description \(\hat{Y}_{\text{ss}}\). Recall that the destination receives the side information \(Y_{\text{sD}}\) from the source. Hence, by using Wyner-Ziv coding, the destination needs from the relay a number of bits approaching from above \(I(Y_{\text{ss}};\hat{Y}_{\text{ss}}\mid Y_{\text{sD}})\cdot n_{1}\), in order to decode the message sent by the source.