Сбалансированная булева функция
В булевой алгебре, сбалансированной булевой функцией называется такая булева функция, которая на всей области определения функции принимает значение 0 ровно столько же раз как и значение 1. Другими словами, в таблице истинности сбалансированной булевой функции количество входных комбинаций, при которых функция принимает значение 0, совпадает с количеством комбинаций, при которых функция принимает значение 1. Сбалансированные функции так же называются уравновешенными или равновероятными, поскольку при равновероятных случайных значениях на входе или при переборе всех комбинаций по таблице истинности вероятность получения на выходе значения 1 равна 1/2.
Простейшим примером сбалансированной булевой функции является функция, принимающая значение 1, если на входе четное число, и 0, если на входе нечетное число (или наоборот).
Использование
Сбалансированные булевы функции в основном используются в криптографии.
См. также
Напишите отзыв о статье "Сбалансированная булева функция"
Ссылки
- [portal.acm.org/citation.cfm?id=1060627 Balanced boolean functions that can be evaluated so that every input bit is unlikely to be read], Annual ACM Symposium on Theory of Computing
|
Это заготовка статьи по криптографии. Вы можете помочь проекту, дополнив её. |
Отрывок, характеризующий Сбалансированная булева функция
Алпатыч более поспешным шагом, чем он ходил обыкновенно, вошел во двор и прямо пошел под сарай к своим лошадям и повозке. Кучер спал; он разбудил его, велел закладывать и вошел в сени. В хозяйской горнице слышался детский плач, надрывающиеся рыдания женщины и гневный, хриплый крик Ферапонтова. Кухарка, как испуганная курица, встрепыхалась в сенях, как только вошел Алпатыч.– До смерти убил – хозяйку бил!.. Так бил, так волочил!..
– За что? – спросил Алпатыч.
– Ехать просилась. Дело женское! Увези ты, говорит, меня, не погуби ты меня с малыми детьми; народ, говорит, весь уехал, что, говорит, мы то? Как зачал бить. Так бил, так волочил!
Алпатыч как бы одобрительно кивнул головой на эти слова и, не желая более ничего знать, подошел к противоположной – хозяйской двери горницы, в которой оставались его покупки.
– Злодей ты, губитель, – прокричала в это время худая, бледная женщина с ребенком на руках и с сорванным с головы платком, вырываясь из дверей и сбегая по лестнице на двор. Ферапонтов вышел за ней и, увидав Алпатыча, оправил жилет, волосы, зевнул и вошел в горницу за Алпатычем.
– Аль уж ехать хочешь? – спросил он.
Не отвечая на вопрос и не оглядываясь на хозяина, перебирая свои покупки, Алпатыч спросил, сколько за постой следовало хозяину.
