<4D F736F F D B B83578B6594BB2D834A836F815B82D082C88C60202E646F63>

Size: px

Start display at page:

Download "<4D6963726F736F667420576F7264202D204850835483938376838B8379815B83578B6594BB2D834A836F815B82D082C88C60202E646F63>"

ときのたけ
9 years ago
Views:

2 誤り訂正技術の基礎サンプルページこの本の定価判型などは, 以下の URL からご覧いただけますこのサンプルページの内容は, 第 1 版発行時のものです

3 e mail editor@morikitacojp FAX e mail info@jcopyorjp

4 i CD CD 10 1 CD DVD 1

5 ii DVB-S2 LDPC 2 2 sum-product sum-product sum-product LDPC

6 iii,

7 iv

8 v 6 F q I II BCH sum-product sum-product 132

91 97 92 100 93 103 94 108 95 110 112 10 114 101 114 102

9 vi MAP MAP (FB) FB MAP LDPC I LDPC LDPC LDPC II sum-product sum-product

II 172 141 172 142 sum-product 174 143 sum-product 178 144

10 vii I[condition] [a, b] condition 1 0 a b = := A A A, A A A B A B A B A B A\B A B a A a A B A B A O(g(n)) n f(n) C g(n) C f(n) =O(g(n)) d h (a, b) a, b w h (a) a ln(x) F 2 F q R tanh A t Z (n,w) Prob[event] arg max x D f(x) arg min x D f(x) x A mod B 2 q q A n w 2 event f(x) x D f(x) x D x A B A, B A b A A\{b} A\b 2 2 +, 1+1=2 1+1=0 0

$2 q q A n w 2 event f(x) x D f(x) x D x A B A, B A b A A\{b} A\b 2 2 +, 1+1=2 1+1=0$

12 X 2 X = {0, 1} n X code X n C X C n C codeword n C code length 1 X = {0, 1} X 3 = {000, 001, 010, 011, 100, 101, 110, 111} C = {000, 011, 101, 110} C C = {000, 111} X = {0, 1} 2 q q 2

13 code rate C R R = log 2 C log 2 X n (21) C =2 k k X = {0, 1} 2 log 2 2=1 21 R R = log 2 C log 2 X n = log 2 2k log 2 2 n = k n (22) 2 n R n C minimum distance C C d =min{d h (a, b) :a, b C, a b} (23) 3 C = {000, 011, 101, 110} 2 3 {000, 111} d =3 C X n 1 7 F q k =1 n =3 1/3

14 C = {000, 011, 101, 110} 4 {0, 1, 2, 3} 0 000, 1 011, 2 101, encoder M L M =[1,L] C L bijection φ : M C φ φ m 1 m 2 (m 1,m 2 M) φ(m 1 ) φ(m 2 ) c C φ(m) =c m M φ 3 φ 1 φ 1 m M m = φ 1 (φ(m)) ˆX ˆM 3 φ(m) = 000, m =0 (24) 111, m =1 3 φ M C φ M C f : X Y y Y, x X, f(x) =y a, b X(a b),f(a) f(b) f

15 16 2 m m = M = {0, 1} k {0, 1} n 2 2 n 2 k C φ(m) Y Y n Y Y ˆX ˆX ˆM = φ 1 ( ˆX) 231 Y ˆX M C {c 1, c 2,,c M } 4

16 23 17 R(c i )(i [1,M]) R(c i ) Y n R(c i )(i [1,M]) R(c i ) decoding rule 1 Y R(c i ) i j [1,M] Y / R(c j ) ˆX = c i 2 Y R(c i ) ˆX = 3 Y Y R(c j1 ),Y R(c j2 ),,Y R(c js ) c j1, c j2,,c js 5 R(c i ) c i R(c i ) c i 1 3 D1 R(000) = {000, 001, 010, 100}, R(111) = {111, 110, 101, 011} ψ : Y n C { } ψ Y ˆX = ψ(y ) 22 5

17 ψ(y ) ˆX = X 2 ˆX X 3 ˆX = c i Y R(c i ) R(c j ) P c P e P d P c + P e + P d = n C 2 n 1 > 2 >

