Transmission Layer for Digital TV

Video Communication System

In practial situation, there are errors.
- Channel Coding is used to handle the problem (protect the video bitstream, so its less sensitive to error)

Error Propagation in Digital Video

Transmission errors is common due to channel noise

Information may be altered or lost during transmission
Random bit errors: are caused by the imperfections of physical channels
- bit inversion, bit insertion and bit deletion.
Burst error: two or more bits in the data unit have changed from 1 to 1 or from 0 to 1.
- Does not necessarily mean that the errors occur in consecutive bits, the length of the burst is measured from the first corrupted bit to the last corrupted bit. Some bits in between may not have been corrupted.
- Sometimes are caused by packet loss in packet networks or system failures for a short time.

Every bit of error means a great loss of information for compressed video.
Whole video sequence may need to be discarded if the errors are not properly handled.
Burst errors is more destructive than random bit errors due to the loss or damage of a contiguous segment of bits.
The impact of Random bit errors can range from negligible to objectionable, depending on:
- Coding method:
  - Fixed length coding: will only affect one code word, and the caused damage is generally acceptable.
  - Variable length coding (VLC): can desynchronize the coded information such that many following bits are undecodable until the next synchronization code word appears.
- Position of bit error in coded data
  - for example, Affect I frame => Affect all the other B and P frames

Error Propagation in Video Transmission

The effect of transmission error of compressed video is never local.
- 1 bit error will affect all others
A single bit of error can ruin the whole picture or sequence of pictures.
Due to two reasons
- Use of Variable Length Coding (VLC)
  - lead to spatial error propagation
- Use of motion Compensation (MC)
  - lead to temporal error propagation

Spatial Error Propagation

Spatial Error Propagation – VLC

The variable length coding (VLC) introduces the problem of spatial error propagation.
The idea of VLC is to let the most frequently used codes use less bits and less frequently used codes use more bits.
Since the VLC is used, error at one location can spread to a wide area.
It is difficult to locate the source of error
If an error occurs in the bit sequence when it is decoded, then a false codeword would be detected.
This error is also possible to affect the next codewords, which would be incorrectly detected.

Case 1: Error changes a valid huffman code into another valid (but incorrect) huffman of the same length

The decoder cannot recognize that this error has occurred.
But subsequent huffman codes will be correctly decoded.

Case 2: Error changes a valid huffman code into another valid (but incorrect) huffman code of the different length

The decoder may not recognize an error at this point.
Synchronization with the bitstream is lost and it is likely that Huffman codes later in the bitstream will be discovered to be illegal.

Case 3 (Less Serious): Error changes a valid VLC into invalid (illegal) code

Synchronization with the bitstream is lost.
The decoder can immediately recongnize the error and take appropriate action.

Summary of Spatial Error Propagation –VLC:

If there is an error in a VLC sequence, it is unsure where the starting point of the error is. After the error, the decoder has no way to restart the VLC decoding.
- The decoder loses synchronization with the VLC stream
- DCT coefficients and motion vectors occurring after the error are likely to be incorrectly decoded.
- Macroblocks are coded in order from left to right and top to bottom, so this may cause an area to the right and bottom of the errored macroblock to become corrupted in the decoded frame
Need to wait for the next synchronization point (I frame) to restart the VLC code

The Error at the bit will propagate (Black is the error point, Red are propagated errors in above example)

An example of Spatial Error Propagation (Green are Errored points in the image)

Spatial Error Propagation - DC

In DC difference, the error will yield the same result like in VLC.

The error affects a dc coefficient in an intracoded macroblock
- The values of dc coefficients of adjacent blocks in a picture tend to be highly correlated.
- Each dc coefficient in an intracoded block is predicted from the dc coefficient of the previous coded block.
- An error in a dc coefficient will cause all subsequent dc coefficients in the slice to be incorrectly decoded.

Spatial Error Propagation – Motion Vector

The error affects a coded motion vector in a P or B picture
- Since motion vectors for adjacent macroblocks are often similar, they are encoded differentially with respect to the motion vectors in the previous coded macroblock.
- An error in a motion vector will therefore cause all subsequent vectors to be incorrectly decoded.
- An incorrect motion vector means that the macroblock may be predicted from the wrong area within a previous or future reference frame.

At the start of each slice, the decoder can resynchronize to the bitstream

The dc coefficient and motion vector predictions are reset at the start of the slice.

Resynchronization in Video Coding Standard

Used to reduce Spatial Error Propagation

