most recent 30 from http://mathoverflow.net 2013-06-20T11:35:14Z http://mathoverflow.net/feeds/question/101826 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/101826/error-correcting-codes-obtained-as-superposition-of-two-codes-e-g-crcconvolutio Alexander Chervov 2012-07-10T06:07:15Z 2012-07-10T08:30:02Z

<p>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"). </p> <p>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$. </p> <p><strong>General question</strong> 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 ?</p> <p><strong>Specific question</strong> Consider code $A$ is just adding CRC bit: i.e. $A: (x_1, ..., x_n) \to (x_1, ..., x_n, \sum x_i)$.</p> <p>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.</p> <p>How to estimate minimal Hamming distance of this code ? </p> <p>How to decode such a code ?</p> <p>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...</p> <p>How to estimate error probabilty for such a code ? (Say in <a href="http://en.wikipedia.org/wiki/AWGN" rel="nofollow">AWGN</a> channel)</p>

http://mathoverflow.net/questions/101826/error-correcting-codes-obtained-as-superposition-of-two-codes-e-g-crcconvolutio/101833#101833 Jyrki Lahtonen 2012-07-10T08:22:58Z 2012-07-10T08:30:02Z

<p>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.</p> <p>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.</p> <p>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.</p> <p>[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 &amp; Zigangirov's book.</p>