Ортогональные системы булевых функций на выходе фильтрующего генератора

Промышленные АСУ и контроллеры. 2014. № 1. С. 31–36.

Rozhkov M.

The paper deals with the construction of orthogonal systems of Boolean functions (f(x),f(d(x)),...,f(dn-1(x)), xÎ(F2)n generated by conversion d=dL, carried out shift register of great length n with the function of feedback L and a nonlinear function f removal from a small number of arguments k (k<<n). The orthogonality of the specified system functions is equivalent to the mapping Вf,L, defined by a set of coordinate functions (f(x),f(d(x)),...,f(dn-1(x)), is bijective. The new method is proposed, which reduces the original problem to the verification of orthogonal systems of Boolean functions with shift registers limited length n<n0, which allows efficient use of its computing solutions. This method, in particular, allowed to build new infinite classes of bijective mappings Вf,L for the case of nonlinear function f, depending on four variables f=f(x1,x2,x3,x4). Earlier, similar results were known for the case when the function f depends on three arguments f=f(x1,x2,x3). The results can be useful for construction and proof of the statistical properties of the generating random sequences on the basis of filter generators. The particular practical importance has the choice of pairs (f,L), in which simultaneously the mapping Bf,L is  bijective and period of dL is maximal.

Keywords: ортогональные системы функций, регистр сдвига, orthogonal system of Boolean functions, feedback shift register, filter generator, restrictive multitude, фильтрующий генератор, понижающие множества