Due to the nature of VLC, an error can propagate for a long until the next I-frame
To the worst situation, the decoder does not know when to restart the decoding operation
- Lose synchronization.
Need to add redundancy in the bitstream to re-gain synchronization.
- to designate one code word as the synchronization code word in the entropy coder.

Synchronization Code Word

Property: the entropy decoder will regain synchronization once a decoder captures such a code word
The next re-sync point is the start of the next GOB/Slice where a header is located.
Although synchronization can be obtained with a sync code word, the number of decoded symbols may be incorrect
- a shift of sequential blocks in a block-based coder

Different color represent different GOB (group of block/slice)

Yellow is the error point in above example => regain synchronization at next re-sync point

But we still want to know the location of that re-sync microblocks

Therefore we also need a side information to know the number of decoded block.

Side information such as spatial and temporal locations is normally included after the synchronization code to identify where the decoded blocks belong.

Temporal Error Propagation

In motion-compensated macroblock, video decoding is performed by referencing the previous frame and motion vectors
Hence if we have previous frame, we only need to code the motion vector and the residue error
Any error in the current frame will affect the successive frames that use it as the reference.
Error can propagate both temporally and spatially.

Corrupted I-Picture

All P pictures in the current GOP are predicted from the initial I picture, so these may be affected by the propagating corrupted area.
All B pictures between pairs of corrupted I and/or P pictures are likely to be affected in a similar way
- All B pictures within the current GOP.
- The B picture(s) between the I picture and the final P picture in the previous GOP.
- The B picture(s) between the final P picture in the current GOP and the I picture in the next GOP.

Corrupted P-Pictures

All P pictures after the errored P picture will be predicted from this picture and may be affected by the error.
B picture that uses the corrupted P pictures as prediction references may also be affected

Corrupted B-Pictures

No other pictures are predicted from B pictures, so the error will not propagate temporally

Transmission Layer – Channel Coding

Channel coding are applied before Modulator.

Serially Concatenated Channel Coding Architectures

For an acceptable quality video service, the bit error rate (BER) requirement is in the order of 10^-9
- BER = (Number of bits error / total number of tranmitted bits) , during a time interval
Use of concatenated coding approach can achieve the BER requirement.
The outer code is usually implemented with a R-S (ReedSolomon) Code.
The inner code uses trellis coded modulation (TCM), which combines coding and modulation in one step to achieve high coding gains without affecting the bandwidth of the signal.

Both satellite/terrestrial channels are more susceptible to transmission (bit) errors than cable networks
- Using more robust modulation scheme – QPSK/COFDM
- A more rigorous forward error control scheme is applied to each 188-byte packet.
  - Reed-Solomon code (Block coding)
  - Byte interleaving
  - TCM encoding (Convolution coding)

So it will look like:

Forward Error Control (FEC)

Sufficient additional check digits are added to each transmitted message.
- To enable the receiver not only to detect the presence of one or more errors in a received message.
- But also to locate the position of the error(s).
The number of additional check digits required for errorcorrection is much larger than that needed for just error detection
Block codes, e.g. hamming code, RS code, etc
Convolutional codes, e.g TCM code, etc.

Hamming Distance

Hamming distance – the minimum number of bit positions in which two valid codewords differ.

Revisit:

Minimum Hamming distance

the smallest Hamming distance between all possible pairs of codewords in a codebook**

e.g. 00000, 01011, 10101, 11110

d(00000, 01011) = 3

d(00000, 10101) = 3

d(00000, 11110) = 4

d(01011, 10101) = 4

d(01011, 11110) = 4

d(10101, 11110) = 3

Therefore the Minimum Hamming distance = 3

The error-detecting and error-correcting properties of a coding scheme are both related to its Hamming distance.
To detect $m$ errors: hamming distance = $m+1$
To correct $m$ errors: hamming distance = $2m + 1$

Example of 1-bit Error Correction Code

To correct 2 bit error, the hamming distance should be = 2x2+1 = 5.

Block Codes

The original message to be transmitted is treated as a single block (frame) during encoding and subsequent decoding processes
In general, each block of k source digits is encoded to produce an n-digit block (n > k) of output digits.
The encoder is said to produce an (n, k) code.

Lets Consider a single-bit error: say if bit 11 is corrupted from 1 to 0. The new modulo-2 sum is now

Note:

If two bit errors occur, the modulo-2 sum is nonzero, thus indicating an error, but the positions of the errors cannot be determined from the sum.
To summarize, The block code:
- can correct for single-bit errors and
- can detect two-bit errors
- but other multiple-bit errors cannot be detected

Reed-Solomon Code (RS)

Concept is similar to block codes.

