DEGREE REDUCTION AND DEGREE-CONSTRAINED COMBINING FOR RELAYING A FOUNTAIN CODE

• US 20140369253A1
• Filed: 05/30/2014
• Published: 12/18/2014
• Est. Priority Date: 06/12/2013
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: WU, Xinzhou, SUBRAMANIAN, Sundar, JOSE, Jubin, LI, Chong
• Granted Patent: US 9,369,920 B2
• Time in Patent Office: Days
• US Class Current: 370/315
• CPC Class Codes: H03M 13/3761 using code combining, i.e. using combining of codeword portions which may have been transmitted separately, e.g. Digital Fountain codes, Raptor codes or Luby Transform [LT] codes
• CPC Class Codes: H04L 1/0041 Arrangements at the transmitter end
• CPC Class Codes: H04L 1/0058 Block-coded modulation
• CPC Class Codes: H04L 1/0076 Distributed coding, e.g. network coding, involving channel coding coding in both space and time H04L1/0618; cooperative diversity H04B7/022
• CPC Class Codes: H04L 2001/0097 Relays
• CPC Class Codes: H04W 28/065 using assembly or disassembly of packets
• CPC Class Codes: H04W 4/80 Services using short range communication, e.g. near-field communication [NFC], radio-frequency identification [RFID] or low energy communication

Abstract

A method, an apparatus, and a computer program product for relaying a packet are provided. The apparatus receives at least one packet and reduces a degree of the at least one packet. The apparatus further processes the at least one packet based on the reduced degree, generates a combined packet by combining the at least one processed packet with at least one other processed packet based on the reduced degree and a weight of each of the processed packets, and transmits the combined packet.

Claims

1. A method of relaying a packet, comprising:

receiving at least one packet;

reducing a degree of the at least one packet;

processing the at least one packet based on the reduced degree;

generating a combined packet, the generating comprising combining the at least one processed packet with at least one other processed packet based on the reduced degree and a weight of each of the processed packets; and

transmitting the combined packet.

2. The method of claim 1, wherein the at least one packet received is encoded using a fountain code.

3. The method of claim 1, wherein the degree of the at least one packet comprises a number of native packets used to create the at least one packet.

4. The method of claim 1, the reducing comprising:

removing all native packets of the at least one packet that belong to a decoded set of native packets; and

removing any combination of two native packets of the least one packet that belong to a same equivalence class.

5. The method of claim 4, wherein an equivalence class comprises a set of native packets, wherein an exclusive-or operation of any two native packets in the equivalence class can be generated by performing an exclusive-or operation on degree-2 processed packets.

6. The method of claim 4, the processing comprising:

determining the reduced degree of the at least one packet;

when the reduced degree of the at least one packet is equal to one, the processing further comprising;

updating the decoded set with the at least one degree-reduced packet;

updating the decoded set based on belief propagation, and

updating equivalence classes based on the at least one degree-reduced packet; and

when the reduced degree of the at least one packet is equal to two, the processing further comprising updating the equivalence classes based on the at least one degree-reduced packet.

7. The method of claim 6, the generating the combined packet further comprising:

determining a target degree for the combined packet;

selecting at least one degree-reduced packet having a degree less than or equal to the target degree based on a weight assigned to each packet of the at least one packet; and

combining each of the at least one selected degree-reduced packet to generate the combined packet.

8. The method of claim 7, wherein the at least one degree-reduced packet is selected until a sum of respective degrees of selected packets is equal to the target degree, or until a maximum number of selections has occurred.

9. The method of claim 7, further comprising:

diversifying the combined packet comprising;

replacing a native packet in the combined packet with another native packet from the decoded set of native packets, and

replacing any native packet in the combined packet with another native packet that belongs to a same equivalence class.

10. An apparatus for relaying a packet, comprising:

means for receiving at least one packet;

means for reducing a degree of the at least one packet;

means for processing the at least one packet based on the reduced degree;

means for generating a combined packet, the means for generating configured to combine the at least one processed packet with at least one other processed packet based on the reduced degree and a weight of each of the processed packets; and

means for transmitting the combined packet.

11. The apparatus of claim 10, wherein the at least one packet received is encoded using a fountain code.

12. The apparatus of claim 10, wherein the degree of the at least one packet comprises a number of native packets used to create the at least one packet.

13. The apparatus of claim 10, the means for reducing configured to:

