A discrete time Markov chain model for high throughput bidirectional Fano decoders

R Xu; G Woodward; KA Morris; T Koçak

doi:10.1109/GLOCOM.2010.5683855

A discrete time Markov chain model for high throughput bidirectional Fano decoders

R Xu
, G Woodward
, KA Morris
, T Koçak

Communication Systems and Networks

Research output: Chapter in Book/Report/Conference proceeding › Conference Contribution (Conference Proceeding)

3 Citations (Scopus)

783 Downloads (Pure)

Abstract

The bidirectional Fano algorithm (BFA) can achieve at least two times decoding throughput compared to the conventional unidirectional Fano algorithm (UFA). In this paper, bidirectional Fano decoding is examined from the queuing theory perspective. A Discrete Time Markov Chain (DTMC) is employed to model the BFA decoder with a finite input buffer. The relationship between the input data rate, the input buffer size and the clock speed of the BFA decoder is established. The DTMC based modelling can be used in designing a high throughput parallel BFA decoding system. It is shown that there is a trade-off between the number of BFA decoders and the input buffer size, and an optimal input buffer size can be chosen to minimize the hardware complexity for a target decoding throughput in designing a high throughput parallel BFA decoding system.

Translated title of the contribution	A discrete time Markov chain model for high throughput bidirectional fano decoders
Original language	English
Title of host publication	Globecom, Miami
Publisher	Institute of Electrical and Electronics Engineers (IEEE)
Pages	1 - 5
Number of pages	5
ISBN (Print)	9781424456369, 9781424456369, 9781424456376 (eISBN)
DOIs	https://doi.org/10.1109/GLOCOM.2010.5683855 https://doi.org/10.1109/GLOCOM.2010.5683855
Publication status	Published - Dec 2010
Event	Global Telecommunications Conference, 2010 (GLOBECOM 2010) - Miami, Florida, United States Duration: 1 Dec 2010 → …

Publication series

Name
ISSN (Print)	1930529X

Conference

Conference	Global Telecommunications Conference, 2010 (GLOBECOM 2010)
Country/Territory	United States
City	Miami, Florida
Period	1/12/10 → …

Bibliographical note

Rose publication type: Conference contribution

Additional information: With accompanying conference presentation

Sponsorship: The authors would like to thank the Telecommunications Research Laboratory (TRL) of Toshiba Research Europe Ltd. and its directors for supporting this work.

Terms of use: Copyright © 2010 IEEE. Reprinted from IEEE Global Telecommunications Conference 2010
(GLOBECOM 2010).

This material is posted here with permission of the IEEE. Such permission of the IEEE does not in any way imply IEEE endorsement of any of the University of Bristol's products or services. Internal or personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution must be obtained from the IEEE by writing to [email protected].

By choosing to view this document, you agree to all provisions of the copyright laws protecting it.

Keywords

Bidirectional Fano algorithm
high throughput decoding
queuing theory
sequential decoding

Access to Document

Conference paperAccepted author manuscript, 194 KB
Accompanying conference presentationAccepted author manuscript, 815 KB

http://hdl.handle.net/1983/1719

Handle.net

Persistent link

Cite this

@inproceedings{3b7a97e9a4b14534b695daeb3d8d48ce,

title = "A discrete time Markov chain model for high throughput bidirectional Fano decoders",

abstract = "The bidirectional Fano algorithm (BFA) can achieve at least two times decoding throughput compared to the conventional unidirectional Fano algorithm (UFA). In this paper, bidirectional Fano decoding is examined from the queuing theory perspective. A Discrete Time Markov Chain (DTMC) is employed to model the BFA decoder with a finite input buffer. The relationship between the input data rate, the input buffer size and the clock speed of the BFA decoder is established. The DTMC based modelling can be used in designing a high throughput parallel BFA decoding system. It is shown that there is a trade-off between the number of BFA decoders and the input buffer size, and an optimal input buffer size can be chosen to minimize the hardware complexity for a target decoding throughput in designing a high throughput parallel BFA decoding system.",

keywords = "Bidirectional Fano algorithm, high throughput decoding, queuing theory, sequential decoding",

author = "R Xu and G Woodward and KA Morris and T Ko{\c c}ak",

note = "Rose publication type: Conference contribution Additional information: With accompanying conference presentation Sponsorship: The authors would like to thank the Telecommunications Research Laboratory (TRL) of Toshiba Research Europe Ltd. and its directors for supporting this work. Terms of use: Copyright {\textcopyright} 2010 IEEE. Reprinted from IEEE Global Telecommunications Conference 2010 (GLOBECOM 2010). This material is posted here with permission of the IEEE. Such permission of the IEEE does not in any way imply IEEE endorsement of any of the University of Bristol's products or services. Internal or personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution must be obtained from the IEEE by writing to [email protected]. By choosing to view this document, you agree to all provisions of the copyright laws protecting it. ; Global Telecommunications Conference, 2010 (GLOBECOM 2010) ; Conference date: 01-12-2010",

year = "2010",

month = dec,

doi = "10.1109/GLOCOM.2010.5683855",

language = "English",

isbn = "9781424456369",

publisher = "Institute of Electrical and Electronics Engineers (IEEE)",

pages = "1 -- 5",

booktitle = "Globecom, Miami",

address = "United States",

}

