2
$\begingroup$

Setup reminder: linear block error-correcting code is some linear subspace $C$ in $F_2^N$. (Correcting error means to find a point $c \in C$ which is "nearest" to a given $r$ in $F_2^N$, $r$ is signal with "errors").

Consider two codes which are given as images of some operators: $A: F_2^k \to F_2^L$, $B: F_2^L \to F_2^N$. Define the code which is "superposition" - image of $BA$.

General question What can be said about the properties of "superposition" code in terms of properties $A$ and $B$ ? E.g. how to construct decoding algorithm for it ? How to estimate error probability ? How to estimate minimal Hamming distance of this code ?

Specific question Consider code $A$ is just adding CRC bit: i.e. $A: (x_1, ..., x_n) \to (x_1, ..., x_n, \sum x_i)$.

And $B$ is some tail-bited convolutional code (say rate 1/2) which means it is given by $( \bar y ) \to ( T_1 \bar y , T_2 \bar y) $ where $T_1, T_2$ are some circulant matrices with only few non-zero diagonals.

How to estimate minimal Hamming distance of this code ?

How to decode such a code ?

The problem is that Viterbi algorithm used for decoding convolutional codes is based on "local" structure of the circulant matrices, while adding the CRC breaks the locality...

How to estimate error probabilty for such a code ? (Say in AWGN channel)

Improve this question
$\endgroup$
4
  • $\begingroup$ Your CRC can correct a single error (syndrome look up), which is a live possibility, if the Viterbi output has an odd weight (all the words that pass the CRC have an even weight). You can further improve upon that by trying Forney's soft decision decoding (if you have SOVA output at hand): try the effect of swapping one or two (according to the parity) least reliable bits, and see, if you can now correct a remaining error by syndrome look up. Forney had a more general scheme, but as your CRC can only correct a single error, I think his algorithm amounts to just that. $\endgroup$
    – Jyrki Lahtonen
    Commented Jul 11, 2012 at 6:44
  • $\begingroup$ @Jyrki thank you very much ! I'll try but it takes time I am novice. By the way I just understood the following problem with List Viterbi - it does NOT create optimal list (at least in theory), I mean of course Viterbi best path is optimal paths, but second path in list may not be actually second path in true list - the reason is that all members in the list will be more or less the same at the initial N-(6*TrellisLen) bits... So it seems to me that List Viterbi have some space of improvement $\endgroup$
    – Alexander Chervov
    Commented Jul 11, 2012 at 7:32
  • $\begingroup$ Alexander: I forgot to say that "concatenation" of codes (instead of "superposition") is the standard term. So you may have better luck searching for more information using "concatenated codes" as a buzzword. The combinations that I have seen are convolutional+algebraic (such as here) or LDPC+algebraic. An algebraic code is a common choice as the last code, because they can effectively deal with a small number of errors, but are bad at dealing with soft errors. The code exposed to the horrors of radio propagation should always be able to deal with soft errors. $\endgroup$
    – Jyrki Lahtonen
    Commented Aug 6, 2012 at 10:06
  • $\begingroup$ Thank you! Does concatenation exactly means what I mentioned? $\endgroup$
    – Alexander Chervov
    Commented Aug 6, 2012 at 10:19

1 Answer 1

Reset to default
2
$\begingroup$

You do know how to calculate the minimum distance (=free distance?) of a convolutional code? Cut the first edge from the zero state to the zero state (to disallow the all zeros word), and run Viterbi (but counting the weight, or distance to the all zero word) to the point, where all the states have surviving minimal path of weight at least the weight of the surviving path back to the zero state. I guess this can be tweaked to cover your simplest case of a single parity check bit. Essentially now the "legal" inputs to the convolutional encoder are all the even weight sequences. So in the above algorithm we need to double the state complexity as follows. For each state we maintain two penalties: one for paths of an odd input weight and another for even input weights. Then when you run an iteration of Viterbi algorithm you match the parities according to the value of the new input bit. The stopping condition now applies to both variants of the penalty function, but comparisons are to be made only to the penalty of even input weight paths leading to the zero state.

It should be possible to also enumerate words corresponding to even input weights by a suitable variant of the transfer function or some such generating function.

How to decode? The first possibility that comes to mind is to replace the usual Viterbi algorithm with soft-output Viterbi algorithm (aka SOVA) that outputs, not the most likely path, but instead probabilities for each individual bits (often written as log-likelihood-ratios $LLR_i=\ln (P(b_i=0)/P(b_i=1))$, but that may not be needed here). Then if the sequence of bit values corresponding to the more likely choice has an even weight, you accept that. If that sequence has an odd weight, you flip the least reliable bit.

[Edit:] Arrgh! I only noticed after rereading that you were interested in tailbiting codes. The above method for calculating the minimum Hamming weight no longer works. There may be too many pseudocodewords. I'm sure that some algorithms have been developed to attack this, but cannot describe one. The decoding, surprisingly, may not be affected too much by tailbiting. I would begin by studying the sections on tailbiting convolutional codes in Johannesson & Zigangirov's book.

Improve this answer
$\endgroup$
7
  • $\begingroup$ If you use a more complicated CRC (not just a single parity bit), then decoding may become quite complex. An appealing solution then would be to use, instead of a standarda CRC, a suitable error-correcting block code, like a BCH-code. The BCH-code will then correct a couple of residual bit errors (if any), and decoding failure will give a very satisfactory certificate about the correctness of the data. IOW the BCH-code would act as both an error-correcting code and as an error-detecting code. $\endgroup$
    – Jyrki Lahtonen
    Commented Jul 10, 2012 at 8:33
  • $\begingroup$ @Jyrki Lahtonen Thank you very much ! Let me think. Well, actually my CRC is not so simple - it is 24dat+16CRC given by g= x^16+x^12+x^5+1, can something be done in this case ? PS I wrote this comment before yours comment appeared :) $\endgroup$
    – Alexander Chervov
    Commented Jul 10, 2012 at 8:36
  • $\begingroup$ What is "IOW" ? $\endgroup$
    – Alexander Chervov
    Commented Jul 10, 2012 at 8:37
  • $\begingroup$ IOW="In other words". $\endgroup$
    – Jyrki Lahtonen
    Commented Jul 10, 2012 at 9:17
  • $\begingroup$ Are you stuck with that CRC-polynomial? Is that really the recommended CRC for short data segments like this? As you are planning on using the CRC-bits, at least partly, for error-correction as well, a case can be made for using a generator polynomial of a suitable cyclic code. But in either case, I don't see an efficient way of using soft inputs, and would just use a hard decision decoder on the output of plain Viterbi (cannot use SOVA). The trellis representations of mid-rate codes such as this have a tendency to blow up on your face in terms of complexity. $\endgroup$
    – Jyrki Lahtonen
    Commented Jul 10, 2012 at 9:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .