Results 1 to 2 of 2

Thread: A certain distinction which is unclear to me in uniquely decodable codes

  1. #1
    Member
    Join Date
    Feb 2021
    Location
    Israel
    Posts
    1
    Thanks
    0
    Thanked 0 Times in 0 Posts

    A certain distinction which is unclear to me in uniquely decodable codes

    Example 1 :
    • codewords {0,01,11}
    • 0 is prefix of 01 -> dangling suffix is 1.
    • List {0,01,11,1}
    • 1 is a prefix of 11 -> dangling suffix is 1 - already there
    • -> The code is ud

    Example 2:

    • codewords {0,01,10}
    • 0 is prefix of 01 -> dangling suffix is 1
    • List {0,01,10,1}
    • 1 is a prefix of 10 -> dangling suffix is 0 - which is an original codeword!
    • the code is not ud.

    These 2 examples are clear to me, but I have this specfic case where it is not clear to me. In case I add 2 dangling suffixes to my list, and one is prefix of the other, thus getting another dangling suffix. This new dangling suffix is an original codeword does it mean the code is not ud?
    Example :

    • codewrods {0,01,110}
    • 0 is prefix of 01 -> dangling suffix is 1
    • List {0,01,110,1}
    • 1 is a prefix of 110 -> dangling suffix is 10
    • List {0,01,110,1,10} (this is where the misconception happens...) I have in this list 2 dangling suffixes {1,10} which are not an original codewords. and 1 is prefix of 10 -> 0 is a dangling suffix. 0 is also an original codeword thus code is not ud. Is it conventional by sardinas patterson algorithm rules to produce a dangling suffix from 2 other dangling suffixes?

  2. #2
    Administrator Shelwien's Avatar
    Join Date
    May 2008
    Location
    Kharkov, Ukraine
    Posts
    4,135
    Thanks
    320
    Thanked 1,397 Times in 802 Posts
    > Is it conventional by sardinas patterson algorithm rules to produce a dangling suffix from 2 other dangling suffixes?

    Based on https://en.wikipedia.org/wiki/Sardin...rson_algorithm I think yes.

    But in actual coding it would depend on given encoded string - some combination of symbols may be still decodable, even if the code is non-ud.

Similar Threads

  1. Library for length limited prefix codes
    By stbrumme in forum Data Compression
    Replies: 3
    Last Post: 6th February 2021, 12:17
  2. Reduced Length LZ (RLLZ): One way to output LZ77 codes
    By compgt in forum Data Compression
    Replies: 38
    Last Post: 31st August 2020, 21:06
  3. Best Compressor software to compress pure C source codes?
    By paqfan in forum Data Compression
    Replies: 3
    Last Post: 9th August 2016, 23:45
  4. Replies: 7
    Last Post: 19th August 2015, 11:08

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •