turbo 1993code Berrou 1) 2[dB] SNR 05[dB] 1) interleaver parallel concatenated convolutional code ch

Size: px

Start display at page:

Download "turbo 1993code Berrou 1) 2[dB] SNR 05[dB] 1) interleaver parallel concatenated convolutional code ch"

ふみなわかはら
7 years ago
Views:

1 LDPC LDPC 2 LDPC LDPC LDPC 6-1 LDPC c /(13)

2 turbo 1993code Berrou 1) 2[dB] SNR 05[dB] 1) interleaver parallel concatenated convolutional code channel value 2 a priori value L a BCJR BCJR algorithm max log MAP max log MAP algorithm extrinsic L e1 value 2 L a2 2 1 L e a posteriori value, c /(13)

3 La1 Le1 La2 Le /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 /(13)

4 encoder 2 {q k } {u k } {p k } inner decoder channel value 1 a priori value extrinsic value outer decoder 10 a posteriori value (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) / sc BER E b /N 0 [db] 6 5 (7,5),(45,73), (7,5) (SC) =1000 c /(13)

5 LDPC LDPC Low-Density Parity Check sum-product iterative decoding Shannon LDPC ) Gallager 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 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 LDPC H H c /(13)

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} 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 /(13)

7 MP 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 LDPC 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 /(13)

8 (error floor) 19) PEG (ProgressiveEdge-Growth) 20) LDPC LDPC 21) c /(13)

9 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 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 /(13)

10 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) 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 /(13)

11 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 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 MP m i j (α), m ji (α) density evolution 12) l s P(s) c /(13)

12 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, pp , ) 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, pp , ) S Benedetto and G Montorsi, Unveiling turbo codes: some results on parallel concatenated coding schemes, IEEE Trans Inf Theory, vol42, no2, pp , ) RG Gallager, Low density parity check code, Research Monograph series, Cambridge, MIT Press, ) DJC MacKay, Good error-correcting codes based on very sparse matrices, IEEE Trans Inf Theory, vol45, no2, pp , Mar ) J Pearl: Probabilistic inference and expert systems, Morgan Kaufmann (1988) 7) BJ Frey, Graphical models for machine learning and digital communication, MIT Press, ),, ) DEX-SMI, :, : ) 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, ) ETSI EN V112 ( ), 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, ) T Richardson and R Urbanke, Design of capacity-approaching irregular low-density parity-check codes, IEEE Trans Inf Theory, vol47, no2, pp , Feb ) S ten Brink, Convergence behaviour of iterative decoded parallel concatenated codes, IEEE Trans Commun, vol49, no10, pp , Oct ) MG Luby, M Mitzenmacher, MA Shokrollahi, and DA Spielman, Improved low-density paritycheck codes using irregular graphs, IEEE Trans Inf Theory, vol47, no2, pp , Feb ) 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, pp , Nov ) 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 /(13)

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, pp , Oct ) JL Fan, Constrained coding and soft iterative decoding, Springer, ) 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, pp , ) XY Hu, E Eleftheriou, and DM Arnold, Regular and irregular progressive edge-growth Tanner graphs, IEEE Trans Inf Theory, vol51, no7, pp , Jan ) TJ Richardson and RL Urbanke, Efficient encoding of low-density parity-check codes, IEEE Trans Inf Theory, vol47, no2, pp , Feb ), 2002 c /(13)

25 11M15133 0.40 0.44 n O(n 2 ) O(n) 0.33 0.52 O(n) 0.36 0.52 O(n) 2 0.48 0.52

26 1 11M15133 25 11M15133 0.40 0.44 n O(n 2 ) O(n) 0.33 0.52 O(n) 0.36 0.52 O(n) 2 0.48 0.52 1 2 2 4 2.1.............................. 4 2.2.................................. 5 2.2.1...........................