Skip to main content
1 of 4
Alexander Chervov
  • 24.9k
  • 20
  • 102
  • 209

How does minimal Hamming distance depends on the length of code for tb-convolutional codes ? (E.g. 9 9 10 10 12 12 13 13 12 13 15)

Mathematical formulation Fix some vectors $v_1, v_2 \in F_2^k$ , take some number N>k and consider circulant NxN matrices $C(v_1), C(v_2) $ which are defined by these vectors (put zeros on diagonals which are further then k-th diagonal).

Consider the map "encoder" $F_2^N \to F_2^N \oplus F_2^N$, given by $x \mapsto (C(v_1) x, C(v_2) x) $.

Find some vector $y\ne 0$ in image of "encoder" with minimal Hamming weight, denote this weight by $dMin(N)$.

Question How does $dMin(N)$ behave depending on N?

Comments Of course, everything depends on $v_i$, this makes the question vague, so I am interested was it known about it for different $v_i$.

I can take several vectors $v_i$ not just two.


I am not sure my description of C(v) is clear, let me give another. Think of vector $v\in F_k$ as a polynom of degree $k-1$ in a obvious way. Consider the operator of multiplication on this polynom acting in a factor space $F_2[x]/(x^N-1)$ - this is exactly C(v).


Numerical experiment.

I took three vectors corresponding to binary form of octal numbers

G4 = 133;       % 1+D^2+D^3+D^5+D^6

G7 = 171;       % 1+D+D^2+D^3+D^6

G5 = 165;       %165  % 

(this is some practically used error-correcting code).

And calculated minDistance for N=10:20, here is the answer:

(E.g. 9 9 10 10 12 12 13 13 12 13 15)


Error-correcting codes formulation The question is how the minimal distance of the "tail-bited" non-recursive convolutional code behave depending on block lenght N ?

Reminder Non-recursive convolutional codes corresponds to semi-infinite Toeplitz matrices. "Tail-biting" is cuting this semi-infinte matrix to NxN circulant matrix.


Pay attention this is NOT kind of code considered in here:

How many k-nomials of deg N divisible by X^16+x^12+x^5 +1 ? (Spectrum of CRC-16-CCITT erroc-correcting code ?)

Some related question:

What is matrix A such that Hamming weight of [x, Ax] is maximal ? (Min distance of 1/2 block code?)

But not I fix the class of codes to be convolutional.

Alexander Chervov
  • 24.9k
  • 20
  • 102
  • 209