- Fano Decoding with Timeout: Queuing Analysis
- Fano Decoding with Timeout: Queuing Analysis
- ㆍ 저자명
- Pan. W. David,Yoo. Seong-Moo
- ㆍ 간행물명
- ETRI journal
- ㆍ 권/호정보
- 2006년|28권 3호|pp.301-310 (10 pages)
- ㆍ 발행정보
- 한국전자통신연구원
- ㆍ 파일정보
- 정기간행물|ENG| PDF텍스트
- ㆍ 주제분야
- 기타
In mobile communications, a class of variable-complexity algorithms for convolutional decoding known as sequential decoding algorithms is of interest since they have a computational time that could vary with changing channel conditions. The Fano algorithm is one well-known version of a sequential decoding algorithm. Since the decoding time of a Fano decoder follows the Pareto distribution, which is a heavy-tailed distribution parameterized by the channel signal-to-noise ratio (SNR), buffers are required to absorb the variable decoding delays of Fano decoders. Furthermore, since the decoding time drawn by a certain Pareto distribution can become unbounded, a maximum limit is often employed by a practical decoder to limit the worst-case decoding time. In this paper, we investigate the relations between buffer occupancy, decoding time, and channel conditions in a system where the Fano decoder is not allowed to run with unbounded decoding time. A timeout limit is thus imposed so that the decoding will be terminated if the decoding time reaches the limit. We use discrete-time semi-Markov models to describe such a Fano decoding system with timeout limits. Our queuing analysis provides expressions characterizing the average buffer occupancy as a function of channel conditions and timeout limits. Both numerical and simulation results are provided to validate the analytical results.