18 23 19 minimum distance decoding rule C = {c 1, c 2,,c M } c i C c i R(c i ) R(c i ) = {y {0, 1} n : c C\{c i } d h (y, c i ) d h (y, c)} (25) i [1,M] C\{c i } C {c i } 23(a) ˆX Y ˆX =argmin d h(y,x) (26) X C arg min X C Y 23

$d h (y, c i ) d h (y, c)} (25) i [1,M] C\{c i } C {c i$

19 r r 2 4 bounded distance decoding rule C = {c 1, c 2,,c M } R(c i ) = {y {0, 1} n : d h (c i, y) r}, i [1,M] (27) r d 1 r 2 d C x x 23(b) r (d 1)/2 d 1 2r 2 2 d 1 = d 1 (28) 2 2 d r( (d 1)/2 ) 235

20 24 21 n = C 7 R = 800/1000 = 4/ n R 2 O(n2 n ) 8 n n O(n) O(n 2 ) HDD CD DVD LDPC f(n) C g(n) f(n) C g(n) n f(n) =O(g(n)) [10]

) 24 21 21 HDD CD DVD LDPC 241 7 1 8 f(n)

21 22 2 HDD CD DVD LDPC 13 LDPC sum-product CD DVD product code

22 C = {0000, 1010, 0101, 1111} 1 C 2 C 22 2 C = {00000, 11100, 00111, 11011} C C = {00000, 11111} C r =1 1 C 2 p 2 P c P d P e 3 P c + P d + P e = (a, b)(a, b {0, 1}) (a, b) (ā, b) ā, b a, b C = {00, 01} (a, b) =(0, 0) (a, b) =(0, 1)

24 71 7 I F q Reed-Solomon code MDS CD DVD F q q n = q 1 ( ) α 0 α 1 α 2 α q 2 H = (α 0 ) 2 (α 1 ) 2 (α 2 ) 2 (α q 2 ) 2 ( ) 1 α α 2 α n 1 = 1 α 2 α 4 α 2(n 1) (71) F q C = {x F n q : Hx t = 0} (72) α F q C n = q 1

25 72 7 I k = n 2 d =3 F 2 8 n = 255,k = 253,d=3 C 1 C 2 α i α j = αi α 2j α j α 2i α 2i α 2j = α i+2j α j+2i = α i+j (α j α i ) (73) i, j [0,q 2] (i j) α i+j 0 α j α i 0 0 (α i,α 2i ) t (α j,α 2j ) t H C C 3 1 C X F n q Y = X + E E n F q i i [1,n] (error magnitude) e F q Y S = HY t X HX t =0 S = HY t = H(X + E) t = HE t HE t S = s 1 = eαi 1 (74) s 2 eα 2(i 1) s 2 /s 1 s 2 = eα2(i 1) s 1 eα i 1 = α i 1 (75) i

