nach oben

Annals of Telecommunications

Erschienen in:

01.12.2012

Reduced complexity decoding of convolutional codes based on the M-algorithm and the minimal trellis

verfasst von: Richard Demo Souza, Cecilio Pimentel, Daiana Nascimento Muniz

Erschienen in: Annals of Telecommunications | Ausgabe 11-12/2012

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

In this paper, we propose three new sub-optimum, reduced complexity decoding algorithms for convolutional codes. The algorithms are based on the minimal trellis representation for the convolutional code and on the M-algorithm. Since the minimal trellis has a periodically time-varying state profile, each algorithm has a different strategy to select the number of surviving states in each trellis depth. We analyse both the computational complexity, in terms of arithmetic operations, and the bit error rate performance of the proposed algorithms over the additive white Gaussian noise channel. Results demonstrate that considerable complexity reductions can be obtained at the cost of a small loss in the performance, as compared to the Viterbi decoder.

Vorheriger Artikel An autonomic mobility management solution for the future wireless Internet

Nächster Artikel A pairing-free identity-based authenticated group key agreement protocol for imbalanced mobile networks

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

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

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 "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

When running the MA, it is possible that the number of states in section t that are reached by edges coming from section t − 1 be smaller than M. In this case, the MA stores all surviving states. In Section 5, we illustrate one of such cases.

As the minimum trellis and the conventional trellis represent the same code and the MMA algorithm only selects the surviving states at the end of the trellis module, the performances of the MMA algorithm operating over the minimum trellis and of the typical M-algorithm operating over the conventional trellis are identical.

Note that, based on the trellis module definition, \({\bar N}_{\rm s}^{0}={\bar N}_{\rm s}^{n}\).

Note that, alternatively, one could determine the \(\bar{N}_{\rm s}^{t+1}-M\) smallest elements within a vector of \(\bar{N}_{\rm s}^{t+1}\) elements. If that is simpler (less comparisons required), then one should select the survivors that way. In our numerical results, we always consider the case that requires less comparisons.

Similar results were obtained considering other codes of different rates and memory orders and are omitted here for the sake of brevity.

Lin S, Costello DJ (2004) Error control coding, 2nd edn. Prentice-Hall, Englewood Cliffs

IEEE Standard 802.16e-2005 (2006) IEEE standard for local and metropolitan area networks part 16: air interface for fixed and mobile broadband wireless access systems

3GPP TS 45.003 (2007) 3rd generation partnership project; technical specification group GSM/EDGE radio access network; channel coding (release 7)

ETSI TS 101 475 (2000) Broadband radio access networks (BRAN), HYPERLAN type 2, physical (PHY) layer

IEEE Standard 802.11 (1999) Wireless LAN medium access control (MAC) and physical (PHY) layer specifications: high speed physical layer in the 5 GHz band

Masselos K, Blionas S, Rautio T (2002) Reconfigurability requirements of wireless communication systems. In: Proc. IEEE workshop on heterogeneous reconfigurable systems on chip

Bougard B et al (2004) Energy-scalability enhancement of wireless local area network transceivers. In: Proc. IEEE workshop on signal processing advances in wireless communications

Dohler M, Heath R, Lozano A, Papadias C, Valenzuela R (2011) Is the PHY layer dead? IEEE Commun Mag 49(4):159–165CrossRef

Pentikousis K (2010) In search of energy-efficient mobile networking. IEEE Commun Mag 48(1):95–103CrossRef

10.

Demosthenous A, Taylor J (1999) Low-power CMOS and BiCMOS circuits for analog convolutional decoders. IEEE Trans Circuits Syst II 46(8):1077–1080CrossRef

11.

Tomatsopoulos B, Demosthenous A (2008) A CMOS hard-decision analog convolutional decoder employing the MFDA for low-power applications. IEEE Trans Circuits Syst I Regular Pap 55(9):2912–2923MathSciNetCrossRef

12.

Lin C-C, Shih Y-H, Chang H-C, Lee C-Y (2006) A low power turbo/Viterbi decoder for 3GPP2 applications. IEEE Trans Very Large Scale Integr (VLSI) Syst 14(4):426–430CrossRef

13.

Abdallah RA, Shanbhag NR (2008) Error-resilient low-power Viterbi decoders via state clustering. In: Proc. IEEE workshop on signal processing systems

14.

Zigangirov KS, Kolesnik VD (1980) List decoding of trellis codes. Probl Control Inf Theory 6:347–364MathSciNet

15.

Anderson JB (1989) Limited search trellis decoding of convolutional codes. IEEE Trans Inf Theory 35(5):944–955CrossRef

