In-line wire error correction
AssigneeHewlett-Packard Development Company, L.P.
InventorDebendra Das Sharma
Life of this patent
Estimating the term…
Abstract
An error correction scheme for transmission of electronic data using an in-line error correction where there are no explicit wires for error correction code (ECC) bits. A method for in-line error detection and correction is described which uses 0 to k wires, and symbols 0 to n, where information bits and symbols are sent along wires 0 to k. Before sending an information block along wires 0 to k, check bits are calculated from the information bits, wherein the check bits are made up of horizontal parity, extended parity and overall parity of the information. The check bits are sent along wires 0 to k, using the same wires as for the information bits.
Claims8
A method for in-line error detection and correction using wires 0 to k−1, and symbols 0 to n, said method comprising steps of:
- calculating a horizontal parity (HP[i]) for i=0 to n−2, where n is a number of symbols used, and
- HP
-
- [
- i
- ]
- =
- ⊕
- k
- -
- 1
- x
- =
- 0
-
- b
-
- [
- x
- ]
-
- [
- i
- ]
- ,
- and k is a number of wires used;
- calculating an extended parity
- (
- EP
- )
- =
- ∑
- x
- =
- 0
- k
- -
- 1
-
-
- ∑
- y
- =
- 0
- n
- -
- 1
-
-
- b
-
- [
- x
- ]
-
- [
- y
- ]
-
- α
- (
- x
- +
- y
- +
- B
- )
- ,
- where B a degree of primitive polynomial+1 and a number of bits in a syndrome;
- sending contents of the horizontal parity along wire 0 of k wires, where HP[0] is in symbol 0, HP[1] is in symbol 1, . . . , HP[n−2] is in symbol n−2;
- calculating an overall parity (OP) where the OP is an exclusive-or of the horizontal and extended parities;
- sending check bits along the wires in symbol 0, wherein the check bits comprise the extended parity, the horizontal parity and the overall parity;
- sending information bits in symbols 1 . . . n−1, wherein symbol[i] carries bits b[k−1 . . . 0][i];
- determining whether check bits have an error;
- calculating a syndrome 0 and a syndrome 1, wherein syndrome 0 is a B-bit quantity {eB−1, . . . , e2, e1, e0} such that
- e
-
- [
- i
- ]
- =
- ⊕
- k
- x
- =
- 0
-
- b
-
- [
- x
- ]
-
- [
- i
- +
- 1
- ]
- ⊕
- HP
-
- [
- i
- ]
- ,
- where HP[i]=b[i+1][0 . . . 7], and wherein syndrome 1 is a summation of the extended parity and seven degree polynomial;
- determining whether bit i in wire j contains an error;
- and
- if bit i in wire j contains an error, then fixing the bit error by flipping the erroneous bit.
A method for in-line error detection and correction using wires 0 to k−1, and symbols 0 to n, where information bits and symbols are sent along wires 0 to k, said method comprising steps of:
- calculating check bits from information bits, wherein the check bits comprise horizontal parity, extended parity and overall parity of the information;
- sending the check bits along wires 0 to k−1, wherein information is sent along the same wires;
- determining whether an error exists in the sent information using syndromes generated from the check bits, wherein syndrome 0 is obtained from the horizontal parity (HP) bits by taking an exclusive-OR (XOR'ing) of the information bits with the HP bits and wherein syndrome 1 comprises a degree n−1 polynomial;
- and
- correcting single wire errors determined using the syndromes.
An apparatus for in-line error detection and correction using wires 0 to k−1, and symbols 0 to n, comprising:
- an encoder for calculating a horizontal parity (HP), extended parity (EP) and overall parity (OP) for information bits, wherein the horizontal parity (HP[i]) for i=0 to n−2, where n is a number of symbols used, and
- HP
-
- [
- i
- ]
- =
- ⊕
- x
- =
- 0
- k
-
- b
-
- [
- x
- ]
-
- [
- i
- ]
- ,
- and k is a number of wires used, and wherein the extended parity
- (
- EP
- )
- =
- ∑
- x
- =
- 0
- k
- -
- 1
-
- ∑
- y
- =
- 0
- n
- -
- 1
-
- b
-
- [
- x
- ]
-
- [
- y
- ]
-
- α
- (
- x
- +
- y
- +
- B
- )
- ,
- where B a degree of primitive polynomial+1 and a number of bits in a syndrome, and wherein the overall parity (OP) is an exclusive-or of the HP and the EP;
- means for sending the information bits and calculated parity bits across wires 0 to k, wherein check bits are sent along the wires in symbol 0, wherein the check bits comprise the extended parity, the horizontal parity and the overall parity, and wherein information bits are sent in symbols 1 . . . n−1, where symbol[i] carries bits b[k−1 . . . 0][i], and wherein horizontal parity (HP) is sent along wire 0, where HP[0] is in symbol 0, HP[1] is in symbol 1, . . . , HP[n−2] is in symbol n−2;
- means for determining whether check bits have an error, comprising decoder for calculating a syndrome 0 and a syndrome 1, wherein syndrome 0 is a B-bit quantity {eB−1, . . . , e2, e1, e0} such that
- e
-
- [
- i
- ]
- =
- ⊕
- x
- =
- 0
- 17
-
- b
-
- [
- x
- ]
-
- [
- i
- +
- 1
- ]
- ⊕
- HP
-
- [
- i
- ]
- ,
- where HP[i]=b[i+1][0 . . . 7], and wherein syndrome 1 is a summation of the extended parity and seven degree polynomial;
- and
- means for fixing bit errors determined by the determining means.
An apparatus for in-line error detection and correction using wires 0 to k−1, and symbols 0 to n, comprising:
- an encoder for calculating check bits from information bits, wherein the check bits comprise horizontal parity, extended parity and overall parity of the information;
- a transmitter for sending the check bits along wires 0 to k−1, wherein information is sent along the same wires;
- means for determining whether an error exists in the sent information using syndromes generated from the check bits, wherein syndrome 0 is obtained from the horizontal parity (HP) bits by taking an exclusive-OR (XOR'ing) of the information bits with the HP bits and wherein syndrome 1 comprises a degree n−1 polynomial;
- and
- error correction component for correcting single wire errors determined using the syndromes.
Dependencies are inferred from the claim text.