Browse Prior Art Database

A Compact Encoding Scheme

IP.com Disclosure Number: IPCOM000044779D
Original Publication Date: 1984-Aug-01
Included in the Prior Art Database: 2005-Feb-06
Document File: 2 page(s) / 14K

Publishing Venue

IBM

Related People

Frey, AH: AUTHOR

Abstract

In the prior art, data is encoded in two 16-bit code words each containing eight bits of data and eight bits of redundancy. The properties of the code are such that if there were nine bits of data and eight bits of redundancy (an additional data bit), the redundant code would be capable of correcting any single or double error in the 17 bits. The 17th bit is not now part of the 16 bits encoded. The code structure is repeated twice together to form 32 bits, 16 bits of data in two bytes, each byte encoded with an additional byte of redundancy to form a half-rate code.

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

Page 1 of 2

A Compact Encoding Scheme

In the prior art, data is encoded in two 16-bit code words each containing eight bits of data and eight bits of redundancy. The properties of the code are such that if there were nine bits of data and eight bits of redundancy (an additional data bit), the redundant code would be capable of correcting any single or double error in the 17 bits. The 17th bit is not now part of the 16 bits encoded. The code structure is repeated twice together to form 32 bits, 16 bits of data in two bytes, each byte encoded with an additional byte of redundancy to form a half-rate code.

It would be useful to find a 17th bit of information from a novel way of encoding the redundancy without substantially detracting from the error correcting capability of the code. The code now fails any time when three errors occur within a 16-bit word. A new method presented here will only fail when two errors occur in both of the 16-bit words, that is, four errors in the 32 bits of the two words or three errors in any one of the two words. However, the method will not be able to correct four errors, two of which occurred in each word. But since the probability of getting such a four-error pattern is far less than the probability of getting a three-error pattern, the disclosed method is a practical improvement.

To get the extra information bit, make the assumption that the bit is being sent in both words. It is either a one or a zero. Suppose the bits were numbered from zero to 15 with zero being the low order redundancy bit and 15 being the high order data bit. Add an additional high order data bit - bit number 16 - to each word and make it have the same value in the encoding of both words. That bit will be decoded as the 17th information bit. It will be the same in both words. The bit is not actually transmitted, but it is encoded in both words. Then at the receiving end, decode it as if it were a zero. Since it was not transmitted, the receiver does not know what it was. Assume that it was a zero and decode it. If it was a one, an error indication will occur. If there is another error in the word, two error indications will occur. If there is still another error i...