Một phương pháp tăng tốc phép biến đổi Hadamard bằng kiến trúc pipeline

iện trên hình 3. Căn 
cứ vào sơ đồ hình 6, cấu trúc phần cứng bao gồm khối tạo tín hiệu điều khiển DRIVER 
FSM, khối ma trận chính-phụ (SYGN 64 bit), khối thao tác song song với phép tính nhân-
cộng tích lũy và khối dẫn dữ liệu ra FIFO, khối đầu ra FIFO. Hai phương án được lựa 
chọn thực thi biến đổi Hadamard để tiện so sánh. Phương án thứ nhất là phương án không 
sử dụng ma trận trọng số phụ, còn phương án thứ hai là phương án có sử dụng ma trận 
trọng số phụ. Máy trạng thái [2, 7] của 2 phương án được thể hiện trên hình 7a và 7b. 
Kỹ thuật điều khiển & Điện tử 
P. M. Tới, Đ. X. Tiến, H. T. Phương, “Một phương pháp tăng tốc  kiến trúc pipeline.” 100 
a) 
b) 
Hình 7. a) Máy trạnh thái không có ma trận phụ; 
b) Máy trạnh thái có ma trận phụ. 
Tương ứng với máy trạng thái là lưu đồ vòng lặp thao tác của ma trận trọng số 
Hadamard không có ma trận phụ và ma trận trọng số Hadamard có ma trận phụ như thể 
hiện trên hình 8. 
Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số 56, 08 - 2018 101
Hình 8. Vòng lặp thao tác cho a)ma trận trọng số Hadamard không có ma trận phụ, 
b) ma trận trọng số Hadamard có ma trận phụ. 
Như trên hình 8 cho thấy vòng lặp thao tác chính có sự khác biệt về thời gian thao tác. 
Đối với vòng lặp thao tác cho ma trận trọng số Hadamard không có ma trận phụ, hệ phải 
mất 80 clock mới xử lý xong 1 vector dữ liệu kích thước 8 byte, trong khi đó, với vòng lặp 
thao tác cho ma trận trọng số Hadamard có ma trận phụ, hệ chỉ mất 16 clock để xử lý xong 
1 vector dữ liệu kích thước 8 byte. Sự chênh lệch là rất rõ. 
3.2. Thực hiện mô phỏng và phân tích kết quả 
Khi chạy chương trình viết theo thuật toán hình 7 trên ModelSim6.5c cho thấy sự phù 
hợp với lưu đồ thuật toán thể hiện trên hình 7a và hình 8a. Đối với phương án không sử 
dụng ma trận trọng số phụ [4, 5] cho thấy sự phù hợp với lưu đồ thuật toán thể hiện trên 
hình 7a và hình 8a. Trong giai đoạn khởi đầu, hệ thống tiêu tốn 130 clock. Từ clock thứ 
131 đến clock thứ 138 là giai đoạn kết xuất dữ liệu của nửa đầu ma trận trọng số và sau 32 
clock, tới clock thứ 169 hệ thống mới kết xuất nửa sau ma trận trọng số. Khoảng thời gian 
tiêu tốn để nạp nửa ma trận trọng số là 32 clock. Quá trình này được mô phỏng trên 
ModelSim6.5c và được thể hiện trên đồ thị thời gian hình 9a và 9b. 
Đối với phương án có sử dụng ma trận trọng số phụ cho thấy sự phù hợp với máy trạng 
thái và lưu đồ thuật toán thể hiện trên hình 7b và hình 8b. Từ clock thứ 131 đến clock thứ 
138 là thời gian kết xuất dữ liệu của nửa đầu ma trận trọng số và ngay sau đó là clock thứ 
139 hệ thống thực hiện kết xuất nửa sau ma trận trọng số. Khoảng thời gian tiêu tốn để 
nạp nửa ma trận trọng số là 1 clock. Quá trình này được mô phỏng trên ModelSim6.5c và 
được thể hiện trên hình 10. 
Điều lưu ý là ma trận trọng số Hadarmad chỉ bao gồm giá trị +1 và -1 nên trong phần 
thiết kế chỉ cần sử dụng 1 bit để phân biệt. Bit đó là bit sign được ký hiệu trên sơ đồ và 
trong chương trình. Bit sign=0 tương đương với giá trị trọng số +1, còn bit sign=1 tương 
đương với giá trị trọng số -1. Cách làm này đã tiết kiệm tài nguyên rất nhiều và làm cấu 
trúc ma trận trọng số phụ được đơn giản đi nhiều. 
Điều quan trọng nhất là cấu trúc phần cứng trong sơ đồ tối giản đã giảm đi gần 8 lần 
trong khi tốc độ không thay đổi do mạch hồi tiếp có sử dụng kỹ thuật pipeline nên chỉ cần 
một clock là đã thực hiện xong phép nhân trọng số và tích lũy giá trị mới. Clock trong 
mạch này cao gấp 8 lần clock hệ thống. 
Kỹ thuật điều khiển & Điện tử 
P. M. Tới, Đ. X. Tiến, H. T. Phương, “Một phương pháp tăng tốc  kiến trúc pipeline.” 102 
a) 
b) 
Hình 9. a) Quá trình nhân và cộng tích lũy với nửa đầu ma trận trọng số; 
 b) Quá trình nhân và cộng tích lũy với nửa sau ma trận trọng số. 
