Links und Funktionen
Sprachumschaltung

Navigationspfad
You are here: Home / Teaching / Winter 2016/17 / Lecture notes - WS 2016 / Convolution codes I


Inhaltsbereich

Convolution codes I

Plain Text icon Convol1.txt — Plain Text, 11 KB (12042 bytes)

File contents

Convolution codes
=================

Convolution codes are defined via their encoder which is a device for
transforming input messages to code words being sent. Unlike in the
case of block codes as we have seen them, the output, i.e., the sent
message is a function not only of the current input, but also
of earlier inputs. Often, the data sent at time t does not depend on
all previous messages at times 0,...,t, but only on messages at times
t, t-1, t-2, ..., t-M+1 for some fixed M called the *length of
influence*.

Moreover, convolution codes are still linear in the sense that if
C(xs) denotes the encoding of an infinite sequence xs=x1,x2,... of
inputs then C is a linear map on the vector space of infinite sequence
(of 0s and 1s in the (typical) case of GF(2)).

The main advantage of convolution encoders is their simple
implementation. Unfortunately, their theory is not as advanced as for
block codes; convolution codes with good error correction properties
are found by exhaustive search and are tabulated.

A (non-recursive) *convolution encoder* is determined by three
parameters (n,k,M) where n and k are the sizes of the output and input
per clock interval and M is the length of influence. In many cases one
has k=1.

In order to store the last M inputs which as we said determine the
output the convolution encoder needs M shift registers capable of
holding k bits each or M*k simple shift registers.

The n output bits are a linear function of the last M inputs and are
computed using appropriate additions modulo 2 implemented as XOR
gates.  n schliesslich ist die Zahl der pro Zeiteinheit gesendeten
Ausgangsbits.

The quotient r = k/n is the *rate* of the encoder; it must always be
less than 1.

Example for  k=1, n=2 (r=1/2), M=2

           --------->x1
          |
    ---->(+)<----
   |             |
   |             |
u--o->[D]-o->[D]-o
   |      |      |
   |      |      |
    ---->(+)<----
          |
           --------->x2


u is the input, x1 and x2 represent the output. Shift registers are
denoted [D] ("delay") and (+) is addition modulo 2 (XOR). Finally, o
represents a wire junction.

If u(l), x1(l), x2(l) are the signal u,x1,x2 at time l then 

x1(l) = u(l) +          u(l-2)
x2(l) = u(l) + u(l-1) + u(l-2)

Example: u = (1 0 0 1 1 ...)
x1 = (1 0 1 1 1 ...)
x2 = (1 0 1 1 0 ...)



Formal power series
-------------------

An entire signal is conveniently represented as a formal power series
in the unknown D ("delay"), thus

x1 = x1(0) + x1(1)D + x1(2)D^2 + ...

One then has 

x1 = u * g1
x2 = u * g2

where g1 = 1 + D^2 and g2 = 1 + D + D^2 and where * is the product of
power series:

x * y = z(0) + z(1)D + z(2)D^2 + ... + z(k)D^k + ...

where z(k) = sum_{i=0}^k x(i) y(k-i).

Here, the sequence z is known as the *convolution* of sequences x and
y, thus convolution of sequences corresponds to product of power
series.

As already mentioned convolution codes are usually defined through
their encoder. Nevertheless, it is again sometimes useful to also
regard the code as its set of codewords and without the encoder.

Definition (formal power series): Let F be a field and D a
variable. The ring F[[D]] of *formal power series comprises infinite
sequences xs=(x_0,x_1,x_2,x_3,...), where x_i:F, though of and usually
written as a power series x_0 + x_1*D+x_2*D^2+... They are added and
multiplied according to the usual rules. The ring of polynomials F[D]
is then a subring of F[[D]] consisting of those sequences xs for which
x_k=0 for almost all k.

Lemma: A polynomial p : k[D] is invertible in k[[D]]
if and only if p(0)=/=0. 

Proof: W.l.o.g. let p(0)=1 (otherwise apply lemma to p/p(0)). One has

