Diagnostic tests for discrete functions defined on rings

G. V. Antyufeev

Diskretnaya Matematika, Tome 33 (2021) no. 1, pp. 3-11

Résumé

The paper is concerned with sources of faults associated with commutative principal ideal rings. Tables of faults of such sources are known to correspond to Cayley multiplication tables in rings, whose elements are replaced by the values of a Boolean function of these elements. For such rings, the concepts of a diagnostic test and the Shannon function for the length of a diagnostic test are introduced in a natural way. It is shown that if $A$ is a principal ideal ring with only one prime ideal $p \neq A$, and if $p^n = 0$ for some $n \in \mathbb {N}$, then, for this ring, the Shannon length function of a diagnostic test has the form $L^{{\rm diagn}}(A,n) = \Theta(n).$ We also define an easily testable functions, i.e., a function with respect to which the order of growth of the length of a diagnostic test with respect to this function is equal to the logarithm of the number of pairwise distinct columns of the table of faults. A link between easily testable functions and column separation of tables of faults for two concrete sources of faults is established.

Détail

Keywords: source of faults, shift, test, the Shannon function, principal ideal ring.