zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Luận Văn - Báo Cáo

» Công nghệ thông tin

Đồ án tốt nghiệp: Thực hiện bộ giải mã Viterbi trên FPGA

Chia sẻ: Gacon | Ngày: | Loại File: PDF | Số trang:124

Báo xấu

627
lượt xem 175
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Đồ án tốt nghiệp: Thực hiện bộ giải mã VITERBI trên FPGA có cấu trúc gồm 5 chương trình bày về tổng quan hệ thống thông tin số, thuật toán Viterbi, xây dựng thuật giải Viterbi dùng Matlab, xây dựng thuật giải Viterbi trên KITDE2, đá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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Đồ án tốt nghiệp: Thực hiện bộ giải mã Viterbi trên FPGA

Thực hiện bộ giải mã Viterbi trên FPGA Trang i 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 Phần A: Giới thiệu
Thực hiện bộ giải mã Viterbi trên FPGA Trang ii BỘ GIÁO DỤC VÀ ĐÀO TẠO CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM TRƯỜNG ĐẠI HỌC SƯ PHẠM KỸ THUẬT Độc lập - Tự do - Hạnh phúc THÀNH PHỐ HỒ CHÍ MINH  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: 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. o 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 Phần A: Giới thiệu
Thực hiện bộ giải mã Viterbi trên FPGA Trang iii 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 Phần A: Giới thiệu
Thực hiện bộ giải mã Viterbi trên FPGA Trang iv 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 Phần A: Giới thiệu
Thực hiện bộ giải mã Viterbi trên FPGA Trang v 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ón g để 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ố Phần A: Giới thiệu
Thực hiện bộ giải mã Viterbi trên FPGA Trang vi 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 Phần A: Giới thiệu
Thực hiện bộ giải mã Viterbi trên FPGA Trang vii 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 Ưu nhược điểm của mã chập ................................................................ 30 2.5 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 Phần A: Giới thiệu
Thực hiện bộ giải mã Viterbi trên FPGA Trang viii 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 Phần A: Giới thiệu
Thực hiện bộ giải mã Viterbi trên FPGA Trang ix 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 Phần A: Giới thiệu
Thực hiện bộ giải mã Viterbi trên FPGA Trang x 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 độ R  1 / 2 Hình 2.2: Bộ mã hóa hệ thống với R  1 / 2 Hình 2.3: Bộ mã hóa hệ thống Hình 2.4: Sơ đồ bộ mã hóa hệ thống R  2 / 3 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 Phần A: Giới thiệu
Thực hiện bộ giải mã Viterbi trên FPGA Trang xi 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 Phần A: Giới thiệu
Thực hiện bộ giải mã Viterbi trên FPGA Trang xii 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 A: Giới thiệu
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Ố 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. 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 15 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. 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 16 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, 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 17 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 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 18 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. 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 19 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 Chương 2: Thuật giải mã Viterbi

CÓ THỂ BẠN MUỐN DOWNLOAD

LV.09: Bộ Luận Văn Tốt Nghiệp Chuyên Ngành Quản Trị Kinh Doanh

81 tài liệu

1641 lượt tải

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.