# Relations between the parameters of the Best Linear Code

Let the triple $(n,k,d)$ be length and dimension and minimum distance of a code, respectively. For a fixed given numbers $n$, $k$ and $d$, what relations there are between BKLC$($GF(2)$,n,k)$ ,BLLC$($GF(2)$,k,d)$ and BDLC$($GF(2),$n,d)$? $$BKLC(K, n, k)= BestKnownLinearCode(K, n, k)$$

(Given a finite field $K$, a positive integer $n$, and a non-negative integer $k$ such that $k\leq n$, return an $[n; k]$ linear code over $K$ which has the largest minimum weight among all known $[n; k]$ linear codes.)

$$BDLC(K, n, d)= BestDimensionLinearCode(K, n, d)$$

(Given a finite field $K$, a positive integer $n$, and a positive integer $d$ such that $d\leq n$, return a linear code over $K$ with length $n$ and minimum weight $> d$ which has the largest dimension among known codes.) $$BLLC(K, k, d)= BestLengthLinearCode(K, k, d)$$

(Given a finite field $K$, and positive integers $k$ and $d$, return a linear code over $K$ with dimension $k$ and minimum weight at least $d$ which has the shortest length among known codes.)

The definitions of BDLC$(K, n, d)$, BLLC$(K, k, d)$ and BKLC$(K, n, k)$ are from HANDBOOK OF MAGMA FUNCTIONS part 115.13, page 3582.

Answer to quid:

One of the reason that I asked this question, It is, In which conditions if $d$=BKLC$($GF(2),$n,k)$ then we have $n$=BLLC$($GF(2),$k,d)$ and $k$=BDLC$($GF(2),$n,d)$(there are three cases and I just assumed one case). For example we have $3$=BKLC$($GF(2),$15,11)$ and so we can see $15$=BLLC$($GF(2),$11,3)$ and $11$=BDLC$($GF(2),$15,3)$. In the next example we have $4$=BKLC$($GF(2),$15,9)$ but we can see $14$=BLLC$($GF(2),$9,4)$ and $10$=BDLC$($GF(2),$15,4)$.

In fact, at first I worked in this problem , If the generator matrix of a code be the form of $G=(I_n,A_{k_n})$ ,where $I_n$ is the identity matrix of order n and $A_{k_n}$ is the adjacency matrix of a complete graph of order n, do we have the mentioned condition for this code? For example for $n=5$, the generator of the matrix is in this form: $$G:= \left[ \begin {array}{cccccccccc} 1&0&0&0&0&0&1&1&1&1 \\ 0&1&0&0&0&1&0&1&1&1\\ 0&0&1&0&0 &1&1&0&1&1\\0&0&0&1&0&1&1&1&0&1 \\ 0&0&0&0&1&1&1&1&1&0\end {array} \right]$$

With using $LinearCode(G)$ command in the MAGMA we see it is $[10,5,4]$ code that is accepts the above condition at the first paragraph. I mean we have $4$=BKLC$($GF(2),$10,5)$ and we can see $10$=BLLC$($GF(2),$5,4)$ and $5$=BDLC$($GF(2),$10,4)$.

In the last I want to thanks for your comments.

• One cannot format posts here using LaTeX syntax. The formatting of posts here is done via HTML (in part via Markdown); only you can use MathJax, which has Tex-like syntax, for Mathematics – user9072 Mar 13 '16 at 23:12
• What is the motivation or context for this question? It seems quite unusual to me. Each of the function optimizes for one of the three parameters of a binary linear code given the two others, and gives an example for the optimum. I do not think there is any relation as such between these codes. – user9072 Mar 13 '16 at 23:53
• In addition to @quid's comments, you are talking about "the best linear code" and its parameters in the title [for a fixed field] but in a lot of cases there are differences between upper and lower bounds on each of these parameters and a lot of the time "the best code" may not be known--with respect to whatever of the three parameters length, dimension, and minimum distance. The fundamental coding theory problem of optimizing one of those 3 while the other 2 are fixed is very combinatorial in nature for given parameters. – kodlu Mar 14 '16 at 4:18
• Thank you for the explication. Note though that the function returns the code, at least this is what you write, not just the parameter. But this detail aside, I now understand better what you are after. – user9072 Mar 14 '16 at 8:43
• Yes you right. The first paragraph wasn’t enough clear to show that what I mean. In General, I am thinking about every column of the generator matrix as a binary of a number and I want to find a number sequence that generate numbers, that their binary forms, can construct the generator matrix of the Best Known Linear Code. Thank you again for your notation. – Amin235 Mar 14 '16 at 11:18

## 1 Answer

Your question, as explained in your last comment, has no answer in general. Due to transformations which yield equivalent codes, it is unlikely to have a short description of columns for every optimal code, let alone the fact that for a lot of cases, optimal codes are unknown. See, for example, http://www.codetables.de/ for some information on what's known.

Special cases: I will only look at two infinite binary code families.

For codeword length $n$ odd the repetition code $$C=\{00\cdots0, 11\cdots1\}$$is perfect, thus best possible. $G$ is simply the $1\times n$ all $1$s matrix.

For codeword length $n=2^m-1$, the generating matrix of the perfect, thus optimal, Hamming code has all the nonzero binary vectors of length $m$ as columns of its parity check matrix. So writing columns as integers $$H=[1,2,3,\ldots 2^m-1].$$ You can put $H$ in systematic form so, $1,2,2^2,\ldots,2^{m-1}$ are the first columns, and then obtain a systematic $G$ from it by the standard method. So, for $m=3,$ $$H=\left[\begin{array}{ccccccc} 1 & 0 & 0 & 1 & 1 & 0& 1 \\ 0 & 1 & 0 & 1 & 0 & 1& 1 \\ 0 & 0 & 1 & 0 & 1 & 1& 1 \\ \end{array} \right]$$ corresponding to $H=[1,2,4,3,5,6,7],$ while $$G=\left[\begin{array}{ccccccc} 1 & 0 & 0 & 0 & 1 & 1& 0 \\ 0 & 1 & 0 & 0 & 1 & 0& 1 \\ 0 & 0 & 1 & 0 & 0 & 1& 1 \\ 0 & 0 & 0 & 1 & 1 & 1& 1 \end{array} \right].$$

The point is, the columns of the systematic $G$ for Hamming codes are the columns corresponding to the identity matrix inside $G$ followed by the columns of a $\times$ matrix whose transpose has columns which are the remaining nonzero binary vectors of length $m$.

• Thank you for examples but I dont agree with your statement that you said "Your question, as explained in your last comment, has no answer in general". I know It is complicated but I can see some BKLC in some sequence numbers. For example for matrix $G$ that you mentioned, it's column are binary of sequence number $(A116443)$ . you know I dont want to see the coding theory as a classical view. I want to find a method or way like number theory that hard problems in the coding theory can be solved but I am agree with you that is unusual way. – Amin235 Mar 17 '16 at 14:09