The ant colony algorithm for test syntesis for digital devices

Описывается эволюционный алгоритм синтеза тестов для цифровых устройств (ЦУ), основанный на исполь-зовании алгоритма муравьиной колонии. Предлагаемый алгоритм ориентирован на диагностирование таких неисправностей ЦУ, которые обычно трудно обнаруживать и диагностировать другими широко практикуе-мыми методами. includes methods that are relatively easy to implement, but the tests they synthesize are detecting significant part of all possible faults. An example is the pseudo-random test synthesis method. The second group includes methods that are more laborious in implementation, but are capable of detecting faults that are difficult to diagnose. These include methods, for example, of the distin-guishing function and Boolean derivatives. The proposed method belongs to this group. Nowadays, so-called evolutionary algorithms are widespread. These algorithms are very effective for many practical applications. The article proposes a method for test synthesis based on the ideas of evolutionary ant colony algorithms. We briefly describe the problem under study. Let DD be determined in the form of a structural scheme and the set F of its possible faults. For simplicity, it is assumed that the DD is a combinational device, and the set F consists of single constant faults. We consider the problem of test synthesis (PTS) for DD, detecting out of faults from the set F. In the PTS the mathematical model of the DD is the undirected graph G = (V,E), where V is the set of vertices. Each of its verti-ces is some binary input of DD. Only the inputs that detect faults are included in the set V. The set E forms edges between any pair of vertices of the graph G. Each edge (i,j) is assigned to a some number (weight). Its meaning is to assess the feasibility of including the input j in the step-by-step process synthesis of test after the input i. Considered PTS is the most close to the classic traveling salesman problem (TSP).The basis of the proposed ant colony algorithm for the PTS is the analogy with the ant colony algorithm for solving the TSP. The article presents formulas similar to those used in the ant colony algorithm for solving TSP to calculate the probabilities of transitions from one input symbol of the test to the next, correction of the pheromone concentration on the edges of the graph G etc. Note that in the proposed ant colony algorithm for solving an TSP the basic principle of self-organization is based on the interaction of components of randomness, multiplicity, positive and negative feedbacks