57

韓國電磁波學會誌 電磁波技術 第 27 卷第 6 號 2016 年 11 月 5G 를위한채널코드후보기술과연구동향. 서론 4G,, PC,.. 4G, 5G. 5G (high data rate), (low latency), (ultra low cost), (high reliability), (massive connectivity) [1]~[3].. 1990 Shannon limit turbo [4], lowdensity parity-check(ldpc) [5] polar [6]. en/decoding, 5G,,,. 5G turbo, LDPC, polar.. Turbo 코드 Turbo 4G LTE. Turbo Shannon limit encoder,. 2-1 Turbo Encoder Turbo encoder component encoder interleaver. Parallel Concatenated Convolutional Code (PCCC). [ 1] 4G LTE turbo encoder [7]. convolutional encoder 3 linear feedback shift register(lfsr), convolutional encoder bit c k [ 그림 1] 1/3 turbo encoder [7]. 20

韓國電磁波學會誌第 27 卷第 6 號 2016 年 11 月 bit z k 1/2. convolutional encoder, bit c k interleaving c k, bit z k. turbo 1 bit 1 bit 2 bit 1/3. Turbo decoder encoding bit, encoder 0 trellis termination. bit encoding, [ 1] LFSR convolutional encoder 3 encoding 0. Turbo convolutional encoder, interleaver. 2-2 Turbo Decoder Turbo convolutional, con- volutional decoder decoding. Convo- lutional decoding, turbo code decoding BCJR decoding [8]. BCJR decoding convolutional maximum a posteriori(map) decoder, turbo decoding soft-input soft-output(siso) de- coding. log domain BCJR deco- ding. convolutional encoding LFSR Mar- kov state transition, trellis. [ 2] 2 convolutional encoder trellis diagram. codeword T state transition. t i t bit. codeword, log-likelihood ratio(llr),. bit a priori probability LLR,, t [ 그림 2] 2 convolutional encoder trellis diagram [8] = 0,, T s s state transition metric γ t (s, s). γ t (s, s) =, s s state transition bit. γ forward recur- sion α, backward recursion β. x, y x > y. max * (x, y) = x + log((1 + e yx )) x y max * (y, x)., 2. t = 0, s 0 state α 0 (s) =, s = 0 state α 0 (0) = 0. forward recursion. α t (s) = max (α t1 (s ) + γ t (s, s)) 21

