Chương 5 mã hóa kênh

Chia sẻ: BA AB | Ngày: | Loại File: PDF | Số trang:7

Thêm vào BST

Báo xấu

273
lượt xem 49
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tín hiệu truyền qua kênh truyền sẽ bị ảnh hưởng bởi nhiễu, can nhiễu, fading ... là tín hiệu đầu thu bị sai. Mã hóa kênh dùng để bảo vệ dữ liệu không bị sai bằng cách thêm vào các bit dư thừa. Ý tưởng mã hóa kênh là gởi một chuỗi bit có khả năng sửa lỗi

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Chương 5 mã hóa kênh

3/22/2010 N i dung trình bày: Mã hóa kênh ( Channel coding ) Mã hóa kh i (Block codes) CHƯƠNG 5: MÃ HÓA KÊNH + Mã l p (Repetition Code) + Hamming codes + Cyclic codes ð ng Lê Khoa * Reed-Solomon codes Email: dlkhoa@fetel.hcmuns.edu.vn Mã hóa ch p (Convolutional codes) + Encode + Decode ði u ch mã lư i (Trellis Coded Modulation) Facuty of Electronics & Telecommunications, HCMUS 1 2 Channel coding là gì? Sơ ñ kh i DCS • Tín hi u truy n qua kênh truy n s b nh hư ng b i nhi u, can nhi u, fading… là tín hi u ñ u thu b sai. • Mã hóa kênh: dùng ñ b o v d li u không b sai Source Channel Pulse Bandpass b ng cách thêm vào các bit dư th a (redundancy). Format encode encode modulate modulate • Ý tư ng mã hóa kênh là g i m t chu i bit có kh năng s a l i Digital modulation Channel • Mã hóa kênh không làm gi m l i bit truy n mà ch làm gi m l i bit d li u (b ng tin) Digital demodulation • Có hai lo i mã hóa kênh cơ b n là: Block codes và Convolutional codes Source Demod. Channel Format Detect decode Sample decode 3 4 Mã l p Các lo i mã hóa s a sai Mã l p (Repetition Code) Mã kh i tuy n tính (Linear Block Code), e.g. Hamming Mã vòng (Cyclic Code), e.g. CRC Recovered state BCH và RS Code Mã ch p (Convolutional Code) Truy n th ng, gi i mã Viterbi Mã Turbo Mã LDPC Coded Modulation TCM BICM 5 6 1
3/22/2010 Mã kh i tuy n tính (Linear block codes) Ki m tra ch n l (Parity Check) Chu i bit thông tin ñư c chia thành t ng kh i k bit. Thêm 1 bit ñ xor các bit có k t qu là 0 M i kh i ñư c encode thành t ng kh i l n hơn có D li u truy n, s a l i, không th s a l i n bit. Các bit ñư c mã hóa và g i trên kênh truy n. Quá trình gi i mã ñư c th c hi n phía thu. Channel Data block Codeword encoder k bits n bits n-k Redundant bits Ki m tra hàng và c t k Rc = ng d ng: ASCII, truy n d li u qua c ng n i Code rate n ti p 7 8 Linear block codes – cont’d Linear block codes – cont’d Kho ng cách Hamming gi a hai vector U và V, là Kh năng phát hi n l i ñư c cho b i: s các ph n t khác nhau. e = d min − 1 d (U, V ) = w(U ⊕ V ) Kh năng s a l i t c a mã hóa ñư c ñ nh Kho ng các t i thi u c a mã hóa kh i là nghĩa là s l i t i ña có th s a ñư c trên 1 t d min = min d (U i , U j ) = min w(U i ) mã (codeword) i≠ j i Ví d : Tính kho ng cách Hamming c a C1: 101101  d − 1 và C2 :001100 t =  min  2 Gi i: Vì 101101 ⊕ 001100 = 100001 =>d12=W(1000001)=2 => Ta có th gi i mã ñ s a sai b ng cách ch n codewords có dmin 9 10 Linear block codes – cont’d Linear block codes – cont’d Example: Block code (6,3) Encoding trong b mã hóa kh i (n,k) U = mG Message vector Codeword 000 000000  V1   V1   1 1 0 1 0 0  100 110100 V  G = V 2  = 0 1 1 0 1 0  (u1 , u2 ,… , u n ) = (m1 , m2 ,… , mk ) ⋅  2     01 0 011010 ⋮  V3  1 0 1 0 0 1      110 1 011 1 0 Vk  001 1 01 0 0 1 (u1 , u2 ,… , u n ) = m1 ⋅ V1 + m2 ⋅ V2 + … + m2 ⋅ Vk 1 01 0 111 0 1 Các hàng c a G thì ñ c l p tuy n tính. 011 1 1 0 011 1 11 0 0 0 111 11 12 2
3/22/2010 Linear block codes – cont’d Linear block codes – cont’d Mã hóa kh i (n,k) ð i v i b t kỳ mã hóa kh i tuy n tính, chúng ta có m t ma tr n H ( n − k )× n . Các hàng c a k ph n t ñ u tiên (ho c cu i cùng) trong t mã là các bit thông tin. ma tr n này tr c giao v i ma tr n G : G = [P I k ] GH T = 0 I k = k × k identity matrix H ñư c g i là ma tr n ki m tra parity và các Pk = k × (n − k ) matrix hàng c a chúng ñ c l p tuy n tính. ð i v i mã hóa kh i truy n tính: U = (u1 , u 2 ,..., u n ) = ( p1 , p2 ,..., pn − k , m1 , m2 ,..., mk ) H = [I n − k PT ] parity bits message bits 13 14 Linear block codes – cont’d Linear block codes – cont’d M ng tiêu chu n U m Channel Data source Format Modulation n−k Hàng i = 2,3,...,2 encoding ñư c t o thành b ng cách c ng U channel v i pattern e i Channel Demodulation Data sink Format decoding Detection r ˆ m r = U+e zero ⋯ U1 U2 U 2k codeword r = (r1 , r2 ,...., rn ) received codeword or vector e2 ⊕ U 2 e 2 ⊕ U 2k ⋯ e2 e = (e1 , e2 ,...., en ) error pattern or vector coset ⋮ ⋯ ⋱ ⋮ Ki m tra ñ c trưng: e 2 n −k ⊕ U 2 ⋯ e 2 n −k ⊕ U 2 k S là ñ c trưng c a r, tưng ng v i error pattern e. e 2 n −k S = rHT = eHT coset leaders 15 16 Linear block codes – cont’d Linear block codes – cont’d Ví d : M ng chu n cho mã (6,3) M ng tiêu chu n và ñ c trưng b ng gi i mã codewords 1. Tính S = rH T 2. Tìm coset chính e = ei , tưng ng v i S . ˆ 000000 110100 011010 101110 101001 011101 110011 000111 ˆ = r + e và tưng ng v i m . 000001 110101 011011 101111 101000 011100 110010 000110 ˆ ˆ 3. Tính U 000010 110111 011000 101100 101011 011111 110001 000101 U = r + e = (U + e) + e = U + (e + e) ˆ ˆ ˆ ˆ 000100 110011 011100 101010 101101 011010 110111 000110 Chú ý: ⋮ ⋮ ⋮ 001000 111100 N u e = e , error ñư c s a. ˆ • 010000 100100 coset N u e ≠ e , b gi i mã không th phát hi n l i. ˆ ⋮ 100000 010100 • ⋯ ⋯ 010001 100101 010110 Coset leaders 17 18 3
3/22/2010 Linear block codes – cont’d Hamming codes Hamming codes Là trư ng h p riêng c a linear block codes Error pattern Syndrome Di n t theo hàm c a m t s nguyên m ≥ 2 . U = (101110) transmitted. 000000 000 r = (001110) is received. 000001 101 000010 011 The syndrome of r is computed : 000100 110 n = 2m − 1 Code length : S = rH T = (001110) H T = (100) 001000 001 Number of information bits : k = 2 m − m − 1 010000 010 Error pattern corresponding to this syndrome is n-k = m 100000 100 e = (100000) Number of parity bits : ˆ Error correction capability : t = 1 010001 111 The corrected vector is estimated U = r + e = (001110) + (100000) = (101110) ˆ ˆ 19 20 Mã hóa Hamming Hamming codes Example: Systematic Hamming code (7,4) Mã hóa: H(7,4) 1 0 0 0 1 1 1 Nhi u phép ki m tra t ng H = 0 1 0 1 0 1 1 = [I 3×3 Message=[a b c d] Message=[1 0 1 0] PT ]   r=(1+0+0) mod 2 =1 r= (a+b+d) mod 2 0 0 1 1 1 0 1   s=(1+0+1) mod 2 =0 s= (a+b+c) mod 2 t=(0+1+0) mod 2 =1 t= (b+c+d) mod 2 0 1 1 1 0 0 0  Code=[ 1 0 1 1 0 1 0 ] Code=[r s a t b c d] 1 0 1 0 1 0 0 T c ñ mã: 4/7 G=  = [P I 4×4 ] 1 1 0 0 0 1 0 Càng nh , nhi u redundance bit, ñư c b o v t t hơn.   Khác bi t gi a phát hi n và s a l i 1 1 1 0 0 0 1  21 22 Ví d mã hóa Hamming Hamming codes Example: Systematic Hamming code (7,4) H(7,4) 1 0 0 0 1 1 1 Ma tr n sinh G: ñ u tiên là ma tr n ñơn v 4x4 H = 0 1 0 1 0 1 1 = [I 3×3 D li u truy n là vector p PT ]   Vector truy n x (G=[I/P]) 0 0 1 1 1 0 1    0 1 1 1 0 0 0 1 0 1 0 1 0 0 G=  = [P I 4×4 ] 1 1 0 0 0 1 0   1 1 1 0 0 0 1  Vector nh n r và vector l i e 23 24 4
3/22/2010 S al i ð l i mã hóa (Coding Gain) N u không có l i, vector ñ c trưng (syndrome) z=zeros T c ñ mã R=k/n, k: s symbol d li u, n t ng symbol SNR t và SNR c a bit N u có 1 l i v trí th 2 Vector ñ c trưng z là V i m t sơ ñ mã hóa, ñ l i mã hóa t i m t s c xu t l i bit ñư c ñ nh nghĩa là s khác bi t gi a năng lư ng c n thi t cho 1 bit thông tin ñã mã hóa ñ ñ t ñư c s c xu t l i cho trư c và tương v i c t th 2 c a H. V y, l i ñu c phát hi n v trí truy n d n không mã hóa th 2 và có th s a l i cho ñúng. 25 26 Ví d ñ l i mã hóa Example of the block codes PB 8PSK QPSK Eb / N 0 [dB] 27 28 Cyclic code Cyclic block codes Cyclic codes ñư c quan tâm và quan tr ng vì M t mã tuy n tính (n,k) ñư c g i là Cyclic D a trên c u trúc ñ i s và có th ng d ng r ng code n u khi d ch vòng 1codeword thì ñó cũng rãi. là codeword. D dàng th c hi n b ng thanh ghi d ch (shift register) U = (u0 , u1 , u2 ,..., un −1 ) “i” cyclic shifts of U ðư c ng d ng r ng rãi trong th c nghi m U (i ) = (un −i , un −i +1 ,..., un −1 , u0 , u1 , u2 ,..., un −i −1 ) Trong th c nghi m, cyclic codes ñư c s d ng ñ phát hi n l i (Cyclic redundancy check, CRC) ðư c s d ng trong m ng chuy n m ch gói Ví d : U = (1101) Khi có 1 l i ñư c phát hi n b nh n, chúng s U (1) = (1110) U ( 2) = (0111) U (3) = (1011) U ( 4) = (1101) = U ñư c yêu c u truy n l i. ARQ (Automatic Repeat-reQuest) 29 30 5
3/22/2010 Cyclic block codes Cyclic block codes C u trúc ñ i s c a Cyclic codes, suy ra Thu t toán mã hóa Cyclic code (n,k): n −k codewords ñư c sinh ra t 1. Nhân thông tin v i chu i m( X ) b ng X n −1 U ( X ) = u0 + u1 X + u2 X + ... + un −1 X 2 2. Chia k t qu bư c 1 v i ña th c sinh g ( X ) . degree (n-1) L y p( X ) là ph n dư n− k M i quan h gi a codeword và thanh ghi 3. Thêm p( X ) vào X m( X ) ñ t o thành d ch: XU( X ) = u0 X + u1 X 2 + ..., un− 2 X n−1 + u n−1 X n codeword U ( X ) = un −1 + u0 X + u1 X 2 + ... + un − 2 X n −1 + un −1 X n + u n −1 u n −1 ( X n +1) U (1 ) ( X ) = U (1) ( X ) + un −1 ( X n + 1) U (1) ( X ) = XU( X ) modulo ( X n + 1) V y: By extension U (i ) ( X ) = X i U ( X ) modulo ( X n + 1) 31 32 Cyclic block codes Cyclic block codes Find the generator and parity check matrices, G and H, Example: For the systematic (7,4) Cyclic respectively. code with generator polynomial g( X ) = 1 + X + X 3 g ( X ) = 1 + 1 ⋅ X + 0 ⋅ X 2 + 1 ⋅ X 3 ⇒ ( g 0 , g1 , g 2 , g 3 ) = (1101) m = (1011) 1. Find the codeword for the message 1 1 0 1 0 0 0 n = 7, k = 4, n − k = 3 Not in systematic form. 0 1 1 0 1 0 0 G=  We do the following: m = (1011) ⇒ m ( X ) = 1 + X 2 + X 3 0 0 1 1 0 1 0 row(1) + row(3) → row(3) X n− k m ( X ) = X 3m ( X ) = X 3 (1 + X 2 + X 3 ) = X 3 + X 5 + X 6   0 0 0 1 1 0 1 row(1) + row(2) + row(4) → row(4) Divide X n− k m ( X ) by g ( X) : 1 0 1 0 1 0 0 X 3 + X 5 + X 6 = (1 + X + X 2 + X 3 )(1 + X + X 3 ) + 1 1 0 0 1 0 1 1 0 0 1 1 0 1 0 H = 0 1 0 1 1 1 0 G=  quotient q(X) generator g(X) remainder p ( X )   1 0 1 1 0 0 1 Form the codeword polynomial : 0 0 1 0 1 1 1     U ( X ) = p ( X ) + X 3m ( X ) = 1 + X 3 + X 5 + X 6 1 0 1 0 0 0 1 I 3×3 PT U = (1 0 0 1 0 1 1 ) P I 4×4 parity bits message bits 33 34 Ví d CRC Cyclic block codes Gi i mã Cyclic code: T mã b thu ñư c cho b i r ( X ) = U ( X ) + e( X ) Error Received pattern codewor d ð c trưng ph n dư có ñư c b ng cách chia chu i nh n cho ña th c sinh: r( X ) = q( X )g( X ) + S( X ) Syndrome V i ñ c trưng và m ng tiêu chu n, l i s ñư c ư c lư ng. 35 36 6
3/22/2010 Kh năng c a CRC Checking for errors M t l i E(X) không th phát hi n khi chúng chia h t cho G(x). Ngư c l i, thì có th phát hi n l i. Có kh năng m nh m trong phát hi n l i 37 38 BCH Code BCH Performance Bose, Ray-Chaudhuri, Hocquenghem Có kh năng s a ñư c nhi u l i D dàng th c hi n mã hóa và gi i mã Các chu n trong công nghi p - (511, 493) mã hóa BCH trong ITU-T. Chu n H.261- m t chu n mã hóa video ñư c s d ng cho video conferencing và video phone. (40, 32) mã hóa BCH trong ATM (Asynchronous Transfer Mode) 39 40 Reed-Solomon Codes M t trư ng h p riêng c a non-binary BCH ðư c ng d ng r ng rãi Storage devices (tape, CD, DVD…) W ireless or mobile communication Satellite communication Digital television/Digital Video Broadcast(DVB) High-speed modems (ADSL, xDSL…) 41 7