9.3 Equivalent Labelings for Trellis Encoders

Conventionally, CM designs based on CENCs either optimize the encoder for a constellation labeled by a SP labeling (TCM), or simply connect an encoder designed for binary transmission with the BRGC (BICM). Of course, none of these approaches is optimal. Instead, a joint optimization over the labeling universe (see Section 2.5.2) and the CENC universe (see Section 2.6.1) should be performed. This problem is very difficult, even for the simplest cases. As an example, we consider the design of a trellis encoder based on an CENC with and an -ary constellation. In this case, the labeling universe includes different binary labelings and the CENC universe (discarding catastrophic encoders) includes about encoders.⁵ An exhaustive search for this quite simple configuration would require checking about 6 billion combinations of encoders and labelings.

In this section we address the problem of the joint design of the CENC and the labeling for a trellis encoder, which, based on the analysis in the previous sections, can be used in combination with a BICM decoder. The analysis is based on a classification of binary labelings, which allows us to formally prove that in any trellis encoder the NBC can be replaced by many other labelings (including the BRGC) without causing any performance degradation, provided that the encoder is properly selected. This is also used to explain the asymptotic equivalence between BICM-T and TCM presented in Section 9.2.3.

9.3.1 Equivalent Trellis Encoders

We have seen in Fig. 9.4 that if the interleaver is removed in BICM, its performance over the AWGN channel is improved. Moreover, we showed that in terms of MED, a properly designed BICM-T performs asymptotically as well as TCM (see Tables 9.3 and 9.4). The transmitters for TCM andBICM-T for the -state (overall constraint length ) CENC are shown in Fig. 9.5 (a) and c, respectively. A careful examination of the results in Table 9.3 reveals that the optimal trellis encoder found when analyzing BICM-T, in fact, is equivalent to the one proposed by Ungerboeck 30 years ago. For a 4PAM constellation, Ungerboeck's SP labeling (NBC) can be generated using the BRGC plus one binary addition (which we call transform) applied to its inputs, as shown in Fig. 9.5 (b) (see also Example 2.12). If the transform is included in the mapper, the encoder in Fig. 9.5 (a) is obtained, while if it is included in the CENC, the trellis encoder in Fig. 9.5 (c) is obtained. This equivalence also applies to encoders with larger number of states⁶ and simply reveals that for 4PAM a TCM transceiver based on the BRGC will have identical performance to Ungerboeck's TCM if the encoder is properly modified, where the modification is the application of a simple transform.

To formally study this equivalence, we consider the trellis encoder in Fig. 2.4, where for simplicity we assume that . For a given constellation and overall constraint length , a CM encoder is fully defined by the CENC matrix and the labeling of the constellation , and thus, a trellis encoder is defined by the pair . In this section we show how a joint optimization over all (i.e., over the CENC universe) and (i.e., over the labeling universe) can be restricted, without loss of generality, to a joint optimization over all and over a subset of .

The output of a given trellis encoder at time depends only on information bits. Using (2.90), the transmitted symbol at time can then be expressed as

9.51

where , and , i.e., , where was used in (2.90). From now on, we use the notation to explicitly show the dependence of the mapper on the binary labeling .

The following definition gives a condition for the trellis encoders to be equivalent, where this equivalence implies equivalence in terms of BEP and WEP.

In the following, we use to denote the set of all binary invertible matrices and to denote the set of all reduced column echelon binary matrices (see Definition 2.14) of size .

Theorem 9.9 shows that a full search over and will include many pairs of equivalent trellis encoders. Therefore, an optimal trellis encoder with given parameters can be found by searching over a subset of and the whole set or vice versa. Here we choose the latter approach, searching over a subset of .

The following theorem will be used to develop an efficient search algorithm we introduce in the next section. For a proof of the following theorem, we refer the reader to the references we provide in Section 9.4.

Theorem 9.10 shows that all binary matrices can be uniquely generated by finding all the invertible matrices (the set ) and all the different reduced column echelon matrices (the set ). In particular, we have

9.55

9.56

In Table 9.5, the values for and for are shown. In this table we also show the number of binary labelings (), i.e., the number of matrices in the labeling universe.

	2	4	240
	1	6	168	20 160
	2	24	40 320

A modified Hadamard class is defined as the set of matrices that can be generated via (9.54) using the same reduced column echelon matrix . There are thus modified Hadamard classes, each with cardinality .

As a consequence of Theorems 9.9 and 9.10, the two trellis encoders and are equivalent for any and , where and are given by the factorization (9.54). In other words, all nonequivalent trellis encoders can be generated using one member of each modified Hadamard class only, and thus, a joint optimization over all and can be reduced to an optimization over all and with no loss in performance. This means that the search space is reduced by at least a factor of . For example, for -ary constellations (), the total number of different binary labelings that must be tested is reduced from to . Moreover, as shown in Section 9.3.4, this can be reduced even further if the constellation possesses certain symmetries.

9.3.4 and Constellations

