Range representation in a content addressable memory (CAM) using an improved encoding scheme
View Patent ↗In a method and apparatus for encoding a bit field within a memory device, the bit field is encoded in a manner that requires fewer memory device entries and fewer encoded bits per entry than conventional encoding schemes.
1. A method of operation within a packet processing device, the method comprising:
receiving first and second k-bit values that bound a range of values; and
encoding the range bounded by the first and second k-bit values into an encoded value having not more than 2 k −1 bits, wherein encoding the range bounded by the first and second k-bit values into an encoded value comprises:
(i) assigning a first number of bits in a first logic state to be left-justified bits of the encoded value, the first number of bits corresponding to the lower of the first and second k-bit values;
(ii) assigning a second number of bits in the first logic state to be right-justified bits of the encoded value the second number of bits being 2 k −1 less the higher the first and second k-bit values; and
(iii) assigning a third number of bits in a masked state to be contents of the encoded value between the left-justified and right-justified bits of the encoded value, the third number of bits being the difference between the first and second k-bit values, plus one.
2. The method of claim 1 further comprising storing the encoded value within a first entry in a ternary content addressable memory (CAM) device.
3. The method of claim 1 further comprising:
receiving a search value within the ternary CAM device;
encoding a k-bit field within the search value to form an expanded search value having at least an additional 2 k −1 bits; and
comparing the expanded search value with entries, including the first entry, within the TCAM device.
4. The method of claim 1 wherein assigning a first number of bits in the first logic state comprises assigning the first number of bits in a logic ‘0’ state.
5. The method of claim 1 wherein each of the first and second k-bit values is part of a respective M-bit value, where M>k.
6. The method of claim 1 wherein the first and second k-bit values are 2-bit values.
7. A method of operation within a content addressable memory (CAM) device, the method comprising:
encoding at least one group of k bits within a search value into an encoded bit field within an encoded search value, the encoded bit field having 2 k −1 bits wherein encoding the at least one group of k bits into an encoded bit field having 2 k −1 bits comprises:
assigning a first number of bits in a first logic state to be left-justified bits of the encoded bit field, the first number of bits corresponding to the numeric value represented by the k bits; and
assigning a second number of bits in a second logic state to be right-justified bits of the encoded bit field, the second number of bits being 2 k −1 less the first number of bits; and
comparing the encoded search value with data stored within the CAM device.
8. The method of claim 7 further comprising receiving a value that indicates a position of the at least one group of k bits within the search value.
9. The method of claim 8 further comprising storing the value that indicates the position within a programmable register of the CAM device.
10. The method of claim 7 further comprising receiving a value that indicates the number of bits, k, within the at least one group of k bits.
11. The method of claim 10 further comprising storing the value that indicates the number of bits, k, within a programmable register of the CAM device.
12. The method of claim 7 , wherein the first logic state is a logic ‘0’ state and the second logic state is a logic ‘1’ state.
13. A content addressable memory (CAM) device comprising:
a key expansion circuit to receive a search value and to encode at least one group of k bits within the search value into an encoded bit field within an encoded search value, the encoded bit field having 2 k −1 bits, wherein the key expansion circuit comprises circuitry to assign a first number of bits in a first logic state to be left-justified bits of the encoded bit field, and a second number of bits in a second logic state to be right-justified bits of the encoded bit field; and
a CAM array coupled to receive the encoded search value and having a plurality of CAM cells to store data and to compare the data to the encoded search value.
14. The CAM device of claim 13 further comprising a configuration register to store a value that indicates a position of the at least one group of k bits within the search value.
15. The CAM device of claim 13 further comprising a configuration register to store a value that indicates the number of bits, k, within the at least one group of k bits.
16. The CAM device of claim 13 wherein the first logic state is a logic ‘0’ state and the second logic state is a logic ‘1’ state.
17. A content addressable memory (CAM) device comprising:
means for receiving a search value and encoding at least one group of k bits within the search value into an encoded bit field within an encoded search value, the encoded bit field having 2 k −1 bits, wherein encoding at least one group of k bits within the search value comprises:
assigning a first number of bits in a first logic state to be left-justified bits of the encoded bit field; and
assigning a second number of bits in a second logic state to be right-justified bits of the encoded bit field; and
means for storing data and comparing the data to the encoded search value.
18. Computer-readable media having information embodied therein that includes a description of a content addressable memory (CAM) device, the information including descriptions of:
a key expansion circuit to receive a search value and to encode at least one group of k bits within the search value into an encoded bit field within an encoded search value, the encoded bit field having 2 k −1 bits, wherein the key expansion circuit comprises circuitry to assign a first number of bits in a first logic state to be left-justified bits of the encoded bit field, and a second number of bits in a second logic state to be right-justified bits of the encoded bit field; and
a CAM array coupled to receive the encoded search value and having a plurality of CAM cells to store data and to compare the data to the encoded search value.