1 / p = 1 / (1 - (1-p)) = 

1 + (1-p) + (1-p)^2 + (1-p)^3 + (1-p)^4 + ...                   (***)

Now (1-p) is a multiple of D since (1-p)(0)=0 (no constant term). As a
result, (1-p)^k has no powers of D less than k and one can expand
(***) in terms of powers of D ("multiply out").   []

Example:

p=1+D

1/p = 1 + (1-p) + (1-p)^2 + .. =
1 - D + D^2 - D^3 + D^4

Non example:

p=D

1/p = 1 + (1-D) + (1-2D+D^2) + (1-3D+3D^2-D^3) + ... = ????

Remark: one can also consider the ring of formal Laurent series which
also allow finitely many negative powers of D. This ring is actually a
field, i.e., all elements other than 0 are invertible.



Generator matrices for convolution codes
----------------------------------------

We can group the polynomials describing a convolution encoder into an
nxk matrix, thus a column vector in the case k=1.

The n-tuple of formal power series representing the output is then
obtained as the product of the input (formal power series) with that
matrix which is therefore called *generator matrix* by analogy with
the situation for block codes.

Example: the generator matrix of the convolution encoder given above is 

                  ( 1+D^2 )
             G1 = (       )
                  (1+D+D^2)

Example: The convolution encoder for the following generator matrix 

                  (1+D^2+D^3)
             G2 = (         )
                  ( 1+D+D^3 )

is 

       ---------->(+)-->(+)-->
      |            |     |
  ----o->[D]-o-[D]-o-[D]-o
      |      |           |
       ---->(+)-------->(+)-->

If one multiplies a generator matrix from the right with an invertible
(in GF(2)[[D]]) matrix then one get another generator matrix and hence
another convolution encoder which, however, generates the same
code. The association input <-> code word becomes different but the
error correction properties remain the same.

Example: multiplying  G1 from the right with 1+D yields

     (1+D+D^2+D^3)
G3 = (           )
     (  1 + D^3  )

The matrices G1 and G3 describe the same convolution code but
different encoders for that code.

Unlike G1 the generator matrix G3 is *catastrophic* (technical term) in
the sense that there exists an input of infinite weight, here (1 1 1 1
1 ...) =^= 1/(1+D), which is mapped to a codeword of finite weight
here auf ein Codewort von endlichem Gewicht, hier (1+D^2,1+D+D^2) =^=
(10100000..., 111000000....). 


Proposition: An n x 1 generator matrix is catastrophic iff its
polynomials have a common irreducible factor different from D.

Proof: Let g_1..g_n be the polynomials in the generator matrix. If
g=/=D is a factor as in the statement of the proposition then g(0)=/=0
(if g(0)=0, then D divides g so by irreducibility g would be
=D). Thus, g is invertible and the (infinite) input corresponding to
that inverse yields a codeword of finite weight.

Conversely, if a:GF(2)[[D]] \ GF(2)[D] is an input of infinite weight
with finite codeword then let p_1,...,p_n be the polynomials
corresponding to the (finite) codeword. One then has

g_i*a = p_i for i=1..n

thus D^u * a = s/t for appropriate coprime polynomials s and t where
u:N and t(0)=/=0 (begin with s=g_1, t=p_1, cancel common factors and
multiply by D "until" t(0)=/=0). Also, t cannot be constant for
otherwise a would be finite. Now, any irreducible factor u of t (which
cannot be D!) must divide g_i because D^u g_i s = p_i * t.  []

One should avoid catastrophic generator matrices as they lead to
problems with decoding.

We conclude this section with an example of a (3,2,1)-convolution code: 

u1                    x1
-------o----------------
u2     |              x2
--o---------------------
  |    |
  |    o-[D]-
  |    |     |        x3
  |     ----(+)---------
  |          |
   ---- -[D]-

Its generator matrix is

    (1    0)
    (0    1)
    (1+D  D)

Multiplication with (1 0) (subtracting the first column from the second) yields 
                    (1 1)

