Let $C$ be a code over the finite field $GF(2)$ with generator matrix $G$ and parity matrix $H$. Let $e+C=C'$ be a coset of code $C$. Let $S$ be a non-singular matrix and $H'=H\times S$. Finally, let $C''\subset C'$. Is there any efficient way of finding any other element of the coset $C'$ by only using $C''$ and $H'$ (with appropriate parameters for the code $C$)?

  • $\begingroup$ Do you want some structure on $C''$? It could be empty. Anyway, finding another element of the coset is equivalent to finding a non-zero vector in $\mathrm{Ker}\ G = \mathrm{Img}\ H = \mathrm{Img}\ H\times S$, which is trivial. $\endgroup$ – David Cash Jan 24 '14 at 20:31
  • $\begingroup$ @DavidCash Why finding another element of the coset is equivalent to finding ...?. Recall that $e$ is an fixed element. Here an example in SAGE H = matrix(GF(2),[[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]]); Krnl = H.right_kernel(); G = Krnl.basis_matrix(); S = matrix(GF(2),[[1,1,0,1],[1,0,0,1],[0,1,1,1],[1,1,0,0]]) SH= SH m=vector(GF(2),[0,0,1]); m1=vector(GF(2),[1,0,1,1]); e=vector(GF(2),[0,1,0,0,0,0,0]) print 'mG+e=',(mG+e),'sindrome',H*((mG+e)) print 'm1*SH=',(m1*SH),'sindrome',H*((m1*SH)) $\endgroup$ – juaninf Jan 24 '14 at 23:50
  • $\begingroup$ in the last example (SAGE) m1 is a non-zero vetor in Ker G and that not belong to the same coset $C+e$. $\endgroup$ – juaninf Jan 24 '14 at 23:53
  • 1
    $\begingroup$ I meant in $\mathrm{Img}\ G$ (typo). $\endgroup$ – David Cash Jan 25 '14 at 3:12
  • $\begingroup$ @DavidCash I understand, $\endgroup$ – juaninf Jan 30 '14 at 13:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.