You’re in a crowded, noisy room raising your voice to be heard. Everyone else is doing the same, and the cacophony makes you wish you knew sign language, because conversation is out of the question.
The same problem occurs in wireless communications, says Tiffany Jing Li, the P.C. Rossin Assistant Professor of electrical and computer engineering. Many wireless conversations over a radio frequency band spell trouble, because distorted signals interfere with each other and cause errors.
When Li thinks of magnetic data storage devices, she pictures millions of tiny Post-It notes crammed together. As notes are added and space becomes tighter, things get unstable and you can find yourself reading a few of your neighbor’s notes in addition to your own.
Li’s research is in a field known as error correction coding. She seeks to accommodate, in a limited-frequency bandwidth or storage space, the rapidly increasing global appetite for cell phones, text messaging, multimedia streaming, optical signals and hard disk drive storage. Her coding helps prevent an unacceptable rate of errors by making data robust enough to be transmitted across devices without drowning in noise.
What is an acceptable rate? With voice, says Li, it’s one error per thousand signals; with text, one per million; with optical, one per billion; and with data storage, one per trillion.
Li does coding research for WiMax (Worldwide Interoperability for Microwave Access), a standards-based technology that enables the delivery of last-mile wireless broadband access as an alternative to cable and DSL. Her coding will enable cameras to transmit photos wirelessly to computers, allow handhelds to exchange data and multimedia files reliably, and improve the quality of digital video broadcasting over the Internet.
In digital video broadcasting, a “tail-biting” code chases the signal and makes corrections after one trial transmission. The Mobile WiMax standard (IEEE 802.16e) and Digital Video Broadcast (DVB) standard adopt tail-biting codes, whose “code trellis” must start from an initial state that coincides with the end state. The current encoding method must run through the entire encoding module two times, the first time to feel out the possible end state so that the correct starting state can be initiated, and the second time to actually encode the data.
“We have a smarter way,” says Li. “We can cleverly predict the end state without needing to run through the code trellis. It’s twice as fast.”
Li also has found a better way to disseminate data in broadcasting. Currently, 10 or 20 “packets” of video are broadcast wirelessly at one time to many receivers. If one packet is not received by any of the destinations, all 20 are re-broadcast.
“This is inefficient,” she says. “Instead, our code sends 30 packets, so even if you don’t receive a few, you will have everything you need.”
Li also has developed new classes of “digital fountain codes” for disseminating data in broadcasting or multicasting. A digital fountain encodes a set of data packets into an infinite sequence of coded packets or “digital drops,” any of which can be used to reconstruct the original set of data packets.
Consider, for example, that 50 people are simultaneously downloading a video clip from YouTube. A 15-second clip often consists of 400 frames of images, which are transmitted in a string of data packets. Because of channel noise, packet collision and buffer overflow, some data packets will be lost or corrupted. Resending the missing packets is costly. But by using digital fountain codes, the set of images can be encoded into many coded packets and transmitted continuously to end users. Some packets get lost, but as long as each user’s computer receives enough packets, it can reconstruct the original video clip.
Li says these smart codes have applications in teleconferencing, online-classroom, e-medicine, Internet TV, video-on-demand, and digital video broadcasting. She and her students have found new ways to construct these codes, some of which will likely outperform the best-known fountain codes.
Li is also developing error-resilient coding solutions for hostile environments such as disaster recovery and battlefield communications. Her work is supported by NSF and industry. “These new codes will become increasingly critical to our way of life,” she says. “We used to use the Internet for just e-mail and Web surfing, but now we’re using it for peer-to-peer content distribution. We are entering a new world, and noise levels are about to increase substantially. But we’ll handle it.”