2

Consider an alphabet of k symbols and a requirement to optimally encode a series of values of known frequency. The obvious choice for this is to use Huffman coding, which is known to be optimal for this problem. Consider now the extra requirement that when the coded values are received it will be unknown whether or not the symbols that represent them have been reversed, so for example if the coding suggests that "value 1" is encoded as "aab", it may be received at the receiving end as either "aab" or "baa". Therefore each encoding used must not have a valid encoding that contains the same symbols in reverse order.

When k > 2, one possible implementation would be to reserve one of the symbols for a 'start bit' and ensure that it is never used as the terminal symbol of any code. But are there any better approaches?

Update

Just so anyone reading this can get more of an idea what I was talking about, you can see the final implementation I wrote (using the algorithm I was suggesting above, except reversed -- I reserve a colour for the end marker and don't use it in the first symbol, as that's much easier to implement due to the way the Huffman algorithm prepends symbols to the code as it grows) here: http://periata.co.uk/shb/colourcoder.html

I'm still interested in any better ideas, if anyone can come up with one.

  • This question may be a better fit for Computer Science. That said, your problem is found in the UTF-16 text encoding which has ambiguous endianness. They solved it by reserving two symbols as a byte order mark (BOM). The code point U+FEFF is the BOM which will appear as either FEFF (→ everything correct) or FFFE (→ reverse bytes for decoding), the latter of which is otherwise reserved as an unused symbol. Using a single marker is generally more efficient than avoiding ambiguous symbols. – amon Jan 16 '17 at 11:01
  • @amon - That's a good point, I handed considered UTF's endianness markers, and clearly they solve a related problem, however I'm trying to solve in a situation where any individual code can be reversed, as each is stored separately (the application is generating colour-codes for labelling the ends of wires on different circuits, FYI). – Periata Breatta Jan 16 '17 at 11:28
  • 1
    Is the potential reversing caused by transmission/reception issue or because the sender and receiver have not agreed on the same encoding? – Erik Eidt Jan 16 '17 at 15:45
  • @ErikEidt I could be wrong, but I think these are physical wires, and the person working with them could have them flipped upside down. – Frank Hileman Jan 16 '17 at 19:55
  • Since your output is a one-dimensional array of two-dimensional objects (the coloured squares), another option would be to encode the direction on each element instead (e.g. make the bottom-third of the squares black or draw an arrow on them). – Marco Borchert Feb 2 '17 at 9:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.