1 -- 2 6 LDPC 2012 3 1993 1960 30 LDPC 2 LDPC LDPC LDPC 6-1 LDPC 6-2 6-3 c 2013 1/(13)
1 -- 2 -- 6 6--1 2012 3 turbo 1993code Berrou 1) 2[dB] SNR 05[dB] 1) 6 1 2 1 1 interleaver 2 2 2 parallel concatenated convolutional code 6 1 6 2 1 channel value 2 a priori value L a1 1 0 5-3 BCJR BCJR algorithm max log MAP max log MAP algorithm extrinsic L e1 value 2 L a2 2 1 L e2 2 10 a posteriori value, c 2013 2/(13)
La1 Le1 La2 Le2 1 2 6 2 6 3 65536 1/2 02dB 05dB 6 3 =65536 iteration 6 4 Benedetto 2) serially concatenated vonvolutional codes {u k } k outer encoder 1 {p k } {u k} {p k } {u k } {p k } inner c 2013 3/(13)
encoder 2 {q k } {u k } {p k } inner decoder channel value 1 a priori value extrinsic value outer decoder 10 a posteriori value 6 4 6 5 3 (7,5) (1 + D + D 2, 1 + D 2 ) 8 6 (45,73) 3 (7,5) 1000 SNR (7,5) SNR (45,73) SNR 3) / 7 7-4 3 sc 0705 4573 10 2 BER 10 4 10 6 0 1 2 3 E b /N 0 [db] 6 5 (7,5),(45,73), (7,5) (SC) =1000 c 2013 4/(13)
1 -- 2 -- 6 6--2 LDPC 2012 3 6--2--1 LDPC Low-Density Parity Check sum-product iterative decoding Shannon LDPC 1960 4) Gallager 1950 1960 BCH RS LDPC 1990 turbo code 1) 5) MacKay LDPC probabilistic inference 6) machine learning 7) statistical mechanics 8) LDPC 9) 10) 11) LDPC GF(2) 2 LDPC 6--2--2 LDPC GF(2) m n H = [h i j ] C H sparse matrix C LDPC H C LDPC regular LDPC code LDPC LDPC irregular LDPC code LDPC H bipartite graph H p i (i = 1, 2,, m), c j ( j = 1, 2,, n) V c {p 1, p 2,, p m }, V b {c 1, c 2,, c n } V V c V b E {(p i, c j ) V c V b h i j = 1} Γ = (V, E) Γ C H Tanner V c, V b p i, c j check node bit node 6 6 6 6 6 LDPC H H c 2013 5/(13)
1 1 0 1 0 0 1 0 1 0 1 0 0 1 0 1 0 1 0 0 1 0 1 1 6 6 p 1 p 2 p 3 p 4 c 1 c 2 c 3 c 4 c 5 c 6 p i A i c j B j A i = { j h i j = 1}, B j = {i h i j = 1} 6--2--3 LDPC message message passing, MP MP p i (i = 1, 2,, m) c j ( j A i ) m i j (α) (α GF(2)) c j ( j = 1, 2,, n) p i (i B j ) m ji (α) (α GF(2)) 2 m i j (α) m ki (α k ) (k A i \ { j}, α k GF(2)) m ji (α) m l j (α) (l B j \ {i}) 6 7 m k1i(α k1 ) m k2i(α k2 ) m i j (α) c k1 c k2 c j c k Ai p i m k Ai 1i(α k Ai 1 ) p l1 p l2 p i p l B j m ji (α) m l2 j(α) m l1 j(α) c j m l B j 1 j(α) 6 7 MP m i j (α) m ji (α) c j {m i j (α) i B j } ĉ j ĉ = (ĉ 1, ĉ 2,, ĉ n ) Hĉ T = 0 ĉ ĉ c 2013 6/(13)
MP 6-3 6--2--4 LDPC LDPC MP LDPC LDPC ensemble of codes density evolution 12) [ 6-3 ] EXIT EXtrinsic Information Transfer Chart 13) MP MP S/N 2 threshold LDPC EXIT 6--2--5 LDPC 6-2-2 2 2 2 degree distribution 12) 2 2 LDPC LDPC 14) MP 4 MP 4 MP LDPC 15) combinatorial design 16), Ramanujan Ramanujan graph 17) quasi-cyclic code array 18) c 2013 7/(13)
(error floor) 19) PEG (ProgressiveEdge-Growth) 20) LDPC LDPC 21) c 2013 8/(13)
1 -- 2 -- 6 6--3 2012 3 6--3--1 GF(2) m n H = [h i j ] 2 C H A i (i = 1, 2,, m), B j ( j = 1, 2,, n) A i { j h i j 0}, B j {i h i j 0} r c C a posteriori probability P(c r) = κ m ( ) n δ c j, 0 P(r j c j ) j A i i=1 j=1 (6 1) P(r c) κ c GF(2) P(c r) = 1 n δ(a, b) a = b 1 a b 0 P(c r) c j marginal distribution P(c j = α r) c GF(2) n, c j=α P(c r) (α GF(2)) (6 2) c j ĉ j P(c j = 0 r) P(c j = 1 r) ĉ j = 0, P(c j = 0 r) < P(c j = 1 r) ĉ j = 1 ĉ j c j (6 2) n sum-product P(c j = α r) sum-product algorithm c j 6--3--2 1 6 8 (6 1) P(c j = α r) (α GF(2)) 2 (6 1) δ i δ( j A i c j, 0) (i = 1, 2,, m) P j P(r j c j ) ( j = 1, 2,, n) P(c r) c 1, c 2,, c n δ 1, δ 2,, δ m P 1, P 2,, P n c j P(c r) factor graph 6 9 (6 1) 6 9 c j δ i (i B j ) P j δ i c j ( j A i ) c 2013 9/(13)
1 h i j = 1 i, j m i j (α) = 1 (α GF(2)) 2 h i j = 1 i, j m ji (α) m ji (α) P(r j α) m i j(α) (α GF(2)) (6 3) i B j\{i} 3 h i j = 1 i, j m i j (α) m i j (α) m j i(α j ) (α = GF(2)) (6 4) α j GF(2) : j A i \ { j} st j Ai\{ j} α j α j Ai\{ j} 4 m i j (α) 2 4 Q j (α) ( j = 1, 2,, n) κ j Q j (0) + Q j (1) = 1 Q j (α) κ j P(r j α) m i j(α) i B j (α GF(2)) 6 8 δ 1 δ 2 δ 3 δ m c 1 c 2 c 3 c n P 1 P 2 P 3 P n (6 1) 6 9 P(c r) Q j (α) P(c j = α r) 6, Q j (α) 7) 6--3--3 1 4 m i j (α) Q j (α) Q j (0) Q j (1) ĉ j = 0, Q j (0) < Q j (1) ĉ j = 1 ĉ (ĉ 1, ĉ 2,, ĉ n ) Hĉ T = 0 ĉ 2 4 ĉ c 2013 10/(13)
m i j (α), m ji (α) (6 3), (6 4) sum-product decoding in probabilistic domain mi j(0) log m m ji(0) i j(1) log m ji(1) sum-product decoding in logarithm domain 22) 2 m i j (α) (6 3) max-product (6 1) Viterbi decoding 6--3--4 m i j (α), m ji (α) (6 3), (6 4) [ 6-2 ] MP 1 bit flipping MP bit-filliping decoding 2 peeling 2 peeling decoding MP stopping set LDPC 6--3--5 MP m i j (α), m ji (α) density evolution 12) l s P(s) c 2013 11/(13)
l MP s l P e (s, l) lim l P(s, l) MP 0 s threshold MP LDPC MP 4, 12) 1) C Berrou, A Glavieux, and P Thitimajshima, Near Shannon limit error-correcting coding and decoding: Turbo-codes, Proc IEEE Int Commun Conf, pp1064 1070, 1993 2) S Benedetto, D Divsalar, G Montorsi, and F Pollara, Serial concatenation of interleaved codes: Performance analysis, design, and iterative decoding, IEEE Trans Inf Theory, vol44, no3, pp909 926, 1998 3) S Benedetto and G Montorsi, Unveiling turbo codes: some results on parallel concatenated coding schemes, IEEE Trans Inf Theory, vol42, no2, pp409 428, 1996 4) RG Gallager, Low density parity check code, Research Monograph series, Cambridge, MIT Press, 1963 5) DJC MacKay, Good error-correcting codes based on very sparse matrices, IEEE Trans Inf Theory, vol45, no2, pp399 431, Mar 1999 6) J Pearl: Probabilistic inference and expert systems, Morgan Kaufmann (1988) 7) BJ Frey, Graphical models for machine learning and digital communication, MIT Press, 1998 8),, 1999 9) DEX-SMI, :, : 18 21 10) 8023an-2006, IEEE Standard for Information technology-telecommunications and information exchange between systems-local and metropolitan area networks-specific requirements Part 3: Carrier Sense Multiple Access with Collision Detection (CSMA/CD) Access Method and Physical Layer Specifications, 2006 11) ETSI EN 302 307 V112 (2006-06), European Standard (Telecommunications series) Digital Video Broadcasting (DVB); Second generation framing structure, channel coding and modulation systems for Broadcasting, Interactive Services, News Gathering and other broadband satellite applications, 2006 12) T Richardson and R Urbanke, Design of capacity-approaching irregular low-density parity-check codes, IEEE Trans Inf Theory, vol47, no2, pp619 637, Feb 2001 13) S ten Brink, Convergence behaviour of iterative decoded parallel concatenated codes, IEEE Trans Commun, vol49, no10, pp1727 1737, Oct 2001 14) MG Luby, M Mitzenmacher, MA Shokrollahi, and DA Spielman, Improved low-density paritycheck codes using irregular graphs, IEEE Trans Inf Theory, vol47, no2, pp585 598, Feb 2001 15) Y Kou, S Lin, and MPC Fossorier, Low-density parity-check codes based on finite geometries: a rediscovery and new results, IEEE Trans Inf Theory, vol47, no7, pp2711 2736, Nov 2001 16) SJ Johnson and ST Weller, Regular low-density parity-check codes from combinatorial designs, Proc of Inf Theory Workshop 2001, pp90 92, Sep 2001 c 2013 12/(13)
17) J Rosenthal and PO Vontobel, Constructions of LDPC codes using Ramanujan graphs and ideas from Margulis, Prof of 38th Allerton Conf on Commun, Control and Computing, pp248 257, Oct 2000 18) JL Fan, Constrained coding and soft iterative decoding, Springer, 2001 19) DJC MacKay and MC Davey, Evaluation of Gallager codes for short block length and high rate applications, Codes, Systems, and Graphical Models, Springer-Verlag, New York, pp113 130, 2001 20) XY Hu, E Eleftheriou, and DM Arnold, Regular and irregular progressive edge-growth Tanner graphs, IEEE Trans Inf Theory, vol51, no7, pp386 398, Jan 2005 21) TJ Richardson and RL Urbanke, Efficient encoding of low-density parity-check codes, IEEE Trans Inf Theory, vol47, no2, pp638 656, Feb 2001 22), 2002 c 2013 13/(13)