paper a day : Recovery of Time Encoded Bandlimited Signals

Perfect Recovery and Sensitivity Analysis of Time Encoded Bandlimited Signals
Aurel A. Lazar and László T. Tóth
IEEE Transactions on Circuits and Systems – I: Regular Papers, vol. 51, no. 10, October 2004

I heard about this paper from Prakash Narayan, who came to give a seminar at last semester, and I thought it was pretty interesting. In an undergrad signals and systems class we usually spend most of our time talking about converting an analog signal x(t) into a discrete-time signal x[n] by sampling x(t) regularly in time. That is, we set x[n] = x(nT) for some sampling interval T. There are at least two reasons for doing things this way: it’s simple to explain and the math is beautiful. If x(t) is a bandlimited signal, it’s Fourier transform has support only on the interval [-B,B], and the famous Nyquist–Shannon sampling theorem (which goes by many other names) tells us that if 1/T > 2 B the original signal x(t) is recoverable from the sequence x[n]. Since there is all of this beautiful Fourier theory around we can convolve things and show fun properties about linear time-invariant systems with the greatest of ease.

So far so good. But sampling is only half the story in Analog to Digital conversion. Not only should the times be discretized, but the values should also be discretized. In this case we need to use a quantizer on the samples x[n]. Fast, high precision quantizers are expensive, especially at low power. On the other hand, clocks are pretty cheap. The suggestion in this paper is to think about time-encoding mechanisms (TEMs), in which we encode a bandlimited x(t) into a sequence of times {tk}. Another way to think about it is as a signal z(t) taking values +b or -b and switching values at the times {tk}. The disadvantage of this representation is that linear operations on analog signals don’t turn into linear operations on the discrete signals. However, this conversion can be implemented with an adder, integrator, and a noninverting Schmitt trigger that detects when the output of the integrator passes a threshold.

TEM Figure

This paper shows that the circuit above can be implemented in real time and that {tk} are sufficient to reconstruct x(t). The recovery algorithm looks pretty simple — multiplication by a certain pseudoinverse matrix. The second part of the paper deals with the stability of the system with respect to errors in the decoder parameter or time quantization. The compare the scheme to irregular sampling algorithms. The tools they use for this analysis come from non-harmonic analysis, but the math isn’t all that rough.

This work is different than the sampling with a finite rate of innovation work of Vetterli, Marziliano, and Blu, which says (loosely) that regular sampling is good for a wider class of signals than bandlimited signals. It would be interesting to see if a TEM mechanism is good for those signals as well. That might be another robustness issue to explore.

Finally, one interesting connection (and possible another motivation for this work) is that neurons may be doing this kind of time encoding all the time. The integrate-and-fire model of a neuron is, from a black-box perspective, converting an input signal into a sequence of times, just like a TEM.

Choral Internet Radio?

Since I’ve all but abandoned choral singing this year in favor of writing my thesis (and boy does it bum me out), I’m at least trying to get more new old music in my ears. I tend to forget the iPod at home so I’ve turned to internet radio. For a while I was listening to KALX, but it’s not conducive to writing. For a while I was hooked on SomaFM, but no station there is quite what I want to listen to, ever. Then I turned to KKJZ in Long Beach for my jazz fix. I highly recommend it. Anuraag seems to be good for Indian classical music, but there must be other ones out there.

Now I’m itching for some good old vocal polyphony. Chant will do in a pinch. I came across this Choral Treasure station which is ok, but are there alternatives. Perhaps this is something Choralista should be able to tell me about, hmmmm?

[UPDATE: I can’t complain about any radio station that plays the whole Missa Papae Marcelli, so I hope I don’t sound like I’m dissatisfied with Choral Treasure…]

furoshiki madness!

