You are currently browsing the monthly archive for June 2013.

It was a touching and inspiring one to read about that historic day when Nelson Mandela was released.

Here is a photo from NY times . It is taken from Obama’s ongoing African leg tour. This particular one is apparently taken at Goree Island. For some reason, it feel pleasant to see this photo.

The diary is an incredible read in itself.

I don’t think we needed to be told about the perils of plastic.  Enough is known and seen already. Among the many haunting stories, I distinctly remember the stories heard about animals and birds species being hit with the terminal trouble, after innocently consuming the plastic and other non-organic waste laregely left over by our actions. Those horrific stories that caught my attention were from cities of India, but I am sure that India is only a coincidence. It is sure to have happened or happens in many other parts of the world, especially the developing countries. Now, this documentary tells us how severe and grim the reality is. One of the remote island of our planet and its inhabitants too have to suffer for the callousness of our deeds. How unfair!

Jack Eidt has this eye opener report on the plights of Albatross, caused by our own ignorance.

At some point the great Federer run had to end. A 2nd round exit from Wimbledon is not what we are used to from the great champion. The last time, he had to bow this early, was more than 10 years ago and that tells the greatness of his journey. Even the great king, pistol Pete Sampras had to taste the sourness at this piece of grass. That way, it was not completely out of ordinary that this happened today, but I always loved to see master march on for this title; one more time, every time!  The great man didn’t play all too badly today, but the Ukranian was full of confidence. Seeing the way Serhiy Stakhovsky served and stayed confident to go to the nets at Wimbledon, facing the 7 time champion was a sight that was reminiscent of foregone days . It was a pleasant sign to see some serve and volley show staged at Wimbledon. In that respect, as much pain I am with Federer’s exit, happy to take home, memory of a good match and feel for the star of the day.

The 2012 Turing award goes to two cryptography pioneers Shafi Goldwasser and Silvio Micali. I don’t do much of cryptography (for that matter I never did anything serious on that front, besides doing some C programming to demonstrate RSA and later on some class project involving elliptic curve cryptography and mathematica programming at EPFL). But I always was fascinated by the topic of Cryptography, largely for the many interesting toy like, yet deeply thought provocative combinatorial as well as probabilistic problems it addressed. Several of these problems stay at the very intersection of CS theory and cryptography.

One such classical problem that we all learned in graduate classes is the zero knowledge proof. The idea is pretty cute.  In the most simple scenario, this involve two parties Alice and Bob, who don’t trust each other, but one of them (say Alice) have to convince the other (bob) that she has knowledge (say a mathematical proof) of something without  really revealing it. The fact that it is not revealed explains why it is zero knowledge (Bob in the end never get to know what Alice know, but just gets convinced that she knows!).  So, it will work more like an interactive protocol wherein a lot of questions are being asked by Bob, chosen randomly, depending on prior answers from Alice. Doing this way for long, can Alice convince Bob, with an overwhelmingly high probability, that she knows what was claimed? Such an interactive protocol constitute what is coined as a zero knowledge proof. An example would be a novel ATM machine where, you don’t have to enter the PIN (unlike the ones that we have), but you can still convince the machine that you know your correct PIN. Sound cool and yet thought provoking, right? Well, that is why I said it is cute and interesting. This zero knowledge interactive proof idea was first conceived by the new Turning award winners.  The names didn’t strike me initially  with the Turning award news, but after reading the details, it occurred to me that, I had read their classic paper , as part of my coursework at EPFL.

A bit more formally stated, the two entities are namely a Prover and a Verifier. In the ATM example, the ATM machine is a verifier and you the user is a Prover. Prover knows the proof of a mathematical statement and verifier tries to verify whether the claim is indeed correct with high probability. The machinery of zero knowledge proof is that, if the prover is trying to trick, the verifier will be able to find that out as well, with high probability. There are many examples illustrating this beautiful idea. A classic example is the problem of helping a blind man in identifying whether two otherwise identical balls are of different colors? Can you convince him, without really telling which is which? Now there are variants of their original idea and myriads of practical significance have emerged or are still emerging.

The ACM award page has pretty enthralling account of these two pioneers (Shafi and Micali).  Now, here is an interesting family trivia. Shafi Goldwasser and her husband Nir Shavit together now keeps three Gödel Prize in their shelves, besides adding the Turing award aroma, now to their household!

