Tài liệu Thiết Kế Modul Mã hoá và Giải mã Mã Chập

  • Số trang: 59 |
  • Loại file: PDF |
  • Lượt xem: 791 |
  • Lượt tải: 0
xomthong

Tham gia: 05/05/2016

Mô tả:

LỜI MỞ ĐẦU Mã hoá và giải mã đã xuất hiện từ rất sớm đặc biệt là trong quân sự. Các yêu cầu với một loại mã là phải có tính bảo mật cao, khả năng phát hiện và sửa lỗi trong qua trình truyền. Để tìm ra được một loại mã thực sự hiệu quả là không đơn giản. Trong các loại mã mã chập ra đời từ những năm 1955 cùng thời với nhiều loại mã như mã vòng, mã BCH... Mã chập là loại mã có khả năng khôi phục dữ liệu rất tốt, song khi mới ra đời do chưa tìm được giải thuật giải mã khả thi nên ít được quan tâm. Mãi đến năm 1967 Viterbi đã đưa ra một giải thuật giải mã tối ưu gọi là giải thuật Viterbi. Với giải thuật Viterbi cùng với sự tiến bộ KHKT với công nghệ sản xuất các mạch tổ hợp cỡ lớn và sự phát triển của công nghệ sản xuất bộ nhớ, mã chập ngày càng được ứng dụng rộng rãi trong công nghệ viễn thông. Mặc dù đã xuất hiện từ rất lâu song mã hoá vẫn là một môn học khá mới. Với mong muốn tạo một bộ thí nghiệm về mã hoá và giải mã phục vụ cho việc học tập, đề tài : nghiên cứu “ Thiết Kế Modul Mã hoá và Giải mã Mã Chập“. Nội dung của đề tài là nghiên cứu và hiện thực thuật toán mã hoá mã chập và giải thuật giải mã của Viterbi. Mặc dù có nhiều cố gắng, nhưng do kiến thức hạn chế và thời gian thực hiện đề tài không nhiều nên đề tài vẫn còn nhiều hạn chế và sai sót. Em rất mong nhận được sự đánh giá nhận xét của các thầy giáo và các bạn. Nhân đây em muốn nói lời cảm ơn sâu sắc tới các thầy giáo trong khoa đặc biệt là thầy giáo hướng dẫn Ths Nguyễn Phương Lâm đã nhiệt tình quan tâm và giúp đỡ em hoàn thành đồ án. Đồng thời em cũng muốn gửi lời cảm ơn tới gia đình và các bạn đã động viên, giúp đỡ em trong quá trình hoàn thành đồ án tốt nghiệp. Hải Phòng, ngày 9 tháng 12 năm 2008 Sinh viên : Vũ Xuân Hiệp 1 Chương I. TỔNG QUAN VỀ MÃ HOÁ I.1. CÁC KHÁI NIỆM CƠ BẢN VỀ MÃ HOÁ I.1.1.Định nghĩa mã hoá Mã hoá nguồn tin X theo bộ mã M là phép ánh xạ 1:1 biến đổi một tin x i  X thành một tổ hợp các kí hiệu của bộ mã M. Nguồn X = {x1,x2,x3,...,xn} Bộ mã M = {m1,m2,...,mk} Trong đó k là cơ số của bộ mã. Nếu k=2 là mã nhị phân, k=10 là mã thập phân, k=8 là mã bát phân... Một tin xi được mã hoá thành xi  mr1mr2...mrL Trong đó L là số kí hiệu của bộ mã dùng để biểu diễn xi , đồng thời L cũng là độ dài của từ mã. Ví dụ: Ta có nguồn tin X = {x1,x2,x3,x4}. Nguồn này được mã hoá với bộ mã nhịu phân M={0,1}. Mã hoá x 1 = 00, x 2 = 01, x 3 = 11, x 1 = 10. I.1.2. Một số khái niệm cơ bản về mã hoá a) Chiều dài từ mã Chiều dài từ mã là số kí hiệu của bộ mã dùng để mã hoá cho từ mã đó. Ví dụ: từ mã 10101110 được mã hoá bằng 8 kí hiệu của bộ mã nhị phân nên có chiều dài là 8. b) Trọng lượng từ mã Trọng lượng từ mã là tổng số các kí hiệu khác 0 của từ mã. Kí hiêu: w(xi) là trọng lượng của từ mã xi Ví dụ: từ mã 01010111 có trọng lượng là 5. c)Quãng cách mã Quãng cách mã là số kí hiệu khác nhau tính theo vị trí tương ứng của 2 từ mã có chiều dài bằng nhau. Kí hiệu quãng cách mã d(x1,x2) = w(x1  x2). Trong đó  là phép toán cộng modul 2. 2 Ví dụ: có 2 từ mã x1 = 01011011, x 2 = 10101110 Quãng cách mã d(x1,x2) = 2. Quãng cách của một bộ mã được dịnh nghĩa là quãng cách mã tối thiểu của 2 từ mã bất kì của bộ mã. I.2.MỤC ĐÍCH MÃ HOÁ VÀ CÁC ĐIỀU KIỆN KHI LẬP MÃ Một số mục đích mà việc mã hoá nhằm tới ; - Phối hợp nguồn tin và nơi nhận tin - Tăng hiệu suất thông tin. - Tăng độ tin cậy truyền tin. - Bảo mật thông tin. Khi thiết lập một mã nào đơ ta cần tuân theo một số điều kiện sau: a)Điều kiện chung. Đảm vảo tính đơn trị, nghĩa là khi nhận được một dãy tín hiệu thì phải tách ra được thành từng từ mã một và phép tách này phải duy nhất. b) Điều kiện riêng. Đối với phương pháp xây dựng mã thống kê tối ưu (mã nén) thì phải làm sao cho độ dài trung bình của mã là nhỏ nhất, còn đối với mã có thể phát hiện và sửa sai thì phải cho phép phát hiện và sửa được lỗi càng nhiều càng tốt. I.3.CÁC CÁCH PHÂN LOẠI MÃ Có nhiều cách để phân loại mã, dưới đây là một số phương pháp tiêu biểu [1]: I.3.1. Phân loại theo trọng lượng của từ mã. - Mã có trọng lượng không đổi - Mã có trọng lượng thay đổi I.3.2. Phân loại theo chiều dài của từ mã. - Mã có chiều dài không đổi - Mã có chiều dài thay đổi 3 I.3.3. Phân loại theo hiệu suất thông tin - Mã tối ưu - Mã chưa tối ưu I.3.4. Phân loại theo độ tin cậy -Mã có khả năng phát hiện và sửa sai -Mã không có khả năng phát hiện và sửa sai I.3.5. Phân loại theo cơ số của bộ mã Có thể xây dựng bộ mã với cơ số bất kì, trong đó mã nhị phân là phổ biến nhất. I.3.6. Phân loại theo các cột số trong từ m ã - Mã có trọng số: Thứ tự các cột số có ảnh hưởng đến nội dung từ mã. - Mã khôg có trọng số: Thứ tự các cột số không ảnh hưởng đến nội dung từ mã. I.3.7. Phân loại theo mục đích sử dụng m ã - Mã số. - Mã kí tự. I.3.8. Phân loại theo quãng cách mã giữa hai từ mã kế cận - d  const : mã vòng. - d = const : mã Gray, mã Johnson. I.3.8. Phân loại theo cách tạo mã. Trong việc truyền tin có hai loại mã được sử dụng phổ biến là mã khối (Block Code) và mã chập (Convolutional Code). a) Mã khối Bộ mã hoá của mã khối sẽ chia dòng thông tin thành những khối tin có k bit. Mỗi tin được biẻu diễn thành một khối k thành phần nhị phân u = {u1,u2,...,uk}, u được gọi là vector thông tin. Có tổng cộng 2k vector thông tin khác nhau. Bộ mã hoá sẽ chuyển vector thông tin u thành một bộ n thành phần v = {v1,v2,...,vn }, v được gọi là từ mã.Như vậy ứng với 2k vector thông tin sẽ có 2k từ mã khác nhau. Tập hợp có 2k từ mã có chiều dài n được gọi là một mã khối (n,k). 4 Gọi R = k/n là tỉ số mã. R chính là số bít thông tin đưa vào bộ giải mã trên số bít được truyền. Do n bít ra chỉ phụ thuộc vào k bit thông tin vào nên bộ mã hoá và giải mã không có nhớ và có thể thực hiện được bằng mạch logic tổ hợp. b) Mã chập Bộ mã hoá của mã chập giống như bộ mã hoá của mã khối, cũng nhận k bít thông tin u và tạo thành từ mã v là những khối n bít. Nhưng n bít của từ mã v không chỉ phụ thuộc vào k bít thông tin mà còn phụ thuộc vào m bít thông tin trước đó. Do đó bộ mã hoá có bộ nhớ m bít. Tập hợp dòng mã hoá n bit tạo bởi k bít thông tin và m bít nhớ được gọi là mã chập (n,k,m). Tỉ số R=k/n được gọi là tốc độ lập mã. Do tính có nhớ của mã chập nên nó phải được thực hiện bằng mạch dãy. 5 CHƯƠNG II. MÃ HOÁ VÀ GIẢI MÃ MÃ CHẬP II.1.TỔNG QUAN VỀ MÃ CHẬP II.1.1.Cấu trúc bộ mã hoá Cũng giống như nhiều loại mã sửa lỗi khác, mã hoá mã chập đưa vào dòng dữ liệu một lượng dư thừa bằng cách sử dụng thanh ghi dịch tuyến tính. Sơ đồ của một bộ mã hoá mã chập được cho trong hình vẽ sau: X1 X 2 D D D D D + C1 + C2 + C3 Hình 2.1.Sơ đồ bộ mã hoá mã chập (3,2,3) Trong sơ đồ trên các có kí hiệu D biểu thị một khâu trễ. Các bít thông tin được đưa lần lượt vào thanh ghi dịch, các bít mã hoá được tạo bởi các bộ cộng modul 2 giữa bít vào và các bít lưu trong thanh ghi dịch. Đường nối giữa bộ cộng modul 2 và các bít trong thanh ghi dịch được cho bởi các đa thức sinh. II.1.2.Các tham số của bộ mã hoá mã chập Một bộ mã hoá mã chập thường được xác định thông qua các tham số (n,k,m). trong đó : n: số bít ra tại tại một thời điểm k: số bít vào bộ mã hoá tại tại một thời điểm m: độ dài lớn nhất của thanh ghi dịch. 6 Tốc độ lập mã: r k n Độ dài ràng buộc (Constrain Lenght) K. Đây là một thông số rất quan trọng của bộ mã chập. Với bộ tạo mã, độ dài ràng buộc xác định có bao nhiêu bít tại các thời điểm trước có ảnh hưởng đến bít hiện tại. Với bộ giải mã, độ dài ràng buộc xác định khi nào có thể quyết định được bít giải mã. Trong mã chập, độ dài ràng buộc càng lớn thì khả năng sửa lỗi càng tốt. Độ dài ràng buộc được tính theo biểu thức: K = m+1 Ứng với tốc độ lập mã r=1/2 ta có một số đa thức sinh [3]: Độ dài ràng buộc G1(D) G1(D) (HEX) K G2(D) G2(D) (HEX) 3 4 5 6 7 8 9 1 + D2 0x05 1 + D + D2 0x07 1 + D + D3 0x0B 1 + D + D2 + D 3 0x0F 1 + D3 + D4 0x19 1 + D + D2 + D 4 0x17 1 + D2 + D4 + D5 0x35 1 + D + D2 + D 3 + D 5 0x2F 1 + D2 + D3 + D5 + D6 0x6D 1 + D + D2 + D 3 + D 6 0x4F 1 + D2 + D5 + D6 + D7 0XE5 1 + D + D2 + D 3 + D 4 + D 7 0x9F 1 + D2 + D3 + D4 + D8 1 + D + D2 + D 3 + D 5 + D 7 + D 8 7 Với bộ mã hoá trong hình 2.1 ta có thể xác định các tham số: n = 3 , k = 2 , m = 3. Tốc độ mã r = 2/3 . Độ dài ràng buộc K = 4. II.2. CÁC PHƯƠNG PHÁP BIỂU DIỄN MÃ CHẬP Bộ mã của mã chập có thể được biểu diễn bằng các phương pháp sau: - Đồ hình trạng thái (state Diagram) - Đồ hình cây (Tree Diagram) - Đồ hình đồ hình lưới (Trellis Diagram) Ví dụ ta có sơ đồ bộ mã hoá như sau: + D C1 D MUX X1 C2 + Hình vẽ 2.2. Sơ đồ bộ mã hoá mã chập (2,1,2) II.2.1. Đồ hình trạng thái Đồ hình trạng thái của mã (2,1,2) cho trong hình 2.1 được biểu diễn như hình vẽ dưới. Các kí hiệu trong mỗi vòng tròn biểu diễn trạng thái hiện thời của thanh ghi dịch, tại mỗi thời điểm bộ mã hoá sẽ ở một trong số các trạng thái đó. Các đường nối biểu diễn sự chuyển đổi trạng thái khi có một bít vào. Các kí hiệu ghi trên các đường nối biểu diễn bít vào/ các bít ra của bộ mã hoá, ví dụ: kí hiệu 0/10 ghi trên đường nối từ trạng thái 10 đến trạng thái 01 nghĩa là khi có bít 0 vào bộ mã hoá và trạng thái thanh ghi dịch là 10 thì trạng thái của thanh ghi dịch sẽ chuyển sang 01 và cặp bít sau mã hoá là 10. 8 Hình 2.3a.Đồ hình trạng thái của bộ mã (2,1,2) Thông thường, bộ mã hoá sẽ bắt đầu từ trạng thái 0. Lấy 1 ví dụ, khi dãy bít vào bộ mã hoá là x = { 1011} (với trạng thái đầu của thanh ghi dịch là 0) thì dãy chuyển đổi trạng thái là s = {00,10,01,10,11} và dãy bít sau mã hoá là c = {11,10,00,01}. Hình dưới biểu diễn sự chuyển đổi trạng thái của bộ mã hoá với dãy bít vào cho trên (đường in đậm. Hình 2.3b. Sự chuyển trạng thái với chuỗi bit vào x = { 1011} II.2.2. Đồ hình cây. Đồ hình dạng cây biểu diễn theo thời gian tất cả các khả năng mà ta có thể đi tới theo chiều sâu của các nhánh. 9 Hình 2.4. Đồ hình cây của bộ mã hoá (2,1,2) Trong đồ hình cây, các đường nét liền biểu diễn nhánh khi có bít vào là 0, các đương nét đứt biểu diễn nhành khi có bít 1 vào. Và các bít sau mã hoá được biểu diễn ở trên mỗi nhánh cây. Với một chuỗi bít vào sẽ xác định một đường đi nhất định từ trái sang phải trên đồ hình. Ví dụ với chuỗi bít vào x = {1011} (với trạng thái đầu của thanh ghi dịch là 0) . Ta sẽ thực hiện việc dịch chuyển trên đồ hình như sau: đầu tiên tại nhánh 1 ta đi xuống, cặp bít mã hoá là 11 và trạng thái thanh ghi dịch l à 10. Tiếp theo ta thu được bít 0, do đó ta tiếp tục đi lên , cặp bít mã hoá là 10 và trạng thái thanh ghi dịch là 01. Bít thu được tiếp theo là 1, ta đi xuống, cặp bít mã hoá là 00 và trạng thái thanh ghi dịch là 10. Cuối cùng ta thu được bít 1, ta đi xuống, cặp bít mã hoá là 00 và trạng thái thanh ghi dịch l à 10. Cuối cùng chuỗi thông tin ra là: c = {11,10,00,00}. II.2.3. Đồ hình lưới Đồ hình lưới phức tạp hơn các dạng đồ hình khác, tuy nhiên nó lại được sử dụng nhiều hơn vì nó thể hiện được sự thay đổi theo thời gian của chuỗi bít vào. Đồ hình lưới biểu diễn tất cả các trạng thái chuyển đổi có thể xảy ra tại mỗi thời điểm. Trong đó 10 trục x là trục thời gian tăng dần, và trục y biểu diễn các trạng thái của bộ mã hoá. Mỗi khi thu được một bít ta sẽ dịch chuyển đến một trạng thái mới theo chiều tăng dần của trục thời gian. Đồ hình lưới dưới đây biểu diễn cho bộ tạo mã trên hình 2.1 với 4 bit vào Hình 2.5.a. Đồ hình lưới của bộ tạo mã (2,1,2) Các kí hiệu trên các đường nối có dạng (x/c), ví dụ (1/01) nghĩa là sự chuyển trạng thái đó khi có bít vào là 1 và cặp bít ra bộ mã hoá là 01. Việc tạo các bít mã hoá sử dụng đồ hình lưới rất đơn giản. Tại mỗi thời điểm khi có bít vào là 0 ta sẽ đi lên đến thời điểm tiếp, và khi thu được bít 1 ta sẽ đi xuống đến thời điểm tiếp. Giả sử có chuỗi bít vào x = {1011} ta có sự chuyển đổi trạng thái như trong hình dưới. Các đường nét đậm biểu diễn sự chuyển đổi trạng thái khi có bít vào. Hình 2.5.b.Đồ hình lưới của bộ tạo mã (2,1,2) với chuỗi bít vào 1011 11 II.3. CÁC PHƯƠNG PHÁP GIẢI MÃ MÃ CHẬP Có một số phương pháp giải mã mã chập, chúng được gộp lại thành 2 phương pháp chính: - Giải mã theo từng chuỗi (Sequential Decoding) dựa vào giải thuật của Fano - Giải mã dựa vào kết quả so sánh sự giống nhau giữa các từ mã (Maximmum Likely-hood Decoding), dựa vào giả thuật của Viterbi. Cả 2 phương pháp trên đều có chung 1 ý tưởng, được trình bày qua ví dụ sau: Giả sử ta gửi 3 bít qua bộ mã hoá với tốc độ mã ½, ta sẽ thu được 6 bít. Sau khi truyền đi, tại phía thu ta thu được 6 bít nhưng ta chưa biết 6 bít đó có bị lỗi hay không. Nếu các bít thu được có lỗi ta sẽ nhận được tổ hợp của 6 bít. Ta biết rằng với sự hoán vị của 3 bít đầu vào bộ mã hoá ta sẽ được 8 khả năng của chuỗi đầu ra và mỗi một trong số đó lại có một bản đồ mã riêng (đường đi trong đồ hình lưới). Nhiệm vụ của bộ giải mã là phải xác định chuỗi nào đã được gửi đi. Giả sử ta thu được chuỗi 111100, bây giờ ta sẽ so sánh chuỗi thu được với các chuỗi có thể được tạo ra bởi bộ mã hoá khi có 3 bit vào và xác định xem chúng khác nhau bao nhiêu bit (chính là khoảng cách Hamming giữa các từ mã). Ta có bảng sau: Chuỗi bít vào Chuỗi ra đúng từ bộ Chuỗi thu được mã hoá Khoảng cách Hamming 000 000000 111100 4 001 000011 111100 6 010 001111 111100 4 011 001100 111100 2 100 111110 111100 1 101 111101 111100 1 110 110001 111100 3 111 110010 111100 3 12 Ta thấy rằng từ mã thu được không thuộc từ mã nào trong bảng trên. Ta sẽ xác định từ mã đúng như thế nào? Ta có 2 cách : - Ta sẽ chọn 1 từ mã trong bảng trên có khoảng cách Hamming nhỏ nhất, hoặc - Ta sẽ tìm tính tương quan giữa các từ mã có thể thu được với từ mã thu được và chọn ra từ mã có tính tương quan lớn nhất là từ mã đúng. Trong thủ tục thứ nhất ta gọi là thủ tục giải mã quyết định cứng (hard decision decoding ), thủ tục thứ hai ta gọi là thủ tục giải mã quyết định mềm (soft decision decoding ). Nhưng nếu chỉ dựa vào số bít khác nhau (khoảng cách hamming) giữa chuỗi thu được và chuỗi dự đoán ta cũng chưa thể có câu trả lời chính xác ngay từ mã nào là từ mã đúng, vì trong bảng trên ta thấy có đến 2 chuỗi có cùng khoảng cách Hamming là 1. Hơn nữa khi độ dài chuỗi bít tăng thì số lượng phép tính sẽ tăng rất lớn vì thế phương pháp này sẽ không hiệu quả trong thực tế. Ta cần có 1 phương pháp khác hiệu quả hơn và cho kết qủa chính xác hơn. Nếu ta thu được bản tin có độ dài s , số khả năng của chuỗi thu đúng là 2s. Làm thế nào để xác định được bản tin đúng mà không cần phải kiểm tra 2s khả năng, đó chính là ý tưởng của thuật toán giải mã. II.3.1.Giải mã theo từng chuỗi (Sequential Decoding) Đây là 1 trong những phương pháp giải mã chập. Phương pháp này được đề xuất lần đầu bởi Wozencraft và được tối ưu bởi Fano. Phương pháp giải mã theo chuỗi được mô tả rõ nhất thông qua phương pháp loại suy. Tại mỗi thời điểm ta có nhiều nút để lựa chọn, và mỗi hướng triển khai sẽ có một giới hạn (Landmark). Nhưng khi chọn một hướng ta lại thường khó nhận ra giới hạn của nó nên nhiều khi ta đã đi sai hướng. Mỗi khi nhận thấy đã đi sai hướng ta sẽ quay trở lại điểm (nút) mà tại đó ta nhận thấy giới hạn và lặp lại qui trình trên đến khi tìm thấy hướng đi đúng. Số lần lặp lại tuỳ thuộc vào độ chính xác của mỗi hướng đi được chọn. Trong trường hợp số lỗi trong chuỗi thu ít, giải thuật này sẽ nhanh chóng cho ra chuỗi từ mã đúng. Ta dễ dàng nhận thấy được nhược điểm của phương pháp này 13 là “làm thế nào để biết được giới hạn ?”. Tuy nhiên đây lại là phương pháp khả thi tại thời điểm đó. II.3.2. Thuật toán giải mã Viterbi (VA) Thuật toán Viterbi giải mã mã chập dựa vào sự giống nhau nhất giữa các chuỗi (Maximum Likely-hood). Theo phương pháp này ta sẽ giới hạn số đường dẫn tại từng thời điểm. Nguyên tắc để giới hạn số lựa chọn là : - Các lỗi xuất hiện không có chu kì, và xác suất lỗi nhỏ. - Xác suất xuất hiện các lỗi cụm nhỏ hơn nhiều so với các lỗi đơn, các lỗi phân bố ngẫu nhiên. Giải thuật Viterbi thực hiện trên toàn bộ chuỗi thu được. Bộ giải mã sẽ tính và tạo ma trận của các đường dẫn, cơ sở của việc quyết định sẽ dựa vào ma trận này. Tất cả các đường dẫn được tính toán cho đến khi 2 đường dẫn gặp nhau. Sau đó ta sẽ giữ lại nhánh có giá trị nhỏ hơn, đồng thời loại bỏ nhánh có giá trị lớn hơn. Đường dẫn được chọn gọi là Survivors path (đường dẫn còn lại). Ta thấy với giải thuật Viterbi sẽ có một khoảng thời gian trễ để tạo ma trận các đường dẫn, và cũng cần có một bộ nhớ khá lớn_điều n ày khó có thể đáp ứng được vào những năm 1967 khi mà Viterbi đưa giả giải thuật này. Tuy nhiên điều đó sẽ tạo thuận tiện cho việc nhận ra ‘giới hạn’ của mỗi đường dẫn và thực hiện lại tại nút đó. Do có những hạn chế về mặt kĩ thuật nh ư đã kể trên mà vào thời điểm đó giải thuật giải m ã của Viterbi khó có thể triển khai trên thực tế. 14 CHƯƠNG III . THUẬT TOÁN GIẢI MÃ VITERBI III. 1. CƠ SỞ TOÁN HỌC CỦA GIẢI THUẬT VITERBI III.1.1.Thuật toán giải mã Viterbi quyết định cứng (Hard_Decison Viterbi Algorithm-HDVA) Với mã hoá mã chập, dòng bít vào là x sẽ cho chuỗi thông tin ra l à c. Chuỗi bít c sẽ được phát đi qua kênh thông tin có nhiễu và khi đến phía giải mã sẽ thu được chuỗi bit r. Nhờ tính có nhớ của mã chập nên phía giải mã có thể căn cứ vào các từ mã thu được tại các thời điểm trước đó để dự đoán ra từ mã sẽ thu được tại thời điểm hiện tại, gọi là từ mã dự đoán y. Thuật toán Viterbi sẽ đánh giá mức độ giống nhau ( Maximium Likelihood ML) giữa chuỗi dự đoán y và chuỗi thu được r dựa trên xác xuất có điều kiện p(r|y), nghĩa là xác suất thu được chuỗi r với điều kiện giải mã được chuỗi y. Chuỗi y là 1 trong số những chuỗi giải mã có thể có. Hình vẽ sau sẽ mô tả kiến trúc của hệ thống : x Convolutional Encoder c r Chanel y Viterbi Decoder Noise Hình 3.1.1. Sơ đồ hệ thống truyền tin sử dụng m ã chập. Với tốc độ mã r, số đầu vào bộ mã hoá tại một thời điểm là k bít, và đầu ra là n bít song song, chu ỗi bít vào sẽ được kí hiệu như sau: x={x0(1),x0(2),....,x0(k),x1(1),....,x1(k),...,xL+m-1(1),....,xL+m-1(k)} , chuỗi bít ra bộ mã hoá là: c={c0(1),c0(2),....,c0(n),c1(1),....,c1(n),...,cL+m-1(1),....,cL+m-1(n)} 15 trong đó L là độ dài chuỗi bít vào, m là độ dài lớn nhất của thanh ghi dịch. Các chỉ số dưới chỉ các điểm thời gian, các chỉ số tr ên chỉ số thứ tự của các bít vào- ra tại thời điểm đó. Với điều kiện đầu là có m bít ở cuối chuỗi bít vào để đưa bộ mã hoá về trạng thái toàn 0, điều đó cho phép bộ mã hoá bắt đầu và kêt thúc đều ở trạng thái 0. chuỗi thu được được mô tả như sau: r={r0(1),r0(2),....,r0(n),r1(1),....,r1(n),...,rL+m-1(1),....,rL+m-1(n)} và chuỗi sau giải mã là: y={y0(1),y0(2),....,y0(n),y1(1),....,y1(n),...,yL+m-1(1),....,yL+m-1(n)} Trong giải thuật ML, thuật toán Viterbi sẽ lựa chọn y sao cho xác suất p(r|y) lớn nhất. Giả sử kêng không có nhớ, và nhiễu tác động độc lập với các bít khác nhau. Theo lí thuyết xác suất, xác suất của sự kiện độc lập sẽ b ằng tích của các sự kiện, do đó : p (r | y )  L  m 1   p(r i 0 L  m 1 = | y i(1) ) p (ri (2) | y i(2) )... p (ri ( n) | y i( n) )  (1) i  n   p(r i 0  j 1 ( j) i  | yi( j ) )  Biểu thức trên gọi là hàm Likelihood giữa chuỗi y với điều kiện thu được chuỗi r. Việc đánh giá giá trị lớn nhất của p(r|y) t ương đương với việc đánh giá giá trị l ớn nhất của log(p(r|y) ), bởi v ì logarit là hàm đơn điệu tăng, do đó hàm Likelihood còn được định nghĩa như sau: log p( r | y)  L  m 1  i 0  n ( j) ( j)    log p( ri | y i )   j 1  Để đơn giản trong tính toán ta định nghĩa ma trận bit (bit metric) nh ư sau: M  ri ( j ) | yi( j )   a log p (ri ( j ) | yi( j ) )  b  Trong đó a và b là số nguyên dương nhỏ, giá trị của a,b được chọn theo kênh nhị phân đối xứng (BSC) hoặc theo thuật toán giải m ã quyết định cứng. Hình sau minh hoạ kênh BSC. 16 Hình 3.1.2. Mô hình kênh BSC Với kênh BSC giá trị a,b được chọn theo 2 cách khác nhau. Thôn g thường a,b được chọn như sau: a 1 log p  log(1  p) Và b   log(1  p ) Ma trận bit khi đó sẽ là: M  ri ( j ) | yi( j )   1 log p (ri ( j ) | yi( j ) )  log(1  p )  log p  log(1  p)  Trong kênh nhị phân p (ri ( j ) | yi( j ) ) chỉ có thể nhận 1 trong 2 giá trị p hoặc (1-p). Bảng sau mô tả ma trận bit theo cách thông thường : M (ri (j) | yi( j ) ) Bít giải mã Bít thu vào Bít thu vào ri ( j )  0 ri ( j )  1 0 1 1 0 yi( j )  0 Bít giải mã yi( j )  1 Ma trận bít cho ta biết giá trị (trọng số) của bít thu được và bít sau khi giải mã. Ví dụ, nếu bít giải mã là yi(j) = 0 và bít thu được là ri(j) = 0 thì giá trị sẽ là M  ri ( j ) | yi( j )   1 . Ta có nhận xét, nó có quan hệ giống như với khoảng cách Hamming 17 do đó ma trận trên còn gọi là ma trận khoảng cách Hamming. Thuật toán Viterbi s ẽ lựa chọn chuỗi mã y trong đồ hình lưới với giá trị nhỏ nhất/khoảng cách Hamming quan h ệ với chuỗi thu được r. Trong trường hợp khác a, b được định nghĩa như sau: a 1 log(1  p)  log p Và b   log p kết qua là ma trận bit sẽ như sau : M  ri ( j ) | yi( j )   1 log p (ri ( j ) | yi( j ) )  log p  log(1  p)  log p bảng sau cho thấy ma trận bit theo cách chọn này: M (ri (j) | yi( j ) ) Bít thu vào Bít thu vào ri ( j )  0 ri ( j )  1 1 0 0 1 Bít giải mã yi( j )  0 Bít giải mã yi( j )  1 Khi đó thuật toán Viterbi sẽ lựa chọn chuỗi y trong đồ hình lưới sao cho có giá trị khoảng cách Hamming lớn nhất với chuỗi r thu được. Từ ma trận bit giá trị của đường dẫn của ma trận được định nghĩa như sau: M (r | y )  L  m 1  i 0  n ( j) ( j)    M (ri | y i )   j 1  biểu thức trên chỉ ra tổng giá trị khi thu được chuỗi r và giải mã được chuỗi y trong đồ hình lưới. Giá trị nhánh ma trận thứ k được định nghĩa như sau : 18 n M (rk | yk )   M (rk j | ykj ) j 1 Và giá trị bộ phận của nhánh thứ k được định nghĩa như sau: k M k (r | y )   M (ri | y i ) i 0    M (ri ( j ) | yi( j ) )  k i 0 Nhánh ma trận thứ k chỉ ra giá trị của việc chọn nhánh đó từ đồ hình lưới. Giá trị bộ phận trong nhánh thứ k chỉ ra giá trị của việc chọn nhánh đó khi đi đến thời điểm k. Thuật toán Viterbi sử dụng đồ hình lưới để tính ma trận đường đi (Path Metric). Tại mỗi trạng thái (nút) trong đồ hình lưới ta sẽ ghi giá trị cục bộ trong nhánh đó. Giá trị cục bộ trong nhánh ma trận được định nghĩa là giá trị khi đi từ trạng thái s =0 tại thời điểm t = 0 đến trạng thái s = k tại thời điểm t >0. Tại mỗi trạng thái giá trị “tốt nhất” (nhỏ nhất/lớn nhất tuỳ vào việc chọn a,b theo cách thông thường hay cách ngược lại) được chọn từ điểm cuối của nhánh tại trạng thái đó. Tập các nhánh ma trận được chọn gọi là Survivor Path (đường dẫn còn lại) và các nhánh còn lại là Nonsurvivor Path. Survivor Path sẽ được lưu trong khi Nonsurvivor Path sẽ bị loại bỏ trong đồ hình lưới. Thuật toán Viterbi sẽ chọn các nhánh riêng rẽ về phía bên trái (theo chiều tăng của trục thời gian), kết thúc của thuật toán sẽ là ML Path (đường đi đúng). Đi ngược lại trong ML Path ta sẽ được chuỗi giải mã. Tóm lại thuật toán giải mã Viterbi quyết định cứng (HDVA) thực hiện như sau: Gọi Sk,t trong đồ hình lưới là trạng thái S k tại thời điểm t. Mỗi trạng thái trong đồ hình lưới được gán một giá trị là V(Sk,t). 1.- Khởi tạo t = 0. - Khởi tạo V(S 0,0) = 0 và các trạng thái khác V(S k,t) = +  2.- Gán t = t +1. - Tính giá trị nhánh cục bộ cho tất cả các nhánh đi từ trạng thái S k tại thời k điểm t đang xét. Đầu tiên ta tìm nhánh ma trận thứ t M (rt | yt )   M (rt ( j ) | yt( j ) ) . Nó i 0 19 n r được tính như với khoảng cách Hamming j 1 t ( j)  yt( j ) . Tiếp theo tính giá trị của t nhánh cục bộ trong nhánh t : M (r | y )   M (ri | y i ) . Nó được tính từ công thức i 0 V ( S k ,t 1 )  M (ri | yi ) . 3.-Gán giá trị V(Sk,t) bằng giá trị nhánh cục bộ “tốt nhất” khi đi từ trạng thái Sk tại thời điểm t. Thông thường giá trị “tốt nhất” của nhánh cục bộ là nhánh có giá trị nhỏ nhất. 4.Lưu giá trị “tốt nhất” của nhánh cục bộ đó, nó là 1 trong số các bít Survivor. 5. Nếu t - Xem thêm -