remove all native packets of the at least one packet that belong to a decoded set of native packets; and

remove any combination of two native packets of the least one packet that belong to a same equivalence class.

14. The apparatus of claim 13, wherein an equivalence class comprises a set of native packets, wherein an exclusive-or operation of any two native packets in the equivalence class can be generated by performing an exclusive-or operation on degree-2 processed packets.

15. The apparatus of claim 13, the means for processing configured to:

determine the reduced degree of the at least one packet;

when the reduced degree of the at least one packet is equal to one, the means for processing further configured to;

update the decoded set with the at least one degree-reduced packet;

update the decoded set based on belief propagation, and

update equivalence classes based on the at least one degree-reduced packet; and

when the reduced degree of the at least one packet is equal to two, the means for processing further configured to update the equivalence classes based on the at least one degree-reduced packet.

16. The apparatus of claim 15, the means for generating the combined packet further configured to:

determine a target degree for the combined packet;

select at least one degree-reduced packet having a degree less than or equal to the target degree based on a weight assigned to each packet of the at least one packet; and

combine each of the at least one selected degree-reduced packet to generate the combined packet.

17. The apparatus of claim 16, wherein the at least one degree-reduced packet is selected until a sum of respective degrees of selected packets is equal to the target degree, or until a maximum number of selections has occurred.

18. The apparatus of claim 16, further comprising:

means for diversifying the combined packet, configured to;

replace a native packet in the combined packet with another native packet from the decoded set of native packets, and

replace any native packet in the combined packet with another native packet that belongs to a same equivalence class.

19. An apparatus for relaying a packet, comprising:

a memory; and

at least one processor coupled to the memory and configured to;

receive at least one packet;

reduce a degree of the at least one packet;

process the at least one packet based on the reduced degree;

generate a combined packet, wherein the at least one processor configured to generate is further configured to combine the at least one processed packet with at least one other processed packet based on the reduced degree and a weight of each of the processed packets; and

transmit the combined packet.

20. The apparatus of claim 19, wherein the at least one packet received is encoded using a fountain code.

21. The apparatus of claim 19, wherein the degree of the at least one packet comprises a number of native packets used to create the at least one packet.

22. The apparatus of claim 19, wherein the at least one processor configured to reduce is further configured to:

remove all native packets of the at least one packet that belong to a decoded set of native packets; and

remove any combination of two native packets of the least one packet that belong to a same equivalence class.

23. The apparatus of claim 22, wherein an equivalence class comprises a set of native packets, wherein an exclusive-or operation of any two native packets in the equivalence class can be generated by performing an exclusive-or operation on degree-2 processed packets.

24. The apparatus of claim 22, wherein the at least one processor configured to process is further configured to:

determine the reduced degree of the at least one packet;

when the reduced degree of the at least one packet is equal to one, the at least one processor configured to process is further configured to;

update the decoded set with the at least one degree-reduced packet;

update the decoded set based on belief propagation, and

update equivalence classes based on the at least one degree-reduced packet; and

when the reduced degree of the at least one packet is equal to two, the at least one processor configured to process is further configured to update the equivalence classes based on the at least one degree-reduced packet.

25. The apparatus of claim 24, wherein the at least one processor configured to generate the combined packet is further configured to:

determine a target degree for the combined packet;

select at least one degree-reduced packet having a degree less than or equal to the target degree based on a weight assigned to each packet of the at least one packet; and

combine each of the at least one selected degree-reduced packet to generate the combined packet.

26. The apparatus of claim 25, wherein the at least one degree-reduced packet is selected until a sum of respective degrees of selected packets is equal to the target degree, or until a maximum number of selections has occurred.

27. The apparatus of claim 25, wherein the at least one processor is further configured to:

diversify the combined packet, wherein the at least one processor configured to diversify is further configured to;

replace a native packet in the combined packet with another native packet from the decoded set of native packets, and

replace any native packet in the combined packet with another native packet that belongs to a same equivalence class.

28. A computer program product stored on a computer-readable medium and comprising code that when executed on at least one processor performs the steps of:

receiving at least one packet;

reducing a degree of the at least one packet;

processing the at least one packet based on the reduced degree;

generating a combined packet, the generating comprising combining the at least one processed packet with at least one other processed packet based on the reduced degree and a weight of each of the processed packets; and

transmitting the combined packet.