Efficient source blocking algorithm for FEC for MBMS streaming

• US 20060077890A1
• Filed: 10/05/2005
• Published: 04/13/2006
• Est. Priority Date: 10/07/2004
• Status: Abandoned Application

• Current Assignee: Nokia Corporation
• Original Assignee: Nokia Corporation
• Inventors: Vedantham, Ramakrishna, Curcio, Igor, Suryavanshi, Vijay
• Application Number:
  US11/244,629
• Publication Number:
  US 20060077890A1
• Time in Patent Office: Days
• US Class Current: 370/216
• CPC Class Codes: H03M 13/05 using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits H03M13/2906 takes precedence
• CPC Class Codes: H04L 1/0041 Arrangements at the transmitter end
• CPC Class Codes: H04L 1/0057 Block codes H04L1/0061, H04L1/0064 take precedence
• CPC Class Codes: H04L 1/0078 Avoidance of errors by organising the transmitted data in a format specifically designed to deal with errors, e.g. location forward error control, e.g. FEC, CRC H04L1/004; adaptive formatting H04L1/0006; mappings H04L27/00
• CPC Class Codes: H04L 1/0083 Formatting with frames or packets; Protocol or part of protocol for error control
• CPC Class Codes: H04L 2001/0093 Point-to-multipoint
• CPC Class Codes: H04L 65/1101 Session protocols
• CPC Class Codes: H04L 65/611 for multicast or broadcast systems for broadcast or conference H04L12/18; arrangements for broadcast or distribution combined with broadcast H04H20/00; arrangements for broadcast applications with a direct linkage to broadcast information or to broadcast space-time H04H60/00; selective distribution of broadcast services, e.g. multimedia broadcast multicast service [MBMS], H04W4/06
• CPC Class Codes: H04L 65/65 Network streaming protocols, e.g. real-time transport protocol [RTP] or real-time control protocol [RTCP]
• CPC Class Codes: H04L 65/70 Media network packetisation
• CPC Class Codes: H04L 65/80 Responding to QoS

Abstract

A hybrid-padding approach for arranging variable size data packets for error correction encoding and decoding is disclosed. The approach can involve arranging the data packets in columns and rows and selecting the row size to minimize the amount of padding required. If data packet is smaller than the number of rows the data packet is inserted into the column and the remaining rows are padded. If the data packet is larger than the number of rows, the data packet is allowed to span multiple columns with the last column being padded if necessary. The data packets can include parameters, such as a source block number, packet length, and starting column number, and the error correction packets can include parameters, such as, a source block number an N, a K, the starting column number, and the number of row, to signal the hybrid-padding message.

Claims

1. A method for arranging a plurality of variable size data packets for FEC encoding and decoding, the method comprising:

Selecting a number of rows of an encoding block arranged in rows and columns;

Filling the plurality of data packets into the columns of a encoding block by;

if a data packet has a size smaller than the selected number of rows, entering the data packet into a column and padding the remaining rows with at least one padded symbol;

or

if a data packet has size larger than the selected number of rows, allowing the data packet to span across multiple columns and padding a last column spanned by the data packet with at least one padded symbol;

Forming FEC data blocks; and

Appending the filled encoding block with the FEC data blocks.

2. The method of claim 1, wherein the number of rows is selected to equal an average size of the data packets.

3. The method of claim 1, wherein the number of rows is selected based on the following algorithm:

