Integrated circuits with memory circuitry may include error detection circuitry and error correction circuitry. The error detection circuitry may be used to detect soft errors in the memory circuitry. The error detection circuitry may include logic gates that are used to perform parity checking. The error detection circuitry may have an interleaved structure to provide interleaved data bit processing, may have a tree structure to reduce logic gate delays, and may be pipelined to optimize performance. The memory circuitry may be loaded with interleaved parity check bits in conjunction with the interleaved structure to provide multi-bit error detection capability. The parity check bits may be precomputed using design tools or computed during device configuration. In response to detection of a memory error, the error correction circuitry may be used to scan desired portions of the memory circuitry and to correct the memory error.