CODES AND ITERATIVE DECODING ON GENERAL GRAPHS

被引:164
作者
WIBERG, N
LOELIGER, HA
KOTTER, R
机构
[1] Department of Electrical Engineering, Linkoping University, Linkoping
来源
EUROPEAN TRANSACTIONS ON TELECOMMUNICATIONS | 1995年 / 6卷 / 05期
关键词
D O I
10.1002/ett.4460060507
中图分类号
TN [电子技术、通信技术];
学科分类号
0809 ;
摘要
A general framework, based on ideas of Tanner, for the description of codes and iterative decoding (''turbo coding'') is developed. Just like trellis-based code descriptions are naturally matched to Viterbi decoding, code descriptions based on Tanner graphs (which may be viewed as generalized trellises) are naturally matched to iterative decoding. Two basic iterative decoding algorithms (which are versions of the algorithms of Berrou et al. and of Hagenauer, respectively) are shown to be natural generalizations of the forward-backward algorithm (Bahl et al.) and the Viterbi algorithm, respectively, to arbitrary Tanner graphs. The careful derivation of these algorithms clarifies, in particular, which a priori probabilities are admissible and how they are properly dealt with. For cycle codes (a class of binary linear block codes), a complete characterization is given of the error patterns that are corrected by the generalized Viterbi algorithm after infinitely many iterations.
引用
收藏
页码:513 / 525
页数:13
相关论文
共 21 条
[1]  
Berrou C., Glavieux A., Thitimajshima P., pp. 1064-1070, (1993)
[2]  
Gallager R.G., Low‐density parity‐check codes, IEEE Transactions on Information Theory, 8, pp. 21-28, (1962)
[3]  
Zyablov V.V., Pinsker M.S., Estimation of the error‐correction complexity of Gallager low‐density codes, Probl. Peredach. Inform., 11, pp. 23-36, (1975)
[4]  
Tanner R.M., A recursive approach to low complexity codes, IEEE Transactions on Information Theory, 27 IT, pp. 533-547, (1981)
[5]  
Forney G.D., The Viterbi algorithm, Proc. IEEE, 61, pp. 268-278, (1973)
[6]  
Bahl L.R., Cocke J., Jelinek F., Raviv J., Optimal decoding of linear codes for minimizing symbol error rate, IEEE Transactions on Information Theory, 20 IT, pp. 284-287, (1974)
[7]  
Hagenauer J., Papke L., (1994)
[8]  
Peterson W.W., Weldon E.J., Error‐correcting codes, (1972)
[9]  
Willems J.C., Models for dynamics, Dynamics Reported, 2, pp. 171-269, (1989)
[10]  
Loeliger H.-A., Forney G.D., Mittelholier T., Trott M.D., Minimality and observability of group svstems, Linear Algebra & Appl., 205-206, pp. 937-963, (1994)