Range code compression method and apparatus for ternary content addressable memory (CAM) devices
View Patent ↗A content addressable memory (CAM) device, method, and method of generating entries for range matching are disclosed. A CAM device ( 800 ) according to one embodiment can include a pre-encoder ( 806 ) that encodes range bit values W into additional bits E. Additional bits E can indicate compression of range rules according to particular bit pairs. A CAM array ( 802 ) can include entries that store compressed range code values (RANGE) with corresponding additional bit values (ENC). Alternate embodiments can include pre-encoders that encode portions of range values (K 1 to Ki) in a “one-hot” fashion. Corresponding CAM entries can include encoded value having sections that each represent increasingly finer divisions of a range space.
1. A method for generating ternary content addressable memory entries to represent a search range, comprising the steps of:
generating range code values to represent the search range, the range code values comprising at least a prefix that includes a plurality of bit values;
compressing range code values based on the values varying from one another by predetermined least significant bit values into one range code value; and
adding an extra bit to the compressed range code value to indicate the compressed range code value.
2. The method of claim 1 , wherein:
the step of compressing range code values includes determining if the last two bit values of a first range code value prefix are “01”,
a next higher range code value prefix matches all bits of higher significance than the last two bits of the first range code value prefix,
the two bits of the next higher range code value prefix corresponding to the last two bits of the first range code value prefix are “1X”, and
generating a compressed range code value to represent the first and next higher range code values, the compressed range code value being the same as the first range code value, except for the last two bits of the prefix of the compressed range code value being changed to “XX”; and
the step of adding an extra bit to the compressed range code value includes setting an extra low bound bit to “1” that corresponds to the two bit values changed from 01 to XX, where a bit value of X represents a masked or a “don't care” value.
3. The method of claim 1 , wherein:
the step of compressing range code values includes determining if the last two bit values of a first range code value prefix are “10”,
a next lower range code value prefix value matches all bits of higher significance than the last two bits of the first range code value prefix,
the two bits of the next lower range code value prefix corresponding to the last two bits of the first range code value prefix are “0X”, and
generating a compressed range code value to represent the first and next lower range code values, the compressed range code value being the same as the first range code value, except for the last two bits of the prefix of the compressed range code value being changed to “XX”; and
the step of adding an extra bit to the compressed range code value includes setting an extra high bound bit to “1” that corresponds to the two bit values changed from 10 to XX, where a bit value of X represents a masked or a “don't care” value.
4. The method of claim 1 , wherein:
the bits of the compressed range code value have an order of increasing significance with respect to one another; and
the step of adding an extra bit to the compressed range code value includes adding E bits to each compressed range code value, where E is an integer, each of the E bits corresponding to two bit locations adjacent to one another in the order of significance and representing a compressed range code generated by compressing two range codes that vary from one another at the two bit locations.
5. The method of claim 4 , wherein:
the number of bits in the range code values is W, where W is an integer; and
E is equal to at least ½W, each E bit representing non-overlapping two bit locations beginning with the least significant two bit locations.
6. The method of claim 5 , wherein:
E is no more than W, and includes
a lower bound group of L=W/2 bits that indicates when bit values are compressed to represent a lower bound limitation in the range, and
an upper bound group of H=W/2 bits that indicates when bit values are compressed to represent an upper bound limitation in the range.
7. The method of claim 4 , wherein:
number of bits in the range code values is W, where W is an integer; and
E is equal to at least W−1, each E bit representing overlapping two bit locations beginning with the least significant two bit locations.
8. The method of claim 7 , wherein:
E is no more than 2(W−1), and includes
a lower bound group of L=W−1 bits that indicates when bit values are compressed to represent a lower bound limitation in the range, and
an upper bound group of H=W−1 bits that indicates when bit values are compressed to represent an upper bound limitation in the range.
9. A method for generating search key values for a range rule search in a ternary content addressable memory (CAM), comprising the steps of:
logically combining bit pairs of an original search key value to generate encoded bits in addition to the bits of the original search key value, each encoded bit being generated from no more than two original search key bits; and
applying the bits of the original search key value in parallel with the encoded bits to entries of the ternary CAM, the bits of the original search key being applied to first portions of the ternary CAM entries, the encoded bits being applied to second portions of the ternary CAM entries, the second portions having different bit locations than the first portions.
10. The method of claim 9 , wherein:
the step of logically combining bit pairs includes logically ORing each bit pair with circuits on the ternary CAM.
11. The method of claim 9 , wherein:
the step of logically combining bit pairs includes logically NANDing each bit pair with circuits on the ternary CAM.
12. The method of claim 9 , wherein:
the step of logically combining bit pairs includes logically combining bit pairs in a non-overlapping manner beginning with the least significant bit pair.
13. The method of claim 12 , wherein:
the number of bits in the search key is W, where W is an integer; and
the step of logically combining bit pairs includes logically combining non-overlapping adjacent bit pairs beginning with the least significant bit pair to generate
½W encoded bits that are applied to additional bits of the entries that represent lower boundary compression, and
½W encoded bits that are applied to additional bits of the entries that represent higher boundary compression.
14. The method of claim 9 , wherein:
the step of logically combining bit pairs includes logically combining bit pairs in an overlapping manner beginning with the least significant bit pair.
15. The method of claim 14 , wherein:
the number of bits in the search key is W, where W is an integer; and
the step of logically combining bit pairs includes logically combining overlapping adjacent bit pairs beginning with the least significant bit pair to generate
W−1 encoded bits that are applied to additional bits of the entries that represent lower boundary compression, and
W−1 encoded bits that are applied to additional bits of the entries that represent higher boundary compression.
16. A ternary content addressable memory (CAM) device, comprising:
a compare data input that receives search key values that include W bits, where W is an integer;
at least a first encoder for logically combining bit pairs of the search key value to generate E additional bits, where E is an integer, the first encoder generating each of the E additional bits from no more than one bit pair of the search key value; and
at least one ternary CAM array having entries of M-bit width coupled to receive the W bits of the search key in parallel with the E additional bits, with M being greater than or equal to W+E.
17. The ternary CAM device of claim 16 , wherein:
the at least first encoder comprises a plurality of first logic gates that logically OR bit pairs of the search key value.
18. The ternary CAM device of claim 16 , wherein:
the at least first encoder comprises a plurality of second gates that logically NAND bit pairs of the search key value.
19. The ternary CAM device of claim 16 , wherein:
the bits of the search key value have an order of increasing significance with respect to one another; and
the at least first encoder logically combines bit pairs adjacent to one another in the order of significance in a non-overlapping manner to generate two additional bit values for each bit pair of the search key, such that E=W.
20. The ternary CAM device of claim 16 , wherein:
the bits of the search key value have an order of increasing significance with respect to one another; and
the at least first encoder logically combines bit pairs adjacent to one another in the order of significance in an overlapping manner to generate two additional bit values for each bit pair of the search key, such that E=2(W−1).