#[1]IEEE Spectrum

#[1]IEEE Spectrum

(BUTTON) ____________________

IFRAME: [2]https://www.googletagmanager.com/ns.html?id=GTM-5WJB5X2

[3]IEEE.org[4]IEEE Xplore Digital Library[5]IEEE Standards[6]More Sites
[7]Sign In[8]Join IEEE

The November 2022 issue of IEEE Spectrum is here!
[9]Download PDF |v
[10]Close bar
Build a Passive Radar With Software-Defined Radio
Share
FOR THE TECHNOLOGY INSIDER
Search: ____________________ (Search)
Explore by topic
[11]Aerospace[12]Artificial
Intelligence[13]Biomedical[14]Computing[15]Consumer
Electronics[16]Energy[17]History of
Technology[18]Robotics[19]Semiconductors[20]Sensors[21]Telecommunicatio
ns[22]Transportation
[23]IEEE Spectrum
FOR THE TECHNOLOGY INSIDER

Topics

[24]Aerospace[25]Artificial
Intelligence[26]Biomedical[27]Computing[28]Consumer
Electronics[29]Energy[30]History of
Technology[31]Robotics[32]Semiconductors[33]Sensors[34]Telecommunicatio
ns[35]Transportation

Sections

[36]Features[37]News[38]Opinion[39]Careers[40]DIY[41]The Big
Picture[42]Engineering Resources

More

[43]Special
Reports[44]Collections[45]Explainers[46]Podcasts[47]Videos[48]Newslette
rs[49]Top Programming Languages[50]Robots Guide

For IEEE Members

[51]Current Issue[52]Magazine Archive[53]The Institute[54]TI Archive

For IEEE Members

[55]Current Issue[56]Magazine Archive[57]The Institute[58]TI Archive

IEEE Spectrum

[59]About Us[60]Contact Us[61]Reprints & Permissions[62]Advertising

Follow IEEE Spectrum

Support IEEE Spectrum

IEEE Spectrum is the flagship publication of the IEEE -- the world's
largest professional organization devoted to engineering and applied
sciences. Our articles, podcasts, and infographics inform our readers
about developments in technology, engineering, and science.
[63]Join IEEE
[64]Subscribe
[65]About IEEE[66]Contact &
Support[67]Accessibility[68]Nondiscrimination Policy[69]Terms[70]IEEE
Privacy Policy
© Copyright 2022 IEEE -- All rights reserved. A not-for-profit
organization, IEEE is the world's largest technical professional
organization dedicated to advancing technology for the benefit of
humanity.

IEEE websites place cookies on your device to give you the best user
experience. By using our websites, you agree to the placement of these
cookies. To learn more, read our Privacy Policy.
[71]view privacy policy [72]accept & close

Enjoy more free content and benefits by creating an account

Saving articles to read later requires an IEEE Spectrum account

The Institute content is only available for members

Downloading full PDF issues is exclusive for IEEE Members

Access to Spectrum's Digital Edition is exclusive for IEEE Members

Following topics is a feature exclusive for IEEE Members

Adding your response to an article requires an IEEE Spectrum account

Create an account to access more content and features on IEEE Spectrum,
including the ability to save articles to read later, download Spectrum
Collections, and participate in conversations with readers and editors. For
more exclusive content and features, consider [73]Joining IEEE.

Join the world's largest professional organization devoted to engineering and
applied sciences and get access to all of Spectrum's articles, archives, PDF
downloads, and other benefits. [74]Learn more ->

[75]CREATE AN ACCOUNT[76]SIGN IN
[77]JOIN IEEE[78]SIGN IN
[79]Close

Access Thousands of Articles -- Completely Free

Create an account and get exclusive content and features: Save articles,
download collections, and talk to tech insiders -- all free! For full access
and benefits, [80]join IEEE as a paying member.

[81]CREATE AN ACCOUNT[82]SIGN IN

[83]DIY[84]Topic[85]Magazine[86]Hands On[87]Type[88]November 2022

[89]Build a Passive Radar With Software-Defined Radio

Spot stuff with the KrakenSDR and two TV antennas
[90]Stephen Cass
25 Oct 2022
5 min read
A flat building rooftop with a chimney stack. In the distance, through
the tops of some trees the top of the Empire State Building is visible.
A directional antenna is mounted on the stack pointed towards the
Empire State Building while another antenna points in the opposite
direction. Cables connect the antenna to a battery pack, KrakenRF radio
and a Raspberry Pi on the roof.

Transmissions from a broadcast tower, such as the spire on top of the
Empire State Building, can be used with cheap TV antennas and a
software-defined radio to track the movements of airplanes.
James Provost

[91]DIY[92]SDR[93]software defined radio[94]type:departments

Normally, when it comes to radio-related projects, my home of New York
City is a terrible place to be. If we could see and hear radio waves,
it would make an [95]EDM rave feel like a sensory deprivation tank.
Radio interference plagues the metropolis. But for once, I realized I
could use this kaleidoscope of electromagnetism to my advantage--with a
passive radar station.

Unlike conventional radar, [96]passive radar doesn't send out pulses of
its own and watch for reflections. Instead, it uses ambient signals. A
reference antenna picks up a signal from, say, a cell tower, while a
surveillance antenna is tuned to the same frequency. The reference and
surveillance signals are compared. If a reflection from an object is
detected, then the time it took to arrive at the surveillance antenna
gives a range. Frequency shifts indicate the object's speed via the
[97]Doppler effect.
__________________________________________________________________

