Chapter9 9 LDPC sum-product LDPC 9.1 ( ) 9.2 c 1, c 2, {0, 1, } SUM, PROD : {0, 1, } {0, 1, } SUM(c 1, c 2,, c n ) := { c1 + + c n (c n0 (1 n

9 LDPC sum-product 9.1 9.2 LDPC 9.1 ( ) 9.2 c 1, c 2, {0, 1, } SUM, PROD : {0, 1, } {0, 1, } SUM(c 1, c 2,, c n ) := { c1 + + c n (c n0 (1 n 0 n)) ( ) 0 (N(0 c) > N(1 c)) PROD(c 1, c 2,, c n ) := 1 (N(0 c) < N(1 c)) ( ) N(x c) := N(x c 1, c 2,, c n ) N( ) ( 6.6 ) x {0, 1} SUM(c 1, c 2,, c n )

2 9 LDPC sum-product SUM({c n0 n 0 {1, 2,, n}}) 9.3 () 9.4 9.5 ( sum-product ) 9.6 H 0 F 0 F 0 F 1 F 1 F 1 F 0 F 0 F 0 F H := 1 F 0 F 0 F 1 F 0 F 0 F 0 F 1 F 0 F. 1 F 1 F 1 F 0 F 1 F 0 F 1 F 1 F 1 F y y := (, 0 F, 1 F,, 0 F, 1 F, 0 F, 0 F, ) l max := 20 1. H y 9 2. l l := 1 β b 0 F 1 F β := 0 F 0 F 1 F 0 F 0 F 0 F 3. α (1, 1) H (1, 1) 0 F 3. (2, 1) H (2, 1) 1 F 3. α 2,1 := SUM(β 2,4, β 2,8 ) = SUM(, 0 F ) =

9.2 LDPC 3 (1, 4) H (1, 4) 1 F 3. α 1,4 := SUM(β 1,5, β 1,6 ) = SUM(0 F, 1 F ) = 0 F + 1 F = 1 F (3, 8) H (3, 8) 1 F 3. α 3,8 := SUM(β 3,1, β 3,2, β 3,3, β 3,5, β 3,7, β 3,9 ) = SUM(, 0 F, 1 F, 0 F, 0 F, ) = α 1 F α =. 4. β (1, 1) H (1, 1) 0 F 4. (2, 1) H (2, 1) 1 F 4. 1 (2, 1) F 2 (2, 1) (1, 4) H (1, 4) 1 F 4. β 1,4 := PROD(y 4, α 2,4 ) = PROD(, ) = (2, 4) H (2, 4) 1 F 4. β 2,4 := PROD(y 4, α 1,4 ) = PROD(, 1 F ) = 1 F β

4 9 LDPC sum-product β = 0 F 1 F 1 F 0 F 0 F 1 F 0 F 0 F 0 F. 5. c 1, 2, 4 1 c 1 := PROD(y 1, α 2,1, α 3,1 ) = PROD(,, ) =. 2 c 2 := PROD(y 2, α 3,2 ) = PROD(0 F, ) = 0 F. 4 c 4 := PROD(y 4, α 1,4, α 2,4 ) = PROD(, 1 F, ) = 1 F. c c = (, 0 F, 1 F, 1 F, 0 F, 1 F, 0 F, 0 F, ). 6. c 7. l = 1, l max = 20 l > l max 8. l = 2 3. 3. α 1 F α = 1 F. 4. β 1 F 0 F 1 F β = 1 F 0 F. 1 F 0 F 1 F 0 F 0 F 0 F 5. c c = (1 F, 0 F, 1 F, 1 F, 0 F, 1 F, 0 F, 0 F, ). 6. c 7. l = 2, l max = 20 l > l max

9.2 LDPC 5 8. l = 3 3. 3. α 1 F 0 F 1 F α = 1 F. 0 F 4. β 0 F 1 F β = 1 F 0 F. 1 F 0 F 1 F 0 F 0 F 0 F 5. c c = (1 F, 0 F, 1 F, 1 F, 0 F, 1 F, 0 F, 0 F, 0 F ). 6. c Hc T = 0 c = (1 F, 0 F, 1 F, 1 F, 0 F, 1 F, 0 F, 0 F, 0 F ) 9.7 ( ) 9.8 9.9 9.10 9.11 ( LDPC )

6 9 LDPC sum-product 9.3 9.12 9.13 ((λ, ρ) LDPC ) m 0, n 0 H (m 0, n 0 ) h m0,n 0 h m0,n 0 = 1 sumproduct α, β (m 0, n 0 ) H p sum-product α m0,n 0, β m0,n 0 α m0,n 0 = β m0,n 0 = sum-product y n 0 y n0 y n0 = n 0 y n0 p 0 := p sum-product β m0,n 0 y n0 β m0,n 0 = p α m0,n 0 := SUM({β m0,n 1 n 1 V (m 0 ) \ {m 0 }}) α m0,n 0 = {β m0,n 1 n 1 V (m 0 ) \ {n 0 }} ρ 1 1 α m0,n 0 = 1 α m0,n 0 β p α m0,n 0 (1 ) (m 0,n 0 ) = (1 p) ρ 1 α m0,n 0 F 2 α m0,n 0 = 1 (1 p) ρ 1.

9.3 7 β m0,n 0 := PROD(y n0, {α m1,n 0 m 1 F (n 0 ) \ {m 0 }}) β m0,n 0 = y n0 {α m1,n 0 m 1 F (n 0 ) \ {m 0 }} β m0,n 0 = y n0 p λ 1 1 (1 p) ρ 1 λ 1 (1 (1 p) ρ 1 ) λ 1 β m0,n 0 = p(1 (1 p) ρ 1 ) λ 1 1) p 1 l (l 2)β m0,n 0 = 1 (1 p l 1 ) ρ 1. l α m0,n 0 = p(1 (1 p l 1 ) ρ 1 ) λ 1 p l l β m0,n 0 = p l p l = { p (l = 0) p(1 (1 p l 1 ) ρ 1 ) λ 1 (l 1) (9.2) 1)

8 9 LDPC sum-product 9.14 9.15 9.16 9.4 LDPC 9.17 9.18 ( ) 9.19 9.20 ( ) 9.21 () 9.22 ( ) 9.23 ( ) LDPC 1 1 ( 9.21) LDPC (2, 5) LDPC LDPC 4 4

9.5 9 1 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 0 0 1 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 1 I(a) a ( 0 2 0 1 2 ) 2 0 3 2 0 a 9.24 9.25 9.5 9.26 () 9.27 ( ) 9.28 ( ) 9.29 ( )

10 9 LDPC sum-product 9.30 9.31 9.32 ( ) 9.33 () 9.34 ( ) 9.35 9.36 ( ) 9.37 9.6 9.38 ( ) 9.39 9.40 (, ) P X n W : Y X R n y Y n W P P W ( y) : X n R 0 P W (x y) := P (x)w (y x) x X n P (x )W (y x ). (x X n ) 0 y

9.6 11 Y n r y P W ( y) X n P W ( y) W y 9.41 W : {0, 1} {0, 1} R P : {0, 1} R x, y {0, 1} P W { 1 p (x = y) P W (x y) = p (x y) 9.42 W : {0, 1} {0, 1, } R P : {0, 1} R x {0, 1} y {0, 1, } P W 1 (y = ) 2 P W (x y) = 1 (y, x = y) 0 (y, x y) 9.43 C X n X n P (C) 1 (x C) P (C) (x) := C 0 (x C) W (y x) (x C) P (C)W W (y c) (x y) = c C 0 (x C) (9.3) (9.4) C P (C) 9.44 ( (MAP )) W : Y X R (f, ϕ MAP ) W n (f, ϕ MAP ) M (f, ϕ MAP )

12 9 LDPC sum-product P : X n R ϕ MAP (maximum a posteriori probability) y Y n r P W (f(ϕ MAP (y)) y) = max M M P W (f(m) y). 9.45 9.4.3 (9,4) W n (y x) P (C)W W (x y) = n (x C) (y c) c C 0 (x C) y 9.46 F 2 Y W : Y F 2 R H m n F 2 C H x F n 2, y Y n r P (C)W ( y) ( m [ P (C)W (x y) = K δ K x F n 2 m 0=1 ν V (m 0 ) ]) ( n ) x ν = 0 W (y n1 x n1 ). n 1=1 P (C)W (x y) = 1 δ[ ] [ ] 1 0

9.6 13 9.4.3 (9,4) W (y x) (x C) P (C)W W (y c) (x y) = c C 0 (x C) K KW (y x) = K n W (y P (C)W n1 x n1 ) (x C) (x y) = n 1 =1 0 (x C) x = (x 1, x 2,, x n ), y = (y 1, y 2,, y n ) m m 0 =1 δ [ ν V (m 0) x ν = 0 m m 0 =1 ] δ [ = { 1 (x C) ν V (m 0) 0 (x C) x ν = 0 ] Hx T 0 1 x C 1 9.47 ( ) n W : Y X R P : X R y Yr n P W ( y) : X n R W y P W ( y) 1 n 0 n Pn W 0 ( y) : X R Pn W 0 (x n0 y) := P W (x y). (x n0 X ) x/[n]\{n 0 }

14 9 LDPC sum-product := x/[n]\{n 0} x 1 X x n0 1 X x n0 +1 X x n X x n0 Pn W 0 ( y) ( P y n 0 ) 9.48 ( (MPM(maximum posterior marginal) )) W (f, ϕ MP M ) W n (f, ϕ MP M ) P : X R M (f, ϕ MP M ) Y (f, ϕ MP M ) ϕ MP M y Y n r 1 n 0 n P W n 0 (c n0 y) = max x X P W n 0 (x y). f(ϕ MP M (y)) = (c 1, c 2,, c n ) δ [ ν V (m 0 ) x ν = 0 ] δ[x/v (m 0 )] 9.49 ( ) F 2 H m n F 2 W : Y F 2 R C H P (C) : F n 2 R 9.4.3 y Y n n 0 1 n 0 n Pn W 0 ( y) : F 2 R n 0 1 m 0 m n 0 α m0,n 0 : F 2 R

9.6 15 ( α m0,n 0 (x n0 ) := W (y/v (m 0, n 0 ) \ {n 0 } x/v (m 0, n 0 ) \ {n 0 }) x/v (m 0,n 0 )\{n 0 } ) δ[x/v (m 0)] m 0 F (m0,n0) x/v (m 0, n 0 ) V (m 0, n 0 ) P n (C)W 0 (x n0 y) = KW (y n0 x n0 ) α m0,n 0 (x n0 ). m 0 F (n 0 ) K 9.46 K ( ) K := 1/ W (y n0 0) α m1,n 0 (0) + W (y n0 1) α m1,n 0 (1) m 1 F (n 0 ) m 1 F (n 0 ) P n (C)W 0 (x n0 y) := P (C)W (x y) x/[n]\{n 0} ( 9.46) P n (C)W 0 (x n0 y) = K m W (y [n] x [n] ) δ[x/v (m 0 )] x/[n]\{n 0 } x n0 P (C)W n 0 (x n0 y) = KW (y n0 x n0 ) x/[n]\{n 0 } m 0=1 W (y [n]\{n0 } x [n]\{n0 }) m m 0=1 δ[x/v (m 0 )] 9.7 v n0 (f, v n0 )

16 9 LDPC sum-product v n0 9.7 2 F (n 0 ) 1 f m0 F (n 0 ) f m0 F (m 0, n 0 ) v n0 V (m 0, n 0 ) F (m 1, n 1 ) m m 0 =1 = m 0 F (n 0) m 0 F (m0,n0) Pn W 0 (x n0 y) = KW (y n0 x n0 ) W (y [n]\{n0 } x [n]\{n0 }) x/[n]\{n 0} m 0 F (n 0) m 0 F (m0,n0) δ[x/v (m 0)] [n] \ {n 0 } = (V (m 0, n 0 ) \ {n 0 }) m 0 F (n 0) P W n 0 (x n0 y) = KW (y n0 x n0 ) ( m 0 F (n 0 ) x/v (m 0,n 0 )\{n 0 } m 0 F (m 0,n 0 ) W (y/v (m 0, n 0 ) \ {n 0 } x/v (m 0, n 0 ) \ {n 0 }) δ[x/v (m 0)] )

9.6 17 α m0,n 0 Pn W 0 (x n0 y) = KW (y n0 x n0 ) α m0,n 0 (x n0 ) m 0 F (n 0 ) 9.50 ( ) β m0,n 0 : F 2 R β m0,n 0 (x n0 ) := W (y n0 x n0 ) α m1,n 0 (x n0 ). m 1 F (n 1 )\{m 0 } α m0,n 0 (x n0 ) = δ[x/v (m 0 )] β m0,n 1 (x n1 ). x/v (m 0 )\{n 0 } n 1 V (m 0 )\{n 0 } F (m 0, n 0 ) \ {m 0 } = n 1 V (m 0)\{n 0} m 1 F (n 1)\{m 0} F (m 1, n 1 ) α m0,n 0 α m0,n 0 (x n0 ) = δ[x/v (m 0 )]W (y/v (m 0, n 0 ) \ {n 0 } x/v (m 0, n 0 ) \ {n 0 }) x/v (m 0,n 0 )\{n 0 } δ[x/v (m 1)] n 1 V (m 0 )\{n 0 } m 1 F (n 1 )\{m 0 } m 1 F (m 1,n 1 ) W (y/v (m 0, n 0 ) \ {n 0 } x/v (m 0, n 0 ) \ {n 0 }) α m0,n 0 (x n0 ) = δ[x/v (m 0 )] W (y n1 x n1 ) x/v (m 0,n 0 )\{n 0 } m 1 F (n 1 )\{m 0 } m 1 F (m 1,n 1 ) n 1 V (m 0 )\{n 0 } W (y/v (m 1, n 1 ) \ {n 1 } x/v (m 1, n 1 ) \ {n 1 }) δ[x/v (m 1)]

18 9 LDPC sum-product, α m0,n 0 (x n0 ) = δ[x/v (m 0 )] W (y n1 x n1 ) x/v (m 0)\{n 0} ( n 1 V (m 0)\{n 0} m 1 F (n 1 )\{m 0 } x/v (m 1,n 1 )\{n 1 } δ[x/v (m 1 )] W (y/v (m 1, n 1 ) \ {n 1 } x/v (m 1, n 1 ) \ {n 1 }) ) = δ[x/v (m 1)] m 1 F (m 1,n 1 ) δ[x/v (m 0 )] W (y n1 x n1 ) x/v (m 0)\{n 0} m 1 F (n 1)\{m 0} α m1,n 1 (x n1 ) n 1 V (m 0)\{n 0} β m0,n 1 (x n1 ) α m0,n 0 (x n0 ) = δ[x/v (m 0 )] β m0,n 1 (x n1 ) x/v (m 0 )\{n 0 } n 1 V (m 0 )\{n 0 } 9.7 sum-product 9.51 (( ) sum-product )

9.7 sum-product 19 * F 2 H = (h m0,n 0 ) W : Y F 2 R Y y l max * H C c? 1. H y H m n 2. h m0,n 0 = 1 (m 0, n 0 ) β m0,n 0 (0), β m0,n 0 (1) β m0,n 0 (x) := W (y n0 x). x {0, 1} ( ) l := 1 3. h m0,n 0 = 1 (m 0, n 0 ) α m0,n 0 (0), α m0,n 0 (1) α m0,n 0 (x) := K c/v (m 0 )\{n 0 } n 1 V (m 0 )\{n 0 } [ δ ν V (m 0 )\{n 0 } β m0,n 1 (c n1 ) ] c ν = x x {0, 1} K α m0,n 0 (0) + α m0,n 0 (1) = 1 4. h m0,n 0 = 1 (m 0, n 0) β m0,n 0 (0) β m0,n 0 (1) β m0,n 0 (x) := K W (y n0 x) m 1 F (n 0 )\{m 0 } α m1,n 0 (x) x {0, 1} K β m0,n 0 (0) + β m0,n 0 (1) = 1 5. 1 n 0 n γ n0 (0), γ n0 (1) γ n0 (x) := W (y n0 x) α m1,n 0 (x) m 1 F (n 0 ) x {0, 1} γ n0 (0) γ n0 (1) F 2 ĉ n0 ĉ n0 := 0 ĉ n0 := 1 6. H(ĉ 1, ĉ 2,, ĉ n0 ) T = 0 c := (ĉ 1, ĉ 2,, ĉ n0 ) 7. 7. l l max? 8. l < l max l 1 3. ( )

20 9 LDPC sum-product 9.8 sum-product 9.52 ( sum-product ) * F 2 H = (h m0,n 0 ) W : Y F 2 R Y y l max * H C c? 1. H y H m n 2. 1 n 0 n λ n0

9.8 sum-product 21 λ n0 := log 2 W (y n0 0) W (y n0 1). h m0,n 0 = 1 (m 0, n 0) β m0,n 0 := λ n0 l := 1 3. h m0,n 0 = 1 (m 0, n 0) α m0,n 0 ( α m0,n 0 := n 1 V (m 0 )\{n 0 } ) ( sgn(β m0,n 1 ) GA n 1 V (m 0 )\{n 0 } ) GA( β m0,n 1 ) sgn(a) := 1(a R a 0 ) sgn(a) := 1 ( ) GA(a) GA(a) := log 2 exp 2 (a) + 1 exp 2 (a) 1. 4. h m0,n 0 = 1 (m 0, n 0 ) β m0,n 0 β m0,n 0 := λ n0 + m 1 F (n 0 )\{m 0 } 5. 1 n 0 n γ n0 := λ n0 + α m1,n 0 m 1 F (n 0 ) α m1,n 0. γ n0 0 F 2 ĉ n0 ĉ n0 := 0 ĉ n := 1 6. H(ĉ 1, ĉ 2,, ĉ n0 ) T = 0 c := (ĉ 1, ĉ 2,, ĉ n0 ) 7. 7. l l max? 8. l < l max l 1 3. ( ) 9.53