The Gate Complexity of Syndrome Decoding of Hamming Codes
J. Carmelo Interlando, Eimear Byrne, Joachim Rosenthal · 2004
Let A = (aij)k£n be a matrix with entries in the Galois fleld GF(2), and let x = (x1;x2;:::;xn)t be a vector of variables assuming values in GF(2). The gate complexity of A, denoted by C(A), is the minimum number of XOR gates necessary to compute the matrix-vector product Ax. In this paper it is shown that C(Hk) = 2 k+1 i 2k i 2, where Hk is the parity-check matrix of the (2 k i 1;2 k i k i 1) Hamming code. As a consequence, upper bounds on C(A) for any matrix A = (aij)k£n, one for flxed k and another one for flxed n, are derived. As a interesting application of these results, we give a simple proof that the upper bound on the gate complexity of an n £ n matrix is 2n 2 =log2 n.