# Decoding BCH codes with permuted parity-check matrix

A normal t-error correcting $BCH(n,k)$ code over $GF(2^m)$ would be constructed using a generator polynomial g(x), which is the LCM of the minimal polynomials of $a,a^2,..a^{2t}$, with $a$ being a primitive element of $GF(2^m)$ with the understanding that $a^x$ and $a^{2x}$ are conjugates.

A code constructed like this would have a parity check matrix $H[2t*n]$ whose row $r$ would be

$H[r] = [a^{r*(n-1)} a^{r*(n-2)} ... a^{r*1} a^0]$

I came across a variation of this standard BCH code that uses a column permuted version of the aforementioned array H as the parity check matrix. This means that the new parity check matrix $H'$ contains the same columns as H, but in a different order. The order itself is specified and known, but it doesn't follow any obvious pattern. The codewords defined by $H'$ would then be permutations of the codewords defined by $H$.

I am trying to understand the possible advantages of using a permuted parity check matrix, and whether it might be possible in certain cases to locate more than $t$ bit errors in a codeword that belongs to the code defined by the parity check matrix $H'$. Any help would be greatly appreciated.

Thanks,
Dimitri

## 1 Answer

If I understood the question correctly, the order of the bits in the words of the resulting code is permuted, and all the words are reordered according to the same permutation.

Such a permutation is an isometry (w.r.t. the Hamming metric) of the ambient vector space $GF(2)^n$. Therefore the resulting code has the same minimum distance, the same weight distribution, and hence the same error-correcting capability. For such reasons permuted versions of codes are called equivalent, and an algebraist/combinatorialist working on codes is likely to think of them as the "same" code for all purposes.

But, there may be something else at play. Reordering the bits like this leads to different collections of partial codewords. This can be exploited in some soft-error-correcting algorithms. For example, such tinkering can reduce the size of the trellis representation of the BCH-code. I made an attempt at describing the trellis diagram of a linear block code in this answer. I'm not up to speed with the latest developments, but I have the impression that you cannot bring down the trellis state complexity of a longish BCH-code enough to make full Viterbi feasible. May be if you don't traverse all of the trellis? IIRC a method for reducing the complexity of the trellis diagram of a BCH-code amounts to using a bit ordering such that the $r=1$ row has adjacent blocks forming cosets of a linear subspace of $GF(2^m)$. I don't know if other ideas have been developed, sorry.

Such permutations also play a role in the McEliece cryptosystem, but that does not seem to fit with the other bits you said.