Graph models for PLA folding problems

This paper considers combinatorial optimization models for the problem of reducing the chip area of programmable logic arrays (PLAs) by folding. In particular, we focus on the variable and block folding problems, and we present theoretical optimization models based on the compatibility graph, on the incompatibility graph and on the representative hyper-graph of a PLA.     

Designing with programmable logic arrays

Programmable logic arrays (PLAs) are characterized by the ability to replace discrete logic components and their equivalent functions in a variety of system designs. With the advent of new technologies and computer software tools such as Amaze, the exercise of designing with PLAs has been simplified. This paper provides a tutorial overview of various aspects of designing with PLAs, and discusses their uses and basic variations to their structures. A design example involving a single-board computer is presented; the control logic in this design can easily be adapted to other single-board computers.     

Automated design of MOS circuits and layout

As the integration size of VLSI chips increases, programmable logic arrays (PLAs) are indispensable for reducing chip design time. In many cases, however, PLAs are too larger or too slow. Here is presented a new approach to overcome such disadvantages. This produces a circuit of a smaller area and faster response time than PLAs, still maintaining the short design time. The approach works as follows: electronic circuits are automatically designed by an algorithm DIMN directly from given logic functions, and then a symbolic layout for them is automatically made by a program SIMON.     

输入端加译码器的可编程逻辑阵列的复杂性分析

输入端加译码器的可编程逻辑阵列比普通的可编程逻辑阵列具有更大的实现能力。这种阵列表现为三级或－与－或电路。本文提出了与该电路相关的一系列基本概念和理论，并且还进行了复杂性分析，结论是使用该阵列实现一个任意Ｎ变量逻辑函数所需的最大存储单元数为：（２ｎ＋１）２＾ｎ－２．     

Seven strategies for tolerating highly defective fabrication

This article we present an architecture that supports fine-grained sparing and resource matching. The base logic structure is a set of interconnected PLAs. The PLAs and their interconnections consist of large arrays of interchangeable nanowires, which serve as programmable product and sum terms and as programmable interconnect links. Each nanowire can have several defective programmable junctions. We can test nanowires for functionality and use only the subset that provides appropriate conductivity and electrical characteristics. We then perform a matching between nanowire junction programmability and application logic needs to use almost all the nanowires even though most of them have defective junctions. We employ seven high-level strategies to achieve this level of defect tolerance.     

Analysis of testable PLA designs

A framework is presented for evaluating methods of testing programmable logic arrays (PLAs), and the attributes of 25 test design methodologies are tabulated. PLA testing problems are first examined, and several test-generation algorithms are briefly described. Techniques for designing testable designs are examined, namely, special coding, parity checking, signature analysis, divide and conquer, and fully testable PLAs. The attributes that make a good testable design are then discussed. They fall into four categories: (1) testability characteristics; (2) effect on original design; (3) requirements of the application environment; and (4) design costs, i.e. how difficult it is to implement the technique     

Minimal covering problem and PLA minimization

Solving the minimal covering problem by an implicit enumeration method is discussed. The implicit enumeration method in this paper is a modification of the Quine-McCluskey method tailored to computer processing and also its extension, utilizing some new properties of the minimal covering problem for speedup. A heuristic algorithm is also presented to solve large-scale problems. Its application to the minimization of programmable logic arrays (i.e., PLAs) is shown as an example. Computational experiences are presented to confirm the improvements by the implicit enumeration method discussed.This work was supported in part by the National Science Foundation under Grants Nos. MCS77-09744 and MCS81-08505 and also by the Department of Computer Science.M.-H. Young was with the Department of Computer Science, University of Illinois, Urbana, Illinois.     

Built-in test for folded programmable logic arrays

Implementing a function using a programmable logic array (PLA) can often be very expensive in terms of area. Folding rows and/or columns of a PLA usually leads to a reduction in area. In this paper the problem of fault detection in folded PLAs is considered. A new fault, the ‘cutpoint’ fault, is described and universal test sets for the detection of this fault are presented. Modifications to existing built-in universally testable design techniques for nonfolded PLAs are presented; the new designs are now applicable to folded PLAs.     

