Need help with Reed-Solomon Coding

Hi

I am trying to encode my image with Reed-Solomon code. The code is as below

n = 255;
img = imread('pout.tif');
binary = img > 102;

resized = imresize(binary,[291 247]);
[row k] = size(resized);

gfmsg = gf(resized);
enc = rsenc(gfmsg,n,k);
error = enc + gf(randerr(row,n));

When I run the code, I get an error :

Error using rsenc (line 74)

Symbols in MSG must all have 3 or more bits.

Can you pls help me with this?

Answer 1

[Walter Roberson]

n = 255;
img = imread('pout.tif');
binary = img > 102;

resized = imresize(binary,[291 247]);
[row k] = size(resized);

gfmsg = gf(resized,8);
enc = rsenc(gfmsg,n,k);
error = enc + gf(randerr(row,n),8);

[Neeraj Chimwal]

What you did here is to specify the galois field order. right?

This galois field makes my head spins. I have been trying to understand it for 2 days yet no progress

[Walter Roberson]

Yes, I specified the galois field order.

You should be considering packing your binary into larger groups, such as

n = 255;
img = imread('pout.tif');

binary = img > 102;
resized = imresize(binary,[296 247]);
r8 = reshape(resized, 8, []);
resized = reshape(2.^(0:7) * r8, [], 247);  %8 bits into one byte
[row k] = size(resized);

gfmsg = gf(resized, 8);
enc = rsenc(gfmsg,n,k);
error = enc + gf(randerr(row,n),8);

size(resized)

ans = 1×2

37 247

size(enc)

ans = 1×2

37 255

size(error)

ans = 1×2

37 255

Notice I went slightly larger on the imresize(), to 296 instead of 291, in order to make it a multiple of 8 so that bits could be packed more easily. If the 291 is somehow important, then you could instead pad the bottom of the 291 with 5 rows of zeros and process that, and remove the 5 rows of zeros after the rs decoding.

[Neeraj Chimwal]

This might be naive question but can you please explain how packing binary into large group will help here?

The thing is that I have never worked on MATLAB before and now my professor want me to compare every convolution and block encoding methods on Images. So I am trying all methods one by one in the easiest way I can understand.

[Walter Roberson]

rsenc() simply refuses to work when the number of bits per item is less than 3.

rsenc() requires that n be at most 2^m-1 where m is the number of bits the gf was built for --- so if we tried m = 3 then n would be at most 2^3-1 = 7.

rsenc() requires that this value, hypothetically 7, be larger than the number of columns of the message, by an even positive integer. If we did not want to pad the message then we must reshape it to have at most 7 minus an even positive integer columns -- so we would have to use 1, 3, or 5 columns, and that number has to divide the number of elements in 291 x 247, so we would have to use either 1 or 3 columns.

With 3 columns that would look like

m = 3;
n = 2^m-1;

img = imread('pout.tif');
binary = img > 102;
resized = imresize(binary,[291 247]);
resized = reshape(resized, [], 3);   %3 divides 291 x 247, and we need odd integer < 7 that divides that
[row k] = size(resized)

row = 23959

k = 3

[row k]

ans = 1×2

23959 3

gfmsg = gf(resized,m);
enc = rsenc(gfmsg,n,k);
error = enc + gf(randerr(row,n),m);

size(enc)

ans = 1×2

23959 7

size(error)

ans = 1×2

23959 7

Could we use 1 column instead? Yes. We can also reduce the number of bits per word to the minimum

m = 3;
n = 3;

img = imread('pout.tif');
binary = img > 102;
resized = imresize(binary,[291 247]);
resized = reshape(resized, [], 1);   %1 divides 291 x 247, and we need odd integer < 7 that divides that
[row k] = size(resized);
[row k]

ans = 1×2

71877 1

gfmsg = gf(resized,m);
enc = rsenc(gfmsg,n,k);
error = enc + gf(randerr(row,n),m);

size(enc)

ans = 1×2

71877 3

size(error)

ans = 1×2

71877 3

If you examine the output for this last one, you get rows that are only ever

   1   6   8

or

   0   0   0