I was interested in passive radar because I wanted to put a new
software-defined radio (SDR) through its paces. I've checked in with
amateur SDR developments for IEEE Spectrum since 2006, when [98]SDR
became something remotely within a maker's budget. The biggest leap
forward happened in 2012 when it was discovered that USB stick TV
tuners using the [99]RTL2832U demodulator chip could be tapped [100]to
make very cheap but effective SDR receivers. An explosion of interest
in SDRs followed. Building off the demand stimulated by this activity,
a number of manufacturers have started making premium, but still
relatively cheap, SDRs. This includes RTLx-based USB sticks built with
better supporting components and designs versus the original TV tuners,
and completely new receivers such as the [101]RSPDx. Some of these new
SDRs can transmit as well as receive, such as the [102]HackRF One
or[103] Lime Mini.

I was researching diving back into SDR with one of these devices when I
spotted the CrowdSupply campaign for the US $399 [104]KrakenSDR. It's
receive only, but it boasts not one or two tuners, but five! The tuners
are based on the [105]RTL R820T2/R860 chip, and they are combined with
hardware that can automatically do coherence synchronization among
them.

The Kraken RF is a rectangular box with a cooling fan. The Pi 4 is
single board computer whose width and height is that of a credit card.
The battery pack is a large portable unit with a handle. The TV
antennas have a long pole with a receiving element about a third of the
way along. It sits in front of a longer reflecting element and behind a
series of nine smaller elements. Both the KrakenRF SDR and the
Raspberry Pi 4 [middle bottom] require a fair amount of power via USB C
cables, so a battery pack [top middle] is needed for mobile operation.
The Pi is connected to the SDR via a data link, and in turn the SDR is
connected via coaxial cables to two directional TV antennas [right and
left].James Provost

What that means is that, for example, you can arrange five
omnidirectional antennas in a circle, and do radio direction finding by
looking at when a transmission arrives at each antenna. Normally,
[106]an amateur looking to do direction finding would have to wave
around a directional antenna, something difficult to do while, for
example, driving a car.