Algorithms for the compilation of regular expressions into PLAs

The language of regular expressions is a useful one for specifying certain sequential processes at a very high level. They allow easy modification of designs for circuits, like controllers, that are described by patterns of events they must recognize and the responses they must make to those patterns. This paper discusses the compilation of such expressions into specifications for programmable logic arrays (PLAs) that will implement the required function. A regular expression is converted into a nondeterministic finite automaton, and then the automaton states are encoded as values on wires that are inputs and outputs of a PLA. The translation of regular expressions into nondeterministic automata by two different methods is discussed, along with the advantages of each method. A major part of the compilation problem is selection of good state codes for the nondeterministic automata; one successful strategy and its application to microcode compaction is explained in the paper.     

Algorithms for the compilation of regular expressions into PLAs

The language of regular expressions is a useful one for specifying certain sequential processes at a very high level. They allow easy modification of designs for circuits, like controllers, that are described by patterns of events they must recognize and the responses they must make to those patterns. This paper discusses the compilation of such expressions into specifications for programmable logic arrays (PLAs) that will implement the required function. A regular expression is converted into a nondeterministic finite automaton, and then the automaton states are encoded as values on wires that are inputs and outputs of a PLA. The translation of regular expressions into nondeterministic automata by two different methods is discussed, along with the advantages of each method. A major part of the compilation problem is selection of good state codes for the nondeterministic automata; one successful strategy and its application to microcode compaction is explained in the paper.Research supported by DARPA Contract N00039-83-C-0136 and NSF Grant MCS-82-03405.     

A method for consistent fault coverage reporting

Procedure 5012 of Mil-Std-883, which describes requirements for the logic model, the assumed fault model and universe, fault classing, fault simulation and reporting of test results for digital microcircuits is described. The procedure provides a consistent means of measuring fault coverage regardless of the specific logic and fault simulator used. Procedure 5012 addresses complex, embedded structures such as random-access memories (RAMs), read-only memories (ROMs), and programmable logic arrays (PLAs) weighting gate-level and non-gate-level structures by transistor counts to arrive at overall fault coverage     

Multiple-valued logic and optimization of programmable logic arrays

Shows a method of designing programmable logic arrays (PLAs) using multiple-valued input, two-valued output functions (MVITVOFs). A MVITVOF is an extension of the two-valued logic function. An expression for a MVITVOF directly represents a multiple-output PLA with decoders. Each product of the expression corresponds to each column of the PLA, so the number of products; in the expression equals the number of columns of the PLA. The array size of the PLA is proportional to the number of products; the PLA can thus be minimized by minimizing the expression     

Testing And Applications of Inverter-Free PLAs

The testing properties of inverter-free PLAs make them ideal for application to totally self-checking and easily testable circuits. After a class of test patterns and masking relations for these new patterns are determined, a complete test set for single and multiple crosspoint faults can be easily generated. Moreover, the procedure does not require any fault simulation. The code space inputs detect all single and multiple faults in PLAs for totally self-checking circuits, even if the faults are not unidirectional. The test results can be used to analyze easily testable PLAs. With minor hardware changes in one-input decoder PLAs, the personality matrix will serve as a complete test set.     

Agile product-line architecting in practice: A case study in smart grids

ContextSoftware Product Line Engineering implies the upfront design of a Product-Line Architecture (PLA) from which individual product applications can be engineered. The big upfront design associated with PLAs is in conflict with the current need of “being open to change”. To make the development of product-lines more flexible and adaptable to changes, several companies are adopting Agile Product Line Engineering. However, to put Agile Product Line Engineering into practice it is still necessary to make mechanisms available to assist and guide the agile construction and evolution of PLAs.ObjectiveThis paper presents the validation of a process for “the agile construction and evolution of product-line architectures”, called Agile Product-Line Architecting (APLA). The contribution of the APLA process is the integration of a set of models for describing, documenting, and tracing PLAs, as well as an algorithm for guiding the change decision-making process of PLAs. The APLA process is assessed to prove that assists Agile Product Line Engineering practitioners in the construction and evolution of PLAs.MethodValidation is performed through a case study by using both quantitative and qualitative analysis. Quantitative analysis was performed using statistics, whereas qualitative analysis was performed through interviews using constant comparison, triangulation, and supporting tools. This case study was conducted according to the guidelines of Runeson and Höst in a software factory where three projects in the domain of Smart Grids were involved.ResultsAPLA is deployed through the Flexible-PLA modeling framework. This framework supported the successful development and evolution of the PLA of a family of power metering management applications for Smart Grids.ConclusionsAPLA is a well-supported solution for the agile construction and evolution of PLAs. This case study illustrates that the proposed solution for the agile construction of PLAs is viable in an industry project on Smart Grids.     

