A method is described that includes reading a cache tag and the cache tag's corresponding ECC from storage circuitry of a cache. The method also includes generating an ECC for a search tag. The method also includes calculating a hamming distance between a) the cache tag and its corresponding ECC and b) the search tag and its corresponding ECC. The method also includes determining if the cache tag matches the search tag by comparing the hamming distance against a threshold.