But it was the KrakenSDR's ability to do passive radar that really
caught my eye as a new capability in lowish-cost radio tech , so I
plonked down the money. The next step was to get suitable antennas. The
radio's manufacturer, KrakenRF, recommends directional Yagi TV antennas
for two reasons. First, while the KrakenSDR can work with many signals
including FM radio or cell-tower transmissions, digital TV signals are
best to work with because they are fairly evenly distributed across the
channel's broadcast band, unlike the narrower and more variable signals
from an FM station. (KrakenRF notes that if you must use an FM signal,
pick a heavy-metal station "since heavy metal is closer to white
noise.") The second reason is that pointing a directional antenna away
from the reference source means that it's less likely to be swamped by
the reference signal.

I ordered two small and light [107]$19 TV antennas. Portability was
important because I needed to carry my entire setup to and from my
apartment building's roof, where my particular location in an outer
borough of the city provided more advantages. First, the sky above has
a regular supply of aircraft landing and taking off from NYC's
airports--and large metal assemblies moving against an empty background
are perfect radar test objects. Second, my roof has a line of sight to
the Empire State Building, giving me the ability to choose as a
reference signal any one of[108] more than half a dozen TV channels
transmitted from its spire.

I deployed my rig: a heavy-duty battery pack, the KrakenSDR, cables and
antennas, along with a Raspberry Pi 4 to process data from the SDR.
KrakenRF offers [109]an SD card image for the Pi that bundles an
operating system configured to work with its preinstalled open-source
software. It also sets up the Pi as a Wi-Fi access point with a Web
interface. I really wish more companies would adopt this approach, as
installing open-source software is often a frustrating exercise in
trying to replicate the precise system environment it was developed in.
Even if you want to ultimately install the KrakenSDR software somewhere
other than a Pi, having a known-good setup is useful as a reference,
and allows you to test the hardware.

An illustration of an antenna on a building with arrows pointing from
the Empire State Building to the antenna to an airplane. Comparing the
time between the arrival of a signal from a broadcast transmitter and
the arrival of a reflection of that signal lets you detect objects such
as airplanes and estimate their range. Frequency shifts between the two
signals allow you to plot the speed of the object away or toward the
antennas along with the range. The trace on the right shows a plane
moving away as it increases its speed.James Provost

I pointed the reference antenna toward the Empire State Building and
retreated with the surveillance antenna behind the superstructure of my
building's stairwell. This was in a bid to shield the antenna from the
reference signal and myself from the wind. Checking the feed from the
antennas using the Web interface's built-in spectrum analyzer, I
discovered I was almost too successful in choosing the Empire State's
transmitter tower as a source of radio illumination: The reference
signal was saturating the receiver with the default gain setting of 27
[110]decibels, so I dropped it down to just 2.7 dB.

But intense illumination means bright reflections. With one hand I
pointed the surveillance antenna at the overcast skies and held my
phone in the other. Gratifyingly, I almost instantly started seeing a
blip on the speed-versus-range radar plot, matched a few moments later
by the rumble of an approaching jet. (The plot updates about once every
3 seconds.) Because of the strength of the echoes, I was able to raise
the signal-cutoff threshold significantly, giving me radar returns
uncluttered with noise, and often with multiple aircraft. A win for
SDR!

Admittedly, my passive radar setup doesn't have much everyday value.
But as a demonstration of how far and fast inexpensive SDR technology
is advancing, it's a clear signal.

This article appears in the November 2022 print issue as "Passive Radar
With the KrakenSDR."
From Your Site Articles
* [111]Cuba Jamming Ham Radio? Listen For Yourself - IEEE Spectrum >
* [112]Software-Defined Radio Will Let Communities Build Their Own 4G
... >
* [113]Chasing Weather Balloons With Software-Defined Radio - IEEE
... >

[114]DIY[115]SDR[116]software defined radio[117]type:departments

[118]Stephen Cass

[119]Stephen Cass is the special projects editor at IEEE Spectrum. He
currently helms Spectrum's Hands On column, and is also responsible for
interactive projects such as the [120]Top Programming Languages app. He
has a bachelor's degree in experimental physics from Trinity College
Dublin.
The Conversation (2)
Thomas Johnson
Thomas Johnson04 Nov, 2022
SM

I'm curious if the use of digital TV signal sources introduces an ITAR
issue. The use of passive RF is governed by the US Munitions List,
Category 11(a)(3)(xxvii):

(xxvii) Bi-static/multi-static radar that exploits greater than 125 kHz
bandwidth and is lower than 2 GHz center frequency to passively detect
or track using radio frequency (RF) transmissions (e.g., commercial
radio, television stations);

https://www.ecfr.gov/current/title-22/chapter-I/subchapter-M/part-121

[121]0 Replies [122]Hide replies
Show More Replies
Michael Jacobs
Michael Jacobs31 Oct, 2022
M

Another fun passive radar project is to use this capability to detect
the reentry paths of meteors in the upper atmosphere. In this case one
would select a n ATSC TV pilot frequency that is beyond line of sight
so that under ordinary conditions the signal cannot be received. When a
meteor enters the atmosphere, it leaves a momentary ionized trail that
will reflect RF signals from beyond the horizon. Using power detection
or spectrum analyzer mode it is easy to see trails. With a USB
demodulator, you can even hear them including the Doppler shift!
[123]0 Replies [124]Hide replies
Show More Replies

[125]different colored layers and textures
[126]Energy[127]Topic[128]Type[129]News

[130]Egg-Crate Nanostructured PV Crosses Solar Threshold

6h
3 min read

[131]A Black Hawk helicopter with the DARPA logo on it flies over the
desert with no crew on board
[132]Robotics[133]Topic[134]Type[135]News

[136]Video Friday: Uncrewed

6h
3 min read

[137]A shot from overhead of a helicopter, with its rotors spinning. A
large cylindrical object hangs from it on a cable.
[138]Aerospace[139]Topic[140]Type[141]News[142]Transportation

[143]Chopper Rocket Chasers Played "Catch Me if You Can"

8h
4 min read

Related Stories

[144]History of
Technology[145]Topic[146]Magazine[147]Article[148]Type[149]November
2022

[150]Pong Was Boring--And People Loved It

[151]Artificial Intelligence[152]Topic[153]Type[154]News[155]Consumer
Electronics

[156]AI-Generated Fashion Is Next Wave of DIY Design

[157]Careers[158]Topic[159]Magazine[160]Type[161]Profile[162]November
2022

[163]Craig Partridge Is Still Working to Improve Internet Traffic

[164]DIY[165]Topic[166]Type[167]Feature

[168]From WinZips to Cat GIFs, Jacob Ziv's Algorithms Have Powered Decades of
Compression

The lossless-compression pioneer received the 2021 IEEE Medal of Honor

[169]Tekla S. Perry
21 Apr 2021
11 min read
Vertical
Photo of Jacob Ziv
Photo: Rami Shlush
Yellow

Lossless data compression seems a bit like a magic trick. Its cousin,
lossy compression, is easier to comprehend. Lossy algorithms are used
to get music into the popular MP3 format and turn a digital image into
a standard JPEG file. They do this by selectively removing bits, taking
what scientists know about the way we see and hear to determine which
bits we'd least miss. But no one can make the case that the resulting
file is a perfect replica of the original.

Not so with lossless data compression. Bits do disappear, making the
data file dramatically smaller and thus easier to store and transmit.
The important difference is that the bits reappear on command. It's as
if the bits are rabbits in a magician's act, disappearing and then
reappearing from inside a hat at the wave of a wand.

The world of magic had Houdini, who pioneered tricks that are still
performed today. And data compression has Jacob Ziv.

In 1977, Ziv, working with Abraham Lempel, published the equivalent of
Houdini on Magic: a paper in the IEEE Transactions on Information
Theory titled [170]"A Universal Algorithm for Sequential Data
Compression." The algorithm described in the paper came to be called
LZ77--from the authors' names, in alphabetical order, and the year.
LZ77 wasn't the first lossless compression algorithm, but it was the
first that could work its magic in a single step.

Jacob Ziv

A photo of Jacob Ziv

RAMI SHLUSH

Current job: Technion Distinguished Professor Emeritus, Faculty of
Electrical Engineering

Date of birth: 27 November 1931

Birthplace: Tiberias, British-ruled Palestine (now Israel)

Height: 172 centimeters

Family: Married to Shoshana, four children, nine grandchildren

Education: BSc, Dip-Eng, MSc, all in electrical engineering from
Technion, in 1954, 1955, 1957; Sc.D, MIT, 1962

Favorite books: Detective stories, particularly those featuring Perry
Mason

Favorite kind of music: classical, particularly Bach; jazz

Favorite food: Falafel, ice cream

How he starts the day: A cup of espresso and a piece of dark chocolate

Favorite movie: Casablanca (1942)

Organizational memberships: Israel Academy of Science and Humanities,
U.S. National Academy of Engineering, U.S. National Academy of
Sciences, American Philosophical Society, IEEE Fellow

Major awards: IEEE Medal of Honor "for fundamental contributions to
information theory and data compression technology, and for
distinguished research leadership"; [171]BBVA Foundation Frontiers of
Knowledge Award; [172]Claude E. Shannon Award of the IEEE Information
Theory Society

The following year, the two researchers issued a refinement, LZ78. That
algorithm became the basis for the Unix compress program used in the
early '80s; WinZip and Gzip, born in the early '90s; and the GIF and
TIFF image formats. Without these algorithms, we'd likely be mailing
large data files on discs instead of sending them across the Internet
with a click, buying our music on CDs instead of streaming it, and
looking at Facebook feeds that don't have bouncing animated images.

Ziv went on to partner with other researchers on other innovations in
compression. It is his full body of work, spanning more than half a
century, that earned him the [173]2021 IEEE Medal of Honor "for
fundamental contributions to information theory and data compression
technology, and for distinguished research leadership."

Ziv was born in 1931 to Russian immigrants in Tiberias, a city then in
British-ruled Palestine and now part of Israel. Electricity and
gadgets--and little else--fascinated him as a child. While practicing
violin, for example, he came up with a scheme to turn his music stand
into a lamp. He also tried to build a Marconi transmitter from metal
player-piano parts. When he plugged the contraption in, the entire
house went dark. He never did get that transmitter to work.

When the Arab-Israeli War began in 1948, Ziv was in high school.
Drafted into the Israel Defense Forces, he served briefly on the front
lines until a group of mothers held organized protests, demanding that
the youngest soldiers be sent elsewhere. Ziv's reassignment took him to
the Israeli Air Force, where he trained as a radar technician. When the
war ended, he entered Technion--Israel Institute of Technology to study
electrical engineering.

After completing his master's degree in 1955, Ziv returned to the
defense world, this time joining Israel's National Defense Research
Laboratory (now [174]Rafael Advanced Defense Systems) to develop
electronic components for use in missiles and other military systems.
The trouble was, Ziv recalls, that none of the engineers in the group,
including himself, had more than a basic understanding of electronics.
Their electrical engineering education had focused more on power
systems.

"We had about six people, and we had to teach ourselves," he says. "We
would pick a book and then study together, like religious Jews studying
the Hebrew Bible. It wasn't enough."

The group's goal was to build a telemetry system using transistors
instead of vacuum tubes. They needed not only knowledge, but parts. Ziv
contacted Bell Telephone Laboratories and requested a free sample of
its transistor; the company sent 100.

"That covered our needs for a few months," he says. "I give myself
credit for being the first one in Israel to do something serious with
the transistor."

In 1959, Ziv was selected as one of a handful of researchers from
Israel's defense lab to study abroad. That program, he says,
transformed the evolution of science in Israel. Its organizers didn't
steer the selected young engineers and scientists into particular
fields. Instead, they let them pursue any type of graduate studies in
any Western nation.
"In order to run a computer program at the time, you had to use punch
cards and I hated them. That is why I didn't go into real computer
science."

Ziv planned to continue working in communications, but he was no longer
interested in just the hardware. He had recently read Information
Theory (Prentice-Hall, 1953), one of the [175]earliest books on the
subject, by Stanford Goldman, and he decided to make information theory
his focus. And where else would one study information theory but MIT,
where Claude Shannon, the field's pioneer, had started out?

Ziv arrived in Cambridge, Mass., in 1960. His Ph.D. research involved a
method of determining how to encode and decode messages sent through a
noisy channel, minimizing the probability and error while at the same
time keeping the decoding simple.

"Information theory is beautiful," he says. "It tells you what is the
best that you can ever achieve, and [it] tells you how to approximate
the outcome. So if you invest the computational effort, you can know
you are approaching the best outcome possible."

Ziv contrasts that certainty with the uncertainty of a deep-learning
algorithm. It may be clear that the algorithm is working, but nobody
really knows whether it is the best result possible.

While at MIT, Ziv held a part-time job at U.S. defense contractor
[176]Melpar, where he worked on error-correcting software. He found
this work less beautiful. "In order to run a computer program at the
time, you had to use punch cards," he recalls. "And I hated them. That
is why I didn't go into real computer science."

Back at the Defense Research Laboratory after two years in the United
States, Ziv took charge of the Communications Department. Then in 1970,
with several other coworkers, he joined the faculty of [177]Technion.

Younger photo of Jacob Ziv

two men in front of a chalk board. Jacob Ziv (with glasses), who became
chair of Technion's electrical engineering department in the 1970s,
worked earlier on information theory with Moshe Zakai. The two
collaborated on a paper describing what became known as the Ziv-Zakai
bound.Photo: Jacob Ziv/Technion

There he met Abraham Lempel. The two discussed trying to improve
lossless data compression.

The state of the art in lossless data compression at the time was
Huffman coding. This approach starts by finding sequences of bits in a
data file and then sorting them by the frequency with which they
appear. Then the encoder builds a dictionary in which the most common
sequences are represented by the smallest number of bits. This is the
same idea behind Morse code: The most frequent letter in the English
language, e, is represented by a single dot, while rarer letters have
more complex combinations of dots and dashes.

Huffman coding, while still used today in the MPEG-2 compression format
and a lossless form of JPEG, has its drawbacks. It requires two passes
through a data file: one to calculate the statistical features of the
file, and the second to encode the data. And storing the dictionary
along with the encoded data adds to the size of the compressed file.

Ziv and Lempel wondered if they could develop a lossless
data-compression algorithm that would work on any kind of data, did not
require preprocessing, and would achieve the best compression for that
data, a target defined by something known as the Shannon entropy. It
was unclear if their goal was even possible. They decided to find out.

Ziv says he and Lempel were the "perfect match" to tackle this
question. "I knew all about information theory and statistics, and
Abraham was well equipped in Boolean algebra and computer science."

The two came up with the idea of having the algorithm look for unique
sequences of bits at the same time that it's compressing the data,
using pointers to refer to previously seen sequences. This approach
requires only one pass through the file, so it's faster than Huffman
coding.

Ziv explains it this way: "You look at incoming bits to find the
longest stretch of bits for which there is a match in the past. Let's
say that first incoming bit is a 1. Now, since you have only one bit,
you have never seen it in the past, so you have no choice but to
transmit it as is."

"But then you get another bit," he continues. "Say that's a 1 as well.
So you enter into your dictionary 1-1. Say the next bit is a 0. So in
your dictionary you now have 1-1 and also 1-0."

Here's where the pointer comes in. The next time that the stream of
bits includes a 1-1 or a 1-0, the software doesn't transmit those bits.
Instead it sends a pointer to the location where that sequence first
appeared, along with the length of the matched sequence. The number of
bits that you need for that pointer is very small.
"Information theory is beautiful. It tells you what is the best that
you can ever achieve, and (it) tells you how to approximate the
outcome."

"It's basically what they used to do in publishing TV Guide," Ziv says.
"They would run a synopsis of each program once. If the program
appeared more than once, they didn't republish the synopsis. They just
said, go back to page x."

Decoding in this way is even simpler, because the decoder doesn't have
to identify unique sequences. Instead it finds the locations of the
sequences by following the pointers and then replaces each pointer with
a copy of the relevant sequence.

The algorithm did everything Ziv and Lempel had set out to do--it
proved that universally optimum lossless compression without
preprocessing was possible.

"At the time they published their work, the fact that the algorithm was
crisp and elegant and was easily implementable with low computational
complexity was almost beside the point," says Tsachy Weissman, an
electrical engineering professor at Stanford University who specializes
in information theory. "It was more about the theoretical result."

Eventually, though, researchers recognized the algorithm's practical
implications, Weissman says. "The algorithm itself became really useful
when our technologies started dealing with larger file sizes beyond
100,000 or even a million characters."

"Their story is a story about the power of fundamental theoretical
research," Weissman adds. "You can establish theoretical results about
what should be achievable--and decades later humanity benefits from the
implementation of algorithms based on those results."

Ziv and Lempel kept working on the technology, trying to get closer to
entropy for small data files. That work led to LZ78. Ziv says LZ78
seems similar to LZ77 but is actually very different, because it
anticipates the next bit. "Let's say the first bit is a 1, so you enter
in the dictionary two codes, 1-1 and 1-0," he explains. You can imagine
these two sequences as the first branches of a tree."

"When the second bit comes," Ziv says, "if it's a 1, you send the
pointer to the first code, the 1-1, and if it's 0, you point to the
other code, 1-0. And then you extend the dictionary by adding two more
possibilities to the selected branch of the tree. As you do that
repeatedly, sequences that appear more frequently will grow longer
branches."

"It turns out," he says, "that not only was that the optimal
[approach], but so simple that it became useful right away."

Photo of Jacob Ziv (left) and Abraham Lempel. Jacob Ziv (left) and
Abraham Lempel published algorithms for lossless data compression in
1977 and 1978, both in the IEEE Transactions on Information Theory. The
methods became known as LZ77 and LZ78 and are still in use today.Photo:
Jacob Ziv/Technion

While Ziv and Lempel were working on LZ78, they were both on sabbatical
from Technion and working at U.S. companies. They knew their
development would be commercially useful, and they wanted to patent it.

"I was at Bell Labs," Ziv recalls, "and so I thought the patent should
belong to them. But they said that it's not possible to get a patent
unless it's a piece of hardware, and they were not interested in
trying." (The U.S. Supreme Court didn't open the door to direct patent
protection for software until the 1980s.)

