0122229现代数字通信与编码理论 October 18,2012 XDU,Fall 2012 Lecture Notes Chapter 4 Binary Capacity-Approaching Codes This chapter is an introduction to modern coding theory.The encoding and decoding ngcod(including Trb cd LDPC as codes defined on graphs.The general graphical models will be addressed with emphasis on Forney-style graph. 4.1 Introduction It has been universally recognized that turbo-like codes are the most successful known class of codes,which shes The common feature of all codes in this family is the feasibiliy of n can achieve near-capacity decoder,which performs close to the ML decoder provided that SNR is sufficiently high. Typical examples of turbo-like codes are listed below. Turbo Codes(by Claude Berrou and A.Glavieux) Block turbo codes (or.Turbo product codes) Asvmnmetric turbo codes (by Costello and Massev) Serially concatenated codes with iterative decoding Mixed turbo codes (by Divsalar,et al) Doped turbo codes (by ten Brink) Concatenated Tree(CT Codes(by LiPing) Low-Density Parity-Check(LDPC)Codes Regular codes (by Gallager) Irregular LDPC codes (by Luby,Richardson,et al) Repeat-Accumulate(RA)Codes(by McEliece,Divsalar,Jin) 4.1.1 The Turbo-Era State of the Art on the AWGN Channel The performance of turbo-like codes on the power-limited AWGN channel is shown in Fig.4.1,where some classical FEC codes are also included for comparison. Turbo codes.also called parallel concatenated convolutional codes (PCCC)were proposed by Berrou and Glavieux in the ICC93.Performance within 0.5 dB of the channel capacity limit for BPSK was demonstrated. Since 1993,turbo codes have been widely studied and adopted in several communication systems,and the inherent concepts of the "turbo prineiple"have been applied to topics other than error correction coding.such as single-user The significance of turbo codes upon observing their performance Figure 4.2 shows simulation results of the original rate R=1/2 turbo code presented in [1]. 4.1
4-1 0122229 现代数字通信与编码理论 October 18, 2012 XDU, Fall 2012 Lecture Notes Chapter 4 Binary Capacity-Approaching Codes This chapter is an introduction to modern coding theory. The encoding and decoding principles of several classes of capacity-approaching codes (including Turbo codes, LDPC codes, and RA codes) will be discussed in detail. They can be viewed as codes defined on graphs. The general graphical models will be addressed with emphasis on Forney-style graph. 4.1 Introduction It has been universally recognized that turbo-like codes are the most successful known class of codes, which can achieve near-capacity performance over AWGN and many other channels. The common feature of all codes in this family is the feasibility of an iterative decoder, which performs close to the ML decoder provided that SNR is sufficiently high. Typical examples of turbo-like codes are listed below. Turbo Codes (by Claude Berrou and A. Glavieux) Block turbo codes (or, Turbo product codes) Asymmetric turbo codes (by Costello and Massey) Serially concatenated codes with iterative decoding Mixed turbo codes (by Divsalar, et al) Doped turbo codes (by ten Brink) Concatenated Tree (CT) Codes (by Li Ping) Low-Density Parity-Check (LDPC) Codes Regular codes (by Gallager) Irregular LDPC codes (by Luby, Richardson, et al) Repeat-Accumulate (RA) Codes (by McEliece, Divsalar, Jin) 4.1.1 The Turbo-Era State of the Art on the AWGN Channel The performance of turbo-like codes on the power-limited AWGN channel is shown in Fig. 4.1, where some classical FEC codes are also included for comparison. Turbo codes, also called parallel concatenated convolutional codes (PCCC), were proposed by Berrou and Glavieux in the ICC’93. Performance within 0.5 dB of the channel capacity limit for BPSK was demonstrated. Since 1993, turbo codes have been widely studied and adopted in several communication systems, and the inherent concepts of the “turbo principle” have been applied to topics other than error correction coding, such as single-user (equalization) and multi-user detection. The significance of turbo codes becomes clear upon observing their performance. Figure 4.2 shows simulation results of the original rate R = 1/2 turbo code presented in [1]
Sharnon bound 50. Rs245.23 (15.11 0. cc21w新 ubo(1024) iML decoding Golay(24,12) turbo(65536 B0H25,123) cc21, ce4均yVp.】 0 6 8 10 E/No (dB) Fig.4.1 Milestones in the drive towards channel capacity achieved over the past 50 years. 10 1 iteration 2iterations 401 iterations 3 iterations 10 181 10 1.5 E,N。indB Figure 4.2 Performance of a rate-1/2 binary turbo code with 16-state RSC codes as constituent codes.Block interleaver size =65536. 4-2
4-2 Fig. 4.1 Milestones in the drive towards channel capacity achieved over the past 50 years. Figure 4.2 Performance of a rate-1/2 binary turbo code with 16-state RSC codes as constituent codes. Block interleaver size = 65536. 0.5 1 1.5 2 10-7 10-6 10-5 10-4 10-3 10-2 10-1 100 Eb /No in dB BER 1 iteration 2 iterations 3 iterations 6 iterations 10 iterations 18 iterations
It has been reported [Chung01]that a well-designed irregular LDPC code of length 10has the performance within 0.04dB of the Shannon limit at BER=10 d-20 m 10 . 0.05 0.1 015 02 04 05 05 Irregular LDPC Codes,Density Evolution (Chung,Forney,Richardson,Urbanke,2001) For non-binary codes,the coded modulation schemes based on Turbo-like codes can also achieve near capacity performance on both AWGN and fading channels.Fig.4.3 compares the Turbo-TCM scheme to the ti TCM scheme It is se that the improvement made by coding becomes evident.The bit-interleaved coded modulation (BICM)and multilevel coding (MLC)schemes using LDPC codes exhibit similar or even better performance. 4-3
4-3 It has been reported [Chung01] that a well-designed irregular LDPC code of length 107 has the performance within 0.04dB of the Shannon limit at BER=10-6. For non-binary codes, the coded modulation schemes based on Turbo-like codes can also achieve near capacity performance on both AWGN and fading channels. Fig. 4.3 compares the Turbo-TCM scheme to the conventional TCM scheme. It is seen that the improvement made by coding becomes evident. The bit-interleaved coded modulation (BICM) and multilevel coding (MLC) schemes using LDPC codes exhibit similar or even better performance
M-QAM bound Shannon bound Y33 64-0AM Wei4043.5 -491943 32-QAM MLCI4QAN .hg. 16QAM 40(4,36) M43,7 T32刀c QPSK e44,3,5 P=109 2 4 1214 16 1820 E/N(dB) Figure 4.3 Performance of various coded modulation schemes based on turbo-like codes. 4.2 Binary Turbo Codes 4.2.1 The Invent of Turbo Codes Shannon理论证明，随机码是好码，但是它的译码却太复杂。因此，多少年来随机 编码理论一直是作为分析与证明编码定理的主要方法，而如何在构造码上发挥作用却并 未引起人们的足够重视。直到1993年，Tubo码的发现，才较好地解决了这一问题，为 Shannon随机编码理论的应用研究奠定了基础。 Turbo码，又称并行级连卷积码PCCC),是由C berrou等在ICC93会议上提出的 []。它巧妙地将卷积码和随机交织器结合在一起，实现了随机编码的思想，同时，采用 软输出迭代译码来逼近最大似然译码。 关于turbo码的发展历程，C.Berrou等在]中给出了详细的说明。因为C.Berrou 主要从事的是通信集成电路的研究，所以他们将SOVA译码器看作是“信噪比放大器”， 从而将电子放大器中的反馈技术应用于串行级联的软输出译码器，并且为了使两个译码 器工作于相同的时钟，以简化时钟电路设计，就提出了并行级联方式，这导致了tubo 码的发明。 Serially Concatenated Coding Fig.4.4 depicts a serially concatenated coding scheme,where the outer encoder/ decoder and inner encoder/decoder operate on different clocks.To solve this problem,Berrou proposed parallel concatenated coding schemes. 4-4
4-4 Figure 4.3 Performance of various coded modulation schemes based on turbo-like codes. 4.2 Binary Turbo Codes 4.2.1 The Invent of Turbo Codes Shannon 理论证明，随机码是好码，但是它的译码却太复杂。因此，多少年来随机 编码理论一直是作为分析与证明编码定理的主要方法，而如何在构造码上发挥作用却并 未引起人们的足够重视。直到 1993 年，Turbo 码的发现，才较好地解决了这一问题，为 Shannon 随机编码理论的应用研究奠定了基础。 Turbo 码，又称并行级连卷积码(PCCC)，是由 C.Berrou 等在 ICC’93 会议上提出的 [1]。它巧妙地将卷积码和随机交织器结合在一起，实现了随机编码的思想，同时，采用 软输出迭代译码来逼近最大似然译码。 关于 turbo 码的发展历程，C. Berrou 等在[?]中给出了详细的说明。因为 C. Berrou 主要从事的是通信集成电路的研究，所以他们将 SOVA 译码器看作是“信噪比放大器”， 从而将电子放大器中的反馈技术应用于串行级联的软输出译码器，并且为了使两个译码 器工作于相同的时钟，以简化时钟电路设计，就提出了并行级联方式，这导致了 turbo 码的发明。 Serially Concatenated Coding Fig. 4.4 depicts a serially concatenated coding scheme, where the outer encoder / decoder and inner encoder/decoder operate on different clocks. To solve this problem, Berrou proposed parallel concatenated coding schemes
Outer Block Inner Encode Interleaver Encoder Channel De- Inner coder Decoder Figure 4.4 Serially concatenated coding scheme Features of turbo codes Parallel concatenated coding Recursive convolutional encoders Pseudo-random interleaving ·Iterative decoding For details,see []and the references therein 4.2.2 Structure of Turbo Encoder The original turbo code is a parallel concatenation of two Recursive Systematie Co(RSC)codes.Fig.4.5 depicts a typical turbo encoder,where two constituent RSC encoders a udo-r ndom interleaver The inter used to permute the input bits such that the two encoders are operating on the same block of input bits,but in a different order. 信息序列口 交织器 递归卷积编 器RSC2 Figure4.5 Turbo码编码器的基本结构 对于一个长为N的二进制序列，我们用整数集合I=1,2,N来表示其比特位置 索引。则长为N的交织器可以被定义为索引集合T=1,2,N上的置换： π：I→I. 通常，我们用π()与k分别表示一个元素（比特）在原序列与交织后序列中的位置索引。 例如，记交织前的原序列为x个，交织后的序列为个，则有 4.5
4-5 Figure 4.4 Serially concatenated coding scheme Features of turbo codes • Parallel concatenated coding • Recursive convolutional encoders • Pseudo-random interleaving • Iterative decoding For details, see [1][2], and the references therein. 4.2.2 Structure of Turbo Encoder The original turbo code is a parallel concatenation of two Recursive Systematic Convolutional (RSC) codes. Fig. 4.5 depicts a typical turbo encoder, where two constituent RSC encoders are concatenated in parallel by a pseudo-random interleaver. The interleaver is used to permute the input bits such that the two encoders are operating on the same block of input bits, but in a different order. 交织器π 递归卷积编 码器 RSC1 复用 递归卷积编 码器 RSC2 信息序列 c 1p c 2p c c s 删余 u c p u Figure 4.5 Turbo 码编码器的基本结构 对于一个长为 N 的二进制序列，我们用整数集合 {1,2,., } N 来表示其比特位置 索引。则长为 N 的交织器可以被定义为索引集合 {1,2,., } N 上的置换： : . 通常，我们用 ( ) k 与 k 分别表示一个元素（比特）在原序列与交织后序列中的位置索引。 例如，记交织前的原序列为 x[ ] k ，交织后的序列为 y[ ] k ，则有 Outer Encoder Block Interleaver Inner Encoder Outer Decoder Deinterleaver Inner Decoder Channel