<< 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
ThS. Lê Minh Thành KS. Đặng Phƣớc Hải Trang Huỳnh Minh Khả 06117029 Lê Duy 06117010
GVHD: SVTH: MSSV: SVTH: MSSV:
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
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.
Phần A: Giới thiệu
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
CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM Độc lập - Tự do - Hạnh phúc
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
QUYẾT ĐỊNH GIAO ĐỀ TÀI
MSSV: 06117029 MSSV: 06117010
Huỳnh Minh Khả Lê Duy Công Nghệ Điện tử - Viễn thông
Họ và tên sinh viên: Ngành: 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….
Phần A: Giới thiệu
Chủ nhiệm bộ môn
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
…………………………………………………………
………………………………………………………………
………………………………………………………………
………………………………………………………………
………………………………………………………………
………………………………………………………………
………………………………………………………………
………………………………………………………………
………………………………………………………………
………………………………………………………………
………………………………………………………………
………………………………………………………………
………………………………………………………………
……………………………………………
Phần A: Giới thiệu
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
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
Phần A: Giới thiệu
Giáo viên phản biện
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ó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:
Phần A: Giới thiệu
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
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.
Phần A: Giới thiệu
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
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
Phần A: Giới thiệu
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
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
Phần A: Giới thiệu
4.4 Kết quả ................................................................................................. 82
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
Phần A: Giới thiệu
II. Tài liệu tham khảo ................................................................................ 123
Thực hiện bộ giải mã Viterbi trên FPGA
Trang x
LIỆT KÊ HÌNH
có phần cứng đơn giản
Phần A: Giới thiệu
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 độ Hình 2.2: Bộ mã hóa hệ thống với Hình 2.3: Bộ mã hóa hệ thống Hình 2.4: Sơ đồ bộ mã hóa hệ thống 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
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ó
Phần A: Giới thiệu
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Ố
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
Chương 1: Tổng quan về hệ thống thông tin số
kênh truyền.
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
Chương 1: Tổng quan về hệ thống thông tin số
1. Mã khối.
Thực hiện bộ giải mã Viterbi trên FPGA
Trang 16
2. Mã trellis.
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ệ.
Chúng phân tích ba đặc tính sau của mã (nói chung) 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,
Chương 1: Tổng quan về hệ thống thông tin số
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
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.
Chương 1: Tổng quan về hệ thống thông tin số
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
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.
Chương 1: Tổng quan về hệ thống thông tin số
Đề 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
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ả.
Chương 2: Thuật giải mã Viterbi
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
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ã
đượ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:
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à
. Như vậy
Đố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)]
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 độ
(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.
k = mk+ mk-1 + mk-2
C(1)
k = mk + mk-2 .
và C(2)
Chương 2: Thuật giải mã Viterbi
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
độ 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:
g1(x) = 1 + x +x2.
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+ x4+ x6 [[ ]].
Các đầu ra sẽ là:
C(1)(x) = m(x)g1(x) = (1+ x +x4 + x6 )(1+ x + x2) = 1 +x3 +x4 +x5 +x7 + x8 C(2)(x) = m(x)g2(x) = (1+ x +x4 + x6 )(1+ x2) = 1+x + x2 +x3 +x4 +x8
có một hàm truyền ma trận k × n (x) (còn Với mỗi mã chập tốc độ
ở ví dụ trên ta có:
được gọi là ma trận truyền). Với mã tố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:
Chương 2: Thuật giải mã Viterbi
Hình 2.2: Bộ mã hóa hệ thống với
Thực hiện bộ giải mã Viterbi trên FPGA
Trang 22
k và C(2)
k có
Với dòng vào: m (x) = 1+ x + x 2 + x3+ x 4 + x8 các đầu ra C(1)
dạng:
k = m(x) =1 + x +x2 + x3 + x 4 + x8
C(1)
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 độ có ma trận truyền sau:
Chương 2: Thuật giải mã Viterbi
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
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 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+ x5+ x7+ …, 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ỷ
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) vào các chuỗi Laurent C(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)). Chương 2: Thuật giải mã Viterbi
Thực hiện bộ giải mã Viterbi trên FPGA
Trang 24
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).
12... k
Chuỗi thông tin
1 2... k
đầu vào k bit
1 2 ... k
Chuỗi mã n bit
Hình 2.5: Sơ đồ tổng quát bộ mã chập.
Chương 2: Thuật giải mã Viterbi
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ỉ
Thực hiện bộ giải mã Viterbi trên FPGA
Trang 25
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à:
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:
Chương 2: Thuật giải mã Viterbi
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
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:
Có thể biểu diễn dưới dạng đa thức sinh là: G(D) = [1 1+D2 1+D+D2]
Chương 2: Thuật giải mã Viterbi
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
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:
Chương 2: Thuật giải mã Viterbi
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
Hình 2.8: Sơ đồ hình cây của bộ mã (2,1,3)
*Sơ đồ hình lƣới:
Chương 2: Thuật giải mã Viterbi
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
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:
Chương 2: Thuật giải mã Viterbi
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
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.
Chương 2: Thuật giải mã Viterbi
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
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
Chương 2: Thuật giải mã Viterbi
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
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.
Chương 2: Thuật giải mã Viterbi
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
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.
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:
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.
Chương 2: Thuật giải mã Viterbi
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
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 Chương 2: Thuật giải mã Viterbi
Thực hiện bộ giải mã Viterbi trên FPGA
Trang 35
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.
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.
Chương 2: Thuật giải mã Viterbi
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
đườ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.
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
Chương 2: Thuật giải mã Viterbi
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ú ý 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:
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:
Hình 2.21: Tất cả dữ liệu đã được giải mã và sửa sai chính xác
Chương 2: Thuật giải mã Viterbi
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
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.
Chương 2: Thuật giải mã Viterbi
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
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. Chương 2: Thuật giải mã Viterbi
Thực hiện bộ giải mã Viterbi trên FPGA
Trang 40
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:
Ở 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.
Chương 2: Thuật giải mã Viterbi
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
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 2K. 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ã.
Chương 2: Thuật giải mã Viterbi
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
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ó
Hình 2.22: Bộ mã tốc độ 1/3 và K= (7,7,5)
Chương 2: Thuật giải mã Viterbi
thể được mã hóa sử dụng bộ mã hóa như bên dưới:
Thực hiện bộ giải mã Viterbi trên FPGA
Trang 43
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à
Chương 2: Thuật giải mã Viterbi
(2.8.1)
Thực hiện bộ giải mã Viterbi trên FPGA
Trang 44
Và chuỗi được mã hóa là
(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ự.
(2.8.3)
Và
(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,
(2.8.5)
(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(/),
(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:
(2.8.8)
Chương 2: Thuật giải mã Viterbi
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
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)
] (2.8.11)
[
(2.8.10)
Và Kết quả metric bit là
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
0 1 Bit được giải mã
(j) = 0 và bit nhận được ri
(j) = 0 thì ước lượng M(yi
(j) | ri
(j) = 0 và bit nhận được ri
(j) | ri
1 0 Bit được giải mã
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ụ (j)) = nếu bit được giải mã yi (j) = 1 thì ước lượng 0. Tuy nhiên, nếu bit được giải mã yi (j)) = 1. Như vậy điều này liên quan đến khoảng cách Hamming và được M(yi 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:
Chương 2: Thuật giải mã Viterbi
(2.8.12)
Trang 46
Thực hiện bộ giải mã Viterbi trên FPGA
Và
(2.8.13)
]
(2.8.14) [
Kết quả metric bit cách 2 là
Bảng 2.9: Các giá trị metric bit cách 2
Bit nhận Bit nhận
1 0 Bit được giải mã
0 1 Bit được giải mã
Đố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 đó: ∑ ∑ 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.
Chương 2: Thuật giải mã Viterbi
(2.8.18)
Thực hiện bộ giải mã Viterbi trên FPGA
Trang 47
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.
(2.8.19) Đầu tiên, tìm metric nhánh thứ t ∑
|
∑ |
(2.8.20)
Metric này được tính từ khoảng cách Hamming 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.
Chương 2: Thuật giải mã Viterbi
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
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).
Chương 2: Thuật giải mã Viterbi
1. (a) khởi tạo t = 0
Thực hiện bộ giải mã Viterbi trên FPGA
Trang 49
(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 √ và
một phía. Bit nhận được là biến ngẫu nhiên Gaussian có trung bình là phương sai là N/2. Hàm log của khả năng xảy ra có thể được định nghĩa là:
∑ (∑
Chương 2: Thuật giải mã Viterbi
)
Thực hiện bộ giải mã Viterbi trên FPGA
Trang 50
√ )
( ∑ (∑ * ) √ +
√ )
)
∑ (∑(
Trong đó
∑ (∑
)
Trong đó C1 và C2 là hằng số, không phải là hàm của y
(2.8.28)
(2.8.29) Từ đây metric bit được định nghĩa là
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) ∑
và
, ∑
.
Metric này được tính từ sự tương quan của Thứ 2, tính metric đường từng phần thứ t
∑
(2.8.31)
Metric này được tính từ
Chương 2: Thuật giải mã Viterbi
(2.8.32)
Thực hiện bộ giải mã Viterbi trên FPGA
Trang 51
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 Từ mã Bit parity đƣợc tạo bởi bộ mã hóa
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
Chương 2: Thuật giải mã Viterbi
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
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 001 Khoảng cách Hamming 1 000
001 1 011
001 1 101
001 3 110
Chương 2: Thuật giải mã Viterbi
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
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ể
Tính toán khoảng cách Euclidean
Khoảng cách Euclidean
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
0 0 0 0.2V 0.4V 0.7V 0.69 (0-0.2)2+ (0-0.4)2+ (0-0.7)2 ( 0V 0V 0V )
0 1 1 0.2V 0.4V 0.7V 0.49 (0-0.2)2+ (1-0.4)2+ (1-0.7)2 ( 0V 1V 1V )
1 0 1 0.2V 0.4V 0.7V 0.89 (1-0.2)2+ (0-0.4)2+ (1-0.7)2 ( 1V 0V 1V )
Chương 2: Thuật giải mã Viterbi
1 1 0 0.2V 0.4V 0.7V 1.49 (1-0.2)2+ (1-0.4)2+ (0-0.7)2 ( 1V 1V 0V )
Thực hiện bộ giải mã Viterbi trên FPGA
Trang 54
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.
Chương 2: Thuật giải mã Viterbi
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
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.
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ỉ
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.
Chương 2: Thuật giải mã Viterbi
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 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
AWGN
Kênh truyền
Ngõ ra bit
Ngõ vào bit
Khối mã hóa mã chập
Khối giải mã Viterbi
Bit mã hóa
Bit nhận được
Hình 3.1: Sơ đồ khối hệ thống
Chương 3: Mô phỏng thuật toán Viterbi dùng Matlab
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.
Thực hiện bộ giải mã Viterbi trên FPGA
Trang 57
Xác định đa thức sinh và chiều dài ràng buộc
Xây dựng sơ đồ trellis
Khối tạo bit ngõ vào
Khối mã hóa
Tạo bit
Mã hóa mã chập
Cộng nhiễu Gauss trắng
Lượng tử bit nhận được
Khối giải mã
Giải mã Viterbi
Tính và vẽ BER
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 ) ;
Chương 3: Mô phỏng thuật toán Viterbi dùng Matlab
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
Thực hiện bộ giải mã Viterbi trên FPGA
Trang 58
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
Chương 3: Mô phỏng thuật toán Viterbi dùng Matlab
decbits = vitdec(quanbits,trellis,numbit-1,‟term‟,‟hard‟);
Thực hiện bộ giải mã Viterbi trên FPGA
Trang 59
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
Chương 3: Mô phỏng thuật toán Viterbi dùng Matlab
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
Hình 3.4: Giao diện chương trình mô phỏng 1
Chương 3: Mô phỏng thuật toán Viterbi dùng Matlab
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
Hình 3.6: Nhập bit ngẫu nhiên – Quyết định mềm
Chương 3: Mô phỏng thuật toán Viterbi dùng Matlab
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
Hình 3.8: Nhập bit ngẫu nhiên – Quyết định cứng
Chương 3: Mô phỏng thuật toán Viterbi dùng Matlab
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
Hình 3.10: So sánh BER của cả quyết định cứng và mềm
Chương 3: Mô phỏng thuật toán Viterbi dùng Matlab
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
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.
Chương 3: Mô phỏng thuật toán Viterbi dùng Matlab
- 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 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).
Chương 4: Xây dựng thuật toán giải mã Viterbi trên Kit DE2
512 Kbyte SRAM.
Thực hiện bộ giải mã Viterbi trên FPGA
Trang 66
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
Chương 4: Xây dựng thuật toán giải mã Viterbi trên Kit DE2
Tổng cộng 483,840 RAM bits
Thực hiện bộ giải mã Viterbi trên FPGA
Trang 67
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.
Chương 4: Xây dựng thuật toán giải mã Viterbi trên Kit DE2
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
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.
Chương 4: Xây dựng thuật toán giải mã Viterbi trên Kit DE2
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
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
Chương 4: Xây dựng thuật toán giải mã Viterbi trên Kit DE2
cũng đều đến từ chỉ 2 trạng thái có thể trước đó.
Thực hiện bộ giải mã Viterbi trên FPGA
Trang 70
- Trong 2 trạng thái đó thì chỉ có một trạng thái đúng là trạng thái trước đó. Chúng ta có thể tìm ra trạng thái đó dựa trên bit mã hóa nhận được và bỏ qua trạng thái còn lại.
- Lỗi xuất hiện trong chuỗi bit mã hóa nhận được là một phân bố ngẫu nhiên và
xác xuất của lỗi là nhỏ.
Dựa theo các giả thuyết như trên, Lưu đồ giải mã được tiến hành như sau: Giả sử là có N bit được mã hóa, lấy 2 bit mã hóa ở cùng một thời điểm để xử lí và tính toán khoảng cách Hamming, metric nhánh, metric đường, và thông số đường tồn tại cho N/2 +K-1 lần, lấy i là biến chạy từ 1 đến N/2 + K -1.
Tính toán khoảng cách Hamming
Để giải mã, ta hãy xem xét 2 bit mã hóa nhận được ở thời điểm yi và tính toán khoảng cách hamming giữa tất cả những sự kết hợp có thể của 2 bit này. Số bit khác nhau có thể được tính toán bằng thuật toán XOR giữa yi với 00, 01, 10, 11 và sau đó tính toán số bit 1.
là số bit 1 thu được sau phép tính
là số bit 1 thu được sau phép tính
là số bit 1 thu được sau phép tính
là số bit 1 thu được sau phép tính
Tính toán metric nhánh và metric đƣờng
Như đã đề cập trước đó, mỗi trạng thái chỉ có thể đến từ 2 trạng thái có thể trước đó (thể hiện bằng 2 đường màu đỏ và xanh tương ứng trong hình 4.4). Thông số metric nhánh chính là tổng của metric đường của trạng thái trước đó và khoảng cách hamming trong sự chuyển đổi giữa 2 trạng thái. Trong 2 metric nhánh có được, thông số metric nhánh nhỏ hơn sẽ được chọn để giữ lại. Đây chính là nhiệm vụ chính của bộ ACS (Add Compare and Select).
Ghi chú:
1. Theo quy ước thì mã hóa chập luôn bắt đầu từ trạng thái 00, và bộ giải mã
Viterbi cũng tương tự.
2. Khi i = 1, metric nhánh cho trạng thái 00 (từ trạng thái 00_dịch bit 0 vào) và trạng thái 10 (từ trạng thái 00_ dịch bit 1 vào) có thể được tính toán. Trong trường hợp này, metric đường cho mỗi trạng thái là chính bằng với metric nhánh khi các nhánh còn lại là không hợp lệ (không tồn tại).
Chương 4: Xây dựng thuật toán giải mã Viterbi trên Kit DE2
3. Khi i = 2, metric nhánh cho trạng thái 00 (từ trạng thái 00), trạng thái 01 (từ trạng thái 10), trạng thái 10 (từ trạng thái 00), và trạng thái 11 (từ trạng thái 10) có thể được tính toán. Trong trường hợp này cũng vậy, metric đường cho mỗi trạng thái chính bằng metric nhánh khi các nhánh khác là không hợp lệ.
Thực hiện bộ giải mã Viterbi trên FPGA
Trang 71
4. Bắt đầu từ thời điểm i = 3, mỗi trạng thái có 2 nhánh và chúng ta cần tiến hành
thuật toán ACS đã nói ở trên.
5. Trong trường hợp 2 metric nhánh có cùng giá trị, chúng ta chọn ngẫu nhiên 1
trạng thái để tiến hành xử lí tiếp
Hình 4.4 Tính toán metric nhánh và metric đường cho bộ giải mã Viterbi
Trạng thái 00 có thể đến từ 2 nhánh
(a) Trạng thái 00 với ngõ ra 00. Metric nhánh cho sự chuyển đổi này,
(4.1)
(b) Trạng thái 01 với ngõ ra 11. Metric nhánh cho sự chuyển đổi này,
(4.2)
Metric đường cho trạng thái 00 được chọn dựa trên giá trị nhỏ hơn trong 2 metric nhánh ở trên.
(4.3) ( )
Đường tồn tại cho trạng thái 00 được lưu trữ trong biến “metric đường tồn tại”
Trạng thái 01 có thể đến từ 2 nhánh
(c) Trạng thái 10 với ngõ ra 10. Metric nhánh cho sự chuyển đổi này,
(4.4)
(d) Trạng thái 11 với ngõ ra 01. Metric nhánh cho sự chuyển đổi này,
Chương 4: Xây dựng thuật toán giải mã Viterbi trên Kit DE2
(4.5)
Thực hiện bộ giải mã Viterbi trên FPGA
Trang 72
Metric đường cho trạng thái 01 được chọn dựa trên giá trị nhỏ hơn trong 2 metric nhánh ở trên.
(4.6) ( )
Đường tồn tại cho trạng thái 01 được lưu trữ trong biến “metric đường tồn tại”
Trạng thái 10 có thể đến từ 2 nhánh
(e) Trạng thái 00 với ngõ ra 11. Metric nhánh cho sự chuyển đổi này,
(4.7)
(f) Trạng thái 01 với ngõ ra 00. Metric nhánh cho sự chuyển đổi này,
(4.8)
Metric đường cho trạng thái 10 được chọn dựa trên giá trị nhỏ hơn trong 2 metric nhánh ở trên.
(4.9) ( ).
Đường tồn tại cho trạng thái 10 được lưu trữ trong biến “metric đường tồn tại”
Trạng thái 11 có thể đến từ 2 nhánh
(g) Trạng thái 10 với ngõ ra 01. Metric nhánh cho sự chuyển đổi này,
(4.10)
(h) Trạng thái 11 với ngõ ra 10. Metric nhánh cho sự chuyển đổi này,
(4.11)
Metric đường cho trạng thái 11 được chọn dựa trên giá trị nhỏ hơn trong 2 metric nhánh ở trên.
(4.12) ( ).
Đường tồn tại cho trạng thái 11 được lưu trữ trong biến “metric đường tồn tại”
Khối truy hồi
Khi đường tồn tại được tính toán N/2 + K – 1 lần, thuật toán giải mã có thể bắt đầu ước lượng chuỗi ngõ vào. Nhờ vào sự có mặt của các bit tận cùng (K-1 bit 0 thêm vào), thì trạng thái cuối cùng của chuỗi bit theo bộ mã hóa chập là trạng thái 00.
Vì vậy, bắt đầu từ metric đường cuối cùng được tính toán ở thời điểm N/2 + K -1 cho trạng thái 00, từ đường tồn tại, ta tìm ra trạng thái trước đó tương ứng với trạng thái hiện tại. Từ kiến thức về trạng thái hiện tại và trạng thái trước, chuỗi ngõ vào có thể được quyết định (xem bảng 4.3 về trạng thái ngõ vào và trạng thái ngõ ra). Tiếp tục truy hồi dựa theo đường tồn tại và ước lượng chuỗi ngõ vào cho đến thời điểm i = 1. Chương 4: Xây dựng thuật toán giải mã Viterbi trên Kit DE2
Thực hiện bộ giải mã Viterbi trên FPGA
Trang 73
Bảng 4.3: Trạng thái hiện tại và trạng thái trước của nó
Input,
if previous state
Current state 00 01 10 11
0 0 x x 00
x x 0 0 01
1 1 x x 10
x x 1 1 11
4.2.2 Giải mã viterbi quyết định mềm
Ở trên chúng ta đã bàn về thuật toán lập trình giải mã Viterbi quyết định cứng, giờ chúng ta tiến hành phân tích thuật toán giải mã viterbi quyết định mềm. Điều chế được sử dụng là BPSK và kênh truyền được giả sử là kênh AWGN.
Mô hình hệ thống
Chuỗi mã nhận được là
, trong đó c là chuỗi mã hóa đã được điều chế sẽ có giá trị √ nếu bit được mã hóa là bit 1 và √ nếu bit được mã hóa là bit 0, n là nhiễu Gauss trắng cộng tính với hàm phân phối xác xuất là,
với giá trị trung bình và phương sai
√
.
( √ )
Hàm phân bố xác xuất (PDF) có điều kiện của y nếu bit được mã hóa là bit 0 là,
√
(4.13)
( √ )
Hàm phân bố xác xuất (PDF) có điều kiện của y nếu bit được mã hóa là bit 1 là,
√
(4.14)
Khoảng cách Euclidean
Chương 4: Xây dựng thuật toán giải mã Viterbi trên Kit DE2
Trong giải mã Viterbi quyết định mềm, dựa trên vị trí của ký hiệu đã được mã hóa nhận được, bit đã mã hóa được ước lượng; nếu ký hiệu nhận được là lớn hơn 0, bit
Thực hiện bộ giải mã Viterbi trên FPGA
Trang 74
đã mã hóa nhận được sẽ là 1; nếu ký hiệu nhận được là bé hơn hoặc bằng 0, bit đã mã hóa nhận được sẽ là bit 0.
Trong giải mã quyết định mềm, thay vì ước lượng bit đã được mã hóa và tìm khoảng cách Hamming, ta sẽ tìm khoảng cách giữa ký hiệu nhận được và ký hiệu có thể đã được phát đi.
Khoảng cách Euclidean nếu bit đã mã hóa được truyền đi là bit 0 là,
( √ )
(4.15) ( √ )
Khoảng cách Euclidean nếu bit đã mã hóa được truyền đi là bit 1 là,
(4.16) ( √ ) ( √ )
Các thành phần , y2, √ và là chung cho cả 2 biểu thức nên chúng có thể được bỏ đi. Khoảng cách Euclidean sau khi đơn giản biểu thức là,
(4.17) và
Khi thuật toán Viterbi nhận được 2 bit mã hóa ở cùng một thời điểm để xử lí, chúng ta cần phải tìm ra khoảng cách Euclidean từ cả 2 bit.
( √ )
(4.18) ( √ ) ( )
( √ )
( √ )
( √ ) ( )
( √ )
( √ ) ( )
Chương 4: Xây dựng thuật toán giải mã Viterbi trên Kit DE2
( √ ) ( )
Thực hiện bộ giải mã Viterbi trên FPGA
Trang 75
Lưu đồ giải thuật chính của chương trình
Hình 4.5: Lưu đồ giải thuật chính của chương trình
Chương 4: Xây dựng thuật toán giải mã Viterbi trên Kit DE2
4.3 Lưu dồ thuật toán lập trình
Thực hiện bộ giải mã Viterbi trên FPGA
Trang 76
Khối cài đặt ban đầu thiết lập những thông số cho bộ mã giống như bên phần mã chập, đồng thời nhận các bit ngõ vào từ kênh truyền. Bảng trạng thái tiếp theo cũng được tính toán trước và lưu vào bộ nhớ ở khối này.
Sau đó, với mỗi xung bộ giải mã sẽ tính toán 4 khoảng cách nhánh Hamming hoặc Euclidean (gọi chung là khoảng cách), phụ thuộc vào chế độ quyết định cứng hay mềm đã lựa chọn ban đầu. Với mỗi trạng thái, khối Cộng-So sánh-Lựa chọn (ACS) tính toán hai khoảng cách đường, so sánh và lựa chọn ra đường có khoảng cách bé nhất. Tại thời điểm này, bộ giải mã cũng lưu lại các thông số tích lũy cho trạng thái.
Giống như mã chập, sơ đồ trellis được xây dựng, trên sơ đồ này, các điểm truyền được đánh dấu với các thông số tương tứng như thông số đường và trạng thái trước đó. Khi tất cả các bit vào đã được nhận, sơ đồ trellis đã xây dựng xong, tính toán tất cả các thông số tích lũy, dựa vào bẳng tích lũy bộ giữa mã tìm đường tồn tại, kết hợp giữa đường tồn tại và bảng trạng thái tiếp theo bộ giải mã sẽ tìm ra chuỗi bit ban đầu.
Hình 4.6: Lưu đồ giải thuật bộ giải mã
Chương 4: Xây dựng thuật toán giải mã Viterbi trên Kit DE2
Sau đây là lưu đồ chi tiết hơn cho bộ giải mã Viterbi
Thực hiện bộ giải mã Viterbi trên FPGA
Trang 77
Chương 4: Xây dựng thuật toán giải mã Viterbi trên Kit DE2
Hình 4.7: Lưu đồ chi tiết giải thuật giải mã Viterbi trên Kit DE2
Thực hiện bộ giải mã Viterbi trên FPGA
Trang 78
Trước khi thực hiện giải mã, bộ giải mã phải được cài đặt chế độ quyết định cho giải mã từ bên ngoài. Với mỗi chế độ, sẽ có cách tính khoảng cách nhánh khác nhau, Hamming (tương ứng với quyết định cứng) hay Euclidean (tương ứng với quyết định mềm).
Khối tính khoảng cách Hamming
Hình 4.8: Lưu đồ tính khoảng cách Hamming
Như đã trình bày trong phần trước, các bit nhận được ở bộ thu sẽ được lượng tử với 1 bit, khoảng cách Hamming được tính dựa trên sự khác nhau giữa bit thu được và bit chuẩn tương ứng 00, 01, 10, 11. Sau khi qua khối tính khoảng cách Hamming, kết quả được đưa đến khối ACS để tìm ra đường tồn tại.
Chương 4: Xây dựng thuật toán giải mã Viterbi trên Kit DE2
Theo sơ đồ trên, mặc dù khối cộng có 4 ngõ vào, tuy nhiên tại 1 thời điểm, chỉ có 2 ngõ vào tương ứng với giá trị khi so sánh sự giống nhau của bit thu được và bit chuẩn.
Thực hiện bộ giải mã Viterbi trên FPGA
Trang 79
Khối tính khoảng cách Euclidean
Hình 4.9: Lưu đồ giải thuật tính khoảng cách Euclidean
Khi chế độ lựa chọn là quyết định mềm thì bộ giải mã sẽ tính toán khoảng cách Euclidean thay cho khoảng cách Hamming. Lý thuyết về việc tính toán khoảng cách Euclidean đã được trình bày ở phần trước.
Kết quả tính toán khoảng cách Hamming hay Euclidean đều được lưu vào 1 biến duy nhất tương ứng với bit chuẩn (00, 01, 10, 11). Các giá trị này được so sánh với nhau để tìm ra khoảng cách có giá trị nhỏ nhất. Các thông số liên quan đến giá trị nhỏ nhất này được lưu trữ bào bộ nhớ để phục vụ cho quá trình truy hồi sau này.
Khối trạng thái tiếp theo
Khi vừa cấp nguồn, bộ giải mã sẽ thực hiện tính toán và lưu trữ một bảng bao gồm các giá trị của ngõ ra và giá trị tiếp theo tương ứng với tất cả các giá trị ngõ vào. Bảng này gọi là bảng trạng thái tiếp theo. Bảng trạng thái tiếp theo được sử dụng kết hợp với giá trị của đường tối ưu để tìm ra chuỗi bit ban đầu.
Chương 4: Xây dựng thuật toán giải mã Viterbi trên Kit DE2
Việc tạo ra các giá trị tiếp theo giống như tạo mã chập cho các giá trị ngõ vào được cho trước. Các giá trị này nằm ở các vị trí đã được xác định, để bộ giải mã có thể truy cập đến một cách chính xác để tìm ra bit ngõ vào chính xác.
Thực hiện bộ giải mã Viterbi trên FPGA
Trang 80
Bảng trạng thái tiếp theo của bộ mã được sử dụng trong bài báo cáo này được
xác định như sau:
Bảng 4.4: Bảng trạng thái tiếp theo
INPUT 0 INPUT 1
Previous State
Next State Output Bit Next State Output Bit
00 00 10 11 00
00 11 10 00 01
01 01 11 10 10
01 10 11 01 11
Khối tính khoảng cách nhánh
Hình 4.10: Lưu đồ khối tính khoảng cách nhánh
Chương 4: Xây dựng thuật toán giải mã Viterbi trên Kit DE2
Tương ứng với mỗi cặp bit vào, bộ giải mã tính ra 4 khoảng cách nhánh tương ứng với các cặp bit chuẩn 00, 01, 10, 11.
Thực hiện bộ giải mã Viterbi trên FPGA
Trang 81
Khối cộng so sánh lựa chọn
Hình 4.11: Lưu đồ khối ACS
Khoảng cách nhánh tại trrạng thái hiện tại được cộng dồn với giá trị đã tích lũy trước đó trên cùng đường đi của sơ đồ trellis. Sau khi cộng, bộ giải mã sẽ so sánh 2 kết quả cộng trên, giả sử tại thời điểm này, hai kết quả này bằng nhau, bộ so sánh sẽ tiếp tục dịch lên một trạng thái và tiến hành so sánh lần thứ hai, lúc này bộ giải mã sẽ tìm ra giá trị nhỏ nhất, từ đó bộ so sánh truy ngược lại và xác định giá trị lựa chọn ở trạng thái trước. Giá trị sau khi được lựa chọn sẽ được lưu vào bảng tích lũy, bảng này sẽ phục vụ cho việc tìm đường tồn tại sau này.
Khối truy hồi
Chương 4: Xây dựng thuật toán giải mã Viterbi trên Kit DE2
Hình 4.12: Lưu đồ khối truy hồi
Thực hiện bộ giải mã Viterbi trên FPGA
Trang 82
Từ trạng thái đầu tiên, khối truy hồi sẽ so sánh các giá trị trong bảng tích lũy để
tìm ra đường tồn tại tối ưu nhất.
Khối giải mã
Hình 4.13: Lưu đồ khối giải mã
Sau khi qua khối truy hồi, bộ giải mã đã tìm được đường tồn tại. Bộ giải mã sẽ tiến hành so sánh giá trị tiếp theo của đường tồn tại tại thời điểm hiện tại với giá trị của đường tồn tại tại thời điểm sau một trạng thái. Với mỗi lần so sánh, bộ giải mã sẽ thử với một trong hai bit vào là 0 hay 1, so sánh sự giống nhau tương ứng với giá trị vào là 0 hay 1, bộ giải mã sẽ xác định được bit được mã hóa ban đầu ở khối phát là 0 hay 1.
Sau khi hoàn thành so sánh tất cả các trạng thái, bộ giải mã đã xác định được
chuỗi bit ban đầu.
4.4 Kết quả
Quá trình thực hiện được chia làm hai quá trình, thứ nhất là lập trình giải thuật mã hóa mã chập và thuật giải Viterbi chạy mô phỏng sử dụng phần mềm mô phỏng có sẵn trong Quartus II; thứ hai là tiến hành biên dịch tổng hợp và đổ chương trình lên Kit DE2 có kèm theo chương trình hiển thị trên LCD cà các Led đơn, trong chương trình đổ lên Kit DE2 thì người lập trình đã loại bỏ khối mã hóa mã chập.
Giả sử cho chuỗi bit ban đầu trước khi mã hóa mã chập là: 11100101.
Chương 4: Xây dựng thuật toán giải mã Viterbi trên Kit DE2
Sau khi mã hóa mã chập cho ra chuỗi bit sau: 1110011011110100
Thực hiện bộ giải mã Viterbi trên FPGA
Trang 83
Cho ngược chuỗi 16 bit trên vào ngõ vào của bộ giải mã Viterbi. Kết quả ngõ ra
là: 11100101
Vì không có nhiễu tác động nên kết quả của hai quyết định cứng và mềm là như
nhau.
Kết quả mô phỏng trên phần mềm Quartus II như sau:
Hình 4.14: Kết quả mô phỏng 1
Giả sử ngõ vào bộ giải mã Viterbi bị sai 2 bit: 1010011010110100
Kết quả ra vẫn chính xác: 11100101
Chương 4: Xây dựng thuật toán giải mã Viterbi trên Kit DE2
Hình 4.15: Kết quả mô phỏng 2
Thực hiện bộ giải mã Viterbi trên FPGA
Trang 84
Giả sử ngõ vào bộ giải mã Viterbi bị sai 3 bit : 1010011010110101
Kết quả 1 bit cuối bị giải mã sai: 11100100
Hình 4.16: Kết quả mô phỏng 3
Giả sử ngõ vào bộ giải mã Viterbi bị sai 4 bit : 1010001010110101
Kết quả 1 bit cuối bị giải mã sai: 11100100
Hình 4.17: Kết quả mô phỏng 4
Kết quả trên chứng minh bộ giải mã Viterbi có khả năng sửa sai bit đơn rất tốt.
Giả sử ngõ vào bộ giải mã Viterbi bị sai 1 cặp bit : 1101011011110100
Chương 4: Xây dựng thuật toán giải mã Viterbi trên Kit DE2
Kết quả 2 bit bị giải mã sai: 10110101
Thực hiện bộ giải mã Viterbi trên FPGA
Trang 85
Hình 4.18: Kết quả mô phỏng 5
Giả sử ngõ vào bộ giải mã Viterbi bị sai 1 bit đơn và 1cặp bit :
1101011011111100
Kết quả 5 bit bị giải mã sai: 10110010
Hình 4.19: Kết quả mô phỏng 6
Kết quả trên cho thấy, thuật giải mã Viterbi không có khả năng sửa lỗi sai trong
trường hợp lỗi đa bit.
So sánh với kết quả đã mô phỏng trên Matlab
Chương 4: Xây dựng thuật toán giải mã Viterbi trên Kit DE2
Vẫn chuỗi bit vào như trên: 11100101. Với mô phỏng trên Matlab, hệ thống có tác động của nhiễu trắng Gaussian. Kết quả giải mã bị sai 1 bit với quyết định mềm.
Thực hiện bộ giải mã Viterbi trên FPGA
Trang 86
Hình 4.20: Mô phỏng trên Matlab
Vì mô phỏng trên Kit DE2 là môi trường lý tưởng, dữ liệu bit nhận được nhập vào bởi người sử dụng, không bị tác động của kênh truyền, do đó kết quả giải mã cho chính xác hơn so với giải mã trên Matlab.
Hình ảnh thực tế trên Kit DE2 như sau:
Khởi động chương trình mô phỏng, LCD hiển thị DH SPKT TPHCM và dòng chữ DO AN TOT NGHIEP
Chương 4: Xây dựng thuật toán giải mã Viterbi trên Kit DE2
Hình 4.21: Hình thực tế bộ kit 1
Thực hiện bộ giải mã Viterbi trên FPGA
Trang 87
Tiếp theo, LCD hiển thị nhóm thực hiện đề tài
Key 0 để reset mạch
Hình 4.22: Hình thực tế bộ kit 2
2. 16 SW để gán dữ liệu cần giải mã.
3. Mức 1 để bắt đầu giải mã.
4. LCD hiển thị chuỗi dữ liệu cần giải mã và chuỗi dữ liệu sau giải mã.
1. Mức 0 để chọn giải mã quyết định mềm
5. 8 LED biễu diễn chuỗi dữ liệu sau giải mã.
Chương 4: Xây dựng thuật toán giải mã Viterbi trên Kit DE2
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 88
CHƢƠNG 5: KẾT LUẬN
5.1 Tổng kết nhận xét
Tổng kết lại, trong cuốn đồ án này nhóm đã thực hiện được những nội dung
sau:
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.
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.
Khái niệm và phân tích thuật toán giải mã Viterbi, cách mà thuật toán Viterbi giải mã một tín hiệu và sửa sai các lỗi xảy ra trên kênh truyền, phân biệt hai phương pháp giải mã là giải mã quyết định cứng và quyết định mềm.
Thực hiện mô phỏng Matlab để xem hiệu quả của thuật toán Viterbi. Thực hiện mô tả trên Kit DE2 bằng ngôn ngữ VHDL để kiểm chứng kết quả
mô phỏng.
Qua kết quả mô phỏng bằng Matlab và kết quả mô tả trên kit DE2, nhóm đã rút
ra được những nhận xét sau:
Mã hóa kênh truyền giúp giảm thiểu tác động của nhiễu và cải thiện tin tức
tốt.
Thuật toán giải mã viterbi đạt hiệu quả cao, xác suất lỗi thấp Trên kênh truyền có lỗi Gauss trắng, tín hiệu có thể được phục hồi tốt. Thuật toán viterbi với quyết định mềm cho kết quả tốt hơn quyết định cứng. Vì với quyết định mềm tín hiệu sau khi được nhận ở bộ thu được lượng tử với nhiều mức, do đó dẫn đến xác suất sai sẽ thấp hơn so với quyết định cứng.
Đối với các lỗi nhiều bit liên tiếp, thuật toán Viterbi không mang lại hiệu
quả.
Trong kênh truyền có tỉ số SNR cao, thuật toán viterbi với cả 2 quyết định
cứng và mềm đều cho kết quả tốt gần như nhau.
5.2 Tồn tại và hướng phát triển của đề tài
Những mặt còn tồn tại:
Chương 5: Kết luận
- Việc mô phỏng trên matlab cũng như mô tả trên kit DE2 đều chỉ mới tiến hành với bộ mã đơn giản tốc độ ½ với chiều dài ràng buộc thấp. Vì thế, kết quả mô phỏng có thể sẽ không bao quát và nói hết được ưu nhược điểm của thuật toán.
Thực hiện bộ giải mã Viterbi trên FPGA
Trang 89
- Việc mô tả trên kit DE2 chỉ là khâu giải mã với chuỗi bit nhận được nhập bởi người sử dụng. Do đó, ta không thể đánh giá được hết tác động của nhiễu chỉ với vài lần thử nghiệm với các bit nhận được là sai.
- Việc giải mã Viterbi quyết dịnh mềm chỉ mới thực hiện với phương pháp
dùng khoảng cách Euclidean.
Hướng phát triển đề tài:
- Với giới hạn thời gian cũng như khả năng có hạn nên nhóm tác giả vẫn còn chưa tìm hiểu hoàn chỉnh về mã chập cũng như thuật giải Viterbi. Vì vậy, có thể phương pháp thực hiện cũng như lập trình sẽ không là giải pháp tối ưu. Nếu có cơ hội để nghiên cứu tiếp thì đề tài có thể nâng lên để thực hiện tối ưu hóa cho bộ thu Viterbi, thử nghiệm với các bộ mã khác nhau để từ đó tìm ra bộ mã tối ưu nhất cho kênh truyền AWGN.
- Cải thiện việc mô tả trên kit DE2 bằng cách thêm phần tạo bit nhận ngẫu nhiên chứ không nhập trực tiếp bằng tay, từ đó tổng hợp đánh giá tác động của nhiễu lên tín hiệu một cách tổng quát hơn.
- Từ kết quả của đề tài, chúng ta có thể thiết kế các IC thực hiện các chức
năng khác nhau trong hệ thống thông tin số.
Chương 5: Kết luận
- Nghiên cứu tiến hành xây dựng bộ mã hóa nguồn.
PHẦN C
PHỤ LỤC VÀ TÀI LIỆU THAM KHẢO
Thực hiện bộ giải mã Viterbi trên FPGA
Trang 91
I. Phụ lục
1. Hướng dẫn sử dụng kit DE2 để mô phỏng
Chức năng các một số thiết bị trên Kit DE2 như sau:
- Switch 0: Chức năng start, để bắt đầu quá trình giải mã. Mức 1 tương ứng
với lệnh thực hiện bắt đầu.
- Switch 1: Chức năng lựa chọn chế độ quyết định cứng hay mềm.
1. Mức 0: Quyết định cứng 2. Mức 1: Quyết định mềm
- Switch 2 đến 17: Tương ứng với 16 bit ngõ vào. - Nút nhấn Key 0: Chức năng reset mạch. - LCD: Chức năng hiển thị thông tin về đồ án và dữ liệu vào ra của bộ giải
mã.
- Led 0 đến 7: Chức năng hiển thị giá trị của 8 bit ngõ ra.
1. Led sáng: Mức 1 2. Led tắt: Mức 0
Quá trình mô phỏng trên Kit DE2 nhƣ sau:
Sau khi đã nạp chương trình từ máy tính xuống Kit DE2, màn hình LCD sẽ hiển thị một số thông tin về đồ án. Khi gạt các Switch từ 2 đến 17 để cấp dữ liệu ngõ vào cho bộ giải mã, LCD sẽ hiển thị giá trị 16 bit này. Khi gạt Switch 0, quá trình giải mã bắt đầu, LCD hiển thị thêm 8 bit ra ở dòng thứ 2, đồng thời các Led sẽ sáng.
Nếu nhấn nút Key 0 (Reset), LCD sẽ hiển thị lại các thông tin ban đầu, nếu lúc này, Switch Start đang bật thì các Led vẫn sáng, nếu Switch Start gạt xuống mức 0 thì các Led tắt hết.
2. Tài nguyên sử dụng trên Kit DE2
Phần C: Phụ lục và tài liệu tham khảo
Bảng: Thông báo về tài nguyên sử dụng trên kit DE2
Thực hiện bộ giải mã Viterbi trên FPGA
Trang 92
Bảng: Danh sách các chân sử dụng trên Kit DE2
Signal Name PIN Discription
Clock_50 PIN_N2 50 mHz clock input
SW[0] PIN_N25 Toggle Switch[0]
SW[1] PIN_N26 Toggle Switch[1]
SW[2] PIN_P25 Toggle Switch[2]
SW[3] PIN_AE14 Toggle Switch[3]
SW[4] PIN_AF14 Toggle Switch[4]
SW[5] PIN_AD13 Toggle Switch[5]
SW[6] PIN_AC13 Toggle Switch[6]
SW[7] PIN_C13 Toggle Switch[7]
SW[8] PIN_B13 Toggle Switch[8]
SW[9] PIN_A13 Toggle Switch[9]
SW[10] PIN_N1 Toggle Switch[10]
SW[11] PIN_P1 Toggle Switch[11]
SW[12] PIN_P2 Toggle Switch[12]
SW[13] PIN_T7 Toggle Switch[13]
SW[14] PIN_U3 Toggle Switch[14]
SW[15] PIN_U4 Toggle Switch[15]
SW[16] PIN_V1 Toggle Switch[16]
SW[17] PIN_V2 Toggle Switch[17]
LEDR[0] PIN_AE23 LED Red[]
Phần C: Phụ lục và tài liệu tham khảo
LEDR[1] PIN_AF23 LED Red[]
Thực hiện bộ giải mã Viterbi trên FPGA
Trang 93
LEDR[2] PIN_AB21 LED Red[]
LEDR[3] PIN_AC22 LED Red[]
LEDR[4] PIN_AD22 LED Red[]
LEDR[5] PIN_AD23 LED Red[]
LEDR[6] PIN_AD21 LED Red[]
LEDR[7] PIN_AC21 LED Red[]
KEY[0] PIN_G26 Pushbutton[0]
LCD_DATA[0] PIN_J1 LCD DATA []
LCD_DATA[1] PIN_J2 LCD DATA []
LCD_DATA[2] PIN_H1 LCD DATA []
LCD_DATA[3] PIN_H2 LCD DATA []
LCD_DATA[4] PIN_J4 LCD DATA []
LCD_DATA[5] PIN_J3 LCD DATA []
LCD_DATA[6] PIN_H4 LCD DATA []
LCD_DATA[7] PIN_H3 LCD DATA []
LCD_RW PIN_K4
LCD Read/Write Select, 0 = Write, 1 = Read
LCD_EN PIN_K3 LCD Enable
LCD Command/Data Select, 0 = Command, 1 = Data
LCD_RS PIN_K1
LCD_ON PIN_L4 LCD Power ON/OFF
LCD_BLON PIN_L2 LCD Back Light ON/OFF
3. Mã nguồn Matlab
Phần C: Phụ lục và tài liệu tham khảo
function varargout = viterbi2(varargin)
Thực hiện bộ giải mã Viterbi trên FPGA
Trang 94
Phần C: Phụ lục và tài liệu tham khảo
gui_Singleton = 1; gui_State = struct('gui_Name', mfilename, ... 'gui_Singleton', gui_Singleton, ... 'gui_OpeningFcn', @viterbi2_OpeningFcn, ... 'gui_OutputFcn', @viterbi2_OutputFcn, ... 'gui_LayoutFcn', [] , ... 'gui_Callback', []); if nargin && ischar(varargin{1}) gui_State.gui_Callback = str2func(varargin{1}); end if nargout [varargout{1:nargout}] = gui_mainfcn(gui_State, varargin{:}); else gui_mainfcn(gui_State, varargin{:}); end function viterbi2_OpeningFcn(hObject, eventdata, handles, varargin) handles.output = hObject; guidata(hObject, handles); h1 = getappdata(0,'GUI1_handle'); close(h1) h2 = gcf; setappdata(0,'GUI2_handle',h2); axes(handles.logo); imshow('KHOADIENTU.png'); viterbi3; set(handles.bitin,'Enable','inactive'); global inbit numin ; inbit =0; function varargout = viterbi2_OutputFcn(hObject, eventdata, handles) varargout{1} = handles.output; function button_back_Callback(hObject, eventdata, handles) viterbi1; function button_exit_Callback(hObject, eventdata, handles) exit = questdlg('Ready to quit?',...
Thực hiện bộ giải mã Viterbi trên FPGA
Trang 95
Phần C: Phụ lục và tài liệu tham khảo
'Exit Dialog','Yes','No','No'); switch exit case 'Yes', disp('Exiting MATLAB'); save quit case 'No' quit cancel; end function numin_Callback(hObject, eventdata, handles) user_entry = str2double(get(hObject,'String')); if isnan(user_entry) errordlg('Type the integer, maximum value is 10^6! ','Input Error !','modal') set(hObject,'String',''); return end function numin_CreateFcn(hObject, eventdata, handles) if ispc && isequal(get(hObject,'BackgroundColor'), get(0,'defaultUicontrolBackgroundColor')) set(hObject,'BackgroundColor','white'); end function numin_ButtonDownFcn(hObject, eventdata, handles) function g2_Callback(hObject, eventdata, handles) user_entry = str2double(get(hObject,'string')); if isnan(user_entry) errordlg('Type the integer ! ','Input Error !','modal') set(hObject,'String',''); return end function g2_CreateFcn(hObject, eventdata, handles) if ispc && isequal(get(hObject,'BackgroundColor'), get(0,'defaultUicontrolBackgroundColor')) set(hObject,'BackgroundColor','white'); end function g1_Callback(hObject, eventdata, handles)
Thực hiện bộ giải mã Viterbi trên FPGA
Trang 96
Phần C: Phụ lục và tài liệu tham khảo
user_entry = str2double(get(hObject,'string')); if isnan(user_entry) errordlg('Type the integer ! ','Input Error !','modal') set(hObject,'String',''); return end function g1_CreateFcn(hObject, eventdata, handles) if ispc && isequal(get(hObject,'BackgroundColor'), get(0,'defaultUicontrolBackgroundColor')) set(hObject,'BackgroundColor','white'); end function length_Callback(hObject, eventdata, handles) user_entry = str2double(get(hObject,'string')); if isnan(user_entry) errordlg('Type the integer ! ','Input Error !','modal') set(hObject,'String',''); return end function length_CreateFcn(hObject, eventdata, handles) if ispc && isequal(get(hObject,'BackgroundColor'), get(0,'defaultUicontrolBackgroundColor')) set(hObject,'BackgroundColor','white'); end function numout_Callback(hObject, eventdata, handles) user_entry = str2double(get(hObject,'string')); if isnan(user_entry) errordlg('Type the integer ! ','Input Error !','modal') set(hObject,'String',''); return end if (user_entry > 2)||(user_entry < 1) errordlg('The Viterbi decoder is just for maximum 2 outputs !','Input Error !','modal') set(hObject,'String',''); return end
Thực hiện bộ giải mã Viterbi trên FPGA
Trang 97
Phần C: Phụ lục và tài liệu tham khảo
if user_entry == 1 set(handles.g2,'Enable','inactive'); set(handles.textber,'ForegroundColor','black') elseif user_entry == 2 set(handles.g2,'Enable','on'); set(handles.textber,'ForegroundColor','blue') end function numout_CreateFcn(hObject, eventdata, handles) if ispc && isequal(get(hObject,'BackgroundColor'), get(0,'defaultUicontrolBackgroundColor')) set(hObject,'BackgroundColor','white'); end function auto_Callback(hObject, eventdata, handles) if (get(hObject,'Value') == get(hObject,'Max')) a = 1; set(handles.numin,'Enable','inactive'); set(handles.numin,'String',''); set(handles.bitin,'Enable','on'); set(handles.bitin,'String',''); set(handles.text7,'ForegroundColor','black'); else a = 0; set(handles.numin,'Enable','on'); set(handles.bitin,'Enable','inactive'); set(handles.text7,'ForegroundColor','blue'); end function bitin_Callback(hObject, eventdata, handles) function bitin_CreateFcn(hObject, eventdata, handles) if ispc && isequal(get(hObject,'BackgroundColor'), get(0,'defaultUicontrolBackgroundColor')) set(hObject,'BackgroundColor','white'); end function bitencoded_Callback(hObject, eventdata, handles) function bitencoded_CreateFcn(hObject, eventdata, handles)
Thực hiện bộ giải mã Viterbi trên FPGA
Trang 98
Phần C: Phụ lục và tài liệu tham khảo
if ispc && isequal(get(hObject,'BackgroundColor'), get(0,'defaultUicontrolBackgroundColor')) set(hObject,'BackgroundColor','white'); end function bitout_Callback(hObject, eventdata, handles) function bitout_CreateFcn(hObject, eventdata, handles) if ispc && isequal(get(hObject,'BackgroundColor'), get(0,'defaultUicontrolBackgroundColor')) set(hObject,'BackgroundColor','white'); end function ber_Callback(hObject, eventdata, handles) clc; if (get(handles.auto,'Value') == get(handles.auto,'Max')) a = 1; else a = 0; end if a == 1 inbit = get(handles.bitin,'String'); inbit = str2num(inbit); numin = length(inbit); else numin = get(handles.numin,'String'); numin = str2num(numin); inbit = randint(1,numin); end numout = get(handles.numout,'String'); numout = str2num(numout); len = get(handles.length,'String'); len = str2num(len); g1 = get(handles.g1,'String'); g1 = str2num(g1); g2 = get(handles.g2,'String' g2 = str2num(g2); Eb_N0_dB = [1:1:10];
Thực hiện bộ giải mã Viterbi trên FPGA
Trang 99
Phần C: Phụ lục và tài liệu tham khảo
for i = 1:length(Eb_N0_dB) snr_db = Eb_N0_dB(i) if numout == 1 trellis = poly2trellis(len,g1); elseif numout == 2 trellis = poly2trellis(len,[g1 g2]); end encbits = convenc(inbit,trellis); encbits = 2*encbits - 1; awgnbits = awgn(encbits,snr_db,'measured'); str = get(handles.typeofdec,'String'); val = get(handles.typeofdec,'Value'); switch str{val} case 'Soft Decision' select = 0; case 'Hard Decision' select = 1; case 'Both' select = 2; end if select == 0 partition = [-.8571 -.5714 -.2857 0 .2857 .5714 .8571]; codebook = [-.99 -.8571 -.5714 -.2857 0 .2857 .5714 .8571]; quanbits = quantiz(awgnbits,partition,codebook); tblen = numin -1 ; opmode = 'term'; dectype = 'soft'; nsdec = 3; decbits = vitdec(quanbits,trellis,tblen,'term','soft',nsdec); end if select == 1 partition = [0]; codebook = [0 1]; quanbits = quantiz(awgnbits,partition,codebook); tblen = numin-1; opmode = 'term' ; dectype = 'hard';
Thực hiện bộ giải mã Viterbi trên FPGA
Trang 100
decbits = vitdec(quanbits,trellis,tblen,'term','hard'); end if select == 0 || select == 1 [numerr ratioerr] = biterr(inbit, decbits); ratioerr_comp(i) = ratioerr end if select == 2 partition_h = [0]; codebook_h = [0 1]; quanbits_h = quantiz(awgnbits,partition_h,codebook_h); tblen_h = numin-1; opmode_h = 'term' ; dectype_h = 'hard'; decbits_h = vitdec(quanbits_h,trellis,tblen_h,'term','hard'); partition_s = [-.8571 -.5714 -.2857 0 .2857 .5714 .8571];
codebook_s = [-.99 -.8571 -.5714 -.2857 0 .2857 .5714 .8571]; quanbits_s = quantiz(awgnbits,partition_s,codebook_s);
Phần C: Phụ lục và tài liệu tham khảo
tblen_s = numin -1 ; opmode_s = 'term'; dectype_s = 'soft'; nsdec = 3; decbits_s = vitdec(quanbits_s,trellis,tblen_s,'term','soft',nsdec); [numerr_s ratioerr_s] = biterr(inbit, decbits_s); ratioerr_comp_s(i) = ratioerr_s [numerr_h ratioerr_h] = biterr(inbit, decbits_h); ratioerr_comp_h(i) = ratioerr_h end end if select == 0 figure semilogy(Eb_N0_dB,ratioerr_comp,'mp-','LineWidth',2); axis([0 10 10^-8 0.5]) grid on legend('Viterbi-Soft decision(rate-1/2, [5,7]_8)'); xlabel('Eb/No, dB'); ylabel('Bit Error Rate'); title('BER for Viterbi-Soft decision decoding in AWGN'); end
Thực hiện bộ giải mã Viterbi trên FPGA
Trang 101
Phần C: Phụ lục và tài liệu tham khảo
if select == 1 figure semilogy(Eb_N0_dB,ratioerr_comp,'bd-','LineWidth',2); axis([0 10 10^-8 0.5]) grid on legend('Viterbi-Hard decision(rate-1/2, [5,7]_8)'); xlabel('Eb/No, dB'); ylabel('Bit Error Rate'); title('BER for Viterbi-Hard decision decoding in AWGN'); end if select == 2 figure semilogy(Eb_N0_dB,ratioerr_comp_s,'mp-','LineWidth',2); hold on; semilogy(Eb_N0_dB,ratioerr_comp_h,'bd-','LineWidth',2); axis([0 10 10^-8 0.5]) grid on legend('Viterbi-Soft decision(rate-1/2, [5,7]_8)','Viterbi-Hard decision(rate-1/2, [5,7]_8)'); xlabel('Eb/No, dB'); ylabel('Bit Error Rate'); title('BER for both types of decision of Viterbi decoding in AWGN'); end function reset_CreateFcn(hObject, eventdata, handles) if ispc && isequal(get(hObject,'BackgroundColor'), get(0,'defaultUicontrolBackgroundColor')) set(hObject,'BackgroundColor','white'); end function start_Callback(hObject, eventdata, handles) clc; global inbit numin ratioerr inbit = get(handles.bitin,'String'); inbit = str2num(inbit); numin = length(inbit); numout = get(handles.numout,'String'); numout = str2num(numout); len = get(handles.length,'String');
Thực hiện bộ giải mã Viterbi trên FPGA
Trang 102
Phần C: Phụ lục và tài liệu tham khảo
len = str2num(len); g1 = get(handles.g1,'String'); g1 = str2num(g1); g2 = get(handles.g2,'String'); g2 = str2num(g2); if numout == 1 trellis = poly2trellis(len,g1); elseif numout == 2 trellis = poly2trellis(len,[g1 g2]); end encbits = convenc(inbit,trellis); encbits = num2str(encbits); set(handles.bitencoded,'String',encbits) encbits = str2num(encbits); encbits = 2*encbits - 1; snr = get(handles.snr,'String'); snr = str2num(snr); awgnbits = awgn(encbits, snr, 'measured'); str = get(handles.typeofdec,'String'); val = get(handles.typeofdec,'Value'); switch str{val} case 'Soft Decision'. select = 0; case 'Hard Decision' select = 1; case 'Both' select = 2; end if select == 0 partition = [-.8571 -.5714 -.2857 0 .2857 .5714 .8571]; codebook = [-.99 -.8571 -.5714 -.2857 0 .2857 .5714 .8571]; quanbits = quantiz(awgnbits,partition,codebook); tblen = numin -1 ; opmode = 'term'; dectype = 'soft'; nsdec = 3; decbits = vitdec(quanbits,trellis,tblen,'term','soft',nsdec);
Thực hiện bộ giải mã Viterbi trên FPGA
Trang 103
Phần C: Phụ lục và tài liệu tham khảo
end if select == 1 partition = [0]; codebook = [0 1]; quanbits = quantiz(awgnbits,partition,codebook); tblen = numin-1; opmode = 'term' ; dectype = 'hard'; decbits = vitdec(quanbits,trellis,tblen,'term','hard'); end decbits = num2str(decbits); set(handles.bitout,'String',decbits) decbits = str2num(decbits); [numerr ratioerr] = biterr(inbit, decbits); numerr = num2str(numerr); set(handles.numerr,'String',numerr); numerr = str2num(numerr); ratioerr = num2str(ratioerr); set(handles.ratioerr,'String',ratioerr); ratioerr = str2num(ratioerr); function reset_Callback(hObject, eventdata, handles) clc; set(handles.typeofdec,'Value',1); set(handles.auto,'Value',0); set(handles.bitin,'Enable','inactive'); set(handles.numin,'String',''); set(handles.numout,'String','2'); set(handles.length,'String','3'); set(handles.g1,'String','5'); set(handles.g2,'String','7'); set(handles.snr,'String','5'); set(handles.bitin,'String',''); set(handles.bitencoded,'String',''); set(handles.bitout,'String',''); set(handles.numerr,'String',''); set(handles.ratioerr,'String',''); set(handles.g2,'Enable','on'); set(handles.textber,'ForegroundColor','blue')
Thực hiện bộ giải mã Viterbi trên FPGA
Trang 104
Phần C: Phụ lục và tài liệu tham khảo
function togglebutton1_Callback(hObject, eventdata, handles) function edit17_Callback(hObject, eventdata, handles) function edit17_CreateFcn(hObject, eventdata, handles) if ispc && isequal(get(hObject,'BackgroundColor'), get(0,'defaultUicontrolBackgroundColor')) set(hObject,'BackgroundColor','white'); end function snr_Callback(hObject, eventdata, handles) user_entry = str2double(get(hObject,'string')); if isnan(user_entry) errordlg('Type the integer ! ','Input Error !','modal') set(hObject,'String',''); return end function snr_CreateFcn(hObject, eventdata, handles) if ispc && isequal(get(hObject,'BackgroundColor'), get(0,'defaultUicontrolBackgroundColor')) set(hObject,'BackgroundColor','white'); end function pushbutton5_Callback(hObject, eventdata, handles) function start_KeyPressFcn(hObject, eventdata, handles) function taoinbit_Callback(hObject, eventdata, handles) clc; global inbit numin ; if (get(handles.auto,'Value') == get(handles.auto,'Max')) a = 1; else a = 0; end if a == 1 inbit = get(handles.bitin,'String');
Thực hiện bộ giải mã Viterbi trên FPGA
Trang 105
inbit = str2num(inbit); else numin = get(handles.numin,'String'); numin = str2num(numin); inbit = randint(1,numin); end inbit = num2str(inbit); set(handles.bitin,'Enable','on'); set(handles.bitin,'String',inbit); inbit = str2num(inbit); function viwebit_Callback(hObject, eventdata, handles) close 'Gui_3' ; function typeofdec_Callback(hObject, eventdata, handles) function typeofdec_CreateFcn(hObject, eventdata, handles) if ispc && isequal(get(hObject,'BackgroundColor'), get(0,'defaultUicontrolBackgroundColor')) set(hObject,'BackgroundColor','white'); end
4. Mã nguồn VHDL
Phần C: Phụ lục và tài liệu tham khảo
Viterbi.vhd LIBRARY ieee; USE ieee.std_logic_1164.all; USE ieee.std_logic_arith.all; USE ieee.std_logic_unsigned.all; USE work.distance.all; USE work.converter.all; ENTITY viterbi is GENERIC( CONSTANT K: natural: = 1; CONSTANT N: natural: = 2; CONSTANT L: natural: = 3; CONSTANT Ga: natural: = 5; CONSTANT Gb: natural: = 7; CONSTANT V: natural: = 8 );
Thực hiện bộ giải mã Viterbi trên FPGA
Trang 106
: in std_logic;
clk reset : in std_logic; start : in std_logic; dec_in : in std_logic; sel_dec: in std_logic; : in std_logic_vector (V*N-1 downto 0); data data_out: out std_logic_vector (V-1 downto 0); conv_in: in std_logic_vector(V-1 downto 0); conv_out: out std_logic_vector(V*N-1 downto 0)
: matrix_7;
TYPE matrix_1 is array (0 to 3, 0 to 1) of std_logic_vector(3 downto 0); TYPE matrix_2 is array (0 to 3, 0 to 10) of integer ; TYPE matrix_3 is array (0 to 3, 0 to 1) of integer; TYPE matrix_4 is array (0 to 8) of integer; TYPE matrix_7 is array (0 to 7) of std_logic_vector (1 downto 0); TYPE matrix_8 is array (0 to 3, 0 to 10) of integer; TYPE matrix_9 is array (0 to 10) of integer; SIGNAL data_in SIGNAL ne_st_reg: matrix_1; BEGIN
-- the firt part is get data input
data_in(7-v2) <= data(v2*2+1 downto v2*2);
FOR v2 in 0 to 7 LOOP END LOOP;
IF reset = '0' THEN v2: = 0; ELSIF dec_in = '1' THEN END IF;
get_data_in: PROCESS(dec_in,reset,sel_dec) VARIABLE v2: integer; BEGIN END PROCESS;
Phần C: Phụ lục và tài liệu tham khảo
PORT( ); END viterbi; ARCHITECTURE rtl OF viterbi IS --------------------------------------------------------------------------------- --------------------------------------------------------------------------------- ------------------------------------------------------------------------------- -- The second part is to initialize the next state -------------------------------------------------------------------------------- next_state_out_reg: PROCESS(reset) VARIABLE lp1: std_logic_vector(1 downto 0);
Thực hiện bộ giải mã Viterbi trên FPGA
Trang 107
lp2: = '0';
lp2: = '1';
lp1: = conv_std_logic_vector(l1,2); IF l2=0 THEN ELSE END IF;
FOR l1 in 0 to 3 LOOP FOR l2 in 0 to 1 LOOP -- next state and output bits IF reset = '0' THEN lp1: = "00"; lp2: = '0'; ELSE VARIABLE lp2: std_logic; VARIABLE l1,l2,l3: integer; BEGIN
END LOOP;
END LOOP;
END IF;
END PROCESS;
: std_logic_vector(V-1 downto 0); : matrix_8; -- accumalated metric table : matrix_9; -- survier path register : integer: =0; -- internal cuonter : std_logic: = '0';
Phần C: Phụ lục và tài liệu tham khảo
ne_st_reg(l1,l2) <= lp2&lp1(1)&(lp2 xor lp1(0))&(lp2 xor lp1(1) xor lp1(0)); ------------------------------------------------------------------------------- -- The third part is calculate Hamming distance -------------------------------------------------------------------------------- VARIABLE pre_state_reg: matrix_2; -- previous states for trace back : matrix_3; -- aem VARIABLE aem_reg VARIABLE ssa_reg: matrix_4; -- trace back VARIABLE result VARIABLE ac_reg VARIABLE sv_reg VARIABLE cnt VARIABLE flag VARIABLE dist_00, dist_01, dist_10, dist_11: integer; VARIABLE v3: integer: =0; VARIABLE t1: std_logic_vector (1 downto 0); VARIABLE t3,t4: integer range 0 to 3; VARIABLE l1,l2,l3: integer; VARIABLE dec_en: std_logic: = '0'; BEGIN IF reset = '0' THEN v3: = 0; cnt: = 0; Hd_calculation: PROCESS(clk,start)
Thực hiện bộ giải mã Viterbi trên FPGA
Trang 108
ELSIF start = '1' THEN IF Rising_edge(clk) THEN
cnt: = 0;
IF sel_dec = '1' THEN -- Euclidean
ac_reg(l1,l2): = 0;
aem_reg(l1,0): = 0; aem_reg(l1,1): = 0; FOR l2 in 0 to 8 LOOP END LOOP;
FOR l1 in 0 to 3 LOOP END LOOP;
ac_reg(0,1): = dist_00 ; ac_reg(2,1): = dist_11 ; pre_state_reg(0,1): = 0; pre_state_reg(2,1): = 0;
Phần C: Phụ lục và tài liệu tham khảo
-- cnt is a counter to count terllics diagrame to tell us which step now cnt: = cnt + 1; IF cnt = 10 THEN END IF; -- This part is to calculate Hamming distance or Euclidean distance dist_00: = euclid(data_in(cnt-1),"00"); dist_01: = euclid(data_in(cnt-1),"01"); dist_10: = euclid(data_in(cnt-1),"10"); dist_11: = euclid(data_in(cnt-1),"11"); ELSE -- Hamming dist_00: = hamming(data_in(cnt-1),"00"); dist_01: = hamming(data_in(cnt-1),"01"); dist_10: = hamming(data_in(cnt-1),"10"); dist_11: = hamming(data_in(cnt-1),"11"); END IF; ------------------------------------------------ -- This is ACS block ------------------------------------------------- -- This is Branch Metric Unit WHEN 0 => WHEN 1 => WHEN 2 => CASE cnt is ac_reg(0,2): = dist_00 + ac_reg(0,1); ac_reg(1,2): = dist_01 + ac_reg(2,1); ac_reg(2,2): = dist_11 + ac_reg(0,1);
Thực hiện bộ giải mã Viterbi trên FPGA
Trang 109
ac_reg(3,2): = dist_10 + ac_reg(2,1); pre_state_reg(0,2): = 0; pre_state_reg(2,2): = 0; pre_state_reg(1,2): = 2; pre_state_reg(3,2): = 2;
WHEN others => aem_reg(0,0): = dist_00 + ac_reg(0,cnt-1); aem_reg(2,0): = dist_11 + ac_reg(0,cnt-1); aem_reg(1,0): = dist_01 + ac_reg(2,cnt-1); aem_reg(3,0): = dist_10 + ac_reg(2,cnt-1); aem_reg(0,1): = dist_11 + ac_reg(1,cnt-1); aem_reg(2,1): = dist_00 + ac_reg(1,cnt-1); aem_reg(1,1): = dist_10 + ac_reg(3,cnt-1); aem_reg(3,1): = dist_01 + ac_reg(3,cnt-1); END CASE;
IF (cnt >= 3) and (cnt <= 8) THEN FOR l1 in 0 to 3 LOOP t1: = conv_std_logic_vector(l1,2); IF aem_reg(l1, 0) <= aem_reg(l1, 1) THEN ac_reg(l1,cnt): = aem_reg(l1, 0); pre_state_reg(l1,cnt): = conv_int(t1(0) & '0'); ELSE ac_reg(l1,cnt): = aem_reg(l1, 1); pre_state_reg(l1,cnt): = conv_int(t1(0) & '1'); END IF;
END LOOP;
--The following part compare each 2 possible path and select -- a small one and write the survival path to the survival path register. END IF;
-- compare the third step
l2: = ac_reg(0,2);
Phần C: Phụ lục và tài liệu tham khảo
-- This is the trace back part which finds the Most Likelihood Path IF cnt = 9 THEN sv_reg(0): = 0; -- 0 is allway the first step IF ac_reg(0,1) < ac_reg(2,1) THEN -- the second step sv_reg(1): = 0; ELSIF ac_reg(0,1) > ac_reg(2,1) THEN sv_reg(1): = 2; ELSE IF ac_reg(0,2) <= ac_reg(2,2) THEN ELSE l2: = ac_reg(2,2);
Thực hiện bộ giải mã Viterbi trên FPGA
Trang 110
l3: = ac_reg(1,2);
l3: = ac_reg(3,2);
sv_reg(1): = 0;
sv_reg(1): = 2;
END IF; IF ac_reg(1,2) <= ac_reg(3,2) THEN ELSE END IF; IF l2 <= l3 THEN ELSE END IF; END IF; FOR l1 in 2 to 8 LOOP IF ac_reg(0,l1) <= ac_reg(1,l1) THEN l2: = ac_reg(0,l1); ELSE l2: = ac_reg(1,l1); END IF; IF ac_reg(2,l1) <= ac_reg(3,l1) THEN l3: = ac_reg(2,l1); ELSE l3: = ac_reg(3,l1); END IF; IF l2 < l3 THEN
sv_reg(l1): = 0;
SV_reg(l1): = 1;
sv_reg(l1): = 2;
sv_reg(l1): = 3; END IF;
l2: = ac_reg(0,l1+1);
l2: = ac_reg(1,l1+1);
Phần C: Phụ lục và tài liệu tham khảo
IF ac_reg(0,l1) <= ac_reg(1,l1) THEN ELSE END IF; ELSIF l2 > l3 THEN ac_reg(2,l1) <= ac_reg(3,l1) THEN ELSE ELSE IF ac_reg(0,l1+1) <= ac_reg(1,l1+1) THEN ELSE END IF;
Thực hiện bộ giải mã Viterbi trên FPGA
Trang 111
l3: = ac_reg(2,l1+1);
l3: = ac_reg(3,l1+1);
END IF; SV_reg(l1): = pre_state_reg(1,l1+1); IF ac_reg(0,l1+1) <= ac_reg(1,l1+1) THEN sv_reg(l1): = pre_state_reg(0,l1+1); ELSE
END IF; IF l1 = 8 THEN flag: = '1'; ELSE flag: = '0'; END IF;
sv_reg(l1): = pre_state_reg(3,l1+1); END IF; IF ac_reg(2,l1+1) <= ac_reg(3,l1+1) THEN sv_reg(l1): = pre_state_reg(2,l1+1); ELSE END IF; END IF; END LOOP;
IF flag = '1' THEN
FOR l1 in 0 to 7 LOOP t3: = sv_reg(l1); t4: = sv_reg(l1+1); IF t4 = conv_int(ne_st_reg(t3, 0)(3 downto 2)) THEN result(l1): = '0';
END IF; END LOOP;
Phần C: Phụ lục và tài liệu tham khảo
IF ac_reg(2,l1+1) <= ac_reg(3,l1+1) THEN ELSE END IF; IF l2 <= l3 THEN ELSIF l2 > l3 THEN ----------------------------------------------------------------------- -- when the flag is one, it means the TB part is done. -- Then the decoder begins to decode the data ELSIF t4 = conv_int(ne_st_reg(t3, 1)(3 downto 2)) THEN result(l1): = '1'; END IF; END IF; FOR l1 in 0 to 7 LOOP data_out(l1) <= result(7-l1);
Thực hiện bộ giải mã Viterbi trên FPGA
Trang 112
END LOOP; IF l1 = 7 THEN dec_en: = '1'; END IF;
END IF; END PROCESS;
ff: = ff(1 downto 0) & conv_in(i-1) ; conv_out_v(j): = ff(0) xor ff(2); conv_out_v(j-1): = ff(0) xor ff(1) xor ff(2);
IF i > 0 THEN END IF; j: = j-2; i: = i-1 ;
conv_out <= conv_out_v(15 downto 0) ;
IF reset = '0' THEN i:= 8; j: = 15; ELSIF Rising_edge(clk) THEN END IF;
FUNCTION conv_std_logic(gt_v: in INTEGER; sl_v: in INTEGER)
FUNCTION conv_int(gt_i: in std_logic_vector(1 downto 0)) RETURN
Phần C: Phụ lục và tài liệu tham khảo
------------------------------------------------------------------------- -- This part is show convolution processor. Convolution: PROCESS(clk,reset) VARIABLE conv_out_v: std_logic_vector(15 downto 0); VARIABLE ff: std_logic_vector(2 downto 0):="000"; VARIABLE i: integer: = 8; VARIABLE j: integer: = 15; BEGIN IF i = 0 THEN END IF; END PROCESS; END ARCHITECTURE rtl; CONVERTER.VHD LIBRARY IEEE; USE ieee.std_logic_1164.all; USE ieee.std_logic_arith.all; USE ieee.std_logic_unsigned.all; PACKAGE converter IS RETURN std_logic_vector; integer; END converter;
Thực hiện bộ giải mã Viterbi trên FPGA
Trang 113
FUNCTION conv_std_logic(gt_v,sl_v: integer) RETURN std_logic_vector
VARIABLE i_v: integer range 0 to (gt_v - 1): = 0; VARIABLE u_v: std_logic_vector(sl_v downto 0); BEGIN IF gt_v /= 0 THEN FOR i in 0 to (gt_v - 1) LOOP u_v: = u_v + 1; END LOOP; END IF; RETURN u_v; END conv_std_logic; FUNCTION conv_int(gt_i: in std_logic_vector(1 downto 0)) RETURN
WHEN "00" => i_i: = 0; WHEN "01" => i_i: = 1; WHEN "10" => i_i: = 2; WHEN others => i_i: = 3;
END conv_int; CASE gt_i IS END CASE; RETURN i_i;
FUNCTION hamming(i1,i2: in std_logic_vector(1 downto 0)) RETURN
FUNCTION euclid(e1,e2: in std_logic_vector(1 downto 0)) RETURN
Phần C: Phụ lục và tài liệu tham khảo
PACKAGE BODY converter IS IS integer IS VARIABLE i_i, u_i: integer; BEGIN END converter; DISTANCE.VHD LIBRARY IEEE; USE ieee.std_logic_1164.all; USE ieee.std_logic_arith.all; USE ieee.std_logic_unsigned.all; USE work.converter.all; PACKAGE distance IS integer; integer; END distance; PACKAGE BODY distance IS
Thực hiện bộ giải mã Viterbi trên FPGA
Trang 114
FUNCTION hamming(i1,i2: in std_logic_vector(1 downto 0)) RETURN
u(0): = '1';
u(0): = '0';
u(1): = '1';
u(1): = '0';
result: = 0;
result: = result + 1;
result: = result + 1;
IF i1(0) > '0' THEN ELSE END IF; IF i1(1) > '0' THEN ELSE END IF; IF u(0) = i2(0) THEN ELSE END IF; IF u(1) = i2(1) THEN result: = result; ELSE END IF;
VARIABLE result: integer: = 0; VARIABLE u: std_logic_vector(1 downto 0); BEGIN RETURN result;
type display_mode is ( name, information,author, inoutbit, bits);
Phần C: Phụ lục và tài liệu tham khảo
integer IS END hamming; END distance; DISPLAY.VHD LIBRARY ieee; USE ieee.std_logic_1164.all; package display_types is end package display_types; LIBRARY ieee; USE ieee.std_logic_1164.all; USE work.display_types.all; USE work.lcd_types.all; package display_components is
Thực hiện bộ giải mã Viterbi trên FPGA
Trang 115
reset, clock: IN STD_LOGIC; : IN std_logic_vector(17 downto 0); SW DATA_OUT: IN std_logic_vector(7 downto 0); mode: IN display_mode; lcd_dd: OUT CHAR_VECTOR(0 to 31)
reset, clock: IN STD_LOGIC; SW : IN std_logic_vector(17 downto 0); DATA_OUT: IN std_logic_vector(7 downto 0); mode: IN display_mode; lcd_dd: OUT CHAR_VECTOR(0 to 31)
Phần C: Phụ lục và tài liệu tham khảo
component display is PORT ( ); end component; end package; LIBRARY ieee; USE ieee.std_logic_1164.all; USE ieee.std_logic_unsigned.all; use ieee.numeric_std.all; USE work.display_types.all; USE work.lcd_types.all; USE work.lcd_conv.all; ENTITY display IS PORT ( ); END ENTITY display; ARCHITECTURE display OF display IS SIGNAL A: char: = x"41";SIGNAL B: char: = x"42"; SIGNAL C: char: = x"43";SIGNAL D: char: = x"44"; SIGNAL E: char: = x"45";SIGNAL F: char: = x"46"; SIGNAL G: char: = x"47";SIGNAL H: char: = x"48"; SIGNAL I: char: = x"49";SIGNAL J: char: = x"4A"; SIGNAL K: char: = x"4B";SIGNAL L: char: = x"4C"; SIGNAL M: char: = x"4D";SIGNAL N: char: = x"4E"; SIGNAL O: char: = x"4F";SIGNAL P: char: = x"50"; SIGNAL Q: char: = x"51";SIGNAL R: char: = x"52"; SIGNAL S: char: = x"53";SIGNAL T: char: = x"54"; SIGNAL U: char: = x"55";SIGNAL V: char: = x"56"; SIGNAL W: char: = x"57";SIGNAL X: char: = x"58"; SIGNAL Y: char: = x"59";SIGNAL Z: char: = x"5A";
Thực hiện bộ giải mã Viterbi trên FPGA
Trang 116
SIGNAL s1: char: = x"31";SIGNAL s6: char: = x"36"; SIGNAL s2: char: = x"32";SIGNAL s7: char: = x"37"; SIGNAL s3: char: = x"33";SIGNAL s8: char: = x"38"; SIGNAL s4: char: = x"34";SIGNAL s9: char: = x"39"; SIGNAL s5: char: = x"35";SIGNAL s0: char: = x"30"; SIGNAL KT: char: = x"20"; -- KHOANG TRONG
(b162slv(SW(15 downto 0))) when bits;
subtype char is std_logic_vector(7 downto 0); type char_vector is array(natural range <>) of char;
Phần C: Phụ lục và tài liệu tham khảo
BEGIN -- the first row with mode select lcd_dd(0 to 15) <= -- DH SPKT TP HCM (KT,D,H,KT,S,P,K,T,KT,T,P,KT,H,C,M,KT) when information, -- GIAI THUAT (KT,KT,G,I,A,I,KT,KT,T,H,U,A,T,KT,KT,KT) when name, --SVTH LE DUY (S,V,T,H,KT,KT,L,E,KT,D,U,Y,KT,KT,KT,KT) when author, --16 BITS VAO (s1,s6,KT,B,I,T,S,KT,V,A,O,KT,KT,KT,KT,KT) when inoutbit, -- hien thi 16 bitS vao -- the second row with mode select lcd_dd(16 to 31) <= --DO AN TOT NGHIEP (D,O,KT,A,N,KT,T,O,T,KT,N,G,H,I,E,P) when information, -- VITERBI (KT,KT,KT,KT,V,I,T,E,R,B,I,KT,KT,KT,KT,KT) when name, -- HUYNH MINH KHA (KT,H,U,Y,N,H,KT,M,I,N,H,KT,K,H,A,KT) when author, --8 BIT RA (s8,KT,B,I,T,S,KT,R,A,KT,KT,KT,KT,KT,KT,KT) when inoutbit, -- hien thi 8 bits ra (b82slv(DATA_OUT(7 downto 0))) when bits; END ARCHITECTURE display; LCD.VHD library ieee; use ieee.std_logic_1164.all; package lcd_types is end package lcd_types; library ieee;
Thực hiện bộ giải mã Viterbi trên FPGA
Trang 117
reset, clock: IN STD_LOGIC; dd: IN CHAR_VECTOR(0 to 31); LCD_ON: OUT STD_LOGIC; LCD_BLON: OUT STD_LOGIC; LCD_RW: OUT STD_LOGIC; LCD_EN: OUT STD_LOGIC; LCD_RS: OUT STD_LOGIC; LCD_DATA: INOUT STD_LOGIC_VECTOR(7 DOWNTO 0) );
component lcd is port( end component lcd;
reset, clock: IN STD_LOGIC; dd: IN CHAR_VECTOR(0 to 31); LCD_ON: OUT STD_LOGIC; LCD_BLON: OUT STD_LOGIC; LCD_RW: OUT STD_LOGIC; LCD_EN: OUT STD_LOGIC; LCD_RS: OUT STD_LOGIC; LCD_DATA: INOUT STD_LOGIC_VECTOR(7 DOWNTO 0)
PORT( );
Phần C: Phụ lục và tài liệu tham khảo
use ieee.std_logic_1164.all; use work.lcd_types.all; package lcd_components is end package lcd_components; library ieee; use ieee.std_logic_1164.all; use ieee.std_logic_unsigned.all; use ieee.numeric_std.all; use work.lcd_types.all; ENTITY lcd IS END ENTITY lcd; ARCHITECTURE lcd of lcd is SIGNAL wait_counter: INTEGER: = 0; SIGNAL timing_counter: INTEGER: = 0; TYPE timing_states IS (idle, setup, hold); SIGNAL timing_state: timing_states: = idle; TYPE timing_modes IS (idle, read_cmd, read_data, write_cmd, write_data); SIGNAL timing_mode: timing_modes: = idle; SIGNAL timing_done: STD_LOGIC: = '1';
Thực hiện bộ giải mã Viterbi trên FPGA
Trang 118
x"38", -- set up interface x"0C", -- set up display x"01", -- clear screen x"06" -- set up entry mode
CONSTANT init_cmds_count: INTEGER: = 4; CONSTANT init_cmds: CHAR_VECTOR(0 to init_cmds_count - 1): = ( ); CONSTANT init_cmds_wait: INTEGER: = 100000; -- wait 2 ms for each
TYPE states IS ( init, init_cmd, init_cmd_complete, update_dd, update_dd_addr, update_dd_addr_complete, update_dd_data, update_dd_data_complete ); SIGNAL state: states: = init; SIGNAL i, j: INTEGER: = 0;
timing_state <= idle; timing_counter <= 0; timing_done <= '1';
timing_counter <= timing_counter - 1;
Phần C: Phụ lục và tài liệu tham khảo
init command BEGIN LCD_ON <= '1'; LCD_BLON <= '1'; timing: PROCESS(clock, reset) IS BEGIN IF (reset = '1') THEN ELSIF (clock = '1' AND clock'event) THEN IF (timing_counter > 0) THEN ELSE CASE timing_state IS WHEN idle => CASE timing_mode IS WHEN idle => LCD_RS <= '0'; LCD_RW <= '1'; timing_done <= '1';
Thực hiện bộ giải mã Viterbi trên FPGA
Trang 119
timing_state <= idle;
LCD_RS <= '0'; LCD_RW <= '1'; timing_done <= '0'; timing_counter <= 3; timing_state <= setup;
LCD_RS <= '1'; LCD_RW <= '1'; timing_done <= '0'; timing_counter <= 3; timing_state <= setup;
WHEN read_cmd => WHEN read_data => WHEN write_cmd => LCD_RS <= '0'; LCD_RW <= '0'; timing_done <= '0'; timing_counter <= 3; timing_state <= setup; WHEN write_data => LCD_RS <= '1'; LCD_RW <= '0'; timing_done <= '0'; timing_counter <= 3; timing_state <= setup; END CASE;
LCD_EN <= '1'; timing_counter <= 30; timing_state <= hold;
WHEN setup => WHEN hold => LCD_EN <= '0'; timing_counter <= 3000; -- a 60 microsecond wait
timing_state <= idle;
timing_state <= idle;
WHEN others => END CASE;
END IF;
END IF;
Phần C: Phụ lục và tài liệu tham khảo
guarantees operation execution END PROCESS;
Thực hiện bộ giải mã Viterbi trên FPGA
Trang 120
timing_mode <= idle; state <= init;
wait_counter <= wait_counter - 1;
i <= 0; timing_mode <= idle; wait_counter <= init_cmds_wait; state <= init_cmd;
LCD_DATA <= init_cmds(i); timing_mode <= write_cmd; wait_counter <= init_cmds_wait; state <= init_cmd_complete;
state <= update_dd; -- sai
i <= i + 1; state <= init_cmd;
IF (i = init_cmds_count - 1) THEN ELSE END IF;
i <= 0; j <= 0; state <= update_dd_addr;
IF (reset = '1') THEN ELSIF (clock = '1' AND clock'event) THEN IF (timing_mode /= idle) THEN timing_mode <= idle; ELSIF (timing_done /= '1') THEN ELSIF (wait_counter > 0) THEN ELSE CASE state IS WHEN init => WHEN init_cmd => WHEN init_cmd_complete => WHEN update_dd => -- hien thi lcd 16X2 WHEN update_dd_addr => LCD_DATA <= "1" & std_logic_vector(to_unsigned(i,
timing_mode <= write_cmd; state <= update_dd_addr_complete;
Phần C: Phụ lục và tài liệu tham khảo
fsm: PROCESS(clock, reset) IS BEGIN 1)) & "00" & std_logic_vector(to_unsigned(j, 4)); WHEN update_dd_addr_complete => state <= update_dd_data;
Thực hiện bộ giải mã Viterbi trên FPGA
Trang 121
LCD_DATA <= dd(i * 16 + j); timing_mode <= write_data; state <= update_dd_data_complete;
state <= update_dd; -- quay lai lam lai
j <= 0; i <= i + 1; state <= update_dd_addr;
IF (i = 1) THEN ELSE END IF;
j <= j + 1; state <= update_dd_addr;
WHEN update_dd_data => WHEN update_dd_data_complete => IF (j = 15) THEN ELSE END IF;
state <= init;
WHEN others => END CASE;
END IF;
END IF;
TYPE out_vector is array (0 to 15 ) of std_logic_vector(7 downto 0);
Phần C: Phụ lục và tài liệu tham khảo
END PROCESS; END ARCHITECTURE lcd; LCD_CONV.VHD LIBRARY ieee; USE ieee.std_logic_1164.all; PACKAGE lcd_conv_type is END PACKAGE lcd_conv_type; LIBRARY ieee; USE ieee.std_logic_1164.all; USE ieee.std_logic_arith.all; USE ieee.std_logic_unsigned.all; USE work.lcd_types.all; USE work.lcd_conv_type.all; PACKAGE lcd_conv IS
Thực hiện bộ giải mã Viterbi trên FPGA
Trang 122
FUNCTION b162slv(bin: in std_logic_vector(15 downto 0)) RETURN
FUNCTION b82slv(bin: in std_logic_vector(7 downto 0)) RETURN
WHEN '0' => slv(t): = x"30"; -- 0 WHEN others => slv(t): = x"31"; -- 1
VARIABLE slv: char_vector (15 downto 0) ; VARIABLE t: integer; BEGIN FOR t in 0 to 15 LOOP CASE bin(t) IS END CASE; END LOOP;
RETURN slv;
WHEN '0' => slv(t+4): = x"30"; WHEN others => slv(t+4): = x"31";
CASE bin(t) IS END CASE;
slv(t): = x"20"; -- khoang trang
FOR t in 0 to 3 LOOP slv(t): = x"20"; -- khoang trang END LOOP; FOR t in 12 to 15 LOOP END LOOP; RETURN slv;
Phần C: Phụ lục và tài liệu tham khảo
char_vector; char_vector; END lcd_conv; PACKAGE BODY lcd_conv IS FUNCTION b162slv(bin: in std_logic_vector(15 downto 0)) RETURN char_vector IS END b162slv; FUNCTION b82slv(bin: in std_logic_vector(7 downto 0)) RETURN char_vector IS VARIABLE slv: char_vector (15 downto 0); VARIABLE t: integer; BEGIN FOR t in 0 to 7 LOOP END LOOP; END b82slv; END lcd_conv;
Thực hiện bộ giải mã Viterbi trên FPGA
Trang 123
II. Tài liệu tham khảo
[1] John Proakis, Digital Communications (Chapter 8-Block and Convolutional Channel Codes), McGraw-Hill Science/ Engineering/ Math, 4th, 2000.
Codes(chapter 2_convolution codes), Master's Thesis, 1997.
[2] Fu Hua Huang, Evaluation of Soft Output Decoding for Turbo
[3] Mr. Chip Fleming, Tutorial on Convolutional Coding with Viterbi
Decoding, Spectrum Applications, 2006.
[4] Wei Chen, RTL implementation of Viterbi decoder, Master’s thesis
performed in Computer Engineering, 2006.
[5] Nguyễn Minh Khánh Ngọc, Luận văn cao học “Thiết kế và thực hiện gải
thuật Viterbi trên FPGA”, 2009.
[6] Một số trang web mà nhóm có tham khảo:
http://www.altera.com
http://www.fotech.org
http://www.ngohaibac.net
http://www.mathwork.com
http://en.wikipedia.org
http://www.dsplog.com
http://home.netcom.com
Phần C: Phụ lục và tài liệu tham khảo
http://gaussianwaves.blogspot.com