$\mathrm{For}<br><br>\text{\hspace{1em}<br><br>}<br><br>j=1<br><br>\text{\hspace{1em}<br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{to}<br><br>\text{\hspace{1em}<br><br>}<br><br>M$ $\text{{}<br><br>\mathrm{Total\_padding}<br><br>\mathrm{\_j}=\underset{k=1}{\overset{M}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>\left(\mathrm{s\_j}\right)-\left[\left(\mathrm{s\_k}\right)<br><br>\mathrm{mod}<br><br>\left(\mathrm{s\_j}\right)\right]$ $\mathrm{If}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{Total\_padding}<br><br>\mathrm{\_j}<<br><br>\mathrm{Min\_Padding},<br><br>\mathrm{Then}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{Min\_padding}=\mathrm{Total\_padding}<br><br>\mathrm{\_j}<br><br><br><br>\mathrm{Number\_of}<br><br>\mathrm{\_rows}=\mathrm{s\_j}<br><br>\text{}}$ $\mathrm{Where}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{the}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{plurality}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{of}<br><br>\text{\hspace{1em}<br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{data}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{blocks}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{have}<br><br>\text{\hspace{1em}<br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{sizes}<br><br>\left\{\mathrm{s\_}<br><br>1,\mathrm{s\_}<br><br>2,\mathrm{s\_}<br><br>3<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{\dots <br><br>}<br><br>\text{\hspace{1em}<br><br>},\mathrm{s\_M}\right).$

4. The method of claim 1, wherein, the at least one padded symbol is zero.

5. The method of claim 1, wherein the at least one padded symbol is an arbitrary symbol that is agreed between a sender and receiver.

6. A computer code product for arranging a plurality of variable size data packets for FEC encoding and decoding, the computer code product comprising computer code configured to:

Select a number of rows of an encoding block arranged in rows and columns;

Fill the plurality of data packets into the columns of a encoding block by;

if a data packet has a size smaller than the selected number of rows, entering the data packet into a column and padding the remaining rows with at least one padding symbol;

or

if a data packet has size larger than the selected number of rows, allowing the data packet to span across multiple columns and -padding a last column spanned by the data packet with at least one padding symbol;

Append the filled encoding block with the FEC data blocks.

7. The computer code product of claim 6, wherein the number of rows is selected to equal an average size of the data packets.

8. The computer code product of claim 6, wherein the number of rows is selected based on the following algorithm:

$\mathrm{For}<br><br>\text{\hspace{1em}<br><br>}<br><br>j=1<br><br>\text{\hspace{1em}<br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{to}<br><br>\text{\hspace{1em}<br><br>}<br><br>M$ $\text{{}<br><br>\mathrm{Total\_padding}<br><br>\mathrm{\_j}=\underset{k=1}{\overset{M}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>\left(\mathrm{s\_j}\right)-\left[\left(\mathrm{s\_k}\right)<br><br>\mathrm{mod}<br><br>\left(\mathrm{s\_j}\right)\right]$ $\mathrm{If}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{Total\_padding}<br><br>\mathrm{\_j}<<br><br>\mathrm{Min\_Padding},<br><br>\mathrm{Then}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{Min\_padding}=\mathrm{Total\_padding}<br><br>\mathrm{\_j}<br><br><br><br>\mathrm{Number\_of}<br><br>\mathrm{\_rows}=\mathrm{s\_j}<br><br>\text{}}$ $\mathrm{Where}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{the}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{plurality}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{of}<br><br>\text{\hspace{1em}<br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{data}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{blocks}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{have}<br><br>\text{\hspace{1em}<br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{sizes}<br><br>\left\{\mathrm{s\_}<br><br>1,\mathrm{s\_}<br><br>2,\mathrm{s\_}<br><br>3<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{\dots <br><br>}<br><br>\text{\hspace{1em}<br><br>},\mathrm{s\_M}\right).$

9. The computer code product of claim 6, wherein the at least one padded symbol is zero.

10. The computer code product of claim 6, wherein the at least one padded symbol is an arbitrary symbol that is agreed between a sender and receiver.

11. An encoder configured for encoding a plurality of variable size data packets for FEC, the encoder comprising:

A processor;

Memory;

Wherein the processor is configured to Select a number of rows of an encoding block arranged in rows and columns;

Fill the plurality of data packets into the columns of a encoding block by;

if a data packet has a size smaller than the selected number of rows, entering the data packet into a column and padding the remaining rows with at least one padding symbol;

or

if a data packet has size larger than the selected number of rows, allowing the data packet to span across multiple columns and padding a last column spanned by the data packet with at least one padding symbol;

Form FEC data blocks; and

Append the filled encoding block with the FEC data blocks.

12. The encoder of claim 11, wherein the number of rows is selected to equal an average size of the data packets.

13. The encoder of claim 11, wherein the number of rows is selected based on the following algorithm:

$\mathrm{For}<br><br>\text{\hspace{1em}<br><br>}<br><br>j=1<br><br>\text{\hspace{1em}<br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{to}<br><br>\text{\hspace{1em}<br><br>}<br><br>M$ $\text{{}<br><br>\mathrm{Total\_padding}<br><br>\mathrm{\_j}=\underset{k=1}{\overset{M}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>\left(\mathrm{s\_j}\right)-\left[\left(\mathrm{s\_k}\right)<br><br>\mathrm{mod}<br><br>\left(\mathrm{s\_j}\right)\right]$ $\mathrm{If}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{Total\_padding}<br><br>\mathrm{\_j}<<br><br>\mathrm{Min\_Padding},<br><br>\mathrm{Then}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{Min\_padding}=\mathrm{Total\_padding}<br><br>\mathrm{\_j}<br><br><br><br>\mathrm{Number\_of}<br><br>\mathrm{\_rows}=\mathrm{s\_j}<br><br>\text{}}$ $\mathrm{Where}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{the}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{plurality}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{of}<br><br>\text{\hspace{1em}<br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{data}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{blocks}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{have}<br><br>\text{\hspace{1em}<br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{sizes}<br><br>\left\{\mathrm{s\_}<br><br>1,\mathrm{s\_}<br><br>2,\mathrm{s\_}<br><br>3<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{\dots <br><br>}<br><br>\text{\hspace{1em}<br><br>},\mathrm{s\_M}\right).$

14. The encoder of claim 11, wherein the at least one padding symbol is zero.

15. The encoder of claim 11, wherein the at least one padding symbol is an arbitrary symbol that is agreed between a sender and receiver.

16. A system for signaling a hybrid-padding method of encoding data packets, the system comprising:

A data packet including;

A source block number; and

A starting column number of the data packet; and

An error correction packet including;

A source block number;

A starting column number of the error correction packet;

A number of rows parameter;

An N RS-code parameter; and

A K RS-code parameter.

17. The system of claim 16, further comprising a real-time transmission protocol.

18. The system of claim 16, further comprising an optional packet length parameter which is used in an FEC encoding and decoding procedure but not signaled.

19. The system of claim 16, further comprising a real-time transmission protocol.