Chương 1 TỔNG QUAN 1. Tổng quan về lĩnh vực nghiên cứu, các kết quả nghiên cứu trong và ngoài nước đã công bố Trong những năm gần đây, rất nhiều thuật toán nén, mã hóa và giải mã ký tự và dữ liệu cho ứng dụng vi điều khiển trong giao tiếp, hiển thị cũng như kết nối với FPGA. Một thuật toán nén dùng phương pháp LZSS có khả năng xử lý tới 50 MB trên một giây trên một chip FPGA Virtex-5. Bài báo này còn khai thác các khối RAM cổng kép có thể định được địa chỉ độc lập bên trong chip FPGA để đạt được hiệu suất trung bình là 2 byte tốc độ đồng hồ.
Để làm cho luồng nén tương thích với thư viện ZLib [1], việc mã hóa đầu ra của thuật toán LZSS sử dụng một bảng Huffman cố định được xác định bởi đặc tả của Deflate [2]. Nghiên cứu này chứng minh có thể thay đổi số lượng bộ nhớ được phân bổ cho các bảng nội bộ khác nhau tác động đến hiệu suất và tỷ lệ nén. Thuật toán giải nén LZW được nghiên cứu và ứng dụng trong FPGA. Các kết quả thực nghiệm cho thấy một mô đun được đề xuất cho họ Virtex-7 FPGA XC7VX485T- 2 chạy nhanh hơn 2,16 lần so với giải nén với phương pháp LZW tuần tự trên một CPU duy nhất, ở đó tần số của FPGA là 301,02 MHz.
Vì mô đun được đề xuất được thiết kế gọn nhẹ và sử dụng một số tài nguyên của FPGA nên nghiên cứu đã thành công trong việc thực hiện 150 mô-đun giống hệt nhau trên FPGA, ở đó tần số của FPGA là 245,4MHz [3]. Trong nghiên cứu này, thiết kế dựa trên FPGA được giới thiệu và thực hiện một bộ lưới tam giác 3D. Lưới tam giác là ưu điểm trong mô hình hình học 3D. Qui trình giải nén nguyên mẫu được dựa trên thuật toán nén lưới tam giác đơn giản và hiệu quả cao, được gọi là mã hóa BFT [10-11].
Hơn nữa, đây còn là phần cứng đầu tiên được thực hiện việc giải nén hình tam giác. Vậy thì, trình giải nén có thể được thêm vào ở đầu giao diện của một card đồ họa 3D trên PCI/AGP. Nó có thể làm giảm băng thông yêu cầu trên bus giữa máy chủ lưu trữ và card đồ hoạ lên tới 80% so với các biểu diễn lưới tam giác chuẩn [4]. Tổng quan Bài báo này mô tả một phương pháp nén dữ liệu cho các hệ thống FPGA được gọi là GCC (Thuật toán mã nén Golomb).
Phương pháp này được sử dụng rộng rãi cho nén dữ liệu kiểu không tổn hao (Lossless) có độ phức tạp thấp hơn trong các phương pháp mã hóa và giải mã. Mục tiêu chính của việc nén dữ liệu này là tìm ra sự thừa và loại bỏ chúng thông qua thuật toán Golomb, do đó các dữ liệu được yêu cầu ít bộ nhớ cũng như kích thước của dữ liệu giảm vì thế chi phí truyền dẫn cũng giảm. Nghiên cứu này cho phép nén dữ liệu không tổn hao và tái tạo dữ liệu ban đầu có độ chính xác từ dữ liệu nén, trong khi nén dữ liệu không tổn hao không thể tái tạo các dữ liệu ban đầu hoàn hảo từ dữ liệu đã nén [5]. Trong kỹ thuật nén khác có thể được chia ra 3 bước: 1) sắp xếp thông minh của các bit nén mà có thể làm giảm đáng kể chi phí của động cơ giải nén; 2) sự kết hợp của nén dựa trên bitmask và chạy mã dài và các mẫu lặp lại; 3) lựa chọn tham số có lợi cho nén bitstream [6-7].
Hơn nữa, khám phá ý tưởng nén cấu hình và phát triển thuật toán cho các hệ thống nhận dạng và các thuật toán này nhắm đến áp dụng FPGA Xilinx Virtex với sửa đổi tối thiểu phần cứng, có thể làm giảm đáng kể lượng dữ liệu cần thiết để truyền tải trong quá trình cấu hình. Trong nghiên cứu này, kỹ thuật nén gồm mã hóa Huffman, mã hóa số học và mã hóa LZ, các thuật toán khác nhau được phát triển nhằm mục tiêu cấu trúc phần cứng khác nhau. Thuật toán readback cho phép các khung nhất định được sử dụng lại như là một từ điển và sử dụng đầy đủ các thông thường trong bitstream cấu hình [8]. Thuật toán nén trong GZIP sử dụng một biến thể của mã hóa LZ77, mã hóa Huffman tĩnh và mã hóa Huffman động.
Với thực tế là lưu lượng truy cập web chiếm 42% của tất cả lưu lượng truy cập internet, sự tăng tốc các thuật toán như GZIP có thể khá có lợi cho việc giảm lưu lượng internet. Việc thực hiện phần cứng của thuật toán GZIP có thể được sử dụng để cho phép các CPU thực hiện các tác vụ khác, do đó tăng hiệu suất của hệ thống [9]. Bên cạnh đó cón nhiều thuật toán nén và mã hóa như mã hóa jbit (JBE). Thuật toán này sẽ thao tác mỗi bit dữ liệu bên trong tệp để giảm thiểu kích thước mà không làm mất dữ liệu sau khi giải mã được phân loại thành nén không mất dữ liệu [10].
Thuật toán bảng 2 Luan van 1. Tổng quan tra cứu từ sẽ là một phần của hệ điều hành và việc giảm sẽ được thực hiện bởi hệ điều hành [11]. Tính cấp thiết Hiện nay, việc tính toán để dữ liệu chiếm càng ít dung lượng nhớ càng tốt, nhất là trong các hệ thống dùng vi điều khiển. Trong thực tế rất nhiều hệ thống dùng vi điều khiển để lưu trữ các dữ liệu dạng phông chữ và hình ảnh để hiển thị, để truyền đi và để in ấn cho nhanh trong các hệ thống các KIT thí nghiệm, Quản lý nhà thông minh, Điều khiển DRONE (quadcopter), Điều khiển xe tự hành, Điều khiển máy khâu, máy in trong công nghiệp, các sản phẩm cầm tay.
Một ứng dụng cụ thể như thiết bị phụ trợ in kỹ thuật số trong công nghiệp được dùng để in những hạn sử dụng, logo, mã vạch và những thông tin khác trên những sản phẩm dạng vật liệu giấy, nhựa hay thép. Việc in nhiều thông tin và in với tốc độ nhanh đòi hỏi phải có dữ liệu đa dạng và nhiều, điều này đòi hỏi phải có dung lượng lớn để lưu trữ. Hơn nữa, việc in còn đòi hỏi tốc độ cao. Để đáp ứng điều này, hệ thống sử dụng vi điều khiển có thể giao tiếp với FPGA cho điều khiển chính xác và tốc độ nhanh.
Để đáp ứng kỹ thuật này, việc nén phông chữ để giảm dung lượng lưu trong bộ nhớ là rất quan trọng bởi không chỉ đáp ứng được việc lưu đa dạng dữ liệu mà còn tang tốc độ điều khiển lên. Cụ thể, việc nén là cho phép mã hóa và giải mã ảnh phông chữ để giảm dung lượng khi truyền qua bộ FPGA để thực hiện điều khiển hệ thống nhanh và chính xác. Hơn nữa, việc giải mã phải đáp ứng chuẩn kết nối dữ liệu giữa bộ vi điều khiển và FPGA. Do vậy, phương pháp nén tối ưu là rất quan trọng và cấp thiết.
Mục tiêu đề tài Đề tài sẽ đưa ra giải pháp nén mới để đáp ứng việc mã hóa và giải mã phông chữ một cách tối ưu để lưu được nhiều dữ liệu phông chữ ảnh trong hệ thống vi điều khiển. Hơn nữa, kết quả được kiểm chứng trên hệ thống nhúng giữa vi điều khiển ARM và FPGA. Cách tiếp cận, phương pháp nghiên cứu, phạm vi nghiên cứu Cách tiếp cận 3 Luan van 1. Tổng quan Đưa ra giải pháp nén tối ưu, tính toán và chạy trên máy tính giả lập để kiểm chứng hiệu suất nén.
Đồng thời so sánh với các phương pháp nén trước đó. Sau đó, sử dụng các phương pháp nén đã được nghiên cứu để áp dụng trên mô hình thực tế để đánh giá tính khả thi trong ứng dụng. Phương pháp nghiên cứu - Phương pháp Huffman cho nén ảnh - Phương pháp nén phông ảnh bằng việc chia các pixel trong mỗi ký tự và nhóm ký tự - Kiểm chứng trên phần cứng - Đánh giá hiệu quả. Phạm vi nghiên cứu Kiến nghị phương pháp nén tối ưu cho phông chữ ảnh.
Nội dung nghiên cứu - Phương pháp nén ảnh - Tính toán hiệu quả nén ký tự ảnh của 1 số phông chữ - Trình bày kết quả mã hóa và giải mã - Các lưu đồ thuật giải và viết code - Kiểm chứng trên hệ thống phần cứng và hiệu chỉnh - Viết bài báo - Viết báo cáo. - Hoàn thiện các hồ sơ. Cơ sở lý thuyết Chương 2: CƠ SỞ LÝ THUYẾT 2. Tổng quan về nén dữ liệu Nén dữ liệu là quá trình làm giảm dung lượng trong dữ liệu gốc vì vậy sau khi nén thì dung lượng dữ liệu thu được thường nhỏ hơn dung lượng dữ liệu gốc.
Nén dữ liệu có thể thực hiện bằng phần cứng chuyên dùng hoặc bằng phần mềm. Các kỹ thuật nén dữ liệu bằng phần cứng yêu cầu phải có phần cứng được thiết kế đặc biệt thích hợp với dữ liệu muốn nén. Các kỹ thuật nén số liệu bằng phần mềm được thực hiện các thiết bị chạy hệ điều hành như Window, Linux, OS Apple có thể được sử dụng để nén file văn bản, các file ảnh, video hay là file âm thanh. Dữ liệu bao gồm: thông tin, độ dữ thừa, tỷ số nén và độ dài trung bình từ mã.
Dữ liệu dùng để biểu diễn và truyền tải thông tin, có thể biểu diễn một lượng thông tin cho trước bằng dung lượng khác nhau. Đơn vị đo dung lượng là bit. Một bit dung lượng được biểu diễn thông qua toán học là chữ số nhị phân 0 và 1. Độ dư thừa dữ liệu trong tập tin được tính dựa trên các yếu tố sau: sự phân bố ký hiệu, sự lập lại của các ký hiệu, những mẫu sử dụng mật độ cao, độ dư thừa vị trí.
Ví dụ, một ảnh chứa một một hàng dọc và hàng dọc này xuất hiện ở cùng một vị trí ở nhiều dòng khác nhau nên có thể mã hóa bằng cách giữ vị trí của hàng và cột đó thay vì giữ từng ký hiệu trong cột. Công thức biểu diễn độ dư thừa dữ liệu bằng toán học: 1 RD 1 (2.1) CN Trong đó RD là độ dư thừa dữ liệu tương đối, CN là tỷ lệ nén. Tỷ lệ nén CN là một đại lượng đặc trưng cho một phương pháp nén. Nó thể hiện phương pháp nén đó có tốt hay không.
Tỷ lệ nén được biểu diễn bằng công thức toán học như sau: N2 CN (2. Cơ sở lý thuyết Với N1 là kích thước tập tin trước khi nén, N2 là kích thước tập tin sau khi nén. Với công thức (2.2) nếu CN càng thấp thì hiệu suất nén càng cao.