Biến đổi Hadamard

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm
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 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 2\times2\times\cdots\times2\times2.[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 một nhà toán học người Pháp Jacques Hadamard, Một nhà toán học người Mỹ gốc Đức Hans Rademacher, và một nhà toán học người Mỹ Joseph Leonard Walsh.

Định nghĩa[sửa | sửa mã nguồn]

Biến đổi Hadamard Hm là một ma trận 2m × 2m, Ma trận Hadamard biến đổi 2m số thực xn thành 2m số thực Xk. 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 nk.

Đố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 (H0) một giá trị khởi tạo H0 = 1, từ đó tính tiếp Hm với m > 0 theo cách sau:

H_m = \frac{1}{\sqrt2} \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ứ (kn) của nó theo cách sau:

k = \sum^{i<m}_{0} {k_i 2^i} = k_{m-1} 2^{m-1} + k_{m-2} 2^{m-2} + \cdots + k_1 2 + k_0

n = \sum^{i<m}_{0} {n_i 2^i} = n_{m-1} 2^{m-1} + n_{m-2} 2^{m-2} + \cdots + n_1 2 + n_0

trong đó kjnj là những chữ số trong biểu diễn nhị phân (0 hoặc 1) của kn. 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: k = n = 0. Trong trường hợp này, ta có:

\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 \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 njkj.

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

\begin{align}
  H_0 = &+1\\
  H_1 = \frac{1}{\sqrt2}
   &\begin{pmatrix}\begin{array}{rr}
    1 & 1\\
    1 & -1
   \end{array}\end{pmatrix}
\end{align}

(H1 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).)

\begin{align}
  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{align}

trong đó  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 \scriptstyle n \geq 2 , ta có: \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 \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ử[sửa | sửa mã nguồn]

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

H=\frac{|0\rangle+|1\rangle}{\sqrt{2}}\langle0|+\frac{|0\rangle-|1\rangle}{\sqrt{2}}\langle1|

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

H_1=\frac{1}{\sqrt{2}}\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}

với cơ sở |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à |0 \rangle thành một trạng thái chồng chập của tất cả 2n trạng thái trực giao của các cơ sở  |0 \rangle, |1 \rangle vơi hệ số bằng nhau.

Hoạt động của cổng Hadamard[sửa | sửa mã nguồn]

H(|1\rangle) = \frac{1}{\sqrt{2}}|0\rangle-\frac{1}{\sqrt{2}}|1\rangle
H(|0\rangle) = \frac{1}{\sqrt{2}}|0\rangle+\frac{1}{\sqrt{2}}|1\rangle
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
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, ko 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[sửa | sửa mã nguồn]

Phép biển đổi Hadamard có thể được thực hiện trong n log n phép toán (n = 2m) bằng cách sử dụng thuật toán biến đổi Hadamard nhanh.

Những ứng dụng khác[sửa | sửa mã nguồn]

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[sửa | sửa mã nguồn]

Tài liệu tham khảo[sửa | sửa mã nguồn]

  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).