Easy Test Generation PLAs

Test Generation for large circuits may be extremely difficult.One of the approaches to alleviatingthis problem is to consider the difficulties during the design cycle.This paper proposes a design of EasyTest Generation Programmable Logic Arrays(ETG PLAs),for which test generation is basically notrequired,since a complete test set can be generated while the test is applied.This paper also presents aprocedure which makes a PLA an ETG PLA by following some design rules and providing reasonableextra hardware.     

Compatibility relation algorithm for the folding of programmable logic arrays

The basic principles of an algorithm for the folding of programmable logic arrays (PLAs) are presented in this paper. The algorithm is valid for both column and row folding, although it has been described considering only the simple column folding. The pairwise compatibility relations among all the pairs of the columns of the PLA are mapped into a square matrix, called the compatibility matrix of the PLA. A foldable compatibility matrix (FCM), is then derived from the compatibility matrix. The algorithm presented in this paper is based on the FCM concept and the folding theorem, which states that the existence of an n x m FCM is both necessary and sufficient to fold 2m columns of an M-column PLA (2m ≤ n). Once an FCM is obtained, the ordered pairs of foldable columns and the reordering of the rows are readily determined. It has been conjectured that the algorithm produces the maximum folding of the PLA in all cases.     

Design of electronically steerable linear arrays with evolutionary algorithms

This paper deals with the design of electronically steerable linear arrays for intelligent antenna systems. The design problem is modeled as a multi-objective optimization problem with non-linear constraints. The well-known NSGA-II and SPEA 2 algorithms are employed as the methodologies to solve the resulting optimization problem. The main goal and contribution of this paper is computation of the trade-off curves between side lobe level and main beam width for steerable linear arrays. The addressed problem considers a driving-point impedance restriction placed on each element in the array. This consideration makes the problem more restrictive and therefore more difficult to solve. Experimental results show the effectiveness of the algorithms for the design of steerable linear arrays.     

一种可重构阵列的最小瑕点覆盖算法

关于可重构阵列的瑕点覆盖问题受到了很多文献的关注，特别地，关于可重构阵列的最小瑕点覆盖问题等价于二分图的受约束最小点覆盖问题，并被证明是NP-完全问题。针对本问题提出的算法运行时间为O(1．19^k kn)，这里k为可替换行与列的数目，改进了原有的最好结果，其运行时间为0(1．266k kn)，较好地组合并扩展了研究参数计算的最新技术与经典匹配理论，且具有较好的实用价值。这是关于可重构阵列的最小瑕点覆盖问题算法又一较大的改进，也是目前最小点覆盖问题相关参数算法的较有意义的改进。     

Synchronizing square arrays in optimum-time

The firing squad synchronization problem on cellular automata has been studied extensively for more than 50 years, and a rich variety of synchronization algorithms have been proposed for not only one-dimensional (1D) arrays but also 2D arrays. In this paper, we construct a survey on a design and implementation of optimum-time synchronization algorithms for 2D square arrays.     

A fast partitioning method for PLA-based FPGAs

A method for automatic multipartitioning of a multiple-output logic function into the smallest number of subfunctions for mapping to fixed-size PLAs of a field-programmable gate array (FPGA) chip is described. A detailed example to demonstrate the procedure is presented. It is shown that, for this example, the method produced almost optimum partitions in a fast and efficient manner