Error Detection Codes for Arbitrary Errors Modeled by Error Graphs

Abstract:
In this paper arbitrary combinational errors are modeled by an error graph. The vertices of the error graph are n-tuples with q-ary components, and two vertices v and v' are connected by an edge from v to v' if the n-tuple v is changed by an combinational error into v'. If the error occurs with a known probability or frequency this can be modeled by weighted edges of the error graph. It is shown how an optimal error detecting code with m = 1 check bits and k = n – m data bits can be determined from the error graph. For a small number of n an optimal solution can be computed. For larger numbers of n an efficient heuristic is proposed. As an example retention errors of multi-level NAND flash memory cells are modeled and the heuristic is used to determine efficient error detection codes. The new codes are compared with error detection codes for unidirectional errors with a limited magnitude by experimental results.