5G, t = T s 0 state β T (s) =, s = 0 β T (s) = 0 backward recursion. β t1 (s ) = max (β t (s) + γ t (s, s)) α β, a posteriori probability LLR,., = max (α t1 (s )+ max (α t1 (s )+ = max (α t1 (s )+ max (α t1 (s )+., x = 0, 1, y = 0, 1 = x s s state transition. Turbo decoder convolutional encoder BCJR decoder. BCJR decoder decoding LLR L p. decoder interleaver deco- der a priori L a., decoder deinterleaver decoder a priori L a., decoder LLR L p bit.. 3-1 LDPC Decoder LDPC turbo decoder( H) [9]. < 1> N=10, K=5 (NK) N. check node(cn, c i, i = 1,, 5), variable node(vn, v j, j = 1,, 10). [ 4] (bipartite graph), LDPC. [ 4] CN, VN., (VN) 0 encoding. [ 3] CN c 1 H 5 1, 1, 2, 5, 7, 10., 1, 2, 5, 7, 10 codeword bit binary field 0, [ 4] c 1 v 1, v 2, v 5, v 7, v 10 bit 0. CN. LDPC belief propagation(bp) 1 1 0 0 1 0 1 0 0 1 0 0 1 1 0 0 0 0 1 0 H = 1 0 1 0 0 1 0 1 0 0 1 0 0 1 0 1 1 0 1 0 0 1 0 0 1 0 0 1 1 1 [ 그림 3] N = 10, K = 5. LDPC 코드 LDPC 4G WiMax Wi-Fi,. LDPC decoder., Shannon limit. LDPC, LDPC [ 그림 4] 3 (bipartite graph) 22

韓國電磁波學會誌第 27 卷第 6 號 2016 年 11 月 decoding, 1 VN CN [10]. N v,j N c,i v j CN, c i VN. v j demodulator LLR L ch,j. v j c i M j,i, c i v j E i,j. M j,i E i,j 0. 1 BP decoding. VN v j, j = 1,, N M j,i = L ch,j + E i,j, CN M j,i E i,j = 2tanh 1 tanh. 1 BP decoding VN CN v j a posteriori LLR L p,j = L ch,j + E i,j. L p,j 0 bit 0, 1, CN. 0 codeword, decoding. 0 BP decoding., BP decoding. 3-2 LDPC Encoder LDPC block, H G encoding., N LDPC, K N G, encoding en- coder,. encoding, encoder quasi-cyclic LDPC(QC-LDPC). QC-LDPC H sub- block, sub-block cyclic shift z z identity,. z N. [ 5] IEEE 802.16e WiMax [11] 1/2. 1 z z, 0 z z identity cyclic shift. QC-LDPC LFSR encoding, [ 5] H dual-diagonal, encoding [12],[13]. 3-3 LDPC 코드의최근연구동향 LDPC, LDPC (non-binary LDPC; NB-LDPC) LDPC [14]., LDPC LDPC. LDPC decoding minsum(ms) decoding LDPC CN extended min-sum(ems) decoding [15], MS EMS decoding [16]~[18]. CN trellis trellis-ems (T-EMS) [19],[20]., spatial-coupled LDPC(SC-LDPC) threshold saturation SC-LDPC [21]~[23]. SC-LDPC convolu- [ 그림 5] IEEE 802.16e 1/2 LDPC [11] 23

5G tional encoder LDPC LDPC convolutional, protograph LDPC. [ 6] protograph spatial coupling. SC-LDPC (binary erasure channel; BEC), BEC AWGN [24],[25].. Polar 코드 [ 7] W 2 Polar 2008 Arikan (polarization) [6]. Polar turbo LDPC. 4-1 채널양극화와 Polar Encoder (capacity). [ 7] W I(W) N = 2 W 2 [6]. bit u 1 u 2 x 1 = u 1 + u 2, x 2 = u 2 x 1 x 2 I(W)., u 1 u 2 I(W ), I(W ) I(W ) = I(W) 2, I(W ) = 2I(W)I(W) 2., u 1 u 2. Polar, [ 8]. W N/2 N R N shuffle W N. [ 9] [ 그림 8] W N/2 W N [6]. index 0, index 1. 0 1. [ 그림 6] SC-LDPC protograph coupling [22] polar N bit u i, K index. NK bit bit( 0), frozen bit. K index bit, N bit codeword (N 24

韓國電磁波學會誌第 27 卷第 6 號 2016 年 11 月 [ 그림 10] SC decoding [26] [ 그림 9] 50% BEC N = 2 10 i = 1,, N [6] K)/N polar. 4-2 Polar Decoder 와최근연구동향 Polar decoding successive cancellation(sc) decoding. index i = 1 i = N u i. Polar decoding [ 10], [ 11] tree [26]. [ 10] [ 11] N = 8, i = 1, 2, 3, 5 u i 0 frozen. i level u i, decoding process,. root bit (path metric) 0 1 i bit 0 1. [ 10], 3 bit frozen bit 1.00 (u 1, u 2, u 3 ) = (000). 4 bit(level 4) v 4 0 1 0.55, 0.45 0. Level 4 (u 1, u 2, u 3, u 4 ) = (0000) (0001) metric Level 4. Level 5 frozen bit u 5 = 0 Level 6. Level 6 (u 1, u 2, u 3, u 4, u 5, u 6 ) = (000000) (000001) 0.30, 0.25. (u 1, u 2, u 3, u 4, u 5, u 6 ) = (000000), Level 7. Level 8 [ 그림 11] SCL decoding (L = 2) [26], (00000011). SC decoding. Polar SC decoding list stack SCL decoding SCS decoding [27],[28]. [ 11] SCL decoding. 2 path(list) L = 2. Level 1, 2, 3 frozen bit (000)., 4 Level 0 1, 2 path (0000) (0001) path metric 0.55, 0.45. Level 5 frozen bit Level 6 (00000) (00010) u 6 = 0, 1 path metric. [ 11] 25

5G 0.30, 0.25, 0.40, 0.05. L = 2 path, L path metric (000000) (000100), Level 7. u 7 = 0, 1 path metric 4 2 path. L path path metric path decoding. SCL decoding cyclic redundancy check(crc) CRC-aided SCL(CA- SCL) decoding [29]. CA-SCL decoding SCL decoding path CRC path.. 결론. 5G turbo, LDPC, polar. Turbo encoder, decoder.,,. LDPC decoder,., LDPC LDPC. polar,. 5G,,. [ 12] WCDMA LTE turbo, WiMax LD- PC, Polar decoding BLER [26]. 1024(LDPC 1056), 1/2. LTE turbo WiMax LDPC, LTE turbo. Polar SC decoder turbo, LDPC, CA-SCL decoding LTE turbo [ 그림 12] Turbo LDPC, polar [26] 참고문헌 [1] Nokia, "5G use cases and requirements", White Paper, 2014. [2] http://www.huawei.com/5gwhitepaper/ [3],,,, "5G Massive IoT ",, 31(1), pp. 68-77, 2016. [4] C. Berrou, A. Glavieux, "Near optimum error correcting coding and decoding: Turbo-codes", IEEE Transactions on Communications, vol. 44, no. 10, Oct. 1996. [5] D. J. C. MacKay, R. M. Neal, "Near shannon limit performance of low density parity check codes", Electronics Letters, vol. 33, no. 6, Mar. 1997. [6] E. Arikan, "Channel polarization: A method for constructing capacity-achieving codes for symmetric binar-input memoryless channels", IEEE Transactions on Information Theory, vol. 55, no. 7, Jul. 2009. [7] http://www.3gpp.org/ftp/specs/2011-03/rel-10/36_series/36212- a10.zip [8] L. R. Bahl, J. Cocke, F. Jelinke, and J. Raviv, "Optimal decoding of linear codes for minimizing symbol error rate", IEEE Transactions on Information Theory, Mar. 1974. [9] R. G. Gallager, "Low-density parity-check codes", IRE Tran- 26

韓國電磁波學會誌第 27 卷第 6 號 2016 年 11 月 sactions on Information Theory, vol. 8, issue 1, Jan. 1962. [10] S. J. Johnson, Iterative Error Correction, Cambridge University Press, 2010. [11] http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=1603394 [12],,,, "IEEE 802.16e LDPC ",, 20(2), pp. 27-33, 2004 12. [13] Z. Cai, J. Hao, P. H. Tan, S. Sun, and P. S. Chin, "Efficient encoding of IEEE 802.11n LDPC codes", Electronics Letters, vol. 42, no. 25, Dec. 2006. [14] M. C. Davey, D. MacKay, "Low-density parity check codes over GF(q)", IEEE Communications Letters, vol. 2, no. 6, Jun. 1998. [15] D. Declercq, M. Fossorier, "Decoding algorithms for nonbinary LDPC codes over GF(q)", IEEE Transactions on Communications, vol. 55, no. 4, Apr. 2007. [16] A. Voicila, D. Declercq, F. Verdier, M. Fossorier, and P. Urard, "Low-complexity decoding for non-binary LDPC codes in high order fields", IEEE Transactions on Communications, vol. 58, no. 5, May 2010. [17] X. Chen, C.-L. Wang, "High-throughput efficient nonbinary LDPC decoder based on simplified min-sum algorithm", IEEE Transactions on Circuits and Systems-I: Regular Papers, vol. 59, no. 11, Nov. 2012. [18] C.-L. Wang, X. Chen, Z. Li, and S. Yang, "A simplified min-sum decoding algorithm for non-binary LDPC codes", IEEE Transactions on Communications, vol. 61, no. 1, Jan. 2013. [19] E. Li, D. Declercq, and K. Gunnam, "Trellis-based extended min-sum algorithm for non-binary LDPC codes and its hardware structure", IEEE Transactions on Communications, vol. 61, no. 7, Jul. 2013. [20] J. O. Lacruz, F. G.-Herrero, J. Valls, and D. Declercq, "One minimum only trellis decoder for non-binary low-density parity-check codes", IEEE Transactions on Circuits and Systems-I: Regular Papers, vol. 62, no. 1, Jan. 2015. [21] M. Lentmaier, A. Sridharan, D. J. Costello, Jr., and K. S. Zigangirov, "Iterative decoding threshold analysis for LDPC convolutional codes", IEEE Transactions on Information Theory, vol. 56, no. 10, Oct. 2010. [22] S. Kudekar, T. J. Richardson, and R. L. Rubanke, "Threshold saturation via spatial coupling: Why convolutional LDPC ensembles perform so well over the BEC", IEEE Transactions on Information Theory, vol. 57, no. 2, Feb. 2011. [23] D. J. Costello, Jr., L. Dolecek, T. E. Fuja, J. Kliewer, D. G. M. Mitchell, and R. Smarandache, "Spatially coupled sparse codes on graphs: Theory and practice", IEEE Communications Magazine, Jul. 2014. [24] L. Schmale, K. Mahdaviani, "Laterally connected spatially coupled code chains for transmission over unstable parallel channels", in Proc. of 8th International Symposium on Turbo Codes and Iterative Information Processing (ISTC), 2014. [25] Md. N.-A-Rahim, K. D. Nguyen, and G. Lechner, "Anytime reliability of spatially coupled codes", IEEE Transactions on Communications, vol. 63, no. 4, Apr. 2015. [26] K. Niu, K. Chen, J. Lin, and Q. T. Zhang, "Polar codes: Primary concepts and practical decoding algorithms", IEEE Communications Magazine, Jul. 2014. [27] I. Tai, A. Vardy, "List decoding of polar codes", IEEE Transactions on Information Theory, vol. 61, no. 5, May 2015. [28] K. Niu, K. Chen, "Stack decoding of polar codes", Electronics Letters, vol. 48, no. 12, 2012. [29] K. Niu, K. Chen, "CRC-aided decoding of polar codes", IEEE Communications Letters, vol. 16, no. 10, Oct. 2012. 27

5G 필자소개 박진수 2009 2: () 2009 3: [ 주관심분야 ], 김강산 2016 2: () 2016 3: [ 주관심분야 ], 김인선 2012 8: () 2012 9: [ 주관심분야 ], 송홍엽 1984 2: () 1986 5: University of Southern California Dept. of EE. Systems () 1991 12: University of Southern California Dept. of EE. Systems () 1992 11993 12: Post-Doc Research Associate, University of Southern California Dept. of EE. Systems 1994 11995 8: Senior Engineer, Qualcomm Inc., San Diego, California. 2002 32003 2: Visiting Professor, University of Waterloo, Canada 1995 9 : [ 주관심분야 ],,,, 28