Bài tập điều kiện môn Kỹ thuật truyền số liệu

Chia sẻ: Do The Thien | Ngày: | Loại File: PDF | Số trang:10

Thêm vào BST

Báo xấu

348
lượt xem 125
download

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

Tìm hiểu phương pháp phát hiện và sửa lỗi theo Convolutional Coding và Viterbi Decoding. Mời các bạn cùng tham khảo tài liệu.

Chủ đề:

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

Lưu

Nội dung Text: Bài tập điều kiện môn Kỹ thuật truyền số liệu

BÀI T P ðI U KI N Môn : K THU T TRUY N S LI U TÌM HI U PHƯƠNG PHÁP PHÁT HI N VÀ S A L I THEO CONVOLUTIONAL CODING VÀ VITERBI DECODING Mã xo n (hay còn g i là mã ch p) là m t lo i mã s a l i trong ñó : - m i symbol m-bit thông tin (chu i m-bit) ñư c mã hóa thành m t symbol n-bit, v i m/n là t l mã hóa (n ≥ m) - Và hàm truy n ñ t là m t hàm c a k symbol thông tin cu i cùng, v i k là chi u dài h n ch c a mã. Convolution Codes, ti ng Vi t g i là Mã ch p, là m t k thu t mã hóa s a sai (FEC). Convolution Codes thu c h mã lư i (mã hóa theo Trellis) và ñư c xây d ng d a trên 1 ña th c sinh ho c 1 sơ ñ chuy n tr ng thái (trellis mã) ñ c trưng. Quá trình gi i mã c a mã ch p ph i d a vào trellis mã thông qua các gi i thu t khác nhau, trong ñó n i ti ng nh t là gi i thu t Viterbi. T i sao g i là mã ch p vì c u trúc mã hóa có th bi u di n dư i d ng phép tính ch p (convolution) gi a ña th c sinh mã và chu i tín hi u ñư c mã hóa. Mã ch p là mã tuy n tính có ma tr n sinh có c u trúc sao cho phép mã hóa có th xem như m t phép l c (ho c l y t ng ch p). Mã ch p ñư c s d ng r ng rãi trong th c t . B i mã hóa ñư c xem như m t t p h p các b l c s tuy n tính v i dãy mã là các ñ u ra c a b l c ñư c phép xen k . Các mã ch p là các mã ñ u tiên ñư c xây d ng các thu t toán gi i mã quy t ñ nh ph n m m hi u qu . B mã hóa cho mã ch p thư ng ñư c coi là m t t p các b l c s . Ví d : Hình sau ch ra m t s ví d v b mã hóa B mã hóa cho mã ch p t c ñ R = ½ Trang 1/10
B mã hóa h th ng R = 2/3 Vào năm 1993, Berrou, Glavieux và Thitimajashima ñã ñưa ra m t sơ ñ mã hóa m i cho các mã ch p ñư c g i là mã Turbo (Hình 1). Trong sơ ñ này dòng thông tin vào ñư c mã hóa hai l n v i m t b xáo tr n ñ t gi a hai b mã hóa nh m t o ra hai dòng d li u ñư c mã hóa có th xem là ñ c l p th ng kê v i nhau. Hình 1. B mã hóa Turbo Trong sơ ñ này các b mã hóa thư ng ñư c s d ng là các b mã hóa cho mã ch p có t c ñ R = 1/2 . Các mã này ñư c s d ng r t hi u qu trên các kênh pha ñinh. Ngư i ta ñã ch ng t r ng hi u năng c a mã Turbo s tăng khi tăng kích thư c c a b xáo tr n. Tuy nhiên trong nhi u ng d ng quan tr ng (ch ng h n khi truy n ti ng nói), kích thư c b xáo tr n quá l n không s d ng ñư c do k t qu gi i mã b gi ch m Coding / Decoding Trang 2/10
Mã xo n trong truy n d n bao g m các k t qu c a s k t h p c a dãy ngu n s d ng nh ng ñ nh d ng xo n khác nhau. Mã xo n GSM bao g m trong vi c thêm 4 bit (thi t l p ñ “0”') cho chu i 185 bit ñ u tiên và sau ñó áp d ng hai xo n khác nhau: ña th c tương ng G1 ( X ) = X 4 + X 3 + 1 và G2 ( X ) = X 4 + X 3 + X + 1 K t qu cu i cùng. là s tr n l n hai l n chu i 189 bit, xem hình sau: Hình 2: TCH / FS truy n Mode S gi i mã mã xo n có th ñư c th c hi n b ng cách s d ng m t thu t toán Viterbi .M t b gi i mã Viterbi khám phá m t cách h p lý song song d li u ngư i dùng m i khi có th trong trình t . Nó mã hóa và so sánh v i m i m t trình t nh n ñư c và ch n lên các kh p g n nh t: nó là m t b gi i mã kh năng t i ña. ð gi m s ph c t p (s lư ng các dãy d li u có th tăng g p ñôi v i m i bit d li u b sung), b gi i mã công nh n t i m i ñi m có trình t nh t ñ nh không th thu c v ñư ng d n kh năng t i ña và lo i b chúng. B nh mã hóa ñư c gi i h n trong nh ng bit K; m t b gi i mã Viterbi trong tình tr ng ho t ñ ng n ñ nh, ch gi 2K-1 ñư ng ñi. S ph c t p c a nó tăng theo c p s nhân v i chi u dài h n ch K. T l mã xo n GSM trên m i dòng d li u là 378 bit m i 20ms, t c là: 18,9KB/s. Tuy nhiên, trư c khi ñi u ch tín hi u này, s có 78 bit không b o v Class II ñư c thêm vào (xem hình 2) Vì v y, t l bit rate GSM cho m i dòng là 456 bit m i 20ms t c là 22,8kb/s * T ng quát Convolutional Coding K thu t mã hóa xo n chuy n (mã hóa) m t chu i bit d li u nh phân thành m t dãy các ký hi u tu n t qua m t phép “ch p”, m i ký hi u là m t nhóm bit. V i m i trư ng h p c a chu i bit d li u ng u nhiên qua phép “ch p” t o ra m t s xác ñ nh các tu n t ký hi u, g i là các tu n t h p l . Tu n t các ký hi u tương ng s ñư c truy n ñi, có m i quan h v i chu i d li u g c. Căn c vào m i quan h này, máy thu s chuy n ngư c l i (gi i mã) thành d li u ñã truy n. N u có l i x y ra, m t tu n t ký hi u h p l g n gi ng nh t v i tu n t ký hi u nh n s ñư c ch n ñ chuy n ngư c thành chu i d li u ban ñ u. K thu t mã hóa xo n ñư c áp d ng cho các thông ñi p r t dài. Gi i pháp gi i mã nhanh ñư c áp d ng r ng rãi là gi i mã Viterbi Trang 3/10
*Ví d mã hóa Gi s chu i bit c n mã hóa là: 11101100 Theo sơ ñ lư i ta có tu n t là: 11 01 10 01 00 01 01 11 *Ví d gi i mã Gi s máy thu nh n ñư c 11 01 11 11 00 01 01 11 1 1 ? ? 1 1 0 0 Các bit b l i, không có ñư ng d n liên t c (không có tu n t h p l ) C n xây d ng các ñư ng liên t c t các thông tin trên. ðư ng d n t t nh t là ñư ng có khác bi t ít nh t v i tu n t nh n ñư c. Có b n ký hi u có th và 8 ho t ñ ng chuy n tr ng thái tương ng có th : Các ph n t kh d ng ñ thi t l p ñư ng liên t c Các ñư ng liên t c có th Th c t có b n ñư ng d n ng viên cho vi c ch n. Căn c vào s sai l ch ñ ch n ra m t. * ng viên 1 Trang 4/10
Tu n t nh n: 11 01 11 11 00 01 01 11 ðư ng d n: 11 10 11 00 11 01 01 11 Sai l ch : 00 11 00 11 11 00 00 00 T ng s sai l ch = 6. Data : 10001100 * ng viên 2 Tu n t nh n: 11 01 11 11 00 01 01 11 ðư ng d n: 11 10 00 10 00 01 01 11 Sai l ch : 00 11 11 01 00 00 00 00 T ng s sai l ch = 5. Data : 10101100 * ng viên 3 Tu n t nh n: 11 01 11 11 00 01 01 11 ðư ng d n: 11 01 01 11 11 01 01 11 Sai l ch : 00 00 10 00 11 00 00 00 T ng s sai l ch = 3. Data : 11001100 * ng viên 4 Tu n t nh n: 11 01 11 11 00 01 01 11 ðư ng d n: 11 01 10 01 00 01 01 11 Sai l ch : 00 00 01 10 00 00 00 00 T ng s sai l ch = 2. Data : 11101100 ðư ng d n 4 có sai l ch nh nh t ñư c ch n và d li u là 11101100. Gi i mã Viterbi Xác ñ nh t t c các ñư ng d n, tính ra kho ng cách Hamming gi a chúng v i tu n t nh n ñư c, ch n l y giá tr nh nh t là công vi c khá l n. ð kh c ph c, l i d ng ñ c tính c a lư c ñ lư i ñ ch n ra m t s ñư ng d n t t nh t cho ch n l a sau cùng: t i m i kho ng, lư i ch có 4 tr ng thái BA có th , có nhi u ñư ng d n ñ n b n tr ng thái này. M i tr ng thái có th d n ñ n m t trong hai tr ng thái trong kho ng k ti p. Ngư c l i, m t tr ng thái cho trư c luôn là ñích ñ n t hai tr ng thái xác ñ nh trong kho ng th i gian k trư c. Nói cách khác, có ñúng hai ñư ng d n ñ n m i m t trong b n tr ng thái. Thông thư ng, m t trong hai ñư ng d n s có s sai l ch tích lũy hi n t i nh hơn ñư ng kia. ðư ng có sai l ch tích lũy hi n hành nh hơn s ñư c ch n ñ xét ti p. Trang 5/10
Thu t toán gi i mã Viterbi Bư c 1: Quá trình b t ñ u t i t ng th nh t v i tr ng thái 00. T ñây ch có hai ñư ng d n. Tính kho ng cách Hamming cho m i ño n ñư ng d n, v i ký hi u tương ng nh n ñư c t i t ng này. Giá tr ñư c ghi l i ñ tích lũy cho bư c k ti p Bư c 2: Có b n ñư ng d n ñư c xác ñ nh d n ñ n t ng k ti p, kho ng cách Hamming c a m i ño n ñư ng lúc này s tùy thu c vào ký hi u nh n ñư c tương ng v i t ng này. Cách tích lũy kho ng cách hamming c a ño n ñư ng: kho ng cách Hamming = kho ng cách Hamming + sai khác t i t ng hi n hành. Tính cho m i ño n ñư ng. Bư c 3: Có tám ñư ng d n ñ n t ng k ti p, hai ñư ng ñ n m t tr ng thái. Tính kho ng cách Hamming cho m i ño n: kho ng cách Hamming = kho ng cách Hamming + sai khác t i t ng hi n hành. M t trong hai ñư ng cùng ñ n m t tr ng thái s có kho ng cách Hamming tích lũy nh hơn và ñư c ch n ñi ti p. Trong trư ng h p c hai có cùng kho ng cách Hamming, ch n ñư ng bên trên. Bư c 4: L p l i bư c 3 cho t ng k ti p cho ñ n khi k t thúc. Cu i cùng còn l i b n ñư ng, ch n ñư ng có kho ng cách Hamming nh hơn c . Bư c 5: Gi i mã t tu n t ký hi u thành chu i bit d li u ñã truy n. Xét ví d sau: ðư ng d n k t thúc t i tr ng thái 11 Data nh n ñư c:11 01 11 11 00 01 01 11 ðư ng d n: 11 01 01 11 00 11 01 10 Sai khác : 00 00 10 00 00 10 00 01 Kho ng cách Hamming = 3 Trang 6/10
ðư ng d n k t thúc t i tr ng thái 10 Data nh n ñư c:11 01 11 11 00 01 01 11 ðư ng d n: 11 01 01 11 00 00 00 11 Sai khác : 00 00 10 00 00 01 01 00 Kho ng cách Hamming = 3 ðư ng d n k t thúc t i tr ng thái 01 Data nh n ñư c:11 01 11 11 00 01 01 11 ðư ng d n: 11 01 01 11 00 11 01 01 Sai khác : 00 00 10 00 00 10 00 10 Kho ng cách Hamming = 3 ðư ng d n k t thúc t i tr ng thái 00 Data nh n ñư c: 11 01 11 11 00 01 01 11 ðư ng d n: 11 01 10 01 00 01 01 11 Sai khác : 00 00 01 10 00 00 00 00 Kho ng cách Hamming = 2 M c ñích c a vi c s a l i chuy n ti p (FEC) là nâng cao năng l c c a m t kênh b ng cách thêm m t s thông tin d phòng ñã ñư c thi t k c n th n cho d li u ñư c truy n thông qua các kênh. Quá trình thêm thông tin dư th a này ñư c g i là mã hóa kênh. Mã hóa xo n và mã hóa kh i là hai hình th c chính c a mã hóa kênh. Mã xo n ho t ñ ng trên d li u n i ti p, m t ho c m t vài bit cùng m t lúc. Mã kh i ho t ñ ng trên nh ng kh i d li u tương ñ i l n (thư ng lên ñ n vài trăm byte) kh i tin nh n. Có r t nhi u mã xo n và mã kh i h u ích, và m t lo t các thu t toán ñ gi i mã các kh i thông tin mã hóa nh n ñư cñ ph c h i d li u g c. Hãy xem xét m t vài ví d . Gi s r ng chúng ta có m t h th ng, nơi m t kênh bit “1” ñư c truy n như là m t ñi n áp c a-1V, và m t kênh bit “0'”ñư c truy n như là m t ñi n áp c a 1 V. ði u này ñư c g i là tín hi u lư ng c c không tr v -to-zero (lư ng c c NRZ). Nó cũng ñư c g i là tín hi u nh phân "ñ i c c" (có nghĩa là các tr ng thái tín hi u thì ñ i ngh ch chính xác v i nhau). Ti p nh n bao g m m t so sánh r ng quy t ñ nh bit nh n ñư c là m t kênh '1 'n u ñi n áp c a nó s th p hơn 0V, và m t '0' n u ñi n áp c a nó l n hơn ho c b ng 0V. M t mu n m u ñ u ra c a comparator gi a m i kho ng bit d li u. Hãy xem ví d cách h th ng c a chúng tôi th c hi n, ñ u tiên, khi Eb/N0 là r t cao, và sau ñó khi Eb/N0 là th p hơn. Mã hóa xo n v i gi i mã Viterbi là m t k thu t FEC mà ñ c bi t phù h p v i m t kênh, trong ñó tín hi u truy n ch y u là b h ng b i ti ng n ph gaussian tr ng (AWGN). B n có th nghĩ AWGN như ti ng n phân ph i ñi n áp mà qua th i gian có ñ c ñi m mà có th ñư c mô t b ng cách s d ng m t Gaussian, ho c bình thư ng, th ng kê, phân Trang 7/10
ph i, t c là m t ñư ng cong chuông. ði u này ñã phân ph i ñi n áp và sai s không có nghĩa là m t tiêu chu n mà là m t hàm c a tín hi u-nhi u t l -(SNR) c a tín hi u nh n ñư c. Gi s th i ñi m này cho r ng m c ñ tín hi u nh n ñư c là c ñ nh. Sau ñó, n u SNR là cao, ñ l ch chu n c a ti ng n là nh , và ngư c l i. Trong truy n thông k thu t s , SNR thư ng ñư c ño b ng các ñi u kho n c a Eb/N0, ñó là vi t t t c a năng lư ng cho m i bit ñư c chia cho m t m t m t ñ ti ng n. Nh ng con s sau ñây cho th y các k t qu c a m t mô ph ng kênh, nơi m t tri u (1 x 10 6) bit kênh ñư c truy n t i qua m t kênh AWGN v i m t E b / N 0 m c 20 dB (t c là các tín hi u ñi n th là mư i l n ti ng n rms ñi n áp ). Trong mô ph ng, m t chút kênh '1 'ñư c truy n m t m c ñ -1V, và m t chút kênh '0' ñư c truy n m t m c ñ 1 V. Các tr c x c a con s này tương ng v i ñi n áp tín hi u nh n ñư c, và tr c y ñ i di n cho s l n m i c p ñi n áp ñã ñư c nh n: Ti p nh n ñơn gi n c a chúng tôi phát hi n m t bit kênh nh n như là '1 'n u ñi n áp c a nó th p hơn 0V, và như là '0' n u ñi n áp c a nó l n hơn ho c b ng 0V. Như m t b ti p nh n s có ít khó khăn ñúng như nh n ñư c m t tín hi u miêu t trong hình trên. R t ít (n u có) kênh ti p nh n chút sai sót s x y ra. Trong ví d này mô ph ng v i E b / N 0 ñ t 20 dB, m t truy n '0 'không bao gi ñư c nh n như là m t '1', và m t truy n '1 'không bao gi ñư c nh n như là m t '0'. Hình ti p theo cho th y các k t qu c a m t mô ph ng kênh tương t như khi bit 1 6 x 10 kênh ñư c truy n t i qua m t kênh AWGN nơi m c ñ E b / N 0 ñã gi m ñ n 6 dB (t c là các tín hi u ñi n th là hai l n ti ng n rms ñi n th ) : Trang 8/10
Bây gi quan sát bên tay m t c a ñư ng cong màu ñ như th nào trong hình trên ñi qua 0V, và làm th nào bên trái bên c a các ñư ng cong màu xanh cũng vư t qua 0V Các ñi m trên ñư ng cong màu ñ ñang trên 0V. ð i di n cho các s ki n mà m t chút kênh ñã ñư c truy n ñi như là m t trong (-1V) ñã ñư c nh n như là m t s không. Các ñi m trên ñư ng cong màu xanh ñư c dư i ñây 0V ñ i di n cho các s ki n mà m t chút kênh ñã ñư c truy n ñi như m t s không (1 V) ñã ñư c nh n như là m t. Rõ ràng, các s ki n này tương ng v i các kênh ti p nh n chút sai sót trong ti p nh n ñơn gi n c a chúng tôi. Trong ví d này mô ph ng v i E b / N 0 ñ t t i 6 dB, m t truy n '0 'ñã ñư c nh n như là m t '1' 1.147 l n, và m t truy n '1 ' ñã ñư c nh n như là m t '0 '1.207 l n, tương ng v i t l l i bit (BER) c a kho ng 0,235% ði u ñó không t t như v y, ñ c bi t là n u b n ñang c g ng ñ truy n t i d li u nén cao, như truy n hình k thu t s .. Tôi s cho b n th y r ng b ng cách s d ng mã hóa xo n v i Viterbi gi i mã, b n có th ñ t ñư c m t BER c a hơn 1 x 10 -7 t i cùng m t E b / N 0, 6 dB. Mã xo n thư ng ñư c mô t b ng hai tham s : t l mã và ñ dài h n ch . T l mã, k / n, ñư c th hi n như là m t t l s bit vào b mã hóa xo n (k) v i s lư ng ñ u ra ký hi u kênh c a b mã hóa xo n (n) trong m t chu kỳ mã hóa nh t ñ nh. Các thông s chi u dài h n ch , K, là b t chi u dài "" c a b mã hóa xo n, t c là có bao nhiêu giai ño n k-bit có s n ñ nuôi các t h p logic mà t o ra nh ng bi u tư ng có liên quan ch t ch ñ n K là m tham s , mà ch ra bao nhiêu. chu kỳ mã hóa m t bit ñ u vào ñư c gi l i và ñư c s d ng ñ mã hoá sau khi l n ñ u tiên xu t hi n ñ u vào c a b mã hóa xo n. Tham s m có th ñư c dùng như chi u dài b nh c a các b mã hóa. Gi i mã Viterbi ñư c phát tri n b i Andrew J. Viterbi, m t ngư i sáng l p c a T ng công ty Qualcomm. T ñó, các nhà nghiên c u khác ñã m r ng v công vi c c a mình b ng cách tìm các mã xo n t t, khám phá các gi i h n th c hi n k thu t này, và thay ñ i các thông s thi t k b gi i mã ñ t i ưu hóa vi c th c hi n các k thu t trong ph n c ng và ph n m m. Thu t toán Viterbi gi i mã cũng ñư c s d ng trong gi i mã trellis-coded ñi u ch , phát minh b i Gottfried Ungerboeck năm 1982. ðây là phương pháp ñư c s d ng trong ñi n tho i-modem dòng ñ si t ch t t l cao c a các bit m i th hai ñ Hertz trên 3 kHz-băng thông tương t ñư ng dây ñi n tho i. Trang 9/10
Gi i mã Viterbi là m t trong hai lo i gi i mã ñư c s d ng v i các thu t toán mã hóa xo n-ki u khác là trình t gi i mã tu n t gi i mã. Có l i th mà nó có th th c hi n r t t t v i khó khăn lâu dài mã xo n, nhưng nó có m t bi n gi i mã th i gian Gi i mã Viterbi có l i th mà nó có m t th i gian gi i mã c ñ nh. ðó là r t thích h p ñ th c hi n b gi i mã ph n c ng. Nhưng yêu c u tính toán c a nó phát tri n theo c p s nhân như là m t ch c năng c a chi u dài h n ch , do ñó nó thư ng là h n ch trong th c hành ñ h n ch ñ dài c a K = 9 ho c ít hơn. Stanford Telecom s n xu t m t K = 9 gi i mã Viterbi ho t ñ ng m c t c ñ lên ñ n 96 kbps, và m t K = 7 b gi i mã Viterbi r ng ho t ñ ng lên ñ n 45 Mbps. Nh ng k thu t Wireless cao c p cung c p K = 9 Viterbi decoder r ng ho t ñ ng m c giá lên ñ n 2 Mbps. NTT ñã công b m t b gi i mã Viterbi r ng ho t ñ ng 60 Mbps, nhưng tôi không bi t thương m i s n có c a nó. ð nh lu t Moore ñư c áp d ng ñ gi i mã Viterbi cũng như vi x lý, vì v y hãy xem xét các m c giá nói trên như là m t nh ch p c a nhà nư c-of-the -ngh thu t th c hi n vào ñ u năm 1999. Trong nhi u năm qua, xo n v i mã hóa gi i mã Viterbi ñã ñư c các k thu t FEC ch y u ñư c s d ng trong giao ti p không gian, ñ c bi t là trong các m ng truy n thông v tinh ñ a tĩnh, như là VSAT (thi t b ñ u cu i kh u ñ r t nh ) các m ng. Các bi n th ph bi n nh t ñư c s d ng trong các m ng VSAT là t l 1/ 2 mã hóa xo n b ng cách s d ng m t mã v i chi u dài h n ch K = 7. V i mã này, b n có th truy n pha nh phân ho c chia bốn ñư c ca-keyed (BPSK hay QPSK) tín hi u v i ít nh t 5 dB ít năng lư ng hơn b n mu n mà không c n nó. ðó là m t s gi m trong Watts c a hơn m t nhân t c a ba! ði u này là r t h u ích trong vi c gi m truy n và / ho c ăng ten ho c cho phép d li u chi phí tăng t giá trao truy n quy n năng tương t và kích thư c ăng ten. Nhưng có m t s cân b ng, t l d li u cùng v i t l 1/2 xo n mã m t g p ñôi băng thông c a tín hi u tương t mà không có nó, cho r ng k thu t ñi u ch là như nhau. ðó là b i vì v i t l 1/2 mã hóa xo n, b n có bi u tư ng hai kênh truy n d li u cho m i bit. Tuy nhiên, n u b n nghĩ r ng nh ng s cân b ng như là 5dB ti t ki m ñi n năng cho m t s m r ng băng thông 3dB, b n có th nhìn th y b n ñi ra phía trư c. Hãy nh r ng: n u các k thu t ñi u ch gi nguyên, các y u t m r ng băng thông c a m t mã xo n ñơn gi n ch là n / k. Nhi u kênh phát thanh là kênh AWGN, nhưng nhi u ngư i, ñ c bi t là các kênh radio trên ñ t li n cũng có khi m khác, như multipath fading ch n l c, can thi p, và ti ng n không khí (sét). Truy n và nh n tín hi u có th thêm spurious và ti ng n giai ño n ñ n tín hi u mong mu n là t t. M c dù xo n v i mã hóa gi i mã Viterbi có th có ích trong vi c ñương ñ u v i nh ng v n ñ khác, nó có th không là k thu t t t nh t. Trang 10/10