>I suspect it's much easier to handle 4-bit words.

I therefore suspect a 3-bit encoding would be more in the spirit of BrainFuck. :)