Combinatorics: Creating Codes

1. Nov 26, 2013

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?

Last edited: Nov 26, 2013
2. Nov 26, 2013

haruspex

3. Nov 26, 2013

scurty

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

Code (Text):

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.

4. Nov 26, 2013

5. Nov 26, 2013

scurty

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

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

6. Nov 26, 2013

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

7. Nov 26, 2013

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

8. Nov 27, 2013

scurty

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.

9. Nov 27, 2013