| I'm unsure of the details of a burst error-correcting code; I thought
there were a wide variety of them. Here I go with meager information,
but I think you'll find it useful.
You should be able to construct a burst error-correcting code that
corrects any error of length b or less, with the property that any
error of length b+1 generates a k-bit correction pattern. Just take
a code that corrects errors of length b+1 or less, and change it so
that, instead of correcting errors of length (exactly) b+1, it simply
toggles k bits (you can choose the k). Such a code is not particularly
useful, but should illustrate that you can't prove something about the
length of the computed correction patterns for errors greater than b.
I thik some progress could be made, knowing more information about the
particular burst error-correcting code. Or, if it can be assumed that
amoung all the 2^(b+1) words having a string of b+1 'dont-care' bits at
a certain place in the word, there is at least one error-free word,
then I think you can construct errors of length > b that have computed
correction patterns of any desired length.
In a reasonable error correcting code, I'd expect the correction patterns
for errors greater than what can be detected to be fairly randomly distributed
amoung the possible correction patterns.
How does some workstation driver code depend on this?
|
| If the burst-error-correcting code you're talking about is a cyclic
code, which it probably is, you can say the following things.
The messages are n-bit blocks. Regard the bits as coefficients
of a polynomial of degree at most n-1.
A message is interpreted as error-free if it is a multiple of the
CRC (generator, really) polynomial, modulo x**n-1. Let the
generator polynomial have degree r.
There are 2**n possible error patterns. (No bits in error up to
all bits in error.) 2**(n-r) of them are multiples of the
generator, 2**(n-r) are congruent to 1, and so on for each of
the possible 2**r remainders when a polynomial of degree n (the
message) is divided by one of degree r (the generator).
The procedure for correcting a burst error assigns one error
pattern to each residue class. Each residue class has 2**(n-r)
error patterns in it. At most one of the error patterns is
a burst of up to b bits.
If the residue class of the recieved message is 0, the algorithm
says "the message was recieved correctly". If the residue class
contains one burst pattern, the algorithm tells you what it is.
If the residue class contains no burst patterns, the algorithm
says that a non-burst error was detected, or at least it has the
info needed to say that.
So if you look at all 2**n possible errors, you can say that 2**(n-r)-1
of them produce undetected errors, and every correction action is
provoked by some 2**(n-r) messages. If two messages provoke the
same correction action, they differ by a multiple of the generator.
(Modulo x**n-1.) (So, for instance, if you have error patterns A
and B which differ in only 1 bit, they won't produce the same
correction pattern -- the 1 bit difference is x**t for some t, and
that's not a multiple of sensible generator polynomials which are
odd.)
If you care particularly about error patterns that are bursts of
b+1, b+2, ... bits, you can figure out what error correction actions
are invoked by the convenient fact that, since 0 is a valid message
and it's all linear, feeding the error pattern to the correction
algorithm tells you what it will do when a message with that error is
received.
|
| Further, the 2**(n-r) error patterns that are interpreted as
being error-free are exactly the 2**(n-r) valid messages. Ie, if
you XOR any two valid messages, you get a valid message -- if both
are multiples of the generator g(x), so is their sum. [Always in
the ring of mod-2 polynomials modulo x**n-1.]
And if a given message is interpreted as having a particular b-bit
error, then XORing in any valid message will produce a message that
will be interpreted as having the same b-bit error.
(The thing that makes the code capable of correcting b-bit errors
is that no 2 b-bit bursts XORed together are a valid message. So
that if a b-bit burst error does occur, it can be identified.)
So, in your specific example, assume we can find a valid message
with the form
......... xxxxxxx .......... xxxxxxxxx ...........
of a 7-bit burst XORed with a 9-bit burst. Then, if the 9-bit
burst error happens, it will be corrected as if the 7-bit error
had happened.
First thing: the 9-bit burst overlaps the 7-bit burst by at most
1 bit; otherwise it would be the sum of 2 7-bit bursts and could
not be a valid message in a 7-bit error correcting code.
Second thing: any valid message, rotated one bit, is a valid message.
This is why cyclic codes are called that, and is because a bit
shifted off the left corresponds to x**n which is 1 modulo x**n-1.
So, to find these messages when they exist, take the 7-bit error
pattern you want to provoke, stick it with leading zeros into a
block of n-r bits, and compute the r-bit checksum. If the checksum
is contained within 9 of the r bits, rotate the 7-bit pattern into
the desired position and cause the corresponding 9-bit error. If the
checksum didn't fit in 9 bits, shift the message left 1 and try again.
You get n-r-6 tries each with a shot of something like (r-8)*.5**(r-9).
If you're feeling thorough, complement the low bit of the 7-bit
pattern and check for an adjacent 8-bit checksum, then try it left
justified and check for a right-justfied 8-bit checksum -- to catch
the 1-bit overlap cases.
If no 9-bit checksum is found, then no 9-bit error can cause that
7-bit correction, since all error patterns that would provoke it
have been seen to span more than 9 bits.
Clearly if an r-bit burst were sought instead of a 9-bit burst,
it could always be found, so you can fake any 7-bit error with an
r-bit error. (This is trivial, since you can set the checksum to
anything you want with an r-bit error.)
There are 2**r possible checksums, and if there are close to
2**r possible b-bit burst errors, it's clear that about any checksum
will be construed as some b-bit error. So in that case the >b-bit
fake errors should be very easy to come by.
|