Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Wireless Personal Communications
Erschienen in: Wireless Personal Communications 2/2014

01.07.2014

Towards Fountain Codes

verfasst von: Seyed Masoud Mirrezaei, Karim Faez, Shahram Yousefi

Erschienen in: Wireless Personal Communications | Ausgabe 2/2014

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Fountain codes are a new class of codes originally designed for robust and scalable transmission of data over lossy computer networks. Binary Fountain codes such as Luby transform codes are a class of erasure codes which have demonstrated an asymptotic performance close to the Shannon limit when decoded with the belief propagation algorithm. Although structures have been extensively studied for low-density parity-check codes, to the best of our knowledge, they have never been fully explored for Fountain codes and there is no survey for them. Thus, we will introduce the \(G\)-based tanner graph and the properties of Fountain codes as rateless low-density generator-matrix codes in this survey. Most of the work carried out during the previous years has been presented.
Vorheriger Artikel An Empirical Examination of Initial Trust in Mobile Payment
Nächster Artikel Towards Fountain Codes. Part II: Belief Propagation Decoding

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Literatur
1.
Mitzenmacher, M. (2004). Digital fountains: a survey and look forward. In Information theory workshop, 2004 (pp. 271–276). IEEE.
2.
MacKay, D. J. (2003). Information theory, inference and learning algorithms. Cambridge: Cambridge university press.MATH
3.
MacKay, D. J. (2005). Fountain codes. In Communications, IEE proceedings (Vol. 152, IET, pp. 1062–1068).
4.
Byers, J. W., Luby, M., Mitzenmacher, M., & Rege, A. (1998). A digital fountain approach to reliable distribution of bulk data. ACM SIGCOMM Computer Communication Review, 28, 56–67.CrossRef
5.
6.
Mandelbaum, D. (1974). An adaptive-feedback coding scheme using incremental redundancy (corresp.). IEEE Transactions on Information Theory, 20(3), 388–389.CrossRefMATHMathSciNet
7.
Sesia, S., Caire, G., & Vivier, G. (2004). Incremental redundancy hybrid arq schemes based on low-density parity-check codes. IEEE Transactions on Communications, 52(8), 1311–1321.CrossRef
8.
Hagenauer, J. (1988). Rate-compatible punctured convolutional codes (RCPC codes) and their applications. IEEE Transactions on Communications, 36(4), 389–400.CrossRef
9.
Luby, M. (2002). Lt codes. In Annual symposium on foundations of computer science, 2002 (pp. 271–280).
10.
Pearl, J. (1988). Probabilistic reasoning in intelligent systems: Networks of plausble inference. Los Altos, CA: Morgan Kaufmann Pub.
11.
Garcia-Frias, J., & Zhong, W. (2003). Approaching shannon performance by iterative decoding of linear codes with low-density generator matrix. Communications Letters, IEEE, 7(6), 266–268.CrossRef
12.
Etesami, O., & Shokrollahi, A. (2006). Raptor codes on binary memoryless symmetric channels. IEEE Transactions on Information Theory, 52(5), 2033–2051.CrossRefMathSciNet
13.
14.
Castura, J., & Mao, Y. (2006). Rateless coding over fading channels. Communications Letters, IEEE, 10(1), 46–48.CrossRef
15.
Cao, Y., & Blostein, S. D. (2008). Raptor codes for hybrid error-erasure channels with memory. Communications. 2008. 24th Biennial symposium on (pp. 84–88). IEEE.
16.
Orozco, V. L., & Yousefi, S. (2010). Trapping sets of fountain codes. Communications Letters, IEEE, 14(8), 755–757.CrossRef
17.
MacKay, D. J., & Postol, M. S. (2003). Weaknesses of margulis and ramanujan-margulis low-density parity-check codes. Electronic Notes in Theoretical Computer Science, 74, 97–104.CrossRef
18.
Richardson, T. (2003). Error floors of LDPC codes. In Proceedings of the annual Allerton conference on communication control and computing (Vol. 41, pp. 1426–1435). The University; 1998.
19.
Laendner, S., & Milenkovic, O. (2007). Ldpc codes based on latin squares: Cycle structure, stopping set, and trapping set analysis. IEEE Transactions on Communications, 55(2), 303–312.CrossRef
20.
Han, Y., & Ryan, W. E. (2008). LDPC decoder strategies for achieving low error floors. In Information theory and applications workshop, 2008 (pp. 277–286). IEEE.
21.
Ivkovic, M., Chilappagari, S. K., & Vasic, B. (2008). Eliminating trapping sets in low-density parity-check codes by using tanner graph covers. IEEE Transactions on Information Theory, 54(8), 3763–3768.CrossRefMathSciNet
22.
Mirrezaei, S. M., Faez, K., & Yousefi, S. (2012). Absorbing sets of fountain codes over noisy channels. In Communications (QBSC). 2012. 26th Biennial symposium on (pp. 44–47). IEEE.
23.
24.
Gallager, R. (1963). Low-density parity-check codes. Ph.D. Thesis, M.I.T., Cambridge, MA.
25.
Reed, I. S., & Solomon, G. (1960). Polynomial codes over certain finite fields. Journal of the Society for Industrial & Applied Mathematics, 8(2), 300–304.CrossRefMATHMathSciNet
26.
Rizzo, L. (1997). Effective erasure codes for reliable computer communication protocols. ACM SIGCOMM Computer Communication Review, 27(2), 24–36.CrossRef
27.
Bloemer, J., Kalfane, M., Karp, R., Karpinski, M., Luby, M, & Zuckerman, D. (1995). An xor-based erasure-resilient coding scheme. ACM SIGCOMM Computer Communication, 8, 6–14.
28.
Byers, J. W., Luby, M., & Mitzenmacher, M. (2002). A digital fountain approach to asynchronous reliable multicast. IEEE Journal on Selected Areas in Communications, 20(8), 1528–1540.CrossRef
29.
Wang, M. H. (2012). A hybrid coding scheme that combines fountain codes and reed-solomon codes. Master’s thesis, University of Tokyo.
30.
Chen, X., Subramanian, V. G., & Leith, D. J. (2013). Phy modulation/rate control for fountain codes in 802.11 a/g wlans. Physical Communication. 7(8), 142–151.
31.
Cao, C., Fei, Z., Xiao, M., Huang, G., Xing, C., & Kuang, J. (2013). An extended packetization-aware mapping algorithm for scalable video coding in finite-length fountain codes. Science China Information Sciences, 56(4), 1–10.CrossRef
32.
Guo, T., Zhao, D., & Li, X. (2013). Study on the application of lt code technology in deep space communications. In Proceedings of the 26th conference of spacecraft TT &C technology in China (pp. 109–118). Springer.
33.
Ferreira, P., Jesus, B., Vieira, J., & Pinho, A. (2013). The rank of random binary matrices and distributed storage applications. Communications Letters, IEEE, 17(1), 151–154.
34.
Ellis, J. D., & Pursley, M. B. (2012). Adaptive-rate channel coding for packet radio systems with higher layer fountain coding. In Military communications conference, 2012-MILCOM 2012 (pp. 1–6). IEEE.
35.
Lu, H., Foh, C. H., Wen, Y., & Cai, J. (2012). Optimizing content retrieval delay for lt-based distributed cloud storage systems. In Global communications conference (GLOBECOM), 2012 (pp. 1920–1925). IEEE.
36.
Heo, K., & Yoon, C. (2012). An effective overlay multicast system using fountain codes based on p2p overlay network. In ICT convergence (ICTC), 2012 international conference on (pp. 370–372). IEEE.
37.
Luby, M. G., Mitzenmacher, M., Shokrollahi, M. A., & Spielman, D. A. (2001). Efficient erasure correcting codes. IEEE Transactions on Information Theory, 47(2), 569–584.CrossRefMATHMathSciNet
38.
Hussain, I., Xiao, M., & Rasmussen, L. (2013). Design of LT codes with equal and unequal erasure protection over binary erasure channels. Communications Letters, IEEE, 17(2), 261–264.
39.
Hyytia, E., Tirronen, T., & Virtamo, J. (2007). Optimal degree distribution for lt codes with small message length. INFOCOM 2007. In 26th IEEE international conference on computer communications (pp. 2576–2580). IEEE.
40.
Auguste, V., Charly, P., & David, D. (2009). Jointly decoded raptor codes: Analysis and design for the biawgn channel. EURASIP Journal on Wireless Communications and Networking.
41.
Richardson, T. J., Shokrollahi, M. A., & Urbanke, R. L. (2001). Design of capacity-approaching irregular low-density parity-check codes. IEEE Transactions on Information Theory, 47(2), 619–637.CrossRefMATHMathSciNet
42.
Richardson, T. J., & Urbanke, R. L. (2001). Efficient encoding of low-density parity-check codes. IEEE Transactions on Information Theory, 47(2), 638–656.CrossRefMATHMathSciNet
43.
Singels, R., du Preez, J., & Wolhuter, R. (2013). Soft decoding of raptor codes over AWGN channels using probabilistic graphical models. In 12th annual wireless telecommunications symposium, 2013 IEEE conference on.
44.
Chong, Z. K., Goi, B. M., Ohsaki, H., Ng, C. K. B., & Ewe, H. T. (2012). Design of short-length message fountain code for erasure channel transmission. In Sustainable utilization and development in engineering and technology (STUDENT), 2012 IEEE conference on (pp. 239–241). IEEE.
45.
Huang, W., Li, H., & Dill, J. (2011). Fountain codes with message passing and maximum likelihood decoding over erasure channels. In 10th annual wireless telecommunications symposium, 2011 IEEE conference on.
46.
Huang, W. (2012). Investigation on digital fountain codes over erasure channels and additive white gaussian noise channels. Ph.D. Thesis, Ohio University.
47.
Park, D., & Chung, S. Y. (2008). Performancecomplexity tradeoffs of rateless codes. In Information theory. 2008. ISIT 2008. IEEE international symposium on (pp. 2056–2060). IEEE.
48.
Jenkac, H., Mayer, T., Stockhammer, T., & Xu, W. (2005). Soft decoding of lt-codes for wireless broadcast. In Proceedings of IST mobile summit 2005.
49.
Palanki, R. (2004). Iterative decoding for wireless networks. Ph.D. Thesis, California Institute of Technology.
50.
Palanki, R., & Yedidia, J. S. (2004). Rateless codes on noisy channels. In Information theory, 2004. ISIT 2004. Proceedings. International symposium on (p. 37). IEEE.
51.
Hu, K., Castura, J., & Mao, Y. (2006). Wlc44-3: Reduced-complexity decoding of raptor codes over fading channels. In Global telecommunications conference. 2006. GLOBECOM’06 (pp. 1–5). IEEE.
52.
Castura, J., & Mao, Y. (2006). When is a message decodable over fading channels? In Communications, 2006. 23rd Biennial symposium on (Vol. 3, pp. 59–62). IEEE.
53.
Pishro-Nik, H., & Fekri, F. (2006). On raptor codes. In Communications, 2006. ICC’06. IEEE international conference on (Vol. 3, pp. 1137–1141). IEEE.
54.
Bonello, N., Zhang, R., Chen, S., & Hanzo, L. (2009). Reconfigurable rateless codes. IEEE Transactions on Wireless Communications, 8(11), 5592–5600.CrossRef
55.
Venkiah, A., Poulliat, C., & Declercq, D. (2007). Analysis and design of raptor codes for joint decoding using information content evolution. In Information theory, 2007. ISIT 2007. IEEE international symposium on (pp. 421–425). IEEE.
56.
Pakzad, P., & Shokrollahi, A. (2006). Design principles for raptor codes. In Information theory workshop. 2006. ITW’06 Punta del Este (pp. 165–169). IEEE.
57.
Cheng, Z., Castura, J., & Mao, Y. (2009). On the design of raptor codes for binary-input gaussian channels. IEEE Transactions on Communications, 57(11), 3269–3277.CrossRef
58.
Hu, K., Castura, J., & Mao, Y. (2007). Performance-complexity tradeoffs of raptor codes over gaussian channels. Communications Letters, IEEE, 11(4), 343–345.CrossRef
59.
AbduiHussein, A. (2008). Efficient decoding and application of rateless codes. Ph.D., Thesis, The University Of British Columbia.
60.
AbdulHussein, A., Oka, A., & Lampe, L. (2008). Decoding with early termination for raptor codes. Communications Letters, IEEE, 12(6), 444–446.CrossRef
61.
AbdulHussein, A., Oka, A., & Lampe, L. (2008). Decoding with early termination for rateless (luby transform) codes. In Wireless communications and networking conference, 2008. WCNC 2008 (pp. 249–254). IEEE.
62.
Yuan, L. (2012). Performance of min-sum for decoding fountain codes over biawgn channels. In Wireless communications, networking and mobile computing (WiCOM), 2012 8th international conference on (pp. 1–4). IEEE.
63.
Liu, X., & Lim, T. J. (2009). Fountain codes over fading relay channels. IEEE Transactions on Wireless Communications, 8(6), 3278–3287.CrossRef
64.
Richardson, T., & Urbanke, R. (2008). Modern coding theory. Cambridge: Cambridge University Press.CrossRefMATH
65.
Luby, M. G., Mitzenmacher, M., & Shokrollahi, M. A. (1998). Analysis of random processes via and-or tree evaluation. In Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms: Society for industrial and applied mathematics (pp. 364–373).
66.
Shao, H., Xu, D., & Zhang, X. (2013). Asymptotic analysis and optimization for generalized distributed fountain codes. Communications Letters, IEEE, 17(5), 988–991.
67.
Hussain, I., Xiao, M., & Rasmussen, L. K. (2011). Error floor analysis of lt codes over the additive white gaussian noise channel. In Global telecommunications conference (GLOBECOM 2011) (pp. 1–5). IEEE.
68.
Karp, R., Luby, M., & Shokrollahi, A. (2004). Finite length analysis of lt codes. In Information theory, 2004. ISIT. (2004). Proceedings international symposium on (p. 39). IEEE.
69.
Tee, R., Nguyen, T., Yang, L., & Hanzo, L. (2006). Serially concatenated luby transform coding and bit-interleaved coded modulation using iteratlive decoding for the wireless internet. In Vehicular technology conference. (2006). VTC 2006-Spring. IEEE 63rd (Vol. 1, pp. 22–26). IEEE.
70.
Grobler, T. L. (2008). Fountain codes and their typical application in wireless standards like edge. Ph.D. Thesis, University of Pretoria.
71.
Joshi, G., Rhim, J. B., Sun, J., & Wang, D. (2010). Fountain codes. In Global telecommunications conference (GLOBECOM 2010) (pp. 7–12). IEEE.
72.
Wiberg, N. (1996). Codes and decoding on general graphs. Citeseer. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing (pp. 121–129). ACM.
73.
Forney, G. D., Jr, Koetter, R., Kschischang, F. R., & Reznik, A. (2001). On the effective weights of pseudocodewords for codes defined on graphs with cycles. In Codes, systems, and graphical models (pp. 101–112). Springer.
74.
Di, C., Proietti, D., Telatar, I. E., Richardson, T. J., & Urbanke, R. L. (2002). Finite-length analysis of low-density parity-check codes on the binary erasure channel. IEEE Transactions on Information Theory, 48(6), 1570–1579.CrossRefMATHMathSciNet
75.
Mirrezaei, S. M., & Yousefi, S. (2012). A new fountain decoder escaping almost all absorbing sets. In Globecom workshops (GC Wkshps), 2012 (pp. 681–685). IEEE.
76.
Cavus, E., & Daneshrad, B. (2005). A performance improvement and error floor avoidance technique for belief propagation decoding of ldpc codes. In Personal, indoor and mobile radio communications. 2005. PIMRC 2005. IEEE 16th international symposium on (Vol. 4., pp. 2386–2390). IEEE.
77.
Laendner, S., Hehn, T., Milenkovic, O., & Huber, J. B. (2006). Cth02-4: When does one redundant parity-check equation matter? In Global telecommunications conference, 2006. GLOBECOM’06 (pp. 1–6). IEEE.
78.
McGregor, A., & Milenkovic, O. (2007). On the hardness of approximating stopping and trapping sets in LDPC codes. In Information theory workshop. (2007). ITW’07 (pp. 248–253). IEEE.
79.
Mirrezaei, S. M., Faez, K., & Yousefi, S. (2013). Analysis and design of a new fountain codec under belief propagation. IET Communications: 8(1), 27–40.
80.
Luby, M. G., Mitzenmacher, M., Shokrollahi, M. A., Spielman, D. A., & Stemann, V. (1997). Practical loss-resilient codes. In Proceedings of the twenty-ninth annual ACM symposium on Theory of computing (pp. 150–159). ACM.
Metadaten
Titel
Towards Fountain Codes
verfasst von
Seyed Masoud Mirrezaei
Karim Faez
Shahram Yousefi
Publikationsdatum
01.07.2014
Verlag
Springer US
Erschienen in
Wireless Personal Communications / Ausgabe 2/2014
Print ISSN: 0929-6212
Elektronische ISSN: 1572-834X
DOI
https://doi.org/10.1007/s11277-013-1597-7

Weitere Artikel der Ausgabe 2/2014

Wireless Personal Communications 2/2014 Zur Ausgabe

OriginalPaper

Fast Convergence Algorithm for Earthquake Prediction Using Electromagnetic Fields Excited by SLF/ELF Horizontal Magnetic Dipole and Schumann Resonance

OriginalPaper

Towards Enhanced Searching Architecture for Unstructured Peer-to-Peer Over Mobile Ad Hoc Networks

ReviewPaper

Efficient Hardware-Based Image Compression Schemes for Wireless Sensor Networks: A Survey

BriefCommunication

Analyzing the Mobile WiMAX System Resource Exploitation of the Downlink Direction

OriginalPaper

Novel Closed-Form Expressions for Ergodic Capacity of MIMO-OSFBC-OFDM Systems Over Channel Adaptation Policies

OriginalPaper

SW-MAC: A Low-Latency MAC Protocol with Adaptive Sleeping for Wireless Sensor Networks

Neuer Inhalt

    Bildnachweise