26 72 73 s 2 1/s 2 s 2 1 = e2 α 2(i 1) = e (76) s 2 eα 2(i 1) i e E Ê ˆX = Y Ê ˆX C determinant F q n n A = {a ij } (i [1,n],j [1,n]) A = { n i=1 ( 1)i+j a ij A ij, n > 1 a 11, n =1 (77) j [1,n] A ij A i j (n 1) (n 1) 1 F q 2 2 A = a b c d A A = ad bc 1

27 74 7 I 1 F q n n a 1 a 2 a n a i i a 1 a 2 aa i a n = a a 1 a 2 a i a n i [1,n] a F q 2 F q n n a 1 a 2 a n 3 a 1 a 2 a i + a j a n = a 1 a 2 a i a n + a 1 a 2 a j a n F q n n A t = A 4 F q n n AB = A B 5 F q n n a 1 a 2 a n a 1 a 2 a n 0 a 1 a 2 a n 6 b 1,b 2,,b n F q B 0 B = n i=1 b i x 1 x 2 x 3 x n X = x 2 1 x 2 2 x 2 3 x 2 n (78) x n 1 1 x n 1 2 x n 1 3 xn n 1 Vandermonde X x 1 x 2 x 3 x n x 2 1 x 2 2 x 2 3 x 2 n = i x j ) (79) i>j(x x n 1 1 x n 1 2 x n 1 3 x n 1 n

28 i>j i, j [1,n] i, j x i x j X X 73 Reed-Solomon code F q 1 α α 2 α n 1 1 α 2 α 4 α 2(n 1) H = 1 α 3 α 6 α 3(n 1) 1 α 2t α 4t α 2t(n 1) (710) F q C = {c F n q : Hc t = 0} (711) n = q 1 t [1, (q 2)/2 ] (712) H 2t H sub α j 1 α j 2 α j 2t α 2j 1 α 2j 2 α 2j 2t H sub = (713) α 2tj 1 α 2tj 2 α 2tj 2t j i [0,n 1] (i [1, 2t]) j k j l (k, l [1, 2t],k l) H sub 2

29 76 7 I α j 1 α j 2 α j 2t α 2j 1 α 2j 2 α 2j 2t H sub = α 2tj 1 α 2tj 2 α 2tj 2t = α j1 α j α j 1 α j 2 α j 2t 2t α (2t 1)j 1 α (2t 1)j 2 α (2t 1)j 2t (714) 1 H sub 0 H sub 5 H 2t C k k = n 2t H 2t C d d 2t +1 d n k +1=n n +2t +1=2t +1 d =2t +1 F q H F q n = q 1 k = n 2t d = n k +1=2t n O(n 3 ) t 3 WWPeterson 1960 Error-Correcting Codes

30 n = q 1 C X =(X 0,,X n 1 ) C 0 Y =(Y 0,,Y n 1 ) F n q Y = X+E E =(E 0,,E n 1 ) F n q w h (E) =ν 1 ν t Y S =(S 1,S 2,,S 2t ) S = HY t 2 S = HY t = H(X + E) t = HE t i [1, 2t] ( ) S i = 1 α i α 2i α (n 1)i E 0 E 1 (715) E n 1 S E HQ T = S (716) Q F n q 5 E t Berlekamp-Massey-Sakata Euclid Sugiyama-Kasahara-Hirasawa-Namekawa Welch-Berlekamp Feng-Rao Sudan Euclid O(n 2 ) t 5

31 78 7 I E t t S E t 716 E E E E E = {i [0,n 1] : Ei 0} (717) E E = ν t ν E E E E = {j 1,j 2,,j ν } x k = α j k (k [1,ν]) e k = Ejk (k [1,ν]) j / E E E j =0 715 ν S i = e k x i k, i [1, 2t] (718) k=1 S 1 x 1 x 2 x 3 x ν 1 x ν S 2 x 2 1 x 2 2 x 2 3 x 2 ν 1 x 2 ν = S 2t x 2t 1 x 2t 2 x 2t 3 x 2t ν 1 x 2t ν e 2 e 1 e ν (719) x k (k [1,ν]) e k (k [1,ν]) 742 σ(z) E ν {x 1 1,x 1 2,,x 1 ν } ν σ 1,,σ ν ν σ(z) =1+ σ k z k (720) k=1 σ(z) x 1 j ν σ(x 1 j )=1+ k=1 (j [1,ν]) σ k x k j = 0 (721)

32 74 79 ν j=1 e jx i+ν j σ(x 1 j )(i [1,ν]) ( ) ν ν ν e j x i+ν j σ(x 1 j )= e j x i+ν j 1+ σ k x k j (722) j=1 = j=1 ν j=1 = S ν+i + e j x i+ν j + ν k=1 ν σ k k=1 j=1 e j x ν+i k j (723) ν σ k S ν+i k (724) k=1 = 0 (725) σ(x 1 j )= 0(j [1,ν]) ν S ν+i = σ k S ν+i k, i [1,ν] (726) k=1 S 1 S 2 S 3 S ν 1 S ν S 2 S 3 S 4 S ν S ν+1 S 3 S 4 S 5 S ν+1 S ν+2 S 4 S 5 S 6 S ν+2 S ν+3 S ν 1 S ν S ν+1 S 2ν 3 S 2ν 2 σ ν σ ν 1 σ ν 2 σ ν 3 σ 2 = S ν+1 S ν+2 S ν+3 S ν+4 S 2ν 1 S ν S ν+1 S ν+2 S 2ν 2 S 2ν 1 σ 1 S 2ν (727) Berlekamp-Massey Sugiyama ν ν ν Y S i (i [1, 2t]) ν t 727 S 1,S 2,,S 2ν (σ 1,σ 2,,σ ν )

33 80 7 I σ 1,σ 2,,σ ν σ(z) σ(z) 0 F q Chien search 721 x 1,x 2,,x ν 743 x 1,x 2,,x ν e 1,e 2,,e ν 718 S 1 x 1 x 2 x 3 x ν 1 x ν e 1 S 2 x 2 1 x 2 2 x 2 3 x 2 ν 1 x 2 ν e 2 = (728) S ν x ν 1 x ν 2 x ν 3 x ν ν 1 x ν ν e ν x 1 x 2 x ν x 2 1 x 2 2 x 2 ν x 1 x 2 x ν = x 1 x 2 x ν x ν 1 x ν 2 x ν ν x ν 1 1 x ν 1 2 x ν 1 ν 0 (729) e 1,e 2,,e ν 744 ν ν ν 1 τ t

34 74 81 D τ = S 1 S 2 S τ S 2 S 3 S τ+1 S τ S τ+1 S 2τ 1 (730) τ = ν D τ 0 τ >ν D τ =0 k [ν +1,t] e k =0,x k = e 1 x T = x 1 x 2 x τ, Q 0 e 2 x 2 0 = x τ 1 1 x τ 1 2 x τ 1 τ 0 0 e τ x τ D τ D τ = TQT t = T Q T t (731) 75 τ>ν Q 0 Q = D τ =0 τ = ν Q 6 x 1,x 2,,x τ F q T 0 D τ 0 ν τ = t τ D τ D τ 0 τ = ν 745 Peterson algorithm Y ˆX Y S 1,S 2,,S 2t τ := t

35 82 7 I 2 D τ 730 D τ = 0 τ := τ 1 3 ν := τ 727 σ 1,σ 2,,σ ν 4 σ(z) x 1,x 2,,x ν Ê =(e 1,e 2,,e ν ) 6 Ê Y ˆX = Y Ê ν t t 746 F α α 2 α 3 α 4 α 5 α 6 H = 1 α 2 α 4 α 6 α 8 α 10 α 12 1 α 3 α 6 α 9 α 12 α 15 α 18 1 α 4 α 8 α 12 α 16 α 20 α 24 C α 7 =1 1 α α 2 α 3 α 4 α 5 α 6 1 α 2 α 4 α 6 α 1 α 3 α 5 H = 1 α 3 α 6 α 2 α 5 α α 4 1 α 4 α α 5 α 2 α 6 α 3 (732) (733) C 2 E =(0, 0, 0,α 5, 0,α 2, 0) X C Y = X + E HY t = H(X + Y ) t = HE t

36 83 S 1 S 2 S 3 S 4 = α 5 α 3 α 6 α 2 α 5 + α 2 α 5 α 3 α α 6 = α 3 1 α 1 (734) S 1 S 2 S 2 S 3 = S 1S 3 S 2 S 2 = α (735) ν =2 727 S 1 S 2 σ 2 = S 3 (736) S 2 S 3 σ 1 S 4 α3 1 σ 2 = α (737) 1 α σ 1 1 σ 1 = α 2,σ 2 = α σ(z) = 1+σ 1 z + σ 2 z 2 =1+α 2 z + αz 2 σ(z) F 2 3 σ(z) σ(α 4 )=0 σ(α 2 )=0 α 4 = α 3 α 2 = α 5 6 x 1 = α 3,x 2 = α α3 α 5 e 1 = α3 (738) α 6 α 3 e 2 1 e 1 = α 5,e 2 = α 2 71 F 2 3 F 2 z 3 + z +1 α 53 ( ) 1 α α 2 α 3 α 4 α 5 α 6 H = 1 α 2 α 4 α 6 α 8 α 10 α 12 6 x F q x y =1 y x y x 1 α 3 α 4 =1 α 3 = α 4 5

37 84 7 I E =(0,α 2, 0, 0, 0, 0, 0) 1 Y = X + E 2 Ê 72 F ta b 73 tc d, a + x b c + y d, a c b d a b c d F 2 3 F 2 z 3 + z +1 α α α 2 α 4 α 2 α 4 α 75 ν =2,τ =2 D τ = TQT t = T Q T t E =(0,α 2,α,0, 0, 0, 0)

38 LDPC I low-density parity check LDPC LDPC sum-product LDPC LDPC LDPC LDPC LDPC F q F 2 2 LDPC LDPC 2 2 m n H (0 <m<n) 2 C C = {x F n 2 : Hxt = 0} H 1 C LDPC 1 Robert G Gallager LDPC 60 Information Theory and Reliable Communication 2 LSI LDPC LDPC 90 DMacKay LDPC LDPC

39 LDPC I C n m C R R 1 m/n LDPC m = 5000,n = H 1 w r =6 1 w c =3 C LDPC LDPC {H 1,H 2,,H n,} H n (n =1, 2,) n αn α 0 α 1 n H n 05n n n 3 H n 1 3n 1 n 1 n n 2 LDPC LDPC sum-product

40 131 LDPC 161 LDPC sum-product sum-product 3 sum-product 1 4 LDPC O(n) 1 O(n) LDPC Tanner graph 2 m n H i j h ij 2 5 G(H) =(V,E) V = V 1 V 2 V 1 = {v1,v 2,,v n }, V 2 = {c1,c 2,,c m } (131) V 1 V 2 h ij =1(i [1,m],j [1,n]) (i, j) v i c j e ij E h ij =0(i [1,m],j [1,n]) v i c j 2 G(H) H i c i j v j h ij =1 c i v j H LDPC 4 n 5 2 V V 1,V 2 V 1 V 2

41 LDPC I 132 v 1,,v c 1 v 1,v 2,v 3 v 1 + v 2 + v 3 =0 LDPC 2 n O(n) LDPC sum-product 132 v 2,v 3 c 1,c LDPC LDPC LDPC LDPC LDPC LDPC LDPC w c w r LDPC LDPC LDPC LDPC w c,w r LDPC LDPC LDPC LDPC LDPC

42 131 LDPC 163 w c w r LDPC 94 LDPC k 6 L k = {i [1,n]:deg(v i)=k} n (132) deg(v) v k % LDPC sum-product sum-product LDPC 2 w c =2 w r =4 H

43 LDPC I H 1 = (133) H 1 8 H 2 = (134) H 1 H H = (135) , 4 w r 1 0 n h 1 H 1 h 1 s(h 1 ) H 1 = s 2 (h 1 ) s n/wr 1 (h 1 ) (136) s( ) w r 4,2 H 2,,H wc H 1 H 2 H = (137) H wc w c,w r H LDPC LDPC 6 H G G 8 8! 9

44 132 LDPC LDPC LDPC 2 sum-product sum-product 2 2 sumproduct 2 sum-product sum-product {0, 1} 3 {0, 1,e} e 0, 1 1 p p p 2 2 m n H LDPC H G O(n 2 )

45 LDPC I C C x 2 y =(y 1,y 2,,y n ) {0, 1,e} n c A(c) v B(v) sum-product sum-product 1 v N(v) =y i c c e 2 v c B(v) M v c M v c B(v)\c e v N(v) e M v c = e M v c B(v)\c e 3 c v A(c) M c v M c v A(c)\v e M c v = e M c v F M c v = v A(c)\v M v c 134 sum-product 3

46 132 LDPC v e b {0, 1} N(v) =e N(v) =b a LDPC 0, 0, 0, 0, 0, 0, 0, 0 Y =(e, e, e, e, 0, 0, 0, 0) v 1,v 2,,v 8 c 1,,c 4 a N(v) b c 4 c 4 v 6,v 8 (M v6 c 4 = M v8 c 4 =0) v 3 M c4 v 3 = M v6 c 4 + M v8 c 4 =0 0 v 3 N(v 3 )=0 3 c d 3 0 LDPC sum-product

47 LDPC I LDPC 9 sum-product density evolution sum-product sum-product d k 11 p i i e q i 11 d k 15

48 132 LDPC 169 i e sum-product p 2 i +1 e e d 1 e 12 p i+1 = pq d 1 i (138) i e q i k 1 e 13 q i =1 (1 p i ) k 1 (139) p i p i+1 = p(1 (1 p i ) k 1 ) d 1 (1310) p 0 = p 2 sum-product p i+1 = g(p i ) p 0 = p g(x) =p(1 (1 x) k 1 ) d 1 d =3,k =6 p i 136 x y y = x y = g(x) p =04 p i p 1 = g(p 0 ) (p 0,p 1 ) x =04 y = g(x) y = x x = p 1 12 sum-product p sum-product p166

49 LDPC I 136 p i p =04 y = g(x) (p 1,p 2 ) y = g(x) (p i,p i+1 ) 136 p i p i 0 14 p =04 sum-product 0 p =0451 y = x y = g(x) 137 p i p i p = p i 0 0

50 171 p d =3,k = LDPC [5] e, e, 0, 0, 0 sum-product 132 m n H H h 1,,h n T = {t 1,t 2,,t s } [1,n] T H(T ) =(h t1 h t2 h ts ) H(T ) 1 T sum-product H G G girth LDPC LDPC sum-product LDPC

52 , 26, 27, 31, 38, , 4,31, 105, 146, 183, 193, , 161 ACS 119, 121 AWGN 106, 120, 183 BCH 94 BCH 42, 92, 93, 187 BCJR 116, 147, 156 LDPC 22, 49, 133, 159, 162 MAP 101, 145, 176 min-sum 183 SN 107 sum-product 132, 135, 138, 160, 174 sum-product 22, 166, 175 u u + v 43 41, 78, 80 78, 82 17, 18, 31, 38, , 78, 80, , 14, 15, 19 11, 13, , 46, , 39, , , 137, , 80, , , , 43, , 157, , , , 99, 131, 140, , , , , , , 26, 27, , , , , 7,17 130, , 21, 28, 103, 122, , 45 29, 30, 40, 67, 68, , , 41 7, 18, , 85 14, 30, 38, 39, 45, 49, 72, 94, 192

53 222 19, 48, 105, , 48, , , 71, 76 49, 102, 103, 105, 110, , 39 26, 38, , 101, 144, 151, , 102, , 10, , 99, 129, , 135, 138, 149, , 156, 173, 182 3, 31 85, 86, 94 29, 42, 76, 86, 95, , , 165, , , 33, 41, 72, 77, 177, , 36, 41 MAP 145, , 43, 62, 68 85, 86, 94 LDPC 162 7, 18 22, , , 29, 31, 61 51, , 87, , , 71, 76, 77, , , 19, , 124, , , , 122, 152, 186, , , , , 27, , , , , , , 115, 126, 152, , , 6 20, 46 5, 20 5, 47 39, 40, , 49, 156, 177 LDPC 162

54 223 76, 81 22, 117, , 132, 135, 147, 161, 172, , 4, 16, 97 3, 16, 101, , 7, 17 6, 7, 17, 19, 49, 111 3, 13 3, 15, 16, 28, 68, 86, 87, 164 3, 15, 87, 156 6, 15, 16, , 27, 63 10, 12, 196, , 14, 62, , 4, 13, 24, 30, 45 85, 93 4, 13, , 28, MAP 101 2, 4, 7, 14, 18, 101, 108, 111, , , , , , 101, , , 136, 141, 175, , , , , , 105 1, 3, 15, 139, , 24, , 102, , , 22, 71, 75, 85, , 44, , 142, 161, 162,

55 c FAX http: wwwmorikitacojp Printed in Japan ISBN

one way two way (talk back) (... ) C.E.Shannon 1948 A Mathematical theory of communication. 1 ( ) 0 ( ) 1

1 1.1 1.2 one way two way (talk back) (... ) 1.3 0 C.E.Shannon 1948 A Mathematical theory of communication. 1 ( ) 0 ( ) 1 ( (coding theory)) 2 2.1 (convolution code) (block code), 3 3.1 Q q Q n Q n 1 Q