Return to Answer

This is, indeed, an open question for most values of $n$. A.D. Brouwer maintains a database of the best known lower and upper bounds, and everything that is known for small $n$ can be found there. A minute of googling points me at

http://mint.sbg.ac.at/desc_CBrouwerTable-Bound.html

Asymptotically the best bound is usually the linear programming bound due to McEliec-Rodemich-Rumsey and Welch, but the asymptotic bounds may not be very good for rate 1/2 codes.

An interesting simple general existence proof is described in van Lint's book (Springer GTM series). Fix a basis for $F=GF(2^n)$. Treat $x$ as an element of $F$, and use encoding $x\mapsto (x,ax)$, where $a$ is an element of $F$ that we choose carefully. Fix a target minimum distance. Let $S(i)$ be the set of elements of $F$ of weight $i$, so $|S(i)|={n\choose i}.$ We must disallow all those elements $a$ that can be written in the form $a=y/x$, where $x\in S(i), y\in S(j), i+j\lt d$. The number of disallowed elements $a$ is thus at most $$ N(d)=\sum_{0\lt i,j\lt d; i+j\lt d}{n\choose i}{n\choose j}. $$ If $N(d)\lt 2^n$ we have not disallowed all the elements of $F$, so the construction succeeds.

This is, indeed, an open question for most values of $n$. A.D. Brouwer maintains a database of the best known lower and upper bounds, and everything that is known for small $n$ can be found there. A minute of googling points me at

http://mint.sbg.ac.at/desc_CBrouwerTable-Bound.html

Asymptotically the best bound is usually the linear programming bound due to McEliece-Rodemich-Rumsey and Welch, but the asymptotic bounds may not be very good for rate 1/2 codes.

An interesting simple general existence proof is described in van Lint's book (Springer GTM series). Fix a basis for $F=GF(2^n)$. Treat $x$ as an element of $F$, and use encoding $x\mapsto (x,ax)$, where $a$ is an element of $F$ that we choose carefully. Fix a target minimum distance. Let $S(i)$ be the set of elements of $F$ of weight $i$, so $|S(i)|={n\choose i}.$ We must disallow all those elements $a$ that can be written in the form $a=y/x$, where $x\in S(i), y\in S(j), i+j\lt d$. The number of disallowed elements $a$ is thus at most $$ N(d)=\sum_{0\lt i,j\lt d; i+j\lt d}{n\choose i}{n\choose j}. $$ If $N(d)\lt 2^n$ we have not disallowed all the elements of $F$, so the construction succeeds.

This is, indeed, an open question for most values of $n$. A.D. Brouwer maintains a database of the best known lower and upper bounds, and everything that is known for small $n$ can be found there. A minute of googling points me at

http://mint.sbg.ac.at/desc_CBrouwerTable-Bound.html

Asymptotically the best bound is usually the linear programming bound due to McEliec-Rodemich-Rumsey and Welch, but the asymptotic bounds may not be very good for rate 1/2 codes.

An interesting simple general existence proof is described in van Lint's book (Springer GTM series). Fix a basis for $F=GF(2^n)$. Treat $x$ as an element of $F$, and use encoding $x\mapsto (x,ax)$, where $a$ is an element of $F$ that we choose carefully. Fix a target minimum distance. Let $S(i)$ be the set of elements of $F$ of weight $i$, so $|S(i)|={n\choose i}.$ We must disallow all those elements $a$ that can be written in the form $a=y/x$, where $x\in S(i), y\in S(j), i+j<d$. The number of disallowed elements $a$ is thus $$ S(d)=\sum_{0<i,j<d; i+j<d}{n\choose i}{n\choose j}. $$ If $S(d)<2^n$ we have not disallowed all the elements of $F$, so the construction succeeds.

This is, indeed, an open question for most values of $n$. A.D. Brouwer maintains a database of the best known lower and upper bounds, and everything that is known for small $n$ can be found there. A minute of googling points me at

http://mint.sbg.ac.at/desc_CBrouwerTable-Bound.html

Asymptotically the best bound is usually the linear programming bound due to McEliec-Rodemich-Rumsey and Welch, but the asymptotic bounds may not be very good for rate 1/2 codes.

An interesting simple general existence proof is described in van Lint's book (Springer GTM series). Fix a basis for $F=GF(2^n)$. Treat $x$ as an element of $F$, and use encoding $x\mapsto (x,ax)$, where $a$ is an element of $F$ that we choose carefully. Fix a target minimum distance. Let $S(i)$ be the set of elements of $F$ of weight $i$, so $|S(i)|={n\choose i}.$ We must disallow all those elements $a$ that can be written in the form $a=y/x$, where $x\in S(i), y\in S(j), i+j\lt d$. The number of disallowed elements $a$ is thus at most $$ N(d)=\sum_{0\lt i,j\lt d; i+j\lt d}{n\choose i}{n\choose j}. $$ If $N(d)\lt 2^n$ we have not disallowed all the elements of $F$, so the construction succeeds.

This is, indeed, an open question for most values of $n$. A.D. Brouwer maintains a database of the best known lower and upper bounds, and everything that is known for small $n$ can be found there. A minute of googling points me at

http://mint.sbg.ac.at/desc_CBrouwerTable-Bound.html

This is, indeed, an open question for most values of $n$. A.D. Brouwer maintains a database of the best known lower and upper bounds, and everything that is known for small $n$ can be found there. A minute of googling points me at

http://mint.sbg.ac.at/desc_CBrouwerTable-Bound.html

Asymptotically the best bound is usually the linear programming bound due to McEliec-Rodemich-Rumsey and Welch, but the asymptotic bounds may not be very good for rate 1/2 codes.

An interesting simple general existence proof is described in van Lint's book (Springer GTM series). Fix a basis for $F=GF(2^n)$. Treat $x$ as an element of $F$, and use encoding $x\mapsto (x,ax)$, where $a$ is an element of $F$ that we choose carefully. Fix a target minimum distance. Let $S(i)$ be the set of elements of $F$ of weight $i$, so $|S(i)|={n\choose i}.$ We must disallow all those elements $a$ that can be written in the form $a=y/x$, where $x\in S(i), y\in S(j), i+j<d$. The number of disallowed elements $a$ is thus $$ S(d)=\sum_{0<i,j<d; i+j<d}{n\choose i}{n\choose j}. $$ If $S(d)<2^n$ we have not disallowed all the elements of $F$, so the construction succeeds.