US 7577011 B2
A method for designing a read-only memory (ROM), and related device, includes partitioning a dataset into two or more sub-datasets that each have the same address space, but are of a smaller bit-width than the original dataset. The sub-datasets are row collapsed, and then respective memory cells for the sub-datasets are provided. The output of the memory cells provides the output of the ROM. Each memory cell includes a decoder that maps addresses to word lines based on mapping information obtained during row collapsing, and a logic array driven by the decoder that encodes the data words of the sub-dataset.
1. A read-only memory (ROM) comprising:
Q input address lines for supplying an address;
P output bit lines for supplying a P-bit data word according to the first address; and
N memory cells C1 to CN, where N>1, and each memory cell Ci comprises:
Wi word lines respectively electrically coupled to Bi bit lines according to a dataset to be stored within the ROM, wherein 1<Bi<P; and
a decoder Di coupled to the Q input lines and adapted to assert one of the Wi word lines according to the first address;
wherein for at least one of the memory cells Ci, the corresponding number of word lines Wi is less than 2Q; and
wherein the P-bit data word is obtained from the bit lines of the memory cells.
2. The ROM of
3. The ROM of
4. The ROM of
5. The ROM of
6. The ROM of
7. The ROM of
This application is a continuation-in-part of Application Ser. No. 11/580,786, filed Oct. 13, 2006, which is included herein by reference in its entirety.
The present invention relates generally to reducing the size requirements of a read-only memory (ROM), and more particularly, to restructuring the architecture of the ROM based upon the data to be stored within the ROM, which may be applicable to SoC and ASIC devices.
Steady advances in miniaturization techniques for integrated circuits have resulted in circuit devices, particularly transistors, of ever-diminishing sizes. Generally speaking, each generation of an integrated circuit utilizes transistors that occupy smaller footprints on the semiconductor substrate than those of the previous generation. However, consumer desires, with resultant design demands, seem to grow even faster than integrated circuit devices have been shrinking. As a result, rather than being in surplus, real estate on the circuit substrate remains at a premium. Every unit of area on a substrate must be maximally utilized to squeeze as much performance as possible into the limited space of the circuit die. If a way can be found to reduce the size of a circuit in one portion of a chip, the area thereby freed up can be used to support additional circuitry to pack even more logic functionality into the same die. The miniaturization race therefore involves not only reducing the footprint of individual devices, such as transistors, on the die, but also finding ways to use fewer such devices to achieve the same functionality.
Many digital designs employ read-only memory (ROM), which is built directly onto the same die with the rest of the circuit. This on-chip ROM provides necessary data for the circuit, such as microcode instructions, object code, operating parameters and the like. Generally, a ROM circuit has Q address lines as input for accessing 2Q data words respectively stored within the ROM at 2Q addresses, where Q≧1. Each data word may hold P data bits, P≧1, which are provided on P respective bit output lines. Hence, at a high level of abstraction, a ROM stores a dataset and implements a 2Q×P look-up table with this dataset, in which the input value is provided on the Q address lines, and the P-bit data word output result is provided on the P bit output lines. By way of example, the following 24×4 dataset is considered:
Four address input bits, A0, A1, A2 and A3, provide sixteen addresses, 0 to 15, each of which stores a data word of four bits, B0, B1, B2 and B3. Although specific reference in the following is drawn to a 16×4 dataset, the principles are applicable to any generalized 2Q×P dataset, where Q is the number of address bits, and P is the number of bits in the data word.
A prior art design for a ROM 10 that implements the dataset of Table 1 is shown in
Because each output bit line B0-B3 is tied to ground, the bit lines B0-B3 are normally in a logical zero state. By utilizing any suitable connecting device 16 to selectively electrically connect each output bit B0-B3 to zero or more word lines L0-L15, it is possible to implement the dataset of Table 1. By electrically connecting an output bit line B0-B3 to a word line L0-L15, the normally-low output bit line B0-B3 will go high when the word line L0-L15 is asserted. Each connecting device 16 may therefore represent a logical one for the corresponding output bit line B0-B3 at a corresponding value of the input address provided by address lines A0-A3.
For the sake of simplicity, the connecting device 16 of
Because ROM is such a ubiquitous component, it would be highly beneficial if a method could be found to reduce the footprint of the ROM, and thereby free up substrate real estate for other circuit components. In particular, since the logic array 18 that encodes the dataset occupies a relatively large footprint, it would be particularly beneficial if the size of the logic array 18 could be reduced.
It is an objective of the instant invention to reduce the footprint of a read-only memory (ROM) by tailoring the logic of the ROM to the particular dataset the ROM is to encode. In one aspect, a ROM device includes Q input address lines for supplying a first address, P output bit lines for supplying a P-bit data word according to the first address, and N memory cells C1 to CN, where N>1. Each memory cell Ci comprises Wi word lines respectively electrically coupled to Bi bit lines according to a dataset to be stored within the ROM, in which 1<Bi<P. Each memory cell Ci also includes a decoder Di coupled to the Q input lines, which asserts one of the Wi word lines based upon the input first address. The P-bit data word may be obtained from the bit lines of all the memory cells (C1 to CN). This P-bit data word may be used to provide the final output of the ROM. In certain embodiment, each memory cell Ci has fewer than 2Q word lines. In a specific embodiment, each memory cell Ci has no more than 2 to the power of Bi word lines, where Bi is the respective number of bit lines in the memory cell Ci. In other embodiments, the total number of bit lines in all of the memory cells Ci equals P, and the bit lines of the memory cells provide the output data word of the ROM. In other embodiments, the bit lines feed into a selector that selects a portion of the bit lines as the output of the ROM based upon an input second address.
In another aspect, a method for designing a ROM that stores a dataset that may be represented as an M×P table is provided. The dataset is partitioned into N sub-datasets capable of respectively being represented by tables T1 to TN, wherein N>1, and for every i from 1 to N, each table Ti is of the form M×Bi, with each Bi being less than P. At least one of the N sub-datasets represented by a table Tr is at least partially row collapsed so that at least a first redundant entry in the table Tr is removed and an address of the removed entry is mapped to a second entry. N logic arrays L1 to LN are then provided that respectively encode the N sub-datasets using W1 to WN word lines, respectively, and B1 to BN bit lines, respectively. N decoders D1 to DN are provided that respectively drive the N logic arrays L1 to LN according to an input address and any respective mapping information from at least partially row collapsing the respective sub-dataset. In particular, a decoder Dr for a logic array Lr that encodes the at least partially row collapsed sub-dataset represented by the table Tr maps the address of the removed entry to a word line corresponding to an address of the second entry. The output of the bit lines may then be used to provide the output of the ROM. In some embodiments, the method further includes fully row-collapsing each of the N sub-datasets, and for each logic array Li, the corresponding number of word lines Wi within the logic array Li is no greater than 2 to the power of the number of bit lines Bi.
For purposes of the following description, when a line is “asserted,” a line is driven into a particular logical state to indicate the occurrence of a certain event or value, or to cause a certain event or value to occur. A line may be asserted high (true logic) or low (false logic). As with the design of most digital logic components, the type of logic used, true or false, is purely a design choice. Hence, in the following, if true logic is used by way of example, it should be clear that with minor modifications false logic could equivalently be used. Such permutations in logic are common for those having ordinary skill in the art of digital electronics, and do not require undue experimentation.
The term “map” is broadly meant as an operation which converts a value to another value, such as y=f(x). The mapping function f(x) may map a set of numbers into a larger space, an equally-sized space, or a smaller space. With respect to a digital component, a digital component may map a value provided on an input into another value provided on one or more outputs. With particular respect to a decoder, a decoder accepts as input an N-bit value, and maps that N-bit value by asserting one of X output lines, as known in the art. A decoder may thus be used to map an input value to an output value or line.
Additionally, for purposes of the following, when a word line is said to “store” or “encode” a data word, it is to be understood that such “storing” or “encoding” may be manifested by the electrical connections established between the word line and one or more bit lines.
The instant invention methods, and related ROM designs, seek to improve the layout of a ROM by first analyzing the dataset that the ROM is to store, and then tailoring the design of the ROM to the dataset so as to reduce the number of devices in the ROM. By way of continuing example, reference is again drawn to the dataset of Table 1. A first aspect of the invention begins by noting identical data words in the dataset. If two or more addresses contain the same data word, then the redundant rows in the table corresponding to these entries may be removed, and the addresses of these removed entries may be mapped to the address of the single entry that is not removed. This is termed row collapsing the table or dataset. In the following, when it is stated that a table is row collapsed, it should be understood that the underlying dataset that the table represents is also row collapsed.
In Table 1, addresses zero, four, eight and twelve all have the same data word, (B0, B1, B2, B3)=(0, 0, 1, 1). The rows for any three of these four entries may be considered redundant, such as the entries for addresses four, eight and twelve. The rows for addresses four, eight and twelve may thus be row collapsed. The redundant entries for addresses four, eight and twelve are removed from the table and are mapped to the address of the remaining entry, address zero. Hence, a single row will exist in the newly row collapsed table or dataset, in which the data word is (B0, B1, B2, B3)=(0, 0, 1, 1), and the corresponding address is zero, but which further includes the mapping information containing the three addresses four, eight and twelve. In short, the row collapsed table has a single entry with multiple addresses.
With respect to Table 1, a similar procedure may be performed for other redundant entries. While the table has some remaining redundant entries and others that contain mapping information, the table may be considered partially row collapsed. When all redundant entries have been row collapsed, the result is a fully row collapsed table that contains no rows that have identical data word entries. With respect to Table 1, the fully row collapsed table is presented below:
As can be seen from Table 2 above, more than half of the rows in Table 1 have been collapsed, yielding Table 2 with but seven rows. Each row of Table 2 holds a unique data word (B0, B1, B2, B3). The embodiment invention method proceeds by designing an improved ROM based upon the row-collapsed table, which, like Table 2 above, may ideally have no repetitive data word entries. That is, it is not necessary that the table or dataset be fully row-collapsed, but it may be desirable to fully row-collapse. The improved ROM has a structure similar to the prior art ROM design 10, but has a modified decoder, and a reduced number of word lines. In particular, the improved ROM may have as many word lines as there are rows in the row collapsed table; the row collapsed table may have only unique data word entries (if it is fully row-collapsed), or may have one or more redundant data word entries. In a specific embodiment, the dataset is fully row-collapsed, so that each word line stores a unique data word value that no other word line in the ROM stores. In particular, because a data word of bit size P has but 2P unique data word values, in these embodiments, the ROM will have no more than 2P word lines in the logic array that encodes the fully row collapsed data set. Because there may be more input addresses than word lines, the modified decoder may thus cause at least two input addresses to map to the same word line. That is, in certain embodiments, the modified decoder may be a Q to X decoder, where X is greater than one and less than 2Q, and each of 2Q possible input address values maps to one and only one of the X word lines output by the decoder. The mapping function may be constructed so that a word line stores the data word for the redundant address value mapped to that word line.
A first embodiment improved ROM design 20 is shown in
A decoder 22 implements the mapping information carried within Table 2, asserting word line W0 when the address on address lines A0-A3 is zero, four, eight or twelve; asserting word line W1 when the address is one, nine or fourteen, etc. Decoder 22 is thus a Q to X decoder, where X is less than 2Q; specifically, decoder 22 is a 4 to 7 decoder, as required by Table 2, which maps each of 2Q=4 possible addresses to one of the X=7 word lines. When an address is mapped to a word line, the presence of that address on the input address lines A0-A3 causes the decoder 22 to assert that word line, as previously explained. Designing the decoder 22 should be routine for one of ordinary skill in the art. For example, simply taking the prior art decoder 10 of
Besides providing a potentially simpler, and hence smaller, design for the decoder 22, the embodiment ROM 20 uses fewer connecting devices 26 to implement the same dataset, and has fewer word lines. The prior art design 10, for example, requires thirty-six connection devices 16 to implement the dataset of Table 1, and sixteen word lines L0-L15. The embodiment ROM 20, however, requires only sixteen connection devices 26, and seven word lines W0-W6. The logic array 28 of the ROM 20 may thus occupy a considerably reduced footprint on the circuit substrate in comparison to the logic array 18 of the prior art. Additionally, because fewer connection devices 26 are used, the ROM 20 may have both lower power demands, and faster access speeds. By decreasing the number of connecting devices (transistors or diodes), leakage power may be reduced. Since fewer connecting devices are present, capacitance may be reduced, and so rise and fall times will be shorter, making for a faster device.
To provide for further reductions in the footprint of the ROM, the dataset may be partitioned into two or more sub-datasets. Each sub-dataset may have the same address space of the original dataset, but has only a portion of the data bits of the data words. The dataset may be partitioned so as to maximize row collapsing of the sub-datasets, and to minimize the number of logic components used to provide the respective decoders, as discussed below. For example, each sub-dataset may have data words of a bit size that is less than, such as half of or a quarter of, the address bit size. In general terms, an M×P dataset, where M may be 2Q, can be partitioned into N sub-datasets of the form M×B1, M×B2 . . . M×BN, where B1+B2+ . . . +BN=P. This may be thought of as vertically splitting the dataset into N sub-datasets M×Bi, which may be respectively represented by tables Ti. At least one, and in some embodiments all, of the sub-datasets Ti, where i is between 1 and N, is at least partially row collapsed. In certain advantageous embodiments, all of the sub-datasets Ti are fully row collapsed. Memory cells Ci are then respectively provided for the resultant sub-datasets Ti, each with its respective decoder Di and logic array Li. The memory cells Ci are analogous to the first embodiment ROM 20, but each provides only a portion of the total output of the ROM, as provided by its respective sub-dataset Ti. Each logic array Li has as many word lines as there are rows in the respective sub-dataset Ti, and as many bit lines as there are columns in the respective sub-dataset Ti, encoding the data words of bit size Bi within the sub-dataset Ti by way of appropriate electrical connections between the bit lines and word lines. The word lines of each logic array Li are driven by the respective decoder Di, which implements the mapping information of the sub-dataset table Ti. The output of the bit lines from the memory cells Ci is combined to provide the full P-bit data word output of the ROM. In certain advantageous embodiments, because the datasets Ti are fully row-collapsed, the maximum number of rows in each logic array Li is 2Bi. The original structure using a single fully row collapsed dataset would have had a maximum of 2P rows. It is evident that P=B1+B2+ . . . BN. However, in the modified structure, a maximum of 2B1+2B2+ . . . +2BN rows are present, which is less than 2P. Better row-collapsing may be possible when vertical splitting of the dataset is performed.
To illustrate the above with a continuing example, the fully row collapsed dataset of Table 2 is considered. Of course, the original dataset as presented by Table 1 does not need to first be row collapsed before being partitioned. A single row collapsing after partitioning will yield the same result as partitioning a row collapsed dataset and then again row collapsing the resultant sub-datasets. However, using the dataset of Table 2 permits the additional benefits of partitioning to be more easily seen. The data set of Table 2 is partitioned into two sub-datasets T1 and T2. Sub-dataset T1 holds data word bits B0 and B1, while sub-dataset T2 holds data word bits B2 and B3. The resultant partitioning is shown in Tables 3 and 4 below:
The sub-dataset T1 or T2, respective depicted in Table 3 and Table 4, may then be at least partially row collapsed. Alternatively, both of the sub-datasets T1 and T2 may be partially row collapsed. In the particular embodiment discussed in the following, both sub-datasets T1 and T2 are fully row collapsed, yielding the following sub-datasets T1′ and T2′:
As can be seen from the above, each sub-dataset T1′ and T2′ has no more than 2B entries, where B is the bit size of the respective data words within the table. As each table holds words of bit size two, neither Table 5 nor Table 6 will have more than 22, or four, entries. Indeed, the original dataset of Table 1 is so redundant that fully row collapsed sub-dataset T2′ has but three entries, into which are mapped all of the possible 24 or sixteen, possible addresses.
A second embodiment improved ROM 30 is depicted in
The ROM 30 has as many memory cells as there are sub-datasets to be implemented. Each memory cell implements its respective sub-dataset, using its own decoder and logic array. Specifically, the ROM 30 has a first memory cell C1 that implements the sub-dataset of Table 5, and a second memory cell C2 that implements the sub-dataset of Table 6. The first memory cell C1 includes a decoder D1 that implements the mapping information in Table 5, and a logic array 38-1 that implements the data words of the sub-dataset in Table 5. The logic array 38-1 thus has four word lines W1-0 to W1-3, which are electrically connected to two bit lines B0, B1 with connection devices 36 according to the sub-dataset of Table 5. Similarly, the second memory cell C2 includes a decoder D2 that implements the mapping information in Table 6, and a logic array 38-2 that implements the data words of the sub-dataset in Table 6. The logic array 38-2 has three word lines W2-0 to W2-2 electrically connected to two bit lines B2, B3 according to the sub-dataset of Table 6. The bit lines B0-B3 provide the four bits of data output from the ROM 30.
Functionally, the ROM 30 provides the same output B0-B3 for the same input A0-A3 as does the prior art ROM 10, and the first embodiment ROM 20. The ROM 30, however, uses only seven connection devices 36, in contrast to the prior art ROM's use of thirty-six connection devices 16. Further, with the memory cells C1, C2 aligned in a row, the ROM 30 has a height of only four word lines, in contrast to the seven of the first embodiment design 20, and sixteen of the prior art 10. Although the second embodiment design 30 makes use of two decoders D1, D2, based upon the dataset, it is possible that the two decoders D1, D2 together utilize no more substrate real estate on the circuit die than does the prior art decoder 12; this, however, will depend upon the dataset. Indeed, if the dataset is logically quite redundant, suitable selections of data bits B0-B3 may be combined to form memory cells that have relatively simple decoders, providing even more savings in substrate real estate.
The improvement methods and related ROMs of the instant invention have been presented with respect to a highly simple 16×4 ROM for ease of description. One of ordinary skill in the art, however, should recognize that the invention is readily expandable to any M×P ROM; indeed, it is possible that ROMs of greater dimension are more likely to benefit from the instant invention than those of lesser dimensions. In particular, ROMs that have a large address space of relatively small data words are very likely to benefit from the instant invention, as multiple memory cells as provided by the instant invention may provide for less height in the ROM without significantly expanding its width. Also, it will be appreciated that if the pattern for any of two or more bit outputs is absolutely identical, then one can collapse them and have one column but still drive two output lines.
The order of the method steps indicated above may be changed. Additionally, it will be appreciated that there is a functional equivalency between a dataset, the table that represents the dataset, and a memory cell that at least partially encodes the dataset. Hence, the above steps may be performed, for example, not by initially partitioning a table into sub-tables, but rather by partitioning a memory cell into sub-memory cells. Row collapsing can be performed on a dataset, a table, or a memory cell. The method steps may thus be variously performed to achieve the desired objective of a smaller device footprint and reduced component counts.
For the sake of simplicity only, the above specific embodiments have shown ROM designs that utilize only row decoders for the word lines. It will be appreciated that the instant invention is equally applicable to 2-D ROM designs that utilize both row and column decoders. An example of such a design is depicted in