Nhân ma trận, DFT, và lý thuyết biểu diễn nhóm (5)

Ngô Quang Hưng | 29 tháng 09, 2008 | Bản để in Bản để in

Tiếp theo các bài trước, bài này nói về DFT trên các nhóm Abel. Ta đã biết rằng các phép biểu diễn tối giản trên một nhóm Abel bất kỳ đều là các phép biểu diễn 1 chiều. Tổng số các (isomorphism classes của) các phép biểu diễn một chiều này bằng với tổng số conjugacy classes của nhóm, nghĩa là bằng với tổng số phần tử trong nhóm vì đây là nhóm Abel.

Để cho dễ hiểu, hãy xét trường hợp đơn giản khi G = \mathbb Z_n. (Nhớ rằng mỗi nhóm Abel hữu hạn đều isomorphic với tổng trực tiếp của một mớ cyclic groups dạng \mathbb Z_m.) Trong trường hợp này, một hàm số \chi: G \to \mathbb C là một character của G nếu nó là một phép đồng cấu từ G vào \mathbb C^\times, nghĩa là nó thỏa mãn

\chi(a+b) = \chi(a) + \chi(b), \ \forall a, b \in G = \mathbb Z_n

Từ đó, dễ thấy rằng \chi(0) = 1 và \chi(1) là một nth root of unity. Các giá trị khác thỏa \chi(k) = (\chi(1))^k. Đặt \omega = e^{2\pi i/n}. Với mỗi phần tử a \in \mathbb Z_n, nếu ta đặt \chi_a(1) = \omega^a thì tập hợp n bộ \chi_a này chính là tập hợp n characters của G. Viết ra cụ thể hơn:

\chi_a = \begin{bmatrix} 1\\ \omega^a\\ \vdots \\ \omega^{(n-1)a} \end{bmatrix}, \ \ a = 0, 1, \dots, n-1

Bộ các characters này một hệ cơ sở trực chuẩn của \mathbb C^n nếu ta dùng inner-product

\langle \chi, \chi' \rangle = \frac 1 n \sum_{b \in \mathbb Z_n} \chi(b)^* \chi'(b)

Như đã nói sơ lược trong bài 2 về DFT, xét một hàm (nghĩa là vector) \mathbf f: \mathbb Z_n \to \mathbb C bất kỳ; biểu diễn \mathbf f dùng hệ cơ sở trực chuẩn trên:

\mathbf f = \hat f_0 \chi_0 + \hat f_1 \chi_1 + \dots + \hat f_{n-1} \chi_{n-1}

thì \mathbf{\hat f} = DFT^{-1}(\mathbf f). Đây chính là cái định nghĩa DFT thường thấy trong sách giáo khoa. Như vậy, DFT thường dùng trong xử lý tín hiệu số là một trường hợp đặc biệt của DFT trên nhóm \mathbb Z_n.

Trường hợp một nhóm Abel bất kỳ thì như thế nào?

Một nhóm Abel G bất kỳ đề có thể viết dưới dạng G \cong \mathbb Z_{m_1} \oplus \cdots \mathbb \oplus Z_{m_k}. Hơn nữa, nếu G \cong H_1 \oplus H_2 và \phi_1, \phi_2 là hai characters của H_1, H_2 thì hàm \chi: G \to \mathbb C định nghĩa bởi \chi(h_1,h_2) = \phi_1(h_1)\phi_2(h_2) là một character của G. Ngược lại, bất kỳ character nào của G cũng có thể viết được dưới dạng “tích” của hai characters của H_1,H_2. Tổng quát hơn, nếu G \cong \mathbb Z_{m_1} \oplus \cdots \mathbb \oplus Z_{m_k} thì mọi character của G đều là “tích” (nói đúng hơn là “tổng trực tiếp”) của các characters của \mathbb Z_{m_i}, 1\leq i \leq k.

Nhờ đó, ta có thể viết cụ thể ra bộ characters của nhóm G \cong \mathbb Z_{m_1} \oplus \cdots \mathbb \oplus Z_{m_k} như sau: mỗi character \chi_{\mathbf a} sẽ được đánh chỉ số bởi một thành viên \mathbf a \in \mathbb Z_{m_1} \times \cdots \mathbb \times Z_{m_k}. Nhớ rằng \mathbf a là một vector. Character này được định nghĩa như sau:

\chi_{\mathbf a}(\mathbf b) = \omega_{m_1}^{a_1b_1}\cdots \omega_{m_k}^{a_kb_k}

Bộ characters này là một hệ cơ sở trực chuẩn của không gian \mathbb C^{G}. Từ đó ta dễ dàng viết lại DFT của một hàm \mathbf f: G \to \mathbb C bất kỳ, cùng với DFT nghịch đảo và các đẳng thức Parseval, Plancharel.

Chủ đề: Thuật Toán |

6 lời bình cho bài “Nhân ma trận, DFT, và lý thuyết biểu diễn nhóm (5)”

  1. 1
    29 tháng 09, 2008, vào lúc 12:53 pm Thang viết:

    Cam on anh Hung vi bai viet. Lau la’m moi’ thay’ anh co’ bai` moi’. Bai` vie’t cua anh giup’ em bo sung rat nhieu` vitamin maths :-)
    Chuc anh luon vui!

  2. 2
    04 tháng 10, 2008, vào lúc 7:59 pm Ngọc Trung viết:

    Chào anh Hưng!
    Anh có thể giúp em tìm hiểu về thuật toán nhân hai số lớn có sử dụng FFT của Fourier được không ạ?
    Em đang rất cần nó để sử dụng trong luận văn tốt nghiệp.
    Cám ơn anh rất nhiều!

    Ngọc Trung

  3. 3
    05 tháng 10, 2008, vào lúc 2:18 am Ngô Quang Hưng viết:

    hello Trung,

    Ở đây có mô tả làm thế nào để nhân hai số lớn dùng FFT. Không phải là thuật toán tốt nhất về mặt lý thuyết, nhưng ý tưởng thì đủ. Wikipedia cũng có một entry đầy đủ về thuật toán Schonhage-Strassen

    http://en.wikipedia.org/wiki/Sch%C3%B6nhage-Strassen_algorithm

  4. 4
    06 tháng 10, 2008, vào lúc 7:42 pm Johan Tran viết:

    Em hiện là sinh viên năm 2 ngành( như một entry của anh trên blog này, em cũng không thể gọi chính xác tên ngành học của mình). Chương trình học của trường em cũng tương tự như những ngành Tin ở các trường đại học khác. Tuy nhiên em rất mơ hồ về chương trình của ngành KHMT, anh có thể giúp em hiểu hơn về những cái cần đi sâu trong ngành này được không ạ. Xin cảm ơn anh.

  5. 5
    07 tháng 10, 2008, vào lúc 8:50 am Ngọc Trung viết:

    Cám ơn anh đã chỉ giúp em!
    Em có đọc nhưng không hiểu rõ lắm! Phiền anh lấy cho em một ví dụ được không ạ?
    Input: 2 số thập phân a, b
    Output: c=a*b

    Anh làm chi tiết giúp em với nhé!

  6. 6
    22 tháng 10, 2008, vào lúc 6:53 am Ngô Quang Hưng viết:

    Ngọc Trung,

    Hiện nay tôi không có thời gian viết rõ ra, hẹn dịp khác nhé.

    Johan Tran,

    Xin xem chuỗi bài này.

Ghi lời bình của bạn: