A code X over the alphabet A is complete if the submonoid X* generated by X meets all two-sided ideals of A*. If one measures the cost of a finite code X over A, with respect to a given information source S, by the quantity gamma(X) = <X> ln |A|, we say that X is completely optimal for S if it does not exist any code X', over an arbitrary alphabet, such that gamma (X') < gamma (X). One can show that for |X| ≤ 5 a completely optimal code has to be complete. However for |X| > 5 there exist uncomplete codes with the property of having a bounded synchronization delay and a redundancy which is minimal. From the information point of view these uncomplete codes should be preferred to the complete ones, which are such to have, except for the biprefix case, an infinite delay of deciphering in at least one direction. Moreover for some values of |X| complete biprefix codes do not exist.
@article{urn:eudml:doc:38873,
title = {On minimal redundancy codes.},
journal = {Stochastica},
volume = {6},
year = {1982},
pages = {85-102},
zbl = {0514.94018},
mrnumber = {MR0691617},
language = {en},
url = {http://dml.mathdoc.fr/item/urn:eudml:doc:38873}
}
De Luca, Aldo; Sessa, Maria I. On minimal redundancy codes.. Stochastica, Tome 6 (1982) pp. 85-102. http://gdmltest.u-ga.fr/item/urn:eudml:doc:38873/