Through Anand Sarwate’s blog and this piece from Sergio Verdu, I came to know that  the well known Information and Coding theorist Jim Massey has passed away. I don’t have any direct personal recollection of Massey, other than seeing him once at an Information theory workshop and also last year at the Marconi award ceremony at Irvine. The one thing I always remember (besides the Berlekamp Massey algorithm and transform decoding paper) is his notes at ETH. I have enormously benefited from his lecture notes on Cryptography when I was trying to learn the topic at EPFL. So lucid, crisp and intuitive were his scribes. How I always wished to sit in one of his live lectures! RIP!

I am sure detailed writing on his life and work will appear at some point. I recall Rudi Urbanke once mentioned the early impact of Massey’s work (as a graduate student ?) on threshold decoding of convolutional code, having spurred interest in industry.  Codex corporation (to which, he was a co-founder, I learned recently.) once wanted to implement it into their line modems. Not sure whether I have all the details intact here, but prior to the Viterbi algorithm, his threshold decoding scheme must have been a big hit in communication! To have industry interested in a graduate student work must be special, any day, anywhere!

In his blog  Sergio Verdu, has pointed to the IEEE oral history interview archive, which I happened to read last year almost same time.

Info theory website has further details including the funeral info.

If you have not seen this yet, a fascinating talk (Cryptography- Science or Magic) he did at MIT several years ago, is archived here. Boy! who did the speaker introduction? Another true connoisseur Peter Elias! First time, I saw a video of Elias.

Almost all the deployed and successful communication strategies till date are half duplex (HD). That is, we don’t have simultaneous transmission and reception on the same frequency band, aka, full duplex (FD). For example, 802.11 WiFi uses a time switch (TDD) between transmit and receive mode.  Both transmission and reception takes place over the same frequency band as well. A single antenna is (typically) used for both tx and rx in this case. It is always either transmit or receive (or none!) that happen at any given time. In the cellular world, such as LTE the popular scheme is to have the frequency slice shared (FDD). In that case the up-link (link from a cell phone to base station) takes place in a range of frequency band different from that on link receiving signal from base station, while both transmit and receive can take place simultaneously. In both TDD and FDD cases, there is no overlap between the transmit and receive signals at a given frequency at the same time.

Let us posit this question. In a given frequency band,  is it feasible at all to have simultaneous transmission and reception? One way of course is to find a domain where these two (transmit and receive) signals stay perfectly distinct. Say use some orthogonal codes. In theory yes, but there is an important practical hurdle here. It is the issue of the loudness (aka self interference) from own transmit signal! An analogy is like one tries to decipher a whisper coming from someone, while he/she is simultaneously shouting at top of his/her voice. In reality, the desired signal comes from a distant source after traveling through adverse medium/channel. More than anything else, the signal intensity level would have got severely degraded by the time signal arrives at the receiver unit. Well, let me put some numbers from a practical setup. In a (typical) WiFi scenario the incoming signal (from an AP) at your receiver antenna (of say tablet) may be around -70dBm, whereas, the power of (tablet PC’s) concurrent transmission power could be $20$ dBm!  The task to fulfill the full duplex goal is really to recover the information from the relatively week signal in the presence of a self interference stronger by 80 to 90dB! In other words, we should hit a mechanism to suppress the self interference by 90dB! Getting a 90dB suppression is no easy, especially when we are constrained chip and board area to get deployed in portable devices! Traditional board layout tricks such as isolation, beam steering etc alone wouldn’t get us there.

OK, now what? the reason I suddenly brought this up is largely due to the increased momentum this one is gathering off later in both academia as well as industry. It still has enormous challenges ahead. Realizing FD on the other hand will bring in enormous benefits. Historically, we always mulled over capacity and throughput, with the strong assumption that all resources in the lot are available. Say for a given channel bandwidth $W$, the capacity is $C(W)$ and throughput is so much and so on. The reality is that, in most cases, to have information exchange, we need two way communication and that means double resources. Spectrum being pricey and scarce, getting the full duplex can potentially get up to double fold in throughput and several other benefits along the way such as remedy to the hidden node problem in current 802.11 MAC access. Now 802.11 standards front, we have a new study group on high efficiency wireless (HEW). I believe HD can play a role there too.

