Xem mẫu
- Digital Communications I:
Modulation and Coding Course
Period 3 - 2007
Catharina Logothetis
Lecture 10
- Last time, we talked about:
Channel coding
Linear block codes
The error detection and correction capability
Encoding and decoding
Hamming codes
Cyclic codes
Lecture 10 2
- Today, we are going to talk about:
Another class of linear codes, known as
Convolutional codes.
We study the structure of the encoder.
We study different ways for representing
the encoder.
Lecture 10 3
- Convolutional codes
Convolutional codes offer an approach to error control
coding substantially different from that of block codes.
A convolutional encoder:
encodes the entire data stream, into a single codeword.
does not need to segment the data stream into blocks of fixed
size (Convolutional codes are often forced to block structure by periodic
truncation).
is a machine with memory.
This fundamental difference in approach imparts a
different nature to the design and evaluation of the code.
Block codes are based on algebraic/combinatorial
techniques.
Convolutional codes are based on construction techniques.
Lecture 10 4
- Convolutional codes-cont’d
A Convolutional code is specified by
three parameters (n, k , K ) or (k / n, K )
where
Rc = k / n is the coding rate, determining the
number of data bits per coded bit.
In practice, usually k=1 is chosen and we
assume that from now on.
K is the constraint length of the encoder a
where the encoder has K-1 memory
elements.
There is different definitions in literatures for
constraint length.
Lecture 10 5
- Block diagram of the DCS
Information Rate 1/n
Modulator
source Conv. encoder
m = (m1 , m2 ,..., mi ,...) U = G(m)
144 44 2 3
= (U1 , U 2 , U 3 ,..., U i ,...)
Channel
Input sequence
144 2444 4 3
Codeword sequence
U i = u1i ,...,u ji ,...,u ni
14 2444 3
Branch word ( n coded bits)
Information Rate 1/n
Demodulator
sink Conv. decoder
m = (m1 , m2 ,..., mi ,...)
ˆ ˆ ˆ ˆ Z = ( Z1 , Z 2 , Z 3 ,..., Z i ,...)
144 2444 4 3
received sequence
Zi = z1i ,...,z ji ,...,z ni
{ 14 2444 3
Demodulator outputs n outputs per Branch word
for Branch word i
Lecture 10 6
- A Rate ½ Convolutional encoder
Convolutional encoder (rate ½, K=3)
3 shift-registers where the first one takes the
incoming data bit and the rest, form the memory
of the encoder.
u1 First coded bit
(Branch word)
Input data bits Output coded bits
m u1 ,u2
u2 Second coded bit
Lecture 10 7
- A Rate ½ Convolutional encoder
Message sequence: m = (101)
Time Output Time Output
(Branch word) (Branch word)
u1 u1
u1 u 2 u1 u 2
t1 1 0 0 t2 0 1 0
1 1 1 0
u2 u2
u1 u1
u1 u 2 u1 u 2
t3 1 0 1 t4 0 1 0
0 0 1 0
u2 u2
Lecture 10 8
- A Rate ½ Convolutional encoder
Time Output Time Output
(Branch word) (Branch word)
u1 u1
u1 u 2 u1 u 2
t5 0 0 1 t6 0 0 0
1 1 0 0
u2 u2
m = (101) Encoder U = (11 10 00 10 11)
Lecture 10 9
- Effective code rate
Initialize the memory before encoding the first bit (all-
zero)
Clear out the memory after encoding the last bit (all-
zero)
Hence, a tail of zero-bits is appended to data bits.
data tail Encoder codeword
Effective code rate :
L is the number of data bits and k=1 is assumed:
L
Reff = < Rc
n( L + K − 1)
Lecture 10 10
- Encoder representation
Vector representation:
We define n binary vector with K elements (one
vector for each modulo-2 adder). The i:th element
in each vector, is “1” if the i:th stage in the shift
register is connected to the corresponding modulo-
2 adder, and “0” otherwise.
Example:
u1
g1 = (111)
m u1 u 2
g 2 = (101)
u2
Lecture 10 11
- Encoder representation – cont’d
Impulse response representaiton:
The response of encoder to a single “one” bit that
goes through it.
Example: Branch word
Register
contents u1 u2
100 1 1
Input sequence : 1 0 0
010 1 0
Output sequence : 11 10 11
001 1 1
Input m Output
1 11 10 11
0 00 00 00
1 11 10 11
Modulo-2 sum: 11 10 00 10 11
Lecture 10 12
- Encoder representation – cont’d
Polynomial representation:
We define n generator polynomials, one for each
modulo-2 adder. Each polynomial is of degree K-1 or
less and describes the connection of the shift
registers to the corresponding modulo-2 adder.
Example:
g1 ( X ) = g 01) + g1(1) . X + g 21) . X 2 = 1 + X + X 2
( (
g 2 ( X ) = g 02 ) + g1( 2 ) . X + g 22 ) . X 2 = 1 + X 2
( (
The output sequence is found as follows:
U( X ) = m( X )g1 ( X ) interlaced with m( X )g 2 ( X )
Lecture 10 13
- Encoder representation –cont’d
In more details:
m( X )g1 ( X ) = (1 + X 2 )(1 + X + X 2 ) = 1 + X + X 3 + X 4
m( X )g 2 ( X ) = (1 + X 2 )(1 + X 2 ) = 1 + X 4
m( X )g1 ( X ) = 1 + X + 0. X 2 + X 3 + X 4
m( X )g 2 ( X ) = 1 + 0. X + 0. X 2 + 0. X 3 + X 4
U( X ) = (1,1) + (1,0) X + (0,0) X 2 + (1,0) X 3 + (1,1) X 4
U = 11 10 00 10 11
Lecture 10 14
- State diagram
A finite-state machine only encounters a
finite number of states.
State of a machine: the smallest amount
of information that, together with a
current input to the machine, can predict
the output of the machine.
In a Convolutional encoder, the state is
represented by the content of the
memory.
Hence, there are 2 states.
K −1
Lecture 10 15
- State diagram – cont’d
A state diagram is a way to represent
the encoder.
A state diagram contains all the states
and all possible transitions between
them.
Only two transitions initiating from a
state
Only two transitions ending up in a state
Lecture 10 16
- State diagram – cont’d
Current input Next output
0/00 Output state state
(Branch word)
S0
Input
S0 0 S0 00
1/11 00 0/11
00 1 S2 11
1/00 S1 0 S0 11
S2 S1
10 01 01 1 S2 00
0/10
S2 0 S1 10
1/01 S3 0/01 10 1 S3 01
0 01
11
S3 S1
1/10 11 1 S3 10
Lecture 10 17
- Trellis – cont’d
Trellis diagram is an extension of the state
diagram that shows the passage of time.
Example of a section of trellis for the rate ½ code
State
S 0 = 00 0/00
1/11
S 2 = 10 0/11
1/00
S1 = 01 1/01
0/10
0/01
S3 = 11 1/10
ti ti +1 Time
Lecture 10 18
- Trellis –cont’d
A trellis diagram for the example code
Input bits Tail bits
1 0 1 0 0
Output bits
11 10 00 10 11
0/00 0/00 0/00 0/00 0/00
1/11 1/11 1/11 1/11 1/11
0/11 0/11 0/11 0/11 0/11
1/00 1/00 1/00 1/00 1/00
0/10 0/10 0/10 0/10 0/10
1/01 1/01 1/01 1/01 1/01
0/01 0/01 0/01 0/01 0/01
t1 t 2 t 3 t 4
t 5 t 6
Lecture 10 19
- Trellis – cont’d
Input bits Tail bits
1 0 1 0 0
Output bits
11 10 00 10 11
0/00 0/00 0/00 0/00 0/00
1/11 1/11 1/11
0/11 0/11 0/11
0/10 1/00
0/10 0/10
1/01 1/01
0/01 0/01
t1 t 2 t 3 t 4
t 5 t 6
Lecture 10 20
nguon tai.lieu . vn