The natural domain for the algebra of binary cyclic codes of length $N$ is the quotient ring $R_N=\mathbb{F}_2[x]/\langle x^N+1\rangle$.
The key observation is that if we turn a sequence $c$ of $N$ bits into a polynomial $c(x)\in R_N$ of degree $\le N-1$ in the usual way, then the binary "inner product" of two vectors $c$ and $c'$, $\langle c,c'\rangle$, is equal to the constant term of the product $c(x)c'(x^{-1})$ in the ring $R$.
If $h$ is any row of the check matrix, then this implies that for all codewords $c$ the product $c(x) h(x^{-1})$ should have a vanishing constant term. But the products $x^jc(x)\in R_N$ is the polynomial we associate with the cyclic shifts of the word $c$, $j=1,2,\ldots, N-1$ by $j$ positions. As the cyclic shifts of $c$ are also codewords, the constant terms of all the products (in $R_N$) $x^jc(x)h(x^{-1})$ must vanish. As $j$ ranges from $0$ to $N-1$, all the terms of the product $c(x)h(x^{-1})$ occur as constant terms for some choice of $j$. Therefore we must have $c(x)h(x^{-1})=0$ in $R_N$.
Let us call any polynomial $h(x)$ with the property that $c(x)h(x^{-1})=0$ for all codewords $c$ a dual polynomial. If $h(x)$ and $h'(x)$ are dual polynomials, then so are all the polynomials of the form $x^jh(x)+x^ih'(x)$ as well as longer linear similar combinations. We see that the dual polynomials form an ideal of $R_N$ as well as of the polynomial ring $\mathbb{F}_2[x]$, so for example the gcd of two dual polynomials is a dual polynomial. Also $x^N+1$ is a dual polynomial. We want to find a generator for this ideal. As all the rows of the parity check matrix yield dual polynomials, we get the following general method:
- Turn all the rows of the check matrix into polynomials $h_i(x)\in R_N$.
- Compute the greatest common divisor ${\tilde h}(x)=\gcd(h_1(x),h_2(x),\ldots,h_{N-k}(x),x^N+1)$ in the ring $\mathbb{F}_2[x]$.
- The reciprocal polynomial of this ${\tilde h}(x)$ is the check polynomial $h(x)=x^N{\tilde h}(x^{-1})$ (I multiplied it with $x^N$ to turn it into a polynomial in $x$. In the ring $R_N$ we have $x^N=1$, so this does not affect the algebra at all).
- Compute the polynomial $g(x)=(x^N+1)/h(x)$.
The validity of this algorithm for finding the polynomials $h(x)$ and $g(x)$ follows from the preceding discussion as well as from the general theory of cyclic codes (telling us in advance that a prescribed polynomial $h(x)$ of degree $N-k$ exists). I am not inclined to reproduce all of it here.