MỞ ĐẦU Để thuận tiện khi nghiên cứu nội dung chính là kỹ thuật điều chế mã lưới TCM trong các phần sau, chương này trình bày vắn tắt các nội dung: mã chập, thuật toán Viterbi và kênh fading Rayleigh. Mã chập [1] Như chúng ta đã biết, trong hệ thống thông tin, do sự không hoàn thiện của kênh truyền nên tại nơi thu tín hiệu sẽ bị lỗi. Mã kênh nhằm sửa lỗi mắc phải khi truyền tin trên kênh. Về cơ bản nó được chia làm 2 loại là mã khối và mã chập.
Khác với mã khối, mã chập là loại mã có nhớ, nghĩa là dữ liệu lối ra sẽ phụ thuộc dữ liệu lối vào tại thời điểm đang xét và cả dữ liệu lối vào trước đó.1 Bộ mã chập Tổng quát bộ mã chập được xây dựng từ các thanh ghi dịch và các bộ cộng môđun 2 như trong hình 1. Thanh ghi dịch là tuyến tính và có số trạng thái hữu hạn. Như trong hình 1.1, hệ thống gồm K nhịp, mỗi nhịp có k bit. Các bộ cộng môđun 2 đóng vai trò là các bộ tạo hàm đại số tuyến tính.
Thông tin nhị phân đi vào bộ mã hóa mỗi nhịp k bit, đầu ra tương ứng sẽ là n bit. Ta định nghĩa tốc độ mã hóa RC = k/n, K được gọi là độ dài ràng buộc của mã chập. Xét ví dụ một bộ mã chập như hình vẽ 1. Tại thời điểm ban đầu, dữ liệu trong thanh ghi dịch đều là bit 0.
Giả sử, bit đầu tiên của lối vào là 1 thì 3 bit lối ra sẽ là 111. Bit thứ 2 vào là 0 thì 3 bit ra tương ứng là 001. Bit lối vào thứ 3 là 1 thì 3 bit ra là 100 .2 Bộ mã chập K=3, k=1, n=3 Mỗi nhịp, một bit lối vào sẽ được lưu trong thanh ghi dịch, 2 bit còn lại xác định trạng thái của bộ mã chập. Các trạng thái được ký hiệu là a:00, b:01, c:10, d:11.
Có nhiều phương pháp để mô tả mã chập. Cách đơn giản nhất để biểu diễn mã chập là dùng biểu đồ cây mã như trong hình 1. Để thuận tiện ta quy ước, lối vào bit 0 ứng với nhánh phía trên và bit 1 được biểu diễn trong nhánh dưới. Cấu trúc cây tuy đơn giản nhưng không thuận tiện.
LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Mã chập cũng có thể biểu diễn theo các hàm tạo mã. Trong ví dụ trên, mỗi bit lối vào ta có 3 bit lối ra. Ta có 3 hàm tạo mã g1 = [100], g2 = [101], g3 = [111] ứng với lần lượt các bit lối ra 1, 2 và 3. Các bit 1 trong hàm tạo mã sẽ ứng với các bit có đường nối với bộ cộng môđun 2.
Các hàm này thường được biểu diễn ở dạng cơ số 8, trong ví dụ này là (4,5,7)8. Trong Matlab, mã chập được biểu diễn theo cách này. Ngoài 2 cách trên, ta còn có thể biểu diễn mã chập theo giản đồ lưới như trong hình 1.4 hoặc giản đồ trạng thái như trong hình 1.3 Cấu trúc cây mã của mã chập K=3, RC = 1/3 Hình 0.4 Giản đồ lưới của mã chập K=3, RC=1/3.5 Giản đồ trạng thái của mã chập K=3, RC=1/3. Trong mã chập, ta dùng hàm truyền để miêu tả mối quan hệ giữa lối vào và lối ra.
Hàm này cũng cho biết tổng các trọng số Hamming của đường tín hiệu lối ra bất kỳ so với đường toàn bit 0 bằng bao nhiêu. Định nghĩa Di với i là khoảng cách Hamming của dãy tạo ra tới dãy toàn 0. Ví dụ từ trạng thái a sang trạng thái c thì chuỗi tạo ra là 111 và do đó khoảng cách Hamming là 3, ký hiệu là D3. Từ đó ta có các phương trình trạng thái là: Xb = D.
Ứng với bước chuyển về trạng thái toàn 0 ta có: Xe = D2. Hàm truyền của mã chập được định nghĩa là: T(D) = Xe/Xa. Giải mã chập – thuật toán Viterbi Thuật toán Viterbi [2] Thuật toán Viterbi được A.Viterbi công bố vào tháng 3 năm 1967 trên tạp chí IEEE. Từ đó đến nay, thuật toán đã trở nên nổi tiếng và được ứng dụng trong nhiều lĩnh vực thuộc ngành viễn thông và công nghệ thông tin, trong đó gồm cả các hệ thống điều chế mã lưới TCM.
Sau đây là nội dung chính của thuật toán. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Xét K hàm vô hướng, giá trị thực: 0 0 , 1 1 ,. Tổng của K hàm này được xác định như sau: k 1 0 , 1,.1) i 0 Giá trị nhỏ nhất của hàm (.) được xác định là : k- 1 m = min å l i (t i ) (1.t k - 1} i= 0 Nếu các biến i là độc lập với nhau thì phương trình trên sẽ thành: k- 1 m= å min l i (t i ) (1.3) ti i= 0 Nghĩa là, cực tiểu của hàm K biến sẽ thành cực tiểu của K hàm 1 biến. Như vậy, về mặt lý thuyết ta luôn tìm được giá trị cực tiểu dù các biến là độc lập hay phụ thuộc.
Tuy nhiên, khi các biến là độc lập, số phép tính cần thực hiện là quá lớn, do đó, cần có các phương pháp khác để xác định hiệu quả hơn. Thuật toán tối thiểu hóa liên tiếp Nếu các biến 0 , 1,., K 1 không độc lập, đầu tiên ta tối thiểu hóa (.) với giả thiết là 0 độc lập, kết quả thu được khi đó sẽ phụ thuộc vào các biến 1 ,. Công việc tìm bây giờ sẽ tương đương với việc tìm hàm cực tiểu 1 ,. Tiếp theo, ta cực tiểu hóa với giả thiết i là độc lập, việc này sẽ chỉ liên quan tới 1 1 ,.
Lặp lại quá trình nhiều lần cho tới hàm K 1 độc lập, đó là phép cực tiểu hóa cuối cùng để thu được. Ta có các phương trình: {t i | t i+1 ,.,t } ë i i+ 1 k- 1 û m = min mk- 1 (t k- 1 ) {t k- 1} Thuật toán Viterbi Có thể đơn giản hóa thuật toán tối thiểu hóa liên tiếp trong công thức (1.4) nhờ việc xét cấu trúc của tập i | i 1,. Tình huống đơn giản nhất khi: i | i 1 ,.5) giá trị i nhận được không bị ảnh hưởng bởi l+1. K-1 , các biến là độc lập và khi đó phương trình (1.4) trở thành phương trình (1.
Tiếp đến, ta xem xét trường hợp đơn giản thứ 2. Ta có: LUAN VAN CHAT LUONG download : add luanvanchat@agmail.6) nghĩa là giá trị i chỉ phụ thuộc vào i+1 , và khi đó phương trình (1.7) i 1| i min K 1 K 1 K 1 Đây chính là nguyên tắc cơ bản của thuật toán Viterbi. Thuật toán Viterbi có thể giải bài toán cực tiểu hóa rất hiệu quả.6: Tạo các trạng thái của 1 thanh ghi dịch. Sau đây, ta sẽ xem xét việc áp dụng thuật toán Viterbi trong việc giải mã chập.
Quá trình giải mã này thực chất là việc tìm đường đi ngắn nhất qua lưới. Xét trường hợp tổng quát, nguồn tin tạo ra một chuỗi hữu hạn các ký hiệu độc lập là 0 , 1,. Các ký hiệu này mang một giá trị xác định trong tập M giá trị hữu hạn. Các ký hiệu này lần lượt tới một hệ thống có i lối ra.
Gọi x i là một hàm phụ thuộc lối vào hiện tại và L lối vào trước đó: xi g i , i 1 ,.8) Chuỗi x i có thể coi như được tạo ra từ một thanh ghi dịch như chỉ ra trong hình 1. Trạng thái của thanh ghi dịch tại thời điểm xuất hiện ký hiệu i thường được biểu diễn thông qua một vectơ, ký hiệu là i: i i 1 ,.9) Lối ra x i phụ thuộc vào lối vào hiện tại i và các trạng thái i của thanh ghi dịch: xi g i , i (1.10) Khi nguồn tin xuất ra ký hiệu i+1 thì thanh ghi dịch chuyển sang trạng thái i 1 i , i 1 ,. Ta định nghĩa sự chuyển đổi giữa hai trạng thái là: i 1 i , i1 (1.11) Trong giản đồ lưới, giá trị i+1 tương ứng với bước chuyển trạng thái từ i tới i+1 , và giá trị i( i) trong phương trình 1.7 thể hiện độ dài hay số đo của nhánh. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Khi đó, tập hợp các biến để (.) tối thiểu sẽ tương ứng với quãng đường có độ dài ngắn nhất trong giản đồ lưới.
Xét ví dụ giản đồ lưới trong hình 1. Các giá trị tương ứng với giản đồ là: L=2, M=2, i {-1,1} và K=5. Với 2<i<5, trạng thái i có 4 giá trị ( 1, 1).7: Giản đồ lưới ví dụ Giải mã Viterbi quyết định cứng và quyết định mềm [2] Ta định nghĩa hàm có khả năng giống nhất p(v/ui), trong đó v là chuỗi bit thu được còn ui là một trong số các chuỗi có thể phát. Bộ giải mã chọn chuỗi un nếu: p(v/un ) = max p(v/ui) , ui (1.12) Dựa vào hàm này, ta phân biệt hai phương pháp giải mã là giải mã quyết định cứng và quyết định mềm.
Giải mã Viterbi quyết định cứng Để đơn giản ta xét kênh truyền là loại đối xứng nhị phân (BSC), với xác suất có điều kiện: p(1/0))=p(0/1)=p và p(1/1)=p(0/0)=1-p. Ta dễ dàng nhận thấy rằng, trong trường hợp này p(v/u n) có giá trị cực đại khi khoảng cách Hamming giữa các từ mã là nhỏ nhất. Xét mã chập trong hình 1.8 có sơ đồ lưới được cho ở hình 1. Chú ý trong hình 1.9, các đường thẳng ứng với bit vào là 0 và các đường đứt nét ứng với bit 1.
Các số đo ở đây là khoảng cách Hamming giữa các từ mã. Với mỗi nhánh, ở thời điểm ti, ta ghi nhãn là khoảng cách Hamming. Ta định nghĩa tổng tích lũy của một đường tín hiệu ở thời điểm t i là tổng các khoảng cách Hamming của các nhánh trên đường đó. Trong ví dụ trên, tại mỗi thời điểm, 1 bit lối vào sẽ làm trạng thái của bộ mã hoá thay đổi.
Ứng với giá trị 1 và 0 của lối vào, mỗi trạng thái trong lưới có 2 trạng thái mới. Như vậy, mỗi trạng thái mới sẽ có 2 đường chuyển vị tới nó. Giải mã Viterbi sẽ tính toán các số đo và loại bỏ đường dài hơn (tổng tích luỹ lớn hơn). LUAN VAN CHAT LUONG download : add luanvanchat@agmail.8: Bộ mã chập ví dụ.9: Giản đồ lưới ví dụ.10 miêu tả 2 đường tín hiệu cùng bắt đầu từ trạng thái b tại t2 và sau 3 chu kỳ tái hợp tại trạng thái a (t5).
Ta nhận thấy đường trên có độ dài là 4 (2+1+1) và đường dưới là 1 (0+0+1). Đường trên bị loại vì Hình 0.10 Các số đo đường dẫn cho 2 đường dưới có số đo nhỏ hơn. đường hội nhập.