© 1985 by British Computer Society
| ||||||||||||||||||||||||||||||||||||||||||||||||||
The Construction of Variable-length Comma-Free Codes
Department of Computing, University of Lancaster, Bailrigg, UK
A method is presented, using finite state models, to design and investigate comma-free codes. The Scholtz method, which will produce maximal comma-free codes for odd fixed codeword lengths, is restated as an algorithm using finite state models. The algorithm is extended, taking advantage of finite state model techniques, to produce finite state generators from which families of comma-free codes in compact representation can be derived. The algorithm is further extended to allow for the design of more general finite state generators as a basis from which to design comma-free codes with codewords of variable length. These may include codewords of unlimited length of codewords with odd or even upper limits on length. Maximal codes cannot be guaranteed for even-length upper limits, but comma-freeness can be assured by considering the G-sets previously discussed by Llewellyn. Results are presented for simple families of binary codes, for a compact ‘maximal’ code for up to 10-bit codewords and a ‘near maximal’ code for up to 12-bit codewords.
* Department of Computing, University of Lancaster, Bailrigg, Lancaster LA1 4YN