You are encoding k = 1 bit at a time producing 3 bits of output per group, and that means the rows can only be one of those two choices. Using higher n, so generating more bits per group, would increase the resiliance to noise but would still have the property that all the rows were one of two distinct choices.

[Neeraj Chimwal]

So that's why you added 8 for galois field order there. m=8 will give n=255.

I read this in galois field tutorial but was confused why in every example they are taking m=3 before knowing the size of signal. Now that you used reshape() to reshape the signal according to order, everything got clear to me.

Thankyou so much for taking time to explain. An explaination can't be any better.

Sorry for bothering you but I have just one last question:

you told that I should consider packing binaries to larger group

and showed how do that using command :

r8 = reshape(resized, 8, []);
resized = reshape(2.^(0:7) * r8, [], 247);

I want to ask that in what way this might help me. Also, it reduces the number of rows in my image so after decoding the signal (i.e image), I have to again reshape it to get original Image right? Coz not doing so gives me Image with very small height compared to original Image.

[Walter Roberson]

So that's why you added 8 for galois field order there. m=8 will give n=255.

Exactly. Your code had a target n = 255, and the way to get that is to have m be at least log2(255+1) --> 8.

Your target n must be greater than the number of columns, which you had set to 247.

n is the number of output entries per row.

But each output entry is a integer in the range 0 to 2^m-1 and n must be at least 2^m-1

In order to use n = 255 then m must be at least 8. So 8 bits are being used per entry.

But your binary inputs are all 0 or 1, and the actual data appears at the beginning of each row. So your first 247 entries per row are going to be numeric value 0 or numeric value 1, but you need 8 bits per entry because m = 8. The final (255-247 = 8) entries per row will have some other value in the range 0 to 255, that actually need the full 8 bits.

It seems a bit of a waste, though, to send 291 rows of 255 columns of 8 bit data for which for the first 247 columns, only 1 bit is significant.

From the point of view of a compact message, it makes more sense to take advantage of the fact that with m = 8 that you might as well pack 8 bits of input into each entry that is to be encoded. You get down to 37 rows of 255 entries, each a meaningful 8 bits per entry.

After the decoding you would need to expand the 8 bits per entry into binary. The code I showed with 2.^(0:7) * r8 encodes with weight

1 2 4 8 16 32 64 128

so for example

0 0 1 0 0 1 0 1

would be

0*1 + 0*2 + 1*4 + 0*8 + 0 * 16 + 1*32 + 0*64 + 1*128 = 164 decimal

You might want to reverse the order bits are used in; if so then

resized = reshape(2.^(7:-1:0) * r8, [], 247);

which would give weights

128 64 32 16 8 4 2 1

so

128*0 + 64*0 + 32*1 + 16*0 + 8*0 + 4*1 + 2*0 + 1*1 = 37

This second order is consistent with using dec2bin()

[Neeraj Chimwal]

ok so what I understand is that can do it in two ways:

1. Either use 1 bit because using 8 bits would be a waste if only 1 bit is enough.
2. If I am using 8 bits, it would be better to pack 8 bits to 1 byte.

is that right?

If so, then using just m=1 bit seems more sensible otherwise I'll have to contract and expand the signal from 8 bit to 1 byte and vice versa which seems unreasonable.

[Walter Roberson]

You cannot use m = 1 because rsenc will not accept anything less than m = 3.

So you would need to use either k = 1 n = 3 or k = 1 n = 5 or k = 1 n = 7, or k = 3 n = 5 or k = 3 n = 7 .

The case k = 1 n = 3, you would be using one logical value from the image, and turning it into something that is logically 3 bits (000 or 001), and when it is encoded it would be followed by two three-bit words. That would give a total of 9 bits per row, and the number of rows would be 291*247 = 71877 for a total of 646893 bits to transmit.

If you pad out to 37 rows of 247 columns, each item a full 8 bit's worth of values, and you use n = 255, then the encoded size would be 37 * 255 with 8 meaningful bits per entry, for a total of 75480 bits to transmit.

[Neeraj Chimwal]

My bad. Got confused in variables. Anyway, Thankyou so much for expaining this stuff to me