As emerging memories are utilized in processors as main memory, they must also coexist with CMOS memories; for instance SRAMs, are used to implement smaller, but faster associative memories. These hybrid designs exploit the advantages of both types of memories to achieve better performance. For some applications, the improvement in performance for on-chip associative memories is crucial for the overall computing system. For CMOS memories, soft errors are a major concern because they flip bits and can lead to data corruption and even a system failure. Error Detection and Correction Codes (EDCCs) are commonly used to protect memories against soft errors. In associative memories, an entry is formed by a tag and its associated data (or value). EDCCs are typically used to separately protect the tag and the data. This paper considers the protection of associative memories in which false negatives do not cause a failure. A Combined Tag and Data Parity (CTDP) protection scheme is proposed. This new approach utilizes a single parity bit per entry, so it reduces the number of parity bits needed to protect an entry as well as the memory size. The proposed scheme also reduces the complexity of read operations; it incurs the lowest circuit overhead for the protection circuitry in terms of area, delay and power consumption when compared to other schemes found in the technical literature. This makes the proposed scheme germane to associative memories used in hybrid designs that combine SRAMs and emerging memories. The extension of the proposed scheme to stronger codes is also discussed.