I am not prepared to discuss all the details involved here. Let me outline a rough problem formulation of FD.  More general versions exists, but let me try with a simple case. Much more detailed formulation of the problem can be seen here and elsewhere. I kinda used the notations and problem statement from this. Let $y_{a}$ be the desired signal from a distant sender, arriving  at the rx antenna. Simultaneously, a much high power signal $x$ is being sent . The signal $x$ is significantly higher power than $y_{a}$. Now, the signal $x$ leaks through some path $H$ and produce an interference $v_{a}$ at the receive antenna. In other words, the effective signal at the receiver antenna port is $z_a=x+y_a$. For sake of simplicity, let us assume that $H$ is modeled as a FIR filter. The sampled signal relationship can be then stated as follows.

$z_{a}[n]=y_{a}[n]+\underbrace{\sum_{k=0}^{\infty}{H[m] x[n-m]}}_{\triangleq u_{a}[n]}$.

Now here is the thing. We cannot simply pass the buck to digital domain and ask to recover the useful signal from powerful interference. Recall that, the A/D converter stands at the very interface of analog to digital partition. High power interference signal will severely saturate the A/D and result in irreversible clipping noise. So, first we must do a level of analog suppression of this interference and make sure that, the A/D is not saturated. Let us say, we go for an analog filter $C_{a}$ and do this job.  Post analog cancellation using a filter $C_{a}[n]$ we will have,

$\tilde{z}_{a}[n]=z_{a}[n]+\underbrace{\sum_{k=0}^{\infty}{C_{a}[m] x[n-m]}}_{\triangleq v_{a}[n]}$.

The A/D signal transformation can be decomposed to the following form (using Bussgang theorem for instance). $\tilde{z}_{d}[n]=\mathcal{A} \tilde{z}_{a}[n]+q[n]$. Now,

$\tilde{z}_{d}[n]={\mathcal{A}} z_{a}[n]+{\mathcal{A}} {\displaystyle \sum_{k=0}^{\infty}{H[m] x[n-m]}}$.

If we do a digital cancellation at the A/D output state with a filter $C_{d}[n]$, we can have $\hat{z}_{d}[n]=\tilde{z}_{d}[n]+\sum_{k=0}^{\infty}{C_{d}[m] x[n-m]}$. Incorporating all these, we will have

$\hat{z}_{d}[n]={\mathcal{A}} y_{a}[n]+ \displaystyle \sum_{m=0}^{\infty}{\left[\mathcal{A} \left(H[m]+C_{a}[m]\right)+C_{d}[m]\right] x[n-m]}+q[n]$.

Now if we can adapt and find $C_{a}[n]$ and $C_{d}[n]$ such that $\mathcal{A} \left(H[m]+C_{a}[m]\right)+C_{d}[m] \rightarrow 0$, then we can hope to have a near perfect self noise cancellation and produce $\hat{z}_{d}[n]={\mathcal{A}} y_{a}[n]+q[n]$!

So, in theory there is a way to do this, by a hybrid approach where in some correction is done in analog domain (before A/D) followed by a more easily realizable digital cancellation circuit. There are many more practical hurdles. Some of them are:

1. Performing correction/adaptation at RF frequency is not trivial
2. If we are to do this post mixer (after downconversion), then the LNA nonlinearity (and a potential saturation) will come into play
3. Channel/coupling path estimation error will degrade performance
4. Calibrating analog correction is a little more involved
5. A typical goal may be to have about 40dB suppression from analog correction and another 40dB from digital.
6. Digital and analog correction, calibration time should be reasonably fast, so as not to spoil the set goal of simultaneity!

Some of the recent results, published are indeed promising. Some prototypes are also being developed. More general version involving multiple antennas’s are also being talked about. In that case, some beam forming can provide additional support. Let us hope that, with some more push and effort, we get to realize this one day into real world.

Most of you may have been following this new prototype being developed and deployed by Google. I am talking about project Loon, an idea conceived by Google to help connect the few billion friends around the world who are still deprived of internet benefits. The idea at first may spell like fiction, but this one is for real. Already, some pilot projects are on the way, in New Zealand. Let us watch out for this to spread its wings in the coming months and years!

Anyone remember the old Motorola/Iridium initiative?  It scooped and failed for many a reasons, but the idea that time was to have the entire world voice connected, but project Loon is a bit more than that in intention, technology and economic viability. Besides, Loon is  backed by a highly successful technology driven company. The goal in itself is to have pretty much every corner of the world to stay connected by internet, the holy grail of global networking. Whereas, Iridium needed sophisticated lower orbit satellites, project Loon can get the job done through a set of balloons equipped with wireless communication technologies. The number of balloons may be much larger than the number 66 or 70 satellites, but the latter is a lot less expensive and green than the failed initiative!

