Member Avatar for lord12

A code is ambiguous when there exists a message using that code that can be partitioned into
different sequences of code words. In other words, in an ambiguous code a message may have
more than one meaning. For example, consider the binary alphabet, composed of symbols
{0,1}. For the code composed of the words {10, 01, 101} the message 10101 can be understood as 10-101 or 101-01 and therefore the code is ambiguous. On the other hand, for the code composed of the words {01, 10, 011} no ambiguous message exists and therefore the code is unambiguous.

I dont' understand how 11011 cannot be interpreted as 11-011 and 110-11. Isn't this ambiguous?

  • 3 Contributors
  • 4 Replies
  • 207 Views
  • 7 Hours Discussion Span
  • Latest Post Latest Post by VernonDozier

Dani AI

Generated

Short answer: is right — those partitions are not valid decodings because the pieces you want to split into are not codewords. Ambiguity means: there exist two different sequences of legal codewords whose concatenation is the same bit-string. If a proposed split uses a fragment that isn't in the codebook, it doesn't count.

A couple of useful clarifications:

  • "Ambiguous" = at least two distinct legal sequences of codewords produce the same message.
  • "Prefix-free" is a stronger property: no codeword is the prefix of another. Every prefix-free code is uniquely decodable, and decoding is simple and deterministic (greedy).
  • A code can be uniquely decodable without being prefix-free; greedy decoding may fail in that case, so you need a different test.

If you can make the code prefix-free, decoding is easy. Example greedy decoder (works only when no codeword is a prefix of another):

public static List<String> decodePrefixFree(String bits, Set<String> codebook) {
    List<String> out = new ArrayList<>();
    int i = 0;
    while (i < bits.length()) {
        boolean matched = false;
        for (int j = i + 1; j <= bits.length(); j++) {
            String sub = bits.substring(i, j);
            if (codebook.contains(sub)) {
                out.add(sub);
                i = j;
                matched = true;
                break;
            }
        }
        if (!matched) throw new IllegalArgumentException("no valid decoding at position " + i);
    }
    return out;
}

For a general test of unique decodability use the Sardinas–Patterson procedure: iteratively build the set of non-empty remainders obtained by removing prefixes; if the empty string ever appears the code is ambiguous; if the remainder set repeats without producing empty, the code is uniquely decodable. Practical advice: when designing codebooks (compression, protocols) prefer prefix-free sets (e.g., Huffman-style) to keep decoding simple and provably unambiguous.

Recommended Answers

All 4 Replies

Member Avatar for VernonDozier

Neither 11 nor 110 is a legal word in your word set of {01, 10, 011} so neither 11-011 nor 110-11 are legal messages. Am I misunderstanding the rules?

Member Avatar for lord12

thanks!

Member Avatar for roshanxi

hi i am new to java.can u plz kindly tell me how to use conditions in case of a switch in java?

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.