Technical Report CS0955

Title: Optimal Codes for Single-Error-Correction, Burst of Length 2 Error-Detection/Correction
Authors: Marina Biberstein and Tuvi Etzion
Abstract: In certain memory systems the most common error is a single error and the next most common error is two errors in positions which are stored physically adjacent in the memory. In this paper we present optimal codes for recovering such errors. We correct single errors and either detect or correct double adjacent errors. For detecting adjacent errors we consider codes which are byte-organized. In the binary case it is clear that the length of the code is at most $2^r -r-1$, where $r$ is the redundancy of the code. We show that if the size of a byte is $b$, where $b$ divides $2^r - r-1$, ${{2^r -r-1} \over b} \geq r-1$, and $b < 2^{\lfloor {r/2} \rfloor} -2$ then a code of length $2^r -r-1$ exists. For the nonbinary case we show another bound, called "the pairs bound", on the length of such code. Over $GF(3)$ codes with bytes of size 2,which attain the bound exist if and only if perfect codes with minimum Hamming distance 5 over $GF(3)$ exist. Over $GF(4)$ codes which attain the bound with byte size 2 exist for all redundancies. For most other parameters we prove the nonexistence of codes which attain the bound. For correcting a burst of length 2 we present five perfect codes for redundancies 5, 6, 7, 8, and 9 and a construction of perfect codes organized in bytes of sizes 3, 16, 32, 64, 128, and 256, for each redundancy $r$ divisible by 4, 5, 6, 7, 8, and 9, respectively.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1999
To the main CS technical reports page

Computer science department, Technion