However, Lempel's employer, Sperry Rand Corp., was willing to try. It
got around the restriction on software patents by building hardware
that implemented the algorithm and patenting that device. Sperry Rand
followed that first patent with a version adapted by researcher Terry
Welch, called the LZW algorithm. It was the LZW variant that spread
most widely.

Ziv regrets not being able to patent LZ78 directly, but, he says, "We
enjoyed the fact that [LZW] was very popular. It made us famous, and we
also enjoyed the research it led us to."

One concept that followed came to be called Lempel-Ziv complexity, a
measure of the number of unique substrings contained in a sequence of
bits. The fewer unique substrings, the more a sequence can be
compressed.

This measure later came to be used to check the security of encryption
codes; if a code is truly random, it cannot be compressed. Lempel-Ziv
complexity has also been used to analyze
electroencephalograms--recordings of electrical activity in the
brain--to [178]determine the depth of anesthesia, to [179]diagnose
depression, and for other purposes. Researchers have even applied it to
[180]analyze pop lyrics, to determine trends in repetitiveness.

Over his career, Ziv published some 100 peer-reviewed papers. While the
1977 and 1978 papers are the most famous, information theorists that
came after Ziv have their own favorites.

For Shlomo Shamai, a distinguished professor at Technion, it's the 1976
paper that introduced [181]the Wyner-Ziv algorithm, a way of
characterizing the limits of using supplementary information available
to the decoder but not the encoder. That problem emerges, for example,
in video applications that take advantage of the fact that the decoder
has already deciphered the previous frame and thus it can be used as
side information for encoding the next one.

