Explicit Rateless Codes for Memoryless Binary-Input Output-Symmetric Channels

by Benny Applebaum, Liron David, and Guy Even

Theory of Computing, Volume 14(4), pp. 1-29, 2018

Bibliography with links to cited articles

[1]   Benny Applebaum, Liron David, and Guy Even: Deterministic rateless codes for BSC. In Proc. 6th Innovations in Theoretical Computer Science Conf. (ITCS’15), pp. 31–40. ACM Press, 2015. [doi:10.1145/2688073.2688117, arXiv:1406.0157]

[2]   Hari Balakrishnan, Peter Iannucci, Jonathan Perry, and Devavrat Shah: De-randomizing Shannon: The design and analysis of a capacity-achieving rateless code, 2012. [arXiv:1206.0418]

[3]   Alexander Barg: Lecture notes ENEE 739C: Advanced topics in signal processing: Coding theory (lecture 4), 2003. Available from author’s website.

[4]   Alexander Barg and George David Forney, Jr.: Random codes: Minimum distances and error exponents. IEEE Trans. Inform. Theory, 48(9):2568–2573, 2002. [doi:10.1109/TIT.2002.800480]

[5]   Alexander Barg and Gilles Zémor: Error exponents of expander codes. IEEE Trans. Inform. Theory, 48(6):1725–1729, 2002. Preliminary version in ISIT’01. [doi:10.1109/TIT.2002.1003853]

[6]   Alexander Barg and Gilles Zémor: Error exponents of expander codes under linear-complexity decoding. SIAM J. Comput., 17(3):426–445, 2004. [doi:10.1137/S0895480102403799]

[7]   John W. Byers, Michael Luby, Michael Mitzenmacher, and Ashutosh Rege: A digital fountain approach to reliable distribution of bulk data. SIGCOMM Comput. Commun. Rev., 28(4):56–67, 1998. [doi:10.1145/285243.285258]

[8]   Giuseppe Caire and Daniela Tuninetti: The throughput of hybrid-ARQ protocols for the Gaussian collision channel. IEEE Trans. Inform. Theory, 47(5):1971–1988, 2001. [doi:10.1109/18.930931]

[9]   David Chase: Code combining–a maximum-likelihood decoding approach for combining an arbitrary number of noisy packets. IEEE Trans. Commun., 33(5):385–393, 1985. [doi:10.1109/TCOM.1985.1096314]

[10]   Uri Erez, Mitchell D. Trott, and Gregory W. Wornell: Rateless coding for Gaussian channels. IEEE Trans. Inform. Theory, 58(2):530–547, 2012. [doi:10.1109/TIT.2011.2173242, arXiv:0708.2575]

[11]   George David Forney, Jr.: Concatenated Codes. MIT Press, 1966.

[12]   Venkatesan Guruswami and Piotr Indyk: Linear-time encodable/decodable codes with near-optimal rate. IEEE Trans. Inform. Theory, 51(10):3393–3400, 2005. Preliminary version in STOC’02. [doi:10.1109/TIT.2005.855587]

[13]    Jeongseok Ha, Jaehong Kim, and Steven W. McLaughlin: Rate-compatible puncturing of low-density parity-check codes. IEEE Trans. Inform. Theory, 50(11):2824–2836, 2004. [doi:10.1109/TIT.2004.836667]

[14]   Joachim Hagenauer: Rate-compatible punctured convolutional codes (RCPC codes) and their applications. IEEE Trans. Commun., 36(4):389–400, 1988. [doi:10.1109/26.2763]

[15]   Tingfang Ji and Wayne Stark: Rate-adaptive transmission over correlated fading channels. IEEE Trans. Commun., 53(10):1663–1670, 2005. [doi:10.1109/TCOMM.2005.857147]

[16]   Shu Lin, Daniel Costello, and Michael Miller: Automatic-repeat-request error-control schemes. IEEE Communications Magazine, 22(12):5–17, 1984. [doi:10.1109/MCOM.1984.1091865]

[17]   Michael Luby: LT codes. In Proc. 43rd FOCS, pp. 271–280. IEEE Comp. Soc. Press, 2002. [doi:10.1109/SFCS.2002.1181950]

[18]   David Mandelbaum: An adaptive-feedback coding scheme using incremental redundancy. IEEE Trans. Inform. Theory, 20(3):388–389, 1974. [doi:10.1109/TIT.1974.1055215]

[19]   Jonathan Perry, Hari Balakrishnan, and Devavrat Shah: Rateless spinal codes. In Proc. 10th ACM Workshop on Hot Topics in Networks (HotNets-X’11), pp. 6:1–6:6. ACM Press, 2011. [doi:10.1145/2070562.2070568]

[20]   Jonathan Perry, Peter A. Iannucci, Kermin E. Fleming, Hari Balakrishnan, and Devavrat Shah: Spinal codes. In Proc. 2012 Conf. on Applications, Technologies, Architectures, and Protocols for Comput. Commun. (SIGCOMM’12), pp. 49–60. ACM Press, 2012. [doi:10.1145/2342356.2342363]

[21]   Gregory Poltyrev: Bounds on the decoding error probability of binary linear codes via their spectra. IEEE Trans. Inform. Theory, 40(4):1284–1292, 1994. [doi:10.1109/18.335935]

[22]   Doron Rajwan: Method of encoding and transmitting data over a communication medium through division and segmentation, 2007. US Patent 7,304,990.

[23]   Doron Rajwan, Eyal Lubetzky, and Joseph Yossi Azar: Data streaming, 2008. US Patent 7,327,761.

[24]   Douglas N. Rowitch and Laurence B. Milstein: On the performance of hybrid FEC/ARQ systems using rate compatible punctured turbo (RCPT) codes. IEEE Trans. Commun., 48(6):948–959, 2000. [doi:10.1109/26.848555]

[25]   Eren Şaşoğlu: Polar Coding Theorems for Discrete Systems. Ph. D. thesis, EPFL, 2011.

[26]   Stefania Sesia, Giuseppe Caire, and Guillaume Vivier: Incremental redundancy hybrid ARQ schemes based on low-density parity-check codes. IEEE Trans. Commun., 52(8):1311–1321, 2004. [doi:10.1109/TCOMM.2004.833022]

[27]   Amin Shokrollahi: Raptor codes. IEEE Trans. Inform. Theory, 52(6):2551–2567, 2006. [doi:10.1109/TIT.2006.874390]

[28]   Nadav Shulman: Communication over an Unknown Channel via Common Broadcasting. Ph. D. thesis, Tel Aviv University, 2003. LINK at SemanticScholar.

[29]   Nadav Shulman and Meir Feder: Random coding techniques for nonrandom codes. IEEE Trans. Inform. Theory, 45(6):2101–2104, 1999. [doi:10.1109/18.782147]

[30]   Nadav Shulman and Meir Feder: Static broadcasting. In Proc. 2000 IEEE Internat. Symp. on Inform. Theory (ISIT’00), p. 23. IEEE Comp. Soc. Press, 2000. [doi:10.1109/ISIT.2000.866313]

[31]   Daniel A. Spielman: Computationally efficient error-correcting codes and holographic proofs. Ph. D. thesis, MIT, 1996. Available at DSpace@MIT.

[32]   Daniel A. Spielman: Linear-time encodable and decodable error-correcting codes. IEEE Trans. Inform. Theory, 42(6):1723–1731, 1996. Preliminary version in STOC’95. [doi:10.1109/18.556668]