1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Combinatorics: Creating Codes

  1. Nov 26, 2013 #1
    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. jcsd
  3. Nov 26, 2013 #2

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

  4. Nov 26, 2013 #3
    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.
     
  5. Nov 26, 2013 #4
  6. Nov 26, 2013 #5
    j only goes up to d-1 in the summation.

    Edit: I see you saw that as I posted this message.
     
  7. Nov 26, 2013 #6

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    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
     
  8. Nov 26, 2013 #7
    Could you please explain your process? I am struck for getting started for this question.
     
  9. Nov 27, 2013 #8
    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.
     
  10. Nov 27, 2013 #9
    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?
     
  11. Nov 27, 2013 #10
    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).
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Combinatorics: Creating Codes
  1. Combinatorics Question (Replies: 4)

  2. Combinatorics question (Replies: 2)

Loading...