Suppose, we want to compute a Boolean function f, but instead of receiving the input, we only get some epsilon-faulty copies of each input bit. A typical solution in this case is to take the majority value of the faulty bits for each individual input bit and apply f on the majority values. We show that if f:{0,1}^{n} -> {0,1} and epsilon are known, the best construction function, F, is often not the trivial. In particular, in many cases the best F cannot be written as a composition of some functions with f, and in addition it is better to use a randomized F than a deterministic one. Our investigations have lead to a new result about the Static Noisy Decision tree complexity, introduced by Reischuk at. al. We fully characterize this complexity measure using a lemma that gives a necessary and sufficient condition for the value of a Boolean function to remain constant under independent random changes of its input bits. This lemma may be interesting on its own right.