So what goes into the making of project Loon?  Logistic wise it needs deployment of enough number of helium powered balloons into the sky, the stratosphere layer of earth atmosphere to be precise. Why stratosphere? Because, the balloons will make use of the wind flow that prevail at stratosphere layers to steer and position it around a certain location locked to ground. The balloons are not quite stationary; they instead will move around, but on the average a certain number of balloons will stay put up in location range to provide a reasonable coverage for any given location. All the balloons are equipped with enough circuitry to perform necessary wireless communication networking jobs. The balloons are all the time connected (wireless that is) to neighboring balloons and some of them will talk to an available ground station terminals through which it will establish connection to the internet backbone and thus to rest of the connected world!

The balloons may have varying shapes and orientation. The shape of the balloon and the wind pattern may come into the equation to steer them and stay around (or move around the earth) at the atmosphere. They may, not only move around the earth, but also can potentially move up and down in the stratosphere layers. Each of these balloons are of approximately 15 meters in diameter which will float at about 20 km altitude from earth surface. For record, this height is more than double the distance where we can spot the farthest cloud or for that matter the highest altitude where airplanes fly!  The task involves gyration, ballon steering and of course quite a lot of wireless mesh networking as well as co-ordination prospects. At the user side, you will have specialized antenna (or antennas, depending on whether MIMO comes in) to talk to one of the balloons above your location and we are all set to go. When fully operational, everything else will be transparent! Pretty much the energy for operation at balloons all will come from solar energy. The other natural resource used is wind. Both are green and free and almost universal!

I am very excited about the prospect of this coming off in full force in the near future. On the beneficiary side, one it will help reaching the far corners of  our planet. More than that this may well serve as an inexpensive way for many billion folks to reap the benefits of internet and staying connected. Of all, the children of a lesser world can as well get to bite  a share of a better world. Imagine a remote village school in Burundi or Bangladesh getting access to better educational tools through internet! Wouldn’t that be a beautiful? Corporations will make money, but when less privileged ones also benefit, that is something to cheer. In the end a model will sustain and everyone can have a share, monetary or otherwise.

Check out more details at the project Loon page. The google+ page has more updates pouring in.

In a lighter vein, what is the main downside of this everywhere connectedness? Here is a potential spoilsport scenario! You will agree with me here:-)

One of my favorite cell phone app till date is the navigation utility Waze. The only downside that I’ve noticed is its hunger for power (It drains the phone battery in no time), but GPS in general hog battery anyway. In a car with some charging unit, it is not a killer drawback, but it is a negative thing anyway. Since this app has such nice user friendliness, coupled with ability to provide almost real time side information (through user assistance and online feeds) such as traffic situations, presence of police etc., makes this such a handy tool on the move. I was almost contemplating that this will be bought over by Google or a Facebook. Now what? It didn’t take too long! Waze is gobbled by Google, for a reported billion odd USD.  I like Google maps too. Now, we have a chance to have all in one! Hopefully, a better one!

Dr. Appanu Nambiar is someone I know personally. Being the father of a close friend of mine has surely helped me to know him from close quarters. He was a teacher and principal at various government institutions in Kerala. Upon retirement from professional life, he decided to contribute to the society by serving one of the most backward and ignored community in Waynad, Kerala, India. In 1997, he thus started a school named Pazhassiraja school, with the primary intention to provide education and skill development for the Adivasi children. Adivasi is a collective term referring to a tribal community which form a significant portion of the aboriginal population of India. We all at some stage have had the intention and good will to contribute to the society. Having a thought is one thing, but to commit yourself into realizing by working through all the nuances;that is an entirely different thing. Inspirational, but now we should  read on and act.

The history of his noble commitment goes like this. During the service as a principal at a neighboring college at Waynad, he happened to get a first hand glimpse of the plight the Adivasi community in Waynad  go through. Without much financial or social support , he ventured his time and effort to help educating the children from the remote and an otherwise largely neglected section of society.

