08_toukei03.dvi

Size: px

Start display at page:

Download "08_toukei03.dvi"

奎牵滕
5 years ago
Views:

1 c LDPC Low-Density Parity-Check LDPC MIMO Feldman LP Feldman, 2003; Feldman et al., 2005 Feldman Vontobel and Koetter 2006 Koetter and Vontobel 2003 Burshtein 2008 LDPC Low-Density Parity-Check; Gallager, 1963 Wadayama, 2010 LP Wadayama, CDMA, LDPC Wadayama

2 Wadayama 2010 LDPC equalization MIMO 2 LDPC Vontobel 2008 Taghavi et al MIMO LDPC LDPC 1960 R. Gallager sum-product loopy belief propagation LDPC LDPC 2 LDPC 2 LDPC sum-product LDPC sum-product LDPC 2 F 2 H = {h i,j}(i [1,m],j [1,n]) 2 C(H) (2.1) C(H) = {x F n 2 : Hx =0 m } Hx 2 F 2 2 F 2 {0,1} 1+1=0 [a,b] {a,a +1,...,b 1,b} 0 m n H C(H) LDPC

3 X Y S P Y X (y x) S n X =(X 1,X 2,...,X n) T Y =(Y 1,Y 2,...,Y n) T S n S n (2.2) P Y X (y x)= P Yi X i (y i x i) i=1 i [1,n] P Yi X i (y i x i) 2 C(H) y ˆx Pr[x ˆx] (2.3) ˆx = arg max P Y X (y x) x C(H) C(H) n 2.3 H C(H) x C(H) AWGN (0,1) (+1, 1) r (2.4) r =(1 2x)+z z 1 1 (2.5) ˆx = arg min r (1 2x ) 2 x C(H) ˆx 2 n

