沃爾什變換

一、沃爾什變換公式

沃爾什變換（Walsh Transform），又稱Walsh-Hadamard變換，它是一種不帶權的正交變換，是傅里葉變換的一種實現方式。

其變換公式如下：

W(u,v) = (-1)^{f(u,v)} \prod_{i=0}^{n-1}w_i(u_i,v_i)

其中：

u,v為整數，0≤u,v≤n-1
f(u,v)為u、v的二進制位按位異或的結果
w_i是Walsh函數，計算方式為：

w_0(x,y) = 1, x,y∈{0,1}
w_i(x,y) = w_{i-1}(x,y)w_{i-1}(x,y⊕2^{i-1}), i≥1

其中 ⊕ 表示按位異或操作。

二、沃爾什變換怎麼求

在計算機中，沃爾什變換可以用遞歸方式實現。

以計算2次沃爾什變換為例：

//計算變換矩陣
int w[4][4];
int WalshMatrix(int x, int y, int n)
{
    if (n == 1)
    {
        w[x][y] = 1;
        return 1;
    }
    int t = n / 2;
    WalshMatrix(x, y, t);
    WalshMatrix(x + t, y, t);
    WalshMatrix(x, y + t, t);
    WalshMatrix(x + t, y + t, t);

     //遞歸計算變換
     for (int i = 0; i < t; i++)
     {
        for (int j = 0; j < t; j++)
        {
            int a = w[x + i][y + j];
            int b = w[x + i][y + j + t];
            int c = w[x + i + t][y + j];
            int d = w[x + i + t][y + j + t];
            w[x + i][y + j] = a + b + c - d;
            w[x + i][y + j + t] = a - b + c + d;
            w[x + i + t][y + j] = a + b - c - d;
            w[x + i + t][y + j + t] = a - b - c + d;
         }
     }
}

//調用接口
WalshMatrix(0, 0, 4);

其中，變換矩陣存放在w數組中。

三、沃爾什變換矩陣

沃爾什變換矩陣是一個n×n的矩陣。在上一節中，我們已經介紹了如何計算沃爾什變換矩陣。

例如，當n=4時，沃爾什變換矩陣如下：

一個大小為n的Walsh矩陣可以通過將一個大小為2的Walsh矩陣的每個元素除以2，然後將四個2×2矩陣插入到新矩陣的相應位置來生成。當n是2的冪時，可以通過運行時間為O(n log n)的遞歸算法來計算Walsh矩陣。

四、沃爾什變換可分離

沃爾什變換具有可分離性，即一個n維向量的Walsh變換可以被分解成一維向量的Walsh變換的張量積。

例如，假設我們有一個4×4的Walsh矩陣A，行向量V和列向量U，其中V和U的元素都是±1。因此，如果Y是向量V與U的張量積，那麼Y的Walsh變換是矩陣乘積A * V * U’。

五、沃爾什變換核

沃爾什變換核是一個n×n的01矩陣。當n為奇數時，沃爾什變換核的第一行和第一列全為1，其他位置值為0和1交替。當n為偶數時，沃爾什變換核可以通過將大小為n/2的沃爾什變換核縮放2倍並插入到大小為n的核的對應位置來構造。

例如，當n=4時，沃爾什變換矩陣如下：

對應的核為：

六、沃爾什變換核矩陣怎麼算

可以通過下面的遞歸算法計算沃爾什變換核矩陣：

void WalshCore(int core[][N], int n)
{
    if (n == 1)
    {
        core[0][0] = 1;
        return;
    }
    int t = n / 2;
    WalshCore(core, t);
    for (int i = 0; i < t; i++)
    {
        for (int j = 0; j < t; j++)
        {
            core[i][j + t] = core[i + t][j] = core[i + t][j + t] = -core[i][j];
        }
    }
}

其中，核矩陣存放在core數組中。

七、沃爾什變換係數

沃爾什變換係數是一個大小為n的向量，其中第i個分量為沃爾什函數wi的第i個輸入和第n個輸入的差的倒數。

