Coding for real-time streaming under packet erasures

Patent metadata

Field	Value
Publication number	US-9531780-B2
Application number	US-201314080686-A
Country	US
Kind code	B2
Filing date	Nov 14, 2013
Priority date	Nov 14, 2012
Publication date	Dec 27, 2016
Grant date	Dec 27, 2016

Abstract

A computer-based real-time streaming system under packet erasures wherein created messages can be decoded within a fixed delay form their creation is presented. Various code construction methods and corresponding hardware implementation for different cases of erasure link models are also presented.

First claim

The invention claimed is:

1. A computer-based method for real-time streaming of a plurality of independent messages over a communication link, the computer-based method comprising the steps:
i) providing via a computer, a message size s of each of the plurality of independent messages at the creation time thereof;
ii) providing via a computer, a message creation interval c based on a number of time steps, wherein the message creation interval defines the time interval between creation times of two consecutive messages of the plurality of independent messages;
iii) providing via a computer, a packet size, wherein the packet size defines a size of an encoded packet transmitted at each time step;
iv) providing via a computer, a link erasure characteristic, wherein the link erasure characteristic defines a communication link over which the encoded packet is transmitted;
v) providing via a computer, a fixed decoding delay d in number of time steps, wherein the fixed decoding delay defines a delay with respect to a creation time of a message from the plurality of independent messages within which the message must be decoded, via a computer-based decoder, based on one or more transmitted encoded packets;
vi) based on the steps i)-v), generating via a computer an encoding algorithm;
vii) based on step vi), generating via a computer a decoding algorithm;
viii) creating a computer-based encoder operatively implementing the encoding algorithm in one or more of hardware, firmware and software of the computer-based encoder, and
ix) creating a computer-based decoder operatively implementing the decoding algorithm in one or more of hardware, firmware and software of the computer-based decoder,
wherein a message of the plurality of independent messages encoded by the computer-based encoder into one or more encoded packets and transmitted over a communication link having the link erasure characteristic is decoded by the computer-based decoder within the fixed decoding delay from a creation time of the message;
wherein the link erasure characteristic is based on an erasure model in which transmitted packets are erased only according to admissible erasure patterns.

2. The computer-based method of claim 1 , wherein the link erasure characteristic is based on a window-based erasure model in which all erasure patterns containing a limited number of erasures in each specifically defined window are admissible.

3. The computer-based method of claim 2 , wherein the specifically defined window is one of: a) a coding window, and b) a sliding window.

4. The computer-based method of claim 1 , wherein the link erasure characteristic is based on a bursty erasure model in which all erasure patterns containing erasure bursts of a limited length, separated by intervals of at least a specified length, are admissible.

5. The computer-based method of claim 1 , wherein the link erasure characteristic is based on an independent and identically distributed erasure model in which transmitted packets are erased independently with the same probability.

6. The computer-based method of claim 2 , wherein the computer-based encoder has a fixed memory size m E and wherein the encoding algorithm operatively implemented within the computer-based encoder is a symmetric time-invariant intra-session coding (STIC) algorithm and comprises the computer-generated steps of:
a. choosing a spreading parameter m=∈{c, c+1, . . . , min(d, m E )} where m E is the encoder memory size;
b. defining an effective coding window W i {(i−1)c+1, . . . , (i−1)c+m} for each message M i of the plurality of independent messages;
c. defining a set of active messages A t at each time step t as A t {M i : t∈W i };
d. dividing a packet space of a packet to be transmitted at each time step t evenly among the set of active messages at time step t, and
e. using a max distance separable (MDS) code or random linear code to encode each message M i of the set of active messages into an appropriate number of symbols corresponding to a space of the packet space allocated to that message in the packet to be transmitted.

7. The computer-based method of claim 6 , wherein the computer-based decoder receives a subset of the encoded packets, and based on the received packets, decodes each message separately using a computer-based decoder for the MDS or random linear code used to encode that message.

8. The computer-based method of claim 7 , wherein the MDS code is a Reed-Solomon code.

9. The computer-based method of claim 7 , wherein the linear code is constructed based on a random linear combination of symbols in a finite field.

10. The computer-based method of claim 4 , wherein the bursty erasure model has a maximum erasure burst length z so that s≦c(d−z)/d, and wherein the encoding algorithm operatively implemented within the computer-based encoder is a diagonally interleaved coding (DIC) algorithm and comprises the computer-generated steps of:
a. considering a rectangular grid with d rows, where each column represents one encoded packet of normalized unit size; each cell in the grid contains one symbol of normalized size 1/d; the top d−z rows of the grid contain the message information symbols, while the bottom z rows contain the parity symbols;
b. inserting the c(d−z) message symbols of message k, which is created at time step (k−1)c+1, into the cells in the top d−z rows of columns (k−1)c+1, . . . , (k−1)c+c, wherein zero padding or repeated symbols may be used if there are fewer than c(d−z) message symbols;
c. applying a computer-generated component systematic block code C to each diagonal on the grid, to generate the parity symbols in the bottom z rows, and
d. transmitting each column of d symbols as a packet at the corresponding time step.

11. The computer-based method of claim 10 , wherein the computer-generated component systematic block code C comprises d symbols, the first d−z symbols being information symbols, while the last z symbols being parity symbols which can be non-degenerate or degenerate, and is generated using the following computer-generated steps:
a. selecting the degenerate parity symbols by grouping parity symbols into disjoint intervals of d−z symbols, if available, counting from the end of the block code, wherein degenerate parity symbols are uncoded copies of the information symbols, arranged in the same order;
b. setting the remaining z′ parity symbols as the non-degenerate parity symbols, where 0≦z′<d−z;
c. arranging the information symbols into rows of z′ symbols, counting from the beginning of the block code; if there are fewer than z′ symbols in the last row, then repeat them as many times as necessary until the row is filled, and
d. arranging the z′ non-degenerate parity symbols below the last row of information symbols, and setting each non-degenerate parity symbol to be the bit-wise modulo-2 sum of the information symbols above the each non-degenerate parity symbol,

wherein the computer-generated component systematic block code is given by the d−z information symbols, followed by the z′ non-degenerate parity symbols (if any), followed by the z−z′ degenerate parity symbols, if any.

12. The computer-based method of claim 10 , wherein the computer-based decoder receives a subset of the encoded packets, and recovers the erased message symbols by taking a bit-wise modulo-2 sum of appropriate codeword symbols on each diagonal.

13. The computer-based method of claim 1 further comprising:
providing parameters specifying decoding requirements for high and low priority messages, wherein high and low priority messages are created according to a periodic pattern such as a message of the

Assignees

• California Inst Of Techn

Inventors

• Leong Derek
• Qureshi Asma
• Wei Yunkai
• Ho Tracey C

Classifications

• H04N19/67

  involving unequal error protection [UEP], i.e. providing protection according to the importance of the data · CPC title

• H03M13/2909

  Product codes · CPC title

• H03M13/2721

  the interleaver involves a diagonal direction, e.g. by using an interleaving matrix with read-out in a diagonal direction · CPC title

• H03M13/373 Primary

  with erasure correction and erasure determination, e.g. for packet loss recovery or setting of erasures for the decoding of Reed-Solomon codes · CPC title

• H03M13/293

  with erasure setting · CPC title