Fano Decoding with Timeout: Queueing Analysis

ETRI Journal

关键词: semi-Markov model;    queuing analysis;    Pareto distribution;    Fano decoder;   

Others  :  1185406
DOI  :  10.4218/etrij.06.0105.0083

【 摘 要 】

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.

   

【 参考文献 】

• [1]S. Lin and D.J. Costello, Error Control Coding: Fundamentals and Applications, 2nd Edition, Pearson Education, 2004.
• [2]R.M. Fano, "A Heuristic Discussion of Probabilistic Decoding," IEEE Trans. Information Theory, vol. IT-9, Apr. 1963, pp. 64-74.
• [3]R.G. Gallager, Information Theory and Reliable Communication, Wiley, New York, 1968.
• [4]J.M. Wozencraft and I.M. Jacobs, Principles of Communication Engineering, Wiley, 1965.
• [5]R.O. Ozdag and P.A. Beerel, "A Channel Based Asynchronous Low Power High Performance Standard-Cell Based Sequential Decoder Implemented with QDI Templates," Proc. of 10th International Symposium on Asynchronous Circuits and Systems, Apr. 2004, pp.187-197
• [6]S. Singh, P. Thienniviboon, R.O. Ozdag, S. Tugsinavisute, R. Chokkalingam, P.A. Beerel, and K.M. Chugg, "Algorithm and Circuit Co-Design for a Low-Power Sequential Decoder," Proc. of Asilomar Conf. on Signal, Systems and Comp., Oct. 1999.
• [7]T. Hashimoto, "Bounds on a Probability for the Heavy Tailed Distribution and the Probability of Deficient Decoding in Sequential Decoding," IEEE Trans. on Information Theory, vol. 51, no. 3, Mar. 2005, pp. 990-1002.
• [8]I.M. Jacobs and E.R. Berlekamp, "A Lower Bound to the Distribution of Computation for Sequential Decoding," IEEE Transactions on Information Theory, vol. 13, no. 2, 1967, pp. 167-174.
• [9]F. Jelinek, "An Upper Bound on Moments of Sequential Decoding Effort," IEEE Transactions on Information Theory, vol. 15, no. 1, 1969, pp. 140-149.
• [10]R. Sundaresan and S. Verdu, "Sequential Decoding for the Exponential Server Timing Channel," IEEE Trans. on Communications, vol. 46, no. 2, Mar. 2000, pp. 705-709.
• [11]F. Pollara, "A Software Simulation Study of a Sequential Decoder using the Fano Algorithm," TDA Progress Report 42-81, JPL, NASA, Jan.-Mar. 1985.
• [12]O.R. Jensen and E. Paaske, "Forced Sequence Sequential Decoding: a Concatenated Coding System with Iterated Sequential Inner Decoding," IEEE Transactions on Communications, vol. 46, no. 10, 1998, pp. 1280-1291.
• [13]W. Pan and A. Ortega, "Buffer Control for Variable Complexity Fano Decoders," IEEE Global Telecommunications Conference, San Antonio, Texas, Nov. 2001, pp. 176-180.
• [14]S. Kallel and D. Haccoun, "Sequential Decoding with an Efficient Partial Retransmission ARQ Strategy," IEEE Trans. on Communications, vol. 39, no. 2, Feb. 1991, pp. 208-213.
• [15]N. Shacham, "ARQ with Sequential Decoding of Packetized Data: Queuing Analysis," IEEE Trans. on Communications, vol. 32, no. 10, Oct. 1984, pp. 1118-1127.
• [16]L. Kleinrock, Queuing Systems Volume 1: Theory, Wiley, 1975.
• [17]D. Gross and C.M. Harris, Fundamentals of Queuing Theory, Wiley, 1998.
• [18]C. Berrou, A. Glavieux, and P. Thitimajshima, "Near Shannon Limit Error Correcting Coding and Decoding: Turbo?Codes," Proc. IEEE International Conference on Communications, May 1993, pp. 1064? 1070.
• [19]Flarion Technologies Inc., "Vector - LDPC Codes for Mobile Broadband Communications," Nov. 2003. http://www.flarion. com/ products/ whitepapers/Vector-LDPC.pdf.