例如，當n=4時，沃爾什變換係數是：

1 1/3 1/3 1/3

八、沃爾什變換核矩陣怎麼算

可以通過下面的遞歸算法計算沃爾什變換的係數：

void WalshCoeff(double coeff[], int n)
{
    if (n == 1)
    {
        coeff[0] = 1;
        return;
    }
    int t = n / 2;
    WalshCoeff(coeff, t);
    for (int i = 0; i < t; i++)
    {
        coeff[i + t] = coeff[i] / -2;
    }
}

其中，係數存放在coeff數組中。

九、沃爾什變換計算題

下面是一個沃爾什變換的計算題：

設f(x)為長度為2^n的01數列，定義g(x)為：g(x) = Sum(f(y) * (-1)^(x⊕y),y∈[0,2^n-1])。請計算g的沃爾什變換。

通過分析題目中的g函數，可以發現它是f函數的沃爾什變換的直接表達式。因此，問題可以轉化為計算f的沃爾什變換，然後用係數對其進行加權求和得到g的沃爾什變換。

沃爾什變換的計算方法已經在前面的章節中介紹了，下面給出計算g的代碼示例：

const int N = 1 <> 1;
    Solve(l, mid), Solve(mid + 1, r);
    memcpy(b, a + l, (r - l + 1) * sizeof(int));
    int p = mid - l + 1;
    for (int i = 0; i < p; i++)
        for (int j = 0; j < (1 << ((int)(log2(r - l + 1) - .5) + 1)); j += 2 * p)
        {
            int x = b[i + j], y = b[i + j + p];
            b[i + j] = x + y, b[i + j + p] = x - y;
        }
    memcpy(c + l, b, (r - l + 1) * sizeof(double));
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < (1 << n); ++i)
        scanf("%d", &a[i]);
    Solve(0, (1 << n) - 1);
    WalshCoeff(c, (1 << n));      //計算Walsh變換係數
    for (int i = 0; i < (1 << n); i++)
        printf("%lf\n", c[i]);
    return 0;
}

十、沃爾什變換例題

下面是一些沃爾什變換的例題：

例題1：POJ 2752 Shuffle’m Up

題目描述：

給你一個長度為2^n的數列a，這個數列的前一半是a[0], …,a[2^(n-1)-1]，後一半是a[2^(n-1)], …, a[2^n-1]。並且，對於i∈[0,2^(n-1)-1]，有f(i)=a[2i]和f(i+2^(n-1))=a[2i+1]；對於i∈[2^(n-1),2^n-1]，有f(i)=a[(i-2^n/2)*2+1]和f(i-2^(n-1))=a[(i-2^n/2)*2]。問最後的數列是什麼。

輸入格式：

第一行一個整數n。接下來的一行包含2^n個整數，表示數列a。

輸出格式：

輸出一個字符串，表示最後的數列。

解題思路：

參考洗牌算法的思路，將序列分成兩部分，然後遞歸地執行沃爾什變換和乘法運算，最後得到新的序列。

代碼如下：

int n;

int a[MAXN];
void shuffle(int l, int r)
{
 if (r - l == 1)
 return;
 int mid = (l + r + 1) >> 1;
 for (int i = 0; i <= mid - l - 1; i++)
 {
 swap(a[l + i], a[mid + i]);
 }
 shuffle(l, mid);
 shuffle(mid, r);
 for (int i = l; i < r; i += 2)
 {
 int x = a[i], y = a[i + 1];
 a[i] = (x + y) / 2, a[i + 1] = (x - y) / 2;
 }
}
int main()
{
 scanf("%d", &n);
 int len = (1 << n);
 for (int i = 0; i < len; i++)
 scanf("%d", &a[i]);
 shuffle(0, len);
 for (int i = 0; i < len; i++)
 putchar(a[i] + 'A
原創文章，作者：小藍，如若轉載，請註明出處：https://www.506064.com/zh-hant/n/257635.html