1
$\begingroup$

Well I have used spheres in coding with radius, $r=\left\lfloor\frac{\delta -1}{2} \right\rfloor=\left\lfloor\frac{8 -1}{2} \right\rfloor = 3$

and that means we have $\sum \limits_{i=0}^3 {16 \choose i} (2-1)^i=697$ words in each sphere, with $2^k=2^5=32$ spheres we have $32*697=22304$ distinct words.

Since we can have a total of $2^{16}=65535$ such a code does exist

Is this an acceptable proof?

$\endgroup$
3
  • 2
    $\begingroup$ I'm not up on this kind of coding stuff, but my first question is whether you can actually say "the room has more volume than the balls, therefore the room can fit all the balls" -- which isn't true in the real-world case. Not to say it isn't true in this case; it's just where I can see a possible failure. $\endgroup$
    – Dan Uznanski
    Oct 9, 2014 at 14:43
  • $\begingroup$ @DanUznanski The radius is the number of changes to a specific code word of length $16$ that are allowed, E.g if it were length $5$ with $r=2$ $00000$ would hold in its sphere $00011$. So these spheres can never intersect(they are more like circles, but that is what the theory is called). Pretty much we have $32$ non-interesecting circles, with $22304$ distinct words, with $65535-22304$ words that can't be corrected. I am fairly confident that the proof is acceptable and thanks for the input, I get that the terminology seems really strange(I think spheres are a terrible name for this) $\endgroup$
    – Partly Putrid Pile of Pus
    Oct 9, 2014 at 14:51
  • $\begingroup$ Related: math.stackexchange.com/questions/232611/…. $\endgroup$
    – Dietrich Burde
    Oct 9, 2014 at 15:19

3 Answers 3

Reset to default
3
$\begingroup$

Your assumption is wrong, at least in the general case. Dan Uznanski already showed it intuitively.

If you want to prove such code exists, you have to construct one. You can construct a linear binary code of $[16,5,8]$ using following code constructs:

Construction of a linear code 
[16,5,8] over GF(2):
[1]:  [8, 1, 8] Cyclic Linear Code over GF(2)
     RepetitionCode of length 8
[2]:  [4, 1, 4] Cyclic Linear Code over GF(2)
     RepetitionCode of length 4
[3]:  [4, 3, 2] Cyclic Linear Code over GF(2)
     Dual of the RepetitionCode of length 4
[4]:  [8, 4, 4] Quasicyclic of degree 2 Linear Code over GF(2)
     PlotkinSum of [3] and [2]
[5]:  [16, 5, 8] Linear Code over GF(2)
     PlotkinSum of [4] and [1]

source: http://www.codetables.de/

$\endgroup$
4
  • $\begingroup$ I agree with what you are saying, the assumption did seem really weak, but I do believe I could prove it without constructing the code. I will get back to you after doing more research. Thank you for your answer and the code! $\endgroup$
    – Partly Putrid Pile of Pus
    Oct 9, 2014 at 15:09
  • 1
    $\begingroup$ Your assumption would also allow a $[16,6,8]$ code, since 64*697 is also less than 65536. However, that code does not exist. $\endgroup$
    – Pieter21
    Oct 9, 2014 at 15:18
  • 1
    $\begingroup$ One of the simplest ways of proving the non-existence of a $(16,6,8)$-code is to use the Griesmer bound. It tells that the length $n$ of an $(n,6,8)$-code is at least $$n\ge\lceil\frac81\rceil+\lceil\frac82\rceil+\lceil\frac84\rceil+\lceil\frac8{8}\rceil+\lceil\frac8{16}\rceil+\lceil\frac8{32}\rceil=8+4+2+1+1+1=17.$$ $\endgroup$
    – Jyrki Lahtonen
    Oct 9, 2014 at 15:40
  • $\begingroup$ @JyrkiLahtonen Also thank you for the Griesmer bound, very nice! Thank you for the code and assistance Pieter! $\endgroup$
    – Partly Putrid Pile of Pus
    Oct 12, 2014 at 15:08
2
$\begingroup$

Such a code exists. Others have posted links and/or construction schemes. I would just state that the Reed-Muller code $RM(1,4)$ is exactly what you need.

My main point is to explain, amplifying the message from Dan Uznanski and Pieter21, why your argument is insufficient (it could lead to a non-existence proof though). Assume that the question were about the existence of a $(7,1,8)$-code. Following your logic we would calculate $$ r=\left\lfloor\frac{\delta-1}2\right\rfloor=3, $$ and that the number of words in a ball of radius $r$ is $$ V(B(r=3))=\sum_{i=0}^3\binom 7 i=1+7+21+35=64. $$ You would then conclude that the space $GF(2)^7$ has room for $2=2^k$ balls.

But the minimum distance of a code obviously cannot exceed the length, so a $(7,1,8)$-code clearly cannot exist.

It was a bit naughty of me to do it that way, sorry. Also there exists a $(7,1,7)$-code, so my example for showing the error of your ways is not as convincing as it might be given that it depended on $\delta=8$ and $\delta=7$ producing the same $r$. The main reason why the point count is not sufficient is that you would still need to prove that you can actually place the balls in such a way that there is no overlap, just as Dan said.

$\endgroup$
1
  • $\begingroup$ Thank you, I can prove that $\mathcal{R}(4)$ exists, since $\mathcal{R}(m)=(2^m,m+1,2^m-1)$ $\endgroup$
    – Partly Putrid Pile of Pus
    Oct 12, 2014 at 15:08
2
$\begingroup$

Such a code exists. There even exists an optimal binary linear $[16,5,8]$-code. For its construction, see for example exercise $121$ in the book "Fundamentals of Error-Correcting Codes", wriiten by W. Cary Huffman and Vera Pless. Just to say that we can have $2^{16}$ words does not prove the existence of such a code.

$\endgroup$
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.