Error detection and error correction algorithm

Suppose we have a chunk of data that came from data transfer medium with the following properties:

• Total chunk size is 8 bytes.
• The data transfer is unreliable, so errors in a number of bits are possible.
• The data transfer is cyclic and the beginning of the chunk is unknown. For example, the code 0123456789ABCDEF is the same as 3456789ABCDEF012 (0123456789ABCDEF << 12) and 02468ACF13579BDE (0123456789ABCDEF << 1). The receiver end should determine the beginning by the code itself.

What are the best error detection and error correction algorithms for this case? Of course, it's always a compromise between useful data amount per chunk and success validation (correction) probabilit开发者_JS百科y.

Here is an attempt with some ideas pinched from http://en.wikipedia.org/wiki/Frame_Relay.

Start off each 64-bit chunk with a fixed header of 01110. Where you have more header info (e.g. sequence number or alternating bit flag, checksum...) you can probably arrange that the bit-pattern 01110 never appears. For arbitrary data, replace any occurrence of 0111 with 01111 - meaning that the effective data rate now depends on the underlying data. Have the provider of data to this layer make sure the data is pretty much random, e.g. by applying a http://en.wikipedia.org/wiki/Randomizer. I think your total data loss here is about 6 bits, which fits with the 6 bits necessary to describe a shift of 0..63.

In the receiver, look for 01110 to mark the true start of the chunk. If you do not see exactly one such pattern, you know that the chunk has been garbled. I think it takes at least a two-bit error to both destroy an existing 01110 and produce a fake one.

Garbles that cause chunk misalignment don't look like typical bit garbles, so CRC error rate calculations won't apply out of the box. I would include a non-CRC checksum in each chunk - perhaps a check calculated mod 31 or mod 961 so as to avoid the forbidden 5-bit pattern 01110, although depending on what abuts this you may need to be more restrictive. The chance of an error not being detected would then be about 1 in 31 or 1 in 961, with no particular guarantee about all single errors, unlike polynomial CRC.

I don't think you have enough space to do per-chunk error correction sensibly, but you could include N error correction chunks after every M ordinary chunks, using e.g. SECDED applied down the columns. You might have e.g. 57 data-bearing chunks and then 6 error correction chunks, treating each payload bit position as bearing 57 data bits and then 6 checksum bits. This should work well if errors tend to corrupt all or none of a single chunk e.g. by causing chunk realignment to fail.

after comment -

EDIT

OK, with one continuously transmitting message you have less bandwidth but relatively more cpu. Two things come to mind:

1) Given any sort of checksum or other constraint on the message you can achieve some limited error correction by e.g. considering all single bit errors, flipping a bit of the received message, and seeing if the checksum now works.

2) A message can be checked to see if complies with the bit-stuffing scheme suggested above by looking at only a 5-bit window passed over the message. I think this holds true even if you need to tweak it to work properly at the wraparound. This means that a message can be checked by a BDD of tractable size (Knuth 4A section 7.1.4). This means that you can count the number of 64-bit messages that comply with the bit-stuffing scheme and convert efficiently between message number and message (same section). So you can use this scheme without underlying randomisation or worst-case assumptions about the data to be sent, by just regarding it as an encoding of a number in the range 0..N (where N is to be computed via BDDs) and a 64-bit message. In fact, less elegantly, I think you could use dynamic programming with a 5-bit state instead of BDDs.

This is only a partial answer to the full question as I will not answer how to determine the start point. Refer to mcdowella's answer for that. I intended this to be a comment, but it's too long.

With a continuously transmitted message, there really is no need for any error-correction anymore. Even if a one bit-flip (or a bunch of them) occurs, it's unlikely it will affect every single instance of the same bit being transmitted - especially if it's being repeated forever. So in this sense, your redundancy factor is N where N approaches infinity as the broadcast goes on.

So reconstructing your 64-bits is now very easy since you have many samples to look at. Assuming the receiver knows the cycle length, you can just poll the stream and count how many occurrences of each bit for each of the 64 positions.

So say after 100 complete cycles, you get:

Bit #    0s / 1s    Interpret bit as
Bit 0:  100 /   0        0
Bit 1:    0 / 100        1
Bit 2:   99 /   1        0
Bit 3:   98 /   2        0
Bit 4:    1 /  99        1
...
Bit 63:  96 /   4        0

Based on these samples, you can statistically figure out what the correct bit values are. The longer the receivers continues to receive the cycle, the stronger your bounds are. So you can tolerate an arbitrarily high error-rate if enough cycles are transferred.

Of course this applies to any cycle length - not just 64-bits. So combine this method with mcdowella's (and the data size will probably increase due to the index-foot-print).

If the cycle period isn't known to the receiver, there are two ways to figure it out:

1. Guess the length and run the polling. Keep doing this for different lengths until you get a length with a very high correlation. (high confidence levels for each of the bits)

2. Perform a Fourier Transform on the received data. This will instantly reveal the period assuming the data isn't too ridiculously noisy.

print("-"*25,'CHECKSUM ERROR DETECTION MECHANISM',25*'-')
print("\n",25*"-","At Sender's Side","-"*25,"\n") 
data_bits = input('Enter the Data Bits : ')
checksum_bits = int(input("Enter number of checksum bits: "))
sum="0"
sum = int(sum,2)
for i in range(0, len(data_bits), checksum_bits):
    part_i = data_bits[i: i + checksum_bits]
    print("The Data Part : ",part_i)
    part = int(part_i,2)
    sum = sum+part
binary_sum = bin(sum)
finalsum = binary_sum[2:]
if len(finalsum)==checksum_bits:
    finalsum = finalsum
else:
    finalsum = binary_sum[3:]
def Convert(string):
    list1=[]
    list1[:0]=string
    return list1
final_sum = Convert(finalsum)
def complement(s):
    for i in range (0,len(s)):
      if s[i] == '1':
       s[i] = '0'
      else:
       s[i] = '1'
complement(final_sum)
def convert(s):
    checksum = ""
    return (checksum.join(s))
checksum = convert(final_sum)
print("The Checksum Calculated is: ",checksum)
codeword = data_bits + checksum
print('The Transmitter sequence will be: ',codeword)
print("\n",25*"-","At Receiver's Side","-"*25,"\n")
data_bits1 = input('Enter the Data Bits : ')
checksum_bits1 = int(input("Enter number of checksum bits: "))
sum1="0"
sum1 = int(sum1,2)
for i in range(0, len(data_bits1), checksum_bits1):
    part = data_bits1[i: i + checksum_bits1]
    parts = int(part,2)
    print("The Data Part: ",part)
    sum1 = sum1+parts
    binarysum = bin(sum1)
    finalsum1 = binarysum[2:]
if len(finalsum1)==checksum_bits1:
    finalsum1 = finalsum1 
else:enter code here
    finalsum1 = binarysum[3:]
    final_sum1 = Convert(finalsum1)
    complement(final_sum1)
    value = convert(final_sum1)
print("The Computed Received Sequence: ",value)
if final_sum1.count('1')>0:
    print("This is an Errored Message...Please try Transmitting the Message again.")
else:
    print("The Transmitted Sequence was Received Successfully with no Error Present.")
print("\n",30*"-","DONE","-"*30,"\n")