Via Lifehacker, I learned about Furoshiki, a traditional Japanese cloth wrapping. You’re less likely to get paper cuts than with origami, but you still get the fun schematic diagrams.
Apparently the Japanese Environment minister (they have an environment minister? Is that essentially the Dept. of the Interior?) wants to promote the use of them. Although you can buy them from vendors, it’s the sort of thing that screams “DIY.”

Berkeley EECS makes TA-ing more cushy

At the end of last semester I got a memo from our department trying to make TA-ing a more attractive prospect. In reality, a grad student in EECS is a TA here (or Graduate Student Instructor (GSI)) for one of three reasons : they’re a first-year and don’t have an advisor (yet), their advisor is low on funds or doesn’t have funds for their particular project, or they are fulfilling their teaching requirement to graduate (one semester only). The difference between being paid as a TA and as a research assistant (Grad Student Researcher (GSR)) is significant — the union negotiates the pay scale for GSIs, and the University is not going to let salaries rise if they can help it. In some instances a student’s advisor can bump up their salary to the GSR level. So now the department recommends:

  • If you are doing research the same semester you’re teaching, your advisor should give you a partial GSR to help out.
  • You can be appointing as a 100% GSR during winter break if you are around.
  • If your advisor can’t afford to pay you and you are GSI-ing to fulfill the graduation requirement, then the department will give you a unconstrained fellowship.

All in all, it’s seems like a much more pleasant deal — how this will end up changing the dynamics of TAing is unclear though. It also makes things much much nicer in EECS than in other departments, which seems somehow unfair in the end. Why can’t all GSIs get better pay?

paper a day : The Byzantine Generals Problem

It’s more like “paper when I feel like it,” but whatever. This is a classic systems paper on decentralized agreement. Because the result is pretty general, I think there is something that could be done to connect it to information-theoretic studies of multi-way communication or maybe key agreement. That’s a bit hand-waving though.

The Byzantine Generals Problem
Leslie Lamport, Robert Shostak, and Marshall Pease
ACM Transactions on Programming Languages and Systems
Vol. 4 No. 3, July 1982, pp. 382–401.

The basic problem is pretty simple. There are n total generals, some of whom may be disloyal. A commanding general must send an order to n-1 lieutenant generals such that (a) all loyal lieutenants follow the same order and (b) if the commander is loyal then all loyal lieutenants follow the order sent by the commander. The paper looks a oral messages, which are unsigned messages such that a disloyal general can send any possible message, as well as signed messages. I’ll just talk about the former. A protocol for solving this problem is an algorithm for each general to execute, at the end of which all generals make a decision based on the information they have received.

The first result is that satisfying both conditions is impossible with m traitors unless n > 3m. This is easiest to see in the case of three generals, where you can go through all the cases. To extend it to general n the insight is that if n = 3m then m disloyal generals can collude to force indecision at m other generals. It’s kind of like having a devil on one shoulder and an angel on the other. If they are equally strong you will not be able to make the right choice. This result can be extended to show that approximate agreement (in a certain sense) is also impossible.

On the more side, for n > 3m there is a spreading/flooding algorithm that satisfies the conditions. The commander sends a message, and then each lieutenant general acts as the commander in a smaller instance of the algorithm to send the command to the remaining generals. This rebroadcasting protocol, while wasteful, guarantees that the loyal generals will all do the same thing. This algorithm can be extended to the case where the communication structure is a graph with certain “nice” structural properties.

To me, the interesting part really is the converse, since it says something about symmetrizing the distribution. The same phenomenon occurs in the arbitrarily varying channel, where the capacity is zero if a jammer can simulate a valid codeword. In this analogy, the encoder is one group of m generals, the decoder another group of m, and the jammer is a coalition of m disloyal generals.

There’s also a nice bit where they lay the smack down: “This argument may appear convincing, but we strongly advise the reader to be very suspicious of such nonrigorous reasoning. Although this result is indeed correct, we have seen equally plausible “proofs” of invalid results. We know of no area in computer science or mathematics in which informal reasoning is more likely to lead to errors than in the study of this type of algorithm.”