# A New Coding Paradigm for the Primitive Relay Channel +
## 3 Main Result  
We are now ready to state our new lower bound for the primitive relay channel. **Theorem 1**. : _Consider the transmission over a primitive relay channel, where the source sends \(X_{\rm S}\) to the relay and the destination, the relay receives \(Y_{\rm S0}\) from the source, and relay and destination are connected via a noiseless link with capacity \(C_{\rm BD}\). Furthermore, denote by \(\hat{Y}_{\rm S0}\) the compressed description of \(Y_{\rm S0}\) transmitted by the relay, and define \(I_{\rm max}=\max\{0,I(X_{\rm S};Y_{\rm S0})-I(X_{\rm S};Y_{\rm S0})\}\). Then, the following rate is achievable:_  
\[R_{\rm new}=\frac{\big{(}C_{\rm BD}-I_{\rm max}\big{)}I(X_{\rm S};\hat{Y}_{\rm S 0},Y_{\rm S0})+\max\{I(X_{\rm S};Y_{\rm S0}),I(X_{\rm S};Y_{\rm S0})\}\big{(}I (Y_{\rm S0};\hat{Y}_{\rm S0}\mid Y_{\rm S0})-C_{\rm BD}\big{)}}{I(Y_{\rm S0}; \hat{Y}_{\rm S0}\mid Y_{\rm S0})-I_{\rm max}}, \tag{33}\]for any joint distribution \(p_{X_{S}}p_{\hat{Y}_{\text{SR}}}|_{Y_{\text{SR}}}\) such that_  
\[I(X_{\hat{s}};Y_{\text{SR}}) <I(X_{\hat{s}};Y_{\text{SD}})+C_{\text{RD}}, \tag{34}\] \[I(Y_{\text{SR}};\hat{Y}_{\text{SR}}|Y_{\text{SD}}) \geq C_{\text{RD}}, \tag{35}\]  
_and where \(|\hat{\mathcal{Y}}_{\text{SR}}|\leq|\mathcal{Y}_{\text{SR}}|+1\). Furthermore, the rate (33) 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._  
**Remark 1**. : _If (34) does not hold, then decode-and-forward achieves the cut-set bound, and it is optimal. Furthermore, if (35) does not hold, then our scheme reduces to compress-and-forward, and the achievable rate is given by (23). As we will see in the proof, we have two slightly different schemes for the cases (i) \(I(X_{\hat{s}};Y_{\text{SR}})\geq I(X_{\hat{s}};Y_{\text{SD}})\) and (ii) \(I(X_{\hat{s}};Y_{\text{SR}})<I(X_{\hat{s}};Y_{\text{SD}})\). Thus, introducing the term \(I_{\max}\) allows us to write the achievable rate in a more compact form._  
**Remark 2**. : _The proposed scheme can be thought of as a particular form of time-sharing between decode-and-forward and compress-and-forward: in the first block, we are performing (a variant of) compress-and-forward, and, in the second block, we are performing decode-and-forward. However, we allow different time-sharing strategies across different channels: in the channel from relay to destination, part of the compressed message of the first block is sent together with the message of the second block. This is different from the 'classical' way of implementing time-sharing, which can be realized through the partial decode-compress-and-forward scheme, as described for example in [35]. In [35], in the same block, a part of the message is processed according to the decode-and-forward scheme, and the remaining part is processed according to the compress-and-forward scheme. Therefore, it is not clear that the rate achievable by our scheme can also be achieved by partial decode-compress-and-forward. In fact, in the special case considered in the numerical simulations of Section 4, our achievable rate strictly improves upon partial decode-compress-and-forward._  
**Remark 3**. : _The proposed scheme is based on a chaining construction. Chaining can be thought of as a form of block Markov encoding, where the joint distribution is over blocks of symbols (instead of being over a single symbol). As described in detail in the proof, at the relay, we generate the first block according to a first codebook; we repeat part of the first block into the second block; and we generate the rest of the second block according to a second codebook. Thus, the repetition of part of the first block into the second block can be interpreted as a particular joint distribution over pairs of blocks._  
The special case of the erasure relay channel is handled by the corollary below. **Corollary 1**.