16.

Adachi F (1995) Reduced-state Viterbi differential detection using a recursively estimated phase reference for M-ary DPSK. IEE Proc Commun 142(4):263–270MathSciNetCrossRef

17.

Chan F, Haccoun D (1997) Adaptive Viterbi decoding of convolutional codes over memoryless channels. IEEE Trans Commun 45(11):1389–1400CrossRef

18.

Henning R, Chakrabarti C (2004) An approach for adaptively approximating the Viterbi algorithm to reduce power consumption while decoding convolutional codes. IEEE Trans Signal Process 52(5):1443–1451MathSciNetCrossRef

19.

Pottie GJ, Taylor DP (1989) A comparison of reduced complexity decoding algorithms for trellis codes. IEEE J Sel Areas Commun 7(9):1369–1380CrossRef

20.

McEliece RJ, Lin W (1996) The trellis complexity of convolutional codes. IEEE Trans Inf Theory 42(6):1855–1864MathSciNetMATHCrossRef

21.

Pimentel C, Souza RD, Uchôa-Filho BF, Pellenz ME (2008) Generalized punctured convolutional codes with unequal error protection. EURASIP J Adv Sig Proc 2008: 1–6. doi:10.1155/2008/28083

22.

Katsiotis A, Rizomiliotis P, Kalouptsidis N (2010) New constructions of high-performance low-complexity convolutional codes. IEEE Trans Commun 58(7):1950–1961CrossRef

23.

Rosnes E, Ytrehus Ø (2004) Maximum length convolutional codes under a trellis complexity constraint. J Complex 20:372–408MathSciNetMATHCrossRef

24.

Uchôa-Filho B, Souza RD, Pimentel C, Jar M (2009) Convolutional codes under minimal trellis complexity measure. IEEE Trans Commun 57:1–5CrossRef

25.

Hug F, Bocharova I, Johannesson R, Kudryashov BD (2009) Searching for high-rate convolutional codes via binary syndrome trellises. In: Proc IEEE int symp inform theory (ISIT 2009). Seoul, Korea, pp 1358–1362

26.

Jondral FK (2005) Software-defined radio: basics and evolution to cognitive radio. EURASIP J Wirel Comm Netw 2005(3):275–283MATH

27.

Mitola J (2000) Cognitive radio: an integrated architecture for software defined radio. Ph.D. dissertation, KTH, Stockholm, Sweden

28.

Vardy A (1998) Trellis structure of codes. In: Pless VS, Huffman WC (eds) Handbook of coding theory, vol II. North-Holland, Amsterdam

29.

Pedroni BU, Pedroni VA, Souza RD (2010) Hardware implementation of a Viterbi decoder using the minimal trellis. In: Proc of the 4th inter symp on commun control and signal processing (ISCCSP’2010). Limassol, Cyprus, pp 1–4

30.

McEliece RJ (1996) On the BCJR trellis for linear block codes. IEEE Trans Inf Theory 42(4):1070–1092MathSciNetCrossRef

31.

Chatzigeorgiou I, Demosthenous AA, Rodrigues MRD, Wassell IJ (2010) Performance-complexity tradeoff of convolutional codes for broadband fixed wireless access systems. IET Comm 4(4):419–427CrossRef

32.

Vucetic B, Yuan J (2000) Turbo codes: principles and applications. Kluwer Academic, BostonMATH

33.

Knuth D (1997) The art of computer programming, vol 3: sorting and searching, 3rd edn. Addison-Wesley, ReadingMATH

Titel: Reduced complexity decoding of convolutional codes based on the M-algorithm and the minimal trellis
verfasst von: Richard Demo Souza
Cecilio Pimentel
Daiana Nascimento Muniz
Publikationsdatum: 01.12.2012
Verlag: Springer-Verlag
Erschienen in: Annals of Telecommunications / Ausgabe 11-12/2012
Print ISSN: 0003-4347
Elektronische ISSN: 1958-9395
DOI: https://doi.org/10.1007/s12243-012-0295-x

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

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

Springer Professional "Wirtschaft"

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 11-12/2012

EBvN: efficient BvN in multi-fiber/multi-wavelength overlaid-star optical networks

A pairing-free identity-based authenticated group key agreement protocol for imbalanced mobile networks

Capacity analysis of distributed antenna systems in MIMO Nakagami fading multicell environment

An AHP-based resource management scheme for CRRM in heterogeneous wireless networks

Rain-induced attenuation for Ku-band satellite communications in the west coast of Peninsular Malaysia, Penang

Some experimental investigations in the WiMAX band and comparison of propagation models in mixed urban environments of Western India

Premium Partner