Method for packet-level FEC encoding a stream of source packets using shifted interleaving

• US 8,223,643 B1
• Filed: 09/06/2006
• Issued: 07/17/2012
• Est. Priority Date: 09/06/2005
• Status: Active Grant

• Current Assignee: KenCast Inc.
• Original Assignee: KenCast Inc.
• Inventors: Wolfgang, H. Lewis
• Primary Examiner(s): Ly, Anh-Vu
• Assistant Examiner(s): Onamuti, Gbemileke
• Application Number:
  US11/516,197
• Time in Patent Office: 2,141 Days
• Field of Search: 375/219, 375/227, 375/259, 714/752, 714/712, 714/776, 714/746, 714/751, 370/235
• US Class Current: 370/235
• CPC Class Codes: H04L 1/0071 Use of interleaving interleaving per se H03M13/27

Abstract

A method for transmitting interleaved shares of packet-level FEC encoded packets, in which a given time shift occurs between consecutive shares, includes determining a current state; associating a packet with a share based on the current state; and determining a position of the packet within the share. Each share includes source packets and error-correcting or wildcard packets. If the position of the packet corresponds to a source packet position, a contribution of the packet to the wildcard packets of the share is computed, and the packet is transmitted as a source packet. If the position of the packet corresponds to a wildcard packet position, the packet is transmitted as a wildcard packet.

Claims

1. A method for transmitting interleaved shares of packet-level forward-error-correction encoded packets, each share including source packets and wildcard packets, wherein a given time shift occurs between consecutive shares, the method comprising the steps of:

determining a current state;

associating a packet with a share based on the current state;

determining a position of the packet within the share based on the given time shift; and

,

if the position of the packet corresponds to a source packet position, computing a contribution from the packet to wildcard packets of the share and transmitting the packet as a source packet, or, if the position of the packet corresponds to a wildcard packet position, transmitting the packet as a wildcard packet,

wherein positions of two consecutive packets within two shares are not the same, and

wherein the above steps are performed by a processor.

2. A method according to claim 1, wherein the given time shift is a difference in time between points of consecutive shares.

3. A method according to claim 1, wherein multiple shares of packets are transmitted as a lot, and wherein the method further comprises the steps of:

determining the given time shift, S, based on;

a number of source packets per share, K,

a number of wildcard packets per share, E, and

a number of shares per lot, L,

wherein K, E and L are integers; and

shifting a share by the given time shift, S, relative to a previous share, wherein S=(K+E)/L.

4. A method according to claim 3, wherein:

the multiple shares of packets form an interleaved arrangement, and

the step of determining a position of the packet within the share includes determining P=C−

R*5 modulo (K+E), wherein;

P represents the position of the packet within the share,

C represents a column number in the arrangement,

R represents a share number in the lot.

5. A method according to claim 4, wherein:

0≦

P≦

(K+E−

1);

0≦

R≦

(L−

1); and

C=is any one of 0, 1, 2, 3, . . . .

6. A method of shifting interleaved shares of packet-level forward-error-correction encoded packets to be transmitted, in which multiple shares of packets are transmitted as a lot, the method comprising the steps of:

determining a time shift, S, based on;

a number of source packets per share, K,

a number of error-correcting packets per share, E, and

a number of shares per lot, L,

wherein K, E and L are integers; and

shifting each interleaved share of packet-level forward-error correction encoded packets by the time shift, S, relative to a corresponding previous share, wherein S=(K+E)/L, wherein positions of two consecutive packets within two shares are not the same, and wherein the above steps are performed by a processor.

7. A method according to claim 6, wherein the step of shifting includes shifting a start point of the interleaved share by the time shift, S, relative to a start point of the corresponding previous share.

8. A method according to claim 6, further comprising the step of:

determining a position, P, of a packet in the interleaved share based on an interleaved arrangement of packets according to;

P=C−

R*S modulo(K+E),

wherein;

C represents a column number in the arrangement,

R represents a share number in the lot.

9. A method according to claim 8, wherein:

0≦

P≦

(K+E−

1);

0≦

R≦

(L−

1); and

C=is any one of 0, 1, 2, 3, . . . .

10. A method according to claim 8, wherein the time shift, S, represents a number of columns the interleaved share is shifted relative to the corresponding previous share.

11. A method according to claim 8, further comprising the step of:

if P<

K, determining an error-correction contribution to the interleaved share from a source packet at the position, P.

12. A method for transmitting interleaved shares of packet-level forward-error-correction encoded packets to be transmitted, in which multiple shares of packets are transmitted as a lot, the method comprising the steps of:

determining a time shift, S, based on;

a number of source packets per share, K,

a number of error-correcting packets per share, E, and

a number of shares per lot, L,

wherein K, E and L are integers, and

wherein S=(K+E)/L;

shifting a share by the time shift, S, relative to a previous share;

arranging the lot packets to be transmitted according to columns and rows, with C representing a column number and R representing a row number, wherein 0≦

R≦

(L−

1) and R corresponds to a share in the lot;

