Biến_đổi Hadamard_Biến_đổi Hadamard_Hay còn được gọi là Biến_đổi Walsh_Hadamard_Biến_đổi Hadamard_Rademacher_Walsh_Biến_đổi Walsh hay Biến_đổi Walsh_Fourier là một kiểu đặc_biệt của Biến_đổi Fourier_Biến_đổi này thực_hiện một_phép tính trực_giao đối_xứng luỹ_thừa tuyến_tính trên formula _ 1 số_thực có_thể áp_dụng trên cả số_phức mặc_dù ma_trận Hadamard là thuần số_thực Biến_đổi Hadamard được xây_dựng trên phép Biến_đổi Fourier rời_rạc DFT 2 chiều và tương_đương với một biến_đổi Fourier rời_rạc nhiều chiều với kích_thước formula _ 2 Nó phân_tích một vector đầu vào bất_kì thành một dạng chồng chập của các hàm Walsh_Biến_đổi này được đặt tên theo tên của nhà toán_học người Pháp Jacques_Hadamard nhà toán_học người Mỹ gốc Đức Hans_Rademacher và nhà toán_học người Mỹ Joseph_Leonard_Walsh_Định nghĩa Biến_đổi Hadamard_H là một ma_trận 2 2 Ma_trận Hadamard biến_đổi 2 số_thực x thành 2 số_thực X Biến_đổi Hadamard có_thể biểu_diễn bằng hai cách đệ quy hoặc biểu_diễn nhị phân của n và k Đối_với cách biểu_diễn bằng đệ quy ta gán cho_phép biến_đổi Hadamard cỡ 1 1 H một giá_trị khởi tạo H 1 từ đó tính tiếp H với m 0 theo cách sau trong đó 1 2 là giá_trị chuẩn_hoá trong nhiều trường_hợp có_thể lược bỏ Do_đó ngoài những giá_trị chuẩn_hoá toàn_bộ ma_trận Hadamard được lấp đầy bởi các giá_trị 1 và 1 Tương_đương với cách biểu_diễn bằng đệ quy trong cách biểu_diễn nhị phân ta biểu_diễn ma_trận Hadamard bằng các phần_tử thứ k n của nó theo cách sau và trong đó k và n là những chữ_số trong biểu_diễn nhị phân 0 hoặc 1 của k và n Một điều cần lưu_ý rằng với phần_tử ở góc trên cùng bên trái chúng_ta gán formula _ 6 Trong trường_hợp này ta có Chúng_ta có_thể coi đây là một_phép biến_đổi Fourier rời_rạc nhiều chiều kích_thước formula _ 8 được chuẩn_hoá thành_đồng nhất nếu đầu_ra và đầu vào được coi như mảng nhiều chiều với các vị_trí được đánh_dấu bởi n và k Sau đây là một_số ví_dụ về ma_trận Hadamard trong đó formula _ 11 là tích chấm tích vô hướng của các biểu_diễn nhị phân của i và j Ví_dụ nếu formula _ 12 ta có formula _ 13 đúng với những gì ở trên bỏ_qua hằng_số toàn_cục Chú_ý rằng hàng_đầu và cột đầu của ma_trận được ký_hiệu bởi formula _ 14 Các hàng trong ma_trận Hadamard chính là những hàm Walsh_Ứng dụng trong điện_toán lượng_tử Trong lĩnh_vực xử_lý thông_tin lượng_tử phép biến_đổi Hadamard thường được gọi là cổng Hadamard là phép quay một qubit ánh xạ trạng_thái qubit cơ_bản formula _ 15 và formula _ 16 thành hai trạng_thái chồng chập với hệ_số của các trạng_thái cơ_bản formula _ 15 và formula _ 16 bằng nhau Pha thường được chọn sao cho ta có trong ký pháp Dirac_Điều này tương_tự như phép biến_đổi ma_trận với cơ_sở formula _ 21 Rất nhiều thuật_toán lượng_tử sử_dụng biến_đổi Hadamard trong bước khởi tạo nếu nó cần ánh xạ n qubits với giá_trị ban_đầu là formula _ 22 thành một trạng_thái chồng chập của tất_cả 2 trạng_thái trực_giao của các cơ_sở formula _ 23 vơi hệ_số bằng nhau Hoạt_động của cổng Hadamard_Khi áp_dụng cổng Hadamard một qubit đang ở trạng_thái 0 hoặc 1 sẽ bị chuyển về một trạng_thái chồng chập mà khi đo_đạc sẽ bị chuyển về một trong hai trạng_thái 0 hoặc 1 với xác_suất của hai trạng_thái bằng nhau chúng_ta có_thể dễ_dàng nhận thấy ở hai phép_tính đầu_tiên Trạng_thái này giống như ta gieo một đồng xu hai mặt chuẩn Tuy_nhiên nếu cổng Hadamard được áp_dụng thành_công 2 lần 2 lần áp_dụng đều có hiệu_lực không gặp trục_trặc trong kĩ_thuật thì trạng_thái cuối_cùng luôn_luôn giống trạng_thái khởi_điểm Việc này có_thể tưởng_tượng giống như việc lấy một đồng xu đang ở mặt ngửa lật hai lần và nó luôn quay về trạng_thái ngửa sau lần lật thứ hai Độ phức_tạp tính_toán Phép biển đổi Hadamard có_thể được thực_hiện trong n log n phép_toán n 2 bằng cách sử_dụng thuật_toán biến_đổi Hadamard nhanh Những ứng_dụng khác Biến_đổi Hadamard cũng được dùng trong mã_hoá dữ_liệu cũng như nhiều thuật_toán xử_lý tín_hiệu và nén dữ_liệu như JPEG XR và H 264 MPEG 4 AVC Trong các ứng_dụng liên_quan đến nén video nó được dùng như một_cách để tính tổng_lượng sai_lệch chuyển_đổi tuyệt_đối SATD Sum of Absolute_Transformed_Differences_Biến_đổi Hadamard cũng là một phần trọng_yếu trong thuật_toán Grover và thuật_toán Shor trong điện_toán lượng_tử Liên_kết ngoài BULLET Terry_Ritter_Walsh_Hadamard Transforms_A_Literature_Survey Aug 1996 BULLET A N Akansu and R Poluri_Walsh_Like_Nonlinear Phase_Orthogonal_Codes for Direct_Sequence_CDMA_Communications IEEE Trans on Signal_Processing vol 55 pp 3800 3806 July 2007 BULLET Pan_Jeng shyang Data_Encryption_Method_Using Discrete_Fractional_Hadamard_Transformation ngày 28 tháng 5 năm 2009 BULLET Godfrey_Beddard_Pump probe Spectroscopy using Hadamard_Transforms_Jan 2011
Biến_đổi Hadamard