Коефіцієнт Уолша булевої функції — це величина , де . Коефіцієнти Уолша є спектральною характеристикою булевої функції, тобто є аналогом коефіцієнтів Фур'є.
Обчислення коефіцієнтів Уолша
Коефіцієнти Уолша можуть бути обчислені за дій. Для цього потрібно на початку проініціалізувати масив : . Після чого для кожної координати : і для кожної пари точок і , що відрізняються за -тій координаті, потрібно замінити значення і на і (вважаємо, що у -тий біт скинуто, а у встановлений). Остаточний стан масиву і буде коефіцієнтами Уолша.
Властивості коефіцієнтів Уолша
- Формула звернення: .
- Рівність Парсеваля: .
- Формула для автокореляційних коефіцієнтів : .
- Вираз коефіцієнтів Уолша через автокореляційні коефіцієнти: .
- Формула для нелінійності булевої функції: .
- Теорема Титсворта: . Разом з рівністю Парсеваля ця тотожність є необхідною і достатньою умовою того, що набір коефіцієта Уолша задає якусь бульову функцію.
- Тотожність Саркара: , де означає домінування, тобто те, що всі одиничні біти містяться серед одиничних бітів , означає вагу функції (кількість наборів, на яких функція дорівнює 1), означає функцію отриману підстановкою замість нуля для всіх при яких .
Див. також
Це незавершена стаття з математики. Ви можете проєкту, виправивши або дописавши її. |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Koeficiyent Uolsha W f u displaystyle W f u bulevoyi funkciyi f displaystyle f ce velichina x F 2 n 1 f x u x displaystyle sum x in F 2 n 1 f x langle u x rangle de a b i 1 n a i b i displaystyle langle a b rangle sum i 1 n a i b i Koeficiyenti Uolsha ye spektralnoyu harakteristikoyu bulevoyi funkciyi tobto ye analogom koeficiyentiv Fur ye Obchislennya koeficiyentiv UolshaKoeficiyenti Uolsha mozhut buti obchisleni za O n 2 n displaystyle O n2 n dij Dlya cogo potribno na pochatku proinicializuvati masiv a displaystyle a a x 1 f x displaystyle a x 1 f x Pislya chogo dlya kozhnoyi koordinati a displaystyle a a x 1 f x displaystyle a x 1 f x i dlya kozhnoyi pari tochok x displaystyle x i y displaystyle y sho vidriznyayutsya za i displaystyle i tij koordinati potribno zaminiti znachennya a x displaystyle a x i a y displaystyle a y na a x a y displaystyle a x a y i a x a y displaystyle a x a y vvazhayemo sho u x displaystyle x i displaystyle i tij bit skinuto a u y displaystyle y vstanovlenij Ostatochnij stan masivu a displaystyle a i bude koeficiyentami Uolsha Vlastivosti koeficiyentiv UolshaFormula zvernennya 1 f x 2 n u F 2 n W f u 1 lt u x gt displaystyle 1 f x 2 n sum u in F 2 n W f u 1 lt u x gt Rivnist Parsevalya u F 2 n W f 2 u 2 2 n displaystyle sum u in F 2 n W f 2 u 2 2n Formula dlya avtokorelyacijnih koeficiyentiv D f u x F 2 n 1 f x f x u displaystyle left Delta f u sum x in F 2 n 1 f x f x u right D f u 2 n 2 1 n x F 2 n 2 lt x u gt W f 2 x displaystyle Delta f u 2 n 2 1 n sum x in F 2 n 2 lt x u gt W f 2 x Viraz koeficiyentiv Uolsha cherez avtokorelyacijni koeficiyenti W f 2 x u F 2 n 1 lt x u gt D f u displaystyle W f 2 x sum u in F 2 n 1 lt x u gt Delta f u Formula dlya nelinijnosti bulevoyi funkciyi n l f 2 n 1 1 2 max u F 2 n W f u displaystyle nl f 2 n 1 frac 1 2 max u in F 2 n W f u Teorema Titsvorta u F 2 n W f u W f u s 0 displaystyle sum u in F 2 n W f u W f u s 0 Razom z rivnistyu Parsevalya cya totozhnist ye neobhidnoyu i dostatnoyu umovoyu togo sho nabir koeficiyeta Uolsha zadaye yakus bulovu funkciyu Totozhnist Sarkara u F 2 n u w W f u 2 n 2 w 1 w t f w displaystyle sum u in F 2 n u in w W f u 2 n 2 w 1 wt f w de u w displaystyle u in w oznachaye dominuvannya tobto te sho vsi odinichni biti u displaystyle u mistyatsya sered odinichnih bitiv w displaystyle w w t f displaystyle wt f oznachaye vagu funkciyi kilkist naboriv na yakih funkciya dorivnyuye 1 f w displaystyle f w oznachaye funkciyu otrimanu pidstanovkoyu zamist x i displaystyle x i nulya dlya vsih i displaystyle i pri yakih w i 1 displaystyle w i 1 Div takozhFunkciya Uolsha Ce nezavershena stattya z matematiki Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi