Browse Prior Art Database

Single Byte Error Correcting and Double Byte Error Detecting Codes

IP.com Disclosure Number: IPCOM000046880D
Original Publication Date: 1983-Aug-01
Included in the Prior Art Database: 2005-Feb-07
Document File: 3 page(s) / 37K

Publishing Venue

IBM

Related People

Chen, CL: AUTHOR

Abstract

A two bit-byte single byte correction and double byte detection (SBC-DBD) code with 70 data bits and 10 check bits can be shortened to become a (74,64) code. Using the terminology of coding theory, an SBC-DBD code with b bits per byte is a linear code over the finite field GF(2b) with a minimum distance 4. The code can be defined as the null space over GF(2b) of a parity check matrix. A necessary and sufficient condition for being a distance 4 code is that any linear combination of 3 or fewer number of the column vectors in the parity check matrix is linearly independent. Let N and R be the code length in bytes and the number of check bytes of an SBC-DBD code.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 56% of the total text.

Page 1 of 3

Single Byte Error Correcting and Double Byte Error Detecting Codes

A two bit-byte single byte correction and double byte detection (SBC-DBD) code with 70 data bits and 10 check bits can be shortened to become a (74,64) code. Using the terminology of coding theory, an SBC-DBD code with b bits per byte is a linear code over the finite field GF(2b) with a minimum distance 4. The code can be defined as the null space over GF(2b) of a parity check matrix. A necessary and sufficient condition for being a distance 4 code is that any linear combination of 3 or fewer number of the column vectors in the parity check matrix is linearly independent. Let N and R be the code length in bytes and the number of check bytes of an SBC-DBD code. Suppose that the parity check matrix of the code over GF(2b) can be expressed in the form

(Image Omitted)

where the first row is an N-component all 1's vector, and M is an (R-1) x N matrix whose elements are in GF(2b). Assume that the binary code defined by the null space of M has a minimum distance greater than 3. Then the code over GF(2b) defined by the following parity check matrix H is an SBC-DBD code,

(Image Omitted)

wheref= 2c-1, Qi = c x N matrix with identical columns, each column being a binary representation of integer i. The code defined by H has a code length of N $ f = N $ (2c-1) with R c-1 check bytes. Now suppose there is an SBC-DBD code with c check bytes and code length n. Let p be the c x n parity check matrix for the code, and each column of P is not a scalar multiple of a binary vector. Define the matrix

(Image Omitted)

where O(R-1) x n is an (R-1) x n matrix with all 0's elements. Then the code over GF (2b) in the null space of H' is an SBC-DBD code. The code length is N(2c-1) + n, and the number of check bytes is R+c-1. For b = 2, let

(Image Omitted)

where W is an element of GF(4), and W2 + W + 1 = 0. The code over GF(4) with the parity check matrix

(Image Omitted)

can be shown to be an SBC-DBD code with N=5, R=3. Furthermore, the binary code defi...