Browse Prior Art Database

Cumulative Error Detector

IP.com Disclosure Number: IPCOM000103823D
Original Publication Date: 1993-Feb-01
Included in the Prior Art Database: 2005-Mar-18
Document File: 2 page(s) / 69K

Publishing Venue

IBM

Related People

Coppersmith, D: AUTHOR [+2]

Abstract

Disclosed is an error detection scheme which detects, among others, two arbitrary bit errors and any burst error of length at most seven. It is designed for a channel constrained to transmit blocks of data with too few parity-check bits per block for standard error detection schemes to succeed. The invention proposes a method which does not guarantee that an error in a given block is detected right after the processing of that block, but is guaranteed to be detected after several blocks are processed. The invention is described with a preferred embodiment, detecting, among others, arbitrary 2 bit-errors.

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

Cumulative Error Detector

      Disclosed is an error detection scheme which detects, among
others, two arbitrary bit errors and any burst error of length at
most seven.  It is designed for a channel constrained to transmit
blocks of data with too few parity-check bits per block for standard
error detection schemes to succeed.  The invention proposes a method
which does not guarantee that an error in a given block is detected
right after the processing of that block, but is guaranteed to be
detected after several blocks are processed.  The invention is
described with a preferred embodiment, detecting, among others,
arbitrary 2 bit-errors.

      The method operates on 96-bit blocks consisting of 92
information bits and 4 parity bits.  Considering the 96-bit block to
be composed of 16 6-bit 6-tuples, an error will mean one or more bits
within one 6-tuple incorrectly received.  A single error will be
detected by the time two additional blocks are received and decoded,
provided no other errors occur in the meantime.  If a second error
does occur in the meantime, the error will still be detected by the
time two additional blocks following the second error are received
and decoded, proved no additional errors occur in the meantime.  If a
third error does occur within these two additional blocks, all errors
may go undetected.  No attempt is made to correct the errors.

      At the beginning of transmission, the sender initializes 6-bit
accumulators E and F to 0, and the receiver initializes 6-bit
accumulators E hat and F hat to 0.  Then for each 96-bit word M, the
following processing takes place.

      Sender.  Represent the 92 information of M as 15 6-tuples m sub
15 , m sub 14 , ...  , m sub 1 , with two bits remaining.  Let the
6-tuple m sub 0 be these two bits concatenated with four 0 bits.  For
each j = 15 , 14 , ...  , 0, do the operations

    E larrow C * E + m sub j , '     '  F larrow D * F + m sub j ,
with all arithmetic begin done in the field of two elements, GF(2).
These operations will be called "cumulative summations."  For each
j=15,14, ...  , 1, set m prime sub j = m sub j .  Form the 6-tuple <
m prime > sub 0 from m sub 0 by replacing the fourth and sixth bits
with the fourth an...