Bài giảng Chương 5: Mã hóa kênh (tiếp)

3/22/2010 1 CHƯƠNG 5: MÃ HÓA KÊNH ðặng Lê Khoa Email: dlkhoa@fetel.hcmuns.edu.vn Facuty of Electronics & Telecommunications, HCMUS 1 Nội dung trình bày:
Mã hóa kênh ( Channel coding )
Mã hóa khối (Block codes) + Mã lập (Repetition Code) + Hamming codes + Cyclic codes * Reed-Solomon codes
Mã hóa chập (Convolutional codes) + Encode + Decode
ðiều chế mã lưới (Trellis Coded Modulation) 2 Sơ ñồ khối DCS Format Source encode Format Source decode Channel encode Pulse modulate Bandpass modulate Channel decode Demod. SampleDetect C ha n nel Digital modulation Digital demodulation 3 Channel coding là gì? • 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 (redundancy). • Ý tưởng mã hóa kênh là gởi một chuỗi bit có khả năng sửa lỗi • 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) • Có hai loại mã hóa kênh cơ bản là: Block codes và Convolutional codes 4 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
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 Mã lập Recovered state 6 3/22/2010 2 Kiểm tra chẵn lẻ (Parity Check)
Thêm 1 bit ñể xor các bit có kết quả là 0
Dữ liệu truyền, sửa lỗi, không thể sửa lỗi
Kiểm tra hàng và cột
Ứng dụng: ASCII, truyền dữ liệu qua cổng nối tiếp 7 Mã khối tuyến tính (Linear block codes)
Chuỗi bit thông tin ñược chia thành từng khối k bit.
Mỗi khối ñược encode thành từng khối lớn hơn có 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. Data block Channel encoder Codeword k bits n bits rate Code bits Redundant n kR n-k c = 8 Linear block codes – cont’d
Khoảng cách Hamming giữa hai vector U và V, là số các phần tử khác nhau.
Khoảng các tối thiểu của mã hóa khối là
Ví dụ: Tính khoảng cách Hamming của C1: 101101 và C2 :001100 Giải: Vì =>d12=W(1000001)=2
=> Ta có thể giải mã ñể sửa sai bằng cách chọn codewords có dmin )()( VUVU, ⊕= wd )(min),(minmin iijiji wdd UUU == ≠ 100001001100101101 =⊕ 9 Linear block codes – cont’d
Khả năng phát hiện lỗi ñược cho bởi:
Khả năng sửa lỗi t của mã hóa ñược ñịnh nghĩa là số lỗi tối ña có thể sửa ñược trên 1 từ mã (codeword)     − = 2 1mindt 1min −= de 10 Linear block codes – cont’d
Encoding trong bộ mã hóa khối (n,k)
Các hàng của G thì ñộc lập tuyến tính. mGU = kn k kn mmmuuu mmmuuu VVV V V V ⋅++⋅+⋅=             ⋅= 2221121 2 1 2121 ),,,( ),,,(),,,( ⋮ 11 Linear block codes – cont’d
Example: Block code (6,3)           =           = 1 0 0 0 1 0 0 0 1 1 1 0 0 1 1 1 0 1 3 2 1 V V V G 1 1 1 1 1 0 0 0 0 1 0 1 1 1 1 1 1 0 1 1 0 0 0 1 1 0 1 1 1 1 1 0 0 0 1 1 1 1 0 0 0 1 1 0 1 0 0 0 1 0 0 0 1 0 1 0 0 1 1 0 0 1 0 0 0 0 1 0 0 0 1 0 Message vector Codeword 12 3/22/2010 3 Linear block codes – cont’d
Mã hóa khối (n,k)
k phần tử ñầu tiên (hoặc cuối cùng) trong từ mã là các bit thông tin. matrix )( matrixidentity ][ knk kk k k k −×= ×= = P I IPG ),...,,,,...,,(),...,,( bits message 21 bitsparity 2121  kknn mmmpppuuu − ==U 13 Linear block codes – cont’d
ðối với bất kỳ mã hóa khối tuyến tính, chúng ta có một ma trận . Các hàng của ma trận này trực giao với ma trận :
H ñược gọi là ma trận kiểm tra parity và các 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: nkn ×− )(H G 0GH =T ][ Tkn PIH −= 14 Linear block codes – cont’d
Kiểm tra ñặc trưng:
S là ñặc trưng của r, tưng ứng với error pattern e. Format Channel encoding Modulation Channel decodingFormat Demodulation Detection Data source Data sink U r m mˆ channel or vectorpattern error ),....,,( or vector codeword received ),....,,( 21 21 n n eee rrr = = e r eUr += TT eHrHS == 15 Linear block codes – cont’d
Mảng tiêu chuẩn
Hàng ñược tạo thành bằng cách cộng U với pattern kknknkn k k 22222 22222 221 UeUee UeUee UUU ⊕⊕ ⊕⊕ −−− ⋯ ⋮⋱⋯⋮ ⋯ ⋯ zero codeword coset coset leaders kni −= 2,...,3,2 ie 16 Linear block codes – cont’d
Mảng tiêu chuẩn và ñặc trưng bảng giải mã 1. Tính 2. Tìm coset chính , tưng ứng với . 3. Tính và tưng ứng với .
Chú ý: • Nếu , error ñược sửa. • Nếu , bộ giải mã không thể phát hiện lỗi. TrHS = iee =ˆ S erU ˆˆ += mˆ )ˆˆ(ˆˆ e(eUee)UerU ++=++=+= ee =ˆ ee ≠ˆ 17 Linear block codes – cont’d
Ví dụ: Mảng chuẩn cho mã (6,3) 010110100101010001 010100100000 100100010000 111100001000 000110110111011010101101101010011100110011000100 000101110001011111101011101100011000110111000010 000110110010011100101000101111011011110101000001 000111110011011101101001101110011010110100000000 ⋯⋯ ⋮ ⋮⋮⋮ Coset leaders coset codewords 18 3/22/2010 4 Linear block codes – cont’d 111010001 100100000 010010000 001001000 110000100 011000010 101000001 000000000 (101110)(100000)(001110)ˆˆ estimated is vector corrected The (100000)ˆ is syndrome this toingcorrespondpattern Error (100)(001110) :computed is of syndrome The received. is (001110) ted. transmit(101110) =+=+= = === = = erU e HrHS r r U TT Error pattern Syndrome 19
Hamming codes
Là trường hợp riêng của linear block codes
Diễn tả theo hàm của một số nguyên . Hamming codes 2≥m t mn-k mk n m m 1 :capability correctionError :bitsparity ofNumber 12 :bitsn informatio ofNumber 12 :length Code = = −−= −= 20 Hamming codes
Example: Systematic Hamming code (7,4) ][ 1011100 1101010 1110001 33 TPIH ×=           = ][ 1000111 0100011 0010101 0001110 44×=             = IPG 21 Mã hóa Hamming
Mã hóa: H(7,4) Nhiều phép kiểm tra tổng Message=[a b c d] r= (a+b+d) mod 2 s= (a+b+c) mod 2 t= (b+c+d) mod 2 Code=[r s a t b c d]
Tốc ñộ mã: 4/7
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 Message=[1 0 1 0] r=(1+0+0) mod 2 =1 s=(1+0+1) mod 2=0 t=(0+1+0) mod 2 =1 Code=[ 1 0 1 1 0 1 0 ] 22 Hamming codes
Example: Systematic Hamming code (7,4) ][ 1011100 1101010 1110001 33 TPIH ×=           = ][ 1000111 0100011 0010101 0001110 44×=             = IPG 23 Ví dụ mã hóa Hamming H(7,4)
Ma trận sinh G: ñầu tiên là ma trận ñơn vị 4x4
Dữ liệu truyền là vector p
Vector truyền x (G=[I/P])
Vector nhận r và vector lỗi e 24 3/22/2010 5 Sửa lỗi
Nếu không có lỗi, vector ñặc trưng (syndrome) z=zeros
Nếu có 1 lỗi ở vị trí thứ 2
Vector ñặc trưng z là tương với cột thứ 2 của H. Vậy, lỗi ñuợc phát hiện ở vị trí thứ 2 và có thể sửa lại cho ñúng. 25 ðộ lợi mã hóa (Coding Gain)
Tốc ñộ mã R=k/n, k: số symbol dữ liệu, n tổng symbol
SNR từ và SNR của bit
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à truyền dẫn không mã hóa 26 Ví dụ ñộ lợi mã hóa 27 Example of the block codes 8PSK QPSK [dB] / 0NEb BP 28 Cyclic code
Cyclic codes ñược quan tâm và quan trọng vì
Dựa trên cấu trúc ñại số và có thể ứng dụng rộng rãi.
Dễ dàng thực hiện bằng thanh ghi dịch (shift register)
ðược ứng dụng rộng rãi trong thực nghiệm
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
Khi có 1 lỗi ñược phát hiện ở bộ nhận, chúng sẽ ñược yêu cầu truyền lại.
ARQ (Automatic Repeat-reQuest) 29 Cyclic block codes
Một mã tuyến tính (n,k) ñược gọi là Cyclic code nếu khi dịch vòng 1codeword thì ñó cũng là codeword.
Ví dụ: ),...,,,,,...,,( ),...,,,( 121011 )( 1210 −−−+−− − = = inninin i n uuuuuuu uuuu U U “i” cyclic shifts of U UUUUU U ===== = )1101( )1011( )0111( )1110( )1101( )4()3()2()1( 30 3/22/2010 6 Cyclic block codes
Cấu trúc ñại số của Cyclic codes, suy ra codewords ñược sinh ra từ
Mối quan hệ giữa codeword và thanh ghi dịch:
Vậy: )1( degree ...)( 112210 n-XuXuXuuX nn −−++++=U )1()( ... ...,)( 1 )1( )1( 11 )( 1 2 2 101 1 1 2 2 10 1 )1( ++= ++++++= +++= − + −− − −− − − − − n n Xu n n n X n nn n n n n XuX uXuXuXuXuu XuXuXuXuXX n n U U U    )1( modulo )()()( += nii XXXX UUBy extension )1( modulo )()()1( += nXXXX UU 31 Cyclic block codes
Thuật toán mã hóa Cyclic code (n,k): 1. Nhân thông tin với chuỗi bằng 2. Chia kết quả bước 1 với ña thức sinh . Lấy là phần dư 3. Thêm vào ñể tạo thành codeword )(Xm knX − )(Xg )(Xp )(Xp )(XX kn m− )(XU 32 Cyclic block codes
Example: For the systematic (7,4) Cyclic code with generator polynomial 1. Find the codeword for the message )1 1 0 1 0 0 1( 1)()()( :polynomial codeword theForm 1)1()1( :(by )( Divide )1()()( 1)()1011( 3 ,4 ,7 bits messagebitsparity 6533 )(remainder generator 3 quotient 32653 6533233 32     = +++=+= ++++++=++ ++=++== ++=⇒= =−== − − U mpU gm mm mm pgq XXXXXXX XXXXXXXX X)XX XXXXXXXXXX XXX knkn X(X)(X) kn kn )1011(=m 31)( XXX ++=g 33 Cyclic block codes
Find the generator and parity check matrices, G and H, respectively.             = =⇒⋅+⋅+⋅+= 1011000 0101100 0010110 0001011 )1101(),,,(1011)( 321032 G g ggggXXXX Not in systematic form. We do the following: row(4)row(4)row(2)row(1) row(3)row(3)row(1) →++ →+             = 1000101 0100111 0010110 0001011 G           = 1110100 0111010 1101001 H 44×I 33×I TPP 34 Cyclic block codes
Giải mã Cyclic code:
Từ mã ở bộ thu ñược cho bởi
ðặc trưng ở phần dư có ñược bằng cách chia chuỗi nhận cho ña thức sinh:
Với ñặc trưng và mảng tiêu chuẩn, lỗi sẽ ñược ước lượng. )()()( XXX eUr +=Received codewor d Error pattern )()()()( XXXX Sgqr += Syndrome 35 Ví dụ CRC 36 3/22/2010 7 Checking for errors 37 Khả năng của CRC
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 38 BCH Code
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 BCH Performance 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)
Wireless or mobile communication
Satellite communication
Digital television/Digital Video Broadcast(DVB)
High-speed modems (ADSL, xDSL) 41