For Vincent Poor, a professor of electrical engineering at Princeton
University, it's the 1969 paper describing [182]the Ziv-Zakai bound, a
way of knowing whether or not a signal processor is getting the most
accurate information possible from a given signal.

Ziv also inspired a number of leading data-compression experts through
the classes he taught at Technion until 1985. Weissman, a former
student, says Ziv "is deeply passionate about the mathematical beauty
of compression as a way to quantify information. Taking a course from
him in 1999 had a big part in setting me on the path of my own
research."

He wasn't the only one so inspired. "I took a class on information
theory from Ziv in 1979, at the beginning of my master's studies," says
Shamai. "More than 40 years have passed, and I still remember the
course. It made me eager to look at these problems, to do research, and
to pursue a Ph.D."

In recent years, glaucoma has taken away most of Ziv's vision. He says
that a paper published in IEEE Transactions on Information Theory this
January is his last. He is 89.

"I started the paper two and a half years ago, when I still had enough
vision to use a computer," he says. "At the end, Yuval Cassuto, a
younger faculty member at Technion, finished the project." The paper
discusses situations in which large information files need to be
transmitted quickly to remote databases.

As Ziv explains it, such a need may arise when a doctor wants to
compare a patient's DNA sample to past samples from the same patient,
to determine if there has been a mutation, or to a library of DNA, to
determine if the patient has a genetic disease. Or a researcher
studying a new virus may want to compare its DNA sequence to a DNA
database of known viruses.