While all the previous results are fully general in the sense that they are valid for any constellation, any memoryless channel, and any receiver, in this section we study well-structured one- and two-dimensional constellations, i.e., PAM and (PSK) constellations defined in Section 2.5.

PAM constellations are symmetric around zero. Because of this, two trellis encoders based on an PAM constellation, the first one using the labeling and the second one using a “reverse” labeling

9.62

are equivalent for any . This result implies that the number of binary labelings that give nonequivalent trellis encoders is . To generate only the nonequivalent labelings for PAM, the MFLSA in Algorithm 1 can be modified as follows. Replace on lines and with , where the integer function is defined as if and otherwise. This has the effect of only generating labelings, in which the all-zero label is among the first positions.

A trellis encoder based on an PSK constellation is not affected by a circular rotation of its labeling, i.e., without loss of generality it can be assumed that the all-zero label is assigned to the constellation point . The consequence of this is that for PSK constellations, the number of reduced column echelon matrices that give nonequivalent trellis encoders is reduced further by a factor of . For the labelings can be obtained from the MFLSA by setting in line , which gives the FLSA.

9.4 Bibliographical Notes

BICM-T was introduced in [1] and later analyzed in detail in [2] for a rate encoder and 4PAM, where the performance analysis developed in this chapter as well as the optimal encoders were also introduced. Very recently, it was shown in [3] that for BICM-T, the asymptotic loss in terms of PEP introduced by the suboptimal BICM receiver is bounded by . Furthermore, [3] also shows that this loss is in fact zero for a wide range of linear codes, including all rate CENCs we studied in this chapter.

TCM designs based on SP are considered heuristic [4, pp. 525, 531], [5, Section 3.4], and thus, they do not necessarily lead to an optimal design [6, p. 680]. Indeed, the results in [7, Tables 2–3], [8, Chapter 6; 9] show the suboptimality of using an SP labeling. For a good explanation about this, we refer the reader to [10, Section I]. The problem of using non-SP labelings for TCM has been studied in the literature. In [6, Section 13.2.1], a trellis encoder that uses a rate ODS CENC and a 4PSK constellation labeled by the BRGC was presented (see also [11, Example 18.2]). The same configuration was presented in [6, Problem 13–11], where the problem of selecting an appropriate labeling for a given encoder was analyzed. Another example is the so-called pragmatic TCM [12, Section 8.6, 13] (see also [14 15, Section 9.2.4]), where a non-SP labeling was used together with an off-the-shelf MFHD/ODS CENC. For 4PSK, this labeling corresponds to the BRGC, but for larger constellations it is not a Gray labeling (although it has a particular structure). A similar labeling was also used in [16]. A binary labeling for BICM-T was heuristically proposed in [1] for PAM constellations for .

The idea of using a Gray labeling and an MFHD CENC in fact dates back to [17 18], which correspond to the first pragmatic TCM approaches. Trellis encoders using a constellation labeled by the BRGC were designed in [7] where a search over CENCs maximizing the MED was performed. In [8, Chapter 6; 9], and in the same spirit of the ODS CENCs, Zhang used a non-Gray non-SP labeling and tabulated trellis encoders with optimal spectrum. Gray-coded TCM codes for fading channels were studied in [19–21].

The classification of labelings is inspired by the one in [22], where the so-called Hadamard classes were used to solve a related search problem in source coding and where the FLSA was also introduced. The modified Hadamard classes introduced in this chapter are narrower than the regular Hadamard classes defined in [22], each including reduced column echelon matrices. For a proof of Theorem 9.10, we refer the reader to [23, p. 187, Corollary 1].

The idea of applying a linear transformation to the labeling/encoder was first introduced in [8, Fig. 6.5], (see also [9 24, 25, Chapter 2]). The equivalence between TCM encoders and encoders optimized for the BRGC and the NBC as well as the relationship between the encoders in [2 26] were first pointed out to us by R. F. H. Fischer [27]. In the same way the encoders in [26, Table I], (which we reproduced in Table 9.4) and [2, Table III] are equivalent, it was shown in [25, Chapter 2], that the encoders found in [8, Chapter 6], using a non-Gray labeling are equivalent to those found with a Gray-labeled constellation in [7]. The formalism of using modified Hadamard classes to study the equivalence of trellis encoders was introduced in [28 29], where the MFLSA was also introduced and trellis encoders with optimum distance spectrum were tabulated.

In a related work, Wesel et al. introduced in [10] the concept of edge profile (EP) of a labeling, and argued that in most of the cases, the EP can be used to find equivalent trellis encoders in terms of MED. The EP is also argued to be a good indication of the quality of a labeling for TCM in [10, Section I]; however, its optimality is not proven. Nevertheless, all the labelings found in [28] have optimal EP. This makes us conjecture that good trellis encoders can be found by using the EP of [10] on top of the Hadamard-based classification. This approach would indeed reduce the search space; however, the optimality would not be guaranteed.

References

