Notation

這些數字如何表示布爾函式?

  • October 18, 2013

在 Wikipedia 文章“ Bent functions ”中,有一些數字代表了這些 Bent 函式:

圖 1 顯示數字

圖 2 顯示數字

這些數字如何表示布爾函式?

較大圖像的圖像描述頁面很好地描述了它。

具體來說,圖頂部的行:

0001 0001 0001 1110

顯示 4 元布爾函式 $ f(x_1, x_2, x_3, x_4) = x_1 x_2 + x_3 x_4 $ 以圖形的形式。具體來說,將每個可能的輸入解釋為 4 位二進制數(例如 $ (0, 1, 0, 1) \mapsto 0101_2 = 5 $ ),如果函式的輸出為 1,則直線上的相應正方形(從左側的正方形 0 開始,一直到右側的正方形 15)為紅色,如果為 0,則為白色。

下面的方塊顯示了16 階Walsh 矩陣,其行對應於 16 個線性4 元布爾函式(又名Walsh 函式),使用與頂行相同的表示。標有點的方塊是頂部顯示的非線性函式與行所描述的線性函式不同的地方,右側的數字計算了行上此類點的數量。

下面的第二個正方形是沃爾什矩陣的補碼,顯示了 16 個非線性仿射四元布爾函式(即除了添加一個非零常數之外的線性函式,對於布爾函式只能是 1 )。點和數字的含義與以前相同。

查看右邊的數字,可以看到給定函式的輸入數量 $ f $ 不同於每個仿射 4 元布爾函式是 6 或 10 = 16 - 6,證明 $ f $ 與每個仿射 4-are 布爾函式等距(在模 16 的絕對差數的意義上),因此是彎曲函式.

另一幅圖像僅包含四個較小但在其他方面相似的子圖,表明漢明權重為 1 的四個 2 元布爾函式中的每一個(即僅為一組輸入產生輸出 1)也是彎曲函式。

引用自:https://crypto.stackexchange.com/questions/11137