2
$\begingroup$

Given a binary block code $C=[n,k]$ of codeword length $n$, and dimension $k$. Suppose I've determined these properties for it : $d_{min}$ (minimum distance), $N_{dmin}$ (number of codewords at $d_{min}$), $G_{min}$ (minimum girth), and $N_{four}$ (number of 4-cylces in its Tanner graph). These are all commonly defined properties so I won't redefine them here. Now suppose that I have a new code derived from $C$ by shortening $N_s$ bits and puncturing $N_p$ bits resulting in a new $C'=[n-N_s-N_p,k-N_s]$ code what can be said about this new code? How would $d_{min}$,$G_{min}$,...change? Bounds are fine if no exact treatment is known. Any reference or survey articles would be really appreciated.

$\endgroup$

1 Answer 1

3
$\begingroup$

Here is an answer that says (at least for $d_{\mathrm{min}}$) we cannot say much meaningful unless we know more about the specific code. For a moment let's forget about shortening and concentrate of minimum distance and puncturing. Puncturing will either leave minimum distance fixed or decrease by exactly $1$. Both are possible; so, we can say $d_{\mathrm{min}} - N_p \leq d'_{\mathrm{min}} \leq d_{\mathrm{min}}$ in the case of only puncturing.

Since shortening is expurgating (removing codewords) which may increase the minimum distance followed by puncturing which may decrease the minimum distance it is hard to say what will happen. Consider $C = \{0^n,10^{n-1},01^{n-1},1^n\}$ which has minimum distance $d'_{\mathrm{min}} = 1$. We can shorten $C$ to obtain $C' = \{0^{n-1}, 1^{n-1}\}$ which has $d'_{\mathrm{min}} = n-1$. We will still have a lower bound $d_{\mathrm{min}} - N_s - N_p \leq d'_{\mathrm{min}}$, but $d'_{\mathrm{min}}$ can become large.

I will think more if something can be said about your other quantities.

$\endgroup$
3
  • $\begingroup$ nice answer, also, something like cycles in Tanner graph will be even harder to say something about. $\endgroup$
    – kodlu
    Jun 14, 2016 at 0:54
  • $\begingroup$ @kodlu Thanks. I imagine all will be hard to make a statement about in general. Perhaps under a certain hypothesis something can be said. $\endgroup$ Jun 14, 2016 at 1:08
  • $\begingroup$ it seems that both puncturing and shortening can only break cycles so I would think $N_{four}' \leq N_{four}$...but I might be overlooking something. $\endgroup$
    – unknown
    Jun 14, 2016 at 1:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.