3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – user9072 Mar 13 '16 at 23:12
  • $\begingroup$ 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. $\endgroup$ – user9072 Mar 13 '16 at 23:53
  • $\begingroup$ 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. $\endgroup$ – kodlu Mar 14 '16 at 4:18
  • $\begingroup$ 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. $\endgroup$ – user9072 Mar 14 '16 at 8:43
  • $\begingroup$ 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. $\endgroup$ – Amin235 Mar 14 '16 at 11:18
1
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Amin235 Mar 17 '16 at 14:09

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.