The school follows a system more like the Gurukula tradition, where in the teachers (guru) and supporting staffs  live along with children in the same premise.  To really understand the level of commitment he was getting into, we must first know some background on the tribal community, their social setup and the geographical position of the school itself. Waynad is a beautiful place located at the southern tip of the Western ghatt  mountain terrain in south India. Waynad belong to the state of Kerala in India. While Kerala is considered socially way forward compared to many other states in India, Waynad is unfortunately one of the more ignored ones among the province of  Kerala, in terms of outreach of several reforms including education and health. The lack of social development reach to the tribal areas also meant that basic education options went missing for the children. As a consequence, generation after generation they are deprived of a good standard of living and livelihood.

The hierarchy of this community is a bit more complicated than what we know from the outset. The adivasi tribes itself is classified into several sub-tribes or castes. The main ones are Adiyas, Kattunayakans, Kurichiyans,Kurumas,Ooralis, Paniyas and Uraali Kurumas. Some of them have slightly different physical characteristics (such as skin texture), but they are historically sectioned into different groups based on the profile of jobs they carried out.  Each of these tribes follow social tradition and rituals of its own, while at the same time they collectively follow a generic form of social life including religious practice, marriage, art etc.,. Deforestation and  general urbanization over the years meant that the traditional resources for these indigenous community is taken away. Instead of providing a needy hand, the society often found ways to exploit this tribe. For whatever reason, the tribal community has not yet been part of the mainstream society and that unfortunately spell disaster for their future.

As always, the biggest casualty in any crisis are the children. For them as well as the generations there on to survive, first thing to do is to make them capable of making a decent livelihood. Nambiar’s initiative is also with that modest goal; to empower some of them to deal with the realities of world around them as they grow up to youth and beyond. When a stream of youth can stand to survive and deal with a decent social life, the next thing will be to pave the way for better education and living opportunities for their children and so on. In a streamlined system, a wagon can roll.  But the first step is to survive this great initiative and that needs a lot of support from well wishers like us. Remember, the grand from government is extremely limited and the untimely arrival makes compound the agony. Relentless effort from the great man along with support from many kind hearted people and organizations have helped the cause reaching this far. Now it has come to a point where surviving itself hinges on generous support. The time is now. A failure here, not only will stop the good work done.  There is also an increased danger looming where some of these youths may break into verge of alcoholism and anti social activities, once they lose the confidence of a viable future ahead. Remember, these are extremely vulnerable section of a population and they can be easily trapped, once let go.

So, dear readers, if you plan to contribute to charity, please help this great cause. You can find the details on how to donate etc here. Any amount, however small it may be, will help its share.

I am convinced why Einstein once supposedly remarked “My dear young boy, you have shown me that there is God in heaven”. I may have got the exact words quite  not correct, but he is quoted something like this about the young genius of Yehudi Menuhin. Forget the literal reference, but the essence of Menuhin’s violin mastery is breathtaking. Here is  that famous West meets East master piece by Yehudi Menuhin and the legendary pandit Ravi Shankar. Music can bring peace, cant it?

Boy, how did this stuck accidentally, this afternoon? I am hearing this immortal piece, after a long long time! Wow, such a beautiful pleasantry musical. Dave Mathews band (DMB)’s famous Two step. The lyrics is a piece of gold too. Such priceless is life and love, Isn’t it?

and this live show is simply captivating too….

The lyrics goes like this (courtesy )

Say, my love, I came to you with best intentions  You laid down and gave to me just what I’m seeking Love,you drive me to distraction Hey my love do you believe that we might last a thousand years Or more if not for this, Our flesh and blood It ties you and me right up Tie me down

Celebrate we will Because life is short but sweet for certain We’re climbing two by two To be sure these days continue These things we cannot change
Hey, my love, you came to me like wine comes to this mouth Grown tired of water all the time You quench my heart and you quench my mind
Celebrate we will Because life is short but Sweet for certain We’re climbing two by two To be sure these days continue

The things we cannot Celebrate, you and me, climbing two by two, to be sure These days continue, things we cannot change
Oh, my love I came to you With best intentions You laid down and gave to me Just what I’m seeking
Celebrate we will Because life is short But sweet for certain We’re climbing two by two To be sure these days continue Things we cannot change… Things we cannot change

 leeyoongu on LT codes decoding using Wiedem… vinod kumar on Yesudas and Rafi singing same… Ramesh on The split lot corner stor… sreelesh. on Yesudas and Rafi singing same… The new Prime gap |… on Improved bounds on Prime numbe…