transmitting a packet at a first position identified by R and C;

determining a next position such that;

if R+1=L, set R=0 and increase C by 1, or,

if R+1<

L, then set R=R+1; and

transmitting a packet at the next position,

wherein positions of two consecutive packets within two shares are not the same.

13. A method according to claim 12, further comprising the step of:

determining a position, P, of a packet in a share of the lot based on an interleaved arrangement of packets according to P=C−

R*S modulo (K+E).

14. A method according to claim 13, wherein:

C=is any one of 0, 1, 2, 3, . . . , and

0≦

P≦

(K+E−

1).

15. A method according to claim 13, wherein the time shift, S, represents a number of columns a share of the lot is shifted relative to a previous share of the lot.

16. A method according to claim 13, further comprising the step of:

if P<

K, determining an error-correction contribution to the share from a source packet at the position, P.

17. A computer programmed to perform transmitting of interleaved shares of packet-level forward-error-correction encoded packets, each share including source packets and wildcard packets, wherein a given time shift occurs between consecutive shares, by using a processor to perform the steps of:

determining a current state;

associating a packet with a share based on the current state;

determining a position of the packet within the share based on the given time shift; and

,

if the position of the packet corresponds to a source packet position, computing a contribution from the packet to wildcard packets of the share and transmitting the packet as a source packet, or, if the position of the packet corresponds to a wildcard packet position, transmitting the packet as a wildcard packet,

wherein positions of two consecutive packets within two shares are not the same.

18. A computer programmed to perform shifting of interleaved shares of packet-level forward-error-correction encoded packets to be transmitted, in which multiple shares of packets are transmitted as a lot, by using a processor to perform the steps of:

determining a time shift, S, based on;

a number of source packets per share, K,

a number of error-correcting packets per share, E, and

a number of shares per lot, L,

wherein K, E and L are integers; and

shifting each interleaved share of packet-level forward-error correction encoded packets by the time shift, S, relative to a corresponding previous share, wherein S=(K+E)/L, wherein positions of two consecutive packets within two shares are not the same.

19. A computer programmed to perform transmitting of interleaved shares of packet-level forward-error-correction encoded packets to be transmitted, in which multiple shares of packets are transmitted as a lot, by using a processor to perform the steps of:

determining a time shift, S, based on;

a number of source packets per share, K,

a number of error-correcting packets per share, E, and

a number of shares per lot, L,

wherein K, E and L are integers, and

wherein S=(K+E)/L;

shifting a share by the time shift, S, relative to a previous share;

arranging the lot packets to be transmitted according to columns and rows, with C representing a column number and R representing a row number, wherein 0≦

R≦

(L−

1) and R corresponds to a share in the lot;

transmitting a packet at a first position identified by R and C;

determining a next position such that;

if R+1=L, set R=0 and increase C by 1, or,

if R+1<

L, then set R=R+1; and

transmitting a packet at the next position, wherein positions of two consecutive packets within two shares are not the same.

20. A communications system for transmitting interleaved shares of packet-level forward-error-correction encoded packets, each share including source packets and wildcard packets, wherein a given time shift occurs between consecutive shares, comprising:

a transmitter configured to perform;

determining a current state;

associating a packet with a share based on the current state;

determining a position of the packet within the share based on the given time shift; and

,

if the position of the packet corresponds to a source packet position,

computing a contribution from the packet to wildcard packets of the share and transmitting the packet as a source packet, or, if the position of the packet corresponds to a wildcard packet position, transmitting the packet as a wildcard packet,

wherein positions of two consecutive packets within two shares are not the same.

21. A communications system for transmitting shifted interleaved shares of packet-level forward-error-correction encoded packets, in which multiple shares of packets are transmitted as a lot, comprising:

a transmitter configured to perform;

determining a time shift, S, based on;

a number of source packets per share, K,

a number of error-correcting packets per share, E, and

a number of shares per lot, L,

wherein K, E and L are integers; and

shifting each interleaved share of packet-level forward-error correction encoded packets by the time shift, S, relative to a corresponding previous share, wherein S=(K+E)/L,

wherein positions of two consecutive packets within two shares are not the same.

22. A communications system for transmitting interleaved shares of packet-level forward-error-correction encoded packets to be transmitted, in which multiple shares of packets are transmitted as a lot, comprising:

a transmitter configured to perform;

determining a time shift, S, based on;

a number of source packets per share, K,

a number of error-correcting packets per share, E, and

a number of shares per lot, L,

wherein K, E and L are integers, and

wherein S=(K+E)/L;

shifting a share by the time shift, S, relative to a previous share;

arranging the lot packets to be transmitted according to columns and rows, with C representing a column number and R representing a row number, wherein 0≦

R≦

(L−

1) and R corresponds to a share in the lot;

transmitting a packet at a first position identified by R and C;

determining a next position such that;

if R+1=L, set R=0 and increase C by 1, or,

if R+1<

L, then set R=R+1; and

transmitting a packet at the next position,

wherein positions of two consecutive packets within two shares are not the same.