Nghiên cứu ứng dụng biểu đồ exit trong phân tích và thiết kế các hệ thống giải mã lặp - Nguyễn Thu Hiền

Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 39, 10 - 2015 21 NGHIÊN CỨU ỨNG DỤNG BIỂU ĐỒ EXIT TRONG PHÂN TÍCH VÀ THIẾT KẾ CÁC HỆ THỐNG GIẢI MÃ LẶP Nguyễn Thu Hiên1*, Lê Nhật Thăng1, Nguyễn Thúy Anh2 Tóm tắt: Biểu đồ truyền đạt thông tin ngoại lai (EXIT) cung cấp một công cụ tính toán hiệu quả, hình ảnh hóa được tiến trình giải mã lặp trong các bộ giải mã kênh của hệ thống thông tin. Bài báo trình bày một số kết quả ứng dụng biểu đồ EXIT trong việc phân tích và thiết kế các hệ thống giải mã lặp, từ đó đưa ra sở cứ lựa chọn các mã thành phần thích hợp để đạt được hiệu năng tiếp cận dung lượng Shannon, mà không yêu cầu các mô phỏng véc cạn để ước lượng tỉ lệ lỗi bit BER. Từ khóa: Mã hóa sửa lỗi trước, Mã Turbo, Giải mã lặp, Biểu đồ EXIT. 1. ĐẶT VẤN ĐỀ Lịch sử của mã hóa kênh được bắt đầu kể từ công trình nghiên cứu tiên phong của Shannon vào năm 1948 [1,2], trong đó ông đã chỉ ra rằng việc truyền thông tin tin cậy có thể đạt được nhờ sử dụng mã hóa kênh, đó là việc đưa thông tin kiểm tra vào các bản tin gửi đi. Kể từ khi dung lượng của một hệ thống truyền thông được định lượng bởi Shannon [1], các nhà nghiên cứu đã cố gắng đưa ra các hệ thống truyền thông không dây có tỷ lệ lỗi bit BER thấp, tốc độ bit cao. Những tiến bộ trong mã hóa (mã hóa kênh) đã làm cho các hệ thống này khả thi tiếp cận đến giới hạn dung lượng Shannon [2-7]. Các khái niệm về mã hóa móc nối song song, nối tiếp với giải mã lặp đã được đề xuất trong [8-10] . Nhiều nghiên cứu về tối ưu hóa hiệu năng của các mã móc nối nhằm cải thiện độ dốc đường cong BER và để đạt được hiệu năng tiệm cận dung lượng không thể không kể đến những nghiên cứu chuyên sâu về tính hội tụ của giải mã lặp trong những năm gần đây. Sử dụng các công cụ bán phân tích để phân tích tính hội tụ của các hệ thống giải mã lặp được đề xuất trong [11-14]. Việc trao đổi thông tin ngoại lai giữa các bộ giải mã thành phần đã được hình ảnh hóa qua các biểu đồ truyền đạt thông tin ngoại lai (EXIT) [15]. Để có sở cứ lựa chọn mã kênh thích hợp sử dụng trong các nghiên cứu về hệ thống truyền thông ở tầng bình lưu, chúng tôi đã bước đầu tiến hành nghiên cứu làm rõ phương pháp ứng dụng biểu đồ EXIT trong phân tích hiệu năng hệ thống giải mã lặp nói chung. Trong bài báo này, chúng tôi chỉ ra một số kết quả đã đạt được khi ứng dụng biểu đồ EXIT trong phân tích, thiết kế hệ thống giải mã lặp và lý giải về phương pháp sử dụng công cụ bán phân tích này trong một hệ thống mã turbo móc nối song song điển hình. 2. NGUYÊN LÝ GIẢI MÃ LẶP Để hiểu rõ về nguyên lý giải mã lặp. Chúng ta xét sơ đồ bộ mã hóa và giải mã của mã Turbo ở hình 1& hình 2 [16]. Trong đó, các đầu vào của bộ giải mã R(x), R(1), và R(2), là các tỷ lệ hợp lệ logarit từ kênh tương ứng đối với chuỗi bit thông tin và kiểm tra: x,  1p ,  2p . Hình 1. Bộ mã hóa Turbo [16]. Kỹ thuật điều khiển & Điện tử N. T. Hiên, L.N. Thăng, N.T. Anh “Nghiên cứu ứng dụng biểu đồ EXIT giải mã lặp.” 22 Hình 2. Bộ giải mã Turbo [16]. Ở vòng lặp đầu tiên (l=1), bộ giải mã 1chưa có thông tin ngoại lai, vì vậy các giá trị đầu vào của thuật toán giải mã BCJR là:  xR ,  1R . Kết quả cho ra các xác suất hậu nghiệm đối với các bit bản tin là tỷ lệ hợp lệ logarit ( )1(1L ). Thông tin ngoại lai mới mà bộ giải mã 1 tạo ra là:  xRLE  )1(1 )1( 1 (1) Các đầu vào của bộ giải mã 2 từ kênh là:   xR và  2R , với các giá trị  xR được ghép xen theo cách giống như khi đưa vào bộ mã hóa 2. Đối với vòng lặp thứ l, bộ giải mã 2 sẽ sử dụng thông tin ngoại lai từ bộ mã hóa 1 (  1lE ) làm thông tin tiền nghiệm bổ sung đối với các bit bản tin (  2lA ). Vector  1 lE từ bộ giải mã 1 sẽ được ghép xen theo cách ghép xen giống như các bit bản tin của bộ mã hóa 2:  )1()2( ll EA  (2) Đầu ra của bộ giải mã 2 là các xác suất hậu nghiệm đối với các bit bản tin ( )2(lL ). Thông tin ngoại lai mới được tạo bởi bộ giải mã 2 đối với các bit bản tin tại vòng lặp thứ l là:    )2()2()2( lxll ARLE  (3) Trong vòng lặp thứ 2 và các vòng lặp tiếp theo, bộ giải mã 1 sẽ lặp lại thuật toán giải mã BCJR với thông tin tiền nghiệm bổ sung ở dạng thông tin ngoại lai từ bộ giải mã 2 tạo ra ở vòng lặp trước. Vì vậy, trong vòng lặp thứ l, thông tin ngoại lai từ bộ giải mã 2 được giải ghép xen theo thứ tự giống như thứ tự các bit bản tin của bộ mã hóa 1:  )2( 11)1(  ll EA (4) Thông tin ngoại lai mới từ bộ giải mã 1:   )1()1()1( l x ll ARLE  (5) Lưu ý: các tỷ lệ hợp lệ log từ kênh không thay đổi qua giải mã turbo; chỉ có thông tin ngoại lai thay đổi ở mỗi vòng lặp. 3. PHÂN TÍCH BIỂU ĐỒ EXIT Biểu đồ EXIT được đề xuất bởi Stephan ten Brink [11,12], là một công cụ bán phân tích mô tả việc thông tin ngoại lai giữa các bộ giải mã thành phần trong các vòng lặp giải mã của hệ thống giải mã lặp. Biểu đồ EXIT cung cấp một hình ảnh trực quan đơn giản và bền vững quá trình giải mã. Ngoài ra, biểu đồ EXIT được sử dụng để dự đoán giá trị SNR (tỷ số tín hiệu trên nhiễu) tại đó bộ giải mã bắt đầu hội tụ đặc tính hội tụ (điểm bắt đầu của Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 39, 10 - 2015 23 vùng dốc). Các biểu đồ EXIT cho phép đánh giá nhanh những ảnh hưởng của các tham số thiết kế (các bộ mã hóa thành phần, các thuật toán giải mã sử dụng,). Một trong những ưu điểm chính của biểu đồ EXIT là hai bộ giải mã thành phần được phân tích riêng biệt, sau đó hai kết quả này được kết hợp để có được hình ảnh về hiệu năng của cả hệ thống. Việc áp dụng biểu đồ EXIT sẽ dựa trên hai giả thiết:  Các giá trị LLR tiền nghiệm hầu như không tương quan;  Hàm mật độ xác suất của các giá trị LLR tiền nghiệm là hàm phân bố Gauss. Phân tích biểu đồ EXIT được áp dụng đối với các hệ thống móc nối song song, nối tiếp và móc nối hỗn hợp sử dụng giải mã lặp. Các lý giải cụ thể về phương pháp sử dụng biểu đồ EXIT trong các hệ thống này được bàn luận qua hệ thống mã turbo móc nối song song.Trước khi đi vào phân tích cụ thể , các khái niệm tỷ lệ hợp lệ logarit (LLR) và thông tin tương hỗ (MI) cần được hiểu rõ. Trên cơ sở nguyên lý giải mã lặp ở mục 2, chúng ta thấy rằng thông tin ngoại lai được cập nhật liên tục trong khi đó các LLR về kênh là cố định. Do đó, để bộ giải mã có thể hội tụ, thì thông tin ngoại lai cần phải cung cấp nhiều thông tin hơn về các bit đã phát tại mỗi vòng lặp. Khi đó, lượng thông tin hữu ích đem lại được xác định qua một đại lượng I(x;E), là thông tin tương hỗ giữa thông tin ngoại lai (E) và các ký hiệu đã phát x, hay chính là lượng thông tin E nói về x. Điều đó có nghĩa là, mỗi bộ giải mã thành phần tạo ra thông tin ngoại lai tại đầu ra của nó có thông tin tương hỗ lớn hơn thông tin tương hỗ được cung cấp bởi thông tin tiền nghiệm tại đầu vào. Để xác định hiệu năng của bộ giải mã thành phần và xác định xem liệu thực sự thông tin ngoại lai này có hữu ích hay không, thì một vector thông tin ngoại lai đầu vào (A) được tạo ra có thông tin tương hỗ là I(x;A), đã biết, được chuyển đến bộ giải mã. Khi thuật toán giải mã thực thi, I(x;E) sẽ được tính toán. Quá trình này được lặp đi lặp lại đối với một số vector A có I(x;A) khác nhau. Trong đó, nhiễu kênh và các LLR thu là không đổi. Xét bộ mã hóa và giải mã Turbo ở hình 1& hình 2, có đa thức sinh của các bộ mã hóa thành phần là (Gr,G)=(7,5),số bộ nhớ=2, tỷ lệ mã hóa 1/3 (mã này đã được chúng tôi sử dụng trong tất cả các kết quả mô phỏng). Với dòng bit đầu vào x và dòng bit mã hóa c ở bộ mã hóa, còn đầu vào bộ giải mã là các LLR tiền nghiệm (A) và đầu ra là các LLR ngoại lai (E). Khi đó, thông tin tương hỗ giữa x và A là IA=I(x, A), 0≤IA ≤1, được sử dụng để định lượng nội dung thông tin biết trước sẽ là [18]:          11 2 log 2 1 , 2 1,1         XpXp xXp xXpIAxI AA A x AA    (6) trong đó,  xXpA  là PDF có điều kiện liên quan đến LLR tiền nghiệm A và các bit thông tin x, được giả thiết có xác suất như nhau (P(x=+1)= P(x=-1)=1/2). Để tính được IA trong (6), thì phải biết được PDF  xXpA  của A. Nếu chúng ta mô hình hóa A là một biến ngẫu nhiên Gauss độc lập trung bình không nA có phương sai 2 A , liên quan đến các bit đầu vào bộ mã hóa  1,1 x như hình 1, đầu vào tiền nghiệm A được viết như [11]: AA nxA   với 22AA   , vì A là giá trị LLR tuân theo phân bố Gauss với điều kiện bộ ghép xen đủ lớn. Khi đó, hàm mật độ xác suất có điều kiện của A sẽ là: Kỹ thuật điều khiển & Điện tử N. T. Hiên, L.N. Thăng, N.T. Anh “Nghiên cứu ứng dụng biểu đồ EXIT giải mã lặp.” 24                         2 22 2 2 exp 2 1 A A A A x xXp      (7) Khi đó, IA trong (6) có thể được viết là:                                     de x I A A A AA 1log 2 2 exp 2 1 1 22 22 (8) Biểu thức (8) có thể giải bằng phương pháp tích phân số, hoặc phương pháp gần đúng [11,12]. Tương tự, theo (6), thông tin tương hỗ  EXI ; được xác định là:           de xepxep xep xepEXII Ee x E       1 2 11 2 log 2 1 ; (9) Khi đó, đồ thị của  EXI ; theo  AXI ; được gọi là đường cong EXIT đối với mã thành phần C, ký hiệu là:  0, NEIFI bAE  . Với mỗi giá trị 0NEb xác định thì đường cong EXIT mới sẽ được tạo ra. Thực tế vì mã Turbo sử dụng các mã thành phần giống nhau cho nên các đường cong EXIT của bộ giải mã 1 và bộ giải mã 2 sẽ đối xứng với nhau. Như vậy, biểu đồ EXIT sẽ là biểu đồ tập hợp hai đường cong EXIT thể hiện đặc tính truyền đạt của hai bộ giải mã thành phần sử dụng trong bộ giải mã Turbo. Hình 3. Biểu đồ EXIT với mã turbo, độ dài ghép xen=10000. Hình 4. Hiệu năng BER của mã turbo, (Gr,G)=(7,5) [17]. Hình 3 cho thấy biểu đồ EXIT của hai bộ giải mã thành phần tại giá trị 0NEb =0,8 dB. Đường màu xanh, màu đỏ thể hiện đặc tính truyền đạt của bộ giải mã 1 và 2, tạo thành một đường hầm mở (open tunnel) đến điểm (1,1) còn đường bậc thang thể hiện quỹ đạo giải mã lặp (6 vòng lặp). Như vậy, qua biểu đồ EXIT chúng ta quan sát được toàn bộ quá trình giải mã lặp. Với 0 1 AI tại thời điểm khởi tạo. Trong trường hợp này, bộ giải mã 1 tạo ra thông tin ngoại lai E1 với thông tin tương hỗ 0 1 EI . Điều này cung cấp thông tin Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 39, 10 - 2015 25 ngoại lai A2 có thông tin tương hỗ 2A I đưa vào bộ giải mã 2, sau đó bộ giải mã 2 tạo ra thông tin ngoại lai E2 có thông tin tương hỗ 2E I , được đưa đến làm đầu vào A1 của bộ giải mã 1 tại vòng lặp tiếp theo. Đồng thời, chúng ta hoàn toàn có thể xác định được số vòng lặp tối thiểu cần thiết để bộ giải mã Turbo hội tụ tại một giá trị 0NEb nào đó. Điều này hoàn toàn phù hợp với so với đường cong BER trong hình 4 [17]: giá trị 0NEb =0,8 dB được sử dụng trong hình 3 nằm ngoài vùng dốc. Quan sát thêm hình 5, là biểu đồ EXIT được vẽ tại giá trị 0NEb =0,2 dB, cho thấy khi đường hầm mở càng hẹp thì sẽ càng cần nhiều vòng giải mã lặp hơn để tới được điểm hội tụ (1,1). Hay nói cách khác, để tiếp cận được đến gần dung lượng (near-capacity) (tại các giá trị 0NEb thấp) thì độ phức tạp cũng sẽ tăng cao. Hình 5. Biểu đồ EXIT với mã turbo (Gr,G) độ dài ghép xen=10000. Hình 6. Biểu đồ EXIT với mã turbo tại 0NEb =-0,7 dB. Một trường hợp khác thể hiện quá trình giải mã bị tắc tại điểm cắt của các đường cong EXIT trong biểu đồ EXIT với giá trị 0NEb =-0,7 dB (hình 6), tức là không có “đường hầm mở’’ (open tunnel) để đi tới điểm (1,1). Điều này hoàn toàn phù hợp với Hình 4, vì giá trị 0NEb này nằm trước vùng dốc (vùng không hội tụ). Như vậy, tại giá trị 0NEb mà đường hầm vừa đủ mở chính là khi chúng ta kỳ vọng giải mã lặp bắt đầu và cho chúng ta một ước lượng tốt về điểm bắt đầu vùng dốc của đường cong BER đối với mã turbo có độ dài ghép xen đủ lớn.Khi đó 0NEb này sẽ được xem như là ngưỡng giải mã. Hình 7. Biểu đồ EXIT với mã turbo, độ dài ghép xen=1000. Hình 8. Biểu đồ EXIT với mã turbo, độ dài ghép xen=100. Một số kết quả khác được chúng tôi thực hiện với biểu đồ EXIT đó là xem xét cho các trường hợp sử dụng bộ ghép xen với các độ dài khác nhau, nhưng tại cùng một giá trị Kỹ thuật điều khiển & Điện tử N. T. Hiên, L.N. Thăng, N.T. Anh “Nghiên cứu ứng dụng biểu đồ EXIT giải mã lặp.” 26 0NEb =0,8dB (hình 7,8). Kết hợp cùng với hình 3, chúng tôi nhận thấy quỹ đạo giải mã của bộ giải mã lặp cũng thay đổi, cụ thể khi giảm độ dài của bộ ghép xen xuống là 100 thì quỹ đạo giải mã càng cách xa hai đường cong EXIT của hai bộ giải mã thành phần, đồng thời số vòng lặp để đạt đến điểm (1,1) cũng tăng. Điều này cho thấy tính chính xác của dự đoán biểu đồ EXIT sẽ chịu ảnh hưởng đến mức nào khi độ dài bộ ghép xen không đủ lớn. Lý giải cho điều này là do khi bộ ghép xen không đủ lớn đồng nghĩa với việc các giá trị LLR không còn tuân theo phân bố Gauss, tức điều kiện 2 đặt ra ở trên không còn được thỏa mãn. Một ưu điểm khác nữa của biều đồ EXIT mà chúng tôi không đề cập đến trong bài báo này là việc ứng dụng biểu đồ EXIT để tính toán BER. Đây cũng là phần nội dung có thể mở rộng khi chúng ta có các mô hình kênh khác nhau dựa trên các kết quả tính toán trong [12] đối với kênh AWGN và Rayleigh. Tóm lại, qua các phân tích ở trên, chúng tôi nhận thấy các kết quả có được hoàn toàn phù hợp với các nghiên cứu của các tác giả trong các bài báo đã khảo sát. Đồng thời, minh chứng rõ ràng hơn về ưu điểm nổi bật của cách tiếp cận biểu đồ EXIT, hiệu quả và đơn giản hơn rất nhiều so với cách mô phỏng thông thường như mô phỏng Monte-Carlo, cần thực hiện các mô phỏng vét cạn của giải mã turbo để tính toán BER. Đồng thời hai tiêu chí đường hầm mở và vùng diện tích giữa hai đường cong EXIT của biểu đồ EXIT là cơ sở để lựa chọn các mã thành phần tốt nhất cho các hệ thống mã hóa móc nối giải mã lặp, đáp ứng được vấn đề thiết kế hệ thống truyền thông tin. 4. KẾT LUẬN Đối với một hệ thống truyền tin, để đạt được BER thấp tại các giá trị SNR gần với dung lượng kênh, thì mã hóa kênh và giải mã lặp là rất cần thiết. Biểu đồ EXIT được đề xuất là công cụ bán phân tích mạnh trong việc phân tích tính hội tụ của các hệ thống giải mã lặp. Bài báo này đã đưa ra một số kết quả đạt được khi ứng dụng biểu đồ EXIT trong việc phân tích và thiết kế hệ thống giải mã lặp. Qua đó chúng tôi sẽ mở rộng và tiếp tục nghiên cứu ứng dụng công cụ này để thiết kế mã kênh trong các hệ thống truyền thông tầng bình lưu có mô hình kênh truyền phức tạp hơn. TÀI LIỆU THAM KHẢO [1]. C. E. Shannon, “A mathematical theory of communication,” Bell Systems Technical Journal, vol. 27, pp. 623–656, October 1948. [2]. L. Hanzo, T.H. Liew, B.L. Yeap, R.Y.S. Tee, S.X. Ng, “Turbo Coding, Turbo Equalisation and Space-Time Coding: EXIT-Chart-Aided Near-Capacity Designs for Wireless Channels,” Second Edition. John Wiley& Sons - IEEE Press, 2011. [3]. R.W. Hamming, “Error detecting and error correcting codes,” Bell Systems Tech. Journal, vol. 29, pp. 41–56, 1950. [4]. P. Elias, “Coding for noisy channels,” IRE Conv. Rept., pp. 37–47, 1955. [5]. J. Wozencraft, “Sequential decoding for reliable communications,” IRENat. Conv. Rec., vol. 5, pp. 11–25, 1957. [6]. R. Fano, “A heuristic discussion of probabilistic decoding,” IEEE Trans. Inf. Theory, vol. 9, pp. 64–74, April 1963. [7]. G. Forney, “The Viterbi algorithm,” Proc. IEEE, vol. 61, pp. 268–278, march 1973. [8]. G. Forney, “Concatenated codes,” Cambridge: MIT Press, 1966. [9]. C. Berrou, A. Glavieux and P. Thitimajshima, “Near Shannon limit error- correcting coding and decoding: Turbo-codes. 1,” in IEEE International Conference on Communications, vol. 2, (Geneva), pp. 1064-1070, May 1993. Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 39, 10 - 2015 27 [10]. S. Benedetto and G. Montorsi, “Serial concatenation of block and convolutional codes,” Electronics Letters, vol. 32, pp. 887–888, May 1996. [11]. S. ten Brink, “Designing iterative decoding schemes with the extrinsic information transfer chart,” AE ă U International Journal of Electronics and Communications, vol. 54, pp. 389–398, November 2000. [12]. S. ten Brink, “Convergence behavior of iteratively decoded parallel concatenated codes,” IEEE Trans. Commun., vol. 49, no. 10, pp. 1727-1737, 2001. [13]. S. Ten Brink, “Design of serially concatenated codes based on iterative decoding convergence,” in Proc. 2nd International Symposium on Turbo Codes and Related Topics , (Brest, France), pp. 319–322, September 2000. [14]. S. ten Brink, “Convergence of iterative decoding,” Electronics Letters, vol. 35, no. 13, pp. 1117–1119, 1999. [15]. J. Hagenauer, “The EXIT chart - introduction to extrinsic information transfer in iterative processing,” in European Signal Processing Conference, (Vienna, Austria), pp. 1541–1548, September 2004. [16]. S.J. Johnson, “Iterative Error Correction: Turbo, Low-Density Parity-Check and Repeat-Accumulate Codes,” Cambridge University Press, November 2009. [17]. Upamanyu Madhow, “Fundamentals of Digital Communication,” Cambridge University Press (2008). [18]. T.M. Cover and J.A. Thomas, “Elements of information theory,” New York: Wiley, 1991. ABSTRACT THE APPLICATION OF EXIT CHART FOR ANALYSING AND DESIGNING ITERATIVELY DECODED SYSTEMS In this paper, the application of EXIT chart for anlysing and designing iteratively decoded systems is investigated. It is a powerful semi-analytical tool to describe the flow of extrinsic information between two constituent decoders. The EXIT charts offer a simple and robust graphical description of the turbo decoding process and are used to predict the SNR value corresponding to when a channel turbo decoder starts to converge, i.e., the start of the (turbo) waterfall region. The EXIT charts enable quick evaluation of the effects that the design parameters (constituent encoders, used decoding algorithms, etc.) have on the overall system performance. One of the main advantages of using EXIT charts is that the two constituent decoders can be analyzed separately and the two results are then combined to obtain the overall performance picture. Keywords: Forward Error Correction, Turbo code, Iterative decoding, EXIT chart. Nhận bài ngày 22 tháng 5 năm 2015 Hoàn thiện ngày 12 tháng 6 năm 2015 Chấp nhận đăng ngày 22 tháng 10 năm 2015 Địa chỉ: 1 Học viện Công nghệ bưu chính viễn thông; 2 Đại học Bách khoa Hà Nội. * Email: hiennt@ptit.edu.vn.