Xu, R, Woodward, G, Morris, KA & Koçak, T 2010, A discrete time Markov chain model for high throughput bidirectional Fano decoders. in Globecom, Miami. Institute of Electrical and Electronics Engineers (IEEE), pp. 1 - 5, Global Telecommunications Conference, 2010 (GLOBECOM 2010), Miami, Florida, United States, 1/12/10. https://doi.org/10.1109/GLOCOM.2010.5683855, https://doi.org/10.1109/GLOCOM.2010.5683855

TY - GEN

T1 - A discrete time Markov chain model for high throughput bidirectional Fano decoders

AU - Xu, R

AU - Woodward, G

AU - Morris, KA

AU - Koçak, T

N1 - Rose publication type: Conference contribution Additional information: With accompanying conference presentation Sponsorship: The authors would like to thank the Telecommunications Research Laboratory (TRL) of Toshiba Research Europe Ltd. and its directors for supporting this work. Terms of use: Copyright © 2010 IEEE. Reprinted from IEEE Global Telecommunications Conference 2010 (GLOBECOM 2010). This material is posted here with permission of the IEEE. Such permission of the IEEE does not in any way imply IEEE endorsement of any of the University of Bristol's products or services. Internal or personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution must be obtained from the IEEE by writing to [email protected]. By choosing to view this document, you agree to all provisions of the copyright laws protecting it.

PY - 2010/12

Y1 - 2010/12

N2 - The bidirectional Fano algorithm (BFA) can achieve at least two times decoding throughput compared to the conventional unidirectional Fano algorithm (UFA). In this paper, bidirectional Fano decoding is examined from the queuing theory perspective. A Discrete Time Markov Chain (DTMC) is employed to model the BFA decoder with a finite input buffer. The relationship between the input data rate, the input buffer size and the clock speed of the BFA decoder is established. The DTMC based modelling can be used in designing a high throughput parallel BFA decoding system. It is shown that there is a trade-off between the number of BFA decoders and the input buffer size, and an optimal input buffer size can be chosen to minimize the hardware complexity for a target decoding throughput in designing a high throughput parallel BFA decoding system.

AB - The bidirectional Fano algorithm (BFA) can achieve at least two times decoding throughput compared to the conventional unidirectional Fano algorithm (UFA). In this paper, bidirectional Fano decoding is examined from the queuing theory perspective. A Discrete Time Markov Chain (DTMC) is employed to model the BFA decoder with a finite input buffer. The relationship between the input data rate, the input buffer size and the clock speed of the BFA decoder is established. The DTMC based modelling can be used in designing a high throughput parallel BFA decoding system. It is shown that there is a trade-off between the number of BFA decoders and the input buffer size, and an optimal input buffer size can be chosen to minimize the hardware complexity for a target decoding throughput in designing a high throughput parallel BFA decoding system.

KW - Bidirectional Fano algorithm

KW - high throughput decoding

KW - queuing theory

KW - sequential decoding

U2 - 10.1109/GLOCOM.2010.5683855

DO - 10.1109/GLOCOM.2010.5683855

M3 - Conference Contribution (Conference Proceeding)

SN - 9781424456369

SN - 9781424456369, 9781424456376 (eISBN)

SP - 1

EP - 5

BT - Globecom, Miami

PB - Institute of Electrical and Electronics Engineers (IEEE)

T2 - Global Telecommunications Conference, 2010 (GLOBECOM 2010)

Y2 - 1 December 2010

ER -

A discrete time Markov chain model for high throughput bidirectional Fano decoders

Abstract

Publication series

Conference

Bibliographical note

Keywords

Access to Document

Handle.net

Fingerprint

Cite this