Synthesis of easily testable logic networks under arbitrary stuck-at faults at inputs and outputs of gates | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2019. № 43. DOI: 10.17223/20710410/43/6

Two binary vectors are called k-adjacent if they differ in at most k components, where k ∈ N. For α ∈ {0, 1} and s ∈ N, let α^s be the Boolean vector (α, . . . , α) with s coordinates α. For each natural k, consider the bases B(k) = = {^(xι,... ,X2k+2),X1 ...Xk+1 V Xi ...Xk+1 ,x, 0} and B'(k) = {φ(xι,... ,X2k+2), ξ(xι,. ..,x3k+2 ),η(x1,...,x4k+2),x, 0}, where ^(xι,... ,X2k+2) is an arbitrary nonself-dual Boolean function taking the value α on the vector α^2k+2 and the value α on all other vectors k-adjacent to this vector; ξ(x1, . . . , x3k+2) is an arbitrary Boolean function taking the value α on the vector α^3k+2, the value α on all other vectors k-adjacent to this vector, and the value α on all vectors k-adjacent to the vector (α^k+1,α^2k+1); η(x₁,... ,x_4k+₂) is an arbitrary Boolean function taking the value 1 on the vector α^4k+2, the value 0 on all other vectors k-adjacent to this vector, and the value α on all vectors k-adjacent to the vector (α_2k+₁,α^2k+1). Let D_k (₁)(f) (D_k (_IO)(f), D- (₁)(f), Dk {∖_θ)(f)) be the least length of a fault detection test (fault detection test, diagnostic test, diagnostic test, respectively) for irredundant logic networks consisting of logic gates in the basis B(k) (basis B(k), basis B'(k), basis B'(k), respectively), implementing given Boolean function f(x1, . . . , xn), and having at most k arbitrary stuck-at faults on inputs of gates (on inputs and/or outputs of gates, on inputs of gates, on inputs and/or outputs of gates, respectively). Let a Boolean function f(x1,.. . , xn) be called palindromic if it takes the same value on any two opposite binary n-tuples. The following facts are obtained. The quantity D_{k (I)}(f) equals 0 iff f is an identical function (i.e., f ≡ xi for some i ∈ {1, . . . , n}) and equals 2 otherwise. The quantity D_{k (IO)}(f) equals 0 iff f is an identical function, equals 1 iff f ≡ 0, equals 2 iff f is not an identical or palindromic function, equals 3 iff f is a palindromic function and f ≡ 0,1, and is undefined iff f ≡ 1. The quantity D_k (₁)(f) equals 0 iff f is an identical function and equals 2 otherwise. The quantity D' (_1o) (f) equals 0 iff f is an identical function, equals 1 iff f ≡ 0, equals 2 iff f ≡ x_i for some i ∈ {1,... ,n}, equals 3 iff f is not a self-dual function and f ≡ 0, 1, equals 4 iff f is a self-dual function and f ∈ {x₁,... ,x_n,X₁,... ,x_n}, and is undefined iff f ≡ 1. For each k ∈ N, the equality Dfc (_1o) (f) = 4 holds true under n 3, and in the case k 2, the proportion of those Boolean functions f in n variables, for which D_k (^_θ)(f) = 4, tends to 1 under n → ∞.