The RS check bytes are added primarily to detect burst errors.
RS(204,188) – 16 check bytes that are appended to each 188-byte packet
- Enable up to 8 bytes in burst error in each 204-byte block to be identified and corrected.
- Problem: very long bursts (greater than 8 bytes) in a block cannot be corrected
- 16 check byte overhead introduced

Byte Interleaver

Very long bursts in a block – that is, greater than 8 bytes – can be broken down into smaller bursts by using an interleaving technique.
Rearranging the order of transmission of the bytes in each 204-byte block so that an error burst longer than 8 bytes will affect no more than 8 sequential bytes in the original 204 bytes.
Instead of transmitting each 204-byte block in order, the contents of the block are transmitted a column at a time.
- Each 204-byte block output by the RS coder is fragmented into twelve 17-byte subblocks.
- The transmitted byte sequence is then the first byte from each of the 12 subblocks, followed by the second in each subblock, and so on

The reverse operation is then performed at the receiver to reorder the bytes into their original sequence.
In this way, should an error burst of, say, 12 bytes occur within a block during its transmission,
- This will affect only every seventeenth byte in the original 204-byte block
- be detected and corrected by RS decoder
To summarize, Byte Interleaver produce a Reordered transmission
- If there is a bit error larger than 8 byte, long burst are broken into small burst

Convolutional Encoder

Satellite/terrestrial transmissions are susceptible to randomly distributed single bit errors

For each input bit, 2 bits are generated and tranmitted to modulators

Convolutional codes

Block codes (memoryless code): Each output codeword depends only on the current k-bit message block being encoded.

But Convolutional codes are different. It has some form of memory

Convolutional codes: some form of memory
- Each bit in the output sequence is dependent not only on the current bit being encoded but also the previous sequence of source bits
- The convolution (binary) operation is performed using one or more modulo-2 adders (exclusive-OR gates).

TCM (Trellis Coded Modulation)

TCM is a type of Convolutional codes.
TCM combines coding and modulation
- To improve the reliability of the digital transmission system without increase the transmission power and bandwidth

Simplified Example - TCM

Modulo-2 is actually XOR operation
- 0 0 => 0
- 0 1 => 1
- 1 0 => 1
- 1 1 => 0
Note the Input sequence I is the output of byte interleaver (204 bytes)
- so the output of TCM will be 408 bytes
For each bit in the input sequence, two bits are output, one from each of the two modulo-2 adders.
=> ½ (k/n) TCM encoder with a constraint length of 3

Because of the memory assoicated with the convolutional encoders, we must have a diagrammatic representation.

Tree diagram - used to Determine the outputs for each possible input sequence
State diagram - used to Determine the outputs for each possible input sequence
Trellis diagram - most frequently used method and useful for demonstrating the decoding operation

We still use the simplified example to represent it.

Note the tree diagram is completely depends on how to circuit is built.
Example of shifting: 000 => 001 (lower branch) => 011 (lower branch) => 111 (lower branch)

Note the number of states is depend on the number of shift registers. $2^{n-1}$

Therefore 2^2 = 4 states in 3 shift registers.
2^6 states in 7 shift registers.

We need to construct a state table

From above tree diagram, we get:

0 0 => A
0 1 => B
1 0 => C
1 1 => D

They will be used in Trellis Diagram.

Trellis Diagram is constructed from the tree diagram.

If input is 0, go to upper branch (see what is the next state)
If input is 1, go to lower branch (see what is the next state)
Then the state transitions will produce a Trellis Diagram.

Encoding

Once Trellis Diagram is constructed, we just need Trellis Diagram to do the encoding or decoding.

Decoding

Objective: determine the most likely output sequence, given a received bitstream. (which may have errors)
- Compare the received sequence with all possible sequences that may be obtained
- Select the sequence that is closest to the received sequence.

Recall: Hamming distance between two codewords is the number of bits that differ between them.

When selecting the sequence that is closest to the received sequence, the Hamming distance between the received sequence and each of the possible sequences is computed.

The one with the least distance is selected.

Viterbi algorithm

Comparing the complete received sequence with all possible sequences is impractical.
A running count is maintained of the distance between the actual received sequence and each possible sequence but, at each node in the trellis, only a single path is retained.
There are always two paths merging at each node
- Survivor path:
  - the path selected is the one with the minimum Hamming distance
  - the upper path is selected if they have same hamming distance.
- The other is simply terminated
The final path selected is the one with a continuous path through the trellis with a minimum aggregate Hamming distance.

Note we want the Sequence, not the state.
- Remember to turn the state back to the sequence

To Summarize:

Block Diagram of Concatenated Coding