AP07_4-5.vp 1 Introduction Since the discovery of Turbo codes [1], which allow for channel coding close to the Shannon limit with moderate complexity, the Turbo principle of exchanging extrinsic infor- mation has been extended to various components of the receiver chain. Iterative source-channel decoding (ISCD) [2, 3] is such an extension. Instead of a concatenation of two or more channel decoders, a channel decoder and a soft decision source decoder (SDSD) [4, 5] are iteratively com- bined exchanging extrinsic information. Unlike Turbo channel decoding, which aims at minimizing the bit error rate, ISCD mainly aims at error concealment and signal resto- ration which is not necessarily connected to a lower bit error rate, but to a higher parameter SNR. ISCD exploits the a pri- ori knowledge on the residual redundancy of the source codec parameters that remains after imperfect source coding. The a priori knowledge can be a nonuniform probability distribution, an autocorrelation or a cross correlation. The source codec parameters can be, e.g., scale factors or predic- tor coefficients for speech, audio and video signals. Delay or complexity constraints prevent a complete removal of the residual redundancy and therefore, in practice, a quite large amount of residual redundancy remains in the source codec parameters, which can be exploited by ISCD. One major design issue in ISCD systems is the index as- signment. Besides the traditional index assignments for non- iterative systems, such as natural binary or Gray, optimized index assignments have been developed that take into ac- count the possible feedback due to the Turbo loop between channel decoder and SDSD. In [6, 7] index assignments have been introduced that are optimized considering a nonuni- form probability distribution, i.e., the zeroth order a priori information, of source samples. Further enhanced index assignments have been presented in [8] and the correspond- ing optimization process even takes the first order a priori information, e.g., the autocorrelation, of the source samples into account. This paper focuses on the latter type of index assignments. In general, an index assignment is chosen in advance and is not exchanged during a transmission, otherwise side infor- mation has to be transmitted to notify the receiver of the change. However, in this paper the index assignment is as- sumed to be constant during a transmission. If it is a priori known that the source codec parameters bear a specific over- all autocorrelation, an appropriate index assignment can be applied exploiting this autocorrelation. But since most signals have a time-varying autocorrelation it has to be examined how much the performance degrades, if the signal correlation does not match the correlation that the index assignment is optimized for. At first, the underlying ISCD transmission scheme is de- scribed in Section 2. Since in this paper the performance of index assignments that consider first order a priori knowl- edge will be under examination, more details on this topic will be given in Section 3. In Section 4 the performance (degrada- tion) of the ISCD system is shown by means of simulation results utilizing the index assignments under both optimal and suboptimal conditions. In Section 5 the simulated sce- narios are then analyzed and confirmed by so-called EXIT (extrinsic information transfer) charts [9]. 2 Iterative source-channel decoding The baseband model of the utilized ISCD transmission scheme is depicted in Fig. 1. Source codec parameters u are generated by a Gauss-Markov source, with an inherent auto- correlation � in order to obtain comparable and reproducible results. At time instant �, K source codec parameters uk,� are assigned to one frame u � with k K� �0 1 1, , ,� denoting the position in the frame. In this paper the autocorrelation � is constant in order to simulate a fixed mismatch between the correlation �T of the transmitted source parameters and the assumed correlation �R at the receiver. The autocorrelation takes on values from a finite set, e.g., � �� � 0 0 01 0 9. , . , , .� . The value-continuous and time-discrete source samples uk,� are each quantized to a quantizer reproduction level u Uk,� � , where U is the quantizer codebook. To each uk,� a unique bit 80 © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ Acta Polytechnica Vol. 47 No. 4–5/2007 Analysis of Mismatched First Order A Priori Information in Iterative Source-Channel Decoding B. Schotsch, P. Vary, T. Clevorn Due to complexity and delay constraints a usually significant amount of residual redundancy remains in the source samples after source coding. This residual redundancy can be exploited by iterative source-channel decoding for error concealment and quality improvements. One key design issue in joint source-channel (de-)coding is the index assignment. Besides conventional index assignments optimized index assignments have been developed, e.g., considering zeroth or first order a priori information of the source samples. However, in real-world scenarios it is unlikely that the amount of residual redundancy is constant over time and thus it may occur that the just deployed index assignment is suboptimal at times when the residual redundancy differs too much from the amount that it is optimized for. In this paper the performance of optimized index assignments is examined that consider first order a priori knowledge under such suboptimal conditions. Keywords: iterative source-channel decoding, optimized index assignments, first order a priori knowledge, EXIT charts pattern xk,� of M bits is assigned according to the utilized index assignment. The single bits of a bit pattern xk,� are indi- cated by xk m , ( ) � with m M� �0 1 1, , ,� , and the frame of bit patterns is denoted as x � . Three parameter SNR optimized index assignments considering first order a priori knowledge (SOAK1) are used and the natural binary (NB) index assign- ment serves as a reference. The SOAK1 index assignments are optimized for different source correlations, thus they are referred to as SOAK(�). The bit interleaver � scrambles the incoming bits x of the frame x � of bit patterns to ~x in a deterministic manner. To simplify the notation, we restrict the interleaving to a single time frame with index � and omit the time frame index � in the following, where appropriate. For the channel encoding of a frame x of interleaved bits x we utilize LDPC codes, which were first proposed by Gallager [10] and rediscovered by MacKay [11]. LDPC codes have a very high error correction capability with iterative decoding that is very close to the Shannon limit. Their performance is comparable or even superior to that of convolutional Turbo codes. In this paper we use a modification of short LDPC codes as presented in [12]. Identical instances of a short LDPC code are combined to a long LDPC code, whose frame size is flexible in multiples of a subframe size, i.e., the frame size of the short LDPC code. By serially concatenating the subframes with a bit-interleaver and a second component that provides extrinsic information according to the Turbo princi- ple (e.g., a soft decision source decoder (SDSD) as in this paper), extrinsic information can also be exchanged between subframes. Such concatenated LDPC codes approach very well the performance of long monolithic LDPC codes of the same frame size [12]. The performance of the concatenated LDPC code strongly depends on the performance of the short code. Therefore, the short code has to be chosen carefully. As short LDPC code a (21,11) difference set cyclic (DSC) code [13] is used. DSC codes feature a high minimum Hamming distance, and especially at short block lengths they can out- perform comparable pseudo-random LDPC codes [14]. The resulting codeword is denoted as y with bits y, which are mapped to bipolar bits � ���y � � 1 for BPSK transmission with symbol energy E s � 1 . We choose the simple BPSK mod- ulation scheme, since modulation is no design issue in this paper. On the channel, the signal ��y is superposed with additive white Gaussian noise (AWGN) n with the known power spec- tral density s Nn 2 0 2� , i.e., z y n� ��� . The received symbols z are evaluated in a Turbo process, in which extrinsic re- liabilities between the LDPC decoder and the SDSD are exchanged. Utilizing LDPC codes results in an additional iterative loop in the LDPC decoder, in which extrinsic in- formation is exchanged between the variable nodes and the check nodes. These iterations are denoted as LDPC- -iterations. Details about the ISCD receiver can be found in [2, 3, 15]. The LDPC decoder uses the belief propagation algorithm [16, 11] to generate extrinsic information. The SDSD deter- mines the extrinsic information mainly from the natural re- sidual source redundancy, which generally remains in the bit patterns xk after source encoding. Such residual redundancy appears on the parameter level, e.g., as a nonuniform distri- bution P u k( ) , in terms of a correlation, or as other possible time-dependencies. The latter terms of residual redundan- cy are generally approximated by a first order Markov chain, i.e., by exploiting the conditional probabilities P k k( )x x �1 . These conditional probabilities heavily depend on the source correlation. For specific source correlations, e.g., �� � 0 0 01. , . , ��, .0 9 , they can be calculated once in advance. The technique for combining this a priori information P k k( )x x �1 on the parameter level with the soft input values P xLDPC [ext] ( ) on the bit level is also well known in the literature. The algorithm for the computation of the extrinsic P xLDPC [ext] ( ) has been detailed, e.g., © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ 81 Acta Polytechnica Vol. 47 No. 4–5/2007 Fig. 1: Baseband model of ISCD with LDPC codes in [2, 3, 15]. As a quality measure we consider the parameter signal-to-noise ratio (SNR) � � � � P E u E u u � � 10 10 2 2 log � . (1) 3 Index assignments The index assignment is a major design factor influenc- ing the performance of ISCD transmission systems. Several conventional index assignments already exist, such as natural binary (NB) or Gray [17]. They are well-suited for non- iterative systems [15, 7, 6], but they exhibit only a suboptimal performance in ISCD. In this paper we consider only bit patterns consisting of M � 3 bit that are assigned to Q M� �2 8 quantizer levels. The utilized index assignments are listed in Table 1, but first, the optimization algorithm will be briefly explained. This was introduced in [8] and can be found in more detail there. According to the notation in [15], the index assignment �: u � x is given in the corresponding decimal representa- tion � �x 10 for an increasing quantizer level u. The quantizer levels are consecutively numbered, i.e., u u u( ) ( ) ( ), , ,0 1 7� for Q � 8. Thus, the decimal notation of the index assignment, e.g., SOAK1 for � � 0 9. is (cf. Table 1) � � � �� � � � � �� � � � � � u u u ( ) ( ) ( ) � � � 0 10 2 1 10 2 7 10 0 000 6 110 7 � � � � x x x x x x � � � � � � � �� �2 111� . Parameter SNR optimized index assignments that take into account first order a priori knowledge are generated by minimizing the overall noise energy function [8] D MQ P u u u u u u Um M u [ ] ( , , ) minSOAK1 1 2 1 1 1 � � �� � � � � � � � � � �� U , (2) with P u u u P u u P u u P u( , , ) ( | ) ( | ) ( ) � � � � � � � � � �� � � ��1 1 1 1 . The term u u� �� � 2 corresponds to the noise energy that originates from estimating the quantizer level � u� instead of the correct quantizer level u� at time instant �. � u� corresponds to the bit pattern that differs from the bit pattern of u� only at position m. Both u� and � u� are assumed to have the same predecessor u��1. Also only single bit errors are taken into account, since the system is generally supposed to operate in good channels, in which the probability of two or more bit errors occurring in one bit pattern is negligible. In order to determine the overall noise energy, each term u u� �� � 2 has to be weighted by the probability of its occurrence P u u u( , , ) � � � ��1 and has to be summed up. Finally, the noise energy function has to be mini- mized either by an exhaustive search for small values of M ( )M � 4 , which yields a global optimum, or by the binary switching algorithm [18, 6, 15], which may lead to a local opti- mum only. 4 Simulation Results In Fig. 2 the parameter SNR performance of ISCD utiliz- ing the optimized index assignments is compared to the one using the conventional natural binary index assignment. The parameter SNR performance is shown for various combina- tions of the source parameter correlation at the transmitter �T and the assumed correlation at the receiver �R. For exploiting the residual redundancy at the receiver it is necessary that the source parameter correlation is known at the receiver. To that end, the source correlation either has to be transmitted as side information or it has to be estimated at the receiver. The latter approach has turned out to be very precise and easy to imple- ment. However, in this paper, the mismatch between �T and �R is preset. 82 © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ Acta Polytechnica Vol. 47 No. 4–5/2007 Index Assignment � � �x 10 � �( )u natural binary (NB) 0, 1, 2, 3, 4, 5, 6, 7 parameter SNR optimized (SOAK1) � � 0 0. 0, 1, 3, 2, 7, 6, 4, 5 � � 0 7. 0, 1, 3, 2, 6, 4, 5, 7 � � 0 9. 0, 6, 5, 1, 3, 2, 4, 7 Table 1: Index assignments �: u � x from Q � 8 quantizer levels u Q� �0 1, ,� , to bit patterns x with M � 3 bit Frame size 330, 8-level LMQ, (L S) iterationsK � 3 6 SOAK1( 0.0)� � NB (reference) SOAK1( 0.9)� � SOAK1( 0.7)� � Fig. 2: Parameter SNR performance of source correlation opti- mized index assignments SOAK13 8 ( )� in combination with an autocorrelation mismatch A reference parameter SNR of P[ ]ref � 13 dB is assumed at which the parameter SNR performances will be compared. The parameters emitted by the Gauss-Markov source ( )�2 1� exhibiting a source correlation of �T, are grouped to frames of size K � 330 and are quantized by an 8-level Lloyd-Max quantizer (LMQ) resulting in 990 uncoded bits per frame. After channel encoding this yields 1890 coded bits per frame. On the receiver side, ( )L S3 6 iterations are performed, which means that during each of the six iterations between LDPC- -decoder and SDSD three LDPC-iterations between the vari- able nodes and the check nodes of the LDPC-decoder are carried out. The set of curves in Fig. 2 that is labeled by ( , ) ( , . )� � �T R T� � 0 0 shows the scenario in which no correlation is exploited at the receiver, independently of the actual source correlation. This is also the current state of today’s transmission systems, where the available correlation is not utilized at the receiver in order to enhance the signal quality. In this case the three curves for NB, SOAK1(� � 0 0. ) and SOAK1(� � 0 7. ) show about the same performance, while for SOAK1(� � 0 9. ) a degradation of � E Nb 0 0 6� . dB can be observed. The leftmost set of curves shows the case in which � �R T� � 0 9. are matching. Such high values for �T are not unusual for several source codec parameters in current com- munication systems like GSM or UMTS. The parameter SNR optimized index assignment SOAK1(� � 0 9. ) yields the high- est gain of � E Nb 0 0 6� . dB compared to the reference index assignment NB . The gain of SOAK1(� � 0 7. ) is already negli- gibly small and the performances of SOAK1(� � 0 0. ) and NB are almost the same. However, this shows that if the source parameters exhibit a certain amount of correlation it is defi- nitely expedient to exploit it. The rightmost set of curves labeled by ( , ) ( . , . )� �T R � 0 0 0 9 displays the performance of the scenario in which the source parameters are uncorrelated, but the receiver assumes a high correlation (�R � 0 9. ). When �R��T a high performance degradation occurs for all index assignments, but for NB the least and for SOAK1(� � 0 9. ) the highest degradation can be observed. However, this scenario is very unlikely, since the correlation can be estimated very accurately at the receiver, so that this high mismatch is temporally limited to the instances of abrupt changes of the source parameter correlation. In systems with a high and slowly varying source correla- tion a reliable estimation of the source correlation is possible, and thereby it is reasonable and feasible to exploit the perfor- mance gain of an index assignment optimized for high source correlations. In systems with fast and high source correlation fluctuations a more conservative choice of the index assign- ment is recommended. 5 EXIT chart analysis In this section the system is analyzed by EXIT (extrinsic information transfer) charts [9], which are a powerful tool for analyzing and optimizing the convergence behavior of iterative systems utilizing the Turbo principle, i.e., systems exchanging and refining extrinsic information. The capabili- ties of the components, in our case the LDPC decoder and the soft decision source decoder (SDSD), are analyzed separately. The extrinsic mutual information I[ext] obtained by each component is determined for a certain a priori mutual infor- mation I[apri]. Both, I[ext] and I[apri], are calculated on the basis of the actual data and the available extrinsic or a priori information of the data. As a basis for this calculation usually histograms of the respective L-values, e.g., LLDPC ext[ ] for LLDPC ext[ ] , are used. L-values are the log-likelihood ratios of the corre- sponding probabilities P [19]. For the EXIT characteristics, the a priori L-values are simulated as uncorrelated Gaussian distributed random variables with variance � A 2 and mean � �� A 2 2 . In most cases, e.g., for a classical Turbo Code [1], this is a good assumption [9]. The applicability of EXIT charts to ISCD is demonstrated, e.g., in [15]. Since the extrinsic information of one component serves as input a priori information for the other component, the two resulting EXIT characteristics are plotted in a single graph with swapped axes. The EXIT characteristic of the LDPC decoder depends on the E Nb 0 of the channel, while the EXIT characteristic of the SDSD is independent of the E Nb 0 since the SDSD has no access to the received channel symbols z. The decoding trajectory (step curve) shows the mu- tual information I for each iteration in a simulation of the complete system. In the optimization process of the system design the components are chosen such that the (first) inter- section of their EXIT characteristics moves towards the point ( , ) ( , )[ ] [ ]L LLDPC ext SDSD ext � 1 1 . In the design of the system, i.e., the design of the characteristics, we have always � �T R� , while in the actual simulation settings � �T R� is not necessarily ful- filled. Thus, when the system design matches the actual set- tings, the decoding trajectory approaches this intersection, indicating that the best possible performance is obtained. The number of steps of the decoding trajectory corresponds to the number of useful iterations. Fig. 3(a) depicts the EXIT charts corresponding to the results with the SOAK1(� � 0 9. ) index assignment in Fig. 2 at © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ 83 Acta Polytechnica Vol. 47 No. 4–5/2007 E Nb 0 2� dB. We can observe that when the system design with the index assignment SOAK1(� � 0 9. ) matches the simu- lated settings with ( , ) ( . , . )� �T R � 0 9 0 9 , the decoding trajectory reaches the intersection of the LDPC EXIT characteristic and the SOAK1(� � 0 9. ) EXIT characteristic, confirming the excellent performance of this case in Fig. 2. In the other cases the decoding trajectory ends very early at low amounts of mu- tual information, especially at low values of ISDSD ext[ ] . Here, only values in the range of the SOAK1(� � 0 0. ) EXIT characteristic are obtained. With ( , ) ( . , . )� �T R � 0 0 0 9 even a significant decrease in mutual information occurs with an increasing number of iterations. This yields the poor results of this case in Fig. 2. Fig. 3(b) depicts the EXIT charts of the results with the SOAK1( � � 0 0. ) index assignment in Fig. 2, again at E Nb 0 2� dB. As expected, with the simulation settings matching the system design, i.e., ( , ) ( . , . )� �T R � 0 0 0 0 in this case, we reach the intersection of the SOAK1(� � 0 0. ) EXIT characteristic with the LDPC EXIT characteristic. However, this intersection occurs at much lower values of mutual in- formation than the intersection with the SOAK1( � � 0 9. ) EXIT characteristic, which is relevant in Fig. 3(a). This rela- tion can also be observed in the corresponding parameter SNR performance in Fig. 2. The two cases with a mis- match differ noticeably in the SOAK1( � � 0 0. ) EXIT chart. For ( , ) ( . , . )� �T R � 0 0 0 9 , which corresponds to a significant overestimation at the receiver, we get a decreasing decoding trajectory, quite similar to the respective case in Fig. 2. But when ( , ) ( . , . )� �T R � 0 9 0 9 , the ISCD receiver correctly uses the high residual redundancy due to the high autocorrelation and significantly outperforms the ( , ) ( . , . )� �T R � 0 0 0 0 case. Only the wrong index assignment SOAK1(� � 0 0. ) instead of SOAK1(� � 0 9. ) lets the ( , ) ( . , . )� �T R � 0 9 0 9 decoding trajec- tory fall short of the SOAK1(� � 0 9. ) EXIT characteristic. Taking Fig. 3(a) and Fig. 3(b) into account, we can observe that by means of EXIT charts we can accurately analyze, ex- plain and confirm the parameter SNR results. 6 Conclusion In this paper the performance of iterative source-channel decoding utilizing optimized index assignments has been analyzed. The studied index assignments are optimized with respect to the parameter SNR and by considering first order a priori knowledge. The simulation results show that high gains are achievable if the source parameter correlation is high and if the correlation at the receiver matches. These findings have been confirmed by an EXIT chart analysis. With opti- mized index assignments additional gains can be achieved compared to conventional index assignments. In case the assumed correlation at the receiver is higher than the source parameter correlation, high deteriorations can occur de- pending on how mismatched the correlations are. Thus, depending on the dynamics and the amount of correlation of the source codec parameters, either the optimized or the con- ventional index assignments are better suited. The index assignments optimized for high correlations perform better in systems with a high and slowly varying source correlation, while the conventional index assignments have an advantage in systems with fast and high source correlation fluctuations. 7 References [1] Berrou, C., Glavieux, A., Thitimajshima, P.: Near Shan- non Limit Error-Correcting Coding and Decoding, in IEEE International Conference on Communications (ICC), Geneva, Switzerland, May 1993. [2] Adrat, M., Vary, P., Spittka, J.: Iterative Source-Channel Decoder Using Extrinsic Information from Softbit-Source Decoding, in IEEE International Confer- ence on Acoustics, Speech, and Signal Processing (ICASSP), Salt Lake City, UT, USA, May 2001. [3] Görtz, N.: On the Iterative Approximation of Optimal Joint Source-Channel Decoding, IEEE Journal on Selected Areas in Communications, Sept. 2001, p. 1662–1670.Q 5 84 © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ Acta Polytechnica Vol. 47 No. 4–5/2007 a) EXIT trajektories for SOAK1 ( 0.9)�� b) EXIT trajektories for SOAK1 ( 0.0)�� Fig. 3: EXIT charts for SOAK1( � � 0 0. ) and SOAK1( � � 0 9. ) [4] Fingscheidt, T., VARY P.: Softbit Speech Decoding: A New Approach to Error Concealment, IEEE Transactions on Speech Audio Processing, Mar. 2001, p. 240–251. [5] Vary, P., Martin R.: Digital Speech Transmission: Enhance- ment, Coding and Error Concealment, John Wiley & Sons Ltd, 2006. [6] Görtz, N.: Optimization of Bit Mappings for Iterative Source-Channel Decoding, in 3rd International Symposium on Turbo Codes & Related Topics, Brest, France, Sept. 2003. [7] Hagenauer, J., Görtz, N.: The Turbo Principle in Joint Source-Channel Coding, in IEEE Information Theory Workshop (ITW), Paris, France, Apr. 2003. [8] Clevorn, T., Vary, P., Adrat, M.: Parameter SNR Opti- mized Index Assignments and Quantizers based on First Order A Priori Knowledge for Iterative Source-Channel Decoding, in Conference on Information Sciences and Sys- tems (CISS), Princeton, NJ, USA, Mar. 2006. [9] Ten Brink, S.: Convergence Behavior of Iteratively De- coded Parallel Concatenated Codes, IEEE Transactions on Communications, Oct. 2001, p. 1727–1737. [10] Gallager, R. G.: Low-Density Parity-Check Codes, IRE Transactions on Information Theory, Jan. 1962, p. 21–28. [11] Mackay, D. J. C., Neal, R. M.: Near Shannon Limit Per- formance of Low Density Parity Check Codes, IEE Elec- tronics Letters, Aug. 1996, p. 1645–1646. [12] Clevorn, T., Oldewurtel, F., Vary, P.: Combined Iterative Demodulation and Decoding using very short LDPC Codes and Rate-1 Convolutional Codes, in Conference on Information Sciences and Systems (CISS), Baltimore, MD, USA, Mar. 2005. [13] Weldon, E. J.: Difference-set cyclic codes, The Bell Systems Technical Journal, Sept. 1966, p. 1045–1055. [14] Lucas, R., Fossorier, M., Kou, Y., Lin, S.: Iterative De- coding of One-Step Majority Logic Decodable Codes Based on Belief Propagation, IEEE Transactions on Com- munications, June 2000, pp. 931–937. [15] Adrat, M., Vary, P.: Iterative Source-Channel Decoding: Improved System Design Using EXIT Charts, EURASIP Journal on Applied Signal Processing (Special Issue: Turbo Processing), May 2005. [16] Pearl, J.: Probabilistic Reasoning in Intelligent Systems: Net- works of Plausible Inference, Morgan Kaufmann, 1988. [17] Gray, F.: Pulse Code Communication, United States Patent Office, US patent 2,632,058, Mar. 1953. [18] Zeger, K., Gersho, A.: Pseudo-Gray Coding, IEEE Trans- actions on Communications, Dec. 1990, p. 2147–2158. [19] Hagenauer, J., Offer, E., Papke, L.: Iterative Decoding of Binary Block and Convolutional Codes, IEEE Transac- tions on Information Theory, Mar. 1996, p. 429–445. Birgit Schotsch e-mail: schotsch@ind.rwth-aachen.de Peter Vary e-mail: vary@ind.rwth-aachen.de Institute of Communication Systems and Data Processing RWTH Aachen University Templergraben 55 52056 Aachen, Germany Thorsten Clevorn e-mail: thorsten.clevorn@infineon.com COM Development Center NRW Infineon Technologies AG Düsseldorfer Landstrasse 401 47259 Duisburg, Germany © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ 85 Acta Polytechnica Vol. 47 No. 4–5/2007 80 81 82 83 84 85