Can Ternary Codes of Length 5 with Minimum Distance 3 Exceed Lower Bound of 2?

[Askhwhelp]

In codes of length five over Z3 with d = 3 By using Hamming bound, the upper bound for the number of codeword is 22 and by Gilbert-Varshamov bound, the lower bound for the number of codeword is 2.

The question is to show that you can do better than the lower bound from above by constructing a ternary code of length 5 with minimum distance three with one more codeword than promised by the lower bound of what I found above 2.

What is the process to find such as code?

 

[haruspex]

When I plug n = 5, q = 3, d = 3 into the formula at http://en.wikipedia.org/wiki/Gilbert–Varshamov_bound I get 81/17, giving a lower bound of 5. Am I wrong?

 

[scurty]

When I plug n = 5, q = 3, d = 3 into the formula at http://en.wikipedia.org/wiki/Gilbert–Varshamov_bound I get 81/17, giving a lower bound of 5. Am I wrong?

If 5 is indeed the value obtained from the formula, I think this would be an appropriate answer (first column of codes):

00000 00000 10000
00111 10110 10111
00222 20220 10222
11112 21111 21112
22221 12222 02221
21001 11002 01001

Honestly, the only method I know of is by guess and check. My Coding Theory professor never showed me an efficient method to create codes when I took the class. I'm sure there is a counting technique that helps I don't know about.

You can transpose the columns of the codes above to get another unique solution that works as well (e.g. second column of codes, transposing first and last digits of the codes), since obviously the distances would stay the same. In addition, you can add 1 or 2, for example, to every number in the first column and still keep the distance the same while changing the solution (e.g. third column of codes, adding 1 to first digit of numbers).

I could explain my process if you want but I imagine you already have an example completed and are just looking for a better way. I don't know of one.

 

[Askhwhelp]

When I plug n = 5, q = 3, d = 3 into the formula at http://en.wikipedia.org/wiki/Gilbert–Varshamov_bound I get 81/17, giving a lower bound of 5. Am I wrong?

I think you are right as I calculate one more term for d

 

[scurty]

j only goes up to d-1 in the summation.

Edit: I see you saw that as I posted this message.

 

[haruspex]

I would think that if there were a standard way of constructing codes likely to beat that lower bound then there would correspondingly be a known provable higher bound. (Of course, there might be for specific values of q and/or d.)
Does this work?
00000, 00111, 11100, 11011, 00222, 22020, 22202, 12210

 

[Askhwhelp]

If 5 is indeed the value obtained from the formula, I think this would be an appropriate answer (first column of codes):

00000 00000 10000
00111 10110 10111
00222 20220 10222
11112 21111 21112
22221 12222 02221
21001 11002 01001

Honestly, the only method I know of is by guess and check. My Coding Theory professor never showed me an efficient method to create codes when I took the class. I'm sure there is a counting technique that helps I don't know about.

You can transpose the columns of the codes above to get another unique solution that works as well (e.g. second column of codes, transposing first and last digits of the codes), since obviously the distances would stay the same. In addition, you can add 1 or 2, for example, to every number in the first column and still keep the distance the same while changing the solution (e.g. third column of codes, adding 1 to first digit of numbers).

I could explain my process if you want but I imagine you already have an example completed and are just looking for a better way. I don't know of one.

Could you please explain your process? I am struck for getting started for this question.

 

[scurty]

I would think that if there were a standard way of constructing codes likely to beat that lower bound then there would correspondingly be a known provable higher bound. (Of course, there might be for specific values of q and/or d.)
Does this work?
00000, 00111, 11100, 11011, 00222, 22020, 22202, 12210

Looks good to me, minimum distance is above 3.

Could you please explain your process? I am struck for getting started for this question.

Sure. First I started with an arbitrary code of length five which was ternary. 00000 is the easiest to work with, but you could have started with any you wanted (01221 for example). My next step was to change three of the digits (since the minimum distance was three) by adding 1 to them. I chose to change the last three digits, but because you can transpose digits you can change any three. This resulted in 00111. The next thing I did was add 1 to those same three digits again to yield 00222. Now, if this was a 4-ary or 5-ary code, you would repeat this process until you got to n-1.

Next, I took the second code (00111) and added 1 to the first two digits and to one of the remaining digits (in my case, the last digit) to yield 11112. Next, repeat this process by adding 2 instead of 1 (I didn't do this originally) to yield 22110. Repeat this procedure with the third code to yield 11220 and 22221.

My last code I got was by guess and check, I forget what I did. That results in 8 codes (two weren't included in my original set which I did here). haruspex got some slightly different results so the amount of solutions can be higher.

I guess my main strategy was to start with a simple code and keep changing 3 digits and making sure the minimum distance between all of the codes is greater than 2. As you get more codes this becomes more time consuming.

 

[Askhwhelp]

Looks good to me, minimum distance is above 3.



Sure. First I started with an arbitrary code of length five which was ternary. 00000 is the easiest to work with, but you could have started with any you wanted (01221 for example). My next step was to change three of the digits (since the minimum distance was three) by adding 1 to them. I chose to change the last three digits, but because you can transpose digits you can change any three. This resulted in 00111. The next thing I did was add 1 to those same three digits again to yield 00222. Now, if this was a 4-ary or 5-ary code, you would repeat this process until you got to n-1.

Next, I took the second code (00111) and added 1 to the first two digits and to one of the remaining digits (in my case, the last digit) to yield 11112. Next, repeat this process by adding 2 instead of 1 (I didn't do this originally) to yield 22110. Repeat this procedure with the third code to yield 11220 and 22221.

My last code I got was by guess and check, I forget what I did. That results in 8 codes (two weren't included in my original set which I did here). haruspex got some slightly different results so the amount of solutions can be higher.

I guess my main strategy was to start with a simple code and keep changing 3 digits and making sure the minimum distance between all of the codes is greater than 2. As you get more codes this becomes more time consuming.

So as long as the code words I pick are at least 3 dist apart from each other of length 5 over Z 3, then they are valid right . in order to make sure I understand, could you check the code words I pick in the following 00000, 00111, 00222, 11100, 22200, 12121?

 

[scurty]

Yep. That looks good. As you get more and more codes it is easier to just write a small program to check for you in case you make a mistake. Should only be 10 lines of code or so (not including input).