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;