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?
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.