Archives

April 2001 Issue
Video Compression 6: Lossless Compression
By

Although information is sometimes lost during compression, the goal is to lose only information the eye or ear cannot detect.

Once video is compressed, repetitive patterns in the data may be removed from the data stream by substituting short code sequences for longer sequences. According to the rules, orginal data must be recovered exactly, hence the technique is said to be "lossless." Long, repetitive patterns of bits should be looked for and replaced with shorter bit sequences.

You should construct a table of bit patterns and the replacement codes. If the pattern is constructed incorrectly, the data rate may increase. If it is done well and common bit patterns are correctly identified, they may be replaced with shorter patterns.

An example familiar to ham radio operators is the International Code (commonly, although incorrectly, called the Morse code), which is a data reduction construct itself.

The most common letter in the English language is e, so it has the shortest code group, a single dit. In international code practices, there are no dots and dashes. Rather, there are dits and dahhs. A dahh is three times as long as a dit. The time between any two elements (dit or dahh) is the same as the length of a dit.

Other common letters are i, represented by dit-dit, s (dit-dit-dit) and t (a single dahh). Uncommon letters include j (dit-dahh-dahh-dahh) and z (dahh-dahh-dit-dit). Commonly occurring letters are assigned short code sequences, and less commonly occurring letters have long sequences making it possible to send code faster than if code groups were randomly assigned.

Similarly, with Moving Pictures Experts Group (MPEG) transmission, long but commonly occurring groups of bits are assigned short code groups, and less frequently occurring groups of bits have longer code groups. An uncommon group of bits will be represented by more bits than it contained originally. A table is constructed defining the bit sequence and the resulting code group, and the substitution is made. The substitution is reversed in the receiving equipment.

Stringing it all together

Picture a bucket containing a bunch of bits representing audio, pictures and other things. The bucket of bits must first be organized into something that can be transmitted and recovered at the receiver. This may be done by organizing the compressed data into streams in a multiplexing process. Dr. Michael Isnardi of Sarnoff Labs, offered the following explanation in a lecture he presented at the IEEE Consumer Electronics Society’s International Conference on Consumer Electronics (www.icce.org) in 1998.

The basic concept

Figure 1 illustrates the concept of packetizing data. Video and audio encoders compress the picture. Periodically, each encoder completes its work on a block of data and becomes ready to move the data along to the next process, which sends it to its destination.

At this point, only the bucket of bits needs to be organized. The bucket represents a piece of audio or video information that has been compressed in either the audio or video encoders, timing and control information or other data.

The bucket may be organized by placing the bits in a time order similar to a progression of railroad cars. The railroad car, or packet, is identified by a label of its contents, also known as a header. A header precedes each packet in time. When the bits are organized into packets, those packets must be organized. This may be done in several steps.

Figure 2 illustrates the packets arriving at random intervals. When an encoder finishes with a packet, it presents it for transmission. The packet, however, must wait its turn. It is the function of the packet scheduler and multiplexer to sort out when each packet gets transmitted. The output of the multiplexer is a parade in time of all the packets presented for transport. This is illustrated by the contents of railroad cars (the bits are refered to as payload), but they are transmitted serially in time on the same transmission path.

The packet scheduler and multiplexer (mux) has been shown as one process, but actually a couple of processes are occurring. Essentially, the packets are groomed so they may be stored or transmitted. The first step is to put the packets into a program elementary stream (PES), which is a variable length bit stream consisting of the bits handed to the mux by the encoder. A header identifies the packet as video, audio and so on. It also includes a time stamp, which the decoder eventually will need in order to know when to decode and display the packet.

The PES contains the number of bits required, which depends, among other things, on picture content. Because a variable number of bits is required to represent a picture (pictures move at a regular rate of 24 or 30 frames per second (FPS) in North America, and 25 FPS in Europe), the PES data stream will be a variable bit rate stream. This is convenient for storage, but not so convenient for transmission. Next month, we will discuss PES, transport and error correction.

Jim Farmer is the chief technical officer of Wave7 Optics. He may be reached at .

 Back to April 2001 Issue

Access Intelligence's CABLE GROUP
Communications Technology | CableFAX Daily | CableFAX's CableWORLD | CT's Pipeline
CableFAX Magazine | CableFAX databriefs | Broadband Leaders Retreat | CableFAX Leaders Retreat