0

Imagine I have $C (n,k,d)$ - linear code above $GF(q)$. Consider I know all words of this code.

$c_1, ..., c_M$ -- vectors from it.

If matrix H -- checking matrix (so any word from code will give zero in this way: $vH=0$ for this code will be

$H = [ c_1^t,...,c_M^t ] $

How can I find minimum distance in this code with such $ H$

  • From the definition of the parity-check matrix, $H$, it directly follows that the minimum distance of the code is the minimum number $d$ such that every $d - 1$ columns of a parity-check matrix $H$ are linearly independent while there exists $d$ columns of $H$ that are linearly dependent. – Random-generator Jun 13 '17 at 13:42
  • If you actually have a list of all the codewords you just need to spot a lowest weight non-zero word. But, it actually sounds like you just have a description of the code in terms of a family of check equations. The bad news are that in the general case the problem of finding the minimum distance is pretty much impossible. It is known that answering the question whether there are words of weight less than a given constant is NP-hard (or some other nasty category of decision problems). – Jyrki Lahtonen Jun 13 '17 at 13:43
  • Moreover, we have the result that minimum distance of a linear block code is equal to the minimum hamming weight of all the codewords generated from that linear code. – Random-generator Jun 13 '17 at 13:43
  • You can, of course, look for a minimal set of linearly dependent columns of $H$. Have fun checking out $\binom M d$ sets of columns :-/ – Jyrki Lahtonen Jun 13 '17 at 13:44
  • @JyrkiLahtonen I actually have list of all code words. And in this question we suppose that matrix H consist of those words as well. Hm, why do I need to spot word with the lowest weight? –  Jun 13 '17 at 13:49
  • Oh, you are defining another code? And $M=q^k$? Sounds a bit strange. But then $c_i=(0,0,0,\ldots,0)$ for some $i$, and that check matrix automatically defines a code of length $q^k$ and minimum distance $1$. It still sounds strange. – Jyrki Lahtonen Jun 13 '17 at 13:54
  • Or are you just trying to define the dual code of the original code? – Jyrki Lahtonen Jun 13 '17 at 13:59
  • @Jyrkilahtonen no, I just have code and I know all codewords from it and in this code matrix H is given as was said above. –  Jun 13 '17 at 13:59
  • I am trying to find this number of independent columns in thus matrix –  Jun 13 '17 at 13:59
  • With the word every, heh –  Jun 13 '17 at 14:00
  • You said that I need to spot word with the lowest weight in my case. Why do I need this? –  Jun 13 '17 at 14:02
  • Well, are you not trying to find the lowest weight word? And, if there is just one code in this exercise, namely the one defined by the check equations, then the vectors $c_i$ are not from the code. – Jyrki Lahtonen Jun 13 '17 at 14:16
  • @Jyrkilahtonen My task is to find this minimum distance $d$ in this special code which consists of M words and matrix H consist of M columns where each column is transposed codeword from the code –  Jun 13 '17 at 14:18
  • But what has $H$ got to do with it if you already have all the codewords? I can't make sense out of this. – Jyrki Lahtonen Jun 13 '17 at 14:23
  • @Jyrkilahtonen I think that the case if this task that I don't exactly those words. I just know that matrix H can be presented in that way. –  Jun 13 '17 at 14:31
  • @JyrkiLahtonen Haha, I got it. It's just about linearity of this code. So every two of codewords will sum up for the third vector from this code. So, it means that in this matrix EVERY two columns are independent, and some sets of three columns are dependent. So $d-1 = 2$. –  Jun 13 '17 at 19:13

1 Answers1

0

Suppose you have a $k\times n$ generator matrix $G$ of the code. Then by elementary row operations and column permutations (which means you consider an equivalent code with the same minimum distance), the matrix has the form $G= (I\mid A)$, where $I$ is the $k\times k$ identity matrix. Then the $(n-k)\times n$ matrix $H = (-A^T\mid I)$ is a check matrix, since $GH^T=0$. Now proceed to find the minimum number of linearly independent columns of $H$. If this number is $d-1$, the minimum distance is $\geq d$ (with equality if the code has a word of Hamming weight $d$).

Wuestenfux
  • 20,964
  • My task is to find this $d$ in this special code which consists of M words and matrix H consist of M columns where each column is transposed codeword from the code –  Jun 13 '17 at 14:15
  • 2
    Usually, the number of codewords, $M=q^k$, is much larger than the length, $n$, of the code, where the underlying field has $q$ elements. – Wuestenfux Jun 13 '17 at 14:19