the following alternative generator matrix 

       (1  0)
       (0  1)
       (1  D)

whose encoder needs one shift register less. 

       
Recursive convolution encoders
------------------------------

A recursive convolution encoder feeds some of its output back into the
entry of its shift registers via an appropriate XOR logic. 

Example: 

    --------------------------------> x1
   |      ----------->(+)--->(+)----> x2
   |     |             |      |
u--o-(+)-o->[D]-o->[D]-o->[D]-o
      ^         |             |
      |--------(+)<-----------


Here we have: x1=u 
              x2=(D^2+D^3)*s
               s=u + (D+D^3)*s

with s representing the signal at the end of the first shift register. 

Rearranging yields: 

(1+D+D^3)*s = u

s = 1/(1+D+D^3)*u

x2 = (D^2+D^3)/(1+D+D^3) * u

Notice that the denominator is indeed invertible. A non-invertible
denominator could only occur with "short circuits", i.e., an XOR gate
with delayless feedback.

We thus have a generator matrix with rational entries, i.e., entries
in GF(2)[[D]] rather than GF(2)[D].


     (          1          )
G4 = (                     )
     ( (D^2+D^3)/(1+D+D^3) )

As before, the code generated remains unchanged upon multiplication
from the right with an invertible matrix. In particular, for every
recursive convolution encoder there is a non-recursive one that
generates the same code. In this example it is given by 

     ( 1+D+D^3 )
G5 = (         )
     ( D^2+D^3 )

Unlike the above recursive encoder this one is no longer "systematic"
in the sense that the input is part of the output. Notice that this
was the case for the recusive encoder.


Conversely, using recursion, i.e., feedback, it is possible to convert
any non-systematic convolution encoder into a systematic, albeit
recursive, one.

In the example

                  ( 1+D^2 )
             G1 = (       )
                  (1+D+D^2)

this would be 

                  ( 1               )
             G6 = (                 )
                  (1+D+D^2 / (1+D^2))


  ----------------------->
 |      --->(+)-->(+)---->
 |     |     |     |
-o-(+)-o-[D]-o-[D]-o
    ^              |
    |<-------------

Systematic convolution encoders are more suitable for certain
applications.  In particular, the *turbo codes* introduced in the 90s
which can be regarded as the interleaved concatenation of two
convolution codes rely on systematic convolution codes and thus use
recursive encoders.


Free distance of a convolution code
-----------------------------------

Just as in the case of block codes the minimal weight of a codeword is
a measure for the quality of a convolution code. Since convolution
codes are linear it is clear that errors of smaller weight than that
minimum can at least be detected.

Definition (free distance): The free distance of a convolution code is
the Hamming-weight of the lightest codeword.

One can read off the free distance from a statechart representing a
corresponding encoder as a Mealy machine, i.e., a finite automaton
with output.

For the generator matrix G1 this machine looks as follows: 


                  0/00
                 -----
                 \   V
                 [00]
          0/11  ^    \ 1/11
               /      \
              /  1/00  \
             /  ----->  V
            [01]      [10]
             ^  <-----  /
              \  0/01  /
         0/10  \      / 1/10
                \    V
                 [11]
                 /  ^
                 ----
                 1/01


The free distance then is the least weight of a finite path from [00]
back to itself. Such a path is given by 11 01 11 of weight 5 and it
corresponds to the input 1 0 0. It is easy to see that there is no
lighter such path and thus this code has free distance 5.

If the encoder is not catastrophic this method is guaranteed to find
the free distance for the input leading to the minimum weight codeword
must then be finite hence captured by the abovedescribed search. On the other hand, the catastrophic code given by

            (1+D)
	    (1+D)



has free distance 2 because 11 00 00 00 00 00 00 00 00 is output upon
input 1 1 1 1 1 1 1... . No finite input can generate this output or
any other of weight 2.

Free distance is related to the quality of a convolutional code but
does not have quite the same significance as for block codes because
in practice coding is stopped after a finite amount of time and the
encoding is restarted.


Document Actions


Funktionsleiste