Communications of the ACM
Last byte
Optimal Chimes
Credit: Getty Images
If you have ever spent any time near a cathedral, you will recognize the rich sound of bells announcing each hour and often even the quarter hours. This puzzle asks you to a imagine living when the church bells were the only source of determining time. Specifically, imagine a country named Medievaliana whose King Meddy has decreed that at most once every 15 minutes all the churches should ring chimes in such a way that everyone within earshot would know the exact time of day to within one minute. The King Meddy, ever a stickler for precision, wants the time to be known using a 24-hour clock. So, for example, 6 P.M. would be different from 6 A.M.
It turns out the people of Medievaliana are great at counting chimes. But still, if all the chimes come in one long sequence, there seems to be no way to avoid a unary encoding. For example, 0:00 would be one chime. 0:15 would be two chimes, .... 1:00 would be 5 chimes, ...., 23:45 would be 96 chimes. That is a lot of counting.
So, King Meddy calls in a proto-computer scientist—Ms. Bin—and asks what to do. Ms. Bin asks whether the "chimers" who ring the bells can create a period of silence. The head of the chimers' guild responds that chimers can stop a ringing bell to create a gap, but if they are to start again afterward it might take a few seconds to do that and the time may vary from one chimer to another. So, basically, a chimer can guarantee the interval between successive chimes without a gap will be significantly less than the interval if there is a gap in between, but the exact length of the gap is unknown.
Ms. Bin thinks about this for a while and decides a listener can distinguish between two chimes without any gap and two chimes with a gap, but the listener should not infer anything about the length of a gap, which can range from two seconds to several. In a burst of inspiration, Ms. Bin decides to encode a chime by a 1 and a gap of any length by a 0. So, for example, a listener should be able to distinguish 11 from 101, but not 101 from 1001 (because chimers are not that precise). That is, she concludes that:
- All chiming sequences should begin and end with a 1; and
- A listener will not be able to distinguish between one and several successive 0s.
Ms. Bin is most concerned about unique decodability. It must never be the case that a given chime sequence could cause the listener to think the time is different from the actual time. So every sequence of 1s and 0s must obey the rules described here and should be unique.
Challenge: Using chimes (1) and gaps (0), can you find an encoding that conforms to the aforementioned rules and has an average duration less than 9 seconds assuming the interval between successive chimes without an intervening gap is one second and the interval between chimes having an intervening gap is (on average) two seconds?
Solution: We start with the encoding of the 15 minutes within the hour. They will all be preceded by a gap and then 00 minutes will be one chime (01), 15 minutes will be two chimes (011), 30 minutes will be three chimes (0111), and 45 minutes will be four chimes (01111). The encoding for hours is shown in the figure here. So, for example, 4:30 A.M. would be 11010111. This encoding gives an average duration of slightly less than 8.6 seconds.
Figure. The encoding for hours.
Chime Upstart. Can you find a minimum average duration uniquely decodable code under these conditions?
Chime Upstart 2. Can you find a minimum average duration uniquely decodable code assuming there can be two tones of bells in every cathedral? How about k different tones? It is still the case, however, that silences can be of varying length.
Footnotes
All are invited to submit their solutions to [email protected]; solutions to upstarts and discussion will be posted at http://cs.nyu.edu/cs/faculty/shasha/papers/cacmpuzzles.html
The Digital Library is published by the Association for Computing Machinery. Copyright © 2020 ACM, Inc.
No entries found