MDS/cyclic code, binary string question

[nugget]

Homework Statement

Suppose n\leq2

Let C be the code consisting of all binary strings of length n in which the sum of the bits is even. Is C and MDS code? is C a cyclic code?

Homework Equations

An MDS code is one where the codewords are separated by a maximum number of bits d. MDS codes obey this theorem: There are q^{n-d+1} different words of length n-(d-1) when the alphabet is of size q. I think this means that if we delete the first (d-1) letters of every codeword of length n, there will be q^{n-d+1} different words of length n-(d-1).

In our case, q = 2 as we are working with binary strings.

e.g. if n = 2, C = {00,11}

n = 3 ---> C = {000,110,101,011}

n = 4 ---> C = {0000,1100,1001,0011,0110,1010,0101,1111}

etc...

The Attempt at a Solution

From observation, d = 2. How do I find this, not simply as an observation? I've checked that the formula fits for n from [2,5] and it seems to.

The codes I have written out appear to be cyclic. Cyclic codes are those where each element can be formed via cyclic shifting of another element.

any hints on how to solidify my argument?

 

[Mark44]

Homework Statement

Suppose n\leq2

Let C be the code consisting of all binary strings of length n in which the sum of the bits is even. Is C and MDS code? is C a cyclic code?

Homework Equations

An MDS code is one where the codewords are separated by a minimum number of bits d. MDS codes obey this theorem: There are q^{n-d+1} different words of length n-(d-1) when the alphabet is of size q.

In our case, q = 2 as we are working with binary strings.

e.g. if n = 2,

C = {00,11}

n = 3 ---> C = {000,110,101,011}

n = 4 ---> C = {0000,1100,1001,0011,0110,1010,0101,1111}

etc...

The Attempt at a Solution

From observation, d = 2. Is there a way to state this, not simply as an observation? I'm at a loss here. I've checked that the formula fits for n from [2,5], and it seems to, but don't know how to generalise the argument.

So I figure it IS an MDS code, and it definitely also appears to be cyclic.

any hints on how to solidify my argument?

I had to think awhile about what you meant by "separated" by a minimum number of bits. After a bit, I realized that what separated means in this context is that any two code words in the code differ by two bits. If you think about it, the codewords couldn't be separated by or differ by only one bit (do you see why?). They also couldn't differ by, say, three bits, for the same reason. Maybe that will give you a place to start.

You gave a definition for MDS codes, but not one for cyclic codes. How are they defined?

 

[nugget]

It makes sense that because the sums of the bits must be even, then d cannot equal an odd number. So I suppose that is sound enough logic to say it is an MDS code, because then the minimum distance is always 2!

nice

Cyclic codes are those where each element can be formed via cyclic shifting (moving all the bits left or right) of another element. e.g. for n = 3, the codewords 110, 101,011 are all formed by cyclic shifts on the first one, 110.

I don't see why it wouldn't be a cyclic code... all my scribblings seem to suggest that it is

thanks for replying so quick!

 

[Mark44]

It makes sense that because the sums of the bits must be even, then d cannot equal an odd number. So I suppose that is sound enough logic to say it is an MDS code, because then the minimum distance is always 2!

I think that for completeness, you need to say why another even number, say 4, couldn't be the minimum distance.

nice

Cyclic codes are those where each element can be formed via cyclic shifting (moving all the bits left or right) of another element. e.g. for n = 3, the codewords 110, 101,011 are all formed by cyclic shifts on the first one, 110.

I don't see why it wouldn't be a cyclic code... all my scribblings seem to suggest that it is

thanks for replying so quick!

Here's your code for n = 4:
C = {0000, 1100, 1001, 0011, 0110, 1010, 0101, 1111}

Here they are again, in groups:
{{0000}, {1100, 1001, 0110}, {1010, 0101}, {1111}}
In each group of more than one codeword, the first one listed can be used to generate the others in the group, by a cyclic shift, or rotation, of the bits.

Now, think about a code consisting of binary strings of length n, where again the sum of the bits is even. If n is even, each codeword will have to have an even number of 1s and an even number of 0s. If n is odd, each codeword will still have to have an even number of 1s, but there will be an odd number of 0s. Could there be a codeword that is not formed by shifting (rotating) the bit pattern for some other codeword? Doesn't seem like it to me, but I'm just throwing out some ideas.

 

[nugget]

I don't see how there could be a codeword in C that can't be formed under cyclic shifts.

I have a theorem in my notes regarding cyclic codes, and it is the only one given so I assume I need to use it:

C is Cyclic if and only if it is an ideal of GF(q)[x]/<x^{n}-1>

so I need to show that every code polynomial can be generated by some <x^{n}-1>, I think. Maybe I'm wrong about what that notation means... I thought we factorise <x^{n}-1> and then all possible combinations of factors generate GF(q)[x].

There is a weird proof given in the notes where they ASSUME C is a cyclic code, and then show it is an ideal of the galois field generated by x^{n}-1. They then go the other way and suppose that C is an ideal of that galois field. then they say it is cyclic as it is an ideal.

it's a pretty airy looking proof, can I use that?

if not I just don't get how to say for sure that it is cyclic... the only thing i can think of is that of course it's cyclic because C contains all possible codewords with an even number of 1s, so shifting those bits around will just yield other words with an even number of 1s, which are definitely in C.I'm assuming that this was a general proof and I can't use it for my question because I don't have a constant codeword length...

 

[nugget]

and now I'm trying to multiply polynomials from the galois field by polynomials from C, and still ending up in C.

perhaps their dodgy proof is the right way?