4 Schrijver 2003 (2.6) ˆx = arg min r (1 2x ) 2 x Conv(C(H)) Conv(C(H)) F 2 (0,1) (0,1) 2 2 Boyd and Vandenberghe, C(H) n Feldman LDPC Feldman, 2003; Feldman et al., C(H) C(H) LDPC n A i = {j [1,n]:hi,j =1} i [1,m] T i(i [1,m]) A i (2.7) T i = {S Ai : S is odd} x R n (2.8) i [1,m], S T i, 1+ t S (x t 1) (2.9) j [1,n], 0 x j 1 t A i \S x t 0, H A i S T i x =(x 1,...,x n) T { 1, i S x i = 0, i/ S x 2 F 2 Hx 0 m S x n h i,jx j = x j = x j + x k =1 j=1 j A i j S k A i \S 2 x 1+ (x t 1) x t =1 t S t A i \S

5 127 x 2 2 P(H) (2.10) P(H) = {x R n : x satisfies constraints (2.8) and (2.9)} Koetter and Vontobel, 2003; Feldman et al., 2005 P(H) P (H) LDPC 2.5 LP Feldman LP Feldman LP 2 BIOS P Yi X i (y i x i)(i [1,n]) AWGN BIOS Y i X i i i λ =(λ 1,λ 2,...,λ n) T (2.11) λ i =ln P Yi X i (y i 0) P Yi X i (y i 1), i [1,n] Feldman LP Feldman et al., 2005 n ˆx = arg min λ ix i x P(H) i=1 ˆx LP LDPC LP C(H) x (2.12) r = V x + b + z, V n n b n V b z R n V b MIMO

6 (2.13) ˆx = arg min f(v x + b,r) x P(H) f(, ) d(, ) 2 2 (2.14) ˆx = arg min r (V x + b) 2 x P(H) LDPC 2 LDPC B(x) = [ ( ln 1+ (x t 1) ) ] x t i [1,m] S T i t S t A i \S ln [ ( x j)] ln[ (x j 1)] j [1,n] j [1,n] x + f(v x + b,r) (3.1) ψ (t) (x)=tf(v x + b,r)+b(x) t ψ (t) (x) 1 t x =(1/2,1/2,...,1/2) T 2 ψ (t) (x) 3 min-sum

7 129 4 t := αt α t t Wadayama 2010 ( ) T (3.2) ψ (t) (x) = ψ (t) (x), ψ (t) (x),..., ψ (t) (x) x 1 x 2 x n k ψ (t) (x) =t f(x)+ B(x) x k x k x k = t f(x)+ x k τ (i,s) i [1,m] S T i k (x) 1 1 x k x k 1 (3.3) τ (i,s) k (x) = I[k A i\s] I[k S] 1+ l S (x l 1) l A i \S x, l (i [1,m],S [1,n]) I[condition] condition I[condition]=1 condition I[condition]=0 2 wr 1 m ψ (t) (x) w r g =(g 1,...,g n) T (3.4) g k = t x k f(x)+ i [1,m] τ (i,s(i) ) k (x) 1 x k 1 x k 1, S (i) [ (3.5) S (i) = arg max 1+ (x l 1) S T i l S l A i \S k [1,n], x P (H) x l ], i [1,m] T i Wadayama 2010 S (i) S (i) w r

8 O(w rm) LDPC Wadayama min-sum f(x) ˆx 3 LDPC min-sum min-sum sum-product LDPC ( ) (3.6) α ci x j = sign(β xk c i ) min β xk c i k A i \j k A i \j c i i x k k α ci x j c i x j β xk c i x k c i 1 min-sum B i B i = {j [1,m]:hi,j =1}, i [1,n] 2010 min-sum tanh min-sum sum-product min-sum min-sum min-sum

9 Gd = g G d d Wadayama 2010 Wadayama 2009 LDPC G LDPC Wadayama, Wadayama 2010 BP LDPC BP LP 1 2 Draper et al LDPC LP 1 BP LP LP 2 2 LP 2 LDPC Tanatmis et al., 2009

10 Miwa et al., 2009 LP C No Boyd, S. and Vandenberghe, L Convex Optimization, Cambridge University Press, New York. Burshtein, D Iterative approximate linear programming decoding of LDPC codes with linear complexity, Proceedings of IEEE International Symposium on Information Theory, Toronto. Draper, S. C., Yedidia, J. S. and Wang, Y ML decoding via mixed-integer adaptive linear programming, Proceedings of IEEE International Symposium on Information Theory, Nice. Feldman, J Decoding error-correcting codes via linear programming, Ph.D. Thesis, Massachusetts Institute of Technology, Feldman, J., Wainwright, M. J. and Karger, D. R Using linear programming to decode binary linear codes, IEEE Transactions on Information Theory, 51(3), Gallager, R. G Low Density Parity Check Codes, MIT Press, Cambridge, Massachusetts CDMA A J94-A(8), Koetter, R. and Vontobel, P. O Graph covers and iterative decoding of finite-length codes, Proceedings of 3rd International Symposium on Turbo Codes and Related Topics, Brest. Miwa,M.,Wadayama,T.andTakumi,I A cutting-plane method based on redundant rows for improving fractional distance, IEEE Journal on Selected Areas in Communications, 27(6) Schrijver, A Combinatorial Optimization: Polyhedra and Efficiency, Springer, Berlin. Taghavi, M. H., Shokrollahi, A. and Siegel, P. H Efficient implementation of linear programming decoding, Forty-Sixth Annual Allerton Conference, Allerton Park & Retreat Center, University of Illinois Monticello, Illinois. Tanatmis, A., Ruzika, S., Hamacher, H., Punekar, M., Kienle, F. and Wehn, N Valid inequalities for binary linear codes, Proceedings of IEEE International Symposium on Information Theory, Seoul. Vontobel, P. O Interior-point algorithms for linear-programming decoding, Proceedings of Information Theory and Its Applications Workshop, UC San Diego, La Jolla. Vontobel P. O. and Koetter R Towards low-complexity linear-programming decoding, Pro-

11 133 ceedings of 4th International Conference on Turbo Codes and Related Topics, Munich. Wadayama, T An LP decoding algorithm based on primal path-following interior point method, Proceedings of IEEE International Symposium on Information Theory, Seoul. Wadayama, T Interior point decoding for linear vector channels based on convex optimization, IEEE Transactions on Information Theory, 56(10),

12 134 Proceedings of the Institute of Statistical Mathematics Vol. 61, No. 1, (2013) A Review of Decoding Algorithm for LDPC Codes Based on Numerical Optimization Techniques Tadashi Wadayama Nagoya Institute of Technology This paper reviews a decoding algorithm for low-density parity-check (LDPC) codes based on convex optimization according to the reference Wadayama (2010). The decoding algorithm, called interior point decoding, is designed for linear vector channels. The linear vector channels include many practically important channels such as inter-symbol interference channels and partial response channels. It is shown that the maximum likelihood decoding (MLD) rule for a linear vector channel can be relaxed to a convex optimization problem called a relaxed MLD problem. The decoding algorithm is based on the primal path-following interior point method with a barrier function. Approximate variations of the gradient descent and the Newton methods are used to solve the convex optimization problem. Key words: Interior point method, convex optimization, low-density parity-check codes.

y 1 = 槡 P 1 1h T 1 1f 1 s 1 + 槡 P 1 2g T 1 2 interference 2f 2 s y 2 = 槡 P 2 2h T 2 2f 2 s 2 + 槡 P 2 1g T 2 1 interference 1f 1 s + n n

y 1 = 槡 P 1 1h T 1 1f 1 s 1 + 槡 P 1 2g T 1 2 interference 2f 2 s y 2 = 槡 P 2 2h T 2 2f 2 s 2 + 槡 P 2 1g T 2 1 interference 1f 1 s + n n 37 1 Vol 37 No 1 2013 1 Journal of Jiangxi Normal UniversityNatural Science Jan 2013 1000-5862201301-0037-05 MISO 郭荣新, 袁继昌 361021 2 RVQ 2 MISO 3 TN 911 7 A 0 MIMO 2 MISO 3 MIMOnetwork MIMO 3GPP LTE-A 2