Đồ án Thực hiện bộ giải mã viterbi trên fpga

<< BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƢỜNG ĐẠI HỌC SƢ PHẠM KỸ THUẬT TP.HCM KHOA ĐIỆN – ĐIỆN TỬ BỘ MÔN ĐIỆN TỬ - VIỄN THÔNG ---------- ĐỒ ÁN TỐT NGHIỆP NGÀNH: CÔNG NGHỆ ĐIỆN TỬ VIỄN THÔNG Đề tài: THỰC HIỆN BỘ GIẢI MÃ VITERBI TRÊN FPGA GVHD: ThS. Lê Minh Thành KS. Đặng Phƣớc Hải Trang SVTH: Huỳnh Minh Khả MSSV: 06117029 SVTH: Lê Duy MSSV: 06117010 Thành phố Hồ Chí Minh, tháng 1 năm 2011 Thực hiện bộ giải mã Viterbi trên FPGA Trang i Phần A: Giới thiệu LỜI CẢM ƠN Cuốn đồ án tốt nghiệp đã hoàn thành đúng thời gian quy định và đạt được kết quả như mong đợi. Để đạt được kết quả đó, trước hết nhóm thực hiện muốn gửi lời biết ơn đến các bậc cha mẹ đã khổ công sinh thành dưỡng dục để tạo nên những thành viên của nhóm ngày hôm nay. Bên cạnh đó, không thể không kể đến sự tận tình giúp đỡ của các thầy cô trong bộ môn Điện tử -Viễn thông cũng như các thầy cô trong khoa Điện- Điện tử, các thầy cô đã hết mực giúp đỡ nhóm trong suốt quá trình học tập tại trường, không chỉ giáo dục nhóm về kiến thức mà còn chỉ bảo những kỹ năng sống cần thiết để nhóm có thể đứng vững trong cuộc sống tự lập sau khi ra trường. Đặc biệt, nhóm thực hiện đề tài xin chân thành cảm ơn thầy Lê Minh Thành và thầy Đặng Phước Hải Trang là những giảng viên đã trực tiếp hướng dẫn nhóm trong quá trình thực hiện đề tài. Các thầy đã tận tình giúp đỡ nhóm trong quá trình học tập tại trường và thể hiện sự quan tâm với việc đảm nhận hướng dẫn nhóm thực hiện đề tài tốt nghiệp. Một lần nữa nhóm thực hiện xin chân thành biết ơn các bậc cha mẹ và chân thành cảm ơn quý thầy cô đã tận tình giúp đỡ nhóm trong quá trình học tập tại trường. TP HCM. Ngày 1 tháng 1 năm 2011 Nhóm thực hiện đề tài Thực hiện bộ giải mã Viterbi trên FPGA Trang ii Phần A: Giới thiệu  QUYẾT ĐỊNH GIAO ĐỀ TÀI Họ và tên sinh viên: Huỳnh Minh Khả MSSV: 06117029 Lê Duy MSSV: 06117010 Ngành: Công Nghệ Điện tử - Viễn thông Tên đề tài: Thực hiện bộ giải mã Viterbi trên FPGA 1) Cơ sở ban đầu: Từ thực tiễn của việc thông tin di động và viễn thông ngày càng bùng nổ, cùng với sự đam mê trong lĩnh vực điện tử và viễn thông, nhóm thực hiện đề tài đã quyết định chọn nội dung đồ án tốt nghiệp là mô tả một thuật giải mã kênh truyền phổ biến là thuật giải Viterbi cho mã xoắn. Đây có thể xem là một sự kết hợp tốt giữa kiến thức viễn thông và chuyên ngành điện tử. 2) Nội dung các phần thuyết minh và tính toán: o Tổng quan về hệ thống thông tin số. o Mã hóa chập và thuật toán giải mã Viterbi. o Mô phỏng thuật toán giải mã Viterbi trên Matlab. o Xây dựng thuật toán giải mã Viterbi trên KIT DE2. 3) Các bản vẽ: ....................................................................................................................... ....................................................................................................................... 4) Giáo viên hướng dẫn: ThS. Lê Minh Thành KS. Đặng Phước Hải Trang 5) Ngày giao nhiệm vụ: ....../....../2010 6) Ngày hoàn thành nhiệm vụ: ....../....../2011 Giáo viên hướng dẫn Ngày ........ tháng....năm 20…. Chủ nhiệm bộ môn BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM KỸ THUẬT THÀNH PHỐ HỒ CHÍ MINH CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM Độc lập - Tự do - Hạnh phúc Thực hiện bộ giải mã Viterbi trên FPGA Trang iii Phần A: Giới thiệu NHẬN XÉT CỦA GIÁO VIÊN HƯỚNG DẪN ………………………………………………………… ……………………………………………………………… ……………………………………………………………… ……………………………………………………………… ……………………………………………………………… ……………………………………………………………… ……………………………………………………………… ……………………………………………………………… ……………………………………………………………… ……………………………………………………………… ……………………………………………………………… ……………………………………………………………… ……………………………………………………………… …………………………………………… TP Hồ Chí Minh, ngày......tháng......năm 2011 Giáo viên hướng dẫn Thực hiện bộ giải mã Viterbi trên FPGA Trang iv Phần A: Giới thiệu NHẬN XÉT CỦA GIÁO VIÊN PHẢN BIỆN ………………………………………………………… ……………………………………………………………… ……………………………………………………………… ……………………………………………………………… ……………………………………………………………… ……………………………………………………………… ……………………………………………………………… ……………………………………………………………… ……………………………………………………………… ……………………………………………………………… ……………………………………………………………… ……………………………………………………………… ……………………………………………………………… …………………………………………… TP Hồ Chí Minh, ngày......tháng......năm 2011 Giáo viên phản biện Thực hiện bộ giải mã Viterbi trên FPGA Trang v Phần A: Giới thiệu LỜI NÓI ĐẦU Cùng với sự phát triển của khoa học và công nghệ phục vụ cho cuộc sống của con người, công nghệ viễn thông trong những năm qua đã có những bước phát triển mạnh mẽ cung cấp ngày càng nhiều tiện ích cho con người. Thế kỷ 21 chứng kiến sự bùng nổ thông tin, trong đó thông tin di động đóng một vai trò rất quan trọng. Nhu cầu trao đổi thông tin ngày càng tăng cả về số lượng, chất lượng và các loại hình dịch vụ kèm theo, điều này đòi hỏi phải tìm ra phương thức trao đổi thông tin mới ngày càng ưu việt và mang lại hiệu quả cao hơn. Các công nghệ di động và viễn thông ngày một phát triển nhanh chóng để hướng tới mục đích tăng tốc độ cũng như chất lượng của các dịch vụ nhằm đáp ứng nhu cầu ngày càng cao của con người về các thiết bị không dây bỏ túi. Một trong những khâu quan trọng nhất của việc thông tin không dây đó là việc truyền và nhận tín hiệu. Điều này cần thiết phải có một loại mã hóa dành riêng cho kênh truyền có khả năng sửa chữa sai sót của tín hiệu truyền đi do các tác động của môi trường. Các hình thức được sử dụng để mã hóa kênh truyền trước đó đều có những khuyết điểm nhất định trong việc khôi phục dữ liệu bị sai sót trên đường truyền, thường chỉ có khả năng phát hiện lỗi và báo về bên phát để thực hiện truyền lại tin tức bị sai đó. Điều này làm chậm quá trình truyền tin tức. Bộ mã hóa dùng mã chập và thuật giải mã Viterbi là một chuẩn đang được ứng dụng rất rộng rãi trên toàn thế giới với nhiều ưu điểm vượt trội so với các hình thức trước đó, ngoài khả năng phát hiện lỗi tốt nhờ sự kiểm soát chặt chẽ tin tức truyền đi, nó còn có khả năng tự khôi phục các tin tức bị sai trong quá trình truyền trên kênh truyền. Điều này giúp giảm thiểu tối đa thời gian truyền nhận tin tức, do đó tốc độ dữ liệu ngày một được nâng cao. Tuy vẫn còn một số hạn chế nhất định trong việc khôi phục các đoạn tin tức sai hàng loạt, nhưng thuật toán Viterbi vẫn là sự lựa chọn ưu tiên và là nền tảng cho việc phát triển các hình thức mã hóa và giải mã tốt hơn nữa hiện tại và sau này. Vì những ưu điểm nổi bật và tính ứng dụng cao của thuật toán này trong hiện tại và tương lai của ngành viễn thông, nhóm thực hiện quyết định chọn đề tài là “Thực hiện bộ giải mã Viterbi trên FPGA”. Trong phạm vi của cuốn đồ án này, nhóm thực hiện đề tài sẽ giới thiệu khái quát về hai hình thức mã hóa và giải mã này và tiến hành mô phỏng thuật toán mã hóa và giải mã đó trên Matlab cũng như mô tả phần cứng trên kit DE2 của Altera. Nội dung của đồ án sẽ bao gồm các vấn đề sau:  Chương 1: Tổng quan về hệ thống thông tin số Thực hiện bộ giải mã Viterbi trên FPGA Trang vi Phần A: Giới thiệu Giới thiệu về vị trí vai trò của mã hóa kênh truyền trong hệ thống thông tin số, so sánh hai hình thức mã hóa là mã khối và mã trellis.  Chương 2: Thuật toán Viterbi Khái niệm và phân tích mã chập, cách thức mã hóa sử dụng mã chập, cũng như cấu trúc của bộ mã hóa chập. Giới thiêu thuật toán giải mã Viterbi, nguyên lý thực hiện giải mã và phân loại một số phương pháp giải mã.  Chương 3: Xây dựng thuật giải Viterbi dùng Matlab Tiến hành đi mô phỏng thuật toán mã hóa mã chập và thuật toán giải mã Viterbi. Phân tích thuật toán  Chương 4: Xây dựng thuật giải Viterbi trên kit DE2 Mô phỏng thuật toán thực tế hơn trên kit DE2 với các led hiển thị dữ liệu từ đó thấy được hiệu quả của thuật toán Viterbi, ứng dụng ngôn ngữ thiết kế phần cứng VHDL  Chương 5: Kết luận Đánh giá kết quả thực hiện của đồ án và đưa ra phương hướng phát triển của đề tài trong tương lai. TP HCM. Ngày … tháng … năm 2011 Nhóm thực hiện đề tài Thực hiện bộ giải mã Viterbi trên FPGA Trang vii Phần A: Giới thiệu MỤC LỤC Trang TRANG BÌA ........................................................................................................ LỜI CẢM ƠN ..................................................................................................... i QUYẾT ĐỊNH GIAO ĐỀ TÀI..........................................................................ii NHẬN XÉT CỦA GIÁO VIÊN HƢỚNG DẪN ............................................. iii NHẬN XÉT CỦA GIÁO VIÊN PHẢN BIỆN ................................................. iv LỜI NÓI ĐẦU ................................................................................................... v MỤC LỤC ....................................................................................................... vii LIỆT KÊ HÌNH ................................................................................................. x LIỆT KÊ BẢNG .............................................................................................. xii PHẦN B: NỘI DUNG ...................................................................................... 13 CHƢƠNG 1: TỔNG QUAN HỆ THỐNG THÔNG TIN SỐ ........................ 14 1.1 Vị trí của mã hóa kênh trong hệ thống thông tin số ................................ 14 1.2 Khái niệm mã hóa kênh và phân loại ..................................................... 14 1.2.1 Khái niệm ....................................................................................... 14 1.2.2 Phân loại mã hóa kênh .................................................................... 15 1.3 Khái quát về mã khối và mã trellis ........................................................ 16 1.3.1 Mã khối .......................................................................................... 16 1.3.2 Mã trellis ........................................................................................ 17 CHƢƠNG 2: THUẬT TOÁN GIẢI MÃ VITERBI....................................... 19 2.1 Khái niệm mã chập ................................................................................ 19 2.2 Phân tích mã hóa dùng mã chập ............................................................ 19 2.3 Cấu trúc mã chập ................................................................................... 23 2.4 Biểu diễn mã chập ................................................................................ 27 2.5 Ưu nhược điểm của mã chập ................................................................ 30 2.5.1 Ưu điểm ......................................................................................... 30 2.5.2 Nhược điểm.................................................................................... 30 2.6 Định nghĩa thuật toán Viterbi ................................................................ 30 2.7 Phân tích thuật giải Viterbi .................................................................... 31 2.8 Giải mã quyết định cứng và giải mã quyết định mềm ............................ 43 Thực hiện bộ giải mã Viterbi trên FPGA Trang viii Phần A: Giới thiệu 2.8.1 Thuật toán Viterbi quyết định cứng ................................................ 43 2.8.2 Thuật toán Viterbi quyết định mềm ................................................ 48 2.8.2.1 Thuật toán Viterbi quyết định mềm (phương pháp 1) .............. 48 2.8.2.2 Thuật toán Viterbi quyết định mềm (phương pháp 2) .............. 49 2.8.3 Ưu điểm của giải mã quyết định mềm so với giải mã quyết định cứng ................................................................................................................. 51 2.9 Xác suất lỗi .......................................................................................... 54 2.10 Ưu nhược điểm của thuật toán giải mã Viterbi .................................... 54 2.10.1 Ưu điểm ....................................................................................... 54 2.10.2 Nhược điểm .................................................................................. 55 CHƢƠNG 3: MÔ PHỎNG THUẬT TOÁN VITERBI TRÊN MATLAB ... 56 3.1 Giới thiệu ............................................................................................. 56 3.2 Sơ đồ khối hệ thống ............................................................................... 56 3.3 Lưu đồ mô phỏng .................................................................................. 57 3.3.1 Khối tạo bit ngõ vào ....................................................................... 57 3.3.2 Khối mã hóa ................................................................................... 58 3.3.3 Khối cộng nhiễu Gausse trắng ........................................................ 58 3.3.4 Khối giải mã ................................................................................... 58 3.3.5 Tính toán và vẽ BER ...................................................................... 59 3.4 Hình ảnh về chương trình mô phỏng ...................................................... 59 CHƢƠNG 4: XÂY DỰNG THUẬT TOÁN VITERBI TRÊN KIT DE2 ...... 65 4.1 Giới thiệu sơ lược KIT DE2 và phần mềm Quartus ............................... 65 4.1.1 KIT DE2 của Altera ........................................................................ 65 4.1.1.1 Tổng quan kit DE2 ................................................................... 65 4.1.1.2 Sử dụng nút nhấn và Switch .................................................... 67 4.1.1.3 Sử dụng LCD ........................................................................... 68 4.1.2 Phần mềm lập trình Quatus II ........................................................ 68 4.2 Giải quyết vấn đề .................................................................................. 69 4.2.1 Giải mã viterbi quyết định cứng ...................................................... 69 4.2.2 Giải mã viterbi quyết định mềm ...................................................... 73 4.3 Lưu dồ thuật toán lập trình ..................................................................... 75 4.4 Kết quả ................................................................................................. 82 Thực hiện bộ giải mã Viterbi trên FPGA Trang ix Phần A: Giới thiệu CHƢƠNG 5: KẾT LUẬN ............................................................................... 88 5.1 Tổng kết nhận xét ................................................................................... 88 5.2 Tồn tại và hướng phát triển của đề tài ..................................................... 88 PHẦN C: PHỤ LỤC VÀ TÀI LIỆU THAM KHẢO ........................................ 90 I. Phụ lục ..................................................................................................... 91 1. Hướng dẫn sử dụng kit DE2 để mô phỏng ............................................ 91 2. Tài nguyên sử dụng trên Kit DE2 ......................................................... 91 3. Mã nguồn Matlab ............................................................................... 93 4. Mã nguồn VHDL .............................................................................. 105 II. Tài liệu tham khảo ................................................................................ 123 Thực hiện bộ giải mã Viterbi trên FPGA Trang x Phần A: Giới thiệu LIỆT KÊ HÌNH Hình 1.1: Vị trí của mã hóa kênh truyền trong hệ thống thông tin số Hình 1.2: Sự phân chia mã hóa kênh thành hai nhánh riêng biệt Hình 2.1: Bộ mã hóa cho mã chập tốc độ 1/ 2R  Hình 2.2: Bộ mã hóa hệ thống với 1/ 2R  Hình 2.3: Bộ mã hóa hệ thống Hình 2.4: Sơ đồ bộ mã hóa hệ thống 2 / 3R  có phần cứng đơn giản Hình 2.5: Sơ đồ tổng quát bộ mã chập Hình 2.6: Bộ mã chập (3,2,2) Hình 2.7: Sơ đồ bộ mã chập với N=3, k=1, n=3 Hình 2.8: Sơ đồ hình cây bộ mã (2,1,3) Hình 2.9: Sơ đồ hình lưới bộ mã chập (2,1,3). Hình 2.10: Sơ đồ trạng thái của bộ mã chập (2,1,3). Hình 2.11: Bộ mã chập tốc độ ½ Hình 2.12: Đồ hình trạng thái của mã chập ½ Hình 2.13: Các nhánh trong bộ mã hóa Hình 2.14: Đường đi hoàn chỉnh khôi phục chính xác tín hiệu tại ngõ ra Hình 2.15: Tín hiệu nhận có 2 bit sai tại t =2 và t = 11 Hình 2.16: Tại thời điểm t = 1 Hình 2.17: Tại thời điểm t = 2 Hình 2.18: Tại thời điểm t = 3 Hình 2.19: Tại thời điểm t = 4 Hình 2.20: Tại thời điểm t = 5 Hình 2.21: Tất cả dữ liệu đã được giải mã và sửa sai chính xác Hình 2.22: Bộ mã tốc độ 1/3 và K= (7,7,5) Hình 2.23: Giải mã quyết định cứng và mềm Hình 2.24: Hệ thống mã tích chập Hình 2.25: Kiểu kênh hệ thống nhị phân, trong đó p là xác suất chéo Hình 2.26: Biểu diễn Viterbi theo ví dụ Hình 2.27: Mô tả giải mã quyết định cứng với bộ mã parity Hình 2.28: Mô tả giải mã quyết định mềm với bộ mã parity Hình 3.1: Sơ đồ khối hệ thống Hình 3.2: Lưu đồ mô phỏng Hình 3.3: Giao diện khởi đầu chương trình mô phỏng Hình 3.4: Giao diện chương trình mô phỏng 1 Hình 3.5: Giao diện chương trình mô phỏng 2 Hình 3.6: Nhập bit ngẫu nhiên – Quyết định mềm Hình 3.7: BER của quyết định mềm Thực hiện bộ giải mã Viterbi trên FPGA Trang xi Phần A: Giới thiệu Hình 3.8: Nhập bit ngẫu nhiên – Quyết định cứng Hình 3.9: BER của quyết định cứng Hình 3.10: So sánh BER của cả quyết định cứng và mềm Hình 3.11: Tự nhập bit vào – Quyết định mềm Hình 4.1: KIT DE2 của Altera Hình 4.2: Sơ đồ khối KIT DE2 Hình 4.3: Chống dội phím nhấn Hình 4.4: Tính toán metric nhánh và metric đường cho bộ giải mã Viterbi Hình 4.5: Lưu đồ giải thuật chính của chương trình Hình 4.6: Lưu đồ giải thuật bộ giải mã Hình 4.7: Lưu đồ chi tiết giải thuật giải mã viterbi tren Kit DE2 Hình 4.8: Lưu đồ tính khoảng cách Hamming Hình 4.9: Lưu đồ giải thuật tính khoảng cách Euclidean Hình 4.10: Lưu đồ khối tính khoảng cách nhánh Hình 4.11: Lưu đồ khối ACS Hình 4.12: Lưu đồ khối truy hồi Hình 4.13: Lưu đồ khối giải mã Hình 4.14: Kết quả mô phỏng 1 Hình 4.15: Kết quả mô phỏng 2 Hình 4.16: Kết quả mô phỏng 3 Hình 4.17: Kết quả mô phỏng 4 Hình 4.18: Kết quả mô phỏng 5 Hình 4.19: Kết quả mô phỏng 6 Hình 4.20: Mô phỏng trên Matlab Hình 4.21: Hình thực tế bộ kit 1 Hình 4.22: Hình thực tế bộ kit 2 Hình 4.23: Hình thực tế bộ kit 3 Thực hiện bộ giải mã Viterbi trên FPGA Trang xii Phần A: Giới thiệu LIỆT KÊ BẢNG Bảng 2.1: Trạng thái ngõ vào và ngõ ra của bộ mã hóa tốc độ ½ Bảng 2.2: Bảng ma trận tích lũy của cả 8 bit của bản tin Bảng 2.3: Bảng lịch sử trạng thái (state history table) Bảng 2.4: Bảng các trạng thái được lựa chọn khi truy hồi Bảng 2.5: Bảng trạng thái kế tiếp (next state table) Bảng 2.6: Bảng chứa các dữ liệu của bản tin gốc đã được khôi phục Bảng 2.7: Ví dụ về punctured code Bảng 2.8: Các giá trị metric bit thông thường Bảng 2.9: Các giá trị metric bit cách 2 Bảng 2.10: Ví dụ với bộ mã parity Bảng 2.11: Tính toán khoảng cách Hamming cho quyết định cứng Bảng 2.12: Tính toán khoảng cách Euclidean cho quyết định mềm Bảng 4.1: Thứ tự kết nối phím nhấn với các chân của FPGA Bảng 4.2: Gán chân FPGA cho màn hình LCD Bảng 4.3: Trạng thái hiện tại và trạng thái trước của nó Bảng 4.4: Bảng trạng thái tiếp theo PHẦN B NỘI DUNG Thực hiện bộ giải mã Viterbi trên FPGA Trang 14 Chương 1: Tổng quan về hệ thống thông tin số CHƢƠNG 1 TỔNG QUAN VỀ HỆ THỐNG THÔNG TIN SỐ 1.1 Vị trí của mã hóa kênh trong hệ thống thông tin số Mã hóa kênh là một khâu rất quan trọng trong hệ thống thông tin số không dây cùng với mã hóa nguồn, ghép kênh, điều chế,… để tạo ra một tín hiệu phù hợp cho việc truyền dẫn vô tuyến và tín hiệu đó có khả năng điều khiển được sự sai bit và sửa các lỗi xảy ra nếu có để có thể khôi phục lại gần như nguyên dạng tín hiệu tin tức mà mình truyền đi. Hình 1.1: Vị trí của mã hóa kênh truyền trong hệ thống thông tin số Mã hoá kênh: mục đích là làm giảm xác suất sai thông tin khi truyền qua kênh truyền. Việc giảm thiểu xác suất sai dựa việc phát hiện sai và sửa sai có thể dẫn đến việc giảm tỉ số tín hiệu trên nhiễu (SNR) cần thiết nhờ đó giảm được công suất, tiết kiệm năng lượng. Việc sửa sai hữu hiệu cho tín hiệu SNR nhỏ sẽ thuận lợi cho việc bảo mật, trải phổ và tăng độ chính xác của thông tin nhận- mục đích quan trọng nhất của truyền thông. 1.2 Khái niệm mã hóa kênh và phân loại 1.2.1 Khái niệm Mã hóa kênh là việc đưa thêm các bit dư vào tín hiệu số theo một quy luật nào đấy, nhằm giúp cho bên thu có thể phát hiện và thậm chí sửa được cả lỗi xảy ra trên kênh truyền. Thực hiện bộ giải mã Viterbi trên FPGA Trang 15 Chương 1: Tổng quan về hệ thống thông tin số Một số hệ thống có thể khắc phục lỗi bằng cách gởi một yêu cầu cho bên phát gửi lại tín hiệu nếu phát hiện lỗi, đó là chế độ ARQ. Nhưng việc này chỉ thích hợp cho các hệ thống truyền dẫn hữu tuyến và một số hệ thống vô tuyến không yêu cầu vể thời gian trễ. Thay vào đó, với các hệ thống thông tin không dây ngày nay, người ta hay sử dụng một loại mã có thể phát hiện và khắc phục lỗi một cách tự động. Việc này giảm thiểu thời gian trể so với các hệ thống yêu cầu truyền lại. Bộ mã này thường được gọi là mã điều khiển lỗi (ECC), hay chính xác hơn là FEC. Mục đích của lý thuyết Mã hóa trên kênh truyền là tìm những mã có thể truyền thông nhanh chóng, chứa đựng nhiều từ mã tự hợp lệ và có thể sửa lỗi hoặc ít nhất phát hiện các lỗi xảy ra. Các mục đích trên không phụ thuộc vào nhau, và mỗi loại mã có công dụng tối ưu cho một ứng dụng riêng biệt. Những đặc tính mà mỗi loại mã này cần còn tuỳ thuộc nhiều vào xác suất lỗi xảy ra trong quá trình truyền thông. Đối với một đĩa CD thông thường, lỗi trong âm thanh xảy ra chủ yếu là do bụi và những vết xước trên mặt đĩa. Vì thế, các mã được lồng vào với nhau. Dữ liệu được phân bổ trên toàn bộ mặt đĩa. Tuy không được tốt cho lắm, song một mã tái diễn đơn giản có thể được dùng làm một ví dụ dễ hiểu. Chẳng hạn, chúng ta lấy một khối số liệu bit (đại diện cho âm thanh) và truyền gửi chúng ba lần liền. Bên máy thu, chúng ta kiểm tra cả ba phần lặp lại ở trên, từng bit từng bit một, rồi lấy cái nào có số bầu cao nhất. Điểm khác biệt ở đây là, chúng ta không chỉ truyền gửi các bit theo thứ tự. Chúng ta lồng nó vào với nhau. Khối dữ liệu này, trước tiên, được chia ra làm 4 khối nhỏ. Sau đó chúng ta gửi một bit ở khối đầu tiên, tiếp theo một bit ở khối thứ hai v.v tuần tự qua các khối. Việc này được lặp đi lặp lại ba lần để phân bổ số liệu ra trên bề mặt đĩa. Trong ngữ cảnh của mã tái diễn đơn giản ở trên, việc làm này hình như không được hiệu quả cho lắm. Song hiện nay có những mã có hiệu ứng cao, rất phù hợp với việc sửa lỗi xảy ra đột ngột do một vết xước hay một vết bụi, khi dùng kỹ thuật lồng số liệu nói trên. Mỗi mã thường chỉ thích hợp cho một ứng dụng nhất định. Viễn thông trong vũ trụ bị giới hạn bởi nhiễu nhiệt trong thiết bị thu. Hiện trạng này không xảy ra một cách đột phát bất thường, song xảy ra theo một chu trình tiếp diễn. Tương tự như vậy, modem với dải tần hẹp bị hạn chế vì nhiễu âm tồn tại trong mạng lưới điện thoại. Những nhiễu âm này có thể được biểu hiện rõ hơn bằng một mô hình tạp âm tiếp diễn. Điện thoại di động hay có vấn đề do sự suy sóng nhanh chóng xảy ra. Tần số cao được dùng có thể gây ra sự suy sóng tín hiệu một cách nhanh chóng, ngay cả khi máy nhận chỉ dời chỗ vài phân Anh. Một lần nữa, người ta hiện đã có một loại mã hóa trên kênh truyền được thiết kế để đối đầu với tình trạng suy sóng. 1.2.2 Phân loại mã hóa kênh Lý thuyết mã hóa đại số được chia ra làm 2 loại mã chính 1. Mã khối. Thực hiện bộ giải mã Viterbi trên FPGA Trang 16 Chương 1: Tổng quan về hệ thống thông tin số 2. Mã trellis. Chúng phân tích ba đặc tính sau của mã (nói chung) là:  Chiều dài của mã.  Tổng số các từ mã hợp lệ.  Khoảng cách Hamming tối thiểu giữa hai từ mã hợp lệ. Hình 1.2: Sự phân chia mã hóa kênh thành hai nhánh riêng biệt Trong mỗi loại mã lại được phân tách thành 2 nhánh nữa đó là mã tuyến tính và mã không tuyến tính. Thường thì các mã không tuyến tính không được ứng dụng trong thực tế vì các nhược điểm của nó, nên ở đây chúng ta chỉ đề cập đến các mã tuyến tính. Trong phần tiếp theo chúng ta sẽ khái quát sơ lược về mã khối và mã trellis. 1.3 Khái quát về mã khối và mã trellis 1.3.1 Mã khối Mã khối tuyến tính mang tính năng tuyến tính, chẳng hạn tổng của hai từ mã nào đấy lại chính là một từ mã; và chúng được ứng dụng vào các bit của nguồn trên từng khối một; cái tên mã khối tuyến tính là vì vậy. Có những khối mã bất tuyến tính, song khó mà chứng minh được rằng một mã nào đó là một mã tốt nếu mã ấy không có đặc tính này. Bất cứ mã khối tuyến tính nào cũng được đại diện là (n,m,dmin), trong đó 1. n, là chiều dài của từ mã, trong ký hiệu, 2. m, là số ký hiệu nguồn được dùng để mã hóa tức thời, Thực hiện bộ giải mã Viterbi trên FPGA Trang 17 Chương 1: Tổng quan về hệ thống thông tin số 3. dmin, là khoảng cách hamming tối thiểu của mã. Có nhiều loại mã khối tuyến tính, như 1. Mã vòng (Mã Hamming là một bộ phận nhỏ của mã tuần hoàn). 2. Mã chẵn lẻ. 3. Mã Reed-Solomon. 4. Mã BCH. 5. Mã Reed-Muller. 6. Mã hoàn hảo. Mã khối được gắn liền với bài toán “đóng gói đồng xu” là bài toán gây một số chú ý trong nhiều năm qua. Trên bề diện hai chiều, chúng ta có thể hình dung được vấn đề một cách dễ dàng. Lấy một nắm đồng xu, để nằm trên mặt bàn, rồi dồn chúng lại gần với nhau. Kết quả cho chúng ta một mẫu hình lục giác tương tự như hình tổ ong. Các mã khối còn dựa vào nhiều chiều khác nữa, không dễ gì mà hình dung được. Mã Golay có hiệu ứng cao, dùng trong truyền thông qua khoảng không vũ trụ, sử dụng những 24 chiều. Nếu được dùng là mã nhị phân (thường thấy), các chiều ám chỉ đến chiều dài của từ mã như đã định nghĩa ở trên. 1.3.2 Mã trellis Mã trellis hay còn gọi là mã chập (kết hợp) được sử dụng trong các modem dải tần âm (V.32, V.17, V.34) và trong các điện thoại di động GSM, cũng như trong các thiết bị truyền thông của quân đội vũ trang và trong các thiết bị truyền thông với vệ tinh. Mục đích của việc tạo ra mã chập là nhằm làm cho tất cả các ký hiệu từ mã trở thành tổng trọng số của nhiều loại ký hiệu thông điệp trong nhập liệu. Nó tương tự như toán kết hợp được dùng trong các hệ tuyến tính bất biến để dùng tìm xuất liệu của một hệ thống, khi chúng ta biết nhập liệu và các đáp ứng xung. Nói chung chúng ta tìm xuất liệu của bộ mã chập hệ thống, tức sự kết hợp của nhập liệu bit, đối chiếu với trạng thái của bộ mã hóa kết hợp, hoặc trạng thái của các thanh ghi. Về cơ bản mà nói, mã chập không giúp thêm gì trong việc chống nhiễu hơn một mã khối tương ứng. Trong nhiều trường hợp, chúng nói chung cho chúng ta một phương pháp thực thi đơn giản hơn, hơn hẳn một mã khối có hiệu quả tương ứng. Bộ mã hóa thường là một mạch điện đơn giản, có một bộ nhớ, một vài biện pháp truyền thông tin phản hồi báo tình hình, thường là các cổng loại trừ XOR. Bộ mã hóa có thể được thực thi trong phần mềm hay phần sụn. Thuật toán Viterbi là một thuật toán tối ưu nhất được dùng để giải mã các mã chập. Hiện có những phương pháp giảm ước giúp vào việc giảm khối lượng tính Thực hiện bộ giải mã Viterbi trên FPGA Trang 18 Chương 1: Tổng quan về hệ thống thông tin số toán phải làm. Những phương pháp này phần lớn dựa vào việc tìm tuyến đường có khả năng xảy ra cao nhất. Tuy không ngắn gọn, song trong môi trường nhiễu thấp hơn, người ta thường thấy chúng cho những kết quả khả quan. Các bộ điều hành vi xử lý hiện đại có khả năng thực hiện những thuật toán tìm giảm ước nói trên với tỷ lệ trên 4000 từ mã trong một giây. Đề tài chủ yếu nghiên cứu về thuật toán giải mã Viterbi để thấy được ưu điểm của thuật toán trong việc giảm tối thiểu sai số khi mã hóa và giải mã tín hiệu. Do đó, trong các phần tiếp theo của đồ án, chúng ta chỉ tìm hiểu việc mã hóa tin tức dùng mã chập và giải mã dựa trên thuật toán Viterbi cũng như những ưu khuyết điểm của chúng. Đồng thời ta tiến hành mô phỏng thuật toán trên Matlab và trên Kit FPGA để kiểm chứng thực tế hơn. Còn đối với các mã trellis còn lại thì ta sẽ không phân tích trong phạm vi cuốn đồ án này. Thực hiện bộ giải mã Viterbi trên FPGA Trang 19 Chương 2: Thuật giải mã Viterbi CHƢƠNG 2 THUẬT GIẢI MÃ VITERBI 2.1 Khái niệm mã chập Mã chập là một kỹ thuật mã hóa sửa sai. Mã chập thuộc họ mã lưới (mã hóa theo Trellis) và được xây dựng dựa trên một đa thức sinh hoặc một sơ đồ chuyển trạng thái (trellis mã) đặc trưng. Quá trình giải mã của mã chập phải dựa vào trellis mã thông qua các giải thuật khác nhau, trong đó nổi tiếng nhất là giải thuật Viterbi. Tại sao gọi là mã chập vì cấu trúc mã hóa có thể biểu diễn dưới dạng phép tính chập giữa đa thức sinh mã và chuỗi tín hiệu được mã hóa. Mã hóa chập và thuật toán giải mã Viterbi được sử dụng trong khoảng hơn một tỉ điện thoại, có thể là lớn nhất trong các loại thuật toán được ứng dụng. Tuy nhiên, hiện tại thì thuật toán xử lý viterbi được ứng dụng nhiều nhất trong các thiết bị âm thanh và hình ảnh kỹ thuật số. Ngày nay, chúng còn được sử dụng trong các thiết bị bluetooth. Mục đích của mã hóa kênh truyền là nhằm tăng dung lượng kênh truyền, bằng cách cộng thêm vào tín hiệu những dữ liệu dư thừa được thiết kế một cách cẩn thận trước khi truyền lên kênh truyền. Mã hóa chập và mã hóa khối là 2 dạng chính của mã hóa kênh truyền. Mã hóa chập thì dựa trên dữ liệu nối tiếp, 2 hoặc một vài bit được truyền một lúc, còn mã hóa khối thì dựa trên một khối dữ liệu lớn tương quan (đặc trưng là khoảng vài trăm bytes). Ví dụ, mã Redsolomon là một mã hóa khối. Sự khác nhau cơ bản giữa mã hóa khối và mã hóa chập là mã hóa khối là mã hóa không nhớ. Cho một chuỗi dữ liệu K bit, thì ngõ ra của bộ mã hóa khối là một khối dữ liệu n bit duy nhất. Mã hóa chập không kết nối các khối bit riêng vào trong một khối từ mã, thay vào đó nó sẽ chấp nhận một chuỗi bit liên tục và taọ thành một chuỗi ngõ ra. Hiệu quả hay tốc độ dữ liệu của mã hóa chập được đánh giá bằng tỉ lệ của số bit ngõ vào k, và số bit ngõ ra n. Trong mã hóa chập là có một vài bộ nhớ dùng để ghi nhớ dòng bit vào. Thông tin này được sử dụng để mã hóa các bit tiếp theo. 2.2 Phân tích mã hóa dùng mã chập Mã chập là mã tuyến tính có ma trận sinh có cấu trúc sao cho phép mã hóa có thể xem như một phép lọc (hoặc lấy tổng chập). Mã chập được sử dụng rộng rãi trong thực tế. Bởi mã hóa được xem như một tập hợp các bộ lọc số tuyến tính với dãy mã là các đầu ra của bộ lọc được ghép xen kẽ. Các mã chập là các mã đầu tiên được xây dựng các thuật toán giải mã quyết định mềm hiệu quả. Mã khối từ các khối k dấu (hay ký hiệu) tạo ra các khối n dấu. Với các mã chập (thường được xem là các mã dòng), bộ mã hóa hoạt động trên dòng liên tục Thực hiện bộ giải mã Viterbi trên FPGA Trang 20 Chương 2: Thuật giải mã Viterbi các bit vào không được phân thành các khối tin rời rạc. Tuy nhiên tốc độ mã   n F X    k n được hiểu là cứ có k ngõ vào ở mỗi bước thời gian sẽ tạo ra n ngõ ra. Các phép tính số học sử dụng trong hình thức mã hóa này có thể được thực hiện trên một trường tùy ý nhưng thông thường vẫn là trên GF(2). Ta biểu thị các dãy và các hàm truyền đạt như các chuỗi lũy thừa của biến x (đôi khi còn dùng ký hiệu D thay cho x). Dãy {…,m-2, m-1, m0, m1, m2, …} (với các phần tử mi thuộc trường F) được xem như một chuỗi Laurent: ( ) ee e m X m x     Tập tất cả các chuỗi Laurent trên F là một trường, ta ký hiệu trường này là  F X   . Như vậy  ( )m X F X    Đối với dòng nhiều bit vào ta dùng ký hiệu m(1)(x) biểu thị dòng đầu vào đầu tiên, m(2)(x) biểu thị dòng đầu vào thứ hai. Tập các dòng vào xem như một vectơ: m(x) = [m (1) (x) m (2) (x)]   2 F X    Bộ mã hóa cho mã chập thường được coi là một tập các bộ lọc số. Hình 2.1 chỉ ra một ví dụ về một bộ mã hóa Hình 2.1: Bộ mã hóa cho mã chập tốc độ 1 2 R  (các ô D biểu thị các ô nhớ một bít – các trigger D) Dòng vào mk đi qua hai bộ lọc dùng chung các phần tử nhớ tạo ra hai dòng ra. C (1) k = m k + m k-1 + m k-2 và C(2)k = mk + mk-2 . Hai dòng ra này được đưa ra xen kẽ để tạo ra dòng được mã hóa Ck. Như vậy cứ mỗi bít vào lại có hai bít mã hóa được đưa ra, kết quả là ta có một mã có tốc Thực hiện bộ giải mã Viterbi trên FPGA Trang 21 Chương 2: Thuật giải mã Viterbi độ R = 1/2. Thông thường ta coi trạng thái ban đầu của các phần tử nhớ là 0. Như vậy, với dòng vào m = {1, 1, 0, 0, 1, 0, 1} các đầu ra sẽ là: C (1) = {1, 0, 0, 1, 1, 1, 0, 1, 1} và C(2)= {1, 1, 1, 1, 1, 0, 0, 0, 1} Dòng ra: C = {11, 01, 01, 11, 11, 10, 00, 10, 11} Ở đây dấu phẩy phân cách các cặp bít ra ứng với mỗi bít vào. Ta có thể biểu thị hàm truyền từ đầu vào m(x) từ đầu ra C(1)(x) như sau: g 1 (x) = 1 + x +x 2 . Tương tự ta có g2(x)= 1 + x 2. Dòng vào m = {1, 1, 0, 0, 1, 0, 1} có thể biểu thị như sau: m (x) = 1+ x+ x 4 + x 6 [[ ]]. Các đầu ra sẽ là: C (1)( x) = m(x)g1(x) = (1+ x +x 4 + x 6 )(1+ x + x 2 ) = 1 +x 3 +x 4 +x 5 +x 7 + x 8 C (2)( x) = m(x)g2(x) = (1+ x +x 4 + x 6 )(1+ x 2 ) = 1+x + x 2 +x 3 +x 4 +x 8 Với mỗi mã chập tốc độ có một hàm truyền ma trận k × n  (x) (còn được gọi là ma trận truyền). Với mã tốc độ ở ví dụ trên ta có: Ga (x) = [1+ x+ x 2 1 + x 2 ] Ma trận truyền này không chỉ có dạng các đa thức, ta có thể thấy thông qua ví dụ sau: Ví dụ 2.2.1: Xét ma trận truyền của mã chập sau: [ ] Vì có “1” ở cột đầu tiên nên dòng vào sẽ xuất hiện trực tiếp ở đầu ra đan xen, bởi vậy đây là một mã chập hệ thống. Bộ mã hóa cho mã này được mô tả ở hình 2.2: Hình 2.2: Bộ mã hóa hệ thống với 1 2 R  Thực hiện bộ giải mã Viterbi trên FPGA Trang 22 Chương 2: Thuật giải mã Viterbi Với dòng vào: m (x) = 1+ x + x 2 + x3+ x 4 + x8 các đầu ra C(1)k và C (2) k có dạng: C (1) k = m(x) =1 + x +x 2 + x 3 + x 4 + x 8   2 3 4 8 2 (2) 2 (1 x x x x x )(1 ) 1 k x x C x x          Một bộ mã hóa chỉ có các hàng đa thức trong ma trận truyền được gọi là bộ mã hóa có đáp ứng xung hữu hạn. Một bộ mã hóa có các hàm hữu tỷ trong ma trận truyền gọi là bộ mã hóa có đáp ứng xung vô hạn. Với mã có tốc độ k/n với k > 1 dãy tin tức đầu vào (ta coi như được tách ra từ một dãy tin tức thành k dòng), ta có: m(x) = [m (1) ( x), m (2)(x),…,m(k)(x)] và Dãy ra được biểu thị như sau: C(X) = [C (1) (x), C (2)(x),…,C(n)(x)] = m(x)G(x) Ma trận truyền G(x) được gọi là hệ thống nếu có thể xác định được một ma trận đơn vị trong các phần tử của G(x) (chẳng hạn nếu bằng các phép hoán vị hàng và/hoặc cột của G(x) có thể thu được một ma trận đơn vị). Ví dụ 2.2.2: Cho mã hệ thống tốc độ 2 3 R  có ma trận truyền sau: Sơ đồ thể hiện của mã này cho trên hình 2.3: Thực hiện bộ giải mã Viterbi trên FPGA Trang 23 Chương 2: Thuật giải mã Viterbi Hình 2.3: Bộ mã hóa hệ thống Một sơ đồ mã hóa khác có hiệu quả hơn được mô tả ở hình 2.4: Hình 2.4: Sơ đồ bộ mã hóa hệ thống 2 3 R  có phần cứng đơn giản Giả sử: m(x) = [1+ x2 + x4+ x5+ x7+…,x2 + x5 + x6 + x7 + …] Khi đó đầu ra C(x) có dạng: C(x) = [1+ x 2 + x 4 + x 5 + x 7+ …, x 2+ x5+ x6+ x7+ …, x+ x3+ x5+ …] Khi đưa ra xen kẽ dòng ra sẽ là: {100, 001, 110, 001, 100, 111, 010, 110} Từ các ví dụ trên ta có định nghĩa sau cho mã chập Định nghĩa: Mã chập tốc độ R = k/n trên trường các chuỗi Laurent hữu tỷ  F X   trường F là ảnh của một ánh xạ tuyến tính đơn ánh của các chuỗi Laurent k chiều m (x)   k F X    vào các chuỗi Laurent C(x)   n F X    2.3 Cấu trúc mã chập Mã chập được tạo ra bằng cách cho chuỗi thông tin truyền qua hệ thống các thanh ghi dịch tuyến tính có số trạng thái hữu hạn. Cho số lượng thanh ghi dịch là m (cũng ký hiệu là N), bộ mã có k bit ngõ vào và đầu ra bộ mã chập có n bit ngõ ra (n hàm đại số tuyến tính hoặc n ngõ ra cộng modulo). Tốc độ mã là R = k/n, số ô nhớ của bộ ghi dịch là m×k và tham số L gọi là chiều dài ràng buộc (Constraint length) của mã chập (với L=k(m-1)). Thực hiện bộ giải mã Viterbi trên FPGA Trang 24 Chương 2: Thuật giải mã Viterbi Chuỗi mã n bit Các thông số k,n có phạm vi giới hạn trong khoảng giá trị từ 1 đến 8, thông số m trong khoảng từ 2 đến 10, và tốc độ mã R từ 1/8 đến 7/8 ngoại trừ các bộ mã hóa được sử dụng trong viễn thông vũ trụ có thể có tốc độ 1/100 hoặc thậm chí cao hơn. Trong một số tài liệu, khi nói đến mã chập, người ta còn đặc trưng cho bộ mã hóa chập bằng chiều dài ràng buộc K và tốc độ mã R. Tốc độ mã, R=k/n, được hiểu là tỉ số giữa số bit ngõ vào và số ký hiệu ngõ ra của bộ mã hóa. Thông số chiều dài ràng buộc, K, cho biết “chiều dài” của bộ mã hóa mã chập, ví dụ, có bao nhiêu trạng thái k-bit có thể đưa đến mạch logic tổ hợp để tạo ra ký hiệu ngõ ra. Trong nội dung đề tài này, chúng tôi sử dụng bộ mã với bộ dữ liệu bao gồm chiều dài ràng buộc K và tốc độ bộ mã R như đã đề cập ở trên. Khi thực hiện với mã chập trong các ứng dụng thông thường, người ta thường chỉ chọn số thanh ghi giới hạn, mỗi thanh ghi chỉ có 1 ô nhớ để đơn giản cho việc thiết kế mà vẫn đảm bảo tính năng mã hóa tốt. Tương ứng với mỗi tốc độ mã hóa (các bộ mã đơn giản), người ta cũng đã thử nghiệm và chọn ra chỉ một số đa thức sinh cho hiệu quả mã hóa cao để sử dụng. Giả thiết, bộ mã chập làm việc với các chữ số nhị phân, thì tại mỗi lần dịch sẽ có k bit thông tin đầu vào được dịch vào thanh ghi dịch thứ nhất và tương ứng có k bit thông tin trong thanh ghi dịch cuối cùng được đẩy ra ngoài mà không tham gia vào quá trình tạo chuỗi bit đầu ra. Đầu ra nhận được chuỗi n bit mã từ n bộ cộng môđun-2 (xem hình 2.5). Như vậy, giá trị chuỗi đầu ra kênh không chỉ phụ thuộc vào k bit thông tin đầu vào hiện tại mà còn phụ thuộc vào (m-1)k bit trước đó, và được gọi là mã chập (n,k,m). Hình 2.5: Sơ đồ tổng quát bộ mã chập. Giả sử u là véctơ đầu vào, x là véctơ tương ứng được mã hoá, bây giờ chúng ta mô tả cách tạo ra x từ u. Để mô tả bộ mã hoá chúng ta phải biết sự kết nối giữa thanh ghi đầu vào vào đầu ra hình 2.5. Cách tiếp cận này có thể giúp chúng ta chỉ ra sự tương tự và khác nhau cũng như là với mã khối. Điều này có thể dẫn tới những ký hiệu phức tạp và nhằm nhấn mạnh cấu trúc đại số của mã chập. Điều đó làm giảm đi tính quan tâm cho mục đích giải mã của chúng ta. Do vậy, chúng ta chỉ Chuỗi thông tin đầu vào k bit 1 2 ... k 1 2... k 12... k Thực hiện bộ giải mã Viterbi trên FPGA Trang 25 Chương 2: Thuật giải mã Viterbi phác hoạ tiếp cận này một cách sơ lược. Sau đó, mô tả mã hoá sẽ được đưa ra với những quan điểm khác. Để mô tả bộ mã hoá hình 2.5 chúng ta sử dụng N ma trận bổ sung G1,G2…,GN bao gồm k hàng và n cột. Ma trận Gi mô tả sự kết nối giữa đoạn thứ i của k ô nhớ trong thanh ghi ngõ vào với n ô của thanh ghi ngõ ra. N ngõ vào của hàng đầu tiên của Gi mô tả kết nối của ô đầu tiên của đoạn thanh ghi đầu vào thứ i với n ô của thanh ghi ngõ ra. Kết quả là “1” trong Gi nghĩa là có kết nối, là “0” nghĩa là không kết nối. Do đó chúng ta có thể định nghĩa ma trận sinh của mã chập: Và tất cả các các ngõ vào khác trong ma trận bằng 0. Do đó nếu ngõ vào là véctơ u, tương ứng véctơ mã hoá là: .x uG Bộ mã chập là hệ thống nếu trong mỗi đoạn của n chữ số đuợc tạo, k số đầu là mẫu của các chữ số đầu vào tương ứng. Nó có thể xác định rằng điều kiện này tương đương có các ma trận k×n theo sau và i = 2,3,….,N Chúng ta xét một vài ví dụ minh hoạ sau đây: Ví dụ 2.3.1: Xét mã (3,2,2). Bộ mã hoá được chỉ trong hình 2.6. Bây giờ mã được định nghĩa thông qua 2 ma trận: Bộ mã hoá là hệ thống, ma trận sinh được tạo ra: Thực hiện bộ giải mã Viterbi trên FPGA Trang 26 Chương 2: Thuật giải mã Viterbi Chuỗi thông tin u = ( 11011011…) được mã hóa thành chuỗi mã x = (111010100110…) Hình 2.6: Bộ mã chập (3,2,2). Một cách tương tự ta cũng có thể biểu diễn ma trận sinh G = (G1,G2,…,GN), Như vậy ý nghĩa của ma trận sinh là nó chỉ ra phải sử dụng các hàm tương ứng nào để tạo ra véc tơ dài n mỗi phần tử có một bộ cộng môđun-2, trên mỗi véc tơ có N×k tham số biểu diễn có hay không các kết nối từ các trạng thái của bộ ghi dịch tới bộ cộng môđun-2 đó. Xét véc tơ thứ i (gi, n ≥ i ≥ 1), nếu tham số thứ j của gi (L×k ≥ j ≥1) có giá trị “1” thì đầu ra thứ j tương ứng trong bộ ghi dịch được kết nối tới bộ cộng môđun-2 thứ i và nếu có giá trị “0” thì đầu ra thứ j tương ứng trong bộ ghi dịch không được kết nối tới bộ cộng môđun-2 thứ i. Ví dụ 2.3.2: Cho bộ mã chập có số thanh ghi N = 3, số ô nhớ trong mỗi thanh ghi dịch k = 1, chiều dài chuỗi đầu ra n = 3 tức là mã (3,1,3) và ma trận sinh của mã chập có dạng sau: 1 2 100 101 (4,5,7) 111 n g g G G G g                     M Có thể biểu diễn dưới dạng đa thức sinh là: G(D) = [1 1+D 2 1+D+D 2 ] Do đó sơ đồ mã chập được biểu diễn như sau: Thực hiện bộ giải mã Viterbi trên FPGA Trang 27 Chương 2: Thuật giải mã Viterbi Hình 2.7: Sơ đồ bộ mã chập với N=3, k=1, n=3 2.4 Biểu diễn mã chập Có ba phương pháp để biểu diễn mã chập đó là: sơ đồ lưới, sơ đồ trạng thái, và sơ đồ hình cây. Để làm rõ phương pháp này ta tập trung phân tích dựa trên ví dụ hình 2.1 với bộ mã (2,1,3), đa thức sinh (7,5). * Sơ đồ hình cây: Từ ví dụ hình 2.1, giả thiết trạng thái ban đầu của các thanh ghi dịch trong bộ mã đều là trạng thái “toàn 0”. Nếu bit vào đầu tiên là bit “0” thì đầu ra ta nhận được chuỗi “00”, còn nếu bit vào đầu tiên là bit “1” thì đầu ra ta nhận được chuỗi “11”. Nếu bit vào đầu tiên là bit “1” và bit vào tiếp theo là bit “0” thì chuỗi thứ nhất là “11” và chuỗi thứ hai là chuỗi “10”. Với cách mã hoá như vậy, ta có thể biểu diễn mã chập theo sơ đồ có dạng hình cây (xem hình 2.8).Với hướng lên là hướng của bit 0 đi vào bộ mã, nhánh đi xuống biểu hiện cho bit 1 được dịch vào. Từ sơ đồ hình cây ta có thể thực hiện mã hoá bằng cách dựa vào các bit đầu vào và thực hiện lần theo các nhánh của cây, ta sẽ nhận được tuyến mã, từ đó ta nhận được dãy các chuỗi đầu ra. Thực hiện bộ giải mã Viterbi trên FPGA Trang 28 Chương 2: Thuật giải mã Viterbi 00 10 0 1 00 10 01 11 00 10 01 11 00 10 01 11 00 00 11 00 11 00 10 01 10 01 11 11 00 01 10 Hình 2.8: Sơ đồ hình cây của bộ mã (2,1,3) *Sơ đồ hình lƣới: Do đặc tính của bộ mã chập, cấu trúc vòng lặp được thực hiện như sau: chuỗi n bit đầu ra phụ thuộc vào chuỗi k bit đầu vào hiện hành và (N-1) chuỗi đầu vào trước đó hay (N-1) × k bit đầu vào trước đó. Từ ví dụ hình 2.1 ta có chuỗi 2 bit đầu ra phụ thuộc vào 1 bit đầu vào là “1” hoặc “0” và 4 trạng thái có thể có của hai thanh ghi dịch, là “00”; “01”; “10”; “11”. Từ sơ đồ hình cây trên, ta thấy rằng tại tầng thứ 3, cứ mỗi trạng thái 00, 01, 10, 11 đều có 2 nhánh đến từ các trạng thái trước đó tùy thuộc vào bit được dịch vào bộ mã là bit 0 hay bit 1. Với tính chất đó ta có thể biểu diễn mã chập bằng sơ đồ có dạng hình lưới gọn hơn, trong đó các đường liền nét được ký hiệu cho bit đầu vào là bit “1” và đường đứt nét được ký hiệu cho các bit đầu vào là bit “0” (xem hình 2.9). Ta thấy rằng từ sau tầng thứ hai hoạt động của lưới ổn định, tại mỗi nút có hai đường vào nút và hai đường ra khỏi nút. Trong hai đường đi ra thì một ứng với bit đầu vào là bit “0” và đường còn lại ứng với bit đầu vào là bit “1”. Thực hiện bộ giải mã Viterbi trên FPGA Trang 29 Chương 2: Thuật giải mã Viterbi T=1T=0 State 00 State 01 State 10 State 11 00 11 T=2 11 00 10 01 T=3 11 00 10 11 00 01 10 01 T=4 11 00 10 11 00 01 10 01 T=5 11 00 10 11 00 01 10 01 Hình 2.9: Sơ đồ hình lưới bộ mã chập (2,1,3) và bộ phát mã (7,5). Trạng thái ban đầu toàn bằng “0” *Sơ đồ trạng thái: Sơ đồ trạng thái được thực hiện bằng cách đơn giản sơ đồ 4 trạng thái có thể có của bộ mã (00, 01, 10 và 11) và trạng thái chuyển tiếp có thể được tạo ra từ trạng thái này chuyển sang trạng thái khác, quá trình chuyển tiếp có thể là: Next State/output symbol, if Current State Input = 0: Input = 1: 00 00/00 10/11 01 00/11 10/00 10 01/10 11/01 11 01/01 11/10 Kết quả ta thu được sơ đồ trạng thái trong hình 2.10 như sau: Hình 2.10: Sơ đồ trạng thái của bộ mã chập (2,1,3) Thực hiện bộ giải mã Viterbi trên FPGA Trang 30 Chương 2: Thuật giải mã Viterbi Từ sơ đồ trạng thái hình 2.10, các đường liền nét được ký hiệu cho bit đầu vào là bit “0” và đường đứt nét được ký hiệu cho các bit đầu vào là bit “1”. So với sơ đồ hình lưới và sơ đồ hình cây thì sơ đồ trạng thái là sơ đồ đơn giản nhất. 2.5 Ưu nhược điểm của mã chập 2.5.1 Ưu điểm Cũng như các mã sửa sai khác, mã chập cho phép chúng ta có thể sửa lại dữ liệu đã bị sai lệch khi truyền qua kênh truyền để khôi phục chính xác tín hiệu gốc. Việc thực hiện mã hóa dùng mã chập tương đối đơn giản hơn các loại mã sửa sai khác mà chất lượng mã hóa lại tốt. Việc thực hiện mã hóa dùng mã chập có thể được thực hiện bằng phần cứng và phần mềm. Dựa trên hình thức mã hóa mã chập cùng thuật giải Viterbi cho nó, các bộ mã hóa sau này đều kế thừa những đặc tính ưu việt của nó. 2.5.2 Nhược điểm Việc mã hóa và giải mã liên quan đến mã chập chỉ giải quyết được các lỗi một bit còn đối với các kênh truyền xuất hiện nhiều bit liên tiếp thì thuật toán mã hóa và giải mã này sẽ không còn hoàn hảo nữa. Kênh truyền ở đây phải là kênh truyền ít nhiễu, vì nếu kênh truyền nhiễu quá lớn, mã hóa chập sẽ không còn tốt nữa. Khi đó ta phải cần tới trải phổ tín hiệu để đưa tín hiệu xuống dưới mức nhiễu để giảm thiểu ảnh hưởng. 2.6 Định nghĩa thuật toán Viterbi Thuật toán Viterbi là một giải pháp được sử dụng phổ biến để giải mã chuỗi bit được mã hóa bởi bộ mã hóa tích chập. Chi tiết của một bộ giải mã riêng phụ thuộc vào một bộ mã hóa tích chập tương ứng. Thuật toán Viterbi không phải là một thuật toán đơn lẻ có thể dùng để giải mã những chuỗi bit mà được mã hóa bởi bất cứ một bộ mã hóa chập nào. Thuật toán Viterbi được khởi xướng bởi Andrew Viterbi năm 1967 như là một thuật toán giải mã cho mã chập qua các tuyến thông tin số có nhiễu. Nó được sử dụng trong cả hai hệ thống CDMA và GSM, các modem số, vệ tinh, thông tin vũ trụ, và các hệ thống mạng cục bộ không dây. Hiện nay còn được sử dụng phổ biến trong kỹ thuật nhận dạng giọng nói, nhận dạng từ mã, ngôn ngữ học máy tính. Thuật toán giải mã Viterbi là một trong hai loại thuật toán giải mã được sử dụng với bộ mã hóa mã chập- một loại khác đó là giải mã tuần tự. Ưu điểm của giải mã tuần tự so với Viterbi là nó có thể hoạt động tốt với các mã chập có chiều dài ràng buộc lớn, nhưng nó lại có thời gian giải mã biến đổi. Thực hiện bộ giải mã Viterbi trên FPGA Trang 31 Chương 2: Thuật giải mã Viterbi Còn ưu điểm của thuật toán giải mã Viterbi là nó có thời gian giải mã ổn định. Điều đó rất tốt cho việc thực thi bộ giải mã bằng phần cứng. Nhưng mà yêu cầu về sự tính toán của nó tăng theo hàm mũ như là một hàm của chiều dài ràng buộc, vì vậy, trong thực tế, người ta thường giới hạn chiều dài ràng buộc của nó K = 9 hoặc nhỏ hơn. Stanford Telecom tạo ra một bộ giải mã Viterbi K = 9 hoạt động ở tốc độ đến 96 kbps, và một bộ giải mã với K = 7 hoạt động với tốc độ lên đến 45 Mbps. Các kỹ thuật không dây nâng cao có thể tạo ra một bộ giải mã Viterbi với K = 9 hoạt động ở tốc độ lên đến 2 Mbps. NTT tuyên bố rằng họ đã tạo được bộ giãi mã Viterbi hoạt động ở tốc độ 60 Mbps, nhưng tính khả thi của nó vẫn chưa được kiểm chứng. 2.7 Phân tích thuật giải Viterbi Chúng ta sẽ lấy ví dụ về mã chập có tốc độ mã là k/n = ½ Hình 2.11: Bộ mã chập tốc độ ½ FF: thanh ghi dịch. Tại mỗi xung clock, nội dung của thanh ghi dịch được dịch qua phải 1 bit. Bit đầu tiên sẽ là ngõ vào, và bit cuối cùng sẽ là ngõ ra. Một thanh ghi dịch có thể sẽ xem xét việc cộng trễ vào ngõ vào. Các thanh ghi dịch có thể được hiểu như là bộ nhớ của bộ mã hóa. Nó ghi nhớ những bit đầu của chuỗi. Thanh ghi dịch được khởi đầu với tất cả giá trị là 0. Thuật toán XOR: 1 1= 0; 1 0=1; 0 1=1; 0 0=0 Nếu chúng ta làm việc trên một chuỗi ngõ vào là 01011101, ngõ ra là 00 11 10 00 01 10 01 002. Bộ mã hóa này cũng có thể được mô hình bởi một bảng trạng thái hữu hạn. Mỗi một trạng thái được quy định bởi 2 bit nhị phân- trạng thái của 2 thanh ghi dịch. Mỗi một sự chuyển trạng thái được quy định bởi w/v1v2 với w đại diện cho bit ngõ vào, và v1v2 là đại diện cho 2 bit ngõ ra, trong trường hợp này chúng ta luôn luôn có w = v1. Thực hiện bộ giải mã Viterbi trên FPGA Trang 32 Chương 2: Thuật giải mã Viterbi Bảng 2.1: Trạng thái ngõ vào và ngõ ra của bộ mã hóa tốc độ ½ Next State/output symbol, if Current State Input = 0: Input = 1: 00 00/00 10/11 01 00/11 10/00 10 01/10 11/01 11 01/01 11/10 Hình 2.12: Đồ hình trạng thái của mã chập ½ Bậy giờ chúng ta có thể mô tả thuật toán giải mã, phần chính là thuật toán Viterbi. Có lẽ, khái niệm quan trọng nhất để hỗ trợ cho việc hiểu được thuật toán Viterbi đó là sơ đồ Trellis. Hình bên dưới cho chúng ta thấy sơ đồ trellis cho ví dụ của chúng ta ở tốc độ ½, mã hóa chập với chiều dài ràng buộc K = 3 với bản tin 8 bit. T=5 T=6 T=7 T=8 T=9 T=10T=4T=3T=2T=1T=0 State 00 State 01 State 10 State 11 Hình 2.13: Các nhánh trong bộ mã hóa Thực hiện bộ giải mã Viterbi trên FPGA Trang 33 Chương 2: Thuật giải mã Viterbi Bốn trạng thái có thể của bộ mã hóa được mô tả như 4 hàng của những dấu chấm theo chiều ngang. Có một cột của 4 chấm cho trạng thái khởi đầu của bộ mã hóa và một ở mỗi thời điểm của bản tin. Các đường in đậm kết nối các điểm trong sơ đồ biểu diễn cho sự chuyển trạng thái khi ngõ vào là một bit 1. Đường chấm chấm là biểu diễn cho sự chuyển trạng thái khi ngõ vào là bit 0. Ta có thể thấy rõ sự phù hợp giữa sơ đồ trellis và đồ hình trạng thái đã nói ở trên. Hình vẽ bên dưới cho ta thấy trạng thái trellis cho toàn bộ 8 bit ngõ vào. Các bit ngõ vào bộ mã hóa và ký hiệu ngõ ra được thể hiện ở bên dưới của hình. T=5 T=6 T=7 T=8 T=9 T=10T=4T=3T=2T=1T=0 State 00 State 01 S ate 10 State 11 ENC IN = ENC OUT = 0 1 0 1 1 1 0 1 0 0 00 11 10 00 01 10 01 00 10 11 Hình 2.14: Đường đi hoàn chỉnh khôi phục chính xác tín hiệu tại ngõ ra. Các bit ngõ vào và các ký hiệu ngõ ra của bộ mã thì có thể xem ở dưới cùng của hình trên. Chú ý sự phù hợp giữa các ký hiệu ngõ ra và bảng ngõ ra chúng ta đã đề cập ở trên. Hãy xem xét một cách chi tiết hơn, sử dụng phiên bản mở rộng của sự chuyển đổi từ một trạng thái tức thời đến một trạng thái kế tiếp như hình bên dưới: State 00 State 01 State 10 State 11 00 11 10 01 11 00 01 10 Giờ chúng ta sẽ xem xét cách thức giải mã của thuật toán Viterbi. Bây giờ chúng ta giả sử là chúng ta có một mẫu tin đã mã hóa (có thể có vài lỗi) và chúng ta muốn khôi phục lại tín hiệu gốc. Giả sử chúng ta nhận được mẫu tin đã mã hóa ở trên với 1 bit lỗi. Thực hiện bộ giải mã Viterbi trên FPGA Trang 34 Chương 2: Thuật giải mã Viterbi T=5 T=6 T=7 T=8 T=9 T=10T=4T=3T=2T=1T=0 State 00 State 01 State 10 State 11 ENC IN = ENC OUT = 0 1 0 1 1 1 0 1 0 0 00 11 10 00 01 10 01 00 10 11 RECEIVED = 00 11 11 00 01 10 01 00 10 11 ERRORS = X Hình 2.15: Tín hiệu nhận có 1 bit sai tại t =2 Ở mỗi thời điểm chúng ta nhận được 2 bit trong ký hiệu. Chúng ta sẽ tính toán thông số metric để đo “khoảng cách” giữa những gì mà chúng ta nhận được với tất cả các cặp bit ký hiệu kênh truyền có thể mà chúng ta có thể nhận được. Đi từ thời điểm t=0 đến t=1, chỉ có 2 trạng thái mà chúng ta có thể nhận được là 00 và 11. Đó là bởi vì chúng ta biết được bộ mã hóa tích chập bắt đầu với trạng thái tất cả đều là 0 và cho 1 bit vào là 0 hay 1 thì chỉ có 2 trạng thái mà chúng ta có thể đi đến và 2 ngõ ra của bộ mã hóa. Những ngõ ra này có trạng thái là 00 và 11. Thông số metric mà chúng ta sẽ sử dụng là khoảng cách Hamming giữa cặp bit của ký hiệu nhận được và cặp bit có thể của kênh truyền. Khoảng cách Hamming được tính một cách đơn giản bằng cách đếm có bao nhiêu bit khác giữa cặp bit nhận được từ kênh truyền và cặp bit so sánh. Kết quả chỉ có thể là 0, 1, 2. Giá trị của khoảng cách Hamming (hay thông số metric) mà chúng ta tính toán ở mỗi khoảng thời gian cho đường dẫn của trạng thái tại thời điểm trước và trạng thái hiện tại được gọi là metric nhánh (branch metric). Ở thời điểm đầu tiên, chúng ta sẽ lưu những kết quả này như là “thông số metric tích lũy”, được liên kết đến các trạng thái. Ở thời điểm thứ 2, thông số metric tích lũy sẽ được tính toán bằng cách cộng thêm thông số metric tích lũy trước đó vào metric nhánh hiện tại. Ở thời điểm t=1, ta nhận được 2 bit “00”. Chỉ có một cặp ký hiệu kênh truyền mà chúng ta có khả năng nhận được là “00” và “11”. Khoảng cách Hamming giữa “00” và “00” là bằng 0. Khoảng cách Hamming giữa “00” và “11” là 2. Do đó, giá trị thông số metric nhánh cho nhánh ứng với sự chuyển trạng thái từ “00” đến “00” là 0 và cho nhánh từ “00” đến “10” là 2. Khi mà thông số metric tích lũy trước đó là 0 thì thông số metric tổng sẽ chính bằng thông số metric của nhánh vừa xét. Tương tự ta tính được thông số metric cho 2 trạng thái kia. Hình bên dưới minh họa kết quả tại thời điểm t= 1 Thực hiện bộ giải mã Viterbi trên FPGA Trang 35 Chương 2: Thuật giải mã Viterbi T=1T=0 State 00 State 01 State 10 State 11 ENC IN = ENC OUT = 0 00 RECEIVED = 00 Accumulated Error Metric = 0 2 00 11 Hình 2.16: Tại thời điểm t = 1 Điều gì sẽ xảy ra ở thời điểm t=2, chúng ta nhận được một cặp kí hiệu kênh truyền là “11”, trong khi đó cặp ký hiệu kênh truyền mà chúng ta có thể nhận được là “00” nếu chuyển từ trạng thái “00” sang trạng thái “00” và “11” khi chuyển từ trạng thái “00” đến trạng thái “10”, “10” khi chuyển từ trạng thái “10” đến trạng thái “01”, “01” khi chuyển từ trạng thái “10” đến trạng thái “11”. Khoảng cách Hamming giữa 00 và 11 là 2, giữa 11 và 11 là 0, giữa 01 hoặc 10 với 11 là 1. Chúng ta cộng các thông số metric ở mỗi nhánh lại với nhau. ở thời điểm t=1 thì trạng thái chỉ có thể là 00 hoặc 10, thông số metric tích lũy sẽ được cộng vào là 0 hoặc là 2 một cách tương ứng. Hình bên dưới thể hiện sự tính toán thông số metric tích lũy ở thời điểm t=2. T=1T=0 State 00 Stat 0 State 10 State 11 ENC IN = ENC OUT = 0 00 RECEIVED = 00 Accumulated Error Metric = 0 + 2 = 2 00 11 T=2 1 11 11 11 00 10 01 2 + 1 = 3 0 + 0 = 0 2 + 1 = 3 Hình 2.17: Tại thời điểm t = 2 Đó là tất cả sự tính toán cho thời điểm t=2. Đường nét đậm là metric nhánh được lựa chọn vì theo các nhánh đó, thông số metric là nhỏ nhất. Giờ chúng ta sẽ tính thông số metric tích lũy cho mỗi trạng thái tại thời điểm t=3. Giờ chúng ta hãy nhìn vào hình minh họa cho thời điểm t=3. Chúng ta sẽ gặp phải một ít phức tạp hơn ở đây, tại mỗi trạng thái trong 4 trạng thái tại t=3 sẽ có 2 Thực hiện bộ giải mã Viterbi trên FPGA Trang 36 Chương 2: Thuật giải mã Viterbi đường đến từ 4 trạng thái của thời điểm t=2. Chúng ta sẽ xoay sở thế nào? Câu trả lời là, chúng ta sẽ tính toán thông số metric tích lũy liên quan của mỗi nhánh, và chúng ta sẽ bỏ đi giá trị metric lớn hơn, tức là sẽ loại bỏ nhánh đó đi. Nếu cặp thông số metric ở mỗi trạng thái là bằng nhau thì chúng ta sẽ giữ lại cả 2 trạng thái. Chúng ta sẽ kế thừa những tính toán đã thực hiện ở thời điểm t=2. Thuật toán cộng thông số metric tích lũy trước đó vào nhánh mới, so sánh kết quả và chọn thông số metric nhỏ hơn (nhỏ nhất) để tiếp tục dùng cho thời điểm kế tiếp, được gọi là thuật toán cộng-so sánh-chọn. Hình bên dưới cho thấy kết quả của việc xử lý tại thời điểm t=3. T=1T=0 State 00 State 01 State 10 St te 11 ENC IN = ENC OUT = 0 00 RECEIVED = 00 Accumulated Error Metric = 00 11 T=2 1 11 11 11 00 10 01 0+1 , 3+1 : 1 T=3 0 10 11 11 00 10 11 00 01 10 01 2+0 , 3+2 : 2 0+1 , 3+1 : 1 2+2 , 3+0 : 3 Hình 2.18: Tại thời điểm t = 3 Chú ý là cặp ký hiệu kênh truyền thứ 3 mà chúng ta nhận được sẽ có một lỗi. Thông số metric nhỏ nhất hiện tại là 1. Chúng ta hãy xem điều gì xảy ra ở thời điểm t=4. Tiến trình xử lý cũng giống như ở thời điểm t=3. Kết quả xem ở hình bên dưới T=1T=0 State 00 State 01 State 10 State 11 ENC IN = ENC OUT = 0 00 RECEIVED = 00 Accumulated Error Metric = 00 11 T=2 1 11 11 11 00 10 01 2+1 , 1+1 : 2 T=3 0 10 11 11 00 10 11 00 01 10 01 3+2 , 1+0 : 1 2+1 , 1+1 : 2 3+0 , 1+2 : 3 T=4 1 00 00 11 0 10 11 00 01 10 01 Hình 2.19: Tại thời điểm t = 4 Thực hiện bộ giải mã Viterbi trên FPGA Trang 37 Chương 2: Thuật giải mã Viterbi Chú ý là ở thời điểm t=4, đường trellis của tin tức thực sự truyền đi được xác định bằng đường in đậm, với thông số metric tích lũy là nhỏ nhất. Hãy xem xét ở thời điểm t=5: T=1T=0 State 00 State 01 State 10 State 11 ENC IN = ENC OUT = 0 00 RECEIVED = 00 00 11 T=2 1 11 11 11 00 10 01 T=3 0 10 11 11 00 10 11 00 01 10 01 T=4 1 00 00 11 00 10 11 00 01 10 01 Accumulated Error Metric = 1+0 , 2+2 : 1 3+1 , 2+1 : 3 1+2 , 2+0 : 2 3+1 , 2+1 : 3 T=5 1 01 01 11 00 10 11 00 01 10 01 Hình 2.20: Tại thời điểm t = 5 Ở thời điểm t=10, sơ đồ trellis sẽ như thế này, các nhánh ko được chọn đã được bỏ đi: T=5 T=6 T=7 T=8 T=9 T=10T=4T=3T=2T=1T=0 State 00 State 01 State 10 State 11 ENC IN = ENC OUT = 0 1 0 1 1 1 0 1 0 0 00 11 10 00 01 10 01 00 10 11 RECEIVED = 00 11 11 00 01 10 01 00 10 11 ERRORS = X Hình 2.21: Tất cả dữ liệu đã được giải mã và sửa sai chính xác Kết quả ở đây cho thấy chúng ta đã giải mã đúng chuỗi dữ liệu gốc. Nếu chúng ta nhìn lại con đường để chúng ta tìm ra dữ liệu gốc là bằng cách so sánh dữ liệu nhận được với dữ liệu so sánh của bộ giải mã có được từ bảng trạng thái. Điều này cho thấy chúng ta đang sử dụng thuật toán giải mã dựa trên sự giống nhau lớn nhất. Thực hiện bộ giải mã Viterbi trên FPGA Trang 38 Chương 2: Thuật giải mã Viterbi Việc xử lý giải mã bắt đầu với xây dựng một thông số metric tích lũy cho một số cặp ký hiệu kênh truyền nhận được, và lưu giữ trạng thái ở mỗi thời điểm t mà thông số metric là nhỏ nhất. Một khi thông tin này được dựng lên thì bộ giải mã viterbi sẵn sàng để khôi phục lại chuỗi bit đã đưa vào bộ mã hóa chập, khi mẫu tin được mã hóa để truyền đi. Điều này đạt được bằng những bước sau: o Đầu tiên, chọn một trạng thái có thông số metric nhỏ nhất và lưu lại số trạng thái của trạng thái đó. o Sử dụng lặp lại cho những bước kế tiếp mãi cho đến khi bắt đầu của trellis đạt được: dựa vào bảng ghi nhớ trạng thái cho trạng thái được chọn, chọn một trạng thái mới được liệt kê trong bảng ghi nhớ trạng thái khi chuyển từ trạng thái trước đến trạng thái đó. Lưu số trạng thái của mỗi trạng thái được chọn. Bước này được gọi là truy hồi (traceback). o Chúng ta làm việc tiếp với danh sách những trạng thái được chọn đã được lưu trong bước xử lý trước đó. Chúng ta tra xem bit ngõ vào nào phù hợp với sự truyền dẫn từ mỗi trạng thái trước đến trạng thái kế tiếp. Đây là bit mà phải được mã hóa bằng mã tích chập. Bảng sau cho chúng ta thấy ma trận tích lũy của đầy đủ 8 bit (cộng với 2 bit phụ thêm) của bản tin ở mỗi thời điểm t: Bảng 4.2: Bảng ma trận tích lũy của cả 8 bit của bản tin Chú ý rằng ở ví dụ về bộ giải mã Viterbi ngõ vào quyết định cứng này, thông số metric tích lũy nhỏ nhất ở trạng thái cuối chỉ ra được có bao nhiêu lỗi ký hiệu kênh truyền xảy ra. Bảng lịch sử trạng thái bên dưới cho thấy trạng thái tồn tại trước đó cho mỗi trạng thái tại thời điểm t: Thực hiện bộ giải mã Viterbi trên FPGA Trang 39 Chương 2: Thuật giải mã Viterbi Bảng 2.3: Bảng lịch sử trạng thái Tương ứng 0,1,2,3 là các vị trí 00,01,10,112. Bảng sau cho thấy trạng thái được lựa chọn khi truy hồi đường dẫn từ bảng trạng thái tồn tại ở trên: Bảng 2.4: Bảng các trạng thái được lựa chọn khi truy hồi Sử dụng bảng ta thấy được sự chuyển đổi trạng thái đến các ngõ vào gây ra chúng, giờ chúng ta đã có thể tạo lại bản tin gốc. Bảng này rất giống với ví dụ của chúng ta ở bộ mã hóa chập tốc độ ½ và K= 3. Bảng 2.5: Bảng trạng thái kế tiếp Ghi chú: trong bảng ở trên, “x” chỉ ra là một sự chuyển trạng thái không thể xảy ra từ một trạng thái đến một trạng thái khác. Thực hiện bộ giải mã Viterbi trên FPGA Trang 40 Chương 2: Thuật giải mã Viterbi Bây giờ chúng ta đã có tất cả các công cụ cần thiết để tái tạo lại bản tin gốc từ bản tin mà chúng ta nhận được. Bảng 2.6: Bảng chứa các dữ liệu của bản tin gốc đã được khôi phục Hai bit phụ đã được bỏ qua. Làm thế nào mà thuật toán truy hồi cuối cùng cũng tìm ra con đường đi đúng nhất của nó thậm chí nếu nó chọn trạng thái ban đầu là sai. Điều này có thể xảy ra nếu có hơn một trạng thái có thông số metric tích lũy là nhỏ nhất. Chúng ta sẽ dùng lại hình 2.18 để làm sáng tỏ điều này: T=1T=0 State 00 State 01 State 10 State 11 ENC IN = ENC OUT = 0 00 RECEIVED = 00 Accumulated Error Metric = 00 11 T=2 1 11 11 11 00 10 01 0+1 , 3+1 : 1 T=3 0 10 11 11 00 10 11 00 01 10 01 2+0 , 3+2 : 2 0+1 , 3+1 : 1 2+2 , 3+0 : 3 Ở thời điểm t=3, cả 2 trạng thái “01” và “11” đều có thông số metric là 1. Đường đi đúng đi đến trạng thái “01”, chú ý là đường in đậm là đường đi thực sự của bản tin để đến trạng thái này. Nhưng giả sử chúng ta chọn trạng thái “11” để bắt đầu quá trình truy hồi của chúng ta. Trạng thái trước đó của trạng thái “11” là trạng thái “10”, cũng là trạng thái trước đó của trạng thái “01”. Điều này là bởi vì ở thời điểm t=2, trạng thái “10” có thông số metric tích lũy là nhỏ nhất. Vì vậy, sau trạng thái bắt đầu sai, chúng ta có thể ngay lập tức trở lại với tuyến đường đúng. Với ví dụ về bản tin 8 bit, chúng ta tiến hành xây dựng một sơ đồ trellis cho toàn bộ bản tin trước khi bắt đầu quá trình truy hồi. Với các bản tin dài hơn hoặc các chuỗi dữ liệu liên tục, điều này là không thực tế, bởi vì bộ nhớ chiều dài ràng buộc và sự trì hoãn trong giải mã. Nghiên cứu cho thấy là độ sâu truy hồi của Kx5 chỉ đủ cho việc giải mã viterbi với loại bộ mã mà chúng ta đang thảo luận. Bất cứ một sự truy hồi sâu hơn sẽ làm tăng thời gian delay giải mã và bộ nhớ yêu cầu cho Thực hiện bộ giải mã Viterbi trên FPGA Trang 41 Chương 2: Thuật giải mã Viterbi việc giãi mã và cũng ko làm tăng hiệu quả việc giải mã, ngoại trừ bộ mã hóa thủng (punctured code) mà chúng ta sẽ nói sau. Để thực thi một bộ giải mã Viterbi bằng phần mềm, bước đầu tiên là phải xây dựng một vài cấu trúc dữ liệu xoay quanh thuật giải mã sẽ được thực thi. Những cấu trúc dữ liệu này được thực thi tốt nhất khi là các mảng. Sáu mảng chính mà chúng ta cần cho bộ giải mã viterbi là: - Một bản sao của “Bảng trại thái kế tiếp” của bộ mã hóa mã chập, bảng chuyển trạng thái của bộ mã hóa. Kích cỡ của bảng này (hàng x cột) là 2(K-1) x 2 K . Mảng này phải được khởi đầu trước khi bắt đầu tiến trình giải mã. - Một bản sao của “bảng ngõ ra” của bộ mã hóa mã chập. Kích cỡ của bảng này là 2(K-1) x 2K. Mảng này cũng cần phải được khởi đầu trước khi bắt đầu tiến trình giải mã. - Một mảng để lưu trữ trạng thái hiện tại và trạng thái kế của bộ mã hóa mã chập, với giá trị ngõ vào (0 hoặc 1) sẽ cho ra trạng thái kế tiếp và trạng thái hiện tại. Chúng ta sẽ gọi bảng này là “bảng ngõ vào”. Kích thước của bảng là 2 (K-1) x 2 (K-1) . Mảng này cũng cần phải được khởi đầu trước khi bắt đầu tiến trình giải mã. - Một mảng để lưu trữ lịch sử các trạng thái trước cho mỗi trạng thái của bộ mã hóa cho Kx5 + 1 cặp kí hiệu kênh truyền nhận được. Chúng ta sẽ gọi bảng này là “bảng lịch sử trạng thái”. Kích thước của mảng này là 2(K-1) x (Kx5 +1). Mảng này không cần khởi động trước khi bắt đầu tiến trình giải mã. - Một mảng để lưu trữ thông số metric tích lũy cho mỗi trạng thái được tính toán sử dụng nguyên tắc cộng- so sánh- lựa chọn. Mảng này sẽ được gọi là “mảng thông số metric tích lũy”. Kích thước của mảng này là 2(K-1) x 2. Mảng này không cần khởi động trước khi bắt đầu tiến trình giải mã. - Một mảng dùng để lưu trữ danh sách các trạng thái đã được quyết định trong suốt quá trình truy hồi. Nó được gọi là “mảng chuỗi trạng thái”. Kích thước của mảng này là (Kx5 + 1). Mảng này không cần khởi động trước khi bắt đầu tiến trình giải mã. Giờ chúng ta hãy nói về tốc độ của những bộ mã hóa chập mà có thể được giải mã bởi các bộ giải mã Viterbi. Ở trên chúng ta đã đề cập đến bộ mã hóa thủng, là một hướng chung của bộ mã hóa tốc độ cao, tốc độ lớn hơn từ k đến n. Punctured code được tạo ra bởi dữ liệu mã hóa đầu tiên sử dụng một bộ mã hóa tốc độ 1/n như là bộ mã hóa thí dụ được mô tả trước đây và sau đó xóa bỏ một vài ký hiệu kênh truyền ở ngõ ra của bộ mã hóa. Quá trình này được gọi là “puncturing”. Ví dụ, để tạo ra mã tốc độ ¾ từ mã tốc độ ½, thì đơn giản là sẽ xóa ký hiệu kênh truyền theo mẫu punctured sau đây: Thực hiện bộ giải mã Viterbi trên FPGA Trang 42 Chương 2: Thuật giải mã Viterbi Bảng 2.7: Ví dụ về punctured code Trong đó, bit “1” chỉ ra rằng một ký hiệu kênh truyền sẽ được truyền, và bit “0” để chỉ ra rằng một kí hiệu kênh truyền sẽ được xóa. Để xem làm thế nào mà việc này có thể tạo ra bộ mã tốc độ ¾. Hãy nghĩ là mỗi cột của bảng trên tương ứng với một bit ngõ vào đến bộ mã hóa và mỗi một bit “1” trong bảng tương ứng với một ký hiệu kênh ở ngõ ra. Có 3 cột trong bảng và 4 bit “1”. Thậm chí bạn có thể tạo ra bộ mã tốc độ 2/3 sử dụng một bộ mã hóa ½ với mẫu puncturing sau: với 2 cột và 3 bit “1”. Để giải mã một punctured code, bit “1” phải thay thế những kí hiệu rỗng cho những kí hiệu đã bị xóa ở ngõ vào của bộ giải mã Viterbi. Kí hiệu rỗng có thể là kí hiệu được lượng tử đến mức “1” yếu và mức “0” yếu hoặc hơn nữa có thể là một kí hiệu cờ đặc biệt, mà khi được xử lí bằng mạch ACS trong bộ giải mã, kết quả là không thay đổi thông số metric tích lũy từ trạng thái trước. Dĩ nhiên, n không phải bằng 2. Ví dụ, một mã tốc độ 1/3 và K=3 (7,7,5) có thể được mã hóa sử dụng bộ mã hóa như bên dưới: Hình 2.22: Bộ mã tốc độ 1/3 và K= (7,7,5) Thực hiện bộ giải mã Viterbi trên FPGA Trang 43 Chương 2: Thuật giải mã Viterbi Bộ mã hóa này có 3 bộ cộng modulo, vì vậy với mỗi một bit ngõ vào, có thể tạo ra 3 ngõ ra kí hiệu kênh truyền. Dĩ nhiên, với mẫu puncturing phù hợp, bạn có thể tạo ra những mã tốc độ cao hơn sử dụng bộ mã hóa này. 2.8 Giải mã quyết định cứng và giải mã quyết định mềm Giải mã quyết định mềm và quyết định cứng dựa vào loại lượng tử hóa được sử dụng ở các bit nhận được. Giải mã quyết định cứng sử dụng loại lượng tử hóa 1 bit trên các giá trị kênh nhận được. Giải mã quyết định mềm sử dụng loại lượng tử hóa nhiều bit trên các giá trị kênh nhận được. Đối với giải mã quyết định mềm lý tưởng (lượng tử hóa không xác định), các giá trị kênh nhận được được sử dụng trực tiếp trong bộ giải mã hóa kênh. Hình 2.23 biểu diễn giải mã quyết định cứng và quyết định mềm. Hình 2.23: Giải mã quyết định cứng và mềm 2.8.1 Thuật toán Viterbi quyết định cứng Đối với mã tích chập, chuỗi ngõ vào được xoắn thành chuỗi mã hóa c. Chuỗi c được phát xuyên qua kênh nhiễu và chuỗi nhận được là chuỗi r. Thuật toán Viterbi là thuật ước đoán khả năng xảy ra lớn nhất (Maximum Likelihood-ML) cho ra chuỗi mã hóa được ước đoán y từ chuỗi nhận được r để cho chuỗi này đạt được xác xuất p(r/y) lớn nhất. Chuỗi y phải là một trong những chuỗi mã hóa cho phép và không thể là bất kì chuỗi tùy ý nào. Hình 2.24 trình bày cấu trúc hệ thống Hình 2.24: Hệ thống mã tích chập Đối với một mã tích chập có tốc độ r, các ngõ vào của bộ mã hóa k bit song song và các ngõ ra n bit song song tại mỗi bước. Chuỗi ngõ ra là 0 0 0 1 1 1 1 1(1), (2),..., ( ), (1), (2),..., ( ), (1),..., ( )l m l mx x x x k x x x k x x k    (2.8.1) Thực hiện bộ giải mã Viterbi trên FPGA Trang 44 Chương 2: Thuật giải mã Viterbi Và chuỗi được mã hóa là 0 0 0 1 1 1 1 1(1), (2),..., ( ), (1), (2),..., ( ), (1),..., ( )l m l mc c c c n c c c n c c n    (2.8.2) Trong đó L là chiều dài của chuỗi tin ngõ vào và m là chiều dài lớn nhất của các thanh ghi dịch. Yêu cầu phải thêm vào đuôi của chuỗi mã hóa với m bit zero để cho bộ mã hóa tích chập trở về trạng thái tất cả zero. Yêu cầu bộ mã hóa phải bắt đầu và kết thúc tại trạng thái tất cả zero. Các chỉ số bên dưới là chỉ số thời gian và các chỉ số bên trên là bit chỉ ra khối k bit ngõ vào hay n bit ngõ ra riêng lẻ. Các chuỗi được ước đoán y và chuỗi nhận được r có thể được mô tả tương tự. 1 1 (1) (2) ( ) (1) (2) ( ) (1) ( ) 1 1 1, ,..., , , ,..., , ,...,l m l m n n n o o or r r r r r r r r        (2.8.3) Và 1 1 (1) (2) ( ) (1) (2) ( ) (1) ( ) 1 1 1, ,..., , , ,..., , ,...,l m l m n n n o o oy y y y y y y y y        (2.8.4) Đối với giải mã ML, thuật toán Viterbi chọn y để P(r/y) lớn nhất. Giả thiết kênh là không nhớ, và vì vậy quá trình nhiễu ảnh hưởng lên bit nhận được độc lập với quá trình nhiễu ảnh hưởng lên tất cả các bit khác. Từ lý thuyết xác suất (xác suất liên kết), xác suất của tập hợp các sự kiện độc lập tương đương với tính xác suất của các sự kiện riêng lẻ. Vì vậy,         1 (1) (1) (2) (2) ( ) ( ) 0 | | | .... | L m n n i i i i i i i p r y p r y p r y p r y        (2.8.5)     1 ( ) ( ) 0 1 | | L m n j j i i i j p r y p r y              (2.8.6) Biểu thức này được gọi là hàm có khả năng xảy ra của y với r nhận được. Việc ước đoán P(r/y) lớn nhất cũng là logP(r/y) lớn nhất bởi vì các hàm logarit là các hàm tăng đều. Vì vậy, một hàm log của khả năng xảy ra có thể được định nghĩa log log(/),   1 ( ) ( ) 0 1 log ( | ) log | l m n j j i i i j p r y p r y              (2.8.7) Vì thao tác trên các tổng dễ dàng hơn thao tác trên các hàm log nên một metric bit được định nghĩa như sau:    ( ) ( ) ( ) ( )| log |j j j ji i i iM r y a p r y b    (2.8.8) Trong đó a và b được chọn trước để cho metric bit là một số nguyên dương nhỏ nhất. Các giá trị a và b được định nghĩa cho kênh hệ thống nhị phân (BSC) hay giải mã quyết định cứng. Hình 2.25 trình bày một BSC Thực hiện bộ giải mã Viterbi trên FPGA Trang 45 Chương 2: Thuật giải mã Viterbi Hình 2.25: Kiểu kênh hệ thống nhị phân, trong đó p là xác suất chéo Đối với BSC a và b có thể được chọn theo 2 cách phân biệt. Theo cách thông thường a và b được chọn như sau: (2.8.9) Và (2.8.10) Kết quả metric bit là [ ] (2.8.11) Từ kiểu BSC, rõ ràng chỉ lấy giá trị p và 1-p. Bảng 2.8 trình bày kết quả metric bit Bảng 2.8: Các giá trị metric bit thông thường Bit nhận Bit nhận Bit được giải mã 0 1 Bit được giải mã 1 0 Metric bit này biểu diễn ước lượng của các bit giải mã và các bit nhận. Ví dụ nếu bit được giải mã yi (j) = 0 và bit nhận được ri (j) = 0 thì ước lượng M(yi (j) | ri (j) ) = 0. Tuy nhiên, nếu bit được giải mã yi (j) = 0 và bit nhận được ri (j) = 1 thì ước lượng M(yi (j) | ri (j)) = 1. Như vậy điều này liên quan đến khoảng cách Hamming và được biết như là metric của khoảng cách Hamming. Vì vậy, thuật toán Viterbi chọn chuỗi mã y qua trellis có ước lượng/khoảng cách Hamming nhỏ nhất liên quan đến chuỗi nhận được r. Cách khác a và b có thể được chọn như sau: (2.8.12) Thực hiện bộ giải mã Viterbi trên FPGA Trang 46 Chương 2: Thuật giải mã Viterbi Và (2.8.13) Kết quả metric bit cách 2 là [ ] (2.8.14) Bảng 2.9: Các giá trị metric bit cách 2 Bit nhận Bit nhận Bit được giải mã 1 0 Bit được giải mã 0 1 Đối với trường hợp này thuật toán Viterbi chọn chuỗi mã hóa y qua trellis có ước lượng/khoảng cách Hamming lớn nhất đối với chuỗi nhận được r. Hơn nữa, đối với một kênh tùy ý(không nhất thiết là BSC), các giá trị a và b được tìm theo nguyên tắc thử- và – sai để lấy metric bit có thể chấp nhận được. Từ metric bit, metric đường được định nghĩa là: ∑ (∑ ) (2.8.15) Và chỉ ra tổng ước lượng của việc ước đoán chuỗi bit nhận được r với chuỗi bit được mã hóa y trong sơ dồ trellis. Hơn nữa metric nhánh thứ K được định nghĩa như sau: ∑ (2.8.16) Và metric đường thành phần được định nghĩa như sau: ∑ (2.8.17) Do đó: ∑ ∑ (2.8.18) Metric nhánh thứ k chỉ ra việc ước lượng chọn một nhánh từ biểu đồ trellis. Metric đường thứ k chỉ ra việc ước lượng chọn một chuỗi bit được mã hóa từng phần y tới chỉ số thời gian k. Thực hiện bộ giải mã Viterbi trên FPGA Trang 47 Chương 2: Thuật giải mã Viterbi Thuật toán Viterbi sử dụng biểu đồ trellis để tính các metric đường. Mỗi trạng thái (nút) trong biểu đồ trellis được gán một giá trị gọi là metric đường thành phần. Metric đường từng phần được xác định từ trạng thái s = 0 tại thời điểm t = 0 đến một trạng thái đặc biệt s = k tại thời điểm t >= 0. Tại mỗi trạng thái metric đường từng phần tốt nhất được chọn từ các đường kết thúc tại trạng thái đó. Metric đường từng phần tốt nhất, có thể là metric lớn nhất hay nhỏ nhất phụ thuộc vào a và b được chọn theo cách thông thường hay chọn lựa khác. Metric được chọn diễn tả bằng đường tồn tại (survivor) và các metric còn lại được diễn tả bằng đường không phù hợp (nonsurvivor). Các đường tồn tại được lưu lại trong khi các đường không phù hợp bị loại bỏ trong sơ đồ trellis. Thuật toán Viterbi chọn đường tồn tại đơn giản đi từ cuối của tiến trình giống như đường ML. Sau đó truy ngược theo đường ML trong biểu đồ trellis sẽ tìm được chuỗi giải mã ML. Thuật toán Viterbi quyết định cứng có thể được thực hiện như sau: Sk,t là trạng thái trong biểu đồ trellis tương ứng với trạng thái Sk tại thời điểm t. Mỗi trạng thái trong Trellis được gán một giá trị là V(Sk,t). 1. (a) khởi tạo t = 0 (b) khởi tạo V(S0,0) = 0 và tất cả các V khác V(Sk,t) = +oo 2. (a) lấy t = t+1 (b) Tính các metric đường từng phần cho tất cả đường đi đến trạng thái Sk tại thời điểm t. Đầu tiên, tìm metric nhánh thứ t ∑ (2.8.19) Metric này được tính từ khoảng cách Hamming ∑ | | (2.8.20) Thứ hai, tính metric đường thành phần thứ t ∑ (2.8.21) Metric này được tính từ 3. a) Lấy V(Sk,t) đến metric đường từng phần tốt nhất là trạng thái Sk tại thời điểm t. Thông thường, metric đường từng phần tốt nhất là metric đường từng phần có giá trị nhỏ nhất (b) Nếu có một nút TIE nằm trên metric đường từng phần tốt nhất, sau đó bất kì một metric đường từng phần có thể được chọn. 4. Lưu trữ metric đường từng phần và các và các đường trạng thái cùng với bit tồn tại liên kết của nó. 5. Nếu t < L+m-1, trở về bước 2. Kết quả của thuật toán Viterbi là một đường Trellis duy nhất tương ứng với từ mã ML. Thực hiện bộ giải mã Viterbi trên FPGA Trang 48 Chương 2: Thuật giải mã Viterbi Ví dụ: Biểu đồ chuyển tiếp trạng thái trình bày các bit tin và các bit mã hóa được ước đoán theo các nhánh (cần thiết cho quá trình giải mã ). Việc giải mã chọn đường ML thông qua trellis như được trình bày trong hình 2.26. Metric đường từng phần (được lưu trữ) được chọn cho ví dụ này là khoảng cách Hamming lớn nhất và được trình bày trong hình cho mỗi nút. Các metric đường từng phần đậm tương ứng với ML. Các đường tồn tại được biểu diễn bởi các đường liền nét đậm và các đường cạnh tranh được biểu diễn bởi các đường nét đứt. Hình 2.26: Biểu diễn Viterbi theo ví dụ 2.8.2 Thuật toán Viterbi quyết định mềm Có 2 phương pháp tổng quát thực hiện thuật toán Viterbi quyết định mềm. Phương pháp thứ nhất (phương pháp 1) sử dụng metric khoảng cách Euclidean thay cho metric khoảng cách Hamming. Các bit nhận sử dụng trong metric khoảng cách Euclidean được xử lí bằng lượng tử hóa nhiều mức. Phương pháp thứ hai (phương pháp 2) sử dụng một metric tương quan trong đó các bit nhận được của nó dùng trong metric này cũng được xử lí bằng lượng tử hóa nhiều mức. 2.8.2.1 Thuật toán Viterbi quyết định mềm (phương pháp 1) Trong giải mã quyết định mềm, bộ thu không gán 0 hay 1 (lượng tử hóa bit đơn) cho mỗi bit nhận được mà sử dụng các giá trị lượng tử hóa nhiều bit hay bit không xác định. Lý tưởng, chuỗi thu r được lượng tử hóa bit không xác định và được sử dụng trực tiếp trong bộ giải mã quyết định mềm. Thuật toán Viterbi quyết định mềm tương tự với thuật toán quyết định cứng ngoại trừ khoảng cách Euclidean bình phương được sử dụng trong metric thay cho khoảng cách Hamming. Thuật toán Viterbi quyết định mềm có thể được thực hiện như sau Sk, t là trạng thái trong biểu đồ trellis tương ứng với trạng thái Sk tại thời điểm t. Mỗi trạng thái trong trellis được gán một giá trị là V(Sk, t). 1. (a) khởi tạo t = 0 Thực hiện bộ giải mã Viterbi trên FPGA Trang 49 Chương 2: Thuật giải mã Viterbi (b) Khởi tạo V(S0, 0) = 0 và tất cả các V khác V(Sk, t) = +00 2. (a) Lấy t = t + 1 (b) Tính các metric đường thành phần cho tất cả các đường đi đến trạng thái Sk tại thơi điểm t. Đầu tiên tìm metric nhánh thứ t ∑ (2.8.22) Metric này được tính từ khoảng cách Euclidean ∑ (| |) (2.8.23) Thứ 2, tính metric đường từng phần thứ t ∑ (2.8.24) Metric này được tính từ (2.8.25) 3. (a) Gán V(Sk, t ) cho metric đường từng phần tốt nhất là trạng thái Sk, tại thời điểm t. Thông thường metric đường từng phần tốt nhất là metric đường từng phần có giá trị nhỏ nhất. (b) Nếu có một TIE cho một metric đường từng phần tốt nhất, thì sau đó bất kỳ một trong những metric đường từng phần có thể được chọn. 4. Lưu trữ metric đường từng phần và các đường trạng thái và các bit tồn tại liên kết của nó. 5. Nếu t <= L+m -1, trở về bước 2. 2.8.2.2 Thuật toán Viterbi quyết định mềm (phương pháp 2) Thuật toán viterbi quyết định mềm thứ 2 được trình bày bên dưới. Hàm khả năng xảy ra được biểu diễn bằng hàm mật độ xác suất Gaussian √ ( √ ) (2.8.26) Trong đó Eb là năng lượng nhận được /bit của từ mã và N0 là mật độ phổ nhiễu một phía. Bit nhận được là biến ngẫu nhiên Gaussian có trung bình là √ và phương sai là N/2. Hàm log của khả năng xảy ra có thể được định nghĩa là: ∑ (∑ ) Thực hiện bộ giải mã Viterbi trên FPGA Trang 50 Chương 2: Thuật giải mã Viterbi ∑ (∑* ( √ ) √ + ) ∑ (∑( √ ) ) Trong đó ∑ (∑ ) Trong đó C1 và C2 là hằng số, không phải là hàm của y (2.8.28) Từ đây metric bit được định nghĩa là (2.8.29) Thuật toán Viterbi quyết định mềm có thể được thực hiện như sau: Sk, t là trạng thái trong biểu đồ trellis tương ứng với trạng thái Sk tại thời điểm t. Mỗi trạng thái trong trellis được gán một giá trị là V(Sk, t ). 1. (a) Khởi tạo t = 0 (b) Khởi tạo V(S0, 0) = 0 và tất cả các V khác V(Sk, t) = +00 2. (a) Lấy t = t + 1 (b) Tính các metric đường thành phần cho tất cả các đường đi đến trạng thái Sk tại thơi điểm t. Đầu tiên tìm metric nhánh thứ t ∑ (2.8.30) Metric này được tính từ sự tương quan của và , ∑ . Thứ 2, tính metric đường từng phần thứ t ∑ (2.8.31) Metric này được tính từ (2.8.32) Thực hiện bộ giải mã Viterbi trên FPGA Trang 51 Chương 2: Thuật giải mã Viterbi 3. (a) Lấy V(Sk,t ) đến metric đường từng phần tốt nhất là trạng thái Sk tại thời điểm t. Metric đường từng phần tốt nhất là metric đường từng phần có giá trị lớn nhất. (b) Nếu có một thay đổi cho metric đường thành phần tốt nhất, thì sau đó bất kỳ một trong những metric đường từng phần có thể được chọn. 4. Lưu trữ metric đường từng phần và các đường trạng thái và các bit tồn tại liên kết của nó. 5. Nếu t < L + m – 1, trở về bước 2. Thông thường đối với giải mã quyết định mềm, trong kênh nhiễu Gaussian thì độ lợi mã hóa khoảng 2dB so với giải mã quyết định cứng. 2.8.3 Ưu điểm của giải mã quyết định mềm so với giải mã quyết định cứng Với việc thuật toán giải mã quyết định mềm chia ra nhiều mức để nhận dạng tín hiệu thu được thì độ tin cậy giải mã sẽ đảm bảo hơn so với giải mã quyết định cứng chỉ có 2 mức duy nhất cho tín hiệu nhận được. Để thấy rõ ưu điểm của thuật toán quyết định mềm so với quyết định cứng, chúng ta xét một ví dụ đơn giản sử dụng bộ mã parity sau: Bảng 2.10: Ví dụ với bộ mã parity Bit vào 1 Bit vào 2 Bit parity đƣợc tạo bởi bộ mã hóa Từ mã 0 0 0 0 0 1 1 011 1 0 1 101 1 1 0 110 Tất cả các trạng thái có thể được tạo bởi bộ mã hóa là 000, 011, 101, 110. Bây giờ chúng ta sẽ tiến hành truyền bản tin “01” xuyên qua kênh truyền. Đối với giải mã quyết định cứng: Giả sử hệ thống thông tin của chúng ta bao gồm một bộ mã hóa tạo kiểm parity, kênh truyền, và một bộ thu giải mã quyết định cứng Với bản tin “01” đưa đến bộ mã hóa parity, từ mã ngõ ra ta nhận được sẽ là “011”, Thực hiện bộ giải mã Viterbi trên FPGA Trang 52 Chương 2: Thuật giải mã Viterbi Hình 2.27 Mô tả giải mã quyết định cứng với bộ mã parity Từ mã này giả sử sẽ được truyền qua kênh truyền như sau: “0” được truyền dưới dạng điện áp “0 volt”, “1” được truyền với điện áp “1 volt”. Kênh truyền có nhiễu sẽ làm suy giảm tín hiệu và tín hiệu thu được tại bộ nhận sẽ bị suy giảm (dạng sóng màu đỏ). Bộ giải mã quyết định cứng thực hiện quyết định dựa trên một mức điện áp ngưỡng. Với trường hợp này, điện áp ngưỡng của chúng ta sẽ là 0,5 volt (nằm giữa các mức 0V và 1V). Ở mỗi thời điểm lấy mẫu của bộ thu (như hình trên), bộ tách sóng quyết định cứng sẽ quyết định trạng thái đó là mức “0” nếu mức áp thu được là nhỏ hơn 0,5V và sẽ chọn là mức “1” nếu áp thu được lớn hơn 0,5V. Do đó, ngõ ra của khối quyết định cứng trên sẽ là “001”. Có lẽ ngõ ra “001” này là vô lý khi so sánh với các từ mã có thể như bảng ở trên, do đó, các bit của từ mã trên có thể đã sai do tác động trên kênh truyền. Bộ giải mã quyết định cứng so sánh ngõ ra của khối giải mã quyết định cứng trên với tất cả các trạng thái có thể của từ mã và tính toán khoảng cách Hamming bé nhất cho mỗi trường hợp. Mô tả như bảng bên dưới: Bảng 2.11: Tính toán khoảng cách Hamming cho quyết định cứng Tất cả từ mã có thể Ngõ ra quyết định cứng Khoảng cách Hamming 000 001 1 011 001 1 101 001 1 110 001 3 Công việc của bộ giải mã là chọn ta từ mã đã phát đi dựa trên khoảng cách Hamming bé nhất. Tuy nhiên, ở đây có tới 3 trường hợp cho ra khoảng cách Thực hiện bộ giải mã Viterbi trên FPGA Trang 53 Chương 2: Thuật giải mã Viterbi Hamming đều là 1. Do đó, bộ giải mã có thể sẽ chọn ngẫu nhiên một trong 3 trường hợp trên làm quyết định cuối cùng. Vì vậy, xác xuất đúng chỉ là 1/3. Đối với bộ giải mã quyết định mềm: Sự khác biệt chủ yếu của thuật toán quyết định cứng và quyết định mềm như ta đã biết chính là thuật toán giải mã quyết định mềm sử dụng khoảng cách Euclidean thay vì khoảng cách Hamming. Với cùng một bộ mã hóa và kênh truyền, giờ ta sẽ xem hiệu quả của quyết định mềm so với quyết định cứng. Hình 2.28 Mô tả giải mã quyết định mềm với bộ mã parity Mức điện áp của tín hiệu nhận được tại mỗi thời điểm lấy mẫu như hình trên. Khối quyết định cứng tính toán khoảng cách Euclidean của tất cả các từ mã có thể với tín hiệu nhận được. Bảng 2.12: Tính toán khoảng cách Euclidean cho quyết định mềm Từ mã có thể Mức điện áp tại mỗi thời điểm lấy mẫu của dạng sóng nhận đƣợc Tính toán khoảng cách Euclidean Khoảng cách Euclidean 0 0 0 ( 0V 0V 0V ) 0.2V 0.4V 0.7V (0-0.2) 2 + (0-0.4) 2 + (0-0.7) 2 0.69 0 1 1 ( 0V 1V 1V ) 0.2V 0.4V 0.7V (0-0.2) 2 + (1-0.4) 2 + (1-0.7) 2 0.49 1 0 1 ( 1V 0V 1V ) 0.2V 0.4V 0.7V (1-0.2) 2 + (0-0.4) 2 + (1-0.7) 2 0.89 1 1 0 ( 1V 1V 0V ) 0.2V 0.4V 0.7V (1-0.2) 2 + (1-0.4) 2 + (0-0.7) 2 1.49 Thực hiện bộ giải mã Viterbi trên FPGA Trang 54 Chương 2: Thuật giải mã Viterbi Khoảng cách Euclidean bé nhất là 0,49 tương ứng với từ mã “011”, chính là từ mã mà chúng ta đã truyền đi. Bộ giải mã quyết định mềm sẽ chọn nó làm từ mã giải được ở ngõ ra, nếu bộ tạo kiểm parity không thể sửa lỗi thì lưu đồ giải mã quyết định mềm này sẽ giúp khôi phục tin tức trong trường hợp này. Qua ví dụ trên ta có thể thấy được ưu điểm của giải mã quyết định mềm so với giải mã quyết định cứng. Tuy nhiên, với trường hợp trên, người ta cũng có thể nhanh chóng tìm ra lỗi của phương pháp xử lí này nếu các mức điện áp tương ứng là 0,2V, 0,4V và 0,6V. Đó là bởi vì bộ tạo kiểm parity không có khả năng sửa lỗi mà chỉ có thể phát hiện lỗi 1 bit. Khi đó, sử dụng bộ giải mã quyết định mềm sẽ nâng cao hiệu quả của bộ nhận chừng 2 dB so với bộ giải mã quyết định cứng. 2.9 Xác suất lỗi Có 2 xác suất lỗi liên quan đến mã tích chập, là xác suất lỗi sự kiện đầu tiên và xác suất lỗi bit. Xác suất lỗi sự kiện đầu tiên, Pe, là xác suất lỗi mà một lỗi bắt đầu tại thời điểm đặc biệt. Xác suất lỗi bit, Pb, là số các lỗi bit ở chuỗi được mã hóa. Đối với giải mã quyết định cứng, xác suất lỗi bit và xác suất lỗi sự kiện đầu tiên được định nghĩa như sau: √ (2.9.1) Và √ (2.9.2) Trong đó, (√ ) (2.9.3) Và ∫ √ (2.9.4) Đối với giải mã quyết định mềm, xác suất lỗi sự kiện đầu tiên và xác suất lỗi bit được định nghĩa như sau: (2.9.5) Và (2.9.6) 2.10 Ưu nhược điểm của thuật toán giải mã Viterbi 2.10.1 Ưu điểm  Thuật toán Viterbi là thuật giải mã có nhớ nên việc giải mã có độ chính xác cao.  Tốc độ xử lí của mộ giải mã Viterbi cao hơn nhiều so với bộ giải mã tuần tự vì ở cùng một thời điểm, bộ giải mã Viterbi giải quyết hết tất cả các nhánh còn bộ giải mã tuần tự chỉ chọn ngẫu nhiên một nhánh nên nó sẽ mất thời gian nếu sự lựa chọn trước đó là không đúng. Thực hiện bộ giải mã Viterbi trên FPGA Trang 55 Chương 2: Thuật giải mã Viterbi 2.10.2 Nhược điểm  Thuật toán giải mã Viterbi dựa trên thuật giải mã giống nhau lớn nhất (ML- Maximum likelihood), thuật toán này lại phải dựa trên các nguyên lý sau để việc giải mã được chính xác:  Lỗi xảy ra phải không thường xuyên, xác suất lỗi phải nhỏ  Xác suất lỗi kép phải thấp hơn nhiều so với lỗi 1 bit, do đó lỗi phải được phân bố một cách ngẫu nhiên. Do vậy, với kênh truyền có xác suất lỗi lớn và thường xuyên, lỗi nhiều bit liên tiếp thì hiệu quả của việc giải mã sẽ không như mong muốn.  Một nhược điểm nữa là thuật toán giải mã Viterbi sử dụng bộ nhớ để ghi lại các trạng thái và thông số metric nên cần có bộ nhớ cho giải mã, bộ giải mã càng phức tạp thì dung lượng bộ nhớ càng lớn.  Không thích hợp với các mã có chiều dài ràng buộc dài và tỉ số S/N lớn (chỉ thích hợp với bộ giải mã tuần tự). Thực hiện bộ giải mã Viterbi trên FPGA Trang 56 Chương 3: Mô phỏng thuật toán Viterbi dùng Matlab CHƢƠNG 3 MÔ PHỎNG THUẬT GIẢI MÃ VITERBI BẰNG MATLAB 3.1 Giới thiệu Matlab là một phần mềm được ứng dụng rộng rãi trong nhiều lĩnh vực như viễn thông, cơ điện, hệ thống điều khiển tự động …, trong đó ứng dụng mô phỏng xử lý tín hiệu trong viễn thông là một ứng dụng mạnh nhất của Matlab. Matlab tích hợp khoảng hơn 400 hàm cho phép người lập trình sử dụng cho công việc một cách hiệu quả và nhanh chóng. Với đề tài này, để mô phỏng quá trình mã hóa dùng mã chập, truyền tín hiệu trên kênh truyền có nhiễu và sử dụng thuật toán Viterbi để giải mã hóa, người thực hiện đề tài đã sử dụng các hàm có sẵn trong Matlab để thực hiện. Để dễ dàng hơn cho việc quan sát và trình bày, tác giả đã sử dụng giao diện đồ họa GUI để mô phỏng thuật giải viterbi. Quá trình mô phỏng sẽ được trình bày rõ ràng trong phần sau. 3.2 Sơ đồ khối hệ thống Hình 3.1: Sơ đồ khối hệ thống Tín hiệu sau khi được số hóa thành các bit, các bit này được đưa đến bộ mã hóa mã chập. Sau khi được mã hóa, tín hiệu (các bit) được truyền trên kênh truyền có nhiễu, ở đây tác giả chỉ xét nhiễu Gauss trắng. Tín hiệu đã bị thay đổi bởi nhiễu được thu và giải mã nhờ bộ giải mã Viterbi. Nhờ thuật toán Viterbi, tín hiệu được giải mã sẽ gần giống nhất với tín hiệu ban đầu. Khối mã hóa mã chập Khối giải mã Viterbi Ngõ ra bit Ngõ vào bit Bit mã hóa Bit nhận được AWGN Kênh truyền Thực hiện bộ giải mã Viterbi trên FPGA Trang 57 Chương 3: Mô phỏng thuật toán Viterbi dùng Matlab 3.3 Lưu đồ mô phỏng Hình 3.2: Lưu đồ mô phỏng 3.3.1 Khối tạo bit ngõ vào Tác giả đưa ra hai lựa chọn cho việc tạo bit tín hiệu ngõ vào. Thứ nhất là tạo bit ngẫu nhiên theo số lượng bit nhập từ người dùng, và thứ hai là nhập trực tiếp chuỗi bit vào. Để tạo bit vào ngẫu nhiên, trong Matlab tác giả sử dụng hàm randint. inbits = randint(1, numbit ) ; với inbits là chuỗi bit ngõ vào, numbit là số lượng bit ngõ vào được nhập bởi người dùng trên giao diện GUI. Hàm randint với 2 thông số sẽ mặc định tạo một Mã hóa mã chập Cộng nhiễu Gauss trắng Lượng tử bit nhận được Giải mã Viterbi Tính và vẽ BER Xây dựng sơ đồ trellis Xác định đa thức sinh và chiều dài ràng buộc Tạo bit Khối tạo bit ngõ vào Khối mã hóa Khối giải mã Thực hiện bộ giải mã Viterbi trên FPGA Trang 58 Chương 3: Mô phỏng thuật toán Viterbi dùng Matlab ma trận số nhị phân với chiều của ma trận tương ứng với 2 thông số đó. Kích thước tối đa có thể tạo ra phụ thuộc vào bộ nhớ dành cho chương trình. Với câu lệnh như trên thì numbit tối đa chỉ là 106. 3.3.2 Khối mã hóa Đối với bộ mã hóa mã chập, như đã giới thiệu, có rất nhiều cách để người ta quy ước cho một bộ mã hóa mã chập dựa trên số thanh ghi, ngõ vào, ngõ ra, đa thức sinh, tốc độ bộ mã..v.v. và tương ướng với mỗi bộ mã có một phương pháp tính toán riêng. Ở đây tác giả mô tả việc tính toán mã chập dựa trên bộ mã được quy ước bởi các nhà sản xuất chip thực hiện mã chập bao gồm các thông số: chiều dài ràng buộc K và tốc độ của bộ mã R. Và G1 và G2 là các đa thức sinh, được nhập bởi người sử dụng. Để tạo sơ đồ trellis, trong Matlab tác giả sử dụng hàm poly2trellis: trellis = poly2trellis (len, [g1 g2]); Dùng hàm convenc để mã hóa mã chập tín hiệu: encbits = convenc(inpbits,trellis); 3.3.3 Khối cộng nhiễu Gausse trắng Khối này mô phỏng cho việc tín hiệu bị can nhiễu khi truyền trên kênh truyền. Tín hiệu bị cộng nhiễu Gauss với thông số SNR đã xác định trước. Sử dụng hàm awgn để cộng nhiễu vào tín hiệu: awgnbits = awgn(encbits,snr,measured); 3.3.4 Khối giải mã Tín hiệu sau khi được cộng nhiễu được đưa đến bộ thu, tại đây tín hiệu được lượng tử trước khi sử dụng thuật toán viterbi để giải mã. Tùy vào kiểu quyết định giải mã mà sử dụng các lượng tử khác nhau. Với quyết định cứng Tín hiệu thu được lượng tử về 2 mức 0 và 1 tương ứng với tín hiệu có mức điện áp nhỏ hơn và lớn hơn 0. Sử dụng hàm quantiz để lượng tử tín hiệu. partition = [0]; codebook = [0 1]; quanbits = quantiz(awgnbits,partition,codebook); Sử dụng hàm vitdec với quyết định cứng để giải mã Viterbi decbits = vitdec(quanbits,trellis,numbit-1,‟term‟,‟hard‟); Thực hiện bộ giải mã Viterbi trên FPGA Trang 59 Chương 3: Mô phỏng thuật toán Viterbi dùng Matlab Với quyết định mềm Tín hiệu thu được lượng tử về 8 mức và việc sử dụng hàm quantiz như sau partition = [-.8571 -.5714 -.2857 0 .2857 .5714 .8571]; codebook = [-.99 -.8571 -.5714 -.2857 0 .2857 .5714 .8571]; quanbits = quantiz(awgnbits,partition,codebook); Sử dụng hàm vitdec với quyết định mềm decbits = vitdec(quanbits,trellis,numbit -1,‟term‟,‟soft‟,3); 3.3.5 Tính toán và vẽ BER Tỉ số bit lỗi là số tỉ số bit lỗi sau khi giải mã so với tổng số bit ngõ vào. Trong matlab tác giả sử dụng hàm semilogy để vẽ BER semilogy(Eb_N0_dB,ratioerr_comp,‟mp-„,‟LineWidth‟,2); 3.4 Hình ảnh về chương trình mô phỏng Hình 3.3: Giao diện khởi đầu chương trình mô phỏng Thực hiện bộ giải mã Viterbi trên FPGA Trang 60 Chương 3: Mô phỏng thuật toán Viterbi dùng Matlab Hình 3.4: Giao diện chương trình mô phỏng 1 Hình 3.5: Giao diện chương trình mô phỏng 2 Thực hiện bộ giải mã Viterbi trên FPGA Trang 61 Chương 3: Mô phỏng thuật toán Viterbi dùng Matlab Hình 3.6: Nhập bit ngẫu nhiên – Quyết định mềm Hình 3.7: BER của quyết định mềm Thực hiện bộ giải mã Viterbi trên FPGA Trang 62 Chương 3: Mô phỏng thuật toán Viterbi dùng Matlab Hình 3.8: Nhập bit ngẫu nhiên – Quyết định cứng Hình 3.9: BER của quyết định cứng Thực hiện bộ giải mã Viterbi trên FPGA Trang 63 Chương 3: Mô phỏng thuật toán Viterbi dùng Matlab Hình 3.10: So sánh BER của cả quyết định cứng và mềm Hình 3.11: Tự nhập bit vào – Quyết định mềm Thực hiện bộ giải mã Viterbi trên FPGA Trang 64 Chương 3: Mô phỏng thuật toán Viterbi dùng Matlab Nhận xét : - Từ các hình 3.6 và 3.8 ta có thể thấy rằng, với cùng một số lượng bit vào như nhau thì giải mã quyết định cứng sẽ giải mã với số bit sai nhiều hơn so với giải mã quyết định mềm. Bởi vì như chúng ta đã đề cập trước đó, giải mã quyết định mềm sử dụng lượng tử hóa nhiều bit, do đó nó tạo độ tin cậy khi giải mã cao hơn so với giải mã quyết định mềm chỉ sử dụng lượng tử 1 bit. - Tỷ số tín hiệu/nhiễu SNR càng cao thì điều đó có nghĩa kênh truyền càng ít nhiễu, khi đó, giải mã quyết định cứng và mềm sẽ cho kết quả giải mã là gần như nhau. - Hình 3.10 cho ta thấy được giản đồ BER của cả hai loại quyết định. Đường BER của giải mã quyết định mềm luôn nằm thấp hơn đường BER của giải mã quyết định cứng. Điều đó có nghĩa là với cùng một tỷ số Eb/N0 thì giải mã quyết định mềm luôn có BER nhỏ hơn so với giải mã quyết định cứng. Do đó, xác suất sai bit sẽ nhỏ hơn. - Vì giải mã quyết định mềm sử dụng lượng tử nhiều bit nên bộ nhớ cần để lưu trữ cho việc giải mã quyết định mềm sẽ lớn hơn nhiều so với khi giải mã quyết định cứng. Thực hiện bộ giải mã Viterbi trên FPGA Trang 65 Chương 4: Xây dựng thuật toán giải mã Viterbi trên Kit DE2 CHƢƠNG 4 XÂY DỰNG THUẬT GIẢI MÃ VITERBI TRÊN KIT DE2 4.1 Giới thiệu sơ lược KIT DE2 và phần mềm Quartus 4.1.1 KIT DE2 của Altera 4.1.1.1 Tổng quan kit DE2 KIT DE2 có rất nhiều tài nguyên cho phép người sử dụng thực thi rất nhiều mạch ứng dụng từ các mạch đơn giản cho tới các dự án lớn có độ phức tạp cao. Hình 4.1 KIT DE2 của Altera Một số tài nguyên trên Kit DE2:  Chip FPGA Cyclone II 2C35.  Thiết bị cấu hình nối tiếp EPCS16.  Cổng USB cho lập trình và điều khiển, hỗ trợ cả 2 chế độ JTAG và nối tiếp (AS).  512 Kbyte SRAM. Thực hiện bộ giải mã Viterbi trên FPGA Trang 66 Chương 4: Xây dựng thuật toán giải mã Viterbi trên Kit DE2  8 Mbyte SDRAM.  4 Mbyte bộ nhớ Flash.  4 nút nhấn và 18 Switch.  18 Led đỏ và 9 led xanh.  2 bộ tạo dao động 50Mhz và 27 Mhz.  Chip codec Audio 24 bit và chip DAC video 10 bit, cổng ethernet 10/100  Cổng RS232 9 chân và cổng PS/2 cho kết nối chuột và bàn phím.  Bộ nhận tín hiệu hồng ngoại.  Và một số chức năng khác... Sơ đồ khối Hình 4.2 Sơ đồ khối KIT DE2 Chip Cyclone EPCS16:  33,216 Logic Elements  105 M4K RAM blocks  Tổng cộng 483,840 RAM bits Thực hiện bộ giải mã Viterbi trên FPGA Trang 67 Chương 4: Xây dựng thuật toán giải mã Viterbi trên Kit DE2  4 PLLs  475 chân I/O 4.1.1.2 Sử dụng nút nhấn và Switch KIT DE2 có 4 nút nhấn, mỗi nút nhấn được chống dội bằng mạch Smith trigger như hình 4.3. Các ngõ ra của mạch Smith Trigger được gọi là KEY0,...,KEY3 được kết nối trực tiếp đến Cyclone II FPGA. Các nút nhấn cung cấp mức logic cao (3.3V) khi không nhấn và cung cấp logic thấp (0V) khi được nhấn. Hình 4.3: Chống dội phím nhấn Có tổng cộng 18 Switch gạt trên kit DE2, mỗi switch được kết nối trực tiếp đến chân của Cyclone II FPGA. Khi switch ở vị trí DOWN (gần cạnh của board), nó cung cấp mức logic thấp (0V) đến FPGA, và khi nó được gạt đến vị trí UP thì cho ra mức logic cao (3.3 V). Có 27 led đơn trên board, 18 led đỏ và 9 led xanh, mỗi led cũng được kết nối trực tiếp đến 1 chân của FPGA. Led sáng khi nhận được mức logic cao từ FPGA, ngược lại led tắt. Có 8 Led 7 đoạn trên Kit chia làm 2 cặp và một nhóm 4 led, led sáng mức thấp. Mỗi đoạn của led được kết nối trực tiếp đến 1 chân của FPGA. Bảng 4.1: Thứ tự kết nối phím nhấn với các chân của FPGA Thực hiện bộ giải mã Viterbi trên FPGA Trang 68 Chương 4: Xây dựng thuật toán giải mã Viterbi trên Kit DE2 4.1.1.3 Sử dụng LCD LCD có phông chữ cài sẵn có thể dùng để hiển thị các văn bản bằng cách gởi các lệnh đến bộ điều khiển hiển thị (HD44780). Bảng 4.2: Gán chân FPGA cho màn hình LCD 4.1.2 Phần mềm lập trình Quatus II Quartus II là công cụ phần mềm phát triển của hãng Altera, cung cấp môi trường thiết kế toàn diện cho các thiết kế SOPC (hệ thống trên 1 chip khả trình - system on a programmable chip). Đây là phần mềm đóng gói tích hợp đầy đủ phục vụ cho thiết kế logic với các linh kiện logic khả trình PLD của Altera, gồm các dòng APEX, Cyclone, FLEX, MAX, Stratix... Quartus cung cấp các khả năng thiết kế logic sau:  Môi trường thiết kế gồm các bản vẽ, sơ đồ khối, công cụ soạn thảo các ngôn ngữ: AHDL, VHDL, và Verilog HDL.  Thiết kế LogicLock.  Là công cụ mạnh để tổng hợp logic.  Khả năng mô phỏng chức năng và thời gian.  Phân tích thời gian.  Phân tích logic nhúng với công cụ phân tích SignalTap@ II. Thực hiện bộ giải mã Viterbi trên FPGA Trang 69 Chương 4: Xây dựng thuật toán giải mã Viterbi trên Kit DE2  Cho phép xuất, tạo và kết nối các file nguồn để tạo ra các file chương trình.  Tự động định vị lỗi.  Khả năng lập trình và nhận diện linh kiện.  Phần mềm Quartus II sử dụng bộ tích hợp NativeLink@ với các công cụ thiết kế cung cấp việc truyền thông tin liền mạch giữa Quartus với các công cụ thiết kế phần cứng EDA khác.  Quartus II cũng có thể đọc các file mạch (netlist) EDIF chuẩn, VHDL và Verilog HDL cũng như tạo ra các file netlist này.  Quartus II có môi trường thiết kế đồ họa giúp nhà thiết kế dễ dàng viết mã, biên dịch, soát lỗi, mô phỏng... Với Quartus có thể kết hợp nhiều kiểu file trong 1 dự án thiết kế phân cấp. Có thể dùng bộ công cụ tạo sơ đồ khối (Quartus Block Editor) để tạo ra sơ đồ khối mô tả thiết kế ở mức cao, sau đó dùng các sơ đồ khối khác, các bản vẽ như: AHDL Text Design Files (.tdf), EDIF Input Files (.edf), VHDL Design Files (.vhd), và Verilog HDL Design Files (.v) để tạo ra thành phần thiết kế mức thấp. Quartus II cho phép làm việc với nhiều file ở cùng thời điểm, soạn thảo file thiết kế trong khi vẫn có thể biên dịch hay chạy mô phỏng các dự án khác. Công cụ biên dịch Quartus II nằm ở trung tâm hệ thống, cung cấp quy trình thiết kế mạnh cho phép tùy biến để đạt được thiết kế tối ưu trong dự án. Công cụ định vị lỗi tự động và các bản tin cảnh báo khiến việc phát hiện và sửa lỗi trở nên đơn giản hơn. 4.2 Giải quyết vấn đề 4.2.1 Giải mã viterbi quyết định cứng Giờ ta sẽ đi giải quyết thuật toán việc giải mã Viterbi (quyết định cứng) cho bộ mã tốc độ ½ với K= 3 và bộ phát mã (hay đa thức sinh) là (5,7)8 đã nhắc đến trong chương 4 về thuật toán Viterbi. Ta đã biết rằng, với trường hợp bộ mã này thì nếu có N bit mã hóa ngõ vào thì sẽ phải tìm từ 2N sự kết hợp có thể (tương ứng một bit vào sẽ có 2 bit ra). Điều này trở nên vô cùng phức tạp nếu N càng lớn. Tuy nhiên, ông Andrew J Viterbi trong một ghi chép về “Error bounds for convolutional codes and an asymptotically optimum decoding algorithm”, IEEE Transactions on Information Theory 13(2):260–269, tháng 4 năm 1967 đã mô tả một sơ đồ để kéo giảm tính phức tạp đó đến mức có thể điều khiển được. Một vài giả thuyết quan trọng được đưa ra như sau: - Như chúng ta thấy trong bảng 4.1 và hình 4.2 thì bất kì một trạng thái nào cũng đều đến từ chỉ 2 trạng thái có thể trước