Programmable logic cell and array

Abstract

Programmable logic cells, and arrays of those cells, having certain characteristics, including: (1) the ability to program each cell to act either as a logic element or as a logical identity element(s) between one or more inputs and one or more outputs; (2) the ability to rotate circuits by 90° and to reflect circuits about horizontal and vertical axes; (3) an integrated logic and communication structure which emphasizes strictly local communications; (4) a minimal complexity of logic functions available at the cell level, making available a very fine-grained logic structure; and (5) suitability for implementation of both synchronous and asynchronous logic, including speed-independent circuits. Cells are arranged in a grid, with each cell communicating with its north, east, west and south neighbors. The cells are programmable to several states. Using a graphics-based programming environment, the user may construct systems at a pictorial block diagram level, rather than having to be concerned about the detailed implementation of the internal structure of each block. Blocks may be rotated and they may be reflected about horizontal and vertical axes, to place their input and output connections on different sides and positions without altering the internal electrical operation of the blocks.

What is claimed is: 
     
       1. A digital logic cell for use in a programmable logic device, such cell having: a. first and second signal inputs for receiving input signals and first and second signal outputs for supplying output signals;   b. means responsive to programming signals applied thereto for programming the cell to assume one of a plurality of available states, each state uniquely defining the type of signal supplied to the signal outputs, and each of the available cell states having the property that, when the cell is programmed in that state, if the first and second signal inputs of the cell are interchanged, and concurrently the first and second signal outputs of the cell are interchanged, then the resulting state of the cell is one of the available cell states; and   c. the means for programming the cell providing a state wherein at least one of the signal outputs supplies an output signal comprising a logical function of the input signals received by both the first and second signal inputs.   
     
     
       2. A digital device containing an array of programmable logic cells, comprising: a. a plurality of programmable logic cells, each having (1) first and second signal inputs for receiving input signals and first and second signal outputs for supplying output signals and (2) means responsive to programming signals applied thereto for programming the cell to assume one of a plurality of available states, each state uniquely defining the type of signal supplied to the signal outputs;   b. said plurality of cells being arranged operatively in a topology forming an array of rows and columns of cells such that each cell except those cells on the periphery of the array has four immediate neighbor cells, referred to as the cell's north, east, south and west neighbors; and   c. said array containing at least one cell in each of four available orientations, wherein (i) in a first cell orientation, the first input of the cell is operatively connected to an output of the cell's western neighbor, the second input is operatively connected to an output of the cell's northern neighbor, the first output is operatively connected to an input of the cell's eastern neighbor, and the second output is operatively connected to an input of the cell's southern neighbor;   (ii) in a second cell orientation, the first input of the cell is operatively connected to an output of the cell's northern neighbor, the second input is operatively connected to an output of the cell's eastern neighbor, the first output is operatively connected to an input of the cell's southern neighbor, and the second output is operatively connected to an input of the cell's western neighbor;   (iii) in a third cell orientation, the first input of the cell is operatively connected to an output of the cell's eastern neighbor, the second input is operatively connected to an output of the cell's southern neighbor, the first output is operatively connected to an input of the cell's western neighbor, and the second output is operatively connected to an input of the cell's northern neighbor; and   (iv) in a fourth cell orientation, the first input of the cell is operatively connected to an output of the cell's southern neighbor, the second input is operatively connected to an output of the cell's western neighbor, the first output is operatively connected to an input of the cell's northern neighbor, and the second output is operatively connected to an input of the cell's eastern neighbor.     
     
     
       3. The device of claim 2 wherein all of said plurality of programmable logic cells are functionally identical. 
     
     
       4. The device of either of claims 2 and 3 wherein each of said cells, other than those cells on the periphery of the array, is in one of said four orientations. 
     
     
       5. The device of claim 4 wherein each of said cells, other than those cells on the periphery of the array, is in a different orientation from its immediate neighbors. 
     
     
       6. The device of either of claims 2 and 3 wherein the array possesses certain attributes of symmetry such that an original circuit formed in the array, by programming an appropriate set of cell states, can be rotated 90° in the array, by an appropriate reprogramming of cell states of the array, to form a circuit that is functionally and topologically identical to said original circuit. 
     
     
       7. The device of either of claims 2 and 3 wherein the array possesses certain attributes of symmetry such that an original circuit formed in the array, by programming an appropriate set of cell states, can be reflected about an axis in the array, by an appropriate reprogramming of cell states of the array, to form a circuit that is functionally and topologically identical to said original circuit. 
     
     
       8. The device of either of claims 2 and 3 wherein the array possesses certain attributes of symmetry such that an original circuit formed in the array, by programming an appropriate set of cell states, can be both reflected about an axis in the array and rotated by 90°, by an appropriate reprogramming of cell states of the array, to form a circuit that is functionally and topologically identical to said original circuit. 
     
     
       9. The device of either of claims 2 and 3 wherein the available cell states for each cell have the property that for each available cell state, if the first and second cell inputs are interchanged and the first and second cell outputs are interchanged, then the resulting cell state is one of the available cell states. 
     
     
       10. A digital device containing an array of programmable logic cells, comprising: a. a plurality of functionally identical, programmable logic cells, each having a plurality of signal inputs and a plurality of signal outputs and being programmable to assume one of a plurality of available states;   b. said plurality of cells being arranged operatively in a topology forming an array of rows and columns of cells such that each cell except those cells on the periphery of the array has four immediate neighbor cells;   c. each of said cells being disposed in one of a plurality of distinct possible cell orientations, the orientations being related such that any cell orientation can be obtained from any other cell orientation through one of a reflection, a rotation, and a rotation followed by a reflection; and   d. said array containing at least one cell in each of said cell orientations.   
     
     
       11. The device of claim 10 wherein each of said cells is in a different orientation than its immediate neighbor cells. 
     
     
       12. The device of either of claims 10 and 11 wherein each of said cells, other than those cells on the periphery of the array, is in one of said four orientations. 
     
     
       13. The device of either of claims 10 and 11 wherein each of said cells has only two inputs and only two output. 
     
     
       14. The device of any of claim 1, 2, 3, 10 or 11 wherein each of the available cell states possesses exactly one axis of symmetry. 
     
     
       15. The cell of any of claims 1, 2, 3, or 10 further including means for providing at least one state in which the cell provides at one of its outputs a logical constant value. 
     
     
       16. The device of any of claims 1, 2, 3 or 10 wherein the available cell states for each cell include a state in which one of the cell's first and second inputs is connected as one of a logical identity and a logical negation to one of its first and second outputs. 
     
     
       17. The cell of claim 16 wherein the available cell states include a state in which the other of the cell's first and second inputs is connected as one of a logical identity and a logical negation to the other of its first and second outputs. 
     
     
       18. The device of any of claims 1, 2, 3 or 10 wherein the available cell states for each cell include states providing functions from which a universal Boolean logic function may be assembled. 
     
     
       19. A digital logic cell for use in a programmable logic device, such cell having: a. only first and second signal inputs for receiving input signals and only first and second signal outputs for supplying output signals;   b. means responsive to programming signals applied thereto for programming the cell to assume one of a plurality of available states, each state uniquely defining the type of signal supplied to the signal outputs, and each of the available cell states having the property that, when the cell is programmed in that state, if the first and second signal inputs of the cell are interchanged, and concurrently the first and second signal outputs of the cell are interchanged, then the resulting state of the cell is one of the available cell states; and   c. the means for programming the cell providing a state wherein at least one of the signal outputs supplies an output signal comprising a logical function of the input signals received by both the first and second signal inputs.   
     
     
       20. A digital device containing an array of programmable logic cells, comprising: a. a plurality of programmable logic cells, each having two signal inputs and two signal outputs and being programmable to assume one of a plurality of available states;   b. said plurality of cells being arranged in an array wherein, except for those cells on the periphery of the array, each of a cell's signal inputs and each of a cell's signal outputs is operatively connected to a neighboring cell in the array; and   c. said array possessing certain attributes of symmetry such that an original circuit formed in the array, by programming an appropriate set of cell states, can be rotated 90° in the array, by an appropriate reprogramming of cell states of the array, to form a circuit that is functionally and topologically identical to said original circuit.   
     
     
       21. A digital device containing an array of programmable logic cells, comprising: a. a plurality of programmable logic cells, each having two signal inputs and two signal outputs and being programmable to assume one of a plurality of available states;   b. said plurality of cells being arranged in an array wherein, except for those cells on the periphery of the array, each of a cell's signal inputs and each of a cell's signal outputs is operatively connected to a neighboring cell in the array; and   c. said array possessing certain attributes of symmetry such that an original circuit formed in the array, by programming an appropriate set of cell states, can be reflected about an axis in the array, by an appropriate reprogramming of cell states of the array, to form a circuit that is functionally and topologically identical to said original circuit.   
     
     
       22. A digital device containing an array of programmable logic cells, comprising: a. a plurality of programmable logic cells, each having two signal inputs and two signal outputs and being programmable to assume one of a plurality of available states;   b. said plurality of cells being arranged in an array wherein, except for those cells on the periphery of the array, each of a cell's signal inputs and each of a cell's signal outputs is operatively connected to a neighboring cell in the array; and   c. said array possessing certain attributes of symmetry such that an original circuit formed in the array, by programming an appropriate set of cell states, can be both reflected about an axis in the array and rotated by 90°, by an appropriate reprogramming of cell states of the array, to form a circuit that is functionally and topologically identical to said original circuit.