Hình 10. Quá trình nhân và cộng tích lũy của hệ thống có ma trận trọng số phụ. 
Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số 56, 08 - 2018 103
Sử dụng ISE Design Suite 14.1 của Xilinx để thực thi phần cứng trên chip FPGA [2,7] 
XC3S500E-PQ208 đã cho ra kiến trúc có chức năng tương ứng với sơ đồ hình 6 và hoạt 
động theo thuật toán của máy trạng thái hình 7. Dưới đây là bảng thông tin về tài nguyên 
sử dụng (trích xuất từ cửa sổ phần mềm Xilinx ISE Design Suite) cho phương án không sử 
dụng ma trận trọng số phụ: 
 Các cấu trúc logic 
 được sử dụng 
 Đã sử dụng (Dung lượng chip 
 Đã sử dụng tính 
theo % tài nguyên 
Number of Slices 3154 4656 67% 
Number of Slice Flip Flops 3415 9312 36% 
Number of 4 input LUTs 2920 9312 31% 
Number of bonded IOBs 27 158 17% 
Number of GCLKs 1 24 4% 
Và dưới đây là bảng thông tin về tài nguyên sử dụng (trích xuất từ cửa sổ phần mềm 
Xilinx ISE Design Suite) cho phương án có sử dụng ma trận trọng số phụ: 
 Các cấu trúc logic 
 được sử dụng 
 Đã sử dụng Dung lượng chip 
Đã sử dụng tính 
theo % tài nguyên 
Number of Slices 3197 4656 68% 
Number of Slice Flip Flops 3446 9312 37% 
Number of 4 input LUTs 2971 9312 31% 
Number of bonded IOBs 25 158 15% 
Number of GCLKs 1 24 4% 
Điều đặc biệt là tài nguyên của phương án không sử dụng ma trận trọng số phụ và có 
sử dụng ma trận trọng số phụ không chênh lệch nhiều, ví dụ số lượng Slices là 3154 so với 
3197; số lượng input LUTs là 2920 so với 2971 Điều này có được là do phương pháp 
biểu diễn giá trị trọng số Hadarmad bằng 1 bit thay vì 1 byte. Hơn nữa với chip Xilinx gói 
XC3S500E-PQ208 chỉ tiêu tốn hết 68% dung lượng mà không cần phải sử dụng tới các 
cấu trúc FPGA cao hơn như FPGA Virtex-5 hay Virtex-6. 
4. KẾT LUẬN 
Đối với các hệ xử lý chuyên dụng, vấn đề dung hòa giữa tốc độ xử lý và độ tin cậy của 
hệ luôn luôn được đặt ra cho các nhà thiết kế. Kiến trúc hệ xử lý Hadamard trong bài báo 
sử dụng phương pháp tối giản cấu trúc phần cứng để nâng cao độ tin cậy nhưng tốc độ vẫn 
không thay đổi nhờ sử dụng kiến trúc pipeline trong mạch hồi tiếp thông minh. Cụ thể: 
Ma trận trọng số được tối giản (1 hàng×4 cột) đã nâng cao được độ tin cậy so với cấu 
trúc ma trận trọng số đầy đủ (8 hàng×4 cột). Hơn nữa, khi sử dụng ma trận trọng số phụ 
thực hiện chức năng copy giá trị ma trận trọng số từ ma trận trọng số phụ vào ma trận 
trọng số chính và kiến trúc pipeline thực hiện chức năng hồi tiếp giá trị kết quả trung gian 
để xử lý trong chu trình vòng lặp đã nâng cao tốc độ làm việc lên so với các phương pháp 
khác do quá trình tái nạp nửa ma trận trọng số chỉ cần trong một chu kỳ clock thay vì 32 
chu kỳ clock. Điều này cho phép trong thực tế chỉ cần sử dụng các chip FPGA thông 
thường thay vì phải sử dụng các chip FPGA cao cấp như Virtex-5 hay Virtex-6. 
Chương trình được viết trên ngôn ngữ mô tả phần cứng VHDL nên bám sát được cấu 
trúc phần cứng. Các khối chức năng đều được viết tách riêng thành các modul chương 
trình nên khi chỉnh sửa hay bổ sung tính năng hệ thống trở nên dễ dàng. Điều này cho 
phép mở rộng quy mô ma trận trọng số Hadamard khi cần thiết và điều khiển việc chia 
tách hàng và cột của ma trận trở nên khả thi hơn. 
Lời cảm ơn: Nhóm tác giả cảm ơn sự hỗ trợ của Phòng thí nghiệm Điện tử số và vi xử 
lý của Bộ môn Kỹ thuật Vi xử lý Khoa Vô tuyến điện tử, Học viện Kỹ thuật quân sự. 
Kỹ thuật điều khiển & Điện tử 
P. M. Tới, Đ. X. Tiến, H. T. Phương, “Một phương pháp tăng tốc  kiến trúc pipeline.” 104 
TÀI LIỆU THAM KHẢO 
[1]. Hoàng Thị Phương. “Thiết kế biến đổi HADAMARD tốc độ cao sử dụng trong các hệ 
vi xử tín hiệu số”. Tạp chí Khoa học Giáo Dục Kỹ Thuật, Đại học SPKT thành phố 
Hồ Chí Minh, năm 2014, số 27, tr. 09-16. 
[2]. Trịnh Quang Kiên, Lê Xuân Bằng. “Thiết kế logic số”. Nxb Học viện kỹ thuật quân 
sự, 2011. 
[3]. Trịnh Quang Kiên, Đào Văn Lân. “Nghiên cứu cải tiến hệ thống kiểm tra tên lửa 
Х35Э (3M-24E) trong tổ hợp tên lửa đối hạm URAN-E”. Đề tài NCKH cấp Bộ Quốc 
phòng 2011-2013. 
[4]. Sanat Kamal Bahi, Jim Plusquellic. “FPGA implementation of a fast Hadamard 
transformer for WCDMA”. Proceeding FPGA '03 Proceedings of the 2003 
ACM/SIGDA eleventh international symposium on Field programmable gate arrays. 
Pages 237 – 237. 
[5]. Ankit Agrawa, Amit Joshi. “FPGA Implementation of 4-Point and 8-Point Fast 
Hadamard Transform”. International Journal of Computer Applications (0975 – 
8887) Volume 124 – No.3, August 2015. 
[6]. Vijayalakshmi Saravanan. “An optimizing pipeline stall reduction algorithm for power 
and performance on multi-core CPUs”. Human-centric Computing and Information 
Sciences. 29 January 2015. 
[7]. Miodrag Bolic, Jonathan Parri. “Accessing an FPGA-based hardware accelerator in a 
paravirtualized environment”. Hardware/Software Codesign and System Synthesis 
(CODES+ISSS), 2013 International Conference. Sept. 29 2013-Oct. 4 2013. pp: 1-9. 
ABSTRACT 
A METHOD TO INCREASE THE HADAMARD TRANSFORM SPEED 
WITH PIPELINE ARCHITECTURE 
 For specialized microprocessor systems, the problem of compromise 
between processing speed and its reliability always has been posed to the designers. 
Based on the idea of minimizing the structure of the Hadamard encoder in the CPU 
core [1], a hardening of a Hadamard algorithm by FPGA technology in 
combination with pipeline architecture to ensure both high speed and high 
reliability due to the simpler structure of the system is proposed in this paper. When 
comparing the 1 row × 4 column matrix structure with the 8 row × 4 column 
matrix, the complexity was reduced to approximately 8 times, but the speed of 64-bit 
data vector encoding on the minimal matrix remained unchanged. Simulation 
results on ModelSim and implementation on the Xilinx ISE Design Suite show that 
performance of the proposed approach is more superior than other approaches. 
Keywords: Specialized microprocessor systems; FPGA; Hadamard; pipeline. 
Nhận bài ngày 02 tháng 5 năm 2018 
Hoàn thiện ngày 11 tháng 6 năm 2018 
Chấp nhận đăng ngày 10 tháng 8 năm 2018 
Địa chỉ: 1 HVKTQS; 
 2 Đại học Sư phạm Kỹ thuật Nam Định. 
 * Email: phamminhtoi@gmail.com.