Skip to main content
2 of 2
retag by quids request
Alexander Chervov
  • 24.8k
  • 20
  • 102
  • 209

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

Everything over F_2.

For any matrix $A$ define the number $N(A) = min_{x}$ HammingWeight $( [x , Ax])$. Where $x$ is vector and [a,b] is just concatenation of vectors: (a_1,...a_n, b_1,...,b_m).

Question What is $max_{A \in Mat(n,m) } (N(A))$ ?

Particular case n=m.


Motivation.

The map $x \to [x, Ax] $ can be considered as error-correcting coding, $x$ - information bits, $Ax$ are redundancy bits.

The code is good if distance between codewords is small.

Reformulation of question: what is the "best possible" code of type above ? ("best possible" in the sense of minimal distance -- it is not always "best" from practical point of view nevertheless).

Alexander Chervov
  • 24.8k
  • 20
  • 102
  • 209