Shortest Error Correcting Code?

[GMarco]

Hi,

I want to solve the followin task:

1. Given is a data string of m bits length.
2. Derive a checksum of the length k, k as short as possible
3. flip one single bit at randob position in the data string.
4. derive with the checksum and the changed data string the original datastring (without knowing the original datastring of course)

I found an algorithm wich can do the trick with m=2^(n) and k = n. That means you need for one Megabyte of Data about three bytes (23 bits) of checksum to detect and correct a random bit flip.

I think, this is pretty short. Is there a shorter one?

In short words, you reshape your text, if it has the length of 2^n in to an n-dimensional binary cube. Sum each coordinate and you get the coordinates of the bit, wich is fliped.

For easier understanding: imagine, you reshape your text to a square and sum each row and each column. this sums are the checksum. If you compare the sums of the text to the sums of a changed text, then you get the coordinates of the position in the matrix, wich is changed. If you do this not with a matrix but wich a cube, you have three coordinates to derive. If you do it with an n-dimensional cube, you need n cooridnates.


Creating the checksum (v2) of the text(t1):
Mix out of octave and pseudocode.

t1=char(n1);
v1=charactertobinary(t1);
n5=floor(log(length(v1))/log(2))+1;
l1=length(v1);
n6=2^n5;
v1=mid(v1,1,n6);
m1=reshape(v1,2*ones(1,n5));
for a=1:n5
m2=m1;
for b=1:n5
if a~=b
m2=sum(m2,b);
end
end
m2=m2(;
m3(1,a)=m2(1);
m3(2,a)=m2(2);
end
v2=m3(2,;
v2=mod(v2,2);



n=v2;

Error correction (t1 initialized with corrupted string, n2=checksum of correct string):
v1=char(t1);
v2=grechks4(v1);
v3=double(n2);
v4=abs(v3-v2);
n5=binary2integer(v4);
v6=grec2b(v1);
n5=n5+1;
v6(n5)=double(not(v6(n5)));
t1=greb2c(v6);


n=t1;

[BioPhysEngr]

My feeling is that for strings of length m=2^n then you will not do better than k=n. To localize an error it seems like you will need to compute the checksum of n/2*2 = n regions to generate 'low frequency' and 'high frequency' data. (Low frequency = parity bits over first half and last half; high frequency = parity bits over all the even bits and all the odd bits).

I haven't studied that particular issue in any systematic way, however, so feel free to be at variance.