Đánh giá hiệu quả sửa lỗi của mã xoắn đột lỗ

Phạm Xuân Nghĩa và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 116 (02): 67 - 71 ĐÁNH GIÁ HIỆU QUẢ SỬA LỖI CỦA MÃ XOẮN ĐỘT LỖ Phạm Xuân Nghĩa*, Nguyễn Khánh Cƣờng Học viện Kỹ thuật quân sự TÓM TẮT Nội dung bài báo này tập trung vào đánh giá chất lƣợng của mã xoắn khi sử dụng kỹ thuật đột lỗ thông qua sự so sánh tỷ lệ lỗi bit giữa các tỷ lệ mã với cùng một mã gốc bằng việc sử dụng các mẫu đột với các mô hình kênh truyền dẫn khác nhau. Kết quả so sánh cho thấy, với cùng một tỷ lệ mã hóa và cùng một mã gốc, nhƣng với các mẫu đột khác nhau cho ta chất lƣợng giải mã khác nhau, độ lợi mã hóa của các mẫu đột tốt lên tới 0,5 dB. Từ khóa: Mã xoắn đột lỗ, mẫu đột lỗ, tỷ lệ mã GIỚI THIỆU* Cấu trúc và tính chất của mã xoắn (n,k,m) Ra đời từ những năm 50 (thế kỷ 20), nhƣng đƣợc quyết định bởi các đa thức sinh gDi (), thời kỳ đó mã xoắn không đƣợc ứng dụng các tham số đặc trƣng cho một mã xoắn bao k rộng rãi do các phƣơng pháp giải mã ban đầu gồm: Tỷ lệ mã hóa r , trong đó k là số bít còn khá phức tạp và cho chất lƣợng giải mã n không cao. Năm 1967, thuật toán Viterbi (dấu) thông tin, n - các bit (dấu) mã ở mỗi thời điểm; độ dài ràng buộc K = k.(m+1), đại xuất hiện mang lại hiệu quả sửa lỗi tốt cho mã diện cho số các bit thông tin ở thời điểm trƣớc xoắn và đơn giản trong quá trình thực hiện. ảnh hƣởng đến bit mã ở thời điểm hiện tại, ở Ngày nay các mã xoắn đóng vai trò chủ đạo đây m là số thanh ghi dịch trong thiết bị mã trong các hệ thống thông tin hiện đại, nhƣ các hóa; và khoảng cách Hamming tự do dfree- hệ thống thông tin di động tế bào mặt đất [1], tham số này thể hiện khả năng sửa lỗi của mã xoắn [3]. các hệ thống thông tin vệ tinh...Việc nghiên cứu chất lƣợng sửa lỗi của mã xoắn ở các tỷ Hình 1 minh họa một bộ mã hóa xoắn có 2 và lệ khác nhau nhƣng cùng xuất phát từ một bộ g1( D ) 1 D D 2 mã gốc với các loại kênh truyền khác nhau sẽ g2 ( D ) 1 D với tỷ lệ mã hóa r = ½. giúp cho việc ứng dụng mã xoắn trong các hệ thống truyền tin hiệu quả hơn. MÃ XOẮN VÀ CÁC KỸ THUẬT GIẢI MÃ CƠ BẢN Mã xoắn và các tham số đặc trưng Đặc trƣng quan trọng của mã xoắn là một dấu mã không những phụ thuộc vào dấu thông tin Hình 1. Bộ mã hóa xoắn với r = 1/2 và K = 3 ở thời điểm hiện tại mà còn phụ thuộc vào Hoạt động của thiết bị mã hóa xoắn đƣợc thể một số dấu thông tin ở thời điểm trƣớc đó. Mã hiện thông qua các bit thông tin đầu vào (mi), xoắn tồn tại ở cả hai dạng nhị phân và phi nhị các trạng thái trong ở thời điểm bắt đầu phân, tuy nhiên trong thực tế các mã xoắn nhị S0[i]S1[i] Sm[i], các trạng thái trong chuyển phân đƣợc ứng dụng rộng rãi hơn, nên trong đến S0[i+1]S1[i+1] Sm[i+1] và các bit mã bài báo chọn đối tƣợng nghiên cứu là mã đầu ra x1[i] x2[i] xn[i] [1,3]. Để đơn giản xoắn nhị phân. cho việc thực hiện mã hóa và giải mã ta sử dụng sơ đồ lƣới, các tham số nêu trên đƣợc * Tel: 0989 505717, Email: nghiapx@mta.edu.vn thể hiện đầy đủ trên sơ đồ lƣới mã [2, 3, 4]. 67 Phạm Xuân Nghĩa và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 116 (02): 67 - 71 Các thuật toán giải mã xoắn tổng số lỗi bit. Các bƣớc giải mã cơ bản của Các thuật toán giải mã xoắn nổi tiếng bao thuật toán Viterbi đƣợc trình bày dƣới đây: gồm [1]: Bước 1: Khởi tạo: - Thuật toán giải mã theo ngƣỡng Từ điểm xuất phát ban đầu i = 0. Đặt các - Thuật toán giải mã nối tiếp. metric và các tuyến - Thuật toán giải mã theo phƣơng pháp hợp lẽ ()k ()k cực đại (ML). M( S0 ) 0, y0 ( empty ) (1) - Thuật toán giải mã Viterbi. Giả sử các tuyến đƣợc thể hiện nhƣ một danh Trong khuôn khổ bài báo đi sâu trình bày sách mà, ban đầu khởi tạo là danh sách trống. thuật toán giải mã Viterbi [3, 4]. Ở thuật toán Bước 2: Tính toán metric nhánh: này sử dụng hai metric là metric nhánh (BM) Tại bƣớc thứ i, tính toán các metric nhánh cục và metric tuyến (PM), trong kỹ thuật giải mã bộ: BM()b d( r [i],v[i]) quyết định cứng, ta nhận đƣợc chuỗi các bit iH (2) kiểm tra đã đƣợc lƣợng tử hóa. Metric nhánh n 1 là khoảng cách Hamming giữa các bit kiểm Trong đó nl1 , đƣợc kết hợp b vl [ i ]2 tra mong muốn (ghi trên lƣới) và các bit nhận l 0 đƣợc. Một ví dụ đƣợc chỉ ra trong hình 2, với n bit đầu ra vi[] của mỗi nhánh và n bit trong đó các bit nhận đƣợc là 00. Cho mỗi sự nhận đƣợc ri[] chuyển đổi trạng thái, các số trên các nhánh . (của sơ đồ lƣới mã) thể hiện metric nhánh cho Bước 3: Cộng, so sánh và lựa chọn (ACS) ()km sự chuyển đổi đó. Metric nhánh bằng 0 tƣơng Với mỗi trạng thái Ski , 0,1, ,2 1 ứng với các trạng thái và sự chuyển đổi trạng và tƣơng ứng với cặp nhánh đến từ hai trạng ()k ()k thái có khoảng cách Hamming bằng 0. Các thái trƣớc đó S 1 và S 2 , thuật toán so metric nhánh khác khác 0 tƣơng ứng với các i 1 i 1 sánh các metric nhánh mở rộng trƣờng hợp khi có các lỗi bit. ()()kb ()()kb11 và 22 i i+1 M() Sii1 BM M() Sii1 BM 0/000 n 1 S1=00 Trong đó nl1 i 1/112 bjl v[ i ]2 1,2, l 0 (3) 0/101 S2=01 Lựa chọn 1 nhánh sống sót, là nhánh có 1/011 metric tuyến là nhỏ nhất, và cập nhật các 0/112 S3=10 metric 1/000 ()k ()()()()k1 b 1 k 2 b 2 0/011 M( S ) min{ M ( S ) BM , M (S )+ BM } (4) S4=11 i i11 i i i 1/101 Bước 4: Cập nhật bộ nhớ tuyến: Hình 2. Metric nhánh cho giải mã quyết định cứng Với mỗi trạng thái ()km, cập Ski , 0,1, ,2 1 Metric tuyến là một giá trị đƣợc kết hợp với nhật các tuyến còn tồn tại y ()k với đầu ra của một trạng thái trong lƣới. Với giải mã quyết nhánh sống sót vj, {1,2}. định cứng, metric tuyến tƣơng ứng với k j khoảng cách Hamming qua tuyến gần giống ()k ()k j yi(,) y i1 v k nhất từ trạng thái khởi tạo tới trạng thái hiện j (5) tại trên sơ đồ lƣới. Tuyến gần giống nhất là Sau khi cập nhật ta đặt i = i + 1 và tiến hành tuyến ứng với khoảng cách Hamming nhỏ lại các bƣớc trên đến khi đƣa toàn bộ chuỗi nhất giữa trạng thái khởi tạo và trạng thái hiện bit mã nhận đƣợc ở phía thu, lúc này ta tìm tại, đã đƣợc tính toán qua tất cả các tuyến có đƣợc đoạn lƣới có metric truyến nhỏ nhất, thể có giữa hai trạng thái. Tuyến với khoảng đƣợc gọi là đƣờng “sống sót”. Tƣơng ứng là cách Hamming nhỏ nhất làm cực tiểu hóa các giá trị bit mã đã đúng (đã đƣợc sửa lỗi). 68 Phạm Xuân Nghĩa và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 116 (02): 67 - 71 KỸ THUẬT ĐỘT LỖ CHO MÃ XOẮN Do đó ta thấy đầu ra thứ hai cứ cách một bit loại bỏ đi một bit không đƣợc truyền đi. Xuất phát từ tính chất không ổn định của kênh truyền cùng với yêu cầu về sự đơn giản trong thiết bị, kỹ thuật đột lỗ cho mã xoắn đƣợc ứng dụng trong hệ thống truyền thông. Việc ứng dụng kỹ thuật này nhằm tạo ra các mã xoắn có tỷ lệ mã hóa khác nhau xuất phát từ một mã gốc (mã mẹ), điều này giúp ta tăng hiệu quả truyền tin, đồng thời vẫn sử dụng Hình 4. Bộ mã hóa của mã PC tỷ lệ mã 2/3. chung một thiết bị mã hóa và giải mã. ĐÁNH GIÁ CHẤT LƢỢNG ĐỘT LỖ Bản chất của kỹ thuật đột lỗ là quá trình xóa THÔNG QUA KẾT QUẢ MÔ PHỎNG hoặc không truyền đi một số bit của một bộ Để đánh giá chất lƣợng của các mã đột lỗ ta mã hóa tỷ lệ thấp một cách có hệ thống. Vì cấu trúc lƣới của bộ mã hóa không thay đổi tiến hành xem xét mã Qualcomm, là một mã nên số lƣợng các bit thông tin trong mỗi chuỗi hệ thống đệ quy có chiều dài ràng buộc K = 7, đƣợc giữ nguyên. Kết quả là chuỗi đầu ra tỷ lệ mã hóa r = 1/2, đa thức sinh g = thuộc về một mã xoắn đƣợc đột lỗ (PC) có tỷ (171,131)8 với nhánh phản hồi là nhánh lệ cao hơn. Ta nghiên cứu phƣơng pháp tạo 171[1]. Trƣớc tiên; tiến hành mô phỏng một các mã xoắn đột lỗ từ các mã xoắn gốc nhị hệ thống thông tin có cấu trúc cơ bản để đánh phân có tỷ lệ 1/n và m phần tử nhớ [3]. Một giá ảnh hƣởng của kỹ thuật đột lỗ đến chất ma trận đột lỗ P đặc trƣng cho các quy tắc lƣợng mã xoắn. Tại đầu phát, luồng bit thông xóa bỏ các bit đầu ra. P là một ma trận nhị tin đƣợc mã hóa bằng mã Qualcomm sau đó phân phần tử. Trong đó tƣơng knp pij đƣợc điều chế BPSK rồi phát qua kênh ứng với các bit đầu ra đƣợc truyền đi AWGN. Tại đầu thu, luồng bit thông tin đầu ( ) hoặc bị xóa bỏ ( ). Một bộ pij 1 pij 0 vào đƣợc giải điều chế, giải mã Viterbi quyết mã hóa của mã PC đƣợc thể hiện nhƣ hình 3. định mềm 8 mức. Hình 5 thể hiện tỷ lệ lỗi bit Ta xem xét một bộ mã xoắn có tỷ lệ mã 2/3 (BER) của mã Qualcomm đã đƣợc đột lỗ với gồm 2 phần tử nhớ có thể đƣợc tạo thành các tỷ lệ mã hóa khác nhau. Từ kết quả mô bằng cách đột các bit đầu ra của bộ mã xoắn phỏng ta nhận thấy mã đƣợc đột lỗ có khả tỷ lệ 1/2 dựa theo ma trận đột lỗ 11 năng sửa lỗi giảm theo số bit bị đột đi. Ví dụ P . -5 10 ở xác suất lỗi bít Pe=4x10 , đối với mã gốc Qualcomm (r=1/2) ta cần Eb/N0 =4,3dB, với mã này đã bị đột lỗ ở tỷ lệ mã r=2/3 yêu cầu Eb/N0 =5,6dB nhƣ vậy ta đã bị thiệt về tỷ số Eb/N0 là 1,3 dB. Với mã Qualcomm đột lỗ ở tỷ lệ mã r=3/4 để đảm bảo giá trị Pe nhƣ trên cần Eb/N0 = 7 dB, đồng nghĩa với sự trả giá về Hình 3. Bộ mã hóa của mã PC dựa trên một mã năng lƣợng là 2,7 dB. có tỷ lệ 1/n Tuy nhiên ở bài toán này ta đã đạt đƣợc độ lợi Bộ mã hóa tƣơng ứng đƣợc thể hiện trong về tỷ lệ mã hóa khá cao, có nghĩa là đã đạt Hình 4. Chuỗi đƣợc mã hóa đƣợc mục đích tăng hiệu quả sử dụng băng (0) (1) (0) (1) (0) (1) (0) (1) v(,,,,,) vi v i v i1 v i 1 v i 2 v i 2 v i 3 v i 3 thông. Các nhận xét trên đây cũng đúng với của bộ mã hóa tỷ lệ 1/2 đƣợc biến đổi thành kênh fadinh Rayleigh, tuy nhiên chất lƣợng một chuỗi mã sửa lỗi của các mã (kể cả mã gốc) đối với (0) (1) (0) (0) (1) (0) kênh này kém hơn rất nhiều so với kênh vp(,,,,,) v i v i v i1 v i 2 v i 2 v i 3 Gauss (hình 6). 69 Phạm Xuân Nghĩa và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 116 (02): 67 - 71 bit này trong quá trình giải mã. Nhƣ vậy để các mã xoắn đột lỗ mang lại chất lƣợng và hiệu quả tốt cho các hệ thống truyền tin, không những phải tìm các mã xoắn tốt mà còn phải tìm đƣợc các mẫu đột tốt tƣơng ứng với các mã đó. Hình 5. Chất lượng sửa lỗi của mã Qualcomm đột lỗ với tỷ lệ khác nhau qua kênh Gauss Binary Convolutional Code [171,133] Rayleigh Channel 8 -1 10 -2 10 -3 10 Hình 7. Chất lượng sửa lỗi của mã Qualcomm với Bit Ratio Error các mẫu đột khác nhau qua kênh Gauss -4 10 PC - rate 3/4 PC - rate 4/5 KẾT LUẬN -5 10 PC - rate 2/3 NoPuncture - rate 1/2 Thông qua nghiên cứu lý thuyết và tiến hành -6 10 0 1 2 3 4 5 6 7 8 9 10 [E /N ] b 0 dB mô phỏng ta có thể kết luận rằng kỹ thuật đột Hình 6. Chất lượng sửa lỗi của mã Qualcomm đột lỗ đem lại nhiều ƣu điểm cho các hệ thống. lỗ với tỷ lệ khác nhau qua kênh Rayleigh Tuy nhiên việc sử dụng các mã xoắn tốt kết Một vấn đề khác cần quan tâm là sự phụ hợp với các mẫu đột tốt sẽ cho ta độ lợi mã thuộc của chất lƣợng các mã đột lỗ vào các hóa đƣợc cải thiện đáng kể. mẫu đột. Khảo sát vấn đề này ta tiến hành tiến hành đột lỗ mã Qualcomm để đƣa các mã TÀI LIỆU THAM KHẢO sau đột lên cùng một tỷ lệ mã hóa nhƣng sử 1. Đỗ Quốc Trinh, Nguyễn Lê Vân, Đinh Thế dụng các mẫu đột khác nhau [3]. Vector đột Cƣờng, Phạm Xuân Nghĩa, (2012) Hệ thống di đầu tiên (v [1 0 1 1 1 0]) chỉ đột động 4G LTE từ lý thuyết đến thực tế, Học viện 1 Kỹ thuật Quân sự. các bit kiểm tra, với vector đột thứ hai 2. Phạm Xuân Nghĩa, Đỗ Quốc Trinh, Nguyễn ( ) ta chỉ đột các bit v2 [0 1 1 1 0 1] Hữu Kiên, (2013) Các hệ thống thông tin vô tuyến hệ thống, sau đó thực hiện mô phỏng đánh giá số, Học viện Kỹ thuật Quân sự. chất lƣợng các mã nhận đƣợc trên kênh Gauss 3. Hagenauer J, (1988) Rate-Compatible (Hình 7). Punctured Convolutional Codes (RCPC codes) and Their Applications, IEEE Transaction on Từ kết quả nhận đƣợc cho thấy, chất lƣợng Communication. của các mã xoắn sử dụng mẫu đột thứ nhất tốt 4. Р. Морелос-Сарагова, (2006) Искусство hơn so với mẫu đột thứ 2 khoảng 0,5 dB. помехоустойчивого кодирования. Методы, Sở dĩ có kết quả nhƣ trên là do lƣợng thông алгоритмы, применение, Техносфера – tin chứa trong mỗi bit mã và vai trò của các Москва. 70 Phạm Xuân Nghĩa và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 116 (02): 67 - 71 SUMMARY PERFORMANCE EVALUATION OF ERROR CORRECTION IN PUNCTURED CONVOLUTIONAL CODES Pham Xuan Nghia*, Nguyen Khanh Cuong Le Quy Don Technical University The contents of this article focus on the performance evaluation of punctured convolutional code when using puncture technical by the comparison between the bit error rate with the same mother code using various punctured patterns with the different transmission channels. The comparison results show that, with the same code rate and mother code, but with the various punctured patterns for different decoding performance, coding gain of the good puncturing patterns is up to 0.5 dB Keywores: punctured convolutional code, punctured patterns, code rate Ngày nhận bài:; Ngày phản biện:; Ngày duyệt đăng: Phản biện khoa học: TS. Dương Chính Cương – Trường ĐH Công nghệ Thông tin & Truyền thông - ĐHTN * Tel: 0989 505717, Email: nghiapx@mta.edu.vn 71