Scribd Logo
Upload

Welcome to Scribd!

  • 45 views

    Coding-Theoretic Foundations: Source Alphabet S Categories of Source Encoding

    Uploaded by

    Rhona Latanga
    1. The document discusses different methods for encoding source data into codewords, including codebook methods that assign unique codewords to symbols and global methods that transform an entire message into a single codeword. 2. It provides examples of encoding single symbols, blocks of symbols, and entire messages. Requirements for codebooks include uniqueness, length indication, and avoiding ill-designed mappings that result in non-unique decodings. 3. Graphical representations like decoding trees are used, and properties of codes like being uniquely decodable or instantaneous are important considerations. Encoding schemes for infinite or countable alphabets like natural numbers are also covered.

    Copyright:

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

    Coding-Theoretic Foundations: Source Alphabet S Categories of Source Encoding

    Uploaded by

    Rhona Latanga
    45 views12 pages
    1. The document discusses different methods for encoding source data into codewords, including codebook methods that assign unique codewords to symbols and global methods that transform an entire message into a single codeword. 2. It provides examples of encoding single symbols, blocks of symbols, and entire messages. Requirements for codebooks include uniqueness, length indication, and avoiding ill-designed mappings that result in non-unique decodings. 3. Graphical representations like decoding trees are used, and properties of codes like being uniquely decodable or instantaneous are important considerations. Encoding schemes for infinite or countable alphabets like natural numbers are also covered.

    Original Title

    2-CodingTheory.ppt

    Copyright

    © © All Rights Reserved

    Available Formats

    PPT, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    1. The document discusses different methods for encoding source data into codewords, including codebook methods that assign unique codewords to symbols and global methods that transform an entire message into a single codeword. 2. It provides examples of encoding single symbols, blocks of symbols, and entire messages. Requirements for codebooks include uniqueness, length indication, and avoiding ill-designed mappings that result in non-unique decodings. 3. Graphical representations like decoding trees are used, and properties of codes like being uniquely decodable or instantaneous are important considerations. Encoding schemes for infinite or countable alphabets like natural numbers are also covered.

    Copyright:

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

    Coding-Theoretic Foundations: Source Alphabet S Categories of Source Encoding

    Uploaded by

    Rhona Latanga
    1. The document discusses different methods for encoding source data into codewords, including codebook methods that assign unique codewords to symbols and global methods that transform an entire message into a single codeword. 2. It provides examples of encoding single symbols, blocks of symbols, and entire messages. Requirements for codebooks include uniqueness, length indication, and avoiding ill-designed mappings that result in non-unique decodings. 3. Graphical representations like decoding trees are used, and properties of codes like being uniquely decodable or instantaneous are important considerations. Encoding schemes for infinite or countable alphabets like natural numbers are also covered.

    Copyright:

    © All Rights Reserved
    Download as PPT, PDF, TXT or read online from Scribd
    Download as ppt, pdf, or txt
    You are on page 1of 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 1


    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 2


    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
    Code string 00110
    ‘b’ = 01
    results from either
    ‘c’ = 11
    ‘dca’ or ‘aaca’
    ‘d’ = 00

    SEAC-2 J.Teuhola 2014 3


    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 4


    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 5
    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 6


    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 7


    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 8


    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 9


    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 10
    Semi-fixed-length codes for numbers x
     Called also reduced block coding

    SEAC-2 J.Teuhola 2014 11


    Golomb and Rice codes
     Examples of parametric codes for numbers

    SEAC-2 J.Teuhola 2014 12

    You might also like