US 8,914,713 B2Granted

Erasure coding scheme for deadlines

AssigneeCalifornia Institute of Technology

InventorsSvitlana Vyetrenko, Tracey C. Ho, Hongyi Yao, Omer Tekin

Life of this patent

Estimating the term…

Loading patent…

Abstract

Error correction coding for streaming communication is provided. A streaming problem is modeled as a non-multicast network problem with a nested receiver structure. Each packet in the streaming problem corresponds to a link, and each deadline in the streaming problem corresponds to a receiver in the non-multicast network problem. For the non-multicast network problem, content to be transmitted in multiple packets to multiple receivers is obtained. Each of the receivers is required to decode specific independent messages from the content, at given time steps, and has access to a subset of the content received by another receiver. The content is allocated into multiple packets to be transmitted on multiple links. No coding occurs across information demanded by different receivers. A capacity region defines a set of information rate vectors that can be communicated to the receivers successfully. A rate vector is successfully communicated if it complies with various inequalities.

Claims21

Dependent claims

A computer-implemented method for error correction coding for streaming communication, comprising:

(a) utilizing, in a computer, a coding scheme defined below in terms of a non-multicast network problem with a nested receiver structure, wherein each packet of multiple packets in a streaming problem corresponds to a link in the non-multicast network problem and each deadline of multiple deadlines in the streaming problem corresponds to a receiver in the nested receiver structure in the non-multicast network problem, wherein:
(i) each receiver of multiple receivers in the nested receiver structure is required to decode specific messages {M1,M2, . . . Mn), from content of received packets, at given time steps {m1, m2, . . . mn} respectively;
and
(ii) each of the multiple receivers in the nested receiver structure has access to a subset of the content received by another receiver in the nested receiver structure;
and
(b) allocating, in the computer, the content into the multiple packets, wherein:
no coding occurs across information demanded by different receivers in the nested receiver structure;
(ii) a capacity region defines a set of information rate vectors {u1, u2, . . . un, }, that can be communicated to the multiple receivers in the nested receiver structure successfully;
(iii) an information rate vector (u1, u2, . . ., un) from the set of information rate vectors is successfully communicated if:
(1) a sum of amounts (yij) of the information corresponding to a message Mj transmitted on unerased links li, is greater than or equal to uj for each of one or more erasure patterns per:
∀
j
:
1
≤
j
≤
n
⁢
⁢
u
j
≤
∑
i
∈
P
⋂
{
1
,
…
⁢
,
m
i
}
⁢
y
i
j
❘
where P denotes a set of unerased links for each erasure pattern;
and
(2) the sum of yij for 1≦j≦n is less than or equal to 1 per:
∀
i
:
1
≤
i
≤
m
n
⁢
⁢
∑
j
=
1
n
⁢
y
i
j
≤
1.

64 more elements

An apparatus for error correction coding for a non-multicast nested receiver structure in a computer system comprising:

(a) a computer having a memory;
(b) an application executing on the computer, wherein the application is configured to:
(i) utilize a coding scheme defined below in terms of a non-multicast network problem with a nested receiver structure, wherein each packet of multiple packets in a streaming problem corresponds to a link in the non-multicast network problem and each deadline of multiple deadlines in the streaming problem corresponds to a receiver in the nested receiver structure in the non-multicast network problem, wherein:
(1) each receiver of multiple receivers in the nested receiver structure is required to decode specific messages {M1, M2, . . . Mn), from content or received packets, at given time steps {m1, m2, . . . mn} respectively;
and
(2) each of the multiple receivers in the nested receiver structure has access to a subset of the content received by another receiver in the nested receiver structure;
(ii) allocate the content into the multiple packets, wherein:
(1) no coding occurs across information demanded by different receivers in the nested receiver structure;
(2) a capacity region defines a set of information rate vectors {u1, u2, . . . , un} that can be communicated to the multiple receivers in the nested receiver structure successfully;
(3) an information rate vector (u1, u2, . . . , un) from the set of information rate vectors is successfully communicated if:
(A) a sum of amounts (yij) of the information corresponding to a message Mj transmitted on unerased links li, is greater than or equal to uj for each of one or more erasure patterns per:
∀
j
:
1
≤
j
≤
n
⁢
⁢
u
j
≤
∑
i
∈
P
⋂
{
1
,
…
⁢
,
m
i
}
⁢
y
i
j
❘
;
where P denotes a set of unerased links for each erasure pattern;
and
(B) the sum of yij for 1≦j≦n is less than or equal to 1 per:
∀
i
:
1
≤
i
≤
m
n
⁢
⁢
∑
j
=
1
n
⁢
y
i
j
≤
1.

66 more elements

A non-transitory computer readable storage medium encoded with computer program instructions which when accessed by a computer cause the computer to load the program instructions to a memory therein creating a special purpose data structure causing the computer to operate as a specially programmed computer, executing a method of error correction coding for a non-multicast nested receiver structure, comprising:

(a) utilizing, in the specially programmed computer, a coding scheme defined below in terms of a non-multicast network problem with a nested receiver structure, wherein each packet of multiple packets in a streaming problem corresponds to a link in the non-multicast network problem and each deadline of multiple deadlines in the streaming problem corresponds to a receiver in the nested receiver structure in the non-multicast network problem, wherein:
(i) each receiver of multiple receivers in the nested receiver structure is required to decode specific messages {M1,M2, . . . Mn), from content of received packets, at given time steps {m1, m2, . . . mn} respectively;
and
(ii) each of the multiple receivers in the nested receiver structure has access to a subset of the content received by another receiver in the nested receiver structure;
(b) allocating, in the specially programmed computer, the content into the multiple packets, wherein:
no coding occurs across information demanded by different receivers in the nested receiver structure;
(ii) a capacity region defines a set of information rate vectors {u1, u2, . . . , un}, that can be communicated to the multiple receivers in the nested receiver structure successfully;
(iii) an information rate vector (u1, u2, . . ., un) from the set of information rate vectors is successfully communicated if:
(1) a sum of amounts (yij) of the information corresponding to a message Mj transmitted on unerased links li, is greater than or equal to uj for each of one or more erasure patterns per:
∀
j
:
1
≤
j
≤
n
⁢
⁢
u
j
≤
∑
i
∈
P
⋂
{
1
,
…
⁢
,
m
i
}
⁢
y
i
j
❘
where P denotes a set of unerased links for each erasure pattern;
and
(2) the sum of yij for 1≦j≦n is less than or equal to 1 per:
∀
i
:
1
≤
i
≤
m
n
⁢
⁢
∑
j
=
1
n
⁢
y
i
j
≤
1.

63 more elements

Dependencies are inferred from the claim text.

Facts

Application: 13/625,857Filed 24 Sep 2012 · us provisional application
Priority: 23 Sep 2011
Published: US 2013/0080861 A128 Mar 2013
Granted: 16 Dec 2014
Term ends: Not estimatedThe source records don’t support an estimate.

Classification11 codes

H03M 13/373
Decoding methods or techniques, not specific to the particular type of coding provided for in groups H03M13/03 - H03M13/35: with erasure…
H03M 13/154
Using error location or error correction polynomials: error and erasure correction, e.g. by using the error and erasure locator or Forney polynomial
H03M 13/293
Decoding strategies: with erasure setting
H03M 13/455
Wherein the candidate code words are obtained by an algebraic decoder, e.g. Chase decoding: using a set of erasure patterns or successive erasure…