Error-Correcting Codes for Ternary Content Addressable Memories

摘要

As VLSI silicon technology continues its relentless advance and memory densities increase, the problem of soft errors--bit upsets caused by alpha particles or neutron hits--demands solutions. Error-correcting codes (ECCs) are routinely used on random-access memories (RAMs) to increase soft error tolerance--codewords (CWs) (ECC bits concatenated to the data) are written to and read from memory, and the read CW is decoded to correct errors. Content addressable memories (CAMs) also demand error mitigation measures. The method employed for RAMs is also applicable to CAMs: the match-line sense amplifier is modified to function as a comparator [1], CWs are stored and searched for. We investigate the extension of this method to ternary CAMs (TCAMs). TCAMs cannot employ the efficient ECCs (known as linear block codes-LBCs) used with RAMs and CAMs. We develop the ECCs necessary to implement error-resilient TCAMs. We prove that the rate (ratio of data bits to total number of bits in the CW) of the specialized ECCs necessary for TCAMs cannot exceed 1/t, where t is the number of bit errors the code can correct (in contrast, LBCs asymptotically have rate one); simple majority codes are the best.