Treillis à complexité réduite pour le décodage de codes à longueur variable
Reduced-complexity trellises for the joint source-channel decoding of variable-length encoded data
OPEN ACCESS
Many trellis-based soft decoding techniques have been proposed for data encoded using variable-length codes (VLC). However, for actual VLC tables, these trellises are too complex to allow real-time soft decoding. This paper presents the principle of an algorithm for grouping VLC codewords into classes, which allows significant reductions of the complexity of the resulting trellises and of the soft decoding techniques. The adapation of decoding algorithms such as SOVA or BCJR to the reduced-complexity trellises is detailed. Illustrations are provided on the VLC table used for texture encoding in H.263+. The performance of a decoding technique for the localization of block frontiers in a bitstream generated by an H.263+ coder is also presented.
Résumé
De nombreux algorithmes ont été proposés pour le décodage souple de données codées à l’aide de codes à longueur variable (CLV), la plupart travaillant avec des treillis. Pour un code réaliste, ces treillis sont très complexes à cause du nombre de mots de code à considérer. Cet article présente le principe d’un algorithme de regroupement de mots de CLV en un nombre minimal de classes, ce qui permet de réduire significativement la complexité des treillis utilisés pour le décodage souple de CLV. L’adaptation des algorithmes de décodage tels que SOVA ou BCJR à ce type de treillis est détaillée. Une illustration sur les CLV de la norme H.263+ est proposée ainsi qu’un exemple d’application à la localisation des frontières de blocs de texture H.263+.
Decoding, joint source-channel decoding, MAP estimation, maximum likelihood decoding, maximum likelihood estimation, variable length codes
Mots clés
Codes à longueur variable, décodage source-canal conjoint, estimation au sens du MAP, estimation au sens du maximum de vraisemblance
[Bal97] V. B. BALAKIRSKY. Joint source-channel coding with variable length codes. In Proceedings of lEEE ISIT, Ulm, Germany, 1997.
[BCJR74] L. R. BAHL, J. COCKE, F. JELINEK, and J. RAVIV. Optimal decoding of linear codes for minimizing symbol error rate. IEEE Trans. Info. Theory, 20 :284–287, 1974.
[BF95] V. BUTTIGIEG and P.G. FARRELL. A MAP decoding algorithm for variable-length error-correcting codes. In Codes and Cyphers : Cryptography and Coding IV, pages 103–119, Essex, England, 1995. The Inst. of Mathematics and its Appl.
[BH00] R. BAUER and J. HAGENAUER. Turbo-FEC/VLC-decoding and its application to text compression. In Proceedings of the Conference on Information Sciences and Systems (CISS’00), Princeton University, USA, 2000.
[DS98] N. DEMIR and K. SAYOOD. Joint source/channel coding for variable length codes. In IEEE Data Compression Conf., pages 139–148, Snowbird, UT, 1998.
[HH89] J. HAGENAUER and P. HOEHER. A Viterbi algorithm with softdecision outputs and its applications. In Proc. Globecom, pages 1680–1686, Dallas, TX, 1989.
[JCS05] M. JEANNE, J.-C. CARLACH and P. SIOHAN. Joint source channel decoding of variable length codes for convolutional codes and turbo codes. IEEE Trans. on Communications, 53(1) :10–15, 2005.
[JMG05] H. JÉGOU, S. MALINOWSKI and C. GUILLEMOT. Trellis stage aggregation for soft decoding of variable-length codes. In Proceedings of SPIS, 2005.
[KB00] S. KAISER and M. BYSTROM. Soft decoding of variable-length codes. In Proceedings of the IEEE International Conference on Communications, volume 3, pages 1203–1207, New Orleans, 2000.
[LKD05] C.M. LEE, M. KIEFFER and P. DUHAMEL. Soft decoding of VLC encoded data for robust transmission of packetized video. In Proceedings of ICASSP, pages 737–740, 2005.
[MKKD06] G. R. MOHAMMAD-KHANI, M. KIEFFER and P. DUHAMEL. Simplification of VLC tables with application to ML and MAP decoding algorithms. IEEE Transactions on Communications, 54(10): 1835-1844, 2006.
[MSJ06] V. MANNONI, P. SIOHAN and M. JEANNE. A simple on-line turbo estimation of source statistics for joint sourcechannel VLC decoders : Application to MPEG-4 video. In Proc., 4th International Symposium on Turbo Codes & Related Topics, 2006.
[ND03] H. NGUYEN and P. DUHAMEL. Compressed image and video redundancy for joint source-channel decoding. In Proc. Globecom, 2003.
[SOD00] K. SAYOOD, H. H. OTU and N. DEMIR. Joint source/channel coding for variable length codes. IEEE Trans. Commun., 48:787–794, 2000.
[TK03] R. THOBABEN and J. KLIEWER. On iterative source-channel decoding for variable-length encoded markov sources using a bitlevel trellis. In Proc. IV IEEE Signal Processing Workshop on Signal Processing Advances in Wireless Communications (SPAWC’03), Rome, 2003.
[VY00] B. VUCETIC and J. YUAN. Turbo Codes – Principles and Applications. Kluwer, Dordrecht, 2000.