Scribd Logo
Upload

Welcome to Scribd!

  • 39 views

    2 CodingTheory

    Uploaded by

    Rhona Latanga
    This document discusses coding theory foundations and different categories of source encoding. It describes: 1. Codebook methods that assign codewords to symbols using an explicit or implicit codebook that can be static or dynamic. 2. Global methods that transform the whole message into a single computed codeword without an explicit correspondence between symbols and code bits. 3. Requirements for codebooks including uniqueness, length indication, and examples of well-designed and ill-designed codebooks.

    Copyright:

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

    2 CodingTheory

    Uploaded by

    Rhona Latanga
    39 views12 pages
    This document discusses coding theory foundations and different categories of source encoding. It describes: 1. Codebook methods that assign codewords to symbols using an explicit or implicit codebook that can be static or dynamic. 2. Global methods that transform the whole message into a single computed codeword without an explicit correspondence between symbols and code bits. 3. Requirements for codebooks including uniqueness, length indication, and examples of well-designed and ill-designed codebooks.

    Original Title

    2-CodingTheory

    Copyright

    © © All Rights Reserved

    Available Formats

    PPT, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document discusses coding theory foundations and different categories of source encoding. It describes: 1. Codebook methods that assign codewords to symbols using an explicit or implicit codebook that can be static or dynamic. 2. Global methods that transform the whole message into a single computed codeword without an explicit correspondence between symbols and code bits. 3. Requirements for codebooks including uniqueness, length indication, and examples of well-designed and ill-designed codebooks.

    Copyright:

    © All Rights Reserved
    Download as PPT, PDF, TXT or read online from Scribd
    Download as ppt, pdf, or txt
    39 views12 pages

    2 CodingTheory

    Uploaded by

    Rhona Latanga
    This document discusses coding theory foundations and different categories of source encoding. It describes: 1. Codebook methods that assign codewords to symbols using an explicit or implicit codebook that can be static or dynamic. 2. Global methods that transform the whole message into a single computed codeword without an explicit correspondence between symbols and code bits. 3. Requirements for codebooks including uniqueness, length indication, and examples of well-designed and ill-designed codebooks.

    Copyright:

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

    2.

    Coding-Theoretic Foundations
     Source alphabet S  Target alphabet {0, 1}

     Categories of source encoding:


    1. Codebook methods: Symbols (S)  Codewords (W)
    - Implicit / explicit codebook
    - Static / dynamic codebook
    - Original/extended alphabet

    2. Global methods:
    - The whole message is transformed into a single
    computed codeword.
    - No explicit correspondence between source symbols
    and code bits .

    SEAC-2 J.Teuhola 2014 13


    Illustration of coding approaches

    Encode single Encode blocks Encode the message


    symbols of symbols as a single block

    Source message Source message Source message

    Codewords Codewords Codeword

    SEAC-2 J.Teuhola 2014 14


    Requirements of a codebook

     Uniqueness: si  sj  C(si)  C (sj)


    Sufficient for fixed-length codes
     Length indication: required for variable-length codes.
    Alternatives:
     Length prefixes the actual code (but length must also be coded …)
     ‘Comma’ = special bit combination indicating the end
     Carefully selected ‘self-punctuative’ codewords
     Example of an ill-designed codebook:
    ‘a’ = 0
    ‘b’ = 01 Code string 00110
    ‘c’ = 11 results from either
    ‘d’ = 00 ‘dca’ or ‘aaca’

    SEAC-2 J.Teuhola 2014 15


    Graphical representation of a codebook

    Decoding tree (decision tree)


     Left son = bit 0, right son = bit 1
     Prefix-free code: Binary tree (usually complete);
    each symbol is represented by a path from the root
    to a leaf, e.g.:
    ’a’
    0
    Code table:
    0 ’b’
    ’a’ = 0
    1
    ’b’ = 10 0 ’c’
    ’c’ = 110 1
    ’d’ = 111 1
    ’d’

    SEAC-2 J.Teuhola 2014 16


    Properties of codes

     Some general codebook categories:


     Uniquely decodable (decipherable) code
     Prefix-free code (= prefix code)
     Instantaneous code

     Kraft inequality: An instantaneous codebook W exists if


    and only if the lengths {l1, ..., lq} of codewords satisfy
    q
    1

    i 1 2
    li  1

     MacMillan inequality: Same as Kraft inequality for any


    uniquely decodable code.
     Important: Instantaneous codes are sufficient.

    SEAC-2 J.Teuhola 2014 17


    Infinite, countable alphabet

     E.g. Natural numbers 1, 2, 3, … without limit


     No explicit codebook
     Codes must be determined algorithmically
     Requirements:
     Effectiveness: There is an effective procedure to decide,
    whether a given codeword belongs to the codebook or not.

     Completeness: Adding a new code would make the codebook


    not uniquely decipherable.

    SEAC-2 J.Teuhola 2014 18


    Application of coding arbitrary numbers

     Run-length coding (Finnish: ‘välimatkakoodaus’):


    Binary string, 0’s and 1’s clustered, cf. black&white images
     Two possible numberings:
     Alternating runs of 0 and 1

    0 0 0 1 1 0 0 0 0 1 0 1 0 0 1 1 1

    3 2 4 1 1 1 2 3

     Runs of 0’s ending at 1:


    0 0 0 1 1 0 0 0 0 1 0 1 0 0 1 1 1

    3 0 4 1 2 1 1

    SEAC-2 J.Teuhola 2014 19


    Encoding of natural numbers (P. Elias)

     -coding: Unary code; not efficient enough (not


    universal).

     -coding: Normal positional representation + end symbol


    (ternary alphabet).

     -coding: Positional representation with -coded length


    as prefix.

     -coding: Positional representation with -coded length


    as prefix.

     -coding: Recursive representation of lengths

    SEAC-2 J.Teuhola 2014 20


    Example codings of natural numbers
    Number -code -code -code -code
    1 1 11 1 1
    2 01 011 010 0100
    3 001 1011 011 0101
    4 0001 0011 00100 01100
    5 00001 01011 00101 01101
    6 000001 10011 00110 01110
    7 0000001 101011 00111 01111
    8 00000001 00011 0001000 00100000
    … … … … …

    SEAC-2 J.Teuhola 2014 21


    Example of robust universal coding
     Zeckendorf coding (called also Fibonacci coding)
     Number representation using a Fibonacci ’base’
    Number Weights for Code
    8 5 3 2 1
    1 0 0 0 0 1 11
    2 0 0 0 1 0 011
    3 0 0 1 0 0 0011
    4 0 0 1 0 1 1011
    5 0 1 0 0 0 00011
    6 0 1 0 0 1 10011
    7 0 1 0 1 0 01011
    8 1 0 0 0 0 000011
    9 1 0 0 0 1 100011
    10 1 0 0 1 0 010011
    11 1 0 1 0 0 001011
    12 1 0 1 0 1 101011
    SEAC-2 J.Teuhola 2014 22
    Semi-fixed-length codes for numbers x

     Called also reduced block coding

    SEAC-2 J.Teuhola 2014 23


    Golomb and Rice codes

     Examples of parametric codes for numbers

    SEAC-2 J.Teuhola 2014 24

    You might also like