On one approach to approximate synthesis of discrete devices with memory

The problem of approximate synthesis of discrete memory devices (DM) is considered. In the last decade a similar problem for combinational circuits (CC) has been actively studied. Interest in them is caused by the possibility of obtaining compact and reliable devices at the expense of relaxing requirements for the accuracy of their functions. The resulting flexibility in operation can be used to reduce chip area, circuit delays, and increase fault tolerance. Changes in the devices result in mismatches with the outputs of the prototype circuit. In a number of areas they may be quite acceptable in practice. The problem of approximate synthesis of discrete memory devices in the proposed article was investigated in the formulation, which has not been previously considered, which explains the absence of relevant publications. In previously known publications on the approximate synthesis of automata-type systems, where the closeness of the obtained solution is understood as obtaining an approximate (in quality) solution to the optimal one of the problem for which the sought simpler device is created. In this case, the quality of the solution can be evaluated according to various criteria. The corresponding methods are not applicable to the problem we are considering, since they are based on the use of the specifics of such systems. In the paper the object of research is any discrete memory device (DM) represented by a finite state machine model described by its transition-exit table (TET). This is the most general and widespread mathematical model of such DMs. For practical applications the following problem is of interest: for a given DM of interest it is required to synthesize an approximating device (ADM) that minimizes the number of mismatches (conflicts) with DM outputs on an arbitrary input sequence and that should be less complex than the prototype DM. The proposed article is devoted to the approach of its solution. This approach implies two stages. The first stage consists in obtaining vectors of characteristic features of outputs of a given automaton. Their obtaining is based on the use of the well-developed apparatus of the theory of sampling research. These vectors are formed by the TET of a given DM using the frequency principle. Their components correspond to DM outputs and are equal to 0 or 1, or to the symbol * . The values 0 or 1 indicate that they are with high probability almost stabilized at the corresponding DM output, while the symbol * indicates the absence of stabilization. The feature vectors are used at the second stage to form the initial generation for the operation of the GA proposed in the article. The second stage consists in obtaining the TET of the sought device with memory, which is an approximate model of the given automaton (prototype). The search for such a table is reduced to a problem of combinatorial type and for its solution the use of so-called simple GA is proposed. It is known that they are very effective for solving problems of combinatorial type. The article gives a generalized description of GA. The introduced target function in the form of a weighted sum of two summands is justified since the problem under consideration is multicriteria. The peculiarities of the implementation of the GA, in particular the execution of the recombination (crossing) operator, are given. The author declares no conflicts of interests.

Keywords

Authors

References