Browse Prior Art Database

Run Length Coding with Error Correcting Code

IP.com Disclosure Number: IPCOM000076224D
Original Publication Date: 1972-Jan-01
Included in the Prior Art Database: 2005-Feb-24
Document File: 2 page(s) / 13K

Publishing Venue

IBM

Related People

Bossen, DC: AUTHOR [+2]

Abstract

A small amount of nonlinearity can be added to a linear error correcting code together with a judicious distribution of check bits, with the result that the run-length property is automatically achieved. A 64-bit single-error correction double-error detection (SEC-DED) linear code with 8 check bits will be used as an example, although the procedure is general. The idea is to perform a mapping on the 8 check bits, so that each pair of bits in the resultant sequence of bits has at least a single 1 bit. Then these pairs of bits can be distributed through the data portion so that a run length is guaranteed, together with error correction.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 54% of the total text.

Page 1 of 2

Run Length Coding with Error Correcting Code

A small amount of nonlinearity can be added to a linear error correcting code together with a judicious distribution of check bits, with the result that the run- length property is automatically achieved. A 64-bit single-error correction double- error detection (SEC-DED) linear code with 8 check bits will be used as an example, although the procedure is general. The idea is to perform a mapping on the 8 check bits, so that each pair of bits in the resultant sequence of bits has at least a single 1 bit. Then these pairs of bits can be distributed through the data portion so that a run length is guaranteed, together with error correction.

Let the check bits be separated into groups of 3 bits each. For 8 check bits there are three such groups, where the third groups have only 2 bits. Now, each group of 3 bits can be coded with 2 ternary symbols. The natural such map is given in Table 1. Binary Ternary b.c.t. 0 0 0 0 0 0 1 0 1 0 0 1 0 1 0 1 1 0 0 1 0 0 2 0 1 1 1 0 1 1 1 0 1 0 0 1 1 0 0 1 1 1 0 1 0 1 0 1 1 2 1 0 1 1 1 1 0 2 0 1 1 0 1 1 1 1 2 1 1 1 1 0 T:ABLE 1.

If the ternary symbols 0, 1, and 2 are further coded in binary as 0 = 01, 1 = 10, and 2 = 11, then the column b.c.t. (binary-coded ternary) results. Applying this code to the 8 check bits of the (72,64) SEC-DED code, a group of 12 bits results. These 12 bits consist of six pairs of bits which have the property that each pair contains at least a single 1 bit. These six pairs are then distributed across the data to yield a run length [64* over 6] + 2 = 13.

In order to preserve the error-correcting code (ECC) capability after run length decoding of the check bits, the following considerations are necessary.

1) A s...