3 ms·

Let me take a stab at an explanation. Suppose we know the positions of all the transmitters and receivers, and we know which receivers are supposed to get which

by troymc 15y ago

Let me take a stab at an explanation. Suppose we know the positions of all the transmitters and receivers, and we know which receivers are supposed to get which signals. Then we determine the signals (waves) to be emitted by the transmitters such that at each receiver, all the other signals cancel out (interfere destructively), leaving nothing but the signal you want at that receiver. (Oh, and don't forget to account for reflection, refraction, dispersion, etc. as the waves propagate around.) If this is what they're doing, then wow, that's pretty cool. It's amazing the problem can be solved fast enough. The way they get around Shannon is by taking advantage of the spatial separation of the various receivers. In effect, Shannon assumed all receivers are at the same position. Is this an accurate understanding?

ChuckMcM 15y ago
As far as I can tell yes, basically its phased-array wi-fi where the system solves for creating channels to individual points rather than beam energy. If you are familiar with phased array RADAR (as used on AEGIS and other platforms) the system computes on the fly the necessary set of signals from an array of antenna which will constructively interfere to put a 'beam' on the target. AEGIS can track hundreds of targets simultaneously (I believe the actual upper limit is classified) I recall a startup in the bay area that was doing something like that with WiFi access points to provide both range and better signal integrity (you could exceed the power limits on non-license use going into the antenna as measured output was still within spec), I thought they had been acquired by Atheros but I'll have to dig a bit deeper to find out for sure.
- Nrsolis 15y ago
  IIRC, there are already companies doing this in the mobile phone space. In essence, they beam steer using slight differences in the arrival time of the signal to actual antennas which in turn causes constructive interference in the desired direction and destructive interference in other locations. For mobile phone networks, this is only for azimuth. For systems like the ones used for AEGIS (the SPY-1 and variants) you get azimuth and elevation beam steering. Honestly, I can't see this working without stepping on some of the patents owned by companies like ArrayCom and others.
  - bmohlenhoff 15y ago
    How did they fit enough transmit elements into a cell phone to do that? I thought cell phone antennae were omnidirectional.
    - tcgore 15y ago
      That is the big claimed upside of this approach, the cell phone transmitter receiver is very simple, with only 1 antenna. The base station number crunching becomes much more sophisticated, but that is fine.
- kragen 15y ago
  > I recall a startup in the bay area that was doing something like that with WiFi access points to provide both range and better signal integrity You may be thinking of Vivato, whose assets were acquired by Catcher.
kragen 15y ago
I proposed doing that in 1999: http://lists.canonical.org/pipermail/kragen-tol/1999-June/000422.html http://lists.canonical.org/pipermail/kragen-tol/1999-June/00... and in audio in 2000 http://lists.canonical.org/pipermail/kragen-tol/2000-May/000589.html http://lists.canonical.org/pipermail/kragen-tol/2000-May/000... but I was far from the first; the early papers on this go back to the 1970s. I believe that you can't get all the other signals to cancel out exactly at everybody else's receiver, but you can get the desired signal to interfere constructively and thus have a much higher amplitude. The common name for this is "MIMO," multiple-input multiple-output. It's not clear from the article how "DIDO" differs from MIMO. But I didn't account for reflection, refraction, and dispersion (!? what medium is dispersive for radio waves? That's gonna make it rough.). HASAS (HydroAcoustic Signal Analysis System) is a piece of open-source software designed to do this for underwater passive sonar purposes.
NY_Entrepreneur 15y ago
"Oh, and don't forget to account for reflection, refraction, dispersion, etc. as the waves propagate around.)" See my post http://news.ycombinator.com/item?id=2820131 For your "reflection, refraction, dispersion, etc.", in principle the 'system' from each transmitter to each receiver is both time invariant and linear which means that can account for the effects of "reflection, refraction, dispersion, etc." just by applying a 'transfer function' (below). Yes, need a different transfer function for each pair of transmitter and receiver. Apparently the 'test data' that is sent is to determine the transfer functions. "Signal"? A 'signal' is just a real valued function of the real variable time. So, say that for time t s(t) is such a signal. To keep this simple but still powerful enough for practice, suppose time t is in only a finite interval. In this real problem the length of the interval is likely a small fraction of one second. "Time invariant"? Over an interval short enough that physical movement, the weather, birds, etc. don't significantly change the situation. In this real problem, we may be asking that the system remain time invariant only over a small fraction of a second. "Linear": If send through signal x and receive signal r(x) and send through signal y and receive signal r(y), then for numbers a and b when send through signal ax + by receive signal ar(x) + br(y). Such linearity should hold even with lots of "reflection, refraction, dispersion, etc.". So this linearity is just another example of classic 'linearity' that math is awash in from linear transformations in linear algebra, linearity of differentiation and integration in calculus, 'linear operators' as in much of mathematical physics, much of 'functional analysis' with Hilbert and Banach spaces, the various 'representation' theorems for linear operators, etc. Or, as in G. Simmons, the twin pillars of mathematical analysis are linearity and continuity. "Transfer function"? Suppose we send signal u(t) and receive signal s(t). Take the Fourier transform of signal u(t). That is, convert u(t) to its 'frequencies'. If u(t) is a sound from one key on an organ, then the Fourier transform gives essentially just the sine waves at the various 'overtones' of the organ note. We are good at understanding such overtones if only because the human ear does some work close to Fourier transforms. Say that the Fourier transform of u(t) is U(w) for frequencies w. Or, U(w) is is the 'spectrum' of u(t). Now, for our time invariant linear system, say that its 'transfer function' is H(w) for frequencies w. Say that the signal that is received is s(t) with Fourier transform S(w). Okay, presto, for each frequency w, S(w) = H(w) U(w). That is, at each frequency, just multiply the input U(w) by the the value of the transfer function H(w) at frequency w and get the output S(w). Then the final signal received s(t) is the inverse Fourier transform of S(w). Cute. Signals in electronic engineering are just awash in this relationship. The context of Shannon's theorem is quite different from that of DIDO. If want to compare with Shannon's theorem, then DIDO raises an issue because as the number of transmitters and receivers and total 'bandwidth' increase, the total transmitted power will have to increase, but a big point of Shannon's work was that the power is limited. That is, Shannon understood that could push through all the data wanted if could just increase power arbitrarily. Another big point in Shannon's work was 'noise' on the communications channel. Again, in principle, with no noise, can push through all the data you want even with limited power. So, here's Shannon's work in a nutshell as I remember it from years ago without review (take with a shovel full of salt): As I did in http://news.ycombinator.com/item?id=2820131 consider the problem over a finite interval of time and convert to discrete points in time and in frequency. Are told the maximum power can send. And as the signal travels, a 'noise' signal gets added. Due to the finite power, all the signals can send are in just a sphere (in a finite dimensional space of appropriate dimension). Then due to the noise, what is received is the signal sent plus the noise. So, in effect, due to the added noise, what is received is a point in a (small) sphere around the signal that would have been received without the noise. So, all the signals that can be received are in a big sphere determined by the power. And each signal that is received is in a small sphere of its own inside the big sphere. But want the separate signals to be distinguishable. So, for any two signals sent, want their small spheres at the receiver not to overlap. So, the number of different signals that can be sent is the number of small spheres that will fit, without overlap, inside the big sphere at the receiver. So, net, we're talking about the number of little balls that will fit inside a big ball. Basically that's it. Likely more details are in http://cm.bell-labs.com/cm/ms/what/shannonday/shannon1948.pdf

by troymc 15y ago

ChuckMcM 15y ago

As far as I can tell yes, basically its phased-array wi-fi where the system solves for creating channels to individual points rather than beam energy. If you are familiar with phased array RADAR (as used on AEGIS and other platforms) the system computes on the fly the necessary set of signals from an array of antenna which will constructively interfere to put a 'beam' on the target. AEGIS can track hundreds of targets simultaneously (I believe the actual upper limit is classified) I recall a startup in the bay area that was doing something like that with WiFi access points to provide both range and better signal integrity (you could exceed the power limits on non-license use going into the antenna as measured output was still within spec), I thought they had been acquired by Atheros but I'll have to dig a bit deeper to find out for sure.

Nrsolis 15y ago
IIRC, there are already companies doing this in the mobile phone space. In essence, they beam steer using slight differences in the arrival time of the signal to actual antennas which in turn causes constructive interference in the desired direction and destructive interference in other locations. For mobile phone networks, this is only for azimuth. For systems like the ones used for AEGIS (the SPY-1 and variants) you get azimuth and elevation beam steering. Honestly, I can't see this working without stepping on some of the patents owned by companies like ArrayCom and others.
- bmohlenhoff 15y ago
  How did they fit enough transmit elements into a cell phone to do that? I thought cell phone antennae were omnidirectional.
  - tcgore 15y ago
    That is the big claimed upside of this approach, the cell phone transmitter receiver is very simple, with only 1 antenna. The base station number crunching becomes much more sophisticated, but that is fine.
kragen 15y ago
> I recall a startup in the bay area that was doing something like that with WiFi access points to provide both range and better signal integrity You may be thinking of Vivato, whose assets were acquired by Catcher.

kragen 15y ago

I proposed doing that in 1999: http://lists.canonical.org/pipermail/kragen-tol/1999-June/000422.html http://lists.canonical.org/pipermail/kragen-tol/1999-June/00... and in audio in 2000 http://lists.canonical.org/pipermail/kragen-tol/2000-May/000589.html http://lists.canonical.org/pipermail/kragen-tol/2000-May/000... but I was far from the first; the early papers on this go back to the 1970s. I believe that you can't get all the other signals to cancel out exactly at everybody else's receiver, but you can get the desired signal to interfere constructively and thus have a much higher amplitude. The common name for this is "MIMO," multiple-input multiple-output. It's not clear from the article how "DIDO" differs from MIMO. But I didn't account for reflection, refraction, and dispersion (!? what medium is dispersive for radio waves? That's gonna make it rough.). HASAS (HydroAcoustic Signal Analysis System) is a piece of open-source software designed to do this for underwater passive sonar purposes.

NY_Entrepreneur 15y ago

"Oh, and don't forget to account for reflection, refraction, dispersion, etc. as the waves propagate around.)" See my post http://news.ycombinator.com/item?id=2820131 For your "reflection, refraction, dispersion, etc.", in principle the 'system' from each transmitter to each receiver is both time invariant and linear which means that can account for the effects of "reflection, refraction, dispersion, etc." just by applying a 'transfer function' (below). Yes, need a different transfer function for each pair of transmitter and receiver. Apparently the 'test data' that is sent is to determine the transfer functions. "Signal"? A 'signal' is just a real valued function of the real variable time. So, say that for time t s(t) is such a signal. To keep this simple but still powerful enough for practice, suppose time t is in only a finite interval. In this real problem the length of the interval is likely a small fraction of one second. "Time invariant"? Over an interval short enough that physical movement, the weather, birds, etc. don't significantly change the situation. In this real problem, we may be asking that the system remain time invariant only over a small fraction of a second. "Linear": If send through signal x and receive signal r(x) and send through signal y and receive signal r(y), then for numbers a and b when send through signal ax + by receive signal ar(x) + br(y). Such linearity should hold even with lots of "reflection, refraction, dispersion, etc.". So this linearity is just another example of classic 'linearity' that math is awash in from linear transformations in linear algebra, linearity of differentiation and integration in calculus, 'linear operators' as in much of mathematical physics, much of 'functional analysis' with Hilbert and Banach spaces, the various 'representation' theorems for linear operators, etc. Or, as in G. Simmons, the twin pillars of mathematical analysis are linearity and continuity. "Transfer function"? Suppose we send signal u(t) and receive signal s(t). Take the Fourier transform of signal u(t). That is, convert u(t) to its 'frequencies'. If u(t) is a sound from one key on an organ, then the Fourier transform gives essentially just the sine waves at the various 'overtones' of the organ note. We are good at understanding such overtones if only because the human ear does some work close to Fourier transforms. Say that the Fourier transform of u(t) is U(w) for frequencies w. Or, U(w) is is the 'spectrum' of u(t). Now, for our time invariant linear system, say that its 'transfer function' is H(w) for frequencies w. Say that the signal that is received is s(t) with Fourier transform S(w). Okay, presto, for each frequency w, S(w) = H(w) U(w). That is, at each frequency, just multiply the input U(w) by the the value of the transfer function H(w) at frequency w and get the output S(w). Then the final signal received s(t) is the inverse Fourier transform of S(w). Cute. Signals in electronic engineering are just awash in this relationship. The context of Shannon's theorem is quite different from that of DIDO. If want to compare with Shannon's theorem, then DIDO raises an issue because as the number of transmitters and receivers and total 'bandwidth' increase, the total transmitted power will have to increase, but a big point of Shannon's work was that the power is limited. That is, Shannon understood that could push through all the data wanted if could just increase power arbitrarily. Another big point in Shannon's work was 'noise' on the communications channel. Again, in principle, with no noise, can push through all the data you want even with limited power. So, here's Shannon's work in a nutshell as I remember it from years ago without review (take with a shovel full of salt): As I did in http://news.ycombinator.com/item?id=2820131 consider the problem over a finite interval of time and convert to discrete points in time and in frequency. Are told the maximum power can send. And as the signal travels, a 'noise' signal gets added. Due to the finite power, all the signals can send are in just a sphere (in a finite dimensional space of appropriate dimension). Then due to the noise, what is received is the signal sent plus the noise. So, in effect, due to the added noise, what is received is a point in a (small) sphere around the signal that would have been received without the noise. So, all the signals that can be received are in a big sphere determined by the power. And each signal that is received is in a small sphere of its own inside the big sphere. But want the separate signals to be distinguishable. So, for any two signals sent, want their small spheres at the receiver not to overlap. So, the number of different signals that can be sent is the number of small spheres that will fit, without overlap, inside the big sphere at the receiver. So, net, we're talking about the number of little balls that will fit inside a big ball. Basically that's it. Likely more details are in http://cm.bell-labs.com/cm/ms/what/shannonday/shannon1948.pdf