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

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* Ra đời từ những năm 50 (thế kỷ 20), nhƣng thời kỳ đó mã xoắn không đƣợc ứng dụng rộng rãi do các phƣơng pháp giải mã ban đầu còn khá phức tạp và cho chất lƣợng giải mã không cao. Năm 1967, thuật toán Viterbi xuất hiện mang lại hiệu quả sửa lỗi tốt cho mã xoắn và đơn giản trong quá trình thực hiện. Ngày nay các mã xoắn đóng vai trò chủ đạo trong các hệ thống thông tin hiện đại, nhƣ các hệ thống thông tin di động tế bào mặt đất [1], 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ỷ lệ khác nhau nhƣng cùng xuất phát từ một bộ mã gốc với các loại kênh truyền khác nhau sẽ 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 ở thời điểm hiện tại mà còn phụ thuộc vào một số dấu thông tin ở thời điểm trƣớc đó. Mã xoắn tồn tại ở cả hai dạng nhị phân và phi nhị phân, tuy nhiên trong thực tế các mã xoắn nhị phân đƣợc ứng dụng rộng rãi hơn, nên trong bài báo chọn đối tƣợng nghiên cứu là mã xoắn nhị phân. * Tel: 0989 505717, Email: nghiapx@mta.edu.vn Cấu trúc và tính chất của mã xoắn (n,k,m) đƣợc quyết định bởi các đa thức sinh ( )ig D , các tham số đặc trƣng cho một mã xoắn bao gồm: Tỷ lệ mã hóa k r n , trong đó k là số bít (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 diện cho số các bit thông tin ở thời điểm trƣớc ảnh hƣởng đến bit mã ở thời điểm hiện tại, ở đây m là số thanh ghi dịch trong thiết bị mã hóa; và khoảng cách Hamming tự do dfree- tham số này thể hiện khả năng sửa lỗi của mã xoắn [3]. Hình 1 minh họa một bộ mã hóa xoắn có 2 1( ) 1g D D D và 2 2( ) 1g D D với tỷ lệ mã hóa r = ½. Hình 1. Bộ mã hóa xoắn với r = 1/2 và K = 3 Hoạt động của thiết bị mã hóa xoắn đƣợc thể hiện thông qua các bit thông tin đầu vào (mi), các trạng thái trong ở thời điểm bắt đầu S0[i]S1[i] Sm[i], các trạng thái trong chuyển đến S0[i+1]S1[i+1] Sm[i+1] và các bit mã đầu ra x1[i] x2[i] xn[i] [1,3]. Để đơn giả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 thể hiện đầy đủ trên sơ đồ lƣới mã [2, 3, 4]. Phạm Xuân Nghĩa và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 116 (02): 67 - 71 68 Các thuật toán giải mã xoắn Các thuật toán giải mã xoắn nổi tiếng bao gồm [1]: - Thuật toán giải mã theo ngƣỡng - Thuật toán giải mã nối tiếp. - Thuật toán giải mã theo phƣơng pháp hợp lẽ cực đại (ML). - Thuật toán giải mã Viterbi. Trong khuôn khổ bài báo đi sâu trình bày thuật toán giải mã Viterbi [3, 4]. Ở thuật toán này sử dụng hai metric là metric nhánh (BM) và metric tuyến (PM), trong kỹ thuật giải mã quyết định cứng, ta nhận đƣợc chuỗi các bit kiểm tra đã đƣợc lƣợng tử hóa. Metric nhánh là khoảng cách Hamming giữa các bit kiểm tra mong muốn (ghi trên lƣới) và các bit nhận đƣợc. Một ví dụ đƣợc chỉ ra trong hình 2, trong đó các bit nhận đƣợc là 00. Cho mỗi sự 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 sự chuyển đổi đó. Metric nhánh bằng 0 tƣơng ứng với các trạng thái và sự chuyển đổi trạng thái có khoảng cách Hamming bằng 0. Các metric nhánh khác khác 0 tƣơng ứng với các trƣờng hợp khi có các lỗi bit. 0/000 1/112 0/101 1/011 0/112 1/000 0/011 1/101 i i+1 S1=00 S2=01 S3=10 S4=11 Hình 2. Metric nhánh cho giải mã quyết định cứng Metric tuyến là một giá trị đƣợc kết hợp với một trạng thái trong lƣới. Với giải mã quyết định cứng, metric tuyến tƣơng ứng với khoảng cách Hamming qua tuyến gần giống nhất từ trạng thái khởi tạo tới trạng thái hiện tại trên sơ đồ lƣới. Tuyến gần giống nhất là tuyến ứng với khoảng cách Hamming nhỏ nhất giữa trạng thái khởi tạo và trạng thái hiện tại, đã đƣợc tính toán qua tất cả các tuyến có thể có giữa hai trạng thái. Tuyến với khoảng cách Hamming nhỏ nhất làm cực tiểu hóa tổng số lỗi bit. Các bƣớc giải mã cơ bản của thuật toán Viterbi đƣợc trình bày dƣới đây: Bước 1: Khởi tạo: Từ điểm xuất phát ban đầu i = 0. Đặt các metric và các tuyến ( )( ) 0 0 ( ) 0, ( ) kkM S y empty (1) Giả sử các tuyến đƣợc thể hiện nhƣ một danh sách mà, ban đầu khởi tạo là danh sách trống. Bước 2: Tính toán metric nhánh: Tại bƣớc thứ i, tính toán các metric nhánh cục bộ: ( ) ( [i],v[i])bi HBM d r (2) Trong đó 1 1 0 [ ]2 n n l l l b v i , đƣợc kết hợp với n bit đầu ra [ ]v i của mỗi nhánh và n bit nhận đƣợc [ ]r i . Bước 3: Cộng, so sánh và lựa chọn (ACS) Với mỗi trạng thái ( ) , 0,1, ,2 1k miS k  và tƣơng ứng với cặp nhánh đến từ hai trạng thái trƣớc đó 1 ( ) 1 k iS và 2( ) 1 k iS , thuật toán so sánh các metric nhánh mở rộng 1 1( ) ( ) 1( ) k b i iM S BM và 2 2( ) ( ) 1( ) k b i iM S BM Trong đó 1 1 0 [ ]2 1,2,i n n l j l l b v i (3) Lựa chọn 1 nhánh sống sót, là nhánh có metric tuyến là nhỏ nhất, và cập nhật các metric 1 1 2 2( ) ( ) ( ) ( )( ) 1 1( ) min{ ( ) , (S )+ } k b k bk i i i i iM S M S BM M BM (4) Bước 4: Cập nhật bộ nhớ tuyến: Với mỗi trạng thái ( ) , 0,1, ,2 1k miS k  , cập nhật các tuyến còn tồn tại ( )ky với đầu ra của nhánh sống sót , {1,2}. jk v j ( )( ) 1( , ) j j kk i i ky y v (5) Sau khi cập nhật ta đặt i = i + 1 và tiến hành lại các bƣớc trên đến khi đƣa toàn bộ chuỗi bit mã nhận đƣợc ở phía thu, lúc này ta tìm đƣợc đoạn lƣới có metric truyến nhỏ nhất, đƣợc gọi là đƣờng “sống sót”. Tƣơng ứng là các giá trị bit mã đã đúng (đã đƣợc sửa lỗi). Phạm Xuân Nghĩa và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 116 (02): 67 - 71 69 KỸ THUẬT ĐỘT LỖ CHO MÃ XOẮN 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 chung một thiết bị mã hóa và giải mã. Bản chất của kỹ thuật đột lỗ là quá trình xóa hoặc không truyền đi một số bit của một bộ 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 nên số lƣợng các bit thông tin trong mỗi chuỗi đƣợc giữ nguyên. Kết quả là chuỗi đầu ra thuộc về một mã xoắn đƣợc đột lỗ (PC) có tỷ lệ cao hơn. Ta nghiên cứu phƣơng pháp tạo các mã xoắn đột lỗ từ các mã xoắn gốc nhị phân có tỷ lệ 1/n và m phần tử nhớ [3]. Một ma trận đột lỗ P đặc trƣng cho các quy tắc xóa bỏ các bit đầu ra. P là một ma trận nhị phân pk n phần tử. Trong đó ijp tƣơng ứng với các bit đầu ra đƣợc truyền đi ( ij 1p ) hoặc bị xóa bỏ ( ij 0p ). Một bộ mã hóa của mã PC đƣợc thể hiện nhƣ hình 3. Ta xem xét một bộ mã xoắn có tỷ lệ mã 2/3 gồm 2 phần tử nhớ có thể đƣợc tạo thành bằng cách đột các bit đầu ra của bộ mã xoắn tỷ lệ 1/2 dựa theo ma trận đột lỗ 1 1 . 1 0 P Hình 3. Bộ mã hóa của mã PC dựa trên một mã có tỷ lệ 1/n Bộ mã hóa tƣơng ứng đƣợc thể hiện trong Hình 4. Chuỗi đƣợc mã hóa (0) (1) (0) (1) (0) (1) (0) (1) 1 1 2 2 3 3( , , , , , )i i i i i i i iv v v v v v v v v  của bộ mã hóa tỷ lệ 1/2 đƣợc biến đổi thành một chuỗi mã (0) (1) (0) (0) (1) (0) 1 2 2 3( , , , , , )p i i i i i iv v v v v v v  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. Hình 4. Bộ mã hóa của mã PC tỷ lệ mã 2/3. ĐÁNH GIÁ CHẤT LƢỢNG ĐỘT LỖ THÔNG QUA KẾT QUẢ MÔ PHỎNG Để đánh giá chất lƣợng của các mã đột lỗ ta tiến hành xem xét mã Qualcomm, là một mã hệ thống đệ quy có chiều dài ràng buộc K = 7, tỷ lệ mã hóa r = 1/2, đa thức sinh g = (171,131)8 với nhánh phản hồi là nhánh 171[1]. Trƣớc tiên; tiến hành mô phỏng một hệ thống thông tin có cấu trúc cơ bản để đánh giá ảnh hƣởng của kỹ thuật đột lỗ đến chất lƣợng mã xoắn. Tại đầu phát, luồng bit thông tin đƣợc mã hóa bằng mã Qualcomm sau đó đƣợc điều chế BPSK rồi phát qua kênh AWGN. Tại đầu thu, luồng bit thông tin đầu vào đƣợc giải điều chế, giải mã Viterbi quyết định mềm 8 mức. Hình 5 thể hiện tỷ lệ lỗi bit (BER) của mã Qualcomm đã đƣợc đột lỗ với các tỷ lệ mã hóa khác nhau. Từ kết quả mô phỏng ta nhận thấy mã đƣợc đột lỗ có khả năng sửa lỗi giảm theo số bit bị đột đi. Ví dụ ở xác suất lỗi bít Pe=4x10 -5, đố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ề năng lƣợng là 2,7 dB. Tuy nhiên ở bài toán này ta đã đạt đƣợc độ lợi về tỷ lệ mã hóa khá cao, có nghĩa là đã đạt đƣợc mục đích tăng hiệu quả sử dụng băng thông. Các nhận xét trên đây cũng đúng với kênh fadinh Rayleigh, tuy nhiên chất lƣợng sửa lỗi của các mã (kể cả mã gốc) đối với kênh này kém hơn rất nhiều so với kênh Gauss (hình 6). Phạm Xuân Nghĩa và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 116 (02): 67 - 71 70 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 Hình 6. Chất lượng sửa lỗi của mã Qualcomm đột lỗ với tỷ lệ khác nhau qua kênh Rayleigh Một vấn đề khác cần quan tâm là sự phụ thuộc của chất lƣợng các mã đột lỗ vào các 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ã sau đột lên cùng một tỷ lệ mã hóa nhƣng sử dụng các mẫu đột khác nhau [3]. Vector đột đầu tiên ( 1 [1 0 1 1 1 0]v ) chỉ đột các bit kiểm tra, với vector đột thứ hai ( 2 [0 1 1 1 0 1]v ) ta chỉ đột các bit hệ thống, sau đó thực hiện mô phỏng đánh giá chất lƣợng các mã nhận đƣợc trên kênh Gauss (Hình 7). Từ kết quả nhận đƣợc cho thấy, chất lƣợng của các mã xoắn sử dụng mẫu đột thứ nhất tốt 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 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 7. Chất lượng sửa lỗi của mã Qualcomm với các mẫu đột khác nhau qua kênh Gauss KẾT LUẬN Thông qua nghiên cứu lý thuyết và tiến hành mô phỏng ta có thể kết luận rằng kỹ thuật đột lỗ đem lại nhiều ƣu điểm cho các hệ thống. Tuy nhiên việc sử dụng các mã xoắn tốt kết hợp với các mẫu đột tốt sẽ cho ta độ lợi mã hóa đƣợc cải thiện đáng kể. TÀI LIỆU THAM KHẢO 1. Đỗ Quốc Trinh, Nguyễn Lê Vân, Đinh Thế Cƣờng, Phạm Xuân Nghĩa, (2012) Hệ thống di động 4G LTE từ lý thuyết đến thực tế, Học viện Kỹ thuật Quân sự. 2. Phạm Xuân Nghĩa, Đỗ Quốc Trinh, Nguyễn Hữu Kiên, (2013) Các hệ thống thông tin vô tuyến số, Học viện Kỹ thuật Quân sự. 3. Hagenauer J, (1988) Rate-Compatible Punctured Convolutional Codes (RCPC codes) and Their Applications, IEEE Transaction on Communication. 4. Р. Морелос-Сарагова, (2006) Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение, Техносфера – Москва. 0 1 2 3 4 5 6 7 8 9 10 10 -6 10 -5 10 -4 10 -3 10 -2 10 -1 [E b /N 0 ] dB B it E rr o r R a ti o Binary Convolutional Code [171,133] 8 Rayleigh Channel PC - rate 3/4 PC - rate 4/5 PC - rate 2/3 NoPuncture - rate 1/2 0 1 2 3 4 5 6 7 8 9 10 10 -6 10 -5 10 -4 10 -3 10 -2 10 -1 [E b /N 0 ] dB B it E rr o r R a ti o Binary Convolutional Code [171,133] 8 Rayleigh Channel PC - rate 3/4 PC - rate 4/5 PC - rate 2/3 NoPuncture - rate 1/2 Phạm Xuân Nghĩa và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 116 (02): 67 - 71 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