{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,24]],"date-time":"2025-12-24T12:41:43Z","timestamp":1766580103900,"version":"build-2065373602"},"reference-count":36,"publisher":"MDPI AG","issue":"10","license":[{"start":{"date-parts":[[2019,10,18]],"date-time":"2019-10-18T00:00:00Z","timestamp":1571356800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Early Postdoc Mobility fellowship","award":["168504"],"award-info":[{"award-number":["168504"]}]},{"DOI":"10.13039\/501100001711","name":"Swiss National Science Foundation","doi-asserted-by":"publisher","award":["200021_156672\/1"],"award-info":[{"award-number":["200021_156672\/1"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>We consider the primitive relay channel, where the source sends a message to the relay and to the destination, and the relay helps the communication by transmitting an additional message to the destination via a separate channel. Two well-known coding techniques have been introduced for this setting: decode-and-forward and compress-and-forward. In decode-and-forward, the relay completely decodes the message and sends some information to the destination; in compress-and-forward, the relay does not decode, and it sends a compressed version of the received signal to the destination using Wyner\u2013Ziv coding. In this paper, we present a novel coding paradigm that provides an improved achievable rate for the primitive relay channel. The idea is to combine compress-and-forward and decode-and-forward via a chaining construction. We transmit over pairs of blocks: in the first block, we use compress-and-forward; and, in the second block, we use decode-and-forward. More specifically, in the first block, the relay does not decode, it compresses the received signal via Wyner\u2013Ziv, and it sends only part of the compression to the destination. In the second block, the relay completely decodes the message, it sends some information to the destination, and it also sends the remaining part of the compression coming from the first block. By doing so, we are able to strictly outperform both compress-and-forward and decode-and-forward. Note that the proposed coding scheme can be implemented with polar codes. As such, it has the typical attractive properties of polar coding schemes, namely, quasi-linear encoding and decoding complexity, and error probability that decays at super-polynomial speed. As a running example, we take into account the special case of the erasure relay channel, and we provide a comparison between the rates achievable by our proposed scheme and the existing upper and lower bounds.<\/jats:p>","DOI":"10.3390\/a12100218","type":"journal-article","created":{"date-parts":[[2019,10,18]],"date-time":"2019-10-18T11:24:15Z","timestamp":1571397855000},"page":"218","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["A New Coding Paradigm for the Primitive Relay Channel"],"prefix":"10.3390","volume":"12","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3242-7020","authenticated-orcid":false,"given":"Marco","family":"Mondelli","sequence":"first","affiliation":[{"name":"Institute of Science and Technology (IST) Austria, 3400 Klosterneuburg, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S. Hamed","family":"Hassani","sequence":"additional","affiliation":[{"name":"Department of Electrical and Systems Engineering, University of Pennsylvania, Philadelphia, PA 19104, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"R\u00fcdiger","family":"Urbanke","sequence":"additional","affiliation":[{"name":"School of Computer and Communication Sciences, EPFL, CH-1015 Lausanne, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2019,10,18]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"120","DOI":"10.2307\/1426331","article-title":"Three-terminal communication channels","volume":"3","year":"1971","journal-title":"Adv. Appl. Probab."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"572","DOI":"10.1109\/TIT.1979.1056084","article-title":"Capacity theorems for the relay channel","volume":"25","author":"Cover","year":"1979","journal-title":"IEEE Trans. Inform. Theory"},{"key":"ref_3","unstructured":"Schein, B., and Gallager, R. (2000, January 25\u201330). The Gaussian parallel relay network. Proceedings of the 2000 IEEE International Symposium on Information Theory, Sorrento, Italy."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"1872","DOI":"10.1109\/TIT.2011.2110110","article-title":"Wireless Network Information Flow: A Deterministic Approach","volume":"57","author":"Avestimehr","year":"2011","journal-title":"IEEE Trans. Inform. Theory"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"6463","DOI":"10.1109\/TIT.2011.2165816","article-title":"Compute-and-forward: Harnessing interference through structured codes","volume":"57","author":"Nazer","year":"2011","journal-title":"IEEE Trans. Inform. Theory"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"3132","DOI":"10.1109\/TIT.2011.2119930","article-title":"Noisy network coding","volume":"57","author":"Lim","year":"2011","journal-title":"IEEE Trans. Inform. Theory"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"1509","DOI":"10.1109\/TIT.2015.2401000","article-title":"A unified approach to hybrid coding","volume":"61","author":"Minero","year":"2015","journal-title":"IEEE Trans. Inform. Theory"},{"key":"ref_8","unstructured":"Zahedi, S. (2005). On Reliable Communication over Relay Channels. [Ph.D. Thesis, Stanford University]."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"536","DOI":"10.1109\/TIT.1982.1056502","article-title":"The capacity of the semideterministic relay channel","volume":"28","author":"Gamal","year":"1982","journal-title":"IEEE Trans. Inform. Theory"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"1328","DOI":"10.1109\/TIT.2007.915921","article-title":"Capacity of a class of deterministic relay channels","volume":"54","author":"Kim","year":"2008","journal-title":"IEEE Trans. Inform. Theory"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"1106","DOI":"10.1109\/18.21243","article-title":"Partial converse for a relay channel","volume":"34","author":"Zhang","year":"1988","journal-title":"IEEE Trans. Inform. Theory"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"921","DOI":"10.1109\/TIT.2008.2011518","article-title":"Capacity of a class of modulo-sum relay channels","volume":"55","author":"Aleksic","year":"2009","journal-title":"IEEE Trans. Inform. Theory"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"4786","DOI":"10.1109\/TIT.2014.2328591","article-title":"A new upper bound on the capacity of a primitive relay channel based on channel simulation","volume":"60","author":"Xue","year":"2014","journal-title":"IEEE Trans. Inform. Theory"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"2254","DOI":"10.1109\/TIT.2017.2664811","article-title":"Improving on the Cut-Set Bound via Geometric Analysis of Typical Sets","volume":"63","author":"Wu","year":"2017","journal-title":"IEEE Trans. Inform. Theory"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Wu, X., and \u00d6zg\u00fcr, A. (2016, January 10\u201315). Improving on the cut-set bound for general primitive relay channels. Proceedings of the 2016 IEEE International Symposium on Information Theory (ISIT), Barcelona, Spain.","DOI":"10.1109\/ISIT.2016.7541584"},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Wu, X., and \u00d6zg\u00fcr, A. (2015, January 29). Cut-set bound is loose for Gaussian relay networks. Proceedings of the Allerton Conference on Communication, Control, and Computing, Monticello, IL, USA.","DOI":"10.1109\/ALLERTON.2015.7447136"},{"key":"ref_17","unstructured":"Gamal, A.E., and Kim, Y.H. (2011). Network Information Theory, Cambridge University Press."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1561\/0100000028","article-title":"Topics in Multi-User Information Theory","volume":"4","author":"Kramer","year":"2007","journal-title":"Found. Trends Commun. Inf. Theory"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"3051","DOI":"10.1109\/TIT.2009.2021379","article-title":"Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels","volume":"55","year":"2009","journal-title":"IEEE Trans. Inform. Theory"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"752","DOI":"10.1109\/LCOMM.2010.08.100875","article-title":"Nested polar codes for wiretap and relay channels","volume":"14","author":"Andersson","year":"2010","journal-title":"IEEE Commun. Lett."},{"key":"ref_21","unstructured":"Karzand, M. (March, January 29). Polar codes for degraded relay channels. Proceedings of the International Zurich Seminar on Communication, Zurich, Switzerland."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"3263","DOI":"10.1109\/TCOMM.2012.081412.110266","article-title":"Polar Codes for Cooperative Relaying","volume":"60","author":"Thobaben","year":"2012","journal-title":"IEEE Trans. Commun."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1109\/WCL.2013.111213.130639","article-title":"Smart decode-and-forward relaying with polar codes","volume":"3","author":"Karas","year":"2014","journal-title":"IEEE Wirel. Comm. Lett."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Wang, L. (2015, January 14\u201319). Polar coding for relay channels. Proceedings of the International Symposium on Information Theory, Hong Kong, China.","DOI":"10.1109\/ISIT.2015.7282712"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"1977","DOI":"10.1109\/TIT.2013.2294373","article-title":"Soft-Decoding-Based Strategies for Relay and Interference Channels: Analysis and Achievable Rates Using LDPC Codes","volume":"60","author":"Bennatan","year":"2014","journal-title":"IEEE Trans. Inform. Theory"},{"key":"ref_26","unstructured":"Kim, Y.H. (2007, January 26\u201328). Coding techniques for primitive relay channels. Proceedings of the Allerton Conference on Communication, Control, and Computing, Monticello, NY, USA."},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Hassani, S.H., and Urbanke, R. (2013). Universal Polar Codes. arXiv.","DOI":"10.1109\/ISIT.2014.6875073"},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"\u015ea\u015fo\u011flu, E., and Vardy, A. (2013, January 7\u201312). A new polar coding scheme for strong security on wiretap channels. Proceedings of the IEEE International Symposium on Information Theory, Istanbul, Turkey.","DOI":"10.1109\/ISIT.2013.6620400"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"783","DOI":"10.1109\/TIT.2014.2368555","article-title":"Achieving Marton\u2019s Region for Broadcast Channels Using Polar Codes","volume":"61","author":"Mondelli","year":"2015","journal-title":"IEEE Trans. Inform. Theory"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"2410","DOI":"10.1109\/TIT.2016.2539145","article-title":"Polar Coding for the Broadcast Channel With Confidential Messages: A Random Binning Analogy","volume":"62","author":"Chou","year":"2016","journal-title":"IEEE Trans. Inform. Theory"},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"3371","DOI":"10.1109\/TIT.2018.2789885","article-title":"How to achieve the capacity of asymmetric channels","volume":"64","author":"Mondelli","year":"2018","journal-title":"IEEE Trans. Inform. Theory"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"4024","DOI":"10.1109\/TIT.2016.2539967","article-title":"Asymmetric Error Correction and Flash-Memory Rewriting using Polar Codes","volume":"62","author":"Gad","year":"2016","journal-title":"IEEE Trans. Inform. Theory"},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"278","DOI":"10.1109\/JSAC.2015.2504275","article-title":"Polar Coding for the General Wiretap Channel With Extensions to Multiuser Scenarios","volume":"34","author":"Wei","year":"2016","journal-title":"IEEE J. Sel. Areas Commun."},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Mondelli, M., Hassani, S.H., and Urbanke, R. (2018, January 17\u201322). A New Coding Paradigm for the Primitive Relay Channel. Proceedings of the IEEE International Symposium on Information Theory, Vail, CO, USA.","DOI":"10.1109\/ISIT.2018.8437479"},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"1280","DOI":"10.1109\/TIT.2016.2514343","article-title":"Capacity of a class of state-dependent orthogonal relay channels","volume":"62","author":"Aguerri","year":"2016","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"7620","DOI":"10.1109\/TIT.2017.2756668","article-title":"Capacity-Achieving Rate-Compatible Polar Codes","volume":"63","author":"Hong","year":"2017","journal-title":"IEEE Trans. Inform. Theory"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/10\/218\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T13:27:30Z","timestamp":1760189250000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/10\/218"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,10,18]]},"references-count":36,"journal-issue":{"issue":"10","published-online":{"date-parts":[[2019,10]]}},"alternative-id":["a12100218"],"URL":"https:\/\/doi.org\/10.3390\/a12100218","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2019,10,18]]}}}