1. [1] Stierstorfer, C., Fischer, R. F. H., and Huber, J. B. (2010) Optimizing BICM with convolutional codes for transmission over the AWGN channel. International Zurich Seminar on Communications, March 2010, Zurich, Switzerland.
2. [2] Alvarado, A., Szczecinski, L., and Agrell, E. (2011) On BICM receivers for TCM transmission. IEEE Trans. Commun., 59 (10), 2692–2702.
3. [3] Ivanov, M., Alvarado, A., Brännström, F., and Agrell, E. (2014) On the asymptotic performance of bit-wise decoders for coded modulation. IEEE Trans. Inf. Theory, 60 (5), 2796–2804.
4. [4] Proakis, J. G. (2000) Digital Communications, 4th edn, McGraw-Hill.
5. [5] Schlegel, C. B. and Perez, L. C. (2004) Trellis and Turbo Coding, 1st edn, John Wiley & Sons.
6. [6] Barry, J. B., Lee, E. A., and Messerschmitt, D. G. (2004) Digital Communication, 3rd edn, Springer.
7. [7] Du, J. and Kasahara, M. (1989) Improvements of the information-bit error rate of trellis code modulation systems. Trans. IEICE, E 72 (5), 609–614.
8. [8] Zhang, W. (1996) Finite state systems in mobile communications. PhD dissertation, University of South Australia, Adelaide, Australia.
9. [9] Zhang, W., Schlegel, C., and Alexander, P. (1994) The bit error rate reduction for systematic 8PSK trellis codes by a Gray scrambler. IEEE International Conference on Universal Wireless Access, April 1994, Melbourne, Australia.
10. [10] Wesel, R. D., Liu, X., Cioffi, J. M., and Komninakis, C. (2001) Constellation labeling for linear encoders. IEEE Trans. Inf. Theory, 47 (6), 2417–2431.
11. [11] Lin, S. and Costello, D. J. Jr. (2004) Error Control Coding, 2nd edn, Prentice Hall, Englewood Cliffs, NJ.
12. [12] Clark, G. C. Jr. and Cain, J. B. (1981) Error-Correction Coding for Digital Communications, 2nd edn, Plenum Press.
13. [13] Viterbi, A. J., Wolf, J. K., Zehavi, E., and Padovani, R. (1989) A pragmatic approach to trellis-coded modulation. IEEE Commun. Mag., 27 (7), 11–19.
14. [14] Wolf, J. K. and Zehavi, E. (1995) codes: pragmatic trellis codes utilizing punctured convolutional codes. IEEE Commun. Mag., 33 (2), 94–99.
15. [15] Morelos-Zaragoza, R. H. (2002) The Art of Error Correcting Coding, 2nd edn, John Wiley & Sons.
16. [16] Hagenauer, J. and Sundberg, C.- E. (1988) On the performance evaluation of trellis-coded 8-PSK systems with carrier phase offset. Arch. Elektron. Uebertragungstechnik, 5 (42), 274–284.
17. [17] Odenwalder, J. P., Viterbi, A. J., Jacobs, I. M., and Heller, J. A. (1973) Study of information transfer optimization for communication satellites. Technical Report NASA-CR-114561, Linkabit Corporation, San Diego, CA.
18. [18] Digeon, A. (1977) On improving bit error probability of QPSK and 4-level amplitude modulation systems by convolutional coding. IEEE Trans. Commun., COM-25 (10), 1238–1239.
19. [19] Du, J. and Vucetic, B. (1990) New -PSK trellis codes for fading channels. Electron. Lett., 26 (16), 1267–1269.
20. [20] Du, J. and Vucetic, B. (1991) New 16-QAM trellis codes for fading channels. Electron. Lett., 27 (12), 1009–1010.
21. [21] Du, J. and Vucetic, B. (1995) Construction of new MPSK trellis codes for fading channels. IEEE Trans. Commun., 43 (2/3/4), 776–478.
22. [22] Knagenhjelm, P. and Agrell, E. (1996) The Hadamard transform—a tool for index assignment. IEEE Trans. Inf. Theory, 42 (4), 1139–1151.
23. [23] Birkhoff, G. and Mac Lane, S. (1977) A Survey of Modern Algebra, 4th edn, Macmillan, New York.
24. [24] Gray, P. K. and Rasmussen, L. K. (1995) Bit error rate reduction of TCM systems using linear scramblers. IEEE International Symposium on Information Theory (ISIT), September 1995, Whistler, BC, Canada.
25. [25] Gray, P. K. (1999) Serially concatenated trellis coded modulation. PhD dissertation, University of South Australia, Adelaide, Australia.
26. [26] Ungerboeck, G. (1982) Channel coding with multilevel/phase signals. IEEE Trans. Inf. Theory, 28 (1), 55–67.
27. [27] Fischer, R. F. H. Private communication, Jan. 2011.
28. [28] Alvarado, A., Graell i Amat, A., Brännström, F., and Agrell, E. (2012) On the equivalence of TCM encoders. IEEE International Symposium on Information Theory (ISIT), July 2012, Cambridge, MA.
29. [29] Alvarado, A., Graell i Amat, A., Brännström, F., and Agrell, E. (2013) On optimal TCM encoders. IEEE Trans. Commun., 61 (6), 2178–2189.