"The problem is that the amount of information in a DNA sample is
huge," Ziv says, "too much to be sent by a network today in a matter of
hours or even, sometimes, in days. If you are, say, trying to identify
viruses that are changing very quickly in time, that may be too long."

The approach he and Cassuto describe involves using known sequences
that appear commonly in the database to help compress the new data,
without first checking for a specific match between the new data and
the known sequences.

"I really hope that this research might be used in the future," Ziv
says. If his track record is any indication, Cassuto-Ziv--or perhaps
CZ21--will add to his legacy.

This article appears in the May 2021 print issue as "Conjurer of
Compression."
Related Articles Around the Web
* [183]An introduction to Generative Art: what it is, and how you
make it >
* [184]Creating Art With Code >

Keep Reading |vShow less

References

Visible links
1. https://spectrum.ieee.org/feeds/topic/diy.rss
2. https://www.googletagmanager.com/ns.html?id=GTM-5WJB5X2
3. https://www.ieee.org/
4. https://ieeexplore.ieee.org/Xplore/home.jsp
5. https://standards.ieee.org/
6. https://www.ieee.org/sitemap.html
7. https://www.ieee.org/profile/public/createwebaccount/showCreateAccount.html?ShowMGAMarkeatbilityOptIn=true&sourceCode=spectrum&signinurl=https://spectrum.ieee.org/core/saml/main/login&url=https://spectrum.ieee.org/&autoSignin=Y&car=IEEE-Spectrum
8. https://spectrum.ieee.org/st/join
9. https://spectrum.ieee.org/passive-radar-with-sdr
10. javascript:void(0);
11. https://spectrum.ieee.org/topic/aerospace/
12. https://spectrum.ieee.org/topic/artificial-intelligence/
13. https://spectrum.ieee.org/topic/biomedical/
14. https://spectrum.ieee.org/topic/computing/
15. https://spectrum.ieee.org/topic/consumer-electronics/
16. https://spectrum.ieee.org/topic/energy/
17. https://spectrum.ieee.org/topic/tech-history/
18. https://spectrum.ieee.org/topic/robotics/
19. https://spectrum.ieee.org/topic/semiconductors/
20. https://spectrum.ieee.org/topic/sensors/
21. https://spectrum.ieee.org/topic/telecommunications/
22. https://spectrum.ieee.org/topic/transportation/
23. https://spectrum.ieee.org/
24. https://spectrum.ieee.org/topic/aerospace/
25. https://spectrum.ieee.org/topic/artificial-intelligence/
26. https://spectrum.ieee.org/topic/biomedical/
27. https://spectrum.ieee.org/topic/computing/
28. https://spectrum.ieee.org/topic/consumer-electronics/
29. https://spectrum.ieee.org/topic/energy/
30. https://spectrum.ieee.org/topic/tech-history/
31. https://spectrum.ieee.org/topic/robotics/
32. https://spectrum.ieee.org/topic/semiconductors/
33. https://spectrum.ieee.org/topic/sensors/
34. https://spectrum.ieee.org/topic/telecommunications/
35. https://spectrum.ieee.org/topic/transportation/
36. https://spectrum.ieee.org/type/feature/
37. https://spectrum.ieee.org/type/news/
38. https://spectrum.ieee.org/type/opinion/
39. https://spectrum.ieee.org/topic/careers/
40. https://spectrum.ieee.org/topic/diy/
41. https://spectrum.ieee.org/type/the-big-picture/
42. https://spectrum.ieee.org/engineering-resources/
43. https://spectrum.ieee.org/special-reports/
44. https://spectrum.ieee.org/collections/
45. https://spectrum.ieee.org/type/explainer/
46. https://spectrum.ieee.org/type/podcast/
47. https://spectrum.ieee.org/type/video/
48. https://spectrum.ieee.org/newsletters/
49. https://spectrum.ieee.org/top-programming-languages
50. https://robots.ieee.org/
51. https://spectrum.ieee.org/magazine/current-issue
52. https://spectrum.ieee.org/magazine/
53. https://spectrum.ieee.org/the-institute/
54. https://spectrum.ieee.org/the-institute/ti-archive/
55. https://spectrum.ieee.org/magazine/current-issue
56. https://spectrum.ieee.org/magazine/
57. https://spectrum.ieee.org/the-institute/
58. https://spectrum.ieee.org/the-institute/ti-archive/
59. https://spectrum.ieee.org/st/about
60. https://spectrum.ieee.org/st/contact
61. https://www.parsintl.com/publications/ieee-media/
62. https://advertise.ieee.org/
63. https://spectrum.ieee.org/st/join
64. https://ieee.omeda.com/ieee/r-main.do
65. https://www.ieee.org/about/
66. https://www.ieee.org/about/contact.html
67. https://www.ieee.org/accessibility-statement.html
68. https://www.ieee.org/about/corporate/governance/p9-26.html
69. https://www.ieee.org/about/help/site-terms-conditions.html
70. https://www.ieee.org/security-privacy.html
71. https://www.ieee.org/security-privacy.html
72. https://spectrum.ieee.org/passive-radar-with-sdr#toggle-gdpr
73. https://spectrum.ieee.org/passive-radar-with-sdr
74. https://spectrum.ieee.org/st/join
75. https://www.ieee.org/profile/public/createwebaccount/showCreateAccount.html?ShowMGAMarkeatbilityOptIn=true&sourceCode=spectrum&signinurl=https%3A%2F%2Fspectrum.ieee.org%2Fcore%2Fsaml%2Fmain%2Flogin%3Fnext_url%3Dhttps%3A%2F%2Fspectrum.ieee.org%2Fcore%2Fintegrations%2Fieee%2Fchanges%0A&url=https://spectrum.ieee.org/&autoSignin=Y&car=IEEE-Spectrum
76. https://spectrum.ieee.org/core/saml/main/login?next_url=https://spectrum.ieee.org/core/integrations/ieee/changes
77. https://spectrum.ieee.org/st/join
78. https://spectrum.ieee.org/core/saml/main/login?next_url=https://spectrum.ieee.org/core/integrations/ieee/changes
79. javascript:;
80. https://spectrum.ieee.org/passive-radar-with-sdr
81. https://www.ieee.org/profile/public/createwebaccount/showCreateAccount.html?ShowMGAMarkeatbilityOptIn=true&sourceCode=spectrum3c&signinurl=https%3A%2F%2Fspectrum.ieee.org%2Fcore%2Fsaml%2Fmain%2Flogin%3Fnext_url%3Dhttps%3A%2F%2Fspectrum.ieee.org%2Fcore%2Fintegrations%2Fieee%2Fchanges%0A&url=https://spectrum.ieee.org/&autoSignin=Y&car=IEEE-Spectrum
82. https://spectrum.ieee.org/core/saml/main/login?next_url=https://spectrum.ieee.org/core/integrations/ieee/changes
83. https://spectrum.ieee.org/topic/diy/
84. https://spectrum.ieee.org/topic/
85. https://spectrum.ieee.org/magazine/
86. https://spectrum.ieee.org/type/hands-on/
87. https://spectrum.ieee.org/type/
88. https://spectrum.ieee.org/magazine/2022/november/
89. https://spectrum.ieee.org/passive-radar-with-sdr
90. https://spectrum.ieee.org/u/stephen-cass
91. https://spectrum.ieee.org/tag/diy
92. https://spectrum.ieee.org/tag/sdr
93. https://spectrum.ieee.org/tag/software-defined-radio
94. https://spectrum.ieee.org/tag/type-departments
95. https://youtu.be/hvIg3PTJWxs?t=312
96. https://en.wikipedia.org/wiki/Passive_radar
97. https://en.wikipedia.org/wiki/Doppler_effect
98. https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=1705782
99. https://www.realtek.com/en/products/communications-network-ics/item/rtl2832u
100. https://spectrum.ieee.org/a-40-softwaredefined-radio
101. https://www.sdrplay.com/rspdx/
102. https://greatscottgadgets.com/hackrf/one/
103. https://www.crowdsupply.com/lime-micro/limesdr-mini-2
104. https://www.krakenrf.com/
105. https://www.rtl-sdr.com/tag/r820t2/
106. https://spectrum.ieee.org/chasing-weather-balloons-with-sdr
107. https://www.homedepot.com/p/Outdoor-TV-Antenna-Digital-UHF-with-100-Miles-Range-744841871152/316916810
108. https://www.necrat.us/empiretv.html
109. https://github.com/krakenrf/krakensdr_doa/releases/
110. https://en.wikipedia.org/wiki/Decibel
111. https://spectrum.ieee.org/cuba-jamming-ham-radio-listen-for-yourself
112. https://spectrum.ieee.org/softwaredefined-radio-will-let-communities-build-their-own-4g-networks
113. https://spectrum.ieee.org/chasing-weather-balloons-with-sdr
114. https://spectrum.ieee.org/tag/diy
115. https://spectrum.ieee.org/tag/sdr
116. https://spectrum.ieee.org/tag/software-defined-radio
117. https://spectrum.ieee.org/tag/type-departments
118. https://spectrum.ieee.org/u/stephen-cass
119. https://twitter.com/stephencass
120. https://spectrum.ieee.org/computing/software/the-2015-top-ten-programming-languages
121. javascript: void(0);
122. javascript: void(0);
123. javascript: void(0);
124. javascript: void(0);
125. https://spectrum.ieee.org/perovskite
126. https://spectrum.ieee.org/topic/energy/
127. https://spectrum.ieee.org/topic/
128. https://spectrum.ieee.org/type/
129. https://spectrum.ieee.org/type/news/
130. https://spectrum.ieee.org/perovskite
131. https://spectrum.ieee.org/video-friday-uncrewed
132. https://spectrum.ieee.org/topic/robotics/
133. https://spectrum.ieee.org/topic/
134. https://spectrum.ieee.org/type/
135. https://spectrum.ieee.org/type/news/
136. https://spectrum.ieee.org/video-friday-uncrewed
137. https://spectrum.ieee.org/reusable-rockets
138. https://spectrum.ieee.org/topic/aerospace/
139. https://spectrum.ieee.org/topic/
140. https://spectrum.ieee.org/type/
141. https://spectrum.ieee.org/type/news/
142. https://spectrum.ieee.org/topic/transportation/
143. https://spectrum.ieee.org/reusable-rockets
144. https://spectrum.ieee.org/topic/tech-history/
145. https://spectrum.ieee.org/topic/
146. https://spectrum.ieee.org/magazine/
147. https://spectrum.ieee.org/type/article/
148. https://spectrum.ieee.org/type/
149. https://spectrum.ieee.org/magazine/2022/november/
150. https://spectrum.ieee.org/pong-video-game
151. https://spectrum.ieee.org/topic/artificial-intelligence/
152. https://spectrum.ieee.org/topic/
153. https://spectrum.ieee.org/type/
154. https://spectrum.ieee.org/type/news/
155. https://spectrum.ieee.org/topic/consumer-electronics/
156. https://spectrum.ieee.org/dall-e-fashion-design
157. https://spectrum.ieee.org/topic/careers/
158. https://spectrum.ieee.org/topic/
159. https://spectrum.ieee.org/magazine/
160. https://spectrum.ieee.org/type/
161. https://spectrum.ieee.org/type/profile/
162. https://spectrum.ieee.org/magazine/2022/november/
163. https://spectrum.ieee.org/craig-partridge-profile
164. https://spectrum.ieee.org/topic/diy/
165. https://spectrum.ieee.org/topic/
166. https://spectrum.ieee.org/type/
167. https://spectrum.ieee.org/type/feature/
168. https://spectrum.ieee.org/from-winzips-to-cat-gifs-jacob-zivs-algorithms-have-powered-decades-of-compression
169. https://spectrum.ieee.org/u/tekla-perry
170. https://ieeexplore.ieee.org/document/1055714
171. https://www.frontiersofknowledgeawards-fbbva.es/
172. https://www.itsoc.org/honors/claude-e-shannon-award
173. https://corporate-awards.ieee.org/award/2021-ieee-medal-of-honor/
174. https://www.rafael.co.il/
175. https://books.google.com/books/about/Information_Theory.html?id=0kVgAAAAMAAJ
176. https://en.wikipedia.org/wiki/Melpar
177. https://www.technion.ac.il/en/home-2/
178. https://www.researchgate.net/publication/11597722_EEG_complexity_as_a_measure_of_depth_of_anesthesia_for_patients
179. https://link.springer.com/chapter/10.1007/978-3-319-11128-5_15
180. https://pudding.cool/2017/05/song-repetition/
181. https://ieeexplore.ieee.org/document/1055508
182. https://ieeexplore.ieee.org/abstract/document/1054301
183. https://www.freecodecamp.org/news/an-introduction-to-generative-art-what-it-is-and-how-you-make-it-b0b363b50a70/
184. https://www.codefellows.org/blog/creating-art-code/

