Scribd Logo
Upload

Welcome to Scribd!

  • 61 views

    Convolution Codes

    Uploaded by

    krishna
    It contains basic information about Convolution Codes used in wireless communications for security purposes.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Convolution Codes

    Uploaded by

    krishna
    61 views14 pages
    It contains basic information about Convolution Codes used in wireless communications for security purposes.

    Original Title

    MCWC_ALA

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    It contains basic information about Convolution Codes used in wireless communications for security purposes.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    61 views14 pages

    Convolution Codes

    Uploaded by

    krishna
    It contains basic information about Convolution Codes used in wireless communications for security purposes.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 14

    2170710

    CONVOLUTION
    CODES

    Submitted By: Guided By:


    Krishna Vyas(151123107009) Prof. Abhijitsinh Parmar
    Kiran Maniya(151123107003) Assistant Professor,
    Sejal Singh(141120107048) PSE,Surat.
    INDEX

    Introduction to Convolution Codes


    Basic Concepts
    State Diagram Representation
    Tree Diagram Representation
    Trellis Diagram Representation
    Viterbi Algorithm
    Conclusion
    INTRODUCTION TO CONVOLUTION CODES

    History: Convolutional codes were introduced in 1955 by Peter Elias. It was thought that convolutional
    codes could be decoded with arbitrary quality at the expense of computation and delay. In 1967 Andrew
    Viterbi determined that convolutional codes could be maximum-likelihood decoded with reasonable
    complexity using time invariant trellis based decoders the Viterbi algorithm. Other trellis-based
    decoder algorithms were later developed, including the BCJR decoding algorithm.

    Block codes are one of the two widely used categories of error correcting codes for wireless
    transmission; the other is convolution codes.

    The Convolution Codes is defined by three parameters: n,k and k. An (n,k,K) code process input data k
    bits at a time and produces an output of n bits for each incoming k bits.

    The difference between block codes and convolutional codes is the encoding principle. The difference is
    that convolution codes have memory, which is characterized by the constant factor K. In essence, the
    current n-bit output of an (n,k,K) code depends not only on the value of the current block of k input bits
    but also on the previous K-1 blocks of k input bits. Hence the current output of n bits is a function of the
    last K x k input bits.

    In the block codes, the information bits are followed by the parity bits. In convolutional codes the
    information bits are spread along the sequence. That means that the convolutional codes map
    information to code bits not block wise, but sequentially convolve the sequence of information bits
    according to some rule.
    INTRODUCTION TO CONVOLUTION CODES

    The code is defined by the circuit, which consists of different number of shift registers allowing building
    different codes in terms of complexity.

    Application:

    Convolutional codes are used extensively to achieve reliable data transfer in numerous applications, such
    as digital video, radio, mobile communications and satellite communications. These codes are often
    implemented in concatenation with a hard-decision code, particularly Reed Solomon. Prior to turbo
    codes such constructions were the most efficient, coming closest to the Shannon limit.

    Convolution Codes provide good performance in noisy channels where a high proportion of the bits are in
    error. Thus, they have found increasing use in wireless applications.

    Block codes typically have algebraic decoders. These decoders operate on hard decisions (0s and 1s,
    or equivalents)

    Convolutional decoders can use soft-decision decoding. Decoder inputs are continuous-valued (or
    quantized values); for instance, the correlator output for BPSK Soft-decision decoding gives a 2-3 dB gain
    over hard decision decoding (2.2 dB for coherent communication)
    BASIC CONCEPTS:

    A convolutional code is generated by passing the information sequence to be transmitted through a


    linear finite-state shift register. In general, the shift register consists of K (k-bit) stages and n linear
    algebraic function generators.
    BASIC CONCEPTS:

    Convolutional codes

    k = number of bits shifted into the encoder at one time (k=1 is usually used!!)

    n = number of encoder output bits corresponding to the k information bits

    Rc = k/n = code rate

    K = constraint length, encoder memory.

    Each encoded bit is a function of the present input bits and their past ones.

    Note that the definition of constraint length here is the same as that of Shu Lins, while the shift registers
    representation is different.
    STATE DIAGRAM REPRESENTAION

    The operation of a convolutional encoder can be explained in several but equivalent ways such as, by a)
    state diagram representation, b) tree diagram representation and c) trellis diagram representation.

    a) State Diagram Representation


    A convolutional encoder may be
    defined as a finite state machine.
    A new input bit causes a transition
    from one state to another. The path
    info. between the states, denoted as
    b/c1c2, represents input information
    bit b and the corresponding output
    bits (c1c2).

    a 0 a a 1 c

    b 0 a b 1 c

    c 0 b c 1 d

    d 0 b d 1 d Figure:Tree diagram for rate 1/3, K=3 convolutional code.


    TREE DIAGRAM REPRESENTAION

    b) Tree Diagram Representation

    Note that the tree diagram in the right repeats itself after the

    third stage.

    This is consistent with the fact that the constraint length K=3.

    The output sequence at each stage is determined by the input

    bit and the two previous input bits.

    In other words, we may sat that the 3-bit output sequence for

    each input bit is determined by the input bit and the four possible

    states of the shift register, denoted as a=00, b=01,c=10, and d=11.

    Figure: Tree diagram for rate 1/3, K=3 convolutional code.


    TRELLIS DIAGRAM REPRESENTAION

    C) Trellis Diagram Representation

    The trellis diagram of a convolutional code is obtained from its state diagram.

    All state transitions at each time step are explicitly shown in the diagram to retain the time dimension, as
    is present in the corresponding tree diagram.

    Usually, supporting descriptions on state transitions, corresponding input and output bits etc. are labeled
    in the trellis diagram.

    It is interesting to note that the trellis diagram, which describes the operation of the encoder, is very
    convenient for describing the behavior of the corresponding decoder, especially when the famous Viterbi
    Algorithm (VA) is followed.
    TRELLIS DIAGRAM REPRESENTAION

    Figure: Tree diagram for rate 1/3, K=3 convolutional code.


    VITERBI ALGORITHM

    The very popular decoding algorithm for convolutional codes, used in GSM standard for instance, is the
    Viterbi algorithm. It uses the Maximum likelihood decoding principle. The Viterbi algorithm consists of
    the following steps for each time index [1]:

    1. For all S state nodes at time step j, j = 0,1,., L / N -1:


    Compute the metrics for each path of the trellis ending in the state node. The metric at the next state
    node is obtained by adding the path metric to the metric at the previous corresponding state node.
    The path metric is obtained by the following formula, :
    = 1 1 + 2 2
    where x is the sent bit, y is the received bit

    If the two paths merge, choose the one with the largest metric, the other one is discarded. If the metrics
    are equal, the survivor path is chosen by some fixed rule.
    2. If the algorithm processed d trellis sections or more, choose the path with the largest metric, go back
    through the trellis and output the code bit sequence and the information bit sequence. The parameter
    d is the decision delay of the algorithm and specifies how many received symbols have to be
    processed until the first block of decoded bits is available. As a rule of thumb, the decision delay is
    often set to 5 M .
    VITERBI ALGORITHM
    VITERBI ALGORITHM

    Example of Viterbi Algorithm:


    Input data : m =1 1 0 1 1
    Codeword : X = 11 01 01 00 01
    Received code : Z = 11 01 01 10 01
    CONCLUSION

    Convolutional codes are very easy to implement. Convolutional codes use smaller codewords
    in comparison to block codes, achieving the same quality. The advantage is that to decode
    them all only one decoder is needed and adaptive coding scheme can be thus implemented.
    One of the most important decoding algorithms is the Viterbi algorithm that uses the principle
    of maximum likelihood decoding. The Viterbi decoding uses hard decisions is therefore very
    vulnerable to error bursts. Using Soft instead of Hard decisions for Viterbi decoding improves
    the performance.

    You might also like