Biến đổi Hadamard

Tích của một hàm logic và một ma trận Walsh chính là phổ Walsh của nó:^[1]
(1,0,1,0,0,1,1,0) * H(8) = (4,2,0,−2,0,2,0,2)

Biến đổi Walsh–Hadamard nhanh
Một cách nhanh hơn để tính phổ Walsh của (1,0,1,0,0,1,1,0).

Hàm gốc có thể được biểu diễn bởi tổng đại số các trung bình trong phổ Walsh của nó.

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 ${\displaystyle 2^{m}}$ 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 ${\displaystyle 2\times 2\times \cdots \times 2\times 2}$.^[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_m là một ma trận 2^m × 2^m, Ma trận Hadamard biến đổi 2^m số thực x_n thành 2^m số thực X_k. 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_m với m > 0 theo cách sau:

${\displaystyle H_{m}={\frac {1}{\sqrt {2}}}{\begin{pmatrix}H_{m-1}&H_{m-1}\\H_{m-1}&-H_{m-1}\end{pmatrix}}}$

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:

${\displaystyle k=\sum _{0}^{i<m}{k_{i}2^{i}}=k_{m-1}2^{m-1}+k_{m-2}2^{m-2}+\cdots +k_{1}2+k_{0}}$

và

${\displaystyle n=\sum _{0}^{i<m}{n_{i}2^{i}}=n_{m-1}2^{m-1}+n_{m-2}2^{m-2}+\cdots +n_{1}2+n_{0}}$

trong đó k_j và n_j 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: ${\displaystyle k=n=0}$. Trong trường hợp này, ta có:

${\displaystyle \left(H_{m}\right)_{k,n}={\frac {1}{2^{\frac {m}{2}}}}(-1)^{\sum _{j}k_{j}n_{j}}}$

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 ${\displaystyle \scriptstyle 2\,\times \,2\,\times \,\cdots \,\times \,2\,\times \,2}$, đượ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_j và k_j.

Sau đây là một số ví dụ về ma trận Hadamard:

${\displaystyle {\begin{aligned}H_{0}=&+1\\H_{1}={\frac {1}{\sqrt {2}}}&{\begin{pmatrix}{\begin{array}{rr}1&1\\1&-1\end{array}}\end{pmatrix}}\end{aligned}}}$

(H₁ trong trường hợp trên chính là phép biến đổi Fourier rời rạc hai chiều. Nó cũng có thể được coi là phép Biến đổi Fourier trên nhóm cộng hai phần tử Z/(2).)

${\displaystyle {\begin{aligned}H_{2}={\frac {1}{2}}&{\begin{pmatrix}{\begin{array}{rrrr}1&1&1&1\\1&-1&1&-1\\1&1&-1&-1\\1&-1&-1&1\end{array}}\end{pmatrix}}\\H_{3}={\frac {1}{2^{\frac {3}{2}}}}&{\begin{pmatrix}{\begin{array}{rrrrrrrr}1&1&1&1&1&1&1&1\\1&-1&1&-1&1&-1&1&-1\\1&1&-1&-1&1&1&-1&-1\\1&-1&-1&1&1&-1&-1&1\\1&1&1&1&-1&-1&-1&-1\\1&-1&1&-1&-1&1&-1&1\\1&1&-1&-1&-1&-1&1&1\\1&-1&-1&1&-1&1&1&-1\end{array}}\end{pmatrix}}\\(H_{n})_{i,j}={\frac {1}{2^{\frac {n}{2}}}}&(-1)^{i\cdot j}\end{aligned}}}$

trong đó ${\displaystyle i\cdot j}$ 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 ${\displaystyle \scriptstyle n\geq 2}$, ta có: ${\displaystyle \scriptstyle ({H_{n}})_{3,2}\;=\;(-1)^{3\cdot 2}\;=\;(-1)^{(1,1)\cdot (1,0)}\;=\;(-1)^{1+0}\;=\;(-1)^{1}\;=\;-1}$, đú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 ${\displaystyle \scriptstyle ({H_{n}})_{0,0}}$.

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 ${\displaystyle |0\rangle }$ và ${\displaystyle |1\rangle }$ 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 ${\displaystyle |0\rangle }$ và ${\displaystyle |1\rangle }$ bằng nhau. Pha thường được chọn sao cho ta có

${\displaystyle H={\frac {|0\rangle +|1\rangle }{\sqrt {2}}}\langle 0|+{\frac {|0\rangle -|1\rangle }{\sqrt {2}}}\langle 1|}$

trong ký pháp Dirac. Điều này tương tự như phép biến đổi ma trận

${\displaystyle H_{1}={\frac {1}{\sqrt {2}}}{\begin{pmatrix}1&1\\1&-1\end{pmatrix}}}$

với cơ sở ${\displaystyle |0\rangle ,|1\rangle }$.

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à ${\displaystyle |0\rangle }$ 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ở ${\displaystyle |0\rangle ,|1\rangle }$ vơi hệ số bằng nhau.

Hoạt động của cổng Hadamard

${\displaystyle H(|1\rangle )={\frac {1}{\sqrt {2}}}|0\rangle -{\frac {1}{\sqrt {2}}}|1\rangle }$

${\displaystyle H(|0\rangle )={\frac {1}{\sqrt {2}}}|0\rangle +{\frac {1}{\sqrt {2}}}|1\rangle }$

${\displaystyle H\left({\frac {1}{\sqrt {2}}}|0\rangle -{\frac {1}{\sqrt {2}}}|1\rangle \right)={\frac {1}{2}}(|0\rangle +|1\rangle )-{\frac {1}{2}}(|0\rangle -|1\rangle )=|1\rangle }$

${\displaystyle H\left({\frac {1}{\sqrt {2}}}|0\rangle +{\frac {1}{\sqrt {2}}}|1\rangle \right)={\frac {1}{\sqrt {2}}}{\frac {1}{\sqrt {2}}}(|0\rangle +|1\rangle )+{\frac {1}{\sqrt {2}}}{\frac {1}{\sqrt {2}}}\left(|0\rangle -|1\rangle \right)=|0\rangle }$

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^m) 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ử.

Tham khảo

1. So sánh Figure 1 trong Walsh Spectrum Computations Using Cayley Graphs
2. Theo H.O. Kunz, trong "On the Equivalence Between One-Dimensional Discrete Walsh-Hadamard and Multidimensional Discrete Fourier Transforms," IEEE Transactions on Computers, vol. 28, no. 3, pp. 267–268 (1979).

Liên kết ngoài

• Terry Ritter, Walsh-Hadamard Transforms: A Literature Survey (Aug. 1996)
• 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.
• Pan, Jeng-shyang Data Encryption Method Using Discrete Fractional Hadamard Transformation (ngày 28 tháng 5 năm 2009)
• Godfrey Beddard, Pump-probe Spectroscopy using Hadamard Transforms Lưu trữ 2014-10-18 tại Wayback Machine (Jan. 2011)