Hidden links:
186. https://spectrum.ieee.org/
187. https://twitter.com/ieeespectrum
188. https://www.facebook.com/IEEE.Spectrum
189. https://www.instagram.com/ieeespectrum/
190. https://www.linkedin.com/company/ieee-spectrum/
191. https://www.youtube.com/c/ieeespectrum
192. https://spectrum.ieee.org/feeds/feed.rss
193. javascript:;
194. mailto:?subject=Build%20a%20Passive%20Radar%20With%20Software-Defined%20Radio&body=https://spectrum.ieee.org/passive-radar-with-sdr
195. https://spectrum.ieee.org/passive-radar-with-sdr
196. https://twitter.com/intent/tweet?url=https://spectrum.ieee.org/passive-radar-with-sdr&text=Build%20a%20Passive%20Radar%20With%20Software-Defined%20Radio&
197. https://www.facebook.com/sharer/sharer.php?u=https%3A%2F%2Fspectrum.ieee.org%2Fpassive-radar-with-sdr%3Fxrs%3DRebelMouse_fb%26ts%3D1666821686
198. http://www.linkedin.com/shareArticle?mini=false&url=https://spectrum.ieee.org/passive-radar-with-sdr&
199. https://spectrum.ieee.org/passive-radar-with-sdr
200. javascript: void(0);
201. javascript: void(0);
202. javascript: void(0);
203. javascript: void(0);
204. javascript: void(0);
205. javascript: void(0);
206. javascript: void(0);
207. javascript: void(0);
208. https://spectrum.ieee.org/pong-video-game
209. https://spectrum.ieee.org/dall-e-fashion-design
210. https://spectrum.ieee.org/craig-partridge-profile
211. mailto:?subject=From%20WinZips%20to%20Cat%20GIFs%2C%20Jacob%20Ziv%E2%80%99s%20Algorithms%20Have%20Powered%20Decades%20of%20Compression&body=https://spectrum.ieee.org/from-winzips-to-cat-gifs-jacob-zivs-algorithms-have-powered-decades-of-compression
212. https://spectrum.ieee.org/from-winzips-to-cat-gifs-jacob-zivs-algorithms-have-powered-decades-of-compression
213. https://twitter.com/intent/tweet?url=https://spectrum.ieee.org/from-winzips-to-cat-gifs-jacob-zivs-algorithms-have-powered-decades-of-compression&text=From%20WinZips%20to%20Cat%20GIFs%2C%20Jacob%20Ziv%E2%80%99s%20Algorithms%20Have%20Powered%20Decades%20of%20Compression&
214. https://www.facebook.com/sharer/sharer.php?u=https%3A%2F%2Fspectrum.ieee.org%2Ffrom-winzips-to-cat-gifs-jacob-zivs-algorithms-have-powered-decades-of-compression%3Fxrs%3DRebelMouse_fb%26ts%3D1664457009
215. http://www.linkedin.com/shareArticle?mini=false&url=https://spectrum.ieee.org/from-winzips-to-cat-gifs-jacob-zivs-algorithms-have-powered-decades-of-compression&
216. https://spectrum.ieee.org/from-winzips-to-cat-gifs-jacob-zivs-algorithms-have-powered-decades-of-compression